Add flake evaluation cache

This exploits the hermetic nature of flake evaluation to speed up
repeated evaluations of a flake output attribute.

For example (doing 'nix build' on an already present package):

  $ time nix build nixpkgs:firefox

  real    0m1.497s
  user    0m1.160s
  sys     0m0.139s

  $ time nix build nixpkgs:firefox

  real    0m0.052s
  user    0m0.038s
  sys     0m0.007s

The cache is ~/.cache/nix/eval-cache-v1.sqlite, which has entries like

  INSERT INTO Attributes VALUES(
    X'92a907d4efe933af2a46959b082cdff176aa5bfeb47a98fabd234809a67ab195',
    'packages.firefox',
    1,
    '/nix/store/pbalzf8x19hckr8cwdv62rd6g0lqgc38-firefox-67.0.drv /nix/store/g6q0gx0v6xvdnizp8lrcw7c4gdkzana0-firefox-67.0 out');

where the hash 92a9... is a fingerprint over the flake store path and
the contents of the lockfile. Because flakes are evaluated in pure
mode, this uniquely identifies the evaluation result.

4 files changed, 165 insertions, 0 deletions

diff --git a/src/libexpr/flake/eval-cache.cc b/src/libexpr/flake/eval-cache.cc
new file mode 100644
index 000000000..fece1a2b5
--- /dev/null
+++ b/src/libexpr/flake/eval-cache.cc
@@ -0,0 +1,111 @@
+#include "eval-cache.hh"
+#include "sqlite.hh"
+
+#include <set>
+
+namespace nix::flake {
+
+static const char * schema = R"sql(
+
+create table if not exists Fingerprints (
+    fingerprint blob primary key not null,
+    timestamp   integer not null
+);
+
+create table if not exists Attributes (
+    fingerprint blob not null,
+    attrPath    text not null,
+    type        integer,
+    value       text,
+    primary key (fingerprint, attrPath),
+    foreign key (fingerprint) references Fingerprints(fingerprint) on delete cascade
+);
+)sql";
+
+struct EvalCache::State
+{
+    SQLite db;
+    SQLiteStmt insertFingerprint;
+    SQLiteStmt insertAttribute;
+    SQLiteStmt queryAttribute;
+    std::set<Fingerprint> fingerprints;
+};
+
+EvalCache::EvalCache()
+    : _state(std::make_unique<Sync<State>>())
+{
+    auto state(_state->lock());
+
+    Path dbPath = getCacheDir() + "/nix/eval-cache-v1.sqlite";
+    createDirs(dirOf(dbPath));
+
+    state->db = SQLite(dbPath);
+    state->db.isCache();
+    state->db.exec(schema);
+
+    state->insertFingerprint.create(state->db,
+        "insert or ignore into Fingerprints(fingerprint, timestamp) values (?, ?)");
+
+    state->insertAttribute.create(state->db,
+        "insert or replace into Attributes(fingerprint, attrPath, type, value) values (?, ?, ?, ?)");
+
+    state->queryAttribute.create(state->db,
+        "select type, value from Attributes where fingerprint = ? and attrPath = ?");
+}
+
+enum ValueType {
+    Derivation = 1,
+};
+
+void EvalCache::addDerivation(
+    const Fingerprint & fingerprint,
+    const std::string & attrPath,
+    const Derivation & drv)
+{
+    auto state(_state->lock());
+
+    if (state->fingerprints.insert(fingerprint).second)
+        // FIXME: update timestamp
+        state->insertFingerprint.use()
+            (fingerprint.hash, fingerprint.hashSize)
+            (time(0)).exec();
+
+    state->insertAttribute.use()
+        (fingerprint.hash, fingerprint.hashSize)
+        (attrPath)
+        (ValueType::Derivation)
+        (drv.drvPath + " " + drv.outPath + " " + drv.outputName).exec();
+}
+
+std::optional<EvalCache::Derivation> EvalCache::getDerivation(
+    const Fingerprint & fingerprint,
+    const std::string & attrPath)
+{
+    auto state(_state->lock());
+
+    auto queryAttribute(state->queryAttribute.use()
+        (fingerprint.hash, fingerprint.hashSize)
+        (attrPath));
+    if (!queryAttribute.next()) return {};
+
+    // FIXME: handle negative results
+
+    auto type = (ValueType) queryAttribute.getInt(0);
+    auto s = queryAttribute.getStr(1);
+
+    if (type != ValueType::Derivation) return {};
+
+    auto ss = tokenizeString<std::vector<std::string>>(s, " ");
+
+    debug("evaluation cache hit for '%s'", attrPath);
+
+    return Derivation { ss[0], ss[1], ss[2] };
+}
+
+EvalCache & EvalCache::singleton()
+{
+    static std::unique_ptr<EvalCache> evalCache(new EvalCache());
+    return *evalCache;
+}
+
+}
diff --git a/src/libexpr/flake/eval-cache.hh b/src/libexpr/flake/eval-cache.hh
new file mode 100644
index 000000000..03aea142e
--- /dev/null
+++ b/src/libexpr/flake/eval-cache.hh
@@ -0,0 +1,39 @@
+#pragma once
+
+#include "sync.hh"
+#include "flake.hh"
+
+namespace nix { struct SQLite; struct SQLiteStmt; }
+
+namespace nix::flake {
+
+class EvalCache
+{
+    struct State;
+
+    std::unique_ptr<Sync<State>> _state;
+
+    EvalCache();
+
+public:
+
+    struct Derivation
+    {
+        Path drvPath;
+        Path outPath;
+        std::string outputName;
+    };
+
+    void addDerivation(
+        const Fingerprint & fingerprint,
+        const std::string & attrPath,
+        const Derivation & drv);
+
+    std::optional<Derivation> getDerivation(
+        const Fingerprint & fingerprint,
+        const std::string & attrPath);
+
+    static EvalCache & singleton();
+};
+
+}
diff --git a/src/libexpr/flake/flake.cc b/src/libexpr/flake/flake.cc
index bb0543541..0018a0d07 100644
--- a/src/libexpr/flake/flake.cc
+++ b/src/libexpr/flake/flake.cc
@@ -601,4 +601,13 @@ const Registries EvalState::getFlakeRegistries()
     return registries;
 }
 
+Fingerprint ResolvedFlake::getFingerprint() const
+{
+    // FIXME: as an optimization, if the flake contains a lockfile and
+    // we haven't changed it, then it's sufficient to use
+    // flake.sourceInfo.storePath for the fingerprint.
+    return hashString(htSHA256,
+        fmt("%s;%s", flake.sourceInfo.storePath, lockFile));
+}
+
 }
diff --git a/src/libexpr/flake/flake.hh b/src/libexpr/flake/flake.hh
index b8d0da252..81b6541f0 100644
--- a/src/libexpr/flake/flake.hh
+++ b/src/libexpr/flake/flake.hh
@@ -83,12 +83,18 @@ struct NonFlake
 
 Flake getFlake(EvalState &, const FlakeRef &, bool impureIsAllowed);
 
+/* Fingerprint of a locked flake; used as a cache key. */
+typedef Hash Fingerprint;
+
 struct ResolvedFlake
 {
     Flake flake;
     LockFile lockFile;
+
     ResolvedFlake(Flake && flake, LockFile && lockFile)
         : flake(flake), lockFile(lockFile) {}
+
+    Fingerprint getFingerprint() const;
 };
 
 ResolvedFlake resolveFlake(EvalState &, const FlakeRef &, HandleLockFile);