335913 - Implement CompareDocumentPosition using nsINode interfaces

Status: RESOLVED FIXED

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

Description

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The current implementation of CompareDocumentPosition is written entierly in nsIDOMNode interfaces. In addition it is extreamly complex and supports all manners of node types that our DOM doesn't support.

Patch comming up with a much simpler implementation that uses nsINode interfaces instead. This is both faster and easier to use from most of our code.

I decided not to share implementation with nsLayoutUtils::DoCompareTreePosition or txXPathNodeUtils::comparePosition (which both do very similar things) since the other two classes have slightly different feature sets and different optimizations. I did optimize nsLayoutUtils::DoCompareTreePosition a tad though.

I also cleaned up the implementation of nsContentUtils::GetCommonAncestor for pretty much the same reasons.

There are probably places in the tree where we could use these new functions, but I couldn't think of any more off the top of my head.

Comment 1

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: Patch to fix

This should do it. I ran this over the DOM test suite and it runs as well as before except for one test. The test compares the position of an attribute node to the textnode contained inside it. We used to have special code for that, but now we don't. However nodes inside attribute nodes are very broken as is so I don't really care about this one edge case not working any more.

If and when we give nodes inside attribute nodes a real parent this should be very easy to fix.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 221064 [details] [diff] [review]
Patch to fix

>Index: content/base/public/nsContentUtils.h
>+   * Returns an error if the two nodes are disconnected and doesn't have
>+   * a common ancestor.

s/doesn't/don't/

Should the nsRange caller that doesn't check the rv from this method be fixed?

>+   * @param   aNode1   The node to which you are comparing.
>+   * @param   aNode2   The reference node to which aNode is compared.

I know this is what the comments used to say... But it still makes no sense.  Perhaps:

  @param aNode1 The node whose position is being compared to the reference node
  @param aNode2 The reference node

or something?  That is, we are _not_ comparing "to aNode1" we're comparing "aNode1 to aNode2".

>+   * @return  The document position flags of the nodes. The result is the
>+   *          relation from aNode1's perspective, i.e. if aNode1 is before
>+   *          aNode2 then DOCUMENT_POSITION_PRECEDING will be set.

That's not the relation from aNode1's perspective, but from aNode2's, no?  The example is correct, however.

>+  static PRBool PositionBefore(nsINode* aNode1,

Maybe PositionIsBefore or even just IsBefore?  Not a big deal either way, though.

>Index: content/base/public/nsINode.h

>+  virtual PRInt32 IndexOf(nsINode* aPossibleChild) const = 0;

Should probably rev the iid...

>Index: content/base/src/nsContentUtils.cpp

> nsContentUtils::GetCommonAncestor(nsIDOMNode *aNode,
....
>+  NS_ENSURE_TRUE(common, NS_ERROR_FAILURE);

Maybe NS_ERROR_NOT_AVAILABLE?

>+nsContentUtils::GetCommonAncestor(nsINode* aNode1,

Do we want to leave the optimization for the aNode1 == aNode2 case?  Or just not worry about it?

>+  PRUint32 pos1 = parents1.Count();
>+  PRUint32 pos2 = parents2.Count();
>+  nsINode* top1 = NS_STATIC_CAST(nsINode*, parents1.FastElementAt(--pos1));
>+  nsINode* top2 = NS_STATIC_CAST(nsINode*, parents2.FastElementAt(--pos2));
>+  if (top1 != top2) {
>+    return nsnull;
>   }
> 
>+  // Find where the parent chain differs

Why have that first bit at all?  Why not just:

  PRUint32 pos1 = parents1.Count();
  PRUint32 pos2 = parents2.Count();
  nsINode* parent = nsnull;

  PRUint32 len;
  for (len = PR_MIN(pos1, pos2); len > 0; --len) {
  
etc?  That looks like it should give the right thing, no?

>+nsContentUtils::ComparePosition(nsINode* aNode1,

What's up with like 3 empty lines before this function?  Just have 1.  ;)

>+      // Both nodes are attributes on the same element.
>+      // Compare position between the attributes.

Why do we care what the position is, really?  Why not just return DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC and be done with it?   I guess this is a rare case anyway, though...

>+    return top1 < top2 ?
>+      (nsIDOM3Node::DOCUMENT_POSITION_PRECEDING |
>+       nsIDOM3Node::DOCUMENT_POSITION_DISCONNECTED |
>+       nsIDOM3Node::DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC) :

Why not just DOCUMENT_POSITION_DISCONNECTED without the other two bits?  That would make the most sense to me...

>+  // Find where the parent chain differs and check indexes in the parent.

s/indexes/indices/

>+    if (child1 != child2) {
>+      // child1 or child2 can be an attribute here. This will work fine since
>+      // IndexOf will return -1 for the attribute making the attribute be
>+      // considered before any child.

Do we care about anonymous content?  I guess not...

>+      return parent->IndexOf(child1) < parent->IndexOf(child2) ?
>+        NS_STATIC_CAST(PRUint16, nsIDOM3Node::DOCUMENT_POSITION_PRECEDING) :
>+        NS_STATIC_CAST(PRUint16, nsIDOM3Node::DOCUMENT_POSITION_FOLLOWING);

Why do you need the casts here but not at other return points in this method?

>+  return pos1 < pos2 ?
>+    (nsIDOM3Node::DOCUMENT_POSITION_PRECEDING |
>+     nsIDOM3Node::DOCUMENT_POSITION_CONTAINS) :
>+    (nsIDOM3Node::DOCUMENT_POSITION_FOLLOWING |
>+     nsIDOM3Node::DOCUMENT_POSITION_CONTAINED_BY);    

So if I compare an element (aNode1) with one of its attributes (aNode2) we'll return PRECEDING | CONTAINS?  Does the element really contain the attribute?  That seems odd.  Too bad the DOM spec is so useless here in terms of actually specifying something.  :(

>Index: content/base/src/nsDOMAttribute.cpp
>+  nsCOMPtr<nsINode> other = do_QueryInterface(aOther);
>+  NS_ENSURE_TRUE(other, NS_ERROR_DOM_NOT_SUPPORTED_ERR);

All the CompareDocumentPosition impls have this in common.  Should we factor it out into a method on nsContentUtils too, maybe?  So just have:

  return nsContentUtils::CompareDocumentPosition(aOther, this, aReturn);

be all of nsDOMAttribute::CompareDocumentPosition?  Either way, I guess.

>Index: layout/base/nsLayoutUtils.cpp

diff -w would have been nice here.  :(

r+sr=bzbarsky with the nits picked.

Comment 3

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I believe that the spec says that we should give order both to attributes and disconnected nodes. And that attributes are contained by their owner elements. See
http://www.w3.org/TR/DOM-Level-3-Core/core.html#DocumentPosition . Specifically the fourth paragraph seems to hint that disconnected nodes have an order.

Reving the iid shouldn't be needed since the new signature is binary compatible with the old.

Will fix the other comments

Comment 4

[Boris Zbarsky [:bzbarsky]]

> Reving the iid shouldn't be needed since the new signature is binary compatible
> with the old.

It's not, technically.  Someone compiling against the new signature and then running against a Gecko that uses the older interface could pass in a node that's not a content, which would effectively get cast to nsIContent and then the different vtable layouts would screw up the callee.  Now our callee happens to not access the vtable, so it might be ok, but...

Thanks for the URI!  I couldn't find that part of the spec.  ;)  It looks like your impl is good to go given that, yes.

Comment 5

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Yeah, since we never deref those pointers I think things should be ok.

Comment 6

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

> Should the nsRange caller that doesn't check the rv from this method be fixed?

Null-checking the ancestor is enough.

> Do we care about anonymous content?  I guess not...

Yeah, If we really want to figure something out there we can do that later. I'm not convinced we do though.

> >+      return parent->IndexOf(child1) < parent->IndexOf(child2) ?
> >+        NS_STATIC_CAST(PRUint16, nsIDOM3Node::DOCUMENT_POSITION_PRECEDING) :
> >+        NS_STATIC_CAST(PRUint16, nsIDOM3Node::DOCUMENT_POSITION_FOLLOWING);
> 
> Why do you need the casts here but not at other return points in this method?

I *think* or-ing flags together will change the type to integer so no casts to avoid warnings should be needed.

> >Index: content/base/src/nsDOMAttribute.cpp
> >+  nsCOMPtr<nsINode> other = do_QueryInterface(aOther);
> >+  NS_ENSURE_TRUE(other, NS_ERROR_DOM_NOT_SUPPORTED_ERR);
> 
> All the CompareDocumentPosition impls have this in common.  Should we factor 

Don't feel strongly about it, but I desided not to.

Comment 7

[Peter van der Woude [:Peter6]]

this may have caused Bug 338188

Comment 8

[Alex Vincent [:WeirdAl]]

bz suspected CSSParser could be at fault.  I just filed bug 338247 for a compile-time warning, on code which CSSParser does use.  Connection?

Comment 9

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

This has been checked in.