1469521 - Change storage of previous and next children in nsINode

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, enhancement, P2)

Description

[Olli Pettay [:smaug][[e-mail]]]

An unreviewed patch is https://bugzilla.mozilla.org/attachment.cgi?id=8966590&action=edit

Comment 2

[Olli Pettay [:smaug][[e-mail]]]

Also https://bug651120.bmoattachments.org/attachment.cgi?id=8966591 needs to be done at the same time.

Comment 3

[Olli Pettay [:smaug][[e-mail]]]

Attachment: dont_use_childarray.diff

remote: View your changes here:
remote:   https://hg.mozilla.org/try/rev/c956b98e0cfbc915bde826acb09587bf78036b0a
remote:   https://hg.mozilla.org/try/rev/a72afe50ff7d41e4ff796e0828fb60d209b317b6
remote:   https://hg.mozilla.org/try/rev/fdebd6f9feb7f92ad719d35bc35ab10ba5b7c281
remote: 
remote: Follow the progress of your build on Treeherder:
remote:   https://treeherder.mozilla.org/#/jobs?repo=try&revision=fdebd6f9feb7f92ad719d35bc35ab10ba5b7c281
remote: 
remote: It looks like this try push has talos jobs. Compare performance against a baseline revision:
remote:   https://treeherder.mozilla.org/perf.html#/comparechooser?newProject=try&newRevision=fdebd6f9feb7f92ad719d35bc35ab10ba5b7c281
remote: recorded changegroup in replication log in 0.007s

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 8995488 [details] [diff] [review]
dont_use_childarray.diff

This is basically two catalin's patches merged together and naming tweaked a bit, and stylo part fixed to handle the case when mPreviousOrLastSibling doesn't point to the previous sibling.

nsINode ctor needs to be non-inline because of nsCOMPtr member variables.

Unused methods in nsAttrAndChildArray are remove in bug 1469523 and after that there are still more cleanups to do.

Comment 5

[Emilio Cobos Álvarez [:emilio]]

It's a bit unfortunate that the last-child, prev sibling accessors are not inline (not talking only about Stylo)... But I guess we can always measure it and change it if it shows up anywhere.

Comment 6

[Olli Pettay [:smaug][[e-mail]]]

All the explicit inlining in stylo is super error prone and makes maintenance harder, so I'd prefer to not inline unless some testcase shows it actually matters.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 8995488 [details] [diff] [review]
dont_use_childarray.diff

>+++ b/dom/base/FragmentOrElement.cpp
>   void UnbindSubtree(nsIContent* aNode)
>+        // the last reference to it.  We need to call DisconnectChild() and
>+        // before calling UnbindFromTree, since this last can notify various

s/and before/before/

>+++ b/dom/base/nsAttrAndChildArray.cpp
> nsAttrAndChildArray::TakeChildAt(uint32_t aPos)
>+  if (child->mPreviousOrLastSibling) {
>+    child->mPreviousOrLastSibling->mNextSibling = child->mNextSibling;
>   }

This is wrong.  We don't want to set the last sibling's mNextSibling.

The only good news is that after this patch this method is unused.  I would prefer that we just removed it and its one (also unused) caller nsAttrAndChildArray::RemoveChildAt here.  If not, I'd prefer that we  replaced all this code with MOZ_ASSERT_UNREACHABLE() or something instead of having incorrect code, even if we're about to remove it.

Alternately, you could condition this on aPos != 0 or something, but...

>+++ b/dom/base/nsDocument.cpp
>@@ -1973,35 +1966,25 @@ NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(ns
>+    nsCOMPtr<nsIContent> child = tmp->nsINode::GetLastChild();

Why does this need the "nsINode::" qualification? If it really does, can we just "using nsINode::GetLastChild" in nsDocument to fix this problem instead?  If not, there should be a comment here explaining why we need that.

>@@ -2239,32 +2222,26 @@ nsIDocument::ResetToURI(nsIURI* aURI,
>+      nsCOMPtr<nsIContent> content = nsINode::GetLastChild();

Same here.

>+       nsIContent* previousSibling = content->GetPreviousSibling();

Fix indent, please.

>+++ b/dom/base/nsINode.cpp
>@@ -1367,56 +1394,48 @@ nsINode::doInsertChildAt(nsIContent* aKi
>-    aChildArray.RemoveChildAt(aIndex);
>-    aKid->UnbindFromTree();
>+    DisconnectChild(aKid);

This is losing the UnbindFromTree() call.  Why?

>+nsINode::AppendChild(nsIContent* aKid)
>+  aKid->mNextSibling = nullptr;

Shouldn't that already be true?  We should at least assert it, even if we don't trust this enough to dely on it.

>+  if (MOZ_LIKELY(mFirstChild)) {

It's not clear to me why this is MOZ_LIKELY.  I'd just let PGO and normal branch prediction do its thing here.

>+    mFirstChild->mPreviousOrLastSibling = aKid;
...
>+    aKid->mPreviousOrLastSibling = aKid;

These could move out of the "if" and just be:

  mFirstChild->mPreviousOrLastSibling = aKid;

after the "if".  Would be a bit clearer, I think.

>+nsINode::InsertBefore(nsIContent* aKid, nsIContent* aChildBefore)

aChildBefore is odd naming.  I'd call it aNextSibling or something.

>+  if (aChildBefore == mFirstChild) {
>+    mFirstChild = aKid;

Can we assert here that previousSibling->mNextSibling is null?

>+nsINode::GetChildAt_Deprecated(uint32_t aIndex) const

We still seem to have a lot of callers here... Are we not worried about the perf hit of making this O(N)?

>+  while (aIndex-- && (child = child->GetNextSibling()));

So we're worried about our length being off?

>+nsINode::RemoveChildNode(nsIContent* aKid, bool aNotify)
>+  nsCOMPtr<nsIContent> kungfu = aKid;
>+  DisconnectChild(aKid);

DisconnectChild() holds a strong ref to the argument.  We're holding another strong ref here.  Why do we need both?  Further, I'd more or less expect the caller of RemoveChildNode() to _also_ be holding a ref.  We should really decide what the ownership model here is.

>+  // - mParent, mNextSibling, mPreviousOrLastSibling, mFirstChild: because they're
>   //   non-owning
>+  // XXXsmaug The comment above has always been bogus, mParent has been owning
>+  //          for ages and now also others.

Not owning in the "exclusive ownership" sense memory reporting cares about.

>+++ b/dom/base/nsINode.h
>+  void AppendChild(nsIContent* aKid);
>+  void InsertBefore(nsIContent* aKid, nsIContent* aChildBefore);
>+  void DisconnectChild(nsIContent* aKid);

These need to be documented, esp. becaase we already have the DOM AppendChild()/InsertBefore() (with different signatures and functionality) and InsertChildBefore/RemoveChildNode.

I'd almost prefer different names here.  Maybe AppendChildToChildList/InsertChildInChildList or something?

>+  // mNextSibling and mFirstChild are strong references while
>+  // mPreviousOrLastSibling is a weak ref. |mFirstChild->mPreviousOrLastSibling|
>+  // points to the last child node.

I think it might be good to document clearly when mPreviousOrLastSibling points to null (when a node is not officially in its parent's child list, right?  So for any anon content?) and when it points to the last child.  It's worth pointing out that mFirstChild->mPreviousOrLastSibling can be mFirstChild, too.

>+  nsIContent* MOZ_NON_OWNING_REF mPreviousOrLastSibling;

I'm a bit torn as to whether this is better than a union of mPreviousSibling and mLastSibling nsIContent pointers....  I guess this makes it clearer that there is something to watch out for...

Another option would be to put this member and mNextSibling into some sort of SiblingInfo struct and access them only via certain methods that assert stuff as needed.  I'm OK with a followup for this if we decide to do it.

>+  //NOTE, there are 32 bits left here!

On 64-bit only, right?

Would it make any sense to put this right after mBoolFlags to make it clearer what things look like?

r=me with the above fixed.

Comment 8

[Olli Pettay [:smaug][[e-mail]]]

(In reply to Boris Zbarsky [:bz] (no decent commit message means r-) from comment #7)

> >+++ b/dom/base/nsAttrAndChildArray.cpp
> > nsAttrAndChildArray::TakeChildAt(uint32_t aPos)
> >+  if (child->mPreviousOrLastSibling) {
> >+    child->mPreviousOrLastSibling->mNextSibling = child->mNextSibling;
> >   }
> 
> This is wrong.  We don't want to set the last sibling's mNextSibling.
> 
> The only good news is that after this patch this method is unused.
Exactly. This patch can't land without bug 1469523.
I did  only minimal changes in this bug.


> >+++ b/dom/base/nsDocument.cpp
> >@@ -1973,35 +1966,25 @@ NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(ns
> >+    nsCOMPtr<nsIContent> child = tmp->nsINode::GetLastChild();
> 
> Why does this need the "nsINode::" qualification? If it really does, can we
> just "using nsINode::GetLastChild" in nsDocument to fix this problem
> instead?  If not, there should be a comment here explaining why we need that.
> 
Looks like it doesn't. leftover


> >@@ -1367,56 +1394,48 @@ nsINode::doInsertChildAt(nsIContent* aKi
> >-    aChildArray.RemoveChildAt(aIndex);
> >-    aKid->UnbindFromTree();
> >+    DisconnectChild(aKid);
> 
> This is losing the UnbindFromTree() call.  Why?
because I suck

> 
> >+nsINode::AppendChild(nsIContent* aKid)
> >+  aKid->mNextSibling = nullptr;
> 
> Shouldn't that already be true?  We should at least assert it, even if we
> don't trust this enough to dely on it.

> 
> >+  if (MOZ_LIKELY(mFirstChild)) {
> 
> It's not clear to me why this is MOZ_LIKELY.  I'd just let PGO and normal
> branch prediction do its thing here.
> 
> >+    mFirstChild->mPreviousOrLastSibling = aKid;
> ...
> >+    aKid->mPreviousOrLastSibling = aKid;
> 
> These could move out of the "if" and just be:
> 
>   mFirstChild->mPreviousOrLastSibling = aKid;
> 
> after the "if".  Would be a bit clearer, I think.
I might disagree, but will do.




> >+nsINode::GetChildAt_Deprecated(uint32_t aIndex) const
> 
> We still seem to have a lot of callers here... Are we not worried about the
> perf hit of making this O(N)?
I'm not particularly worried, since the most common cases use RangeBoundary which does caching
As of now, I'd rather get this landed and get the memory and perf speedups this provides and fix possible regressions afterwards

> 
> >+  while (aIndex-- && (child = child->GetNextSibling()));
> 
> So we're worried about our length being off?
I don't understand the question. We just count from the beginning to the right child node.
Perhaps you mean the null check? 

> 
> >+nsINode::RemoveChildNode(nsIContent* aKid, bool aNotify)
> >+  nsCOMPtr<nsIContent> kungfu = aKid;
> >+  DisconnectChild(aKid);
> 
> DisconnectChild() holds a strong ref to the argument.  
So? We need aKid to stay alive after DisconnectChild. That is the whole point of kugfu here.
(I rename it to kungfuDeathGrip)

We're holding another
> strong ref here.  Why do we need both?  Further, I'd more or less expect the
> caller of RemoveChildNode() to _also_ be holding a ref.
That is something I should probably do.


> >+  // - mParent, mNextSibling, mPreviousOrLastSibling, mFirstChild: because they're
> >   //   non-owning
> >+  // XXXsmaug The comment above has always been bogus, mParent has been owning
> >+  //          for ages and now also others.
> 
> Not owning in the "exclusive ownership" sense memory reporting cares about.



> 
> >+++ b/dom/base/nsINode.h
> >+  void AppendChild(nsIContent* aKid);
> >+  void InsertBefore(nsIContent* aKid, nsIContent* aChildBefore);
> >+  void DisconnectChild(nsIContent* aKid);
> 
> These need to be documented, esp. becaase we already have the DOM
> AppendChild()/InsertBefore() (with different signatures and functionality)
> and InsertChildBefore/RemoveChildNode.
> 
> I'd almost prefer different names here.  Maybe
> AppendChildToChildList/InsertChildInChildList or something?
> 
> >+  // mNextSibling and mFirstChild are strong references while
> >+  // mPreviousOrLastSibling is a weak ref. |mFirstChild->mPreviousOrLastSibling|
> >+  // points to the last child node.
> 
> I think it might be good to document clearly when mPreviousOrLastSibling
> points to null (when a node is not officially in its parent's child list,
> right?  So for any anon content?) and when it points to the last child. 
> It's worth pointing out that mFirstChild->mPreviousOrLastSibling can be
> mFirstChild, too.
> 
> >+  nsIContent* MOZ_NON_OWNING_REF mPreviousOrLastSibling;
> 
> I'm a bit torn as to whether this is better than a union of mPreviousSibling
> and mLastSibling nsIContent pointers....  I guess this makes it clearer that
> there is something to watch out for...
yeah, exactly. In earlier patches this is based on it was just mPreviousSibling and the
stylo part was broken since it was using inlined accesses to that.

> >+  //NOTE, there are 32 bits left here!
> 
> On 64-bit only, right?
depends on what we decide. We haven't been tracking the sizeof Element in 32bit builds.
But I'll improve the comment



> 
> Would it make any sense to put this right after mBoolFlags to make it
> clearer what things look like?
ok

Comment 9

[Boris Zbarsky [:bzbarsky]]

> Exactly. This patch can't land without bug 1469523.

Sounds good.

> I'm not particularly worried, since the most common cases use RangeBoundary which does caching

OK.

> Perhaps you mean the null check? 

Yes, exactly.  Why do we need the null check, if we trust our length?

> So? We need aKid to stay alive after DisconnectChild.

Ah, for the ContentRemoved call, right.  It would be good to have a comment on the strong ref explaining why it's there.

Even better would be requiring callers to pass in a stack-held strong ref, enforced via static analysis.  Kind of like MOZ_CAN_RUN_SCRIPT but for a particular arg, not all args...  A followup static analysis bug asking for that would be awesome.

> That is something I should probably do.

I am fine with that happening in a followup, to be clear.  Especially because it would be fragile until we have that static analysis in place.

Comment 10

[Olli Pettay [:smaug][[e-mail]]]

Attachment: dont_use_childarray_2.diff

another try push

remote: View your changes here:
remote:   https://hg.mozilla.org/try/rev/5f89e1a4f132ee5aac9c57de803a71ba53b19d96
remote:   https://hg.mozilla.org/try/rev/d0e0c06a6a9fb5c8d3ef8c0fc326e14d16d50ddf
remote:   https://hg.mozilla.org/try/rev/7116750e1d251b16eadb8c851fc924d451d3cc3c
remote: 
remote: Follow the progress of your build on Treeherder:
remote:   https://treeherder.mozilla.org/#/jobs?repo=try&revision=7116750e1d251b16eadb8c851fc924d451d3cc3c
remote: recorded changegroup in replication log in 0.007s

Comment 11

[Olli Pettay [:smaug][[e-mail]]]

Attachment: dont_use_childarray_3.diff

without null check
remote: View your changes here:
remote:   https://hg.mozilla.org/try/rev/4cb50889c2cfc788cab7037d26d114e35205e998
remote:   https://hg.mozilla.org/try/rev/4743514586f3abf25e5bc18dcff3bad39b30d869
remote:   https://hg.mozilla.org/try/rev/f7683a97999f55e46288157d5e5e0796bac69eec
remote: 
remote: Follow the progress of your build on Treeherder:
remote:   https://treeherder.mozilla.org/#/jobs?repo=try&revision=f7683a97999f55e46288157d5e5e0796bac69eec
remote: recorded changegroup in replication log in 0.008s

Comment 12

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/ca936adbc565
Change storage of previous and next children in nsINode, r=bz

Comment 13

[Arthur Iakab [arthur_iakab]]

https://hg.mozilla.org/mozilla-central/rev/ca936adbc565