* Change the abstract syntax of slices. It used to be that ids were used as

  keys to reference slice elements, e.g.,

    Slice(["1ef7..."], [("/nix/store/1ef7...-foo", "1ef7", ["8c99..."]), ...])

  This was wrong, since ids represent contents, not locations.  Therefore we
  now have:

    Slice(["/nix/store/1ef7..."], [("/nix/store/1ef7...-foo", "1ef7", ["/nix/store/8c99-..."]), ...])

* Fix a bug in the computation of slice closures that could cause slice
  elements to be duplicated.

4 files changed, 59 insertions, 61 deletions

diff --git a/src/fix.cc b/src/fix.cc
index ef35703342..83e25d142a 100644
--- a/src/fix.cc
+++ b/src/fix.cc
@@ -268,7 +268,7 @@ static Expr evalExpr2(EvalState & state, Expr e)
         elem.id = id;
         FState fs;
         fs.type = FState::fsSlice;
-        fs.slice.roots.push_back(id);
+        fs.slice.roots.push_back(dstPath);
         fs.slice.elems.push_back(elem);
 
         Hash pkgHash = hashPackage(state, fs);
diff --git a/src/fstate.cc b/src/fstate.cc
index 47a93901fe..96826b4a20 100644
--- a/src/fstate.cc
+++ b/src/fstate.cc
@@ -52,15 +52,15 @@ FSId writeTerm(ATerm t, const string & suffix, FSId id)
 }
 
 
-static void parseIds(ATermList ids, FSIds & out)
+static void parsePaths(ATermList paths, Strings & out)
 {
-    while (!ATisEmpty(ids)) {
+    while (!ATisEmpty(paths)) {
         char * s;
-        ATerm id = ATgetFirst(ids);
-        if (!ATmatch(id, "<str>", &s))
-            throw badTerm("not an id", id);
-        out.push_back(parseHash(s));
-        ids = ATgetNext(ids);
+        ATerm t = ATgetFirst(paths);
+        if (!ATmatch(t, "<str>", &s))
+            throw badTerm("not a path", t);
+        out.push_back(s);
+        paths = ATgetNext(paths);
     }
 }
 
@@ -70,22 +70,24 @@ static void checkSlice(const Slice & slice)
     if (slice.elems.size() == 0)
         throw Error("empty slice");
 
-    FSIdSet decl;
+    StringSet decl;
     for (SliceElems::const_iterator i = slice.elems.begin();
          i != slice.elems.end(); i++)
-        decl.insert(i->id);
+        decl.insert(i->path);
     
-    for (FSIds::const_iterator i = slice.roots.begin();
+    for (Strings::const_iterator i = slice.roots.begin();
          i != slice.roots.end(); i++)
         if (decl.find(*i) == decl.end())
-            throw Error(format("undefined id: %1%") % (string) *i);
+            throw Error(format("undefined root path `%1%'") % *i);
     
     for (SliceElems::const_iterator i = slice.elems.begin();
          i != slice.elems.end(); i++)
-        for (FSIds::const_iterator j = i->refs.begin();
+        for (Strings::const_iterator j = i->refs.begin();
              j != i->refs.end(); j++)
             if (decl.find(*j) == decl.end())
-                throw Error(format("undefined id: %1%") % (string) *j);
+                throw Error(
+		    format("undefined path `%1%' referenced by `%2%'")
+		    % *j % i->path);
 }
 
 
@@ -97,7 +99,7 @@ static bool parseSlice(ATerm t, Slice & slice)
     if (!ATmatch(t, "Slice([<list>], [<list>])", &roots, &elems))
         return false;
 
-    parseIds(roots, slice.roots);
+    parsePaths(roots, slice.roots);
 
     while (!ATisEmpty(elems)) {
         char * s1, * s2;
@@ -108,7 +110,7 @@ static bool parseSlice(ATerm t, Slice & slice)
         SliceElem elem;
         elem.path = s1;
         elem.id = parseHash(s2);
-        parseIds(refs, elem.refs);
+        parsePaths(refs, elem.refs);
         slice.elems.push_back(elem);
         elems = ATgetNext(elems);
     }
@@ -143,7 +145,14 @@ static bool parseDerive(ATerm t, Derive & derive)
         outs = ATgetNext(outs);
     }
 
-    parseIds(ins, derive.inputs);
+    while (!ATisEmpty(ins)) {
+        char * s;
+        ATerm t = ATgetFirst(ins);
+        if (!ATmatch(t, "<str>", &s))
+            throw badTerm("not an id", t);
+        derive.inputs.push_back(parseHash(s));
+        ins = ATgetNext(ins);
+    }
 
     derive.builder = builder;
     derive.platform = platform;
@@ -182,20 +191,19 @@ FState parseFState(ATerm t)
 }
 
 
-static ATermList unparseIds(const FSIds & ids)
+static ATermList unparsePaths(const Strings & paths)
 {
     ATermList l = ATempty;
-    for (FSIds::const_iterator i = ids.begin();
-         i != ids.end(); i++)
-        l = ATinsert(l,
-            ATmake("<str>", ((string) *i).c_str()));
+    for (Strings::const_iterator i = paths.begin();
+         i != paths.end(); i++)
+        l = ATinsert(l, ATmake("<str>", i->c_str()));
     return ATreverse(l);
 }
 
 
 static ATerm unparseSlice(const Slice & slice)
 {
-    ATermList roots = unparseIds(slice.roots);
+    ATermList roots = unparsePaths(slice.roots);
     
     ATermList elems = ATempty;
     for (SliceElems::const_iterator i = slice.elems.begin();
@@ -204,7 +212,7 @@ static ATerm unparseSlice(const Slice & slice)
             ATmake("(<str>, <str>, <term>)",
                 i->path.c_str(),
                 ((string) i->id).c_str(),
-                unparseIds(i->refs)));
+                unparsePaths(i->refs)));
 
     return ATmake("Slice(<term>, <term>)", roots, elems);
 }
@@ -219,6 +227,11 @@ static ATerm unparseDerive(const Derive & derive)
             ATmake("(<str>, <str>)", 
                 i->first.c_str(), ((string) i->second).c_str()));
     
+    ATermList ins = ATempty;
+    for (FSIds::const_iterator i = derive.inputs.begin();
+         i != derive.inputs.end(); i++)
+        ins = ATinsert(ins, ATmake("<str>", ((string) *i).c_str()));
+
     ATermList args = ATempty;
     for (Strings::const_iterator i = derive.args.begin();
          i != derive.args.end(); i++)
@@ -233,7 +246,7 @@ static ATerm unparseDerive(const Derive & derive)
 
     return ATmake("Derive(<term>, <term>, <str>, <str>, <term>, <term>)",
         ATreverse(outs),
-        unparseIds(derive.inputs),
+        ATreverse(ins),
         derive.platform.c_str(),
         derive.builder.c_str(),
         ATreverse(args),
diff --git a/src/fstate.hh b/src/fstate.hh
index b71739aed9..e4f69cb232 100644
--- a/src/fstate.hh
+++ b/src/fstate.hh
@@ -16,14 +16,14 @@ struct SliceElem
 {
     string path;
     FSId id;
-    FSIds refs;
+    Strings refs;
 };
 
 typedef list<SliceElem> SliceElems;
 
 struct Slice
 {
-    FSIds roots;
+    Strings roots;
     SliceElems elems;
 };
 
diff --git a/src/normalise.cc b/src/normalise.cc
index 35f6b2d087..09fcc2238d 100644
--- a/src/normalise.cc
+++ b/src/normalise.cc
@@ -101,7 +101,7 @@ FSId normaliseFState(FSId id, FSIdSet pending)
         if (id2 != id) {
             FState fs = parseFState(termFromId(id2));
             debug(format("skipping build of %1%, someone beat us to it")
-                % (string) id);
+		  % (string) id);
             if (fs.type != FState::fsSlice) abort();
             return id2;
         }
@@ -110,7 +110,7 @@ FSId normaliseFState(FSId id, FSIdSet pending)
     /* Right platform? */
     if (fs.derive.platform != thisSystem)
         throw Error(format("a `%1%' is required, but I am a `%2%'")
-            % fs.derive.platform % thisSystem);
+		    % fs.derive.platform % thisSystem);
         
     /* Realise inputs (and remember all input paths). */
     for (FSIds::iterator i = fs.derive.inputs.begin();
@@ -149,7 +149,7 @@ FSId normaliseFState(FSId id, FSIdSet pending)
             expandId(i->second, i->first, "/", pending);
         } catch (Error & e) {
             debug(format("fast build failed for `%1%': %2%")
-                % i->first % e.what());
+		  % i->first % e.what());
             fastBuild = false;
             break;
         }
@@ -189,7 +189,7 @@ FSId normaliseFState(FSId id, FSIdSet pending)
         string path = i->first;
         if (!pathExists(path))
             throw Error(format("path `%1%' does not exist") % path);
-        fs.slice.roots.push_back(i->second);
+        fs.slice.roots.push_back(path);
 
 	/* For this output path, find the references to other paths contained
 	   in it. */
@@ -201,7 +201,7 @@ FSId normaliseFState(FSId id, FSIdSet pending)
         elem.id = i->second;
 
 	/* For each path referenced by this output path, add its id to the
-	   slice element and add the id to the `used' set (so that the
+	   slice element and add the id to the `usedPaths' set (so that the
 	   elements referenced by *its* slice are added below). */
         for (Strings::iterator j = refPaths.begin();
 	     j != refPaths.end(); j++)
@@ -210,18 +210,12 @@ FSId normaliseFState(FSId id, FSIdSet pending)
             ElemMap::iterator k;
             OutPaths::iterator l;
 
-	    /* Is it an input path? */
-            if ((k = inMap.find(path)) != inMap.end()) {
-                elem.refs.push_back(k->second.id);
-                usedPaths.insert(k->second.path);
-            }
+	    elem.refs.push_back(path);
 
-	    /* Or an output path? */
-	    else if ((l = outPaths.find(path)) != outPaths.end())
-                elem.refs.push_back(l->second);
-            
-	    /* Can't happen. */ 
-	    else abort();
+            if ((k = inMap.find(path)) != inMap.end())
+                usedPaths.insert(k->second.path);
+	    else if ((l = outPaths.find(path)) == outPaths.end())
+		abort();
         }
 
         fs.slice.elems.push_back(elem);
@@ -229,40 +223,31 @@ FSId normaliseFState(FSId id, FSIdSet pending)
 
     /* Close the slice.  That is, for any referenced path, add the paths
        referenced by it. */
-    FSIdSet donePaths;
+    StringSet donePaths;
 
     while (!usedPaths.empty()) {
 	StringSet::iterator i = usedPaths.begin();
 	string path = *i;
 	usedPaths.erase(i);
 
+	if (donePaths.find(path) != donePaths.end()) continue;
+	donePaths.insert(path);
+
 	ElemMap::iterator j = inMap.find(path);
 	if (j == inMap.end()) abort();
 
-	donePaths.insert(j->second.id);
-
 	fs.slice.elems.push_back(j->second);
 
-	for (FSIds::iterator k = j->second.refs.begin();
+	for (Strings::iterator k = j->second.refs.begin();
 	     k != j->second.refs.end(); k++)
-	    if (donePaths.find(*k) == donePaths.end()) {
-		/* !!! performance */
-		bool found = false;
-		for (ElemMap::iterator l = inMap.begin();
-		     l != inMap.end(); l++)
-		    if (l->second.id == *k) {
-			usedPaths.insert(l->first);
-			found = true;
-		    }
-		if (!found) abort();
-	    }
+	    usedPaths.insert(*k);
     }
 
     /* For debugging, print out the referenced and unreferenced paths. */
     for (ElemMap::iterator i = inMap.begin();
          i != inMap.end(); i++)
     {
-        FSIdSet::iterator j = donePaths.find(i->second.id);
+        StringSet::iterator j = donePaths.find(i->second.path);
         if (j == donePaths.end())
             debug(format("NOT referenced: `%1%'") % i->second.path);
         else
@@ -319,11 +304,11 @@ Strings fstatePaths(const FSId & id)
 
     if (fs.type == FState::fsSlice) {
         /* !!! fix complexity */
-        for (FSIds::const_iterator i = fs.slice.roots.begin();
+        for (Strings::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->id) paths.push_back(j->path);
+                if (*i == j->path) paths.push_back(j->path);
     }
 
     else if (fs.type == FState::fsDerive) {