Optimize successive calls SourceFile.getLine(). R=nweiz@google.com Review URL: https://codereview.chromium.org//1319303004 .
diff --git a/pkgs/source_span/CHANGELOG.md b/pkgs/source_span/CHANGELOG.md index 10d94f6..caf8af5 100644 --- a/pkgs/source_span/CHANGELOG.md +++ b/pkgs/source_span/CHANGELOG.md
@@ -2,6 +2,7 @@ * Fixed another case in which `FileSpan.union` could throw an exception for external implementations of `FileSpan`. +* Optimize `getLine()` in `SourceFile` when repeatedly called. # 1.1.4
diff --git a/pkgs/source_span/lib/src/file.dart b/pkgs/source_span/lib/src/file.dart index e5bc53c..c2b97e7 100644 --- a/pkgs/source_span/lib/src/file.dart +++ b/pkgs/source_span/lib/src/file.dart
@@ -11,7 +11,6 @@ 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; @@ -43,6 +42,14 @@ /// 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 +92,58 @@ 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].
diff --git a/pkgs/source_span/lib/src/location.dart b/pkgs/source_span/lib/src/location.dart index 2705742..42e2b7d 100644 --- a/pkgs/source_span/lib/src/location.dart +++ b/pkgs/source_span/lib/src/location.dart
@@ -44,11 +44,11 @@ line = line == null ? 0 : line, column = column == null ? offset : column { if (this.offset < 0) { - throw new RangeError("Offset may not be negative, was $offset."); + throw new RangeError("Offset may not be negative, was ${this.offset}."); } else if (this.line < 0) { - throw new RangeError("Line may not be negative, was $line."); + throw new RangeError("Line may not be negative, was ${this.line}."); } else if (this.column < 0) { - throw new RangeError("Column may not be negative, was $column."); + throw new RangeError("Column may not be negative, was ${this.column}."); } }
diff --git a/pkgs/source_span/lib/src/utils.dart b/pkgs/source_span/lib/src/utils.dart index 2d33865..fa08957 100644 --- a/pkgs/source_span/lib/src/utils.dart +++ b/pkgs/source_span/lib/src/utils.dart
@@ -14,29 +14,6 @@ Comparable max(Comparable obj1, Comparable obj2) => obj1.compareTo(obj2) > 0 ? obj1 : obj2; -/// Find the first entry in a sorted [list] that matches a monotonic predicate. -/// -/// 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. -int binarySearch(List list, bool matches(item)) { - if (list.length == 0) return -1; - if (matches(list.first)) return 0; - if (!matches(list.last)) return list.length; - - int min = 0; - int max = list.length - 1; - while (min < max) { - var half = min + ((max - min) ~/ 2); - if (matches(list[half])) { - max = half; - } else { - min = half + 1; - } - } - return max; -} - /// Finds a line in [context] containing [text] at the specified [column]. /// /// Returns the index in [context] where that line begins, or null if none
diff --git a/pkgs/source_span/test/utils_test.dart b/pkgs/source_span/test/utils_test.dart index 3b6238b..5d973f5 100644 --- a/pkgs/source_span/test/utils_test.dart +++ b/pkgs/source_span/test/utils_test.dart
@@ -6,40 +6,6 @@ import 'package:source_span/src/utils.dart'; main() { - group('binary search', () { - test('empty', () { - expect(binarySearch([], (x) => true), -1); - }); - - test('single element', () { - expect(binarySearch([1], (x) => true), 0); - expect(binarySearch([1], (x) => false), 1); - }); - - test('no matches', () { - var list = [1, 2, 3, 4, 5, 6, 7]; - expect(binarySearch(list, (x) => false), list.length); - }); - - test('all match', () { - var list = [1, 2, 3, 4, 5, 6, 7]; - expect(binarySearch(list, (x) => true), 0); - }); - - test('compare with linear search', () { - for (int size = 0; size < 100; size++) { - var list = []; - for (int i = 0; i < size; i++) { - list.add(i); - } - for (int pos = 0; pos <= size; pos++) { - expect(binarySearch(list, (x) => x >= pos), - _linearSearch(list, (x) => x >= pos)); - } - } - }); - }); - group('find line start', () { test('skip entries in wrong column', () { var context = '0_bb\n1_bbb\n2b____\n3bbb\n';