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* 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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    459   bool IsInExport() const {
    460     return (static_cast<int>(current_directive_) &
    461             static_cast<int>(AssignDirective::EXPORT));
    462   }
    463 
    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 
    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 
    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 
    494   void ParseUnexport(StringPiece line, StringPiece) {
    495     CreateExport(line, false);
    496   }
    497 
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    582 void InitParser() {
    583   Parser::Init();
    584 }
    585 
    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 
    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 
    623 const vector<ParseErrorStmt*>& GetParseErrors() {
    624   return Parser::parse_errors;
    625 }
    626