Bug 12359 - XPathEvaluator may return some nodes more than once in a result set
Summary: XPathEvaluator may return some nodes more than once in a result set
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: XML (show other bugs)
Version: 420+
Hardware: Mac OS X 10.4
: P2 Normal
Assignee: Alexey Proskuryakov
URL: http://andrewdupont.net/test/double-d...
Keywords:
Depends on:
Blocks:
 
Reported: 2007-01-21 20:22 PST by Andrew Dupont
Modified: 2007-01-29 10:25 PST (History)
2 users (show)

See Also:


Attachments
Reduced test case (799 bytes, text/html)
2007-01-21 20:43 PST, Andrew Dupont
no flags Details
proposed fix (5.99 KB, patch)
2007-01-28 11:27 PST, Alexey Proskuryakov
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Dupont 2007-01-21 20:22:46 PST
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.
Comment 1 David Kilzer (:ddkilzer) 2007-01-21 20:29:31 PST
Andrew, could you upload a reduced test case?  This would be very helpful in resolving this bug.  Thanks!

Comment 2 Andrew Dupont 2007-01-21 20:43:54 PST
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).
Comment 3 Alexey Proskuryakov 2007-01-28 11:27:12 PST
Created attachment 12729 [details]
proposed fix
Comment 4 Darin Adler 2007-01-28 18:27:37 PST
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
Comment 5 Alexey Proskuryakov 2007-01-29 10:25:04 PST
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 :)