W3C home > Mailing lists > Public > www-dom@w3.org > October to December 1998

Re: Walking the DOM (was: XML APIs)

From: John Cowan <cowan@locke.ccil.org>
Date: Tue, 03 Nov 1998 15:29:42 -0500
Message-ID: <363F67B6.927F8C90@locke.ccil.org>
To: DOM List <www-dom@w3.org>
Stephen R. Savitzky wrote:

> I find this quite insulting.  My intent was to illustrate a rhetorical
> point, not to give an optimal, industrial-strength algorithm for tree
> traversal under all circumstances.

No offense intended.  I posted two responses (though without explaining
why) in order to separate my two issues: why the DOM isn't really a
tree (because it is "live" in my sense, subject to arbitrary changes
from outside), and to talk about the specifics of iteration vs.
recursion when walking trees.

> You _do_ further illustrate my point, however: the algorithm you give fails
> as miserably as mine if your visit or revisit function modifies the tree.

Absolutely true.

> > Because of the reliability of this algorithm vis-a-vis the recursive
> > one, I believe it should be the standard way of walking DOM trees,
> > and therefore it is essential that DOM implementations make the
> > structural access methods fast.
> 
> We are in agreement here,

Excellent!

> but I think you may have missed something.  An
> iterator, the state of which consists of a reference to the ``current
> node'', and all of whose methods are inlineable, can be compiled by a good
> optimizing compiler into the exact equivalent of your algorithm.

Can you sketch this for me?  I don't see how the recursive depth-search
can be optimized away, since the iterative version depends on the
existence of the parent pointer, which the original algorithm did not
even mention.  The breadth-search is obviously tail recursive and
no fundamental problem.

> An iterator that has to take structural changes into account _cannot_ be so
> compiled; it is necessarily going to be _FAR_ less efficient.

Agreed.

> Similarly,
> your algorithm cannot be used as the basis for a live NodeList.

No, indeed.  It is used in my DOMParser, which walks a (presumed static)
DOM in order to generate SAX events from the nodes.

> I believe
> it is also essential that DOM implementations make structural _modification_
> methods fast, which is also incompatible with the kind of non-locality of
> effects imposed by live NodeLists and ``robust'' (in your definition)
> iterators.

I hope that it is *not* utterly incompatible, but of course "fast"
is a loosely defined term; if you mean O(1), you are probably
correct.  I concede that I don't yet see how best to
do it, which is (one reason) why I have not published a DOM
implementation.

-- 
John Cowan	http://www.ccil.org/~cowan		cowan@ccil.org
	You tollerday donsk?  N.  You tolkatiff scowegian?  Nn.
	You spigotty anglease?  Nnn.  You phonio saxo?  Nnnn.
		Clear all so!  'Tis a Jute.... (Finnegans Wake 16.5)
Received on Tuesday, 3 November 1998 15:28:41 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 22 June 2012 06:13:46 GMT