1 // Copyright 2018 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 #include "ui/accessibility/ax_table_info.h"
6
7 #include "ui/accessibility/ax_constants.mojom.h"
8 #include "ui/accessibility/ax_enums.mojom.h"
9 #include "ui/accessibility/ax_node.h"
10 #include "ui/accessibility/ax_role_properties.h"
11 #include "ui/accessibility/ax_tree.h"
12 #include "ui/accessibility/ax_tree_observer.h"
13 #include "ui/gfx/geometry/rect_f.h"
14
15 using ax::mojom::IntAttribute;
16
17 namespace ui {
18
19 namespace {
20
21 // Given a node representing a table row, search its children
22 // recursively to find any cells or table headers, and append
23 // them to |cells|.
24 //
25 // We recursively check generic containers like <div> and any
26 // nodes that are ignored, but we don't search any other roles
27 // in-between a table row and its cells.
FindCellsInRow(AXNode * node,std::vector<AXNode * > * cell_nodes)28 void FindCellsInRow(AXNode* node, std::vector<AXNode*>* cell_nodes) {
29 for (AXNode* child : node->children()) {
30 if (child->IsIgnored() ||
31 child->data().role == ax::mojom::Role::kGenericContainer)
32 FindCellsInRow(child, cell_nodes);
33 else if (IsCellOrTableHeader(child->data().role))
34 cell_nodes->push_back(child);
35 }
36 }
37
38 // Given a node representing a table/grid, search its children
39 // recursively to find any rows and append them to |row_node_list|, then
40 // for each row find its cells and add them to |cell_nodes_per_row| as a
41 // 2-dimensional array.
42 //
43 // We only recursively check for the following roles in between a table and
44 // its rows: generic containers like <div>, any nodes that are ignored, and
45 // table sections (which have Role::kRowGroup).
FindRowsAndThenCells(AXNode * node,std::vector<AXNode * > * row_node_list,std::vector<std::vector<AXNode * >> * cell_nodes_per_row,int32_t & caption_node_id)46 void FindRowsAndThenCells(AXNode* node,
47 std::vector<AXNode*>* row_node_list,
48 std::vector<std::vector<AXNode*>>* cell_nodes_per_row,
49 int32_t& caption_node_id) {
50 for (AXNode* child : node->children()) {
51 if (child->IsIgnored() ||
52 child->data().role == ax::mojom::Role::kGenericContainer ||
53 child->data().role == ax::mojom::Role::kGroup ||
54 child->data().role == ax::mojom::Role::kRowGroup) {
55 FindRowsAndThenCells(child, row_node_list, cell_nodes_per_row,
56 caption_node_id);
57 } else if (IsTableRow(child->data().role)) {
58 row_node_list->push_back(child);
59 cell_nodes_per_row->push_back(std::vector<AXNode*>());
60 FindCellsInRow(child, &cell_nodes_per_row->back());
61 } else if (child->data().role == ax::mojom::Role::kCaption)
62 caption_node_id = child->id();
63 }
64 }
65
GetSizeTAttribute(const AXNode & node,IntAttribute attribute)66 size_t GetSizeTAttribute(const AXNode& node, IntAttribute attribute) {
67 return base::saturated_cast<size_t>(node.GetIntAttribute(attribute));
68 }
69
70 } // namespace
71
72 // static
Create(AXTree * tree,AXNode * table_node)73 AXTableInfo* AXTableInfo::Create(AXTree* tree, AXNode* table_node) {
74 DCHECK(tree);
75 DCHECK(table_node);
76
77 #if DCHECK_IS_ON()
78 // Sanity check, make sure the node is in the tree.
79 AXNode* node = table_node;
80 while (node && node != tree->root())
81 node = node->parent();
82 DCHECK(node == tree->root());
83 #endif
84
85 if (!IsTableLike(table_node->data().role))
86 return nullptr;
87
88 AXTableInfo* info = new AXTableInfo(tree, table_node);
89 bool success = info->Update();
90 DCHECK(success);
91
92 return info;
93 }
94
Update()95 bool AXTableInfo::Update() {
96 if (!table_node_->IsTable())
97 return false;
98
99 ClearVectors();
100
101 std::vector<std::vector<AXNode*>> cell_nodes_per_row;
102 caption_id = 0;
103 FindRowsAndThenCells(table_node_, &row_nodes, &cell_nodes_per_row,
104 caption_id);
105 DCHECK_EQ(cell_nodes_per_row.size(), row_nodes.size());
106
107 // Get the optional row and column count from the table. If we encounter
108 // a cell with an index or span larger than this, we'll update the
109 // table row and column count to be large enough to fit all cells.
110 row_count = GetSizeTAttribute(*table_node_, IntAttribute::kTableRowCount);
111 col_count = GetSizeTAttribute(*table_node_, IntAttribute::kTableColumnCount);
112
113 int32_t aria_rows = table_node_->GetIntAttribute(IntAttribute::kAriaRowCount);
114 aria_row_count = (aria_rows != ax::mojom::kUnknownAriaColumnOrRowCount)
115 ? base::make_optional(int{aria_rows})
116 : base::nullopt;
117
118 int32_t aria_cols =
119 table_node_->GetIntAttribute(IntAttribute::kAriaColumnCount);
120 aria_col_count = (aria_cols != ax::mojom::kUnknownAriaColumnOrRowCount)
121 ? base::make_optional(int{aria_cols})
122 : base::nullopt;
123
124 // Iterate over the cells and build up an array of CellData
125 // entries, one for each cell. Compute the actual row and column
126 BuildCellDataVectorFromRowAndCellNodes(row_nodes, cell_nodes_per_row);
127
128 // At this point we have computed valid row and column indices for
129 // every cell in the table, and an accurate row and column count for the
130 // whole table that fits every cell and its spans. The final step is to
131 // fill in a 2-dimensional array that lets us look up an individual cell
132 // by its (row, column) coordinates, plus arrays to hold row and column
133 // headers.
134 BuildCellAndHeaderVectorsFromCellData();
135
136 // On Mac, we add a few extra nodes to the table - see comment
137 // at the top of UpdateExtraMacNodes for details.
138 if (tree_->enable_extra_mac_nodes())
139 UpdateExtraMacNodes();
140
141 // The table metadata is now valid, any table queries will now be
142 // fast. Any time a node in the table is updated, we'll have to
143 // recompute all of this.
144 valid_ = true;
145 return true;
146 }
147
Invalidate()148 void AXTableInfo::Invalidate() {
149 valid_ = false;
150 }
151
ClearVectors()152 void AXTableInfo::ClearVectors() {
153 col_headers.clear();
154 row_headers.clear();
155 all_headers.clear();
156 cell_ids.clear();
157 unique_cell_ids.clear();
158 cell_data_vector.clear();
159 row_nodes.clear();
160 }
161
BuildCellDataVectorFromRowAndCellNodes(const std::vector<AXNode * > & row_node_list,const std::vector<std::vector<AXNode * >> & cell_nodes_per_row)162 void AXTableInfo::BuildCellDataVectorFromRowAndCellNodes(
163 const std::vector<AXNode*>& row_node_list,
164 const std::vector<std::vector<AXNode*>>& cell_nodes_per_row) {
165 // Iterate over the cells and build up an array of CellData
166 // entries, one for each cell. Compute the actual row and column
167 // indices for each cell by taking the specified row and column
168 // index in the accessibility tree if legal, but replacing it with
169 // valid table coordinates otherwise.
170 size_t cell_index = 0;
171 size_t current_aria_row_index = 1;
172 size_t next_row_index = 0;
173 for (size_t i = 0; i < cell_nodes_per_row.size(); i++) {
174 auto& cell_nodes_in_this_row = cell_nodes_per_row[i];
175 AXNode* row_node = row_node_list[i];
176 bool is_first_cell_in_row = true;
177 size_t current_col_index = 0;
178 size_t current_aria_col_index = 1;
179
180 // Make sure the row index is always at least as high as the one reported by
181 // Blink.
182 row_id_to_index[row_node->id()] =
183 std::max(next_row_index,
184 GetSizeTAttribute(*row_node, IntAttribute::kTableRowIndex));
185 size_t* current_row_index = &row_id_to_index[row_node->id()];
186
187 for (AXNode* cell : cell_nodes_in_this_row) {
188 // Fill in basic info in CellData.
189 CellData cell_data;
190 unique_cell_ids.push_back(cell->id());
191 cell_id_to_index[cell->id()] = cell_index++;
192 cell_data.cell = cell;
193
194 // Get table cell accessibility attributes - note that these may
195 // be missing or invalid, we'll correct them next.
196 cell_data.row_index =
197 GetSizeTAttribute(*cell, IntAttribute::kTableCellRowIndex);
198 cell_data.row_span =
199 GetSizeTAttribute(*cell, IntAttribute::kTableCellRowSpan);
200 cell_data.aria_row_index =
201 GetSizeTAttribute(*cell, IntAttribute::kAriaCellRowIndex);
202 cell_data.col_index =
203 GetSizeTAttribute(*cell, IntAttribute::kTableCellColumnIndex);
204 cell_data.aria_col_index =
205 GetSizeTAttribute(*cell, IntAttribute::kAriaCellColumnIndex);
206 cell_data.col_span =
207 GetSizeTAttribute(*cell, IntAttribute::kTableCellColumnSpan);
208
209 // The col span and row span must be at least 1.
210 cell_data.row_span = std::max(size_t{1}, cell_data.row_span);
211 cell_data.col_span = std::max(size_t{1}, cell_data.col_span);
212
213 // Ensure the column index must always be incrementing.
214 cell_data.col_index = std::max(cell_data.col_index, current_col_index);
215
216 if (is_first_cell_in_row) {
217 is_first_cell_in_row = false;
218
219 // If it's the first cell in the row, ensure the row index is
220 // incrementing. The rest of the cells in this row are forced to have
221 // the same row index.
222 if (cell_data.row_index > *current_row_index) {
223 *current_row_index = cell_data.row_index;
224 } else {
225 cell_data.row_index = *current_row_index;
226 }
227
228 // The starting ARIA row and column index might be specified in
229 // the row node, we should check there.
230 if (!cell_data.aria_row_index) {
231 cell_data.aria_row_index =
232 GetSizeTAttribute(*row_node, IntAttribute::kAriaCellRowIndex);
233 }
234 if (!cell_data.aria_col_index) {
235 cell_data.aria_col_index =
236 GetSizeTAttribute(*row_node, IntAttribute::kAriaCellColumnIndex);
237 }
238 cell_data.aria_row_index =
239 std::max(cell_data.aria_row_index, current_aria_row_index);
240 current_aria_row_index = cell_data.aria_row_index;
241 } else {
242 // Don't allow the row index to change after the beginning
243 // of a row.
244 cell_data.row_index = *current_row_index;
245 cell_data.aria_row_index = current_aria_row_index;
246 }
247
248 // Ensure the ARIA col index is incrementing.
249 cell_data.aria_col_index =
250 std::max(cell_data.aria_col_index, current_aria_col_index);
251 current_aria_col_index = cell_data.aria_col_index;
252
253 // Update the row count and col count for the whole table to make
254 // sure they're large enough to fit this cell, including its spans.
255 // The -1 in the ARIA calculations is because ARIA indices are 1-based,
256 // whereas all other indices are zero-based.
257 row_count = std::max(row_count, cell_data.row_index + cell_data.row_span);
258 col_count = std::max(col_count, cell_data.col_index + cell_data.col_span);
259 if (aria_row_count) {
260 aria_row_count =
261 std::max((*aria_row_count),
262 int(current_aria_row_index + cell_data.row_span - 1));
263 }
264 if (aria_col_count) {
265 aria_col_count =
266 std::max((*aria_col_count),
267 int(current_aria_col_index + cell_data.col_span - 1));
268 }
269 // Update |current_col_index| to reflect the next available index after
270 // this cell including its colspan. The next column index in this row
271 // must be at least this large. Same for the current ARIA col index.
272 current_col_index = cell_data.col_index + cell_data.col_span;
273 current_aria_col_index = cell_data.aria_col_index + cell_data.col_span;
274
275 // Add this cell to our vector.
276 cell_data_vector.push_back(cell_data);
277 }
278
279 // At the end of each row, increment |current_aria_row_index| to reflect the
280 // next available index after this row. The next row index must be at least
281 // this large. Also update |next_row_index|.
282 current_aria_row_index++;
283 next_row_index = *current_row_index + 1;
284 }
285 }
286
BuildCellAndHeaderVectorsFromCellData()287 void AXTableInfo::BuildCellAndHeaderVectorsFromCellData() {
288 // Allocate space for the 2-D array of cell IDs and 1-D
289 // arrays of row headers and column headers.
290 row_headers.resize(row_count);
291 col_headers.resize(col_count);
292 cell_ids.resize(row_count);
293 for (auto& row : cell_ids)
294 row.resize(col_count);
295
296 // Fill in the arrays.
297 //
298 // At this point we have computed valid row and column indices for
299 // every cell in the table, and an accurate row and column count for the
300 // whole table that fits every cell and its spans. The final step is to
301 // fill in a 2-dimensional array that lets us look up an individual cell
302 // by its (row, column) coordinates, plus arrays to hold row and column
303 // headers.
304 for (auto& cell_data : cell_data_vector) {
305 for (size_t r = cell_data.row_index;
306 r < cell_data.row_index + cell_data.row_span; r++) {
307 DCHECK_LT(r, row_count);
308 for (size_t c = cell_data.col_index;
309 c < cell_data.col_index + cell_data.col_span; c++) {
310 DCHECK_LT(c, col_count);
311 AXNode* cell = cell_data.cell;
312 cell_ids[r][c] = cell->id();
313
314 if (cell->data().role == ax::mojom::Role::kColumnHeader) {
315 col_headers[c].push_back(cell->id());
316 all_headers.push_back(cell->id());
317 } else if (cell->data().role == ax::mojom::Role::kRowHeader) {
318 row_headers[r].push_back(cell->id());
319 all_headers.push_back(cell->id());
320 }
321 }
322 }
323 }
324 }
325
UpdateExtraMacNodes()326 void AXTableInfo::UpdateExtraMacNodes() {
327 // On macOS, maintain additional AXNodes: one column node for each
328 // column of the table, and one table header container.
329 //
330 // The nodes all set the table as the parent node, that way the Mac-specific
331 // platform code can treat these nodes as additional children of the table
332 // node.
333 //
334 // The columns have id -1, -2, -3, ... - this won't conflict with ids from
335 // Blink, which are all positive.
336 //
337 // Each column has the kColumnIndex attribute set, and then each of the cells
338 // in that column gets added as an indirect ID. That exposes them as children
339 // via Mac APIs but ensures we don't explore those nodes multiple times when
340 // walking the tree. The column also has the ID of the first column header
341 // set.
342 //
343 // The table header container is just a node with all of the headers in the
344 // table as indirect children.
345
346 if (!extra_mac_nodes.empty()) {
347 // Delete old extra nodes.
348 ClearExtraMacNodes();
349 }
350
351 // One node for each column, and one more for the table header container.
352 size_t extra_node_count = col_count + 1;
353 // Resize.
354 extra_mac_nodes.resize(extra_node_count);
355
356 std::vector<AXTreeObserver::Change> changes;
357 changes.reserve(extra_node_count +
358 1); // Room for extra nodes + table itself.
359
360 // Create column nodes.
361 for (size_t i = 0; i < col_count; i++) {
362 extra_mac_nodes[i] = CreateExtraMacColumnNode(i);
363 changes.push_back(AXTreeObserver::Change(
364 extra_mac_nodes[i], AXTreeObserver::ChangeType::NODE_CREATED));
365 }
366
367 // Create table header container node.
368 extra_mac_nodes[col_count] = CreateExtraMacTableHeaderNode();
369 changes.push_back(AXTreeObserver::Change(
370 extra_mac_nodes[col_count], AXTreeObserver::ChangeType::NODE_CREATED));
371
372 // Update the columns to reflect current state of the table.
373 for (size_t i = 0; i < col_count; i++)
374 UpdateExtraMacColumnNodeAttributes(i);
375
376 // Update the table header container to contain all headers.
377 ui::AXNodeData data = extra_mac_nodes[col_count]->data();
378 data.intlist_attributes.clear();
379 data.AddIntListAttribute(ax::mojom::IntListAttribute::kIndirectChildIds,
380 all_headers);
381 extra_mac_nodes[col_count]->SetData(data);
382
383 changes.push_back(AXTreeObserver::Change(
384 table_node_, AXTreeObserver::ChangeType::NODE_CHANGED));
385 for (AXTreeObserver& observer : tree_->observers()) {
386 observer.OnAtomicUpdateFinished(tree_, false, changes);
387 }
388 }
389
CreateExtraMacColumnNode(size_t col_index)390 AXNode* AXTableInfo::CreateExtraMacColumnNode(size_t col_index) {
391 int32_t id = tree_->GetNextNegativeInternalNodeId();
392 size_t index_in_parent = col_index + table_node_->children().size();
393 int32_t unignored_index_in_parent =
394 col_index + table_node_->GetUnignoredChildCount();
395 AXNode* node = new AXNode(tree_, table_node_, id, index_in_parent,
396 unignored_index_in_parent);
397 AXNodeData data;
398 data.id = id;
399 data.role = ax::mojom::Role::kColumn;
400 node->SetData(data);
401 for (AXTreeObserver& observer : tree_->observers())
402 observer.OnNodeCreated(tree_, node);
403 return node;
404 }
405
CreateExtraMacTableHeaderNode()406 AXNode* AXTableInfo::CreateExtraMacTableHeaderNode() {
407 int32_t id = tree_->GetNextNegativeInternalNodeId();
408 size_t index_in_parent = col_count + table_node_->children().size();
409 int32_t unignored_index_in_parent =
410 col_count + table_node_->GetUnignoredChildCount();
411 AXNode* node = new AXNode(tree_, table_node_, id, index_in_parent,
412 unignored_index_in_parent);
413 AXNodeData data;
414 data.id = id;
415 data.role = ax::mojom::Role::kTableHeaderContainer;
416 node->SetData(data);
417
418 for (AXTreeObserver& observer : tree_->observers())
419 observer.OnNodeCreated(tree_, node);
420
421 return node;
422 }
423
UpdateExtraMacColumnNodeAttributes(size_t col_index)424 void AXTableInfo::UpdateExtraMacColumnNodeAttributes(size_t col_index) {
425 ui::AXNodeData data = extra_mac_nodes[col_index]->data();
426 data.int_attributes.clear();
427
428 // Update the column index.
429 data.AddIntAttribute(IntAttribute::kTableColumnIndex, int32_t(col_index));
430
431 // Update the column header.
432 if (!col_headers[col_index].empty()) {
433 data.AddIntAttribute(IntAttribute::kTableColumnHeaderId,
434 col_headers[col_index][0]);
435 }
436
437 // Update the list of cells in the column.
438 data.intlist_attributes.clear();
439 std::vector<int32_t> col_nodes;
440 int32_t last = 0;
441 for (size_t row_index = 0; row_index < row_count; row_index++) {
442 int32_t cell_id = cell_ids[row_index][col_index];
443 if (cell_id != 0 && cell_id != last)
444 col_nodes.push_back(cell_id);
445 last = cell_id;
446 }
447 data.AddIntListAttribute(ax::mojom::IntListAttribute::kIndirectChildIds,
448 col_nodes);
449 extra_mac_nodes[col_index]->SetData(data);
450 }
451
ClearExtraMacNodes()452 void AXTableInfo::ClearExtraMacNodes() {
453 for (AXNode* extra_mac_node : extra_mac_nodes) {
454 for (AXTreeObserver& observer : tree_->observers())
455 observer.OnNodeWillBeDeleted(tree_, extra_mac_node);
456 AXNode::AXID deleted_id = extra_mac_node->id();
457 delete extra_mac_node;
458 for (AXTreeObserver& observer : tree_->observers())
459 observer.OnNodeDeleted(tree_, deleted_id);
460 }
461 extra_mac_nodes.clear();
462 }
463
AXTableInfo(AXTree * tree,AXNode * table_node)464 AXTableInfo::AXTableInfo(AXTree* tree, AXNode* table_node)
465 : tree_(tree), table_node_(table_node) {}
466
~AXTableInfo()467 AXTableInfo::~AXTableInfo() {
468 if (!extra_mac_nodes.empty()) {
469 ClearExtraMacNodes();
470 for (AXTreeObserver& observer : tree_->observers()) {
471 observer.OnAtomicUpdateFinished(
472 tree_, false,
473 {{table_node_, AXTreeObserver::ChangeType::NODE_CHANGED}});
474 }
475 }
476 }
477
478 } // namespace ui
479