ui/accessibility/extensions/caretbrowsing/traverse_util.js

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