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..777f1c761eeb253efa4d6ba02b6834d024dfda76
--- /dev/null
+++ b/ui/accessibility/ax_position.cc
@@ -0,0 +1,198 @@
+// 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_node.h"
+
+#include <algorithm>
+#include <queue>
+
+namespace ui {
+
+AXPosition::AXPosition(AXNode* anchor, int offset, AXPositionType type) : anchor_(anchor), offset_(offset), type_(type) {
+  switch (type_) {
+    case AXPositionType::TreePosition:
+      offset_ = 0;
+      break;
+    case AXPositionType::TextPosition:
+    if (!anchor_ || offset_ < 0 || offset_ > MaxOffset()) {
+      // Reset to the null position.
+      type_ = AXPositionType::TreePosition;
+      anchor_ = nullptr;
+      offset_ = 0;
+    }
+      break;
+  }
+}
+
+AXPosition::~AXPosition() {
+}
+
+AXPosition AXPosition::CreateNullPosition() {
+  return AXPosition(nullptr, 0, AXPositionType::TreePosition);
+}
+
+AXPosition AXPosition::CreateTreePosition(AXNode* anchor) {
+  return AXPosition(anchor, 0, AXPositionType::TreePosition);
+}
+
+AXPosition AXPosition::CreateTextPosition(AXNode* anchor, int offset = 0) {
+  return AXPosition(anchor, offset, AXPositionType::TextPosition);
+}
+
+// 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 (type_ != AXPositionType::TextPosition)
+    return true;
+  return offset_ <= 0;
+}
+
+bool AXPosition::AtEndOfAnchor() const {
+  if (type_ != AXPositionType::TextPosition)
+    return true;
+  return offset_ >= MaxOffset();
+}
+
+bool AXPosition::operator<(const AXPosition& position) const {
+  return false;
+}
+
+bool AXPosition::operator<=(const AXPosition& position) const {
+  return false;
+}
+
+bool AXPosition::operator>(const AXPosition& position) const {
+  return false;
+}
+
+bool AXPosition::operator>=(const AXPosition& position) const {
+  return false;
+}
+
+AXPosition AXPosition::ToLeafTextPosition() const {
+}
+
+AXPosition AXPosition::ToTextPositionInAnchor(AXNode* anchor) const {
+}
+
+AXPosition AXPosition::GetPositionAtStartOfAnchor() const {
+  if (type_ == AXPositionType::TextPosition)
+    offset_ = 0;
+}
+
+AXPosition AXPosition::GetPositionAtEndOfAnchor() const {
+  if (type_ == AXPositionType::TextPosition)
+    offset_ = MaxOffset();
+}
+
+AXPosition AXPosition::GetNextCharacterPosition() const {
+  return CreateTextPosition(anchor_, offset_ + 1);
+}
+
+AXPosition AXPosition::GetPreviousCharacterPosition() const {
+  return CreateTextPosition(anchor_, offset_ - 1);
+}
+
+AXPosition AXPosition::GetNextWordStartPosition() const {
+  int newOffset = std::upper_bound(GetWordStartOffsets(), get_offset());
+  return CreateTextPosition(get_anchor(), newOffset);
+}
+
+AXPosition AXPosition::GetPreviousWordStartPosition() const {
+  int newOffset = std::upper_bound(GetWordStartOffsets(), get_offset() - 1);
+  return CreateTextPosition(get_anchor(), newOffset);
+}
+
+AXPosition AXPosition::GetNextWordEndPosition() const {
+  int newOffset = std::upper_bound(GetWordEndOffsets(), get_offset());
+  return CreateTextPosition(get_anchor(), newOffset);
+}
+
+AXPosition AXPosition::GetPreviousWordEndPosition() const {
+  int newOffset = std::upper_bound(GetWordEndOffsets(), get_offset() - 1);
+  return CreateTextPosition(get_anchor(), newOffset);
+}
+
+AXPosition AXPosition::GetNextSentenceStartPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetPreviousSentenceStartPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetNextSentenceEndPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetPreviousSentenceEndPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetNextParagraphStartPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetPreviousParagraphStartPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetNextParagraphEndPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetPreviousParagraphEndPosition() const {
+  return CreateNullPosition();
+}
+
+AXPosition AXPosition::GetNextAnchorPosition() const {
+  if (AnchorChildCount())
+    return GetChildPositionAt(0);
+
+  for (AXPosition position = *this; !position.IsNullPosition(); position = position.GetParentPosition()) {
+    // Get the next sibling if it exists.
+    AXPosition parentPosition = position.GetParentPosition();
+    int indexInParent = position.AnchorIndexInParent();
+    if (indexInParent < parentPosition.AnchorChildCount() - 1)
+      return parentPosition.GetChildPositionAt(indexInParent + 1);
+  }
+  return CreateNullPosition();
+}
+
+bool operator==(const AXPosition& first, const AXPosition& second) {
+  return false;
+}
+
+bool operator!=(const AXPosition& first, const AXPosition& second) {
+  return false;
+}
+
+}  // namespace ui