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

ui/views/focus/focus_traversal_unittest.cc

Index: ui/views/focus/focus_traversal_unittest.cc
diff --git a/ui/views/focus/focus_traversal_unittest.cc b/ui/views/focus/focus_traversal_unittest.cc
index cd24bd505a4632d9f61e19eb9267d97f892a0e5c..9ca7b4523804b738234c783262a3764d619882bf 100644
--- a/ui/views/focus/focus_traversal_unittest.cc
+++ b/ui/views/focus/focus_traversal_unittest.cc
@@ -259,13 +259,17 @@ void FocusTraversalTest::InitContentView() {
   //   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
@@ -770,4 +774,79 @@ TEST_F(FocusTraversalTest, PaneTraversal) {
   }
 }
 
+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