Home | History | Annotate | Download | only in kati 
      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:
     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       : 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 
     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 
     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 
    134   static void Quit() { delete make_directives_; }
    135 
    136   void set_state(ParserState st) { state_ = st; }
    137 
    138   static vector<ParseErrorStmt*> parse_errors;
    139 
    140  private:
    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 
    149   size_t FindEndOfLine(size_t* lf_cnt) {
    150     return ::FindEndOfLine(buf_, l_, lf_cnt);
    151   }
    152 
    153   Value* ParseExpr(StringPiece s, ParseExprOpt opt = ParseExprOpt::NORMAL) {
    154     return ::ParseExpr(loc_, s, opt);
    155   }
    156 
    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 
    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 
    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* stmt = new RuleStmt();
    225     stmt->set_loc(loc_);
    226 
    227     size_t found = FindTwoOutsideParen(line.substr(sep + 1), '=', ';');
    228     if (found != string::npos) {
    229       found += sep + 1;
    230       stmt->term = line[found];
    231       ParseExprOpt opt =
    232           stmt->term == ';' ? ParseExprOpt::COMMAND : ParseExprOpt::NORMAL;
    233       stmt->after_term = ParseExpr(TrimLeftSpace(line.substr(found + 1)), opt);
    234       stmt->expr = ParseExpr(TrimSpace(line.substr(0, found)));
    235     } else {
    236       stmt->term = 0;
    237       stmt->after_term = NULL;
    238       stmt->expr = ParseExpr(line);
    239     }
    240     out_stmts_->push_back(stmt);
    241     state_ = is_rule ? ParserState::AFTER_RULE : ParserState::MAYBE_AFTER_RULE;
    242   }
    243 
    244   void ParseAssign(StringPiece line, size_t sep) {
    245     if (sep == 0) {
    246       Error("*** empty variable name ***");
    247       return;
    248     }
    249     StringPiece lhs;
    250     StringPiece rhs;
    251     AssignOp op;
    252     ParseAssignStatement(line, sep, &lhs, &rhs, &op);
    253 
    254     AssignStmt* stmt = new AssignStmt();
    255     stmt->set_loc(loc_);
    256     stmt->lhs = ParseExpr(lhs);
    257     stmt->rhs = ParseExpr(rhs);
    258     stmt->orig_rhs = rhs;
    259     stmt->op = op;
    260     stmt->directive = current_directive_;
    261     out_stmts_->push_back(stmt);
    262     state_ = ParserState::NOT_AFTER_RULE;
    263   }
    264 
    265   void ParseInclude(StringPiece line, StringPiece directive) {
    266     IncludeStmt* stmt = new IncludeStmt();
    267     stmt->set_loc(loc_);
    268     stmt->expr = ParseExpr(line);
    269     stmt->should_exist = directive[0] == 'i';
    270     out_stmts_->push_back(stmt);
    271     state_ = ParserState::NOT_AFTER_RULE;
    272   }
    273 
    274   void ParseDefine(StringPiece line, StringPiece) {
    275     if (line.empty()) {
    276       Error("*** empty variable name.");
    277       return;
    278     }
    279     define_name_ = line;
    280     num_define_nest_ = 1;
    281     define_start_ = 0;
    282     define_start_line_ = loc_.lineno;
    283     state_ = ParserState::NOT_AFTER_RULE;
    284   }
    285 
    286   void ParseInsideDefine(StringPiece line) {
    287     line = TrimLeftSpace(line);
    288     StringPiece directive = GetDirective(line);
    289     if (directive == "define")
    290       num_define_nest_++;
    291     else if (directive == "endef")
    292       num_define_nest_--;
    293     if (num_define_nest_ > 0) {
    294       if (define_start_ == 0)
    295         define_start_ = l_;
    296       return;
    297     }
    298 
    299     StringPiece rest = TrimRightSpace(
    300         RemoveComment(TrimLeftSpace(line.substr(sizeof("endef")))));
    301     if (!rest.empty()) {
    302       WARN_LOC(loc_, "extraneous text after `endef' directive");
    303     }
    304 
    305     AssignStmt* stmt = new AssignStmt();
    306     stmt->set_loc(Loc(loc_.filename, define_start_line_));
    307     stmt->lhs = ParseExpr(define_name_);
    308     StringPiece rhs;
    309     if (define_start_)
    310       rhs = buf_.substr(define_start_, l_ - define_start_ - 1);
    311     stmt->rhs = ParseExpr(rhs, ParseExprOpt::DEFINE);
    312     stmt->orig_rhs = rhs;
    313     stmt->op = AssignOp::EQ;
    314     stmt->directive = current_directive_;
    315     out_stmts_->push_back(stmt);
    316     define_name_.clear();
    317   }
    318 
    319   void EnterIf(IfStmt* stmt) {
    320     IfState* st = new IfState();
    321     st->stmt = stmt;
    322     st->is_in_else = false;
    323     st->num_nest = num_if_nest_;
    324     if_stack_.push(st);
    325     out_stmts_ = &stmt->true_stmts;
    326   }
    327 
    328   void ParseIfdef(StringPiece line, StringPiece directive) {
    329     IfStmt* stmt = new IfStmt();
    330     stmt->set_loc(loc_);
    331     stmt->op = directive[2] == 'n' ? CondOp::IFNDEF : CondOp::IFDEF;
    332     stmt->lhs = ParseExpr(line);
    333     stmt->rhs = NULL;
    334     out_stmts_->push_back(stmt);
    335     EnterIf(stmt);
    336   }
    337 
    338   bool ParseIfEqCond(StringPiece s, IfStmt* stmt) {
    339     if (s.empty()) {
    340       return false;
    341     }
    342 
    343     if (s[0] == '(' && s[s.size() - 1] == ')') {
    344       s = s.substr(1, s.size() - 2);
    345       char terms[] = {',', '\0'};
    346       size_t n;
    347       stmt->lhs = ParseExprImpl(loc_, s, terms, ParseExprOpt::NORMAL, &n, true);
    348       if (s[n] != ',')
    349         return false;
    350       s = TrimLeftSpace(s.substr(n + 1));
    351       stmt->rhs = ParseExprImpl(loc_, s, NULL, ParseExprOpt::NORMAL, &n);
    352       s = TrimLeftSpace(s.substr(n));
    353     } else {
    354       for (int i = 0; i < 2; i++) {
    355         if (s.empty())
    356           return false;
    357         char quote = s[0];
    358         if (quote != '\'' && quote != '"')
    359           return false;
    360         size_t end = s.find(quote, 1);
    361         if (end == string::npos)
    362           return false;
    363         Value* v = ParseExpr(s.substr(1, end - 1), ParseExprOpt::NORMAL);
    364         if (i == 0)
    365           stmt->lhs = v;
    366         else
    367           stmt->rhs = v;
    368         s = TrimLeftSpace(s.substr(end + 1));
    369       }
    370     }
    371     if (!s.empty()) {
    372       WARN_LOC(loc_, "extraneous text after `ifeq' directive");
    373       return true;
    374     }
    375     return true;
    376   }
    377 
    378   void ParseIfeq(StringPiece line, StringPiece directive) {
    379     IfStmt* stmt = new IfStmt();
    380     stmt->set_loc(loc_);
    381     stmt->op = directive[2] == 'n' ? CondOp::IFNEQ : CondOp::IFEQ;
    382 
    383     if (!ParseIfEqCond(line, stmt)) {
    384       Error("*** invalid syntax in conditional.");
    385       return;
    386     }
    387 
    388     out_stmts_->push_back(stmt);
    389     EnterIf(stmt);
    390   }
    391 
    392   void ParseElse(StringPiece line, StringPiece) {
    393     if (!CheckIfStack("else"))
    394       return;
    395     IfState* st = if_stack_.top();
    396     if (st->is_in_else) {
    397       Error("*** only one `else' per conditional.");
    398       return;
    399     }
    400     st->is_in_else = true;
    401     out_stmts_ = &st->stmt->false_stmts;
    402 
    403     StringPiece next_if = TrimLeftSpace(line);
    404     if (next_if.empty())
    405       return;
    406 
    407     num_if_nest_ = st->num_nest + 1;
    408     if (!HandleDirective(next_if, else_if_directives_)) {
    409       WARN_LOC(loc_, "extraneous text after `else' directive");
    410     }
    411     num_if_nest_ = 0;
    412   }
    413 
    414   void ParseEndif(StringPiece line, StringPiece) {
    415     if (!CheckIfStack("endif"))
    416       return;
    417     if (!line.empty()) {
    418       Error("extraneous text after `endif` directive");
    419       return;
    420     }
    421     IfState st = *if_stack_.top();
    422     for (int t = 0; t <= st.num_nest; t++) {
    423       delete if_stack_.top();
    424       if_stack_.pop();
    425       if (if_stack_.empty()) {
    426         out_stmts_ = stmts_;
    427       } else {
    428         IfState* st = if_stack_.top();
    429         if (st->is_in_else)
    430           out_stmts_ = &st->stmt->false_stmts;
    431         else
    432           out_stmts_ = &st->stmt->true_stmts;
    433       }
    434     }
    435   }
    436 
    437   bool IsInExport() const {
    438     return (static_cast<int>(current_directive_) &
    439             static_cast<int>(AssignDirective::EXPORT));
    440   }
    441 
    442   void CreateExport(StringPiece line, bool is_export) {
    443     ExportStmt* stmt = new ExportStmt;
    444     stmt->set_loc(loc_);
    445     stmt->expr = ParseExpr(line);
    446     stmt->is_export = is_export;
    447     out_stmts_->push_back(stmt);
    448   }
    449 
    450   void ParseOverride(StringPiece line, StringPiece) {
    451     current_directive_ = static_cast<AssignDirective>(
    452         (static_cast<int>(current_directive_) |
    453          static_cast<int>(AssignDirective::OVERRIDE)));
    454     if (HandleDirective(line, assign_directives_))
    455       return;
    456     if (IsInExport()) {
    457       CreateExport(line, true);
    458     }
    459     ParseRuleOrAssign(line);
    460   }
    461 
    462   void ParseExport(StringPiece line, StringPiece) {
    463     current_directive_ = static_cast<AssignDirective>(
    464         (static_cast<int>(current_directive_) |
    465          static_cast<int>(AssignDirective::EXPORT)));
    466     if (HandleDirective(line, assign_directives_))
    467       return;
    468     CreateExport(line, true);
    469     ParseRuleOrAssign(line);
    470   }
    471 
    472   void ParseUnexport(StringPiece line, StringPiece) {
    473     CreateExport(line, false);
    474   }
    475 
    476   bool CheckIfStack(const char* keyword) {
    477     if (if_stack_.empty()) {
    478       Error(StringPrintf("*** extraneous `%s'.", keyword));
    479       return false;
    480     }
    481     return true;
    482   }
    483 
    484   StringPiece RemoveComment(StringPiece line) {
    485     size_t i = FindOutsideParen(line, '#');
    486     if (i == string::npos)
    487       return line;
    488     return line.substr(0, i);
    489   }
    490 
    491   StringPiece GetDirective(StringPiece line) {
    492     if (line.size() < shortest_directive_len_)
    493       return StringPiece();
    494     StringPiece prefix = line.substr(0, longest_directive_len_ + 1);
    495     size_t space_index = prefix.find_first_of(" \t#");
    496     return prefix.substr(0, space_index);
    497   }
    498 
    499   bool HandleDirective(StringPiece line, const DirectiveMap* directive_map) {
    500     StringPiece directive = GetDirective(line);
    501     auto found = directive_map->find(directive);
    502     if (found == directive_map->end())
    503       return false;
    504 
    505     StringPiece rest = TrimRightSpace(
    506         RemoveComment(TrimLeftSpace(line.substr(directive.size()))));
    507     (this->*found->second)(rest, directive);
    508     return true;
    509   }
    510 
    511   StringPiece buf_;
    512   size_t l_;
    513   ParserState state_;
    514 
    515   vector<Stmt*>* stmts_;
    516   vector<Stmt*>* out_stmts_;
    517 
    518   StringPiece define_name_;
    519   int num_define_nest_;
    520   size_t define_start_;
    521   int define_start_line_;
    522 
    523   StringPiece orig_line_with_directives_;
    524   AssignDirective current_directive_;
    525 
    526   int num_if_nest_;
    527   stack<IfState*> if_stack_;
    528 
    529   Loc loc_;
    530   bool fixed_lineno_;
    531 
    532   static DirectiveMap* make_directives_;
    533   static DirectiveMap* else_if_directives_;
    534   static DirectiveMap* assign_directives_;
    535   static size_t shortest_directive_len_;
    536   static size_t longest_directive_len_;
    537 };
    538 
    539 void Parse(Makefile* mk) {
    540   COLLECT_STATS("parse file time");
    541   Parser parser(StringPiece(mk->buf()), mk->filename().c_str(),
    542                 mk->mutable_stmts());
    543   parser.Parse();
    544 }
    545 
    546 void Parse(StringPiece buf, const Loc& loc, vector<Stmt*>* out_stmts) {
    547   COLLECT_STATS("parse eval time");
    548   Parser parser(buf, loc, out_stmts);
    549   parser.Parse();
    550 }
    551 
    552 void ParseNotAfterRule(StringPiece buf,
    553                        const Loc& loc,
    554                        vector<Stmt*>* out_stmts) {
    555   Parser parser(buf, loc, out_stmts);
    556   parser.set_state(ParserState::NOT_AFTER_RULE);
    557   parser.Parse();
    558 }
    559 
    560 void InitParser() {
    561   Parser::Init();
    562 }
    563 
    564 void QuitParser() {
    565   Parser::Quit();
    566 }
    567 
    568 Parser::DirectiveMap* Parser::make_directives_;
    569 Parser::DirectiveMap* Parser::else_if_directives_;
    570 Parser::DirectiveMap* Parser::assign_directives_;
    571 size_t Parser::shortest_directive_len_;
    572 size_t Parser::longest_directive_len_;
    573 vector<ParseErrorStmt*> Parser::parse_errors;
    574 
    575 void ParseAssignStatement(StringPiece line,
    576                           size_t sep,
    577                           StringPiece* lhs,
    578                           StringPiece* rhs,
    579                           AssignOp* op) {
    580   CHECK(sep != 0);
    581   *op = AssignOp::EQ;
    582   size_t lhs_end = sep;
    583   switch (line[sep - 1]) {
    584     case ':':
    585       lhs_end--;
    586       *op = AssignOp::COLON_EQ;
    587       break;
    588     case '+':
    589       lhs_end--;
    590       *op = AssignOp::PLUS_EQ;
    591       break;
    592     case '?':
    593       lhs_end--;
    594       *op = AssignOp::QUESTION_EQ;
    595       break;
    596   }
    597   *lhs = TrimSpace(line.substr(0, lhs_end));
    598   *rhs = TrimLeftSpace(line.substr(sep + 1));
    599 }
    600 
    601 const vector<ParseErrorStmt*>& GetParseErrors() {
    602   return Parser::parse_errors;
    603 }
    604