1 // Copyright 2017 The Fuchsia 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 ZIRCON_SYSTEM_HOST_FIDL_INCLUDE_FIDL_PARSER_H_
6 #define ZIRCON_SYSTEM_HOST_FIDL_INCLUDE_FIDL_PARSER_H_
7 
8 #include <memory>
9 
10 #include "error_reporter.h"
11 #include "lexer.h"
12 #include "raw_ast.h"
13 
14 namespace fidl {
15 
16 class Parser {
17 public:
18     Parser(Lexer* lexer, ErrorReporter* error_reporter);
19 
Parse()20     std::unique_ptr<raw::File> Parse() { return ParseFile(); }
21 
Ok()22     bool Ok() const { return error_reporter_->errors().size() == 0; }
23 
24 private:
Lex()25     Token Lex() { return lexer_->LexNoComments(); }
26 
Peek()27     Token::KindAndSubkind Peek() { return last_token_.kind_and_subkind(); }
28 
29     // ASTScope is a tool to track the start and end source location of each
30     // node automatically.  The parser associates each node with the start and
31     // end of its source location.  It also tracks the "gap" is between the the
32     // start and the previous interesting source element.  As we walk the tree,
33     // we create ASTScope objects that can track the beginning and end of the
34     // text associated with the Node being built.  The ASTScope object then
35     // colludes with the Parser to figure out where the beginning and end of
36     // that node are.
37     //
38     // ASTScope should only be created on the stack, when starting to parse
39     // something that will result in a new AST node.
40     class ASTScope {
41     public:
ASTScope(Parser * parser)42         explicit ASTScope(Parser* parser)
43             : parser_(parser) {
44             suppress_ = parser_->suppress_gap_checks_;
45             parser_->suppress_gap_checks_ = false;
46             parser_->active_ast_scopes_.push_back(raw::SourceElement(Token(), Token()));
47         }
48         // The suppress mechanism
ASTScope(Parser * parser,bool suppress)49         ASTScope(Parser* parser, bool suppress)
50             : parser_(parser), suppress_(suppress) {
51             parser_->active_ast_scopes_.push_back(raw::SourceElement(Token(), Token()));
52             suppress_ = parser_->suppress_gap_checks_;
53             parser_->suppress_gap_checks_ = suppress;
54         }
GetSourceElement()55         raw::SourceElement GetSourceElement() {
56             parser_->active_ast_scopes_.back().end_ = parser_->previous_token_;
57             if (!parser_->suppress_gap_checks_) {
58                 parser_->last_was_gap_start_ = true;
59             }
60             return raw::SourceElement(parser_->active_ast_scopes_.back());
61         }
~ASTScope()62         ~ASTScope() {
63             parser_->suppress_gap_checks_ = suppress_;
64             parser_->active_ast_scopes_.pop_back();
65         }
66 
67         ASTScope(const ASTScope&) = delete;
68         ASTScope& operator=(const ASTScope&) = delete;
69 
70     private:
71         Parser* parser_;
72         bool suppress_;
73     };
74 
UpdateMarks(Token & token)75     void UpdateMarks(Token& token) {
76         // There should always be at least one of these - the outermost.
77         if (active_ast_scopes_.size() == 0) {
78             Fail("Internal compiler error: unbalanced parse tree");
79         }
80 
81         if (!suppress_gap_checks_) {
82             // If the end of the last node was the start of a gap, record that.
83             if (last_was_gap_start_ && previous_token_.kind() != Token::Kind::kNotAToken) {
84                 gap_start_ = token.previous_end();
85                 last_was_gap_start_ = false;
86             }
87 
88             // If this is a start node, then the end of it will be the start of
89             // a gap.
90             if (active_ast_scopes_.back().start_.kind() == Token::Kind::kNotAToken) {
91                 last_was_gap_start_ = true;
92             }
93         }
94         // Update the token to record the correct location of the beginning of
95         // the gap prior to it.
96         if (gap_start_.valid()) {
97             token.set_previous_end(gap_start_);
98         }
99 
100         for (auto& scope : active_ast_scopes_) {
101             if (scope.start_.kind() == Token::Kind::kNotAToken) {
102                 scope.start_ = token;
103             }
104         }
105 
106         previous_token_ = token;
107     }
108 
109     // ConsumeToken consumes a token, and matches using the predicate |p|.
110     // See #OfKind, and #IdentifierOfSubkind for the two expected predicates.
111     //
112     // If the token is not retained on return, is_discarded should be true.
113     // That allows the parser to track its source location, in case it should
114     // become interesting to the AST.
115     template <class Predicate>
116     Token ConsumeToken(Predicate p, bool is_discarded = false) {
117         std::unique_ptr<std::string> failure_message = p(Peek());
118         if (failure_message) {
119             Fail(*failure_message);
120         }
121         auto token = last_token_;
122         last_token_ = Lex();
123         UpdateMarks(token);
124 
125         return token;
126     }
127 
128     // MaybeConsumeToken consumes a token if-and-only-if it matches the given
129     // predicate |p|.
130     // See #OfKind, and #IdentifierOfSubkind for the two expected predicates.
131     template <class Predicate>
MaybeConsumeToken(Predicate p)132     bool MaybeConsumeToken(Predicate p) {
133         std::unique_ptr<std::string> failure_message = p(Peek());
134         if (failure_message) {
135             return false;
136         }
137         previous_token_ = last_token_;
138         UpdateMarks(last_token_);
139         last_token_ = Lex();
140         return true;
141     }
142 
OfKind(Token::Kind expected_kind)143     static auto OfKind(Token::Kind expected_kind) {
144         return [expected_kind](Token::KindAndSubkind actual) -> std::unique_ptr<std::string> {
145             if (actual.kind() != expected_kind) {
146                 auto message = std::make_unique<std::string>("unexpected token ");
147                 message->append(Token::Name(actual));
148                 message->append(", was expecting ");
149                 message->append(Token::Name(Token::KindAndSubkind(expected_kind, Token::Subkind::kNone)));
150                 return message;
151             }
152             return nullptr;
153         };
154     }
155 
IdentifierOfSubkind(Token::Subkind expected_subkind)156     static auto IdentifierOfSubkind(Token::Subkind expected_subkind) {
157         return [expected_subkind](Token::KindAndSubkind actual) -> std::unique_ptr<std::string> {
158             auto expected = Token::KindAndSubkind(Token::Kind::kIdentifier, expected_subkind);
159             if (actual.combined() != expected.combined()) {
160                 auto message = std::make_unique<std::string>("unexpected identifier ");
161                 message->append(Token::Name(actual));
162                 message->append(", was expecting ");
163                 message->append(Token::Name(Token::KindAndSubkind(Token::Kind::kIdentifier, Token::Subkind::kNone)));
164                 return message;
165             }
166             return nullptr;
167         };
168     }
169 
170     bool LookupHandleSubtype(const raw::Identifier* identifier, types::HandleSubtype* subtype_out);
171 
172     decltype(nullptr) Fail();
173     decltype(nullptr) Fail(StringView message);
174 
175     std::unique_ptr<raw::Identifier> ParseIdentifier(bool is_discarded = false);
176     std::unique_ptr<raw::CompoundIdentifier> ParseCompoundIdentifier();
177 
178     std::unique_ptr<raw::StringLiteral> ParseStringLiteral();
179     std::unique_ptr<raw::NumericLiteral> ParseNumericLiteral();
180     std::unique_ptr<raw::TrueLiteral> ParseTrueLiteral();
181     std::unique_ptr<raw::FalseLiteral> ParseFalseLiteral();
182     std::unique_ptr<raw::Literal> ParseLiteral();
183     std::unique_ptr<raw::Ordinal> ParseOrdinal();
184 
185     std::unique_ptr<raw::Constant> ParseConstant();
186 
187     std::unique_ptr<raw::Attribute> ParseAttribute();
188     std::unique_ptr<raw::Attribute> ParseDocComment();
189     std::unique_ptr<raw::AttributeList> ParseAttributeList(std::unique_ptr<raw::Attribute>&& doc_comment, ASTScope& scope);
190     std::unique_ptr<raw::AttributeList> MaybeParseAttributeList();
191 
192     std::unique_ptr<raw::Using> ParseUsing();
193 
194     std::unique_ptr<raw::IdentifierType> ParseIdentifierType();
195     std::unique_ptr<raw::ArrayType> ParseArrayType();
196     std::unique_ptr<raw::VectorType> ParseVectorType();
197     std::unique_ptr<raw::StringType> ParseStringType();
198     std::unique_ptr<raw::HandleType> ParseHandleType();
199     std::unique_ptr<raw::RequestHandleType> ParseRequestHandleType();
200     std::unique_ptr<raw::Type> ParseType();
201 
202     std::unique_ptr<raw::ConstDeclaration>
203     ParseConstDeclaration(std::unique_ptr<raw::AttributeList> attributes, ASTScope&);
204 
205     std::unique_ptr<raw::EnumMember> ParseEnumMember();
206     std::unique_ptr<raw::EnumDeclaration>
207     ParseEnumDeclaration(std::unique_ptr<raw::AttributeList> attributes, ASTScope&);
208 
209     std::unique_ptr<raw::Parameter> ParseParameter();
210     std::unique_ptr<raw::ParameterList> ParseParameterList();
211     std::unique_ptr<raw::InterfaceMethod> ParseInterfaceMethod(
212         std::unique_ptr<raw::AttributeList> attributes, ASTScope& scope);
213     std::unique_ptr<raw::InterfaceDeclaration>
214     ParseInterfaceDeclaration(std::unique_ptr<raw::AttributeList> attributes, ASTScope&);
215 
216     std::unique_ptr<raw::StructMember> ParseStructMember();
217     std::unique_ptr<raw::StructDeclaration>
218     ParseStructDeclaration(std::unique_ptr<raw::AttributeList> attributes, ASTScope&);
219 
220     std::unique_ptr<raw::TableMember>
221     ParseTableMember();
222     std::unique_ptr<raw::TableDeclaration>
223     ParseTableDeclaration(std::unique_ptr<raw::AttributeList> attributes, ASTScope&);
224 
225     std::unique_ptr<raw::UnionMember> ParseUnionMember();
226     std::unique_ptr<raw::UnionDeclaration>
227     ParseUnionDeclaration(std::unique_ptr<raw::AttributeList> attributes, ASTScope&);
228 
229     std::unique_ptr<raw::File> ParseFile();
230 
231     std::map<StringView, types::HandleSubtype> handle_subtype_table_;
232 
233     Lexer* lexer_;
234     ErrorReporter* error_reporter_;
235 
236     // The stack of information interesting to the currently active ASTScope
237     // objects.
238     std::vector<raw::SourceElement> active_ast_scopes_;
239     // The most recent start of a "gap" - the uninteresting source prior to the
240     // beginning of a token (usually mostly containing whitespace).
241     SourceLocation gap_start_;
242     // Indicates that the last element was the start of a gap, and that the
243     // scope should be updated accordingly.
244     bool last_was_gap_start_ = false;
245     // Suppress updating the gap for the current Scope.  Useful when
246     // you don't know whether a scope is going to be interesting lexically, and
247     // you have to decide at runtime.
248     bool suppress_gap_checks_ = false;
249     // The token before last_token_ (below).
250     Token previous_token_;
251 
252     Token last_token_;
253 };
254 
255 } // namespace fidl
256 
257 #endif // ZIRCON_SYSTEM_HOST_FIDL_INCLUDE_FIDL_PARSER_H_
258