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    rc::Rc,
8    sync::{Arc, Mutex},
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::Event;
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    events: Arc<Mutex<BTreeMap<RowIndex, Event>>>,
42    contexts: BTreeSet<Rc<str>>,
43    frames: Vec<CallFrame>,
44    block_stack: Vec<Option<SpanContext>>,
45}
46impl CallStack {
47    pub fn new(events: Arc<Mutex<BTreeMap<RowIndex, Event>>>) -> Self {
48        Self {
49            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            events: Arc::new(Default::default()),
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 events = self.events.lock().unwrap();
95            match events.first_key_value() {
96                Some((clk, _)) if *clk <= info.clk => events.pop_first().map(|(_, event)| event),
97                _ => None,
98            }
99        };
100        log::trace!("handling {:?}/{:?} at cycle {}: {:?}", info.control, info.op, info.clk, event);
101        let is_frame_start = event.as_ref().is_some_and(|event| event.is_frame_start());
102        let popped_frame = self.handle_event(event, procedure.clone(), info.op, info.asmop);
103        let is_frame_end = popped_frame.is_some();
104
105        match info.control {
106            Some(ControlFlowOp::Span) => {
107                if let Some(asmop) = info.asmop {
108                    log::debug!("{asmop:#?}");
109                    self.block_stack.push(Some(SpanContext {
110                        frame_index: self.frames.len().saturating_sub(1),
111                        location: asmop.location().cloned(),
112                    }));
113                } else {
114                    self.block_stack.push(None);
115                }
116            }
117            Some(ControlFlowOp::Join | ControlFlowOp::Split) => {
118                self.block_stack.push(None);
119            }
120            Some(ControlFlowOp::End) => {
121                self.block_stack.pop();
122            }
123            Some(ControlFlowOp::Respan) | None => {}
124        }
125
126        let Some(op) = info.op else {
127            return popped_frame;
128        };
129
130        if is_frame_start || is_frame_end {
131            return popped_frame;
132        }
133
134        // Attempt to supply procedure context from the current span context, if needed +
135        // available
136        let (procedure, asmop) = match procedure {
137            proc @ Some(_) => (proc, info.asmop.map(Cow::Borrowed)),
138            None => match self.block_stack.last() {
139                Some(Some(span_ctx)) => {
140                    let proc =
141                        self.frames.get(span_ctx.frame_index).and_then(|f| f.procedure.clone());
142                    let asmop_cow = info.asmop.map(Cow::Borrowed).or_else(|| {
143                        let context_name = proc.as_deref().unwrap_or("<unknown>").to_string();
144                        let raw_asmop = AssemblyOp::new(
145                            span_ctx.location.clone(),
146                            context_name,
147                            1,
148                            op.to_string(),
149                        );
150                        Some(Cow::Owned(raw_asmop))
151                    });
152                    (proc, asmop_cow)
153                }
154                _ => (None, info.asmop.map(Cow::Borrowed)),
155            },
156        };
157
158        // Use the current frame's procedure context, if no other more precise context is
159        // available
160        let procedure = procedure.or_else(|| self.frames.last().and_then(|f| f.procedure.clone()));
161
162        // Do we have a frame? If not, create one
163        if self.frames.is_empty() {
164            self.frames.push(CallFrame::new(procedure.clone()));
165        }
166
167        let current_frame = self.frames.last_mut().unwrap();
168
169        // Does the current frame have a procedure context/location? Use the one from this op if
170        // so
171        let procedure_context_updated = current_frame.procedure.is_none() && procedure.is_some();
172        if procedure_context_updated {
173            current_frame.procedure.clone_from(&procedure);
174        }
175
176        // Push op into call frame if this is any op other than `nop` or frame setup
177        if !matches!(op, Operation::Noop) {
178            let cycle_idx = info.asmop.map(|a| a.num_cycles()).unwrap_or(1);
179            current_frame.push(op, cycle_idx, asmop.as_deref());
180        }
181
182        // Check if we should also update the caller frame's exec detail
183        let num_frames = self.frames.len();
184        if procedure_context_updated && num_frames > 1 {
185            let caller_frame = &mut self.frames[num_frames - 2];
186            if let Some(OpDetail::Exec { callee }) = caller_frame.context.back_mut()
187                && callee.is_none()
188            {
189                *callee = procedure;
190            }
191        }
192
193        popped_frame
194    }
195
196    // Get or cache procedure name/context as `Rc<str>`
197    fn cache_procedure_name(&mut self, context_name: &str) -> Rc<str> {
198        match self.contexts.get(context_name) {
199            Some(name) => Rc::clone(name),
200            None => {
201                let name = Rc::from(context_name.to_string().into_boxed_str());
202                self.contexts.insert(Rc::clone(&name));
203                name
204            }
205        }
206    }
207
208    fn handle_event(
209        &mut self,
210        event: Option<Event>,
211        procedure: Option<Rc<str>>,
212        op: Option<Operation>,
213        asmop: Option<&AssemblyOp>,
214    ) -> Option<CallFrame> {
215        // Do we need to handle any frame events?
216        match event? {
217            Event::FrameStart => {
218                // Record the fact that we exec'd a new procedure in the op context
219                if let Some(current_frame) = self.frames.last_mut() {
220                    current_frame.push_exec(procedure.clone());
221                }
222                // The event is emitted at the start of the callee.
223                let mut frame = CallFrame::new(procedure);
224                if let Some(op) = op {
225                    frame.push(op, 0, asmop);
226                }
227                self.frames.push(frame);
228            }
229            Event::Unknown(code) => log::debug!("unknown trace event: {code}"),
230            Event::FrameEnd => {
231                return self.frames.pop();
232            }
233            _ => (),
234        }
235        None
236    }
237}
238
239pub struct CallFrame {
240    procedure: Option<Rc<str>>,
241    context: VecDeque<OpDetail>,
242    display_name: std::cell::OnceCell<Rc<str>>,
243    finishing: bool,
244}
245impl CallFrame {
246    pub fn new(procedure: Option<Rc<str>>) -> Self {
247        Self {
248            procedure,
249            context: Default::default(),
250            display_name: Default::default(),
251            finishing: false,
252        }
253    }
254
255    /// Build a frame from remote (DAP) data — used in DAP client mode.
256    ///
257    /// The frame stores the procedure name and an optional [ResolvedLocation]
258    /// as a pre-resolved `OpDetail::Full` entry so that `last_resolved()` and
259    /// `recent()` work correctly for pane rendering.
260    #[cfg(feature = "dap")]
261    pub fn from_remote(name: Option<String>, resolved: Option<ResolvedLocation>) -> Self {
262        let procedure = name.map(|n| Rc::from(n.into_boxed_str()));
263        let mut context = VecDeque::new();
264        if let Some(loc) = resolved {
265            let cell = OnceCell::new();
266            cell.set(Some(loc)).ok();
267            context.push_back(OpDetail::Full {
268                op: miden_processor::operation::Operation::Noop,
269                location: None,
270                resolved: cell,
271            });
272        }
273        Self {
274            procedure,
275            context,
276            display_name: Default::default(),
277            finishing: false,
278        }
279    }
280
281    pub fn procedure(&self, strip_prefix: &str) -> Option<Rc<str>> {
282        self.procedure.as_ref()?;
283        let name = self.display_name.get_or_init(|| {
284            let name = self.procedure.as_deref().unwrap();
285            let name = match name.split_once("::") {
286                Some((module, rest)) if module == strip_prefix => demangle(rest),
287                _ => demangle(name),
288            };
289            Rc::from(name.into_boxed_str())
290        });
291        Some(Rc::clone(name))
292    }
293
294    pub fn push_exec(&mut self, callee: Option<Rc<str>>) {
295        if self.context.len() == 5 {
296            self.context.pop_front();
297        }
298
299        self.context.push_back(OpDetail::Exec { callee });
300    }
301
302    pub fn push(&mut self, opcode: Operation, cycle_idx: u8, op: Option<&AssemblyOp>) {
303        if cycle_idx > 1 {
304            // Should we ignore this op?
305            let skip = self.context.back().map(|detail| matches!(detail, OpDetail::Full { op, .. } | OpDetail::Basic { op } if op == &opcode)).unwrap_or(false);
306            if skip {
307                return;
308            }
309        }
310
311        if self.context.len() == 5 {
312            self.context.pop_front();
313        }
314
315        match op {
316            Some(op) => {
317                let location = op.location().cloned();
318                self.context.push_back(OpDetail::Full {
319                    op: opcode,
320                    location,
321                    resolved: Default::default(),
322                });
323            }
324            None => {
325                // If this instruction does not have a location, inherit the location
326                // of the previous op in the frame, if one is present
327                if let Some(loc) = self.context.back().map(|op| op.location().cloned()) {
328                    self.context.push_back(OpDetail::Full {
329                        op: opcode,
330                        location: loc,
331                        resolved: Default::default(),
332                    });
333                } else {
334                    self.context.push_back(OpDetail::Basic { op: opcode });
335                }
336            }
337        }
338    }
339
340    pub fn last_location(&self) -> Option<&Location> {
341        match self.context.back() {
342            Some(OpDetail::Full { location, .. }) => location.as_ref(),
343            Some(OpDetail::Basic { .. }) => None,
344            Some(OpDetail::Exec { .. }) => {
345                let op = self.context.iter().rev().nth(1)?;
346                op.location()
347            }
348            None => None,
349        }
350    }
351
352    pub fn last_resolved(&self, source_manager: &dyn SourceManager) -> Option<&ResolvedLocation> {
353        // Search through context in reverse order to find the most recent op with a resolvable
354        // location.
355        for op in self.context.iter().rev() {
356            if let Some(resolved) = op.resolve(source_manager) {
357                return Some(resolved);
358            }
359        }
360        None
361    }
362
363    pub fn recent(&self) -> &VecDeque<OpDetail> {
364        &self.context
365    }
366
367    #[inline(always)]
368    pub fn should_break_on_exit(&self) -> bool {
369        self.finishing
370    }
371
372    #[inline(always)]
373    pub fn break_on_exit(&mut self) {
374        self.finishing = true;
375    }
376}
377
378#[derive(Debug, Clone)]
379pub enum OpDetail {
380    Full {
381        op: Operation,
382        location: Option<Location>,
383        resolved: OnceCell<Option<ResolvedLocation>>,
384    },
385    Exec {
386        callee: Option<Rc<str>>,
387    },
388    Basic {
389        op: Operation,
390    },
391}
392impl OpDetail {
393    pub fn callee(&self, strip_prefix: &str) -> Option<Box<str>> {
394        match self {
395            Self::Exec { callee: None } => Some(Box::from("<unknown>")),
396            Self::Exec {
397                callee: Some(callee),
398            } => {
399                let name = match callee.split_once("::") {
400                    Some((module, rest)) if module == strip_prefix => demangle(rest),
401                    _ => demangle(callee),
402                };
403                Some(name.into_boxed_str())
404            }
405            _ => None,
406        }
407    }
408
409    pub fn display(&self) -> String {
410        match self {
411            Self::Full { op, .. } | Self::Basic { op } => format!("{op}"),
412            Self::Exec {
413                callee: Some(callee),
414            } => format!("exec.{callee}"),
415            Self::Exec { callee: None } => "exec.<unavailable>".to_string(),
416        }
417    }
418
419    pub fn opcode(&self) -> Operation {
420        match self {
421            Self::Full { op, .. } | Self::Basic { op } => *op,
422            Self::Exec { .. } => panic!("no opcode associated with execs"),
423        }
424    }
425
426    pub fn location(&self) -> Option<&Location> {
427        match self {
428            Self::Full { location, .. } => location.as_ref(),
429            Self::Basic { .. } | Self::Exec { .. } => None,
430        }
431    }
432
433    pub fn resolve(&self, source_manager: &dyn SourceManager) -> Option<&ResolvedLocation> {
434        match self {
435            Self::Full {
436                location: Some(loc),
437                resolved,
438                ..
439            } => resolved
440                .get_or_init(|| {
441                    let source_file = resolve_source_file_for_location(source_manager, loc)?;
442                    let span = SourceSpan::new(source_file.id(), loc.start..loc.end);
443                    let file_line_col = source_file.location(span);
444                    Some(ResolvedLocation {
445                        source_file,
446                        line: file_line_col.line.to_u32(),
447                        col: file_line_col.column.to_u32(),
448                        span,
449                    })
450                })
451                .as_ref(),
452            _ => None,
453        }
454    }
455}
456
457/// Resolve a source file for `location`.
458///
459/// Compiled packages may contain remapped paths such as `src/lib.rs`, while sources loaded by the
460/// VM host may be keyed by an absolute path, or may not be loaded yet at all. Prefer the source
461/// manager's existing URI table, then fall back to loading the file from disk.
462pub fn resolve_source_file_for_location(
463    source_manager: &dyn SourceManager,
464    location: &Location,
465) -> Option<Arc<SourceFile>> {
466    source_manager.get_by_uri(location.uri()).or_else(|| {
467        resolve_source_path(location.uri()).and_then(|path| source_manager.load_file(&path).ok())
468    })
469}
470
471/// Resolve a source URI to an existing local filesystem path.
472///
473/// Non-file URI schemes are left to the source manager. Relative paths are resolved against the
474/// debugger process' current directory, which DAP clients set to the launch `cwd`.
475pub fn resolve_source_path(uri: &Uri) -> Option<PathBuf> {
476    let path = match uri.scheme() {
477        None | Some("file") => Path::new(uri.path()),
478        Some(_) => return None,
479    };
480
481    existing_path(path).or_else(|| {
482        if path.is_relative() {
483            std::env::current_dir().ok().and_then(|cwd| existing_path(&cwd.join(path)))
484        } else {
485            None
486        }
487    })
488}
489
490/// Resolve a source location directly from the filesystem, returning the resolved path and line.
491pub fn resolve_location_from_filesystem(location: &Location) -> Option<(PathBuf, u32)> {
492    let path = resolve_source_path(location.uri())?;
493    let bytes = std::fs::read(&path).ok()?;
494    let start = location.start.to_usize().min(bytes.len());
495    let line = bytes[..start].iter().filter(|byte| **byte == b'\n').count() as u32 + 1;
496    Some((path, line))
497}
498
499/// Returns true for source paths emitted by compiler/runtime internals rather than user code.
500pub fn is_internal_source_uri(uri: &Uri) -> bool {
501    let path = uri.path().replace('\\', "/");
502    path.contains("/codegen/masm/intrinsics/") || path.contains("/rustlib/src/rust/library/")
503}
504
505fn existing_path(path: &Path) -> Option<PathBuf> {
506    path.exists()
507        .then(|| path.canonicalize().unwrap_or_else(|_| path.to_path_buf()))
508}
509
510#[derive(Debug, Clone)]
511pub struct ResolvedLocation {
512    pub source_file: Arc<SourceFile>,
513    // TODO(fabrio): Use LineNumber and ColumnNumber instead of raw `u32`.
514    pub line: u32,
515    pub col: u32,
516    pub span: SourceSpan,
517}
518impl fmt::Display for ResolvedLocation {
519    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
520        write!(f, "{}:{}:{}", self.source_file.uri().as_str(), self.line, self.col)
521    }
522}
523
524pub struct CurrentFrame {
525    pub procedure: Option<Rc<str>>,
526    pub location: Option<ResolvedLocation>,
527}
528
529pub struct StackTrace<'a> {
530    callstack: &'a CallStack,
531    recent: &'a VecDeque<Operation>,
532    source_manager: &'a dyn SourceManager,
533    current_frame: Option<CurrentFrame>,
534}
535
536impl<'a> StackTrace<'a> {
537    pub fn new(
538        callstack: &'a CallStack,
539        recent: &'a VecDeque<Operation>,
540        source_manager: &'a dyn SourceManager,
541    ) -> Self {
542        let current_frame = callstack.current_frame().map(|frame| {
543            let location = frame.last_resolved(source_manager).cloned();
544            let procedure = frame.procedure("");
545            CurrentFrame {
546                procedure,
547                location,
548            }
549        });
550        Self {
551            callstack,
552            recent,
553            source_manager,
554            current_frame,
555        }
556    }
557
558    pub fn current_frame(&self) -> Option<&CurrentFrame> {
559        self.current_frame.as_ref()
560    }
561}
562
563impl fmt::Display for StackTrace<'_> {
564    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
565        use std::fmt::Write;
566
567        let num_frames = self.callstack.frames.len();
568
569        writeln!(f, "\nStack Trace:")?;
570
571        for (i, frame) in self.callstack.frames.iter().enumerate() {
572            let is_top = i + 1 == num_frames;
573            let name = frame.procedure("");
574            let name = name.as_deref().unwrap_or("<unknown>");
575            if is_top {
576                write!(f, " `-> {name}")?;
577            } else {
578                write!(f, " |-> {name}")?;
579            }
580            if let Some(resolved) = frame.last_resolved(self.source_manager) {
581                write!(f, " in {resolved}")?;
582            } else {
583                write!(f, " in <unavailable>")?;
584            }
585            if is_top {
586                // Print op context
587                let context_size = frame.context.len();
588                writeln!(f, ":\n\nLast {context_size} Instructions (of current frame):")?;
589                for (i, op) in frame.context.iter().enumerate() {
590                    let is_last = i + 1 == context_size;
591                    if let Some(callee) = op.callee("") {
592                        write!(f, " |   exec.{callee}")?;
593                    } else {
594                        write!(f, " |   {}", op.opcode())?;
595                    }
596                    if is_last {
597                        writeln!(f, "\n `-> <error occurred here>")?;
598                    } else {
599                        f.write_char('\n')?;
600                    }
601                }
602
603                let context_size = self.recent.len();
604                writeln!(f, "\n\nLast {context_size} Instructions (any frame):")?;
605                for (i, op) in self.recent.iter().enumerate() {
606                    let is_last = i + 1 == context_size;
607                    if is_last {
608                        writeln!(f, " |   {}", op)?;
609                        writeln!(f, " `-> <error occurred here>")?;
610                    } else {
611                        writeln!(f, " |   {}", op)?;
612                    }
613                }
614            } else {
615                f.write_char('\n')?;
616            }
617        }
618
619        Ok(())
620    }
621}
622
623fn demangle(name: &str) -> String {
624    let mut input = name.as_bytes();
625    let mut demangled = Vec::with_capacity(input.len() * 2);
626    rustc_demangle::demangle_stream(&mut input, &mut demangled, /* include_hash= */ false)
627        .expect("failed to write demangled identifier");
628    String::from_utf8(demangled).expect("demangled identifier contains invalid utf-8")
629}
630
631#[cfg(test)]
632mod tests {
633    use std::{cell::OnceCell, fs, path::PathBuf};
634
635    use miden_assembly::DefaultSourceManager;
636    use miden_debug_types::{ByteIndex, Location, Uri};
637
638    use super::*;
639
640    #[test]
641    fn resolves_relative_source_locations_from_filesystem() {
642        let path = test_source_path("relative");
643        fs::create_dir_all(path.parent().unwrap()).unwrap();
644        fs::write(&path, "fn main() {\n    let x = 1;\n}\n").unwrap();
645
646        let start = "fn main() {\n    ".len() as u32;
647        let location = Location::new(
648            Uri::from(path.display().to_string()),
649            ByteIndex::new(start),
650            ByteIndex::new(start + 5),
651        );
652        let detail = OpDetail::Full {
653            op: Operation::Noop,
654            location: Some(location),
655            resolved: OnceCell::new(),
656        };
657        let source_manager = DefaultSourceManager::default();
658
659        let resolved = detail.resolve(&source_manager).expect("source should resolve");
660        assert_eq!(resolved.line, 2);
661        assert!(resolved.source_file.uri().as_str().ends_with("src/lib.rs"));
662
663        fs::remove_dir_all(path.parent().unwrap().parent().unwrap()).ok();
664    }
665
666    fn test_source_path(test_name: &str) -> PathBuf {
667        PathBuf::from("target")
668            .join("debugger-source-tests")
669            .join(format!("{}-{}", test_name, std::process::id()))
670            .join("src")
671            .join("lib.rs")
672    }
673}
miden_debug_engine/debug/stacktrace.rs

miden_debug_engine/debug/
stacktrace.rs
