Make the Derived Path family of types inductive for dynamic derivations

We want to be able to write down `foo.drv^bar.drv^baz`:
`foo.drv^bar.drv` is the dynamic derivation (since it is itself a
derivation output, `bar.drv` from `foo.drv`).

To that end, we create `Single{Derivation,BuiltPath}` types, that are
very similar except instead of having multiple outputs (in a set or
map), they have a single one. This is for everything to the left of the
rightmost `^`.

`NixStringContextElem` has an analogous change, and now can reuse
`SingleDerivedPath` at the top level. In fact, if we ever get rid of
`DrvDeep`, `NixStringContextElem` could be replaced with
`SingleDerivedPath` entirely!

Important note: some JSON formats have changed.

We already can *produce* dynamic derivations, but we can't refer to them
directly. Today, we can merely express building or example at the top
imperatively over time by building `foo.drv^bar.drv`, and then with a
second nix invocation doing `<result-from-first>^baz`, but this is not
declarative. The ethos of Nix of being able to write down the full plan
everything you want to do, and then execute than plan with a single
command, and for that we need the new inductive form of these types.

Co-authored-by: Robert Hensing <roberth@users.noreply.github.com>
Co-authored-by: Valentin Gagarin <valentin.gagarin@tweag.io>

8 files changed, 157 insertions, 29 deletions

diff --git a/src/libcmd/built-path.cc b/src/libcmd/built-path.cc
index db9c440e3..c6cc7fa9c 100644
--- a/src/libcmd/built-path.cc
+++ b/src/libcmd/built-path.cc
@@ -8,13 +8,39 @@
 
 namespace nix {
 
-nlohmann::json BuiltPath::Built::toJSON(ref<Store> store) const {
-    nlohmann::json res;
-    res["drvPath"] = store->printStorePath(drvPath);
-    for (const auto& [output, path] : outputs) {
-        res["outputs"][output] = store->printStorePath(path);
+#define CMP_ONE(CHILD_TYPE, MY_TYPE, FIELD, COMPARATOR) \
+    bool MY_TYPE ::operator COMPARATOR (const MY_TYPE & other) const \
+    { \
+        const MY_TYPE* me = this; \
+        auto fields1 = std::make_tuple<const CHILD_TYPE &, const FIELD_TYPE &>(*me->drvPath, me->FIELD); \
+        me = &other; \
+        auto fields2 = std::make_tuple<const CHILD_TYPE &, const FIELD_TYPE &>(*me->drvPath, me->FIELD); \
+        return fields1 COMPARATOR fields2; \
     }
-    return res;
+#define CMP(CHILD_TYPE, MY_TYPE, FIELD) \
+    CMP_ONE(CHILD_TYPE, MY_TYPE, FIELD, ==) \
+    CMP_ONE(CHILD_TYPE, MY_TYPE, FIELD, !=) \
+    CMP_ONE(CHILD_TYPE, MY_TYPE, FIELD, <)
+
+#define FIELD_TYPE std::pair<std::string, StorePath>
+CMP(SingleBuiltPath, SingleBuiltPathBuilt, output)
+#undef FIELD_TYPE
+
+#define FIELD_TYPE std::map<std::string, StorePath>
+CMP(SingleBuiltPath, BuiltPathBuilt, outputs)
+#undef FIELD_TYPE
+
+#undef CMP
+#undef CMP_ONE
+
+StorePath SingleBuiltPath::outPath() const
+{
+    return std::visit(
+        overloaded{
+            [](const SingleBuiltPath::Opaque & p) { return p.path; },
+            [](const SingleBuiltPath::Built & b) { return b.output.second; },
+        }, raw()
+    );
 }
 
 StorePathSet BuiltPath::outPaths() const
@@ -32,6 +58,40 @@ StorePathSet BuiltPath::outPaths() const
     );
 }
 
+nlohmann::json BuiltPath::Built::toJSON(const Store & store) const
+{
+    nlohmann::json res;
+    res["drvPath"] = drvPath->toJSON(store);
+    for (const auto & [outputName, outputPath] : outputs) {
+        res["outputs"][outputName] = store.printStorePath(outputPath);
+    }
+    return res;
+}
+
+nlohmann::json SingleBuiltPath::Built::toJSON(const Store & store) const
+{
+    nlohmann::json res;
+    res["drvPath"] = drvPath->toJSON(store);
+    auto & [outputName, outputPath] = output;
+    res["output"] = outputName;
+    res["outputPath"] = store.printStorePath(outputPath);
+    return res;
+}
+
+nlohmann::json SingleBuiltPath::toJSON(const Store & store) const
+{
+    return std::visit([&](const auto & buildable) {
+        return buildable.toJSON(store);
+    }, raw());
+}
+
+nlohmann::json BuiltPath::toJSON(const Store & store) const
+{
+    return std::visit([&](const auto & buildable) {
+        return buildable.toJSON(store);
+    }, raw());
+}
+
 RealisedPath::Set BuiltPath::toRealisedPaths(Store & store) const
 {
     RealisedPath::Set res;
@@ -40,7 +100,7 @@ RealisedPath::Set BuiltPath::toRealisedPaths(Store & store) const
             [&](const BuiltPath::Opaque & p) { res.insert(p.path); },
             [&](const BuiltPath::Built & p) {
                 auto drvHashes =
-                    staticOutputHashes(store, store.readDerivation(p.drvPath));
+                    staticOutputHashes(store, store.readDerivation(p.drvPath->outPath()));
                 for (auto& [outputName, outputPath] : p.outputs) {
                     if (experimentalFeatureSettings.isEnabled(
                                 Xp::CaDerivations)) {
@@ -48,7 +108,7 @@ RealisedPath::Set BuiltPath::toRealisedPaths(Store & store) const
                         if (!drvOutput)
                             throw Error(
                                 "the derivation '%s' has unrealised output '%s' (derived-path.cc/toRealisedPaths)",
-                                store.printStorePath(p.drvPath), outputName);
+                                store.printStorePath(p.drvPath->outPath()), outputName);
                         auto thisRealisation = store.queryRealisation(
                             DrvOutput{*drvOutput, outputName});
                         assert(thisRealisation);  // We’ve built it, so we must
diff --git a/src/libcmd/built-path.hh b/src/libcmd/built-path.hh
index 744e8090b..747bcc440 100644
--- a/src/libcmd/built-path.hh
+++ b/src/libcmd/built-path.hh
@@ -3,19 +3,60 @@
 
 namespace nix {
 
+struct SingleBuiltPath;
+
+struct SingleBuiltPathBuilt {
+    ref<SingleBuiltPath> drvPath;
+    std::pair<std::string, StorePath> output;
+
+    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;
+
+    DECLARE_CMP(SingleBuiltPathBuilt);
+};
+
+using _SingleBuiltPathRaw = std::variant<
+    DerivedPathOpaque,
+    SingleBuiltPathBuilt
+>;
+
+struct SingleBuiltPath : _SingleBuiltPathRaw {
+    using Raw = _SingleBuiltPathRaw;
+    using Raw::Raw;
+
+    using Opaque = DerivedPathOpaque;
+    using Built = SingleBuiltPathBuilt;
+
+    inline const Raw & raw() const {
+        return static_cast<const Raw &>(*this);
+    }
+
+    StorePath outPath() const;
+
+    static SingleBuiltPath parse(const Store & store, std::string_view);
+    nlohmann::json toJSON(const Store & store) const;
+};
+
+static inline ref<SingleBuiltPath> staticDrv(StorePath drvPath)
+{
+    return make_ref<SingleBuiltPath>(SingleBuiltPath::Opaque { drvPath });
+}
+
 /**
  * A built derived path with hints in the form of optional concrete output paths.
  *
  * See 'BuiltPath' for more an explanation.
  */
 struct BuiltPathBuilt {
-    StorePath drvPath;
+    ref<SingleBuiltPath> drvPath;
     std::map<std::string, StorePath> outputs;
 
-    nlohmann::json toJSON(ref<Store> store) const;
-    static BuiltPathBuilt parse(const Store & store, std::string_view);
+    std::string to_string(const Store & store) const;
+    static BuiltPathBuilt parse(const Store & store, std::string_view, std::string_view);
+    nlohmann::json toJSON(const Store & store) const;
 
-    GENERATE_CMP(BuiltPathBuilt, me->drvPath, me->outputs);
+    DECLARE_CMP(BuiltPathBuilt);
 };
 
 using _BuiltPathRaw = std::variant<
@@ -41,6 +82,7 @@ struct BuiltPath : _BuiltPathRaw {
     StorePathSet outPaths() const;
     RealisedPath::Set toRealisedPaths(Store & store) const;
 
+    nlohmann::json toJSON(const Store & store) const;
 };
 
 typedef std::vector<BuiltPath> BuiltPaths;
diff --git a/src/libcmd/installable-attr-path.cc b/src/libcmd/installable-attr-path.cc
index b35ca2910..2f89eee02 100644
--- a/src/libcmd/installable-attr-path.cc
+++ b/src/libcmd/installable-attr-path.cc
@@ -92,7 +92,7 @@ DerivedPathsWithInfo InstallableAttrPath::toDerivedPaths()
     for (auto & [drvPath, outputs] : byDrvPath)
         res.push_back({
             .path = DerivedPath::Built {
-                .drvPath = drvPath,
+                .drvPath = makeConstantStorePathRef(drvPath),
                 .outputs = outputs,
             },
             .info = make_ref<ExtraPathInfoValue>(ExtraPathInfoValue::Value {
diff --git a/src/libcmd/installable-derived-path.cc b/src/libcmd/installable-derived-path.cc
index 6ecf54b7c..b45641e8a 100644
--- a/src/libcmd/installable-derived-path.cc
+++ b/src/libcmd/installable-derived-path.cc
@@ -18,14 +18,7 @@ DerivedPathsWithInfo InstallableDerivedPath::toDerivedPaths()
 
 std::optional<StorePath> InstallableDerivedPath::getStorePath()
 {
-    return std::visit(overloaded {
-        [&](const DerivedPath::Built & bfd) {
-            return bfd.drvPath;
-        },
-        [&](const DerivedPath::Opaque & bo) {
-            return bo.path;
-        },
-    }, derivedPath.raw());
+    return derivedPath.getBaseStorePath();
 }
 
 InstallableDerivedPath InstallableDerivedPath::parse(
@@ -42,7 +35,7 @@ InstallableDerivedPath InstallableDerivedPath::parse(
             // Remove this prior to stabilizing the new CLI.
             if (storePath.isDerivation()) {
                 auto oldDerivedPath = DerivedPath::Built {
-                    .drvPath = storePath,
+                    .drvPath = makeConstantStorePathRef(storePath),
                     .outputs = OutputsSpec::All { },
                 };
                 warn(
@@ -55,8 +48,10 @@ InstallableDerivedPath InstallableDerivedPath::parse(
         },
         // If the user did use ^, we just do exactly what is written.
         [&](const ExtendedOutputsSpec::Explicit & outputSpec) -> DerivedPath {
+            auto drv = make_ref<SingleDerivedPath>(SingleDerivedPath::parse(*store, prefix));
+            drvRequireExperiment(*drv);
             return DerivedPath::Built {
-                .drvPath = store->parseStorePath(prefix),
+                .drvPath = std::move(drv),
                 .outputs = outputSpec,
             };
         },
diff --git a/src/libcmd/installable-flake.cc b/src/libcmd/installable-flake.cc
index 4da9b131b..1b169c3bd 100644
--- a/src/libcmd/installable-flake.cc
+++ b/src/libcmd/installable-flake.cc
@@ -118,7 +118,7 @@ DerivedPathsWithInfo InstallableFlake::toDerivedPaths()
 
     return {{
         .path = DerivedPath::Built {
-            .drvPath = std::move(drvPath),
+            .drvPath = makeConstantStorePathRef(std::move(drvPath)),
             .outputs = std::visit(overloaded {
                 [&](const ExtendedOutputsSpec::Default & d) -> OutputsSpec {
                     std::set<std::string> outputsToInstall;
diff --git a/src/libcmd/installable-value.cc b/src/libcmd/installable-value.cc
index 1eff293cc..08ad35105 100644
--- a/src/libcmd/installable-value.cc
+++ b/src/libcmd/installable-value.cc
@@ -55,7 +55,8 @@ std::optional<DerivedPathWithInfo> InstallableValue::trySinglePathToDerivedPaths
 
     else if (v.type() == nString) {
         return {{
-            .path = state->coerceToDerivedPath(pos, v, errorCtx),
+            .path = DerivedPath::fromSingle(
+                state->coerceToSingleDerivedPath(pos, v, errorCtx)),
             .info = make_ref<ExtraPathInfo>(),
         }};
     }
diff --git a/src/libcmd/installables.cc b/src/libcmd/installables.cc
index 9d593a01f..4c7d134ec 100644
--- a/src/libcmd/installables.cc
+++ b/src/libcmd/installables.cc
@@ -515,6 +515,30 @@ ref<Installable> SourceExprCommand::parseInstallable(
     return installables.front();
 }
 
+static SingleBuiltPath getBuiltPath(ref<Store> evalStore, ref<Store> store, const SingleDerivedPath & b)
+{
+    return std::visit(
+        overloaded{
+            [&](const SingleDerivedPath::Opaque & bo) -> SingleBuiltPath {
+                return SingleBuiltPath::Opaque { bo.path };
+            },
+            [&](const SingleDerivedPath::Built & bfd) -> SingleBuiltPath {
+                auto drvPath = getBuiltPath(evalStore, store, *bfd.drvPath);
+                // Resolving this instead of `bfd` will yield the same result, but avoid duplicative work.
+                SingleDerivedPath::Built truncatedBfd {
+                    .drvPath = makeConstantStorePathRef(drvPath.outPath()),
+                    .output = bfd.output,
+                };
+                auto outputPath = resolveDerivedPath(*store, truncatedBfd, &*evalStore);
+                return SingleBuiltPath::Built {
+                    .drvPath = make_ref<SingleBuiltPath>(std::move(drvPath)),
+                    .output = { bfd.output, outputPath },
+                };
+            },
+        },
+        b.raw());
+}
+
 std::vector<BuiltPathWithResult> Installable::build(
     ref<Store> evalStore,
     ref<Store> store,
@@ -568,7 +592,10 @@ std::vector<std::pair<ref<Installable>, BuiltPathWithResult>> Installable::build
                     [&](const DerivedPath::Built & bfd) {
                         auto outputs = resolveDerivedPath(*store, bfd, &*evalStore);
                         res.push_back({aux.installable, {
-                            .path = BuiltPath::Built { bfd.drvPath, outputs },
+                            .path = BuiltPath::Built {
+                                .drvPath = make_ref<SingleBuiltPath>(getBuiltPath(evalStore, store, *bfd.drvPath)),
+                                .outputs = outputs,
+                             },
                             .info = aux.info}});
                     },
                     [&](const DerivedPath::Opaque & bo) {
@@ -597,7 +624,10 @@ std::vector<std::pair<ref<Installable>, BuiltPathWithResult>> Installable::build
                         for (auto & [outputName, realisation] : buildResult.builtOutputs)
                             outputs.emplace(outputName, realisation.outPath);
                         res.push_back({aux.installable, {
-                            .path = BuiltPath::Built { bfd.drvPath, outputs },
+                            .path = BuiltPath::Built {
+                                .drvPath = make_ref<SingleBuiltPath>(getBuiltPath(evalStore, store, *bfd.drvPath)),
+                                .outputs = outputs,
+                            },
                             .info = aux.info,
                             .result = buildResult}});
                     },
@@ -691,7 +721,7 @@ StorePathSet Installable::toDerivations(
                         : throw Error("argument '%s' did not evaluate to a derivation", i->what()));
                 },
                 [&](const DerivedPath::Built & bfd) {
-                    drvPaths.insert(bfd.drvPath);
+                    drvPaths.insert(resolveDerivedPath(*store, *bfd.drvPath));
                 },
             }, b.path.raw());
 
diff --git a/src/libcmd/repl.cc b/src/libcmd/repl.cc
index d15162e76..ea7d0e2ec 100644
--- a/src/libcmd/repl.cc
+++ b/src/libcmd/repl.cc
@@ -648,7 +648,7 @@ bool NixRepl::processLine(std::string line)
         if (command == ":b" || command == ":bl") {
             state->store->buildPaths({
                 DerivedPath::Built {
-                    .drvPath = drvPath,
+                    .drvPath = makeConstantStorePathRef(drvPath),
                     .outputs = OutputsSpec::All { },
                 },
             });