Bug 1638238: Cache previous column header for each cell to make TableCellAccessible::ColHeaders faster. r=eeejay
authorJames Teh <jteh@mozilla.com>
Mon, 25 May 2020 14:15:57 +0000
changeset 532094 da2c7b0ac9a44e44000a6be1cea9d753c33784d4
parent 532093 0b15f53e5fc77898c06c1f25d0db4a688028b805
child 532095 dd35edffc6dffb7ae6a4050b955c6e7855cdffcd
push id37449
push userncsoregi@mozilla.com
push dateTue, 26 May 2020 02:38:57 +0000
treeherdermozilla-central@da2c7b0ac9a4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerseeejay
bugs1638238
milestone78.0a1
first release with
nightly linux32
da2c7b0ac9a4 / 78.0a1 / 20200526023857 / files
nightly linux64
da2c7b0ac9a4 / 78.0a1 / 20200526023857 / files
nightly mac
da2c7b0ac9a4 / 78.0a1 / 20200526023857 / files
nightly win32
da2c7b0ac9a4 / 78.0a1 / 20200526023857 / files
nightly win64
da2c7b0ac9a4 / 78.0a1 / 20200526023857 / files
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
releases
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1638238: Cache previous column header for each cell to make TableCellAccessible::ColHeaders faster. r=eeejay Previously, to get the column headers for a cell when there weren't explicit headers, we walked over all previous cells in the column looking for headers. For large tables with thousands of rows, this was very expensive, particularly when Windows screen readers rendered virtual buffers, fetching headers for all cells. To speed this up, we now lazily cache the previous column header for each cell. We even cache whether there is no previous header, since that is quite common and we don't want to pointlessly walk in that case. Subsequent cells utilise the cached values (if any) for prior cells. We don't store the cache on individual TableCellAccessibles because that would require us to walk all cells to invalidate the cache, even if few or no cells had cached values. Instead, we store the cache as a hash table on the TableAccessible. This way, we can just clear the cache whenever a column header is added to the tree. We invalidate the cache whenever a column header is bound to its parent. We don't need to invalidate the cache for removals because we instead just ignore defunct Accessibles in the cache. Differential Revision: https://phabricator.services.mozilla.com/D76106
accessible/generic/Accessible.cpp
accessible/generic/TableAccessible.h
accessible/generic/TableCellAccessible.cpp
accessible/generic/TableCellAccessible.h
accessible/tests/mochitest/table/a11y.ini
accessible/tests/mochitest/table/test_table_mutation.html
--- a/accessible/generic/Accessible.cpp
+++ b/accessible/generic/Accessible.cpp
@@ -2021,16 +2021,25 @@ void Accessible::BindToParent(Accessible
   if (mParent->HasNameDependentParent() || mParent->IsXULListItem())
     mContextFlags |= eHasNameDependentParent;
   else
     mContextFlags &= ~eHasNameDependentParent;
 
   mContextFlags |=
       static_cast<uint32_t>((mParent->IsAlert() || mParent->IsInsideAlert())) &
       eInsideAlert;
+
+  // if a new column header is being added, invalidate the table's header cache.
+  TableCellAccessible* cell = AsTableCell();
+  if (cell && Role() == roles::COLUMNHEADER) {
+    TableAccessible* table = cell->Table();
+    if (table) {
+      table->GetHeaderCache().Clear();
+    }
+  }
 }
 
 // Accessible protected
 void Accessible::UnbindFromParent() {
   mParent = nullptr;
   mIndexInParent = -1;
   mInt.mIndexOfEmbeddedChild = -1;
   if (IsProxy()) MOZ_CRASH("this should never be called on proxy wrappers");
--- a/accessible/generic/TableAccessible.h
+++ b/accessible/generic/TableAccessible.h
@@ -179,24 +179,39 @@ class TableAccessible {
    */
   virtual bool IsProbablyLayoutTable();
 
   /**
    * Convert the table to an Accessible*.
    */
   virtual Accessible* AsAccessible() = 0;
 
+  typedef nsRefPtrHashtable<nsPtrHashKey<const TableCellAccessible>, Accessible>
+      HeaderCache;
+
+  /**
+   * Get the header cache, which maps a TableCellAccessible to its previous
+   * header.
+   * Although this data is only used in TableCellAccessible, it is stored on
+   * TableAccessible so the cache can be easily invalidated when the table
+   * is mutated.
+   */
+  HeaderCache& GetHeaderCache() { return mHeaderCache; }
+
  protected:
   /**
    * Return row accessible at the given row index.
    */
   Accessible* RowAt(int32_t aRow);
 
   /**
    * Return cell accessible at the given column index in the row.
    */
   Accessible* CellInRowAt(Accessible* aRow, int32_t aColumn);
+
+ private:
+  HeaderCache mHeaderCache;
 };
 
 }  // namespace a11y
 }  // namespace mozilla
 
 #endif
--- a/accessible/generic/TableCellAccessible.cpp
+++ b/accessible/generic/TableCellAccessible.cpp
@@ -29,29 +29,72 @@ void TableCellAccessible::RowHeaderCells
 
     // Avoid addding cells multiple times, if this cell spans more columns
     // we'll get it later.
     if (tableCell->ColIdx() == curColIdx && cell->Role() == roles::ROWHEADER)
       aCells->AppendElement(cell);
   }
 }
 
-void TableCellAccessible::ColHeaderCells(nsTArray<Accessible*>* aCells) {
-  uint32_t rowIdx = RowIdx(), colIdx = ColIdx();
+Accessible* TableCellAccessible::PrevColHeader() {
   TableAccessible* table = Table();
-  if (!table) return;
+  if (!table) {
+    return nullptr;
+  }
 
-  // Move up to find column header cells
+  TableAccessible::HeaderCache& cache = table->GetHeaderCache();
+  bool inCache = false;
+  Accessible* cachedHeader = cache.GetWeak(this, &inCache);
+  if (inCache) {
+    // Cached but null means we know there is no previous column header.
+    // if defunct, the cell was removed, so behave as if there is no cached
+    // value.
+    if (!cachedHeader || !cachedHeader->IsDefunct()) {
+      return cachedHeader;
+    }
+  }
+
+  uint32_t rowIdx = RowIdx(), colIdx = ColIdx();
   for (uint32_t curRowIdx = rowIdx - 1; curRowIdx < rowIdx; curRowIdx--) {
     Accessible* cell = table->CellAt(curRowIdx, colIdx);
-    if (!cell) continue;
-
+    if (!cell) {
+      continue;
+    }
     // CellAt should always return a TableCellAccessible (XXX Bug 587529)
     TableCellAccessible* tableCell = cell->AsTableCell();
-    NS_ASSERTION(tableCell, "cell should be a table cell!");
-    if (!tableCell) continue;
+    MOZ_ASSERT(tableCell, "cell should be a table cell!");
+    if (!tableCell) {
+      continue;
+    }
+
+    // Check whether the previous table cell has a cached value.
+    cachedHeader = cache.GetWeak(tableCell, &inCache);
+    if (inCache && cell->Role() != roles::COLUMNHEADER) {
+      if (!cachedHeader || !cachedHeader->IsDefunct()) {
+        // Cache it for this cell.
+        cache.Put(this, RefPtr<Accessible>(cachedHeader));
+        return cachedHeader;
+      }
+    }
 
     // Avoid addding cells multiple times, if this cell spans more rows
     // we'll get it later.
-    if (tableCell->RowIdx() == curRowIdx && cell->Role() == roles::COLUMNHEADER)
-      aCells->AppendElement(cell);
+    if (cell->Role() != roles::COLUMNHEADER ||
+        tableCell->RowIdx() != curRowIdx) {
+      continue;
+    }
+
+    // Cache the header we found.
+    cache.Put(this, RefPtr<Accessible>(cell));
+    return cell;
+  }
+
+  // There's no header, so cache that fact.
+  cache.Put(this, RefPtr<Accessible>(nullptr));
+  return nullptr;
+}
+
+void TableCellAccessible::ColHeaderCells(nsTArray<Accessible*>* aCells) {
+  for (Accessible* cell = PrevColHeader(); cell;
+       cell = cell->AsTableCell()->PrevColHeader()) {
+    aCells->AppendElement(cell);
   }
 }
--- a/accessible/generic/TableCellAccessible.h
+++ b/accessible/generic/TableCellAccessible.h
@@ -55,14 +55,17 @@ class TableCellAccessible {
    * Return the row header cells for this cell.
    */
   virtual void RowHeaderCells(nsTArray<Accessible*>* aCells);
 
   /**
    * Returns true if this cell is selected.
    */
   virtual bool Selected() = 0;
+
+ private:
+  Accessible* PrevColHeader();
 };
 
 }  // namespace a11y
 }  // namespace mozilla
 
 #endif  // mozilla_a11y_TableCellAccessible_h__
--- a/accessible/tests/mochitest/table/a11y.ini
+++ b/accessible/tests/mochitest/table/a11y.ini
@@ -16,8 +16,9 @@ support-files =
 [test_sels_table.html]
 [test_sels_tree.xhtml]
 [test_struct_ariagrid.html]
 [test_struct_ariatreegrid.html]
 [test_struct_table.html]
 [test_struct_tree.xhtml]
 [test_table_1.html]
 [test_table_2.html]
+[test_table_mutation.html]
new file mode 100644
--- /dev/null
+++ b/accessible/tests/mochitest/table/test_table_mutation.html
@@ -0,0 +1,100 @@
+<!DOCTYPE HTML PUBLIC "-//w3c//dtd html 4.0 transitional//en">
+<html>
+<head>
+  <title>Table mutation</title>
+  <meta http-equiv="content-type" content="text/html; charset=UTF-8">
+  <link rel="stylesheet" type="text/css"
+        href="chrome://mochikit/content/tests/SimpleTest/test.css" />
+
+  <script src="chrome://mochikit/content/tests/SimpleTest/SimpleTest.js"></script>
+
+  <script type="application/javascript"
+          src="../common.js"></script>
+  <script type="application/javascript"
+          src="../table.js"></script>
+  <script type="application/javascript"
+          src="../promisified-events.js"></script>
+
+  <script type="application/javascript">
+
+    async function doTest() {
+      let headers = [
+        {
+          cell: "t1r1c1",
+          columnHeaderCells: [],
+          rowHeaderCells: [],
+        },
+        // t1r2 is hidden
+        {
+          cell: "t1r3c1",
+          columnHeaderCells: ["t1r1c1"],
+          rowHeaderCells: [],
+        },
+      ];
+      testHeaderCells(headers);
+
+      info("Remove row");
+      let reordered = waitForEvent(EVENT_REORDER, "t1");
+      getNode("t1r1").hidden = true;
+      await reordered;
+      headers = [
+        // t1r1 and t1r2 are hidden
+        {
+          cell: "t1r3c1",
+          columnHeaderCells: [],
+          rowHeaderCells: [],
+        },
+      ];
+      testHeaderCells(headers);
+
+      info("Add rows");
+      reordered = waitForEvent(EVENT_REORDER, "t1");
+      getNode("t1r1").hidden = false;
+      getNode("t1r2").hidden = false;
+      await reordered;
+      headers = [
+        {
+          cell: "t1r1c1",
+          columnHeaderCells: [],
+          rowHeaderCells: [],
+        },
+        {
+          cell: "t1r2c1",
+          columnHeaderCells: ["t1r1c1"],
+          rowHeaderCells: [],
+        },
+        {
+          cell: "t1r3c1",
+          columnHeaderCells: ["t1r2c1", "t1r1c1"],
+          rowHeaderCells: [],
+        },
+      ];
+      testHeaderCells(headers);
+
+      SimpleTest.finish();
+    }
+
+    SimpleTest.waitForExplicitFinish();
+    addA11yLoadEvent(doTest);
+  </script>
+</head>
+
+<body>
+  <p id="display"></p>
+  <div id="content" style="display: none"></div>
+  <pre id="test">
+  </pre>
+
+  <table id="t1">
+    <tr id="t1r1">
+      <th id="t1r1c1"></th>
+    </tr>
+    <tr id="t1r2" hidden>
+      <th id="t1r2c1"></th>
+    </tr>
+    <tr id="t1r3">
+      <td id="t1r3c1"></td>
+    </tr>
+  </table>
+</body>
+</html>