From 6bf0a5cb5034a7e684dcc3500e841785237ce2dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 19:32:43 +0200 Subject: Adding upstream version 1:115.7.0. Signed-off-by: Daniel Baumann --- accessible/base/CachedTableAccessible.cpp | 430 ++++++++++++++++++++++++++++++ 1 file changed, 430 insertions(+) create mode 100644 accessible/base/CachedTableAccessible.cpp (limited to 'accessible/base/CachedTableAccessible.cpp') diff --git a/accessible/base/CachedTableAccessible.cpp b/accessible/base/CachedTableAccessible.cpp new file mode 100644 index 0000000000..31d5df08e9 --- /dev/null +++ b/accessible/base/CachedTableAccessible.cpp @@ -0,0 +1,430 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "CachedTableAccessible.h" + +#include "AccIterator.h" +#include "DocAccessibleParent.h" +#include "HTMLTableAccessible.h" +#include "mozilla/ClearOnShutdown.h" +#include "mozilla/StaticPtr.h" +#include "mozilla/UniquePtr.h" +#include "nsAccUtils.h" +#include "nsIAccessiblePivot.h" +#include "Pivot.h" +#include "RemoteAccessible.h" + +namespace mozilla::a11y { + +// Used to search for table descendants relevant to table structure. +class TablePartRule : public PivotRule { + public: + virtual uint16_t Match(Accessible* aAcc) override { + role accRole = aAcc->Role(); + if (accRole == roles::CAPTION || aAcc->IsTableCell()) { + return nsIAccessibleTraversalRule::FILTER_MATCH | + nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE; + } + if (aAcc->IsTableRow()) { + return nsIAccessibleTraversalRule::FILTER_MATCH; + } + if (aAcc->IsTable() || + // Generic containers. + accRole == roles::TEXT || accRole == roles::TEXT_CONTAINER || + accRole == roles::SECTION || + // Row groups. + accRole == roles::GROUPING) { + // Walk inside these, but don't match them. + return nsIAccessibleTraversalRule::FILTER_IGNORE; + } + return nsIAccessibleTraversalRule::FILTER_IGNORE | + nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE; + } +}; + +// The Accessible* keys should only be used for lookup. They should not be +// dereferenced. +using CachedTablesMap = nsTHashMap; +// We use a global map rather than a map in each document for three reasons: +// 1. We don't have a common base class for local and remote documents. +// 2. It avoids wasting memory in a document that doesn't have any tables. +// 3. It allows the cache management to be encapsulated here in +// CachedTableAccessible. +static StaticAutoPtr sCachedTables; + +/* static */ +CachedTableAccessible* CachedTableAccessible::GetFrom(Accessible* aAcc) { + MOZ_ASSERT(aAcc->IsTable()); + if (!sCachedTables) { + sCachedTables = new CachedTablesMap(); + ClearOnShutdown(&sCachedTables); + } + return &sCachedTables->LookupOrInsertWith( + aAcc, [&] { return CachedTableAccessible(aAcc); }); +} + +/* static */ +void CachedTableAccessible::Invalidate(Accessible* aAcc) { + if (!sCachedTables) { + return; + } + + if (Accessible* table = nsAccUtils::TableFor(aAcc)) { + // Destroy the instance (if any). We'll create a new one the next time it + // is requested. + sCachedTables->Remove(table); + } +} + +CachedTableAccessible::CachedTableAccessible(Accessible* aAcc) : mAcc(aAcc) { + MOZ_ASSERT(mAcc); + // Build the cache. The cache can only be built once per instance. When it's + // invalidated, we just throw away the instance and create a new one when + // the cache is next needed. + int32_t rowIdx = -1; + uint32_t colIdx = 0; + // Maps a column index to the cell index of its previous implicit column + // header. + nsTHashMap prevColHeaders; + Pivot pivot(mAcc); + TablePartRule rule; + for (Accessible* part = pivot.Next(mAcc, rule); part; + part = pivot.Next(part, rule)) { + role partRole = part->Role(); + if (partRole == roles::CAPTION) { + // If there are multiple captions, use the first. + if (!mCaptionAccID) { + mCaptionAccID = part->ID(); + } + continue; + } + if (part->IsTableRow()) { + ++rowIdx; + colIdx = 0; + // This might be an empty row, so ensure a row here, as our row count is + // based on the length of mRowColToCellIdx. + EnsureRow(rowIdx); + continue; + } + MOZ_ASSERT(part->IsTableCell()); + if (rowIdx == -1) { + // We haven't created a row yet, so this cell must be outside a row. + continue; + } + // Check for a cell spanning multiple rows which already occupies this + // position. Keep incrementing until we find a vacant position. + for (;;) { + EnsureRowCol(rowIdx, colIdx); + if (mRowColToCellIdx[rowIdx][colIdx] == kNoCellIdx) { + // This position is not occupied. + break; + } + // This position is occupied. + ++colIdx; + } + // Create the cell. + uint32_t cellIdx = mCells.Length(); + auto prevColHeader = prevColHeaders.MaybeGet(colIdx); + auto cell = mCells.AppendElement( + CachedTableCellAccessible(part->ID(), part, rowIdx, colIdx, + prevColHeader ? *prevColHeader : kNoCellIdx)); + mAccToCellIdx.InsertOrUpdate(part, cellIdx); + // Update our row/col map. + // This cell might span multiple rows and/or columns. In that case, we need + // to occupy multiple coordinates in the row/col map. + uint32_t lastRowForCell = + static_cast(rowIdx) + cell->RowExtent() - 1; + MOZ_ASSERT(lastRowForCell >= static_cast(rowIdx)); + uint32_t lastColForCell = colIdx + cell->ColExtent() - 1; + MOZ_ASSERT(lastColForCell >= colIdx); + for (uint32_t spannedRow = static_cast(rowIdx); + spannedRow <= lastRowForCell; ++spannedRow) { + for (uint32_t spannedCol = colIdx; spannedCol <= lastColForCell; + ++spannedCol) { + EnsureRowCol(spannedRow, spannedCol); + auto& rowCol = mRowColToCellIdx[spannedRow][spannedCol]; + // If a cell already occupies this position, it overlaps with this one; + // e.g. r1..2c2 and r2c1..2. In that case, we want to prefer the first + // cell. + if (rowCol == kNoCellIdx) { + rowCol = cellIdx; + } + } + } + if (partRole == roles::COLUMNHEADER) { + for (uint32_t spannedCol = colIdx; spannedCol <= lastColForCell; + ++spannedCol) { + prevColHeaders.InsertOrUpdate(spannedCol, cellIdx); + } + } + // Increment for the next cell. + colIdx = lastColForCell + 1; + } +} + +void CachedTableAccessible::EnsureRow(uint32_t aRowIdx) { + if (mRowColToCellIdx.Length() <= aRowIdx) { + mRowColToCellIdx.AppendElements(aRowIdx - mRowColToCellIdx.Length() + 1); + } + MOZ_ASSERT(mRowColToCellIdx.Length() > aRowIdx); +} + +void CachedTableAccessible::EnsureRowCol(uint32_t aRowIdx, uint32_t aColIdx) { + EnsureRow(aRowIdx); + auto& row = mRowColToCellIdx[aRowIdx]; + if (mColCount <= aColIdx) { + mColCount = aColIdx + 1; + } + row.SetCapacity(mColCount); + for (uint32_t newCol = row.Length(); newCol <= aColIdx; ++newCol) { + // An entry doesn't yet exist for this column in this row. + row.AppendElement(kNoCellIdx); + } + MOZ_ASSERT(row.Length() > aColIdx); +} + +Accessible* CachedTableAccessible::Caption() const { + if (mCaptionAccID) { + Accessible* caption = nsAccUtils::GetAccessibleByID( + nsAccUtils::DocumentFor(mAcc), mCaptionAccID); + MOZ_ASSERT(caption, "Dead caption Accessible!"); + MOZ_ASSERT(caption->Role() == roles::CAPTION, "Caption has wrong role"); + return caption; + } + return nullptr; +} + +void CachedTableAccessible::Summary(nsString& aSummary) { + if (Caption()) { + // If there's a caption, we map caption to Name and summary to Description. + mAcc->Description(aSummary); + } else { + // If there's no caption, we map summary to Name. + mAcc->Name(aSummary); + } +} + +Accessible* CachedTableAccessible::CellAt(uint32_t aRowIdx, uint32_t aColIdx) { + int32_t cellIdx = CellIndexAt(aRowIdx, aColIdx); + if (cellIdx == -1) { + return nullptr; + } + return mCells[cellIdx].Acc(mAcc); +} + +bool CachedTableAccessible::IsProbablyLayoutTable() { + if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) { + return remoteAcc->TableIsProbablyForLayout(); + } + if (auto* localTable = HTMLTableAccessible::GetFrom(mAcc->AsLocal())) { + return localTable->IsProbablyLayoutTable(); + } + return false; +} + +/* static */ +CachedTableCellAccessible* CachedTableCellAccessible::GetFrom( + Accessible* aAcc) { + MOZ_ASSERT(aAcc->IsTableCell()); + for (Accessible* parent = aAcc; parent; parent = parent->Parent()) { + if (parent->IsDoc()) { + break; // Never cross document boundaries. + } + TableAccessible* table = parent->AsTable(); + if (!table) { + continue; + } + if (LocalAccessible* local = parent->AsLocal()) { + nsIContent* content = local->GetContent(); + if (content && content->IsXULElement()) { + // XUL tables don't use CachedTableAccessible. + break; + } + } + // Non-XUL tables only use CachedTableAccessible. + auto* cachedTable = static_cast(table); + if (auto cellIdx = cachedTable->mAccToCellIdx.Lookup(aAcc)) { + return &cachedTable->mCells[*cellIdx]; + } + // We found a table, but it doesn't know about this cell. This can happen + // if a cell is outside of a row due to authoring error. We must not search + // ancestor tables, since this cell's data is not valid there and vice + // versa. + break; + } + return nullptr; +} + +Accessible* CachedTableCellAccessible::Acc(Accessible* aTableAcc) const { + Accessible* acc = + nsAccUtils::GetAccessibleByID(nsAccUtils::DocumentFor(aTableAcc), mAccID); + MOZ_DIAGNOSTIC_ASSERT(acc == mAcc, "Cell's cached mAcc is dead!"); + return acc; +} + +TableAccessible* CachedTableCellAccessible::Table() const { + for (const Accessible* acc = mAcc; acc; acc = acc->Parent()) { + // Since the caller has this cell, the table is already created, so it's + // okay to ignore the const restriction here. + if (TableAccessible* table = const_cast(acc)->AsTable()) { + return table; + } + } + return nullptr; +} + +uint32_t CachedTableCellAccessible::ColExtent() const { + if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) { + if (remoteAcc->mCachedFields) { + if (auto colSpan = remoteAcc->mCachedFields->GetAttribute( + nsGkAtoms::colspan)) { + MOZ_ASSERT(*colSpan > 0); + return *colSpan; + } + } + } else if (auto* cell = HTMLTableCellAccessible::GetFrom(mAcc->AsLocal())) { + // For HTML table cells, we must use the HTMLTableCellAccessible + // GetColExtent method rather than using the DOM attributes directly. + // This is because of things like rowspan="0" which depend on knowing + // about thead, tbody, etc., which is info we don't have in the a11y tree. + uint32_t colExtent = cell->ColExtent(); + MOZ_ASSERT(colExtent > 0); + if (colExtent > 0) { + return colExtent; + } + } + return 1; +} + +uint32_t CachedTableCellAccessible::RowExtent() const { + if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) { + if (remoteAcc->mCachedFields) { + if (auto rowSpan = remoteAcc->mCachedFields->GetAttribute( + nsGkAtoms::rowspan)) { + MOZ_ASSERT(*rowSpan > 0); + return *rowSpan; + } + } + } else if (auto* cell = HTMLTableCellAccessible::GetFrom(mAcc->AsLocal())) { + // For HTML table cells, we must use the HTMLTableCellAccessible + // GetRowExtent method rather than using the DOM attributes directly. + // This is because of things like rowspan="0" which depend on knowing + // about thead, tbody, etc., which is info we don't have in the a11y tree. + uint32_t rowExtent = cell->RowExtent(); + MOZ_ASSERT(rowExtent > 0); + if (rowExtent > 0) { + return rowExtent; + } + } + return 1; +} + +UniquePtr CachedTableCellAccessible::GetExplicitHeadersIterator() { + if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) { + if (remoteAcc->mCachedFields) { + if (auto headers = + remoteAcc->mCachedFields->GetAttribute>( + nsGkAtoms::headers)) { + return MakeUnique(*headers, remoteAcc->Document()); + } + } + } else if (LocalAccessible* localAcc = mAcc->AsLocal()) { + return MakeUnique( + localAcc->Document(), localAcc->GetContent(), nsGkAtoms::headers); + } + return nullptr; +} + +void CachedTableCellAccessible::ColHeaderCells(nsTArray* aCells) { + auto* table = static_cast(Table()); + if (!table) { + return; + } + if (auto iter = GetExplicitHeadersIterator()) { + while (Accessible* header = iter->Next()) { + role headerRole = header->Role(); + if (headerRole == roles::COLUMNHEADER) { + aCells->AppendElement(header); + } else if (headerRole != roles::ROWHEADER) { + // Treat this cell as a column header only if it's in the same column. + if (auto cellIdx = table->mAccToCellIdx.Lookup(header)) { + CachedTableCellAccessible& cell = table->mCells[*cellIdx]; + if (cell.ColIdx() == ColIdx()) { + aCells->AppendElement(header); + } + } + } + } + if (!aCells->IsEmpty()) { + return; + } + } + Accessible* doc = nsAccUtils::DocumentFor(table->AsAccessible()); + // Each cell stores its previous implicit column header, effectively forming a + // linked list. We traverse that to get all the headers. + CachedTableCellAccessible* cell = this; + for (;;) { + if (cell->mPrevColHeaderCellIdx == kNoCellIdx) { + break; // No more headers. + } + cell = &table->mCells[cell->mPrevColHeaderCellIdx]; + Accessible* cellAcc = nsAccUtils::GetAccessibleByID(doc, cell->mAccID); + aCells->AppendElement(cellAcc); + } +} + +void CachedTableCellAccessible::RowHeaderCells(nsTArray* aCells) { + auto* table = static_cast(Table()); + if (!table) { + return; + } + if (auto iter = GetExplicitHeadersIterator()) { + while (Accessible* header = iter->Next()) { + role headerRole = header->Role(); + if (headerRole == roles::ROWHEADER) { + aCells->AppendElement(header); + } else if (headerRole != roles::COLUMNHEADER) { + // Treat this cell as a row header only if it's in the same row. + if (auto cellIdx = table->mAccToCellIdx.Lookup(header)) { + CachedTableCellAccessible& cell = table->mCells[*cellIdx]; + if (cell.RowIdx() == RowIdx()) { + aCells->AppendElement(header); + } + } + } + } + if (!aCells->IsEmpty()) { + return; + } + } + Accessible* doc = nsAccUtils::DocumentFor(table->AsAccessible()); + // We don't cache implicit row headers because there are usually not that many + // cells per row. Get all the row headers on the row before this cell. + uint32_t row = RowIdx(); + uint32_t thisCol = ColIdx(); + for (uint32_t col = thisCol - 1; col < thisCol; --col) { + int32_t cellIdx = table->CellIndexAt(row, col); + if (cellIdx == -1) { + continue; + } + CachedTableCellAccessible& cell = table->mCells[cellIdx]; + Accessible* cellAcc = nsAccUtils::GetAccessibleByID(doc, cell.mAccID); + MOZ_ASSERT(cellAcc); + // cell might span multiple columns. We don't want to visit it multiple + // times, so ensure col is set to cell's starting column. + col = cell.ColIdx(); + if (cellAcc->Role() != roles::ROWHEADER) { + continue; + } + aCells->AppendElement(cellAcc); + } +} + +bool CachedTableCellAccessible::Selected() { + return mAcc->State() & states::SELECTED; +} + +} // namespace mozilla::a11y -- cgit v1.2.3