chrome/browser/resources/chromeos/accessibility/common/cursors/cursor.js

// Copyright 2014 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 Structures related to cursors that point to and select parts of
 * the automation tree.
 */

import {AutomationPredicate} from '../automation_predicate.js';
import {AutomationUtil} from '../automation_util.js';
import {StringUtil} from '../string_util.js';

import {AncestryRecoveryStrategy, RecoveryStrategy} from './recovery_strategy.js';

const AutomationNode = chrome.automation.AutomationNode;
const Dir = constants.Dir;
const RoleType = chrome.automation.RoleType;
const StateType = chrome.automation.StateType;

/**
 * The special index that represents a cursor pointing to a node without
 * pointing to any part of its accessible text.
 */
export const CURSOR_NODE_INDEX = -1;

/**
 * Represents units of CursorMovement.
 * @enum {string}
 */
export const CursorUnit = {
  /** A single character within accessible name or value. */
  CHARACTER: 'character',

  /** A range of characters (given by attributes on automation nodes). */
  WORD: 'word',

  /** A text node. */
  TEXT: 'text',

  /** A leaf node. */
  NODE: 'node',

  /** A leaf node for guesture navigation. */
  GESTURE_NODE: 'gesture_node',

  /**
   * A node or in line textbox that immediately precedes or follows a visual
   *     line break.
   */
  LINE: 'line',
};

/**
 * Represents the ways in which cursors can move given a cursor unit.
 * @enum {string}
 */
export const CursorMovement = {
  /** Move to the beginning or end of the current unit. */
  BOUND: 'bound',

  /** Move to the next unit in a particular direction. */
  DIRECTIONAL: 'directional',

  /**
   * Move to the beginning or end of the current cursor. Only supports
   * Unit.CHARACTER and Unit.WORD
   */
  SYNC: 'sync',
};

/**
 * Represents a position within the automation tree.
 */
export class Cursor {
  /**
   * @param {!AutomationNode} node
   * @param {number} index A 0-based index into this cursor node's primary
   * accessible name. An index of |CURSOR_NODE_INDEX| means the node as a
   * whole is pointed to and covers the case where the accessible text is
   * empty.
   * @param {{wrapped: (boolean|undefined),
   *            preferNodeStartEquivalent: (boolean|undefined)}} args
   *     wrapped: determines whether this cursor wraps when moved beyond a
   * document boundary.
   *     preferNodeStartEquivalent: When true,moves this cursor to the start of
   * the next node when it points to the end of the current node.
   */
  constructor(node, index, args = {}) {
    // Compensate for specific issues in Blink.
    // TODO(dtseng): Pass through affinity; if upstream, skip below.
    if (node.role === RoleType.STATIC_TEXT && node.name.length === index &&
        !args.preferNodeStartEquivalent) {
      // Re-interpret this case as the beginning of the next node.
      const nextNode = AutomationUtil.findNextNode(
          node, Dir.FORWARD, AutomationPredicate.leafOrStaticText,
          {root: r => r === node.root});

      // The exception is when a user types at the end of a line. In that
      // case, staying on the current node is appropriate.
      if (node && node.nextOnLine && node.nextOnLine.role && nextNode) {
        node = nextNode;
        index = 0;
      }
    }

    /** @type {number} @private */
    this.index_ = index;
    /** @type {RecoveryStrategy} */
    this.recovery_ = new AncestryRecoveryStrategy(node);
    /** @private {boolean} */
    this.wrapped_ = args.wrapped || false;
  }

  /**
   * Convenience method to construct a Cursor from a node.
   * @param {!AutomationNode} node
   * @return {!Cursor}
   */
  static fromNode(node) {
    return new Cursor(node, CURSOR_NODE_INDEX);
  }

  /**
   * Gives a function that returns true for leaf types for |unit| navigations.
   * @param {!CursorUnit} unit
   * @return {AutomationPredicate.Unary}
   */
  static getLeafPredForUnit(unit) {
    switch (unit) {
      case CursorUnit.TEXT:
        return AutomationPredicate.leaf;
      case CursorUnit.GESTURE_NODE:
        return AutomationPredicate.gestureObject;
      default:
        return AutomationPredicate.object;
    }
  }

  /**
   * Returns true if |rhs| is equal to this cursor.
   * Use this for strict equality between cursors.
   * @param {!Cursor} rhs
   * @return {boolean}
   */
  equals(rhs) {
    return this.node === rhs.node && this.index === rhs.index;
  }

  equalsWithoutRecovery(rhs) {
    return this.recovery_.equalsWithoutRecovery(rhs.recovery_);
  }

  /**
   * Returns true if |rhs| is equal to this cursor.
   * Use this for loose equality between cursors where specific
   * character-based indicies do not matter such as when processing
   * node-targeted events.
   * @param {!Cursor} rhs
   * @return {boolean}
   */
  contentEquals(rhs) {
    // First, normalize the two nodes so they both point to the first non-text
    // node.
    let lNode = this.node;
    let rNode = rhs.node;
    while (lNode &&
           (lNode.role === RoleType.INLINE_TEXT_BOX ||
            lNode.role === RoleType.STATIC_TEXT)) {
      lNode = lNode.parent;
    }
    while (rNode &&
           (rNode.role === RoleType.INLINE_TEXT_BOX ||
            rNode.role === RoleType.STATIC_TEXT)) {
      rNode = rNode.parent;
    }

    // Ignore indicies for now.

    return lNode === rNode && lNode !== undefined;
  }

  /**
   * Compares this cursor with |rhs|.
   * @param {Cursor} rhs
   * @return Dir.BACKWARD if |rhs| comes before this cursor in
   * document order. Forward otherwise.
   */
  compare(rhs) {
    if (!this.node || !rhs.node) {
      return Dir.FORWARD;
    }

    if (rhs.node === this.node) {
      return rhs.index < this.index ? Dir.BACKWARD : Dir.FORWARD;
    }
    return AutomationUtil.getDirection(this.node, rhs.node);
  }

  /**
   * Returns the node. If the node is invalid since the last time it
   * was accessed, moves the cursor to the nearest valid ancestor first.
   * @return {!AutomationNode}
   */
  get node() {
    if (this.requiresRecovery()) {
      // If we need to recover, the index is no longer valid.
      this.index_ = CURSOR_NODE_INDEX;
    }
    return this.recovery_.node;
  }

  /**
   * @return {number}
   */
  get index() {
    return this.index_;
  }

  /**
   * A node appropriate for making selections.
   * @return {AutomationNode}
   */
  get selectionNode() {
    // TODO(accessibility): figure out if we still need the above property.
    return this.node;
  }

  /**
   * An index appropriate for making selections.  If this cursor has a
   * CURSOR_NODE_INDEX index, the selection index is a node offset e.g. the
   * index in parent. If not, the index is a character offset.
   * @return {number}
   */
  get selectionIndex() {
    return this.index_ === CURSOR_NODE_INDEX ? 0 : this.index_;
  }

  /**
   * Gets the accessible text of the node associated with this cursor.
   * @return {string}
   */
  getText() {
    return AutomationUtil.getText(this.node);
  }

  /**
   * Makes a Cursor which has been moved from this cursor by the unit in the
   * given direction using the given movement type.
   * @param {CursorUnit} unit
   * @param {CursorMovement} movement
   * @param {constants.Dir} dir
   * @return {!Cursor} The moved cursor.
   */
  move(unit, movement, dir) {
    const originalNode = this.node;
    if (!originalNode) {
      return this;
    }

    let newNode = originalNode;
    let newIndex = this.index_;

    switch (unit) {
      case CursorUnit.CHARACTER:
        const text = this.getText();

        switch (movement) {
          case CursorMovement.BOUND:
          case CursorMovement.DIRECTIONAL:
            if (newIndex === CURSOR_NODE_INDEX) {
              newIndex = 0;
            }

            newIndex = dir === Dir.FORWARD ?
                StringUtil.nextCodePointOffset(text, newIndex) :
                StringUtil.previousCodePointOffset(text, newIndex);
            if (newIndex < 0 || newIndex >= text.length) {
              newNode = AutomationUtil.findNextNode(
                  newNode, dir, AutomationPredicate.leafWithText);
              if (newNode) {
                const newText = AutomationUtil.getText(newNode);
                newIndex = dir === Dir.FORWARD ?
                    0 :
                    StringUtil.previousCodePointOffset(newText, newText.length);
                newIndex = Math.max(newIndex, 0);
              } else {
                newIndex = this.index_;
              }
            }
            break;
          case CursorMovement.SYNC:
            if (newIndex === CURSOR_NODE_INDEX) {
              newIndex = dir === Dir.FORWARD ?
                  0 :
                  StringUtil.previousCodePointOffset(text, text.length);
            } else {
              newIndex = dir === Dir.FORWARD ?
                  StringUtil.nextCodePointOffset(text, newIndex) :
                  StringUtil.previousCodePointOffset(text, newIndex);
            }
            if (newIndex < 0 || newIndex >= text.length) {
              // unfortunate case. Fallback to return the same one as |this|.
              newIndex = this.index_;
            }
            break;
        }
        break;
      case CursorUnit.WORD:
        // If we're not already on a node with word stops, find the next one.
        if (!AutomationPredicate.leafWithWordStop(newNode)) {
          newNode =
              AutomationUtil.findNextNode(
                  newNode, Dir.FORWARD, AutomationPredicate.leafWithWordStop,
                  {skipInitialSubtree: false}) ||
              newNode;
        }

        // Ensure start position is on or after first word.
        const firstWordStart =
            (newNode.wordStarts && newNode.wordStarts.length) ?
            newNode.wordStarts[0] :
            0;
        if (newIndex < firstWordStart && movement !== CursorMovement.SYNC) {
          // Also catches CURSOR_NODE_INDEX case.
          newIndex = firstWordStart;
        }

        switch (movement) {
          case CursorMovement.BOUND: {
            let wordStarts;
            let wordEnds;
            if (newNode.role === RoleType.INLINE_TEXT_BOX) {
              wordStarts = newNode.wordStarts;
              wordEnds = newNode.wordEnds;
            } else {
              wordStarts = newNode.nonInlineTextWordStarts;
              wordEnds = newNode.nonInlineTextWordEnds;
            }
            let start;
            let end;
            for (let i = 0; i < wordStarts.length; i++) {
              if (newIndex >= wordStarts[i] && newIndex < wordEnds[i]) {
                start = wordStarts[i];
                end = wordEnds[i];
                break;
              }
            }
            if (goog.isDef(start) && goog.isDef(end)) {
              newIndex = dir === Dir.FORWARD ? end : start;
            }
          } break;
          case CursorMovement.SYNC:
            if (newIndex === CURSOR_NODE_INDEX) {
              newIndex = dir === Dir.FORWARD ? firstWordStart - 1 :
                                               this.getText().length;
            }
          // fallthrough
          case CursorMovement.DIRECTIONAL: {
            let wordStarts;
            let wordEnds;
            let start;
            if (newNode.role === RoleType.INLINE_TEXT_BOX) {
              wordStarts = newNode.wordStarts;
              wordEnds = newNode.wordEnds;
            } else {
              wordStarts = newNode.nonInlineTextWordStarts;
              wordEnds = newNode.nonInlineTextWordEnds;
            }
            // Go to the next word stop in the same piece of text.
            for (let i = 0; i < wordStarts.length; i++) {
              if ((dir === Dir.FORWARD && newIndex < wordStarts[i]) ||
                  (dir === Dir.BACKWARD && newIndex >= wordEnds[i])) {
                start = wordStarts[i];
                if (dir === Dir.FORWARD) {
                  break;
                }
              }
            }
            if (goog.isDef(start)) {
              // Successfully found the next word stop within the same text
              // node.
              newIndex = start;
            } else if (movement === CursorMovement.DIRECTIONAL) {
              // Use adjacent word in adjacent next node in direction |dir|.
              if (dir === Dir.BACKWARD && newIndex > firstWordStart) {
                // The backward case is special at the beginning of nodes.
                newIndex = firstWordStart;
              } else {
                newNode = AutomationUtil.findNextNode(
                    newNode, dir, AutomationPredicate.leafWithWordStop,
                    {root: r => r === newNode.root});
                if (newNode) {
                  let starts;
                  if (newNode.role === RoleType.INLINE_TEXT_BOX) {
                    starts = newNode.wordStarts;
                  } else {
                    starts = newNode.nonInlineTextWordStarts;
                  }
                  if (starts.length) {
                    newIndex = dir === Dir.BACKWARD ?
                        starts[starts.length - 1] :
                        starts[0];
                  }
                }
              }
            }
          }
        }
        break;
      case CursorUnit.TEXT:
      case CursorUnit.NODE:
      case CursorUnit.GESTURE_NODE:
        switch (movement) {
          case CursorMovement.BOUND:
            newIndex = dir === Dir.FORWARD ? this.getText().length - 1 : 0;
            break;
          case CursorMovement.DIRECTIONAL:
            const pred = Cursor.getLeafPredForUnit(unit);
            newNode =
                AutomationUtil.findNextNode(newNode, dir, pred) || originalNode;
            newIndex = CURSOR_NODE_INDEX;
            break;
        }
        break;
      case CursorUnit.LINE:
        switch (movement) {
          case CursorMovement.BOUND:
            newNode = AutomationUtil.findNodeUntil(
                newNode, dir, AutomationPredicate.linebreak, true);
            newNode = newNode || originalNode;
            newIndex = dir === Dir.FORWARD ?
                AutomationUtil.getText(newNode).length :
                0;
            break;
          case CursorMovement.DIRECTIONAL:
            newNode = AutomationUtil.findNodeUntil(
                newNode, dir, AutomationPredicate.linebreak);
            if (newNode) {
              newIndex = 0;
            }
            break;
        }
        break;
      default:
        throw Error('Unrecognized unit: ' + unit);
    }
    newNode = newNode || originalNode;
    newIndex = (newIndex !== undefined) ? newIndex : this.index_;
    return new Cursor(newNode, newIndex);
  }

  /**
   * Returns the deepest equivalent cursor.
   * @return {!Cursor}
   */
  get deepEquivalent() {
    let newNode = this.node;
    let newIndex = this.index_;
    let isTextIndex = false;

    while (newNode.firstChild) {
      if (AutomationPredicate.editText(newNode) &&
          !newNode.state[StateType.MULTILINE]) {
        // Do not reinterpret nodes and indices on this node.
        break;
      } else if (newNode.role === RoleType.STATIC_TEXT) {
        // Text offset.
        // Re-interpret the index as an offset into an inlineTextBox.
        isTextIndex = true;
        let target = newNode.firstChild;
        let length = 0;
        while (target && length < newIndex) {
          const newLength = length + target.name.length;

          // Either |newIndex| falls between target's text or |newIndex| is
          // the total length of all sibling text content.
          if ((length <= newIndex && newIndex < newLength) ||
              (newIndex === newLength && !target.nextSibling)) {
            break;
          }
          length = newLength;
          target = target.nextSibling;
        }
        if (target) {
          newNode = target;
          newIndex = newIndex - length;
        }
        break;
      } else if (
          newNode.role !== RoleType.INLINE_TEXT_BOX &&
          // An index inside a content editable or a descendant of a content
          // editable should be treated as a child offset.
          // However, an index inside a simple editable, such as an input
          // element, should be treated as a character offset.
          (!newNode.state[StateType.EDITABLE] ||
           newNode.state[StateType.RICHLY_EDITABLE]) &&
          newIndex <= newNode.children.length) {
        // Valid child node offset. Note that there is a special case where
        // |newIndex == node.children.length|. In these cases, we actually
        // want to position the cursor at the end of the text of
        // |node.children[newIndex - 1]|.
        // |newIndex| is assumed to be > 0.
        if (newIndex === newNode.children.length) {
          // Take the last child.
          newNode = newNode.lastChild;

          // The |newIndex| is either a text offset or a child offset.
          if (newNode.role === RoleType.STATIC_TEXT) {
            newIndex = newNode.name.length;
            isTextIndex = true;
            break;
          }

          // The last valid child index.
          newIndex = newNode.children.length;
        } else {
          newNode = newNode.children[newIndex];
          newIndex = 0;
        }
      } else {
        // This offset is a text offset into the descendant visible
        // text. Approximate this by indexing into the inline text boxes.
        isTextIndex = true;
        const lines = this.getAllLeaves_(newNode);
        if (!lines.length) {
          break;
        }

        let targetLine;
        let targetIndex = 0;
        for (let i = 0, line, cur = 0; line = lines[i]; i++) {
          const lineLength = line.name ? line.name.length : 1;
          cur += lineLength;
          if (cur > newIndex) {
            targetLine = line;
            if (!line.name) {
              targetIndex = CURSOR_NODE_INDEX;
            } else {
              targetIndex = newIndex - (cur - lineLength);
            }
            break;
          }
        }
        if (!targetLine) {
          // If we got here, that means the index is actually beyond the total
          // length of text. Just get the last line.
          targetLine = lines[lines.length - 1];
          targetIndex = targetLine ? targetLine.name.length : CURSOR_NODE_INDEX;
        }
        newNode = targetLine;
        newIndex = targetIndex;
        break;
      }
    }
    if (!isTextIndex) {
      newIndex = CURSOR_NODE_INDEX;
    }

    return new this.constructor(newNode, newIndex);
  }

  /**
   * Returns whether this cursor points to a valid position.
   * @return {boolean}
   */
  isValid() {
    return this.node != null;
  }

  /**
   * Returns true if this cursor requires recovery.
   * @return {boolean}
   */
  requiresRecovery() {
    return this.recovery_.requiresRecovery();
  }

  /**
   * @private
   * @param {!AutomationNode} node
   * @return {!Array<!AutomationNode>}
   */
  getAllLeaves_(node) {
    let ret = [];
    if (!node.firstChild) {
      ret.push(node);
      return ret;
    }

    for (let i = 0; i < node.children.length; i++) {
      ret = ret.concat(this.getAllLeaves_(node.children[i]));
    }

    return ret;
  }

  /**
   * Returns true if this cursor was created after wrapping. For example, moving
   * from a cursor at the end of a web contents to [this] range at the beginning
   * of the document.
   * @return {boolean}
   */
  get wrapped() {
    return this.wrapped_;
  }
}


/**
 * A Cursor that wraps from beginning to end and vice versa when
 * moved.
 */
export class WrappingCursor extends Cursor {
  /**
   * @param {!AutomationNode} node
   * @param {number} index A 0-based index into this cursor node's primary
   * accessible name. An index of |CURSOR_NODE_INDEX| means the node as a
   * whole is pointed to and covers the case where the accessible text is
   * empty.
   * @param {{wrapped: (boolean|undefined)}} args
   */
  constructor(node, index, args = {}) {
    super(node, index, args);
  }

  /**
   * Convenience method to construct a Cursor from a node.
   * @param {!AutomationNode} node
   * @return {!WrappingCursor}
   */
  static fromNode(node) {
    return new WrappingCursor(node, CURSOR_NODE_INDEX);
  }

  /** @override */
  move(unit, movement, dir) {
    let result = this;
    if (!result.node) {
      return this;
    }

    // Regular movement.
    if (!AutomationPredicate.root(this.node) || dir === Dir.FORWARD ||
        movement === CursorMovement.BOUND) {
      result = Cursor.prototype.move.call(this, unit, movement, dir);
    }

    // Moving to the bounds of a unit never wraps.
    if (movement === CursorMovement.BOUND || movement === CursorMovement.SYNC) {
      return new WrappingCursor(result.node, result.index);
    }

    // There are two cases for wrapping:
    // 1. moving forwards from the last element.
    // 2. moving backwards from the first element.
    // Both result in |move| returning the same cursor.
    // For 1, simply place the new cursor on the document node.
    // For 2, place range on the root (if not already there). If at root,
    // try to descend to the first leaf-like object.
    if (movement === CursorMovement.DIRECTIONAL && result.equals(this)) {
      const pred = Cursor.getLeafPredForUnit(unit);
      let endpoint = this.node;
      if (!endpoint) {
        return this;
      }

      // Finds any explicitly provided focus.
      const getDirectedFocus = function(node) {
        return dir === Dir.FORWARD ? node.nextFocus : node.previousFocus;
      };

      // Case 1: forwards (find the root-like node).
      let directedFocus;
      while (endpoint.parent) {
        if (directedFocus = getDirectedFocus(endpoint)) {
          break;
        }
        if (AutomationPredicate.root(endpoint)) {
          break;
        }
        endpoint = endpoint.parent;
      }

      if (directedFocus) {
        directedFocus =
            (dir === Dir.FORWARD ?
                 AutomationUtil.findNodePre(
                     directedFocus, dir, AutomationPredicate.object) :
                 AutomationUtil.findLastNode(directedFocus, pred)) ||
            directedFocus;
        return new WrappingCursor(directedFocus, CURSOR_NODE_INDEX);
      }

      // Always consider this cursor wrapped when moving forward.
      let wrapped = dir === Dir.FORWARD;

      // Case 2: backward (sync downwards to a leaf), if already on the root.
      if (dir === Dir.BACKWARD && endpoint === this.node) {
        wrapped = true;
        endpoint = AutomationUtil.findLastNode(endpoint, pred) || endpoint;
      }

      return new WrappingCursor(endpoint, CURSOR_NODE_INDEX, {wrapped});
    }
    return new WrappingCursor(result.node, result.index);
  }
}