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* stmt = new RuleStmt(); 225 stmt->set_loc(loc_); 226 227 size_t found = FindTwoOutsideParen(line.substr(sep + 1), '=', ';'); 228 if (found != string::npos) { 229 found += sep + 1; 230 stmt->term = line[found]; 231 ParseExprOpt opt = 232 stmt->term == ';' ? ParseExprOpt::COMMAND : ParseExprOpt::NORMAL; 233 stmt->after_term = ParseExpr(TrimLeftSpace(line.substr(found + 1)), opt); 234 stmt->expr = ParseExpr(TrimSpace(line.substr(0, found))); 235 } else { 236 stmt->term = 0; 237 stmt->after_term = NULL; 238 stmt->expr = ParseExpr(line); 239 } 240 out_stmts_->push_back(stmt); 241 state_ = is_rule ? ParserState::AFTER_RULE : ParserState::MAYBE_AFTER_RULE; 242 } 243 244 void ParseAssign(StringPiece line, size_t sep) { 245 if (sep == 0) { 246 Error("*** empty variable name ***"); 247 return; 248 } 249 StringPiece lhs; 250 StringPiece rhs; 251 AssignOp op; 252 ParseAssignStatement(line, sep, &lhs, &rhs, &op); 253 254 AssignStmt* stmt = new AssignStmt(); 255 stmt->set_loc(loc_); 256 stmt->lhs = ParseExpr(lhs); 257 stmt->rhs = ParseExpr(rhs); 258 stmt->orig_rhs = rhs; 259 stmt->op = op; 260 stmt->directive = current_directive_; 261 out_stmts_->push_back(stmt); 262 state_ = ParserState::NOT_AFTER_RULE; 263 } 264 265 void ParseInclude(StringPiece line, StringPiece directive) { 266 IncludeStmt* stmt = new IncludeStmt(); 267 stmt->set_loc(loc_); 268 stmt->expr = ParseExpr(line); 269 stmt->should_exist = directive[0] == 'i'; 270 out_stmts_->push_back(stmt); 271 state_ = ParserState::NOT_AFTER_RULE; 272 } 273 274 void ParseDefine(StringPiece line, StringPiece) { 275 if (line.empty()) { 276 Error("*** empty variable name."); 277 return; 278 } 279 define_name_ = line; 280 num_define_nest_ = 1; 281 define_start_ = 0; 282 define_start_line_ = loc_.lineno; 283 state_ = ParserState::NOT_AFTER_RULE; 284 } 285 286 void ParseInsideDefine(StringPiece line) { 287 line = TrimLeftSpace(line); 288 StringPiece directive = GetDirective(line); 289 if (directive == "define") 290 num_define_nest_++; 291 else if (directive == "endef") 292 num_define_nest_--; 293 if (num_define_nest_ > 0) { 294 if (define_start_ == 0) 295 define_start_ = l_; 296 return; 297 } 298 299 StringPiece rest = TrimRightSpace( 300 RemoveComment(TrimLeftSpace(line.substr(sizeof("endef"))))); 301 if (!rest.empty()) { 302 WARN_LOC(loc_, "extraneous text after `endef' directive"); 303 } 304 305 AssignStmt* stmt = new AssignStmt(); 306 stmt->set_loc(Loc(loc_.filename, define_start_line_)); 307 stmt->lhs = ParseExpr(define_name_); 308 StringPiece rhs; 309 if (define_start_) 310 rhs = buf_.substr(define_start_, l_ - define_start_ - 1); 311 stmt->rhs = ParseExpr(rhs, ParseExprOpt::DEFINE); 312 stmt->orig_rhs = rhs; 313 stmt->op = AssignOp::EQ; 314 stmt->directive = current_directive_; 315 out_stmts_->push_back(stmt); 316 define_name_.clear(); 317 } 318 319 void EnterIf(IfStmt* stmt) { 320 IfState* st = new IfState(); 321 st->stmt = stmt; 322 st->is_in_else = false; 323 st->num_nest = num_if_nest_; 324 if_stack_.push(st); 325 out_stmts_ = &stmt->true_stmts; 326 } 327 328 void ParseIfdef(StringPiece line, StringPiece directive) { 329 IfStmt* stmt = new IfStmt(); 330 stmt->set_loc(loc_); 331 stmt->op = directive[2] == 'n' ? CondOp::IFNDEF : CondOp::IFDEF; 332 stmt->lhs = ParseExpr(line); 333 stmt->rhs = NULL; 334 out_stmts_->push_back(stmt); 335 EnterIf(stmt); 336 } 337 338 bool ParseIfEqCond(StringPiece s, IfStmt* stmt) { 339 if (s.empty()) { 340 return false; 341 } 342 343 if (s[0] == '(' && s[s.size() - 1] == ')') { 344 s = s.substr(1, s.size() - 2); 345 char terms[] = {',', '\0'}; 346 size_t n; 347 stmt->lhs = ParseExprImpl(loc_, s, terms, ParseExprOpt::NORMAL, &n, true); 348 if (s[n] != ',') 349 return false; 350 s = TrimLeftSpace(s.substr(n + 1)); 351 stmt->rhs = ParseExprImpl(loc_, s, NULL, ParseExprOpt::NORMAL, &n); 352 s = TrimLeftSpace(s.substr(n)); 353 } else { 354 for (int i = 0; i < 2; i++) { 355 if (s.empty()) 356 return false; 357 char quote = s[0]; 358 if (quote != '\'' && quote != '"') 359 return false; 360 size_t end = s.find(quote, 1); 361 if (end == string::npos) 362 return false; 363 Value* v = ParseExpr(s.substr(1, end - 1), ParseExprOpt::NORMAL); 364 if (i == 0) 365 stmt->lhs = v; 366 else 367 stmt->rhs = v; 368 s = TrimLeftSpace(s.substr(end + 1)); 369 } 370 } 371 if (!s.empty()) { 372 WARN_LOC(loc_, "extraneous text after `ifeq' directive"); 373 return true; 374 } 375 return true; 376 } 377 378 void ParseIfeq(StringPiece line, StringPiece directive) { 379 IfStmt* stmt = new IfStmt(); 380 stmt->set_loc(loc_); 381 stmt->op = directive[2] == 'n' ? CondOp::IFNEQ : CondOp::IFEQ; 382 383 if (!ParseIfEqCond(line, stmt)) { 384 Error("*** invalid syntax in conditional."); 385 return; 386 } 387 388 out_stmts_->push_back(stmt); 389 EnterIf(stmt); 390 } 391 392 void ParseElse(StringPiece line, StringPiece) { 393 if (!CheckIfStack("else")) 394 return; 395 IfState* st = if_stack_.top(); 396 if (st->is_in_else) { 397 Error("*** only one `else' per conditional."); 398 return; 399 } 400 st->is_in_else = true; 401 out_stmts_ = &st->stmt->false_stmts; 402 403 StringPiece next_if = TrimLeftSpace(line); 404 if (next_if.empty()) 405 return; 406 407 num_if_nest_ = st->num_nest + 1; 408 if (!HandleDirective(next_if, else_if_directives_)) { 409 WARN_LOC(loc_, "extraneous text after `else' directive"); 410 } 411 num_if_nest_ = 0; 412 } 413 414 void ParseEndif(StringPiece line, StringPiece) { 415 if (!CheckIfStack("endif")) 416 return; 417 if (!line.empty()) { 418 Error("extraneous text after `endif` directive"); 419 return; 420 } 421 IfState st = *if_stack_.top(); 422 for (int t = 0; t <= st.num_nest; t++) { 423 delete if_stack_.top(); 424 if_stack_.pop(); 425 if (if_stack_.empty()) { 426 out_stmts_ = stmts_; 427 } else { 428 IfState* st = if_stack_.top(); 429 if (st->is_in_else) 430 out_stmts_ = &st->stmt->false_stmts; 431 else 432 out_stmts_ = &st->stmt->true_stmts; 433 } 434 } 435 } 436 437 bool IsInExport() const { 438 return (static_cast<int>(current_directive_) & 439 static_cast<int>(AssignDirective::EXPORT)); 440 } 441 442 void CreateExport(StringPiece line, bool is_export) { 443 ExportStmt* stmt = new ExportStmt; 444 stmt->set_loc(loc_); 445 stmt->expr = ParseExpr(line); 446 stmt->is_export = is_export; 447 out_stmts_->push_back(stmt); 448 } 449 450 void ParseOverride(StringPiece line, StringPiece) { 451 current_directive_ = static_cast<AssignDirective>( 452 (static_cast<int>(current_directive_) | 453 static_cast<int>(AssignDirective::OVERRIDE))); 454 if (HandleDirective(line, assign_directives_)) 455 return; 456 if (IsInExport()) { 457 CreateExport(line, true); 458 } 459 ParseRuleOrAssign(line); 460 } 461 462 void ParseExport(StringPiece line, StringPiece) { 463 current_directive_ = static_cast<AssignDirective>( 464 (static_cast<int>(current_directive_) | 465 static_cast<int>(AssignDirective::EXPORT))); 466 if (HandleDirective(line, assign_directives_)) 467 return; 468 CreateExport(line, true); 469 ParseRuleOrAssign(line); 470 } 471 472 void ParseUnexport(StringPiece line, StringPiece) { 473 CreateExport(line, false); 474 } 475 476 bool CheckIfStack(const char* keyword) { 477 if (if_stack_.empty()) { 478 Error(StringPrintf("*** extraneous `%s'.", keyword)); 479 return false; 480 } 481 return true; 482 } 483 484 StringPiece RemoveComment(StringPiece line) { 485 size_t i = FindOutsideParen(line, '#'); 486 if (i == string::npos) 487 return line; 488 return line.substr(0, i); 489 } 490 491 StringPiece GetDirective(StringPiece line) { 492 if (line.size() < shortest_directive_len_) 493 return StringPiece(); 494 StringPiece prefix = line.substr(0, longest_directive_len_ + 1); 495 size_t space_index = prefix.find_first_of(" \t#"); 496 return prefix.substr(0, space_index); 497 } 498 499 bool HandleDirective(StringPiece line, const DirectiveMap* directive_map) { 500 StringPiece directive = GetDirective(line); 501 auto found = directive_map->find(directive); 502 if (found == directive_map->end()) 503 return false; 504 505 StringPiece rest = TrimRightSpace( 506 RemoveComment(TrimLeftSpace(line.substr(directive.size())))); 507 (this->*found->second)(rest, directive); 508 return true; 509 } 510 511 StringPiece buf_; 512 size_t l_; 513 ParserState state_; 514 515 vector<Stmt*>* stmts_; 516 vector<Stmt*>* out_stmts_; 517 518 StringPiece define_name_; 519 int num_define_nest_; 520 size_t define_start_; 521 int define_start_line_; 522 523 StringPiece orig_line_with_directives_; 524 AssignDirective current_directive_; 525 526 int num_if_nest_; 527 stack<IfState*> if_stack_; 528 529 Loc loc_; 530 bool fixed_lineno_; 531 532 static DirectiveMap* make_directives_; 533 static DirectiveMap* else_if_directives_; 534 static DirectiveMap* assign_directives_; 535 static size_t shortest_directive_len_; 536 static size_t longest_directive_len_; 537 }; 538 539 void Parse(Makefile* mk) { 540 COLLECT_STATS("parse file time"); 541 Parser parser(StringPiece(mk->buf()), mk->filename().c_str(), 542 mk->mutable_stmts()); 543 parser.Parse(); 544 } 545 546 void Parse(StringPiece buf, const Loc& loc, vector<Stmt*>* out_stmts) { 547 COLLECT_STATS("parse eval time"); 548 Parser parser(buf, loc, out_stmts); 549 parser.Parse(); 550 } 551 552 void ParseNotAfterRule(StringPiece buf, 553 const Loc& loc, 554 vector<Stmt*>* out_stmts) { 555 Parser parser(buf, loc, out_stmts); 556 parser.set_state(ParserState::NOT_AFTER_RULE); 557 parser.Parse(); 558 } 559 560 void InitParser() { 561 Parser::Init(); 562 } 563 564 void QuitParser() { 565 Parser::Quit(); 566 } 567 568 Parser::DirectiveMap* Parser::make_directives_; 569 Parser::DirectiveMap* Parser::else_if_directives_; 570 Parser::DirectiveMap* Parser::assign_directives_; 571 size_t Parser::shortest_directive_len_; 572 size_t Parser::longest_directive_len_; 573 vector<ParseErrorStmt*> Parser::parse_errors; 574 575 void ParseAssignStatement(StringPiece line, 576 size_t sep, 577 StringPiece* lhs, 578 StringPiece* rhs, 579 AssignOp* op) { 580 CHECK(sep != 0); 581 *op = AssignOp::EQ; 582 size_t lhs_end = sep; 583 switch (line[sep - 1]) { 584 case ':': 585 lhs_end--; 586 *op = AssignOp::COLON_EQ; 587 break; 588 case '+': 589 lhs_end--; 590 *op = AssignOp::PLUS_EQ; 591 break; 592 case '?': 593 lhs_end--; 594 *op = AssignOp::QUESTION_EQ; 595 break; 596 } 597 *lhs = TrimSpace(line.substr(0, lhs_end)); 598 *rhs = TrimLeftSpace(line.substr(sep + 1)); 599 } 600 601 const vector<ParseErrorStmt*>& GetParseErrors() { 602 return Parser::parse_errors; 603 } 604