miden_debug/exec/
executor.rs

1use std::{
2    cell::{Cell, RefCell},
3    collections::{BTreeMap, VecDeque},
4    fmt,
5    ops::Deref,
6    rc::Rc,
7    sync::Arc,
8};
9
10use miden_assembly_syntax::{Library, diagnostics::Report};
11use miden_core::{Program, StackInputs};
12use miden_debug_types::{SourceManager, SourceManagerExt};
13use miden_mast_package::{
14    Dependency, DependencyResolver, LocalResolvedDependency, MastArtifact,
15    MemDependencyResolverByDigest, ResolvedDependency,
16};
17use miden_processor::{
18    AdviceInputs, AdviceProvider, ExecutionError, ExecutionOptions, Felt, Process, ProcessState,
19    RowIndex, VmStateIterator,
20};
21
22use super::{DebugExecutor, DebuggerHost, ExecutionConfig, ExecutionTrace, TraceEvent};
23use crate::{debug::CallStack, felt::FromMidenRepr};
24
25/// The [Executor] is responsible for executing a program with the Miden VM.
26///
27/// It is used by either converting it into a [DebugExecutor], and using that to
28/// manage execution step-by-step, such as is done by the debugger; or by running
29/// the program to completion and obtaining an [ExecutionTrace], which can be used
30/// to introspect the final program state.
31pub struct Executor {
32    stack: StackInputs,
33    advice: AdviceInputs,
34    options: ExecutionOptions,
35    libraries: Vec<Arc<Library>>,
36    dependency_resolver: MemDependencyResolverByDigest,
37}
38impl Executor {
39    /// Construct an executor with the given arguments on the operand stack
40    pub fn new(args: Vec<Felt>) -> Self {
41        let config = ExecutionConfig {
42            inputs: StackInputs::new(args).expect("invalid stack inputs"),
43            ..Default::default()
44        };
45
46        Self::from_config(config)
47    }
48
49    /// Construct an executor from the given configuration
50    ///
51    /// NOTE: The execution options for tracing/debugging will be set to true for you
52    pub fn from_config(config: ExecutionConfig) -> Self {
53        let ExecutionConfig {
54            inputs,
55            advice_inputs,
56            options,
57        } = config;
58        let options = options.with_tracing().with_debugging(true);
59        let dependency_resolver = MemDependencyResolverByDigest::default();
60
61        Self {
62            stack: inputs,
63            advice: advice_inputs,
64            options,
65            libraries: Default::default(),
66            dependency_resolver,
67        }
68    }
69
70    /// Construct the executor with the given inputs and adds dependencies from the given package
71    pub fn for_package<I>(package: &miden_mast_package::Package, args: I) -> Result<Self, Report>
72    where
73        I: IntoIterator<Item = Felt>,
74    {
75        use miden_assembly_syntax::DisplayHex;
76        log::debug!(
77            "creating executor for package '{}' (digest={})",
78            package.name,
79            DisplayHex::new(&package.digest().as_bytes())
80        );
81        let mut exec = Self::new(args.into_iter().collect());
82        let dependencies = package.manifest.dependencies();
83        exec.with_dependencies(dependencies)?;
84        log::debug!("executor created");
85        Ok(exec)
86    }
87
88    /// Adds dependencies to the executor
89    pub fn with_dependencies<'a>(
90        &mut self,
91        dependencies: impl Iterator<Item = &'a Dependency>,
92    ) -> Result<&mut Self, Report> {
93        for dep in dependencies {
94            match self.dependency_resolver.resolve(dep) {
95                Some(resolution) => {
96                    log::debug!("dependency {dep:?} resolved to {resolution:?}");
97                    log::debug!("loading library from package dependency: {dep:?}");
98                    match resolution {
99                        ResolvedDependency::Local(LocalResolvedDependency::Library(lib)) => {
100                            self.with_library(lib);
101                        }
102                        ResolvedDependency::Local(LocalResolvedDependency::Package(pkg)) => {
103                            if let MastArtifact::Library(lib) = &pkg.mast {
104                                self.with_library(lib.clone());
105                            } else {
106                                Err(Report::msg(format!(
107                                    "expected package {} to contain library",
108                                    pkg.name
109                                )))?;
110                            }
111                        }
112                    }
113                }
114                None => panic!("{dep:?} not found in resolver"),
115            }
116        }
117
118        log::debug!("executor created");
119
120        Ok(self)
121    }
122
123    /// Set the contents of memory for the shadow stack frame of the entrypoint
124    pub fn with_advice_inputs(&mut self, advice: AdviceInputs) -> &mut Self {
125        self.advice.extend(advice);
126        self
127    }
128
129    /// Add a [Library] to the execution context
130    pub fn with_library(&mut self, lib: Arc<Library>) -> &mut Self {
131        self.libraries.push(lib);
132        self
133    }
134
135    /// Convert this [Executor] into a [DebugExecutor], which captures much more information
136    /// about the program being executed, and must be stepped manually.
137    pub fn into_debug(
138        mut self,
139        program: &Program,
140        source_manager: Arc<dyn SourceManager>,
141    ) -> DebugExecutor {
142        log::debug!("creating debug executor");
143
144        let advice_provider = AdviceProvider::from(self.advice.clone());
145        let mut host = DebuggerHost::new(advice_provider, source_manager.clone());
146        for lib in core::mem::take(&mut self.libraries) {
147            host.load_mast_forest(lib.mast_forest().clone());
148        }
149
150        let trace_events: Rc<RefCell<BTreeMap<RowIndex, TraceEvent>>> = Rc::new(Default::default());
151        let frame_start_events = Rc::clone(&trace_events);
152        host.register_trace_handler(TraceEvent::FrameStart, move |clk, event| {
153            frame_start_events.borrow_mut().insert(clk, event);
154        });
155        let frame_end_events = Rc::clone(&trace_events);
156        host.register_trace_handler(TraceEvent::FrameEnd, move |clk, event| {
157            frame_end_events.borrow_mut().insert(clk, event);
158        });
159        let assertion_events = Rc::clone(&trace_events);
160        host.register_assert_failed_tracer(move |clk, event| {
161            assertion_events.borrow_mut().insert(clk, event);
162        });
163
164        let mut process =
165            Process::new(program.kernel().clone(), self.stack, self.advice, self.options);
166        let process_state: ProcessState = (&mut process).into();
167        let root_context = process_state.ctx();
168        let result = process.execute(program, &mut host);
169        let stack_outputs = result.as_ref().map(|so| so.clone()).unwrap_or_default();
170        let iter = VmStateIterator::new(process, result);
171        let callstack = CallStack::new(trace_events);
172        DebugExecutor {
173            iter,
174            stack_outputs,
175            contexts: Default::default(),
176            root_context,
177            current_context: root_context,
178            callstack,
179            recent: VecDeque::with_capacity(5),
180            last: None,
181            cycle: 0,
182            stopped: false,
183        }
184    }
185
186    /// Execute the given program until termination, producing a trace
187    pub fn capture_trace(
188        self,
189        program: &Program,
190        source_manager: Arc<dyn SourceManager>,
191    ) -> ExecutionTrace {
192        let mut executor = self.into_debug(program, source_manager);
193        while let Some(step) = executor.next() {
194            if step.is_err() {
195                return executor.into_execution_trace();
196            }
197        }
198        executor.into_execution_trace()
199    }
200
201    /// Execute the given program, producing a trace
202    #[track_caller]
203    pub fn execute(
204        self,
205        program: &Program,
206        source_manager: Arc<dyn SourceManager>,
207    ) -> ExecutionTrace {
208        let mut executor = self.into_debug(program, source_manager.clone());
209        while let Some(step) = executor.next() {
210            if let Err(err) = step {
211                render_execution_error(err, &executor, &source_manager);
212            }
213
214            if log::log_enabled!(target: "executor", log::Level::Trace) {
215                let step = step.unwrap();
216                if let Some((op, asmop)) = step.op.as_ref().zip(step.asmop.as_ref()) {
217                    dbg!(&step.stack);
218                    let source_loc = asmop.as_ref().location().map(|loc| {
219                        let path = std::path::Path::new(loc.uri().path());
220                        let file = source_manager.load_file(path).unwrap();
221                        (file, loc.start)
222                    });
223                    if let Some((source_file, line_start)) = source_loc {
224                        let line_number = source_file.content().line_index(line_start).number();
225                        log::trace!(target: "executor", "in {} (located at {}:{})", asmop.context_name(), source_file.deref().uri().as_str(), &line_number);
226                    } else {
227                        log::trace!(target: "executor", "in {} (no source location available)", asmop.context_name());
228                    }
229                    log::trace!(target: "executor", "  executed `{op:?}` of `{}` (cycle {}/{})", asmop.op(), asmop.cycle_idx(), asmop.num_cycles());
230                    log::trace!(target: "executor", "  stack state: {:#?}", &step.stack);
231                }
232            }
233
234            /*
235            if let Some(op) = state.op {
236                match op {
237                    miden_core::Operation::MLoad => {
238                        let load_addr = last_state
239                            .as_ref()
240                            .map(|state| state.stack[0].as_int())
241                            .unwrap();
242                        let loaded = match state
243                            .memory
244                            .binary_search_by_key(&load_addr, |&(addr, _)| addr)
245                        {
246                            Ok(index) => state.memory[index].1[0].as_int(),
247                            Err(_) => 0,
248                        };
249                        //dbg!(load_addr, loaded, format!("{loaded:08x}"));
250                    }
251                    miden_core::Operation::MLoadW => {
252                        let load_addr = last_state
253                            .as_ref()
254                            .map(|state| state.stack[0].as_int())
255                            .unwrap();
256                        let loaded = match state
257                            .memory
258                            .binary_search_by_key(&load_addr, |&(addr, _)| addr)
259                        {
260                            Ok(index) => {
261                                let word = state.memory[index].1;
262                                [
263                                    word[0].as_int(),
264                                    word[1].as_int(),
265                                    word[2].as_int(),
266                                    word[3].as_int(),
267                                ]
268                            }
269                            Err(_) => [0; 4],
270                        };
271                        let loaded_bytes = {
272                            let word = loaded;
273                            let a = (word[0] as u32).to_be_bytes();
274                            let b = (word[1] as u32).to_be_bytes();
275                            let c = (word[2] as u32).to_be_bytes();
276                            let d = (word[3] as u32).to_be_bytes();
277                            let bytes = [
278                                a[0], a[1], a[2], a[3], b[0], b[1], b[2], b[3], c[0], c[1],
279                                c[2], c[3], d[0], d[1], d[2], d[3],
280                            ];
281                            u128::from_be_bytes(bytes)
282                        };
283                        //dbg!(load_addr, loaded, format!("{loaded_bytes:032x}"));
284                    }
285                    miden_core::Operation::MStore => {
286                        let store_addr = last_state
287                            .as_ref()
288                            .map(|state| state.stack[0].as_int())
289                            .unwrap();
290                        let stored = match state
291                            .memory
292                            .binary_search_by_key(&store_addr, |&(addr, _)| addr)
293                        {
294                            Ok(index) => state.memory[index].1[0].as_int(),
295                            Err(_) => 0,
296                        };
297                        //dbg!(store_addr, stored, format!("{stored:08x}"));
298                    }
299                    miden_core::Operation::MStoreW => {
300                        let store_addr = last_state
301                            .as_ref()
302                            .map(|state| state.stack[0].as_int())
303                            .unwrap();
304                        let stored = {
305                            let memory = state
306                                .memory
307                                .iter()
308                                .find_map(|(addr, word)| {
309                                    if addr == &store_addr {
310                                        Some(word)
311                                    } else {
312                                        None
313                                    }
314                                })
315                                .unwrap();
316                            let a = memory[0].as_int();
317                            let b = memory[1].as_int();
318                            let c = memory[2].as_int();
319                            let d = memory[3].as_int();
320                            [a, b, c, d]
321                        };
322                        let stored_bytes = {
323                            let word = stored;
324                            let a = (word[0] as u32).to_be_bytes();
325                            let b = (word[1] as u32).to_be_bytes();
326                            let c = (word[2] as u32).to_be_bytes();
327                            let d = (word[3] as u32).to_be_bytes();
328                            let bytes = [
329                                a[0], a[1], a[2], a[3], b[0], b[1], b[2], b[3], c[0], c[1],
330                                c[2], c[3], d[0], d[1], d[2], d[3],
331                            ];
332                            u128::from_be_bytes(bytes)
333                        };
334                        //dbg!(store_addr, stored, format!("{stored_bytes:032x}"));
335                    }
336                    _ => (),
337                }
338            }
339            */
340        }
341
342        executor.into_execution_trace()
343    }
344
345    /// Execute a program, parsing the operand stack outputs as a value of type `T`
346    pub fn execute_into<T>(self, program: &Program, source_manager: Arc<dyn SourceManager>) -> T
347    where
348        T: FromMidenRepr + PartialEq,
349    {
350        let out = self.execute(program, source_manager);
351        out.parse_result().expect("invalid result")
352    }
353
354    pub fn dependency_resolver_mut(&mut self) -> &mut MemDependencyResolverByDigest {
355        &mut self.dependency_resolver
356    }
357}
358
359#[track_caller]
360fn render_execution_error(
361    err: ExecutionError,
362    execution_state: &DebugExecutor,
363    source_manager: &dyn SourceManager,
364) -> ! {
365    use miden_assembly_syntax::diagnostics::{
366        LabeledSpan, miette::miette, reporting::PrintDiagnostic,
367    };
368
369    let stacktrace = execution_state.callstack.stacktrace(&execution_state.recent, source_manager);
370
371    eprintln!("{stacktrace}");
372
373    if let Some(last_state) = execution_state.last.as_ref() {
374        let stack = last_state.stack.iter().map(|elem| elem.as_int());
375        let stack = DisplayValues::new(stack);
376        eprintln!(
377            "\nLast Known State (at most recent instruction which succeeded):
378 | Operand Stack: [{stack}]
379 "
380        );
381
382        let mut labels = vec![];
383        if let Some(span) = stacktrace
384            .current_frame()
385            .and_then(|frame| frame.location.as_ref())
386            .map(|loc| loc.span)
387        {
388            labels.push(LabeledSpan::new_with_span(
389                None,
390                span.start().to_usize()..span.end().to_usize(),
391            ));
392        }
393        let report = miette!(
394            labels = labels,
395            "program execution failed at step {step} (cycle {cycle}): {err}",
396            step = execution_state.cycle,
397            cycle = last_state.clk,
398        );
399        let report = match stacktrace
400            .current_frame()
401            .and_then(|frame| frame.location.as_ref())
402            .map(|loc| loc.source_file.clone())
403        {
404            Some(source) => report.with_source_code(source),
405            None => report,
406        };
407
408        panic!("{}", PrintDiagnostic::new(report));
409    } else {
410        panic!("program execution failed at step {step}: {err}", step = execution_state.cycle);
411    }
412}
413
414/// Render an iterator of `T`, comma-separated
415struct DisplayValues<T>(Cell<Option<T>>);
416
417impl<T> DisplayValues<T> {
418    pub fn new(inner: T) -> Self {
419        Self(Cell::new(Some(inner)))
420    }
421}
422
423impl<T, I> fmt::Display for DisplayValues<I>
424where
425    T: fmt::Display,
426    I: Iterator<Item = T>,
427{
428    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
429        let iter = self.0.take().unwrap();
430        for (i, item) in iter.enumerate() {
431            if i == 0 {
432                write!(f, "{item}")?;
433            } else {
434                write!(f, ", {item}")?;
435            }
436        }
437        Ok(())
438    }
439}
miden_debug/exec/executor.rs

miden_debug/exec/
executor.rs
