Cursors, Trees, and Document Object Models

Internal Document Representation in the PIA.

Architectural Notes

World domination.
--Linus Torvalds (emphasis added)

This section was originally in ../roadmap.html. Note that much of the work described has been completed, so this document now contains a mixture of future work and historical data.

The Two Great World Systems

Linguistic side-note:

In paleontology, ``cursorial'' refers to the hypothesis that dinosaurs evolved into birds by running after flying insects with their (feathered) forelimbs outstretched as catchers. This contrasts with the ``arboreal'' hypothesis that wings evolved to improve dinosaurs' ability to jump out of trees.

Historical side-note:

Dialog of the Two Great World Systems was the title of Galileo's (rather one-sided) comparison of the Ptolemaic and Copernican representations of the universe.

Trees

The DOM presently DOMinates the field of Java representations for XML documents (parse trees). Essentially, it's the only game in town. Unfortunately it has some problems:

• Live NodeList's are notoriously hard to implement efficiently.
• There is currently no defined way to create a DOM Level 2 Iterator from a NodeList or NamedNodeMap.
• The obvious representation as doubly-linked trees has quite a lot of storage and processing overhead.
• There is simply no way to move a node from one document to another, or to have an isolated node that is not part of a document.
• There is no representation for element or attribute definitions in the DocumentType interface, so a DTD cannot be completely represented.
• Information about quote characters, implied end tags (in HTML), and so on is lost. It is impossible to reconstruct a document from its DOM representation.

Also, there is no place in the DOM for the kind of metadata (e.g., handlers) that the DPS needs in order to do its job. This by itself is enough to require the PIA to have its own implementation of the DOM, although it's not totally impossible that metadata might not end up in some future level of the DOM.

Cursors

The DPS notion of a Cursor evolved out the (subsequently abandoned, now back in Level 2) DOM interface TreeIterator. The basic idea is that a Cursor allows the DPS to traverse a DOM tree, or what appears to be a DOM tree, without actually looking at the DOM nodes themselves.

Presently there is a lot of leakage between the DOM and the DPS, and the current version of Cursor actually does allow (and in fact require) access to the DOM node. This can be fixed, however. The goal is for the Cursor to allow complete access to all of a Node's attributes without allowing access to the Node itself.

The result would be a purely ``cursorial'' interface to documents, completely independent of the DOM's ``arboreal'' interfaces.

An additional, worthwhile extension to cursors would be permitting a cursor to represent a CharData node (i.e. text, comments, etc.) as a string without the actual node having to exist. This might even apply more generally to nodes with NodeList values. The result would be significantly less node creation.

Benefits

• By reducing the number of things in the PIA that actually depend on the DOM interfaces, it would be easier to transition the PIA from the old DOM interfaces it is using now to the current, official ones.
• Any DOM could be ``dropped in'' by providing suitable cursors.
• The PIA can operate by side-stepping the DOM's interfaces rather than by abusing them, as it presently does.
• The PIA is free to evolve away from the DOM's object model to something perhaps lighter-weight and less restrictive.
• It becomes easier to ``wrap'' non-DOM data structures, since the wrapper doesn't have to look like a DOM tree. In fact, it is not necessary to modify the wrapped object at all -- just provide a cursor for it.

Getting there

There are two distinct routes to a split model with an upgraded DOM:

1. Upgrade the PIA's DOM implementation to the current standard, then upgrade Cursor and the DPS to eliminate direct use of the DOM's interfaces.
2. Upgrade Cursor and the DPS to be totally DOM-independent, then fix the DOM implementation.

The second path is basically cleaner, but the first would get us to DOM compliance more quickly, and integrates better with the other near-term goal of an XML representation for Agents. We have chosen the first route, and the DOM re-implementation has been completed.

Design Notes

This section was originally in ../projects.html.

Possible name: GLOM (Generic Lightweight Object Model). Other possibilities include Dlite, DOC (Document Object Cursors), ...

Relationship to the DOM

The problem is that once you start using the DOM, you're pretty-well stuck with it, including all its unsuitable characteristics: lack of DTD coverage, live nodelists, fragile iterators, doubly-linked trees, total inability to move nodes between documents, and so on.

Our representation needs to be compatible with but disjoint from the DOM. Our trees should have both a DOM interface (for compatibility with other tools) and our own; the DPS should use only our own interface.

Insisting that parse trees be immutable fixes many of the DOM's problems. There are still some problems with entities, but we can gloss over that: if you're redefining entities you're by definition outside of the DOM.

Desirable Characteristics

• The interfaces seen by the DPS should be purely navigational: you never actually point to a DOM node, only navigate among them. This gives total isolation from the implementation. In other words we use cursors.
• For putting things into containers, we will want wrappers (handles?) and wrapper factories. These will go along with the cursors and their factories. They will basically be cursors without navigation. The usual tree nodes, of course, will not need wrappers.
• Active objects like tagsets, namespaces, and agents might be DOM nodes underneath, but we ignore that and use only their interfaces. They can be constructed either declaratively (by reading) or procedurally (by tree manipulation).

Bascally what we're doing is splitting up the DOM interfaces into two pieces: the informational and the navigational. We want to be able to get at the attributes, content/value/children, and text of our nodes without worrying about the connections among them.

Of course, in addition to the DOM attributes, we also want to get at the DPS attributes of our objects: action, syntax, key (for sorting and extraction), etc.

Where Things Go

There are three possibilities:

1. Move the ActiveNode interfaces to org.risource.dom.active, and the implementations to org.risource.dom.tree. Move Cursor and related stuff to, perhaps, org.risource.dom.cursor. Blow away org.risource.dps.active or use it for purely DPS-specific stuff (which might be hard to find). It's rather hard to justify having the ActiveNode interfaces under the DOM, but it does mean that org.risource.dom and its sub-directories constitute a completely stand-alone implementation of the DOM.
2. Move the implementations to org.risource.dps.tree. Blow away org.risource.dom or use it for utilities that use only the org.w3c.dom interfaces. This leaves org.risource.dps and its sub-packages as a stand-alone document processor. If the DOM and DPS go their separate ways, nobody will notice.
3. Move the implementations to org.risource.dom.tree but leave the ActiveNode interfaces in org.risource.dps.active. In this case, neither org.risource.dom nor org.risource.dps can stand alone, but minimal damage is done to the existing directory structure (tree is added, but nothing goes away). The way is still open to a totally DOM-free version of the DPS.

We have taken the middle way.

Implementation

There are basically three ways to proceed:

1. Blow away the old DOM interfaces in org.risource.dom, put the new interfaces in place, move the implementation to org.risource.dom.tree, and basically go to completion in one step. This leaves the working copy of the PIA out of commission for the longest time.
2. Develop new working copies of the mixed (ActiveNode) interfaces and their implementation. Then switch the DPS over, using the mixed interfaces until we can shift it from ``arboreal'' to purely ``cursorial'' form. This is the fastest route to DOM compliance.
3. Switch the DPS over to being purely cursorial. Then drop in the new ActiveNode implementation.

The nice thing about the middle path is that it is the most incremental and least disruptive. It proceeds very quickly to a compliant DOM implementation, then merges it in. It does mean several different disruptions, but at least they would be fairly short ones. It also means that things can go under source control before work is complete.

During the transition, the ActiveNode interfaces will continue to be used in the DPS. Afterward, they will be used only in the cursor implementations.