1// Copyright (c) 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef TOOLS_GN_PARSER_H_
6#define TOOLS_GN_PARSER_H_
7
8#include <map>
9#include <vector>
10
11#include "base/basictypes.h"
12#include "base/gtest_prod_util.h"
13#include "base/memory/scoped_ptr.h"
14#include "tools/gn/err.h"
15#include "tools/gn/parse_tree.h"
16
17class Parser;
18typedef scoped_ptr<ParseNode> (Parser::*PrefixFunc)(Token token);
19typedef scoped_ptr<ParseNode> (Parser::*InfixFunc)(scoped_ptr<ParseNode> left,
20                                                   Token token);
21
22struct ParserHelper {
23  PrefixFunc prefix;
24  InfixFunc infix;
25  int precedence;
26};
27
28// Parses a series of tokens. The resulting AST will refer to the tokens passed
29// to the input, so the tokens an the file data they refer to must outlive your
30// use of the ParseNode.
31class Parser {
32 public:
33  // Will return a null pointer and set the err on error.
34  static scoped_ptr<ParseNode> Parse(const std::vector<Token>& tokens,
35                                     Err* err);
36
37  // Alternative to parsing that assumes the input is an expression.
38  static scoped_ptr<ParseNode> ParseExpression(const std::vector<Token>& tokens,
39                                               Err* err);
40
41  scoped_ptr<ParseNode> ParseExpression();
42
43 private:
44  // Vector must be valid for lifetime of call.
45  Parser(const std::vector<Token>& tokens, Err* err);
46  ~Parser();
47
48  // Parses an expression with the given precedence or higher.
49  scoped_ptr<ParseNode> ParseExpression(int precedence);
50
51  // |PrefixFunc|s used in parsing expressions.
52  scoped_ptr<ParseNode> Literal(Token token);
53  scoped_ptr<ParseNode> Name(Token token);
54  scoped_ptr<ParseNode> Group(Token token);
55  scoped_ptr<ParseNode> Not(Token token);
56  scoped_ptr<ParseNode> List(Token token);
57  scoped_ptr<ParseNode> BlockComment(Token token);
58
59  // |InfixFunc|s used in parsing expressions.
60  scoped_ptr<ParseNode> BinaryOperator(scoped_ptr<ParseNode> left, Token token);
61  scoped_ptr<ParseNode> IdentifierOrCall(scoped_ptr<ParseNode> left,
62                                         Token token);
63  scoped_ptr<ParseNode> Assignment(scoped_ptr<ParseNode> left, Token token);
64  scoped_ptr<ParseNode> Subscript(scoped_ptr<ParseNode> left, Token token);
65  scoped_ptr<ParseNode> DotOperator(scoped_ptr<ParseNode> left, Token token);
66
67  // Helper to parse a comma separated list, optionally allowing trailing
68  // commas (allowed in [] lists, not in function calls).
69  scoped_ptr<ListNode> ParseList(Token start_token,
70                                 Token::Type stop_before,
71                                 bool allow_trailing_comma);
72
73  scoped_ptr<ParseNode> ParseFile();
74  scoped_ptr<ParseNode> ParseStatement();
75  scoped_ptr<BlockNode> ParseBlock();
76  scoped_ptr<ParseNode> ParseCondition();
77
78  // Generates a pre- and post-order traversal of the tree.
79  void TraverseOrder(const ParseNode* root,
80                     std::vector<const ParseNode*>* pre,
81                     std::vector<const ParseNode*>* post);
82
83  // Attach comments to nearby syntax.
84  void AssignComments(ParseNode* file);
85
86  bool IsAssignment(const ParseNode* node) const;
87  bool IsStatementBreak(Token::Type token_type) const;
88
89  bool LookAhead(Token::Type type);
90  bool Match(Token::Type type);
91  Token Consume(Token::Type type, const char* error_message);
92  Token Consume(Token::Type* types,
93                size_t num_types,
94                const char* error_message);
95  Token Consume();
96
97  const Token& cur_token() const { return tokens_[cur_]; }
98
99  bool done() const { return at_end() || has_error(); }
100  bool at_end() const { return cur_ >= tokens_.size(); }
101  bool has_error() const { return err_->has_error(); }
102
103  std::vector<Token> tokens_;
104  std::vector<Token> line_comment_tokens_;
105  std::vector<Token> suffix_comment_tokens_;
106
107  static ParserHelper expressions_[Token::NUM_TYPES];
108
109  Err* err_;
110
111  // Current index into the tokens.
112  size_t cur_;
113
114  FRIEND_TEST_ALL_PREFIXES(Parser, BinaryOp);
115  FRIEND_TEST_ALL_PREFIXES(Parser, Block);
116  FRIEND_TEST_ALL_PREFIXES(Parser, Condition);
117  FRIEND_TEST_ALL_PREFIXES(Parser, Expression);
118  FRIEND_TEST_ALL_PREFIXES(Parser, FunctionCall);
119  FRIEND_TEST_ALL_PREFIXES(Parser, List);
120  FRIEND_TEST_ALL_PREFIXES(Parser, ParenExpression);
121  FRIEND_TEST_ALL_PREFIXES(Parser, UnaryOp);
122
123  DISALLOW_COPY_AND_ASSIGN(Parser);
124};
125
126#endif  // TOOLS_GN_PARSER_H_
127