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