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+

Ryosuke Niwa
Reported 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.
Attachments
refactoring (4.10 KB, patch)
2011-09-26 21:53 PDT, Ryosuke Niwa
no flags
Fixed per comments (3.88 KB, patch)
2011-09-27 11:14 PDT, Ryosuke Niwa
darin: review+
Ryosuke Niwa
Comment 1 2011-09-26 21:53:42 PDT
Created attachment 108786 [details] refactoring
Darin Adler
Comment 2 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.
Ryosuke Niwa
Comment 3 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.
Ryosuke Niwa
Comment 4 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.
Ryosuke Niwa
Comment 5 2011-09-27 11:14:14 PDT
Created attachment 108871 [details] Fixed per comments
Ryosuke Niwa
Comment 6 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).
Ryosuke Niwa
Comment 7 2011-09-27 13:50:40 PDT
Note You need to log in before you can comment on or make changes to this bug.