Adding ChromeVox as a component extensions (enabled only for ChromeOS, for no...

chrome/browser/resources/access_chromevox/common/traverse_table.js

+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+/**
+ * @fileoverview A DOM traversal interface for navigating data in tables.
+ */
+
+goog.provide('cvox.TraverseTable');
+
+goog.require('cvox.SelectionUtil');
+goog.require('cvox.TraverseUtil');
+goog.require('cvox.XpathUtil');
+
+/**
+ * An object that represents an active table cell inside the shadow table.
+ * @constructor
+ */
+function ShadowTableNode() {}
+
+/**
+ * Whether or not the active cell is spanned by a preceding cell.
+ * @type {?boolean}
+ */
+ShadowTableNode.prototype.spanned;
+
+/**
+ * Whether or not this cell is spanned by a rowSpan.
+ * @type {?boolean}
+ */
+ShadowTableNode.prototype.rowSpan;
+
+/**
+ * Whether or not this cell is spanned by a colspan
+ * @type {?boolean}
+ */
+ShadowTableNode.prototype.colSpan;
+
+/**
+ * The row index of the corresponding active table cell
+ * @type {?number}
+ */
+ShadowTableNode.prototype.i;
+
+/**
+ * The column index of the corresponding active table cell
+ * @type {?number}
+ */
+ShadowTableNode.prototype.j;
+
+/**
+ * The corresponding <TD> or <TH> node in the active table.
+ * @type {?Node}
+ */
+ShadowTableNode.prototype.activeCell;
+
+/**
+ * Initializes the traversal with the provided table node.
+ *
+ * @constructor
+ * @param {Node} tableNode The table to be traversed.
+ */
+cvox.TraverseTable = function(tableNode) {
+
+  /**
+   * The active table <TABLE> node. In this context, "active" means that this is
+   * the table the TraverseTable object is navigating.
+   * @type {Node}
+   * @private
+   */
+  this.activeTable_ = [];
+
+  /**
+   * A 2D array "shadow table" that contains pointers to nodes in the active
+   * table. More specifically, each cell of the shadow table contains a special
+   * object ShadowTableNode that has as one of its member variables the
+   * corresponding cell in the active table.
+   *
+   * The shadow table will allow us efficient navigation of tables with
+   * rowspans and colspans without needing to repeatedly scan the table. For
+   * example, if someone requests a cell at (1,3), predecessor cells with
+   * rowspans/colspans mean the cell you eventually return could actually be
+   * one located at (0,2) that spans out to (1,3).
+   *
+   * This shadow table will contain a ShadowTableNode with the (0, 2) index at
+   * the (1,3) position, eliminating the need to check for predecessor cells
+   * with rowspan/colspan every time we traverse the table.
+   *
+   * @type {Array.<Array.<ShadowTableNode>>}
+   * @private
+   */
+  this.shadowTable_ = [];
+
+  this.initialize(tableNode);
+};
+
+
+/**
+ * The active row <TR> node. In this context, "active" means that this is the
+ * row that contains the cell the user is currently looking at.
+ * @type {Node}
+ */
+cvox.TraverseTable.prototype.currentRow;
+
+
+/**
+ * The active column, represented as an array of <TH> or <TD> nodes that make
+ * up a column. In this context, "active" means that this is the column that
+ * contains the cell the user is currently looking at.
+ * @type {Array}
+ */
+cvox.TraverseTable.prototype.currentCol;
+
+
+/**
+ * The cell cursor, represented by an array that stores the row and
+ * column location [i, j] of the active cell. These numbers are 0-based.
+ * In this context, "active" means that this is the cell the user is
+ * currently looking at.
+ * @type {Array}
+ */
+cvox.TraverseTable.prototype.currentCellCursor;
+
+
+/**
+ * The number of columns in the active table. This is calculated at
+ * initialization and then only recalculated if the table changes.
+ *
+ * Please Note: We have chosen to use the number of columns in the shadow
+ * table as the canonical column count. This is important for tables that
+ * have colspans - the number of columns in the active table will always be
+ * less than the true number of columns.
+ * @type {?number}
+ */
+cvox.TraverseTable.prototype.colCount = null;
+
+/**
+ * The number of rows in the active table. This is calculated at
+ * initialization and then only recalculated if the table changes.
+ * @type {?number}
+ */
+cvox.TraverseTable.prototype.rowCount = null;
+
+
+/**
+ * Initializes the class member variables.
+ * @param {Node} tableNode The table to be traversed.
+ */
+cvox.TraverseTable.prototype.initialize = function(tableNode) {
+  this.activeTable_ = tableNode;
+  this.currentRow = null;
+  this.currentCol = null;
+  this.currentCellCursor = null;
+
+  this.buildShadowTable_();
+
+  this.colCount = this.shadowColCount_();
+  this.rowCount = this.countRows_();
+
+  var self = this;
+  // Listen for changes to the active table. If the active table changes,
+  // rebuild the shadow table.
+  this.activeTable_.addEventListener('DOMSubtreeModified',
+      function() {
+        self.buildShadowTable_();
+        self.colCount = self.shadowColCount_();
+        self.rowCount = self.countRows_();
+      }, false);
+};
+
+/**
+ * Builds or rebuilds the shadow table by iterating through all of the cells
+ * ( <TD> or <TH> nodes) of the active table.
+ * @private
+ */
+cvox.TraverseTable.prototype.buildShadowTable_ = function() {
+  // Clear shadow table
+  this.shadowTable_ = [];
+
+  // Build shadow table structure. Initialize it as a 2D array.
+  var allRows = this.getChildRows_();
+  for (var ctr = 0; ctr < allRows.length; ctr++) {
+    this.shadowTable_.push([]);
+  }
+
+  // Iterate through active table by row
+  for (var i = 0; i < allRows.length; i++) {
+    var childCells = this.getChildCells_(allRows[i]);
+
+    // Keep track of position in active table
+    var activeTableCol = 0;
+    // Keep track of position in shadow table
+    var shadowTableCol = 0;
+
+    while (activeTableCol < childCells.length) {
+
+      // Check to make sure we haven't already filled this cell.
+      if (this.shadowTable_[i][shadowTableCol] == null) {
+
+        // Default value for colspan and rowspan is 1
+        var colsSpanned = 1;
+        var rowsSpanned = 1;
+
+        if (childCells[activeTableCol].hasAttribute('colspan')) {
+
+          colsSpanned =
+              parseInt(childCells[activeTableCol].getAttribute('colspan'));
+
+          if ((isNaN(colsSpanned)) || (colsSpanned <= 0)) {
+            // The HTML5 spec defines colspan MUST be greater than 0:
+            // http://dev.w3.org/html5/spec/Overview.html#attr-tdth-colspan
+            //
+            // This is a change from the HTML4 spec:
+            // http://www.w3.org/TR/html401/struct/tables.html#adef-colspan
+            //
+            // We will degrade gracefully by treating a colspan=0 as
+            // equivalent to a colspan=1.
+            // Tested in method testColSpan0 in rowColSpanTable_test.js
+            colsSpanned = 1;
+          }
+        }
+        if (childCells[activeTableCol].hasAttribute('rowspan')) {
+          rowsSpanned =
+              parseInt(childCells[activeTableCol].getAttribute('rowspan'));
+
+          if ((isNaN(rowsSpanned)) || (rowsSpanned <= 0)) {
+            // The HTML5 spec defines that rowspan can be any non-negative
+            // integer, including 0:
+            // http://dev.w3.org/html5/spec/Overview.html#attr-tdth-rowspan
+            //
+            // However, Chromium treats rowspan=0 as rowspan=1. This appears
+            // to be a bug from WebKit:
+            // https://bugs.webkit.org/show_bug.cgi?id=10300
+            // Inherited from a bug (since fixed) in KDE:
+            // http://bugs.kde.org/show_bug.cgi?id=41063
+            //
+            // We will follow Chromium and treat rowspan=0 as equivalent to
+            // rowspan=1.
+            //
+            // Tested in method testRowSpan0 in rowColSpanTable_test.js
+            //
+            // Filed as a bug in Chromium: http://crbug.com/58223
+            rowsSpanned = 1;
+          }
+        }
+        for (var r = 0; r < rowsSpanned; r++) {
+          for (var c = 0; c < colsSpanned; c++) {
+            var shadowNode = new ShadowTableNode();
+            if ((r == 0) && (c == 0)) {
+              // This position is not spanned.
+              shadowNode.spanned = false;
+              shadowNode.rowSpan = false;
+              shadowNode.colSpan = false;
+              shadowNode.i = i;
+              shadowNode.j = shadowTableCol;
+              shadowNode.activeCell = childCells[activeTableCol];
+            } else {
+              // This position is spanned.
+              shadowNode.spanned = true;
+              shadowNode.rowSpan = (rowsSpanned > 1);
+              shadowNode.colSpan = (colsSpanned > 1);
+              shadowNode.i = i;
+              shadowNode.j = shadowTableCol;
+              shadowNode.activeCell = childCells[activeTableCol];
+            }
+            this.shadowTable_[i + r][shadowTableCol + c] = shadowNode;
+          }
+        }
+        shadowTableCol += colsSpanned;
+        activeTableCol++;
+      } else {
+        // This position has already been filled (by a previous cell that has
+        // a colspan or a rowspan)
+        shadowTableCol += 1;
+      }
+    }
+  }
+};
+
+
+/**
+ * Gets the current cell.
+ * @return {?Node} The cell <TD> or <TH> node.
+ */
+cvox.TraverseTable.prototype.getCell = function() {
+  var shadowEntry =
+      this.shadowTable_[this.currentCellCursor[0]][this.currentCellCursor[1]];
+
+  return shadowEntry.activeCell;
+};
+
+
+/**
+ * Gets the table summary text.
+ *
+ * @return {?string} Either:
+ *     1) The table summary text
+ *     2) Null if the table does not contain a summary attribute.
+ */
+cvox.TraverseTable.prototype.summaryText = function() {
+  // see http://code.google.com/p/chromium/issues/detail?id=46567
+  // for information why this is necessary
+  if (!this.activeTable_.hasAttribute('summary')) {
+    return null;
+  }
+  return this.activeTable_.getAttribute('summary');
+};
+
+
+/**
+ * Gets the table caption text.
+ *
+ * @return {?string} Either:
+ *     1) The table caption text
+ *     2) Null if the table does not include a caption tag.
+ */
+cvox.TraverseTable.prototype.captionText = function() {
+  // If there's more than one outer <caption> element, choose the first one.
+  var captionNodes = cvox.XpathUtil.evalXPath('caption\[1]',
+                                         this.activeTable_);
+  if (captionNodes.length > 0) {
+    return captionNodes[0].innerHTML;
+  } else {
+    return null;
+  }
+};
+
+
+/**
+ * Calculates the number of columns in the shadow table.
+ * @return {number} The number of columns in the shadow table.
+ * @private
+ */
+cvox.TraverseTable.prototype.shadowColCount_ = function() {
+  // As the shadow table is a 2D array, the number of columns is the
+  // max number of elements in the second-level arrays.
+  var max = 0;
+  for (var i = 0; i < this.shadowTable_.length; i++) {
+    if (this.shadowTable_[i].length > max) {
+      max = this.shadowTable_[i].length;
+    }
+  }
+  return max;
+};
+
+
+/**
+ * Calculates the number of rows in the table.
+ * @return {number} The number of rows in the table.
+ * @private
+ */
+cvox.TraverseTable.prototype.countRows_ = function() {
+  // Number of rows in a table is equal to the number of TR elements contained
+  // by the (outer) TBODY elements.
+  var rowCount = this.getChildRows_();
+  return rowCount.length;
+};
+
+
+/**
+ * Calculates the number of columns in the table.
+ * This uses the W3C recommended algorithm for calculating number of
+ * columns, but it does not take rowspans or colspans into account. This means
+ * that the number of columns calculated here might be lower than the actual
+ * number of columns in the table if columns are indicated by colspans.
+ * @return {number} The number of columns in the table.
+ * @private
+ */
+cvox.TraverseTable.prototype.getW3CColumnCount_ = function() {
+  // See http://www.w3.org/TR/html401/struct/tables.html#h-11.2.4.3
+
+  var colgroupNodes = cvox.XpathUtil.evalXPath('child::colgroup',
+                                          this.activeTable_);
+  var colNodes = cvox.XpathUtil.evalXPath('child::col', this.activeTable_);
+
+  if ((colgroupNodes.length == 0) && (colNodes.length == 0)) {
+    var maxcols = 0;
+    var outerChildren = this.getChildRows_();
+    for (var i = 0; i < outerChildren.length; i++) {
+      var childrenCount = this.getChildCells_(outerChildren[i]);
+      if (childrenCount.length > maxcols) {
+        maxcols = childrenCount.length;
+      }
+    }
+    return maxcols;
+  } else {
+    var sum = 0;
+    for (var i = 0; i < colNodes.length; i++) {
+      if (colNodes[i].hasAttribute('span')) {
+        sum += colNodes[i].getAttribute('span');
+      } else {
+        sum += 1;
+      }
+    }
+    for (i = 0; i < colgroupNodes.length; i++) {
+      var colChildren = cvox.XpathUtil.evalXPath('child::col',
+          colgroupNodes[i]);
+      if (colChildren.length == 0) {
+        if (colgroupNodes[i].hasAttribute('span')) {
+          sum += colgroupNodes[i].getAttribute('span');
+        } else {
+          sum += 1;
+        }
+      }
+    }
+  }
+  return sum;
+};
+
+
+/**
+ * Moves to the next row in the table. Updates the cell cursor.
+ *
+ * @return {boolean} Either:
+ *    1) True if the update has been made.
+ *    2) False if the end of the table has been reached and the update has not
+ *       happened.
+  */
+cvox.TraverseTable.prototype.nextRow = function() {
+  if (!this.currentCellCursor) {
+    // We have not started moving through the table yet
+    return this.goToRow(0);
+  } else {
+    return this.goToRow(this.currentCellCursor[0] + 1);
+  }
+
+};
+
+
+/**
+ * Moves to the previous row in the table. Updates the cell cursor.
+ *
+ * @return {boolean} Either:
+ *    1) True if the update has been made.
+ *    2) False if the end of the table has been reached and the update has not
+ *       happened.
+ */
+cvox.TraverseTable.prototype.prevRow = function() {
+  if (!this.currentCellCursor) {
+    // We have not started moving through the table yet
+    return this.goToRow(this.rowCount - 1);
+  } else {
+    return this.goToRow(this.currentCellCursor[0] - 1);
+  }
+};
+
+
+/**
+ * Moves to the next column in the table. Updates the cell cursor.
+ *
+ * @return {boolean} Either:
+ *    1) True if the update has been made.
+ *    2) False if the end of the table has been reached and the update has not
+ *       happened.
+ */
+cvox.TraverseTable.prototype.nextCol = function() {
+  if (!this.currentCellCursor) {
+    // We have not started moving through the table yet
+    return this.goToCol(0);
+  } else {
+    return this.goToCol(this.currentCellCursor[1] + 1);
+  }
+};
+
+
+/**
+ * Moves to the previous column in the table. Updates the cell cursor.
+ *
+ * @return {boolean} Either:
+ *    1) True if the update has been made.
+ *    2) False if the end of the table has been reached and the update has not
+ *       happened.
+ */
+cvox.TraverseTable.prototype.prevCol = function() {
+  if (!this.currentCellCursor) {
+    // We have not started moving through the table yet
+    return this.goToCol(this.shadowColCount_() - 1);
+  } else {
+    return this.goToCol(this.currentCellCursor[1] - 1);
+  }
+};
+
+
+/**
+ * Moves to the row at the specified index in the table. Updates the cell
+ * cursor.
+ * @param {number} index The index of the required row.
+ * @return {boolean} Either:
+ *    1) True if the index is valid and the update has been made.
+ *    2) False if the index is not valid (either less than 0 or greater than
+ *       the number of rows in the table).
+ */
+cvox.TraverseTable.prototype.goToRow = function(index) {
+  var childRows = this.getChildRows_();
+  if ((index < this.shadowTable_.length) &&
+      (index < childRows.length) && (index >= 0)) {
+    this.currentRow = childRows[index];
+    if (this.currentCellCursor == null) {
+      // We haven't started moving through the table yet
+      this.currentCellCursor = [index, 0];
+    } else {
+      this.currentCellCursor = [index, this.currentCellCursor[1]];
+    }
+    return true;
+  } else {
+    return false;
+  }
+};
+
+
+/**
+ * Moves to the column at the specified index in the table. Updates the cell
+ * cursor.
+ * @param {number} index The index of the required column.
+ * @return {boolean} Either:
+ *    1) True if the index is valid and the update has been made.
+ *    2) False if the index is not valid (either less than 0 or greater than
+ *       the number of rows in the table).
+ */
+cvox.TraverseTable.prototype.goToCol = function(index) {
+  if (index < 0 || index >= this.colCount) {
+    return false;
+  }
+
+  var colArray = [];
+  for (var i = 0; i < this.shadowTable_.length; i++) {
+
+    if (this.shadowTable_[i][index]) {
+      var shadowEntry = this.shadowTable_[i][index];
+
+      if (shadowEntry.colSpan && shadowEntry.rowSpan) {
+        // Look at the last element in the column cell aray.
+        var prev = colArray[colArray.length - 1];
+        if (prev !=
+            shadowEntry.activeCell) {
+          // Watch out for positions spanned by a cell with rowspan and
+          // colspan. We don't want the same cell showing up multiple times
+          // in per-column cell lists.
+          colArray.push(
+              shadowEntry.activeCell);
+        }
+      } else if ((shadowEntry.colSpan) || (!shadowEntry.rowSpan)) {
+        colArray.push(
+            shadowEntry.activeCell);
+      }
+    }
+  }
+  this.currentCol = colArray;
+  if (this.currentCellCursor == null) {
+    // We haven't started moving through the table yet
+    this.currentCellCursor = [0, index];
+  } else {
+    this.currentCellCursor = [this.currentCellCursor[0], index];
+  }
+  return true;
+};
+
+
+/**
+ * Moves to the cell at the specified index <i, j> in the table. Updates the
+ * cell cursor.
+ * @param {Array.<number>} index The index <i, j> of the required cell.
+ * @return {boolean} Either:
+ *    1) True if the index is valid and the update has been made.
+ *    2) False if the index is not valid (either less than 0, greater than
+ *       the number of rows or columns in the table, or there is no cell
+ *       at that location).
+ */
+cvox.TraverseTable.prototype.goToCell = function(index) {
+  var prevIndex = this.currentCellCursor;
+  if (!this.goToRow(index[0])) {
+    return false;
+  }
+  if (!this.goToCol(index[1])) {
+    this.goToRow(prevIndex[0]);
+    return false;
+  } else {
+    // The row and column exist, but the cell may still not if we're dealing
+    // with a partial column.
+    var cell =
+        this.shadowTable_[this.currentCellCursor[0]][this.currentCellCursor[1]];
+    if (cell) {
+      return true;
+    } else {
+      this.goToRow(prevIndex[0]);
+      this.goToCol(prevIndex[1]);
+      return false;
+    }
+  }
+};
+
+
+/**
+ * Resets the table cursors.
+ *
+ */
+cvox.TraverseTable.prototype.resetCursor = function() {
+  this.currentRow = null;
+  this.currentCellCursor = null;
+  this.currentCol = null;
+};
+
+
+/**
+ * Returns a JavaScript array of all the non-nested rows in the active table.
+ *
+ * @return {Array} An array of all the child rows of the active table.
+ * @private
+ */
+cvox.TraverseTable.prototype.getChildRows_ = function() {
+  return cvox.XpathUtil.evalXPath('child::tbody/tr', this.activeTable_);
+};
+
+
+/**
+ * Returns a JavaScript array of all the child cell <TD> or <TH> nodes of
+ * the given row.
+ *
+ * @param {Node} rowNode The specified row node.
+ * @return {Array} An array of all the child cells of the given row node.
+ * @private
+ */
+cvox.TraverseTable.prototype.getChildCells_ = function(rowNode) {
+  return cvox.XpathUtil.evalXPath('child::td | child::th', rowNode);
+};