Optimize successive calls SourceFile.getLine().

lib/src/file.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.
 
 library source_span.file;
 
 import 'dart:math' as math;
 import 'dart:typed_data';
 
 import 'location.dart';
 import 'span.dart';
 import 'span_mixin.dart';
 import 'span_with_context.dart';
-import 'utils.dart';
 
 // Constants to determine end-of-lines.
 const int _LF = 10;
 const int _CR = 13;
 
 /// A class representing a source file.
 ///
 /// This doesn't necessarily have to correspond to a file on disk, just a chunk
 /// of text usually with a URL associated with it.
 class SourceFile {
@@ skipping 11 matching lines @@
 
   /// The code points of the characters in the file.
   final Uint32List _decodedChars;
 
   /// The length of the file in characters.
   int get length => _decodedChars.length;
 
   /// 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`.
   SourceFile(String text, {url})
       : this.decoded(text.runes, url: url);
 
   /// Creates a new source file from a list of decoded characters.
   ///
   /// [url] may be either a [String], a [Uri], or `null`.
   SourceFile.decoded(Iterable<int> decodedChars, {url})
@@ skipping 22 matching lines @@
   FileLocation location(int offset) => new FileLocation._(this, offset);
 
   /// Gets the 0-based line corresponding to [offset].
   int getLine(int offset) {
     if (offset < 0) {
       throw new RangeError("Offset may not be negative, was $offset.");
     } else if (offset > length) {
       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 (offset < _lineStarts.first) return -1;
+    if (offset >= _lineStarts.last) return _lineStarts.length - 1;
+
+    if (_isNearCachedLine(offset)) return _cachedLine;
+
+    _cachedLine = _binarySearch(offset) - 1;
+    return _cachedLine;
+  }
+
+  /// Returns `true` if [offset] is near [_cachedLine].
+  ///
+  /// 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].
+  ///
+  /// Returns the index of the line in [_lineStarts].
+  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].
   ///
   /// If [line] is passed, it's assumed to be the line containing [offset] and
   /// is used to more efficiently compute the column.
   int getColumn(int offset, {int line}) {
     if (offset < 0) {
       throw new RangeError("Offset may not be negative, was $offset.");
     } else if (offset > length) {
@@ skipping 181 matching lines @@
       var start = math.min(this._start, other._start);
       var end = math.max(this._end, other._end);
       return new _FileSpan(file, start, end);
     } else {
       var start = math.min(this._start, other.start.offset);
       var end = math.max(this._end, other.end.offset);
       return new _FileSpan(file, start, end);
     }
   }
 }