Bug 68866

Summary: CompositeEditCommand::prune should remove subtree at once
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: HTML EditingAssignee: Ryosuke Niwa <rniwa>
Status: RESOLVED FIXED    
Severity: Normal CC: cshu, darin, enrica, kenneth, morrita, ojan, tkent, tonikitoo, tony
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 68874    
Attachments:
Description Flags
refactoring
none
Fixed per comments darin: review+

Description Ryosuke Niwa 2011-09-26 21:37:32 PDT
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.
Comment 1 Ryosuke Niwa 2011-09-26 21:53:42 PDT
Created attachment 108786 [details]
refactoring
Comment 2 Darin Adler 2011-09-27 09:36:59 PDT
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.
Comment 3 Ryosuke Niwa 2011-09-27 09:46:11 PDT
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.
Comment 4 Ryosuke Niwa 2011-09-27 09:53:31 PDT
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.
Comment 5 Ryosuke Niwa 2011-09-27 11:14:14 PDT
Created attachment 108871 [details]
Fixed per comments
Comment 6 Ryosuke Niwa 2011-09-27 11:15:21 PDT
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).
Comment 7 Ryosuke Niwa 2011-09-27 13:50:40 PDT
Landed in http://trac.webkit.org/changeset/96150.