Optimize successive calls SourceFile.getLine().

lib/src/file.dart

Index: lib/src/file.dart
diff --git a/lib/src/file.dart b/lib/src/file.dart
index aee3d7831ae5dddff743dcab14a5d1f39df5c150..6873e6e4e02b139b48c8aed77b59771796e9326e 100644
--- a/lib/src/file.dart
+++ b/lib/src/file.dart
@@ -43,6 +43,14 @@ class SourceFile {
   /// The number of lines in the file.
   int get lines => _lineStarts.length;
 
+  /// The line that the offset fell on the last time [getLine] was called.
+  ///
+  /// In many cases, sequential calls to getLine() are for nearby, usually
+  /// increasing offsets. In that case, we can find the line for an offset
+  /// quickly by first checking to see if the offset is on the same line as the
+  /// previous result.
+  int _cachedLine;
+
   /// Creates a new source file from [text].
   ///
   /// [url] may be either a [String], a [Uri], or `null`.
@@ -85,7 +93,56 @@ class SourceFile {
       throw new RangeError("Offset $offset must not be greater than the number "
           "of characters in the file, $length.");
     }
-    return binarySearch(_lineStarts, (o) => o > offset) - 1;
+
+    if (_isNearCachedLine(offset)) return _cachedLine;
+
+    return _cachedLine = _binarySearch(offset) - 1;

[nweiz, 2015/09/02 00:06:30]

This is cute, but I think it's clearer to assign separately.

+  }
+
+  /// Returns `true` if [offset] is within [_cachedLine].

[nweiz, 2015/09/02 00:06:30]

"within" -> "near"

+  ///
+  /// This actually checks on [_cachedLine] and the next line. If it's on the
+  /// next line, it updates [_cachedLine] to point to that.
+  bool _isNearCachedLine(int offset) {
+    if (_cachedLine == null) return false;
+
+    // See if it's before the cached line.
+    if (offset < _lineStarts[_cachedLine]) return false;
+
+    // See if it's on the cached line.
+    if (_cachedLine >= _lineStarts.length - 1 ||
+        offset < _lineStarts[_cachedLine + 1]) {
+      return true;
+    }
+
+    // See if it's on the next line.
+    if (_cachedLine >= _lineStarts.length - 2 ||
+        offset < _lineStarts[_cachedLine + 2]) {
+      _cachedLine++;
+      return true;
+    }
+
+    return false;
+  }
+
+  /// Binary search through [_lineStarts] to find the line containing [offset].
+  ///
+  /// Given a result `n`, that all items before `n` will not match, `n` matches,
+  /// and all items after `n` match too. The result is -1 when there are no
+  /// items, 0 when all items match, and list.length when none does.

[nweiz, 2015/09/02 00:06:30]

Since we can guarantee there will be at least one line start and that they'll
all be different, I think we can simplify some of this return documentation.

+  int _binarySearch(int offset) {
+    int min = 0;
+    int max = _lineStarts.length - 1;
+    while (min < max) {
+      var half = min + ((max - min) ~/ 2);
+      if (_lineStarts[half] > offset) {
+        max = half;
+      } else {
+        min = half + 1;
+      }
+    }
+
+    return max;
   }
 
   /// Gets the 0-based column corresponding to [offset].