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: [PATCH] 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);
 }
 
-- 
2.7.4