miden_debug_engine/debug/
stacktrace.rs

1use std::{
2    borrow::Cow,
3    cell::OnceCell,
4    collections::{BTreeMap, BTreeSet, VecDeque},
5    fmt,
6    path::{Path, PathBuf},
7    sync::{Arc, Mutex},
8};
9
10use miden_core::operations::AssemblyOp;
11use miden_debug_types::{Location, SourceFile, SourceManager, SourceManagerExt, SourceSpan, Uri};
12use miden_processor::{ContextId, operation::Operation, trace::RowIndex};
13
14use crate::Event;
15
16#[derive(Copy, Clone, Debug, Eq, PartialEq)]
17pub enum ControlFlowOp {
18    Span,
19    Respan,
20    Join,
21    Split,
22    End,
23}
24
25pub struct StepInfo<'a> {
26    pub op: Option<Operation>,
27    pub control: Option<ControlFlowOp>,
28    pub asmop: Option<&'a AssemblyOp>,
29    pub clk: RowIndex,
30    pub ctx: ContextId,
31}
32
33#[derive(Debug, Clone)]
34struct SpanContext {
35    frame_index: usize,
36    location: Option<Location>,
37}
38
39pub struct CallStack {
40    events: Arc<Mutex<BTreeMap<RowIndex, Event>>>,
41    contexts: BTreeSet<Arc<str>>,
42    frames: Vec<CallFrame>,
43    block_stack: Vec<Option<SpanContext>>,
44}
45impl CallStack {
46    pub fn new(events: Arc<Mutex<BTreeMap<RowIndex, Event>>>) -> Self {
47        Self {
48            events,
49            contexts: BTreeSet::default(),
50            frames: vec![],
51            block_stack: vec![],
52        }
53    }
54
55    /// Build a [CallStack] from pre-built frames — used in DAP client mode.
56    #[cfg(feature = "dap")]
57    pub fn from_remote_frames(frames: Vec<CallFrame>) -> Self {
58        Self {
59            events: Arc::new(Default::default()),
60            contexts: BTreeSet::default(),
61            frames,
62            block_stack: vec![],
63        }
64    }
65
66    pub fn stacktrace<'a>(
67        &'a self,
68        recent: &'a VecDeque<Operation>,
69        source_manager: &'a dyn SourceManager,
70    ) -> StackTrace<'a> {
71        StackTrace::new(self, recent, source_manager)
72    }
73
74    pub fn current_frame(&self) -> Option<&CallFrame> {
75        self.frames.last()
76    }
77
78    pub fn current_frame_mut(&mut self) -> Option<&mut CallFrame> {
79        self.frames.last_mut()
80    }
81
82    pub fn frames(&self) -> &[CallFrame] {
83        self.frames.as_slice()
84    }
85
86    /// Updates the call stack from `info`
87    ///
88    /// Returns the call frame exited this cycle, if any
89    pub fn next(&mut self, info: &StepInfo<'_>) -> Option<CallFrame> {
90        let procedure = info.asmop.map(|op| self.cache_procedure_name(op.context_name()));
91
92        let event = {
93            let mut events = self.events.lock().unwrap();
94            match events.first_key_value() {
95                Some((clk, _)) if *clk <= info.clk => events.pop_first().map(|(_, event)| event),
96                _ => None,
97            }
98        };
99        log::trace!("handling {:?}/{:?} at cycle {}: {:?}", info.control, info.op, info.clk, event);
100        let is_frame_start = event.as_ref().is_some_and(|event| event.is_frame_start());
101        let popped_frame = self.handle_event(event, procedure.clone(), info.op, info.asmop);
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_start || 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 `Arc<str>`
196    fn cache_procedure_name(&mut self, context_name: &str) -> Arc<str> {
197        match self.contexts.get(context_name) {
198            Some(name) => Arc::clone(name),
199            None => {
200                let name = Arc::from(context_name.to_string().into_boxed_str());
201                self.contexts.insert(Arc::clone(&name));
202                name
203            }
204        }
205    }
206
207    fn handle_event(
208        &mut self,
209        event: Option<Event>,
210        procedure: Option<Arc<str>>,
211        op: Option<Operation>,
212        asmop: Option<&AssemblyOp>,
213    ) -> Option<CallFrame> {
214        // Do we need to handle any frame events?
215        match event? {
216            Event::FrameStart => {
217                // Record the fact that we exec'd a new procedure in the op context
218                if let Some(current_frame) = self.frames.last_mut() {
219                    current_frame.push_exec(procedure.clone());
220                }
221                // The event is emitted at the start of the callee.
222                let mut frame = CallFrame::new(procedure);
223                if let Some(op) = op {
224                    frame.push(op, 0, asmop);
225                }
226                self.frames.push(frame);
227            }
228            Event::Unknown(code) => log::debug!("unknown trace event: {code}"),
229            Event::FrameEnd => {
230                return self.frames.pop();
231            }
232            _ => (),
233        }
234        None
235    }
236}
237
238pub struct CallFrame {
239    procedure: Option<Arc<str>>,
240    context: VecDeque<OpDetail>,
241    display_name: std::cell::OnceCell<Arc<str>>,
242    finishing: bool,
243}
244impl CallFrame {
245    pub fn new(procedure: Option<Arc<str>>) -> Self {
246        Self {
247            procedure,
248            context: Default::default(),
249            display_name: Default::default(),
250            finishing: false,
251        }
252    }
253
254    /// Build a frame from remote (DAP) data — used in DAP client mode.
255    ///
256    /// The frame stores the procedure name and an optional [ResolvedLocation]
257    /// as a pre-resolved `OpDetail::Full` entry so that `last_resolved()` and
258    /// `recent()` work correctly for pane rendering.
259    #[cfg(feature = "dap")]
260    pub fn from_remote(procedure: Option<Arc<str>>, resolved: Option<ResolvedLocation>) -> Self {
261        let mut context = VecDeque::new();
262        if let Some(loc) = resolved {
263            let cell = OnceCell::new();
264            cell.set(Some(loc)).ok();
265            context.push_back(OpDetail::Full {
266                op: miden_processor::operation::Operation::Noop,
267                location: None,
268                resolved: cell,
269            });
270        }
271        Self {
272            procedure,
273            context,
274            display_name: Default::default(),
275            finishing: false,
276        }
277    }
278
279    pub fn procedure(&self, strip_prefix: &str) -> Option<Arc<str>> {
280        self.procedure.as_ref()?;
281        let name = self.display_name.get_or_init(|| {
282            let name = self.procedure.as_deref().unwrap();
283            let name = match name.split_once("::") {
284                Some((module, rest)) if module == strip_prefix => demangle(rest),
285                _ => demangle(name),
286            };
287            Arc::<str>::from(name.into_boxed_str())
288        });
289        Some(Arc::clone(name))
290    }
291
292    pub fn push_exec(&mut self, callee: Option<Arc<str>>) {
293        if self.context.len() == 5 {
294            self.context.pop_front();
295        }
296
297        self.context.push_back(OpDetail::Exec { callee });
298    }
299
300    pub fn push(&mut self, opcode: Operation, cycle_idx: u8, op: Option<&AssemblyOp>) {
301        if cycle_idx > 1 {
302            // Should we ignore this op?
303            let skip = self.context.back().map(|detail| matches!(detail, OpDetail::Full { op, .. } | OpDetail::Basic { op } if op == &opcode)).unwrap_or(false);
304            if skip {
305                return;
306            }
307        }
308
309        if self.context.len() == 5 {
310            self.context.pop_front();
311        }
312
313        match op {
314            Some(op) => {
315                let location = op.location().cloned();
316                self.context.push_back(OpDetail::Full {
317                    op: opcode,
318                    location,
319                    resolved: Default::default(),
320                });
321            }
322            None => {
323                // If this instruction does not have a location, inherit the location
324                // of the previous op in the frame, if one is present
325                if let Some(loc) = self.context.back().map(|op| op.location().cloned()) {
326                    self.context.push_back(OpDetail::Full {
327                        op: opcode,
328                        location: loc,
329                        resolved: Default::default(),
330                    });
331                } else {
332                    self.context.push_back(OpDetail::Basic { op: opcode });
333                }
334            }
335        }
336    }
337
338    pub fn last_location(&self) -> Option<&Location> {
339        match self.context.back() {
340            Some(OpDetail::Full { location, .. }) => location.as_ref(),
341            Some(OpDetail::Basic { .. }) => None,
342            Some(OpDetail::Exec { .. }) => {
343                let op = self.context.iter().rev().nth(1)?;
344                op.location()
345            }
346            None => None,
347        }
348    }
349
350    pub fn last_resolved(&self, source_manager: &dyn SourceManager) -> Option<&ResolvedLocation> {
351        // Search through context in reverse order to find the most recent op with a resolvable
352        // location.
353        for op in self.context.iter().rev() {
354            if let Some(resolved) = op.resolve(source_manager) {
355                return Some(resolved);
356            }
357        }
358        None
359    }
360
361    pub fn recent(&self) -> &VecDeque<OpDetail> {
362        &self.context
363    }
364
365    #[inline(always)]
366    pub fn should_break_on_exit(&self) -> bool {
367        self.finishing
368    }
369
370    #[inline(always)]
371    pub fn break_on_exit(&mut self) {
372        self.finishing = true;
373    }
374}
375
376#[derive(Debug, Clone)]
377pub enum OpDetail {
378    Full {
379        op: Operation,
380        location: Option<Location>,
381        resolved: OnceCell<Option<ResolvedLocation>>,
382    },
383    Exec {
384        callee: Option<Arc<str>>,
385    },
386    Basic {
387        op: Operation,
388    },
389}
390impl OpDetail {
391    pub fn callee(&self, strip_prefix: &str) -> Option<Box<str>> {
392        match self {
393            Self::Exec { callee: None } => Some(Box::from("<unknown>")),
394            Self::Exec {
395                callee: Some(callee),
396            } => {
397                let name = match callee.split_once("::") {
398                    Some((module, rest)) if module == strip_prefix => demangle(rest),
399                    _ => demangle(callee),
400                };
401                Some(name.into_boxed_str())
402            }
403            _ => None,
404        }
405    }
406
407    pub fn display(&self) -> String {
408        match self {
409            Self::Full { op, .. } | Self::Basic { op } => format!("{op}"),
410            Self::Exec {
411                callee: Some(callee),
412            } => format!("exec.{callee}"),
413            Self::Exec { callee: None } => "exec.<unavailable>".to_string(),
414        }
415    }
416
417    pub fn opcode(&self) -> Operation {
418        match self {
419            Self::Full { op, .. } | Self::Basic { op } => *op,
420            Self::Exec { .. } => panic!("no opcode associated with execs"),
421        }
422    }
423
424    pub fn location(&self) -> Option<&Location> {
425        match self {
426            Self::Full { location, .. } => location.as_ref(),
427            Self::Basic { .. } | Self::Exec { .. } => None,
428        }
429    }
430
431    pub fn resolve(&self, source_manager: &dyn SourceManager) -> Option<&ResolvedLocation> {
432        match self {
433            Self::Full {
434                location: Some(loc),
435                resolved,
436                ..
437            } => resolved
438                .get_or_init(|| {
439                    let source_file = resolve_source_file_for_location(source_manager, loc)?;
440                    let span = SourceSpan::new(source_file.id(), loc.start..loc.end);
441                    let file_line_col = source_file.location(span);
442                    Some(ResolvedLocation {
443                        source_file,
444                        line: file_line_col.line.to_u32(),
445                        col: file_line_col.column.to_u32(),
446                        span,
447                    })
448                })
449                .as_ref(),
450            _ => None,
451        }
452    }
453}
454
455/// Resolve a source file for `location`.
456///
457/// Compiled packages may contain remapped paths such as `src/lib.rs`, while sources loaded by the
458/// VM host may be keyed by an absolute path, or may not be loaded yet at all. Prefer the source
459/// manager's existing URI table, then fall back to loading the file from disk.
460pub fn resolve_source_file_for_location(
461    source_manager: &dyn SourceManager,
462    location: &Location,
463) -> Option<Arc<SourceFile>> {
464    source_manager.get_by_uri(location.uri()).or_else(|| {
465        resolve_source_path(location.uri()).and_then(|path| source_manager.load_file(&path).ok())
466    })
467}
468
469/// Resolve a source URI to an existing local filesystem path.
470///
471/// Non-file URI schemes are left to the source manager. Relative paths are resolved against the
472/// debugger process' current directory, which DAP clients set to the launch `cwd`.
473pub fn resolve_source_path(uri: &Uri) -> Option<PathBuf> {
474    let path = match uri.scheme() {
475        None | Some("file") => Path::new(uri.path()),
476        Some(_) => return None,
477    };
478
479    existing_path(path).or_else(|| {
480        if path.is_relative() {
481            std::env::current_dir().ok().and_then(|cwd| existing_path(&cwd.join(path)))
482        } else {
483            None
484        }
485    })
486}
487
488/// Resolve a source location directly from the filesystem, returning the resolved path and line.
489pub fn resolve_location_from_filesystem(location: &Location) -> Option<(PathBuf, u32)> {
490    let path = resolve_source_path(location.uri())?;
491    let bytes = std::fs::read(&path).ok()?;
492    let start = location.start.to_usize().min(bytes.len());
493    let line = bytes[..start].iter().filter(|byte| **byte == b'\n').count() as u32 + 1;
494    Some((path, line))
495}
496
497/// Returns true for source paths emitted by compiler/runtime internals rather than user code.
498pub fn is_internal_source_uri(uri: &Uri) -> bool {
499    let path = uri.path().replace('\\', "/");
500    path.contains("/codegen/masm/intrinsics/") || path.contains("/rustlib/src/rust/library/")
501}
502
503fn existing_path(path: &Path) -> Option<PathBuf> {
504    path.exists()
505        .then(|| path.canonicalize().unwrap_or_else(|_| path.to_path_buf()))
506}
507
508#[derive(Debug, Clone)]
509pub struct ResolvedLocation {
510    pub source_file: Arc<SourceFile>,
511    // TODO(fabrio): Use LineNumber and ColumnNumber instead of raw `u32`.
512    pub line: u32,
513    pub col: u32,
514    pub span: SourceSpan,
515}
516impl fmt::Display for ResolvedLocation {
517    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
518        write!(f, "{}:{}:{}", self.source_file.uri().as_str(), self.line, self.col)
519    }
520}
521
522pub struct CurrentFrame {
523    pub procedure: Option<Arc<str>>,
524    pub location: Option<ResolvedLocation>,
525}
526
527pub struct StackTrace<'a> {
528    callstack: &'a CallStack,
529    recent: &'a VecDeque<Operation>,
530    source_manager: &'a dyn SourceManager,
531    current_frame: Option<CurrentFrame>,
532}
533
534impl<'a> StackTrace<'a> {
535    pub fn new(
536        callstack: &'a CallStack,
537        recent: &'a VecDeque<Operation>,
538        source_manager: &'a dyn SourceManager,
539    ) -> Self {
540        let current_frame = callstack.current_frame().map(|frame| {
541            let location = frame.last_resolved(source_manager).cloned();
542            let procedure = frame.procedure("");
543            CurrentFrame {
544                procedure,
545                location,
546            }
547        });
548        Self {
549            callstack,
550            recent,
551            source_manager,
552            current_frame,
553        }
554    }
555
556    pub fn current_frame(&self) -> Option<&CurrentFrame> {
557        self.current_frame.as_ref()
558    }
559}
560
561impl fmt::Display for StackTrace<'_> {
562    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
563        use std::fmt::Write;
564
565        let num_frames = self.callstack.frames.len();
566
567        writeln!(f, "\nStack Trace:")?;
568
569        for (i, frame) in self.callstack.frames.iter().enumerate() {
570            let is_top = i + 1 == num_frames;
571            let name = frame.procedure("");
572            let name = name.as_deref().unwrap_or("<unknown>");
573            if is_top {
574                write!(f, " `-> {name}")?;
575            } else {
576                write!(f, " |-> {name}")?;
577            }
578            if let Some(resolved) = frame.last_resolved(self.source_manager) {
579                write!(f, " in {resolved}")?;
580            } else {
581                write!(f, " in <unavailable>")?;
582            }
583            if is_top {
584                // Print op context
585                let context_size = frame.context.len();
586                writeln!(f, ":\n\nLast {context_size} Instructions (of current frame):")?;
587                for (i, op) in frame.context.iter().enumerate() {
588                    let is_last = i + 1 == context_size;
589                    if let Some(callee) = op.callee("") {
590                        write!(f, " |   exec.{callee}")?;
591                    } else {
592                        write!(f, " |   {}", op.opcode())?;
593                    }
594                    if is_last {
595                        writeln!(f, "\n `-> <error occurred here>")?;
596                    } else {
597                        f.write_char('\n')?;
598                    }
599                }
600
601                let context_size = self.recent.len();
602                writeln!(f, "\n\nLast {context_size} Instructions (any frame):")?;
603                for (i, op) in self.recent.iter().enumerate() {
604                    let is_last = i + 1 == context_size;
605                    if is_last {
606                        writeln!(f, " |   {}", op)?;
607                        writeln!(f, " `-> <error occurred here>")?;
608                    } else {
609                        writeln!(f, " |   {}", op)?;
610                    }
611                }
612            } else {
613                f.write_char('\n')?;
614            }
615        }
616
617        Ok(())
618    }
619}
620
621fn demangle(name: &str) -> String {
622    let mut input = name.as_bytes();
623    let mut demangled = Vec::with_capacity(input.len() * 2);
624    rustc_demangle::demangle_stream(&mut input, &mut demangled, /* include_hash= */ false)
625        .expect("failed to write demangled identifier");
626    String::from_utf8(demangled).expect("demangled identifier contains invalid utf-8")
627}
628
629#[cfg(test)]
630mod tests {
631    use std::{cell::OnceCell, fs, path::PathBuf};
632
633    use miden_assembly::DefaultSourceManager;
634    use miden_debug_types::{ByteIndex, Location, Uri};
635
636    use super::*;
637
638    #[test]
639    fn resolves_relative_source_locations_from_filesystem() {
640        let path = test_source_path("relative");
641        fs::create_dir_all(path.parent().unwrap()).unwrap();
642        fs::write(&path, "fn main() {\n    let x = 1;\n}\n").unwrap();
643
644        let start = "fn main() {\n    ".len() as u32;
645        let location = Location::new(
646            Uri::from(path.display().to_string()),
647            ByteIndex::new(start),
648            ByteIndex::new(start + 5),
649        );
650        let detail = OpDetail::Full {
651            op: Operation::Noop,
652            location: Some(location),
653            resolved: OnceCell::new(),
654        };
655        let source_manager = DefaultSourceManager::default();
656
657        let resolved = detail.resolve(&source_manager).expect("source should resolve");
658        assert_eq!(resolved.line, 2);
659        assert!(resolved.source_file.uri().as_str().ends_with("src/lib.rs"));
660
661        fs::remove_dir_all(path.parent().unwrap().parent().unwrap()).ok();
662    }
663
664    fn test_source_path(test_name: &str) -> PathBuf {
665        PathBuf::from("target")
666            .join("debugger-source-tests")
667            .join(format!("{}-{}", test_name, std::process::id()))
668            .join("src")
669            .join("lib.rs")
670    }
671}
miden_debug_engine/debug/stacktrace.rs

miden_debug_engine/debug/
stacktrace.rs
