From fec43b8aff1c8cb94dbc521ea8f323336688b526 Mon Sep 17 00:00:00 2001
From: "rniwa@webkit.org"
 <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Date: Tue, 27 Sep 2011 20:51:24 +0000
Subject: [PATCH] CompositeEditCommand::prune should remove subtree at once
 https://bugs.webkit.org/show_bug.cgi?id=68866

Reviewed by Darin Adler.

Extracted the logic to find the highest ancestor to remove as highestNodeToRemoveInPruning from prune.
This reduces the number of node removals from O(n) to O(1) where n is the depth of the tree.

* editing/CompositeEditCommand.cpp:
(WebCore::hasARenderedDescendant): Takes excludedNode in addition to node. excludedNode is used to ignore
the child node from which we climbed up the tree in highestNodeToRemoveInPruning.
(WebCore::highestNodeToRemoveInPruning): Extracted from prune.
(WebCore::CompositeEditCommand::prune):
(WebCore::CompositeEditCommand::breakOutOfEmptyMailBlockquotedParagraph):



git-svn-id: http://svn.webkit.org/repository/webkit/trunk@96150 268f45cc-cd09-0410-ab3c-d52691b4dbfc
---
 Source/WebCore/ChangeLog                        | 17 ++++++++++
 Source/WebCore/editing/CompositeEditCommand.cpp | 45 ++++++++++++++-----------
 2 files changed, 42 insertions(+), 20 deletions(-)

diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index a7beeef..57c2e77 100644
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,20 @@
+2011-09-27  Ryosuke Niwa  <rniwa@webkit.org>
+
+        CompositeEditCommand::prune should remove subtree at once
+        https://bugs.webkit.org/show_bug.cgi?id=68866
+
+        Reviewed by Darin Adler.
+
+        Extracted the logic to find the highest ancestor to remove as highestNodeToRemoveInPruning from prune.
+        This reduces the number of node removals from O(n) to O(1) where n is the depth of the tree.
+
+        * editing/CompositeEditCommand.cpp:
+        (WebCore::hasARenderedDescendant): Takes excludedNode in addition to node. excludedNode is used to ignore
+        the child node from which we climbed up the tree in highestNodeToRemoveInPruning.
+        (WebCore::highestNodeToRemoveInPruning): Extracted from prune.
+        (WebCore::CompositeEditCommand::prune):
+        (WebCore::CompositeEditCommand::breakOutOfEmptyMailBlockquotedParagraph):
+
 2011-09-27  David Hyatt  <hyatt@apple.com>
 
         https://bugs.webkit.org/show_bug.cgi?id=68922
diff --git a/Source/WebCore/editing/CompositeEditCommand.cpp b/Source/WebCore/editing/CompositeEditCommand.cpp
index 804ed13..acb1d38 100644
--- a/Source/WebCore/editing/CompositeEditCommand.cpp
+++ b/Source/WebCore/editing/CompositeEditCommand.cpp
@@ -247,10 +247,13 @@ HTMLElement* CompositeEditCommand::replaceElementWithSpanPreservingChildrenAndAt
     return command->spanElement();
 }
 
-static bool hasARenderedDescendant(Node* node)
+static bool hasARenderedDescendant(Node* node, Node* excludedNode)
 {
-    Node* n = node->firstChild();
-    while (n) {
+    for (Node* n = node->firstChild(); n;) {
+        if (n == excludedNode) {
+            n = n->traverseNextSibling(node);
+            continue;
+        }
         if (n->renderer())
             return true;
         n = n->traverseNextNode(node);
@@ -258,20 +261,24 @@ static bool hasARenderedDescendant(Node* node)
     return false;
 }
 
-void CompositeEditCommand::prune(PassRefPtr<Node> prpNode)
+static Node* highestNodeToRemoveInPruning(Node* node)
 {
-    RefPtr<Node> node = prpNode;
-
-    while (node) {
-        // If you change this rule you may have to add an updateLayout() here.
-        RenderObject* renderer = node->renderer();
-        if (renderer && (!renderer->canHaveChildren() || hasARenderedDescendant(node.get()) || node->rootEditableElement() == node))
-            return;
-            
-        RefPtr<ContainerNode> next = node->parentNode();
-        removeNode(node);
-        node = next;
+    Node* previousNode = 0;
+    Node* rootEditableElement = node ? node->rootEditableElement() : 0;
+    for (; node; node = node->parentNode()) {
+        if (RenderObject* renderer = node->renderer()) {
+            if (!renderer->canHaveChildren() || hasARenderedDescendant(node, previousNode) || rootEditableElement == node)
+                return previousNode;
+        }
+        previousNode = node;
     }
+    return 0;
+}
+
+void CompositeEditCommand::prune(PassRefPtr<Node> node)
+{
+    if (RefPtr<Node> highestNodeToRemove = highestNodeToRemoveInPruning(node.get()))
+        removeNode(highestNodeToRemove.release());
 }
 
 void CompositeEditCommand::splitTextNode(PassRefPtr<Text> node, unsigned offset)
@@ -1165,11 +1172,9 @@ bool CompositeEditCommand::breakOutOfEmptyMailBlockquotedParagraph()
     // A line break is either a br or a preserved newline.
     ASSERT(caretPos.deprecatedNode()->hasTagName(brTag) || (caretPos.deprecatedNode()->isTextNode() && caretPos.deprecatedNode()->renderer()->style()->preserveNewline()));
     
-    if (caretPos.deprecatedNode()->hasTagName(brTag)) {
-        Position beforeBR(positionInParentBeforeNode(caretPos.deprecatedNode()));
-        removeNode(caretPos.deprecatedNode());
-        prune(beforeBR.deprecatedNode());
-    } else if (caretPos.deprecatedNode()->isTextNode()) {
+    if (caretPos.deprecatedNode()->hasTagName(brTag))
+        removeNodeAndPruneAncestors(caretPos.deprecatedNode());
+    else if (caretPos.deprecatedNode()->isTextNode()) {
         ASSERT(caretPos.deprecatedEditingOffset() == 0);
         Text* textNode = static_cast<Text*>(caretPos.deprecatedNode());
         ContainerNode* parentNode = textNode->parentNode();
-- 
2.7.4