foundry_evm/executors/invariant/
shrink.rs1use crate::executors::{
2 Executor,
3 invariant::{
4 call_after_invariant_function, call_invariant_function, error::FailedInvariantCaseData,
5 },
6};
7use alloy_primitives::{Address, Bytes, U256};
8use foundry_evm_core::constants::MAGIC_ASSUME;
9use foundry_evm_fuzz::BasicTxDetails;
10use indicatif::ProgressBar;
11use proptest::bits::{BitSetLike, VarBitSet};
12use std::cmp::min;
13
14#[derive(Clone, Copy, Debug)]
15struct Shrink {
16 call_index: usize,
17}
18
19#[derive(Debug)]
24struct CallSequenceShrinker {
25 call_sequence_len: usize,
27 included_calls: VarBitSet,
29 shrink: Shrink,
31 prev_shrink: Option<Shrink>,
33}
34
35impl CallSequenceShrinker {
36 fn new(call_sequence_len: usize) -> Self {
37 Self {
38 call_sequence_len,
39 included_calls: VarBitSet::saturated(call_sequence_len),
40 shrink: Shrink { call_index: 0 },
41 prev_shrink: None,
42 }
43 }
44
45 fn current(&self) -> impl Iterator<Item = usize> + '_ {
47 (0..self.call_sequence_len).filter(|&call_id| self.included_calls.test(call_id))
48 }
49
50 fn simplify(&mut self) -> bool {
52 if self.shrink.call_index >= self.call_sequence_len {
53 false
55 } else {
56 self.included_calls.clear(self.shrink.call_index);
58 self.prev_shrink = Some(self.shrink);
60 self.shrink = Shrink { call_index: self.shrink.call_index + 1 };
62 true
63 }
64 }
65
66 fn complicate(&mut self) -> bool {
68 match self.prev_shrink {
69 Some(shrink) => {
70 self.included_calls.set(shrink.call_index);
72 self.prev_shrink = None;
73 self.simplify()
75 }
76 None => false,
77 }
78 }
79}
80
81pub(crate) fn shrink_sequence(
89 failed_case: &FailedInvariantCaseData,
90 calls: &[BasicTxDetails],
91 executor: &Executor,
92 call_after_invariant: bool,
93 progress: Option<&ProgressBar>,
94) -> eyre::Result<Vec<BasicTxDetails>> {
95 trace!(target: "forge::test", "Shrinking sequence of {} calls.", calls.len());
96
97 if let Some(progress) = progress {
99 progress.set_length(min(calls.len(), failed_case.shrink_run_limit as usize) as u64);
100 progress.reset();
101 progress.set_message(" Shrink");
102 }
103
104 let (_, success) =
107 call_invariant_function(executor, failed_case.addr, failed_case.calldata.clone())?;
108 if !success {
109 return Ok(vec![]);
110 }
111
112 let mut shrinker = CallSequenceShrinker::new(calls.len());
113 for _ in 0..failed_case.shrink_run_limit {
114 match check_sequence(
116 executor.clone(),
117 calls,
118 shrinker.current().collect(),
119 failed_case.addr,
120 failed_case.calldata.clone(),
121 failed_case.fail_on_revert,
122 call_after_invariant,
123 ) {
124 Ok((false, _)) if !shrinker.simplify() => break,
126 Ok((true, _)) if !shrinker.complicate() => break,
129 _ => {}
130 }
131
132 if let Some(progress) = progress {
133 progress.inc(1);
134 }
135 }
136
137 Ok(shrinker.current().map(|idx| &calls[idx]).cloned().collect())
138}
139
140pub fn check_sequence(
147 mut executor: Executor,
148 calls: &[BasicTxDetails],
149 sequence: Vec<usize>,
150 test_address: Address,
151 calldata: Bytes,
152 fail_on_revert: bool,
153 call_after_invariant: bool,
154) -> eyre::Result<(bool, bool)> {
155 for call_index in sequence {
157 let tx = &calls[call_index];
158 let call_result = executor.transact_raw(
159 tx.sender,
160 tx.call_details.target,
161 tx.call_details.calldata.clone(),
162 U256::ZERO,
163 )?;
164 if call_result.reverted && fail_on_revert && call_result.result.as_ref() != MAGIC_ASSUME {
168 return Ok((false, false));
171 }
172 }
173
174 let (_, mut success) = call_invariant_function(&executor, test_address, calldata)?;
176 if success && call_after_invariant {
179 (_, success) = call_after_invariant_function(&executor, test_address)?;
180 }
181
182 Ok((success, true))
183}