Avoid tail recursion to mitigate stack exhaustion

Source/core/page/FocusController.cpp

 /*
  * Copyright (C) 2006, 2007 Apple Inc. All rights reserved.
  * Copyright (C) 2008 Nuanti Ltd.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
@@ skipping 361 matching lines @@
 // @return The focus element that comes after/before start node.
 //
 // [1] https://html.spec.whatwg.org/multipage/interaction.html#sequential-focus-navigation
 // [2] https://w3c.github.io/webcomponents/spec/shadow/#focus-navigation
 inline Element* findFocusableElementInternal(WebFocusType type, const FocusNavigationScope& scope, Node* node)
 {
     Element* found = (type == WebFocusTypeForward) ? nextFocusableElement(scope, node) : previousFocusableElement(scope, node);
     return found;
 }
 
 Element* findFocusableElementRecursivelyForward(const FocusNavigationScope& scope, Node* start)

[hayato, 2015/06/25 07:31:02]

The function name should be changed?

[kochi, 2015/06/25 07:56:32]

No, this function is still recursive.
(line 391, 404)

The level of recursion is ~equal to DOM nesting level.

The previous code used recursion for sibling DOM nodes. 

[hayato, 2015/06/25 08:04:40]

Acknowledged.

 {
     // Starting node is exclusive.
     Element* found = findFocusableElementInternal(WebFocusTypeForward, scope, start);
-    if (!found)
-        return nullptr;
-    if (isShadowHostDelegatesFocus(*found)) {
-        // If tabindex is positive, find focusable node inside its shadow tree.
-        if (found->tabIndex() >= 0 && isShadowHostWithoutCustomFocusLogic(*found)) {
-            FocusNavigationScope innerScope = FocusNavigationScope::ownedByShadowHost(*found);
-            if (Element* foundInInnerFocusScope = findFocusableElementRecursivelyForward(innerScope, nullptr))
-                return foundInInnerFocusScope;
+    while (found) {
+        if (isShadowHostDelegatesFocus(*found)) {
+            // If tabindex is positive, find focusable node inside its shadow tree.
+            if (found->tabIndex() >= 0 && isShadowHostWithoutCustomFocusLogic(*found)) {
+                FocusNavigationScope innerScope = FocusNavigationScope::ownedByShadowHost(*found);
+                if (Element* foundInInnerFocusScope = findFocusableElementRecursivelyForward(innerScope, nullptr))
+                    return foundInInnerFocusScope;
+            }
+            // Skip to the next node in the same scope.
+            found = findFocusableElementRecursivelyForward(scope, found);
         }
-        // Skip to the next node in the same scope.
-        found = findFocusableElementRecursivelyForward(scope, found);
+        if (!found || !isNonFocusableFocusScopeOwner(*found))
+            break;
+
+        // Now |found| is on a non focusable scope owner (either shadow host or <shadow>)
+        // Find inside the inward scope and return it if found. Otherwise continue searching in the same
+        // scope.
+        FocusNavigationScope innerScope = FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(*found);
+        if (Element* foundInInnerFocusScope = findFocusableElementRecursivelyForward(innerScope, nullptr))
+            return foundInInnerFocusScope;
+
+        found = findFocusableElementInternal(WebFocusTypeForward, scope, found);
     }
-    if (!found || !isNonFocusableFocusScopeOwner(*found))
-        return found;
-
-    // Now |found| is on a non focusable scope owner (either shadow host or <shadow>)
-    // Find inside the inward scope and return it if found. Otherwise continue searching in the same
-    // scope.
-    FocusNavigationScope innerScope = FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(*found);
-    if (Element* foundInInnerFocusScope = findFocusableElementRecursivelyForward(innerScope, nullptr))
-        return foundInInnerFocusScope;
-    return findFocusableElementRecursivelyForward(scope, found);
+    return found;

[hayato, 2015/06/25 07:31:02]

return nullptr;

[kochi, 2015/06/25 07:56:32]

No, if line 398 breaks, |found| can be non-null.

[hayato, 2015/06/25 08:04:40]

Ops. I didn't realize it.
line 398 should `return found`, instead of `break`.

[kochi, 2015/06/25 08:23:38]

Done.

If the code doesn't break there, line 409 should return nullptr, as the original
comment suggests.

 }
 
 Element* findFocusableElementRecursivelyBackward(const FocusNavigationScope& scope, Node* start)

[hayato, 2015/06/25 07:31:02]

The same.

 {
     // Starting node is exclusive.
     Element* found = findFocusableElementInternal(WebFocusTypeBackward, scope, start);
-    if (!found)
-        return nullptr;
+    while (found) {
+        // Now |found| is on a focusable shadow host.
+        // Find inside shadow backwards. If any focusable element is found, return it, otherwise return
+        // the host itself.
+        if (isKeyboardFocusableShadowHost(*found)) {
+            FocusNavigationScope innerScope = FocusNavigationScope::ownedByShadowHost(*found);
+            Element* foundInInnerFocusScope = findFocusableElementRecursivelyBackward(innerScope, nullptr);
+            if (foundInInnerFocusScope)
+                return foundInInnerFocusScope;
+            if (isShadowHostDelegatesFocus(*found))
+                found = findFocusableElementRecursivelyBackward(scope, found);
+            break;
+        }
 
-    // Now |found| is on a focusable shadow host.
-    // Find inside shadow backwards. If any focusable element is found, return it, otherwise return
-    // the host itself.
-    if (isKeyboardFocusableShadowHost(*found)) {
-        FocusNavigationScope innerScope = FocusNavigationScope::ownedByShadowHost(*found);
-        Element* foundInInnerFocusScope = findFocusableElementRecursivelyBackward(innerScope, nullptr);
-        if (foundInInnerFocusScope)
-            return foundInInnerFocusScope;
-        if (isShadowHostDelegatesFocus(*found))
-            found = findFocusableElementRecursivelyBackward(scope, found);
-        return found;
+        // If delegatesFocus is true and tabindex is negative, skip the whole shadow tree under the
+        // shadow host.
+        if (isShadowHostDelegatesFocus(*found) && found->tabIndex() < 0)
+            return findFocusableElementRecursivelyBackward(scope, found);
+
+        // Now |found| is on a non focusable scope owner (either shadow host or <shadow>).
+        // Find focusable node in descendant scope. If not found, find next focusable node within the
+        // current scope.
+        if (isNonFocusableFocusScopeOwner(*found)) {
+            FocusNavigationScope innerScope = FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(*found);
+            Element* foundInInnerFocusScope = findFocusableElementRecursivelyBackward(innerScope, nullptr);
+            return foundInInnerFocusScope ? foundInInnerFocusScope : findFocusableElementRecursivelyBackward(scope, found);
+        }
+        if (!isShadowHostDelegatesFocus(*found))
+            break;
+        found = findFocusableElementInternal(WebFocusTypeBackward, scope, found);
     }
-
-    // If delegatesFocus is true and tabindex is negative, skip the whole shadow tree under the
-    // shadow host.
-    if (isShadowHostDelegatesFocus(*found) && found->tabIndex() < 0)
-        return findFocusableElementRecursivelyBackward(scope, found);
-
-    // Now |found| is on a non focusable scope owner (either shadow host or <shadow>).
-    // Find focusable node in descendant scope. If not found, find next focusable node within the
-    // current scope.
-    if (isNonFocusableFocusScopeOwner(*found)) {
-        FocusNavigationScope innerScope = FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(*found);
-        Element* foundInInnerFocusScope = findFocusableElementRecursivelyBackward(innerScope, nullptr);
-        return foundInInnerFocusScope ? foundInInnerFocusScope : findFocusableElementRecursivelyBackward(scope, found);
-    }
-
-    return !isShadowHostDelegatesFocus(*found) ? found : findFocusableElementRecursivelyBackward(scope, found);
+    return found;

[hayato, 2015/06/25 07:31:02]

return nullptr;

[kochi, 2015/06/25 07:56:32]

No, if line 427 or 443 breaks, |found| is non-null.

[hayato, 2015/06/25 08:04:40]

Instead of `break`, they should `return found`.

[kochi, 2015/06/25 08:23:38]

Done.

 }
 
 Element* findFocusableElementRecursively(WebFocusType type, const FocusNavigationScope& scope, Node* start)
 {
     return (type == WebFocusTypeForward) ?
         findFocusableElementRecursivelyForward(scope, start) :
         findFocusableElementRecursivelyBackward(scope, start);
 }
 
 Element* findFocusableElementDescendingDownIntoFrameDocument(WebFocusType type, Element* element)
@@ skipping 582 matching lines @@
     return consumed;
 }
 
 DEFINE_TRACE(FocusController)
 {
     visitor->trace(m_page);
     visitor->trace(m_focusedFrame);
 }
 
 } // namespace blink