From eb7167d456b8ef2dad3846ca2ba6438b060518c9 Mon Sep 17 00:00:00 2001
From: Nico Weber <nicolasweber@gmx.de>
Date: Wed, 18 Mar 2015 16:54:16 -0400
Subject: Don't crash on cyclic references between rule bindings.

Fixes #902.

This dynamically detects cycles.  I like this approach less than
detecting them statically when parsing rules [1], but it has the
advantage that it doesn't break existing ninja manifest files.

It has the disadvantage that it slows down manifest_parser_perftest by
3.9%.

1: https://github.com/martine/ninja/commit/cc6f54d6d436047
---
 src/graph.cc | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/src/graph.cc b/src/graph.cc
index b19dc85..41055ec 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -226,6 +226,7 @@ struct EdgeEnv : public Env {
                       vector<Node*>::iterator end,
                       char sep);
 
+  vector<string> lookups_;
   Edge* edge_;
   EscapeKind escape_in_out_;
 };
@@ -243,8 +244,19 @@ string EdgeEnv::LookupVariable(const string& var) {
                         ' ');
   }
 
+  vector<string>::const_iterator it;
+  if ((it = find(lookups_.begin(), lookups_.end(), var)) != lookups_.end()) {
+    string cycle;
+    for (; it != lookups_.end(); ++it)
+      cycle.append(*it + " -> ");
+    cycle.append(var);
+    Fatal(("cycle in rule variables: " + cycle).c_str());
+  }
+
   // See notes on BindingEnv::LookupWithFallback.
   const EvalString* eval = edge_->rule_->GetBinding(var);
+  if (eval)
+    lookups_.push_back(var);
   return edge_->env_->LookupWithFallback(var, eval, this);
 }
 
-- 
cgit v0.12


From 4d44291739222e453421a237ff77d9e5daaa3dd4 Mon Sep 17 00:00:00 2001
From: Nico Weber <nicolasweber@gmx.de>
Date: Fri, 20 Mar 2015 21:11:31 -0700
Subject: Recover slowdown for cyclic rule bindings fix.

---
 src/graph.cc | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)

diff --git a/src/graph.cc b/src/graph.cc
index 41055ec..d99c8bd 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -217,7 +217,7 @@ struct EdgeEnv : public Env {
   enum EscapeKind { kShellEscape, kDoNotEscape };
 
   EdgeEnv(Edge* edge, EscapeKind escape)
-      : edge_(edge), escape_in_out_(escape) {}
+      : edge_(edge), escape_in_out_(escape), recursive_(false) {}
   virtual string LookupVariable(const string& var);
 
   /// Given a span of Nodes, construct a list of paths suitable for a command
@@ -226,9 +226,11 @@ struct EdgeEnv : public Env {
                       vector<Node*>::iterator end,
                       char sep);
 
+ private:
   vector<string> lookups_;
   Edge* edge_;
   EscapeKind escape_in_out_;
+  bool recursive_;
 };
 
 string EdgeEnv::LookupVariable(const string& var) {
@@ -244,19 +246,25 @@ string EdgeEnv::LookupVariable(const string& var) {
                         ' ');
   }
 
-  vector<string>::const_iterator it;
-  if ((it = find(lookups_.begin(), lookups_.end(), var)) != lookups_.end()) {
-    string cycle;
-    for (; it != lookups_.end(); ++it)
-      cycle.append(*it + " -> ");
-    cycle.append(var);
-    Fatal(("cycle in rule variables: " + cycle).c_str());
+  if (recursive_) {
+    vector<string>::const_iterator it;
+    if ((it = find(lookups_.begin(), lookups_.end(), var)) != lookups_.end()) {
+      string cycle;
+      for (; it != lookups_.end(); ++it)
+        cycle.append(*it + " -> ");
+      cycle.append(var);
+      Fatal(("cycle in rule variables: " + cycle).c_str());
+    }
   }
 
   // See notes on BindingEnv::LookupWithFallback.
   const EvalString* eval = edge_->rule_->GetBinding(var);
-  if (eval)
+  if (recursive_ && eval)
     lookups_.push_back(var);
+
+  // In practice, variables defined on rules never use another rule variable.
+  // For performance, only start checking for cycles after the first lookup.
+  recursive_ = true;
   return edge_->env_->LookupWithFallback(var, eval, this);
 }
 
-- 
cgit v0.12


From 9aab00003c62f8d6b8142e6ecfe8f0aeefc81f74 Mon Sep 17 00:00:00 2001
From: Nico Weber <nicolasweber@gmx.de>
Date: Fri, 20 Mar 2015 21:21:14 -0700
Subject: Preallocate edge node vectors. ~1% faster.

---
 src/manifest_parser.cc | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc
index 4e639d1..b747ad4 100644
--- a/src/manifest_parser.cc
+++ b/src/manifest_parser.cc
@@ -321,6 +321,7 @@ bool ManifestParser::ParseEdge(string* err) {
     edge->pool_ = pool;
   }
 
+  edge->outputs_.reserve(outs.size());
   for (vector<EvalString>::iterator i = outs.begin(); i != outs.end(); ++i) {
     string path = i->Evaluate(env);
     string path_err;
@@ -337,6 +338,7 @@ bool ManifestParser::ParseEdge(string* err) {
     return true;
   }
 
+  edge->inputs_.reserve(ins.size());
   for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) {
     string path = i->Evaluate(env);
     string path_err;
-- 
cgit v0.12