Clean up `SearchPath`

- Better types

- Own header / C++ file pair

- Test factored out methods

- Pass parsed thing around more than strings

Co-authored-by: Robert Hensing <roberth@users.noreply.github.com>

12 files changed, 300 insertions, 64 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 97a264085..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,15 +563,17 @@ 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.path);
+        for (auto & i : searchPath.elements) {
+            auto r = resolveSearchPathPath(i.path);
             if (!r) continue;
 
             auto path = *std::move(r);
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index e1a540a7f..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.
  */
@@ -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,7 +423,7 @@ 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)
@@ -440,7 +432,7 @@ public:
      *
      * If it is not found, return `std::nullopt`
      */
-    std::optional<std::string> resolveSearchPathElem(const std::string & value);
+    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 f839e804c..77bcc31e0 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.path);
-        if (!r) continue;
-        Path res = *r + 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,8 +775,9 @@ SourcePath EvalState::findFile(SearchPath & searchPath, const std::string_view p
 }
 
 
-std::optional<std::string> EvalState::resolveSearchPathElem(const std::string & value)
+std::optional<std::string> EvalState::resolveSearchPathPath(const SearchPath::Path & value0)
 {
+    auto & value = value0.s;
     auto i = searchPathResolved.find(value);
     if (i != searchPathResolved.end()) return i->second;
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 5dfad470a..b98b06db9 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -1656,9 +1656,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 },
         });
     }
 
@@ -4319,12 +4319,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));