compareDocumentPosition() should report PRECEDING or FOLLOWING information even if nodes are disconnected

• Component: DOM
• Status: RESOLVED FIXED

[Ryosuke Niwa]

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.

[Ryosuke Niwa]

Reverted in https://chromium.googlesource.com/chromium/blink/+/1b044bea20701ec484f159b4aa74d867b7a2c397.

[Ryosuke Niwa]

Relanded in https://chromium.googlesource.com/chromium/blink/+/6c9a408bdc07b499e7dfe7c41b2e6ed8cce2681a.

[Chris Dumez]

I'm planning to merge this to WebKit very soon.

[Chris Dumez]

Created attachment 207812 [details]
Patch

[Ryosuke Niwa]

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?

[Chris Dumez]

Created attachment 207988 [details]
Patch

[Ryosuke Niwa]

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.

[Chris Dumez]

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.

[Chris Dumez]

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.

[Chris Dumez]

Created attachment 207998 [details]
Patch for landing

I renamed the function to compareDetachedElementsPosition() but kept the rest as it was for now.

[Ryosuke Niwa]

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.

[Chris Dumez]

(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.

[Ryosuke Niwa]

(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.

[Chris Dumez]

(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.

[Chris Dumez]

Created attachment 208031 [details]
Patch for landing

Move WontFix tests to global TestExpectations.

[Ryosuke Niwa]

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?

[Chris Dumez]

(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.

[Chris Dumez]

Created attachment 208032 [details]
Patch for landing

Move remaining failure to the global TestExpectations file.

[WebKit Commit Bot]

Comment on attachment 208032 [details]
Patch for landing

Clearing flags on attachment: 208032

Committed r153660: <http://trac.webkit.org/changeset/153660>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Alexey Proskuryakov]

> 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.

[Chris Dumez]

(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.

[Alexey Proskuryakov]

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.

[Chris Dumez]

(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.

[Alexey Proskuryakov]

Pointer comparison is crazy talk. Undoing this in bug 120244.

[Chris Dumez]

Reopening as Alexey rolled it out. I will work on implementing this without pointer comparison.

[Chris Dumez]

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

[Chris Dumez]

Created attachment 259804 [details]
Patch

[WebKit Commit Bot]

Comment on attachment 259804 [details]
Patch

Clearing flags on attachment: 259804

Committed r188917: <http://trac.webkit.org/changeset/188917>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.