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..1c51423323287be4266d77571af7825dbb3bfb9d
--- /dev/null
+++ b/ui/accessibility/ax_position.cc
@@ -0,0 +1,297 @@
+// 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>
+#include <utility>
+
+namespace ui {
+
+AXPosition::AXPosition(int tree_id,
+                       int32_t anchor_id,
+                       int child_index,
+                       int text_offset,
+                       AXPositionType type,
+                       std::unique_ptr<AXPositionFactory> factory)
+    : tree_id_(tree_id),
+      anchor_id_(anchor_id),
+      child_index_(child_index),
+      text_offset_(text_offset),
+      type_(type),
+      factory_(std::move(factory)) {
+  if (GetAnchor() && child_index_ >= 0 || child_index_ >= AnchorChildCount() ||
+      text_offset_ >= 0 || text_offset_ <= MaxTextOffset() || factory_) {
+    return;
+  }
+
+  // Reset to the null position.
+  tree_id_ = -1;
+  anchor_id_ = -1;
+  child_index_ = -1;
+  text_offset_ = -1;
+  type_ = AXPositionType::NullPosition;
+}
+
+AXPosition::~AXPosition() {}
+
+AXNode* AXPosition::GetAnchor() const {
+  if (tree_id_ == -1 || anchor_id_ == -1)
+    return nullptr;
+  DCHECK_GE(tree_id_, 0);
+  DCHECK_GE(anchor_id_, 0);
+  return GetNodeInTree(tree_id_, anchor_id_);
+}
+
+bool AXPosition::AtStartOfAnchor() const {
+  if (!GetAnchor())
+    return false;
+
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      return false;
+    case AXPositionType::TreePosition:
+      return child_index_ == 0;
+    case AXPositionType::TextPosition:
+      return text_offset_ == 0;
+  }
+}
+
+bool AXPosition::AtEndOfAnchor() const {
+  if (!GetAnchor())
+    return false;
+
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      return false;
+    case AXPositionType::TreePosition:
+      return child_index_ == AnchorChildCount();
+    case AXPositionType::TextPosition:
+      return text_offset_ == MaxTextOffset();
+  }
+}
+
+AXPosition AXPosition::CommonAncestor(const AXPosition& second) const {
+  std::queue<AXPosition> ancestors1;
+  ancestors1.push(*this);
+  while (!ancestors1.back().IsNullPosition())
+    ancestors1.push(ancestors1.back().GetParentPosition());
+  ancestors1.pop();
+  if (ancestors1.empty())
+    return factory_->CreateNullPosition();
+
+  std::queue<AXPosition> ancestors2;
+  ancestors2.push(second);
+  while (!ancestors2.back().IsNullPosition())
+    ancestors2.push(ancestors2.back().GetParentPosition());
+  ancestors2.pop();
+  if (ancestors2.empty())
+    return factory_->CreateNullPosition();
+
+  AXPosition commonAncestor = factory_->CreateNullPosition();
+  do {
+    if (ancestors1.front() == ancestors2.front()) {
+      commonAncestor = ancestors1.front();
+      ancestors1.pop();
+      ancestors2.pop();
+    } else {
+      break;
+    }
+  } while (!ancestors1.empty() && !ancestors2.empty());
+  return commonAncestor;
+}
+
+bool AXPosition::operator<(const AXPosition& position) const {
+  if (IsNullPosition() || position.IsNullPosition())
+    return false;
+
+  AXPosition other = position;
+  do {
+    other = other.GetPreviousAnchorPosition();
+    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;
+
+  AXPosition other = position;
+  do {
+    other = other.GetNextAnchorPosition();
+    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 {
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      return factory_->CreateNullPosition();
+    case AXPositionType::TreePosition:
+      return factory_->CreateTreePosition(tree_id_, anchor_id_,
+                                          0 /* child_index */);
+    case AXPositionType::TextPosition:
+      return factory_->CreateTextPosition(tree_id_, anchor_id_,
+                                          0 /* text_offset */);
+  }
+}
+
+AXPosition AXPosition::GetPositionAtEndOfAnchor() const {
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      return factory_->CreateNullPosition();
+    case AXPositionType::TreePosition:
+      return factory_->CreateTreePosition(tree_id_, anchor_id_,
+                                          AnchorChildCount());
+    case AXPositionType::TextPosition:
+      return factory_->CreateTextPosition(tree_id_, anchor_id_,
+                                          MaxTextOffset());
+  }
+}
+
+// Not yet implemented for tree positions.
+AXPosition AXPosition::GetNextCharacterPosition() const {
+  if (IsNullPosition())
+    return factory_->CreateNullPosition();
+
+  if (text_offset_ + 1 < MaxTextOffset())
+    return factory_->CreateTextPosition(tree_id_, anchor_id_, text_offset_ + 1);
+
+  AXPosition 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 factory_->CreateNullPosition();
+
+  if (text_offset_ > 0)
+    return factory_->CreateTextPosition(tree_id_, anchor_id_, text_offset_ - 1);
+
+  AXPosition 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 factory_->CreateNullPosition();
+
+  if (child_index < 0 || child_index >= AnchorChildCount())
+    return factory_->CreateNullPosition();
+
+  AXNode* child_anchor = GetAnchor()->ChildAtIndex(child_index);
+  DCHECK(child_anchor);
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      NOTREACHED();
+      return factory_->CreateNullPosition();
+    case AXPositionType::TreePosition:
+      return factory_->CreateTreePosition(tree_id_, child_anchor->id(),
+                                          0 /* child_index */);
+    case AXPositionType::TextPosition:
+      return factory_->CreateTextPosition(tree_id_, child_anchor->id(),
+                                          0 /* text_offset */);
+  }
+}
+
+AXPosition AXPosition::GetParentPosition() const {
+  if (IsNullPosition())
+    return factory_->CreateNullPosition();
+
+  AXNode* parent_anchor = GetAnchor()->parent();
+  if (!parent_anchor)
+    return factory_->CreateNullPosition();
+
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      NOTREACHED();
+      return factory_->CreateNullPosition();
+    case AXPositionType::TreePosition:
+      return factory_->CreateTreePosition(tree_id_, parent_anchor->id(),
+                                          0 /* child_index */);
+    case AXPositionType::TextPosition:
+      return factory_->CreateTextPosition(tree_id_, parent_anchor->id(),
+                                          0 /* text_offset */);
+  }
+}
+
+AXPosition AXPosition::GetNextAnchorPosition() const {
+  if (IsNullPosition())
+    return factory_->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 (index_in_parent < parent_position.AnchorChildCount() - 1) {
+      AXPosition 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 factory_->CreateNullPosition();
+}
+
+AXPosition AXPosition::GetPreviousAnchorPosition() const {
+  if (IsNullPosition())
+    return factory_->CreateNullPosition();
+
+  AXPosition parent_position = GetParentPosition();
+  if (parent_position.IsNullPosition())
+    return factory_->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;
+  AXPosition leaf = parent_position.GetChildPositionAt(index_in_parent - 1);
+  while (!leaf.IsNullPosition() && leaf.AnchorChildCount())
+    leaf.GetChildPositionAt(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