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