ui/accessibility/ax_table_info.cc - chromium/src - Git at Google

 // Copyright 2018 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "ui/accessibility/ax_table_info.h"

 #include "base/strings/string_util.h"
 #include "ui/accessibility/ax_constants.mojom.h"
 #include "ui/accessibility/ax_enums.mojom.h"
 #include "ui/accessibility/ax_node.h"
 #include "ui/accessibility/ax_role_properties.h"
 #include "ui/accessibility/ax_tree.h"
 #include "ui/accessibility/ax_tree_observer.h"
 #include "ui/gfx/geometry/rect_f.h"

 using ax::mojom::IntAttribute;

 namespace ui {

 namespace {

 // Given a node representing a table row, search its children
 // recursively to find any cells or table headers, and append
 // them to |cells|.
 //
 // We recursively check generic containers like <div> and any
 // nodes that are ignored, but we don't search any other roles
 // in-between a table row and its cells.
 void FindCellsInRow(AXNode* node, std::vector<AXNode*>* cell_nodes) {
   for (AXNode* child : node->children()) {
     if (child->IsIgnored() ||
         child->data().role == ax::mojom::Role::kGenericContainer)
       FindCellsInRow(child, cell_nodes);
     else if (IsCellOrTableHeader(child->data().role))
       cell_nodes->push_back(child);
   }
 }

 // Given a node representing a table/grid, search its children
 // recursively to find any rows and append them to |row_node_list|, then
 // for each row find its cells and add them to |cell_nodes_per_row| as a
 // 2-dimensional array.
 //
 // We only recursively check for the following roles in between a table and
 // its rows: generic containers like <div>, any nodes that are ignored, and
 // table sections (which have Role::kRowGroup).
 void FindRowsAndThenCells(AXNode* node,
                           std::vector<AXNode*>* row_node_list,
                           std::vector<std::vector<AXNode*>>* cell_nodes_per_row,
                           int32_t& caption_node_id) {
   for (AXNode* child : node->children()) {
     if (child->IsIgnored() ||
         child->data().role == ax::mojom::Role::kGenericContainer ||
         child->data().role == ax::mojom::Role::kGroup ||
         child->data().role == ax::mojom::Role::kRowGroup) {
       FindRowsAndThenCells(child, row_node_list, cell_nodes_per_row,
                            caption_node_id);
     } else if (IsTableRow(child->data().role)) {
       row_node_list->push_back(child);
       cell_nodes_per_row->push_back(std::vector<AXNode*>());
       FindCellsInRow(child, &cell_nodes_per_row->back());
     } else if (child->data().role == ax::mojom::Role::kCaption)
       caption_node_id = child->id();
   }
 }

 size_t GetSizeTAttribute(const AXNode& node, IntAttribute attribute) {
   return base::saturated_cast<size_t>(node.GetIntAttribute(attribute));
 }

 }  // namespace

 // static
 AXTableInfo* AXTableInfo::Create(AXTree* tree, AXNode* table_node) {
   DCHECK(tree);
   DCHECK(table_node);

 #if DCHECK_IS_ON()
   // Sanity check, make sure the node is in the tree.
   AXNode* node = table_node;
   while (node && node != tree->root())
     node = node->parent();
   DCHECK(node == tree->root());
 #endif

   if (!IsTableLike(table_node->data().role))
     return nullptr;

   AXTableInfo* info = new AXTableInfo(tree, table_node);
   bool success = info->Update();
   DCHECK(success);

   return info;
 }

 bool AXTableInfo::Update() {
   if (!table_node_->IsTable())
     return false;

   ClearVectors();

   std::vector<std::vector<AXNode*>> cell_nodes_per_row;
   caption_id = 0;
   FindRowsAndThenCells(table_node_, &row_nodes, &cell_nodes_per_row,
                        caption_id);
   DCHECK_EQ(cell_nodes_per_row.size(), row_nodes.size());

   // Get the optional row and column count from the table. If we encounter
   // a cell with an index or span larger than this, we'll update the
   // table row and column count to be large enough to fit all cells.
   row_count = GetSizeTAttribute(*table_node_, IntAttribute::kTableRowCount);
   col_count = GetSizeTAttribute(*table_node_, IntAttribute::kTableColumnCount);

   // Note - GetIntAttribute returns 0 if no value has been specified for the
   // attribute.
   aria_row_count =
       int{table_node_->GetIntAttribute(IntAttribute::kAriaRowCount)};
   aria_col_count =
       int{table_node_->GetIntAttribute(IntAttribute::kAriaColumnCount)};

   // Iterate over the cells and build up an array of CellData
   // entries, one for each cell. Compute the actual row and column
   BuildCellDataVectorFromRowAndCellNodes(row_nodes, cell_nodes_per_row);

   // At this point we have computed valid row and column indices for
   // every cell in the table, and an accurate row and column count for the
   // whole table that fits every cell and its spans. The final step is to
   // fill in a 2-dimensional array that lets us look up an individual cell
   // by its (row, column) coordinates, plus arrays to hold row and column
   // headers.
   BuildCellAndHeaderVectorsFromCellData();

   // On Mac, we add a few extra nodes to the table - see comment
   // at the top of UpdateExtraMacNodes for details.
   if (tree_->enable_extra_mac_nodes())
     UpdateExtraMacNodes();

   // The table metadata is now valid, any table queries will now be
   // fast. Any time a node in the table is updated, we'll have to
   // recompute all of this.
   valid_ = true;
   return true;
 }

 void AXTableInfo::Invalidate() {
   valid_ = false;
 }

 void AXTableInfo::ClearVectors() {
   col_headers.clear();
   row_headers.clear();
   all_headers.clear();
   cell_ids.clear();
   unique_cell_ids.clear();
   cell_data_vector.clear();
   row_nodes.clear();
   cell_id_to_index.clear();
   row_id_to_index.clear();
   incremental_row_col_map_.clear();
 }

 void AXTableInfo::BuildCellDataVectorFromRowAndCellNodes(
     const std::vector<AXNode*>& row_node_list,
     const std::vector<std::vector<AXNode*>>& cell_nodes_per_row) {
   // Iterate over the cells and build up an array of CellData
   // entries, one for each cell. Compute the actual row and column
   // indices for each cell by taking the specified row and column
   // index in the accessibility tree if legal, but replacing it with
   // valid table coordinates otherwise.
   size_t cell_index = 0;
   size_t current_aria_row_index = 1;
   size_t next_row_index = 0;
   for (size_t i = 0; i < cell_nodes_per_row.size(); i++) {
     auto& cell_nodes_in_this_row = cell_nodes_per_row[i];
     AXNode* row_node = row_node_list[i];
     bool is_first_cell_in_row = true;
     size_t current_col_index = 0;
     size_t current_aria_col_index = 1;

     // Make sure the row index is always at least as high as the one reported by
     // the source tree.
     row_id_to_index[row_node->id()] =
         std::max(next_row_index,
                  GetSizeTAttribute(*row_node, IntAttribute::kTableRowIndex));
     size_t* current_row_index = &row_id_to_index[row_node->id()];
     size_t spanned_col_index = 0;
     for (AXNode* cell : cell_nodes_in_this_row) {
       // Fill in basic info in CellData.
       CellData cell_data;
       unique_cell_ids.push_back(cell->id());
       cell_id_to_index[cell->id()] = cell_index++;
       cell_data.cell = cell;

       // Get table cell accessibility attributes - note that these may
       // be missing or invalid, we'll correct them next.
       cell_data.row_index =
           GetSizeTAttribute(*cell, IntAttribute::kTableCellRowIndex);
       cell_data.row_span =
           GetSizeTAttribute(*cell, IntAttribute::kTableCellRowSpan);
       cell_data.aria_row_index =
           GetSizeTAttribute(*cell, IntAttribute::kAriaCellRowIndex);
       cell_data.col_index =
           GetSizeTAttribute(*cell, IntAttribute::kTableCellColumnIndex);
       cell_data.aria_col_index =
           GetSizeTAttribute(*cell, IntAttribute::kAriaCellColumnIndex);
       cell_data.col_span =
           GetSizeTAttribute(*cell, IntAttribute::kTableCellColumnSpan);

       // The col span and row span must be at least 1.
       cell_data.row_span = std::max(size_t{1}, cell_data.row_span);
       cell_data.col_span = std::max(size_t{1}, cell_data.col_span);

       // Ensure the column index must always be incrementing.
       cell_data.col_index = std::max(cell_data.col_index, current_col_index);

       // And update the spanned column index.
       spanned_col_index = std::max(spanned_col_index, cell_data.col_index);

       if (is_first_cell_in_row) {
         is_first_cell_in_row = false;

         // If it's the first cell in the row, ensure the row index is
         // incrementing. The rest of the cells in this row are forced to have
         // the same row index.
         if (cell_data.row_index > *current_row_index) {
           *current_row_index = cell_data.row_index;
         } else {
           cell_data.row_index = *current_row_index;
         }

         // The starting ARIA row and column index might be specified in
         // the row node, we should check there.
         if (!cell_data.aria_row_index) {
           cell_data.aria_row_index =
               GetSizeTAttribute(*row_node, IntAttribute::kAriaCellRowIndex);
         }
         if (!cell_data.aria_col_index) {
           cell_data.aria_col_index =
               GetSizeTAttribute(*row_node, IntAttribute::kAriaCellColumnIndex);
         }
         cell_data.aria_row_index =
             std::max(cell_data.aria_row_index, current_aria_row_index);
         current_aria_row_index = cell_data.aria_row_index;
       } else {
         // Don't allow the row index to change after the beginning
         // of a row.
         cell_data.row_index = *current_row_index;
         cell_data.aria_row_index = current_aria_row_index;
       }

       // Adjust the spanned col index by looking at the incremental row col map.
       // This map contains already filled in values, accounting for spans, of
       // all row, col indices. The map should have filled in all values we need
       // (upper left triangle of cells of the table).
       while (true) {
         const auto& row_it = incremental_row_col_map_.find(*current_row_index);
         if (row_it == incremental_row_col_map_.end()) {
           break;
         } else {
           const auto& col_it = row_it->second.find(spanned_col_index);
           if (col_it == row_it->second.end()) {
             break;
           } else {
             // A pre-existing cell resides in our desired position. Make a
             // best-fit to the right of the existing span.
             const CellData& spanned_cell_data = col_it->second;
             spanned_col_index =
                 spanned_cell_data.col_index + spanned_cell_data.col_span;

             // Adjust the actual col index to be the best fit with the existing
             // spanned cell data.
             cell_data.col_index = spanned_col_index;
           }
         }
       }

       // Memoize the cell data using our incremental row col map.
       for (size_t r = cell_data.row_index;
            r < (cell_data.row_index + cell_data.row_span); r++) {
         for (size_t c = cell_data.col_index;
              c < (cell_data.col_index + cell_data.col_span); c++) {
           incremental_row_col_map_[r][c] = cell_data;
         }
       }

       // Ensure the ARIA col index is incrementing.
       cell_data.aria_col_index =
           std::max(cell_data.aria_col_index, current_aria_col_index);
       current_aria_col_index = cell_data.aria_col_index;

       // Update the row count and col count for the whole table to make
       // sure they're large enough to fit this cell, including its spans.
       // The -1 in the ARIA calculations is because ARIA indices are 1-based,
       // whereas all other indices are zero-based.
       row_count = std::max(row_count, cell_data.row_index + cell_data.row_span);
       col_count = std::max(col_count, cell_data.col_index + cell_data.col_span);
       if (aria_row_count != ax::mojom::kUnknownAriaColumnOrRowCount) {
         aria_row_count =
             std::max((aria_row_count),
                      int{current_aria_row_index + cell_data.row_span - 1});
       }
       if (aria_col_count != ax::mojom::kUnknownAriaColumnOrRowCount) {
         aria_col_count =
             std::max((aria_col_count),
                      int{current_aria_col_index + cell_data.col_span - 1});
       }
       // Update |current_col_index| to reflect the next available index after
       // this cell including its colspan. The next column index in this row
       // must be at least this large. Same for the current ARIA col index.
       current_col_index = cell_data.col_index + cell_data.col_span;
       current_aria_col_index = cell_data.aria_col_index + cell_data.col_span;
       spanned_col_index = current_col_index;

       // Add this cell to our vector.
       cell_data_vector.push_back(cell_data);
     }

     // At the end of each row, increment |current_aria_row_index| to reflect the
     // next available index after this row. The next row index must be at least
     // this large. Also update |next_row_index|.
     current_aria_row_index++;
     next_row_index = *current_row_index + 1;
   }
 }

 void AXTableInfo::BuildCellAndHeaderVectorsFromCellData() {
   // Allocate space for the 2-D array of cell IDs and 1-D
   // arrays of row headers and column headers.
   row_headers.resize(row_count);
   col_headers.resize(col_count);
   // Fill in the arrays.
   //
   // At this point we have computed valid row and column indices for
   // every cell in the table, and an accurate row and column count for the
   // whole table that fits every cell and its spans. The final step is to
   // fill in a 2-dimensional array that lets us look up an individual cell
   // by its (row, column) coordinates, plus arrays to hold row and column
   // headers.

   // For cells.
   cell_ids.resize(row_count);
   for (size_t r = 0; r < row_count; r++) {
     cell_ids[r].resize(col_count);
     for (size_t c = 0; c < col_count; c++) {
       const auto& row_it = incremental_row_col_map_.find(r);
       if (row_it != incremental_row_col_map_.end()) {
         const auto& col_it = row_it->second.find(c);
         if (col_it != row_it->second.end())
           cell_ids[r][c] = col_it->second.cell->id();
       }
     }
   }

   // No longer need this.
   incremental_row_col_map_.clear();

   // For relations.
   for (auto& cell_data : cell_data_vector) {
     for (size_t r = cell_data.row_index;
          r < cell_data.row_index + cell_data.row_span; r++) {
       DCHECK_LT(r, row_count);
       for (size_t c = cell_data.col_index;
            c < cell_data.col_index + cell_data.col_span; c++) {
         DCHECK_LT(c, col_count);
         AXNode* cell = cell_data.cell;
         if (cell->data().role == ax::mojom::Role::kColumnHeader) {
           col_headers[c].push_back(cell->id());
           all_headers.push_back(cell->id());
         } else if (cell->data().role == ax::mojom::Role::kRowHeader) {
           row_headers[r].push_back(cell->id());
           all_headers.push_back(cell->id());
         }
       }
     }
   }
 }

 void AXTableInfo::UpdateExtraMacNodes() {
   // On macOS, maintain additional AXNodes: one column node for each
   // column of the table, and one table header container.
   //
   // The nodes all set the table as the parent node, that way the Mac-specific
   // platform code can treat these nodes as additional children of the table
   // node.
   //
   // The columns have id -1, -2, -3, ... - this won't conflict with ids from
   // the source tree, which are all positive.
   //
   // Each column has the kColumnIndex attribute set, and then each of the cells
   // in that column gets added as an indirect ID. That exposes them as children
   // via Mac APIs but ensures we don't explore those nodes multiple times when
   // walking the tree. The column also has the ID of the first column header
   // set.
   //
   // The table header container is just a node with all of the headers in the
   // table as indirect children.

   if (!extra_mac_nodes.empty()) {
     // Delete old extra nodes.
     ClearExtraMacNodes();
   }

   // One node for each column, and one more for the table header container.
   size_t extra_node_count = col_count + 1;
   // Resize.
   extra_mac_nodes.resize(extra_node_count);

   std::vector<AXTreeObserver::Change> changes;
   changes.reserve(extra_node_count +
                   1);  // Room for extra nodes + table itself.

   // Create column nodes.
   for (size_t i = 0; i < col_count; i++) {
     extra_mac_nodes[i] = CreateExtraMacColumnNode(i);
     changes.push_back(AXTreeObserver::Change(
         extra_mac_nodes[i], AXTreeObserver::ChangeType::NODE_CREATED));
   }

   // Create table header container node.
   extra_mac_nodes[col_count] = CreateExtraMacTableHeaderNode();
   changes.push_back(AXTreeObserver::Change(
       extra_mac_nodes[col_count], AXTreeObserver::ChangeType::NODE_CREATED));

   // Update the columns to reflect current state of the table.
   for (size_t i = 0; i < col_count; i++)
     UpdateExtraMacColumnNodeAttributes(i);

   // Update the table header container to contain all headers.
   ui::AXNodeData data = extra_mac_nodes[col_count]->data();
   data.intlist_attributes.clear();
   data.AddIntListAttribute(ax::mojom::IntListAttribute::kIndirectChildIds,
                            all_headers);
   extra_mac_nodes[col_count]->SetData(data);

   changes.push_back(AXTreeObserver::Change(
       table_node_, AXTreeObserver::ChangeType::NODE_CHANGED));
   for (AXTreeObserver& observer : tree_->observers()) {
     observer.OnAtomicUpdateFinished(tree_, false, changes);
   }
 }

 AXNode* AXTableInfo::CreateExtraMacColumnNode(size_t col_index) {
   int32_t id = tree_->GetNextNegativeInternalNodeId();
   size_t index_in_parent = col_index + table_node_->children().size();
   int32_t unignored_index_in_parent =
       col_index + table_node_->GetUnignoredChildCount();
   AXNode* node = new AXNode(tree_, table_node_, id, index_in_parent,
                             unignored_index_in_parent);
   AXNodeData data;
   data.id = id;
   data.role = ax::mojom::Role::kColumn;
   node->SetData(data);
   for (AXTreeObserver& observer : tree_->observers())
     observer.OnNodeCreated(tree_, node);
   return node;
 }

 AXNode* AXTableInfo::CreateExtraMacTableHeaderNode() {
   int32_t id = tree_->GetNextNegativeInternalNodeId();
   size_t index_in_parent = col_count + table_node_->children().size();
   int32_t unignored_index_in_parent =
       col_count + table_node_->GetUnignoredChildCount();
   AXNode* node = new AXNode(tree_, table_node_, id, index_in_parent,
                             unignored_index_in_parent);
   AXNodeData data;
   data.id = id;
   data.role = ax::mojom::Role::kTableHeaderContainer;
   node->SetData(data);

   for (AXTreeObserver& observer : tree_->observers())
     observer.OnNodeCreated(tree_, node);

   return node;
 }

 void AXTableInfo::UpdateExtraMacColumnNodeAttributes(size_t col_index) {
   ui::AXNodeData data = extra_mac_nodes[col_index]->data();
   data.int_attributes.clear();

   // Update the column index.
   data.AddIntAttribute(IntAttribute::kTableColumnIndex, int32_t{col_index});

   // Update the column header.
   if (!col_headers[col_index].empty()) {
     data.AddIntAttribute(IntAttribute::kTableColumnHeaderId,
                          col_headers[col_index][0]);
   }

   // Update the list of cells in the column.
   data.intlist_attributes.clear();
   std::vector<int32_t> col_nodes;
   int32_t last = 0;
   for (size_t row_index = 0; row_index < row_count; row_index++) {
     int32_t cell_id = cell_ids[row_index][col_index];
     if (cell_id != 0 && cell_id != last)
       col_nodes.push_back(cell_id);
     last = cell_id;
   }
   data.AddIntListAttribute(ax::mojom::IntListAttribute::kIndirectChildIds,
                            col_nodes);
   extra_mac_nodes[col_index]->SetData(data);
 }

 void AXTableInfo::ClearExtraMacNodes() {
   for (AXNode* extra_mac_node : extra_mac_nodes) {
     for (AXTreeObserver& observer : tree_->observers())
       observer.OnNodeWillBeDeleted(tree_, extra_mac_node);
     AXNode::AXID deleted_id = extra_mac_node->id();
     delete extra_mac_node;
     for (AXTreeObserver& observer : tree_->observers())
       observer.OnNodeDeleted(tree_, deleted_id);
   }
   extra_mac_nodes.clear();
 }

 std::string AXTableInfo::ToString() const {
   // First, scan through to get the length of the largest id.
   int padding = 0;
   for (size_t r = 0; r < row_count; r++) {
     for (size_t c = 0; c < col_count; c++) {
       // Extract the length of the id for padding purposes.
       padding = std::max(padding, static_cast<int>(log10(cell_ids[r][c])));
     }
   }

   std::string result;
   for (size_t r = 0; r < row_count; r++) {
     result += "|";
     for (size_t c = 0; c < col_count; c++) {
       int cell_id = cell_ids[r][c];
       result += base::NumberToString(cell_id);
       int cell_padding = padding;
       if (cell_id != 0)
         cell_padding = padding - static_cast<int>(log10(cell_id));
       result += std::string(cell_padding, ' ') + '|';
     }
     result += "\n";
   }
   return result;
 }

 AXTableInfo::AXTableInfo(AXTree* tree, AXNode* table_node)
     : tree_(tree), table_node_(table_node) {}

 AXTableInfo::~AXTableInfo() {
   if (!extra_mac_nodes.empty()) {
     ClearExtraMacNodes();
     for (AXTreeObserver& observer : tree_->observers()) {
       observer.OnAtomicUpdateFinished(
           tree_, false,
           {{table_node_, AXTreeObserver::ChangeType::NODE_CHANGED}});
     }
   }
 }

 }  // namespace ui
	// Copyright 2018 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "ui/accessibility/ax_table_info.h"

	#include "base/strings/string_util.h"
	#include "ui/accessibility/ax_constants.mojom.h"
	#include "ui/accessibility/ax_enums.mojom.h"
	#include "ui/accessibility/ax_node.h"
	#include "ui/accessibility/ax_role_properties.h"
	#include "ui/accessibility/ax_tree.h"
	#include "ui/accessibility/ax_tree_observer.h"
	#include "ui/gfx/geometry/rect_f.h"

	using ax::mojom::IntAttribute;

	namespace ui {

	namespace {

	// Given a node representing a table row, search its children
	// recursively to find any cells or table headers, and append
	// them to \|cells\|.
	//
	// We recursively check generic containers like <div> and any
	// nodes that are ignored, but we don't search any other roles
	// in-between a table row and its cells.
	void FindCellsInRow(AXNode* node, std::vector<AXNode> cell_nodes) {
	for (AXNode* child : node->children()) {
	if (child->IsIgnored() \|\|
	child->data().role == ax::mojom::Role::kGenericContainer)
	FindCellsInRow(child, cell_nodes);
	else if (IsCellOrTableHeader(child->data().role))
	cell_nodes->push_back(child);
	}
	}

	// Given a node representing a table/grid, search its children
	// recursively to find any rows and append them to \|row_node_list\|, then
	// for each row find its cells and add them to \|cell_nodes_per_row\| as a
	// 2-dimensional array.
	//
	// We only recursively check for the following roles in between a table and
	// its rows: generic containers like <div>, any nodes that are ignored, and
	// table sections (which have Role::kRowGroup).
	void FindRowsAndThenCells(AXNode* node,
	std::vector<AXNode> row_node_list,
	std::vector<std::vector<AXNode>> cell_nodes_per_row,
	int32_t& caption_node_id) {
	for (AXNode* child : node->children()) {
	if (child->IsIgnored() \|\|
	child->data().role == ax::mojom::Role::kGenericContainer \|\|
	child->data().role == ax::mojom::Role::kGroup \|\|
	child->data().role == ax::mojom::Role::kRowGroup) {
	FindRowsAndThenCells(child, row_node_list, cell_nodes_per_row,
	caption_node_id);
	} else if (IsTableRow(child->data().role)) {
	row_node_list->push_back(child);
	cell_nodes_per_row->push_back(std::vector<AXNode*>());
	FindCellsInRow(child, &cell_nodes_per_row->back());
	} else if (child->data().role == ax::mojom::Role::kCaption)
	caption_node_id = child->id();
	}
	}

	size_t GetSizeTAttribute(const AXNode& node, IntAttribute attribute) {
	return base::saturated_cast<size_t>(node.GetIntAttribute(attribute));
	}

	} // namespace

	// static
	AXTableInfo* AXTableInfo::Create(AXTree* tree, AXNode* table_node) {
	DCHECK(tree);
	DCHECK(table_node);

	#if DCHECK_IS_ON()
	// Sanity check, make sure the node is in the tree.
	AXNode* node = table_node;
	while (node && node != tree->root())
	node = node->parent();
	DCHECK(node == tree->root());
	#endif

	if (!IsTableLike(table_node->data().role))
	return nullptr;

	AXTableInfo* info = new AXTableInfo(tree, table_node);
	bool success = info->Update();
	DCHECK(success);

	return info;
	}

	bool AXTableInfo::Update() {
	if (!table_node_->IsTable())
	return false;

	ClearVectors();

	std::vector<std::vector<AXNode*>> cell_nodes_per_row;
	caption_id = 0;
	FindRowsAndThenCells(table_node_, &row_nodes, &cell_nodes_per_row,
	caption_id);
	DCHECK_EQ(cell_nodes_per_row.size(), row_nodes.size());

	// Get the optional row and column count from the table. If we encounter
	// a cell with an index or span larger than this, we'll update the
	// table row and column count to be large enough to fit all cells.
	row_count = GetSizeTAttribute(*table_node_, IntAttribute::kTableRowCount);
	col_count = GetSizeTAttribute(*table_node_, IntAttribute::kTableColumnCount);

	// Note - GetIntAttribute returns 0 if no value has been specified for the
	// attribute.
	aria_row_count =
	int{table_node_->GetIntAttribute(IntAttribute::kAriaRowCount)};
	aria_col_count =
	int{table_node_->GetIntAttribute(IntAttribute::kAriaColumnCount)};

	// Iterate over the cells and build up an array of CellData
	// entries, one for each cell. Compute the actual row and column
	BuildCellDataVectorFromRowAndCellNodes(row_nodes, cell_nodes_per_row);

	// At this point we have computed valid row and column indices for
	// every cell in the table, and an accurate row and column count for the
	// whole table that fits every cell and its spans. The final step is to
	// fill in a 2-dimensional array that lets us look up an individual cell
	// by its (row, column) coordinates, plus arrays to hold row and column
	// headers.
	BuildCellAndHeaderVectorsFromCellData();

	// On Mac, we add a few extra nodes to the table - see comment
	// at the top of UpdateExtraMacNodes for details.
	if (tree_->enable_extra_mac_nodes())
	UpdateExtraMacNodes();

	// The table metadata is now valid, any table queries will now be
	// fast. Any time a node in the table is updated, we'll have to
	// recompute all of this.
	valid_ = true;
	return true;
	}

	void AXTableInfo::Invalidate() {
	valid_ = false;
	}

	void AXTableInfo::ClearVectors() {
	col_headers.clear();
	row_headers.clear();
	all_headers.clear();
	cell_ids.clear();
	unique_cell_ids.clear();
	cell_data_vector.clear();
	row_nodes.clear();
	cell_id_to_index.clear();
	row_id_to_index.clear();
	incremental_row_col_map_.clear();
	}

	void AXTableInfo::BuildCellDataVectorFromRowAndCellNodes(
	const std::vector<AXNode*>& row_node_list,
	const std::vector<std::vector<AXNode*>>& cell_nodes_per_row) {
	// Iterate over the cells and build up an array of CellData
	// entries, one for each cell. Compute the actual row and column
	// indices for each cell by taking the specified row and column
	// index in the accessibility tree if legal, but replacing it with
	// valid table coordinates otherwise.
	size_t cell_index = 0;
	size_t current_aria_row_index = 1;
	size_t next_row_index = 0;
	for (size_t i = 0; i < cell_nodes_per_row.size(); i++) {
	auto& cell_nodes_in_this_row = cell_nodes_per_row[i];
	AXNode* row_node = row_node_list[i];
	bool is_first_cell_in_row = true;
	size_t current_col_index = 0;
	size_t current_aria_col_index = 1;

	// Make sure the row index is always at least as high as the one reported by
	// the source tree.
	row_id_to_index[row_node->id()] =
	std::max(next_row_index,
	GetSizeTAttribute(*row_node, IntAttribute::kTableRowIndex));
	size_t* current_row_index = &row_id_to_index[row_node->id()];
	size_t spanned_col_index = 0;
	for (AXNode* cell : cell_nodes_in_this_row) {
	// Fill in basic info in CellData.
	CellData cell_data;
	unique_cell_ids.push_back(cell->id());
	cell_id_to_index[cell->id()] = cell_index++;
	cell_data.cell = cell;

	// Get table cell accessibility attributes - note that these may
	// be missing or invalid, we'll correct them next.
	cell_data.row_index =
	GetSizeTAttribute(*cell, IntAttribute::kTableCellRowIndex);
	cell_data.row_span =
	GetSizeTAttribute(*cell, IntAttribute::kTableCellRowSpan);
	cell_data.aria_row_index =
	GetSizeTAttribute(*cell, IntAttribute::kAriaCellRowIndex);
	cell_data.col_index =
	GetSizeTAttribute(*cell, IntAttribute::kTableCellColumnIndex);
	cell_data.aria_col_index =
	GetSizeTAttribute(*cell, IntAttribute::kAriaCellColumnIndex);
	cell_data.col_span =
	GetSizeTAttribute(*cell, IntAttribute::kTableCellColumnSpan);

	// The col span and row span must be at least 1.
	cell_data.row_span = std::max(size_t{1}, cell_data.row_span);
	cell_data.col_span = std::max(size_t{1}, cell_data.col_span);

	// Ensure the column index must always be incrementing.
	cell_data.col_index = std::max(cell_data.col_index, current_col_index);

	// And update the spanned column index.
	spanned_col_index = std::max(spanned_col_index, cell_data.col_index);

	if (is_first_cell_in_row) {
	is_first_cell_in_row = false;

	// If it's the first cell in the row, ensure the row index is
	// incrementing. The rest of the cells in this row are forced to have
	// the same row index.
	if (cell_data.row_index > *current_row_index) {
	*current_row_index = cell_data.row_index;
	} else {
	cell_data.row_index = *current_row_index;
	}

	// The starting ARIA row and column index might be specified in
	// the row node, we should check there.
	if (!cell_data.aria_row_index) {
	cell_data.aria_row_index =
	GetSizeTAttribute(*row_node, IntAttribute::kAriaCellRowIndex);
	}
	if (!cell_data.aria_col_index) {
	cell_data.aria_col_index =
	GetSizeTAttribute(*row_node, IntAttribute::kAriaCellColumnIndex);
	}
	cell_data.aria_row_index =
	std::max(cell_data.aria_row_index, current_aria_row_index);
	current_aria_row_index = cell_data.aria_row_index;
	} else {
	// Don't allow the row index to change after the beginning
	// of a row.
	cell_data.row_index = *current_row_index;
	cell_data.aria_row_index = current_aria_row_index;
	}

	// Adjust the spanned col index by looking at the incremental row col map.
	// This map contains already filled in values, accounting for spans, of
	// all row, col indices. The map should have filled in all values we need
	// (upper left triangle of cells of the table).
	while (true) {
	const auto& row_it = incremental_row_col_map_.find(*current_row_index);
	if (row_it == incremental_row_col_map_.end()) {
	break;
	} else {
	const auto& col_it = row_it->second.find(spanned_col_index);
	if (col_it == row_it->second.end()) {
	break;
	} else {
	// A pre-existing cell resides in our desired position. Make a
	// best-fit to the right of the existing span.
	const CellData& spanned_cell_data = col_it->second;
	spanned_col_index =
	spanned_cell_data.col_index + spanned_cell_data.col_span;

	// Adjust the actual col index to be the best fit with the existing
	// spanned cell data.
	cell_data.col_index = spanned_col_index;
	}
	}
	}

	// Memoize the cell data using our incremental row col map.
	for (size_t r = cell_data.row_index;
	r < (cell_data.row_index + cell_data.row_span); r++) {
	for (size_t c = cell_data.col_index;
	c < (cell_data.col_index + cell_data.col_span); c++) {
	incremental_row_col_map_[r][c] = cell_data;
	}
	}

	// Ensure the ARIA col index is incrementing.
	cell_data.aria_col_index =
	std::max(cell_data.aria_col_index, current_aria_col_index);
	current_aria_col_index = cell_data.aria_col_index;

	// Update the row count and col count for the whole table to make
	// sure they're large enough to fit this cell, including its spans.
	// The -1 in the ARIA calculations is because ARIA indices are 1-based,
	// whereas all other indices are zero-based.
	row_count = std::max(row_count, cell_data.row_index + cell_data.row_span);
	col_count = std::max(col_count, cell_data.col_index + cell_data.col_span);
	if (aria_row_count != ax::mojom::kUnknownAriaColumnOrRowCount) {
	aria_row_count =
	std::max((aria_row_count),
	int{current_aria_row_index + cell_data.row_span - 1});
	}
	if (aria_col_count != ax::mojom::kUnknownAriaColumnOrRowCount) {
	aria_col_count =
	std::max((aria_col_count),
	int{current_aria_col_index + cell_data.col_span - 1});
	}
	// Update \|current_col_index\| to reflect the next available index after
	// this cell including its colspan. The next column index in this row
	// must be at least this large. Same for the current ARIA col index.
	current_col_index = cell_data.col_index + cell_data.col_span;
	current_aria_col_index = cell_data.aria_col_index + cell_data.col_span;
	spanned_col_index = current_col_index;

	// Add this cell to our vector.
	cell_data_vector.push_back(cell_data);
	}

	// At the end of each row, increment \|current_aria_row_index\| to reflect the
	// next available index after this row. The next row index must be at least
	// this large. Also update \|next_row_index\|.
	current_aria_row_index++;
	next_row_index = *current_row_index + 1;
	}
	}

	void AXTableInfo::BuildCellAndHeaderVectorsFromCellData() {
	// Allocate space for the 2-D array of cell IDs and 1-D
	// arrays of row headers and column headers.
	row_headers.resize(row_count);
	col_headers.resize(col_count);
	// Fill in the arrays.
	//
	// At this point we have computed valid row and column indices for
	// every cell in the table, and an accurate row and column count for the
	// whole table that fits every cell and its spans. The final step is to
	// fill in a 2-dimensional array that lets us look up an individual cell
	// by its (row, column) coordinates, plus arrays to hold row and column
	// headers.

	// For cells.
	cell_ids.resize(row_count);
	for (size_t r = 0; r < row_count; r++) {
	cell_ids[r].resize(col_count);
	for (size_t c = 0; c < col_count; c++) {
	const auto& row_it = incremental_row_col_map_.find(r);
	if (row_it != incremental_row_col_map_.end()) {
	const auto& col_it = row_it->second.find(c);
	if (col_it != row_it->second.end())
	cell_ids[r][c] = col_it->second.cell->id();
	}
	}
	}

	// No longer need this.
	incremental_row_col_map_.clear();

	// For relations.
	for (auto& cell_data : cell_data_vector) {
	for (size_t r = cell_data.row_index;
	r < cell_data.row_index + cell_data.row_span; r++) {
	DCHECK_LT(r, row_count);
	for (size_t c = cell_data.col_index;
	c < cell_data.col_index + cell_data.col_span; c++) {
	DCHECK_LT(c, col_count);
	AXNode* cell = cell_data.cell;
	if (cell->data().role == ax::mojom::Role::kColumnHeader) {
	col_headers[c].push_back(cell->id());
	all_headers.push_back(cell->id());
	} else if (cell->data().role == ax::mojom::Role::kRowHeader) {
	row_headers[r].push_back(cell->id());
	all_headers.push_back(cell->id());
	}
	}
	}
	}
	}

	void AXTableInfo::UpdateExtraMacNodes() {
	// On macOS, maintain additional AXNodes: one column node for each
	// column of the table, and one table header container.
	//
	// The nodes all set the table as the parent node, that way the Mac-specific
	// platform code can treat these nodes as additional children of the table
	// node.
	//
	// The columns have id -1, -2, -3, ... - this won't conflict with ids from
	// the source tree, which are all positive.
	//
	// Each column has the kColumnIndex attribute set, and then each of the cells
	// in that column gets added as an indirect ID. That exposes them as children
	// via Mac APIs but ensures we don't explore those nodes multiple times when
	// walking the tree. The column also has the ID of the first column header
	// set.
	//
	// The table header container is just a node with all of the headers in the
	// table as indirect children.

	if (!extra_mac_nodes.empty()) {
	// Delete old extra nodes.
	ClearExtraMacNodes();
	}

	// One node for each column, and one more for the table header container.
	size_t extra_node_count = col_count + 1;
	// Resize.
	extra_mac_nodes.resize(extra_node_count);

	std::vector<AXTreeObserver::Change> changes;
	changes.reserve(extra_node_count +
	1); // Room for extra nodes + table itself.

	// Create column nodes.
	for (size_t i = 0; i < col_count; i++) {
	extra_mac_nodes[i] = CreateExtraMacColumnNode(i);
	changes.push_back(AXTreeObserver::Change(
	extra_mac_nodes[i], AXTreeObserver::ChangeType::NODE_CREATED));
	}

	// Create table header container node.
	extra_mac_nodes[col_count] = CreateExtraMacTableHeaderNode();
	changes.push_back(AXTreeObserver::Change(
	extra_mac_nodes[col_count], AXTreeObserver::ChangeType::NODE_CREATED));

	// Update the columns to reflect current state of the table.
	for (size_t i = 0; i < col_count; i++)
	UpdateExtraMacColumnNodeAttributes(i);

	// Update the table header container to contain all headers.
	ui::AXNodeData data = extra_mac_nodes[col_count]->data();
	data.intlist_attributes.clear();
	data.AddIntListAttribute(ax::mojom::IntListAttribute::kIndirectChildIds,
	all_headers);
	extra_mac_nodes[col_count]->SetData(data);

	changes.push_back(AXTreeObserver::Change(
	table_node_, AXTreeObserver::ChangeType::NODE_CHANGED));
	for (AXTreeObserver& observer : tree_->observers()) {
	observer.OnAtomicUpdateFinished(tree_, false, changes);
	}
	}

	AXNode* AXTableInfo::CreateExtraMacColumnNode(size_t col_index) {
	int32_t id = tree_->GetNextNegativeInternalNodeId();
	size_t index_in_parent = col_index + table_node_->children().size();
	int32_t unignored_index_in_parent =
	col_index + table_node_->GetUnignoredChildCount();
	AXNode* node = new AXNode(tree_, table_node_, id, index_in_parent,
	unignored_index_in_parent);
	AXNodeData data;
	data.id = id;
	data.role = ax::mojom::Role::kColumn;
	node->SetData(data);
	for (AXTreeObserver& observer : tree_->observers())
	observer.OnNodeCreated(tree_, node);
	return node;
	}

	AXNode* AXTableInfo::CreateExtraMacTableHeaderNode() {
	int32_t id = tree_->GetNextNegativeInternalNodeId();
	size_t index_in_parent = col_count + table_node_->children().size();
	int32_t unignored_index_in_parent =
	col_count + table_node_->GetUnignoredChildCount();
	AXNode* node = new AXNode(tree_, table_node_, id, index_in_parent,
	unignored_index_in_parent);
	AXNodeData data;
	data.id = id;
	data.role = ax::mojom::Role::kTableHeaderContainer;
	node->SetData(data);

	for (AXTreeObserver& observer : tree_->observers())
	observer.OnNodeCreated(tree_, node);

	return node;
	}

	void AXTableInfo::UpdateExtraMacColumnNodeAttributes(size_t col_index) {
	ui::AXNodeData data = extra_mac_nodes[col_index]->data();
	data.int_attributes.clear();

	// Update the column index.
	data.AddIntAttribute(IntAttribute::kTableColumnIndex, int32_t{col_index});

	// Update the column header.
	if (!col_headers[col_index].empty()) {
	data.AddIntAttribute(IntAttribute::kTableColumnHeaderId,
	col_headers[col_index][0]);
	}

	// Update the list of cells in the column.
	data.intlist_attributes.clear();
	std::vector<int32_t> col_nodes;
	int32_t last = 0;
	for (size_t row_index = 0; row_index < row_count; row_index++) {
	int32_t cell_id = cell_ids[row_index][col_index];
	if (cell_id != 0 && cell_id != last)
	col_nodes.push_back(cell_id);
	last = cell_id;
	}
	data.AddIntListAttribute(ax::mojom::IntListAttribute::kIndirectChildIds,
	col_nodes);
	extra_mac_nodes[col_index]->SetData(data);
	}

	void AXTableInfo::ClearExtraMacNodes() {
	for (AXNode* extra_mac_node : extra_mac_nodes) {
	for (AXTreeObserver& observer : tree_->observers())
	observer.OnNodeWillBeDeleted(tree_, extra_mac_node);
	AXNode::AXID deleted_id = extra_mac_node->id();
	delete extra_mac_node;
	for (AXTreeObserver& observer : tree_->observers())
	observer.OnNodeDeleted(tree_, deleted_id);
	}
	extra_mac_nodes.clear();
	}

	std::string AXTableInfo::ToString() const {
	// First, scan through to get the length of the largest id.
	int padding = 0;
	for (size_t r = 0; r < row_count; r++) {
	for (size_t c = 0; c < col_count; c++) {
	// Extract the length of the id for padding purposes.
	padding = std::max(padding, static_cast<int>(log10(cell_ids[r][c])));
	}
	}

	std::string result;
	for (size_t r = 0; r < row_count; r++) {
	result += "\|";
	for (size_t c = 0; c < col_count; c++) {
	int cell_id = cell_ids[r][c];
	result += base::NumberToString(cell_id);
	int cell_padding = padding;
	if (cell_id != 0)
	cell_padding = padding - static_cast<int>(log10(cell_id));
	result += std::string(cell_padding, ' ') + '\|';
	}
	result += "\n";
	}
	return result;
	}

	AXTableInfo::AXTableInfo(AXTree* tree, AXNode* table_node)
	: tree_(tree), table_node_(table_node) {}

	AXTableInfo::~AXTableInfo() {
	if (!extra_mac_nodes.empty()) {
	ClearExtraMacNodes();
	for (AXTreeObserver& observer : tree_->observers()) {
	observer.OnAtomicUpdateFinished(
	tree_, false,
	{{table_node_, AXTreeObserver::ChangeType::NODE_CHANGED}});
	}
	}
	}

	} // namespace ui