fasta: Use more efficient Uint16List/Uint32List for line offset information, use hints for length

pkg/front_end/lib/src/fasta/scanner/abstract_scanner.dart

Index: pkg/front_end/lib/src/fasta/scanner/abstract_scanner.dart
diff --git a/pkg/front_end/lib/src/fasta/scanner/abstract_scanner.dart b/pkg/front_end/lib/src/fasta/scanner/abstract_scanner.dart
index f4de827c7fa5399a8d90e8207653e0b2503b8d77..aa0d742a755c79e6e0b4807358b24eeb8a01536e 100644
--- a/pkg/front_end/lib/src/fasta/scanner/abstract_scanner.dart
+++ b/pkg/front_end/lib/src/fasta/scanner/abstract_scanner.dart
@@ -4,6 +4,13 @@
 
 library fasta.scanner.abstract_scanner;
 
+import 'dart:collection' show
+    ListMixin;
+
+import 'dart:typed_data' show
+    Uint16List,
+    Uint32List;
+
 import '../scanner.dart' show
     ErrorToken,
     Scanner,
@@ -55,9 +62,10 @@ abstract class AbstractScanner implements Scanner {
    */
   Token tail;
 
-  final List<int> lineStarts = <int>[0];
+  final List<int> lineStarts;
 
-  AbstractScanner(this.includeComments) {
+  AbstractScanner(this.includeComments, {int numberOfBytesHint})
+      : lineStarts = new LineStarts(numberOfBytesHint) {
     this.tail = this.tokens;
   }
 
@@ -1165,3 +1173,83 @@ PrecedenceInfo closeBraceInfoFor(BeginGroupToken begin) {
     r'${': CLOSE_CURLY_BRACKET_INFO,
   }[begin.value];
 }
+
+class LineStarts extends Object with ListMixin<int> {
+  List<int> array;
+  int arrayLength = 0;
+
+  LineStarts(int numberOfBytesHint) {
+    // Let's assume the average Dart file is 300 bytes.
+    if (numberOfBytesHint == null) numberOfBytesHint = 300;
+
+    // Let's assume we have on average 22 bytes per line.
+    final int expectedNumberOfLines = 1 + (numberOfBytesHint ~/ 22);
+
+    // We don't use the hint to indicate whether we might need a Uint32List to
+    // represent the offsets, since it's very unlikly to have more than 2^16-1
+    // characters.

[ahe, 2017/02/23 12:47:35]

I don't understand this comment. It seems like you do use the hint.

[kustermann, 2017/02/24 14:24:49]

Sorry that was a left over, will remove it.

+    if (numberOfBytesHint > 65535) {
+      array = new Uint32List(expectedNumberOfLines);
+    } else {
+      array = new Uint16List(expectedNumberOfLines);
+    }
+
+    // The first line starts at character offset 0.
+    add(0);
+  }
+
+  // Implement abstract members used by [ListMixin]
+
+  int get length => arrayLength;
+
+  int operator[](int index) {
+    assert(index < arrayLength);
+    return array[index];
+  }
+
+  void set length(int newLength) {
+    if (newLength > array.length) {
+      grow(newLength);
+    }
+    arrayLength = newLength;
+  }
+
+  void operator[]=(int index, int value) {
+    if (value > 65535 && array is! Uint32List) {
+      switchToUint32(array.length);
+    }
+    array[index] = value;
+  }
+
+  // Specialize methods from [ListMixin].
+  void add(int value) {
+    if (arrayLength >= array.length) {
+      grow(0);
+    }
+    if (value > 65535 && array is! Uint32List) {
+      switchToUint32(array.length);
+    }
+    array[arrayLength++] = value;
+  }
+
+  // Helper methods.
+
+  void grow(int newLengthMinimum) {
+    int newLength = array.length * 2;
+    if (newLength < newLengthMinimum) newLength = newLengthMinimum;
+
+    if (array is Uint16List) {
+      final newArray = new Uint16List(newLength);
+      newArray.setRange(0, arrayLength, array);
+      array = newArray;
+    } else {
+      switchToUint32(newLength);
+    }
+  }
+
+  void switchToUint32(int newLength) {
+    final newArray = new Uint32List(newLength);
+    newArray.setRange(0, arrayLength, array);
+    array = newArray;
+  }
+}