ax_tree_serializer.h 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802
  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_SERIALIZER_H_
  5. #define UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <ctime>
  9. #include <map>
  10. #include <memory>
  11. #include <ostream>
  12. #include <set>
  13. #include <vector>
  14. #include "base/debug/crash_logging.h"
  15. #include "base/logging.h"
  16. #include "base/memory/raw_ptr.h"
  17. #include "base/time/time.h"
  18. #include "base/timer/elapsed_timer.h"
  19. #include "ui/accessibility/ax_common.h"
  20. #include "ui/accessibility/ax_export.h"
  21. #include "ui/accessibility/ax_tree_source.h"
  22. #include "ui/accessibility/ax_tree_update.h"
  23. namespace ui {
  24. struct ClientTreeNode;
  25. // AXTreeSerializer is a helper class that serializes incremental
  26. // updates to an AXTreeSource as a AXTreeUpdate struct.
  27. // These structs can be unserialized by a client object such as an
  28. // AXTree. An AXTreeSerializer keeps track of the tree of node ids that its
  29. // client is aware of so that it will never generate an AXTreeUpdate that
  30. // results in an invalid tree.
  31. //
  32. // Every node in the source tree must have an id that's a unique positive
  33. // integer, the same node must not appear twice.
  34. //
  35. // Usage:
  36. //
  37. // You must call SerializeChanges() every time a node in the tree changes,
  38. // and send the generated AXTreeUpdate to the client. Changes to the
  39. // AXTreeData, if any, are also automatically included in the AXTreeUpdate.
  40. //
  41. // If a node is added, call SerializeChanges on its parent.
  42. // If a node is removed, call SerializeChanges on its parent.
  43. // If a whole new subtree is added, just call SerializeChanges on its root.
  44. // If the root of the tree changes, call SerializeChanges on the new root.
  45. //
  46. // AXTreeSerializer will avoid re-serializing nodes that do not change.
  47. // For example, if node 1 has children 2, 3, 4, 5 and then child 2 is
  48. // removed and a new child 6 is added, the AXTreeSerializer will only
  49. // update nodes 1 and 6 (and any children of node 6 recursively). It will
  50. // assume that nodes 3, 4, and 5 are not modified unless you explicitly
  51. // call SerializeChanges() on them.
  52. //
  53. // As long as the source tree has unique ids for every node and no loops,
  54. // and as long as every update is applied to the client tree, AXTreeSerializer
  55. // will continue to work. If the source tree makes a change but fails to
  56. // call SerializeChanges properly, the trees may get out of sync - but
  57. // because AXTreeSerializer always keeps track of what updates it's sent,
  58. // it will never send an invalid update and the client tree will not break,
  59. // it just may not contain all of the changes.
  60. template <typename AXSourceNode>
  61. class AXTreeSerializer {
  62. public:
  63. explicit AXTreeSerializer(AXTreeSource<AXSourceNode>* tree,
  64. bool crash_on_error = true);
  65. ~AXTreeSerializer();
  66. // Throw out the internal state that keeps track of the nodes the client
  67. // knows about. This has the effect that the next update will send the
  68. // entire tree over because it assumes the client knows nothing.
  69. void Reset();
  70. // Sets the maximum number of nodes that will be serialized, or zero
  71. // for no maximum. This is not a hard maximum - once it hits or
  72. // exceeds this maximum it stops walking the children of nodes, but
  73. // it may exceed this value a bit in order to create a consistent
  74. // tree.
  75. void set_max_node_count(size_t max_node_count) {
  76. max_node_count_ = max_node_count;
  77. }
  78. // Sets the maximum amount of time to be spend serializing, or zero for
  79. // no maximum. This is not a hard maximum - once it hits or
  80. // exceeds this timeout it stops walking the children of nodes, but
  81. // it may exceed this value a bit in order to create a consistent
  82. // tree. This is only intended to be used for one-time tree snapshots.
  83. void set_timeout(base::TimeDelta timeout) { timeout_ = timeout; }
  84. // Serialize all changes to |node| and append them to |out_update|.
  85. // Returns true on success. On failure, returns false and calls Reset();
  86. // this only happens when the source tree has a problem like duplicate
  87. // ids or changing during serialization.
  88. bool SerializeChanges(AXSourceNode node, AXTreeUpdate* out_update);
  89. // Get incompletely serialized nodes. This will only be nonempty if either
  90. // set_max_node_count or set_timeout were used. This is only valid after a
  91. // call to SerializeChanges, and it's reset with each call.
  92. std::vector<AXNodeID> GetIncompleteNodeIds();
  93. // Invalidate the subtree rooted at this node, ensuring that the whole
  94. // subtree is re-serialized the next time any of those nodes end up
  95. // being serialized.
  96. void InvalidateSubtree(AXSourceNode node);
  97. // Return whether or not this node is in the client tree. If you call
  98. // this immediately after serializing, this indicates whether a given
  99. // node is in the set of nodes that the client (the recipient of
  100. // the AXTreeUpdates) is aware of.
  101. //
  102. // For example, you could use this to determine if a given node is
  103. // reachable. If one of its ancestors is hidden and it was pruned
  104. // from the accessibility tree, this would return false.
  105. bool IsInClientTree(AXSourceNode node);
  106. // Only for unit testing. Normally this class relies on getting a call
  107. // to SerializeChanges() every time the source tree changes. For unit
  108. // testing, it's convenient to create a static AXTree for the initial
  109. // state and then call ChangeTreeSourceForTesting and then SerializeChanges
  110. // to simulate the changes you'd get if a tree changed from the initial
  111. // state to the second tree's state.
  112. void ChangeTreeSourceForTesting(AXTreeSource<AXSourceNode>* new_tree);
  113. // Returns the number of nodes in the client tree. After a serialization
  114. // operation this should be an accurate representation of the tree source
  115. // as explored by the serializer.
  116. size_t ClientTreeNodeCount() const;
  117. private:
  118. // Return the least common ancestor of a node in the source tree
  119. // and a node in the client tree, or nullptr if there is no such node.
  120. // The least common ancestor is the closest ancestor to |node| (which
  121. // may be |node| itself) that's in both the source tree and client tree,
  122. // and for which both the source and client tree agree on their ancestor
  123. // chain up to the root.
  124. //
  125. // Example 1:
  126. //
  127. // Client Tree Source tree |
  128. // 1 1 |
  129. // / \ / \ |
  130. // 2 3 2 4 |
  131. //
  132. // LCA(source node 2, client node 2) is node 2.
  133. // LCA(source node 3, client node 4) is node 1.
  134. //
  135. // Example 2:
  136. //
  137. // Client Tree Source tree |
  138. // 1 1 |
  139. // / \ / \ |
  140. // 2 3 2 3 |
  141. // / \ / / |
  142. // 4 7 8 4 |
  143. // / \ / \ |
  144. // 5 6 5 6 |
  145. //
  146. // LCA(source node 8, client node 7) is node 2.
  147. // LCA(source node 5, client node 5) is node 1.
  148. // It's not node 5, because the two trees disagree on the parent of
  149. // node 4, so the LCA is the first ancestor both trees agree on.
  150. AXSourceNode LeastCommonAncestor(AXSourceNode node,
  151. ClientTreeNode* client_node);
  152. // Return the least common ancestor of |node| that's in the client tree.
  153. // This just walks up the ancestors of |node| until it finds a node that's
  154. // also in the client tree and not inside an invalid subtree, and then calls
  155. // LeastCommonAncestor on the source node and client node.
  156. AXSourceNode LeastCommonAncestor(AXSourceNode node);
  157. // Walk the subtree rooted at |node| and return true if any nodes that
  158. // would be updated are being reparented. If so, update |out_lca| to point
  159. // to the least common ancestor of the previous LCA and the previous
  160. // parent of the node being reparented.
  161. bool AnyDescendantWasReparented(AXSourceNode node,
  162. AXSourceNode* out_lca);
  163. ClientTreeNode* ClientTreeNodeById(AXNodeID id);
  164. // Invalidate the subtree rooted at this node.
  165. void InvalidateClientSubtree(ClientTreeNode* client_node);
  166. // Delete all descendants of this node.
  167. void DeleteDescendants(ClientTreeNode* client_node);
  168. // Delete the client subtree rooted at this node.
  169. void DeleteClientSubtree(ClientTreeNode* client_node);
  170. // Helper function, called recursively with each new node to serialize.
  171. bool SerializeChangedNodes(AXSourceNode node, AXTreeUpdate* out_update);
  172. // Delete the entire client subtree but don't set the did_reset_ flag
  173. // like when Reset() is called.
  174. void InternalReset();
  175. ClientTreeNode* GetClientTreeNodeParent(ClientTreeNode* obj);
  176. // The tree source.
  177. raw_ptr<AXTreeSource<AXSourceNode>> tree_;
  178. // The tree data most recently sent to the client.
  179. AXTreeData client_tree_data_;
  180. // Our representation of the client tree.
  181. raw_ptr<ClientTreeNode> client_root_ = nullptr;
  182. // A map from IDs to nodes in the client tree.
  183. std::map<AXNodeID, ClientTreeNode*> client_id_map_;
  184. // The maximum number of nodes to serialize in a given call to
  185. // SerializeChanges, or 0 if there's no maximum.
  186. size_t max_node_count_ = 0;
  187. // The maximum time to spend serializing before timing out, or 0
  188. // if there's no maximum.
  189. base::TimeDelta timeout_;
  190. // The timer, which runs if there's a nonzero timeout and it hasn't
  191. // yet expired. Once the timeout elapses, the timer is deleted.
  192. std::unique_ptr<base::ElapsedTimer> timer_;
  193. // The IDs of nodes that weren't able to be completely serialized due to
  194. // max_node_count_ or timeout_.
  195. std::vector<AXNodeID> incomplete_node_ids_;
  196. // Keeps track of if Reset() was called. If so, we need to always
  197. // explicitly set node_id_to_clear to ensure that the next serialized
  198. // tree is treated as a completely new tree and not a partial update.
  199. bool did_reset_ = false;
  200. // Whether to crash the process on serialization error or not.
  201. const bool crash_on_error_;
  202. };
  203. // In order to keep track of what nodes the client knows about, we keep a
  204. // representation of the client tree - just IDs and parent/child
  205. // relationships, and a marker indicating whether it's been invalidated.
  206. struct AX_EXPORT ClientTreeNode {
  207. ClientTreeNode();
  208. virtual ~ClientTreeNode();
  209. AXNodeID id;
  210. raw_ptr<ClientTreeNode> parent;
  211. std::vector<ClientTreeNode*> children;
  212. bool ignored;
  213. bool invalid;
  214. };
  215. template <typename AXSourceNode>
  216. AXTreeSerializer<AXSourceNode>::AXTreeSerializer(
  217. AXTreeSource<AXSourceNode>* tree,
  218. bool crash_on_error)
  219. : tree_(tree), crash_on_error_(crash_on_error) {}
  220. template <typename AXSourceNode>
  221. AXTreeSerializer<AXSourceNode>::~AXTreeSerializer() {
  222. // Clear |tree_| to prevent any additional calls to the tree source
  223. // during teardown.
  224. tree_ = nullptr;
  225. Reset();
  226. }
  227. template <typename AXSourceNode>
  228. void AXTreeSerializer<AXSourceNode>::Reset() {
  229. InternalReset();
  230. did_reset_ = true;
  231. }
  232. template <typename AXSourceNode>
  233. void AXTreeSerializer<AXSourceNode>::InternalReset() {
  234. client_tree_data_ = AXTreeData();
  235. // Normally we use DeleteClientSubtree to remove nodes from the tree,
  236. // but Reset() needs to work even if the tree is in a broken state.
  237. // Instead, iterate over |client_id_map_| to ensure we clear all nodes and
  238. // start from scratch.
  239. for (auto&& item : client_id_map_) {
  240. if (tree_)
  241. tree_->SerializerClearedNode(item.first);
  242. delete item.second;
  243. }
  244. client_id_map_.clear();
  245. client_root_ = nullptr;
  246. }
  247. template <typename AXSourceNode>
  248. void AXTreeSerializer<AXSourceNode>::ChangeTreeSourceForTesting(
  249. AXTreeSource<AXSourceNode>* new_tree) {
  250. tree_ = new_tree;
  251. }
  252. template <typename AXSourceNode>
  253. size_t AXTreeSerializer<AXSourceNode>::ClientTreeNodeCount() const {
  254. return client_id_map_.size();
  255. }
  256. template <typename AXSourceNode>
  257. AXSourceNode AXTreeSerializer<AXSourceNode>::LeastCommonAncestor(
  258. AXSourceNode node,
  259. ClientTreeNode* client_node) {
  260. if (!tree_->IsValid(node) || client_node == nullptr)
  261. return tree_->GetNull();
  262. std::vector<AXSourceNode> ancestors;
  263. while (tree_->IsValid(node)) {
  264. ancestors.push_back(node);
  265. node = tree_->GetParent(node);
  266. }
  267. std::vector<ClientTreeNode*> client_ancestors;
  268. while (client_node) {
  269. client_ancestors.push_back(client_node);
  270. client_node = GetClientTreeNodeParent(client_node);
  271. }
  272. // Start at the root. Keep going until the source ancestor chain and
  273. // client ancestor chain disagree. The last node before they disagree
  274. // is the LCA.
  275. AXSourceNode lca = tree_->GetNull();
  276. for (size_t source_index = ancestors.size(),
  277. client_index = client_ancestors.size();
  278. source_index > 0 && client_index > 0; --source_index, --client_index) {
  279. if (tree_->GetId(ancestors[source_index - 1]) !=
  280. client_ancestors[client_index - 1]->id) {
  281. return lca;
  282. }
  283. lca = ancestors[source_index - 1];
  284. }
  285. return lca;
  286. }
  287. template <typename AXSourceNode>
  288. AXSourceNode AXTreeSerializer<AXSourceNode>::LeastCommonAncestor(
  289. AXSourceNode node) {
  290. // Walk up the tree until the source node's id also exists in the
  291. // client tree, whose parent is not invalid, then call LeastCommonAncestor
  292. // on those two nodes.
  293. //
  294. // Note that it's okay if |client_node| is invalid - the LCA can be the
  295. // root of an invalid subtree, since we're going to serialize the
  296. // LCA. But it's not okay if |client_node->parent| is invalid - that means
  297. // that we're inside of an invalid subtree that all needs to be
  298. // re-serialized, so the LCA should be higher.
  299. ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
  300. while (tree_->IsValid(node)) {
  301. if (client_node) {
  302. ClientTreeNode* parent = GetClientTreeNodeParent(client_node);
  303. if (!parent || !parent->invalid)
  304. break;
  305. }
  306. node = tree_->GetParent(node);
  307. if (tree_->IsValid(node))
  308. client_node = ClientTreeNodeById(tree_->GetId(node));
  309. }
  310. return LeastCommonAncestor(node, client_node);
  311. }
  312. template <typename AXSourceNode>
  313. bool AXTreeSerializer<AXSourceNode>::AnyDescendantWasReparented(
  314. AXSourceNode node,
  315. AXSourceNode* out_lca) {
  316. bool result = false;
  317. int id = tree_->GetId(node);
  318. std::vector<AXSourceNode> children;
  319. tree_->GetChildren(node, &children);
  320. for (size_t i = 0; i < children.size(); ++i) {
  321. AXSourceNode& child = children[i];
  322. int child_id = tree_->GetId(child);
  323. ClientTreeNode* client_child = ClientTreeNodeById(child_id);
  324. if (client_child) {
  325. ClientTreeNode* parent = client_child->parent;
  326. if (!parent) {
  327. // If the client child has no parent, it must have been the
  328. // previous root node, so there is no LCA and we can exit early.
  329. *out_lca = tree_->GetNull();
  330. return true;
  331. } else if (parent->id != id) {
  332. // If the client child's parent is not this node, update the LCA
  333. // and return true (reparenting was found).
  334. *out_lca = LeastCommonAncestor(*out_lca, client_child);
  335. result = true;
  336. continue;
  337. } else if (!client_child->invalid) {
  338. // This child is already in the client tree and valid, we won't
  339. // recursively serialize it so we don't need to check this
  340. // subtree recursively for reparenting.
  341. // However, if the child is or was ignored, the children may now be
  342. // considered as reparented, so continue recursion in that case.
  343. if (!client_child->ignored && !tree_->IsIgnored(child))
  344. continue;
  345. }
  346. }
  347. // This is a new child or reparented child, check it recursively.
  348. if (AnyDescendantWasReparented(child, out_lca))
  349. result = true;
  350. }
  351. return result;
  352. }
  353. template <typename AXSourceNode>
  354. ClientTreeNode* AXTreeSerializer<AXSourceNode>::ClientTreeNodeById(
  355. AXNodeID id) {
  356. std::map<AXNodeID, ClientTreeNode*>::iterator iter = client_id_map_.find(id);
  357. if (iter != client_id_map_.end())
  358. return iter->second;
  359. return nullptr;
  360. }
  361. template <typename AXSourceNode>
  362. ClientTreeNode* AXTreeSerializer<AXSourceNode>::GetClientTreeNodeParent(
  363. ClientTreeNode* obj) {
  364. ClientTreeNode* parent = obj->parent;
  365. if (!parent)
  366. return nullptr;
  367. if (!ClientTreeNodeById(parent->id)) {
  368. std::ostringstream error;
  369. error << "Child: " << tree_->GetDebugString(tree_->GetFromId(obj->id))
  370. << "\nParent: "
  371. << tree_->GetDebugString(tree_->GetFromId(parent->id));
  372. static auto* missing_parent_err = base::debug::AllocateCrashKeyString(
  373. "ax_ts_missing_parent_err", base::debug::CrashKeySize::Size256);
  374. base::debug::SetCrashKeyString(missing_parent_err,
  375. error.str().substr(0, 230));
  376. if (crash_on_error_) {
  377. CHECK(false) << error.str();
  378. } else {
  379. LOG(ERROR) << error.str();
  380. // Different from other errors, not calling Reset() here to avoid breaking
  381. // the internal state of this class.
  382. }
  383. }
  384. return parent;
  385. }
  386. template <typename AXSourceNode>
  387. bool AXTreeSerializer<AXSourceNode>::SerializeChanges(
  388. AXSourceNode node,
  389. AXTreeUpdate* out_update) {
  390. if (!timeout_.is_zero())
  391. timer_ = std::make_unique<base::ElapsedTimer>();
  392. incomplete_node_ids_.clear();
  393. // Send the tree data if it's changed since the last update, or if
  394. // out_update->has_tree_data is already set to true.
  395. AXTreeData new_tree_data;
  396. if (tree_->GetTreeData(&new_tree_data) &&
  397. (out_update->has_tree_data || new_tree_data != client_tree_data_)) {
  398. out_update->has_tree_data = true;
  399. out_update->tree_data = new_tree_data;
  400. client_tree_data_ = new_tree_data;
  401. }
  402. // If the node isn't in the client tree, we need to serialize starting
  403. // with the LCA.
  404. AXSourceNode lca = LeastCommonAncestor(node);
  405. // This loop computes the least common ancestor that includes the old
  406. // and new parents of any nodes that have been reparented, and clears the
  407. // whole client subtree of that LCA if necessary. If we do end up clearing
  408. // any client nodes, keep looping because we have to search for more
  409. // nodes that may have been reparented from this new LCA.
  410. bool need_delete;
  411. do {
  412. need_delete = false;
  413. if (client_root_) {
  414. if (tree_->IsValid(lca)) {
  415. // Check for any reparenting within this subtree - if there is
  416. // any, we need to delete and reserialize the whole subtree
  417. // that contains the old and new parents of the reparented node.
  418. if (AnyDescendantWasReparented(lca, &lca))
  419. need_delete = true;
  420. }
  421. if (!tree_->IsValid(lca)) {
  422. // If there's no LCA, just tell the client to destroy the whole
  423. // tree and then we'll serialize everything from the new root.
  424. // Cases where this occurs:
  425. // - A new document is loaded (main or iframe)
  426. // - document.body.innerHTML is changed
  427. // - A modal <dialog> is opened
  428. // - Full screen mode is toggled
  429. out_update->node_id_to_clear = client_root_->id;
  430. InternalReset();
  431. } else if (need_delete) {
  432. // Otherwise, if we need to reserialize a subtree, first we need
  433. // to delete those nodes in our client tree so that
  434. // SerializeChangedNodes() will be sure to send them again.
  435. out_update->node_id_to_clear = tree_->GetId(lca);
  436. ClientTreeNode* client_lca = ClientTreeNodeById(tree_->GetId(lca));
  437. CHECK(client_lca);
  438. DeleteDescendants(client_lca);
  439. }
  440. }
  441. } while (need_delete);
  442. // Serialize from the LCA, or from the root if there isn't one.
  443. if (!tree_->IsValid(lca))
  444. lca = tree_->GetRoot();
  445. if (!SerializeChangedNodes(lca, out_update))
  446. return false;
  447. // If we had a reset, ensure that the old tree is cleared before the client
  448. // unserializes this update. If we didn't do this, there's a chance that
  449. // treating this update as an incremental update could result in some
  450. // reparenting.
  451. if (did_reset_) {
  452. out_update->node_id_to_clear = tree_->GetId(lca);
  453. did_reset_ = false;
  454. }
  455. return true;
  456. }
  457. template <typename AXSourceNode>
  458. std::vector<AXNodeID> AXTreeSerializer<AXSourceNode>::GetIncompleteNodeIds() {
  459. DCHECK(max_node_count_ > 0 || !timeout_.is_zero());
  460. return incomplete_node_ids_;
  461. }
  462. template <typename AXSourceNode>
  463. void AXTreeSerializer<AXSourceNode>::InvalidateSubtree(AXSourceNode node) {
  464. ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
  465. if (client_node)
  466. InvalidateClientSubtree(client_node);
  467. }
  468. template <typename AXSourceNode>
  469. bool AXTreeSerializer<AXSourceNode>::IsInClientTree(AXSourceNode node) {
  470. ClientTreeNode* client_node = ClientTreeNodeById(tree_->GetId(node));
  471. return client_node ? !client_node->invalid : false;
  472. }
  473. template <typename AXSourceNode>
  474. void AXTreeSerializer<AXSourceNode>::InvalidateClientSubtree(
  475. ClientTreeNode* client_node) {
  476. client_node->invalid = true;
  477. for (size_t i = 0; i < client_node->children.size(); ++i)
  478. InvalidateClientSubtree(client_node->children[i]);
  479. }
  480. template <typename AXSourceNode>
  481. void AXTreeSerializer<AXSourceNode>::DeleteClientSubtree(
  482. ClientTreeNode* client_node) {
  483. if (client_node == client_root_) {
  484. Reset(); // Do not try to reuse a bad root later.
  485. // A heuristic for this condition rather than an explicit Reset() from a
  486. // caller makes it difficult to debug whether extra resets / lost virtual
  487. // buffer positions are occurring because of this code. Therefore, a DCHECK
  488. // has been added in order to debug if or when this condition may occur.
  489. #if defined(AX_FAIL_FAST_BUILD)
  490. CHECK(!crash_on_error_)
  491. << "Attempt to delete entire client subtree, including the root.";
  492. #else
  493. DCHECK(!crash_on_error_)
  494. << "Attempt to delete entire client subtree, including the root.";
  495. #endif
  496. } else {
  497. DeleteDescendants(client_node);
  498. tree_->SerializerClearedNode(client_node->id);
  499. client_id_map_.erase(client_node->id);
  500. delete client_node;
  501. }
  502. }
  503. template <typename AXSourceNode>
  504. void AXTreeSerializer<AXSourceNode>::DeleteDescendants(
  505. ClientTreeNode* client_node) {
  506. for (size_t i = 0; i < client_node->children.size(); ++i)
  507. DeleteClientSubtree(client_node->children[i]);
  508. client_node->children.clear();
  509. }
  510. template <typename AXSourceNode>
  511. bool AXTreeSerializer<AXSourceNode>::SerializeChangedNodes(
  512. AXSourceNode node,
  513. AXTreeUpdate* out_update) {
  514. // This method has three responsibilities:
  515. // 1. Serialize |node| into an AXNodeData, and append it to
  516. // the AXTreeUpdate to be sent to the client.
  517. // 2. Determine if |node| has any new children that the client doesn't
  518. // know about yet, and call SerializeChangedNodes recursively on those.
  519. // 3. Update our internal data structure that keeps track of what nodes
  520. // the client knows about.
  521. // First, find the ClientTreeNode for this id in our data structure where
  522. // we keep track of what accessibility objects the client already knows
  523. // about.
  524. // If we don't find it, then the intention may be to use it as the
  525. // new root of the accessibility tree. A heuristic for this condition rather
  526. // than an explicit Reset() from a caller makes it difficult to debug whether
  527. // extra resets / lost virtual buffer positions are occurring because of this
  528. // code. Therefore, a DCHECK has been added in order to debug if or when this
  529. // condition may occur.
  530. int id = tree_->GetId(node);
  531. ClientTreeNode* client_node = ClientTreeNodeById(id);
  532. if (!client_node) {
  533. if (client_root_) {
  534. Reset();
  535. #if defined(AX_FAIL_FAST_BUILD)
  536. CHECK(!crash_on_error_) << "Missing client node for serialization.";
  537. #else
  538. DCHECK(!crash_on_error_) << "Missing client node for serialization.";
  539. #endif
  540. }
  541. client_root_ = new ClientTreeNode();
  542. client_node = client_root_;
  543. client_node->id = id;
  544. client_node->parent = nullptr;
  545. client_id_map_[client_node->id] = client_node;
  546. }
  547. // We're about to serialize it, so mark it as valid.
  548. client_node->invalid = false;
  549. client_node->ignored = tree_->IsIgnored(node);
  550. // Terminate early if a maximum number of nodes is reached.
  551. // the output tree is still consistent).
  552. bool should_terminate_early = false;
  553. if (max_node_count_ > 0 && out_update->nodes.size() >= max_node_count_)
  554. should_terminate_early = true;
  555. // Also terminate early if a timeout is reached.
  556. if (!timeout_.is_zero()) {
  557. if (timer_ && timer_->Elapsed() >= timeout_) {
  558. // Terminate early and delete the timer so that we don't have to
  559. // keep checking if we timed out.
  560. should_terminate_early = true;
  561. timer_.reset();
  562. } else if (!timer_) {
  563. // Already timed out; keep terminating early until the serialization
  564. // is done.
  565. should_terminate_early = true;
  566. }
  567. }
  568. // Iterate over the ids of the children of |node|.
  569. // Create a set of the child ids so we can quickly look
  570. // up which children are new and which ones were there before.
  571. // If we've hit the maximum number of serialized nodes, pretend
  572. // this node has no children but keep going so that we get
  573. // consistent results.
  574. std::set<AXNodeID> new_ignored_ids;
  575. std::set<AXNodeID> new_child_ids;
  576. std::vector<AXSourceNode> children;
  577. if (should_terminate_early) {
  578. incomplete_node_ids_.push_back(id);
  579. } else {
  580. tree_->GetChildren(node, &children);
  581. }
  582. for (size_t i = 0; i < children.size(); ++i) {
  583. AXSourceNode& child = children[i];
  584. int new_child_id = tree_->GetId(child);
  585. new_child_ids.insert(new_child_id);
  586. if (tree_->IsIgnored(child))
  587. new_ignored_ids.insert(new_child_id);
  588. // There shouldn't be any reparenting because we've already handled it
  589. // above. If this happens, reset and return an error.
  590. ClientTreeNode* client_child = ClientTreeNodeById(new_child_id);
  591. if (client_child && GetClientTreeNodeParent(client_child) != client_node) {
  592. // This condition leads to performance problems. It will
  593. // also reset virtual buffers, causing users to lose their place.
  594. std::ostringstream error;
  595. error << "Passed-in parent: "
  596. << tree_->GetDebugString(tree_->GetFromId(client_node->id))
  597. << "\nChild: " << tree_->GetDebugString(child)
  598. << "\nChild's parent: "
  599. << tree_->GetDebugString(
  600. tree_->GetFromId(client_child->parent->id));
  601. static auto* reparent_err = base::debug::AllocateCrashKeyString(
  602. "ax_ts_reparent_err", base::debug::CrashKeySize::Size256);
  603. base::debug::SetCrashKeyString(reparent_err, error.str().substr(0, 230));
  604. if (crash_on_error_) {
  605. CHECK(false) << error.str();
  606. } else {
  607. LOG(ERROR) << error.str();
  608. Reset();
  609. }
  610. return false;
  611. }
  612. }
  613. // Go through the old children and delete subtrees for child
  614. // ids that are no longer present, and create a map from
  615. // id to ClientTreeNode for the rest. It's important to delete
  616. // first in a separate pass so that nodes that are reparented
  617. // don't end up children of two different parents in the middle
  618. // of an update, which can lead to a double-free.
  619. std::map<AXNodeID, ClientTreeNode*> client_child_id_map;
  620. std::vector<ClientTreeNode*> old_children;
  621. old_children.swap(client_node->children);
  622. for (size_t i = 0; i < old_children.size(); ++i) {
  623. ClientTreeNode* old_child = old_children[i];
  624. int old_child_id = old_child->id;
  625. if (new_child_ids.find(old_child_id) == new_child_ids.end()) {
  626. DeleteClientSubtree(old_child);
  627. } else {
  628. client_child_id_map[old_child_id] = old_child;
  629. }
  630. }
  631. // Serialize this node. This fills in all of the fields in
  632. // AXNodeData except child_ids, which we handle below.
  633. size_t serialized_node_index = out_update->nodes.size();
  634. out_update->nodes.push_back(AXNodeData());
  635. {
  636. // Take the address of an element in a vector only within a limited
  637. // scope because otherwise the pointer can become invalid if the
  638. // vector is resized.
  639. AXNodeData* serialized_node = &out_update->nodes[serialized_node_index];
  640. tree_->SerializeNode(node, serialized_node);
  641. if (serialized_node->id == client_root_->id)
  642. out_update->root_id = serialized_node->id;
  643. }
  644. // Iterate over the children, serialize them, and update the ClientTreeNode
  645. // data structure to reflect the new tree.
  646. std::vector<AXNodeID> actual_serialized_node_child_ids;
  647. client_node->children.reserve(children.size());
  648. for (size_t i = 0; i < children.size(); ++i) {
  649. AXSourceNode& child = children[i];
  650. int child_id = tree_->GetId(child);
  651. // Skip if the child isn't valid.
  652. if (!tree_->IsValid(child))
  653. continue;
  654. // Skip if the same child is included more than once.
  655. if (new_child_ids.find(child_id) == new_child_ids.end())
  656. continue;
  657. new_child_ids.erase(child_id);
  658. actual_serialized_node_child_ids.push_back(child_id);
  659. ClientTreeNode* reused_child = nullptr;
  660. if (client_child_id_map.find(child_id) != client_child_id_map.end())
  661. reused_child = ClientTreeNodeById(child_id);
  662. if (reused_child) {
  663. client_node->children.push_back(reused_child);
  664. const bool ignored_state_changed =
  665. reused_child->ignored !=
  666. (new_ignored_ids.find(reused_child->id) != new_ignored_ids.end());
  667. // Re-serialize it if the child is marked as invalid, otherwise
  668. // we don't have to because the client already has it.
  669. if (reused_child->invalid || ignored_state_changed) {
  670. if (!SerializeChangedNodes(child, out_update))
  671. return false;
  672. }
  673. } else {
  674. ClientTreeNode* new_child = new ClientTreeNode();
  675. new_child->id = child_id;
  676. new_child->parent = client_node;
  677. new_child->ignored = tree_->IsIgnored(child);
  678. new_child->invalid = false;
  679. client_node->children.push_back(new_child);
  680. if (ClientTreeNodeById(child_id)) {
  681. // TODO(accessibility) Remove all cases where this occurs and re-add
  682. // This condition leads to performance problems. It will
  683. // also reset virtual buffers, causing users to lose their place.
  684. std::ostringstream error;
  685. error << "Child id " << child_id << " already in map."
  686. << "\nChild: "
  687. << tree_->GetDebugString(tree_->GetFromId(child_id))
  688. << "\nWanted for parent " << tree_->GetDebugString(node)
  689. << "\nAlready had parent "
  690. << tree_->GetDebugString(tree_->GetFromId(
  691. ClientTreeNodeById(child_id)->parent->id));
  692. static auto* dupe_id_err = base::debug::AllocateCrashKeyString(
  693. "ax_ts_dupe_id_err", base::debug::CrashKeySize::Size256);
  694. base::debug::SetCrashKeyString(dupe_id_err, error.str().substr(0, 230));
  695. if (crash_on_error_) {
  696. CHECK(false) << error.str();
  697. } else {
  698. LOG(ERROR) << error.str();
  699. Reset();
  700. }
  701. return false;
  702. }
  703. client_id_map_[child_id] = new_child;
  704. if (!SerializeChangedNodes(child, out_update))
  705. return false;
  706. }
  707. }
  708. // Finally, update the child ids of this node to reflect the actual child
  709. // ids that were valid during serialization.
  710. out_update->nodes[serialized_node_index].child_ids.swap(
  711. actual_serialized_node_child_ids);
  712. return true;
  713. }
  714. } // namespace ui
  715. #endif // UI_ACCESSIBILITY_AX_TREE_SERIALIZER_H_