1 use std::collections::{hash_map::DefaultHasher, HashMap, HashSet};
2 use std::fmt;
3 use std::hash::{Hash, Hasher};
4
5 use super::{Backtrace, Symbol, SymbolTrace, Trace};
6
7 /// An adjacency list representation of an execution tree.
8 ///
9 /// This tree provides a convenient intermediate representation for formatting
10 /// [`Trace`] as a tree.
11 pub(super) struct Tree {
12 /// The roots of the trees.
13 ///
14 /// There should only be one root, but the code is robust to multiple roots.
15 roots: HashSet<Symbol>,
16
17 /// The adjacency list of symbols in the execution tree(s).
18 edges: HashMap<Symbol, HashSet<Symbol>>,
19 }
20
21 impl Tree {
22 /// Constructs a [`Tree`] from [`Trace`]
from_trace(trace: Trace) -> Self23 pub(super) fn from_trace(trace: Trace) -> Self {
24 let mut roots: HashSet<Symbol> = HashSet::default();
25 let mut edges: HashMap<Symbol, HashSet<Symbol>> = HashMap::default();
26
27 for trace in trace.backtraces {
28 let trace = to_symboltrace(trace);
29
30 if let Some(first) = trace.first() {
31 roots.insert(first.to_owned());
32 }
33
34 let mut trace = trace.into_iter().peekable();
35 while let Some(frame) = trace.next() {
36 let subframes = edges.entry(frame).or_default();
37 if let Some(subframe) = trace.peek() {
38 subframes.insert(subframe.clone());
39 }
40 }
41 }
42
43 Tree { roots, edges }
44 }
45
46 /// Produces the sub-symbols of a given symbol.
consequences(&self, frame: &Symbol) -> Option<impl ExactSizeIterator<Item = &Symbol>>47 fn consequences(&self, frame: &Symbol) -> Option<impl ExactSizeIterator<Item = &Symbol>> {
48 Some(self.edges.get(frame)?.iter())
49 }
50
51 /// Format this [`Tree`] as a textual tree.
display<W: fmt::Write>( &self, f: &mut W, root: &Symbol, is_last: bool, prefix: &str, ) -> fmt::Result52 fn display<W: fmt::Write>(
53 &self,
54 f: &mut W,
55 root: &Symbol,
56 is_last: bool,
57 prefix: &str,
58 ) -> fmt::Result {
59 let root_fmt = format!("{}", root);
60
61 let current;
62 let next;
63
64 if is_last {
65 current = format!("{prefix}└╼\u{a0}{root_fmt}");
66 next = format!("{}\u{a0}\u{a0}\u{a0}", prefix);
67 } else {
68 current = format!("{prefix}├╼\u{a0}{root_fmt}");
69 next = format!("{}│\u{a0}\u{a0}", prefix);
70 }
71
72 write!(f, "{}", {
73 let mut current = current.chars();
74 current.next().unwrap();
75 current.next().unwrap();
76 ¤t.as_str()
77 })?;
78
79 if let Some(consequences) = self.consequences(root) {
80 let len = consequences.len();
81 for (i, consequence) in consequences.enumerate() {
82 let is_last = i == len - 1;
83 writeln!(f)?;
84 self.display(f, consequence, is_last, &next)?;
85 }
86 }
87
88 Ok(())
89 }
90 }
91
92 impl fmt::Display for Tree {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result93 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
94 for root in &self.roots {
95 self.display(f, root, true, " ")?;
96 }
97 Ok(())
98 }
99 }
100
101 /// Resolve a sequence of [`backtrace::BacktraceFrame`]s into a sequence of
102 /// [`Symbol`]s.
to_symboltrace(backtrace: Backtrace) -> SymbolTrace103 fn to_symboltrace(backtrace: Backtrace) -> SymbolTrace {
104 // Resolve the backtrace frames to symbols.
105 let backtrace: Backtrace = {
106 let mut backtrace = backtrace::Backtrace::from(backtrace);
107 backtrace.resolve();
108 backtrace.into()
109 };
110
111 // Accumulate the symbols in descending order into `symboltrace`.
112 let mut symboltrace: SymbolTrace = vec![];
113 let mut state = DefaultHasher::new();
114 for frame in backtrace.into_iter().rev() {
115 for symbol in frame.symbols().iter().rev() {
116 let symbol = Symbol {
117 symbol: symbol.clone(),
118 parent_hash: state.finish(),
119 };
120 symbol.hash(&mut state);
121 symboltrace.push(symbol);
122 }
123 }
124
125 symboltrace
126 }
127