Improve flake references

8 files changed, 378 insertions, 58 deletions

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index e3a264277..548eef31b 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -7,6 +7,7 @@
 #include "eval-inline.hh"
 #include "download.hh"
 #include "json.hh"
+#include "primops/flake.hh"
 
 #include <algorithm>
 #include <cstring>
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index c8ee63551..35c01b97a 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -17,6 +17,7 @@ namespace nix {
 class Store;
 class EvalState;
 enum RepairFlag : bool;
+struct FlakeRegistry;
 
 
 typedef void (* PrimOpFun) (EvalState & state, const Pos & pos, Value * * args, Value & v);
@@ -315,15 +316,6 @@ private:
 
 public:
 
-    struct FlakeRegistry
-    {
-        struct Entry
-        {
-            std::string uri;
-        };
-        std::map<std::string, Entry> entries;
-    };
-
     const FlakeRegistry & getFlakeRegistry();
 
 private:
diff --git a/src/libexpr/primops/fetchGit.cc b/src/libexpr/primops/fetchGit.cc
index 3027e0f2d..62e9dfc0e 100644
--- a/src/libexpr/primops/fetchGit.cc
+++ b/src/libexpr/primops/fetchGit.cc
@@ -16,7 +16,7 @@ using namespace std::string_literals;
 
 namespace nix {
 
-std::regex revRegex("^[0-9a-fA-F]{40}$");
+extern std::regex revRegex;
 
 GitInfo exportGit(ref<Store> store, const std::string & uri,
     std::optional<std::string> ref, std::string rev,
diff --git a/src/libexpr/primops/fetchGit.hh b/src/libexpr/primops/fetchGit.hh
index 6031e09e1..d7a0e165a 100644
--- a/src/libexpr/primops/fetchGit.hh
+++ b/src/libexpr/primops/fetchGit.hh
@@ -18,6 +18,4 @@ GitInfo exportGit(ref<Store> store, const std::string & uri,
     std::optional<std::string> ref, std::string rev,
     const std::string & name);
 
-extern std::regex revRegex;
-
 }
diff --git a/src/libexpr/primops/flake.cc b/src/libexpr/primops/flake.cc
index 1367fa420..5e92b1da3 100644
--- a/src/libexpr/primops/flake.cc
+++ b/src/libexpr/primops/flake.cc
@@ -1,3 +1,4 @@
+#include "flake.hh"
 #include "primops.hh"
 #include "eval-inline.hh"
 #include "fetchGit.hh"
@@ -9,7 +10,7 @@
 
 namespace nix {
 
-const EvalState::FlakeRegistry & EvalState::getFlakeRegistry()
+const FlakeRegistry & EvalState::getFlakeRegistry()
 {
     std::call_once(_flakeRegistryInit, [&]()
     {
@@ -33,10 +34,7 @@ const EvalState::FlakeRegistry & EvalState::getFlakeRegistry()
 
             auto flakes = json["flakes"];
             for (auto i = flakes.begin(); i != flakes.end(); ++i) {
-                FlakeRegistry::Entry entry;
-                entry.uri = i->value("uri", "");
-                if (entry.uri.empty())
-                    throw Error("invalid flake registry entry");
+                FlakeRegistry::Entry entry{FlakeRef(i->value("uri", ""))};
                 _flakeRegistry->entries.emplace(i.key(), entry);
             }
         }
@@ -54,7 +52,7 @@ static void prim_flakeRegistry(EvalState & state, const Pos & pos, Value * * arg
     for (auto & entry : registry.entries) {
         auto vEntry = state.allocAttr(v, entry.first);
         state.mkAttrs(*vEntry, 2);
-        mkString(*state.allocAttr(*vEntry, state.symbols.create("uri")), entry.second.uri);
+        mkString(*state.allocAttr(*vEntry, state.symbols.create("uri")), entry.second.ref.to_string());
         vEntry->attrs->sort();
     }
 
@@ -63,44 +61,53 @@ static void prim_flakeRegistry(EvalState & state, const Pos & pos, Value * * arg
 
 static RegisterPrimOp r1("__flakeRegistry", 0, prim_flakeRegistry);
 
+static FlakeRef lookupFlake(EvalState & state, const FlakeRef & flakeRef)
+{
+    if (auto refData = std::get_if<FlakeRef::IsFlakeId>(&flakeRef.data)) {
+        auto registry = state.getFlakeRegistry();
+        auto i = registry.entries.find(refData->id);
+        if (i == registry.entries.end())
+            throw Error("cannot find flake '%s' in the flake registry", refData->id);
+        auto newRef = FlakeRef(i->second.ref);
+        if (!newRef.isDirect())
+            throw Error("found indirect flake URI '%s' in the flake registry", i->second.ref.to_string());
+        return newRef;
+    } else
+        return flakeRef;
+}
+
 struct Flake
 {
-    std::string name;
+    FlakeId id;
     std::string description;
     Path path;
     std::set<std::string> requires;
     Value * vProvides; // FIXME: gc
+    // commit hash
+    // date
+    // content hash
 };
 
-std::regex flakeRegex("^flake:([a-zA-Z][a-zA-Z0-9_-]*)(/[a-zA-Z][a-zA-Z0-9_.-]*)?$");
-std::regex githubRegex("^github:([a-zA-Z][a-zA-Z0-9_-]*)/([a-zA-Z][a-zA-Z0-9_-]*)(/([a-zA-Z][a-zA-Z0-9_-]*))?$");
-
-static Path fetchFlake(EvalState & state, const std::string & flakeUri)
+static Path fetchFlake(EvalState & state, const FlakeRef & flakeRef)
 {
-    std::smatch match;
-
-    if (std::regex_match(flakeUri, match, flakeRegex)) {
-        auto flakeName = match[1];
-        auto revOrRef = match[2];
-        auto registry = state.getFlakeRegistry();
-        auto i = registry.entries.find(flakeName);
-        if (i == registry.entries.end())
-            throw Error("unknown flake '%s'", flakeName);
-        return fetchFlake(state, i->second.uri);
-    }
-
-    else if (std::regex_match(flakeUri, match, githubRegex)) {
-        auto owner = match[1];
-        auto repo = match[2];
-        auto revOrRef = match[4].str();
-        if (revOrRef.empty()) revOrRef = "master";
+    assert(flakeRef.isDirect());
 
+    if (auto refData = std::get_if<FlakeRef::IsGitHub>(&flakeRef.data)) {
         // FIXME: require hash in pure mode.
 
         // FIXME: use regular /archive URLs instead? api.github.com
         // might have stricter rate limits.
+
+        // FIXME: support passing auth tokens for private repos.
+
         auto storePath = getDownloader()->downloadCached(state.store,
-            fmt("https://api.github.com/repos/%s/%s/tarball/%s", owner, repo, revOrRef),
+            fmt("https://api.github.com/repos/%s/%s/tarball/%s",
+                refData->owner, refData->repo,
+                refData->rev
+                  ? refData->rev->to_string(Base16, false)
+                  : refData->ref
+                    ? *refData->ref
+                    : "master"),
             true, "source");
 
         // FIXME: extract revision hash from ETag.
@@ -108,18 +115,18 @@ static Path fetchFlake(EvalState & state, const std::string & flakeUri)
         return storePath;
     }
 
-    else if (hasPrefix(flakeUri, "/") || hasPrefix(flakeUri, "git://")) {
-        auto gitInfo = exportGit(state.store, flakeUri, {}, "", "source");
+    else if (auto refData = std::get_if<FlakeRef::IsGit>(&flakeRef.data)) {
+        auto gitInfo = exportGit(state.store, refData->uri, refData->ref,
+            refData->rev ? refData->rev->to_string(Base16, false) : "", "source");
         return gitInfo.storePath;
     }
 
-    else
-        throw Error("unsupported flake URI '%s'", flakeUri);
+    else abort();
 }
 
-static Flake getFlake(EvalState & state, const std::string & flakeUri)
+static Flake getFlake(EvalState & state, const FlakeRef & flakeRef)
 {
-    auto flakePath = fetchFlake(state, flakeUri);
+    auto flakePath = fetchFlake(state, flakeRef);
     state.store->assertStorePath(flakePath);
 
     Flake flake;
@@ -130,7 +137,7 @@ static Flake getFlake(EvalState & state, const std::string & flakeUri)
     state.forceAttrs(vInfo);
 
     if (auto name = vInfo.attrs->get(state.sName))
-        flake.name = state.forceStringNoCtx(*(**name).value, *(**name).pos);
+        flake.id = state.forceStringNoCtx(*(**name).value, *(**name).pos);
     else
         throw Error("flake lacks attribute 'name'");
 
@@ -153,23 +160,31 @@ static Flake getFlake(EvalState & state, const std::string & flakeUri)
     return flake;
 }
 
-static std::map<std::string, Flake> resolveFlakes(EvalState & state, const StringSet & flakeUris)
+/* Given a set of flake references, recursively fetch them and their
+   dependencies. */
+static std::map<FlakeId, Flake> resolveFlakes(EvalState & state, const std::vector<FlakeRef> & flakeRefs)
 {
-    std::map<std::string, Flake> done;
-    std::queue<std::string> todo;
-    for (auto & i : flakeUris) todo.push(i);
+    std::map<FlakeId, Flake> done;
+    std::queue<FlakeRef> todo;
+    for (auto & i : flakeRefs) todo.push(i);
 
     while (!todo.empty()) {
-        auto flakeUri = todo.front();
+        auto flakeRef = todo.front();
         todo.pop();
-        if (done.count(flakeUri)) continue;
 
-        auto flake = getFlake(state, flakeUri);
+        if (auto refData = std::get_if<FlakeRef::IsFlakeId>(&flakeRef.data)) {
+            if (done.count(refData->id)) continue; // optimization
+            flakeRef = lookupFlake(state, flakeRef);
+        }
+
+        auto flake = getFlake(state, flakeRef);
+
+        if (done.count(flake.id)) continue;
 
         for (auto & require : flake.requires)
             todo.push(require);
 
-        done.emplace(flake.name, flake);
+        done.emplace(flake.id, flake);
     }
 
     return done;
@@ -177,7 +192,7 @@ static std::map<std::string, Flake> resolveFlakes(EvalState & state, const Strin
 
 static void prim_getFlake(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
-    std::string flakeUri = state.forceStringNoCtx(*args[0], pos);
+    auto flakeUri = FlakeRef(state.forceStringNoCtx(*args[0], pos));
 
     auto flakes = resolveFlakes(state, {flakeUri});
 
@@ -186,7 +201,7 @@ static void prim_getFlake(EvalState & state, const Pos & pos, Value * * args, Va
     state.mkAttrs(*vResult, flakes.size());
 
     for (auto & flake : flakes) {
-        auto vFlake = state.allocAttr(*vResult, flake.second.name);
+        auto vFlake = state.allocAttr(*vResult, flake.second.id);
         state.mkAttrs(*vFlake, 2);
         mkString(*state.allocAttr(*vFlake, state.sDescription), flake.second.description);
         auto vProvides = state.allocAttr(*vFlake, state.symbols.create("provides"));
diff --git a/src/libexpr/primops/flake.hh b/src/libexpr/primops/flake.hh
new file mode 100644
index 000000000..6be6e99d2
--- /dev/null
+++ b/src/libexpr/primops/flake.hh
@@ -0,0 +1,17 @@
+#include "types.hh"
+#include "flakeref.hh"
+
+#include <variant>
+
+namespace nix {
+
+struct FlakeRegistry
+{
+    struct Entry
+    {
+        FlakeRef ref;
+    };
+    std::map<FlakeId, Entry> entries;
+};
+
+}
diff --git a/src/libexpr/primops/flakeref.cc b/src/libexpr/primops/flakeref.cc
new file mode 100644
index 000000000..447b56822
--- /dev/null
+++ b/src/libexpr/primops/flakeref.cc
@@ -0,0 +1,139 @@
+#include "flakeref.hh"
+
+#include <regex>
+
+namespace nix {
+
+// A Git ref (i.e. branch or tag name).
+const static std::string refRegex = "[a-zA-Z][a-zA-Z0-9_.-]*"; // FIXME: check
+
+// A Git revision (a SHA-1 commit hash).
+const static std::string revRegexS = "[0-9a-fA-F]{40}";
+std::regex revRegex(revRegexS, std::regex::ECMAScript);
+
+// A Git ref or revision.
+const static std::string revOrRefRegex = "(?:(" + revRegexS + ")|(" + refRegex + "))";
+
+// A rev ("e72daba8250068216d79d2aeef40d4d95aff6666"), or a ref
+// optionally followed by a rev (e.g. "master" or
+// "master/e72daba8250068216d79d2aeef40d4d95aff6666").
+const static std::string refAndOrRevRegex = "(?:(" + revRegexS + ")|(?:(" + refRegex + ")(?:/(" + revRegexS + "))?))";
+
+const static std::string flakeId = "[a-zA-Z][a-zA-Z0-9_-]*";
+
+// GitHub references.
+const static std::string ownerRegex = "[a-zA-Z][a-zA-Z0-9_-]*";
+const static std::string repoRegex = "[a-zA-Z][a-zA-Z0-9_-]*";
+
+// URI stuff.
+const static std::string schemeRegex = "(?:http|https|ssh|git|file)";
+const static std::string authorityRegex = "[a-zA-Z0-9._~-]*";
+const static std::string segmentRegex = "[a-zA-Z0-9._~-]+";
+const static std::string pathRegex = "/?" + segmentRegex + "(?:/" + segmentRegex + ")*";
+const static std::string paramRegex = "[a-z]+=[a-zA-Z0-9._-]*";
+
+FlakeRef::FlakeRef(const std::string & uri)
+{
+    // FIXME: could combine this into one regex.
+
+    static std::regex flakeRegex(
+        "(?:flake:)?(" + flakeId + ")(?:/(?:" + refAndOrRevRegex + "))?",
+        std::regex::ECMAScript);
+
+    static std::regex githubRegex(
+        "github:(" + ownerRegex + ")/(" + repoRegex + ")(?:/" + revOrRefRegex + ")?",
+        std::regex::ECMAScript);
+
+    static std::regex uriRegex(
+        "((" + schemeRegex + "):" +
+        "(?://(" + authorityRegex + "))?" +
+        "(" + pathRegex + "))" +
+        "(?:[?](" + paramRegex + "(?:&" + paramRegex + ")*))?",
+        std::regex::ECMAScript);
+
+    static std::regex refRegex2(refRegex, std::regex::ECMAScript);
+
+    std::cmatch match;
+    if (std::regex_match(uri.c_str(), match, flakeRegex)) {
+        IsFlakeId d;
+        d.id = match[1];
+        if (match[2].matched)
+            d.rev = Hash(match[2], htSHA1);
+        else if (match[3].matched) {
+            d.ref = match[3];
+            if (match[4].matched)
+                d.rev = Hash(match[4], htSHA1);
+        }
+        data = d;
+    }
+
+    else if (std::regex_match(uri.c_str(), match, githubRegex)) {
+        IsGitHub d;
+        d.owner = match[1];
+        d.repo = match[2];
+        if (match[3].matched)
+            d.rev = Hash(match[3], htSHA1);
+        else if (match[4].matched) {
+            d.ref = match[4];
+        }
+        data = d;
+    }
+
+    else if (std::regex_match(uri.c_str(), match, uriRegex) && hasSuffix(match[4], ".git")) {
+        IsGit d;
+        d.uri = match[1];
+        for (auto & param : tokenizeString<Strings>(match[5], "&")) {
+            auto n = param.find('=');
+            assert(n != param.npos);
+            std::string name(param, 0, n);
+            std::string value(param, n + 1);
+            if (name == "rev") {
+                if (!std::regex_match(value, revRegex))
+                    throw Error("invalid Git revision '%s'", value);
+                d.rev = Hash(value, htSHA1);
+            } else if (name == "ref") {
+                if (!std::regex_match(value, refRegex2))
+                    throw Error("invalid Git ref '%s'", value);
+                d.ref = value;
+            } else
+                // FIXME: should probably pass through unknown parameters
+                throw Error("invalid Git flake reference parameter '%s', in '%s'", name, uri);
+        }
+        if (d.rev && !d.ref)
+            throw Error("flake URI '%s' lacks a Git ref", uri);
+        data = d;
+    }
+
+    else
+        throw Error("'%s' is not a valid flake reference", uri);
+}
+
+std::string FlakeRef::to_string() const
+{
+    if (auto refData = std::get_if<FlakeRef::IsFlakeId>(&data)) {
+        return
+            "flake:" + refData->id +
+            (refData->ref ? "/" + *refData->ref : "") +
+            (refData->rev ? "/" + refData->rev->to_string(Base16, false) : "");
+    }
+
+    else if (auto refData = std::get_if<FlakeRef::IsGitHub>(&data)) {
+        assert(!refData->ref || !refData->rev);
+        return
+            "github:" + refData->owner + "/" + refData->repo +
+            (refData->ref ? "/" + *refData->ref : "") +
+            (refData->rev ? "/" + refData->rev->to_string(Base16, false) : "");
+    }
+
+    else if (auto refData = std::get_if<FlakeRef::IsGit>(&data)) {
+        assert(refData->ref || !refData->rev);
+        return
+            refData->uri +
+            (refData->ref ? "?ref=" + *refData->ref : "") +
+            (refData->rev ? "&rev=" + refData->rev->to_string(Base16, false) : "");
+    }
+
+    else abort();
+}
+
+}
diff --git a/src/libexpr/primops/flakeref.hh b/src/libexpr/primops/flakeref.hh
new file mode 100644
index 000000000..8559317e0
--- /dev/null
+++ b/src/libexpr/primops/flakeref.hh
@@ -0,0 +1,158 @@
+#include "types.hh"
+#include "hash.hh"
+
+#include <variant>
+
+namespace nix {
+
+/* Flake references are a URI-like syntax to specify a flake.
+
+   Examples:
+
+   * <flake-id>(/rev-or-ref(/rev)?)?
+
+     Look up a flake by ID in the flake lock file or in the flake
+     registry. These must specify an actual location for the flake
+     using the formats listed below. Note that in pure evaluation
+     mode, the flake registry is empty.
+
+     Optionally, the rev or ref from the dereferenced flake can be
+     overriden. For example,
+
+       nixpkgs/19.09
+
+     uses the "19.09" branch of the nixpkgs' flake GitHub repository,
+     while
+
+       nixpkgs/98a2a5b5370c1e2092d09cb38b9dcff6d98a109f
+
+     uses the specified revision. For Git (rather than GitHub)
+     repositories, both the rev and ref must be given, e.g.
+
+       nixpkgs/19.09/98a2a5b5370c1e2092d09cb38b9dcff6d98a109f
+
+   * github:<owner>/<repo>(/<rev-or-ref>)?
+
+     A repository on GitHub. These differ from Git references in that
+     they're downloaded in a efficient way (via the tarball mechanism)
+     and that they support downloading a specific revision without
+     specifying a branch. <rev-or-ref> is either a commit hash ("rev")
+     or a branch or tag name ("ref"). The default is: "master" if none
+     is specified. Note that in pure evaluation mode, a commit hash
+     must be used.
+
+     Flakes fetched in this manner expose "rev" and "lastModified"
+     attributes, but not "revCount".
+
+     Examples:
+
+       github:edolstra/dwarffs
+       github:edolstra/dwarffs/unstable
+       github:edolstra/dwarffs/41c0c1bf292ea3ac3858ff393b49ca1123dbd553
+
+   * https://<server>/<path>.git(\?attr(&attr)*)?
+     ssh://<server>/<path>.git(\?attr(&attr)*)?
+     git://<server>/<path>.git(\?attr(&attr)*)?
+     file:///<path>(\?attr(&attr)*)?
+
+     where 'attr' is one of:
+       rev=<rev>
+       ref=<ref>
+
+     A Git repository fetched through https. Note that the path must
+     end in ".git". The default for "ref" is "master".
+
+     Examples:
+
+       https://example.org/my/repo.git
+       https://example.org/my/repo.git?ref=release-1.2.3
+       https://example.org/my/repo.git?rev=e72daba8250068216d79d2aeef40d4d95aff6666
+
+   * /path.git(\?attr(&attr)*)?
+
+     Like file://path.git, but if no "ref" or "rev" is specified, the
+     (possibly dirty) working tree will be used. Using a working tree
+     is not allowed in pure evaluation mode.
+
+     Examples:
+
+       /path/to/my/repo
+       /path/to/my/repo?ref=develop
+       /path/to/my/repo?rev=e72daba8250068216d79d2aeef40d4d95aff6666
+
+   * https://<server>/<path>.tar.xz(?hash=<sri-hash>)
+     file:///<path>.tar.xz(?hash=<sri-hash>)
+
+     A flake distributed as a tarball. In pure evaluation mode, an SRI
+     hash is mandatory. It exposes a "lastModified" attribute, being
+     the newest file inside the tarball.
+
+     Example:
+
+       https://releases.nixos.org/nixos/unstable/nixos-19.03pre167858.f2a1a4e93be/nixexprs.tar.xz
+       https://releases.nixos.org/nixos/unstable/nixos-19.03pre167858.f2a1a4e93be/nixexprs.tar.xz?hash=sha256-56bbc099995ea8581ead78f22832fee7dbcb0a0b6319293d8c2d0aef5379397c
+
+  Note: currently, there can be only one flake per Git repository, and
+  it must be at top-level. In the future, we may want to add a field
+  (e.g. "dir=<dir>") to specify a subdirectory inside the repository.
+*/
+
+typedef std::string FlakeId;
+
+struct FlakeRef
+{
+    struct IsFlakeId
+    {
+        FlakeId id;
+        std::optional<std::string> ref;
+        std::optional<Hash> rev;
+    };
+
+    struct IsGitHub
+    {
+        std::string owner, repo;
+        std::optional<std::string> ref;
+        std::optional<Hash> rev;
+    };
+
+    struct IsGit
+    {
+        std::string uri;
+        std::optional<std::string> ref;
+        std::optional<Hash> rev;
+    };
+
+    // Git, Tarball
+
+    std::variant<IsFlakeId, IsGitHub, IsGit> data;
+
+    // Parse a flake URI.
+    FlakeRef(const std::string & uri);
+
+    /* Unify two flake references so that the resulting reference
+       combines the information from both. For example,
+       "nixpkgs/<hash>" and "github:NixOS/nixpkgs" unifies to
+       "nixpkgs/master". May throw an exception if the references are
+       incompatible (e.g. "nixpkgs/<hash1>" and "nixpkgs/<hash2>",
+       where hash1 != hash2). */
+    FlakeRef(const FlakeRef & a, const FlakeRef & b);
+
+    // FIXME: change to operator <<.
+    std::string to_string() const;
+
+    /* Check whether this is a "direct" flake reference, that is, not
+       a flake ID, which requires a lookup in the flake registry. */
+    bool isDirect() const
+    {
+        return !std::get_if<FlakeRef::IsFlakeId>(&data);
+    }
+
+    /* Check whether this is an "immutable" flake reference, that is,
+       one that contains a commit hash or content hash. */
+    bool isImmutable() const
+    {
+        abort(); // TODO
+    }
+};
+
+}