Skip to main content

foundry_evm_traces/
folded_stack_trace.rs

1use crate::{CallTraceArena, CallTraceNode, CallTraceStep, DecodedTraceStep, TraceMemberOrder};
2use alloy_primitives::hex::ToHexExt;
3
4/// Wrapper for building a folded stack trace using EVM call trace node.
5#[derive(Default)]
6pub struct EvmFoldedStackTraceBuilder {
7    /// Raw folded stack trace builder.
8    fst: FoldedStackTraceBuilder,
9}
10
11impl EvmFoldedStackTraceBuilder {
12    /// Returns the folded stack trace as formatted strings.
13    pub fn build(self) -> Vec<String> {
14        self.fst.build()
15    }
16
17    /// Creates an entry for an EVM CALL in the folded stack trace. This method recursively
18    /// processes all the children nodes of the call node and at the end it exits.
19    pub fn process_call_node(&mut self, nodes: &[CallTraceNode], idx: usize) {
20        let node = &nodes[idx];
21
22        // Call gas is gross: refunds are only subtracted from the test's reported gas.
23        self.fst.enter(call_frame_name(node), node.trace.gas_used);
24
25        // Track internal function step exits to do in this call context.
26        let mut step_exits = vec![];
27
28        // Process children nodes.
29        for order in &node.ordering {
30            match order {
31                TraceMemberOrder::Call(child_idx) => {
32                    let child_node_idx = node.children[*child_idx];
33                    self.process_call_node(nodes, child_node_idx);
34                }
35                TraceMemberOrder::Step(step_idx) => {
36                    self.exit_previous_steps(&mut step_exits, *step_idx);
37                    self.process_step(&node.trace.steps, *step_idx, &mut step_exits)
38                }
39                TraceMemberOrder::Log(_) => {}
40            }
41        }
42
43        // Exit pending internal function calls if any.
44        for _ in 0..step_exits.len() {
45            self.fst.exit();
46        }
47
48        // Exit from this call context in the folded stack trace.
49        self.fst.exit();
50    }
51
52    /// Creates an entry for an internal function call in the folded stack trace. This method only
53    /// enters the function in the folded stack trace, we cannot exit since we need to exit at a
54    /// future step. Hence, we keep track of the step end index in the `step_exits`.
55    fn process_step(
56        &mut self,
57        steps: &[CallTraceStep],
58        step_idx: usize,
59        step_exits: &mut Vec<usize>,
60    ) {
61        let step = &steps[step_idx];
62        if let Some(decoded_step) = &step.decoded {
63            match decoded_step.as_ref() {
64                DecodedTraceStep::InternalCall(decoded_internal_call, step_end_idx) => {
65                    // Gas metering resets can increase the remaining gas across an internal call.
66                    let gas_used =
67                        step.gas_remaining.saturating_sub(steps[*step_end_idx].gas_remaining);
68                    self.fst.enter(decoded_internal_call.func_name.clone(), gas_used);
69                    step_exits.push(*step_end_idx);
70                }
71                DecodedTraceStep::Line(_) => {}
72            }
73        }
74    }
75
76    /// Exits all the previous internal calls that should end before starting step_idx.
77    fn exit_previous_steps(&mut self, step_exits: &mut Vec<usize>, step_idx: usize) {
78        let initial_length = step_exits.len();
79        step_exits.retain(|&number| number > step_idx);
80
81        let num_exits = initial_length - step_exits.len();
82        for _ in 0..num_exits {
83            self.fst.exit();
84        }
85    }
86}
87
88/// Helps to translate a function enter-exit flow into a folded stack trace.
89///
90/// Example:
91/// ```solidity
92/// function top() { child_a(); child_b() } // consumes 500 gas
93/// function child_a() {} // consumes 100 gas
94/// function child_b() {} // consumes 200 gas
95/// ```
96///
97/// For execution of the `top` function looks like:
98/// 1. enter `top`
99/// 2. enter `child_a`
100/// 3. exit `child_a`
101/// 4. enter `child_b`
102/// 5. exit `child_b`
103/// 6. exit `top`
104///
105/// The translated folded stack trace lines look like:
106/// 1. top
107/// 2. top;child_a
108/// 3. top;child_b
109///
110/// Including the gas consumed by the function by itself.
111/// 1. top 200 // 500 - 100 - 200
112/// 2. top;child_a 100
113/// 3. top;child_b 200
114#[derive(Debug, Default)]
115pub struct FoldedStackTraceBuilder {
116    /// Trace entries.
117    traces: Vec<TraceEntry>,
118    /// Number of exits to be done before entering a new function.
119    exits: usize,
120}
121
122/// A single entry in a folded stack trace.
123#[derive(Debug, Default)]
124struct TraceEntry {
125    /// Name of the function entered by this trace.
126    label: String,
127    /// Index of the trace entry of the calling function, if any.
128    parent: Option<usize>,
129    /// Gas consumed by this function, not including refunds.
130    gas: u64,
131}
132
133impl FoldedStackTraceBuilder {
134    /// Enter execution of a function call that consumes `gas`.
135    pub fn enter(&mut self, label: String, gas: u64) {
136        // The previous entry is the innermost open function before the pending exits.
137        let mut parent = self.traces.len().checked_sub(1);
138        while self.exits > 0 {
139            parent = parent.and_then(|idx| self.traces[idx].parent);
140            self.exits -= 1;
141        }
142
143        self.traces.push(TraceEntry { label, parent, gas });
144    }
145
146    /// Exit execution of a function call.
147    pub const fn exit(&mut self) {
148        self.exits += 1;
149    }
150
151    /// Returns folded stack trace as formatted strings.
152    pub fn build(mut self) -> Vec<String> {
153        self.subtract_children();
154        self.build_without_subtraction()
155    }
156
157    /// Internal method to build the folded stack trace without subtracting gas consumed by
158    /// the children function calls.
159    pub fn build_without_subtraction(&self) -> Vec<String> {
160        // A parent always precedes its children, so its stack is already built.
161        let mut stacks = Vec::<String>::with_capacity(self.traces.len());
162        for entry in &self.traces {
163            stacks.push(match entry.parent {
164                Some(parent) => format!("{};{}", stacks[parent], entry.label),
165                None => entry.label.clone(),
166            });
167        }
168        stacks.iter().zip(&self.traces).map(|(stack, e)| format!("{stack} {}", e.gas)).collect()
169    }
170
171    /// Subtracts gas consumed by the children function calls from the parent function calls.
172    fn subtract_children(&mut self) {
173        // A child always follows its parent, and only its own children reduce its gas, so each
174        // entry still holds its gross gas when it is subtracted from its parent.
175        for i in 0..self.traces.len() {
176            let TraceEntry { parent, gas, .. } = self.traces[i];
177            if let Some(parent) = parent {
178                let parent = &mut self.traces[parent];
179                parent.gas = parent.gas.saturating_sub(gas);
180            }
181        }
182    }
183}
184
185/// Returns the frame name of a call node, as used in flamegraphs and speedscope profiles.
186pub(crate) fn call_frame_name(node: &CallTraceNode) -> String {
187    if node.trace.kind.is_any_create() {
188        let contract_name =
189            node.trace.decoded.as_ref().and_then(|dc| dc.label.as_deref()).unwrap_or("Contract");
190        return format!("new {contract_name}");
191    }
192
193    let selector = node
194        .selector()
195        .map(|selector| selector.encode_hex_with_prefix())
196        .unwrap_or_else(|| "fallback".to_string());
197    let signature = node
198        .trace
199        .decoded
200        .as_ref()
201        .and_then(|dc| dc.call_data.as_ref())
202        .map(|dc| &dc.signature)
203        .unwrap_or(&selector);
204
205    if let Some(label) = node.trace.decoded.as_ref().and_then(|dc| dc.label.as_ref()) {
206        format!("{label}.{signature}")
207    } else {
208        signature.clone()
209    }
210}
211
212/// Builds a folded stack trace from a call trace arena.
213pub fn build(arena: &CallTraceArena) -> Vec<String> {
214    let mut fst = EvmFoldedStackTraceBuilder::default();
215    if !arena.nodes().is_empty() {
216        fst.process_call_node(arena.nodes(), 0);
217    }
218    fst.build()
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224    use crate::{CallTrace, DecodedInternalCall};
225    use alloy_primitives::{Bytes, U256};
226    use evm2::interpreter::{InstrStop, opcode::OpCode};
227
228    fn trace_step(gas_remaining: u64) -> CallTraceStep {
229        CallTraceStep {
230            pc: 0,
231            op: OpCode::STOP,
232            stack: Some(Vec::<U256>::new().into_boxed_slice()),
233            push_stack: None,
234            memory: None,
235            returndata: Bytes::new(),
236            gas_remaining,
237            gas_refund_counter: 0,
238            gas_cost: 0,
239            state_gas_cost: None,
240            state_gas_reservoir: None,
241            state_gas_spent: 0,
242            storage_change: None,
243            status: Some(InstrStop::Stop),
244            immediate_bytes: None,
245            decoded: None,
246        }
247    }
248
249    #[test]
250    fn test_fst_1() {
251        let mut trace = super::FoldedStackTraceBuilder::default();
252        trace.enter("top".to_string(), 500);
253        trace.enter("child_a".to_string(), 100);
254        trace.exit();
255        trace.enter("child_b".to_string(), 200);
256
257        assert_eq!(
258            trace.build_without_subtraction(),
259            vec![
260                "top 500", //
261                "top;child_a 100",
262                "top;child_b 200",
263            ]
264        );
265        assert_eq!(
266            trace.build(),
267            vec![
268                "top 200", // 500 - 100 - 200
269                "top;child_a 100",
270                "top;child_b 200",
271            ]
272        );
273    }
274
275    #[test]
276    fn test_fst_2() {
277        let mut trace = super::FoldedStackTraceBuilder::default();
278        trace.enter("top".to_string(), 500);
279        trace.enter("child_a".to_string(), 300);
280        trace.enter("child_b".to_string(), 100);
281        trace.exit();
282        trace.exit();
283        trace.enter("child_c".to_string(), 100);
284
285        assert_eq!(
286            trace.build_without_subtraction(),
287            vec![
288                "top 500", //
289                "top;child_a 300",
290                "top;child_a;child_b 100",
291                "top;child_c 100",
292            ]
293        );
294
295        assert_eq!(
296            trace.build(),
297            vec![
298                "top 100",         // 500 - 300 - 100
299                "top;child_a 200", // 300 - 100
300                "top;child_a;child_b 100",
301                "top;child_c 100",
302            ]
303        );
304    }
305
306    #[test]
307    fn test_fst_3() {
308        let mut trace = super::FoldedStackTraceBuilder::default();
309        trace.enter("top".to_string(), 1700);
310        trace.enter("child_a".to_string(), 500);
311        trace.exit();
312        trace.enter("child_b".to_string(), 500);
313        trace.enter("child_c".to_string(), 500);
314        trace.exit();
315        trace.exit();
316        trace.exit();
317        trace.enter("top2".to_string(), 1700);
318
319        assert_eq!(
320            trace.build_without_subtraction(),
321            vec![
322                "top 1700", //
323                "top;child_a 500",
324                "top;child_b 500",
325                "top;child_b;child_c 500",
326                "top2 1700",
327            ]
328        );
329
330        assert_eq!(
331            trace.build(),
332            vec![
333                "top 700", //
334                "top;child_a 500",
335                "top;child_b 0",
336                "top;child_b;child_c 500",
337                "top2 1700",
338            ]
339        );
340    }
341
342    #[test]
343    fn folded_stack_trace_saturates_parent_gas() {
344        let mut trace = super::FoldedStackTraceBuilder::default();
345        trace.enter("top".to_string(), 100);
346        trace.enter("child".to_string(), 150);
347
348        assert_eq!(trace.build(), vec!["top 0", "top;child 150"]);
349    }
350
351    #[test]
352    fn folded_stack_trace_keeps_precise_internal_function_names() {
353        let mut arena = CallTraceArena::default();
354        let root = &mut arena.nodes_mut()[0];
355        root.trace.gas_used = 100;
356        root.trace.gas_limit = 100;
357        root.trace.steps = vec![trace_step(100), trace_step(70)];
358        root.trace.steps[0].decoded = Some(Box::new(DecodedTraceStep::InternalCall(
359            DecodedInternalCall {
360                func_name: "DebugVarsTest::foo(uint256)".to_string(),
361                args: Some(vec!["42".to_string()]),
362                return_data: Some(vec!["43".to_string()]),
363            },
364            1,
365        )));
366        root.ordering = vec![TraceMemberOrder::Step(0), TraceMemberOrder::Step(1)];
367
368        assert_eq!(
369            super::build(&arena),
370            vec!["fallback 70", "fallback;DebugVarsTest::foo(uint256) 30",]
371        );
372    }
373
374    #[test]
375    fn folded_stack_trace_saturates_internal_call_gas_on_reset_metering() {
376        // Model an internal call whose gas meter resets before returning.
377        let mut arena = CallTraceArena::default();
378        let root = &mut arena.nodes_mut()[0];
379        root.trace.gas_used = 100;
380        root.trace.gas_limit = 100;
381        root.trace.steps = vec![trace_step(70), trace_step(100)];
382        root.trace.steps[0].decoded = Some(Box::new(DecodedTraceStep::InternalCall(
383            DecodedInternalCall {
384                func_name: "DebugVarsTest::resetsGas()".to_string(),
385                args: None,
386                return_data: None,
387            },
388            1,
389        )));
390        root.ordering = vec![TraceMemberOrder::Step(0), TraceMemberOrder::Step(1)];
391
392        assert_eq!(
393            super::build(&arena),
394            vec!["fallback 100", "fallback;DebugVarsTest::resetsGas() 0",]
395        );
396    }
397
398    #[test]
399    fn folded_stack_trace_does_not_add_refunds() {
400        // Call gas is gross, so a refund must not be added on top of it at any depth.
401        let mut arena = CallTraceArena::default();
402        let root = &mut arena.nodes_mut()[0];
403        root.trace.gas_used = 100;
404        root.trace.gas_refund_counter = 40;
405        root.children = vec![1];
406        root.ordering = vec![TraceMemberOrder::Call(0)];
407        arena.nodes_mut().push(CallTraceNode {
408            parent: Some(0),
409            idx: 1,
410            trace: CallTrace {
411                depth: 1,
412                gas_used: 60,
413                gas_refund_counter: 40,
414                ..Default::default()
415            },
416            ..Default::default()
417        });
418
419        assert_eq!(super::build(&arena), vec!["fallback 40", "fallback;fallback 60"]);
420    }
421}