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   }
  99 };
 100
 101 /**
 102  * Find the next node in the given direction in depth first order.
 103  * @param {AutomationNode} cur Node to begin the search from.
 104  * @param {Dir} dir
 105  * @param {AutomationPredicate.Unary} pred A predicate to apply
 106  *     to a candidate node.
 107  * @return {AutomationNode}
 108  */
 109 AutomationUtil.findNextNode = function(cur, dir, pred) {
 110   var next = cur;
 111   do {
 112     if (!(next = AutomationUtil.findNextSubtree(cur, dir)))
 113       return null;
 114     cur = next;
 115     next = AutomationUtil.findNodePre(next, dir, pred);
 116   } while (!next);
 117   return next;
 118 };
 119
 120 /**
 121  * Given nodes a_1, ..., a_n starting at |cur| in pre order traversal, apply
 122  * |pred| to a_i and a_(i - 1) until |pred| is satisfied.  Returns a_(i - 1) or
 123  * a_i (depending on opt_options.before) or null if no match was found.
 124  * @param {AutomationNode} cur
 125  * @param {Dir} dir
 126  * @param {AutomationPredicate.Binary} pred
 127  * @param {{filter: (AutomationPredicate.Unary|undefined),
 128  *      before: boolean?}=} opt_options
 129  *     filter - Filters which candidate nodes to consider. Defaults to leaf
 130  *         only.
 131  *     before - True to return a_(i - 1); a_i otherwise. Defaults to false.
 132  * @return {AutomationNode}
 133  */
 134 AutomationUtil.findNodeUntil = function(cur, dir, pred, opt_options) {
 135   opt_options =
 136       opt_options || {filter: AutomationPredicate.leaf, before: false};
 137   if (!opt_options.filter)
 138     opt_options.filter = AutomationPredicate.leaf;
 139
 140   var before = null;
 141   var after = null;
 142   var prev = cur;
 143   AutomationUtil.findNextNode(cur,
 144       dir,
 145       function(candidate) {
 146         if (!opt_options.filter(candidate))
 147           return false;
 148
 149         var satisfied = pred(prev, candidate);
 150
 151         prev = candidate;
 152         if (!satisfied)
 153           before = candidate;
 154         else
 155           after = candidate;
 156         return satisfied;
 157     });
 158   return opt_options.before ? before : after;
 159 };
 160
 161 /**
 162  * Returns an array containing ancestors of node starting at root down to node.
 163  * @param {!AutomationNode} node
 164  * @return {!Array<AutomationNode>}
 165  */
 166 AutomationUtil.getAncestors = function(node) {
 167   var ret = [];
 168   var candidate = node;
 169   while (candidate) {
 170     ret.push(candidate);
 171
 172     if (!AutomationUtil.isInSameTree(candidate, candidate.parent))
 173       break;
 174
 175     candidate = candidate.parent;
 176   }
 177   return ret.reverse();
 178 };
 179
 180 /**
 181  * Gets the first index where the two input arrays differ. Returns -1 if they
 182  * do not.
 183  * @param {!Array<AutomationNode>} ancestorsA
 184  * @param {!Array<AutomationNode>} ancestorsB
 185  * @return {number}
 186  */
 187 AutomationUtil.getDivergence = function(ancestorsA, ancestorsB) {
 188   for (var i = 0; i < ancestorsA.length; i++) {
 189     if (ancestorsA[i] !== ancestorsB[i])
 190       return i;
 191   }
 192   if (ancestorsA.length == ancestorsB.length)
 193     return -1;
 194   return ancestorsA.length;
 195 };
 196
 197 /**
 198  * Returns ancestors of |node| that are not also ancestors of |prevNode|.
 199  * @param {!AutomationNode} prevNode
 200  * @param {!AutomationNode} node
 201  * @return {!Array<AutomationNode>}
 202  */
 203 AutomationUtil.getUniqueAncestors = function(prevNode, node) {
 204   var prevAncestors = AutomationUtil.getAncestors(prevNode);
 205   var ancestors = AutomationUtil.getAncestors(node);
 206   var divergence = AutomationUtil.getDivergence(prevAncestors, ancestors);
 207   return ancestors.slice(divergence);
 208 };
 209
 210 /**
 211  * Given |nodeA| and |nodeB| in that order, determines their ordering in the
 212  * document.
 213  * @param {!AutomationNode} nodeA
 214  * @param {!AutomationNode} nodeB
 215  * @return {AutomationUtil.Dir}
 216  */
 217 AutomationUtil.getDirection = function(nodeA, nodeB) {
 218   var ancestorsA = AutomationUtil.getAncestors(nodeA);
 219   var ancestorsB = AutomationUtil.getAncestors(nodeB);
 220   var divergence = AutomationUtil.getDivergence(ancestorsA, ancestorsB);
 221
 222   // Default to Dir.FORWARD.
 223   if (divergence == -1)
 224     return Dir.FORWARD;
 225
 226   var divA = ancestorsA[divergence];
 227   var divB = ancestorsB[divergence];
 228
 229   // One of the nodes is an ancestor of the other. Don't distinguish and just
 230   // consider it Dir.FORWARD.
 231   if (!divA || !divB || divA.parent === nodeB || divB.parent === nodeA)
 232     return Dir.FORWARD;
 233
 234   return divA.indexInParent <= divB.indexInParent ? Dir.FORWARD : Dir.BACKWARD;
 235 };
 236
 237 /**
 238  * Determines whether the two given nodes come from the same tree source.
 239  * @param {AutomationNode} a
 240  * @param {AutomationNode} b
 241  * @return {boolean}
 242  */
 243 AutomationUtil.isInSameTree = function(a, b) {
 244   if (!a || !b)
 245     return true;
 246
 247   return a.root === b.root;
 248 };
 249
 250 });  // goog.scope