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..d815b2c29c62dc07d00a6742af52f3a49e0b394f
--- /dev/null
+++ b/ui/accessibility/ax_position.h
@@ -0,0 +1,382 @@
+// 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 <memory>
+
+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:
+  static int INVALID_TREE_ID;
+  static int INVALID_ANCHOR_ID;
+  static int INVALID_INDEX;
+  static int INVALID_OFFSET;
+
+  AXPosition() {}
+  virtual ~AXPosition() {}
+
+  static AXPosition<AXPositionType, AXNodeType>* CreateNullPosition() {
+    auto new_position = static_cast<AXPosition<AXPositionType, AXNodeType>*>(
+        new AXPositionType());
+    DCHECK(new_position);
+    new_position->Initialize(AXPositionKind::NullPosition, INVALID_TREE_ID,
+                             INVALID_ANCHOR_ID, INVALID_INDEX, INVALID_OFFSET,
+                             AX_TEXT_AFFINITY_UPSTREAM);
+    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(AXPositionKind::TreePosition, tree_id, anchor_id,
+                             child_index, INVALID_OFFSET,
+                             AX_TEXT_AFFINITY_UPSTREAM);
+    return new_position;
+  }
+
+  static AXPosition<AXPositionType, AXNodeType>* CreateTextPosition(
+      int tree_id,
+      int32_t anchor_id,
+      int text_offset,
+      AXTextAffinity affinity) {
+    auto new_position = static_cast<AXPosition<AXPositionType, AXNodeType>*>(
+        new AXPositionType());
+    DCHECK(new_position);
+    new_position->Initialize(AXPositionKind::TextPosition, tree_id, anchor_id,
+                             INVALID_INDEX, text_offset, affinity);
+    return new_position;
+  }
+
+  int tree_id() const { return tree_id_; }
+  int32_t anchor_id() const { return anchor_id_; }
+
+  AXNodeType* GetAnchor() const {
+    if (tree_id_ == INVALID_TREE_ID || anchor_id_ == INVALID_ANCHOR_ID)
+      return nullptr;
+    DCHECK_GE(tree_id_, 0);
+    DCHECK_GE(anchor_id_, 0);
+    return GetNodeInTree(tree_id_, anchor_id_);
+  }
+
+  AXPositionKind kind() const { return kind_; }
+  int child_index() const { return child_index_; }
+  int text_offset() const { return text_offset_; }
+  AXTextAffinity affinity() const { return 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>* CreatePositionAtStartOfAnchor()
+      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 */,
+                                  AX_TEXT_AFFINITY_UPSTREAM);
+    }
+    return CreateNullPosition();
+  }
+
+  AXPosition<AXPositionType, AXNodeType>* CreatePositionAtEndOfAnchor() 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(),
+                                  AX_TEXT_AFFINITY_UPSTREAM);
+    }
+    return CreateNullPosition();
+  }
+
+  AXPosition<AXPositionType, AXNodeType>* CreateChildPositionAt(
+      int child_index) const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (child_index < 0 || child_index >= AnchorChildCount())
+      return CreateNullPosition();
+
+    int32_t child_id = AnchorChildID(child_index);
+    DCHECK_NE(child_id, INVALID_ANCHOR_ID);
+    switch (kind_) {
+      case AXPositionKind::NullPosition:
+        NOTREACHED();
+        return CreateNullPosition();
+      case AXPositionKind::TreePosition:
+        return CreateTreePosition(tree_id_, child_id, 0 /* child_index */);
+      case AXPositionKind::TextPosition:
+        return CreateTextPosition(tree_id_, child_id, 0 /* text_offset */,
+                                  AX_TEXT_AFFINITY_UPSTREAM);
+    }
+
+    return CreateNullPosition();
+  }
+
+  AXPosition<AXPositionType, AXNodeType>* CreateParentPosition() const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    int32_t parent_id = AnchorParentID();
+    if (parent_id == INVALID_ANCHOR_ID)
+      return CreateNullPosition();
+
+    DCHECK_GE(parent_id, 0);
+    switch (kind_) {
+      case AXPositionKind::NullPosition:
+        NOTREACHED();
+        return CreateNullPosition();
+      case AXPositionKind::TreePosition:
+        return CreateTreePosition(tree_id_, parent_id, 0 /* child_index */);
+      case AXPositionKind::TextPosition:
+        return CreateTextPosition(tree_id_, parent_id, 0 /* text_offset */,
+                                  AX_TEXT_AFFINITY_UPSTREAM);
+    }
+
+    return CreateNullPosition();
+  }
+
+  // The following methods work across anchors.
+
+  // TODO(nektar): Not yet implemented for tree positions.
+  AXPosition<AXPositionType, AXNodeType>* CreateNextCharacterPosition() const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (text_offset_ + 1 < MaxTextOffset()) {
+      return CreateTextPosition(tree_id_, anchor_id_, text_offset_ + 1,
+                                AX_TEXT_AFFINITY_UPSTREAM);
+    }
+
+    std::unique_ptr<AXPosition<AXPositionType, AXNodeType>> next_leaf(
+        CreateNextAnchorPosition());
+    while (next_leaf && !next_leaf->IsNullPosition() &&
+           next_leaf->AnchorChildCount()) {
+      next_leaf.reset(next_leaf->CreateNextAnchorPosition());
+    }
+
+    DCHECK(next_leaf);
+    return next_leaf.release();
+  }
+
+  // TODO(nektar): Not yet implemented for tree positions.
+  AXPosition<AXPositionType, AXNodeType>* CreatePreviousCharacterPosition()
+      const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (text_offset_ > 0) {
+      return CreateTextPosition(tree_id_, anchor_id_, text_offset_ - 1,
+                                AX_TEXT_AFFINITY_UPSTREAM);
+    }
+
+    std::unique_ptr<AXPosition<AXPositionType, AXNodeType>> previous_leaf(
+        CreatePreviousAnchorPosition());
+    while (previous_leaf && !previous_leaf->IsNullPosition() &&
+           previous_leaf->AnchorChildCount()) {
+      previous_leaf.reset(previous_leaf->CreatePreviousAnchorPosition());
+    }
+
+    DCHECK(previous_leaf);
+    previous_leaf.reset(previous_leaf->CreatePositionAtEndOfAnchor());
+    if (!previous_leaf->AtStartOfAnchor())
+      --previous_leaf->text_offset_;
+    return previous_leaf.release();
+  }
+
+  // TODO(nektar): Add word, line and paragraph navigation methods.
+
+ protected:
+  virtual void Initialize(AXPositionKind kind,
+                          int tree_id,
+                          int32_t anchor_id,
+                          int child_index,
+                          int text_offset,
+                          AXTextAffinity affinity) {
+    kind_ = kind;
+    tree_id_ = tree_id;
+    anchor_id_ = anchor_id;
+    child_index_ = child_index;
+    text_offset_ = text_offset;
+    affinity_ = affinity;
+
+    if (!GetAnchor() ||
+        (child_index_ != INVALID_INDEX &&
+         (child_index_ < 0 || child_index_ > AnchorChildCount())) ||
+        (text_offset_ != INVALID_OFFSET &&
+         (text_offset_ < 0 || text_offset_ > MaxTextOffset()))) {
+      // reset to the null position.
+      kind_ = AXPositionKind::NullPosition;
+      tree_id_ = INVALID_TREE_ID;
+      anchor_id_ = INVALID_ANCHOR_ID;
+      child_index_ = INVALID_INDEX;
+      text_offset_ = INVALID_OFFSET;
+      affinity_ = AX_TEXT_AFFINITY_UPSTREAM;
+    }
+  }
+
+  // Uses depth-first pre-order traversal.
+  virtual AXPosition<AXPositionType, AXNodeType>* CreateNextAnchorPosition()
+      const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    if (AnchorChildCount())
+      return CreateChildPositionAt(0);
+
+    std::unique_ptr<AXPosition<AXPositionType, AXNodeType>> current_position(
+        CreateTreePosition(tree_id_, anchor_id_, child_index_));
+    std::unique_ptr<AXPosition<AXPositionType, AXNodeType>> parent_position(
+        CreateParentPosition());
+    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->CreateChildPositionAt(index_in_parent + 1);
+        DCHECK(next_sibling && !next_sibling->IsNullPosition());
+        return next_sibling;
+      }
+
+      current_position = std::move(parent_position);
+      parent_position.reset(current_position->CreateParentPosition());
+    }
+
+    return CreateNullPosition();
+  }
+
+  // Uses depth-first pre-order traversal.
+  virtual AXPosition<AXPositionType, AXNodeType>* CreatePreviousAnchorPosition()
+      const {
+    if (IsNullPosition())
+      return CreateNullPosition();
+
+    std::unique_ptr<AXPosition<AXPositionType, AXNodeType>> parent_position(
+        CreateParentPosition());
+    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.release();
+
+    std::unique_ptr<AXPosition<AXPositionType, AXNodeType>> leaf(
+        parent_position->CreateChildPositionAt(index_in_parent - 1));
+    while (leaf && !leaf->IsNullPosition() && leaf->AnchorChildCount())
+      leaf.reset(leaf->CreateChildPositionAt(0));
+
+    return leaf.release();
+  }
+
+  // Abstract methods.
+  virtual int32_t AnchorChildID(int child_index) const = 0;
+  virtual int AnchorChildCount() const = 0;
+  virtual int AnchorIndexInParent() const = 0;
+  virtual int32_t AnchorParentID() 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:
+  AXPositionKind kind_;
+  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_;
+
+  // 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>
+int AXPosition<AXPositionType, AXNodeType>::INVALID_TREE_ID = -1;
+template <class AXPositionType, class AXNodeType>
+int32_t AXPosition<AXPositionType, AXNodeType>::INVALID_ANCHOR_ID = -1;
+template <class AXPositionType, class AXNodeType>
+int AXPosition<AXPositionType, AXNodeType>::INVALID_INDEX = -1;
+template <class AXPositionType, class AXNodeType>
+int AXPosition<AXPositionType, AXNodeType>::INVALID_OFFSET = -1;
+
+}  // namespace ui
+
+#endif  // UI_ACCESSIBILITY_AX_POSITION_H_