chrome/browser/resources/chromeos/chromevox/cvox2/background/automation_util.js

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 /**
   6  * @fileoverview ChromeVox utilities for the automation extension API.
   7  */
   8
   9 goog.provide('AutomationUtil');
  10 goog.provide('AutomationUtil.Dir');
  11
  12 goog.require('AutomationPredicate');
  13
  14 /**
  15  * @constructor
  16  */
  17 AutomationUtil = function() {};
  18
  19 /**
  20  * Possible directions to perform tree traversals.
  21  * @enum {string}
  22  */
  23 AutomationUtil.Dir = {
  24   // Search from left to right.
  25   FORWARD: 'forward',
  26
  27   // Search from right to left.
  28   BACKWARD: 'backward'
  29 };
  30
  31
  32 goog.scope(function() {
  33 var AutomationNode = chrome.automation.AutomationNode;
  34 var Dir = AutomationUtil.Dir;
  35
  36 /**
  37  * Find a node in subtree of |cur| satisfying |pred| using pre-order traversal.
  38  * @param {AutomationNode} cur Node to begin the search from.
  39  * @param {Dir} dir
  40  * @param {AutomationPredicate.Unary} pred A predicate to apply
  41  *     to a candidate node.
  42  * @return {AutomationNode}
  43  */
  44 AutomationUtil.findNodePre = function(cur, dir, pred) {
  45   if (pred(cur))
  46     return cur;
  47
  48   var child = dir == Dir.BACKWARD ? cur.lastChild : cur.firstChild;
  49   while (child) {
  50     var ret = AutomationUtil.findNodePre(child, dir, pred);
  51     if (ret)
  52       return ret;
  53     child = dir == Dir.BACKWARD ?
  54         child.previousSibling : child.nextSibling;
  55   }
  56 };
  57
  58 /**
  59  * Find a node in subtree of |cur| satisfying |pred| using post-order traversal.
  60  * @param {AutomationNode} cur Node to begin the search from.
  61  * @param {Dir} dir
  62  * @param {AutomationPredicate.Unary} pred A predicate to apply
  63  *     to a candidate node.
  64  * @return {AutomationNode}
  65  */
  66 AutomationUtil.findNodePost = function(cur, dir, pred) {
  67   var child = dir == Dir.BACKWARD ? cur.lastChild : cur.firstChild;
  68   while (child) {
  69     var ret = AutomationUtil.findNodePost(child, dir, pred);
  70     if (ret)
  71       return ret;
  72     child = dir == Dir.BACKWARD ?
  73         child.previousSibling : child.nextSibling;
  74   }
  75
  76   if (pred(cur))
  77     return cur;
  78 };
  79
  80 /**
  81  * Find the next node in the given direction that is either an immediate sibling
  82  * or a sibling of an ancestor.
  83  * @param {AutomationNode} cur Node to start search from.
  84  * @param {Dir} dir
  85  * @return {AutomationNode}
  86  */
  87 AutomationUtil.findNextSubtree = function(cur, dir) {
  88   while (cur) {
  89     var next = dir == Dir.BACKWARD ?
  90         cur.previousSibling : cur.nextSibling;
  91     if (!AutomationUtil.isInSameTree(cur, next))
  92       return null;
  93     if (next)
  94       return next;
  95     if (!AutomationUtil.isInSameTree(cur, cur.parent))
  96       return null;
  97     cur = cur.parent;
  98     if (AutomationUtil.isTraversalRoot_(cur))
  99       return null;
 100   }
 101 };
 102
 103 /**
 104  * Find the next node in the given direction in depth first order.
 105  * @param {AutomationNode} cur Node to begin the search from.
 106  * @param {Dir} dir
 107  * @param {AutomationPredicate.Unary} pred A predicate to apply
 108  *     to a candidate node.
 109  * @return {AutomationNode}
 110  */
 111 AutomationUtil.findNextNode = function(cur, dir, pred) {
 112   var next = cur;
 113   do {
 114     if (!(next = AutomationUtil.findNextSubtree(cur, dir)))
 115       return null;
 116     cur = next;
 117     next = AutomationUtil.findNodePre(next, dir, pred);
 118     if (next && AutomationPredicate.shouldIgnoreLeaf(next)) {
 119       cur = next;
 120       next = null;
 121     }
 122   } while (!next);
 123   return next;
 124 };
 125
 126 /**
 127  * Given nodes a_1, ..., a_n starting at |cur| in pre order traversal, apply
 128  * |pred| to a_i and a_(i - 1) until |pred| is satisfied.  Returns a_(i - 1) or
 129  * a_i (depending on opt_options.before) or null if no match was found.
 130  * @param {AutomationNode} cur
 131  * @param {Dir} dir
 132  * @param {AutomationPredicate.Binary} pred
 133  * @param {{filter: (AutomationPredicate.Unary|undefined),
 134  *      before: boolean?}=} opt_options
 135  *     filter - Filters which candidate nodes to consider. Defaults to leaf
 136  *         only.
 137  *     before - True to return a_(i - 1); a_i otherwise. Defaults to false.
 138  * @return {AutomationNode}
 139  */
 140 AutomationUtil.findNodeUntil = function(cur, dir, pred, opt_options) {
 141   opt_options =
 142       opt_options || {filter: AutomationPredicate.leaf, before: false};
 143   if (!opt_options.filter)
 144     opt_options.filter = AutomationPredicate.leaf;
 145
 146   var before = null;
 147   var after = null;
 148   var prev = cur;
 149   AutomationUtil.findNextNode(cur,
 150       dir,
 151       function(candidate) {
 152         if (!opt_options.filter(candidate))
 153           return false;
 154
 155         var satisfied = pred(prev, candidate);
 156
 157         prev = candidate;
 158         if (!satisfied)
 159           before = candidate;
 160         else
 161           after = candidate;
 162         return satisfied;
 163     });
 164   return opt_options.before ? before : after;
 165 };
 166
 167 /**
 168  * Returns an array containing ancestors of node starting at root down to node.
 169  * @param {!AutomationNode} node
 170  * @return {!Array<AutomationNode>}
 171  */
 172 AutomationUtil.getAncestors = function(node) {
 173   var ret = [];
 174   var candidate = node;
 175   while (candidate) {
 176     ret.push(candidate);
 177
 178     if (!AutomationUtil.isInSameTree(candidate, candidate.parent))
 179       break;
 180
 181     candidate = candidate.parent;
 182   }
 183   return ret.reverse();
 184 };
 185
 186 /**
 187  * Gets the first index where the two input arrays differ. Returns -1 if they
 188  * do not.
 189  * @param {!Array<AutomationNode>} ancestorsA
 190  * @param {!Array<AutomationNode>} ancestorsB
 191  * @return {number}
 192  */
 193 AutomationUtil.getDivergence = function(ancestorsA, ancestorsB) {
 194   for (var i = 0; i < ancestorsA.length; i++) {
 195     if (ancestorsA[i] !== ancestorsB[i])
 196       return i;
 197   }
 198   if (ancestorsA.length == ancestorsB.length)
 199     return -1;
 200   return ancestorsA.length;
 201 };
 202
 203 /**
 204  * Returns ancestors of |node| that are not also ancestors of |prevNode|.
 205  * @param {!AutomationNode} prevNode
 206  * @param {!AutomationNode} node
 207  * @return {!Array<AutomationNode>}
 208  */
 209 AutomationUtil.getUniqueAncestors = function(prevNode, node) {
 210   var prevAncestors = AutomationUtil.getAncestors(prevNode);
 211   var ancestors = AutomationUtil.getAncestors(node);
 212   var divergence = AutomationUtil.getDivergence(prevAncestors, ancestors);
 213   return ancestors.slice(divergence);
 214 };
 215
 216 /**
 217  * Given |nodeA| and |nodeB| in that order, determines their ordering in the
 218  * document.
 219  * @param {!AutomationNode} nodeA
 220  * @param {!AutomationNode} nodeB
 221  * @return {AutomationUtil.Dir}
 222  */
 223 AutomationUtil.getDirection = function(nodeA, nodeB) {
 224   var ancestorsA = AutomationUtil.getAncestors(nodeA);
 225   var ancestorsB = AutomationUtil.getAncestors(nodeB);
 226   var divergence = AutomationUtil.getDivergence(ancestorsA, ancestorsB);
 227
 228   // Default to Dir.FORWARD.
 229   if (divergence == -1)
 230     return Dir.FORWARD;
 231
 232   var divA = ancestorsA[divergence];
 233   var divB = ancestorsB[divergence];
 234
 235   // One of the nodes is an ancestor of the other. Don't distinguish and just
 236   // consider it Dir.FORWARD.
 237   if (!divA || !divB || divA.parent === nodeB || divB.parent === nodeA)
 238     return Dir.FORWARD;
 239
 240   return divA.indexInParent <= divB.indexInParent ? Dir.FORWARD : Dir.BACKWARD;
 241 };
 242
 243 /**
 244  * Determines whether the two given nodes come from the same tree source.
 245  * @param {AutomationNode} a
 246  * @param {AutomationNode} b
 247  * @return {boolean}
 248  */
 249 AutomationUtil.isInSameTree = function(a, b) {
 250   if (!a || !b)
 251     return true;
 252
 253   // Given two non-desktop roots, consider them in the "same" tree.
 254   return a.root === b.root ||
 255       (a.root.role == b.root.role && a.root.role == 'rootWebArea');
 256 };
 257
 258 /**
 259  * Returns whether the given node should not be crossed when performing
 260  * traversals up the ancestry chain.
 261  * @param {AutomationNode} node
 262  * @return {boolean}
 263  * @private
 264  */
 265 AutomationUtil.isTraversalRoot_ = function(node) {
 266   switch (node.role) {
 267     case 'dialog':
 268     case 'window':
 269       return true;
 270     case 'toolbar':
 271       return node.root.role == 'desktop';
 272     default:
 273       return false;
 274   }
 275 };
 276
 277 });  // goog.scope