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 PosInSet of |node|. Looks in node_set_size_pos_in_set_info_map_ 151 // for cached value. Calls |ComputeSetSizePosInSetAndCache|if no value is 152 // present in the cache. 153 base::Optional<int> GetPosInSet(const AXNode& node) override; 154 // Returns the SetSize of |node|. Looks in node_set_size_pos_in_set_info_map_ 155 // for cached value. Calls |ComputeSetSizePosInSetAndCache|if no value is 156 // present in the cache. 157 base::Optional<int> GetSetSize(const AXNode& node) override; 158 159 Selection GetUnignoredSelection() const override; 160 161 bool GetTreeUpdateInProgressState() const override; 162 void SetTreeUpdateInProgressState(bool set_tree_update_value); 163 164 // AXNode::OwnerTree override. 165 // Returns true if the tree represents a paginated document 166 bool HasPaginationSupport() const override; 167 168 // Language detection manager, entry point to language detection features. 169 // TODO(chrishall): Should this be stored by pointer or value? 170 // When should we initialize this? 171 std::unique_ptr<AXLanguageDetectionManager> language_detection_manager; 172 173 // A list of intents active during a tree update/unserialization. event_intents()174 const std::vector<AXEventIntent>& event_intents() const { 175 return event_intents_; 176 } 177 178 private: 179 friend class AXTableInfoTest; 180 181 // Accumulate errors as there can be more than one before Chrome is crashed 182 // via AccessibilityFatalError(); 183 void RecordError(std::string new_error); 184 185 // AXNode::OwnerTree override. 186 // 187 // Given a node in this accessibility tree that corresponds to a table 188 // or grid, return an object containing information about the 189 // table structure. This object is computed lazily on-demand and 190 // cached until the next time the tree is updated. Clients should 191 // not retain this pointer, they should just request it every time 192 // it's needed. 193 // 194 // Returns nullptr if the node is not a valid table. 195 AXTableInfo* GetTableInfo(const AXNode* table_node) const override; 196 197 AXNode* CreateNode(AXNode* parent, 198 AXNode::AXID id, 199 size_t index_in_parent, 200 AXTreeUpdateState* update_state); 201 202 // Accumulates the work that will be required to update the AXTree. 203 // This allows us to notify observers of structure changes when the 204 // tree is still in a stable and unchanged state. 205 bool ComputePendingChanges(const AXTreeUpdate& update, 206 AXTreeUpdateState* update_state); 207 208 // Populates |update_state| with information about actions that will 209 // be performed on the tree during the update, such as adding or 210 // removing nodes in the tree. Returns true on success. 211 // Nothing within this call should modify tree structure or node data. 212 bool ComputePendingChangesToNode(const AXNodeData& new_data, 213 bool is_new_root, 214 AXTreeUpdateState* update_state); 215 216 // This is called from within Unserialize(), it returns true on success. 217 bool UpdateNode(const AXNodeData& src, 218 bool is_new_root, 219 AXTreeUpdateState* update_state); 220 221 // Notify the delegate that the subtree rooted at |node| will be 222 // destroyed or reparented. 223 void NotifySubtreeWillBeReparentedOrDeleted( 224 AXNode* node, 225 const AXTreeUpdateState* update_state); 226 227 // Notify the delegate that |node| will be destroyed or reparented. 228 void NotifyNodeWillBeReparentedOrDeleted( 229 AXNode* node, 230 const AXTreeUpdateState* update_state); 231 232 // Notify the delegate that |node| and all of its descendants will be 233 // destroyed. This function is called during AXTree teardown. 234 void RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode* node); 235 236 // Notify the delegate that the node marked by |node_id| has been deleted. 237 // We are passing the node id instead of ax node is because by the time this 238 // function is called, the ax node in the tree will already have been 239 // destroyed. 240 void NotifyNodeHasBeenDeleted(AXNode::AXID node_id); 241 242 // Notify the delegate that |node| has been created or reparented. 243 void NotifyNodeHasBeenReparentedOrCreated( 244 AXNode* node, 245 const AXTreeUpdateState* update_state); 246 247 // Notify the delegate that a node will change its data. 248 void NotifyNodeDataWillChange(const AXNodeData& old_data, 249 const AXNodeData& new_data); 250 251 // Notify the delegate that |node| has changed its data. 252 void NotifyNodeDataHasBeenChanged(AXNode* node, 253 const AXNodeData& old_data, 254 const AXNodeData& new_data); 255 256 void UpdateReverseRelations(AXNode* node, const AXNodeData& new_data); 257 258 // Returns true if all pending changes in the |update_state| have been 259 // handled. If this returns false, the |error_| message will be populated. 260 // It's a fatal error to have pending changes after exhausting 261 // the AXTreeUpdate. 262 bool ValidatePendingChangesComplete(const AXTreeUpdateState& update_state); 263 264 // Modifies |update_state| so that it knows what subtree and nodes are 265 // going to be destroyed for the subtree rooted at |node|. 266 void MarkSubtreeForDestruction(AXNode::AXID node_id, 267 AXTreeUpdateState* update_state); 268 269 // Modifies |update_state| so that it knows what nodes are 270 // going to be destroyed for the subtree rooted at |node|. 271 void MarkNodesForDestructionRecursive(AXNode::AXID node_id, 272 AXTreeUpdateState* update_state); 273 274 // Validates that destroying the subtree rooted at |node| has required 275 // information in |update_state|, then calls DestroyNodeAndSubtree on it. 276 void DestroySubtree(AXNode* node, AXTreeUpdateState* update_state); 277 278 // Call Destroy() on |node|, and delete it from the id map, and then 279 // call recursively on all nodes in its subtree. 280 void DestroyNodeAndSubtree(AXNode* node, AXTreeUpdateState* update_state); 281 282 // Iterate over the children of |node| and for each child, destroy the 283 // child and its subtree if its id is not in |new_child_ids|. 284 void DeleteOldChildren(AXNode* node, 285 const std::vector<int32_t>& new_child_ids, 286 AXTreeUpdateState* update_state); 287 288 // Iterate over |new_child_ids| and populate |new_children| with 289 // pointers to child nodes, reusing existing nodes already in the tree 290 // if they exist, and creating otherwise. Reparenting is disallowed, so 291 // if the id already exists as the child of another node, that's an 292 // error. Returns true on success, false on fatal error. 293 bool CreateNewChildVector(AXNode* node, 294 const std::vector<int32_t>& new_child_ids, 295 std::vector<AXNode*>* new_children, 296 AXTreeUpdateState* update_state); 297 298 // Internal implementation of RelativeToTreeBounds. It calls itself 299 // recursively but ensures that it can only do so exactly once! 300 gfx::RectF RelativeToTreeBoundsInternal(const AXNode* node, 301 gfx::RectF node_bounds, 302 bool* offscreen, 303 bool clip_bounds, 304 bool allow_recursion) const; 305 306 base::ObserverList<AXTreeObserver> observers_; 307 AXNode* root_ = nullptr; 308 std::unordered_map<int32_t, AXNode*> id_map_; 309 std::string error_; 310 AXTreeData data_; 311 312 // Map from an int attribute (if IsNodeIdIntAttribute is true) to 313 // a reverse mapping from target nodes to source nodes. 314 IntReverseRelationMap int_reverse_relations_; 315 // Map from an int list attribute (if IsNodeIdIntListAttribute is true) to 316 // a reverse mapping from target nodes to source nodes. 317 IntListReverseRelationMap intlist_reverse_relations_; 318 // Map from child tree ID to the set of node IDs that contain that attribute. 319 std::map<AXTreeID, std::set<int32_t>> child_tree_id_reverse_map_; 320 321 // Map from node ID to cached table info, if the given node is a table. 322 // Invalidated every time the tree is updated. 323 mutable std::unordered_map<int32_t, std::unique_ptr<AXTableInfo>> 324 table_info_map_; 325 326 // The next negative node ID to use for internal nodes. 327 int32_t next_negative_internal_node_id_ = -1; 328 329 // Whether we should create extra nodes that 330 // are only useful on macOS. Implemented using this flag to allow 331 // this code to be unit-tested on other platforms (for example, more 332 // code sanitizers run on Linux). 333 bool enable_extra_mac_nodes_ = false; 334 335 // Contains pos_in_set and set_size data for an AXNode. 336 struct NodeSetSizePosInSetInfo { 337 NodeSetSizePosInSetInfo(); 338 ~NodeSetSizePosInSetInfo(); 339 340 base::Optional<int> pos_in_set; 341 base::Optional<int> set_size; 342 base::Optional<int> lowest_hierarchical_level; 343 }; 344 345 // Represents the content of an ordered set which includes the ordered set 346 // items and the ordered set container if it exists. 347 struct OrderedSetContent; 348 349 // Maps a particular hierarchical level to a list of OrderedSetContents. 350 // Represents all ordered set items/container on a particular hierarchical 351 // level. 352 struct OrderedSetItemsMap; 353 354 // Populates |items_map_to_be_populated| with all items associated with 355 // |original_node| and within |ordered_set|. Only items whose roles match the 356 // role of the |ordered_set| will be added. 357 void PopulateOrderedSetItemsMap( 358 const AXNode& original_node, 359 const AXNode* ordered_set, 360 OrderedSetItemsMap* items_map_to_be_populated) const; 361 362 // Helper function for recursively populating ordered sets items map with 363 // all items associated with |original_node| and |ordered_set|. |local_parent| 364 // tracks the recursively passed in child nodes of |ordered_set|. 365 void RecursivelyPopulateOrderedSetItemsMap( 366 const AXNode& original_node, 367 const AXNode* ordered_set, 368 const AXNode* local_parent, 369 base::Optional<int> ordered_set_min_level, 370 base::Optional<int> prev_level, 371 OrderedSetItemsMap* items_map_to_be_populated) const; 372 373 // Computes the pos_in_set and set_size values of all items in ordered_set and 374 // caches those values. Called by GetPosInSet and GetSetSize. 375 void ComputeSetSizePosInSetAndCache(const AXNode& node, 376 const AXNode* ordered_set); 377 378 // Helper for ComputeSetSizePosInSetAndCache. Computes and caches the 379 // pos_in_set and set_size values for a given OrderedSetContent. 380 void ComputeSetSizePosInSetAndCacheHelper( 381 const OrderedSetContent& ordered_set_content); 382 383 // Map from node ID to OrderedSetInfo. 384 // Item-like and ordered-set-like objects will map to populated OrderedSetInfo 385 // objects. 386 // All other objects will map to default-constructed OrderedSetInfo objects. 387 // Invalidated every time the tree is updated. 388 mutable std::unordered_map<int32_t, NodeSetSizePosInSetInfo> 389 node_set_size_pos_in_set_info_map_; 390 391 // Indicates if the tree is updating. 392 bool tree_update_in_progress_ = false; 393 394 // Indicates if the tree represents a paginated document 395 bool has_pagination_support_ = false; 396 397 std::vector<AXEventIntent> event_intents_; 398 }; 399 400 } // namespace ui 401 402 #endif // UI_ACCESSIBILITY_AX_TREE_H_ 403