Merge branch 'single-ca-drv-build' of https://github.com/obsidiansystems/nix

30 files changed, 1098 insertions, 513 deletions

diff --git a/perl/lib/Nix/Store.xs b/perl/lib/Nix/Store.xs
index 4e038866e..8546f6307 100644
--- a/perl/lib/Nix/Store.xs
+++ b/perl/lib/Nix/Store.xs
@@ -303,11 +303,14 @@ SV * derivationFromPath(char * drvPath)
             hash = newHV();
 
             HV * outputs = newHV();
-            for (auto & i : drv.outputsAndPaths(*store()))
+            for (auto & i : drv.outputsAndOptPaths(*store())) {
                 hv_store(
                     outputs, i.first.c_str(), i.first.size(),
-                    newSVpv(store()->printStorePath(i.second.second).c_str(), 0),
+                    !i.second.second
+                        ? newSV(0) /* null value */
+                        : newSVpv(store()->printStorePath(*i.second.second).c_str(), 0),
                     0);
+            }
             hv_stores(hash, "outputs", newRV((SV *) outputs));
 
             AV * inputDrvs = newAV();
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 5d6e39aa0..91916e8bf 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -38,8 +38,11 @@ DrvInfo::DrvInfo(EvalState & state, ref<Store> store, const std::string & drvPat
     auto i = drv.outputs.find(outputName);
     if (i == drv.outputs.end())
         throw Error("derivation '%s' does not have output '%s'", store->printStorePath(drvPath), outputName);
+    auto & [outputName, output] = *i;
 
-    outPath = store->printStorePath(i->second.path(*store, drv.name));
+    auto optStorePath = output.path(*store, drv.name, outputName);
+    if (optStorePath)
+        outPath = store->printStorePath(*optStorePath);
 }
 
 
@@ -77,12 +80,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 3350d05d4..4a0dd5544 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,50 @@ 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->queryDerivationOutputMap(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)));
+            }
+        }
+    }
 }
 
+/* Add and attribute to the given attribute map from the output name to
+   the output path, or a placeholder.
+
+   Where possible the path is used, but for floating CA derivations we
+   may not know it. For sake of determinism we always assume we don't
+   and instead put in a place holder. In either case, however, the
+   string context will contain the drv path and output name, so
+   downstream derivations will have the proper dependency, and in
+   addition, before building, the placeholder will be rewritten to be
+   the actual path.
+
+   The 'drv' and 'drvPath' outputs must correspond. */
+static void mkOutputString(EvalState & state, Value & v,
+    const StorePath & drvPath, const BasicDerivation & drv,
+    std::pair<string, DerivationOutput> o)
+{
+    auto optOutputPath = o.second.path(*state.store, drv.name, o.first);
+    mkString(
+        *state.allocAttr(v, state.symbols.create(o.first)),
+        optOutputPath
+            ? state.store->printStorePath(*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,9 +146,8 @@ static void import(EvalState & state, const Pos & pos, Value & vPath, Value * vS
         state.mkList(*outputsVal, drv.outputs.size());
         unsigned int outputs_index = 0;
 
-        for (const auto & o : drv.outputsAndPaths(*state.store)) {
-            v2 = state.allocAttr(w, state.symbols.create(o.first));
-            mkString(*v2, state.store->printStorePath(o.second.second), {"!" + o.first + "!" + path});
+        for (const auto & o : drv.outputs) {
+            mkOutputString(state, w, storePath, drv, o);
             outputsVal->listElems()[outputs_index] = state.allocValue();
             mkString(*(outputsVal->listElems()[outputs_index++]), o.first);
         }
@@ -1080,16 +1111,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.outputsAndPaths(*state.store)) {
-        mkString(*state.allocAttr(v, state.symbols.create(i.first)),
-            state.store->printStorePath(i.second.second), {"!" + 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 dd932cee9..ce973862d 100644
--- a/src/libstore/build.cc
+++ b/src/libstore/build.cc
@@ -16,6 +16,7 @@
 #include "machines.hh"
 #include "daemon.hh"
 #include "worker-protocol.hh"
+#include "topo-sort.hh"
 
 #include <algorithm>
 #include <iostream>
@@ -717,6 +718,33 @@ typedef enum {rpAccept, rpDecline, rpPostpone} HookReply;
 
 class SubstitutionGoal;
 
+/* Unless we are repairing, we don't both to test validity and just assume it,
+   so the choices are `Absent` or `Valid`. */
+enum struct PathStatus {
+    Corrupt,
+    Absent,
+    Valid,
+};
+
+struct InitialOutputStatus {
+    StorePath path;
+    PathStatus status;
+    /* Valid in the store, and additionally non-corrupt if we are repairing */
+    bool isValid() const {
+        return status == PathStatus::Valid;
+    }
+    /* Merely present, allowed to be corrupt */
+    bool isPresent() const {
+        return status == PathStatus::Corrupt
+            || status == PathStatus::Valid;
+    }
+};
+
+struct InitialOutput {
+    bool wanted;
+    std::optional<InitialOutputStatus> known;
+};
+
 class DerivationGoal : public Goal
 {
 private:
@@ -744,19 +772,14 @@ private:
 
     /* The remainder is state held during the build. */
 
-    /* Locks on the output paths. */
+    /* Locks on (fixed) output paths. */
     PathLocks outputLocks;
 
     /* All input paths (that is, the union of FS closures of the
        immediate input paths). */
     StorePathSet inputPaths;
 
-    /* Outputs that are already valid.  If we're repairing, these are
-       the outputs that are valid *and* not corrupt. */
-    StorePathSet validPaths;
-
-    /* Outputs that are corrupt or not valid. */
-    StorePathSet missingPaths;
+    std::map<std::string, InitialOutput> initialOutputs;
 
     /* User selected for running the builder. */
     std::unique_ptr<UserLock> buildUser;
@@ -839,6 +862,31 @@ private:
     typedef map<StorePath, StorePath> RedirectedOutputs;
     RedirectedOutputs redirectedOutputs;
 
+    /* The outputs paths used during the build.
+
+       - Input-addressed derivations or fixed content-addressed outputs are
+         sometimes built when some of their outputs already exist, and can not
+         be hidden via sandboxing. We use temporary locations instead and
+         rewrite after the build. Otherwise the regular predetermined paths are
+         put here.
+
+       - Floating content-addressed derivations do not know their final build
+         output paths until the outputs are hashed, so random locations are
+         used, and then renamed. The randomness helps guard against hidden
+         self-references.
+     */
+    OutputPathMap scratchOutputs;
+
+    /* The final output paths of the build.
+
+       - For input-addressed derivations, always the precomputed paths
+
+       - For content-addressed derivations, calcuated from whatever the hash
+         ends up being. (Note that fixed outputs derivations that produce the
+         "wrong" output still install that data under its true content-address.)
+     */
+    OutputPathMap finalOutputs;
+
     BuildMode buildMode;
 
     /* If we're repairing without a chroot, there may be outputs that
@@ -937,7 +985,8 @@ private:
     void getDerivation();
     void loadDerivation();
     void haveDerivation();
-    void outputsSubstituted();
+    void outputsSubstitutionTried();
+    void gaveUpOnSubstitution();
     void closureRepaired();
     void inputsRealised();
     void tryToBuild();
@@ -998,13 +1047,27 @@ private:
     void handleEOF(int fd) override;
     void flushLine();
 
+    /* Wrappers around the corresponding Store methods that first consult the
+       derivation.  This is currently needed because when there is no drv file
+       there also is no DB entry. */
+    std::map<std::string, std::optional<StorePath>> queryPartialDerivationOutputMap();
+    OutputPathMap queryDerivationOutputMap();
+
     /* Return the set of (in)valid paths. */
-    StorePathSet checkPathValidity(bool returnValid, bool checkHash);
+    void checkPathValidity();
 
     /* Forcibly kill the child process, if any. */
     void killChild();
 
-    void addHashRewrite(const StorePath & path);
+    /* Create alternative path calculated from but distinct from the
+       input, so we can avoid overwriting outputs (or other store paths)
+       that already exist. */
+    StorePath makeFallbackPath(const StorePath & path);
+    /* Make a path to another based on the output name along with the
+       derivation hash. */
+    /* FIXME add option to randomize, so we can audit whether our
+       rewrites caught everything */
+    StorePath makeFallbackPath(std::string_view outputName);
 
     void repairClosure();
 
@@ -1047,7 +1110,7 @@ DerivationGoal::DerivationGoal(const StorePath & drvPath, const BasicDerivation
 {
     this->drv = std::make_unique<BasicDerivation>(BasicDerivation(drv));
     state = &DerivationGoal::haveDerivation;
-    name = fmt("building of %s", worker.store.showPaths(drv.outputPaths(worker.store)));
+    name = fmt("building of %s", StorePathWithOutputs { drvPath, drv.outputNames() }.to_string(worker.store));
     trace("created");
 
     mcExpectedBuilds = std::make_unique<MaintainCount<uint64_t>>(worker.expectedBuilds);
@@ -1179,43 +1242,60 @@ void DerivationGoal::haveDerivation()
 {
     trace("have derivation");
 
+    if (drv->type() == DerivationType::CAFloating)
+        settings.requireExperimentalFeature("ca-derivations");
+
     retrySubstitution = false;
 
-    for (auto & i : drv->outputsAndPaths(worker.store))
-        worker.store.addTempRoot(i.second.second);
+    for (auto & i : drv->outputsAndOptPaths(worker.store))
+        if (i.second.second)
+            worker.store.addTempRoot(*i.second.second);
 
     /* Check what outputs paths are not already valid. */
-    auto invalidOutputs = checkPathValidity(false, buildMode == bmRepair);
+    checkPathValidity();
+    bool allValid = true;
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.wanted) continue;
+        if (!status.known || !status.known->isValid()) {
+            allValid = false;
+            break;
+        }
+    }
 
     /* If they are all valid, then we're done. */
-    if (invalidOutputs.size() == 0 && buildMode == bmNormal) {
+    if (allValid && buildMode == bmNormal) {
         done(BuildResult::AlreadyValid);
         return;
     }
 
     parsedDrv = std::make_unique<ParsedDerivation>(drvPath, *drv);
 
-    if (drv->type() == DerivationType::CAFloating) {
-        settings.requireExperimentalFeature("ca-derivations");
-        throw UnimplementedError("ca-derivations isn't implemented yet");
-    }
-
 
     /* We are first going to try to create the invalid output paths
        through substitutes.  If that doesn't work, we'll build
        them. */
     if (settings.useSubstitutes && parsedDrv->substitutesAllowed())
-        for (auto & i : invalidOutputs)
-            addWaitee(worker.makeSubstitutionGoal(i, buildMode == bmRepair ? Repair : NoRepair, getDerivationCA(*drv)));
+        for (auto & [_, status] : initialOutputs) {
+            if (!status.wanted) continue;
+            if (!status.known) {
+                warn("do not know how to query for unknown floating content-addressed derivation output yet");
+                /* Nothing to wait for; tail call */
+                return DerivationGoal::gaveUpOnSubstitution();
+            }
+            addWaitee(worker.makeSubstitutionGoal(
+                status.known->path,
+                buildMode == bmRepair ? Repair : NoRepair,
+                getDerivationCA(*drv)));
+        }
 
     if (waitees.empty()) /* to prevent hang (no wake-up event) */
-        outputsSubstituted();
+        outputsSubstitutionTried();
     else
-        state = &DerivationGoal::outputsSubstituted;
+        state = &DerivationGoal::outputsSubstitutionTried;
 }
 
 
-void DerivationGoal::outputsSubstituted()
+void DerivationGoal::outputsSubstitutionTried()
 {
     trace("all outputs substituted (maybe)");
 
@@ -1239,7 +1319,14 @@ void DerivationGoal::outputsSubstituted()
         return;
     }
 
-    auto nrInvalid = checkPathValidity(false, buildMode == bmRepair).size();
+    checkPathValidity();
+    size_t nrInvalid = 0;
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.wanted) continue;
+        if (!status.known || !status.known->isValid())
+            nrInvalid++;
+    }
+
     if (buildMode == bmNormal && nrInvalid == 0) {
         done(BuildResult::Substituted);
         return;
@@ -1252,9 +1339,14 @@ void DerivationGoal::outputsSubstituted()
         throw Error("some outputs of '%s' are not valid, so checking is not possible",
             worker.store.printStorePath(drvPath));
 
-    /* Otherwise, at least one of the output paths could not be
-       produced using a substitute.  So we have to build instead. */
+    /* Nothing to wait for; tail call */
+    gaveUpOnSubstitution();
+}
 
+/* At least one of the output paths could not be
+   produced using a substitute.  So we have to build instead. */
+void DerivationGoal::gaveUpOnSubstitution()
+{
     /* Make sure checkPathValidity() from now on checks all
        outputs. */
     wantedOutputs.clear();
@@ -1287,15 +1379,16 @@ void DerivationGoal::repairClosure()
        that produced those outputs. */
 
     /* Get the output closure. */
+    auto outputs = queryDerivationOutputMap();
     StorePathSet outputClosure;
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
+    for (auto & i : outputs) {
         if (!wantOutput(i.first, wantedOutputs)) continue;
-        worker.store.computeFSClosure(i.second.second, outputClosure);
+        worker.store.computeFSClosure(i.second, outputClosure);
     }
 
     /* Filter out our own outputs (which we have already checked). */
-    for (auto & i : drv->outputsAndPaths(worker.store))
-        outputClosure.erase(i.second.second);
+    for (auto & i : outputs)
+        outputClosure.erase(i.second);
 
     /* Get all dependencies of this derivation so that we know which
        derivation is responsible for which path in the output
@@ -1305,9 +1398,10 @@ void DerivationGoal::repairClosure()
     std::map<StorePath, StorePath> outputsToDrv;
     for (auto & i : inputClosure)
         if (i.isDerivation()) {
-            Derivation drv = worker.store.derivationFromPath(i);
-            for (auto & j : drv.outputsAndPaths(worker.store))
-                outputsToDrv.insert_or_assign(j.second.second, i);
+            auto depOutputs = worker.store.queryPartialDerivationOutputMap(i);
+            for (auto & j : depOutputs)
+                if (j.second)
+                    outputsToDrv.insert_or_assign(*j.second, i);
         }
 
     /* Check each path (slow!). */
@@ -1370,20 +1464,24 @@ void DerivationGoal::inputsRealised()
 
     /* First, the input derivations. */
     if (useDerivation)
-        for (auto & i : dynamic_cast<Derivation *>(drv.get())->inputDrvs) {
+        for (auto & [depDrvPath, wantedDepOutputs] : dynamic_cast<Derivation *>(drv.get())->inputDrvs) {
             /* Add the relevant output closures of the input derivation
                `i' as input paths.  Only add the closures of output paths
                that are specified as inputs. */
-            assert(worker.store.isValidPath(i.first));
-            Derivation inDrv = worker.store.derivationFromPath(i.first);
-            for (auto & j : i.second) {
-                auto k = inDrv.outputs.find(j);
-                if (k != inDrv.outputs.end())
-                    worker.store.computeFSClosure(k->second.path(worker.store, inDrv.name), inputPaths);
-                else
+            assert(worker.store.isValidPath(drvPath));
+            auto outputs = worker.store.queryPartialDerivationOutputMap(depDrvPath);
+            for (auto & j : wantedDepOutputs) {
+                if (outputs.count(j) > 0) {
+                    auto optRealizedInput = outputs.at(j);
+                    if (!optRealizedInput)
+                        throw Error(
+                            "derivation '%s' requires output '%s' from input derivation '%s', which is supposedly realized already, yet we still don't know what path corresponds to that output",
+                            worker.store.printStorePath(drvPath), j, worker.store.printStorePath(drvPath));
+                    worker.store.computeFSClosure(*optRealizedInput, inputPaths);
+                } else
                     throw Error(
                         "derivation '%s' requires non-existent output '%s' from input derivation '%s'",
-                        worker.store.printStorePath(drvPath), j, worker.store.printStorePath(i.first));
+                        worker.store.printStorePath(drvPath), j, worker.store.printStorePath(drvPath));
             }
         }
 
@@ -1426,14 +1524,18 @@ void DerivationGoal::tryToBuild()
 {
     trace("trying to build");
 
-    /* Obtain locks on all output paths.  The locks are automatically
-       released when we exit this function or Nix crashes.  If we
-       can't acquire the lock, then continue; hopefully some other
-       goal can start a build, and if not, the main loop will sleep a
-       few seconds and then retry this goal. */
+    /* Obtain locks on all output paths, if the paths are known a priori.
+
+       The locks are automatically released when we exit this function or Nix
+       crashes.  If we can't acquire the lock, then continue; hopefully some
+       other goal can start a build, and if not, the main loop will sleep a few
+       seconds and then retry this goal. */
     PathSet lockFiles;
-    for (auto & outPath : drv->outputPaths(worker.store))
-        lockFiles.insert(worker.store.Store::toRealPath(outPath));
+    /* FIXME: Should lock something like the drv itself so we don't build same
+       CA drv concurrently */
+    for (auto & i : drv->outputsAndOptPaths(worker.store))
+        if (i.second.second)
+            lockFiles.insert(worker.store.Store::toRealPath(*i.second.second));
 
     if (!outputLocks.lockPaths(lockFiles, "", false)) {
         if (!actLock)
@@ -1452,24 +1554,29 @@ void DerivationGoal::tryToBuild()
        omitted, but that would be less efficient.)  Note that since we
        now hold the locks on the output paths, no other process can
        build this derivation, so no further checks are necessary. */
-    validPaths = checkPathValidity(true, buildMode == bmRepair);
-    if (buildMode != bmCheck && validPaths.size() == drv->outputs.size()) {
+    checkPathValidity();
+    bool allValid = true;
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.wanted) continue;
+        if (!status.known || !status.known->isValid()) {
+            allValid = false;
+            break;
+        }
+    }
+    if (buildMode != bmCheck && allValid) {
         debug("skipping build of derivation '%s', someone beat us to it", worker.store.printStorePath(drvPath));
         outputLocks.setDeletion(true);
         done(BuildResult::AlreadyValid);
         return;
     }
 
-    missingPaths = drv->outputPaths(worker.store);
-    if (buildMode != bmCheck)
-        for (auto & i : validPaths) missingPaths.erase(i);
-
     /* If any of the outputs already exist but are not valid, delete
        them. */
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
-        if (worker.store.isValidPath(i.second.second)) continue;
-        debug("removing invalid path '%s'", worker.store.printStorePath(i.second.second));
-        deletePath(worker.store.Store::toRealPath(i.second.second));
+    for (auto & [_, status] : initialOutputs) {
+        if (!status.known || status.known->isValid()) continue;
+        auto storePath = status.known->path;
+        debug("removing invalid path '%s'", worker.store.printStorePath(status.known->path));
+        deletePath(worker.store.Store::toRealPath(storePath));
     }
 
     /* Don't do a remote build if the derivation has the attribute
@@ -1477,7 +1584,6 @@ void DerivationGoal::tryToBuild()
        supported for local builds. */
     bool buildLocally = buildMode != bmNormal || parsedDrv->willBuildLocally(worker.store);
 
-    /* Is the build hook willing to accept this job? */
     if (!buildLocally) {
         switch (tryBuildHook()) {
             case rpAccept:
@@ -1661,8 +1767,10 @@ void DerivationGoal::buildDone()
             /* Move paths out of the chroot for easier debugging of
                build failures. */
             if (useChroot && buildMode == bmNormal)
-                for (auto & i : missingPaths) {
-                    auto p = worker.store.printStorePath(i);
+                for (auto & [_, status] : initialOutputs) {
+                    if (!status.known) continue;
+                    if (buildMode != bmCheck && status.known->isValid()) continue;
+                    auto p = worker.store.printStorePath(status.known->path);
                     if (pathExists(chrootRootDir + p))
                         rename((chrootRootDir + p).c_str(), p.c_str());
                 }
@@ -1692,7 +1800,10 @@ void DerivationGoal::buildDone()
                 fmt("running post-build-hook '%s'", settings.postBuildHook),
                 Logger::Fields{worker.store.printStorePath(drvPath)});
             PushActivity pact(act.id);
-            auto outputPaths = drv->outputPaths(worker.store);
+            StorePathSet outputPaths;
+            for (auto i : drv->outputs) {
+                outputPaths.insert(finalOutputs.at(i.first));
+            }
             std::map<std::string, std::string> hookEnvironment = getEnv();
 
             hookEnvironment.emplace("DRV_PATH", worker.store.printStorePath(drvPath));
@@ -1868,7 +1979,15 @@ HookReply DerivationGoal::tryBuildHook()
 
     /* Tell the hooks the missing outputs that have to be copied back
        from the remote system. */
-    writeStorePaths(worker.store, hook->sink, missingPaths);
+    {
+        StorePathSet missingPaths;
+        for (auto & [_, status] : initialOutputs) {
+            if (!status.known) continue;
+            if (buildMode != bmCheck && status.known->isValid()) continue;
+            missingPaths.insert(status.known->path);
+        }
+        writeStorePaths(worker.store, hook->sink, missingPaths);
+    }
 
     hook->sink = FdSink();
     hook->toHook.writeSide = -1;
@@ -1919,8 +2038,15 @@ StorePathSet DerivationGoal::exportReferences(const StorePathSet & storePaths)
     for (auto & j : paths2) {
         if (j.isDerivation()) {
             Derivation drv = worker.store.derivationFromPath(j);
-            for (auto & k : drv.outputsAndPaths(worker.store))
-                worker.store.computeFSClosure(k.second.second, paths);
+            for (auto & k : drv.outputsAndOptPaths(worker.store)) {
+                if (!k.second.second)
+                    /* FIXME: I am confused why we are calling
+                       `computeFSClosure` on the output path, rather than
+                       derivation itself. That doesn't seem right to me, so I
+                       won't try to implemented this for CA derivations. */
+                    throw UnimplementedError("exportReferences on CA derivations is not yet implemented");
+                worker.store.computeFSClosure(*k.second.second, paths);
+            }
         }
     }
 
@@ -1951,7 +2077,7 @@ void linkOrCopy(const Path & from, const Path & to)
            file (e.g. 32000 of ext3), which is quite possible after a
            'nix-store --optimise'. FIXME: actually, why don't we just
            bind-mount in this case?
-           
+
            It can also fail with EPERM in BeegFS v7 and earlier versions
            which don't allow hard-links to other directories */
         if (errno != EMLINK && errno != EPERM)
@@ -2013,9 +2139,64 @@ void DerivationGoal::startBuilder()
 
     chownToBuilder(tmpDir);
 
-    /* Substitute output placeholders with the actual output paths. */
-    for (auto & output : drv->outputsAndPaths(worker.store))
-        inputRewrites[hashPlaceholder(output.first)] = worker.store.printStorePath(output.second.second);
+    for (auto & [outputName, status] : initialOutputs) {
+        /* Set scratch path we'll actually use during the build.
+
+           If we're not doing a chroot build, but we have some valid
+           output paths.  Since we can't just overwrite or delete
+           them, we have to do hash rewriting: i.e. in the
+           environment/arguments passed to the build, we replace the
+           hashes of the valid outputs with unique dummy strings;
+           after the build, we discard the redirected outputs
+           corresponding to the valid outputs, and rewrite the
+           contents of the new outputs to replace the dummy strings
+           with the actual hashes. */
+        auto scratchPath =
+            !status.known
+                ? makeFallbackPath(outputName)
+            : !needsHashRewrite()
+                /* Can always use original path in sandbox */
+                ? status.known->path
+            : !status.known->isPresent()
+                /* If path doesn't yet exist can just use it */
+                ? status.known->path
+            : buildMode != bmRepair && !status.known->isValid()
+                /* If we aren't repairing we'll delete a corrupted path, so we
+                   can use original path */
+                ? status.known->path
+            :   /* If we are repairing or the path is totally valid, we'll need
+                   to use a temporary path */
+                makeFallbackPath(status.known->path);
+        scratchOutputs.insert_or_assign(outputName, scratchPath);
+
+        /* A non-removed corrupted path needs to be stored here, too */
+        if (buildMode == bmRepair && !status.known->isValid())
+            redirectedBadOutputs.insert(status.known->path);
+
+        /* Substitute output placeholders with the scratch output paths.
+           We'll use during the build. */
+        inputRewrites[hashPlaceholder(outputName)] = worker.store.printStorePath(scratchPath);
+
+        /* Additional tasks if we know the final path a priori. */
+        if (!status.known) continue;
+        auto fixedFinalPath = status.known->path;
+
+        /* Additional tasks if the final and scratch are both known and
+           differ. */
+        if (fixedFinalPath == scratchPath) continue;
+
+        /* Ensure scratch path is ours to use. */
+        deletePath(worker.store.printStorePath(scratchPath));
+
+        /* Rewrite and unrewrite paths */
+        {
+            std::string h1 { fixedFinalPath.hashPart() };
+            std::string h2 { scratchPath.hashPart() };
+            inputRewrites[h1] = h2;
+        }
+
+        redirectedOutputs.insert_or_assign(std::move(fixedFinalPath), std::move(scratchPath));
+    }
 
     /* Construct the environment passed to the builder. */
     initEnv();
@@ -2199,8 +2380,15 @@ void DerivationGoal::startBuilder()
            rebuilding a path that is in settings.dirsInChroot
            (typically the dependencies of /bin/sh).  Throw them
            out. */
-        for (auto & i : drv->outputsAndPaths(worker.store))
-            dirsInChroot.erase(worker.store.printStorePath(i.second.second));
+        for (auto & i : drv->outputsAndOptPaths(worker.store)) {
+            /* If the name isn't known a priori (i.e. floating
+               content-addressed derivation), the temporary location we use
+               should be fresh.  Freshness means it is impossible that the path
+               is already in the sandbox, so we don't need to worry about
+               removing it.  */
+            if (i.second.second)
+                dirsInChroot.erase(worker.store.printStorePath(*i.second.second));
+        }
 
 #elif __APPLE__
         /* We don't really have any parent prep work to do (yet?)
@@ -2210,33 +2398,8 @@ void DerivationGoal::startBuilder()
 #endif
     }
 
-    if (needsHashRewrite()) {
-
-        if (pathExists(homeDir))
-            throw Error("home directory '%1%' exists; please remove it to assure purity of builds without sandboxing", homeDir);
-
-        /* We're not doing a chroot build, but we have some valid
-           output paths.  Since we can't just overwrite or delete
-           them, we have to do hash rewriting: i.e. in the
-           environment/arguments passed to the build, we replace the
-           hashes of the valid outputs with unique dummy strings;
-           after the build, we discard the redirected outputs
-           corresponding to the valid outputs, and rewrite the
-           contents of the new outputs to replace the dummy strings
-           with the actual hashes. */
-        if (validPaths.size() > 0)
-            for (auto & i : validPaths)
-                addHashRewrite(i);
-
-        /* If we're repairing, then we don't want to delete the
-           corrupt outputs in advance.  So rewrite them as well. */
-        if (buildMode == bmRepair)
-            for (auto & i : missingPaths)
-                if (worker.store.isValidPath(i) && pathExists(worker.store.printStorePath(i))) {
-                    addHashRewrite(i);
-                    redirectedBadOutputs.insert(i);
-                }
-    }
+    if (needsHashRewrite() && pathExists(homeDir))
+        throw Error("home directory '%1%' exists; please remove it to assure purity of builds without sandboxing", homeDir);
 
     if (useChroot && settings.preBuildHook != "" && dynamic_cast<Derivation *>(drv.get())) {
         printMsg(lvlChatty, format("executing pre-build hook '%1%'")
@@ -2612,8 +2775,11 @@ void DerivationGoal::writeStructuredAttrs()
 
     /* Add an "outputs" object containing the output paths. */
     nlohmann::json outputs;
-    for (auto & i : drv->outputsAndPaths(worker.store))
-        outputs[i.first] = rewriteStrings(worker.store.printStorePath(i.second.second), inputRewrites);
+    for (auto & i : drv->outputs) {
+        /* The placeholder must have a rewrite, so we use it to cover both the
+           cases where we know or don't know the output path ahead of time. */
+        outputs[i.first] = rewriteStrings(hashPlaceholder(i.first), inputRewrites);
+    }
     json["outputs"] = outputs;
 
     /* Handle exportReferencesGraph. */
@@ -2815,19 +2981,20 @@ struct RestrictedStore : public LocalFSStore
         StorePathSet newPaths;
 
         for (auto & path : paths) {
-            if (path.path.isDerivation()) {
-                if (!goal.isAllowed(path.path))
-                    throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
-                auto drv = derivationFromPath(path.path);
-                for (auto & output : drv.outputsAndPaths(*this))
-                    if (wantOutput(output.first, path.outputs))
-                        newPaths.insert(output.second.second);
-            } else if (!goal.isAllowed(path.path))
+            if (!goal.isAllowed(path.path))
                 throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
         }
 
         next->buildPaths(paths, buildMode);
 
+        for (auto & path : paths) {
+            if (!path.path.isDerivation()) continue;
+            auto outputs = next->queryDerivationOutputMap(path.path);
+            for (auto & output : outputs)
+                if (wantOutput(output.first, path.outputs))
+                    newPaths.insert(output.second);
+        }
+
         StorePathSet closure;
         next->computeFSClosure(newPaths, closure);
         for (auto & path : closure)
@@ -3444,14 +3611,10 @@ void DerivationGoal::runChild()
                 if (derivationIsImpure(derivationType))
                     sandboxProfile += "(import \"sandbox-network.sb\")\n";
 
-                /* Our rwx outputs */
+                /* Add the output paths we'll use at build-time to the chroot */
                 sandboxProfile += "(allow file-read* file-write* process-exec\n";
-                for (auto & i : missingPaths)
-                    sandboxProfile += fmt("\t(subpath \"%s\")\n", worker.store.printStorePath(i));
-
-                /* Also add redirected outputs to the chroot */
-                for (auto & i : redirectedOutputs)
-                    sandboxProfile += fmt("\t(subpath \"%s\")\n", worker.store.printStorePath(i.second));
+                for (auto & [_, path] : scratchOutputs)
+                    sandboxProfile += fmt("\t(subpath \"%s\")\n", worker.store.printStorePath(path));
 
                 sandboxProfile += ")\n";
 
@@ -3574,23 +3737,6 @@ void DerivationGoal::runChild()
 }
 
 
-/* Parse a list of reference specifiers.  Each element must either be
-   a store path, or the symbolic name of the output of the derivation
-   (such as `out'). */
-StorePathSet parseReferenceSpecifiers(Store & store, const BasicDerivation & drv, const Strings & paths)
-{
-    StorePathSet result;
-    for (auto & i : paths) {
-        if (store.isStorePath(i))
-            result.insert(store.parseStorePath(i));
-        else if (drv.outputs.count(i))
-            result.insert(drv.outputs.find(i)->second.path(store, drv.name));
-        else throw BuildError("derivation contains an illegal reference specifier '%s'", i);
-    }
-    return result;
-}
-
-
 static void moveCheckToStore(const Path & src, const Path & dst)
 {
     /* For the rename of directory to succeed, we must be running as root or
@@ -3618,11 +3764,17 @@ void DerivationGoal::registerOutputs()
 {
     /* When using a build hook, the build hook can register the output
        as valid (by doing `nix-store --import').  If so we don't have
-       to do anything here. */
+       to do anything here.
+
+       We can only early return when the outputs are known a priori. For
+       floating content-addressed derivations this isn't the case.
+     */
     if (hook) {
         bool allValid = true;
-        for (auto & i : drv->outputsAndPaths(worker.store))
-            if (!worker.store.isValidPath(i.second.second)) allValid = false;
+        for (auto & i : drv->outputsAndOptPaths(worker.store)) {
+            if (!i.second.second || !worker.store.isValidPath(*i.second.second))
+                allValid = false;
+        }
         if (allValid) return;
     }
 
@@ -3643,47 +3795,51 @@ void DerivationGoal::registerOutputs()
        Nix calls. */
     StorePathSet referenceablePaths;
     for (auto & p : inputPaths) referenceablePaths.insert(p);
-    for (auto & i : drv->outputsAndPaths(worker.store)) referenceablePaths.insert(i.second.second);
+    for (auto & i : scratchOutputs) referenceablePaths.insert(i.second);
     for (auto & p : addedPaths) referenceablePaths.insert(p);
 
-    /* Check whether the output paths were created, and grep each
-       output path to determine what other paths it references.  Also make all
-       output paths read-only. */
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
-        auto path = worker.store.printStorePath(i.second.second);
-        if (!missingPaths.count(i.second.second)) continue;
-
-        Path actualPath = path;
-        if (needsHashRewrite()) {
-            auto r = redirectedOutputs.find(i.second.second);
-            if (r != redirectedOutputs.end()) {
-                auto redirected = worker.store.Store::toRealPath(r->second);
-                if (buildMode == bmRepair
-                    && redirectedBadOutputs.count(i.second.second)
-                    && pathExists(redirected))
-                    replaceValidPath(path, redirected);
-                if (buildMode == bmCheck)
-                    actualPath = redirected;
-            }
-        } else if (useChroot) {
-            actualPath = chrootRootDir + path;
-            if (pathExists(actualPath)) {
-                /* Move output paths from the chroot to the Nix store. */
-                if (buildMode == bmRepair)
-                    replaceValidPath(path, actualPath);
-                else
-                    if (buildMode != bmCheck && rename(actualPath.c_str(), worker.store.toRealPath(path).c_str()) == -1)
-                        throw SysError("moving build output '%1%' from the sandbox to the Nix store", path);
-            }
-            if (buildMode != bmCheck) actualPath = worker.store.toRealPath(path);
+    /* FIXME `needsHashRewrite` should probably be removed and we get to the
+       real reason why we aren't using the chroot dir */
+    auto toRealPathChroot = [&](const Path & p) -> Path {
+        return useChroot && !needsHashRewrite()
+            ? chrootRootDir + p
+            : worker.store.toRealPath(p);
+    };
+
+    /* Check whether the output paths were created, and make all
+       output paths read-only.  Then get the references of each output (that we
+       might need to register), so we can topologically sort them. For the ones
+       that are most definitely already installed, we just store their final
+       name so we can also use it in rewrites. */
+    StringSet outputsToSort;
+    struct AlreadyRegistered { StorePath path; };
+    struct PerhapsNeedToRegister { StorePathSet refs; };
+    std::map<std::string, std::variant<AlreadyRegistered, PerhapsNeedToRegister>> outputReferencesIfUnregistered;
+    std::map<std::string, struct stat> outputStats;
+    for (auto & [outputName, _] : drv->outputs) {
+        auto actualPath = toRealPathChroot(worker.store.printStorePath(scratchOutputs.at(outputName)));
+
+        outputsToSort.insert(outputName);
+
+        /* Updated wanted info to remove the outputs we definitely don't need to register */
+        auto & initialInfo = initialOutputs.at(outputName);
+
+        /* Don't register if already valid, and not checking */
+        initialInfo.wanted = buildMode == bmCheck
+            || !(initialInfo.known && initialInfo.known->isValid());
+        if (!initialInfo.wanted) {
+            outputReferencesIfUnregistered.insert_or_assign(
+                outputName,
+                AlreadyRegistered { .path = initialInfo.known->path });
+            continue;
         }
 
         struct stat st;
         if (lstat(actualPath.c_str(), &st) == -1) {
             if (errno == ENOENT)
                 throw BuildError(
-                    "builder for '%s' failed to produce output path '%s'",
-                    worker.store.printStorePath(drvPath), path);
+                    "builder for '%s' failed to produce output path for output '%s' at '%s'",
+                    worker.store.printStorePath(drvPath), outputName, actualPath);
             throw SysError("getting attributes of path '%s'", actualPath);
         }
 
@@ -3694,116 +3850,281 @@ void DerivationGoal::registerOutputs()
            user. */
         if ((!S_ISLNK(st.st_mode) && (st.st_mode & (S_IWGRP | S_IWOTH))) ||
             (buildUser && st.st_uid != buildUser->getUID()))
-            throw BuildError("suspicious ownership or permission on '%1%'; rejecting this build output", path);
+            throw BuildError(
+                    "suspicious ownership or permission on '%s' for output '%s'; rejecting this build output",
+                    actualPath, outputName);
 #endif
 
-        /* Apply hash rewriting if necessary. */
-        bool rewritten = false;
-        if (!outputRewrites.empty()) {
-            logWarning({
-                .name = "Rewriting hashes",
-                .hint = hintfmt("rewriting hashes in '%1%'; cross fingers", path)
-            });
+        /* Canonicalise first.  This ensures that the path we're
+           rewriting doesn't contain a hard link to /etc/shadow or
+           something like that. */
+        canonicalisePathMetaData(actualPath, buildUser ? buildUser->getUID() : -1, inodesSeen);
 
-            /* Canonicalise first.  This ensures that the path we're
-               rewriting doesn't contain a hard link to /etc/shadow or
-               something like that. */
-            canonicalisePathMetaData(actualPath, buildUser ? buildUser->getUID() : -1, inodesSeen);
+        debug("scanning for references for output %1 in temp location '%1%'", outputName, actualPath);
 
-            /* FIXME: this is in-memory. */
-            StringSink sink;
-            dumpPath(actualPath, sink);
-            deletePath(actualPath);
-            sink.s = make_ref<std::string>(rewriteStrings(*sink.s, outputRewrites));
-            StringSource source(*sink.s);
-            restorePath(actualPath, source);
+        /* Pass blank Sink as we are not ready to hash data at this stage. */
+        NullSink blank;
+        auto references = worker.store.parseStorePathSet(
+            scanForReferences(blank, actualPath, worker.store.printStorePathSet(referenceablePaths)));
 
-            rewritten = true;
-        }
-
-        /* Check that fixed-output derivations produced the right
-           outputs (i.e., the content hash should match the specified
-           hash). */
-        std::optional<ContentAddress> ca;
+        outputReferencesIfUnregistered.insert_or_assign(
+            outputName,
+            PerhapsNeedToRegister { .refs = references });
+        outputStats.insert_or_assign(outputName, std::move(st));
+    }
 
-        if (! std::holds_alternative<DerivationOutputInputAddressed>(i.second.first.output)) {
-            DerivationOutputCAFloating outputHash;
-            std::visit(overloaded {
-                [&](DerivationOutputInputAddressed doi) {
-                    assert(false); // Enclosing `if` handles this case in other branch
+    auto sortedOutputNames = topoSort(outputsToSort,
+        {[&](const std::string & name) {
+            return std::visit(overloaded {
+                /* Since we'll use the already installed versions of these, we
+                   can treat them as leaves and ignore any references they
+                   have. */
+                [&](AlreadyRegistered _) { return StringSet {}; },
+                [&](PerhapsNeedToRegister refs) {
+                    StringSet referencedOutputs;
+                    /* FIXME build inverted map up front so no quadratic waste here */
+                    for (auto & r : refs.refs)
+                        for (auto & [o, p] : scratchOutputs)
+                            if (r == p)
+                                referencedOutputs.insert(o);
+                    return referencedOutputs;
                 },
-                [&](DerivationOutputCAFixed dof) {
-                    outputHash = DerivationOutputCAFloating {
-                        .method = dof.hash.method,
-                        .hashType = dof.hash.hash.type,
-                    };
-                },
-                [&](DerivationOutputCAFloating dof) {
-                    outputHash = dof;
-                },
-            }, i.second.first.output);
+            }, outputReferencesIfUnregistered.at(name));
+        }},
+        {[&](const std::string & path, const std::string & parent) {
+            // TODO with more -vvvv also show the temporary paths for manual inspection.
+            return BuildError(
+                "cycle detected in build of '%s' in the references of output '%s' from output '%s'",
+                worker.store.printStorePath(drvPath), path, parent);
+        }});
+
+    std::reverse(sortedOutputNames.begin(), sortedOutputNames.end());
+
+    for (auto & outputName : sortedOutputNames) {
+        auto output = drv->outputs.at(outputName);
+        auto & scratchPath = scratchOutputs.at(outputName);
+        auto actualPath = toRealPathChroot(worker.store.printStorePath(scratchPath));
+
+        auto finish = [&](StorePath finalStorePath) {
+            /* Store the final path */
+            finalOutputs.insert_or_assign(outputName, finalStorePath);
+            /* The rewrite rule will be used in downstream outputs that refer to
+               use. This is why the topological sort is essential to do first
+               before this for loop. */
+            if (scratchPath != finalStorePath)
+                outputRewrites[std::string { scratchPath.hashPart() }] = std::string { finalStorePath.hashPart() };
+        };
+
+        bool rewritten = false;
+        std::optional<StorePathSet> referencesOpt = std::visit(overloaded {
+            [&](AlreadyRegistered skippedFinalPath) -> std::optional<StorePathSet> {
+                finish(skippedFinalPath.path);
+                return std::nullopt;
+            },
+            [&](PerhapsNeedToRegister r) -> std::optional<StorePathSet> {
+                return r.refs;
+            },
+        }, outputReferencesIfUnregistered.at(outputName));
+
+        if (!referencesOpt)
+            continue;
+        auto references = *referencesOpt;
+
+        auto rewriteOutput = [&]() {
+            /* Apply hash rewriting if necessary. */
+            if (!outputRewrites.empty()) {
+                logWarning({
+                    .name = "Rewriting hashes",
+                    .hint = hintfmt("rewriting hashes in '%1%'; cross fingers", actualPath),
+                });
+
+                /* FIXME: this is in-memory. */
+                StringSink sink;
+                dumpPath(actualPath, sink);
+                deletePath(actualPath);
+                sink.s = make_ref<std::string>(rewriteStrings(*sink.s, outputRewrites));
+                StringSource source(*sink.s);
+                restorePath(actualPath, source);
+
+                rewritten = true;
+            }
+        };
+
+        auto rewriteRefs = [&]() -> std::pair<bool, StorePathSet> {
+            /* In the CA case, we need the rewritten refs to calculate the
+               final path, therefore we look for a *non-rewritten
+               self-reference, and use a bool rather try to solve the
+               computationally intractable fixed point. */
+            std::pair<bool, StorePathSet> res {
+                false,
+                {},
+            };
+            for (auto & r : references) {
+                auto name = r.name();
+                auto origHash = std::string { r.hashPart() };
+                if (r == scratchPath)
+                    res.first = true;
+                else if (outputRewrites.count(origHash) == 0)
+                    res.second.insert(r);
+                else {
+                    std::string newRef = outputRewrites.at(origHash);
+                    newRef += '-';
+                    newRef += name;
+                    res.second.insert(StorePath { newRef });
+                }
+            }
+            return res;
+        };
 
+        auto newInfoFromCA = [&](const DerivationOutputCAFloating outputHash) -> ValidPathInfo {
+            auto & st = outputStats.at(outputName);
             if (outputHash.method == FileIngestionMethod::Flat) {
                 /* The output path should be a regular file without execute permission. */
                 if (!S_ISREG(st.st_mode) || (st.st_mode & S_IXUSR) != 0)
                     throw BuildError(
                         "output path '%1%' should be a non-executable regular file "
                         "since recursive hashing is not enabled (outputHashMode=flat)",
-                        path);
+                        actualPath);
             }
-
-            /* Check the hash. In hash mode, move the path produced by
-               the derivation to its content-addressed location. */
-            Hash h2 = outputHash.method == FileIngestionMethod::Recursive
-                ? hashPath(outputHash.hashType, actualPath).first
-                : hashFile(outputHash.hashType, actualPath);
-
-            auto dest = worker.store.makeFixedOutputPath(outputHash.method, h2, i.second.second.name());
-
-            // true if either floating CA, or incorrect fixed hash.
-            bool needsMove = true;
-
-            if (auto p = std::get_if<DerivationOutputCAFixed>(& i.second.first.output)) {
-              Hash & h = p->hash.hash;
-              if (h != h2) {
-
-                /* Throw an error after registering the path as
-                   valid. */
-                worker.hashMismatch = true;
-                delayedException = std::make_exception_ptr(
-                    BuildError("hash mismatch in fixed-output derivation '%s':\n  wanted: %s\n  got:    %s",
-                        worker.store.printStorePath(dest),
-                        h.to_string(SRI, true),
-                        h2.to_string(SRI, true)));
-              } else {
-                  // matched the fixed hash, so no move needed.
-                  needsMove = false;
-              }
+            rewriteOutput();
+            /* FIXME optimize and deduplicate with addToStore */
+            std::string oldHashPart { scratchPath.hashPart() };
+            HashModuloSink caSink { outputHash.hashType, oldHashPart };
+            switch (outputHash.method) {
+            case FileIngestionMethod::Recursive:
+                dumpPath(actualPath, caSink);
+                break;
+            case FileIngestionMethod::Flat:
+                readFile(actualPath, caSink);
+                break;
             }
+            auto got = caSink.finish().first;
+            auto refs = rewriteRefs();
+            HashModuloSink narSink { htSHA256, oldHashPart };
+            dumpPath(actualPath, narSink);
+            auto narHashAndSize = narSink.finish();
+            ValidPathInfo newInfo0 {
+                worker.store.makeFixedOutputPath(
+                    outputHash.method,
+                    got,
+                    outputPathName(drv->name, outputName),
+                    refs.second,
+                    refs.first),
+                narHashAndSize.first,
+            };
+            newInfo0.narSize = narHashAndSize.second;
+            newInfo0.ca = FixedOutputHash {
+                .method = outputHash.method,
+                .hash = got,
+            };
+            newInfo0.references = refs.second;
+            if (refs.first)
+                newInfo0.references.insert(newInfo0.path);
 
-            if (needsMove) {
-                Path actualDest = worker.store.Store::toRealPath(dest);
+            assert(newInfo0.ca);
+            return newInfo0;
+        };
 
-                if (worker.store.isValidPath(dest))
-                    std::rethrow_exception(delayedException);
+        ValidPathInfo newInfo = std::visit(overloaded {
+            [&](DerivationOutputInputAddressed output) {
+                /* input-addressed case */
+                auto requiredFinalPath = output.path;
+                /* Preemtively add rewrite rule for final hash, as that is
+                   what the NAR hash will use rather than normalized-self references */
+                if (scratchPath != requiredFinalPath)
+                    outputRewrites.insert_or_assign(
+                        std::string { scratchPath.hashPart() },
+                        std::string { requiredFinalPath.hashPart() });
+                rewriteOutput();
+                auto narHashAndSize = hashPath(htSHA256, actualPath);
+                ValidPathInfo newInfo0 { requiredFinalPath, narHashAndSize.first };
+                newInfo0.narSize = narHashAndSize.second;
+                auto refs = rewriteRefs();
+                newInfo0.references = refs.second;
+                if (refs.first)
+                    newInfo0.references.insert(newInfo0.path);
+                return newInfo0;
+            },
+            [&](DerivationOutputCAFixed dof) {
+                auto newInfo0 = newInfoFromCA(DerivationOutputCAFloating {
+                    .method = dof.hash.method,
+                    .hashType = dof.hash.hash.type,
+                });
 
-                if (actualPath != actualDest) {
-                    PathLocks outputLocks({actualDest});
-                    deletePath(actualDest);
-                    if (rename(actualPath.c_str(), actualDest.c_str()) == -1)
-                        throw SysError("moving '%s' to '%s'", actualPath, worker.store.printStorePath(dest));
+                /* Check wanted hash */
+                Hash & wanted = dof.hash.hash;
+                assert(newInfo0.ca);
+                auto got = getContentAddressHash(*newInfo0.ca);
+                if (wanted != got) {
+                    /* Throw an error after registering the path as
+                       valid. */
+                    worker.hashMismatch = true;
+                    delayedException = std::make_exception_ptr(
+                        BuildError("hash mismatch in fixed-output derivation '%s':\n  wanted: %s\n  got:    %s",
+                            worker.store.printStorePath(drvPath),
+                            wanted.to_string(SRI, true),
+                            got.to_string(SRI, true)));
                 }
+                return newInfo0;
+            },
+            [&](DerivationOutputCAFloating dof) {
+                return newInfoFromCA(dof);
+            },
+        }, output.output);
+
+        /* Calculate where we'll move the output files. In the checking case we
+           will leave leave them where they are, for now, rather than move to
+           their usual "final destination" */
+        auto finalDestPath = worker.store.printStorePath(newInfo.path);
+
+        /* Lock final output path, if not already locked. This happens with
+           floating CA derivations and hash-mismatching fixed-output
+           derivations. */
+        PathLocks dynamicOutputLock;
+        auto optFixedPath = output.path(worker.store, drv->name, outputName);
+        if (!optFixedPath ||
+            worker.store.printStorePath(*optFixedPath) != finalDestPath)
+        {
+            assert(newInfo.ca);
+            dynamicOutputLock.lockPaths({worker.store.toRealPath(finalDestPath)});
+        }
 
-                path = worker.store.printStorePath(dest);
-                actualPath = actualDest;
+        /* Move files, if needed */
+        if (worker.store.toRealPath(finalDestPath) != actualPath) {
+            if (buildMode == bmRepair) {
+                /* Path already exists, need to replace it */
+                replaceValidPath(worker.store.toRealPath(finalDestPath), actualPath);
+                actualPath = worker.store.toRealPath(finalDestPath);
+            } else if (buildMode == bmCheck) {
+                /* Path already exists, and we want to compare, so we leave out
+                   new path in place. */
+            } else if (worker.store.isValidPath(newInfo.path)) {
+                /* Path already exists because CA path produced by something
+                   else. No moving needed. */
+                assert(newInfo.ca);
+            } else {
+                /* Temporarily add write perm so we can move, will be fixed
+                   later. */
+                {
+                    struct stat st;
+                    auto & mode = st.st_mode;
+                    if (lstat(actualPath.c_str(), &st))
+                        throw SysError("getting attributes of path '%1%'", actualPath);
+                    mode |= 0200;
+                    /* Try to change the perms, but only if the file isn't a
+                       symlink as symlinks permissions are mostly ignored and
+                       calling `chmod` on it will just forward the call to the
+                       target of the link. */
+                    if (!S_ISLNK(st.st_mode))
+                        if (chmod(actualPath.c_str(), mode) == -1)
+                            throw SysError("changing mode of '%1%' to %2$o", actualPath, mode);
+                }
+                if (rename(
+                        actualPath.c_str(),
+                        worker.store.toRealPath(finalDestPath).c_str()) == -1)
+                    throw SysError("moving build output '%1%' from it's temporary location to the Nix store", finalDestPath);
+                actualPath = worker.store.toRealPath(finalDestPath);
             }
-            else
-                assert(worker.store.parseStorePath(path) == dest);
-
-            ca = FixedOutputHash {
-                .method = outputHash.method,
-                .hash = h2,
-            };
         }
 
         /* Get rid of all weird permissions.  This also checks that
@@ -3811,45 +4132,33 @@ void DerivationGoal::registerOutputs()
         canonicalisePathMetaData(actualPath,
             buildUser && !rewritten ? buildUser->getUID() : -1, inodesSeen);
 
-        /* For this output path, find the references to other paths
-           contained in it.  Compute the SHA-256 NAR hash at the same
-           time.  The hash is stored in the database so that we can
-           verify later on whether nobody has messed with the store. */
-        debug("scanning for references inside '%1%'", path);
-        // HashResult hash;
-        auto pathSetAndHash = scanForReferences(actualPath, worker.store.printStorePathSet(referenceablePaths));
-        auto references = worker.store.parseStorePathSet(pathSetAndHash.first);
-        HashResult hash = pathSetAndHash.second;
-
         if (buildMode == bmCheck) {
-            if (!worker.store.isValidPath(worker.store.parseStorePath(path))) continue;
-            ValidPathInfo info(*worker.store.queryPathInfo(worker.store.parseStorePath(path)));
-            if (hash.first != info.narHash) {
+            if (!worker.store.isValidPath(newInfo.path)) continue;
+            ValidPathInfo oldInfo(*worker.store.queryPathInfo(newInfo.path));
+            if (newInfo.narHash != oldInfo.narHash) {
                 worker.checkMismatch = true;
                 if (settings.runDiffHook || settings.keepFailed) {
-                    Path dst = worker.store.toRealPath(path + checkSuffix);
+                    Path dst = worker.store.toRealPath(finalDestPath + checkSuffix);
                     deletePath(dst);
                     moveCheckToStore(actualPath, dst);
 
                     handleDiffHook(
                         buildUser ? buildUser->getUID() : getuid(),
                         buildUser ? buildUser->getGID() : getgid(),
-                        path, dst, worker.store.printStorePath(drvPath), tmpDir);
+                        finalDestPath, dst, worker.store.printStorePath(drvPath), tmpDir);
 
                     throw NotDeterministic("derivation '%s' may not be deterministic: output '%s' differs from '%s'",
-                        worker.store.printStorePath(drvPath), worker.store.toRealPath(path), dst);
+                        worker.store.printStorePath(drvPath), worker.store.toRealPath(finalDestPath), dst);
                 } else
                     throw NotDeterministic("derivation '%s' may not be deterministic: output '%s' differs",
-                        worker.store.printStorePath(drvPath), worker.store.toRealPath(path));
+                        worker.store.printStorePath(drvPath), worker.store.toRealPath(finalDestPath));
             }
 
             /* Since we verified the build, it's now ultimately trusted. */
-            if (!info.ultimate) {
-                info.ultimate = true;
-                worker.store.signPathInfo(info);
-                ValidPathInfos infos;
-                infos.push_back(std::move(info));
-                worker.store.registerValidPaths(infos);
+            if (!oldInfo.ultimate) {
+                oldInfo.ultimate = true;
+                worker.store.signPathInfo(oldInfo);
+                worker.store.registerValidPaths({ std::move(oldInfo) });
             }
 
             continue;
@@ -3866,26 +4175,22 @@ void DerivationGoal::registerOutputs()
 
         if (curRound == nrRounds) {
             worker.store.optimisePath(actualPath); // FIXME: combine with scanForReferences()
-            worker.markContentsGood(worker.store.parseStorePath(path));
+            worker.markContentsGood(newInfo.path);
         }
 
-        ValidPathInfo info {
-            worker.store.parseStorePath(path),
-            hash.first,
-        };
-        info.narSize = hash.second;
-        info.references = std::move(references);
-        info.deriver = drvPath;
-        info.ultimate = true;
-        info.ca = ca;
-        worker.store.signPathInfo(info);
-
-        if (!info.references.empty()) {
-            // FIXME don't we have an experimental feature for fixed output with references?
-            info.ca = {};
-        }
+        newInfo.deriver = drvPath;
+        newInfo.ultimate = true;
+        worker.store.signPathInfo(newInfo);
+
+        finish(newInfo.path);
 
-        infos.emplace(i.first, std::move(info));
+        /* If it's a CA path, register it right away. This is necessary if it
+           isn't statically known so that we can safely unlock the path before
+           the next iteration */
+        if (newInfo.ca)
+            worker.store.registerValidPaths({newInfo});
+
+        infos.emplace(outputName, std::move(newInfo));
     }
 
     if (buildMode == bmCheck) return;
@@ -3928,8 +4233,8 @@ void DerivationGoal::registerOutputs()
 
     /* If this is the first round of several, then move the output out of the way. */
     if (nrRounds > 1 && curRound == 1 && curRound < nrRounds && keepPreviousRound) {
-        for (auto & i : drv->outputsAndPaths(worker.store)) {
-            auto path = worker.store.printStorePath(i.second.second);
+        for (auto & [_, outputStorePath] : finalOutputs) {
+            auto path = worker.store.printStorePath(outputStorePath);
             Path prev = path + checkSuffix;
             deletePath(prev);
             Path dst = path + checkSuffix;
@@ -3946,8 +4251,8 @@ void DerivationGoal::registerOutputs()
     /* Remove the .check directories if we're done. FIXME: keep them
        if the result was not determistic? */
     if (curRound == nrRounds) {
-        for (auto & i : drv->outputsAndPaths(worker.store)) {
-            Path prev = worker.store.printStorePath(i.second.second) + checkSuffix;
+        for (auto & [_, outputStorePath] : finalOutputs) {
+            Path prev = worker.store.printStorePath(outputStorePath) + checkSuffix;
             deletePath(prev);
         }
     }
@@ -3955,16 +4260,28 @@ void DerivationGoal::registerOutputs()
     /* Register each output path as valid, and register the sets of
        paths referenced by each of them.  If there are cycles in the
        outputs, this will fail. */
-    {
-        ValidPathInfos infos2;
-        for (auto & i : infos) infos2.push_back(i.second);
-        worker.store.registerValidPaths(infos2);
+    ValidPathInfos infos2;
+    for (auto & [outputName, newInfo] : infos) {
+        infos2.push_back(newInfo);
     }
+    worker.store.registerValidPaths(infos2);
 
     /* In case of a fixed-output derivation hash mismatch, throw an
        exception now that we have registered the output as valid. */
     if (delayedException)
         std::rethrow_exception(delayedException);
+
+    /* If we made it this far, we are sure the output matches the derivation
+       (since the delayedException would be a fixed output CA mismatch). That
+       means it's safe to link the derivation to the output hash. We must do
+       that for floating CA derivations, which otherwise couldn't be cached,
+       but it's fine to do in all cases. */
+    for (auto & [outputName, newInfo] : infos) {
+        /* FIXME: we will want to track this mapping in the DB whether or
+           not we have a drv file. */
+        if (useDerivation)
+            worker.store.linkDeriverToPath(drvPath, outputName, newInfo.path);
+    }
 }
 
 
@@ -4033,7 +4350,17 @@ void DerivationGoal::checkOutputs(const std::map<Path, ValidPathInfo> & outputs)
             {
                 if (!value) return;
 
-                auto spec = parseReferenceSpecifiers(worker.store, *drv, *value);
+                /* Parse a list of reference specifiers.  Each element must
+                   either be a store path, or the symbolic name of the output
+                   of the derivation (such as `out'). */
+                StorePathSet spec;
+                for (auto & i : *value) {
+                    if (worker.store.isStorePath(i))
+                        spec.insert(worker.store.parseStorePath(i));
+                    else if (finalOutputs.count(i))
+                        spec.insert(finalOutputs.at(i));
+                    else throw BuildError("derivation contains an illegal reference specifier '%s'", i);
+                }
 
                 auto used = recursive
                     ? getClosure(info.path).first
@@ -4242,31 +4569,67 @@ void DerivationGoal::flushLine()
 }
 
 
-StorePathSet DerivationGoal::checkPathValidity(bool returnValid, bool checkHash)
+std::map<std::string, std::optional<StorePath>> DerivationGoal::queryPartialDerivationOutputMap()
 {
-    StorePathSet result;
-    for (auto & i : drv->outputsAndPaths(worker.store)) {
-        if (!wantOutput(i.first, wantedOutputs)) continue;
-        bool good =
-            worker.store.isValidPath(i.second.second) &&
-            (!checkHash || worker.pathContentsGood(i.second.second));
-        if (good == returnValid) result.insert(i.second.second);
+    if (drv->type() != DerivationType::CAFloating) {
+        std::map<std::string, std::optional<StorePath>> res;
+        for (auto & [name, output] : drv->outputs)
+            res.insert_or_assign(name, output.path(worker.store, drv->name, name));
+        return res;
+    } else {
+        return worker.store.queryPartialDerivationOutputMap(drvPath);
     }
-    return result;
+}
+
+OutputPathMap DerivationGoal::queryDerivationOutputMap()
+{
+    if (drv->type() != DerivationType::CAFloating) {
+        OutputPathMap res;
+        for (auto & [name, output] : drv->outputsAndOptPaths(worker.store))
+            res.insert_or_assign(name, *output.second);
+        return res;
+    } else {
+        return worker.store.queryDerivationOutputMap(drvPath);
+    }
+}
+
+
+void DerivationGoal::checkPathValidity()
+{
+    bool checkHash = buildMode == bmRepair;
+    for (auto & i : queryPartialDerivationOutputMap()) {
+        InitialOutput info {
+            .wanted = wantOutput(i.first, wantedOutputs),
+        };
+        if (i.second) {
+            auto outputPath = *i.second;
+            info.known = {
+                .path = outputPath,
+                .status = !worker.store.isValidPath(outputPath)
+                    ? PathStatus::Absent
+                    : !checkHash || worker.pathContentsGood(outputPath)
+                    ? PathStatus::Valid
+                    : PathStatus::Corrupt,
+            };
+        }
+        initialOutputs.insert_or_assign(i.first, info);
+    }
+}
+
+
+StorePath DerivationGoal::makeFallbackPath(std::string_view outputName)
+{
+    return worker.store.makeStorePath(
+        "rewrite:" + std::string(drvPath.to_string()) + ":name:" + std::string(outputName),
+        Hash(htSHA256), outputPathName(drv->name, outputName));
 }
 
 
-void DerivationGoal::addHashRewrite(const StorePath & path)
+StorePath DerivationGoal::makeFallbackPath(const StorePath & path)
 {
-    auto h1 = std::string(((std::string_view) path.to_string()).substr(0, 32));
-    auto p = worker.store.makeStorePath(
+    return worker.store.makeStorePath(
         "rewrite:" + std::string(drvPath.to_string()) + ":" + std::string(path.to_string()),
         Hash(htSHA256), path.name());
-    auto h2 = std::string(((std::string_view) p.to_string()).substr(0, 32));
-    deletePath(worker.store.printStorePath(p));
-    inputRewrites[h1] = h2;
-    outputRewrites[h2] = h1;
-    redirectedOutputs.insert_or_assign(path, std::move(p));
 }
 
 
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index d263cf0c5..9d8ce5e36 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -7,7 +7,7 @@
 
 namespace nix {
 
-std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::string_view drvName) const
+std::optional<StorePath> DerivationOutput::path(const Store & store, std::string_view drvName, std::string_view outputName) const
 {
     return std::visit(overloaded {
         [](DerivationOutputInputAddressed doi) -> std::optional<StorePath> {
@@ -15,7 +15,7 @@ std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::str
         },
         [&](DerivationOutputCAFixed dof) -> std::optional<StorePath> {
             return {
-                store.makeFixedOutputPath(dof.hash.method, dof.hash.hash, drvName)
+                dof.path(store, drvName, outputName)
             };
         },
         [](DerivationOutputCAFloating dof) -> std::optional<StorePath> {
@@ -25,6 +25,13 @@ std::optional<StorePath> DerivationOutput::pathOpt(const Store & store, std::str
 }
 
 
+StorePath DerivationOutputCAFixed::path(const Store & store, std::string_view drvName, std::string_view outputName) const {
+    return store.makeFixedOutputPath(
+        hash.method, hash.hash,
+        outputPathName(drvName, outputName));
+}
+
+
 bool derivationIsCA(DerivationType dt) {
     switch (dt) {
     case DerivationType::InputAddressed: return false;
@@ -106,12 +113,15 @@ static string parseString(std::istream & str)
     return res;
 }
 
+static void validatePath(std::string_view s) {
+    if (s.size() == 0 || s[0] != '/')
+        throw FormatError("bad path '%1%' in derivation", s);
+}
 
 static Path parsePath(std::istream & str)
 {
-    string s = parseString(str);
-    if (s.size() == 0 || s[0] != '/')
-        throw FormatError("bad path '%1%' in derivation", s);
+    auto s = parseString(str);
+    validatePath(s);
     return s;
 }
 
@@ -140,7 +150,7 @@ static StringSet parseStrings(std::istream & str, bool arePaths)
 
 
 static DerivationOutput parseDerivationOutput(const Store & store,
-    StorePath path, std::string_view hashAlgo, std::string_view hash)
+    std::string_view pathS, std::string_view hashAlgo, std::string_view hash)
 {
     if (hashAlgo != "") {
         auto method = FileIngestionMethod::Flat;
@@ -148,40 +158,45 @@ static DerivationOutput parseDerivationOutput(const Store & store,
             method = FileIngestionMethod::Recursive;
             hashAlgo = hashAlgo.substr(2);
         }
-        const HashType hashType = parseHashType(hashAlgo);
-
-        return hash != ""
-            ? DerivationOutput {
-                  .output = DerivationOutputCAFixed {
-                      .hash = FixedOutputHash {
-                          .method = std::move(method),
-                          .hash = Hash::parseNonSRIUnprefixed(hash, hashType),
-                      },
-                  }
-               }
-            : (settings.requireExperimentalFeature("ca-derivations"),
-              DerivationOutput {
-                  .output =  DerivationOutputCAFloating {
-                      .method = std::move(method),
-                      .hashType = std::move(hashType),
-                  },
-              });
-    } else
+        const auto hashType = parseHashType(hashAlgo);
+        if (hash != "") {
+            validatePath(pathS);
+            return DerivationOutput {
+                .output = DerivationOutputCAFixed {
+                    .hash = FixedOutputHash {
+                        .method = std::move(method),
+                        .hash = Hash::parseNonSRIUnprefixed(hash, hashType),
+                    },
+                },
+            };
+        } else {
+            settings.requireExperimentalFeature("ca-derivations");
+            assert(pathS == "");
+            return DerivationOutput {
+                .output = DerivationOutputCAFloating {
+                    .method = std::move(method),
+                    .hashType = std::move(hashType),
+                },
+            };
+        }
+    } else {
+        validatePath(pathS);
         return DerivationOutput {
             .output = DerivationOutputInputAddressed {
-                .path = std::move(path),
+                .path = store.parseStorePath(pathS),
             }
         };
+    }
 }
 
 static DerivationOutput parseDerivationOutput(const Store & store, std::istringstream & str)
 {
-    expect(str, ","); auto path = store.parseStorePath(parsePath(str));
+    expect(str, ","); const auto pathS = parseString(str);
     expect(str, ","); const auto hashAlgo = parseString(str);
     expect(str, ","); const auto hash = parseString(str);
     expect(str, ")");
 
-    return parseDerivationOutput(store, std::move(path), hashAlgo, hash);
+    return parseDerivationOutput(store, pathS, hashAlgo, hash);
 }
 
 
@@ -294,17 +309,19 @@ string Derivation::unparse(const Store & store, bool maskOutputs,
     for (auto & i : outputs) {
         if (first) first = false; else s += ',';
         s += '('; printUnquotedString(s, i.first);
-        s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(i.second.path(store, name)));
         std::visit(overloaded {
             [&](DerivationOutputInputAddressed doi) {
+                s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(doi.path));
                 s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, "");
             },
             [&](DerivationOutputCAFixed dof) {
+                s += ','; printUnquotedString(s, maskOutputs ? "" : store.printStorePath(dof.path(store, name, i.first)));
                 s += ','; printUnquotedString(s, dof.hash.printMethodAlgo());
                 s += ','; printUnquotedString(s, dof.hash.hash.to_string(Base16, false));
             },
             [&](DerivationOutputCAFloating dof) {
+                s += ','; printUnquotedString(s, "");
                 s += ','; printUnquotedString(s, makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
                 s += ','; printUnquotedString(s, "");
             },
@@ -360,6 +377,16 @@ bool isDerivation(const string & fileName)
 }
 
 
+std::string outputPathName(std::string_view drvName, std::string_view outputName) {
+    std::string res { drvName };
+    if (outputName != "out") {
+        res += "-";
+        res += outputName;
+    }
+    return res;
+}
+
+
 DerivationType BasicDerivation::type() const
 {
     std::set<std::string_view> inputAddressedOutputs, fixedCAOutputs, floatingCAOutputs;
@@ -452,12 +479,12 @@ DrvHashModulo hashDerivationModulo(Store & store, const Derivation & drv, bool m
         throw Error("Regular input-addressed derivations are not yet allowed to depend on CA derivations");
     case DerivationType::CAFixed: {
         std::map<std::string, Hash> outputHashes;
-        for (const auto & i : drv.outputsAndPaths(store)) {
-            auto & dof = std::get<DerivationOutputCAFixed>(i.second.first.output);
+        for (const auto & i : drv.outputs) {
+            auto & dof = std::get<DerivationOutputCAFixed>(i.second.output);
             auto hash = hashString(htSHA256, "fixed:out:"
                 + dof.hash.printMethodAlgo() + ":"
                 + dof.hash.hash.to_string(Base16, false) + ":"
-                + store.printStorePath(i.second.second));
+                + store.printStorePath(dof.path(store, drv.name, i.first)));
             outputHashes.insert_or_assign(i.first, std::move(hash));
         }
         return outputHashes;
@@ -508,21 +535,13 @@ bool wantOutput(const string & output, const std::set<string> & wanted)
 }
 
 
-StorePathSet BasicDerivation::outputPaths(const Store & store) const
-{
-    StorePathSet paths;
-    for (auto & i : outputsAndPaths(store))
-        paths.insert(i.second.second);
-    return paths;
-}
-
 static DerivationOutput readDerivationOutput(Source & in, const Store & store)
 {
-    auto path = store.parseStorePath(readString(in));
+    const auto pathS = readString(in);
     const auto hashAlgo = readString(in);
     const auto hash = readString(in);
 
-    return parseDerivationOutput(store, std::move(path), hashAlgo, hash);
+    return parseDerivationOutput(store, pathS, hashAlgo, hash);
 }
 
 StringSet BasicDerivation::outputNames() const
@@ -533,23 +552,12 @@ StringSet BasicDerivation::outputNames() const
     return names;
 }
 
-DerivationOutputsAndPaths BasicDerivation::outputsAndPaths(const Store & store) const {
-    DerivationOutputsAndPaths outsAndPaths;
-    for (auto output : outputs)
-        outsAndPaths.insert(std::make_pair(
-            output.first,
-            std::make_pair(output.second, output.second.path(store, name))
-            )
-        );
-    return outsAndPaths;
-}
-
 DerivationOutputsAndOptPaths BasicDerivation::outputsAndOptPaths(const Store & store) const {
     DerivationOutputsAndOptPaths outsAndOptPaths;
     for (auto output : outputs)
         outsAndOptPaths.insert(std::make_pair(
             output.first,
-            std::make_pair(output.second, output.second.pathOpt(store, output.first))
+            std::make_pair(output.second, output.second.path(store, name, output.first))
             )
         );
     return outsAndOptPaths;
@@ -594,22 +602,25 @@ Source & readDerivation(Source & in, const Store & store, BasicDerivation & drv,
 void writeDerivation(Sink & out, const Store & store, const BasicDerivation & drv)
 {
     out << drv.outputs.size();
-    for (auto & i : drv.outputsAndPaths(store)) {
-        out << i.first
-            << store.printStorePath(i.second.second);
+    for (auto & i : drv.outputs) {
+        out << i.first;
         std::visit(overloaded {
             [&](DerivationOutputInputAddressed doi) {
-                out << "" << "";
+                out << store.printStorePath(doi.path)
+                    << ""
+                    << "";
             },
             [&](DerivationOutputCAFixed dof) {
-                out << dof.hash.printMethodAlgo()
+                out << store.printStorePath(dof.path(store, drv.name, i.first))
+                    << dof.hash.printMethodAlgo()
                     << dof.hash.hash.to_string(Base16, false);
             },
             [&](DerivationOutputCAFloating dof) {
-                out << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
+                out << ""
+                    << (makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType))
                     << "";
             },
-        }, i.second.first.output);
+        }, i.second.output);
     }
     writeStorePaths(store, out, drv.inputSrcs);
     out << drv.platform << drv.builder << drv.args;
@@ -625,5 +636,12 @@ std::string hashPlaceholder(const std::string & outputName)
     return "/" + hashString(htSHA256, "nix-output:" + outputName).to_string(Base32, false);
 }
 
+std::string downstreamPlaceholder(const Store & store, const StorePath & drvPath, std::string_view outputName)
+{
+    auto drvNameWithExtension = drvPath.name();
+    auto drvName = drvNameWithExtension.substr(0, drvNameWithExtension.size() - 4);
+    auto clearText = "nix-upstream-output:" + std::string { drvPath.hashPart() } + ":" + outputPathName(drvName, outputName);
+    return "/" + hashString(htSHA256, clearText).to_string(Base32, false);
+}
 
 }
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 573502c90..0b5652685 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -27,6 +27,7 @@ struct DerivationOutputInputAddressed
 struct DerivationOutputCAFixed
 {
     FixedOutputHash hash; /* hash used for expected hash computation */
+    StorePath path(const Store & store, std::string_view drvName, std::string_view outputName) const;
 };
 
 /* Floating-output derivations, whose output paths are content addressed, but
@@ -49,14 +50,8 @@ struct DerivationOutput
     std::optional<HashType> hashAlgoOpt(const Store & store) const;
     /* Note, when you use this function you should make sure that you're passing
        the right derivation name. When in doubt, you should use the safer
-       interface provided by BasicDerivation::outputsAndPaths */
-    std::optional<StorePath> pathOpt(const Store & store, std::string_view drvName) const;
-    /* DEPRECATED: Remove after CA drvs are fully implemented */
-    StorePath path(const Store & store, std::string_view drvName) const {
-        auto p = pathOpt(store, drvName);
-        if (!p) throw UnimplementedError("floating content-addressed derivations are not yet implemented");
-        return *p;
-    }
+       interface provided by BasicDerivation::outputsAndOptPaths */
+    std::optional<StorePath> path(const Store & store, std::string_view drvName, std::string_view outputName) const;
 };
 
 typedef std::map<string, DerivationOutput> DerivationOutputs;
@@ -113,17 +108,12 @@ struct BasicDerivation
     /* Return true iff this is a fixed-output derivation. */
     DerivationType type() const;
 
-    /* Return the output paths of a derivation. */
-    StorePathSet outputPaths(const Store & store) const;
-
     /* Return the output names of a derivation. */
     StringSet outputNames() const;
 
     /* Calculates the maps that contains all the DerivationOutputs, but
-       augmented with knowledge of the Store paths they would be written into.
-       The first one of these functions will be removed when the CA work is
-       completed */
-    DerivationOutputsAndPaths outputsAndPaths(const Store & store) const;
+       augmented with knowledge of the Store paths they would be written
+       into. */
     DerivationOutputsAndOptPaths outputsAndOptPaths(const Store & store) const;
 
     static std::string_view nameFromPath(const StorePath & storePath);
@@ -155,6 +145,13 @@ Derivation parseDerivation(const Store & store, std::string && s, std::string_vi
 // FIXME: remove
 bool isDerivation(const string & fileName);
 
+/* Calculate the name that will be used for the store path for this
+   output.
+
+   This is usually <drv-name>-<output-name>, but is just <drv-name> when
+   the output name is "out". */
+std::string outputPathName(std::string_view drvName, std::string_view outputName);
+
 // known CA drv's output hashes, current just for fixed-output derivations
 // whose output hashes are always known since they are fixed up-front.
 typedef std::map<std::string, Hash> CaOutputHashes;
@@ -202,6 +199,21 @@ struct Sink;
 Source & readDerivation(Source & in, const Store & store, BasicDerivation & drv, std::string_view name);
 void writeDerivation(Sink & out, const Store & store, const BasicDerivation & drv);
 
+/* This creates an opaque and almost certainly unique string
+   deterministically from the output name.
+
+   It is used as a placeholder to allow derivations to refer to their
+   own outputs without needing to use the hash of a derivation in
+   itself, making the hash near-impossible to calculate. */
 std::string hashPlaceholder(const std::string & outputName);
 
+/* This creates an opaque and almost certainly unique string
+   deterministically from a derivation path and output name.
+
+   It is used as a placeholder to allow derivations to refer to
+   content-addressed paths whose content --- and thus the path
+   themselves --- isn't yet known. This occurs when a derivation has a
+   dependency which is a CA derivation. */
+std::string downstreamPlaceholder(const Store & store, const StorePath & drvPath, std::string_view outputName);
+
 }
diff --git a/src/libstore/local-store.cc b/src/libstore/local-store.cc
index a79b2da44..0086bb13e 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)
 {
@@ -618,12 +637,11 @@ uint64_t LocalStore::addValidPath(State & state,
            registration above is undone. */
         if (checkOutputs) checkDerivationOutputs(info.path, drv);
 
-        for (auto & i : drv.outputsAndPaths(*this)) {
-            state.stmtAddDerivationOutput.use()
-                (id)
-                (i.first)
-                (printStorePath(i.second.second))
-                .exec();
+        for (auto & i : drv.outputsAndOptPaths(*this)) {
+            /* Floating CA derivations have indeterminate output paths until
+               they are built, so don't register anything in that case */
+            if (i.second.second)
+                linkDeriverToPath(state, id, i.first, *i.second.second);
         }
     }
 
diff --git a/src/libstore/local-store.hh b/src/libstore/local-store.hh
index bb4ed9b19..d5e6d68ef 100644
--- a/src/libstore/local-store.hh
+++ b/src/libstore/local-store.hh
@@ -279,6 +279,11 @@ private:
        specified by the ‘secret-key-files’ option. */
     void signPathInfo(ValidPathInfo & info);
 
+    /* Register the store path 'output' as the output named 'outputName' of
+       derivation 'deriver'. */
+    void linkDeriverToPath(const StorePath & deriver, const string & outputName, const StorePath & output);
+    void linkDeriverToPath(State & state, uint64_t deriver, const string & outputName, const StorePath & output);
+
     Path getRealStoreDir() override { return realStoreDir; }
 
     void createUser(const std::string & userName, uid_t userId) override;
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index f6aa570bb..da3981696 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -203,17 +203,24 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
                 return;
             }
 
+            PathSet invalid;
+            /* true for regular derivations, and CA derivations for which we
+               have a trust mapping for all wanted outputs. */
+            auto knownOutputPaths = true;
+            for (auto & [outputName, pathOpt] : queryPartialDerivationOutputMap(path.path)) {
+                if (!pathOpt) {
+                    knownOutputPaths = false;
+                    break;
+                }
+                if (wantOutput(outputName, path.outputs) && !isValidPath(*pathOpt))
+                    invalid.insert(printStorePath(*pathOpt));
+            }
+            if (knownOutputPaths && invalid.empty()) return;
+
             auto drv = make_ref<Derivation>(derivationFromPath(path.path));
             ParsedDerivation parsedDrv(StorePath(path.path), *drv);
 
-            PathSet invalid;
-            for (auto & j : drv->outputsAndPaths(*this))
-                if (wantOutput(j.first, path.outputs)
-                    && !isValidPath(j.second.second))
-                    invalid.insert(printStorePath(j.second.second));
-            if (invalid.empty()) return;
-
-            if (settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
+            if (knownOutputPaths && settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
                 auto drvState = make_ref<Sync<DrvState>>(DrvState(invalid.size()));
                 for (auto & output : invalid)
                     pool.enqueue(std::bind(checkOutput, printStorePath(path.path), drv, output, drvState));
diff --git a/src/libstore/references.cc b/src/libstore/references.cc
index 62a3cda61..d2096cb49 100644
--- a/src/libstore/references.cc
+++ b/src/libstore/references.cc
@@ -79,9 +79,17 @@ void RefScanSink::operator () (const unsigned char * data, size_t len)
 std::pair<PathSet, HashResult> scanForReferences(const string & path,
     const PathSet & refs)
 {
-    RefScanSink refsSink;
     HashSink hashSink { htSHA256 };
-    TeeSink sink { refsSink, hashSink };
+    auto found = scanForReferences(hashSink, path, refs);
+    auto hash = hashSink.finish();
+    return std::pair<PathSet, HashResult>(found, hash);
+}
+
+PathSet scanForReferences(Sink & toTee,
+    const string & path, const PathSet & refs)
+{
+    RefScanSink refsSink;
+    TeeSink sink { refsSink, toTee };
     std::map<string, Path> backMap;
 
     /* For efficiency (and a higher hit rate), just search for the
@@ -111,9 +119,7 @@ std::pair<PathSet, HashResult> scanForReferences(const string & path,
         found.insert(j->second);
     }
 
-    auto hash = hashSink.finish();
-
-    return std::pair<PathSet, HashResult>(found, hash);
+    return found;
 }
 
 
diff --git a/src/libstore/references.hh b/src/libstore/references.hh
index 598a3203a..c2efd095c 100644
--- a/src/libstore/references.hh
+++ b/src/libstore/references.hh
@@ -7,6 +7,8 @@ namespace nix {
 
 std::pair<PathSet, HashResult> scanForReferences(const Path & path, const PathSet & refs);
 
+PathSet scanForReferences(Sink & toTee, const Path & path, const PathSet & refs);
+
 struct RewritingSink : Sink
 {
     std::string from, to, prev;
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index a41441079..b3877487c 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 61aa3ba7e..8b42aa6d2 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -247,10 +247,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 a6f1c42e9..6f4f4c855 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. Warning: a BufferedSink should not be
    used from multiple threads concurrently. */
diff --git a/src/nix-build/nix-build.cc b/src/nix-build/nix-build.cc
index 0400f94f5..3a8d67f21 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));
+        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->queryDerivationOutputMap(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));
+                }
+
+                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 3f2594712..b027e84b7 100644
--- a/src/nix-store/nix-store.cc
+++ b/src/nix-store/nix-store.cc
@@ -64,6 +64,7 @@ static PathSet realisePath(StorePathWithOutputs path, bool build = true)
 
     if (path.path.isDerivation()) {
         if (build) store->buildPaths({path});
+        auto outputPaths = store->queryDerivationOutputMap(path.path);
         Derivation drv = store->derivationFromPath(path.path);
         rootNr++;
 
@@ -76,7 +77,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();
@@ -84,10 +86,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);
+                    retPath = store2->addPermRoot(outPath, rootName);
                 }
             }
-            outputs.insert(outPath);
+            outputs.insert(retPath);
         }
         return outputs;
     }
@@ -217,8 +219,13 @@ static StorePathSet maybeUseOutputs(const StorePath & storePath, bool useOutput,
     if (useOutput && storePath.isDerivation()) {
         auto drv = store->derivationFromPath(storePath);
         StorePathSet outputs;
-        for (auto & i : drv.outputsAndPaths(*store))
-            outputs.insert(i.second.second);
+        if (forceRealise)
+            return store->queryDerivationOutputs(storePath);
+        for (auto & i : drv.outputsAndOptPaths(*store)) {
+            if (!i.second.second)
+                throw UsageError("Cannot use output path of floating content-addressed derivation until we know what it is (e.g. by building it)");
+            outputs.insert(*i.second.second);
+        }
         return outputs;
     }
     else return {storePath};
@@ -308,11 +315,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.outputsAndPaths(*store))
-                    cout << fmt("%1%\n", store->printStorePath(j.second.second));
+                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 75a42ac55..4605eb13e 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));
                         },
                         [&](BuildableFromDrv bfd) {
-                            for (auto & output : bfd.outputs) {
+                            auto builtOutputs = store->queryDerivationOutputMap(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 efac230bd..37a4bc785 100644
--- a/src/nix/command.cc
+++ b/src/nix/command.cc
@@ -150,7 +150,10 @@ void MixProfile::updateProfile(const Buildables & buildables)
             },
             [&](BuildableFromDrv bfd) {
                 for (auto & output : bfd.outputs) {
-                    result.push_back(output.second);
+                    /* Output path should be known because we just tried to
+                       build it. */
+                    assert(!output.second);
+                    result.push_back(*output.second);
                 }
             },
         }, buildable);
diff --git a/src/nix/develop.cc b/src/nix/develop.cc
index 516e7bda9..a2ce9c8c1 100644
--- a/src/nix/develop.cc
+++ b/src/nix/develop.cc
@@ -145,7 +145,10 @@ StorePath getDerivationEnvironment(ref<Store> store, const StorePath & drvPath)
     /* Build the derivation. */
     store->buildPaths({{shellDrvPath}});
 
-    for (auto & outPath : drv.outputPaths(*store)) {
+    for (auto & [_0, outputAndOptPath] : drv.outputsAndOptPaths(*store)) {
+        auto & [_1, optPath] = outputAndOptPath;
+        assert(optPath);
+        auto & outPath = *optPath;
         assert(store->isValidPath(outPath));
         auto outPathS = store->toRealPath(outPath);
         if (lstat(outPathS).st_size)
diff --git a/src/nix/installables.cc b/src/nix/installables.cc
index 1f1ed680f..9bf6b7caa 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 & i : drv.outputsAndPaths(*store))
-                outputs.emplace(i.first, i.second.second);
+            for (auto & [name, output] : drv.outputsAndOptPaths(*store))
+                outputs.emplace(name, output.second);
             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 9241931e9..7ce4dfe4c 100644
--- a/src/nix/profile.cc
+++ b/src/nix/profile.cc
@@ -180,7 +180,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,
@@ -191,7 +193,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);
@@ -349,7 +351,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 50d9b2568..329999475 100644
--- a/src/nix/repl.cc
+++ b/src/nix/repl.cc
@@ -496,8 +496,8 @@ bool NixRepl::processLine(string line)
             if (runProgram(settings.nixBinDir + "/nix", Strings{"build", "--no-link", drvPathRaw}) == 0) {
                 auto drv = state->store->readDerivation(drvPath);
                 std::cout << std::endl << "this derivation produced the following outputs:" << std::endl;
-                for (auto & i : drv.outputsAndPaths(*state->store))
-                    std::cout << fmt("  %s -> %s\n", i.first, state->store->printStorePath(i.second.second));
+                for (auto & i : drv.outputsAndOptPaths(*state->store))
+                    std::cout << fmt("  %s -> %s\n", i.first, state->store->printStorePath(*i.second.second));
             }
         } else if (command == ":i") {
             runProgram(settings.nixBinDir + "/nix-env", Strings{"-i", drvPathRaw});
diff --git a/src/nix/show-derivation.cc b/src/nix/show-derivation.cc
index 8c4bfb03e..b9f33499b 100644
--- a/src/nix/show-derivation.cc
+++ b/src/nix/show-derivation.cc
@@ -67,21 +67,22 @@ struct CmdShowDerivation : InstallablesCommand
 
             {
                 auto outputsObj(drvObj.object("outputs"));
-                for (auto & output : drv.outputsAndPaths(*store)) {
-                    auto outputObj(outputsObj.object(output.first));
-                    outputObj.attr("path", store->printStorePath(output.second.second));
-
+                for (auto & [_outputName, output] : drv.outputs) {
+                    auto & outputName = _outputName; // work around clang bug
+                    auto outputObj { outputsObj.object(outputName) };
                     std::visit(overloaded {
                         [&](DerivationOutputInputAddressed doi) {
+                            outputObj.attr("path", store->printStorePath(doi.path));
                         },
                         [&](DerivationOutputCAFixed dof) {
+                            outputObj.attr("path", store->printStorePath(dof.path(*store, drv.name, outputName)));
                             outputObj.attr("hashAlgo", dof.hash.printMethodAlgo());
                             outputObj.attr("hash", dof.hash.hash.to_string(Base16, false));
                         },
                         [&](DerivationOutputCAFloating dof) {
                             outputObj.attr("hashAlgo", makeFileIngestionPrefix(dof.method) + printHashType(dof.hashType));
                         },
-                    }, output.second.first.output);
+                    }, output.output);
                 }
             }
 
diff --git a/tests/content-addressed.nix b/tests/content-addressed.nix
new file mode 100644
index 000000000..5e9bad0ac
--- /dev/null
+++ b/tests/content-addressed.nix
@@ -0,0 +1,32 @@
+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
+rec {
+  rootLegacy = mkDerivation {
+    name = "simple-input-addressed";
+    buildCommand = ''
+      set -x
+      echo "Building a legacy derivation"
+      mkdir -p $out
+      echo "Hello World" > $out/hello
+    '';
+  };
+  rootCA = mkDerivation {
+    name = "dependent";
+    outputs = [ "out" "dev" ];
+    buildCommand = ''
+      echo "building a CA derivation"
+      echo "The seed is ${toString seed}"
+      mkdir -p $out
+      echo ${rootLegacy}/hello > $out/dep
+      # test symlink at root
+      ln -s $out $dev
+    '';
+    __contentAddressed = true;
+    outputHashMode = "recursive";
+    outputHashAlgo = "sha256";
+  };
+}
diff --git a/tests/content-addressed.sh b/tests/content-addressed.sh
new file mode 100644
index 000000000..ae9e3c59e
--- /dev/null
+++ b/tests/content-addressed.sh
@@ -0,0 +1,17 @@
+#!/usr/bin/env bash
+
+source common.sh
+
+clearStore
+clearCache
+
+export REMOTE_STORE=file://$cacheDir
+
+drv=$(nix-instantiate --experimental-features ca-derivations ./content-addressed.nix -A rootCA --arg seed 1)
+nix --experimental-features 'nix-command ca-derivations' show-derivation --derivation "$drv" --arg seed 1
+
+commonArgs=("--experimental-features" "ca-derivations" "./content-addressed.nix" "-A" "rootCA" "--no-out-link")
+out1=$(nix-build "${commonArgs[@]}" ./content-addressed.nix --arg seed 1)
+out2=$(nix-build "${commonArgs[@]}" ./content-addressed.nix --arg seed 2)
+
+test $out1 == $out2
diff --git a/tests/local.mk b/tests/local.mk
index 53035da41..5d25de019 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
   # build-remote-content-addressed-fixed.sh \
 
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..."