1use crate::{CallTraceArena, CallTraceNode, CallTraceStep, DecodedTraceStep, TraceMemberOrder};
2use alloy_primitives::hex::ToHexExt;
3
4#[derive(Default)]
6pub struct EvmFoldedStackTraceBuilder {
7 fst: FoldedStackTraceBuilder,
9}
10
11impl EvmFoldedStackTraceBuilder {
12 pub fn build(self) -> Vec<String> {
14 self.fst.build()
15 }
16
17 pub fn process_call_node(&mut self, nodes: &[CallTraceNode], idx: usize) {
20 let node = &nodes[idx];
21
22 self.fst.enter(call_frame_name(node), node.trace.gas_used);
24
25 let mut step_exits = vec![];
27
28 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 for _ in 0..step_exits.len() {
45 self.fst.exit();
46 }
47
48 self.fst.exit();
50 }
51
52 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 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 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#[derive(Debug, Default)]
115pub struct FoldedStackTraceBuilder {
116 traces: Vec<TraceEntry>,
118 exits: usize,
120}
121
122#[derive(Debug, Default)]
124struct TraceEntry {
125 label: String,
127 parent: Option<usize>,
129 gas: u64,
131}
132
133impl FoldedStackTraceBuilder {
134 pub fn enter(&mut self, label: String, gas: u64) {
136 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 pub const fn exit(&mut self) {
148 self.exits += 1;
149 }
150
151 pub fn build(mut self) -> Vec<String> {
153 self.subtract_children();
154 self.build_without_subtraction()
155 }
156
157 pub fn build_without_subtraction(&self) -> Vec<String> {
160 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 fn subtract_children(&mut self) {
173 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
185pub(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
212pub 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", "top;child_a 100",
262 "top;child_b 200",
263 ]
264 );
265 assert_eq!(
266 trace.build(),
267 vec![
268 "top 200", "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", "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", "top;child_a 200", "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", "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", "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 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 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}