Bug 119316 - compareDocumentPosition() should report PRECEDING or FOLLOWING information even if nodes are disconnected
Summary: compareDocumentPosition() should report PRECEDING or FOLLOWING information ev...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Chris Dumez
URL: http://dom.spec.whatwg.org/#dom-node-...
Keywords: BlinkMergeCandidate, WebExposed
Depends on:
Blocks:
 
Reported: 2013-07-30 21:27 PDT by Ryosuke Niwa
Modified: 2015-08-25 10:58 PDT (History)
12 users (show)

See Also:


Attachments
Patch (27.32 KB, patch)
2013-07-31 00:03 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (28.01 KB, patch)
2013-08-02 00:30 PDT, Chris Dumez
rniwa: review+
Details | Formatted Diff | Diff
Patch for landing (27.25 KB, patch)
2013-08-02 03:43 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch for landing (25.01 KB, patch)
2013-08-02 10:35 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch for landing (21.98 KB, patch)
2013-08-02 10:53 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff
Patch (23.61 KB, patch)
2015-08-24 18:50 PDT, Chris Dumez
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2013-07-30 21:27:32 PDT
Consider merging https://chromium.googlesource.com/chromium/blink/+/12e90f1c03c5782b68a7256f9b88a37563e9876f

As per the latest specification, compareDocumentPosition() should report PRECEEDING or FOLLOWING
information even if nodes are disconnected:
- http://dom.spec.whatwg.org/#dom-node-comparedocumentposition

This behavior is consistent with both IE10 and Firefox 22.

Blink was not reporting PRECEEDING or FOLLOWING in all cases. This patches makes Blink behave
as expected.
Comment 3 Chris Dumez 2013-07-30 22:28:52 PDT
I'm planning to merge this to WebKit very soon.
Comment 4 Chris Dumez 2013-07-31 00:03:41 PDT
Created attachment 207812 [details]
Patch
Comment 5 Ryosuke Niwa 2013-08-01 20:16:35 PDT
Comment on attachment 207812 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=207812&action=review

> Source/WebCore/dom/Node.cpp:1642
> +        unsigned short direction = (this > otherNode) ? DOCUMENT_POSITION_PRECEDING : DOCUMENT_POSITION_FOLLOWING;

There is a nice comment how about we use an implementation dependent ordering in some cases.
Can we extract that comment along with pointer comparisons as a function so that it doesn't look as strange?
Comment 6 Chris Dumez 2013-08-02 00:30:01 PDT
Created attachment 207988 [details]
Patch
Comment 7 Ryosuke Niwa 2013-08-02 02:41:41 PDT
Comment on attachment 207988 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=207988&action=review

> Source/WebCore/dom/Node.cpp:1624
> +static inline unsigned short computeDisconnectedElementsPosition(Node* firstNode, Node* secondNode)

I would have called this compareDetachedElementPositions

> Source/WebCore/dom/Node.cpp:1700
>      unsigned index2 = chain2.size();

Huh, this one implements a fancy O(n) algorithm to find the common ancestor...
We should probably extract this a function in Node and use it in various places; e.g. Range::commonAncestor.

> LayoutTests/platform/efl/TestExpectations:350
> +# These conformace tests are no longer in sync with the latest specification
> +# and expect compareDocumentPosition() to return:
> +# DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_DISCONNECTED
> +# for disconnected nodes (missing PRECEDING / FOLLOWING information).
> +dom/xhtml/level3/core/nodecomparedocumentposition03.xhtml [ WontFix ]
> +dom/xhtml/level3/core/nodecomparedocumentposition05.xhtml [ WontFix ]
> +dom/xhtml/level3/core/nodecomparedocumentposition16.xhtml [ WontFix ]
> +dom/xhtml/level3/core/nodecomparedocumentposition33.xhtml [ WontFix ]

Instead of adding these expectations, simply rebaseline tests with the new expectations.
Comment 8 Chris Dumez 2013-08-02 03:27:28 PDT
Comment on attachment 207988 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=207988&action=review

>> Source/WebCore/dom/Node.cpp:1700
>>      unsigned index2 = chain2.size();
> 
> Huh, this one implements a fancy O(n) algorithm to find the common ancestor...
> We should probably extract this a function in Node and use it in various places; e.g. Range::commonAncestor.

Ok, I can look into this in a follow-up patch since this is a bit out of scope.
Comment 9 Chris Dumez 2013-08-02 03:38:15 PDT
Comment on attachment 207988 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=207988&action=review

>> LayoutTests/platform/efl/TestExpectations:350
>> +dom/xhtml/level3/core/nodecomparedocumentposition33.xhtml [ WontFix ]
> 
> Instead of adding these expectations, simply rebaseline tests with the new expectations.

This will not work: it will result in flakiness. The output will look like:
isImplSpecificDisconnected1: assertEquals failed, actual 35, expected 33.

However, the actual value can be 35 or 37 depending on the test run (PRECEDING / FOLLOWING is not necessarily consistent between test runs since it relies on pointer comparison. I suggest to keep them in the TestExpectations.
Comment 10 Chris Dumez 2013-08-02 03:43:51 PDT
Created attachment 207998 [details]
Patch for landing

I renamed the function to compareDetachedElementsPosition() but kept the rest as it was for now.
Comment 11 Ryosuke Niwa 2013-08-02 10:10:59 PDT
Comment on attachment 207998 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=207998&action=review

> LayoutTests/platform/efl/TestExpectations:350
> +# These conformace tests are no longer in sync with the latest specification
> +# and expect compareDocumentPosition() to return:
> +# DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_DISCONNECTED
> +# for disconnected nodes (missing PRECEDING / FOLLOWING information).
> +dom/xhtml/level3/core/nodecomparedocumentposition03.xhtml [ WontFix ]
> +dom/xhtml/level3/core/nodecomparedocumentposition05.xhtml [ WontFix ]
> +dom/xhtml/level3/core/nodecomparedocumentposition16.xhtml [ WontFix ]
> +dom/xhtml/level3/core/nodecomparedocumentposition33.xhtml [ WontFix ]

We shouldn't do this. We should check in the failing results so that we can detect when they start passing or output changes.
Comment 12 Chris Dumez 2013-08-02 10:20:50 PDT
(In reply to comment #11)
> (From update of attachment 207998 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=207998&action=review
> 
> > LayoutTests/platform/efl/TestExpectations:350
> > +# These conformace tests are no longer in sync with the latest specification
> > +# and expect compareDocumentPosition() to return:
> > +# DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_DISCONNECTED
> > +# for disconnected nodes (missing PRECEDING / FOLLOWING information).
> > +dom/xhtml/level3/core/nodecomparedocumentposition03.xhtml [ WontFix ]
> > +dom/xhtml/level3/core/nodecomparedocumentposition05.xhtml [ WontFix ]
> > +dom/xhtml/level3/core/nodecomparedocumentposition16.xhtml [ WontFix ]
> > +dom/xhtml/level3/core/nodecomparedocumentposition33.xhtml [ WontFix ]
> 
> We shouldn't do this. We should check in the failing results so that we can detect when they start passing or output changes.

(In reply to comment #11)
> (From update of attachment 207998 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=207998&action=review
> 
> > LayoutTests/platform/efl/TestExpectations:350
> > +# These conformace tests are no longer in sync with the latest specification
> > +# and expect compareDocumentPosition() to return:
> > +# DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC | DOCUMENT_POSITION_DISCONNECTED
> > +# for disconnected nodes (missing PRECEDING / FOLLOWING information).
> > +dom/xhtml/level3/core/nodecomparedocumentposition03.xhtml [ WontFix ]
> > +dom/xhtml/level3/core/nodecomparedocumentposition05.xhtml [ WontFix ]
> > +dom/xhtml/level3/core/nodecomparedocumentposition16.xhtml [ WontFix ]
> > +dom/xhtml/level3/core/nodecomparedocumentposition33.xhtml [ WontFix ]
> 
> We shouldn't do this. We should check in the failing results so that we can detect when they start passing or output changes.

As I explained in https://bugs.webkit.org/show_bug.cgi?id=119316#c9, their result is likely to change for every test run due to the pointer comparison. Therefore, I cannot rebaseline them. This will make them flaky.
Comment 13 Ryosuke Niwa 2013-08-02 10:23:56 PDT
(In reply to comment #12)
> As I explained in https://bugs.webkit.org/show_bug.cgi?id=119316#c9, their result is likely to change for every test run due to the pointer comparison. Therefore, I cannot rebaseline them. This will make them flaky.

In that case, we should explain that and put it in LayoutTests/TestExpectations, not in each port's TestExpectations files.
Comment 14 Chris Dumez 2013-08-02 10:25:34 PDT
(In reply to comment #13)
> (In reply to comment #12)
> > As I explained in https://bugs.webkit.org/show_bug.cgi?id=119316#c9, their result is likely to change for every test run due to the pointer comparison. Therefore, I cannot rebaseline them. This will make them flaky.
> 
> In that case, we should explain that and put it in LayoutTests/TestExpectations, not in each port's TestExpectations files.

Ok, I did not know we had a global TestExpectations. It is better indeed, I'll do that.
Comment 15 Chris Dumez 2013-08-02 10:35:04 PDT
Created attachment 208031 [details]
Patch for landing

Move WontFix tests to global TestExpectations.
Comment 16 Ryosuke Niwa 2013-08-02 10:40:57 PDT
Comment on attachment 208031 [details]
Patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=208031&action=review

> LayoutTests/platform/efl/TestExpectations:1715
> +# Node::compareDocumentPosition() wrongly reports an attribute and its content as disconnected.
> +webkit.org/b/119325 dom/xhtml/level3/core/nodecomparedocumentposition38.xhtml [ Failure ]

Why don't we also do this in LayoutTests/TestExpectations given that it's going to fail everywhere?
Comment 17 Chris Dumez 2013-08-02 10:46:18 PDT
(In reply to comment #16)
> (From update of attachment 208031 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=208031&action=review
> 
> > LayoutTests/platform/efl/TestExpectations:1715
> > +# Node::compareDocumentPosition() wrongly reports an attribute and its content as disconnected.
> > +webkit.org/b/119325 dom/xhtml/level3/core/nodecomparedocumentposition38.xhtml [ Failure ]
> 
> Why don't we also do this in LayoutTests/TestExpectations given that it's going to fail everywhere?

Yes, it is going to fail everywhere. I did not know what was the policy for the global TestExpectations but I'll move it as well.
Comment 18 Chris Dumez 2013-08-02 10:53:41 PDT
Created attachment 208032 [details]
Patch for landing

Move remaining failure to the global TestExpectations file.
Comment 19 WebKit Commit Bot 2013-08-02 11:51:42 PDT
Comment on attachment 208032 [details]
Patch for landing

Clearing flags on attachment: 208032

Committed r153660: <http://trac.webkit.org/changeset/153660>
Comment 20 WebKit Commit Bot 2013-08-02 11:51:46 PDT
All reviewed patches have been landed.  Closing bug.
Comment 21 Alexey Proskuryakov 2013-08-02 13:51:33 PDT
> As I explained in https://bugs.webkit.org/show_bug.cgi?id=119316#c9, their result is likely to change for every test run due to the pointer comparison.

I'm not sure if that's acceptable in a Web API.
Comment 22 Chris Dumez 2013-08-02 13:54:40 PDT
(In reply to comment #21)
> > As I explained in https://bugs.webkit.org/show_bug.cgi?id=119316#c9, their result is likely to change for every test run due to the pointer comparison.
> 
> I'm not sure if that's acceptable in a Web API.

FYI, this is the way recommended by the specification (Step 3):
http://dom.spec.whatwg.org/#dom-node-comparedocumentposition

I also looked at Firefox's code and it is implemented the same way.
Comment 23 Alexey Proskuryakov 2013-08-02 14:02:33 PDT
Well, the spec just just doesn't make any sense - they also allow returning a result based on Math.random, which means that a.compareDocumentPosition(b) and b.compareDocumentPosition(a) can both return PRECEDING. That violates a basic contract of any comparison function. You can have sets that are not fully ordered, but then comparison function should just refuse to compare elements that are not comparable.

Pointer comparison also has the same issue, because an implementation is free to move objects around at any time, even between two lines of JS code. And pointer comparison creates a way for JS to peek at implementation details that it simply has no business peeking at.
Comment 24 Chris Dumez 2013-08-02 14:15:31 PDT
(In reply to comment #23)
> Well, the spec just just doesn't make any sense - they also allow returning a result based on Math.random, which means that a.compareDocumentPosition(b) and b.compareDocumentPosition(a) can both return PRECEDING. That violates a basic contract of any comparison function. You can have sets that are not fully ordered, but then comparison function should just refuse to compare elements that are not comparable.
> 
> Pointer comparison also has the same issue, because an implementation is free to move objects around at any time, even between two lines of JS code. And pointer comparison creates a way for JS to peek at implementation details that it simply has no business peeking at.

I agree that uses Math.random() wouldn't make sense.
In the case of pointer comparison though, it works in practice (while in theory, it is possible that the implementation moves objects around).

Also note that my patch is not really doing anything new. We were already doing pointer comparison in 1 out of 3 cases where the elements are detected as disconnected. My patch is merely making the code more consistent and using pointer comparison (to return FOLLOWING/PRECEDING information) in the 2 other places as well.
Comment 25 Alexey Proskuryakov 2014-02-28 22:42:31 PST
Pointer comparison is crazy talk. Undoing this in bug 120244.
Comment 26 Chris Dumez 2015-08-24 16:00:47 PDT
Reopening as Alexey rolled it out. I will work on implementing this without pointer comparison.
Comment 27 Chris Dumez 2015-08-24 16:20:29 PDT
One possible idea would be to hash (with a cryptographically strong hash function) the pointers before comparing them.

W3C test suite covering this:
http://w3c-test.org/dom/nodes/Node-compareDocumentPosition.html
Comment 28 Chris Dumez 2015-08-24 18:50:42 PDT
Created attachment 259804 [details]
Patch
Comment 29 WebKit Commit Bot 2015-08-25 10:58:42 PDT
Comment on attachment 259804 [details]
Patch

Clearing flags on attachment: 259804

Committed r188917: <http://trac.webkit.org/changeset/188917>
Comment 30 WebKit Commit Bot 2015-08-25 10:58:48 PDT
All reviewed patches have been landed.  Closing bug.