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