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