Bug 68866 - CompositeEditCommand::prune should remove subtree at once
Summary: CompositeEditCommand::prune should remove subtree at once
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords:
Depends on:
Blocks: 68874
  Show dependency treegraph
 
Reported: 2011-09-26 21:37 PDT by Ryosuke Niwa
Modified: 2011-09-27 13:50 PDT (History)
9 users (show)

See Also:


Attachments
refactoring (4.10 KB, patch)
2011-09-26 21:53 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Fixed per comments (3.88 KB, patch)
2011-09-27 11:14 PDT, Ryosuke Niwa
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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.