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, PathBuf},
7    rc::Rc,
8    sync::Arc,
9};
10
11use miden_core::operations::AssemblyOp;
12use miden_debug_types::{Location, SourceFile, SourceManager, SourceManagerExt, SourceSpan, Uri};
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 source_file = resolve_source_file_for_location(source_manager, loc)?;
449                    let span = SourceSpan::new(source_file.id(), loc.start..loc.end);
450                    let file_line_col = source_file.location(span);
451                    Some(ResolvedLocation {
452                        source_file,
453                        line: file_line_col.line.to_u32(),
454                        col: file_line_col.column.to_u32(),
455                        span,
456                    })
457                })
458                .as_ref(),
459            _ => None,
460        }
461    }
462}
463
464/// Resolve a source file for `location`.
465///
466/// Compiled packages may contain remapped paths such as `src/lib.rs`, while sources loaded by the
467/// VM host may be keyed by an absolute path, or may not be loaded yet at all. Prefer the source
468/// manager's existing URI table, then fall back to loading the file from disk.
469pub fn resolve_source_file_for_location(
470    source_manager: &dyn SourceManager,
471    location: &Location,
472) -> Option<Arc<SourceFile>> {
473    source_manager.get_by_uri(location.uri()).or_else(|| {
474        resolve_source_path(location.uri()).and_then(|path| source_manager.load_file(&path).ok())
475    })
476}
477
478/// Resolve a source URI to an existing local filesystem path.
479///
480/// Non-file URI schemes are left to the source manager. Relative paths are resolved against the
481/// debugger process' current directory, which DAP clients set to the launch `cwd`.
482pub fn resolve_source_path(uri: &Uri) -> Option<PathBuf> {
483    let path = match uri.scheme() {
484        None | Some("file") => Path::new(uri.path()),
485        Some(_) => return None,
486    };
487
488    existing_path(path).or_else(|| {
489        if path.is_relative() {
490            std::env::current_dir().ok().and_then(|cwd| existing_path(&cwd.join(path)))
491        } else {
492            None
493        }
494    })
495}
496
497/// Resolve a source location directly from the filesystem, returning the resolved path and line.
498pub fn resolve_location_from_filesystem(location: &Location) -> Option<(PathBuf, u32)> {
499    let path = resolve_source_path(location.uri())?;
500    let bytes = std::fs::read(&path).ok()?;
501    let start = location.start.to_usize().min(bytes.len());
502    let line = bytes[..start].iter().filter(|byte| **byte == b'\n').count() as u32 + 1;
503    Some((path, line))
504}
505
506/// Returns true for source paths emitted by compiler/runtime internals rather than user code.
507pub fn is_internal_source_uri(uri: &Uri) -> bool {
508    let path = uri.path().replace('\\', "/");
509    path.contains("/codegen/masm/intrinsics/") || path.contains("/rustlib/src/rust/library/")
510}
511
512fn existing_path(path: &Path) -> Option<PathBuf> {
513    path.exists()
514        .then(|| path.canonicalize().unwrap_or_else(|_| path.to_path_buf()))
515}
516
517#[derive(Debug, Clone)]
518pub struct ResolvedLocation {
519    pub source_file: Arc<SourceFile>,
520    // TODO(fabrio): Use LineNumber and ColumnNumber instead of raw `u32`.
521    pub line: u32,
522    pub col: u32,
523    pub span: SourceSpan,
524}
525impl fmt::Display for ResolvedLocation {
526    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
527        write!(f, "{}:{}:{}", self.source_file.uri().as_str(), self.line, self.col)
528    }
529}
530
531pub struct CurrentFrame {
532    pub procedure: Option<Rc<str>>,
533    pub location: Option<ResolvedLocation>,
534}
535
536pub struct StackTrace<'a> {
537    callstack: &'a CallStack,
538    recent: &'a VecDeque<Operation>,
539    source_manager: &'a dyn SourceManager,
540    current_frame: Option<CurrentFrame>,
541}
542
543impl<'a> StackTrace<'a> {
544    pub fn new(
545        callstack: &'a CallStack,
546        recent: &'a VecDeque<Operation>,
547        source_manager: &'a dyn SourceManager,
548    ) -> Self {
549        let current_frame = callstack.current_frame().map(|frame| {
550            let location = frame.last_resolved(source_manager).cloned();
551            let procedure = frame.procedure("");
552            CurrentFrame {
553                procedure,
554                location,
555            }
556        });
557        Self {
558            callstack,
559            recent,
560            source_manager,
561            current_frame,
562        }
563    }
564
565    pub fn current_frame(&self) -> Option<&CurrentFrame> {
566        self.current_frame.as_ref()
567    }
568}
569
570impl fmt::Display for StackTrace<'_> {
571    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
572        use std::fmt::Write;
573
574        let num_frames = self.callstack.frames.len();
575
576        writeln!(f, "\nStack Trace:")?;
577
578        for (i, frame) in self.callstack.frames.iter().enumerate() {
579            let is_top = i + 1 == num_frames;
580            let name = frame.procedure("");
581            let name = name.as_deref().unwrap_or("<unknown>");
582            if is_top {
583                write!(f, " `-> {name}")?;
584            } else {
585                write!(f, " |-> {name}")?;
586            }
587            if let Some(resolved) = frame.last_resolved(self.source_manager) {
588                write!(f, " in {resolved}")?;
589            } else {
590                write!(f, " in <unavailable>")?;
591            }
592            if is_top {
593                // Print op context
594                let context_size = frame.context.len();
595                writeln!(f, ":\n\nLast {context_size} Instructions (of current frame):")?;
596                for (i, op) in frame.context.iter().enumerate() {
597                    let is_last = i + 1 == context_size;
598                    if let Some(callee) = op.callee("") {
599                        write!(f, " |   exec.{callee}")?;
600                    } else {
601                        write!(f, " |   {}", &op.opcode())?;
602                    }
603                    if is_last {
604                        writeln!(f, "\n `-> <error occured here>")?;
605                    } else {
606                        f.write_char('\n')?;
607                    }
608                }
609
610                let context_size = self.recent.len();
611                writeln!(f, "\n\nLast {context_size} Instructions (any frame):")?;
612                for (i, op) in self.recent.iter().enumerate() {
613                    let is_last = i + 1 == context_size;
614                    if is_last {
615                        writeln!(f, " |   {}", &op)?;
616                        writeln!(f, " `-> <error occured here>")?;
617                    } else {
618                        writeln!(f, " |   {}", &op)?;
619                    }
620                }
621            } else {
622                f.write_char('\n')?;
623            }
624        }
625
626        Ok(())
627    }
628}
629
630fn demangle(name: &str) -> String {
631    let mut input = name.as_bytes();
632    let mut demangled = Vec::with_capacity(input.len() * 2);
633    rustc_demangle::demangle_stream(&mut input, &mut demangled, /* include_hash= */ false)
634        .expect("failed to write demangled identifier");
635    String::from_utf8(demangled).expect("demangled identifier contains invalid utf-8")
636}
637
638#[cfg(test)]
639mod tests {
640    use std::{cell::OnceCell, fs, path::PathBuf};
641
642    use miden_assembly::DefaultSourceManager;
643    use miden_debug_types::{ByteIndex, Location, Uri};
644
645    use super::*;
646
647    #[test]
648    fn resolves_relative_source_locations_from_filesystem() {
649        let path = test_source_path("relative");
650        fs::create_dir_all(path.parent().unwrap()).unwrap();
651        fs::write(&path, "fn main() {\n    let x = 1;\n}\n").unwrap();
652
653        let start = "fn main() {\n    ".len() as u32;
654        let location = Location::new(
655            Uri::from(path.display().to_string()),
656            ByteIndex::new(start),
657            ByteIndex::new(start + 5),
658        );
659        let detail = OpDetail::Full {
660            op: Operation::Noop,
661            location: Some(location),
662            resolved: OnceCell::new(),
663        };
664        let source_manager = DefaultSourceManager::default();
665
666        let resolved = detail.resolve(&source_manager).expect("source should resolve");
667        assert_eq!(resolved.line, 2);
668        assert!(resolved.source_file.uri().as_str().ends_with("src/lib.rs"));
669
670        fs::remove_dir_all(path.parent().unwrap().parent().unwrap()).ok();
671    }
672
673    fn test_source_path(test_name: &str) -> PathBuf {
674        PathBuf::from("target")
675            .join("debugger-source-tests")
676            .join(format!("{}-{}", test_name, std::process::id()))
677            .join("src")
678            .join("lib.rs")
679    }
680}
miden_debug_engine/debug/stacktrace.rs

miden_debug_engine/debug/
stacktrace.rs
