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