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    /// Trace produced in isolate mode, meaning refund needs to be reversed at the depth=1
11    /// frame for consistent gas values.
12    isolate: bool,
13    /// Raw folded stack trace builder.
14    fst: FoldedStackTraceBuilder,
15}
16
17impl EvmFoldedStackTraceBuilder {
18    pub fn new(isolate: bool) -> Self {
19        Self { isolate, fst: FoldedStackTraceBuilder::default() }
20    }
21
22    /// Returns the folded stack trace as formatted strings.
23    pub fn build(self) -> Vec<String> {
24        self.fst.build()
25    }
26
27    /// Creates an entry for an EVM CALL in the folded stack trace. This method recursively
28    /// processes all the children nodes of the call node and at the end it exits.
29    pub fn process_call_node(&mut self, nodes: &[CallTraceNode], idx: usize) {
30        let node = &nodes[idx];
31
32        let func_name = if node.trace.kind.is_any_create() {
33            let contract_name = node
34                .trace
35                .decoded
36                .as_ref()
37                .and_then(|dc| dc.label.as_deref())
38                .unwrap_or("Contract");
39            format!("new {contract_name}")
40        } else {
41            let selector = node
42                .selector()
43                .map(|selector| selector.encode_hex_with_prefix())
44                .unwrap_or_else(|| "fallback".to_string());
45            let signature = node
46                .trace
47                .decoded
48                .as_ref()
49                .and_then(|dc| dc.call_data.as_ref())
50                .map(|dc| &dc.signature)
51                .unwrap_or(&selector);
52
53            if let Some(label) = node.trace.decoded.as_ref().and_then(|dc| dc.label.as_ref()) {
54                format!("{label}.{signature}")
55            } else {
56                signature.clone()
57            }
58        };
59
60        let mut gas_used = node.trace.gas_used;
61        let max_refund_adjust_depth = if self.isolate { 1 } else { 0 };
62        if node.trace.depth <= max_refund_adjust_depth {
63            gas_used += node.trace.gas_refund_counter;
64        }
65
66        self.fst.enter(func_name, gas_used);
67
68        // Track internal function step exits to do in this call context.
69        let mut step_exits = vec![];
70
71        // Process children nodes.
72        for order in &node.ordering {
73            match order {
74                TraceMemberOrder::Call(child_idx) => {
75                    let child_node_idx = node.children[*child_idx];
76                    self.process_call_node(nodes, child_node_idx);
77                }
78                TraceMemberOrder::Step(step_idx) => {
79                    self.exit_previous_steps(&mut step_exits, *step_idx);
80                    self.process_step(&node.trace.steps, *step_idx, &mut step_exits)
81                }
82                TraceMemberOrder::Log(_) => {}
83            }
84        }
85
86        // Exit pending internal function calls if any.
87        for _ in 0..step_exits.len() {
88            self.fst.exit();
89        }
90
91        // Exit from this call context in the folded stack trace.
92        self.fst.exit();
93    }
94
95    /// Creates an entry for an internal function call in the folded stack trace. This method only
96    /// enters the function in the folded stack trace, we cannot exit since we need to exit at a
97    /// future step. Hence, we keep track of the step end index in the `step_exits`.
98    fn process_step(
99        &mut self,
100        steps: &[CallTraceStep],
101        step_idx: usize,
102        step_exits: &mut Vec<usize>,
103    ) {
104        let step = &steps[step_idx];
105        if let Some(decoded_step) = &step.decoded {
106            match decoded_step.as_ref() {
107                DecodedTraceStep::InternalCall(decoded_internal_call, step_end_idx) => {
108                    let gas_used = step.gas_remaining - steps[*step_end_idx].gas_remaining;
109                    self.fst.enter(decoded_internal_call.func_name.clone(), gas_used);
110                    step_exits.push(*step_end_idx);
111                }
112                DecodedTraceStep::Line(_) => {}
113            }
114        }
115    }
116
117    /// Exits all the previous internal calls that should end before starting step_idx.
118    fn exit_previous_steps(&mut self, step_exits: &mut Vec<usize>, step_idx: usize) {
119        let initial_length = step_exits.len();
120        step_exits.retain(|&number| number > step_idx);
121
122        let num_exits = initial_length - step_exits.len();
123        for _ in 0..num_exits {
124            self.fst.exit();
125        }
126    }
127}
128
129/// Helps to translate a function enter-exit flow into a folded stack trace.
130///
131/// Example:
132/// ```solidity
133/// function top() { child_a(); child_b() } // consumes 500 gas
134/// function child_a() {} // consumes 100 gas
135/// function child_b() {} // consumes 200 gas
136/// ```
137///
138/// For execution of the `top` function looks like:
139/// 1. enter `top`
140/// 2. enter `child_a`
141/// 3. exit `child_a`
142/// 4. enter `child_b`
143/// 5. exit `child_b`
144/// 6. exit `top`
145///
146/// The translated folded stack trace lines look like:
147/// 1. top
148/// 2. top;child_a
149/// 3. top;child_b
150///
151/// Including the gas consumed by the function by itself.
152/// 1. top 200 // 500 - 100 - 200
153/// 2. top;child_a 100
154/// 3. top;child_b 200
155#[derive(Debug, Default)]
156pub struct FoldedStackTraceBuilder {
157    /// Trace entries.
158    traces: Vec<TraceEntry>,
159    /// Number of exits to be done before entering a new function.
160    exits: usize,
161}
162
163/// A single entry in a folded stack trace.
164#[derive(Debug, Default)]
165struct TraceEntry {
166    /// Names of all functions in the call stack of this trace.
167    names: Vec<String>,
168    /// Gas consumed by this function, not including refunds.
169    gas: u64,
170}
171
172impl FoldedStackTraceBuilder {
173    /// Enter execution of a function call that consumes `gas`.
174    pub fn enter(&mut self, label: String, gas: u64) {
175        let mut names = self.traces.last().map(|entry| entry.names.clone()).unwrap_or_default();
176
177        while self.exits > 0 {
178            names.pop();
179            self.exits -= 1;
180        }
181
182        names.push(label);
183        self.traces.push(TraceEntry { names, gas });
184    }
185
186    /// Exit execution of a function call.
187    pub const fn exit(&mut self) {
188        self.exits += 1;
189    }
190
191    /// Returns folded stack trace as formatted strings.
192    pub fn build(mut self) -> Vec<String> {
193        self.subtract_children();
194        self.traces.iter().map(|e| format!("{} {}", e.names.join(";"), e.gas)).collect()
195    }
196
197    /// Internal method to build the folded stack trace without subtracting gas consumed by
198    /// the children function calls.
199    pub fn build_without_subtraction(&self) -> Vec<String> {
200        self.traces.iter().map(|e| format!("{} {}", e.names.join(";"), e.gas)).collect()
201    }
202
203    /// Subtracts gas consumed by the children function calls from the parent function calls.
204    fn subtract_children(&mut self) {
205        // Iterate over each trace to find the children and subtract their values from the parents.
206        for i in 0..self.traces.len() {
207            let (left, right) = self.traces.split_at_mut(i);
208            let TraceEntry { names, gas } = &right[0];
209            if names.len() > 1 {
210                let parent_trace_to_match = &names[..names.len() - 1];
211                for parent in left.iter_mut().rev() {
212                    if parent.names == parent_trace_to_match {
213                        parent.gas = parent.gas.saturating_sub(*gas);
214                        break;
215                    }
216                }
217            }
218        }
219    }
220}
221
222/// Builds a folded stack trace from a call trace arena.
223pub fn build(arena: &CallTraceArena, isolate: bool) -> Vec<String> {
224    let mut fst = EvmFoldedStackTraceBuilder::new(isolate);
225    if !arena.nodes().is_empty() {
226        fst.process_call_node(arena.nodes(), 0);
227    }
228    fst.build()
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
