Get rid of the old eval cache

2 files changed, 501 insertions, 94 deletions

diff --git a/src/libexpr/flake/eval-cache.cc b/src/libexpr/flake/eval-cache.cc
index 8d01ef0fc..e17dbde84 100644
--- a/src/libexpr/flake/eval-cache.cc
+++ b/src/libexpr/flake/eval-cache.cc
@@ -1,116 +1,460 @@
 #include "eval-cache.hh"
 #include "sqlite.hh"
 #include "eval.hh"
+#include "eval-inline.hh"
 
-#include <set>
-
-namespace nix::flake {
+namespace nix::eval_cache {
 
+// FIXME: inefficient representation of attrs
 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,
+    parent      integer not null,
+    name        text,
+    type        integer not null,
     value       text,
-    primary key (fingerprint, attrPath),
-    foreign key (fingerprint) references Fingerprints(fingerprint) on delete cascade
+    primary key (parent, name)
 );
 )sql";
 
-struct EvalCache::State
+struct AttrDb
 {
-    SQLite db;
-    SQLiteStmt insertFingerprint;
-    SQLiteStmt insertAttribute;
-    SQLiteStmt queryAttribute;
-    std::set<Fingerprint> fingerprints;
+    struct State
+    {
+        SQLite db;
+        SQLiteStmt insertAttribute;
+        SQLiteStmt queryAttribute;
+        SQLiteStmt queryAttributes;
+        std::unique_ptr<SQLiteTxn> txn;
+    };
+
+    std::unique_ptr<Sync<State>> _state;
+
+    AttrDb(const Hash & fingerprint)
+        : _state(std::make_unique<Sync<State>>())
+    {
+        auto state(_state->lock());
+
+        Path cacheDir = getCacheDir() + "/nix/eval-cache-v1";
+        createDirs(cacheDir);
+
+        Path dbPath = cacheDir + "/" + fingerprint.to_string(Base16, false) + ".sqlite";
+
+        state->db = SQLite(dbPath);
+        state->db.isCache();
+        state->db.exec(schema);
+
+        state->insertAttribute.create(state->db,
+            "insert or replace into Attributes(parent, name, type, value) values (?, ?, ?, ?)");
+
+        state->queryAttribute.create(state->db,
+            "select rowid, type, value from Attributes where parent = ? and name = ?");
+
+        state->queryAttributes.create(state->db,
+            "select name from Attributes where parent = ?");
+
+        state->txn = std::make_unique<SQLiteTxn>(state->db);
+    }
+
+    ~AttrDb()
+    {
+        try {
+            auto state(_state->lock());
+            state->txn->commit();
+            state->txn.reset();
+        } catch (...) {
+            ignoreException();
+        }
+    }
+
+    AttrId setAttrs(
+        AttrKey key,
+        const std::vector<Symbol> & attrs)
+    {
+        auto state(_state->lock());
+
+        state->insertAttribute.use()
+            (key.first)
+            (key.second)
+            (AttrType::FullAttrs)
+            (0, false).exec();
+
+        AttrId rowId = state->db.getLastInsertedRowId();
+        assert(rowId);
+
+        for (auto & attr : attrs)
+            state->insertAttribute.use()
+                (rowId)
+                (attr)
+                (AttrType::Placeholder)
+                (0, false).exec();
+
+        return rowId;
+    }
+
+    AttrId setString(
+        AttrKey key,
+        std::string_view s)
+    {
+        auto state(_state->lock());
+
+        state->insertAttribute.use()
+            (key.first)
+            (key.second)
+            (AttrType::String)
+            (s).exec();
+
+        return state->db.getLastInsertedRowId();
+    }
+
+    AttrId setPlaceholder(AttrKey key)
+    {
+        auto state(_state->lock());
+
+        state->insertAttribute.use()
+            (key.first)
+            (key.second)
+            (AttrType::Placeholder)
+            (0, false).exec();
+
+        return state->db.getLastInsertedRowId();
+    }
+
+    AttrId setMissing(AttrKey key)
+    {
+        auto state(_state->lock());
+
+        state->insertAttribute.use()
+            (key.first)
+            (key.second)
+            (AttrType::Missing)
+            (0, false).exec();
+
+        return state->db.getLastInsertedRowId();
+    }
+
+    AttrId setMisc(AttrKey key)
+    {
+        auto state(_state->lock());
+
+        state->insertAttribute.use()
+            (key.first)
+            (key.second)
+            (AttrType::Misc)
+            (0, false).exec();
+
+        return state->db.getLastInsertedRowId();
+    }
+
+    AttrId setFailed(AttrKey key)
+    {
+        auto state(_state->lock());
+
+        state->insertAttribute.use()
+            (key.first)
+            (key.second)
+            (AttrType::Failed)
+            (0, false).exec();
+
+        return state->db.getLastInsertedRowId();
+    }
+
+    std::optional<std::pair<AttrId, AttrValue>> getAttr(
+        AttrKey key,
+        SymbolTable & symbols)
+    {
+        auto state(_state->lock());
+
+        auto queryAttribute(state->queryAttribute.use()(key.first)(key.second));
+        if (!queryAttribute.next()) return {};
+
+        auto rowId = (AttrType) queryAttribute.getInt(0);
+        auto type = (AttrType) queryAttribute.getInt(1);
+
+        if (type == AttrType::Placeholder)
+            return {{rowId, placeholder_t()}};
+        else if (type == AttrType::FullAttrs) {
+            // FIXME: expensive, should separate this out.
+            std::vector<Symbol> attrs;
+            auto queryAttributes(state->queryAttributes.use()(rowId));
+            while (queryAttributes.next())
+                attrs.push_back(symbols.create(queryAttributes.getStr(0)));
+            return {{rowId, attrs}};
+        } else if (type == AttrType::String) {
+            return {{rowId, queryAttribute.getStr(2)}};
+        } else if (type == AttrType::Missing) {
+            return {{rowId, missing_t()}};
+        } else if (type == AttrType::Misc) {
+            return {{rowId, misc_t()}};
+        } else if (type == AttrType::Failed) {
+            return {{rowId, failed_t()}};
+        } else
+            throw Error("unexpected type in evaluation cache");
+    }
 };
 
-EvalCache::EvalCache()
-    : _state(std::make_unique<Sync<State>>())
+EvalCache::EvalCache(
+    bool useCache,
+    const Hash & fingerprint,
+    EvalState & state,
+    RootLoader rootLoader)
+    : db(useCache ? std::make_shared<AttrDb>(fingerprint) : nullptr)
+    , state(state)
+    , rootLoader(rootLoader)
+{
+}
+
+Value * EvalCache::getRootValue()
+{
+    if (!value) {
+        debug("getting root value");
+        value = allocRootValue(rootLoader());
+    }
+    return *value;
+}
+
+std::shared_ptr<AttrCursor> EvalCache::getRoot()
 {
-    auto state(_state->lock());
+    return std::make_shared<AttrCursor>(ref(shared_from_this()), std::nullopt);
+}
 
-    Path dbPath = getCacheDir() + "/nix/eval-cache-v1.sqlite";
-    createDirs(dirOf(dbPath));
+AttrCursor::AttrCursor(
+    ref<EvalCache> root,
+    Parent parent,
+    Value * value,
+    std::optional<std::pair<AttrId, AttrValue>> && cachedValue)
+    : root(root), parent(parent), cachedValue(std::move(cachedValue))
+{
+    if (value)
+        _value = allocRootValue(value);
+}
 
-    state->db = SQLite(dbPath);
-    state->db.isCache();
-    state->db.exec(schema);
+AttrKey AttrCursor::getKey()
+{
+    if (!parent)
+        return {0, root->state.sEpsilon};
+    if (!parent->first->cachedValue) {
+        parent->first->cachedValue = root->db->getAttr(
+            parent->first->getKey(), root->state.symbols);
+        assert(parent->first->cachedValue);
+    }
+    return {parent->first->cachedValue->first, parent->second};
+}
 
-    state->insertFingerprint.create(state->db,
-        "insert or ignore into Fingerprints(fingerprint, timestamp) values (?, ?)");
+Value & AttrCursor::getValue()
+{
+    if (!_value) {
+        if (parent) {
+            auto & vParent = parent->first->getValue();
+            root->state.forceAttrs(vParent);
+            auto attr = vParent.attrs->get(parent->second);
+            if (!attr)
+                throw Error("attribute '%s' is unexpectedly missing", getAttrPathStr());
+            _value = allocRootValue(attr->value);
+        } else
+            _value = allocRootValue(root->getRootValue());
+    }
+    return **_value;
+}
+
+std::vector<Symbol> AttrCursor::getAttrPath() const
+{
+    if (parent) {
+        auto attrPath = parent->first->getAttrPath();
+        attrPath.push_back(parent->second);
+        return attrPath;
+    } else
+        return {};
+}
 
-    state->insertAttribute.create(state->db,
-        "insert or replace into Attributes(fingerprint, attrPath, type, value) values (?, ?, ?, ?)");
+std::vector<Symbol> AttrCursor::getAttrPath(Symbol name) const
+{
+    auto attrPath = getAttrPath();
+    attrPath.push_back(name);
+    return attrPath;
+}
 
-    state->queryAttribute.create(state->db,
-        "select type, value from Attributes where fingerprint = ? and attrPath = ?");
+std::string AttrCursor::getAttrPathStr() const
+{
+    return concatStringsSep(".", getAttrPath());
 }
 
-enum ValueType {
-    Derivation = 1,
-};
+std::string AttrCursor::getAttrPathStr(Symbol name) const
+{
+    return concatStringsSep(".", getAttrPath(name));
+}
 
-void EvalCache::addDerivation(
-    const Fingerprint & fingerprint,
-    const std::string & attrPath,
-    const Derivation & drv)
+Value & AttrCursor::forceValue()
 {
-    if (!evalSettings.pureEval) return;
+    debug("evaluating uncached attribute %s", getAttrPathStr());
 
-    auto state(_state->lock());
+    auto & v = getValue();
 
-    if (state->fingerprints.insert(fingerprint).second)
-        // FIXME: update timestamp
-        state->insertFingerprint.use()
-            (fingerprint.hash, fingerprint.hashSize)
-            (time(0)).exec();
+    try {
+        root->state.forceValue(v);
+    } catch (EvalError &) {
+        debug("setting '%s' to failed", getAttrPathStr());
+        if (root->db)
+            cachedValue = {root->db->setFailed(getKey()), failed_t()};
+        throw;
+    }
 
-    state->insertAttribute.use()
-        (fingerprint.hash, fingerprint.hashSize)
-        (attrPath)
-        (ValueType::Derivation)
-        (std::string(drv.drvPath.to_string()) + " " + std::string(drv.outPath.to_string()) + " " + drv.outputName).exec();
+    if (root->db && (!cachedValue || std::get_if<placeholder_t>(&cachedValue->second))) {
+        if (v.type == tString)
+            cachedValue = {root->db->setString(getKey(), v.string.s), v.string.s};
+        else if (v.type == tAttrs)
+            ; // FIXME: do something?
+        else
+            cachedValue = {root->db->setMisc(getKey()), misc_t()};
+    }
+
+    return v;
 }
 
-std::optional<EvalCache::Derivation> EvalCache::getDerivation(
-    const Fingerprint & fingerprint,
-    const std::string & attrPath)
+std::shared_ptr<AttrCursor> AttrCursor::maybeGetAttr(Symbol name)
 {
-    if (!evalSettings.pureEval) return {};
+    if (root->db) {
+        if (!cachedValue)
+            cachedValue = root->db->getAttr(getKey(), root->state.symbols);
+
+        if (cachedValue) {
+            if (auto attrs = std::get_if<std::vector<Symbol>>(&cachedValue->second)) {
+                for (auto & attr : *attrs)
+                    if (attr == name)
+                        return std::make_shared<AttrCursor>(root, std::make_pair(shared_from_this(), name));
+                return nullptr;
+            } else if (std::get_if<placeholder_t>(&cachedValue->second)) {
+                auto attr = root->db->getAttr({cachedValue->first, name}, root->state.symbols);
+                if (attr) {
+                    if (std::get_if<missing_t>(&attr->second))
+                        return nullptr;
+                    else if (std::get_if<failed_t>(&attr->second))
+                        throw EvalError("cached failure of attribute '%s'", getAttrPathStr(name));
+                    else
+                        return std::make_shared<AttrCursor>(root,
+                            std::make_pair(shared_from_this(), name), nullptr, std::move(attr));
+                }
+                // Incomplete attrset, so need to fall thru and
+                // evaluate to see whether 'name' exists
+            } else
+                return nullptr;
+                //throw TypeError("'%s' is not an attribute set", getAttrPathStr());
+        }
+    }
+
+    auto & v = forceValue();
+
+    if (v.type != tAttrs)
+        return nullptr;
+        //throw TypeError("'%s' is not an attribute set", getAttrPathStr());
+
+    auto attr = v.attrs->get(name);
 
-    auto state(_state->lock());
+    if (!attr) {
+        if (root->db) {
+            if (!cachedValue)
+                cachedValue = {root->db->setPlaceholder(getKey()), placeholder_t()};
+            root->db->setMissing({cachedValue->first, name});
+        }
+        return nullptr;
+    }
 
-    auto queryAttribute(state->queryAttribute.use()
-        (fingerprint.hash, fingerprint.hashSize)
-        (attrPath));
-    if (!queryAttribute.next()) return {};
+    std::optional<std::pair<AttrId, AttrValue>> cachedValue2;
+    if (root->db) {
+        if (!cachedValue)
+            cachedValue = {root->db->setPlaceholder(getKey()), placeholder_t()};
+        cachedValue2 = {root->db->setPlaceholder({cachedValue->first, name}), placeholder_t()};
+    }
 
-    // FIXME: handle negative results
+    return std::make_shared<AttrCursor>(
+        root, std::make_pair(shared_from_this(), name), attr->value, std::move(cachedValue2));
+}
+
+std::shared_ptr<AttrCursor> AttrCursor::maybeGetAttr(std::string_view name)
+{
+    return maybeGetAttr(root->state.symbols.create(name));
+}
+
+std::shared_ptr<AttrCursor> AttrCursor::getAttr(Symbol name)
+{
+    auto p = maybeGetAttr(name);
+    if (!p)
+        throw Error("attribute '%s' does not exist", getAttrPathStr(name));
+    return p;
+}
+
+std::shared_ptr<AttrCursor> AttrCursor::getAttr(std::string_view name)
+{
+    return getAttr(root->state.symbols.create(name));
+}
+
+std::shared_ptr<AttrCursor> AttrCursor::findAlongAttrPath(const std::vector<Symbol> & attrPath)
+{
+    auto res = shared_from_this();
+    for (auto & attr : attrPath) {
+        res = res->maybeGetAttr(attr);
+        if (!res) return {};
+    }
+    return res;
+}
+
+std::string AttrCursor::getString()
+{
+    if (root->db) {
+        if (!cachedValue)
+            cachedValue = root->db->getAttr(getKey(), root->state.symbols);
+        if (cachedValue && !std::get_if<placeholder_t>(&cachedValue->second)) {
+            if (auto s = std::get_if<std::string>(&cachedValue->second)) {
+                debug("using cached string attribute '%s'", getAttrPathStr());
+                return *s;
+            } else
+                throw TypeError("'%s' is not a string", getAttrPathStr());
+        }
+    }
+
+    auto & v = forceValue();
+
+    if (v.type != tString)
+        throw TypeError("'%s' is not a string", getAttrPathStr());
+
+    return v.string.s;
+}
+
+std::vector<Symbol> AttrCursor::getAttrs()
+{
+    if (root->db) {
+        if (!cachedValue)
+            cachedValue = root->db->getAttr(getKey(), root->state.symbols);
+        if (cachedValue && !std::get_if<placeholder_t>(&cachedValue->second)) {
+            if (auto attrs = std::get_if<std::vector<Symbol>>(&cachedValue->second)) {
+                debug("using cached attrset attribute '%s'", getAttrPathStr());
+                return *attrs;
+            } else
+                throw TypeError("'%s' is not an attribute set", getAttrPathStr());
+        }
+    }
 
-    auto type = (ValueType) queryAttribute.getInt(0);
-    auto s = queryAttribute.getStr(1);
+    auto & v = forceValue();
 
-    if (type != ValueType::Derivation) return {};
+    if (v.type != tAttrs)
+        throw TypeError("'%s' is not an attribute set", getAttrPathStr());
 
-    auto ss = tokenizeString<std::vector<std::string>>(s, " ");
+    std::vector<Symbol> attrs;
+    for (auto & attr : *getValue().attrs)
+        attrs.push_back(attr.name);
+    std::sort(attrs.begin(), attrs.end(), [](const Symbol & a, const Symbol & b) {
+        return (const string &) a < (const string &) b;
+    });
 
-    debug("evaluation cache hit for '%s'", attrPath);
+    if (root->db)
+        cachedValue = {root->db->setAttrs(getKey(), attrs), attrs};
 
-    return Derivation { StorePath::fromBaseName(ss[0]), StorePath::fromBaseName(ss[1]), ss[2] };
+    return attrs;
 }
 
-EvalCache & EvalCache::singleton()
+bool AttrCursor::isDerivation()
 {
-    static std::unique_ptr<EvalCache> evalCache(new EvalCache());
-    return *evalCache;
+    auto aType = maybeGetAttr("type");
+    return aType && aType->getString() == "derivation";
 }
 
 }
diff --git a/src/libexpr/flake/eval-cache.hh b/src/libexpr/flake/eval-cache.hh
index f81d48ba5..a2c21b6ea 100644
--- a/src/libexpr/flake/eval-cache.hh
+++ b/src/libexpr/flake/eval-cache.hh
@@ -1,40 +1,103 @@
 #pragma once
 
 #include "sync.hh"
-#include "flake.hh"
-#include "path.hh"
+#include "hash.hh"
+#include "eval.hh"
 
-namespace nix { struct SQLite; struct SQLiteStmt; }
+#include <variant>
 
-namespace nix::flake {
+namespace nix::eval_cache {
 
-class EvalCache
+class AttrDb;
+class AttrCursor;
+
+class EvalCache : public std::enable_shared_from_this<EvalCache>
+{
+    friend class AttrCursor;
+
+    std::shared_ptr<AttrDb> db;
+    EvalState & state;
+    typedef std::function<Value *()> RootLoader;
+    RootLoader rootLoader;
+    RootValue value;
+
+    Value * getRootValue();
+
+public:
+
+    EvalCache(
+        bool useCache,
+        const Hash & fingerprint,
+        EvalState & state,
+        RootLoader rootLoader);
+
+    std::shared_ptr<AttrCursor> getRoot();
+};
+
+enum AttrType {
+    Placeholder = 0,
+    FullAttrs = 1,
+    String = 2,
+    Missing = 3,
+    Misc = 4,
+    Failed = 5,
+};
+
+struct placeholder_t {};
+struct missing_t {};
+struct misc_t {};
+struct failed_t {};
+typedef uint64_t AttrId;
+typedef std::pair<AttrId, Symbol> AttrKey;
+typedef std::variant<std::vector<Symbol>, std::string, placeholder_t, missing_t, misc_t, failed_t> AttrValue;
+
+class AttrCursor : public std::enable_shared_from_this<AttrCursor>
 {
-    struct State;
+    friend class EvalCache;
+
+    ref<EvalCache> root;
+    typedef std::optional<std::pair<std::shared_ptr<AttrCursor>, Symbol>> Parent;
+    Parent parent;
+    RootValue _value;
+    std::optional<std::pair<AttrId, AttrValue>> cachedValue;
 
-    std::unique_ptr<Sync<State>> _state;
+    AttrKey getKey();
 
-    EvalCache();
+    Value & getValue();
 
 public:
 
-    struct Derivation
-    {
-        StorePath drvPath;
-        StorePath outPath;
-        std::string outputName;
-    };
+    AttrCursor(
+        ref<EvalCache> root,
+        Parent parent,
+        Value * value = nullptr,
+        std::optional<std::pair<AttrId, AttrValue>> && cachedValue = {});
+
+    std::vector<Symbol> getAttrPath() const;
+
+    std::vector<Symbol> getAttrPath(Symbol name) const;
+
+    std::string getAttrPathStr() const;
+
+    std::string getAttrPathStr(Symbol name) const;
+
+    std::shared_ptr<AttrCursor> maybeGetAttr(Symbol name);
+
+    std::shared_ptr<AttrCursor> maybeGetAttr(std::string_view name);
+
+    std::shared_ptr<AttrCursor> getAttr(Symbol name);
+
+    std::shared_ptr<AttrCursor> getAttr(std::string_view name);
+
+    std::shared_ptr<AttrCursor> findAlongAttrPath(const std::vector<Symbol> & attrPath);
+
+    std::string getString();
 
-    void addDerivation(
-        const Fingerprint & fingerprint,
-        const std::string & attrPath,
-        const Derivation & drv);
+    std::vector<Symbol> getAttrs();
 
-    std::optional<Derivation> getDerivation(
-        const Fingerprint & fingerprint,
-        const std::string & attrPath);
+    bool isDerivation();
 
-    static EvalCache & singleton();
+    Value & forceValue();
 };
 
 }