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

miden_debug_engine/debug/
stacktrace.rs
