Merge pull request #5212 from mkenigs/auto-uid-allocation

Merge master into #3600

8 files changed, 1719 insertions, 0 deletions

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/config.cc b/src/libexpr/flake/config.cc
new file mode 100644
index 000000000..41b6f78ed
--- /dev/null
+++ b/src/libexpr/flake/config.cc
@@ -0,0 +1,83 @@
+#include "flake.hh"
+
+#include <nlohmann/json.hpp>
+
+namespace nix::flake {
+
+// setting name -> setting value -> allow or ignore.
+typedef std::map<std::string, std::map<std::string, bool>> TrustedList;
+
+Path trustedListPath()
+{
+    return getDataDir() + "/nix/trusted-settings.json";
+}
+
+static TrustedList readTrustedList()
+{
+    auto path = trustedListPath();
+    if (!pathExists(path)) return {};
+    auto json = nlohmann::json::parse(readFile(path));
+    return json;
+}
+
+static void writeTrustedList(const TrustedList & trustedList)
+{
+    auto path = trustedListPath();
+    createDirs(dirOf(path));
+    writeFile(path, nlohmann::json(trustedList).dump());
+}
+
+void ConfigFile::apply()
+{
+    std::set<std::string> whitelist{"bash-prompt", "bash-prompt-suffix", "flake-registry"};
+
+    for (auto & [name, value] : settings) {
+
+        auto baseName = hasPrefix(name, "extra-") ? std::string(name, 6) : name;
+
+        // FIXME: Move into libutil/config.cc.
+        std::string valueS;
+        if (auto s = std::get_if<std::string>(&value))
+            valueS = *s;
+        else if (auto n = std::get_if<int64_t>(&value))
+            valueS = fmt("%d", n);
+        else if (auto b = std::get_if<Explicit<bool>>(&value))
+            valueS = b->t ? "true" : "false";
+        else if (auto ss = std::get_if<std::vector<std::string>>(&value))
+            valueS = concatStringsSep(" ", *ss); // FIXME: evil
+        else
+            assert(false);
+
+        if (!whitelist.count(baseName)) {
+            auto trustedList = readTrustedList();
+
+            bool trusted = false;
+
+            if (auto saved = get(get(trustedList, name).value_or(std::map<std::string, bool>()), valueS)) {
+                trusted = *saved;
+            } else {
+                // FIXME: filter ANSI escapes, newlines, \r, etc.
+                if (std::tolower(logger->ask(fmt("do you want to allow configuration setting '%s' to be set to '" ANSI_RED "%s" ANSI_NORMAL "' (y/N)?", name, valueS)).value_or('n')) != 'y') {
+                    if (std::tolower(logger->ask("do you want to permanently mark this value as untrusted (y/N)?").value_or('n')) == 'y') {
+                        trustedList[name][valueS] = false;
+                        writeTrustedList(trustedList);
+                    }
+                } else {
+                    if (std::tolower(logger->ask("do you want to permanently mark this value as trusted (y/N)?").value_or('n')) == 'y') {
+                        trustedList[name][valueS] = trusted = true;
+                        writeTrustedList(trustedList);
+                    }
+                }
+            }
+
+            if (!trusted) {
+                warn("ignoring untrusted flake configuration setting '%s'", name);
+                continue;
+            }
+        }
+
+        globalConfig.set(name, valueS);
+    }
+}
+
+}
diff --git a/src/libexpr/flake/flake.cc b/src/libexpr/flake/flake.cc
new file mode 100644
index 000000000..010d97285
--- /dev/null
+++ b/src/libexpr/flake/flake.cc
@@ -0,0 +1,714 @@
+#include "flake.hh"
+#include "eval.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<fetchers::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});
+                fetched.emplace(*fetchedResolved);
+            }
+            else {
+                throw Error("'%s' is an indirect flake reference, but registry lookups are not allowed", originalRef);
+            }
+        }
+        flakeCache.push_back({originalRef, *fetched});
+    }
+
+    auto [tree, lockedRef] = *fetched;
+
+    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 forceTrivialValue(EvalState & state, Value & value, const Pos & pos)
+{
+    if (value.isThunk() && value.isTrivial())
+        state.forceValue(value, pos);
+}
+
+
+static void expectType(EvalState & state, ValueType type,
+    Value & value, const Pos & pos)
+{
+    forceTrivialValue(state, 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, nAttrs, *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, nString, *attr.value, *attr.pos);
+                url = attr.value->string.s;
+                attrs.emplace("url", *url);
+            } else if (attr.name == sFlake) {
+                expectType(state, nBool, *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, nString, *attr.value, *attr.pos);
+                input.follows = parseInputPath(attr.value->string.s);
+            } else {
+                switch (attr.value->type()) {
+                    case nString:
+                        attrs.emplace(attr.name, attr.value->string.s);
+                        break;
+                    case nBool:
+                        attrs.emplace(attr.name, Explicit<bool> { attr.value->boolean });
+                        break;
+                    case nInt:
+                        attrs.emplace(attr.name, (long unsigned int)attr.value->integer);
+                        break;
+                    default:
+                        throw TypeError("flake input attribute '%s' is %s while a string, Boolean, or integer 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, nAttrs, *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, nAttrs, vInfo, Pos(foFile, state.symbols.create(flakeFile), 0, 0));
+
+    if (auto description = vInfo.attrs->get(state.sDescription)) {
+        expectType(state, nString, *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, nFunction, *outputs->value, *outputs->pos);
+
+        if (outputs->value->isLambda() && outputs->value->lambda.fun->matchAttrs) {
+            for (auto & formal : outputs->value->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);
+
+    auto sNixConfig = state.symbols.create("nixConfig");
+
+    if (auto nixConfig = vInfo.attrs->get(sNixConfig)) {
+        expectType(state, nAttrs, *nixConfig->value, *nixConfig->pos);
+
+        for (auto & setting : *nixConfig->value->attrs) {
+            forceTrivialValue(state, *setting.value, *setting.pos);
+            if (setting.value->type() == nString)
+                flake.config.settings.insert({setting.name, state.forceStringNoCtx(*setting.value, *setting.pos)});
+            else if (setting.value->type() == nInt)
+                flake.config.settings.insert({setting.name, state.forceInt(*setting.value, *setting.pos)});
+            else if (setting.value->type() == nBool)
+                flake.config.settings.insert({setting.name, state.forceBool(*setting.value, *setting.pos)});
+            else if (setting.value->type() == nList) {
+                std::vector<std::string> ss;
+                for (unsigned int n = 0; n < setting.value->listSize(); ++n) {
+                    auto elem = setting.value->listElems()[n];
+                    if (elem->type() != nString)
+                        throw TypeError("list element in flake configuration setting '%s' is %s while a string is expected",
+                            setting.name, showType(*setting.value));
+                    ss.push_back(state.forceStringNoCtx(*elem, *setting.pos));
+                }
+                flake.config.settings.insert({setting.name, ss});
+            }
+            else
+                throw TypeError("flake configuration setting '%s' is %s",
+                    setting.name, showType(*setting.value));
+        }
+    }
+
+    for (auto & attr : *vInfo.attrs) {
+        if (attr.name != state.sDescription &&
+            attr.name != sInputs &&
+            attr.name != sOutputs &&
+            attr.name != sNixConfig)
+            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, if the flake is writable. */
+LockedFlake lockFlake(
+    EvalState & state,
+    const FlakeRef & topRef,
+    const LockFlags & lockFlags)
+{
+    settings.requireExperimentalFeature("flakes");
+
+    FlakeCache flakeCache;
+
+    auto useRegistries = lockFlags.useRegistries.value_or(settings.useRegistries);
+
+    auto flake = getFlake(state, topRef, useRegistries, flakeCache);
+
+    if (lockFlags.applyNixConfig) {
+        flake.config.apply();
+        // FIXME: send new config to the daemon.
+    }
+
+    try {
+
+        // 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;
+
+        struct LockParent {
+            /* The path to this parent. */
+            InputPath path;
+
+            /* Whether we are currently inside a top-level lockfile
+               (inputs absolute) or subordinate lockfile (inputs
+               relative). */
+            bool absolute;
+        };
+
+        std::function<void(
+            const FlakeInputs & flakeInputs,
+            std::shared_ptr<Node> node,
+            const InputPath & inputPathPrefix,
+            std::shared_ptr<const Node> oldNode,
+            const LockParent & parent,
+            const Path & parentPath)>
+            computeLocks;
+
+        computeLocks = [&](
+            const FlakeInputs & flakeInputs,
+            std::shared_ptr<Node> node,
+            const InputPath & inputPathPrefix,
+            std::shared_ptr<const Node> oldNode,
+            const LockParent & parent,
+            const Path & parentPath)
+        {
+            debug("computing lock file node '%s'", printInputPath(inputPathPrefix));
+
+            /* Get the overrides (i.e. attributes of the form
+               'inputs.nixops.inputs.nixpkgs.url = ...'). */
+            for (auto & [id, input] : flakeInputs) {
+                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);
+
+                try {
+
+                    /* 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);
+                        // Respect the “flakeness” of the input even if we
+                        // override it
+                        i->second.isFlake = input2.isFlake;
+                    }
+                    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 (parent.absolute && !hasOverride) {
+                            target = *input.follows;
+                        } else {
+                            if (hasOverride) {
+                                target = inputPathPrefix;
+                                target.pop_back();
+                            } else
+                                target = parent.path;
+
+                            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
+                           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, parent, parentPath);
+                        } 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,
+                                    });
+                                }
+                            }
+
+                            computeLocks(fakeInputs, childNode, inputPath, oldLock, parent, parentPath);
+                        }
+
+                    } 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) {
+                            Path localPath = parentPath;
+                            FlakeRef localRef = *input.ref;
+
+                            // If this input is a path, recurse it down.
+                            // This allows us to resolve path inputs relative to the current flake.
+                            if (localRef.input.getType() == "path") {
+                                localRef.input.parent = parentPath;
+                                localPath = canonPath(parentPath + "/" + *input.ref->input.getSourcePath());
+                            }
+
+                            auto inputFlake = getFlake(state, localRef, 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(); });
+
+                            // Follows paths from existing inputs in the top-level lockfile are absolute,
+                            // whereas paths in subordinate lockfiles are relative to those lockfiles.
+                            LockParent newParent {
+                                .path = inputPath,
+                                .absolute = oldLock ? true : false
+                            };
+
+                            /* 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,
+                                newParent, localPath);
+                        }
+
+                        else {
+                            auto [sourceInfo, resolvedRef, lockedRef] = fetchOrSubstituteTree(
+                                state, *input.ref, useRegistries, flakeCache);
+                            node->inputs.insert_or_assign(id,
+                                std::make_shared<LockedNode>(lockedRef, *input.ref, false));
+                        }
+                    }
+
+                } catch (Error & e) {
+                    e.addTrace({}, "while updating the flake input '%s'", inputPathS);
+                    throw;
+                }
+            }
+        };
+
+        LockParent parent {
+            .path = {},
+            .absolute = true
+        };
+
+        // Bring in the current ref for relative path resolution if we have it
+        auto parentPath = canonPath(flake.sourceInfo->actualPath + "/" + flake.lockedRef.subdir);
+
+        computeLocks(
+            flake.inputs, newLockFile.root, {},
+            lockFlags.recreateLockFile ? nullptr : oldLockFile.root, parent, parentPath);
+
+        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 lock file changes:\n\n%s",
+                                    relPath, lockFileExists ? "Update" : "Add", filterANSIEscapes(diff, true)))
+                            : 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, 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) };
+
+    } catch (Error & e) {
+        e.addTrace({}, "while updating the lock file of flake '%s'", flake.lockedRef.to_string());
+        throw;
+    }
+}
+
+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);
+
+    if (!state.vCallFlake) {
+        state.vCallFlake = allocRootValue(state.allocValue());
+        state.eval(state.parseExprFromString(
+            #include "call-flake.nix.gen.hh"
+            , "/"), **state.vCallFlake);
+    }
+
+    state.callFunction(**state.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 && settings.useRegistries,
+                .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..d46da9d68
--- /dev/null
+++ b/src/libexpr/flake/flake.hh
@@ -0,0 +1,145 @@
+#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;
+
+/* FlakeInput is the 'Flake'-level parsed form of the "input" entries
+ * in the flake file.
+ *
+ * A FlakeInput is normally constructed by the 'parseFlakeInput'
+ * function which parses the input specification in the '.flake' file
+ * to create a 'FlakeRef' (a fetcher, the fetcher-specific
+ * representation of the input specification, and possibly the fetched
+ * local store path result) and then creating this FlakeInput to hold
+ * that FlakeRef, along with anything that might override that
+ * FlakeRef (like command-line overrides or "follows" specifications).
+ *
+ * A FlakeInput is also sometimes constructed directly from a FlakeRef
+ * instead of starting at the flake-file input specification
+ * (e.g. overrides, follows, and implicit inputs).
+ *
+ * A FlakeInput will usually have one of either "ref" or "follows"
+ * set.  If not otherwise specified, a "ref" will be generated to a
+ * 'type="indirect"' flake, which is treated as simply the name of a
+ * flake to be resolved in the registry.
+ */
+
+struct FlakeInput
+{
+    std::optional<FlakeRef> ref;
+    bool isFlake = true;  // true = process flake to get outputs, false = (fetched) static source path
+    std::optional<InputPath> follows;
+    FlakeInputs overrides;
+};
+
+struct ConfigFile
+{
+    using ConfigValue = std::variant<std::string, int64_t, Explicit<bool>, std::vector<std::string>>;
+
+    std::map<std::string, ConfigValue> settings;
+
+    void apply();
+};
+
+/* The contents of a flake.nix file. */
+struct Flake
+{
+    FlakeRef originalRef;   // the original flake specification (by the user)
+    FlakeRef resolvedRef;   // registry references and caching resolved to the specific underlying flake
+    FlakeRef lockedRef;     // the specific local store result of invoking the fetcher
+    std::optional<std::string> description;
+    std::shared_ptr<const fetchers::Tree> sourceInfo;
+    FlakeInputs inputs;
+    ConfigFile config; // 'nixConfig' attribute
+    ~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'. */
+    std::optional<bool> useRegistries = std::nullopt;
+
+    /* Whether to apply flake's nixConfig attribute to the configuration */
+
+    bool applyNixConfig = false;
+
+    /* 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 overridden. */
+    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, bool emptyRevFallback = false);
+
+}
diff --git a/src/libexpr/flake/flakeref.cc b/src/libexpr/flake/flakeref.cc
new file mode 100644
index 000000000..833e8a776
--- /dev/null
+++ b/src/libexpr/flake/flakeref.cc
@@ -0,0 +1,206 @@
+#include "flakeref.hh"
+#include "store-api.hh"
+#include "url.hh"
+#include "url-parts.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
+{
+    std::map<std::string, std::string> extraQuery;
+    if (subdir != "")
+        extraQuery.insert_or_assign("dir", subdir);
+    return input.toURLString(extraQuery);
+}
+
+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])));
+    }
+
+    else if (std::regex_match(url, match, pathUrlRegex)) {
+        std::string path = match[1];
+        std::string fragment = percentDecode(std::string(match[3]));
+
+        if (baseDir) {
+            /* 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). */
+
+            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 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);
+            }
+
+        } else {
+            if (!hasPrefix(path, "/"))
+                throw BadURL("flake reference '%s' is not an absolute path", url);
+            auto query = decodeQuery(match[2]);
+            path = canonPath(path + "/" + get(query, "dir").value_or(""));
+        }
+
+        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..0292eb210
--- /dev/null
+++ b/src/libexpr/flake/flakeref.hh
@@ -0,0 +1,76 @@
+#pragma once
+
+#include "types.hh"
+#include "hash.hh"
+#include "fetchers.hh"
+
+#include <variant>
+
+namespace nix {
+
+class Store;
+
+typedef std::string FlakeId;
+
+/* A flake reference specifies how to fetch a flake or raw source
+ * (e.g. from a Git repository).  It is created from a URL-like syntax
+ * (e.g. 'github:NixOS/patchelf'), an attrset representation (e.g. '{
+ * type="github"; owner = "NixOS"; repo = "patchelf"; }'), or a local
+ * path.
+ *
+ * Each flake will have a number of FlakeRef objects: one for each
+ * input to the flake.
+ *
+ * The normal method of constructing a FlakeRef is by starting with an
+ * input description (usually the attrs or a url from the flake file),
+ * locating a fetcher for that input, and then capturing the Input
+ * object that fetcher generates (usually via
+ * FlakeRef::fromAttrs(attrs) or parseFlakeRef(url) calls).
+ *
+ * The actual fetch not have been performed yet (i.e. a FlakeRef may
+ * be lazy), but the fetcher can be invoked at any time via the
+ * FlakeRef to ensure the store is populated with this input.
+ */
+
+struct FlakeRef
+{
+    /* fetcher-specific representation of the input, sufficient to
+       perform the fetch operation. */
+    fetchers::Input input;
+
+    /* sub-path within the fetched input that represents this 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..fda340789
--- /dev/null
+++ b/src/libexpr/flake/lockfile.cc
@@ -0,0 +1,356 @@
+#include "lockfile.hh"
+#include "store-api.hh"
+#include "url-parts.hh"
+
+#include <iomanip>
+
+#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 = fetchers::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 : fetchers::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'",
+            fetchers::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()) { // FIXME: remove, obsolete
+                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 nodes = json["nodes"];
+                    auto jsonNode2 = nodes.find(inputKey);
+                    if (jsonNode2 == nodes.end())
+                        throw Error("lock file references missing node '%s'", 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;
+}
+
+static std::string describe(const FlakeRef & flakeRef)
+{
+    auto s = fmt("'%s'", flakeRef.to_string());
+
+    if (auto lastModified = flakeRef.input.getLastModified())
+        s += fmt(" (%s)", std::put_time(std::gmtime(&*lastModified), "%Y-%m-%d"));
+
+    return s;
+}
+
+std::ostream & operator <<(std::ostream & stream, const Node::Edge & edge)
+{
+    if (auto node = std::get_if<0>(&edge))
+        stream << describe((*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("• " ANSI_GREEN "Added input '%s':" ANSI_NORMAL "\n    %s\n",
+                printInputPath(j->first), j->second);
+            ++j;
+        } else if (i != oldFlat.end() && (j == newFlat.end() || i->first < j->first)) {
+            res += fmt("• " ANSI_RED "Removed input '%s'" ANSI_NORMAL "\n", printInputPath(i->first));
+            ++i;
+        } else {
+            if (!equals(i->second, j->second)) {
+                res += fmt("• " ANSI_BOLD "Updated input '%s':" ANSI_NORMAL "\n    %s\n  → %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..96f1edc76
--- /dev/null
+++ b/src/libexpr/flake/lockfile.hh
@@ -0,0 +1,83 @@
+#pragma once
+
+#include "flakeref.hh"
+
+#include <nlohmann/json_fwd.hpp>
+
+namespace nix {
+class Store;
+class StorePath;
+}
+
+namespace nix::flake {
+
+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);
+
+}