[C++] Refactor DepBuilder
After this patch, multiple Rule objects won't be merged to
a single rule. Instead, DepBuilder holds the list of Rules
and directly write merged results to DepNode.
diff --git a/dep.cc b/dep.cc
index e30e6f0..57b322c 100644
--- a/dep.cc
+++ b/dep.cc
@@ -45,6 +45,31 @@
return Intern(r);
}
+void ApplyOutputPattern(const Rule& r,
+ Symbol output,
+ const vector<Symbol>& inputs,
+ vector<Symbol>* out_inputs) {
+ if (inputs.empty())
+ return;
+ if (r.is_suffix_rule) {
+ for (Symbol input : inputs) {
+ out_inputs->push_back(ReplaceSuffix(output, input));
+ }
+ return;
+ }
+ if (r.output_patterns.empty()) {
+ copy(inputs.begin(), inputs.end(), back_inserter(*out_inputs));
+ return;
+ }
+ CHECK(r.output_patterns.size() == 1);
+ Pattern pat(r.output_patterns[0].str());
+ for (Symbol input : inputs) {
+ string buf;
+ pat.AppendSubst(output.str(), input.str(), &buf);
+ out_inputs->push_back(Intern(buf));
+ }
+}
+
class RuleTrie {
struct Entry {
Entry(const Rule* r, StringPiece s)
@@ -101,6 +126,98 @@
unordered_map<char, RuleTrie*> children_;
};
+
+bool IsSuffixRule(Symbol output) {
+ if (output.empty() || output.str()[0] != '.')
+ return false;
+ const StringPiece rest = StringPiece(output.str()).substr(1);
+ size_t dot_index = rest.find('.');
+ // If there is only a single dot or the third dot, this is not a
+ // suffix rule.
+ if (dot_index == string::npos ||
+ rest.substr(dot_index+1).find('.') != string::npos) {
+ return false;
+ }
+ return true;
+}
+
+struct RuleMerger {
+ vector<const Rule*> rules;
+ const Rule* primary_rule;
+ bool is_double_colon;
+
+ RuleMerger()
+ : primary_rule(nullptr),
+ is_double_colon(false) {
+ }
+
+ void AddRule(Symbol output, const Rule* r) {
+ if (rules.empty()) {
+ is_double_colon = r->is_double_colon;
+ } else if (is_double_colon != r->is_double_colon) {
+ ERROR("%s:%d: *** target file `%s' has both : and :: entries.",
+ LOCF(r->loc), output.c_str());
+ }
+
+ if (primary_rule && !r->cmds.empty() &&
+ !IsSuffixRule(output) && !r->is_double_colon) {
+ WARN("%s:%d: warning: overriding commands for target `%s'",
+ LOCF(r->cmd_loc()), output.c_str());
+ WARN("%s:%d: warning: ignoring old commands for target `%s'",
+ LOCF(primary_rule->cmd_loc()), output.c_str());
+ primary_rule = r;
+ }
+ if (!primary_rule && !r->cmds.empty()) {
+ primary_rule = r;
+ }
+
+ rules.push_back(r);
+ }
+
+ void FillDepNodeFromRule(Symbol output,
+ const Rule* r,
+ DepNode* n) const {
+ if (is_double_colon)
+ copy(r->cmds.begin(), r->cmds.end(), back_inserter(n->cmds));
+
+ ApplyOutputPattern(*r, output, r->inputs, &n->actual_inputs);
+ ApplyOutputPattern(*r, output, r->order_only_inputs,
+ &n->actual_order_only_inputs);
+
+ if (r->output_patterns.size() >= 1) {
+ CHECK(r->output_patterns.size() == 1);
+ n->output_pattern = r->output_patterns[0];
+ }
+ }
+
+ void FillDepNodeLoc(const Rule* r, DepNode* n) const {
+ n->loc = r->loc;
+ if (!r->cmds.empty() && r->cmd_lineno)
+ n->loc.lineno = r->cmd_lineno;
+ }
+
+ void FillDepNode(Symbol output,
+ const Rule* pattern_rule,
+ DepNode* n) const {
+ if (primary_rule) {
+ CHECK(!pattern_rule);
+ FillDepNodeFromRule(output, primary_rule, n);
+ FillDepNodeLoc(primary_rule, n);
+ n->cmds = primary_rule->cmds;
+ } else if (pattern_rule) {
+ FillDepNodeFromRule(output, pattern_rule, n);
+ FillDepNodeLoc(pattern_rule, n);
+ n->cmds = pattern_rule->cmds;
+ }
+
+ for (const Rule* r : rules) {
+ if (r == primary_rule)
+ continue;
+ FillDepNodeFromRule(output, r, n);
+ }
+ }
+};
+
} // namespace
DepNode::DepNode(Symbol o, bool p, bool r)
@@ -193,10 +310,12 @@
if (g_flags.gen_all_targets) {
unordered_set<Symbol> non_root_targets;
for (const auto& p : rules_) {
- for (Symbol t : p.second->inputs)
- non_root_targets.insert(t);
- for (Symbol t : p.second->order_only_inputs)
- non_root_targets.insert(t);
+ for (const Rule* r : p.second.rules) {
+ for (Symbol t : r->inputs)
+ non_root_targets.insert(t);
+ for (Symbol t : r->order_only_inputs)
+ non_root_targets.insert(t);
+ }
}
for (const auto& p : rules_) {
@@ -235,9 +354,11 @@
return false;
o->clear();
- *l = found->second->loc;
- for (Symbol i : found->second->inputs) {
- o->push_back(i);
+ CHECK(!found->second.rules.empty());
+ *l = found->second.rules.front()->loc;
+ for (const Rule* r : found->second.rules) {
+ for (Symbol i : r->inputs)
+ o->push_back(i);
}
return true;
}
@@ -256,17 +377,11 @@
}
bool PopulateSuffixRule(const Rule* rule, Symbol output) {
- if (output.empty() || output.str()[0] != '.')
+ if (!IsSuffixRule(output))
return false;
const StringPiece rest = StringPiece(output.str()).substr(1);
size_t dot_index = rest.find('.');
- // If there is only a single dot or the third dot, this is not a
- // suffix rule.
- if (dot_index == string::npos ||
- rest.substr(dot_index+1).find('.') != string::npos) {
- return false;
- }
StringPiece input_suffix = rest.substr(0, dot_index);
StringPiece output_suffix = rest.substr(dot_index+1);
@@ -278,98 +393,13 @@
return true;
}
- void ApplyOutputPattern(const Rule& r,
- Symbol output,
- const vector<Symbol>& inputs,
- vector<Symbol>* out_inputs) {
- if (inputs.empty())
- return;
- if (r.is_suffix_rule) {
- for (Symbol input : inputs) {
- out_inputs->push_back(ReplaceSuffix(output, input));
+ void PopulateExplicitRule(const Rule* rule) {
+ for (Symbol output : rule->outputs) {
+ if (!first_rule_.IsValid() && output.get(0) != '.') {
+ first_rule_ = output;
}
- return;
- }
- if (r.output_patterns.empty()) {
- copy(inputs.begin(), inputs.end(), back_inserter(*out_inputs));
- return;
- }
- CHECK(r.output_patterns.size() == 1);
- Pattern pat(r.output_patterns[0].str());
- for (Symbol input : inputs) {
- string buf;
- pat.AppendSubst(output.str(), input.str(), &buf);
- out_inputs->push_back(Intern(buf));
- }
- }
-
- shared_ptr<Rule> MergeRules(const Rule& old_rule,
- const Rule& rule,
- Symbol output,
- bool is_suffix_rule) {
- COLLECT_STATS("make dep (merge rule)");
- if (old_rule.is_double_colon != rule.is_double_colon) {
- ERROR("%s:%d: *** target file `%s' has both : and :: entries.",
- LOCF(rule.loc), output.str().c_str());
- }
- if (!old_rule.cmds.empty() && !rule.cmds.empty() &&
- !is_suffix_rule && !rule.is_double_colon) {
- WARN("%s:%d: warning: overriding commands for target `%s'",
- LOCF(rule.cmd_loc()), output.str().c_str());
- WARN("%s:%d: warning: ignoring old commands for target `%s'",
- LOCF(old_rule.cmd_loc()), output.str().c_str());
- }
-
- shared_ptr<Rule> r = make_shared<Rule>(rule);
- if (rule.is_double_colon) {
- r->cmds.clear();
- for (Value* c : old_rule.cmds)
- r->cmds.push_back(c);
- for (Value* c : rule.cmds)
- r->cmds.push_back(c);
- if (!rule.output_patterns.empty() && !old_rule.output_patterns.empty() &&
- rule.output_patterns != old_rule.output_patterns) {
- ERROR("%s:%d: TODO: merging two double colon rules with output "
- "patterns is not supported", LOCF(rule.loc));
- }
- } else if (!old_rule.cmds.empty() && rule.cmds.empty()) {
- r->cmds = old_rule.cmds;
- }
-
- // If the latter rule has a command (regardless of the commands in
- // |old_rule|), inputs in the latter rule has a priority.
- if (rule.cmds.empty()) {
- r->inputs = old_rule.inputs;
- ApplyOutputPattern(rule, output, rule.inputs, &r->inputs);
- r->order_only_inputs = old_rule.order_only_inputs;
- ApplyOutputPattern(rule, output, rule.order_only_inputs,
- &r->order_only_inputs);
- r->output_patterns = old_rule.output_patterns;
- } else {
- ApplyOutputPattern(old_rule, output, old_rule.inputs, &r->inputs);
- ApplyOutputPattern(old_rule, output, old_rule.order_only_inputs,
- &r->order_only_inputs);
- }
- return r;
- }
-
- void PopulateExplicitRule(const Rule* orig_rule) {
- for (Symbol output : orig_rule->outputs) {
- const bool is_suffix_rule = PopulateSuffixRule(orig_rule, output);
-
- shared_ptr<Rule> rule = make_shared<Rule>(*orig_rule);
- rule->outputs.clear();
- rule->outputs.push_back(output);
-
- auto p = rules_.emplace(output, rule);
- if (p.second) {
- if (!first_rule_.IsValid() && output.get(0) != '.') {
- first_rule_ = output;
- }
- } else {
- p.first->second =
- MergeRules(*p.first->second, *rule, output, is_suffix_rule);
- }
+ rules_[output].AddRule(output, rule);
+ PopulateSuffixRule(rule, output);
}
}
@@ -394,18 +424,19 @@
}
}
- shared_ptr<Rule> LookupRule(Symbol o) {
+ const RuleMerger* LookupRuleMerger(Symbol o) {
auto found = rules_.find(o);
- if (found != rules_.end())
- return found->second;
- return NULL;
+ if (found != rules_.end()) {
+ return &found->second;
+ }
+ return nullptr;
}
Vars* LookupRuleVars(Symbol o) {
auto found = rule_vars_.find(o);
if (found != rule_vars_.end())
return found->second;
- return NULL;
+ return nullptr;
}
bool CanPickImplicitRule(const Rule* rule, Symbol output, DepNode* n,
@@ -465,53 +496,40 @@
return r;
}
- bool PickRule(Symbol output, DepNode* n,
- shared_ptr<Rule>* out_rule, Vars** out_var) {
- COLLECT_STATS("make dep (pick rule)");
- shared_ptr<Rule> rule = LookupRule(output);
+ bool PickRule(Symbol output,
+ DepNode* n,
+ const RuleMerger** out_rule_merger,
+ shared_ptr<Rule>* pattern_rule,
+ Vars** out_var) {
+ const RuleMerger* rule_merger = LookupRuleMerger(output);
Vars* vars = LookupRuleVars(output);
- *out_rule = rule;
+ *out_rule_merger = rule_merger;
*out_var = vars;
- if (rule) {
- if (!rule->cmds.empty()) {
- return true;
- }
- }
+ if (rule_merger && rule_merger->primary_rule)
+ return true;
vector<const Rule*> irules;
implicit_rules_->Get(output.str(), &irules);
for (auto iter = irules.rbegin(); iter != irules.rend(); ++iter) {
- shared_ptr<Rule> irule;
- if (!CanPickImplicitRule(*iter, output, n, &irule))
+ if (!CanPickImplicitRule(*iter, output, n, pattern_rule))
continue;
- if (rule) {
- shared_ptr<Rule> r = make_shared<Rule>(*rule);
- r->output_patterns = irule->output_patterns;
- r->inputs.clear();
- r->inputs = irule->inputs;
- copy(rule->inputs.begin(), rule->inputs.end(),
- back_inserter(r->inputs));
- r->cmds = irule->cmds;
- r->loc = irule->loc;
- r->cmd_lineno = irule->cmd_lineno;
- *out_rule = r;
+ if (rule_merger) {
return true;
}
- CHECK(irule->output_patterns.size() == 1);
- vars = MergeImplicitRuleVars(irule->output_patterns[0], vars);
+ CHECK((*pattern_rule)->output_patterns.size() == 1);
+ vars = MergeImplicitRuleVars((*pattern_rule)->output_patterns[0], vars);
*out_var = vars;
- *out_rule = make_shared<Rule>(*irule);
return true;
}
StringPiece output_suffix = GetExt(output.str());
if (output_suffix.get(0) != '.')
- return rule.get();
+ return rule_merger;
output_suffix = output_suffix.substr(1);
SuffixRuleMap::const_iterator found = suffix_rules_.find(output_suffix);
if (found == suffix_rules_.end())
- return rule.get();
+ return rule_merger;
for (shared_ptr<Rule> irule : found->second) {
CHECK(irule->inputs.size() == 1);
@@ -519,25 +537,18 @@
if (!Exists(input))
continue;
- if (rule) {
- shared_ptr<Rule> r = make_shared<Rule>(*rule);
- r->inputs.insert(r->inputs.begin(), input);
- r->cmds = irule->cmds;
- r->loc = irule->loc;
- r->cmd_lineno = irule->cmd_lineno;
- *out_rule = r;
+ *pattern_rule = irule;
+ if (rule_merger)
return true;
- }
if (vars) {
CHECK(irule->outputs.size() == 1);
vars = MergeImplicitRuleVars(irule->outputs[0], vars);
*out_var = vars;
}
- *out_rule = irule;
return true;
}
- return rule.get();
+ return rule_merger;
}
DepNode* BuildPlan(Symbol output, Symbol needed_by UNUSED) {
@@ -555,20 +566,19 @@
restat_.count(output));
done_[output] = n;
- shared_ptr<Rule> rule;
+ const RuleMerger* rule_merger = nullptr;
+ shared_ptr<Rule> pattern_rule;
Vars* vars;
- if (!PickRule(output, n, &rule, &vars)) {
+ if (!PickRule(output, n, &rule_merger, &pattern_rule, &vars)) {
return n;
}
-
- if (rule->output_patterns.size() >= 1) {
- CHECK(rule->output_patterns.size() == 1);
- n->output_pattern = rule->output_patterns[0];
- }
+ if (rule_merger)
+ rule_merger->FillDepNode(output, pattern_rule.get(), n);
+ else
+ RuleMerger().FillDepNode(output, pattern_rule.get(), n);
vector<unique_ptr<ScopedVar>> sv;
if (vars) {
- COLLECT_STATS("make dep (create scope)");
for (const auto& p : *vars) {
Symbol name = p.first;
RuleVar* var = reinterpret_cast<RuleVar*>(p.second);
@@ -600,22 +610,17 @@
}
}
- ApplyOutputPattern(*rule, output, rule->inputs, &n->actual_inputs);
for (Symbol input : n->actual_inputs) {
DepNode* c = BuildPlan(input, output);
n->deps.push_back(c);
}
- vector<Symbol> order_only_inputs;
- ApplyOutputPattern(*rule, output, rule->order_only_inputs,
- &order_only_inputs);
- for (Symbol input : order_only_inputs) {
+ for (Symbol input : n->actual_order_only_inputs) {
DepNode* c = BuildPlan(input, output);
n->order_onlys.push_back(c);
}
n->has_rule = true;
- n->cmds = rule->cmds;
n->is_default_target = first_rule_ == output;
if (cur_rule_vars_->empty()) {
n->rule_vars = NULL;
@@ -625,15 +630,12 @@
n->rule_vars->insert(p);
}
}
- n->loc = rule->loc;
- if (!rule->cmds.empty() && rule->cmd_lineno)
- n->loc.lineno = rule->cmd_lineno;
return n;
}
Evaluator* ev_;
- map<Symbol, shared_ptr<Rule>> rules_;
+ map<Symbol, RuleMerger> rules_;
const unordered_map<Symbol, Vars*>& rule_vars_;
unique_ptr<Vars> cur_rule_vars_;