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 40 matching lines @@
  * 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? :].
  */
 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;
   }
 
+  bool isValidTypeArguments(Token token, {bool requireParenthesis: false}) {
+    // 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:

[ahe, 2016/02/23 08:05:27]

The scanner should already have computed this for you. See:

ArrayBasedScanner.appendGtGt

For example, in the case `foo(a < 0, b >> 2)`, the token representing `<`, will
have endGroup null, and thus cannot be a type argument.

In the case, `foo(a < 0, b > 2)`, again you don't need to count the angle
brackets. All you need to do is look at endGroup.next.

Once you take advantage of the fact that you can look ahead to see what comes
after the closing '>', you should be able to recursively answer this question
which should be simpler and let you remove the TODO. In addition, you'll be
making it easier to actually create the AST nodes required long term.

[eernst, 2016/02/23 12:40:45]

Ah, yes, I hadn't looked at that.
But in `foo(a<B, C<D, E>>(2))`, the second '<' will have `endGroup` null, so I
cannot immediately use `endGroup == null` to determine whether or not a given
'<' matches any '>'. I would then declare "Nope,  `<B, C<D, E>>` is not a
`typeArguments`" and give up, incorrectly.
But even if I do confirm at '<' that there is a matching '>', it does not help
me much. Example: with `foo(a < b, 2 > c)` we need to detect that the matching
'>' occurs after '2', because this means that `< b, 2 >` could not be a
`typeArguments`, whereas `<B, C>` in `foo(a<B, C>(d))` should be accepted. The
point is that we need to check that we have a '<'/'>'-balanced token sequence
consisting of allowed tokens (and we haven't yet seen the counter-example '2'
when we see '<', so we must introduce accounting like "make sure that we step
far enough to have seen the matching '>' for any '<' seen so far" as well as
"make sure we don't have any non-allowed tokens like '2' during this stepping
process".

I'm afraid it would be more complex to take into account that '<' has a matching
'>' and then do all the accounting to make sure that we can detect the
difference between these two examples.

In any case, we cannot just "jump to the end" of anything, because we need to
confirm, token by token, that we are looking at a sequence of
type-arguments-compatible tokens.

I'll think about it, but I cannot immediately see how the `endGroup` info can be
of much help here.
Certainly, we'll need to create the ASTs very soon, but that won't solve this
problem: What we are doing here is checking at the point where the potential
`typeArguments` begins that it does indeed parse correctly as a `typeArguments`,
such that we can call `parseTypeArguments`; if it does not parse correctly then
we just back up and parse it as a binary expression ('<' as "less-than").

There is no finite limit on the amount of lookahead we need in order to do this,
so we need to use something like `isValidTypeArguments` which is able to peek an
unlimited number of tokens into the future. We could of course use a recursive
descent approach (as we would surely have to do if we were to implement
something like `isValidMethod` or even `isValidExpression`), but in order to do
that we'd have to find a solution to the problem that parsing can change the
token sequence ['>>'] into ['>', '>'], whereas `isValid..` cannot have
side-effects like that (I think).

+    //
+    //   typeArguments  ::= '<' typeList '>'
+    //   typeList       ::= type (',' type)*
+    //   type           ::= typeName typeArguments?
+    //   typeName       ::= qualified
+    //   qualified      ::= identifier ('.' identifier)?
+    //
+    // The point is that we check for parenthesis correctness for '<'/'>' plus
+    // membership of the intersection between the following regular languages:
+    //
+    //   anything starting with '<' and ending with '>'
+    //   (identifier | (identifier '.' identifier) | ',' | '<' | '>' | '>>')*
+    //
+    // 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.
+    // If that property does not hold then we will reject some correct programs.
+    if (optional('<', token)) {
+      int angleBracketLevel = 1;
+      token = token.next;
+      while (!identical(token.kind, EOF_TOKEN) && angleBracketLevel > 0) {
+        // Invariant: `angleBracketLevel` is #'<' - #'>' from initial token

[ahe, 2016/02/23 08:05:27]

What does #'<' mean?

[eernst, 2016/02/23 12:40:45]

The number of '<' tokens. Added an explanation to the comment.

+        // to `token`, both included, and considering ['>>'] as ['>', '>'].

[ahe, 2016/02/23 08:05:27]

I don't think ['>>'] is a valid reference.

[eernst, 2016/02/23 12:40:45]

Ah, of course not. It is intended to be the sequence of tokens of length one
whose only element is '>>'. Rephrased to use words.

+        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;

[floitsch, 2016/02/22 12:45:20]

couldn't you treat the "comma" the same way as the "." ?

[eernst, 2016/02/22 18:02:51]

Not immediately: The comma separates complex constructs (types) whereas the
period only separates identifiers. This means that we can make `identifier` and
`identifier.identifier` work as "atoms" such that we don't accept things like
`<.identifier`, which makes the over-approximation of the actual language more
tight. I don't think there is an easy analogous way to make it tighter around
commas.

It is possible, though, that we should use a general parsing strategy rather
than a "near regular expression" check, if the over-approximation turns out to
be too loose. But that would presumably require a duplication of a lot of
parsing methods, such that we can parse `typeArguments` in general without
splitting ['>>'] to ['>', '>']. Alternatively, we could split '>>', but remember
where we did it and then undo it if the `isValidTypeArguments` call returns
false.

+          case LT_TOKEN: angleBracketLevel++; break;
+          case GT_TOKEN: angleBracketLevel--; break;
+          case GT_GT_TOKEN: angleBracketLevel -= 2; break;
+          default: return false;
+        }
+        token = token.next;
+      }
+      if (angleBracketLevel != 0) return false;
+      return requireParenthesis
+          ? token.kind == OPEN_PAREN_TOKEN
+          : true;
+    } else {
+      return false;
+    }
+  }
+
   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);
+    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: false}) {
+    if (isValidTypeArguments(token, requireParenthesis: requireParenthesis)) {
+      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) {

[floitsch, 2016/02/22 12:45:20]

All these duplicated parseAndIgnore make me think that it's easier if you just
ignore them in the listener.

[eernst, 2016/02/22 18:02:51]

Will probably have to do that in the next step anyway, more or less, since it
needs to know about the declared types and make them work as `dynamic`.
Presumably it makes sense to postpone it until I've studied enough of the
compiler to know how to do that.

+    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;
       } while (optional(',', token));
       Token next = token.next;
       if (identical(token.stringValue, '>>')) {
         token = new SymbolToken(GT_INFO, token.charOffset);
         token.next = new SymbolToken(GT_INFO, token.charOffset + 1);
         token.next.next = next;
-      } else if (identical(token.stringValue, '>>>')) {
-        token = new SymbolToken(GT_INFO, token.charOffset);
-        token.next = new SymbolToken(GT_GT_INFO, token.charOffset + 1);
-        token.next.next = next;
       }
       endStuff(count, begin, token);
       return expect('>', token);
     }
     handleNoStuff(token);
     return token;
   }
 
   Token parseTopLevelMember(Token token) {
     Token start = token;
@@ skipping 210 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);
+    }
     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);
   }
 }