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..ea5cef04d219b6127392b121a5ef09df35056eed
--- /dev/null
+++ b/ui/accessibility/ax_position.cc
@@ -0,0 +1,325 @@
+// 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()) {
+    return;
+  }
+
+  // Reset to the null position.
+  tree_id_ = -1;
+  anchor_id_ = -1;
+  child_index_ = -1;
+  text_offset_ = -1;
+  type_ = AXPositionType::NullPosition;
+}
+
+AXPosition::~AXPosition() {}
+
+// static
+AXNodeType::AXPosition* AXPosition::CreateNullPosition() {
+  return new AXNodeType::AXPosition(-1 /* tree_id */, -1 /* anchor_id */,
+                                    -1 /* child_index */, -1 /* text_offset */,
+                                    ui::AXPositionType::NullPosition);
+}
+
+// static
+AXNodeType::AXPosition* AXPosition::CreateTreePosition(int tree_id,
+                                                       int32_t anchor_id,
+                                                       int child_index) {
+  return new AXNodeType::AXPosition(tree_id, anchor_id, child_index,
+                                    -1 /* text_offset */,
+                                    ui::AXPositionType::TreePosition);
+}
+
+// static
+AXNodeType::AXPosition* AXPosition::CreateTextPosition(int tree_id,
+                                                       int32_t anchor_id,
+                                                       int text_offset) {
+  return new AXNodeType::AXPosition(tree_id, anchor_id, -1 /* child_index */,
+                                    text_offset,
+                                    ui::AXPositionType::TextPosition);
+}
+
+AXNodeType* 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() || !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() || !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.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 != *other);
+  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 != *other);
+  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 CreateNullPosition();
+    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 {
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      return CreateNullPosition();
+    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);
+
+  AXPosition* next_leaf = GetNextAnchorPosition();
+  while (next_leaf && 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);
+
+  AXPosition* previous_leaf = GetPreviousAnchorPosition();
+  while (previous_leaf && previous_leaf->AnchorChildCount())
+    previous_leaf = previous_leaf->GetNextAnchorPosition();
+  return previous_leaf;
+}
+
+AXPosition* AXPosition::GetNextAnchorPosition() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  if (AnchorChildCount())
+    return GetChildPositionAt(0);
+
+  AXPosition* current_position = this;
+  AXPosition* parent_position = GetParentPosition();
+  while (parent_position && !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 && !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 || 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;
+
+  AXPosition* leaf = parent_position->GetChildPositionAt(index_in_parent - 1);
+  while (leaf && !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);
+}
+
+AXNodePosition::AXNodePosition(int tree_id,
+                               int32_t anchor_id,
+                               int child_index,
+                               int text_offset,
+                               AXPositionType type)
+    : AXPosition(tree_id, anchor_id, child_index, text_offset, type) {}
+
+AXNodePosition::~AXNodePosition() {}
+
+AXPosition* AXNodePosition::GetChildPositionAt(int child_index) const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  if (child_index < 0 || child_index >= AnchorChildCount())
+    return CreateNullPosition();
+
+  AXNodeType* child_anchor = GetAnchor()->ChildAtIndex(child_index);
+  DCHECK(child_anchor);
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      NOTREACHED();
+      return CreateNullPosition();
+    case AXPositionType::TreePosition:
+      return CreateTreePosition(tree_id_, child_anchor->id(),
+                                0 /* child_index */);
+    case AXPositionType::TextPosition:
+      return CreateTextPosition(tree_id_, child_anchor->id(),
+                                0 /* text_offset */);
+  }
+}
+
+AXPosition* AXNodePosition::GetParentPosition() const {
+  if (IsNullPosition())
+    return CreateNullPosition();
+
+  AXNodeType* parent_anchor = GetAnchor()->parent();
+  if (!parent_anchor)
+    return CreateNullPosition();
+
+  switch (type_) {
+    case AXPositionType::NullPosition:
+      NOTREACHED();
+      return CreateNullPosition();
+    case AXPositionType::TreePosition:
+      return CreateTreePosition(tree_id_, parent_anchor->id(),
+                                0 /* child_index */);
+    case AXPositionType::TextPosition:
+      return CreateTextPosition(tree_id_, parent_anchor->id(),
+                                0 /* text_offset */);
+  }
+}
+
+}  // namespace ui