// 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 "content/browser/accessibility/browser_accessibility.h"

#include <stddef.h>

#include <algorithm>

#include "base/logging.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/string_util.h"
#include "content/browser/accessibility/browser_accessibility_manager.h"
#include "content/common/accessibility_messages.h"
#include "ui/accessibility/ax_text_utils.h"
#include "ui/accessibility/platform/ax_platform_node.h"
#include "ui/gfx/geometry/rect_conversions.h"
#include "ui/gfx/geometry/rect_f.h"

namespace content {

namespace {

// Map from unique_id to BrowserAccessibility
using UniqueIDMap = base::hash_map<int32_t, BrowserAccessibility*>;
base::LazyInstance<UniqueIDMap> g_unique_id_map = LAZY_INSTANCE_INITIALIZER;

}

#if !defined(PLATFORM_HAS_NATIVE_ACCESSIBILITY_IMPL)
// static
BrowserAccessibility* BrowserAccessibility::Create() {
  return new BrowserAccessibility();
}
#endif

BrowserAccessibility::BrowserAccessibility()
    : manager_(NULL),
      node_(NULL),
      unique_id_(ui::AXPlatformNode::GetNextUniqueId()) {
  g_unique_id_map.Get()[unique_id_] = this;
}

BrowserAccessibility::~BrowserAccessibility() {
  if (unique_id_)
    g_unique_id_map.Get().erase(unique_id_);
}

// static
BrowserAccessibility* BrowserAccessibility::GetFromUniqueID(int32_t unique_id) {
  auto iter = g_unique_id_map.Get().find(unique_id);
  if (iter == g_unique_id_map.Get().end())
    return nullptr;

  return iter->second;
}

void BrowserAccessibility::Init(BrowserAccessibilityManager* manager,
    ui::AXNode* node) {
  manager_ = manager;
  node_ = node;
}

bool BrowserAccessibility::PlatformIsLeaf() const {
  if (InternalChildCount() == 0)
    return true;

  // These types of objects may have children that we use as internal
  // implementation details, but we want to expose them as leaves to platform
  // accessibility APIs because screen readers might be confused if they find
  // any children.
  // Note that if a combo box, search box or text field are not native, they
  // might present a menu of choices using aria-owns which should not be hidden
  // from tree.
  if (IsNativeTextControl() || IsTextOnlyObject())
    return true;

  // Roles whose children are only presentational according to the ARIA and
  // HTML5 Specs should be hidden from screen readers.
  // (Note that whilst ARIA buttons can have only presentational children, HTML5
  // buttons are allowed to have content.)
  switch (GetRole()) {
    case ui::AX_ROLE_IMAGE:
    case ui::AX_ROLE_MATH:
    case ui::AX_ROLE_METER:
    case ui::AX_ROLE_SCROLL_BAR:
    case ui::AX_ROLE_SLIDER:
    case ui::AX_ROLE_SPLITTER:
    case ui::AX_ROLE_PROGRESS_INDICATOR:
      return true;
    default:
      return false;
  }
}

uint32_t BrowserAccessibility::PlatformChildCount() const {
  if (HasIntAttribute(ui::AX_ATTR_CHILD_TREE_ID)) {
    BrowserAccessibilityManager* child_manager =
        BrowserAccessibilityManager::FromID(
            GetIntAttribute(ui::AX_ATTR_CHILD_TREE_ID));
    if (child_manager && child_manager->GetRoot()->GetParent() == this)
      return 1;

    return 0;
  }

  return PlatformIsLeaf() ? 0 : InternalChildCount();
}

bool BrowserAccessibility::IsNative() const {
  return false;
}

bool BrowserAccessibility::IsDescendantOf(
    const BrowserAccessibility* ancestor) const {
  if (!ancestor)
    return false;

  if (this == ancestor)
    return true;

  if (GetParent())
    return GetParent()->IsDescendantOf(ancestor);

  return false;
}

bool BrowserAccessibility::IsTextOnlyObject() const {
  return GetRole() == ui::AX_ROLE_STATIC_TEXT ||
         GetRole() == ui::AX_ROLE_LINE_BREAK ||
         GetRole() == ui::AX_ROLE_INLINE_TEXT_BOX;
}

bool BrowserAccessibility::IsLineBreakObject() const {
  return GetRole() == ui::AX_ROLE_LINE_BREAK ||
         (IsTextOnlyObject() && GetParent() &&
          GetParent()->GetRole() == ui::AX_ROLE_LINE_BREAK);
}

BrowserAccessibility* BrowserAccessibility::PlatformGetChild(
    uint32_t child_index) const {
  BrowserAccessibility* result = nullptr;

  if (child_index == 0 && HasIntAttribute(ui::AX_ATTR_CHILD_TREE_ID)) {
    BrowserAccessibilityManager* child_manager =
        BrowserAccessibilityManager::FromID(
            GetIntAttribute(ui::AX_ATTR_CHILD_TREE_ID));
    if (child_manager && child_manager->GetRoot()->GetParent() == this)
      result = child_manager->GetRoot();
  } else {
    result = InternalGetChild(child_index);
  }

  return result;
}

bool BrowserAccessibility::PlatformIsChildOfLeaf() const {
  BrowserAccessibility* ancestor = InternalGetParent();
  while (ancestor) {
    if (ancestor->PlatformIsLeaf())
      return true;
    ancestor = ancestor->InternalGetParent();
  }

  return false;
}

BrowserAccessibility* BrowserAccessibility::GetClosestPlatformObject() const {
  BrowserAccessibility* platform_object =
      const_cast<BrowserAccessibility*>(this);
  while (platform_object && platform_object->PlatformIsChildOfLeaf())
    platform_object = platform_object->InternalGetParent();

  DCHECK(platform_object);
  return platform_object;
}

BrowserAccessibility* BrowserAccessibility::GetPreviousSibling() const {
  if (GetParent() && GetIndexInParent() > 0)
    return GetParent()->InternalGetChild(GetIndexInParent() - 1);

  return nullptr;
}

BrowserAccessibility* BrowserAccessibility::GetNextSibling() const {
  if (GetParent() &&
      GetIndexInParent() >= 0 &&
      GetIndexInParent() < static_cast<int>(
          GetParent()->InternalChildCount() - 1)) {
    return GetParent()->InternalGetChild(GetIndexInParent() + 1);
  }

  return nullptr;
}

bool BrowserAccessibility::IsPreviousSiblingOnSameLine() const {
  const BrowserAccessibility* previous_sibling = GetPreviousSibling();
  if (!previous_sibling)
    return false;

  // Line linkage information might not be provided on non-leaf objects.
  const BrowserAccessibility* leaf_object = PlatformDeepestFirstChild();
  if (!leaf_object)
    leaf_object = this;

  int32_t previous_on_line_id;
  if (leaf_object->GetIntAttribute(ui::AX_ATTR_PREVIOUS_ON_LINE_ID,
                                   &previous_on_line_id)) {
    const BrowserAccessibility* previous_on_line =
        manager()->GetFromID(previous_on_line_id);
    // In the case of a static text sibling, the object designated to be the
    // previous object on this line might be one of its children, i.e. the last
    // inline text box.
    return previous_on_line &&
           previous_on_line->IsDescendantOf(previous_sibling);
  }
  return false;
}

bool BrowserAccessibility::IsNextSiblingOnSameLine() const {
  const BrowserAccessibility* next_sibling = GetNextSibling();
  if (!next_sibling)
    return false;

  // Line linkage information might not be provided on non-leaf objects.
  const BrowserAccessibility* leaf_object = PlatformDeepestLastChild();
  if (!leaf_object)
    leaf_object = this;

  int32_t next_on_line_id;
  if (leaf_object->GetIntAttribute(ui::AX_ATTR_NEXT_ON_LINE_ID,
                                   &next_on_line_id)) {
    const BrowserAccessibility* next_on_line =
        manager()->GetFromID(next_on_line_id);
    // In the case of a static text sibling, the object designated to be the
    // next object on this line might be one of its children, i.e. the first
    // inline text box.
    return next_on_line && next_on_line->IsDescendantOf(next_sibling);
  }
  return false;
}

BrowserAccessibility* BrowserAccessibility::PlatformDeepestFirstChild() const {
  if (!PlatformChildCount())
    return nullptr;

  BrowserAccessibility* deepest_child = PlatformGetChild(0);
  while (deepest_child->PlatformChildCount())
    deepest_child = deepest_child->PlatformGetChild(0);

  return deepest_child;
}

BrowserAccessibility* BrowserAccessibility::PlatformDeepestLastChild() const {
  if (!PlatformChildCount())
    return nullptr;

  BrowserAccessibility* deepest_child =
      PlatformGetChild(PlatformChildCount() - 1);
  while (deepest_child->PlatformChildCount()) {
    deepest_child = deepest_child->PlatformGetChild(
        deepest_child->PlatformChildCount() - 1);
  }

  return deepest_child;
}

BrowserAccessibility* BrowserAccessibility::InternalDeepestFirstChild() const {
  if (!InternalChildCount())
    return nullptr;

  BrowserAccessibility* deepest_child = InternalGetChild(0);
  while (deepest_child->InternalChildCount())
    deepest_child = deepest_child->InternalGetChild(0);

  return deepest_child;
}

BrowserAccessibility* BrowserAccessibility::InternalDeepestLastChild() const {
  if (!InternalChildCount())
    return nullptr;

  BrowserAccessibility* deepest_child =
      InternalGetChild(InternalChildCount() - 1);
  while (deepest_child->InternalChildCount()) {
    deepest_child = deepest_child->InternalGetChild(
        deepest_child->InternalChildCount() - 1);
  }

  return deepest_child;
}

uint32_t BrowserAccessibility::InternalChildCount() const {
  if (!node_ || !manager_)
    return 0;
  return static_cast<uint32_t>(node_->child_count());
}

BrowserAccessibility* BrowserAccessibility::InternalGetChild(
    uint32_t child_index) const {
  if (!node_ || !manager_ || child_index >= InternalChildCount())
    return nullptr;

  auto* child_node = node_->ChildAtIndex(child_index);
  DCHECK(child_node);
  return manager_->GetFromAXNode(child_node);
}

BrowserAccessibility* BrowserAccessibility::GetParent() const {
  if (!instance_active())
    return nullptr;

  ui::AXNode* parent = node_->parent();
  if (parent)
    return manager_->GetFromAXNode(parent);

  return manager_->GetParentNodeFromParentTree();
}

BrowserAccessibility* BrowserAccessibility::InternalGetParent() const {
  if (!node_ || !manager_)
    return nullptr;
  ui::AXNode* parent = node_->parent();
  if (parent)
    return manager_->GetFromAXNode(parent);

  return nullptr;
}

int32_t BrowserAccessibility::GetIndexInParent() const {
  return node_ ? node_->index_in_parent() : -1;
}

int32_t BrowserAccessibility::GetId() const {
  return node_ ? node_->id() : -1;
}

const ui::AXNodeData& BrowserAccessibility::GetData() const {
  CR_DEFINE_STATIC_LOCAL(ui::AXNodeData, empty_data, ());
  if (node_)
    return node_->data();
  else
    return empty_data;
}

gfx::RectF BrowserAccessibility::GetLocation() const {
  return GetData().location;
}

int32_t BrowserAccessibility::GetRole() const {
  return GetData().role;
}

int32_t BrowserAccessibility::GetState() const {
  return GetData().state;
}

const BrowserAccessibility::HtmlAttributes&
BrowserAccessibility::GetHtmlAttributes() const {
  return GetData().html_attributes;
}

gfx::Rect BrowserAccessibility::GetFrameBoundsRect() const {
  gfx::RectF bounds = GetLocation();
  FixEmptyBounds(&bounds);
  return RelativeToAbsoluteBounds(bounds, true);
}

gfx::Rect BrowserAccessibility::GetPageBoundsRect() const {
  gfx::RectF bounds = GetLocation();
  FixEmptyBounds(&bounds);
  return RelativeToAbsoluteBounds(bounds, false);
}

gfx::Rect BrowserAccessibility::GetScreenBoundsRect() const {
  gfx::Rect bounds = GetPageBoundsRect();

  // Adjust the bounds by the top left corner of the containing view's bounds
  // in screen coordinates.
  bounds.Offset(manager_->GetViewBounds().OffsetFromOrigin());

  return bounds;
}

gfx::Rect BrowserAccessibility::GetPageBoundsForRange(int start, int len)
    const {
  DCHECK_GE(start, 0);
  DCHECK_GE(len, 0);

  // Standard text fields such as textarea have an embedded div inside them that
  // holds all the text.
  // TODO(nektar): This is fragile! Replace with code that flattens tree.
  if (IsSimpleTextControl() && InternalChildCount() == 1)
    return InternalGetChild(0)->GetPageBoundsForRange(start, len);

  if (GetRole() != ui::AX_ROLE_STATIC_TEXT) {
    gfx::Rect bounds;
    for (size_t i = 0; i < InternalChildCount() && len > 0; ++i) {
      BrowserAccessibility* child = InternalGetChild(i);
      // Child objects are of length one, since they are represented by a single
      // embedded object character. The exception is text-only objects.
      int child_length_in_parent = 1;
      if (child->IsTextOnlyObject())
        child_length_in_parent = static_cast<int>(child->GetText().size());
      if (start < child_length_in_parent) {
        gfx::Rect child_rect;
        if (child->IsTextOnlyObject()) {
          child_rect = child->GetPageBoundsForRange(start, len);
        } else {
          child_rect = child->GetPageBoundsForRange(
              0, static_cast<int>(child->GetText().size()));
        }
        bounds.Union(child_rect);
        len -= (child_length_in_parent - start);
      }
      if (start > child_length_in_parent)
        start -= child_length_in_parent;
      else
        start = 0;
    }
    return bounds;
  }

  int end = start + len;
  int child_start = 0;
  int child_end = 0;
  gfx::Rect bounds;
  for (size_t i = 0; i < InternalChildCount() && child_end < start + len; ++i) {
    BrowserAccessibility* child = InternalGetChild(i);
    if (child->GetRole() != ui::AX_ROLE_INLINE_TEXT_BOX) {
      DLOG(WARNING) << "BrowserAccessibility objects with role STATIC_TEXT " <<
          "should have children of role INLINE_TEXT_BOX.";
      continue;
    }

    int child_length = static_cast<int>(child->GetText().size());
    child_start = child_end;
    child_end += child_length;

    if (child_end < start)
      continue;

    int overlap_start = std::max(start, child_start);
    int overlap_end = std::min(end, child_end);

    int local_start = overlap_start - child_start;
    int local_end = overlap_end - child_start;
    // |local_end| and |local_start| may equal |child_length| when the caret is
    // at the end of a text field.
    DCHECK_GE(local_start, 0);
    DCHECK_LE(local_start, child_length);
    DCHECK_GE(local_end, 0);
    DCHECK_LE(local_end, child_length);

    const std::vector<int32_t>& character_offsets =
        child->GetIntListAttribute(ui::AX_ATTR_CHARACTER_OFFSETS);
    int character_offsets_length = static_cast<int>(character_offsets.size());
    if (character_offsets_length < child_length) {
      // Blink might not return pixel offsets for all characters.
      // Clamp the character range to be within the number of provided pixels.
      local_start = std::min(local_start, character_offsets_length);
      local_end = std::min(local_end, character_offsets_length);
    }
    int start_pixel_offset =
        local_start > 0 ? character_offsets[local_start - 1] : 0;
    int end_pixel_offset =
        local_end > 0 ? character_offsets[local_end - 1] : 0;

    gfx::Rect child_rect = child->GetPageBoundsRect();
    auto text_direction = static_cast<ui::AXTextDirection>(
        child->GetIntAttribute(ui::AX_ATTR_TEXT_DIRECTION));
    gfx::Rect child_overlap_rect;
    switch (text_direction) {
      case ui::AX_TEXT_DIRECTION_NONE:
      case ui::AX_TEXT_DIRECTION_LTR: {
        int left = child_rect.x() + start_pixel_offset;
        int right = child_rect.x() + end_pixel_offset;
        child_overlap_rect = gfx::Rect(left, child_rect.y(),
                                       right - left, child_rect.height());
        break;
      }
      case ui::AX_TEXT_DIRECTION_RTL: {
        int right = child_rect.right() - start_pixel_offset;
        int left = child_rect.right() - end_pixel_offset;
        child_overlap_rect = gfx::Rect(left, child_rect.y(),
                                       right - left, child_rect.height());
        break;
      }
      case ui::AX_TEXT_DIRECTION_TTB: {
        int top = child_rect.y() + start_pixel_offset;
        int bottom = child_rect.y() + end_pixel_offset;
        child_overlap_rect = gfx::Rect(child_rect.x(), top,
                                       child_rect.width(), bottom - top);
        break;
      }
      case ui::AX_TEXT_DIRECTION_BTT: {
        int bottom = child_rect.bottom() - start_pixel_offset;
        int top = child_rect.bottom() - end_pixel_offset;
        child_overlap_rect = gfx::Rect(child_rect.x(), top,
                                       child_rect.width(), bottom - top);
        break;
      }
    }

    if (bounds.width() == 0 && bounds.height() == 0)
      bounds = child_overlap_rect;
    else
      bounds.Union(child_overlap_rect);
  }

  return bounds;
}

gfx::Rect BrowserAccessibility::GetScreenBoundsForRange(int start, int len)
    const {
  gfx::Rect bounds = GetPageBoundsForRange(start, len);

  // Adjust the bounds by the top left corner of the containing view's bounds
  // in screen coordinates.
  bounds.Offset(manager_->GetViewBounds().OffsetFromOrigin());

  return bounds;
}

base::string16 BrowserAccessibility::GetValue() const {
  base::string16 value = GetString16Attribute(ui::AX_ATTR_VALUE);
  // Some screen readers like Jaws and older versions of VoiceOver require a
  // value to be set in text fields with rich content, even though the same
  // information is available on the children.
  if (value.empty() &&
      (IsSimpleTextControl() || IsRichTextControl()) &&
      !IsNativeTextControl())
    value = GetInnerText();
  return value;
}

int BrowserAccessibility::GetLineStartBoundary(
    int start,
    ui::TextBoundaryDirection direction,
    ui::AXTextAffinity affinity) const {
  DCHECK_GE(start, 0);
  DCHECK_LE(start, static_cast<int>(GetText().length()));

  if (IsSimpleTextControl()) {
    return ui::FindAccessibleTextBoundary(GetText(), GetLineStartOffsets(),
                                          ui::LINE_BOUNDARY, start, direction,
                                          affinity);
  }

  // Keeps track of the start offset of each consecutive line.
  int line_start = 0;
  // Keeps track of the length of each consecutive line.
  int line_length = 0;
  for (size_t i = 0; i < InternalChildCount(); ++i) {
    const BrowserAccessibility* child = InternalGetChild(i);
    DCHECK(child);
    // Child objects are of length one, since they are represented by a
    // single embedded object character. The exception is text-only objects.
    int child_length = 1;
    if (child->IsTextOnlyObject())
      child_length = static_cast<int>(child->GetText().length());

    // Determine if |start| is within this child. As a special case, if
    // the affinity is upstream, then the cursor position between two
    // lines belongs to the previous line.
    bool start_index_within_child = start < child_length;
    if (start == child_length &&
        !child->IsNextSiblingOnSameLine() &&
        affinity == ui::AX_TEXT_AFFINITY_UPSTREAM) {
      start_index_within_child = true;
    }

    // Stop when we reach both the child containing our start offset and, in
    // case we are searching forward, the child that is at the end of the line
    // on which this object is located.
    if (start_index_within_child && (direction == ui::BACKWARDS_DIRECTION ||
                                     !child->IsNextSiblingOnSameLine())) {
      // Recurse into the inline text boxes.
      if (child->GetRole() == ui::AX_ROLE_STATIC_TEXT) {
        switch (direction) {
          case ui::FORWARDS_DIRECTION:
            line_length += child->GetLineStartBoundary(
                std::max(start, 0), direction, affinity);
            break;
          case ui::BACKWARDS_DIRECTION:
            line_start += child->GetLineStartBoundary(
                std::max(start, 0), direction, affinity);
            break;
        }
      } else {
        line_length += child_length;
      }

      break;
    }
    line_length += child_length;

    if (!child->IsNextSiblingOnSameLine()) {
      // We are on a new line.
      line_start += line_length;
      line_length = 0;
    }

    start -= child_length;
  }

  switch (direction) {
    case ui::FORWARDS_DIRECTION:
      return line_start + line_length;
    case ui::BACKWARDS_DIRECTION:
      return line_start;
  }
  NOTREACHED();
  return 0;
}

int BrowserAccessibility::GetWordStartBoundary(
    int start, ui::TextBoundaryDirection direction) const {
  DCHECK_GE(start, -1);
  // Special offset that indicates that a word boundary has not been found.
  int word_start_not_found = static_cast<int>(GetText().size());
  int word_start = word_start_not_found;

  switch (GetRole()) {
    case ui::AX_ROLE_STATIC_TEXT: {
      int prev_word_start = word_start_not_found;
      int child_start = 0;
      int child_end = 0;

      // Go through the inline text boxes.
      for (size_t i = 0; i < InternalChildCount(); ++i) {
        // The next child starts where the previous one ended.
        child_start = child_end;
        const BrowserAccessibility* child = InternalGetChild(i);
        DCHECK_EQ(child->GetRole(), ui::AX_ROLE_INLINE_TEXT_BOX);
        int child_len = static_cast<int>(child->GetText().size());
        child_end += child_len; // End is one past the last character.

        const std::vector<int32_t>& word_starts =
            child->GetIntListAttribute(ui::AX_ATTR_WORD_STARTS);
        if (word_starts.empty()) {
          word_start = child_end;
          continue;
        }

        int local_start = start - child_start;
        std::vector<int32_t>::const_iterator iter = std::upper_bound(
            word_starts.begin(), word_starts.end(), local_start);
        if (iter != word_starts.end()) {
          if (direction == ui::FORWARDS_DIRECTION) {
            word_start = child_start + *iter;
          } else if (direction == ui::BACKWARDS_DIRECTION) {
            if (iter == word_starts.begin()) {
              // Return the position of the last word in the previous child.
              word_start = prev_word_start;
            } else {
              word_start = child_start + *(iter - 1);
            }
          } else {
            NOTREACHED();
          }
          break;
        }

        // No word start that is greater than the requested offset has been
        // found.
        prev_word_start = child_start + *(iter - 1);
        if (direction == ui::FORWARDS_DIRECTION) {
          word_start = child_end;
        } else if (direction == ui::BACKWARDS_DIRECTION) {
          word_start = prev_word_start;
        } else {
          NOTREACHED();
        }
      }
      return word_start;
    }

    case ui::AX_ROLE_LINE_BREAK:
      // Words never start at a line break.
      return word_start_not_found;

    default:
      // If there are no children, the word start boundary is still unknown or
      // found previously depending on the direction.
      if (!InternalChildCount())
        return word_start_not_found;

      const BrowserAccessibility* this_object = this;
      // Standard text fields such as textarea have an embedded div inside them
      // that should be skipped.
      // TODO(nektar): This is fragile. Replace with code that flattens tree.
      if (IsSimpleTextControl() && InternalChildCount() == 1) {
        this_object = InternalGetChild(0);
      }
      int child_start = 0;
      for (size_t i = 0; i < this_object->InternalChildCount(); ++i) {
        BrowserAccessibility* child = this_object->InternalGetChild(i);
        // Child objects are of length one, since they are represented by a
        // single embedded object character. The exception is text-only objects.
        int child_len = 1;
        if (child->IsTextOnlyObject()) {
          child_len = static_cast<int>(child->GetText().length());
          int child_word_start = child->GetWordStartBoundary(start, direction);
          if (child_word_start < child_len) {
            // We have found a possible word boundary.
            word_start = child_start + child_word_start;
          }

          // Decide when to stop searching.
          if ((word_start != word_start_not_found &&
               direction == ui::FORWARDS_DIRECTION) ||
              (start < child_len && direction == ui::BACKWARDS_DIRECTION)) {
            break;
          }
        }

        child_start += child_len;
        if (start >= child_len)
          start -= child_len;
        else
          start = -1;
      }
      return word_start;
  }
}

BrowserAccessibility* BrowserAccessibility::ApproximateHitTest(
    const gfx::Point& point) {
  // The best result found that's a child of this object.
  BrowserAccessibility* child_result = NULL;
  // The best result that's an indirect descendant like grandchild, etc.
  BrowserAccessibility* descendant_result = NULL;

  // Walk the children recursively looking for the BrowserAccessibility that
  // most tightly encloses the specified point. Walk backwards so that in
  // the absence of any other information, we assume the object that occurs
  // later in the tree is on top of one that comes before it.
  for (int i = static_cast<int>(PlatformChildCount()) - 1; i >= 0; --i) {
    BrowserAccessibility* child = PlatformGetChild(i);

    // Skip table columns because cells are only contained in rows,
    // not columns.
    if (child->GetRole() == ui::AX_ROLE_COLUMN)
      continue;

    if (child->GetScreenBoundsRect().Contains(point)) {
      BrowserAccessibility* result = child->ApproximateHitTest(point);
      if (result == child && !child_result)
        child_result = result;
      if (result != child && !descendant_result)
        descendant_result = result;
    }

    if (child_result && descendant_result)
      break;
  }

  // Explanation of logic: it's possible that this point overlaps more than
  // one child of this object. If so, as a heuristic we prefer if the point
  // overlaps a descendant of one of the two children and not the other.
  // As an example, suppose you have two rows of buttons - the buttons don't
  // overlap, but the rows do. Without this heuristic, we'd greedily only
  // consider one of the containers.
  if (descendant_result)
    return descendant_result;
  if (child_result)
    return child_result;

  return this;
}

void BrowserAccessibility::Destroy() {
  // Allow the object to fire a TextRemoved notification.
  manager()->NotifyAccessibilityEvent(
      BrowserAccessibilityEvent::FromTreeChange,
      ui::AX_EVENT_HIDE,
      this);
  node_ = NULL;
  manager_ = NULL;

  if (unique_id_)
    g_unique_id_map.Get().erase(unique_id_);
  unique_id_ = 0;

  NativeReleaseReference();
}

void BrowserAccessibility::NativeReleaseReference() {
  delete this;
}

bool BrowserAccessibility::HasBoolAttribute(
    ui::AXBoolAttribute attribute) const {
  return GetData().HasBoolAttribute(attribute);
}

bool BrowserAccessibility::GetBoolAttribute(
    ui::AXBoolAttribute attribute) const {
  return GetData().GetBoolAttribute(attribute);
}

bool BrowserAccessibility::GetBoolAttribute(
    ui::AXBoolAttribute attribute, bool* value) const {
  return GetData().GetBoolAttribute(attribute, value);
}

bool BrowserAccessibility::HasFloatAttribute(
    ui::AXFloatAttribute attribute) const {
  return GetData().HasFloatAttribute(attribute);
}

float BrowserAccessibility::GetFloatAttribute(
    ui::AXFloatAttribute attribute) const {
  return GetData().GetFloatAttribute(attribute);
}

bool BrowserAccessibility::GetFloatAttribute(
    ui::AXFloatAttribute attribute, float* value) const {
  return GetData().GetFloatAttribute(attribute, value);
}

bool BrowserAccessibility::HasInheritedStringAttribute(
    ui::AXStringAttribute attribute) const {
  if (!instance_active())
    return false;

  if (GetData().HasStringAttribute(attribute))
    return true;
  return GetParent() && GetParent()->HasInheritedStringAttribute(attribute);
}

const std::string& BrowserAccessibility::GetInheritedStringAttribute(
    ui::AXStringAttribute attribute) const {
  if (!instance_active())
    return base::EmptyString();

  const BrowserAccessibility* current_object = this;
  do {
    if (current_object->GetData().HasStringAttribute(attribute))
      return current_object->GetData().GetStringAttribute(attribute);
    current_object = current_object->GetParent();
  } while (current_object);
  return base::EmptyString();
}

bool BrowserAccessibility::GetInheritedStringAttribute(
    ui::AXStringAttribute attribute,
    std::string* value) const {
  if (!instance_active()) {
    *value = std::string();
    return false;
  }

  if (GetData().GetStringAttribute(attribute, value))
    return true;
  return GetParent() &&
         GetParent()->GetData().GetStringAttribute(attribute, value);
}

base::string16 BrowserAccessibility::GetInheritedString16Attribute(
    ui::AXStringAttribute attribute) const {
  if (!instance_active())
    return base::string16();

  const BrowserAccessibility* current_object = this;
  do {
    if (current_object->GetData().HasStringAttribute(attribute))
      return current_object->GetData().GetString16Attribute(attribute);
    current_object = current_object->GetParent();
  } while (current_object);
  return base::string16();
}

bool BrowserAccessibility::GetInheritedString16Attribute(
    ui::AXStringAttribute attribute,
    base::string16* value) const {
  if (!instance_active()) {
    *value = base::string16();
    return false;
  }

  if (GetData().GetString16Attribute(attribute, value))
    return true;
  return GetParent() &&
         GetParent()->GetData().GetString16Attribute(attribute, value);
}

bool BrowserAccessibility::HasIntAttribute(
    ui::AXIntAttribute attribute) const {
  return GetData().HasIntAttribute(attribute);
}

int BrowserAccessibility::GetIntAttribute(ui::AXIntAttribute attribute) const {
  return GetData().GetIntAttribute(attribute);
}

bool BrowserAccessibility::GetIntAttribute(
    ui::AXIntAttribute attribute, int* value) const {
  return GetData().GetIntAttribute(attribute, value);
}

bool BrowserAccessibility::HasStringAttribute(
    ui::AXStringAttribute attribute) const {
  return GetData().HasStringAttribute(attribute);
}

const std::string& BrowserAccessibility::GetStringAttribute(
    ui::AXStringAttribute attribute) const {
  return GetData().GetStringAttribute(attribute);
}

bool BrowserAccessibility::GetStringAttribute(
    ui::AXStringAttribute attribute, std::string* value) const {
  return GetData().GetStringAttribute(attribute, value);
}

base::string16 BrowserAccessibility::GetString16Attribute(
    ui::AXStringAttribute attribute) const {
  return GetData().GetString16Attribute(attribute);
}

bool BrowserAccessibility::GetString16Attribute(ui::AXStringAttribute attribute,
                                                base::string16* value) const {
  return GetData().GetString16Attribute(attribute, value);
}

bool BrowserAccessibility::HasIntListAttribute(
    ui::AXIntListAttribute attribute) const {
  return GetData().HasIntListAttribute(attribute);
}

const std::vector<int32_t>& BrowserAccessibility::GetIntListAttribute(
    ui::AXIntListAttribute attribute) const {
  return GetData().GetIntListAttribute(attribute);
}

bool BrowserAccessibility::GetIntListAttribute(
    ui::AXIntListAttribute attribute,
    std::vector<int32_t>* value) const {
  return GetData().GetIntListAttribute(attribute, value);
}

bool BrowserAccessibility::GetHtmlAttribute(
    const char* html_attr, std::string* value) const {
  return GetData().GetHtmlAttribute(html_attr, value);
}

bool BrowserAccessibility::GetHtmlAttribute(
    const char* html_attr, base::string16* value) const {
  return GetData().GetHtmlAttribute(html_attr, value);
}

bool BrowserAccessibility::GetAriaTristate(
    const char* html_attr,
    bool* is_defined,
    bool* is_mixed) const {
  *is_defined = false;
  *is_mixed = false;

  base::string16 value;
  if (!GetHtmlAttribute(html_attr, &value) ||
      value.empty() ||
      base::EqualsASCII(value, "undefined")) {
    return false;  // Not set (and *is_defined is also false)
  }

  *is_defined = true;

  if (base::EqualsASCII(value, "true"))
    return true;

  if (base::EqualsASCII(value, "mixed"))
    *is_mixed = true;

  return false;  // Not set.
}

base::string16 BrowserAccessibility::GetText() const {
  return GetInnerText();
}

bool BrowserAccessibility::HasState(ui::AXState state_enum) const {
  return (GetState() >> state_enum) & 1;
}

bool BrowserAccessibility::IsCellOrTableHeaderRole() const {
  return (GetRole() == ui::AX_ROLE_CELL ||
          GetRole() == ui::AX_ROLE_COLUMN_HEADER ||
          GetRole() == ui::AX_ROLE_ROW_HEADER);
}

bool BrowserAccessibility::IsTableOrGridOrTreeGridRole() const {
  return (GetRole() == ui::AX_ROLE_TABLE ||
          GetRole() == ui::AX_ROLE_GRID ||
          GetRole() == ui::AX_ROLE_TREE_GRID);
}

bool BrowserAccessibility::HasCaret() const {
  if (IsSimpleTextControl() && HasIntAttribute(ui::AX_ATTR_TEXT_SEL_START) &&
      HasIntAttribute(ui::AX_ATTR_TEXT_SEL_END)) {
    return true;
  }

  // The caret is always at the focus of the selection.
  int32_t focus_id = manager()->GetTreeData().sel_focus_object_id;
  BrowserAccessibility* focus_object = manager()->GetFromID(focus_id);
  if (!focus_object)
    return false;

  return focus_object->IsDescendantOf(this);
}

bool BrowserAccessibility::IsWebAreaForPresentationalIframe() const {
  if (GetRole() != ui::AX_ROLE_WEB_AREA &&
      GetRole() != ui::AX_ROLE_ROOT_WEB_AREA) {
    return false;
  }

  BrowserAccessibility* parent = GetParent();
  if (!parent)
    return false;

  return parent->GetRole() == ui::AX_ROLE_IFRAME_PRESENTATIONAL;
}

bool BrowserAccessibility::IsClickable() const {
  switch (GetRole()) {
    case ui::AX_ROLE_BUTTON:
    case ui::AX_ROLE_CHECK_BOX:
    case ui::AX_ROLE_COLOR_WELL:
    case ui::AX_ROLE_DISCLOSURE_TRIANGLE:
    case ui::AX_ROLE_IMAGE_MAP_LINK:
    case ui::AX_ROLE_LINK:
    case ui::AX_ROLE_LIST_BOX_OPTION:
    case ui::AX_ROLE_MENU_BUTTON:
    case ui::AX_ROLE_MENU_ITEM:
    case ui::AX_ROLE_MENU_ITEM_CHECK_BOX:
    case ui::AX_ROLE_MENU_ITEM_RADIO:
    case ui::AX_ROLE_MENU_LIST_OPTION:
    case ui::AX_ROLE_MENU_LIST_POPUP:
    case ui::AX_ROLE_POP_UP_BUTTON:
    case ui::AX_ROLE_RADIO_BUTTON:
    case ui::AX_ROLE_SWITCH:
    case ui::AX_ROLE_TAB:
    case ui::AX_ROLE_TOGGLE_BUTTON:
      return true;
    default:
      return false;
  }
}

bool BrowserAccessibility::IsControl() const {
  switch (GetRole()) {
    case ui::AX_ROLE_BUTTON:
    case ui::AX_ROLE_CHECK_BOX:
    case ui::AX_ROLE_COLOR_WELL:
    case ui::AX_ROLE_COMBO_BOX:
    case ui::AX_ROLE_DISCLOSURE_TRIANGLE:
    case ui::AX_ROLE_LIST_BOX:
    case ui::AX_ROLE_MENU:
    case ui::AX_ROLE_MENU_BAR:
    case ui::AX_ROLE_MENU_BUTTON:
    case ui::AX_ROLE_MENU_ITEM:
    case ui::AX_ROLE_MENU_ITEM_CHECK_BOX:
    case ui::AX_ROLE_MENU_ITEM_RADIO:
    case ui::AX_ROLE_MENU_LIST_OPTION:
    case ui::AX_ROLE_MENU_LIST_POPUP:
    case ui::AX_ROLE_POP_UP_BUTTON:
    case ui::AX_ROLE_RADIO_BUTTON:
    case ui::AX_ROLE_SCROLL_BAR:
    case ui::AX_ROLE_SEARCH_BOX:
    case ui::AX_ROLE_SLIDER:
    case ui::AX_ROLE_SPIN_BUTTON:
    case ui::AX_ROLE_SWITCH:
    case ui::AX_ROLE_TAB:
    case ui::AX_ROLE_TEXT_FIELD:
    case ui::AX_ROLE_TOGGLE_BUTTON:
    case ui::AX_ROLE_TREE:
      return true;
    default:
      return false;
  }
}

bool BrowserAccessibility::IsMenuRelated() const {
  switch (GetRole()) {
    case ui::AX_ROLE_MENU:
    case ui::AX_ROLE_MENU_BAR:
    case ui::AX_ROLE_MENU_BUTTON:
    case ui::AX_ROLE_MENU_ITEM:
    case ui::AX_ROLE_MENU_ITEM_CHECK_BOX:
    case ui::AX_ROLE_MENU_ITEM_RADIO:
    case ui::AX_ROLE_MENU_LIST_OPTION:
    case ui::AX_ROLE_MENU_LIST_POPUP:
      return true;
    default:
      return false;
  }
}

bool BrowserAccessibility::IsNativeTextControl() const {
  const std::string& html_tag = GetStringAttribute(ui::AX_ATTR_HTML_TAG);
  if (html_tag == "input") {
    std::string input_type;
    if (!GetHtmlAttribute("type", &input_type))
      return true;
    return input_type.empty() || input_type == "email" ||
           input_type == "password" || input_type == "search" ||
           input_type == "tel" || input_type == "text" || input_type == "url" ||
           input_type == "number";
  }
  return html_tag == "textarea";
}

bool BrowserAccessibility::IsSimpleTextControl() const {
  // Time fields, color wells and spinner buttons might also use text fields as
  // constituent parts, but they are not considered text fields as a whole.
  switch (GetRole()) {
    case ui::AX_ROLE_COMBO_BOX:
    case ui::AX_ROLE_SEARCH_BOX:
      return true;
    case ui::AX_ROLE_TEXT_FIELD:
      return !HasState(ui::AX_STATE_RICHLY_EDITABLE);
    default:
      return false;
  }
}

// Indicates if this object is at the root of a rich edit text control.
bool BrowserAccessibility::IsRichTextControl() const {
  return HasState(ui::AX_STATE_RICHLY_EDITABLE) &&
         (!GetParent() || !GetParent()->HasState(ui::AX_STATE_RICHLY_EDITABLE));
}

std::string BrowserAccessibility::ComputeAccessibleNameFromDescendants() {
  std::string name;
  for (size_t i = 0; i < InternalChildCount(); ++i) {
    BrowserAccessibility* child = InternalGetChild(i);
    std::string child_name;
    if (child->GetStringAttribute(ui::AX_ATTR_NAME, &child_name)) {
      if (!name.empty())
        name += " ";
      name += child_name;
    } else if (!child->HasState(ui::AX_STATE_FOCUSABLE)) {
      child_name = child->ComputeAccessibleNameFromDescendants();
      if (!child_name.empty()) {
        if (!name.empty())
          name += " ";
        name += child_name;
      }
    }
  }

  return name;
}

std::vector<int> BrowserAccessibility::GetLineStartOffsets() const {
  if (!instance_active())
    return std::vector<int>();
  return node()->GetOrComputeLineStartOffsets();
}

base::string16 BrowserAccessibility::GetInnerText() const {
  if (IsTextOnlyObject())
    return GetString16Attribute(ui::AX_ATTR_NAME);

  base::string16 text;
  for (size_t i = 0; i < InternalChildCount(); ++i)
    text += InternalGetChild(i)->GetInnerText();
  return text;
}

void BrowserAccessibility::FixEmptyBounds(gfx::RectF* bounds) const
{
  if (bounds->width() > 0 && bounds->height() > 0)
    return;

  for (size_t i = 0; i < InternalChildCount(); ++i) {
    // Compute the bounds of each child - this calls FixEmptyBounds
    // recursively if necessary.
    BrowserAccessibility* child = InternalGetChild(i);
    gfx::Rect child_bounds = child->GetPageBoundsRect();

    // Ignore children that don't have valid bounds themselves.
    if (child_bounds.width() == 0 || child_bounds.height() == 0)
      continue;

    // For the first valid child, just set the bounds to that child's bounds.
    if (bounds->width() == 0 || bounds->height() == 0) {
      *bounds = gfx::RectF(child_bounds);
      continue;
    }

    // Union each additional child's bounds.
    bounds->Union(gfx::RectF(child_bounds));
  }
}

gfx::Rect BrowserAccessibility::RelativeToAbsoluteBounds(
    gfx::RectF bounds,
    bool frame_only) const {
  const BrowserAccessibility* node = this;
  while (node) {
    if (node->GetData().transform)
      node->GetData().transform->TransformRect(&bounds);

    const BrowserAccessibility* container =
        node->manager()->GetFromID(node->GetData().offset_container_id);
    if (!container) {
      if (node == node->manager()->GetRoot() && !frame_only) {
        container = node->GetParent();
      } else {
        container = node->manager()->GetRoot();
      }
    }

    if (!container || container == node)
      break;

    gfx::RectF container_bounds = container->GetLocation();
    bounds.Offset(container_bounds.x(), container_bounds.y());

    if (container->manager()->UseRootScrollOffsetsWhenComputingBounds() ||
        container->GetParent()) {
      int sx = 0;
      int sy = 0;
      if (container->GetIntAttribute(ui::AX_ATTR_SCROLL_X, &sx) &&
          container->GetIntAttribute(ui::AX_ATTR_SCROLL_Y, &sy)) {
        bounds.Offset(-sx, -sy);
      }
    }

    node = container;
  }

  return gfx::ToEnclosingRect(bounds);
}

}  // namespace content