20 files changed, 496 insertions, 124 deletions

diff --git a/src/libstore/build/derivation-goal.cc b/src/libstore/build/derivation-goal.cc
index 2e7be517e..3ce538f77 100644
--- a/src/libstore/build/derivation-goal.cc
+++ b/src/libstore/build/derivation-goal.cc
@@ -73,7 +73,7 @@ DerivationGoal::DerivationGoal(const StorePath & drvPath,
     state = &DerivationGoal::getDerivation;
     name = fmt(
         "building of '%s' from .drv file",
-        StorePathWithOutputs { drvPath, wantedOutputs }.to_string(worker.store));
+        DerivedPath::Built { drvPath, wantedOutputs }.to_string(worker.store));
     trace("created");
 
     mcExpectedBuilds = std::make_unique<MaintainCount<uint64_t>>(worker.expectedBuilds);
@@ -94,7 +94,7 @@ DerivationGoal::DerivationGoal(const StorePath & drvPath, const BasicDerivation
     state = &DerivationGoal::haveDerivation;
     name = fmt(
         "building of '%s' from in-memory derivation",
-        StorePathWithOutputs { drvPath, drv.outputNames() }.to_string(worker.store));
+        DerivedPath::Built { drvPath, drv.outputNames() }.to_string(worker.store));
     trace("created");
 
     mcExpectedBuilds = std::make_unique<MaintainCount<uint64_t>>(worker.expectedBuilds);
diff --git a/src/libstore/build/entry-points.cc b/src/libstore/build/entry-points.cc
index 686364440..732d4785d 100644
--- a/src/libstore/build/entry-points.cc
+++ b/src/libstore/build/entry-points.cc
@@ -6,16 +6,20 @@
 
 namespace nix {
 
-void Store::buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode)
+void Store::buildPaths(const std::vector<DerivedPath> & reqs, BuildMode buildMode)
 {
     Worker worker(*this);
 
     Goals goals;
-    for (auto & path : drvPaths) {
-        if (path.path.isDerivation())
-            goals.insert(worker.makeDerivationGoal(path.path, path.outputs, buildMode));
-        else
-            goals.insert(worker.makePathSubstitutionGoal(path.path, buildMode == bmRepair ? Repair : NoRepair));
+    for (auto & br : reqs) {
+        std::visit(overloaded {
+            [&](DerivedPath::Built bfd) {
+                goals.insert(worker.makeDerivationGoal(bfd.drvPath, bfd.outputs, buildMode));
+            },
+            [&](DerivedPath::Opaque bo) {
+                goals.insert(worker.makePathSubstitutionGoal(bo.path, buildMode == bmRepair ? Repair : NoRepair));
+            },
+        }, br.raw());
     }
 
     worker.run(goals);
diff --git a/src/libstore/build/local-derivation-goal.cc b/src/libstore/build/local-derivation-goal.cc
index 8ef43c225..7c1402918 100644
--- a/src/libstore/build/local-derivation-goal.cc
+++ b/src/libstore/build/local-derivation-goal.cc
@@ -1190,6 +1190,26 @@ void LocalDerivationGoal::writeStructuredAttrs()
     chownToBuilder(tmpDir + "/.attrs.sh");
 }
 
+
+static StorePath pathPartOfReq(const DerivedPath & req)
+{
+    return std::visit(overloaded {
+        [&](DerivedPath::Opaque bo) {
+            return bo.path;
+        },
+        [&](DerivedPath::Built bfd)  {
+            return bfd.drvPath;
+        },
+    }, req.raw());
+}
+
+
+bool LocalDerivationGoal::isAllowed(const DerivedPath & req)
+{
+    return this->isAllowed(pathPartOfReq(req));
+}
+
+
 struct RestrictedStoreConfig : virtual LocalFSStoreConfig
 {
     using LocalFSStoreConfig::LocalFSStoreConfig;
@@ -1312,25 +1332,27 @@ struct RestrictedStore : public virtual RestrictedStoreConfig, public virtual Lo
     // an allowed derivation
     { throw Error("queryRealisation"); }
 
-    void buildPaths(const std::vector<StorePathWithOutputs> & paths, BuildMode buildMode) override
+    void buildPaths(const std::vector<DerivedPath> & paths, BuildMode buildMode) override
     {
         if (buildMode != bmNormal) throw Error("unsupported build mode");
 
         StorePathSet newPaths;
 
-        for (auto & path : paths) {
-            if (!goal.isAllowed(path.path))
-                throw InvalidPath("cannot build unknown path '%s' in recursive Nix", printStorePath(path.path));
+        for (auto & req : paths) {
+            if (!goal.isAllowed(req))
+                throw InvalidPath("cannot build '%s' in recursive Nix because path is unknown", req.to_string(*next));
         }
 
         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);
+            auto p =  std::get_if<DerivedPath::Built>(&path);
+            if (!p) continue;
+            auto & bfd = *p;
+            auto outputs = next->queryDerivationOutputMap(bfd.drvPath);
+            for (auto & [outputName, outputPath] : outputs)
+                if (wantOutput(outputName, bfd.outputs))
+                    newPaths.insert(outputPath);
         }
 
         StorePathSet closure;
@@ -1358,7 +1380,7 @@ struct RestrictedStore : public virtual RestrictedStoreConfig, public virtual Lo
     void addSignatures(const StorePath & storePath, const StringSet & sigs) override
     { unsupported("addSignatures"); }
 
-    void queryMissing(const std::vector<StorePathWithOutputs> & targets,
+    void queryMissing(const std::vector<DerivedPath> & targets,
         StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
         uint64_t & downloadSize, uint64_t & narSize) override
     {
@@ -1366,12 +1388,12 @@ struct RestrictedStore : public virtual RestrictedStoreConfig, public virtual Lo
            client about what paths will be built/substituted or are
            already present. Probably not a big deal. */
 
-        std::vector<StorePathWithOutputs> allowed;
-        for (auto & path : targets) {
-            if (goal.isAllowed(path.path))
-                allowed.emplace_back(path);
+        std::vector<DerivedPath> allowed;
+        for (auto & req : targets) {
+            if (goal.isAllowed(req))
+                allowed.emplace_back(req);
             else
-                unknown.insert(path.path);
+                unknown.insert(pathPartOfReq(req));
         }
 
         next->queryMissing(allowed, willBuild, willSubstitute,
diff --git a/src/libstore/build/local-derivation-goal.hh b/src/libstore/build/local-derivation-goal.hh
index 47b818a8b..d30be2351 100644
--- a/src/libstore/build/local-derivation-goal.hh
+++ b/src/libstore/build/local-derivation-goal.hh
@@ -116,6 +116,7 @@ struct LocalDerivationGoal : public DerivationGoal
     {
         return inputPaths.count(path) || addedPaths.count(path);
     }
+    bool isAllowed(const DerivedPath & req);
 
     friend struct RestrictedStore;
 
diff --git a/src/libstore/build/worker.cc b/src/libstore/build/worker.cc
index 616b17e61..6c04d3ed3 100644
--- a/src/libstore/build/worker.cc
+++ b/src/libstore/build/worker.cc
@@ -226,14 +226,14 @@ void Worker::waitForAWhile(GoalPtr goal)
 
 void Worker::run(const Goals & _topGoals)
 {
-    std::vector<nix::StorePathWithOutputs> topPaths;
+    std::vector<nix::DerivedPath> topPaths;
 
     for (auto & i : _topGoals) {
         topGoals.insert(i);
         if (auto goal = dynamic_cast<DerivationGoal *>(i.get())) {
-            topPaths.push_back({goal->drvPath, goal->wantedOutputs});
+            topPaths.push_back(DerivedPath::Built{goal->drvPath, goal->wantedOutputs});
         } else if (auto goal = dynamic_cast<PathSubstitutionGoal *>(i.get())) {
-            topPaths.push_back({goal->storePath});
+            topPaths.push_back(DerivedPath::Opaque{goal->storePath});
         }
     }
 
diff --git a/src/libstore/daemon.cc b/src/libstore/daemon.cc
index f28ab6438..affd60472 100644
--- a/src/libstore/daemon.cc
+++ b/src/libstore/daemon.cc
@@ -2,6 +2,7 @@
 #include "monitor-fd.hh"
 #include "worker-protocol.hh"
 #include "store-api.hh"
+#include "path-with-outputs.hh"
 #include "finally.hh"
 #include "affinity.hh"
 #include "archive.hh"
@@ -259,6 +260,18 @@ static void writeValidPathInfo(
     }
 }
 
+static std::vector<DerivedPath> readDerivedPaths(Store & store, unsigned int clientVersion, Source & from)
+{
+    std::vector<DerivedPath> reqs;
+    if (GET_PROTOCOL_MINOR(clientVersion) >= 29) {
+        reqs = worker_proto::read(store, from, Phantom<std::vector<DerivedPath>> {});
+    } else {
+        for (auto & s : readStrings<Strings>(from))
+            reqs.push_back(parsePathWithOutputs(store, s).toDerivedPath());
+    }
+    return reqs;
+}
+
 static void performOp(TunnelLogger * logger, ref<Store> store,
     TrustedFlag trusted, RecursiveFlag recursive, unsigned int clientVersion,
     Source & from, BufferedSink & to, unsigned int op)
@@ -493,9 +506,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
     }
 
     case wopBuildPaths: {
-        std::vector<StorePathWithOutputs> drvs;
-        for (auto & s : readStrings<Strings>(from))
-            drvs.push_back(store->parsePathWithOutputs(s));
+        auto drvs = readDerivedPaths(*store, clientVersion, from);
         BuildMode mode = bmNormal;
         if (GET_PROTOCOL_MINOR(clientVersion) >= 15) {
             mode = (BuildMode) readInt(from);
@@ -859,9 +870,7 @@ static void performOp(TunnelLogger * logger, ref<Store> store,
     }
 
     case wopQueryMissing: {
-        std::vector<StorePathWithOutputs> targets;
-        for (auto & s : readStrings<Strings>(from))
-            targets.push_back(store->parsePathWithOutputs(s));
+        auto targets = readDerivedPaths(*store, clientVersion, from);
         logger->startWork();
         StorePathSet willBuild, willSubstitute, unknown;
         uint64_t downloadSize, narSize;
diff --git a/src/libstore/derivations.cc b/src/libstore/derivations.cc
index fe98182bb..f6defd98f 100644
--- a/src/libstore/derivations.cc
+++ b/src/libstore/derivations.cc
@@ -590,14 +590,6 @@ std::map<std::string, Hash> staticOutputHashes(Store& store, const Derivation& d
 }
 
 
-std::string StorePathWithOutputs::to_string(const Store & store) const
-{
-    return outputs.empty()
-        ? store.printStorePath(path)
-        : store.printStorePath(path) + "!" + concatStringsSep(",", outputs);
-}
-
-
 bool wantOutput(const string & output, const std::set<string> & wanted)
 {
     return wanted.empty() || wanted.find(output) != wanted.end();
diff --git a/src/libstore/derived-path.cc b/src/libstore/derived-path.cc
new file mode 100644
index 000000000..13833c58e
--- /dev/null
+++ b/src/libstore/derived-path.cc
@@ -0,0 +1,77 @@
+#include "derived-path.hh"
+#include "store-api.hh"
+
+#include <nlohmann/json.hpp>
+
+namespace nix {
+
+nlohmann::json DerivedPath::Opaque::toJSON(ref<Store> store) const {
+    nlohmann::json res;
+    res["path"] = store->printStorePath(path);
+    return res;
+}
+
+nlohmann::json DerivedPathWithHints::Built::toJSON(ref<Store> store) const {
+    nlohmann::json res;
+    res["drvPath"] = store->printStorePath(drvPath);
+    for (const auto& [output, path] : outputs) {
+        res["outputs"][output] = path ? store->printStorePath(*path) : "";
+    }
+    return res;
+}
+
+nlohmann::json derivedPathsWithHintsToJSON(const DerivedPathsWithHints & buildables, ref<Store> store) {
+    auto res = nlohmann::json::array();
+    for (const DerivedPathWithHints & buildable : buildables) {
+        std::visit([&res, store](const auto & buildable) {
+            res.push_back(buildable.toJSON(store));
+        }, buildable.raw());
+    }
+    return res;
+}
+
+
+std::string DerivedPath::Opaque::to_string(const Store & store) const {
+    return store.printStorePath(path);
+}
+
+std::string DerivedPath::Built::to_string(const Store & store) const {
+    return store.printStorePath(drvPath)
+        + "!"
+        + (outputs.empty() ? std::string { "*" } : concatStringsSep(",", outputs));
+}
+
+std::string DerivedPath::to_string(const Store & store) const
+{
+    return std::visit(
+        [&](const auto & req) { return req.to_string(store); },
+        this->raw());
+}
+
+
+DerivedPath::Opaque DerivedPath::Opaque::parse(const Store & store, std::string_view s)
+{
+    return {store.parseStorePath(s)};
+}
+
+DerivedPath::Built DerivedPath::Built::parse(const Store & store, std::string_view s)
+{
+    size_t n = s.find("!");
+    assert(n != s.npos);
+    auto drvPath = store.parseStorePath(s.substr(0, n));
+    auto outputsS = s.substr(n + 1);
+    std::set<string> outputs;
+    if (outputsS != "*")
+        outputs = tokenizeString<std::set<string>>(outputsS);
+    return {drvPath, outputs};
+}
+
+DerivedPath DerivedPath::parse(const Store & store, std::string_view s)
+{
+    size_t n = s.find("!");
+    return n == s.npos
+        ? (DerivedPath) DerivedPath::Opaque::parse(store, s)
+        : (DerivedPath) DerivedPath::Built::parse(store, s);
+}
+
+}
diff --git a/src/libstore/derived-path.hh b/src/libstore/derived-path.hh
new file mode 100644
index 000000000..7a2fe59de
--- /dev/null
+++ b/src/libstore/derived-path.hh
@@ -0,0 +1,129 @@
+#pragma once
+
+#include "util.hh"
+#include "path.hh"
+
+#include <optional>
+
+#include <nlohmann/json_fwd.hpp>
+
+namespace nix {
+
+class Store;
+
+/**
+ * An opaque derived path.
+ *
+ * Opaque derived paths are just store paths, and fully evaluated. They
+ * cannot be simplified further. Since they are opaque, they cannot be
+ * built, but they can fetched.
+ */
+struct DerivedPathOpaque {
+    StorePath path;
+
+    nlohmann::json toJSON(ref<Store> store) const;
+    std::string to_string(const Store & store) const;
+    static DerivedPathOpaque parse(const Store & store, std::string_view);
+};
+
+/**
+ * A derived path that is built from a derivation
+ *
+ * Built derived paths are pair of a derivation and some output names.
+ * They are evaluated by building the derivation, and then replacing the
+ * output names with the resulting outputs.
+ *
+ * Note that does mean a derived store paths evaluates to multiple
+ * opaque paths, which is sort of icky as expressions are supposed to
+ * evaluate to single values. Perhaps this should have just a single
+ * output name.
+ */
+struct DerivedPathBuilt {
+    StorePath drvPath;
+    std::set<std::string> outputs;
+
+    std::string to_string(const Store & store) const;
+    static DerivedPathBuilt parse(const Store & store, std::string_view);
+};
+
+using _DerivedPathRaw = std::variant<
+    DerivedPathOpaque,
+    DerivedPathBuilt
+>;
+
+/**
+ * A "derived path" is a very simple sort of expression that evaluates
+ * to (concrete) store path. It is either:
+ *
+ * - opaque, in which case it is just a concrete store path with
+ *   possibly no known derivation
+ *
+ * - built, in which case it is a pair of a derivation path and an
+ *   output name.
+ */
+struct DerivedPath : _DerivedPathRaw {
+    using Raw = _DerivedPathRaw;
+    using Raw::Raw;
+
+    using Opaque = DerivedPathOpaque;
+    using Built = DerivedPathBuilt;
+
+    inline const Raw & raw() const {
+        return static_cast<const Raw &>(*this);
+    }
+
+    std::string to_string(const Store & store) const;
+    static DerivedPath parse(const Store & store, std::string_view);
+};
+
+/**
+ * A built derived path with hints in the form of optional concrete output paths.
+ *
+ * See 'DerivedPathWithHints' for more an explanation.
+ */
+struct DerivedPathWithHintsBuilt {
+    StorePath drvPath;
+    std::map<std::string, std::optional<StorePath>> outputs;
+
+    nlohmann::json toJSON(ref<Store> store) const;
+    static DerivedPathWithHintsBuilt parse(const Store & store, std::string_view);
+};
+
+using _DerivedPathWithHintsRaw = std::variant<
+    DerivedPath::Opaque,
+    DerivedPathWithHintsBuilt
+>;
+
+/**
+ * A derived path with hints in the form of optional concrete output paths in the built case.
+ *
+ * This type is currently just used by the CLI. The paths are filled in
+ * during evaluation for derivations that know what paths they will
+ * produce in advanced, i.e. input-addressed or fixed-output content
+ * addressed derivations.
+ *
+ * That isn't very good, because it puts floating content-addressed
+ * derivations "at a disadvantage". It would be better to never rely on
+ * the output path of unbuilt derivations, and exclusively use the
+ * realizations types to work with built derivations' concrete output
+ * paths.
+ */
+// FIXME Stop using and delete this, or if that is not possible move out of libstore to libcmd.
+struct DerivedPathWithHints : _DerivedPathWithHintsRaw {
+    using Raw = _DerivedPathWithHintsRaw;
+    using Raw::Raw;
+
+    using Opaque = DerivedPathOpaque;
+    using Built = DerivedPathWithHintsBuilt;
+
+    inline const Raw & raw() const {
+        return static_cast<const Raw &>(*this);
+    }
+
+};
+
+typedef std::vector<DerivedPathWithHints> DerivedPathsWithHints;
+
+nlohmann::json derivedPathsWithHintsToJSON(const DerivedPathsWithHints & buildables, ref<Store> store);
+
+}
diff --git a/src/libstore/legacy-ssh-store.cc b/src/libstore/legacy-ssh-store.cc
index a9f53bad9..edaf75136 100644
--- a/src/libstore/legacy-ssh-store.cc
+++ b/src/libstore/legacy-ssh-store.cc
@@ -3,6 +3,7 @@
 #include "remote-store.hh"
 #include "serve-protocol.hh"
 #include "store-api.hh"
+#include "path-with-outputs.hh"
 #include "worker-protocol.hh"
 #include "ssh.hh"
 #include "derivations.hh"
@@ -266,14 +267,23 @@ public:
         return status;
     }
 
-    void buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode) override
+    void buildPaths(const std::vector<DerivedPath> & drvPaths, BuildMode buildMode) override
     {
         auto conn(connections->get());
 
         conn->to << cmdBuildPaths;
         Strings ss;
-        for (auto & p : drvPaths)
-            ss.push_back(p.to_string(*this));
+        for (auto & p : drvPaths) {
+            auto sOrDrvPath = StorePathWithOutputs::tryFromDerivedPath(p);
+            std::visit(overloaded {
+                [&](StorePathWithOutputs s) {
+                    ss.push_back(s.to_string(*this));
+                },
+                [&](StorePath drvPath) {
+                    throw Error("wanted to fetch '%s' but the legacy ssh protocol doesn't support merely substituting drv files via the build paths command. It would build them instead. Try using ssh-ng://", printStorePath(drvPath));
+                },
+            }, sOrDrvPath);
+        }
         conn->to << ss;
 
         putBuildSettings(*conn);
diff --git a/src/libstore/misc.cc b/src/libstore/misc.cc
index f58816ad8..a99a2fc78 100644
--- a/src/libstore/misc.cc
+++ b/src/libstore/misc.cc
@@ -117,7 +117,7 @@ std::optional<ContentAddress> getDerivationCA(const BasicDerivation & drv)
     return std::nullopt;
 }
 
-void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
+void Store::queryMissing(const std::vector<DerivedPath> & targets,
     StorePathSet & willBuild_, StorePathSet & willSubstitute_, StorePathSet & unknown_,
     uint64_t & downloadSize_, uint64_t & narSize_)
 {
@@ -145,7 +145,7 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
 
     Sync<State> state_(State{{}, unknown_, willSubstitute_, willBuild_, downloadSize_, narSize_});
 
-    std::function<void(StorePathWithOutputs)> doPath;
+    std::function<void(DerivedPath)> doPath;
 
     auto mustBuildDrv = [&](const StorePath & drvPath, const Derivation & drv) {
         {
@@ -154,7 +154,7 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
         }
 
         for (auto & i : drv.inputDrvs)
-            pool.enqueue(std::bind(doPath, StorePathWithOutputs { i.first, i.second }));
+            pool.enqueue(std::bind(doPath, DerivedPath::Built { i.first, i.second }));
     };
 
     auto checkOutput = [&](
@@ -177,24 +177,25 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
                 drvState->outPaths.insert(outPath);
                 if (!drvState->left) {
                     for (auto & path : drvState->outPaths)
-                        pool.enqueue(std::bind(doPath, StorePathWithOutputs { path } ));
+                        pool.enqueue(std::bind(doPath, DerivedPath::Opaque { path } ));
                 }
             }
         }
     };
 
-    doPath = [&](const StorePathWithOutputs & path) {
+    doPath = [&](const DerivedPath & req) {
 
         {
             auto state(state_.lock());
-            if (!state->done.insert(path.to_string(*this)).second) return;
+            if (!state->done.insert(req.to_string(*this)).second) return;
         }
 
-        if (path.path.isDerivation()) {
-            if (!isValidPath(path.path)) {
+        std::visit(overloaded {
+          [&](DerivedPath::Built bfd) {
+            if (!isValidPath(bfd.drvPath)) {
                 // FIXME: we could try to substitute the derivation.
                 auto state(state_.lock());
-                state->unknown.insert(path.path);
+                state->unknown.insert(bfd.drvPath);
                 return;
             }
 
@@ -202,52 +203,54 @@ void Store::queryMissing(const std::vector<StorePathWithOutputs> & targets,
             /* 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)) {
+            for (auto & [outputName, pathOpt] : queryPartialDerivationOutputMap(bfd.drvPath)) {
                 if (!pathOpt) {
                     knownOutputPaths = false;
                     break;
                 }
-                if (wantOutput(outputName, path.outputs) && !isValidPath(*pathOpt))
+                if (wantOutput(outputName, bfd.outputs) && !isValidPath(*pathOpt))
                     invalid.insert(*pathOpt);
             }
             if (knownOutputPaths && invalid.empty()) return;
 
-            auto drv = make_ref<Derivation>(derivationFromPath(path.path));
-            ParsedDerivation parsedDrv(StorePath(path.path), *drv);
+            auto drv = make_ref<Derivation>(derivationFromPath(bfd.drvPath));
+            ParsedDerivation parsedDrv(StorePath(bfd.drvPath), *drv);
 
             if (knownOutputPaths && settings.useSubstitutes && parsedDrv.substitutesAllowed()) {
                 auto drvState = make_ref<Sync<DrvState>>(DrvState(invalid.size()));
                 for (auto & output : invalid)
-                    pool.enqueue(std::bind(checkOutput, path.path, drv, output, drvState));
+                    pool.enqueue(std::bind(checkOutput, bfd.drvPath, drv, output, drvState));
             } else
-                mustBuildDrv(path.path, *drv);
+                mustBuildDrv(bfd.drvPath, *drv);
 
-        } else {
+          },
+          [&](DerivedPath::Opaque bo) {
 
-            if (isValidPath(path.path)) return;
+            if (isValidPath(bo.path)) return;
 
             SubstitutablePathInfos infos;
-            querySubstitutablePathInfos({{path.path, std::nullopt}}, infos);
+            querySubstitutablePathInfos({{bo.path, std::nullopt}}, infos);
 
             if (infos.empty()) {
                 auto state(state_.lock());
-                state->unknown.insert(path.path);
+                state->unknown.insert(bo.path);
                 return;
             }
 
-            auto info = infos.find(path.path);
+            auto info = infos.find(bo.path);
             assert(info != infos.end());
 
             {
                 auto state(state_.lock());
-                state->willSubstitute.insert(path.path);
+                state->willSubstitute.insert(bo.path);
                 state->downloadSize += info->second.downloadSize;
                 state->narSize += info->second.narSize;
             }
 
             for (auto & ref : info->second.references)
-                pool.enqueue(std::bind(doPath, StorePathWithOutputs { ref }));
-        }
+                pool.enqueue(std::bind(doPath, DerivedPath::Opaque { ref }));
+          },
+        }, req.raw());
     };
 
     for (auto & path : targets)
diff --git a/src/libstore/path-with-outputs.cc b/src/libstore/path-with-outputs.cc
new file mode 100644
index 000000000..865d64cf2
--- /dev/null
+++ b/src/libstore/path-with-outputs.cc
@@ -0,0 +1,71 @@
+#include "path-with-outputs.hh"
+#include "store-api.hh"
+
+namespace nix {
+
+std::string StorePathWithOutputs::to_string(const Store & store) const
+{
+    return outputs.empty()
+        ? store.printStorePath(path)
+        : store.printStorePath(path) + "!" + concatStringsSep(",", outputs);
+}
+
+
+DerivedPath StorePathWithOutputs::toDerivedPath() const
+{
+    if (!outputs.empty() || path.isDerivation())
+        return DerivedPath::Built { path, outputs };
+    else
+        return DerivedPath::Opaque { path };
+}
+
+
+std::vector<DerivedPath> toDerivedPaths(const std::vector<StorePathWithOutputs> ss)
+{
+	std::vector<DerivedPath> reqs;
+	for (auto & s : ss) reqs.push_back(s.toDerivedPath());
+	return reqs;
+}
+
+
+std::variant<StorePathWithOutputs, StorePath> StorePathWithOutputs::tryFromDerivedPath(const DerivedPath & p)
+{
+    return std::visit(overloaded {
+        [&](DerivedPath::Opaque bo) -> std::variant<StorePathWithOutputs, StorePath> {
+            if (bo.path.isDerivation()) {
+                // drv path gets interpreted as "build", not "get drv file itself"
+                return bo.path;
+            }
+            return StorePathWithOutputs { bo.path };
+        },
+        [&](DerivedPath::Built bfd) -> std::variant<StorePathWithOutputs, StorePath> {
+            return StorePathWithOutputs { bfd.drvPath, bfd.outputs };
+        },
+    }, p.raw());
+}
+
+
+std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s)
+{
+    size_t n = s.find("!");
+    return n == s.npos
+        ? std::make_pair(s, std::set<string>())
+        : std::make_pair(((std::string_view) s).substr(0, n),
+            tokenizeString<std::set<string>>(((std::string_view) s).substr(n + 1), ","));
+}
+
+
+StorePathWithOutputs parsePathWithOutputs(const Store & store, std::string_view pathWithOutputs)
+{
+    auto [path, outputs] = parsePathWithOutputs(pathWithOutputs);
+    return StorePathWithOutputs { store.parseStorePath(path), std::move(outputs) };
+}
+
+
+StorePathWithOutputs followLinksToStorePathWithOutputs(const Store & store, std::string_view pathWithOutputs)
+{
+    auto [path, outputs] = parsePathWithOutputs(pathWithOutputs);
+    return StorePathWithOutputs { store.followLinksToStorePath(path), std::move(outputs) };
+}
+
+}
diff --git a/src/libstore/path-with-outputs.hh b/src/libstore/path-with-outputs.hh
new file mode 100644
index 000000000..4c4023dcb
--- /dev/null
+++ b/src/libstore/path-with-outputs.hh
@@ -0,0 +1,35 @@
+#pragma once
+
+#include <variant>
+
+#include "path.hh"
+#include "derived-path.hh"
+
+namespace nix {
+
+struct StorePathWithOutputs
+{
+    StorePath path;
+    std::set<std::string> outputs;
+
+    std::string to_string(const Store & store) const;
+
+    DerivedPath toDerivedPath() const;
+
+    static std::variant<StorePathWithOutputs, StorePath> tryFromDerivedPath(const DerivedPath &);
+};
+
+std::vector<DerivedPath> toDerivedPaths(const std::vector<StorePathWithOutputs>);
+
+std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s);
+
+class Store;
+
+/* Split a string specifying a derivation and a set of outputs
+   (/nix/store/hash-foo!out1,out2,...) into the derivation path
+   and the outputs. */
+StorePathWithOutputs parsePathWithOutputs(const Store & store, std::string_view pathWithOutputs);
+
+StorePathWithOutputs followLinksToStorePathWithOutputs(const Store & store, std::string_view pathWithOutputs);
+
+}
diff --git a/src/libstore/path.cc b/src/libstore/path.cc
index dc9dc3897..e642abcd5 100644
--- a/src/libstore/path.cc
+++ b/src/libstore/path.cc
@@ -82,19 +82,4 @@ PathSet Store::printStorePathSet(const StorePathSet & paths) const
     return res;
 }
 
-std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s)
-{
-    size_t n = s.find("!");
-    return n == s.npos
-        ? std::make_pair(s, std::set<string>())
-        : std::make_pair(((std::string_view) s).substr(0, n),
-            tokenizeString<std::set<string>>(((std::string_view) s).substr(n + 1), ","));
-}
-
-StorePathWithOutputs Store::parsePathWithOutputs(const std::string & s)
-{
-    auto [path, outputs] = nix::parsePathWithOutputs(s);
-    return {parseStorePath(path), std::move(outputs)};
-}
-
 }
diff --git a/src/libstore/path.hh b/src/libstore/path.hh
index b03a0f69d..06ba0663b 100644
--- a/src/libstore/path.hh
+++ b/src/libstore/path.hh
@@ -69,16 +69,6 @@ typedef std::map<StorePath, std::optional<ContentAddress>> StorePathCAMap;
 /* Extension of derivations in the Nix store. */
 const std::string drvExtension = ".drv";
 
-struct StorePathWithOutputs
-{
-    StorePath path;
-    std::set<std::string> outputs;
-
-    std::string to_string(const Store & store) const;
-};
-
-std::pair<std::string_view, StringSet> parsePathWithOutputs(std::string_view s);
-
 }
 
 namespace std {
diff --git a/src/libstore/remote-store.cc b/src/libstore/remote-store.cc
index ccf095dc2..761b4a087 100644
--- a/src/libstore/remote-store.cc
+++ b/src/libstore/remote-store.cc
@@ -1,5 +1,6 @@
 #include "serialise.hh"
 #include "util.hh"
+#include "path-with-outputs.hh"
 #include "remote-fs-accessor.hh"
 #include "remote-store.hh"
 #include "worker-protocol.hh"
@@ -50,6 +51,19 @@ void write(const Store & store, Sink & out, const ContentAddress & ca)
     out << renderContentAddress(ca);
 }
 
+
+DerivedPath read(const Store & store, Source & from, Phantom<DerivedPath> _)
+{
+    auto s = readString(from);
+    return DerivedPath::parse(store, s);
+}
+
+void write(const Store & store, Sink & out, const DerivedPath & req)
+{
+    out << req.to_string(store);
+}
+
+
 Realisation read(const Store & store, Source & from, Phantom<Realisation> _)
 {
     std::string rawInput = readString(from);
@@ -58,8 +72,12 @@ Realisation read(const Store & store, Source & from, Phantom<Realisation> _)
         "remote-protocol"
     );
 }
+
 void write(const Store & store, Sink & out, const Realisation & realisation)
-{ out << realisation.toJSON().dump(); }
+{
+    out << realisation.toJSON().dump();
+}
+
 
 DrvOutput read(const Store & store, Source & from, Phantom<DrvOutput> _)
 {
@@ -652,16 +670,36 @@ std::optional<const Realisation> RemoteStore::queryRealisation(const DrvOutput &
     return {Realisation{.id = id, .outPath = *outPaths.begin()}};
 }
 
+static void writeDerivedPaths(RemoteStore & store, ConnectionHandle & conn, const std::vector<DerivedPath> & reqs)
+{
+    if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 29) {
+        worker_proto::write(store, conn->to, reqs);
+    } else {
+        Strings ss;
+        for (auto & p : reqs) {
+            auto sOrDrvPath = StorePathWithOutputs::tryFromDerivedPath(p);
+            std::visit(overloaded {
+                [&](StorePathWithOutputs s) {
+                    ss.push_back(s.to_string(store));
+                },
+                [&](StorePath drvPath) {
+                    throw Error("trying to request '%s', but daemon protocol %d.%d is too old (< 1.29) to request a derivation file",
+                        store.printStorePath(drvPath),
+                        GET_PROTOCOL_MAJOR(conn->daemonVersion),
+                        GET_PROTOCOL_MINOR(conn->daemonVersion));
+                },
+            }, sOrDrvPath);
+        }
+        conn->to << ss;
+    }
+}
 
-void RemoteStore::buildPaths(const std::vector<StorePathWithOutputs> & drvPaths, BuildMode buildMode)
+void RemoteStore::buildPaths(const std::vector<DerivedPath> & drvPaths, BuildMode buildMode)
 {
     auto conn(getConnection());
     conn->to << wopBuildPaths;
     assert(GET_PROTOCOL_MINOR(conn->daemonVersion) >= 13);
-    Strings ss;
-    for (auto & p : drvPaths)
-        ss.push_back(p.to_string(*this));
-    conn->to << ss;
+    writeDerivedPaths(*this, conn, drvPaths);
     if (GET_PROTOCOL_MINOR(conn->daemonVersion) >= 15)
         conn->to << buildMode;
     else
@@ -800,7 +838,7 @@ void RemoteStore::addSignatures(const StorePath & storePath, const StringSet & s
 }
 
 
-void RemoteStore::queryMissing(const std::vector<StorePathWithOutputs> & targets,
+void RemoteStore::queryMissing(const std::vector<DerivedPath> & targets,
     StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
     uint64_t & downloadSize, uint64_t & narSize)
 {
@@ -811,10 +849,7 @@ void RemoteStore::queryMissing(const std::vector<StorePathWithOutputs> & targets
             // to prevent a deadlock.
             goto fallback;
         conn->to << wopQueryMissing;
-        Strings ss;
-        for (auto & p : targets)
-            ss.push_back(p.to_string(*this));
-        conn->to << ss;
+        writeDerivedPaths(*this, conn, targets);
         conn.processStderr();
         willBuild = worker_proto::read(*this, conn->from, Phantom<StorePathSet> {});
         willSubstitute = worker_proto::read(*this, conn->from, Phantom<StorePathSet> {});
diff --git a/src/libstore/remote-store.hh b/src/libstore/remote-store.hh
index b3a9910a3..6cf76a46d 100644
--- a/src/libstore/remote-store.hh
+++ b/src/libstore/remote-store.hh
@@ -85,7 +85,7 @@ public:
 
     std::optional<const Realisation> queryRealisation(const DrvOutput &) override;
 
-    void buildPaths(const std::vector<StorePathWithOutputs> & paths, BuildMode buildMode) override;
+    void buildPaths(const std::vector<DerivedPath> & paths, BuildMode buildMode) override;
 
     BuildResult buildDerivation(const StorePath & drvPath, const BasicDerivation & drv,
         BuildMode buildMode) override;
@@ -108,7 +108,7 @@ public:
 
     void addSignatures(const StorePath & storePath, const StringSet & sigs) override;
 
-    void queryMissing(const std::vector<StorePathWithOutputs> & targets,
+    void queryMissing(const std::vector<DerivedPath> & targets,
         StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
         uint64_t & downloadSize, uint64_t & narSize) override;
 
diff --git a/src/libstore/store-api.cc b/src/libstore/store-api.cc
index 5e321cedf..93fcb068f 100644
--- a/src/libstore/store-api.cc
+++ b/src/libstore/store-api.cc
@@ -53,13 +53,6 @@ StorePath Store::followLinksToStorePath(std::string_view path) const
 }
 
 
-StorePathWithOutputs Store::followLinksToStorePathWithOutputs(std::string_view path) const
-{
-    auto [path2, outputs] = nix::parsePathWithOutputs(path);
-    return StorePathWithOutputs { followLinksToStorePath(path2), std::move(outputs) };
-}
-
-
 /* Store paths have the following form:
 
    <realized-path> = <store>/<h>-<name>
@@ -536,10 +529,10 @@ void Store::queryPathInfo(const StorePath & storePath,
 
 void Store::substitutePaths(const StorePathSet & paths)
 {
-    std::vector<StorePathWithOutputs> paths2;
+    std::vector<DerivedPath> paths2;
     for (auto & path : paths)
         if (!path.isDerivation())
-            paths2.push_back({path});
+            paths2.push_back(DerivedPath::Opaque{path});
     uint64_t downloadSize, narSize;
     StorePathSet willBuild, willSubstitute, unknown;
     queryMissing(paths2,
@@ -547,8 +540,8 @@ void Store::substitutePaths(const StorePathSet & paths)
 
     if (!willSubstitute.empty())
         try {
-            std::vector<StorePathWithOutputs> subs;
-            for (auto & p : willSubstitute) subs.push_back({p});
+            std::vector<DerivedPath> subs;
+            for (auto & p : willSubstitute) subs.push_back(DerivedPath::Opaque{p});
             buildPaths(subs);
         } catch (Error & e) {
             logWarning(e.info());
diff --git a/src/libstore/store-api.hh b/src/libstore/store-api.hh
index 5d19e8949..f66298991 100644
--- a/src/libstore/store-api.hh
+++ b/src/libstore/store-api.hh
@@ -2,6 +2,7 @@
 
 #include "realisation.hh"
 #include "path.hh"
+#include "derived-path.hh"
 #include "hash.hh"
 #include "content-address.hh"
 #include "serialise.hh"
@@ -261,11 +262,6 @@ public:
 
     PathSet printStorePathSet(const StorePathSet & path) const;
 
-    /* Split a string specifying a derivation and a set of outputs
-       (/nix/store/hash-foo!out1,out2,...) into the derivation path
-       and the outputs. */
-    StorePathWithOutputs parsePathWithOutputs(const string & s);
-
     /* Display a set of paths in human-readable form (i.e., between quotes
        and separated by commas). */
     std::string showPaths(const StorePathSet & paths);
@@ -289,8 +285,6 @@ public:
        result. */
     StorePath followLinksToStorePath(std::string_view path) const;
 
-    StorePathWithOutputs followLinksToStorePathWithOutputs(std::string_view path) const;
-
     /* Constructs a unique store path name. */
     StorePath makeStorePath(std::string_view type,
         std::string_view hash, std::string_view name) const;
@@ -500,7 +494,7 @@ public:
        recursively building any sub-derivations. For inputs that are
        not derivations, substitute them. */
     virtual void buildPaths(
-        const std::vector<StorePathWithOutputs> & paths,
+        const std::vector<DerivedPath> & paths,
         BuildMode buildMode = bmNormal);
 
     /* Build a single non-materialized derivation (i.e. not from an
@@ -662,7 +656,7 @@ public:
     /* Given a set of paths that are to be built, return the set of
        derivations that will be built, and the set of output paths
        that will be substituted. */
-    virtual void queryMissing(const std::vector<StorePathWithOutputs> & targets,
+    virtual void queryMissing(const std::vector<DerivedPath> & targets,
         StorePathSet & willBuild, StorePathSet & willSubstitute, StorePathSet & unknown,
         uint64_t & downloadSize, uint64_t & narSize);
 
diff --git a/src/libstore/worker-protocol.hh b/src/libstore/worker-protocol.hh
index be071dd78..001ed25e3 100644
--- a/src/libstore/worker-protocol.hh
+++ b/src/libstore/worker-protocol.hh
@@ -86,9 +86,11 @@ namespace worker_proto {
 MAKE_WORKER_PROTO(, std::string);
 MAKE_WORKER_PROTO(, StorePath);
 MAKE_WORKER_PROTO(, ContentAddress);
+MAKE_WORKER_PROTO(, DerivedPath);
 MAKE_WORKER_PROTO(, Realisation);
 MAKE_WORKER_PROTO(, DrvOutput);
 
+MAKE_WORKER_PROTO(template<typename T>, std::vector<T>);
 MAKE_WORKER_PROTO(template<typename T>, std::set<T>);
 
 #define X_ template<typename K, typename V>
@@ -114,6 +116,26 @@ MAKE_WORKER_PROTO(, std::optional<StorePath>);
 MAKE_WORKER_PROTO(, std::optional<ContentAddress>);
 
 template<typename T>
+std::vector<T> read(const Store & store, Source & from, Phantom<std::vector<T>> _)
+{
+    std::vector<T> resSet;
+    auto size = readNum<size_t>(from);
+    while (size--) {
+        resSet.push_back(read(store, from, Phantom<T> {}));
+    }
+    return resSet;
+}
+
+template<typename T>
+void write(const Store & store, Sink & out, const std::vector<T> & resSet)
+{
+    out << resSet.size();
+    for (auto & key : resSet) {
+        write(store, out, key);
+    }
+}
+
+template<typename T>
 std::set<T> read(const Store & store, Source & from, Phantom<std::set<T>> _)
 {
     std::set<T> resSet;