1use crate::executors::Executor;
16use alloy_primitives::{
17 Address, U256,
18 map::{AddressMap, HashMap, HashSet},
19};
20use evm2::evm::PendingState;
21use foundry_evm_core::{
22 constants::CHEATCODE_ADDRESS, eip2935::is_history_storage_address, evm::FoundryEvmNetwork,
23};
24use foundry_evm_fuzz::BasicTxDetails;
25use proptest::{prelude::Rng, test_runner::TestRunner};
26use std::{
27 hash::{BuildHasher, BuildHasherDefault, DefaultHasher},
28 sync::Arc,
29};
30
31const MAX_SNAPSHOTS: usize = 64;
33const SNAPSHOT_SLOT_BUDGET: usize = 1 << 20;
37const MAX_PREFIX_DEPTHS: usize = 4;
39const MAX_SET_VALUES: usize = 64;
41const MIN_LIVENESS: f64 = 0.01;
43
44const COMPUTED_SLOT: U256 = U256::from_limbs([0, 0, 1, 0]);
46
47fn log2_bin(value: U256) -> u16 {
50 if value.bit(255) { 512 - (!value).bit_len() as u16 } else { value.bit_len() as u16 }
51}
52
53fn storage_slots<FEN: FoundryEvmNetwork>(executor: &Executor<FEN>) -> usize {
55 let lifecycle = executor.backend().lifecycle();
56 let forks = lifecycle.forks();
57 let local = forks.context(None).and_then(|context| context.cache.as_deref());
58 let fork = forks.active().and(lifecycle.active().cache.as_deref());
59 local
61 .into_iter()
62 .chain(fork)
63 .flat_map(|cache| cache.storage.values())
64 .map(|storage| storage.slots.len())
65 .sum()
66}
67
68fn computed_cardinality<FEN: FoundryEvmNetwork>(executor: &Executor<FEN>) -> AddressMap<u64> {
70 executor
73 .backend()
74 .lifecycle()
75 .active()
76 .cache
77 .as_deref()
78 .into_iter()
79 .flat_map(|cache| &cache.storage)
80 .filter_map(|(address, storage)| {
81 let computed = storage
82 .slots
83 .iter()
84 .filter(|(slot, value)| **slot >= COMPUTED_SLOT && !value.is_zero())
85 .count() as u64;
86 (computed > 0).then_some((*address, computed))
87 })
88 .collect()
89}
90
91#[derive(Clone, Copy, Default)]
92struct Energy {
93 picks: u32,
94 finds: u32,
95 calls: u64,
97 reverted: u64,
98}
99
100impl Energy {
101 fn productivity(self) -> f64 {
109 let finds = f64::from(self.finds + 1) / f64::from(self.picks + 1);
110 if self.calls == 0 {
111 return finds;
112 }
113 let success = 1.0 - self.reverted as f64 / self.calls as f64;
114 finds * (success * success).max(MIN_LIVENESS)
115 }
116}
117
118struct Snapshot<FEN: FoundryEvmNetwork> {
119 executor: Executor<FEN>,
120 prefix: Arc<[BasicTxDetails]>,
121 cardinality: AddressMap<u64>,
123 slots: usize,
125 features: Vec<u64>,
127 energy: Energy,
128}
129
130#[derive(Clone, Copy)]
132enum Start {
133 Setup,
134 Snapshot(usize),
135}
136
137pub(super) struct RunStart<FEN: FoundryEvmNetwork> {
139 pub executor: Executor<FEN>,
140 pub prefix: Arc<[BasicTxDetails]>,
141 pub state: Option<u64>,
143}
144
145pub(super) struct StateSnapshots<FEN: FoundryEvmNetwork> {
147 slot_budget: usize,
149 max_prefix: usize,
150 hasher: BuildHasherDefault<DefaultHasher>,
152 hits: HashMap<u64, u32>,
154 slot_values: HashMap<(Address, U256), HashSet<U256>>,
156 setup: Energy,
157 snapshots: Vec<Snapshot<FEN>>,
158 current: Start,
159 setup_cardinality: AddressMap<u64>,
161 cardinality: AddressMap<u64>,
163 run_found: bool,
165}
166
167impl<FEN: FoundryEvmNetwork> StateSnapshots<FEN> {
168 pub(super) fn new(depth: u32, setup: &Executor<FEN>, workers: usize) -> Self {
170 Self {
171 slot_budget: SNAPSHOT_SLOT_BUDGET / workers.max(1),
172 max_prefix: (depth as usize).saturating_mul(MAX_PREFIX_DEPTHS),
173 hasher: BuildHasherDefault::default(),
174 hits: HashMap::default(),
175 slot_values: HashMap::default(),
176 setup: Energy::default(),
177 snapshots: Vec::new(),
178 current: Start::Setup,
179 setup_cardinality: computed_cardinality(setup),
180 cardinality: AddressMap::default(),
181 run_found: false,
182 }
183 }
184
185 fn rarity(&self, snapshot: &Snapshot<FEN>) -> f64 {
186 snapshot
187 .features
188 .iter()
189 .map(|feature| 1.0 / f64::from(self.hits.get(feature).copied().unwrap_or(1).max(1)))
190 .sum()
191 }
192
193 fn weight(&self, snapshot: &Snapshot<FEN>) -> f64 {
194 self.rarity(snapshot) * snapshot.energy.productivity()
195 }
196
197 pub(super) fn start(
199 &mut self,
200 runner: &mut TestRunner,
201 setup: &Executor<FEN>,
202 ) -> RunStart<FEN> {
203 self.run_found = false;
204 self.current = self.pick(runner);
205 match self.current {
206 Start::Setup => self.start_from_setup(setup),
207 Start::Snapshot(index) => {
208 let snapshot = &mut self.snapshots[index];
209 snapshot.energy.picks += 1;
210 self.cardinality.clone_from(&snapshot.cardinality);
211 RunStart {
212 executor: snapshot.executor.clone(),
213 prefix: snapshot.prefix.clone(),
214 state: snapshot.features.first().copied(),
215 }
216 }
217 }
218 }
219
220 fn pick(&self, runner: &mut TestRunner) -> Start {
221 if self.snapshots.is_empty() {
222 return Start::Setup;
223 }
224 let setup = self.setup.productivity();
227 let weights = self.snapshots.iter().map(|s| self.weight(s)).collect::<Vec<_>>();
228 let total = setup + weights.iter().sum::<f64>();
229 let mut point = runner.rng().random::<f64>() * total;
230 if point < setup {
231 return Start::Setup;
232 }
233 point -= setup;
234 for (index, weight) in weights.iter().enumerate() {
235 if point < *weight {
236 return Start::Snapshot(index);
237 }
238 point -= weight;
239 }
240 Start::Snapshot(self.snapshots.len() - 1)
241 }
242
243 pub(super) fn start_from_setup(&mut self, setup: &Executor<FEN>) -> RunStart<FEN> {
245 self.run_found = false;
246 self.current = Start::Setup;
247 self.setup.picks += 1;
248 self.cardinality.clone_from(&self.setup_cardinality);
249 RunStart { executor: setup.clone(), prefix: Arc::from([]), state: None }
250 }
251
252 fn feature(&self, parts: impl std::hash::Hash) -> u64 {
253 self.hasher.hash_one(parts)
254 }
255
256 pub(super) fn observe(&mut self, changeset: &PendingState) -> Vec<u64> {
259 self.observe_writes(changeset.account_changes().map(|changes| {
260 let writes = changes
261 .storage
262 .changed_slots()
263 .map(|(slot, value)| (*slot, value.original, value.current));
264 (changes.address, writes)
265 }))
266 }
267
268 fn observe_writes(
270 &mut self,
271 changeset: impl IntoIterator<Item = (Address, impl IntoIterator<Item = (U256, U256, U256)>)>,
272 ) -> Vec<u64> {
273 let mut features = Vec::new();
274 for (address, storage) in changeset {
275 let address = &address;
276 if *address == CHEATCODE_ADDRESS || is_history_storage_address(address) {
279 continue;
280 }
281 let mut cardinality_changed = false;
282 let mut writes = storage
286 .into_iter()
287 .filter(|(_, original, present)| original != present)
288 .map(|(slot, original, present)| {
289 let computed = slot >= COMPUTED_SLOT;
290 (if computed { U256::MAX } else { slot }, computed, original, present)
291 })
292 .collect::<Vec<_>>();
293 writes.sort_unstable_by_key(|(slot_key, _, _, present)| (*slot_key, *present));
294 for (slot_key, computed, original, present) in writes {
295 if computed && original.is_zero() != present.is_zero() {
296 let count = self.cardinality.entry(*address).or_default();
297 if present.is_zero() {
298 *count = count.saturating_sub(1);
299 } else {
300 *count += 1;
301 }
302 cardinality_changed = true;
303 }
304 let values = self.slot_values.entry((*address, slot_key)).or_default();
305 if values.len() <= MAX_SET_VALUES {
306 values.insert(present);
307 }
308 let bin = if values.len() <= MAX_SET_VALUES {
309 (0u8, present)
310 } else {
311 (1, U256::from(log2_bin(present)))
312 };
313 features.push(self.feature((address, slot_key, bin)));
314 }
315 if cardinality_changed {
316 let count = self.cardinality.get(address).copied().unwrap_or_default();
317 features.push(self.feature((address, 2u8, 64 - count.leading_zeros())));
318 }
319 }
320 let mut novel = Vec::new();
321 for feature in features {
322 let hits = self.hits.entry(feature).or_default();
323 if *hits == 0 {
324 novel.push(feature);
325 }
326 *hits = hits.saturating_add(1);
327 }
328 novel.sort_unstable();
329 novel.dedup();
330 if !novel.is_empty() {
331 self.run_found = true;
332 }
333 novel
334 }
335
336 pub(super) fn capture(
338 &mut self,
339 executor: &Executor<FEN>,
340 inputs: &[BasicTxDetails],
341 novel: Vec<u64>,
342 ) {
343 if novel.is_empty() || inputs.is_empty() || inputs.len() > self.max_prefix {
344 return;
345 }
346 let slots = storage_slots(executor);
347 let mut total = self.snapshots.iter().map(|snapshot| snapshot.slots).sum::<usize>();
348 while self.snapshots.len() >= 2
351 && (self.snapshots.len() >= MAX_SNAPSHOTS || total + slots > self.slot_budget)
352 {
353 let current = match self.current {
354 Start::Snapshot(index) => Some(index),
355 Start::Setup => None,
356 };
357 let Some(weakest) = self
358 .snapshots
359 .iter()
360 .enumerate()
361 .filter(|(index, _)| current != Some(*index))
362 .min_by(|(_, a), (_, b)| self.weight(a).total_cmp(&self.weight(b)))
363 .map(|(index, _)| index)
364 else {
365 break;
366 };
367 total -= self.snapshots.remove(weakest).slots;
368 if let Start::Snapshot(index) = &mut self.current
369 && *index > weakest
370 {
371 *index -= 1;
372 }
373 }
374 self.snapshots.push(Snapshot {
375 executor: executor.clone(),
376 prefix: Arc::from(inputs),
377 cardinality: self.cardinality.clone(),
378 slots,
379 features: novel,
380 energy: Energy::default(),
381 });
382 }
383
384 pub(super) fn finish_run(&mut self, new_coverage: bool, calls: u64, reverted: u64) {
387 let energy = match self.current {
388 Start::Setup => &mut self.setup,
389 Start::Snapshot(index) => match self.snapshots.get_mut(index) {
390 Some(snapshot) => &mut snapshot.energy,
391 None => return,
392 },
393 };
394 energy.calls += calls;
395 energy.reverted += reverted;
396 if new_coverage || self.run_found {
397 energy.finds += 1;
398 }
399 }
400}
401
402#[cfg(test)]
403mod tests {
404 use super::*;
405 use crate::executors::{ExecutorBuilder, test_executor};
406 use alloy_primitives::Bytes;
407 use foundry_evm_core::{
408 eip2935::HISTORY_STORAGE_ADDRESS,
409 evm::{EthEvmNetwork, ExecutionPhase},
410 fork::CreateFork,
411 opts::EvmOpts,
412 };
413 use foundry_evm_fuzz::CallDetails;
414
415 type Writes = Vec<(Address, Vec<(U256, U256, U256)>)>;
416
417 fn write(slot: U256, original: U256, present: U256) -> Writes {
418 vec![(Address::repeat_byte(0x11), vec![(slot, original, present)])]
419 }
420
421 fn executor() -> Executor<EthEvmNetwork> {
422 test_executor(ExecutorBuilder::default(), Default::default())
423 }
424
425 fn snapshots() -> StateSnapshots<EthEvmNetwork> {
426 StateSnapshots::new(10, &executor(), 1)
427 }
428
429 #[test]
430 fn small_value_sets_stay_exact_then_bin_by_magnitude() {
431 let mut snapshots = snapshots();
432 let slot = U256::from(3);
433 for value in 1..=MAX_SET_VALUES as u64 {
434 assert!(
435 !snapshots.observe_writes(write(slot, U256::ZERO, U256::from(value))).is_empty()
436 );
437 }
438 assert!(!snapshots.observe_writes(write(slot, U256::ZERO, U256::from(1000))).is_empty());
440 assert!(snapshots.observe_writes(write(slot, U256::ZERO, U256::from(1001))).is_empty());
441 assert!(!snapshots.observe_writes(write(slot, U256::ZERO, U256::from(1 << 20))).is_empty());
442 }
443
444 #[test]
445 fn mapping_entries_count_by_log2_cardinality() {
446 let mut snapshots = snapshots();
447 let entry = |i: u64| U256::MAX - U256::from(i);
448 assert!(!snapshots.observe_writes(write(entry(0), U256::ZERO, U256::ONE)).is_empty());
450 assert!(!snapshots.observe_writes(write(entry(1), U256::ZERO, U256::ONE)).is_empty());
452 assert!(snapshots.observe_writes(write(entry(2), U256::ZERO, U256::ONE)).is_empty());
454 assert!(!snapshots.observe_writes(write(entry(3), U256::ZERO, U256::ONE)).is_empty());
455 }
456
457 #[test]
458 fn unchanged_cheatcode_and_history_writes_are_ignored() {
459 let mut snapshots = snapshots();
460 assert!(snapshots.observe_writes(write(U256::ZERO, U256::ONE, U256::ONE)).is_empty());
461 for address in [CHEATCODE_ADDRESS, HISTORY_STORAGE_ADDRESS] {
462 let mut changeset = write(U256::ZERO, U256::ZERO, U256::ONE);
463 changeset[0].0 = address;
464 assert!(snapshots.observe_writes(changeset).is_empty());
465 }
466 }
467
468 #[test]
469 fn reverting_runs_lower_a_states_productivity() {
470 let live = Energy { picks: 4, finds: 2, calls: 400, reverted: 40 };
471 let dead = Energy { picks: 4, finds: 2, calls: 400, reverted: 360 };
472 let untried = Energy { picks: 0, finds: 0, calls: 0, reverted: 0 };
473 assert!(dead.productivity() < live.productivity());
474 let expected_live = 0.6 * 0.81;
475 let expected_dead = 0.6 * MIN_LIVENESS;
476 assert!((live.productivity() - expected_live).abs() < 1e-9);
477 assert!((dead.productivity() - expected_dead).abs() < 1e-9);
478 assert_eq!(untried.productivity(), 1.0);
479 }
480
481 #[test]
482 fn log2_bins_fold_sign() {
483 assert_eq!(log2_bin(U256::ZERO), 0);
484 assert_eq!(log2_bin(U256::from(1)), 1);
485 assert_eq!(log2_bin(U256::from(255)), 8);
486 assert_eq!(log2_bin(U256::MAX), 512);
487 assert_eq!(log2_bin(U256::MAX - U256::from(255)), 504);
488 assert!(log2_bin(U256::MAX) > log2_bin(U256::from(1) << 254));
489 }
490
491 #[test]
492 fn deletions_count_from_setup_entries() {
493 let entry = |i: u64| U256::MAX - U256::from(i);
494 let mut setup = executor();
495 for i in 0..4 {
496 setup.set_storage_slot(Address::repeat_byte(0x11), entry(i), U256::ONE).unwrap();
497 }
498 let mut snapshots = StateSnapshots::new(10, &setup, 1);
499 snapshots.start(&mut TestRunner::deterministic(), &setup);
500 assert!(!snapshots.observe_writes(write(entry(0), U256::ONE, U256::ZERO)).is_empty());
502 assert!(snapshots.observe_writes(write(entry(1), U256::ONE, U256::ZERO)).is_empty());
504 assert!(!snapshots.observe_writes(write(entry(2), U256::ONE, U256::ZERO)).is_empty());
506 assert!(!snapshots.observe_writes(write(entry(3), U256::ONE, U256::ZERO)).is_empty());
507 }
508
509 #[test]
510 fn snapshot_pool_stays_within_slot_budget() {
511 let tx = BasicTxDetails {
512 warp: None,
513 roll: None,
514 sender: Address::ZERO,
515 call_details: CallDetails {
516 target: Address::ZERO,
517 calldata: Bytes::new(),
518 value: None,
519 },
520 };
521 let retained = |pool: &StateSnapshots<EthEvmNetwork>| {
522 pool.snapshots.iter().map(|snapshot| storage_slots(&snapshot.executor)).sum::<usize>()
523 };
524
525 let mut state = executor();
528 let mut pool = StateSnapshots::new(10, &state, 16);
529 for step in 0..16u64 {
530 for slot in 0..1u64 << 11 {
531 let slot = U256::from((step << 11) + slot);
532 state.set_storage_slot(Address::repeat_byte(0x22), slot, U256::ONE).unwrap();
533 }
534 pool.capture(&state, std::slice::from_ref(&tx), vec![step]);
535 assert!(retained(&pool) <= SNAPSHOT_SLOT_BUDGET / 16);
536 assert_eq!(pool.snapshots.last().unwrap().features, [step]);
538 }
539
540 let mut pool = StateSnapshots::new(10, &state, 64);
542 for feature in 1..=3 {
543 pool.capture(&state, std::slice::from_ref(&tx), vec![feature]);
544 }
545 assert_eq!(pool.snapshots.len(), 2);
546 pool.current = Start::Snapshot(0);
548 let start = pool.snapshots[0].features.clone();
549 pool.capture(&state, std::slice::from_ref(&tx), vec![4]);
550 assert_eq!(pool.snapshots[0].features, start);
551 assert_eq!(pool.snapshots[1].features, [4]);
552 }
553
554 #[test]
555 fn features_do_not_depend_on_storage_order_or_mapping_keys() {
556 let entry = |i: u64| U256::MAX - U256::from(i);
557 let outcomes = (0..16)
558 .map(|round| {
559 let mut snapshots = snapshots();
560 for i in 1..MAX_SET_VALUES as u64 {
561 snapshots.observe_writes(write(entry(100 + i), U256::ZERO, U256::from(i)));
562 }
563 let keys = if round % 2 == 0 { [1, 2] } else { [2, 1] };
567 let storage = keys
568 .into_iter()
569 .zip([U256::from(1000), U256::from(1u64 << 40)])
570 .map(|(i, value)| (entry(i), U256::ZERO, value))
571 .collect::<Vec<_>>();
572 let filled = snapshots.observe_writes(vec![(Address::repeat_byte(0x11), storage)]);
573 let next = snapshots.observe_writes(write(
574 entry(3),
575 U256::ZERO,
576 U256::from((1u64 << 40) + 1),
577 ));
578 (filled, next)
579 })
580 .collect::<Vec<_>>();
581 assert!(outcomes.windows(2).all(|pair| pair[0] == pair[1]), "{outcomes:?}");
582 }
583
584 #[tokio::test(flavor = "multi_thread")]
585 async fn fork_entries_count_from_the_active_database() {
586 let entry = |i: u64| U256::MAX - U256::from(i);
587 let mut setup = executor();
588 let persistent = Address::repeat_byte(0x11);
589 for i in 0..4 {
590 setup.set_storage_slot(persistent, entry(i), U256::ONE).unwrap();
591 }
592 let backend = setup.backend_mut();
593 backend.add_persistent_account(persistent);
594 let evm_opts = EvmOpts {
595 fork_url: Some(foundry_test_utils::rpc::next_http_rpc_endpoint()),
596 ..Default::default()
597 };
598 let fork =
599 CreateFork { enable_caching: false, url: evm_opts.fork_url.clone().unwrap(), evm_opts };
600 let mut evm = backend.create_evm();
601 backend.create_select_fork(fork, &mut evm, ExecutionPhase::Boundary).unwrap();
602 backend.park(evm);
603
604 let slots = storage_slots(&setup);
606 let cardinality = computed_cardinality(&setup);
607 assert_eq!(slots, 8);
608 assert_eq!(cardinality, AddressMap::from_iter([(persistent, 4)]));
609 }
610}