miden_debug_engine/debug/
stacktrace.rs

1use std::{
2    borrow::Cow,
3    cell::{OnceCell, RefCell},
4    collections::{BTreeMap, BTreeSet, VecDeque},
5    fmt,
6    path::Path,
7    rc::Rc,
8    sync::Arc,
9};
10
11use miden_core::operations::AssemblyOp;
12use miden_debug_types::{Location, SourceFile, SourceManager, SourceManagerExt, SourceSpan};
13use miden_processor::{ContextId, operation::Operation, trace::RowIndex};
14
15use crate::exec::TraceEvent;
16
17#[derive(Copy, Clone, Debug, Eq, PartialEq)]
18pub enum ControlFlowOp {
19    Span,
20    Respan,
21    Join,
22    Split,
23    End,
24}
25
26pub struct StepInfo<'a> {
27    pub op: Option<Operation>,
28    pub control: Option<ControlFlowOp>,
29    pub asmop: Option<&'a AssemblyOp>,
30    pub clk: RowIndex,
31    pub ctx: ContextId,
32}
33
34#[derive(Debug, Clone)]
35struct SpanContext {
36    frame_index: usize,
37    location: Option<Location>,
38}
39
40pub struct CallStack {
41    trace_events: Rc<RefCell<BTreeMap<RowIndex, TraceEvent>>>,
42    contexts: BTreeSet<Rc<str>>,
43    frames: Vec<CallFrame>,
44    block_stack: Vec<Option<SpanContext>>,
45}
46impl CallStack {
47    pub fn new(trace_events: Rc<RefCell<BTreeMap<RowIndex, TraceEvent>>>) -> Self {
48        Self {
49            trace_events,
50            contexts: BTreeSet::default(),
51            frames: vec![],
52            block_stack: vec![],
53        }
54    }
55
56    /// Build a [CallStack] from pre-built frames — used in DAP client mode.
57    #[cfg(feature = "dap")]
58    pub fn from_remote_frames(frames: Vec<CallFrame>) -> Self {
59        Self {
60            trace_events: Rc::new(RefCell::new(BTreeMap::new())),
61            contexts: BTreeSet::default(),
62            frames,
63            block_stack: vec![],
64        }
65    }
66
67    pub fn stacktrace<'a>(
68        &'a self,
69        recent: &'a VecDeque<Operation>,
70        source_manager: &'a dyn SourceManager,
71    ) -> StackTrace<'a> {
72        StackTrace::new(self, recent, source_manager)
73    }
74
75    pub fn current_frame(&self) -> Option<&CallFrame> {
76        self.frames.last()
77    }
78
79    pub fn current_frame_mut(&mut self) -> Option<&mut CallFrame> {
80        self.frames.last_mut()
81    }
82
83    pub fn frames(&self) -> &[CallFrame] {
84        self.frames.as_slice()
85    }
86
87    /// Updates the call stack from `info`
88    ///
89    /// Returns the call frame exited this cycle, if any
90    pub fn next(&mut self, info: &StepInfo<'_>) -> Option<CallFrame> {
91        let procedure = info.asmop.map(|op| self.cache_procedure_name(op.context_name()));
92
93        let event = {
94            let mut trace_events = self.trace_events.borrow_mut();
95            match trace_events.first_key_value() {
96                Some((clk, _)) if *clk <= info.clk => {
97                    trace_events.pop_first().map(|(_, event)| event)
98                }
99                _ => None,
100            }
101        };
102        log::trace!(
103            "handling {:?}/{:?} at cycle {}: {:?}",
104            info.control,
105            info.op,
106            info.clk,
107            &event
108        );
109        let is_frame_start = event.is_some_and(|event| event.is_frame_start());
110        let popped_frame = self.handle_trace_event(event);
111        let is_frame_end = popped_frame.is_some();
112
113        match info.control {
114            Some(ControlFlowOp::Span) => {
115                if let Some(asmop) = info.asmop {
116                    log::debug!("{asmop:#?}");
117                    self.block_stack.push(Some(SpanContext {
118                        frame_index: self.frames.len().saturating_sub(1),
119                        location: asmop.location().cloned(),
120                    }));
121                } else {
122                    self.block_stack.push(None);
123                }
124            }
125            Some(ControlFlowOp::Join | ControlFlowOp::Split) => {
126                self.block_stack.push(None);
127            }
128            Some(ControlFlowOp::End) => {
129                self.block_stack.pop();
130            }
131            Some(ControlFlowOp::Respan) | None => {}
132        }
133
134        let Some(op) = info.op else {
135            return popped_frame;
136        };
137
138        if is_frame_start || is_frame_end {
139            return popped_frame;
140        }
141
142        // Attempt to supply procedure context from the current span context, if needed +
143        // available
144        let (procedure, asmop) = match procedure {
145            proc @ Some(_) => (proc, info.asmop.map(Cow::Borrowed)),
146            None => match self.block_stack.last() {
147                Some(Some(span_ctx)) => {
148                    let proc =
149                        self.frames.get(span_ctx.frame_index).and_then(|f| f.procedure.clone());
150                    let asmop_cow = info.asmop.map(Cow::Borrowed).or_else(|| {
151                        let context_name = proc.as_deref().unwrap_or("<unknown>").to_string();
152                        let raw_asmop = AssemblyOp::new(
153                            span_ctx.location.clone(),
154                            context_name,
155                            1,
156                            op.to_string(),
157                        );
158                        Some(Cow::Owned(raw_asmop))
159                    });
160                    (proc, asmop_cow)
161                }
162                _ => (None, info.asmop.map(Cow::Borrowed)),
163            },
164        };
165
166        // Use the current frame's procedure context, if no other more precise context is
167        // available
168        let procedure = procedure.or_else(|| self.frames.last().and_then(|f| f.procedure.clone()));
169
170        // Do we have a frame? If not, create one
171        if self.frames.is_empty() {
172            self.frames.push(CallFrame::new(procedure.clone()));
173        }
174
175        let current_frame = self.frames.last_mut().unwrap();
176
177        // Does the current frame have a procedure context/location? Use the one from this op if
178        // so
179        let procedure_context_updated = current_frame.procedure.is_none() && procedure.is_some();
180        if procedure_context_updated {
181            current_frame.procedure.clone_from(&procedure);
182        }
183
184        // Push op into call frame if this is any op other than `nop` or frame setup
185        if !matches!(op, Operation::Noop) {
186            let cycle_idx = info.asmop.map(|a| a.num_cycles()).unwrap_or(1);
187            current_frame.push(op, cycle_idx, asmop.as_deref());
188        }
189
190        // Check if we should also update the caller frame's exec detail
191        let num_frames = self.frames.len();
192        if procedure_context_updated && num_frames > 1 {
193            let caller_frame = &mut self.frames[num_frames - 2];
194            if let Some(OpDetail::Exec { callee }) = caller_frame.context.back_mut()
195                && callee.is_none()
196            {
197                *callee = procedure;
198            }
199        }
200
201        popped_frame
202    }
203
204    // Get or cache procedure name/context as `Rc<str>`
205    fn cache_procedure_name(&mut self, context_name: &str) -> Rc<str> {
206        match self.contexts.get(context_name) {
207            Some(name) => Rc::clone(name),
208            None => {
209                let name = Rc::from(context_name.to_string().into_boxed_str());
210                self.contexts.insert(Rc::clone(&name));
211                name
212            }
213        }
214    }
215
216    fn handle_trace_event(&mut self, event: Option<TraceEvent>) -> Option<CallFrame> {
217        // Do we need to handle any frame events?
218        if let Some(event) = event {
219            match event {
220                TraceEvent::FrameStart => {
221                    // Record the fact that we exec'd a new procedure in the op context
222                    if let Some(current_frame) = self.frames.last_mut() {
223                        current_frame.push_exec(None);
224                    }
225                    // The trace decorator is emitted in the caller, immediately before the exec.
226                    // Leave the new frame unnamed until the first callee op provides its context.
227                    self.frames.push(CallFrame::new(None));
228                }
229                TraceEvent::Unknown(code) => log::debug!("unknown trace event: {code}"),
230                TraceEvent::FrameEnd => {
231                    return self.frames.pop();
232                }
233                _ => (),
234            }
235        }
236        None
237    }
238}
239
240pub struct CallFrame {
241    procedure: Option<Rc<str>>,
242    context: VecDeque<OpDetail>,
243    display_name: std::cell::OnceCell<Rc<str>>,
244    finishing: bool,
245}
246impl CallFrame {
247    pub fn new(procedure: Option<Rc<str>>) -> Self {
248        Self {
249            procedure,
250            context: Default::default(),
251            display_name: Default::default(),
252            finishing: false,
253        }
254    }
255
256    /// Build a frame from remote (DAP) data — used in DAP client mode.
257    ///
258    /// The frame stores the procedure name and an optional [ResolvedLocation]
259    /// as a pre-resolved `OpDetail::Full` entry so that `last_resolved()` and
260    /// `recent()` work correctly for pane rendering.
261    #[cfg(feature = "dap")]
262    pub fn from_remote(name: Option<String>, resolved: Option<ResolvedLocation>) -> Self {
263        let procedure = name.map(|n| Rc::from(n.into_boxed_str()));
264        let mut context = VecDeque::new();
265        if let Some(loc) = resolved {
266            let cell = OnceCell::new();
267            cell.set(Some(loc)).ok();
268            context.push_back(OpDetail::Full {
269                op: miden_processor::operation::Operation::Noop,
270                location: None,
271                resolved: cell,
272            });
273        }
274        Self {
275            procedure,
276            context,
277            display_name: Default::default(),
278            finishing: false,
279        }
280    }
281
282    pub fn procedure(&self, strip_prefix: &str) -> Option<Rc<str>> {
283        self.procedure.as_ref()?;
284        let name = self.display_name.get_or_init(|| {
285            let name = self.procedure.as_deref().unwrap();
286            let name = match name.split_once("::") {
287                Some((module, rest)) if module == strip_prefix => demangle(rest),
288                _ => demangle(name),
289            };
290            Rc::from(name.into_boxed_str())
291        });
292        Some(Rc::clone(name))
293    }
294
295    pub fn push_exec(&mut self, callee: Option<Rc<str>>) {
296        if self.context.len() == 5 {
297            self.context.pop_front();
298        }
299
300        self.context.push_back(OpDetail::Exec { callee });
301    }
302
303    pub fn push(&mut self, opcode: Operation, cycle_idx: u8, op: Option<&AssemblyOp>) {
304        if cycle_idx > 1 {
305            // Should we ignore this op?
306            let skip = self.context.back().map(|detail| matches!(detail, OpDetail::Full { op, .. } | OpDetail::Basic { op } if op == &opcode)).unwrap_or(false);
307            if skip {
308                return;
309            }
310        }
311
312        if self.context.len() == 5 {
313            self.context.pop_front();
314        }
315
316        match op {
317            Some(op) => {
318                let location = op.location().cloned();
319                self.context.push_back(OpDetail::Full {
320                    op: opcode,
321                    location,
322                    resolved: Default::default(),
323                });
324            }
325            None => {
326                // If this instruction does not have a location, inherit the location
327                // of the previous op in the frame, if one is present
328                if let Some(loc) = self.context.back().map(|op| op.location().cloned()) {
329                    self.context.push_back(OpDetail::Full {
330                        op: opcode,
331                        location: loc,
332                        resolved: Default::default(),
333                    });
334                } else {
335                    self.context.push_back(OpDetail::Basic { op: opcode });
336                }
337            }
338        }
339    }
340
341    pub fn last_location(&self) -> Option<&Location> {
342        match self.context.back() {
343            Some(OpDetail::Full { location, .. }) => {
344                let loc = location.as_ref();
345                if loc.is_none() {
346                    dbg!(&self.context);
347                }
348                loc
349            }
350            Some(OpDetail::Basic { .. }) => None,
351            Some(OpDetail::Exec { .. }) => {
352                let op = self.context.iter().rev().nth(1)?;
353                op.location()
354            }
355            None => None,
356        }
357    }
358
359    pub fn last_resolved(&self, source_manager: &dyn SourceManager) -> Option<&ResolvedLocation> {
360        // Search through context in reverse order to find the most recent op with a resolvable
361        // location.
362        for op in self.context.iter().rev() {
363            if let Some(resolved) = op.resolve(source_manager) {
364                return Some(resolved);
365            }
366        }
367        None
368    }
369
370    pub fn recent(&self) -> &VecDeque<OpDetail> {
371        &self.context
372    }
373
374    #[inline(always)]
375    pub fn should_break_on_exit(&self) -> bool {
376        self.finishing
377    }
378
379    #[inline(always)]
380    pub fn break_on_exit(&mut self) {
381        self.finishing = true;
382    }
383}
384
385#[derive(Debug, Clone)]
386pub enum OpDetail {
387    Full {
388        op: Operation,
389        location: Option<Location>,
390        resolved: OnceCell<Option<ResolvedLocation>>,
391    },
392    Exec {
393        callee: Option<Rc<str>>,
394    },
395    Basic {
396        op: Operation,
397    },
398}
399impl OpDetail {
400    pub fn callee(&self, strip_prefix: &str) -> Option<Box<str>> {
401        match self {
402            Self::Exec { callee: None } => Some(Box::from("<unknown>")),
403            Self::Exec {
404                callee: Some(callee),
405            } => {
406                let name = match callee.split_once("::") {
407                    Some((module, rest)) if module == strip_prefix => demangle(rest),
408                    _ => demangle(callee),
409                };
410                Some(name.into_boxed_str())
411            }
412            _ => None,
413        }
414    }
415
416    pub fn display(&self) -> String {
417        match self {
418            Self::Full { op, .. } | Self::Basic { op } => format!("{op}"),
419            Self::Exec {
420                callee: Some(callee),
421            } => format!("exec.{callee}"),
422            Self::Exec { callee: None } => "exec.<unavailable>".to_string(),
423        }
424    }
425
426    pub fn opcode(&self) -> Operation {
427        match self {
428            Self::Full { op, .. } | Self::Basic { op } => *op,
429            Self::Exec { .. } => panic!("no opcode associated with execs"),
430        }
431    }
432
433    pub fn location(&self) -> Option<&Location> {
434        match self {
435            Self::Full { location, .. } => location.as_ref(),
436            Self::Basic { .. } | Self::Exec { .. } => None,
437        }
438    }
439
440    pub fn resolve(&self, source_manager: &dyn SourceManager) -> Option<&ResolvedLocation> {
441        match self {
442            Self::Full {
443                location: Some(loc),
444                resolved,
445                ..
446            } => resolved
447                .get_or_init(|| {
448                    let path = Path::new(loc.uri().as_str());
449                    let source_file = if path.exists() {
450                        source_manager.load_file(path).ok()?
451                    } else {
452                        source_manager.get_by_uri(loc.uri())?
453                    };
454                    let span = SourceSpan::new(source_file.id(), loc.start..loc.end);
455                    let file_line_col = source_file.location(span);
456                    Some(ResolvedLocation {
457                        source_file,
458                        line: file_line_col.line.to_u32(),
459                        col: file_line_col.column.to_u32(),
460                        span,
461                    })
462                })
463                .as_ref(),
464            _ => None,
465        }
466    }
467}
468
469#[derive(Debug, Clone)]
470pub struct ResolvedLocation {
471    pub source_file: Arc<SourceFile>,
472    // TODO(fabrio): Use LineNumber and ColumnNumber instead of raw `u32`.
473    pub line: u32,
474    pub col: u32,
475    pub span: SourceSpan,
476}
477impl fmt::Display for ResolvedLocation {
478    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
479        write!(f, "{}:{}:{}", self.source_file.uri().as_str(), self.line, self.col)
480    }
481}
482
483pub struct CurrentFrame {
484    pub procedure: Option<Rc<str>>,
485    pub location: Option<ResolvedLocation>,
486}
487
488pub struct StackTrace<'a> {
489    callstack: &'a CallStack,
490    recent: &'a VecDeque<Operation>,
491    source_manager: &'a dyn SourceManager,
492    current_frame: Option<CurrentFrame>,
493}
494
495impl<'a> StackTrace<'a> {
496    pub fn new(
497        callstack: &'a CallStack,
498        recent: &'a VecDeque<Operation>,
499        source_manager: &'a dyn SourceManager,
500    ) -> Self {
501        let current_frame = callstack.current_frame().map(|frame| {
502            let location = frame.last_resolved(source_manager).cloned();
503            let procedure = frame.procedure("");
504            CurrentFrame {
505                procedure,
506                location,
507            }
508        });
509        Self {
510            callstack,
511            recent,
512            source_manager,
513            current_frame,
514        }
515    }
516
517    pub fn current_frame(&self) -> Option<&CurrentFrame> {
518        self.current_frame.as_ref()
519    }
520}
521
522impl fmt::Display for StackTrace<'_> {
523    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
524        use std::fmt::Write;
525
526        let num_frames = self.callstack.frames.len();
527
528        writeln!(f, "\nStack Trace:")?;
529
530        for (i, frame) in self.callstack.frames.iter().enumerate() {
531            let is_top = i + 1 == num_frames;
532            let name = frame.procedure("");
533            let name = name.as_deref().unwrap_or("<unknown>");
534            if is_top {
535                write!(f, " `-> {name}")?;
536            } else {
537                write!(f, " |-> {name}")?;
538            }
539            if let Some(resolved) = frame.last_resolved(self.source_manager) {
540                write!(f, " in {resolved}")?;
541            } else {
542                write!(f, " in <unavailable>")?;
543            }
544            if is_top {
545                // Print op context
546                let context_size = frame.context.len();
547                writeln!(f, ":\n\nLast {context_size} Instructions (of current frame):")?;
548                for (i, op) in frame.context.iter().enumerate() {
549                    let is_last = i + 1 == context_size;
550                    if let Some(callee) = op.callee("") {
551                        write!(f, " |   exec.{callee}")?;
552                    } else {
553                        write!(f, " |   {}", &op.opcode())?;
554                    }
555                    if is_last {
556                        writeln!(f, "\n `-> <error occured here>")?;
557                    } else {
558                        f.write_char('\n')?;
559                    }
560                }
561
562                let context_size = self.recent.len();
563                writeln!(f, "\n\nLast {context_size} Instructions (any frame):")?;
564                for (i, op) in self.recent.iter().enumerate() {
565                    let is_last = i + 1 == context_size;
566                    if is_last {
567                        writeln!(f, " |   {}", &op)?;
568                        writeln!(f, " `-> <error occured here>")?;
569                    } else {
570                        writeln!(f, " |   {}", &op)?;
571                    }
572                }
573            } else {
574                f.write_char('\n')?;
575            }
576        }
577
578        Ok(())
579    }
580}
581
582fn demangle(name: &str) -> String {
583    let mut input = name.as_bytes();
584    let mut demangled = Vec::with_capacity(input.len() * 2);
585    rustc_demangle::demangle_stream(&mut input, &mut demangled, /* include_hash= */ false)
586        .expect("failed to write demangled identifier");
587    String::from_utf8(demangled).expect("demangled identifier contains invalid utf-8")
588}
miden_debug_engine/debug/stacktrace.rs

miden_debug_engine/debug/
stacktrace.rs
