foundry_evm_traces/
folded_stack_trace.rs

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

foundry_evm_traces/
folded_stack_trace.rs
