chrome/browser/resources/chromeos/chromevox/common/traverse_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 Low-level DOM traversal utility functions to find the
   7  *     next (or previous) character, word, sentence, line, or paragraph,
   8  *     in a completely stateless manner without actually manipulating the
   9  *     selection.
  10  */
  11
  12 goog.provide('cvox.TraverseUtil');
  13
  14 goog.require('cvox.Cursor');
  15 goog.require('cvox.DomPredicates');
  16 goog.require('cvox.DomUtil');
  17
  18 /**
  19  * Utility functions for stateless DOM traversal.
  20  * @constructor
  21  */
  22 cvox.TraverseUtil = function() {};
  23
  24 /**
  25  * Gets the text representation of a node. This allows us to substitute
  26  * alt text, names, or titles for html elements that provide them.
  27  * @param {Node} node A DOM node.
  28  * @return {string} A text string representation of the node.
  29  */
  30 cvox.TraverseUtil.getNodeText = function(node) {
  31   if (node.constructor == Text) {
  32     return node.data;
  33   } else {
  34     return '';
  35   }
  36 };
  37
  38 /**
  39  * Return true if a node should be treated as a leaf node, because
  40  * its children are properties of the object that shouldn't be traversed.
  41  *
  42  * TODO(dmazzoni): replace this with a predicate that detects nodes with
  43  * ARIA roles and other objects that have their own description.
  44  * For now we just detect a couple of common cases.
  45  *
  46  * @param {Node} node A DOM node.
  47  * @return {boolean} True if the node should be treated as a leaf node.
  48  */
  49 cvox.TraverseUtil.treatAsLeafNode = function(node) {
  50   return node.childNodes.length == 0 ||
  51          node.nodeName == 'SELECT' ||
  52          node.getAttribute('role') == 'listbox' ||
  53          node.nodeName == 'OBJECT';
  54 };
  55
  56 /**
  57  * Return true only if a single character is whitespace.
  58  * From https://developer.mozilla.org/en/Whitespace_in_the_DOM,
  59  * whitespace is defined as one of the characters
  60  *  "\t" TAB \u0009
  61  *  "\n" LF  \u000A
  62  *  "\r" CR  \u000D
  63  *  " "  SPC \u0020.
  64  *
  65  * @param {string} c A string containing a single character.
  66  * @return {boolean} True if the character is whitespace, otherwise false.
  67  */
  68 cvox.TraverseUtil.isWhitespace = function(c) {
  69   return (c == ' ' || c == '\n' || c == '\r' || c == '\t');
  70 };
  71
  72 /**
  73  * Set the selection to the range between the given start and end cursors.
  74  * @param {cvox.Cursor} start The desired start of the selection.
  75  * @param {cvox.Cursor} end The desired end of the selection.
  76  * @return {Selection} the selection object.
  77  */
  78 cvox.TraverseUtil.setSelection = function(start, end) {
  79   var sel = window.getSelection();
  80   sel.removeAllRanges();
  81   var range = document.createRange();
  82   range.setStart(start.node, start.index);
  83   range.setEnd(end.node, end.index);
  84   sel.addRange(range);
  85
  86   return sel;
  87 };
  88
  89 // TODO(dtseng): Combine with cvox.DomUtil.hasContent.
  90 /**
  91  * Check if this DOM node has the attribute aria-hidden='true', which should
  92  * hide it from screen readers.
  93  * @param {Node} node An HTML DOM node.
  94  * @return {boolean} Whether or not the html node should be traversed.
  95  */
  96 cvox.TraverseUtil.isHidden = function(node) {
  97   if (node instanceof HTMLElement &&
  98       node.getAttribute('aria-hidden') == 'true') {
  99     return true;
 100   }
 101   switch (node.tagName) {
 102     case 'SCRIPT':
 103     case 'NOSCRIPT':
 104       return true;
 105   }
 106   return false;
 107 };
 108
 109 /**
 110  * Moves the cursor forwards until it has crossed exactly one character.
 111  * @param {cvox.Cursor} cursor The cursor location where the search should
 112  *     start.  On exit, the cursor will be immediately to the right of the
 113  *     character returned.
 114  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 115  * @param {Array<Element>} elementsLeft Any HTML elements left.
 116  * @return {?string} The character found, or null if the bottom of the
 117  *     document has been reached.
 118  */
 119 cvox.TraverseUtil.forwardsChar = function(
 120     cursor, elementsEntered, elementsLeft) {
 121   while (true) {
 122     // Move down until we get to a leaf node.
 123     var childNode = null;
 124     if (!cvox.TraverseUtil.treatAsLeafNode(cursor.node)) {
 125       for (var i = cursor.index; i < cursor.node.childNodes.length; i++) {
 126         var node = cursor.node.childNodes[i];
 127         if (cvox.TraverseUtil.isHidden(node)) {
 128           if (node instanceof HTMLElement) {
 129             elementsEntered.push(node);
 130           }
 131           continue;
 132         }
 133         if (cvox.DomUtil.isVisible(node, {checkAncestors: false})) {
 134           childNode = node;
 135           break;
 136         }
 137       }
 138     }
 139     if (childNode) {
 140       cursor.node = childNode;
 141       cursor.index = 0;
 142       cursor.text = cvox.TraverseUtil.getNodeText(cursor.node);
 143       if (cursor.node instanceof HTMLElement) {
 144         elementsEntered.push(cursor.node);
 145       }
 146       continue;
 147     }
 148
 149     // Return the next character from this leaf node.
 150     if (cursor.index < cursor.text.length)
 151       return cursor.text[cursor.index++];
 152
 153     // Move to the next sibling, going up the tree as necessary.
 154     while (cursor.node != null) {
 155       // Try to move to the next sibling.
 156       var siblingNode = null;
 157       for (var node = cursor.node.nextSibling;
 158            node != null;
 159            node = node.nextSibling) {
 160         if (cvox.TraverseUtil.isHidden(node)) {
 161           if (node instanceof HTMLElement) {
 162             elementsEntered.push(node);
 163           }
 164           continue;
 165         }
 166         if (cvox.DomUtil.isVisible(node, {checkAncestors: false})) {
 167           siblingNode = node;
 168           break;
 169         }
 170       }
 171       if (siblingNode) {
 172         if (cursor.node instanceof HTMLElement) {
 173           elementsLeft.push(cursor.node);
 174         }
 175
 176         cursor.node = siblingNode;
 177         cursor.text = cvox.TraverseUtil.getNodeText(siblingNode);
 178         cursor.index = 0;
 179
 180         if (cursor.node instanceof HTMLElement) {
 181           elementsEntered.push(cursor.node);
 182         }
 183
 184         break;
 185       }
 186
 187       // Otherwise, move to the parent.
 188       if (cursor.node.parentNode &&
 189           cursor.node.parentNode.constructor != HTMLBodyElement) {
 190         if (cursor.node instanceof HTMLElement) {
 191           elementsLeft.push(cursor.node);
 192         }
 193         cursor.node = cursor.node.parentNode;
 194         cursor.text = null;
 195         cursor.index = 0;
 196       } else {
 197         return null;
 198       }
 199     }
 200   }
 201 };
 202
 203 /**
 204  * Moves the cursor backwards until it has crossed exactly one character.
 205  * @param {cvox.Cursor} cursor The cursor location where the search should
 206  *     start.  On exit, the cursor will be immediately to the left of the
 207  *     character returned.
 208  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 209  * @param {Array<Element>} elementsLeft Any HTML elements left.
 210  * @return {?string} The previous character, or null if the top of the
 211  *     document has been reached.
 212  */
 213 cvox.TraverseUtil.backwardsChar = function(
 214     cursor, elementsEntered, elementsLeft) {
 215   while (true) {
 216     // Move down until we get to a leaf node.
 217     var childNode = null;
 218     if (!cvox.TraverseUtil.treatAsLeafNode(cursor.node)) {
 219       for (var i = cursor.index - 1; i >= 0; i--) {
 220         var node = cursor.node.childNodes[i];
 221         if (cvox.TraverseUtil.isHidden(node)) {
 222           if (node instanceof HTMLElement) {
 223             elementsEntered.push(node);
 224           }
 225           continue;
 226         }
 227         if (cvox.DomUtil.isVisible(node, {checkAncestors: false})) {
 228           childNode = node;
 229           break;
 230         }
 231       }
 232     }
 233     if (childNode) {
 234       cursor.node = childNode;
 235       cursor.text = cvox.TraverseUtil.getNodeText(cursor.node);
 236       if (cursor.text.length)
 237         cursor.index = cursor.text.length;
 238       else
 239         cursor.index = cursor.node.childNodes.length;
 240       if (cursor.node instanceof HTMLElement) {
 241         elementsEntered.push(cursor.node);
 242       }
 243       continue;
 244     }
 245
 246     // Return the previous character from this leaf node.
 247     if (cursor.text.length > 0 && cursor.index > 0) {
 248       return cursor.text[--cursor.index];
 249     }
 250
 251     // Move to the previous sibling, going up the tree as necessary.
 252     while (true) {
 253       // Try to move to the previous sibling.
 254       var siblingNode = null;
 255       for (var node = cursor.node.previousSibling;
 256            node != null;
 257            node = node.previousSibling) {
 258         if (cvox.TraverseUtil.isHidden(node)) {
 259           if (node instanceof HTMLElement) {
 260             elementsEntered.push(node);
 261           }
 262           continue;
 263         }
 264         if (cvox.DomUtil.isVisible(node, {checkAncestors: false})) {
 265           siblingNode = node;
 266           break;
 267         }
 268       }
 269       if (siblingNode) {
 270         if (cursor.node instanceof HTMLElement) {
 271           elementsLeft.push(cursor.node);
 272         }
 273
 274         cursor.node = siblingNode;
 275         cursor.text = cvox.TraverseUtil.getNodeText(siblingNode);
 276         if (cursor.text.length)
 277           cursor.index = cursor.text.length;
 278         else
 279           cursor.index = cursor.node.childNodes.length;
 280
 281         if (cursor.node instanceof HTMLElement) {
 282           elementsEntered.push(cursor.node);
 283         }
 284         break;
 285       }
 286
 287       // Otherwise, move to the parent.
 288       if (cursor.node.parentNode &&
 289           cursor.node.parentNode.constructor != HTMLBodyElement) {
 290         if (cursor.node instanceof HTMLElement) {
 291           elementsLeft.push(cursor.node);
 292         }
 293         cursor.node = cursor.node.parentNode;
 294         cursor.text = null;
 295         cursor.index = 0;
 296       } else {
 297         return null;
 298       }
 299     }
 300   }
 301 };
 302
 303 /**
 304  * Finds the next character, starting from endCursor.  Upon exit, startCursor
 305  * and endCursor will surround the next character. If skipWhitespace is
 306  * true, will skip until a real character is found. Otherwise, it will
 307  * attempt to select all of the whitespace between the initial position
 308  * of endCursor and the next non-whitespace character.
 309  * @param {!cvox.Cursor} startCursor On exit, points to the position before
 310  *     the char.
 311  * @param {!cvox.Cursor} endCursor The position to start searching for the next
 312  *     char.  On exit, will point to the position past the char.
 313  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 314  * @param {Array<Element>} elementsLeft Any HTML elements left.
 315  *     initial and final cursor position will be pushed onto this array.
 316  * @param {boolean} skipWhitespace If true, will keep scanning until a
 317  *     non-whitespace character is found.
 318  * @return {?string} The next char, or null if the bottom of the
 319  *     document has been reached.
 320  */
 321 cvox.TraverseUtil.getNextChar = function(
 322     startCursor, endCursor, elementsEntered, elementsLeft, skipWhitespace) {
 323
 324   // Save the starting position and get the first character.
 325   startCursor.copyFrom(endCursor);
 326   var c = cvox.TraverseUtil.forwardsChar(
 327       endCursor, elementsEntered, elementsLeft);
 328   if (c == null)
 329     return null;
 330
 331   // Keep track of whether the first character was whitespace.
 332   var initialWhitespace = cvox.TraverseUtil.isWhitespace(c);
 333
 334   // Keep scanning until we find a non-whitespace or non-skipped character.
 335   while ((cvox.TraverseUtil.isWhitespace(c)) ||
 336       (cvox.TraverseUtil.isHidden(endCursor.node))) {
 337     c = cvox.TraverseUtil.forwardsChar(
 338         endCursor, elementsEntered, elementsLeft);
 339     if (c == null)
 340       return null;
 341   }
 342   if (skipWhitespace || !initialWhitespace) {
 343     // If skipWhitepace is true, or if the first character we encountered
 344     // was not whitespace, return that non-whitespace character.
 345     startCursor.copyFrom(endCursor);
 346     startCursor.index--;
 347     return c;
 348   }
 349   else {
 350     for (var i = 0; i < elementsEntered.length; i++) {
 351       if (cvox.TraverseUtil.isHidden(elementsEntered[i])) {
 352         // We need to make sure that startCursor and endCursor aren't
 353         // surrounding a skippable node.
 354         endCursor.index--;
 355         startCursor.copyFrom(endCursor);
 356         startCursor.index--;
 357         return ' ';
 358       }
 359     }
 360     // Otherwise, return all of the whitespace before that last character.
 361     endCursor.index--;
 362     return ' ';
 363   }
 364 };
 365
 366 /**
 367  * Finds the previous character, starting from startCursor.  Upon exit,
 368  * startCursor and endCursor will surround the previous character.
 369  * If skipWhitespace is true, will skip until a real character is found.
 370  * Otherwise, it will attempt to select all of the whitespace between
 371  * the initial position of endCursor and the next non-whitespace character.
 372  * @param {!cvox.Cursor} startCursor The position to start searching for the
 373  *     char. On exit, will point to the position before the char.
 374  * @param {!cvox.Cursor} endCursor The position to start searching for the next
 375  *     char. On exit, will point to the position past the char.
 376  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 377  * @param {Array<Element>} elementsLeft Any HTML elements left.
 378  *     initial and final cursor position will be pushed onto this array.
 379  * @param {boolean} skipWhitespace If true, will keep scanning until a
 380  *     non-whitespace character is found.
 381  * @return {?string} The previous char, or null if the top of the
 382  *     document has been reached.
 383  */
 384 cvox.TraverseUtil.getPreviousChar = function(
 385     startCursor, endCursor, elementsEntered, elementsLeft, skipWhitespace) {
 386
 387   // Save the starting position and get the first character.
 388   endCursor.copyFrom(startCursor);
 389   var c = cvox.TraverseUtil.backwardsChar(
 390       startCursor, elementsEntered, elementsLeft);
 391   if (c == null)
 392     return null;
 393
 394   // Keep track of whether the first character was whitespace.
 395   var initialWhitespace = cvox.TraverseUtil.isWhitespace(c);
 396
 397   // Keep scanning until we find a non-whitespace or non-skipped character.
 398   while ((cvox.TraverseUtil.isWhitespace(c)) ||
 399       (cvox.TraverseUtil.isHidden(startCursor.node))) {
 400     c = cvox.TraverseUtil.backwardsChar(
 401         startCursor, elementsEntered, elementsLeft);
 402     if (c == null)
 403       return null;
 404   }
 405   if (skipWhitespace || !initialWhitespace) {
 406     // If skipWhitepace is true, or if the first character we encountered
 407     // was not whitespace, return that non-whitespace character.
 408     endCursor.copyFrom(startCursor);
 409     endCursor.index++;
 410     return c;
 411   } else {
 412     for (var i = 0; i < elementsEntered.length; i++) {
 413       if (cvox.TraverseUtil.isHidden(elementsEntered[i])) {
 414         startCursor.index++;
 415         endCursor.copyFrom(startCursor);
 416         endCursor.index++;
 417         return ' ';
 418       }
 419     }
 420     // Otherwise, return all of the whitespace before that last character.
 421     startCursor.index++;
 422     return ' ';
 423   }
 424 };
 425
 426 /**
 427  * Finds the next word, starting from endCursor.  Upon exit, startCursor
 428  * and endCursor will surround the next word.  A word is defined to be
 429  * a string of 1 or more non-whitespace characters in the same DOM node.
 430  * @param {cvox.Cursor} startCursor On exit, will point to the beginning of the
 431  *     word returned.
 432  * @param {cvox.Cursor} endCursor The position to start searching for the next
 433  *     word.  On exit, will point to the end of the word returned.
 434  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 435  * @param {Array<Element>} elementsLeft Any HTML elements left.
 436  * @return {?string} The next word, or null if the bottom of the
 437  *     document has been reached.
 438  */
 439 cvox.TraverseUtil.getNextWord = function(startCursor, endCursor,
 440     elementsEntered, elementsLeft) {
 441
 442   // Find the first non-whitespace or non-skipped character.
 443   var cursor = endCursor.clone();
 444   var c = cvox.TraverseUtil.forwardsChar(cursor, elementsEntered, elementsLeft);
 445   if (c == null)
 446     return null;
 447   while ((cvox.TraverseUtil.isWhitespace(c)) ||
 448       (cvox.TraverseUtil.isHidden(cursor.node))) {
 449     c = cvox.TraverseUtil.forwardsChar(cursor, elementsEntered, elementsLeft);
 450     if (c == null)
 451       return null;
 452   }
 453
 454   // Set startCursor to the position immediately before the first
 455   // character in our word. It's safe to decrement |index| because
 456   // forwardsChar guarantees that the cursor will be immediately to the
 457   // right of the returned character on exit.
 458   startCursor.copyFrom(cursor);
 459   startCursor.index--;
 460
 461   // Keep building up our word until we reach a whitespace character or
 462   // would cross a tag.  Don't actually return any tags crossed, because this
 463   // word goes up until the tag boundary but not past it.
 464   endCursor.copyFrom(cursor);
 465   var word = c;
 466   var newEntered = [];
 467   var newLeft = [];
 468   c = cvox.TraverseUtil.forwardsChar(cursor, newEntered, newLeft);
 469   if (c == null) {
 470     return word;
 471   }
 472   while (!cvox.TraverseUtil.isWhitespace(c) &&
 473          newEntered.length == 0 &&
 474          newLeft == 0) {
 475     word += c;
 476     endCursor.copyFrom(cursor);
 477     c = cvox.TraverseUtil.forwardsChar(cursor, newEntered, newLeft);
 478     if (c == null) {
 479       return word;
 480     }
 481   }
 482
 483   return word;
 484 };
 485
 486 /**
 487  * Finds the previous word, starting from startCursor.  Upon exit, startCursor
 488  * and endCursor will surround the previous word.  A word is defined to be
 489  * a string of 1 or more non-whitespace characters in the same DOM node.
 490  * @param {cvox.Cursor} startCursor The position to start searching for the
 491  *     previous word.  On exit, will point to the beginning of the
 492  *     word returned.
 493  * @param {cvox.Cursor} endCursor On exit, will point to the end of the
 494  *     word returned.
 495  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 496  * @param {Array<Element>} elementsLeft Any HTML elements left.
 497  * @return {?string} The previous word, or null if the bottom of the
 498  *     document has been reached.
 499  */
 500 cvox.TraverseUtil.getPreviousWord = function(startCursor, endCursor,
 501     elementsEntered, elementsLeft) {
 502   // Find the first non-whitespace or non-skipped character.
 503   var cursor = startCursor.clone();
 504   var c = cvox.TraverseUtil.backwardsChar(
 505       cursor, elementsEntered, elementsLeft);
 506   if (c == null)
 507     return null;
 508   while ((cvox.TraverseUtil.isWhitespace(c) ||
 509       (cvox.TraverseUtil.isHidden(cursor.node)))) {
 510     c = cvox.TraverseUtil.backwardsChar(cursor, elementsEntered, elementsLeft);
 511     if (c == null)
 512       return null;
 513   }
 514
 515   // Set endCursor to the position immediately after the first
 516   // character we've found (the last character of the word, since we're
 517   // searching backwards).
 518   endCursor.copyFrom(cursor);
 519   endCursor.index++;
 520
 521   // Keep building up our word until we reach a whitespace character or
 522   // would cross a tag.  Don't actually return any tags crossed, because this
 523   // word goes up until the tag boundary but not past it.
 524   startCursor.copyFrom(cursor);
 525   var word = c;
 526   var newEntered = [];
 527   var newLeft = [];
 528   c = cvox.TraverseUtil.backwardsChar(cursor, newEntered, newLeft);
 529   if (c == null)
 530     return word;
 531   while (!cvox.TraverseUtil.isWhitespace(c) &&
 532          newEntered.length == 0 &&
 533          newLeft.length == 0) {
 534     word = c + word;
 535     startCursor.copyFrom(cursor);
 536
 537     c = cvox.TraverseUtil.backwardsChar(cursor, newEntered, newLeft);
 538     if (c == null)
 539       return word;
 540   }
 541
 542   return word;
 543 };
 544
 545
 546 /**
 547  * Given elements entered and left, and break tags, returns true if the
 548  *     current word should break.
 549  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 550  * @param {Array<Element>} elementsLeft Any HTML elements left.
 551  * @param {Object<boolean>} breakTags Associative array of tags that should
 552  *     break.
 553  * @return {boolean} True if elementsEntered or elementsLeft include an
 554  *     element with one of these tags.
 555  */
 556 cvox.TraverseUtil.includesBreakTagOrSkippedNode = function(
 557     elementsEntered, elementsLeft, breakTags) {
 558   for (var i = 0; i < elementsEntered.length; i++) {
 559     if (cvox.TraverseUtil.isHidden(elementsEntered[i])) {
 560       return true;
 561     }
 562     var style = window.getComputedStyle(elementsEntered[i], null);
 563     if ((style && style.display != 'inline') ||
 564         breakTags[elementsEntered[i].tagName]) {
 565       return true;
 566     }
 567   }
 568   for (i = 0; i < elementsLeft.length; i++) {
 569     var style = window.getComputedStyle(elementsLeft[i], null);
 570     if ((style && style.display != 'inline') ||
 571         breakTags[elementsLeft[i].tagName]) {
 572       return true;
 573     }
 574   }
 575   return false;
 576 };
 577
 578
 579 /**
 580  * Finds the next sentence, starting from endCursor.  Upon exit,
 581  * startCursor and endCursor will surround the next sentence.
 582  *
 583  * @param {cvox.Cursor} startCursor On exit, marks the beginning of the
 584  *     sentence.
 585  * @param {cvox.Cursor} endCursor The position to start searching for the next
 586  *     sentence.  On exit, will point to the end of the returned string.
 587  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 588  * @param {Array<Element>} elementsLeft Any HTML elements left.
 589  * @param {Object<boolean>} breakTags Associative array of tags that should
 590  *     break the sentence.
 591  * @return {?string} The next sentence, or null if the bottom of the
 592  *     document has been reached.
 593  */
 594 cvox.TraverseUtil.getNextSentence = function(
 595     startCursor, endCursor, elementsEntered, elementsLeft, breakTags) {
 596   return cvox.TraverseUtil.getNextString(
 597       startCursor, endCursor, elementsEntered, elementsLeft,
 598       function(str, word, elementsEntered, elementsLeft) {
 599         if (str.substr(-1) == '.')
 600           return true;
 601         return cvox.TraverseUtil.includesBreakTagOrSkippedNode(
 602             elementsEntered, elementsLeft, breakTags);
 603       });
 604 };
 605
 606 /**
 607  * Finds the previous sentence, starting from startCursor.  Upon exit,
 608  * startCursor and endCursor will surround the previous sentence.
 609  *
 610  * @param {cvox.Cursor} startCursor The position to start searching for the next
 611  *     sentence.  On exit, will point to the start of the returned string.
 612  * @param {cvox.Cursor} endCursor On exit, the end of the returned string.
 613  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 614  * @param {Array<Element>} elementsLeft Any HTML elements left.
 615  * @param {Object<boolean>} breakTags Associative array of tags that should
 616  *     break the sentence.
 617  * @return {?string} The previous sentence, or null if the bottom of the
 618  *     document has been reached.
 619  */
 620 cvox.TraverseUtil.getPreviousSentence = function(
 621     startCursor, endCursor, elementsEntered, elementsLeft, breakTags) {
 622   return cvox.TraverseUtil.getPreviousString(
 623       startCursor, endCursor, elementsEntered, elementsLeft,
 624       function(str, word, elementsEntered, elementsLeft) {
 625         if (word.substr(-1) == '.')
 626           return true;
 627         return cvox.TraverseUtil.includesBreakTagOrSkippedNode(
 628             elementsEntered, elementsLeft, breakTags);
 629       });
 630 };
 631
 632 /**
 633  * Finds the next line, starting from endCursor.  Upon exit,
 634  * startCursor and endCursor will surround the next line.
 635  *
 636  * @param {cvox.Cursor} startCursor On exit, marks the beginning of the line.
 637  * @param {cvox.Cursor} endCursor The position to start searching for the next
 638  *     line.  On exit, will point to the end of the returned string.
 639  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 640  * @param {Array<Element>} elementsLeft Any HTML elements left.
 641  * @param {Object<boolean>} breakTags Associative array of tags that should
 642  *     break the line.
 643  * @return {?string} The next line, or null if the bottom of the
 644  *     document has been reached.
 645  */
 646 cvox.TraverseUtil.getNextLine = function(
 647     startCursor, endCursor, elementsEntered, elementsLeft, breakTags) {
 648   var range = document.createRange();
 649   var currentRect = null;
 650   var rightMostRect = null;
 651   var prevCursor = endCursor.clone();
 652  return cvox.TraverseUtil.getNextString(
 653       startCursor, endCursor, elementsEntered, elementsLeft,
 654       function(str, word, elementsEntered, elementsLeft) {
 655         range.setStart(startCursor.node, startCursor.index);
 656         range.setEnd(endCursor.node, endCursor.index);
 657         var currentRect = range.getBoundingClientRect();
 658         if (!rightMostRect) {
 659           rightMostRect = currentRect;
 660         }
 661
 662         // Break at new lines except when within a link.
 663         if (currentRect.bottom != rightMostRect.bottom &&
 664             !cvox.DomPredicates.linkPredicate(cvox.DomUtil.getAncestors(
 665                 endCursor.node))) {
 666           endCursor.copyFrom(prevCursor);
 667           return true;
 668         }
 669
 670         rightMostRect = currentRect;
 671         prevCursor.copyFrom(endCursor);
 672
 673         return cvox.TraverseUtil.includesBreakTagOrSkippedNode(
 674             elementsEntered, elementsLeft, breakTags);
 675       });
 676 };
 677
 678 /**
 679  * Finds the previous line, starting from startCursor.  Upon exit,
 680  * startCursor and endCursor will surround the previous line.
 681  *
 682  * @param {cvox.Cursor} startCursor The position to start searching for the next
 683  *     line.  On exit, will point to the start of the returned string.
 684  * @param {cvox.Cursor} endCursor On exit, the end of the returned string.
 685  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 686  * @param {Array<Element>} elementsLeft Any HTML elements left.
 687  * @param {Object<boolean>} breakTags Associative array of tags that should
 688  *     break the line.
 689  * @return {?string} The previous line, or null if the bottom of the
 690  *     document has been reached.
 691  */
 692 cvox.TraverseUtil.getPreviousLine = function(
 693     startCursor, endCursor, elementsEntered, elementsLeft, breakTags) {
 694   var range = document.createRange();
 695   var currentRect = null;
 696   var leftMostRect = null;
 697   var prevCursor = startCursor.clone();
 698   return cvox.TraverseUtil.getPreviousString(
 699       startCursor, endCursor, elementsEntered, elementsLeft,
 700       function(str, word, elementsEntered, elementsLeft) {
 701         range.setStart(startCursor.node, startCursor.index);
 702         range.setEnd(endCursor.node, endCursor.index);
 703         var currentRect = range.getBoundingClientRect();
 704         if (!leftMostRect) {
 705           leftMostRect = currentRect;
 706         }
 707
 708         // Break at new lines except when within a link.
 709         if (currentRect.top != leftMostRect.top &&
 710             !cvox.DomPredicates.linkPredicate(cvox.DomUtil.getAncestors(
 711                 startCursor.node))) {
 712           startCursor.copyFrom(prevCursor);
 713           return true;
 714         }
 715
 716         leftMostRect = currentRect;
 717         prevCursor.copyFrom(startCursor);
 718
 719         return cvox.TraverseUtil.includesBreakTagOrSkippedNode(
 720             elementsEntered, elementsLeft, breakTags);
 721       });
 722 };
 723
 724 /**
 725  * Finds the next paragraph, starting from endCursor.  Upon exit,
 726  * startCursor and endCursor will surround the next paragraph.
 727  *
 728  * @param {cvox.Cursor} startCursor On exit, marks the beginning of the
 729  *     paragraph.
 730  * @param {cvox.Cursor} endCursor The position to start searching for the next
 731  *     paragraph.  On exit, will point to the end of the returned string.
 732  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 733  * @param {Array<Element>} elementsLeft Any HTML elements left.
 734  * @return {?string} The next paragraph, or null if the bottom of the
 735  *     document has been reached.
 736  */
 737 cvox.TraverseUtil.getNextParagraph = function(startCursor, endCursor,
 738     elementsEntered, elementsLeft) {
 739   return cvox.TraverseUtil.getNextString(
 740       startCursor, endCursor, elementsEntered, elementsLeft,
 741       function(str, word, elementsEntered, elementsLeft) {
 742         for (var i = 0; i < elementsEntered.length; i++) {
 743           if (cvox.TraverseUtil.isHidden(elementsEntered[i])) {
 744             return true;
 745           }
 746           var style = window.getComputedStyle(elementsEntered[i], null);
 747           if (style && style.display != 'inline') {
 748             return true;
 749           }
 750         }
 751         for (i = 0; i < elementsLeft.length; i++) {
 752           var style = window.getComputedStyle(elementsLeft[i], null);
 753           if (style && style.display != 'inline') {
 754             return true;
 755           }
 756         }
 757         return false;
 758       });
 759 };
 760
 761 /**
 762  * Finds the previous paragraph, starting from startCursor.  Upon exit,
 763  * startCursor and endCursor will surround the previous paragraph.
 764  *
 765  * @param {cvox.Cursor} startCursor The position to start searching for the next
 766  *     paragraph.  On exit, will point to the start of the returned string.
 767  * @param {cvox.Cursor} endCursor On exit, the end of the returned string.
 768  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 769  * @param {Array<Element>} elementsLeft Any HTML elements left.
 770  * @return {?string} The previous paragraph, or null if the bottom of the
 771  *     document has been reached.
 772  */
 773 cvox.TraverseUtil.getPreviousParagraph = function(
 774     startCursor, endCursor, elementsEntered, elementsLeft) {
 775   return cvox.TraverseUtil.getPreviousString(
 776       startCursor, endCursor, elementsEntered, elementsLeft,
 777       function(str, word, elementsEntered, elementsLeft) {
 778         for (var i = 0; i < elementsEntered.length; i++) {
 779           if (cvox.TraverseUtil.isHidden(elementsEntered[i])) {
 780             return true;
 781           }
 782           var style = window.getComputedStyle(elementsEntered[i], null);
 783           if (style && style.display != 'inline') {
 784             return true;
 785           }
 786         }
 787         for (i = 0; i < elementsLeft.length; i++) {
 788           var style = window.getComputedStyle(elementsLeft[i], null);
 789           if (style && style.display != 'inline') {
 790             return true;
 791           }
 792         }
 793         return false;
 794       });
 795 };
 796
 797 /**
 798  * Customizable function to return the next string of words in the DOM, based
 799  * on provided functions to decide when to break one string and start
 800  * the next. This can be used to get the next sentence, line, paragraph,
 801  * or potentially other granularities.
 802  *
 803  * Finds the next contiguous string, starting from endCursor.  Upon exit,
 804  * startCursor and endCursor will surround the next string.
 805  *
 806  * The breakBefore function takes four parameters, and
 807  * should return true if the string should be broken before the proposed
 808  * next word:
 809  *   str The string so far.
 810  *   word The next word to be added.
 811  *   elementsEntered The elements entered in reaching this next word.
 812  *   elementsLeft The elements left in reaching this next word.
 813  *
 814  * @param {cvox.Cursor} startCursor On exit, will point to the beginning of the
 815  *     next string.
 816  * @param {cvox.Cursor} endCursor The position to start searching for the next
 817  *     string.  On exit, will point to the end of the returned string.
 818  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 819  * @param {Array<Element>} elementsLeft Any HTML elements left.
 820  * @param {function(string, string, Array<Element>, Array<Element>)}
 821  *     breakBefore Function that takes the string so far, next word to be
 822  *     added, and elements entered and left, and returns true if the string
 823  *     should be ended before adding this word.
 824  * @return {?string} The next string, or null if the bottom of the
 825  *     document has been reached.
 826  */
 827 cvox.TraverseUtil.getNextString = function(
 828     startCursor, endCursor, elementsEntered, elementsLeft, breakBefore) {
 829   // Get the first word and set the start cursor to the start of the
 830   // first word.
 831   var wordStartCursor = endCursor.clone();
 832   var wordEndCursor = endCursor.clone();
 833   var newEntered = [];
 834   var newLeft = [];
 835   var str = '';
 836   var word = cvox.TraverseUtil.getNextWord(
 837       wordStartCursor, wordEndCursor, newEntered, newLeft);
 838   if (word == null)
 839     return null;
 840   startCursor.copyFrom(wordStartCursor);
 841
 842   // Always add the first word when the string is empty, and then keep
 843   // adding more words as long as breakBefore returns false
 844   while (!str || !breakBefore(str, word, newEntered, newLeft)) {
 845     // Append this word, set the end cursor to the end of this word, and
 846     // update the returned list of nodes crossed to include ones we crossed
 847     // in reaching this word.
 848     if (str)
 849       str += ' ';
 850     str += word;
 851     elementsEntered = elementsEntered.concat(newEntered);
 852     elementsLeft = elementsLeft.concat(newLeft);
 853     endCursor.copyFrom(wordEndCursor);
 854
 855     // Get the next word and go back to the top of the loop.
 856     newEntered = [];
 857     newLeft = [];
 858     word = cvox.TraverseUtil.getNextWord(
 859         wordStartCursor, wordEndCursor, newEntered, newLeft);
 860     if (word == null)
 861       return str;
 862   }
 863
 864   return str;
 865 };
 866
 867 /**
 868  * Customizable function to return the previous string of words in the DOM,
 869  * based on provided functions to decide when to break one string and start
 870  * the next. See getNextString, above, for more details.
 871  *
 872  * Finds the previous contiguous string, starting from startCursor.  Upon exit,
 873  * startCursor and endCursor will surround the next string.
 874  *
 875  * @param {cvox.Cursor} startCursor The position to start searching for the
 876  *     previous string.  On exit, will point to the beginning of the
 877  *     string returned.
 878  * @param {cvox.Cursor} endCursor On exit, will point to the end of the
 879  *     string returned.
 880  * @param {Array<Element>} elementsEntered Any HTML elements entered.
 881  * @param {Array<Element>} elementsLeft Any HTML elements left.
 882  * @param {function(string, string, Array<Element>, Array<Element>)}
 883  *     breakBefore Function that takes the string so far, the word to be
 884  *     added, and nodes crossed, and returns true if the string should be
 885  *     ended before adding this word.
 886  * @return {?string} The next string, or null if the top of the
 887  *     document has been reached.
 888  */
 889 cvox.TraverseUtil.getPreviousString = function(
 890     startCursor, endCursor, elementsEntered, elementsLeft, breakBefore) {
 891   // Get the first word and set the end cursor to the end of the
 892   // first word.
 893   var wordStartCursor = startCursor.clone();
 894   var wordEndCursor = startCursor.clone();
 895   var newEntered = [];
 896   var newLeft = [];
 897   var str = '';
 898   var word = cvox.TraverseUtil.getPreviousWord(
 899       wordStartCursor, wordEndCursor, newEntered, newLeft);
 900   if (word == null)
 901     return null;
 902   endCursor.copyFrom(wordEndCursor);
 903
 904   // Always add the first word when the string is empty, and then keep
 905   // adding more words as long as breakBefore returns false
 906   while (!str || !breakBefore(str, word, newEntered, newLeft)) {
 907     // Prepend this word, set the start cursor to the start of this word, and
 908     // update the returned list of nodes crossed to include ones we crossed
 909     // in reaching this word.
 910     if (str)
 911       str = ' ' + str;
 912     str = word + str;
 913     elementsEntered = elementsEntered.concat(newEntered);
 914     elementsLeft = elementsLeft.concat(newLeft);
 915     startCursor.copyFrom(wordStartCursor);
 916
 917     // Get the previous word and go back to the top of the loop.
 918     newEntered = [];
 919     newLeft = [];
 920     word = cvox.TraverseUtil.getPreviousWord(
 921         wordStartCursor, wordEndCursor, newEntered, newLeft);
 922     if (word == null)
 923       return str;
 924   }
 925
 926   return str;
 927 };