1use alloy_primitives::U256;
4use evm2::{
5 EvmTypes, Inspector,
6 evm::JournalEntry,
7 interpreter::{InstrStop, Interpreter, Message, MessageResult, op, opcode::OpCode},
8};
9use foundry_evm_traces::debug::{
10 DebugRecording, DebugStepSink, RecordedFrame, StepConverter, step_record,
11};
12use soldb_core::{EvmWord, StepRecord, StepTable};
13use std::{fmt, sync::Arc};
14
15const STORAGE_INPUTS: usize = 2;
18
19pub struct DebugRecorder {
27 sink: DebugStepSink,
28 table: Option<StepTable>,
30 first_step: usize,
32 frames: Vec<RecordedFrame>,
34 open: Vec<OpenFrame>,
36 calls_below_root: Option<usize>,
42 pending: Option<PendingStep>,
44 words: Vec<U256>,
47 shared: usize,
50 converter: StepConverter,
52}
53
54struct OpenFrame {
56 frame: usize,
58 write: Option<std::ops::Range<usize>>,
60 memory_size: usize,
62}
63
64struct PendingStep {
66 pc: u64,
67 op: OpCode,
68 gas: u64,
69 depth: u64,
70 #[cfg(test)]
71 memory: Vec<u8>,
72 return_data: Option<Arc<str>>,
74 shared: usize,
77 inputs: [U256; STORAGE_INPUTS],
79 inputs_len: usize,
80 journal_len: usize,
82}
83
84impl DebugRecorder {
85 pub fn new(sink: DebugStepSink) -> Self {
87 Self {
88 sink,
89 table: None,
90 first_step: 0,
91 frames: vec![RecordedFrame::default()],
93 open: Vec::new(),
94 calls_below_root: Some(0),
95 pending: None,
96 words: Vec::new(),
97 shared: 0,
98 converter: StepConverter::default(),
99 }
100 }
101
102 pub fn finish(&mut self) -> DebugRecording {
104 let end = self.table.as_ref().map_or(self.first_step, StepTable::len);
105 DebugRecording {
106 sink: self.sink.clone(),
107 steps: self.first_step..end,
108 frames: std::mem::take(&mut self.frames),
109 }
110 }
111
112 fn table(&mut self) -> &mut StepTable {
114 if self.table.is_none() {
115 let table = self.sink.take().unwrap_or_else(|| {
118 self.sink = DebugStepSink::new();
119 self.sink.take().unwrap_or_default()
120 });
121 self.first_step = table.len();
122 self.table = Some(table);
123 }
124 self.table.as_mut().unwrap()
125 }
126
127 fn enter(&mut self, depth: usize) {
129 if depth == 0 {
130 self.calls_below_root = None;
131 } else if self.open.is_empty()
132 && let Some(calls) = &mut self.calls_below_root
133 {
134 *calls += 1;
135 if *calls == 2 {
138 self.lower_recorded_steps();
139 }
140 }
141 let entry_step = self.table().len() - self.first_step;
142 let frame = RecordedFrame { depth, entry_step, exit_step: entry_step };
143 let index = if depth == 0 {
145 self.frames[0] = frame;
146 0
147 } else {
148 self.frames.push(frame);
149 self.frames.len() - 1
150 };
151 self.table().start_memory_frame();
152 self.open.push(OpenFrame { frame: index, write: None, memory_size: 0 });
153 }
154
155 fn exit(&mut self) {
157 debug_assert!(self.pending.is_none(), "a step did not end before its frame");
158 self.pending = None;
159 let exit_step = self.table().len() - self.first_step;
160 if let Some(open) = self.open.pop() {
161 self.frames[open.frame].exit_step = exit_step;
162 self.shared = 0;
165 self.table().end_memory_frame();
166 }
167 }
168
169 fn lower_recorded_steps(&mut self) {
174 let Some(table) = self.table.as_mut().filter(|table| table.len() > self.first_step) else {
175 return;
176 };
177 let mut lowered = StepTable::with_capacity(table.len());
178 copy_steps(table, 0..self.first_step, &mut lowered, 0);
179 copy_steps(table, self.first_step..table.len(), &mut lowered, 1);
180 *table = lowered;
181 }
182
183 fn start_step<T: EvmTypes>(&mut self, interp: &mut Interpreter<'_, '_, T>) {
185 let Some(open) = self.open.last_mut() else { return };
186 let op = OpCode::new_or_unknown(interp.opcode());
187
188 let current = interp.memory().as_slice();
191 let table = self.table.as_mut().expect("a frame is open");
192 if let Some(range) = open.write.take() {
193 let start = range.start.min(current.len());
194 let end = range.end.min(current.len());
195 table
196 .write_memory(start as u64, ¤t[start..end], current.len() as u64)
197 .expect("the write is bounded by the interpreter's memory");
198 } else if open.memory_size != current.len() {
199 table
200 .write_memory(0, &[], current.len() as u64)
201 .expect("EVM memory only grows within a frame");
202 }
203 open.memory_size = current.len();
204 open.write = memory_write(op, interp.stack().as_slice());
205 #[cfg(test)]
206 let memory = current.to_vec();
207
208 let return_data = self.converter.return_data(interp.return_data());
209
210 let stack = interp.stack();
216 let stack = stack.as_slice();
217 let shared = self.shared.min(stack.len());
218 self.words.clear();
219 self.words.extend_from_slice(&stack[shared..]);
220 let read = if op.is_valid() { op.inputs() as usize } else { 0 };
221 let changed = match op.get() {
222 op::DUP1..=op::DUP16 => 0,
223 op::SWAPN | op::EXCHANGE => stack.len(),
224 _ => read,
225 };
226 self.shared = stack.len() - changed.min(stack.len());
227 let inputs_len = read.min(stack.len()).min(STORAGE_INPUTS);
228 let mut inputs = [U256::ZERO; STORAGE_INPUTS];
229 inputs[..inputs_len].copy_from_slice(&stack[stack.len() - inputs_len..]);
230
231 let lifted = self.calls_below_root == Some(1);
232 let depth = self.frames[open.frame].depth as u64 + 1 - u64::from(lifted);
233 let pc = interp.pc() as u64;
234 let gas = interp.gas().remaining();
235 let journal_len = interp.host().state().journal().len();
236 self.pending = Some(PendingStep {
237 pc,
238 op,
239 gas,
240 depth,
241 #[cfg(test)]
242 memory,
243 return_data,
244 shared,
245 inputs,
246 inputs_len,
247 journal_len,
248 });
249 }
250
251 fn end_step<T: EvmTypes>(&mut self, interp: &mut Interpreter<'_, '_, T>) {
253 let Some(step) = self.pending.take() else { return };
254 let status = interp.result().err();
255 let had_value = if step.op == OpCode::SSTORE {
256 let journal = interp.host().state().journal();
257 (journal.len() != step.journal_len)
258 .then(|| match journal.last() {
259 Some(JournalEntry::StorageChange { previous, .. }) => Some(*previous),
260 _ => None,
261 })
262 .flatten()
263 } else {
264 None
265 };
266 let result = interp.result();
269 let gas_cost = if result == Err(InstrStop::ReentrancySentryOOG) {
270 0
271 } else if result.is_err_and(InstrStop::is_out_of_gas) {
272 step.gas
273 } else {
274 step.gas.saturating_sub(interp.gas().remaining_excluding_state_spill())
275 };
276 let after = interp.stack();
277 let after = after.as_slice();
278 let loaded = status.is_none().then(|| after.last().copied()).flatten();
281 self.append(step, status, gas_cost, loaded, had_value);
282 }
283
284 pub(crate) fn end_step_before_frame<T: EvmTypes>(&mut self, interp: &Interpreter<'_, '_, T>) {
289 let Some(step) = self.pending.take() else { return };
290 let gas_cost = step.gas.saturating_sub(interp.gas().remaining());
291 self.append(step, None, gas_cost, None, None);
292 }
293
294 pub fn end_step_not_run(&mut self) {
296 let Some(step) = self.pending.take() else { return };
297 self.append(step, None, 0, None, None);
298 }
299
300 fn append(
305 &mut self,
306 step: PendingStep,
307 status: Option<InstrStop>,
308 gas_cost: u64,
309 loaded: Option<U256>,
310 had_value: Option<U256>,
311 ) {
312 #[cfg(test)]
313 let expected_memory = step.memory;
314 let PendingStep { pc, op, gas, depth, return_data, shared, inputs, inputs_len, .. } = step;
315 let storage = self.converter.storage(op.get(), &inputs[..inputs_len], loaded, had_value);
316 let error =
317 status.filter(|status| !status.is_success()).map(|status| format!("{status:?}"));
318 let table = self.table.as_mut().expect("a frame is open");
319 table.append_kept(
320 StepRecord {
321 pc,
322 op: op.get(),
323 gas,
324 gas_cost,
325 depth,
326 error,
327 memory: None,
328 storage: Some(storage.storage),
329 storage_diff: storage.storage_diff,
330 transient_storage: storage.transient_storage,
331 return_data,
332 },
333 shared,
334 self.words.iter().map(|word| EvmWord(word.to_be_bytes())),
335 );
336 #[cfg(test)]
337 assert_eq!(
338 table.step(table.len() - 1).memory().as_deref(),
339 Some(expected_memory.as_slice()),
340 "recorded memory differs at pc {pc}, opcode {op}"
341 );
342 }
343}
344
345impl Default for DebugRecorder {
346 fn default() -> Self {
347 Self::new(DebugStepSink::new())
348 }
349}
350
351impl Clone for DebugRecorder {
353 fn clone(&self) -> Self {
354 Self::new(self.sink.clone())
355 }
356}
357
358impl Drop for DebugRecorder {
360 fn drop(&mut self) {
361 if let Some(table) = self.table.take() {
362 self.sink.put(table);
363 }
364 }
365}
366
367impl fmt::Debug for DebugRecorder {
368 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
369 f.debug_struct("DebugRecorder")
370 .field("frames", &self.frames.len())
371 .field("steps", &self.table.as_ref().map(StepTable::len))
372 .finish_non_exhaustive()
373 }
374}
375
376impl<T: EvmTypes> Inspector<T> for DebugRecorder {
377 #[inline]
378 fn step(&mut self, interp: &mut Interpreter<'_, '_, T>) {
379 self.start_step(interp);
380 }
381
382 #[inline]
383 fn step_end(&mut self, interp: &mut Interpreter<'_, '_, T>) {
384 self.end_step(interp);
385 }
386
387 fn call(
388 &mut self,
389 interp: &mut Interpreter<'_, '_, T>,
390 message: &mut Message<T>,
391 ) -> Option<MessageResult<T>> {
392 self.end_step_before_frame(interp);
393 self.enter(usize::from(message.depth));
394 None
395 }
396
397 fn call_end(
398 &mut self,
399 _interp: &mut Interpreter<'_, '_, T>,
400 _message: &Message<T>,
401 _result: &mut MessageResult<T>,
402 ) {
403 self.exit();
404 }
405
406 fn create(
407 &mut self,
408 interp: &mut Interpreter<'_, '_, T>,
409 message: &mut Message<T>,
410 ) -> Option<MessageResult<T>> {
411 self.end_step_before_frame(interp);
412 self.enter(usize::from(message.depth));
413 None
414 }
415
416 fn create_end(
417 &mut self,
418 _interp: &mut Interpreter<'_, '_, T>,
419 _message: &Message<T>,
420 _result: &mut MessageResult<T>,
421 ) {
422 self.exit();
423 }
424}
425
426fn copy_steps(
431 source: &StepTable,
432 steps: std::ops::Range<usize>,
433 target: &mut StepTable,
434 deeper: u64,
435) {
436 let mut frames = Vec::<Vec<u8>>::new();
438 for index in steps {
439 let step = source.step(index);
440 let mut record = step_record(&step);
441 let memory = record.memory.take().unwrap_or_default();
442 record.depth += deeper;
443
444 let level = step.depth() as usize + 1;
445 while frames.len() > level
448 || (frames.len() == level
449 && frames.last().is_some_and(|last| last.len() > memory.len()))
450 {
451 target.end_memory_frame();
452 frames.pop();
453 }
454 while frames.len() < level {
455 target.start_memory_frame();
456 frames.push(Vec::new());
457 }
458 let last = frames.last_mut().expect("a frame is open");
459 let grew = last.len() < memory.len();
460 last.resize(memory.len(), 0);
462 let size = memory.len() as u64;
463 if let Some(range) = changed(last, &memory) {
464 target
465 .write_memory(range.start as u64, &memory[range.clone()], size)
466 .expect("the write is bounded by the memory");
467 last[range.clone()].copy_from_slice(&memory[range]);
468 } else if grew {
469 target.write_memory(0, &[], size).expect("memory only grows");
470 }
471 target.append(record, step.stack().iter());
472 }
473 for _ in frames {
474 target.end_memory_frame();
475 }
476}
477
478fn changed(old: &[u8], new: &[u8]) -> Option<std::ops::Range<usize>> {
482 const CHUNK: usize = 256;
483 let differs = |(a, b)| a != b;
484 let (index, (a, b)) =
485 old.chunks(CHUNK).zip(new.chunks(CHUNK)).enumerate().find(|(_, (a, b))| a != b)?;
486 let start = index * CHUNK + a.iter().zip(b).position(differs)?;
487 let (index, (a, b)) =
488 old.rchunks(CHUNK).zip(new.rchunks(CHUNK)).enumerate().find(|(_, (a, b))| a != b)?;
489 let end = old.len() - index * CHUNK - a.iter().rev().zip(b.iter().rev()).position(differs)?;
490 Some(start..end)
491}
492
493fn memory_write(op: OpCode, stack: &[U256]) -> Option<std::ops::Range<usize>> {
496 let word = |depth: usize| -> Option<usize> {
497 stack.get(stack.len().checked_sub(depth + 1)?)?.try_into().ok()
498 };
499 let (offset, length) = match op {
500 OpCode::MSTORE => (word(0)?, 32),
501 OpCode::MSTORE8 => (word(0)?, 1),
502 OpCode::CALLDATACOPY | OpCode::CODECOPY | OpCode::RETURNDATACOPY | OpCode::MCOPY => {
503 (word(0)?, word(2)?)
504 }
505 OpCode::EXTCODECOPY => (word(1)?, word(3)?),
506 OpCode::CALL | OpCode::CALLCODE => (word(5)?, word(6)?),
507 OpCode::DELEGATECALL | OpCode::STATICCALL => (word(4)?, word(5)?),
508 _ => return None,
509 };
510 Some(offset..offset.saturating_add(length))
511}
512
513#[cfg(test)]
514mod tests {
515 use super::*;
516 use alloy_network::TransactionBuilder;
517 use alloy_primitives::{Address, hex};
518 use evm2::{
519 SpecId,
520 bytecode::Bytecode,
521 evm::{AccountInfo, InMemoryDB},
522 };
523 use foundry_evm_core::evm::{
524 EthEvmNetwork, EvmEnv, EvmFactoryFor, FoundryEvmFactory, FoundryTxConversion, SpecFor,
525 TransactionRequestFor, TypesFor,
526 };
527
528 #[derive(Default)]
530 struct Snapshots {
531 recorder: DebugRecorder,
532 steps: Vec<(Vec<u8>, Vec<EvmWord>)>,
533 }
534
535 impl<T: EvmTypes> Inspector<T> for Snapshots {
536 fn step(&mut self, interp: &mut Interpreter<'_, '_, T>) {
537 self.steps.push((
538 interp.memory().as_slice().to_vec(),
539 interp.stack().as_slice().iter().map(|word| EvmWord(word.to_be_bytes())).collect(),
540 ));
541 Inspector::<T>::step(&mut self.recorder, interp);
542 }
543
544 fn step_end(&mut self, interp: &mut Interpreter<'_, '_, T>) {
545 Inspector::<T>::step_end(&mut self.recorder, interp);
546 }
547
548 fn call(
549 &mut self,
550 interp: &mut Interpreter<'_, '_, T>,
551 message: &mut Message<T>,
552 ) -> Option<MessageResult<T>> {
553 Inspector::<T>::call(&mut self.recorder, interp, message)
554 }
555
556 fn call_end(
557 &mut self,
558 interp: &mut Interpreter<'_, '_, T>,
559 message: &Message<T>,
560 result: &mut MessageResult<T>,
561 ) {
562 Inspector::<T>::call_end(&mut self.recorder, interp, message, result);
563 }
564 }
565
566 #[test]
567 fn memory_writes_reconstruct_interpreter_state_in_both_directions() {
568 let target = Address::with_last_byte(0x40);
569 let child = Address::with_last_byte(0x20);
570 let mut db = InMemoryDB::default();
571 let parent = hex::decode(concat!(
574 "61abcd5f52", "6089600753", "601f5f60085e", "601f60085f5e", "60295f608037", "60295f61010039", "60295f61018060203c", "6102005150", "604261030052", "60406102e05f5f5f60205af150", "3d5f6104003e", "60206104405f5f60205afa50", "60206104605f5f60205af450", "60206104805f5f5f60205af250", "00"
589 ))
590 .unwrap();
591 db.insert_account_info(
592 &target,
593 AccountInfo::default().with_code(Bytecode::new_legacy(parent.into())),
594 );
595 db.insert_account_info(
596 &child,
597 AccountInfo::default()
598 .with_code(Bytecode::new_legacy(hex::decode("61cafe5f5260205ff3").unwrap().into())),
599 );
600 assert_reconstructs(db, target, SpecFor::<EthEvmNetwork>::default());
601 }
602
603 #[test]
604 fn immediate_stack_swaps_reconstruct_interpreter_stack() {
605 let target = Address::with_last_byte(0x40);
606 let exchange = "600160026003e88e00".to_string();
608 let swapn = (1..=18).map(|i| format!("60{i:02x}")).collect::<String>() + "e78000";
610 for code in [exchange, swapn] {
611 let mut db = InMemoryDB::default();
612 db.insert_account_info(
613 &target,
614 AccountInfo::default()
615 .with_code(Bytecode::new_legacy(hex::decode(&code).unwrap().into())),
616 );
617 assert_reconstructs(db, target, SpecId::AMSTERDAM);
618 }
619 }
620
621 #[test]
622 fn stack_reconstructs_across_dup_swap_and_call_return() {
623 let target = Address::with_last_byte(0x40);
624 let child = Address::with_last_byte(0x20);
625 let mut db = InMemoryDB::default();
626 db.insert_account_info(
629 &target,
630 AccountInfo::default().with_code(Bytecode::new_legacy(
631 hex::decode("60aa60bb90805f5f5f5f5f60205af100").unwrap().into(),
632 )),
633 );
634 db.insert_account_info(
636 &child,
637 AccountInfo::default()
638 .with_code(Bytecode::new_legacy(hex::decode("6001600200").unwrap().into())),
639 );
640 assert_reconstructs(db, target, SpecFor::<EthEvmNetwork>::default());
641 }
642
643 fn assert_reconstructs(db: InMemoryDB, target: Address, spec: SpecFor<EthEvmNetwork>) {
646 let factory = EvmFactoryFor::<EthEvmNetwork>::default();
647 let mut evm =
648 factory.create_evm(db, EvmEnv::new(spec, factory.version(spec, 1), Default::default()));
649 evm.set_inspector(Snapshots::default());
650 let request = TransactionRequestFor::<EthEvmNetwork>::default()
651 .with_from(Address::with_last_byte(0x30))
652 .with_to(target)
653 .with_nonce(0)
654 .with_chain_id(1)
655 .with_gas_limit(1_000_000)
656 .with_max_fee_per_gas(0)
657 .with_max_priority_fee_per_gas(0);
658 let tx = TypesFor::<EthEvmNetwork>::tx_from_request(request).unwrap();
659 let result = evm.transact(&tx).unwrap().commit();
660 let Snapshots { recorder, steps } = *evm.clear_inspector_as::<Snapshots>().unwrap();
661 assert!(result.status);
662 let table = recorder.table.as_ref().unwrap();
663 assert_eq!(table.len(), steps.len());
664 for index in (0..table.len()).rev().chain(0..table.len()) {
665 let step = table.step(index);
666 assert_eq!(
667 step.memory().as_deref(),
668 Some(steps[index].0.as_slice()),
669 "memory at {index}"
670 );
671 assert_eq!(step.stack().to_vec(), steps[index].1, "stack at {index}");
672 }
673 }
674
675 #[test]
676 fn second_call_below_root_lowers_recorded_steps() {
677 fn step(table: &mut StepTable, pc: u8, depth: u64) {
679 let record = StepRecord { pc: pc.into(), depth, ..Default::default() };
680 table.append(record, [EvmWord([pc; 32])]);
681 }
682
683 let mut earlier = StepTable::new();
685 earlier.start_memory_frame();
686 earlier.write_memory(0, &[9; 2], 32).unwrap();
687 step(&mut earlier, 0, 1);
688 earlier.end_memory_frame();
689 let sink = DebugStepSink::new();
690 sink.put(earlier);
691 let mut recorder = DebugRecorder::new(sink);
692
693 recorder.enter(1);
695 step(recorder.table(), 1, 1);
696 recorder.table().write_memory(0, &[1; 32], 32).unwrap();
697 step(recorder.table(), 2, 1);
698 recorder.table().write_memory(40, &[2; 8], 64).unwrap();
699 step(recorder.table(), 3, 1);
700 recorder.enter(2);
701 step(recorder.table(), 4, 2);
702 recorder.table().write_memory(0, &[3; 32], 32).unwrap();
703 step(recorder.table(), 5, 2);
704 recorder.exit();
705 recorder.table().write_memory(0, &[4; 4], 64).unwrap();
707 step(recorder.table(), 6, 1);
708 recorder.enter(2);
710 recorder.table().write_memory(0, &[], 96).unwrap();
711 step(recorder.table(), 7, 2);
712 recorder.exit();
713 recorder.enter(2);
714 step(recorder.table(), 8, 2);
715 recorder.exit();
716 step(recorder.table(), 9, 1);
717 recorder.exit();
718 recorder.enter(1);
720 recorder.table().write_memory(0, &[5; 32], 32).unwrap();
721 step(recorder.table(), 10, 2);
722 recorder.exit();
723
724 let recording = recorder.finish();
725 assert_eq!(recording.steps, 1..11);
726 assert_eq!(
727 recording.frames.iter().map(|frame| frame.depth).collect::<Vec<_>>(),
728 [0, 1, 2, 2, 2, 1]
729 );
730 let caller = [vec![1; 32], vec![0; 8], vec![2; 8], vec![0; 16]].concat();
731 let resumed = [vec![4; 4], caller[4..].to_vec()].concat();
732 let expected = [
733 (0, 1, [vec![9; 2], vec![0; 30]].concat()),
734 (1, 2, vec![]),
735 (2, 2, vec![1; 32]),
736 (3, 2, caller),
737 (4, 3, vec![]),
738 (5, 3, vec![3; 32]),
739 (6, 2, resumed.clone()),
740 (7, 3, vec![0; 96]),
741 (8, 3, vec![]),
742 (9, 2, resumed),
743 (10, 2, vec![5; 32]),
744 ];
745 let table = recorder.table.as_ref().unwrap();
746 assert_eq!(table.len(), expected.len());
747 for index in (0..table.len()).rev().chain(0..table.len()) {
748 let step = table.step(index);
749 let (pc, depth, memory) = &expected[index];
750 assert_eq!((step.pc(), step.depth()), (*pc, *depth), "step {index}");
751 assert_eq!(step.memory().as_deref(), Some(memory.as_slice()), "memory at {index}");
752 assert_eq!(step.stack().to_vec(), [EvmWord([*pc as u8; 32])], "stack at {index}");
753 }
754 }
755
756 #[test]
757 fn changed_spans_the_differing_bytes() {
758 let old = vec![0; 600];
760 let with = |set: &[usize]| {
761 let mut new = old.clone();
762 for &at in set {
763 new[at] = 1;
764 }
765 new
766 };
767 assert_eq!(changed(&[], &[]), None);
768 assert_eq!(changed(&old, &old), None);
769 assert_eq!(changed(&old, &with(&[1, 599])), Some(1..600));
770 assert_eq!(changed(&old, &with(&[255, 256])), Some(255..257));
771 assert_eq!(changed(&old, &with(&[300, 301])), Some(300..302));
772 assert_eq!(changed(&old, &with(&[3])), Some(3..4));
773 }
774}