Bug 68866 – CompositeEditCommand::prune should remove subtree at once

• Component: HTML Editing
• Status: RESOLVED FIXED

[Ryosuke Niwa]

The way CompositeEditCommand::prune is implemented now is quite inefficient. It removes the deepest node and climb up the tree to remove ancestors. Instead, we can just figure out the highest node to remove and get rid of the subtree at once.

[Ryosuke Niwa]

Created attachment 108786 [details]
refactoring

[Darin Adler]

Comment on attachment 108786 [details]
refactoring

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

review- because of the traverseNextSibling issue, and in part due to lack of test

> Source/WebCore/ChangeLog:9
> +        This reduces the number of node removals from O(n) to O(1) where n is the depth of the tree.

Can we make a performance test demonstrating this fix? Ojan’s performance harness typically makes that easy.

> Source/WebCore/editing/CompositeEditCommand.cpp:254
> +            n = n->nextSibling();

I think you want:

    n = n->traverseNextSibling(node);

here, not just nextSibling.

> Source/WebCore/editing/CompositeEditCommand.cpp:277
> +void CompositeEditCommand::prune(PassRefPtr<Node> prpNode)

Normally we only use the "prp" naming if we are transferring ownership to a local variable with a simpler name. Since we’re not doing that here, a prp prefix is not necessary.

> Source/WebCore/editing/CompositeEditCommand.cpp:280
> +        removeNode(highestNodeToRemove);

This should probably have a “release” in it.

[Ryosuke Niwa]

Comment on attachment 108786 [details]
refactoring

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

>> Source/WebCore/editing/CompositeEditCommand.cpp:254
>> +            n = n->nextSibling();
> 
> I think you want:
> 
>     n = n->traverseNextSibling(node);
> 
> here, not just nextSibling.

Ah, you're right. Will fix.

>> Source/WebCore/editing/CompositeEditCommand.cpp:277
>> +void CompositeEditCommand::prune(PassRefPtr<Node> prpNode)
> 
> Normally we only use the "prp" naming if we are transferring ownership to a local variable with a simpler name. Since we’re not doing that here, a prp prefix is not necessary.

Will fix.

>> Source/WebCore/editing/CompositeEditCommand.cpp:280
>> +        removeNode(highestNodeToRemove);
> 
> This should probably have a “release” in it.

Good point. Will do.

[Ryosuke Niwa]

Comment on attachment 108786 [details]
refactoring

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

>> Source/WebCore/ChangeLog:9
>> +        This reduces the number of node removals from O(n) to O(1) where n is the depth of the tree.
> 
> Can we make a performance test demonstrating this fix? Ojan’s performance harness typically makes that easy.

Unfortunately not. This function isn't exposed to DRT or is used in any obvious way by an editing command to test it.

I could tweak breakOutOfEmptyMailBlockquotedParagraph to call this function but that seems like a bad testing strategy because any changes to breakOutOfEmptyMailBlockquotedParagraph will invalidate the test.

[Ryosuke Niwa]

Created attachment 108871 [details]
Fixed per comments

[Ryosuke Niwa]

Comment on attachment 108871 [details]
Fixed per comments

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

> Source/WebCore/editing/CompositeEditCommand.cpp:267
> +    Node* rootEditableElement = node ? node->rootEditableElement() : 0;

This will make highestNodeToRemoveInPruning O(n) instead of O(n^2).

[Ryosuke Niwa]

Landed in http://trac.webkit.org/changeset/96150.