Skip to main content

foundry_cheatcodes/test/
assert.rs

1use crate::{CheatcodesExecutor, CheatsCtxt, Result, Vm::*};
2use alloy_primitives::{Address, B256, Bytes, I256, U256, U512, keccak256, uint};
3use alloy_sol_types::SolCall;
4use evm2::interpreter::{InstrStop, op, opcode::OpCode};
5use foundry_evm_core::{
6    abi::console::{format_units_int, format_units_uint},
7    backend::GLOBAL_FAIL_SLOT,
8    constants::CHEATCODE_ADDRESS,
9    decode::ASSERTION_FAILED_PREFIX,
10    evm::{FoundryEvmNetwork, InterpreterFor, MessageResultFor},
11};
12use itertools::Itertools;
13use std::{
14    borrow::Cow,
15    fmt,
16    sync::{
17        Arc,
18        atomic::{AtomicBool, Ordering},
19    },
20};
21
22const EQ_REL_DELTA_RESOLUTION: U256 = uint!(18_U256);
23
24struct ComparisonAssertionError<'a, T> {
25    kind: AssertionKind,
26    left: &'a T,
27    right: &'a T,
28}
29
30#[derive(Clone, Copy)]
31enum AssertionKind {
32    Eq,
33    Ne,
34    Gt,
35    Ge,
36    Lt,
37    Le,
38}
39
40impl AssertionKind {
41    const fn inverse(self) -> Self {
42        match self {
43            Self::Eq => Self::Ne,
44            Self::Ne => Self::Eq,
45            Self::Gt => Self::Le,
46            Self::Ge => Self::Lt,
47            Self::Lt => Self::Ge,
48            Self::Le => Self::Gt,
49        }
50    }
51
52    const fn to_str(self) -> &'static str {
53        match self {
54            Self::Eq => "==",
55            Self::Ne => "!=",
56            Self::Gt => ">",
57            Self::Ge => ">=",
58            Self::Lt => "<",
59            Self::Le => "<=",
60        }
61    }
62}
63
64impl<T> ComparisonAssertionError<'_, T> {
65    fn format_values<D: fmt::Display>(&self, f: impl Fn(&T) -> D) -> String {
66        format!("{} {} {}", f(self.left), self.kind.inverse().to_str(), f(self.right))
67    }
68}
69
70impl<T: fmt::Display> ComparisonAssertionError<'_, T> {
71    fn format_for_values(&self) -> String {
72        self.format_values(T::to_string)
73    }
74}
75
76impl<T: fmt::Display> ComparisonAssertionError<'_, Vec<T>> {
77    fn format_for_arrays(&self) -> String {
78        self.format_values(|v| format!("[{}]", v.iter().format(", ")))
79    }
80}
81
82impl ComparisonAssertionError<'_, U256> {
83    fn format_with_decimals(&self, decimals: &U256) -> String {
84        self.format_values(|v| format_units_uint(v, decimals))
85    }
86}
87
88impl ComparisonAssertionError<'_, I256> {
89    fn format_with_decimals(&self, decimals: &U256) -> String {
90        self.format_values(|v| format_units_int(v, decimals))
91    }
92}
93
94#[derive(thiserror::Error, Debug)]
95#[error("{left} !~= {right} (max delta: {max_delta}, real delta: {real_delta})")]
96struct EqAbsAssertionError<T, D> {
97    left: T,
98    right: T,
99    max_delta: D,
100    real_delta: D,
101}
102
103impl EqAbsAssertionError<U256, U256> {
104    fn format_with_decimals(&self, decimals: &U256) -> String {
105        format!(
106            "{} !~= {} (max delta: {}, real delta: {})",
107            format_units_uint(&self.left, decimals),
108            format_units_uint(&self.right, decimals),
109            format_units_uint(&self.max_delta, decimals),
110            format_units_uint(&self.real_delta, decimals),
111        )
112    }
113}
114
115impl EqAbsAssertionError<I256, U256> {
116    fn format_with_decimals(&self, decimals: &U256) -> String {
117        format!(
118            "{} !~= {} (max delta: {}, real delta: {})",
119            format_units_int(&self.left, decimals),
120            format_units_int(&self.right, decimals),
121            format_units_uint(&self.max_delta, decimals),
122            format_units_uint(&self.real_delta, decimals),
123        )
124    }
125}
126
127fn format_delta_percent(delta: &U256) -> String {
128    format!("{}%", format_units_uint(delta, &(EQ_REL_DELTA_RESOLUTION - U256::from(2))))
129}
130
131#[derive(Debug)]
132enum EqRelDelta {
133    Defined(U256),
134    Undefined,
135}
136
137impl fmt::Display for EqRelDelta {
138    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139        match self {
140            Self::Defined(delta) => write!(f, "{}", format_delta_percent(delta)),
141            Self::Undefined => write!(f, "undefined"),
142        }
143    }
144}
145
146#[derive(thiserror::Error, Debug)]
147#[error(
148    "{left} !~= {right} (max delta: {}, real delta: {})",
149    format_delta_percent(max_delta),
150    real_delta
151)]
152struct EqRelAssertionFailure<T> {
153    left: T,
154    right: T,
155    max_delta: U256,
156    real_delta: EqRelDelta,
157}
158
159#[derive(thiserror::Error, Debug)]
160enum EqRelAssertionError<T> {
161    #[error(transparent)]
162    Failure(Box<EqRelAssertionFailure<T>>),
163    #[error("overflow in delta calculation")]
164    Overflow,
165}
166
167impl EqRelAssertionError<U256> {
168    fn format_with_decimals(&self, decimals: &U256) -> String {
169        match self {
170            Self::Failure(f) => format!(
171                "{} !~= {} (max delta: {}, real delta: {})",
172                format_units_uint(&f.left, decimals),
173                format_units_uint(&f.right, decimals),
174                format_delta_percent(&f.max_delta),
175                f.real_delta,
176            ),
177            Self::Overflow => self.to_string(),
178        }
179    }
180}
181
182impl EqRelAssertionError<I256> {
183    fn format_with_decimals(&self, decimals: &U256) -> String {
184        match self {
185            Self::Failure(f) => format!(
186                "{} !~= {} (max delta: {}, real delta: {})",
187                format_units_int(&f.left, decimals),
188                format_units_int(&f.right, decimals),
189                format_delta_percent(&f.max_delta),
190                f.real_delta,
191            ),
192            Self::Overflow => self.to_string(),
193        }
194    }
195}
196
197type ComparisonResult<'a, T> = Result<(), ComparisonAssertionError<'a, T>>;
198
199#[cold]
200fn handle_assertion_result<FEN: FoundryEvmNetwork, E>(
201    ccx: &mut CheatsCtxt<'_, '_, FEN>,
202    executor: &mut dyn CheatcodesExecutor<FEN>,
203    selector: [u8; 4],
204    err: E,
205    error_formatter: Option<&dyn Fn(&E) -> String>,
206    error_msg: Option<&str>,
207) -> Result {
208    let error_msg = error_msg.unwrap_or(ASSERTION_FAILED_PREFIX);
209    let msg = if let Some(error_formatter) = error_formatter {
210        Cow::Owned(format!("{error_msg}: {}", error_formatter(&err)))
211    } else {
212        Cow::Borrowed(error_msg)
213    };
214    let reverts = ccx.state.core.config.assertions_revert;
215    if let Some(trace) = &mut ccx.state.failure_trace {
216        let revert = reverts.then(|| keccak256(crate::Error::encode(msg.to_string())));
217        trace.record_assertion(selector, error_msg, revert);
218    }
219    if let Some(provenance) = &mut ccx.state.failure_provenance {
220        provenance.pending_assertion = Some(keccak256([&selector[..], msg.as_bytes()].concat()));
221    }
222    handle_assertion_result_mono(ccx, executor, msg)
223}
224
225fn handle_assertion_result_mono<FEN: FoundryEvmNetwork>(
226    ccx: &mut CheatsCtxt<'_, '_, FEN>,
227    executor: &mut dyn CheatcodesExecutor<FEN>,
228    msg: Cow<'_, str>,
229) -> Result {
230    ccx.state.failed_assertion.get_or_insert_with(|| msg.to_string());
231    if ccx.state.core.config.assertions_revert {
232        Err(msg.into_owned().into())
233    } else {
234        executor.console_log(&msg);
235        ccx.evm.state_mut().storage_slot(&CHEATCODE_ADDRESS, GLOBAL_FAIL_SLOT)?.set(U256::ONE);
236        Ok(Default::default())
237    }
238}
239
240/// Implements [crate::Cheatcode] for pairs of cheatcodes.
241///
242/// Accepts a list of pairs of cheatcodes, where the first cheatcode is the one that doesn't contain
243/// a custom error message, and the second one contains it at `err` field.
244///
245/// Passed `args` are the common arguments for both cheatcode structs (excluding `err` field).
246///
247/// Macro also accepts an optional closure that formats the error returned by the assertion.
248macro_rules! impl_assertions {
249    (|$($arg:ident),*| $body:expr, false, $(($no_error:ident, $with_error:ident)),* $(,)?) => {
250        impl_assertions! { @args_tt |($($arg),*)| $body, None, $(($no_error, $with_error)),* }
251    };
252    (|$($arg:ident),*| $body:expr, $(($no_error:ident, $with_error:ident)),* $(,)?) => {
253        impl_assertions! { @args_tt |($($arg),*)| $body, Some(&ToString::to_string), $(($no_error, $with_error)),* }
254    };
255    (|$($arg:ident),*| $body:expr, $error_formatter:expr, $(($no_error:ident, $with_error:ident)),* $(,)?) => {
256        impl_assertions! { @args_tt |($($arg),*)| $body, Some(&$error_formatter), $(($no_error, $with_error)),* }
257    };
258
259    // We convert args to `tt` and later expand them back into tuple to allow usage of expanded args inside of
260    // each assertion type context.
261    (@args_tt |$args:tt| $body:expr, $error_formatter:expr, $(($no_error:ident, $with_error:ident)),* $(,)?) => {
262        $(
263            impl_assertions! { @impl $no_error, $with_error, $args, $body, $error_formatter }
264        )*
265    };
266
267    (@impl $no_error:ident, $with_error:ident, ($($arg:ident),*), $body:expr, $error_formatter:expr) => {
268        impl crate::Cheatcode for $no_error {
269            fn apply_full<FEN: FoundryEvmNetwork>(
270                &self,
271                ccx: &mut CheatsCtxt<'_, '_, FEN>,
272                executor: &mut dyn CheatcodesExecutor<FEN>,
273            ) -> Result {
274                let Self { $($arg),* } = self;
275                match $body {
276                    Ok(()) => Ok(Default::default()),
277                    Err(err) => handle_assertion_result(
278                        ccx,
279                        executor,
280                        Self::SELECTOR,
281                        err,
282                        $error_formatter,
283                        None,
284                    ),
285                }
286            }
287        }
288
289        impl crate::Cheatcode for $with_error {
290            fn apply_full<FEN: FoundryEvmNetwork>(
291                &self,
292                ccx: &mut CheatsCtxt<'_, '_, FEN>,
293                executor: &mut dyn CheatcodesExecutor<FEN>,
294            ) -> Result {
295                let Self { $($arg,)* err } = self;
296                match $body {
297                    Ok(()) => Ok(Default::default()),
298                    Err(assertion_err) => handle_assertion_result(
299                        ccx,
300                        executor,
301                        Self::SELECTOR,
302                        assertion_err,
303                        $error_formatter,
304                        Some(err),
305                    ),
306                }
307            }
308        }
309    };
310}
311
312impl_assertions! {
313    |condition| assert_true(*condition),
314    false,
315    (assertTrue_0Call, assertTrue_1Call),
316}
317
318impl_assertions! {
319    |condition| assert_false(*condition),
320    false,
321    (assertFalse_0Call, assertFalse_1Call),
322}
323
324impl_assertions! {
325    |left, right| assert_eq(left, right),
326    ComparisonAssertionError::format_for_values,
327    (assertEq_0Call, assertEq_1Call),
328    (assertEq_2Call, assertEq_3Call),
329    (assertEq_4Call, assertEq_5Call),
330    (assertEq_6Call, assertEq_7Call),
331    (assertEq_8Call, assertEq_9Call),
332    (assertEq_10Call, assertEq_11Call),
333    (assertEq_12Call, assertEq_13Call),
334}
335
336impl_assertions! {
337    |left, right| assert_eq(left, right),
338    ComparisonAssertionError::format_for_arrays,
339    (assertEq_14Call, assertEq_15Call),
340    (assertEq_16Call, assertEq_17Call),
341    (assertEq_18Call, assertEq_19Call),
342    (assertEq_20Call, assertEq_21Call),
343    (assertEq_22Call, assertEq_23Call),
344    (assertEq_24Call, assertEq_25Call),
345    (assertEq_26Call, assertEq_27Call),
346}
347
348impl_assertions! {
349    |left, right, decimals| assert_eq(left, right),
350    |e| e.format_with_decimals(decimals),
351    (assertEqDecimal_0Call, assertEqDecimal_1Call),
352    (assertEqDecimal_2Call, assertEqDecimal_3Call),
353}
354
355impl_assertions! {
356    |left, right| assert_not_eq(left, right),
357    ComparisonAssertionError::format_for_values,
358    (assertNotEq_0Call, assertNotEq_1Call),
359    (assertNotEq_2Call, assertNotEq_3Call),
360    (assertNotEq_4Call, assertNotEq_5Call),
361    (assertNotEq_6Call, assertNotEq_7Call),
362    (assertNotEq_8Call, assertNotEq_9Call),
363    (assertNotEq_10Call, assertNotEq_11Call),
364    (assertNotEq_12Call, assertNotEq_13Call),
365}
366
367impl_assertions! {
368    |left, right| assert_not_eq(left, right),
369    ComparisonAssertionError::format_for_arrays,
370    (assertNotEq_14Call, assertNotEq_15Call),
371    (assertNotEq_16Call, assertNotEq_17Call),
372    (assertNotEq_18Call, assertNotEq_19Call),
373    (assertNotEq_20Call, assertNotEq_21Call),
374    (assertNotEq_22Call, assertNotEq_23Call),
375    (assertNotEq_24Call, assertNotEq_25Call),
376    (assertNotEq_26Call, assertNotEq_27Call),
377}
378
379impl_assertions! {
380    |left, right, decimals| assert_not_eq(left, right),
381    |e| e.format_with_decimals(decimals),
382    (assertNotEqDecimal_0Call, assertNotEqDecimal_1Call),
383    (assertNotEqDecimal_2Call, assertNotEqDecimal_3Call),
384}
385
386impl_assertions! {
387    |left, right| assert_gt(left, right),
388    ComparisonAssertionError::format_for_values,
389    (assertGt_0Call, assertGt_1Call),
390    (assertGt_2Call, assertGt_3Call),
391}
392
393impl_assertions! {
394    |left, right, decimals| assert_gt(left, right),
395    |e| e.format_with_decimals(decimals),
396    (assertGtDecimal_0Call, assertGtDecimal_1Call),
397    (assertGtDecimal_2Call, assertGtDecimal_3Call),
398}
399
400impl_assertions! {
401    |left, right| assert_ge(left, right),
402    ComparisonAssertionError::format_for_values,
403    (assertGe_0Call, assertGe_1Call),
404    (assertGe_2Call, assertGe_3Call),
405}
406
407impl_assertions! {
408    |left, right, decimals| assert_ge(left, right),
409    |e| e.format_with_decimals(decimals),
410    (assertGeDecimal_0Call, assertGeDecimal_1Call),
411    (assertGeDecimal_2Call, assertGeDecimal_3Call),
412}
413
414impl_assertions! {
415    |left, right| assert_lt(left, right),
416    ComparisonAssertionError::format_for_values,
417    (assertLt_0Call, assertLt_1Call),
418    (assertLt_2Call, assertLt_3Call),
419}
420
421impl_assertions! {
422    |left, right, decimals| assert_lt(left, right),
423    |e| e.format_with_decimals(decimals),
424    (assertLtDecimal_0Call, assertLtDecimal_1Call),
425    (assertLtDecimal_2Call, assertLtDecimal_3Call),
426}
427
428impl_assertions! {
429    |left, right| assert_le(left, right),
430    ComparisonAssertionError::format_for_values,
431    (assertLe_0Call, assertLe_1Call),
432    (assertLe_2Call, assertLe_3Call),
433}
434
435impl_assertions! {
436    |left, right, decimals| assert_le(left, right),
437    |e| e.format_with_decimals(decimals),
438    (assertLeDecimal_0Call, assertLeDecimal_1Call),
439    (assertLeDecimal_2Call, assertLeDecimal_3Call),
440}
441
442impl_assertions! {
443    |left, right, maxDelta| uint_assert_approx_eq_abs(*left, *right, *maxDelta),
444    (assertApproxEqAbs_0Call, assertApproxEqAbs_1Call),
445}
446
447impl_assertions! {
448    |left, right, maxDelta| int_assert_approx_eq_abs(*left, *right, *maxDelta),
449    (assertApproxEqAbs_2Call, assertApproxEqAbs_3Call),
450}
451
452impl_assertions! {
453    |left, right, decimals, maxDelta| uint_assert_approx_eq_abs(*left, *right, *maxDelta),
454    |e| e.format_with_decimals(decimals),
455    (assertApproxEqAbsDecimal_0Call, assertApproxEqAbsDecimal_1Call),
456}
457
458impl_assertions! {
459    |left, right, decimals, maxDelta| int_assert_approx_eq_abs(*left, *right, *maxDelta),
460    |e| e.format_with_decimals(decimals),
461    (assertApproxEqAbsDecimal_2Call, assertApproxEqAbsDecimal_3Call),
462}
463
464impl_assertions! {
465    |left, right, maxPercentDelta| uint_assert_approx_eq_rel(*left, *right, *maxPercentDelta),
466    (assertApproxEqRel_0Call, assertApproxEqRel_1Call),
467}
468
469impl_assertions! {
470    |left, right, maxPercentDelta| int_assert_approx_eq_rel(*left, *right, *maxPercentDelta),
471    (assertApproxEqRel_2Call, assertApproxEqRel_3Call),
472}
473
474impl_assertions! {
475    |left, right, decimals, maxPercentDelta| uint_assert_approx_eq_rel(*left, *right, *maxPercentDelta),
476    |e| e.format_with_decimals(decimals),
477    (assertApproxEqRelDecimal_0Call, assertApproxEqRelDecimal_1Call),
478}
479
480impl_assertions! {
481    |left, right, decimals, maxPercentDelta| int_assert_approx_eq_rel(*left, *right, *maxPercentDelta),
482    |e| e.format_with_decimals(decimals),
483    (assertApproxEqRelDecimal_2Call, assertApproxEqRelDecimal_3Call),
484}
485
486const fn assert_true(condition: bool) -> Result<(), ()> {
487    if condition { Ok(()) } else { Err(()) }
488}
489
490const fn assert_false(condition: bool) -> Result<(), ()> {
491    assert_true(!condition)
492}
493
494fn assert_eq<'a, T: PartialEq>(left: &'a T, right: &'a T) -> ComparisonResult<'a, T> {
495    if left == right {
496        Ok(())
497    } else {
498        Err(ComparisonAssertionError { kind: AssertionKind::Eq, left, right })
499    }
500}
501
502fn assert_not_eq<'a, T: PartialEq>(left: &'a T, right: &'a T) -> ComparisonResult<'a, T> {
503    if left == right {
504        Err(ComparisonAssertionError { kind: AssertionKind::Ne, left, right })
505    } else {
506        Ok(())
507    }
508}
509
510fn assert_gt<'a, T: PartialOrd>(left: &'a T, right: &'a T) -> ComparisonResult<'a, T> {
511    if left > right {
512        Ok(())
513    } else {
514        Err(ComparisonAssertionError { kind: AssertionKind::Gt, left, right })
515    }
516}
517
518fn assert_ge<'a, T: PartialOrd>(left: &'a T, right: &'a T) -> ComparisonResult<'a, T> {
519    if left >= right {
520        Ok(())
521    } else {
522        Err(ComparisonAssertionError { kind: AssertionKind::Ge, left, right })
523    }
524}
525
526fn assert_lt<'a, T: PartialOrd>(left: &'a T, right: &'a T) -> ComparisonResult<'a, T> {
527    if left < right {
528        Ok(())
529    } else {
530        Err(ComparisonAssertionError { kind: AssertionKind::Lt, left, right })
531    }
532}
533
534fn assert_le<'a, T: PartialOrd>(left: &'a T, right: &'a T) -> ComparisonResult<'a, T> {
535    if left <= right {
536        Ok(())
537    } else {
538        Err(ComparisonAssertionError { kind: AssertionKind::Le, left, right })
539    }
540}
541
542fn get_delta_int(left: I256, right: I256) -> U256 {
543    let (left_sign, left_abs) = left.into_sign_and_abs();
544    let (right_sign, right_abs) = right.into_sign_and_abs();
545
546    if left_sign == right_sign {
547        if left_abs > right_abs { left_abs - right_abs } else { right_abs - left_abs }
548    } else {
549        left_abs.wrapping_add(right_abs)
550    }
551}
552
553/// Calculates the relative delta for an absolute difference.
554///
555/// Avoids overflow in the multiplication by using [`U512`] to hold the intermediary result.
556fn calc_delta_full<T>(abs_diff: U256, right: U256) -> Result<U256, EqRelAssertionError<T>> {
557    let delta = U512::from(abs_diff) * U512::from(10).pow(U512::from(EQ_REL_DELTA_RESOLUTION))
558        / U512::from(right);
559    U256::checked_from_limbs_slice(delta.as_limbs()).ok_or(EqRelAssertionError::Overflow)
560}
561
562fn uint_assert_approx_eq_abs(
563    left: U256,
564    right: U256,
565    max_delta: U256,
566) -> Result<(), Box<EqAbsAssertionError<U256, U256>>> {
567    let delta = left.abs_diff(right);
568
569    if delta <= max_delta {
570        Ok(())
571    } else {
572        Err(Box::new(EqAbsAssertionError { left, right, max_delta, real_delta: delta }))
573    }
574}
575
576fn int_assert_approx_eq_abs(
577    left: I256,
578    right: I256,
579    max_delta: U256,
580) -> Result<(), Box<EqAbsAssertionError<I256, U256>>> {
581    let delta = get_delta_int(left, right);
582
583    if delta <= max_delta {
584        Ok(())
585    } else {
586        Err(Box::new(EqAbsAssertionError { left, right, max_delta, real_delta: delta }))
587    }
588}
589
590fn uint_assert_approx_eq_rel(
591    left: U256,
592    right: U256,
593    max_delta: U256,
594) -> Result<(), EqRelAssertionError<U256>> {
595    if right.is_zero() {
596        if left.is_zero() {
597            return Ok(());
598        }
599        return Err(EqRelAssertionError::Failure(Box::new(EqRelAssertionFailure {
600            left,
601            right,
602            max_delta,
603            real_delta: EqRelDelta::Undefined,
604        })));
605    }
606
607    let delta = calc_delta_full::<U256>(left.abs_diff(right), right)?;
608
609    if delta <= max_delta {
610        Ok(())
611    } else {
612        Err(EqRelAssertionError::Failure(Box::new(EqRelAssertionFailure {
613            left,
614            right,
615            max_delta,
616            real_delta: EqRelDelta::Defined(delta),
617        })))
618    }
619}
620
621fn int_assert_approx_eq_rel(
622    left: I256,
623    right: I256,
624    max_delta: U256,
625) -> Result<(), EqRelAssertionError<I256>> {
626    if right.is_zero() {
627        if left.is_zero() {
628            return Ok(());
629        }
630        return Err(EqRelAssertionError::Failure(Box::new(EqRelAssertionFailure {
631            left,
632            right,
633            max_delta,
634            real_delta: EqRelDelta::Undefined,
635        })));
636    }
637
638    let delta = calc_delta_full::<I256>(get_delta_int(left, right), right.unsigned_abs())?;
639
640    if delta <= max_delta {
641        Ok(())
642    } else {
643        Err(EqRelAssertionError::Failure(Box::new(EqRelAssertionFailure {
644            left,
645            right,
646            max_delta,
647            real_delta: EqRelDelta::Defined(delta),
648        })))
649    }
650}
651
652/// Records the failed assertions and frames of a call by value-independent call sites, so a
653/// minimizer can tell whether a smaller input fails the same way.
654#[derive(Clone, Debug, Default)]
655pub struct FailureTrace {
656    /// Site of the latest call made by an executing frame.
657    pending: B256,
658    /// Tracking of each executing frame, indexed by call depth.
659    frames: Vec<SiteFrame>,
660    /// Failed assertions and failed frames, in execution order.
661    events: Vec<FailureEvent>,
662    /// See [`Self::halt`].
663    halt: Option<(usize, U256)>,
664    /// Whether a snapshot was restored, which can make a different path look like this one.
665    pub(crate) unidentified: bool,
666    /// Whether a cheatcode with effects outside the EVM was skipped since recording started. Later
667    /// calls can read the state it would have changed, so it leaves them unidentified too. Shared
668    /// with the copies of the inspector that calls such as invariant checks run on and discard.
669    pub(crate) skipped_host_effects: Arc<AtomicBool>,
670    /// Whether recording is paused: calls still skip cheatcodes with effects outside the EVM, but
671    /// do not step every instruction and have no identity.
672    pub paused: bool,
673}
674
675/// Call site tracking of one executing frame.
676#[derive(Clone, Debug, Default)]
677struct SiteFrame {
678    /// Site of the call that entered this frame.
679    entry: B256,
680    /// For each stack slot, the pc of the `PUSH` its value was copied from, if any.
681    pushed_at: Vec<Option<usize>>,
682    /// Address and code of this frame, to identify the instruction that halted it.
683    destination: Address,
684    /// See [`Self::destination`].
685    code: Bytes,
686    /// Whether this frame runs initcode.
687    is_create: bool,
688    /// Highest pc executed so far, used to hash the executed part of initcode.
689    max_pc: usize,
690    /// Pc of the latest instruction, which halted the frame if it halted.
691    last_pc: usize,
692    /// End of the memory the latest instruction accessed, or zero.
693    last_memory_end: U256,
694    /// Pc of the latest `JUMPI`, taken or not.
695    last_jumpi: usize,
696    /// Number of failure events recorded before this frame started.
697    events_before: usize,
698    /// Site of the `REVERT` or `INVALID` instruction that failed this frame, if any.
699    failed_at: Option<B256>,
700}
701
702impl SiteFrame {
703    /// Returns the site of the instruction about to execute: the frame's entry, the executing
704    /// code and pc, and the return labels of the internal functions that led to it. Values that
705    /// are not pushed constants, such as inputs, are ignored.
706    fn site<FEN: FoundryEvmNetwork>(&self, interpreter: &InterpreterFor<'_, '_, FEN>) -> B256 {
707        let code = interpreter.original_bytecode_slice();
708        let mut preimage = self.entry.to_vec();
709        // Initcode embeds constructor arguments, so constructors only hash executed code, and
710        // their address can derive from those arguments, so the entry identifies them instead.
711        let code_hash = if self.is_create {
712            keccak256(code.get(..=self.max_pc).unwrap_or(code))
713        } else {
714            preimage.extend_from_slice(interpreter.message().destination.as_slice());
715            interpreter.original_bytecode_hash()
716        };
717        preimage.extend_from_slice(code_hash.as_slice());
718        preimage.extend_from_slice(&interpreter.pc().to_be_bytes());
719        for (value, pushed_at) in interpreter.stack().as_slice().iter().zip(&self.pushed_at) {
720            if let Some(pushed_at) = pushed_at
721                && is_return_label(code, value)
722            {
723                preimage.extend_from_slice(&pushed_at.to_be_bytes());
724            }
725        }
726        keccak256(preimage)
727    }
728
729    /// Returns the site of the latest instruction, which halted the frame, without the return
730    /// labels on its stack.
731    fn halt_site(&self) -> B256 {
732        let mut preimage = self.entry.to_vec();
733        let code_hash = if self.is_create {
734            keccak256(self.code.get(..=self.max_pc).unwrap_or(&self.code))
735        } else {
736            preimage.extend_from_slice(self.destination.as_slice());
737            keccak256(&self.code)
738        };
739        preimage.extend_from_slice(code_hash.as_slice());
740        preimage.extend_from_slice(&self.last_pc.to_be_bytes());
741        preimage.extend_from_slice(&self.last_jumpi.to_be_bytes());
742        keccak256(preimage)
743    }
744}
745
746/// A failure recorded by [`FailureTrace`].
747#[derive(Clone, Debug)]
748enum FailureEvent {
749    /// A failed assertion, identified by its call site, cheatcode and unformatted message, with
750    /// the hash of its revert data when assertions revert.
751    Assertion { identity: B256, revert: Option<B256> },
752    /// A call or create that reverted or halted, identified by the site where it failed, or of
753    /// the call when it ran no instructions, with the number of failure events recorded within it.
754    Frame { site: B256, stop: InstrStop, events: usize },
755}
756
757impl FailureTrace {
758    /// Starts tracking the frame of `interpreter` at `depth`.
759    pub(crate) fn enter_frame<FEN: FoundryEvmNetwork>(
760        &mut self,
761        interpreter: &InterpreterFor<'_, '_, FEN>,
762        depth: usize,
763    ) {
764        let frame = SiteFrame {
765            entry: self.pending,
766            events_before: self.events.len(),
767            ..Default::default()
768        };
769        // Frames entered without an interpreter, such as cheatcode calls, were entered at
770        // `pending` too.
771        self.frames.resize(depth, frame.clone());
772        self.frames.push(SiteFrame {
773            destination: interpreter.message().destination,
774            code: interpreter.original_bytecode(),
775            is_create: interpreter.message().kind.is_create(),
776            ..frame
777        });
778    }
779
780    /// Records the site of external calls and tracks which stack values are pushed constants.
781    pub(crate) fn step<FEN: FoundryEvmNetwork>(
782        &mut self,
783        interpreter: &mut InterpreterFor<'_, '_, FEN>,
784        depth: usize,
785    ) {
786        let Some(frame) = self.frames.get_mut(depth) else { return };
787        let height = interpreter.stack().len();
788        frame.pushed_at.resize(height, None);
789        let pc = interpreter.pc();
790        frame.max_pc = frame.max_pc.max(pc);
791        frame.last_pc = pc;
792        let opcode = interpreter.opcode();
793        if depth == 1 {
794            frame.last_memory_end = memory_end(opcode, interpreter.stack().as_slice());
795        }
796        match opcode {
797            op::PUSH0..=op::PUSH32 => return frame.pushed_at.push(Some(pc)),
798            op::DUP1..=op::DUP16 => {
799                let n = (opcode - op::DUP1 + 1) as usize;
800                if let Some(slot) = height.checked_sub(n) {
801                    frame.pushed_at.push(frame.pushed_at[slot]);
802                }
803                return;
804            }
805            op::SWAP1..=op::SWAP16 => {
806                let n = (opcode - op::SWAP1 + 1) as usize;
807                if let Some(slot) = height.checked_sub(n + 1) {
808                    frame.pushed_at.swap(slot, height - 1);
809                }
810                return;
811            }
812            // Their stack effect depends on an immediate, so stop trusting the tracked slots.
813            op::SWAPN | op::EXCHANGE => frame.pushed_at.fill(None),
814            op::CALL
815            | op::CALLCODE
816            | op::DELEGATECALL
817            | op::STATICCALL
818            | op::CREATE
819            | op::CREATE2 => self.pending = frame.site::<FEN>(interpreter),
820            op::JUMPI => frame.last_jumpi = pc,
821            op::REVERT | op::INVALID => {
822                // The optimizer shares revert blocks between checks, which the latest branch tells
823                // apart.
824                let site = frame.site::<FEN>(interpreter);
825                let preimage = [site.as_slice(), &frame.last_jumpi.to_be_bytes()].concat();
826                frame.failed_at = Some(keccak256(preimage));
827            }
828            _ => {}
829        }
830        if let Some(info) = OpCode::new(opcode) {
831            frame.pushed_at.truncate(height.saturating_sub(info.inputs() as usize));
832            frame.pushed_at.extend(std::iter::repeat_n(None, info.outputs() as usize));
833        }
834    }
835
836    /// Records a failed assertion, or a `fail()`, made by the latest call.
837    pub(crate) fn record_assertion(
838        &mut self,
839        selector: [u8; 4],
840        message: &str,
841        revert: Option<B256>,
842    ) {
843        let identity = keccak256([self.pending.as_slice(), &selector, message.as_bytes()].concat());
844        self.events.push(FailureEvent::Assertion { identity, revert });
845    }
846
847    /// Records the outcome of the frame at `depth` once all inspectors have finalized it.
848    pub fn finish_frame<FEN: FoundryEvmNetwork>(
849        &mut self,
850        depth: usize,
851        result: &MessageResultFor<FEN>,
852    ) {
853        if !result.stop.is_success() {
854            // Frames without an interpreter, such as cheatcode calls, were entered at `pending`.
855            let (site, events_before) =
856                self.frames.get(depth + 1).map_or((self.pending, self.events.len()), |frame| {
857                    (frame.failed_at.unwrap_or_else(|| frame.halt_site()), frame.events_before)
858                });
859            let events = self.events.len() - events_before;
860            self.events.push(FailureEvent::Frame { site, stop: result.stop, events });
861            if depth == 0 {
862                self.halt = self.frames.get(1).map(|frame| (frame.last_pc, frame.last_memory_end));
863            }
864        }
865        self.frames.truncate(depth + 1);
866    }
867
868    /// Returns the pc of the instruction that halted the outermost frame of the finished call, if
869    /// it failed, and the end of the memory that instruction accessed, or zero. `None` when the
870    /// identity is unknown, as a skipped cheatcode can change the path.
871    pub fn halt(&self) -> Option<(usize, U256)> {
872        self.halt.filter(|_| {
873            !self.paused && !self.unidentified && !self.skipped_host_effects.load(Ordering::Relaxed)
874        })
875    }
876
877    /// Returns whether a cheatcode with effects outside the EVM was skipped, and clears it for the
878    /// copies that share it.
879    pub fn take_skipped_host_effects(&self) -> bool {
880        self.skipped_host_effects.swap(false, Ordering::Relaxed)
881    }
882
883    /// Returns the value-independent identity of the finished call that stopped with `exit` and
884    /// returned `output`, and starts recording the next call.
885    ///
886    /// The identity is unknown when a snapshot restore discarded part of the history, when a
887    /// cheatcode with effects outside the EVM was skipped in this or an earlier call, when the call
888    /// succeeded without a failed assertion or `fail()`, such as after a legacy DSTest failure that
889    /// only wrote its own flag, or when several failed assertions could have produced the revert
890    /// data.
891    pub fn take_identity(&mut self, exit: InstrStop, output: &[u8]) -> Option<B256> {
892        let skipped_host_effects = self.skipped_host_effects.clone();
893        let Self { events, unidentified, paused, .. } = std::mem::replace(
894            self,
895            Self {
896                skipped_host_effects: skipped_host_effects.clone(),
897                paused: self.paused,
898                ..Default::default()
899            },
900        );
901        if paused || unidentified || skipped_host_effects.load(Ordering::Relaxed) {
902            return None;
903        }
904        let mut preimage = vec![exit as u8];
905        for event in &events {
906            match event {
907                FailureEvent::Assertion { identity, .. } => {
908                    preimage.push(0);
909                    preimage.extend_from_slice(identity.as_slice());
910                }
911                FailureEvent::Frame { site, stop, events } => {
912                    preimage.push(1);
913                    preimage.extend_from_slice(site.as_slice());
914                    preimage.push(*stop as u8);
915                    preimage.extend_from_slice(&events.to_be_bytes());
916                }
917            }
918        }
919        if exit.is_success() {
920            if !events.iter().any(|event| matches!(event, FailureEvent::Assertion { .. })) {
921                return None;
922            }
923        } else {
924            // Revert data produced by exactly one failed assertion is identified by that
925            // assertion, without the values in its message. Other revert data is compared in full,
926            // as custom error arguments can tell apart failures raised from one `REVERT`, such as
927            // a failure code. Errors that carry the minimized values therefore do not shrink.
928            let output_hash = keccak256(output);
929            let mut sources = events.iter().enumerate().filter(|(_, event)| {
930                matches!(event, FailureEvent::Assertion { revert, .. } if *revert == Some(output_hash))
931            });
932            match (sources.next(), sources.next()) {
933                (Some((index, _)), None) => {
934                    preimage.push(2);
935                    preimage.extend_from_slice(&index.to_be_bytes());
936                }
937                (None, _) => {
938                    preimage.push(3);
939                    preimage.extend_from_slice(output_hash.as_slice());
940                }
941                (Some(_), Some(_)) => return None,
942            }
943        }
944        Some(keccak256(preimage))
945    }
946}
947
948/// Records where a call failed, cheaply enough to run during campaigns, so a replay of the same
949/// input can be checked to fail the same way, unlike its revert data, exit reason and gas, which
950/// other failure paths can reproduce.
951///
952/// Unlike [`FailureTrace`], sites include values such as return labels, so only runs of the same
953/// input are comparable.
954#[derive(Clone, Debug, Default)]
955pub struct FailureProvenance {
956    /// Frame index and site of the `REVERT` or `INVALID` instruction about to end a frame.
957    pending_revert: Option<(usize, B256)>,
958    /// Identity of the failed assertion made by the cheatcode call in progress.
959    pub(crate) pending_assertion: Option<B256>,
960    /// Hash of the failed assertions and failed frames so far, in execution order.
961    hash: B256,
962    /// Whether a frame halted at an instruction that is not recorded, so the call has no
963    /// provenance.
964    unknown: bool,
965    /// Sites of the calls that entered the frames in progress, by depth.
966    callers: Vec<B256>,
967    /// Pc of the latest `JUMPI` of each frame in progress, taken or not, by the depth
968    /// [`Self::record_revert`] receives.
969    jumpis: Vec<usize>,
970}
971
972impl FailureProvenance {
973    /// Returns the site of the instruction about to execute: the executing address, code and pc,
974    /// and the stack values that look like return labels of internal functions.
975    fn site<FEN: FoundryEvmNetwork>(interpreter: &InterpreterFor<'_, '_, FEN>) -> B256 {
976        let code = interpreter.original_bytecode_slice();
977        let mut preimage = interpreter.message().destination.to_vec();
978        preimage.extend_from_slice(interpreter.original_bytecode_hash().as_slice());
979        preimage.extend_from_slice(&interpreter.pc().to_be_bytes());
980        for value in interpreter.stack().as_slice() {
981            if is_return_label(code, value) {
982                preimage.extend_from_slice(&value.to_be_bytes::<32>());
983            }
984        }
985        keccak256(preimage)
986    }
987
988    /// Records the site of the `REVERT` or `INVALID` instruction about to execute in the frame at
989    /// `depth`.
990    pub(crate) fn record_revert<FEN: FoundryEvmNetwork>(
991        &mut self,
992        interpreter: &InterpreterFor<'_, '_, FEN>,
993        depth: usize,
994    ) {
995        // The optimizer shares revert blocks between checks, which the frame's latest branch
996        // tells apart.
997        let jumpi = self.jumpis.get(depth).copied().unwrap_or_default();
998        let site = Self::site::<FEN>(interpreter);
999        self.pending_revert =
1000            Some((depth, keccak256([site.as_slice(), &jumpi.to_be_bytes()].concat())));
1001    }
1002
1003    /// Records the `JUMPI` about to execute at `pc` in the frame at `depth`.
1004    pub(crate) fn record_jumpi(&mut self, depth: usize, pc: usize) {
1005        if self.jumpis.len() <= depth {
1006            self.jumpis.resize(depth + 1, 0);
1007        }
1008        self.jumpis[depth] = pc;
1009    }
1010
1011    /// Records the site of `interpreter`'s call that enters the frame at `depth`.
1012    pub fn enter_frame<FEN: FoundryEvmNetwork>(
1013        &mut self,
1014        depth: usize,
1015        interpreter: &InterpreterFor<'_, '_, FEN>,
1016    ) {
1017        self.callers.truncate(depth);
1018        self.callers.push(Self::site::<FEN>(interpreter));
1019        // The entered frame, stepped at `depth + 1`, has not branched yet.
1020        self.jumpis.truncate(depth + 1);
1021    }
1022
1023    /// Records the failed assertion of the finished cheatcode call, if any, by the sites of the
1024    /// calls that led to it, so the same assertion reached through different callers differs.
1025    pub(crate) fn finish_assertion(&mut self) {
1026        if let Some(assertion) = self.pending_assertion.take() {
1027            let site = keccak256(self.callers.concat());
1028            self.fold(keccak256([site.as_slice(), assertion.as_slice()].concat()));
1029        }
1030    }
1031
1032    /// Records the outcome of the frame at `depth` once all inspectors have finalized it, by the
1033    /// sites of the calls that led to it, given the interpreter of its caller, or of the frame
1034    /// itself for the first frame.
1035    pub fn finish_frame<FEN: FoundryEvmNetwork>(
1036        &mut self,
1037        depth: usize,
1038        interpreter: &InterpreterFor<'_, '_, FEN>,
1039        result: &MessageResultFor<FEN>,
1040    ) {
1041        let pending_revert = self.pending_revert.take();
1042        // The same callee fails the same way when entered through different calls.
1043        let callers = (!result.stop.is_success()).then(|| keccak256(self.callers.concat()));
1044        self.callers.truncate(depth);
1045        let Some(callers) = callers else { return };
1046        let stop = result.stop as u8;
1047        let site = match pending_revert {
1048            Some((frame, site)) if frame == depth + 1 => site,
1049            // Halts such as invalid jumps or running out of gas can happen at any instruction,
1050            // which is not recorded.
1051            _ if result.stop != InstrStop::Revert => {
1052                self.unknown = true;
1053                return;
1054            }
1055            // Frames without instructions, such as cheatcode calls, are identified by the call
1056            // that entered them.
1057            _ => {
1058                let entry = if usize::from(interpreter.message().depth) < depth {
1059                    Self::site::<FEN>(interpreter)
1060                } else {
1061                    keccak256(interpreter.message().destination)
1062                };
1063                keccak256([entry.as_slice(), &[stop]].concat())
1064            }
1065        };
1066        let output = keccak256(&result.output);
1067        self.fold(keccak256(
1068            [callers.as_slice(), site.as_slice(), &[stop], output.as_slice()].concat(),
1069        ));
1070    }
1071
1072    /// Returns the provenance of the finished call, if known, and starts recording the next call.
1073    pub fn take(&mut self) -> Option<B256> {
1074        let this = std::mem::take(self);
1075        (!this.unknown).then_some(this.hash)
1076    }
1077
1078    /// Appends a failure event to the hash.
1079    fn fold(&mut self, event: B256) {
1080        self.hash = keccak256([self.hash.as_slice(), event.as_slice()].concat());
1081    }
1082}
1083
1084/// Returns the end of the memory that `opcode` accesses with `stack`, whose top is last, or zero
1085/// when it accesses none.
1086fn memory_end(opcode: u8, stack: &[U256]) -> U256 {
1087    let arg = |n: usize| stack.len().checked_sub(n + 1).map_or(U256::ZERO, |i| stack[i]);
1088    let range = |offset: usize, size: usize| (arg(offset), arg(size));
1089    let none = (U256::ZERO, U256::ZERO);
1090    let ranges = match opcode {
1091        op::MLOAD | op::MSTORE => [(arg(0), U256::from(32)), none],
1092        op::MSTORE8 => [(arg(0), U256::from(1)), none],
1093        op::KECCAK256 | op::LOG0..=op::LOG4 | op::RETURN | op::REVERT => [range(0, 1), none],
1094        op::CALLDATACOPY | op::CODECOPY | op::RETURNDATACOPY => [range(0, 2), none],
1095        op::EXTCODECOPY => [range(1, 3), none],
1096        op::MCOPY => [range(0, 2), range(1, 2)],
1097        op::CREATE | op::CREATE2 => [range(1, 2), none],
1098        op::CALL | op::CALLCODE => [range(3, 4), range(5, 6)],
1099        op::DELEGATECALL | op::STATICCALL => [range(2, 3), range(4, 5)],
1100        _ => return U256::ZERO,
1101    };
1102    ranges
1103        .into_iter()
1104        .filter(|(_, size)| !size.is_zero())
1105        .map(|(offset, size)| offset.saturating_add(size))
1106        .max()
1107        .unwrap_or_default()
1108}
1109
1110/// Returns whether `value` is the pc of a `JUMPDEST` right after a `JUMP` in `code`, as the
1111/// return label of an internal function call is.
1112fn is_return_label(code: &[u8], value: &U256) -> bool {
1113    usize::try_from(*value).is_ok_and(|label| {
1114        label > 0 && code.get(label) == Some(&op::JUMPDEST) && code[label - 1] == op::JUMP
1115    })
1116}
1117
1118#[cfg(test)]
1119mod tests {
1120    use super::*;
1121
1122    #[test]
1123    fn memory_halt_requires_identified_trace() {
1124        let halt = Some((42, U256::from(1024)));
1125        let mut trace = FailureTrace { halt, ..Default::default() };
1126        assert_eq!(trace.halt(), halt);
1127
1128        trace.paused = true;
1129        assert_eq!(trace.halt(), None);
1130        trace.paused = false;
1131        trace.unidentified = true;
1132        assert_eq!(trace.halt(), None);
1133        trace.unidentified = false;
1134
1135        let copy = trace.clone();
1136        copy.skipped_host_effects.store(true, Ordering::Relaxed);
1137        assert_eq!(trace.halt(), None);
1138        assert!(copy.take_skipped_host_effects());
1139        assert_eq!(trace.halt(), halt);
1140    }
1141}