Squashed get CA derivations building

29 files changed, 1020 insertions, 484 deletions

diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 5d6e39aa0..d41cac132 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -39,7 +39,9 @@ DrvInfo::DrvInfo(EvalState & state, ref<Store> store, const std::string & drvPat
     if (i == drv.outputs.end())
         throw Error("derivation '%s' does not have output '%s'", store->printStorePath(drvPath), outputName);
 
-    outPath = store->printStorePath(i->second.path(*store, drv.name));
+    auto optStorePath = i->second.pathOpt(*store, drv.name);
+    if (optStorePath)
+        outPath = store->printStorePath(*optStorePath);
 }
 
 
@@ -77,12 +79,15 @@ string DrvInfo::queryDrvPath() const
 
 string DrvInfo::queryOutPath() const
 {
-    if (outPath == "" && attrs) {
+    if (!outPath && attrs) {
         Bindings::iterator i = attrs->find(state->sOutPath);
         PathSet context;
-        outPath = i != attrs->end() ? state->coerceToPath(*i->pos, *i->value, context) : "";
+        if (i != attrs->end())
+            outPath = state->coerceToPath(*i->pos, *i->value, context);
     }
-    return outPath;
+    if (!outPath)
+        throw UnimplementedError("CA derivations are not yet supported");
+    return *outPath;
 }
 
 
diff --git a/src/libexpr/get-drvs.hh b/src/libexpr/get-drvs.hh
index d7860fc6a..29bb6a660 100644
--- a/src/libexpr/get-drvs.hh
+++ b/src/libexpr/get-drvs.hh
@@ -20,7 +20,7 @@ private:
     mutable string name;
     mutable string system;
     mutable string drvPath;
-    mutable string outPath;
+    mutable std::optional<string> outPath;
     mutable string outputName;
     Outputs outputs;
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 65d36ca0e..11f44fb97 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -44,16 +44,6 @@ void EvalState::realiseContext(const PathSet & context)
             throw InvalidPathError(store->printStorePath(ctx));
         if (!outputName.empty() && ctx.isDerivation()) {
             drvs.push_back(StorePathWithOutputs{ctx, {outputName}});
-
-            /* Add the output of this derivation to the allowed
-               paths. */
-            if (allowedPaths) {
-                auto drv = store->derivationFromPath(ctx);
-                DerivationOutputs::iterator i = drv.outputs.find(outputName);
-                if (i == drv.outputs.end())
-                    throw Error("derivation '%s' does not have an output named '%s'", ctxS, outputName);
-                allowedPaths->insert(store->printStorePath(i->second.path(*store, drv.name)));
-            }
         }
     }
 
@@ -69,8 +59,38 @@ void EvalState::realiseContext(const PathSet & context)
     store->queryMissing(drvs, willBuild, willSubstitute, unknown, downloadSize, narSize);
 
     store->buildPaths(drvs);
+
+    /* Add the output of this derivations to the allowed
+       paths. */
+    if (allowedPaths) {
+        for (auto & [drvPath, outputs] : drvs) {
+            auto outputPaths = store->queryDerivationOutputMapAssumeTotal(drvPath);
+            for (auto & outputName : outputs) {
+                if (outputPaths.count(outputName) == 0)
+                    throw Error("derivation '%s' does not have an output named '%s'",
+                            store->printStorePath(drvPath), outputName);
+                allowedPaths->insert(store->printStorePath(outputPaths.at(outputName)));
+            }
+        }
+    }
 }
 
+static void mkOutputString(EvalState & state, Value & v,
+    const StorePath & drvPath, const BasicDerivation & drv,
+    std::pair<string, DerivationOutput> o)
+{
+    auto optOutputPath = o.second.pathOpt(*state.store, drv.name);
+    mkString(
+        *state.allocAttr(v, state.symbols.create(o.first)),
+        state.store->printStorePath(optOutputPath
+            ? *optOutputPath
+            /* Downstream we would substitute this for an actual path once
+               we build the floating CA derivation */
+            /* FIXME: we need to depend on the basic derivation, not
+               derivation */
+            : downstreamPlaceholder(*state.store, drvPath, o.first)),
+        {"!" + o.first + "!" + state.store->printStorePath(drvPath)});
+}
 
 /* Load and evaluate an expression from path specified by the
    argument. */
@@ -114,8 +134,7 @@ static void prim_scopedImport(EvalState & state, const Pos & pos, Value * * args
         unsigned int outputs_index = 0;
 
         for (const auto & o : drv.outputs) {
-            v2 = state.allocAttr(w, state.symbols.create(o.first));
-            mkString(*v2, state.store->printStorePath(o.second.path(*state.store, drv.name)), {"!" + o.first + "!" + path});
+            mkOutputString(state, w, storePath, drv, o);
             outputsVal->listElems()[outputs_index] = state.allocValue();
             mkString(*(outputsVal->listElems()[outputs_index++]), o.first);
         }
@@ -846,16 +865,18 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
 
     /* Optimisation, but required in read-only mode! because in that
        case we don't actually write store derivations, so we can't
-       read them later. */
-    drvHashes.insert_or_assign(drvPath,
-        hashDerivationModulo(*state.store, Derivation(drv), false));
+       read them later.
+
+       However, we don't bother doing this for floating CA derivations because
+       their "hash modulo" is indeterminate until built. */
+    if (drv.type() != DerivationType::CAFloating)
+        drvHashes.insert_or_assign(drvPath,
+            hashDerivationModulo(*state.store, Derivation(drv), false));
 
     state.mkAttrs(v, 1 + drv.outputs.size());
     mkString(*state.allocAttr(v, state.sDrvPath), drvPathS, {"=" + drvPathS});
-    for (auto & i : drv.outputs) {
-        mkString(*state.allocAttr(v, state.symbols.create(i.first)),
-            state.store->printStorePath(i.second.path(*state.store, drv.name)), {"!" + i.first + "!" + drvPathS});
-    }
+    for (auto & i : drv.outputs)
+        mkOutputString(state, v, drvPath, drv, i);
     v.attrs->sort();
 }
 
diff --git a/src/libstore/build.cc b/src/libstore/build.cc
index b47aeff3b..7c2225805 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,24 @@ typedef enum {rpAccept, rpDecline, rpPostpone} HookReply;
 
 class SubstitutionGoal;
 
+struct KnownInitialOutputStatus {
+    StorePath path;
+    /* The output optional indicates whether it's already valid; i.e. exists
+       and is registered. If we're repairing, inner bool indicates whether the
+       valid path is in fact not corrupt. Otherwise, the inner bool is always
+       true (assumed no corruption). */
+    std::optional<bool> valid;
+    /* Valid in the store, and additionally non-corrupt if we are repairing */
+    bool isValid() const {
+        return valid && *valid;
+    }
+};
+
+struct InitialOutputStatus {
+    bool wanted;
+    std::optional<KnownInitialOutputStatus> known;
+};
+
 class DerivationGoal : public Goal
 {
 private:
@@ -744,19 +763,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, InitialOutputStatus> initialOutputs;
 
     /* User selected for running the builder. */
     std::unique_ptr<UserLock> buildUser;
@@ -839,6 +853,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.)
+     */
+    std::map<std::string, StorePath> finalOutputs;
+
     BuildMode buildMode;
 
     /* If we're repairing without a chroot, there may be outputs that
@@ -937,7 +976,8 @@ private:
     void getDerivation();
     void loadDerivation();
     void haveDerivation();
-    void outputsSubstituted();
+    void outputsSubstitutionTried();
+    void gaveUpOnSubstitution();
     void closureRepaired();
     void inputsRealised();
     void tryToBuild();
@@ -998,13 +1038,24 @@ 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>> queryDerivationOutputMap();
+    OutputPathMap queryDerivationOutputMapAssumeTotal();
+
     /* 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);
+    /* Map a path to another (reproducably) so we can avoid overwriting outputs
+       that already exist. */
+    StorePath makeFallbackPath(const StorePath & path);
+    /* Make a path to another based on the output name alone, if one doesn't
+       want to use a random path for CA builds. */
+    StorePath makeFallbackPath(std::string_view path);
 
     void repairClosure();
 
@@ -1047,7 +1098,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 +1230,63 @@ void DerivationGoal::haveDerivation()
 {
     trace("have derivation");
 
+    if (drv->type() == DerivationType::CAFloating)
+        settings.requireExperimentalFeature("ca-derivations");
+
     retrySubstitution = false;
 
-    for (auto & i : drv->outputs)
-        worker.store.addTempRoot(i.second.path(worker.store, drv->name));
+    /* Temporarily root output paths that are known a priori building */
+    for (auto & i : drv->outputs) {
+        auto optOutputPath = i.second.pathOpt(worker.store, drv->name);
+        if (optOutputPath)
+            worker.store.addTempRoot(*optOutputPath);
+    }
 
     /* 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 CA drv 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 +1310,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,6 +1330,12 @@ void DerivationGoal::outputsSubstituted()
         throw Error("some outputs of '%s' are not valid, so checking is not possible",
             worker.store.printStorePath(drvPath));
 
+    /* Nothing to wait for; tail call */
+    gaveUpOnSubstitution();
+}
+
+void DerivationGoal::gaveUpOnSubstitution()
+{
     /* Otherwise, at least one of the output paths could not be
        produced using a substitute.  So we have to build instead. */
 
@@ -1287,15 +1371,16 @@ void DerivationGoal::repairClosure()
        that produced those outputs. */
 
     /* Get the output closure. */
+    auto outputs = queryDerivationOutputMapAssumeTotal();
     StorePathSet outputClosure;
-    for (auto & i : drv->outputs) {
+    for (auto & i : outputs) {
         if (!wantOutput(i.first, wantedOutputs)) continue;
-        worker.store.computeFSClosure(i.second.path(worker.store, drv->name), outputClosure);
+        worker.store.computeFSClosure(i.second, outputClosure);
     }
 
     /* Filter out our own outputs (which we have already checked). */
-    for (auto & i : drv->outputs)
-        outputClosure.erase(i.second.path(worker.store, drv->name));
+    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 +1390,9 @@ 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.outputs)
-                outputsToDrv.insert_or_assign(j.second.path(worker.store, drv.name), i);
+            auto depOutputs = worker.store.queryDerivationOutputMapAssumeTotal(i);
+            for (auto & j : depOutputs)
+                outputsToDrv.insert_or_assign(j.second, i);
         }
 
     /* Check each path (slow!). */
@@ -1370,20 +1455,19 @@ 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);
+            assert(worker.store.isValidPath(drvPath));
+            auto outputs = worker.store.queryDerivationOutputMapAssumeTotal(depDrvPath);
+            for (auto & j : wantedDepOutputs) {
+                if (outputs.count(j) > 0)
+                    worker.store.computeFSClosure(outputs.at(j), 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 +1510,20 @@ 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->outputs) {
+        auto optPath = i.second.pathOpt(worker.store, drv->name);
+        if (optPath)
+            lockFiles.insert(worker.store.Store::toRealPath(*optPath));
+    }
 
     if (!outputLocks.lockPaths(lockFiles, "", false)) {
         if (!actLock)
@@ -1452,24 +1542,28 @@ 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()) {
+    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->outputs) {
-        if (worker.store.isValidPath(i.second.path(worker.store, drv->name))) continue;
-        debug("removing invalid path '%s'", worker.store.printStorePath(i.second.path(worker.store, drv->name)));
-        deletePath(worker.store.Store::toRealPath(i.second.path(worker.store, drv->name)));
+    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 +1571,6 @@ void DerivationGoal::tryToBuild()
        supported for local builds. */
     bool buildLocally = buildMode != bmNormal || parsedDrv->willBuildLocally();
 
-    /* Is the build hook willing to accept this job? */
     if (!buildLocally) {
         switch (tryBuildHook()) {
             case rpAccept:
@@ -1661,8 +1754,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 +1787,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 +1966,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 +2025,16 @@ StorePathSet DerivationGoal::exportReferences(const StorePathSet & storePaths)
     for (auto & j : paths2) {
         if (j.isDerivation()) {
             Derivation drv = worker.store.derivationFromPath(j);
-            for (auto & k : drv.outputs)
-                worker.store.computeFSClosure(k.second.path(worker.store, drv.name), paths);
+            for (auto & k : drv.outputs) {
+                auto optPath = k.second.pathOpt(worker.store, drv.name);
+                if (!optPath)
+                    /* 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("export references including CA derivations (themselves) is not yet implemented");
+                worker.store.computeFSClosure(*optPath, paths);
+            }
         }
     }
 
@@ -2013,9 +2127,66 @@ void DerivationGoal::startBuilder()
 
     chownToBuilder(tmpDir);
 
-    /* Substitute output placeholders with the actual output paths. */
-    for (auto & output : drv->outputs)
-        inputRewrites[hashPlaceholder(output.first)] = worker.store.printStorePath(output.second.path(worker.store, drv->name));
+    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
+                /* FIXME add option to randomize, so we can audit whether our
+                 * rewrites caught everything */
+                ? makeFallbackPath(outputName)
+            : !needsHashRewrite()
+                /* Can always use original path in sandbox */
+                ? status.known->path
+            : !status.known->valid
+                /* If path doesn't yet exist can just use it */
+                ? status.known->path
+            : buildMode != bmRepair && !*status.known->valid
+                /* 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->valid)
+            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 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 +2370,14 @@ void DerivationGoal::startBuilder()
            rebuilding a path that is in settings.dirsInChroot
            (typically the dependencies of /bin/sh).  Throw them
            out. */
-        for (auto & i : drv->outputs)
-            dirsInChroot.erase(worker.store.printStorePath(i.second.path(worker.store, drv->name)));
+        for (auto & i : drv->outputs) {
+            /* If the name isn't known a prior (i.e. floating content-addressed
+               derivation), the temporary location we use should be fresh and
+               never in the sandbox in the first place. */
+            auto optPath = i.second.pathOpt(worker.store, drv->name);
+            if (optPath)
+                dirsInChroot.erase(worker.store.printStorePath(*optPath));
+        }
 
 #elif __APPLE__
         /* We don't really have any parent prep work to do (yet?)
@@ -2210,33 +2387,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 +2764,11 @@ void DerivationGoal::writeStructuredAttrs()
 
     /* Add an "outputs" object containing the output paths. */
     nlohmann::json outputs;
-    for (auto & i : drv->outputs)
-        outputs[i.first] = rewriteStrings(worker.store.printStorePath(i.second.path(worker.store, drv->name)), 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. */
@@ -2815,19 +2970,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.outputs)
-                    if (wantOutput(output.first, path.outputs))
-                        newPaths.insert(output.second.path(*this, drv.name));
-            } 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->queryDerivationOutputMapAssumeTotal(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)
@@ -3443,14 +3599,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";
 
@@ -3573,23 +3725,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
@@ -3617,11 +3752,18 @@ 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->outputs)
-            if (!worker.store.isValidPath(i.second.path(worker.store, drv->name))) allValid = false;
+        for (auto & i : drv->outputs) {
+            auto optStorePath = i.second.pathOpt(worker.store, drv->name);
+            if (!optStorePath || !worker.store.isValidPath(*optStorePath))
+                allValid = false;
+        }
         if (allValid) return;
     }
 
@@ -3642,47 +3784,47 @@ void DerivationGoal::registerOutputs()
        Nix calls. */
     StorePathSet referenceablePaths;
     for (auto & p : inputPaths) referenceablePaths.insert(p);
-    for (auto & i : drv->outputs) referenceablePaths.insert(i.second.path(worker.store, drv->name));
+    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->outputs) {
-        auto path = worker.store.printStorePath(i.second.path(worker.store, drv->name));
-        if (!missingPaths.count(i.second.path(worker.store, drv->name))) continue;
-
-        Path actualPath = path;
-        if (needsHashRewrite()) {
-            auto r = redirectedOutputs.find(i.second.path(worker.store, drv->name));
-            if (r != redirectedOutputs.end()) {
-                auto redirected = worker.store.Store::toRealPath(r->second);
-                if (buildMode == bmRepair
-                    && redirectedBadOutputs.count(i.second.path(worker.store, drv->name))
-                    && 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;
+    std::map<std::string, std::variant<StorePath, StorePathSet>> outputReferences;
+    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) {
+            outputReferences.insert_or_assign(outputName, 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);
         }
 
@@ -3693,116 +3835,280 @@ 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;
-        }
+        outputReferences.insert_or_assign(outputName, references);
+        outputStats.insert_or_assign(outputName, std::move(st));
+    }
+
+    auto sortedOutputNames = topoSort(outputsToSort,
+        {[&](const std::string & name) {
+            auto x = outputReferences.at(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. */
+                [&](StorePath _) { return StringSet {}; },
+                [&](StorePathSet refs) {
+                    StringSet referencedOutputs;
+                    /* FIXME build inverted map up front so no quadratic waste here */
+                    for (auto & r : refs)
+                        for (auto & [o, p] : scratchOutputs)
+                            if (r == p)
+                                referencedOutputs.insert(o);
+                    return referencedOutputs;
+                },
+            }, x);
+        }},
+        {[&](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(scratchOutputs.at(outputName)));
+
+        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 {
+            [&](StorePath skippedFinalPath) -> std::optional<StorePathSet> {
+                finish(skippedFinalPath);
+                return std::nullopt;
+            },
+            [&](StorePathSet references) -> std::optional<StorePathSet> {
+                return references;
+            },
+        }, outputReferences.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;
+            }
+        };
 
-        /* Check that fixed-output derivations produced the right
-           outputs (i.e., the content hash should match the specified
-           hash). */
-        std::optional<ContentAddress> ca;
+        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;
+        };
 
-        if (! std::holds_alternative<DerivationOutputInputAddressed>(i.second.output)) {
-            DerivationOutputCAFloating outputHash;
-            std::visit(overloaded {
-                [&](DerivationOutputInputAddressed doi) {
-                    assert(false); // Enclosing `if` handles this case in other branch
+        ValidPathInfo newInfo = [&]() {if (auto outputP = std::get_if<DerivationOutputInputAddressed>(&output.output)) {
+            /* input-addressed case */
+            auto requiredFinalPath = outputP->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 };
+            newInfo0.narHash = narHashAndSize.first;
+            newInfo0.narSize = narHashAndSize.second;
+            auto refs = rewriteRefs();
+            newInfo0.references = refs.second;
+            if (refs.first)
+                newInfo0.references.insert(newInfo0.path);
+            return newInfo0;
+        } else {
+            /* content-addressed case */
+            DerivationOutputCAFloating outputHash = std::visit(overloaded {
+                [&](DerivationOutputInputAddressed doi) -> DerivationOutputCAFloating {
+                    // Enclosing `if` handles this case in other branch
+                    throw Error("ought to unreachable, handled in other branch");
                 },
                 [&](DerivationOutputCAFixed dof) {
-                    outputHash = DerivationOutputCAFloating {
+                    return DerivationOutputCAFloating {
                         .method = dof.hash.method,
                         .hashType = dof.hash.hash.type,
                     };
                 },
                 [&](DerivationOutputCAFloating dof) {
-                    outputHash = dof;
+                   return dof;
                 },
-            }, i.second.output);
-
+            }, output.output);
+            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.path(worker.store, drv->name).name());
-
-            // true if either floating CA, or incorrect fixed hash.
-            bool needsMove = true;
-
-            if (auto p = std::get_if<DerivationOutputCAFixed>(& i.second.output)) {
-              Hash & h = p->hash.hash;
-              if (h != h2) {
-
-                /* Throw an error after registering the path as
-                   valid. */
-                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();
+            ValidPathInfo newInfo0 {
+                worker.store.makeFixedOutputPath(
+                    outputHash.method,
+                    got,
+                    outputPathName(drv->name, outputName),
+                    refs.second,
+                    refs.first),
+            };
+            newInfo0.ca = FixedOutputHash {
+                .method = outputHash.method,
+                .hash = got,
+            };
+            newInfo0.references = refs.second;
+            if (refs.first)
+                newInfo0.references.insert(newInfo0.path);
+            {
+                HashModuloSink narSink { htSHA256, oldHashPart };
+                dumpPath(actualPath, narSink);
+                auto narHashAndSize = narSink.finish();
+                newInfo0.narHash = narHashAndSize.first;
+                newInfo0.narSize = narHashAndSize.second;
             }
 
-            if (needsMove) {
-                Path actualDest = worker.store.Store::toRealPath(dest);
+            /* Check wanted hash if output is fixed */
+            if (auto p = std::get_if<DerivationOutputCAFixed>(&output.output)) {
+                Hash & wanted = p->hash.hash;
+                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)));
+                }
+            }
 
-                if (worker.store.isValidPath(dest))
-                    std::rethrow_exception(delayedException);
+            assert(newInfo0.ca);
+            return newInfo0;
+        }}();
+
+        /* 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.pathOpt(worker.store, drv->name);
+        if (!optFixedPath ||
+            worker.store.printStorePath(*optFixedPath) != finalDestPath)
+        {
+            assert(newInfo.ca);
+            dynamicOutputLock.lockPaths({worker.store.toRealPath(finalDestPath)});
+        }
 
-                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));
+        /* 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 (finalDestPath == finalDestPath && 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;
+                    if (chmod(actualPath.c_str(), mode) == -1)
+                        throw SysError("changing mode of '%1%' to %2$o", actualPath, mode);
                 }
-
-                path = worker.store.printStorePath(dest);
-                actualPath = actualDest;
+                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
@@ -3810,45 +4116,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;
@@ -3865,24 +4159,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));
-        info.narHash = 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);
+
+        /* 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(i.first, std::move(info));
+        infos.emplace(outputName, std::move(newInfo));
     }
 
     if (buildMode == bmCheck) return;
@@ -3925,8 +4217,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->outputs) {
-            auto path = worker.store.printStorePath(i.second.path(worker.store, drv->name));
+        for (auto & [_, outputStorePath] : finalOutputs) {
+            auto path = worker.store.printStorePath(outputStorePath);
             Path prev = path + checkSuffix;
             deletePath(prev);
             Path dst = path + checkSuffix;
@@ -3943,8 +4235,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->outputs) {
-            Path prev = worker.store.printStorePath(i.second.path(worker.store, drv->name)) + checkSuffix;
+        for (auto & [_, outputStorePath] : finalOutputs) {
+            Path prev = worker.store.printStorePath(outputStorePath) + checkSuffix;
             deletePath(prev);
         }
     }
@@ -3954,7 +4246,13 @@ void DerivationGoal::registerOutputs()
        outputs, this will fail. */
     {
         ValidPathInfos infos2;
-        for (auto & i : infos) infos2.push_back(i.second);
+        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);
+            infos2.push_back(newInfo);
+        }
         worker.store.registerValidPaths(infos2);
     }
 
@@ -4030,7 +4328,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
@@ -4239,31 +4547,65 @@ void DerivationGoal::flushLine()
 }
 
 
-StorePathSet DerivationGoal::checkPathValidity(bool returnValid, bool checkHash)
+std::map<std::string, std::optional<StorePath>> DerivationGoal::queryDerivationOutputMap()
 {
-    StorePathSet result;
-    for (auto & i : drv->outputs) {
-        if (!wantOutput(i.first, wantedOutputs)) continue;
-        bool good =
-            worker.store.isValidPath(i.second.path(worker.store, drv->name)) &&
-            (!checkHash || worker.pathContentsGood(i.second.path(worker.store, drv->name)));
-        if (good == returnValid) result.insert(i.second.path(worker.store, drv->name));
+    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.pathOpt(worker.store, drv->name));
+        return res;
+    } else {
+        return worker.store.queryDerivationOutputMap(drvPath);
     }
-    return result;
+}
+
+OutputPathMap DerivationGoal::queryDerivationOutputMapAssumeTotal()
+{
+    if (drv->type() != DerivationType::CAFloating) {
+        OutputPathMap res;
+        for (auto & [name, output] : drv->outputs)
+            res.insert_or_assign(name, *output.pathOpt(worker.store, drv->name));
+        return res;
+    } else {
+        return worker.store.queryDerivationOutputMapAssumeTotal(drvPath);
+    }
+}
+
+
+void DerivationGoal::checkPathValidity()
+{
+    bool checkHash = buildMode == bmRepair;
+    for (auto & i : queryDerivationOutputMap()) {
+        InitialOutputStatus status {
+            .wanted = wantOutput(i.first, wantedOutputs),
+        };
+        if (i.second) {
+            auto outputPath = *i.second;
+            status.known = {
+                .path = outputPath,
+                .valid = !worker.store.isValidPath(outputPath)
+                    ? std::optional<bool> {}
+                    : !checkHash || worker.pathContentsGood(outputPath),
+            };
+        }
+        initialOutputs.insert_or_assign(i.first, status);
+    }
+}
+
+
+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 68b081058..58c67e40c 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -15,7 +15,8 @@ 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)
+                // FIXME if we intend to support multiple CA outputs.
+                dof.path(store, drvName, "out")
             };
         },
         [](DerivationOutputCAFloating dof) -> std::optional<StorePath> {
@@ -25,6 +26,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 +114,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;
 }
 
@@ -141,7 +152,7 @@ static StringSet parseStrings(std::istream & str, bool arePaths)
 
 static DerivationOutput parseDerivationOutput(const Store & store, std::istringstream & str)
 {
-    expect(str, ","); auto path = store.parseStorePath(parsePath(str));
+    expect(str, ","); auto pathS = parseString(str);
     expect(str, ","); auto hashAlgo = parseString(str);
     expect(str, ","); const auto hash = parseString(str);
     expect(str, ")");
@@ -152,30 +163,35 @@ static DerivationOutput parseDerivationOutput(const Store & store, std::istrings
             method = FileIngestionMethod::Recursive;
             hashAlgo = string(hashAlgo, 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),
             }
         };
+    }
 }
 
 
@@ -316,17 +332,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, "");
             },
@@ -382,6 +400,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;
@@ -479,7 +507,7 @@ DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool m
             auto hash = hashString(htSHA256, "fixed:out:"
                 + dof.hash.printMethodAlgo() + ":"
                 + dof.hash.hash.to_string(Base16, false) + ":"
-                + store.printStorePath(i.second.path(store, drv.name)));
+                + store.printStorePath(dof.path(store, drv.name, i.first)));
             outputHashes.insert_or_assign(i.first, std::move(hash));
         }
         return outputHashes;
@@ -530,17 +558,9 @@ bool wantOutput(const string & output, const std::set<string> & wanted)
 }
 
 
-StorePathSet BasicDerivation::outputPaths(const Store & store) const
-{
-    StorePathSet paths;
-    for (auto & i : outputs)
-        paths.insert(i.second.path(store, name));
-    return paths;
-}
-
 static DerivationOutput readDerivationOutput(Source & in, const Store & store)
 {
-    auto path = store.parseStorePath(readString(in));
+    auto pathS = readString(in);
     auto hashAlgo = readString(in);
     auto hash = readString(in);
 
@@ -550,29 +570,35 @@ static DerivationOutput readDerivationOutput(Source & in, const Store & store)
             method = FileIngestionMethod::Recursive;
             hashAlgo = string(hashAlgo, 2);
         }
-        auto 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),
             }
         };
+    }
 }
 
 StringSet BasicDerivation::outputNames() const
@@ -624,18 +650,21 @@ void writeDerivation(Sink & out, const Store & store, const BasicDerivation & dr
 {
     out << drv.outputs.size();
     for (auto & i : drv.outputs) {
-        out << i.first
-            << store.printStorePath(i.second.path(store, drv.name));
+        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.output);
@@ -654,5 +683,14 @@ std::string hashPlaceholder(const std::string & outputName)
     return "/" + hashString(htSHA256, "nix-output:" + outputName).to_string(Base32, false);
 }
 
+StorePath downstreamPlaceholder(const Store & store, const StorePath & drvPath, std::string_view outputName)
+{
+    auto drvNameWithExtension = drvPath.name();
+    auto drvName = drvNameWithExtension.substr(0, drvNameWithExtension.size() - 4);
+    return store.makeStorePath(
+        "downstream-placeholder:" + std::string { drvPath.name() } + ":" + std::string { outputName },
+        "compressed:" + std::string { drvPath.hashPart() },
+        outputPathName(drvName, outputName));
+}
 
 }
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 14e0e947a..963b44b8c 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
@@ -48,12 +49,6 @@ struct DerivationOutput
     > output;
     std::optional<HashType> hashAlgoOpt(const Store & store) const;
     std::optional<StorePath> pathOpt(const Store & store, std::string_view drvName) const;
-    /* DEPRECATED: Remove after CA drvs are fully implemented */
-    StorePath path(const Store & store, std::string_view drvName) const {
-        auto p = pathOpt(store, drvName);
-        if (!p) throw UnimplementedError("floating content-addressed derivations are not yet implemented");
-        return *p;
-    }
 };
 
 typedef std::map<string, DerivationOutput> DerivationOutputs;
@@ -101,9 +96,6 @@ 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;
 
@@ -136,6 +128,8 @@ Derivation readDerivation(const Store & store, const Path & drvPath, std::string
 // FIXME: remove
 bool isDerivation(const string & fileName);
 
+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;
@@ -185,4 +179,6 @@ void writeDerivation(Sink & out, const Store & store, const BasicDerivation & dr
 
 std::string hashPlaceholder(const std::string & outputName);
 
+StorePath downstreamPlaceholder(const Store & store, const StorePath & drvPath, std::string_view outputName);
+
 }
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index e96091aae..027efc7c9 100644
--- a/src/libstore/local-store.cc
+++ b/src/libstore/local-store.cc
@@ -578,13 +578,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)
 {
@@ -619,11 +638,11 @@ uint64_t LocalStore::addValidPath(State & state,
         if (checkOutputs) checkDerivationOutputs(info.path, drv);
 
         for (auto & i : drv.outputs) {
-            state.stmtAddDerivationOutput.use()
-                (id)
-                (i.first)
-                (printStorePath(i.second.path(*this, drv.name)))
-                .exec();
+            /* Floating CA derivations have indeterminate output paths until
+               they are built, so don't register anything in that case */
+            auto optPath = i.second.pathOpt(*this, drv.name);
+            if (optPath)
+                linkDeriverToPath(state, id, i.first, *optPath);
         }
     }
 
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index 627b1f557..bf4016b13 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -282,6 +282,12 @@ private:
        specified by the ‘secret-key-files’ option. */
     void signPathInfo(ValidPathInfo & info);
 
+    /* Add a mapping from the deriver of the path info (if specified) to its
+     * out path
+     */
+    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 0ae1ceaad..9024fb2bd 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] : queryDerivationOutputMap(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->outputs)
-                if (wantOutput(j.first, path.outputs)
-                    && !isValidPath(j.second.path(*this, drv->name)))
-                    invalid.insert(printStorePath(j.second.path(*this, drv->name)));
-            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 005415666..e69d15c53 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -74,7 +74,7 @@ void write(const Store & store, Sink & out, const StorePath & storePath)
 template<>
 std::optional<StorePath> read(const Store & store, Source & from, Phantom<std::optional<StorePath>> _)
 {
-	auto s = readString(from);
+    auto s = readString(from);
     return s == "" ? std::optional<StorePath> {} : store.parseStorePath(s);
 }
 
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index e66c04df4..63accd514 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));
 }
 
 
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 9003ab541..943f08211 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -244,10 +244,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,
diff --git a/src/libutil/serialise.hh b/src/libutil/serialise.hh
index c29c6b29b..3650857aa 100644
--- a/src/libutil/serialise.hh
+++ b/src/libutil/serialise.hh
@@ -22,6 +22,12 @@ struct Sink
     }
 };
 
+/* Just throws away data. */
+struct NullSink : Sink
+{
+    void operator () (const unsigned char * data, size_t len) override
+    { }
+};
 
 /* A buffered abstract sink. */
 struct BufferedSink : virtual Sink
diff --git a/src/nix-build/nix-build.cc b/src/nix-build/nix-build.cc
index 94412042f..be73ea724 100755
--- a/src/nix-build/nix-build.cc
+++ b/src/nix-build/nix-build.cc
@@ -487,50 +487,56 @@ static void _main(int argc, char * * argv)
 
         std::vector<StorePathWithOutputs> pathsToBuild;
 
-        std::map<Path, Path> drvPrefixes;
-        std::map<Path, Path> resultSymlinks;
-        std::vector<Path> outPaths;
+        std::map<StorePath, std::pair<size_t, StringSet>> drvMap;
 
         for (auto & drvInfo : drvs) {
-            auto drvPath = drvInfo.queryDrvPath();
-            auto outPath = drvInfo.queryOutPath();
+            auto drvPath = store->parseStorePath(drvInfo.queryDrvPath());
 
             auto outputName = drvInfo.queryOutputName();
             if (outputName == "")
-                throw Error("derivation '%s' lacks an 'outputName' attribute", drvPath);
+                throw Error("derivation '%s' lacks an 'outputName' attribute", store->printStorePath(drvPath));
 
-            pathsToBuild.push_back({store->parseStorePath(drvPath), {outputName}});
+            pathsToBuild.push_back({drvPath, {outputName}});
 
-            std::string drvPrefix;
-            auto i = drvPrefixes.find(drvPath);
-            if (i != drvPrefixes.end())
-                drvPrefix = i->second;
+            auto i = drvMap.find(drvPath);
+            if (i != drvMap.end())
+                i->second.second.insert(outputName);
             else {
-                drvPrefix = outLink;
-                if (drvPrefixes.size())
-                    drvPrefix += fmt("-%d", drvPrefixes.size() + 1);
-                drvPrefixes[drvPath] = drvPrefix;
+                drvMap[drvPath] = {drvMap.size(), {outputName}};
             }
-
-            std::string symlink = drvPrefix;
-            if (outputName != "out") symlink += "-" + outputName;
-
-            resultSymlinks[symlink] = outPath;
-            outPaths.push_back(outPath);
         }
 
         buildPaths(pathsToBuild);
 
         if (dryRun) return;
 
-        for (auto & symlink : resultSymlinks)
-            if (auto store2 = store.dynamic_pointer_cast<LocalFSStore>())
-                store2->addPermRoot(store->parseStorePath(symlink.second), absPath(symlink.first), true);
+        std::vector<StorePath> outPaths;
+
+        for (auto & [drvPath, info] : drvMap) {
+            auto & [counter, wantedOutputs] = info;
+            std::string drvPrefix = outLink;
+            if (counter)
+                drvPrefix += fmt("-%d", counter + 1);
+
+            auto builtOutputs = store->queryDerivationOutputMapAssumeTotal(drvPath);
+
+            for (auto & outputName : wantedOutputs) {
+                auto outputPath = builtOutputs.at(outputName);
+
+                if (auto store2 = store.dynamic_pointer_cast<LocalFSStore>()) {
+                    std::string symlink = drvPrefix;
+                    if (outputName != "out") symlink += "-" + outputName;
+                    store2->addPermRoot(outputPath, absPath(symlink), true);
+                }
+
+                outPaths.push_back(outputPath);
+            }
+        }
 
         logger->stop();
 
         for (auto & path : outPaths)
-            std::cout << path << '\n';
+            std::cout << store->printStorePath(path) << '\n';
     }
 }
 
diff --git a/src/nix-store/nix-store.cc b/src/nix-store/nix-store.cc
index 2996e36c4..9eadf62e4 100644
--- a/src/nix-store/nix-store.cc
+++ b/src/nix-store/nix-store.cc
@@ -65,6 +65,7 @@ static PathSet realisePath(StorePathWithOutputs path, bool build = true)
 
     if (path.path.isDerivation()) {
         if (build) store->buildPaths({path});
+        auto outputPaths = store->queryDerivationOutputMapAssumeTotal(path.path);
         Derivation drv = store->derivationFromPath(path.path);
         rootNr++;
 
@@ -77,7 +78,8 @@ static PathSet realisePath(StorePathWithOutputs path, bool build = true)
             if (i == drv.outputs.end())
                 throw Error("derivation '%s' does not have an output named '%s'",
                     store2->printStorePath(path.path), j);
-            auto outPath = store2->printStorePath(i->second.path(*store, drv.name));
+            auto outPath = outputPaths.at(i->first);
+            auto retPath = store->printStorePath(outPath);
             if (store2) {
                 if (gcRoot == "")
                     printGCWarning();
@@ -85,10 +87,10 @@ static PathSet realisePath(StorePathWithOutputs path, bool build = true)
                     Path rootName = gcRoot;
                     if (rootNr > 1) rootName += "-" + std::to_string(rootNr);
                     if (i->first != "out") rootName += "-" + i->first;
-                    outPath = store2->addPermRoot(store->parseStorePath(outPath), rootName, indirectRoot);
+                    retPath = store2->addPermRoot(outPath, rootName, indirectRoot);
                 }
             }
-            outputs.insert(outPath);
+            outputs.insert(retPath);
         }
         return outputs;
     }
@@ -218,8 +220,14 @@ static StorePathSet maybeUseOutputs(const StorePath & storePath, bool useOutput,
     if (useOutput && storePath.isDerivation()) {
         auto drv = store->derivationFromPath(storePath);
         StorePathSet outputs;
-        for (auto & i : drv.outputs)
-            outputs.insert(i.second.path(*store, drv.name));
+        if (forceRealise)
+            return store->queryDerivationOutputs(storePath);
+        for (auto & i : drv.outputs) {
+            auto optPath = i.second.pathOpt(*store, drv.name);
+            if (!optPath)
+                throw UsageError("Cannot use output path of floating content-addressed derivation until we know what it is (e.g. by building it)");
+            outputs.insert(*optPath);
+        }
         return outputs;
     }
     else return {storePath};
@@ -309,11 +317,9 @@ static void opQuery(Strings opFlags, Strings opArgs)
 
         case qOutputs: {
             for (auto & i : opArgs) {
-                auto i2 = store->followLinksToStorePath(i);
-                if (forceRealise) realisePath({i2});
-                Derivation drv = store->derivationFromPath(i2);
-                for (auto & j : drv.outputs)
-                    cout << fmt("%1%\n", store->printStorePath(j.second.path(*store, drv.name)));
+                auto outputs = maybeUseOutputs(store->followLinksToStorePath(i), true, forceRealise);
+                for (auto & outputPath : outputs)
+                    cout << fmt("%1%\n", store->printStorePath(outputPath));
             }
             break;
         }
diff --git a/src/nix/build.cc b/src/nix/build.cc
index 13d14a7fb..a66e8dac4 100644
--- a/src/nix/build.cc
+++ b/src/nix/build.cc
@@ -74,7 +74,8 @@ struct CmdBuild : InstallablesCommand, MixDryRun, MixProfile
                             store2->addPermRoot(bo.path, absPath(symlink), true);
                         },
                         [&](BuildableFromDrv bfd) {
-                            for (auto & output : bfd.outputs) {
+                            auto builtOutputs = store->queryDerivationOutputMapAssumeTotal(bfd.drvPath);
+                            for (auto & output : builtOutputs) {
                                 std::string symlink = outLink;
                                 if (i) symlink += fmt("-%d", i);
                                 if (output.first != "out") symlink += fmt("-%s", output.first);
diff --git a/src/nix/command.cc b/src/nix/command.cc
index da32819da..4a93d8e73 100644
--- a/src/nix/command.cc
+++ b/src/nix/command.cc
@@ -137,7 +137,9 @@ void MixProfile::updateProfile(const Buildables & buildables)
             },
             [&](BuildableFromDrv bfd) {
                 for (auto & output : bfd.outputs) {
-                    result.push_back(output.second);
+                    if (!output.second)
+                        throw Error("output path should be known because we just tried to build it");
+                    result.push_back(*output.second);
                 }
             },
         }, buildable);
diff --git a/src/nix/installables.cc b/src/nix/installables.cc
index ea152709f..2ff94cd38 100644
--- a/src/nix/installables.cc
+++ b/src/nix/installables.cc
@@ -302,10 +302,10 @@ struct InstallableStorePath : Installable
     Buildables toBuildables() override
     {
         if (storePath.isDerivation()) {
-            std::map<std::string, StorePath> outputs;
+            std::map<std::string, std::optional<StorePath>> outputs;
             auto drv = store->readDerivation(storePath);
             for (auto & [name, output] : drv.outputs)
-                outputs.emplace(name, output.path(*store, drv.name));
+                outputs.emplace(name, output.pathOpt(*store, drv.name));
             return {
                 BuildableFromDrv {
                     .drvPath = storePath,
@@ -331,7 +331,7 @@ Buildables InstallableValue::toBuildables()
 {
     Buildables res;
 
-    std::map<StorePath, OutputPathMap> drvsToOutputs;
+    std::map<StorePath, std::map<std::string, std::optional<StorePath>>> drvsToOutputs;
 
     // Group by derivation, helps with .all in particular
     for (auto & drv : toDerivations()) {
@@ -674,8 +674,11 @@ StorePathSet toStorePaths(ref<Store> store,
                     outPaths.insert(bo.path);
                 },
                 [&](BuildableFromDrv bfd) {
-                    for (auto & output : bfd.outputs)
-                        outPaths.insert(output.second);
+                    for (auto & output : bfd.outputs) {
+                        if (!output.second)
+                            throw Error("Cannot operate on output of unbuilt CA drv");
+                        outPaths.insert(*output.second);
+                    }
                 },
             }, b);
     } else {
diff --git a/src/nix/installables.hh b/src/nix/installables.hh
index 26e87ee3a..41c75a4ed 100644
--- a/src/nix/installables.hh
+++ b/src/nix/installables.hh
@@ -20,7 +20,7 @@ struct BuildableOpaque {
 
 struct BuildableFromDrv {
     StorePath drvPath;
-    std::map<std::string, StorePath> outputs;
+    std::map<std::string, std::optional<StorePath>> outputs;
 };
 
 typedef std::variant<
@@ -82,7 +82,7 @@ struct InstallableValue : Installable
     struct DerivationInfo
     {
         StorePath drvPath;
-        StorePath outPath;
+        std::optional<StorePath> outPath;
         std::string outputName;
     };
 
diff --git a/src/nix/profile.cc b/src/nix/profile.cc
index 7dcc0b6d4..be002519a 100644
--- a/src/nix/profile.cc
+++ b/src/nix/profile.cc
@@ -178,7 +178,9 @@ struct CmdProfileInstall : InstallablesCommand, MixDefaultProfile
                 auto [attrPath, resolvedRef, drv] = installable2->toDerivation();
 
                 ProfileElement element;
-                element.storePaths = {drv.outPath}; // FIXME
+                if (!drv.outPath)
+                    throw UnimplementedError("CA derivations are not yet supported by 'nix profile'");
+                element.storePaths = {*drv.outPath}; // FIXME
                 element.source = ProfileElementSource{
                     installable2->flakeRef,
                     resolvedRef,
@@ -189,7 +191,7 @@ struct CmdProfileInstall : InstallablesCommand, MixDefaultProfile
 
                 manifest.elements.emplace_back(std::move(element));
             } else
-                throw Error("'nix profile install' does not support argument '%s'", installable->what());
+                throw UnimplementedError("'nix profile install' does not support argument '%s'", installable->what());
         }
 
         store->buildPaths(pathsToBuild);
@@ -347,7 +349,9 @@ struct CmdProfileUpgrade : virtual SourceExprCommand, MixDefaultProfile, MixProf
                 printInfo("upgrading '%s' from flake '%s' to '%s'",
                     element.source->attrPath, element.source->resolvedRef, resolvedRef);
 
-                element.storePaths = {drv.outPath}; // FIXME
+                if (!drv.outPath)
+                    throw UnimplementedError("CA derivations are not yet supported by 'nix profile'");
+                element.storePaths = {*drv.outPath}; // FIXME
                 element.source = ProfileElementSource{
                     installable.flakeRef,
                     resolvedRef,
diff --git a/src/nix/repl.cc b/src/nix/repl.cc
index c3c9e54a8..0224f891d 100644
--- a/src/nix/repl.cc
+++ b/src/nix/repl.cc
@@ -488,10 +488,10 @@ bool NixRepl::processLine(string line)
                but doing it in a child makes it easier to recover from
                problems / SIGINT. */
             if (runProgram(settings.nixBinDir + "/nix", Strings{"build", "--no-link", drvPath}) == 0) {
-                auto drv = readDerivation(*state->store, drvPath, Derivation::nameFromPath(state->store->parseStorePath(drvPath)));
+                auto outputs = state->store->queryDerivationOutputMapAssumeTotal(state->store->parseStorePath(drvPath));
                 std::cout << std::endl << "this derivation produced the following outputs:" << std::endl;
-                for (auto & i : drv.outputs)
-                    std::cout << fmt("  %s -> %s\n", i.first, state->store->printStorePath(i.second.path(*state->store, drv.name)));
+                for (auto & i : outputs)
+                    std::cout << fmt("  %s -> %s\n", i.first, state->store->printStorePath(i.second));
             }
         } else if (command == ":i") {
             runProgram(settings.nixBinDir + "/nix-env", Strings{"-i", drvPath});
diff --git a/src/nix/show-derivation.cc b/src/nix/show-derivation.cc
index 1b51d114f..b204b2d4c 100644
--- a/src/nix/show-derivation.cc
+++ b/src/nix/show-derivation.cc
@@ -69,12 +69,12 @@ struct CmdShowDerivation : InstallablesCommand
                 auto outputsObj(drvObj.object("outputs"));
                 for (auto & output : drv.outputs) {
                     auto outputObj(outputsObj.object(output.first));
-                    outputObj.attr("path", store->printStorePath(output.second.path(*store, drv.name)));
-
                     std::visit(overloaded {
                         [&](DerivationOutputInputAddressed doi) {
+                            outputObj.attr("path", store->printStorePath(doi.path));
                         },
                         [&](DerivationOutputCAFixed dof) {
+                            outputObj.attr("path", store->printStorePath(dof.path(*store, drv.name, output.first)));
                             outputObj.attr("hashAlgo", dof.hash.printMethodAlgo());
                             outputObj.attr("hash", dof.hash.hash.to_string(Base16, false));
                         },
diff --git a/tests/content-addressed.nix b/tests/content-addressed.nix
new file mode 100644
index 000000000..586e4cba6
--- /dev/null
+++ b/tests/content-addressed.nix
@@ -0,0 +1,19 @@
+with import ./config.nix;
+
+{ seed ? 0 }:
+# A simple content-addressed derivation.
+# The derivation can be arbitrarily modified by passing a different `seed`,
+# but the output will always be the same
+mkDerivation {
+  name = "simple-content-addressed";
+  buildCommand = ''
+    set -x
+    echo "Building a CA derivation"
+    echo "The seed is ${toString seed}"
+    mkdir -p $out
+    echo "Hello World" > $out/hello
+  '';
+  __contentAddressed = true;
+  outputHashMode = "recursive";
+  outputHashAlgo = "sha256";
+}
diff --git a/tests/content-addressed.sh b/tests/content-addressed.sh
new file mode 100644
index 000000000..2968f3a8c
--- /dev/null
+++ b/tests/content-addressed.sh
@@ -0,0 +1,16 @@
+#!/usr/bin/env bash
+
+source common.sh
+
+clearStore
+clearCache
+
+export REMOTE_STORE=file://$cacheDir
+
+drv=$(nix-instantiate --experimental-features ca-derivations ./content-addressed.nix --arg seed 1)
+nix --experimental-features 'nix-command ca-derivations' show-derivation --derivation "$drv" --arg seed 1
+
+out1=$(nix-build --experimental-features ca-derivations ./content-addressed.nix --arg seed 1 --no-out-link)
+out2=$(nix-build --experimental-features ca-derivations ./content-addressed.nix --arg seed 2 --no-out-link)
+
+test $out1 == $out2
diff --git a/tests/local.mk b/tests/local.mk
index 0f3bfe606..4f4e63a5a 100644
--- a/tests/local.mk
+++ b/tests/local.mk
@@ -32,7 +32,8 @@ nix_tests = \
   post-hook.sh \
   function-trace.sh \
   recursive.sh \
-  flakes.sh
+  flakes.sh \
+  content-addressed.sh
   # parallel.sh
 
 install-tests += $(foreach x, $(nix_tests), tests/$(x))
diff --git a/tests/multiple-outputs.nix b/tests/multiple-outputs.nix
index 4a9010d18..b915493f7 100644
--- a/tests/multiple-outputs.nix
+++ b/tests/multiple-outputs.nix
@@ -2,6 +2,21 @@ with import ./config.nix;
 
 rec {
 
+  # Want to ensure that "out" doesn't get a suffix on it's path.
+  nameCheck = mkDerivation {
+    name = "multiple-outputs-a";
+    outputs = [ "out" "dev" ];
+    builder = builtins.toFile "builder.sh"
+      ''
+        mkdir $first $second
+        test -z $all
+        echo "first" > $first/file
+        echo "second" > $second/file
+        ln -s $first $second/link
+      '';
+    helloString = "Hello, world!";
+  };
+
   a = mkDerivation {
     name = "multiple-outputs-a";
     outputs = [ "first" "second" ];
diff --git a/tests/multiple-outputs.sh b/tests/multiple-outputs.sh
index bedbc39a4..7a6ec181d 100644
--- a/tests/multiple-outputs.sh
+++ b/tests/multiple-outputs.sh
@@ -4,6 +4,12 @@ clearStore
 
 rm -f $TEST_ROOT/result*
 
+# Test whether the output names match our expectations
+outPath=$(nix-instantiate multiple-outputs.nix --eval -A nameCheck.out.outPath)
+[ "$(echo "$outPath" | sed -E 's_^".*/[^-/]*-([^/]*)"$_\1_')" = "multiple-outputs-a" ]
+outPath=$(nix-instantiate multiple-outputs.nix --eval -A nameCheck.dev.outPath)
+[ "$(echo "$outPath" | sed -E 's_^".*/[^-/]*-([^/]*)"$_\1_')" = "multiple-outputs-a-dev" ]
+
 # Test whether read-only evaluation works when referring to the
 # ‘drvPath’ attribute.
 echo "evaluating c..."