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 "dep.h" 18 19 #include <algorithm> 20 #include <iterator> 21 #include <map> 22 #include <memory> 23 #include <unordered_map> 24 #include <unordered_set> 25 26 #include "eval.h" 27 #include "fileutil.h" 28 #include "flags.h" 29 #include "log.h" 30 #include "rule.h" 31 #include "stats.h" 32 #include "strutil.h" 33 #include "symtab.h" 34 #include "timeutil.h" 35 #include "var.h" 36 37 namespace { 38 39 static vector<DepNode*>* g_dep_node_pool; 40 41 static Symbol ReplaceSuffix(Symbol s, Symbol newsuf) { 42 string r; 43 AppendString(StripExt(s.str()), &r); 44 r += '.'; 45 AppendString(newsuf.str(), &r); 46 return Intern(r); 47 } 48 49 void ApplyOutputPattern(const Rule& r, 50 Symbol output, 51 const vector<Symbol>& inputs, 52 vector<Symbol>* out_inputs) { 53 if (inputs.empty()) 54 return; 55 if (r.is_suffix_rule) { 56 for (Symbol input : inputs) { 57 out_inputs->push_back(ReplaceSuffix(output, input)); 58 } 59 return; 60 } 61 if (r.output_patterns.empty()) { 62 copy(inputs.begin(), inputs.end(), back_inserter(*out_inputs)); 63 return; 64 } 65 CHECK(r.output_patterns.size() == 1); 66 Pattern pat(r.output_patterns[0].str()); 67 for (Symbol input : inputs) { 68 string buf; 69 pat.AppendSubst(output.str(), input.str(), &buf); 70 out_inputs->push_back(Intern(buf)); 71 } 72 } 73 74 class RuleTrie { 75 struct Entry { 76 Entry(const Rule* r, StringPiece s) 77 : rule(r), suffix(s) { 78 } 79 const Rule* rule; 80 StringPiece suffix; 81 }; 82 83 public: 84 RuleTrie() {} 85 ~RuleTrie() { 86 for (auto& p : children_) 87 delete p.second; 88 } 89 90 void Add(StringPiece name, const Rule* rule) { 91 if (name.empty() || name[0] == '%') { 92 rules_.push_back(Entry(rule, name)); 93 return; 94 } 95 const char c = name[0]; 96 auto p = children_.emplace(c, nullptr); 97 if (p.second) { 98 p.first->second = new RuleTrie(); 99 } 100 p.first->second->Add(name.substr(1), rule); 101 } 102 103 void Get(StringPiece name, vector<const Rule*>* rules) const { 104 for (const Entry& ent : rules_) { 105 if ((ent.suffix.empty() && name.empty()) || 106 HasSuffix(name, ent.suffix.substr(1))) { 107 rules->push_back(ent.rule); 108 } 109 } 110 if (name.empty()) 111 return; 112 auto found = children_.find(name[0]); 113 if (found != children_.end()) { 114 found->second->Get(name.substr(1), rules); 115 } 116 } 117 118 size_t size() const { 119 size_t r = rules_.size(); 120 for (const auto& c : children_) 121 r += c.second->size(); 122 return r; 123 } 124 125 private: 126 vector<Entry> rules_; 127 unordered_map<char, RuleTrie*> children_; 128 }; 129 130 131 bool IsSuffixRule(Symbol output) { 132 if (output.empty() || output.str()[0] != '.') 133 return false; 134 const StringPiece rest = StringPiece(output.str()).substr(1); 135 size_t dot_index = rest.find('.'); 136 // If there is only a single dot or the third dot, this is not a 137 // suffix rule. 138 if (dot_index == string::npos || 139 rest.substr(dot_index+1).find('.') != string::npos) { 140 return false; 141 } 142 return true; 143 } 144 145 struct RuleMerger { 146 vector<const Rule*> rules; 147 const Rule* primary_rule; 148 bool is_double_colon; 149 150 RuleMerger() 151 : primary_rule(nullptr), 152 is_double_colon(false) { 153 } 154 155 void AddRule(Symbol output, const Rule* r) { 156 if (rules.empty()) { 157 is_double_colon = r->is_double_colon; 158 } else if (is_double_colon != r->is_double_colon) { 159 ERROR_LOC(r->loc, "*** target file `%s' has both : and :: entries.", 160 output.c_str()); 161 } 162 163 if (primary_rule && !r->cmds.empty() && 164 !IsSuffixRule(output) && !r->is_double_colon) { 165 if (g_flags.werror_overriding_commands) { 166 ERROR_LOC(r->cmd_loc(), 167 "*** overriding commands for target `%s', previously defined at %s:%d", 168 output.c_str(), LOCF(primary_rule->cmd_loc())); 169 } else { 170 WARN_LOC(r->cmd_loc(), 171 "warning: overriding commands for target `%s'", 172 output.c_str()); 173 WARN_LOC(primary_rule->cmd_loc(), 174 "warning: ignoring old commands for target `%s'", 175 output.c_str()); 176 } 177 primary_rule = r; 178 } 179 if (!primary_rule && !r->cmds.empty()) { 180 primary_rule = r; 181 } 182 183 rules.push_back(r); 184 } 185 186 void FillDepNodeFromRule(Symbol output, 187 const Rule* r, 188 DepNode* n) const { 189 if (is_double_colon) 190 copy(r->cmds.begin(), r->cmds.end(), back_inserter(n->cmds)); 191 192 ApplyOutputPattern(*r, output, r->inputs, &n->actual_inputs); 193 ApplyOutputPattern(*r, output, r->order_only_inputs, 194 &n->actual_order_only_inputs); 195 196 if (r->output_patterns.size() >= 1) { 197 CHECK(r->output_patterns.size() == 1); 198 n->output_pattern = r->output_patterns[0]; 199 } 200 } 201 202 void FillDepNodeLoc(const Rule* r, DepNode* n) const { 203 n->loc = r->loc; 204 if (!r->cmds.empty() && r->cmd_lineno) 205 n->loc.lineno = r->cmd_lineno; 206 } 207 208 void FillDepNode(Symbol output, 209 const Rule* pattern_rule, 210 DepNode* n) const { 211 if (primary_rule) { 212 CHECK(!pattern_rule); 213 FillDepNodeFromRule(output, primary_rule, n); 214 FillDepNodeLoc(primary_rule, n); 215 n->cmds = primary_rule->cmds; 216 } else if (pattern_rule) { 217 FillDepNodeFromRule(output, pattern_rule, n); 218 FillDepNodeLoc(pattern_rule, n); 219 n->cmds = pattern_rule->cmds; 220 } 221 222 for (const Rule* r : rules) { 223 if (r == primary_rule) 224 continue; 225 FillDepNodeFromRule(output, r, n); 226 if (n->loc.filename == NULL) 227 n->loc = r->loc; 228 } 229 } 230 }; 231 232 } // namespace 233 234 DepNode::DepNode(Symbol o, bool p, bool r) 235 : output(o), 236 has_rule(false), 237 is_default_target(false), 238 is_phony(p), 239 is_restat(r), 240 rule_vars(NULL), 241 depfile_var(NULL), 242 ninja_pool_var(NULL), 243 output_pattern(Symbol::IsUninitialized()) { 244 g_dep_node_pool->push_back(this); 245 } 246 247 class DepBuilder { 248 public: 249 DepBuilder(Evaluator* ev, 250 const vector<const Rule*>& rules, 251 const unordered_map<Symbol, Vars*>& rule_vars) 252 : ev_(ev), 253 rule_vars_(rule_vars), 254 implicit_rules_(new RuleTrie()), 255 first_rule_(Symbol::IsUninitialized{}), 256 depfile_var_name_(Intern(".KATI_DEPFILE")), 257 ninja_pool_var_name_(Intern(".KATI_NINJA_POOL")) { 258 ScopedTimeReporter tr("make dep (populate)"); 259 PopulateRules(rules); 260 // TODO? 261 //LOG_STAT("%zu variables", ev->mutable_vars()->size()); 262 LOG_STAT("%zu explicit rules", rules_.size()); 263 LOG_STAT("%zu implicit rules", implicit_rules_->size()); 264 LOG_STAT("%zu suffix rules", suffix_rules_.size()); 265 266 HandleSpecialTargets(); 267 } 268 269 void HandleSpecialTargets() { 270 Loc loc; 271 vector<Symbol> targets; 272 273 if (GetRuleInputs(Intern(".PHONY"), &targets, &loc)) { 274 for (Symbol t : targets) 275 phony_.insert(t); 276 } 277 if (GetRuleInputs(Intern(".KATI_RESTAT"), &targets, &loc)) { 278 for (Symbol t : targets) 279 restat_.insert(t); 280 } 281 if (GetRuleInputs(Intern(".SUFFIXES"), &targets, &loc)) { 282 if (targets.empty()) { 283 suffix_rules_.clear(); 284 } else { 285 WARN_LOC(loc, "kati doesn't support .SUFFIXES with prerequisites"); 286 } 287 } 288 289 // Note we can safely ignore .DELETE_ON_ERROR for --ninja mode. 290 static const char* kUnsupportedBuiltinTargets[] = { 291 ".DEFAULT", 292 ".PRECIOUS", 293 ".INTERMEDIATE", 294 ".SECONDARY", 295 ".SECONDEXPANSION", 296 ".IGNORE", 297 ".LOW_RESOLUTION_TIME", 298 ".SILENT", 299 ".EXPORT_ALL_VARIABLES", 300 ".NOTPARALLEL", 301 ".ONESHELL", 302 NULL 303 }; 304 for (const char** p = kUnsupportedBuiltinTargets; *p; p++) { 305 if (GetRuleInputs(Intern(*p), &targets, &loc)) { 306 WARN_LOC(loc, "kati doesn't support %s", *p); 307 } 308 } 309 } 310 311 ~DepBuilder() { 312 } 313 314 void Build(vector<Symbol> targets, vector<DepNode*>* nodes) { 315 if (!first_rule_.IsValid()) { 316 ERROR("*** No targets."); 317 } 318 319 if (!g_flags.gen_all_targets && targets.empty()) { 320 targets.push_back(first_rule_); 321 } 322 if (g_flags.gen_all_targets) { 323 unordered_set<Symbol> non_root_targets; 324 for (const auto& p : rules_) { 325 for (const Rule* r : p.second.rules) { 326 for (Symbol t : r->inputs) 327 non_root_targets.insert(t); 328 for (Symbol t : r->order_only_inputs) 329 non_root_targets.insert(t); 330 } 331 } 332 333 for (const auto& p : rules_) { 334 Symbol t = p.first; 335 if (!non_root_targets.count(t)) { 336 targets.push_back(p.first); 337 } 338 } 339 } 340 341 // TODO: LogStats? 342 343 for (Symbol target : targets) { 344 cur_rule_vars_.reset(new Vars); 345 ev_->set_current_scope(cur_rule_vars_.get()); 346 DepNode* n = BuildPlan(target, Intern("")); 347 nodes->push_back(n); 348 ev_->set_current_scope(NULL); 349 cur_rule_vars_.reset(NULL); 350 } 351 } 352 353 private: 354 bool Exists(Symbol target) { 355 auto found = rules_.find(target); 356 if (found != rules_.end()) 357 return true; 358 if (phony_.count(target)) 359 return true; 360 return ::Exists(target.str()); 361 } 362 363 bool GetRuleInputs(Symbol s, vector<Symbol>* o, Loc* l) { 364 auto found = rules_.find(s); 365 if (found == rules_.end()) 366 return false; 367 368 o->clear(); 369 CHECK(!found->second.rules.empty()); 370 *l = found->second.rules.front()->loc; 371 for (const Rule* r : found->second.rules) { 372 for (Symbol i : r->inputs) 373 o->push_back(i); 374 } 375 return true; 376 } 377 378 void PopulateRules(const vector<const Rule*>& rules) { 379 for (const Rule* rule : rules) { 380 if (rule->outputs.empty()) { 381 PopulateImplicitRule(rule); 382 } else { 383 PopulateExplicitRule(rule); 384 } 385 } 386 for (auto& p : suffix_rules_) { 387 reverse(p.second.begin(), p.second.end()); 388 } 389 } 390 391 bool PopulateSuffixRule(const Rule* rule, Symbol output) { 392 if (!IsSuffixRule(output)) 393 return false; 394 395 const StringPiece rest = StringPiece(output.str()).substr(1); 396 size_t dot_index = rest.find('.'); 397 398 StringPiece input_suffix = rest.substr(0, dot_index); 399 StringPiece output_suffix = rest.substr(dot_index+1); 400 shared_ptr<Rule> r = make_shared<Rule>(*rule); 401 r->inputs.clear(); 402 r->inputs.push_back(Intern(input_suffix)); 403 r->is_suffix_rule = true; 404 suffix_rules_[output_suffix].push_back(r); 405 return true; 406 } 407 408 void PopulateExplicitRule(const Rule* rule) { 409 for (Symbol output : rule->outputs) { 410 if (!first_rule_.IsValid() && output.get(0) != '.') { 411 first_rule_ = output; 412 } 413 rules_[output].AddRule(output, rule); 414 PopulateSuffixRule(rule, output); 415 } 416 } 417 418 static bool IsIgnorableImplicitRule(const Rule* rule) { 419 // As kati doesn't have RCS/SCCS related default rules, we can 420 // safely ignore suppression for them. 421 if (rule->inputs.size() != 1) 422 return false; 423 if (!rule->order_only_inputs.empty()) 424 return false; 425 if (!rule->cmds.empty()) 426 return false; 427 const string& i = rule->inputs[0].str(); 428 return (i == "RCS/%,v" || i == "RCS/%" || i == "%,v" || 429 i == "s.%" || i == "SCCS/s.%"); 430 } 431 432 void PopulateImplicitRule(const Rule* rule) { 433 for (Symbol output_pattern : rule->output_patterns) { 434 if (output_pattern.str() != "%" || !IsIgnorableImplicitRule(rule)) 435 implicit_rules_->Add(output_pattern.str(), rule); 436 } 437 } 438 439 const RuleMerger* LookupRuleMerger(Symbol o) { 440 auto found = rules_.find(o); 441 if (found != rules_.end()) { 442 return &found->second; 443 } 444 return nullptr; 445 } 446 447 Vars* LookupRuleVars(Symbol o) { 448 auto found = rule_vars_.find(o); 449 if (found != rule_vars_.end()) 450 return found->second; 451 return nullptr; 452 } 453 454 bool CanPickImplicitRule(const Rule* rule, Symbol output, DepNode* n, 455 shared_ptr<Rule>* out_rule) { 456 Symbol matched(Symbol::IsUninitialized{}); 457 for (Symbol output_pattern : rule->output_patterns) { 458 Pattern pat(output_pattern.str()); 459 if (pat.Match(output.str())) { 460 bool ok = true; 461 for (Symbol input : rule->inputs) { 462 string buf; 463 pat.AppendSubst(output.str(), input.str(), &buf); 464 if (!Exists(Intern(buf))) { 465 ok = false; 466 break; 467 } 468 } 469 470 if (ok) { 471 matched = output_pattern; 472 break; 473 } 474 } 475 } 476 if (!matched.IsValid()) 477 return false; 478 479 *out_rule = make_shared<Rule>(*rule); 480 if ((*out_rule)->output_patterns.size() > 1) { 481 // We should mark all other output patterns as used. 482 Pattern pat(matched.str()); 483 for (Symbol output_pattern : rule->output_patterns) { 484 if (output_pattern == matched) 485 continue; 486 string buf; 487 pat.AppendSubst(output.str(), output_pattern.str(), &buf); 488 done_[Intern(buf)] = n; 489 } 490 (*out_rule)->output_patterns.clear(); 491 (*out_rule)->output_patterns.push_back(matched); 492 } 493 494 return true; 495 } 496 497 Vars* MergeImplicitRuleVars(Symbol output, Vars* vars) { 498 auto found = rule_vars_.find(output); 499 if (found == rule_vars_.end()) 500 return vars; 501 if (vars == NULL) 502 return found->second; 503 // TODO: leak. 504 Vars* r = new Vars(*found->second); 505 for (auto p : *vars) { 506 (*r)[p.first] = p.second; 507 } 508 return r; 509 } 510 511 bool PickRule(Symbol output, 512 DepNode* n, 513 const RuleMerger** out_rule_merger, 514 shared_ptr<Rule>* pattern_rule, 515 Vars** out_var) { 516 const RuleMerger* rule_merger = LookupRuleMerger(output); 517 Vars* vars = LookupRuleVars(output); 518 *out_rule_merger = rule_merger; 519 *out_var = vars; 520 if (rule_merger && rule_merger->primary_rule) 521 return true; 522 523 vector<const Rule*> irules; 524 implicit_rules_->Get(output.str(), &irules); 525 for (auto iter = irules.rbegin(); iter != irules.rend(); ++iter) { 526 if (!CanPickImplicitRule(*iter, output, n, pattern_rule)) 527 continue; 528 if (rule_merger) { 529 return true; 530 } 531 CHECK((*pattern_rule)->output_patterns.size() == 1); 532 vars = MergeImplicitRuleVars((*pattern_rule)->output_patterns[0], vars); 533 *out_var = vars; 534 return true; 535 } 536 537 StringPiece output_suffix = GetExt(output.str()); 538 if (output_suffix.get(0) != '.') 539 return rule_merger; 540 output_suffix = output_suffix.substr(1); 541 542 SuffixRuleMap::const_iterator found = suffix_rules_.find(output_suffix); 543 if (found == suffix_rules_.end()) 544 return rule_merger; 545 546 for (const shared_ptr<Rule> &irule : found->second) { 547 CHECK(irule->inputs.size() == 1); 548 Symbol input = ReplaceSuffix(output, irule->inputs[0]); 549 if (!Exists(input)) 550 continue; 551 552 *pattern_rule = irule; 553 if (rule_merger) 554 return true; 555 if (vars) { 556 CHECK(irule->outputs.size() == 1); 557 vars = MergeImplicitRuleVars(irule->outputs[0], vars); 558 *out_var = vars; 559 } 560 return true; 561 } 562 563 return rule_merger; 564 } 565 566 DepNode* BuildPlan(Symbol output, Symbol needed_by UNUSED) { 567 LOG("BuildPlan: %s for %s", 568 output.c_str(), 569 needed_by.c_str()); 570 571 auto found = done_.find(output); 572 if (found != done_.end()) { 573 return found->second; 574 } 575 576 DepNode* n = new DepNode(output, 577 phony_.count(output), 578 restat_.count(output)); 579 done_[output] = n; 580 581 const RuleMerger* rule_merger = nullptr; 582 shared_ptr<Rule> pattern_rule; 583 Vars* vars; 584 if (!PickRule(output, n, &rule_merger, &pattern_rule, &vars)) { 585 return n; 586 } 587 if (rule_merger) 588 rule_merger->FillDepNode(output, pattern_rule.get(), n); 589 else 590 RuleMerger().FillDepNode(output, pattern_rule.get(), n); 591 592 vector<unique_ptr<ScopedVar>> sv; 593 if (vars) { 594 for (const auto& p : *vars) { 595 Symbol name = p.first; 596 RuleVar* var = reinterpret_cast<RuleVar*>(p.second); 597 CHECK(var); 598 Var* new_var = var->v(); 599 if (var->op() == AssignOp::PLUS_EQ) { 600 Var* old_var = ev_->LookupVar(name); 601 if (old_var->IsDefined()) { 602 // TODO: This would be incorrect and has a leak. 603 shared_ptr<string> s = make_shared<string>(); 604 old_var->Eval(ev_, s.get()); 605 if (!s->empty()) 606 *s += ' '; 607 new_var->Eval(ev_, s.get()); 608 new_var = new SimpleVar(*s, old_var->Origin()); 609 } 610 } else if (var->op() == AssignOp::QUESTION_EQ) { 611 Var* old_var = ev_->LookupVar(name); 612 if (old_var->IsDefined()) { 613 continue; 614 } 615 } 616 617 if (name == depfile_var_name_) { 618 n->depfile_var = new_var; 619 } else if (name == ninja_pool_var_name_) { 620 n->ninja_pool_var = new_var; 621 } else { 622 sv.emplace_back(new ScopedVar(cur_rule_vars_.get(), name, new_var)); 623 } 624 } 625 } 626 627 for (Symbol input : n->actual_inputs) { 628 DepNode* c = BuildPlan(input, output); 629 n->deps.push_back(c); 630 } 631 632 for (Symbol input : n->actual_order_only_inputs) { 633 DepNode* c = BuildPlan(input, output); 634 n->order_onlys.push_back(c); 635 } 636 637 n->has_rule = true; 638 n->is_default_target = first_rule_ == output; 639 if (cur_rule_vars_->empty()) { 640 n->rule_vars = NULL; 641 } else { 642 n->rule_vars = new Vars; 643 for (auto p : *cur_rule_vars_) { 644 n->rule_vars->insert(p); 645 } 646 } 647 648 return n; 649 } 650 651 Evaluator* ev_; 652 map<Symbol, RuleMerger> rules_; 653 const unordered_map<Symbol, Vars*>& rule_vars_; 654 unique_ptr<Vars> cur_rule_vars_; 655 656 unique_ptr<RuleTrie> implicit_rules_; 657 typedef unordered_map<StringPiece, vector<shared_ptr<Rule>>> SuffixRuleMap; 658 SuffixRuleMap suffix_rules_; 659 660 Symbol first_rule_; 661 unordered_map<Symbol, DepNode*> done_; 662 unordered_set<Symbol> phony_; 663 unordered_set<Symbol> restat_; 664 Symbol depfile_var_name_; 665 Symbol ninja_pool_var_name_; 666 }; 667 668 void MakeDep(Evaluator* ev, 669 const vector<const Rule*>& rules, 670 const unordered_map<Symbol, Vars*>& rule_vars, 671 const vector<Symbol>& targets, 672 vector<DepNode*>* nodes) { 673 DepBuilder db(ev, rules, rule_vars); 674 ScopedTimeReporter tr("make dep (build)"); 675 db.Build(targets, nodes); 676 } 677 678 void InitDepNodePool() { 679 g_dep_node_pool = new vector<DepNode*>; 680 } 681 682 void QuitDepNodePool() { 683 for (DepNode* n : *g_dep_node_pool) 684 delete n; 685 delete g_dep_node_pool; 686 } 687