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