//! This module implements the scope-tracking logic of the Tvix //! compiler. //! //! Scoping in Nix is fairly complicated, there are features like //! mutually recursive bindings, `with`, upvalue capturing, and so //! on that introduce a fair bit of complexity. //! //! Tvix attempts to do as much of the heavy lifting of this at //! compile time, and leave the runtime to mostly deal with known //! stack indices. To do this, the compiler simulates where locals //! will be at runtime using the data structures implemented here. use rustc_hash::FxHashMap; use std::{collections::hash_map, ops::Index}; use smol_str::SmolStr; use crate::opcode::{StackIdx, UpvalueIdx}; #[derive(Debug)] enum LocalName { /// Normally declared local with a statically known name. Ident(String), /// Phantom stack value (e.g. attribute set used for `with`) that /// must be accounted for to calculate correct stack offsets. Phantom, } /// Represents a single local already known to the compiler. #[derive(Debug)] pub struct Local { /// Identifier of this local. This is always a statically known /// value (Nix does not allow dynamic identifier names in locals), /// or a "phantom" value not accessible by users. name: LocalName, /// Source span at which this local was declared. pub span: Option, /// Scope depth of this local. pub depth: usize, /// Is this local initialised? pub initialised: bool, /// Is this local known to have been used at all? pub used: bool, /// Does this local need to be finalised after the enclosing scope /// is completely constructed? pub needs_finaliser: bool, /// Does this local's upvalues contain a reference to itself? pub must_thunk: bool, } impl Local { /// Retrieve the name of the given local (if available). pub fn name(&self) -> Option { match &self.name { LocalName::Phantom => None, LocalName::Ident(name) => Some(SmolStr::new(name)), } } /// Is this local intentionally ignored? (i.e. name starts with `_`) pub fn is_ignored(&self) -> bool { match &self.name { LocalName::Ident(name) => name.starts_with('_'), LocalName::Phantom => false, } } pub fn is_used(&self) -> bool { self.depth == 0 || self.used || self.is_ignored() } } /// Represents the current position of an identifier as resolved in a scope. pub enum LocalPosition { /// Local is not known in this scope. Unknown, /// Local is known at the given local index. Known(LocalIdx), /// Local is known, but is being accessed recursively within its /// own initialisation. Depending on context, this is either an /// error or forcing a closure/thunk. Recursive(LocalIdx), } /// Represents the different ways in which upvalues can be captured in /// closures or thunks. #[derive(Clone, Debug, PartialEq, Eq)] pub enum UpvalueKind { /// This upvalue captures a local from the stack. Local(LocalIdx), /// This upvalue captures an enclosing upvalue. Upvalue(UpvalueIdx), } #[derive(Clone, Debug)] pub struct Upvalue { pub kind: UpvalueKind, pub span: codemap::Span, } /// The index of a local in the scope's local array at compile time. #[repr(transparent)] #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd)] pub struct LocalIdx(usize); /// Helper struct for indexing over `Scope::locals` by name. #[derive(Debug)] enum ByName { Single(LocalIdx), Shadowed(Vec), } impl ByName { /// Add an additional index for this name. fn add_idx(&mut self, new: LocalIdx) { match self { ByName::Shadowed(indices) => indices.push(new), ByName::Single(idx) => { *self = ByName::Shadowed(vec![*idx, new]); } } } /// Remove the most recent index for this name, unless it is a /// single. Returns `true` if an entry was removed. fn remove_idx(&mut self) -> bool { match self { ByName::Single(_) => false, ByName::Shadowed(indices) => match indices[..] { [fst, _snd] => { *self = ByName::Single(fst); true } _ => { indices.pop(); true } }, } } /// Return the most recent index. pub fn index(&self) -> LocalIdx { match self { ByName::Single(idx) => *idx, ByName::Shadowed(vec) => *vec.last().unwrap(), } } } /// Represents a scope known during compilation, which can be resolved /// directly to stack indices. #[derive(Debug, Default)] pub struct Scope { locals: Vec, pub upvalues: Vec, /// Secondary by-name index over locals. by_name: FxHashMap, /// How many scopes "deep" are these locals? scope_depth: usize, /// Current size of the `with`-stack at runtime. with_stack_size: usize, } impl Index for Scope { type Output = Local; fn index(&self, index: LocalIdx) -> &Self::Output { &self.locals[index.0] } } impl Scope { /// Inherit scope details from a parent scope (required for /// correctly nesting scopes in lambdas and thunks when special /// scope features like dynamic resolution are present). pub fn inherit(&self) -> Self { Self { scope_depth: self.scope_depth + 1, with_stack_size: self.with_stack_size, ..Default::default() } } /// Increase the `with`-stack size of this scope. pub fn push_with(&mut self) { self.with_stack_size += 1; } /// Decrease the `with`-stack size of this scope. pub fn pop_with(&mut self) { self.with_stack_size -= 1; } /// Does this scope currently require dynamic runtime resolution /// of identifiers that could not be found? pub fn has_with(&self) -> bool { self.with_stack_size > 0 } /// Resolve the stack index of a statically known local. pub fn resolve_local(&mut self, name: &str) -> LocalPosition { if let Some(by_name) = self.by_name.get(name) { let idx = by_name.index(); let local = self .locals .get_mut(idx.0) .expect("invalid compiler state: indexed local missing"); local.used = true; // 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(idx); } return LocalPosition::Known(idx); } LocalPosition::Unknown } /// Declare a local variable that occupies a stack slot and should /// be accounted for, but is not directly accessible by users /// (e.g. attribute sets used for `with`). pub fn declare_phantom(&mut self, span: codemap::Span, initialised: bool) -> LocalIdx { let idx = self.locals.len(); self.locals.push(Local { initialised, span: Some(span), name: LocalName::Phantom, depth: self.scope_depth, needs_finaliser: false, must_thunk: false, used: true, }); LocalIdx(idx) } /// Declare an uninitialised, named local variable. /// /// Returns the `LocalIdx` of the new local, and optionally the /// index of a previous local shadowed by this one. pub fn declare_local( &mut self, name: String, span: codemap::Span, ) -> (LocalIdx, Option) { let idx = LocalIdx(self.locals.len()); self.locals.push(Local { name: LocalName::Ident(name.clone()), span: Some(span), depth: self.scope_depth, initialised: false, needs_finaliser: false, must_thunk: false, used: false, }); let mut shadowed = None; match self.by_name.entry(name) { hash_map::Entry::Occupied(mut entry) => { let existing = entry.get_mut(); shadowed = Some(existing.index()); existing.add_idx(idx); } hash_map::Entry::Vacant(entry) => { entry.insert(ByName::Single(idx)); } } (idx, shadowed) } pub fn declare_constant(&mut self, name: String) -> LocalIdx { let idx = LocalIdx(self.locals.len()); self.locals.push(Local { name: LocalName::Ident(name.clone()), span: None, depth: 0, initialised: true, used: false, needs_finaliser: false, must_thunk: false, }); // We don't need to worry about shadowing for constants; they're defined at the toplevel // always self.by_name.insert(name, ByName::Single(idx)); idx } /// Mark local as initialised after compiling its expression. pub fn mark_initialised(&mut self, idx: LocalIdx) { self.locals[idx.0].initialised = true; } /// Mark local as needing a finaliser. pub fn mark_needs_finaliser(&mut self, idx: LocalIdx) { self.locals[idx.0].needs_finaliser = true; } /// Mark local as must be wrapped in a thunk. This happens if /// the local has a reference to itself in its upvalues. pub fn mark_must_thunk(&mut self, idx: LocalIdx) { self.locals[idx.0].must_thunk = true; } /// Compute the runtime stack index for a given local by /// accounting for uninitialised variables at scopes below this /// one. pub fn stack_index(&self, idx: LocalIdx) -> StackIdx { let uninitialised_count = self.locals[..(idx.0)] .iter() .filter(|l| !l.initialised && self[idx].depth > l.depth) .count(); StackIdx(idx.0 - uninitialised_count) } /// Increase the current scope depth (e.g. within a new bindings /// block, or `with`-scope). pub fn begin_scope(&mut self) { self.scope_depth += 1; } /// Decrease the scope depth and remove all locals still tracked /// for the current scope. /// /// Returns the count of locals that were dropped while marked as /// initialised (used by the compiler to determine whether to emit /// scope cleanup operations), as well as the spans of the /// definitions of unused locals (used by the compiler to emit /// unused binding warnings). pub fn end_scope(&mut self) -> (usize, Vec) { debug_assert!(self.scope_depth != 0, "can not end top scope"); let mut pops = 0; let mut unused_spans = vec![]; // TL;DR - iterate from the back while things belonging to the // ended scope still exist. while self.locals.last().unwrap().depth == self.scope_depth { if let Some(local) = self.locals.pop() { // pop the local from the stack if it was actually // initialised if local.initialised { pops += 1; } // analyse whether the local was accessed during its // lifetime, and emit a warning otherwise (unless the // user explicitly chose to ignore it by prefixing the // identifier with `_`) if local.is_used() { unused_spans.extend(local.span); } // remove the by-name index if this was a named local if let LocalName::Ident(name) = local.name { if let hash_map::Entry::Occupied(mut entry) = self.by_name.entry(name) { // If no removal occured through `remove_idx` // (i.e. there was no shadowing going on), // nuke the whole entry. if !entry.get_mut().remove_idx() { entry.remove(); } } } } } self.scope_depth -= 1; (pops, unused_spans) } /// Access the current scope depth. pub fn scope_depth(&self) -> usize { self.scope_depth } }