[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.

2 files changed, 169 insertions, 166 deletions

diff --git a/dep.cc b/dep.cc
index e30e6f0..57b322c 100644
--- a/dep.cc
+++ b/dep.cc
@@ -45,6 +45,31 @@ static Symbol ReplaceSuffix(Symbol s, Symbol newsuf) {
   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 @@ class RuleTrie {
   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 @@ class DepBuilder {
     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 @@ class DepBuilder {
       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 @@ class DepBuilder {
   }
 
   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 @@ class DepBuilder {
     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));
-      }
-      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);
+  void PopulateExplicitRule(const Rule* rule) {
+    for (Symbol output : rule->outputs) {
+      if (!first_rule_.IsValid() && output.get(0) != '.') {
+        first_rule_ = output;
       }
+      rules_[output].AddRule(output, rule);
+      PopulateSuffixRule(rule, output);
     }
   }
 
@@ -394,18 +424,19 @@ class DepBuilder {
     }
   }
 
-  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 @@ class DepBuilder {
     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 @@ class DepBuilder {
       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 @@ class DepBuilder {
                              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 @@ class DepBuilder {
       }
     }
 
-    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 @@ class DepBuilder {
         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_;
 
diff --git a/dep.h b/dep.h
index 05d10d0..4302997 100644
--- a/dep.h
+++ b/dep.h
@@ -42,6 +42,7 @@ struct DepNode {
   bool is_phony;
   bool is_restat;
   vector<Symbol> actual_inputs;
+  vector<Symbol> actual_order_only_inputs;
   Vars* rule_vars;
   Var* depfile_var;
   Symbol output_pattern;