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

snix_eval/compiler/
mod.rs
