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

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

 // Copyright (c) 2016, 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.stack_listener;
 
 import 'dart:collection' show Queue;
 
 import 'package:front_end/src/fasta/parser.dart' show ErrorKind, Listener;
 
@@ skipping 25 matching lines @@
   Modifiers,
   SwitchScope,
   Type,
   TypeArguments,
   TypeList,
   TypeVariable,
   TypeVariables,
 }
 
 abstract class StackListener extends Listener {
-  final Queue<Object> stack = new Queue<Object>();
+  final _Stack<Object> stack = new _Stack<Object>();
 
   Uri get uri;
 
   // TODO(ahe): This doesn't belong here. Only implemented by body_builder.dart
   // and ast_builder.dart.
   void finishFunction(
       covariant formals, AsyncMarker asyncModifier, covariant body) {
     return internalError("Unsupported operation");
   }
 
   // TODO(ahe): This doesn't belong here. Only implemented by body_builder.dart
   // and ast_builder.dart.
   void exitLocalScope() => internalError("Unsupported operation");
 
   // TODO(ahe): This doesn't belong here. Only implemented by body_builder.dart
   // and ast_builder.dart.
   void prepareInitializers() => internalError("Unsupported operation");
 
   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();
   }
 
   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) {
     // printEvent(name);
   }
 
   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) {
         s = s.substring(0, index) + "...";
       }
       print(s);
     }
     print(name);
   }
 
   @override
   void logEvent(String name) {
     internalError("Unhandled event: $name in $runtimeType $uri:\n"
-        "  ${stack.join('\n  ')}");
+        "  ${stack.values.join('\n  ')}");
   }
 
   @override
   void handleIdentifier(Token token) {
     debugEvent("handleIdentifier");
     push(token.value);
   }
 
   @override
   void endInitializer(Token token) {
     debugEvent("Initializer");
   }
 
   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.
       inputError(uri, recoverableErrors.first.beginOffset, recoverableErrors);
     }
   }
 
   @override
   void endTopLevelDeclaration(Token token) {
     debugEvent("TopLevelDeclaration");
@@ skipping 93 matching lines @@
   }
 
   void nit(String message, [int charOffset = -1]) {
     messages.nit(uri, charOffset, message);
   }
 
   void warning(String message, [int charOffset = -1]) {
     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;
+  }
+}