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

foundry_evm_traces/
folded_stack_trace.rs
