ax_tree.cc 114 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778
  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. #include "ui/accessibility/ax_tree.h"
  5. #include <stddef.h>
  6. #include <algorithm>
  7. #include <numeric>
  8. #include <utility>
  9. #include "base/auto_reset.h"
  10. #include "base/callback_helpers.h"
  11. #include "base/check_op.h"
  12. #include "base/command_line.h"
  13. #include "base/containers/adapters.h"
  14. #include "base/containers/contains.h"
  15. #include "base/memory/ptr_util.h"
  16. #include "base/memory/raw_ptr.h"
  17. #include "base/metrics/histogram_macros.h"
  18. #include "base/no_destructor.h"
  19. #include "base/notreached.h"
  20. #include "base/observer_list.h"
  21. #include "base/strings/stringprintf.h"
  22. #include "components/crash/core/common/crash_key.h"
  23. #include "ui/accessibility/accessibility_switches.h"
  24. #include "ui/accessibility/ax_enums.mojom.h"
  25. #include "ui/accessibility/ax_event.h"
  26. #include "ui/accessibility/ax_language_detection.h"
  27. #include "ui/accessibility/ax_node.h"
  28. #include "ui/accessibility/ax_node_position.h"
  29. #include "ui/accessibility/ax_role_properties.h"
  30. #include "ui/accessibility/ax_table_info.h"
  31. #include "ui/accessibility/ax_tree_observer.h"
  32. #include "ui/gfx/geometry/transform.h"
  33. namespace ui {
  34. namespace {
  35. std::string TreeToStringHelper(const AXNode* node, int indent) {
  36. if (!node)
  37. return "";
  38. return std::accumulate(
  39. node->children().cbegin(), node->children().cend(),
  40. std::string(2 * indent, ' ') + node->data().ToString() + "\n",
  41. [indent](const std::string& str, const auto* child) {
  42. return str + TreeToStringHelper(child, indent + 1);
  43. });
  44. }
  45. template <typename K, typename V>
  46. bool KeyValuePairsKeysMatch(std::vector<std::pair<K, V>> pairs1,
  47. std::vector<std::pair<K, V>> pairs2) {
  48. if (pairs1.size() != pairs2.size())
  49. return false;
  50. for (size_t i = 0; i < pairs1.size(); ++i) {
  51. if (pairs1[i].first != pairs2[i].first)
  52. return false;
  53. }
  54. return true;
  55. }
  56. template <typename K, typename V>
  57. std::map<K, V> MapFromKeyValuePairs(std::vector<std::pair<K, V>> pairs) {
  58. std::map<K, V> result;
  59. for (size_t i = 0; i < pairs.size(); ++i)
  60. result[pairs[i].first] = pairs[i].second;
  61. return result;
  62. }
  63. // Given two vectors of <K, V> key, value pairs representing an "old" vs "new"
  64. // state, or "before" vs "after", calls a callback function for each key that
  65. // changed value. Note that if an attribute is removed, that will result in
  66. // a call to the callback with the value changing from the previous value to
  67. // |empty_value|, and similarly when an attribute is added.
  68. template <typename K, typename V, typename F>
  69. void CallIfAttributeValuesChanged(const std::vector<std::pair<K, V>>& pairs1,
  70. const std::vector<std::pair<K, V>>& pairs2,
  71. const V& empty_value,
  72. F callback) {
  73. // Fast path - if they both have the same keys in the same order.
  74. if (KeyValuePairsKeysMatch(pairs1, pairs2)) {
  75. for (size_t i = 0; i < pairs1.size(); ++i) {
  76. if (pairs1[i].second != pairs2[i].second)
  77. callback(pairs1[i].first, pairs1[i].second, pairs2[i].second);
  78. }
  79. return;
  80. }
  81. // Slower path - they don't have the same keys in the same order, so
  82. // check all keys against each other, using maps to prevent this from
  83. // becoming O(n^2) as the size grows.
  84. auto map1 = MapFromKeyValuePairs(pairs1);
  85. auto map2 = MapFromKeyValuePairs(pairs2);
  86. for (size_t i = 0; i < pairs1.size(); ++i) {
  87. const auto& new_iter = map2.find(pairs1[i].first);
  88. if (pairs1[i].second != empty_value && new_iter == map2.end())
  89. callback(pairs1[i].first, pairs1[i].second, empty_value);
  90. }
  91. for (size_t i = 0; i < pairs2.size(); ++i) {
  92. const auto& iter = map1.find(pairs2[i].first);
  93. if (pairs2[i].second == empty_value && iter == map1.end())
  94. continue;
  95. if (iter == map1.end())
  96. callback(pairs2[i].first, empty_value, pairs2[i].second);
  97. else if (iter->second != pairs2[i].second)
  98. callback(pairs2[i].first, iter->second, pairs2[i].second);
  99. }
  100. }
  101. bool IsCollapsed(const AXNode* node) {
  102. return node && node->HasState(ax::mojom::State::kCollapsed);
  103. }
  104. } // namespace
  105. // static
  106. bool AXTree::is_focused_node_always_unignored_ = false;
  107. // This object is used to track structure changes that will occur for a specific
  108. // AXID. This includes how many times we expect that a node with a specific AXID
  109. // will be created and/or destroyed, and how many times a subtree rooted at AXID
  110. // expects to be destroyed during an AXTreeUpdate.
  111. //
  112. // An AXTreeUpdate is a serialized representation of an atomic change to an
  113. // AXTree. See also |AXTreeUpdate| which documents the nature and invariants
  114. // required to atomically update the AXTree.
  115. //
  116. // The reason that we must track these counts, and the reason these are counts
  117. // rather than a bool/flag is because an AXTreeUpdate may contain multiple
  118. // AXNodeData updates for a given AXID. A common way that this occurs is when
  119. // multiple AXTreeUpdates are merged together, combining their AXNodeData list.
  120. // Additionally AXIDs may be reused after being removed from the tree,
  121. // most notably when "reparenting" a node. A "reparent" occurs when an AXID is
  122. // first destroyed from the tree then created again in the same AXTreeUpdate,
  123. // which may also occur multiple times with merged updates.
  124. //
  125. // We need to accumulate these counts for 3 reasons :
  126. // 1. To determine what structure changes *will* occur before applying
  127. // updates to the tree so that we can notify observers of structure changes
  128. // when the tree is still in a stable and unchanged state.
  129. // 2. Capture any errors *before* applying updates to the tree structure
  130. // due to the order of (or lack of) AXNodeData entries in the update
  131. // so we can abort a bad update instead of applying it partway.
  132. // 3. To validate that the expectations we accumulate actually match
  133. // updates that are applied to the tree.
  134. //
  135. // To reiterate the invariants that this structure is taking a dependency on
  136. // from |AXTreeUpdate|, suppose that the next AXNodeData to be applied is
  137. // |node|. The following invariants must hold:
  138. // 1. Either
  139. // a) |node.id| is already in the tree, or
  140. // b) the tree is empty, and
  141. // |node| is the new root of the tree, and
  142. // |node.role| == kRootWebArea.
  143. // 2. Every child id in |node.child_ids| must either be already a child
  144. // of this node, or a new id not previously in the tree. It is not
  145. // allowed to "reparent" a child to this node without first removing
  146. // that child from its previous parent.
  147. // 3. When a new id appears in |node.child_ids|, the tree should create a
  148. // new uninitialized placeholder node for it immediately. That
  149. // placeholder must be updated within the same AXTreeUpdate, otherwise
  150. // it's a fatal error. This guarantees the tree is always complete
  151. // before or after an AXTreeUpdate.
  152. struct PendingStructureChanges {
  153. explicit PendingStructureChanges(const AXNode* node)
  154. : destroy_subtree_count(0),
  155. destroy_node_count(0),
  156. create_node_count(0),
  157. node_exists(!!node),
  158. parent_node_id((node && node->parent())
  159. ? absl::make_optional<AXNodeID>(node->parent()->id())
  160. : absl::nullopt),
  161. last_known_data(node ? &node->data() : nullptr) {}
  162. // Returns true if this node has any changes remaining.
  163. // This includes pending subtree or node destruction, and node creation.
  164. bool DoesNodeExpectAnyStructureChanges() const {
  165. return DoesNodeExpectSubtreeWillBeDestroyed() ||
  166. DoesNodeExpectNodeWillBeDestroyed() ||
  167. DoesNodeExpectNodeWillBeCreated();
  168. }
  169. // Returns true if there are any pending changes that require destroying
  170. // this node or its subtree.
  171. bool DoesNodeExpectSubtreeOrNodeWillBeDestroyed() const {
  172. return DoesNodeExpectSubtreeWillBeDestroyed() ||
  173. DoesNodeExpectNodeWillBeDestroyed();
  174. }
  175. // Returns true if the subtree rooted at this node needs to be destroyed
  176. // during the update, but this may not be the next action that needs to be
  177. // performed on the node.
  178. bool DoesNodeExpectSubtreeWillBeDestroyed() const {
  179. return destroy_subtree_count;
  180. }
  181. // Returns true if this node needs to be destroyed during the update, but this
  182. // may not be the next action that needs to be performed on the node.
  183. bool DoesNodeExpectNodeWillBeDestroyed() const { return destroy_node_count; }
  184. // Returns true if this node needs to be created during the update, but this
  185. // may not be the next action that needs to be performed on the node.
  186. bool DoesNodeExpectNodeWillBeCreated() const { return create_node_count; }
  187. // Returns true if this node would exist in the tree as of the last pending
  188. // update that was processed, and the node has not been provided node data.
  189. bool DoesNodeRequireInit() const { return node_exists && !last_known_data; }
  190. // Keep track of the number of times the subtree rooted at this node
  191. // will be destroyed.
  192. // An example of when this count may be larger than 1 is if updates were
  193. // merged together. A subtree may be [created,] destroyed, created, and
  194. // destroyed again within the same |AXTreeUpdate|. The important takeaway here
  195. // is that an update may request destruction of a subtree rooted at an
  196. // AXID more than once, not that a specific subtree is being destroyed
  197. // more than once.
  198. int32_t destroy_subtree_count;
  199. // Keep track of the number of times this node will be destroyed.
  200. // An example of when this count may be larger than 1 is if updates were
  201. // merged together. A node may be [created,] destroyed, created, and destroyed
  202. // again within the same |AXTreeUpdate|. The important takeaway here is that
  203. // an AXID may request destruction more than once, not that a specific node
  204. // is being destroyed more than once.
  205. int32_t destroy_node_count;
  206. // Keep track of the number of times this node will be created.
  207. // An example of when this count may be larger than 1 is if updates were
  208. // merged together. A node may be [destroyed,] created, destroyed, and created
  209. // again within the same |AXTreeUpdate|. The important takeaway here is that
  210. // an AXID may request creation more than once, not that a specific node is
  211. // being created more than once.
  212. int32_t create_node_count;
  213. // Keep track of whether this node exists in the tree as of the last pending
  214. // update that was processed.
  215. bool node_exists;
  216. // Keep track of the parent id for this node as of the last pending
  217. // update that was processed.
  218. absl::optional<AXNodeID> parent_node_id;
  219. // Keep track of the last known node data for this node.
  220. // This will be null either when a node does not exist in the tree, or
  221. // when the node is new and has not been initialized with node data yet.
  222. // This is needed to determine what children have changed between pending
  223. // updates.
  224. raw_ptr<const AXNodeData> last_known_data;
  225. };
  226. // Represents the different states when computing PendingStructureChanges
  227. // required for tree Unserialize.
  228. enum class AXTreePendingStructureStatus {
  229. // PendingStructureChanges have not begun computation.
  230. kNotStarted,
  231. // PendingStructureChanges are currently being computed.
  232. kComputing,
  233. // All PendingStructureChanges have successfully been computed.
  234. kComplete,
  235. // An error occurred when computing pending changes.
  236. kFailed,
  237. };
  238. // Intermediate state to keep track of during a tree update.
  239. struct AXTreeUpdateState {
  240. AXTreeUpdateState(const AXTree& tree, const AXTreeUpdate& pending_tree_update)
  241. : pending_update_status(AXTreePendingStructureStatus::kNotStarted),
  242. root_will_be_created(false),
  243. pending_tree_update(pending_tree_update),
  244. tree(tree) {}
  245. // Returns whether this update removes |node|.
  246. bool IsRemovedNode(const AXNode* node) const {
  247. return base::Contains(removed_node_ids, node->id());
  248. }
  249. // Returns whether this update creates a node marked by |node_id|.
  250. bool IsCreatedNode(AXNodeID node_id) const {
  251. return base::Contains(new_node_ids, node_id);
  252. }
  253. // Returns whether this update creates |node|.
  254. bool IsCreatedNode(const AXNode* node) const {
  255. return IsCreatedNode(node->id());
  256. }
  257. // Returns whether this update reparents |node|.
  258. bool IsReparentedNode(const AXNode* node) const {
  259. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  260. << "This method should not be called before pending changes have "
  261. "finished computing.";
  262. PendingStructureChanges* data = GetPendingStructureChanges(node->id());
  263. if (!data)
  264. return false;
  265. // In order to know if the node will be reparented during the update,
  266. // we check if either the node will be destroyed or has been destroyed at
  267. // least once during the update.
  268. // Since this method is only allowed to be called after calculating all
  269. // pending structure changes, |node_exists| tells us if the node should
  270. // exist after all updates have been applied.
  271. return (data->DoesNodeExpectNodeWillBeDestroyed() || IsRemovedNode(node)) &&
  272. data->node_exists;
  273. }
  274. // Returns true if the node should exist in the tree but doesn't have
  275. // any node data yet.
  276. bool DoesPendingNodeRequireInit(AXNodeID node_id) const {
  277. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  278. << "This method should only be called while computing pending changes, "
  279. "before updates are made to the tree.";
  280. PendingStructureChanges* data = GetPendingStructureChanges(node_id);
  281. return data && data->DoesNodeRequireInit();
  282. }
  283. // Returns the parent node id for the pending node.
  284. absl::optional<AXNodeID> GetParentIdForPendingNode(AXNodeID node_id) {
  285. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  286. << "This method should only be called while computing pending changes, "
  287. "before updates are made to the tree.";
  288. PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
  289. DCHECK(!data->parent_node_id ||
  290. ShouldPendingNodeExistInTree(*data->parent_node_id));
  291. return data->parent_node_id;
  292. }
  293. // Returns true if this node should exist in the tree.
  294. bool ShouldPendingNodeExistInTree(AXNodeID node_id) {
  295. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  296. << "This method should only be called while computing pending changes, "
  297. "before updates are made to the tree.";
  298. return GetOrCreatePendingStructureChanges(node_id)->node_exists;
  299. }
  300. // Returns the last known node data for a pending node.
  301. const AXNodeData& GetLastKnownPendingNodeData(AXNodeID node_id) const {
  302. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  303. << "This method should only be called while computing pending changes, "
  304. "before updates are made to the tree.";
  305. static base::NoDestructor<ui::AXNodeData> empty_data;
  306. PendingStructureChanges* data = GetPendingStructureChanges(node_id);
  307. return (data && data->last_known_data) ? *data->last_known_data
  308. : *empty_data;
  309. }
  310. // Clear the last known pending data for |node_id|.
  311. void ClearLastKnownPendingNodeData(AXNodeID node_id) {
  312. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  313. << "This method should only be called while computing pending changes, "
  314. "before updates are made to the tree.";
  315. GetOrCreatePendingStructureChanges(node_id)->last_known_data = nullptr;
  316. }
  317. // Update the last known pending node data for |node_data.id|.
  318. void SetLastKnownPendingNodeData(const AXNodeData* node_data) {
  319. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  320. << "This method should only be called while computing pending changes, "
  321. "before updates are made to the tree.";
  322. GetOrCreatePendingStructureChanges(node_data->id)->last_known_data =
  323. node_data;
  324. }
  325. // Returns the number of times the update is expected to destroy a
  326. // subtree rooted at |node_id|.
  327. int32_t GetPendingDestroySubtreeCount(AXNodeID node_id) const {
  328. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  329. << "This method should not be called before pending changes have "
  330. "finished computing.";
  331. if (PendingStructureChanges* data = GetPendingStructureChanges(node_id))
  332. return data->destroy_subtree_count;
  333. return 0;
  334. }
  335. // Increments the number of times the update is expected to
  336. // destroy a subtree rooted at |node_id|.
  337. // Returns true on success, false on failure when the node will not exist.
  338. bool IncrementPendingDestroySubtreeCount(AXNodeID node_id) {
  339. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  340. << "This method should only be called while computing pending changes, "
  341. "before updates are made to the tree.";
  342. PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
  343. if (!data->node_exists)
  344. return false;
  345. ++data->destroy_subtree_count;
  346. return true;
  347. }
  348. // Decrements the number of times the update is expected to
  349. // destroy a subtree rooted at |node_id|.
  350. void DecrementPendingDestroySubtreeCount(AXNodeID node_id) {
  351. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  352. << "This method should not be called before pending changes have "
  353. "finished computing.";
  354. if (PendingStructureChanges* data = GetPendingStructureChanges(node_id)) {
  355. DCHECK_GT(data->destroy_subtree_count, 0);
  356. --data->destroy_subtree_count;
  357. }
  358. }
  359. // Returns the number of times the update is expected to destroy
  360. // a node with |node_id|.
  361. int32_t GetPendingDestroyNodeCount(AXNodeID node_id) const {
  362. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  363. << "This method should not be called before pending changes have "
  364. "finished computing.";
  365. if (PendingStructureChanges* data = GetPendingStructureChanges(node_id))
  366. return data->destroy_node_count;
  367. return 0;
  368. }
  369. // Increments the number of times the update is expected to
  370. // destroy a node with |node_id|.
  371. // Returns true on success, false on failure when the node will not exist.
  372. bool IncrementPendingDestroyNodeCount(AXNodeID node_id) {
  373. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  374. << "This method should only be called while computing pending changes, "
  375. "before updates are made to the tree.";
  376. PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
  377. if (!data->node_exists)
  378. return false;
  379. ++data->destroy_node_count;
  380. data->node_exists = false;
  381. data->last_known_data = nullptr;
  382. data->parent_node_id = absl::nullopt;
  383. if (pending_root_id == node_id)
  384. pending_root_id = absl::nullopt;
  385. return true;
  386. }
  387. // Decrements the number of times the update is expected to
  388. // destroy a node with |node_id|.
  389. void DecrementPendingDestroyNodeCount(AXNodeID node_id) {
  390. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  391. << "This method should not be called before pending changes have "
  392. "finished computing.";
  393. if (PendingStructureChanges* data = GetPendingStructureChanges(node_id)) {
  394. DCHECK_GT(data->destroy_node_count, 0);
  395. --data->destroy_node_count;
  396. }
  397. }
  398. // Returns the number of times the update is expected to create
  399. // a node with |node_id|.
  400. int32_t GetPendingCreateNodeCount(AXNodeID node_id) const {
  401. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  402. << "This method should not be called before pending changes have "
  403. "finished computing.";
  404. if (PendingStructureChanges* data = GetPendingStructureChanges(node_id))
  405. return data->create_node_count;
  406. return 0;
  407. }
  408. // Increments the number of times the update is expected to
  409. // create a node with |node_id|.
  410. // Returns true on success, false on failure when the node will already exist.
  411. bool IncrementPendingCreateNodeCount(
  412. AXNodeID node_id,
  413. absl::optional<AXNodeID> parent_node_id) {
  414. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  415. << "This method should only be called while computing pending changes, "
  416. "before updates are made to the tree.";
  417. PendingStructureChanges* data = GetOrCreatePendingStructureChanges(node_id);
  418. if (data->node_exists)
  419. return false;
  420. ++data->create_node_count;
  421. data->node_exists = true;
  422. data->parent_node_id = parent_node_id;
  423. return true;
  424. }
  425. // Decrements the number of times the update is expected to
  426. // create a node with |node_id|.
  427. void DecrementPendingCreateNodeCount(AXNodeID node_id) {
  428. DCHECK_EQ(AXTreePendingStructureStatus::kComplete, pending_update_status)
  429. << "This method should not be called before pending changes have "
  430. "finished computing.";
  431. if (PendingStructureChanges* data = GetPendingStructureChanges(node_id)) {
  432. DCHECK_GT(data->create_node_count, 0);
  433. --data->create_node_count;
  434. }
  435. }
  436. // Returns true if this node's updated data in conjunction with the updated
  437. // tree data indicate that the node will need to invalidate any of its cached
  438. // values, such as the number of its unignored children.
  439. bool HasIgnoredChanged(const AXNodeData& new_data) const {
  440. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  441. << "This method should only be called while computing pending changes, "
  442. "before updates are made to the tree.";
  443. const AXNodeData& old_data = GetLastKnownPendingNodeData(new_data.id);
  444. return AXTree::ComputeNodeIsIgnored(
  445. old_tree_data ? &old_tree_data.value() : nullptr, old_data) !=
  446. AXTree::ComputeNodeIsIgnored(
  447. new_tree_data ? &new_tree_data.value() : nullptr, new_data);
  448. }
  449. // Returns whether this update must invalidate the unignored cached
  450. // values for |node_id|.
  451. bool InvalidatesUnignoredCachedValues(AXNodeID node_id) const {
  452. return base::Contains(invalidate_unignored_cached_values_ids, node_id);
  453. }
  454. // Adds the parent of |node_id| to the list of nodes to invalidate unignored
  455. // cached values.
  456. void InvalidateParentNodeUnignoredCacheValues(AXNodeID node_id) {
  457. DCHECK_EQ(AXTreePendingStructureStatus::kComputing, pending_update_status)
  458. << "This method should only be called while computing pending changes, "
  459. "before updates are made to the tree.";
  460. absl::optional<AXNodeID> parent_node_id =
  461. GetParentIdForPendingNode(node_id);
  462. if (parent_node_id) {
  463. invalidate_unignored_cached_values_ids.insert(*parent_node_id);
  464. }
  465. }
  466. // Indicates the status for calculating what changes will occur during
  467. // an update before the update applies changes.
  468. AXTreePendingStructureStatus pending_update_status;
  469. // Keeps track of the existing tree's root node id when calculating what
  470. // changes will occur during an update before the update applies changes.
  471. absl::optional<AXNodeID> pending_root_id;
  472. // Keeps track of whether the root node will need to be created as a new node.
  473. // This may occur either when the root node does not exist before applying
  474. // updates to the tree (new tree), or if the root is the |node_id_to_clear|
  475. // and will be destroyed before applying AXNodeData updates to the tree.
  476. bool root_will_be_created;
  477. // During an update, this keeps track of all node IDs that have been
  478. // implicitly referenced as part of this update, but haven't been updated yet.
  479. // It's an error if there are any pending nodes at the end of Unserialize.
  480. std::set<AXNodeID> pending_node_ids;
  481. // before, During and after an update, this keeps track of the nodes' data
  482. // that have been provided as part of the update.
  483. std::vector<AXNodeData> updated_nodes;
  484. // Keeps track of nodes whose cached unignored child count, or unignored
  485. // index in parent may have changed, and must be updated.
  486. std::set<AXNodeID> invalidate_unignored_cached_values_ids;
  487. // Keeps track of nodes that have changed their node data or their ignored
  488. // state.
  489. std::set<AXNodeID> node_data_changed_ids;
  490. // Keeps track of new nodes created during this update.
  491. std::set<AXNodeID> new_node_ids;
  492. // Keeps track of any nodes removed. Nodes are removed when their AXID no
  493. // longer exist in the parent |child_ids| list, or the node is part of to the
  494. // subtree of the AXID that was explicitally cleared with |node_id_to_clear|.
  495. // Used to identify re-parented nodes. A re-parented occurs when any AXID
  496. // is first removed from the tree then added to the tree again.
  497. std::set<AXNodeID> removed_node_ids;
  498. // Maps between a node id and its pending update information.
  499. std::map<AXNodeID, std::unique_ptr<PendingStructureChanges>>
  500. node_id_to_pending_data;
  501. // Maps between a node id and the data it owned before being updated.
  502. // We need to keep this around in order to correctly fire post-update events.
  503. std::map<AXNodeID, AXNodeData> old_node_id_to_data;
  504. // Optional copy of the old tree data, only populated when the tree data will
  505. // need to be updated.
  506. absl::optional<AXTreeData> old_tree_data;
  507. // Optional copy of the updated tree data, used when calculating what changes
  508. // will occur during an update before the update applies changes.
  509. absl::optional<AXTreeData> new_tree_data;
  510. // Keep track of the pending tree update to help create useful error messages.
  511. // TODO(crbug.com/1156601) Revert this once we have the crash data we need
  512. // (crrev.com/c/2892259).
  513. const AXTreeUpdate& pending_tree_update;
  514. private:
  515. PendingStructureChanges* GetPendingStructureChanges(AXNodeID node_id) const {
  516. auto iter = node_id_to_pending_data.find(node_id);
  517. return (iter != node_id_to_pending_data.cend()) ? iter->second.get()
  518. : nullptr;
  519. }
  520. PendingStructureChanges* GetOrCreatePendingStructureChanges(
  521. AXNodeID node_id) {
  522. auto iter = node_id_to_pending_data.find(node_id);
  523. if (iter == node_id_to_pending_data.cend()) {
  524. const AXNode* node = tree.GetFromId(node_id);
  525. iter = node_id_to_pending_data
  526. .emplace(std::make_pair(
  527. node_id, std::make_unique<PendingStructureChanges>(node)))
  528. .first;
  529. }
  530. return iter->second.get();
  531. }
  532. // We need to hold onto a reference to the AXTree so that we can
  533. // lazily initialize |PendingStructureChanges| objects.
  534. const AXTree& tree;
  535. };
  536. AXTree::NodeSetSizePosInSetInfo::NodeSetSizePosInSetInfo() = default;
  537. AXTree::NodeSetSizePosInSetInfo::~NodeSetSizePosInSetInfo() = default;
  538. struct AXTree::OrderedSetContent {
  539. explicit OrderedSetContent(const AXNode* ordered_set = nullptr)
  540. : ordered_set_(ordered_set) {}
  541. ~OrderedSetContent() = default;
  542. std::vector<const AXNode*> set_items_;
  543. // Some ordered set items may not be associated with an ordered set.
  544. raw_ptr<const AXNode> ordered_set_;
  545. };
  546. struct AXTree::OrderedSetItemsMap {
  547. OrderedSetItemsMap() = default;
  548. ~OrderedSetItemsMap() = default;
  549. // Check if a particular hierarchical level exists in this map.
  550. bool HierarchicalLevelExists(absl::optional<int> level) {
  551. if (items_map_.find(level) == items_map_.end())
  552. return false;
  553. return true;
  554. }
  555. // Add the OrderedSetContent to the corresponding hierarchical level in the
  556. // map.
  557. void Add(absl::optional<int> level,
  558. const OrderedSetContent& ordered_set_content) {
  559. if (!HierarchicalLevelExists(level))
  560. items_map_[level] = std::vector<OrderedSetContent>();
  561. items_map_[level].push_back(ordered_set_content);
  562. }
  563. // Add an ordered set item to the OrderedSetItemsMap given its hierarchical
  564. // level. We always want to append the item to the last OrderedSetContent of
  565. // that hierarchical level, due to the following:
  566. // - The last OrderedSetContent on any level of the items map is in progress
  567. // of being populated.
  568. // - All other OrderedSetContent other than the last one on a level
  569. // represents a complete ordered set and should not be modified.
  570. void AddItemToBack(absl::optional<int> level, const AXNode* item) {
  571. if (!HierarchicalLevelExists(level))
  572. return;
  573. std::vector<OrderedSetContent>& sets_list = items_map_[level];
  574. if (!sets_list.empty()) {
  575. OrderedSetContent& ordered_set_content = sets_list.back();
  576. ordered_set_content.set_items_.push_back(item);
  577. }
  578. }
  579. // Retrieve the first OrderedSetContent of the OrderedSetItemsMap.
  580. OrderedSetContent* GetFirstOrderedSetContent() {
  581. if (items_map_.empty())
  582. return nullptr;
  583. std::vector<OrderedSetContent>& sets_list = items_map_.begin()->second;
  584. if (sets_list.empty())
  585. return nullptr;
  586. return &(sets_list.front());
  587. }
  588. // Clears all the content in the map.
  589. void Clear() { items_map_.clear(); }
  590. // Maps a hierarchical level to a list of OrderedSetContent.
  591. std::map<absl::optional<int32_t>, std::vector<OrderedSetContent>> items_map_;
  592. };
  593. // static
  594. void AXTree::SetFocusedNodeShouldNeverBeIgnored() {
  595. is_focused_node_always_unignored_ = true;
  596. }
  597. // static
  598. bool AXTree::ComputeNodeIsIgnored(const AXTreeData* optional_tree_data,
  599. const AXNodeData& node_data) {
  600. // A node with an ARIA presentational role (role="none") should also be
  601. // ignored.
  602. bool is_ignored = node_data.HasState(ax::mojom::State::kIgnored) ||
  603. node_data.role == ax::mojom::Role::kNone;
  604. // Exception: We should never ignore focused nodes otherwise users of
  605. // assistive software might be unable to interact with the webpage.
  606. //
  607. // TODO(nektar): This check is erroneous: It's missing a check of
  608. // focused_tree_id. Fix after updating `AXNode::IsFocusedInThisTree`.
  609. if (is_focused_node_always_unignored_ && is_ignored && optional_tree_data &&
  610. optional_tree_data->focus_id != kInvalidAXNodeID &&
  611. node_data.id == optional_tree_data->focus_id) {
  612. // If the focus has moved to or away from this node, it can also flip the
  613. // ignored state, provided that the node's data has the ignored state in the
  614. // first place. In all other cases, focus cannot affect the ignored state.
  615. is_ignored = false;
  616. }
  617. return is_ignored;
  618. }
  619. // static
  620. bool AXTree::ComputeNodeIsIgnoredChanged(
  621. const AXTreeData* optional_old_tree_data,
  622. const AXNodeData& old_node_data,
  623. const AXTreeData* optional_new_tree_data,
  624. const AXNodeData& new_node_data) {
  625. // We should not notify observers of an ignored state change if the node was
  626. // invisible and continues to be invisible after the update. Also, we should
  627. // not notify observers if the node has flipped its invisible state from
  628. // invisible to visible or vice versa. This is because when invisibility
  629. // changes, the entire subtree is being inserted or removed. For example if
  630. // the "hidden" CSS property is deleted from a list item, its ignored state
  631. // will change but the change would be due to the list item becoming visible
  632. // and thereby adding a whole subtree of nodes, including a list marker and
  633. // possibly some static text. This situation arises because hidden nodes are
  634. // included in the internal accessibility tree, but they are marked as
  635. // ignored.
  636. //
  637. // TODO(nektar): This should be dealt with by fixing AXEventGenerator or
  638. // individual platforms.
  639. const bool old_node_is_ignored =
  640. ComputeNodeIsIgnored(optional_old_tree_data, old_node_data);
  641. const bool new_node_is_ignored =
  642. ComputeNodeIsIgnored(optional_new_tree_data, new_node_data);
  643. return old_node_is_ignored != new_node_is_ignored;
  644. }
  645. AXTree::AXTree() {
  646. AXNodeData root;
  647. root.id = kInvalidAXNodeID;
  648. AXTreeUpdate initial_state;
  649. initial_state.root_id = kInvalidAXNodeID;
  650. initial_state.nodes.push_back(root);
  651. CHECK(Unserialize(initial_state)) << error();
  652. // TODO(chrishall): should language_detection_manager be a member or pointer?
  653. // TODO(chrishall): do we want to initialize all the time, on demand, or only
  654. // when feature flag is set?
  655. DCHECK(!language_detection_manager);
  656. language_detection_manager =
  657. std::make_unique<AXLanguageDetectionManager>(this);
  658. }
  659. AXTree::AXTree(const AXTreeUpdate& initial_state) {
  660. CHECK(Unserialize(initial_state)) << error();
  661. DCHECK(!language_detection_manager);
  662. language_detection_manager =
  663. std::make_unique<AXLanguageDetectionManager>(this);
  664. }
  665. AXTree::~AXTree() {
  666. Destroy();
  667. // Language detection manager will detach from AXTree observer list in its
  668. // destructor. But because of variable order, when destroying AXTree, the
  669. // observer list will already be destroyed. To avoid that problem, free
  670. // language detection manager before.
  671. language_detection_manager.reset();
  672. }
  673. void AXTree::AddObserver(AXTreeObserver* observer) {
  674. observers_.AddObserver(observer);
  675. }
  676. bool AXTree::HasObserver(AXTreeObserver* observer) {
  677. return observers_.HasObserver(observer);
  678. }
  679. void AXTree::RemoveObserver(AXTreeObserver* observer) {
  680. observers_.RemoveObserver(observer);
  681. }
  682. const AXTreeID& AXTree::GetAXTreeID() const {
  683. return data().tree_id;
  684. }
  685. const AXTreeData& AXTree::data() const {
  686. return data_;
  687. }
  688. AXNode* AXTree::GetFromId(AXNodeID id) const {
  689. auto iter = id_map_.find(id);
  690. return iter != id_map_.end() ? iter->second.get() : nullptr;
  691. }
  692. void AXTree::Destroy() {
  693. table_info_map_.clear();
  694. if (!root_)
  695. return;
  696. RecursivelyNotifyNodeDeletedForTreeTeardown(root_);
  697. {
  698. ScopedTreeUpdateInProgressStateSetter tree_update_in_progress(*this);
  699. // ExtractAsDangling clears the underlying pointer and returns another
  700. // raw_ptr instance that is allowed to dangle.
  701. DestroyNodeAndSubtree(root_.ExtractAsDangling(), nullptr);
  702. } // tree_update_in_progress.
  703. }
  704. void AXTree::UpdateDataForTesting(const AXTreeData& new_data) {
  705. if (data_ == new_data)
  706. return;
  707. AXTreeUpdate update;
  708. update.has_tree_data = true;
  709. update.tree_data = new_data;
  710. Unserialize(update);
  711. }
  712. gfx::RectF AXTree::RelativeToTreeBoundsInternal(const AXNode* node,
  713. gfx::RectF bounds,
  714. bool* offscreen,
  715. bool clip_bounds,
  716. bool skip_container_offset,
  717. bool allow_recursion) const {
  718. // If |bounds| is uninitialized, which is not the same as empty,
  719. // start with the node bounds.
  720. if (bounds.width() == 0 && bounds.height() == 0) {
  721. bounds = node->data().relative_bounds.bounds;
  722. // If the node bounds is empty (either width or height is zero),
  723. // try to compute good bounds from the children.
  724. // If a tree update is in progress, skip this step as children may be in a
  725. // bad state.
  726. if (bounds.IsEmpty() && !GetTreeUpdateInProgressState() &&
  727. allow_recursion) {
  728. for (size_t i = 0; i < node->children().size(); i++) {
  729. ui::AXNode* child = node->children()[i];
  730. bool ignore_offscreen;
  731. gfx::RectF child_bounds =
  732. RelativeToTreeBoundsInternal(child, gfx::RectF(), &ignore_offscreen,
  733. clip_bounds, skip_container_offset,
  734. /* allow_recursion = */ false);
  735. bounds.Union(child_bounds);
  736. }
  737. if (bounds.width() > 0 && bounds.height() > 0) {
  738. return bounds;
  739. }
  740. }
  741. } else if (!skip_container_offset) {
  742. bounds.Offset(node->data().relative_bounds.bounds.x(),
  743. node->data().relative_bounds.bounds.y());
  744. }
  745. const AXNode* original_node = node;
  746. while (node != nullptr) {
  747. if (node->data().relative_bounds.transform)
  748. node->data().relative_bounds.transform->TransformRect(&bounds);
  749. // Apply any transforms and offsets for each node and then walk up to
  750. // its offset container. If no offset container is specified, coordinates
  751. // are relative to the root node.
  752. const AXNode* container =
  753. GetFromId(node->data().relative_bounds.offset_container_id);
  754. if (!container && container != root())
  755. container = root();
  756. if (!container || container == node || skip_container_offset)
  757. break;
  758. gfx::RectF container_bounds = container->data().relative_bounds.bounds;
  759. bounds.Offset(container_bounds.x(), container_bounds.y());
  760. int scroll_x = 0;
  761. int scroll_y = 0;
  762. if (container->GetIntAttribute(ax::mojom::IntAttribute::kScrollX,
  763. &scroll_x) &&
  764. container->GetIntAttribute(ax::mojom::IntAttribute::kScrollY,
  765. &scroll_y)) {
  766. bounds.Offset(-scroll_x, -scroll_y);
  767. }
  768. // Get the intersection between the bounds and the container.
  769. gfx::RectF intersection = bounds;
  770. intersection.Intersect(container_bounds);
  771. // Calculate the clipped bounds to determine offscreen state.
  772. gfx::RectF clipped = bounds;
  773. // If this node has the kClipsChildren attribute set, clip the rect to fit.
  774. if (container->GetBoolAttribute(ax::mojom::BoolAttribute::kClipsChildren)) {
  775. if (!intersection.IsEmpty()) {
  776. // We can simply clip it to the container.
  777. clipped = intersection;
  778. } else {
  779. // Totally offscreen. Find the nearest edge or corner.
  780. // Make the minimum dimension 1 instead of 0.
  781. if (clipped.x() >= container_bounds.width()) {
  782. clipped.set_x(container_bounds.right() - 1);
  783. clipped.set_width(1);
  784. } else if (clipped.x() + clipped.width() <= 0) {
  785. clipped.set_x(container_bounds.x());
  786. clipped.set_width(1);
  787. }
  788. if (clipped.y() >= container_bounds.height()) {
  789. clipped.set_y(container_bounds.bottom() - 1);
  790. clipped.set_height(1);
  791. } else if (clipped.y() + clipped.height() <= 0) {
  792. clipped.set_y(container_bounds.y());
  793. clipped.set_height(1);
  794. }
  795. }
  796. }
  797. if (clip_bounds)
  798. bounds = clipped;
  799. if (container->GetBoolAttribute(ax::mojom::BoolAttribute::kClipsChildren) &&
  800. intersection.IsEmpty() && !clipped.IsEmpty()) {
  801. // If it is offscreen with respect to its parent, and the node itself is
  802. // not empty, label it offscreen.
  803. // Here we are extending the definition of offscreen to include elements
  804. // that are clipped by their parents in addition to those clipped by
  805. // the rootWebArea.
  806. // No need to update |offscreen| if |intersection| is not empty, because
  807. // it should be false by default.
  808. if (offscreen != nullptr)
  809. *offscreen |= true;
  810. }
  811. node = container;
  812. }
  813. // If we don't have any size yet, try to adjust the bounds to fill the
  814. // nearest ancestor that does have bounds.
  815. //
  816. // The rationale is that it's not useful to the user for an object to
  817. // have no width or height and it's probably a bug; it's better to
  818. // reflect the bounds of the nearest ancestor rather than a 0x0 box.
  819. // Tag this node as 'offscreen' because it has no true size, just a
  820. // size inherited from the ancestor.
  821. if (bounds.width() == 0 && bounds.height() == 0) {
  822. const AXNode* ancestor = original_node->parent();
  823. gfx::RectF ancestor_bounds;
  824. while (ancestor) {
  825. ancestor_bounds = ancestor->data().relative_bounds.bounds;
  826. if (ancestor_bounds.width() > 0 || ancestor_bounds.height() > 0)
  827. break;
  828. ancestor = ancestor->parent();
  829. }
  830. if (ancestor && allow_recursion) {
  831. bool ignore_offscreen;
  832. ancestor_bounds = RelativeToTreeBoundsInternal(
  833. ancestor, gfx::RectF(), &ignore_offscreen, clip_bounds,
  834. skip_container_offset,
  835. /* allow_recursion = */ false);
  836. gfx::RectF original_bounds = original_node->data().relative_bounds.bounds;
  837. if (original_bounds.x() == 0 && original_bounds.y() == 0) {
  838. bounds = ancestor_bounds;
  839. } else {
  840. bounds.set_width(std::max(0.0f, ancestor_bounds.right() - bounds.x()));
  841. bounds.set_height(
  842. std::max(0.0f, ancestor_bounds.bottom() - bounds.y()));
  843. }
  844. if (offscreen != nullptr)
  845. *offscreen |= true;
  846. }
  847. }
  848. return bounds;
  849. }
  850. gfx::RectF AXTree::RelativeToTreeBounds(const AXNode* node,
  851. gfx::RectF bounds,
  852. bool* offscreen,
  853. bool clip_bounds,
  854. bool skip_container_offset) const {
  855. bool allow_recursion = true;
  856. return RelativeToTreeBoundsInternal(node, bounds, offscreen, clip_bounds,
  857. skip_container_offset, allow_recursion);
  858. }
  859. gfx::RectF AXTree::GetTreeBounds(const AXNode* node,
  860. bool* offscreen,
  861. bool clip_bounds) const {
  862. return RelativeToTreeBounds(node, gfx::RectF(), offscreen, clip_bounds);
  863. }
  864. std::set<AXNodeID> AXTree::GetReverseRelations(ax::mojom::IntAttribute attr,
  865. AXNodeID dst_id) const {
  866. DCHECK(IsNodeIdIntAttribute(attr));
  867. // Conceptually, this is the "const" version of:
  868. // return int_reverse_relations_[attr][dst_id];
  869. const auto& attr_relations = int_reverse_relations_.find(attr);
  870. if (attr_relations != int_reverse_relations_.end()) {
  871. const auto& result = attr_relations->second.find(dst_id);
  872. if (result != attr_relations->second.end())
  873. return result->second;
  874. }
  875. return std::set<AXNodeID>();
  876. }
  877. std::set<AXNodeID> AXTree::GetReverseRelations(ax::mojom::IntListAttribute attr,
  878. AXNodeID dst_id) const {
  879. DCHECK(IsNodeIdIntListAttribute(attr));
  880. // Conceptually, this is the "const" version of:
  881. // return intlist_reverse_relations_[attr][dst_id];
  882. const auto& attr_relations = intlist_reverse_relations_.find(attr);
  883. if (attr_relations != intlist_reverse_relations_.end()) {
  884. const auto& result = attr_relations->second.find(dst_id);
  885. if (result != attr_relations->second.end())
  886. return result->second;
  887. }
  888. return std::set<AXNodeID>();
  889. }
  890. std::set<AXNodeID> AXTree::GetNodeIdsForChildTreeId(
  891. AXTreeID child_tree_id) const {
  892. // Conceptually, this is the "const" version of:
  893. // return child_tree_id_reverse_map_[child_tree_id];
  894. const auto& result = child_tree_id_reverse_map_.find(child_tree_id);
  895. if (result != child_tree_id_reverse_map_.end())
  896. return result->second;
  897. return std::set<AXNodeID>();
  898. }
  899. const std::set<AXTreeID> AXTree::GetAllChildTreeIds() const {
  900. std::set<AXTreeID> result;
  901. for (auto entry : child_tree_id_reverse_map_)
  902. result.insert(entry.first);
  903. return result;
  904. }
  905. bool AXTree::Unserialize(const AXTreeUpdate& update) {
  906. event_data_ = std::make_unique<AXEvent>();
  907. event_data_->event_from = update.event_from;
  908. event_data_->event_from_action = update.event_from_action;
  909. event_data_->event_intents = update.event_intents;
  910. base::ScopedClosureRunner clear_event_data(base::BindOnce(
  911. [](std::unique_ptr<AXEvent>* event_data) { event_data->reset(); },
  912. &event_data_));
  913. AXTreeUpdateState update_state(*this, update);
  914. const AXNodeID old_root_id = root_ ? root_->id() : kInvalidAXNodeID;
  915. // Accumulates the work that will be required to update the AXTree.
  916. // This allows us to notify observers of structure changes when the
  917. // tree is still in a stable and unchanged state.
  918. if (!ComputePendingChanges(update, &update_state))
  919. return false;
  920. // Log unserialize perf after early returns.
  921. SCOPED_UMA_HISTOGRAM_TIMER("Accessibility.Performance.Tree.Unserialize");
  922. // Notify observers of subtrees and nodes that are about to be destroyed or
  923. // reparented, this must be done before applying any updates to the tree.
  924. for (auto&& pair : update_state.node_id_to_pending_data) {
  925. const AXNodeID node_id = pair.first;
  926. const std::unique_ptr<PendingStructureChanges>& data = pair.second;
  927. if (data->DoesNodeExpectSubtreeOrNodeWillBeDestroyed()) {
  928. if (AXNode* node = GetFromId(node_id)) {
  929. if (data->DoesNodeExpectSubtreeWillBeDestroyed())
  930. NotifySubtreeWillBeReparentedOrDeleted(node, &update_state);
  931. if (data->DoesNodeExpectNodeWillBeDestroyed())
  932. NotifyNodeWillBeReparentedOrDeleted(node, &update_state);
  933. }
  934. }
  935. }
  936. // Notify observers of nodes that are about to change their ignored state or
  937. // their data. This must be done before applying any updates to the tree. This
  938. // is iterating in reverse order so that we only notify once per node id, and
  939. // so that we only notify the initial node data against the final node data,
  940. // unless the node is a new root.
  941. std::set<AXNodeID> notified_node_attributes_will_change;
  942. for (const auto& new_data : base::Reversed(update_state.updated_nodes)) {
  943. const bool is_new_root =
  944. update_state.root_will_be_created && new_data.id == update.root_id;
  945. if (is_new_root)
  946. continue;
  947. AXNode* node = GetFromId(new_data.id);
  948. if (node &&
  949. notified_node_attributes_will_change.insert(new_data.id).second) {
  950. NotifyNodeAttributesWillChange(
  951. node,
  952. update_state.old_tree_data ? &update_state.old_tree_data.value()
  953. : nullptr,
  954. node->data(),
  955. update_state.new_tree_data ? &update_state.new_tree_data.value()
  956. : nullptr,
  957. new_data);
  958. }
  959. }
  960. // Now that we have finished sending events for changes that will happen,
  961. // set update state to true. |tree_update_in_progress_| gets set back to
  962. // false whenever this function exits.
  963. std::vector<AXTreeObserver::Change> changes;
  964. {
  965. ScopedTreeUpdateInProgressStateSetter tree_update_in_progress(*this);
  966. // Update the tree data. Do not call `UpdateDataForTesting` since this
  967. // method should be used only for testing, but importantly, we want to defer
  968. // the `OnTreeDataChanged` event until after the tree has finished updating.
  969. if (update_state.new_tree_data)
  970. data_ = update.tree_data;
  971. // Handle |node_id_to_clear| before applying ordinary node updates.
  972. // We distinguish between updating the root, e.g. changing its children or
  973. // some of its attributes, or replacing the root completely. If the root is
  974. // being updated, update.node_id_to_clear should hold the current root's ID.
  975. // Otherwise if the root is being replaced, update.root_id should hold the
  976. // ID of the new root.
  977. bool root_updated = false;
  978. if (update.node_id_to_clear != kInvalidAXNodeID) {
  979. // If the incoming tree was initialized with a root with an id != 1, the
  980. // update won't match the tree created by CreateEmptyDocument In this
  981. // case, the update won't be able to set the right node_id_to_clear.
  982. // If node_id_to_clear was set and the update's root_id doesn't match the
  983. // old_root_id, we assume that the update meant to replace the root.
  984. int node_id_to_clear = update.node_id_to_clear;
  985. if (!GetFromId(node_id_to_clear) && update.root_id == node_id_to_clear &&
  986. update.root_id != old_root_id && root_) {
  987. node_id_to_clear = old_root_id;
  988. }
  989. if (AXNode* cleared_node = GetFromId(node_id_to_clear)) {
  990. DCHECK(root_);
  991. if (cleared_node == root_) {
  992. // Only destroy the root if the root was replaced and not if it's
  993. // simply updated. To figure out if the root was simply updated, we
  994. // compare the ID of the new root with the existing root ID.
  995. if (update.root_id != old_root_id) {
  996. // Clear root_ before calling DestroySubtree so that root_ doesn't
  997. // ever point to an invalid node.
  998. AXNode* old_root = root_;
  999. root_ = nullptr;
  1000. DestroySubtree(old_root, &update_state);
  1001. } else {
  1002. // If the root has simply been updated, we treat it like an update
  1003. // to any other node.
  1004. root_updated = true;
  1005. }
  1006. }
  1007. // If the tree doesn't exists any more because the root has just been
  1008. // replaced, there is nothing more to clear.
  1009. if (root_) {
  1010. for (auto* child : cleared_node->children())
  1011. DestroySubtree(child, &update_state);
  1012. std::vector<AXNode*> children;
  1013. cleared_node->SwapChildren(&children);
  1014. update_state.pending_node_ids.insert(cleared_node->id());
  1015. }
  1016. }
  1017. }
  1018. DCHECK_EQ(!GetFromId(update.root_id), update_state.root_will_be_created);
  1019. // Update all of the nodes in the update.
  1020. for (const AXNodeData& updated_node_data : update_state.updated_nodes) {
  1021. const bool is_new_root = update_state.root_will_be_created &&
  1022. updated_node_data.id == update.root_id;
  1023. if (!UpdateNode(updated_node_data, is_new_root, &update_state))
  1024. return false;
  1025. }
  1026. if (!root_) {
  1027. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1028. AXTreeUnserializeError::kNoRoot);
  1029. RecordError(update_state, "Tree has no root.");
  1030. return false;
  1031. }
  1032. if (!ValidatePendingChangesComplete(update_state))
  1033. return false;
  1034. changes.reserve(update_state.updated_nodes.size());
  1035. // Look for changes to nodes that are a descendant of a table,
  1036. // and invalidate their table info if so. We have to walk up the
  1037. // ancestry of every node that was updated potentially, so keep track of
  1038. // ids that were checked to eliminate duplicate work.
  1039. std::set<AXNodeID> table_ids_checked;
  1040. for (const AXNodeData& node_data : update_state.updated_nodes) {
  1041. AXNode* node = GetFromId(node_data.id);
  1042. while (node) {
  1043. if (table_ids_checked.find(node->id()) != table_ids_checked.end())
  1044. break;
  1045. // Remove any table infos.
  1046. const auto& table_info_entry = table_info_map_.find(node->id());
  1047. if (table_info_entry != table_info_map_.end()) {
  1048. table_info_entry->second->Invalidate();
  1049. #if defined(AX_EXTRA_MAC_NODES)
  1050. // It will emit children changed notification on mac to make sure that
  1051. // extra mac accessibles are recreated.
  1052. changes.emplace_back(node, AXTreeObserver::NODE_CHANGED);
  1053. #endif
  1054. }
  1055. table_ids_checked.insert(node->id());
  1056. node = node->parent();
  1057. }
  1058. }
  1059. // Clears |node_set_size_pos_in_set_info_map_|
  1060. node_set_size_pos_in_set_info_map_.clear();
  1061. std::set<AXNodeID> visited_observer_changes;
  1062. for (const AXNodeData& updated_node_data : update_state.updated_nodes) {
  1063. AXNode* node = GetFromId(updated_node_data.id);
  1064. if (!node ||
  1065. !visited_observer_changes.emplace(updated_node_data.id).second)
  1066. continue;
  1067. bool is_new_node = update_state.IsCreatedNode(node);
  1068. bool is_reparented_node = update_state.IsReparentedNode(node);
  1069. AXTreeObserver::ChangeType change = AXTreeObserver::NODE_CHANGED;
  1070. if (is_new_node) {
  1071. if (is_reparented_node) {
  1072. // A reparented subtree is any new node whose parent either doesn't
  1073. // exist, or whose parent is not new.
  1074. // Note that we also need to check for the special case when we update
  1075. // the root without replacing it.
  1076. bool is_subtree = !node->parent() ||
  1077. !update_state.IsCreatedNode(node->parent()) ||
  1078. (node->parent() == root_ && root_updated);
  1079. change = is_subtree ? AXTreeObserver::SUBTREE_REPARENTED
  1080. : AXTreeObserver::NODE_REPARENTED;
  1081. } else {
  1082. // A new subtree is any new node whose parent is either not new, or
  1083. // whose parent happens to be new only because it has been reparented.
  1084. // Note that we also need to check for the special case when we update
  1085. // the root without replacing it.
  1086. bool is_subtree = !node->parent() ||
  1087. !update_state.IsCreatedNode(node->parent()) ||
  1088. update_state.IsRemovedNode(node->parent()) ||
  1089. (node->parent() == root_ && root_updated);
  1090. change = is_subtree ? AXTreeObserver::SUBTREE_CREATED
  1091. : AXTreeObserver::NODE_CREATED;
  1092. }
  1093. }
  1094. changes.push_back(AXTreeObserver::Change(node, change));
  1095. }
  1096. // Clear cached information in `AXComputedNodeData` for every node that has
  1097. // been changed in any way, including because of changes to one of its
  1098. // descendants.
  1099. std::set<AXNodeID> cleared_computed_node_data_ids;
  1100. for (AXNodeID node_id : update_state.node_data_changed_ids) {
  1101. AXNode* node = GetFromId(node_id);
  1102. while (node) {
  1103. if (cleared_computed_node_data_ids.insert(node->id()).second)
  1104. node->ClearComputedNodeData();
  1105. node = node->parent();
  1106. }
  1107. }
  1108. // Update the unignored cached values as necessary, ensuring that we only
  1109. // update once for each unignored node.
  1110. // If the node is ignored, we must update from an unignored ancestor.
  1111. std::set<AXNodeID> updated_unignored_cached_values_ids;
  1112. for (AXNodeID node_id :
  1113. update_state.invalidate_unignored_cached_values_ids) {
  1114. AXNode* unignored_ancestor = GetUnignoredAncestorFromId(node_id);
  1115. if (unignored_ancestor &&
  1116. updated_unignored_cached_values_ids.insert(unignored_ancestor->id())
  1117. .second) {
  1118. unignored_ancestor->UpdateUnignoredCachedValues();
  1119. }
  1120. }
  1121. } // tree_update_in_progress.
  1122. if (update_state.old_tree_data) {
  1123. DCHECK(update.has_tree_data)
  1124. << "If `UpdateState::old_tree_data` exists, then there must be a "
  1125. "request to update the tree data.";
  1126. // Now that the tree is stable and its nodes have been updated, notify if
  1127. // the tree data changed. We must do this after updating nodes in case the
  1128. // root has been replaced, so observers have the most up-to-date
  1129. // information.
  1130. for (AXTreeObserver& observer : observers_)
  1131. observer.OnTreeDataChanged(this, *update_state.old_tree_data, data_);
  1132. }
  1133. // Now that the unignored cached values are up to date, notify observers of
  1134. // the nodes that were deleted from the tree but not reparented.
  1135. for (AXNodeID node_id : update_state.removed_node_ids) {
  1136. if (!update_state.IsCreatedNode(node_id))
  1137. NotifyNodeHasBeenDeleted(node_id);
  1138. }
  1139. // Now that the unignored cached values are up to date, notify observers of
  1140. // new nodes in the tree.
  1141. for (AXNodeID node_id : update_state.new_node_ids) {
  1142. AXNode* node = GetFromId(node_id);
  1143. if (node)
  1144. NotifyNodeHasBeenReparentedOrCreated(node, &update_state);
  1145. }
  1146. // Now that the unignored cached values are up to date, notify observers of
  1147. // node changes.
  1148. for (AXNodeID changed_id : update_state.node_data_changed_ids) {
  1149. AXNode* node = GetFromId(changed_id);
  1150. DCHECK(node);
  1151. // If the node exists and is in the old data map, then the node data
  1152. // may have changed unless this is a new root.
  1153. const bool is_new_root =
  1154. update_state.root_will_be_created && changed_id == update.root_id;
  1155. if (!is_new_root) {
  1156. auto it = update_state.old_node_id_to_data.find(changed_id);
  1157. if (it != update_state.old_node_id_to_data.end()) {
  1158. NotifyNodeAttributesHaveBeenChanged(
  1159. node,
  1160. update_state.old_tree_data ? &update_state.old_tree_data.value()
  1161. : nullptr,
  1162. it->second,
  1163. update_state.new_tree_data ? &update_state.new_tree_data.value()
  1164. : nullptr,
  1165. node->data());
  1166. }
  1167. }
  1168. // |OnNodeChanged| should be fired for all nodes that have been updated.
  1169. for (AXTreeObserver& observer : observers_)
  1170. observer.OnNodeChanged(this, node);
  1171. }
  1172. for (AXTreeObserver& observer : observers_)
  1173. observer.OnAtomicUpdateFinished(this, root_->id() != old_root_id, changes);
  1174. return true;
  1175. }
  1176. AXTableInfo* AXTree::GetTableInfo(const AXNode* const_table_node) const {
  1177. DCHECK(!GetTreeUpdateInProgressState());
  1178. // Note: the const_casts are here because we want this function to be able
  1179. // to be called from a const virtual function on AXNode. AXTableInfo is
  1180. // computed on demand and cached, but that's an implementation detail
  1181. // we want to hide from users of this API.
  1182. AXNode* table_node = const_cast<AXNode*>(const_table_node);
  1183. AXTree* tree = const_cast<AXTree*>(this);
  1184. DCHECK(table_node);
  1185. const auto& cached = table_info_map_.find(table_node->id());
  1186. if (cached != table_info_map_.end()) {
  1187. // Get existing table info, and update if invalid because the
  1188. // tree has changed since the last time we accessed it.
  1189. AXTableInfo* table_info = cached->second.get();
  1190. if (!table_info->valid()) {
  1191. if (!table_info->Update()) {
  1192. // If Update() returned false, this is no longer a valid table.
  1193. // Remove it from the map.
  1194. table_info_map_.erase(table_node->id());
  1195. return nullptr;
  1196. }
  1197. }
  1198. return table_info;
  1199. }
  1200. AXTableInfo* table_info = AXTableInfo::Create(tree, table_node);
  1201. if (!table_info)
  1202. return nullptr;
  1203. table_info_map_[table_node->id()] = base::WrapUnique<AXTableInfo>(table_info);
  1204. return table_info;
  1205. }
  1206. std::string AXTree::ToString() const {
  1207. return "AXTree" + data_.ToString() + "\n" + TreeToStringHelper(root_, 0);
  1208. }
  1209. AXNode* AXTree::CreateNode(AXNode* parent,
  1210. AXNodeID id,
  1211. size_t index_in_parent,
  1212. AXTreeUpdateState* update_state) {
  1213. DCHECK(GetTreeUpdateInProgressState());
  1214. // |update_state| must already contain information about all of the expected
  1215. // changes and invalidations to apply. If any of these are missing, observers
  1216. // may not be notified of changes.
  1217. DCHECK(!GetFromId(id));
  1218. DCHECK_GT(update_state->GetPendingCreateNodeCount(id), 0);
  1219. DCHECK(update_state->InvalidatesUnignoredCachedValues(id));
  1220. DCHECK(!parent ||
  1221. update_state->InvalidatesUnignoredCachedValues(parent->id()));
  1222. update_state->DecrementPendingCreateNodeCount(id);
  1223. update_state->new_node_ids.insert(id);
  1224. // If this node is the root, use the given index_in_parent as the unignored
  1225. // index in parent to provide consistency with index_in_parent.
  1226. auto node = std::make_unique<AXNode>(this, parent, id, index_in_parent,
  1227. parent ? 0 : index_in_parent);
  1228. auto emplaced = id_map_.emplace(id, std::move(node));
  1229. // There should not have been a node already in the map with the same id.
  1230. DCHECK(emplaced.second);
  1231. return emplaced.first->second.get();
  1232. }
  1233. bool AXTree::ComputePendingChanges(const AXTreeUpdate& update,
  1234. AXTreeUpdateState* update_state) {
  1235. DCHECK_EQ(AXTreePendingStructureStatus::kNotStarted,
  1236. update_state->pending_update_status)
  1237. << "Pending changes have already started being computed.";
  1238. update_state->pending_update_status =
  1239. AXTreePendingStructureStatus::kComputing;
  1240. // The ID of the current root is temporarily stored in `update_state`, but
  1241. // reset after all pending updates have been computed in order to avoid stale
  1242. // data hanging around.
  1243. base::AutoReset<absl::optional<AXNodeID>> pending_root_id_resetter(
  1244. &update_state->pending_root_id,
  1245. root_ ? absl::make_optional<AXNodeID>(root_->id()) : absl::nullopt);
  1246. if (update.has_tree_data && data_ != update.tree_data) {
  1247. update_state->old_tree_data = data_;
  1248. update_state->new_tree_data = update.tree_data;
  1249. }
  1250. update_state->updated_nodes = update.nodes;
  1251. // We distinguish between updating the root, e.g. changing its children or
  1252. // some of its attributes, or replacing the root completely. If the root is
  1253. // being updated, update.node_id_to_clear should hold the current root's ID.
  1254. // Otherwise if the root is being replaced, update.root_id should hold the ID
  1255. // of the new root.
  1256. if (update.node_id_to_clear != kInvalidAXNodeID) {
  1257. if (AXNode* cleared_node = GetFromId(update.node_id_to_clear)) {
  1258. DCHECK(root_);
  1259. if (cleared_node == root_ &&
  1260. update.root_id != update_state->pending_root_id) {
  1261. // Only destroy the root if the root was replaced and not if it's simply
  1262. // updated. To figure out if the root was simply updated, we compare
  1263. // the ID of the new root with the existing root ID.
  1264. MarkSubtreeForDestruction(*update_state->pending_root_id, update_state);
  1265. }
  1266. // If the tree has been marked for destruction because the root will be
  1267. // replaced, there is nothing more to clear.
  1268. if (update_state->ShouldPendingNodeExistInTree(root_->id())) {
  1269. update_state->invalidate_unignored_cached_values_ids.insert(
  1270. cleared_node->id());
  1271. update_state->ClearLastKnownPendingNodeData(cleared_node->id());
  1272. for (AXNode* child : cleared_node->children()) {
  1273. MarkSubtreeForDestruction(child->id(), update_state);
  1274. }
  1275. }
  1276. }
  1277. }
  1278. if (is_focused_node_always_unignored_ && update_state->old_tree_data &&
  1279. update_state->new_tree_data) {
  1280. // Ensure that if the focused node has changed, any unignored cached values
  1281. // would be invalidated on both the previous as well as the new focus, in
  1282. // cases where their ignored state will be affected. This block is necessary
  1283. // in the rare situation when the focus node has changed but the previous or
  1284. // new focused nodes are not in the list of updated nodes, because their
  1285. // data has not been modified.
  1286. // TODO(nektar): This check is erroneous: It's missing a check of
  1287. // focused_tree_id. Fix after updating `AXNode::IsFocusedInThisTree`.
  1288. if (update_state->old_tree_data->focus_id != kInvalidAXNodeID) {
  1289. const AXNode* old_focus =
  1290. GetFromId(update_state->old_tree_data->focus_id);
  1291. if (old_focus &&
  1292. update_state->ShouldPendingNodeExistInTree(old_focus->id()) &&
  1293. std::find_if(update_state->updated_nodes.begin(),
  1294. update_state->updated_nodes.end(),
  1295. [old_focus](const AXNodeData& data) {
  1296. return data.id == old_focus->id();
  1297. }) == update_state->updated_nodes.end()) {
  1298. update_state->updated_nodes.push_back(old_focus->data());
  1299. }
  1300. }
  1301. if (update_state->new_tree_data->focus_id != kInvalidAXNodeID) {
  1302. const AXNode* new_focus =
  1303. GetFromId(update_state->new_tree_data->focus_id);
  1304. if (new_focus &&
  1305. update_state->ShouldPendingNodeExistInTree(new_focus->id()) &&
  1306. std::find_if(update_state->updated_nodes.begin(),
  1307. update_state->updated_nodes.end(),
  1308. [new_focus](const AXNodeData& data) {
  1309. return data.id == new_focus->id();
  1310. }) == update_state->updated_nodes.end()) {
  1311. update_state->updated_nodes.push_back(new_focus->data());
  1312. }
  1313. }
  1314. }
  1315. update_state->root_will_be_created =
  1316. !GetFromId(update.root_id) ||
  1317. !update_state->ShouldPendingNodeExistInTree(update.root_id);
  1318. // Populate |update_state| with all of the changes that will be performed
  1319. // on the tree during the update.
  1320. for (const AXNodeData& new_data : update_state->updated_nodes) {
  1321. bool is_new_root =
  1322. update_state->root_will_be_created && new_data.id == update.root_id;
  1323. if (!ComputePendingChangesToNode(new_data, is_new_root, update_state)) {
  1324. update_state->pending_update_status =
  1325. AXTreePendingStructureStatus::kFailed;
  1326. return false;
  1327. }
  1328. }
  1329. update_state->pending_update_status = AXTreePendingStructureStatus::kComplete;
  1330. return true;
  1331. }
  1332. bool AXTree::ComputePendingChangesToNode(const AXNodeData& new_data,
  1333. bool is_new_root,
  1334. AXTreeUpdateState* update_state) {
  1335. // Compare every child's index in parent in the update with the existing
  1336. // index in parent. If the order has changed, invalidate the cached
  1337. // unignored index in parent.
  1338. for (size_t j = 0; j < new_data.child_ids.size(); j++) {
  1339. const AXNode* node = GetFromId(new_data.child_ids[j]);
  1340. if (node && node->GetIndexInParent() != j)
  1341. update_state->InvalidateParentNodeUnignoredCacheValues(node->id());
  1342. }
  1343. // If the node does not exist in the tree throw an error unless this
  1344. // is the new root and it can be created.
  1345. if (!update_state->ShouldPendingNodeExistInTree(new_data.id)) {
  1346. if (!is_new_root) {
  1347. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1348. AXTreeUnserializeError::kNotInTree);
  1349. RecordError(*update_state,
  1350. base::StringPrintf(
  1351. "%d will not be in the tree and is not the new root",
  1352. new_data.id));
  1353. return false;
  1354. }
  1355. // Creation is implicit for new root nodes. If |new_data.id| is already
  1356. // pending for creation, then it must be a duplicate entry in the tree.
  1357. if (!update_state->IncrementPendingCreateNodeCount(new_data.id,
  1358. absl::nullopt)) {
  1359. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1360. AXTreeUnserializeError::kCreationPending);
  1361. RecordError(
  1362. *update_state,
  1363. base::StringPrintf(
  1364. "Node %d is already pending for creation, cannot be the new root",
  1365. new_data.id));
  1366. return false;
  1367. }
  1368. if (update_state->pending_root_id) {
  1369. MarkSubtreeForDestruction(*update_state->pending_root_id, update_state);
  1370. }
  1371. update_state->pending_root_id = new_data.id;
  1372. }
  1373. // Create a set of new child ids so we can use it to find the nodes that
  1374. // have been added and removed. Returns false if a duplicate is found.
  1375. std::set<AXNodeID> new_child_id_set;
  1376. for (AXNodeID new_child_id : new_data.child_ids) {
  1377. if (base::Contains(new_child_id_set, new_child_id)) {
  1378. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1379. AXTreeUnserializeError::kDuplicateChild);
  1380. RecordError(*update_state,
  1381. base::StringPrintf("Node %d has duplicate child id %d",
  1382. new_data.id, new_child_id));
  1383. return false;
  1384. }
  1385. new_child_id_set.insert(new_child_id);
  1386. }
  1387. // If the node has not been initialized yet then its node data has either been
  1388. // cleared when handling |node_id_to_clear|, or it's a new node.
  1389. // In either case, all children must be created.
  1390. if (update_state->DoesPendingNodeRequireInit(new_data.id)) {
  1391. update_state->invalidate_unignored_cached_values_ids.insert(new_data.id);
  1392. // If this node has been cleared via |node_id_to_clear| or is a new node,
  1393. // the last-known parent's unignored cache needs to be updated.
  1394. update_state->InvalidateParentNodeUnignoredCacheValues(new_data.id);
  1395. for (AXNodeID child_id : new_child_id_set) {
  1396. // If a |child_id| is already pending for creation, then it must be a
  1397. // duplicate entry in the tree.
  1398. update_state->invalidate_unignored_cached_values_ids.insert(child_id);
  1399. if (!update_state->IncrementPendingCreateNodeCount(child_id,
  1400. new_data.id)) {
  1401. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1402. AXTreeUnserializeError::kCreationPendingForChild);
  1403. RecordError(*update_state,
  1404. base::StringPrintf("Node %d is already pending for "
  1405. "creation, cannot be a new child",
  1406. child_id));
  1407. return false;
  1408. }
  1409. }
  1410. update_state->SetLastKnownPendingNodeData(&new_data);
  1411. return true;
  1412. }
  1413. const AXNodeData& old_data =
  1414. update_state->GetLastKnownPendingNodeData(new_data.id);
  1415. // Create a set of old child ids so we can use it to find the nodes that
  1416. // have been added and removed.
  1417. std::set<AXNodeID> old_child_id_set(old_data.child_ids.cbegin(),
  1418. old_data.child_ids.cend());
  1419. std::vector<AXNodeID> create_or_destroy_ids;
  1420. std::set_symmetric_difference(
  1421. old_child_id_set.cbegin(), old_child_id_set.cend(),
  1422. new_child_id_set.cbegin(), new_child_id_set.cend(),
  1423. std::back_inserter(create_or_destroy_ids));
  1424. // If the node has changed ignored state or there are any differences in
  1425. // its children, then its unignored cached values must be invalidated.
  1426. if (!create_or_destroy_ids.empty() ||
  1427. update_state->HasIgnoredChanged(new_data)) {
  1428. update_state->invalidate_unignored_cached_values_ids.insert(new_data.id);
  1429. // If this ignored state had changed also invalidate the parent.
  1430. update_state->InvalidateParentNodeUnignoredCacheValues(new_data.id);
  1431. }
  1432. for (AXNodeID child_id : create_or_destroy_ids) {
  1433. if (base::Contains(new_child_id_set, child_id)) {
  1434. // This is a serious error - nodes should never be reparented without
  1435. // first being removed from the tree. If a node exists in the tree already
  1436. // then adding it to a new parent would mean stealing the node from its
  1437. // old parent which hadn't been updated to reflect the change.
  1438. if (update_state->ShouldPendingNodeExistInTree(child_id)) {
  1439. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1440. AXTreeUnserializeError::kReparent);
  1441. RecordError(*update_state,
  1442. base::StringPrintf("Node %d is not marked for destruction, "
  1443. "would be reparented to %d",
  1444. child_id, new_data.id));
  1445. return false;
  1446. }
  1447. // If a |child_id| is already pending for creation, then it must be a
  1448. // duplicate entry in the tree.
  1449. update_state->invalidate_unignored_cached_values_ids.insert(child_id);
  1450. if (!update_state->IncrementPendingCreateNodeCount(child_id,
  1451. new_data.id)) {
  1452. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1453. AXTreeUnserializeError::kCreationPendingForChild);
  1454. RecordError(*update_state,
  1455. base::StringPrintf("Node %d is already pending for "
  1456. "creation, cannot be a new child",
  1457. child_id));
  1458. return false;
  1459. }
  1460. } else {
  1461. // If |child_id| does not exist in the new set, then it has
  1462. // been removed from |node|, and the subtree must be deleted.
  1463. MarkSubtreeForDestruction(child_id, update_state);
  1464. }
  1465. }
  1466. update_state->SetLastKnownPendingNodeData(&new_data);
  1467. return true;
  1468. }
  1469. bool AXTree::UpdateNode(const AXNodeData& src,
  1470. bool is_new_root,
  1471. AXTreeUpdateState* update_state) {
  1472. DCHECK(GetTreeUpdateInProgressState());
  1473. // This method updates one node in the tree based on serialized data
  1474. // received in an AXTreeUpdate. See AXTreeUpdate for pre and post
  1475. // conditions.
  1476. // Look up the node by id. If it's not found, then either the root
  1477. // of the tree is being swapped, or we're out of sync with the source
  1478. // and this is a serious error.
  1479. AXNode* node = GetFromId(src.id);
  1480. if (node) {
  1481. update_state->pending_node_ids.erase(node->id());
  1482. UpdateReverseRelations(node, src);
  1483. if (!update_state->IsCreatedNode(node) ||
  1484. update_state->IsReparentedNode(node)) {
  1485. update_state->old_node_id_to_data.insert(
  1486. std::make_pair(node->id(), node->TakeData()));
  1487. }
  1488. node->SetData(src);
  1489. } else {
  1490. if (!is_new_root) {
  1491. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1492. AXTreeUnserializeError::kNotInTree);
  1493. RecordError(*update_state,
  1494. base::StringPrintf(
  1495. "%d is not in the tree and not the new root", src.id));
  1496. return false;
  1497. }
  1498. node = CreateNode(nullptr, src.id, 0, update_state);
  1499. UpdateReverseRelations(node, src);
  1500. node->SetData(src);
  1501. }
  1502. // If we come across a page breaking object, mark the tree as a paginated root
  1503. if (src.GetBoolAttribute(ax::mojom::BoolAttribute::kIsPageBreakingObject))
  1504. has_pagination_support_ = true;
  1505. update_state->node_data_changed_ids.insert(node->id());
  1506. // First, delete nodes that used to be children of this node but aren't
  1507. // anymore.
  1508. DeleteOldChildren(node, src.child_ids, update_state);
  1509. // Now build a new children vector, reusing nodes when possible,
  1510. // and swap it in.
  1511. std::vector<AXNode*> new_children;
  1512. bool success = CreateNewChildVector(
  1513. node, src.child_ids, &new_children, update_state);
  1514. node->SwapChildren(&new_children);
  1515. // Update the root of the tree if needed.
  1516. if (is_new_root) {
  1517. // Make sure root_ always points to something valid or null_, even inside
  1518. // DestroySubtree.
  1519. AXNode* old_root = root_;
  1520. root_ = node;
  1521. if (old_root && old_root != node)
  1522. DestroySubtree(old_root, update_state);
  1523. }
  1524. return success;
  1525. }
  1526. void AXTree::NotifySubtreeWillBeReparentedOrDeleted(
  1527. AXNode* node,
  1528. const AXTreeUpdateState* update_state) {
  1529. DCHECK(!GetTreeUpdateInProgressState());
  1530. if (node->id() == kInvalidAXNodeID)
  1531. return;
  1532. for (AXTreeObserver& observer : observers_) {
  1533. if (update_state->IsReparentedNode(node)) {
  1534. observer.OnSubtreeWillBeReparented(this, node);
  1535. } else {
  1536. observer.OnSubtreeWillBeDeleted(this, node);
  1537. }
  1538. }
  1539. }
  1540. void AXTree::NotifyNodeWillBeReparentedOrDeleted(
  1541. AXNode* node,
  1542. const AXTreeUpdateState* update_state) {
  1543. DCHECK(!GetTreeUpdateInProgressState());
  1544. AXNodeID id = node->id();
  1545. if (id == kInvalidAXNodeID)
  1546. return;
  1547. table_info_map_.erase(id);
  1548. for (AXTreeObserver& observer : observers_) {
  1549. if (update_state->IsReparentedNode(node)) {
  1550. observer.OnNodeWillBeReparented(this, node);
  1551. } else {
  1552. observer.OnNodeWillBeDeleted(this, node);
  1553. }
  1554. }
  1555. DCHECK(table_info_map_.find(id) == table_info_map_.end())
  1556. << "Table info should never be recreated during node deletion";
  1557. }
  1558. void AXTree::RecursivelyNotifyNodeDeletedForTreeTeardown(AXNode* node) {
  1559. DCHECK(!GetTreeUpdateInProgressState());
  1560. if (node->id() == kInvalidAXNodeID)
  1561. return;
  1562. for (AXTreeObserver& observer : observers_)
  1563. observer.OnNodeDeleted(this, node->id());
  1564. for (auto* child : node->children())
  1565. RecursivelyNotifyNodeDeletedForTreeTeardown(child);
  1566. }
  1567. void AXTree::NotifyNodeHasBeenDeleted(AXNodeID node_id) {
  1568. DCHECK(!GetTreeUpdateInProgressState());
  1569. if (node_id == kInvalidAXNodeID)
  1570. return;
  1571. for (AXTreeObserver& observer : observers_)
  1572. observer.OnNodeDeleted(this, node_id);
  1573. }
  1574. void AXTree::NotifyNodeHasBeenReparentedOrCreated(
  1575. AXNode* node,
  1576. const AXTreeUpdateState* update_state) {
  1577. DCHECK(!GetTreeUpdateInProgressState());
  1578. if (node->id() == kInvalidAXNodeID)
  1579. return;
  1580. for (AXTreeObserver& observer : observers_) {
  1581. if (update_state->IsReparentedNode(node)) {
  1582. observer.OnNodeReparented(this, node);
  1583. } else {
  1584. observer.OnNodeCreated(this, node);
  1585. }
  1586. }
  1587. }
  1588. void AXTree::NotifyNodeAttributesWillChange(
  1589. AXNode* node,
  1590. const AXTreeData* optional_old_tree_data,
  1591. const AXNodeData& old_data,
  1592. const AXTreeData* optional_new_tree_data,
  1593. const AXNodeData& new_data) {
  1594. DCHECK(!GetTreeUpdateInProgressState());
  1595. if (new_data.id == kInvalidAXNodeID)
  1596. return;
  1597. for (AXTreeObserver& observer : observers_)
  1598. observer.OnNodeDataWillChange(this, old_data, new_data);
  1599. if (ComputeNodeIsIgnoredChanged(optional_old_tree_data, old_data,
  1600. optional_new_tree_data, new_data)) {
  1601. for (AXTreeObserver& observer : observers_)
  1602. observer.OnIgnoredWillChange(this, node, !node->IsIgnored());
  1603. }
  1604. }
  1605. void AXTree::NotifyNodeAttributesHaveBeenChanged(
  1606. AXNode* node,
  1607. const AXTreeData* optional_old_tree_data,
  1608. const AXNodeData& old_data,
  1609. const AXTreeData* optional_new_tree_data,
  1610. const AXNodeData& new_data) {
  1611. DCHECK(!GetTreeUpdateInProgressState());
  1612. if (node->id() == kInvalidAXNodeID)
  1613. return;
  1614. for (AXTreeObserver& observer : observers_)
  1615. observer.OnNodeDataChanged(this, old_data, new_data);
  1616. if (old_data.role != new_data.role) {
  1617. for (AXTreeObserver& observer : observers_)
  1618. observer.OnRoleChanged(this, node, old_data.role, new_data.role);
  1619. }
  1620. if (ComputeNodeIsIgnoredChanged(optional_old_tree_data, old_data,
  1621. optional_new_tree_data, new_data)) {
  1622. for (AXTreeObserver& observer : observers_)
  1623. observer.OnIgnoredChanged(this, node, node->IsIgnored());
  1624. }
  1625. if (old_data.state != new_data.state) {
  1626. for (int32_t i = static_cast<int32_t>(ax::mojom::State::kNone) + 1;
  1627. i <= static_cast<int32_t>(ax::mojom::State::kMaxValue); ++i) {
  1628. ax::mojom::State state = static_cast<ax::mojom::State>(i);
  1629. // The ignored state has been already handled via `OnIgnoredChanged`.
  1630. if (state == ax::mojom::State::kIgnored)
  1631. continue;
  1632. if (old_data.HasState(state) != new_data.HasState(state)) {
  1633. for (AXTreeObserver& observer : observers_)
  1634. observer.OnStateChanged(this, node, state, new_data.HasState(state));
  1635. }
  1636. }
  1637. }
  1638. auto string_callback = [this, node](ax::mojom::StringAttribute attr,
  1639. const std::string& old_string,
  1640. const std::string& new_string) {
  1641. DCHECK_NE(old_string, new_string);
  1642. for (AXTreeObserver& observer : observers_) {
  1643. observer.OnStringAttributeChanged(this, node, attr, old_string,
  1644. new_string);
  1645. }
  1646. };
  1647. CallIfAttributeValuesChanged(old_data.string_attributes,
  1648. new_data.string_attributes, std::string(),
  1649. string_callback);
  1650. auto bool_callback = [this, node](ax::mojom::BoolAttribute attr,
  1651. const bool& old_bool,
  1652. const bool& new_bool) {
  1653. DCHECK_NE(old_bool, new_bool);
  1654. for (AXTreeObserver& observer : observers_)
  1655. observer.OnBoolAttributeChanged(this, node, attr, new_bool);
  1656. };
  1657. CallIfAttributeValuesChanged(old_data.bool_attributes,
  1658. new_data.bool_attributes, false, bool_callback);
  1659. auto float_callback = [this, node](ax::mojom::FloatAttribute attr,
  1660. const float& old_float,
  1661. const float& new_float) {
  1662. DCHECK_NE(old_float, new_float);
  1663. for (AXTreeObserver& observer : observers_)
  1664. observer.OnFloatAttributeChanged(this, node, attr, old_float, new_float);
  1665. };
  1666. CallIfAttributeValuesChanged(old_data.float_attributes,
  1667. new_data.float_attributes, 0.0f, float_callback);
  1668. auto int_callback = [this, node](ax::mojom::IntAttribute attr,
  1669. const int& old_int, const int& new_int) {
  1670. DCHECK_NE(old_int, new_int);
  1671. for (AXTreeObserver& observer : observers_)
  1672. observer.OnIntAttributeChanged(this, node, attr, old_int, new_int);
  1673. };
  1674. CallIfAttributeValuesChanged(old_data.int_attributes, new_data.int_attributes,
  1675. 0, int_callback);
  1676. auto intlist_callback = [this, node](
  1677. ax::mojom::IntListAttribute attr,
  1678. const std::vector<int32_t>& old_intlist,
  1679. const std::vector<int32_t>& new_intlist) {
  1680. for (AXTreeObserver& observer : observers_)
  1681. observer.OnIntListAttributeChanged(this, node, attr, old_intlist,
  1682. new_intlist);
  1683. };
  1684. CallIfAttributeValuesChanged(old_data.intlist_attributes,
  1685. new_data.intlist_attributes,
  1686. std::vector<int32_t>(), intlist_callback);
  1687. auto stringlist_callback =
  1688. [this, node](ax::mojom::StringListAttribute attr,
  1689. const std::vector<std::string>& old_stringlist,
  1690. const std::vector<std::string>& new_stringlist) {
  1691. for (AXTreeObserver& observer : observers_)
  1692. observer.OnStringListAttributeChanged(this, node, attr,
  1693. old_stringlist, new_stringlist);
  1694. };
  1695. CallIfAttributeValuesChanged(old_data.stringlist_attributes,
  1696. new_data.stringlist_attributes,
  1697. std::vector<std::string>(), stringlist_callback);
  1698. }
  1699. void AXTree::UpdateReverseRelations(AXNode* node, const AXNodeData& new_data) {
  1700. DCHECK(GetTreeUpdateInProgressState());
  1701. const AXNodeData& old_data = node->data();
  1702. int id = new_data.id;
  1703. auto int_callback = [this, id](ax::mojom::IntAttribute attr,
  1704. const int& old_id, const int& new_id) {
  1705. if (!IsNodeIdIntAttribute(attr))
  1706. return;
  1707. // Remove old_id -> id from the map, and clear map keys if their
  1708. // values are now empty.
  1709. auto& map = int_reverse_relations_[attr];
  1710. if (map.find(old_id) != map.end()) {
  1711. map[old_id].erase(id);
  1712. if (map[old_id].empty())
  1713. map.erase(old_id);
  1714. }
  1715. // Add new_id -> id to the map, unless new_id is zero indicating that
  1716. // we're only removing a relation.
  1717. if (new_id)
  1718. map[new_id].insert(id);
  1719. };
  1720. CallIfAttributeValuesChanged(old_data.int_attributes, new_data.int_attributes,
  1721. 0, int_callback);
  1722. auto intlist_callback = [this, id](ax::mojom::IntListAttribute attr,
  1723. const std::vector<int32_t>& old_idlist,
  1724. const std::vector<int32_t>& new_idlist) {
  1725. if (!IsNodeIdIntListAttribute(attr))
  1726. return;
  1727. auto& map = intlist_reverse_relations_[attr];
  1728. for (AXNodeID old_id : old_idlist) {
  1729. if (map.find(old_id) != map.end()) {
  1730. map[old_id].erase(id);
  1731. if (map[old_id].empty())
  1732. map.erase(old_id);
  1733. }
  1734. }
  1735. for (AXNodeID new_id : new_idlist)
  1736. intlist_reverse_relations_[attr][new_id].insert(id);
  1737. };
  1738. CallIfAttributeValuesChanged(old_data.intlist_attributes,
  1739. new_data.intlist_attributes,
  1740. std::vector<AXNodeID>(), intlist_callback);
  1741. auto string_callback = [this, id](ax::mojom::StringAttribute attr,
  1742. const std::string& old_string,
  1743. const std::string& new_string) {
  1744. if (attr == ax::mojom::StringAttribute::kChildTreeId) {
  1745. // Remove old_string -> id from the map, and clear map keys if
  1746. // their values are now empty.
  1747. AXTreeID old_ax_tree_id = AXTreeID::FromString(old_string);
  1748. if (child_tree_id_reverse_map_.find(old_ax_tree_id) !=
  1749. child_tree_id_reverse_map_.end()) {
  1750. child_tree_id_reverse_map_[old_ax_tree_id].erase(id);
  1751. if (child_tree_id_reverse_map_[old_ax_tree_id].empty())
  1752. child_tree_id_reverse_map_.erase(old_ax_tree_id);
  1753. }
  1754. // Add new_string -> id to the map, unless new_id is zero indicating that
  1755. // we're only removing a relation.
  1756. if (!new_string.empty()) {
  1757. AXTreeID new_ax_tree_id = AXTreeID::FromString(new_string);
  1758. child_tree_id_reverse_map_[new_ax_tree_id].insert(id);
  1759. }
  1760. }
  1761. };
  1762. CallIfAttributeValuesChanged(old_data.string_attributes,
  1763. new_data.string_attributes, std::string(),
  1764. string_callback);
  1765. }
  1766. bool AXTree::ValidatePendingChangesComplete(
  1767. const AXTreeUpdateState& update_state) {
  1768. if (!update_state.pending_node_ids.empty()) {
  1769. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1770. AXTreeUnserializeError::kPendingNodes);
  1771. std::string error = "Nodes left pending by the update:";
  1772. for (const AXNodeID pending_id : update_state.pending_node_ids)
  1773. error += base::StringPrintf(" %d", pending_id);
  1774. RecordError(update_state, error);
  1775. return false;
  1776. }
  1777. if (!update_state.node_id_to_pending_data.empty()) {
  1778. std::string destroy_subtree_ids;
  1779. std::string destroy_node_ids;
  1780. std::string create_node_ids;
  1781. bool has_pending_changes = false;
  1782. for (auto&& pair : update_state.node_id_to_pending_data) {
  1783. const AXNodeID pending_id = pair.first;
  1784. const std::unique_ptr<PendingStructureChanges>& data = pair.second;
  1785. if (data->DoesNodeExpectAnyStructureChanges()) {
  1786. if (data->DoesNodeExpectSubtreeWillBeDestroyed())
  1787. destroy_subtree_ids += base::StringPrintf(" %d", pending_id);
  1788. if (data->DoesNodeExpectNodeWillBeDestroyed())
  1789. destroy_node_ids += base::StringPrintf(" %d", pending_id);
  1790. if (data->DoesNodeExpectNodeWillBeCreated())
  1791. create_node_ids += base::StringPrintf(" %d", pending_id);
  1792. has_pending_changes = true;
  1793. }
  1794. }
  1795. if (has_pending_changes) {
  1796. ACCESSIBILITY_TREE_UNSERIALIZE_ERROR_HISTOGRAM(
  1797. AXTreeUnserializeError::kPendingChanges);
  1798. RecordError(
  1799. update_state,
  1800. base::StringPrintf(
  1801. "Changes left pending by the update; "
  1802. "destroy subtrees: %s, destroy nodes: %s, create nodes: %s",
  1803. destroy_subtree_ids.c_str(), destroy_node_ids.c_str(),
  1804. create_node_ids.c_str()));
  1805. }
  1806. return !has_pending_changes;
  1807. }
  1808. return true;
  1809. }
  1810. void AXTree::MarkSubtreeForDestruction(AXNodeID node_id,
  1811. AXTreeUpdateState* update_state) {
  1812. update_state->IncrementPendingDestroySubtreeCount(node_id);
  1813. MarkNodesForDestructionRecursive(node_id, update_state);
  1814. }
  1815. void AXTree::MarkNodesForDestructionRecursive(AXNodeID node_id,
  1816. AXTreeUpdateState* update_state) {
  1817. // If this subtree has already been marked for destruction, return so
  1818. // we don't walk it again.
  1819. if (!update_state->ShouldPendingNodeExistInTree(node_id))
  1820. return;
  1821. const AXNodeData& last_known_data =
  1822. update_state->GetLastKnownPendingNodeData(node_id);
  1823. update_state->IncrementPendingDestroyNodeCount(node_id);
  1824. for (AXNodeID child_id : last_known_data.child_ids) {
  1825. MarkNodesForDestructionRecursive(child_id, update_state);
  1826. }
  1827. }
  1828. void AXTree::DestroySubtree(AXNode* node,
  1829. AXTreeUpdateState* update_state) {
  1830. DCHECK(GetTreeUpdateInProgressState());
  1831. // |update_state| must already contain information about all of the expected
  1832. // changes and invalidations to apply. If any of these are missing, observers
  1833. // may not be notified of changes.
  1834. DCHECK(update_state);
  1835. DCHECK_GT(update_state->GetPendingDestroySubtreeCount(node->id()), 0);
  1836. DCHECK(!node->parent() ||
  1837. update_state->InvalidatesUnignoredCachedValues(node->parent()->id()));
  1838. update_state->DecrementPendingDestroySubtreeCount(node->id());
  1839. DestroyNodeAndSubtree(node, update_state);
  1840. }
  1841. void AXTree::DestroyNodeAndSubtree(AXNode* node,
  1842. AXTreeUpdateState* update_state) {
  1843. DCHECK(GetTreeUpdateInProgressState());
  1844. DCHECK(!update_state ||
  1845. update_state->GetPendingDestroyNodeCount(node->id()) > 0);
  1846. // Clear out any reverse relations.
  1847. AXNodeData empty_data;
  1848. empty_data.id = node->id();
  1849. UpdateReverseRelations(node, empty_data);
  1850. AXNodeID id = node->id();
  1851. auto iter = id_map_.find(id);
  1852. std::unique_ptr<AXNode> node_to_delete = std::move(iter->second);
  1853. id_map_.erase(iter);
  1854. node = nullptr;
  1855. for (auto* child : node_to_delete->children())
  1856. DestroyNodeAndSubtree(child, update_state);
  1857. if (update_state) {
  1858. update_state->pending_node_ids.erase(id);
  1859. update_state->DecrementPendingDestroyNodeCount(id);
  1860. update_state->removed_node_ids.insert(id);
  1861. update_state->new_node_ids.erase(id);
  1862. update_state->node_data_changed_ids.erase(id);
  1863. if (update_state->IsReparentedNode(node_to_delete.get())) {
  1864. update_state->old_node_id_to_data.insert(
  1865. std::make_pair(id, node_to_delete->TakeData()));
  1866. }
  1867. }
  1868. }
  1869. void AXTree::DeleteOldChildren(AXNode* node,
  1870. const std::vector<AXNodeID>& new_child_ids,
  1871. AXTreeUpdateState* update_state) {
  1872. DCHECK(GetTreeUpdateInProgressState());
  1873. // Create a set of child ids in |src| for fast lookup, we know the set does
  1874. // not contain duplicate entries already, because that was handled when
  1875. // populating |update_state| with information about all of the expected
  1876. // changes to be applied.
  1877. std::set<AXNodeID> new_child_id_set(new_child_ids.begin(),
  1878. new_child_ids.end());
  1879. // Delete the old children.
  1880. for (AXNode* child : node->children()) {
  1881. if (!base::Contains(new_child_id_set, child->id()))
  1882. DestroySubtree(child, update_state);
  1883. }
  1884. }
  1885. bool AXTree::CreateNewChildVector(AXNode* node,
  1886. const std::vector<AXNodeID>& new_child_ids,
  1887. std::vector<AXNode*>* new_children,
  1888. AXTreeUpdateState* update_state) {
  1889. DCHECK(GetTreeUpdateInProgressState());
  1890. bool success = true;
  1891. for (size_t i = 0; i < new_child_ids.size(); ++i) {
  1892. AXNodeID child_id = new_child_ids[i];
  1893. AXNode* child = GetFromId(child_id);
  1894. if (child) {
  1895. if (child->parent() != node) {
  1896. // This is a serious error - nodes should never be reparented.
  1897. // If this case occurs, continue so this node isn't left in an
  1898. // inconsistent state, but return failure at the end.
  1899. if (child->parent()) {
  1900. RecordError(*update_state,
  1901. base::StringPrintf("Node %d reparented from %d to %d",
  1902. child->id(), child->parent()->id(),
  1903. node->id()));
  1904. } else {
  1905. // --- Begin temporary change ---
  1906. // TODO(crbug.com/1156601) Revert this once we have the crash data we
  1907. // need (crrev.com/c/2892259)
  1908. // Diagnose strange errors "Node 1 reparented from 0 to 2", which
  1909. // sounds like the root node is getting the <html> element as a parent
  1910. // -- in the normal case, the root is 1 and <html> is 2.
  1911. std::ostringstream error;
  1912. error << "Node did not have a previous parent, but "
  1913. "reparenting error triggered:"
  1914. << "\n* Child = " << *child << "\n* New parent = " << *node
  1915. << "\n* root_will_be_created = "
  1916. << update_state->root_will_be_created
  1917. << "\n* pending_root_id = "
  1918. << (update_state->pending_root_id
  1919. ? *update_state->pending_root_id
  1920. : kInvalidAXNodeID)
  1921. << "\nTree update: "
  1922. << update_state->pending_tree_update.ToString();
  1923. // Add a crash key so we can figure out why this is happening.
  1924. static crash_reporter::CrashKeyString<256> ax_tree_error(
  1925. "ax_reparenting_error");
  1926. ax_tree_error.Set(error.str());
  1927. LOG(ERROR) << error.str();
  1928. CHECK(false);
  1929. // --- End temporary change ---
  1930. }
  1931. success = false;
  1932. continue;
  1933. }
  1934. child->SetIndexInParent(i);
  1935. } else {
  1936. child = CreateNode(node, child_id, i, update_state);
  1937. update_state->pending_node_ids.insert(child->id());
  1938. }
  1939. new_children->push_back(child);
  1940. }
  1941. return success;
  1942. }
  1943. AXNode* AXTree::GetUnignoredAncestorFromId(AXNodeID node_id) const {
  1944. AXNode* node = GetFromId(node_id);
  1945. // We can't simply call `AXNode::GetUnignoredParent()` because the node's
  1946. // unignored cached values may be out-of-date.
  1947. while (node && node->IsIgnored())
  1948. node = node->parent();
  1949. return node;
  1950. }
  1951. AXNodeID AXTree::GetNextNegativeInternalNodeId() {
  1952. AXNodeID return_value = next_negative_internal_node_id_;
  1953. next_negative_internal_node_id_--;
  1954. if (next_negative_internal_node_id_ > 0)
  1955. next_negative_internal_node_id_ = -1;
  1956. return return_value;
  1957. }
  1958. void AXTree::PopulateOrderedSetItemsMap(
  1959. const AXNode& original_node,
  1960. const AXNode* ordered_set,
  1961. OrderedSetItemsMap* items_map_to_be_populated) const {
  1962. // Ignored nodes are not a part of ordered sets.
  1963. if (original_node.IsIgnored())
  1964. return;
  1965. // Not all ordered set containers support hierarchical level, but their set
  1966. // items may support hierarchical level. For example, container <tree> does
  1967. // not support level, but <treeitem> supports level. For ordered sets like
  1968. // this, the set container (e.g. <tree>) will take on the min of the levels
  1969. // of its direct children(e.g. <treeitem>), if the children's levels are
  1970. // defined.
  1971. absl::optional<int> ordered_set_min_level =
  1972. ordered_set->GetHierarchicalLevel();
  1973. for (AXNode::UnignoredChildIterator child =
  1974. ordered_set->UnignoredChildrenBegin();
  1975. child != ordered_set->UnignoredChildrenEnd(); ++child) {
  1976. absl::optional<int> child_level = child->GetHierarchicalLevel();
  1977. if (child_level) {
  1978. ordered_set_min_level = ordered_set_min_level
  1979. ? std::min(child_level, ordered_set_min_level)
  1980. : child_level;
  1981. }
  1982. }
  1983. RecursivelyPopulateOrderedSetItemsMap(original_node, ordered_set, ordered_set,
  1984. ordered_set_min_level, absl::nullopt,
  1985. items_map_to_be_populated);
  1986. // If after RecursivelyPopulateOrderedSetItemsMap() call, the corresponding
  1987. // level (i.e. |ordered_set_min_level|) does not exist in
  1988. // |items_map_to_be_populated|, and |original_node| equals |ordered_set|, we
  1989. // know |original_node| is an empty ordered set and contains no set items.
  1990. // However, |original_node| may still have set size attribute, so we still
  1991. // want to add this empty set (i.e. original_node/ordered_set) to
  1992. // |items_map_to_be_populated|.
  1993. if (&original_node == ordered_set &&
  1994. !items_map_to_be_populated->HierarchicalLevelExists(
  1995. ordered_set_min_level)) {
  1996. items_map_to_be_populated->Add(ordered_set_min_level,
  1997. OrderedSetContent(&original_node));
  1998. }
  1999. }
  2000. void AXTree::RecursivelyPopulateOrderedSetItemsMap(
  2001. const AXNode& original_node,
  2002. const AXNode* ordered_set,
  2003. const AXNode* local_parent,
  2004. absl::optional<int> ordered_set_min_level,
  2005. absl::optional<int> prev_level,
  2006. OrderedSetItemsMap* items_map_to_be_populated) const {
  2007. // For optimization purpose, we want to only populate set items that are
  2008. // direct descendants of |ordered_set|, since we will only be calculating
  2009. // PosInSet & SetSize of items of that level. So we skip items on deeper
  2010. // levels by stop searching recursively on node |local_parent| that turns out
  2011. // to be an ordered set whose role matches that of |ordered_set|. However,
  2012. // when we encounter a flattened structure such as the following:
  2013. // <div role="tree">
  2014. // <div role="treeitem" aria-level="1"></div>
  2015. // <div role="treeitem" aria-level="2"></div>
  2016. // <div role="treeitem" aria-level="3"></div>
  2017. // </div>
  2018. // This optimization won't apply, we will end up populating items from all
  2019. // levels.
  2020. if (ordered_set->GetRole() == local_parent->GetRole() &&
  2021. ordered_set != local_parent)
  2022. return;
  2023. for (AXNode::UnignoredChildIterator itr =
  2024. local_parent->UnignoredChildrenBegin();
  2025. itr != local_parent->UnignoredChildrenEnd(); ++itr) {
  2026. const AXNode* child = itr.get();
  2027. // Invisible children should not be counted.
  2028. // However, in the collapsed container case (e.g. a combobox), items can
  2029. // still be chosen/navigated. However, the options in these collapsed
  2030. // containers are historically marked invisible. Therefore, in that case,
  2031. // count the invisible items. Only check 2 levels up, as combobox containers
  2032. // are never higher.
  2033. if (child->data().IsInvisible() && !IsCollapsed(local_parent) &&
  2034. !IsCollapsed(local_parent->parent())) {
  2035. continue;
  2036. }
  2037. absl::optional<int> curr_level = child->GetHierarchicalLevel();
  2038. // Add child to |items_map_to_be_populated| if role matches with the role of
  2039. // |ordered_set|. If role of node is kRadioButton, don't add items of other
  2040. // roles, even if item role matches the role of |ordered_set|.
  2041. if (child->GetRole() == ax::mojom::Role::kComment ||
  2042. (original_node.GetRole() == ax::mojom::Role::kRadioButton &&
  2043. child->GetRole() == ax::mojom::Role::kRadioButton) ||
  2044. (original_node.GetRole() != ax::mojom::Role::kRadioButton &&
  2045. child->SetRoleMatchesItemRole(ordered_set))) {
  2046. // According to WAI-ARIA spec, some ordered set items do not support
  2047. // hierarchical level while its ordered set container does. For example,
  2048. // <tab> does not support level, while <tablist> supports level.
  2049. // https://www.w3.org/WAI/PF/aria/roles#tab
  2050. // https://www.w3.org/WAI/PF/aria/roles#tablist
  2051. // For this special case, when we add set items (e.g. tab) to
  2052. // |items_map_to_be_populated|, set item is placed at the same level as
  2053. // its container (e.g. tablist) in |items_map_to_be_populated|.
  2054. if (!curr_level && child->GetUnignoredParent() == ordered_set)
  2055. curr_level = ordered_set_min_level;
  2056. // We only add child to |items_map_to_be_populated| if the child set item
  2057. // is at the same hierarchical level as |ordered_set|'s level.
  2058. if (!items_map_to_be_populated->HierarchicalLevelExists(curr_level)) {
  2059. bool use_ordered_set = child->SetRoleMatchesItemRole(ordered_set) &&
  2060. ordered_set_min_level == curr_level;
  2061. const AXNode* child_ordered_set =
  2062. use_ordered_set ? ordered_set : nullptr;
  2063. items_map_to_be_populated->Add(curr_level,
  2064. OrderedSetContent(child_ordered_set));
  2065. }
  2066. items_map_to_be_populated->AddItemToBack(curr_level, child);
  2067. }
  2068. // If |child| is an ignored container for ordered set and should not be used
  2069. // to contribute to |items_map_to_be_populated|, we recurse into |child|'s
  2070. // descendants to populate |items_map_to_be_populated|.
  2071. if (child->IsIgnoredContainerForOrderedSet()) {
  2072. RecursivelyPopulateOrderedSetItemsMap(original_node, ordered_set, child,
  2073. ordered_set_min_level, curr_level,
  2074. items_map_to_be_populated);
  2075. }
  2076. // If |curr_level| goes up one level from |prev_level|, which indicates
  2077. // the ordered set of |prev_level| is closed, we add a new OrderedSetContent
  2078. // on the previous level of |items_map_to_be_populated| to signify this.
  2079. // Consider the example below:
  2080. // <div role="tree">
  2081. // <div role="treeitem" aria-level="1"></div>
  2082. // <!--- set1-level2 -->
  2083. // <div role="treeitem" aria-level="2"></div>
  2084. // <div role="treeitem" aria-level="2"></div> <--|prev_level|
  2085. // <div role="treeitem" aria-level="1" id="item2-level1"> <--|curr_level|
  2086. // </div>
  2087. // <!--- set2-level2 -->
  2088. // <div role="treeitem" aria-level="2"></div>
  2089. // <div role="treeitem" aria-level="2"></div>
  2090. // </div>
  2091. // |prev_level| is on the last item of "set1-level2" and |curr_level| is on
  2092. // "item2-level1". Since |curr_level| is up one level from |prev_level|, we
  2093. // already completed adding all items from "set1-level2" to
  2094. // |items_map_to_be_populated|. So we close up "set1-level2" by adding a new
  2095. // OrderedSetContent to level 2. When |curr_level| ends up on the items of
  2096. // "set2-level2" next, it has a fresh new set to be populated.
  2097. if (child->SetRoleMatchesItemRole(ordered_set) && curr_level < prev_level)
  2098. items_map_to_be_populated->Add(prev_level, OrderedSetContent());
  2099. prev_level = curr_level;
  2100. }
  2101. }
  2102. // Given an ordered_set, compute pos_in_set and set_size for all of its items
  2103. // and store values in cache.
  2104. // Ordered_set should never be nullptr.
  2105. void AXTree::ComputeSetSizePosInSetAndCache(const AXNode& node,
  2106. const AXNode* ordered_set) {
  2107. DCHECK(ordered_set);
  2108. // Set items role::kComment and role::kRadioButton are special cases and do
  2109. // not necessarily need to be contained in an ordered set.
  2110. if (node.GetRole() != ax::mojom::Role::kComment &&
  2111. node.GetRole() != ax::mojom::Role::kRadioButton &&
  2112. !node.SetRoleMatchesItemRole(ordered_set) && !node.IsOrderedSet())
  2113. return;
  2114. // Find all items within ordered_set and add to |items_map_to_be_populated|.
  2115. OrderedSetItemsMap items_map_to_be_populated;
  2116. PopulateOrderedSetItemsMap(node, ordered_set, &items_map_to_be_populated);
  2117. // If ordered_set role is kPopUpButton and it wraps a kMenuListPopUp, then we
  2118. // would like it to inherit the SetSize from the kMenuListPopUp it wraps. To
  2119. // do this, we treat the kMenuListPopUp as the ordered_set and eventually
  2120. // assign its SetSize value to the kPopUpButton.
  2121. if (node.GetRole() == ax::mojom::Role::kPopUpButton &&
  2122. node.GetUnignoredChildCount() > 0) {
  2123. // kPopUpButtons are only allowed to contain one kMenuListPopUp.
  2124. // The single element is guaranteed to be a kMenuListPopUp because that is
  2125. // the only item role that matches the ordered set role of kPopUpButton.
  2126. // Please see AXNode::SetRoleMatchesItemRole for more details.
  2127. OrderedSetContent* set_content =
  2128. items_map_to_be_populated.GetFirstOrderedSetContent();
  2129. if (set_content && set_content->set_items_.size() == 1) {
  2130. const AXNode* menu_list_popup = set_content->set_items_.front();
  2131. if (menu_list_popup->GetRole() == ax::mojom::Role::kMenuListPopup) {
  2132. items_map_to_be_populated.Clear();
  2133. PopulateOrderedSetItemsMap(node, menu_list_popup,
  2134. &items_map_to_be_populated);
  2135. set_content = items_map_to_be_populated.GetFirstOrderedSetContent();
  2136. // Replace |set_content|'s ordered set container with |node|
  2137. // (Role::kPopUpButton), which acts as the set container for nodes with
  2138. // Role::kMenuListOptions (children of |menu_list_popup|).
  2139. if (set_content)
  2140. set_content->ordered_set_ = &node;
  2141. }
  2142. }
  2143. }
  2144. // Iterate over all items from OrderedSetItemsMap to compute and cache each
  2145. // ordered set item's PosInSet and SetSize and corresponding ordered set
  2146. // container's SetSize.
  2147. for (auto element : items_map_to_be_populated.items_map_) {
  2148. for (const OrderedSetContent& ordered_set_content : element.second) {
  2149. ComputeSetSizePosInSetAndCacheHelper(ordered_set_content);
  2150. }
  2151. }
  2152. }
  2153. void AXTree::ComputeSetSizePosInSetAndCacheHelper(
  2154. const OrderedSetContent& ordered_set_content) {
  2155. // Keep track of number of items in the set.
  2156. int32_t num_elements = 0;
  2157. // Keep track of largest ordered set item's |aria-setsize| attribute value.
  2158. int32_t max_item_set_size_from_attribute = 0;
  2159. for (const AXNode* item : ordered_set_content.set_items_) {
  2160. // |item|'s PosInSet value is the maximum of accumulated number of
  2161. // elements count and the value from its |aria-posinset| attribute.
  2162. int32_t pos_in_set_value =
  2163. std::max(num_elements + 1,
  2164. item->GetIntAttribute(ax::mojom::IntAttribute::kPosInSet));
  2165. // For |item| that has defined hierarchical level and |aria-posinset|
  2166. // attribute, the attribute value takes precedence.
  2167. // Note: According to WAI-ARIA spec, items that support
  2168. // |aria-posinset| do not necessarily support hierarchical level.
  2169. if (item->GetHierarchicalLevel() &&
  2170. item->HasIntAttribute(ax::mojom::IntAttribute::kPosInSet))
  2171. pos_in_set_value =
  2172. item->GetIntAttribute(ax::mojom::IntAttribute::kPosInSet);
  2173. num_elements = pos_in_set_value;
  2174. // Cache computed PosInSet value for |item|.
  2175. node_set_size_pos_in_set_info_map_[item->id()] = NodeSetSizePosInSetInfo();
  2176. node_set_size_pos_in_set_info_map_[item->id()].pos_in_set =
  2177. pos_in_set_value;
  2178. // Track the largest set size for this OrderedSetContent.
  2179. max_item_set_size_from_attribute =
  2180. std::max(max_item_set_size_from_attribute,
  2181. item->GetIntAttribute(ax::mojom::IntAttribute::kSetSize));
  2182. } // End of iterating over each item in |ordered_set_content|.
  2183. // The SetSize of an ordered set (and all of its items) is the maximum of
  2184. // the following values:
  2185. // 1. The number of elements in the ordered set.
  2186. // 2. The largest item set size from |aria-setsize| attribute.
  2187. // 3. The ordered set container's |aria-setsize| attribute value.
  2188. int32_t set_size_value =
  2189. std::max(num_elements, max_item_set_size_from_attribute);
  2190. // Cache the hierarchical level and set size of |ordered_set_content|'s set
  2191. // container, if the container exists.
  2192. if (const AXNode* ordered_set = ordered_set_content.ordered_set_) {
  2193. set_size_value = std::max(
  2194. set_size_value,
  2195. ordered_set->GetIntAttribute(ax::mojom::IntAttribute::kSetSize));
  2196. // Cache |ordered_set|'s hierarchical level.
  2197. absl::optional<int> ordered_set_level = ordered_set->GetHierarchicalLevel();
  2198. if (node_set_size_pos_in_set_info_map_.find(ordered_set->id()) ==
  2199. node_set_size_pos_in_set_info_map_.end()) {
  2200. node_set_size_pos_in_set_info_map_[ordered_set->id()] =
  2201. NodeSetSizePosInSetInfo();
  2202. node_set_size_pos_in_set_info_map_[ordered_set->id()]
  2203. .lowest_hierarchical_level = ordered_set_level;
  2204. } else if (node_set_size_pos_in_set_info_map_[ordered_set->id()]
  2205. .lowest_hierarchical_level > ordered_set_level) {
  2206. node_set_size_pos_in_set_info_map_[ordered_set->id()]
  2207. .lowest_hierarchical_level = ordered_set_level;
  2208. }
  2209. // Cache |ordered_set|'s set size.
  2210. node_set_size_pos_in_set_info_map_[ordered_set->id()].set_size =
  2211. set_size_value;
  2212. }
  2213. // Cache the set size of |ordered_set_content|'s set items.
  2214. for (const AXNode* item : ordered_set_content.set_items_) {
  2215. // If item's hierarchical level and |aria-setsize| attribute are specified,
  2216. // the item's |aria-setsize| value takes precedence.
  2217. if (item->GetHierarchicalLevel() &&
  2218. item->HasIntAttribute(ax::mojom::IntAttribute::kSetSize))
  2219. node_set_size_pos_in_set_info_map_[item->id()].set_size =
  2220. item->GetIntAttribute(ax::mojom::IntAttribute::kSetSize);
  2221. else
  2222. node_set_size_pos_in_set_info_map_[item->id()].set_size = set_size_value;
  2223. } // End of iterating over each item in |ordered_set_content|.
  2224. }
  2225. absl::optional<int> AXTree::GetPosInSet(const AXNode& node) {
  2226. if (node.GetRole() == ax::mojom::Role::kPopUpButton &&
  2227. node.GetUnignoredChildCount() == 0 &&
  2228. node.HasIntAttribute(ax::mojom::IntAttribute::kPosInSet)) {
  2229. return node.GetIntAttribute(ax::mojom::IntAttribute::kPosInSet);
  2230. }
  2231. if (node_set_size_pos_in_set_info_map_.find(node.id()) !=
  2232. node_set_size_pos_in_set_info_map_.end()) {
  2233. // If item's id is in the cache, return stored PosInSet value.
  2234. return node_set_size_pos_in_set_info_map_[node.id()].pos_in_set;
  2235. }
  2236. if (GetTreeUpdateInProgressState())
  2237. return absl::nullopt;
  2238. // Only allow this to be called on nodes that can hold PosInSet values,
  2239. // which are defined in the ARIA spec.
  2240. if (!node.IsOrderedSetItem() || node.IsIgnored())
  2241. return absl::nullopt;
  2242. const AXNode* ordered_set = node.GetOrderedSet();
  2243. if (!ordered_set)
  2244. return absl::nullopt;
  2245. ComputeSetSizePosInSetAndCache(node, ordered_set);
  2246. absl::optional<int> pos_in_set =
  2247. node_set_size_pos_in_set_info_map_[node.id()].pos_in_set;
  2248. if (pos_in_set.has_value() && pos_in_set.value() < 1)
  2249. return absl::nullopt;
  2250. return pos_in_set;
  2251. }
  2252. absl::optional<int> AXTree::GetSetSize(const AXNode& node) {
  2253. if (node.GetRole() == ax::mojom::Role::kPopUpButton &&
  2254. node.GetUnignoredChildCount() == 0 &&
  2255. node.HasIntAttribute(ax::mojom::IntAttribute::kSetSize)) {
  2256. return node.GetIntAttribute(ax::mojom::IntAttribute::kSetSize);
  2257. }
  2258. if (node_set_size_pos_in_set_info_map_.find(node.id()) !=
  2259. node_set_size_pos_in_set_info_map_.end()) {
  2260. // If item's id is in the cache, return stored SetSize value.
  2261. return node_set_size_pos_in_set_info_map_[node.id()].set_size;
  2262. }
  2263. if (GetTreeUpdateInProgressState())
  2264. return absl::nullopt;
  2265. // Only allow this to be called on nodes that can hold SetSize values, which
  2266. // are defined in the ARIA spec. However, we allow set-like items to receive
  2267. // SetSize values for internal purposes.
  2268. if ((!node.IsOrderedSetItem() && !node.IsOrderedSet()) || node.IsIgnored() ||
  2269. node.IsEmbeddedGroup()) {
  2270. return absl::nullopt;
  2271. }
  2272. // If |node| is an ordered set item-like, find its outerlying ordered set.
  2273. // Otherwise, |node| is the ordered set.
  2274. const AXNode* ordered_set = &node;
  2275. if (node.IsOrderedSetItem())
  2276. ordered_set = node.GetOrderedSet();
  2277. if (!ordered_set)
  2278. return absl::nullopt;
  2279. // For popup buttons that control a single element, inherit the controlled
  2280. // item's SetSize. Skip this block if the popup button controls itself.
  2281. if (node.GetRole() == ax::mojom::Role::kPopUpButton) {
  2282. const auto& controls_ids =
  2283. node.GetIntListAttribute(ax::mojom::IntListAttribute::kControlsIds);
  2284. if (controls_ids.size() == 1 && GetFromId(controls_ids[0]) &&
  2285. controls_ids[0] != node.id()) {
  2286. const AXNode& controlled_item = *GetFromId(controls_ids[0]);
  2287. absl::optional<int> controlled_item_set_size =
  2288. GetSetSize(controlled_item);
  2289. node_set_size_pos_in_set_info_map_[node.id()].set_size =
  2290. controlled_item_set_size;
  2291. return controlled_item_set_size;
  2292. }
  2293. }
  2294. // Compute, cache, then return.
  2295. ComputeSetSizePosInSetAndCache(node, ordered_set);
  2296. absl::optional<int> set_size =
  2297. node_set_size_pos_in_set_info_map_[node.id()].set_size;
  2298. if (set_size.has_value() && set_size.value() < 0)
  2299. return absl::nullopt;
  2300. return set_size;
  2301. }
  2302. namespace {
  2303. // Helper for GetUnignoredSelection. Creates a position using |node_id|,
  2304. // |offset| and |affinity|, and if it's ignored, updates these arguments so
  2305. // that they represent a non-null non-ignored position, according to
  2306. // |adjustment_behavior|. Returns true on success, false on failure. Note that
  2307. // if the position is initially null, it's not ignored and it's a success.
  2308. bool ComputeUnignoredSelectionEndpoint(
  2309. const AXTree& tree,
  2310. AXPositionAdjustmentBehavior adjustment_behavior,
  2311. AXNodeID& node_id,
  2312. int32_t& offset,
  2313. ax::mojom::TextAffinity& affinity) {
  2314. AXNode* node = tree.GetFromId(node_id);
  2315. if (!node) {
  2316. node_id = kInvalidAXNodeID;
  2317. offset = -1;
  2318. affinity = ax::mojom::TextAffinity::kDownstream;
  2319. return false;
  2320. }
  2321. AXNodePosition::AXPositionInstance position =
  2322. AXNodePosition::CreatePosition(*node, offset, affinity);
  2323. // Null positions are never ignored, but must be considered successful, or
  2324. // these Android tests would fail:
  2325. // org.chromium.content.browser.accessibility.AssistViewStructureTest#*
  2326. // The reason is that |position| becomes null because no AXTreeManager is
  2327. // registered for that |tree|'s AXTreeID.
  2328. // TODO(accessibility): investigate and fix this if needed.
  2329. if (!position->IsIgnored())
  2330. return true; // We assume that unignored positions are already valid.
  2331. position =
  2332. position->AsValidPosition()->AsUnignoredPosition(adjustment_behavior);
  2333. // Moving to an unignored position might have placed the position on a leaf
  2334. // node. Any selection endpoint that is inside a leaf node is expressed as a
  2335. // text position in AXTreeData. (Note that in this context "leaf node" means
  2336. // a node with no children or with only ignored children. This does not
  2337. // refer to a platform leaf.)
  2338. if (position->IsLeafTreePosition())
  2339. position = position->AsTextPosition();
  2340. // We do not expect the selection to have an endpoint on an inline text
  2341. // box as this will create issues with parts of the code that don't use
  2342. // inline text boxes.
  2343. if (position->IsTextPosition() &&
  2344. position->GetRole() == ax::mojom::Role::kInlineTextBox) {
  2345. position = position->CreateParentPosition();
  2346. }
  2347. switch (position->kind()) {
  2348. case AXPositionKind::NULL_POSITION:
  2349. node_id = kInvalidAXNodeID;
  2350. offset = -1;
  2351. affinity = ax::mojom::TextAffinity::kDownstream;
  2352. return false;
  2353. case AXPositionKind::TREE_POSITION:
  2354. node_id = position->anchor_id();
  2355. offset = position->child_index();
  2356. affinity = ax::mojom::TextAffinity::kDownstream;
  2357. return true;
  2358. case AXPositionKind::TEXT_POSITION:
  2359. node_id = position->anchor_id();
  2360. offset = position->text_offset();
  2361. affinity = position->affinity();
  2362. return true;
  2363. }
  2364. }
  2365. } // namespace
  2366. AXTree::Selection AXTree::GetSelection() const {
  2367. return {data().sel_is_backward, data().sel_anchor_object_id,
  2368. data().sel_anchor_offset, data().sel_anchor_affinity,
  2369. data().sel_focus_object_id, data().sel_focus_offset,
  2370. data().sel_focus_affinity};
  2371. }
  2372. AXTree::Selection AXTree::GetUnignoredSelection() const {
  2373. Selection unignored_selection = GetSelection();
  2374. // If one of the selection endpoints is invalid, then the other endpoint
  2375. // should also be unset.
  2376. if (!ComputeUnignoredSelectionEndpoint(
  2377. *this,
  2378. unignored_selection.is_backward
  2379. ? AXPositionAdjustmentBehavior::kMoveForward
  2380. : AXPositionAdjustmentBehavior::kMoveBackward,
  2381. unignored_selection.anchor_object_id,
  2382. unignored_selection.anchor_offset,
  2383. unignored_selection.anchor_affinity)) {
  2384. unignored_selection.focus_object_id = kInvalidAXNodeID;
  2385. unignored_selection.focus_offset = -1;
  2386. unignored_selection.focus_affinity = ax::mojom::TextAffinity::kDownstream;
  2387. } else if (!ComputeUnignoredSelectionEndpoint(
  2388. *this,
  2389. unignored_selection.is_backward
  2390. ? AXPositionAdjustmentBehavior::kMoveBackward
  2391. : AXPositionAdjustmentBehavior::kMoveForward,
  2392. unignored_selection.focus_object_id,
  2393. unignored_selection.focus_offset,
  2394. unignored_selection.focus_affinity)) {
  2395. unignored_selection.anchor_object_id = kInvalidAXNodeID;
  2396. unignored_selection.anchor_offset = -1;
  2397. unignored_selection.anchor_affinity = ax::mojom::TextAffinity::kDownstream;
  2398. }
  2399. return unignored_selection;
  2400. }
  2401. bool AXTree::GetTreeUpdateInProgressState() const {
  2402. return tree_update_in_progress_;
  2403. }
  2404. void AXTree::SetTreeUpdateInProgressState(bool set_tree_update_value) {
  2405. tree_update_in_progress_ = set_tree_update_value;
  2406. }
  2407. bool AXTree::HasPaginationSupport() const {
  2408. return has_pagination_support_;
  2409. }
  2410. void AXTree::NotifyTreeManagerWillBeRemoved(AXTreeID previous_tree_id) {
  2411. if (previous_tree_id == AXTreeIDUnknown())
  2412. return;
  2413. for (AXTreeObserver& observer : observers_)
  2414. observer.OnTreeManagerWillBeRemoved(previous_tree_id);
  2415. }
  2416. void AXTree::RecordError(const AXTreeUpdateState& update_state,
  2417. std::string new_error) {
  2418. if (!error_.empty())
  2419. error_ = error_ + "\n"; // Add visual separation between errors.
  2420. error_ = error_ + new_error;
  2421. LOG(ERROR) << new_error;
  2422. static auto* const ax_tree_error_key = base::debug::AllocateCrashKeyString(
  2423. "ax_tree_error", base::debug::CrashKeySize::Size256);
  2424. static auto* const ax_tree_update_key = base::debug::AllocateCrashKeyString(
  2425. "ax_tree_update", base::debug::CrashKeySize::Size256);
  2426. static auto* const ax_tree_key = base::debug::AllocateCrashKeyString(
  2427. "ax_tree", base::debug::CrashKeySize::Size256);
  2428. static auto* const ax_tree_data_key = base::debug::AllocateCrashKeyString(
  2429. "ax_tree_data", base::debug::CrashKeySize::Size256);
  2430. // Log additional crash keys so we can debug bad tree updates.
  2431. base::debug::SetCrashKeyString(ax_tree_error_key, new_error);
  2432. base::debug::SetCrashKeyString(ax_tree_update_key,
  2433. update_state.pending_tree_update.ToString());
  2434. base::debug::SetCrashKeyString(ax_tree_key, TreeToStringHelper(root_, 1));
  2435. base::debug::SetCrashKeyString(ax_tree_data_key, data().ToString());
  2436. // In fast-failing-builds, crash immediately with a message, otherwise
  2437. // rely on AccessibilityFatalError(), which will not crash until multiple
  2438. // errors occur.
  2439. SANITIZER_NOTREACHED() << new_error << "\n"
  2440. << update_state.pending_tree_update.ToString() << "\n"
  2441. << ToString();
  2442. }
  2443. } // namespace ui