feat(tvix/eval): add scaffolding for merging nested attribute sets r/4995

This sets up the required logic for finding and merging attribute sets
into nested bindings if they exist. This is absolutely not complete
yet and can, at this commit, probably cause undefined runtime
behaviour if nested attributes are specified.

The basic idea is that a new helper function on the `TrackedBindings`
struct is called with each encountered attribute and determines
whether the new entry can be merged into an existing attribute or not.

Right now the only effect this has in practice is that a new error
becomes available if somebody attempts to cause a merge into an
inherited key.

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

2 files changed, 116 insertions, 25 deletions

diff --git a/tvix/eval/src/compiler/bindings.rs b/tvix/eval/src/compiler/bindings.rs
index 7d6b305693..5fa08210fd 100644
--- a/tvix/eval/src/compiler/bindings.rs
+++ b/tvix/eval/src/compiler/bindings.rs
@@ -4,8 +4,29 @@
 //! In the case of recursive scopes these cases share almost all of their
 //! (fairly complex) logic.
 
+use rnix::ast::AttrpathValue;
+
 use super::*;
 
+/// What kind of bindings scope is being compiled?
+#[derive(Clone, Copy, PartialEq)]
+enum BindingsKind {
+    /// Standard `let ... in ...`-expression.
+    LetIn,
+
+    /// Non-recursive attribute set.
+    Attrs,
+
+    /// Recursive attribute set.
+    RecAttrs,
+}
+
+impl BindingsKind {
+    fn is_attrs(&self) -> bool {
+        matches!(self, BindingsKind::Attrs | BindingsKind::RecAttrs)
+    }
+}
+
 // Data structures to track the bindings observed in the second pass, and
 // forward the information needed to compile their value.
 enum Binding {
@@ -20,6 +41,18 @@ enum Binding {
     },
 }
 
+impl Binding {
+    fn merge(&mut self, _expr: ast::Expr) -> Option<ErrorKind> {
+        match self {
+            Binding::InheritFrom { name, .. } => {
+                Some(ErrorKind::UnmergeableInherit { name: name.clone() })
+            }
+
+            Binding::Plain { .. } => todo!(),
+        }
+    }
+}
+
 enum KeySlot {
     /// There is no key slot (`let`-expressions do not emit their key).
     None { name: SmolStr },
@@ -38,6 +71,19 @@ struct TrackedBinding {
     binding: Binding,
 }
 
+impl TrackedBinding {
+    /// Does this binding match the given key?
+    ///
+    /// Used to determine which binding to merge another one into.
+    fn matches(&self, key: &str) -> bool {
+        match &self.key_slot {
+            KeySlot::None { name } => name == key,
+            KeySlot::Static { name, .. } => name == key,
+            KeySlot::Dynamic { .. } => false,
+        }
+    }
+}
+
 struct TrackedBindings {
     kind: BindingsKind,
     bindings: Vec<TrackedBinding>,
@@ -51,6 +97,46 @@ impl TrackedBindings {
         }
     }
 
+    /// Attempt to merge an entry into an existing matching binding, assuming
+    /// that the provided binding is mergable (i.e. either a nested key or an
+    /// attribute set literal).
+    ///
+    /// Returns true if the binding was merged, false if it needs to be compiled
+    /// separately as a new binding.
+    fn try_merge(&mut self, c: &mut Compiler, entry: &AttrpathValue) -> bool {
+        let path = entry.attrpath().unwrap().attrs().collect::<Vec<_>>();
+        let value = entry.value().unwrap();
+
+        // If the path only has one element, and if the entry is not an attribute
+        // set literal, the entry can not be merged.
+        if path.len() == 1 && !matches!(value, ast::Expr::AttrSet(_)) {
+            return false;
+        }
+
+        // If the first element of the path is not statically known, the entry
+        // can not be merged.
+        let name = match c.expr_static_attr_str(&path[0]) {
+            Some(name) => name,
+            None => return false,
+        };
+
+        // If there is no existing binding with this key, the entry can not be
+        // merged.
+        // TODO: benchmark whether using a map or something is useful over the
+        // `find` here
+        let binding = match self.bindings.iter_mut().find(|b| b.matches(&name)) {
+            Some(b) => b,
+            None => return false,
+        };
+
+        // No more excuses ... the binding can be merged!
+        if let Some(err) = binding.binding.merge(value) {
+            c.emit_error(entry, err);
+        }
+
+        true
+    }
+
     /// Add a completely new binding to the tracked bindings.
     fn track_new(&mut self, key_slot: KeySlot, value_slot: LocalIdx, binding: Binding) {
         self.bindings.push(TrackedBinding {
@@ -61,25 +147,6 @@ impl TrackedBindings {
     }
 }
 
-/// What kind of bindings scope is being compiled?
-#[derive(Clone, Copy, PartialEq)]
-enum BindingsKind {
-    /// Standard `let ... in ...`-expression.
-    LetIn,
-
-    /// Non-recursive attribute set.
-    Attrs,
-
-    /// Recursive attribute set.
-    RecAttrs,
-}
-
-impl BindingsKind {
-    fn is_attrs(&self) -> bool {
-        matches!(self, BindingsKind::Attrs | BindingsKind::RecAttrs)
-    }
-}
-
 /// AST-traversing functions related to bindings.
 impl Compiler<'_> {
     /// Compile all inherits of a node with entries that do *not* have a
@@ -242,16 +309,25 @@ impl Compiler<'_> {
         N: ToSpan + ast::HasEntry,
     {
         for entry in node.attrpath_values() {
+            if bindings.try_merge(self, &entry) {
+                // Binding is nested, or already exists and was merged, move on.
+                continue;
+            }
+
             *count += 1;
 
-            let mut path = entry.attrpath().unwrap().attrs().collect::<Vec<_>>();
-            if path.len() != 1 {
+            let (key, mut path) = {
+                let mut path = entry.attrpath().unwrap().attrs();
+                (path.next().unwrap(), path.peekable())
+            };
+
+            if path.peek().is_some() {
                 self.emit_error(&entry, ErrorKind::NotImplemented("nested bindings :("));
                 continue;
             }
 
-            let key_span = self.span_for(&path[0]);
-            let key_slot = match self.expr_static_attr_str(&path[0]) {
+            let key_span = self.span_for(&key);
+            let key_slot = match self.expr_static_attr_str(&key) {
                 Some(name) if kind.is_attrs() => KeySlot::Static {
                     name,
                     slot: self.scope_mut().declare_phantom(key_span, false),
@@ -260,12 +336,12 @@ impl Compiler<'_> {
                 Some(name) => KeySlot::None { name },
 
                 None if kind.is_attrs() => KeySlot::Dynamic {
-                    attr: path.pop().unwrap(),
+                    attr: key,
                     slot: self.scope_mut().declare_phantom(key_span, false),
                 },
 
                 None => {
-                    self.emit_error(&path[0], ErrorKind::DynamicKeyInScope("let-expression"));
+                    self.emit_error(&key, ErrorKind::DynamicKeyInScope("let-expression"));
                     continue;
                 }
             };
diff --git a/tvix/eval/src/errors.rs b/tvix/eval/src/errors.rs
index 822ebdbc8c..92ca59f105 100644
--- a/tvix/eval/src/errors.rs
+++ b/tvix/eval/src/errors.rs
@@ -4,6 +4,7 @@ use std::{fmt::Display, num::ParseIntError};
 
 use codemap::{CodeMap, Span};
 use codemap_diagnostic::{Diagnostic, Emitter, Level, SpanLabel, SpanStyle};
+use smol_str::SmolStr;
 
 use crate::Value;
 
@@ -88,6 +89,12 @@ pub enum ErrorKind {
         length: i64,
     },
 
+    // Errors specific to nested attribute sets and merges thereof.
+    /// Nested attributes can not be merged with an inherited value.
+    UnmergeableInherit {
+        name: SmolStr,
+    },
+
     /// Tvix internal warning for features triggered by users that are
     /// not actually implemented yet, and without which eval can not
     /// proceed.
@@ -242,6 +249,13 @@ to a missing value in the attribute set(s) included via `with`."#,
                 )
             }
 
+            ErrorKind::UnmergeableInherit { name } => {
+                format!(
+                    "cannot merge a nested attribute set into the inherited entry '{}'",
+                    name
+                )
+            }
+
             ErrorKind::NotImplemented(feature) => {
                 format!("feature not yet implemented in Tvix: {}", feature)
             }
@@ -275,6 +289,7 @@ to a missing value in the attribute set(s) included via `with`."#,
             ErrorKind::ParseIntError(_) => "E021",
             ErrorKind::NegativeLength { .. } => "E022",
             ErrorKind::TailEmptyList { .. } => "E023",
+            ErrorKind::UnmergeableInherit { .. } => "E024",
             ErrorKind::NotImplemented(_) => "E999",
         }
     }