20 files changed, 2341 insertions, 60 deletions

diff --git a/src/libexpr/common-eval-args.cc b/src/libexpr/common-eval-args.cc
index 44baadd53..6b48ead1f 100644
--- a/src/libexpr/common-eval-args.cc
+++ b/src/libexpr/common-eval-args.cc
@@ -4,6 +4,8 @@
 #include "util.hh"
 #include "eval.hh"
 #include "fetchers.hh"
+#include "registry.hh"
+#include "flake/flakeref.hh"
 #include "store-api.hh"
 
 namespace nix {
@@ -31,6 +33,27 @@ MixEvalArgs::MixEvalArgs()
         .labels = {"path"},
         .handler = {[&](std::string s) { searchPath.push_back(s); }}
     });
+
+    addFlag({
+        .longName = "impure",
+        .description = "allow access to mutable paths and repositories",
+        .handler = {[&]() {
+            evalSettings.pureEval = false;
+        }},
+    });
+
+    addFlag({
+        .longName = "override-flake",
+        .description = "override a flake registry value",
+        .labels = {"original-ref", "resolved-ref"},
+        .handler = {[&](std::string _from, std::string _to) {
+            auto from = parseFlakeRef(_from, absPath("."));
+            auto to = parseFlakeRef(_to, absPath("."));
+            fetchers::Attrs extraAttrs;
+            if (to.subdir != "") extraAttrs["dir"] = to.subdir;
+            fetchers::overrideRegistry(from.input, to.input, extraAttrs);
+        }}
+    });
 }
 
 Bindings * MixEvalArgs::getAutoArgs(EvalState & state)
@@ -53,7 +76,7 @@ Path lookupFileArg(EvalState & state, string s)
     if (isUri(s)) {
         return state.store->toRealPath(
             fetchers::downloadTarball(
-                state.store, resolveUri(s), "source", false).storePath);
+                state.store, resolveUri(s), "source", false).first.storePath);
     } else if (s.size() > 2 && s.at(0) == '<' && s.at(s.size() - 1) == '>') {
         Path p = s.substr(1, s.size() - 2);
         return state.findFile(p);
diff --git a/src/libexpr/eval-cache.cc b/src/libexpr/eval-cache.cc
new file mode 100644
index 000000000..deb32484f
--- /dev/null
+++ b/src/libexpr/eval-cache.cc
@@ -0,0 +1,616 @@
+#include "eval-cache.hh"
+#include "sqlite.hh"
+#include "eval.hh"
+#include "eval-inline.hh"
+#include "store-api.hh"
+
+namespace nix::eval_cache {
+
+static const char * schema = R"sql(
+create table if not exists Attributes (
+    parent      integer not null,
+    name        text,
+    type        integer not null,
+    value       text,
+    context     text,
+    primary key (parent, name)
+);
+)sql";
+
+struct AttrDb
+{
+    std::atomic_bool failed{false};
+
+    struct State
+    {
+        SQLite db;
+        SQLiteStmt insertAttribute;
+        SQLiteStmt insertAttributeWithContext;
+        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-v2";
+        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->insertAttributeWithContext.create(state->db,
+            "insert or replace into Attributes(parent, name, type, value, context) values (?, ?, ?, ?, ?)");
+
+        state->queryAttribute.create(state->db,
+            "select rowid, type, value, context 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());
+            if (!failed)
+                state->txn->commit();
+            state->txn.reset();
+        } catch (...) {
+            ignoreException();
+        }
+    }
+
+    template<typename F>
+    AttrId doSQLite(F && fun)
+    {
+        if (failed) return 0;
+        try {
+            return fun();
+        } catch (SQLiteError &) {
+            ignoreException();
+            failed = true;
+            return 0;
+        }
+    }
+
+    AttrId setAttrs(
+        AttrKey key,
+        const std::vector<Symbol> & attrs)
+    {
+        return doSQLite([&]()
+        {
+            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,
+        const char * * context = nullptr)
+    {
+        return doSQLite([&]()
+        {
+            auto state(_state->lock());
+
+            if (context) {
+                std::string ctx;
+                for (const char * * p = context; *p; ++p) {
+                    if (p != context) ctx.push_back(' ');
+                    ctx.append(*p);
+                }
+                state->insertAttributeWithContext.use()
+                    (key.first)
+                    (key.second)
+                    (AttrType::String)
+                    (s)
+                    (ctx).exec();
+            } else {
+                state->insertAttribute.use()
+                    (key.first)
+                    (key.second)
+                    (AttrType::String)
+                (s).exec();
+            }
+
+            return state->db.getLastInsertedRowId();
+        });
+    }
+
+    AttrId setBool(
+        AttrKey key,
+        bool b)
+    {
+        return doSQLite([&]()
+        {
+            auto state(_state->lock());
+
+            state->insertAttribute.use()
+                (key.first)
+                (key.second)
+                (AttrType::Bool)
+                (b ? 1 : 0).exec();
+
+            return state->db.getLastInsertedRowId();
+        });
+    }
+
+    AttrId setPlaceholder(AttrKey key)
+    {
+        return doSQLite([&]()
+        {
+            auto state(_state->lock());
+
+            state->insertAttribute.use()
+                (key.first)
+                (key.second)
+                (AttrType::Placeholder)
+                (0, false).exec();
+
+            return state->db.getLastInsertedRowId();
+        });
+    }
+
+    AttrId setMissing(AttrKey key)
+    {
+        return doSQLite([&]()
+        {
+            auto state(_state->lock());
+
+            state->insertAttribute.use()
+                (key.first)
+                (key.second)
+                (AttrType::Missing)
+                (0, false).exec();
+
+            return state->db.getLastInsertedRowId();
+        });
+    }
+
+    AttrId setMisc(AttrKey key)
+    {
+        return doSQLite([&]()
+        {
+            auto state(_state->lock());
+
+            state->insertAttribute.use()
+                (key.first)
+                (key.second)
+                (AttrType::Misc)
+                (0, false).exec();
+
+            return state->db.getLastInsertedRowId();
+        });
+    }
+
+    AttrId setFailed(AttrKey key)
+    {
+        return doSQLite([&]()
+        {
+            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);
+
+        switch (type) {
+            case AttrType::Placeholder:
+                return {{rowId, placeholder_t()}};
+            case 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}};
+            }
+            case AttrType::String: {
+                std::vector<std::pair<Path, std::string>> context;
+                if (!queryAttribute.isNull(3))
+                    for (auto & s : tokenizeString<std::vector<std::string>>(queryAttribute.getStr(3), ";"))
+                        context.push_back(decodeContext(s));
+                return {{rowId, string_t{queryAttribute.getStr(2), context}}};
+            }
+            case AttrType::Bool:
+                return {{rowId, queryAttribute.getInt(2) != 0}};
+            case AttrType::Missing:
+                return {{rowId, missing_t()}};
+            case AttrType::Misc:
+                return {{rowId, misc_t()}};
+            case AttrType::Failed:
+                return {{rowId, failed_t()}};
+            default:
+                throw Error("unexpected type in evaluation cache");
+        }
+    }
+};
+
+static std::shared_ptr<AttrDb> makeAttrDb(const Hash & fingerprint)
+{
+    try {
+        return std::make_shared<AttrDb>(fingerprint);
+    } catch (SQLiteError &) {
+        ignoreException();
+        return nullptr;
+    }
+}
+
+EvalCache::EvalCache(
+    std::optional<std::reference_wrapper<const Hash>> useCache,
+    EvalState & state,
+    RootLoader rootLoader)
+    : db(useCache ? makeAttrDb(*useCache) : 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()
+{
+    return std::make_shared<AttrCursor>(ref(shared_from_this()), std::nullopt);
+}
+
+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);
+}
+
+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};
+}
+
+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 {};
+}
+
+std::vector<Symbol> AttrCursor::getAttrPath(Symbol name) const
+{
+    auto attrPath = getAttrPath();
+    attrPath.push_back(name);
+    return attrPath;
+}
+
+std::string AttrCursor::getAttrPathStr() const
+{
+    return concatStringsSep(".", getAttrPath());
+}
+
+std::string AttrCursor::getAttrPathStr(Symbol name) const
+{
+    return concatStringsSep(".", getAttrPath(name));
+}
+
+Value & AttrCursor::forceValue()
+{
+    debug("evaluating uncached attribute %s", getAttrPathStr());
+
+    auto & v = getValue();
+
+    try {
+        root->state.forceValue(v);
+    } catch (EvalError &) {
+        debug("setting '%s' to failed", getAttrPathStr());
+        if (root->db)
+            cachedValue = {root->db->setFailed(getKey()), failed_t()};
+        throw;
+    }
+
+    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.context), v.string.s};
+        else if (v.type == tPath)
+            cachedValue = {root->db->setString(getKey(), v.path), v.path};
+        else if (v.type == tBool)
+            cachedValue = {root->db->setBool(getKey(), v.boolean), v.boolean};
+        else if (v.type == tAttrs)
+            ; // FIXME: do something?
+        else
+            cachedValue = {root->db->setMisc(getKey()), misc_t()};
+    }
+
+    return v;
+}
+
+std::shared_ptr<AttrCursor> AttrCursor::maybeGetAttr(Symbol name)
+{
+    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);
+
+    if (!attr) {
+        if (root->db) {
+            if (!cachedValue)
+                cachedValue = {root->db->setPlaceholder(getKey()), placeholder_t()};
+            root->db->setMissing({cachedValue->first, name});
+        }
+        return nullptr;
+    }
+
+    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()};
+    }
+
+    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<string_t>(&cachedValue->second)) {
+                debug("using cached string attribute '%s'", getAttrPathStr());
+                return s->first;
+            } else
+                throw TypeError("'%s' is not a string", getAttrPathStr());
+        }
+    }
+
+    auto & v = forceValue();
+
+    if (v.type != tString && v.type != tPath)
+        throw TypeError("'%s' is not a string but %s", getAttrPathStr(), showType(v.type));
+
+    return v.type == tString ? v.string.s : v.path;
+}
+
+string_t AttrCursor::getStringWithContext()
+{
+    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<string_t>(&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)
+        return {v.string.s, v.getContext()};
+    else if (v.type == tPath)
+        return {v.path, {}};
+    else
+        throw TypeError("'%s' is not a string but %s", getAttrPathStr(), showType(v.type));
+}
+
+bool AttrCursor::getBool()
+{
+    if (root->db) {
+        if (!cachedValue)
+            cachedValue = root->db->getAttr(getKey(), root->state.symbols);
+        if (cachedValue && !std::get_if<placeholder_t>(&cachedValue->second)) {
+            if (auto b = std::get_if<bool>(&cachedValue->second)) {
+                debug("using cached Boolean attribute '%s'", getAttrPathStr());
+                return *b;
+            } else
+                throw TypeError("'%s' is not a Boolean", getAttrPathStr());
+        }
+    }
+
+    auto & v = forceValue();
+
+    if (v.type != tBool)
+        throw TypeError("'%s' is not a Boolean", getAttrPathStr());
+
+    return v.boolean;
+}
+
+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 & v = forceValue();
+
+    if (v.type != tAttrs)
+        throw TypeError("'%s' is not an attribute set", getAttrPathStr());
+
+    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;
+    });
+
+    if (root->db)
+        cachedValue = {root->db->setAttrs(getKey(), attrs), attrs};
+
+    return attrs;
+}
+
+bool AttrCursor::isDerivation()
+{
+    auto aType = maybeGetAttr("type");
+    return aType && aType->getString() == "derivation";
+}
+
+StorePath AttrCursor::forceDerivation()
+{
+    auto aDrvPath = getAttr(root->state.sDrvPath);
+    auto drvPath = root->state.store->parseStorePath(aDrvPath->getString());
+    if (!root->state.store->isValidPath(drvPath) && !settings.readOnlyMode) {
+        /* The eval cache contains 'drvPath', but the actual path has
+           been garbage-collected. So force it to be regenerated. */
+        aDrvPath->forceValue();
+        if (!root->state.store->isValidPath(drvPath))
+            throw Error("don't know how to recreate store derivation '%s'!",
+                root->state.store->printStorePath(drvPath));
+    }
+    return drvPath;
+}
+
+}
diff --git a/src/libexpr/eval-cache.hh b/src/libexpr/eval-cache.hh
new file mode 100644
index 000000000..afee85fa9
--- /dev/null
+++ b/src/libexpr/eval-cache.hh
@@ -0,0 +1,121 @@
+#pragma once
+
+#include "sync.hh"
+#include "hash.hh"
+#include "eval.hh"
+
+#include <functional>
+#include <variant>
+
+namespace nix::eval_cache {
+
+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(
+        std::optional<std::reference_wrapper<const Hash>> useCache,
+        EvalState & state,
+        RootLoader rootLoader);
+
+    std::shared_ptr<AttrCursor> getRoot();
+};
+
+enum AttrType {
+    Placeholder = 0,
+    FullAttrs = 1,
+    String = 2,
+    Missing = 3,
+    Misc = 4,
+    Failed = 5,
+    Bool = 6,
+};
+
+struct placeholder_t {};
+struct missing_t {};
+struct misc_t {};
+struct failed_t {};
+typedef uint64_t AttrId;
+typedef std::pair<AttrId, Symbol> AttrKey;
+typedef std::pair<std::string, std::vector<std::pair<Path, std::string>>> string_t;
+
+typedef std::variant<
+    std::vector<Symbol>,
+    string_t,
+    placeholder_t,
+    missing_t,
+    misc_t,
+    failed_t,
+    bool
+    > AttrValue;
+
+class AttrCursor : public std::enable_shared_from_this<AttrCursor>
+{
+    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;
+
+    AttrKey getKey();
+
+    Value & getValue();
+
+public:
+
+    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();
+
+    string_t getStringWithContext();
+
+    bool getBool();
+
+    std::vector<Symbol> getAttrs();
+
+    bool isDerivation();
+
+    Value & forceValue();
+
+    /* Force creation of the .drv file in the Nix store. */
+    StorePath forceDerivation();
+};
+
+}
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index c1a9af9b2..7a2f55504 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -199,6 +199,18 @@ string showType(const Value & v)
 }
 
 
+bool Value::isTrivial() const
+{
+    return
+        type != tApp
+        && type != tPrimOpApp
+        && (type != tThunk
+            || (dynamic_cast<ExprAttrs *>(thunk.expr)
+                && ((ExprAttrs *) thunk.expr)->dynamicAttrs.empty())
+            || dynamic_cast<ExprLambda *>(thunk.expr));
+}
+
+
 #if HAVE_BOEHMGC
 /* Called when the Boehm GC runs out of memory. */
 static void * oomHandler(size_t requested)
@@ -337,6 +349,9 @@ EvalState::EvalState(const Strings & _searchPath, ref<Store> store)
     , sOutputHashAlgo(symbols.create("outputHashAlgo"))
     , sOutputHashMode(symbols.create("outputHashMode"))
     , sRecurseForDerivations(symbols.create("recurseForDerivations"))
+    , sDescription(symbols.create("description"))
+    , sSelf(symbols.create("self"))
+    , sEpsilon(symbols.create(""))
     , repair(NoRepair)
     , store(store)
     , baseEnv(allocEnv(128))
@@ -366,7 +381,7 @@ EvalState::EvalState(const Strings & _searchPath, ref<Store> store)
 
             if (store->isInStore(r.second)) {
                 StorePathSet closure;
-                store->computeFSClosure(store->parseStorePath(store->toStorePath(r.second)), closure);
+                store->computeFSClosure(store->toStorePath(r.second).first, closure);
                 for (auto & path : closure)
                     allowedPaths->insert(store->printStorePath(path));
             } else
@@ -782,7 +797,7 @@ Value * ExprPath::maybeThunk(EvalState & state, Env & env)
 }
 
 
-void EvalState::evalFile(const Path & path_, Value & v)
+void EvalState::evalFile(const Path & path_, Value & v, bool mustBeTrivial)
 {
     auto path = checkSourcePath(path_);
 
@@ -811,6 +826,11 @@ void EvalState::evalFile(const Path & path_, Value & v)
     fileParseCache[path2] = e;
 
     try {
+        // Enforce that 'flake.nix' is a direct attrset, not a
+        // computation.
+        if (mustBeTrivial &&
+            !(dynamic_cast<ExprAttrs *>(e)))
+            throw Error("file '%s' must be an attribute set", path);
         eval(e, v);
     } catch (Error & e) {
         addErrorTrace(e, "while evaluating the file '%1%':", path2);
@@ -1586,6 +1606,18 @@ string EvalState::forceString(Value & v, const Pos & pos)
 }
 
 
+/* Decode a context string ‘!<name>!<path>’ into a pair <path,
+   name>. */
+std::pair<string, string> decodeContext(std::string_view s)
+{
+    if (s.at(0) == '!') {
+        size_t index = s.find("!", 1);
+        return {std::string(s.substr(index + 1)), std::string(s.substr(1, index - 1))};
+    } else
+        return {s.at(0) == '/' ? std::string(s) : std::string(s.substr(1)), ""};
+}
+
+
 void copyContext(const Value & v, PathSet & context)
 {
     if (v.string.context)
@@ -1594,6 +1626,17 @@ void copyContext(const Value & v, PathSet & context)
 }
 
 
+std::vector<std::pair<Path, std::string>> Value::getContext()
+{
+    std::vector<std::pair<Path, std::string>> res;
+    assert(type == tString);
+    if (string.context)
+        for (const char * * p = string.context; *p; ++p)
+            res.push_back(decodeContext(*p));
+    return res;
+}
+
+
 string EvalState::forceString(Value & v, PathSet & context, const Pos & pos)
 {
     string s = forceString(v, pos);
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 0d52a7f63..8986952e3 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -4,13 +4,13 @@
 #include "value.hh"
 #include "nixexpr.hh"
 #include "symbol-table.hh"
-#include "hash.hh"
 #include "config.hh"
 
 #include <regex>
 #include <map>
 #include <optional>
 #include <unordered_map>
+#include <mutex>
 
 
 namespace nix {
@@ -75,7 +75,8 @@ public:
         sFile, sLine, sColumn, sFunctor, sToString,
         sRight, sWrong, sStructuredAttrs, sBuilder, sArgs,
         sOutputHash, sOutputHashAlgo, sOutputHashMode,
-        sRecurseForDerivations;
+        sRecurseForDerivations,
+        sDescription, sSelf, sEpsilon;
     Symbol sDerivationNix;
 
     /* If set, force copying files to the Nix store even if they
@@ -90,6 +91,7 @@ public:
 
     const ref<Store> store;
 
+
 private:
     SrcToStore srcToStore;
 
@@ -152,8 +154,9 @@ public:
     Expr * parseStdin();
 
     /* Evaluate an expression read from the given file to normal
-       form. */
-    void evalFile(const Path & path, Value & v);
+       form. Optionally enforce that the top-level expression is
+       trivial (i.e. doesn't require arbitrary computation). */
+    void evalFile(const Path & path, Value & v, bool mustBeTrivial = false);
 
     void resetFileCache();
 
@@ -330,7 +333,7 @@ string showType(const Value & v);
 
 /* Decode a context string ‘!<name>!<path>’ into a pair <path,
    name>. */
-std::pair<string, string> decodeContext(const string & s);
+std::pair<string, string> decodeContext(std::string_view s);
 
 /* If `path' refers to a directory, then append "/default.nix". */
 Path resolveExprPath(Path path);
diff --git a/src/libexpr/flake/call-flake.nix b/src/libexpr/flake/call-flake.nix
new file mode 100644
index 000000000..932ac5e90
--- /dev/null
+++ b/src/libexpr/flake/call-flake.nix
@@ -0,0 +1,56 @@
+lockFileStr: rootSrc: rootSubdir:
+
+let
+
+  lockFile = builtins.fromJSON lockFileStr;
+
+  allNodes =
+    builtins.mapAttrs
+      (key: node:
+        let
+
+          sourceInfo =
+            if key == lockFile.root
+            then rootSrc
+            else fetchTree (node.info or {} // removeAttrs node.locked ["dir"]);
+
+          subdir = if key == lockFile.root then rootSubdir else node.locked.dir or "";
+
+          flake = import (sourceInfo + (if subdir != "" then "/" else "") + subdir + "/flake.nix");
+
+          inputs = builtins.mapAttrs
+            (inputName: inputSpec: allNodes.${resolveInput inputSpec})
+            (node.inputs or {});
+
+          # Resolve a input spec into a node name. An input spec is
+          # either a node name, or a 'follows' path from the root
+          # node.
+          resolveInput = inputSpec:
+              if builtins.isList inputSpec
+              then getInputByPath lockFile.root inputSpec
+              else inputSpec;
+
+          # Follow an input path (e.g. ["dwarffs" "nixpkgs"]) from the
+          # root node, returning the final node.
+          getInputByPath = nodeName: path:
+            if path == []
+            then nodeName
+            else
+              getInputByPath
+                # Since this could be a 'follows' input, call resolveInput.
+                (resolveInput lockFile.nodes.${nodeName}.inputs.${builtins.head path})
+                (builtins.tail path);
+
+          outputs = flake.outputs (inputs // { self = result; });
+
+          result = outputs // sourceInfo // { inherit inputs; inherit outputs; inherit sourceInfo; };
+        in
+          if node.flake or true then
+            assert builtins.isFunction flake.outputs;
+            result
+          else
+            sourceInfo
+      )
+      lockFile.nodes;
+
+in allNodes.${lockFile.root}
diff --git a/src/libexpr/flake/flake.cc b/src/libexpr/flake/flake.cc
new file mode 100644
index 000000000..01f464859
--- /dev/null
+++ b/src/libexpr/flake/flake.cc
@@ -0,0 +1,609 @@
+#include "flake.hh"
+#include "lockfile.hh"
+#include "primops.hh"
+#include "eval-inline.hh"
+#include "store-api.hh"
+#include "fetchers.hh"
+#include "finally.hh"
+
+namespace nix {
+
+using namespace flake;
+
+namespace flake {
+
+typedef std::pair<Tree, FlakeRef> FetchedFlake;
+typedef std::vector<std::pair<FlakeRef, FetchedFlake>> FlakeCache;
+
+static std::optional<FetchedFlake> lookupInFlakeCache(
+    const FlakeCache & flakeCache,
+    const FlakeRef & flakeRef)
+{
+    // FIXME: inefficient.
+    for (auto & i : flakeCache) {
+        if (flakeRef == i.first) {
+            debug("mapping '%s' to previously seen input '%s' -> '%s",
+                flakeRef, i.first, i.second.second);
+            return i.second;
+        }
+    }
+
+    return std::nullopt;
+}
+
+static std::tuple<fetchers::Tree, FlakeRef, FlakeRef> fetchOrSubstituteTree(
+    EvalState & state,
+    const FlakeRef & originalRef,
+    bool allowLookup,
+    FlakeCache & flakeCache)
+{
+    auto fetched = lookupInFlakeCache(flakeCache, originalRef);
+    FlakeRef resolvedRef = originalRef;
+
+    if (!fetched) {
+        if (originalRef.input.isDirect()) {
+            fetched.emplace(originalRef.fetchTree(state.store));
+        } else {
+            if (allowLookup) {
+                resolvedRef = originalRef.resolve(state.store);
+                auto fetchedResolved = lookupInFlakeCache(flakeCache, originalRef);
+                if (!fetchedResolved) fetchedResolved.emplace(resolvedRef.fetchTree(state.store));
+                flakeCache.push_back({resolvedRef, fetchedResolved.value()});
+                fetched.emplace(fetchedResolved.value());
+            }
+            else {
+                throw Error("'%s' is an indirect flake reference, but registry lookups are not allowed", originalRef);
+            }
+        }
+        flakeCache.push_back({originalRef, fetched.value()});
+    }
+
+    auto [tree, lockedRef] = fetched.value();
+
+    debug("got tree '%s' from '%s'",
+        state.store->printStorePath(tree.storePath), lockedRef);
+
+    if (state.allowedPaths)
+        state.allowedPaths->insert(tree.actualPath);
+
+    assert(!originalRef.input.getNarHash() || tree.storePath == originalRef.input.computeStorePath(*state.store));
+
+    return {std::move(tree), resolvedRef, lockedRef};
+}
+
+static void expectType(EvalState & state, ValueType type,
+    Value & value, const Pos & pos)
+{
+    if (value.type == tThunk && value.isTrivial())
+        state.forceValue(value, pos);
+    if (value.type != type)
+        throw Error("expected %s but got %s at %s",
+            showType(type), showType(value.type), pos);
+}
+
+static std::map<FlakeId, FlakeInput> parseFlakeInputs(
+    EvalState & state, Value * value, const Pos & pos);
+
+static FlakeInput parseFlakeInput(EvalState & state,
+    const std::string & inputName, Value * value, const Pos & pos)
+{
+    expectType(state, tAttrs, *value, pos);
+
+    FlakeInput input;
+
+    auto sInputs = state.symbols.create("inputs");
+    auto sUrl = state.symbols.create("url");
+    auto sFlake = state.symbols.create("flake");
+    auto sFollows = state.symbols.create("follows");
+
+    fetchers::Attrs attrs;
+    std::optional<std::string> url;
+
+    for (nix::Attr attr : *(value->attrs)) {
+        try {
+            if (attr.name == sUrl) {
+                expectType(state, tString, *attr.value, *attr.pos);
+                url = attr.value->string.s;
+                attrs.emplace("url", *url);
+            } else if (attr.name == sFlake) {
+                expectType(state, tBool, *attr.value, *attr.pos);
+                input.isFlake = attr.value->boolean;
+            } else if (attr.name == sInputs) {
+                input.overrides = parseFlakeInputs(state, attr.value, *attr.pos);
+            } else if (attr.name == sFollows) {
+                expectType(state, tString, *attr.value, *attr.pos);
+                input.follows = parseInputPath(attr.value->string.s);
+            } else {
+                state.forceValue(*attr.value);
+                if (attr.value->type == tString)
+                    attrs.emplace(attr.name, attr.value->string.s);
+                else
+                    throw TypeError("flake input attribute '%s' is %s while a string is expected",
+                        attr.name, showType(*attr.value));
+            }
+        } catch (Error & e) {
+            e.addTrace(*attr.pos, hintfmt("in flake attribute '%s'", attr.name));
+            throw;
+        }
+    }
+
+    if (attrs.count("type"))
+        try {
+            input.ref = FlakeRef::fromAttrs(attrs);
+        } catch (Error & e) {
+            e.addTrace(pos, hintfmt("in flake input"));
+            throw;
+        }
+    else {
+        attrs.erase("url");
+        if (!attrs.empty())
+            throw Error("unexpected flake input attribute '%s', at %s", attrs.begin()->first, pos);
+        if (url)
+            input.ref = parseFlakeRef(*url, {}, true);
+    }
+
+    if (!input.follows && !input.ref)
+        input.ref = FlakeRef::fromAttrs({{"type", "indirect"}, {"id", inputName}});
+
+    return input;
+}
+
+static std::map<FlakeId, FlakeInput> parseFlakeInputs(
+    EvalState & state, Value * value, const Pos & pos)
+{
+    std::map<FlakeId, FlakeInput> inputs;
+
+    expectType(state, tAttrs, *value, pos);
+
+    for (nix::Attr & inputAttr : *(*value).attrs) {
+        inputs.emplace(inputAttr.name,
+            parseFlakeInput(state,
+                inputAttr.name,
+                inputAttr.value,
+                *inputAttr.pos));
+    }
+
+    return inputs;
+}
+
+static Flake getFlake(
+    EvalState & state,
+    const FlakeRef & originalRef,
+    bool allowLookup,
+    FlakeCache & flakeCache)
+{
+    auto [sourceInfo, resolvedRef, lockedRef] = fetchOrSubstituteTree(
+        state, originalRef, allowLookup, flakeCache);
+
+    // Guard against symlink attacks.
+    auto flakeFile = canonPath(sourceInfo.actualPath + "/" + lockedRef.subdir + "/flake.nix");
+    if (!isInDir(flakeFile, sourceInfo.actualPath))
+        throw Error("'flake.nix' file of flake '%s' escapes from '%s'",
+            lockedRef, state.store->printStorePath(sourceInfo.storePath));
+
+    Flake flake {
+        .originalRef = originalRef,
+        .resolvedRef = resolvedRef,
+        .lockedRef = lockedRef,
+        .sourceInfo = std::make_shared<fetchers::Tree>(std::move(sourceInfo))
+    };
+
+    if (!pathExists(flakeFile))
+        throw Error("source tree referenced by '%s' does not contain a '%s/flake.nix' file", lockedRef, lockedRef.subdir);
+
+    Value vInfo;
+    state.evalFile(flakeFile, vInfo, true); // FIXME: symlink attack
+
+    expectType(state, tAttrs, vInfo, Pos(foFile, state.symbols.create(flakeFile), 0, 0));
+
+    auto sEdition = state.symbols.create("edition"); // FIXME: remove soon
+
+    if (vInfo.attrs->get(sEdition))
+        warn("flake '%s' has deprecated attribute 'edition'", lockedRef);
+
+    if (auto description = vInfo.attrs->get(state.sDescription)) {
+        expectType(state, tString, *description->value, *description->pos);
+        flake.description = description->value->string.s;
+    }
+
+    auto sInputs = state.symbols.create("inputs");
+
+    if (auto inputs = vInfo.attrs->get(sInputs))
+        flake.inputs = parseFlakeInputs(state, inputs->value, *inputs->pos);
+
+    auto sOutputs = state.symbols.create("outputs");
+
+    if (auto outputs = vInfo.attrs->get(sOutputs)) {
+        expectType(state, tLambda, *outputs->value, *outputs->pos);
+        flake.vOutputs = allocRootValue(outputs->value);
+
+        if ((*flake.vOutputs)->lambda.fun->matchAttrs) {
+            for (auto & formal : (*flake.vOutputs)->lambda.fun->formals->formals) {
+                if (formal.name != state.sSelf)
+                    flake.inputs.emplace(formal.name, FlakeInput {
+                        .ref = parseFlakeRef(formal.name)
+                    });
+            }
+        }
+
+    } else
+        throw Error("flake '%s' lacks attribute 'outputs'", lockedRef);
+
+    for (auto & attr : *vInfo.attrs) {
+        if (attr.name != sEdition &&
+            attr.name != state.sDescription &&
+            attr.name != sInputs &&
+            attr.name != sOutputs)
+            throw Error("flake '%s' has an unsupported attribute '%s', at %s",
+                lockedRef, attr.name, *attr.pos);
+    }
+
+    return flake;
+}
+
+Flake getFlake(EvalState & state, const FlakeRef & originalRef, bool allowLookup)
+{
+    FlakeCache flakeCache;
+    return getFlake(state, originalRef, allowLookup, flakeCache);
+}
+
+/* Compute an in-memory lock file for the specified top-level flake,
+   and optionally write it to file, it the flake is writable. */
+LockedFlake lockFlake(
+    EvalState & state,
+    const FlakeRef & topRef,
+    const LockFlags & lockFlags)
+{
+    settings.requireExperimentalFeature("flakes");
+
+    FlakeCache flakeCache;
+
+    auto flake = getFlake(state, topRef, lockFlags.useRegistries, flakeCache);
+
+    // FIXME: symlink attack
+    auto oldLockFile = LockFile::read(
+        flake.sourceInfo->actualPath + "/" + flake.lockedRef.subdir + "/flake.lock");
+
+    debug("old lock file: %s", oldLockFile);
+
+    // FIXME: check whether all overrides are used.
+    std::map<InputPath, FlakeInput> overrides;
+    std::set<InputPath> overridesUsed, updatesUsed;
+
+    for (auto & i : lockFlags.inputOverrides)
+        overrides.insert_or_assign(i.first, FlakeInput { .ref = i.second });
+
+    LockFile newLockFile;
+
+    std::vector<FlakeRef> parents;
+
+    std::function<void(
+        const FlakeInputs & flakeInputs,
+        std::shared_ptr<Node> node,
+        const InputPath & inputPathPrefix,
+        std::shared_ptr<const Node> oldNode)>
+        computeLocks;
+
+    computeLocks = [&](
+        const FlakeInputs & flakeInputs,
+        std::shared_ptr<Node> node,
+        const InputPath & inputPathPrefix,
+        std::shared_ptr<const Node> oldNode)
+    {
+        debug("computing lock file node '%s'", printInputPath(inputPathPrefix));
+
+        /* Get the overrides (i.e. attributes of the form
+           'inputs.nixops.inputs.nixpkgs.url = ...'). */
+        // FIXME: check this
+        for (auto & [id, input] : flake.inputs) {
+            for (auto & [idOverride, inputOverride] : input.overrides) {
+                auto inputPath(inputPathPrefix);
+                inputPath.push_back(id);
+                inputPath.push_back(idOverride);
+                overrides.insert_or_assign(inputPath, inputOverride);
+            }
+        }
+
+        /* Go over the flake inputs, resolve/fetch them if
+           necessary (i.e. if they're new or the flakeref changed
+           from what's in the lock file). */
+        for (auto & [id, input2] : flakeInputs) {
+            auto inputPath(inputPathPrefix);
+            inputPath.push_back(id);
+            auto inputPathS = printInputPath(inputPath);
+            debug("computing input '%s'", inputPathS);
+
+            /* Do we have an override for this input from one of the
+               ancestors? */
+            auto i = overrides.find(inputPath);
+            bool hasOverride = i != overrides.end();
+            if (hasOverride) overridesUsed.insert(inputPath);
+            auto & input = hasOverride ? i->second : input2;
+
+            /* Resolve 'follows' later (since it may refer to an input
+               path we haven't processed yet. */
+            if (input.follows) {
+                InputPath target;
+                if (hasOverride || input.absolute)
+                    /* 'follows' from an override is relative to the
+                       root of the graph. */
+                    target = *input.follows;
+                else {
+                    /* Otherwise, it's relative to the current flake. */
+                    target = inputPathPrefix;
+                    for (auto & i : *input.follows) target.push_back(i);
+                }
+                debug("input '%s' follows '%s'", inputPathS, printInputPath(target));
+                node->inputs.insert_or_assign(id, target);
+                continue;
+            }
+
+            assert(input.ref);
+
+            /* Do we have an entry in the existing lock file? And we
+               don't have a --update-input flag for this input? */
+            std::shared_ptr<LockedNode> oldLock;
+
+            updatesUsed.insert(inputPath);
+
+            if (oldNode && !lockFlags.inputUpdates.count(inputPath))
+                if (auto oldLock2 = get(oldNode->inputs, id))
+                    if (auto oldLock3 = std::get_if<0>(&*oldLock2))
+                        oldLock = *oldLock3;
+
+            if (oldLock
+                && oldLock->originalRef == *input.ref
+                && !hasOverride)
+            {
+                debug("keeping existing input '%s'", inputPathS);
+
+                /* Copy the input from the old lock since its flakeref
+                   didn't change and there is no override from a
+                   higher level flake. */
+                auto childNode = std::make_shared<LockedNode>(
+                    oldLock->lockedRef, oldLock->originalRef, oldLock->isFlake);
+
+                node->inputs.insert_or_assign(id, childNode);
+
+                /* If we have an --update-input flag for an input
+                   of this input, then we must fetch the flake to
+                   to update it. */
+                auto lb = lockFlags.inputUpdates.lower_bound(inputPath);
+
+                auto hasChildUpdate =
+                    lb != lockFlags.inputUpdates.end()
+                    && lb->size() > inputPath.size()
+                    && std::equal(inputPath.begin(), inputPath.end(), lb->begin());
+
+                if (hasChildUpdate) {
+                    auto inputFlake = getFlake(
+                        state, oldLock->lockedRef, false, flakeCache);
+                    computeLocks(inputFlake.inputs, childNode, inputPath, oldLock);
+                } else {
+                    /* No need to fetch this flake, we can be
+                       lazy. However there may be new overrides on the
+                       inputs of this flake, so we need to check
+                       those. */
+                    FlakeInputs fakeInputs;
+
+                    for (auto & i : oldLock->inputs) {
+                        if (auto lockedNode = std::get_if<0>(&i.second)) {
+                            fakeInputs.emplace(i.first, FlakeInput {
+                                .ref = (*lockedNode)->originalRef,
+                                .isFlake = (*lockedNode)->isFlake,
+                            });
+                        } else if (auto follows = std::get_if<1>(&i.second)) {
+                            fakeInputs.emplace(i.first, FlakeInput {
+                                .follows = *follows,
+                                .absolute = true
+                            });
+                        }
+                    }
+
+                    computeLocks(fakeInputs, childNode, inputPath, oldLock);
+                }
+
+            } else {
+                /* We need to create a new lock file entry. So fetch
+                   this input. */
+                debug("creating new input '%s'", inputPathS);
+
+                if (!lockFlags.allowMutable && !input.ref->input.isImmutable())
+                    throw Error("cannot update flake input '%s' in pure mode", inputPathS);
+
+                if (input.isFlake) {
+                    auto inputFlake = getFlake(state, *input.ref, lockFlags.useRegistries, flakeCache);
+
+                    /* Note: in case of an --override-input, we use
+                       the *original* ref (input2.ref) for the
+                       "original" field, rather than the
+                       override. This ensures that the override isn't
+                       nuked the next time we update the lock
+                       file. That is, overrides are sticky unless you
+                       use --no-write-lock-file. */
+                    auto childNode = std::make_shared<LockedNode>(
+                        inputFlake.lockedRef, input2.ref ? *input2.ref : *input.ref);
+
+                    node->inputs.insert_or_assign(id, childNode);
+
+                    /* Guard against circular flake imports. */
+                    for (auto & parent : parents)
+                        if (parent == *input.ref)
+                            throw Error("found circular import of flake '%s'", parent);
+                    parents.push_back(*input.ref);
+                    Finally cleanup([&]() { parents.pop_back(); });
+
+                    /* Recursively process the inputs of this
+                       flake. Also, unless we already have this flake
+                       in the top-level lock file, use this flake's
+                       own lock file. */
+                    computeLocks(
+                        inputFlake.inputs, childNode, inputPath,
+                        oldLock
+                        ? std::dynamic_pointer_cast<const Node>(oldLock)
+                        : LockFile::read(
+                            inputFlake.sourceInfo->actualPath + "/" + inputFlake.lockedRef.subdir + "/flake.lock").root);
+                }
+
+                else {
+                    auto [sourceInfo, resolvedRef, lockedRef] = fetchOrSubstituteTree(
+                        state, *input.ref, lockFlags.useRegistries, flakeCache);
+                    node->inputs.insert_or_assign(id,
+                        std::make_shared<LockedNode>(lockedRef, *input.ref, false));
+                }
+            }
+        }
+    };
+
+    computeLocks(
+        flake.inputs, newLockFile.root, {},
+        lockFlags.recreateLockFile ? nullptr : oldLockFile.root);
+
+    for (auto & i : lockFlags.inputOverrides)
+        if (!overridesUsed.count(i.first))
+            warn("the flag '--override-input %s %s' does not match any input",
+                printInputPath(i.first), i.second);
+
+    for (auto & i : lockFlags.inputUpdates)
+        if (!updatesUsed.count(i))
+            warn("the flag '--update-input %s' does not match any input", printInputPath(i));
+
+    /* Check 'follows' inputs. */
+    newLockFile.check();
+
+    debug("new lock file: %s", newLockFile);
+
+    /* Check whether we need to / can write the new lock file. */
+    if (!(newLockFile == oldLockFile)) {
+
+        auto diff = LockFile::diff(oldLockFile, newLockFile);
+
+        if (lockFlags.writeLockFile) {
+            if (auto sourcePath = topRef.input.getSourcePath()) {
+                if (!newLockFile.isImmutable()) {
+                    if (settings.warnDirty)
+                        warn("will not write lock file of flake '%s' because it has a mutable input", topRef);
+                } else {
+                    if (!lockFlags.updateLockFile)
+                        throw Error("flake '%s' requires lock file changes but they're not allowed due to '--no-update-lock-file'", topRef);
+
+                    auto relPath = (topRef.subdir == "" ? "" : topRef.subdir + "/") + "flake.lock";
+
+                    auto path = *sourcePath + "/" + relPath;
+
+                    bool lockFileExists = pathExists(path);
+
+                    if (lockFileExists) {
+                        auto s = chomp(diff);
+                        if (s.empty())
+                            warn("updating lock file '%s'", path);
+                        else
+                            warn("updating lock file '%s':\n%s", path, s);
+                    } else
+                        warn("creating lock file '%s'", path);
+
+                    newLockFile.write(path);
+
+                    topRef.input.markChangedFile(
+                        (topRef.subdir == "" ? "" : topRef.subdir + "/") + "flake.lock",
+                        lockFlags.commitLockFile
+                        ? std::optional<std::string>(fmt("%s: %s\n\nFlake input changes:\n\n%s",
+                                relPath, lockFileExists ? "Update" : "Add", diff))
+                        : std::nullopt);
+
+                    /* Rewriting the lockfile changed the top-level
+                       repo, so we should re-read it. FIXME: we could
+                       also just clear the 'rev' field... */
+                    auto prevLockedRef = flake.lockedRef;
+                    FlakeCache dummyCache;
+                    flake = getFlake(state, topRef, lockFlags.useRegistries, dummyCache);
+
+                    if (lockFlags.commitLockFile &&
+                        flake.lockedRef.input.getRev() &&
+                        prevLockedRef.input.getRev() != flake.lockedRef.input.getRev())
+                        warn("committed new revision '%s'", flake.lockedRef.input.getRev()->gitRev());
+
+                    /* Make sure that we picked up the change,
+                       i.e. the tree should usually be dirty
+                       now. Corner case: we could have reverted from a
+                       dirty to a clean tree! */
+                    if (flake.lockedRef.input == prevLockedRef.input
+                        && !flake.lockedRef.input.isImmutable())
+                        throw Error("'%s' did not change after I updated its 'flake.lock' file; is 'flake.lock' under version control?", flake.originalRef);
+                }
+            } else
+                throw Error("cannot write modified lock file of flake '%s' (use '--no-write-lock-file' to ignore)", topRef);
+        } else
+            warn("not writing modified lock file of flake '%s':\n%s", topRef, chomp(diff));
+    }
+
+    return LockedFlake { .flake = std::move(flake), .lockFile = std::move(newLockFile) };
+}
+
+void callFlake(EvalState & state,
+    const LockedFlake & lockedFlake,
+    Value & vRes)
+{
+    auto vLocks = state.allocValue();
+    auto vRootSrc = state.allocValue();
+    auto vRootSubdir = state.allocValue();
+    auto vTmp1 = state.allocValue();
+    auto vTmp2 = state.allocValue();
+
+    mkString(*vLocks, lockedFlake.lockFile.to_string());
+
+    emitTreeAttrs(state, *lockedFlake.flake.sourceInfo, lockedFlake.flake.lockedRef.input, *vRootSrc);
+
+    mkString(*vRootSubdir, lockedFlake.flake.lockedRef.subdir);
+
+    static RootValue vCallFlake = nullptr;
+
+    if (!vCallFlake) {
+        vCallFlake = allocRootValue(state.allocValue());
+        state.eval(state.parseExprFromString(
+            #include "call-flake.nix.gen.hh"
+            , "/"), **vCallFlake);
+    }
+
+    state.callFunction(**vCallFlake, *vLocks, *vTmp1, noPos);
+    state.callFunction(*vTmp1, *vRootSrc, *vTmp2, noPos);
+    state.callFunction(*vTmp2, *vRootSubdir, vRes, noPos);
+}
+
+static void prim_getFlake(EvalState & state, const Pos & pos, Value * * args, Value & v)
+{
+    auto flakeRefS = state.forceStringNoCtx(*args[0], pos);
+    auto flakeRef = parseFlakeRef(flakeRefS, {}, true);
+    if (evalSettings.pureEval && !flakeRef.input.isImmutable())
+        throw Error("cannot call 'getFlake' on mutable flake reference '%s', at %s (use --impure to override)", flakeRefS, pos);
+
+    callFlake(state,
+        lockFlake(state, flakeRef,
+            LockFlags {
+                .updateLockFile = false,
+                .useRegistries = !evalSettings.pureEval,
+                .allowMutable  = !evalSettings.pureEval,
+            }),
+        v);
+}
+
+static RegisterPrimOp r2("__getFlake", 1, prim_getFlake, "flakes");
+
+}
+
+Fingerprint LockedFlake::getFingerprint() const
+{
+    // FIXME: as an optimization, if the flake contains a lock file
+    // and we haven't changed it, then it's sufficient to use
+    // flake.sourceInfo.storePath for the fingerprint.
+    return hashString(htSHA256,
+        fmt("%s;%d;%d;%s",
+            flake.sourceInfo->storePath.to_string(),
+            flake.lockedRef.input.getRevCount().value_or(0),
+            flake.lockedRef.input.getLastModified().value_or(0),
+            lockFile));
+}
+
+Flake::~Flake() { }
+
+}
diff --git a/src/libexpr/flake/flake.hh b/src/libexpr/flake/flake.hh
new file mode 100644
index 000000000..77f3abdeb
--- /dev/null
+++ b/src/libexpr/flake/flake.hh
@@ -0,0 +1,111 @@
+#pragma once
+
+#include "types.hh"
+#include "flakeref.hh"
+#include "lockfile.hh"
+#include "value.hh"
+
+namespace nix {
+
+class EvalState;
+
+namespace fetchers { struct Tree; }
+
+namespace flake {
+
+struct FlakeInput;
+
+typedef std::map<FlakeId, FlakeInput> FlakeInputs;
+
+struct FlakeInput
+{
+    std::optional<FlakeRef> ref;
+    bool isFlake = true;
+    std::optional<InputPath> follows;
+    bool absolute = false; // whether 'follows' is relative to the flake root
+    FlakeInputs overrides;
+};
+
+struct Flake
+{
+    FlakeRef originalRef;
+    FlakeRef resolvedRef;
+    FlakeRef lockedRef;
+    std::optional<std::string> description;
+    std::shared_ptr<const fetchers::Tree> sourceInfo;
+    FlakeInputs inputs;
+    RootValue vOutputs;
+    ~Flake();
+};
+
+Flake getFlake(EvalState & state, const FlakeRef & flakeRef, bool allowLookup);
+
+/* Fingerprint of a locked flake; used as a cache key. */
+typedef Hash Fingerprint;
+
+struct LockedFlake
+{
+    Flake flake;
+    LockFile lockFile;
+
+    Fingerprint getFingerprint() const;
+};
+
+struct LockFlags
+{
+    /* Whether to ignore the existing lock file, creating a new one
+       from scratch. */
+    bool recreateLockFile = false;
+
+    /* Whether to update the lock file at all. If set to false, if any
+       change to the lock file is needed (e.g. when an input has been
+       added to flake.nix), you get a fatal error. */
+    bool updateLockFile = true;
+
+    /* Whether to write the lock file to disk. If set to true, if the
+       any changes to the lock file are needed and the flake is not
+       writable (i.e. is not a local Git working tree or similar), you
+       get a fatal error. If set to false, Nix will use the modified
+       lock file in memory only, without writing it to disk. */
+    bool writeLockFile = true;
+
+    /* Whether to use the registries to lookup indirect flake
+       references like 'nixpkgs'. */
+    bool useRegistries = true;
+
+    /* Whether mutable flake references (i.e. those without a Git
+       revision or similar) without a corresponding lock are
+       allowed. Mutable flake references with a lock are always
+       allowed. */
+    bool allowMutable = true;
+
+    /* Whether to commit changes to flake.lock. */
+    bool commitLockFile = false;
+
+    /* Flake inputs to be overriden. */
+    std::map<InputPath, FlakeRef> inputOverrides;
+
+    /* Flake inputs to be updated. This means that any existing lock
+       for those inputs will be ignored. */
+    std::set<InputPath> inputUpdates;
+};
+
+LockedFlake lockFlake(
+    EvalState & state,
+    const FlakeRef & flakeRef,
+    const LockFlags & lockFlags);
+
+void callFlake(
+    EvalState & state,
+    const LockedFlake & lockedFlake,
+    Value & v);
+
+}
+
+void emitTreeAttrs(
+    EvalState & state,
+    const fetchers::Tree & tree,
+    const fetchers::Input & input,
+    Value & v);
+
+}
diff --git a/src/libexpr/flake/flakeref.cc b/src/libexpr/flake/flakeref.cc
new file mode 100644
index 000000000..701546671
--- /dev/null
+++ b/src/libexpr/flake/flakeref.cc
@@ -0,0 +1,199 @@
+#include "flakeref.hh"
+#include "store-api.hh"
+#include "url.hh"
+#include "fetchers.hh"
+#include "registry.hh"
+
+namespace nix {
+
+#if 0
+// 'dir' path elements cannot start with a '.'. We also reject
+// potentially dangerous characters like ';'.
+const static std::string subDirElemRegex = "(?:[a-zA-Z0-9_-]+[a-zA-Z0-9._-]*)";
+const static std::string subDirRegex = subDirElemRegex + "(?:/" + subDirElemRegex + ")*";
+#endif
+
+std::string FlakeRef::to_string() const
+{
+    auto url = input.toURL();
+    if (subdir != "")
+        url.query.insert_or_assign("dir", subdir);
+    return url.to_string();
+}
+
+fetchers::Attrs FlakeRef::toAttrs() const
+{
+    auto attrs = input.toAttrs();
+    if (subdir != "")
+        attrs.emplace("dir", subdir);
+    return attrs;
+}
+
+std::ostream & operator << (std::ostream & str, const FlakeRef & flakeRef)
+{
+    str << flakeRef.to_string();
+    return str;
+}
+
+bool FlakeRef::operator ==(const FlakeRef & other) const
+{
+    return input == other.input && subdir == other.subdir;
+}
+
+FlakeRef FlakeRef::resolve(ref<Store> store) const
+{
+    auto [input2, extraAttrs] = lookupInRegistries(store, input);
+    return FlakeRef(std::move(input2), fetchers::maybeGetStrAttr(extraAttrs, "dir").value_or(subdir));
+}
+
+FlakeRef parseFlakeRef(
+    const std::string & url, const std::optional<Path> & baseDir, bool allowMissing)
+{
+    auto [flakeRef, fragment] = parseFlakeRefWithFragment(url, baseDir, allowMissing);
+    if (fragment != "")
+        throw Error("unexpected fragment '%s' in flake reference '%s'", fragment, url);
+    return flakeRef;
+}
+
+std::optional<FlakeRef> maybeParseFlakeRef(
+    const std::string & url, const std::optional<Path> & baseDir)
+{
+    try {
+        return parseFlakeRef(url, baseDir);
+    } catch (Error &) {
+        return {};
+    }
+}
+
+std::pair<FlakeRef, std::string> parseFlakeRefWithFragment(
+    const std::string & url, const std::optional<Path> & baseDir, bool allowMissing)
+{
+    using namespace fetchers;
+
+    static std::string fnRegex = "[0-9a-zA-Z-._~!$&'\"()*+,;=]+";
+
+    static std::regex pathUrlRegex(
+        "(/?" + fnRegex + "(?:/" + fnRegex + ")*/?)"
+        + "(?:\\?(" + queryRegex + "))?"
+        + "(?:#(" + queryRegex + "))?",
+        std::regex::ECMAScript);
+
+    static std::regex flakeRegex(
+        "((" + flakeIdRegexS + ")(?:/(?:" + refAndOrRevRegex + "))?)"
+        + "(?:#(" + queryRegex + "))?",
+        std::regex::ECMAScript);
+
+    std::smatch match;
+
+    /* Check if 'url' is a flake ID. This is an abbreviated syntax for
+       'flake:<flake-id>?ref=<ref>&rev=<rev>'. */
+
+    if (std::regex_match(url, match, flakeRegex)) {
+        auto parsedURL = ParsedURL{
+            .url = url,
+            .base = "flake:" + std::string(match[1]),
+            .scheme = "flake",
+            .authority = "",
+            .path = match[1],
+        };
+
+        return std::make_pair(
+            FlakeRef(Input::fromURL(parsedURL), ""),
+            percentDecode(std::string(match[6])));
+    }
+
+    /* Check if 'url' is a path (either absolute or relative to
+       'baseDir'). If so, search upward to the root of the repo
+       (i.e. the directory containing .git). */
+
+    else if (std::regex_match(url, match, pathUrlRegex)) {
+        std::string path = match[1];
+        if (!baseDir && !hasPrefix(path, "/"))
+            throw BadURL("flake reference '%s' is not an absolute path", url);
+        path = absPath(path, baseDir, true);
+
+        if (!S_ISDIR(lstat(path).st_mode))
+            throw BadURL("path '%s' is not a flake (because it's not a directory)", path);
+
+        if (!allowMissing && !pathExists(path + "/flake.nix"))
+            throw BadURL("path '%s' is not a flake (because it doesn't contain a 'flake.nix' file)", path);
+
+        auto fragment = percentDecode(std::string(match[3]));
+
+        auto flakeRoot = path;
+        std::string subdir;
+
+        while (flakeRoot != "/") {
+            if (pathExists(flakeRoot + "/.git")) {
+                auto base = std::string("git+file://") + flakeRoot;
+
+                auto parsedURL = ParsedURL{
+                    .url = base, // FIXME
+                    .base = base,
+                    .scheme = "git+file",
+                    .authority = "",
+                    .path = flakeRoot,
+                    .query = decodeQuery(match[2]),
+                };
+
+                if (subdir != "") {
+                    if (parsedURL.query.count("dir"))
+                        throw Error("flake URL '%s' has an inconsistent 'dir' parameter", url);
+                    parsedURL.query.insert_or_assign("dir", subdir);
+                }
+
+                if (pathExists(flakeRoot + "/.git/shallow"))
+                    parsedURL.query.insert_or_assign("shallow", "1");
+
+                return std::make_pair(
+                    FlakeRef(Input::fromURL(parsedURL), get(parsedURL.query, "dir").value_or("")),
+                    fragment);
+            }
+
+            subdir = std::string(baseNameOf(flakeRoot)) + (subdir.empty() ? "" : "/" + subdir);
+            flakeRoot = dirOf(flakeRoot);
+        }
+
+        fetchers::Attrs attrs;
+        attrs.insert_or_assign("type", "path");
+        attrs.insert_or_assign("path", path);
+
+        return std::make_pair(FlakeRef(Input::fromAttrs(std::move(attrs)), ""), fragment);
+    }
+
+    else {
+        auto parsedURL = parseURL(url);
+        std::string fragment;
+        std::swap(fragment, parsedURL.fragment);
+        return std::make_pair(
+            FlakeRef(Input::fromURL(parsedURL), get(parsedURL.query, "dir").value_or("")),
+            fragment);
+    }
+}
+
+std::optional<std::pair<FlakeRef, std::string>> maybeParseFlakeRefWithFragment(
+    const std::string & url, const std::optional<Path> & baseDir)
+{
+    try {
+        return parseFlakeRefWithFragment(url, baseDir);
+    } catch (Error & e) {
+        return {};
+    }
+}
+
+FlakeRef FlakeRef::fromAttrs(const fetchers::Attrs & attrs)
+{
+    auto attrs2(attrs);
+    attrs2.erase("dir");
+    return FlakeRef(
+        fetchers::Input::fromAttrs(std::move(attrs2)),
+        fetchers::maybeGetStrAttr(attrs, "dir").value_or(""));
+}
+
+std::pair<fetchers::Tree, FlakeRef> FlakeRef::fetchTree(ref<Store> store) const
+{
+    auto [tree, lockedInput] = input.fetch(store);
+    return {std::move(tree), FlakeRef(std::move(lockedInput), subdir)};
+}
+
+}
diff --git a/src/libexpr/flake/flakeref.hh b/src/libexpr/flake/flakeref.hh
new file mode 100644
index 000000000..f4eb825a6
--- /dev/null
+++ b/src/libexpr/flake/flakeref.hh
@@ -0,0 +1,53 @@
+#pragma once
+
+#include "types.hh"
+#include "hash.hh"
+#include "fetchers.hh"
+
+#include <variant>
+
+namespace nix {
+
+class Store;
+
+typedef std::string FlakeId;
+
+struct FlakeRef
+{
+    fetchers::Input input;
+
+    Path subdir;
+
+    bool operator==(const FlakeRef & other) const;
+
+    FlakeRef(fetchers::Input && input, const Path & subdir)
+        : input(std::move(input)), subdir(subdir)
+    { }
+
+    // FIXME: change to operator <<.
+    std::string to_string() const;
+
+    fetchers::Attrs toAttrs() const;
+
+    FlakeRef resolve(ref<Store> store) const;
+
+    static FlakeRef fromAttrs(const fetchers::Attrs & attrs);
+
+    std::pair<fetchers::Tree, FlakeRef> fetchTree(ref<Store> store) const;
+};
+
+std::ostream & operator << (std::ostream & str, const FlakeRef & flakeRef);
+
+FlakeRef parseFlakeRef(
+    const std::string & url, const std::optional<Path> & baseDir = {}, bool allowMissing = false);
+
+std::optional<FlakeRef> maybeParseFlake(
+    const std::string & url, const std::optional<Path> & baseDir = {});
+
+std::pair<FlakeRef, std::string> parseFlakeRefWithFragment(
+    const std::string & url, const std::optional<Path> & baseDir = {}, bool allowMissing = false);
+
+std::optional<std::pair<FlakeRef, std::string>> maybeParseFlakeRefWithFragment(
+    const std::string & url, const std::optional<Path> & baseDir = {});
+
+}
diff --git a/src/libexpr/flake/lockfile.cc b/src/libexpr/flake/lockfile.cc
new file mode 100644
index 000000000..a74846944
--- /dev/null
+++ b/src/libexpr/flake/lockfile.cc
@@ -0,0 +1,338 @@
+#include "lockfile.hh"
+#include "store-api.hh"
+
+#include <nlohmann/json.hpp>
+
+namespace nix::flake {
+
+FlakeRef getFlakeRef(
+    const nlohmann::json & json,
+    const char * attr,
+    const char * info)
+{
+    auto i = json.find(attr);
+    if (i != json.end()) {
+        auto attrs = jsonToAttrs(*i);
+        // FIXME: remove when we drop support for version 5.
+        if (info) {
+            auto j = json.find(info);
+            if (j != json.end()) {
+                for (auto k : jsonToAttrs(*j))
+                    attrs.insert_or_assign(k.first, k.second);
+            }
+        }
+        return FlakeRef::fromAttrs(attrs);
+    }
+
+    throw Error("attribute '%s' missing in lock file", attr);
+}
+
+LockedNode::LockedNode(const nlohmann::json & json)
+    : lockedRef(getFlakeRef(json, "locked", "info"))
+    , originalRef(getFlakeRef(json, "original", nullptr))
+    , isFlake(json.find("flake") != json.end() ? (bool) json["flake"] : true)
+{
+    if (!lockedRef.input.isImmutable())
+        throw Error("lockfile contains mutable lock '%s'", attrsToJson(lockedRef.input.toAttrs()));
+}
+
+StorePath LockedNode::computeStorePath(Store & store) const
+{
+    return lockedRef.input.computeStorePath(store);
+}
+
+std::shared_ptr<Node> LockFile::findInput(const InputPath & path)
+{
+    auto pos = root;
+
+    if (!pos) return {};
+
+    for (auto & elem : path) {
+        if (auto i = get(pos->inputs, elem)) {
+            if (auto node = std::get_if<0>(&*i))
+                pos = *node;
+            else if (auto follows = std::get_if<1>(&*i)) {
+                pos = findInput(*follows);
+                if (!pos) return {};
+            }
+        } else
+            return {};
+    }
+
+    return pos;
+}
+
+LockFile::LockFile(const nlohmann::json & json, const Path & path)
+{
+    auto version = json.value("version", 0);
+    if (version < 5 || version > 7)
+        throw Error("lock file '%s' has unsupported version %d", path, version);
+
+    std::unordered_map<std::string, std::shared_ptr<Node>> nodeMap;
+
+    std::function<void(Node & node, const nlohmann::json & jsonNode)> getInputs;
+
+    getInputs = [&](Node & node, const nlohmann::json & jsonNode)
+    {
+        if (jsonNode.find("inputs") == jsonNode.end()) return;
+        for (auto & i : jsonNode["inputs"].items()) {
+            if (i.value().is_array()) {
+                InputPath path;
+                for (auto & j : i.value())
+                    path.push_back(j);
+                node.inputs.insert_or_assign(i.key(), path);
+            } else {
+                std::string inputKey = i.value();
+                auto k = nodeMap.find(inputKey);
+                if (k == nodeMap.end()) {
+                    auto jsonNode2 = json["nodes"][inputKey];
+                    auto input = std::make_shared<LockedNode>(jsonNode2);
+                    k = nodeMap.insert_or_assign(inputKey, input).first;
+                    getInputs(*input, jsonNode2);
+                }
+                if (auto child = std::dynamic_pointer_cast<LockedNode>(k->second))
+                    node.inputs.insert_or_assign(i.key(), child);
+                else
+                    // FIXME: replace by follows node
+                    throw Error("lock file contains cycle to root node");
+            }
+        }
+    };
+
+    std::string rootKey = json["root"];
+    nodeMap.insert_or_assign(rootKey, root);
+    getInputs(*root, json["nodes"][rootKey]);
+
+    // FIXME: check that there are no cycles in version >= 7. Cycles
+    // between inputs are only possible using 'follows' indirections.
+    // Once we drop support for version <= 6, we can simplify the code
+    // a bit since we don't need to worry about cycles.
+}
+
+nlohmann::json LockFile::toJson() const
+{
+    nlohmann::json nodes;
+    std::unordered_map<std::shared_ptr<const Node>, std::string> nodeKeys;
+    std::unordered_set<std::string> keys;
+
+    std::function<std::string(const std::string & key, std::shared_ptr<const Node> node)> dumpNode;
+
+    dumpNode = [&](std::string key, std::shared_ptr<const Node> node) -> std::string
+    {
+        auto k = nodeKeys.find(node);
+        if (k != nodeKeys.end())
+            return k->second;
+
+        if (!keys.insert(key).second) {
+            for (int n = 2; ; ++n) {
+                auto k = fmt("%s_%d", key, n);
+                if (keys.insert(k).second) {
+                    key = k;
+                    break;
+                }
+            }
+        }
+
+        nodeKeys.insert_or_assign(node, key);
+
+        auto n = nlohmann::json::object();
+
+        if (!node->inputs.empty()) {
+            auto inputs = nlohmann::json::object();
+            for (auto & i : node->inputs) {
+                if (auto child = std::get_if<0>(&i.second)) {
+                    inputs[i.first] = dumpNode(i.first, *child);
+                } else if (auto follows = std::get_if<1>(&i.second)) {
+                    auto arr = nlohmann::json::array();
+                    for (auto & x : *follows)
+                        arr.push_back(x);
+                    inputs[i.first] = std::move(arr);
+                }
+            }
+            n["inputs"] = std::move(inputs);
+        }
+
+        if (auto lockedNode = std::dynamic_pointer_cast<const LockedNode>(node)) {
+            n["original"] = fetchers::attrsToJson(lockedNode->originalRef.toAttrs());
+            n["locked"] = fetchers::attrsToJson(lockedNode->lockedRef.toAttrs());
+            if (!lockedNode->isFlake) n["flake"] = false;
+        }
+
+        nodes[key] = std::move(n);
+
+        return key;
+    };
+
+    nlohmann::json json;
+    json["version"] = 7;
+    json["root"] = dumpNode("root", root);
+    json["nodes"] = std::move(nodes);
+
+    return json;
+}
+
+std::string LockFile::to_string() const
+{
+    return toJson().dump(2);
+}
+
+LockFile LockFile::read(const Path & path)
+{
+    if (!pathExists(path)) return LockFile();
+    return LockFile(nlohmann::json::parse(readFile(path)), path);
+}
+
+std::ostream & operator <<(std::ostream & stream, const LockFile & lockFile)
+{
+    stream << lockFile.toJson().dump(2);
+    return stream;
+}
+
+void LockFile::write(const Path & path) const
+{
+    createDirs(dirOf(path));
+    writeFile(path, fmt("%s\n", *this));
+}
+
+bool LockFile::isImmutable() const
+{
+    std::unordered_set<std::shared_ptr<const Node>> nodes;
+
+    std::function<void(std::shared_ptr<const Node> node)> visit;
+
+    visit = [&](std::shared_ptr<const Node> node)
+    {
+        if (!nodes.insert(node).second) return;
+        for (auto & i : node->inputs)
+            if (auto child = std::get_if<0>(&i.second))
+                visit(*child);
+    };
+
+    visit(root);
+
+    for (auto & i : nodes) {
+        if (i == root) continue;
+        auto lockedNode = std::dynamic_pointer_cast<const LockedNode>(i);
+        if (lockedNode && !lockedNode->lockedRef.input.isImmutable()) return false;
+    }
+
+    return true;
+}
+
+bool LockFile::operator ==(const LockFile & other) const
+{
+    // FIXME: slow
+    return toJson() == other.toJson();
+}
+
+InputPath parseInputPath(std::string_view s)
+{
+    InputPath path;
+
+    for (auto & elem : tokenizeString<std::vector<std::string>>(s, "/")) {
+        if (!std::regex_match(elem, flakeIdRegex))
+            throw UsageError("invalid flake input path element '%s'", elem);
+        path.push_back(elem);
+    }
+
+    return path;
+}
+
+std::map<InputPath, Node::Edge> LockFile::getAllInputs() const
+{
+    std::unordered_set<std::shared_ptr<Node>> done;
+    std::map<InputPath, Node::Edge> res;
+
+    std::function<void(const InputPath & prefix, std::shared_ptr<Node> node)> recurse;
+
+    recurse = [&](const InputPath & prefix, std::shared_ptr<Node> node)
+    {
+        if (!done.insert(node).second) return;
+
+        for (auto &[id, input] : node->inputs) {
+            auto inputPath(prefix);
+            inputPath.push_back(id);
+            res.emplace(inputPath, input);
+            if (auto child = std::get_if<0>(&input))
+                recurse(inputPath, *child);
+        }
+    };
+
+    recurse({}, root);
+
+    return res;
+}
+
+std::ostream & operator <<(std::ostream & stream, const Node::Edge & edge)
+{
+    if (auto node = std::get_if<0>(&edge))
+        stream << "'" << (*node)->lockedRef << "'";
+    else if (auto follows = std::get_if<1>(&edge))
+        stream << fmt("follows '%s'", printInputPath(*follows));
+    return stream;
+}
+
+static bool equals(const Node::Edge & e1, const Node::Edge & e2)
+{
+    if (auto n1 = std::get_if<0>(&e1))
+        if (auto n2 = std::get_if<0>(&e2))
+            return (*n1)->lockedRef == (*n2)->lockedRef;
+    if (auto f1 = std::get_if<1>(&e1))
+        if (auto f2 = std::get_if<1>(&e2))
+            return *f1 == *f2;
+    return false;
+}
+
+std::string LockFile::diff(const LockFile & oldLocks, const LockFile & newLocks)
+{
+    auto oldFlat = oldLocks.getAllInputs();
+    auto newFlat = newLocks.getAllInputs();
+
+    auto i = oldFlat.begin();
+    auto j = newFlat.begin();
+    std::string res;
+
+    while (i != oldFlat.end() || j != newFlat.end()) {
+        if (j != newFlat.end() && (i == oldFlat.end() || i->first > j->first)) {
+            res += fmt("* Added '%s': %s\n", printInputPath(j->first), j->second);
+            ++j;
+        } else if (i != oldFlat.end() && (j == newFlat.end() || i->first < j->first)) {
+            res += fmt("* Removed '%s'\n", printInputPath(i->first));
+            ++i;
+        } else {
+            if (!equals(i->second, j->second)) {
+                res += fmt("* Updated '%s': %s -> %s\n",
+                    printInputPath(i->first),
+                    i->second,
+                    j->second);
+            }
+            ++i;
+            ++j;
+        }
+    }
+
+    return res;
+}
+
+void LockFile::check()
+{
+    auto inputs = getAllInputs();
+
+    for (auto & [inputPath, input] : inputs) {
+        if (auto follows = std::get_if<1>(&input)) {
+            if (!follows->empty() && !get(inputs, *follows))
+                throw Error("input '%s' follows a non-existent input '%s'",
+                    printInputPath(inputPath),
+                    printInputPath(*follows));
+        }
+    }
+}
+
+void check();
+
+std::string printInputPath(const InputPath & path)
+{
+    return concatStringsSep("/", path);
+}
+
+}
diff --git a/src/libexpr/flake/lockfile.hh b/src/libexpr/flake/lockfile.hh
new file mode 100644
index 000000000..5e7cfda3e
--- /dev/null
+++ b/src/libexpr/flake/lockfile.hh
@@ -0,0 +1,85 @@
+#pragma once
+
+#include "flakeref.hh"
+
+#include <nlohmann/json_fwd.hpp>
+
+namespace nix {
+class Store;
+struct StorePath;
+}
+
+namespace nix::flake {
+
+using namespace fetchers;
+
+typedef std::vector<FlakeId> InputPath;
+
+struct LockedNode;
+
+/* A node in the lock file. It has outgoing edges to other nodes (its
+   inputs). Only the root node has this type; all other nodes have
+   type LockedNode. */
+struct Node : std::enable_shared_from_this<Node>
+{
+    typedef std::variant<std::shared_ptr<LockedNode>, InputPath> Edge;
+
+    std::map<FlakeId, Edge> inputs;
+
+    virtual ~Node() { }
+};
+
+/* A non-root node in the lock file. */
+struct LockedNode : Node
+{
+    FlakeRef lockedRef, originalRef;
+    bool isFlake = true;
+
+    LockedNode(
+        const FlakeRef & lockedRef,
+        const FlakeRef & originalRef,
+        bool isFlake = true)
+        : lockedRef(lockedRef), originalRef(originalRef), isFlake(isFlake)
+    { }
+
+    LockedNode(const nlohmann::json & json);
+
+    StorePath computeStorePath(Store & store) const;
+};
+
+struct LockFile
+{
+    std::shared_ptr<Node> root = std::make_shared<Node>();
+
+    LockFile() {};
+    LockFile(const nlohmann::json & json, const Path & path);
+
+    nlohmann::json toJson() const;
+
+    std::string to_string() const;
+
+    static LockFile read(const Path & path);
+
+    void write(const Path & path) const;
+
+    bool isImmutable() const;
+
+    bool operator ==(const LockFile & other) const;
+
+    std::shared_ptr<Node> findInput(const InputPath & path);
+
+    std::map<InputPath, Node::Edge> getAllInputs() const;
+
+    static std::string diff(const LockFile & oldLocks, const LockFile & newLocks);
+
+    /* Check that every 'follows' input target exists. */
+    void check();
+};
+
+std::ostream & operator <<(std::ostream & stream, const LockFile & lockFile);
+
+InputPath parseInputPath(std::string_view s);
+
+std::string printInputPath(const InputPath & path);
+
+}
diff --git a/src/libexpr/local.mk b/src/libexpr/local.mk
index 9ed39e745..d84b150e0 100644
--- a/src/libexpr/local.mk
+++ b/src/libexpr/local.mk
@@ -4,7 +4,12 @@ libexpr_NAME = libnixexpr
 
 libexpr_DIR := $(d)
 
-libexpr_SOURCES := $(wildcard $(d)/*.cc) $(wildcard $(d)/primops/*.cc) $(d)/lexer-tab.cc $(d)/parser-tab.cc
+libexpr_SOURCES := \
+  $(wildcard $(d)/*.cc) \
+  $(wildcard $(d)/primops/*.cc) \
+  $(wildcard $(d)/flake/*.cc) \
+  $(d)/lexer-tab.cc \
+  $(d)/parser-tab.cc
 
 libexpr_CXXFLAGS += -I src/libutil -I src/libstore -I src/libfetchers -I src/libmain -I src/libexpr
 
@@ -34,4 +39,9 @@ dist-files += $(d)/parser-tab.cc $(d)/parser-tab.hh $(d)/lexer-tab.cc $(d)/lexer
 
 $(eval $(call install-file-in, $(d)/nix-expr.pc, $(prefix)/lib/pkgconfig, 0644))
 
+$(foreach i, $(wildcard src/libexpr/flake/*.hh), \
+  $(eval $(call install-file-in, $(i), $(includedir)/nix/flake, 0644)))
+
 $(d)/primops.cc: $(d)/imported-drv-to-derivation.nix.gen.hh
+
+$(d)/flake/flake.cc: $(d)/flake/call-flake.nix.gen.hh
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 878f06c96..24b21f7da 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -719,7 +719,7 @@ std::pair<bool, std::string> EvalState::resolveSearchPathElem(const SearchPathEl
     if (isUri(elem.second)) {
         try {
             res = { true, store->toRealPath(fetchers::downloadTarball(
-                        store, resolveUri(elem.second), "source", false).storePath) };
+                        store, resolveUri(elem.second), "source", false).first.storePath) };
         } catch (FileTransferError & e) {
             logWarning({
                 .name = "Entry download",
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 138e00f48..09989102a 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -30,18 +30,6 @@ namespace nix {
  *************************************************************/
 
 
-/* Decode a context string ‘!<name>!<path>’ into a pair <path,
-   name>. */
-std::pair<string, string> decodeContext(const string & s)
-{
-    if (s.at(0) == '!') {
-        size_t index = s.find("!", 1);
-        return std::pair<string, string>(string(s, index + 1), string(s, 1, index - 1));
-    } else
-        return std::pair<string, string>(s.at(0) == '/' ? s : string(s, 1), "");
-}
-
-
 InvalidPathError::InvalidPathError(const Path & path) :
     EvalError("path '%s' is not valid", path), path(path) {}
 
@@ -883,10 +871,10 @@ static void prim_storePath(EvalState & state, const Pos & pos, Value * * args, V
             .hint = hintfmt("path '%1%' is not in the Nix store", path),
             .errPos = pos
         });
-    Path path2 = state.store->toStorePath(path);
+    auto path2 = state.store->toStorePath(path).first;
     if (!settings.readOnlyMode)
-        state.store->ensurePath(state.store->parseStorePath(path2));
-    context.insert(path2);
+        state.store->ensurePath(path2);
+    context.insert(state.store->printStorePath(path2));
     mkString(v, path, context);
 }
 
diff --git a/src/libexpr/primops/fetchGit.cc b/src/libexpr/primops/fetchGit.cc
index 9b9754e25..1d64caac3 100644
--- a/src/libexpr/primops/fetchGit.cc
+++ b/src/libexpr/primops/fetchGit.cc
@@ -62,23 +62,23 @@ static void prim_fetchGit(EvalState & state, const Pos & pos, Value * * args, Va
     attrs.insert_or_assign("url", url.find("://") != std::string::npos ? url : "file://" + url);
     if (ref) attrs.insert_or_assign("ref", *ref);
     if (rev) attrs.insert_or_assign("rev", rev->gitRev());
-    if (fetchSubmodules) attrs.insert_or_assign("submodules", true);
-    auto input = fetchers::inputFromAttrs(attrs);
+    if (fetchSubmodules) attrs.insert_or_assign("submodules", fetchers::Explicit<bool>{true});
+    auto input = fetchers::Input::fromAttrs(std::move(attrs));
 
     // FIXME: use name?
-    auto [tree, input2] = input->fetchTree(state.store);
+    auto [tree, input2] = input.fetch(state.store);
 
     state.mkAttrs(v, 8);
     auto storePath = state.store->printStorePath(tree.storePath);
     mkString(*state.allocAttr(v, state.sOutPath), storePath, PathSet({storePath}));
     // Backward compatibility: set 'rev' to
     // 0000000000000000000000000000000000000000 for a dirty tree.
-    auto rev2 = input2->getRev().value_or(Hash(htSHA1));
+    auto rev2 = input2.getRev().value_or(Hash(htSHA1));
     mkString(*state.allocAttr(v, state.symbols.create("rev")), rev2.gitRev());
     mkString(*state.allocAttr(v, state.symbols.create("shortRev")), rev2.gitShortRev());
     // Backward compatibility: set 'revCount' to 0 for a dirty tree.
     mkInt(*state.allocAttr(v, state.symbols.create("revCount")),
-        tree.info.revCount.value_or(0));
+        input2.getRevCount().value_or(0));
     mkBool(*state.allocAttr(v, state.symbols.create("submodules")), fetchSubmodules);
     v.attrs->sort();
 
diff --git a/src/libexpr/primops/fetchMercurial.cc b/src/libexpr/primops/fetchMercurial.cc
index d2340f4ca..cef85cfef 100644
--- a/src/libexpr/primops/fetchMercurial.cc
+++ b/src/libexpr/primops/fetchMercurial.cc
@@ -65,23 +65,23 @@ static void prim_fetchMercurial(EvalState & state, const Pos & pos, Value * * ar
     attrs.insert_or_assign("url", url.find("://") != std::string::npos ? url : "file://" + url);
     if (ref) attrs.insert_or_assign("ref", *ref);
     if (rev) attrs.insert_or_assign("rev", rev->gitRev());
-    auto input = fetchers::inputFromAttrs(attrs);
+    auto input = fetchers::Input::fromAttrs(std::move(attrs));
 
     // FIXME: use name
-    auto [tree, input2] = input->fetchTree(state.store);
+    auto [tree, input2] = input.fetch(state.store);
 
     state.mkAttrs(v, 8);
     auto storePath = state.store->printStorePath(tree.storePath);
     mkString(*state.allocAttr(v, state.sOutPath), storePath, PathSet({storePath}));
-    if (input2->getRef())
-        mkString(*state.allocAttr(v, state.symbols.create("branch")), *input2->getRef());
+    if (input2.getRef())
+        mkString(*state.allocAttr(v, state.symbols.create("branch")), *input2.getRef());
     // Backward compatibility: set 'rev' to
     // 0000000000000000000000000000000000000000 for a dirty tree.
-    auto rev2 = input2->getRev().value_or(Hash(htSHA1));
+    auto rev2 = input2.getRev().value_or(Hash(htSHA1));
     mkString(*state.allocAttr(v, state.symbols.create("rev")), rev2.gitRev());
     mkString(*state.allocAttr(v, state.symbols.create("shortRev")), std::string(rev2.gitRev(), 0, 12));
-    if (tree.info.revCount)
-        mkInt(*state.allocAttr(v, state.symbols.create("revCount")), *tree.info.revCount);
+    if (auto revCount = input2.getRevCount())
+        mkInt(*state.allocAttr(v, state.symbols.create("revCount")), *revCount);
     v.attrs->sort();
 
     if (state.allowedPaths)
diff --git a/src/libexpr/primops/fetchTree.cc b/src/libexpr/primops/fetchTree.cc
index f6d8cca44..5f480d919 100644
--- a/src/libexpr/primops/fetchTree.cc
+++ b/src/libexpr/primops/fetchTree.cc
@@ -3,6 +3,7 @@
 #include "store-api.hh"
 #include "fetchers.hh"
 #include "filetransfer.hh"
+#include "registry.hh"
 
 #include <ctime>
 #include <iomanip>
@@ -12,30 +13,37 @@ namespace nix {
 void emitTreeAttrs(
     EvalState & state,
     const fetchers::Tree & tree,
-    std::shared_ptr<const fetchers::Input> input,
+    const fetchers::Input & input,
     Value & v)
 {
+    assert(input.isImmutable());
+
     state.mkAttrs(v, 8);
 
     auto storePath = state.store->printStorePath(tree.storePath);
 
     mkString(*state.allocAttr(v, state.sOutPath), storePath, PathSet({storePath}));
 
-    assert(tree.info.narHash);
+    // FIXME: support arbitrary input attributes.
+
+    auto narHash = input.getNarHash();
+    assert(narHash);
     mkString(*state.allocAttr(v, state.symbols.create("narHash")),
-        tree.info.narHash->to_string(SRI, true));
+        narHash->to_string(SRI, true));
 
-    if (input->getRev()) {
-        mkString(*state.allocAttr(v, state.symbols.create("rev")), input->getRev()->gitRev());
-        mkString(*state.allocAttr(v, state.symbols.create("shortRev")), input->getRev()->gitShortRev());
+    if (auto rev = input.getRev()) {
+        mkString(*state.allocAttr(v, state.symbols.create("rev")), rev->gitRev());
+        mkString(*state.allocAttr(v, state.symbols.create("shortRev")), rev->gitShortRev());
     }
 
-    if (tree.info.revCount)
-        mkInt(*state.allocAttr(v, state.symbols.create("revCount")), *tree.info.revCount);
+    if (auto revCount = input.getRevCount())
+        mkInt(*state.allocAttr(v, state.symbols.create("revCount")), *revCount);
 
-    if (tree.info.lastModified)
-        mkString(*state.allocAttr(v, state.symbols.create("lastModified")),
-            fmt("%s", std::put_time(std::gmtime(&*tree.info.lastModified), "%Y%m%d%H%M%S")));
+    if (auto lastModified = input.getLastModified()) {
+        mkInt(*state.allocAttr(v, state.symbols.create("lastModified")), *lastModified);
+        mkString(*state.allocAttr(v, state.symbols.create("lastModifiedDate")),
+            fmt("%s", std::put_time(std::gmtime(&*lastModified), "%Y%m%d%H%M%S")));
+    }
 
     v.attrs->sort();
 }
@@ -44,7 +52,7 @@ static void prim_fetchTree(EvalState & state, const Pos & pos, Value * * args, V
 {
     settings.requireExperimentalFeature("flakes");
 
-    std::shared_ptr<const fetchers::Input> input;
+    fetchers::Input input;
     PathSet context;
 
     state.forceValue(*args[0]);
@@ -59,9 +67,11 @@ static void prim_fetchTree(EvalState & state, const Pos & pos, Value * * args, V
             if (attr.value->type == tString)
                 attrs.emplace(attr.name, attr.value->string.s);
             else if (attr.value->type == tBool)
-                attrs.emplace(attr.name, attr.value->boolean);
+                attrs.emplace(attr.name, fetchers::Explicit<bool>{attr.value->boolean});
+            else if (attr.value->type == tInt)
+                attrs.emplace(attr.name, attr.value->integer);
             else
-                throw TypeError("fetchTree argument '%s' is %s while a string or Boolean is expected",
+                throw TypeError("fetchTree argument '%s' is %s while a string, Boolean or integer is expected",
                     attr.name, showType(*attr.value));
         }
 
@@ -71,15 +81,17 @@ static void prim_fetchTree(EvalState & state, const Pos & pos, Value * * args, V
                 .errPos = pos
             });
 
-        input = fetchers::inputFromAttrs(attrs);
+        input = fetchers::Input::fromAttrs(std::move(attrs));
     } else
-        input = fetchers::inputFromURL(state.coerceToString(pos, *args[0], context, false, false));
+        input = fetchers::Input::fromURL(state.coerceToString(pos, *args[0], context, false, false));
+
+    if (!evalSettings.pureEval && !input.isDirect())
+        input = lookupInRegistries(state.store, input).first;
 
-    if (evalSettings.pureEval && !input->isImmutable())
-        throw Error("in pure evaluation mode, 'fetchTree' requires an immutable input");
+    if (evalSettings.pureEval && !input.isImmutable())
+        throw Error("in pure evaluation mode, 'fetchTree' requires an immutable input, at %s", pos);
 
-    // FIXME: use fetchOrSubstituteTree
-    auto [tree, input2] = input->fetchTree(state.store);
+    auto [tree, input2] = input.fetch(state.store);
 
     if (state.allowedPaths)
         state.allowedPaths->insert(tree.actualPath);
@@ -136,7 +148,7 @@ static void fetch(EvalState & state, const Pos & pos, Value * * args, Value & v,
 
     auto storePath =
         unpack
-        ? fetchers::downloadTarball(state.store, *url, name, (bool) expectedHash).storePath
+        ? fetchers::downloadTarball(state.store, *url, name, (bool) expectedHash).first.storePath
         : fetchers::downloadFile(state.store, *url, name, (bool) expectedHash).storePath;
 
     auto path = state.store->toRealPath(storePath);
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
index 7ba5e1c14..4eb6dac81 100644
--- a/src/libexpr/symbol-table.hh
+++ b/src/libexpr/symbol-table.hh
@@ -28,6 +28,12 @@ public:
         return s == s2.s;
     }
 
+    // FIXME: remove
+    bool operator == (std::string_view s2) const
+    {
+        return s->compare(s2) == 0;
+    }
+
     bool operator != (const Symbol & s2) const
     {
         return s != s2.s;
@@ -68,9 +74,10 @@ private:
     Symbols symbols;
 
 public:
-    Symbol create(const string & s)
+    Symbol create(std::string_view s)
     {
-        std::pair<Symbols::iterator, bool> res = symbols.insert(s);
+        // FIXME: avoid allocation if 's' already exists in the symbol table.
+        std::pair<Symbols::iterator, bool> res = symbols.emplace(std::string(s));
         return Symbol(&*res.first);
     }
 
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
index 71025824e..fe11bb2ed 100644
--- a/src/libexpr/value.hh
+++ b/src/libexpr/value.hh
@@ -166,6 +166,13 @@ struct Value
     {
         return type == tList1 ? 1 : type == tList2 ? 2 : bigList.size;
     }
+
+    /* Check whether forcing this value requires a trivial amount of
+       computation. In particular, function applications are
+       non-trivial. */
+    bool isTrivial() const;
+
+    std::vector<std::pair<Path, std::string>> getContext();
 };