Something went wrong. Try again.
forked from tvlfyi/tvix
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396//! 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<codemap::Span>,
/// 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<SmolStr> { 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,}
/// 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<LocalIdx>),}
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<Local>, pub upvalues: Vec<Upvalue>,
/// Secondary by-name index over locals. by_name: FxHashMap<String, ByName>,
/// How many scopes "deep" are these locals? scope_depth: usize,
/// Current size of the `with`-stack at runtime. with_stack_size: usize,}
impl Index<LocalIdx> 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(&self, name: &str) -> LocalPosition { if let Some(by_name) = self.by_name.get(name) { let idx = by_name.index(); let local = &self.locals[idx.0];
// 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<LocalIdx>) { 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; }
pub fn mark_used(&mut self, idx: LocalIdx) { self.locals[idx.0].used = 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<codemap::Span>) { 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 }}