1 // Copyright 2015 Google Inc. All rights reserved
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // +build ignore
16
17 #include "parser.h"
18
19 #include <stack>
20 #include <unordered_map>
21
22 #include "expr.h"
23 #include "file.h"
24 #include "loc.h"
25 #include "log.h"
26 #include "stats.h"
27 #include "stmt.h"
28 #include "string_piece.h"
29 #include "strutil.h"
30
31 enum struct ParserState {
32 NOT_AFTER_RULE = 0,
33 AFTER_RULE,
34 MAYBE_AFTER_RULE,
35 };
36
37 class Parser {
38 struct IfState {
39 IfStmt* stmt;
40 bool is_in_else;
41 int num_nest;
42 };
43
44 typedef void (Parser::*DirectiveHandler)(
45 StringPiece line, StringPiece directive);
46 typedef unordered_map<StringPiece, DirectiveHandler> DirectiveMap;
47
48 public:
Parser(StringPiece buf,const char * filename,vector<Stmt * > * stmts)49 Parser(StringPiece buf, const char* filename, vector<Stmt*>* stmts)
50 : buf_(buf),
51 state_(ParserState::NOT_AFTER_RULE),
52 stmts_(stmts),
53 out_stmts_(stmts),
54 num_define_nest_(0),
55 num_if_nest_(0),
56 loc_(filename, 0),
57 fixed_lineno_(false) {
58 }
59
Parser(StringPiece buf,const Loc & loc,vector<Stmt * > * stmts)60 Parser(StringPiece buf, const Loc& loc, vector<Stmt*>* stmts)
61 : buf_(buf),
62 state_(ParserState::NOT_AFTER_RULE),
63 stmts_(stmts),
64 out_stmts_(stmts),
65 num_if_nest_(0),
66 loc_(loc),
67 fixed_lineno_(true) {
68 }
69
~Parser()70 ~Parser() {
71 }
72
Parse()73 void Parse() {
74 l_ = 0;
75
76 for (l_ = 0; l_ < buf_.size();) {
77 size_t lf_cnt = 0;
78 size_t e = FindEndOfLine(&lf_cnt);
79 if (!fixed_lineno_)
80 loc_.lineno++;
81 StringPiece line(buf_.data() + l_, e - l_);
82 if (line.get(line.size() - 1) == '\r')
83 line.remove_suffix(1);
84 orig_line_with_directives_ = line;
85 ParseLine(line);
86 if (!fixed_lineno_)
87 loc_.lineno += lf_cnt - 1;
88 if (e == buf_.size())
89 break;
90
91 l_ = e + 1;
92 }
93
94 if (!if_stack_.empty())
95 ERROR_LOC(Loc(loc_.filename, loc_.lineno + 1), "*** missing `endif'.");
96 if (!define_name_.empty())
97 ERROR_LOC(Loc(loc_.filename, define_start_line_),
98 "*** missing `endef', unterminated `define'.");
99 }
100
Init()101 static void Init() {
102 make_directives_ = new DirectiveMap;
103 (*make_directives_)["include"] = &Parser::ParseInclude;
104 (*make_directives_)["-include"] = &Parser::ParseInclude;
105 (*make_directives_)["sinclude"] = &Parser::ParseInclude;
106 (*make_directives_)["define"] = &Parser::ParseDefine;
107 (*make_directives_)["ifdef"] = &Parser::ParseIfdef;
108 (*make_directives_)["ifndef"] = &Parser::ParseIfdef;
109 (*make_directives_)["ifeq"] = &Parser::ParseIfeq;
110 (*make_directives_)["ifneq"] = &Parser::ParseIfeq;
111 (*make_directives_)["else"] = &Parser::ParseElse;
112 (*make_directives_)["endif"] = &Parser::ParseEndif;
113 (*make_directives_)["override"] = &Parser::ParseOverride;
114 (*make_directives_)["export"] = &Parser::ParseExport;
115 (*make_directives_)["unexport"] = &Parser::ParseUnexport;
116
117 else_if_directives_ = new DirectiveMap;
118 (*else_if_directives_)["ifdef"] = &Parser::ParseIfdef;
119 (*else_if_directives_)["ifndef"] = &Parser::ParseIfdef;
120 (*else_if_directives_)["ifeq"] = &Parser::ParseIfeq;
121 (*else_if_directives_)["ifneq"] = &Parser::ParseIfeq;
122
123 assign_directives_ = new DirectiveMap;
124 (*assign_directives_)["define"] = &Parser::ParseDefine;
125 (*assign_directives_)["export"] = &Parser::ParseExport;
126 (*assign_directives_)["override"] = &Parser::ParseOverride;
127
128 shortest_directive_len_ = 9999;
129 longest_directive_len_ = 0;
130 for (auto p : *make_directives_) {
131 size_t len = p.first.size();
132 shortest_directive_len_ = min(len, shortest_directive_len_);
133 longest_directive_len_ = max(len, longest_directive_len_);
134 }
135 }
136
Quit()137 static void Quit() {
138 delete make_directives_;
139 }
140
set_state(ParserState st)141 void set_state(ParserState st) { state_ = st; }
142
143 static vector<ParseErrorStmt*> parse_errors;
144
145 private:
Error(const string & msg)146 void Error(const string& msg) {
147 ParseErrorStmt* stmt = new ParseErrorStmt();
148 stmt->set_loc(loc_);
149 stmt->msg = msg;
150 out_stmts_->push_back(stmt);
151 parse_errors.push_back(stmt);
152 }
153
FindEndOfLine(size_t * lf_cnt)154 size_t FindEndOfLine(size_t* lf_cnt) {
155 return ::FindEndOfLine(buf_, l_, lf_cnt);
156 }
157
ParseExpr(StringPiece s,ParseExprOpt opt=ParseExprOpt::NORMAL)158 Value* ParseExpr(StringPiece s, ParseExprOpt opt = ParseExprOpt::NORMAL) {
159 return ::ParseExpr(loc_, s, opt);
160 }
161
ParseLine(StringPiece line)162 void ParseLine(StringPiece line) {
163 if (!define_name_.empty()) {
164 ParseInsideDefine(line);
165 return;
166 }
167
168 if (line.empty() || (line.size() == 1 && line[0] == '\r'))
169 return;
170
171 current_directive_ = AssignDirective::NONE;
172
173 if (line[0] == '\t' && state_ != ParserState::NOT_AFTER_RULE) {
174 CommandStmt* stmt = new CommandStmt();
175 stmt->set_loc(loc_);
176 stmt->expr = ParseExpr(line.substr(1), ParseExprOpt::COMMAND);
177 stmt->orig = line;
178 out_stmts_->push_back(stmt);
179 return;
180 }
181
182 line = TrimLeftSpace(line);
183
184 if (line[0] == '#')
185 return;
186
187 if (HandleDirective(line, make_directives_)) {
188 return;
189 }
190
191 ParseRuleOrAssign(line);
192 }
193
ParseRuleOrAssign(StringPiece line)194 void ParseRuleOrAssign(StringPiece line) {
195 size_t sep = FindThreeOutsideParen(line, ':', '=', ';');
196 if (sep == string::npos || line[sep] == ';') {
197 ParseRule(line, string::npos);
198 } else if (line[sep] == '=') {
199 ParseAssign(line, sep);
200 } else if (line.get(sep+1) == '=') {
201 ParseAssign(line, sep+1);
202 } else if (line[sep] == ':') {
203 ParseRule(line, sep);
204 } else {
205 CHECK(false);
206 }
207 }
208
ParseRule(StringPiece line,size_t sep)209 void ParseRule(StringPiece line, size_t sep) {
210 if (current_directive_ != AssignDirective::NONE) {
211 if (IsInExport())
212 return;
213 if (sep != string::npos) {
214 sep += orig_line_with_directives_.size() - line.size();
215 }
216 line = orig_line_with_directives_;
217 }
218
219 line = TrimLeftSpace(line);
220 if (line.empty())
221 return;
222
223 if (orig_line_with_directives_[0] == '\t') {
224 Error("*** commands commence before first target.");
225 return;
226 }
227
228 const bool is_rule = sep != string::npos && line[sep] == ':';
229 RuleStmt* stmt = new RuleStmt();
230 stmt->set_loc(loc_);
231
232 size_t found = FindTwoOutsideParen(line.substr(sep + 1), '=', ';');
233 if (found != string::npos) {
234 found += sep + 1;
235 stmt->term = line[found];
236 ParseExprOpt opt =
237 stmt->term == ';' ? ParseExprOpt::COMMAND : ParseExprOpt::NORMAL;
238 stmt->after_term = ParseExpr(TrimLeftSpace(line.substr(found + 1)), opt);
239 stmt->expr = ParseExpr(TrimSpace(line.substr(0, found)));
240 } else {
241 stmt->term = 0;
242 stmt->after_term = NULL;
243 stmt->expr = ParseExpr(line);
244 }
245 out_stmts_->push_back(stmt);
246 state_ = is_rule ? ParserState::AFTER_RULE : ParserState::MAYBE_AFTER_RULE;
247 }
248
ParseAssign(StringPiece line,size_t sep)249 void ParseAssign(StringPiece line, size_t sep) {
250 if (sep == 0) {
251 Error("*** empty variable name ***");
252 return;
253 }
254 StringPiece lhs;
255 StringPiece rhs;
256 AssignOp op;
257 ParseAssignStatement(line, sep, &lhs, &rhs, &op);
258
259 AssignStmt* stmt = new AssignStmt();
260 stmt->set_loc(loc_);
261 stmt->lhs = ParseExpr(lhs);
262 stmt->rhs = ParseExpr(rhs);
263 stmt->orig_rhs = rhs;
264 stmt->op = op;
265 stmt->directive = current_directive_;
266 out_stmts_->push_back(stmt);
267 state_ = ParserState::NOT_AFTER_RULE;
268 }
269
ParseInclude(StringPiece line,StringPiece directive)270 void ParseInclude(StringPiece line, StringPiece directive) {
271 IncludeStmt* stmt = new IncludeStmt();
272 stmt->set_loc(loc_);
273 stmt->expr = ParseExpr(line);
274 stmt->should_exist = directive[0] == 'i';
275 out_stmts_->push_back(stmt);
276 state_ = ParserState::NOT_AFTER_RULE;
277 }
278
ParseDefine(StringPiece line,StringPiece)279 void ParseDefine(StringPiece line, StringPiece) {
280 if (line.empty()) {
281 Error("*** empty variable name.");
282 return;
283 }
284 define_name_ = line;
285 num_define_nest_ = 1;
286 define_start_ = 0;
287 define_start_line_ = loc_.lineno;
288 state_ = ParserState::NOT_AFTER_RULE;
289 }
290
ParseInsideDefine(StringPiece line)291 void ParseInsideDefine(StringPiece line) {
292 line = TrimLeftSpace(line);
293 StringPiece directive = GetDirective(line);
294 if (directive == "define")
295 num_define_nest_++;
296 else if (directive == "endef")
297 num_define_nest_--;
298 if (num_define_nest_ > 0) {
299 if (define_start_ == 0)
300 define_start_ = l_;
301 return;
302 }
303
304 StringPiece rest = TrimRightSpace(RemoveComment(TrimLeftSpace(
305 line.substr(sizeof("endef")))));
306 if (!rest.empty()) {
307 WARN_LOC(loc_, "extraneous text after `endef' directive");
308 }
309
310 AssignStmt* stmt = new AssignStmt();
311 stmt->set_loc(Loc(loc_.filename, define_start_line_));
312 stmt->lhs = ParseExpr(define_name_);
313 StringPiece rhs;
314 if (define_start_)
315 rhs = buf_.substr(define_start_, l_ - define_start_ - 1);
316 stmt->rhs = ParseExpr(rhs, ParseExprOpt::DEFINE);
317 stmt->orig_rhs = rhs;
318 stmt->op = AssignOp::EQ;
319 stmt->directive = current_directive_;
320 out_stmts_->push_back(stmt);
321 define_name_.clear();
322 }
323
EnterIf(IfStmt * stmt)324 void EnterIf(IfStmt* stmt) {
325 IfState* st = new IfState();
326 st->stmt = stmt;
327 st->is_in_else = false;
328 st->num_nest = num_if_nest_;
329 if_stack_.push(st);
330 out_stmts_ = &stmt->true_stmts;
331 }
332
ParseIfdef(StringPiece line,StringPiece directive)333 void ParseIfdef(StringPiece line, StringPiece directive) {
334 IfStmt* stmt = new IfStmt();
335 stmt->set_loc(loc_);
336 stmt->op = directive[2] == 'n' ? CondOp::IFNDEF : CondOp::IFDEF;
337 stmt->lhs = ParseExpr(line);
338 stmt->rhs = NULL;
339 out_stmts_->push_back(stmt);
340 EnterIf(stmt);
341 }
342
ParseIfEqCond(StringPiece s,IfStmt * stmt)343 bool ParseIfEqCond(StringPiece s, IfStmt* stmt) {
344 if (s.empty()) {
345 return false;
346 }
347
348 if (s[0] == '(' && s[s.size() - 1] == ')') {
349 s = s.substr(1, s.size() - 2);
350 char terms[] = {',', '\0'};
351 size_t n;
352 stmt->lhs = ParseExprImpl(loc_, s, terms, ParseExprOpt::NORMAL, &n, true);
353 if (s[n] != ',')
354 return false;
355 s = TrimLeftSpace(s.substr(n+1));
356 stmt->rhs = ParseExprImpl(loc_, s, NULL, ParseExprOpt::NORMAL, &n);
357 s = TrimLeftSpace(s.substr(n));
358 } else {
359 for (int i = 0; i < 2; i++) {
360 if (s.empty())
361 return false;
362 char quote = s[0];
363 if (quote != '\'' && quote != '"')
364 return false;
365 size_t end = s.find(quote, 1);
366 if (end == string::npos)
367 return false;
368 Value* v = ParseExpr(s.substr(1, end - 1), ParseExprOpt::NORMAL);
369 if (i == 0)
370 stmt->lhs = v;
371 else
372 stmt->rhs = v;
373 s = TrimLeftSpace(s.substr(end+1));
374 }
375 }
376 if (!s.empty()) {
377 WARN_LOC(loc_, "extraneous text after `ifeq' directive");
378 return true;
379 }
380 return true;
381 }
382
ParseIfeq(StringPiece line,StringPiece directive)383 void ParseIfeq(StringPiece line, StringPiece directive) {
384 IfStmt* stmt = new IfStmt();
385 stmt->set_loc(loc_);
386 stmt->op = directive[2] == 'n' ? CondOp::IFNEQ : CondOp::IFEQ;
387
388 if (!ParseIfEqCond(line, stmt)) {
389 Error("*** invalid syntax in conditional.");
390 return;
391 }
392
393 out_stmts_->push_back(stmt);
394 EnterIf(stmt);
395 }
396
ParseElse(StringPiece line,StringPiece)397 void ParseElse(StringPiece line, StringPiece) {
398 if (!CheckIfStack("else"))
399 return;
400 IfState* st = if_stack_.top();
401 if (st->is_in_else) {
402 Error("*** only one `else' per conditional.");
403 return;
404 }
405 st->is_in_else = true;
406 out_stmts_ = &st->stmt->false_stmts;
407
408 StringPiece next_if = TrimLeftSpace(line);
409 if (next_if.empty())
410 return;
411
412 num_if_nest_ = st->num_nest + 1;
413 if (!HandleDirective(next_if, else_if_directives_)) {
414 WARN_LOC(loc_, "extraneous text after `else' directive");
415 }
416 num_if_nest_ = 0;
417 }
418
ParseEndif(StringPiece line,StringPiece)419 void ParseEndif(StringPiece line, StringPiece) {
420 if (!CheckIfStack("endif"))
421 return;
422 if (!line.empty()) {
423 Error("extraneous text after `endif` directive");
424 return;
425 }
426 IfState st = *if_stack_.top();
427 for (int t = 0; t <= st.num_nest; t++) {
428 delete if_stack_.top();
429 if_stack_.pop();
430 if (if_stack_.empty()) {
431 out_stmts_ = stmts_;
432 } else {
433 IfState* st = if_stack_.top();
434 if (st->is_in_else)
435 out_stmts_ = &st->stmt->false_stmts;
436 else
437 out_stmts_ = &st->stmt->true_stmts;
438 }
439 }
440 }
441
IsInExport() const442 bool IsInExport() const {
443 return (static_cast<int>(current_directive_) &
444 static_cast<int>(AssignDirective::EXPORT));
445 }
446
CreateExport(StringPiece line,bool is_export)447 void CreateExport(StringPiece line, bool is_export) {
448 ExportStmt* stmt = new ExportStmt;
449 stmt->set_loc(loc_);
450 stmt->expr = ParseExpr(line);
451 stmt->is_export = is_export;
452 out_stmts_->push_back(stmt);
453 }
454
ParseOverride(StringPiece line,StringPiece)455 void ParseOverride(StringPiece line, StringPiece) {
456 current_directive_ =
457 static_cast<AssignDirective>(
458 (static_cast<int>(current_directive_) |
459 static_cast<int>(AssignDirective::OVERRIDE)));
460 if (HandleDirective(line, assign_directives_))
461 return;
462 if (IsInExport()) {
463 CreateExport(line, true);
464 }
465 ParseRuleOrAssign(line);
466 }
467
ParseExport(StringPiece line,StringPiece)468 void ParseExport(StringPiece line, StringPiece) {
469 current_directive_ =
470 static_cast<AssignDirective>(
471 (static_cast<int>(current_directive_) |
472 static_cast<int>(AssignDirective::EXPORT)));
473 if (HandleDirective(line, assign_directives_))
474 return;
475 CreateExport(line, true);
476 ParseRuleOrAssign(line);
477 }
478
ParseUnexport(StringPiece line,StringPiece)479 void ParseUnexport(StringPiece line, StringPiece) {
480 CreateExport(line, false);
481 }
482
CheckIfStack(const char * keyword)483 bool CheckIfStack(const char* keyword) {
484 if (if_stack_.empty()) {
485 Error(StringPrintf("*** extraneous `%s'.", keyword));
486 return false;
487 }
488 return true;
489 }
490
RemoveComment(StringPiece line)491 StringPiece RemoveComment(StringPiece line) {
492 size_t i = FindOutsideParen(line, '#');
493 if (i == string::npos)
494 return line;
495 return line.substr(0, i);
496 }
497
GetDirective(StringPiece line)498 StringPiece GetDirective(StringPiece line) {
499 if (line.size() < shortest_directive_len_)
500 return StringPiece();
501 StringPiece prefix = line.substr(0, longest_directive_len_ + 1);
502 size_t space_index = prefix.find_first_of(" \t#");
503 return prefix.substr(0, space_index);
504 }
505
HandleDirective(StringPiece line,const DirectiveMap * directive_map)506 bool HandleDirective(StringPiece line, const DirectiveMap* directive_map) {
507 StringPiece directive = GetDirective(line);
508 auto found = directive_map->find(directive);
509 if (found == directive_map->end())
510 return false;
511
512 StringPiece rest = TrimRightSpace(RemoveComment(TrimLeftSpace(
513 line.substr(directive.size()))));
514 (this->*found->second)(rest, directive);
515 return true;
516 }
517
518 StringPiece buf_;
519 size_t l_;
520 ParserState state_;
521
522 vector<Stmt*>* stmts_;
523 vector<Stmt*>* out_stmts_;
524
525 StringPiece define_name_;
526 int num_define_nest_;
527 size_t define_start_;
528 int define_start_line_;
529
530 StringPiece orig_line_with_directives_;
531 AssignDirective current_directive_;
532
533 int num_if_nest_;
534 stack<IfState*> if_stack_;
535
536 Loc loc_;
537 bool fixed_lineno_;
538
539 static DirectiveMap* make_directives_;
540 static DirectiveMap* else_if_directives_;
541 static DirectiveMap* assign_directives_;
542 static size_t shortest_directive_len_;
543 static size_t longest_directive_len_;
544 };
545
Parse(Makefile * mk)546 void Parse(Makefile* mk) {
547 COLLECT_STATS("parse file time");
548 Parser parser(StringPiece(mk->buf()),
549 mk->filename().c_str(),
550 mk->mutable_stmts());
551 parser.Parse();
552 }
553
Parse(StringPiece buf,const Loc & loc,vector<Stmt * > * out_stmts)554 void Parse(StringPiece buf, const Loc& loc, vector<Stmt*>* out_stmts) {
555 COLLECT_STATS("parse eval time");
556 Parser parser(buf, loc, out_stmts);
557 parser.Parse();
558 }
559
ParseNotAfterRule(StringPiece buf,const Loc & loc,vector<Stmt * > * out_stmts)560 void ParseNotAfterRule(StringPiece buf, const Loc& loc,
561 vector<Stmt*>* out_stmts) {
562 Parser parser(buf, loc, out_stmts);
563 parser.set_state(ParserState::NOT_AFTER_RULE);
564 parser.Parse();
565 }
566
InitParser()567 void InitParser() {
568 Parser::Init();
569 }
570
QuitParser()571 void QuitParser() {
572 Parser::Quit();
573 }
574
575 Parser::DirectiveMap* Parser::make_directives_;
576 Parser::DirectiveMap* Parser::else_if_directives_;
577 Parser::DirectiveMap* Parser::assign_directives_;
578 size_t Parser::shortest_directive_len_;
579 size_t Parser::longest_directive_len_;
580 vector<ParseErrorStmt*> Parser::parse_errors;
581
ParseAssignStatement(StringPiece line,size_t sep,StringPiece * lhs,StringPiece * rhs,AssignOp * op)582 void ParseAssignStatement(StringPiece line, size_t sep,
583 StringPiece* lhs, StringPiece* rhs, AssignOp* op) {
584 CHECK(sep != 0);
585 *op = AssignOp::EQ;
586 size_t lhs_end = sep;
587 switch (line[sep-1]) {
588 case ':':
589 lhs_end--;
590 *op = AssignOp::COLON_EQ;
591 break;
592 case '+':
593 lhs_end--;
594 *op = AssignOp::PLUS_EQ;
595 break;
596 case '?':
597 lhs_end--;
598 *op = AssignOp::QUESTION_EQ;
599 break;
600 }
601 *lhs = TrimSpace(line.substr(0, lhs_end));
602 *rhs = TrimLeftSpace(line.substr(sep + 1));
603 }
604
GetParseErrors()605 const vector<ParseErrorStmt*>& GetParseErrors() {
606 return Parser::parse_errors;
607 }
608