fasta: Use a slightly more efficient implementation for the [StackListener]s stack

pkg/front_end/lib/src/fasta/source/stack_listener.dart

Index: pkg/front_end/lib/src/fasta/source/stack_listener.dart
diff --git a/pkg/front_end/lib/src/fasta/source/stack_listener.dart b/pkg/front_end/lib/src/fasta/source/stack_listener.dart
index 23d915588b113e03b5131915b7d25088306c64d8..30b92241e0cca9f91316c5c4012b2e8ca8018f8e 100644
--- a/pkg/front_end/lib/src/fasta/source/stack_listener.dart
+++ b/pkg/front_end/lib/src/fasta/source/stack_listener.dart
@@ -43,7 +43,7 @@ enum NullValue {
 }
 
 abstract class StackListener extends Listener {
-  final Queue<Object> stack = new Queue<Object>();
+  final _Stack<Object> stack = new _Stack<Object>();
 
   Uri get uri;
 
@@ -64,18 +64,12 @@ abstract class StackListener extends Listener {
 
   void push(Object node) {
     if (node == null) internalError("null not allowed.");
-    stack.addLast(node);
+    stack.push(node);
   }
 
-  Object peek() {
-    Object node = stack.last;
-    return node is NullValue ? null : node;
-  }
+  Object peek() => stack.last;
 
-  Object pop() {
-    Object node = stack.removeLast();
-    return node is NullValue ? null : node;
-  }
+  Object pop() => stack.pop();
 
   Object popIfNotNull(Object value) {
     return value == null ? null : pop();
@@ -83,11 +77,7 @@ abstract class StackListener extends Listener {
 
   List popList(int n) {
     if (n == 0) return null;
-    List list = new List.filled(n, null, growable: true);
-    for (int i = n - 1; i >= 0; i--) {
-      list[i] = pop();
-    }
-    return list;
+    return stack.popList(n);
   }

[kustermann, 2017/02/21 13:29:09]

It's more efficient to implement stack.popList() directly instead of doing many
pop()s.

Therefore I moved the handling of NullValue into _Stack.popList().

For consistency I moved all other handling of NullValue into _Stack as well.

 
   void debugEvent(String name) {
@@ -95,7 +85,7 @@ abstract class StackListener extends Listener {
   }
 
   void printEvent(String name) {
-    for (Object o in stack) {
+    for (Object o in stack.values) {
       String s = "  $o";
       int index = s.indexOf("\n");
       if (index != -1) {
@@ -109,7 +99,7 @@ abstract class StackListener extends Listener {
   @override
   void logEvent(String name) {
     internalError("Unhandled event: $name in $runtimeType $uri:\n"
-        "  ${stack.join('\n  ')}");
+        "  ${stack.values.join('\n  ')}");
   }
 
   @override
@@ -126,7 +116,7 @@ abstract class StackListener extends Listener {
   void checkEmpty(int charOffset) {
     if (stack.isNotEmpty) {
       internalError("${runtimeType}: Stack not empty:\n"
-          "  ${stack.join('\n  ')}", uri, charOffset);
+          "  ${stack.values.join('\n  ')}", uri, charOffset);
     }
     if (recoverableErrors.isNotEmpty) {
       // TODO(ahe): Handle recoverable errors better.
@@ -240,3 +230,60 @@ abstract class StackListener extends Listener {
     messages.warning(uri, charOffset, message);
   }
 }
+
+class _Stack<E> {

[ahe, 2017/02/21 14:24:34]

Please don't use privacy.

[ahe, 2017/02/21 14:24:34]

I think you don't need the type variable. It should just be Object.

[kustermann, 2017/02/22 13:59:37]

Done.

[kustermann, 2017/02/22 13:59:37]

Done.

+  List<E> _table = new List<E>(8);

[ahe, 2017/02/21 14:24:34]

This type annotation isn't correct as NullValue isn't a subtype of E.

Here's how I make sure that the program doesn't have any warnings:

./xcodebuild/ReleaseX64/dart pkg/testing/bin/testing.dart
--config=pkg/front_end/test/fasta/testing.json analyze

[kustermann, 2017/02/22 13:59:37]

Thanks.

+  int _length = 0;
+
+  bool get isNotEmpty => _length > 0;
+
+  int get length => _length;
+
+  E get last {
+    final value = _table[_length - 1];
+    return value is NullValue ? null : value;
+  }
+
+  void push(E value) {
+    _table[_length++] = value;
+    if (_table.length == _length) {
+      _grow();
+    }
+  }
+
+  E pop() {
+    assert(_length > 0);
+    final E value = _table[--_length];
+    _table[_length] = null;
+    return value is NullValue ? null : value;
+  }
+
+  List<E> popList(int count) {
+    assert(_length >= count);
+
+    final table = _table;
+    final length = _length;
+
+    final tailList = new List<E>.filled(count, null, growable: true);
+    final startIndex = length - count;
+    for (int i = 0; i < count; i++) {
+      final value = table[startIndex + i];
+      tailList[i] = value is NullValue ? null : value;
+    }
+    _length -= count;
+
+    return tailList;
+  }
+
+  List<E> get values {
+    final List<E> list = new List<E>(_length);
+    list.setRange(0, _length, _table);
+    return list;
+  }
+
+  void _grow() {
+    final List<E> newTable = new List<E>(_table.length * 2);
+    newTable.setRange(0, _table.length, _table, 0);
+    _table = newTable;
+  }
+}