// 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 <stddef.h>

#include "base/macros.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"
#include "ui/views/background.h"
#include "ui/views/border.h"
#include "ui/views/controls/button/checkbox.h"
#include "ui/views/controls/button/label_button.h"
#include "ui/views/controls/button/radio_button.h"
#include "ui/views/controls/combobox/combobox.h"
#include "ui/views/controls/label.h"
#include "ui/views/controls/link.h"
#include "ui/views/controls/native/native_view_host.h"
#include "ui/views/controls/scroll_view.h"
#include "ui/views/controls/tabbed_pane/tabbed_pane.h"
#include "ui/views/controls/textfield/textfield.h"
#include "ui/views/test/focus_manager_test.h"
#include "ui/views/widget/root_view.h"
#include "ui/views/widget/widget.h"

using base::ASCIIToUTF16;

namespace views {

namespace {

int count = 1;

const int kTopCheckBoxID = count++;  // 1
const int kLeftContainerID = count++;
const int kAppleLabelID = count++;
const int kAppleTextfieldID = count++;
const int kOrangeLabelID = count++;  // 5
const int kOrangeTextfieldID = count++;
const int kBananaLabelID = count++;
const int kBananaTextfieldID = count++;
const int kKiwiLabelID = count++;
const int kKiwiTextfieldID = count++;  // 10
const int kFruitButtonID = count++;
const int kFruitCheckBoxID = count++;
const int kComboboxID = count++;

const int kRightContainerID = count++;
const int kAsparagusButtonID = count++;  // 15
const int kBroccoliButtonID = count++;
const int kCauliflowerButtonID = count++;

const int kInnerContainerID = count++;
const int kScrollViewID = count++;
const int kRosettaLinkID = count++;  // 20
const int kStupeurEtTremblementLinkID = count++;
const int kDinerGameLinkID = count++;
const int kRidiculeLinkID = count++;
const int kClosetLinkID = count++;
const int kVisitingLinkID = count++;  // 25
const int kAmelieLinkID = count++;
const int kJoyeuxNoelLinkID = count++;
const int kCampingLinkID = count++;
const int kBriceDeNiceLinkID = count++;
const int kTaxiLinkID = count++;  // 30
const int kAsterixLinkID = count++;

const int kOKButtonID = count++;
const int kCancelButtonID = count++;
const int kHelpButtonID = count++;

const int kStyleContainerID = count++;  // 35
const int kBoldCheckBoxID = count++;
const int kItalicCheckBoxID = count++;
const int kUnderlinedCheckBoxID = count++;
const int kStyleHelpLinkID = count++;
const int kStyleTextEditID = count++;  // 40

const int kSearchContainerID = count++;
const int kSearchTextfieldID = count++;
const int kSearchButtonID = count++;
const int kHelpLinkID = count++;

const int kThumbnailContainerID = count++;  // 45
const int kThumbnailStarID = count++;
const int kThumbnailSuperStarID = count++;

class DummyComboboxModel : public ui::ComboboxModel {
 public:
  // Overridden from ui::ComboboxModel:
  int GetItemCount() const override { return 10; }
  base::string16 GetItemAt(int index) override {
    return ASCIIToUTF16("Item ") + base::IntToString16(index);
  }
};

// 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 View:
  FocusTraversable* GetPaneFocusTraversable() override {
    if (focus_search_)
      return this;
    else
      return NULL;
  }

  // Overridden from FocusTraversable:
  views::FocusSearch* GetFocusSearch() override { return focus_search_; }
  FocusTraversable* GetFocusTraversableParent() override { return NULL; }
  View* GetFocusTraversableParentView() override { return NULL; }

 private:
  FocusSearch* focus_search_;
};

// BorderView is a view containing a native window with its own view hierarchy.
// It is interesting to test focus traversal from a view hierarchy to an inner
// view hierarchy.
class BorderView : public NativeViewHost {
 public:
  explicit BorderView(View* child) : child_(child), widget_(NULL) {
    DCHECK(child);
    SetFocusable(false);
  }

  ~BorderView() override {}

  virtual internal::RootView* GetContentsRootView() {
    return static_cast<internal::RootView*>(widget_->GetRootView());
  }

  FocusTraversable* GetFocusTraversable() override {
    return static_cast<internal::RootView*>(widget_->GetRootView());
  }

  void ViewHierarchyChanged(
      const ViewHierarchyChangedDetails& details) override {
    NativeViewHost::ViewHierarchyChanged(details);

    if (details.child == this && details.is_add) {
      if (!widget_) {
        widget_ = new Widget;
        Widget::InitParams params(Widget::InitParams::TYPE_CONTROL);
        params.parent = details.parent->GetWidget()->GetNativeView();
        widget_->Init(params);
        widget_->SetFocusTraversableParentView(this);
        widget_->SetContentsView(child_);
      }

      // We have been added to a view hierarchy, attach the native view.
      Attach(widget_->GetNativeView());
      // Also update the FocusTraversable parent so the focus traversal works.
      static_cast<internal::RootView*>(widget_->GetRootView())->
          SetFocusTraversableParent(GetWidget()->GetFocusTraversable());
    }
  }

 private:
  View* child_;
  Widget* widget_;

  DISALLOW_COPY_AND_ASSIGN(BorderView);
};

}  // namespace

class FocusTraversalTest : public FocusManagerTest {
 public:
  ~FocusTraversalTest() override;

  void InitContentView() override;

 protected:
  FocusTraversalTest();

  View* FindViewByID(int id) {
    View* view = GetContentsView()->GetViewByID(id);
    if (view)
      return view;
    if (style_tab_)
      view = style_tab_->GetSelectedTab()->GetViewByID(id);
    if (view)
      return view;
    view = search_border_view_->GetContentsRootView()->GetViewByID(id);
    if (view)
      return view;
    return NULL;
  }

 protected:
  TabbedPane* style_tab_;
  BorderView* search_border_view_;
  DummyComboboxModel combobox_model_;
  PaneView* left_container_;
  PaneView* right_container_;

  DISALLOW_COPY_AND_ASSIGN(FocusTraversalTest);
};

FocusTraversalTest::FocusTraversalTest()
    : style_tab_(NULL),
      search_border_view_(NULL) {
}

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
  //     TabStrip
  //       Tab ("Style")
  //       Tab ("Other")
  //     View
  //       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(
      Background::CreateSolidBackground(SK_ColorWHITE));

  Checkbox* cb = new Checkbox(ASCIIToUTF16("This is a checkbox"));
  GetContentsView()->AddChildView(cb);
  // In this fast paced world, who really has time for non hard-coded layout?
  cb->SetBounds(10, 10, 200, 20);
  cb->set_id(kTopCheckBoxID);

  left_container_ = new PaneView();
  left_container_->SetBorder(Border::CreateSolidBorder(1, SK_ColorBLACK));
  left_container_->set_background(
      Background::CreateSolidBackground(240, 240, 240));
  left_container_->set_id(kLeftContainerID);
  GetContentsView()->AddChildView(left_container_);
  left_container_->SetBounds(10, 35, 250, 200);

  int label_x = 5;
  int label_width = 50;
  int label_height = 15;
  int text_field_width = 150;
  int y = 10;
  int gap_between_labels = 10;

  Label* label = new Label(ASCIIToUTF16("Apple:"));
  label->set_id(kAppleLabelID);
  left_container_->AddChildView(label);
  label->SetBounds(label_x, y, label_width, label_height);

  Textfield* text_field = new Textfield();
  text_field->set_id(kAppleTextfieldID);
  left_container_->AddChildView(text_field);
  text_field->SetBounds(label_x + label_width + 5, y,
                        text_field_width, label_height);

  y += label_height + gap_between_labels;

  label = new Label(ASCIIToUTF16("Orange:"));
  label->set_id(kOrangeLabelID);
  left_container_->AddChildView(label);
  label->SetBounds(label_x, y, label_width, label_height);

  text_field = new Textfield();
  text_field->set_id(kOrangeTextfieldID);
  left_container_->AddChildView(text_field);
  text_field->SetBounds(label_x + label_width + 5, y,
                        text_field_width, label_height);

  y += label_height + gap_between_labels;

  label = new Label(ASCIIToUTF16("Banana:"));
  label->set_id(kBananaLabelID);
  left_container_->AddChildView(label);
  label->SetBounds(label_x, y, label_width, label_height);

  text_field = new Textfield();
  text_field->set_id(kBananaTextfieldID);
  left_container_->AddChildView(text_field);
  text_field->SetBounds(label_x + label_width + 5, y,
                        text_field_width, label_height);

  y += label_height + gap_between_labels;

  label = new Label(ASCIIToUTF16("Kiwi:"));
  label->set_id(kKiwiLabelID);
  left_container_->AddChildView(label);
  label->SetBounds(label_x, y, label_width, label_height);

  text_field = new Textfield();
  text_field->set_id(kKiwiTextfieldID);
  left_container_->AddChildView(text_field);
  text_field->SetBounds(label_x + label_width + 5, y,
                        text_field_width, label_height);

  y += label_height + gap_between_labels;

  LabelButton* button = new LabelButton(NULL, ASCIIToUTF16("Click me"));
  button->SetStyle(Button::STYLE_BUTTON);
  button->SetBounds(label_x, y + 10, 80, 30);
  button->set_id(kFruitButtonID);
  left_container_->AddChildView(button);
  y += 40;

  cb =  new Checkbox(ASCIIToUTF16("This is another check box"));
  cb->SetBounds(label_x + label_width + 5, y, 180, 20);
  cb->set_id(kFruitCheckBoxID);
  left_container_->AddChildView(cb);
  y += 20;

  Combobox* combobox =  new Combobox(&combobox_model_);
  combobox->SetBounds(label_x + label_width + 5, y, 150, 30);
  combobox->set_id(kComboboxID);
  left_container_->AddChildView(combobox);

  right_container_ = new PaneView();
  right_container_->SetBorder(Border::CreateSolidBorder(1, SK_ColorBLACK));
  right_container_->set_background(
      Background::CreateSolidBackground(240, 240, 240));
  right_container_->set_id(kRightContainerID);
  GetContentsView()->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(ASCIIToUTF16("Asparagus"), 1);
  radio_button->set_id(kAsparagusButtonID);
  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(ASCIIToUTF16("Broccoli"), 1);
  radio_button->set_id(kBroccoliButtonID);
  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(ASCIIToUTF16("Cauliflower"), 1);
  radio_button->set_id(kCauliflowerButtonID);
  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;

  View* inner_container = new View();
  inner_container->SetBorder(Border::CreateSolidBorder(1, SK_ColorBLACK));
  inner_container->set_background(
      Background::CreateSolidBackground(230, 230, 230));
  inner_container->set_id(kInnerContainerID);
  right_container_->AddChildView(inner_container);
  inner_container->SetBounds(100, 10, 150, 180);

  ScrollView* scroll_view = new ScrollView();
  scroll_view->set_id(kScrollViewID);
  inner_container->AddChildView(scroll_view);
  scroll_view->SetBounds(1, 1, 148, 178);

  View* scroll_content = new View();
  scroll_content->SetBounds(0, 0, 200, 200);
  scroll_content->set_background(
      Background::CreateSolidBackground(200, 200, 200));
  scroll_view->SetContents(scroll_content);

  static const char* const kTitles[] = {
      "Rosetta", "Stupeur et tremblement", "The diner game",
      "Ridicule", "Le placard", "Les Visiteurs", "Amelie",
      "Joyeux Noel", "Camping", "Brice de Nice",
      "Taxi", "Asterix"
  };

  static const int kIDs[] = {
      kRosettaLinkID, kStupeurEtTremblementLinkID, kDinerGameLinkID,
      kRidiculeLinkID, kClosetLinkID, kVisitingLinkID, kAmelieLinkID,
      kJoyeuxNoelLinkID, kCampingLinkID, kBriceDeNiceLinkID,
      kTaxiLinkID, kAsterixLinkID
  };

  DCHECK(arraysize(kTitles) == arraysize(kIDs));

  y = 5;
  for (size_t i = 0; i < arraysize(kTitles); ++i) {
    Link* link = new Link(ASCIIToUTF16(kTitles[i]));
    link->SetHorizontalAlignment(gfx::ALIGN_LEFT);
    link->set_id(kIDs[i]);
    scroll_content->AddChildView(link);
    link->SetBounds(5, y, 300, 15);
    y += 15;
  }

  y = 250;
  int width = 60;
  button = new LabelButton(NULL, ASCIIToUTF16("OK"));
  button->SetStyle(Button::STYLE_BUTTON);
  button->set_id(kOKButtonID);
  button->SetIsDefault(true);

  GetContentsView()->AddChildView(button);
  button->SetBounds(150, y, width, 30);

  button = new LabelButton(NULL, ASCIIToUTF16("Cancel"));
  button->SetStyle(Button::STYLE_BUTTON);
  button->set_id(kCancelButtonID);
  GetContentsView()->AddChildView(button);
  button->SetBounds(220, y, width, 30);

  button = new LabelButton(NULL, ASCIIToUTF16("Help"));
  button->SetStyle(Button::STYLE_BUTTON);
  button->set_id(kHelpButtonID);
  GetContentsView()->AddChildView(button);
  button->SetBounds(290, y, width, 30);

  y += 40;

  View* contents = NULL;
  Link* link = NULL;

  // Left bottom box with style checkboxes.
  contents = new View();
  contents->set_background(Background::CreateSolidBackground(SK_ColorWHITE));
  cb = new Checkbox(ASCIIToUTF16("Bold"));
  contents->AddChildView(cb);
  cb->SetBounds(10, 10, 50, 20);
  cb->set_id(kBoldCheckBoxID);

  cb = new Checkbox(ASCIIToUTF16("Italic"));
  contents->AddChildView(cb);
  cb->SetBounds(70, 10, 50, 20);
  cb->set_id(kItalicCheckBoxID);

  cb = new Checkbox(ASCIIToUTF16("Underlined"));
  contents->AddChildView(cb);
  cb->SetBounds(130, 10, 70, 20);
  cb->set_id(kUnderlinedCheckBoxID);

  link = new Link(ASCIIToUTF16("Help"));
  contents->AddChildView(link);
  link->SetBounds(10, 35, 70, 10);
  link->set_id(kStyleHelpLinkID);

  text_field = new Textfield();
  contents->AddChildView(text_field);
  text_field->SetBounds(10, 50, 100, 20);
  text_field->set_id(kStyleTextEditID);

  style_tab_ = new TabbedPane();
  style_tab_->set_id(kStyleContainerID);
  GetContentsView()->AddChildView(style_tab_);
  style_tab_->SetBounds(10, y, 210, 100);
  style_tab_->AddTab(ASCIIToUTF16("Style"), contents);
  style_tab_->AddTab(ASCIIToUTF16("Other"), new View());

  // Right bottom box with search.
  contents = new View();
  contents->set_background(Background::CreateSolidBackground(SK_ColorWHITE));
  text_field = new Textfield();
  contents->AddChildView(text_field);
  text_field->SetBounds(10, 10, 100, 20);
  text_field->set_id(kSearchTextfieldID);

  button = new LabelButton(NULL, ASCIIToUTF16("Search"));
  button->SetStyle(Button::STYLE_BUTTON);
  contents->AddChildView(button);
  button->SetBounds(112, 5, 60, 30);
  button->set_id(kSearchButtonID);

  link = new Link(ASCIIToUTF16("Help"));
  link->SetHorizontalAlignment(gfx::ALIGN_LEFT);
  link->set_id(kHelpLinkID);
  contents->AddChildView(link);
  link->SetBounds(175, 10, 30, 20);

  search_border_view_ = new BorderView(contents);
  search_border_view_->set_id(kSearchContainerID);

  GetContentsView()->AddChildView(search_border_view_);
  search_border_view_->SetBounds(300, y, 240, 50);

  y += 60;

  contents = new View();
  contents->SetFocusable(true);
  contents->set_background(Background::CreateSolidBackground(SK_ColorBLUE));
  contents->set_id(kThumbnailContainerID);
  button = new LabelButton(NULL, ASCIIToUTF16("Star"));
  button->SetStyle(Button::STYLE_BUTTON);
  contents->AddChildView(button);
  button->SetBounds(5, 5, 50, 30);
  button->set_id(kThumbnailStarID);
  button = new LabelButton(NULL, ASCIIToUTF16("SuperStar"));
  button->SetStyle(Button::STYLE_BUTTON);
  contents->AddChildView(button);
  button->SetBounds(60, 5, 100, 30);
  button->set_id(kThumbnailSuperStarID);

  GetContentsView()->AddChildView(contents);
  contents->SetBounds(250, y, 200, 50);
  // We can only call RadioButton::SetChecked() on the radio-button is part of
  // the view hierarchy.
  radio_button_to_check->SetChecked(true);
}

TEST_F(FocusTraversalTest, NormalTraversal) {
  const int kTraversalIDs[] = { kTopCheckBoxID,  kAppleTextfieldID,
      kOrangeTextfieldID, kBananaTextfieldID, kKiwiTextfieldID,
      kFruitButtonID, kFruitCheckBoxID, kComboboxID, kBroccoliButtonID,
      kRosettaLinkID, kStupeurEtTremblementLinkID,
      kDinerGameLinkID, kRidiculeLinkID, kClosetLinkID, kVisitingLinkID,
      kAmelieLinkID, kJoyeuxNoelLinkID, kCampingLinkID, kBriceDeNiceLinkID,
      kTaxiLinkID, kAsterixLinkID, kOKButtonID, kCancelButtonID, kHelpButtonID,
      kStyleContainerID, kBoldCheckBoxID, kItalicCheckBoxID,
      kUnderlinedCheckBoxID, kStyleHelpLinkID, kStyleTextEditID,
      kSearchTextfieldID, kSearchButtonID, kHelpLinkID,
      kThumbnailContainerID, kThumbnailStarID, kThumbnailSuperStarID };

  // Let's traverse the whole focus hierarchy (several times, to make sure it
  // loops OK).
  GetFocusManager()->ClearFocus();
  for (int i = 0; i < 3; ++i) {
    for (size_t j = 0; j < arraysize(kTraversalIDs); j++) {
      GetFocusManager()->AdvanceFocus(false);
      View* focused_view = GetFocusManager()->GetFocusedView();
      EXPECT_TRUE(focused_view != NULL);
      if (focused_view)
        EXPECT_EQ(kTraversalIDs[j], focused_view->id());
    }
  }

  // Let's traverse in reverse order.
  GetFocusManager()->ClearFocus();
  for (int i = 0; i < 3; ++i) {
    for (int j = arraysize(kTraversalIDs) - 1; j >= 0; --j) {
      GetFocusManager()->AdvanceFocus(true);
      View* focused_view = GetFocusManager()->GetFocusedView();
      EXPECT_TRUE(focused_view != NULL);
      if (focused_view)
        EXPECT_EQ(kTraversalIDs[j], focused_view->id());
    }
  }
}

TEST_F(FocusTraversalTest, TraversalWithNonEnabledViews) {
  const int kDisabledIDs[] = {
      kBananaTextfieldID, kFruitCheckBoxID, kComboboxID, kAsparagusButtonID,
      kCauliflowerButtonID, kClosetLinkID, kVisitingLinkID, kBriceDeNiceLinkID,
      kTaxiLinkID, kAsterixLinkID, kHelpButtonID, kBoldCheckBoxID,
      kSearchTextfieldID, kHelpLinkID };

  const int kTraversalIDs[] = { kTopCheckBoxID,  kAppleTextfieldID,
      kOrangeTextfieldID, kKiwiTextfieldID, kFruitButtonID, kBroccoliButtonID,
      kRosettaLinkID, kStupeurEtTremblementLinkID, kDinerGameLinkID,
      kRidiculeLinkID, kAmelieLinkID, kJoyeuxNoelLinkID, kCampingLinkID,
      kOKButtonID, kCancelButtonID, kStyleContainerID, kItalicCheckBoxID,
      kUnderlinedCheckBoxID, kStyleHelpLinkID, kStyleTextEditID,
      kSearchButtonID, kThumbnailContainerID, kThumbnailStarID,
      kThumbnailSuperStarID };

  // Let's disable some views.
  for (size_t i = 0; i < arraysize(kDisabledIDs); i++) {
    View* v = FindViewByID(kDisabledIDs[i]);
    ASSERT_TRUE(v != NULL);
    v->SetEnabled(false);
  }

  View* focused_view;
  // Let's do one traversal (several times, to make sure it loops ok).
  GetFocusManager()->ClearFocus();
  for (int i = 0; i < 3; ++i) {
    for (size_t j = 0; j < arraysize(kTraversalIDs); j++) {
      GetFocusManager()->AdvanceFocus(false);
      focused_view = GetFocusManager()->GetFocusedView();
      EXPECT_TRUE(focused_view != NULL);
      if (focused_view)
        EXPECT_EQ(kTraversalIDs[j], focused_view->id());
    }
  }

  // Same thing in reverse.
  GetFocusManager()->ClearFocus();
  for (int i = 0; i < 3; ++i) {
    for (int j = arraysize(kTraversalIDs) - 1; j >= 0; --j) {
      GetFocusManager()->AdvanceFocus(true);
      focused_view = GetFocusManager()->GetFocusedView();
      EXPECT_TRUE(focused_view != NULL);
      if (focused_view)
        EXPECT_EQ(kTraversalIDs[j], focused_view->id());
    }
  }
}

TEST_F(FocusTraversalTest, TraversalWithInvisibleViews) {
  const int kInvisibleIDs[] = { kTopCheckBoxID, kOKButtonID,
      kThumbnailContainerID };

  const int kTraversalIDs[] = { kAppleTextfieldID, kOrangeTextfieldID,
      kBananaTextfieldID, kKiwiTextfieldID, kFruitButtonID, kFruitCheckBoxID,
      kComboboxID, kBroccoliButtonID, kRosettaLinkID,
      kStupeurEtTremblementLinkID, kDinerGameLinkID, kRidiculeLinkID,
      kClosetLinkID, kVisitingLinkID, kAmelieLinkID, kJoyeuxNoelLinkID,
      kCampingLinkID, kBriceDeNiceLinkID, kTaxiLinkID, kAsterixLinkID,
      kCancelButtonID, kHelpButtonID, kStyleContainerID, kBoldCheckBoxID,
      kItalicCheckBoxID, kUnderlinedCheckBoxID, kStyleHelpLinkID,
      kStyleTextEditID, kSearchTextfieldID, kSearchButtonID, kHelpLinkID };


  // Let's make some views invisible.
  for (size_t i = 0; i < arraysize(kInvisibleIDs); i++) {
    View* v = FindViewByID(kInvisibleIDs[i]);
    ASSERT_TRUE(v != NULL);
    v->SetVisible(false);
  }

  View* focused_view;
  // Let's do one traversal (several times, to make sure it loops ok).
  GetFocusManager()->ClearFocus();
  for (int i = 0; i < 3; ++i) {
    for (size_t j = 0; j < arraysize(kTraversalIDs); j++) {
      GetFocusManager()->AdvanceFocus(false);
      focused_view = GetFocusManager()->GetFocusedView();
      EXPECT_TRUE(focused_view != NULL);
      if (focused_view)
        EXPECT_EQ(kTraversalIDs[j], focused_view->id());
    }
  }

  // Same thing in reverse.
  GetFocusManager()->ClearFocus();
  for (int i = 0; i < 3; ++i) {
    for (int j = arraysize(kTraversalIDs) - 1; j >= 0; --j) {
      GetFocusManager()->AdvanceFocus(true);
      focused_view = GetFocusManager()->GetFocusedView();
      EXPECT_TRUE(focused_view != NULL);
      if (focused_view)
        EXPECT_EQ(kTraversalIDs[j], focused_view->id());
    }
  }
}

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->id());
    }
  }

  // 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->id());
    }
  }

  // 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)->SetAccessibilityFocusable(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->id());
    }
  }

  // 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->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