snix_eval/compiler/

bindings.rs

//! This module implements compiler logic related to name/value binding
//! definitions (that is, attribute sets and let-expressions).
//!
//! 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 crate::spans::{EntireFile, OrEntireFile};

use super::{scope::ScopeGuard, *};

type PeekableAttrs = Peekable<AstChildren<ast::Attr>>;

/// 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)
    }
}

// Internal representation of an attribute set used for merging sets, or
// inserting nested keys.
#[derive(Clone)]
struct AttributeSet {
    /// Original span at which this set was first encountered.
    span: Span,

    /// Tracks the kind of set (rec or not).
    kind: BindingsKind,

    /// All inherited entries
    inherits: Vec<ast::Inherit>,

    /// All internal entries
    entries: Vec<AttributeEntry>,
}

#[derive(Clone)]
struct AttributeEntry {
    span: Span,
    lowered_from: Option<Span>,
    remaining_path: PeekableAttrs,
    expr: ast::Expr,
}

impl ToSpan for AttributeSet {
    fn span_for(&self, _: &codemap::File) -> Span {
        self.span
    }
}

impl AttributeSet {
    fn from_ast(c: &Compiler, node: &ast::AttrSet) -> Self {
        AttributeSet {
            span: c.span_for(node),

            // Kind of the attrs depends on the first time it is
            // encountered. We actually believe this to be a Nix
            // bug: https://github.com/NixOS/nix/issues/7111
            kind: if node.rec_token().is_some() {
                BindingsKind::RecAttrs
            } else {
                BindingsKind::Attrs
            },

            inherits: ast::HasEntry::inherits(node).collect(),

            entries: ast::HasEntry::attrpath_values(node)
                .map(|entry| AttributeEntry {
                    span: c.span_for(&entry),
                    lowered_from: None,
                    remaining_path: entry.attrpath().unwrap().attrs().peekable(),
                    expr: entry.value().unwrap(),
                })
                .collect(),
        }
    }
}

// Data structures to track the bindings observed in the second pass, and
// forward the information needed to compile their value.
enum Binding {
    InheritFrom {
        namespace: ast::Expr,
        name: SmolStr,
        span: Span,
    },

    Plain {
        expr: ast::Expr,
    },

    Set(AttributeSet),
}

impl Binding {
    /// 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, mut entry: AttributeEntry) {
        match self {
            Binding::InheritFrom { name, span, .. } => {
                c.emit_error(span, ErrorKind::UnmergeableInherit { name: name.clone() })
            }

            // If the value is not yet a nested binding, flip the representation
            // and recurse.
            Binding::Plain { expr } => match expr {
                ast::Expr::AttrSet(existing) => {
                    let nested = AttributeSet::from_ast(c, existing);
                    *self = Binding::Set(nested);
                    self.merge(c, entry);
                }

                _ => c.emit_error(&entry.expr, 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 entry.remaining_path.peek().is_some() => {
                existing.entries.push(entry)
            }

            Binding::Set(existing) => {
                if let ast::Expr::AttrSet(new) = entry.expr {
                    existing.inherits.extend(ast::HasEntry::inherits(&new));
                    existing
                        .entries
                        .extend(
                            ast::HasEntry::attrpath_values(&new).map(|entry| AttributeEntry {
                                span: c.span_for(&entry),
                                lowered_from: None,
                                remaining_path: entry.attrpath().unwrap().attrs().peekable(),
                                expr: entry.value().unwrap(),
                            }),
                        );
                } else {
                    // 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!()
                }
            }
        }
    }
}

enum KeySlot {
    /// There is no key slot (`let`-expressions do not emit their key).
    None { name: SmolStr },

    /// The key is statically known and has a slot.
    Static { slot: LocalIdx, name: SmolStr },

    /// The key is dynamic, i.e. only known at runtime, and must be compiled
    /// into its slot.
    Dynamic { slot: LocalIdx, attr: ast::Attr },
}

struct TrackedBinding {
    key_slot: KeySlot,
    value_slot: LocalIdx,
    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 {
    bindings: Vec<TrackedBinding>,
}

impl TrackedBindings {
    fn new() -> Self {
        TrackedBindings { bindings: vec![] }
    }

    /// 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 `Ok` if the binding was merged, `Err` if it needs to be compiled
    /// separately as a new binding.
    fn try_merge(
        &mut self,
        c: &mut Compiler,
        name: &ast::Attr,
        mut entry: AttributeEntry,
    ) -> Result<(), AttributeEntry> {
        // If the path has no more entries, and if the entry is not an
        // attribute set literal, the entry can not be merged.
        if entry.remaining_path.peek().is_none() && !matches!(&entry.expr, ast::Expr::AttrSet(_)) {
            return Err(entry);
        }

        // If the first element of the path is not statically known, the entry
        // can not be merged.
        let name_str = match expr_static_attr_str(name) {
            Some(name) => name,
            None => return Err(entry),
        };

        // 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_str)) {
            Some(b) => b,
            None => return Err(entry),
        };

        // To comply with Nix's unsafeGetAttrPos behaviour, lowered attrpath's
        // position should refer to the first segment of the path.
        //
        // example:
        //   foo.bar.baz = 1
        //
        // After consuming `foo`, `remaining_path` is `bar.baz`. Any attrset
        // generated from this attrpath should refer to position of `foo`.
        //
        // If we are recursively compiling an already-lowered attrpath,
        // preserver the first segment's span.
        if entry.lowered_from.is_none() && entry.remaining_path.peek().is_some() {
            entry.lowered_from = Some(c.span_for(name));
        }

        // No more excuses ... the binding can be merged!
        binding.binding.merge(c, entry);

        Ok(())
    }

    /// 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 {
            key_slot,
            value_slot,
            binding,
        });
    }
}

/// Wrapper around the `ast::HasEntry` trait as that trait can not be
/// implemented for custom types.
trait HasEntryProxy {
    fn inherits(&self) -> Box<dyn Iterator<Item = ast::Inherit>>;

    fn attributes<'a>(
        &self,
        file: &'a codemap::File,
    ) -> Box<dyn Iterator<Item = AttributeEntry> + 'a>;
}

impl<N: HasEntry> HasEntryProxy for N {
    fn inherits(&self) -> Box<dyn Iterator<Item = ast::Inherit>> {
        Box::new(ast::HasEntry::inherits(self))
    }

    fn attributes<'a>(
        &self,
        file: &'a codemap::File,
    ) -> Box<dyn Iterator<Item = AttributeEntry> + 'a> {
        Box::new(
            ast::HasEntry::attrpath_values(self).map(move |entry| AttributeEntry {
                span: entry.span_for(file),
                lowered_from: None,
                remaining_path: entry.attrpath().unwrap().attrs().peekable(),
                expr: entry.value().unwrap(),
            }),
        )
    }
}

impl HasEntryProxy for AttributeSet {
    fn inherits(&self) -> Box<dyn Iterator<Item = ast::Inherit>> {
        Box::new(self.inherits.clone().into_iter())
    }

    fn attributes<'a>(
        &self,
        _: &'a codemap::File,
    ) -> Box<dyn Iterator<Item = AttributeEntry> + 'a> {
        Box::new(self.entries.clone().into_iter())
    }
}

/// AST-traversing functions related to bindings.
impl Compiler<'_, '_> {
    /// Compile all inherits of a node with entries that do *not* have a
    /// namespace to inherit from, and return the remaining ones that do.
    fn compile_plain_inherits<N>(
        &mut self,
        slot: LocalIdx,
        kind: BindingsKind,
        count: &mut usize,
        node: &N,
    ) -> Vec<(ast::Expr, SmolStr, Span)>
    where
        N: ToSpan + HasEntryProxy,
    {
        // Pass over all inherits, resolving only those without namespaces.
        // Since they always resolve in a higher scope, we can just compile and
        // declare them immediately.
        //
        // Inherits with namespaces are returned to the caller.
        let mut inherit_froms: Vec<(ast::Expr, SmolStr, Span)> = vec![];

        for inherit in node.inherits() {
            if inherit.attrs().peekable().peek().is_none() {
                self.emit_warning(&inherit, WarningKind::EmptyInherit);
                continue;
            }

            match inherit.from() {
                // Within a `let` binding, inheriting from the outer scope is a
                // no-op *if* there are no dynamic bindings.
                None if !kind.is_attrs() && !self.has_dynamic_ancestor() => {
                    self.emit_warning(&inherit, WarningKind::UselessInherit);
                    continue;
                }

                None => {
                    for attr in inherit.attrs() {
                        let name = match expr_static_attr_str(&attr) {
                            Some(name) => name,
                            None => {
                                self.emit_error(&attr, ErrorKind::DynamicKeyInScope("inherit"));
                                continue;
                            }
                        };

                        // If the identifier resolves statically in a `let`, it
                        // has precedence over dynamic bindings, and the inherit
                        // is useless.
                        if kind == BindingsKind::LetIn
                            && matches!(
                                self.scope_mut().resolve_local(&name),
                                LocalPosition::Known(_)
                            )
                        {
                            self.emit_warning(&attr, WarningKind::UselessInherit);
                            continue;
                        }

                        *count += 1;

                        // Place key on the stack when compiling attribute sets.
                        if kind.is_attrs() {
                            self.emit_constant(name.as_str().into(), &attr);
                            let span = self.span_for(&attr);
                            self.scope_mut().declare_phantom(span, true);
                        }

                        // Place the value on the stack. Note that because plain
                        // inherits are always in the outer scope, the slot of
                        // *this* scope itself is used.
                        self.compile_identifier_access(slot, &name, &attr);

                        // In non-recursive attribute sets, the key slot must be
                        // a phantom (i.e. the identifier can not be resolved in
                        // this scope).
                        let idx = if kind == BindingsKind::Attrs {
                            let span = self.span_for(&attr);
                            self.scope_mut().declare_phantom(span, false)
                        } else {
                            self.declare_local(&attr, name)
                        };

                        self.scope_mut().mark_initialised(idx);
                    }
                }

                Some(from) => {
                    for attr in inherit.attrs() {
                        let name = match expr_static_attr_str(&attr) {
                            Some(name) => name,
                            None => {
                                self.emit_error(&attr, ErrorKind::DynamicKeyInScope("inherit"));
                                continue;
                            }
                        };

                        *count += 1;
                        inherit_froms.push((from.expr().unwrap(), name, self.span_for(&attr)));
                    }
                }
            }
        }

        inherit_froms
    }

    /// Declare all namespaced inherits, that is inherits which are inheriting
    /// values from an attribute set.
    ///
    /// This only ensures that the locals stack is aware of the inherits, it
    /// does not yet emit bytecode that places them on the stack. This is up to
    /// the owner of the `bindings` vector, which this function will populate.
    fn declare_namespaced_inherits(
        &mut self,
        kind: BindingsKind,
        inherit_froms: Vec<(ast::Expr, SmolStr, Span)>,
        bindings: &mut TrackedBindings,
    ) {
        for (from, name, span) in inherit_froms {
            let key_slot = if kind.is_attrs() {
                // In an attribute set, the keys themselves are placed on the
                // stack but their stack slot is inaccessible (it is only
                // consumed by `OpAttrs`).
                KeySlot::Static {
                    slot: self.scope_mut().declare_phantom(span, false),
                    name: name.clone(),
                }
            } else {
                KeySlot::None { name: name.clone() }
            };

            let value_slot = match kind {
                // In recursive scopes, the value needs to be accessible on the
                // stack.
                BindingsKind::LetIn | BindingsKind::RecAttrs => {
                    self.declare_local(&span, name.clone())
                }

                // In non-recursive attribute sets, the value is inaccessible
                // (only consumed by `OpAttrs`).
                BindingsKind::Attrs => self.scope_mut().declare_phantom(span, false),
            };

            bindings.track_new(
                key_slot,
                value_slot,
                Binding::InheritFrom {
                    namespace: from,
                    name,
                    span,
                },
            );
        }
    }

    /// Declare all regular bindings (i.e. `key = value;`) in a bindings scope,
    /// but do not yet compile their values.
    fn declare_bindings<N>(
        &mut self,
        kind: BindingsKind,
        count: &mut usize,
        bindings: &mut TrackedBindings,
        node: &N,
    ) where
        N: ToSpan + HasEntryProxy,
    {
        for mut entry in node.attributes(self.file) {
            let key = entry.remaining_path.next().unwrap();

            let mut entry = match bindings.try_merge(self, &key, entry) {
                // Binding is nested, or already exists and was merged, move on.
                Ok(()) => continue,
                Err(entry) => entry,
            };

            *count += 1;

            let key_span = self.span_for(&key);

            let pos_span = entry.lowered_from.unwrap_or(key_span);
            self.push_attrset_pos(pos_span);

            let key_slot = match expr_static_attr_str(&key) {
                Some(name) if kind.is_attrs() => KeySlot::Static {
                    name,
                    slot: self.scope_mut().declare_phantom(key_span, false),
                },

                Some(name) => KeySlot::None { name },

                None if kind.is_attrs() => KeySlot::Dynamic {
                    attr: key,
                    slot: self.scope_mut().declare_phantom(key_span, false),
                },

                None => {
                    self.emit_error(&key, ErrorKind::DynamicKeyInScope("let-expression"));
                    continue;
                }
            };

            let value_slot = match kind {
                BindingsKind::LetIn | BindingsKind::RecAttrs => match &key_slot {
                    // In recursive scopes, the value needs to be accessible on the
                    // stack if it is statically known
                    KeySlot::None { name } | KeySlot::Static { name, .. } => {
                        self.declare_local(&key_span, name.as_str())
                    }

                    // Dynamic values are never resolvable (as their names are
                    // of course only known at runtime).
                    //
                    // Note: This branch is unreachable in `let`-expressions.
                    KeySlot::Dynamic { .. } => self.scope_mut().declare_phantom(key_span, false),
                },

                // In non-recursive attribute sets, the value is inaccessible
                // (only consumed by `OpAttrs`).
                BindingsKind::Attrs => self.scope_mut().declare_phantom(key_span, false),
            };

            let binding = if entry.remaining_path.peek().is_some() {
                let span = entry.span;
                entry.lowered_from = Some(pos_span);

                Binding::Set(AttributeSet {
                    span,
                    kind: BindingsKind::Attrs,
                    inherits: vec![],
                    entries: vec![entry],
                })
            } else {
                Binding::Plain { expr: entry.expr }
            };

            bindings.track_new(key_slot, value_slot, binding);
        }
    }

    /// Compile attribute set literals into equivalent bytecode.
    ///
    /// This is complicated by a number of features specific to Nix attribute
    /// sets, most importantly:
    ///
    /// 1. Keys can be dynamically constructed through interpolation.
    /// 2. Keys can refer to nested attribute sets.
    /// 3. Attribute sets can (optionally) be recursive.
    pub(super) fn compile_attr_set(&mut self, slot: LocalIdx, node: &ast::AttrSet) {
        let kind = if node.rec_token().is_some() {
            BindingsKind::RecAttrs
        } else {
            BindingsKind::Attrs
        };

        let guard = self.compile_bindings(slot, kind, node);
        self.scope_mut().end_scope(guard);
    }

    /// Emit definitions for all variables in the top-level global env passed to the evaluation (eg
    /// local variables in the REPL)
    pub(super) fn compile_env(&mut self, env: &FxHashMap<SmolStr, Value>) {
        for (name, value) in env {
            self.scope_mut().declare_constant(name.to_string());
            self.emit_constant(value.clone(), &EntireFile);
        }
    }

    /// Actually binds all tracked bindings by emitting the bytecode that places
    /// them in their stack slots.
    fn bind_values(&mut self, bindings: TrackedBindings) {
        let mut value_indices: Vec<LocalIdx> = vec![];

        for binding in bindings.bindings.into_iter() {
            value_indices.push(binding.value_slot);

            match binding.key_slot {
                KeySlot::None { .. } => {} // nothing to do here

                KeySlot::Static { slot, name } => {
                    let span = self.scope()[slot].span;
                    self.emit_constant(name.as_str().into(), &OrEntireFile(span));
                    self.scope_mut().mark_initialised(slot);
                }

                KeySlot::Dynamic { slot, attr } => {
                    self.compile_attr(slot, &attr);
                    self.scope_mut().mark_initialised(slot);
                }
            }

            match binding.binding {
                // This entry is an inherit (from) expr. The value is placed on
                // the stack by selecting an attribute.
                Binding::InheritFrom {
                    namespace,
                    name,
                    span,
                } => {
                    // Create a thunk wrapping value (which may be one as well)
                    // to avoid forcing the from expr too early.
                    self.thunk(binding.value_slot, &namespace, |c, s| {
                        c.compile(s, namespace.clone());
                        c.emit_force(&namespace);

                        c.emit_constant(name.as_str().into(), &span);
                        c.push_op(Op::AttrsSelect, &span);
                    })
                }

                // Binding is "just" a plain expression that needs to be
                // compiled.
                Binding::Plain { expr } => self.compile(binding.value_slot, expr),

                // Binding is a merged or nested attribute set, and needs to be
                // recursively compiled as another binding.
                Binding::Set(set) => self.thunk(binding.value_slot, &set, |c, _| {
                    let g = c.compile_bindings(binding.value_slot, set.kind, &set);
                    c.scope_mut().end_scope(g);
                }),
            }

            // Any code after this point will observe the value in the right
            // stack slot, so mark it as initialised.
            self.scope_mut().mark_initialised(binding.value_slot);
        }

        // Final pass to emit finaliser instructions if necessary.
        for idx in value_indices {
            if self.scope()[idx].needs_finaliser {
                let stack_idx = self.scope().stack_index(idx);
                let span = self.scope()[idx].span;
                self.push_op(Op::Finalise, &OrEntireFile(span));
                self.push_uvarint(stack_idx.0 as u64)
            }
        }
    }

    fn compile_bindings<N>(&mut self, slot: LocalIdx, kind: BindingsKind, node: &N) -> ScopeGuard
    where
        N: ToSpan + HasEntryProxy,
    {
        let mut count = 0;
        let scope_guard = self.scope_mut().begin_scope("compile_bindings");

        // Vector to track all observed bindings.
        let mut bindings = TrackedBindings::new();

        let inherit_froms = self.compile_plain_inherits(slot, kind, &mut count, node);
        self.declare_namespaced_inherits(kind, inherit_froms, &mut bindings);
        self.declare_bindings(kind, &mut count, &mut bindings, node);

        // Check if we can bail out on empty bindings
        if count == 0 {
            // still need an attrset to exist, but it is empty.
            if kind.is_attrs() {
                self.emit_constant(Value::Attrs(NixAttrs::empty()), node);
                return scope_guard;
            }

            self.emit_warning(node, WarningKind::EmptyLet);
            return scope_guard;
        }

        // Actually bind values and ensure they are on the stack.
        self.bind_values(bindings);

        if kind.is_attrs() {
            self.push_op(Op::Attrs, node);
            self.push_uvarint(count as u64);
        }

        scope_guard
    }

    /// Compile a standard `let ...; in ...` expression.
    ///
    /// Unless in a non-standard scope, the encountered values are simply pushed
    /// on the stack and their indices noted in the entries vector.
    pub(super) fn compile_let_in(&mut self, slot: LocalIdx, node: &ast::LetIn) {
        let guard = self.compile_bindings(slot, BindingsKind::LetIn, node);

        // Deal with the body, then clean up the locals afterwards.
        self.compile(slot, node.body().unwrap());
        self.cleanup_scope(node, guard);
    }

    pub(super) fn compile_legacy_let(&mut self, slot: LocalIdx, node: &ast::LegacyLet) {
        self.emit_warning(node, WarningKind::DeprecatedLegacyLet);
        let g = self.compile_bindings(slot, BindingsKind::RecAttrs, node);

        // Remove the scope, but do not emit any additional cleanup
        // (OpAttrs consumes all of these locals).
        self.scope_mut().end_scope(g);

        self.emit_constant("body".into(), node);
        self.push_op(Op::AttrsSelect, node);
    }

    /// Is the given identifier defined *by the user* in any current scope?
    pub(super) fn is_user_defined(&mut self, ident: &str) -> bool {
        matches!(
            self.scope_mut().resolve_local(ident),
            LocalPosition::Known(_) | LocalPosition::Recursive(_)
        )
    }

    /// Resolve and compile access to an identifier in the scope.
    fn compile_identifier_access<N: ToSpan + Clone>(
        &mut self,
        slot: LocalIdx,
        ident: &str,
        node: &N,
    ) {
        match self.scope_mut().resolve_local(ident) {
            LocalPosition::Unknown => {
                // Are we possibly dealing with an upvalue?
                if let Some(idx) = self.resolve_upvalue_for_use(self.contexts.len() - 1, ident) {
                    self.push_op(Op::GetUpvalue, node);
                    self.push_uvarint(idx.0 as u64);
                    return;
                }

                // Globals are the "upmost upvalues": they behave
                // exactly like a `let ... in` prepended to the
                // program's text, and the global scope is nothing
                // more than the parent scope of the root scope.
                if let Some(global) = self.globals.get(ident) {
                    self.emit_constant(global.clone(), &self.span_for(node));
                    return;
                }

                // If there is a non-empty `with`-stack (or a parent context
                // with one), emit a runtime dynamic resolution instruction.
                //
                // Since it is possible for users to e.g. assign a variable to a
                // dynamic resolution without actually using it, this operation
                // is wrapped in an extra thunk.
                if self.has_dynamic_ancestor() {
                    self.thunk(slot, node, |c, _| {
                        c.context_mut().captures_with_stack = true;
                        c.emit_constant(ident.into(), node);
                        c.push_op(Op::ResolveWith, node);
                    });
                    return;
                }

                // Otherwise, this variable is missing.
                self.emit_error(node, ErrorKind::UnknownStaticVariable);
            }

            LocalPosition::Known(idx) => {
                self.scope_mut().mark_used(idx);

                let stack_idx = self.scope().stack_index(idx);
                self.push_op(Op::GetLocal, node);
                self.push_uvarint(stack_idx.0 as u64);
            }

            // This identifier is referring to a value from the same scope which
            // is not yet defined. This identifier access must be thunked.
            LocalPosition::Recursive(idx) => {
                self.scope_mut().mark_used(idx);
                self.thunk(slot, node, move |compiler, _| {
                    let upvalue_idx =
                        compiler.add_upvalue(compiler.contexts.len() - 1, UpvalueKind::Local(idx));
                    compiler.push_op(Op::GetUpvalue, node);
                    compiler.push_uvarint(upvalue_idx.0 as u64);
                })
            }
        };
    }

    pub(super) fn compile_ident(&mut self, slot: LocalIdx, node: &ast::Ident) {
        let ident = node.ident_token().unwrap();
        self.compile_identifier_access(slot, ident.text(), node);
    }
}

/// Private compiler helpers related to bindings.
impl Compiler<'_, '_> {
    // ATTN: Also marks local backing the upvalue as used if any
    fn resolve_upvalue_for_use(&mut self, ctx_idx: usize, name: &str) -> Option<UpvalueIdx> {
        if ctx_idx == 0 {
            // There can not be any upvalue at the outermost context.
            return None;
        }

        // Determine whether the upvalue is a local in the enclosing context.
        match self.contexts[ctx_idx - 1].scope.resolve_local(name) {
            // recursive upvalues are dealt with the same way as standard known
            // ones, as thunks and closures are guaranteed to be placed on the
            // stack (i.e. in the right position) *during* their runtime
            // construction
            LocalPosition::Known(idx) | LocalPosition::Recursive(idx) => {
                self.contexts[ctx_idx - 1].scope.mark_used(idx);
                return Some(self.add_upvalue(ctx_idx, UpvalueKind::Local(idx)));
            }

            LocalPosition::Unknown => { /* continue below */ }
        };

        // If the upvalue comes from even further up, we need to recurse to make
        // sure that the upvalues are created at each level.
        if let Some(idx) = self.resolve_upvalue_for_use(ctx_idx - 1, name) {
            return Some(self.add_upvalue(ctx_idx, UpvalueKind::Upvalue(idx)));
        }

        None
    }

    fn add_upvalue(&mut self, ctx_idx: usize, kind: UpvalueKind) -> UpvalueIdx {
        // If there is already an upvalue closing over the specified index,
        // retrieve that instead.
        for (idx, existing) in self.contexts[ctx_idx].scope.upvalues.iter().enumerate() {
            if existing.kind == kind {
                return UpvalueIdx(idx);
            }
        }

        self.contexts[ctx_idx].scope.upvalues.push(Upvalue { kind });

        let idx = UpvalueIdx(self.contexts[ctx_idx].lambda.upvalue_count);
        self.contexts[ctx_idx].lambda.upvalue_count += 1;
        idx
    }
}