chrome/browser/resources/chromeos/accessibility/select_to_speak/node_utils.js

// Copyright 2018 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.

import {AutomationPredicate} from '../common/automation_predicate.js';
import {AutomationUtil} from '../common/automation_util.js';
import {RectUtil} from '../common/rect_util.js';

import {ParagraphUtils} from './paragraph_utils.js';

const AutomationNode = chrome.automation.AutomationNode;
const RoleType = chrome.automation.RoleType;

// Utilities for automation nodes in Select-to-Speak.

export class NodeUtils {
  constructor() {}

  /**
   * Gets the current visibility state for a given node.
   *
   * @param {AutomationNode} node The starting node.
   * @return {NodeUtils.NodeState} the current node state.
   */
  static getNodeState(node) {
    if (node === undefined || node.root === null || node.root === undefined) {
      // The node has been removed from the tree, perhaps because the
      // window was closed.
      return NodeUtils.NodeState.NODE_STATE_INVALID;
    }
    // This might not be populated correctly on children nodes even if their
    // parents or roots are now invisible.
    // TODO: Update the C++ bindings to set 'invisible' automatically based
    // on parents, rather than going through parents in JS below.
    if (node.state.invisible) {
      return NodeUtils.NodeState.NODE_STATE_INVISIBLE;
    }
    // Walk up the tree to make sure the window it is in is not invisible.
    const window = NodeUtils.getNearestContainingWindow(node);
    if (window != null && window.state[chrome.automation.StateType.INVISIBLE]) {
      return NodeUtils.NodeState.NODE_STATE_INVISIBLE;
    }
    // TODO: Also need a check for whether the window is minimized,
    // which would also return NodeState.NODE_STATE_INVISIBLE.
    return NodeUtils.NodeState.NODE_STATE_NORMAL;
  }

  /**
   * Returns true if a node should be ignored by Select-to-Speak, or if it
   * is of interest. This does not deal with whether nodes have children --
   * nodes are interesting if they have a name or a value and have an onscreen
   * location.
   * @param {!AutomationNode} node The node to test
   * @param {boolean} includeOffscreen Whether to include offscreen nodes.
   * @return {boolean} whether this node should be ignored.
   */
  static shouldIgnoreNode(node, includeOffscreen) {
    if (NodeUtils.isNodeInvisible(node, includeOffscreen)) {
      return true;
    }
    return ParagraphUtils.isWhitespace(ParagraphUtils.getNodeName(node));
  }

  /**
   * Returns true if the node should be ignored by Select-to-Speak because
   * it was marked with user-select:none. For Inline Text elements, the
   * parent is marked with this attribute, hence the check.
   *
   * @param {!AutomationNode} node The node to test
   * @return {boolean} whether this node was marked user-select:none
   */
  static isNotSelectable(node) {
    return Boolean(
        node &&
        (node.notUserSelectableStyle ||
         (node.parent && node.parent.notUserSelectableStyle)));
  }

  /**
   * Returns true if a node is invisible for any reason.
   * @param {!AutomationNode} node The node to test
   * @param {boolean} includeOffscreen Whether to include offscreen nodes
   *     as visible type nodes.
   * @return {boolean} whether this node is invisible.
   */
  static isNodeInvisible(node, includeOffscreen) {
    return !node.location || node.state.invisible ||
        (node.state.offscreen && !includeOffscreen);
  }

  /**
   * Gets the first window containing this node.
   * @param {AutomationNode} node The node to find a window for.
   * @return {AutomationNode|undefined} The node representing the nearest
   *     containing window.
   */
  static getNearestContainingWindow(node) {
    // Go upwards to root nodes' parents until we find the first window.
    if (node.root && node.root.role === RoleType.ROOT_WEB_AREA) {
      let nextRootParent = node;
      while (nextRootParent != null &&
             nextRootParent.role !== RoleType.WINDOW &&
             nextRootParent.root != null &&
             nextRootParent.root.role === RoleType.ROOT_WEB_AREA) {
        nextRootParent = nextRootParent.root.parent;
      }
      return nextRootParent;
    }
    // If the parent isn't a root web area, just walk up the tree to find the
    // nearest window.
    let parent = node;
    while (parent != null &&
           parent.role !== chrome.automation.RoleType.WINDOW) {
      parent = parent.parent;
    }
    return parent;
  }

  /**
   * Gets the length of a node's name. Returns 0 if the name is
   * undefined.
   * @param {AutomationNode} node The node for which to check the name.
   * @return {number} The length of the node's name
   */
  static nameLength(node) {
    return node.name ? node.name.length : 0;
  }

  /**
   * Returns true if a node is a text field type, but not for any other type,
   * including contentEditables.
   * @param {!AutomationNode} node The node to check
   * @return {boolean} True if the node is a text field type.
   */
  static isTextField(node) {
    return node.role === RoleType.TEXT_FIELD ||
        node.role === RoleType.TEXT_FIELD_WITH_COMBO_BOX;
  }

  /**
   * Gets the first (left-most) leaf node of a node. Returns undefined if
   *  none is found.
   * @param {AutomationNode} node The node to search for the first leaf.
   * @return {AutomationNode|undefined} The leaf node.
   */
  static getFirstLeafChild(node) {
    let result = node.firstChild;
    while (result && result.firstChild) {
      result = result.firstChild;
    }
    return result;
  }

  /**
   * Gets the first (left-most) leaf node of a node. Returns undefined
   * if none is found.
   * @param {AutomationNode} node The node to search for the first leaf.
   * @return {AutomationNode|undefined} The leaf node.
   */
  static getLastLeafChild(node) {
    let result = node.lastChild;
    while (result && result.lastChild) {
      result = result.lastChild;
    }
    return result;
  }

  /**
   * Finds all nodes within the subtree rooted at |node| that overlap
   * a given rectangle.
   * @param {!AutomationNode} node The starting node.
   * @param {{left: number, top: number, width: number, height: number}} rect
   *     The bounding box to search.
   * @param {Array<AutomationNode>} nodes The matching node array to be
   *     populated.
   * @return {boolean} True if any matches are found.
   */
  static findAllMatching(node, rect, nodes) {
    var found = false;
    for (var c = node.firstChild; c; c = c.nextSibling) {
      if (NodeUtils.findAllMatching(c, rect, nodes)) {
        found = true;
      }
    }

    if (found) {
      return true;
    }

    // Closure needs node.location check here to allow the next few
    // lines to compile.
    if (NodeUtils.shouldIgnoreNode(node, /* don't include offscreen */ false) ||
        node.location === undefined) {
      return false;
    }

    if (RectUtil.overlaps(node.location, rect)) {
      if (!node.children || node.children.length === 0 ||
          node.children[0].role !== RoleType.INLINE_TEXT_BOX) {
        // Only add a node if it has no inlineTextBox children. If
        // it has text children, they will be more precisely bounded
        // and specific, so no need to add the parent node.
        nodes.push(node);
        return true;
      }
    }

    return false;
  }

  /**
   * Finds the deep equivalent node where a selection starts given a node
   * object and selection offset. This is meant to be used in conjunction with
   * the selectionStartObject/selectionStartOffset and
   * selectionEndObject/selectionEndOffset of the automation API.
   * @param {!AutomationNode} parent The parent node of the selection,
   * similar to chrome.automation.selectionStartObject or selectionEndObject.
   * @param {number} offset The integer offset of the selection. This is
   * similar to chrome.automation.selectionStartOffset or selectionEndOffset.
   * @param {boolean} isStart whether this is the start or end of a selection.
   * @return {!NodeUtils.Position} The node matching the selected offset.
   */
  static getDeepEquivalentForSelection(parent, offset, isStart) {
    const automationPosition = parent.createPosition(offset);
    if (!automationPosition.node) {
      // TODO(accessibility): Bugs in AXPosition cause this; for example, a
      // selection on a text field.
      return this.getDeepEquivalentForSelectionDeprecated(
          parent, offset, isStart);
    }

    automationPosition.asLeafTextPosition();

    if (!automationPosition.node ||
        automationPosition.node.role === RoleType.IMAGE) {
      // TODO(accessibility): Bugs in AXPosition cause this; for example, a
      // selection on a image has incorrect text offsets.
      return this.getDeepEquivalentForSelectionDeprecated(
          parent, offset, isStart);
    }

    return {
      node: automationPosition.node,
      offset: automationPosition.textOffset,
    };
  }

  /**
   * TODO(accessibility): remove once AXPosition bugs are fixed; see above.
   * @param {!AutomationNode} parent The parent node of the selection,
   * similar to chrome.automation.selectionStartObject or selectionEndObject.
   * @param {number} offset The integer offset of the selection. This is
   * similar to chrome.automation.selectionStartOffset or selectionEndOffset.
   * @param {boolean} isStart whether this is the start or end of a selection.
   * @return {!NodeUtils.Position} The node matching the selected offset.
   */
  static getDeepEquivalentForSelectionDeprecated(parent, offset, isStart) {
    if (parent.children.length === 0) {
      return {node: parent, offset};
    }

    // Non-text nodes with children.
    if (parent.role !== RoleType.STATIC_TEXT &&
        parent.role !== RoleType.INLINE_TEXT_BOX &&
        parent.children.length > 0 && !NodeUtils.isTextField(parent)) {
      const index = isStart ? offset : offset - 1;
      if (parent.children.length > index && index >= 0) {
        let child = parent.children[index];
        if (child.children.length > 0) {
          child = isStart ? NodeUtils.getFirstLeafChild(child) :
                            NodeUtils.getLastLeafChild(child);
        }
        return {
          node: /** @type {!AutomationNode} */ (child),
          offset: isStart ?
              0 :
              NodeUtils.nameLength(/** @type {!AutomationNode} */ (child)),
        };
      } else if (isStart && !NodeUtils.isTextField(parent)) {
        // We are off the edge of this parent. Go to the next leaf node that is
        // not an ancestor of the parent.
        const lastChild = NodeUtils.getLastLeafChild(parent);
        if (lastChild) {
          const nextNode = AutomationUtil.findNextNode(
              lastChild, constants.Dir.FORWARD, AutomationPredicate.leaf);
          if (nextNode) {
            return {node: nextNode, offset: 0};
          }
        }
      } else if (index < 0) {
        // Otherwise we are before the beginning of this parent. Find the
        // previous leaf node and use that.
        const previousNode = AutomationUtil.findNextNode(
            parent, constants.Dir.BACKWARD, AutomationPredicate.leaf);
        if (previousNode) {
          return {
            node: previousNode,
            offset: NodeUtils.nameLength(previousNode),
          };
        }
      }
    }

    // If this is a node without children or a text node, create a stack of
    // nodes to search through.
    // TODO(katie): Since we only have non-text nodes or nodes without children,
    // can this be simplified?
    let nodesToCheck;
    if (NodeUtils.isTextField(parent) && parent.firstChild &&
        parent.firstChild.firstChild) {
      // Skip ahead.
      nodesToCheck = parent.firstChild.children.slice().reverse();
    } else {
      nodesToCheck = parent.children.slice().reverse();
    }
    let index = 0;
    var node = parent;
    // Delve down into the children recursively to find the
    // one at this offset.
    while (nodesToCheck.length > 0) {
      node = nodesToCheck.pop();
      if (node.state.invisible) {
        continue;
      }
      if (node.children.length > 0) {
        if (node.role !== RoleType.STATIC_TEXT) {
          index += 1;
        } else {
          nodesToCheck = nodesToCheck.concat(node.children.slice().reverse());
        }
      } else {
        if (node.parent.role === RoleType.STATIC_TEXT ||
            node.parent.role === RoleType.INLINE_TEXT_BOX) {
          // How many characters are in the name.
          index += NodeUtils.nameLength(node);
        } else {
          // Add one for itself only.
          index += 1;
        }
      }
      // Check if we've indexed far enough into the nodes of this parent to be
      // past the offset if |isStart|, or at the offset if !|isStart|.
      if (((isStart && index > offset) || (!isStart && index >= offset))) {
        // If the node is a text field type with children, return its first
        // (or last if !|isStart|) leaf child. Otherwise, just return the node
        // and its offset. textField nodes are indexed differently in selection
        // from others -- it seems as though the whole node counts only once in
        // the selection index if the textField is entirely selected, whereas a
        // normal staticText will count for itself plus one. This is probably
        // because textFields cannot be partially selected if other elements
        // outside of themselves are selected.
        if (NodeUtils.isTextField(node)) {
          const leafNode = isStart ? NodeUtils.getFirstLeafChild(node) :
                                     NodeUtils.getLastLeafChild(node);
          if (leafNode) {
            return {
              node: leafNode,
              offset: isStart ? 0 : NodeUtils.nameLength(leafNode),
            };
          }
        }
        const result = offset - index + NodeUtils.nameLength(node);
        return {node, offset: result > 0 ? result : 0};
      }
    }
    // We are at the end of the last node.
    // If it's a textField we skipped, go ahead and find the first (or last, if
    // !|isStart|) child, otherwise just return this node itself.
    if (NodeUtils.isTextField(node)) {
      const leafNode = isStart ? NodeUtils.getFirstLeafChild(node) :
                                 NodeUtils.getLastLeafChild(node);
      if (leafNode) {
        return {
          node: leafNode,
          offset: isStart ? 0 : NodeUtils.nameLength(leafNode),
        };
      }
    }
    return {node, offset: NodeUtils.nameLength(node)};
  }

  /**
   * Sorts given nodes by visual reading order. Expects nodes to be leaf nodes
   * with text.
   * @param {!Array<!AutomationNode>} nodes
   */
  static sortNodesByReadingOrder(nodes) {
    // Pre-compute ancestors for each node.
    const nodeAncestorMap = new Map();
    for (const node of nodes) {
      nodeAncestorMap.set(node, AutomationUtil.getAncestors(node));
    }

    // Sort nodes by bounds of their divergent ancestors. This will ensure all
    // nodes with the same parent are grouped together.
    nodes.sort((a, b) => {
      const ancestorsA = nodeAncestorMap.get(a);
      const ancestorsB = nodeAncestorMap.get(b);
      const divergence = AutomationUtil.getDivergence(ancestorsA, ancestorsB);
      if (divergence === -1 || divergence >= ancestorsA.length ||
          divergence >= ancestorsB.length) {
        // Nodes do not have any ancestors in common (different trees) or one
        // node is the ancestor of another.
        console.warn(
            'Nodes are directly related or have no common ancestors', a, b);
        return 0;
      }
      const divA = ancestorsA[divergence];
      const divB = ancestorsB[divergence];

      if (RectUtil.sameRow(divA.unclippedLocation, divB.unclippedLocation)) {
        // Nodes are on the same line, sort by LTR reading order.
        // TODO(joelriley@google.com): Handle RTL.
        if (divA.unclippedLocation.left < divB.unclippedLocation.left) {
          return -1;
        }
        if (divB.unclippedLocation.left < divA.unclippedLocation.left) {
          return 1;
        }
        return 0;
      }
      // Nodes are on different lines, sort top-to-bottom.
      if (divA.unclippedLocation.top < divB.unclippedLocation.top) {
        return -1;
      }
      if (divB.unclippedLocation.top < divA.unclippedLocation.top) {
        return 1;
      }
      return 0;
    });
  }

  /**
   * Sorts a specific range of a given array of nodes by visual reading order.
   * Expects nodes to be leaf nodes with text.
   * @param {!Array<!AutomationNode>} nodes
   * @param {number} startIndex Index specifying start of range.
   * @param {number} endIndex  Index specifying end of range, non-inclusive.
   */
  static sortNodeRangeByReadingOrder(nodes, startIndex, endIndex) {
    const nodesToSort = nodes.slice(startIndex, endIndex);
    NodeUtils.sortNodesByReadingOrder(nodesToSort);
    nodes.splice(startIndex, endIndex - startIndex, ...nodesToSort);
  }

  /**
   * Sorts SVG nodes with the same SVG root parent by visual reading order.
   * @param {!Array<!AutomationNode>} nodes
   */
  static sortSvgNodesByReadingOrder(nodes) {
    let lastSvgRoot = null;
    let startIndex = 0;
    for (let i = 0; i < nodes.length; i++) {
      const node = nodes[i];
      const svgRoot =
          AutomationUtil.getFirstAncestorWithRole(node, RoleType.SVG_ROOT);
      if (svgRoot !== lastSvgRoot) {
        if (lastSvgRoot !== null) {
          NodeUtils.sortNodeRangeByReadingOrder(nodes, startIndex, i);
        } else if (svgRoot !== null) {
          startIndex = i;
        }
        lastSvgRoot = svgRoot;
      }
    }
    if (lastSvgRoot !== null) {
      NodeUtils.sortNodeRangeByReadingOrder(nodes, startIndex, nodes.length);
    }
  }

  /**
   * @param {!AutomationNode} node Leaf node.
   * @return {!Array<!AutomationNode>} All selectable leaf nodes in the
   *     paragraph that the given leaf node belongs to. If the node does
   *     not belong to a paragraph, then just the node itself is returned.
   */
  static getAllNodesInParagraph(node) {
    const blockParent = ParagraphUtils.getFirstBlockAncestor(node);
    if (blockParent === null || blockParent === node.root) {
      return [node];
    }
    return AutomationUtil.findAllNodes(
        blockParent, constants.Dir.FORWARD,
        /* pred= */ NodeUtils.isValidLeafNode, /* opt_restrictions= */ {
          root: node => node === blockParent,  // Only traverse within the block
        });
  }

  /**
   * Gets the |NodeUtils.Position| identified by the |charIndex| to the text of
   * |nodeGroup|. If |fallbackToEnd| is true, when the |charIndex| is undefined
   * or out of the text of |nodeGroup|, we will return the end of the
   * |nodeGroup|. Otherwise, we fallback to the start of the |nodeGroup|.
   * @param {!ParagraphUtils.NodeGroup} nodeGroup
   * @param {number|undefined} charIndex
   * @param {boolean} fallbackToEnd
   * @return {!NodeUtils.Position}
   */
  static getPositionFromNodeGroup(nodeGroup, charIndex, fallbackToEnd) {
    let node;
    let offset;
    if (charIndex !== undefined) {
      ({node, offset} = ParagraphUtils.findNodeFromNodeGroupByCharIndex(
           nodeGroup, charIndex));
    }
    if (node && offset !== undefined) {
      return {node, offset};
    }

    // |charIndex| is undefined or out of the text of |nodeGroup|, fallback to
    // the end or the start of the |nodeGroup|.
    if (fallbackToEnd) {
      const lastNode = nodeGroup.nodes[nodeGroup.nodes.length - 1].node;
      const lastChildOfLastNode = NodeUtils.getLastLeafChild(lastNode);
      node = lastChildOfLastNode || lastNode;
      offset = ParagraphUtils.getNodeName(node).length;
    } else {
      const firstNode = nodeGroup.nodes[0].node;
      const firstChildOfFirstNode = NodeUtils.getFirstLeafChild(firstNode);
      node = firstChildOfFirstNode || firstNode;
      offset = 0;
    }
    return {node, offset};
  }

  /**
   * @param {!AutomationNode} node
   * @return {boolean} Whether the given node is a valid leaf node that is can
   *     be ingested by Select-to-speak.
   */
  static isValidLeafNode(node) {
    return AutomationPredicate.leafWithText(node) &&
        !NodeUtils.shouldIgnoreNode(node, /* includeOffscreen= */ true) &&
        !NodeUtils.isNotSelectable(node);
  }

  /**
   * @param {!NodeUtils.Position} startPosition
   * @param {!NodeUtils.Position} endPosition
   * @return {constants.Dir} the direction from the |startPosition| to the
   *     |endPosition|. If the input positions are equal, we view the
   *     |endPosition| is to the |constants.Dir.BACKWARD| of the
   *     |startPosition|.
   */
  static getDirectionBetweenPositions(startPosition, endPosition) {
    const startNode = startPosition.node;
    const startOffset = startPosition.offset;
    const endNode = endPosition.node;
    const endOffset = endPosition.offset;
    if (startNode !== endNode) {
      return AutomationUtil.getDirection(startNode, endNode);
    }
    if (startOffset < endOffset) {
      return constants.Dir.FORWARD;
    }
    return constants.Dir.BACKWARD;
  }
}

/**
 * Node state. Nodes can be on-screen like normal, or they may
 * be invisible if they are in a tab that is not in the foreground
 * or similar, or they may be invalid if they were removed from their
 * root, i.e. if they were in a window that was closed.
 * @enum {number}
 */
NodeUtils.NodeState = {
  NODE_STATE_INVALID: 0,
  NODE_STATE_INVISIBLE: 1,
  NODE_STATE_NORMAL: 2,
};


/**
 * Class representing a position on the accessibility, made of a
 * selected node and the offset of that selection.
 * @typedef {{node: (!AutomationNode),
 *            offset: (number)}}
 */
NodeUtils.Position;