foundry_evm_fuzz/strategies/
int.rs

1use alloy_dyn_abi::{DynSolType, DynSolValue};
2use alloy_primitives::{I256, Sign, U256};
3use proptest::{
4    prelude::Rng,
5    strategy::{NewTree, Strategy, ValueTree},
6    test_runner::TestRunner,
7};
8
9/// Clamps a signed integer to the range [-(max+1), max] to match real signed type ranges.
10/// For example, i128 range is [-2^127, 2^127-1], not [-2^127+1, 2^127-1].
11pub fn clamp(value: I256, max: U256) -> I256 {
12    let max_i256 = I256::from_raw(max);
13    let min_i256 = I256::overflowing_from_sign_and_abs(Sign::Negative, max + U256::from(1)).0;
14    if value > max_i256 {
15        max_i256
16    } else if value < min_i256 {
17        min_i256
18    } else {
19        value
20    }
21}
22
23/// Value tree for signed ints (up to int256).
24pub struct IntValueTree {
25    /// Lower base (by absolute value)
26    lo: I256,
27    /// Current value
28    curr: I256,
29    /// Higher base (by absolute value)
30    hi: I256,
31    /// If true cannot be simplified or complexified
32    fixed: bool,
33}
34
35impl IntValueTree {
36    /// Create a new tree
37    /// # Arguments
38    /// * `start` - Starting value for the tree
39    /// * `fixed` - If `true` the tree would only contain one element and won't be simplified.
40    fn new(start: I256, fixed: bool) -> Self {
41        Self { lo: I256::ZERO, curr: start, hi: start, fixed }
42    }
43
44    fn reposition(&mut self) -> bool {
45        let interval = self.hi - self.lo;
46        let new_mid = self.lo + interval / I256::from_raw(U256::from(2));
47
48        if new_mid == self.curr {
49            false
50        } else {
51            self.curr = new_mid;
52            true
53        }
54    }
55
56    fn magnitude_greater(lhs: I256, rhs: I256) -> bool {
57        if lhs.is_zero() {
58            return false;
59        }
60        (lhs > rhs) ^ (lhs.is_negative())
61    }
62}
63
64impl ValueTree for IntValueTree {
65    type Value = I256;
66
67    fn current(&self) -> Self::Value {
68        self.curr
69    }
70
71    fn simplify(&mut self) -> bool {
72        if self.fixed || !Self::magnitude_greater(self.hi, self.lo) {
73            return false;
74        }
75        self.hi = self.curr;
76        self.reposition()
77    }
78
79    fn complicate(&mut self) -> bool {
80        if self.fixed || !Self::magnitude_greater(self.hi, self.lo) {
81            return false;
82        }
83
84        self.lo = if self.curr != I256::MIN && self.curr != I256::MAX {
85            self.curr + if self.hi.is_negative() { I256::MINUS_ONE } else { I256::ONE }
86        } else {
87            self.curr
88        };
89
90        self.reposition()
91    }
92}
93
94/// Value tree for signed ints (up to int256).
95/// The strategy combines 3 different strategies, each assigned a specific weight:
96/// 1. Generate purely random value in a range. This will first choose bit size uniformly (up `bits`
97///    param). Then generate a value for this bit size.
98/// 2. Generate a random value around the edges (+/- 3 around min, 0 and max possible value)
99/// 3. Generate a value from a predefined fixtures set
100///
101/// To define int fixtures:
102/// - return an array of possible values for a parameter named `amount` declare a function `function
103///   fixture_amount() public returns (int32[] memory)`.
104/// - use `amount` named parameter in fuzzed test in order to include fixtures in fuzzed values
105///   `function testFuzz_int32(int32 amount)`.
106///
107/// If fixture is not a valid int type then error is raised and random value generated.
108#[derive(Debug)]
109pub struct IntStrategy {
110    /// Bit size of int (e.g. 256)
111    bits: usize,
112    /// A set of fixtures to be generated
113    fixtures: Vec<DynSolValue>,
114    /// The weight for edge cases (+/- 3 around 0 and max possible value)
115    edge_weight: usize,
116    /// The weight for fixtures
117    fixtures_weight: usize,
118    /// The weight for purely random values
119    random_weight: usize,
120    /// Optional maximum value for generated integers, used to simulate smaller signed types.
121    /// When set, generated values will be clamped to [-(max_value+1), max_value] to match
122    /// real signed integer type ranges (e.g., i128 range is [-2^127, 2^127-1]).
123    max_value: Option<U256>,
124}
125
126impl IntStrategy {
127    /// Create a new strategy.
128    /// # Arguments
129    /// * `bits` - Size of int in bits
130    /// * `fixtures` - A set of fixed values to be generated (according to fixtures weight)
131    /// * `max_value` - Optional maximum value to simulate smaller signed types. Values will be
132    ///   clamped to [-(max_value+1), max_value].
133    pub fn new(bits: usize, fixtures: Option<&[DynSolValue]>, max_value: Option<U256>) -> Self {
134        Self {
135            bits,
136            fixtures: Vec::from(fixtures.unwrap_or_default()),
137            edge_weight: 10usize,
138            fixtures_weight: 40usize,
139            random_weight: 50usize,
140            max_value,
141        }
142    }
143
144    fn effective_max(&self) -> U256 {
145        let type_max: U256 = (U256::from(1) << (self.bits - 1)) - U256::from(1);
146        self.max_value.map(|m| type_max.min(m)).unwrap_or(type_max)
147    }
148
149    fn generate_edge_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
150        let rng = runner.rng();
151
152        let offset = I256::from_raw(U256::from(rng.random_range(0..4)));
153        let umax = self.effective_max();
154        // Choose if we want values around min, -0, +0, or max
155        let kind = rng.random_range(0..4);
156        let start = match kind {
157            0 => {
158                I256::overflowing_from_sign_and_abs(Sign::Negative, umax + U256::from(1)).0 + offset
159            }
160            1 => -offset - I256::ONE,
161            2 => offset,
162            3 => I256::overflowing_from_sign_and_abs(Sign::Positive, umax).0 - offset,
163            _ => unreachable!(),
164        };
165        Ok(IntValueTree::new(clamp(start, self.effective_max()), false))
166    }
167
168    fn generate_fixtures_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
169        // generate random cases if there's no fixtures
170        if self.fixtures.is_empty() {
171            return self.generate_random_tree(runner);
172        }
173
174        // Generate value tree from fixture.
175        let fixture = &self.fixtures[runner.rng().random_range(0..self.fixtures.len())];
176        if let Some(int_fixture) = fixture.as_int()
177            && int_fixture.1 == self.bits
178        {
179            return Ok(IntValueTree::new(clamp(int_fixture.0, self.effective_max()), false));
180        }
181
182        // If fixture is not a valid type, raise error and generate random value.
183        error!("{:?} is not a valid {} fixture", fixture, DynSolType::Int(self.bits));
184        self.generate_random_tree(runner)
185    }
186
187    fn generate_random_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
188        let rng = runner.rng();
189
190        // generate random number of bits uniformly
191        let bits = rng.random_range(0..=self.bits);
192
193        if bits == 0 {
194            return Ok(IntValueTree::new(I256::ZERO, false));
195        }
196
197        // init 2 128-bit randoms
198        let mut higher: u128 = rng.random_range(0..=u128::MAX);
199        let mut lower: u128 = rng.random_range(0..=u128::MAX);
200
201        // cut 2 randoms according to bits size
202        match bits - 1 {
203            x if x < 128 => {
204                lower &= (1u128 << x) - 1;
205                higher = 0;
206            }
207            x if (128..256).contains(&x) => higher &= (1u128 << (x - 128)) - 1,
208            _ => {}
209        };
210
211        // init I256 from 2 randoms
212        let mut inner: [u64; 4] = [0; 4];
213        let mask64 = (1 << 65) - 1;
214        inner[0] = (lower & mask64) as u64;
215        inner[1] = (lower >> 64) as u64;
216        inner[2] = (higher & mask64) as u64;
217        inner[3] = (higher >> 64) as u64;
218
219        // we have a small bias here, i.e. intN::min will never be generated
220        // but it's ok since it's generated in `fn generate_edge_tree(...)`
221        let sign = if rng.random::<bool>() { Sign::Positive } else { Sign::Negative };
222        let (start, _) = I256::overflowing_from_sign_and_abs(sign, U256::from_limbs(inner));
223
224        Ok(IntValueTree::new(clamp(start, self.effective_max()), false))
225    }
226}
227
228impl Strategy for IntStrategy {
229    type Tree = IntValueTree;
230    type Value = I256;
231
232    fn new_tree(&self, runner: &mut TestRunner) -> NewTree<Self> {
233        let total_weight = self.random_weight + self.fixtures_weight + self.edge_weight;
234        let bias = runner.rng().random_range(0..total_weight);
235        // randomly select one of 3 strategies
236        match bias {
237            x if x < self.edge_weight => self.generate_edge_tree(runner),
238            x if x < self.edge_weight + self.fixtures_weight => self.generate_fixtures_tree(runner),
239            _ => self.generate_random_tree(runner),
240        }
241    }
242}
243
244#[cfg(test)]
245mod tests {
246    use crate::strategies::int::IntValueTree;
247    use alloy_primitives::I256;
248    use proptest::strategy::ValueTree;
249
250    #[test]
251    fn test_int_tree_complicate_should_not_overflow() {
252        let mut int_tree = IntValueTree::new(I256::MAX, false);
253        assert_eq!(int_tree.hi, I256::MAX);
254        assert_eq!(int_tree.curr, I256::MAX);
255        int_tree.complicate();
256        assert_eq!(int_tree.lo, I256::MAX);
257
258        let mut int_tree = IntValueTree::new(I256::MIN, false);
259        assert_eq!(int_tree.hi, I256::MIN);
260        assert_eq!(int_tree.curr, I256::MIN);
261        int_tree.complicate();
262        assert_eq!(int_tree.lo, I256::MIN);
263    }
264}
foundry_evm_fuzz/strategies/int.rs

foundry_evm_fuzz/strategies/
int.rs
