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)(
     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 
    546 void 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 
    554 void 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 
    560 void 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 
    567 void InitParser() {
    568   Parser::Init();
    569 }
    570 
    571 void QuitParser() {
    572   Parser::Quit();
    573 }
    574 
    575 Parser::DirectiveMap* Parser::make_directives_;
    576 Parser::DirectiveMap* Parser::else_if_directives_;
    577 Parser::DirectiveMap* Parser::assign_directives_;
    578 size_t Parser::shortest_directive_len_;
    579 size_t Parser::longest_directive_len_;
    580 vector<ParseErrorStmt*> Parser::parse_errors;
    581 
    582 void 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 
    605 const vector<ParseErrorStmt*>& GetParseErrors() {
    606   return Parser::parse_errors;
    607 }
    608