[webkit-reviews] review requested: [Bug 58695] Creating copy of ContainerNode's when inserting or removing is inefficient : [Attachment 90652] Updated patch

[bugzilla-daemon at webkit.org]

Michael Saboff <msaboff at apple.com> has asked  for review:
Bug 58695: Creating copy of ContainerNode's when inserting or removing is
inefficient
https://bugs.webkit.org/show_bug.cgi?id=58695

Attachment 90652: Updated patch
https://bugs.webkit.org/attachment.cgi?id=90652&action=review

------- Additional Comments from Michael Saboff <msaboff at apple.com>
This patch adds the "child's parent not me" check to willRemove().

Concerning various questions raised with the initial patch:

> > Therefore the proposed patch (or a slight modification) has better
performance and is arguably just as correct for this corner case.
> 
> Please add a test for this case.

As I stated above, the existing code and proposed code have similar correctness
issues.  In both cases the correctness issues happen when the tree is modified
during the insertion or removal.  The existing code notifies nodes that are
(will be) no longer part of the tree that they are being inserted.  The
proposed code stops notifying later sibling nodes when it encounters a node
that has been removed as a side effect. Existing tests verify the correctness
and no regression on the earlier crashing problems.

> > I would like to proceed at this point with the faster "not necessarily
correct" version of the current slower "but not correct" version.  And then
work on the longer term version.
>
> That's fine as long as we can convince ourselves that the (potential)
correctness issues in the new version don't include security vulnerabilities.

Given that we use RefPtr's as well as other sanity checks we solved for the
original use after free issues.  This is as evident by removing these
safeguards and running tests added with the earlier fixes and seeing the
crashes.  We Ref a parent node, which will has the side effect of holding a ref
to the chain of children which allows us to safely traverse them.

> > Source/WebCore/dom/ContainerNode.cpp:368
> > +	 RefPtr<Node> protect = this;
> 
> This protect is new in this code, right?  Does that mean we're fixing a
crash?	Have you looked at all callers of this function to make sure they
understand that |this| might be deleted after this operation?
> 
> > Source/WebCore/dom/ContainerNode.cpp:743
> > +	 // NOTE: Since insertedIntoDocument can cause arbitrary changes to the

> > +	 // document, we need to guard our data with RefPtrs and guard each
operation
> > +	 // with checks for mutation.
> > +	 RefPtr<Node> protect = this;
> 
> Same question here.  If we're fixing crashes, we should have tests that
document that.

These ref's allows us to safely access the parent node and its children.  It
wasn't add to fix a crash, but to prevent one.

> >> Source/WebCore/dom/ContainerNode.cpp:371
> >> +	  for (RefPtr<Node> child = firstChild(); child; child =
child->nextSibling())
> >> +	      child->willRemove();
> > 
> > What will happen to the 3rd child, if calling willRemove on the 1st removes
the 2nd?  Won't it get left out in the cold? (aka, never get a willRemove()?)
> 
> What will happen if one of these nodes gets moved to another parent during
this operation?  It seems like we'll call willRemove on nodes that aren't
actually going to be removed.
> 
> > Source/WebCore/dom/ContainerNode.cpp:752
> > +	     if (child->parentNode() != this) // Check for child being removed
from subtree while reparenting.
> > +		 break;
> 
> What if child N gets moved to the first or last sibling position during this
operation?  It seems like we'll either call insertedIntoDocument too many or
too few times in that case, which could cause problems.

The current code calls insertedIntoDocument too many times while the proposed
patch could call too few times.  Both behaviors are incorrect.	We need to deal
with the correctness issue by queueing up the notify calls while traversing the
tree and then making the notify calls in order.

I will be filing a separate bug for the correctness issue with an outline of
the proposed fix.