486002 - Node.compareDocumentPosition returns spurious preceding|following bits for disconnected nodes

Status: RESOLVED INVALID

(Core :: DOM: Core & HTML, defect)

Description

[Mike Samuel]

User-Agent:       Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.0.7) Gecko/2009030423 Ubuntu/8.04 (hardy) Firefox/3.0.7
Build Identifier: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.0.7) Gecko/2009030423 Ubuntu/8.04 (hardy) Firefox/3.0.7

According to my reading of
http://www.w3.org/TR/DOM-Level-3-Core/core.html#DocumentPosition
I should get '1 / 1' for the below.
  var n0 = document.createElement('DIV');
  var n1 = document.createElement('DIV');
  alert((n0.compareDocumentPosition(n1) & 0x1f) + ' / ' +
        (n1.compareDocumentPosition(n0) & 0x1f));
  // Should be 1 / 1.
  // I actually see 5 / 3

The result of compareDocumentPosition is a bitfield, and the 1 bit indicates that there is no sequence of parent/child traversals that create a path from this node to the given node -- if they share no common ancestor, the 1 bit is set.  The 2 and 4 bits indicate whether this node follows or preceeds the given node in a pre-order traversal of the tree of which this node is a part.  As such, if 1 is set, then 2 and 4 must both be empty.

Perhaps the current tree implementation is caching some pre-order numbering state, and using that regardless of whether this node and the given node share any common ancestor.

Reproducible: Always

Steps to Reproduce:
1. Browse to http://squarefree.com/shell/shell.html
2. Paste the below and hit enter
  var n0 = document.createElement('DIV');
  var n1 = document.createElement('DIV');
  alert((n0.compareDocumentPosition(n1) & 0x1f) + ' / ' +
        (n1.compareDocumentPosition(n0) & 0x1f));

Actual Results:  
Alerts "5 / 3"

Expected Results:  
Should alert "1 / 1"

Comment 1

[Tyler Downer [He/Him]]

This is a mass search for bugs which are in the Firefox General component, are
UNCO, have not been changed for 500 days and have an unspecified version. 

Reporter, can you please update to Firefox 3.6.10 or later, create a fresh profile, http://support.mozilla.com/en-US/kb/managing+profiles, and test again. If you still see the issue, please update this bug. If the issue is gone, please set the status to RESOLVED > WORKSFORME.

Comment 2

[Mike Samuel]

I can repeat the problem on 
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.2.10) Gecko/20100914 Firefox/3.6.10

Comment 3

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

This code dates to bug 335913, and now lives in nsINode.cpp:

  // Check if the nodes are disconnected.
  uint32_t pos1 = parents1.Length();
  uint32_t pos2 = parents2.Length();
  nsINode* top1 = parents1.ElementAt(--pos1);
  nsINode* top2 = parents2.ElementAt(--pos2);
  if (top1 != top2) {
    return top1 < top2 ?
      (nsIDOMNode::DOCUMENT_POSITION_PRECEDING |
       nsIDOMNode::DOCUMENT_POSITION_DISCONNECTED |
       nsIDOMNode::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC) :
      (nsIDOMNode::DOCUMENT_POSITION_FOLLOWING |
       nsIDOMNode::DOCUMENT_POSITION_DISCONNECTED |
       nsIDOMNode::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC);
  }
http://hg.mozilla.org/mozilla-central/file/942ed5747b63/content/base/src/nsINode.cpp#l764

In other words, if the nodes are disconnected, return either 0x23 or 0x25 depending on which root node's pointer is greater.  I wish I were kidding.  I wish even more that this weren't 100% supported by the old DOM Level 3 Core spec:

"""
If there is no common container node, then the order is based upon order between the root container of each node that is in no container. In this case, the result is disconnected and implementation-specific. This result is stable as long as these outer-most containing nodes remain in memory and are not inserted into some other containing node. This would be the case when the nodes belong to different documents or fragments, and cloning the document or inserting a fragment might change the order.
"""
http://www.w3.org/TR/DOM-Level-3-Core/core.html#DocumentPosition

It says "disconnected and implementation-specific", so that gives you 0x01 and 0x20.  And it says they're ordered, so that gives you another 0x02 or 0x04 in an implementation-defined manner.  Fortunately, the more recent DOM spec is much less insane:

http://dom.spec.whatwg.org/#dom-node-comparedocumentposition

It says to just return 0x01 here.

Testing, Opera seems to always return 0x23.  IE seems to return 0x23 or 0x25 at random, like us.  WebKit seems to always return 0x21.  Do we want to try returning just 0x01 like the new spec here, or does 0x21 seem safer?

Comment 4

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

(This will be tested by new tests I'm going to commit upstream shortly, which will be synced to us sooner or later, so it doesn't need further tests.)

Comment 5

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

Attachment: Patch

This carries nonzero compat risk, since we would be the first UA to no longer return the Node.DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC flag here.  But it doesn't seem very scary -- this method is quite arcane, so not many sites are going to use it, and the ones that do will hopefully use actual bitwise arithmetic.  They can't do simple equality checks for the disconnected case, because the result can be 0x21 or 0x23 or 0x25 depending on UA and chance.  So this will only break sites that are really doing something like

  if (result == 35 || result == 37) { ... }

which I wouldn't say is impossible, but not something I'm scared about.

Try, although I might have canceled it and not realized how to restart it: https://tbpl.mozilla.org/?tree=Try&rev=d84dcec531e9

Comment 6

[Boris Zbarsky [:bzbarsky]]

> WebKit seems to always return 0x21. 

I'm not sure how that ends up working out.  In particular, jQuery basically has this going on (modulo various object-detection goop):

  sortOrder = function(a, b) {
    return a.compareDocumentPosition(b) & 4 ? -1 : 1;
  }

which in your new setup will return "1" for both sortOrder(x, y) and sortOrder(y, x) if x and y are disconnected.  But then it does:

  Sizzle.uniqueSort = function( results ) {
    // ...
    results.sort( sortOrder );
  }

and JS does not promise termination if the callback to Array.sort lies like that.  Not sure whether JSC and Chrome do so in practice, or whether SpiderMonkey does.

Looks like internally they don't apply it to disconnected nodes, but it's part of the jQuery public API as jQuery.unique....

Comment 7

[Boris Zbarsky [:bzbarsky]]

Note that per ES5 the behavior of such a sorting function is undefined, by the way.  So exploding is perfectly conforming, and might be reasonable depending on the sort algorithm....

I expect that's why DOM 3 Core defined nodes to always be ordered, by the way: anything else makes sorting nodes quite hellish.

Comment 8

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

So do we actually want to keep this IMPLEMENTATION_SPECIFIC craziness, or do we think it's safe to get rid of?  As far as I can tell, WebKit doesn't support it, and I don't see any bugs in their tracker about it.  If we aren't willing to try killing it, the spec should be changed to re-add it.

Comment 9

[Boris Zbarsky [:bzbarsky]]

Again, WebKit may be able to get away with it because of implementation details of the sort algorithm in V8 and JSC.  Those implementation details may not apply to other JS engines, and are most certainly not required by the ECMA spec.

I agree that getting rid of the craziness is desirable (and in particular, implementing consistent sort order for disconnected nodes in a UA which moves nodes around in memory is a huge pain).  I really worry about the knock-on effects given the jQuery behavior here.

Things that are worth doing:

1)  Having this discussion somewhere where more than just you and I are seeing it.  Ideally where Microsoft, Apple, and WebKit people will see it.

2)  Talking to our JS engine folks to find out how SpiderMonkey Array.sort() behaves in the face of a comparator like this.

Comment 10

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

I filed a spec bug suggesting it change to match the old DOM Level 3 Core behavior:

https://www.w3.org/Bugs/Public/show_bug.cgi?id=19555

Comment 11

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 671404 [details] [diff] [review]
Patch

Please re-request review once we decide what we're doing here.

Comment 12

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

From the W3C bug, it looks like the spec will change here.  I'll leave this open until the spec/test changes land.

Comment 13

[Aryeh Gregor (:ayg) (no longer with Mozilla)]

Upstream spec and test changes landed, our behavior is now standard again.  There are always at least two ways to fix a spec bug . . .