Bug 9467 – TreeWalker/NodeIterator do not restrict the traversal

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Graham Dennis]

When setting a root object for a TreeWalker or NodeIterator object, this only sets the starting point for iteration, and successively calling nextNode on either of these objects will result in nodes outside of the root node. 

This would appear to be caused by the calls to traverseNextNode() in NodeIterator/TreeWalker not restricting themselves to within the root of the iterator.

On a side note, bug #3492 mentions that TreeWalker is broken in more serious ways, and I suspect that some of the problems mentioned also apply to NodeIterator.

[Graham Dennis]

Created attachment 8965 [details]
testcase

testcase using javascript to demonstrate the bug.

[Graham Dennis]

Created attachment 8966 [details]
patch

This patch fixes the problem. However, it does not pass the traversal layout tests (it passes all other tests), but I believe that this is in fact a bug in the other traversal layout tests. This is most definitely the case for the TreeWalker layout tests, as they set the root element to be (e.g. <span id="A">) and then expect the TreeWalker to reach a sibling span (e.g. <span id="B">). In the NodeIterator case, it is not immediately clear to me whether or not the 'root' node specified in the interator is simply a starting point, or a root node that should not be left. The w3c Recommendation for the DOM level 2 traversal interface says:
"Iterators are used to step through a set of nodes, e.g. the set of nodes in a NodeList, the document subtree governed by a particular Node..."
Because of this I am inclined to believe that the root node is not to be exited for a NodeIterator as well. However, it does still sound a bit ambiguous to me.

I have not modified the other traversal testcases in this patch (as I am not certain that they are in fact wrong).

[Darin Adler]

Comment on attachment 8966 [details]
patch

Seems low risk to make an incremental improvement to these classes since they are broken in major ways.

But I do not understand the need for changes to Node.cpp. Before I can review+ this I need to understand why that file had to change at all. And in fact, those functions are used heavily all over the code, so changes to them are high risk and need a motivation.

And we need a change log entry too.

[Graham Dennis]

(In reply to comment #3)
> But I do not understand the need for changes to Node.cpp. Before I can review+
> this I need to understand why that file had to change at all. And in fact,
> those functions are used heavily all over the code, so changes to them are high
> risk and need a motivation.
My concern was that the 'stayWithin' argument could not have been an ancestor of the current node when doing any traversals. What I didn't realise is that the only way this can happen from external code is through a 'setCurrentNode' call on a TreeWalker. So it would be better to test there instead of modifying all the traversal functions. I will put together another patch with a changelog, the changes to the traversal testcases and removing these changes to Node.cpp.

However, is it reasonable to add a 'stayWithin' parameter to the traversePreviousNode call (for use by TreeWalker/NodeIterator), or is it better to do the test ensuring that they stay within the root node (for backward iteration) in the traversal classes?

[Graham Dennis]

Created attachment 8981 [details]
patch 2

This patch removes my unnecessary changes to the traverse* functions in Node.cpp. The only code I have changed in Node.cpp is adding a stayWithin argument to traversePreviousNode. I have also modified the affected traversal tests included an additional test.

ChangeLog entries included.

[Darin Adler]

Comment on attachment 8981 [details]
patch 2

The reason that traversePreviousNode does not have a "stayWithin" argument is that it's trivial to stay within a node with traversePreviousNode without it. You just write this:

    for (Node* n = first; n && n != stayWithin; n = n->traversePreviousNode())

That would not work with traverseNextNode or with traversePreviousNodePostOrder, which is why those have a stayWithin parameter.

That having been said, I suppose we could still add the parameter to traversePreviousNode for ease of understanding the function -- I have mixed feelings about it.

I'll review the rest of the patch soon.

[Darin Adler]

Comment on attachment 8981 [details]
patch 2

r=me

[Alexey Proskuryakov]

Committed revision 15009.