refactor(tvix/eval): decouple local depth & initialisation tracking r/4661

In order to resolve recursive references correctly, these two can not
be initialised the same way as a potentially large number of (nested!)
locals can be declared without initialising their depth.

This would lead to issues with detecting things like shadowed
variables, so making both bits explicit is preferable.

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

2 files changed, 33 insertions, 56 deletions

diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs
index 0d2ed66f5bf5..ca1098af64dd 100644
--- a/tvix/eval/src/compiler/mod.rs
+++ b/tvix/eval/src/compiler/mod.rs
@@ -29,7 +29,7 @@ use crate::opcode::{CodeIdx, Count, JumpOffset, OpCode, StackIdx, UpvalueIdx};
 use crate::value::{Closure, Lambda, Value};
 use crate::warnings::{EvalWarning, WarningKind};
 
-use self::scope::{Depth, Local, LocalPosition, Scope, Upvalue};
+use self::scope::{Local, LocalPosition, Scope, Upvalue};
 
 /// Represents the result of compiling a piece of Nix code. If
 /// compilation was successful, the resulting bytecode can be passed
@@ -752,7 +752,7 @@ impl Compiler {
             // Calculate the with_idx without taking into account
             // uninitialised variables that are not yet in their stack
             // slots.
-            .filter(|l| matches!(l.depth, Depth::At(_)))
+            .filter(|l| l.initialised)
             .count()
             - 1;
 
@@ -897,9 +897,7 @@ impl Compiler {
         // TL;DR - iterate from the back while things belonging to the
         // ended scope still exist.
         while !self.scope().locals.is_empty()
-            && self.scope().locals[self.scope().locals.len() - 1]
-                .depth
-                .above(self.scope().scope_depth)
+            && self.scope().locals[self.scope().locals.len() - 1].above(self.scope().scope_depth)
         {
             pops += 1;
 
@@ -944,13 +942,8 @@ impl Compiler {
         }
 
         let mut shadowed = false;
-        for local in self.scope().locals.iter().rev() {
-            if local.depth.below(self.scope().scope_depth) {
-                // Shadowing identifiers from higher scopes is allowed.
-                break;
-            }
-
-            if local.name == name {
+        for other in self.scope().locals.iter().rev() {
+            if other.name == name && other.depth == depth {
                 shadowed = true;
                 break;
             }
@@ -965,7 +958,8 @@ impl Compiler {
 
         self.scope_mut().locals.push(Local {
             name,
-            depth: Depth::Unitialised,
+            depth,
+            initialised: false,
             node: Some(node),
             phantom: false,
             used: false,
@@ -978,7 +972,8 @@ impl Compiler {
     fn declare_phantom(&mut self) {
         let depth = self.scope().scope_depth;
         self.scope_mut().locals.push(Local {
-            depth: Depth::At(depth),
+            depth,
+            initialised: true,
             name: "".into(),
             node: None,
             phantom: true,
@@ -990,8 +985,8 @@ impl Compiler {
     fn mark_initialised(&mut self, name: &str) {
         let depth = self.scope().scope_depth;
         for local in self.scope_mut().locals.iter_mut().rev() {
-            if matches!(local.depth, Depth::Unitialised) && local.name == name {
-                local.depth = Depth::At(depth);
+            if !local.initialised && local.depth == depth && local.name == name {
+                local.initialised = true;
                 return;
             }
         }
diff --git a/tvix/eval/src/compiler/scope.rs b/tvix/eval/src/compiler/scope.rs
index 3061e08ead25..a76a411b461b 100644
--- a/tvix/eval/src/compiler/scope.rs
+++ b/tvix/eval/src/compiler/scope.rs
@@ -16,34 +16,6 @@ use smol_str::SmolStr;
 
 use crate::opcode::{StackIdx, UpvalueIdx};
 
-/// Represents the initialisation status of a variable, tracking
-/// whether it is only known or also already defined.
-pub enum Depth {
-    /// Variable is defined and located at the given depth.
-    At(usize),
-
-    /// Variable is known but not yet defined.
-    Unitialised,
-}
-
-impl Depth {
-    /// Does this variable live above the other given depth?
-    pub fn above(&self, theirs: usize) -> bool {
-        match self {
-            Depth::Unitialised => false,
-            Depth::At(ours) => *ours > theirs,
-        }
-    }
-
-    /// Does this variable live below the other given depth?
-    pub fn below(&self, theirs: usize) -> bool {
-        match self {
-            Depth::Unitialised => false,
-            Depth::At(ours) => *ours < theirs,
-        }
-    }
-}
-
 /// Represents a single local already known to the compiler.
 pub struct Local {
     // Definition name, which can be different kinds of tokens (plain
@@ -55,7 +27,10 @@ pub struct Local {
     pub node: Option<rnix::SyntaxNode>,
 
     // Scope depth of this local.
-    pub depth: Depth,
+    pub depth: usize,
+
+    // Is this local initialised?
+    pub initialised: bool,
 
     // Phantom locals are not actually accessible by users (e.g.
     // intermediate values used for `with`).
@@ -65,6 +40,13 @@ pub struct Local {
     pub used: bool,
 }
 
+impl Local {
+    /// Does this local live above the other given depth?
+    pub fn above(&self, theirs: usize) -> bool {
+        self.depth > theirs
+    }
+}
+
 /// Represents the current position of a local as resolved in a scope.
 pub enum LocalPosition {
     /// Local is not known in this scope.
@@ -175,17 +157,17 @@ impl Scope {
             if !local.phantom && local.name == name {
                 local.used = true;
 
-                match local.depth {
-                    // This local is still being initialised, meaning
-                    // that we know its final runtime stack position,
-                    // but it is not yet on the stack.
-                    Depth::Unitialised => return LocalPosition::Recursive(StackIdx(idx)),
-
-                    // This local is known, but we need to account for
-                    // uninitialised variables in this "initialiser
-                    // stack".
-                    Depth::At(_) => return LocalPosition::Known(self.resolve_uninit(idx)),
+                // This local is still being initialised, meaning that
+                // we know its final runtime stack position, but it is
+                // not yet on the stack.
+                if !local.initialised {
+                    return LocalPosition::Recursive(StackIdx(idx));
                 }
+
+                // This local is known, but we need to account for
+                // uninitialised variables in this "initialiser
+                // stack".
+                return LocalPosition::Known(self.resolve_uninit(idx));
             }
         }
 
@@ -200,7 +182,7 @@ impl Scope {
         StackIdx(
             self.locals[..locals_idx]
                 .iter()
-                .filter(|local| matches!(local.depth, Depth::At(_)))
+                .filter(|local| local.initialised)
                 .count(),
         )
     }