[ tor-browser ].git.dasho

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