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}