Change finding common ancestor from O(n^2) to O(n)

third_party/WebKit/Source/core/input/PointerEventManager.cpp

Index: third_party/WebKit/Source/core/input/PointerEventManager.cpp
diff --git a/third_party/WebKit/Source/core/input/PointerEventManager.cpp b/third_party/WebKit/Source/core/input/PointerEventManager.cpp
index 9f8556979c8d409b9338455f071d73f776cfc2b2..1000ba42c635ca638c67232c04d73eaddeec691c 100644
--- a/third_party/WebKit/Source/core/input/PointerEventManager.cpp
+++ b/third_party/WebKit/Source/core/input/PointerEventManager.cpp
@@ -79,6 +79,38 @@ PlatformMouseEvent mouseEventWithRegion(Node* node, const PlatformMouseEvent& mo
     return newMouseEvent;
 }
 
+void findCommonAncestor(

[mustaq, 2016/04/20 16:09:05]

s/findCommonAncestor/buildAncestorChainsAndFindCommonAncestors/?

Didn't find a shorter alternative!

[dtapuska, 2016/04/20 19:42:28]

Can we add some comments around this in terms of the ordering of the arrays.

When I first looked at it I would have expected the arrays to be reversed

like enteredAncestors[0] is the root; but the arrays are actually inverted.

[Navid Zolghadr, 2016/04/21 14:46:41]

Done.

+    EventTarget* exitedTarget, EventTarget* enteredTarget,
+    HeapVector<Member<Node>, 32> &exitedAncestors,
+    HeapVector<Member<Node>, 32> &enteredAncestors,
+    size_t& exitedAncestorsCommonParentIndex,
+    size_t& enteredAncestorsCommonParentIndex)
+{
+    if (isInDocument(exitedTarget)) {
+        Node* exitedNode = exitedTarget->toNode();
+        exitedNode->updateDistribution();
+        for (Node* node = exitedNode; node; node = FlatTreeTraversal::parent(*node))
+            exitedAncestors.append(node);
+    }
+
+    if (isInDocument(enteredTarget)) {
+        Node* enteredNode = enteredTarget->toNode();
+        enteredNode->updateDistribution();
+        for (Node* node = enteredNode; node; node = FlatTreeTraversal::parent(*node))
+            enteredAncestors.append(node);
+    }
+
+    exitedAncestorsCommonParentIndex = exitedAncestors.size();

[mustaq, 2016/04/20 16:09:05]

Add DCHECKs to emphasize that we are not subtracting 1 from 0U.

[Navid Zolghadr, 2016/04/21 14:46:41]

Why is that needed though? The for/while condition prevents that from happening
anyway. Also I believe these arrays may be empty as the target might have been
removed from its document.

+    enteredAncestorsCommonParentIndex = enteredAncestors.size();
+    for (size_t i = exitedAncestors.size(), j = enteredAncestors.size();

[mustaq, 2016/04/20 16:09:06]

Nit: I think a |while| loop modifying the |*Index| vars directly would be
cleaner than the 2-line |for| loop.

[Navid Zolghadr, 2016/04/21 14:46:41]

Done.

+        i > 0 && j > 0; --i, --j) {
+        if (exitedAncestors[i-1] != enteredAncestors[j-1])
+            break;
+        exitedAncestorsCommonParentIndex = i-1;
+        enteredAncestorsCommonParentIndex = j-1;
+    }
+}
+
 } // namespace
 
 WebInputEventResult PointerEventManager::dispatchPointerEvent(
@@ -182,19 +214,8 @@ void PointerEventManager::sendNodeTransitionEvents(
     // Create lists of all exited/entered ancestors, locate the common ancestor
     HeapVector<Member<Node>, 32> exitedAncestors;

[mustaq, 2016/04/20 16:09:05]

Please add a comment that httparchive=>97% cases have depth<20, and cut down the
initial size to, say, 20.

[Navid Zolghadr, 2016/04/21 14:46:41]

Done.

     HeapVector<Member<Node>, 32> enteredAncestors;
-    if (isInDocument(exitedTarget)) {
-        Node* exitedNode = exitedTarget->toNode();
-        exitedNode->updateDistribution();
-        for (Node* node = exitedNode; node; node = FlatTreeTraversal::parent(*node))
-            exitedAncestors.append(node);
-    }
-
-    if (isInDocument(enteredTarget)) {
-        Node* enteredNode = enteredTarget->toNode();
-        enteredNode->updateDistribution();
-        for (Node* node = enteredNode; node; node = FlatTreeTraversal::parent(*node))
-            enteredAncestors.append(node);
-    }
+    size_t exitedAncestorsCommonParentIndex = 0;
+    size_t enteredAncestorsCommonParentIndex = 0;
 
     // A note on mouseenter and mouseleave: These are non-bubbling events, and they are dispatched if there
     // is a capturing event handler on an ancestor or a normal event handler on the element itself. This special
@@ -210,22 +231,10 @@ void PointerEventManager::sendNodeTransitionEvents(
     //
     // TODO(mustaq): Confirm spec conformance, double-check with other browsers.
 
-    size_t numExitedAncestors = exitedAncestors.size();
-    size_t numEnteredAncestors = enteredAncestors.size();
-
-    size_t exitedAncestorIndex = numExitedAncestors;
-    size_t enteredAncestorIndex = numEnteredAncestors;
-    for (size_t i = 0; i < numExitedAncestors; i++) {
-        for (size_t j = 0; j < numEnteredAncestors; j++) {
-            if (exitedAncestors[i] == enteredAncestors[j]) {
-                exitedAncestorIndex = i;
-                enteredAncestorIndex = j;
-                break;
-            }
-        }
-        if (exitedAncestorIndex <  exitedAncestors.size())
-            break;
-    }
+    findCommonAncestor(
+        exitedTarget, enteredTarget,
+        exitedAncestors, enteredAncestors,
+        exitedAncestorsCommonParentIndex, enteredAncestorsCommonParentIndex);
 
     bool exitedNodeHasCapturingAncestor = false;
     for (size_t j = 0; j < exitedAncestors.size(); j++) {
@@ -236,7 +245,7 @@ void PointerEventManager::sendNodeTransitionEvents(
     }
 
     // Dispatch pointerleave/mouseleave events, in child-to-parent order.
-    for (size_t j = 0; j < exitedAncestorIndex; j++) {
+    for (size_t j = 0; j < exitedAncestorsCommonParentIndex; j++) {
         if (!sendMouseEvent) {
             dispatchPointerEvent(exitedAncestors[j].get(),
                 m_pointerEventFactory.createPointerTransitionEvent(
@@ -272,7 +281,7 @@ void PointerEventManager::sendNodeTransitionEvents(
     }
 
     // Dispatch pointerenter/mouseenter events, in parent-to-child order.
-    for (size_t i = enteredAncestorIndex; i > 0; i--) {
+    for (size_t i = enteredAncestorsCommonParentIndex; i > 0; i--) {
         if (!sendMouseEvent) {
             dispatchPointerEvent(enteredAncestors[i-1].get(),
                 m_pointerEventFactory.createPointerTransitionEvent(