Fix focus navigation for nested slot case

third_party/WebKit/Source/core/dom/shadow/SlotScopedTraversal.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/dom/shadow/SlotScopedTraversal.h"
 
 #include "core/dom/Element.h"
 #include "core/dom/ElementTraversal.h"
 #include "core/html/HTMLSlotElement.h"
 
@@ skipping 13 matching lines @@
   // is directly assigned to a slot.
   Element* element = const_cast<Element*>(&current);
   for (; element; element = element->parentElement()) {
     if (element->assignedSlot())
       break;
   }
   return element;
 }
 
 Element* SlotScopedTraversal::next(const Element& current) {
-  // current.assignedSlot returns a slot only when current is assigned
-  // explicitly
-  // If current is assigned to a slot, return a descendant of current, which is
-  // in the assigned scope of the same slot as current.
-  HTMLSlotElement* slot = current.assignedSlot();
+  Element* next = nullptr;
   Element* nearestAncestorAssignedToSlot =

[hayato, 2016/10/24 06:43:26]

Could we rename |nearestAncestorAssignedToSlot| to 
|nearestInclusiveAncestorAssignedToSlot|?

The current name might be confusing.

[kochi, 2016/10/24 08:55:20]

I agree the renaming, and adding "Inclusive" clarifies what
it does more.  With that, the comment in the function (L23-24)
become redundant as the function name almost says the same thing.
And as you said in the other comment, 'directly assigned' is not
preferable.

Also I renamed variables that hold return value from the function
to 'slottedAncestor', which would be enough to describe what it is
in a function.

       SlotScopedTraversal::nearestAncestorAssignedToSlot(current);
-  if (slot) {
-    if (Element* next = ElementTraversal::next(current, &current))
-      return next;
+  // Search within children of an element which is directly assigned to a slot.

[hayato, 2016/10/24 06:43:26]

Could you remove |directly| from the comments in this file?
It is redundant. We do not want to use |indirectly assigned| in any case, which
is confusing.

[kochi, 2016/10/24 08:55:20]

Done.

+  if (current.assignedSlot()) {
+    next = ElementTraversal::next(current, &current);
   } else {
     // If current is in assigned scope, find an assigned ancestor.
     DCHECK(nearestAncestorAssignedToSlot);
-    if (Element* next =
-            ElementTraversal::next(current, nearestAncestorAssignedToSlot))
-      return next;
-    slot = nearestAncestorAssignedToSlot->assignedSlot();
-    DCHECK(slot);
+    if (current == nearestAncestorAssignedToSlot)

[hayato, 2016/10/24 06:43:26]

When does it happen?
It looks that current.assignedSlot() is true if current ==
nearestAncestorAssignedToSlot.

[kochi, 2016/10/24 08:55:20]

Good catch.  Looks like an artifact while I was debugging.
Remved.

+      return nullptr;
+    next = ElementTraversal::next(current, nearestAncestorAssignedToSlot);
   }
+
+  // Exclude elements that is assigned to another slot scope.
+  while (next && next->assignedSlot())
+    next = ElementTraversal::nextSkippingChildren(*next, &current);
+
+  if (next) {
+    DCHECK(!next->assignedSlot());
+    return next;
+  }
+
+  // Seek to the next element assigned to the same slot.
+  HTMLSlotElement* slot = nearestAncestorAssignedToSlot->assignedSlot();
+  DCHECK(slot);
   HeapVector<Member<Node>> assignedNodes = slot->assignedNodes();
   size_t currentIndex = assignedNodes.find(*nearestAncestorAssignedToSlot);
   DCHECK_NE(currentIndex, kNotFound);
   for (++currentIndex; currentIndex < assignedNodes.size(); ++currentIndex) {
     if (assignedNodes[currentIndex]->isElementNode())
       return toElement(assignedNodes[currentIndex]);
   }
   return nullptr;
 }
 
 Element* SlotScopedTraversal::previous(const Element& current) {
   Element* nearestAncestorAssignedToSlot =
       SlotScopedTraversal::nearestAncestorAssignedToSlot(current);
   DCHECK(nearestAncestorAssignedToSlot);
-  // NodeTraversal within nearestAncestorAssignedToSlot
-  if (Element* previous =
-          ElementTraversal::previous(current, nearestAncestorAssignedToSlot))
-    return previous;
-  // If null, jump to previous assigned node's descendant
+
+  // Search within children of an element which is directly assigned to a slot.
+  Element* previous =
+      ElementTraversal::previous(current, nearestAncestorAssignedToSlot);
+
+  // TODO(kochi): repeatedly calling nearestAncestorAssignedToSlot() which
+  // is O(depth from directly slotted ancestor) and can be very slow.
+  while (previous) {

[hayato, 2016/10/24 06:43:26]

Could you extract L81-L88 as a separate function?
It looks there are similar patterns in other places.

In addition to that, I do not understand why we need this check.

Could you explain briefly what this check achieves?

[kochi, 2016/10/24 08:55:20]

Separated as a function previousWithinSameSlotScopeOrSelf().

In the original code, it returned element from
ElementTraversal::previous() directly, but that element could be
in a different slot scope (i.e. assigned to another slot).

As this SlotScopedTraversal has to guarantee that the traversal
happens within the same slot scope, we have to try to find a previous
element that is in the same slot scope.

For SlotScoepdTraversal::previous(current), |current|'s scope
is |nearestAncestorAssignedToSlot|'s slot. If |current|'s previous
or any of its ancestor is assigned to another slot, the scopes are
different.  So we check the equality of the scope with nearest
assigned slots, and if they are same, return the previous.

Otherwise, such previous element is in a different slot scope,
and in the light DOM of a shadow host,
so move up to the shadow host to continue searching.
(|ancestor->parentElement()| on line 87 should be a shadow host.)

+    Element* ancestor =
+        SlotScopedTraversal::nearestAncestorAssignedToSlot(*previous);
+    DCHECK(ancestor);
+    if (ancestor == nearestAncestorAssignedToSlot)
+      return previous;
+    previous = ancestor->parentElement();
+  }
+
+  // Seek to the previous element assigned to the same slot.
   const HeapVector<Member<Node>> assignedNodes =
       nearestAncestorAssignedToSlot->assignedSlot()->assignedNodes();
   size_t currentIndex =
       assignedNodes.reverseFind(*nearestAncestorAssignedToSlot);
   DCHECK_NE(currentIndex, kNotFound);
   for (; currentIndex > 0; --currentIndex) {
     const Member<Node> assignedPrevious = assignedNodes[currentIndex - 1];
-    if (assignedPrevious->isElementNode()) {
-      if (Element* last =
-              ElementTraversal::lastWithin(*toElement(assignedPrevious)))
+    if (!assignedPrevious->isElementNode())
+      continue;
+
+    Element* last = ElementTraversal::lastWithin(*toElement(assignedPrevious));
+    if (!last)
+      return toElement(assignedPrevious);
+
+    while (last) {
+      Element* ancestor =
+          SlotScopedTraversal::nearestAncestorAssignedToSlot(*last);
+      DCHECK(ancestor);
+      if (ancestor == assignedPrevious)
         return last;
-      return toElement(assignedPrevious);
+      last = ancestor->parentElement();
     }
+    NOTREACHED();
   }
   return nullptr;
 }
 
 bool SlotScopedTraversal::isSlotScoped(const Element& current) {
   return SlotScopedTraversal::nearestAncestorAssignedToSlot(current);
 }
 
 }  // namespace blink