Peek past balanced parens to see if they are an expression or lambda.

parser.dart

 // Copyright (c) 2011, 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.
 
 // TODO(jimhug): Error recovery needs major work!
 /**
  * A simple recursive descent parser for the dart language.
  *
  * This parser is designed to be more permissive than the official
  * Dart grammar.  It is expected that many grammar errors would be
  * reported by a later compiler phase.  For example, a class is allowed
  * to extend an arbitrary number of base classes - this can be
  * very clearly detected and is reported in a later compiler phase.
  */
 class Parser {
-  Tokenizer tokenizer;
+  TokenSource tokenizer;

[jimhug, 2011/10/31 14:16:46]

Note: This change seems good independent of the rest.

 
   final SourceFile source;
   /** Enables diet parse, which skips function bodies. */
   final bool diet;
 
   // TODO(jimhug): Is it possible to handle initializers cleanly?
   bool _inInitializers;
 
   Token _previousToken;
   Token _peekToken;
 
+  // Map from start position of a '(' to token following the matching ')'. Used
+  // to distinguish closure formal parameter lists from parenthesised
+  // expressions and argument lists.  Closure formals are followed by '=>' or
+  // '{'.
+  Map<int, Token> _afterCloseParenCache;
+  int _highestCachePosition = -1;
+
   Parser(this.source, [this.diet = false, int startOffset = 0]) {
     tokenizer = new Tokenizer(source, true, startOffset);
     _peekToken = tokenizer.next();
     _previousToken = null;
     _inInitializers = false;
+
+    _afterCloseParenCache = new Map<int, Token>();
   }
 
   /** Generate an error if [source] has not been completely consumed. */
   void checkEndOfFile() {
     _eat(TokenKind.END_OF_FILE);
   }
 
   /** Guard to break out of parser when an unexpected end of file is found. */
   // TODO(jimhug): Failure to call this method can lead to inifinite parser
   //   loops.  Consider embracing exceptions for more errors to reduce
@@ skipping 820 matching lines @@
     expr = expression();
     if (label === null && _maybeEat(TokenKind.COLON)) {
       label = _makeLabel(expr);
       expr = expression();
     }
     return new ArgumentNode(label, expr, _makeSpan(start));
   }
 
   arguments() {
     var args = [];
-    // TODO(jimhug): switch to forced formals when get a DeclaredId
     _eat(TokenKind.LPAREN);
     if (!_maybeEat(TokenKind.RPAREN)) {
       do {
         args.add(argument());
       } while (_maybeEat(TokenKind.COMMA));
       _eat(TokenKind.RPAREN);
     }
     return args;
   }
 
   finishPostfixExpression(expr) {
     switch(_peek()) {
       case TokenKind.LPAREN:
-        return finishPostfixExpression(new CallExpression(expr, arguments(),
-          _makeSpan(expr.span.start)));
+        return finishCallOrLambdaExpression(expr);
       case TokenKind.LBRACK:
         _eat(TokenKind.LBRACK);
         var index = expression();
         _eat(TokenKind.RBRACK);
         return finishPostfixExpression(new IndexExpression(expr, index,
           _makeSpan(expr.span.start)));
       case TokenKind.DOT:
         _eat(TokenKind.DOT);
         var name = identifier();
         var ret = new DotExpression(expr, name, _makeSpan(expr.span.start));
         return finishPostfixExpression(ret);
 
       case TokenKind.INCR:
       case TokenKind.DECR:
         var tok = _next();
         return new PostfixExpression(expr, tok, _makeSpan(expr.span.start));
 
       // These are pseudo-expressions supported for cover grammar
       // must be forbidden when parsing initializers.
+
       case TokenKind.ARROW:
       case TokenKind.LBRACE:
-        if (_inInitializers) return expr;
-        var body = functionBody(true);
-        return _makeFunction(expr, body);
+         return expr;
 
       default:
         if (_peekIdentifier()) {
           return finishPostfixExpression(
             new DeclaredIdentifier(_makeType(expr), identifier(),
               _makeSpan(expr.span.start)));
         } else {
           return expr;
         }
     }
   }
 
+  finishCallOrLambdaExpression(expr) {
+    if (!_inInitializers && _atClosureParameters()) {
+      var formals = formalParameterList();
+      var body = functionBody(true);
+      return _makeFunction(expr, formals, body);
+    } else {
+      var args = arguments();
+      return finishPostfixExpression(
+          new CallExpression(expr, args, _makeSpan(expr.span.start)));
+    }
+  }
+
   /** Checks if the given expression is a binary op of the given kind. */
   _isBin(expr, kind) {
     return expr is BinaryExpression && expr.op.kind == kind;
   }
 
   _boolTypeRef(SourceSpan span) {
     return new TypeReference(span, world.boolType);
   }
 
   _numTypeRef(SourceSpan span) {
@@ skipping 148 matching lines @@
       _errorExpected('string literal, but found interpolated string start');
     } else if (kind == TokenKind.INCOMPLETE_STRING) {
       _next();
       _errorExpected('string literal, but found incomplete string');
     }
     return null;
   }
 
   _parenOrLambda() {
     int start = _peekToken.start;
-    var args = arguments();
-    if (!_inInitializers &&
-        (_peekKind(TokenKind.ARROW) || _peekKind(TokenKind.LBRACE))) {
+    if (!_inInitializers && _atClosureParameters()) {
+      var formals = formalParameterList();
       var body = functionBody(true);
-      var formals = _makeFormals(args);
       var func = new FunctionDefinition(null, null, null, formals, null,
         body, _makeSpan(start));
       return new LambdaExpression(func, func.span);
     } else {
+      var args = arguments();
       if (args.length == 1) {
         return new ParenExpression(args[0].value, _makeSpan(start));
       } else {
         _error('unexpected comma expression');
         return args[0].value;
       }
     }
   }
 
+  bool _atClosureParameters() {
+    Token afterCloseParen = _peekPastCloseParen();
+    return afterCloseParen.kind == TokenKind.ARROW
+        || afterCloseParen.kind == TokenKind.LBRACE;
+  }
+
+  Token _peekPastCloseParen() {
+    int pos = _peekToken.start;
+    if (pos > _highestCachePosition)

[jimhug, 2011/10/31 14:16:46]

Style: The return either needs to be on the same line as the if or it needs {}'s
surrounding it.

+      return _fillAfterCloseParenCache();
+    return _afterCloseParenCache[pos];
+  }
+
+  _fillAfterCloseParenCache() {
+    // Scan for the matching RPAREN to the current LPAREN and return the
+    // following token.  Add intermediate values to cache to prevent this
+    // look-ahead scan from being called again for nested parentheses.  Note
+    // that the outermost parens are not added to the cache as the following
+    // token is directly available; not touching the cache for non-nested parens
+    // has a small performance benefit.
+    List tokens = [];
+    List positions = [];
+    Token firstOpenParen = _peekToken;
+    while (true) {
+      Token token = _next();
+      tokens.add(token);
+      int kind = token.kind;
+      if (kind == TokenKind.LPAREN) {
+        positions.add(token.start);
+      } else if (kind == TokenKind.RPAREN) {
+        int openPos = positions.removeLast();
+        if (positions.length == 0)
+          break;
+        _afterCloseParenCache[openPos] = _peekToken;
+        if (openPos > _highestCachePosition)
+          _highestCachePosition = openPos;
+      } else if (kind == TokenKind.END_OF_FILE) {
+        _error('parenthesis never closed', firstOpenParen.span);
+        // The invariant that all positions less than _highestCachePosition are
+        // in the cache is violated if we bail out here due to the error.  We
+        // could add the pending elements of the positions list, but instead we
+        // clear the cache.  Clearing the cache also causes all the unmatched
+        // parens to be enumerated, which might be a useful diagnostic behavior.
+        _afterCloseParenCache = new Map<int,Token>();
+        _highestCachePosition = -1;
+        break;
+      }
+    }
+
+    var after = _peekToken;
+    // Put all the lookahead tokens back into the parser's token stream.
+    tokens.add(_peekToken);
+    tokenizer = new DivertedTokenSource(tokens, this, tokenizer);
+    _next();  // Re-synchronize parser lookahead state.
+    return after;
+  }
+
 
   _typeAsIdentifier(type) {
     // TODO(jimhug): lots of errors to check for
     return type.name;
   }
 
   _specialIdentifier(bool includeOperators) {
     int start = _peekToken.start;
     String name;
 
@@ skipping 360 matching lines @@
 
     return new Identifier(tok.text, _makeSpan(tok.start));
   }
 
   ///////////////////////////////////////////////////////////////////
   // These last productions handle most ambiguities in grammar
   // They will convert expressions into other types.
   ///////////////////////////////////////////////////////////////////
 
   /**
-   * Converts an [Expression] and a [Statment] body into a
+   * Converts an [Expression], [Formals] and a [Statment] body into a
    * [FunctionDefinition].
    */
-  _makeFunction(expr, body) {
+  _makeFunction(expr, formals, body) {
     var name, type;
-    if (expr is CallExpression) {
-      if (expr.target is VarExpression) {
-        name = expr.target.name;
-        type = null;
-      } else if (expr.target is DeclaredIdentifier) {
-        name = expr.target.name;
-        type = expr.target.type;
-      } else {
-        _error('bad function');
-      }
-      var formals = _makeFormals(expr.arguments);
-      var span =
-        new SourceSpan(expr.span.file, expr.span.start, body.span.end);
-      var func =
+    if (expr is VarExpression) {
+      name = expr.name;
+      type = null;
+    } else if (expr is DeclaredIdentifier) {
+      name = expr.name;
+      type = expr.type;
+    } else {
+      _error('bad function');
+    }
+    var span = new SourceSpan(expr.span.file, expr.span.start, body.span.end);
+    var func =
         new FunctionDefinition(null, type, name, formals, null, body, span);
-      return new LambdaExpression(func, func.span);
-    } else {
-      _error('expected function');
-    }
-  }
-
-  /** Converts a single expression into a formal or list of formals. */
-  _makeFormal(expr) {
-    if (expr is VarExpression) {
-      return new FormalNode(false, false, null, expr.name, null, expr.span);
-    } else if (expr is DeclaredIdentifier) {
-      return new FormalNode(false, false, expr.type, expr.name, null,
-        expr.span);
-    } else if (_isBin(expr, TokenKind.ASSIGN) &&
-               (expr.x is DeclaredIdentifier)) {
-      DeclaredIdentifier di = expr.x; // TODO(jimhug): inference should handle!
-      return new FormalNode(false, false, di.type, di.name, expr.y,
-        expr.span);
-    } else if (_isBin(expr, TokenKind.LT)) {
-      // special signaling value to merge with next arg.
-      return null;
-    } else if (expr is ListExpression) {
-      return _makeFormalsFromList(expr);
-    } else {
-      _error('expected formal', expr.span);
-    }
-  }
-
-  _makeFormalsFromList(expr) {
-    if (expr.isConst) {
-      _error('expected formal, but found "const"', expr.span);
-    } else if (expr.type != null) {
-      _error('expected formal, but found generic type arguments',
-         expr.type.span);
-    }
-
-    return _makeFormalsFromExpressions(expr.values, allowOptional:false);
-  }
-
-  /** Converts a list of arguments into a list of formals. */
-  _makeFormals(arguments) {
-    var expressions = [];
-    for (int i = 0; i < arguments.length; i++) {
-      final arg = arguments[i];
-      if (arg.label != null) {
-        _error('expected formal, but found ":"');
-      }
-      expressions.add(arg.value);
-    }
-    return _makeFormalsFromExpressions(expressions, allowOptional:true);
-  }
-
-  /** Converts a list of expressions into a list of formals. */
-  _makeFormalsFromExpressions(expressions, [bool allowOptional]) {
-    var formals = [];
-    for (int i = 0; i < expressions.length; i++) {
-      var formal = _makeFormal(expressions[i]);
-      if (formal == null) {
-        // special signal that we have the A<C case
-        var baseType = _makeType(expressions[i].x);
-        var typeParams = [_makeType(expressions[i].y)];
-        i++;
-        while (i < expressions.length) {
-          var expr = expressions[i++];
-          // Looking for D > m closer
-          if (_isBin(expr, TokenKind.GT)) {
-            typeParams.add(_makeType(expr.x));
-            var type = new GenericTypeReference(baseType, typeParams, 0,
-              _makeSpan(baseType.span.start));
-            var name = null;
-            if (expr.y is VarExpression) {
-              // TODO(jimhug): Should be handled by inference!
-              VarExpression ve = expr.y;
-              name = ve.name;
-            } else {
-              _error('expected formal', expr.span);
-            }
-            formal = new FormalNode(false, false, type, name, null,
-              _makeSpan(expressions[0].span.start));
-            break;
-          } else {
-            typeParams.add(_makeType(expr));
-          }
-        }
-        formals.add(formal);
-
-      } else if (formal is List) {
-        formals.addAll(formal);
-        if (!allowOptional) {
-          _error('unexpected nested optional formal', expressions[i].span);
-        }
-
-      } else {
-        formals.add(formal);
-      }
-    }
-    return formals;
+    return new LambdaExpression(func, func.span);
   }
 
   /** Converts an expression to a [DeclaredIdentifier]. */
   _makeDeclaredIdentifier(e) {
     if (e is VarExpression) {
       return new DeclaredIdentifier(null, e.name, e.span);
     } else if (e is DeclaredIdentifier) {
       return e;
     } else {
       _error('expected declared identifier');
       return new DeclaredIdentifier(null, null, e.span);
     }
   }
 
   /** Converts an expression into a label. */
   _makeLabel(expr) {
     if (expr is VarExpression) {
       return expr.name;
     } else {
       _errorExpected('label');
       return null;
     }
   }
 }
+
+
+class DivertedTokenSource implements TokenSource {

[jimhug, 2011/10/31 14:16:46]

Now that you've provided this, I'd love to do an experiment where we first
Tokenize and then parse the file.  I can' work out in my head how that will turn
out  - since I think it will have to do with cache contention issues more than
anything else.

+  final List tokens;
+  final Parser parser;
+  final TokenSource previousTokenizer;
+  DivertedTokenSource(this.tokens, this.parser, this.previousTokenizer);
+
+  int _pos = 0;
+  next() {
+    var token = tokens[_pos];
+    ++_pos;

[jimhug, 2011/10/31 14:16:46]

Style: prefer _pos++ for this bare increment.

+    if (_pos == tokens.length) {
+      parser.tokenizer = previousTokenizer;
+    }
+    return token;
+  }
+}