fix(tvix/eval): place plain inherits in correct stack slots r/4809

We need to make sure that we compile all plain inherits in a let
expression before declaring any other locals. Plain inherits are special
in the sense that they can never be recursive, instead resolving to a
higher scope. Thus we need to compile their value, before declaring
them. If we don't do that, before any other local can be declared,
we cause a situation where the plain inherits' values are placed into
other locals' stack slots.

Note that we can't integrate the plain inherit compilation into the
regular 2-3 phase model where we defer the compilation of the value or
we'd compile `let inherit x; in …` as `let x = x; in …`.

Change-Id: I951d5df3c9661a054e12401546875f4685b5bf08
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6496
Tested-by: BuildkiteCI
Reviewed-by: tazjin <tazjin@tvl.su>
Reviewed-by: sterni <sternenseemann@systemli.org>

3 files changed, 62 insertions, 27 deletions

diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs
index 7cca7004ab..79754e4de0 100644
--- a/tvix/eval/src/compiler/mod.rs
+++ b/tvix/eval/src/compiler/mod.rs
@@ -755,29 +755,14 @@ impl Compiler<'_, '_> {
     fn compile_let_in(&mut self, slot: LocalIdx, node: ast::LetIn) {
         self.begin_scope();
 
-        // First pass to ensure that all identifiers are known;
-        // required for resolving recursion.
-        let mut entries: Vec<(LocalIdx, ast::Expr, Option<ast::Ident>)> = vec![];
-        for entry in node.attrpath_values() {
-            let mut path = match self.normalise_ident_path(entry.attrpath().unwrap().attrs()) {
-                Ok(p) => p,
-                Err(err) => {
-                    self.errors.push(err);
-                    continue;
-                }
-            };
-
-            if path.len() != 1 {
-                todo!("nested bindings in let expressions :(")
-            }
-
-            let idx = self.declare_local(&entry.attrpath().unwrap(), path.pop().unwrap());
-
-            entries.push((idx, entry.value().unwrap(), None));
-        }
-
-        // We also need to do such a pass for all inherits, we can even populate
-        // plain inherits directly, since they can't be (self) recursive.
+        // First pass to find all plain inherits (if they are not useless).
+        // Since they always resolve to a higher scope, we can just compile and
+        // declare them immediately. This needs to happen *before* we declare
+        // any other locals in the scope or the stack order gets messed up.
+        // While we are looping through the inherits, already note all inherit
+        // (from) expressions, that may very well resolve recursively and need
+        // to be compiled like normal let in bindings.
+        let mut inherit_froms: Vec<(ast::Expr, ast::Ident)> = vec![];
         for inherit in node.inherits() {
             match inherit.from() {
                 // Within a `let` binding, inheriting from the outer
@@ -810,14 +795,43 @@ impl Compiler<'_, '_> {
 
                 Some(from) => {
                     for ident in inherit.idents() {
-                        let idx = self.declare_local(&ident, ident.ident_token().unwrap().text());
-                        entries.push((idx, from.expr().unwrap(), Some(ident)))
+                        inherit_froms.push((from.expr().unwrap(), ident));
                     }
                 }
             }
         }
+        // Second pass to ensure that all remaining identifiers (that may
+        // resolve recursively) are known.
+        // Track locals as an index, the expression of its values and optionally
+        // the ident of an attribute to select from it.
+        let mut entries: Vec<(LocalIdx, ast::Expr, Option<ast::Ident>)> = vec![];
+
+        // Begin with the inherit (from)s since they all become a thunk anyway
+        for (from, ident) in inherit_froms {
+            let idx = self.declare_local(&ident, ident.ident_token().unwrap().text());
+            entries.push((idx, from, Some(ident)))
+        }
+
+        // Declare all regular bindings
+        for entry in node.attrpath_values() {
+            let mut path = match self.normalise_ident_path(entry.attrpath().unwrap().attrs()) {
+                Ok(p) => p,
+                Err(err) => {
+                    self.errors.push(err);
+                    continue;
+                }
+            };
+
+            if path.len() != 1 {
+                todo!("nested bindings in let expressions :(")
+            }
+
+            let idx = self.declare_local(&entry.attrpath().unwrap(), path.pop().unwrap());
+
+            entries.push((idx, entry.value().unwrap(), None));
+        }
 
-        // Second pass to place the values in the correct stack slots.
+        // Third pass to place the values in the correct stack slots.
         let mut indices: Vec<LocalIdx> = vec![];
         for (idx, value, path) in entries.into_iter() {
             indices.push(idx);
@@ -842,7 +856,7 @@ impl Compiler<'_, '_> {
             self.scope_mut().mark_initialised(idx);
         }
 
-        // Third pass to emit finaliser instructions if necessary.
+        // Fourth pass to emit finaliser instructions if necessary.
         for idx in indices {
             if self.scope()[idx].needs_finaliser {
                 let stack_idx = self.scope().stack_index(idx);
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-let-useful-plain-inherit-mixed.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-let-useful-plain-inherit-mixed.exp
new file mode 100644
index 0000000000..3bed31f76e
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-let-useful-plain-inherit-mixed.exp
@@ -0,0 +1 @@
+[ 1 2 3 4 ]
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-let-useful-plain-inherit-mixed.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-let-useful-plain-inherit-mixed.nix
new file mode 100644
index 0000000000..30981099cb
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-let-useful-plain-inherit-mixed.nix
@@ -0,0 +1,20 @@
+# This test mixes different ways of creating bindings in a let … in expression
+# to make sure that the compiler initialises the locals in the same order as
+# they are declared.
+
+let
+  d = 4;
+in
+
+# Trick to allow useless inherits in the following let
+with { _unused = null; };
+
+let
+  set = { b = 2; };
+  a = 1;
+  inherit (set) b;
+  c = 3;
+  inherit d;
+in
+
+[ a b c d ]