# Implementing Pull Parsing

by Peter B. West

- An alternative parsing methodology
  - Structure of SAX parsing
  - Cluttered callbacks
  - From push to pull parsing
  - FoXMLEvent me[thods
  - FOP modularisation

### An alternative parsing methodology

This note proposes an alternative method of integrating the output of the SAX parsing of the Flow Object (FO) tree into FOP processing. The pupose of the proposed changes is to provide for:

- better decomposition of FOP into processing phases
- top-down FO tree building, providing
- integrated validation of FO tree input.

#### Structure of SAX parsing

Figure 1 is a schematic representation of the process of SAX parsing of an input source. SAX parsing involves the registration, with an object implementing the XMLReader interface, of a ContentHandler which contains a callback routine for each of the event types encountered by the parser, e.g., startDocument(), startElement(), characters(), endElement() and endDocument(). Parsing is initiated by a call to the parser() method of the XMLReader. Note that the call to parser() and the calls to individual callback methods are synchronous: parser() will only return when the last callback method returns, and each callback must complete before the next is called.
Figure 1

In the process of parsing, the hierarchical structure of the original FO tree is flattened into a number of streams of events of the same type which are reported in the sequence in which they are encountered. Apart from that, the API imposes no structure or constraint which expresses the relationship between, e.g., a startElement event and the endElement event for the same element. To the extent that such relationship information is required, it must be managed by the callback routines.

The most direct approach here is to build the tree "invisibly"; to bury within the callback routines the necessary code to construct the tree. In the simplest case, the whole of the FO tree is built within the call to parser(), and that in-memory tree is subsequently processed to (a) validate the FO structure, and (b) construct the Area tree. The problem with this approach is the potential size of the FO tree in memory. FOP has suffered from this problem in the past.

#### Cluttered callbacks

On the other hand, the callback code may become increasingly complex as tree validation and the triggering of the Area tree processing and subsequent rendering is moved into the callbacks, typically the endElement() method. In order to overcome acute memory problems, the FOP code was recently modified in this way, to trigger Area tree building and rendering in the endElement() method, when the end of a page-sequence was detected.

The drawback with such a method is that it becomes difficult to detemine the order of events and the circumstances in which any particular processing events are triggered. When the processing events are inherently self-contained, this is irrelevant. But the more complex and context-dependent the relationships are among the processing elements, the more obscurity is engendered in the code by such "side-effect" processing.

#### From push to pull parsing

In order to solve the simultaneous problems of exposing the structure of the processing and minimising in-memory requirements, the experimental code separates the parsing of the input source from the building of the FO tree and all downstream processing. The callback routines become minimal, consisting of the creation and buffering of XMLEvent objects as a producer. All of these objects are effectively merged into a single event stream, in strict event order, for subsequent access by the FO tree building process, acting as a consumer. This, essentially, is the difference between push and pull parsing. In itself, this does not reduce the footprint. This occurs when the approach is generalised to modularise FOP processing.
Figure 2

The most useful change that this brings about is the switch from passive to active XML element processing. The process of parsing now becomes visible to the controlling process. All local validation requirements, all object and data structure building, are initiated by the process(es) getting from the queue - in the case above, the FO tree builder.

#### FoXMLEvent methods

The experimental code uses a class FoXMLEvent to provide the objects which are placed in the queue. FoXMLEvent includes a variety of methods to access elements in the queue. Namespace URIs encountered in parsing are maintained in an XMLNamespaces object where they are associated with a unique integer index. This integer value is used in the signature of some of the access methods.

The class which manages the buffer is SyncedFoXmlEventsBuffer.

FoXMLEvent getEvent(SyncedCircularBuffer events)
  This is the basis of all of the queue access methods. It returns the next element from the queue, which may be a pushback element.
FoXMLEvent getTypedEvent()
  A series of these methods provide for the recovery only of events of a particular event type, and possibly other specific characteristics. Get methods discard input which does not meet the requirements. E.g.
  FoXMLEvent getEndDocument()
    Discard input until and EndDocument event occurs. Return this event.
  FoXMLEvent getStartElement()
    A series of getStartElement methods provide for discarding input until a StartElement event of the appropriate type occurs. This event is returned. This series of methods includes some which accept a list of Element specifiers.
FoXMLEvent expectTypedEvent()
  A series of these methods provide for the recovery only of events of a particular event type, and possibly other specific characteristics. Expect methods throw an exception on input which does not meet the requirements. Expect methods generally take a boolean argument specifying whitespace treatment. Examples include:
  FoXMLEvent expectEndDocument()
    Expect an EndDocument event. Return this event.
  FoXMLEvent expectStartElement()
    A series of expectStartElement methods provide for examinging the pending input for a StartElement event of the appropriate type. This event is returned. This series of methods includes some which accept a list of Element specifiers.

#### FOP modularisation

This same principle can be extended to the other major sub-systems of FOP processing. In each case, while it is possible to hold a complete intermediate result in memory, the memory costs of that approach are too high. The sub-systems - xml parsing, FO tree construction, Area tree construction and rendering - must run in parallel if the footprint is to be kept manageable. By creating a series of producer-consumer pairs linked by synchronized buffers, logical isolation can be achieved while rates of processing remain coupled. By introducing feedback loops conveying information about the completion of processing of the elements, sub-systems can dispose of or precis those elements without having to be tightly coupled to downstream processes.
Figure 3

In the case of communication between the FO tree building process and the layout process, feedback is required in order to parse expressions containing lengths expressed as a percentage of some enclosing area. This communication is incorporated within the general model of inter-phase communication discussed above.
Figure 4