1use alloy_primitives::{
2 Address, U256,
3 map::{Entry, HashMap},
4};
5use core::fmt;
6use revm::{
7 Inspector,
8 bytecode::opcode,
9 context::{ContextTr, JournalTr},
10 interpreter::{
11 Interpreter,
12 interpreter_types::{InputsTr, Jumps},
13 },
14};
15
16pub(crate) const MAX_EDGE_COUNT: usize = 65536;
18
19const MAX_CMP_LOG_SITES: usize = 1024;
21
22const MAX_CMP_OBSERVATIONS_PER_SITE: u8 = 8;
25
26#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
28pub enum EdgeCovKind {
29 #[default]
31 CollisionFree,
32 Hash,
34}
35
36#[derive(Clone, Copy, Debug, Eq, PartialEq)]
38pub struct EdgeCovConfig {
39 pub kind: EdgeCovKind,
41 pub include_call_depth: bool,
43}
44
45impl EdgeCovConfig {
46 pub const fn new(kind: EdgeCovKind, include_call_depth: bool) -> Self {
48 Self { kind, include_call_depth }
49 }
50
51 pub const fn legacy_hash_ids() -> Self {
53 Self::new(EdgeCovKind::Hash, false)
54 }
55}
56
57impl Default for EdgeCovConfig {
58 fn default() -> Self {
59 Self::new(EdgeCovKind::CollisionFree, false)
60 }
61}
62
63impl From<&foundry_config::FuzzCorpusConfig> for EdgeCovConfig {
64 fn from(corpus: &foundry_config::FuzzCorpusConfig) -> Self {
65 let kind = if corpus.evm_edge_coverage_collision_free() {
66 EdgeCovKind::CollisionFree
67 } else {
68 EdgeCovKind::Hash
69 };
70 Self::new(kind, corpus.evm_edge_coverage_include_call_depth())
71 }
72}
73
74#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
76pub struct CmpOperands {
77 pub op1: U256,
79 pub op2: U256,
81 pub pc: usize,
83 pub address: Address,
85 pub opcode: u8,
87}
88
89#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
90pub struct EdgeKey {
91 pub address: Address,
92 pub depth: Option<usize>,
93 pub pc: usize,
94 pub jump_dest: U256,
95}
96
97impl EdgeKey {
98 fn new(
99 address: Address,
100 depth: usize,
101 pc: usize,
102 jump_dest: U256,
103 include_depth: bool,
104 ) -> Self {
105 Self { address, depth: include_depth.then_some(depth), pc, jump_dest }
106 }
107}
108
109#[derive(Clone, Debug, Default)]
110pub struct EdgeIndexMap {
111 edge_indices: HashMap<EdgeKey, usize>,
112 next_index: usize,
113}
114
115impl EdgeIndexMap {
116 #[inline]
117 pub fn edge_index(&mut self, edge: EdgeKey) -> usize {
118 match self.edge_indices.entry(edge) {
119 Entry::Occupied(entry) => *entry.get(),
120 Entry::Vacant(entry) => {
121 let index = self.next_index;
122 self.next_index += 1;
123 entry.insert(index);
124 index
125 }
126 }
127 }
128
129 pub const fn edge_count(&self) -> usize {
130 self.next_index
131 }
132}
133
134#[derive(Clone, Copy, Debug, Eq, PartialEq)]
135pub struct EdgeCovHit {
136 pub edge: EdgeKey,
137 pub count: u8,
138}
139
140#[derive(Clone, Debug, Eq, PartialEq)]
141pub enum EdgeCoverage {
142 Hash(Vec<u8>),
143 CollisionFree(Vec<EdgeCovHit>),
144}
145
146impl EdgeCoverage {
147 pub fn is_empty(&self) -> bool {
148 match self {
149 Self::Hash(hitcount) => hitcount.iter().all(|&count| count == 0),
150 Self::CollisionFree(hits) => hits.is_empty(),
151 }
152 }
153}
154
155#[derive(Clone)]
161pub struct EdgeCovInspector {
162 hitcount: Vec<u8>,
164 config: EdgeCovConfig,
166 collect_edges: bool,
169 dense_hitcount: HashMap<EdgeKey, u8>,
171 cmp_log: Option<Vec<CmpOperands>>,
173 cmp_site_counts: HashMap<CmpSiteKey, u8>,
174}
175
176impl fmt::Debug for EdgeCovInspector {
177 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178 f.debug_struct("EdgeCovInspector")
179 .field("capacity", &self.hitcount.len())
180 .field("edges", &self.edge_count())
181 .field("config", &self.config)
182 .field("collect_edges", &self.collect_edges)
183 .finish()
184 }
185}
186
187impl EdgeCovInspector {
188 pub fn new() -> Self {
190 Self::with_config(EdgeCovConfig::default())
191 }
192
193 pub fn with_cmp_log() -> Self {
195 let mut inspector = Self::new();
196 inspector.enable_cmp_log(true);
197 inspector
198 }
199
200 pub fn with_cmp_log_only() -> Self {
202 let mut inspector = Self::new();
203 inspector.collect_edges = false;
204 inspector.enable_cmp_log(true);
205 inspector
206 }
207
208 pub fn with_config(config: EdgeCovConfig) -> Self {
213 let hitcount = match config.kind {
214 EdgeCovKind::Hash => vec![0; MAX_EDGE_COUNT],
215 EdgeCovKind::CollisionFree => Vec::new(),
216 };
217 Self {
218 hitcount,
219 config,
220 collect_edges: true,
221 dense_hitcount: HashMap::default(),
222 cmp_log: None,
223 cmp_site_counts: HashMap::default(),
224 }
225 }
226
227 pub fn enable_cmp_log(&mut self, yes: bool) {
229 if yes {
230 self.cmp_log.get_or_insert_with(|| Vec::with_capacity(MAX_CMP_LOG_SITES));
231 } else {
232 self.cmp_log = None;
233 self.cmp_site_counts.clear();
234 }
235 }
236
237 pub fn reset(&mut self) {
239 match self.config.kind {
240 EdgeCovKind::CollisionFree => self.dense_hitcount.clear(),
241 EdgeCovKind::Hash => self.hitcount.fill(0),
242 }
243 if let Some(cmp_log) = &mut self.cmp_log {
244 cmp_log.clear();
245 }
246 self.cmp_site_counts.clear();
247 }
248
249 pub const fn get_cmp_log(&self) -> &[CmpOperands] {
251 match &self.cmp_log {
252 Some(cmp_log) => cmp_log.as_slice(),
253 None => &[],
254 }
255 }
256
257 pub fn into_parts(mut self) -> (EdgeCoverage, Vec<CmpOperands>) {
259 let cmp_log = self.cmp_log.take().unwrap_or_default();
260 (self.into(), cmp_log)
261 }
262
263 pub fn edge_count(&self) -> usize {
265 self.dense_hitcount.len()
266 }
267
268 fn store_hit(&mut self, address: Address, depth: usize, pc: usize, jump_dest: U256) {
270 if !self.collect_edges {
271 return;
272 }
273
274 let edge_id = match self.config.kind {
275 EdgeCovKind::CollisionFree => {
276 self.store_dense_hit(address, depth, pc, jump_dest);
277 return;
278 }
279 EdgeCovKind::Hash => self.hash_edge_id(address, depth, pc, jump_dest),
280 };
281 self.hitcount[edge_id] = self.hitcount[edge_id].wrapping_add(1).max(1);
282 }
283
284 fn store_dense_hit(&mut self, address: Address, depth: usize, pc: usize, jump_dest: U256) {
285 let key = EdgeKey::new(address, depth, pc, jump_dest, self.config.include_call_depth);
286 let count = self.dense_hitcount.entry(key).or_default();
287 *count = count.wrapping_add(1).max(1);
288 }
289
290 fn hash_edge_id(
291 &mut self,
292 address: Address,
293 depth: usize,
294 pc: usize,
295 jump_dest: U256,
296 ) -> usize {
297 let mut hash = FNV_OFFSET_BASIS;
298 hash_bytes(&mut hash, address.as_slice());
299 if self.config.include_call_depth {
300 hash_bytes(&mut hash, &depth.to_le_bytes());
301 }
302 hash_bytes(&mut hash, &pc.to_le_bytes());
303 hash_bytes(&mut hash, &jump_dest.to_be_bytes::<32>());
304 (hash % self.hitcount.len() as u64) as usize
307 }
308
309 #[cfg(test)]
310 fn dense_hits(&self) -> Vec<EdgeCovHit> {
311 let mut hits = self
312 .dense_hitcount
313 .iter()
314 .map(|(&edge, &count)| EdgeCovHit { edge, count })
315 .collect::<Vec<_>>();
316 hits.sort_by_key(|hit| hit.edge);
317 hits
318 }
319
320 fn store_cmp(&mut self, cmp: CmpOperands) {
322 let Some(cmp_log) = &mut self.cmp_log else {
323 return;
324 };
325
326 let site = CmpSiteKey::new(&cmp);
327 if let Some(count) = self.cmp_site_counts.get_mut(&site) {
328 if *count >= MAX_CMP_OBSERVATIONS_PER_SITE {
329 return;
330 }
331 *count += 1;
332 cmp_log.push(cmp);
333 } else if self.cmp_site_counts.len() < MAX_CMP_LOG_SITES {
334 self.cmp_site_counts.insert(site, 1);
335 cmp_log.push(cmp);
336 }
337 }
338
339 #[cold]
340 fn do_step<CTX>(&mut self, interp: &mut Interpreter, context: &mut CTX)
341 where
342 CTX: ContextTr,
343 {
344 let address = interp.input.target_address();
345 let depth = context.journal_ref().depth();
346 let current_pc = interp.bytecode.pc();
347
348 match interp.bytecode.opcode() {
349 opcode::JUMP => {
350 if let Ok(jump_dest) = interp.stack.peek(0) {
352 self.store_hit(address, depth, current_pc, jump_dest);
353 }
354 }
355 opcode::JUMPI => {
356 if let Ok(stack_value) = interp.stack.peek(1) {
357 let jump_dest = if stack_value.is_zero() {
358 Ok(U256::from(current_pc + 1))
360 } else {
361 interp.stack.peek(0)
363 };
364
365 if let Ok(jump_dest) = jump_dest {
366 self.store_hit(address, depth, current_pc, jump_dest);
367 }
368 }
369 }
370 _ => {
371 }
373 }
374 }
375
376 #[cold]
377 fn do_cmp_step(&mut self, interp: &mut Interpreter) {
378 if self.cmp_log.is_none() {
379 return;
380 }
381
382 let address = interp.input.target_address();
383 let current_pc = interp.bytecode.pc();
384
385 match interp.bytecode.opcode() {
386 op @ (opcode::EQ | opcode::LT | opcode::SLT | opcode::GT | opcode::SGT) => {
387 if let (Ok(op1), Ok(op2)) = (interp.stack.peek(0), interp.stack.peek(1)) {
388 self.store_cmp(CmpOperands { op1, op2, pc: current_pc, address, opcode: op });
389 }
390 }
391 op @ opcode::ISZERO => {
392 if let Ok(op1) = interp.stack.peek(0) {
393 self.store_cmp(CmpOperands {
394 op1,
395 op2: U256::ZERO,
396 pc: current_pc,
397 address,
398 opcode: op,
399 });
400 }
401 }
402 _ => {}
403 }
404 }
405}
406
407impl Default for EdgeCovInspector {
408 fn default() -> Self {
409 Self::new()
410 }
411}
412
413impl From<EdgeCovInspector> for EdgeCoverage {
414 fn from(inspector: EdgeCovInspector) -> Self {
415 let EdgeCovInspector { hitcount, config, dense_hitcount, .. } = inspector;
416 match config.kind {
417 EdgeCovKind::CollisionFree => Self::CollisionFree(
422 dense_hitcount
423 .into_iter()
424 .map(|(edge, count)| EdgeCovHit { edge, count })
425 .collect(),
426 ),
427 EdgeCovKind::Hash => Self::Hash(hitcount),
428 }
429 }
430}
431
432impl<CTX> Inspector<CTX> for EdgeCovInspector
433where
434 CTX: ContextTr,
435{
436 #[inline]
437 fn step(&mut self, interp: &mut Interpreter, context: &mut CTX) {
438 let op = interp.bytecode.opcode();
439 if self.collect_edges && matches!(op, opcode::JUMP | opcode::JUMPI) {
440 self.do_step(interp, context);
441 }
442 if self.cmp_log.is_some()
443 && matches!(
444 op,
445 opcode::EQ | opcode::LT | opcode::GT | opcode::SLT | opcode::SGT | opcode::ISZERO
446 )
447 {
448 self.do_cmp_step(interp);
449 }
450 }
451}
452
453#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
454struct CmpSiteKey {
455 address: Address,
456 pc: usize,
457 opcode: u8,
458}
459
460impl CmpSiteKey {
461 const fn new(cmp: &CmpOperands) -> Self {
462 Self { address: cmp.address, pc: cmp.pc, opcode: cmp.opcode }
463 }
464}
465
466const FNV_OFFSET_BASIS: u64 = 0xcbf29ce484222325;
467const FNV_PRIME: u64 = 0x100000001b3;
468
469fn hash_bytes(hash: &mut u64, bytes: &[u8]) {
470 for byte in bytes {
471 *hash ^= u64::from(*byte);
472 *hash = hash.wrapping_mul(FNV_PRIME);
473 }
474}
475
476#[cfg(test)]
477mod tests {
478 use super::*;
479
480 fn dense_counts(inspector: &EdgeCovInspector) -> Vec<u8> {
481 inspector.dense_hits().into_iter().map(|hit| hit.count).collect()
482 }
483
484 #[test]
485 fn cmp_operands_defaults_and_clones() {
486 let cmp = CmpOperands {
487 op1: U256::from(123),
488 op2: U256::from(456),
489 pc: 42,
490 address: Address::repeat_byte(0xaa),
491 opcode: opcode::EQ,
492 };
493
494 assert_eq!(cmp.op1, U256::from(123));
495 assert_eq!(cmp.op2, U256::from(456));
496 assert_eq!(cmp.pc, 42);
497
498 assert_eq!(CmpOperands::default(), CmpOperands::default());
499 let cloned = cmp;
500 assert_eq!(cloned, cmp);
501 }
502
503 #[test]
504 fn cmp_log_starts_empty_and_is_returned_by_into_parts() {
505 let inspector = EdgeCovInspector::new();
506
507 assert!(inspector.get_cmp_log().is_empty());
508
509 let (coverage, cmp_log) = inspector.into_parts();
510 assert_eq!(coverage, EdgeCoverage::CollisionFree(Vec::new()));
511 assert!(cmp_log.is_empty());
512 }
513
514 #[test]
515 fn cmp_log_only_does_not_collect_edges() {
516 let mut inspector = EdgeCovInspector::with_cmp_log_only();
517 let addr = Address::ZERO;
518
519 inspector.store_hit(addr, 0, 0, U256::ONE);
520 inspector.store_cmp(CmpOperands {
521 op1: U256::from(123),
522 op2: U256::from(456),
523 pc: 42,
524 address: addr,
525 opcode: opcode::EQ,
526 });
527
528 let (coverage, cmp_log) = inspector.into_parts();
529 assert_eq!(coverage, EdgeCoverage::CollisionFree(Vec::new()));
530 assert_eq!(cmp_log.len(), 1);
531 }
532
533 #[test]
534 fn collision_free_ids() {
535 let mut inspector = EdgeCovInspector::new();
536 let addr = Address::ZERO;
537
538 inspector.store_hit(addr, 0, 0, U256::from(10));
539 inspector.store_hit(addr, 0, 0, U256::from(20));
540 inspector.store_hit(addr, 0, 1, U256::from(10));
541
542 assert_eq!(inspector.edge_count(), 3);
543 assert_eq!(dense_counts(&inspector), [1, 1, 1]);
544 }
545
546 #[test]
547 fn same_edge_increments_same_dense_slot() {
548 let mut inspector = EdgeCovInspector::new();
549 let addr = Address::ZERO;
550
551 for _ in 0..5 {
552 inspector.store_hit(addr, 0, 42, U256::from(100));
553 }
554
555 assert_eq!(inspector.edge_count(), 1);
556 assert_eq!(dense_counts(&inspector), [5]);
557 }
558
559 #[test]
560 fn edge_index_map_keeps_indices_stable() {
561 let addr = Address::ZERO;
562 let mut indices = EdgeIndexMap::default();
563 let first = EdgeKey::new(addr, 0, 0, U256::from(10), false);
564 let second = EdgeKey::new(addr, 0, 0, U256::from(20), false);
565
566 assert_eq!(indices.edge_index(first), 0);
567 assert_eq!(indices.edge_index(second), 1);
568 assert_eq!(indices.edge_index(first), 0);
569 assert_eq!(indices.edge_count(), 2);
570 }
571
572 #[test]
573 fn hitcount_neverzero_on_wrap() {
574 let mut inspector = EdgeCovInspector::new();
575 let addr = Address::ZERO;
576
577 for _ in 0..256 {
578 inspector.store_hit(addr, 0, 0, U256::ONE);
579 }
580
581 assert_eq!(inspector.edge_count(), 1);
582 assert_eq!(dense_counts(&inspector), [1]);
583 }
584
585 #[test]
586 fn reset_clears_dense_hitcounts() {
587 let mut inspector = EdgeCovInspector::new();
588 let addr = Address::ZERO;
589
590 inspector.store_hit(addr, 0, 0, U256::ONE);
591 inspector.store_hit(addr, 0, 0, U256::from(2));
592 assert_eq!(inspector.edge_count(), 2);
593 assert_eq!(dense_counts(&inspector), [1, 1]);
594
595 inspector.reset();
596 assert_eq!(inspector.edge_count(), 0);
597 assert!(inspector.dense_hits().is_empty());
598
599 inspector.store_hit(addr, 0, 0, U256::ONE);
600 assert_eq!(inspector.edge_count(), 1);
601 assert_eq!(dense_counts(&inspector), [1]);
602 }
603
604 #[test]
605 fn hash_ids_use_stable_encoding() {
606 let mut inspector = EdgeCovInspector::with_config(EdgeCovConfig::legacy_hash_ids());
607 let addr = Address::ZERO;
608 let pc = 42;
609 let jump_dest = U256::from(100);
610
611 inspector.store_hit(addr, 0, pc, jump_dest);
612
613 assert_eq!(inspector.hitcount[65235], 1);
614 assert_eq!(inspector.hitcount.iter().filter(|&&count| count != 0).count(), 1);
615 }
616
617 #[test]
618 fn call_depth_option_delineates_same_edge() {
619 let addr = Address::ZERO;
620
621 let mut without_depth = EdgeCovInspector::new();
622 without_depth.store_hit(addr, 0, 0, U256::ONE);
623 without_depth.store_hit(addr, 1, 0, U256::ONE);
624 assert_eq!(without_depth.edge_count(), 1);
625 assert_eq!(dense_counts(&without_depth), [2]);
626
627 let mut with_depth =
628 EdgeCovInspector::with_config(EdgeCovConfig::new(EdgeCovKind::CollisionFree, true));
629 with_depth.store_hit(addr, 0, 0, U256::ONE);
630 with_depth.store_hit(addr, 1, 0, U256::ONE);
631 assert_eq!(with_depth.edge_count(), 2);
632 assert_eq!(dense_counts(&with_depth), [1, 1]);
633 }
634
635 #[test]
636 fn reset_clears_hitcount_and_cmp_log() {
637 let mut inspector = EdgeCovInspector::with_cmp_log();
638
639 inspector.store_hit(Address::ZERO, 0, 0, U256::ONE);
640 inspector.store_cmp(CmpOperands {
641 op1: U256::from(123),
642 op2: U256::from(456),
643 pc: 42,
644 address: Address::ZERO,
645 opcode: opcode::EQ,
646 });
647
648 inspector.reset();
649
650 assert!(inspector.dense_hits().is_empty());
651 assert!(inspector.get_cmp_log().is_empty());
652 }
653
654 #[test]
655 fn cmp_log_is_capped_per_site() {
656 let mut inspector = EdgeCovInspector::with_cmp_log();
657
658 for i in 0..usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) + 1 {
659 inspector.store_cmp(CmpOperands {
660 op1: U256::from(i),
661 op2: U256::from(i + 1),
662 pc: 42,
663 address: Address::ZERO,
664 opcode: opcode::EQ,
665 });
666 }
667
668 assert_eq!(inspector.get_cmp_log().len(), usize::from(MAX_CMP_OBSERVATIONS_PER_SITE));
669 }
670
671 #[test]
672 fn cmp_log_caps_sites_without_starving_later_observations() {
673 let mut inspector = EdgeCovInspector::with_cmp_log();
674
675 for i in 0..usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) * 2 {
676 inspector.store_cmp(CmpOperands {
677 op1: U256::from(i),
678 op2: U256::from(i + 1),
679 pc: 1,
680 address: Address::ZERO,
681 opcode: opcode::EQ,
682 });
683 }
684 inspector.store_cmp(CmpOperands {
685 op1: U256::from(123),
686 op2: U256::from(456),
687 pc: 2,
688 address: Address::ZERO,
689 opcode: opcode::EQ,
690 });
691
692 assert_eq!(inspector.get_cmp_log().len(), usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) + 1);
693 assert_eq!(inspector.get_cmp_log().last().unwrap().pc, 2);
694 }
695}