Merge pull request #4628 from obsidiansystems/dynamic-drvs

Dynamic derivations RFC 92

23 files changed, 792 insertions, 193 deletions

diff --git a/doc/manual/src/protocols/derivation-aterm.md b/doc/manual/src/protocols/derivation-aterm.md
index c9dc00ef7..e58b602a3 100644
--- a/doc/manual/src/protocols/derivation-aterm.md
+++ b/doc/manual/src/protocols/derivation-aterm.md
@@ -2,8 +2,18 @@
 
 For historical reasons, [derivations](@docroot@/glossary.md#gloss-store-derivation) are stored on-disk in [ATerm](https://homepages.cwi.nl/~daybuild/daily-books/technology/aterm-guide/aterm-guide.html) format.
 
-Derivations are serialised in the following format:
+Derivations are serialised in one of the following formats:
 
-```
-Derive(...)
-```
+- ```
+  Derive(...)
+  ```
+
+  For all stable derivations.
+
+- ```
+  DrvWithVersion(<version-string>, ...)
+  ```
+
+  The only `version-string`s that are in use today are for [experimental features](@docroot@/contributing/experimental-features.md):
+
+  - `"xp-dyn-drv"` for the [`dynamic-derivations`](@docroot@/contributing/experimental-features.md#xp-feature-dynamic-derivations) experimental feature.
diff --git a/perl/lib/Nix/Store.xs b/perl/lib/Nix/Store.xs
index c38ea2d2b..e96885e4c 100644
--- a/perl/lib/Nix/Store.xs
+++ b/perl/lib/Nix/Store.xs
@@ -324,7 +324,7 @@ SV * derivationFromPath(char * drvPath)
             hv_stores(hash, "outputs", newRV((SV *) outputs));
 
             AV * inputDrvs = newAV();
-            for (auto & i : drv.inputDrvs)
+            for (auto & i : drv.inputDrvs.map)
                 av_push(inputDrvs, newSVpv(store()->printStorePath(i.first).c_str(), 0)); // !!! ignores i->second
             hv_stores(hash, "inputDrvs", newRV((SV *) inputDrvs));
 
diff --git a/src/build-remote/build-remote.cc b/src/build-remote/build-remote.cc
index c1f03a8ef..d69d3a0c2 100644
--- a/src/build-remote/build-remote.cc
+++ b/src/build-remote/build-remote.cc
@@ -314,7 +314,7 @@ connected:
             //
             // 2. Changing the `inputSrcs` set changes the associated
             //    output ids, which break CA derivations
-            if (!drv.inputDrvs.empty())
+            if (!drv.inputDrvs.map.empty())
                 drv.inputSrcs = store->parseStorePathSet(inputs);
             optResult = sshStore->buildDerivation(*drvPath, (const BasicDerivation &) drv);
             auto & result = *optResult;
diff --git a/src/libcmd/built-path.cc b/src/libcmd/built-path.cc
index c6cc7fa9c..9a2dce806 100644
--- a/src/libcmd/built-path.cc
+++ b/src/libcmd/built-path.cc
@@ -58,6 +58,28 @@ StorePathSet BuiltPath::outPaths() const
     );
 }
 
+SingleDerivedPath::Built SingleBuiltPath::Built::discardOutputPath() const
+{
+    return SingleDerivedPath::Built {
+        .drvPath = make_ref<SingleDerivedPath>(drvPath->discardOutputPath()),
+        .output = output.first,
+    };
+}
+
+SingleDerivedPath SingleBuiltPath::discardOutputPath() const
+{
+    return std::visit(
+        overloaded{
+            [](const SingleBuiltPath::Opaque & p) -> SingleDerivedPath {
+                return p;
+            },
+            [](const SingleBuiltPath::Built & b) -> SingleDerivedPath {
+                return b.discardOutputPath();
+            },
+        }, raw()
+    );
+}
+
 nlohmann::json BuiltPath::Built::toJSON(const Store & store) const
 {
     nlohmann::json res;
diff --git a/src/libcmd/built-path.hh b/src/libcmd/built-path.hh
index 747bcc440..e677bc810 100644
--- a/src/libcmd/built-path.hh
+++ b/src/libcmd/built-path.hh
@@ -9,6 +9,8 @@ struct SingleBuiltPathBuilt {
     ref<SingleBuiltPath> drvPath;
     std::pair<std::string, StorePath> output;
 
+    SingleDerivedPathBuilt discardOutputPath() const;
+
     std::string to_string(const Store & store) const;
     static SingleBuiltPathBuilt parse(const Store & store, std::string_view, std::string_view);
     nlohmann::json toJSON(const Store & store) const;
@@ -34,6 +36,8 @@ struct SingleBuiltPath : _SingleBuiltPathRaw {
 
     StorePath outPath() const;
 
+    SingleDerivedPath discardOutputPath() const;
+
     static SingleBuiltPath parse(const Store & store, std::string_view);
     nlohmann::json toJSON(const Store & store) const;
 };
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index e2b1ac4f6..cd9a05bb2 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -1252,15 +1252,13 @@ drvName, Bindings * attrs, Value & v)
                 state.store->computeFSClosure(d.drvPath, refs);
                 for (auto & j : refs) {
                     drv.inputSrcs.insert(j);
-                    if (j.isDerivation())
-                        drv.inputDrvs[j] = state.store->readDerivation(j).outputNames();
+                    if (j.isDerivation()) {
+                        drv.inputDrvs.map[j].value = state.store->readDerivation(j).outputNames();
+                    }
                 }
             },
             [&](const NixStringContextElem::Built & b) {
-                if (auto * p = std::get_if<DerivedPath::Opaque>(&*b.drvPath))
-                    drv.inputDrvs[p->path].insert(b.output);
-                else
-                    throw UnimplementedError("Dependencies on the outputs of dynamic derivations are not yet supported");
+                drv.inputDrvs.ensureSlot(*b.drvPath).value.insert(b.output);
             },
             [&](const NixStringContextElem::Opaque & o) {
                 drv.inputSrcs.insert(o.path);
diff --git a/src/libstore/build/derivation-goal.cc b/src/libstore/build/derivation-goal.cc
index bec0bc538..6472ecd99 100644
--- a/src/libstore/build/derivation-goal.cc
+++ b/src/libstore/build/derivation-goal.cc
@@ -350,25 +350,37 @@ void DerivationGoal::gaveUpOnSubstitution()
 
     /* The inputs must be built before we can build this goal. */
     inputDrvOutputs.clear();
-    if (useDerivation)
-        for (auto & i : dynamic_cast<Derivation *>(drv.get())->inputDrvs) {
+    if (useDerivation) {
+        std::function<void(ref<SingleDerivedPath>, const DerivedPathMap<StringSet>::ChildNode &)> addWaiteeDerivedPath;
+
+        addWaiteeDerivedPath = [&](ref<SingleDerivedPath> inputDrv, const DerivedPathMap<StringSet>::ChildNode & inputNode) {
+            if (!inputNode.value.empty())
+                addWaitee(worker.makeGoal(
+                    DerivedPath::Built {
+                        .drvPath = inputDrv,
+                        .outputs = inputNode.value,
+                    },
+                    buildMode == bmRepair ? bmRepair : bmNormal));
+            for (const auto & [outputName, childNode] : inputNode.childMap)
+                addWaiteeDerivedPath(
+                    make_ref<SingleDerivedPath>(SingleDerivedPath::Built { inputDrv, outputName }),
+                    childNode);
+        };
+
+        for (const auto & [inputDrvPath, inputNode] : dynamic_cast<Derivation *>(drv.get())->inputDrvs.map) {
             /* Ensure that pure, non-fixed-output derivations don't
                depend on impure derivations. */
             if (experimentalFeatureSettings.isEnabled(Xp::ImpureDerivations) && drv->type().isPure() && !drv->type().isFixed()) {
-                auto inputDrv = worker.evalStore.readDerivation(i.first);
+                auto inputDrv = worker.evalStore.readDerivation(inputDrvPath);
                 if (!inputDrv.type().isPure())
                     throw Error("pure derivation '%s' depends on impure derivation '%s'",
                         worker.store.printStorePath(drvPath),
-                        worker.store.printStorePath(i.first));
+                        worker.store.printStorePath(inputDrvPath));
             }
 
-            addWaitee(worker.makeGoal(
-                DerivedPath::Built {
-                    .drvPath = makeConstantStorePathRef(i.first),
-                    .outputs = i.second,
-                },
-                buildMode == bmRepair ? bmRepair : bmNormal));
+            addWaiteeDerivedPath(makeConstantStorePathRef(inputDrvPath), inputNode);
         }
+    }
 
     /* Copy the input sources from the eval store to the build
        store. */
@@ -501,7 +513,7 @@ void DerivationGoal::inputsRealised()
                 return ia.deferred;
             },
             [&](const DerivationType::ContentAddressed & ca) {
-                return !fullDrv.inputDrvs.empty() && (
+                return !fullDrv.inputDrvs.map.empty() && (
                     ca.fixed
                     /* Can optionally resolve if fixed, which is good
                        for avoiding unnecessary rebuilds. */
@@ -515,7 +527,7 @@ void DerivationGoal::inputsRealised()
             }
         }, drvType.raw);
 
-        if (resolveDrv && !fullDrv.inputDrvs.empty()) {
+        if (resolveDrv && !fullDrv.inputDrvs.map.empty()) {
             experimentalFeatureSettings.require(Xp::CaDerivations);
 
             /* We are be able to resolve this derivation based on the
@@ -552,11 +564,13 @@ void DerivationGoal::inputsRealised()
             return;
         }
 
-        for (auto & [depDrvPath, wantedDepOutputs] : fullDrv.inputDrvs) {
+        std::function<void(const StorePath &, const DerivedPathMap<StringSet>::ChildNode &)> accumInputPaths;
+
+        accumInputPaths = [&](const StorePath & depDrvPath, const DerivedPathMap<StringSet>::ChildNode & inputNode) {
             /* 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. */
-            for (auto & j : wantedDepOutputs) {
+            auto getOutput = [&](const std::string & outputName) {
                 /* TODO (impure derivations-induced tech debt):
                    Tracking input derivation outputs statefully through the
                    goals is error prone and has led to bugs.
@@ -568,21 +582,30 @@ void DerivationGoal::inputsRealised()
                    a representation in the store, which is a usability problem
                    in itself. When implementing this logic entirely with lookups
                    make sure that they're cached. */
-                if (auto outPath = get(inputDrvOutputs, { depDrvPath, j })) {
-                    worker.store.computeFSClosure(*outPath, inputPaths);
+                if (auto outPath = get(inputDrvOutputs, { depDrvPath, outputName })) {
+                    return *outPath;
                 }
                 else {
                     auto outMap = worker.evalStore.queryDerivationOutputMap(depDrvPath);
-                    auto outMapPath = outMap.find(j);
+                    auto outMapPath = outMap.find(outputName);
                     if (outMapPath == outMap.end()) {
                         throw Error(
                             "derivation '%s' requires non-existent output '%s' from input derivation '%s'",
-                            worker.store.printStorePath(drvPath), j, worker.store.printStorePath(depDrvPath));
+                            worker.store.printStorePath(drvPath), outputName, worker.store.printStorePath(depDrvPath));
                     }
-                    worker.store.computeFSClosure(outMapPath->second, inputPaths);
+                    return outMapPath->second;
                 }
-            }
-        }
+            };
+
+            for (auto & outputName : inputNode.value)
+                worker.store.computeFSClosure(getOutput(outputName), inputPaths);
+
+            for (auto & [outputName, childNode] : inputNode.childMap)
+                accumInputPaths(getOutput(outputName), childNode);
+        };
+
+        for (auto & [depDrvPath, depNode] : fullDrv.inputDrvs.map)
+            accumInputPaths(depDrvPath, depNode);
     }
 
     /* Second, the input sources. */
@@ -1475,22 +1498,24 @@ void DerivationGoal::waiteeDone(GoalPtr waitee, ExitCode result)
     if (!useDerivation) return;
     auto & fullDrv = *dynamic_cast<Derivation *>(drv.get());
 
-    auto * dg = tryGetConcreteDrvGoal(waitee);
-    if (!dg) return;
+    std::optional info = tryGetConcreteDrvGoal(waitee);
+    if (!info) return;
+    const auto & [dg, drvReq] = *info;
 
-    auto outputs = fullDrv.inputDrvs.find(dg->drvPath);
-    if (outputs == fullDrv.inputDrvs.end()) return;
+    auto * nodeP = fullDrv.inputDrvs.findSlot(drvReq.get());
+    if (!nodeP) return;
+    auto & outputs = nodeP->value;
 
-    for (auto & outputName : outputs->second) {
-        auto buildResult = dg->getBuildResult(DerivedPath::Built {
-            .drvPath = makeConstantStorePathRef(dg->drvPath),
+    for (auto & outputName : outputs) {
+        auto buildResult = dg.get().getBuildResult(DerivedPath::Built {
+            .drvPath = makeConstantStorePathRef(dg.get().drvPath),
             .outputs = OutputsSpec::Names { outputName },
         });
         if (buildResult.success()) {
             auto i = buildResult.builtOutputs.find(outputName);
             if (i != buildResult.builtOutputs.end())
                 inputDrvOutputs.insert_or_assign(
-                    { dg->drvPath, outputName },
+                    { dg.get().drvPath, outputName },
                     i->second.outPath);
         }
     }
diff --git a/src/libstore/build/worker.cc b/src/libstore/build/worker.cc
index f65f63b99..b4a634e7b 100644
--- a/src/libstore/build/worker.cc
+++ b/src/libstore/build/worker.cc
@@ -594,11 +594,14 @@ GoalPtr upcast_goal(std::shared_ptr<DerivationGoal> subGoal)
     return subGoal;
 }
 
-const DerivationGoal * tryGetConcreteDrvGoal(GoalPtr waitee)
+std::optional<std::pair<std::reference_wrapper<const DerivationGoal>, std::reference_wrapper<const SingleDerivedPath>>> tryGetConcreteDrvGoal(GoalPtr waitee)
 {
     auto * odg = dynamic_cast<CreateDerivationAndRealiseGoal *>(&*waitee);
-    if (!odg) return nullptr;
-    return &*odg->concreteDrvGoal;
+    if (!odg) return std::nullopt;
+    return {{
+        std::cref(*odg->concreteDrvGoal),
+        std::cref(*odg->drvReq),
+    }};
 }
 
 }
diff --git a/src/libstore/build/worker.hh b/src/libstore/build/worker.hh
index a778e311c..6f6d25d7d 100644
--- a/src/libstore/build/worker.hh
+++ b/src/libstore/build/worker.hh
@@ -49,7 +49,8 @@ typedef std::chrono::time_point<std::chrono::steady_clock> steady_time_point;
  * we have made the function, written in `worker.cc` where all the goal
  * types are visible, and use it instead.
  */
-const DerivationGoal * tryGetConcreteDrvGoal(GoalPtr waitee);
+
+std::optional<std::pair<std::reference_wrapper<const DerivationGoal>, std::reference_wrapper<const SingleDerivedPath>>> tryGetConcreteDrvGoal(GoalPtr waitee);
 
 /**
  * A mapping used to remember for each child process to what goal it
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index 43d3dc4a2..67069c3c9 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -136,7 +136,7 @@ StorePath writeDerivation(Store & store,
     const Derivation & drv, RepairFlag repair, bool readOnly)
 {
     auto references = drv.inputSrcs;
-    for (auto & i : drv.inputDrvs)
+    for (auto & i : drv.inputDrvs.map)
         references.insert(i.first);
     /* Note that the outputs of a derivation are *not* references
        (that can be missing (of course) and should not necessarily be
@@ -208,22 +208,25 @@ static bool endOfList(std::istream & str)
 static StringSet parseStrings(std::istream & str, bool arePaths)
 {
     StringSet res;
+    expect(str, "[");
     while (!endOfList(str))
         res.insert(arePaths ? parsePath(str) : parseString(str));
     return res;
 }
 
 
-static DerivationOutput parseDerivationOutput(const Store & store,
-    std::string_view pathS, std::string_view hashAlgo, std::string_view hashS)
+static DerivationOutput parseDerivationOutput(
+    const Store & store,
+    std::string_view pathS, std::string_view hashAlgo, std::string_view hashS,
+    const ExperimentalFeatureSettings & xpSettings)
 {
     if (hashAlgo != "") {
         ContentAddressMethod method = ContentAddressMethod::parsePrefix(hashAlgo);
         if (method == TextIngestionMethod {})
-            experimentalFeatureSettings.require(Xp::DynamicDerivations);
+            xpSettings.require(Xp::DynamicDerivations);
         const auto hashType = parseHashType(hashAlgo);
         if (hashS == "impure") {
-            experimentalFeatureSettings.require(Xp::ImpureDerivations);
+            xpSettings.require(Xp::ImpureDerivations);
             if (pathS != "")
                 throw FormatError("impure derivation output should not specify output path");
             return DerivationOutput::Impure {
@@ -240,7 +243,7 @@ static DerivationOutput parseDerivationOutput(const Store & store,
                 },
             };
         } else {
-            experimentalFeatureSettings.require(Xp::CaDerivations);
+            xpSettings.require(Xp::CaDerivations);
             if (pathS != "")
                 throw FormatError("content-addressed derivation output should not specify output path");
             return DerivationOutput::CAFloating {
@@ -259,29 +262,116 @@ static DerivationOutput parseDerivationOutput(const Store & store,
     }
 }
 
-static DerivationOutput parseDerivationOutput(const Store & store, std::istringstream & str)
+static DerivationOutput parseDerivationOutput(
+    const Store & store, std::istringstream & str,
+    const ExperimentalFeatureSettings & xpSettings = experimentalFeatureSettings)
 {
     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, pathS, hashAlgo, hash);
+    return parseDerivationOutput(store, pathS, hashAlgo, hash, xpSettings);
+}
+
+/**
+ * All ATerm Derivation format versions currently known.
+ *
+ * Unknown versions are rejected at the parsing stage.
+ */
+enum struct DerivationATermVersion {
+    /**
+     * Older unversioned form
+     */
+    Traditional,
+
+    /**
+     * Newer versioned form; only this version so far.
+     */
+    DynamicDerivations,
+};
+
+static DerivedPathMap<StringSet>::ChildNode parseDerivedPathMapNode(
+    const Store & store,
+    std::istringstream & str,
+    DerivationATermVersion version)
+{
+    DerivedPathMap<StringSet>::ChildNode node;
+
+    auto parseNonDynamic = [&]() {
+        node.value = parseStrings(str, false);
+    };
+
+    // Older derivation should never use new form, but newer
+    // derivaiton can use old form.
+    switch (version) {
+    case DerivationATermVersion::Traditional:
+        parseNonDynamic();
+        break;
+    case DerivationATermVersion::DynamicDerivations:
+        switch (str.peek()) {
+        case '[':
+            parseNonDynamic();
+            break;
+        case '(':
+            expect(str, "(");
+            node.value = parseStrings(str, false);
+            expect(str, ",[");
+            while (!endOfList(str)) {
+                expect(str, "(");
+                auto outputName = parseString(str);
+                expect(str, ",");
+                node.childMap.insert_or_assign(outputName, parseDerivedPathMapNode(store, str, version));
+                expect(str, ")");
+            }
+            expect(str, ")");
+            break;
+        default:
+            throw FormatError("invalid inputDrvs entry in derivation");
+        }
+        break;
+    default:
+        // invalid format, not a parse error but internal error
+        assert(false);
+    }
+    return node;
 }
 
 
-Derivation parseDerivation(const Store & store, std::string && s, std::string_view name)
+Derivation parseDerivation(
+    const Store & store, std::string && s, std::string_view name,
+    const ExperimentalFeatureSettings & xpSettings)
 {
     Derivation drv;
     drv.name = name;
 
     std::istringstream str(std::move(s));
-    expect(str, "Derive([");
+    expect(str, "D");
+    DerivationATermVersion version;
+    switch (str.peek()) {
+    case 'e':
+        expect(str, "erive(");
+        version = DerivationATermVersion::Traditional;
+        break;
+    case 'r':
+        expect(str, "rvWithVersion(");
+        auto versionS = parseString(str);
+        if (versionS == "xp-dyn-drv") {
+            // Only verison we have so far
+            version = DerivationATermVersion::DynamicDerivations;
+            xpSettings.require(Xp::DynamicDerivations);
+        } else {
+            throw FormatError("Unknown derivation ATerm format version '%s'", versionS);
+        }
+        expect(str, ",");
+        break;
+    }
 
     /* Parse the list of outputs. */
+    expect(str, "[");
     while (!endOfList(str)) {
         expect(str, "("); std::string id = parseString(str);
-        auto output = parseDerivationOutput(store, str);
+        auto output = parseDerivationOutput(store, str, xpSettings);
         drv.outputs.emplace(std::move(id), std::move(output));
     }
 
@@ -290,12 +380,12 @@ Derivation parseDerivation(const Store & store, std::string && s, std::string_vi
     while (!endOfList(str)) {
         expect(str, "(");
         Path drvPath = parsePath(str);
-        expect(str, ",[");
-        drv.inputDrvs.insert_or_assign(store.parseStorePath(drvPath), parseStrings(str, false));
+        expect(str, ",");
+        drv.inputDrvs.map.insert_or_assign(store.parseStorePath(drvPath), parseDerivedPathMapNode(store, str, version));
         expect(str, ")");
     }
 
-    expect(str, ",["); drv.inputSrcs = store.parseStorePathSet(parseStrings(str, true));
+    expect(str, ","); drv.inputSrcs = store.parseStorePathSet(parseStrings(str, true));
     expect(str, ","); drv.platform = parseString(str);
     expect(str, ","); drv.builder = parseString(str);
 
@@ -379,14 +469,67 @@ static void printUnquotedStrings(std::string & res, ForwardIterator i, ForwardIt
 }
 
 
+static void unparseDerivedPathMapNode(const Store & store, std::string & s, const DerivedPathMap<StringSet>::ChildNode & node)
+{
+    s += ',';
+    if (node.childMap.empty()) {
+        printUnquotedStrings(s, node.value.begin(), node.value.end());
+    } else {
+        s += "(";
+        printUnquotedStrings(s, node.value.begin(), node.value.end());
+        s += ",[";
+        bool first = true;
+        for (auto & [outputName, childNode] : node.childMap) {
+            if (first) first = false; else s += ',';
+            s += '('; printUnquotedString(s, outputName);
+            unparseDerivedPathMapNode(store, s, childNode);
+            s += ')';
+        }
+        s += "])";
+    }
+}
+
+
+/**
+ * Does the derivation have a dependency on the output of a dynamic
+ * derivation?
+ *
+ * In other words, does it on the output of derivation that is itself an
+ * ouput of a derivation? This corresponds to a dependency that is an
+ * inductive derived path with more than one layer of
+ * `DerivedPath::Built`.
+ */
+static bool hasDynamicDrvDep(const Derivation & drv)
+{
+    return
+        std::find_if(
+            drv.inputDrvs.map.begin(),
+            drv.inputDrvs.map.end(),
+            [](auto & kv) { return !kv.second.childMap.empty(); })
+        != drv.inputDrvs.map.end();
+}
+
+
 std::string Derivation::unparse(const Store & store, bool maskOutputs,
-    std::map<std::string, StringSet> * actualInputs) const
+    DerivedPathMap<StringSet>::ChildNode::Map * actualInputs) const
 {
     std::string s;
     s.reserve(65536);
-    s += "Derive([";
+
+    /* Use older unversioned form if possible, for wider compat. Use
+       newer form only if we need it, which we do for
+       `Xp::DynamicDerivations`. */
+    if (hasDynamicDrvDep(*this)) {
+        s += "DrvWithVersion(";
+        // Only version we have so far
+        printUnquotedString(s, "xp-dyn-drv");
+        s += ",";
+    } else {
+        s += "Derive(";
+    }
 
     bool first = true;
+    s += "[";
     for (auto & i : outputs) {
         if (first) first = false; else s += ',';
         s += '('; printUnquotedString(s, i.first);
@@ -424,17 +567,17 @@ std::string Derivation::unparse(const Store & store, bool maskOutputs,
     s += "],[";
     first = true;
     if (actualInputs) {
-        for (auto & i : *actualInputs) {
+        for (auto & [drvHashModulo, childMap] : *actualInputs) {
             if (first) first = false; else s += ',';
-            s += '('; printUnquotedString(s, i.first);
-            s += ','; printUnquotedStrings(s, i.second.begin(), i.second.end());
+            s += '('; printUnquotedString(s, drvHashModulo);
+            unparseDerivedPathMapNode(store, s, childMap);
             s += ')';
         }
     } else {
-        for (auto & i : inputDrvs) {
+        for (auto & [drvPath, childMap] : inputDrvs.map) {
             if (first) first = false; else s += ',';
-            s += '('; printUnquotedString(s, store.printStorePath(i.first));
-            s += ','; printUnquotedStrings(s, i.second.begin(), i.second.end());
+            s += '('; printUnquotedString(s, store.printStorePath(drvPath));
+            unparseDerivedPathMapNode(store, s, childMap);
             s += ')';
         }
     }
@@ -668,18 +811,16 @@ DrvHash hashDerivationModulo(Store & store, const Derivation & drv, bool maskOut
         }
     }, drv.type().raw);
 
-    std::map<std::string, StringSet> inputs2;
-    for (auto & [drvPath, inputOutputs0] : drv.inputDrvs) {
-        // Avoid lambda capture restriction with standard / Clang
-        auto & inputOutputs = inputOutputs0;
+    DerivedPathMap<StringSet>::ChildNode::Map inputs2;
+    for (auto & [drvPath, node] : drv.inputDrvs.map) {
         const auto & res = pathDerivationModulo(store, drvPath);
         if (res.kind == DrvHash::Kind::Deferred)
             kind = DrvHash::Kind::Deferred;
-        for (auto & outputName : inputOutputs) {
+        for (auto & outputName : node.value) {
             const auto h = get(res.hashes, outputName);
             if (!h)
                 throw Error("no hash for output '%s' of derivation '%s'", outputName, drv.name);
-            inputs2[h->to_string(Base16, false)].insert(outputName);
+            inputs2[h->to_string(Base16, false)].value.insert(outputName);
         }
     }
 
@@ -709,7 +850,7 @@ static DerivationOutput readDerivationOutput(Source & in, const Store & store)
     const auto hashAlgo = readString(in);
     const auto hash = readString(in);
 
-    return parseDerivationOutput(store, pathS, hashAlgo, hash);
+    return parseDerivationOutput(store, pathS, hashAlgo, hash, experimentalFeatureSettings);
 }
 
 StringSet BasicDerivation::outputNames() const
@@ -824,6 +965,8 @@ std::string hashPlaceholder(const OutputNameView outputName)
 
 static void rewriteDerivation(Store & store, BasicDerivation & drv, const StringMap & rewrites)
 {
+    debug("Rewriting the derivation");
+
     for (auto & rewrite : rewrites) {
         debug("rewriting %s as %s", rewrite.first, rewrite.second);
     }
@@ -862,14 +1005,70 @@ std::optional<BasicDerivation> Derivation::tryResolve(Store & store) const
 {
     std::map<std::pair<StorePath, std::string>, StorePath> inputDrvOutputs;
 
-    for (auto & input : inputDrvs)
-        for (auto & [outputName, outputPath] : store.queryPartialDerivationOutputMap(input.first))
-            if (outputPath)
-                inputDrvOutputs.insert_or_assign({input.first, outputName}, *outputPath);
+    std::function<void(const StorePath &, const DerivedPathMap<StringSet>::ChildNode &)> accum;
+    accum = [&](auto & inputDrv, auto & node) {
+        for (auto & [outputName, outputPath] : store.queryPartialDerivationOutputMap(inputDrv)) {
+            if (outputPath) {
+                inputDrvOutputs.insert_or_assign({inputDrv, outputName}, *outputPath);
+                if (auto p = get(node.childMap, outputName))
+                    accum(*outputPath, *p);
+            }
+        }
+    };
+
+    for (auto & [inputDrv, node] : inputDrvs.map)
+        accum(inputDrv, node);
 
     return tryResolve(store, inputDrvOutputs);
 }
 
+static bool tryResolveInput(
+    Store & store, StorePathSet & inputSrcs, StringMap & inputRewrites,
+    const DownstreamPlaceholder * placeholderOpt,
+    const StorePath & inputDrv, const DerivedPathMap<StringSet>::ChildNode & inputNode,
+    const std::map<std::pair<StorePath, std::string>, StorePath> & inputDrvOutputs)
+{
+    auto getOutput = [&](const std::string & outputName) {
+        auto * actualPathOpt = get(inputDrvOutputs, { inputDrv, outputName });
+        if (!actualPathOpt)
+            warn("output %s of input %s missing, aborting the resolving",
+                outputName,
+                store.printStorePath(inputDrv)
+            );
+        return actualPathOpt;
+    };
+
+    auto getPlaceholder = [&](const std::string & outputName) {
+        return placeholderOpt
+            ? DownstreamPlaceholder::unknownDerivation(*placeholderOpt, outputName)
+            : DownstreamPlaceholder::unknownCaOutput(inputDrv, outputName);
+    };
+
+    for (auto & outputName : inputNode.value) {
+        auto actualPathOpt = getOutput(outputName);
+        if (!actualPathOpt) return false;
+        auto actualPath = *actualPathOpt;
+        if (experimentalFeatureSettings.isEnabled(Xp::CaDerivations)) {
+            inputRewrites.emplace(
+                getPlaceholder(outputName).render(),
+                store.printStorePath(actualPath));
+        }
+        inputSrcs.insert(std::move(actualPath));
+    }
+
+    for (auto & [outputName, childNode] : inputNode.childMap) {
+        auto actualPathOpt = getOutput(outputName);
+        if (!actualPathOpt) return false;
+        auto actualPath = *actualPathOpt;
+        auto nextPlaceholder = getPlaceholder(outputName);
+        if (!tryResolveInput(store, inputSrcs, inputRewrites,
+            &nextPlaceholder, actualPath, childNode,
+            inputDrvOutputs))
+            return false;
+    }
+    return true;
+}
+
 std::optional<BasicDerivation> Derivation::tryResolve(
     Store & store,
     const std::map<std::pair<StorePath, std::string>, StorePath> & inputDrvOutputs) const
@@ -879,23 +1078,10 @@ std::optional<BasicDerivation> Derivation::tryResolve(
     // Input paths that we'll want to rewrite in the derivation
     StringMap inputRewrites;
 
-    for (auto & [inputDrv, inputOutputs] : inputDrvs) {
-        for (auto & outputName : inputOutputs) {
-            if (auto actualPath = get(inputDrvOutputs, { inputDrv, outputName })) {
-                if (experimentalFeatureSettings.isEnabled(Xp::CaDerivations)) {
-                    inputRewrites.emplace(
-                        DownstreamPlaceholder::unknownCaOutput(inputDrv, outputName).render(),
-                        store.printStorePath(*actualPath));
-                }
-                resolved.inputSrcs.insert(*actualPath);
-            } else {
-                warn("output '%s' of input '%s' missing, aborting the resolving",
-                    outputName,
-                    store.printStorePath(inputDrv));
-                return {};
-            }
-        }
-    }
+    for (auto & [inputDrv, inputNode] : inputDrvs.map)
+        if (!tryResolveInput(store, resolved.inputSrcs, inputRewrites,
+            nullptr, inputDrv, inputNode, inputDrvOutputs))
+            return std::nullopt;
 
     rewriteDerivation(store, resolved, inputRewrites);
 
@@ -1084,10 +1270,25 @@ nlohmann::json Derivation::toJSON(const Store & store) const
     }
 
     {
-        auto& inputDrvsObj = res["inputDrvs"];
-        inputDrvsObj = nlohmann::json ::object();
-        for (auto & input : inputDrvs)
-            inputDrvsObj[store.printStorePath(input.first)] = input.second;
+        std::function<nlohmann::json(const DerivedPathMap<StringSet>::ChildNode &)> doInput;
+        doInput = [&](const auto & inputNode) {
+            auto value = nlohmann::json::object();
+            value["outputs"] = inputNode.value;
+            {
+                auto next = nlohmann::json::object();
+                for (auto & [outputId, childNode] : inputNode.childMap)
+                    next[outputId] = doInput(childNode);
+                value["dynamicOutputs"] = std::move(next);
+            }
+            return value;
+        };
+        {
+            auto& inputDrvsObj = res["inputDrvs"];
+            inputDrvsObj = nlohmann::json::object();
+            for (auto & [inputDrv, inputNode] : inputDrvs.map) {
+                inputDrvsObj[store.printStorePath(inputDrv)] = doInput(inputNode);
+            }
+        }
     }
 
     res["system"] = platform;
@@ -1101,7 +1302,8 @@ nlohmann::json Derivation::toJSON(const Store & store) const
 
 Derivation Derivation::fromJSON(
     const Store & store,
-    const nlohmann::json & json)
+    const nlohmann::json & json,
+    const ExperimentalFeatureSettings & xpSettings)
 {
     using nlohmann::detail::value_t;
 
@@ -1133,12 +1335,21 @@ Derivation Derivation::fromJSON(
     }
 
     try {
+        std::function<DerivedPathMap<StringSet>::ChildNode(const nlohmann::json &)> doInput;
+        doInput = [&](const auto & json) {
+            DerivedPathMap<StringSet>::ChildNode node;
+            node.value = static_cast<const StringSet &>(
+                ensureType(valueAt(json, "outputs"), value_t::array));
+            for (auto & [outputId, childNode] : ensureType(valueAt(json, "dynamicOutputs"), value_t::object).items()) {
+                xpSettings.require(Xp::DynamicDerivations);
+                node.childMap[outputId] = doInput(childNode);
+            }
+            return node;
+        };
         auto & inputDrvsObj = ensureType(valueAt(json, "inputDrvs"), value_t::object);
-        for (auto & [inputDrvPath, inputOutputs] : inputDrvsObj.items()) {
-            ensureType(inputOutputs, value_t::array);
-            res.inputDrvs[store.parseStorePath(inputDrvPath)] =
-                static_cast<const StringSet &>(inputOutputs);
-        }
+        for (auto & [inputDrvPath, inputOutputs] : inputDrvsObj.items())
+            res.inputDrvs.map[store.parseStorePath(inputDrvPath)] =
+                doInput(inputOutputs);
     } catch (Error & e) {
         e.addTrace({}, "while reading key 'inputDrvs'");
         throw;
diff --git a/src/libstore/derivations.hh b/src/libstore/derivations.hh
index 106056f2d..fa14e7536 100644
--- a/src/libstore/derivations.hh
+++ b/src/libstore/derivations.hh
@@ -6,7 +6,7 @@
 #include "hash.hh"
 #include "content-address.hh"
 #include "repair-flag.hh"
-#include "derived-path.hh"
+#include "derived-path-map.hh"
 #include "sync.hh"
 #include "comparator.hh"
 #include "variant-wrapper.hh"
@@ -323,13 +323,13 @@ struct Derivation : BasicDerivation
     /**
      * inputs that are sub-derivations
      */
-    DerivationInputs inputDrvs;
+    DerivedPathMap<std::set<OutputName>> inputDrvs;
 
     /**
      * Print a derivation.
      */
     std::string unparse(const Store & store, bool maskOutputs,
-        std::map<std::string, StringSet> * actualInputs = nullptr) const;
+        DerivedPathMap<StringSet>::ChildNode::Map * actualInputs = nullptr) const;
 
     /**
      * Return the underlying basic derivation but with these changes:
@@ -368,7 +368,8 @@ struct Derivation : BasicDerivation
     nlohmann::json toJSON(const Store & store) const;
     static Derivation fromJSON(
         const Store & store,
-        const nlohmann::json & json);
+        const nlohmann::json & json,
+        const ExperimentalFeatureSettings & xpSettings = experimentalFeatureSettings);
 
     GENERATE_CMP(Derivation,
         static_cast<const BasicDerivation &>(*me),
@@ -389,7 +390,11 @@ StorePath writeDerivation(Store & store,
 /**
  * Read a derivation from a file.
  */
-Derivation parseDerivation(const Store & store, std::string && s, std::string_view name);
+Derivation parseDerivation(
+    const Store & store,
+    std::string && s,
+    std::string_view name,
+    const ExperimentalFeatureSettings & xpSettings = experimentalFeatureSettings);
 
 /**
  * \todo Remove.
diff --git a/src/libstore/derived-path-map.cc b/src/libstore/derived-path-map.cc
index 5c8c7a4f2..437b6a71a 100644
--- a/src/libstore/derived-path-map.cc
+++ b/src/libstore/derived-path-map.cc
@@ -21,6 +21,32 @@ typename DerivedPathMap<V>::ChildNode & DerivedPathMap<V>::ensureSlot(const Sing
     return initIter(k);
 }
 
+template<typename V>
+typename DerivedPathMap<V>::ChildNode * DerivedPathMap<V>::findSlot(const SingleDerivedPath & k)
+{
+    std::function<ChildNode *(const SingleDerivedPath & )> initIter;
+    initIter = [&](const auto & k) {
+        return std::visit(overloaded {
+            [&](const SingleDerivedPath::Opaque & bo) {
+                auto it = map.find(bo.path);
+                return it != map.end()
+                    ? &it->second
+                    : nullptr;
+            },
+            [&](const SingleDerivedPath::Built & bfd) {
+                auto * n = initIter(*bfd.drvPath);
+                if (!n) return (ChildNode *)nullptr;
+
+                auto it = n->childMap.find(bfd.output);
+                return it != n->childMap.end()
+                    ? &it->second
+                    : nullptr;
+            },
+        }, k.raw());
+    };
+    return initIter(k);
+}
+
 }
 
 // instantiations
@@ -30,4 +56,17 @@ namespace nix {
 
 template struct DerivedPathMap<std::weak_ptr<CreateDerivationAndRealiseGoal>>;
 
-}
+GENERATE_CMP_EXT(
+    template<>,
+    DerivedPathMap<std::set<std::string>>::ChildNode,
+    me->value,
+    me->childMap);
+
+GENERATE_CMP_EXT(
+    template<>,
+    DerivedPathMap<std::set<std::string>>,
+    me->map);
+
+template struct DerivedPathMap<std::set<std::string>>;
+
+};
diff --git a/src/libstore/derived-path-map.hh b/src/libstore/derived-path-map.hh
index 9ce58206e..4a2c90733 100644
--- a/src/libstore/derived-path-map.hh
+++ b/src/libstore/derived-path-map.hh
@@ -48,6 +48,8 @@ struct DerivedPathMap {
          * The map of the root node.
          */
         Map childMap;
+
+        DECLARE_CMP(ChildNode);
     };
 
     /**
@@ -60,6 +62,8 @@ struct DerivedPathMap {
      */
     Map map;
 
+    DECLARE_CMP(DerivedPathMap);
+
     /**
      * Find the node for `k`, creating it if needed.
      *
@@ -68,6 +72,27 @@ struct DerivedPathMap {
      * by changing this node.
      */
     ChildNode & ensureSlot(const SingleDerivedPath & k);
+
+    /**
+     * Like `ensureSlot` but does not create the slot if it doesn't exist.
+     *
+     * Read the entire description of `ensureSlot` to understand an
+     * important caveat here that "have slot" does *not* imply "key is
+     * set in map". To ensure a key is set one would need to get the
+     * child node (with `findSlot` or `ensureSlot`) *and* check the
+     * `ChildNode::value`.
+     */
+    ChildNode * findSlot(const SingleDerivedPath & k);
 };
 
+
+DECLARE_CMP_EXT(
+    template<>,
+    DerivedPathMap<std::set<std::string>>::,
+    DerivedPathMap<std::set<std::string>>);
+DECLARE_CMP_EXT(
+    template<>,
+    DerivedPathMap<std::set<std::string>>::ChildNode::,
+    DerivedPathMap<std::set<std::string>>::ChildNode);
+
 }
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index c043b9b93..1035691c7 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -125,14 +125,26 @@ void Store::queryMissing(const std::vector<DerivedPath> & targets,
 
     std::function<void(DerivedPath)> doPath;
 
+    std::function<void(ref<SingleDerivedPath>, const DerivedPathMap<StringSet>::ChildNode &)> enqueueDerivedPaths;
+
+    enqueueDerivedPaths = [&](ref<SingleDerivedPath> inputDrv, const DerivedPathMap<StringSet>::ChildNode & inputNode) {
+        if (!inputNode.value.empty())
+            pool.enqueue(std::bind(doPath, DerivedPath::Built { inputDrv, inputNode.value }));
+        for (const auto & [outputName, childNode] : inputNode.childMap)
+            enqueueDerivedPaths(
+                make_ref<SingleDerivedPath>(SingleDerivedPath::Built { inputDrv, outputName }),
+                childNode);
+    };
+
     auto mustBuildDrv = [&](const StorePath & drvPath, const Derivation & drv) {
         {
             auto state(state_.lock());
             state->willBuild.insert(drvPath);
         }
 
-        for (auto & i : drv.inputDrvs)
-            pool.enqueue(std::bind(doPath, DerivedPath::Built { makeConstantStorePathRef(i.first), i.second }));
+        for (const auto & [inputDrv, inputNode] : drv.inputDrvs.map) {
+            enqueueDerivedPaths(makeConstantStorePathRef(inputDrv), inputNode);
+        }
     };
 
     auto checkOutput = [&](
@@ -322,24 +334,41 @@ std::map<DrvOutput, StorePath> drvOutputReferences(
 {
     std::set<Realisation> inputRealisations;
 
-    for (const auto & [inputDrv, outputNames] : drv.inputDrvs) {
-        const auto outputHashes =
-            staticOutputHashes(store, store.readDerivation(inputDrv));
-        for (const auto & outputName : outputNames) {
-            auto outputHash = get(outputHashes, outputName);
-            if (!outputHash)
-                throw Error(
-                    "output '%s' of derivation '%s' isn't realised", outputName,
-                    store.printStorePath(inputDrv));
-            auto thisRealisation = store.queryRealisation(
-                DrvOutput{*outputHash, outputName});
-            if (!thisRealisation)
-                throw Error(
-                    "output '%s' of derivation '%s' isn't built", outputName,
-                    store.printStorePath(inputDrv));
-            inputRealisations.insert(*thisRealisation);
+    std::function<void(const StorePath &, const DerivedPathMap<StringSet>::ChildNode &)> accumRealisations;
+
+    accumRealisations = [&](const StorePath & inputDrv, const DerivedPathMap<StringSet>::ChildNode & inputNode) {
+        if (!inputNode.value.empty()) {
+            auto outputHashes =
+                staticOutputHashes(store, store.readDerivation(inputDrv));
+            for (const auto & outputName : inputNode.value) {
+                auto outputHash = get(outputHashes, outputName);
+                if (!outputHash)
+                    throw Error(
+                        "output '%s' of derivation '%s' isn't realised", outputName,
+                        store.printStorePath(inputDrv));
+                auto thisRealisation = store.queryRealisation(
+                    DrvOutput{*outputHash, outputName});
+                if (!thisRealisation)
+                    throw Error(
+                        "output '%s' of derivation '%s' isn’t built", outputName,
+                        store.printStorePath(inputDrv));
+                inputRealisations.insert(*thisRealisation);
+            }
         }
-    }
+        if (!inputNode.value.empty()) {
+            auto d = makeConstantStorePathRef(inputDrv);
+            for (const auto & [outputName, childNode] : inputNode.childMap) {
+                SingleDerivedPath next = SingleDerivedPath::Built { d, outputName };
+                accumRealisations(
+                    // TODO deep resolutions for dynamic derivations, issue #8947, would go here.
+                    resolveDerivedPath(store, next),
+                    childNode);
+            }
+        }
+    };
+
+    for (const auto & [inputDrv, inputNode] : drv.inputDrvs.map)
+        accumRealisations(inputDrv, inputNode);
 
     auto info = store.queryPathInfo(outputPath);
 
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index 58f72beb9..a639346d1 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -172,7 +172,24 @@ void RemoteStore::ConnectionHandle::processStderr(Sink * sink, Source * source,
     auto ex = handle->processStderr(sink, source, flush);
     if (ex) {
         daemonException = true;
-        std::rethrow_exception(ex);
+        try {
+            std::rethrow_exception(ex);
+        } catch (const Error & e) {
+            // Nix versions before #4628 did not have an adequate behavior for reporting that the derivation format was upgraded.
+            // To avoid having to add compatibility logic in many places, we expect to catch almost all occurrences of the
+            // old incomprehensible error here, so that we can explain to users what's going on when their daemon is
+            // older than #4628 (2023).
+            if (experimentalFeatureSettings.isEnabled(Xp::DynamicDerivations) &&
+                GET_PROTOCOL_MINOR(handle->daemonVersion) <= 35)
+            {
+                auto m = e.msg();
+                if (m.find("parsing derivation") != std::string::npos &&
+                    m.find("expected string") != std::string::npos &&
+                    m.find("Derive([") != std::string::npos)
+                    throw Error("%s, this might be because the daemon is too old to understand dependencies on dynamic derivations. Check to see if the raw dervation is in the form '%s'", std::move(m), "DrvWithVersion(..)");
+            }
+            throw;
+        }
     }
 }
 
diff --git a/src/libstore/tests/derivation.cc b/src/libstore/tests/derivation.cc
index 7fd7f9278..c360c9707 100644
--- a/src/libstore/tests/derivation.cc
+++ b/src/libstore/tests/derivation.cc
@@ -42,6 +42,26 @@ class ImpureDerivationTest : public DerivationTest
     }
 };
 
+TEST_F(DerivationTest, BadATerm_version) {
+    ASSERT_THROW(
+        parseDerivation(
+            *store,
+            R"(DrvWithVersion("invalid-version",[],[("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv",["cat","dog"])],["/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"],"wasm-sel4","foo",["bar","baz"],[("BIG_BAD","WOLF")]))",
+            "whatever",
+            mockXpSettings),
+        FormatError);
+}
+
+TEST_F(DynDerivationTest, BadATerm_oldVersionDynDeps) {
+    ASSERT_THROW(
+        parseDerivation(
+            *store,
+            R"(Derive([],[("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv",(["cat","dog"],[("cat",["kitten"]),("goose",["gosling"])]))],["/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"],"wasm-sel4","foo",["bar","baz"],[("BIG_BAD","WOLF")]))",
+            "dyn-dep-derivation",
+            mockXpSettings),
+        FormatError);
+}
+
 #define TEST_JSON(FIXTURE, NAME, STR, VAL, DRV_NAME, OUTPUT_NAME) \
     TEST_F(FIXTURE, DerivationOutput_ ## NAME ## _to_json) {    \
         using nlohmann::literals::operator "" _json;           \
@@ -143,35 +163,37 @@ TEST_JSON(ImpureDerivationTest, impure,
 
 #undef TEST_JSON
 
-#define TEST_JSON(NAME, STR, VAL)                                \
-    TEST_F(DerivationTest, Derivation_ ## NAME ## _to_json) {    \
+#define TEST_JSON(FIXTURE, NAME, STR, VAL)                       \
+    TEST_F(FIXTURE, Derivation_ ## NAME ## _to_json) {           \
         using nlohmann::literals::operator "" _json;             \
         ASSERT_EQ(                                               \
             STR ## _json,                                        \
             (VAL).toJSON(*store));                               \
     }                                                            \
                                                                  \
-    TEST_F(DerivationTest, Derivation_ ## NAME ## _from_json) {  \
+    TEST_F(FIXTURE, Derivation_ ## NAME ## _from_json) {         \
         using nlohmann::literals::operator "" _json;             \
         ASSERT_EQ(                                               \
             (VAL),                                               \
             Derivation::fromJSON(                                \
                 *store,                                          \
-                STR ## _json));                                  \
+                STR ## _json,                                    \
+                mockXpSettings));                                \
     }
 
-#define TEST_ATERM(NAME, STR, VAL, DRV_NAME)                     \
-    TEST_F(DerivationTest, Derivation_ ## NAME ## _to_aterm) {   \
+#define TEST_ATERM(FIXTURE, NAME, STR, VAL, DRV_NAME)            \
+    TEST_F(FIXTURE, Derivation_ ## NAME ## _to_aterm) {          \
         ASSERT_EQ(                                               \
             STR,                                                 \
             (VAL).unparse(*store, false));                       \
     }                                                            \
                                                                  \
-    TEST_F(DerivationTest, Derivation_ ## NAME ## _from_aterm) { \
+    TEST_F(FIXTURE, Derivation_ ## NAME ## _from_aterm) {        \
         auto parsed = parseDerivation(                           \
-             *store,                                             \
-             STR,                                                \
-             DRV_NAME);                                          \
+            *store,                                              \
+            STR,                                                 \
+            DRV_NAME,                                            \
+            mockXpSettings);                                     \
         ASSERT_EQ(                                               \
             (VAL).toJSON(*store),                                \
             parsed.toJSON(*store));                              \
@@ -187,11 +209,15 @@ Derivation makeSimpleDrv(const Store & store) {
         store.parseStorePath("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"),
     };
     drv.inputDrvs = {
-        {
-            store.parseStorePath("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv"),
+        .map = {
             {
-                "cat",
-                "dog",
+                store.parseStorePath("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv"),
+                {
+                    .value = {
+                        "cat",
+                        "dog",
+                    },
+                },
             },
         },
     };
@@ -210,17 +236,20 @@ Derivation makeSimpleDrv(const Store & store) {
     return drv;
 }
 
-TEST_JSON(simple,
+TEST_JSON(DerivationTest, simple,
     R"({
       "name": "simple-derivation",
       "inputSrcs": [
         "/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"
       ],
       "inputDrvs": {
-        "/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv": [
-          "cat",
-          "dog"
-        ]
+        "/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv": {
+          "dynamicOutputs": {},
+          "outputs": [
+            "cat",
+            "dog"
+          ]
+        }
       },
       "system": "wasm-sel4",
       "builder": "foo",
@@ -235,11 +264,105 @@ TEST_JSON(simple,
     })",
     makeSimpleDrv(*store))
 
-TEST_ATERM(simple,
+TEST_ATERM(DerivationTest, simple,
     R"(Derive([],[("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv",["cat","dog"])],["/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"],"wasm-sel4","foo",["bar","baz"],[("BIG_BAD","WOLF")]))",
     makeSimpleDrv(*store),
     "simple-derivation")
 
+Derivation makeDynDepDerivation(const Store & store) {
+    Derivation drv;
+    drv.name = "dyn-dep-derivation";
+    drv.inputSrcs = {
+        store.parseStorePath("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"),
+    };
+    drv.inputDrvs = {
+        .map = {
+            {
+                store.parseStorePath("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv"),
+                DerivedPathMap<StringSet>::ChildNode {
+                    .value = {
+                        "cat",
+                        "dog",
+                    },
+                    .childMap = {
+                        {
+                            "cat",
+                            DerivedPathMap<StringSet>::ChildNode {
+                                .value = {
+                                    "kitten",
+                                },
+                            },
+                        },
+                        {
+                            "goose",
+                            DerivedPathMap<StringSet>::ChildNode {
+                                .value = {
+                                    "gosling",
+                                },
+                            },
+                        },
+                    },
+                },
+            },
+        },
+    };
+    drv.platform = "wasm-sel4";
+    drv.builder = "foo";
+    drv.args = {
+        "bar",
+        "baz",
+    };
+    drv.env = {
+        {
+            "BIG_BAD",
+            "WOLF",
+        },
+    };
+    return drv;
+}
+
+TEST_JSON(DynDerivationTest, dynDerivationDeps,
+    R"({
+      "name": "dyn-dep-derivation",
+      "inputSrcs": [
+        "/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"
+      ],
+      "inputDrvs": {
+        "/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv": {
+          "dynamicOutputs": {
+            "cat": {
+              "dynamicOutputs": {},
+              "outputs": ["kitten"]
+            },
+            "goose": {
+              "dynamicOutputs": {},
+              "outputs": ["gosling"]
+            }
+          },
+          "outputs": [
+            "cat",
+            "dog"
+          ]
+        }
+      },
+      "system": "wasm-sel4",
+      "builder": "foo",
+      "args": [
+        "bar",
+        "baz"
+      ],
+      "env": {
+        "BIG_BAD": "WOLF"
+      },
+      "outputs": {}
+    })",
+    makeDynDepDerivation(*store))
+
+TEST_ATERM(DynDerivationTest, dynDerivationDeps,
+    R"(DrvWithVersion("xp-dyn-drv",[],[("/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep2.drv",(["cat","dog"],[("cat",["kitten"]),("goose",["gosling"])]))],["/nix/store/c015dhfh5l0lp6wxyvdn7bmwhbbr6hr9-dep1"],"wasm-sel4","foo",["bar","baz"],[("BIG_BAD","WOLF")]))",
+    makeDynDepDerivation(*store),
+    "dyn-dep-derivation")
+
 #undef TEST_JSON
 #undef TEST_ATERM
 
diff --git a/src/libutil/comparator.hh b/src/libutil/comparator.hh
index 7982fdc5e..a4d20a675 100644
--- a/src/libutil/comparator.hh
+++ b/src/libutil/comparator.hh
@@ -1,21 +1,48 @@
 #pragma once
 ///@file
 
+#define DECLARE_ONE_CMP(PRE, QUAL, COMPARATOR, MY_TYPE) \
+    PRE bool QUAL operator COMPARATOR(const MY_TYPE & other) const;
+#define DECLARE_EQUAL(prefix, qualification, my_type) \
+    DECLARE_ONE_CMP(prefix, qualification, ==, my_type)
+#define DECLARE_LEQ(prefix, qualification, my_type) \
+    DECLARE_ONE_CMP(prefix, qualification, <, my_type)
+#define DECLARE_NEQ(prefix, qualification, my_type) \
+    DECLARE_ONE_CMP(prefix, qualification, !=, my_type)
+
+#define GENERATE_ONE_CMP(PRE, QUAL, COMPARATOR, MY_TYPE, ...) \
+    PRE bool QUAL operator COMPARATOR(const MY_TYPE & other) const { \
+      __VA_OPT__(const MY_TYPE * me = this;) \
+      auto fields1 = std::make_tuple( __VA_ARGS__ ); \
+      __VA_OPT__(me = &other;) \
+      auto fields2 = std::make_tuple( __VA_ARGS__ ); \
+      return fields1 COMPARATOR fields2; \
+    }
+#define GENERATE_EQUAL(prefix, qualification, my_type, args...) \
+    GENERATE_ONE_CMP(prefix, qualification, ==, my_type, args)
+#define GENERATE_LEQ(prefix, qualification, my_type, args...) \
+    GENERATE_ONE_CMP(prefix, qualification, <, my_type, args)
+#define GENERATE_NEQ(prefix, qualification, my_type, args...) \
+    GENERATE_ONE_CMP(prefix, qualification, !=, my_type, args)
+
 /**
  * Declare comparison methods without defining them.
  */
-#define DECLARE_ONE_CMP(COMPARATOR, MY_TYPE) \
-    bool operator COMPARATOR(const MY_TYPE & other) const;
-#define DECLARE_EQUAL(my_type) \
-    DECLARE_ONE_CMP(==, my_type)
-#define DECLARE_LEQ(my_type) \
-    DECLARE_ONE_CMP(<, my_type)
-#define DECLARE_NEQ(my_type) \
-    DECLARE_ONE_CMP(!=, my_type)
 #define DECLARE_CMP(my_type) \
-    DECLARE_EQUAL(my_type) \
-    DECLARE_LEQ(my_type) \
-    DECLARE_NEQ(my_type)
+    DECLARE_EQUAL(,,my_type) \
+    DECLARE_LEQ(,,my_type) \
+    DECLARE_NEQ(,,my_type)
+
+/**
+ * @param prefix This is for something before each declaration like
+ * `template<classname Foo>`.
+ *
+ * @param my_type the type are defining operators for.
+ */
+#define DECLARE_CMP_EXT(prefix, qualification, my_type) \
+    DECLARE_EQUAL(prefix, qualification, my_type) \
+    DECLARE_LEQ(prefix, qualification, my_type) \
+    DECLARE_NEQ(prefix, qualification, my_type)
 
 /**
  * Awful hacky generation of the comparison operators by doing a lexicographic
@@ -33,18 +60,18 @@
  * }
  * ```
  */
-#define GENERATE_ONE_CMP(COMPARATOR, MY_TYPE, ...) \
-    bool operator COMPARATOR(const MY_TYPE& other) const { \
-      __VA_OPT__(const MY_TYPE* me = this;) \
-      auto fields1 = std::make_tuple( __VA_ARGS__ ); \
-      __VA_OPT__(me = &other;) \
-      auto fields2 = std::make_tuple( __VA_ARGS__ ); \
-      return fields1 COMPARATOR fields2; \
-    }
-#define GENERATE_EQUAL(args...) GENERATE_ONE_CMP(==, args)
-#define GENERATE_LEQ(args...) GENERATE_ONE_CMP(<, args)
-#define GENERATE_NEQ(args...) GENERATE_ONE_CMP(!=, args)
 #define GENERATE_CMP(args...) \
-    GENERATE_EQUAL(args) \
-    GENERATE_LEQ(args) \
-    GENERATE_NEQ(args)
+    GENERATE_EQUAL(,,args) \
+    GENERATE_LEQ(,,args) \
+    GENERATE_NEQ(,,args)
+
+/**
+ * @param prefix This is for something before each declaration like
+ * `template<classname Foo>`.
+ *
+ * @param my_type the type are defining operators for.
+ */
+#define GENERATE_CMP_EXT(prefix, my_type, args...) \
+    GENERATE_EQUAL(prefix, my_type ::, my_type, args) \
+    GENERATE_LEQ(prefix, my_type ::, my_type, args) \
+    GENERATE_NEQ(prefix, my_type ::, my_type, args)
diff --git a/src/nix-build/nix-build.cc b/src/nix-build/nix-build.cc
index 66f319c3e..e2189fc66 100644
--- a/src/nix-build/nix-build.cc
+++ b/src/nix-build/nix-build.cc
@@ -406,8 +406,22 @@ static void main_nix_build(int argc, char * * argv)
             }
         }
 
+        std::function<void(ref<SingleDerivedPath>, const DerivedPathMap<StringSet>::ChildNode &)> accumDerivedPath;
+
+        accumDerivedPath = [&](ref<SingleDerivedPath> inputDrv, const DerivedPathMap<StringSet>::ChildNode & inputNode) {
+            if (!inputNode.value.empty())
+                pathsToBuild.push_back(DerivedPath::Built {
+                    .drvPath = inputDrv,
+                    .outputs = OutputsSpec::Names { inputNode.value },
+                });
+            for (const auto & [outputName, childNode] : inputNode.childMap)
+                accumDerivedPath(
+                    make_ref<SingleDerivedPath>(SingleDerivedPath::Built { inputDrv, outputName }),
+                    childNode);
+        };
+
         // Build or fetch all dependencies of the derivation.
-        for (const auto & [inputDrv0, inputOutputs] : drv.inputDrvs) {
+        for (const auto & [inputDrv0, inputNode] : drv.inputDrvs.map) {
             // To get around lambda capturing restrictions in the
             // standard.
             const auto & inputDrv = inputDrv0;
@@ -416,10 +430,7 @@ static void main_nix_build(int argc, char * * argv)
                         return !std::regex_search(store->printStorePath(inputDrv), std::regex(exclude));
                     }))
             {
-                pathsToBuild.push_back(DerivedPath::Built {
-                    .drvPath = makeConstantStorePathRef(inputDrv),
-                    .outputs = OutputsSpec::Names { inputOutputs },
-                });
+                accumDerivedPath(makeConstantStorePathRef(inputDrv), inputNode);
                 pathsToCopy.insert(inputDrv);
             }
         }
@@ -482,13 +493,21 @@ static void main_nix_build(int argc, char * * argv)
 
         if (env.count("__json")) {
             StorePathSet inputs;
-            for (auto & [depDrvPath, wantedDepOutputs] : drv.inputDrvs) {
-                auto outputs = evalStore->queryPartialDerivationOutputMap(depDrvPath);
-                for (auto & i : wantedDepOutputs) {
+
+            std::function<void(const StorePath &, const DerivedPathMap<StringSet>::ChildNode &)> accumInputClosure;
+
+            accumInputClosure = [&](const StorePath & inputDrv, const DerivedPathMap<StringSet>::ChildNode & inputNode) {
+                auto outputs = evalStore->queryPartialDerivationOutputMap(inputDrv);
+                for (auto & i : inputNode.value) {
                     auto o = outputs.at(i);
                     store->computeFSClosure(*o, inputs);
                 }
-            }
+                for (const auto & [outputName, childNode] : inputNode.childMap)
+                    accumInputClosure(*outputs.at(outputName), childNode);
+            };
+
+            for (const auto & [inputDrv, inputNode] : drv.inputDrvs.map)
+                accumInputClosure(inputDrv, inputNode);
 
             ParsedDerivation parsedDrv(drvInfo.requireDrvPath(), drv);
 
diff --git a/src/nix/app.cc b/src/nix/app.cc
index 67c5ef344..34fac9935 100644
--- a/src/nix/app.cc
+++ b/src/nix/app.cc
@@ -20,15 +20,22 @@ StringPairs resolveRewrites(
     const std::vector<BuiltPathWithResult> & dependencies)
 {
     StringPairs res;
-    for (auto & dep : dependencies)
-        if (auto drvDep = std::get_if<BuiltPathBuilt>(&dep.path))
-            if (experimentalFeatureSettings.isEnabled(Xp::CaDerivations))
-                for (auto & [ outputName, outputPath ] : drvDep->outputs)
+    if (experimentalFeatureSettings.isEnabled(Xp::CaDerivations)) {
+        for (auto & dep : dependencies) {
+            if (auto drvDep = std::get_if<BuiltPathBuilt>(&dep.path)) {
+                for (auto & [ outputName, outputPath ] : drvDep->outputs) {
                     res.emplace(
-                        DownstreamPlaceholder::unknownCaOutput(
-                            drvDep->drvPath->outPath(), outputName).render(),
+                        DownstreamPlaceholder::fromSingleDerivedPathBuilt(
+                            SingleDerivedPath::Built {
+                                .drvPath = make_ref<SingleDerivedPath>(drvDep->drvPath->discardOutputPath()),
+                                .output = outputName,
+                            }).render(),
                         store.printStorePath(outputPath)
                     );
+                }
+            }
+        }
+    }
     return res;
 }
 
diff --git a/tests/dyn-drv/dep-built-drv.sh b/tests/dyn-drv/dep-built-drv.sh
index 8c4a45e3b..c3daf2c59 100644
--- a/tests/dyn-drv/dep-built-drv.sh
+++ b/tests/dyn-drv/dep-built-drv.sh
@@ -6,4 +6,6 @@ out1=$(nix-build ./text-hashed-output.nix -A hello --no-out-link)
 
 clearStore
 
-expectStderr 1 nix-build ./text-hashed-output.nix -A wrapper --no-out-link | grepQuiet "Dependencies on the outputs of dynamic derivations are not yet supported"
+out2=$(nix-build ./text-hashed-output.nix -A wrapper --no-out-link)
+
+diff -r $out1 $out2
diff --git a/tests/dyn-drv/local.mk b/tests/dyn-drv/local.mk
index 0ce7cd37d..6b435499b 100644
--- a/tests/dyn-drv/local.mk
+++ b/tests/dyn-drv/local.mk
@@ -3,7 +3,8 @@ dyn-drv-tests := \
   $(d)/recursive-mod-json.sh \
   $(d)/build-built-drv.sh \
   $(d)/eval-outputOf.sh \
-  $(d)/dep-built-drv.sh
+  $(d)/dep-built-drv.sh \
+  $(d)/old-daemon-error-hack.sh
 
 install-tests-groups += dyn-drv
 
diff --git a/tests/dyn-drv/old-daemon-error-hack.nix b/tests/dyn-drv/old-daemon-error-hack.nix
new file mode 100644
index 000000000..c9d4a62d4
--- /dev/null
+++ b/tests/dyn-drv/old-daemon-error-hack.nix
@@ -0,0 +1,20 @@
+with import ./config.nix;
+
+# 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 {
+  stub = mkDerivation {
+    name = "stub";
+    buildCommand = ''
+      echo stub > $out
+    '';
+  };
+  wrapper = mkDerivation {
+    name = "has-dynamic-drv-dep";
+    buildCommand = ''
+      exit 1 # we're not building this derivation
+      ${builtins.outputOf stub.outPath "out"}
+    '';
+  };
+}
diff --git a/tests/dyn-drv/old-daemon-error-hack.sh b/tests/dyn-drv/old-daemon-error-hack.sh
new file mode 100644
index 000000000..43b049973
--- /dev/null
+++ b/tests/dyn-drv/old-daemon-error-hack.sh
@@ -0,0 +1,11 @@
+# Purposely bypassing our usual common for this subgroup
+source ../common.sh
+
+# Need backend to support text-hashing too
+isDaemonNewer "2.18.0pre20230906" && skipTest "Daemon is too new"
+
+enableFeatures "ca-derivations dynamic-derivations"
+
+restartDaemon
+
+expectStderr 1 nix-instantiate --read-write-mode ./old-daemon-error-hack.nix | grepQuiet "the daemon is too old to understand dependencies on dynamic derivations"