Views: Fixed exponential behaviour on reverse focus search (Shift+Tab).

ui/views/focus/focus_traversal_unittest.cc

 // Copyright (c) 2012 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 "ui/views/focus/focus_manager.h"
 
 #include "base/run_loop.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/utf_string_conversions.h"
 #include "ui/base/models/combobox_model.h"
@@ skipping 241 matching lines @@
   //           Link        * kAmelieLinkID
   //           Link        * kJoyeuxNoelLinkID
   //           Link        * kCampingLinkID
   //           Link        * kBriceDeNiceLinkID
   //           Link        * kTaxiLinkID
   //           Link        * kAsterixLinkID
   //   NativeButton        * kOKButtonID
   //   NativeButton        * kCancelButtonID
   //   NativeButton        * kHelpButtonID
   //   TabbedPane          * kStyleContainerID
+  //     TabStrip
+  //       Tab ("Style")
+  //       Tab ("Other")
   //     View
-  //       Checkbox        * kBoldCheckBoxID
-  //       Checkbox        * kItalicCheckBoxID
-  //       Checkbox        * kUnderlinedCheckBoxID
-  //       Link            * kStyleHelpLinkID
-  //       Textfield       * kStyleTextEditID
-  //     Other
+  //       View
+  //         Checkbox      * kBoldCheckBoxID
+  //         Checkbox      * kItalicCheckBoxID
+  //         Checkbox      * kUnderlinedCheckBoxID
+  //         Link          * kStyleHelpLinkID
+  //         Textfield     * kStyleTextEditID
+  //       View
   //   BorderView            kSearchContainerID
   //     View
   //       Textfield       * kSearchTextfieldID
   //       NativeButton    * kSearchButtonID
   //       Link            * kHelpLinkID
   //   View                * kThumbnailContainerID
   //     NativeButton      * kThumbnailStarID
   //     NativeButton      * kThumbnailSuperStarID
 
   GetContentsView()->set_background(
@@ skipping 484 matching lines @@
     for (int j = arraysize(kRightTraversalIDs) - 1; j >= 0; --j) {
       GetFocusManager()->AdvanceFocus(true);
       View* focused_view = GetFocusManager()->GetFocusedView();
       EXPECT_TRUE(focused_view != NULL);
       if (focused_view)
         EXPECT_EQ(kRightTraversalIDs[j], focused_view->id());
     }
   }
 }
 
+class FocusTraversalNonFocusableTest : public FocusManagerTest {
+ public:
+  ~FocusTraversalNonFocusableTest() override {}
+
+  void InitContentView() override;
+
+ protected:
+  FocusTraversalNonFocusableTest() {}
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(FocusTraversalNonFocusableTest);
+};
+
+void FocusTraversalNonFocusableTest::InitContentView() {
+  // Create a complex nested view hierarchy with no focusable views. This is a
+  // regression test for http://crbug.com/453699. There was previously a bug
+  // where advancing focus backwards through this tree resulted in an
+  // exponential number of nodes being searched. (Each time it traverses one of
+  // the x1-x3-x2 triangles, it will traverse the left sibling of x1, (x+1)0,
+  // twice, which means it will visit O(2^n) nodes.)
+  //
+  //              0
+  //            /   \
+  //          /       \
+  //         10        1
+  //        /  \      / \
+  //      /      \   /   \
+  //     20      11  2   3
+  //    / \      / \
+  //   /   \    /   \
+  //  ...  21  12   13
+  //       / \
+  //      /   \
+  //     22   23
+
+  View* v = GetContentsView();
+  // Create 30 groups of 4 nodes. |v| is the top of each group.
+  for (int i = 0; i < 300; i += 10) {
+    // |v|'s left child is the top of the next group. If |v| is 20, this is 30.
+    View* v10 = new View;
+    v10->set_id(i + 10);
+    v->AddChildView(v10);
+
+    // |v|'s right child. If |v| is 20, this is 21.
+    View* v1 = new View;
+    v1->set_id(i + 1);
+    v->AddChildView(v1);
+
+    // |v|'s right child has two children. If |v| is 20, these are 22 and 23.
+    View* v2 = new View;
+    v2->set_id(i + 2);
+    View* v3 = new View;
+    v3->set_id(i + 3);
+    v1->AddChildView(v2);
+    v1->AddChildView(v3);
+
+    v = v10;
+  }
+}
+
+// See explanation in InitContentView.
+// NOTE: The failure mode of this test (if http://crbug.com/453699 were to
+// regress) is a timeout, due to exponential run time.
+TEST_F(FocusTraversalNonFocusableTest, PathologicalSiblingTraversal) {
+  // Advance forwards from the root node.
+  GetFocusManager()->ClearFocus();
+  GetFocusManager()->AdvanceFocus(false);
+  EXPECT_FALSE(GetFocusManager()->GetFocusedView());
+
+  // Advance backwards from the root node.
+  GetFocusManager()->ClearFocus();
+  GetFocusManager()->AdvanceFocus(true);
+  EXPECT_FALSE(GetFocusManager()->GetFocusedView());
+}
+
 }  // namespace views