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