First step of support for parsing and ignoring generic methods.

pkg/compiler/lib/src/parser/parser.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 dart2js.parser;
 
 import '../common.dart';
 import '../tokens/keyword.dart' show
     Keyword;
 import '../tokens/precedence.dart' show
@@ skipping 21 matching lines @@
     KeywordToken,
     SymbolToken,
     Token;
 import '../tokens/token_constants.dart' show
     BAD_INPUT_TOKEN,
     COMMA_TOKEN,
     DOUBLE_TOKEN,
     EOF_TOKEN,
     EQ_TOKEN,
     FUNCTION_TOKEN,
+    GT_TOKEN,
+    GT_GT_TOKEN,
     HASH_TOKEN,
     HEXADECIMAL_TOKEN,
     IDENTIFIER_TOKEN,
     INT_TOKEN,
     KEYWORD_TOKEN,
     LT_TOKEN,
     OPEN_CURLY_BRACKET_TOKEN,
     OPEN_PAREN_TOKEN,
     OPEN_SQUARE_BRACKET_TOKEN,
     PERIOD_TOKEN,
@@ skipping 35 matching lines @@
  *
  * Parse methods generate events (by calling methods on [listener])
  * and return the next token to parse. Peek methods do not generate
  * events (except for errors) and may return null.
  *
  * Parse methods are generally named parseGrammarProductionSuffix. The
  * suffix can be one of "opt", or "star". "opt" means zero or one
  * matches, "star" means zero or more matches. For example,
  * [parseMetadataStar] corresponds to this grammar snippet: [:
  * metadata* :], and [parseTypeOpt] corresponds to: [: type? :].
+ *
+ * On the extension to support generic methods:
+ *
+ * The syntactic conflict associated with relational expressions is resolved
+ * in favor of generic invocations (for instance, with `foo(m<B, C>(3))` we
+ * parse it as an invocation of `m` with type arguments `B, C` and value
+ * argument `3`, not as two boolean arguments passed to `foo`. It is expected
+ * that this situation is occurs rarely in practice, especially because a comma
+ * or ')' will delimit the expression where we have `3` in the example,
+ * which means that it won't need to be wrapped in parentheses. The work-around
+ * is to add parentheses around the last relational expression (i.e., `(C>(3))`
+ * in the example).
+ *
+ * Relative to the DEP #22 proposal, there is no support for currying
+ * invocations (that is, we cannot evalate a type like `myMethod<T,S>` to
+ * obtain a closure which is non-generic and which will pass the actual values
+ * of `T` and `S` in the given context as type arguments).
  */
 class Parser {
   final Listener listener;
   bool mayParseFunctionExpressions = true;
   final bool enableConditionalDirectives;
+  final bool enableGenericMethods;
   bool asyncAwaitKeywordsEnabled;
 
   Parser(this.listener,
       {this.enableConditionalDirectives: false,
-       this.asyncAwaitKeywordsEnabled: false});
+       this.asyncAwaitKeywordsEnabled: false,
+       this.enableGenericMethods: false});
 
   Token parseUnit(Token token) {
     listener.beginCompilationUnit(token);
     int count = 0;
     while (!identical(token.kind, EOF_TOKEN)) {
       token = parseTopLevelDeclaration(token);
       listener.endTopLevelDeclaration(token);
       count++;
     }
     listener.endCompilationUnit(count, token);
@@ skipping 400 matching lines @@
     if (identical(kind, KEYWORD_TOKEN)) {
       Keyword keyword = (token as KeywordToken).keyword;
       String value = keyword.syntax;
       return keyword.isPseudo
           || (identical(value, 'dynamic'))
           || (identical(value, 'void'));
     }
     return false;
   }
 
+  /// Performs lookahead to see whether the next tokens can be type arguments.
+  ///
+  /// This method performs a lookahead (parsing without listener events)
+  /// using a near-regular language to determine a conservative approximation
+  /// of whether the next tokens can be a list of actual type arguments.
+  ///
+  /// It is conservative in the sense that it does not return true in cases
+  /// where the next tokens are a correct construct which is not an actual type
+  /// argument list (because we would then reject a correct program). But it
+  /// is OK to return either true or false when the next tokens are definitely
+  /// not correct (because this just causes a choice of one error message where
+  /// another one could also have been chosen). This allows for an imprecise
+  /// parsing approach, which is the reason why we can use a near-regular
+  /// language.
+  ///
+  /// The language which is recognized contains atoms consisting of a few
+  /// tokens:
+  ///
+  ///   (identifier | (identifier '.' identifier) | ',' | '<' | '>' | '>>')*
+  ///
+  /// Moreover, it is enforced that it starts with '<', ends with '>' or '>>',
+  /// and that the angle brackets are balanced (where '>>' counts for two).
+  ///
+  /// Exceptions to this are controlled with the named arguments: If
+  /// [requireParenthesis] is true then it is required that the first token
+  /// after the successfully recognized type argument list is '(', and if
+  /// [allowImbalance] is true then one extra case is allowed: The recognized
+  /// type argument list may end in '>>' such that the final '>' creates an
+  /// imbalance (that is, it would have been balanced if we had had '>' rather
+  /// than '>>').
+  ///
+  /// The former is used to reduce the amount of recognized constructs when
+  /// it is known that the context requires the '(', and the latter is used to
+  /// allow for the '>>' balance violation when the context may be another type
+  /// argument list.
+  //
+  // Obviously, every correct `typeArguments` will pass this test. However,
+  // some incorrect ones will also pass, e.g., `<K,<<><>>,>`. This should be
+  // safe, but the real solution is of course the following:
+  //
+  // TODO(eernst): Prove that if a token sequence is accepted by this test,
+  // but it is not a correct `typeArguments` then it is a syntax error rather
+  // than a correct continuation of the program that does not contain a
+  // `typeArguments` construct at this point.
+  bool isValidTypeArguments(Token token,
+      {bool requireParenthesis, bool allowImbalance}) {
+    // To avoid changing the token stream during an investigation of whether
+    // the parser is looking at a `typeArguments` construct, we do not replace
+    // one `>>` token by two `>` tokens (which would destroy a correct
+    // expression like `foo(a < 0, b >> 2)`). Instead, we count levels for the
+    // '<'/'>' brackets directly. This makes sense because the type argument
+    // sublanguage is so tiny:
+    //
+    //   typeArguments  ::= '<' typeList '>'
+    //   typeList       ::= type (',' type)*
+    //   type           ::= typeName typeArguments?
+    //   typeName       ::= qualified
+    //   qualified      ::= identifier ('.' identifier)?
+    //
+    // Clearly, any correct `typeArguments` construct will belong to the
+    // following regular language:
+    //
+    //   (identifier | (identifier '.' identifier) | ',' | '<' | '>' | '>>')*
+    //
+    // So we check for that, and also for the context free language that just
+    // requires '<'/'>' to be balanced, and the first/last token to be '<'
+    // and '>' or '>>', respectively. The two named arguments are used to
+    // adjust the language slightly for context as described.
+    if (!optional('<', token)) return false;
+    int angleBracketLevel = 1;
+    token = token.next;
+    while (!identical(token.kind, EOF_TOKEN) && angleBracketLevel > 0) {
+      // Invariant: `angleBracketLevel` is #'<' - #'>' from initial token
+      // to `token`, both included, where #'x' is the number of tokens with
+      // `stringValue` 'x'; in this computation, we consider the one-element
+      // token sequence '>>' equivalent to the two element sequence '>', '>'.
+      final int kind = token.kind;
+      switch (kind) {
+        case IDENTIFIER_TOKEN:
+          if (optional('.', token.next)) {
+            token = token.next.next;
+            if (token.kind != IDENTIFIER_TOKEN) return false;
+          }
+          break;
+        case COMMA_TOKEN: break;
+        case LT_TOKEN: angleBracketLevel++; break;
+        case GT_TOKEN: angleBracketLevel--; break;
+        case GT_GT_TOKEN: angleBracketLevel -= 2; break;
+        default: return false;
+      }
+      token = token.next;
+    }
+    if ((allowImbalance && angleBracketLevel > 0) ||
+        (!allowImbalance && angleBracketLevel != 0)) {
+      return false;
+    }
+    return requireParenthesis
+        ? token.kind == OPEN_PAREN_TOKEN
+        : true;
+  }
+
   Token parseQualified(Token token) {
     token = parseIdentifier(token);
     while (optional('.', token)) {
       token = parseQualifiedRest(token);
     }
     return token;
   }
 
   Token parseQualifiedRestOpt(Token token) {
     if (optional('.', token)) {
       return parseQualifiedRest(token);
     } else {
       return token;
     }
   }
 
+  Token parseAndIgnoreQualifiedRestOpt(Token token) {
+    if (optional('.', token)) {
+      return parseAndIgnoreQualifiedRest(token);
+    } else {
+      return token;
+    }
+  }
+
   Token parseQualifiedRest(Token token) {
     assert(optional('.', token));
     Token period = token;
     token = parseIdentifier(token.next);
     listener.handleQualified(period);
     return token;
   }
 
+  Token parseAndIgnoreQualifiedRest(Token token) {
+    assert(optional('.', token));
+    token = parseAndIgnoreIdentifier(token.next);
+    return token;
+  }
+
   Token skipBlock(Token token) {
     if (!optional('{', token)) {
       return listener.expectedBlockToSkip(token);
     }
     BeginGroupToken beginGroupToken = token;
     Token endGroup = beginGroupToken.endGroup;
     if (endGroup == null) {
       return listener.unmatched(beginGroupToken);
     } else if (!identical(endGroup.kind, Characters.$CLOSE_CURLY_BRACKET)) {
       return listener.unmatched(beginGroupToken);
@@ skipping 111 matching lines @@
   }
 
   Token parseIdentifier(Token token) {
     if (!token.isIdentifier()) {
       token = listener.expectedIdentifier(token);
     }
     listener.handleIdentifier(token);
     return token.next;
   }
 
+  Token parseAndIgnoreIdentifier(Token token) {
+    if (!token.isIdentifier()) {
+      token = listener.expectedIdentifier(token);
+    }
+    return token.next;
+  }
+
   Token expect(String string, Token token) {
     if (!identical(string, token.stringValue)) {
       return listener.expected(string, token);
     }
     return token.next;
   }
 
   Token parseTypeVariable(Token token) {
     listener.beginTypeVariable(token);
     token = parseIdentifier(token);
     if (optional('extends', token)) {
       token = parseType(token.next);
     } else {
       listener.handleNoType(token);
     }
     listener.endTypeVariable(token);
     return token;
   }
 
+  Token parseAndIgnoreTypeParameter(Token token) {
+    token = parseAndIgnoreIdentifier(token);
+    if (optional('extends', token)) {
+      token = parseAndIgnoreType(token.next);
+    }
+    return token;
+  }
+
   /**
    * Returns true if the stringValue of the [token] is [value].
    */
   bool optional(String value, Token token) {
     return identical(value, token.stringValue);
   }
 
   /**
    * Returns true if the stringValue of the [token] is either [value1],
    * [value2], or [value3].
@@ skipping 30 matching lines @@
       token = parseIdentifier(token);
       token = parseQualifiedRestOpt(token);
     } else {
       token = listener.expectedType(token);
     }
     token = parseTypeArgumentsOpt(token);
     listener.endType(begin, token);
     return token;
   }
 
+  Token parseAndIgnoreType(Token token) {
+    if (isValidTypeReference(token)) {
+      token = parseAndIgnoreIdentifier(token);
+      token = parseAndIgnoreQualifiedRestOpt(token);
+    } else {
+      token = listener.expectedType(token);
+    }
+    token = parseAndIgnoreTypeArgumentsOpt(token,
+        requireParenthesis: false, allowImbalance: true);
+    return token;
+  }
+
   Token parseTypeArgumentsOpt(Token token) {
     return parseStuff(token,
                       (t) => listener.beginTypeArguments(t),
                       (t) => parseType(t),
                       (c, bt, et) => listener.endTypeArguments(c, bt, et),
                       (t) => listener.handleNoTypeArguments(t));
   }
 
+  Token parseAndIgnoreTypeArgumentsOpt(Token token,
+      {bool requireParenthesis, bool allowImbalance}) {
+    if (isValidTypeArguments(
+        token,
+        requireParenthesis: requireParenthesis,
+        allowImbalance: allowImbalance)) {
+      return parseStuff(token,
+                        (t) {},
+                        (t) => parseAndIgnoreType(t),
+                        (c, bt, et) {},
+                        (t) {});
+    } else {
+      return token;
+    }
+  }
+
   Token parseTypeVariablesOpt(Token token) {
     return parseStuff(token,
                       (t) => listener.beginTypeVariables(t),
                       (t) => parseTypeVariable(t),
                       (c, bt, et) => listener.endTypeVariables(c, bt, et),
                       (t) => listener.handleNoTypeVariables(t));
   }
 
+  Token parseAndIgnoreTypeParametersOpt(Token token) {
+    return parseStuff(token,
+                      (t) {},
+                      (t) => parseAndIgnoreTypeParameter(t),
+                      (c, bt, et) {},
+                      (t) {});
+  }
+
   // TODO(ahe): Clean this up.
   Token parseStuff(Token token, Function beginStuff, Function stuffParser,
                    Function endStuff, Function handleNoStuff) {
     if (optional('<', token)) {
       Token begin = token;
       beginStuff(begin);
       int count = 0;
       do {
         token = stuffParser(token.next);
         ++count;
@@ skipping 226 matching lines @@
       listener.handleModifiers(0);
     }
 
     if (type == null) {
       listener.handleNoType(name);
     } else {
       parseReturnTypeOpt(type);
     }
     Token token = parseIdentifier(name);
 
+    if (enableGenericMethods && getOrSet == null) {
+      token = parseAndIgnoreTypeParametersOpt(token);
+    }
     token = parseFormalParametersOpt(token);
     bool previousAsyncAwaitKeywordsEnabled = asyncAwaitKeywordsEnabled;
     token = parseAsyncModifier(token);
     token = parseFunctionBody(token, false, externalModifier != null);
     asyncAwaitKeywordsEnabled = previousAsyncAwaitKeywordsEnabled;
     Token endToken = token;
     token = token.next;
     if (token.kind == BAD_INPUT_TOKEN) {
       token = listener.unexpected(token);
     }
@@ skipping 288 matching lines @@
       }
     }
 
     token = afterName;
     bool isField;
     while (true) {
       // Loop to allow the listener to rewrite the token stream for
       // error handling.
       final String value = token.stringValue;
       if ((identical(value, '(')) || (identical(value, '.'))
-          || (identical(value, '{')) || (identical(value, '=>'))) {
+          || (identical(value, '{')) || (identical(value, '=>'))
+          || (enableGenericMethods && identical(value, '<'))) {
         isField = false;
         break;
       } else if (identical(value, ';')) {
         if (getOrSet != null) {
           // If we found a "get" keyword, this must be an abstract
           // getter.
           isField = (!identical(getOrSet.stringValue, 'get'));
           // TODO(ahe): This feels like a hack.
         } else {
           isField = true;
@@ skipping 80 matching lines @@
       if (staticModifier != null) {
         listener.reportError(
             staticModifier, MessageKind.EXTRANEOUS_MODIFIER,
             {'modifier': staticModifier});
       }
     } else {
       token = parseIdentifier(name);
     }
 
     token = parseQualifiedRestOpt(token);
+    if (enableGenericMethods && getOrSet == null) {
+      token = parseAndIgnoreTypeParametersOpt(token);
+    }
     token = parseFormalParametersOpt(token);
     token = parseInitializersOpt(token);
     bool previousAsyncAwaitKeywordsEnabled = asyncAwaitKeywordsEnabled;
     token = parseAsyncModifier(token);
     if (optional('=', token)) {
       token = parseRedirectingFactoryBody(token);
     } else {
       token = parseFunctionBody(
           token, false, staticModifier == null || externalModifier != null);
     }
@@ skipping 66 matching lines @@
       }
       listener.beginFunctionName(token);
       if (optional('operator', token)) {
         token = parseOperatorName(token);
       } else {
         token = parseIdentifier(token);
       }
     }
     token = parseQualifiedRestOpt(token);
     listener.endFunctionName(token);
+    if (enableGenericMethods && getOrSet == null) {
+      token = parseAndIgnoreTypeParametersOpt(token);
+    }
     token = parseFormalParametersOpt(token);
     token = parseInitializersOpt(token);
     bool previousAsyncAwaitKeywordsEnabled = asyncAwaitKeywordsEnabled;
     token = parseAsyncModifier(token);
     if (optional('=', token)) {
       token = parseRedirectingFactoryBody(token);
     } else {
       token = parseFunctionBody(token, false, true);
     }
     asyncAwaitKeywordsEnabled = previousAsyncAwaitKeywordsEnabled;
@@ skipping 809 matching lines @@
   }
 
   Token parseLiteralNull(Token token) {
     listener.handleLiteralNull(token);
     return token.next;
   }
 
   Token parseSend(Token token) {
     listener.beginSend(token);
     token = parseIdentifier(token);
+    if (enableGenericMethods) {
+      token = parseAndIgnoreTypeArgumentsOpt(token,
+          requireParenthesis: true, allowImbalance: false);
+    }
     token = parseArgumentsOpt(token);
     listener.endSend(token);
     return token;
   }
 
   Token parseArgumentsOpt(Token token) {
     if (!optional('(', token)) {
       listener.handleNoArguments(token);
       return token;
     } else {
@@ skipping 431 matching lines @@
     }
     listener.handleContinueStatement(hasTarget, continueKeyword, token);
     return expectSemicolon(token);
   }
 
   Token parseEmptyStatement(Token token) {
     listener.handleEmptyStatement(token);
     return expectSemicolon(token);
   }
 }