* Use maps and sets in the FState data type. This ensures normalisation of

  slices and derivations w.r.t. order of paths, slice elements, etc.

5 files changed, 86 insertions, 105 deletions

diff --git a/src/fix.cc b/src/fix.cc
index 83e25d142a19..38c53c6d79a7 100644
--- a/src/fix.cc
+++ b/src/fix.cc
@@ -137,14 +137,16 @@ static Strings fstatePathsCached(EvalState & state, const FSId & id)
 static Hash hashPackage(EvalState & state, FState fs)
 {
     if (fs.type == FState::fsDerive) {
-        for (FSIds::iterator i = fs.derive.inputs.begin();
+	FSIdSet inputs2;
+        for (FSIdSet::iterator i = fs.derive.inputs.begin();
              i != fs.derive.inputs.end(); i++)
         {
             PkgHashes::iterator j = state.pkgHashes.find(*i);
             if (j == state.pkgHashes.end())
                 throw Error(format("unknown package id %1%") % (string) *i);
-            *i = j->second;
+            inputs2.insert(j->second);
         }
+	fs.derive.inputs = inputs2;
     }
     return hashTerm(unparseFState(fs));
 }
@@ -159,7 +161,7 @@ static string processBinding(EvalState & state, Expr e, FState & fs)
         Strings paths = fstatePathsCached(state, id);
         if (paths.size() != 1) abort();
         string path = *(paths.begin());
-        fs.derive.inputs.push_back(id);
+        fs.derive.inputs.insert(id);
         return path;
     }
     
@@ -264,12 +266,11 @@ static Expr evalExpr2(EvalState & state, Expr e)
         addToStore(srcPath, dstPath, id, true);
 
         SliceElem elem;
-        elem.path = dstPath;
         elem.id = id;
         FState fs;
         fs.type = FState::fsSlice;
-        fs.slice.roots.push_back(dstPath);
-        fs.slice.elems.push_back(elem);
+        fs.slice.roots.insert(dstPath);
+        fs.slice.elems[dstPath] = elem;
 
         Hash pkgHash = hashPackage(state, fs);
         FSId pkgId = writeTerm(unparseFState(fs), "");
@@ -324,7 +325,7 @@ static Expr evalExpr2(EvalState & state, Expr e)
 
             else {
                 string s = processBinding(state, value, fs);
-                fs.derive.env.push_back(StringPair(key, s));
+                fs.derive.env[key] = s;
 
                 if (key == "build") fs.derive.builder = s;
                 if (key == "name") name = s;
@@ -349,8 +350,8 @@ static Expr evalExpr2(EvalState & state, Expr e)
         if (!outIdGiven) outId = hashPackage(state, fs);
         string outPath = 
             canonPath(nixStore + "/" + ((string) outId).c_str() + "-" + name);
-        fs.derive.env.push_back(StringPair("out", outPath));
-        fs.derive.outputs.push_back(DeriveOutput(outPath, outId));
+        fs.derive.env["out"] = outPath;
+        fs.derive.outputs[outPath] = outId;
 
         /* Write the resulting term into the Nix store directory. */
         Hash pkgHash = outIdGiven
diff --git a/src/fstate.cc b/src/fstate.cc
index 96826b4a2052..0502a8524fa5 100644
--- a/src/fstate.cc
+++ b/src/fstate.cc
@@ -52,14 +52,14 @@ FSId writeTerm(ATerm t, const string & suffix, FSId id)
 }
 
 
-static void parsePaths(ATermList paths, Strings & out)
+static void parsePaths(ATermList paths, StringSet & out)
 {
     while (!ATisEmpty(paths)) {
         char * s;
         ATerm t = ATgetFirst(paths);
         if (!ATmatch(t, "<str>", &s))
             throw badTerm("not a path", t);
-        out.push_back(s);
+        out.insert(s);
         paths = ATgetNext(paths);
     }
 }
@@ -73,21 +73,21 @@ static void checkSlice(const Slice & slice)
     StringSet decl;
     for (SliceElems::const_iterator i = slice.elems.begin();
          i != slice.elems.end(); i++)
-        decl.insert(i->path);
+        decl.insert(i->first);
     
-    for (Strings::const_iterator i = slice.roots.begin();
+    for (StringSet::const_iterator i = slice.roots.begin();
          i != slice.roots.end(); i++)
         if (decl.find(*i) == decl.end())
             throw Error(format("undefined root path `%1%'") % *i);
     
     for (SliceElems::const_iterator i = slice.elems.begin();
          i != slice.elems.end(); i++)
-        for (Strings::const_iterator j = i->refs.begin();
-             j != i->refs.end(); j++)
+        for (StringSet::const_iterator j = i->second.refs.begin();
+             j != i->second.refs.end(); j++)
             if (decl.find(*j) == decl.end())
                 throw Error(
 		    format("undefined path `%1%' referenced by `%2%'")
-		    % *j % i->path);
+		    % *j % i->first);
 }
 
 
@@ -108,10 +108,9 @@ static bool parseSlice(ATerm t, Slice & slice)
         if (!ATmatch(t, "(<str>, <str>, [<list>])", &s1, &s2, &refs))
             throw badTerm("not a slice element", t);
         SliceElem elem;
-        elem.path = s1;
         elem.id = parseHash(s2);
         parsePaths(refs, elem.refs);
-        slice.elems.push_back(elem);
+        slice.elems[s1] = elem;
         elems = ATgetNext(elems);
     }
 
@@ -141,7 +140,7 @@ static bool parseDerive(ATerm t, Derive & derive)
         ATerm t = ATgetFirst(outs);
         if (!ATmatch(t, "(<str>, <str>)", &s1, &s2))
             throw badTerm("not a derive output", t);
-        derive.outputs.push_back(DeriveOutput(s1, parseHash(s2)));
+        derive.outputs[s1] = parseHash(s2);
         outs = ATgetNext(outs);
     }
 
@@ -150,7 +149,7 @@ static bool parseDerive(ATerm t, Derive & derive)
         ATerm t = ATgetFirst(ins);
         if (!ATmatch(t, "<str>", &s))
             throw badTerm("not an id", t);
-        derive.inputs.push_back(parseHash(s));
+        derive.inputs.insert(parseHash(s));
         ins = ATgetNext(ins);
     }
 
@@ -171,7 +170,7 @@ static bool parseDerive(ATerm t, Derive & derive)
         ATerm bnd = ATgetFirst(bnds);
         if (!ATmatch(bnd, "(<str>, <str>)", &s1, &s2))
             throw badTerm("tuple of strings expected", bnd);
-        derive.env.push_back(StringPair(s1, s2));
+        derive.env[s1] = s2;
         bnds = ATgetNext(bnds);
     }
 
@@ -191,10 +190,10 @@ FState parseFState(ATerm t)
 }
 
 
-static ATermList unparsePaths(const Strings & paths)
+static ATermList unparsePaths(const StringSet & paths)
 {
     ATermList l = ATempty;
-    for (Strings::const_iterator i = paths.begin();
+    for (StringSet::const_iterator i = paths.begin();
          i != paths.end(); i++)
         l = ATinsert(l, ATmake("<str>", i->c_str()));
     return ATreverse(l);
@@ -210,9 +209,9 @@ static ATerm unparseSlice(const Slice & slice)
          i != slice.elems.end(); i++)
         elems = ATinsert(elems,
             ATmake("(<str>, <str>, <term>)",
-                i->path.c_str(),
-                ((string) i->id).c_str(),
-                unparsePaths(i->refs)));
+                i->first.c_str(),
+                ((string) i->second.id).c_str(),
+                unparsePaths(i->second.refs)));
 
     return ATmake("Slice(<term>, <term>)", roots, elems);
 }
@@ -228,7 +227,7 @@ static ATerm unparseDerive(const Derive & derive)
                 i->first.c_str(), ((string) i->second).c_str()));
     
     ATermList ins = ATempty;
-    for (FSIds::const_iterator i = derive.inputs.begin();
+    for (FSIdSet::const_iterator i = derive.inputs.begin();
          i != derive.inputs.end(); i++)
         ins = ATinsert(ins, ATmake("<str>", ((string) *i).c_str()));
 
diff --git a/src/fstate.hh b/src/fstate.hh
index e4f69cb232df..a7935be5250e 100644
--- a/src/fstate.hh
+++ b/src/fstate.hh
@@ -14,28 +14,25 @@ typedef list<FSId> FSIds;
 
 struct SliceElem
 {
-    string path;
     FSId id;
-    Strings refs;
+    StringSet refs;
 };
 
-typedef list<SliceElem> SliceElems;
+typedef map<string, SliceElem> SliceElems;
 
 struct Slice
 {
-    Strings roots;
+    StringSet roots;
     SliceElems elems;
 };
 
-typedef pair<string, FSId> DeriveOutput;
-typedef pair<string, string> StringPair;
-typedef list<DeriveOutput> DeriveOutputs;
-typedef list<StringPair> StringPairs;
+typedef map<string, FSId> DeriveOutputs;
+typedef map<string, string> StringPairs;
 
 struct Derive
 {
     DeriveOutputs outputs;
-    FSIds inputs;
+    FSIdSet inputs;
     string platform;
     string builder;
     Strings args;
diff --git a/src/nix.cc b/src/nix.cc
index 704442c313e4..04195e8d4428 100644
--- a/src/nix.cc
+++ b/src/nix.cc
@@ -193,7 +193,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
                     string label, shape;
                     
                     if (fs.type == FState::fsDerive) {
-                        for (FSIds::iterator i = fs.derive.inputs.begin();
+                        for (FSIdSet::iterator i = fs.derive.inputs.begin();
                              i != fs.derive.inputs.end(); i++)
                         {
                             workList.push_back(*i);
@@ -209,7 +209,7 @@ static void opQuery(Strings opFlags, Strings opArgs)
                     }
 
                     else if (fs.type == FState::fsSlice) {
-                        label = baseNameOf((*fs.slice.elems.begin()).path);
+                        label = baseNameOf((*fs.slice.elems.begin()).first);
                         shape = "ellipse";
                         if (isHash(string(label, 0, Hash::hashSize * 2)) && 
                             label[Hash::hashSize * 2] == '-')
diff --git a/src/normalise.cc b/src/normalise.cc
index 09fcc2238d8a..52437059a4e3 100644
--- a/src/normalise.cc
+++ b/src/normalise.cc
@@ -26,14 +26,10 @@ static FSId useSuccessor(const FSId & id)
 }
 
 
-typedef map<string, FSId> OutPaths;
-typedef map<string, SliceElem> ElemMap;
-
-
-Strings pathsFromOutPaths(const OutPaths & ps)
+Strings pathsFromOutputs(const DeriveOutputs & ps)
 {
     Strings ss;
-    for (OutPaths::const_iterator i = ps.begin();
+    for (DeriveOutputs::const_iterator i = ps.begin();
          i != ps.end(); i++)
         ss.push_back(i->first);
     return ss;
@@ -62,31 +58,31 @@ FSId normaliseFState(FSId id, FSIdSet pending)
 
     /* Some variables. */
 
-    /* Output paths, with their ids. */
-    OutPaths outPaths;
-
     /* Input paths, with their slice elements. */
-    ElemMap inMap; 
+    SliceElems inSlices; 
 
     /* Referencable paths (i.e., input and output paths). */
-    Strings allPaths;
+    StringSet allPaths;
 
     /* The environment to be passed to the builder. */
     Environment env; 
 
+    /* The result. */
+    FState nfFS;
+    nfFS.type = FState::fsSlice;
+
 
     /* Parse the outputs. */
     for (DeriveOutputs::iterator i = fs.derive.outputs.begin();
          i != fs.derive.outputs.end(); i++)
     {
         debug(format("building %1% in `%2%'") % (string) i->second % i->first);
-        outPaths[i->first] = i->second;
-        allPaths.push_back(i->first);
+        allPaths.insert(i->first);
     }
 
     /* Obtain locks on all output paths.  The locks are automatically
        released when we exit this function or Nix crashes. */
-    PathLocks outputLocks(pathsFromOutPaths(outPaths));
+    PathLocks outputLocks(pathsFromOutputs(fs.derive.outputs));
 
     /* Now check again whether there is a successor.  This is because
        another process may have started building in parallel.  After
@@ -113,8 +109,9 @@ FSId normaliseFState(FSId id, FSIdSet pending)
 		    % fs.derive.platform % thisSystem);
         
     /* Realise inputs (and remember all input paths). */
-    for (FSIds::iterator i = fs.derive.inputs.begin();
-         i != fs.derive.inputs.end(); i++) {
+    for (FSIdSet::iterator i = fs.derive.inputs.begin();
+         i != fs.derive.inputs.end(); i++)
+    {
         FSId nf = normaliseFState(*i, pending);
         realiseSlice(nf, pending);
         /* !!! nf should be a root of the garbage collector while we
@@ -123,12 +120,12 @@ FSId normaliseFState(FSId id, FSIdSet pending)
         if (fs.type != FState::fsSlice) abort();
         for (SliceElems::iterator j = fs.slice.elems.begin();
              j != fs.slice.elems.end(); j++)
-            inMap[j->path] = *j;
+	{
+            inSlices[j->first] = j->second;
+	    allPaths.insert(j->first);
+	}
     }
 
-    for (ElemMap::iterator i = inMap.begin(); i != inMap.end(); i++)
-        allPaths.push_back(i->second.path);
-
     /* Most shells initialise PATH to some default (/bin:/usr/bin:...) when
        PATH is not set.  We don't want this, so we fill it in with some dummy
        value. */
@@ -142,8 +139,8 @@ FSId normaliseFState(FSId id, FSIdSet pending)
     /* We can skip running the builder if we can expand all output
        paths from their ids. */
     bool fastBuild = true;
-    for (OutPaths::iterator i = outPaths.begin();
-         i != outPaths.end(); i++)
+    for (DeriveOutputs::iterator i = fs.derive.outputs.begin();
+         i != fs.derive.outputs.end(); i++)
     {
         try {
             expandId(i->second, i->first, "/", pending);
@@ -159,8 +156,8 @@ FSId normaliseFState(FSId id, FSIdSet pending)
 
         /* If any of the outputs already exist but are not registered,
            delete them. */
-        for (OutPaths::iterator i = outPaths.begin(); 
-             i != outPaths.end(); i++)
+        for (DeriveOutputs::iterator i = fs.derive.outputs.begin(); 
+             i != fs.derive.outputs.end(); i++)
         {
             string path = i->first;
             FSId id;
@@ -183,21 +180,21 @@ FSId normaliseFState(FSId id, FSIdSet pending)
     /* Check whether the output paths were created, and grep each
        output path to determine what other paths it references. */
     StringSet usedPaths;
-    for (OutPaths::iterator i = outPaths.begin(); 
-         i != outPaths.end(); i++)
+    for (DeriveOutputs::iterator i = fs.derive.outputs.begin(); 
+         i != fs.derive.outputs.end(); i++)
     {
         string path = i->first;
         if (!pathExists(path))
             throw Error(format("path `%1%' does not exist") % path);
-        fs.slice.roots.push_back(path);
+        nfFS.slice.roots.insert(path);
 
 	/* For this output path, find the references to other paths contained
 	   in it. */
-        Strings refPaths = filterReferences(path, allPaths);
+        Strings refPaths = filterReferences(path, 
+	    Strings(allPaths.begin(), allPaths.end()));
 
 	/* Construct a slice element for this output path. */
         SliceElem elem;
-        elem.path = path;
         elem.id = i->second;
 
 	/* For each path referenced by this output path, add its id to the
@@ -207,18 +204,14 @@ FSId normaliseFState(FSId id, FSIdSet pending)
 	     j != refPaths.end(); j++)
 	{
 	    string path = *j;
-            ElemMap::iterator k;
-            OutPaths::iterator l;
-
-	    elem.refs.push_back(path);
-
-            if ((k = inMap.find(path)) != inMap.end())
-                usedPaths.insert(k->second.path);
-	    else if ((l = outPaths.find(path)) == outPaths.end())
+	    elem.refs.insert(path);
+            if (inSlices.find(path) != inSlices.end())
+                usedPaths.insert(path);
+	    else if (fs.derive.outputs.find(path) == fs.derive.outputs.end())
 		abort();
         }
 
-        fs.slice.elems.push_back(elem);
+        nfFS.slice.elems[path] = elem;
     }
 
     /* Close the slice.  That is, for any referenced path, add the paths
@@ -233,31 +226,30 @@ FSId normaliseFState(FSId id, FSIdSet pending)
 	if (donePaths.find(path) != donePaths.end()) continue;
 	donePaths.insert(path);
 
-	ElemMap::iterator j = inMap.find(path);
-	if (j == inMap.end()) abort();
+	SliceElems::iterator j = inSlices.find(path);
+	if (j == inSlices.end()) abort();
 
-	fs.slice.elems.push_back(j->second);
+	nfFS.slice.elems[path] = j->second;
 
-	for (Strings::iterator k = j->second.refs.begin();
+	for (StringSet::iterator k = j->second.refs.begin();
 	     k != j->second.refs.end(); k++)
 	    usedPaths.insert(*k);
     }
 
     /* For debugging, print out the referenced and unreferenced paths. */
-    for (ElemMap::iterator i = inMap.begin();
-         i != inMap.end(); i++)
+    for (SliceElems::iterator i = inSlices.begin();
+         i != inSlices.end(); i++)
     {
-        StringSet::iterator j = donePaths.find(i->second.path);
+        StringSet::iterator j = donePaths.find(i->first);
         if (j == donePaths.end())
-            debug(format("NOT referenced: `%1%'") % i->second.path);
+            debug(format("NOT referenced: `%1%'") % i->first);
         else
-            debug(format("referenced: `%1%'") % i->second.path);
+            debug(format("referenced: `%1%'") % i->first);
     }
 
     /* Write the normal form.  This does not have to occur in the
        transaction below because writing terms is idem-potent. */
-    fs.type = FState::fsSlice;
-    ATerm nf = unparseFState(fs);
+    ATerm nf = unparseFState(nfFS);
     msg(lvlVomit, format("normal form: %1%") % printTerm(nf));
     FSId idNF = writeTerm(nf, "-s-" + (string) id);
 
@@ -268,8 +260,8 @@ FSId normaliseFState(FSId id, FSIdSet pending)
        deleted arbitrarily, while registered paths can only be deleted
        by running the garbage collector. */
     Transaction txn(nixDB);
-    for (OutPaths::iterator i = outPaths.begin(); 
-         i != outPaths.end(); i++)
+    for (DeriveOutputs::iterator i = fs.derive.outputs.begin(); 
+         i != fs.derive.outputs.end(); i++)
         registerPath(txn, i->first, i->second);
     registerSuccessor(txn, id, idNF);
     txn.commit();
@@ -289,10 +281,7 @@ void realiseSlice(const FSId & id, FSIdSet pending)
     
     for (SliceElems::const_iterator i = fs.slice.elems.begin();
          i != fs.slice.elems.end(); i++)
-    {
-        SliceElem elem = *i;
-        expandId(elem.id, elem.path, "/", pending);
-    }
+        expandId(i->second.id, i->first, "/", pending);
 }
 
 
@@ -303,12 +292,9 @@ Strings fstatePaths(const FSId & id)
     FState fs = parseFState(termFromId(id));
 
     if (fs.type == FState::fsSlice) {
-        /* !!! fix complexity */
-        for (Strings::const_iterator i = fs.slice.roots.begin();
+        for (StringSet::const_iterator i = fs.slice.roots.begin();
              i != fs.slice.roots.end(); i++)
-            for (SliceElems::const_iterator j = fs.slice.elems.begin();
-                 j != fs.slice.elems.end(); j++)
-                if (*i == j->path) paths.push_back(j->path);
+	    paths.push_back(*i);
     }
 
     else if (fs.type == FState::fsDerive) {
@@ -328,18 +314,16 @@ static void fstateRequisitesSet(const FSId & id,
 {
     FState fs = parseFState(termFromId(id));
 
-    if (fs.type == FState::fsSlice) {
+    if (fs.type == FState::fsSlice)
         for (SliceElems::iterator i = fs.slice.elems.begin();
              i != fs.slice.elems.end(); i++)
-            paths.insert(i->path);
-    }
+            paths.insert(i->first);
     
-    else if (fs.type == FState::fsDerive) {
-        for (FSIds::iterator i = fs.derive.inputs.begin();
+    else if (fs.type == FState::fsDerive)
+        for (FSIdSet::iterator i = fs.derive.inputs.begin();
              i != fs.derive.inputs.end(); i++)
             fstateRequisitesSet(*i,
                 includeExprs, includeSuccessors, paths);
-    }
 
     else abort();
 
@@ -394,7 +378,7 @@ FSIds findGenerators(const FSIds & _ids)
         bool okay = true;
         for (SliceElems::const_iterator i = fs.slice.elems.begin();
              i != fs.slice.elems.end(); i++)
-            if (ids.find(i->id) == ids.end()) {
+            if (ids.find(i->second.id) == ids.end()) {
                 okay = false;
                 break;
             }