Creates AXPosition to uniquely identify a position in the accessibility tree

ui/accessibility/ax_position.cc

Index: ui/accessibility/ax_position.cc
diff --git a/ui/accessibility/ax_position.cc b/ui/accessibility/ax_position.cc
new file mode 100644
index 0000000000000000000000000000000000000000..8558c37a6e512ac600510f34195535c55d1c105c
--- /dev/null
+++ b/ui/accessibility/ax_position.cc
@@ -0,0 +1,275 @@
+// Copyright 2016 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/accessibility/ax_position.h"
+
+#include <queue>
+
+namespace ui {
+
+AXPosition::AXPosition(int tree_id, int32_t anchor_id, int child_index, int text_offset, AXPositionType type) : tree_id_(tree_id), anchor_id_(anchor_id), child_index_(child_index), text_offset_(text_offset), type_(type) {
+  if (!GetAnchor() || child_index_ < 0 || child_index_ > AnchorChildCount() || text_offset_ < 0 || text_offset_ > MaxTextOffset()) {
+    // Reset to the null position.
+    tree_id_ = -1;
+    anchor_id_ = -1;
+    child_index_ = -1;
+    text_offset_ = -1;
+    type_ = AXPositionType::TreePosition;
+  }
+}
+
+AXPosition::~AXPosition() {
+}
+
+AXPosition AXPosition::CreateNullPosition() {
+  return AXPosition(-1 /* tree_id */, -1 /* anchor_id */, -1 /* child_index */, -1 /* text_offset */, AXPositionType::TreePosition);
+}
+
+AXPosition AXPosition::CreateTreePosition(int tree_id, int32_t anchor_id, int child_index) {
+  return AXPosition(tree_id, anchor_id, child_index, -1 /* text_offset */, AXPositionType::TreePosition);
+}
+
+AXPosition AXPosition::CreateTextPosition(int tree_id, int32_t anchor_id, int text_offset) {
+  return AXPosition(tree_id, anchor_id, -1 /* child_index */, text_offset, AXPositionType::TextPosition);
+}
+
+AXNode* AXPosition::GetAnchor() const {
+  if (tree_id_ == -1 || anchor_id_ == -1)
+    return nullptr;
+  DCHECK_GE(tree_id_, 0);
+  DCHECK_GE(anchor_id_, 0);
+  return GetNodeFromTree(tree_id_, anchor_id_);
+}
+
+// static
+AXPosition AXPosition::CommonAncestor(const AXPosition& first, const AXPosition& second) {
+  std::queue<AXPosition> ancestors1;
+  ancestors1.push(first);
+  while (!ancestors1.back().IsNullPosition())
+    ancestors1.push(ancestors1.back().GetParentPosition());
+  ancestors1.pop();
+  if (ancestors1.empty())
+    return CreateNullPosition();
+
+  std::queue<AXPosition> ancestors2;
+  ancestors2.push(second);
+  while (!ancestors2.back().IsNullPosition())
+    ancestors2.push(ancestors2.back().GetParentPosition());
+  ancestors2.pop();
+  if (ancestors2.empty())
+    return CreateNullPosition();
+
+  AXPosition commonAncestor = CreateNullPosition();
+  do {
+    if (ancestors1.front() == ancestors2.front()) {
+      commonAncestor = ancestors1.pop(), ancestors2.pop();
+    } else {
+      break;
+    }
+  } while (!ancestors1.empty() && !ancestors2.empty());
+  return commonAncestor;
+}
+
+bool AXPosition::AtStartOfAnchor() const {
+  if (IsNullPosition())
+    return false;
+
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      return child_index_ == 0;
+    case AXPositionType:TextPosition:
+      return text_offset_ == 0;
+  }
+}
+
+bool AXPosition::AtEndOfAnchor() const {
+  if (IsNullPosition())
+    return false;
+
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      return child_index_ == AnchorChildCount();
+    case AXPositionType:TextPosition:
+      return text_offset_ == MaxTextOffset();
+  }
+}
+
+bool AXPosition::operator<(const AXPosition& position) const {
+  if (IsNullPosition() || position.IsNullPosition())
+    return false;
+
+  Position other = position;
+  do {
+    other = other.GetPreviousPosition();
+    if (other.IsNullPosition())
+      return false;
+  } while (*this != position);
+  return true;
+}
+
+bool AXPosition::operator<=(const AXPosition& position) const {
+  if (IsNullPosition() || position.IsNullPosition())
+    return false;
+  return *this == position || *this < position;
+}
+
+bool AXPosition::operator>(const AXPosition& position) const {
+  if (IsNullPosition() || position.IsNullPosition())
+    return false;
+
+  Position other = position;
+  do {
+    other = other.GetNextPosition();
+    if (other.IsNullPosition())
+      return false;
+  } while (*this != position);
+  return true;
+}
+
+bool AXPosition::operator>=(const AXPosition& position) const {
+  if (IsNullPosition() || position.IsNullPosition())
+    return false;
+  return *this == position || *this > position;
+}
+
+AXPosition AXPosition::GetPositionAtStartOfAnchor() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      return CreateTreePosition(tree_id_, anchor_id_, 0 /* child_index */);
+    case AXPositionType:TextPosition:
+      return CreateTextPosition(tree_id_, anchor_id_, 0, /* text_offset */);
+  }
+}
+
+AXPosition AXPosition::GetPositionAtEndOfAnchor() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      return CreateTreePosition(tree_id_, anchor_id_, AnchorChildCount());
+    case AXPositionType:TextPosition:
+      return CreateTextPosition(tree_id_, anchor_id_, MaxTextOffset());
+  }
+}
+
+// Not yet implemented for tree positions.
+AXPosition AXPosition::GetNextCharacterPosition() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  if (text_offset_ + 1 < MaxTextOffset())
+    return CreateTextPosition(tree_id_, anchor_id_, text_offset_ + 1);
+
+  Position next_leaf = GetNextAnchorPosition();
+  while (next_leaf.AnchorChildCount())
+    next_leaf = next_leaf.GetNextAnchorPosition();
+  return next_leaf;
+}
+
+// Not yet implemented for tree positions.
+AXPosition AXPosition::GetPreviousCharacterPosition() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+  
+  if (text_offset_ > 0)
+    return CreateTextPosition(tree_id_, anchor_id_, text_offset_ - 1);
+
+  Position previous_leaf = GetPreviousAnchorPosition();
+  while (previous_leaf.AnchorChildCount())
+    previous_leaf = previous_leaf.GetNextAnchorPosition();
+  return previous_leaf;
+}
+
+AXPosition AXPosition::GetChildPositionAt(int child_index) const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  if (child_index < 0 || child_index >= AnchorChildCount())
+    return CreateNullPosition();
+
+  AXNode* child_anchor = GetAnchor()->ChildAtIndex(child_index);
+  DCHECK(child_anchor);
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      return CreateTreePosition(tree_id_, child_anchor->id());
+    case AXPositionType::TextPosition:
+      return CreateTextPosition(tree_id_, child_anchor->id());
+  }
+}
+
+AXPosition AXPosition::GetParentPosition() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  AXNode* parent_anchor = GetAnchor()->parent();
+  if (!parent_anchor)
+    return CreateNullPosition();
+
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      return CreateTreePosition(tree_id_, parent_anchor->id());
+    case AXPositionType::TextPosition:
+      return CreateTextPosition(tree_id_, parent_anchor->id());
+  }
+}
+
+AXPosition AXPosition::GetNextAnchorPosition() const {
+  if (IsNullPosition()
+    return CreateNullPosition();
+
+  if (AnchorChildCount())
+    return GetChildPositionAt(0);
+
+  AXPosition current_position = *this;
+  AXPosition parent_position = GetParentPosition();
+  while (!parent_position.IsNullPosition()) {
+    // Get the next sibling if it exists, otherwise move up to the parent's next sibling.
+    int index_in_parent = current_position.AnchorIndexInParent();
+    if (indexInParent < parentPosition.AnchorChildCount() - 1) {
+      Position next_sibling = parent_position.GetChildPositionAt(index_in_parent + 1);
+      DCHECK(!next_sibling.IsNullPosition());
+      return next_sibling;
+    }
+
+    current_position = parent_position;
+    parent_position = current_position.GetParentPosition();
+  }
+
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetPreviousAnchorPosition() const {
+  if (IsNullPosition()
+    return CreateNullPosition();
+
+  AXPosition parent_position = GetParentPosition();
+  if (parent_position.IsNullPosition())
+    return CreateNullPosition();
+
+  // Get the previous sibling's deepest first child if a previous sibling exists, otherwise move up to the parent.
+  int index_in_parent = AnchorIndexInParent();
+  if (index_in_parent <= 0)
+    return parent_position;
+  Position leaf = parent_position.GetChildPositionAt(index_in_parent - 1);
+  while (!leaf.IsNullPosition() && leaf.AnchorChildCount())
+    leaf.GetChildPosition(0);
+
+  return leaf;
+}
+
+bool operator==(const AXPosition& first, const AXPosition& second) {
+  if (first.IsNullPosition() && second.IsNullPosition())
+    return true;
+  return first == second;
+}
+
+bool operator!=(const AXPosition& first, const AXPosition& second) {
+  return !operator==(first, second);
+}
+
+}  // namespace ui