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..0eabad365f90acb6ece0b0513c85c2e9c28ad903
--- /dev/null
+++ b/ui/accessibility/ax_position.h
@@ -0,0 +1,383 @@
+// 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.
+  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;
+    }
+
+    // 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()
+      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);
+
+    return leaf;
+  }
+
+  // Abstract methods.
+  virtual AXPosition<AXPositionType, AXNodeType>* GetChildPositionAt(

[dmazzoni, 2016/10/10 20:05:15]

Would it be simpler to have this return the AXNodeType* for a child rather than
a position? It seems like you have some duplicate code between ax_node_position
and ax_platform_position that doesn't seem necessary.

You could implement GetChildPositionAt here as a function of GetChildNodeAt,
which would be abstract.

+      int child_index) const = 0;
+  virtual AXPosition<AXPositionType, AXNodeType>* GetParentPosition() const = 0;
+  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_