text: // Copyright 2012 Google Inc.
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  //      http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  
  /**
   * @fileoverview Caret browsing content script, runs in each frame.
   *
   * The behavior is based on Mozilla's spec whenever possible:
   *   http://www.mozilla.org/access/keyboard/proposal
   *
   * The one exception is that Esc is used to escape out of a form control,
   * rather than their proposed key (which doesn't seem to work in the
   * latest Firefox anyway).
   *
   * Some details about how WebKit selection works, which will help in
   * understanding the code:
   *
   * The Selection object (window.getSelection()) has four components that
   * completely describe the state of the caret or selection:
   *
   * base and anchor: this is the start of the selection, the fixed point.
   * extent and focus: this is the end of the selection, the part that
   *     moves when you hold down shift and press the left or right arrows.
   *
   * When the selection is a cursor, the base, anchor, extent, and focus are
   * all the same.
   *
   * There's only one time when the base and anchor are not the same, or the
   * extent and focus are not the same, and that's when the selection is in
   * an ambiguous state - i.e. it's not clear which edge is the focus and which
   * is the anchor. As an example, if you double-click to select a word, then
   * the behavior is dependent on your next action. If you press Shift+Right,
   * the right edge becomes the focus. But if you press Shift+Left, the left
   * edge becomes the focus.
   *
   * When the selection is in an ambiguous state, the base and extent are set
   * to the position where the mouse clicked, and the anchor and focus are set
   * to the boundaries of the selection.
   *
   * The only way to set the selection and give it direction is to use
   * the non-standard Selection.setBaseAndExtent method. If you try to use
   * Selection.addRange(), the anchor will always be on the left and the focus
   * will always be on the right, making it impossible to manipulate
   * selections that move from right to left.
   *
   * Finally, WebKit will throw an exception if you try to set an invalid
   * selection - a selection where the left and right edges are not the same,
   * but it doesn't span any visible characters. A common example is that
   * there are often many whitespace characters in the DOM that are not
   * visible on the page; trying to select them will fail. Another example is
   * any node that's invisible or not displayed.
   *
   * While there are probably many possible methods to determine what is
   * selectable, this code uses the method of determining if there's a valid
   * bounding box for the range or not - keep moving the cursor forwards until
   * the range from the previous position and candidate next position has a
   * valid bounding box.
   *
   * @author dmazzoni@google.com (Dominic Mazzoni)
   */
  
  goog.provide('CaretBrowsing');
  
  goog.require('cvox.Cursor');
  goog.require('cvox.DomUtil');
  goog.require('cvox.TraverseUtil');
  
  /**
   * The class handling the Caret Browsing implementation in the page.
   * Installs a keydown listener that always responds to the F7 key,
   * sets up communication with the background page, and then when caret
   * browsing is enabled, response to various key events to move the caret
   * or selection within the text content of the document. Uses the native
   * WebKit selection wherever possible, but displays its own flashing
   * caret using a DIV because there's no native caret available.
   * @constructor
   */
  var CaretBrowsing = function() {};
  
  /**
   * Is caret browsing enabled?
   * @type {boolean}
   */
  CaretBrowsing.isEnabled = false;
  
  /**
   * Is this window / iframe focused? We won't show the caret if not,
   * especially so that carets aren't shown in two iframes of the same
   * tab.
   * @type {boolean}
   */
  CaretBrowsing.isWindowFocused = false;
  
  /**
   * Is the caret actually visible? This is true only if isEnabled and
   * isWindowFocused are both true.
   * @type {boolean}
   */
  CaretBrowsing.isCaretVisible = false;
  
  /**
   * The actual caret element, an absolute-positioned flashing line.
   * @type {Element}
   */
  CaretBrowsing.caretElement;
  
  /**
   * The x-position of the caret, in absolute pixels.
   * @type {number}
   */
  CaretBrowsing.caretX = 0;
  
  /**
   * The y-position of the caret, in absolute pixels.
   * @type {number}
   */
  CaretBrowsing.caretY = 0;
  
  /**
   * The width of the caret in pixels.
   * @type {number}
   */
  CaretBrowsing.caretWidth = 0;
  
  /**
   * The height of the caret in pixels.
   * @type {number}
   */
  CaretBrowsing.caretHeight = 0;
  
  /**
   * Is the selection collapsed, i.e. are the start and end locations
   * the same? If so, our blinking caret image is shown; otherwise
   * the WebKit selection is shown.
   * @type {boolean}
   */
  CaretBrowsing.isSelectionCollapsed = false;
  
  /**
   * The id returned by window.setInterval for our blink function, so
   * we can cancel it when caret browsing is disabled.
   * @type {number?}
   */
  CaretBrowsing.blinkFunctionId = null;
  
  /**
   * The desired x-coordinate to match when moving the caret up and down.
   * To match the behavior as documented in Mozilla's caret browsing spec
   * (http://www.mozilla.org/access/keyboard/proposal), we keep track of the
   * initial x position when the user starts moving the caret up and down,
   * so that the x position doesn't drift as you move throughout lines, but
   * stays as close as possible to the initial position. This is reset when
   * moving left or right or clicking.
   * @type {number?}
   */
  CaretBrowsing.targetX = null;
  
  /**
   * A flag that flips on or off as the caret blinks.
   * @type {boolean}
   */
  CaretBrowsing.blinkFlag = true;
  
  /**
   * Check if a node is a control that normally allows the user to interact
   * with it using arrow keys. We won't override the arrow keys when such a
   * control has focus, the user must press Escape to do caret browsing outside
   * that control.
   * @param {Node} node A node to check.
   * @return {boolean} True if this node is a control that the user can
   *     interact with using arrow keys.
   */
  CaretBrowsing.isControlThatNeedsArrowKeys = function(node) {
    if (!node) {
      return false;
    }
  
    if (node == document.body || node != document.activeElement) {
      return false;
    }
  
    if (node.constructor == HTMLSelectElement) {
      return true;
    }
  
    if (node.constructor == HTMLInputElement) {
      switch (node.type) {
        case 'email':
        case 'number':
        case 'password':
        case 'search':
        case 'text':
        case 'tel':
        case 'url':
        case '':
          return true;  // All of these are text boxes.
        case 'datetime':
        case 'datetime-local':
        case 'date':
        case 'month':
        case 'range':
        case 'week':
          return true;  // These are other input elements that use arrows.
      }
    }
  
    // Handle focusable ARIA controls.
    if (node.getAttribute && cvox.DomUtil.isFocusable(node)) {
      var role = node.getAttribute('role');
      switch (role) {
        case 'combobox':
        case 'grid':
        case 'gridcell':
        case 'listbox':
        case 'menu':
        case 'menubar':
        case 'menuitem':
        case 'menuitemcheckbox':
        case 'menuitemradio':
        case 'option':
        case 'radiogroup':
        case 'scrollbar':
        case 'slider':
        case 'spinbutton':
        case 'tab':
        case 'tablist':
        case 'textbox':
        case 'tree':
        case 'treegrid':
        case 'treeitem':
          return true;
      }
    }
  
    return false;
  };
  
  /**
   * If there's no initial selection, set the cursor just before the
   * first text character in the document.
   */
  CaretBrowsing.setInitialCursor = function() {
    var sel = window.getSelection();
    if (sel.rangeCount > 0) {
      return;
    }
  
    var start = new cvox.Cursor(document.body, 0, '');
    var end = new cvox.Cursor(document.body, 0, '');
    var elementsEntered = [];
    var elementsLeft = [];
    var result = cvox.TraverseUtil.getNextChar(
        start, end, elementsEntered, elementsLeft, true);
    if (result == null) {
      return;
    }
    CaretBrowsing.setAndValidateSelection(start, start);
  };
  
  /**
   * Set focus to a node if it's focusable. If it's an input element,
   * select the text, otherwise it doesn't appear focused to the user.
   * Every other control behaves normally if you just call focus() on it.
   * @param {Node} node The node to focus.
   * @return {boolean} True if the node was focused.
   */
  CaretBrowsing.setFocusToNode = function(node) {
    while (node && node != document.body) {
      if (cvox.DomUtil.isFocusable(node)) {
        node.focus();
        if (node.constructor == HTMLInputElement && node.select) {
          node.select();
        }
        return true;
      }
      node = node.parentNode;
    }
  
    return false;
  };
  
  /**
   * Set focus to the first focusable node in the given list.
   * select the text, otherwise it doesn't appear focused to the user.
   * Every other control behaves normally if you just call focus() on it.
   * @param {Array.<Node>} nodeList An array of nodes to focus.
   * @return {boolean} True if the node was focused.
   */
  CaretBrowsing.setFocusToFirstFocusable = function(nodeList) {
    for (var i = 0; i < nodeList.length; i++) {
      if (CaretBrowsing.setFocusToNode(nodeList[i])) {
        return true;
      }
    }
    return false;
  };
  
  /**
   * Create the caret element. This assumes that caretX, caretY,
   * caretWidth, and caretHeight have all been set. The caret is
   * animated from a larger box to the final cursor location to
   * make it easier for the user to find when it first appears.
   */
  CaretBrowsing.createCaretElement = function() {
    var element = document.createElement('div');
  
    // Constant properties.
    element.style.position = 'absolute';
    element.style.zIndex = 99999;
    element.style.borderLeft = '1px solid #fff';
    element.style.minHeight = '10px';
    var width = CaretBrowsing.caretWidth;
    var height = CaretBrowsing.caretHeight;
  
    // The property that will animate. This is the initial state,
    // just shown transiently.
    element.style.left = (CaretBrowsing.caretX - 50) + 'px';
    element.style.top = (CaretBrowsing.caretY - 100) + 'px';
    element.style.width = (width + 100) + 'px';
    element.style.height = (height + 200) + 'px';
    element.style.backgroundColor = '#f90';
    element.style.opacity = '0.3';
  
    // Tell TraverseUtil not to traverse this node.
    element.setAttribute('aria-hidden', 'true');
  
    // Show it.
    document.body.appendChild(element);
    CaretBrowsing.caretElement = element;
  
    // Start the animation. The setTimeout is so that the old values will get
    // applied first, so we can animate to the new values.
    window.setTimeout(function() {
      // If we have a cursor, this animates into the cursor. If it's a selection,
      // the animation disappears as it becomes the selection.
      element.style.opacity = CaretBrowsing.isSelectionCollapsed ? '1.0' : '0.0';
      element.style.left = CaretBrowsing.caretX + 'px';
      element.style.top = CaretBrowsing.caretY + 'px';
      element.style.width = width + 'px';
      element.style.height = height + 'px';
  
      element.style['-webkit-transition'] = 'all 0.8s ease-in';
      element.style.backgroundColor = '#000';
      function listener() {
        element.removeEventListener(
            'webkitTransitionEnd', listener, false);
        element.style['-webkit-transition'] = 'none';
      }
      element.addEventListener(
          'webkitTransitionEnd', listener, false);
    }, 0);
  };
  
  /**
   * Get the rectangle for a cursor position. This is tricky because
   * you can't get the bounding rectangle of an empty range, so this function
   * computes the rect by trying a range including one character earlier or
   * later than the cursor position.
   * @param {cvox.Cursor} cursor A single cursor position.
   * @return {{left: number, top: number, width: number, height: number}}
   *     The bounding rectangle of the cursor.
   */
  CaretBrowsing.getCursorRect = function(cursor) {
    var node = cursor.node;
    var index = cursor.index;
    var rect = {
      left: 0,
      top: 0,
      width: 1,
      height: 0
    };
    if (node.constructor == Text) {
      var left = index;
      var right = index;
      var max = node.data.length;
      var newRange = document.createRange();
      while (left > 0 || right < max) {
        if (left > 0) {
          left--;
          newRange.setStart(node, left);
          newRange.setEnd(node, index);
          var rangeRect = newRange.getBoundingClientRect();
          if (rangeRect) {
            rect.left = rangeRect.right;
            rect.top = rangeRect.top;
            rect.height = rangeRect.height;
            break;
          }
        }
        if (right < max) {
          right++;
          newRange.setStart(node, index);
          newRange.setEnd(node, right);
          var rangeRect = newRange.getBoundingClientRect();
          if (rangeRect) {
            rect.left = rangeRect.left;
            rect.top = rangeRect.top;
            rect.height = rangeRect.height;
            break;
          }
        }
      }
    } else {
      rect.height = node.offsetHeight;
      while (node !== null) {
        rect.left += node.offsetLeft;
        rect.top += node.offsetTop;
        node = node.offsetParent;
      }
    }
    rect.left += window.pageXOffset;
    rect.top += window.pageYOffset;
    return rect;
  };
  
  /**
   * Compute the new location of the caret or selection and update
   * the element as needed.
   * @param {boolean} scrollToSelection If true, will also scroll the page
   *     to the caret / selection location.
   */
  CaretBrowsing.updateCaretOrSelection = function(scrollToSelection) {
    var sel = window.getSelection();
    if (sel.rangeCount == 0) {
      if (CaretBrowsing.caretElement) {
        CaretBrowsing.isSelectionCollapsed = false;
        CaretBrowsing.caretElement.style.opacity = '0.0';
      }
      return;
    }
  
    var range = sel.getRangeAt(0);
    if (!range) {
      if (CaretBrowsing.caretElement) {
        CaretBrowsing.isSelectionCollapsed = false;
        CaretBrowsing.caretElement.style.opacity = '0.0';
      }
      return;
    }
  
    if (CaretBrowsing.isControlThatNeedsArrowKeys(document.activeElement)) {
      var node = document.activeElement;
      CaretBrowsing.caretWidth = node.offsetWidth;
      CaretBrowsing.caretHeight = node.offsetHeight;
      CaretBrowsing.caretX = 0;
      CaretBrowsing.caretY = 0;
      while (node.offsetParent) {
        CaretBrowsing.caretX += node.offsetLeft;
        CaretBrowsing.caretY += node.offsetTop;
        node = node.offsetParent;
      }
      CaretBrowsing.isSelectionCollapsed = false;
    } else if (range.startOffset != range.endOffset ||
               range.startContainer != range.endContainer) {
      var rect = range.getBoundingClientRect();
      if (!rect) {
        return;
      }
      CaretBrowsing.caretX = rect.left + window.pageXOffset;
      CaretBrowsing.caretY = rect.top + window.pageYOffset;
      CaretBrowsing.caretWidth = rect.width;
      CaretBrowsing.caretHeight = rect.height;
      CaretBrowsing.isSelectionCollapsed = false;
    } else {
      var rect = CaretBrowsing.getCursorRect(
          new cvox.Cursor(range.startContainer,
                          range.startOffset,
                          cvox.TraverseUtil.getNodeText(range.startContainer)));
      CaretBrowsing.caretX = rect.left;
      CaretBrowsing.caretY = rect.top;
      CaretBrowsing.caretWidth = rect.width;
      CaretBrowsing.caretHeight = rect.height;
      CaretBrowsing.isSelectionCollapsed = true;
    }
  
    if (!CaretBrowsing.caretElement) {
      CaretBrowsing.createCaretElement();
    } else {
      var element = CaretBrowsing.caretElement;
      if (CaretBrowsing.isSelectionCollapsed) {
        element.style.opacity = '1.0';
        element.style.left = CaretBrowsing.caretX + 'px';
        element.style.top = CaretBrowsing.caretY + 'px';
        element.style.width = CaretBrowsing.caretWidth + 'px';
        element.style.height = CaretBrowsing.caretHeight + 'px';
      } else {
        element.style.opacity = '0.0';
      }
    }
  
    if (scrollToSelection) {
      // Scroll just to the "focus" position of the selection,
      // the part the user is manipulating.
      var rect = CaretBrowsing.getCursorRect(
          new cvox.Cursor(sel.focusNode, sel.focusOffset,
                          cvox.TraverseUtil.getNodeText(sel.focusNode)));
  
      var yscroll = window.pageYOffset;
      var pageHeight = window.innerHeight;
      var caretY = rect.top;
      var caretHeight = Math.min(rect.height, 30);
      if (yscroll + pageHeight < caretY + caretHeight) {
        window.scroll(0, (caretY + caretHeight - pageHeight + 100));
      } else if (caretY < yscroll) {
        window.scroll(0, (caretY - 100));
      }
    }
  };
  
  /**
   * Return true if the selection directionality is ambiguous, which happens
   * if, for example, the user double-clicks in the middle of a word to select
   * it. In that case, the selection should extend by the right edge if the
   * user presses right, and by the left edge if the user presses left.
   * @param {Selection} sel The selection.
   * @return {boolean} True if the selection directionality is ambiguous.
   */
  CaretBrowsing.isAmbiguous = function(sel) {
    return (sel.anchorNode != sel.baseNode ||
            sel.anchorOffset != sel.baseOffset ||
            sel.focusNode != sel.extentNode ||
            sel.focusOffset != sel.extentOffset);
  };
  
  /**
   * Create a Cursor from the anchor position of the selection, the
   * part that doesn't normally move.
   * @param {Selection} sel The selection.
   * @return {cvox.Cursor} A cursor pointing to the selection's anchor location.
   */
  CaretBrowsing.makeAnchorCursor = function(sel) {
    return new cvox.Cursor(sel.anchorNode, sel.anchorOffset,
                           cvox.TraverseUtil.getNodeText(sel.anchorNode));
  };
  
  /**
   * Create a Cursor from the focus position of the selection.
   * @param {Selection} sel The selection.
   * @return {cvox.Cursor} A cursor pointing to the selection's focus location.
   */
  CaretBrowsing.makeFocusCursor = function(sel) {
    return new cvox.Cursor(sel.focusNode, sel.focusOffset,
                           cvox.TraverseUtil.getNodeText(sel.focusNode));
  };
  
  /**
   * Create a Cursor from the left boundary of the selection - the boundary
   * closer to the start of the document.
   * @param {Selection} sel The selection.
   * @return {cvox.Cursor} A cursor pointing to the selection's left boundary.
   */
  CaretBrowsing.makeLeftCursor = function(sel) {
    var range = sel.rangeCount == 1 ? sel.getRangeAt(0) : null;
    if (range &&
        range.endContainer == sel.anchorNode &&
        range.endOffset == sel.anchorOffset) {
      return CaretBrowsing.makeFocusCursor(sel);
    } else {
      return CaretBrowsing.makeAnchorCursor(sel);
    }
  };
  
  /**
   * Create a Cursor from the right boundary of the selection - the boundary
   * closer to the end of the document.
   * @param {Selection} sel The selection.
   * @return {cvox.Cursor} A cursor pointing to the selection's right boundary.
   */
  CaretBrowsing.makeRightCursor = function(sel) {
    var range = sel.rangeCount == 1 ? sel.getRangeAt(0) : null;
    if (range &&
        range.endContainer == sel.anchorNode &&
        range.endOffset == sel.anchorOffset) {
      return CaretBrowsing.makeAnchorCursor(sel);
    } else {
      return CaretBrowsing.makeFocusCursor(sel);
    }
  };
  
  /**
   * Try to set the window's selection to be between the given start and end
   * cursors, and return whether or not it was successful.
   * @param {cvox.Cursor} start The start position.
   * @param {cvox.Cursor} end The end position.
   * @return {boolean} True if the selection was successfully set.
   */
  CaretBrowsing.setAndValidateSelection = function(start, end) {
    var sel = window.getSelection();
    sel.setBaseAndExtent(start.node, start.index, end.node, end.index);
  
    if (sel.rangeCount != 1) {
      return false;
    }
  
    return (sel.anchorNode == start.node &&
            sel.anchorOffset == start.index &&
            sel.focusNode == end.node &&
            sel.focusOffset == end.index);
  };
  
  /**
   * Note: the built-in WebKit function by the same name is unreliable.
   * @param {Selection} sel The selection.
   * @return {boolean} True if the start and end positions are the same.
   */
  CaretBrowsing.isCollapsed = function(sel) {
    return (sel.anchorOffset == sel.focusOffset &&
            sel.anchorNode == sel.focusNode);
  };
  
  /**
   * Moves the cursor forwards to the next valid position.
   * @param {cvox.Cursor} cursor The current cursor location.
   *     On exit, the cursor will be at the next position.
   * @param {Array.<Element>} elementsEntered Any HTML elements entered.
   * @param {Array.<Element>} elementsLeft Any HTML elements left.
   * @return {?string} The character reached, or null if the bottom of the
   *     document has been reached.
   */
  CaretBrowsing.forwards = function(cursor, elementsEntered, elementsLeft) {
    var previousCursor = cursor.clone();
    var result = cvox.TraverseUtil.forwardsChar(
        cursor, elementsEntered, elementsLeft);
  
    // Work around the fact that TraverseUtil.forwardsChar returns once per
    // char in a block of text, rather than once per possible selection
    // position in a block of text.
    if (result && cursor.node != previousCursor.node && cursor.index > 0) {
      cursor.index = 0;
    }
  
    return result;
  };
  
  /**
   * Moves the cursor backwards to the previous valid position.
   * @param {cvox.Cursor} cursor The current cursor location.
   *     On exit, the cursor will be at the previous position.
   * @param {Array.<Element>} elementsEntered Any HTML elements entered.
   * @param {Array.<Element>} elementsLeft Any HTML elements left.
   * @return {?string} The character reached, or null if the top of the
   *     document has been reached.
   */
  CaretBrowsing.backwards = function(cursor, elementsEntered, elementsLeft) {
    var previousCursor = cursor.clone();
    var result = cvox.TraverseUtil.backwardsChar(
        cursor, elementsEntered, elementsLeft);
  
    // Work around the fact that TraverseUtil.backwardsChar returns once per
    // char in a block of text, rather than once per possible selection
    // position in a block of text.
    if (result &&
        cursor.node != previousCursor.node &&
        cursor.index < cursor.text.length) {
      cursor.index = cursor.text.length;
    }
  
    return result;
  };
  
  /**
   * Called when the user presses the right arrow. If there's a selection,
   * moves the cursor to the end of the selection range. If it's a cursor,
   * moves past one character.
   * @param {Event} evt The DOM event.
   * @return {boolean} True if the default action should be performed.
   */
  CaretBrowsing.moveRight = function(evt) {
    CaretBrowsing.targetX = null;
  
    var sel = window.getSelection();
    if (!evt.shiftKey && !CaretBrowsing.isCollapsed(sel)) {
      var right = CaretBrowsing.makeRightCursor(sel);
      CaretBrowsing.setAndValidateSelection(right, right);
      return false;
    }
  
    var start = CaretBrowsing.isAmbiguous(sel) ?
                CaretBrowsing.makeLeftCursor(sel) :
                CaretBrowsing.makeAnchorCursor(sel);
    var end = CaretBrowsing.isAmbiguous(sel) ?
              CaretBrowsing.makeRightCursor(sel) :
              CaretBrowsing.makeFocusCursor(sel);
    var previousEnd = end.clone();
    var elementsEntered = [];
    var elementsLeft = [];
    while (true) {
      var result;
      if (evt.ctrlKey) {
        result = cvox.TraverseUtil.getNextWord(
            previousEnd, end, elementsEntered, elementsLeft);
      } else {
        previousEnd = end.clone();
        result = CaretBrowsing.forwards(end, elementsEntered, elementsLeft);
      }
  
      if (result === null) {
        break;
      }
  
      if (CaretBrowsing.setAndValidateSelection(
              evt.shiftKey ? start : end, end)) {
        break;
      }
    }
  
    if (!evt.shiftKey) {
      elementsEntered.push(end.node);
      CaretBrowsing.setFocusToFirstFocusable(elementsEntered);
    }
  
    return false;
  };
  
  /**
   * Called when the user presses the left arrow. If there's a selection,
   * moves the cursor to the start of the selection range. If it's a cursor,
   * moves backwards past one character.
   * @param {Event} evt The DOM event.
   * @return {boolean} True if the default action should be performed.
   */
  CaretBrowsing.moveLeft = function(evt) {
    CaretBrowsing.targetX = null;
  
    var sel = window.getSelection();
    if (!evt.shiftKey && !CaretBrowsing.isCollapsed(sel)) {
      var left = CaretBrowsing.makeLeftCursor(sel);
      CaretBrowsing.setAndValidateSelection(left, left);
      return false;
    }
  
    var start = CaretBrowsing.isAmbiguous(sel) ?
                CaretBrowsing.makeLeftCursor(sel) :
                CaretBrowsing.makeFocusCursor(sel);
    var end = CaretBrowsing.isAmbiguous(sel) ?
              CaretBrowsing.makeRightCursor(sel) :
              CaretBrowsing.makeAnchorCursor(sel);
    var previousStart = start.clone();
    var elementsEntered = [];
    var elementsLeft = [];
    while (true) {
      var result;
      if (evt.ctrlKey) {
        result = cvox.TraverseUtil.getPreviousWord(
            start, previousStart, elementsEntered, elementsLeft);
      } else {
        previousStart = start.clone();
        result = CaretBrowsing.backwards(start, elementsEntered, elementsLeft);
      }
  
      if (result === null) {
        break;
      }
  
      if (CaretBrowsing.setAndValidateSelection(
              evt.shiftKey ? end : start, start)) {
        break;
      }
    }
  
    if (!evt.shiftKey) {
      elementsEntered.push(start.node);
      CaretBrowsing.setFocusToFirstFocusable(elementsEntered);
    }
  
    return false;
  };
  
  
  /**
   * Called when the user presses the down arrow. If there's a selection,
   * moves the cursor to the end of the selection range. If it's a cursor,
   * attempts to move to the equivalent horizontal pixel position in the
   * subsequent line of text. If this is impossible, go to the first character
   * of the next line.
   * @param {Event} evt The DOM event.
   * @return {boolean} True if the default action should be performed.
   */
  CaretBrowsing.moveDown = function(evt) {
    var sel = window.getSelection();
    if (!evt.shiftKey && !CaretBrowsing.isCollapsed(sel)) {
      var right = CaretBrowsing.makeRightCursor(sel);
      CaretBrowsing.setAndValidateSelection(right, right);
      return false;
    }
  
    var start = CaretBrowsing.isAmbiguous(sel) ?
                CaretBrowsing.makeLeftCursor(sel) :
                CaretBrowsing.makeAnchorCursor(sel);
    var end = CaretBrowsing.isAmbiguous(sel) ?
              CaretBrowsing.makeRightCursor(sel) :
              CaretBrowsing.makeFocusCursor(sel);
    var endRect = CaretBrowsing.getCursorRect(end);
    if (CaretBrowsing.targetX === null) {
      CaretBrowsing.targetX = endRect.left;
    }
    var previousEnd = end.clone();
    var leftPos = end.clone();
    var rightPos = end.clone();
    var bestPos = null;
    var bestY = null;
    var bestDelta = null;
    var bestHeight = null;
    var elementsEntered = [];
    var elementsLeft = [];
    var y = -1;
    while (true) {
      if (null === CaretBrowsing.forwards(
          rightPos, elementsEntered, elementsLeft)) {
        CaretBrowsing.setAndValidateSelection(
            evt.shiftKey ? start : leftPos, leftPos);
        break;
      }
      var range = document.createRange();
      range.setStart(leftPos.node, leftPos.index);
      range.setEnd(rightPos.node, rightPos.index);
      var rect = range.getBoundingClientRect();
      if (rect && rect.width < rect.height) {
        y = rect.top + window.pageYOffset;
  
        // Return the best match so far if we get half a line past the best.
        if (bestY != null && y > bestY + bestHeight / 2) {
          if (CaretBrowsing.setAndValidateSelection(
                  evt.shiftKey ? start : bestPos, bestPos)) {
            break;
          } else {
            bestY = null;
          }
        }
  
        // Stop here if we're an entire line the wrong direction
        // (for example, we reached the top of the next column).
        if (y < endRect.top - endRect.height) {
          if (CaretBrowsing.setAndValidateSelection(
                  evt.shiftKey ? start : leftPos, leftPos)) {
            break;
          }
        }
  
        // Otherwise look to see if this current position is on the
        // next line and better than the previous best match, if any.
        if (y >= endRect.top + endRect.height) {
          var deltaLeft = Math.abs(CaretBrowsing.targetX - rect.left);
          if ((bestDelta == null || deltaLeft < bestDelta) &&
              (leftPos.node != end.node || leftPos.index != end.index)) {
            bestPos = leftPos.clone();
            bestY = y;
            bestDelta = deltaLeft;
            bestHeight = rect.height;
          }
          var deltaRight = Math.abs(CaretBrowsing.targetX - rect.right);
          if (bestDelta == null || deltaRight < bestDelta) {
            bestPos = rightPos.clone();
            bestY = y;
            bestDelta = deltaRight;
            bestHeight = rect.height;
          }
  
          // Return the best match so far if the deltas are getting worse,
          // not better.
          if (bestDelta != null &&
              deltaLeft > bestDelta &&
              deltaRight > bestDelta) {
            if (CaretBrowsing.setAndValidateSelection(
                    evt.shiftKey ? start : bestPos, bestPos)) {
              break;
            } else {
              bestY = null;
            }
          }
        }
      }
      leftPos = rightPos.clone();
    }
  
    if (!evt.shiftKey) {
      CaretBrowsing.setFocusToNode(leftPos.node);
    }
  
    return false;
  };
  
  /**
   * Called when the user presses the up arrow. If there's a selection,
   * moves the cursor to the start of the selection range. If it's a cursor,
   * attempts to move to the equivalent horizontal pixel position in the
   * previous line of text. If this is impossible, go to the last character
   * of the previous line.
   * @param {Event} evt The DOM event.
   * @return {boolean} True if the default action should be performed.
   */
  CaretBrowsing.moveUp = function(evt) {
    var sel = window.getSelection();
    if (!evt.shiftKey && !CaretBrowsing.isCollapsed(sel)) {
      var left = CaretBrowsing.makeLeftCursor(sel);
      CaretBrowsing.setAndValidateSelection(left, left);
      return false;
    }
  
    var start = CaretBrowsing.isAmbiguous(sel) ?
                CaretBrowsing.makeLeftCursor(sel) :
                CaretBrowsing.makeFocusCursor(sel);
    var end = CaretBrowsing.isAmbiguous(sel) ?
              CaretBrowsing.makeRightCursor(sel) :
              CaretBrowsing.makeAnchorCursor(sel);
    var startRect = CaretBrowsing.getCursorRect(start);
    if (CaretBrowsing.targetX === null) {
      CaretBrowsing.targetX = startRect.left;
    }
    var previousStart = start.clone();
    var leftPos = start.clone();
    var rightPos = start.clone();
    var bestPos = null;
    var bestY = null;
    var bestDelta = null;
    var bestHeight = null;
    var elementsEntered = [];
    var elementsLeft = [];
    var y = 999999;
    while (true) {
      if (null === CaretBrowsing.backwards(
          leftPos, elementsEntered, elementsLeft)) {
        CaretBrowsing.setAndValidateSelection(
            evt.shiftKey ? end : rightPos, rightPos);
        break;
      }
      var range = document.createRange();
      range.setStart(leftPos.node, leftPos.index);
      range.setEnd(rightPos.node, rightPos.index);
      var rect = range.getBoundingClientRect();
      if (rect && rect.width < rect.height) {
        y = rect.top + window.pageYOffset;
  
        // Return the best match so far if we get half a line past the best.
        if (bestY != null && y < bestY - bestHeight / 2) {
          if (CaretBrowsing.setAndValidateSelection(
                  evt.shiftKey ? end : bestPos, bestPos)) {
            break;
          } else {
            bestY = null;
          }
        }
  
        // Exit if we're an entire line the wrong direction
        // (for example, we reached the bottom of the previous column.)
        if (y > startRect.top + startRect.height) {
          if (CaretBrowsing.setAndValidateSelection(
                  evt.shiftKey ? end : rightPos, rightPos)) {
            break;
          }
        }
  
        // Otherwise look to see if this current position is on the
        // next line and better than the previous best match, if any.
        if (y <= startRect.top - startRect.height) {
          var deltaLeft = Math.abs(CaretBrowsing.targetX - rect.left);
          if (bestDelta == null || deltaLeft < bestDelta) {
            bestPos = leftPos.clone();
            bestY = y;
            bestDelta = deltaLeft;
            bestHeight = rect.height;
          }
          var deltaRight = Math.abs(CaretBrowsing.targetX - rect.right);
          if ((bestDelta == null || deltaRight < bestDelta) &&
              (rightPos.node != start.node || rightPos.index != start.index)) {
            bestPos = rightPos.clone();
            bestY = y;
            bestDelta = deltaRight;
            bestHeight = rect.height;
          }
  
          // Return the best match so far if the deltas are getting worse,
          // not better.
          if (bestDelta != null &&
              deltaLeft > bestDelta &&
              deltaRight > bestDelta) {
            if (CaretBrowsing.setAndValidateSelection(
                    evt.shiftKey ? end : bestPos, bestPos)) {
              break;
            } else {
              bestY = null;
            }
          }
        }
      }
      rightPos = leftPos.clone();
    }
  
    if (!evt.shiftKey) {
      CaretBrowsing.setFocusToNode(rightPos.node);
    }
  
    return false;
  };
  
  /**
   * Set the document's selection to surround a control, so that the next
   * arrow key they press will allow them to explore the content before
   * or after a given control.
   * @param {Node} control The control to escape from.
   */
  CaretBrowsing.escapeFromControl = function(control) {
    control.blur();
  
    var start = new cvox.Cursor(control, 0, '');
    var previousStart = start.clone();
    var end = new cvox.Cursor(control, 0, '');
    var previousEnd = end.clone();
  
    var elementsEntered = [];
    var elementsLeft = [];
    while (true) {
      if (null === CaretBrowsing.backwards(
          start, elementsEntered, elementsLeft)) {
        break;
      }
  
      var r = document.createRange();
      r.setStart(start.node, start.index);
      r.setEnd(previousStart.node, previousStart.index);
      if (r.getBoundingClientRect()) {
        break;
      }
      previousStart = start.clone();
    }
    while (true) {
      if (null === CaretBrowsing.forwards(end, elementsEntered, elementsLeft)) {
        break;
      }
      if (cvox.DomUtil.isDescendantOfNode(end.node, control)) {
        previousEnd = end.clone();
        continue;
      }
  
      var r = document.createRange();
      r.setStart(previousEnd.node, previousEnd.index);
      r.setEnd(end.node, end.index);
      if (r.getBoundingClientRect()) {
        break;
      }
    }
  
    if (!cvox.DomUtil.isDescendantOfNode(previousStart.node, control)) {
      start = previousStart.clone();
    }
  
    if (!cvox.DomUtil.isDescendantOfNode(previousEnd.node, control)) {
      end = previousEnd.clone();
    }
  
    CaretBrowsing.setAndValidateSelection(start, end);
  
    window.setTimeout(function() {
      CaretBrowsing.updateCaretOrSelection(true);
    }, 0);
  };
  
  /**
   * Event handler, called when a key is pressed.
   * @param {Event} evt The DOM event.
   * @return {boolean} True if the default action should be performed.
   */
  CaretBrowsing.onKeyDown = function(evt) {
    if (evt.keyCode == 118) {  // F7
      chrome.extension.sendRequest({'toggle': true});
    }
  
    if (!CaretBrowsing.isEnabled) {
      return true;
    }
  
    if (evt.target && CaretBrowsing.isControlThatNeedsArrowKeys(
        /** @type (Node) */(evt.target))) {
      if (evt.keyCode == 27) {
        CaretBrowsing.escapeFromControl(/** @type {Node} */(evt.target));
        evt.preventDefault();
        evt.stopPropagation();
        return false;
      } else {
        return true;
      }
    }
  
    // If the current selection doesn't have a range, try to escape out of
    // the current control. If that fails, return so we don't fail when
    // trying to move the cursor or selection.
    var sel = window.getSelection();
    if (sel.rangeCount == 0) {
      if (document.activeElement) {
        CaretBrowsing.escapeFromControl(document.activeElement);
        sel = window.getSelection();
      }
  
      if (sel.rangeCount == 0) {
        return true;
      }
    }
  
    if (CaretBrowsing.caretElement) {
      CaretBrowsing.caretElement.style.visibility = 'visible';
      CaretBrowsing.blinkFlag = true;
    }
  
    var result = true;
    switch (evt.keyCode) {
      case 37:
        result = CaretBrowsing.moveLeft(evt);
        break;
      case 38:
        result = CaretBrowsing.moveUp(evt);
        break;
      case 39:
        result = CaretBrowsing.moveRight(evt);
        break;
      case 40:
        result = CaretBrowsing.moveDown(evt);
        break;
    }
  
    if (result == false) {
      evt.preventDefault();
      evt.stopPropagation();
    }
  
    window.setTimeout(function() {
      CaretBrowsing.updateCaretOrSelection(result == false);
    }, 0);
  
    return result;
  };
  
  /**
   * Event handler, called when the mouse is clicked. WebKit already
   * sets the selection when the mouse is clicked, all we need to do is
   * update our cursor.
   * @param {Event} evt The DOM event.
   * @return {boolean} True if the default action should be performed.
   */
  CaretBrowsing.onClick = function(evt) {
    if (!CaretBrowsing.isEnabled) {
      return true;
    }
    window.setTimeout(function() {
      CaretBrowsing.targetX = null;
      CaretBrowsing.updateCaretOrSelection(false);
    }, 0);
    return true;
  };
  
  /**
   * Called at a regular interval. Blink the cursor by changing its visibility.
   */
  CaretBrowsing.caretBlinkFunction = function() {
    if (CaretBrowsing.caretElement) {
      if (CaretBrowsing.blinkFlag) {
        CaretBrowsing.caretElement.style.visibility = 'visible';
        CaretBrowsing.blinkFlag = false;
      } else {
        CaretBrowsing.caretElement.style.visibility = 'hidden';
        CaretBrowsing.blinkFlag = true;
      }
    }
  };
  
  /**
   * Update whether or not the caret is visible, based on whether caret browsing
   * is enabled and whether this window / iframe has focus.
   */
  CaretBrowsing.updateIsCaretVisible = function() {
    var previousCaretVisible = CaretBrowsing.isCaretVisible;
    CaretBrowsing.isCaretVisible =
        (CaretBrowsing.isEnabled && CaretBrowsing.isWindowFocused);
    if (CaretBrowsing.isCaretVisible && !previousCaretVisible) {
      CaretBrowsing.blinkFunctionId = window.setInterval(
          CaretBrowsing.caretBlinkFunction, 500);
      CaretBrowsing.setInitialCursor();
      CaretBrowsing.updateCaretOrSelection(true);
    } else if (!CaretBrowsing.isCaretVisible && previousCaretVisible) {
      window.clearInterval(CaretBrowsing.blinkFunctionId);
      if (CaretBrowsing.caretElement) {
        CaretBrowsing.isSelectionCollapsed = false;
        CaretBrowsing.caretElement.style.opacity = '0.0';
        CaretBrowsing.caretElement = null;
      }
    }
  };
  
  /**
   * Called when we get a message from the background page updating the
   * enabled/disabled state of caret browsing.
   * @param {Object} request The message.
   */
  CaretBrowsing.onExtensionMessage = function(request) {
    CaretBrowsing.isEnabled = (request['enabled'] == true);
    CaretBrowsing.updateIsCaretVisible();
  };
  
  /**
   * Called when this window / iframe gains focus.
   */
  CaretBrowsing.onWindowFocus = function() {
    CaretBrowsing.isWindowFocused = true;
    CaretBrowsing.updateIsCaretVisible();
  };
  
  /**
   * Called when this window / iframe loses focus.
   */
  CaretBrowsing.onWindowBlur = function() {
    CaretBrowsing.isWindowFocused = false;
    CaretBrowsing.updateIsCaretVisible();
  };
  
  /**
   * Initializes caret browsing by adding event listeners and extension
   * message listeners.
   */
  CaretBrowsing.init = function() {
    CaretBrowsing.isWindowFocused = document.hasFocus();
  
    document.addEventListener('keydown', CaretBrowsing.onKeyDown, false);
    document.addEventListener('click', CaretBrowsing.onClick, false);
    window.addEventListener('focus', CaretBrowsing.onWindowFocus, false);
    window.addEventListener('blur', CaretBrowsing.onWindowBlur, false);
  };
  