midenc_debug/exec/
trace.rs

1use std::{
2    cell::RefCell,
3    collections::{BTreeMap, BTreeSet, VecDeque},
4    rc::Rc,
5};
6
7use miden_assembly::Library as CompiledLibrary;
8use miden_core::{Program, StackInputs, Word};
9use miden_processor::{
10    AdviceInputs, ContextId, ExecutionError, Felt, MastForest, MemAdviceProvider, Process,
11    ProcessState, RowIndex, StackOutputs, TraceLenSummary, VmState, VmStateIterator,
12};
13use midenc_codegen_masm::NativePtr;
14pub use midenc_hir::TraceEvent;
15use midenc_hir::Type;
16use midenc_session::Session;
17
18use super::Chiplets;
19use crate::{debug::CallStack, felt::PopFromStack, DebuggerHost, TestFelt};
20
21/// A callback to be executed when a [TraceEvent] occurs at a given clock cycle
22pub type TraceHandler = dyn FnMut(RowIndex, TraceEvent);
23
24/// Occurs when an attempt to read memory of the VM fails
25#[derive(Debug, thiserror::Error)]
26pub enum MemoryReadError {
27    #[error("attempted to read beyond end of linear memory")]
28    OutOfBounds,
29    #[error("unaligned reads are not supported yet")]
30    UnalignedRead,
31}
32
33/// An [ExecutionTrace] represents a final state of a program that was executed.
34///
35/// It can be used to examine the program results, and the memory of the program at
36/// any cycle up to the last cycle. It is typically used for those purposes once
37/// execution of a program terminates.
38pub struct ExecutionTrace {
39    pub(super) root_context: ContextId,
40    pub(super) last_cycle: RowIndex,
41    pub(super) chiplets: Chiplets,
42    pub(super) outputs: StackOutputs,
43    pub(super) trace_len_summary: TraceLenSummary,
44}
45
46impl ExecutionTrace {
47    /// Parse the program outputs on the operand stack as a value of type `T`
48    pub fn parse_result<T>(&self) -> Option<T>
49    where
50        T: PopFromStack,
51    {
52        let mut stack =
53            VecDeque::from_iter(self.outputs.clone().stack().iter().copied().map(TestFelt));
54        T::try_pop(&mut stack)
55    }
56
57    /// Consume the [ExecutionTrace], extracting just the outputs on the operand stack
58    #[inline]
59    pub fn into_outputs(self) -> StackOutputs {
60        self.outputs
61    }
62
63    /// Return a reference to the operand stack outputs
64    #[inline]
65    pub fn outputs(&self) -> &StackOutputs {
66        &self.outputs
67    }
68
69    /// Return a reference to the trace length summary
70    #[inline]
71    pub fn trace_len_summary(&self) -> &TraceLenSummary {
72        &self.trace_len_summary
73    }
74
75    /// Read the word at the given Miden memory address
76    pub fn read_memory_word(&self, addr: u32) -> Option<Word> {
77        self.read_memory_word_in_context(addr, self.root_context, self.last_cycle)
78    }
79
80    /// Read the word at the given Miden memory address, under `ctx`, at cycle `clk`
81    pub fn read_memory_word_in_context(
82        &self,
83        addr: u32,
84        ctx: ContextId,
85        clk: RowIndex,
86    ) -> Option<Word> {
87        use miden_core::FieldElement;
88
89        let words = self.chiplets.get_mem_state_at(ctx, clk);
90        let addr = addr as u64;
91        match words.binary_search_by_key(&addr, |item| item.0) {
92            Ok(index) => Some(words[index].1),
93            Err(_) => Some([Felt::ZERO; 4]),
94        }
95    }
96
97    /// Read the word at the given Miden memory address and element offset
98    #[track_caller]
99    pub fn read_memory_element(&self, addr: u32, index: u8) -> Option<Felt> {
100        self.read_memory_element_in_context(addr, index, self.root_context, self.last_cycle)
101    }
102
103    /// Read the word at the given Miden memory address and element offset, under `ctx`, at cycle
104    /// `clk`
105    #[track_caller]
106    pub fn read_memory_element_in_context(
107        &self,
108        addr: u32,
109        index: u8,
110        ctx: ContextId,
111        clk: RowIndex,
112    ) -> Option<Felt> {
113        assert!(index < 4, "invalid element index");
114        self.read_memory_word_in_context(addr, ctx, clk)
115            .map(|word| word[index as usize])
116    }
117
118    /// Read a raw byte vector from `addr`, under `ctx`, at cycle `clk`, sufficient to hold a value
119    /// of type `ty`
120    pub fn read_bytes_for_type(
121        &self,
122        addr: NativePtr,
123        ty: &Type,
124        ctx: ContextId,
125        clk: RowIndex,
126    ) -> Result<Vec<u8>, MemoryReadError> {
127        const U32_MASK: u64 = u32::MAX as u64;
128        let size = ty.size_in_bytes();
129        let mut buf = Vec::with_capacity(size);
130
131        let size_in_words = ty.size_in_words();
132        let mut elems = Vec::with_capacity(size_in_words);
133
134        if addr.is_word_aligned() {
135            for i in 0..size_in_words {
136                let addr = addr.waddr.checked_add(i as u32).ok_or(MemoryReadError::OutOfBounds)?;
137                elems.extend(self.read_memory_word_in_context(addr, ctx, clk).unwrap_or_default());
138            }
139        } else if addr.is_element_aligned() {
140            let leading =
141                self.read_memory_word_in_context(addr.waddr, ctx, clk).unwrap_or_default();
142            for item in leading.into_iter().skip(addr.index as usize) {
143                elems.push(item);
144            }
145            for i in 1..size_in_words {
146                let addr = addr.waddr.checked_add(i as u32).ok_or(MemoryReadError::OutOfBounds)?;
147                elems.extend(self.read_memory_word_in_context(addr, ctx, clk).unwrap_or_default());
148            }
149            let trailing_addr = addr
150                .waddr
151                .checked_add(size_in_words as u32)
152                .ok_or(MemoryReadError::OutOfBounds)?;
153            let trailing =
154                self.read_memory_word_in_context(trailing_addr, ctx, clk).unwrap_or_default();
155            for item in trailing.into_iter().take(4 - addr.index as usize) {
156                elems.push(item);
157            }
158        } else {
159            return Err(MemoryReadError::UnalignedRead);
160        }
161
162        let mut needed = size - buf.len();
163        for elem in elems {
164            let bytes = ((elem.as_int() & U32_MASK) as u32).to_be_bytes();
165            let take = core::cmp::min(needed, 4);
166            buf.extend(&bytes[0..take]);
167            needed -= take;
168        }
169
170        Ok(buf)
171    }
172
173    /// Read a value of the given type, given an address in Rust's address space
174    #[track_caller]
175    pub fn read_from_rust_memory<T>(&self, addr: u32) -> Option<T>
176    where
177        T: core::any::Any + PopFromStack,
178    {
179        self.read_from_rust_memory_in_context(addr, self.root_context, self.last_cycle)
180    }
181
182    /// Read a value of the given type, given an address in Rust's address space, under `ctx`, at
183    /// cycle `clk`
184    #[track_caller]
185    pub fn read_from_rust_memory_in_context<T>(
186        &self,
187        addr: u32,
188        ctx: ContextId,
189        clk: RowIndex,
190    ) -> Option<T>
191    where
192        T: core::any::Any + PopFromStack,
193    {
194        use core::any::TypeId;
195
196        let ptr = NativePtr::from_ptr(addr);
197        if TypeId::of::<T>() == TypeId::of::<Felt>() {
198            assert_eq!(ptr.offset, 0, "cannot read values of type Felt from unaligned addresses");
199            let elem = self.read_memory_element_in_context(ptr.waddr, ptr.index, ctx, clk)?;
200            let mut stack = VecDeque::from([TestFelt(elem)]);
201            return Some(T::try_pop(&mut stack).unwrap_or_else(|| {
202                panic!(
203                    "could not decode a value of type {} from {}",
204                    core::any::type_name::<T>(),
205                    addr
206                )
207            }));
208        }
209        match core::mem::size_of::<T>() {
210            n if n < 4 => {
211                if (4 - ptr.offset as usize) < n {
212                    todo!("unaligned, split read")
213                }
214                let elem = self.read_memory_element_in_context(ptr.waddr, ptr.index, ctx, clk)?;
215                let elem = if ptr.offset > 0 {
216                    let mask = 2u64.pow(32 - (ptr.offset as u32 * 8)) - 1;
217                    let elem = elem.as_int() & mask;
218                    Felt::new(elem << (ptr.offset as u64 * 8))
219                } else {
220                    elem
221                };
222                let mut stack = VecDeque::from([TestFelt(elem)]);
223                Some(T::try_pop(&mut stack).unwrap_or_else(|| {
224                    panic!(
225                        "could not decode a value of type {} from {}",
226                        core::any::type_name::<T>(),
227                        addr
228                    )
229                }))
230            }
231            4 if ptr.offset > 0 => {
232                todo!("unaligned, split read")
233            }
234            4 => {
235                let elem = self.read_memory_element_in_context(ptr.waddr, ptr.index, ctx, clk)?;
236                let mut stack = VecDeque::from([TestFelt(elem)]);
237                Some(T::try_pop(&mut stack).unwrap_or_else(|| {
238                    panic!(
239                        "could not decode a value of type {} from {}",
240                        core::any::type_name::<T>(),
241                        addr
242                    )
243                }))
244            }
245            n if n <= 16 && ptr.offset > 0 => {
246                todo!("unaligned, split read")
247            }
248            n if n <= 16 => {
249                let word = self.read_memory_word_in_context(ptr.waddr, ctx, clk)?;
250                let mut stack = VecDeque::from_iter(word.into_iter().map(TestFelt));
251                Some(T::try_pop(&mut stack).unwrap_or_else(|| {
252                    panic!(
253                        "could not decode a value of type {} from {}",
254                        core::any::type_name::<T>(),
255                        addr
256                    )
257                }))
258            }
259            n => {
260                let mut buf = VecDeque::default();
261                let chunks_needed = ((n / 4) as u32) + ((n % 4) > 0) as u32;
262                if ptr.offset > 0 {
263                    todo!()
264                } else {
265                    for i in 0..chunks_needed {
266                        let abs_i = i + ptr.index as u32;
267                        let word = ptr.waddr + (abs_i / 4);
268                        let index = (abs_i % 4) as u8;
269                        let elem = self
270                            .read_memory_element_in_context(word, index, ctx, clk)
271                            .expect("invalid memory access");
272                        buf.push_back(TestFelt(elem));
273                    }
274                }
275                Some(T::try_pop(&mut buf).unwrap_or_else(|| {
276                    panic!(
277                        "could not decode a value of type {} from {}",
278                        core::any::type_name::<T>(),
279                        addr
280                    )
281                }))
282            }
283        }
284    }
285}
midenc_debug/exec/trace.rs

midenc_debug/exec/
trace.rs
