Revert "Revert "Merge pull request #6621 from Kha/nested-follows""

This reverts commit a8b3d777fbdaf0b732f129e5be62cd2a1227674b.

This undoes the revert of PR#6621, which allows nested `follows`, i.e.

    {
      inputs = {
        foo.url = "github:bar/foo";
        foo.inputs.bar.inputs.nixpkgs = "nixpkgs";
      };
    }

does the expected thing now. This is useful to avoid the 1000 instances
of nixpkgs problem without having each flake in the dependency tree to
expose all of its transitive dependencies for modification.

This was in fact part of Nix before and the C++ changes applied w/o
conflicts. However, it got reverted then because people didn't want to
merge lazy-trees against it which was supposed to be merged soon back in
October 2022.

Fixes: https://git.lix.systems/lix-project/lix/issues/201

Change-Id: I5ddef914135b695717b2ef88862d57ced5e7aa3c

3 files changed, 115 insertions, 13 deletions

diff --git a/doc/manual/rl-next/fix-nested-follows.md b/doc/manual/rl-next/fix-nested-follows.md
new file mode 100644
index 000000000..d4a381ba4
--- /dev/null
+++ b/doc/manual/rl-next/fix-nested-follows.md
@@ -0,0 +1,21 @@
+---
+synopsis: Fix nested flake input `follows`
+prs: 6621
+cls: 994
+---
+
+Previously nested-input overrides were ignored; that is, the following did not
+override anything, in spite of the `nix3-flake` manual documenting it working:
+
+```
+{
+  inputs = {
+    foo.url = "github:bar/foo";
+    foo.inputs.bar.inputs.nixpkgs = "nixpkgs";
+  };
+}
+```
+
+This is useful to avoid the 1000 instances of nixpkgs problem without having
+each flake in the dependency tree to expose all of its transitive dependencies
+for modification.
diff --git a/src/libexpr/flake/flake.cc b/src/libexpr/flake/flake.cc
index 4cc2ab43b..e13d1cb93 100644
--- a/src/libexpr/flake/flake.cc
+++ b/src/libexpr/flake/flake.cc
@@ -91,11 +91,11 @@ static void expectType(EvalState & state, ValueType type,
 
 static std::map<FlakeId, FlakeInput> parseFlakeInputs(
     EvalState & state, Value * value, const PosIdx pos,
-    const std::optional<Path> & baseDir, InputPath lockRootPath);
+    const std::optional<Path> & baseDir, InputPath lockRootPath, unsigned depth);
 
 static FlakeInput parseFlakeInput(EvalState & state,
     const std::string & inputName, Value * value, const PosIdx pos,
-    const std::optional<Path> & baseDir, InputPath lockRootPath)
+    const std::optional<Path> & baseDir, InputPath lockRootPath, unsigned depth)
 {
     expectType(state, nAttrs, *value, pos);
 
@@ -119,7 +119,7 @@ static FlakeInput parseFlakeInput(EvalState & state,
                 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, baseDir, lockRootPath);
+                input.overrides = parseFlakeInputs(state, attr.value, attr.pos, baseDir, lockRootPath, depth + 1);
             } else if (attr.name == sFollows) {
                 expectType(state, nString, *attr.value, attr.pos);
                 auto follows(parseInputPath(attr.value->string.s));
@@ -168,7 +168,11 @@ static FlakeInput parseFlakeInput(EvalState & state,
             input.ref = parseFlakeRef(*url, baseDir, true, input.isFlake);
     }
 
-    if (!input.follows && !input.ref)
+    if (!input.follows && !input.ref && depth == 0)
+        // in `input.nixops.inputs.nixpkgs.url = ...`, we assume `nixops` is from
+        // the flake registry absent `ref`/`follows`, but we should not assume so
+        // about `nixpkgs` (where `depth == 1`) as the `nixops` flake should
+        // determine its default source
         input.ref = FlakeRef::fromAttrs({{"type", "indirect"}, {"id", inputName}});
 
     return input;
@@ -176,7 +180,7 @@ static FlakeInput parseFlakeInput(EvalState & state,
 
 static std::map<FlakeId, FlakeInput> parseFlakeInputs(
     EvalState & state, Value * value, const PosIdx pos,
-    const std::optional<Path> & baseDir, InputPath lockRootPath)
+    const std::optional<Path> & baseDir, InputPath lockRootPath, unsigned depth)
 {
     std::map<FlakeId, FlakeInput> inputs;
 
@@ -189,7 +193,8 @@ static std::map<FlakeId, FlakeInput> parseFlakeInputs(
                 inputAttr.value,
                 inputAttr.pos,
                 baseDir,
-                lockRootPath));
+                lockRootPath,
+                depth));
     }
 
     return inputs;
@@ -239,7 +244,7 @@ static Flake getFlake(
     auto sInputs = state.symbols.create("inputs");
 
     if (auto inputs = vInfo.attrs->get(sInputs))
-        flake.inputs = parseFlakeInputs(state, inputs->value, inputs->pos, flakeDir, lockRootPath);
+        flake.inputs = parseFlakeInputs(state, inputs->value, inputs->pos, flakeDir, lockRootPath, 0);
 
     auto sOutputs = state.symbols.create("outputs");
 
@@ -322,6 +327,19 @@ Flake getFlake(EvalState & state, const FlakeRef & originalRef, bool allowLookup
     return getFlake(state, originalRef, allowLookup, flakeCache);
 }
 
+/* Recursively merge `overrides` into `overrideMap` */
+static void updateOverrides(std::map<InputPath, FlakeInput> & overrideMap, const FlakeInputs & overrides,
+                       const InputPath & inputPathPrefix)
+{
+    for (auto & [id, input] : overrides) {
+        auto inputPath(inputPathPrefix);
+        inputPath.push_back(id);
+        // Do not override existing assignment from outer flake
+        overrideMap.insert({inputPath, input});
+        updateOverrides(overrideMap, input.overrides, inputPath);
+    }
+}
+
 /* 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(
@@ -394,12 +412,9 @@ LockedFlake lockFlake(
             /* 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);
-                }
+                auto inputPath(inputPathPrefix);
+                inputPath.push_back(id);
+                updateOverrides(overrides, input.overrides, inputPath);
             }
 
             /* Check whether this input has overrides for a
@@ -434,6 +449,12 @@ LockedFlake lockFlake(
                         // Respect the “flakeness” of the input even if we
                         // override it
                         i->second.isFlake = input2.isFlake;
+                        if (!i->second.ref)
+                            i->second.ref = input2.ref;
+                        if (!i->second.follows)
+                            i->second.follows = input2.follows;
+                        // Note that `input.overrides` is not used in the following,
+                        // so no need to merge it here (already done by `updateOverrides`)
                     }
                     auto & input = hasOverride ? i->second : input2;
 
diff --git a/tests/functional/flakes/follow-paths.sh b/tests/functional/flakes/follow-paths.sh
index 183893bde..cd3f75693 100644
--- a/tests/functional/flakes/follow-paths.sh
+++ b/tests/functional/flakes/follow-paths.sh
@@ -230,3 +230,63 @@ git -C "$flakeFollowsOverloadA" add flake.nix flakeB/flake.nix \
 nix flake metadata "$flakeFollowsOverloadA"
 nix flake update --flake "$flakeFollowsOverloadA"
 nix flake lock "$flakeFollowsOverloadA"
+
+# Test nested flake overrides: A overrides B/C/D
+
+cat <<EOF > $flakeFollowsD/flake.nix
+{ outputs = _: {}; }
+EOF
+cat <<EOF > $flakeFollowsC/flake.nix
+{
+  inputs.D.url = "path:nosuchflake";
+  outputs = _: {};
+}
+EOF
+cat <<EOF > $flakeFollowsB/flake.nix
+{
+  inputs.C.url = "path:$flakeFollowsC";
+  outputs = _: {};
+}
+EOF
+cat <<EOF > $flakeFollowsA/flake.nix
+{
+  inputs.B.url = "path:$flakeFollowsB";
+  inputs.D.url = "path:$flakeFollowsD";
+  inputs.B.inputs.C.inputs.D.follows = "D";
+  outputs = _: {};
+}
+EOF
+
+nix flake lock $flakeFollowsA
+
+[[ $(jq -c .nodes.C.inputs.D $flakeFollowsA/flake.lock) = '["D"]' ]]
+
+# Test overlapping flake follows: B has D follow C/D, while A has B/C follow C
+
+cat <<EOF > $flakeFollowsC/flake.nix
+{
+  inputs.D.url = "path:$flakeFollowsD";
+  outputs = _: {};
+}
+EOF
+cat <<EOF > $flakeFollowsB/flake.nix
+{
+  inputs.C.url = "path:nosuchflake";
+  inputs.D.url = "path:nosuchflake";
+  inputs.D.follows = "C/D";
+  outputs = _: {};
+}
+EOF
+cat <<EOF > $flakeFollowsA/flake.nix
+{
+  inputs.B.url = "path:$flakeFollowsB";
+  inputs.C.url = "path:$flakeFollowsC";
+  inputs.B.inputs.C.follows = "C";
+  outputs = _: {};
+}
+EOF
+
+# bug was not triggered without recreating the lockfile
+nix flake update --flake $flakeFollowsA
+
+[[ $(jq -c .nodes.B.inputs.D $flakeFollowsA/flake.lock) = '["B","C","D"]' ]]