Changeset 200690 in webkit

Timestamp:

May 11, 2016, 9:25:53 AM (9 years ago)

Author:

Chris Dumez

Message:

Optimize DataDetection's searchForLinkRemovingExistingDDLinks()
​https://bugs.webkit.org/show_bug.cgi?id=157561

Reviewed by Ryosuke Niwa.

Optimize DataDetection's searchForLinkRemovingExistingDDLinks():

1. The first loop was using Node::childNodes() to iterate over the child elements. Because of the recursive call, we may end up prepending children as we iterate over them. This is an issue because the childCount was cached before the loop and vector it would blow away the cache inside the NodeList. Switch to using ElementTraversal which should be both safer and more efficient. I don't believe we can use our nice ElementChildIterator here unfortunately as we would hit assertions due the the DOM mutations while iterating.
2. The second loop was using again Node::childNodes() and kept calling item(0) to get the first child and move it to make it the previous sibling of its old parent. Again, using childNodes() here is super inefficient because we keep modifying the children and childNodes() returns a live NodeList. The call to NodeList::length() would cache all the children in a Vector, only to blow that cache away after removing the first child. Switch to using ContainerNode::firstChild().
3. Drop the parentElement parameter as we can just get it from the child.
4. Use tighter typing so we don't end up calling the implementations of insertBefore() / removeChild() that are on Node, thus unnecessarily doing a is<ContainerNode>() check every time.
5. Pass element by reference instead of pointer as it cannot be null.

• editing/cocoa/DataDetection.mm:

(WebCore::removeResultLinksFromAnchor):
(WebCore::searchForLinkRemovingExistingDDLinks):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• editing/cocoa/DataDetection.mm (modified) (4 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2016-05-11  Chris Dumez  <cdumez@apple.com>
+
+        Optimize DataDetection's searchForLinkRemovingExistingDDLinks()
+        https://bugs.webkit.org/show_bug.cgi?id=157561
+
+        Reviewed by Ryosuke Niwa.
+
+        Optimize DataDetection's searchForLinkRemovingExistingDDLinks():
+        1. The first loop was using Node::childNodes() to iterate over the child
+           elements. Because of the recursive call, we may end up prepending
+           children as we iterate over them. This is an issue because the
+           childCount was cached before the loop and vector it would blow away
+           the cache inside the NodeList. Switch to using ElementTraversal which
+           should be both safer and more efficient. I don't believe we can use
+           our nice ElementChildIterator here unfortunately as we would hit
+           assertions due the the DOM mutations while iterating.
+        2. The second loop was using again Node::childNodes() and kept calling
+           item(0) to get the first child and move it to make it the previous
+           sibling of its old parent. Again, using childNodes() here is super
+           inefficient because we keep modifying the children and childNodes()
+           returns a live NodeList. The call to NodeList::length() would cache
+           all the children in a Vector, only to blow that cache away after
+          removing the first child. Switch to using ContainerNode::firstChild().
+        3. Drop the parentElement parameter as we can just get it from the child.
+        4. Use tighter typing so we don't end up calling the implementations of
+           insertBefore() / removeChild() that are on Node, thus unnecessarily
+           doing a is<ContainerNode>() check every time.
+        5. Pass element by reference instead of pointer as it cannot be null.
+
+        * editing/cocoa/DataDetection.mm:
+        (WebCore::removeResultLinksFromAnchor):
+        (WebCore::searchForLinkRemovingExistingDDLinks):
+
 2016-05-11  Rawinder Singh  <rawinder.singh-webkit@cisra.canon.com.au>
 

trunk/Source/WebCore/editing/cocoa/DataDetection.mm

@@ -30 +30 @@
 #import "CSSStyleDeclaration.h"
 #import "DataDetectorsSPI.h"
+#import "ElementTraversal.h"
 #import "FrameView.h"
 #import "HTMLAnchorElement.h"
@@ -249 +250 @@
 }
 
-static void removeResultLinksFromAnchor(Node* node, Node* nodeParent)
+static void removeResultLinksFromAnchor(Element& element)
 {
     // Perform a depth-first search for anchor nodes, which have the DDURLScheme attribute set to true,
-    // take their children and insert them before the anchor,
-    // and then remove the anchor.
-    
-    if (!node)
+    // take their children and insert them before the anchor, and then remove the anchor.
+
+    // Note that this is not using ElementChildIterator because we potentially prepend children as we iterate over them.
+    for (auto* child = ElementTraversal::firstChild(element); child; child = ElementTraversal::nextSibling(*child))
+        removeResultLinksFromAnchor(*child);
+
+    auto* elementParent = element.parentElement();
+    if (!elementParent)
         return;
     
-    BOOL nodeIsDDAnchor = is<HTMLAnchorElement>(*node) && equalIgnoringASCIICase(downcast<Element>(*node).fastGetAttribute(x_apple_data_detectorsAttr), "true");
-    
-    RefPtr<NodeList> children = node->childNodes();
-    unsigned childCount = children->length();
-    for (size_t i = 0; i < childCount; i++) {
-        Node* child = children->item(i);
-        if (is<Element>(*child))
-            removeResultLinksFromAnchor(child, node);
-    }
-    
-    if (nodeIsDDAnchor && nodeParent) {
-        children = node->childNodes();
-        childCount = children->length();
-        
-        // Iterate over the children and move them all onto the same level as this anchor.
-        // Remove the anchor afterwards.
-        for (size_t i = 0; i < childCount; i++) {
-            Node* child = children->item(0);
-            nodeParent->insertBefore(child, node, ASSERT_NO_EXCEPTION);
-        }
-        nodeParent->removeChild(node, ASSERT_NO_EXCEPTION);
-    }
+    bool elementIsDDAnchor = is<HTMLAnchorElement>(element) && equalIgnoringASCIICase(element.fastGetAttribute(x_apple_data_detectorsAttr), "true");
+    if (!elementIsDDAnchor)
+        return;
+
+    // Iterate over the children and move them all onto the same level as this anchor. Remove the anchor afterwards.
+    while (auto* child = element.firstChild())
+        elementParent->insertBefore(*child, &element);
+
+    elementParent->removeChild(element);
 }
 
@@ -288 +280 @@
     while (node) {
         if (is<HTMLAnchorElement>(*node)) {
-            if (!equalIgnoringASCIICase(downcast<Element>(*node).fastGetAttribute(x_apple_data_detectorsAttr), "true"))
+            auto& anchor = downcast<HTMLAnchorElement>(*node);
+            if (!equalIgnoringASCIICase(anchor.fastGetAttribute(x_apple_data_detectorsAttr), "true"))
                 return true;
-            removeResultLinksFromAnchor(node, node->parentElement());
+            removeResultLinksFromAnchor(anchor);
             didModifyDOM = true;
         }
@@ -300 +293 @@
             while (node) {
                 if (is<HTMLAnchorElement>(*node)) {
-                    if (!equalIgnoringASCIICase(downcast<Element>(*node).fastGetAttribute(x_apple_data_detectorsAttr), "true"))
+                    auto& anchor = downcast<HTMLAnchorElement>(*node);
+                    if (!equalIgnoringASCIICase(anchor.fastGetAttribute(x_apple_data_detectorsAttr), "true"))
                         return true;
-                    removeResultLinksFromAnchor(node, node->parentElement());
+                    removeResultLinksFromAnchor(anchor);
                     didModifyDOM = true;
                 }