about summary refs log tree commit diff
diff options
context:
space:
mode:
authorEelco Dolstra <e.dolstra@tudelft.nl>2003-08-25T14·56+0000
committerEelco Dolstra <e.dolstra@tudelft.nl>2003-08-25T14·56+0000
commit31be53cd0a50ef9e3ddf64f79222e8e8dd1d05aa (patch)
treefc654cfd7358e284f8c07b078d3ef903408e41ba
parent920193beb1a7b8894d100c63adadf00ad855dd64 (diff)
* Fix the atrocious (exponential? factorial?) time complexity in
  `nix --query --requisites'.

-rw-r--r--src/normalise.cc13
1 files changed, 9 insertions, 4 deletions
diff --git a/src/normalise.cc b/src/normalise.cc
index 059b3c83a9ab..c7be5320611e 100644
--- a/src/normalise.cc
+++ b/src/normalise.cc
@@ -321,8 +321,12 @@ Strings fstatePaths(const FSId & id)
 
 
 static void fstateRequisitesSet(const FSId & id, 
-    bool includeExprs, bool includeSuccessors, StringSet & paths)
+    bool includeExprs, bool includeSuccessors, StringSet & paths,
+    FSIdSet & doneSet)
 {
+    if (doneSet.find(id) != doneSet.end()) return;
+    doneSet.insert(id);
+
     FState fs = parseFState(termFromId(id));
 
     if (fs.type == FState::fsSlice)
@@ -334,7 +338,7 @@ static void fstateRequisitesSet(const FSId & id,
         for (FSIdSet::iterator i = fs.derive.inputs.begin();
              i != fs.derive.inputs.end(); i++)
             fstateRequisitesSet(*i,
-                includeExprs, includeSuccessors, paths);
+                includeExprs, includeSuccessors, paths, doneSet);
 
     else abort();
 
@@ -345,7 +349,7 @@ static void fstateRequisitesSet(const FSId & id,
     if (includeSuccessors &&
         nixDB.queryString(noTxn, dbSuccessors, id, idSucc))
         fstateRequisitesSet(parseHash(idSucc), 
-            includeExprs, includeSuccessors, paths);
+            includeExprs, includeSuccessors, paths, doneSet);
 }
 
 
@@ -353,7 +357,8 @@ Strings fstateRequisites(const FSId & id,
     bool includeExprs, bool includeSuccessors)
 {
     StringSet paths;
-    fstateRequisitesSet(id, includeExprs, includeSuccessors, paths);
+    FSIdSet doneSet;
+    fstateRequisitesSet(id, includeExprs, includeSuccessors, paths, doneSet);
     return Strings(paths.begin(), paths.end());
 }