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

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

 // Copyright (c) 2012, 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 fasta.scanner.abstract_scanner;
 
+import 'dart:collection' show
+    ListMixin;
+
+import 'dart:typed_data' show
+    Uint16List,
+    Uint32List;
+
 import '../scanner.dart' show
     ErrorToken,
     Scanner,
     buildUnexpectedCharacterToken;
 
 import 'error_token.dart' show
     UnmatchedToken,
     UnterminatedToken;
 
 import 'keyword.dart' show
@@ skipping 31 matching lines @@
    * is not exposed to clients of the scanner, which are expected to invoke
    * [firstToken] to access the token stream.
    */
   final Token tokens = new SymbolToken(EOF_INFO, -1);
 
   /**
    * A pointer to the last scanned token.
    */
   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;
   }
 
   /**
    * Advances and returns the next character.
    *
    * If the next character is non-ASCII, then the returned value depends on the
    * scanner implementation. The [Utf8BytesScanner] returns a UTF-8 byte, while
    * the [StringScanner] returns a UTF-16 code unit.
    *
@@ skipping 1087 matching lines @@
 
 PrecedenceInfo closeBraceInfoFor(BeginGroupToken begin) {
   return const {
     '(': CLOSE_PAREN_INFO,
     '[': CLOSE_SQUARE_BRACKET_INFO,
     '{': CLOSE_CURLY_BRACKET_INFO,
     '<': GT_INFO,
     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;
+  }
+}