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
31enum struct ParserState {
32  NOT_AFTER_RULE = 0,
33  AFTER_RULE,
34  MAYBE_AFTER_RULE,
35};
36
37class 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:
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
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
70  ~Parser() {
71  }
72
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
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
137  static void Quit() {
138    delete make_directives_;
139  }
140
141  void set_state(ParserState st) { state_ = st; }
142
143  static vector<ParseErrorStmt*> parse_errors;
144
145 private:
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
154  size_t FindEndOfLine(size_t* lf_cnt) {
155    return ::FindEndOfLine(buf_, l_, lf_cnt);
156  }
157
158  Value* ParseExpr(StringPiece s, ParseExprOpt opt = ParseExprOpt::NORMAL) {
159    return ::ParseExpr(loc_, s, opt);
160  }
161
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
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
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
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
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
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
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
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
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
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
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
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
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
442  bool IsInExport() const {
443    return (static_cast<int>(current_directive_) &
444            static_cast<int>(AssignDirective::EXPORT));
445  }
446
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
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
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
479  void ParseUnexport(StringPiece line, StringPiece) {
480    CreateExport(line, false);
481  }
482
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
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
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
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
546void 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
554void 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
560void 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
567void InitParser() {
568  Parser::Init();
569}
570
571void QuitParser() {
572  Parser::Quit();
573}
574
575Parser::DirectiveMap* Parser::make_directives_;
576Parser::DirectiveMap* Parser::else_if_directives_;
577Parser::DirectiveMap* Parser::assign_directives_;
578size_t Parser::shortest_directive_len_;
579size_t Parser::longest_directive_len_;
580vector<ParseErrorStmt*> Parser::parse_errors;
581
582void 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
605const vector<ParseErrorStmt*>& GetParseErrors() {
606  return Parser::parse_errors;
607}
608