snix_eval/compiler/
mod.rs

1//! This module implements a compiler for compiling the rnix AST
2//! representation to Snix bytecode.
3//!
4//! A note on `unwrap()`: This module contains a lot of calls to
5//! `unwrap()` or `expect(...)` on data structures returned by `rnix`.
6//! The reason for this is that rnix uses the same data structures to
7//! represent broken and correct ASTs, so all typed AST variants have
8//! the ability to represent an incorrect node.
9//!
10//! However, at the time that the AST is passed to the compiler we
11//! have verified that `rnix` considers the code to be correct, so all
12//! variants are fulfilled. In cases where the invariant is guaranteed
13//! by the code in this module, `debug_assert!` has been used to catch
14//! mistakes early during development.
15
16mod bindings;
17mod import;
18mod optimiser;
19mod scope;
20
21use codemap::Span;
22use rnix::ast::{self, AstToken};
23use rustc_hash::FxHashMap;
24use smol_str::SmolStr;
25use std::collections::BTreeMap;
26use std::path::{Path, PathBuf};
27use std::rc::{Rc, Weak};
28
29use crate::chunk::Chunk;
30use crate::errors::{CatchableErrorKind, Error, ErrorKind, EvalResult};
31use crate::observer::CompilerObserver;
32use crate::opcode::{CodeIdx, Op, Position, UpvalueIdx};
33use crate::spans::ToSpan;
34use crate::value::{Closure, Formals, Lambda, NixAttrs, Thunk, Value};
35use crate::warnings::{EvalWarning, WarningKind};
36use crate::CoercionKind;
37use crate::SourceCode;
38
39use self::scope::{LocalIdx, LocalPosition, Scope, Upvalue, UpvalueKind};
40
41/// Represents the result of compiling a piece of Nix code. If
42/// compilation was successful, the resulting bytecode can be passed
43/// to the VM.
44pub struct CompilationOutput {
45    pub lambda: Rc<Lambda>,
46    pub warnings: Vec<EvalWarning>,
47    pub errors: Vec<Error>,
48}
49
50/// Represents the lambda currently being compiled.
51struct LambdaCtx {
52    lambda: Lambda,
53    scope: Scope,
54    captures_with_stack: bool,
55}
56
57impl LambdaCtx {
58    fn new() -> Self {
59        LambdaCtx {
60            lambda: Lambda::default(),
61            scope: Default::default(),
62            captures_with_stack: false,
63        }
64    }
65
66    fn inherit(&self) -> Self {
67        LambdaCtx {
68            lambda: Lambda::default(),
69            scope: self.scope.inherit(),
70            captures_with_stack: false,
71        }
72    }
73}
74
75/// When compiling functions with an argument attribute set destructuring pattern,
76/// we need to do multiple passes over the declared formal arguments when setting
77/// up their local bindings (similarly to `let … in` expressions and recursive
78/// attribute sets. For this purpose, this struct is used to represent the two
79/// kinds of formal arguments:
80///
81/// - `TrackedFormal::NoDefault` is always required and causes an evaluation error
82///   if the corresponding attribute is missing in a function call.
83/// - `TrackedFormal::WithDefault` may be missing in the passed attribute set—
84///   in which case a `default_expr` will be evaluated and placed in the formal
85///   argument's local variable slot.
86enum TrackedFormal {
87    NoDefault {
88        local_idx: LocalIdx,
89        pattern_entry: ast::PatEntry,
90    },
91    WithDefault {
92        local_idx: LocalIdx,
93        /// Extra phantom local used for coordinating runtime dispatching not observable to
94        /// the language user. Detailed description in `compile_param_pattern()`.
95        finalise_request_idx: LocalIdx,
96        default_expr: ast::Expr,
97        pattern_entry: ast::PatEntry,
98    },
99}
100
101impl TrackedFormal {
102    fn pattern_entry(&self) -> &ast::PatEntry {
103        match self {
104            TrackedFormal::NoDefault { pattern_entry, .. } => pattern_entry,
105            TrackedFormal::WithDefault { pattern_entry, .. } => pattern_entry,
106        }
107    }
108    fn local_idx(&self) -> LocalIdx {
109        match self {
110            TrackedFormal::NoDefault { local_idx, .. } => *local_idx,
111            TrackedFormal::WithDefault { local_idx, .. } => *local_idx,
112        }
113    }
114}
115
116/// The map of globally available functions and other values that
117/// should implicitly be resolvable in the global scope.
118pub type GlobalsMap = FxHashMap<&'static str, Value>;
119
120/// Set of builtins that (if they exist) should be made available in
121/// the global scope, meaning that they can be accessed not just
122/// through `builtins.<name>`, but directly as `<name>`. This is not
123/// configurable, it is based on what Nix 2.3 exposed.
124const GLOBAL_BUILTINS: &[&str] = &[
125    "abort",
126    "baseNameOf",
127    "derivation",
128    "derivationStrict",
129    "dirOf",
130    "fetchGit",
131    "fetchMercurial",
132    "fetchTarball",
133    "fromTOML",
134    "import",
135    "isNull",
136    "map",
137    "placeholder",
138    "removeAttrs",
139    "scopedImport",
140    "throw",
141    "toString",
142    "__curPos",
143];
144
145pub struct Compiler<'source, 'observer> {
146    contexts: Vec<LambdaCtx>,
147    warnings: Vec<EvalWarning>,
148    errors: Vec<Error>,
149    root_dir: PathBuf,
150
151    /// Carries all known global tokens; the full set of which is
152    /// created when the compiler is invoked.
153    ///
154    /// Each global has an associated token, which when encountered as
155    /// an identifier is resolved against the scope poisoning logic,
156    /// and a function that should emit code for the token.
157    globals: Rc<GlobalsMap>,
158
159    /// Reference to the struct holding all of the source code, which
160    /// is used for error creation.
161    source: &'source SourceCode,
162
163    /// File reference in the source map for the current file, which
164    /// is used for creating spans.
165    file: &'source codemap::File,
166
167    /// Carry an observer for the compilation process, which is called
168    /// whenever a chunk is emitted.
169    observer: &'observer mut dyn CompilerObserver,
170
171    /// Carry a count of nested scopes which have requested the
172    /// compiler not to emit anything. This used for compiling dead
173    /// code branches to catch errors & warnings in them.
174    dead_scope: usize,
175}
176
177impl Compiler<'_, '_> {
178    pub(super) fn span_for<S: ToSpan>(&self, to_span: &S) -> Span {
179        to_span.span_for(self.file)
180    }
181}
182
183/// Compiler construction
184impl<'source, 'observer> Compiler<'source, 'observer> {
185    pub(crate) fn new(
186        location: Option<PathBuf>,
187        globals: Rc<GlobalsMap>,
188        env: Option<&FxHashMap<SmolStr, Value>>,
189        source: &'source SourceCode,
190        file: &'source codemap::File,
191        observer: &'observer mut dyn CompilerObserver,
192    ) -> EvalResult<Self> {
193        let mut root_dir = match location {
194            Some(dir) if cfg!(target_arch = "wasm32") || dir.is_absolute() => Ok(dir),
195            _ => {
196                let current_dir = std::env::current_dir().map_err(|e| {
197                    Error::new(
198                        ErrorKind::RelativePathResolution(format!(
199                            "could not determine current directory: {}",
200                            e
201                        )),
202                        file.span,
203                        source.clone(),
204                    )
205                })?;
206                if let Some(dir) = location {
207                    Ok(current_dir.join(dir))
208                } else {
209                    Ok(current_dir)
210                }
211            }
212        }?;
213
214        // If the path passed from the caller points to a file, the
215        // filename itself needs to be truncated as this must point to a
216        // directory.
217        if root_dir.is_file() {
218            root_dir.pop();
219        }
220
221        #[cfg(not(target_arch = "wasm32"))]
222        debug_assert!(root_dir.is_absolute());
223
224        let mut compiler = Self {
225            root_dir,
226            source,
227            file,
228            observer,
229            globals,
230            contexts: vec![LambdaCtx::new()],
231            warnings: vec![],
232            errors: vec![],
233            dead_scope: 0,
234        };
235
236        if let Some(env) = env {
237            compiler.compile_env(env);
238        }
239
240        Ok(compiler)
241    }
242}
243
244// Helper functions for emitting code and metadata to the internal
245// structures of the compiler.
246impl Compiler<'_, '_> {
247    fn context(&self) -> &LambdaCtx {
248        &self.contexts[self.contexts.len() - 1]
249    }
250
251    fn context_mut(&mut self) -> &mut LambdaCtx {
252        let idx = self.contexts.len() - 1;
253        &mut self.contexts[idx]
254    }
255
256    fn chunk(&mut self) -> &mut Chunk {
257        &mut self.context_mut().lambda.chunk
258    }
259
260    fn scope(&self) -> &Scope {
261        &self.context().scope
262    }
263
264    fn scope_mut(&mut self) -> &mut Scope {
265        &mut self.context_mut().scope
266    }
267
268    /// Push a single instruction to the current bytecode chunk and
269    /// track the source span from which it was compiled.
270    fn push_op<T: ToSpan>(&mut self, data: Op, node: &T) -> CodeIdx {
271        if self.dead_scope > 0 {
272            return CodeIdx(0);
273        }
274
275        let span = self.span_for(node);
276        CodeIdx(self.chunk().push_op(data, span))
277    }
278
279    fn push_u8(&mut self, data: u8) {
280        if self.dead_scope > 0 {
281            return;
282        }
283
284        self.chunk().code.push(data);
285    }
286
287    fn push_uvarint(&mut self, data: u64) {
288        if self.dead_scope > 0 {
289            return;
290        }
291
292        self.chunk().push_uvarint(data);
293    }
294
295    fn push_u16(&mut self, data: u16) {
296        if self.dead_scope > 0 {
297            return;
298        }
299
300        self.chunk().push_u16(data);
301    }
302
303    /// Emit a single constant to the current bytecode chunk and track
304    /// the source span from which it was compiled.
305    pub(super) fn emit_constant<T: ToSpan>(&mut self, value: Value, node: &T) {
306        if self.dead_scope > 0 {
307            return;
308        }
309
310        let idx = self.chunk().push_constant(value);
311        self.push_op(Op::Constant, node);
312        self.push_uvarint(idx.0 as u64);
313    }
314}
315
316// Actual code-emitting AST traversal methods.
317impl Compiler<'_, '_> {
318    fn compile(&mut self, slot: LocalIdx, expr: ast::Expr) {
319        let expr = optimiser::optimise_expr(self, slot, expr);
320
321        match &expr {
322            ast::Expr::Literal(literal) => self.compile_literal(literal),
323            ast::Expr::Path(path) => self.compile_path(slot, path),
324            ast::Expr::Str(s) => self.compile_str(slot, s),
325
326            ast::Expr::UnaryOp(op) => self.thunk(slot, op, move |c, s| c.compile_unary_op(s, op)),
327
328            ast::Expr::BinOp(binop) => {
329                self.thunk(slot, binop, move |c, s| c.compile_binop(s, binop))
330            }
331
332            ast::Expr::HasAttr(has_attr) => {
333                self.thunk(slot, has_attr, move |c, s| c.compile_has_attr(s, has_attr))
334            }
335
336            ast::Expr::List(list) => self.thunk(slot, list, move |c, s| c.compile_list(s, list)),
337
338            ast::Expr::AttrSet(attrs) => {
339                self.thunk(slot, attrs, move |c, s| c.compile_attr_set(s, attrs))
340            }
341
342            ast::Expr::Select(select) => {
343                self.thunk(slot, select, move |c, s| c.compile_select(s, select))
344            }
345
346            ast::Expr::Assert(assert) => {
347                self.thunk(slot, assert, move |c, s| c.compile_assert(s, assert))
348            }
349            ast::Expr::IfElse(if_else) => {
350                self.thunk(slot, if_else, move |c, s| c.compile_if_else(s, if_else))
351            }
352
353            ast::Expr::LetIn(let_in) => {
354                self.thunk(slot, let_in, move |c, s| c.compile_let_in(s, let_in))
355            }
356
357            ast::Expr::Ident(ident) => self.compile_ident(slot, ident),
358            ast::Expr::With(with) => self.thunk(slot, with, |c, s| c.compile_with(s, with)),
359            ast::Expr::Lambda(lambda) => self.thunk(slot, lambda, move |c, s| {
360                c.compile_lambda_or_thunk(false, s, lambda, |c, s| c.compile_lambda(s, lambda))
361            }),
362            ast::Expr::Apply(apply) => {
363                self.thunk(slot, apply, move |c, s| c.compile_apply(s, apply))
364            }
365
366            // Parenthesized expressions are simply unwrapped, leaving
367            // their value on the stack.
368            ast::Expr::Paren(paren) => self.compile(slot, paren.expr().unwrap()),
369
370            ast::Expr::LegacyLet(legacy_let) => self.thunk(slot, legacy_let, move |c, s| {
371                c.compile_legacy_let(s, legacy_let)
372            }),
373
374            ast::Expr::Root(_) => unreachable!("there cannot be more than one root"),
375            ast::Expr::Error(_) => unreachable!("compile is only called on validated trees"),
376        }
377    }
378
379    /// Compiles an expression, but does not emit any code for it as
380    /// it is considered dead. This will still catch errors and
381    /// warnings in that expression.
382    ///
383    /// A warning about the that code being dead is assumed to already be
384    /// emitted by the caller of this.
385    fn compile_dead_code(&mut self, slot: LocalIdx, node: ast::Expr) {
386        self.dead_scope += 1;
387        self.compile(slot, node);
388        self.dead_scope -= 1;
389    }
390
391    fn compile_literal(&mut self, node: &ast::Literal) {
392        let value = match node.kind() {
393            ast::LiteralKind::Float(f) => Value::Float(f.value().unwrap()),
394            ast::LiteralKind::Integer(i) => match i.value() {
395                Ok(v) => Value::Integer(v),
396                Err(err) => return self.emit_error(node, err.into()),
397            },
398
399            ast::LiteralKind::Uri(u) => {
400                self.emit_warning(node, WarningKind::DeprecatedLiteralURL);
401                Value::from(u.syntax().text())
402            }
403        };
404
405        self.emit_constant(value, node);
406    }
407
408    fn compile_path(&mut self, slot: LocalIdx, node: &ast::Path) {
409        // TODO(tazjin): placeholder implementation while waiting for
410        // https://github.com/nix-community/rnix-parser/pull/96
411
412        let raw_path = node.to_string();
413        let path = if raw_path.starts_with('/') {
414            Path::new(&raw_path).to_owned()
415        } else if raw_path.starts_with('~') {
416            // We assume that home paths start with ~/ or fail to parse
417            // TODO: this should be checked using a parse-fail test.
418            debug_assert!(raw_path.len() > 2 && raw_path.starts_with("~/"));
419
420            let home_relative_path = &raw_path[2..(raw_path.len())];
421            self.emit_constant(
422                Value::UnresolvedPath(Box::new(home_relative_path.into())),
423                node,
424            );
425            self.push_op(Op::ResolveHomePath, node);
426            return;
427        } else if raw_path.starts_with('<') {
428            // TODO: decide what to do with findFile
429            if raw_path.len() == 2 {
430                return self.emit_constant(
431                    Value::Catchable(Box::new(CatchableErrorKind::NixPathResolution(
432                        "Empty <> path not allowed".into(),
433                    ))),
434                    node,
435                );
436            }
437            let path = &raw_path[1..(raw_path.len() - 1)];
438            // Make a thunk to resolve the path (without using `findFile`, at least for now?)
439            return self.thunk(slot, node, move |c, _| {
440                c.emit_constant(Value::UnresolvedPath(Box::new(path.into())), node);
441                c.push_op(Op::FindFile, node);
442            });
443        } else {
444            let mut buf = self.root_dir.clone();
445            buf.push(&raw_path);
446            buf
447        };
448
449        // TODO: Use https://github.com/rust-lang/rfcs/issues/2208
450        // once it is available
451        let value = Value::Path(Box::new(crate::value::canon_path(path)));
452        self.emit_constant(value, node);
453    }
454
455    /// Helper that compiles the given string parts strictly. The caller
456    /// (`compile_str`) needs to figure out if the result of compiling this
457    /// needs to be thunked or not.
458    fn compile_str_parts(
459        &mut self,
460        slot: LocalIdx,
461        parent_node: &ast::Str,
462        parts: Vec<ast::InterpolPart<String>>,
463    ) {
464        // The string parts are produced in literal order, however
465        // they need to be reversed on the stack in order to
466        // efficiently create the real string in case of
467        // interpolation.
468        for part in parts.iter().rev() {
469            match part {
470                // Interpolated expressions are compiled as normal and
471                // dealt with by the VM before being assembled into
472                // the final string. We need to coerce them here,
473                // so OpInterpolate definitely has a string to consume.
474                ast::InterpolPart::Interpolation(ipol) => {
475                    self.compile(slot, ipol.expr().unwrap());
476                    // implicitly forces as well
477                    self.push_op(Op::CoerceToString, ipol);
478
479                    let encoded: u8 = CoercionKind {
480                        strong: false,
481                        import_paths: true,
482                    }
483                    .into();
484
485                    self.push_u8(encoded);
486                }
487
488                ast::InterpolPart::Literal(lit) => {
489                    self.emit_constant(Value::from(lit.as_str()), parent_node);
490                }
491            }
492        }
493
494        if parts.len() != 1 {
495            self.push_op(Op::Interpolate, parent_node);
496            self.push_uvarint(parts.len() as u64);
497        }
498    }
499
500    fn compile_str(&mut self, slot: LocalIdx, node: &ast::Str) {
501        let parts = node.normalized_parts();
502
503        // We need to thunk string expressions if they are the result of
504        // interpolation. A string that only consists of a single part (`"${foo}"`)
505        // can't desugar to the enclosed expression (`foo`) because we need to
506        // coerce the result to a string value. This would require forcing the
507        // value of the inner expression, so we need to wrap it in another thunk.
508        if parts.len() != 1 || matches!(&parts[0], ast::InterpolPart::Interpolation(_)) {
509            self.thunk(slot, node, move |c, s| {
510                c.compile_str_parts(s, node, parts);
511            });
512        } else {
513            self.compile_str_parts(slot, node, parts);
514        }
515    }
516
517    fn compile_unary_op(&mut self, slot: LocalIdx, op: &ast::UnaryOp) {
518        self.compile(slot, op.expr().unwrap());
519        self.emit_force(op);
520
521        let opcode = match op.operator().unwrap() {
522            ast::UnaryOpKind::Invert => Op::Invert,
523            ast::UnaryOpKind::Negate => Op::Negate,
524        };
525
526        self.push_op(opcode, op);
527    }
528
529    fn compile_binop(&mut self, slot: LocalIdx, op: &ast::BinOp) {
530        use ast::BinOpKind;
531
532        // Short-circuiting and other strange operators, which are
533        // under the same node type as NODE_BIN_OP, but need to be
534        // handled separately (i.e. before compiling the expressions
535        // used for standard binary operators).
536
537        match op.operator().unwrap() {
538            BinOpKind::And => return self.compile_and(slot, op),
539            BinOpKind::Or => return self.compile_or(slot, op),
540            BinOpKind::Implication => return self.compile_implication(slot, op),
541            _ => {}
542        };
543
544        // For all other operators, the two values need to be left on
545        // the stack in the correct order before pushing the
546        // instruction for the operation itself.
547        self.compile(slot, op.lhs().unwrap());
548        self.emit_force(&op.lhs().unwrap());
549
550        self.compile(slot, op.rhs().unwrap());
551        self.emit_force(&op.rhs().unwrap());
552
553        match op.operator().unwrap() {
554            BinOpKind::Add => self.push_op(Op::Add, op),
555            BinOpKind::Sub => self.push_op(Op::Sub, op),
556            BinOpKind::Mul => self.push_op(Op::Mul, op),
557            BinOpKind::Div => self.push_op(Op::Div, op),
558            BinOpKind::Update => self.push_op(Op::AttrsUpdate, op),
559            BinOpKind::Equal => self.push_op(Op::Equal, op),
560            BinOpKind::Less => self.push_op(Op::Less, op),
561            BinOpKind::LessOrEq => self.push_op(Op::LessOrEq, op),
562            BinOpKind::More => self.push_op(Op::More, op),
563            BinOpKind::MoreOrEq => self.push_op(Op::MoreOrEq, op),
564            BinOpKind::Concat => self.push_op(Op::Concat, op),
565
566            BinOpKind::NotEqual => {
567                self.push_op(Op::Equal, op);
568                self.push_op(Op::Invert, op)
569            }
570
571            // Handled by separate branch above.
572            BinOpKind::And | BinOpKind::Implication | BinOpKind::Or => {
573                unreachable!()
574            }
575        };
576    }
577
578    fn compile_and(&mut self, slot: LocalIdx, node: &ast::BinOp) {
579        debug_assert!(
580            matches!(node.operator(), Some(ast::BinOpKind::And)),
581            "compile_and called with wrong operator kind: {:?}",
582            node.operator(),
583        );
584
585        // Leave left-hand side value on the stack.
586        self.compile(slot, node.lhs().unwrap());
587        self.emit_force(&node.lhs().unwrap());
588
589        let throw_idx = self.push_op(Op::JumpIfCatchable, node);
590        self.push_u16(0);
591        // If this value is false, jump over the right-hand side - the
592        // whole expression is false.
593        let end_idx = self.push_op(Op::JumpIfFalse, node);
594        self.push_u16(0);
595
596        // Otherwise, remove the previous value and leave the
597        // right-hand side on the stack. Its result is now the value
598        // of the whole expression.
599        self.push_op(Op::Pop, node);
600        self.compile(slot, node.rhs().unwrap());
601        self.emit_force(&node.rhs().unwrap());
602
603        self.patch_jump(end_idx);
604        self.push_op(Op::AssertBool, node);
605        self.patch_jump(throw_idx);
606    }
607
608    fn compile_or(&mut self, slot: LocalIdx, node: &ast::BinOp) {
609        debug_assert!(
610            matches!(node.operator(), Some(ast::BinOpKind::Or)),
611            "compile_or called with wrong operator kind: {:?}",
612            node.operator(),
613        );
614
615        // Leave left-hand side value on the stack
616        self.compile(slot, node.lhs().unwrap());
617        self.emit_force(&node.lhs().unwrap());
618
619        let throw_idx = self.push_op(Op::JumpIfCatchable, node);
620        self.push_u16(0);
621        // Opposite of above: If this value is **true**, we can
622        // short-circuit the right-hand side.
623        let end_idx = self.push_op(Op::JumpIfTrue, node);
624        self.push_u16(0);
625        self.push_op(Op::Pop, node);
626        self.compile(slot, node.rhs().unwrap());
627        self.emit_force(&node.rhs().unwrap());
628
629        self.patch_jump(end_idx);
630        self.push_op(Op::AssertBool, node);
631        self.patch_jump(throw_idx);
632    }
633
634    fn compile_implication(&mut self, slot: LocalIdx, node: &ast::BinOp) {
635        debug_assert!(
636            matches!(node.operator(), Some(ast::BinOpKind::Implication)),
637            "compile_implication called with wrong operator kind: {:?}",
638            node.operator(),
639        );
640
641        // Leave left-hand side value on the stack and invert it.
642        self.compile(slot, node.lhs().unwrap());
643        self.emit_force(&node.lhs().unwrap());
644        let throw_idx = self.push_op(Op::JumpIfCatchable, node);
645        self.push_u16(0);
646        self.push_op(Op::Invert, node);
647
648        // Exactly as `||` (because `a -> b` = `!a || b`).
649        let end_idx = self.push_op(Op::JumpIfTrue, node);
650        self.push_u16(0);
651
652        self.push_op(Op::Pop, node);
653        self.compile(slot, node.rhs().unwrap());
654        self.emit_force(&node.rhs().unwrap());
655
656        self.patch_jump(end_idx);
657        self.push_op(Op::AssertBool, node);
658        self.patch_jump(throw_idx);
659    }
660
661    /// Compile list literals into equivalent bytecode. List
662    /// construction is fairly simple, consisting of pushing code for
663    /// each literal element and an instruction with the element
664    /// count.
665    ///
666    /// The VM, after evaluating the code for each element, simply
667    /// constructs the list from the given number of elements.
668    fn compile_list(&mut self, slot: LocalIdx, node: &ast::List) {
669        let mut count = 0;
670
671        // Open a temporary scope to correctly account for stack items
672        // that exist during the construction.
673        self.scope_mut().begin_scope();
674
675        for item in node.items() {
676            // Start tracing new stack slots from the second list
677            // element onwards. The first list element is located in
678            // the stack slot of the list itself.
679            let item_slot = match count {
680                0 => slot,
681                _ => {
682                    let item_span = self.span_for(&item);
683                    self.scope_mut().declare_phantom(item_span, false)
684                }
685            };
686
687            count += 1;
688            self.compile(item_slot, item);
689            self.scope_mut().mark_initialised(item_slot);
690        }
691
692        self.push_op(Op::List, node);
693        self.push_uvarint(count as u64);
694        self.scope_mut().end_scope();
695    }
696
697    fn compile_attr(&mut self, slot: LocalIdx, node: &ast::Attr) {
698        match node {
699            ast::Attr::Dynamic(dynamic) => {
700                self.compile(slot, dynamic.expr().unwrap());
701                self.emit_force(&dynamic.expr().unwrap());
702            }
703
704            ast::Attr::Str(s) => {
705                self.compile_str(slot, s);
706                self.emit_force(s);
707            }
708
709            ast::Attr::Ident(ident) => self.emit_literal_ident(ident),
710        }
711    }
712
713    fn compile_has_attr(&mut self, slot: LocalIdx, node: &ast::HasAttr) {
714        // Put the attribute set on the stack.
715        self.compile(slot, node.expr().unwrap());
716        self.emit_force(node);
717
718        // Push all path fragments with an operation for fetching the
719        // next nested element, for all fragments except the last one.
720        for (count, fragment) in node.attrpath().unwrap().attrs().enumerate() {
721            if count > 0 {
722                self.push_op(Op::AttrsTrySelect, &fragment);
723                self.emit_force(&fragment);
724            }
725
726            self.compile_attr(slot, &fragment);
727        }
728
729        // After the last fragment, emit the actual instruction that
730        // leaves a boolean on the stack.
731        self.push_op(Op::HasAttr, node);
732    }
733
734    /// When compiling select or select_or expressions, an optimisation is
735    /// possible of compiling the set emitted a constant attribute set by
736    /// immediately replacing it with the actual value.
737    ///
738    /// We take care not to emit an error here, as that would interfere with
739    /// thunking behaviour (there can be perfectly valid Nix code that accesses
740    /// a statically known attribute set that is lacking a key, because that
741    /// thunk is never evaluated). If anything is missing, just inform the
742    /// caller that the optimisation did not take place and move on. We may want
743    /// to emit warnings here in the future.
744    fn optimise_select(&mut self, path: &ast::Attrpath) -> bool {
745        // If compiling the set emitted a constant attribute set, the
746        // associated constant can immediately be replaced with the
747        // actual value.
748        //
749        // We take care not to emit an error here, as that would
750        // interfere with thunking behaviour (there can be perfectly
751        // valid Nix code that accesses a statically known attribute
752        // set that is lacking a key, because that thunk is never
753        // evaluated). If anything is missing, just move on. We may
754        // want to emit warnings here in the future.
755        if let Some((Op::Constant, op_idx)) = self.chunk().last_op() {
756            let (idx, _) = self.chunk().read_uvarint(op_idx + 1);
757            let constant = &mut self.chunk().constants[idx as usize];
758            if let Value::Attrs(attrs) = constant {
759                let mut path_iter = path.attrs();
760
761                // Only do this optimisation if there is a *single*
762                // element in the attribute path. It is extremely
763                // unlikely that we'd have a static nested set.
764                if let (Some(attr), None) = (path_iter.next(), path_iter.next()) {
765                    // Only do this optimisation for statically known attrs.
766                    if let Some(ident) = expr_static_attr_str(&attr) {
767                        if let Some(selected_value) = attrs.select(ident.as_bytes()) {
768                            *constant = selected_value.clone();
769                            return true;
770                        }
771                    }
772                }
773            }
774        }
775
776        false
777    }
778
779    fn compile_select(&mut self, slot: LocalIdx, node: &ast::Select) {
780        let set = node.expr().unwrap();
781        let path = node.attrpath().unwrap();
782
783        if node.or_token().is_some() {
784            return self.compile_select_or(slot, set, path, node.default_expr().unwrap());
785        }
786
787        // Push the set onto the stack
788        self.compile(slot, set.clone());
789        if self.optimise_select(&path) {
790            return;
791        }
792
793        // Compile each key fragment and emit access instructions.
794        //
795        // TODO: multi-select instruction to avoid re-pushing attrs on
796        // nested selects.
797        for fragment in path.attrs() {
798            // Force the current set value.
799            self.emit_force(&set);
800
801            self.compile_attr(slot, &fragment);
802            self.push_op(Op::AttrsSelect, &fragment);
803        }
804    }
805
806    /// Compile an `or` expression into a chunk of conditional jumps.
807    ///
808    /// If at any point during attribute set traversal a key is
809    /// missing, the `OpAttrOrNotFound` instruction will leave a
810    /// special sentinel value on the stack.
811    ///
812    /// After each access, a conditional jump evaluates the top of the
813    /// stack and short-circuits to the default value if it sees the
814    /// sentinel.
815    ///
816    /// Code like `{ a.b = 1; }.a.c or 42` yields this bytecode and
817    /// runtime stack:
818    ///
819    /// ```notrust
820    ///            Bytecode                     Runtime stack
821    ///  ┌────────────────────────────┐   ┌─────────────────────────┐
822    ///  │    ...                     │   │ ...                     │
823    ///  │ 5  OP_ATTRS(1)             │ → │ 5  [ { a.b = 1; }     ] │
824    ///  │ 6  OP_CONSTANT("a")        │ → │ 6  [ { a.b = 1; } "a" ] │
825    ///  │ 7  OP_ATTR_OR_NOT_FOUND    │ → │ 7  [ { b = 1; }       ] │
826    ///  │ 8  JUMP_IF_NOT_FOUND(13)   │ → │ 8  [ { b = 1; }       ] │
827    ///  │ 9  OP_CONSTANT("C")        │ → │ 9  [ { b = 1; } "c"   ] │
828    ///  │ 10 OP_ATTR_OR_NOT_FOUND    │ → │ 10 [ NOT_FOUND        ] │
829    ///  │ 11 JUMP_IF_NOT_FOUND(13)   │ → │ 11 [                  ] │
830    ///  │ 12 JUMP(14)                │   │ ..     jumped over      │
831    ///  │ 13 CONSTANT(42)            │ → │ 12 [ 42 ]               │
832    ///  │ 14 ...                     │   │ ..   ....               │
833    ///  └────────────────────────────┘   └─────────────────────────┘
834    /// ```
835    fn compile_select_or(
836        &mut self,
837        slot: LocalIdx,
838        set: ast::Expr,
839        path: ast::Attrpath,
840        default: ast::Expr,
841    ) {
842        self.compile(slot, set);
843        if self.optimise_select(&path) {
844            return;
845        }
846
847        let mut jumps = vec![];
848
849        for fragment in path.attrs() {
850            self.emit_force(&fragment);
851            self.compile_attr(slot, &fragment.clone());
852            self.push_op(Op::AttrsTrySelect, &fragment);
853            jumps.push(self.push_op(Op::JumpIfNotFound, &fragment));
854            self.push_u16(0);
855        }
856
857        let final_jump = self.push_op(Op::Jump, &path);
858        self.push_u16(0);
859
860        for jump in jumps {
861            self.patch_jump(jump);
862        }
863
864        // Compile the default value expression and patch the final
865        // jump to point *beyond* it.
866        self.compile(slot, default);
867        self.patch_jump(final_jump);
868    }
869
870    /// Compile `assert` expressions using jumping instructions in the VM.
871    ///
872    /// ```notrust
873    ///                        ┌─────────────────────┐
874    ///                        │ 0  [ conditional ]  │
875    ///                        │ 1   JUMP_IF_FALSE  →┼─┐
876    ///                        │ 2  [  main body  ]  │ │ Jump to else body if
877    ///                       ┌┼─3─←     JUMP        │ │ condition is false.
878    ///  Jump over else body  ││ 4   OP_ASSERT_FAIL ←┼─┘
879    ///  if condition is true.└┼─5─→     ...         │
880    ///                        └─────────────────────┘
881    /// ```
882    fn compile_assert(&mut self, slot: LocalIdx, node: &ast::Assert) {
883        // Compile the assertion condition to leave its value on the stack.
884        self.compile(slot, node.condition().unwrap());
885        self.emit_force(&node.condition().unwrap());
886
887        let throw_idx = self.push_op(Op::JumpIfCatchable, node);
888        self.push_u16(0);
889
890        let then_idx = self.push_op(Op::JumpIfFalse, node);
891        self.push_u16(0);
892
893        self.push_op(Op::Pop, node);
894        self.compile(slot, node.body().unwrap());
895
896        let else_idx = self.push_op(Op::Jump, node);
897        self.push_u16(0);
898
899        self.patch_jump(then_idx);
900        self.push_op(Op::Pop, node);
901        self.push_op(Op::AssertFail, &node.condition().unwrap());
902
903        self.patch_jump(else_idx);
904        self.patch_jump(throw_idx);
905    }
906
907    /// Compile conditional expressions using jumping instructions in the VM.
908    ///
909    /// ```notrust
910    ///                        ┌────────────────────┐
911    ///                        │ 0  [ conditional ] │
912    ///                        │ 1   JUMP_IF_FALSE →┼─┐
913    ///                        │ 2  [  main body  ] │ │ Jump to else body if
914    ///                       ┌┼─3─←     JUMP       │ │ condition is false.
915    ///  Jump over else body  ││ 4  [  else body  ]←┼─┘
916    ///  if condition is true.└┼─5─→     ...        │
917    ///                        └────────────────────┘
918    /// ```
919    fn compile_if_else(&mut self, slot: LocalIdx, node: &ast::IfElse) {
920        self.compile(slot, node.condition().unwrap());
921        self.emit_force(&node.condition().unwrap());
922
923        let throw_idx = self.push_op(Op::JumpIfCatchable, &node.condition().unwrap());
924        self.push_u16(0);
925
926        let then_idx = self.push_op(Op::JumpIfFalse, &node.condition().unwrap());
927        self.push_u16(0);
928
929        self.push_op(Op::Pop, node); // discard condition value
930        self.compile(slot, node.body().unwrap());
931
932        let else_idx = self.push_op(Op::Jump, node);
933        self.push_u16(0);
934
935        self.patch_jump(then_idx); // patch jump *to* else_body
936        self.push_op(Op::Pop, node); // discard condition value
937        self.compile(slot, node.else_body().unwrap());
938
939        self.patch_jump(else_idx); // patch jump *over* else body
940        self.patch_jump(throw_idx); // patch jump *over* else body
941    }
942
943    /// Compile `with` expressions by emitting instructions that
944    /// pop/remove the indices of attribute sets that are implicitly
945    /// in scope through `with` on the "with-stack".
946    fn compile_with(&mut self, slot: LocalIdx, node: &ast::With) {
947        self.scope_mut().begin_scope();
948        // TODO: Detect if the namespace is just an identifier, and
949        // resolve that directly (thus avoiding duplication on the
950        // stack).
951        self.compile(slot, node.namespace().unwrap());
952
953        let span = self.span_for(&node.namespace().unwrap());
954
955        // The attribute set from which `with` inherits values
956        // occupies a slot on the stack, but this stack slot is not
957        // directly accessible. As it must be accounted for to
958        // calculate correct offsets, what we call a "phantom" local
959        // is declared here.
960        let local_idx = self.scope_mut().declare_phantom(span, true);
961        let with_idx = self.scope().stack_index(local_idx);
962
963        self.scope_mut().push_with();
964
965        self.push_op(Op::PushWith, &node.namespace().unwrap());
966        self.push_uvarint(with_idx.0 as u64);
967
968        self.compile(slot, node.body().unwrap());
969
970        self.push_op(Op::PopWith, node);
971        self.scope_mut().pop_with();
972        self.cleanup_scope(node);
973    }
974
975    /// Compiles pattern function arguments, such as `{ a, b }: ...`.
976    ///
977    /// These patterns are treated as a special case of locals binding
978    /// where the attribute set itself is placed on the first stack
979    /// slot of the call frame (either as a phantom, or named in case
980    /// of an `@` binding), and the function call sets up the rest of
981    /// the stack as if the parameters were rewritten into a `let`
982    /// binding.
983    ///
984    /// For example:
985    ///
986    /// ```nix
987    /// ({ a, b ? 2, c ? a * b, ... }@args: <body>)  { a = 10; }
988    /// ```
989    ///
990    /// would be compiled similarly to a binding such as
991    ///
992    /// ```nix
993    /// let args = { a = 10; };
994    /// in let a = args.a;
995    ///        b = args.a or 2;
996    ///        c = args.c or a * b;
997    ///    in <body>
998    /// ```
999    ///
1000    /// However, there are two properties of pattern function arguments that can
1001    /// not be compiled by desugaring in this way:
1002    ///
1003    /// 1. Bindings have to fail if too many arguments are provided. This is
1004    ///    done by emitting a special instruction that checks the set of keys
1005    ///    from a constant containing the expected keys.
1006    /// 2. Formal arguments with a default expression are (as an optimization and
1007    ///    because it is simpler) not wrapped in another thunk, instead compiled
1008    ///    and accessed separately. This means that the default expression may
1009    ///    never make it into the local's stack slot if the argument is provided
1010    ///    by the caller. We need to take this into account and skip any
1011    ///    operations specific to the expression like thunk finalisation in such
1012    ///    cases.
1013    fn compile_param_pattern(&mut self, pattern: &ast::Pattern) -> (Formals, CodeIdx) {
1014        let span = self.span_for(pattern);
1015
1016        let (set_idx, pat_bind_name) = match pattern.pat_bind() {
1017            Some(name) => {
1018                let pat_bind_name = name.ident().unwrap().to_string();
1019                (
1020                    self.declare_local(&name, pat_bind_name.clone()),
1021                    Some(pat_bind_name),
1022                )
1023            }
1024            None => (self.scope_mut().declare_phantom(span, true), None),
1025        };
1026
1027        // At call time, the attribute set is already at the top of the stack.
1028        self.scope_mut().mark_initialised(set_idx);
1029        self.emit_force(pattern);
1030        let throw_idx = self.push_op(Op::JumpIfCatchable, pattern);
1031        self.push_u16(0);
1032
1033        // Evaluation fails on a type error, even if the argument(s) are unused.
1034        self.push_op(Op::AssertAttrs, pattern);
1035
1036        let ellipsis = pattern.ellipsis_token().is_some();
1037        if !ellipsis {
1038            self.push_op(Op::ValidateClosedFormals, pattern);
1039        }
1040
1041        // Similar to `let ... in ...`, we now do multiple passes over
1042        // the bindings to first declare them, then populate them, and
1043        // then finalise any necessary recursion into the scope.
1044        let mut entries: Vec<TrackedFormal> = vec![];
1045        let mut arguments = BTreeMap::default();
1046
1047        for entry in pattern.pat_entries() {
1048            let ident = entry.ident().unwrap();
1049            let idx = self.declare_local(&ident, ident.to_string());
1050
1051            arguments.insert(ident.into(), entry.default().is_some());
1052
1053            if let Some(default_expr) = entry.default() {
1054                entries.push(TrackedFormal::WithDefault {
1055                    local_idx: idx,
1056                    // This phantom is used to track at runtime (!) whether we need to
1057                    // finalise the local's stack slot or not. The relevant instructions are
1058                    // emitted in the second pass where the mechanism is explained as well.
1059                    finalise_request_idx: {
1060                        let span = self.span_for(&default_expr);
1061                        self.scope_mut().declare_phantom(span, false)
1062                    },
1063                    default_expr,
1064                    pattern_entry: entry,
1065                });
1066            } else {
1067                entries.push(TrackedFormal::NoDefault {
1068                    local_idx: idx,
1069                    pattern_entry: entry,
1070                });
1071            }
1072        }
1073
1074        // For each of the bindings, push the set on the stack and
1075        // attempt to select from it.
1076        let stack_idx = self.scope().stack_index(set_idx);
1077        for tracked_formal in entries.iter() {
1078            self.push_op(Op::GetLocal, pattern);
1079            self.push_uvarint(stack_idx.0 as u64);
1080            self.emit_literal_ident(&tracked_formal.pattern_entry().ident().unwrap());
1081
1082            let idx = tracked_formal.local_idx();
1083
1084            // Use the same mechanism as `compile_select_or` if a
1085            // default value was provided, or simply select otherwise.
1086            match tracked_formal {
1087                TrackedFormal::WithDefault {
1088                    default_expr,
1089                    pattern_entry,
1090                    ..
1091                } => {
1092                    // The tricky bit about compiling a formal argument with a default value
1093                    // is that the default may be a thunk that may depend on the value of
1094                    // other formal arguments, i.e. may need to be finalised. This
1095                    // finalisation can only happen if we are actually using the default
1096                    // value—otherwise OpFinalise will crash on an already finalised (or
1097                    // non-thunk) value.
1098                    //
1099                    // Thus we use an additional local to track whether we wound up
1100                    // defaulting or not. `FinaliseRequest(false)` indicates that we should
1101                    // not finalise, as we did not default.
1102                    //
1103                    // We are being wasteful with VM stack space in case of default
1104                    // expressions that don't end up needing to be finalised. Unfortunately
1105                    // we only know better after compiling the default expression, so
1106                    // avoiding unnecessary locals would mean we'd need to modify the chunk
1107                    // after the fact.
1108                    self.push_op(Op::AttrsTrySelect, &pattern_entry.ident().unwrap());
1109                    let jump_to_default = self.push_op(Op::JumpIfNotFound, default_expr);
1110                    self.push_u16(0);
1111
1112                    self.emit_constant(Value::FinaliseRequest(false), default_expr);
1113
1114                    let jump_over_default = self.push_op(Op::Jump, default_expr);
1115                    self.push_u16(0);
1116
1117                    self.patch_jump(jump_to_default);
1118
1119                    // Does not need to thunked since compile() already does so when necessary
1120                    self.compile(idx, default_expr.clone());
1121
1122                    self.emit_constant(Value::FinaliseRequest(true), default_expr);
1123
1124                    self.patch_jump(jump_over_default);
1125                }
1126                TrackedFormal::NoDefault { pattern_entry, .. } => {
1127                    self.push_op(Op::AttrsSelect, &pattern_entry.ident().unwrap());
1128                }
1129            }
1130
1131            self.scope_mut().mark_initialised(idx);
1132            if let TrackedFormal::WithDefault {
1133                finalise_request_idx,
1134                ..
1135            } = tracked_formal
1136            {
1137                self.scope_mut().mark_initialised(*finalise_request_idx);
1138            }
1139        }
1140
1141        for tracked_formal in entries.iter() {
1142            if self.scope()[tracked_formal.local_idx()].needs_finaliser {
1143                let stack_idx = self.scope().stack_index(tracked_formal.local_idx());
1144                match tracked_formal {
1145                    TrackedFormal::NoDefault { .. } =>
1146                        panic!("Snix bug: local for pattern formal needs finaliser, but has no default expr"),
1147                    TrackedFormal::WithDefault { finalise_request_idx, .. } => {
1148                        let finalise_request_stack_idx = self.scope().stack_index(*finalise_request_idx);
1149
1150                        // TODO(sterni): better spans
1151                        self.push_op(Op::GetLocal, pattern);
1152                        self.push_uvarint(finalise_request_stack_idx.0 as u64);
1153                        let jump_over_finalise =
1154                            self.push_op(Op::JumpIfNoFinaliseRequest, pattern);
1155                        self.push_u16(0);
1156                        self.push_op(Op::Finalise, pattern);
1157                        self.push_uvarint(stack_idx.0 as u64);
1158                        self.patch_jump(jump_over_finalise);
1159                        // Get rid of finaliser request value on the stack
1160                        self.push_op(Op::Pop, pattern);
1161                    }
1162                }
1163            }
1164        }
1165
1166        (
1167            (Formals {
1168                arguments,
1169                ellipsis,
1170                span,
1171                name: pat_bind_name,
1172            }),
1173            throw_idx,
1174        )
1175    }
1176
1177    fn compile_lambda(&mut self, slot: LocalIdx, node: &ast::Lambda) -> Option<CodeIdx> {
1178        // Compile the function itself, recording its formal arguments (if any)
1179        // for later use
1180        let formals = match node.param().unwrap() {
1181            ast::Param::Pattern(pat) => Some(self.compile_param_pattern(&pat)),
1182
1183            ast::Param::IdentParam(param) => {
1184                let name = param
1185                    .ident()
1186                    .unwrap()
1187                    .ident_token()
1188                    .unwrap()
1189                    .text()
1190                    .to_string();
1191
1192                let idx = self.declare_local(&param, &name);
1193                self.scope_mut().mark_initialised(idx);
1194                None
1195            }
1196        };
1197
1198        self.compile(slot, node.body().unwrap());
1199        if let Some((formals, throw_idx)) = formals {
1200            self.context_mut().lambda.formals = Some(formals);
1201            Some(throw_idx)
1202        } else {
1203            self.context_mut().lambda.formals = None;
1204            None
1205        }
1206    }
1207
1208    fn thunk<N, F>(&mut self, outer_slot: LocalIdx, node: &N, content: F)
1209    where
1210        N: ToSpan,
1211        F: FnOnce(&mut Compiler, LocalIdx),
1212    {
1213        self.compile_lambda_or_thunk(true, outer_slot, node, |comp, idx| {
1214            content(comp, idx);
1215            None
1216        })
1217    }
1218
1219    /// Compile an expression into a runtime closure or thunk
1220    fn compile_lambda_or_thunk<N, F>(
1221        &mut self,
1222        is_suspended_thunk: bool,
1223        outer_slot: LocalIdx,
1224        node: &N,
1225        content: F,
1226    ) where
1227        N: ToSpan,
1228        F: FnOnce(&mut Compiler, LocalIdx) -> Option<CodeIdx>,
1229    {
1230        let name = self.scope()[outer_slot].name();
1231        self.new_context();
1232
1233        // Set the (optional) name of the current slot on the lambda that is
1234        // being compiled.
1235        self.context_mut().lambda.name = name;
1236
1237        let span = self.span_for(node);
1238        let slot = self.scope_mut().declare_phantom(span, false);
1239        self.scope_mut().begin_scope();
1240
1241        let throw_idx = content(self, slot);
1242        self.cleanup_scope(node);
1243        if let Some(throw_idx) = throw_idx {
1244            self.patch_jump(throw_idx);
1245        }
1246
1247        // Pop the lambda context back off, and emit the finished
1248        // lambda as a constant.
1249        let mut compiled = self.contexts.pop().unwrap();
1250
1251        // Emit an instruction to inform the VM that the chunk has ended.
1252        compiled
1253            .lambda
1254            .chunk
1255            .push_op(Op::Return, self.span_for(node));
1256
1257        let lambda = Rc::new(compiled.lambda);
1258        if is_suspended_thunk {
1259            self.observer.observe_compiled_thunk(&lambda);
1260        } else {
1261            self.observer.observe_compiled_lambda(&lambda);
1262        }
1263
1264        // If no upvalues are captured, emit directly and move on.
1265        if lambda.upvalue_count == 0 && !compiled.captures_with_stack {
1266            self.emit_constant(
1267                if is_suspended_thunk {
1268                    Value::Thunk(Thunk::new_suspended(lambda, span))
1269                } else {
1270                    Value::Closure(Rc::new(Closure::new(lambda)))
1271                },
1272                node,
1273            );
1274            return;
1275        }
1276
1277        // Otherwise, we need to emit the variable number of
1278        // operands that allow the runtime to close over the
1279        // upvalues and leave a blueprint in the constant index from
1280        // which the result can be constructed.
1281        let blueprint_idx = self.chunk().push_constant(Value::Blueprint(lambda));
1282
1283        let code_idx = self.push_op(
1284            if is_suspended_thunk {
1285                Op::ThunkSuspended
1286            } else {
1287                Op::ThunkClosure
1288            },
1289            node,
1290        );
1291        self.push_uvarint(blueprint_idx.0 as u64);
1292
1293        self.emit_upvalue_data(
1294            outer_slot,
1295            node,
1296            compiled.scope.upvalues,
1297            compiled.captures_with_stack,
1298        );
1299
1300        if !is_suspended_thunk && !self.scope()[outer_slot].needs_finaliser {
1301            if !self.scope()[outer_slot].must_thunk {
1302                // The closure has upvalues, but is not recursive. Therefore no
1303                // thunk is required, which saves us the overhead of
1304                // Rc<RefCell<>>
1305                self.chunk().code[code_idx.0] = Op::Closure as u8;
1306            } else {
1307                // This case occurs when a closure has upvalue-references to
1308                // itself but does not need a finaliser. Since no OpFinalise
1309                // will be emitted later on we synthesize one here. It is needed
1310                // here only to set [`Closure::is_finalised`] which is used for
1311                // sanity checks.
1312                #[cfg(debug_assertions)]
1313                {
1314                    self.push_op(Op::Finalise, &self.span_for(node));
1315                    self.push_uvarint(self.scope().stack_index(outer_slot).0 as u64);
1316                }
1317            }
1318        }
1319    }
1320
1321    fn compile_apply(&mut self, slot: LocalIdx, node: &ast::Apply) {
1322        // To call a function, we leave its arguments on the stack,
1323        // followed by the function expression itself, and then emit a
1324        // call instruction. This way, the stack is perfectly laid out
1325        // to enter the function call straight away.
1326        self.compile(slot, node.argument().unwrap());
1327        self.compile(slot, node.lambda().unwrap());
1328        self.emit_force(&node.lambda().unwrap());
1329        self.push_op(Op::Call, node);
1330    }
1331
1332    /// Emit the data instructions that the runtime needs to correctly
1333    /// assemble the upvalues struct.
1334    fn emit_upvalue_data<T: ToSpan>(
1335        &mut self,
1336        slot: LocalIdx,
1337        _: &T, // TODO
1338        upvalues: Vec<Upvalue>,
1339        capture_with: bool,
1340    ) {
1341        // Push the count of arguments to be expected, with one bit set to
1342        // indicate whether the with stack needs to be captured.
1343        let mut count = (upvalues.len() as u64) << 1;
1344        if capture_with {
1345            count |= 1;
1346        }
1347        self.push_uvarint(count);
1348
1349        for upvalue in upvalues {
1350            match upvalue.kind {
1351                UpvalueKind::Local(idx) => {
1352                    let target = &self.scope()[idx];
1353                    let stack_idx = self.scope().stack_index(idx);
1354
1355                    // If the target is not yet initialised, we need to defer
1356                    // the local access
1357                    if !target.initialised {
1358                        self.push_uvarint(Position::deferred_local(stack_idx).0);
1359                        self.scope_mut().mark_needs_finaliser(slot);
1360                    } else {
1361                        // a self-reference
1362                        if slot == idx {
1363                            self.scope_mut().mark_must_thunk(slot);
1364                        }
1365                        self.push_uvarint(Position::stack_index(stack_idx).0);
1366                    }
1367                }
1368
1369                UpvalueKind::Upvalue(idx) => {
1370                    self.push_uvarint(Position::upvalue_index(idx).0);
1371                }
1372            };
1373        }
1374    }
1375
1376    /// Emit the literal string value of an identifier. Required for
1377    /// several operations related to attribute sets, where
1378    /// identifiers are used as string keys.
1379    fn emit_literal_ident(&mut self, ident: &ast::Ident) {
1380        self.emit_constant(Value::String(ident.clone().into()), ident);
1381    }
1382
1383    /// Patch the jump instruction at the given index, setting its
1384    /// jump offset from the placeholder to the current code position.
1385    ///
1386    /// This is required because the actual target offset of jumps is
1387    /// not known at the time when the jump operation itself is
1388    /// emitted.
1389    fn patch_jump(&mut self, idx: CodeIdx) {
1390        self.chunk().patch_jump(idx.0);
1391    }
1392
1393    /// Decrease scope depth of the current function and emit
1394    /// instructions to clean up the stack at runtime.
1395    fn cleanup_scope<N: ToSpan>(&mut self, node: &N) {
1396        // When ending a scope, all corresponding locals need to be
1397        // removed, but the value of the body needs to remain on the
1398        // stack. This is implemented by a separate instruction.
1399        let (popcount, unused_spans) = self.scope_mut().end_scope();
1400
1401        for span in &unused_spans {
1402            self.emit_warning(span, WarningKind::UnusedBinding);
1403        }
1404
1405        if popcount > 0 {
1406            self.push_op(Op::CloseScope, node);
1407            self.push_uvarint(popcount as u64);
1408        }
1409    }
1410
1411    /// Open a new lambda context within which to compile a function,
1412    /// closure or thunk.
1413    fn new_context(&mut self) {
1414        self.contexts.push(self.context().inherit());
1415    }
1416
1417    /// Declare a local variable known in the scope that is being
1418    /// compiled by pushing it to the locals. This is used to
1419    /// determine the stack offset of variables.
1420    fn declare_local<S: Into<String>, N: ToSpan>(&mut self, node: &N, name: S) -> LocalIdx {
1421        let name = name.into();
1422        let depth = self.scope().scope_depth();
1423
1424        // Do this little dance to turn name:&'a str into the same
1425        // string with &'static lifetime, as required by WarningKind
1426        if let Some((global_ident, _)) = self.globals.get_key_value(name.as_str()) {
1427            self.emit_warning(node, WarningKind::ShadowedGlobal(global_ident));
1428        }
1429
1430        let span = self.span_for(node);
1431        let (idx, shadowed) = self.scope_mut().declare_local(name, span);
1432
1433        if let Some(shadow_idx) = shadowed {
1434            let other = &self.scope()[shadow_idx];
1435            if other.depth == depth {
1436                self.emit_error(node, ErrorKind::VariableAlreadyDefined(other.span));
1437            }
1438        }
1439
1440        idx
1441    }
1442
1443    /// Determine whether the current lambda context has any ancestors
1444    /// that use dynamic scope resolution, and mark contexts as
1445    /// needing to capture their enclosing `with`-stack in their
1446    /// upvalues.
1447    fn has_dynamic_ancestor(&mut self) -> bool {
1448        let mut ancestor_has_with = false;
1449
1450        for ctx in self.contexts.iter_mut() {
1451            if ancestor_has_with {
1452                // If the ancestor has an active with stack, mark this
1453                // lambda context as needing to capture it.
1454                ctx.captures_with_stack = true;
1455            } else {
1456                // otherwise, check this context and move on
1457                ancestor_has_with = ctx.scope.has_with();
1458            }
1459        }
1460
1461        ancestor_has_with
1462    }
1463
1464    fn emit_force<N: ToSpan>(&mut self, node: &N) {
1465        self.push_op(Op::Force, node);
1466    }
1467
1468    fn emit_warning<N: ToSpan>(&mut self, node: &N, kind: WarningKind) {
1469        let span = self.span_for(node);
1470        self.warnings.push(EvalWarning { kind, span })
1471    }
1472
1473    fn emit_error<N: ToSpan>(&mut self, node: &N, kind: ErrorKind) {
1474        let span = self.span_for(node);
1475        self.errors
1476            .push(Error::new(kind, span, self.source.clone()))
1477    }
1478}
1479
1480/// Convert a non-dynamic string expression to a string if possible.
1481fn expr_static_str(node: &ast::Str) -> Option<SmolStr> {
1482    let mut parts = node.normalized_parts();
1483
1484    if parts.len() != 1 {
1485        return None;
1486    }
1487
1488    if let Some(ast::InterpolPart::Literal(lit)) = parts.pop() {
1489        return Some(SmolStr::new(lit));
1490    }
1491
1492    None
1493}
1494
1495/// Convert the provided `ast::Attr` into a statically known string if
1496/// possible.
1497fn expr_static_attr_str(node: &ast::Attr) -> Option<SmolStr> {
1498    match node {
1499        ast::Attr::Ident(ident) => Some(ident.ident_token().unwrap().text().into()),
1500        ast::Attr::Str(s) => expr_static_str(s),
1501
1502        // The dynamic node type is just a wrapper. C++ Nix does not care
1503        // about the dynamic wrapper when determining whether the node
1504        // itself is dynamic, it depends solely on the expression inside
1505        // (i.e. `let ${"a"} = 1; in a` is valid).
1506        ast::Attr::Dynamic(ref dynamic) => match dynamic.expr().unwrap() {
1507            ast::Expr::Str(s) => expr_static_str(&s),
1508            _ => None,
1509        },
1510    }
1511}
1512
1513/// Create a delayed source-only builtin compilation, for a builtin
1514/// which is written in Nix code.
1515///
1516/// **Important:** snix *panics* if a builtin with invalid source code
1517/// is supplied. This is because there is no user-friendly way to
1518/// thread the errors out of this function right now.
1519fn compile_src_builtin(
1520    name: &'static str,
1521    code: &str,
1522    source: SourceCode,
1523    weak: &Weak<GlobalsMap>,
1524) -> Value {
1525    use std::fmt::Write;
1526
1527    let parsed = rnix::ast::Root::parse(code);
1528
1529    if !parsed.errors().is_empty() {
1530        let mut out = format!("BUG: code for source-builtin '{}' had parser errors", name);
1531        for error in parsed.errors() {
1532            writeln!(out, "{}", error).unwrap();
1533        }
1534
1535        panic!("{}", out);
1536    }
1537
1538    let file = source.add_file(format!("<src-builtins/{}.nix>", name), code.to_string());
1539    let weak = weak.clone();
1540
1541    Value::Thunk(Thunk::new_suspended_native(Box::new(move || {
1542        let result = compile(
1543            &parsed.tree().expr().unwrap(),
1544            None,
1545            weak.upgrade().unwrap(),
1546            None,
1547            &source,
1548            &file,
1549            &mut crate::observer::NoOpObserver {},
1550        )
1551        .map_err(|e| ErrorKind::NativeError {
1552            gen_type: "derivation",
1553            err: Box::new(e),
1554        })?;
1555
1556        if !result.errors.is_empty() {
1557            return Err(ErrorKind::ImportCompilerError {
1558                path: format!("src-builtins/{}.nix", name).into(),
1559                errors: result.errors,
1560            });
1561        }
1562
1563        Ok(Value::Thunk(Thunk::new_suspended(result.lambda, file.span)))
1564    })))
1565}
1566
1567/// Prepare the full set of globals available in evaluated code. These
1568/// are constructed from the set of builtins supplied by the caller,
1569/// which are made available globally under the `builtins` identifier.
1570///
1571/// A subset of builtins (specified by [`GLOBAL_BUILTINS`]) is
1572/// available globally *iff* they are set.
1573///
1574/// Optionally adds the `import` feature if desired by the caller.
1575pub fn prepare_globals(
1576    builtins: Vec<(&'static str, Value)>,
1577    src_builtins: Vec<(&'static str, &'static str)>,
1578    source: SourceCode,
1579    enable_import: bool,
1580) -> Rc<GlobalsMap> {
1581    Rc::new_cyclic(Box::new(move |weak: &Weak<GlobalsMap>| {
1582        // First step is to construct the builtins themselves as
1583        // `NixAttrs`.
1584        let mut builtins: GlobalsMap = FxHashMap::from_iter(builtins);
1585
1586        // At this point, optionally insert `import` if enabled. To
1587        // "tie the knot" of `import` needing the full set of globals
1588        // to instantiate its compiler, the `Weak` reference is passed
1589        // here.
1590        if enable_import {
1591            let import = Value::Builtin(import::builtins_import(weak, source.clone()));
1592            builtins.insert("import", import);
1593        }
1594
1595        // Next, the actual map of globals which the compiler will use
1596        // to resolve identifiers is constructed.
1597        let mut globals: GlobalsMap = FxHashMap::default();
1598
1599        // builtins contain themselves (`builtins.builtins`), which we
1600        // can resolve by manually constructing a suspended thunk that
1601        // dereferences the same weak pointer as above.
1602        let weak_globals = weak.clone();
1603        builtins.insert(
1604            "builtins",
1605            Value::Thunk(Thunk::new_suspended_native(Box::new(move || {
1606                Ok(weak_globals
1607                    .upgrade()
1608                    .unwrap()
1609                    .get("builtins")
1610                    .cloned()
1611                    .unwrap())
1612            }))),
1613        );
1614
1615        // Insert top-level static value builtins.
1616        globals.insert("true", Value::Bool(true));
1617        globals.insert("false", Value::Bool(false));
1618        globals.insert("null", Value::Null);
1619
1620        // If "source builtins" were supplied, compile them and insert
1621        // them.
1622        builtins.extend(src_builtins.into_iter().map(move |(name, code)| {
1623            let compiled = compile_src_builtin(name, code, source.clone(), weak);
1624            (name, compiled)
1625        }));
1626
1627        // Construct the actual `builtins` attribute set and insert it
1628        // in the global scope.
1629        globals.insert(
1630            "builtins",
1631            Value::attrs(NixAttrs::from_iter(builtins.clone())),
1632        );
1633
1634        // Finally, the builtins that should be globally available are
1635        // "elevated" to the outer scope.
1636        for global in GLOBAL_BUILTINS {
1637            if let Some(builtin) = builtins.get(global).cloned() {
1638                globals.insert(global, builtin);
1639            }
1640        }
1641
1642        globals
1643    }))
1644}
1645
1646pub fn compile(
1647    expr: &ast::Expr,
1648    location: Option<PathBuf>,
1649    globals: Rc<GlobalsMap>,
1650    env: Option<&FxHashMap<SmolStr, Value>>,
1651    source: &SourceCode,
1652    file: &codemap::File,
1653    observer: &mut dyn CompilerObserver,
1654) -> EvalResult<CompilationOutput> {
1655    let mut c = Compiler::new(location, globals.clone(), env, source, file, observer)?;
1656
1657    let root_span = c.span_for(expr);
1658    let root_slot = c.scope_mut().declare_phantom(root_span, false);
1659    c.compile(root_slot, expr.clone());
1660
1661    // The final operation of any top-level Nix program must always be
1662    // `OpForce`. A thunk should not be returned to the user in an
1663    // unevaluated state (though in practice, a value *containing* a
1664    // thunk might be returned).
1665    c.emit_force(expr);
1666    if let Some(env) = env {
1667        if !env.is_empty() {
1668            c.push_op(Op::CloseScope, &root_span);
1669            c.push_uvarint(env.len() as u64);
1670        }
1671    }
1672    c.push_op(Op::Return, &root_span);
1673
1674    let lambda = Rc::new(c.contexts.pop().unwrap().lambda);
1675    c.observer.observe_compiled_toplevel(&lambda);
1676
1677    Ok(CompilationOutput {
1678        lambda,
1679        warnings: c.warnings,
1680        errors: c.errors,
1681    })
1682}