Optimize LineInfo.getLocation().

pkg/analyzer/lib/src/generated/source.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // This code was auto-generated, is not intended to be edited, and is subject to
 // significant change. Please see the README file for more information.
 
 library engine.source;
 
 import 'dart:collection';
@@ skipping 138 matching lines @@
  * Instances of the class `LineInfo` encapsulate information about line and column information
  * within a source file.
  */
 class LineInfo {
   /**
    * An array containing the offsets of the first character of each line in the source code.
    */
   final List<int> _lineStarts;
 
   /**
+   * The zero-based [_lineStarts] index resulting from the last call to
+   * [getLocation].
+   */
+  int _previousLine = 0;
+
+  /**
    * Initialize a newly created set of line information to represent the data encoded in the given
    * array.
    *
    * @param lineStarts the offsets of the first character of each line in the source code
    */
   LineInfo(this._lineStarts) {
     if (_lineStarts == null) {
       throw new IllegalArgumentException("lineStarts must be non-null");
     } else if (_lineStarts.length < 1) {
       throw new IllegalArgumentException("lineStarts must be non-empty");
     }
   }
 
   /**
    * Return the location information for the character at the given offset.
    *
    * @param offset the offset of the character for which location information is to be returned
    * @return the location information for the character at the given offset
    */
   LineInfo_Location getLocation(int offset) {
-    int lineCount = _lineStarts.length;
-    for (int i = 1; i < lineCount; i++) {
-      if (offset < _lineStarts[i]) {
-        return new LineInfo_Location(i, offset - _lineStarts[i - 1] + 1);
+    var min = 0;
+    var max = _lineStarts.length - 1;
+
+    // Subsequent calls to [getLocation] are often for offsets near each other.
+    // To take advantage of that, we cache the index of the line start we found
+    // when this was last called. If the current offset is on that line or
+    // later, we'll skip those early indices completely when searching.
+    if (offset >= _lineStarts[_previousLine]) {
+      min = _previousLine;
+
+      // Before kicking off a full binary search, do a quick check here to see
+      // if the new offset is on that exact line.
+      if (min == _lineStarts.length - 1 || offset < _lineStarts[min + 1]) {
+        return new LineInfo_Location(min + 1, offset - _lineStarts[min] + 1);
       }
     }
-    return new LineInfo_Location(lineCount, offset - _lineStarts[lineCount - 1] + 1);
+
+    // Binary search to fine the line containing this offset.
+    while (min < max) {
+      var midpoint = (max - min + 1) ~/ 2 + min;
+
+      if (_lineStarts[midpoint] > offset) {
+        max = midpoint - 1;
+      } else {
+        min = midpoint;
+      }
+    }
+
+    _previousLine = min;
+
+    return new LineInfo_Location(min + 1, offset - _lineStarts[min] + 1);
   }
 }
 
 /**
  * Instances of the class `Location` represent the location of a character as a line and
  * column pair.
  */
 class LineInfo_Location {
   /**
    * The one-based index of the line containing the character.
@@ skipping 718 matching lines @@
 
   /**
    * Return an absolute URI that represents the given source, or `null` if a valid URI cannot
    * be computed.
    *
    * @param source the source to get URI for
    * @return the absolute URI representing the given source
    */
   Uri restoreAbsolute(Source source) => null;
 }