leo_interpreter/
cursor.rs

1// Copyright (C) 2019-2025 Provable Inc.
2// This file is part of the Leo library.
3
4// The Leo library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// The Leo library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with the Leo library. If not, see <https://www.gnu.org/licenses/>.
16
17use super::*;
18
19use leo_ast::{
20    AssertVariant,
21    Block,
22    CoreConstant,
23    CoreFunction,
24    DefinitionPlace,
25    Expression,
26    Function,
27    Statement,
28    Type,
29    Variant,
30    interpreter_value::{
31        AsyncExecution,
32        CoreFunctionHelper,
33        Future,
34        GlobalId,
35        StructContents,
36        SvmAddress,
37        Value,
38        evaluate_binary,
39        evaluate_core_function,
40        evaluate_unary,
41        literal_to_value,
42    },
43};
44use leo_errors::{InterpreterHalt, Result};
45use leo_passes::TypeTable;
46use leo_span::{Span, Symbol, sym};
47
48use snarkvm::prelude::{
49    Closure as SvmClosure,
50    Finalize as SvmFinalize,
51    Function as SvmFunctionParam,
52    ProgramID,
53    TestnetV0,
54};
55
56use indexmap::{IndexMap, IndexSet};
57use rand_chacha::{ChaCha20Rng, rand_core::SeedableRng};
58use std::{cmp::Ordering, collections::HashMap, mem, str::FromStr as _};
59
60pub type Closure = SvmClosure<TestnetV0>;
61pub type Finalize = SvmFinalize<TestnetV0>;
62pub type SvmFunction = SvmFunctionParam<TestnetV0>;
63
64/// Names associated to values in a function being executed.
65#[derive(Clone, Debug)]
66pub struct FunctionContext {
67    program: Symbol,
68    pub caller: SvmAddress,
69    names: HashMap<Symbol, Value>,
70    accumulated_futures: Future,
71    is_async: bool,
72}
73
74/// A stack of contexts, building with the function call stack.
75#[derive(Clone, Debug, Default)]
76pub struct ContextStack {
77    contexts: Vec<FunctionContext>,
78    current_len: usize,
79}
80
81impl ContextStack {
82    fn len(&self) -> usize {
83        self.current_len
84    }
85
86    fn push(&mut self, program: Symbol, caller: SvmAddress, is_async: bool) {
87        if self.current_len == self.contexts.len() {
88            self.contexts.push(FunctionContext {
89                program,
90                caller,
91                names: HashMap::new(),
92                accumulated_futures: Default::default(),
93                is_async,
94            });
95        }
96        self.contexts[self.current_len].accumulated_futures.0.clear();
97        self.contexts[self.current_len].names.clear();
98        self.contexts[self.current_len].caller = caller;
99        self.contexts[self.current_len].program = program;
100        self.contexts[self.current_len].is_async = is_async;
101        self.current_len += 1;
102    }
103
104    pub fn pop(&mut self) {
105        // We never actually pop the underlying Vec
106        // so we can reuse the storage of the hash
107        // tables.
108        assert!(self.len() > 0);
109        self.current_len -= 1;
110        self.contexts[self.current_len].names.clear();
111    }
112
113    /// Get the future accumulated by awaiting futures in the current function call.
114    ///
115    /// If the current code being interpreted is not in an async function, this
116    /// will of course be empty.
117    fn get_future(&mut self) -> Future {
118        assert!(self.len() > 0);
119        mem::take(&mut self.contexts[self.current_len - 1].accumulated_futures)
120    }
121
122    fn set(&mut self, symbol: Symbol, value: Value) {
123        assert!(self.current_len > 0);
124        self.last_mut().unwrap().names.insert(symbol, value);
125    }
126
127    pub fn add_future(&mut self, future: Future) {
128        assert!(self.current_len > 0);
129        self.contexts[self.current_len - 1].accumulated_futures.0.extend(future.0);
130    }
131
132    /// Are we currently in an async function?
133    fn is_async(&self) -> bool {
134        assert!(self.current_len > 0);
135        self.last().unwrap().is_async
136    }
137
138    pub fn current_program(&self) -> Option<Symbol> {
139        self.last().map(|c| c.program)
140    }
141
142    pub fn last(&self) -> Option<&FunctionContext> {
143        self.len().checked_sub(1).and_then(|i| self.contexts.get(i))
144    }
145
146    fn last_mut(&mut self) -> Option<&mut FunctionContext> {
147        self.len().checked_sub(1).and_then(|i| self.contexts.get_mut(i))
148    }
149}
150
151#[derive(Clone, Debug)]
152pub enum AleoContext {
153    Closure(Closure),
154    Function(SvmFunction),
155    Finalize(Finalize),
156}
157
158/// A Leo construct to be evauated.
159#[derive(Clone, Debug)]
160pub enum Element {
161    /// A Leo statement.
162    Statement(Statement),
163
164    /// A Leo expression.
165    Expression(Expression),
166
167    /// A Leo block.
168    ///
169    /// We have a separate variant for Leo blocks for two reasons:
170    /// 1. In a ConditionalExpression, the `then` block is stored
171    ///    as just a Block with no statement, and
172    /// 2. We need to remember if a Block came from a function body,
173    ///    so that if such a block ends, we know to push a `Unit` to
174    ///    the values stack.
175    Block {
176        block: Block,
177        function_body: bool,
178    },
179
180    AleoExecution {
181        context: Box<AleoContext>,
182        registers: IndexMap<u64, Value>,
183        instruction_index: usize,
184    },
185
186    DelayedCall(GlobalId),
187}
188
189impl Element {
190    pub fn span(&self) -> Span {
191        use Element::*;
192        match self {
193            Statement(statement) => statement.span(),
194            Expression(expression) => expression.span(),
195            Block { block, .. } => block.span(),
196            AleoExecution { .. } | DelayedCall(..) => Default::default(),
197        }
198    }
199}
200
201/// A frame of execution, keeping track of the Element next to
202/// be executed and the number of steps we've done so far.
203#[derive(Clone, Debug)]
204pub struct Frame {
205    pub step: usize,
206    pub element: Element,
207    pub user_initiated: bool,
208}
209
210#[derive(Clone, Debug)]
211pub enum FunctionVariant {
212    Leo(Function),
213    AleoClosure(Closure),
214    AleoFunction(SvmFunction),
215}
216
217/// Tracks the current execution state - a cursor into the running program.
218#[derive(Clone, Debug)]
219pub struct Cursor {
220    /// Stack of execution frames, with the one currently to be executed on top.
221    pub frames: Vec<Frame>,
222
223    /// Stack of values from evaluated expressions.
224    ///
225    /// Each time an expression completes evaluation, a value is pushed here.
226    pub values: Vec<Value>,
227
228    /// All functions (or transitions or inlines) in any program being interpreted.
229    pub functions: HashMap<GlobalId, FunctionVariant>,
230
231    /// Consts are stored here.
232    pub globals: HashMap<GlobalId, Value>,
233
234    pub user_values: HashMap<Symbol, Value>,
235
236    pub mappings: HashMap<GlobalId, HashMap<Value, Value>>,
237
238    /// For each struct type, we only need to remember the names of its members, in order.
239    pub structs: HashMap<GlobalId, IndexSet<Symbol>>,
240
241    pub futures: Vec<Future>,
242
243    pub contexts: ContextStack,
244
245    pub type_table: TypeTable,
246
247    pub signer: SvmAddress,
248
249    pub rng: ChaCha20Rng,
250
251    pub block_height: u32,
252
253    pub really_async: bool,
254
255    pub program: Option<Symbol>,
256}
257
258impl CoreFunctionHelper for Cursor {
259    fn pop_value_impl(&mut self) -> Option<Value> {
260        self.values.pop()
261    }
262
263    fn set_block_height(&mut self, height: u32) {
264        self.block_height = height;
265    }
266
267    fn lookup_mapping(&self, program: Option<Symbol>, name: Symbol) -> Option<&HashMap<Value, Value>> {
268        Cursor::lookup_mapping(self, program, name)
269    }
270
271    fn lookup_mapping_mut(&mut self, program: Option<Symbol>, name: Symbol) -> Option<&mut HashMap<Value, Value>> {
272        Cursor::lookup_mapping_mut(self, program, name)
273    }
274
275    fn rng(&mut self) -> Option<&mut ChaCha20Rng> {
276        Some(&mut self.rng)
277    }
278}
279
280impl Cursor {
281    /// `really_async` indicates we should really delay execution of async function calls until the user runs them.
282    pub fn new(really_async: bool, signer: SvmAddress, block_height: u32) -> Self {
283        Cursor {
284            frames: Default::default(),
285            values: Default::default(),
286            functions: Default::default(),
287            globals: Default::default(),
288            user_values: Default::default(),
289            mappings: Default::default(),
290            structs: Default::default(),
291            contexts: Default::default(),
292            futures: Default::default(),
293            type_table: Default::default(),
294            rng: ChaCha20Rng::from_entropy(),
295            signer,
296            block_height,
297            really_async,
298            program: None,
299        }
300    }
301
302    pub fn set_program(&mut self, program: &str) {
303        let p = program.strip_suffix(".aleo").unwrap_or(program);
304        self.program = Some(Symbol::intern(p));
305    }
306
307    pub fn current_program(&self) -> Option<Symbol> {
308        self.contexts.current_program().or(self.program)
309    }
310
311    pub fn increment_step(&mut self) {
312        let Some(Frame { step, .. }) = self.frames.last_mut() else {
313            panic!("frame expected");
314        };
315        *step += 1;
316    }
317
318    fn new_caller(&self) -> SvmAddress {
319        if let Some(function_context) = self.contexts.last() {
320            let program_id = ProgramID::<TestnetV0>::from_str(&format!("{}.aleo", function_context.program))
321                .expect("should be able to create ProgramID");
322            program_id.to_address().expect("should be able to convert to address")
323        } else {
324            self.signer
325        }
326    }
327
328    fn pop_value(&mut self) -> Result<Value> {
329        match self.values.pop() {
330            Some(v) => Ok(v),
331            None => {
332                Err(InterpreterHalt::new("value expected - this may be a bug in the Leo interpreter".to_string())
333                    .into())
334            }
335        }
336    }
337
338    fn lookup(&self, name: Symbol) -> Option<Value> {
339        if let Some(context) = self.contexts.last() {
340            let option_value =
341                context.names.get(&name).or_else(|| self.globals.get(&GlobalId { program: context.program, name }));
342            if option_value.is_some() {
343                return option_value.cloned();
344            }
345        };
346
347        self.user_values.get(&name).cloned()
348    }
349
350    pub fn lookup_mapping(&self, program: Option<Symbol>, name: Symbol) -> Option<&HashMap<Value, Value>> {
351        let Some(program) = program.or_else(|| self.current_program()) else {
352            panic!("no program for mapping lookup");
353        };
354        self.mappings.get(&GlobalId { program, name })
355    }
356
357    pub fn lookup_mapping_mut(&mut self, program: Option<Symbol>, name: Symbol) -> Option<&mut HashMap<Value, Value>> {
358        let Some(program) = program.or_else(|| self.current_program()) else {
359            panic!("no program for mapping lookup");
360        };
361        self.mappings.get_mut(&GlobalId { program, name })
362    }
363
364    fn lookup_function(&self, program: Symbol, name: Symbol) -> Option<FunctionVariant> {
365        self.functions.get(&GlobalId { program, name }).cloned()
366    }
367
368    fn set_variable(&mut self, symbol: Symbol, value: Value) {
369        if self.contexts.len() > 0 {
370            self.contexts.set(symbol, value);
371        } else {
372            self.user_values.insert(symbol, value);
373        }
374    }
375
376    /// Execute the whole step of the current Element.
377    ///
378    /// That is, perform a step, and then finish all statements and expressions that have been pushed,
379    /// until we're ready for the next step of the current Element (if there is one).
380    pub fn whole_step(&mut self) -> Result<StepResult> {
381        let frames_len = self.frames.len();
382        let initial_result = self.step()?;
383        if !initial_result.finished {
384            while self.frames.len() > frames_len {
385                self.step()?;
386            }
387        }
388        Ok(initial_result)
389    }
390
391    /// Step `over` the current Element.
392    ///
393    /// That is, continue executing until the current Element is finished.
394    pub fn over(&mut self) -> Result<StepResult> {
395        let frames_len = self.frames.len();
396        loop {
397            match self.frames.len().cmp(&frames_len) {
398                Ordering::Greater => {
399                    self.step()?;
400                }
401                Ordering::Equal => {
402                    let result = self.step()?;
403                    if result.finished {
404                        return Ok(result);
405                    }
406                }
407                Ordering::Less => {
408                    // This can happen if, for instance, a `return` was encountered,
409                    // which means we exited the function we were evaluating and the
410                    // frame stack was truncated.
411                    return Ok(StepResult { finished: true, value: None });
412                }
413            }
414        }
415    }
416
417    pub fn step_block(&mut self, block: &Block, function_body: bool, step: usize) -> bool {
418        let len = self.frames.len();
419
420        let done = match step {
421            0 => {
422                for statement in block.statements.iter().rev() {
423                    self.frames.push(Frame {
424                        element: Element::Statement(statement.clone()),
425                        step: 0,
426                        user_initiated: false,
427                    });
428                }
429                false
430            }
431            1 if function_body => {
432                self.values.push(Value::Unit);
433                self.contexts.pop();
434                true
435            }
436            1 => true,
437            _ => unreachable!(),
438        };
439
440        if done {
441            assert_eq!(len, self.frames.len());
442            self.frames.pop();
443        } else {
444            self.frames[len - 1].step += 1;
445        }
446
447        done
448    }
449
450    fn step_statement(&mut self, statement: &Statement, step: usize) -> Result<bool> {
451        let len = self.frames.len();
452
453        let mut push = |expression: &Expression| {
454            self.frames.push(Frame { element: Element::Expression(expression.clone()), step: 0, user_initiated: false })
455        };
456
457        let done = match statement {
458            Statement::Assert(assert) if step == 0 => {
459                match &assert.variant {
460                    AssertVariant::Assert(x) => push(x),
461                    AssertVariant::AssertEq(x, y) | AssertVariant::AssertNeq(x, y) => {
462                        push(y);
463                        push(x);
464                    }
465                };
466                false
467            }
468            Statement::Assert(assert) if step == 1 => {
469                match &assert.variant {
470                    AssertVariant::Assert(..) => {
471                        let value = self.pop_value()?;
472                        match value {
473                            Value::Bool(true) => {}
474                            Value::Bool(false) => halt!(assert.span(), "assert failure"),
475                            _ => tc_fail!(),
476                        }
477                    }
478                    AssertVariant::AssertEq(..) | AssertVariant::AssertNeq(..) => {
479                        let x = self.pop_value()?;
480                        let y = self.pop_value()?;
481                        let b =
482                            if matches!(assert.variant, AssertVariant::AssertEq(..)) { x.eq(&y)? } else { x.neq(&y)? };
483                        if !b {
484                            halt!(assert.span(), "assert failure");
485                        }
486                    }
487                };
488                true
489            }
490            Statement::Assign(assign) if step == 0 => {
491                push(&assign.value);
492                false
493            }
494            Statement::Assign(assign) if step == 1 => {
495                let value = self.values.pop().unwrap();
496                match &assign.place {
497                    Expression::Identifier(name) => self.set_variable(name.name, value),
498                    Expression::TupleAccess(tuple_access) => {
499                        let Expression::Identifier(identifier) = tuple_access.tuple else {
500                            halt!(assign.span(), "tuple assignments must refer to identifiers.");
501                        };
502                        let mut current_tuple = self.lookup(identifier.name).expect_tc(identifier.span())?;
503                        let Value::Tuple(tuple) = &mut current_tuple else {
504                            halt!(tuple_access.span(), "Type error: this must be a tuple.");
505                        };
506                        tuple[tuple_access.index.value()] = value;
507                        self.set_variable(identifier.name, current_tuple);
508                    }
509                    _ => halt!(assign.span(), "Invalid assignment place."),
510                }
511                true
512            }
513            Statement::Block(block) => return Ok(self.step_block(block, false, step)),
514            Statement::Conditional(conditional) if step == 0 => {
515                push(&conditional.condition);
516                false
517            }
518            Statement::Conditional(conditional) if step == 1 => {
519                match self.pop_value()? {
520                    Value::Bool(true) => self.frames.push(Frame {
521                        step: 0,
522                        element: Element::Block { block: conditional.then.clone(), function_body: false },
523                        user_initiated: false,
524                    }),
525                    Value::Bool(false) => {
526                        if let Some(otherwise) = conditional.otherwise.as_ref() {
527                            self.frames.push(Frame {
528                                step: 0,
529                                element: Element::Statement(Statement::clone(otherwise)),
530                                user_initiated: false,
531                            })
532                        }
533                    }
534                    _ => tc_fail!(),
535                };
536                false
537            }
538            Statement::Conditional(_) if step == 2 => true,
539            Statement::Const(const_) if step == 0 => {
540                push(&const_.value);
541                false
542            }
543            Statement::Const(const_) if step == 1 => {
544                let value = self.pop_value()?;
545                self.set_variable(const_.place.name, value);
546                true
547            }
548            Statement::Definition(definition) if step == 0 => {
549                push(&definition.value);
550                false
551            }
552            Statement::Definition(definition) if step == 1 => {
553                let value = self.pop_value()?;
554                match &definition.place {
555                    DefinitionPlace::Single(id) => self.set_variable(id.name, value),
556                    DefinitionPlace::Multiple(ids) => {
557                        let Value::Tuple(rhs) = value else {
558                            tc_fail!();
559                        };
560                        for (id, val) in ids.iter().zip(rhs.into_iter()) {
561                            self.set_variable(id.name, val);
562                        }
563                    }
564                }
565                true
566            }
567            Statement::Expression(expression) if step == 0 => {
568                push(&expression.expression);
569                false
570            }
571            Statement::Expression(_) if step == 1 => {
572                self.values.pop();
573                true
574            }
575            Statement::Iteration(iteration) if step == 0 => {
576                assert!(!iteration.inclusive);
577                push(&iteration.stop);
578                push(&iteration.start);
579                false
580            }
581            Statement::Iteration(iteration) => {
582                // Currently there actually isn't a syntax in Leo for inclusive ranges.
583                let stop = self.pop_value()?;
584                let start = self.pop_value()?;
585                if start.eq(&stop)? {
586                    true
587                } else {
588                    let new_start = start.inc_wrapping();
589                    self.set_variable(iteration.variable.name, start);
590                    self.frames.push(Frame {
591                        step: 0,
592                        element: Element::Block { block: iteration.block.clone(), function_body: false },
593                        user_initiated: false,
594                    });
595                    self.values.push(new_start);
596                    self.values.push(stop);
597                    false
598                }
599            }
600            Statement::Return(return_) if step == 0 => {
601                push(&return_.expression);
602                false
603            }
604            Statement::Return(_) if step == 1 => loop {
605                let last_frame = self.frames.last().expect("a frame should be present");
606                match last_frame.element {
607                    Element::Expression(Expression::Call(_)) | Element::DelayedCall(_) => {
608                        if self.contexts.is_async() {
609                            // Get rid of the Unit we previously pushed, and replace it with a Future.
610                            self.values.pop();
611                            self.values.push(Value::Future(self.contexts.get_future()));
612                        }
613                        self.contexts.pop();
614                        return Ok(true);
615                    }
616                    _ => {
617                        self.frames.pop();
618                    }
619                }
620            },
621            _ => unreachable!(),
622        };
623
624        if done {
625            assert_eq!(len, self.frames.len());
626            self.frames.pop();
627        } else {
628            self.frames[len - 1].step += 1;
629        }
630
631        Ok(done)
632    }
633
634    fn step_expression(&mut self, expression: &Expression, step: usize) -> Result<bool> {
635        let len = self.frames.len();
636
637        macro_rules! push {
638            () => {
639                |expression: &Expression| {
640                    self.frames.push(Frame {
641                        element: Element::Expression(expression.clone()),
642                        step: 0,
643                        user_initiated: false,
644                    })
645                }
646            };
647        }
648
649        if let Some(value) = match expression {
650            Expression::ArrayAccess(array) if step == 0 => {
651                push!()(&array.index);
652                push!()(&array.array);
653                None
654            }
655            Expression::ArrayAccess(array) if step == 1 => {
656                let span = array.span();
657                let index = self.pop_value()?;
658                let array = self.pop_value()?;
659
660                let to_usize = |value: &Value, s: &str| -> Result<usize> {
661                    match value {
662                        Value::U8(x) => Ok((*x).into()),
663                        Value::U16(x) => Ok((*x).into()),
664                        Value::U32(x) => (*x).try_into().expect_tc(span),
665                        Value::U64(x) => (*x).try_into().expect_tc(span),
666                        Value::U128(x) => (*x).try_into().expect_tc(span),
667                        Value::I8(x) => (*x).try_into().expect_tc(span),
668                        Value::I16(x) => (*x).try_into().expect_tc(span),
669                        Value::I32(x) => (*x).try_into().expect_tc(span),
670                        Value::I64(x) => (*x).try_into().expect_tc(span),
671                        Value::I128(x) => (*x).try_into().expect_tc(span),
672                        _ => halt!(expression.span(), "invalid {s} {index}"),
673                    }
674                };
675
676                let index_usize = to_usize(&index, "array index")?;
677                if let Value::Repeat(expr, count) = array {
678                    if index_usize < to_usize(&count, "repeat expression count")? {
679                        Some(*expr)
680                    } else {
681                        halt!(expression.span(), "array index {index_usize} is out of bounds")
682                    }
683                } else if let Value::Array(vec_array) = array {
684                    Some(vec_array.get(index_usize).expect_tc(span)?.clone())
685                } else {
686                    // Shouldn't have anything else here.
687                    tc_fail!()
688                }
689            }
690            Expression::MemberAccess(access) => match &access.inner {
691                Expression::Identifier(identifier) if identifier.name == sym::SelfLower => match access.name.name {
692                    sym::signer => Some(Value::Address(self.signer)),
693                    sym::caller => {
694                        if let Some(function_context) = self.contexts.last() {
695                            Some(Value::Address(function_context.caller))
696                        } else {
697                            Some(Value::Address(self.signer))
698                        }
699                    }
700                    _ => halt!(access.span(), "unknown member of self"),
701                },
702                Expression::Identifier(identifier) if identifier.name == sym::block => match access.name.name {
703                    sym::height => Some(Value::U32(self.block_height)),
704                    _ => halt!(access.span(), "unknown member of block"),
705                },
706
707                // Otherwise, we just have a normal struct member access.
708                _ if step == 0 => {
709                    push!()(&access.inner);
710                    None
711                }
712                _ if step == 1 => {
713                    let Some(Value::Struct(struct_)) = self.values.pop() else {
714                        tc_fail!();
715                    };
716                    let value = struct_.contents.get(&access.name.name).cloned();
717                    if value.is_none() {
718                        tc_fail!();
719                    }
720                    value
721                }
722                _ => unreachable!("we've actually covered all possible patterns above"),
723            },
724            Expression::TupleAccess(tuple_access) if step == 0 => {
725                push!()(&tuple_access.tuple);
726                None
727            }
728            Expression::TupleAccess(tuple_access) if step == 1 => {
729                let Some(value) = self.values.pop() else { tc_fail!() };
730                let Value::Tuple(tuple) = value else {
731                    halt!(tuple_access.span(), "Type error");
732                };
733                if let Some(result) = tuple.get(tuple_access.index.value()) {
734                    Some(result.clone())
735                } else {
736                    halt!(tuple_access.span(), "Tuple index out of range");
737                }
738            }
739            Expression::Array(array) if step == 0 => {
740                array.elements.iter().rev().for_each(push!());
741                None
742            }
743            Expression::Array(array) if step == 1 => {
744                let len = self.values.len();
745                let array_values = self.values.drain(len - array.elements.len()..).collect();
746                Some(Value::Array(array_values))
747            }
748            Expression::Repeat(repeat) if step == 0 => {
749                push!()(&repeat.count);
750                push!()(&repeat.expr);
751                None
752            }
753            Expression::Repeat(_) if step == 1 => {
754                let count = self.pop_value()?;
755                let expr = self.pop_value()?;
756                Some(Value::Repeat(Box::new(expr), Box::new(count)))
757            }
758            Expression::AssociatedConstant(constant) if step == 0 => {
759                let Type::Identifier(type_ident) = constant.ty else {
760                    tc_fail!();
761                };
762                let Some(core_constant) = CoreConstant::from_symbols(type_ident.name, constant.name.name) else {
763                    halt!(constant.span(), "Unknown constant {constant}");
764                };
765                match core_constant {
766                    CoreConstant::GroupGenerator => Some(Value::generator()),
767                }
768            }
769            Expression::AssociatedFunction(function) if step == 0 => {
770                let Some(core_function) = CoreFunction::from_symbols(function.variant.name, function.name.name) else {
771                    halt!(function.span(), "Unkown core function {function}");
772                };
773
774                // We want to push expressions for each of the arguments... except for mappings,
775                // because we don't look them up as Values.
776                match core_function {
777                    CoreFunction::MappingGet | CoreFunction::MappingRemove | CoreFunction::MappingContains => {
778                        push!()(&function.arguments[1]);
779                    }
780                    CoreFunction::MappingGetOrUse | CoreFunction::MappingSet => {
781                        push!()(&function.arguments[2]);
782                        push!()(&function.arguments[1]);
783                    }
784                    CoreFunction::CheatCodePrintMapping => {
785                        // Do nothing, as we don't need to evaluate the mapping.
786                    }
787                    _ => function.arguments.iter().rev().for_each(push!()),
788                }
789                None
790            }
791            Expression::AssociatedFunction(function) if step == 1 => {
792                let Some(core_function) = CoreFunction::from_symbols(function.variant.name, function.name.name) else {
793                    halt!(function.span(), "Unkown core function {function}");
794                };
795
796                let span = function.span();
797
798                if let CoreFunction::FutureAwait = core_function {
799                    let value = self.pop_value()?;
800                    let Value::Future(future) = value else {
801                        halt!(span, "Invalid value for await: {value}");
802                    };
803                    for async_execution in future.0 {
804                        self.values.extend(async_execution.arguments.into_iter());
805                        self.frames.push(Frame {
806                            step: 0,
807                            element: Element::DelayedCall(async_execution.function),
808                            user_initiated: false,
809                        });
810                    }
811                    // For an await, we have one extra step - first we must evaluate the delayed call.
812                    None
813                } else {
814                    let value = evaluate_core_function(self, core_function.clone(), &function.arguments, span)?;
815                    assert!(value.is_some());
816                    value
817                }
818            }
819            Expression::AssociatedFunction(function) if step == 2 => {
820                let Some(core_function) = CoreFunction::from_symbols(function.variant.name, function.name.name) else {
821                    halt!(function.span(), "Unkown core function {function}");
822                };
823                assert!(core_function == CoreFunction::FutureAwait);
824                Some(Value::Unit)
825            }
826            Expression::Binary(binary) if step == 0 => {
827                push!()(&binary.right);
828                push!()(&binary.left);
829                None
830            }
831            Expression::Binary(binary) if step == 1 => {
832                let rhs = self.pop_value()?;
833                let lhs = self.pop_value()?;
834                Some(evaluate_binary(binary.span, binary.op, &lhs, &rhs)?)
835            }
836            Expression::Call(call) if step == 0 => {
837                // Treat const generic arguments as regular inputs
838                call.arguments.iter().rev().for_each(push!());
839                call.const_arguments.iter().rev().for_each(push!());
840                None
841            }
842            Expression::Call(call) if step == 1 => {
843                let len = self.values.len();
844                let (program, name) = {
845                    let maybe_program = call.program.or_else(|| self.current_program());
846                    if let Some(program) = maybe_program {
847                        (program, call.function.name)
848                    } else {
849                        halt!(call.span, "No current program");
850                    }
851                };
852                // It's a bit cheesy to collect the arguments into a Vec first, but it's the easiest way
853                // to handle lifetimes here.
854                let arguments: Vec<Value> =
855                    self.values.drain(len - call.arguments.len() - call.const_arguments.len()..).collect();
856                self.do_call(
857                    program,
858                    name,
859                    arguments.into_iter(),
860                    false, // finalize
861                    call.span(),
862                )?;
863                None
864            }
865            Expression::Call(_call) if step == 2 => Some(self.pop_value()?),
866            Expression::Cast(cast) if step == 0 => {
867                push!()(&cast.expression);
868                None
869            }
870            Expression::Cast(cast) if step == 1 => {
871                let span = cast.span();
872                let arg = self.pop_value()?;
873                match arg.cast(&cast.type_) {
874                    Some(value) => Some(value),
875                    None => return Err(InterpreterHalt::new_spanned("cast failure".to_string(), span).into()),
876                }
877            }
878            Expression::Err(_) => todo!(),
879            Expression::Identifier(identifier) if step == 0 => {
880                Some(self.lookup(identifier.name).expect_tc(identifier.span())?)
881            }
882            Expression::Literal(literal) if step == 0 => {
883                Some(literal_to_value(literal, &self.type_table.get(&expression.id()))?)
884            }
885            Expression::Locator(_locator) => todo!(),
886            Expression::Struct(struct_) if step == 0 => {
887                struct_.members.iter().flat_map(|init| init.expression.as_ref()).for_each(push!());
888                None
889            }
890            Expression::Struct(struct_) if step == 1 => {
891                // Collect all the key/value pairs into a HashMap.
892                let mut contents_tmp = HashMap::with_capacity(struct_.members.len());
893                for initializer in struct_.members.iter() {
894                    let name = initializer.identifier.name;
895                    let value = if initializer.expression.is_some() {
896                        self.pop_value()?
897                    } else {
898                        self.lookup(name).expect_tc(struct_.span())?
899                    };
900                    contents_tmp.insert(name, value);
901                }
902
903                // And now put them into an IndexMap in the correct order.
904                let program = self.current_program().expect("there should be a current program");
905                let id = GlobalId { program, name: struct_.name.name };
906                let struct_type = self.structs.get(&id).expect_tc(struct_.span())?;
907                let contents = struct_type
908                    .iter()
909                    .map(|sym| (*sym, contents_tmp.remove(sym).expect("we just inserted this")))
910                    .collect();
911
912                Some(Value::Struct(StructContents { name: struct_.name.name, contents }))
913            }
914            Expression::Ternary(ternary) if step == 0 => {
915                push!()(&ternary.condition);
916                None
917            }
918            Expression::Ternary(ternary) if step == 1 => {
919                let condition = self.pop_value()?;
920                match condition {
921                    Value::Bool(true) => push!()(&ternary.if_true),
922                    Value::Bool(false) => push!()(&ternary.if_false),
923                    _ => halt!(ternary.span(), "Invalid type for ternary expression {ternary}"),
924                }
925                None
926            }
927            Expression::Ternary(_) if step == 2 => Some(self.pop_value()?),
928            Expression::Tuple(tuple) if step == 0 => {
929                tuple.elements.iter().rev().for_each(push!());
930                None
931            }
932            Expression::Tuple(tuple) if step == 1 => {
933                let len = self.values.len();
934                let tuple_values = self.values.drain(len - tuple.elements.len()..).collect();
935                Some(Value::Tuple(tuple_values))
936            }
937            Expression::Unary(unary) if step == 0 => {
938                push!()(&unary.receiver);
939                None
940            }
941            Expression::Unary(unary) if step == 1 => {
942                let value = self.pop_value()?;
943                Some(evaluate_unary(unary.span, unary.op, &value)?)
944            }
945            Expression::Unit(_) if step == 0 => Some(Value::Unit),
946            x => unreachable!("Unexpected expression {x}"),
947        } {
948            assert_eq!(self.frames.len(), len);
949            self.frames.pop();
950            self.values.push(value);
951            Ok(true)
952        } else {
953            self.frames[len - 1].step += 1;
954            Ok(false)
955        }
956    }
957
958    /// Execute one step of the current element.
959    ///
960    /// Many Leo constructs require multiple steps. For instance, when executing a conditional,
961    /// the first step will push the condition expression to the stack. Once that has executed
962    /// and we've returned to the conditional, we push the `then` or `otherwise` block to the
963    /// stack. Once that has executed and we've returned to the conditional, the final step
964    /// does nothing.
965    pub fn step(&mut self) -> Result<StepResult> {
966        if self.frames.is_empty() {
967            return Err(InterpreterHalt::new("no execution frames available".into()).into());
968        }
969
970        let Frame { element, step, user_initiated } = self.frames.last().expect("there should be a frame").clone();
971        match element {
972            Element::Block { block, function_body } => {
973                let finished = self.step_block(&block, function_body, step);
974                Ok(StepResult { finished, value: None })
975            }
976            Element::Statement(statement) => {
977                let finished = self.step_statement(&statement, step)?;
978                Ok(StepResult { finished, value: None })
979            }
980            Element::Expression(expression) => {
981                let finished = self.step_expression(&expression, step)?;
982                let value = match (finished, user_initiated) {
983                    (false, _) => None,
984                    (true, false) => self.values.last().cloned(),
985                    (true, true) => self.values.pop(),
986                };
987                let maybe_future = if let Some(Value::Tuple(vals)) = &value { vals.last() } else { value.as_ref() };
988
989                if let Some(Value::Future(future)) = &maybe_future {
990                    if user_initiated && !future.0.is_empty() {
991                        self.futures.push(future.clone());
992                    }
993                }
994                Ok(StepResult { finished, value })
995            }
996            Element::AleoExecution { .. } => {
997                self.step_aleo()?;
998                Ok(StepResult { finished: true, value: None })
999            }
1000            Element::DelayedCall(gid) if step == 0 => {
1001                match self.lookup_function(gid.program, gid.name).expect("function should exist") {
1002                    FunctionVariant::Leo(function) => {
1003                        assert!(function.variant == Variant::AsyncFunction);
1004                        let len = self.values.len();
1005                        let values: Vec<Value> = self.values.drain(len - function.input.len()..).collect();
1006                        self.contexts.push(
1007                            gid.program,
1008                            self.signer,
1009                            true, // is_async
1010                        );
1011                        let param_names = function.input.iter().map(|input| input.identifier.name);
1012                        for (name, value) in param_names.zip(values) {
1013                            self.set_variable(name, value);
1014                        }
1015                        self.frames.last_mut().unwrap().step = 1;
1016                        self.frames.push(Frame {
1017                            step: 0,
1018                            element: Element::Block { block: function.block.clone(), function_body: true },
1019                            user_initiated: false,
1020                        });
1021                        Ok(StepResult { finished: false, value: None })
1022                    }
1023                    FunctionVariant::AleoFunction(function) => {
1024                        let Some(finalize_f) = function.finalize_logic() else {
1025                            panic!("must have finalize logic for a delayed call");
1026                        };
1027                        let len = self.values.len();
1028                        let values_iter = self.values.drain(len - finalize_f.inputs().len()..);
1029                        self.contexts.push(
1030                            gid.program,
1031                            self.signer,
1032                            true, // is_async
1033                        );
1034                        self.frames.last_mut().unwrap().step = 1;
1035                        self.frames.push(Frame {
1036                            step: 0,
1037                            element: Element::AleoExecution {
1038                                context: AleoContext::Finalize(finalize_f.clone()).into(),
1039                                registers: values_iter.enumerate().map(|(i, v)| (i as u64, v)).collect(),
1040                                instruction_index: 0,
1041                            },
1042                            user_initiated: false,
1043                        });
1044                        Ok(StepResult { finished: false, value: None })
1045                    }
1046                    FunctionVariant::AleoClosure(..) => panic!("A call to a closure can't be delayed"),
1047                }
1048            }
1049            Element::DelayedCall(_gid) => {
1050                assert_eq!(step, 1);
1051                let value = self.values.pop();
1052                self.frames.pop();
1053                Ok(StepResult { finished: true, value })
1054            }
1055        }
1056    }
1057
1058    pub fn do_call(
1059        &mut self,
1060        function_program: Symbol,
1061        function_name: Symbol,
1062        arguments: impl Iterator<Item = Value>,
1063        finalize: bool,
1064        span: Span,
1065    ) -> Result<()> {
1066        let Some(function_variant) = self.lookup_function(function_program, function_name) else {
1067            halt!(span, "unknown function {function_program}.aleo/{function_name}");
1068        };
1069        match function_variant {
1070            FunctionVariant::Leo(function) => {
1071                let caller = if matches!(function.variant, Variant::Transition | Variant::AsyncTransition) {
1072                    self.new_caller()
1073                } else {
1074                    self.signer
1075                };
1076                if self.really_async && function.variant == Variant::AsyncFunction {
1077                    // Don't actually run the call now.
1078                    let async_ex = AsyncExecution {
1079                        function: GlobalId { name: function_name, program: function_program },
1080                        arguments: arguments.collect(),
1081                    };
1082                    self.values.push(Value::Future(Future(vec![async_ex])));
1083                } else {
1084                    let is_async = function.variant == Variant::AsyncFunction;
1085                    self.contexts.push(function_program, caller, is_async);
1086                    // Treat const generic parameters as regular inputs
1087                    let param_names = function
1088                        .const_parameters
1089                        .iter()
1090                        .map(|param| param.identifier.name)
1091                        .chain(function.input.iter().map(|input| input.identifier.name));
1092                    for (name, value) in param_names.zip(arguments) {
1093                        self.set_variable(name, value);
1094                    }
1095                    self.frames.push(Frame {
1096                        step: 0,
1097                        element: Element::Block { block: function.block.clone(), function_body: true },
1098                        user_initiated: false,
1099                    });
1100                }
1101            }
1102            FunctionVariant::AleoClosure(closure) => {
1103                self.contexts.push(function_program, self.signer, false);
1104                let context = AleoContext::Closure(closure);
1105                self.frames.push(Frame {
1106                    step: 0,
1107                    element: Element::AleoExecution {
1108                        context: context.into(),
1109                        registers: arguments.enumerate().map(|(i, v)| (i as u64, v)).collect(),
1110                        instruction_index: 0,
1111                    },
1112                    user_initiated: false,
1113                });
1114            }
1115            FunctionVariant::AleoFunction(function) => {
1116                let caller = self.new_caller();
1117                self.contexts.push(function_program, caller, false);
1118                let context = if finalize {
1119                    let Some(finalize_f) = function.finalize_logic() else {
1120                        panic!("finalize call with no finalize logic");
1121                    };
1122                    AleoContext::Finalize(finalize_f.clone())
1123                } else {
1124                    AleoContext::Function(function)
1125                };
1126                self.frames.push(Frame {
1127                    step: 0,
1128                    element: Element::AleoExecution {
1129                        context: context.into(),
1130                        registers: arguments.enumerate().map(|(i, v)| (i as u64, v)).collect(),
1131                        instruction_index: 0,
1132                    },
1133                    user_initiated: false,
1134                });
1135            }
1136        }
1137
1138        Ok(())
1139    }
1140}
1141
1142#[derive(Clone, Debug)]
1143pub struct StepResult {
1144    /// Has this element completely finished running?
1145    pub finished: bool,
1146
1147    /// If the element was an expression, here's its value.
1148    pub value: Option<Value>,
1149}