1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef UI_ACCESSIBILITY_AX_TREE_UPDATE_H_
6 #define UI_ACCESSIBILITY_AX_TREE_UPDATE_H_
7
8 #include <stddef.h>
9 #include <stdint.h>
10
11 #include <string>
12 #include <unordered_map>
13 #include <vector>
14
15 #include "base/strings/string_number_conversions.h"
16 #include "ui/accessibility/ax_enums.mojom.h"
17 #include "ui/accessibility/ax_node_data.h"
18 #include "ui/accessibility/ax_tree_data.h"
19
20 namespace ui {
21
22 // An AXTreeUpdate is a serialized representation of an atomic change
23 // to an AXTree. The sender and receiver must be in sync; the update
24 // is only meant to bring the tree from a specific previous state into
25 // its next state. Trying to apply it to the wrong tree should immediately
26 // die with a fatal assertion.
27 //
28 // An AXTreeUpdate consists of an optional node id to clear (meaning
29 // that all of that node's children and their descendants are deleted),
30 // followed by an ordered vector of zero or more AXNodeData structures to
31 // be applied to the tree in order. An update may also include an optional
32 // update to the AXTreeData structure that applies to the tree as a whole.
33 //
34 // Suppose that the next AXNodeData to be applied is |node|. The following
35 // invariants must hold:
36 // 1. Either
37 // a) |node.id| is already in the tree, or
38 // b) the tree is empty, and
39 // |node| is the new root of the tree, and
40 // |node.role| == WebAXRoleRootWebArea.
41 // 2. Every child id in |node.child_ids| must either be already a child
42 // of this node, or a new id not previously in the tree. It is not
43 // allowed to "reparent" a child to this node without first removing
44 // that child from its previous parent.
45 // 3. When a new id appears in |node.child_ids|, the tree should create a
46 // new uninitialized placeholder node for it immediately. That
47 // placeholder must be updated within the same AXTreeUpdate, otherwise
48 // it's a fatal error. This guarantees the tree is always complete
49 // before or after an AXTreeUpdate.
50 template<typename AXNodeData, typename AXTreeData> struct AXTreeUpdateBase {
51 AXTreeUpdateBase() = default;
52 ~AXTreeUpdateBase() = default;
53
54 // If |has_tree_data| is true, the value of |tree_data| should be used
55 // to update the tree data, otherwise it should be ignored.
56 bool has_tree_data = false;
57 AXTreeData tree_data;
58
59 // The id of a node to clear, before applying any updates,
60 // or 0 if no nodes should be cleared. Clearing a node means deleting
61 // all of its children and their descendants, but leaving that node in
62 // the tree. It's an error to clear a node but not subsequently update it
63 // as part of the tree update.
64 int node_id_to_clear = 0;
65
66 // The id of the root of the tree, if the root is changing. This is
67 // required to be set if the root of the tree is changing or Unserialize
68 // will fail. If the root of the tree is not changing this is optional
69 // and it is allowed to pass 0.
70 int root_id = 0;
71
72 // A vector of nodes to update, according to the rules above.
73 std::vector<AXNodeData> nodes;
74
75 // The source of the event.
76 ax::mojom::EventFrom event_from = ax::mojom::EventFrom::kNone;
77
78 // Return a multi-line indented string representation, for logging.
79 std::string ToString() const;
80
81 // TODO(dmazzoni): location changes
82 };
83
84 using AXTreeUpdate = AXTreeUpdateBase<AXNodeData, AXTreeData>;
85
86 template<typename AXNodeData, typename AXTreeData>
ToString()87 std::string AXTreeUpdateBase<AXNodeData, AXTreeData>::ToString() const {
88 std::string result;
89
90 if (has_tree_data) {
91 result += "AXTreeUpdate tree data:" + tree_data.ToString() + "\n";
92 }
93
94 if (node_id_to_clear != 0) {
95 result += "AXTreeUpdate: clear node " +
96 base::NumberToString(node_id_to_clear) + "\n";
97 }
98
99 if (root_id != 0) {
100 result += "AXTreeUpdate: root id " + base::NumberToString(root_id) + "\n";
101 }
102
103 // The challenge here is that we want to indent the nodes being updated
104 // so that parent/child relationships are clear, but we don't have access
105 // to the rest of the tree for context, so we have to try to show the
106 // relative indentation of child nodes in this update relative to their
107 // parents.
108 std::unordered_map<int32_t, int> id_to_indentation;
109 for (size_t i = 0; i < nodes.size(); ++i) {
110 int indent = id_to_indentation[nodes[i].id];
111 result += std::string(2 * indent, ' ');
112 result += nodes[i].ToString() + "\n";
113 for (size_t j = 0; j < nodes[i].child_ids.size(); ++j)
114 id_to_indentation[nodes[i].child_ids[j]] = indent + 1;
115 }
116
117 return result;
118 }
119
120 // Two tree updates can be merged into one if the second one
121 // doesn't clear a subtree, doesn't have new tree data, and
122 // doesn't have a new root id - in other words the second tree
123 // update consists of only changes to nodes.
124 template <typename AXNodeData, typename AXTreeData>
TreeUpdatesCanBeMerged(const AXTreeUpdateBase<AXNodeData,AXTreeData> & u1,const AXTreeUpdateBase<AXNodeData,AXTreeData> & u2)125 bool TreeUpdatesCanBeMerged(
126 const AXTreeUpdateBase<AXNodeData, AXTreeData>& u1,
127 const AXTreeUpdateBase<AXNodeData, AXTreeData>& u2) {
128 if (u2.node_id_to_clear)
129 return false;
130
131 if (u2.has_tree_data && u2.tree_data != u1.tree_data)
132 return false;
133
134 if (u2.root_id != u1.root_id)
135 return false;
136
137 return true;
138 }
139
140 } // namespace ui
141
142 #endif // UI_ACCESSIBILITY_AX_TREE_UPDATE_H_
143