foundry_evm_fuzz/strategies/
int.rs

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

foundry_evm_fuzz/strategies/
int.rs
