Bug 12359 – XPathEvaluator may return some nodes more than once in a result set

• Component: XML
• Status: RESOLVED FIXED

[Andrew Dupont]

While working on routing CSS selector queries through XPath for performance, I noticed that WebKit's version of document.evaluate doesn't ensure uniqueness of the result set.  At the test URL, you'll notice that some queries -- like "div div" (or in XPath: ".//div//div" -- fail: the length of the result set is far larger than it should be because a DIV with two DIV ancestors would occur twice.  This is different from the behavior of Firefox or Opera.  Filtering for uniqueness in my own code solves this problem.

Discovered using document.evaluate with result set of type ORDERED_NODE_SNAPSHOT_TYPE.

[David Kilzer (:ddkilzer)]

Andrew, could you upload a reduced test case?  This would be very helpful in resolving this bug.  Thanks!

[Andrew Dupont]

Created attachment 12597 [details]
Reduced test case

Illustrates the example in the above comment.  Firefox returns 2 results; WebKit returns 3 (counting the innermost DIV twice).

[Alexey Proskuryakov]

Created attachment 12729 [details]
proposed fix

[Darin Adler]

Comment on attachment 12729 [details]
proposed fix

+                if (!outDOMNodesSet.contains(node)) {
+                    outDOMNodes.append(node);
+                    outDOMNodesSet.add(node);
+                }

This can be done more efficiently by taking advantage of the return value from add. Like this:

    if (outDOMNodesSet.add(node).second)
        outDOMNodes.append(node);

I know it's a little ugly, but I love the fact that it cuts the number of hash table lookups roughly in half, so please consider this idiom.

r=me

[Alexey Proskuryakov]

Committed revision 19227.

(In reply to comment #4)
> I know it's a little ugly, but I love the fact that it cuts the number of hash
> table lookups roughly in half, so please consider this idiom.

Oops - corrected! I should be more critical of idioms used in existing code :)