about summary refs log tree commit diff
diff options
context:
space:
mode:
authorEelco Dolstra <e.dolstra@tudelft.nl>2005-11-04T15·17+0000
committerEelco Dolstra <e.dolstra@tudelft.nl>2005-11-04T15·17+0000
commit5bf939885a8bfca9b66a2440bf52330c5fde6477 (patch)
treece78c95b1bd52a5d9fd9cf6eece4733480c5ad94
parent1f285cf5563047f236213c8eadc91324b69af42b (diff)
* Memoise checkVarDefs since internally produced terms (i.e., not the
  result of parsing) can have very heavy sharing, causing exponential
  complexity if we naively recurse into them.  ATerms are graphs, not
  trees!

-rw-r--r--src/libexpr/nixexpr.cc33
1 files changed, 24 insertions, 9 deletions
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 289e923c3311..6fb72687d160 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -301,8 +301,16 @@ Expr substitute(const ATermMap & subs, Expr e)
 }
 
 
-void checkVarDefs(const ATermMap & defs, Expr e)
+/* We use memoisation to prevent exponential complexity on heavily
+   shared ATerms (remember, an ATerm is a graph, not a tree!).  Note
+   that using an STL set is fine here wrt to ATerm garbage collection
+   since all the ATerms in the set are already reachable from
+   somewhere else. */
+static void checkVarDefs2(set<Expr> & done, const ATermMap & defs, Expr e)
 {
+    if (done.find(e) != done.end()) return;
+    done.insert(e);
+    
     ATerm name, pos, value;
     ATermList formals;
     ATerm with, body;
@@ -320,22 +328,22 @@ void checkVarDefs(const ATermMap & defs, Expr e)
             Expr deflt;
             if (!matchNoDefFormal(*i, name))
                 if (matchDefFormal(*i, name, deflt))
-                    checkVarDefs(defs, deflt);
+                    checkVarDefs2(done, defs, deflt);
                 else
                     abort();
             defs2.set(name, (ATerm) ATempty);
         }
-        checkVarDefs(defs2, body);
+        checkVarDefs2(done, defs2, body);
     }
         
     else if (matchFunction1(e, name, body, pos)) {
         ATermMap defs2(defs);
         defs2.set(name, (ATerm) ATempty);
-        checkVarDefs(defs2, body);
+        checkVarDefs2(done, defs2, body);
     }
         
     else if (matchRec(e, rbnds, nrbnds)) {
-        checkVarDefs(defs, (ATerm) nrbnds);
+        checkVarDefs2(done, defs, (ATerm) nrbnds);
         ATermMap defs2(defs);
         for (ATermIterator i(rbnds); i; ++i) {
             if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
@@ -345,25 +353,32 @@ void checkVarDefs(const ATermMap & defs, Expr e)
             if (!matchBind(*i, name, value, pos)) abort(); /* can't happen */
             defs2.set(name, (ATerm) ATempty);
         }
-        checkVarDefs(defs2, (ATerm) rbnds);
+        checkVarDefs2(done, defs2, (ATerm) rbnds);
     }
 
     else if (matchWith(e, with, body, pos)) {
         /* We can't check the body without evaluating the definitions
            (which is an arbitrary expression), so we don't do that
            here but only when actually evaluating the `with'. */
-        checkVarDefs(defs, with);
+        checkVarDefs2(done, defs, with);
     }
     
     else if (ATgetType(e) == AT_APPL) {
         int arity = ATgetArity(ATgetAFun(e));
         for (int i = 0; i < arity; ++i)
-            checkVarDefs(defs, ATgetArgument(e, i));
+            checkVarDefs2(done, defs, ATgetArgument(e, i));
     }
 
     else if (ATgetType(e) == AT_LIST)
         for (ATermIterator i((ATermList) e); i; ++i)
-            checkVarDefs(defs, *i);
+            checkVarDefs2(done, defs, *i);
+}
+
+
+void checkVarDefs(const ATermMap & defs, Expr e)
+{
+    set<Expr> done;
+    checkVarDefs2(done, defs, e);
 }