Merge remote-tracking branch 'origin/master' into readd-hashed-mirrors

47 files changed, 947 insertions, 456 deletions

diff --git a/src/build-remote/build-remote.cc b/src/build-remote/build-remote.cc
index 3579d8fff..5247cefa6 100644
--- a/src/build-remote/build-remote.cc
+++ b/src/build-remote/build-remote.cc
@@ -103,7 +103,7 @@ static int _main(int argc, char * * argv)
             drvPath = store->parseStorePath(readString(source));
             auto requiredFeatures = readStrings<std::set<std::string>>(source);
 
-             auto canBuildLocally = amWilling
+            auto canBuildLocally = amWilling
                  &&  (  neededSystem == settings.thisSystem
                      || settings.extraPlatforms.get().count(neededSystem) > 0)
                  &&  allSupportedLocally(requiredFeatures);
@@ -170,7 +170,45 @@ static int _main(int argc, char * * argv)
                     if (rightType && !canBuildLocally)
                         std::cerr << "# postpone\n";
                     else
+                    {
+                        // build the hint template.
+                        string hintstring =  "derivation: %s\nrequired (system, features): (%s, %s)";
+                        hintstring += "\n%s available machines:";
+                        hintstring += "\n(systems, maxjobs, supportedFeatures, mandatoryFeatures)";
+
+                        for (unsigned int i = 0; i < machines.size(); ++i) {
+                          hintstring += "\n(%s, %s, %s, %s)";
+                        }
+
+                        // add the template values.
+                        string drvstr;
+                        if (drvPath.has_value())
+                            drvstr = drvPath->to_string();
+                        else
+                            drvstr = "<unknown>";
+
+                        auto hint = hintformat(hintstring);
+                        hint
+                          % drvstr
+                          % neededSystem
+                          % concatStringsSep<StringSet>(", ", requiredFeatures)
+                          % machines.size();
+
+                        for (auto & m : machines) {
+                          hint % concatStringsSep<vector<string>>(", ", m.systemTypes)
+                            % m.maxJobs
+                            % concatStringsSep<StringSet>(", ", m.supportedFeatures)
+                            % concatStringsSep<StringSet>(", ", m.mandatoryFeatures);
+                        }
+
+                        logError({
+                              .name = "Remote build",
+                              .description = "Failed to find a machine for remote build!",
+                              .hint = hint
+                        });
+
                         std::cerr << "# decline\n";
+                    }
                     break;
                 }
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 7a2f55504..0123070d1 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -345,6 +345,7 @@ EvalState::EvalState(const Strings & _searchPath, ref<Store> store)
     , sStructuredAttrs(symbols.create("__structuredAttrs"))
     , sBuilder(symbols.create("builder"))
     , sArgs(symbols.create("args"))
+    , sContentAddressed(symbols.create("__contentAddressed"))
     , sOutputHash(symbols.create("outputHash"))
     , sOutputHashAlgo(symbols.create("outputHashAlgo"))
     , sOutputHashMode(symbols.create("outputHashMode"))
@@ -1256,10 +1257,10 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v, const Pos & po
         try {
             lambda.body->eval(*this, env2, v);
         } catch (Error & e) {
-            addErrorTrace(e, lambda.pos, "while evaluating %s", 
-              (lambda.name.set() 
-                  ? "'" + (string) lambda.name + "'" 
-                  : "anonymous lambdaction"));
+            addErrorTrace(e, lambda.pos, "while evaluating %s",
+              (lambda.name.set()
+                  ? "'" + (string) lambda.name + "'"
+                  : "anonymous lambda"));
             addErrorTrace(e, pos, "from call site%s", "");
             throw;
         }
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 8986952e3..0382298b3 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -74,6 +74,7 @@ public:
         sSystem, sOverrides, sOutputs, sOutputName, sIgnoreNulls,
         sFile, sLine, sColumn, sFunctor, sToString,
         sRight, sWrong, sStructuredAttrs, sBuilder, sArgs,
+        sContentAddressed,
         sOutputHash, sOutputHashAlgo, sOutputHashMode,
         sRecurseForDerivations,
         sDescription, sSelf, sEpsilon;
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 05d499d1f..65d36ca0e 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -583,6 +583,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
 
     PathSet context;
 
+    bool contentAddressed = false;
     std::optional<std::string> outputHash;
     std::string outputHashAlgo;
     auto ingestionMethod = FileIngestionMethod::Flat;
@@ -639,9 +640,14 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                 if (i->value->type == tNull) continue;
             }
 
+            if (i->name == state.sContentAddressed) {
+                settings.requireExperimentalFeature("ca-derivations");
+                contentAddressed = state.forceBool(*i->value, pos);
+            }
+
             /* The `args' attribute is special: it supplies the
                command-line arguments to the builder. */
-            if (i->name == state.sArgs) {
+            else if (i->name == state.sArgs) {
                 state.forceList(*i->value, pos);
                 for (unsigned int n = 0; n < i->value->listSize(); ++n) {
                     string s = state.coerceToString(posDrvName, *i->value->listElems()[n], context, true);
@@ -694,7 +700,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
             }
 
         } catch (Error & e) {
-            e.addTrace(posDrvName, 
+            e.addTrace(posDrvName,
                 "while evaluating the attribute '%1%' of the derivation '%2%'",
                 key, drvName);
             throw;
@@ -761,7 +767,10 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
         });
 
     if (outputHash) {
-        /* Handle fixed-output derivations. */
+        /* Handle fixed-output derivations.
+
+           Ignore `__contentAddressed` because fixed output derivations are
+           already content addressed. */
         if (outputs.size() != 1 || *(outputs.begin()) != "out")
             throw Error({
                 .hint = hintfmt("multiple outputs are not supported in fixed-output derivations"),
@@ -774,7 +783,7 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
         auto outPath = state.store->makeFixedOutputPath(ingestionMethod, h, drvName);
         if (!jsonObject) drv.env["out"] = state.store->printStorePath(outPath);
         drv.outputs.insert_or_assign("out", DerivationOutput {
-                .output = DerivationOutputFixed {
+                .output = DerivationOutputCAFixed {
                     .hash = FixedOutputHash {
                         .method = ingestionMethod,
                         .hash = std::move(h),
@@ -783,6 +792,19 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
         });
     }
 
+    else if (contentAddressed) {
+        HashType ht = parseHashType(outputHashAlgo);
+        for (auto & i : outputs) {
+            if (!jsonObject) drv.env[i] = hashPlaceholder(i);
+            drv.outputs.insert_or_assign(i, DerivationOutput {
+                .output = DerivationOutputCAFloating {
+                    .method = ingestionMethod,
+                    .hashType = std::move(ht),
+                },
+            });
+        }
+    }
+
     else {
         /* Compute a hash over the "masked" store derivation, which is
            the final one except that in the list of outputs, the
@@ -800,7 +822,9 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                 });
         }
 
-        Hash h = hashDerivationModulo(*state.store, Derivation(drv), true);
+        // Regular, non-CA derivation should always return a single hash and not
+        // hash per output.
+        Hash h = std::get<0>(hashDerivationModulo(*state.store, Derivation(drv), true));
 
         for (auto & i : outputs) {
             auto outPath = state.store->makeOutputPath(i, h, drvName);
diff --git a/src/libexpr/primops/fetchMercurial.cc b/src/libexpr/primops/fetchMercurial.cc
index fc2a6a1c2..cef85cfef 100644
--- a/src/libexpr/primops/fetchMercurial.cc
+++ b/src/libexpr/primops/fetchMercurial.cc
@@ -31,7 +31,7 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
                 // be both a revision or a branch/tag name.
                 auto value = state.forceStringNoCtx(*attr.value, *attr.pos);
                 if (std::regex_match(value, revRegex))
-                    rev = Hash(value, htSHA1);
+                    rev = Hash::parseAny(value, htSHA1);
                 else
                     ref = value;
             }
diff --git a/src/libfetchers/fetchers.cc b/src/libfetchers/fetchers.cc
index 28db8aa9c..9c69fc564 100644
--- a/src/libfetchers/fetchers.cc
+++ b/src/libfetchers/fetchers.cc
@@ -200,9 +200,12 @@ std::string Input::getType() const
 
 std::optional<Hash> Input::getNarHash() const
 {
-    if (auto s = maybeGetStrAttr(attrs, "narHash"))
-        // FIXME: require SRI hash.
-        return newHashAllowEmpty(*s, htSHA256);
+    if (auto s = maybeGetStrAttr(attrs, "narHash")) {
+        auto hash = s->empty() ? Hash(htSHA256) : Hash::parseSRI(*s);
+        if (hash.type != htSHA256)
+            throw UsageError("narHash must use SHA-256");
+        return hash;
+    }
     return {};
 }
 
@@ -216,7 +219,7 @@ std::optional<std::string> Input::getRef() const
 std::optional<Hash> Input::getRev() const
 {
     if (auto s = maybeGetStrAttr(attrs, "rev"))
-        return Hash(*s, htSHA1);
+        return Hash::parseAny(*s, htSHA1);
     return {};
 }
 
diff --git a/src/libfetchers/git.cc b/src/libfetchers/git.cc
index 5d38e0c2b..8b6e047f1 100644
--- a/src/libfetchers/git.cc
+++ b/src/libfetchers/git.cc
@@ -121,7 +121,7 @@ struct GitInputScheme : InputScheme
             args.push_back(*ref);
         }
 
-        if (input.getRev()) throw Error("cloning a specific revision is not implemented");
+        if (input.getRev()) throw UnimplementedError("cloning a specific revision is not implemented");
 
         args.push_back(destDir);
 
@@ -293,14 +293,14 @@ struct GitInputScheme : InputScheme
 
             if (!input.getRev())
                 input.attrs.insert_or_assign("rev",
-                    Hash(chomp(runProgram("git", true, { "-C", actualUrl, "rev-parse", *input.getRef() })), htSHA1).gitRev());
+                    Hash::parseAny(chomp(runProgram("git", true, { "-C", actualUrl, "rev-parse", *input.getRef() })), htSHA1).gitRev());
 
             repoDir = actualUrl;
 
         } else {
 
             if (auto res = getCache()->lookup(store, mutableAttrs)) {
-                auto rev2 = Hash(getStrAttr(res->first, "rev"), htSHA1);
+                auto rev2 = Hash::parseAny(getStrAttr(res->first, "rev"), htSHA1);
                 if (!input.getRev() || input.getRev() == rev2) {
                     input.attrs.insert_or_assign("rev", rev2.gitRev());
                     return makeResult(res->first, std::move(res->second));
@@ -370,7 +370,7 @@ struct GitInputScheme : InputScheme
             }
 
             if (!input.getRev())
-                input.attrs.insert_or_assign("rev", Hash(chomp(readFile(localRefFile)), htSHA1).gitRev());
+                input.attrs.insert_or_assign("rev", Hash::parseAny(chomp(readFile(localRefFile)), htSHA1).gitRev());
         }
 
         bool isShallow = chomp(runProgram("git", true, { "-C", repoDir, "rev-parse", "--is-shallow-repository" })) == "true";
diff --git a/src/libfetchers/github.cc b/src/libfetchers/github.cc
index 8bb7c2c1d..9f84ffb68 100644
--- a/src/libfetchers/github.cc
+++ b/src/libfetchers/github.cc
@@ -29,7 +29,7 @@ struct GitArchiveInputScheme : InputScheme
         if (path.size() == 2) {
         } else if (path.size() == 3) {
             if (std::regex_match(path[2], revRegex))
-                rev = Hash(path[2], htSHA1);
+                rev = Hash::parseAny(path[2], htSHA1);
             else if (std::regex_match(path[2], refRegex))
                 ref = path[2];
             else
@@ -41,7 +41,7 @@ struct GitArchiveInputScheme : InputScheme
             if (name == "rev") {
                 if (rev)
                     throw BadURL("URL '%s' contains multiple commit hashes", url.url);
-                rev = Hash(value, htSHA1);
+                rev = Hash::parseAny(value, htSHA1);
             }
             else if (name == "ref") {
                 if (!std::regex_match(value, refRegex))
@@ -191,7 +191,7 @@ struct GitHubInputScheme : GitArchiveInputScheme
             readFile(
                 store->toRealPath(
                     downloadFile(store, url, "source", false).storePath)));
-        auto rev = Hash(std::string { json["sha"] }, htSHA1);
+        auto rev = Hash::parseAny(std::string { json["sha"] }, htSHA1);
         debug("HEAD revision for '%s' is %s", url, rev.gitRev());
         return rev;
     }
@@ -235,7 +235,7 @@ struct GitLabInputScheme : GitArchiveInputScheme
             readFile(
                 store->toRealPath(
                     downloadFile(store, url, "source", false).storePath)));
-        auto rev = Hash(std::string(json[0]["id"]), htSHA1);
+        auto rev = Hash::parseAny(std::string(json[0]["id"]), htSHA1);
         debug("HEAD revision for '%s' is %s", url, rev.gitRev());
         return rev;
     }
diff --git a/src/libfetchers/indirect.cc b/src/libfetchers/indirect.cc
index 91dc83740..b981d4d8e 100644
--- a/src/libfetchers/indirect.cc
+++ b/src/libfetchers/indirect.cc
@@ -18,7 +18,7 @@ struct IndirectInputScheme : InputScheme
         if (path.size() == 1) {
         } else if (path.size() == 2) {
             if (std::regex_match(path[1], revRegex))
-                rev = Hash(path[1], htSHA1);
+                rev = Hash::parseAny(path[1], htSHA1);
             else if (std::regex_match(path[1], refRegex))
                 ref = path[1];
             else
@@ -29,7 +29,7 @@ struct IndirectInputScheme : InputScheme
             ref = path[1];
             if (!std::regex_match(path[2], revRegex))
                 throw BadURL("in flake URL '%s', '%s' is not a commit hash", url.url, path[2]);
-            rev = Hash(path[2], htSHA1);
+            rev = Hash::parseAny(path[2], htSHA1);
         } else
             throw BadURL("GitHub URL '%s' is invalid", url.url);
 
diff --git a/src/libfetchers/mercurial.cc b/src/libfetchers/mercurial.cc
index c48cb6fd1..3e76ffc4d 100644
--- a/src/libfetchers/mercurial.cc
+++ b/src/libfetchers/mercurial.cc
@@ -209,7 +209,7 @@ struct MercurialInputScheme : InputScheme
         });
 
         if (auto res = getCache()->lookup(store, mutableAttrs)) {
-            auto rev2 = Hash(getStrAttr(res->first, "rev"), htSHA1);
+            auto rev2 = Hash::parseAny(getStrAttr(res->first, "rev"), htSHA1);
             if (!input.getRev() || input.getRev() == rev2) {
                 input.attrs.insert_or_assign("rev", rev2.gitRev());
                 return makeResult(res->first, std::move(res->second));
@@ -252,7 +252,7 @@ struct MercurialInputScheme : InputScheme
             runProgram("hg", true, { "log", "-R", cacheDir, "-r", revOrRef, "--template", "{node} {rev} {branch}" }));
         assert(tokens.size() == 3);
 
-        input.attrs.insert_or_assign("rev", Hash(tokens[0], htSHA1).gitRev());
+        input.attrs.insert_or_assign("rev", Hash::parseAny(tokens[0], htSHA1).gitRev());
         auto revCount = std::stoull(tokens[1]);
         input.attrs.insert_or_assign("ref", tokens[2]);
 
diff --git a/src/libstore/binary-cache-store.cc b/src/libstore/binary-cache-store.cc
index 3d3195e03..9682db730 100644
--- a/src/libstore/binary-cache-store.cc
+++ b/src/libstore/binary-cache-store.cc
@@ -169,6 +169,7 @@ void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource
     TeeSource teeSource(narSource, *compressionSink);
     narAccessor = makeNarAccessor(teeSource);
     compressionSink->finish();
+    fileSink.flush();
     }
 
     auto now2 = std::chrono::steady_clock::now();
@@ -282,7 +283,7 @@ void BinaryCacheStore::addToStore(const ValidPathInfo & info, Source & narSource
     if (repair || !fileExists(narInfo->url)) {
         stats.narWrite++;
         upsertFile(narInfo->url,
-            std::make_shared<std::fstream>(fnTemp, std::ios_base::in),
+            std::make_shared<std::fstream>(fnTemp, std::ios_base::in | std::ios_base::binary),
             "application/x-nix-nar");
     } else
         stats.narWriteAverted++;
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index 4156cd678..76baa1a6e 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -806,8 +806,8 @@ private:
     /* RAII object to delete the chroot directory. */
     std::shared_ptr<AutoDelete> autoDelChroot;
 
-    /* Whether this is a fixed-output derivation. */
-    bool fixedOutput;
+    /* The sort of derivation we are building. */
+    DerivationType derivationType;
 
     /* Whether to run the build in a private network namespace. */
     bool privateNetwork = false;
@@ -1195,9 +1195,9 @@ void DerivationGoal::haveDerivation()
 
     parsedDrv = std::make_unique<ParsedDerivation>(drvPath, *drv);
 
-    if (parsedDrv->contentAddressed()) {
+    if (drv->type() == DerivationType::CAFloating) {
         settings.requireExperimentalFeature("ca-derivations");
-        throw Error("ca-derivations isn't implemented yet");
+        throw UnimplementedError("ca-derivations isn't implemented yet");
     }
 
 
@@ -1392,12 +1392,12 @@ void DerivationGoal::inputsRealised()
 
     debug("added input paths %s", worker.store.showPaths(inputPaths));
 
-    /* Is this a fixed-output derivation? */
-    fixedOutput = drv->isFixedOutput();
+    /* What type of derivation are we building? */
+    derivationType = drv->type();
 
     /* Don't repeat fixed-output derivations since they're already
        verified by their output hash.*/
-    nrRounds = fixedOutput ? 1 : settings.buildRepeat + 1;
+    nrRounds = derivationIsFixed(derivationType) ? 1 : settings.buildRepeat + 1;
 
     /* Okay, try to build.  Note that here we don't wait for a build
        slot to become available, since we don't need one if there is a
@@ -1783,7 +1783,7 @@ void DerivationGoal::buildDone()
             st =
                 dynamic_cast<NotDeterministic*>(&e) ? BuildResult::NotDeterministic :
                 statusOk(status) ? BuildResult::OutputRejected :
-                fixedOutput || diskFull ? BuildResult::TransientFailure :
+                derivationIsImpure(derivationType) || diskFull ? BuildResult::TransientFailure :
                 BuildResult::PermanentFailure;
         }
 
@@ -1996,7 +1996,7 @@ void DerivationGoal::startBuilder()
         else if (settings.sandboxMode == smDisabled)
             useChroot = false;
         else if (settings.sandboxMode == smRelaxed)
-            useChroot = !fixedOutput && !noChroot;
+            useChroot = !(derivationIsImpure(derivationType)) && !noChroot;
     }
 
     if (worker.store.storeDir != worker.store.realStoreDir) {
@@ -2165,7 +2165,7 @@ void DerivationGoal::startBuilder()
                 "nogroup:x:65534:\n") % sandboxGid).str());
 
         /* Create /etc/hosts with localhost entry. */
-        if (!fixedOutput)
+        if (!(derivationIsImpure(derivationType)))
             writeFile(chrootRootDir + "/etc/hosts", "127.0.0.1 localhost\n::1 localhost\n");
 
         /* Make the closure of the inputs available in the chroot,
@@ -2373,7 +2373,7 @@ void DerivationGoal::startBuilder()
            us.
         */
 
-        if (!fixedOutput)
+        if (!(derivationIsImpure(derivationType)))
             privateNetwork = true;
 
         userNamespaceSync.create();
@@ -2574,7 +2574,7 @@ void DerivationGoal::initEnv()
        derivation, tell the builder, so that for instance `fetchurl'
        can skip checking the output.  On older Nixes, this environment
        variable won't be set, so `fetchurl' will do the check. */
-    if (fixedOutput) env["NIX_OUTPUT_CHECKED"] = "1";
+    if (derivationIsFixed(derivationType)) env["NIX_OUTPUT_CHECKED"] = "1";
 
     /* *Only* if this is a fixed-output derivation, propagate the
        values of the environment variables specified in the
@@ -2585,7 +2585,7 @@ void DerivationGoal::initEnv()
        to the builder is generally impure, but the output of
        fixed-output derivations is by definition pure (since we
        already know the cryptographic hash of the output). */
-    if (fixedOutput) {
+    if (derivationIsImpure(derivationType)) {
         for (auto & i : parsedDrv->getStringsAttr("impureEnvVars").value_or(Strings()))
             env[i] = getEnv(i).value_or("");
     }
@@ -3195,7 +3195,7 @@ void DerivationGoal::runChild()
             /* Fixed-output derivations typically need to access the
                network, so give them access to /etc/resolv.conf and so
                on. */
-            if (fixedOutput) {
+            if (derivationIsImpure(derivationType)) {
                 ss.push_back("/etc/resolv.conf");
 
                 // Only use nss functions to resolve hosts and
@@ -3436,7 +3436,7 @@ void DerivationGoal::runChild()
 
                 sandboxProfile += "(import \"sandbox-defaults.sb\")\n";
 
-                if (fixedOutput)
+                if (derivationIsImpure(derivationType))
                     sandboxProfile += "(import \"sandbox-network.sb\")\n";
 
                 /* Our rwx outputs */
@@ -3721,9 +3721,22 @@ void DerivationGoal::registerOutputs()
            hash). */
         std::optional<ContentAddress> ca;
 
-        if (fixedOutput) {
-
-            FixedOutputHash outputHash = std::get<DerivationOutputFixed>(i.second.output).hash;
+        if (! std::holds_alternative<DerivationOutputInputAddressed>(i.second.output)) {
+            DerivationOutputCAFloating outputHash;
+            std::visit(overloaded {
+                [&](DerivationOutputInputAddressed doi) {
+                    assert(false); // Enclosing `if` handles this case in other branch
+                },
+                [&](DerivationOutputCAFixed dof) {
+                    outputHash = DerivationOutputCAFloating {
+                        .method = dof.hash.method,
+                        .hashType = dof.hash.hash.type,
+                    };
+                },
+                [&](DerivationOutputCAFloating dof) {
+                    outputHash = dof;
+                },
+            }, i.second.output);
 
             if (outputHash.method == FileIngestionMethod::Flat) {
                 /* The output path should be a regular file without execute permission. */
@@ -3737,12 +3750,17 @@ void DerivationGoal::registerOutputs()
             /* Check the hash. In hash mode, move the path produced by
                the derivation to its content-addressed location. */
             Hash h2 = outputHash.method == FileIngestionMethod::Recursive
-                ? hashPath(outputHash.hash.type, actualPath).first
-                : hashFile(outputHash.hash.type, actualPath);
+                ? hashPath(outputHash.hashType, actualPath).first
+                : hashFile(outputHash.hashType, actualPath);
 
             auto dest = worker.store.makeFixedOutputPath(outputHash.method, h2, i.second.path(worker.store, drv->name).name());
 
-            if (outputHash.hash != h2) {
+            // true if either floating CA, or incorrect fixed hash.
+            bool needsMove = true;
+
+            if (auto p = std::get_if<DerivationOutputCAFixed>(& i.second.output)) {
+              Hash & h = p->hash.hash;
+              if (h != h2) {
 
                 /* Throw an error after registering the path as
                    valid. */
@@ -3750,9 +3768,15 @@ void DerivationGoal::registerOutputs()
                 delayedException = std::make_exception_ptr(
                     BuildError("hash mismatch in fixed-output derivation '%s':\n  wanted: %s\n  got:    %s",
                         worker.store.printStorePath(dest),
-                        outputHash.hash.to_string(SRI, true),
+                        h.to_string(SRI, true),
                         h2.to_string(SRI, true)));
+              } else {
+                  // matched the fixed hash, so no move needed.
+                  needsMove = false;
+              }
+            }
 
+            if (needsMove) {
                 Path actualDest = worker.store.Store::toRealPath(dest);
 
                 if (worker.store.isValidPath(dest))
@@ -4852,8 +4876,17 @@ void Worker::run(const Goals & _topGoals)
             waitForInput();
         else {
             if (awake.empty() && 0 == settings.maxBuildJobs)
-                throw Error("unable to start any build; either increase '--max-jobs' "
-                            "or enable remote builds");
+            {
+                if (getMachines().empty())
+                   throw Error("unable to start any build; either increase '--max-jobs' "
+                            "or enable remote builds."
+                            "\nhttps://nixos.org/nix/manual/#chap-distributed-builds");
+                else
+                   throw Error("unable to start any build; remote machines may not have "
+                            "all required system features."
+                            "\nhttps://nixos.org/nix/manual/#chap-distributed-builds");
+
+            }
             assert(!awake.empty());
         }
     }
diff --git a/src/libstore/content-address.cc b/src/libstore/content-address.cc
index f83b98a98..0885c3d0e 100644
--- a/src/libstore/content-address.cc
+++ b/src/libstore/content-address.cc
@@ -1,4 +1,6 @@
+#include "args.hh"
 #include "content-address.hh"
+#include "split.hh"
 
 namespace nix {
 
@@ -24,10 +26,6 @@ std::string makeFixedOutputCA(FileIngestionMethod method, const Hash & hash)
         + hash.to_string(Base32, true);
 }
 
-// FIXME Put this somewhere?
-template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
-template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
-
 std::string renderContentAddress(ContentAddress ca) {
     return std::visit(overloaded {
         [](TextHash th) {
@@ -40,38 +38,46 @@ std::string renderContentAddress(ContentAddress ca) {
 }
 
 ContentAddress parseContentAddress(std::string_view rawCa) {
-    auto prefixSeparator = rawCa.find(':');
-    if (prefixSeparator != string::npos) {
-        auto prefix = string(rawCa, 0, prefixSeparator);
-        if (prefix == "text") {
-            auto hashTypeAndHash = rawCa.substr(prefixSeparator+1, string::npos);
-            Hash hash = Hash(string(hashTypeAndHash));
-            if (hash.type != htSHA256) {
-                throw Error("parseContentAddress: the text hash should have type SHA256");
-            }
-            return TextHash { hash };
-        } else if (prefix == "fixed") {
-            // This has to be an inverse of makeFixedOutputCA
-            auto methodAndHash = rawCa.substr(prefixSeparator+1, string::npos);
-            if (methodAndHash.substr(0,2) == "r:") {
-                std::string_view hashRaw = methodAndHash.substr(2,string::npos);
-                return FixedOutputHash {
-                    .method = FileIngestionMethod::Recursive,
-                    .hash = Hash(string(hashRaw)),
-                };
-            } else {
-                std::string_view hashRaw = methodAndHash;
-                return FixedOutputHash {
-                    .method = FileIngestionMethod::Flat,
-                    .hash = Hash(string(hashRaw)),
-                };
-            }
-        } else {
-            throw Error("parseContentAddress: format not recognized; has to be text or fixed");
-        }
-    } else {
-        throw Error("Not a content address because it lacks an appropriate prefix");
+    auto rest = rawCa;
+
+    std::string_view prefix;
+    {
+        auto optPrefix = splitPrefixTo(rest, ':');
+        if (!optPrefix)
+            throw UsageError("not a content address because it is not in the form '<prefix>:<rest>': %s", rawCa);
+        prefix = *optPrefix;
     }
+
+    auto parseHashType_ = [&](){
+        auto hashTypeRaw = splitPrefixTo(rest, ':');
+        if (!hashTypeRaw)
+            throw UsageError("content address hash must be in form '<algo>:<hash>', but found: %s", rawCa);
+        HashType hashType = parseHashType(*hashTypeRaw);
+        return std::move(hashType);
+    };
+
+    // Switch on prefix
+    if (prefix == "text") {
+        // No parsing of the method, "text" only support flat.
+        HashType hashType = parseHashType_();
+        if (hashType != htSHA256)
+            throw Error("text content address hash should use %s, but instead uses %s",
+                printHashType(htSHA256), printHashType(hashType));
+        return TextHash {
+            .hash = Hash::parseNonSRIUnprefixed(rest, std::move(hashType)),
+        };
+    } else if (prefix == "fixed") {
+        // Parse method
+        auto method = FileIngestionMethod::Flat;
+        if (splitPrefix(rest, "r:"))
+            method = FileIngestionMethod::Recursive;
+        HashType hashType = parseHashType_();
+        return FixedOutputHash {
+            .method = method,
+            .hash = Hash::parseNonSRIUnprefixed(rest, std::move(hashType)),
+        };
+    } else
+        throw UsageError("content address prefix '%s' is unrecognized. Recogonized prefixes are 'text' or 'fixed'", prefix);
 };
 
 std::optional<ContentAddress> parseContentAddressOpt(std::string_view rawCaOpt) {
diff --git a/src/libstore/daemon.cc b/src/libstore/daemon.cc
index b9a750425..5e568fc94 100644
--- a/src/libstore/daemon.cc
+++ b/src/libstore/daemon.cc
@@ -698,7 +698,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
         auto deriver = readString(from);
         if (deriver != "")
             info.deriver = store->parseStorePath(deriver);
-        info.narHash = Hash(readString(from), htSHA256);
+        info.narHash = Hash::parseAny(readString(from), htSHA256);
         info.references = readStorePaths<StorePathSet>(*store, from);
         from >> info.registrationTime >> info.narSize >> info.ultimate;
         info.sigs = readStrings<StringSet>(from);
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index 7d0a5abeb..68b081058 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -7,23 +7,54 @@
 
 namespace nix {
 
-// FIXME Put this somewhere?
-template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
-template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
-
-StorePath DerivationOutput::path(const Store & store, std::string_view drvName) const
+std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::string_view drvName) const
 {
     return std::visit(overloaded {
-        [](DerivationOutputInputAddressed doi) {
-            return doi.path;
+        [](DerivationOutputInputAddressed doi) -> std::optional<StorePath> {
+            return { doi.path };
+        },
+        [&](DerivationOutputCAFixed dof) -> std::optional<StorePath> {
+            return {
+                store.makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName)
+            };
+        },
+        [](DerivationOutputCAFloating dof) -> std::optional<StorePath> {
+            return std::nullopt;
         },
-        [&](DerivationOutputFixed dof) {
-            return store.makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName);
-        }
     }, output);
 }
 
 
+bool derivationIsCA(DerivationType dt) {
+    switch (dt) {
+    case DerivationType::InputAddressed: return false;
+    case DerivationType::CAFixed: return true;
+    case DerivationType::CAFloating: return true;
+    };
+    // Since enums can have non-variant values, but making a `default:` would
+    // disable exhaustiveness warnings.
+    assert(false);
+}
+
+bool derivationIsFixed(DerivationType dt) {
+    switch (dt) {
+    case DerivationType::InputAddressed: return false;
+    case DerivationType::CAFixed: return true;
+    case DerivationType::CAFloating: return false;
+    };
+    assert(false);
+}
+
+bool derivationIsImpure(DerivationType dt) {
+    switch (dt) {
+    case DerivationType::InputAddressed: return false;
+    case DerivationType::CAFixed: return true;
+    case DerivationType::CAFloating: return false;
+    };
+    assert(false);
+}
+
+
 bool BasicDerivation::isBuiltin() const
 {
     return string(builder, 0, 8) == "builtin:";
@@ -123,14 +154,22 @@ static DerivationOutput parseDerivationOutput(const Store & store, std::istrings
         }
         const HashType hashType = parseHashType(hashAlgo);
 
-        return DerivationOutput {
-            .output = DerivationOutputFixed {
-                .hash = FixedOutputHash {
-                    .method = std::move(method),
-                    .hash = Hash(hash, hashType),
-                },
-            }
-        };
+        return hash != ""
+            ? DerivationOutput {
+                  .output = DerivationOutputCAFixed {
+                      .hash = FixedOutputHash {
+                          .method = std::move(method),
+                          .hash = Hash::parseNonSRIUnprefixed(hash, hashType),
+                      },
+                  }
+               }
+            : (settings.requireExperimentalFeature("ca-derivations"),
+              DerivationOutput {
+                  .output =  DerivationOutputCAFloating {
+                      .method = std::move(method),
+                      .hashType = std::move(hashType),
+                  },
+              });
     } else
         return DerivationOutput {
             .output = DerivationOutputInputAddressed {
@@ -278,13 +317,20 @@ string Derivation::unparse(const Store & store, bool maskOutputs,
         if (first) first = false; else s += ',';
         s += '('; printUnquotedString(s, i.first);
         s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(i.second.path(store, name)));
-        if (auto hash = std::get_if<DerivationOutputFixed>(&i.second.output)) {
-            s += ','; printUnquotedString(s, hash->hash.printMethodAlgo());
-            s += ','; printUnquotedString(s, hash->hash.hash.to_string(Base16, false));
-        } else {
-            s += ','; printUnquotedString(s, "");
-            s += ','; printUnquotedString(s, "");
-        }
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed doi) {
+                s += ','; printUnquotedString(s, "");
+                s += ','; printUnquotedString(s, "");
+            },
+            [&](DerivationOutputCAFixed dof) {
+                s += ','; printUnquotedString(s, dof.hash.printMethodAlgo());
+                s += ','; printUnquotedString(s, dof.hash.hash.to_string(Base16, false));
+            },
+            [&](DerivationOutputCAFloating dof) {
+                s += ','; printUnquotedString(s, makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
+                s += ','; printUnquotedString(s, "");
+            },
+        }, i.second.output);
         s += ')';
     }
 
@@ -336,60 +382,134 @@ bool isDerivation(const string & fileName)
 }
 
 
-bool BasicDerivation::isFixedOutput() const
+DerivationType BasicDerivation::type() const
 {
-    return outputs.size() == 1 &&
-        outputs.begin()->first == "out" &&
-        std::holds_alternative<DerivationOutputFixed>(outputs.begin()->second.output);
+    std::set<std::string_view> inputAddressedOutputs, fixedCAOutputs, floatingCAOutputs;
+    std::optional<HashType> floatingHashType;
+    for (auto & i : outputs) {
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed _) {
+               inputAddressedOutputs.insert(i.first);
+            },
+            [&](DerivationOutputCAFixed _) {
+                fixedCAOutputs.insert(i.first);
+            },
+            [&](DerivationOutputCAFloating dof) {
+                floatingCAOutputs.insert(i.first);
+                if (!floatingHashType) {
+                    floatingHashType = dof.hashType;
+                } else {
+                    if (*floatingHashType != dof.hashType)
+                        throw Error("All floating outputs must use the same hash type");
+                }
+            },
+        }, i.second.output);
+    }
+
+    if (inputAddressedOutputs.empty() && fixedCAOutputs.empty() && floatingCAOutputs.empty()) {
+        throw Error("Must have at least one output");
+    } else if (! inputAddressedOutputs.empty() && fixedCAOutputs.empty() && floatingCAOutputs.empty()) {
+        return DerivationType::InputAddressed;
+    } else if (inputAddressedOutputs.empty() && ! fixedCAOutputs.empty() && floatingCAOutputs.empty()) {
+        if (fixedCAOutputs.size() > 1)
+            // FIXME: Experimental feature?
+            throw Error("Only one fixed output is allowed for now");
+        if (*fixedCAOutputs.begin() != "out")
+            throw Error("Single fixed output must be named \"out\"");
+        return DerivationType::CAFixed;
+    } else if (inputAddressedOutputs.empty() && fixedCAOutputs.empty() && ! floatingCAOutputs.empty()) {
+        return DerivationType::CAFloating;
+    } else {
+        throw Error("Can't mix derivation output types");
+    }
 }
 
 
 DrvHashes drvHashes;
 
+/* pathDerivationModulo and hashDerivationModulo are mutually recursive
+ */
+
+/* Look up the derivation by value and memoize the
+   `hashDerivationModulo` call.
+ */
+static const DrvHashModulo & pathDerivationModulo(Store & store, const StorePath & drvPath)
+{
+    auto h = drvHashes.find(drvPath);
+    if (h == drvHashes.end()) {
+        assert(store.isValidPath(drvPath));
+        // Cache it
+        h = drvHashes.insert_or_assign(
+            drvPath,
+            hashDerivationModulo(
+                store,
+                store.readDerivation(drvPath),
+                false)).first;
+    }
+    return h->second;
+}
 
-/* Returns the hash of a derivation modulo fixed-output
-   subderivations.  A fixed-output derivation is a derivation with one
-   output (`out') for which an expected hash and hash algorithm are
-   specified (using the `outputHash' and `outputHashAlgo'
-   attributes).  We don't want changes to such derivations to
-   propagate upwards through the dependency graph, changing output
-   paths everywhere.
-
-   For instance, if we change the url in a call to the `fetchurl'
-   function, we do not want to rebuild everything depending on it
-   (after all, (the hash of) the file being downloaded is unchanged).
-   So the *output paths* should not change.  On the other hand, the
-   *derivation paths* should change to reflect the new dependency
-   graph.
-
-   That's what this function does: it returns a hash which is just the
-   hash of the derivation ATerm, except that any input derivation
-   paths have been replaced by the result of a recursive call to this
-   function, and that for fixed-output derivations we return a hash of
-   its output path. */
-Hash hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs)
+/* See the header for interface details. These are the implementation details.
+
+   For fixed-output derivations, each hash in the map is not the
+   corresponding output's content hash, but a hash of that hash along
+   with other constant data. The key point is that the value is a pure
+   function of the output's contents, and there are no preimage attacks
+   either spoofing an output's contents for a derivation, or
+   spoofing a derivation for an output's contents.
+
+   For regular derivations, it looks up each subderivation from its hash
+   and recurs. If the subderivation is also regular, it simply
+   substitutes the derivation path with its hash. If the subderivation
+   is fixed-output, however, it takes each output hash and pretends it
+   is a derivation hash producing a single "out" output. This is so we
+   don't leak the provenance of fixed outputs, reducing pointless cache
+   misses as the build itself won't know this.
+ */
+DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs)
 {
     /* Return a fixed hash for fixed-output derivations. */
-    if (drv.isFixedOutput()) {
-        DerivationOutputs::const_iterator i = drv.outputs.begin();
-        auto hash = std::get<DerivationOutputFixed>(i->second.output);
-        return hashString(htSHA256, "fixed:out:"
-            + hash.hash.printMethodAlgo() + ":"
-            + hash.hash.hash.to_string(Base16, false) + ":"
-            + store.printStorePath(i->second.path(store, drv.name)));
+    switch (drv.type()) {
+    case DerivationType::CAFloating:
+        throw Error("Regular input-addressed derivations are not yet allowed to depend on CA derivations");
+    case DerivationType::CAFixed: {
+        std::map<std::string, Hash> outputHashes;
+        for (const auto & i : drv.outputs) {
+            auto & dof = std::get<DerivationOutputCAFixed>(i.second.output);
+            auto hash = hashString(htSHA256, "fixed:out:"
+                + dof.hash.printMethodAlgo() + ":"
+                + dof.hash.hash.to_string(Base16, false) + ":"
+                + store.printStorePath(i.second.path(store, drv.name)));
+            outputHashes.insert_or_assign(i.first, std::move(hash));
+        }
+        return outputHashes;
+    }
+    case DerivationType::InputAddressed:
+        break;
     }
 
     /* For other derivations, replace the inputs paths with recursive
-       calls to this function.*/
+       calls to this function. */
     std::map<std::string, StringSet> inputs2;
     for (auto & i : drv.inputDrvs) {
-        auto h = drvHashes.find(i.first);
-        if (h == drvHashes.end()) {
-            assert(store.isValidPath(i.first));
-            h = drvHashes.insert_or_assign(i.first, hashDerivationModulo(store,
-                store.readDerivation(i.first), false)).first;
-        }
-        inputs2.insert_or_assign(h->second.to_string(Base16, false), i.second);
+        const auto & res = pathDerivationModulo(store, i.first);
+        std::visit(overloaded {
+            // Regular non-CA derivation, replace derivation
+            [&](Hash drvHash) {
+                inputs2.insert_or_assign(drvHash.to_string(Base16, false), i.second);
+            },
+            // CA derivation's output hashes
+            [&](CaOutputHashes outputHashes) {
+                std::set<std::string> justOut = { "out" };
+                for (auto & output : i.second) {
+                    /* Put each one in with a single "out" output.. */
+                    const auto h = outputHashes.at(output);
+                    inputs2.insert_or_assign(
+                        h.to_string(Base16, false),
+                        justOut);
+                }
+            },
+        }, res);
     }
 
     return hashString(htSHA256, drv.unparse(store, maskOutputs, &inputs2));
@@ -431,14 +551,22 @@ static DerivationOutput readDerivationOutput(Source & in, const Store & store)
             hashAlgo = string(hashAlgo, 2);
         }
         auto hashType = parseHashType(hashAlgo);
-        return DerivationOutput {
-            .output = DerivationOutputFixed {
-                .hash = FixedOutputHash {
-                    .method = std::move(method),
-                    .hash = Hash(hash, hashType),
-                },
-            }
-        };
+        return hash != ""
+            ? DerivationOutput {
+                  .output = DerivationOutputCAFixed {
+                      .hash = FixedOutputHash {
+                          .method = std::move(method),
+                          .hash = Hash::parseNonSRIUnprefixed(hash, hashType),
+                      },
+                  }
+               }
+            : (settings.requireExperimentalFeature("ca-derivations"),
+              DerivationOutput {
+                  .output = DerivationOutputCAFloating {
+                      .method = std::move(method),
+                      .hashType = std::move(hashType),
+                  },
+              });
     } else
         return DerivationOutput {
             .output = DerivationOutputInputAddressed {
@@ -498,12 +626,19 @@ void writeDerivation(Sink & out, const Store & store, const BasicDerivation & dr
     for (auto & i : drv.outputs) {
         out << i.first
             << store.printStorePath(i.second.path(store, drv.name));
-        if (auto hash = std::get_if<DerivationOutputFixed>(&i.second.output)) {
-            out << hash->hash.printMethodAlgo()
-                << hash->hash.hash.to_string(Base16, false);
-        } else {
-            out << "" << "";
-        }
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed doi) {
+                out << "" << "";
+            },
+            [&](DerivationOutputCAFixed dof) {
+                out << dof.hash.printMethodAlgo()
+                    << dof.hash.hash.to_string(Base16, false);
+            },
+            [&](DerivationOutputCAFloating dof) {
+                out << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
+                    << "";
+            },
+        }, i.second.output);
     }
     writeStorePaths(store, out, drv.inputSrcs);
     out << drv.platform << drv.builder << drv.args;
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 133ffe50e..14e0e947a 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -6,6 +6,7 @@
 #include "content-address.hh"
 
 #include <map>
+#include <variant>
 
 
 namespace nix {
@@ -13,20 +14,46 @@ namespace nix {
 
 /* Abstract syntax of derivations. */
 
+/* The traditional non-fixed-output derivation type. */
 struct DerivationOutputInputAddressed
 {
+    /* Will need to become `std::optional<StorePath>` once input-addressed
+       derivations are allowed to depend on cont-addressed derivations */
     StorePath path;
 };
 
-struct DerivationOutputFixed
+/* Fixed-output derivations, whose output paths are content addressed
+   according to that fixed output. */
+struct DerivationOutputCAFixed
 {
     FixedOutputHash hash; /* hash used for expected hash computation */
 };
 
+/* Floating-output derivations, whose output paths are content addressed, but
+   not fixed, and so are dynamically calculated from whatever the output ends
+   up being. */
+struct DerivationOutputCAFloating
+{
+    /* information used for expected hash computation */
+    FileIngestionMethod method;
+    HashType hashType;
+};
+
 struct DerivationOutput
 {
-    std::variant<DerivationOutputInputAddressed, DerivationOutputFixed> output;
-    StorePath path(const Store & store, std::string_view drvName) const;
+    std::variant<
+        DerivationOutputInputAddressed,
+        DerivationOutputCAFixed,
+        DerivationOutputCAFloating
+    > output;
+    std::optional<HashType> hashAlgoOpt(const Store & store) const;
+    std::optional<StorePath> pathOpt(const Store & store, std::string_view drvName) const;
+    /* DEPRECATED: Remove after CA drvs are fully implemented */
+    StorePath path(const Store & store, std::string_view drvName) const {
+        auto p = pathOpt(store, drvName);
+        if (!p) throw UnimplementedError("floating content-addressed derivations are not yet implemented");
+        return *p;
+    }
 };
 
 typedef std::map<string, DerivationOutput> DerivationOutputs;
@@ -37,6 +64,25 @@ typedef std::map<StorePath, StringSet> DerivationInputs;
 
 typedef std::map<string, string> StringPairs;
 
+enum struct DerivationType : uint8_t {
+    InputAddressed,
+    CAFixed,
+    CAFloating,
+};
+
+/* Do the outputs of the derivation have paths calculated from their content,
+   or from the derivation itself? */
+bool derivationIsCA(DerivationType);
+
+/* Is the content of the outputs fixed a-priori via a hash? Never true for
+   non-CA derivations. */
+bool derivationIsFixed(DerivationType);
+
+/* Is the derivation impure and needs to access non-deterministic resources, or
+   pure and can be sandboxed? Note that whether or not we actually sandbox the
+   derivation is controlled separately. Never true for non-CA derivations. */
+bool derivationIsImpure(DerivationType);
+
 struct BasicDerivation
 {
     DerivationOutputs outputs; /* keyed on symbolic IDs */
@@ -53,7 +99,7 @@ struct BasicDerivation
     bool isBuiltin() const;
 
     /* Return true iff this is a fixed-output derivation. */
-    bool isFixedOutput() const;
+    DerivationType type() const;
 
     /* Return the output paths of a derivation. */
     StorePathSet outputPaths(const Store & store) const;
@@ -90,10 +136,42 @@ Derivation readDerivation(const Store & store, const Path & drvPath, std::string
 // FIXME: remove
 bool isDerivation(const string & fileName);
 
-Hash hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs);
+// known CA drv's output hashes, current just for fixed-output derivations
+// whose output hashes are always known since they are fixed up-front.
+typedef std::map<std::string, Hash> CaOutputHashes;
+
+typedef std::variant<
+    Hash, // regular DRV normalized hash
+    CaOutputHashes
+> DrvHashModulo;
+
+/* Returns hashes with the details of fixed-output subderivations
+   expunged.
+
+   A fixed-output derivation is a derivation whose outputs have a
+   specified content hash and hash algorithm. (Currently they must have
+   exactly one output (`out'), which is specified using the `outputHash'
+   and `outputHashAlgo' attributes, but the algorithm doesn't assume
+   this.) We don't want changes to such derivations to propagate upwards
+   through the dependency graph, changing output paths everywhere.
+
+   For instance, if we change the url in a call to the `fetchurl'
+   function, we do not want to rebuild everything depending on it---after
+   all, (the hash of) the file being downloaded is unchanged.  So the
+   *output paths* should not change. On the other hand, the *derivation
+   paths* should change to reflect the new dependency graph.
+
+   For fixed-output derivations, this returns a map from the name of
+   each output to its hash, unique up to the output's contents.
+
+   For regular derivations, it returns a single hash of the derivation
+   ATerm, after subderivations have been likewise expunged from that
+   derivation.
+ */
+DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool maskOutputs);
 
 /* Memoisation of hashDerivationModulo(). */
-typedef std::map<StorePath, Hash> DrvHashes;
+typedef std::map<StorePath, DrvHashModulo> DrvHashes;
 
 extern DrvHashes drvHashes; // FIXME: global, not thread-safe
 
diff --git a/src/libstore/legacy-ssh-store.cc b/src/libstore/legacy-ssh-store.cc
index 5d7566121..c6eeab548 100644
--- a/src/libstore/legacy-ssh-store.cc
+++ b/src/libstore/legacy-ssh-store.cc
@@ -113,7 +113,7 @@ struct LegacySSHStore : public Store
 
             if (GET_PROTOCOL_MINOR(conn->remoteVersion) >= 4) {
                 auto s = readString(conn->from);
-                info->narHash = s.empty() ? std::optional<Hash>{} : Hash{s};
+                info->narHash = s.empty() ? std::optional<Hash>{} : Hash::parseAnyPrefixed(s);
                 info->ca = parseContentAddressOpt(readString(conn->from));
                 info->sigs = readStrings<StringSet>(conn->from);
             }
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index f908f7d67..3c66a4dfd 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -544,11 +544,8 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
     std::string drvName(drvPath.name());
     drvName = string(drvName, 0, drvName.size() - drvExtension.size());
 
-    auto check = [&](const StorePath & expected, const StorePath & actual, const std::string & varName)
+    auto envHasRightPath = [&](const StorePath & actual, const std::string & varName)
     {
-        if (actual != expected)
-            throw Error("derivation '%s' has incorrect output '%s', should be '%s'",
-                printStorePath(drvPath), printStorePath(actual), printStorePath(expected));
         auto j = drv.env.find(varName);
         if (j == drv.env.end() || parseStorePath(j->second) != actual)
             throw Error("derivation '%s' has incorrect environment variable '%s', should be '%s'",
@@ -556,16 +553,34 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
     };
 
 
-    if (drv.isFixedOutput()) {
-        DerivationOutputs::const_iterator out = drv.outputs.find("out");
-        if (out == drv.outputs.end())
-            throw Error("derivation '%s' does not have an output named 'out'", printStorePath(drvPath));
-    }
+    // Don't need the answer, but do this anyways to assert is proper
+    // combination. The code below is more general and naturally allows
+    // combinations that are currently prohibited.
+    drv.type();
 
-    else {
-        Hash h = hashDerivationModulo(*this, drv, true);
-        for (auto & i : drv.outputs)
-            check(makeOutputPath(i.first, h, drvName), i.second.path(*this, drv.name), i.first);
+    std::optional<Hash> h;
+    for (auto & i : drv.outputs) {
+        std::visit(overloaded {
+            [&](DerivationOutputInputAddressed doia) {
+                if (!h) {
+                    // somewhat expensive so we do lazily
+                    auto temp = hashDerivationModulo(*this, drv, true);
+                    h = std::get<Hash>(temp);
+                }
+                StorePath recomputed = makeOutputPath(i.first, *h, drvName);
+                if (doia.path != recomputed)
+                    throw Error("derivation '%s' has incorrect output '%s', should be '%s'",
+                        printStorePath(drvPath), printStorePath(doia.path), printStorePath(recomputed));
+                envHasRightPath(doia.path, i.first);
+            },
+            [&](DerivationOutputCAFixed dof) {
+                StorePath path = makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName);
+                envHasRightPath(path, i.first);
+            },
+            [&](DerivationOutputCAFloating _) {
+                throw UnimplementedError("floating CA output derivations are not yet implemented");
+            },
+        }, i.second.output);
     }
 }
 
@@ -640,7 +655,7 @@ void LocalStore::queryPathInfoUncached(const StorePath & path,
             info->id = useQueryPathInfo.getInt(0);
 
             try {
-                info->narHash = Hash(useQueryPathInfo.getStr(1));
+                info->narHash = Hash::parseAnyPrefixed(useQueryPathInfo.getStr(1));
             } catch (BadHash & e) {
                 throw Error("in valid-path entry for '%s': %s", printStorePath(path), e.what());
             }
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index 7f1b62f26..0ae1ceaad 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -4,6 +4,7 @@
 #include "local-store.hh"
 #include "store-api.hh"
 #include "thread-pool.hh"
+#include "topo-sort.hh"
 
 
 namespace nix {
@@ -112,7 +113,7 @@ std::optional<ContentAddress> getDerivationCA(const BasicDerivation & drv)
 {
     auto out = drv.outputs.find("out");
     if (out != drv.outputs.end()) {
-        if (auto v = std::get_if<DerivationOutputFixed>(&out->second.output))
+        if (auto v = std::get_if<DerivationOutputCAFixed>(&out->second.output))
             return v->hash;
     }
     return std::nullopt;
@@ -256,41 +257,21 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
 
 StorePaths Store::topoSortPaths(const StorePathSet & paths)
 {
-    StorePaths sorted;
-    StorePathSet visited, parents;
-
-    std::function<void(const StorePath & path, const StorePath * parent)> dfsVisit;
-
-    dfsVisit = [&](const StorePath & path, const StorePath * parent) {
-        if (parents.count(path))
-            throw BuildError("cycle detected in the references of '%s' from '%s'",
-                printStorePath(path), printStorePath(*parent));
-
-        if (!visited.insert(path).second) return;
-        parents.insert(path);
-
-        StorePathSet references;
-        try {
-            references = queryPathInfo(path)->references;
-        } catch (InvalidPath &) {
-        }
-
-        for (auto & i : references)
-            /* Don't traverse into paths that don't exist.  That can
-               happen due to substitutes for non-existent paths. */
-            if (i != path && paths.count(i))
-                dfsVisit(i, &path);
-
-        sorted.push_back(path);
-        parents.erase(path);
-    };
-
-    for (auto & i : paths)
-        dfsVisit(i, nullptr);
-
-    std::reverse(sorted.begin(), sorted.end());
-
-    return sorted;
+    return topoSort(paths,
+        {[&](const StorePath & path) {
+            StorePathSet references;
+            try {
+                references = queryPathInfo(path)->references;
+            } catch (InvalidPath &) {
+            }
+            return references;
+        }},
+        {[&](const StorePath & path, const StorePath & parent) {
+            return BuildError(
+                "cycle detected in the references of '%s' from '%s'",
+                printStorePath(path),
+                printStorePath(parent));
+        }});
 }
 
 
diff --git a/src/libstore/nar-info-disk-cache.cc b/src/libstore/nar-info-disk-cache.cc
index 9ddb9957f..92da14e23 100644
--- a/src/libstore/nar-info-disk-cache.cc
+++ b/src/libstore/nar-info-disk-cache.cc
@@ -193,9 +193,9 @@ public:
             narInfo->url = queryNAR.getStr(2);
             narInfo->compression = queryNAR.getStr(3);
             if (!queryNAR.isNull(4))
-                narInfo->fileHash = Hash(queryNAR.getStr(4));
+                narInfo->fileHash = Hash::parseAnyPrefixed(queryNAR.getStr(4));
             narInfo->fileSize = queryNAR.getInt(5);
-            narInfo->narHash = Hash(queryNAR.getStr(6));
+            narInfo->narHash = Hash::parseAnyPrefixed(queryNAR.getStr(6));
             narInfo->narSize = queryNAR.getInt(7);
             for (auto & r : tokenizeString<Strings>(queryNAR.getStr(8), " "))
                 narInfo->references.insert(StorePath(r));
diff --git a/src/libstore/nar-info.cc b/src/libstore/nar-info.cc
index ca471463c..5812aa4ac 100644
--- a/src/libstore/nar-info.cc
+++ b/src/libstore/nar-info.cc
@@ -12,7 +12,7 @@ NarInfo::NarInfo(const Store & store, const std::string & s, const std::string &
 
     auto parseHashField = [&](const string & s) {
         try {
-            return Hash(s);
+            return Hash::parseAnyPrefixed(s);
         } catch (BadHash &) {
             throw corrupt();
         }
diff --git a/src/libstore/parsed-derivations.cc b/src/libstore/parsed-derivations.cc
index c7797b730..24f848e46 100644
--- a/src/libstore/parsed-derivations.cc
+++ b/src/libstore/parsed-derivations.cc
@@ -117,9 +117,4 @@ bool ParsedDerivation::substitutesAllowed() const
     return getBoolAttr("allowSubstitutes", true);
 }
 
-bool ParsedDerivation::contentAddressed() const
-{
-    return getBoolAttr("__contentAddressed", false);
-}
-
 }
diff --git a/src/libstore/parsed-derivations.hh b/src/libstore/parsed-derivations.hh
index 0b8e8d031..6ee172d81 100644
--- a/src/libstore/parsed-derivations.hh
+++ b/src/libstore/parsed-derivations.hh
@@ -34,8 +34,6 @@ public:
     bool willBuildLocally() const;
 
     bool substitutesAllowed() const;
-
-    bool contentAddressed() const;
 };
 
 }
diff --git a/src/libstore/path-info.hh b/src/libstore/path-info.hh
new file mode 100644
index 000000000..2a015ea3c
--- /dev/null
+++ b/src/libstore/path-info.hh
@@ -0,0 +1,111 @@
+#pragma once
+
+#include "path.hh"
+#include "hash.hh"
+#include "content-address.hh"
+
+#include <string>
+#include <optional>
+
+namespace nix {
+
+
+class Store;
+
+
+struct SubstitutablePathInfo
+{
+    std::optional<StorePath> deriver;
+    StorePathSet references;
+    uint64_t downloadSize; /* 0 = unknown or inapplicable */
+    uint64_t narSize; /* 0 = unknown */
+};
+
+typedef std::map<StorePath, SubstitutablePathInfo> SubstitutablePathInfos;
+
+
+struct ValidPathInfo
+{
+    StorePath path;
+    std::optional<StorePath> deriver;
+    // TODO document this
+    std::optional<Hash> narHash;
+    StorePathSet references;
+    time_t registrationTime = 0;
+    uint64_t narSize = 0; // 0 = unknown
+    uint64_t id; // internal use only
+
+    /* Whether the path is ultimately trusted, that is, it's a
+       derivation output that was built locally. */
+    bool ultimate = false;
+
+    StringSet sigs; // note: not necessarily verified
+
+    /* If non-empty, an assertion that the path is content-addressed,
+       i.e., that the store path is computed from a cryptographic hash
+       of the contents of the path, plus some other bits of data like
+       the "name" part of the path. Such a path doesn't need
+       signatures, since we don't have to trust anybody's claim that
+       the path is the output of a particular derivation. (In the
+       extensional store model, we have to trust that the *contents*
+       of an output path of a derivation were actually produced by
+       that derivation. In the intensional model, we have to trust
+       that a particular output path was produced by a derivation; the
+       path then implies the contents.)
+
+       Ideally, the content-addressability assertion would just be a Boolean,
+       and the store path would be computed from the name component, ‘narHash’
+       and ‘references’. However, we support many types of content addresses.
+    */
+    std::optional<ContentAddress> ca;
+
+    bool operator == (const ValidPathInfo & i) const
+    {
+        return
+            path == i.path
+            && narHash == i.narHash
+            && references == i.references;
+    }
+
+    /* Return a fingerprint of the store path to be used in binary
+       cache signatures. It contains the store path, the base-32
+       SHA-256 hash of the NAR serialisation of the path, the size of
+       the NAR, and the sorted references. The size field is strictly
+       speaking superfluous, but might prevent endless/excessive data
+       attacks. */
+    std::string fingerprint(const Store & store) const;
+
+    void sign(const Store & store, const SecretKey & secretKey);
+
+    /* Return true iff the path is verifiably content-addressed. */
+    bool isContentAddressed(const Store & store) const;
+
+    /* Functions to view references + hasSelfReference as one set, mainly for
+       compatibility's sake. */
+    StorePathSet referencesPossiblyToSelf() const;
+    void insertReferencePossiblyToSelf(StorePath && ref);
+    void setReferencesPossiblyToSelf(StorePathSet && refs);
+
+    static const size_t maxSigs = std::numeric_limits<size_t>::max();
+
+    /* Return the number of signatures on this .narinfo that were
+       produced by one of the specified keys, or maxSigs if the path
+       is content-addressed. */
+    size_t checkSignatures(const Store & store, const PublicKeys & publicKeys) const;
+
+    /* Verify a single signature. */
+    bool checkSignature(const Store & store, const PublicKeys & publicKeys, const std::string & sig) const;
+
+    Strings shortRefs() const;
+
+    ValidPathInfo(const ValidPathInfo & other) = default;
+
+    ValidPathInfo(StorePath && path) : path(std::move(path)) { };
+    ValidPathInfo(const StorePath & path) : path(path) { };
+
+    virtual ~ValidPathInfo() { }
+};
+
+typedef list<ValidPathInfo> ValidPathInfos;
+
+}
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 0c65bcd29..33d1e431b 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -422,7 +422,7 @@ void RemoteStore::queryPathInfoUncached(const StorePath & path,
             info = std::make_shared<ValidPathInfo>(StorePath(path));
             auto deriver = readString(conn->from);
             if (deriver != "") info->deriver = parseStorePath(deriver);
-            info->narHash = Hash(readString(conn->from), htSHA256);
+            info->narHash = Hash::parseAny(readString(conn->from), htSHA256);
             info->references = readStorePaths<StorePathSet>(*this, conn->from);
             conn->from >> info->registrationTime >> info->narSize;
             if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 16) {
diff --git a/src/libstore/s3-binary-cache-store.cc b/src/libstore/s3-binary-cache-store.cc
index 67935f3ba..a0a446bd3 100644
--- a/src/libstore/s3-binary-cache-store.cc
+++ b/src/libstore/s3-binary-cache-store.cc
@@ -266,6 +266,10 @@ struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
         const std::string & mimeType,
         const std::string & contentEncoding)
     {
+        istream->seekg(0, istream->end);
+        auto size = istream->tellg();
+        istream->seekg(0, istream->beg);
+
         auto maxThreads = std::thread::hardware_concurrency();
 
         static std::shared_ptr<Aws::Utils::Threading::PooledThreadExecutor>
@@ -343,10 +347,11 @@ struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
             std::chrono::duration_cast<std::chrono::milliseconds>(now2 - now1)
                 .count();
 
-        printInfo("uploaded 's3://%s/%s' in %d ms",
-            bucketName, path, duration);
+        printInfo("uploaded 's3://%s/%s' (%d bytes) in %d ms",
+            bucketName, path, size, duration);
 
         stats.putTimeMs += duration;
+        stats.putBytes += std::max(size, (decltype(size)) 0);
         stats.put++;
     }
 
diff --git a/src/libstore/s3-binary-cache-store.hh b/src/libstore/s3-binary-cache-store.hh
index b2b75d498..4d43fe4d2 100644
--- a/src/libstore/s3-binary-cache-store.hh
+++ b/src/libstore/s3-binary-cache-store.hh
@@ -19,6 +19,7 @@ public:
     struct Stats
     {
         std::atomic<uint64_t> put{0};
+        std::atomic<uint64_t> putBytes{0};
         std::atomic<uint64_t> putTimeMs{0};
         std::atomic<uint64_t> get{0};
         std::atomic<uint64_t> getBytes{0};
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index fb9e30597..2837910b9 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -193,10 +193,6 @@ StorePath Store::makeFixedOutputPath(
     }
 }
 
-// FIXME Put this somewhere?
-template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
-template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
-
 StorePath Store::makeFixedOutputPathFromCA(std::string_view name, ContentAddress ca,
     const StorePathSet & references, bool hasSelfReference) const
 {
@@ -876,7 +872,7 @@ std::optional<ValidPathInfo> decodeValidPathInfo(const Store & store, std::istre
     if (hashGiven) {
         string s;
         getline(str, s);
-        info.narHash = Hash(s, htSHA256);
+        info.narHash = Hash::parseAny(s, htSHA256);
         getline(str, s);
         if (!string2Int(s, info.narSize)) throw Error("number expected");
     }
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index e05a19975..e94d975c5 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -10,6 +10,7 @@
 #include "globals.hh"
 #include "config.hh"
 #include "derivations.hh"
+#include "path-info.hh"
 
 #include <atomic>
 #include <limits>
@@ -101,95 +102,6 @@ struct GCResults
 };
 
 
-struct SubstitutablePathInfo
-{
-    std::optional<StorePath> deriver;
-    StorePathSet references;
-    uint64_t downloadSize; /* 0 = unknown or inapplicable */
-    uint64_t narSize; /* 0 = unknown */
-};
-
-typedef std::map<StorePath, SubstitutablePathInfo> SubstitutablePathInfos;
-
-struct ValidPathInfo
-{
-    StorePath path;
-    std::optional<StorePath> deriver;
-    // TODO document this
-    std::optional<Hash> narHash;
-    StorePathSet references;
-    time_t registrationTime = 0;
-    uint64_t narSize = 0; // 0 = unknown
-    uint64_t id; // internal use only
-
-    /* Whether the path is ultimately trusted, that is, it's a
-       derivation output that was built locally. */
-    bool ultimate = false;
-
-    StringSet sigs; // note: not necessarily verified
-
-    /* If non-empty, an assertion that the path is content-addressed,
-       i.e., that the store path is computed from a cryptographic hash
-       of the contents of the path, plus some other bits of data like
-       the "name" part of the path. Such a path doesn't need
-       signatures, since we don't have to trust anybody's claim that
-       the path is the output of a particular derivation. (In the
-       extensional store model, we have to trust that the *contents*
-       of an output path of a derivation were actually produced by
-       that derivation. In the intensional model, we have to trust
-       that a particular output path was produced by a derivation; the
-       path then implies the contents.)
-
-       Ideally, the content-addressability assertion would just be a Boolean,
-       and the store path would be computed from the name component, ‘narHash’
-       and ‘references’. However, we support many types of content addresses.
-    */
-    std::optional<ContentAddress> ca;
-
-    bool operator == (const ValidPathInfo & i) const
-    {
-        return
-            path == i.path
-            && narHash == i.narHash
-            && references == i.references;
-    }
-
-    /* Return a fingerprint of the store path to be used in binary
-       cache signatures. It contains the store path, the base-32
-       SHA-256 hash of the NAR serialisation of the path, the size of
-       the NAR, and the sorted references. The size field is strictly
-       speaking superfluous, but might prevent endless/excessive data
-       attacks. */
-    std::string fingerprint(const Store & store) const;
-
-    void sign(const Store & store, const SecretKey & secretKey);
-
-    /* Return true iff the path is verifiably content-addressed. */
-    bool isContentAddressed(const Store & store) const;
-
-    static const size_t maxSigs = std::numeric_limits<size_t>::max();
-
-    /* Return the number of signatures on this .narinfo that were
-       produced by one of the specified keys, or maxSigs if the path
-       is content-addressed. */
-    size_t checkSignatures(const Store & store, const PublicKeys & publicKeys) const;
-
-    /* Verify a single signature. */
-    bool checkSignature(const Store & store, const PublicKeys & publicKeys, const std::string & sig) const;
-
-    Strings shortRefs() const;
-
-    ValidPathInfo(const ValidPathInfo & other) = default;
-
-    ValidPathInfo(StorePath && path) : path(std::move(path)) { };
-    ValidPathInfo(const StorePath & path) : path(path) { };
-
-    virtual ~ValidPathInfo() { }
-};
-
-typedef list<ValidPathInfo> ValidPathInfos;
-
-
 enum BuildMode { bmNormal, bmRepair, bmCheck };
 
 
diff --git a/src/libutil/error.hh b/src/libutil/error.hh
index 0daaf3be2..f3babcbde 100644
--- a/src/libutil/error.hh
+++ b/src/libutil/error.hh
@@ -192,6 +192,7 @@ public:
 
 MakeError(Error, BaseError);
 MakeError(UsageError, Error);
+MakeError(UnimplementedError, Error);
 
 class SysError : public Error
 {
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index 2b0390da4..dfb3668f1 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -7,6 +7,7 @@
 #include "args.hh"
 #include "hash.hh"
 #include "archive.hh"
+#include "split.hh"
 #include "util.hh"
 
 #include <sys/types.h>
@@ -15,6 +16,7 @@
 
 namespace nix {
 
+
 static size_t regularHashSize(HashType type) {
     switch (type) {
     case htMD5: return md5HashSize;
@@ -25,10 +27,11 @@ static size_t regularHashSize(HashType type) {
     abort();
 }
 
+
 std::set<std::string> hashTypes = { "md5", "sha1", "sha256", "sha512" };
 
 
-void Hash::init()
+Hash::Hash(HashType type) : type(type)
 {
     hashSize = regularHashSize(type);
     assert(hashSize <= maxHashSize);
@@ -133,57 +136,89 @@ std::string Hash::to_string(Base base, bool includeType) const
     return s;
 }
 
-Hash::Hash(std::string_view s, HashType type) : Hash(s, std::optional { type }) { }
-Hash::Hash(std::string_view s) : Hash(s, std::optional<HashType>{}) { }
-
-Hash::Hash(std::string_view original, std::optional<HashType> optType)
-{
+Hash Hash::parseSRI(std::string_view original) {
     auto rest = original;
 
-    size_t pos = 0;
+    // Parse the has type before the separater, if there was one.
+    auto hashRaw = splitPrefixTo(rest, '-');
+    if (!hashRaw)
+        throw BadHash("hash '%s' is not SRI", original);
+    HashType parsedType = parseHashType(*hashRaw);
+
+    return Hash(rest, parsedType, true);
+}
+
+// Mutates the string to eliminate the prefixes when found
+static std::pair<std::optional<HashType>, bool> getParsedTypeAndSRI(std::string_view & rest) {
     bool isSRI = false;
 
     // Parse the has type before the separater, if there was one.
     std::optional<HashType> optParsedType;
     {
-        auto sep = rest.find(':');
-        if (sep == std::string_view::npos) {
-            sep = rest.find('-');
-            if (sep != std::string_view::npos)
+        auto hashRaw = splitPrefixTo(rest, ':');
+
+        if (!hashRaw) {
+            hashRaw = splitPrefixTo(rest, '-');
+            if (hashRaw)
                 isSRI = true;
         }
-        if (sep != std::string_view::npos) {
-            auto hashRaw = rest.substr(0, sep);
-            optParsedType = parseHashType(hashRaw);
-            rest = rest.substr(sep + 1);
-        }
+        if (hashRaw)
+            optParsedType = parseHashType(*hashRaw);
     }
 
+    return {optParsedType, isSRI};
+}
+
+Hash Hash::parseAnyPrefixed(std::string_view original)
+{
+    auto rest = original;
+    auto [optParsedType, isSRI] = getParsedTypeAndSRI(rest);
+
     // Either the string or user must provide the type, if they both do they
     // must agree.
-    if (!optParsedType && !optType) {
+    if (!optParsedType)
+        throw BadHash("hash '%s' does not include a type", rest);
+
+    return Hash(rest, *optParsedType, isSRI);
+}
+
+Hash Hash::parseAny(std::string_view original, std::optional<HashType> optType)
+{
+    auto rest = original;
+    auto [optParsedType, isSRI] = getParsedTypeAndSRI(rest);
+
+    // Either the string or user must provide the type, if they both do they
+    // must agree.
+    if (!optParsedType && !optType)
         throw BadHash("hash '%s' does not include a type, nor is the type otherwise known from context.", rest);
-    } else {
-        this->type = optParsedType ? *optParsedType : *optType;
-        if (optParsedType && optType && *optParsedType != *optType)
-            throw BadHash("hash '%s' should have type '%s'", original, printHashType(*optType));
-    }
+    else if (optParsedType && optType && *optParsedType != *optType)
+        throw BadHash("hash '%s' should have type '%s'", original, printHashType(*optType));
 
-    init();
+    HashType hashType = optParsedType ? *optParsedType : *optType;
+    return Hash(rest, hashType, isSRI);
+}
 
+Hash Hash::parseNonSRIUnprefixed(std::string_view s, HashType type)
+{
+    return Hash(s, type, false);
+}
+
+Hash::Hash(std::string_view rest, HashType type, bool isSRI)
+    : Hash(type)
+{
     if (!isSRI && rest.size() == base16Len()) {
 
         auto parseHexDigit = [&](char c) {
             if (c >= '0' && c <= '9') return c - '0';
             if (c >= 'A' && c <= 'F') return c - 'A' + 10;
             if (c >= 'a' && c <= 'f') return c - 'a' + 10;
-            throw BadHash("invalid base-16 hash '%s'", original);
+            throw BadHash("invalid base-16 hash '%s'", rest);
         };
 
         for (unsigned int i = 0; i < hashSize; i++) {
             hash[i] =
-                parseHexDigit(rest[pos + i * 2]) << 4
-                | parseHexDigit(rest[pos + i * 2 + 1]);
+                parseHexDigit(rest[i * 2]) << 4
+                | parseHexDigit(rest[i * 2 + 1]);
         }
     }
 
@@ -195,7 +230,7 @@ Hash::Hash(std::string_view original, std::optional<HashType> optType)
             for (digit = 0; digit < base32Chars.size(); ++digit) /* !!! slow */
                 if (base32Chars[digit] == c) break;
             if (digit >= 32)
-                throw BadHash("invalid base-32 hash '%s'", original);
+                throw BadHash("invalid base-32 hash '%s'", rest);
             unsigned int b = n * 5;
             unsigned int i = b / 8;
             unsigned int j = b % 8;
@@ -205,7 +240,7 @@ Hash::Hash(std::string_view original, std::optional<HashType> optType)
                 hash[i + 1] |= digit >> (8 - j);
             } else {
                 if (digit >> (8 - j))
-                    throw BadHash("invalid base-32 hash '%s'", original);
+                    throw BadHash("invalid base-32 hash '%s'", rest);
             }
         }
     }
@@ -213,7 +248,7 @@ Hash::Hash(std::string_view original, std::optional<HashType> optType)
     else if (isSRI || rest.size() == base64Len()) {
         auto d = base64Decode(rest);
         if (d.size() != hashSize)
-            throw BadHash("invalid %s hash '%s'", isSRI ? "SRI" : "base-64", original);
+            throw BadHash("invalid %s hash '%s'", isSRI ? "SRI" : "base-64", rest);
         assert(hashSize);
         memcpy(hash, d.data(), hashSize);
     }
@@ -231,7 +266,7 @@ Hash newHashAllowEmpty(std::string hashStr, std::optional<HashType> ht)
         warn("found empty hash, assuming '%s'", h.to_string(SRI, true));
         return h;
     } else
-        return Hash(hashStr, ht);
+        return Hash::parseAny(hashStr, ht);
 }
 
 
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index abcd58f24..00ce7bb6f 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -34,21 +34,31 @@ struct Hash
     HashType type;
 
     /* Create a zero-filled hash object. */
-    Hash(HashType type) : type(type) { init(); };
+    Hash(HashType type);
 
-    /* Initialize the hash from a string representation, in the format
+    /* Parse the hash from a string representation in the format
        "[<type>:]<base16|base32|base64>" or "<type>-<base64>" (a
        Subresource Integrity hash expression). If the 'type' argument
        is not present, then the hash type must be specified in the
        string. */
-    Hash(std::string_view s, std::optional<HashType> type);
-    // type must be provided
-    Hash(std::string_view s, HashType type);
-    // hash type must be part of string
-    Hash(std::string_view s);
+    static Hash parseAny(std::string_view s, std::optional<HashType> type);
 
-    void init();
+    /* Parse a hash from a string representation like the above, except the
+       type prefix is mandatory is there is no separate arguement. */
+    static Hash parseAnyPrefixed(std::string_view s);
 
+    /* Parse a plain hash that musst not have any prefix indicating the type.
+       The type is passed in to disambiguate. */
+    static Hash parseNonSRIUnprefixed(std::string_view s, HashType type);
+
+    static Hash parseSRI(std::string_view original);
+
+private:
+    /* The type must be provided, the string view must not include <type>
+       prefix. `isSRI` helps disambigate the various base-* encodings. */
+    Hash(std::string_view s, HashType type, bool isSRI);
+
+public:
     /* Check whether a hash is set. */
     operator bool () const { return (bool) type; }
 
diff --git a/src/libutil/split.hh b/src/libutil/split.hh
new file mode 100644
index 000000000..d19d7d8ed
--- /dev/null
+++ b/src/libutil/split.hh
@@ -0,0 +1,33 @@
+#pragma once
+
+#include <optional>
+#include <string_view>
+
+#include "util.hh"
+
+namespace nix {
+
+// If `separator` is found, we return the portion of the string before the
+// separator, and modify the string argument to contain only the part after the
+// separator. Otherwise, wer return `std::nullopt`, and we leave the argument
+// string alone.
+static inline std::optional<std::string_view> splitPrefixTo(std::string_view & string, char separator) {
+    auto sepInstance = string.find(separator);
+
+    if (sepInstance != std::string_view::npos) {
+        auto prefix = string.substr(0, sepInstance);
+        string.remove_prefix(sepInstance+1);
+        return prefix;
+    }
+
+    return std::nullopt;
+}
+
+static inline bool splitPrefix(std::string_view & string, std::string_view prefix) {
+    bool res = hasPrefix(string, prefix);
+    if (res)
+        string.remove_prefix(prefix.length());
+    return res;
+}
+
+}
diff --git a/src/libutil/topo-sort.hh b/src/libutil/topo-sort.hh
new file mode 100644
index 000000000..7a68ff169
--- /dev/null
+++ b/src/libutil/topo-sort.hh
@@ -0,0 +1,40 @@
+#include "error.hh"
+
+namespace nix {
+
+template<typename T>
+std::vector<T> topoSort(std::set<T> items,
+        std::function<std::set<T>(const T &)> getChildren,
+        std::function<Error(const T &, const T &)> makeCycleError)
+{
+    std::vector<T> sorted;
+    std::set<T> visited, parents;
+
+    std::function<void(const T & path, const T * parent)> dfsVisit;
+
+    dfsVisit = [&](const T & path, const T * parent) {
+        if (parents.count(path)) throw makeCycleError(path, *parent);
+
+        if (!visited.insert(path).second) return;
+        parents.insert(path);
+
+        std::set<T> references = getChildren(path);
+
+        for (auto & i : references)
+            /* Don't traverse into items that don't exist in our starting set. */
+            if (i != path && items.count(i))
+                dfsVisit(i, &path);
+
+        sorted.push_back(path);
+        parents.erase(path);
+    };
+
+    for (auto & i : items)
+        dfsVisit(i, nullptr);
+
+    std::reverse(sorted.begin(), sorted.end());
+
+    return sorted;
+}
+
+}
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index 8bc60ec2d..c0b9698ee 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -1450,7 +1450,7 @@ string base64Decode(std::string_view s)
 
         char digit = decode[(unsigned char) c];
         if (digit == -1)
-            throw Error("invalid character in Base64 string");
+            throw Error("invalid character in Base64 string: '%c'", c);
 
         bits += 6;
         d = d << 6 | digit;
diff --git a/src/libutil/util.hh b/src/libutil/util.hh
index 6850b5a7a..3a20679a8 100644
--- a/src/libutil/util.hh
+++ b/src/libutil/util.hh
@@ -601,4 +601,9 @@ constexpr auto enumerate(T && iterable)
 }
 
 
+// C++17 std::visit boilerplate
+template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
+template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;
+
+
 }
diff --git a/src/nix-prefetch-url/nix-prefetch-url.cc b/src/nix-prefetch-url/nix-prefetch-url.cc
index 65d8ec6b6..1001f27af 100644
--- a/src/nix-prefetch-url/nix-prefetch-url.cc
+++ b/src/nix-prefetch-url/nix-prefetch-url.cc
@@ -157,7 +157,7 @@ static int _main(int argc, char * * argv)
         Hash hash(ht);
         std::optional<StorePath> storePath;
         if (args.size() == 2) {
-            expectedHash = Hash(args[1], ht);
+            expectedHash = Hash::parseAny(args[1], ht);
             const auto recursive = unpack ? FileIngestionMethod::Recursive : FileIngestionMethod::Flat;
             storePath = store->makeFixedOutputPath(recursive, *expectedHash, name);
             if (store->isValidPath(*storePath))
diff --git a/src/nix-store/nix-store.cc b/src/nix-store/nix-store.cc
index 7b26970ef..2996e36c4 100644
--- a/src/nix-store/nix-store.cc
+++ b/src/nix-store/nix-store.cc
@@ -208,7 +208,7 @@ static void opPrintFixedPath(Strings opFlags, Strings opArgs)
     string hash = *i++;
     string name = *i++;
 
-    cout << fmt("%s\n", store->printStorePath(store->makeFixedOutputPath(recursive, Hash(hash, hashAlgo), name)));
+    cout << fmt("%s\n", store->printStorePath(store->makeFixedOutputPath(recursive, Hash::parseAny(hash, hashAlgo), name)));
 }
 
 
@@ -948,7 +948,7 @@ static void opServe(Strings opFlags, Strings opArgs)
                 auto deriver = readString(in);
                 if (deriver != "")
                     info.deriver = store->parseStorePath(deriver);
-                info.narHash = Hash(readString(in), htSHA256);
+                info.narHash = Hash::parseAny(readString(in), htSHA256);
                 info.references = readStorePaths<StorePathSet>(*store, in);
                 in >> info.registrationTime >> info.narSize >> info.ultimate;
                 info.sigs = readStrings<StringSet>(in);
diff --git a/src/nix/build.cc b/src/nix/build.cc
index 613cc15eb..13d14a7fb 100644
--- a/src/nix/build.cc
+++ b/src/nix/build.cc
@@ -64,17 +64,24 @@ struct CmdBuild : InstallablesCommand, MixDryRun, MixProfile
 
         if (dryRun) return;
 
-        if (outLink != "") {
-            for (size_t i = 0; i < buildables.size(); ++i) {
-                for (auto & output : buildables[i].outputs)
-                    if (auto store2 = store.dynamic_pointer_cast<LocalFSStore>()) {
-                        std::string symlink = outLink;
-                        if (i) symlink += fmt("-%d", i);
-                        if (output.first != "out") symlink += fmt("-%s", output.first);
-                        store2->addPermRoot(output.second, absPath(symlink), true);
-                    }
-            }
-        }
+        if (outLink != "")
+            if (auto store2 = store.dynamic_pointer_cast<LocalFSStore>())
+                for (size_t i = 0; i < buildables.size(); ++i)
+                    std::visit(overloaded {
+                        [&](BuildableOpaque bo) {
+                            std::string symlink = outLink;
+                            if (i) symlink += fmt("-%d", i);
+                            store2->addPermRoot(bo.path, absPath(symlink), true);
+                        },
+                        [&](BuildableFromDrv bfd) {
+                            for (auto & output : bfd.outputs) {
+                                std::string symlink = outLink;
+                                if (i) symlink += fmt("-%d", i);
+                                if (output.first != "out") symlink += fmt("-%s", output.first);
+                                store2->addPermRoot(output.second, absPath(symlink), true);
+                            }
+                        },
+                    }, buildables[i]);
 
         updateProfile(buildables);
     }
diff --git a/src/nix/command.cc b/src/nix/command.cc
index af36dda89..da32819da 100644
--- a/src/nix/command.cc
+++ b/src/nix/command.cc
@@ -128,20 +128,25 @@ void MixProfile::updateProfile(const Buildables & buildables)
 {
     if (!profile) return;
 
-    std::optional<StorePath> result;
+    std::vector<StorePath> result;
 
     for (auto & buildable : buildables) {
-        for (auto & output : buildable.outputs) {
-            if (result)
-                throw Error("'--profile' requires that the arguments produce a single store path, but there are multiple");
-            result = output.second;
-        }
+        std::visit(overloaded {
+            [&](BuildableOpaque bo) {
+                result.push_back(bo.path);
+            },
+            [&](BuildableFromDrv bfd) {
+                for (auto & output : bfd.outputs) {
+                    result.push_back(output.second);
+                }
+            },
+        }, buildable);
     }
 
-    if (!result)
-        throw Error("'--profile' requires that the arguments produce a single store path, but there are none");
+    if (result.size() != 1)
+        throw Error("'--profile' requires that the arguments produce a single store path, but there are %d", result.size());
 
-    updateProfile(*result);
+    updateProfile(result[0]);
 }
 
 MixDefaultProfile::MixDefaultProfile()
diff --git a/src/nix/develop.cc b/src/nix/develop.cc
index a0c119e43..12658078a 100644
--- a/src/nix/develop.cc
+++ b/src/nix/develop.cc
@@ -135,7 +135,7 @@ StorePath getDerivationEnvironment(ref<Store> store, const StorePath & drvPath)
     drv.env["_outputs_saved"] = drv.env["outputs"];
     drv.env["outputs"] = "out";
     drv.inputSrcs.insert(std::move(getEnvShPath));
-    Hash h = hashDerivationModulo(*store, drv, true);
+    Hash h = std::get<0>(hashDerivationModulo(*store, drv, true));
     auto shellOutPath = store->makeOutputPath("out", h, drvName);
     drv.outputs.insert_or_assign("out", DerivationOutput { .output = DerivationOutputInputAddressed {
                 .path = shellOutPath
diff --git a/src/nix/hash.cc b/src/nix/hash.cc
index b94751e45..0eca4f8ea 100644
--- a/src/nix/hash.cc
+++ b/src/nix/hash.cc
@@ -107,7 +107,7 @@ struct CmdToBase : Command
     void run() override
     {
         for (auto s : args)
-            logger->stdout(Hash(s, ht).to_string(base, base == SRI));
+            logger->stdout(Hash::parseAny(s, ht).to_string(base, base == SRI));
     }
 };
 
diff --git a/src/nix/installables.cc b/src/nix/installables.cc
index babb0e5fe..06e61380b 100644
--- a/src/nix/installables.cc
+++ b/src/nix/installables.cc
@@ -308,16 +308,15 @@ struct InstallableStorePath : Installable
             for (auto & [name, output] : drv.outputs)
                 outputs.emplace(name, output.path(*store, drv.name));
             return {
-                Buildable {
+                BuildableFromDrv {
                     .drvPath = storePath,
                     .outputs = std::move(outputs)
                 }
             };
         } else {
             return {
-                Buildable {
-                    .drvPath = {},
-                    .outputs = {{"out", storePath}}
+                BuildableOpaque {
+                    .path = storePath,
                 }
             };
         }
@@ -333,33 +332,20 @@ Buildables InstallableValue::toBuildables()
 {
     Buildables res;
 
-    StorePathSet drvPaths;
+    std::map<StorePath, OutputPathMap> drvsToOutputs;
 
+    // Group by derivation, helps with .all in particular
     for (auto & drv : toDerivations()) {
-        Buildable b{.drvPath = drv.drvPath};
-        drvPaths.insert(drv.drvPath);
-
         auto outputName = drv.outputName;
         if (outputName == "")
-            throw Error("derivation '%s' lacks an 'outputName' attribute", state->store->printStorePath(*b.drvPath));
-
-        b.outputs.emplace(outputName, drv.outPath);
-
-        res.push_back(std::move(b));
+            throw Error("derivation '%s' lacks an 'outputName' attribute", state->store->printStorePath(drv.drvPath));
+        drvsToOutputs[drv.drvPath].insert_or_assign(outputName, drv.outPath);
     }
 
-    // Hack to recognize .all: if all drvs have the same drvPath,
-    // merge the buildables.
-    if (drvPaths.size() == 1) {
-        Buildable b{.drvPath = *drvPaths.begin()};
-        for (auto & b2 : res)
-            for (auto & output : b2.outputs)
-                b.outputs.insert_or_assign(output.first, output.second);
-        Buildables bs;
-        bs.push_back(std::move(b));
-        return bs;
-    } else
-        return res;
+    for (auto & i : drvsToOutputs)
+        res.push_back(BuildableFromDrv { i.first, i.second });
+
+    return res;
 }
 
 struct InstallableAttrPath : InstallableValue
@@ -437,7 +423,7 @@ ref<eval_cache::EvalCache> openEvalCache(
     std::shared_ptr<flake::LockedFlake> lockedFlake,
     bool useEvalCache)
 {
-	auto fingerprint = lockedFlake->getFingerprint();
+    auto fingerprint = lockedFlake->getFingerprint();
     return make_ref<nix::eval_cache::EvalCache>(
         useEvalCache && evalSettings.pureEval
             ? std::optional { std::cref(fingerprint) }
@@ -656,14 +642,17 @@ Buildables build(ref<Store> store, Realise mode,
 
     for (auto & i : installables) {
         for (auto & b : i->toBuildables()) {
-            if (b.drvPath) {
-                StringSet outputNames;
-                for (auto & output : b.outputs)
-                    outputNames.insert(output.first);
-                pathsToBuild.push_back({*b.drvPath, outputNames});
-            } else
-                for (auto & output : b.outputs)
-                    pathsToBuild.push_back({output.second});
+            std::visit(overloaded {
+                [&](BuildableOpaque bo) {
+                    pathsToBuild.push_back({bo.path});
+                },
+                [&](BuildableFromDrv bfd) {
+                    StringSet outputNames;
+                    for (auto & output : bfd.outputs)
+                        outputNames.insert(output.first);
+                    pathsToBuild.push_back({bfd.drvPath, outputNames});
+                },
+            }, b);
             buildables.push_back(std::move(b));
         }
     }
@@ -684,16 +673,23 @@ StorePathSet toStorePaths(ref<Store> store,
 
     if (operateOn == OperateOn::Output) {
         for (auto & b : build(store, mode, installables))
-            for (auto & output : b.outputs)
-                outPaths.insert(output.second);
+            std::visit(overloaded {
+                [&](BuildableOpaque bo) {
+                    outPaths.insert(bo.path);
+                },
+                [&](BuildableFromDrv bfd) {
+                    for (auto & output : bfd.outputs)
+                        outPaths.insert(output.second);
+                },
+            }, b);
     } else {
         if (mode == Realise::Nothing)
             settings.readOnlyMode = true;
 
         for (auto & i : installables)
             for (auto & b : i->toBuildables())
-                if (b.drvPath)
-                    outPaths.insert(*b.drvPath);
+                if (auto bfd = std::get_if<BuildableFromDrv>(&b))
+                    outPaths.insert(bfd->drvPath);
     }
 
     return outPaths;
@@ -717,20 +713,21 @@ StorePathSet toDerivations(ref<Store> store,
     StorePathSet drvPaths;
 
     for (auto & i : installables)
-        for (auto & b : i->toBuildables()) {
-            if (!b.drvPath) {
-                if (!useDeriver)
-                    throw Error("argument '%s' did not evaluate to a derivation", i->what());
-                for (auto & output : b.outputs) {
-                    auto derivers = store->queryValidDerivers(output.second);
+        for (auto & b : i->toBuildables())
+            std::visit(overloaded {
+                [&](BuildableOpaque bo) {
+                    if (!useDeriver)
+                        throw Error("argument '%s' did not evaluate to a derivation", i->what());
+                    auto derivers = store->queryValidDerivers(bo.path);
                     if (derivers.empty())
                         throw Error("'%s' does not have a known deriver", i->what());
                     // FIXME: use all derivers?
                     drvPaths.insert(*derivers.begin());
-                }
-            } else
-                drvPaths.insert(*b.drvPath);
-        }
+                },
+                [&](BuildableFromDrv bfd) {
+                    drvPaths.insert(bfd.drvPath);
+                },
+            }, b);
 
     return drvPaths;
 }
diff --git a/src/nix/installables.hh b/src/nix/installables.hh
index eb34365d4..9edff3331 100644
--- a/src/nix/installables.hh
+++ b/src/nix/installables.hh
@@ -14,12 +14,20 @@ struct SourceExprCommand;
 
 namespace eval_cache { class EvalCache; class AttrCursor; }
 
-struct Buildable
-{
-    std::optional<StorePath> drvPath;
+struct BuildableOpaque {
+    StorePath path;
+};
+
+struct BuildableFromDrv {
+    StorePath drvPath;
     std::map<std::string, StorePath> outputs;
 };
 
+typedef std::variant<
+    BuildableOpaque,
+    BuildableFromDrv
+> Buildable;
+
 typedef std::vector<Buildable> Buildables;
 
 struct App
diff --git a/src/nix/log.cc b/src/nix/log.cc
index 7e10d373a..33380dcf5 100644
--- a/src/nix/log.cc
+++ b/src/nix/log.cc
@@ -45,11 +45,14 @@ struct CmdLog : InstallableCommand
 
         RunPager pager;
         for (auto & sub : subs) {
-            auto log = b.drvPath ? sub->getBuildLog(*b.drvPath) : nullptr;
-            for (auto & output : b.outputs) {
-                if (log) break;
-                log = sub->getBuildLog(output.second);
-            }
+            auto log = std::visit(overloaded {
+                [&](BuildableOpaque bo) {
+                    return sub->getBuildLog(bo.path);
+                },
+                [&](BuildableFromDrv bfd) {
+                    return sub->getBuildLog(bfd.drvPath);
+                },
+            }, b);
             if (!log) continue;
             stopProgressBar();
             printInfo("got build log for '%s' from '%s'", installable->what(), sub->getUri());
diff --git a/src/nix/repl.cc b/src/nix/repl.cc
index fb9050d0d..c3c9e54a8 100644
--- a/src/nix/repl.cc
+++ b/src/nix/repl.cc
@@ -33,12 +33,17 @@ extern "C" {
 #include "command.hh"
 #include "finally.hh"
 
+#if HAVE_BOEHMGC
 #define GC_INCLUDE_NEW
 #include <gc/gc_cpp.h>
+#endif
 
 namespace nix {
 
-struct NixRepl : gc
+struct NixRepl
+    #if HAVE_BOEHMGC
+    : gc
+    #endif
 {
     string curDir;
     std::unique_ptr<EvalState> state;
diff --git a/src/nix/show-derivation.cc b/src/nix/show-derivation.cc
index 9fd26e2d7..1b51d114f 100644
--- a/src/nix/show-derivation.cc
+++ b/src/nix/show-derivation.cc
@@ -70,10 +70,18 @@ struct CmdShowDerivation : InstallablesCommand
                 for (auto & output : drv.outputs) {
                     auto outputObj(outputsObj.object(output.first));
                     outputObj.attr("path", store->printStorePath(output.second.path(*store, drv.name)));
-                    if (auto hash = std::get_if<DerivationOutputFixed>(&output.second.output)) {
-                        outputObj.attr("hashAlgo", hash->hash.printMethodAlgo());
-                        outputObj.attr("hash", hash->hash.hash.to_string(Base16, false));
-                    }
+
+                    std::visit(overloaded {
+                        [&](DerivationOutputInputAddressed doi) {
+                        },
+                        [&](DerivationOutputCAFixed dof) {
+                            outputObj.attr("hashAlgo", dof.hash.printMethodAlgo());
+                            outputObj.attr("hash", dof.hash.hash.to_string(Base16, false));
+                        },
+                        [&](DerivationOutputCAFloating dof) {
+                            outputObj.attr("hashAlgo", makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
+                        },
+                    }, output.second.output);
                 }
             }