Merge remote-tracking branch 'upstream/master' into remove-storetype-delegate-regStore

22 files changed, 1240 insertions, 657 deletions

diff --git a/src/libstore/binary-cache-store.cc b/src/libstore/binary-cache-store.cc
index 5433fe50d..34f844a18 100644
--- a/src/libstore/binary-cache-store.cc
+++ b/src/libstore/binary-cache-store.cc
@@ -22,7 +22,8 @@
 namespace nix {
 
 BinaryCacheStore::BinaryCacheStore(const Params & params)
-    : Store(params)
+    : BinaryCacheStoreConfig(params)
+    , Store(params)
 {
     if (secretKeyFile != "")
         secretKey = std::unique_ptr<SecretKey>(new SecretKey(readFile(secretKeyFile)));
diff --git a/src/libstore/binary-cache-store.hh b/src/libstore/binary-cache-store.hh
index 9bcdf5901..4b779cdd4 100644
--- a/src/libstore/binary-cache-store.hh
+++ b/src/libstore/binary-cache-store.hh
@@ -11,17 +11,21 @@ namespace nix {
 
 struct NarInfo;
 
-class BinaryCacheStore : public Store
+struct BinaryCacheStoreConfig : virtual StoreConfig
 {
-public:
-
-    const Setting<std::string> compression{this, "xz", "compression", "NAR compression method ('xz', 'bzip2', or 'none')"};
-    const Setting<bool> writeNARListing{this, false, "write-nar-listing", "whether to write a JSON file listing the files in each NAR"};
-    const Setting<bool> writeDebugInfo{this, false, "index-debug-info", "whether to index DWARF debug info files by build ID"};
-    const Setting<Path> secretKeyFile{this, "", "secret-key", "path to secret key used to sign the binary cache"};
-    const Setting<Path> localNarCache{this, "", "local-nar-cache", "path to a local cache of NARs"};
-    const Setting<bool> parallelCompression{this, false, "parallel-compression",
+    using StoreConfig::StoreConfig;
+
+    const Setting<std::string> compression{(StoreConfig*) this, "xz", "compression", "NAR compression method ('xz', 'bzip2', or 'none')"};
+    const Setting<bool> writeNARListing{(StoreConfig*) this, false, "write-nar-listing", "whether to write a JSON file listing the files in each NAR"};
+    const Setting<bool> writeDebugInfo{(StoreConfig*) this, false, "index-debug-info", "whether to index DWARF debug info files by build ID"};
+    const Setting<Path> secretKeyFile{(StoreConfig*) this, "", "secret-key", "path to secret key used to sign the binary cache"};
+    const Setting<Path> localNarCache{(StoreConfig*) this, "", "local-nar-cache", "path to a local cache of NARs"};
+    const Setting<bool> parallelCompression{(StoreConfig*) this, false, "parallel-compression",
         "enable multi-threading compression, available for xz only currently"};
+};
+
+class BinaryCacheStore : public Store, public virtual BinaryCacheStoreConfig
+{
 
 private:
 
@@ -58,7 +62,7 @@ public:
 
 public:
 
-    virtual void init();
+    virtual void init() override;
 
 private:
 
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index dd932cee9..6e55f83d5 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -16,6 +16,7 @@
 #include "machines.hh"
 #include "daemon.hh"
 #include "worker-protocol.hh"
+#include "topo-sort.hh"
 
 #include <algorithm>
 #include <iostream>
@@ -717,6 +718,33 @@ typedef enum {rpAccept, rpDecline, rpPostpone} HookReply;
 
 class SubstitutionGoal;
 
+/* Unless we are repairing, we don't both to test validity and just assume it,
+   so the choices are `Absent` or `Valid`. */
+enum struct PathStatus {
+    Corrupt,
+    Absent,
+    Valid,
+};
+
+struct InitialOutputStatus {
+    StorePath path;
+    PathStatus status;
+    /* Valid in the store, and additionally non-corrupt if we are repairing */
+    bool isValid() const {
+        return status == PathStatus::Valid;
+    }
+    /* Merely present, allowed to be corrupt */
+    bool isPresent() const {
+        return status == PathStatus::Corrupt
+            || status == PathStatus::Valid;
+    }
+};
+
+struct InitialOutput {
+    bool wanted;
+    std::optional<InitialOutputStatus> known;
+};
+
 class DerivationGoal : public Goal
 {
 private:
@@ -744,19 +772,14 @@ private:
 
     /* The remainder is state held during the build. */
 
-    /* Locks on the output paths. */
+    /* Locks on (fixed) output paths. */
     PathLocks outputLocks;
 
     /* All input paths (that is, the union of FS closures of the
        immediate input paths). */
     StorePathSet inputPaths;
 
-    /* Outputs that are already valid.  If we're repairing, these are
-       the outputs that are valid *and* not corrupt. */
-    StorePathSet validPaths;
-
-    /* Outputs that are corrupt or not valid. */
-    StorePathSet missingPaths;
+    std::map<std::string, InitialOutput> initialOutputs;
 
     /* User selected for running the builder. */
     std::unique_ptr<UserLock> buildUser;
@@ -839,6 +862,31 @@ private:
     typedef map<StorePath, StorePath> RedirectedOutputs;
     RedirectedOutputs redirectedOutputs;
 
+    /* The outputs paths used during the build.
+
+       - Input-addressed derivations or fixed content-addressed outputs are
+         sometimes built when some of their outputs already exist, and can not
+         be hidden via sandboxing. We use temporary locations instead and
+         rewrite after the build. Otherwise the regular predetermined paths are
+         put here.
+
+       - Floating content-addressed derivations do not know their final build
+         output paths until the outputs are hashed, so random locations are
+         used, and then renamed. The randomness helps guard against hidden
+         self-references.
+     */
+    OutputPathMap scratchOutputs;
+
+    /* The final output paths of the build.
+
+       - For input-addressed derivations, always the precomputed paths
+
+       - For content-addressed derivations, calcuated from whatever the hash
+         ends up being. (Note that fixed outputs derivations that produce the
+         "wrong" output still install that data under its true content-address.)
+     */
+    OutputPathMap finalOutputs;
+
     BuildMode buildMode;
 
     /* If we're repairing without a chroot, there may be outputs that
@@ -937,7 +985,8 @@ private:
     void getDerivation();
     void loadDerivation();
     void haveDerivation();
-    void outputsSubstituted();
+    void outputsSubstitutionTried();
+    void gaveUpOnSubstitution();
     void closureRepaired();
     void inputsRealised();
     void tryToBuild();
@@ -998,13 +1047,27 @@ private:
     void handleEOF(int fd) override;
     void flushLine();
 
+    /* Wrappers around the corresponding Store methods that first consult the
+       derivation.  This is currently needed because when there is no drv file
+       there also is no DB entry. */
+    std::map<std::string, std::optional<StorePath>> queryPartialDerivationOutputMap();
+    OutputPathMap queryDerivationOutputMap();
+
     /* Return the set of (in)valid paths. */
-    StorePathSet checkPathValidity(bool returnValid, bool checkHash);
+    void checkPathValidity();
 
     /* Forcibly kill the child process, if any. */
     void killChild();
 
-    void addHashRewrite(const StorePath & path);
+    /* Create alternative path calculated from but distinct from the
+       input, so we can avoid overwriting outputs (or other store paths)
+       that already exist. */
+    StorePath makeFallbackPath(const StorePath & path);
+    /* Make a path to another based on the output name along with the
+       derivation hash. */
+    /* FIXME add option to randomize, so we can audit whether our
+       rewrites caught everything */
+    StorePath makeFallbackPath(std::string_view outputName);
 
     void repairClosure();
 
@@ -1047,7 +1110,7 @@ DerivationGoal::DerivationGoal(const StorePath & drvPath, const BasicDerivation
 {
     this->drv = std::make_unique<BasicDerivation>(BasicDerivation(drv));
     state = &DerivationGoal::haveDerivation;
-    name = fmt("building of %s", worker.store.showPaths(drv.outputPaths(worker.store)));
+    name = fmt("building of %s", StorePathWithOutputs { drvPath, drv.outputNames() }.to_string(worker.store));
     trace("created");
 
     mcExpectedBuilds = std::make_unique<MaintainCount<uint64_t>>(worker.expectedBuilds);
@@ -1179,43 +1242,60 @@ void DerivationGoal::haveDerivation()
 {
     trace("have derivation");
 
+    if (drv->type() == DerivationType::CAFloating)
+        settings.requireExperimentalFeature("ca-derivations");
+
     retrySubstitution = false;
 
-    for (auto & i : drv->outputsAndPaths(worker.store))
-        worker.store.addTempRoot(i.second.second);
+    for (auto & i : drv->outputsAndOptPaths(worker.store))
+        if (i.second.second)
+            worker.store.addTempRoot(*i.second.second);
 
     /* Check what outputs paths are not already valid. */
-    auto invalidOutputs = checkPathValidity(false, buildMode == bmRepair);
+    checkPathValidity();
+    bool allValid = true;
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.wanted) continue;
+        if (!status.known || !status.known->isValid()) {
+            allValid = false;
+            break;
+        }
+    }
 
     /* If they are all valid, then we're done. */
-    if (invalidOutputs.size() == 0 && buildMode == bmNormal) {
+    if (allValid && buildMode == bmNormal) {
         done(BuildResult::AlreadyValid);
         return;
     }
 
     parsedDrv = std::make_unique<ParsedDerivation>(drvPath, *drv);
 
-    if (drv->type() == DerivationType::CAFloating) {
-        settings.requireExperimentalFeature("ca-derivations");
-        throw UnimplementedError("ca-derivations isn't implemented yet");
-    }
-
 
     /* We are first going to try to create the invalid output paths
        through substitutes.  If that doesn't work, we'll build
        them. */
     if (settings.useSubstitutes && parsedDrv->substitutesAllowed())
-        for (auto & i : invalidOutputs)
-            addWaitee(worker.makeSubstitutionGoal(i, buildMode == bmRepair ? Repair : NoRepair, getDerivationCA(*drv)));
+        for (auto & [_, status] : initialOutputs) {
+            if (!status.wanted) continue;
+            if (!status.known) {
+                warn("do not know how to query for unknown floating content-addressed derivation output yet");
+                /* Nothing to wait for; tail call */
+                return DerivationGoal::gaveUpOnSubstitution();
+            }
+            addWaitee(worker.makeSubstitutionGoal(
+                status.known->path,
+                buildMode == bmRepair ? Repair : NoRepair,
+                getDerivationCA(*drv)));
+        }
 
     if (waitees.empty()) /* to prevent hang (no wake-up event) */
-        outputsSubstituted();
+        outputsSubstitutionTried();
     else
-        state = &DerivationGoal::outputsSubstituted;
+        state = &DerivationGoal::outputsSubstitutionTried;
 }
 
 
-void DerivationGoal::outputsSubstituted()
+void DerivationGoal::outputsSubstitutionTried()
 {
     trace("all outputs substituted (maybe)");
 
@@ -1239,7 +1319,14 @@ void DerivationGoal::outputsSubstituted()
         return;
     }
 
-    auto nrInvalid = checkPathValidity(false, buildMode == bmRepair).size();
+    checkPathValidity();
+    size_t nrInvalid = 0;
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.wanted) continue;
+        if (!status.known || !status.known->isValid())
+            nrInvalid++;
+    }
+
     if (buildMode == bmNormal && nrInvalid == 0) {
         done(BuildResult::Substituted);
         return;
@@ -1252,9 +1339,14 @@ void DerivationGoal::outputsSubstituted()
         throw Error("some outputs of '%s' are not valid, so checking is not possible",
             worker.store.printStorePath(drvPath));
 
-    /* Otherwise, at least one of the output paths could not be
-       produced using a substitute.  So we have to build instead. */
+    /* Nothing to wait for; tail call */
+    gaveUpOnSubstitution();
+}
 
+/* At least one of the output paths could not be
+   produced using a substitute.  So we have to build instead. */
+void DerivationGoal::gaveUpOnSubstitution()
+{
     /* Make sure checkPathValidity() from now on checks all
        outputs. */
     wantedOutputs.clear();
@@ -1287,15 +1379,16 @@ void DerivationGoal::repairClosure()
        that produced those outputs. */
 
     /* Get the output closure. */
+    auto outputs = queryDerivationOutputMap();
     StorePathSet outputClosure;
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
+    for (auto & i : outputs) {
         if (!wantOutput(i.first, wantedOutputs)) continue;
-        worker.store.computeFSClosure(i.second.second, outputClosure);
+        worker.store.computeFSClosure(i.second, outputClosure);
     }
 
     /* Filter out our own outputs (which we have already checked). */
-    for (auto & i : drv->outputsAndPaths(worker.store))
-        outputClosure.erase(i.second.second);
+    for (auto & i : outputs)
+        outputClosure.erase(i.second);
 
     /* Get all dependencies of this derivation so that we know which
        derivation is responsible for which path in the output
@@ -1305,9 +1398,10 @@ void DerivationGoal::repairClosure()
     std::map<StorePath, StorePath> outputsToDrv;
     for (auto & i : inputClosure)
         if (i.isDerivation()) {
-            Derivation drv = worker.store.derivationFromPath(i);
-            for (auto & j : drv.outputsAndPaths(worker.store))
-                outputsToDrv.insert_or_assign(j.second.second, i);
+            auto depOutputs = worker.store.queryPartialDerivationOutputMap(i);
+            for (auto & j : depOutputs)
+                if (j.second)
+                    outputsToDrv.insert_or_assign(*j.second, i);
         }
 
     /* Check each path (slow!). */
@@ -1370,20 +1464,24 @@ void DerivationGoal::inputsRealised()
 
     /* First, the input derivations. */
     if (useDerivation)
-        for (auto & i : dynamic_cast<Derivation *>(drv.get())->inputDrvs) {
+        for (auto & [depDrvPath, wantedDepOutputs] : dynamic_cast<Derivation *>(drv.get())->inputDrvs) {
             /* Add the relevant output closures of the input derivation
                `i' as input paths.  Only add the closures of output paths
                that are specified as inputs. */
-            assert(worker.store.isValidPath(i.first));
-            Derivation inDrv = worker.store.derivationFromPath(i.first);
-            for (auto & j : i.second) {
-                auto k = inDrv.outputs.find(j);
-                if (k != inDrv.outputs.end())
-                    worker.store.computeFSClosure(k->second.path(worker.store, inDrv.name), inputPaths);
-                else
+            assert(worker.store.isValidPath(drvPath));
+            auto outputs = worker.store.queryPartialDerivationOutputMap(depDrvPath);
+            for (auto & j : wantedDepOutputs) {
+                if (outputs.count(j) > 0) {
+                    auto optRealizedInput = outputs.at(j);
+                    if (!optRealizedInput)
+                        throw Error(
+                            "derivation '%s' requires output '%s' from input derivation '%s', which is supposedly realized already, yet we still don't know what path corresponds to that output",
+                            worker.store.printStorePath(drvPath), j, worker.store.printStorePath(drvPath));
+                    worker.store.computeFSClosure(*optRealizedInput, inputPaths);
+                } else
                     throw Error(
                         "derivation '%s' requires non-existent output '%s' from input derivation '%s'",
-                        worker.store.printStorePath(drvPath), j, worker.store.printStorePath(i.first));
+                        worker.store.printStorePath(drvPath), j, worker.store.printStorePath(drvPath));
             }
         }
 
@@ -1426,14 +1524,18 @@ void DerivationGoal::tryToBuild()
 {
     trace("trying to build");
 
-    /* Obtain locks on all output paths.  The locks are automatically
-       released when we exit this function or Nix crashes.  If we
-       can't acquire the lock, then continue; hopefully some other
-       goal can start a build, and if not, the main loop will sleep a
-       few seconds and then retry this goal. */
+    /* Obtain locks on all output paths, if the paths are known a priori.
+
+       The locks are automatically released when we exit this function or Nix
+       crashes.  If we can't acquire the lock, then continue; hopefully some
+       other goal can start a build, and if not, the main loop will sleep a few
+       seconds and then retry this goal. */
     PathSet lockFiles;
-    for (auto & outPath : drv->outputPaths(worker.store))
-        lockFiles.insert(worker.store.Store::toRealPath(outPath));
+    /* FIXME: Should lock something like the drv itself so we don't build same
+       CA drv concurrently */
+    for (auto & i : drv->outputsAndOptPaths(worker.store))
+        if (i.second.second)
+            lockFiles.insert(worker.store.Store::toRealPath(*i.second.second));
 
     if (!outputLocks.lockPaths(lockFiles, "", false)) {
         if (!actLock)
@@ -1452,24 +1554,29 @@ void DerivationGoal::tryToBuild()
        omitted, but that would be less efficient.)  Note that since we
        now hold the locks on the output paths, no other process can
        build this derivation, so no further checks are necessary. */
-    validPaths = checkPathValidity(true, buildMode == bmRepair);
-    if (buildMode != bmCheck && validPaths.size() == drv->outputs.size()) {
+    checkPathValidity();
+    bool allValid = true;
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.wanted) continue;
+        if (!status.known || !status.known->isValid()) {
+            allValid = false;
+            break;
+        }
+    }
+    if (buildMode != bmCheck && allValid) {
         debug("skipping build of derivation '%s', someone beat us to it", worker.store.printStorePath(drvPath));
         outputLocks.setDeletion(true);
         done(BuildResult::AlreadyValid);
         return;
     }
 
-    missingPaths = drv->outputPaths(worker.store);
-    if (buildMode != bmCheck)
-        for (auto & i : validPaths) missingPaths.erase(i);
-
     /* If any of the outputs already exist but are not valid, delete
        them. */
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
-        if (worker.store.isValidPath(i.second.second)) continue;
-        debug("removing invalid path '%s'", worker.store.printStorePath(i.second.second));
-        deletePath(worker.store.Store::toRealPath(i.second.second));
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.known || status.known->isValid()) continue;
+        auto storePath = status.known->path;
+        debug("removing invalid path '%s'", worker.store.printStorePath(status.known->path));
+        deletePath(worker.store.Store::toRealPath(storePath));
     }
 
     /* Don't do a remote build if the derivation has the attribute
@@ -1477,7 +1584,6 @@ void DerivationGoal::tryToBuild()
        supported for local builds. */
     bool buildLocally = buildMode != bmNormal || parsedDrv->willBuildLocally(worker.store);
 
-    /* Is the build hook willing to accept this job? */
     if (!buildLocally) {
         switch (tryBuildHook()) {
             case rpAccept:
@@ -1661,8 +1767,10 @@ void DerivationGoal::buildDone()
             /* Move paths out of the chroot for easier debugging of
                build failures. */
             if (useChroot && buildMode == bmNormal)
-                for (auto & i : missingPaths) {
-                    auto p = worker.store.printStorePath(i);
+                for (auto & [_, status] : initialOutputs) {
+                    if (!status.known) continue;
+                    if (buildMode != bmCheck && status.known->isValid()) continue;
+                    auto p = worker.store.printStorePath(status.known->path);
                     if (pathExists(chrootRootDir + p))
                         rename((chrootRootDir + p).c_str(), p.c_str());
                 }
@@ -1692,7 +1800,10 @@ void DerivationGoal::buildDone()
                 fmt("running post-build-hook '%s'", settings.postBuildHook),
                 Logger::Fields{worker.store.printStorePath(drvPath)});
             PushActivity pact(act.id);
-            auto outputPaths = drv->outputPaths(worker.store);
+            StorePathSet outputPaths;
+            for (auto i : drv->outputs) {
+                outputPaths.insert(finalOutputs.at(i.first));
+            }
             std::map<std::string, std::string> hookEnvironment = getEnv();
 
             hookEnvironment.emplace("DRV_PATH", worker.store.printStorePath(drvPath));
@@ -1868,7 +1979,15 @@ HookReply DerivationGoal::tryBuildHook()
 
     /* Tell the hooks the missing outputs that have to be copied back
        from the remote system. */
-    writeStorePaths(worker.store, hook->sink, missingPaths);
+    {
+        StorePathSet missingPaths;
+        for (auto & [_, status] : initialOutputs) {
+            if (!status.known) continue;
+            if (buildMode != bmCheck && status.known->isValid()) continue;
+            missingPaths.insert(status.known->path);
+        }
+        writeStorePaths(worker.store, hook->sink, missingPaths);
+    }
 
     hook->sink = FdSink();
     hook->toHook.writeSide = -1;
@@ -1919,8 +2038,15 @@ StorePathSet DerivationGoal::exportReferences(const StorePathSet & storePaths)
     for (auto & j : paths2) {
         if (j.isDerivation()) {
             Derivation drv = worker.store.derivationFromPath(j);
-            for (auto & k : drv.outputsAndPaths(worker.store))
-                worker.store.computeFSClosure(k.second.second, paths);
+            for (auto & k : drv.outputsAndOptPaths(worker.store)) {
+                if (!k.second.second)
+                    /* FIXME: I am confused why we are calling
+                       `computeFSClosure` on the output path, rather than
+                       derivation itself. That doesn't seem right to me, so I
+                       won't try to implemented this for CA derivations. */
+                    throw UnimplementedError("exportReferences on CA derivations is not yet implemented");
+                worker.store.computeFSClosure(*k.second.second, paths);
+            }
         }
     }
 
@@ -1951,7 +2077,7 @@ void linkOrCopy(const Path & from, const Path & to)
            file (e.g. 32000 of ext3), which is quite possible after a
            'nix-store --optimise'. FIXME: actually, why don't we just
            bind-mount in this case?
-           
+
            It can also fail with EPERM in BeegFS v7 and earlier versions
            which don't allow hard-links to other directories */
         if (errno != EMLINK && errno != EPERM)
@@ -2013,9 +2139,64 @@ void DerivationGoal::startBuilder()
 
     chownToBuilder(tmpDir);
 
-    /* Substitute output placeholders with the actual output paths. */
-    for (auto & output : drv->outputsAndPaths(worker.store))
-        inputRewrites[hashPlaceholder(output.first)] = worker.store.printStorePath(output.second.second);
+    for (auto & [outputName, status] : initialOutputs) {
+        /* Set scratch path we'll actually use during the build.
+
+           If we're not doing a chroot build, but we have some valid
+           output paths.  Since we can't just overwrite or delete
+           them, we have to do hash rewriting: i.e. in the
+           environment/arguments passed to the build, we replace the
+           hashes of the valid outputs with unique dummy strings;
+           after the build, we discard the redirected outputs
+           corresponding to the valid outputs, and rewrite the
+           contents of the new outputs to replace the dummy strings
+           with the actual hashes. */
+        auto scratchPath =
+            !status.known
+                ? makeFallbackPath(outputName)
+            : !needsHashRewrite()
+                /* Can always use original path in sandbox */
+                ? status.known->path
+            : !status.known->isPresent()
+                /* If path doesn't yet exist can just use it */
+                ? status.known->path
+            : buildMode != bmRepair && !status.known->isValid()
+                /* If we aren't repairing we'll delete a corrupted path, so we
+                   can use original path */
+                ? status.known->path
+            :   /* If we are repairing or the path is totally valid, we'll need
+                   to use a temporary path */
+                makeFallbackPath(status.known->path);
+        scratchOutputs.insert_or_assign(outputName, scratchPath);
+
+        /* A non-removed corrupted path needs to be stored here, too */
+        if (buildMode == bmRepair && !status.known->isValid())
+            redirectedBadOutputs.insert(status.known->path);
+
+        /* Substitute output placeholders with the scratch output paths.
+           We'll use during the build. */
+        inputRewrites[hashPlaceholder(outputName)] = worker.store.printStorePath(scratchPath);
+
+        /* Additional tasks if we know the final path a priori. */
+        if (!status.known) continue;
+        auto fixedFinalPath = status.known->path;
+
+        /* Additional tasks if the final and scratch are both known and
+           differ. */
+        if (fixedFinalPath == scratchPath) continue;
+
+        /* Ensure scratch path is ours to use. */
+        deletePath(worker.store.printStorePath(scratchPath));
+
+        /* Rewrite and unrewrite paths */
+        {
+            std::string h1 { fixedFinalPath.hashPart() };
+            std::string h2 { scratchPath.hashPart() };
+            inputRewrites[h1] = h2;
+        }
+
+        redirectedOutputs.insert_or_assign(std::move(fixedFinalPath), std::move(scratchPath));
+    }
 
     /* Construct the environment passed to the builder. */
     initEnv();
@@ -2199,8 +2380,15 @@ void DerivationGoal::startBuilder()
            rebuilding a path that is in settings.dirsInChroot
            (typically the dependencies of /bin/sh).  Throw them
            out. */
-        for (auto & i : drv->outputsAndPaths(worker.store))
-            dirsInChroot.erase(worker.store.printStorePath(i.second.second));
+        for (auto & i : drv->outputsAndOptPaths(worker.store)) {
+            /* If the name isn't known a priori (i.e. floating
+               content-addressed derivation), the temporary location we use
+               should be fresh.  Freshness means it is impossible that the path
+               is already in the sandbox, so we don't need to worry about
+               removing it.  */
+            if (i.second.second)
+                dirsInChroot.erase(worker.store.printStorePath(*i.second.second));
+        }
 
 #elif __APPLE__
         /* We don't really have any parent prep work to do (yet?)
@@ -2210,33 +2398,8 @@ void DerivationGoal::startBuilder()
 #endif
     }
 
-    if (needsHashRewrite()) {
-
-        if (pathExists(homeDir))
-            throw Error("home directory '%1%' exists; please remove it to assure purity of builds without sandboxing", homeDir);
-
-        /* We're not doing a chroot build, but we have some valid
-           output paths.  Since we can't just overwrite or delete
-           them, we have to do hash rewriting: i.e. in the
-           environment/arguments passed to the build, we replace the
-           hashes of the valid outputs with unique dummy strings;
-           after the build, we discard the redirected outputs
-           corresponding to the valid outputs, and rewrite the
-           contents of the new outputs to replace the dummy strings
-           with the actual hashes. */
-        if (validPaths.size() > 0)
-            for (auto & i : validPaths)
-                addHashRewrite(i);
-
-        /* If we're repairing, then we don't want to delete the
-           corrupt outputs in advance.  So rewrite them as well. */
-        if (buildMode == bmRepair)
-            for (auto & i : missingPaths)
-                if (worker.store.isValidPath(i) && pathExists(worker.store.printStorePath(i))) {
-                    addHashRewrite(i);
-                    redirectedBadOutputs.insert(i);
-                }
-    }
+    if (needsHashRewrite() && pathExists(homeDir))
+        throw Error("home directory '%1%' exists; please remove it to assure purity of builds without sandboxing", homeDir);
 
     if (useChroot && settings.preBuildHook != "" && dynamic_cast<Derivation *>(drv.get())) {
         printMsg(lvlChatty, format("executing pre-build hook '%1%'")
@@ -2612,8 +2775,11 @@ void DerivationGoal::writeStructuredAttrs()
 
     /* Add an "outputs" object containing the output paths. */
     nlohmann::json outputs;
-    for (auto & i : drv->outputsAndPaths(worker.store))
-        outputs[i.first] = rewriteStrings(worker.store.printStorePath(i.second.second), inputRewrites);
+    for (auto & i : drv->outputs) {
+        /* The placeholder must have a rewrite, so we use it to cover both the
+           cases where we know or don't know the output path ahead of time. */
+        outputs[i.first] = rewriteStrings(hashPlaceholder(i.first), inputRewrites);
+    }
     json["outputs"] = outputs;
 
     /* Handle exportReferencesGraph. */
@@ -2706,18 +2872,23 @@ void DerivationGoal::writeStructuredAttrs()
     chownToBuilder(tmpDir + "/.attrs.sh");
 }
 
+struct RestrictedStoreConfig : LocalFSStoreConfig
+{
+    using LocalFSStoreConfig::LocalFSStoreConfig;
+    const std::string name() { return "Restricted Store"; }
+};
 
 /* A wrapper around LocalStore that only allows building/querying of
    paths that are in the input closures of the build or were added via
    recursive Nix calls. */
-struct RestrictedStore : public LocalFSStore
+struct RestrictedStore : public LocalFSStore, public virtual RestrictedStoreConfig
 {
     ref<LocalStore> next;
 
     DerivationGoal & goal;
 
     RestrictedStore(const Params & params, ref<LocalStore> next, DerivationGoal & goal)
-        : Store(params), LocalFSStore(params), next(next), goal(goal)
+        : StoreConfig(params), Store(params), LocalFSStore(params), next(next), goal(goal)
     { }
 
     Path getRealStoreDir() override
@@ -2815,19 +2986,20 @@ struct RestrictedStore : public LocalFSStore
         StorePathSet newPaths;
 
         for (auto & path : paths) {
-            if (path.path.isDerivation()) {
-                if (!goal.isAllowed(path.path))
-                    throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
-                auto drv = derivationFromPath(path.path);
-                for (auto & output : drv.outputsAndPaths(*this))
-                    if (wantOutput(output.first, path.outputs))
-                        newPaths.insert(output.second.second);
-            } else if (!goal.isAllowed(path.path))
+            if (!goal.isAllowed(path.path))
                 throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
         }
 
         next->buildPaths(paths, buildMode);
 
+        for (auto & path : paths) {
+            if (!path.path.isDerivation()) continue;
+            auto outputs = next->queryDerivationOutputMap(path.path);
+            for (auto & output : outputs)
+                if (wantOutput(output.first, path.outputs))
+                    newPaths.insert(output.second);
+        }
+
         StorePathSet closure;
         next->computeFSClosure(newPaths, closure);
         for (auto & path : closure)
@@ -3444,14 +3616,10 @@ void DerivationGoal::runChild()
                 if (derivationIsImpure(derivationType))
                     sandboxProfile += "(import \"sandbox-network.sb\")\n";
 
-                /* Our rwx outputs */
+                /* Add the output paths we'll use at build-time to the chroot */
                 sandboxProfile += "(allow file-read* file-write* process-exec\n";
-                for (auto & i : missingPaths)
-                    sandboxProfile += fmt("\t(subpath \"%s\")\n", worker.store.printStorePath(i));
-
-                /* Also add redirected outputs to the chroot */
-                for (auto & i : redirectedOutputs)
-                    sandboxProfile += fmt("\t(subpath \"%s\")\n", worker.store.printStorePath(i.second));
+                for (auto & [_, path] : scratchOutputs)
+                    sandboxProfile += fmt("\t(subpath \"%s\")\n", worker.store.printStorePath(path));
 
                 sandboxProfile += ")\n";
 
@@ -3574,23 +3742,6 @@ void DerivationGoal::runChild()
 }
 
 
-/* Parse a list of reference specifiers.  Each element must either be
-   a store path, or the symbolic name of the output of the derivation
-   (such as `out'). */
-StorePathSet parseReferenceSpecifiers(Store & store, const BasicDerivation & drv, const Strings & paths)
-{
-    StorePathSet result;
-    for (auto & i : paths) {
-        if (store.isStorePath(i))
-            result.insert(store.parseStorePath(i));
-        else if (drv.outputs.count(i))
-            result.insert(drv.outputs.find(i)->second.path(store, drv.name));
-        else throw BuildError("derivation contains an illegal reference specifier '%s'", i);
-    }
-    return result;
-}
-
-
 static void moveCheckToStore(const Path & src, const Path & dst)
 {
     /* For the rename of directory to succeed, we must be running as root or
@@ -3618,11 +3769,17 @@ void DerivationGoal::registerOutputs()
 {
     /* When using a build hook, the build hook can register the output
        as valid (by doing `nix-store --import').  If so we don't have
-       to do anything here. */
+       to do anything here.
+
+       We can only early return when the outputs are known a priori. For
+       floating content-addressed derivations this isn't the case.
+     */
     if (hook) {
         bool allValid = true;
-        for (auto & i : drv->outputsAndPaths(worker.store))
-            if (!worker.store.isValidPath(i.second.second)) allValid = false;
+        for (auto & i : drv->outputsAndOptPaths(worker.store)) {
+            if (!i.second.second || !worker.store.isValidPath(*i.second.second))
+                allValid = false;
+        }
         if (allValid) return;
     }
 
@@ -3643,47 +3800,51 @@ void DerivationGoal::registerOutputs()
        Nix calls. */
     StorePathSet referenceablePaths;
     for (auto & p : inputPaths) referenceablePaths.insert(p);
-    for (auto & i : drv->outputsAndPaths(worker.store)) referenceablePaths.insert(i.second.second);
+    for (auto & i : scratchOutputs) referenceablePaths.insert(i.second);
     for (auto & p : addedPaths) referenceablePaths.insert(p);
 
-    /* Check whether the output paths were created, and grep each
-       output path to determine what other paths it references.  Also make all
-       output paths read-only. */
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
-        auto path = worker.store.printStorePath(i.second.second);
-        if (!missingPaths.count(i.second.second)) continue;
-
-        Path actualPath = path;
-        if (needsHashRewrite()) {
-            auto r = redirectedOutputs.find(i.second.second);
-            if (r != redirectedOutputs.end()) {
-                auto redirected = worker.store.Store::toRealPath(r->second);
-                if (buildMode == bmRepair
-                    && redirectedBadOutputs.count(i.second.second)
-                    && pathExists(redirected))
-                    replaceValidPath(path, redirected);
-                if (buildMode == bmCheck)
-                    actualPath = redirected;
-            }
-        } else if (useChroot) {
-            actualPath = chrootRootDir + path;
-            if (pathExists(actualPath)) {
-                /* Move output paths from the chroot to the Nix store. */
-                if (buildMode == bmRepair)
-                    replaceValidPath(path, actualPath);
-                else
-                    if (buildMode != bmCheck && rename(actualPath.c_str(), worker.store.toRealPath(path).c_str()) == -1)
-                        throw SysError("moving build output '%1%' from the sandbox to the Nix store", path);
-            }
-            if (buildMode != bmCheck) actualPath = worker.store.toRealPath(path);
+    /* FIXME `needsHashRewrite` should probably be removed and we get to the
+       real reason why we aren't using the chroot dir */
+    auto toRealPathChroot = [&](const Path & p) -> Path {
+        return useChroot && !needsHashRewrite()
+            ? chrootRootDir + p
+            : worker.store.toRealPath(p);
+    };
+
+    /* Check whether the output paths were created, and make all
+       output paths read-only.  Then get the references of each output (that we
+       might need to register), so we can topologically sort them. For the ones
+       that are most definitely already installed, we just store their final
+       name so we can also use it in rewrites. */
+    StringSet outputsToSort;
+    struct AlreadyRegistered { StorePath path; };
+    struct PerhapsNeedToRegister { StorePathSet refs; };
+    std::map<std::string, std::variant<AlreadyRegistered, PerhapsNeedToRegister>> outputReferencesIfUnregistered;
+    std::map<std::string, struct stat> outputStats;
+    for (auto & [outputName, _] : drv->outputs) {
+        auto actualPath = toRealPathChroot(worker.store.printStorePath(scratchOutputs.at(outputName)));
+
+        outputsToSort.insert(outputName);
+
+        /* Updated wanted info to remove the outputs we definitely don't need to register */
+        auto & initialInfo = initialOutputs.at(outputName);
+
+        /* Don't register if already valid, and not checking */
+        initialInfo.wanted = buildMode == bmCheck
+            || !(initialInfo.known && initialInfo.known->isValid());
+        if (!initialInfo.wanted) {
+            outputReferencesIfUnregistered.insert_or_assign(
+                outputName,
+                AlreadyRegistered { .path = initialInfo.known->path });
+            continue;
         }
 
         struct stat st;
         if (lstat(actualPath.c_str(), &st) == -1) {
             if (errno == ENOENT)
                 throw BuildError(
-                    "builder for '%s' failed to produce output path '%s'",
-                    worker.store.printStorePath(drvPath), path);
+                    "builder for '%s' failed to produce output path for output '%s' at '%s'",
+                    worker.store.printStorePath(drvPath), outputName, actualPath);
             throw SysError("getting attributes of path '%s'", actualPath);
         }
 
@@ -3694,116 +3855,281 @@ void DerivationGoal::registerOutputs()
            user. */
         if ((!S_ISLNK(st.st_mode) && (st.st_mode & (S_IWGRP | S_IWOTH))) ||
             (buildUser && st.st_uid != buildUser->getUID()))
-            throw BuildError("suspicious ownership or permission on '%1%'; rejecting this build output", path);
+            throw BuildError(
+                    "suspicious ownership or permission on '%s' for output '%s'; rejecting this build output",
+                    actualPath, outputName);
 #endif
 
-        /* Apply hash rewriting if necessary. */
-        bool rewritten = false;
-        if (!outputRewrites.empty()) {
-            logWarning({
-                .name = "Rewriting hashes",
-                .hint = hintfmt("rewriting hashes in '%1%'; cross fingers", path)
-            });
+        /* Canonicalise first.  This ensures that the path we're
+           rewriting doesn't contain a hard link to /etc/shadow or
+           something like that. */
+        canonicalisePathMetaData(actualPath, buildUser ? buildUser->getUID() : -1, inodesSeen);
 
-            /* Canonicalise first.  This ensures that the path we're
-               rewriting doesn't contain a hard link to /etc/shadow or
-               something like that. */
-            canonicalisePathMetaData(actualPath, buildUser ? buildUser->getUID() : -1, inodesSeen);
+        debug("scanning for references for output %1 in temp location '%1%'", outputName, actualPath);
 
-            /* FIXME: this is in-memory. */
-            StringSink sink;
-            dumpPath(actualPath, sink);
-            deletePath(actualPath);
-            sink.s = make_ref<std::string>(rewriteStrings(*sink.s, outputRewrites));
-            StringSource source(*sink.s);
-            restorePath(actualPath, source);
+        /* Pass blank Sink as we are not ready to hash data at this stage. */
+        NullSink blank;
+        auto references = worker.store.parseStorePathSet(
+            scanForReferences(blank, actualPath, worker.store.printStorePathSet(referenceablePaths)));
 
-            rewritten = true;
-        }
-
-        /* Check that fixed-output derivations produced the right
-           outputs (i.e., the content hash should match the specified
-           hash). */
-        std::optional<ContentAddress> ca;
+        outputReferencesIfUnregistered.insert_or_assign(
+            outputName,
+            PerhapsNeedToRegister { .refs = references });
+        outputStats.insert_or_assign(outputName, std::move(st));
+    }
 
-        if (! std::holds_alternative<DerivationOutputInputAddressed>(i.second.first.output)) {
-            DerivationOutputCAFloating outputHash;
-            std::visit(overloaded {
-                [&](DerivationOutputInputAddressed doi) {
-                    assert(false); // Enclosing `if` handles this case in other branch
+    auto sortedOutputNames = topoSort(outputsToSort,
+        {[&](const std::string & name) {
+            return std::visit(overloaded {
+                /* Since we'll use the already installed versions of these, we
+                   can treat them as leaves and ignore any references they
+                   have. */
+                [&](AlreadyRegistered _) { return StringSet {}; },
+                [&](PerhapsNeedToRegister refs) {
+                    StringSet referencedOutputs;
+                    /* FIXME build inverted map up front so no quadratic waste here */
+                    for (auto & r : refs.refs)
+                        for (auto & [o, p] : scratchOutputs)
+                            if (r == p)
+                                referencedOutputs.insert(o);
+                    return referencedOutputs;
                 },
-                [&](DerivationOutputCAFixed dof) {
-                    outputHash = DerivationOutputCAFloating {
-                        .method = dof.hash.method,
-                        .hashType = dof.hash.hash.type,
-                    };
-                },
-                [&](DerivationOutputCAFloating dof) {
-                    outputHash = dof;
-                },
-            }, i.second.first.output);
+            }, outputReferencesIfUnregistered.at(name));
+        }},
+        {[&](const std::string & path, const std::string & parent) {
+            // TODO with more -vvvv also show the temporary paths for manual inspection.
+            return BuildError(
+                "cycle detected in build of '%s' in the references of output '%s' from output '%s'",
+                worker.store.printStorePath(drvPath), path, parent);
+        }});
+
+    std::reverse(sortedOutputNames.begin(), sortedOutputNames.end());
+
+    for (auto & outputName : sortedOutputNames) {
+        auto output = drv->outputs.at(outputName);
+        auto & scratchPath = scratchOutputs.at(outputName);
+        auto actualPath = toRealPathChroot(worker.store.printStorePath(scratchPath));
+
+        auto finish = [&](StorePath finalStorePath) {
+            /* Store the final path */
+            finalOutputs.insert_or_assign(outputName, finalStorePath);
+            /* The rewrite rule will be used in downstream outputs that refer to
+               use. This is why the topological sort is essential to do first
+               before this for loop. */
+            if (scratchPath != finalStorePath)
+                outputRewrites[std::string { scratchPath.hashPart() }] = std::string { finalStorePath.hashPart() };
+        };
 
+        bool rewritten = false;
+        std::optional<StorePathSet> referencesOpt = std::visit(overloaded {
+            [&](AlreadyRegistered skippedFinalPath) -> std::optional<StorePathSet> {
+                finish(skippedFinalPath.path);
+                return std::nullopt;
+            },
+            [&](PerhapsNeedToRegister r) -> std::optional<StorePathSet> {
+                return r.refs;
+            },
+        }, outputReferencesIfUnregistered.at(outputName));
+
+        if (!referencesOpt)
+            continue;
+        auto references = *referencesOpt;
+
+        auto rewriteOutput = [&]() {
+            /* Apply hash rewriting if necessary. */
+            if (!outputRewrites.empty()) {
+                logWarning({
+                    .name = "Rewriting hashes",
+                    .hint = hintfmt("rewriting hashes in '%1%'; cross fingers", actualPath),
+                });
+
+                /* FIXME: this is in-memory. */
+                StringSink sink;
+                dumpPath(actualPath, sink);
+                deletePath(actualPath);
+                sink.s = make_ref<std::string>(rewriteStrings(*sink.s, outputRewrites));
+                StringSource source(*sink.s);
+                restorePath(actualPath, source);
+
+                rewritten = true;
+            }
+        };
+
+        auto rewriteRefs = [&]() -> std::pair<bool, StorePathSet> {
+            /* In the CA case, we need the rewritten refs to calculate the
+               final path, therefore we look for a *non-rewritten
+               self-reference, and use a bool rather try to solve the
+               computationally intractable fixed point. */
+            std::pair<bool, StorePathSet> res {
+                false,
+                {},
+            };
+            for (auto & r : references) {
+                auto name = r.name();
+                auto origHash = std::string { r.hashPart() };
+                if (r == scratchPath)
+                    res.first = true;
+                else if (outputRewrites.count(origHash) == 0)
+                    res.second.insert(r);
+                else {
+                    std::string newRef = outputRewrites.at(origHash);
+                    newRef += '-';
+                    newRef += name;
+                    res.second.insert(StorePath { newRef });
+                }
+            }
+            return res;
+        };
+
+        auto newInfoFromCA = [&](const DerivationOutputCAFloating outputHash) -> ValidPathInfo {
+            auto & st = outputStats.at(outputName);
             if (outputHash.method == FileIngestionMethod::Flat) {
                 /* The output path should be a regular file without execute permission. */
                 if (!S_ISREG(st.st_mode) || (st.st_mode & S_IXUSR) != 0)
                     throw BuildError(
                         "output path '%1%' should be a non-executable regular file "
                         "since recursive hashing is not enabled (outputHashMode=flat)",
-                        path);
+                        actualPath);
             }
-
-            /* 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.hashType, actualPath).first
-                : hashFile(outputHash.hashType, actualPath);
-
-            auto dest = worker.store.makeFixedOutputPath(outputHash.method, h2, i.second.second.name());
-
-            // true if either floating CA, or incorrect fixed hash.
-            bool needsMove = true;
-
-            if (auto p = std::get_if<DerivationOutputCAFixed>(& i.second.first.output)) {
-              Hash & h = p->hash.hash;
-              if (h != h2) {
-
-                /* Throw an error after registering the path as
-                   valid. */
-                worker.hashMismatch = true;
-                delayedException = std::make_exception_ptr(
-                    BuildError("hash mismatch in fixed-output derivation '%s':\n  wanted: %s\n  got:    %s",
-                        worker.store.printStorePath(dest),
-                        h.to_string(SRI, true),
-                        h2.to_string(SRI, true)));
-              } else {
-                  // matched the fixed hash, so no move needed.
-                  needsMove = false;
-              }
+            rewriteOutput();
+            /* FIXME optimize and deduplicate with addToStore */
+            std::string oldHashPart { scratchPath.hashPart() };
+            HashModuloSink caSink { outputHash.hashType, oldHashPart };
+            switch (outputHash.method) {
+            case FileIngestionMethod::Recursive:
+                dumpPath(actualPath, caSink);
+                break;
+            case FileIngestionMethod::Flat:
+                readFile(actualPath, caSink);
+                break;
             }
+            auto got = caSink.finish().first;
+            auto refs = rewriteRefs();
+            HashModuloSink narSink { htSHA256, oldHashPart };
+            dumpPath(actualPath, narSink);
+            auto narHashAndSize = narSink.finish();
+            ValidPathInfo newInfo0 {
+                worker.store.makeFixedOutputPath(
+                    outputHash.method,
+                    got,
+                    outputPathName(drv->name, outputName),
+                    refs.second,
+                    refs.first),
+                narHashAndSize.first,
+            };
+            newInfo0.narSize = narHashAndSize.second;
+            newInfo0.ca = FixedOutputHash {
+                .method = outputHash.method,
+                .hash = got,
+            };
+            newInfo0.references = refs.second;
+            if (refs.first)
+                newInfo0.references.insert(newInfo0.path);
 
-            if (needsMove) {
-                Path actualDest = worker.store.Store::toRealPath(dest);
+            assert(newInfo0.ca);
+            return newInfo0;
+        };
 
-                if (worker.store.isValidPath(dest))
-                    std::rethrow_exception(delayedException);
+        ValidPathInfo newInfo = std::visit(overloaded {
+            [&](DerivationOutputInputAddressed output) {
+                /* input-addressed case */
+                auto requiredFinalPath = output.path;
+                /* Preemtively add rewrite rule for final hash, as that is
+                   what the NAR hash will use rather than normalized-self references */
+                if (scratchPath != requiredFinalPath)
+                    outputRewrites.insert_or_assign(
+                        std::string { scratchPath.hashPart() },
+                        std::string { requiredFinalPath.hashPart() });
+                rewriteOutput();
+                auto narHashAndSize = hashPath(htSHA256, actualPath);
+                ValidPathInfo newInfo0 { requiredFinalPath, narHashAndSize.first };
+                newInfo0.narSize = narHashAndSize.second;
+                auto refs = rewriteRefs();
+                newInfo0.references = refs.second;
+                if (refs.first)
+                    newInfo0.references.insert(newInfo0.path);
+                return newInfo0;
+            },
+            [&](DerivationOutputCAFixed dof) {
+                auto newInfo0 = newInfoFromCA(DerivationOutputCAFloating {
+                    .method = dof.hash.method,
+                    .hashType = dof.hash.hash.type,
+                });
 
-                if (actualPath != actualDest) {
-                    PathLocks outputLocks({actualDest});
-                    deletePath(actualDest);
-                    if (rename(actualPath.c_str(), actualDest.c_str()) == -1)
-                        throw SysError("moving '%s' to '%s'", actualPath, worker.store.printStorePath(dest));
+                /* Check wanted hash */
+                Hash & wanted = dof.hash.hash;
+                assert(newInfo0.ca);
+                auto got = getContentAddressHash(*newInfo0.ca);
+                if (wanted != got) {
+                    /* Throw an error after registering the path as
+                       valid. */
+                    worker.hashMismatch = true;
+                    delayedException = std::make_exception_ptr(
+                        BuildError("hash mismatch in fixed-output derivation '%s':\n  wanted: %s\n  got:    %s",
+                            worker.store.printStorePath(drvPath),
+                            wanted.to_string(SRI, true),
+                            got.to_string(SRI, true)));
                 }
+                return newInfo0;
+            },
+            [&](DerivationOutputCAFloating dof) {
+                return newInfoFromCA(dof);
+            },
+        }, output.output);
+
+        /* Calculate where we'll move the output files. In the checking case we
+           will leave leave them where they are, for now, rather than move to
+           their usual "final destination" */
+        auto finalDestPath = worker.store.printStorePath(newInfo.path);
+
+        /* Lock final output path, if not already locked. This happens with
+           floating CA derivations and hash-mismatching fixed-output
+           derivations. */
+        PathLocks dynamicOutputLock;
+        auto optFixedPath = output.path(worker.store, drv->name, outputName);
+        if (!optFixedPath ||
+            worker.store.printStorePath(*optFixedPath) != finalDestPath)
+        {
+            assert(newInfo.ca);
+            dynamicOutputLock.lockPaths({worker.store.toRealPath(finalDestPath)});
+        }
 
-                path = worker.store.printStorePath(dest);
-                actualPath = actualDest;
+        /* Move files, if needed */
+        if (worker.store.toRealPath(finalDestPath) != actualPath) {
+            if (buildMode == bmRepair) {
+                /* Path already exists, need to replace it */
+                replaceValidPath(worker.store.toRealPath(finalDestPath), actualPath);
+                actualPath = worker.store.toRealPath(finalDestPath);
+            } else if (buildMode == bmCheck) {
+                /* Path already exists, and we want to compare, so we leave out
+                   new path in place. */
+            } else if (worker.store.isValidPath(newInfo.path)) {
+                /* Path already exists because CA path produced by something
+                   else. No moving needed. */
+                assert(newInfo.ca);
+            } else {
+                /* Temporarily add write perm so we can move, will be fixed
+                   later. */
+                {
+                    struct stat st;
+                    auto & mode = st.st_mode;
+                    if (lstat(actualPath.c_str(), &st))
+                        throw SysError("getting attributes of path '%1%'", actualPath);
+                    mode |= 0200;
+                    /* Try to change the perms, but only if the file isn't a
+                       symlink as symlinks permissions are mostly ignored and
+                       calling `chmod` on it will just forward the call to the
+                       target of the link. */
+                    if (!S_ISLNK(st.st_mode))
+                        if (chmod(actualPath.c_str(), mode) == -1)
+                            throw SysError("changing mode of '%1%' to %2$o", actualPath, mode);
+                }
+                if (rename(
+                        actualPath.c_str(),
+                        worker.store.toRealPath(finalDestPath).c_str()) == -1)
+                    throw SysError("moving build output '%1%' from it's temporary location to the Nix store", finalDestPath);
+                actualPath = worker.store.toRealPath(finalDestPath);
             }
-            else
-                assert(worker.store.parseStorePath(path) == dest);
-
-            ca = FixedOutputHash {
-                .method = outputHash.method,
-                .hash = h2,
-            };
         }
 
         /* Get rid of all weird permissions.  This also checks that
@@ -3811,45 +4137,33 @@ void DerivationGoal::registerOutputs()
         canonicalisePathMetaData(actualPath,
             buildUser && !rewritten ? buildUser->getUID() : -1, inodesSeen);
 
-        /* For this output path, find the references to other paths
-           contained in it.  Compute the SHA-256 NAR hash at the same
-           time.  The hash is stored in the database so that we can
-           verify later on whether nobody has messed with the store. */
-        debug("scanning for references inside '%1%'", path);
-        // HashResult hash;
-        auto pathSetAndHash = scanForReferences(actualPath, worker.store.printStorePathSet(referenceablePaths));
-        auto references = worker.store.parseStorePathSet(pathSetAndHash.first);
-        HashResult hash = pathSetAndHash.second;
-
         if (buildMode == bmCheck) {
-            if (!worker.store.isValidPath(worker.store.parseStorePath(path))) continue;
-            ValidPathInfo info(*worker.store.queryPathInfo(worker.store.parseStorePath(path)));
-            if (hash.first != info.narHash) {
+            if (!worker.store.isValidPath(newInfo.path)) continue;
+            ValidPathInfo oldInfo(*worker.store.queryPathInfo(newInfo.path));
+            if (newInfo.narHash != oldInfo.narHash) {
                 worker.checkMismatch = true;
                 if (settings.runDiffHook || settings.keepFailed) {
-                    Path dst = worker.store.toRealPath(path + checkSuffix);
+                    Path dst = worker.store.toRealPath(finalDestPath + checkSuffix);
                     deletePath(dst);
                     moveCheckToStore(actualPath, dst);
 
                     handleDiffHook(
                         buildUser ? buildUser->getUID() : getuid(),
                         buildUser ? buildUser->getGID() : getgid(),
-                        path, dst, worker.store.printStorePath(drvPath), tmpDir);
+                        finalDestPath, dst, worker.store.printStorePath(drvPath), tmpDir);
 
                     throw NotDeterministic("derivation '%s' may not be deterministic: output '%s' differs from '%s'",
-                        worker.store.printStorePath(drvPath), worker.store.toRealPath(path), dst);
+                        worker.store.printStorePath(drvPath), worker.store.toRealPath(finalDestPath), dst);
                 } else
                     throw NotDeterministic("derivation '%s' may not be deterministic: output '%s' differs",
-                        worker.store.printStorePath(drvPath), worker.store.toRealPath(path));
+                        worker.store.printStorePath(drvPath), worker.store.toRealPath(finalDestPath));
             }
 
             /* Since we verified the build, it's now ultimately trusted. */
-            if (!info.ultimate) {
-                info.ultimate = true;
-                worker.store.signPathInfo(info);
-                ValidPathInfos infos;
-                infos.push_back(std::move(info));
-                worker.store.registerValidPaths(infos);
+            if (!oldInfo.ultimate) {
+                oldInfo.ultimate = true;
+                worker.store.signPathInfo(oldInfo);
+                worker.store.registerValidPaths({ std::move(oldInfo) });
             }
 
             continue;
@@ -3866,26 +4180,22 @@ void DerivationGoal::registerOutputs()
 
         if (curRound == nrRounds) {
             worker.store.optimisePath(actualPath); // FIXME: combine with scanForReferences()
-            worker.markContentsGood(worker.store.parseStorePath(path));
+            worker.markContentsGood(newInfo.path);
         }
 
-        ValidPathInfo info {
-            worker.store.parseStorePath(path),
-            hash.first,
-        };
-        info.narSize = hash.second;
-        info.references = std::move(references);
-        info.deriver = drvPath;
-        info.ultimate = true;
-        info.ca = ca;
-        worker.store.signPathInfo(info);
-
-        if (!info.references.empty()) {
-            // FIXME don't we have an experimental feature for fixed output with references?
-            info.ca = {};
-        }
+        newInfo.deriver = drvPath;
+        newInfo.ultimate = true;
+        worker.store.signPathInfo(newInfo);
+
+        finish(newInfo.path);
 
-        infos.emplace(i.first, std::move(info));
+        /* If it's a CA path, register it right away. This is necessary if it
+           isn't statically known so that we can safely unlock the path before
+           the next iteration */
+        if (newInfo.ca)
+            worker.store.registerValidPaths({newInfo});
+
+        infos.emplace(outputName, std::move(newInfo));
     }
 
     if (buildMode == bmCheck) return;
@@ -3928,8 +4238,8 @@ void DerivationGoal::registerOutputs()
 
     /* If this is the first round of several, then move the output out of the way. */
     if (nrRounds > 1 && curRound == 1 && curRound < nrRounds && keepPreviousRound) {
-        for (auto & i : drv->outputsAndPaths(worker.store)) {
-            auto path = worker.store.printStorePath(i.second.second);
+        for (auto & [_, outputStorePath] : finalOutputs) {
+            auto path = worker.store.printStorePath(outputStorePath);
             Path prev = path + checkSuffix;
             deletePath(prev);
             Path dst = path + checkSuffix;
@@ -3946,8 +4256,8 @@ void DerivationGoal::registerOutputs()
     /* Remove the .check directories if we're done. FIXME: keep them
        if the result was not determistic? */
     if (curRound == nrRounds) {
-        for (auto & i : drv->outputsAndPaths(worker.store)) {
-            Path prev = worker.store.printStorePath(i.second.second) + checkSuffix;
+        for (auto & [_, outputStorePath] : finalOutputs) {
+            Path prev = worker.store.printStorePath(outputStorePath) + checkSuffix;
             deletePath(prev);
         }
     }
@@ -3955,16 +4265,28 @@ void DerivationGoal::registerOutputs()
     /* Register each output path as valid, and register the sets of
        paths referenced by each of them.  If there are cycles in the
        outputs, this will fail. */
-    {
-        ValidPathInfos infos2;
-        for (auto & i : infos) infos2.push_back(i.second);
-        worker.store.registerValidPaths(infos2);
+    ValidPathInfos infos2;
+    for (auto & [outputName, newInfo] : infos) {
+        infos2.push_back(newInfo);
     }
+    worker.store.registerValidPaths(infos2);
 
     /* In case of a fixed-output derivation hash mismatch, throw an
        exception now that we have registered the output as valid. */
     if (delayedException)
         std::rethrow_exception(delayedException);
+
+    /* If we made it this far, we are sure the output matches the derivation
+       (since the delayedException would be a fixed output CA mismatch). That
+       means it's safe to link the derivation to the output hash. We must do
+       that for floating CA derivations, which otherwise couldn't be cached,
+       but it's fine to do in all cases. */
+    for (auto & [outputName, newInfo] : infos) {
+        /* FIXME: we will want to track this mapping in the DB whether or
+           not we have a drv file. */
+        if (useDerivation)
+            worker.store.linkDeriverToPath(drvPath, outputName, newInfo.path);
+    }
 }
 
 
@@ -4033,7 +4355,17 @@ void DerivationGoal::checkOutputs(const std::map<Path, ValidPathInfo> & outputs)
             {
                 if (!value) return;
 
-                auto spec = parseReferenceSpecifiers(worker.store, *drv, *value);
+                /* Parse a list of reference specifiers.  Each element must
+                   either be a store path, or the symbolic name of the output
+                   of the derivation (such as `out'). */
+                StorePathSet spec;
+                for (auto & i : *value) {
+                    if (worker.store.isStorePath(i))
+                        spec.insert(worker.store.parseStorePath(i));
+                    else if (finalOutputs.count(i))
+                        spec.insert(finalOutputs.at(i));
+                    else throw BuildError("derivation contains an illegal reference specifier '%s'", i);
+                }
 
                 auto used = recursive
                     ? getClosure(info.path).first
@@ -4242,31 +4574,67 @@ void DerivationGoal::flushLine()
 }
 
 
-StorePathSet DerivationGoal::checkPathValidity(bool returnValid, bool checkHash)
+std::map<std::string, std::optional<StorePath>> DerivationGoal::queryPartialDerivationOutputMap()
 {
-    StorePathSet result;
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
-        if (!wantOutput(i.first, wantedOutputs)) continue;
-        bool good =
-            worker.store.isValidPath(i.second.second) &&
-            (!checkHash || worker.pathContentsGood(i.second.second));
-        if (good == returnValid) result.insert(i.second.second);
+    if (drv->type() != DerivationType::CAFloating) {
+        std::map<std::string, std::optional<StorePath>> res;
+        for (auto & [name, output] : drv->outputs)
+            res.insert_or_assign(name, output.path(worker.store, drv->name, name));
+        return res;
+    } else {
+        return worker.store.queryPartialDerivationOutputMap(drvPath);
     }
-    return result;
+}
+
+OutputPathMap DerivationGoal::queryDerivationOutputMap()
+{
+    if (drv->type() != DerivationType::CAFloating) {
+        OutputPathMap res;
+        for (auto & [name, output] : drv->outputsAndOptPaths(worker.store))
+            res.insert_or_assign(name, *output.second);
+        return res;
+    } else {
+        return worker.store.queryDerivationOutputMap(drvPath);
+    }
+}
+
+
+void DerivationGoal::checkPathValidity()
+{
+    bool checkHash = buildMode == bmRepair;
+    for (auto & i : queryPartialDerivationOutputMap()) {
+        InitialOutput info {
+            .wanted = wantOutput(i.first, wantedOutputs),
+        };
+        if (i.second) {
+            auto outputPath = *i.second;
+            info.known = {
+                .path = outputPath,
+                .status = !worker.store.isValidPath(outputPath)
+                    ? PathStatus::Absent
+                    : !checkHash || worker.pathContentsGood(outputPath)
+                    ? PathStatus::Valid
+                    : PathStatus::Corrupt,
+            };
+        }
+        initialOutputs.insert_or_assign(i.first, info);
+    }
+}
+
+
+StorePath DerivationGoal::makeFallbackPath(std::string_view outputName)
+{
+    return worker.store.makeStorePath(
+        "rewrite:" + std::string(drvPath.to_string()) + ":name:" + std::string(outputName),
+        Hash(htSHA256), outputPathName(drv->name, outputName));
 }
 
 
-void DerivationGoal::addHashRewrite(const StorePath & path)
+StorePath DerivationGoal::makeFallbackPath(const StorePath & path)
 {
-    auto h1 = std::string(((std::string_view) path.to_string()).substr(0, 32));
-    auto p = worker.store.makeStorePath(
+    return worker.store.makeStorePath(
         "rewrite:" + std::string(drvPath.to_string()) + ":" + std::string(path.to_string()),
         Hash(htSHA256), path.name());
-    auto h2 = std::string(((std::string_view) p.to_string()).substr(0, 32));
-    deletePath(worker.store.printStorePath(p));
-    inputRewrites[h1] = h2;
-    outputRewrites[h2] = h1;
-    redirectedOutputs.insert_or_assign(path, std::move(p));
 }
 
 
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index d263cf0c5..9d8ce5e36 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -7,7 +7,7 @@
 
 namespace nix {
 
-std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::string_view drvName) const
+std::optional<StorePath> DerivationOutput::path(const Store & store, std::string_view drvName, std::string_view outputName) const
 {
     return std::visit(overloaded {
         [](DerivationOutputInputAddressed doi) -> std::optional<StorePath> {
@@ -15,7 +15,7 @@ std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::str
         },
         [&](DerivationOutputCAFixed dof) -> std::optional<StorePath> {
             return {
-                store.makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName)
+                dof.path(store, drvName, outputName)
             };
         },
         [](DerivationOutputCAFloating dof) -> std::optional<StorePath> {
@@ -25,6 +25,13 @@ std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::str
 }
 
 
+StorePath DerivationOutputCAFixed::path(const Store & store, std::string_view drvName, std::string_view outputName) const {
+    return store.makeFixedOutputPath(
+        hash.method, hash.hash,
+        outputPathName(drvName, outputName));
+}
+
+
 bool derivationIsCA(DerivationType dt) {
     switch (dt) {
     case DerivationType::InputAddressed: return false;
@@ -106,12 +113,15 @@ static string parseString(std::istream & str)
     return res;
 }
 
+static void validatePath(std::string_view s) {
+    if (s.size() == 0 || s[0] != '/')
+        throw FormatError("bad path '%1%' in derivation", s);
+}
 
 static Path parsePath(std::istream & str)
 {
-    string s = parseString(str);
-    if (s.size() == 0 || s[0] != '/')
-        throw FormatError("bad path '%1%' in derivation", s);
+    auto s = parseString(str);
+    validatePath(s);
     return s;
 }
 
@@ -140,7 +150,7 @@ static StringSet parseStrings(std::istream & str, bool arePaths)
 
 
 static DerivationOutput parseDerivationOutput(const Store & store,
-    StorePath path, std::string_view hashAlgo, std::string_view hash)
+    std::string_view pathS, std::string_view hashAlgo, std::string_view hash)
 {
     if (hashAlgo != "") {
         auto method = FileIngestionMethod::Flat;
@@ -148,40 +158,45 @@ static DerivationOutput parseDerivationOutput(const Store & store,
             method = FileIngestionMethod::Recursive;
             hashAlgo = hashAlgo.substr(2);
         }
-        const HashType hashType = parseHashType(hashAlgo);
-
-        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
+        const auto hashType = parseHashType(hashAlgo);
+        if (hash != "") {
+            validatePath(pathS);
+            return DerivationOutput {
+                .output = DerivationOutputCAFixed {
+                    .hash = FixedOutputHash {
+                        .method = std::move(method),
+                        .hash = Hash::parseNonSRIUnprefixed(hash, hashType),
+                    },
+                },
+            };
+        } else {
+            settings.requireExperimentalFeature("ca-derivations");
+            assert(pathS == "");
+            return DerivationOutput {
+                .output = DerivationOutputCAFloating {
+                    .method = std::move(method),
+                    .hashType = std::move(hashType),
+                },
+            };
+        }
+    } else {
+        validatePath(pathS);
         return DerivationOutput {
             .output = DerivationOutputInputAddressed {
-                .path = std::move(path),
+                .path = store.parseStorePath(pathS),
             }
         };
+    }
 }
 
 static DerivationOutput parseDerivationOutput(const Store & store, std::istringstream & str)
 {
-    expect(str, ","); auto path = store.parseStorePath(parsePath(str));
+    expect(str, ","); const auto pathS = parseString(str);
     expect(str, ","); const auto hashAlgo = parseString(str);
     expect(str, ","); const auto hash = parseString(str);
     expect(str, ")");
 
-    return parseDerivationOutput(store, std::move(path), hashAlgo, hash);
+    return parseDerivationOutput(store, pathS, hashAlgo, hash);
 }
 
 
@@ -294,17 +309,19 @@ string Derivation::unparse(const Store & store, bool maskOutputs,
     for (auto & i : outputs) {
         if (first) first = false; else s += ',';
         s += '('; printUnquotedString(s, i.first);
-        s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(i.second.path(store, name)));
         std::visit(overloaded {
             [&](DerivationOutputInputAddressed doi) {
+                s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(doi.path));
                 s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, "");
             },
             [&](DerivationOutputCAFixed dof) {
+                s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(dof.path(store, name, i.first)));
                 s += ','; printUnquotedString(s, dof.hash.printMethodAlgo());
                 s += ','; printUnquotedString(s, dof.hash.hash.to_string(Base16, false));
             },
             [&](DerivationOutputCAFloating dof) {
+                s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
                 s += ','; printUnquotedString(s, "");
             },
@@ -360,6 +377,16 @@ bool isDerivation(const string & fileName)
 }
 
 
+std::string outputPathName(std::string_view drvName, std::string_view outputName) {
+    std::string res { drvName };
+    if (outputName != "out") {
+        res += "-";
+        res += outputName;
+    }
+    return res;
+}
+
+
 DerivationType BasicDerivation::type() const
 {
     std::set<std::string_view> inputAddressedOutputs, fixedCAOutputs, floatingCAOutputs;
@@ -452,12 +479,12 @@ DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool m
         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.outputsAndPaths(store)) {
-            auto & dof = std::get<DerivationOutputCAFixed>(i.second.first.output);
+        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.second));
+                + store.printStorePath(dof.path(store, drv.name, i.first)));
             outputHashes.insert_or_assign(i.first, std::move(hash));
         }
         return outputHashes;
@@ -508,21 +535,13 @@ bool wantOutput(const string & output, const std::set<string> & wanted)
 }
 
 
-StorePathSet BasicDerivation::outputPaths(const Store & store) const
-{
-    StorePathSet paths;
-    for (auto & i : outputsAndPaths(store))
-        paths.insert(i.second.second);
-    return paths;
-}
-
 static DerivationOutput readDerivationOutput(Source & in, const Store & store)
 {
-    auto path = store.parseStorePath(readString(in));
+    const auto pathS = readString(in);
     const auto hashAlgo = readString(in);
     const auto hash = readString(in);
 
-    return parseDerivationOutput(store, std::move(path), hashAlgo, hash);
+    return parseDerivationOutput(store, pathS, hashAlgo, hash);
 }
 
 StringSet BasicDerivation::outputNames() const
@@ -533,23 +552,12 @@ StringSet BasicDerivation::outputNames() const
     return names;
 }
 
-DerivationOutputsAndPaths BasicDerivation::outputsAndPaths(const Store & store) const {
-    DerivationOutputsAndPaths outsAndPaths;
-    for (auto output : outputs)
-        outsAndPaths.insert(std::make_pair(
-            output.first,
-            std::make_pair(output.second, output.second.path(store, name))
-            )
-        );
-    return outsAndPaths;
-}
-
 DerivationOutputsAndOptPaths BasicDerivation::outputsAndOptPaths(const Store & store) const {
     DerivationOutputsAndOptPaths outsAndOptPaths;
     for (auto output : outputs)
         outsAndOptPaths.insert(std::make_pair(
             output.first,
-            std::make_pair(output.second, output.second.pathOpt(store, output.first))
+            std::make_pair(output.second, output.second.path(store, name, output.first))
             )
         );
     return outsAndOptPaths;
@@ -594,22 +602,25 @@ Source & readDerivation(Source & in, const Store & store, BasicDerivation & drv,
 void writeDerivation(Sink & out, const Store & store, const BasicDerivation & drv)
 {
     out << drv.outputs.size();
-    for (auto & i : drv.outputsAndPaths(store)) {
-        out << i.first
-            << store.printStorePath(i.second.second);
+    for (auto & i : drv.outputs) {
+        out << i.first;
         std::visit(overloaded {
             [&](DerivationOutputInputAddressed doi) {
-                out << "" << "";
+                out << store.printStorePath(doi.path)
+                    << ""
+                    << "";
             },
             [&](DerivationOutputCAFixed dof) {
-                out << dof.hash.printMethodAlgo()
+                out << store.printStorePath(dof.path(store, drv.name, i.first))
+                    << dof.hash.printMethodAlgo()
                     << dof.hash.hash.to_string(Base16, false);
             },
             [&](DerivationOutputCAFloating dof) {
-                out << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
+                out << ""
+                    << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
                     << "";
             },
-        }, i.second.first.output);
+        }, i.second.output);
     }
     writeStorePaths(store, out, drv.inputSrcs);
     out << drv.platform << drv.builder << drv.args;
@@ -625,5 +636,12 @@ std::string hashPlaceholder(const std::string & outputName)
     return "/" + hashString(htSHA256, "nix-output:" + outputName).to_string(Base32, false);
 }
 
+std::string downstreamPlaceholder(const Store & store, const StorePath & drvPath, std::string_view outputName)
+{
+    auto drvNameWithExtension = drvPath.name();
+    auto drvName = drvNameWithExtension.substr(0, drvNameWithExtension.size() - 4);
+    auto clearText = "nix-upstream-output:" + std::string { drvPath.hashPart() } + ":" + outputPathName(drvName, outputName);
+    return "/" + hashString(htSHA256, clearText).to_string(Base32, false);
+}
 
 }
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 573502c90..0b5652685 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -27,6 +27,7 @@ struct DerivationOutputInputAddressed
 struct DerivationOutputCAFixed
 {
     FixedOutputHash hash; /* hash used for expected hash computation */
+    StorePath path(const Store & store, std::string_view drvName, std::string_view outputName) const;
 };
 
 /* Floating-output derivations, whose output paths are content addressed, but
@@ -49,14 +50,8 @@ struct DerivationOutput
     std::optional<HashType> hashAlgoOpt(const Store & store) const;
     /* Note, when you use this function you should make sure that you're passing
        the right derivation name. When in doubt, you should use the safer
-       interface provided by BasicDerivation::outputsAndPaths */
-    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;
-    }
+       interface provided by BasicDerivation::outputsAndOptPaths */
+    std::optional<StorePath> path(const Store & store, std::string_view drvName, std::string_view outputName) const;
 };
 
 typedef std::map<string, DerivationOutput> DerivationOutputs;
@@ -113,17 +108,12 @@ struct BasicDerivation
     /* Return true iff this is a fixed-output derivation. */
     DerivationType type() const;
 
-    /* Return the output paths of a derivation. */
-    StorePathSet outputPaths(const Store & store) const;
-
     /* Return the output names of a derivation. */
     StringSet outputNames() const;
 
     /* Calculates the maps that contains all the DerivationOutputs, but
-       augmented with knowledge of the Store paths they would be written into.
-       The first one of these functions will be removed when the CA work is
-       completed */
-    DerivationOutputsAndPaths outputsAndPaths(const Store & store) const;
+       augmented with knowledge of the Store paths they would be written
+       into. */
     DerivationOutputsAndOptPaths outputsAndOptPaths(const Store & store) const;
 
     static std::string_view nameFromPath(const StorePath & storePath);
@@ -155,6 +145,13 @@ Derivation parseDerivation(const Store & store, std::string && s, std::string_vi
 // FIXME: remove
 bool isDerivation(const string & fileName);
 
+/* Calculate the name that will be used for the store path for this
+   output.
+
+   This is usually <drv-name>-<output-name>, but is just <drv-name> when
+   the output name is "out". */
+std::string outputPathName(std::string_view drvName, std::string_view outputName);
+
 // 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;
@@ -202,6 +199,21 @@ struct Sink;
 Source & readDerivation(Source & in, const Store & store, BasicDerivation & drv, std::string_view name);
 void writeDerivation(Sink & out, const Store & store, const BasicDerivation & drv);
 
+/* This creates an opaque and almost certainly unique string
+   deterministically from the output name.
+
+   It is used as a placeholder to allow derivations to refer to their
+   own outputs without needing to use the hash of a derivation in
+   itself, making the hash near-impossible to calculate. */
 std::string hashPlaceholder(const std::string & outputName);
 
+/* This creates an opaque and almost certainly unique string
+   deterministically from a derivation path and output name.
+
+   It is used as a placeholder to allow derivations to refer to
+   content-addressed paths whose content --- and thus the path
+   themselves --- isn't yet known. This occurs when a derivation has a
+   dependency which is a CA derivation. */
+std::string downstreamPlaceholder(const Store & store, const StorePath & drvPath, std::string_view outputName);
+
 }
diff --git a/src/libstore/dummy-store.cc b/src/libstore/dummy-store.cc
index 7a5744bc1..128832e60 100644
--- a/src/libstore/dummy-store.cc
+++ b/src/libstore/dummy-store.cc
@@ -2,17 +2,27 @@
 
 namespace nix {
 
-static std::string uriScheme = "dummy://";
+struct DummyStoreConfig : virtual StoreConfig {
+    using StoreConfig::StoreConfig;
 
-struct DummyStore : public Store
+    const std::string name() override { return "Dummy Store"; }
+};
+
+struct DummyStore : public Store, public virtual DummyStoreConfig
 {
-    DummyStore(const Params & params)
-        : Store(params)
+    DummyStore(const std::string scheme, const std::string uri, const Params & params)
+        : DummyStore(params)
     { }
 
+    DummyStore(const Params & params)
+        : StoreConfig(params)
+        , Store(params)
+    {
+    }
+
     string getUri() override
     {
-        return uriScheme;
+        return *uriSchemes().begin();
     }
 
     void queryPathInfoUncached(const StorePath & path,
@@ -21,6 +31,10 @@ struct DummyStore : public Store
         callback(nullptr);
     }
 
+    static std::set<std::string> uriSchemes() {
+        return {"dummy"};
+    }
+
     std::optional<StorePath> queryPathFromHashPart(const std::string & hashPart) override
     { unsupported("queryPathFromHashPart"); }
 
@@ -48,12 +62,6 @@ struct DummyStore : public Store
     { unsupported("buildDerivation"); }
 };
 
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    if (uri != uriScheme) return nullptr;
-    return std::make_shared<DummyStore>(params);
-});
+static RegisterStoreImplementation<DummyStore, DummyStoreConfig> regStore;
 
 }
diff --git a/src/libstore/globals.cc b/src/libstore/globals.cc
index 4a5971c3f..491c664db 100644
--- a/src/libstore/globals.cc
+++ b/src/libstore/globals.cc
@@ -162,11 +162,6 @@ template<> std::string BaseSetting<SandboxMode>::to_string() const
     else abort();
 }
 
-template<> nlohmann::json BaseSetting<SandboxMode>::toJSON()
-{
-    return AbstractSetting::toJSON();
-}
-
 template<> void BaseSetting<SandboxMode>::convertToArg(Args & args, const std::string & category)
 {
     args.addFlag({
diff --git a/src/libstore/globals.hh b/src/libstore/globals.hh
index 8a2d3ff75..02721285a 100644
--- a/src/libstore/globals.hh
+++ b/src/libstore/globals.hh
@@ -2,6 +2,7 @@
 
 #include "types.hh"
 #include "config.hh"
+#include "abstractsettingtojson.hh"
 #include "util.hh"
 
 #include <map>
diff --git a/src/libstore/http-binary-cache-store.cc b/src/libstore/http-binary-cache-store.cc
index 1733239fb..f4ab15a10 100644
--- a/src/libstore/http-binary-cache-store.cc
+++ b/src/libstore/http-binary-cache-store.cc
@@ -7,7 +7,14 @@ namespace nix {
 
 MakeError(UploadToHTTP, Error);
 
-class HttpBinaryCacheStore : public BinaryCacheStore
+struct HttpBinaryCacheStoreConfig : virtual BinaryCacheStoreConfig
+{
+    using BinaryCacheStoreConfig::BinaryCacheStoreConfig;
+
+    const std::string name() override { return "Http Binary Cache Store"; }
+};
+
+class HttpBinaryCacheStore : public BinaryCacheStore, public HttpBinaryCacheStoreConfig
 {
 private:
 
@@ -24,9 +31,12 @@ private:
 public:
 
     HttpBinaryCacheStore(
-        const Params & params, const Path & _cacheUri)
-        : BinaryCacheStore(params)
-        , cacheUri(_cacheUri)
+        const std::string & scheme,
+        const Path & _cacheUri,
+        const Params & params)
+        : StoreConfig(params)
+        , BinaryCacheStore(params)
+        , cacheUri(scheme + "://" + _cacheUri)
     {
         if (cacheUri.back() == '/')
             cacheUri.pop_back();
@@ -55,6 +65,13 @@ public:
         }
     }
 
+    static std::set<std::string> uriSchemes()
+    {
+        static bool forceHttp = getEnv("_NIX_FORCE_HTTP") == "1";
+        auto ret = std::set<std::string>({"http", "https"});
+        if (forceHttp) ret.insert("file");
+        return ret;
+    }
 protected:
 
     void maybeDisable()
@@ -162,18 +179,6 @@ protected:
 
 };
 
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    static bool forceHttp = getEnv("_NIX_FORCE_HTTP") == "1";
-    if (std::string(uri, 0, 7) != "http://" &&
-        std::string(uri, 0, 8) != "https://" &&
-        (!forceHttp || std::string(uri, 0, 7) != "file://"))
-        return 0;
-    auto store = std::make_shared<HttpBinaryCacheStore>(params, uri);
-    store->init();
-    return store;
-});
+static RegisterStoreImplementation<HttpBinaryCacheStore, HttpBinaryCacheStoreConfig> regStore;
 
 }
diff --git a/src/libstore/legacy-ssh-store.cc b/src/libstore/legacy-ssh-store.cc
index dc03313f0..e9478c1d5 100644
--- a/src/libstore/legacy-ssh-store.cc
+++ b/src/libstore/legacy-ssh-store.cc
@@ -9,18 +9,24 @@
 
 namespace nix {
 
-static std::string uriScheme = "ssh://";
-
-struct LegacySSHStore : public Store
+struct LegacySSHStoreConfig : virtual StoreConfig
 {
-    const Setting<int> maxConnections{this, 1, "max-connections", "maximum number of concurrent SSH connections"};
-    const Setting<Path> sshKey{this, "", "ssh-key", "path to an SSH private key"};
-    const Setting<bool> compress{this, false, "compress", "whether to compress the connection"};
-    const Setting<Path> remoteProgram{this, "nix-store", "remote-program", "path to the nix-store executable on the remote system"};
-    const Setting<std::string> remoteStore{this, "", "remote-store", "URI of the store on the remote system"};
+    using StoreConfig::StoreConfig;
+    const Setting<int> maxConnections{(StoreConfig*) this, 1, "max-connections", "maximum number of concurrent SSH connections"};
+    const Setting<Path> sshKey{(StoreConfig*) this, "", "ssh-key", "path to an SSH private key"};
+    const Setting<bool> compress{(StoreConfig*) this, false, "compress", "whether to compress the connection"};
+    const Setting<Path> remoteProgram{(StoreConfig*) this, "nix-store", "remote-program", "path to the nix-store executable on the remote system"};
+    const Setting<std::string> remoteStore{(StoreConfig*) this, "", "remote-store", "URI of the store on the remote system"};
+
+    const std::string name() override { return "Legacy SSH Store"; }
+};
 
+struct LegacySSHStore : public Store, public virtual LegacySSHStoreConfig
+{
     // Hack for getting remote build log output.
-    const Setting<int> logFD{this, -1, "log-fd", "file descriptor to which SSH's stderr is connected"};
+    // Intentionally not in `LegacySSHStoreConfig` so that it doesn't appear in
+    // the documentation
+    const Setting<int> logFD{(StoreConfig*) this, -1, "log-fd", "file descriptor to which SSH's stderr is connected"};
 
     struct Connection
     {
@@ -37,8 +43,11 @@ struct LegacySSHStore : public Store
 
     SSHMaster master;
 
-    LegacySSHStore(const string & host, const Params & params)
-        : Store(params)
+    static std::set<std::string> uriSchemes() { return {"ssh"}; }
+
+    LegacySSHStore(const string & scheme, const string & host, const Params & params)
+        : StoreConfig(params)
+        , Store(params)
         , host(host)
         , connections(make_ref<Pool<Connection>>(
             std::max(1, (int) maxConnections),
@@ -84,7 +93,7 @@ struct LegacySSHStore : public Store
 
     string getUri() override
     {
-        return uriScheme + host;
+        return *uriSchemes().begin() + "://" + host;
     }
 
     void queryPathInfoUncached(const StorePath & path,
@@ -325,12 +334,6 @@ public:
     }
 };
 
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    if (std::string(uri, 0, uriScheme.size()) != uriScheme) return 0;
-    return std::make_shared<LegacySSHStore>(std::string(uri, uriScheme.size()), params);
-});
+static RegisterStoreImplementation<LegacySSHStore, LegacySSHStoreConfig> regStore;
 
 }
diff --git a/src/libstore/local-binary-cache-store.cc b/src/libstore/local-binary-cache-store.cc
index 87d8334d7..b5744448e 100644
--- a/src/libstore/local-binary-cache-store.cc
+++ b/src/libstore/local-binary-cache-store.cc
@@ -4,7 +4,14 @@
 
 namespace nix {
 
-class LocalBinaryCacheStore : public BinaryCacheStore
+struct LocalBinaryCacheStoreConfig : virtual BinaryCacheStoreConfig
+{
+    using BinaryCacheStoreConfig::BinaryCacheStoreConfig;
+
+    const std::string name() override { return "Local Binary Cache Store"; }
+};
+
+class LocalBinaryCacheStore : public BinaryCacheStore, public virtual LocalBinaryCacheStoreConfig
 {
 private:
 
@@ -13,8 +20,11 @@ private:
 public:
 
     LocalBinaryCacheStore(
-        const Params & params, const Path & binaryCacheDir)
-        : BinaryCacheStore(params)
+        const std::string scheme,
+        const Path & binaryCacheDir,
+        const Params & params)
+        : StoreConfig(params)
+        , BinaryCacheStore(params)
         , binaryCacheDir(binaryCacheDir)
     {
     }
@@ -26,6 +36,8 @@ public:
         return "file://" + binaryCacheDir;
     }
 
+    static std::set<std::string> uriSchemes();
+
 protected:
 
     bool fileExists(const std::string & path) override;
@@ -85,16 +97,14 @@ bool LocalBinaryCacheStore::fileExists(const std::string & path)
     return pathExists(binaryCacheDir + "/" + path);
 }
 
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
+std::set<std::string> LocalBinaryCacheStore::uriSchemes()
 {
-    if (getEnv("_NIX_FORCE_HTTP_BINARY_CACHE_STORE") == "1" ||
-        std::string(uri, 0, 7) != "file://")
-        return 0;
-    auto store = std::make_shared<LocalBinaryCacheStore>(params, std::string(uri, 7));
-    store->init();
-    return store;
-});
+    if (getEnv("_NIX_FORCE_HTTP_BINARY_CACHE_STORE") == "1")
+        return {};
+    else
+        return {"file"};
+}
+
+static RegisterStoreImplementation<LocalBinaryCacheStore, LocalBinaryCacheStoreConfig> regStore;
 
 }
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index 84f8d7752..c618203f0 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -42,7 +42,8 @@ namespace nix {
 
 
 LocalStore::LocalStore(const Params & params)
-    : Store(params)
+    : StoreConfig(params)
+    , Store(params)
     , LocalFSStore(params)
     , realStoreDir_{this, false, rootDir != "" ? rootDir + "/nix/store" : storeDir, "real",
         "physical path to the Nix store"}
@@ -578,13 +579,32 @@ void LocalStore::checkDerivationOutputs(const StorePath & drvPath, const Derivat
                 envHasRightPath(path, i.first);
             },
             [&](DerivationOutputCAFloating _) {
-                throw UnimplementedError("floating CA output derivations are not yet implemented");
+                /* Nothing to check */
             },
         }, i.second.output);
     }
 }
 
 
+void LocalStore::linkDeriverToPath(const StorePath & deriver, const string & outputName, const StorePath & output)
+{
+    auto state(_state.lock());
+    return linkDeriverToPath(*state, queryValidPathId(*state, deriver), outputName, output);
+}
+
+void LocalStore::linkDeriverToPath(State & state, uint64_t deriver, const string & outputName, const StorePath & output)
+{
+    retrySQLite<void>([&]() {
+        state.stmtAddDerivationOutput.use()
+            (deriver)
+            (outputName)
+            (printStorePath(output))
+            .exec();
+    });
+
+}
+
+
 uint64_t LocalStore::addValidPath(State & state,
     const ValidPathInfo & info, bool checkOutputs)
 {
@@ -618,12 +638,11 @@ uint64_t LocalStore::addValidPath(State & state,
            registration above is undone. */
         if (checkOutputs) checkDerivationOutputs(info.path, drv);
 
-        for (auto & i : drv.outputsAndPaths(*this)) {
-            state.stmtAddDerivationOutput.use()
-                (id)
-                (i.first)
-                (printStorePath(i.second.second))
-                .exec();
+        for (auto & i : drv.outputsAndOptPaths(*this)) {
+            /* Floating CA derivations have indeterminate output paths until
+               they are built, so don't register anything in that case */
+            if (i.second.second)
+                linkDeriverToPath(state, id, i.first, *i.second.second);
         }
     }
 
@@ -1533,27 +1552,5 @@ void LocalStore::createUser(const std::string & userName, uid_t userId)
     }
 }
 
-static bool isNonUriPath(const std::string & spec) {
-    return
-        // is not a URL
-        spec.find("://") == std::string::npos
-        // Has at least one path separator, and so isn't a single word that
-        // might be special like "auto"
-        && spec.find("/") != std::string::npos;
-}
-
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    Store::Params params2 = params;
-    if (uri == "local") {
-    } else if (isNonUriPath(uri)) {
-        params2["root"] = absPath(uri);
-    } else {
-        return nullptr;
-    }
-    return std::shared_ptr<Store>(std::make_shared<LocalStore>(params2));
-});
 
 }
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index bb4ed9b19..e7c9d1605 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -30,8 +30,19 @@ struct OptimiseStats
     uint64_t blocksFreed = 0;
 };
 
+struct LocalStoreConfig : virtual LocalFSStoreConfig
+{
+    using LocalFSStoreConfig::LocalFSStoreConfig;
+
+    Setting<bool> requireSigs{(StoreConfig*) this,
+        settings.requireSigs,
+        "require-sigs", "whether store paths should have a trusted signature on import"};
+
+    const std::string name() override { return "Local Store"; }
+};
 
-class LocalStore : public LocalFSStore
+
+class LocalStore : public LocalFSStore, public virtual LocalStoreConfig
 {
 private:
 
@@ -95,10 +106,6 @@ public:
 
 private:
 
-    Setting<bool> requireSigs{(Store*) this,
-        settings.requireSigs,
-        "require-sigs", "whether store paths should have a trusted signature on import"};
-
     const PublicKeys & getPublicKeys();
 
 public:
@@ -279,6 +286,11 @@ private:
        specified by the ‘secret-key-files’ option. */
     void signPathInfo(ValidPathInfo & info);
 
+    /* Register the store path 'output' as the output named 'outputName' of
+       derivation 'deriver'. */
+    void linkDeriverToPath(const StorePath & deriver, const string & outputName, const StorePath & output);
+    void linkDeriverToPath(State & state, uint64_t deriver, const string & outputName, const StorePath & output);
+
     Path getRealStoreDir() override { return realStoreDir; }
 
     void createUser(const std::string & userName, uid_t userId) override;
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index f6aa570bb..da3981696 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -203,17 +203,24 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
                 return;
             }
 
+            PathSet invalid;
+            /* true for regular derivations, and CA derivations for which we
+               have a trust mapping for all wanted outputs. */
+            auto knownOutputPaths = true;
+            for (auto & [outputName, pathOpt] : queryPartialDerivationOutputMap(path.path)) {
+                if (!pathOpt) {
+                    knownOutputPaths = false;
+                    break;
+                }
+                if (wantOutput(outputName, path.outputs) && !isValidPath(*pathOpt))
+                    invalid.insert(printStorePath(*pathOpt));
+            }
+            if (knownOutputPaths && invalid.empty()) return;
+
             auto drv = make_ref<Derivation>(derivationFromPath(path.path));
             ParsedDerivation parsedDrv(StorePath(path.path), *drv);
 
-            PathSet invalid;
-            for (auto & j : drv->outputsAndPaths(*this))
-                if (wantOutput(j.first, path.outputs)
-                    && !isValidPath(j.second.second))
-                    invalid.insert(printStorePath(j.second.second));
-            if (invalid.empty()) return;
-
-            if (settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
+            if (knownOutputPaths && settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
                 auto drvState = make_ref<Sync<DrvState>>(DrvState(invalid.size()));
                 for (auto & output : invalid)
                     pool.enqueue(std::bind(checkOutput, printStorePath(path.path), drv, output, drvState));
diff --git a/src/libstore/references.cc b/src/libstore/references.cc
index 62a3cda61..d2096cb49 100644
--- a/src/libstore/references.cc
+++ b/src/libstore/references.cc
@@ -79,9 +79,17 @@ void RefScanSink::operator () (const unsigned char * data, size_t len)
 std::pair<PathSet, HashResult> scanForReferences(const string & path,
     const PathSet & refs)
 {
-    RefScanSink refsSink;
     HashSink hashSink { htSHA256 };
-    TeeSink sink { refsSink, hashSink };
+    auto found = scanForReferences(hashSink, path, refs);
+    auto hash = hashSink.finish();
+    return std::pair<PathSet, HashResult>(found, hash);
+}
+
+PathSet scanForReferences(Sink & toTee,
+    const string & path, const PathSet & refs)
+{
+    RefScanSink refsSink;
+    TeeSink sink { refsSink, toTee };
     std::map<string, Path> backMap;
 
     /* For efficiency (and a higher hit rate), just search for the
@@ -111,9 +119,7 @@ std::pair<PathSet, HashResult> scanForReferences(const string & path,
         found.insert(j->second);
     }
 
-    auto hash = hashSink.finish();
-
-    return std::pair<PathSet, HashResult>(found, hash);
+    return found;
 }
 
 
diff --git a/src/libstore/references.hh b/src/libstore/references.hh
index 598a3203a..c2efd095c 100644
--- a/src/libstore/references.hh
+++ b/src/libstore/references.hh
@@ -7,6 +7,8 @@ namespace nix {
 
 std::pair<PathSet, HashResult> scanForReferences(const Path & path, const PathSet & refs);
 
+PathSet scanForReferences(Sink & toTee, const Path & path, const PathSet & refs);
+
 struct RewritingSink : Sink
 {
     std::string from, to, prev;
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index d890042bb..e92b94975 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -94,6 +94,7 @@ void write(const Store & store, Sink & out, const std::optional<StorePath> & sto
 /* TODO: Separate these store impls into different files, give them better names */
 RemoteStore::RemoteStore(const Params & params)
     : Store(params)
+    , RemoteStoreConfig(params)
     , connections(make_ref<Pool<Connection>>(
             std::max(1, (int) maxConnections),
             [this]() {
@@ -132,19 +133,21 @@ ref<RemoteStore::Connection> RemoteStore::openConnectionWrapper()
 
 
 UDSRemoteStore::UDSRemoteStore(const Params & params)
-    : Store(params)
+    : StoreConfig(params)
+    , Store(params)
     , LocalFSStore(params)
     , RemoteStore(params)
 {
 }
 
 
-UDSRemoteStore::UDSRemoteStore(std::string socket_path, const Params & params)
-    : Store(params)
-    , LocalFSStore(params)
-    , RemoteStore(params)
-    , path(socket_path)
+UDSRemoteStore::UDSRemoteStore(
+        const std::string scheme,
+        std::string socket_path,
+        const Params & params)
+    : UDSRemoteStore(params)
 {
+    path.emplace(socket_path);
 }
 
 
@@ -989,18 +992,6 @@ std::exception_ptr RemoteStore::Connection::processStderr(Sink * sink, Source *
     return nullptr;
 }
 
-static std::string_view uriScheme = "unix://";
-
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    if (hasPrefix(uri, uriScheme))
-        return std::make_shared<UDSRemoteStore>(std::string(uri, uriScheme.size()), params);
-    else if (uri == "daemon")
-        return std::make_shared<UDSRemoteStore>(params);
-    else
-        return nullptr;
-});
+static RegisterStoreImplementation<UDSRemoteStore, UDSRemoteStoreConfig> regStore;
 
 }
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index eaeb68e57..91c748006 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -16,18 +16,22 @@ struct FdSource;
 template<typename T> class Pool;
 struct ConnectionHandle;
 
-
-/* FIXME: RemoteStore is a misnomer - should be something like
-   DaemonStore. */
-class RemoteStore : public virtual Store
+struct RemoteStoreConfig : virtual StoreConfig
 {
-public:
+    using StoreConfig::StoreConfig;
 
-    const Setting<int> maxConnections{(Store*) this, 1,
+    const Setting<int> maxConnections{(StoreConfig*) this, 1,
             "max-connections", "maximum number of concurrent connections to the Nix daemon"};
 
-    const Setting<unsigned int> maxConnectionAge{(Store*) this, std::numeric_limits<unsigned int>::max(),
+    const Setting<unsigned int> maxConnectionAge{(StoreConfig*) this, std::numeric_limits<unsigned int>::max(),
             "max-connection-age", "number of seconds to reuse a connection"};
+};
+
+/* FIXME: RemoteStore is a misnomer - should be something like
+   DaemonStore. */
+class RemoteStore : public virtual Store, public virtual RemoteStoreConfig
+{
+public:
 
     virtual bool sameMachine() = 0;
 
@@ -141,15 +145,35 @@ private:
 
 };
 
-class UDSRemoteStore : public LocalFSStore, public RemoteStore
+struct UDSRemoteStoreConfig : virtual LocalFSStoreConfig, virtual RemoteStoreConfig
+{
+    UDSRemoteStoreConfig(const Store::Params & params)
+        : StoreConfig(params)
+        , LocalFSStoreConfig(params)
+        , RemoteStoreConfig(params)
+    {
+    }
+
+    UDSRemoteStoreConfig()
+        : UDSRemoteStoreConfig(Store::Params({}))
+    {
+    }
+
+    const std::string name() override { return "Local Daemon Store"; }
+};
+
+class UDSRemoteStore : public LocalFSStore, public RemoteStore, public virtual UDSRemoteStoreConfig
 {
 public:
 
     UDSRemoteStore(const Params & params);
-    UDSRemoteStore(std::string path, const Params & params);
+    UDSRemoteStore(const std::string scheme, std::string path, const Params & params);
 
     std::string getUri() override;
 
+    static std::set<std::string> uriSchemes()
+    { return {"unix"}; }
+
     bool sameMachine() override
     { return true; }
 
diff --git a/src/libstore/s3-binary-cache-store.cc b/src/libstore/s3-binary-cache-store.cc
index a0a446bd3..d43f267e0 100644
--- a/src/libstore/s3-binary-cache-store.cc
+++ b/src/libstore/s3-binary-cache-store.cc
@@ -172,20 +172,26 @@ S3Helper::FileTransferResult S3Helper::getObject(
     return res;
 }
 
-struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
+struct S3BinaryCacheStoreConfig : virtual BinaryCacheStoreConfig
 {
-    const Setting<std::string> profile{this, "", "profile", "The name of the AWS configuration profile to use."};
-    const Setting<std::string> region{this, Aws::Region::US_EAST_1, "region", {"aws-region"}};
-    const Setting<std::string> scheme{this, "", "scheme", "The scheme to use for S3 requests, https by default."};
-    const Setting<std::string> endpoint{this, "", "endpoint", "An optional override of the endpoint to use when talking to S3."};
-    const Setting<std::string> narinfoCompression{this, "", "narinfo-compression", "compression method for .narinfo files"};
-    const Setting<std::string> lsCompression{this, "", "ls-compression", "compression method for .ls files"};
-    const Setting<std::string> logCompression{this, "", "log-compression", "compression method for log/* files"};
+    using BinaryCacheStoreConfig::BinaryCacheStoreConfig;
+    const Setting<std::string> profile{(StoreConfig*) this, "", "profile", "The name of the AWS configuration profile to use."};
+    const Setting<std::string> region{(StoreConfig*) this, Aws::Region::US_EAST_1, "region", {"aws-region"}};
+    const Setting<std::string> scheme{(StoreConfig*) this, "", "scheme", "The scheme to use for S3 requests, https by default."};
+    const Setting<std::string> endpoint{(StoreConfig*) this, "", "endpoint", "An optional override of the endpoint to use when talking to S3."};
+    const Setting<std::string> narinfoCompression{(StoreConfig*) this, "", "narinfo-compression", "compression method for .narinfo files"};
+    const Setting<std::string> lsCompression{(StoreConfig*) this, "", "ls-compression", "compression method for .ls files"};
+    const Setting<std::string> logCompression{(StoreConfig*) this, "", "log-compression", "compression method for log/* files"};
     const Setting<bool> multipartUpload{
-        this, false, "multipart-upload", "whether to use multi-part uploads"};
+        (StoreConfig*) this, false, "multipart-upload", "whether to use multi-part uploads"};
     const Setting<uint64_t> bufferSize{
-        this, 5 * 1024 * 1024, "buffer-size", "size (in bytes) of each part in multi-part uploads"};
+        (StoreConfig*) this, 5 * 1024 * 1024, "buffer-size", "size (in bytes) of each part in multi-part uploads"};
 
+    const std::string name() override { return "S3 Binary Cache Store"; }
+};
+
+struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore, virtual S3BinaryCacheStoreConfig
+{
     std::string bucketName;
 
     Stats stats;
@@ -193,8 +199,11 @@ struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
     S3Helper s3Helper;
 
     S3BinaryCacheStoreImpl(
-        const Params & params, const std::string & bucketName)
-        : S3BinaryCacheStore(params)
+        const std::string & scheme,
+        const std::string & bucketName,
+        const Params & params)
+        : StoreConfig(params)
+        , S3BinaryCacheStore(params)
         , bucketName(bucketName)
         , s3Helper(profile, region, scheme, endpoint)
     {
@@ -426,17 +435,11 @@ struct S3BinaryCacheStoreImpl : public S3BinaryCacheStore
         return paths;
     }
 
+    static std::set<std::string> uriSchemes() { return {"s3"}; }
+
 };
 
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    if (std::string(uri, 0, 5) != "s3://") return 0;
-    auto store = std::make_shared<S3BinaryCacheStoreImpl>(params, std::string(uri, 5));
-    store->init();
-    return store;
-});
+static RegisterStoreImplementation<S3BinaryCacheStoreImpl, S3BinaryCacheStoreConfig> regStore;
 
 }
 
diff --git a/src/libstore/ssh-store.cc b/src/libstore/ssh-store.cc
index 046b5710a..6d6eca98d 100644
--- a/src/libstore/ssh-store.cc
+++ b/src/libstore/ssh-store.cc
@@ -8,19 +8,25 @@
 
 namespace nix {
 
-static std::string uriScheme = "ssh-ng://";
+struct SSHStoreConfig : virtual RemoteStoreConfig
+{
+    using RemoteStoreConfig::RemoteStoreConfig;
+
+    const Setting<Path> sshKey{(StoreConfig*) this, "", "ssh-key", "path to an SSH private key"};
+    const Setting<bool> compress{(StoreConfig*) this, false, "compress", "whether to compress the connection"};
+    const Setting<Path> remoteProgram{(StoreConfig*) this, "nix-daemon", "remote-program", "path to the nix-daemon executable on the remote system"};
+    const Setting<std::string> remoteStore{(StoreConfig*) this, "", "remote-store", "URI of the store on the remote system"};
+
+    const std::string name() override { return "SSH Store"; }
+};
 
-class SSHStore : public RemoteStore
+class SSHStore : public virtual RemoteStore, public virtual SSHStoreConfig
 {
 public:
 
-    const Setting<Path> sshKey{(Store*) this, "", "ssh-key", "path to an SSH private key"};
-    const Setting<bool> compress{(Store*) this, false, "compress", "whether to compress the connection"};
-    const Setting<Path> remoteProgram{(Store*) this, "nix-daemon", "remote-program", "path to the nix-daemon executable on the remote system"};
-    const Setting<std::string> remoteStore{(Store*) this, "", "remote-store", "URI of the store on the remote system"};
-
-    SSHStore(const std::string & host, const Params & params)
-        : Store(params)
+    SSHStore(const std::string & scheme, const std::string & host, const Params & params)
+        : StoreConfig(params)
+        , Store(params)
         , RemoteStore(params)
         , host(host)
         , master(
@@ -32,9 +38,11 @@ public:
     {
     }
 
+    static std::set<std::string> uriSchemes() { return {"ssh-ng"}; }
+
     std::string getUri() override
     {
-        return uriScheme + host;
+        return *uriSchemes().begin() + "://" + host;
     }
 
     bool sameMachine() override
@@ -75,12 +83,6 @@ ref<RemoteStore::Connection> SSHStore::openConnection()
     return conn;
 }
 
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-    if (std::string(uri, 0, uriScheme.size()) != uriScheme) return 0;
-    return std::make_shared<SSHStore>(std::string(uri, uriScheme.size()), params);
-});
+static RegisterStoreImplementation<SSHStore, SSHStoreConfig> regStore;
 
 }
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index ba4459bbe..2d5077ed0 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -140,21 +140,28 @@ StorePathWithOutputs Store::followLinksToStorePathWithOutputs(std::string_view p
 */
 
 
-StorePath Store::makeStorePath(const string & type,
-    const Hash & hash, std::string_view name) const
+StorePath Store::makeStorePath(std::string_view type,
+    std::string_view hash, std::string_view name) const
 {
     /* e.g., "source:sha256:1abc...:/nix/store:foo.tar.gz" */
-    string s = type + ":" + hash.to_string(Base16, true) + ":" + storeDir + ":" + std::string(name);
+    string s = std::string { type } + ":" + std::string { hash }
+        + ":" + storeDir + ":" + std::string { name };
     auto h = compressHash(hashString(htSHA256, s), 20);
     return StorePath(h, name);
 }
 
 
-StorePath Store::makeOutputPath(const string & id,
+StorePath Store::makeStorePath(std::string_view type,
+    const Hash & hash, std::string_view name) const
+{
+    return makeStorePath(type, hash.to_string(Base16, true), name);
+}
+
+
+StorePath Store::makeOutputPath(std::string_view id,
     const Hash & hash, std::string_view name) const
 {
-    return makeStorePath("output:" + id, hash,
-        std::string(name) + (id == "out" ? "" : "-" + id));
+    return makeStorePath("output:" + std::string { id }, hash, outputPathName(name, id));
 }
 
 
@@ -339,7 +346,7 @@ ValidPathInfo Store::addToStoreSlow(std::string_view name, const Path & srcPath,
 
 
 Store::Store(const Params & params)
-    : Config(params)
+    : StoreConfig(params)
     , state({(size_t) pathInfoCacheSize})
 {
 }
@@ -1002,7 +1009,6 @@ Derivation Store::readDerivation(const StorePath & drvPath)
     }
 }
 
-
 }
 
 
@@ -1012,9 +1018,6 @@ Derivation Store::readDerivation(const StorePath & drvPath)
 
 namespace nix {
 
-
-RegisterStoreImplementation::Implementations * RegisterStoreImplementation::implementations = 0;
-
 /* Split URI into protocol+hierarchy part and its parameter set. */
 std::pair<std::string, Store::Params> splitUriAndParams(const std::string & uri_)
 {
@@ -1028,45 +1031,72 @@ std::pair<std::string, Store::Params> splitUriAndParams(const std::string & uri_
     return {uri, params};
 }
 
+static bool isNonUriPath(const std::string & spec) {
+    return
+        // is not a URL
+        spec.find("://") == std::string::npos
+        // Has at least one path separator, and so isn't a single word that
+        // might be special like "auto"
+        && spec.find("/") != std::string::npos;
+}
+
+std::shared_ptr<Store> openFromNonUri(const std::string & uri, const Store::Params & params)
+{
+    if (uri == "" || uri == "auto") {
+        auto stateDir = get(params, "state").value_or(settings.nixStateDir);
+        if (access(stateDir.c_str(), R_OK | W_OK) == 0)
+            return std::make_shared<LocalStore>(params);
+        else if (pathExists(settings.nixDaemonSocketFile))
+            return std::make_shared<UDSRemoteStore>(params);
+        else
+            return std::make_shared<LocalStore>(params);
+    } else if (uri == "daemon") {
+        return std::make_shared<UDSRemoteStore>(params);
+    } else if (uri == "local") {
+        return std::make_shared<LocalStore>(params);
+    } else if (isNonUriPath(uri)) {
+        Store::Params params2 = params;
+        params2["root"] = absPath(uri);
+        return std::make_shared<LocalStore>(params2);
+    } else {
+        return nullptr;
+    }
+}
+
 ref<Store> openStore(const std::string & uri_,
     const Store::Params & extraParams)
 {
-    auto [uri, uriParams] = splitUriAndParams(uri_);
     auto params = extraParams;
-    params.insert(uriParams.begin(), uriParams.end());
+    try {
+        auto parsedUri = parseURL(uri_);
+        params.insert(parsedUri.query.begin(), parsedUri.query.end());
+
+        auto baseURI = parsedUri.authority.value_or("") + parsedUri.path;
+
+        for (auto implem : *Implementations::registered) {
+            if (implem.uriSchemes.count(parsedUri.scheme)) {
+                auto store = implem.create(parsedUri.scheme, baseURI, params);
+                if (store) {
+                    store->init();
+                    store->warnUnknownSettings();
+                    return ref<Store>(store);
+                }
+            }
+        }
+    }
+    catch (BadURL &) {
+        auto [uri, uriParams] = splitUriAndParams(uri_);
+        params.insert(uriParams.begin(), uriParams.end());
 
-    for (auto fun : *RegisterStoreImplementation::implementations) {
-        auto store = fun(uri, params);
-        if (store) {
+        if (auto store = openFromNonUri(uri, params)) {
             store->warnUnknownSettings();
             return ref<Store>(store);
         }
     }
 
-    throw Error("don't know how to open Nix store '%s'", uri);
+    throw Error("don't know how to open Nix store '%s'", uri_);
 }
 
-
-// Specific prefixes are handled by the specific types of store, while here we
-// handle the general cases not covered by the other ones.
-static RegisterStoreImplementation regStore([](
-    const std::string & uri, const Store::Params & params)
-    -> std::shared_ptr<Store>
-{
-     auto stateDir = get(params, "state").value_or(settings.nixStateDir);
-     if (uri == "" || uri == "auto") {
-        if (access(stateDir.c_str(), R_OK | W_OK) == 0)
-            return std::make_shared<LocalStore>(params);
-        else if (pathExists(settings.nixDaemonSocketFile))
-            return std::make_shared<UDSRemoteStore>(params);
-        else
-            return std::make_shared<LocalStore>(params);
-     } else {
-         return nullptr;
-     }
-});
-
-
 std::list<ref<Store>> getDefaultSubstituters()
 {
     static auto stores([]() {
@@ -1099,5 +1129,6 @@ std::list<ref<Store>> getDefaultSubstituters()
     return stores;
 }
 
+std::vector<StoreFactory> * Implementations::registered = 0;
 
 }
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 52f0916f2..4d3f07dfc 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -24,6 +24,31 @@
 
 namespace nix {
 
+/**
+ * About the class hierarchy of the store implementations:
+ *
+ * Each store type `Foo` consists of two classes:
+ *
+ * 1. A class `FooConfig : virtual StoreConfig` that contains the configuration
+ *   for the store
+ *
+ *   It should only contain members of type `const Setting<T>` (or subclasses
+ *   of it) and inherit the constructors of `StoreConfig`
+ *   (`using StoreConfig::StoreConfig`).
+ *
+ * 2. A class `Foo : virtual Store, virtual FooConfig` that contains the
+ *   implementation of the store.
+ *
+ *   This class is expected to have a constructor `Foo(const Params & params)`
+ *   that calls `StoreConfig(params)` (otherwise you're gonna encounter an
+ *   `assertion failure` when trying to instantiate it).
+ *
+ * You can then register the new store using:
+ *
+ * ```
+ * cpp static RegisterStoreImplementation<Foo, FooConfig> regStore;
+ * ```
+ */
 
 MakeError(SubstError, Error);
 MakeError(BuildError, Error); // denotes a permanent build failure
@@ -33,6 +58,7 @@ MakeError(SubstituteGone, Error);
 MakeError(SubstituterDisabled, Error);
 MakeError(BadStorePath, Error);
 
+MakeError(InvalidStoreURI, Error);
 
 class FSAccessor;
 class NarInfoDiskCache;
@@ -144,12 +170,31 @@ struct BuildResult
     }
 };
 
-
-class Store : public std::enable_shared_from_this<Store>, public Config
+struct StoreConfig : public Config
 {
-public:
-
-    typedef std::map<std::string, std::string> Params;
+    using Config::Config;
+
+    /**
+     * When constructing a store implementation, we pass in a map `params` of
+     * parameters that's supposed to initialize the associated config.
+     * To do that, we must use the `StoreConfig(StringMap & params)`
+     * constructor, so we'd like to `delete` its default constructor to enforce
+     * it.
+     *
+     * However, actually deleting it means that all the subclasses of
+     * `StoreConfig` will have their default constructor deleted (because it's
+     * supposed to call the deleted default constructor of `StoreConfig`). But
+     * because we're always using virtual inheritance, the constructors of
+     * child classes will never implicitely call this one, so deleting it will
+     * be more painful than anything else.
+     *
+     * So we `assert(false)` here to ensure at runtime that the right
+     * constructor is always called without having to redefine a custom
+     * constructor for each `*Config` class.
+     */
+    StoreConfig() { assert(false); }
+
+    virtual const std::string name() = 0;
 
     const PathSetting storeDir_{this, false, settings.nixStore,
         "store", "path to the Nix store"};
@@ -167,6 +212,14 @@ public:
         "system-features",
         "Optional features that the system this store builds on implements (like \"kvm\")."};
 
+};
+
+class Store : public std::enable_shared_from_this<Store>, public virtual StoreConfig
+{
+public:
+
+    typedef std::map<std::string, std::string> Params;
+
 protected:
 
     struct PathInfoCacheValue {
@@ -200,6 +253,11 @@ protected:
     Store(const Params & params);
 
 public:
+    /**
+     * Perform any necessary effectful operation to make the store up and
+     * running
+     */
+    virtual void init() {};
 
     virtual ~Store() { }
 
@@ -247,10 +305,12 @@ public:
     StorePathWithOutputs followLinksToStorePathWithOutputs(std::string_view path) const;
 
     /* Constructs a unique store path name. */
-    StorePath makeStorePath(const string & type,
+    StorePath makeStorePath(std::string_view type,
+        std::string_view hash, std::string_view name) const;
+    StorePath makeStorePath(std::string_view type,
         const Hash & hash, std::string_view name) const;
 
-    StorePath makeOutputPath(const string & id,
+    StorePath makeOutputPath(std::string_view id,
         const Hash & hash, std::string_view name) const;
 
     StorePath makeFixedOutputPath(FileIngestionMethod method,
@@ -624,22 +684,25 @@ protected:
 
 };
 
-
-class LocalFSStore : public virtual Store
+struct LocalFSStoreConfig : virtual StoreConfig
 {
-public:
-
-    // FIXME: the (Store*) cast works around a bug in gcc that causes
+    using StoreConfig::StoreConfig;
+    // FIXME: the (StoreConfig*) cast works around a bug in gcc that causes
     // it to omit the call to the Setting constructor. Clang works fine
     // either way.
-    const PathSetting rootDir{(Store*) this, true, "",
+    const PathSetting rootDir{(StoreConfig*) this, true, "",
         "root", "directory prefixed to all other paths"};
-    const PathSetting stateDir{(Store*) this, false,
+    const PathSetting stateDir{(StoreConfig*) this, false,
         rootDir != "" ? rootDir + "/nix/var/nix" : settings.nixStateDir,
         "state", "directory where Nix will store state"};
-    const PathSetting logDir{(Store*) this, false,
+    const PathSetting logDir{(StoreConfig*) this, false,
         rootDir != "" ? rootDir + "/nix/var/log/nix" : settings.nixLogDir,
         "log", "directory where Nix will store state"};
+};
+
+class LocalFSStore : public virtual Store, public virtual LocalFSStoreConfig
+{
+public:
 
     const static string drvsLogDir;
 
@@ -732,25 +795,45 @@ ref<Store> openStore(const std::string & uri = settings.storeUri.get(),
    ‘substituters’ option and various legacy options. */
 std::list<ref<Store>> getDefaultSubstituters();
 
+struct StoreFactory
+{
+    std::set<std::string> uriSchemes;
+    std::function<std::shared_ptr<Store> (const std::string & scheme, const std::string & uri, const Store::Params & params)> create;
+    std::function<std::shared_ptr<StoreConfig> ()> getConfig;
+};
+struct Implementations
+{
+    static std::vector<StoreFactory> * registered;
 
-/* Store implementation registration. */
-typedef std::function<std::shared_ptr<Store>(
-    const std::string & uri, const Store::Params & params)> OpenStore;
+    template<typename T, typename TConfig>
+    static void add()
+    {
+        if (!registered) registered = new std::vector<StoreFactory>();
+        StoreFactory factory{
+            .uriSchemes = T::uriSchemes(),
+            .create =
+                ([](const std::string & scheme, const std::string & uri, const Store::Params & params)
+                 -> std::shared_ptr<Store>
+                 { return std::make_shared<T>(scheme, uri, params); }),
+            .getConfig =
+                ([]()
+                 -> std::shared_ptr<StoreConfig>
+                 { return std::make_shared<TConfig>(StringMap({})); })
+        };
+        registered->push_back(factory);
+    }
+};
 
+template<typename T, typename TConfig>
 struct RegisterStoreImplementation
 {
-    typedef std::vector<OpenStore> Implementations;
-    static Implementations * implementations;
-
-    RegisterStoreImplementation(OpenStore fun)
+    RegisterStoreImplementation()
     {
-        if (!implementations) implementations = new Implementations;
-        implementations->push_back(fun);
+        Implementations::add<T, TConfig>();
     }
 };
 
 
-
 /* Display a set of paths in human-readable form (i.e., between quotes
    and separated by commas). */
 string showPaths(const PathSet & paths);