Bug 113433 – ContainerNode::removeChildren should first detach the children then remove them

• Component: DOM
• Status: RESOLVED FIXED

[Andrei Bucur]

The order of operations in ContainerNode::removeChildren is unintuitive and can lead to subtle bugs. The function ContainerNode::removeChild first detaches the child and then removes it from the DOM tree. ContainerNode::removeChildren does it the other way around. This leaves the render tree in an inconsistent state when calling detach on the removed nodes (the renderers point to nodes that are no longer in the DOM).
The main reason invoked for this behaviour is the performance gain. However, the removeChildren method makes two iterations thorough the children list that may be avoided:
- removedChildren.reserveInitialCapacity(childNodeCount()); // childNodeCount is O(n)
- children detachment is another O(n)
The patch should also try to remove these time consumers as well.

[Andrei Bucur]

Created attachment 195951 [details]
Patch

[Antti Koivisto]

Comment on attachment 195951 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=195951&action=review

> Source/WebCore/dom/ContainerNode.cpp:459
> +static void willRemoveChildren(ContainerNode* container, NodeVector& children)

This function has unclear purpose (doing both pre-removal tasks and building up the child vector). I think it would be better to pass in an initialized child vector and possibly rename the function to something more descriptive (though I don't have great suggestions, fireEventsBeforeRemovingAllChildren or something).

[Andrei Bucur]

This will be fixed in https://bugs.webkit.org/show_bug.cgi?id=113517 .

*** This bug has been marked as a duplicate of bug 113517 ***

[Andrei Bucur]

https://bugs.webkit.org/show_bug.cgi?id=113517 is a lot harder than initially estimated. Just refactor the code a bit and first detach then remove the nodes.

[Andrei Bucur]

Created attachment 198113 [details]
Patch

[Andrei Bucur]

Created attachment 198121 [details]
Patch

[Andrei Bucur]

*** This bug has been marked as a duplicate of bug 114677 ***

[Andrei Bucur]

Use this bug to track the simple change of first detaching a child before it is removed.

[Andrei Bucur]

Created attachment 198725 [details]
Simple version of the patch

[Andrei Bucur]

Created attachment 198738 [details]
Perf results for the very simple patch

innserHTML-setter.html and html5-full-render.html
There doesn't seem to be any performance regression. This is aligned with the small performance boost found in the more complex patch.

[Elliott Sprehn]

I think the Simple version is the way to go. Make tiny changes and watch the perf and security issues as you go. Calling shrink(0) on the vector is also really weird, I don't think that's what you want to do since it frees the vector buffer and you end up mallocing again.

btw I don't think html5-full-render.html is the right benchmark for this. It's doing document.write() which goes directly at the parser/tree builder. It doesn't go through innerHTML which would benchmark this code.

[Andrei Bucur]

Great, thanks for the review!

(In reply to comment #11)
> I think the Simple version is the way to go. Make tiny changes and watch the perf and security issues as you go. Calling shrink(0) on the vector is also really weird, I don't think that's what you want to do since it frees the vector buffer and you end up mallocing again.

shrink() doesn't modify the capacity. It will just remove the nodes, keeping the buffer intact. This is why I said reserveInitialCapacity() is not required any more.
shrinkCapacity() does what you describe.
The advanced patch saves a free() and possibly a malloc(). The free() that happens when exiting willRemoveChildren() and the possible malloc() when calling reserveInitialCapacity, if the inline size of the vector is smaller than the number of nodes. I'm not counting the loop through the children required when calling reserveInitialCapacity.

> 
> btw I don't think html5-full-render.html is the right benchmark for this. It's doing document.write() which goes directly at the parser/tree builder. It doesn't go through innerHTML which would benchmark this code.

[Ryosuke Niwa]

Comment on attachment 198725 [details]
Simple version of the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=198725&action=review

> Source/WebCore/dom/ContainerNode.cpp:633
> -            for (size_t i = 0; i < removedChildren.size(); ++i) {
> -                Node* removedChild = removedChildren[i].get();
> -                if (removedChild->attached())
> -                    removedChild->detach();
> +                removedChildren.append(n.release());

Why aren't we moving this loop before the other loop?
Is the comment you removed no longer applicable?

[Andrei Bucur]

Comment on attachment 198725 [details]
Simple version of the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=198725&action=review

>> Source/WebCore/dom/ContainerNode.cpp:633
>> +                removedChildren.append(n.release());
> 
> Why aren't we moving this loop before the other loop?
> Is the comment you removed no longer applicable?

No, it's not applicable. The pointers are fixed after each node is removed and I didn't find any evidence of detachment being faster for removed nodes that a new iteration through them is worth the effort.

[Ryosuke Niwa]

Comment on attachment 198725 [details]
Simple version of the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=198725&action=review

>>> Source/WebCore/dom/ContainerNode.cpp:633
>>> +                removedChildren.append(n.release());
>> 
>> Why aren't we moving this loop before the other loop?
>> Is the comment you removed no longer applicable?
> 
> No, it's not applicable. The pointers are fixed after each node is removed and I didn't find any evidence of detachment being faster for removed nodes that a new iteration through them is worth the effort.

Please clarify that in the change log.

[Andrei Bucur]

Created attachment 198893 [details]
Patch for landing

[WebKit Commit Bot]

Comment on attachment 198893 [details]
Patch for landing

Clearing flags on attachment: 198893

Committed r148754: <http://trac.webkit.org/changeset/148754>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.