src/gn/parser.cc

// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "gn/parser.h"

#include <memory>
#include <utility>

#include "base/logging.h"
#include "gn/functions.h"
#include "gn/operators.h"
#include "gn/token.h"

const char kGrammar_Help[] =
    R"*(Language and grammar for GN build files

Tokens

  GN build files are read as sequences of tokens.  While splitting the file
  into tokens, the next token is the longest sequence of characters that form a
  valid token.

White space and comments

  White space is comprised of spaces (U+0020), horizontal tabs (U+0009),
  carriage returns (U+000D), and newlines (U+000A).

  Comments start at the character "#" and stop at the next newline.

  White space and comments are ignored except that they may separate tokens
  that would otherwise combine into a single token.

Identifiers

  Identifiers name variables and functions.

      identifier = letter { letter | digit } .
      letter     = "A" ... "Z" | "a" ... "z" | "_" .
      digit      = "0" ... "9" .

Keywords

  The following keywords are reserved and may not be used as identifiers:

          else    false   if      true

Integer literals

  An integer literal represents a decimal integer value.

      integer = [ "-" ] digit { digit } .

  Leading zeros and negative zero are disallowed.

String literals

  A string literal represents a string value consisting of the quoted
  characters with possible escape sequences and variable expansions.

      string           = `"` { char | escape | expansion } `"` .
      escape           = `\` ( "$" | `"` | char ) .
      BracketExpansion = "{" ( identifier | ArrayAccess | ScopeAccess ) "}" .
      Hex              = "0x" [0-9A-Fa-f][0-9A-Fa-f]
      expansion        = "$" ( identifier | BracketExpansion | Hex ) .
      char             = /* any character except "$", `"`, or newline */ .

  After a backslash, certain sequences represent special characters:

          \"    U+0022    quotation mark
          \$    U+0024    dollar sign
          \\    U+005C    backslash

  All other backslashes represent themselves.

  To insert an arbitrary byte value, use $0xFF. For example, to insert a
  newline character: "Line one$0x0ALine two".

  An expansion will evaluate the variable following the '$' and insert a
  stringified version of it into the result. For example, to concat two path
  components with a slash separating them:
    "$var_one/$var_two"
  Use the "${var_one}" format to be explicitly deliniate the variable for
  otherwise-ambiguous cases.

Punctuation

  The following character sequences represent punctuation:

          +       +=      ==      !=      (       )
          -       -=      <       <=      [       ]
          !       =       >       >=      {       }
                          &&      ||      .       ,

Grammar

  The input tokens form a syntax tree following a context-free grammar:

      File = StatementList .

      Statement     = Assignment | Call | Condition .
      LValue        = identifier | ArrayAccess | ScopeAccess .
      Assignment    = LValue AssignOp Expr .
      Call          = identifier "(" [ ExprList ] ")" [ Block ] .
      Condition     = "if" "(" Expr ")" Block
                      [ "else" ( Condition | Block ) ] .
      Block         = "{" StatementList "}" .
      StatementList = { Statement } .

      ArrayAccess = identifier "[" Expr "]" .
      ScopeAccess = identifier "." identifier .
      Expr        = UnaryExpr | Expr BinaryOp Expr .
      UnaryExpr   = PrimaryExpr | UnaryOp UnaryExpr .
      PrimaryExpr = identifier | integer | string | Call
                  | ArrayAccess | ScopeAccess | Block
                  | "(" Expr ")"
                  | "[" [ ExprList [ "," ] ] "]" .
      ExprList    = Expr { "," Expr } .

      AssignOp = "=" | "+=" | "-=" .
      UnaryOp  = "!" .
      BinaryOp = "+" | "-"                  // highest priority
               | "<" | "<=" | ">" | ">="
               | "==" | "!="
               | "&&"
               | "||" .                     // lowest priority

  All binary operators are left-associative.

Types

  The GN language is dynamically typed. The following types are used:

   - Boolean: Uses the keywords "true" and "false". There is no implicit
     conversion between booleans and integers.

   - Integers: All numbers in GN are signed 64-bit integers.

   - Strings: Strings are 8-bit with no enforced encoding. When a string is
     used to interact with other systems with particular encodings (like the
     Windows and Mac filesystems) it is assumed to be UTF-8. See "String
     literals" above for more.

   - Lists: Lists are arbitrary-length ordered lists of values. See "Lists"
     below for more.

   - Scopes: Scopes are like dictionaries that use variable names for keys. See
     "Scopes" below for more.

Lists

  Lists are created with [] and using commas to separate items:

       mylist = [ 0, 1, 2, "some string" ]

  A comma after the last item is optional. Lists are dereferenced using 0-based
  indexing:

       mylist[0] += 1
       var = mylist[2]

  Lists can be concatenated using the '+' and '+=' operators. Bare values can
  not be concatenated with lists, to add a single item, it must be put into a
  list of length one.

  Items can be removed from lists using the '-' and '-=' operators. This will
  remove all occurrences of every item in the right-hand list from the
  left-hand list. It is an error to remove an item not in the list. This is to
  prevent common typos and to detect dead code that is removing things that no
  longer apply.

  It is an error to use '=' to replace a nonempty list with another nonempty
  list. This is to prevent accidentally overwriting data when in most cases
  '+=' was intended. To overwrite a list on purpose, first assign it to the
  empty list:

    mylist = []
    mylist = otherlist

Scopes

  All execution happens in the context of a scope which holds the current state
  (like variables). With the exception of loops and conditions, '{' introduces
  a new scope that has a parent reference to the old scope.

  Variable reads recursively search all nested scopes until the variable is
  found or there are no more scopes. Variable writes always go into the current
  scope. This means that after the closing '}' (again excepting loops and
  conditions), all local variables will be restored to the previous values.
  This also means that "foo = foo" can do useful work by copying a variable
  into the current scope that was defined in a containing scope.

  Scopes can also be assigned to variables. Such scopes can be created by
  functions like exec_script, when invoking a template (the template code
  refers to the variables set by the invoking code by the implicitly-created
  "invoker" scope), or explicitly like:

    empty_scope = {}
    myvalues = {
      foo = 21
      bar = "something"
    }

  Inside such a scope definition can be any GN code including conditionals and
  function calls. After the close of the scope, it will contain all variables
  explicitly set by the code contained inside it. After this, the values can be
  read, modified, or added to:

    myvalues.foo += 2
    empty_scope.new_thing = [ 1, 2, 3 ]

  Scope equality is defined as single-level scopes identical within the current
  scope. That is, all values in the first scope must be present and identical
  within the second, and vice versa. Note that this means inherited scopes are
  always unequal by definition.
)*";

// Precedence constants.
//
// Currently all operators are left-associative so this list is sequential. To
// implement a right-assocative operators in a Pratt parser we would leave gaps
// in between the constants, and right-associative operators get a precedence
// of "<left-associated-precedence> - 1".
enum Precedence {
  PRECEDENCE_ASSIGNMENT = 1,  // Lowest precedence.
  PRECEDENCE_OR = 2,
  PRECEDENCE_AND = 3,
  PRECEDENCE_EQUALITY = 4,
  PRECEDENCE_RELATION = 5,
  PRECEDENCE_SUM = 6,
  PRECEDENCE_PREFIX = 7,
  PRECEDENCE_CALL = 8,
  PRECEDENCE_DOT = 9,  // Highest precedence.
};

// The top-level for blocks/ifs is recursive descent, the expression parser is
// a Pratt parser. The basic idea there is to have the precedences (and
// associativities) encoded relative to each other and only parse up until you
// hit something of that precedence. There's a dispatch table in expressions_
// at the top of parser.cc that describes how each token dispatches if it's
// seen as either a prefix or infix operator, and if it's infix, what its
// precedence is.
//
// References:
// http://javascript.crockford.com/tdop/tdop.html
// http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/

// Indexed by Token::Type.
ParserHelper Parser::expressions_[] = {
    {nullptr, nullptr, -1},                                   // INVALID
    {&Parser::Literal, nullptr, -1},                          // INTEGER
    {&Parser::Literal, nullptr, -1},                          // STRING
    {&Parser::Literal, nullptr, -1},                          // TRUE_TOKEN
    {&Parser::Literal, nullptr, -1},                          // FALSE_TOKEN
    {nullptr, &Parser::Assignment, PRECEDENCE_ASSIGNMENT},    // EQUAL
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_SUM},       // PLUS
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_SUM},       // MINUS
    {nullptr, &Parser::Assignment, PRECEDENCE_ASSIGNMENT},    // PLUS_EQUALS
    {nullptr, &Parser::Assignment, PRECEDENCE_ASSIGNMENT},    // MINUS_EQUALS
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_EQUALITY},  // EQUAL_EQUAL
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_EQUALITY},  // NOT_EQUAL
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_RELATION},  // LESS_EQUAL
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_RELATION},  // GREATER_EQUAL
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_RELATION},  // LESS_THAN
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_RELATION},  // GREATER_THAN
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_AND},       // BOOLEAN_AND
    {nullptr, &Parser::BinaryOperator, PRECEDENCE_OR},        // BOOLEAN_OR
    {&Parser::Not, nullptr, -1},                              // BANG
    {nullptr, &Parser::DotOperator, PRECEDENCE_DOT},          // DOT
    {&Parser::Group, nullptr, -1},                            // LEFT_PAREN
    {nullptr, nullptr, -1},                                   // RIGHT_PAREN
    {&Parser::List, &Parser::Subscript, PRECEDENCE_CALL},     // LEFT_BRACKET
    {nullptr, nullptr, -1},                                   // RIGHT_BRACKET
    {&Parser::Block, nullptr, -1},                            // LEFT_BRACE
    {nullptr, nullptr, -1},                                   // RIGHT_BRACE
    {nullptr, nullptr, -1},                                   // IF
    {nullptr, nullptr, -1},                                   // ELSE
    {&Parser::Name, &Parser::IdentifierOrCall, PRECEDENCE_CALL},  // IDENTIFIER
    {nullptr, nullptr, -1},                                       // COMMA
    {nullptr, nullptr, -1},                // UNCLASSIFIED_COMMENT
    {nullptr, nullptr, -1},                // LINE_COMMENT
    {nullptr, nullptr, -1},                // SUFFIX_COMMENT
    {&Parser::BlockComment, nullptr, -1},  // BLOCK_COMMENT
};

Parser::Parser(const std::vector<Token>& tokens, Err* err)
    : invalid_token_(Location(), Token::INVALID, std::string_view()),
      err_(err),
      cur_(0) {
  for (const auto& token : tokens) {
    switch (token.type()) {
      case Token::LINE_COMMENT:
        line_comment_tokens_.push_back(token);
        break;
      case Token::SUFFIX_COMMENT:
        suffix_comment_tokens_.push_back(token);
        break;
      default:
        // Note that BLOCK_COMMENTs (top-level standalone comments) are passed
        // through the real parser.
        tokens_.push_back(token);
        break;
    }
  }
}

Parser::~Parser() = default;

// static
std::unique_ptr<ParseNode> Parser::Parse(const std::vector<Token>& tokens,
                                         Err* err) {
  Parser p(tokens, err);
  return p.ParseFile();
}

// static
std::unique_ptr<ParseNode> Parser::ParseExpression(
    const std::vector<Token>& tokens,
    Err* err) {
  Parser p(tokens, err);
  std::unique_ptr<ParseNode> expr = p.ParseExpression();
  if (!p.at_end() && !err->has_error()) {
    *err = Err(p.cur_token(), "Trailing garbage");
    return nullptr;
  }
  return expr;
}

// static
std::unique_ptr<ParseNode> Parser::ParseValue(const std::vector<Token>& tokens,
                                              Err* err) {
  for (const Token& token : tokens) {
    switch (token.type()) {
      case Token::INTEGER:
      case Token::STRING:
      case Token::TRUE_TOKEN:
      case Token::FALSE_TOKEN:
      case Token::LEFT_BRACKET:
      case Token::RIGHT_BRACKET:
      case Token::COMMA:
        continue;
      default:
        *err = Err(token, "Invalid token in literal value");
        return nullptr;
    }
  }

  return ParseExpression(tokens, err);
}

bool Parser::IsAssignment(const ParseNode* node) const {
  return node && node->AsBinaryOp() &&
         (node->AsBinaryOp()->op().type() == Token::EQUAL ||
          node->AsBinaryOp()->op().type() == Token::PLUS_EQUALS ||
          node->AsBinaryOp()->op().type() == Token::MINUS_EQUALS);
}

bool Parser::IsStatementBreak(Token::Type token_type) const {
  switch (token_type) {
    case Token::IDENTIFIER:
    case Token::LEFT_BRACE:
    case Token::RIGHT_BRACE:
    case Token::IF:
    case Token::ELSE:
      return true;
    default:
      return false;
  }
}

bool Parser::LookAhead(Token::Type type) {
  if (at_end())
    return false;
  return cur_token().type() == type;
}

bool Parser::Match(Token::Type type) {
  if (!LookAhead(type))
    return false;
  Consume();
  return true;
}

const Token& Parser::Consume(Token::Type type, const char* error_message) {
  Token::Type types[1] = {type};
  return Consume(types, 1, error_message);
}

const Token& Parser::Consume(Token::Type* types,
                             size_t num_types,
                             const char* error_message) {
  if (has_error()) {
    // Don't overwrite current error, but make progress through tokens so that
    // a loop that's expecting a particular token will still terminate.
    if (!at_end())
      cur_++;
    return invalid_token_;
  }
  if (at_end()) {
    const char kEOFMsg[] = "I hit EOF instead.";
    if (tokens_.empty())
      *err_ = Err(Location(), error_message, kEOFMsg);
    else
      *err_ = Err(tokens_[tokens_.size() - 1], error_message, kEOFMsg);
    return invalid_token_;
  }

  for (size_t i = 0; i < num_types; ++i) {
    if (cur_token().type() == types[i])
      return Consume();
  }
  *err_ = Err(cur_token(), error_message);
  return invalid_token_;
}

const Token& Parser::Consume() {
  return tokens_[cur_++];
}

std::unique_ptr<ParseNode> Parser::ParseExpression() {
  return ParseExpression(0);
}

std::unique_ptr<ParseNode> Parser::ParseExpression(int precedence) {
  if (at_end())
    return std::unique_ptr<ParseNode>();

  const Token& token = Consume();
  PrefixFunc prefix = expressions_[token.type()].prefix;

  if (prefix == nullptr) {
    *err_ = Err(token, "Unexpected token '" + std::string(token.value()) + "'");
    return std::unique_ptr<ParseNode>();
  }

  std::unique_ptr<ParseNode> left = (this->*prefix)(token);
  if (has_error())
    return left;

  while (!at_end() && !IsStatementBreak(cur_token().type()) &&
         precedence <= expressions_[cur_token().type()].precedence) {
    const Token& next_token = Consume();
    InfixFunc infix = expressions_[next_token.type()].infix;
    if (infix == nullptr) {
      *err_ = Err(next_token,
                  "Unexpected token '" + std::string(next_token.value()) + "'");
      return std::unique_ptr<ParseNode>();
    }
    left = (this->*infix)(std::move(left), next_token);
    if (has_error())
      return std::unique_ptr<ParseNode>();
  }

  return left;
}

std::unique_ptr<ParseNode> Parser::Block(const Token& token) {
  // This entrypoint into ParseBlock means it's part of an expression and we
  // always want the result.
  return ParseBlock(token, BlockNode::RETURNS_SCOPE);
}

std::unique_ptr<ParseNode> Parser::Literal(const Token& token) {
  return std::make_unique<LiteralNode>(token);
}

std::unique_ptr<ParseNode> Parser::Name(const Token& token) {
  return IdentifierOrCall(std::unique_ptr<ParseNode>(), token);
}

std::unique_ptr<ParseNode> Parser::BlockComment(const Token& token) {
  std::unique_ptr<BlockCommentNode> comment =
      std::make_unique<BlockCommentNode>();
  comment->set_comment(token);
  return std::move(comment);
}

std::unique_ptr<ParseNode> Parser::Group(const Token& token) {
  std::unique_ptr<ParseNode> expr = ParseExpression();
  if (has_error())
    return std::unique_ptr<ParseNode>();
  Consume(Token::RIGHT_PAREN, "Expected ')'");
  return expr;
}

std::unique_ptr<ParseNode> Parser::Not(const Token& token) {
  std::unique_ptr<ParseNode> expr = ParseExpression(PRECEDENCE_PREFIX + 1);
  if (has_error())
    return std::unique_ptr<ParseNode>();
  if (!expr) {
    if (!has_error())
      *err_ = Err(token, "Expected right-hand side for '!'.");
    return std::unique_ptr<ParseNode>();
  }
  std::unique_ptr<UnaryOpNode> unary_op = std::make_unique<UnaryOpNode>();
  unary_op->set_op(token);
  unary_op->set_operand(std::move(expr));
  return std::move(unary_op);
}

std::unique_ptr<ParseNode> Parser::List(const Token& node) {
  std::unique_ptr<ParseNode> list(ParseList(node, Token::RIGHT_BRACKET, true));
  if (!has_error() && !at_end())
    Consume(Token::RIGHT_BRACKET, "Expected ']'");
  return list;
}

std::unique_ptr<ParseNode> Parser::BinaryOperator(
    std::unique_ptr<ParseNode> left,
    const Token& token) {
  std::unique_ptr<ParseNode> right =
      ParseExpression(expressions_[token.type()].precedence + 1);
  if (!right) {
    if (!has_error()) {
      *err_ = Err(token, "Expected right-hand side for '" +
                             std::string(token.value()) + "'");
    }
    return std::unique_ptr<ParseNode>();
  }
  std::unique_ptr<BinaryOpNode> binary_op = std::make_unique<BinaryOpNode>();
  binary_op->set_op(token);
  binary_op->set_left(std::move(left));
  binary_op->set_right(std::move(right));
  return std::move(binary_op);
}

std::unique_ptr<ParseNode> Parser::IdentifierOrCall(
    std::unique_ptr<ParseNode> left,
    const Token& token) {
  std::unique_ptr<ListNode> list = std::make_unique<ListNode>();
  list->set_begin_token(token);
  list->set_end(std::make_unique<EndNode>(token));
  std::unique_ptr<BlockNode> block;
  bool has_arg = false;
  if (LookAhead(Token::LEFT_PAREN)) {
    const Token& start_token = Consume();
    // Parsing a function call.
    has_arg = true;
    if (Match(Token::RIGHT_PAREN)) {
      // Nothing, just an empty call.
    } else {
      list = ParseList(start_token, Token::RIGHT_PAREN, false);
      if (has_error())
        return std::unique_ptr<ParseNode>();
      Consume(Token::RIGHT_PAREN, "Expected ')' after call");
    }
    // Optionally with a scope.
    if (LookAhead(Token::LEFT_BRACE)) {
      block = ParseBlock(Consume(), BlockNode::DISCARDS_RESULT);
      if (has_error())
        return std::unique_ptr<ParseNode>();
    }
  }

  if (!left && !has_arg) {
    // Not a function call, just a standalone identifier.
    return std::make_unique<IdentifierNode>(token);
  }
  std::unique_ptr<FunctionCallNode> func_call =
      std::make_unique<FunctionCallNode>();
  func_call->set_function(token);
  func_call->set_args(std::move(list));
  if (block)
    func_call->set_block(std::move(block));
  return std::move(func_call);
}

std::unique_ptr<ParseNode> Parser::Assignment(std::unique_ptr<ParseNode> left,
                                              const Token& token) {
  if (left->AsIdentifier() == nullptr && left->AsAccessor() == nullptr) {
    *err_ = Err(left.get(),
                "The left-hand side of an assignment must be an identifier, "
                "scope access, or array access.");
    return std::unique_ptr<ParseNode>();
  }
  std::unique_ptr<ParseNode> value = ParseExpression(PRECEDENCE_ASSIGNMENT);
  if (!value) {
    if (!has_error())
      *err_ = Err(token, "Expected right-hand side for assignment.");
    return std::unique_ptr<ParseNode>();
  }
  std::unique_ptr<BinaryOpNode> assign = std::make_unique<BinaryOpNode>();
  assign->set_op(token);
  assign->set_left(std::move(left));
  assign->set_right(std::move(value));
  return std::move(assign);
}

std::unique_ptr<ParseNode> Parser::Subscript(std::unique_ptr<ParseNode> left,
                                             const Token& token) {
  // TODO: Maybe support more complex expressions like a[0][0]. This would
  // require work on the evaluator too.
  if (left->AsIdentifier() == nullptr) {
    *err_ = Err(
        left.get(), "May only subscript identifiers.",
        "The thing on the left hand side of the [] must be an identifier\n"
        "and not an expression. If you need this, you'll have to assign the\n"
        "value to a temporary before subscripting. Sorry.");
    return std::unique_ptr<ParseNode>();
  }
  std::unique_ptr<ParseNode> value = ParseExpression();
  Consume(Token::RIGHT_BRACKET, "Expecting ']' after subscript.");
  std::unique_ptr<AccessorNode> accessor = std::make_unique<AccessorNode>();
  accessor->set_base(left->AsIdentifier()->value());
  accessor->set_subscript(std::move(value));
  return std::move(accessor);
}

std::unique_ptr<ParseNode> Parser::DotOperator(std::unique_ptr<ParseNode> left,
                                               const Token& token) {
  if (left->AsIdentifier() == nullptr) {
    *err_ = Err(
        left.get(), "May only use \".\" for identifiers.",
        "The thing on the left hand side of the dot must be an identifier\n"
        "and not an expression. If you need this, you'll have to assign the\n"
        "value to a temporary first. Sorry.");
    return std::unique_ptr<ParseNode>();
  }

  std::unique_ptr<ParseNode> right = ParseExpression(PRECEDENCE_DOT);
  if (!right || !right->AsIdentifier()) {
    *err_ = Err(
        token, "Expected identifier for right-hand-side of \".\"",
        "Good: a.cookies\nBad: a.42\nLooks good but still bad: a.cookies()");
    return std::unique_ptr<ParseNode>();
  }

  std::unique_ptr<AccessorNode> accessor = std::make_unique<AccessorNode>();
  accessor->set_base(left->AsIdentifier()->value());
  accessor->set_member(std::unique_ptr<IdentifierNode>(
      static_cast<IdentifierNode*>(right.release())));
  return std::move(accessor);
}

// Does not Consume the start or end token.
std::unique_ptr<ListNode> Parser::ParseList(const Token& start_token,
                                            Token::Type stop_before,
                                            bool allow_trailing_comma) {
  std::unique_ptr<ListNode> list = std::make_unique<ListNode>();
  list->set_begin_token(start_token);
  bool just_got_comma = false;
  bool first_time = true;
  while (!LookAhead(stop_before)) {
    if (!first_time) {
      if (!just_got_comma) {
        // Require commas separate things in lists.
        *err_ = Err(cur_token(), "Expected comma between items.");
        return std::unique_ptr<ListNode>();
      }
    }
    first_time = false;

    // Why _OR? We're parsing things that are higher precedence than the ,
    // that separates the items of the list. , should appear lower than
    // boolean expressions (the lowest of which is OR), but above assignments.
    list->append_item(ParseExpression(PRECEDENCE_OR));
    if (has_error())
      return std::unique_ptr<ListNode>();
    if (at_end()) {
      *err_ =
          Err(tokens_[tokens_.size() - 1], "Unexpected end of file in list.");
      return std::unique_ptr<ListNode>();
    }
    if (list->contents().back()->AsBlockComment()) {
      // If there was a comment inside the list, we don't need a comma to the
      // next item, so pretend we got one, if we're expecting one.
      just_got_comma = allow_trailing_comma;
    } else {
      just_got_comma = Match(Token::COMMA);
    }
  }
  if (just_got_comma && !allow_trailing_comma) {
    *err_ = Err(cur_token(), "Trailing comma");
    return std::unique_ptr<ListNode>();
  }
  list->set_end(std::make_unique<EndNode>(cur_token()));
  return list;
}

std::unique_ptr<ParseNode> Parser::ParseFile() {
  std::unique_ptr<BlockNode> file =
      std::make_unique<BlockNode>(BlockNode::DISCARDS_RESULT);
  for (;;) {
    if (at_end())
      break;
    std::unique_ptr<ParseNode> statement = ParseStatement();
    if (!statement)
      break;
    file->append_statement(std::move(statement));
  }
  if (!at_end() && !has_error())
    *err_ = Err(cur_token(), "Unexpected here, should be newline.");
  if (has_error())
    return std::unique_ptr<ParseNode>();

  // TODO(scottmg): If this is measurably expensive, it could be done only
  // when necessary (when reformatting, or during tests). Comments are
  // separate from the parse tree at this point, so downstream code can remain
  // ignorant of them.
  AssignComments(file.get());

  return std::move(file);
}

std::unique_ptr<ParseNode> Parser::ParseStatement() {
  if (LookAhead(Token::IF)) {
    return ParseCondition();
  } else if (LookAhead(Token::BLOCK_COMMENT)) {
    return BlockComment(Consume());
  } else {
    // TODO(scottmg): Is this too strict? Just drop all the testing if we want
    // to allow "pointless" expressions and return ParseExpression() directly.
    std::unique_ptr<ParseNode> stmt = ParseExpression();
    if (stmt) {
      if (stmt->AsFunctionCall() || IsAssignment(stmt.get()))
        return stmt;
    }
    if (!has_error()) {
      const Token& token = cur_or_last_token();
      *err_ = Err(token, "Expecting assignment or function call.");
    }
    return std::unique_ptr<ParseNode>();
  }
}

std::unique_ptr<BlockNode> Parser::ParseBlock(
    const Token& begin_brace,
    BlockNode::ResultMode result_mode) {
  if (has_error())
    return std::unique_ptr<BlockNode>();
  std::unique_ptr<BlockNode> block = std::make_unique<BlockNode>(result_mode);
  block->set_begin_token(begin_brace);

  for (;;) {
    if (LookAhead(Token::RIGHT_BRACE)) {
      block->set_end(std::make_unique<EndNode>(Consume()));
      break;
    }

    std::unique_ptr<ParseNode> statement = ParseStatement();
    if (!statement)
      return std::unique_ptr<BlockNode>();
    block->append_statement(std::move(statement));
  }
  return block;
}

std::unique_ptr<ParseNode> Parser::ParseCondition() {
  std::unique_ptr<ConditionNode> condition = std::make_unique<ConditionNode>();
  condition->set_if_token(Consume(Token::IF, "Expected 'if'"));
  Consume(Token::LEFT_PAREN, "Expected '(' after 'if'.");
  condition->set_condition(ParseExpression());
  if (IsAssignment(condition->condition()))
    *err_ = Err(condition->condition(), "Assignment not allowed in 'if'.");
  Consume(Token::RIGHT_PAREN, "Expected ')' after condition of 'if'.");
  condition->set_if_true(ParseBlock(
      Consume(Token::LEFT_BRACE, "Expected '{' to start 'if' block."),
      BlockNode::DISCARDS_RESULT));
  if (Match(Token::ELSE)) {
    if (LookAhead(Token::LEFT_BRACE)) {
      condition->set_if_false(
          ParseBlock(Consume(), BlockNode::DISCARDS_RESULT));
    } else if (LookAhead(Token::IF)) {
      condition->set_if_false(ParseStatement());
    } else {
      *err_ = Err(cur_or_last_token(), "Expected '{' or 'if' after 'else'.");
      return std::unique_ptr<ParseNode>();
    }
  }
  if (has_error())
    return std::unique_ptr<ParseNode>();
  return std::move(condition);
}

void Parser::TraverseOrder(const ParseNode* root,
                           std::vector<const ParseNode*>* pre,
                           std::vector<const ParseNode*>* post) {
  if (root) {
    pre->push_back(root);

    if (const AccessorNode* accessor = root->AsAccessor()) {
      TraverseOrder(accessor->subscript(), pre, post);
      TraverseOrder(accessor->member(), pre, post);
    } else if (const BinaryOpNode* binop = root->AsBinaryOp()) {
      TraverseOrder(binop->left(), pre, post);
      TraverseOrder(binop->right(), pre, post);
    } else if (const BlockNode* block = root->AsBlock()) {
      for (const auto& statement : block->statements())
        TraverseOrder(statement.get(), pre, post);
      TraverseOrder(block->End(), pre, post);
    } else if (const ConditionNode* condition = root->AsCondition()) {
      TraverseOrder(condition->condition(), pre, post);
      TraverseOrder(condition->if_true(), pre, post);
      TraverseOrder(condition->if_false(), pre, post);
    } else if (const FunctionCallNode* func_call = root->AsFunctionCall()) {
      TraverseOrder(func_call->args(), pre, post);
      TraverseOrder(func_call->block(), pre, post);
    } else if (root->AsIdentifier()) {
      // Nothing.
    } else if (const ListNode* list = root->AsList()) {
      for (const auto& node : list->contents())
        TraverseOrder(node.get(), pre, post);
      TraverseOrder(list->End(), pre, post);
    } else if (root->AsLiteral()) {
      // Nothing.
    } else if (const UnaryOpNode* unaryop = root->AsUnaryOp()) {
      TraverseOrder(unaryop->operand(), pre, post);
    } else if (root->AsBlockComment()) {
      // Nothing.
    } else if (root->AsEnd()) {
      // Nothing.
    } else {
      CHECK(false) << "Unhandled case in TraverseOrder.";
    }

    post->push_back(root);
  }
}

void Parser::AssignComments(ParseNode* file) {
  // Start by generating a pre- and post- order traversal of the tree so we
  // can determine what's before and after comments.
  std::vector<const ParseNode*> pre;
  std::vector<const ParseNode*> post;
  TraverseOrder(file, &pre, &post);

  // Assign line comments to syntax immediately following.
  int cur_comment = 0;
  for (auto* node : pre) {
    if (node->GetRange().is_null()) {
      CHECK_EQ(node, file) << "Only expected on top file node";
      continue;
    }
    const Location start = node->GetRange().begin();
    while (cur_comment < static_cast<int>(line_comment_tokens_.size())) {
      if (start.byte() >= line_comment_tokens_[cur_comment].location().byte()) {
        const_cast<ParseNode*>(node)->comments_mutable()->append_before(
            line_comment_tokens_[cur_comment]);
        ++cur_comment;
      } else {
        break;
      }
    }
  }

  // Remaining line comments go at end of file.
  for (; cur_comment < static_cast<int>(line_comment_tokens_.size());
       ++cur_comment)
    file->comments_mutable()->append_after(line_comment_tokens_[cur_comment]);

  // Assign suffix to syntax immediately before.
  cur_comment = static_cast<int>(suffix_comment_tokens_.size() - 1);
  for (std::vector<const ParseNode*>::const_reverse_iterator i = post.rbegin();
       i != post.rend(); ++i) {
    // Don't assign suffix comments to the function, list, or block, but instead
    // to the last thing inside.
    if ((*i)->AsFunctionCall() || (*i)->AsList() || (*i)->AsBlock())
      continue;

    Location start = (*i)->GetRange().begin();
    Location end = (*i)->GetRange().end();

    // Don't assign suffix comments to something that starts on an earlier
    // line, so that in:
    //
    // sources = [ "a",
    //     "b" ] # comment
    //
    // it's attached to "b", not sources = [ ... ].
    if (start.line_number() != end.line_number())
      continue;

    while (cur_comment >= 0) {
      if (end.byte() <= suffix_comment_tokens_[cur_comment].location().byte()) {
        const_cast<ParseNode*>(*i)->comments_mutable()->append_suffix(
            suffix_comment_tokens_[cur_comment]);
        --cur_comment;
      } else {
        break;
      }
    }

    // Suffix comments were assigned in reverse, so if there were multiple on
    // the same node, they need to be reversed.
    if ((*i)->comments() && !(*i)->comments()->suffix().empty())
      const_cast<ParseNode*>(*i)->comments_mutable()->ReverseSuffix();
  }
}

std::string IndentFor(int value) {
  return std::string(value, ' ');
}

void RenderToText(const base::Value& node,
                  int indent_level,
                  std::ostringstream& os) {
  const base::Value* child = node.FindKey(std::string("child"));
  std::string node_type(node.FindKey("type")->GetString());
  if (node_type == "ACCESSOR") {
    // AccessorNode is a bit special, in that it holds a Token, not a ParseNode
    // for the base.
    os << IndentFor(indent_level) << node_type << std::endl;
    os << IndentFor(indent_level + 1) << node.FindKey("value")->GetString()
       << std::endl;
  } else {
    os << IndentFor(indent_level) << node_type;
    if (node.FindKey("value")) {
      os << "(" << node.FindKey("value")->GetString() << ")";
    }
    os << std::endl;
  }
  if (node.FindKey(kJsonBeforeComment)) {
    for (auto& v : node.FindKey(kJsonBeforeComment)->GetList()) {
      os << IndentFor(indent_level + 1) << "+BEFORE_COMMENT(\"" << v.GetString()
         << "\")\n";
    }
  }
  if (node.FindKey(kJsonSuffixComment)) {
    for (auto& v : node.FindKey(kJsonSuffixComment)->GetList()) {
      os << IndentFor(indent_level + 1) << "+SUFFIX_COMMENT(\"" << v.GetString()
         << "\")\n";
    }
  }
  if (node.FindKey(kJsonAfterComment)) {
    for (auto& v : node.FindKey(kJsonAfterComment)->GetList()) {
      os << IndentFor(indent_level + 1) << "+AFTER_COMMENT(\"" << v.GetString()
         << "\")\n";
    }
  }
  if (child) {
    for (const base::Value& n : child->GetList()) {
      RenderToText(n, indent_level + 1, os);
    }
  }
  const base::Value* end = node.FindKey("end");
  if (end &&
      (end->FindKey(kJsonBeforeComment) || end->FindKey(kJsonSuffixComment) ||
       end->FindKey(kJsonAfterComment))) {
    RenderToText(*end, indent_level + 1, os);
  }
}