Improve toolbar keyboard accessibility.

Design doc: https://docs.google.com/a/google.com/Doc?docid=0ATICCjR-gNReY2djdjkyNnNfNzl4ZnpiODQ2Mg&hl=en
BUG=40745
BUG=36728
BUG=36222
TEST=New test added to focus_manager_unittest.cc

Review URL: http://codereview.chromium.org/2737010

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@50234 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 652 insertions, 98 deletions

diff --git a/views/focus/accelerator_handler_gtk.cc b/views/focus/accelerator_handler_gtk.cc
index fb04e89..ee91906 100644
--- a/views/focus/accelerator_handler_gtk.cc
+++ b/views/focus/accelerator_handler_gtk.cc
@@ -55,6 +55,7 @@ bool AcceleratorHandler::Dispatch(GdkEvent* event) {
     gtk_main_do_event(event);
     return true;
   }
+
   DCHECK(ptr);
 
   // The top-level window or window widget is expected to always be associated
diff --git a/views/focus/focus_manager.cc b/views/focus/focus_manager.cc
index f637e09..9646bb8 100644
--- a/views/focus/focus_manager.cc
+++ b/views/focus/focus_manager.cc
@@ -15,6 +15,7 @@
 #include "base/keyboard_codes.h"
 #include "base/logging.h"
 #include "views/accelerator.h"
+#include "views/focus/focus_search.h"
 #include "views/focus/view_storage.h"
 #include "views/view.h"
 #include "views/widget/root_view.h"
@@ -122,7 +123,7 @@ bool FocusManager::OnKeyEvent(const KeyEvent& event) {
     } else if (index >= static_cast<int>(views.size())) {
       index = 0;
     }
-    views[index]->RequestFocus();
+    SetFocusedView(views[index]);
     return false;
   }
 
@@ -183,7 +184,7 @@ void FocusManager::AdvanceFocus(bool reverse) {
   // first element on the page.
   if (v) {
     v->AboutToRequestFocusFromTabTraversal(reverse);
-    v->RequestFocus();
+    SetFocusedView(v);
   }
 }
 
@@ -197,21 +198,36 @@ View* FocusManager::GetNextFocusableView(View* original_starting_view,
 
   View* starting_view = NULL;
   if (original_starting_view) {
-    if (!reverse) {
-      // If the starting view has a focus traversable, use it.
-      // This is the case with WidgetWins for example.
-      focus_traversable = original_starting_view->GetFocusTraversable();
+    // Search up the containment hierarchy to see if a view is acting as
+    // a pane, and wants to implement its own focus traversable to keep
+    // the focus trapped within that pane.
+    View* pane_search = original_starting_view;
+    while (pane_search) {
+      focus_traversable = pane_search->GetPaneFocusTraversable();
+      if (focus_traversable) {
+        starting_view = original_starting_view;
+        break;
+      }
+      pane_search = pane_search->GetParent();
+    }
 
-      // Otherwise default to the root view.
-      if (!focus_traversable) {
+    if (!focus_traversable) {
+      if (!reverse) {
+        // If the starting view has a focus traversable, use it.
+        // This is the case with WidgetWins for example.
+        focus_traversable = original_starting_view->GetFocusTraversable();
+
+        // Otherwise default to the root view.
+        if (!focus_traversable) {
+          focus_traversable = original_starting_view->GetRootView();
+          starting_view = original_starting_view;
+        }
+      } else {
+        // When you are going back, starting view's FocusTraversable
+        // should not be used.
         focus_traversable = original_starting_view->GetRootView();
         starting_view = original_starting_view;
       }
-    } else {
-      // When you are going back, starting view's FocusTraversable should not be
-      // used.
-      focus_traversable = original_starting_view->GetRootView();
-      starting_view = original_starting_view;
     }
   } else {
     focus_traversable = widget_->GetRootView();
@@ -231,8 +247,8 @@ View* FocusManager::GetNextFocusableView(View* original_starting_view,
       View* new_starting_view = NULL;
       // When we are going backward, the parent view might gain the next focus.
       bool check_starting_view = reverse;
-      v = parent_focus_traversable->FindNextFocusableView(
-          starting_view, reverse, FocusTraversable::UP,
+      v = parent_focus_traversable->GetFocusSearch()->FindNextFocusableView(
+          starting_view, reverse, FocusSearch::UP,
           check_starting_view, &new_focus_traversable, &new_starting_view);
 
       if (new_focus_traversable) {
@@ -368,12 +384,13 @@ View* FocusManager::FindFocusableView(FocusTraversable* focus_traversable,
                                       bool reverse) {
   FocusTraversable* new_focus_traversable = NULL;
   View* new_starting_view = NULL;
-  View* v = focus_traversable->FindNextFocusableView(starting_view,
-                                                     reverse,
-                                                     FocusTraversable::DOWN,
-                                                     false,
-                                                     &new_focus_traversable,
-                                                     &new_starting_view);
+  View* v = focus_traversable->GetFocusSearch()->FindNextFocusableView(
+      starting_view,
+      reverse,
+      FocusSearch::DOWN,
+      false,
+      &new_focus_traversable,
+      &new_starting_view);
 
   // Let's go down the FocusTraversable tree as much as we can.
   while (new_focus_traversable) {
@@ -382,12 +399,13 @@ View* FocusManager::FindFocusableView(FocusTraversable* focus_traversable,
     starting_view = new_starting_view;
     new_focus_traversable = NULL;
     starting_view = NULL;
-    v = focus_traversable->FindNextFocusableView(starting_view,
-                                                 reverse,
-                                                 FocusTraversable::DOWN,
-                                                 false,
-                                                 &new_focus_traversable,
-                                                 &new_starting_view);
+    v = focus_traversable->GetFocusSearch()->FindNextFocusableView(
+        starting_view,
+        reverse,
+        FocusSearch::DOWN,
+        false,
+        &new_focus_traversable,
+        &new_starting_view);
   }
   return v;
 }
diff --git a/views/focus/focus_manager.h b/views/focus/focus_manager.h
index 565184c..d789d12 100644
--- a/views/focus/focus_manager.h
+++ b/views/focus/focus_manager.h
@@ -48,7 +48,7 @@
 // If you are embedding a native view containing a nested RootView (for example
 // by adding a NativeControl that contains a WidgetWin as its native
 // component), then you need to:
-// - override the View::GetFocusTraversable() method in your outter component.
+// - override the View::GetFocusTraversable() method in your outer component.
 //   It should return the RootView of the inner component. This is used when
 //   the focus traversal traverse down the focus hierarchy to enter the nested
 //   RootView. In the example mentioned above, the NativeControl overrides
@@ -66,11 +66,12 @@
 //   hwnd_view_container_->GetRootView()->SetFocusTraversableParent(
 //      native_control);
 //
-// Note that FocusTraversable do not have to be RootViews: TabContents is
-// FocusTraversable.
+// Note that FocusTraversable do not have to be RootViews: AccessibleToolbarView
+// is FocusTraversable.
 
 namespace views {
 
+class FocusSearch;
 class RootView;
 class View;
 class Widget;
@@ -79,42 +80,9 @@ class Widget;
 // focus traversal events (due to Tab/Shift-Tab key events).
 class FocusTraversable {
  public:
-  // The direction in which the focus traversal is going.
-  // TODO (jcampan): add support for lateral (left, right) focus traversal. The
-  // goal is to switch to focusable views on the same level when using the arrow
-  // keys (ala Windows: in a dialog box, arrow keys typically move between the
-  // dialog OK, Cancel buttons).
-  enum Direction {
-    UP = 0,
-    DOWN
-  };
-
-  // Should find the next view that should be focused and return it. If a
-  // FocusTraversable is found while searching for the focusable view, NULL
-  // should be returned, focus_traversable should be set to the FocusTraversable
-  // and focus_traversable_view should be set to the view associated with the
-  // FocusTraversable.
-  // This call should return NULL if the end of the focus loop is reached.
-  // - |starting_view| is the view that should be used as the starting point
-  //   when looking for the previous/next view. It may be NULL (in which case
-  //   the first/last view should be used depending if normal/reverse).
-  // - |reverse| whether we should find the next (reverse is false) or the
-  //   previous (reverse is true) view.
-  // - |direction| specifies whether we are traversing down (meaning we should
-  //   look into child views) or traversing up (don't look at child views).
-  // - |check_starting_view| is true if starting_view may obtain the next focus.
-  // - |focus_traversable| is set to the focus traversable that should be
-  //   traversed if one is found (in which case the call returns NULL).
-  // - |focus_traversable_view| is set to the view associated with the
-  //   FocusTraversable set in the previous parameter (it is used as the
-  //   starting view when looking for the next focusable view).
-
-  virtual View* FindNextFocusableView(View* starting_view,
-                                      bool reverse,
-                                      Direction direction,
-                                      bool check_starting_view,
-                                      FocusTraversable** focus_traversable,
-                                      View** focus_traversable_view) = 0;
+  // Return a FocusSearch object that implements the algorithm to find
+  // the next or previous focusable view.
+  virtual FocusSearch* GetFocusSearch() = 0;
 
   // Should return the parent FocusTraversable.
   // The top RootView which is the top FocusTraversable returns NULL.
diff --git a/views/focus/focus_manager_unittest.cc b/views/focus/focus_manager_unittest.cc
index 80cbd5f4..ae585a7 100644
--- a/views/focus/focus_manager_unittest.cc
+++ b/views/focus/focus_manager_unittest.cc
@@ -2,10 +2,6 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-// Disabled right now as this won't work on BuildBots right now as this test
-// require the box it runs on to be unlocked (and no screen-savers).
-// The test actually simulates mouse and key events, so if the screen is locked,
-// the events don't go to the Chrome window.
 #include "testing/gtest/include/gtest/gtest.h"
 
 #include "app/combobox_model.h"
@@ -331,6 +327,41 @@ class DummyComboboxModel : public ComboboxModel {
   }
 };
 
+// A View that can act as a pane.
+class PaneView : public View, public FocusTraversable {
+ public:
+  PaneView() : focus_search_(NULL) {}
+
+  // If this method is called, this view will use GetPaneFocusTraversable to
+  // have this provided FocusSearch used instead of the default one, allowing
+  // you to trap focus within the pane.
+  void EnablePaneFocus(FocusSearch* focus_search) {
+    focus_search_ = focus_search;
+  }
+
+  // Overridden from views::View:
+  virtual FocusTraversable* GetPaneFocusTraversable() {
+    if (focus_search_)
+      return this;
+    else
+      return NULL;
+  }
+
+  // Overridden from views::FocusTraversable:
+  virtual views::FocusSearch* GetFocusSearch() {
+    return focus_search_;
+  }
+  virtual FocusTraversable* GetFocusTraversableParent() {
+    return NULL;
+  }
+  virtual View* GetFocusTraversableParentView() {
+    return NULL;
+  }
+
+ private:
+  FocusSearch* focus_search_;
+};
+
 class FocusTraversalTest : public FocusManagerTest {
  public:
   ~FocusTraversalTest();
@@ -357,10 +388,12 @@ class FocusTraversalTest : public FocusManagerTest {
     return NULL;
   }
 
- private:
+ protected:
   TabbedPane* style_tab_;
   BorderView* search_border_view_;
   DummyComboboxModel combobox_model_;
+  PaneView* left_container_;
+  PaneView* right_container_;
 
   DISALLOW_COPY_AND_ASSIGN(FocusTraversalTest);
 };
@@ -378,6 +411,64 @@ FocusTraversalTest::~FocusTraversalTest() {
 }
 
 void FocusTraversalTest::InitContentView() {
+  // Create a complicated view hierarchy with lots of control types for
+  // use by all of the focus traversal tests.
+  //
+  // Class name, ID, and asterisk next to focusable views:
+  //
+  // View
+  //   Checkbox            * kTopCheckBoxID
+  //   PaneView              kLeftContainerID
+  //     Label               kAppleLabelID
+  //     Textfield         * kAppleTextfieldID
+  //     Label               kOrangeLabelID
+  //     Textfield         * kOrangeTextfieldID
+  //     Label               kBananaLabelID
+  //     Textfield         * kBananaTextfieldID
+  //     Label               kKiwiLabelID
+  //     Textfield         * kKiwiTextfieldID
+  //     NativeButton      * kFruitButtonID
+  //     Checkbox          * kFruitCheckBoxID
+  //     Combobox          * kComboboxID
+  //   PaneView              kRightContainerID
+  //     RadioButton       * kAsparagusButtonID
+  //     RadioButton       * kBroccoliButtonID
+  //     RadioButton       * kCauliflowerButtonID
+  //     View                kInnerContainerID
+  //       ScrollView        kScrollViewID
+  //         View
+  //           Link        * kRosettaLinkID
+  //           Link        * kStupeurEtTremblementLinkID
+  //           Link        * kDinerGameLinkID
+  //           Link        * kRidiculeLinkID
+  //           Link        * kClosetLinkID
+  //           Link        * kVisitingLinkID
+  //           Link        * kAmelieLinkID
+  //           Link        * kJoyeuxNoelLinkID
+  //           Link        * kCampingLinkID
+  //           Link        * kBriceDeNiceLinkID
+  //           Link        * kTaxiLinkID
+  //           Link        * kAsterixLinkID
+  //   NativeButton        * kOKButtonID
+  //   NativeButton        * kCancelButtonID
+  //   NativeButton        * kHelpButtonID
+  //   TabbedPane          * kStyleContainerID
+  //     View
+  //       Checkbox        * kBoldCheckBoxID
+  //       Checkbox        * kItalicCheckBoxID
+  //       Checkbox        * kUnderlinedCheckBoxID
+  //       Link            * kStyleHelpLinkID
+  //       Textfield       * kStyleTextEditID
+  //     Other
+  //   BorderView            kSearchContainerID
+  //     View
+  //       Textfield       * kSearchTextfieldID
+  //       NativeButton    * kSearchButtonID
+  //       Link            * kHelpLinkID
+  //   View                * kThumbnailContainerID
+  //     NativeButton      * kThumbnailStarID
+  //     NativeButton      * kThumbnailSuperStarID
+
   content_view_->set_background(
       Background::CreateSolidBackground(SK_ColorWHITE));
 
@@ -387,13 +478,13 @@ void FocusTraversalTest::InitContentView() {
   cb->SetBounds(10, 10, 200, 20);
   cb->SetID(kTopCheckBoxID);
 
-  View* left_container = new View();
-  left_container->set_border(Border::CreateSolidBorder(1, SK_ColorBLACK));
-  left_container->set_background(
+  left_container_ = new PaneView();
+  left_container_->set_border(Border::CreateSolidBorder(1, SK_ColorBLACK));
+  left_container_->set_background(
       Background::CreateSolidBackground(240, 240, 240));
-  left_container->SetID(kLeftContainerID);
-  content_view_->AddChildView(left_container);
-  left_container->SetBounds(10, 35, 250, 200);
+  left_container_->SetID(kLeftContainerID);
+  content_view_->AddChildView(left_container_);
+  left_container_->SetBounds(10, 35, 250, 200);
 
   int label_x = 5;
   int label_width = 50;
@@ -404,12 +495,12 @@ void FocusTraversalTest::InitContentView() {
 
   Label* label = new Label(L"Apple:");
   label->SetID(kAppleLabelID);
-  left_container->AddChildView(label);
+  left_container_->AddChildView(label);
   label->SetBounds(label_x, y, label_width, label_height);
 
   Textfield* text_field = new Textfield();
   text_field->SetID(kAppleTextfieldID);
-  left_container->AddChildView(text_field);
+  left_container_->AddChildView(text_field);
   text_field->SetBounds(label_x + label_width + 5, y,
                         text_field_width, label_height);
 
@@ -417,12 +508,12 @@ void FocusTraversalTest::InitContentView() {
 
   label = new Label(L"Orange:");
   label->SetID(kOrangeLabelID);
-  left_container->AddChildView(label);
+  left_container_->AddChildView(label);
   label->SetBounds(label_x, y, label_width, label_height);
 
   text_field = new Textfield();
   text_field->SetID(kOrangeTextfieldID);
-  left_container->AddChildView(text_field);
+  left_container_->AddChildView(text_field);
   text_field->SetBounds(label_x + label_width + 5, y,
                         text_field_width, label_height);
 
@@ -430,12 +521,12 @@ void FocusTraversalTest::InitContentView() {
 
   label = new Label(L"Banana:");
   label->SetID(kBananaLabelID);
-  left_container->AddChildView(label);
+  left_container_->AddChildView(label);
   label->SetBounds(label_x, y, label_width, label_height);
 
   text_field = new Textfield();
   text_field->SetID(kBananaTextfieldID);
-  left_container->AddChildView(text_field);
+  left_container_->AddChildView(text_field);
   text_field->SetBounds(label_x + label_width + 5, y,
                         text_field_width, label_height);
 
@@ -443,12 +534,12 @@ void FocusTraversalTest::InitContentView() {
 
   label = new Label(L"Kiwi:");
   label->SetID(kKiwiLabelID);
-  left_container->AddChildView(label);
+  left_container_->AddChildView(label);
   label->SetBounds(label_x, y, label_width, label_height);
 
   text_field = new Textfield();
   text_field->SetID(kKiwiTextfieldID);
-  left_container->AddChildView(text_field);
+  left_container_->AddChildView(text_field);
   text_field->SetBounds(label_x + label_width + 5, y,
                         text_field_width, label_height);
 
@@ -457,47 +548,47 @@ void FocusTraversalTest::InitContentView() {
   NativeButton* button = new NativeButton(NULL, L"Click me");
   button->SetBounds(label_x, y + 10, 80, 30);
   button->SetID(kFruitButtonID);
-  left_container->AddChildView(button);
+  left_container_->AddChildView(button);
   y += 40;
 
   cb =  new Checkbox(L"This is another check box");
   cb->SetBounds(label_x + label_width + 5, y, 180, 20);
   cb->SetID(kFruitCheckBoxID);
-  left_container->AddChildView(cb);
+  left_container_->AddChildView(cb);
   y += 20;
 
   Combobox* combobox =  new Combobox(&combobox_model_);
   combobox->SetBounds(label_x + label_width + 5, y, 150, 30);
   combobox->SetID(kComboboxID);
-  left_container->AddChildView(combobox);
+  left_container_->AddChildView(combobox);
 
-  View* right_container = new View();
-  right_container->set_border(Border::CreateSolidBorder(1, SK_ColorBLACK));
-  right_container->set_background(
+  right_container_ = new PaneView();
+  right_container_->set_border(Border::CreateSolidBorder(1, SK_ColorBLACK));
+  right_container_->set_background(
       Background::CreateSolidBackground(240, 240, 240));
-  right_container->SetID(kRightContainerID);
-  content_view_->AddChildView(right_container);
-  right_container->SetBounds(270, 35, 300, 200);
+  right_container_->SetID(kRightContainerID);
+  content_view_->AddChildView(right_container_);
+  right_container_->SetBounds(270, 35, 300, 200);
 
   y = 10;
   int radio_button_height = 18;
   int gap_between_radio_buttons = 10;
   RadioButton* radio_button = new RadioButton(L"Asparagus", 1);
   radio_button->SetID(kAsparagusButtonID);
-  right_container->AddChildView(radio_button);
+  right_container_->AddChildView(radio_button);
   radio_button->SetBounds(5, y, 70, radio_button_height);
   radio_button->SetGroup(1);
   y += radio_button_height + gap_between_radio_buttons;
   radio_button = new RadioButton(L"Broccoli", 1);
   radio_button->SetID(kBroccoliButtonID);
-  right_container->AddChildView(radio_button);
+  right_container_->AddChildView(radio_button);
   radio_button->SetBounds(5, y, 70, radio_button_height);
   radio_button->SetGroup(1);
   RadioButton* radio_button_to_check = radio_button;
   y += radio_button_height + gap_between_radio_buttons;
   radio_button = new RadioButton(L"Cauliflower", 1);
   radio_button->SetID(kCauliflowerButtonID);
-  right_container->AddChildView(radio_button);
+  right_container_->AddChildView(radio_button);
   radio_button->SetBounds(5, y, 70, radio_button_height);
   radio_button->SetGroup(1);
   y += radio_button_height + gap_between_radio_buttons;
@@ -507,7 +598,7 @@ void FocusTraversalTest::InitContentView() {
   inner_container->set_background(
       Background::CreateSolidBackground(230, 230, 230));
   inner_container->SetID(kInnerContainerID);
-  right_container->AddChildView(inner_container);
+  right_container_->AddChildView(inner_container);
   inner_container->SetBounds(100, 10, 150, 180);
 
   ScrollView* scroll_view = new ScrollView();
@@ -1057,6 +1148,84 @@ TEST_F(FocusTraversalTest, TraversalWithNonEnabledViews) {
   }
 }
 
+TEST_F(FocusTraversalTest, PaneTraversal) {
+  // Tests trapping the traversal within a pane - useful for full
+  // keyboard accessibility for toolbars.
+
+  // First test the left container.
+  const int kLeftTraversalIDs[] = {
+    kAppleTextfieldID,
+    kOrangeTextfieldID, kBananaTextfieldID, kKiwiTextfieldID,
+    kFruitButtonID, kFruitCheckBoxID, kComboboxID };
+
+  FocusSearch focus_search_left(left_container_, true, false);
+  left_container_->EnablePaneFocus(&focus_search_left);
+  FindViewByID(kComboboxID)->RequestFocus();
+
+  // Traverse the focus hierarchy within the pane several times.
+  for (int i = 0; i < 3; ++i) {
+    for (size_t j = 0; j < arraysize(kLeftTraversalIDs); j++) {
+      GetFocusManager()->AdvanceFocus(false);
+      View* focused_view = GetFocusManager()->GetFocusedView();
+      EXPECT_TRUE(focused_view != NULL);
+      if (focused_view)
+        EXPECT_EQ(kLeftTraversalIDs[j], focused_view->GetID());
+    }
+  }
+
+  // Traverse in reverse order.
+  FindViewByID(kAppleTextfieldID)->RequestFocus();
+  for (int i = 0; i < 3; ++i) {
+    for (int j = arraysize(kLeftTraversalIDs) - 1; j >= 0; --j) {
+      GetFocusManager()->AdvanceFocus(true);
+      View* focused_view = GetFocusManager()->GetFocusedView();
+      EXPECT_TRUE(focused_view != NULL);
+      if (focused_view)
+        EXPECT_EQ(kLeftTraversalIDs[j], focused_view->GetID());
+    }
+  }
+
+  // Now test the right container, but this time with accessibility mode.
+  // Make some links not focusable, but mark one of them as
+  // "accessibility focusable", so it should show up in the traversal.
+  const int kRightTraversalIDs[] = {
+    kBroccoliButtonID, kDinerGameLinkID, kRidiculeLinkID,
+    kClosetLinkID, kVisitingLinkID, kAmelieLinkID, kJoyeuxNoelLinkID,
+    kCampingLinkID, kBriceDeNiceLinkID, kTaxiLinkID, kAsterixLinkID };
+
+  FocusSearch focus_search_right(right_container_, true, true);
+  right_container_->EnablePaneFocus(&focus_search_right);
+  FindViewByID(kRosettaLinkID)->SetFocusable(false);
+  FindViewByID(kStupeurEtTremblementLinkID)->SetFocusable(false);
+  FindViewByID(kDinerGameLinkID)->set_accessibility_focusable(true);
+  FindViewByID(kDinerGameLinkID)->SetFocusable(false);
+  FindViewByID(kAsterixLinkID)->RequestFocus();
+
+  // Traverse the focus hierarchy within the pane several times.
+  for (int i = 0; i < 3; ++i) {
+    for (size_t j = 0; j < arraysize(kRightTraversalIDs); j++) {
+      GetFocusManager()->AdvanceFocus(false);
+      View* focused_view = GetFocusManager()->GetFocusedView();
+      EXPECT_TRUE(focused_view != NULL);
+      if (focused_view)
+        EXPECT_EQ(kRightTraversalIDs[j], focused_view->GetID());
+    }
+  }
+
+  // Traverse in reverse order.
+  FindViewByID(kBroccoliButtonID)->RequestFocus();
+  for (int i = 0; i < 3; ++i) {
+    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->GetID());
+    }
+  }
+
+}
+
 // Counts accelerator calls.
 class TestAcceleratorTarget : public AcceleratorTarget {
  public:
diff --git a/views/focus/focus_search.cc b/views/focus/focus_search.cc
new file mode 100644
index 0000000..eaeb8ac
--- /dev/null
+++ b/views/focus/focus_search.cc
@@ -0,0 +1,278 @@
+// Copyright (c) 2010 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 "base/logging.h"
+#include "views/focus/focus_manager.h"
+#include "views/focus/focus_search.h"
+#include "views/view.h"
+
+namespace views {
+
+FocusSearch::FocusSearch(View* root, bool cycle, bool accessibility_mode)
+    : root_(root),
+      cycle_(cycle),
+      accessibility_mode_(accessibility_mode) {
+}
+
+View* FocusSearch::FindNextFocusableView(View* starting_view,
+                                         bool reverse,
+                                         Direction direction,
+                                         bool check_starting_view,
+                                         FocusTraversable** focus_traversable,
+                                         View** focus_traversable_view) {
+  *focus_traversable = NULL;
+  *focus_traversable_view = NULL;
+
+  if (root_->GetChildViewCount() == 0) {
+    NOTREACHED();
+    // Nothing to focus on here.
+    return NULL;
+  }
+
+  View* initial_starting_view = starting_view;
+  int starting_view_group = -1;
+  if (starting_view)
+    starting_view_group = starting_view->GetGroup();
+
+  if (!starting_view) {
+    // Default to the first/last child
+    starting_view =
+        reverse ?
+        root_->GetChildViewAt(root_->GetChildViewCount() - 1) :
+        root_->GetChildViewAt(0);
+    // If there was no starting view, then the one we select is a potential
+    // focus candidate.
+    check_starting_view = true;
+  } else {
+    // The starting view should be a direct or indirect child of the root.
+    DCHECK(root_->IsParentOf(starting_view));
+  }
+
+  View* v = NULL;
+  if (!reverse) {
+    v = FindNextFocusableViewImpl(starting_view, check_starting_view,
+                                  true,
+                                  (direction == DOWN) ? true : false,
+                                  starting_view_group,
+                                  focus_traversable,
+                                  focus_traversable_view);
+  } else {
+    // If the starting view is focusable, we don't want to go down, as we are
+    // traversing the view hierarchy tree bottom-up.
+    bool can_go_down = (direction == DOWN) && !IsFocusable(starting_view);
+    v = FindPreviousFocusableViewImpl(starting_view, check_starting_view,
+                                      true,
+                                      can_go_down,
+                                      starting_view_group,
+                                      focus_traversable,
+                                      focus_traversable_view);
+  }
+
+  // Don't set the focus to something outside of this view hierarchy.
+  if (v && v != root_ && !root_->IsParentOf(v))
+    v = NULL;
+
+  // If |cycle_| is true, prefer to keep cycling rather than returning NULL.
+  if (cycle_ && !v && initial_starting_view) {
+    v = FindNextFocusableView(NULL, reverse, direction, check_starting_view,
+                              focus_traversable, focus_traversable_view);
+    DCHECK(IsFocusable(v));
+    return v;
+  }
+
+  // Doing some sanity checks.
+  if (v) {
+    DCHECK(IsFocusable(v));
+    return v;
+  }
+  if (*focus_traversable) {
+    DCHECK(*focus_traversable_view);
+    return NULL;
+  }
+  // Nothing found.
+  return NULL;
+}
+
+bool FocusSearch::IsViewFocusableCandidate(View* v, int skip_group_id) {
+  return IsFocusable(v) &&
+      (v->IsGroupFocusTraversable() || skip_group_id == -1 ||
+       v->GetGroup() != skip_group_id);
+}
+
+bool FocusSearch::IsFocusable(View* v) {
+  if (accessibility_mode_)
+    return v && v->IsAccessibilityFocusable();
+  else
+    return v && v->IsFocusable();
+}
+
+View* FocusSearch::FindSelectedViewForGroup(View* view) {
+  if (view->IsGroupFocusTraversable() ||
+      view->GetGroup() == -1)  // No group for that view.
+    return view;
+
+  View* selected_view = view->GetSelectedViewForGroup(view->GetGroup());
+  if (selected_view)
+    return selected_view;
+
+  // No view selected for that group, default to the specified view.
+  return view;
+}
+
+View* FocusSearch::GetParent(View* v) {
+  if (root_->IsParentOf(v)) {
+    return v->GetParent();
+  } else {
+    return NULL;
+  }
+}
+
+// Strategy for finding the next focusable view:
+// - keep going down the first child, stop when you find a focusable view or
+//   a focus traversable view (in that case return it) or when you reach a view
+//   with no children.
+// - go to the right sibling and start the search from there (by invoking
+//   FindNextFocusableViewImpl on that view).
+// - if the view has no right sibling, go up the parents until you find a parent
+//   with a right sibling and start the search from there.
+View* FocusSearch::FindNextFocusableViewImpl(
+    View* starting_view,
+    bool check_starting_view,
+    bool can_go_up,
+    bool can_go_down,
+    int skip_group_id,
+    FocusTraversable** focus_traversable,
+    View** focus_traversable_view) {
+  if (check_starting_view) {
+    if (IsViewFocusableCandidate(starting_view, skip_group_id)) {
+      View* v = FindSelectedViewForGroup(starting_view);
+      // The selected view might not be focusable (if it is disabled for
+      // example).
+      if (IsFocusable(v))
+        return v;
+    }
+
+    *focus_traversable = starting_view->GetFocusTraversable();
+    if (*focus_traversable) {
+      *focus_traversable_view = starting_view;
+      return NULL;
+    }
+  }
+
+  // First let's try the left child.
+  if (can_go_down) {
+    if (starting_view->GetChildViewCount() > 0) {
+      View* v = FindNextFocusableViewImpl(starting_view->GetChildViewAt(0),
+                                          true, false, true, skip_group_id,
+                                          focus_traversable,
+                                          focus_traversable_view);
+      if (v || *focus_traversable)
+        return v;
+    }
+  }
+
+  // Then try the right sibling.
+  View* sibling = starting_view->GetNextFocusableView();
+  if (sibling) {
+    View* v = FindNextFocusableViewImpl(sibling,
+                                        true, false, true, skip_group_id,
+                                        focus_traversable,
+                                        focus_traversable_view);
+    if (v || *focus_traversable)
+      return v;
+  }
+
+  // Then go up to the parent sibling.
+  if (can_go_up) {
+    View* parent = GetParent(starting_view);
+    while (parent) {
+      sibling = parent->GetNextFocusableView();
+      if (sibling) {
+        return FindNextFocusableViewImpl(sibling,
+                                         true, true, true,
+                                         skip_group_id,
+                                         focus_traversable,
+                                         focus_traversable_view);
+      }
+      parent = GetParent(parent);
+    }
+  }
+
+  // We found nothing.
+  return NULL;
+}
+
+// Strategy for finding the previous focusable view:
+// - keep going down on the right until you reach a view with no children, if it
+//   it is a good candidate return it.
+// - start the search on the left sibling.
+// - if there are no left sibling, start the search on the parent (without going
+//   down).
+View* FocusSearch::FindPreviousFocusableViewImpl(
+    View* starting_view,
+    bool check_starting_view,
+    bool can_go_up,
+    bool can_go_down,
+    int skip_group_id,
+    FocusTraversable** focus_traversable,
+    View** focus_traversable_view) {
+  // Let's go down and right as much as we can.
+  if (can_go_down) {
+    // Before we go into the direct children, we have to check if this view has
+    // a FocusTraversable.
+    *focus_traversable = starting_view->GetFocusTraversable();
+    if (*focus_traversable) {
+      *focus_traversable_view = starting_view;
+      return NULL;
+    }
+
+    if (starting_view->GetChildViewCount() > 0) {
+      View* view =
+          starting_view->GetChildViewAt(starting_view->GetChildViewCount() - 1);
+      View* v = FindPreviousFocusableViewImpl(view, true, false, true,
+                                              skip_group_id,
+                                              focus_traversable,
+                                              focus_traversable_view);
+      if (v || *focus_traversable)
+        return v;
+    }
+  }
+
+  // Then look at this view. Here, we do not need to see if the view has
+  // a FocusTraversable, since we do not want to go down any more.
+  if (check_starting_view &&
+      IsViewFocusableCandidate(starting_view, skip_group_id)) {
+    View* v = FindSelectedViewForGroup(starting_view);
+    // The selected view might not be focusable (if it is disabled for
+    // example).
+    if (IsFocusable(v))
+      return v;
+  }
+
+  // Then try the left sibling.
+  View* sibling = starting_view->GetPreviousFocusableView();
+  if (sibling) {
+    return FindPreviousFocusableViewImpl(sibling,
+                                         true, true, true,
+                                         skip_group_id,
+                                         focus_traversable,
+                                         focus_traversable_view);
+  }
+
+  // Then go up the parent.
+  if (can_go_up) {
+    View* parent = GetParent(starting_view);
+    if (parent)
+      return FindPreviousFocusableViewImpl(parent,
+                                           true, true, false,
+                                           skip_group_id,
+                                           focus_traversable,
+                                           focus_traversable_view);
+  }
+
+  // We found nothing.
+  return NULL;
+}
+
+}  // namespace views
diff --git a/views/focus/focus_search.h b/views/focus/focus_search.h
new file mode 100644
index 0000000..f24864b
--- /dev/null
+++ b/views/focus/focus_search.h
@@ -0,0 +1,120 @@
+// Copyright (c) 2010 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.
+
+#ifndef VIEWS_WIDGET_FOCUS_SEARCH_H_
+#define VIEWS_WIDGET_FOCUS_SEARCH_H_
+
+#include "views/view.h"
+
+namespace views {
+
+class FocusTraversable;
+
+// FocusSearch is an object that implements the algorithm to find the
+// next view to focus.
+class FocusSearch {
+ public:
+  // The direction in which the focus traversal is going.
+  // TODO (jcampan): add support for lateral (left, right) focus traversal. The
+  // goal is to switch to focusable views on the same level when using the arrow
+  // keys (ala Windows: in a dialog box, arrow keys typically move between the
+  // dialog OK, Cancel buttons).
+  enum Direction {
+    UP = 0,
+    DOWN
+  };
+
+  // Constructor.
+  // - |root| is the root of the view hierarchy to traverse. Focus will be
+  //   trapped inside.
+  // - |cycle| should be true if you want FindNextFocusableView to cycle back
+  //           to the first view within this root when the traversal reaches
+  //           the end. If this is true, then if you pass a valid starting
+  //           view to FindNextFocusableView you will always get a valid view
+  //           out, even if it's the same view.
+  // - |accessibility_mode| should be true if full keyboard accessibility is
+  //   needed and you  want to check IsAccessibilityFocusable(),
+  //   rather than IsFocusable().
+  FocusSearch(View* root, bool cycle, bool accessibility_mode);
+  virtual ~FocusSearch() {}
+
+  // Finds the next view that should be focused and returns it. If a
+  // FocusTraversable is found while searching for the focusable view,
+  // returns NULL and sets |focus_traversable| to the FocusTraversable
+  // and |focus_traversable_view| to the view associated with the
+  // FocusTraversable.
+  //
+  // Return NULL if the end of the focus loop is reached, unless this object
+  // was initialized with |cycle|=true, in which case it goes back to the
+  // beginning when it reaches the end of the traversal.
+  // - |starting_view| is the view that should be used as the starting point
+  //   when looking for the previous/next view. It may be NULL (in which case
+  //   the first/last view should be used depending if normal/reverse).
+  // - |reverse| whether we should find the next (reverse is false) or the
+  //   previous (reverse is true) view.
+  // - |direction| specifies whether we are traversing down (meaning we should
+  //   look into child views) or traversing up (don't look at child views).
+  // - |check_starting_view| is true if starting_view may obtain the next focus.
+  // - |focus_traversable| is set to the focus traversable that should be
+  //   traversed if one is found (in which case the call returns NULL).
+  // - |focus_traversable_view| is set to the view associated with the
+  //   FocusTraversable set in the previous parameter (it is used as the
+  //   starting view when looking for the next focusable view).
+  virtual View* FindNextFocusableView(View* starting_view,
+                                      bool reverse,
+                                      Direction direction,
+                                      bool check_starting_view,
+                                      FocusTraversable** focus_traversable,
+                                      View** focus_traversable_view);
+
+ private:
+  // Convenience method that returns true if a view is focusable and does not
+  // belong to the specified group.
+  bool IsViewFocusableCandidate(View* v, int skip_group_id);
+
+  // Convenience method; returns true if a view is not NULL and is focusable
+  // (checking IsAccessibilityFocusable() if accessibility_mode_ is true).
+  bool IsFocusable(View* v);
+
+  // Returns the view selected for the group of the selected view. If the view
+  // does not belong to a group or if no view is selected in the group, the
+  // specified view is returned.
+  View* FindSelectedViewForGroup(View* view);
+
+  // Get the parent, but stay within the root. Returns NULL if asked for
+  // the parent of root_.
+  View* GetParent(View* view);
+
+  // Returns the next focusable view or view containing a FocusTraversable
+  // (NULL if none was found), starting at the starting_view.
+  // |check_starting_view|, |can_go_up| and |can_go_down| controls the
+  // traversal of the views hierarchy. |skip_group_id| specifies a group_id,
+  // -1 means no group. All views from a group are traversed in one pass.
+  View* FindNextFocusableViewImpl(View* starting_view,
+                                  bool check_starting_view,
+                                  bool can_go_up,
+                                  bool can_go_down,
+                                  int skip_group_id,
+                                  FocusTraversable** focus_traversable,
+                                  View** focus_traversable_view);
+
+  // Same as FindNextFocusableViewImpl but returns the previous focusable view.
+  View* FindPreviousFocusableViewImpl(View* starting_view,
+                                      bool check_starting_view,
+                                      bool can_go_up,
+                                      bool can_go_down,
+                                      int skip_group_id,
+                                      FocusTraversable** focus_traversable,
+                                      View** focus_traversable_view);
+
+  View* root_;
+  bool cycle_;
+  bool accessibility_mode_;
+
+  DISALLOW_COPY_AND_ASSIGN(FocusSearch);
+};
+
+}  // namespace views
+
+#endif  // VIEWS_WIDGET_FOCUS_SEARCH_H_