Skip to main content

foundry_evm/inspectors/
debug_recorder.rs

1//! Records the debugger's opcode steps straight into a SolDB step table.
2
3use 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
15/// The most stack words the storage opcodes read: `SSTORE` and `TSTORE` read the slot and the
16/// value.
17const STORAGE_INPUTS: usize = 2;
18
19/// Records every opcode step of the debugged calls into a [`StepTable`], with the steps that
20/// each call and creation spans.
21///
22/// The steps are the ones `TracingInspector` records in debug mode, converted as the SolDB
23/// frontend converts them, but without the per-step `CallTraceStep` and its full stack copy. The
24/// inspector stack calls this recorder next to the tracer, so its frames are the tracer's nodes
25/// in the same order.
26pub struct DebugRecorder {
27    sink: DebugStepSink,
28    /// The sink's table while this recorder appends to it.
29    table: Option<StepTable>,
30    /// The first step this recorder appended.
31    first_step: usize,
32    /// The steps of each call trace node, by node index.
33    frames: Vec<RecordedFrame>,
34    /// The frames that run now, innermost last.
35    open: Vec<OpenFrame>,
36    /// The calls that started below the transaction with no frame open, under the empty root
37    /// node, or `None` once a call at depth zero replaced that node.
38    ///
39    /// The trace arena lifts a single such call into the root, see
40    /// `SparsedTraceArena::lift_single_top_level_call`, so its steps record one level up.
41    calls_below_root: Option<usize>,
42    /// The step that started and did not end yet.
43    pending: Option<PendingStep>,
44    /// The words of the pending step's stack above the ones it shares with the step appended
45    /// last, bottom first.
46    words: Vec<U256>,
47    /// How many bottom words the next step's stack shares with the stack of the step appended
48    /// last: an instruction changes only the words it reads, so the ones below them stay.
49    shared: usize,
50    /// Converts the return data and storage of the steps.
51    converter: StepConverter,
52}
53
54/// A frame that runs now.
55struct OpenFrame {
56    /// The index of the frame in `frames`.
57    frame: usize,
58    /// The range the previous opcode may have written, applied when this frame resumes.
59    write: Option<std::ops::Range<usize>>,
60    /// The memory size already recorded for this frame.
61    memory_size: usize,
62}
63
64/// What a step records when it starts.
65struct PendingStep {
66    pc: u64,
67    op: OpCode,
68    gas: u64,
69    depth: u64,
70    #[cfg(test)]
71    memory: Vec<u8>,
72    /// The hex return data buffer, or `None` if it is the one of the step appended last.
73    return_data: Option<Arc<str>>,
74    /// How many bottom words of the stack are the ones of the step appended last; the rest are
75    /// in [`DebugRecorder::words`].
76    shared: usize,
77    /// The top words a storage opcode reads, bottom first.
78    inputs: [U256; STORAGE_INPUTS],
79    inputs_len: usize,
80    /// The journal length before the step.
81    journal_len: usize,
82}
83
84impl DebugRecorder {
85    /// A recorder that appends to `sink`.
86    pub fn new(sink: DebugStepSink) -> Self {
87        Self {
88            sink,
89            table: None,
90            first_step: 0,
91            // The arena of a new tracer starts with an empty root node.
92            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    /// The steps this recorder appended, by call trace node.
103    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    /// The table to append to, taken from the sink on first use.
113    fn table(&mut self) -> &mut StepTable {
114        if self.table.is_none() {
115            // A recorder of another stack that has not finished holds the shared table, so this
116            // one records into a table of its own.
117            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    /// Opens a frame at journal depth `depth`, as the tracer opens a node.
128    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            // With a second call, the empty root stays to group the calls, so the steps of the
136            // first one go back down a level.
137            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        // The tracer replaces the root node with the call at depth zero.
144        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    /// Closes the innermost frame.
156    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            // The step appended last may be the frame's, whose stack is not the caller's. A
163            // frame's first step has an empty stack, so entering a frame shares nothing either.
164            self.shared = 0;
165            self.table().end_memory_frame();
166        }
167    }
168
169    /// Records the steps this recorder appended one level deeper.
170    ///
171    /// A step table cannot change a step in place, so the table is copied, with the steps of
172    /// earlier recorders as they are.
173    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    /// Starts a step.
184    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        // CALL output is copied after the child's call_end hook. Record it when the caller
189        // resumes, along with ordinary writes, before taking this step's memory reference.
190        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, &current[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        // The step appended last has the bottom `shared` words of this stack, so only the
211        // words above them are copied. An instruction changes only the words it reads, so the
212        // next step shares the ones below them; a `DUP` reads a word but leaves it in place.
213        // `SWAPN` and `EXCHANGE` declare no inputs but swap words at the depth their immediate
214        // gives, so they share nothing.
215        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    /// Ends the pending step after its instruction ran.
252    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        // As the tracer: the reentrancy sentry halts before any charge, and any other out-of-gas
267        // step consumes the whole remainder it started with.
268        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        // The frame runs another step unless this one ended it; that step starts with the value
279        // a load pushed on top.
280        let loaded = status.is_none().then(|| after.last().copied()).flatten();
281        self.append(step, status, gas_cost, loaded, had_value);
282    }
283
284    /// Ends the pending step of the instruction that starts a call or creation.
285    ///
286    /// evm2 ends such a step after its frame returns, but the step comes before the frame's
287    /// steps, so it ends when the frame starts, with the gas the caller charged for it.
288    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    /// Ends the pending step if an inspector halted the frame before its instruction ran.
295    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    /// Appends `step`, whose stack is the shared words of the step appended last and `words`.
301    ///
302    /// `loaded` is the value an `SLOAD` or `TLOAD` pushed, if the frame went on, and `had_value`
303    /// the value an `SSTORE` overwrote, if the journal recorded it.
304    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
351/// A clone records the next call into the same sink, from an empty state.
352impl Clone for DebugRecorder {
353    fn clone(&self) -> Self {
354        Self::new(self.sink.clone())
355    }
356}
357
358/// Gives the table back to the sink.
359impl 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
426/// Appends `steps` of `source` to `target`, `deeper` levels deeper.
427///
428/// Memory is written as it changes, within a frame for each depth, as the recorder writes it,
429/// so the copy does not store the memory of every step in full.
430fn copy_steps(
431    source: &StepTable,
432    steps: std::ops::Range<usize>,
433    target: &mut StepTable,
434    deeper: u64,
435) {
436    // The memory last written to each frame open in `target`, by depth.
437    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        // Memory never shrinks within a frame, so shorter memory at the same depth is another
446        // frame's.
447        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        // Memory grows with zeros.
461        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
478/// The range where `new` differs from `old`, which has the same length.
479///
480/// Compares whole chunks first, so unchanged memory is skipped without testing each byte.
481fn 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
493/// The destination a memory-writing opcode takes from its pre-execution stack.
494/// Memory-reading opcodes can expand memory but leave all new bytes zero.
495fn 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    /// Runs the recorder and records the interpreter's memory and stack before each step.
529    #[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        // Stores, overlapping MCOPY, the three copy instructions, and expansion by MLOAD.
572        // The child returns 32 bytes into a 64-byte output range; the rest must stay unchanged.
573        let parent = hex::decode(concat!(
574            "61abcd5f52",                 // MSTORE(0, 0xabcd).
575            "6089600753",                 // MSTORE8(7, 0x89).
576            "601f5f60085e",               // MCOPY(8, 0, 31).
577            "601f60085f5e",               // MCOPY(0, 8, 31).
578            "60295f608037",               // CALLDATACOPY(128, 0, 41).
579            "60295f61010039",             // CODECOPY(256, 0, 41).
580            "60295f61018060203c",         // EXTCODECOPY(child, 384, 0, 41).
581            "6102005150",                 // MLOAD(512).
582            "604261030052",               // MSTORE(768, 66).
583            "60406102e05f5f5f60205af150", // CALL with output at 736.
584            "3d5f6104003e",               // RETURNDATACOPY(1024, 0, RETURNDATASIZE).
585            "60206104405f5f60205afa50",   // STATICCALL.
586            "60206104605f5f60205af450",   // DELEGATECALL.
587            "60206104805f5f5f60205af250", // CALLCODE.
588            "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        // `PUSH1 1; PUSH1 2; PUSH1 3; EXCHANGE 0x8e; STOP`.
607        let exchange = "600160026003e88e00".to_string();
608        // 18 pushes, `SWAPN 0x80`, and `STOP`.
609        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        // `PUSH1 0xaa; PUSH1 0xbb; SWAP1; DUP1`, a call to the child, and `STOP`, which must
627        // show the words below the call's arguments and its result, not the child's stack.
628        db.insert_account_info(
629            &target,
630            AccountInfo::default().with_code(Bytecode::new_legacy(
631                hex::decode("60aa60bb90805f5f5f5f5f60205af100").unwrap().into(),
632            )),
633        );
634        // `PUSH1 1; PUSH1 2; STOP`.
635        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    /// Calls `target` under `spec` and checks that each recorded step has the interpreter's
644    /// memory and stack, read backwards and then forwards.
645    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        /// Appends a step at `pc` and `depth`, with `pc` as its stack.
678        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        // A step of an earlier recorder that shares the table, which stays as it is.
684        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        // The first call records one level up, as the arena lifts it into the root.
694        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        // The caller resumes with the call's output.
706        recorder.table().write_memory(0, &[4; 4], 64).unwrap();
707        step(recorder.table(), 6, 1);
708        // Two calls in a row, the second with less memory than the first.
709        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        // A second call keeps the root, so both calls record below it.
719        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        // Two whole chunks and a short one, which comes first when chunked from the end.
759        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}