* Substitutes now should produce a path with the same id as they are

  substituting for (obvious, really).

* For greater efficiency, nix-pull/unnar will place the output in a
  path that is probably the same as what is actually needed, thus
  preventing a path copy.

* Even if a output id is given in a Fix package expression, ensure
  that the resulting Nix derive expression has a different id.  This
  is because Nix expressions that are semantically equivalent (i.e.,
  build the same result) might be different w.r.t. efficiency or
  divergence.  It is absolutely vital for the substitute mechanism
  that such expressions are not used interchangeably.

6 files changed, 72 insertions, 46 deletions

diff --git a/src/fix.cc b/src/fix.cc
index 93cc27cfca7c..afa0167ecdc0 100644
--- a/src/fix.cc
+++ b/src/fix.cc
@@ -9,11 +9,13 @@
 typedef ATerm Expr;
 
 typedef map<ATerm, ATerm> NormalForms;
+typedef map<FSId, Hash> PkgHashes;
 
 struct EvalState 
 {
     Strings searchDirs;
     NormalForms normalForms;
+    PkgHashes pkgHashes; /* normalised package hashes */
 };
 
 
@@ -104,6 +106,23 @@ static Expr substExprMany(ATermList formals, ATermList args, Expr body)
 }
 
 
+Hash hashPackage(EvalState & state, FState fs)
+{
+    if (fs.type == FState::fsDerive) {
+        for (FSIds::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;
+        }
+    }
+    debug(printTerm(unparseFState(fs)));
+    return hashTerm(unparseFState(fs));
+}
+
+
 static Expr evalExpr2(EvalState & state, Expr e)
 {
     char * s1;
@@ -117,9 +136,10 @@ static Expr evalExpr2(EvalState & state, Expr e)
         return e;
 
     try {
-        parseFState(e);
-        return ATmake("FSId(<str>)", 
-            ((string) writeTerm(e, "")).c_str());
+        Hash pkgHash = hashPackage(state, parseFState(e));
+        FSId pkgId = writeTerm(e, "");
+        state.pkgHashes[pkgId] = pkgHash;
+        return ATmake("FSId(<str>)", ((string) pkgId).c_str());
     } catch (...) { /* !!! catch parse errors only */
     }
 
@@ -153,10 +173,10 @@ static Expr evalExpr2(EvalState & state, Expr e)
         fs.slice.roots.push_back(id);
         fs.slice.elems.push_back(elem);
 
-        FSId termId = hashString("producer-" + (string) id
-            + "-" + dstPath);
-        writeTerm(unparseFState(fs), "", termId);
-        return ATmake("FSId(<str>)", ((string) termId).c_str());
+        Hash pkgHash = hashPackage(state, fs);
+        FSId pkgId = writeTerm(unparseFState(fs), "");
+        state.pkgHashes[pkgId] = pkgHash;
+        return ATmake("FSId(<str>)", ((string) pkgId).c_str());
     }
 
     /* Packages are transformed into Derive fstate expressions. */
@@ -179,6 +199,7 @@ static Expr evalExpr2(EvalState & state, Expr e)
         fs.derive.platform = SYSTEM;
         string name;
         FSId outId;
+        bool outIdGiven = false;
         bnds = ATempty;
 
         for (map<string, ATerm>::iterator it = bndMap.begin();
@@ -198,7 +219,10 @@ static Expr evalExpr2(EvalState & state, Expr e)
             }
             else if (ATmatch(value, "<str>", &s1)) {
                 if (key == "name") name = s1;
-                if (key == "id") outId = parseHash(s1);
+                if (key == "id") { 
+                    outId = parseHash(s1);
+                    outIdGiven = true;
+                }
                 fs.derive.env.push_back(StringPair(key, s1));
             }
             else throw badTerm("invalid package argument", value);
@@ -215,8 +239,7 @@ static Expr evalExpr2(EvalState & state, Expr e)
         
         /* Hash the fstate-expression with no outputs to produce a
            unique but deterministic path name for this package. */
-        if (outId == FSId())
-            outId = hashTerm(unparseFState(fs));
+        if (!outIdGiven) outId = hashPackage(state, fs);
         string outPath = 
             canonPath(nixStore + "/" + ((string) outId).c_str() + "-" + name);
         fs.derive.env.push_back(StringPair("out", outPath));
@@ -224,10 +247,12 @@ static Expr evalExpr2(EvalState & state, Expr e)
         debug(format("%1%: %2%") % (string) outId % name);
 
         /* Write the resulting term into the Nix store directory. */
-        FSId termId = hashString("producer-" + (string) outId
-            + "-" + outPath);
-        writeTerm(unparseFState(fs), "-d-" + name, termId);
-        return ATmake("FSId(<str>)", ((string) termId).c_str());
+        Hash pkgHash = outIdGiven
+            ? hashString((string) outId + outPath)
+            : hashPackage(state, fs);
+        FSId pkgId = writeTerm(unparseFState(fs), "-d-" + name);
+        state.pkgHashes[pkgId] = pkgHash;
+        return ATmake("FSId(<str>)", ((string) pkgId).c_str());
     }
 
     /* BaseName primitive function. */
diff --git a/src/fstate.cc b/src/fstate.cc
index 1c8c6776f1ed..5da3d8358f74 100644
--- a/src/fstate.cc
+++ b/src/fstate.cc
@@ -62,9 +62,6 @@ static void parseIds(ATermList ids, FSIds & out)
 }
 
 
-typedef set<FSId> FSIdSet;
-
-
 static void checkSlice(const Slice & slice)
 {
     if (slice.elems.size() == 0)
diff --git a/src/normalise.cc b/src/normalise.cc
index 8da940aa67ce..f463457e4ab5 100644
--- a/src/normalise.cc
+++ b/src/normalise.cc
@@ -24,7 +24,7 @@ static FSId storeSuccessor(const FSId & id1, ATerm sc)
 typedef set<FSId> FSIdSet;
 
 
-Slice normaliseFState(FSId id)
+Slice normaliseFState(FSId id, FSIdSet pending)
 {
     debug(format("normalising fstate %1%") % (string) id);
     Nest nest(true);
@@ -57,8 +57,8 @@ Slice normaliseFState(FSId id)
 
     for (FSIds::iterator i = fs.derive.inputs.begin();
          i != fs.derive.inputs.end(); i++) {
-        Slice slice = normaliseFState(*i);
-        realiseSlice(slice);
+        Slice slice = normaliseFState(*i, pending);
+        realiseSlice(slice, pending);
 
         for (SliceElems::iterator j = slice.elems.begin();
              j != slice.elems.end(); j++)
@@ -93,7 +93,7 @@ Slice normaliseFState(FSId id)
          i != outPaths.end(); i++)
     {
         try {
-            expandId(i->second, i->first);
+            expandId(i->second, i->first, "/", pending);
         } catch (Error & e) {
             debug(format("fast build failed: %1%") % e.what());
             fastBuild = false;
@@ -175,7 +175,7 @@ Slice normaliseFState(FSId id)
 }
 
 
-void realiseSlice(const Slice & slice)
+void realiseSlice(const Slice & slice, FSIdSet pending)
 {
     debug(format("realising slice"));
     Nest nest(true);
@@ -209,7 +209,7 @@ void realiseSlice(const Slice & slice)
     {
         SliceElem elem = *i;
         debug(format("expanding %1% in %2%") % (string) elem.id % elem.path);
-        expandId(elem.id, elem.path);
+        expandId(elem.id, elem.path, "/", pending);
     }
 }
 
diff --git a/src/normalise.hh b/src/normalise.hh
index 49f9e68eee63..72ee1d0897d6 100644
--- a/src/normalise.hh
+++ b/src/normalise.hh
@@ -5,11 +5,11 @@
 
 
 /* Normalise an fstate-expression, that is, return an equivalent
-   Slice. */
-Slice normaliseFState(FSId id);
+   Slice.  (For the meaning of `pending', see expandId()). */
+Slice normaliseFState(FSId id, FSIdSet pending = FSIdSet());
 
 /* Realise a Slice in the file system. */
-void realiseSlice(const Slice & slice);
+void realiseSlice(const Slice & slice, FSIdSet pending = FSIdSet());
 
 /* Get the list of root (output) paths of the given
    fstate-expression. */
diff --git a/src/store.cc b/src/store.cc
index 65c44ca37fee..013bd2e2a7bc 100644
--- a/src/store.cc
+++ b/src/store.cc
@@ -165,8 +165,11 @@ bool isInPrefix(const string & path, const string & _prefix)
 
 
 string expandId(const FSId & id, const string & target,
-    const string & prefix)
+    const string & prefix, FSIdSet pending)
 {
+    debug(format("expanding %1%") % (string) id);
+    Nest nest(true);
+
     Strings paths;
 
     if (!target.empty() && !isInPrefix(target, prefix))
@@ -203,30 +206,24 @@ string expandId(const FSId & id, const string & target,
         }
     }
 
-    /* Try to realise the substitutes. */
+    if (pending.find(id) != pending.end())
+        throw Error(format("id %1% already being expanded") % (string) id);
+    pending.insert(id);
 
+    /* Try to realise the substitutes, but only if this id is not
+       already being realised by a substitute. */
     Strings subs;
     queryListDB(nixDB, dbSubstitutes, id, subs); /* non-existence = ok */
 
     for (Strings::iterator it = subs.begin(); it != subs.end(); it++) {
         FSId subId = parseHash(*it);
-        Slice slice = normaliseFState(subId);
-        realiseSlice(slice);
-        
-        Strings paths = fstatePaths(subId, true);
-        if (paths.size() != 1) 
-            throw Error("substitute created more than 1 path");
-        string path = *(paths.begin());
 
-        if (target.empty())
-            return path; /* !!! prefix */
-        else {
-            if (path != target) {
-                copyPath(path, target);
-                registerPath(target, id);
-            }
-            return target;
-        }
+        debug(format("trying substitute %1%") % (string) subId);
+
+        Slice slice = normaliseFState(subId, pending);
+        realiseSlice(slice, pending);
+
+        return expandId(id, target, prefix, pending);
     }
     
     throw Error(format("cannot expand id `%1%'") % (string) id);
diff --git a/src/store.hh b/src/store.hh
index faac760099bf..b2cdc41f166e 100644
--- a/src/store.hh
+++ b/src/store.hh
@@ -10,6 +10,8 @@ using namespace std;
 
 typedef Hash FSId;
 
+typedef set<FSId> FSIdSet;
+
 
 /* Copy a path recursively. */
 void copyPath(string src, string dst);
@@ -26,9 +28,14 @@ bool queryPathId(const string & path, FSId & id);
 /* Return a path whose contents have the given hash.  If target is
    not empty, ensure that such a path is realised in target (if
    necessary by copying from another location).  If prefix is not
-   empty, only return a path that is an descendent of prefix. */
+   empty, only return a path that is an descendent of prefix.
+
+   The list of pending ids are those that already being expanded.
+   This prevents infinite recursion for ids realised through a
+   substitute (since when we build the substitute, we would first try
+   to expand the id... kaboom!). */
 string expandId(const FSId & id, const string & target = "",
-    const string & prefix = "/");
+    const string & prefix = "/", FSIdSet pending = FSIdSet());
 
 /* Copy a file to the nixStore directory and register it in dbRefs.
    Return the hash code of the value. */