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 5 #ifndef UI_ACCESSIBILITY_AX_TREE_H_ 6 #define UI_ACCESSIBILITY_AX_TREE_H_ 7 8 #include <stdint.h> 9 10 #include <map> 11 #include <memory> 12 #include <set> 13 #include <string> 14 #include <unordered_map> 15 #include <vector> 16 17 #include "base/observer_list.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 25 namespace ui { 26 27 class AXTableInfo; 28 class AXTreeObserver; 29 struct AXTreeUpdateState; 30 class AXLanguageDetectionManager; 31 32 // AXTree is a live, managed tree of AXNode objects that can receive 33 // updates from another AXTreeSource via AXTreeUpdates, and it can be 34 // used as a source for sending updates to another client tree. 35 // It's designed to be subclassed to implement support for native 36 // accessibility APIs on a specific platform. 37 class AX_EXPORT AXTree : public AXNode::OwnerTree { 38 public: 39 using IntReverseRelationMap = 40 std::map<ax::mojom::IntAttribute, std::map<int32_t, std::set<int32_t>>>; 41 using IntListReverseRelationMap = 42 std::map<ax::mojom::IntListAttribute, 43 std::map<int32_t, std::set<int32_t>>>; 44 45 AXTree(); 46 explicit AXTree(const AXTreeUpdate& initial_state); 47 virtual ~AXTree(); 48 49 // AXTree owns pointers so copying is non-trivial. 50 AXTree(const AXTree&) = delete; 51 AXTree& operator=(const AXTree&) = delete; 52 53 void AddObserver(AXTreeObserver* observer); 54 bool HasObserver(AXTreeObserver* observer); 55 void RemoveObserver(AXTreeObserver* observer); 56 observers()57 base::ObserverList<AXTreeObserver>& observers() { return observers_; } 58 root()59 AXNode* root() const { return root_; } 60 data()61 const AXTreeData& data() const { return data_; } 62 63 // Destroys the tree and notifies all observers. 64 void Destroy(); 65 66 // AXNode::OwnerTree override. 67 // Returns the globally unique ID of this accessibility tree. 68 AXTreeID GetAXTreeID() const override; 69 70 // AXNode::OwnerTree override. 71 // Returns the AXNode with the given |id| if it is part of this AXTree. 72 AXNode* GetFromId(int32_t id) const override; 73 74 // Returns true on success. If it returns false, it's a fatal error 75 // and this tree should be destroyed, and the source of the tree update 76 // should not be trusted any longer. 77 virtual bool Unserialize(const AXTreeUpdate& update); 78 79 virtual void UpdateData(const AXTreeData& data); 80 81 // Convert any rectangle from the local coordinate space of one node in 82 // the tree, to bounds in the coordinate space of the tree. 83 // If set, updates |offscreen| boolean to be true if the node is offscreen 84 // relative to its rootWebArea. Callers should initialize |offscreen| 85 // to false: this method may get called multiple times in a row and 86 // |offscreen| will be propagated. 87 // If |clip_bounds| is true, result bounds will be clipped. 88 gfx::RectF RelativeToTreeBounds(const AXNode* node, 89 gfx::RectF node_bounds, 90 bool* offscreen = nullptr, 91 bool clip_bounds = true) const; 92 93 // Get the bounds of a node in the coordinate space of the tree. 94 // If set, updates |offscreen| boolean to be true if the node is offscreen 95 // relative to its rootWebArea. Callers should initialize |offscreen| 96 // to false: this method may get called multiple times in a row and 97 // |offscreen| will be propagated. 98 // If |clip_bounds| is true, result bounds will be clipped. 99 gfx::RectF GetTreeBounds(const AXNode* node, 100 bool* offscreen = nullptr, 101 bool clip_bounds = true) const; 102 103 // Given a node ID attribute (one where IsNodeIdIntAttribute is true), 104 // and a destination node ID, return a set of all source node IDs that 105 // have that relationship attribute between them and the destination. 106 std::set<int32_t> GetReverseRelations(ax::mojom::IntAttribute attr, 107 int32_t dst_id) const; 108 109 // Given a node ID list attribute (one where 110 // IsNodeIdIntListAttribute is true), and a destination node ID, 111 // return a set of all source node IDs that have that relationship 112 // attribute between them and the destination. 113 std::set<int32_t> GetReverseRelations(ax::mojom::IntListAttribute attr, 114 int32_t dst_id) const; 115 116 // Given a child tree ID, return the node IDs of all nodes in the tree who 117 // have a kChildTreeId int attribute with that value. 118 std::set<int32_t> GetNodeIdsForChildTreeId(AXTreeID child_tree_id) const; 119 120 // Get all of the child tree IDs referenced by any node in this tree. 121 const std::set<AXTreeID> GetAllChildTreeIds() const; 122 123 // Map from a relation attribute to a map from a target id to source ids. int_reverse_relations()124 const IntReverseRelationMap& int_reverse_relations() { 125 return int_reverse_relations_; 126 } intlist_reverse_relations()127 const IntListReverseRelationMap& intlist_reverse_relations() { 128 return intlist_reverse_relations_; 129 } 130 131 // Return a multi-line indented string representation, for logging. 132 std::string ToString() const; 133 134 // A string describing the error from an unsuccessful Unserialize, 135 // for testing and debugging. error()136 const std::string& error() const { return error_; } 137 size()138 int size() { return static_cast<int>(id_map_.size()); } 139 140 // Call this to enable support for extra Mac nodes - for each table, 141 // a table column header and a node for each column. 142 void SetEnableExtraMacNodes(bool enabled); enable_extra_mac_nodes()143 bool enable_extra_mac_nodes() const { return enable_extra_mac_nodes_; } 144 145 // Return a negative number that's suitable to use for a node ID for 146 // internal nodes created automatically by an AXTree, so as not to 147 // conflict with positive-numbered node IDs from tree sources. 148 int32_t GetNextNegativeInternalNodeId(); 149 150 // Returns the pos_in_set of node. Looks in node_set_size_pos_in_set_info_map_ 151 // for cached value. Calculates pos_in_set and set_size for node (and all 152 // other nodes in the same ordered set) if no value is present in the cache. 153 // This function is guaranteed to be only called on nodes that can hold 154 // pos_in_set values, minimizing the size of the cache. 155 int32_t GetPosInSet(const AXNode& node, const AXNode* ordered_set) override; 156 // Returns the set_size of node. Looks in node_set_size_pos_in_set_info_map_ 157 // for cached value. Calculates pos_inset_set and set_size for node (and all 158 // other nodes in the same ordered set) if no value is present in the cache. 159 // This function is guaranteed to be only called on nodes that can hold 160 // set_size values, minimizing the size of the cache. 161 int32_t GetSetSize(const AXNode& node, const AXNode* ordered_set) override; 162 163 Selection GetUnignoredSelection() const override; 164 165 bool GetTreeUpdateInProgressState() const override; 166 void SetTreeUpdateInProgressState(bool set_tree_update_value); 167 168 // AXNode::OwnerTree override. 169 // Returns true if the tree represents a paginated document 170 bool HasPaginationSupport() const override; 171 172 // Language detection manager, entry point to language detection features. 173 // TODO(chrishall): Should this be stored by pointer or value? 174 // When should we initialize this? 175 std::unique_ptr<AXLanguageDetectionManager> language_detection_manager; 176 177 private: 178 friend class AXTableInfoTest; 179 180 // AXNode::OwnerTree override. 181 // 182 // Given a node in this accessibility tree that corresponds to a table 183 // or grid, return an object containing information about the 184 // table structure. This object is computed lazily on-demand and 185 // cached until the next time the tree is updated. Clients should 186 // not retain this pointer, they should just request it every time 187 // it's needed. 188 // 189 // Returns nullptr if the node is not a valid table. 190 AXTableInfo* GetTableInfo(const AXNode* table_node) const override; 191 192 AXNode* CreateNode(AXNode* parent, 193 AXNode::AXID id, 194 size_t index_in_parent, 195 AXTreeUpdateState* update_state); 196 197 // Accumulates the work that will be required to update the AXTree. 198 // This allows us to notify observers of structure changes when the 199 // tree is still in a stable and unchanged state. 200 bool ComputePendingChanges(const AXTreeUpdate& update, 201 AXTreeUpdateState* update_state); 202 203 // Populates |update_state| with information about actions that will 204 // be performed on the tree during the update, such as adding or 205 // removing nodes in the tree. Returns true on success. 206 // Nothing within this call should modify tree structure or node data. 207 bool ComputePendingChangesToNode(const AXNodeData& new_data, 208 bool is_new_root, 209 AXTreeUpdateState* update_state); 210 211 // This is called from within Unserialize(), it returns true on success. 212 bool UpdateNode(const AXNodeData& src, 213 bool is_new_root, 214 AXTreeUpdateState* update_state); 215 216 // Notify the delegate that the subtree rooted at |node| will be 217 // destroyed or reparented. 218 void NotifySubtreeWillBeReparentedOrDeleted( 219 AXNode* node, 220 const AXTreeUpdateState* update_state); 221 222 // Notify the delegate that |node| will be destroyed or reparented. 223 void NotifyNodeWillBeReparentedOrDeleted( 224 AXNode* node, 225 const AXTreeUpdateState* update_state); 226 227 // Notify the delegate that |node| and all of its descendants will be 228 // destroyed. This function is called during AXTree teardown. 229 void RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode* node); 230 231 // Notify the delegate that the node marked by |node_id| has been deleted. 232 // We are passing the node id instead of ax node is because by the time this 233 // function is called, the ax node in the tree will already have been 234 // destroyed. 235 void NotifyNodeHasBeenDeleted(AXNode::AXID node_id); 236 237 // Notify the delegate that |node| has been created or reparented. 238 void NotifyNodeHasBeenReparentedOrCreated( 239 AXNode* node, 240 const AXTreeUpdateState* update_state); 241 242 // Notify the delegate that a node will change its data. 243 void NotifyNodeDataWillChange(const AXNodeData& old_data, 244 const AXNodeData& new_data); 245 246 // Notify the delegate that |node| has changed its data. 247 void NotifyNodeDataHasBeenChanged(AXNode* node, 248 const AXNodeData& old_data, 249 const AXNodeData& new_data); 250 251 void UpdateReverseRelations(AXNode* node, const AXNodeData& new_data); 252 253 // Returns true if all pending changes in the |update_state| have been 254 // handled. If this returns false, the |error_| message will be populated. 255 // It's a fatal error to have pending changes after exhausting 256 // the AXTreeUpdate. 257 bool ValidatePendingChangesComplete(const AXTreeUpdateState& update_state); 258 259 // Modifies |update_state| so that it knows what subtree and nodes are 260 // going to be destroyed for the subtree rooted at |node|. 261 void MarkSubtreeForDestruction(AXNode::AXID node_id, 262 AXTreeUpdateState* update_state); 263 264 // Modifies |update_state| so that it knows what nodes are 265 // going to be destroyed for the subtree rooted at |node|. 266 void MarkNodesForDestructionRecursive(AXNode::AXID node_id, 267 AXTreeUpdateState* update_state); 268 269 // Validates that destroying the subtree rooted at |node| has required 270 // information in |update_state|, then calls DestroyNodeAndSubtree on it. 271 void DestroySubtree(AXNode* node, AXTreeUpdateState* update_state); 272 273 // Call Destroy() on |node|, and delete it from the id map, and then 274 // call recursively on all nodes in its subtree. 275 void DestroyNodeAndSubtree(AXNode* node, AXTreeUpdateState* update_state); 276 277 // Iterate over the children of |node| and for each child, destroy the 278 // child and its subtree if its id is not in |new_child_ids|. 279 void DeleteOldChildren(AXNode* node, 280 const std::vector<int32_t>& new_child_ids, 281 AXTreeUpdateState* update_state); 282 283 // Iterate over |new_child_ids| and populate |new_children| with 284 // pointers to child nodes, reusing existing nodes already in the tree 285 // if they exist, and creating otherwise. Reparenting is disallowed, so 286 // if the id already exists as the child of another node, that's an 287 // error. Returns true on success, false on fatal error. 288 bool CreateNewChildVector(AXNode* node, 289 const std::vector<int32_t>& new_child_ids, 290 std::vector<AXNode*>* new_children, 291 AXTreeUpdateState* update_state); 292 293 // Internal implementation of RelativeToTreeBounds. It calls itself 294 // recursively but ensures that it can only do so exactly once! 295 gfx::RectF RelativeToTreeBoundsInternal(const AXNode* node, 296 gfx::RectF node_bounds, 297 bool* offscreen, 298 bool clip_bounds, 299 bool allow_recursion) const; 300 301 base::ObserverList<AXTreeObserver> observers_; 302 AXNode* root_ = nullptr; 303 std::unordered_map<int32_t, AXNode*> id_map_; 304 std::string error_; 305 AXTreeData data_; 306 307 // Map from an int attribute (if IsNodeIdIntAttribute is true) to 308 // a reverse mapping from target nodes to source nodes. 309 IntReverseRelationMap int_reverse_relations_; 310 // Map from an int list attribute (if IsNodeIdIntListAttribute is true) to 311 // a reverse mapping from target nodes to source nodes. 312 IntListReverseRelationMap intlist_reverse_relations_; 313 // Map from child tree ID to the set of node IDs that contain that attribute. 314 std::map<AXTreeID, std::set<int32_t>> child_tree_id_reverse_map_; 315 316 // Map from node ID to cached table info, if the given node is a table. 317 // Invalidated every time the tree is updated. 318 mutable std::unordered_map<int32_t, std::unique_ptr<AXTableInfo>> 319 table_info_map_; 320 321 // The next negative node ID to use for internal nodes. 322 int32_t next_negative_internal_node_id_ = -1; 323 324 // Whether we should create extra nodes that 325 // are only useful on macOS. Implemented using this flag to allow 326 // this code to be unit-tested on other platforms (for example, more 327 // code sanitizers run on Linux). 328 bool enable_extra_mac_nodes_ = false; 329 330 // Contains pos_in_set and set_size data for an AXNode. 331 struct NodeSetSizePosInSetInfo { 332 NodeSetSizePosInSetInfo() = default; 333 ~NodeSetSizePosInSetInfo() = default; 334 335 int32_t pos_in_set = 0; 336 int32_t set_size = 0; 337 base::Optional<int> lowest_hierarchical_level; 338 }; 339 340 // Represents the content of an ordered set which includes the ordered set 341 // items and the ordered set container if it exists. 342 struct OrderedSetContent; 343 344 // Maps a particular hierarchical level to a list of OrderedSetContents. 345 // Represents all ordered set items/container on a particular hierarchical 346 // level. 347 struct OrderedSetItemsMap; 348 349 // Populates |items_map_to_be_populated| with all items associated with 350 // |original_node| and within |ordered_set|. Only items whose roles match the 351 // role of the |ordered_set| will be added. 352 void PopulateOrderedSetItemsMap( 353 const AXNode& original_node, 354 const AXNode* ordered_set, 355 OrderedSetItemsMap* items_map_to_be_populated) const; 356 357 // Helper function for recursively populating ordered sets items map with 358 // all items associated with |original_node| and |ordered_set|. |local_parent| 359 // tracks the recursively passed in child nodes of |ordered_set|. 360 void RecursivelyPopulateOrderedSetItemsMap( 361 const AXNode& original_node, 362 const AXNode* ordered_set, 363 const AXNode* local_parent, 364 base::Optional<int> ordered_set_min_level, 365 base::Optional<int> prev_level, 366 OrderedSetItemsMap* items_map_to_be_populated) const; 367 368 // Computes the pos_in_set and set_size values of all items in ordered_set and 369 // caches those values. Called by GetPosInSet and GetSetSize. 370 void ComputeSetSizePosInSetAndCache(const AXNode& node, 371 const AXNode* ordered_set); 372 373 // Helper for ComputeSetSizePosInSetAndCache. Computes and caches the 374 // pos_in_set and set_size values for a given OrderedSetContent. 375 void ComputeSetSizePosInSetAndCacheHelper( 376 const OrderedSetContent& ordered_set_content); 377 378 // Map from node ID to OrderedSetInfo. 379 // Item-like and ordered-set-like objects will map to populated OrderedSetInfo 380 // objects. 381 // All other objects will map to default-constructed OrderedSetInfo objects. 382 // Invalidated every time the tree is updated. 383 mutable std::unordered_map<int32_t, NodeSetSizePosInSetInfo> 384 node_set_size_pos_in_set_info_map_; 385 386 // Indicates if the tree is updating. 387 bool tree_update_in_progress_ = false; 388 389 // Indicates if the tree represents a paginated document 390 bool has_pagination_support_ = false; 391 }; 392 393 } // namespace ui 394 395 #endif // UI_ACCESSIBILITY_AX_TREE_H_ 396