From da1e3e9ac586747cf8d65a257f330706b051d06e Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Thu, 29 Sep 2022 20:34:23 +0300 Subject: feat(tvix/eval): implement nested keys This finishes up the implementation of nested keys after the key insight that the nesting level does not need to be tracked, and instead the attribute iterator can simply be retained inside the structures as is (in an advanced state). With this implementation, when encountering a nested key, the Tvix compiler will first analyse whether there is already a matching binding that can be merged (i.e. a binding that is a literal attribute set), and perform the merge, or otherwise create a new recursive set of bindings in which the entry is inserted with the path iterator advanced beyond the first name component. With this, all the logic simply applies recursively until there are no more nested bindings (i.e. until all iterators are "empty"). Note that this has one (potentially insignificant) deviation from Nix currently: If a non-mergable value is supplied (e.g. `a.b = 1; a = 2;`), Tvix will emit a *runtime* error (whereas it is *parse* time in Nix) as the branch which could statically analyse this is currently unreachable. There's a TODO for this, so we can fix it up later. Change-Id: I53df70e09614ff4281a70b80eac7da3beca12da9 Reviewed-on: https://cl.tvl.fyi/c/depot/+/6806 Reviewed-by: sterni Tested-by: BuildkiteCI --- tvix/eval/src/compiler/bindings.rs | 89 +++++++++++++++++++++++++------------- 1 file changed, 60 insertions(+), 29 deletions(-) (limited to 'tvix/eval/src') diff --git a/tvix/eval/src/compiler/bindings.rs b/tvix/eval/src/compiler/bindings.rs index 7bbf41b205e9..f023e67b5d3e 100644 --- a/tvix/eval/src/compiler/bindings.rs +++ b/tvix/eval/src/compiler/bindings.rs @@ -4,11 +4,15 @@ //! In the case of recursive scopes these cases share almost all of their //! (fairly complex) logic. +use std::iter::Peekable; + use rnix::ast::HasEntry; use rowan::ast::AstChildren; use super::*; +type PeekableAttrs = Peekable>; + /// What kind of bindings scope is being compiled? #[derive(Clone, Copy, PartialEq)] enum BindingsKind { @@ -42,7 +46,7 @@ struct AttributeSet { inherits: Vec, /// All internal entries - entries: Vec<(Span, AstChildren, ast::Expr)>, + entries: Vec<(Span, PeekableAttrs, ast::Expr)>, } impl ToSpan for AttributeSet { @@ -72,7 +76,7 @@ impl AttributeSet { let span = c.span_for(&entry); ( span, - entry.attrpath().unwrap().attrs(), + entry.attrpath().unwrap().attrs().peekable(), entry.value().unwrap(), ) }) @@ -98,7 +102,15 @@ enum Binding { } impl Binding { - fn merge(&mut self, c: &mut Compiler, value: ast::Expr) { + /// Merge the provided value into the current binding, or emit an + /// error if this turns out to be impossible. + fn merge( + &mut self, + c: &mut Compiler, + span: Span, + mut remaining_path: PeekableAttrs, + value: ast::Expr, + ) { match self { Binding::InheritFrom { name, ref span, .. } => { c.emit_error(span, ErrorKind::UnmergeableInherit { name: name.clone() }) @@ -110,12 +122,19 @@ impl Binding { ast::Expr::AttrSet(existing) => { let nested = AttributeSet::from_ast(c, existing); *self = Binding::Set(nested); - self.merge(c, value); + self.merge(c, span, remaining_path, value); } _ => c.emit_error(&value, ErrorKind::UnmergeableValue), }, + // If the value is nested further, it is simply inserted into the + // bindings with its full path and resolved recursively further + // down. + Binding::Set(existing) if remaining_path.peek().is_some() => { + existing.entries.push((span, remaining_path, value)) + } + Binding::Set(existing) => { if let ast::Expr::AttrSet(new) = value { existing.inherits.extend(ast::HasEntry::inherits(&new)); @@ -125,12 +144,20 @@ impl Binding { let span = c.span_for(&entry); ( span, - entry.attrpath().unwrap().attrs(), + entry.attrpath().unwrap().attrs().peekable(), entry.value().unwrap(), ) })); } else { - todo!() + // This branch is unreachable because in cases where the + // path is empty (i.e. there is no further nesting), the + // previous try_merge function already verified that the + // expression is an attribute set. + + // TODO(tazjin): Consider making this branch live by + // shuffling that check around and emitting a static error + // here instead of a runtime error. + unreachable!() } } } @@ -187,24 +214,23 @@ impl TrackedBindings { /// /// Returns true if the binding was merged, false if it needs to be compiled /// separately as a new binding. - fn try_merge>( + fn try_merge( &mut self, c: &mut Compiler, span: Span, - path: I, + name: &ast::Attr, + mut remaining_path: PeekableAttrs, value: ast::Expr, ) -> bool { - let path = path.collect::>(); - - // 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(_)) { + // If the path has no more entries, and if the entry is not an + // attribute set literal, the entry can not be merged. + if remaining_path.peek().is_none() && !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]) { + let name = match c.expr_static_attr_str(name) { Some(name) => name, None => return false, }; @@ -219,7 +245,7 @@ impl TrackedBindings { }; // No more excuses ... the binding can be merged! - binding.binding.merge(c, value); + binding.binding.merge(c, span, remaining_path, value); true } @@ -242,7 +268,7 @@ trait HasEntryProxy { fn attributes( &self, file: Arc, - ) -> Box, ast::Expr)>>; + ) -> Box>; } impl HasEntryProxy for N { @@ -253,11 +279,11 @@ impl HasEntryProxy for N { fn attributes( &self, file: Arc, - ) -> Box, ast::Expr)>> { + ) -> Box> { Box::new(ast::HasEntry::attrpath_values(self).map(move |entry| { ( entry.span_for(&file), - entry.attrpath().unwrap().attrs(), + entry.attrpath().unwrap().attrs().peekable(), entry.value().unwrap(), ) })) @@ -272,7 +298,7 @@ impl HasEntryProxy for AttributeSet { fn attributes( &self, _: Arc, - ) -> Box, ast::Expr)>> { + ) -> Box> { Box::new(self.entries.clone().into_iter()) } } @@ -439,21 +465,15 @@ impl Compiler<'_> { N: ToSpan + HasEntryProxy, { for (span, mut path, value) in node.attributes(self.file.clone()) { - if bindings.try_merge(self, span, path.clone(), value.clone()) { + let key = path.next().unwrap(); + + if bindings.try_merge(self, span, &key, path.clone(), value.clone()) { // Binding is nested, or already exists and was merged, move on. continue; } *count += 1; - let key = path.next().unwrap(); - let mut path = path.peekable(); - - if path.peek().is_some() { - self.emit_error(&span, ErrorKind::NotImplemented("nested bindings :(")); - continue; - } - 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 { @@ -494,7 +514,18 @@ impl Compiler<'_> { BindingsKind::Attrs => self.scope_mut().declare_phantom(key_span, false), }; - bindings.track_new(key_slot, value_slot, Binding::Plain { expr: value }); + let binding = if path.peek().is_some() { + Binding::Set(AttributeSet { + span, + kind: BindingsKind::Attrs, + inherits: vec![], + entries: vec![(span, path, value)], + }) + } else { + Binding::Plain { expr: value } + }; + + bindings.track_new(key_slot, value_slot, binding); } } -- cgit 1.4.1