Issue 25558. Report an error, but don't crash when AST it too deep.

pkg/analyzer/lib/src/generated/parser.dart

 // Copyright (c) 2014, 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 analyzer.src.generated.parser;
 
 import 'dart:collection';
 import "dart:math" as math;
 
 import 'package:analyzer/dart/ast/ast.dart';
@@ skipping 152 matching lines @@
   static String _AWAIT = Keyword.AWAIT.syntax;
 
   static String _HIDE = Keyword.HIDE.syntax;
 
   static String _SHOW = Keyword.SHOW.syntax;
 
   static String SYNC = Keyword.SYNC.syntax;
 
   static String _YIELD = Keyword.YIELD.syntax;
 
+  static const int _MAX_TREE_DEPTH = 300;
+
   /**
    * The source being parsed.
    */
   final Source _source;
 
   /**
    * The error listener that will be informed of any errors that are found
    * during the parse.
    */
   final AnalysisErrorListener _errorListener;
@@ skipping 25 matching lines @@
    * A flag indicating whether parser is to parse function bodies.
    */
   bool _parseFunctionBodies = true;
 
   /**
    * The next token to be parsed.
    */
   Token _currentToken;
 
   /**
+   * The depth of the current AST. When this depth is too high, so we're at the
+   * risk of overflowing the stack, we stop parsing and report an error.
+   */
+  int _treeDepth = 0;
+
+  /**
    * A flag indicating whether the parser is currently in a function body marked
    * as being 'async'.
    */
   bool _inAsync = false;
 
   /**
    * A flag indicating whether the parser is currently in a function body marked
    * (by a star) as being a generator.
    */
   bool _inGenerator = false;
@@ skipping 1725 matching lines @@
         }
         directives.add(directive);
       } else if (type == TokenType.SEMICOLON) {
         // TODO(brianwilkerson) Consider moving this error detection into
         // _parseCompilationUnitMember (in the places where EXPECTED_EXECUTABLE
         // is being generated).
         _reportErrorForToken(ParserErrorCode.UNEXPECTED_TOKEN, _currentToken,
             [_currentToken.lexeme]);
         _advance();
       } else {
-        CompilationUnitMember member =
-            parseCompilationUnitMember(commentAndMetadata);
+        CompilationUnitMember member;
+        try {
+          member = parseCompilationUnitMember(commentAndMetadata);
+        } on _TooDeepTreeError {
+          _reportErrorForToken(ParserErrorCode.STACK_OVERFLOW, _currentToken);
+          Token eof = new Token(TokenType.EOF, 0);
+          eof.previous = eof;
+          eof.setNext(eof);
+          return astFactory.compilationUnit(eof, null, null, null, eof);
+        }
         if (member != null) {
           declarations.add(member);
         }
       }
       if (identical(_currentToken, memberStart)) {
         _reportErrorForToken(ParserErrorCode.UNEXPECTED_TOKEN, _currentToken,
             [_currentToken.lexeme]);
         _advance();
         while (!_matches(TokenType.EOF) &&
             !_couldBeStartOfCompilationUnitMember()) {
@@ skipping 730 matching lines @@
   /**
    * Parse an expression that might contain a cascade. Return the expression
    * that was parsed.
    *
    *     expression ::=
    *         assignableExpression assignmentOperator expression
    *       | conditionalExpression cascadeSection*
    *       | throwExpression
    */
   Expression parseExpression2() {
-    Keyword keyword = _currentToken.keyword;
-    if (keyword == Keyword.THROW) {
-      return parseThrowExpression();
-    } else if (keyword == Keyword.RETHROW) {
-      // TODO(brianwilkerson) Rethrow is a statement again.
-      return parseRethrowExpression();
+    if (_treeDepth > _MAX_TREE_DEPTH) {
+      throw new _TooDeepTreeError();
     }
-    //
-    // assignableExpression is a subset of conditionalExpression, so we can
-    // parse a conditional expression and then determine whether it is followed
-    // by an assignmentOperator, checking for conformance to the restricted
-    // grammar after making that determination.
-    //
-    Expression expression = parseConditionalExpression();
-    TokenType type = _currentToken.type;
-    if (type == TokenType.PERIOD_PERIOD) {
-      List<Expression> cascadeSections = <Expression>[];
-      do {
-        Expression section = parseCascadeSection();
-        if (section != null) {
-          cascadeSections.add(section);
-        }
-      } while (_currentToken.type == TokenType.PERIOD_PERIOD);
-      return astFactory.cascadeExpression(expression, cascadeSections);
-    } else if (type.isAssignmentOperator) {
-      Token operator = getAndAdvance();
-      _ensureAssignable(expression);
-      return astFactory.assignmentExpression(
-          expression, operator, parseExpression2());
+    _treeDepth++;
+    try {
+      Keyword keyword = _currentToken.keyword;
+      if (keyword == Keyword.THROW) {
+        return parseThrowExpression();
+      } else if (keyword == Keyword.RETHROW) {
+        // TODO(brianwilkerson) Rethrow is a statement again.
+        return parseRethrowExpression();
+      }
+      //
+      // assignableExpression is a subset of conditionalExpression, so we can
+      // parse a conditional expression and then determine whether it is followed
+      // by an assignmentOperator, checking for conformance to the restricted
+      // grammar after making that determination.
+      //
+      Expression expression = parseConditionalExpression();
+      TokenType type = _currentToken.type;
+      if (type == TokenType.PERIOD_PERIOD) {
+        List<Expression> cascadeSections = <Expression>[];
+        do {
+          Expression section = parseCascadeSection();
+          if (section != null) {
+            cascadeSections.add(section);
+          }
+        } while (_currentToken.type == TokenType.PERIOD_PERIOD);
+        return astFactory.cascadeExpression(expression, cascadeSections);
+      } else if (type.isAssignmentOperator) {
+        Token operator = getAndAdvance();
+        _ensureAssignable(expression);
+        return astFactory.assignmentExpression(
+            expression, operator, parseExpression2());
+      }
+      return expression;
+    } finally {
+      _treeDepth--;
     }
-    return expression;
   }
 
   /**
    * Parse a list of expressions. Return the expression that was parsed.
    *
    *     expressionList ::=
    *         expression (',' expression)*
    */
   List<Expression> parseExpressionList() {
     List<Expression> expressions = <Expression>[parseExpression2()];
@@ skipping 2032 matching lines @@
     return parseStatement2();
   }
 
   /**
    * Parse a statement. Return the statement that was parsed.
    *
    *     statement ::=
    *         label* nonLabeledStatement
    */
   Statement parseStatement2() {
-    List<Label> labels = null;
-    while (_matchesIdentifier() && _currentToken.next.type == TokenType.COLON) {
-      Label label = parseLabel(isDeclaration: true);
+    if (_treeDepth > _MAX_TREE_DEPTH) {
+      throw new _TooDeepTreeError();
+    }
+    _treeDepth++;
+    try {
+      List<Label> labels = null;
+      while (
+          _matchesIdentifier() && _currentToken.next.type == TokenType.COLON) {
+        Label label = parseLabel(isDeclaration: true);
+        if (labels == null) {
+          labels = <Label>[label];
+        } else {
+          labels.add(label);
+        }
+      }
+      Statement statement = parseNonLabeledStatement();
       if (labels == null) {
-        labels = <Label>[label];
-      } else {
-        labels.add(label);
+        return statement;
       }
+      return astFactory.labeledStatement(labels, statement);
+    } finally {
+      _treeDepth--;
     }
-    Statement statement = parseNonLabeledStatement();
-    if (labels == null) {
-      return statement;
-    }
-    return astFactory.labeledStatement(labels, statement);
   }
 
   /**
    * Parse a sequence of statements, starting with the given [token]. Return the
    * statements that were parsed, or `null` if the tokens do not represent a
    * recognizable sequence of statements.
    */
   List<Statement> parseStatements(Token token) {
     _currentToken = token;
     return _parseStatementList();
@@ skipping 3738 matching lines @@
     }
     if (modifiers.finalKeyword != null) {
       _reportErrorForToken(
           ParserErrorCode.FINAL_TYPEDEF, modifiers.finalKeyword);
     }
     if (modifiers.varKeyword != null) {
       _reportErrorForToken(ParserErrorCode.VAR_TYPEDEF, modifiers.varKeyword);
     }
   }
 }
+
+/**
+ * Instances of this class are thrown when the parser detects that AST has
+ * too many nested expressions to be parsed safely and avoid possibility of
+ * [StackOverflowError] in the parser or during later analysis.
+ */
+class _TooDeepTreeError {}