tokio/runtime/task/trace/
tree.rs

1use std::collections::{hash_map::DefaultHasher, HashMap, HashSet};
2use std::fmt;
3use std::hash::{Hash, Hasher};
4
5use 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.
11pub(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
21impl Tree {
22    /// Constructs a [`Tree`] from [`Trace`]
23    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.
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.
52    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            &current.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
92impl fmt::Display for Tree {
93    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.
103fn 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}
tokio/runtime/task/trace/tree.rs

tokio/runtime/task/trace/
tree.rs
