.TLNavigating Large XML Documents on Small Devices.AURoger Peppe.AIVita Nuova.brApril 2002.ABBrowsing eBooks on platforms with limited memory presents aninteresting problem: how can memory usage be bounded despitethe need to view documents that may be much larger than theavailable memory. A simple interface to an XML parser enablesthis whilst retaining much of the ease of access affordedby XML parsers that read all of a document into memory at once..AE.SHIntroduction.LPThe Open Ebook Publication Structure was devised by the Open Ebook Forumin order to ``provide a specification for representing the content of electronicbooks''. It is based on many existing standards, notably XML and HTML.An Open eBook publication consists of a set of documents bound togetherwith an Open eBook package file which enumerates all the documents,pictures and other items that make up the book.LPThe underlying document format is essentially HTML compatible,which is where the first problem arises: HTML was not designed tomake it easy to view partial sections of a document. Conventionallyan entire HTML document is read in at once and rendered ontothe device. When viewing an eBook on a limited-memory device,however, this may not be possible; books tend to be fairly large.For such a device, the ideal format would keep the book itselfin non-volatile storage (e.g. flash or disk) and make it possiblefor reader to seek to an arbitrary position in the book and renderwhat it finds there..LPThis is not possible in an HTML or XML document, as thearbitrarily nested nature of the format means that everyposition in the document has some unknown surrounding context,which cannot be discovered without reading sequentially throughthe document from the beginning..SHSAX and DOM.LPThere are two conventional programming interfaces to an XMLparser. A SAX parser provides a stream of XML entities, leavingit up to the application to maintain the context. It is not possibleto rewind the stream, except, perhaps, to the beginning.Using a SAX parser isfairly straightforward, but awkward: the stream-like natureof the interface does not map well to the tree-like structurethat is XML. A DOM parser reads a whole document into an internaldata structure representation, so a program can treat it exactlyas a tree. This also enables a program to access parts of thedocument in an arbitrary order.The DOM approach is all very well for small documents, but for largedocuments the memory usage can rapidly grow to exceedthe available memory capacity. For eBook documents, this is unacceptable..SHA different approach.LPThe XML parser used in the eBook browser is akin to a SAX parser,in that only a little of the XML structure is held in memory at one time.The first significant difference is that the XML entities returned aretaken from one level of the tree - if the program does not wish tosee the contents of a particular XML tag, it is trivial to skip over.The second significant difference is that random access is possible.This possibility comes from the observation that if we have visiteda part of the document we can record the context that we found thereand restore it later if necessary. In this scheme, if we wish to return later toa part of a document that we are currently at, we can create a ``mark'',a token that holds the current context; at some later time we can usethat mark to return to this position..LPThe eBook browser uses this technique to enable random accessto the document on a page-by-page basis. Moreover a markcan be written to external storage, thus allowing an external``index'' into the document so it is not always necessary toread the entire document from the start in order to jump to a particularpage in that document..SHThe programming interface.LPThe interface is implemented by a module named.CW Xml ,which provides a.CW Parseradt which gives access to the contents of an XML document.Xml items are represented by an.CW Itempick adt with one branch of the pick corresponding to eachtype of item that might be encountered..LPThe interface to the parser looks like this:.P1open: fn(f: string, warning: chan of (Locator, string)): (ref Parser, string);Parser: adt {    next:       fn(p: self ref Parser): ref Item;    down:   fn(p: self ref Parser);    up:     fn(p: self ref Parser);    mark:   fn(p: self ref Parser): ref Mark;    atmark: fn(p: self ref Parser, m: ref Mark): int;    goto:   fn(p: self ref Parser, m: ref Mark);    str2mark:   fn(p: self ref Parser, s: string): ref Mark;};.P2To start parsing an XML document, it must first be.CW open ed;.CW warningis a channel on which non-fatal error messages will be sentif they are encountered during the parsing of the document.It can be nil, in which case warnings are ignored.If the document is opened successfully, a new.CW Parseradt, say.I p ,is returned.Calling.CW \fIp\fP.nextreturns the next XML item at the current level of the tree. If thereare no more items in the current branch at the current level, itreturns.CW nil .When a.CW Tagitem is returned,.CW \fIp\fP.downcan be used to descend ``into'' that tag; subsequent calls of.CW \fIp\fP.nextwill return XML items contained within the tag,and.CW \fIp\fP.upreturns to the previous level..LPAn.CW Itemis a pick adt:.P1Item: adt {    fileoffset: int;    pick {    Tag =>        name:   string;        attrs:      Attributes;    Text =>        ch:     string;        ws1, ws2: int;    Process =>        target: string;        data:       string;    Doctype =>        name:   string;        public: int;        params: list of string;    Stylesheet =>        attrs:      Attributes;    Error =>        loc:        Locator;        msg:        string;    }};.P2.CW Item.Tagrepresents a XML tag, empty or not. The XMLfragments.CW "<tag></tag>" '' ``and.CW "<tag />" '' ``look identical from the point of view of this interface.A.CW Textitem holds text found in between tags, with adjacent whitespaces mergedand whitespace at the beginning and end of the text elided..CW Ws1and.CW ws2are non-zero if there was originally whitespace at the beginningor end of the text respectively..CW Processrepresents an XML processing request, as found between.CW "<?....?>" '' ``delimiters..CW Doctypeand.CW Stylesheetare items found in an XML document's prolog, theformer representing a.CW "<!DOCTYPE...>" '' ``document type declaration, and the latter an XMLstylesheet processing request..LPWhen most applications are processing documents, theywill wish to ignore all items other than.CW Tagand.CW Text .To this end, it is conventional to define a ``front-end'' functionto return desired items, discard others, and take an appropriateaction when an error is encountered. Here's an example:.P1nextitem(p: ref Parser): ref Item{    while ((gi := p.next()) != nil) {        pick i := gi {        Error =>            sys->print("error at %s:%d: %s\n",                i.loc.systemid, i.loc.line, i.msg);            exit;        Process =>            ;   # ignore        Stylesheet  =>            ;   # ignore        Doctype =>            ;   # ignore        * =>            return gi;        }    }    return nil;}.P2When.CW nextitemencounters an error, it exits; it might instead handle theerror another way, say by raising an exception to be caught at theoutermost level of the parsing code..SHA small example.LPSuppose we have an XML document that contains some data that we wouldlike to extract, ignoring the rest of the document. For this example we willassume that the data is held within.CW <data>tags, which contain zero or more.CW <item>tags, holding the actual data as text within them.Tags that we do not recognize we choose to ignore.So for example, given the following XML document:.P1<metadata>    <a>hello</a>    <b>goodbye</b></metadata><data>    <item>one</item>    <item>two</item>    <item>three</item></data><data>    <item>four</item></data>.P2we wish to extract all the data items, but ignore everything insidethe.CW <metadata>tag. First, let us define another little convenience function to getthe next XML tag, ignoring extraneous items:.P1nexttag(p: ref Parser): ref Item.Tag{    while ((gi := nextitem(p)) != nil) {        pick i := gi {        Tag =>            return i;        }    }    return nil;}.P2Assuming that the document has already been opened,the following function scans through the document, lookingfor top level.CW <data>tags, and ignoring others:.P1document(p: ref Parser){    while ((i := nexttag(p)) != nil) {        if (i.name == "data") {            p.down();            data(p);            p.up();        }    }}.P2The function to parse a.CW <data>tag is almost as straightforward; it scans for.CW <item>tags and extracts any textual data contained therein:.P1data(p: ref Parser){    while ((i := nexttag(p)) != nil) {        if (i.name == "item") {            p.down();            if ((gni := p.next()) != nil) {                pick ni := gni {                Text =>                    sys->print("item data: %s\n", ni.ch);                }            }            p.up();        }    }}.P2The above program is all very well and works fine, butsuppose that the document that we are parsing is verylarge, with data items scattered through its length, and thatwe wish to access those items in an order that is not necessarilythat in which they appear in the document.This is quite straightforward; every time we see adata item, we record the current position with a mark.Assuming the global declaration:.P1marks: list of ref Mark;.P2the.CW documentfunction might become:.P1document(p: ref Parser){    while ((i := nexttag(p)) != nil) {        if (i.name == "data") {            p.down();            marks = p.mark() :: marks;            p.up();        }    }}.P2At some later time, we can access the data items arbitrarily,for instance:.P1    for (m := marks; m != nil; m = tl m) {        p.goto(hd m);        data(p);    }.P2If we wish to store the data item marks in some external index(in a file, perhaps), the.CW Markadt provides a.CW strfunction which returns a string representation of the mark..CW Parser 's.CW str2markfunction can later be used to recover the mark. Care mustbe taken that the document it refers to has not been changed,otherwise it is likely that the mark will be invalid..SHThe eBook implementation.LPThe Open eBook reader software uses the primitives described aboveto maintain display-page-based access to arbitrarily large documentswhile trying to bound memory usage.Unfortunately it is difficult to unconditionally bound memory usage,given that any element in an XML document may be arbitrarilylarge. For instance a perfectly legal document might have 100MBof continuous text containing no tags whatsoever. The describedinterface would attempt to put all this text in one single item, rapidlyrunning out of memory! Similar types of problems can occur whengathering the items necessary to format a particular tag.For instance, to format the first row of a table, it is necessary to lay outthe entire table to determine the column widths..LPI chose to make the simplifying assumption that top-level items withinthe document would be small enough to fit into memory.From the point of view of the display module, the documentlooks like a simple sequence of items, one after another.One item might cover more than one page, in which case a differentpart of it will be displayed on each of those pages..LPOne difficulty is that the displayed size of an item depends on manyfactors, such as stylesheet parameters, size of installed fonts, etc.When a document is read, the page index must have been createdfrom the same document with the same parameters. It is difficult ingeneral to enumerate all the relevant parameters; they would needto be stored inside, or alongside the index; any change would invalidatethe index. Instead of doing this, as the document is being displayed,the eBook display program constantly checks to see if the resultsit is getting from the index match with the results it is gettingwhen actually laying out the document. If the results differ, theindex is remade; the discrepancy will hopefully not be noticed bythe user!