ax_tree.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518
  1. // Copyright 2013 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef UI_ACCESSIBILITY_AX_TREE_H_
  5. #define UI_ACCESSIBILITY_AX_TREE_H_
  6. #include <stdint.h>
  7. #include <map>
  8. #include <memory>
  9. #include <set>
  10. #include <string>
  11. #include <vector>
  12. #include "base/containers/flat_map.h"
  13. #include "base/debug/crash_logging.h"
  14. #include "base/memory/raw_ptr.h"
  15. #include "base/metrics/histogram_functions.h"
  16. #include "base/observer_list.h"
  17. #include "third_party/abseil-cpp/absl/types/optional.h"
  18. #include "ui/accessibility/ax_enums.mojom-forward.h"
  19. #include "ui/accessibility/ax_export.h"
  20. #include "ui/accessibility/ax_node.h"
  21. #include "ui/accessibility/ax_node_data.h"
  22. #include "ui/accessibility/ax_tree_data.h"
  23. #include "ui/accessibility/ax_tree_update.h"
  24. namespace ui {
  25. struct AXEvent;
  26. class AXTableInfo;
  27. class AXTreeObserver;
  28. struct AXTreeUpdateState;
  29. class AXLanguageDetectionManager;
  30. // These values are persisted to logs. Entries should not be renumbered and
  31. // numeric values should never be reused.
  32. enum class AXTreeUnserializeError {
  33. // Tree has no root.
  34. kNoRoot = 0,
  35. // Node will not be in the tree and is not the new root.
  36. kNotInTree = 1,
  37. // Node is already pending for creation, cannot be the new root
  38. kCreationPending = 2,
  39. // Node has duplicate child.
  40. kDuplicateChild = 3,
  41. // Node is already pending for creation, cannot be a new child.
  42. kCreationPendingForChild = 4,
  43. // Node is not marked for destruction, would be reparented.
  44. kReparent = 5,
  45. // Nodes are left pending by the update.
  46. kPendingNodes = 6,
  47. // Changes left pending by the update;
  48. kPendingChanges = 7,
  49. // This must always be the last enum. It's okay for its value to
  50. // increase, but none of the other enum values may change.
  51. kMaxValue = kPendingChanges
  52. };
  53. #define ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(enum_value) \
  54. base::UmaHistogramEnumeration( \
  55. "Accessibility.Reliability.Tree.UnserializeError", enum_value)
  56. // AXTree is a live, managed tree of AXNode objects that can receive
  57. // updates from another AXTreeSource via AXTreeUpdates, and it can be
  58. // used as a source for sending updates to another client tree.
  59. // It's designed to be subclassed to implement support for native
  60. // accessibility APIs on a specific platform.
  61. class AX_EXPORT AXTree : public AXNode::OwnerTree {
  62. public:
  63. using IntReverseRelationMap =
  64. std::map<ax::mojom::IntAttribute, std::map<AXNodeID, std::set<AXNodeID>>>;
  65. using IntListReverseRelationMap =
  66. std::map<ax::mojom::IntListAttribute,
  67. std::map<AXNodeID, std::set<AXNodeID>>>;
  68. // If called, the focused node in this tree will never be ignored, even if it
  69. // has the ignored state set. For now, this boolean will be set to false for
  70. // all trees except in test scenarios, in order to thoroughly test the
  71. // relevant code without causing any potential regressions. Ultimately, we
  72. // want to expose all focused nodes so that a user of an assistive technology
  73. // will be able to interact with the application / website, even if there is
  74. // an authoring error, e.g. the aria-hidden attribute has been applied to the
  75. // focused element.
  76. // TODO(nektar): Removed once the feature has been fully tested.
  77. static void SetFocusedNodeShouldNeverBeIgnored();
  78. // Determines the ignored state of a node, given information about the node
  79. // and the tree.
  80. static bool ComputeNodeIsIgnored(const AXTreeData* optional_tree_data,
  81. const AXNodeData& node_data);
  82. // Determines whether a node has flipped its ignored state, given information
  83. // about the previous and current state of the node / tree.
  84. static bool ComputeNodeIsIgnoredChanged(
  85. const AXTreeData* optional_old_tree_data,
  86. const AXNodeData& old_node_data,
  87. const AXTreeData* optional_new_tree_data,
  88. const AXNodeData& new_node_data);
  89. AXTree();
  90. explicit AXTree(const AXTreeUpdate& initial_state);
  91. virtual ~AXTree();
  92. // AXTree owns pointers so copying is non-trivial.
  93. AXTree(const AXTree&) = delete;
  94. AXTree& operator=(const AXTree&) = delete;
  95. void AddObserver(AXTreeObserver* observer);
  96. bool HasObserver(AXTreeObserver* observer);
  97. void RemoveObserver(AXTreeObserver* observer);
  98. base::ObserverList<AXTreeObserver>& observers() { return observers_; }
  99. AXNode* root() const { return root_; }
  100. const AXTreeData& data() const override;
  101. // Destroys the tree and notifies all observers.
  102. void Destroy();
  103. // AXNode::OwnerTree override.
  104. // Returns the globally unique ID of this accessibility tree.
  105. const AXTreeID& GetAXTreeID() const override;
  106. // AXNode::OwnerTree override.
  107. // Returns the AXNode with the given |id| if it is part of this AXTree.
  108. AXNode* GetFromId(AXNodeID id) const override;
  109. // Returns true on success. If it returns false, it's a fatal error
  110. // and this tree should be destroyed, and the source of the tree update
  111. // should not be trusted any longer.
  112. virtual bool Unserialize(const AXTreeUpdate& update);
  113. // Used by tests to update the tree data without changing any of the nodes in
  114. // the tree, notifying all tree observers in the process.
  115. virtual void UpdateDataForTesting(const AXTreeData& data);
  116. // Convert any rectangle from the local coordinate space of one node in
  117. // the tree, to bounds in the coordinate space of the tree.
  118. // If set, updates |offscreen| boolean to be true if the node is offscreen
  119. // relative to its rootWebArea. Callers should initialize |offscreen|
  120. // to false: this method may get called multiple times in a row and
  121. // |offscreen| will be propagated.
  122. // If |clip_bounds| is true, result bounds will be clipped.
  123. gfx::RectF RelativeToTreeBounds(const AXNode* node,
  124. gfx::RectF node_bounds,
  125. bool* offscreen = nullptr,
  126. bool clip_bounds = true,
  127. bool skip_container_offset = false) const;
  128. // Get the bounds of a node in the coordinate space of the tree.
  129. // If set, updates |offscreen| boolean to be true if the node is offscreen
  130. // relative to its rootWebArea. Callers should initialize |offscreen|
  131. // to false: this method may get called multiple times in a row and
  132. // |offscreen| will be propagated.
  133. // If |clip_bounds| is true, result bounds will be clipped.
  134. gfx::RectF GetTreeBounds(const AXNode* node,
  135. bool* offscreen = nullptr,
  136. bool clip_bounds = true) const;
  137. // Given a node ID attribute (one where IsNodeIdIntAttribute is true),
  138. // and a destination node ID, return a set of all source node IDs that
  139. // have that relationship attribute between them and the destination.
  140. std::set<AXNodeID> GetReverseRelations(ax::mojom::IntAttribute attr,
  141. AXNodeID dst_id) const;
  142. // Given a node ID list attribute (one where
  143. // IsNodeIdIntListAttribute is true), and a destination node ID,
  144. // return a set of all source node IDs that have that relationship
  145. // attribute between them and the destination.
  146. std::set<AXNodeID> GetReverseRelations(ax::mojom::IntListAttribute attr,
  147. AXNodeID dst_id) const;
  148. // Given a child tree ID, return the node IDs of all nodes in the tree who
  149. // have a kChildTreeId int attribute with that value.
  150. //
  151. // TODO(accessibility): There should really be only one host node per child
  152. // tree, so the return value should not be a set but a single node ID or
  153. // `kInvalidAXNodeID`.
  154. std::set<AXNodeID> GetNodeIdsForChildTreeId(AXTreeID child_tree_id) const;
  155. // Get all of the child tree IDs referenced by any node in this tree.
  156. const std::set<AXTreeID> GetAllChildTreeIds() const;
  157. // Map from a relation attribute to a map from a target id to source ids.
  158. const IntReverseRelationMap& int_reverse_relations() {
  159. return int_reverse_relations_;
  160. }
  161. const IntListReverseRelationMap& intlist_reverse_relations() {
  162. return intlist_reverse_relations_;
  163. }
  164. // Return a multi-line indented string representation, for logging.
  165. std::string ToString() const;
  166. // A string describing the error from an unsuccessful Unserialize,
  167. // for testing and debugging.
  168. const std::string& error() const { return error_; }
  169. int size() { return static_cast<int>(id_map_.size()); }
  170. // Return a negative number that's suitable to use for a node ID for
  171. // internal nodes created automatically by an AXTree, so as not to
  172. // conflict with positive-numbered node IDs from tree sources.
  173. AXNodeID GetNextNegativeInternalNodeId();
  174. // Returns the PosInSet of |node|. Looks in node_set_size_pos_in_set_info_map_
  175. // for cached value. Calls |ComputeSetSizePosInSetAndCache|if no value is
  176. // present in the cache.
  177. absl::optional<int> GetPosInSet(const AXNode& node) override;
  178. // Returns the SetSize of |node|. Looks in node_set_size_pos_in_set_info_map_
  179. // for cached value. Calls |ComputeSetSizePosInSetAndCache|if no value is
  180. // present in the cache.
  181. absl::optional<int> GetSetSize(const AXNode& node) override;
  182. // Returns the part of the current selection that falls within this
  183. // accessibility tree, if any.
  184. Selection GetSelection() const override;
  185. // Returns the part of the current selection that falls within this
  186. // accessibility tree, if any, adjusting its endpoints to be within unignored
  187. // nodes. (An "ignored" node is a node that is not exposed to platform APIs:
  188. // See `AXNode::IsIgnored`.)
  189. Selection GetUnignoredSelection() const override;
  190. bool GetTreeUpdateInProgressState() const override;
  191. // AXNode::OwnerTree override.
  192. // Returns true if the tree represents a paginated document
  193. bool HasPaginationSupport() const override;
  194. // Language detection manager, entry point to language detection features.
  195. // TODO(chrishall): Should this be stored by pointer or value?
  196. // When should we initialize this?
  197. std::unique_ptr<AXLanguageDetectionManager> language_detection_manager;
  198. // Event metadata while applying a tree update during unserialization.
  199. AXEvent* event_data() const { return event_data_.get(); }
  200. // Notify the delegate that the tree manager for |previous_tree_id| will be
  201. // removed from the AXTreeManagerMap. Because we sometimes remove the tree
  202. // manager after the tree's id has been modified, we need to pass the (old)
  203. // tree id associated with the manager we are removing even though it is the
  204. // same tree.
  205. void NotifyTreeManagerWillBeRemoved(AXTreeID previous_tree_id);
  206. private:
  207. friend class ScopedTreeUpdateInProgressStateSetter;
  208. friend class AXTableInfoTest;
  209. // Indicates if the node with the focus should never be ignored, (see
  210. // `SetFocusedNodeShouldNeverBeIgnored` above).
  211. static bool is_focused_node_always_unignored_;
  212. // Accumulate errors as there can be more than one before Chrome is crashed
  213. // via AccessibilityFatalError();
  214. // In an AX_FAIL_FAST_BUILD, will assert/crash immediately.
  215. void RecordError(const AXTreeUpdateState& update_state,
  216. std::string new_error);
  217. // AXNode::OwnerTree override.
  218. //
  219. // Given a node in this accessibility tree that corresponds to a table
  220. // or grid, return an object containing information about the
  221. // table structure. This object is computed lazily on-demand and
  222. // cached until the next time the tree is updated. Clients should
  223. // not retain this pointer, they should just request it every time
  224. // it's needed.
  225. //
  226. // Returns nullptr if the node is not a valid table.
  227. AXTableInfo* GetTableInfo(const AXNode* table_node) const override;
  228. AXNode* CreateNode(AXNode* parent,
  229. AXNodeID id,
  230. size_t index_in_parent,
  231. AXTreeUpdateState* update_state);
  232. // Accumulates the work that will be required to update the AXTree.
  233. // This allows us to notify observers of structure changes when the
  234. // tree is still in a stable and unchanged state.
  235. bool ComputePendingChanges(const AXTreeUpdate& update,
  236. AXTreeUpdateState* update_state);
  237. // Populates |update_state| with information about actions that will
  238. // be performed on the tree during the update, such as adding or
  239. // removing nodes in the tree. Returns true on success.
  240. // Nothing within this call should modify tree structure or node data.
  241. bool ComputePendingChangesToNode(const AXNodeData& new_data,
  242. bool is_new_root,
  243. AXTreeUpdateState* update_state);
  244. // This is called from within Unserialize(), it returns true on success.
  245. bool UpdateNode(const AXNodeData& src,
  246. bool is_new_root,
  247. AXTreeUpdateState* update_state);
  248. // Notify the delegate that the subtree rooted at |node| will be
  249. // destroyed or reparented.
  250. void NotifySubtreeWillBeReparentedOrDeleted(
  251. AXNode* node,
  252. const AXTreeUpdateState* update_state);
  253. // Notify the delegate that |node| will be destroyed or reparented.
  254. void NotifyNodeWillBeReparentedOrDeleted(
  255. AXNode* node,
  256. const AXTreeUpdateState* update_state);
  257. // Notify the delegate that |node| and all of its descendants will be
  258. // destroyed. This function is called during AXTree teardown.
  259. void RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode* node);
  260. // Notify the delegate that the node marked by |node_id| has been deleted.
  261. // We are passing the node id instead of ax node is because by the time this
  262. // function is called, the ax node in the tree will already have been
  263. // destroyed.
  264. void NotifyNodeHasBeenDeleted(AXNodeID node_id);
  265. // Notify the delegate that |node| has been created or reparented.
  266. void NotifyNodeHasBeenReparentedOrCreated(
  267. AXNode* node,
  268. const AXTreeUpdateState* update_state);
  269. // Notify the delegate that `node` will change its data attributes, including
  270. // its ignored state.
  271. void NotifyNodeAttributesWillChange(AXNode* node,
  272. const AXTreeData* optional_old_tree_data,
  273. const AXNodeData& old_data,
  274. const AXTreeData* new_tree_data,
  275. const AXNodeData& new_data);
  276. // Notify the delegate that `node` has changed its data attributes, including
  277. // its ignored state.
  278. void NotifyNodeAttributesHaveBeenChanged(
  279. AXNode* node,
  280. const AXTreeData* optional_old_tree_data,
  281. const AXNodeData& old_data,
  282. const AXTreeData* new_tree_data,
  283. const AXNodeData& new_data);
  284. void UpdateReverseRelations(AXNode* node, const AXNodeData& new_data);
  285. // Sets a flag indicating whether the tree is currently being updated or not.
  286. // If the tree is being updated, then its internal pointers might be invalid
  287. // and the tree should not be traversed.
  288. void SetTreeUpdateInProgressState(bool set_tree_update_value);
  289. // Returns true if all pending changes in the |update_state| have been
  290. // handled. If this returns false, the |error_| message will be populated.
  291. // It's a fatal error to have pending changes after exhausting
  292. // the AXTreeUpdate.
  293. bool ValidatePendingChangesComplete(const AXTreeUpdateState& update_state);
  294. // Modifies |update_state| so that it knows what subtree and nodes are
  295. // going to be destroyed for the subtree rooted at |node|.
  296. void MarkSubtreeForDestruction(AXNodeID node_id,
  297. AXTreeUpdateState* update_state);
  298. // Modifies |update_state| so that it knows what nodes are
  299. // going to be destroyed for the subtree rooted at |node|.
  300. void MarkNodesForDestructionRecursive(AXNodeID node_id,
  301. AXTreeUpdateState* update_state);
  302. // Validates that destroying the subtree rooted at |node| has required
  303. // information in |update_state|, then calls DestroyNodeAndSubtree on it.
  304. void DestroySubtree(AXNode* node, AXTreeUpdateState* update_state);
  305. // Call Destroy() on |node|, and delete it from the id map, and then
  306. // call recursively on all nodes in its subtree.
  307. void DestroyNodeAndSubtree(AXNode* node, AXTreeUpdateState* update_state);
  308. // Iterate over the children of |node| and for each child, destroy the
  309. // child and its subtree if its id is not in |new_child_ids|.
  310. void DeleteOldChildren(AXNode* node,
  311. const std::vector<AXNodeID>& new_child_ids,
  312. AXTreeUpdateState* update_state);
  313. // Iterate over |new_child_ids| and populate |new_children| with
  314. // pointers to child nodes, reusing existing nodes already in the tree
  315. // if they exist, and creating otherwise. Reparenting is disallowed, so
  316. // if the id already exists as the child of another node, that's an
  317. // error. Returns true on success, false on fatal error.
  318. bool CreateNewChildVector(AXNode* node,
  319. const std::vector<AXNodeID>& new_child_ids,
  320. std::vector<AXNode*>* new_children,
  321. AXTreeUpdateState* update_state);
  322. // Returns the lowest unignored ancestor of the node with the given ID. If the
  323. // node is not ignored, it returns the node.
  324. AXNode* GetUnignoredAncestorFromId(AXNodeID node_id) const;
  325. // Internal implementation of RelativeToTreeBounds. It calls itself
  326. // recursively but ensures that it can only do so exactly once!
  327. gfx::RectF RelativeToTreeBoundsInternal(const AXNode* node,
  328. gfx::RectF node_bounds,
  329. bool* offscreen,
  330. bool clip_bounds,
  331. bool skip_container_offset,
  332. bool allow_recursion) const;
  333. base::ObserverList<AXTreeObserver> observers_;
  334. raw_ptr<AXNode> root_ = nullptr;
  335. std::string error_;
  336. AXTreeData data_;
  337. base::flat_map<AXNodeID, std::unique_ptr<AXNode>> id_map_;
  338. // Map from an int attribute (if IsNodeIdIntAttribute is true) to
  339. // a reverse mapping from target nodes to source nodes.
  340. IntReverseRelationMap int_reverse_relations_;
  341. // Map from an int list attribute (if IsNodeIdIntListAttribute is true) to
  342. // a reverse mapping from target nodes to source nodes.
  343. IntListReverseRelationMap intlist_reverse_relations_;
  344. // Map from child tree ID to the set of node IDs that contain that attribute.
  345. std::map<AXTreeID, std::set<AXNodeID>> child_tree_id_reverse_map_;
  346. // Map from node ID to cached table info, if the given node is a table.
  347. // Invalidated every time the tree is updated.
  348. mutable base::flat_map<AXNodeID, std::unique_ptr<AXTableInfo>>
  349. table_info_map_;
  350. // The next negative node ID to use for internal nodes.
  351. AXNodeID next_negative_internal_node_id_ = -1;
  352. // Contains pos_in_set and set_size data for an AXNode.
  353. struct NodeSetSizePosInSetInfo {
  354. NodeSetSizePosInSetInfo();
  355. ~NodeSetSizePosInSetInfo();
  356. absl::optional<int> pos_in_set;
  357. absl::optional<int> set_size;
  358. absl::optional<int> lowest_hierarchical_level;
  359. };
  360. // Represents the content of an ordered set which includes the ordered set
  361. // items and the ordered set container if it exists.
  362. struct OrderedSetContent;
  363. // Maps a particular hierarchical level to a list of OrderedSetContents.
  364. // Represents all ordered set items/container on a particular hierarchical
  365. // level.
  366. struct OrderedSetItemsMap;
  367. // Populates |items_map_to_be_populated| with all items associated with
  368. // |original_node| and within |ordered_set|. Only items whose roles match the
  369. // role of the |ordered_set| will be added.
  370. void PopulateOrderedSetItemsMap(
  371. const AXNode& original_node,
  372. const AXNode* ordered_set,
  373. OrderedSetItemsMap* items_map_to_be_populated) const;
  374. // Helper function for recursively populating ordered sets items map with
  375. // all items associated with |original_node| and |ordered_set|. |local_parent|
  376. // tracks the recursively passed in child nodes of |ordered_set|.
  377. void RecursivelyPopulateOrderedSetItemsMap(
  378. const AXNode& original_node,
  379. const AXNode* ordered_set,
  380. const AXNode* local_parent,
  381. absl::optional<int> ordered_set_min_level,
  382. absl::optional<int> prev_level,
  383. OrderedSetItemsMap* items_map_to_be_populated) const;
  384. // Computes the pos_in_set and set_size values of all items in ordered_set and
  385. // caches those values. Called by GetPosInSet and GetSetSize.
  386. void ComputeSetSizePosInSetAndCache(const AXNode& node,
  387. const AXNode* ordered_set);
  388. // Helper for ComputeSetSizePosInSetAndCache. Computes and caches the
  389. // pos_in_set and set_size values for a given OrderedSetContent.
  390. void ComputeSetSizePosInSetAndCacheHelper(
  391. const OrderedSetContent& ordered_set_content);
  392. // Map from node ID to OrderedSetInfo.
  393. // Item-like and ordered-set-like objects will map to populated OrderedSetInfo
  394. // objects.
  395. // All other objects will map to default-constructed OrderedSetInfo objects.
  396. // Invalidated every time the tree is updated.
  397. mutable base::flat_map<AXNodeID, NodeSetSizePosInSetInfo>
  398. node_set_size_pos_in_set_info_map_;
  399. // Indicates if the tree is updating.
  400. bool tree_update_in_progress_ = false;
  401. // Indicates if the tree represents a paginated document
  402. bool has_pagination_support_ = false;
  403. std::unique_ptr<AXEvent> event_data_;
  404. };
  405. // Sets the flag that indicates whether the accessibility tree is currently
  406. // being updated, and ensures that it is reset to its previous value when the
  407. // instance is destructed. An accessibility tree that is being updated is
  408. // unstable and should not be traversed.
  409. class AX_EXPORT ScopedTreeUpdateInProgressStateSetter {
  410. public:
  411. explicit ScopedTreeUpdateInProgressStateSetter(AXTree& tree)
  412. : tree_(&tree),
  413. last_tree_update_in_progress_(tree.GetTreeUpdateInProgressState()) {
  414. tree_->SetTreeUpdateInProgressState(true);
  415. }
  416. ~ScopedTreeUpdateInProgressStateSetter() {
  417. tree_->SetTreeUpdateInProgressState(last_tree_update_in_progress_);
  418. }
  419. ScopedTreeUpdateInProgressStateSetter(
  420. const ScopedTreeUpdateInProgressStateSetter&) = delete;
  421. ScopedTreeUpdateInProgressStateSetter& operator=(
  422. const ScopedTreeUpdateInProgressStateSetter&) = delete;
  423. private:
  424. const raw_ptr<AXTree> tree_;
  425. bool last_tree_update_in_progress_;
  426. };
  427. } // namespace ui
  428. #endif // UI_ACCESSIBILITY_AX_TREE_H_