snix_eval/compiler/
scope.rs

1//! This module implements the scope-tracking logic of the Snix
2//! compiler.
3//!
4//! Scoping in Nix is fairly complicated, there are features like
5//! mutually recursive bindings, `with`, upvalue capturing, and so
6//! on that introduce a fair bit of complexity.
7//!
8//! Snix attempts to do as much of the heavy lifting of this at
9//! compile time, and leave the runtime to mostly deal with known
10//! stack indices. To do this, the compiler simulates where locals
11//! will be at runtime using the data structures implemented here.
12
13use rustc_hash::FxHashMap;
14use std::{collections::hash_map, ops::Index};
15
16use smol_str::SmolStr;
17
18use crate::opcode::{StackIdx, UpvalueIdx};
19
20#[derive(Debug)]
21enum LocalName {
22    /// Normally declared local with a statically known name.
23    Ident(String),
24
25    /// Phantom stack value (e.g. attribute set used for `with`) that
26    /// must be accounted for to calculate correct stack offsets.
27    Phantom,
28}
29
30/// Represents a single local already known to the compiler.
31#[derive(Debug)]
32pub struct Local {
33    /// Identifier of this local. This is always a statically known
34    /// value (Nix does not allow dynamic identifier names in locals),
35    /// or a "phantom" value not accessible by users.
36    name: LocalName,
37
38    /// Source span at which this local was declared.
39    pub span: Option<codemap::Span>,
40
41    /// Scope depth of this local.
42    pub depth: usize,
43
44    /// Is this local initialised?
45    pub initialised: bool,
46
47    /// Is this local known to have been used at all?
48    pub used: bool,
49
50    /// Does this local need to be finalised after the enclosing scope
51    /// is completely constructed?
52    pub needs_finaliser: bool,
53
54    /// Does this local's upvalues contain a reference to itself?
55    pub must_thunk: bool,
56}
57
58impl Local {
59    /// Retrieve the name of the given local (if available).
60    pub fn name(&self) -> Option<SmolStr> {
61        match &self.name {
62            LocalName::Phantom => None,
63            LocalName::Ident(name) => Some(SmolStr::new(name)),
64        }
65    }
66
67    /// Is this local intentionally ignored? (i.e. name starts with `_`)
68    pub fn is_ignored(&self) -> bool {
69        match &self.name {
70            LocalName::Ident(name) => name.starts_with('_'),
71            LocalName::Phantom => false,
72        }
73    }
74
75    pub fn is_used(&self) -> bool {
76        self.depth == 0 || self.used || self.is_ignored()
77    }
78}
79
80/// Represents the current position of an identifier as resolved in a scope.
81pub enum LocalPosition {
82    /// Local is not known in this scope.
83    Unknown,
84
85    /// Local is known at the given local index.
86    Known(LocalIdx),
87
88    /// Local is known, but is being accessed recursively within its
89    /// own initialisation. Depending on context, this is either an
90    /// error or forcing a closure/thunk.
91    Recursive(LocalIdx),
92}
93
94/// Represents the different ways in which upvalues can be captured in
95/// closures or thunks.
96#[derive(Clone, Debug, PartialEq, Eq)]
97pub enum UpvalueKind {
98    /// This upvalue captures a local from the stack.
99    Local(LocalIdx),
100
101    /// This upvalue captures an enclosing upvalue.
102    Upvalue(UpvalueIdx),
103}
104
105#[derive(Clone, Debug)]
106pub struct Upvalue {
107    pub kind: UpvalueKind,
108}
109
110/// The index of a local in the scope's local array at compile time.
111#[repr(transparent)]
112#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd)]
113pub struct LocalIdx(usize);
114
115/// Helper struct for indexing over `Scope::locals` by name.
116#[derive(Debug)]
117enum ByName {
118    Single(LocalIdx),
119    Shadowed(Vec<LocalIdx>),
120}
121
122impl ByName {
123    /// Add an additional index for this name.
124    fn add_idx(&mut self, new: LocalIdx) {
125        match self {
126            ByName::Shadowed(indices) => indices.push(new),
127            ByName::Single(idx) => {
128                *self = ByName::Shadowed(vec![*idx, new]);
129            }
130        }
131    }
132
133    /// Remove the most recent index for this name, unless it is a
134    /// single. Returns `true` if an entry was removed.
135    fn remove_idx(&mut self) -> bool {
136        match self {
137            ByName::Single(_) => false,
138            ByName::Shadowed(indices) => match indices[..] {
139                [fst, _snd] => {
140                    *self = ByName::Single(fst);
141                    true
142                }
143                _ => {
144                    indices.pop();
145                    true
146                }
147            },
148        }
149    }
150
151    /// Return the most recent index.
152    pub fn index(&self) -> LocalIdx {
153        match self {
154            ByName::Single(idx) => *idx,
155            ByName::Shadowed(vec) => *vec.last().unwrap(),
156        }
157    }
158}
159
160/// Represents a scope known during compilation, which can be resolved
161/// directly to stack indices.
162#[derive(Debug, Default)]
163pub struct Scope {
164    locals: Vec<Local>,
165    pub upvalues: Vec<Upvalue>,
166
167    /// Secondary by-name index over locals.
168    by_name: FxHashMap<String, ByName>,
169
170    /// How many scopes "deep" are these locals?
171    scope_depth: usize,
172
173    /// Current size of the `with`-stack at runtime.
174    with_stack_size: usize,
175}
176
177impl Index<LocalIdx> for Scope {
178    type Output = Local;
179
180    fn index(&self, index: LocalIdx) -> &Self::Output {
181        &self.locals[index.0]
182    }
183}
184
185impl Scope {
186    /// Inherit scope details from a parent scope (required for
187    /// correctly nesting scopes in lambdas and thunks when special
188    /// scope features like dynamic resolution are present).
189    pub fn inherit(&self) -> Self {
190        Self {
191            scope_depth: self.scope_depth + 1,
192            with_stack_size: self.with_stack_size,
193            ..Default::default()
194        }
195    }
196
197    /// Increase the `with`-stack size of this scope.
198    pub fn push_with(&mut self) {
199        self.with_stack_size += 1;
200    }
201
202    /// Decrease the `with`-stack size of this scope.
203    pub fn pop_with(&mut self) {
204        self.with_stack_size -= 1;
205    }
206
207    /// Does this scope currently require dynamic runtime resolution
208    /// of identifiers that could not be found?
209    pub fn has_with(&self) -> bool {
210        self.with_stack_size > 0
211    }
212
213    /// Resolve the stack index of a statically known local.
214    pub fn resolve_local(&self, name: &str) -> LocalPosition {
215        if let Some(by_name) = self.by_name.get(name) {
216            let idx = by_name.index();
217            let local = &self.locals[idx.0];
218
219            // This local is still being initialised, meaning that
220            // we know its final runtime stack position, but it is
221            // not yet on the stack.
222            if !local.initialised {
223                return LocalPosition::Recursive(idx);
224            }
225
226            return LocalPosition::Known(idx);
227        }
228
229        LocalPosition::Unknown
230    }
231
232    /// Declare a local variable that occupies a stack slot and should
233    /// be accounted for, but is not directly accessible by users
234    /// (e.g. attribute sets used for `with`).
235    pub fn declare_phantom(&mut self, span: codemap::Span, initialised: bool) -> LocalIdx {
236        let idx = self.locals.len();
237        self.locals.push(Local {
238            initialised,
239            span: Some(span),
240            name: LocalName::Phantom,
241            depth: self.scope_depth,
242            needs_finaliser: false,
243            must_thunk: false,
244            used: true,
245        });
246
247        LocalIdx(idx)
248    }
249
250    /// Declare an uninitialised, named local variable.
251    ///
252    /// Returns the `LocalIdx` of the new local, and optionally the
253    /// index of a previous local shadowed by this one.
254    pub fn declare_local(
255        &mut self,
256        name: String,
257        span: codemap::Span,
258    ) -> (LocalIdx, Option<LocalIdx>) {
259        let idx = LocalIdx(self.locals.len());
260        self.locals.push(Local {
261            name: LocalName::Ident(name.clone()),
262            span: Some(span),
263            depth: self.scope_depth,
264            initialised: false,
265            needs_finaliser: false,
266            must_thunk: false,
267            used: false,
268        });
269
270        let mut shadowed = None;
271        match self.by_name.entry(name) {
272            hash_map::Entry::Occupied(mut entry) => {
273                let existing = entry.get_mut();
274                shadowed = Some(existing.index());
275                existing.add_idx(idx);
276            }
277            hash_map::Entry::Vacant(entry) => {
278                entry.insert(ByName::Single(idx));
279            }
280        }
281
282        (idx, shadowed)
283    }
284
285    pub fn declare_constant(&mut self, name: String) -> LocalIdx {
286        let idx = LocalIdx(self.locals.len());
287        self.locals.push(Local {
288            name: LocalName::Ident(name.clone()),
289            span: None,
290            depth: 0,
291            initialised: true,
292            used: false,
293            needs_finaliser: false,
294            must_thunk: false,
295        });
296        // We don't need to worry about shadowing for constants; they're defined at the toplevel
297        // always
298        self.by_name.insert(name, ByName::Single(idx));
299        idx
300    }
301
302    /// Mark local as initialised after compiling its expression.
303    pub fn mark_initialised(&mut self, idx: LocalIdx) {
304        self.locals[idx.0].initialised = true;
305    }
306
307    pub fn mark_used(&mut self, idx: LocalIdx) {
308        self.locals[idx.0].used = true;
309    }
310
311    /// Mark local as needing a finaliser.
312    pub fn mark_needs_finaliser(&mut self, idx: LocalIdx) {
313        self.locals[idx.0].needs_finaliser = true;
314    }
315
316    /// Mark local as must be wrapped in a thunk.  This happens if
317    /// the local has a reference to itself in its upvalues.
318    pub fn mark_must_thunk(&mut self, idx: LocalIdx) {
319        self.locals[idx.0].must_thunk = true;
320    }
321
322    /// Compute the runtime stack index for a given local by
323    /// accounting for uninitialised variables at scopes below this
324    /// one.
325    pub fn stack_index(&self, idx: LocalIdx) -> StackIdx {
326        let uninitialised_count = self.locals[..(idx.0)]
327            .iter()
328            .filter(|l| !l.initialised && self[idx].depth > l.depth)
329            .count();
330
331        StackIdx(idx.0 - uninitialised_count)
332    }
333
334    /// Increase the current scope depth (e.g. within a new bindings
335    /// block, or `with`-scope).
336    pub fn begin_scope(&mut self) {
337        self.scope_depth += 1;
338    }
339
340    /// Decrease the scope depth and remove all locals still tracked
341    /// for the current scope.
342    ///
343    /// Returns the count of locals that were dropped while marked as
344    /// initialised (used by the compiler to determine whether to emit
345    /// scope cleanup operations), as well as the spans of the
346    /// definitions of unused locals (used by the compiler to emit
347    /// unused binding warnings).
348    pub fn end_scope(&mut self) -> (usize, Vec<codemap::Span>) {
349        debug_assert!(self.scope_depth != 0, "can not end top scope");
350
351        let mut pops = 0;
352        let mut unused_spans = vec![];
353
354        // TL;DR - iterate from the back while things belonging to the
355        // ended scope still exist.
356        while self.locals.last().unwrap().depth == self.scope_depth {
357            if let Some(local) = self.locals.pop() {
358                // pop the local from the stack if it was actually
359                // initialised
360                if local.initialised {
361                    pops += 1;
362                }
363
364                // analyse whether the local was accessed during its
365                // lifetime, and emit a warning otherwise (unless the
366                // user explicitly chose to ignore it by prefixing the
367                // identifier with `_`)
368                if !local.is_used() {
369                    unused_spans.extend(local.span);
370                }
371
372                // remove the by-name index if this was a named local
373                if let LocalName::Ident(name) = local.name {
374                    if let hash_map::Entry::Occupied(mut entry) = self.by_name.entry(name) {
375                        // If no removal occured through `remove_idx`
376                        // (i.e. there was no shadowing going on),
377                        // nuke the whole entry.
378                        if !entry.get_mut().remove_idx() {
379                            entry.remove();
380                        }
381                    }
382                }
383            }
384        }
385
386        self.scope_depth -= 1;
387
388        (pops, unused_spans)
389    }
390
391    /// Access the current scope depth.
392    pub fn scope_depth(&self) -> usize {
393        self.scope_depth
394    }
395}