Creates AXPosition to uniquely identify a position in the accessibility tree

ui/accessibility/ax_position.h

Index: ui/accessibility/ax_position.h
diff --git a/ui/accessibility/ax_position.h b/ui/accessibility/ax_position.h
new file mode 100644
index 0000000000000000000000000000000000000000..8abcd27e44e509e2d9fc10d64ecf6d4d5fe4587b
--- /dev/null
+++ b/ui/accessibility/ax_position.h
@@ -0,0 +1,384 @@
+// 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.
+
+#ifndef UI_ACCESSIBILITY_AX_POSITION_H_
+#define UI_ACCESSIBILITY_AX_POSITION_H_
+
+#include <stdint.h>
+
+#include <queue>
+
+#include "ui/accessibility/ax_enums.h"
+#include "ui/accessibility/ax_export.h"
+
+namespace ui {
+
+// Defines the type of position in the accessibility tree.
+// A tree position is used when referring to a specific child of a node in the
+// accessibility tree.
+// A text position is used when referring to a specific character of text inside
+// a particular node.
+// A null position is used to signify that the provided data is invalid or that
+// a boundary has been reached.
+enum class AXPositionKind { NullPosition, TreePosition, TextPosition };
+
+// A position in the |AXTree|.
+// It could either indicate a non-textual node in the accessibility tree, or a
+// text node and a character offset.
+// A text node has either a role of static_text, inline_text_box or line_break.
+//
+// This class template uses static polymorphism in order to allow sub-classes to
+// be created from the base class without the base class knowing the type of the
+// sub-class in advance.
+// The template argument |AXPositionType| should always be set to the type of
+// any class that inherits from this template, making this a
+// "curiously recursive template".
+template <class AXPositionType, class AXNodeType>
+class AXPosition {
+ public:
+  AXPosition() {}
+  virtual ~AXPosition() {}
+
+  static AXPosition<AXPositionType, AXNodeType>* CreateNullPosition() {
+    auto new_position = static_cast<AXPosition<AXPositionType, AXNodeType>*>(
+        new AXPositionType());
+    DCHECK(new_position);
+    new_position->Initialize(-1 /* tree_id */, -1 /* anchor_id */,
+                             -1 /* child_index */, -1 /* text_offset */,
+                             AXPositionKind::NullPosition);
+    return new_position;
+  }
+
+  static AXPosition<AXPositionType, AXNodeType>*
+  CreateTreePosition(int tree_id, int32_t anchor_id, int child_index) {
+    auto new_position = static_cast<AXPosition<AXPositionType, AXNodeType>*>(
+        new AXPositionType());
+    DCHECK(new_position);
+    new_position->Initialize(tree_id, anchor_id, child_index,
+                             -1 /* text_offset */,
+                             AXPositionKind::TreePosition);
+    return new_position;
+  }
+
+  static AXPosition<AXPositionType, AXNodeType>*
+  CreateTextPosition(int tree_id, int32_t anchor_id, int text_offset) {
+    auto new_position = static_cast<AXPosition<AXPositionType, AXNodeType>*>(
+        new AXPositionType());
+    DCHECK(new_position);
+    new_position->Initialize(tree_id, anchor_id, -1 /* child_index */,
+                             text_offset, AXPositionKind::TextPosition);
+    return new_position;
+  }
+
+  int get_tree_id() const { return tree_id_; }
+  int32_t get_anchor_id() const { return anchor_id_; }
+
+  AXNodeType* 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_);
+  }
+
+  int get_child_index() const { return child_index_; }
+  int get_text_offset() const { return text_offset_; }
+  AXPositionKind get_kind() const { return kind_; }
+  ui::AXTextAffinity get_affinity() const { return affinity_; }
+  void set_affinity(ui::AXTextAffinity affinity) { affinity_ = affinity; }
+
+  bool IsNullPosition() const {
+    return kind_ == AXPositionKind::NullPosition || !GetAnchor();
+  }
+  bool IsTreePosition() const {
+    return GetAnchor() && kind_ == AXPositionKind::TreePosition;
+  }
+  bool IsTextPosition() const {
+    return GetAnchor() && kind_ == AXPositionKind::TextPosition;
+  }
+
+  bool AtStartOfAnchor() const {
+    if (!GetAnchor())
+      return false;
+
+    switch (kind_) {
+      case AXPositionKind::NullPosition:
+        return false;
+      case AXPositionKind::TreePosition:
+        return child_index_ == 0;
+      case AXPositionKind::TextPosition:
+        return text_offset_ == 0;
+    }
+
+    return false;
+  }
+
+  bool AtEndOfAnchor() const {
+    if (!GetAnchor())
+      return false;
+
+    switch (kind_) {
+      case AXPositionKind::NullPosition:
+        return false;
+      case AXPositionKind::TreePosition:
+        return child_index_ == AnchorChildCount();
+      case AXPositionKind::TextPosition:
+        return text_offset_ == MaxTextOffset();
+    }
+
+    return false;
+  }
+
+  AXPosition<AXPositionType, AXNodeType>* CommonAncestor(
+      const AXPosition<AXPositionType, AXNodeType>& second) const {
+    std::queue<const AXPosition<AXPositionType, AXNodeType>*> ancestors1;
+    ancestors1.push(this);
+    while (!ancestors1.back() || !ancestors1.back()->IsNullPosition())
+      ancestors1.push(ancestors1.back()->GetParentPosition());
+    ancestors1.pop();
+    if (ancestors1.empty())
+      return CreateNullPosition();
+
+    std::queue<const AXPosition<AXPositionType, AXNodeType>*> ancestors2;
+    ancestors2.push(&second);
+    while (!ancestors2.back() || !ancestors2.back()->IsNullPosition())
+      ancestors2.push(ancestors2.back()->GetParentPosition());
+    ancestors2.pop();
+    if (ancestors2.empty())
+      return CreateNullPosition();
+
+    const AXPosition<AXPositionType, AXNodeType>* commonAncestor =
+        CreateNullPosition();
+    do {
+      if (*ancestors1.front() == *ancestors2.front()) {
+        commonAncestor = ancestors1.front();
+        ancestors1.pop();
+        ancestors2.pop();
+      } else {
+        break;
+      }
+    } while (!ancestors1.empty() && !ancestors2.empty());
+    return const_cast<AXPosition<AXPositionType, AXNodeType>*>(commonAncestor);
+  }
+
+  bool operator<(const AXPosition<AXPositionType, AXNodeType>& position) const {
+    if (IsNullPosition() || position.IsNullPosition())
+      return false;
+
+    const AXPosition<AXPositionType, AXNodeType>* other = &position;
+    do {
+      other = other->GetPreviousAnchorPosition();
+      if (!other || other->IsNullPosition())
+        return false;
+    } while (*this != *other);
+    return true;
+  }
+
+  bool operator<=(
+      const AXPosition<AXPositionType, AXNodeType>& position) const {
+    if (IsNullPosition() || position.IsNullPosition())
+      return false;
+    return *this == position || *this < position;
+  }
+
+  bool operator>(const AXPosition<AXPositionType, AXNodeType>& position) const {
+    if (IsNullPosition() || position.IsNullPosition())
+      return false;
+
+    const AXPosition<AXPositionType, AXNodeType>* other = &position;
+    do {
+      other = other->GetNextAnchorPosition();
+      if (!other || other->IsNullPosition())
+        return false;
+    } while (*this != *other);
+    return true;
+  }
+
+  bool operator>=(
+      const AXPosition<AXPositionType, AXNodeType>& position) const {
+    if (IsNullPosition() || position.IsNullPosition())
+      return false;
+    return *this == position || *this > position;
+  }
+
+  AXPosition<AXPositionType, AXNodeType>* GetPositionAtStartOfAnchor() const {
+    switch (kind_) {
+      case AXPositionKind::NullPosition:
+        return CreateNullPosition();
+      case AXPositionKind::TreePosition:
+        return CreateTreePosition(tree_id_, anchor_id_, 0 /* child_index */);
+      case AXPositionKind::TextPosition:
+        return CreateTextPosition(tree_id_, anchor_id_, 0 /* text_offset */);
+    }
+    return CreateNullPosition();
+  }
+
+  AXPosition<AXPositionType, AXNodeType>* GetPositionAtEndOfAnchor() const {
+    switch (kind_) {
+      case AXPositionKind::NullPosition:
+        return CreateNullPosition();
+      case AXPositionKind::TreePosition:
+        return CreateTreePosition(tree_id_, anchor_id_, AnchorChildCount());
+      case AXPositionKind::TextPosition:
+        return CreateTextPosition(tree_id_, anchor_id_, MaxTextOffset());
+    }
+    return CreateNullPosition();
+  }
+
+  // The following methods work across anchors.
+
+  // TODO(nektar): Not yet implemented for tree positions.

[dmazzoni, 2016/10/12 20:45:41]

As you walk the tree won't you go between tree positions
and text positions? It seems like this class needs another
virtual method that returns whether or not a node is a
text node or not.

+  AXPosition<AXPositionType, AXNodeType>* GetNextCharacterPosition() const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (text_offset_ + 1 < MaxTextOffset())
+      return CreateTextPosition(tree_id_, anchor_id_, text_offset_ + 1);
+
+    AXPosition<AXPositionType, AXNodeType>* next_leaf = GetNextAnchorPosition();
+    while (next_leaf && next_leaf->AnchorChildCount())
+      next_leaf = next_leaf->GetNextAnchorPosition();
+    return next_leaf;
+  }
+
+  // TODO(nektar): Not yet implemented for tree positions.
+  AXPosition<AXPositionType, AXNodeType>* GetPreviousCharacterPosition() const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (text_offset_ > 0)
+      return CreateTextPosition(tree_id_, anchor_id_, text_offset_ - 1);
+
+    AXPosition<AXPositionType, AXNodeType>* previous_leaf =
+        GetPreviousAnchorPosition();
+    while (previous_leaf && previous_leaf->AnchorChildCount())
+      previous_leaf = previous_leaf->GetNextAnchorPosition();
+    return previous_leaf;
+  }
+
+  // TODO(nektar): Add word, line and paragraph navigation methods.
+
+ protected:
+  virtual void Initialize(int tree_id,
+                          int32_t anchor_id,
+                          int child_index,
+                          int text_offset,
+                          AXPositionKind kind) {
+    if (GetAnchor() && child_index >= 0 && child_index <= AnchorChildCount() &&
+        text_offset >= 0 && text_offset <= MaxTextOffset()) {
+      tree_id_ = tree_id;
+      anchor_id_ = anchor_id;
+      child_index_ = child_index;
+      text_offset_ = text_offset;
+      kind_ = kind;
+      return;
+    }
+
+    // Reset to the null position.
+    tree_id_ = -1;
+    anchor_id_ = -1;
+    child_index_ = -1;
+    text_offset_ = -1;
+    kind_ = AXPositionKind::NullPosition;
+  }
+
+  // Uses depth-first pre-order traversal.
+  virtual AXPosition<AXPositionType, AXNodeType>* GetNextAnchorPosition()
+      const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (AnchorChildCount())
+      return GetChildPositionAt(0);
+
+    const AXPosition<AXPositionType, AXNodeType>* current_position = this;
+    const AXPosition<AXPositionType, AXNodeType>* 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<AXPositionType, AXNodeType>* 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();
+  }
+
+  // Uses depth-first pre-order traversal.
+  virtual AXPosition<AXPositionType, AXNodeType>* GetPreviousAnchorPosition()

[dmazzoni, 2016/10/12 20:45:41]

Shouldn't this return the end of the previous anchor? I don't see where it does
that.

+      const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    AXPosition<AXPositionType, AXNodeType>* 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<AXPositionType, AXNodeType>* leaf =
+        parent_position->GetChildPositionAt(index_in_parent - 1);
+    while (leaf && !leaf->IsNullPosition() && leaf->AnchorChildCount())
+      leaf->GetChildPositionAt(0);

[dmazzoni, 2016/10/12 20:45:41]

It doesn't look like you're doing anything with the return value here,
this could loop forever

+
+    return leaf;
+  }
+
+  // Abstract methods.
+  virtual AXPosition<AXPositionType, AXNodeType>* GetChildPositionAt(

[dmazzoni, 2016/10/12 20:45:41]

As I said in a previous comment, I think it would be better
to have this be GetChildAt() and return an AXNodeType, because then
you could implement GetChildPositionAt in terms of that and not
need to duplicate all of the logic in two subclasses.

+      int child_index) const = 0;
+  virtual AXPosition<AXPositionType, AXNodeType>* GetParentPosition() const = 0;

[dmazzoni, 2016/10/12 20:45:41]

Same, this should return an AXNodeType.

+  virtual int AnchorChildCount() const = 0;
+  virtual int AnchorIndexInParent() const = 0;
+  virtual AXNodeType* GetNodeInTree(int tree_id, int32_t node_id) const = 0;
+  // Returns the length of the text that is present inside the anchor node,
+  // including any text found on descendant nodes.
+  virtual int MaxTextOffset() const = 0;
+
+ private:
+  int tree_id_;
+  int32_t anchor_id_;
+
+  // For text positions, |child_index_| is initially set to |-1| and only
+  // computed on demand. The same with tree positions and |text_offset_|.
+  int child_index_;
+  int text_offset_;
+
+  AXPositionKind kind_;
+
+  // TODO(nektar): Get rid of affinity and make Blink handle affinity
+  // internally since inline text objects don't span lines.
+  ui::AXTextAffinity affinity_;
+};
+
+template <class AXPositionType, class AXNodeType>
+bool operator==(const AXPosition<AXPositionType, AXNodeType>& first,
+                const AXPosition<AXPositionType, AXNodeType>& second) {
+  if (first.IsNullPosition() && second.IsNullPosition())
+    return true;
+  return first == second;
+}
+
+template <class AXPositionType, class AXNodeType>
+bool operator!=(const AXPosition<AXPositionType, AXNodeType>& first,
+                const AXPosition<AXPositionType, AXNodeType>& second) {
+  return !operator==(first, second);
+}
+
+}  // namespace ui
+
+#endif  // UI_ACCESSIBILITY_AX_POSITION_H_