Implement ChromeVox next/previous line, link, and heading.

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

Index: chrome/browser/resources/chromeos/chromevox/cvox2/background/automation_util.js
diff --git a/chrome/browser/resources/chromeos/chromevox/cvox2/background/automation_util.js b/chrome/browser/resources/chromeos/chromevox/cvox2/background/automation_util.js
new file mode 100644
index 0000000000000000000000000000000000000000..c87e463227326fd5a0709b5db0f58e4de4dbbce9
--- /dev/null
+++ b/chrome/browser/resources/chromeos/chromevox/cvox2/background/automation_util.js
@@ -0,0 +1,127 @@
+// 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 ChromeVox utilities for the automation extension API.
+ */
+
+goog.provide('cvox2.AutomationPredicates');
+goog.provide('cvox2.AutomationUtil');
+
+/**
+ * @constructor
+ */
+cvox2.AutomationPredicates = function() {};
+
+/**
+ * Constructs a predicate given a role.
+ * @param {string} role
+ * @return {function(AutomationNode) : boolean}
+ */
+cvox2.AutomationPredicates.makeRolePredicate = function(role) {
+  return function(node) {
+    return node.role == role;
+  };
+};
+
+/** @type {function(AutomationNode) : boolean} */
+cvox2.AutomationPredicates.heading =
+    cvox2.AutomationPredicates.makeRolePredicate(
+        chrome.automation.RoleType.heading);
+/** @type {function(AutomationNode) : boolean} */
+cvox2.AutomationPredicates.inlineTextBox =
+    cvox2.AutomationPredicates.makeRolePredicate(
+        chrome.automation.RoleType.inlineTextBox);
+/** @type {function(AutomationNode) : boolean} */
+cvox2.AutomationPredicates.link =
+    cvox2.AutomationPredicates.makeRolePredicate(
+        chrome.automation.RoleType.link);
+
+/**
+ * @constructor
+ */
+cvox2.AutomationUtil = function() {};
+
+/**
+ * Find a node in subtree of |cur| satisfying |pred|.
+ * @param {AutomationNode} cur Node to begin the search from.
+ * @param {boolean} r False to search forward (left to right), true to search
+ * backward (right to left).
+ * @param {function(AutomationNode) : boolean} pred A predicate to apply to a
+ * candidate node.
+ * @return {AutomationNode}
+ */
+cvox2.AutomationUtil.findNode = function(cur, r, pred) {
+  if (pred(cur))
+    return cur;
+
+  var child = r ? cur.lastChild() : cur.firstChild();
+  while (child) {
+    var ret = cvox2.AutomationUtil.findNode(child, r, pred);
+    if (ret)
+      return ret;
+    child = r ? child.previousSibling() : child.nextSibling();
+  }
+};
+
+/**
+ * Find a node in subtree of |cur| satisfying |pred|. Differs from |findNode|
+ * in-terms of ordering: checks while unwinding stack.
+ * @param {AutomationNode} cur Node to begin the search from.
+ * @param {boolean} r False to search forward (left to right), true to search
+ * backward (right to left).
+ * @param {function(AutomationNode) : boolean} pred A predicate to apply to a
+ * candidate node.
+ * @return {AutomationNode}
+ */
+cvox2.AutomationUtil.findDeepestNode = function(cur, r, pred) {

[dmazzoni, 2014/09/26 06:08:52]

Hmmm, this doesn't really find the "deepest" node - I believe the correct
technical term is that this is a post-order traversal of the tree, the other one
is pre-order traversal.

+  var child = r ? cur.lastChild() : cur.firstChild();
+  while (child) {
+    var ret = cvox2.AutomationUtil.findDeepestNode(child, r, pred);
+    if (ret)
+      return ret;
+    child = r ? child.previousSibling() : child.nextSibling();
+  }
+
+  if (pred(cur))
+    return cur;
+};
+
+/**
+ * Find the directed next node that is either an immediate sibling or a sibling
+ * of an ancestor.
+ * @param {AutomationNode} cur Node to start search from.
+ * @param {boolean} r False to search forward (left to right), true to search
+ * backward (right to left).
+ * @return {AutomationNode}
+ */
+cvox2.AutomationUtil.findNextSubtree = function(cur, r) {
+  while (cur) {
+    var next = r ? cur.previousSibling() : cur.nextSibling();
+    if (next)
+      return next;
+
+    cur = cur.parent();
+  }
+};
+
+/**
+ * Find the directed next node in depth first order.
+ * @param {AutomationNode} cur Node to begin the search from.
+ * @param {boolean} r False to search forward (left to right), true to search
+ * backward (right to left).
+ * @param {function(AutomationNode) : boolean} pred A predicate to apply to a
+ * candidate node.
+ * @return {AutomationNode}
+ */
+cvox2.AutomationUtil.findNextNode = function(cur, r, pred) {
+  var next = cur;
+  do {
+    if (!(next = cvox2.AutomationUtil.findNextSubtree(cur, r)))
+      return null;
+    cur = next;
+    next = cvox2.AutomationUtil.findNode(next, r, pred);
+  } while (!next);
+  return next;
+};