snix_eval/vm/
mod.rs

1//! This module implements the abstract/virtual machine that runs Snix
2//! bytecode.
3//!
4//! The operation of the VM is facilitated by the [`Frame`] type,
5//! which controls the current execution state of the VM and is
6//! processed within the VM's operating loop.
7//!
8//! A [`VM`] is used by instantiating it with an initial [`Frame`],
9//! then triggering its execution and waiting for the VM to return or
10//! yield an error.
11
12pub mod generators;
13mod macros;
14
15use bstr::{BString, ByteSlice, ByteVec};
16use codemap::Span;
17use rustc_hash::FxHashMap;
18use serde_json::json;
19use std::{cmp::Ordering, ops::DerefMut, path::PathBuf, rc::Rc};
20
21use crate::{
22    arithmetic_op,
23    chunk::Chunk,
24    cmp_op,
25    compiler::GlobalsMap,
26    errors::{CatchableErrorKind, Error, ErrorKind, EvalResult},
27    io::EvalIO,
28    lifted_pop,
29    nix_search_path::NixSearchPath,
30    observer::RuntimeObserver,
31    opcode::{CodeIdx, Op, Position, UpvalueIdx},
32    upvalues::Upvalues,
33    value::{
34        Builtin, BuiltinResult, Closure, CoercionKind, Lambda, NixAttrs, NixContext, NixList,
35        PointerEquality, Thunk, Value,
36    },
37    vm::generators::GenCo,
38    warnings::{EvalWarning, WarningKind},
39    NixString, SourceCode,
40};
41
42use generators::{call_functor, Generator, GeneratorState};
43
44use self::generators::{VMRequest, VMResponse};
45
46/// Internal helper trait for taking a span from a variety of types, to make use
47/// of `WithSpan` (defined below) more ergonomic at call sites.
48trait GetSpan {
49    fn get_span(self) -> Span;
50}
51
52impl<IO> GetSpan for &VM<'_, IO> {
53    fn get_span(self) -> Span {
54        self.reasonable_span
55    }
56}
57
58impl GetSpan for &CallFrame {
59    fn get_span(self) -> Span {
60        self.current_span()
61    }
62}
63
64impl GetSpan for &Span {
65    fn get_span(self) -> Span {
66        *self
67    }
68}
69
70impl GetSpan for Span {
71    fn get_span(self) -> Span {
72        self
73    }
74}
75
76/// Internal helper trait for ergonomically converting from a `Result<T,
77/// ErrorKind>` to a `Result<T, Error>` using the current span of a call frame,
78/// and chaining the VM's frame stack around it for printing a cause chain.
79trait WithSpan<T, S: GetSpan, IO> {
80    fn with_span(self, top_span: S, vm: &VM<IO>) -> Result<T, Error>;
81}
82
83impl<T, S: GetSpan, IO> WithSpan<T, S, IO> for Result<T, ErrorKind> {
84    fn with_span(self, top_span: S, vm: &VM<IO>) -> Result<T, Error> {
85        match self {
86            Ok(something) => Ok(something),
87            Err(kind) => {
88                let mut error = Error::new(kind, top_span.get_span(), vm.source.clone());
89
90                // Wrap the top-level error in chaining errors for each element
91                // of the frame stack.
92                for frame in vm.frames.iter().rev() {
93                    match frame {
94                        Frame::CallFrame { span, .. } => {
95                            error = Error::new(
96                                ErrorKind::BytecodeError(Box::new(error)),
97                                *span,
98                                vm.source.clone(),
99                            );
100                        }
101                        Frame::Generator { name, span, .. } => {
102                            error = Error::new(
103                                ErrorKind::NativeError {
104                                    err: Box::new(error),
105                                    gen_type: name,
106                                },
107                                *span,
108                                vm.source.clone(),
109                            );
110                        }
111                    }
112                }
113
114                Err(error)
115            }
116        }
117    }
118}
119
120struct CallFrame {
121    /// The lambda currently being executed.
122    lambda: Rc<Lambda>,
123
124    /// Optional captured upvalues of this frame (if a thunk or
125    /// closure if being evaluated).
126    upvalues: Rc<Upvalues>,
127
128    /// Instruction pointer to the instruction currently being
129    /// executed.
130    ip: CodeIdx,
131
132    /// Stack offset, i.e. the frames "view" into the VM's full stack.
133    stack_offset: usize,
134}
135
136impl CallFrame {
137    /// Retrieve an upvalue from this frame at the given index.
138    fn upvalue(&self, idx: UpvalueIdx) -> &Value {
139        &self.upvalues[idx]
140    }
141
142    /// Borrow the chunk of this frame's lambda.
143    fn chunk(&self) -> &Chunk {
144        &self.lambda.chunk
145    }
146
147    /// Increment this frame's instruction pointer and return the operation that
148    /// the pointer moved past.
149    fn inc_ip(&mut self) -> Op {
150        debug_assert!(
151            self.ip.0 < self.chunk().code.len(),
152            "out of bounds code at IP {} in {:p}",
153            self.ip.0,
154            self.lambda
155        );
156
157        let op = self.chunk().code[self.ip.0];
158        self.ip += 1;
159        op.into()
160    }
161
162    /// Read a varint-encoded operand and return it. The frame pointer is
163    /// incremented internally.
164    fn read_uvarint(&mut self) -> u64 {
165        let (arg, size) = self.chunk().read_uvarint(self.ip.0);
166        self.ip += size;
167        arg
168    }
169
170    /// Read a fixed-size u16 and increment the frame pointer.
171    fn read_u16(&mut self) -> u16 {
172        let arg = self.chunk().read_u16(self.ip.0);
173        self.ip += 2;
174        arg
175    }
176
177    /// Construct an error result from the given ErrorKind and the source span
178    /// of the current instruction.
179    pub fn error<T, IO>(&self, vm: &VM<IO>, kind: ErrorKind) -> Result<T, Error> {
180        Err(kind).with_span(self, vm)
181    }
182
183    /// Returns the current span. This is potentially expensive and should only
184    /// be used when actually constructing an error or warning.
185    pub fn current_span(&self) -> Span {
186        self.chunk().get_span(self.ip - 1)
187    }
188}
189
190/// A frame represents an execution state of the VM. The VM has a stack of
191/// frames representing the nesting of execution inside of the VM, and operates
192/// on the frame at the top.
193///
194/// When a frame has been fully executed, it is removed from the VM's frame
195/// stack and expected to leave a result [`Value`] on the top of the stack.
196enum Frame {
197    /// CallFrame represents the execution of Snix bytecode within a thunk,
198    /// function or closure.
199    CallFrame {
200        /// The call frame itself, separated out into another type to pass it
201        /// around easily.
202        call_frame: CallFrame,
203
204        /// Span from which the call frame was launched.
205        span: Span,
206    },
207
208    /// Generator represents a frame that can yield further
209    /// instructions to the VM while its execution is being driven.
210    ///
211    /// A generator is essentially an asynchronous function that can
212    /// be suspended while waiting for the VM to do something (e.g.
213    /// thunk forcing), and resume at the same point.
214    Generator {
215        /// human-readable description of the generator,
216        name: &'static str,
217
218        /// Span from which the generator was launched.
219        span: Span,
220
221        state: GeneratorState,
222
223        /// Generator itself, which can be resumed with `.resume()`.
224        generator: Generator,
225    },
226}
227
228impl Frame {
229    pub fn span(&self) -> Span {
230        match self {
231            Frame::CallFrame { span, .. } | Frame::Generator { span, .. } => *span,
232        }
233    }
234}
235
236#[derive(Default)]
237struct ImportCache(FxHashMap<PathBuf, Value>);
238
239/// The `ImportCache` holds the `Value` resulting from `import`ing a certain
240/// file, so that the same file doesn't need to be re-evaluated multiple times.
241/// Currently the real path of the imported file (determined using
242/// [`std::fs::canonicalize()`], not to be confused with our
243/// [`crate::value::canon_path()`]) is used to identify the file,
244/// just like C++ Nix does.
245///
246/// Errors while determining the real path are currently just ignored, since we
247/// pass around some fake paths like `/__corepkgs__/fetchurl.nix`.
248///
249/// In the future, we could use something more sophisticated, like file hashes.
250/// However, a consideration is that the eval cache is observable via impurities
251/// like pointer equality and `builtins.trace`.
252impl ImportCache {
253    fn get(&self, path: PathBuf) -> Option<&Value> {
254        let path = match std::fs::canonicalize(path.as_path()).map_err(ErrorKind::from) {
255            Ok(path) => path,
256            Err(_) => path,
257        };
258        self.0.get(&path)
259    }
260
261    fn insert(&mut self, path: PathBuf, value: Value) -> Option<Value> {
262        self.0.insert(
263            match std::fs::canonicalize(path.as_path()).map_err(ErrorKind::from) {
264                Ok(path) => path,
265                Err(_) => path,
266            },
267            value,
268        )
269    }
270}
271
272struct VM<'o, IO> {
273    /// VM's frame stack, representing the execution contexts the VM is working
274    /// through. Elements are usually pushed when functions are called, or
275    /// thunks are being forced.
276    frames: Vec<Frame>,
277
278    /// The VM's top-level value stack. Within this stack, each code-executing
279    /// frame holds a "view" of the stack representing the slice of the
280    /// top-level stack that is relevant to its operation. This is done to avoid
281    /// allocating a new `Vec` for each frame's stack.
282    pub(crate) stack: Vec<Value>,
283
284    /// Stack indices (absolute indexes into `stack`) of attribute
285    /// sets from which variables should be dynamically resolved
286    /// (`with`).
287    with_stack: Vec<usize>,
288
289    /// Runtime warnings collected during evaluation.
290    warnings: Vec<EvalWarning>,
291
292    /// Import cache, mapping absolute file paths to the value that
293    /// they compile to. Note that this reuses thunks, too!
294    // TODO: should probably be based on a file hash
295    pub import_cache: ImportCache,
296
297    /// Data structure holding all source code evaluated in this VM,
298    /// used for pretty error reporting.
299    source: SourceCode,
300
301    /// Parsed Nix search path, which is used to resolve `<...>`
302    /// references.
303    nix_search_path: NixSearchPath,
304
305    /// Implementation of I/O operations used for impure builtins and
306    /// features like `import`.
307    io_handle: IO,
308
309    /// Runtime observer which can print traces of runtime operations.
310    observer: &'o mut dyn RuntimeObserver,
311
312    /// Strong reference to the globals, guaranteeing that they are
313    /// kept alive for the duration of evaluation.
314    ///
315    /// This is important because recursive builtins (specifically
316    /// `import`) hold a weak reference to the builtins, while the
317    /// original strong reference is held by the compiler which does
318    /// not exist anymore at runtime.
319    #[allow(dead_code)]
320    globals: Rc<GlobalsMap>,
321
322    /// A reasonably applicable span that can be used for errors in each
323    /// execution situation.
324    ///
325    /// The VM should update this whenever control flow changes take place (i.e.
326    /// entering or exiting a frame to yield control somewhere).
327    reasonable_span: Span,
328
329    /// This field is responsible for handling `builtins.tryEval`. When that
330    /// builtin is encountered, it sends a special message to the VM which
331    /// pushes the frame index that requested to be informed of catchable
332    /// errors in this field.
333    ///
334    /// The frame stack is then laid out like this:
335    ///
336    /// ```notrust
337    /// ┌──┬──────────────────────────┐
338    /// │ 0│ `Result`-producing frame │
339    /// ├──┼──────────────────────────┤
340    /// │-1│ `builtins.tryEval` frame │
341    /// ├──┼──────────────────────────┤
342    /// │..│ ... other frames ...     │
343    /// └──┴──────────────────────────┘
344    /// ```
345    ///
346    /// Control is yielded to the outer VM loop, which evaluates the next frame
347    /// and returns the result itself to the `builtins.tryEval` frame.
348    try_eval_frames: Vec<usize>,
349}
350
351impl<'o, IO> VM<'o, IO>
352where
353    IO: AsRef<dyn EvalIO> + 'static,
354{
355    pub fn new(
356        nix_search_path: NixSearchPath,
357        io_handle: IO,
358        observer: &'o mut dyn RuntimeObserver,
359        source: SourceCode,
360        globals: Rc<GlobalsMap>,
361        reasonable_span: Span,
362    ) -> Self {
363        Self {
364            nix_search_path,
365            io_handle,
366            observer,
367            globals,
368            reasonable_span,
369            source,
370            frames: vec![],
371            stack: vec![],
372            with_stack: vec![],
373            warnings: vec![],
374            import_cache: Default::default(),
375            try_eval_frames: vec![],
376        }
377    }
378
379    /// Push a call frame onto the frame stack.
380    fn push_call_frame(&mut self, span: Span, call_frame: CallFrame) {
381        self.frames.push(Frame::CallFrame { span, call_frame })
382    }
383
384    /// Run the VM's primary (outer) execution loop, continuing execution based
385    /// on the current frame at the top of the frame stack.
386    fn execute(mut self) -> EvalResult<RuntimeResult> {
387        while let Some(frame) = self.frames.pop() {
388            self.reasonable_span = frame.span();
389            let frame_id = self.frames.len();
390
391            match frame {
392                Frame::CallFrame { call_frame, span } => {
393                    self.observer
394                        .observe_enter_call_frame(0, &call_frame.lambda, frame_id);
395
396                    match self.execute_bytecode(span, call_frame) {
397                        Ok(true) => self.observer.observe_exit_call_frame(frame_id, &self.stack),
398                        Ok(false) => self
399                            .observer
400                            .observe_suspend_call_frame(frame_id, &self.stack),
401
402                        Err(err) => return Err(err),
403                    };
404                }
405
406                // Handle generator frames, which can request thunk forcing
407                // during their execution.
408                Frame::Generator {
409                    name,
410                    span,
411                    state,
412                    generator,
413                } => {
414                    self.observer
415                        .observe_enter_generator(frame_id, name, &self.stack);
416
417                    match self.run_generator(name, span, frame_id, state, generator, None) {
418                        Ok(true) => {
419                            self.observer
420                                .observe_exit_generator(frame_id, name, &self.stack)
421                        }
422                        Ok(false) => {
423                            self.observer
424                                .observe_suspend_generator(frame_id, name, &self.stack)
425                        }
426
427                        Err(err) => return Err(err),
428                    };
429                }
430            }
431        }
432
433        // Once no more frames are present, return the stack's top value as the
434        // result.
435        let value = self
436            .stack
437            .pop()
438            .expect("Snix bug: runtime stack empty after execution");
439        Ok(RuntimeResult {
440            value,
441            warnings: self.warnings,
442        })
443    }
444
445    /// Run the VM's inner execution loop, processing Snix bytecode from a
446    /// chunk. This function returns if:
447    ///
448    /// 1. The code has run to the end, and has left a value on the top of the
449    ///    stack. In this case, the frame is not returned to the frame stack.
450    ///
451    /// 2. The code encounters a generator, in which case the frame in its
452    ///    current state is pushed back on the stack, and the generator is left
453    ///    on top of it for the outer loop to execute.
454    ///
455    /// 3. An error is encountered.
456    ///
457    /// This function *must* ensure that it leaves the frame stack in the
458    /// correct order, especially when re-enqueuing a frame to execute.
459    ///
460    /// The return value indicates whether the bytecode has been executed to
461    /// completion, or whether it has been suspended in favour of a generator.
462    fn execute_bytecode(&mut self, span: Span, mut frame: CallFrame) -> EvalResult<bool> {
463        loop {
464            let op = frame.inc_ip();
465            self.observer.observe_execute_op(frame.ip, &op, &self.stack);
466
467            match op {
468                Op::ThunkSuspended | Op::ThunkClosure => {
469                    let idx = frame.read_uvarint() as usize;
470
471                    let blueprint = match &frame.chunk().constants[idx] {
472                        Value::Blueprint(lambda) => lambda.clone(),
473                        _ => panic!("compiler bug: non-blueprint in blueprint slot"),
474                    };
475
476                    let upvalue_count = frame.read_uvarint();
477
478                    debug_assert!(
479                        (upvalue_count >> 1) == blueprint.upvalue_count as u64,
480                        "TODO: new upvalue count not correct",
481                    );
482
483                    let thunk = if op == Op::ThunkClosure {
484                        debug_assert!(
485                            (((upvalue_count >> 1) > 0) || (upvalue_count & 0b1 == 1)),
486                            "OpThunkClosure should not be called for plain lambdas",
487                        );
488                        Thunk::new_closure(blueprint)
489                    } else {
490                        Thunk::new_suspended(blueprint, frame.current_span())
491                    };
492                    let upvalues = thunk.upvalues_mut();
493                    self.stack.push(Value::Thunk(thunk.clone()));
494
495                    // From this point on we internally mutate the
496                    // upvalues. The closure (if `is_closure`) is
497                    // already in its stack slot, which means that it
498                    // can capture itself as an upvalue for
499                    // self-recursion.
500                    self.populate_upvalues(&mut frame, upvalue_count, upvalues)?;
501                }
502
503                Op::Force => {
504                    if let Some(Value::Thunk(_)) = self.stack.last() {
505                        let thunk = match self.stack_pop() {
506                            Value::Thunk(t) => t,
507                            _ => unreachable!(),
508                        };
509
510                        let gen_span = frame.current_span();
511
512                        self.push_call_frame(span, frame);
513                        self.enqueue_generator("force", gen_span, |co| {
514                            Thunk::force(thunk, co, gen_span)
515                        });
516
517                        return Ok(false);
518                    }
519                }
520
521                Op::GetUpvalue => {
522                    let idx = UpvalueIdx(frame.read_uvarint() as usize);
523                    let value = frame.upvalue(idx).clone();
524                    self.stack.push(value);
525                }
526
527                // Discard the current frame.
528                Op::Return => {
529                    // TODO(amjoseph): I think this should assert `==` rather
530                    // than `<=` but it fails with the stricter condition.
531                    debug_assert!(self.stack.len() - 1 <= frame.stack_offset);
532                    return Ok(true);
533                }
534
535                Op::Constant => {
536                    let idx = frame.read_uvarint() as usize;
537
538                    debug_assert!(
539                        idx < frame.chunk().constants.len(),
540                        "out of bounds constant at IP {} in {:p}",
541                        frame.ip.0,
542                        frame.lambda
543                    );
544
545                    let c = frame.chunk().constants[idx].clone();
546                    self.stack.push(c);
547                }
548
549                Op::Call => {
550                    let callable = self.stack_pop();
551                    self.call_value(frame.current_span(), Some((span, frame)), callable)?;
552
553                    // exit this loop and let the outer loop enter the new call
554                    return Ok(true);
555                }
556
557                // Remove the given number of elements from the stack,
558                // but retain the top value.
559                Op::CloseScope => {
560                    let count = frame.read_uvarint() as usize;
561                    // Immediately move the top value into the right
562                    // position.
563                    let target_idx = self.stack.len() - 1 - count;
564                    self.stack[target_idx] = self.stack_pop();
565
566                    // Then drop the remaining values.
567                    for _ in 0..(count - 1) {
568                        self.stack.pop();
569                    }
570                }
571
572                Op::Closure => {
573                    let idx = frame.read_uvarint() as usize;
574                    let blueprint = match &frame.chunk().constants[idx] {
575                        Value::Blueprint(lambda) => lambda.clone(),
576                        _ => panic!("compiler bug: non-blueprint in blueprint slot"),
577                    };
578
579                    let upvalue_count = frame.read_uvarint();
580
581                    debug_assert!(
582                        (upvalue_count >> 1) == blueprint.upvalue_count as u64,
583                        "TODO: new upvalue count not correct in closure",
584                    );
585
586                    debug_assert!(
587                        ((upvalue_count >> 1) > 0 || (upvalue_count & 0b1 == 1)),
588                        "OpClosure should not be called for plain lambdas"
589                    );
590
591                    let mut upvalues = Upvalues::with_capacity(blueprint.upvalue_count);
592                    self.populate_upvalues(&mut frame, upvalue_count, &mut upvalues)?;
593                    self.stack
594                        .push(Value::Closure(Rc::new(Closure::new_with_upvalues(
595                            Rc::new(upvalues),
596                            blueprint,
597                        ))));
598                }
599
600                Op::AttrsSelect => lifted_pop! {
601                    self(key, attrs) => {
602                        let key = key.to_str().with_span(&frame, self)?;
603                        let attrs = attrs.to_attrs().with_span(&frame, self)?;
604
605                        match attrs.select(&key) {
606                            Some(value) => self.stack.push(value.clone()),
607
608                            None => {
609                                return frame.error(
610                                    self,
611                                    ErrorKind::AttributeNotFound {
612                                        name: key.to_str_lossy().into_owned()
613                                    },
614                                );
615                            }
616                        }
617                    }
618                },
619
620                Op::JumpIfFalse => {
621                    let offset = frame.read_u16() as usize;
622                    debug_assert!(offset != 0);
623                    if !self.stack_peek(0).as_bool().with_span(&frame, self)? {
624                        frame.ip += offset;
625                    }
626                }
627
628                Op::JumpIfCatchable => {
629                    let offset = frame.read_u16() as usize;
630                    debug_assert!(offset != 0);
631                    if self.stack_peek(0).is_catchable() {
632                        frame.ip += offset;
633                    }
634                }
635
636                Op::JumpIfNoFinaliseRequest => {
637                    let offset = frame.read_u16() as usize;
638                    debug_assert!(offset != 0);
639                    match self.stack_peek(0) {
640                        Value::FinaliseRequest(finalise) => {
641                            if !finalise {
642                                frame.ip += offset;
643                            }
644                        },
645                        val => panic!("Snix bug: OpJumIfNoFinaliseRequest: expected FinaliseRequest, but got {}", val.type_of()),
646                    }
647                }
648
649                Op::Pop => {
650                    self.stack.pop();
651                }
652
653                Op::AttrsTrySelect => {
654                    let key = self.stack_pop().to_str().with_span(&frame, self)?;
655                    let value = match self.stack_pop() {
656                        Value::Attrs(attrs) => match attrs.select(&key) {
657                            Some(value) => value.clone(),
658                            None => Value::AttrNotFound,
659                        },
660
661                        _ => Value::AttrNotFound,
662                    };
663
664                    self.stack.push(value);
665                }
666
667                Op::GetLocal => {
668                    let local_idx = frame.read_uvarint() as usize;
669                    let idx = frame.stack_offset + local_idx;
670                    self.stack.push(self.stack[idx].clone());
671                }
672
673                Op::JumpIfNotFound => {
674                    let offset = frame.read_u16() as usize;
675                    debug_assert!(offset != 0);
676                    if matches!(self.stack_peek(0), Value::AttrNotFound) {
677                        self.stack_pop();
678                        frame.ip += offset;
679                    }
680                }
681
682                Op::Jump => {
683                    let offset = frame.read_u16() as usize;
684                    debug_assert!(offset != 0);
685                    frame.ip += offset;
686                }
687
688                Op::Equal => lifted_pop! {
689                    self(b, a) => {
690                        let gen_span = frame.current_span();
691                        self.push_call_frame(span, frame);
692                        self.enqueue_generator("nix_eq", gen_span, |co| {
693                            a.nix_eq_owned_genco(b, co, PointerEquality::ForbidAll, gen_span)
694                        });
695                        return Ok(false);
696                    }
697                },
698
699                // These assertion operations error out if the stack
700                // top is not of the expected type. This is necessary
701                // to implement some specific behaviours of Nix
702                // exactly.
703                Op::AssertBool => {
704                    let val = self.stack_peek(0);
705                    // TODO(edef): propagate this into is_bool, since bottom values *are* values of any type
706                    if !val.is_catchable() && !val.is_bool() {
707                        return frame.error(
708                            self,
709                            ErrorKind::TypeError {
710                                expected: "bool",
711                                actual: val.type_of(),
712                            },
713                        );
714                    }
715                }
716
717                Op::AssertAttrs => {
718                    let val = self.stack_peek(0);
719                    // TODO(edef): propagate this into is_attrs, since bottom values *are* values of any type
720                    if !val.is_catchable() && !val.is_attrs() {
721                        return frame.error(
722                            self,
723                            ErrorKind::TypeError {
724                                expected: "set",
725                                actual: val.type_of(),
726                            },
727                        );
728                    }
729                }
730
731                Op::Attrs => self.run_attrset(frame.read_uvarint() as usize, &frame)?,
732
733                Op::AttrsUpdate => lifted_pop! {
734                    self(rhs, lhs) => {
735                        let rhs = rhs.to_attrs().with_span(&frame, self)?;
736                        let lhs = lhs.to_attrs().with_span(&frame, self)?;
737                        self.stack.push(Value::attrs(lhs.update(*rhs)))
738                    }
739                },
740
741                Op::Invert => lifted_pop! {
742                    self(v) => {
743                        let v = v.as_bool().with_span(&frame, self)?;
744                        self.stack.push(Value::Bool(!v));
745                    }
746                },
747
748                Op::List => {
749                    let count = frame.read_uvarint() as usize;
750                    let list =
751                        NixList::construct(count, self.stack.split_off(self.stack.len() - count));
752
753                    self.stack.push(Value::List(list));
754                }
755
756                Op::JumpIfTrue => {
757                    let offset = frame.read_u16() as usize;
758                    debug_assert!(offset != 0);
759                    if self.stack_peek(0).as_bool().with_span(&frame, self)? {
760                        frame.ip += offset;
761                    }
762                }
763
764                Op::HasAttr => lifted_pop! {
765                    self(key, attrs) => {
766                        let key = key.to_str().with_span(&frame, self)?;
767                        let result = match attrs {
768                            Value::Attrs(attrs) => attrs.contains(&key),
769
770                            // Nix allows use of `?` on non-set types, but
771                            // always returns false in those cases.
772                            _ => false,
773                        };
774
775                        self.stack.push(Value::Bool(result));
776                    }
777                },
778
779                Op::Concat => lifted_pop! {
780                    self(rhs, lhs) => {
781                        let rhs = rhs.to_list().with_span(&frame, self)?.into_inner();
782                        let mut lhs = lhs.to_list().with_span(&frame, self)?.into_inner();
783                        lhs.extend(rhs.into_iter());
784                        self.stack.push(Value::List(lhs.into()))
785                    }
786                },
787
788                Op::ResolveWith => {
789                    let ident = self.stack_pop().to_str().with_span(&frame, self)?;
790
791                    // Re-enqueue this frame.
792                    let op_span = frame.current_span();
793                    self.push_call_frame(span, frame);
794
795                    // Construct a generator frame doing the lookup in constant
796                    // stack space.
797                    let with_stack_len = self.with_stack.len();
798                    let closed_with_stack_len = self
799                        .last_call_frame()
800                        .map(|frame| frame.upvalues.with_stack_len())
801                        .unwrap_or(0);
802
803                    self.enqueue_generator("resolve_with", op_span, |co| {
804                        resolve_with(co, ident.into(), with_stack_len, closed_with_stack_len)
805                    });
806
807                    return Ok(false);
808                }
809
810                Op::Finalise => {
811                    let idx = frame.read_uvarint() as usize;
812                    match &self.stack[frame.stack_offset + idx] {
813                        Value::Closure(_) => panic!("attempted to finalise a closure"),
814                        Value::Thunk(thunk) => thunk.finalise(&self.stack[frame.stack_offset..]),
815                        _ => panic!("attempted to finalise a non-thunk"),
816                    }
817                }
818
819                Op::CoerceToString => {
820                    let kind: CoercionKind = frame.chunk().code[frame.ip.0].into();
821                    frame.ip.0 += 1;
822
823                    let value = self.stack_pop();
824                    let gen_span = frame.current_span();
825                    self.push_call_frame(span, frame);
826
827                    self.enqueue_generator("coerce_to_string", gen_span, |co| {
828                        value.coerce_to_string(co, kind, gen_span)
829                    });
830
831                    return Ok(false);
832                }
833
834                Op::Interpolate => self.run_interpolate(frame.read_uvarint(), &frame)?,
835
836                Op::ValidateClosedFormals => {
837                    let formals = frame.lambda.formals.as_ref().expect(
838                        "OpValidateClosedFormals called within the frame of a lambda without formals",
839                    );
840
841                    let peeked = self.stack_peek(0);
842                    if peeked.is_catchable() {
843                        continue;
844                    }
845
846                    let args = peeked.to_attrs().with_span(&frame, self)?;
847                    for arg in args.keys() {
848                        if !formals.contains(arg) {
849                            return frame.error(
850                                self,
851                                ErrorKind::UnexpectedArgumentFormals {
852                                    arg: arg.clone(),
853                                    formals_span: formals.span,
854                                },
855                            );
856                        }
857                    }
858                }
859
860                Op::Add => lifted_pop! {
861                    self(b, a) => {
862                        let gen_span = frame.current_span();
863                        self.push_call_frame(span, frame);
864
865                        // OpAdd can add not just numbers, but also string-like
866                        // things, which requires more VM logic. This operation is
867                        // evaluated in a generator frame.
868                        self.enqueue_generator("add_values", gen_span, |co| add_values(co, a, b));
869                        return Ok(false);
870                    }
871                },
872
873                Op::Sub => lifted_pop! {
874                    self(b, a) => {
875                        let result = arithmetic_op!(&a, &b, -).with_span(&frame, self)?;
876                        self.stack.push(result);
877                    }
878                },
879
880                Op::Mul => lifted_pop! {
881                    self(b, a) => {
882                        let result = arithmetic_op!(&a, &b, *).with_span(&frame, self)?;
883                        self.stack.push(result);
884                    }
885                },
886
887                Op::Div => lifted_pop! {
888                    self(b, a) => {
889                        match b {
890                            Value::Integer(0) => return frame.error(self, ErrorKind::DivisionByZero),
891                            Value::Float(0.0_f64) => {
892                                return frame.error(self, ErrorKind::DivisionByZero)
893                            }
894                            _ => {}
895                        };
896
897                        let result = arithmetic_op!(&a, &b, /).with_span(&frame, self)?;
898                        self.stack.push(result);
899                    }
900                },
901
902                Op::Negate => match self.stack_pop() {
903                    Value::Integer(i) => self.stack.push(Value::Integer(-i)),
904                    Value::Float(f) => self.stack.push(Value::Float(-f)),
905                    Value::Catchable(cex) => self.stack.push(Value::Catchable(cex)),
906                    v => {
907                        return frame.error(
908                            self,
909                            ErrorKind::TypeError {
910                                expected: "number (either int or float)",
911                                actual: v.type_of(),
912                            },
913                        );
914                    }
915                },
916
917                Op::Less => cmp_op!(self, frame, span, <),
918                Op::LessOrEq => cmp_op!(self, frame, span, <=),
919                Op::More => cmp_op!(self, frame, span, >),
920                Op::MoreOrEq => cmp_op!(self, frame, span, >=),
921
922                Op::FindFile => match self.stack_pop() {
923                    Value::UnresolvedPath(path) => {
924                        let resolved = self
925                            .nix_search_path
926                            .resolve(&self.io_handle, *path)
927                            .with_span(&frame, self)?;
928                        self.stack.push(resolved.into());
929                    }
930
931                    _ => panic!("Snix bug: OpFindFile called on non-UnresolvedPath"),
932                },
933
934                Op::ResolveHomePath => match self.stack_pop() {
935                    Value::UnresolvedPath(path) => {
936                        match dirs::home_dir() {
937                            None => {
938                                return frame.error(
939                                    self,
940                                    ErrorKind::RelativePathResolution(
941                                        "failed to determine home directory".into(),
942                                    ),
943                                );
944                            }
945                            Some(mut buf) => {
946                                buf.push(*path);
947                                self.stack.push(buf.into());
948                            }
949                        };
950                    }
951
952                    _ => {
953                        panic!("Snix bug: OpResolveHomePath called on non-UnresolvedPath")
954                    }
955                },
956
957                Op::PushWith => self
958                    .with_stack
959                    .push(frame.stack_offset + frame.read_uvarint() as usize),
960
961                Op::PopWith => {
962                    self.with_stack.pop();
963                }
964
965                Op::AssertFail => {
966                    self.stack
967                        .push(Value::from(CatchableErrorKind::AssertionFailed));
968                }
969
970                // Encountering an invalid opcode is a critical error in the
971                // VM/compiler.
972                Op::Invalid => {
973                    panic!("Snix bug: attempted to execute invalid opcode")
974                }
975            }
976        }
977    }
978}
979
980/// Implementation of helper functions for the runtime logic above.
981impl<IO> VM<'_, IO>
982where
983    IO: AsRef<dyn EvalIO> + 'static,
984{
985    pub(crate) fn stack_pop(&mut self) -> Value {
986        self.stack.pop().expect("runtime stack empty")
987    }
988
989    fn stack_peek(&self, offset: usize) -> &Value {
990        &self.stack[self.stack.len() - 1 - offset]
991    }
992
993    fn run_attrset(&mut self, count: usize, frame: &CallFrame) -> EvalResult<()> {
994        let attrs = NixAttrs::construct(count, self.stack.split_off(self.stack.len() - count * 2))
995            .with_span(frame, self)?
996            .map(Value::attrs)
997            .into();
998
999        self.stack.push(attrs);
1000        Ok(())
1001    }
1002
1003    /// Access the last call frame present in the frame stack.
1004    fn last_call_frame(&self) -> Option<&CallFrame> {
1005        for frame in self.frames.iter().rev() {
1006            if let Frame::CallFrame { call_frame, .. } = frame {
1007                return Some(call_frame);
1008            }
1009        }
1010
1011        None
1012    }
1013
1014    /// Push an already constructed warning.
1015    pub fn push_warning(&mut self, warning: EvalWarning) {
1016        self.warnings.push(warning);
1017    }
1018
1019    /// Emit a warning with the given WarningKind and the source span
1020    /// of the current instruction.
1021    pub fn emit_warning(&mut self, kind: WarningKind) {
1022        self.push_warning(EvalWarning {
1023            kind,
1024            span: self.get_span(),
1025        });
1026    }
1027
1028    /// Interpolate string fragments by popping the specified number of
1029    /// fragments of the stack, evaluating them to strings, and pushing
1030    /// the concatenated result string back on the stack.
1031    fn run_interpolate(&mut self, count: u64, frame: &CallFrame) -> EvalResult<()> {
1032        let mut out = BString::default();
1033        // Interpolation propagates the context and union them.
1034        let mut context: NixContext = NixContext::new();
1035
1036        for i in 0..count {
1037            let val = self.stack_pop();
1038            if val.is_catchable() {
1039                for _ in (i + 1)..count {
1040                    self.stack.pop();
1041                }
1042                self.stack.push(val);
1043                return Ok(());
1044            }
1045            let mut nix_string = val.to_contextful_str().with_span(frame, self)?;
1046            out.push_str(nix_string.as_bstr());
1047            if let Some(nix_string_ctx) = nix_string.take_context() {
1048                context.extend(nix_string_ctx.into_iter())
1049            }
1050        }
1051
1052        self.stack
1053            .push(Value::String(NixString::new_context_from(context, out)));
1054        Ok(())
1055    }
1056
1057    /// Apply an argument from the stack to a builtin, and attempt to call it.
1058    ///
1059    /// All calls are tail-calls in Snix, as every function application is a
1060    /// separate thunk and OpCall is thus the last result in the thunk.
1061    ///
1062    /// Due to this, once control flow exits this function, the generator will
1063    /// automatically be run by the VM.
1064    fn call_builtin(&mut self, span: Span, mut builtin: Builtin) -> EvalResult<()> {
1065        let builtin_name = builtin.name();
1066        self.observer.observe_enter_builtin(builtin_name);
1067
1068        builtin.apply_arg(self.stack_pop());
1069
1070        match builtin.call() {
1071            // Partially applied builtin is just pushed back on the stack.
1072            BuiltinResult::Partial(partial) => self.stack.push(Value::Builtin(partial)),
1073
1074            // Builtin is fully applied and the generator needs to be run by the VM.
1075            BuiltinResult::Called(name, generator) => self.frames.push(Frame::Generator {
1076                generator,
1077                span,
1078                name,
1079                state: GeneratorState::Running,
1080            }),
1081        }
1082
1083        Ok(())
1084    }
1085
1086    fn call_value(
1087        &mut self,
1088        span: Span,
1089        parent: Option<(Span, CallFrame)>,
1090        callable: Value,
1091    ) -> EvalResult<()> {
1092        match callable {
1093            Value::Builtin(builtin) => self.call_builtin(span, builtin),
1094            Value::Thunk(thunk) => self.call_value(span, parent, thunk.value().clone()),
1095
1096            Value::Closure(closure) => {
1097                let lambda = closure.lambda();
1098                self.observer.observe_tail_call(self.frames.len(), &lambda);
1099
1100                // The stack offset is always `stack.len() - arg_count`, and
1101                // since this branch handles native Nix functions (which always
1102                // take only a single argument and are curried), the offset is
1103                // `stack_len - 1`.
1104                let stack_offset = self.stack.len() - 1;
1105
1106                // Reenqueue the parent frame, which should only have
1107                // `OpReturn` left. Not throwing it away leads to more
1108                // useful error traces.
1109                if let Some((parent_span, parent_frame)) = parent {
1110                    self.push_call_frame(parent_span, parent_frame);
1111                }
1112
1113                self.push_call_frame(
1114                    span,
1115                    CallFrame {
1116                        lambda,
1117                        upvalues: closure.upvalues(),
1118                        ip: CodeIdx(0),
1119                        stack_offset,
1120                    },
1121                );
1122
1123                Ok(())
1124            }
1125
1126            // Attribute sets with a __functor attribute are callable.
1127            val @ Value::Attrs(_) => {
1128                if let Some((parent_span, parent_frame)) = parent {
1129                    self.push_call_frame(parent_span, parent_frame);
1130                }
1131
1132                self.enqueue_generator("__functor call", span, |co| call_functor(co, val));
1133                Ok(())
1134            }
1135
1136            val @ Value::Catchable(_) => {
1137                // the argument that we tried to apply a catchable to
1138                self.stack.pop();
1139                // applying a `throw` to anything is still a `throw`, so we just
1140                // push it back on the stack.
1141                self.stack.push(val);
1142                Ok(())
1143            }
1144
1145            v => Err(ErrorKind::NotCallable(v.type_of())).with_span(span, self),
1146        }
1147    }
1148
1149    /// Populate the upvalue fields of a thunk or closure under construction.
1150    ///
1151    /// See the closely tied function `emit_upvalue_data` in the compiler
1152    /// implementation for details on the argument processing.
1153    fn populate_upvalues(
1154        &mut self,
1155        frame: &mut CallFrame,
1156        count: u64,
1157        mut upvalues: impl DerefMut<Target = Upvalues>,
1158    ) -> EvalResult<()> {
1159        // Determine whether to capture the with stack, and then shift the
1160        // actual count of upvalues back.
1161        let capture_with = count & 0b1 == 1;
1162        let count = count >> 1;
1163        if capture_with {
1164            // Start the captured with_stack off of the
1165            // current call frame's captured with_stack, ...
1166            let mut captured_with_stack = frame
1167                .upvalues
1168                .with_stack()
1169                .cloned()
1170                // ... or make an empty one if there isn't one already.
1171                .unwrap_or_else(|| Vec::with_capacity(self.with_stack.len()));
1172
1173            for idx in &self.with_stack {
1174                captured_with_stack.push(self.stack[*idx].clone());
1175            }
1176
1177            upvalues.deref_mut().set_with_stack(captured_with_stack);
1178        }
1179
1180        for _ in 0..count {
1181            let pos = Position(frame.read_uvarint());
1182
1183            if let Some(stack_idx) = pos.runtime_stack_index() {
1184                let idx = frame.stack_offset + stack_idx.0;
1185
1186                let val = match self.stack.get(idx) {
1187                    Some(val) => val.clone(),
1188                    None => {
1189                        return frame.error(
1190                            self,
1191                            ErrorKind::SnixBug {
1192                                msg: "upvalue to be captured was missing on stack",
1193                                metadata: Some(Rc::new(json!({
1194                                    "ip": format!("{:#x}", frame.ip.0 - 1),
1195                                    "stack_idx(relative)": stack_idx.0,
1196                                    "stack_idx(absolute)": idx,
1197                                }))),
1198                            },
1199                        );
1200                    }
1201                };
1202
1203                upvalues.deref_mut().push(val);
1204                continue;
1205            }
1206
1207            if let Some(idx) = pos.runtime_deferred_local() {
1208                upvalues.deref_mut().push(Value::DeferredUpvalue(idx));
1209                continue;
1210            }
1211
1212            if let Some(idx) = pos.runtime_upvalue_index() {
1213                upvalues.deref_mut().push(frame.upvalue(idx).clone());
1214                continue;
1215            }
1216
1217            panic!("Snix bug: invalid capture position emitted")
1218        }
1219
1220        Ok(())
1221    }
1222}
1223
1224// TODO(amjoseph): de-asyncify this
1225/// Resolve a dynamically bound identifier (through `with`) by looking
1226/// for matching values in the with-stacks carried at runtime.
1227async fn resolve_with(
1228    co: GenCo,
1229    ident: BString,
1230    vm_with_len: usize,
1231    upvalue_with_len: usize,
1232) -> Result<Value, ErrorKind> {
1233    /// Fetch and force a value on the with-stack from the VM.
1234    async fn fetch_forced_with(co: &GenCo, idx: usize) -> Value {
1235        match co.yield_(VMRequest::WithValue(idx)).await {
1236            VMResponse::Value(value) => value,
1237            msg => panic!(
1238                "Snix bug: VM responded with incorrect generator message: {}",
1239                msg
1240            ),
1241        }
1242    }
1243
1244    /// Fetch and force a value on the *captured* with-stack from the VM.
1245    async fn fetch_captured_with(co: &GenCo, idx: usize) -> Value {
1246        match co.yield_(VMRequest::CapturedWithValue(idx)).await {
1247            VMResponse::Value(value) => value,
1248            msg => panic!(
1249                "Snix bug: VM responded with incorrect generator message: {}",
1250                msg
1251            ),
1252        }
1253    }
1254
1255    for with_stack_idx in (0..vm_with_len).rev() {
1256        // TODO(tazjin): is this branch still live with the current with-thunking?
1257        let with = fetch_forced_with(&co, with_stack_idx).await;
1258
1259        if with.is_catchable() {
1260            return Ok(with);
1261        }
1262
1263        match with.to_attrs()?.select(&ident) {
1264            None => continue,
1265            Some(val) => return Ok(val.clone()),
1266        }
1267    }
1268
1269    for upvalue_with_idx in (0..upvalue_with_len).rev() {
1270        let with = fetch_captured_with(&co, upvalue_with_idx).await;
1271
1272        if with.is_catchable() {
1273            return Ok(with);
1274        }
1275
1276        match with.to_attrs()?.select(&ident) {
1277            None => continue,
1278            Some(val) => return Ok(val.clone()),
1279        }
1280    }
1281
1282    Err(ErrorKind::UnknownDynamicVariable(ident.to_string()))
1283}
1284
1285// TODO(amjoseph): de-asyncify this
1286async fn add_values(co: GenCo, a: Value, b: Value) -> Result<Value, ErrorKind> {
1287    // What we try to do is solely determined by the type of the first value!
1288    let result = match (a, b) {
1289        (Value::Path(p), v) => {
1290            let mut path = p.into_os_string();
1291            match generators::request_string_coerce(
1292                &co,
1293                v,
1294                CoercionKind {
1295                    strong: false,
1296
1297                    // Concatenating a Path with something else results in a
1298                    // Path, so we don't need to import any paths (paths
1299                    // imported by Nix always exist as a string, unless
1300                    // converted by the user). In C++ Nix they even may not
1301                    // contain any string context, the resulting error of such a
1302                    // case can not be replicated by us.
1303                    import_paths: false,
1304                    // FIXME(raitobezarius): per https://b.tvl.fyi/issues/364, this is a usecase
1305                    // for having a `reject_context: true` option here. This didn't occur yet in
1306                    // nixpkgs during my evaluations, therefore, I skipped it.
1307                },
1308            )
1309            .await
1310            {
1311                Ok(vs) => {
1312                    path.push(vs.to_os_str()?);
1313                    crate::value::canon_path(PathBuf::from(path)).into()
1314                }
1315                Err(c) => Value::Catchable(Box::new(c)),
1316            }
1317        }
1318        (Value::String(s1), Value::String(s2)) => Value::String(s1.concat(&s2)),
1319        (Value::String(s1), v) => generators::request_string_coerce(
1320            &co,
1321            v,
1322            CoercionKind {
1323                strong: false,
1324                // Behaves the same as string interpolation
1325                import_paths: true,
1326            },
1327        )
1328        .await
1329        .map(|s2| Value::String(s1.concat(&s2)))
1330        .into(),
1331        (a @ Value::Integer(_), b) | (a @ Value::Float(_), b) => arithmetic_op!(&a, &b, +)?,
1332        (a, b) => {
1333            let r1 = generators::request_string_coerce(
1334                &co,
1335                a,
1336                CoercionKind {
1337                    strong: false,
1338                    import_paths: false,
1339                },
1340            )
1341            .await;
1342            let r2 = generators::request_string_coerce(
1343                &co,
1344                b,
1345                CoercionKind {
1346                    strong: false,
1347                    import_paths: false,
1348                },
1349            )
1350            .await;
1351            match (r1, r2) {
1352                (Ok(s1), Ok(s2)) => Value::String(s1.concat(&s2)),
1353                (Err(c), _) => return Ok(Value::from(c)),
1354                (_, Err(c)) => return Ok(Value::from(c)),
1355            }
1356        }
1357    };
1358
1359    Ok(result)
1360}
1361
1362/// The result of a VM's runtime evaluation.
1363pub struct RuntimeResult {
1364    pub value: Value,
1365    pub warnings: Vec<EvalWarning>,
1366}
1367
1368// TODO(amjoseph): de-asyncify this
1369/// Generator that retrieves the final value from the stack, and deep-forces it
1370/// before returning.
1371async fn final_deep_force(co: GenCo) -> Result<Value, ErrorKind> {
1372    let value = generators::request_stack_pop(&co).await;
1373    Ok(generators::request_deep_force(&co, value).await)
1374}
1375
1376/// Specification for how to handle top-level values returned by evaluation
1377#[derive(Debug, Clone, Copy, Default)]
1378pub enum EvalMode {
1379    /// The default. Values are returned from evaluations as-is, without any extra forcing or
1380    /// special handling.
1381    #[default]
1382    Lazy,
1383
1384    /// Strictly and deeply evaluate top-level values returned by evaluation.
1385    Strict,
1386}
1387
1388pub fn run_lambda<IO>(
1389    nix_search_path: NixSearchPath,
1390    io_handle: IO,
1391    observer: &mut dyn RuntimeObserver,
1392    source: SourceCode,
1393    globals: Rc<GlobalsMap>,
1394    lambda: Rc<Lambda>,
1395    mode: EvalMode,
1396) -> EvalResult<RuntimeResult>
1397where
1398    IO: AsRef<dyn EvalIO> + 'static,
1399{
1400    // Retain the top-level span of the expression in this lambda, as
1401    // synthetic "calls" in deep_force will otherwise not have a span
1402    // to fall back to.
1403    //
1404    // We exploit the fact that the compiler emits a final instruction
1405    // with the span of the entire file for top-level expressions.
1406    let root_span = lambda.chunk.get_span(CodeIdx(lambda.chunk.code.len() - 1));
1407
1408    let mut vm = VM::new(
1409        nix_search_path,
1410        io_handle,
1411        observer,
1412        source,
1413        globals,
1414        root_span,
1415    );
1416
1417    // When evaluating strictly, synthesise a frame that will instruct
1418    // the VM to deep-force the final value before returning it.
1419    match mode {
1420        EvalMode::Lazy => {}
1421        EvalMode::Strict => vm.enqueue_generator("final_deep_force", root_span, final_deep_force),
1422    }
1423
1424    vm.frames.push(Frame::CallFrame {
1425        span: root_span,
1426        call_frame: CallFrame {
1427            lambda,
1428            upvalues: Rc::new(Upvalues::with_capacity(0)),
1429            ip: CodeIdx(0),
1430            stack_offset: 0,
1431        },
1432    });
1433
1434    vm.execute()
1435}