[XML-SIG] Major upcoming DOM changes in CVS

[Andrew M. Kuchling]

Greg Stein writes:
>post-DOM-construction walk of the DOM tree). Each element can define any
>number of prefixes, so my stack is a list (one item per element depth)
>of dictionaries (prefix to URI mapping). When an element "starts", I

	I could do that, keeping a dictionary on each _nodeData
instance.  Finding the namespace for a given prefix is then
proportional to the height of the DOM tree, because you have to start
at the node and scan back toward the root.  A common operation is
likely to be "find attribute X in namespace with URI Y", and that
would be terribly slow; scan back until you find a namespace
declaration with URI Y, and then check for an attribute with that
prefix.  That's O(height of tree * # of attributes), but I can't think
of a better way.

	It would obviously be better to store a cumulative map on each
node, reducing the height-of-tree factor to a constant, but I'm
frightened of that approach, fearing it'll make changing the tree
expensive or difficult, since you'd either have to recompute the maps
on an entire subtree every time you change an attribute or move
something around (expensive), or use smart updating to saveCPU time
(difficult, and potentially a source of bugs from complicated updating
logic).

	In a recent xml-dev posting, David Megginson mentioned that
some implementors are turning the element names into longer,
"URI-prefix tagName" strings, like "http://www.w3.org/RDF rdf".  This
is apparently of dubious legality, but it gets their job done.  I
think it's an ugly hack, myself...

-- 
A.M. Kuchling			http://starship.python.net/crew/amk/
REMIND ME AGAIN, he said, HOW THE LITTLE HORSE-SHAPED ONES MOVE.
    -- Death on symbolic last games, in Terry Pratchett's _Small Gods_