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 17:19:53 -0500
Message-ID: <363F8189.CCE271@locke.ccil.org>
To: DOM List <www-dom@w3.org>
Stephen R. Savitzky wrote:

> > > 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.
> 
> AHA!  If it's ``presumed static'', then your NodeList's aren't live!

Distinguo.  I have two hats, DOM implementer and DOM consumer.  This
algorithm is used by DOMParser, which is a DOM-consuming algorithm.
DOMParser's contract *assumes* that the DOM is stable: that the build
is complete and that the application is not modifying the DOM.
If either condition doesn't apply, you can't call DOMParser.

As a DOM implementer, I have to deal with the DOM's liveness.
I can't say (as you can), "Well, my implementation does most of the
DOM but not all."  A library that does that just isn't a DOM
implementation, whatever its other virtues.

> My whole point is that _with_ live NodeLists, the simple, sane, obvious,
> lowest-common-denominator implementation becomes impossible.

This is plainly too strong.  A stupid implementation of NodeLists
(and I assume here we are talking only about the NodeLists from
getElementsByTagName; the ones from childNodes are easy to make live),
one that recomputes the nth node from scratch on every call, will work
fine with O(1) structure modification.

You can even keep structure modification O(1) and avoid the totally
naive implementation of NodeLists by keeping a modification timestamp
in every NodeList and in the Document object.  IOW, recompute from
scratch if the NodeList is out of date.  (The "timestamp" needn't
be UTC time, as long as it is monotonically increasing with every
modification.)

My problem at present: is that sufficient, or do I need to do more?
 
> The whole problem with NodeList as specified is _precisely_ that it breaks
> the encapsulation of Node by rendering this straightforward implementation
> invalid.

Again, I think this is untrue: one's instincts revolt against the
O(n^2) implementation of NodeList, but it's not *illegal*.

> My point is that the problem is not with your implementation, but with the
> specification.

Can't be helped.  No spec is perfect, nor any implementation, but
I can't just discard parts of the spec I don't like.

-- 
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 17:18:52 GMT

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