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,

[bokan, 2016/04/21 21:38:29]

Seems like these can't be null? If that's true, make them references, preferably
const ref if possible.

[Navid Zolghadr, 2016/04/21 23:40:14]

No. They can be null. The isInDocument checks for the nullity and returns false.

[bokan, 2016/04/22 00:52:54]

Got it, ok, fine as they are (if possible though, make them pointer to const)

[Navid Zolghadr, 2016/04/22 17:04:12]

This turned out to be harder than I thought. Marking these EventTargets as const
make toNode function not callable as that function is not marked as const and
changing that would need me to change quite a lot of things around the code. Are
you okay with having these pointers as non-const or do you have a better
solution like maybe const_cast which I'm not sure is as cleaner than what it is
now?

[bokan, 2016/04/22 17:30:52]

Nah, if it's more trouble lgtm as-is. Our code is only mostly const-correct...

+    HeapVector<Member<Node>, 20> &exitedAncestors,
+    HeapVector<Member<Node>, 20> &enteredAncestors,
+    size_t& exitedAncestorsCommonParentIndex,
+    size_t& enteredAncestorsCommonParentIndex)

[bokan, 2016/04/21 21:38:28]

Output parameters should be passed by pointer.

[Navid Zolghadr, 2016/04/21 23:40:14]

You mean like size_t* and  HeapVector<Member<Node>, 20>*? Are you sure we do
that here in Blink? That seems to be a C way of doing this.
Then do I need to add another check to make sure those pointer are not null?

[bokan, 2016/04/22 00:52:54]

Yup, see the bit about output params here:
https://google.github.io/styleguide/cppguide.html#Reference_Arguments (when
Blink and Chromium style guide doesn't have a specific rule, we use Google
style). Reference output probably exists in some places in Blink, but we use
pointer so it's clearer from the call site the param will be output.

You can put DCHECKs for nullity but also put 'out' in the param names.

[Navid Zolghadr, 2016/04/22 17:04:12]

Done.

+{
+    // Index 0 element in the ancestors arrays will be the corresponding
+    // target. So the root of their document will be their last element.
+

[bokan, 2016/04/21 21:38:29]

I see you check if exitedTarget == enteredTarget before calling here, but adding
an DCHECK in here wouldn't hurt. 

[Navid Zolghadr, 2016/04/21 23:40:14]

I don't think that is needed. This function doesn't make any assumption whether
those nodes are the same or not. It just fills up the ancestor array and if they
happen to be the same node that single node will be the only member of those two
arrays which is correct.

[bokan, 2016/04/22 00:52:54]

Whoops, yah, you're right. That's fine.

+    if (isInDocument(exitedTarget)) {
+        Node* exitedNode = exitedTarget->toNode();

[bokan, 2016/04/21 21:38:28]

Either DCHECK that exitedNode != nullptr (if indeed it must be a Node) or handle
the case where it's not a Node.

[Navid Zolghadr, 2016/04/21 23:40:14]

Neither the DCHECK nor the behavior of handling when it is not a node was there
before (as I just moved this code here in this function). So I assume it means
it is always a node. So I will just add a DCHECK here.

[bokan, 2016/04/22 00:52:54]

Acknowledged.

[Navid Zolghadr, 2016/04/22 17:04:12]

Done.

+        exitedNode->updateDistribution();
+        for (Node* node = exitedNode; node; node = FlatTreeTraversal::parent(*node))
+            exitedAncestors.append(node);
+    }
+
+    if (isInDocument(enteredTarget)) {
+        Node* enteredNode = enteredTarget->toNode();
+        enteredNode->updateDistribution();

[bokan, 2016/04/21 21:38:29]

Question: what does updateDistribution do?

[Navid Zolghadr, 2016/04/21 23:40:14]

To be honest with you, I'm not sure myself. From the looks of it and where it's
used around the code it seems whenever we want to play with dom like take
parents of the nodes if there was a call previously to js we call
updateDistribution to make sure we restructure/re-style or something like that
if js had changed the dom as the result of the previous call.

[bokan, 2016/04/22 00:52:54]

Hmm, I've never seen it before. But I can see it was there before, just curious
what it meant :)

+        for (Node* node = enteredNode; node; node = FlatTreeTraversal::parent(*node))
+            enteredAncestors.append(node);
+    }
+
+    exitedAncestorsCommonParentIndex = exitedAncestors.size();
+    enteredAncestorsCommonParentIndex = enteredAncestors.size();

[bokan, 2016/04/21 21:38:29]

One more suggested DCHECK here :), exitedAncestors[exitedAncestors.size() - 1]
== enteredAncestors[enteredAncestors.size() - 1], that is, they should have a
common root.

[Navid Zolghadr, 2016/04/21 23:40:14]

That's not right. They might be from different documents and in that case they
don't have a common root at all.

[bokan, 2016/04/22 00:52:54]

That's what I'm getting at, you have no way of distinguishing that case from the
return values here, it'll just return the first element in each vector (i.e. the
targets themselves) as the common ancestor even if they're different nodes.

[Navid Zolghadr, 2016/04/22 01:46:13]

No. That is not the case. Here is an example
if we call buildAncestorChainsAndFindCommonAncestors(A,B)

If C is the root and and happens to be parent of both A and B
A->C
B->C

these indices will be 1. But if they are in two different documents
A->D
B->C

Then the indices are 2. If the two targets happen to be the same (i.e. A==B)
then the indices are 0. Is that right? Or maybe I'm not quite understanding your
case.

[bokan, 2016/04/22 01:50:47]

Bah, I'm not having a good day...you're totally right. 

+    while (exitedAncestorsCommonParentIndex > 0
+        && enteredAncestorsCommonParentIndex > 0) {
+        if (exitedAncestors[exitedAncestorsCommonParentIndex-1]
+            != enteredAncestors[enteredAncestorsCommonParentIndex-1])
+            break;
+        exitedAncestorsCommonParentIndex--;
+        enteredAncestorsCommonParentIndex--;
+    }
+}
+
 } // 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

[bokan, 2016/04/21 21:38:29]

Doesn't this mean that in 3% of cases we'll incur a heap allocation in here?
That seems a bit excessive. any reason not to leave it at 32? Or at least a a
number that's a couple of nines worth of percent?

[Navid Zolghadr, 2016/04/21 23:40:14]

I don't have a strong answer here.
I had it at 32. But Mustaq suggested to make it 20. Either way I don't think
that matters at all 20 or 32. By creating 20 we are already allocating that
whole array in the memory. If we add more, the array just expands (and
reallocate that 20 that was filled). So in 3% of the cases we reallocate that
20. Either way 12 less pointer (in the case of 20) doesn't really change the
memory or reallocating/copying 20 pointer (in the case of 32) shouldn't be time
consuming here at all.

[bokan, 2016/04/22 00:52:54]

Heap allocations can be fairly expensive and unpredictable, at least (IMO)
compared to saving 12 WORDs, and this would be especially important in event
delivery where we care about latency. Though I agree in this case it's small and
unlikely to make a difference in practice, just more "death by a thousand paper
cuts". Anyway, I'll leave the decision up to you guys :)

+    // 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