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

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

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "core/input/PointerEventManager.h"
 
 #include "core/dom/ElementTraversal.h"
 #include "core/dom/shadow/FlatTreeTraversal.h"
 #include "core/events/MouseEvent.h"
 #include "core/html/HTMLCanvasElement.h"
@@ skipping 61 matching lines @@
     HTMLCanvasElement* canvas = Traversal<HTMLCanvasElement>::firstAncestorOrSelf(*element);
     // In this case, the event target is canvas and mouse rerouting doesn't happen.
     if (canvas == element)
         return mouseEvent;
     String region = canvas->getIdFromControl(element);
     PlatformMouseEvent newMouseEvent = mouseEvent;
     newMouseEvent.setRegion(region);
     return newMouseEvent;
 }
 
+void buildAncestorChainsAndFindCommonAncestors(
+    EventTarget* exitedTarget, EventTarget* enteredTarget,
+    HeapVector<Member<Node>, 20>* exitedAncestorsOut,
+    HeapVector<Member<Node>, 20>* enteredAncestorsOut,
+    size_t* exitedAncestorsCommonParentIndexOut,
+    size_t* enteredAncestorsCommonParentIndexOut)
+{
+    DCHECK(exitedAncestorsOut);
+    DCHECK(enteredAncestorsOut);
+    DCHECK(exitedAncestorsCommonParentIndexOut);
+    DCHECK(enteredAncestorsCommonParentIndexOut);
+
+    // Index 0 element in the ancestors arrays will be the corresponding
+    // target. So the root of their document will be their last element.
+
+    if (isInDocument(exitedTarget)) {
+        Node* exitedNode = exitedTarget->toNode();
+        DCHECK(exitedNode);
+        exitedNode->updateDistribution();
+        for (Node* node = exitedNode; node; node = FlatTreeTraversal::parent(*node))
+            exitedAncestorsOut->append(node);
+    }
+
+    if (isInDocument(enteredTarget)) {
+        Node* enteredNode = enteredTarget->toNode();
+        DCHECK(enteredNode);
+        enteredNode->updateDistribution();
+        for (Node* node = enteredNode; node; node = FlatTreeTraversal::parent(*node))
+            enteredAncestorsOut->append(node);
+    }
+
+    *exitedAncestorsCommonParentIndexOut = exitedAncestorsOut->size();
+    *enteredAncestorsCommonParentIndexOut = enteredAncestorsOut->size();
+    while (*exitedAncestorsCommonParentIndexOut > 0
+        && *enteredAncestorsCommonParentIndexOut > 0) {
+        if ((*exitedAncestorsOut)[(*exitedAncestorsCommonParentIndexOut)-1]
+            != (*enteredAncestorsOut)[(*enteredAncestorsCommonParentIndexOut)-1])
+            break;
+        (*exitedAncestorsCommonParentIndexOut)--;
+        (*enteredAncestorsCommonParentIndexOut)--;
+    }
+}
+
 } // namespace
 
 WebInputEventResult PointerEventManager::dispatchPointerEvent(
     EventTarget* target,
     PointerEvent* pointerEvent,
     bool checkForListener)
 {
     if (!target)
         return WebInputEventResult::NotHandled;
 
@@ skipping 81 matching lines @@
                 pointerEvent, EventTypeNames::pointerout, enteredTarget));
         } else {
             dispatchMouseEvent(exitedTarget,
                 EventTypeNames::mouseout,
                 mouseEventWithRegion(exitedTarget->toNode(), mouseEvent),
                 enteredTarget);
         }
     }
 
     // Create lists of all exited/entered ancestors, locate the common ancestor
-    HeapVector<Member<Node>, 32> exitedAncestors;
-    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);
-    }
+    // Based on httparchive, in more than 97% cases the depth of DOM is less
+    // than 20.
+    HeapVector<Member<Node>, 20> exitedAncestors;
+    HeapVector<Member<Node>, 20> enteredAncestors;
+    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
     // handling is necessary to avoid O(n^2) capturing event handler checks.
     //
     //   Note, however, that this optimization can possibly cause some unanswered/missing/redundant mouseenter or
     // mouseleave events in certain contrived eventhandling scenarios, e.g., when:
     // - the mouseleave handler for a node sets the only capturing-mouseleave-listener in its ancestor, or
     // - DOM mods in any mouseenter/mouseleave handler changes the common ancestor of exited & entered nodes, etc.
     // We think the spec specifies a "frozen" state to avoid such corner cases (check the discussion on "candidate event
     // listeners" at http://www.w3.org/TR/uievents), but our code below preserves one such behavior from past only to
     // match Firefox and IE behavior.
     //
     // 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;
-    }
+    buildAncestorChainsAndFindCommonAncestors(
+        exitedTarget, enteredTarget,
+        &exitedAncestors, &enteredAncestors,
+        &exitedAncestorsCommonParentIndex, &enteredAncestorsCommonParentIndex);
 
     bool exitedNodeHasCapturingAncestor = false;
     for (size_t j = 0; j < exitedAncestors.size(); j++) {
         if (exitedAncestors[j]->hasCapturingEventListeners(EventTypeNames::mouseleave)
             || (RuntimeEnabledFeatures::pointerEventEnabled()
             && exitedAncestors[j]->hasCapturingEventListeners(EventTypeNames::pointerleave)))
             exitedNodeHasCapturingAncestor = true;
     }
 
     // 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(
                     pointerEvent, EventTypeNames::pointerleave, enteredTarget),
                 !exitedNodeHasCapturingAncestor);
         } else {
             dispatchMouseEvent(exitedAncestors[j].get(),
                 EventTypeNames::mouseleave,
                 mouseEventWithRegion(exitedTarget->toNode(), mouseEvent),
                 enteredTarget, 0, !exitedNodeHasCapturingAncestor);
@@ skipping 15 matching lines @@
     // the leave handlers might set a capturing enter handler.
     bool enteredNodeHasCapturingAncestor = false;
     for (size_t i = 0; i < enteredAncestors.size(); i++) {
         if (enteredAncestors[i]->hasCapturingEventListeners(EventTypeNames::mouseenter)
             || (RuntimeEnabledFeatures::pointerEventEnabled()
             && enteredAncestors[i]->hasCapturingEventListeners(EventTypeNames::pointerenter)))
             enteredNodeHasCapturingAncestor = true;
     }
 
     // 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(
                     pointerEvent, EventTypeNames::pointerenter, exitedTarget),
                 !enteredNodeHasCapturingAncestor);
         } else {
             dispatchMouseEvent(enteredAncestors[i-1].get(),
                 EventTypeNames::mouseenter, mouseEvent, exitedTarget,
                 0, !enteredNodeHasCapturingAncestor);
         }
@@ skipping 346 matching lines @@
 
 DEFINE_TRACE(PointerEventManager)
 {
     visitor->trace(m_nodeUnderPointer);
     visitor->trace(m_pointerCaptureTarget);
     visitor->trace(m_pendingPointerCaptureTarget);
 }
 
 
 } // namespace blink