12 files changed, 331 insertions, 88 deletions

diff --git a/src/libcmd/common-eval-args.cc b/src/libcmd/common-eval-args.cc
index 7f97364a1..3df2c71a5 100644
--- a/src/libcmd/common-eval-args.cc
+++ b/src/libcmd/common-eval-args.cc
@@ -105,7 +105,9 @@ MixEvalArgs::MixEvalArgs()
   )",
         .category = category,
         .labels = {"path"},
-        .handler = {[&](std::string s) { searchPath.push_back(s); }}
+        .handler = {[&](std::string s) {
+            searchPath.elements.emplace_back(SearchPath::Elem::parse(s));
+        }}
     });
 
     addFlag({
diff --git a/src/libcmd/common-eval-args.hh b/src/libcmd/common-eval-args.hh
index b65cb5b20..6359b2579 100644
--- a/src/libcmd/common-eval-args.hh
+++ b/src/libcmd/common-eval-args.hh
@@ -3,6 +3,7 @@
 
 #include "args.hh"
 #include "common-args.hh"
+#include "search-path.hh"
 
 namespace nix {
 
@@ -19,7 +20,7 @@ struct MixEvalArgs : virtual Args, virtual MixRepair
 
     Bindings * getAutoArgs(EvalState & state);
 
-    Strings searchPath;
+    SearchPath searchPath;
 
     std::optional<std::string> evalStoreUrl;
 
diff --git a/src/libcmd/repl.cc b/src/libcmd/repl.cc
index 4b160a100..f9e9c2bf8 100644
--- a/src/libcmd/repl.cc
+++ b/src/libcmd/repl.cc
@@ -68,7 +68,7 @@ struct NixRepl
 
     const Path historyFile;
 
-    NixRepl(const Strings & searchPath, nix::ref<Store> store,ref<EvalState> state,
+    NixRepl(const SearchPath & searchPath, nix::ref<Store> store,ref<EvalState> state,
             std::function<AnnotatedValues()> getValues);
     virtual ~NixRepl();
 
@@ -104,7 +104,7 @@ std::string removeWhitespace(std::string s)
 }
 
 
-NixRepl::NixRepl(const Strings & searchPath, nix::ref<Store> store, ref<EvalState> state,
+NixRepl::NixRepl(const SearchPath & searchPath, nix::ref<Store> store, ref<EvalState> state,
             std::function<NixRepl::AnnotatedValues()> getValues)
     : AbstractNixRepl(state)
     , debugTraceIndex(0)
@@ -1024,7 +1024,7 @@ std::ostream & NixRepl::printValue(std::ostream & str, Value & v, unsigned int m
 
 
 std::unique_ptr<AbstractNixRepl> AbstractNixRepl::create(
-   const Strings & searchPath, nix::ref<Store> store, ref<EvalState> state,
+   const SearchPath & searchPath, nix::ref<Store> store, ref<EvalState> state,
    std::function<AnnotatedValues()> getValues)
 {
     return std::make_unique<NixRepl>(
@@ -1044,7 +1044,7 @@ void AbstractNixRepl::runSimple(
         NixRepl::AnnotatedValues values;
         return values;
     };
-    const Strings & searchPath = {};
+    SearchPath searchPath = {};
     auto repl = std::make_unique<NixRepl>(
             searchPath,
             openStore(),
diff --git a/src/libcmd/repl.hh b/src/libcmd/repl.hh
index 731c8e6db..6d88883fe 100644
--- a/src/libcmd/repl.hh
+++ b/src/libcmd/repl.hh
@@ -25,7 +25,7 @@ struct AbstractNixRepl
     typedef std::vector<std::pair<Value*,std::string>> AnnotatedValues;
 
     static std::unique_ptr<AbstractNixRepl> create(
-        const Strings & searchPath, nix::ref<Store> store, ref<EvalState> state,
+        const SearchPath & searchPath, nix::ref<Store> store, ref<EvalState> state,
         std::function<AnnotatedValues()> getValues);
 
     static void runSimple(
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 706a19024..be1bdb806 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -498,7 +498,7 @@ ErrorBuilder & ErrorBuilder::withFrame(const Env & env, const Expr & expr)
 
 
 EvalState::EvalState(
-    const Strings & _searchPath,
+    const SearchPath & _searchPath,
     ref<Store> store,
     std::shared_ptr<Store> buildStore)
     : sWith(symbols.create("<with>"))
@@ -563,30 +563,32 @@ EvalState::EvalState(
 
     /* Initialise the Nix expression search path. */
     if (!evalSettings.pureEval) {
-        for (auto & i : _searchPath) addToSearchPath(i);
-        for (auto & i : evalSettings.nixPath.get()) addToSearchPath(i);
+        for (auto & i : _searchPath.elements)
+            addToSearchPath(SearchPath::Elem {i});
+        for (auto & i : evalSettings.nixPath.get())
+            addToSearchPath(SearchPath::Elem::parse(i));
     }
 
     if (evalSettings.restrictEval || evalSettings.pureEval) {
         allowedPaths = PathSet();
 
-        for (auto & i : searchPath) {
-            auto r = resolveSearchPathElem(i);
-            if (!r.first) continue;
+        for (auto & i : searchPath.elements) {
+            auto r = resolveSearchPathPath(i.path);
+            if (!r) continue;
 
-            auto path = r.second;
+            auto path = *std::move(r);
 
-            if (store->isInStore(r.second)) {
+            if (store->isInStore(path)) {
                 try {
                     StorePathSet closure;
-                    store->computeFSClosure(store->toStorePath(r.second).first, closure);
+                    store->computeFSClosure(store->toStorePath(path).first, closure);
                     for (auto & path : closure)
                         allowPath(path);
                 } catch (InvalidPath &) {
-                    allowPath(r.second);
+                    allowPath(path);
                 }
             } else
-                allowPath(r.second);
+                allowPath(path);
         }
     }
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index e3676c1b7..277e77ad5 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -9,6 +9,7 @@
 #include "config.hh"
 #include "experimental-features.hh"
 #include "input-accessor.hh"
+#include "search-path.hh"
 
 #include <map>
 #include <optional>
@@ -122,15 +123,6 @@ std::string printValue(const EvalState & state, const Value & v);
 std::ostream & operator << (std::ostream & os, const ValueType t);
 
 
-struct SearchPathElem
-{
-    std::string prefix;
-    // FIXME: maybe change this to an std::variant<SourcePath, URL>.
-    std::string path;
-};
-typedef std::list<SearchPathElem> SearchPath;
-
-
 /**
  * Initialise the Boehm GC, if applicable.
  */
@@ -317,7 +309,7 @@ private:
 
     SearchPath searchPath;
 
-    std::map<std::string, std::pair<bool, std::string>> searchPathResolved;
+    std::map<std::string, std::optional<std::string>> searchPathResolved;
 
     /**
      * Cache used by checkSourcePath().
@@ -344,12 +336,12 @@ private:
 public:
 
     EvalState(
-        const Strings & _searchPath,
+        const SearchPath & _searchPath,
         ref<Store> store,
         std::shared_ptr<Store> buildStore = nullptr);
     ~EvalState();
 
-    void addToSearchPath(const std::string & s);
+    void addToSearchPath(SearchPath::Elem && elem);
 
     SearchPath getSearchPath() { return searchPath; }
 
@@ -431,12 +423,16 @@ public:
      * Look up a file in the search path.
      */
     SourcePath findFile(const std::string_view path);
-    SourcePath findFile(SearchPath & searchPath, const std::string_view path, const PosIdx pos = noPos);
+    SourcePath findFile(const SearchPath & searchPath, const std::string_view path, const PosIdx pos = noPos);
 
     /**
+     * Try to resolve a search path value (not the optinal key part)
+     *
      * If the specified search path element is a URI, download it.
+     *
+     * If it is not found, return `std::nullopt`
      */
-    std::pair<bool, std::string> resolveSearchPathElem(const SearchPathElem & elem);
+    std::optional<std::string> resolveSearchPathPath(const SearchPath::Path & path);
 
     /**
      * Evaluate an expression to normal form
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 3336d3315..0a1ad9967 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -734,22 +734,9 @@ Expr * EvalState::parseStdin()
 }
 
 
-void EvalState::addToSearchPath(const std::string & s)
+void EvalState::addToSearchPath(SearchPath::Elem && elem)
 {
-    size_t pos = s.find('=');
-    std::string prefix;
-    Path path;
-    if (pos == std::string::npos) {
-        path = s;
-    } else {
-        prefix = std::string(s, 0, pos);
-        path = std::string(s, pos + 1);
-    }
-
-    searchPath.emplace_back(SearchPathElem {
-        .prefix = prefix,
-        .path = path,
-    });
+    searchPath.elements.emplace_back(std::move(elem));
 }
 
 
@@ -759,22 +746,19 @@ SourcePath EvalState::findFile(const std::string_view path)
 }
 
 
-SourcePath EvalState::findFile(SearchPath & searchPath, const std::string_view path, const PosIdx pos)
+SourcePath EvalState::findFile(const SearchPath & searchPath, const std::string_view path, const PosIdx pos)
 {
-    for (auto & i : searchPath) {
-        std::string suffix;
-        if (i.prefix.empty())
-            suffix = concatStrings("/", path);
-        else {
-            auto s = i.prefix.size();
-            if (path.compare(0, s, i.prefix) != 0 ||
-                (path.size() > s && path[s] != '/'))
-                continue;
-            suffix = path.size() == s ? "" : concatStrings("/", path.substr(s));
-        }
-        auto r = resolveSearchPathElem(i);
-        if (!r.first) continue;
-        Path res = r.second + suffix;
+    for (auto & i : searchPath.elements) {
+        auto suffixOpt = i.prefix.suffixIfPotentialMatch(path);
+
+        if (!suffixOpt) continue;
+        auto suffix = *suffixOpt;
+
+        auto rOpt = resolveSearchPathPath(i.path);
+        if (!rOpt) continue;
+        auto r = *rOpt;
+
+        Path res = suffix == "" ? r : concatStrings(r, "/", suffix);
         if (pathExists(res)) return CanonPath(canonPath(res));
     }
 
@@ -791,49 +775,53 @@ SourcePath EvalState::findFile(SearchPath & searchPath, const std::string_view p
 }
 
 
-std::pair<bool, std::string> EvalState::resolveSearchPathElem(const SearchPathElem & elem)
+std::optional<std::string> EvalState::resolveSearchPathPath(const SearchPath::Path & value0)
 {
-    auto i = searchPathResolved.find(elem.path);
+    auto & value = value0.s;
+    auto i = searchPathResolved.find(value);
     if (i != searchPathResolved.end()) return i->second;
 
-    std::pair<bool, std::string> res;
+    std::optional<std::string> res;
 
-    if (EvalSettings::isPseudoUrl(elem.path)) {
+    if (EvalSettings::isPseudoUrl(value)) {
         try {
             auto storePath = fetchers::downloadTarball(
-                store, EvalSettings::resolvePseudoUrl(elem.path), "source", false).tree.storePath;
-            res = { true, store->toRealPath(storePath) };
+                store, EvalSettings::resolvePseudoUrl(value), "source", false).tree.storePath;
+            res = { store->toRealPath(storePath) };
         } catch (FileTransferError & e) {
             logWarning({
-                .msg = hintfmt("Nix search path entry '%1%' cannot be downloaded, ignoring", elem.path)
+                .msg = hintfmt("Nix search path entry '%1%' cannot be downloaded, ignoring", value)
             });
-            res = { false, "" };
+            res = std::nullopt;
         }
     }
 
-    else if (hasPrefix(elem.path, "flake:")) {
+    else if (hasPrefix(value, "flake:")) {
         experimentalFeatureSettings.require(Xp::Flakes);
-        auto flakeRef = parseFlakeRef(elem.path.substr(6), {}, true, false);
-        debug("fetching flake search path element '%s''", elem.path);
+        auto flakeRef = parseFlakeRef(value.substr(6), {}, true, false);
+        debug("fetching flake search path element '%s''", value);
         auto storePath = flakeRef.resolve(store).fetchTree(store).first.storePath;
-        res = { true, store->toRealPath(storePath) };
+        res = { store->toRealPath(storePath) };
     }
 
     else {
-        auto path = absPath(elem.path);
+        auto path = absPath(value);
         if (pathExists(path))
-            res = { true, path };
+            res = { path };
         else {
             logWarning({
-                .msg = hintfmt("Nix search path entry '%1%' does not exist, ignoring", elem.path)
+                .msg = hintfmt("Nix search path entry '%1%' does not exist, ignoring", value)
             });
-            res = { false, "" };
+            res = std::nullopt;
         }
     }
 
-    debug("resolved search path element '%s' to '%s'", elem.path, res.second);
+    if (res)
+        debug("resolved search path element '%s' to '%s'", value, *res);
+    else
+        debug("failed to resolve search path element '%s'", value);
 
-    searchPathResolved[elem.path] = res;
+    searchPathResolved[value] = res;
     return res;
 }
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index f4bdf8fc6..8a61e57cc 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -1658,9 +1658,9 @@ static void prim_findFile(EvalState & state, const PosIdx pos, Value * * args, V
             }));
         }
 
-        searchPath.emplace_back(SearchPathElem {
-            .prefix = prefix,
-            .path = path,
+        searchPath.elements.emplace_back(SearchPath::Elem {
+            .prefix = SearchPath::Prefix { .s = prefix },
+            .path = SearchPath::Path { .s = path },
         });
     }
 
@@ -4321,12 +4321,12 @@ void EvalState::createBaseEnv()
     });
 
     /* Add a value containing the current Nix expression search path. */
-    mkList(v, searchPath.size());
+    mkList(v, searchPath.elements.size());
     int n = 0;
-    for (auto & i : searchPath) {
+    for (auto & i : searchPath.elements) {
         auto attrs = buildBindings(2);
-        attrs.alloc("path").mkString(i.path);
-        attrs.alloc("prefix").mkString(i.prefix);
+        attrs.alloc("path").mkString(i.path.s);
+        attrs.alloc("prefix").mkString(i.prefix.s);
         (v.listElems()[n++] = allocValue())->mkAttrs(attrs);
     }
     addConstant("__nixPath", v, {
diff --git a/src/libexpr/search-path.cc b/src/libexpr/search-path.cc
new file mode 100644
index 000000000..36bb4c3a5
--- /dev/null
+++ b/src/libexpr/search-path.cc
@@ -0,0 +1,56 @@
+#include "search-path.hh"
+#include "util.hh"
+
+namespace nix {
+
+std::optional<std::string_view> SearchPath::Prefix::suffixIfPotentialMatch(
+    std::string_view path) const
+{
+    auto n = s.size();
+
+    /* Non-empty prefix and suffix must be separated by a /, or the
+       prefix is not a valid path prefix. */
+    bool needSeparator = n > 0 && (path.size() - n) > 0;
+
+    if (needSeparator && path[n] != '/') {
+        return std::nullopt;
+    }
+
+    /* Prefix must be prefix of this path. */
+    if (path.compare(0, n, s) != 0) {
+        return std::nullopt;
+    }
+
+    /* Skip next path separator. */
+    return {
+        path.substr(needSeparator ? n + 1 : n)
+    };
+}
+
+
+SearchPath::Elem SearchPath::Elem::parse(std::string_view rawElem)
+{
+    size_t pos = rawElem.find('=');
+
+    return SearchPath::Elem {
+        .prefix = Prefix {
+            .s = pos == std::string::npos
+                ? std::string { "" }
+                : std::string { rawElem.substr(0, pos) },
+        },
+        .path = Path {
+            .s = std::string { rawElem.substr(pos + 1) },
+        },
+    };
+}
+
+
+SearchPath parseSearchPath(const Strings & rawElems)
+{
+    SearchPath res;
+    for (auto & rawElem : rawElems)
+        res.elements.emplace_back(SearchPath::Elem::parse(rawElem));
+    return res;
+}
+
+}
diff --git a/src/libexpr/search-path.hh b/src/libexpr/search-path.hh
new file mode 100644
index 000000000..ce78135b5
--- /dev/null
+++ b/src/libexpr/search-path.hh
@@ -0,0 +1,108 @@
+#pragma once
+///@file
+
+#include <optional>
+
+#include "types.hh"
+#include "comparator.hh"
+
+namespace nix {
+
+/**
+ * A "search path" is a list of ways look for something, used with
+ * `builtins.findFile` and `< >` lookup expressions.
+ */
+struct SearchPath
+{
+    /**
+     * A single element of a `SearchPath`.
+     *
+     * Each element is tried in succession when looking up a path. The first
+     * element to completely match wins.
+     */
+    struct Elem;
+
+    /**
+     * The first part of a `SearchPath::Elem` pair.
+     *
+     * Called a "prefix" because it takes the form of a prefix of a file
+     * path (first `n` path components). When looking up a path, to use
+     * a `SearchPath::Elem`, its `Prefix` must match the path.
+     */
+    struct Prefix;
+
+    /**
+     * The second part of a `SearchPath::Elem` pair.
+     *
+     * It is either a path or a URL (with certain restrictions / extra
+     * structure).
+     *
+     * If the prefix of the path we are looking up matches, we then
+     * check if the rest of the path points to something that exists
+     * within the directory denoted by this. If so, the
+     * `SearchPath::Elem` as a whole matches, and that *something* being
+     * pointed to by the rest of the path we are looking up is the
+     * result.
+     */
+    struct Path;
+
+    /**
+     * The list of search path elements. Each one is checked for a path
+     * when looking up. (The actual lookup entry point is in `EvalState`
+     * not in this class.)
+     */
+    std::list<SearchPath::Elem> elements;
+
+    /**
+     * Parse a string into a `SearchPath`
+     */
+    static SearchPath parse(const Strings & rawElems);
+};
+
+struct SearchPath::Prefix
+{
+    /**
+     * Underlying string
+     *
+     * @todo Should we normalize this when constructing a `SearchPath::Prefix`?
+     */
+    std::string s;
+
+    GENERATE_CMP(SearchPath::Prefix, me->s);
+
+    /**
+     * If the path possibly matches this search path element, return the
+     * suffix that we should look for inside the resolved value of the
+     * element
+     * Note the double optionality in the name. While we might have a matching prefix, the suffix may not exist.
+     */
+    std::optional<std::string_view> suffixIfPotentialMatch(std::string_view path) const;
+};
+
+struct SearchPath::Path
+{
+    /**
+     * The location of a search path item, as a path or URL.
+     *
+     * @todo Maybe change this to `std::variant<SourcePath, URL>`.
+     */
+    std::string s;
+
+    GENERATE_CMP(SearchPath::Path, me->s);
+};
+
+struct SearchPath::Elem
+{
+
+    Prefix prefix;
+    Path path;
+
+    GENERATE_CMP(SearchPath::Elem, me->prefix, me->path);
+
+    /**
+     * Parse a string into a `SearchPath::Elem`
+     */
+    static SearchPath::Elem parse(std::string_view rawElem);
+};
+
+}
diff --git a/src/libexpr/tests/search-path.cc b/src/libexpr/tests/search-path.cc
new file mode 100644
index 000000000..dbe7ab95f
--- /dev/null
+++ b/src/libexpr/tests/search-path.cc
@@ -0,0 +1,90 @@
+#include <gtest/gtest.h>
+#include <gmock/gmock.h>
+
+#include "search-path.hh"
+
+namespace nix {
+
+TEST(SearchPathElem, parse_justPath) {
+    ASSERT_EQ(
+        SearchPath::Elem::parse("foo"),
+        (SearchPath::Elem {
+            .prefix = SearchPath::Prefix { .s = "" },
+            .path = SearchPath::Path { .s = "foo" },
+        }));
+}
+
+TEST(SearchPathElem, parse_emptyPrefix) {
+    ASSERT_EQ(
+        SearchPath::Elem::parse("=foo"),
+        (SearchPath::Elem {
+            .prefix = SearchPath::Prefix { .s = "" },
+            .path = SearchPath::Path { .s = "foo" },
+        }));
+}
+
+TEST(SearchPathElem, parse_oneEq) {
+    ASSERT_EQ(
+        SearchPath::Elem::parse("foo=bar"),
+        (SearchPath::Elem {
+            .prefix = SearchPath::Prefix { .s = "foo" },
+            .path = SearchPath::Path { .s = "bar" },
+        }));
+}
+
+TEST(SearchPathElem, parse_twoEqs) {
+    ASSERT_EQ(
+        SearchPath::Elem::parse("foo=bar=baz"),
+        (SearchPath::Elem {
+            .prefix = SearchPath::Prefix { .s = "foo" },
+            .path = SearchPath::Path { .s = "bar=baz" },
+        }));
+}
+
+
+TEST(SearchPathElem, suffixIfPotentialMatch_justPath) {
+    SearchPath::Prefix prefix { .s = "" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("any/thing"), std::optional { "any/thing" });
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_misleadingPrefix1) {
+    SearchPath::Prefix prefix { .s = "foo" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("fooX"), std::nullopt);
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_misleadingPrefix2) {
+    SearchPath::Prefix prefix { .s = "foo" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("fooX/bar"), std::nullopt);
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_partialPrefix) {
+    SearchPath::Prefix prefix { .s = "fooX" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("foo"), std::nullopt);
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_exactPrefix) {
+    SearchPath::Prefix prefix { .s = "foo" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("foo"), std::optional { "" });
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_multiKey) {
+    SearchPath::Prefix prefix { .s = "foo/bar" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("foo/bar/baz"), std::optional { "baz" });
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_trailingSlash) {
+    SearchPath::Prefix prefix { .s = "foo" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("foo/"), std::optional { "" });
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_trailingDoubleSlash) {
+    SearchPath::Prefix prefix { .s = "foo" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("foo//"), std::optional { "/" });
+}
+
+TEST(SearchPathElem, suffixIfPotentialMatch_trailingPath) {
+    SearchPath::Prefix prefix { .s = "foo" };
+    ASSERT_EQ(prefix.suffixIfPotentialMatch("foo/bar/baz"), std::optional { "bar/baz" });
+}
+
+}
diff --git a/src/nix/upgrade-nix.cc b/src/nix/upgrade-nix.cc
index 3997c98bf..d05c23fb7 100644
--- a/src/nix/upgrade-nix.cc
+++ b/src/nix/upgrade-nix.cc
@@ -146,7 +146,7 @@ struct CmdUpgradeNix : MixDryRun, StoreCommand
         auto req = FileTransferRequest(storePathsUrl);
         auto res = getFileTransfer()->download(req);
 
-        auto state = std::make_unique<EvalState>(Strings(), store);
+        auto state = std::make_unique<EvalState>(SearchPath{}, store);
         auto v = state->allocValue();
         state->eval(state->parseExprFromString(res.data, state->rootPath(CanonPath("/no-such-path"))), *v);
         Bindings & bindings(*state->allocBindings(0));