accessible/base/CachedTableAccessible.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "CachedTableAccessible.h"
   8
   9 #include "AccIterator.h"
  10 #include "HTMLTableAccessible.h"
  11 #include "mozilla/ClearOnShutdown.h"
  12 #include "mozilla/StaticPtr.h"
  13 #include "mozilla/UniquePtr.h"
  14 #include "nsAccUtils.h"
  15 #include "nsIAccessiblePivot.h"
  16 #include "Pivot.h"
  17 #include "RemoteAccessible.h"
  18
  19 namespace mozilla::a11y {
  20
  21 // Used to search for table descendants relevant to table structure.
  22 class TablePartRule : public PivotRule {
  23  public:
  24   virtual uint16_t Match(Accessible* aAcc) override {
  25     role accRole = aAcc->Role();
  26     if (accRole == roles::CAPTION || aAcc->IsTableCell()) {
  27       return nsIAccessibleTraversalRule::FILTER_MATCH |
  28              nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
  29     }
  30     if (aAcc->IsTableRow()) {
  31       return nsIAccessibleTraversalRule::FILTER_MATCH;
  32     }
  33     if (aAcc->IsTable() ||
  34         // Generic containers.
  35         accRole == roles::TEXT || accRole == roles::TEXT_CONTAINER ||
  36         accRole == roles::SECTION ||
  37         // Row groups.
  38         accRole == roles::GROUPING) {
  39       // Walk inside these, but don't match them.
  40       return nsIAccessibleTraversalRule::FILTER_IGNORE;
  41     }
  42     return nsIAccessibleTraversalRule::FILTER_IGNORE |
  43            nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
  44   }
  45 };
  46
  47 // The Accessible* keys should only be used for lookup. They should not be
  48 // dereferenced.
  49 using CachedTablesMap = nsTHashMap<Accessible*, CachedTableAccessible>;
  50 // We use a global map rather than a map in each document for three reasons:
  51 // 1. We don't have a common base class for local and remote documents.
  52 // 2. It avoids wasting memory in a document that doesn't have any tables.
  53 // 3. It allows the cache management to be encapsulated here in
  54 // CachedTableAccessible.
  55 static StaticAutoPtr<CachedTablesMap> sCachedTables;
  56
  57 /* static */
  58 CachedTableAccessible* CachedTableAccessible::GetFrom(Accessible* aAcc) {
  59   MOZ_ASSERT(aAcc->IsTable());
  60   if (!sCachedTables) {
  61     sCachedTables = new CachedTablesMap();
  62     ClearOnShutdown(&sCachedTables);
  63   }
  64   return &sCachedTables->LookupOrInsertWith(
  65       aAcc, [&] { return CachedTableAccessible(aAcc); });
  66 }
  67
  68 /* static */
  69 void CachedTableAccessible::Invalidate(Accessible* aAcc) {
  70   if (!sCachedTables) {
  71     return;
  72   }
  73
  74   if (Accessible* table = nsAccUtils::TableFor(aAcc)) {
  75     // Destroy the instance (if any). We'll create a new one the next time it
  76     // is requested.
  77     sCachedTables->Remove(table);
  78   }
  79 }
  80
  81 CachedTableAccessible::CachedTableAccessible(Accessible* aAcc) : mAcc(aAcc) {
  82   MOZ_ASSERT(mAcc);
  83   // Build the cache. The cache can only be built once per instance. When it's
  84   // invalidated, we just throw away the instance and create a new one when
  85   // the cache is next needed.
  86   int32_t rowIdx = -1;
  87   uint32_t colIdx = 0;
  88   // Maps a column index to the cell index of its previous implicit column
  89   // header.
  90   nsTHashMap<uint32_t, uint32_t> prevColHeaders;
  91   Pivot pivot(mAcc);
  92   TablePartRule rule;
  93   for (Accessible* part = pivot.Next(mAcc, rule); part;
  94        part = pivot.Next(part, rule)) {
  95     role partRole = part->Role();
  96     if (partRole == roles::CAPTION) {
  97       // If there are multiple captions, use the first.
  98       if (!mCaptionAccID) {
  99         mCaptionAccID = part->ID();
 100       }
 101       continue;
 102     }
 103     if (part->IsTableRow()) {
 104       ++rowIdx;
 105       colIdx = 0;
 106       // This might be an empty row, so ensure a row here, as our row count is
 107       // based on the length of mRowColToCellIdx.
 108       EnsureRow(rowIdx);
 109       continue;
 110     }
 111     MOZ_ASSERT(part->IsTableCell());
 112     if (rowIdx == -1) {
 113       // We haven't created a row yet, so this cell must be outside a row.
 114       continue;
 115     }
 116     // Check for a cell spanning multiple rows which already occupies this
 117     // position. Keep incrementing until we find a vacant position.
 118     for (;;) {
 119       EnsureRowCol(rowIdx, colIdx);
 120       if (mRowColToCellIdx[rowIdx][colIdx] == kNoCellIdx) {
 121         // This position is not occupied.
 122         break;
 123       }
 124       // This position is occupied.
 125       ++colIdx;
 126     }
 127     // Create the cell.
 128     uint32_t cellIdx = mCells.Length();
 129     auto prevColHeader = prevColHeaders.MaybeGet(colIdx);
 130     auto cell = mCells.AppendElement(
 131         CachedTableCellAccessible(part->ID(), part, rowIdx, colIdx,
 132                                   prevColHeader ? *prevColHeader : kNoCellIdx));
 133     mAccToCellIdx.InsertOrUpdate(part, cellIdx);
 134     // Update our row/col map.
 135     // This cell might span multiple rows and/or columns. In that case, we need
 136     // to occupy multiple coordinates in the row/col map.
 137     uint32_t lastRowForCell =
 138         static_cast<uint32_t>(rowIdx) + cell->RowExtent() - 1;
 139     MOZ_ASSERT(lastRowForCell >= static_cast<uint32_t>(rowIdx));
 140     uint32_t lastColForCell = colIdx + cell->ColExtent() - 1;
 141     MOZ_ASSERT(lastColForCell >= colIdx);
 142     for (uint32_t spannedRow = static_cast<uint32_t>(rowIdx);
 143          spannedRow <= lastRowForCell; ++spannedRow) {
 144       for (uint32_t spannedCol = colIdx; spannedCol <= lastColForCell;
 145            ++spannedCol) {
 146         EnsureRowCol(spannedRow, spannedCol);
 147         auto& rowCol = mRowColToCellIdx[spannedRow][spannedCol];
 148         // If a cell already occupies this position, it overlaps with this one;
 149         // e.g. r1..2c2 and r2c1..2. In that case, we want to prefer the first
 150         // cell.
 151         if (rowCol == kNoCellIdx) {
 152           rowCol = cellIdx;
 153         }
 154       }
 155     }
 156     if (partRole == roles::COLUMNHEADER) {
 157       for (uint32_t spannedCol = colIdx; spannedCol <= lastColForCell;
 158            ++spannedCol) {
 159         prevColHeaders.InsertOrUpdate(spannedCol, cellIdx);
 160       }
 161     }
 162     // Increment for the next cell.
 163     colIdx = lastColForCell + 1;
 164   }
 165 }
 166
 167 void CachedTableAccessible::EnsureRow(uint32_t aRowIdx) {
 168   if (mRowColToCellIdx.Length() <= aRowIdx) {
 169     mRowColToCellIdx.AppendElements(aRowIdx - mRowColToCellIdx.Length() + 1);
 170   }
 171   MOZ_ASSERT(mRowColToCellIdx.Length() > aRowIdx);
 172 }
 173
 174 void CachedTableAccessible::EnsureRowCol(uint32_t aRowIdx, uint32_t aColIdx) {
 175   EnsureRow(aRowIdx);
 176   auto& row = mRowColToCellIdx[aRowIdx];
 177   if (mColCount <= aColIdx) {
 178     mColCount = aColIdx + 1;
 179   }
 180   row.SetCapacity(mColCount);
 181   for (uint32_t newCol = row.Length(); newCol <= aColIdx; ++newCol) {
 182     // An entry doesn't yet exist for this column in this row.
 183     row.AppendElement(kNoCellIdx);
 184   }
 185   MOZ_ASSERT(row.Length() > aColIdx);
 186 }
 187
 188 Accessible* CachedTableAccessible::Caption() const {
 189   if (mCaptionAccID) {
 190     Accessible* caption = nsAccUtils::GetAccessibleByID(
 191         nsAccUtils::DocumentFor(mAcc), mCaptionAccID);
 192     MOZ_ASSERT(caption, "Dead caption Accessible!");
 193     MOZ_ASSERT(caption->Role() == roles::CAPTION, "Caption has wrong role");
 194     return caption;
 195   }
 196   return nullptr;
 197 }
 198
 199 void CachedTableAccessible::Summary(nsString& aSummary) {
 200   if (Caption()) {
 201     // If there's a caption, we map caption to Name and summary to Description.
 202     mAcc->Description(aSummary);
 203   } else {
 204     // If there's no caption, we map summary to Name.
 205     mAcc->Name(aSummary);
 206   }
 207 }
 208
 209 Accessible* CachedTableAccessible::CellAt(uint32_t aRowIdx, uint32_t aColIdx) {
 210   int32_t cellIdx = CellIndexAt(aRowIdx, aColIdx);
 211   if (cellIdx == -1) {
 212     return nullptr;
 213   }
 214   return mCells[cellIdx].Acc(mAcc);
 215 }
 216
 217 bool CachedTableAccessible::IsProbablyLayoutTable() {
 218   if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) {
 219     return remoteAcc->TableIsProbablyForLayout();
 220   }
 221   if (auto* localTable = HTMLTableAccessible::GetFrom(mAcc->AsLocal())) {
 222     return localTable->IsProbablyLayoutTable();
 223   }
 224   return false;
 225 }
 226
 227 /* static */
 228 CachedTableCellAccessible* CachedTableCellAccessible::GetFrom(
 229     Accessible* aAcc) {
 230   MOZ_ASSERT(aAcc->IsTableCell());
 231   for (Accessible* parent = aAcc; parent; parent = parent->Parent()) {
 232     if (parent->IsDoc()) {
 233       break;  // Never cross document boundaries.
 234     }
 235     TableAccessible* table = parent->AsTable();
 236     if (!table) {
 237       continue;
 238     }
 239     if (LocalAccessible* local = parent->AsLocal()) {
 240       nsIContent* content = local->GetContent();
 241       if (content && content->IsXULElement()) {
 242         // XUL tables don't use CachedTableAccessible.
 243         break;
 244       }
 245     }
 246     // Non-XUL tables only use CachedTableAccessible.
 247     auto* cachedTable = static_cast<CachedTableAccessible*>(table);
 248     if (auto cellIdx = cachedTable->mAccToCellIdx.Lookup(aAcc)) {
 249       return &cachedTable->mCells[*cellIdx];
 250     }
 251     // We found a table, but it doesn't know about this cell. This can happen
 252     // if a cell is outside of a row due to authoring error. We must not search
 253     // ancestor tables, since this cell's data is not valid there and vice
 254     // versa.
 255     break;
 256   }
 257   return nullptr;
 258 }
 259
 260 Accessible* CachedTableCellAccessible::Acc(Accessible* aTableAcc) const {
 261   Accessible* acc =
 262       nsAccUtils::GetAccessibleByID(nsAccUtils::DocumentFor(aTableAcc), mAccID);
 263   MOZ_DIAGNOSTIC_ASSERT(acc == mAcc, "Cell's cached mAcc is dead!");
 264   return acc;
 265 }
 266
 267 TableAccessible* CachedTableCellAccessible::Table() const {
 268   for (const Accessible* acc = mAcc; acc; acc = acc->Parent()) {
 269     // Since the caller has this cell, the table is already created, so it's
 270     // okay to ignore the const restriction here.
 271     if (TableAccessible* table = const_cast<Accessible*>(acc)->AsTable()) {
 272       return table;
 273     }
 274   }
 275   return nullptr;
 276 }
 277
 278 uint32_t CachedTableCellAccessible::ColExtent() const {
 279   if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) {
 280     if (remoteAcc->mCachedFields) {
 281       if (auto colSpan = remoteAcc->mCachedFields->GetAttribute<int32_t>(
 282               CacheKey::ColSpan)) {
 283         MOZ_ASSERT(*colSpan > 0);
 284         return *colSpan;
 285       }
 286     }
 287   } else if (auto* cell = HTMLTableCellAccessible::GetFrom(mAcc->AsLocal())) {
 288     // For HTML table cells, we must use the HTMLTableCellAccessible
 289     // GetColExtent method rather than using the DOM attributes directly.
 290     // This is because of things like rowspan="0" which depend on knowing
 291     // about thead, tbody, etc., which is info we don't have in the a11y tree.
 292     uint32_t colExtent = cell->ColExtent();
 293     MOZ_ASSERT(colExtent > 0);
 294     if (colExtent > 0) {
 295       return colExtent;
 296     }
 297   }
 298   return 1;
 299 }
 300
 301 uint32_t CachedTableCellAccessible::RowExtent() const {
 302   if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) {
 303     if (remoteAcc->mCachedFields) {
 304       if (auto rowSpan = remoteAcc->mCachedFields->GetAttribute<int32_t>(
 305               CacheKey::RowSpan)) {
 306         MOZ_ASSERT(*rowSpan > 0);
 307         return *rowSpan;
 308       }
 309     }
 310   } else if (auto* cell = HTMLTableCellAccessible::GetFrom(mAcc->AsLocal())) {
 311     // For HTML table cells, we must use the HTMLTableCellAccessible
 312     // GetRowExtent method rather than using the DOM attributes directly.
 313     // This is because of things like rowspan="0" which depend on knowing
 314     // about thead, tbody, etc., which is info we don't have in the a11y tree.
 315     uint32_t rowExtent = cell->RowExtent();
 316     MOZ_ASSERT(rowExtent > 0);
 317     if (rowExtent > 0) {
 318       return rowExtent;
 319     }
 320   }
 321   return 1;
 322 }
 323
 324 UniquePtr<AccIterable> CachedTableCellAccessible::GetExplicitHeadersIterator() {
 325   if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) {
 326     if (remoteAcc->mCachedFields) {
 327       if (auto headers =
 328               remoteAcc->mCachedFields->GetAttribute<nsTArray<uint64_t>>(
 329                   CacheKey::CellHeaders)) {
 330         return MakeUnique<RemoteAccIterator>(*headers, remoteAcc->Document());
 331       }
 332     }
 333   } else if (LocalAccessible* localAcc = mAcc->AsLocal()) {
 334     return MakeUnique<IDRefsIterator>(
 335         localAcc->Document(), localAcc->GetContent(), nsGkAtoms::headers);
 336   }
 337   return nullptr;
 338 }
 339
 340 void CachedTableCellAccessible::ColHeaderCells(nsTArray<Accessible*>* aCells) {
 341   auto* table = static_cast<CachedTableAccessible*>(Table());
 342   if (!table) {
 343     return;
 344   }
 345   if (auto iter = GetExplicitHeadersIterator()) {
 346     while (Accessible* header = iter->Next()) {
 347       role headerRole = header->Role();
 348       if (headerRole == roles::COLUMNHEADER) {
 349         aCells->AppendElement(header);
 350       } else if (headerRole != roles::ROWHEADER) {
 351         // Treat this cell as a column header only if it's in the same column.
 352         if (auto cellIdx = table->mAccToCellIdx.Lookup(header)) {
 353           CachedTableCellAccessible& cell = table->mCells[*cellIdx];
 354           if (cell.ColIdx() == ColIdx()) {
 355             aCells->AppendElement(header);
 356           }
 357         }
 358       }
 359     }
 360     if (!aCells->IsEmpty()) {
 361       return;
 362     }
 363   }
 364   Accessible* doc = nsAccUtils::DocumentFor(table->AsAccessible());
 365   // Each cell stores its previous implicit column header, effectively forming a
 366   // linked list. We traverse that to get all the headers.
 367   CachedTableCellAccessible* cell = this;
 368   for (;;) {
 369     if (cell->mPrevColHeaderCellIdx == kNoCellIdx) {
 370       break;  // No more headers.
 371     }
 372     cell = &table->mCells[cell->mPrevColHeaderCellIdx];
 373     Accessible* cellAcc = nsAccUtils::GetAccessibleByID(doc, cell->mAccID);
 374     aCells->AppendElement(cellAcc);
 375   }
 376 }
 377
 378 void CachedTableCellAccessible::RowHeaderCells(nsTArray<Accessible*>* aCells) {
 379   auto* table = static_cast<CachedTableAccessible*>(Table());
 380   if (!table) {
 381     return;
 382   }
 383   if (auto iter = GetExplicitHeadersIterator()) {
 384     while (Accessible* header = iter->Next()) {
 385       role headerRole = header->Role();
 386       if (headerRole == roles::ROWHEADER) {
 387         aCells->AppendElement(header);
 388       } else if (headerRole != roles::COLUMNHEADER) {
 389         // Treat this cell as a row header only if it's in the same row.
 390         if (auto cellIdx = table->mAccToCellIdx.Lookup(header)) {
 391           CachedTableCellAccessible& cell = table->mCells[*cellIdx];
 392           if (cell.RowIdx() == RowIdx()) {
 393             aCells->AppendElement(header);
 394           }
 395         }
 396       }
 397     }
 398     if (!aCells->IsEmpty()) {
 399       return;
 400     }
 401   }
 402   Accessible* doc = nsAccUtils::DocumentFor(table->AsAccessible());
 403   // We don't cache implicit row headers because there are usually not that many
 404   // cells per row. Get all the row headers on the row before this cell.
 405   uint32_t row = RowIdx();
 406   uint32_t thisCol = ColIdx();
 407   for (uint32_t col = thisCol - 1; col < thisCol; --col) {
 408     int32_t cellIdx = table->CellIndexAt(row, col);
 409     if (cellIdx == -1) {
 410       continue;
 411     }
 412     CachedTableCellAccessible& cell = table->mCells[cellIdx];
 413     Accessible* cellAcc = nsAccUtils::GetAccessibleByID(doc, cell.mAccID);
 414     MOZ_ASSERT(cellAcc);
 415     // cell might span multiple columns. We don't want to visit it multiple
 416     // times, so ensure col is set to cell's starting column.
 417     col = cell.ColIdx();
 418     if (cellAcc->Role() != roles::ROWHEADER) {
 419       continue;
 420     }
 421     aCells->AppendElement(cellAcc);
 422   }
 423 }
 424
 425 bool CachedTableCellAccessible::Selected() {
 426   return mAcc->State() & states::SELECTED;
 427 }
 428
 429 }  // namespace mozilla::a11y