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 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(
     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;

[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
     // 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;
-    }
+    findCommonAncestor(
+        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