path: root/accessible/base/CachedTableAccessible.cpp

/* -*- 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 "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<Accessible*, CachedTableAccessible>;
// 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<CachedTablesMap> 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<uint32_t, uint32_t> 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<uint32_t>(rowIdx) + cell->RowExtent() - 1;
    MOZ_ASSERT(lastRowForCell >= static_cast<uint32_t>(rowIdx));
    uint32_t lastColForCell = colIdx + cell->ColExtent() - 1;
    MOZ_ASSERT(lastColForCell >= colIdx);
    for (uint32_t spannedRow = static_cast<uint32_t>(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<CachedTableAccessible*>(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<Accessible*>(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<int32_t>(
              CacheKey::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<int32_t>(
              CacheKey::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<AccIterable> CachedTableCellAccessible::GetExplicitHeadersIterator() {
  if (RemoteAccessible* remoteAcc = mAcc->AsRemote()) {
    if (remoteAcc->mCachedFields) {
      if (auto headers =
              remoteAcc->mCachedFields->GetAttribute<nsTArray<uint64_t>>(
                  CacheKey::CellHeaders)) {
        return MakeUnique<RemoteAccIterator>(*headers, remoteAcc->Document());
      }
    }
  } else if (LocalAccessible* localAcc = mAcc->AsLocal()) {
    return MakeUnique<IDRefsIterator>(
        localAcc->Document(), localAcc->GetContent(), nsGkAtoms::headers);
  }
  return nullptr;
}

void CachedTableCellAccessible::ColHeaderCells(nsTArray<Accessible*>* aCells) {
  auto* table = static_cast<CachedTableAccessible*>(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<Accessible*>* aCells) {
  auto* table = static_cast<CachedTableAccessible*>(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