Skip to main content

foundry_evm_coverage/
edge.rs

1use alloy_primitives::{
2    Address, U256,
3    map::{AddressHashMap, Entry, HashMap},
4};
5use core::{
6    fmt,
7    hash::{Hash, Hasher},
8};
9use evm2::{
10    EvmTypesHost, Inspector, InspectorConfig, OpcodeSet,
11    interpreter::{Interpreter, op as opcode},
12};
13use foundry_evm_core::{
14    edgecov::{InstrumentedEdgeHit, MAX_CMP_LOG_SITES, MAX_CMP_OBSERVATIONS_PER_SITE},
15    utils::opcodes,
16};
17
18pub use foundry_evm_core::edgecov::CmpOperands;
19
20/// Default capacity for the hitcount buffer.
21pub const MAX_EDGE_COUNT: usize = 65536;
22
23/// Edge coverage collection kind.
24#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
25pub enum EdgeCovKind {
26    /// Assign dense monotonically-increasing indices to unique edges.
27    #[default]
28    CollisionFree,
29    /// Preserve the legacy fixed-size hash ID calculation.
30    Hash,
31}
32
33/// Configuration for [`EdgeCovInspector`].
34#[derive(Clone, Copy, Debug, Eq, PartialEq)]
35pub struct EdgeCovConfig {
36    /// Which edge coverage representation should be collected.
37    pub kind: EdgeCovKind,
38    /// Whether call-frame depth should be included in the edge identity.
39    pub include_call_depth: bool,
40}
41
42impl EdgeCovConfig {
43    /// Creates a new edge coverage configuration.
44    pub const fn new(kind: EdgeCovKind, include_call_depth: bool) -> Self {
45        Self { kind, include_call_depth }
46    }
47
48    /// Legacy fixed-size hash ID configuration.
49    pub const fn legacy_hash_ids() -> Self {
50        Self::new(EdgeCovKind::Hash, false)
51    }
52}
53
54impl Default for EdgeCovConfig {
55    fn default() -> Self {
56        Self::new(EdgeCovKind::CollisionFree, false)
57    }
58}
59
60/// Identity of a control-flow edge: the jump at `pc` in the code running at `address` to
61/// `jump_dest`, optionally split by call depth.
62#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
63pub struct EdgeKey {
64    pub address: Address,
65    pub depth: Option<usize>,
66    pub pc: usize,
67    pub jump_dest: U256,
68}
69
70impl Hash for EdgeKey {
71    /// Hashes a 24-byte digest of the key instead of all 80 bytes.
72    ///
73    /// The map that counts hits is probed once per executed `JUMP` and `JUMPI`, so the hash is
74    /// on the hot path of every coverage-guided run. Equal keys still hash equal because the
75    /// digest is a function of the key; the fields it leaves out only take part in equality.
76    /// The low eight bytes of the address separate distinct contracts, the jump source and
77    /// destination separate edges within a contract, and the rotated depth keeps same-edge keys at
78    /// different depths apart when depth is part of the identity.
79    #[inline]
80    fn hash<H: Hasher>(&self, state: &mut H) {
81        let address = u64::from_be_bytes(self.address.0[12..].try_into().unwrap());
82        let depth = self.depth.map_or(0, |depth| (depth as u64).rotate_left(48));
83        state.write_u64(address);
84        state.write_u64(self.pc as u64 ^ depth);
85        state.write_u64(self.jump_dest.as_limbs()[0]);
86    }
87}
88
89impl EdgeKey {
90    fn new(
91        address: Address,
92        depth: usize,
93        pc: usize,
94        jump_dest: U256,
95        include_depth: bool,
96    ) -> Self {
97        Self { address, depth: include_depth.then_some(depth), pc, jump_dest }
98    }
99}
100
101/// An [`EdgeKey`] in 64 bits: the index of its address among those of the execution, its depth,
102/// its pc and its jump destination.
103///
104/// The map that counts hits is probed once per executed `JUMP` and `JUMPI`, and most hits of a
105/// call insert a new edge, so its entries are 16 bytes instead of the 88 of an [`EdgeKey`] entry.
106#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
107struct PackedEdge(u64);
108
109impl PackedEdge {
110    const ADDRESS_BITS: u32 = 12;
111    const DEPTH_BITS: u32 = 12;
112    const PC_BITS: u32 = 20;
113
114    /// Packs an edge, if every part fits its bits. Code is far smaller than the pc range, so only
115    /// an invalid jump destination or an unusual number of addresses does not fit.
116    #[inline]
117    const fn new(address: usize, depth: usize, pc: usize, jump_dest: U256) -> Option<Self> {
118        let [dest, 0, 0, 0] = jump_dest.into_limbs() else { return None };
119        if address >> Self::ADDRESS_BITS != 0
120            || depth >> Self::DEPTH_BITS != 0
121            || pc >> Self::PC_BITS != 0
122            || dest >> Self::PC_BITS != 0
123        {
124            return None;
125        }
126        let high = (address << Self::DEPTH_BITS | depth) as u64;
127        Some(Self((high << Self::PC_BITS | pc as u64) << Self::PC_BITS | dest))
128    }
129
130    /// Returns the edge this was packed from, given the addresses of the execution.
131    fn key(self, addresses: &[Address], include_depth: bool) -> EdgeKey {
132        let mask = |bits: u32| (1 << bits) - 1;
133        let dest = self.0 & mask(Self::PC_BITS);
134        let pc = (self.0 >> Self::PC_BITS) & mask(Self::PC_BITS);
135        let depth = (self.0 >> (2 * Self::PC_BITS)) & mask(Self::DEPTH_BITS);
136        let address = self.0 >> (2 * Self::PC_BITS + Self::DEPTH_BITS);
137        EdgeKey {
138            address: addresses[address as usize],
139            depth: include_depth.then_some(depth as usize),
140            pc: pc as usize,
141            jump_dest: U256::from(dest),
142        }
143    }
144}
145
146#[derive(Clone, Debug, Default)]
147pub struct EdgeIndexMap {
148    edge_indices: HashMap<EdgeKey, usize>,
149    next_index: usize,
150}
151
152impl EdgeIndexMap {
153    #[inline]
154    pub fn edge_index(&mut self, edge: EdgeKey) -> usize {
155        match self.edge_indices.entry(edge) {
156            Entry::Occupied(entry) => *entry.get(),
157            Entry::Vacant(entry) => {
158                let index = self.next_index;
159                self.next_index += 1;
160                entry.insert(index);
161                index
162            }
163        }
164    }
165
166    pub const fn edge_count(&self) -> usize {
167        self.next_index
168    }
169}
170
171#[derive(Clone, Copy, Debug, Eq, PartialEq)]
172pub struct EdgeCovHit {
173    pub edge: EdgeKey,
174    pub count: u8,
175}
176
177#[derive(Clone, Debug, Eq, PartialEq)]
178pub enum EdgeCoverage {
179    Hash(Vec<u8>),
180    CollisionFree(Vec<EdgeCovHit>),
181    /// Hits of compiler-instrumented edges, keyed by their dense compiler-assigned IDs.
182    Instrumented(Vec<InstrumentedEdgeHit>),
183}
184
185impl EdgeCoverage {
186    pub fn is_empty(&self) -> bool {
187        match self {
188            Self::Hash(hitcount) => hitcount.iter().all(|&count| count == 0),
189            Self::CollisionFree(hits) => hits.is_empty(),
190            Self::Instrumented(hits) => hits.is_empty(),
191        }
192    }
193}
194
195/// An `Inspector` that tracks [edge coverage](https://clang.llvm.org/docs/SanitizerCoverage.html#edge-coverage).
196/// Covered edges will not wrap to zero e.g. a loop edge hit more than 255 will still be retained.
197///
198/// Also tracks comparison operands for CmpLog-style guided fuzzing.
199// see https://github.com/AFLplusplus/AFLplusplus/blob/5777ceaf23f48ae4ceae60e4f3a79263802633c6/instrumentation/afl-llvm-pass.so.cc#L810-L829
200#[derive(Clone)]
201pub struct EdgeCovInspector {
202    /// Map of hitcounts that can be diffed against to determine if new coverage was reached.
203    hitcount: Vec<u8>,
204    /// Configuration for edge ID generation.
205    config: EdgeCovConfig,
206    /// Whether to collect edge hits. Comparison-only consumers keep this off to avoid affecting
207    /// the active coverage guidance source.
208    collect_edges: bool,
209    /// Per-execution dense edge hitcounts, by [`PackedEdge`]. Stable IDs are assigned by the
210    /// corpus history owner.
211    dense_hitcount: HashMap<PackedEdge, u8>,
212    /// Per-execution hitcounts of the edges that do not fit a [`PackedEdge`].
213    wide_hitcount: HashMap<EdgeKey, u8>,
214    /// Addresses of the frames that hit an edge in this execution. A [`PackedEdge`] holds the
215    /// index of its address.
216    addresses: Vec<Address>,
217    /// Index in `addresses` of each address, for the hits that do not come from the latest one.
218    address_indices: AddressHashMap<usize>,
219    /// Index in `addresses` of the address of the latest hit.
220    last_address: usize,
221    /// Comparison operand log for CmpLog-style guided fuzzing.
222    cmp_log: Option<Vec<CmpOperands>>,
223    cmp_site_counts: HashMap<CmpSiteKey, u8>,
224    /// Operands of the last `SUB`, logged when the next `JUMPI` branches on its result.
225    last_sub: Option<CmpOperands>,
226}
227
228impl fmt::Debug for EdgeCovInspector {
229    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
230        f.debug_struct("EdgeCovInspector")
231            .field("capacity", &self.hitcount.len())
232            .field("edges", &self.edge_count())
233            .field("config", &self.config)
234            .field("collect_edges", &self.collect_edges)
235            .finish()
236    }
237}
238
239impl EdgeCovInspector {
240    /// Create a new `EdgeCovInspector` with default configuration and capacity.
241    pub fn new() -> Self {
242        Self::with_config(EdgeCovConfig::default())
243    }
244
245    /// Create a new `EdgeCovInspector` with comparison operand logging enabled.
246    pub fn with_cmp_log() -> Self {
247        let mut inspector = Self::new();
248        inspector.enable_cmp_log(true);
249        inspector
250    }
251
252    /// Create a comparison-operand inspector without collecting EVM edge hits.
253    pub fn with_cmp_log_only() -> Self {
254        let mut inspector = Self::new();
255        inspector.collect_edges = false;
256        inspector.enable_cmp_log(true);
257        inspector
258    }
259
260    /// Create a new `EdgeCovInspector` with the given configuration.
261    ///
262    /// [`EdgeCovKind::Hash`] preallocates a fixed-size bitmap;
263    /// [`EdgeCovKind::CollisionFree`] grows its dense map on demand.
264    pub fn with_config(config: EdgeCovConfig) -> Self {
265        let hitcount = match config.kind {
266            EdgeCovKind::Hash => vec![0; MAX_EDGE_COUNT],
267            EdgeCovKind::CollisionFree => Vec::new(),
268        };
269        Self {
270            hitcount,
271            config,
272            collect_edges: true,
273            dense_hitcount: HashMap::default(),
274            wide_hitcount: HashMap::default(),
275            addresses: Vec::new(),
276            address_indices: AddressHashMap::default(),
277            last_address: 0,
278            cmp_log: None,
279            cmp_site_counts: HashMap::default(),
280            last_sub: None,
281        }
282    }
283
284    /// Set whether to collect comparison operand logs.
285    pub fn enable_cmp_log(&mut self, yes: bool) {
286        if yes {
287            self.cmp_log.get_or_insert_with(|| Vec::with_capacity(MAX_CMP_LOG_SITES));
288        } else {
289            self.cmp_log = None;
290            self.cmp_site_counts.clear();
291            self.last_sub = None;
292        }
293    }
294
295    /// Reset the hitcount to zero and clear the comparison log.
296    pub fn reset(&mut self) {
297        match self.config.kind {
298            EdgeCovKind::CollisionFree => {
299                self.dense_hitcount.clear();
300                self.wide_hitcount.clear();
301                self.addresses.clear();
302                self.address_indices.clear();
303                self.last_address = 0;
304            }
305            EdgeCovKind::Hash => self.hitcount.fill(0),
306        }
307        if let Some(cmp_log) = &mut self.cmp_log {
308            cmp_log.clear();
309        }
310        self.cmp_site_counts.clear();
311        self.last_sub = None;
312    }
313
314    /// Get an immutable reference to the comparison operand log.
315    pub const fn get_cmp_log(&self) -> &[CmpOperands] {
316        match &self.cmp_log {
317            Some(cmp_log) => cmp_log.as_slice(),
318            None => &[],
319        }
320    }
321
322    /// Consume the inspector and take ownership of both the hitcount and comparison log.
323    pub fn into_parts(mut self) -> (EdgeCoverage, Vec<CmpOperands>) {
324        let cmp_log = self.cmp_log.take().unwrap_or_default();
325        (self.into(), cmp_log)
326    }
327
328    /// Number of unique collision-free edges discovered so far.
329    pub fn edge_count(&self) -> usize {
330        self.dense_hitcount.len() + self.wide_hitcount.len()
331    }
332
333    /// Mark the edge `(address, depth, pc, jump_dest)` as hit.
334    fn store_hit(&mut self, address: Address, depth: usize, pc: usize, jump_dest: U256) {
335        if !self.collect_edges {
336            return;
337        }
338
339        let edge_id = match self.config.kind {
340            EdgeCovKind::CollisionFree => {
341                self.store_dense_hit(address, depth, pc, jump_dest);
342                return;
343            }
344            EdgeCovKind::Hash => self.hash_edge_id(address, depth, pc, jump_dest),
345        };
346        self.hitcount[edge_id] = self.hitcount[edge_id].wrapping_add(1).max(1);
347    }
348
349    fn store_dense_hit(&mut self, address: Address, depth: usize, pc: usize, jump_dest: U256) {
350        let include_depth = self.config.include_call_depth;
351        let index = self.address_index(address);
352        let packed_depth = if include_depth { depth } else { 0 };
353        let count = match PackedEdge::new(index, packed_depth, pc, jump_dest) {
354            Some(edge) => self.dense_hitcount.entry(edge).or_default(),
355            None => {
356                let key = EdgeKey::new(address, depth, pc, jump_dest, include_depth);
357                self.wide_hitcount.entry(key).or_default()
358            }
359        };
360        *count = count.wrapping_add(1).max(1);
361    }
362
363    /// Returns the index of `address` in the addresses of this execution, adding it if needed.
364    ///
365    /// Consecutive hits mostly come from the same frame, so this compares the latest address
366    /// first and looks the others up by hash, which stays constant per hit when an execution
367    /// visits many contracts.
368    #[inline]
369    fn address_index(&mut self, address: Address) -> usize {
370        if self.addresses.get(self.last_address) != Some(&address) {
371            self.last_address = self.other_address_index(address);
372        }
373        self.last_address
374    }
375
376    /// Returns the index of an address that is not the latest one, adding it if needed.
377    fn other_address_index(&mut self, address: Address) -> usize {
378        let next = self.addresses.len();
379        *self.address_indices.entry(address).or_insert_with(|| {
380            self.addresses.push(address);
381            next
382        })
383    }
384
385    /// Returns the hits of this execution, in no particular order.
386    fn hits(&self) -> impl Iterator<Item = EdgeCovHit> + '_ {
387        let include_depth = self.config.include_call_depth;
388        let dense = self.dense_hitcount.iter().map(move |(edge, &count)| EdgeCovHit {
389            edge: edge.key(&self.addresses, include_depth),
390            count,
391        });
392        dense.chain(self.wide_hitcount.iter().map(|(&edge, &count)| EdgeCovHit { edge, count }))
393    }
394
395    fn hash_edge_id(
396        &mut self,
397        address: Address,
398        depth: usize,
399        pc: usize,
400        jump_dest: U256,
401    ) -> usize {
402        let mut hash = FNV_OFFSET_BASIS;
403        hash_bytes(&mut hash, address.as_slice());
404        if self.config.include_call_depth {
405            hash_bytes(&mut hash, &depth.to_le_bytes());
406        }
407        hash_bytes(&mut hash, &pc.to_le_bytes());
408        hash_bytes(&mut hash, &jump_dest.to_be_bytes::<32>());
409        // The hash is used to index into the hitcount array,
410        // so it must be modulo the map size.
411        (hash % self.hitcount.len() as u64) as usize
412    }
413
414    #[cfg(test)]
415    fn dense_hits(&self) -> Vec<EdgeCovHit> {
416        let mut hits = self.hits().collect::<Vec<_>>();
417        hits.sort_by_key(|hit| hit.edge);
418        hits
419    }
420
421    /// Store comparison operands for CmpLog-style guided fuzzing.
422    fn store_cmp(&mut self, cmp: CmpOperands) {
423        let Some(cmp_log) = &mut self.cmp_log else {
424            return;
425        };
426
427        let site = CmpSiteKey::new(&cmp);
428        if let Some(count) = self.cmp_site_counts.get_mut(&site) {
429            if *count >= MAX_CMP_OBSERVATIONS_PER_SITE {
430                return;
431            }
432            *count += 1;
433            cmp_log.push(cmp);
434        } else if self.cmp_site_counts.len() < MAX_CMP_LOG_SITES {
435            self.cmp_site_counts.insert(site, 1);
436            cmp_log.push(cmp);
437        }
438    }
439
440    /// Logs the last `SUB` as an equality comparison when a `JUMPI` at `address` branches on its
441    /// nonzero result: solc compiles `if (a == b)` to `SUB` + `JUMPI`.
442    fn store_sub_branch(&mut self, condition: U256, address: Address) {
443        if let Some(sub) = self.last_sub.take()
444            && sub.address == address
445            && !condition.is_zero()
446            && condition == sub.op1.wrapping_sub(sub.op2)
447        {
448            self.store_cmp(sub);
449        }
450    }
451
452    fn do_step<T: EvmTypesHost>(&mut self, interp: &Interpreter<'_, '_, T>) {
453        let address = interp.message().destination;
454        // Journal depth of the frame, which counts the top-level frame as 1.
455        let depth = usize::from(interp.message().depth) + 1;
456        let current_pc = interp.pc();
457        let stack = interp.stack();
458
459        match interp.opcode() {
460            opcode::JUMP => {
461                // unconditional jump
462                if let Some(jump_dest) = stack.peek(0) {
463                    self.store_hit(address, depth, current_pc, jump_dest);
464                }
465            }
466            opcode::JUMPI => {
467                if let Some(stack_value) = stack.peek(1) {
468                    let jump_dest = if stack_value.is_zero() {
469                        // fall through
470                        Some(U256::from(current_pc + 1))
471                    } else {
472                        // branch taken
473                        stack.peek(0)
474                    };
475
476                    if let Some(jump_dest) = jump_dest {
477                        self.store_hit(address, depth, current_pc, jump_dest);
478                    }
479                }
480            }
481            _ => {
482                // no-op
483            }
484        }
485    }
486
487    fn do_cmp_step<T: EvmTypesHost>(&mut self, interp: &Interpreter<'_, '_, T>) {
488        if self.cmp_log.is_none() {
489            return;
490        }
491
492        let address = interp.message().destination;
493        let current_pc = interp.pc();
494        let stack = interp.stack();
495
496        match interp.opcode() {
497            op @ (opcode::EQ | opcode::LT | opcode::SLT | opcode::GT | opcode::SGT) => {
498                if let (Some(op1), Some(op2)) = (stack.peek(0), stack.peek(1)) {
499                    self.store_cmp(CmpOperands { op1, op2, pc: current_pc, address, opcode: op });
500                }
501            }
502            op @ opcode::ISZERO => {
503                if let Some(op1) = stack.peek(0) {
504                    self.store_cmp(CmpOperands {
505                        op1,
506                        op2: U256::ZERO,
507                        pc: current_pc,
508                        address,
509                        opcode: op,
510                    });
511                }
512            }
513            op @ opcode::SUB => {
514                if let (Some(op1), Some(op2)) = (stack.peek(0), stack.peek(1)) {
515                    self.last_sub =
516                        Some(CmpOperands { op1, op2, pc: current_pc, address, opcode: op });
517                }
518            }
519            opcode::JUMPI => {
520                if let Some(condition) = stack.peek(1) {
521                    self.store_sub_branch(condition, address);
522                }
523            }
524            _ => {}
525        }
526    }
527}
528
529impl Default for EdgeCovInspector {
530    fn default() -> Self {
531        Self::new()
532    }
533}
534
535impl From<EdgeCovInspector> for EdgeCoverage {
536    fn from(inspector: EdgeCovInspector) -> Self {
537        match inspector.config.kind {
538            // Hits are deliberately not sorted here — this is the per-call drain
539            // path and `merge_edge_coverage` doesn't care about order. Consumers
540            // that need a deterministic order (e.g. `snapshot_edge_fingerprint`)
541            // sort locally.
542            EdgeCovKind::CollisionFree => Self::CollisionFree(inspector.hits().collect()),
543            EdgeCovKind::Hash => Self::Hash(inspector.hitcount),
544        }
545    }
546}
547
548impl<T: EvmTypesHost> Inspector<T> for EdgeCovInspector {
549    fn inspector_config(&self) -> InspectorConfig {
550        let mut steps = OpcodeSet::EMPTY;
551        if self.collect_edges {
552            steps = steps.union(EDGE_OPCODES);
553        }
554        if self.cmp_log.is_some() {
555            steps = steps.union(CMP_OPCODES);
556        }
557        InspectorConfig::new().with_steps(steps)
558    }
559
560    #[inline]
561    fn step(&mut self, interp: &mut Interpreter<'_, '_, T>) {
562        let op = interp.opcode();
563        if self.collect_edges && EDGE_OPCODES.contains(op) {
564            self.do_step(interp);
565        }
566        if self.cmp_log.is_some() && CMP_OPCODES.contains(op) {
567            self.do_cmp_step(interp);
568        }
569    }
570}
571
572/// The instructions at which the inspector records an edge.
573const EDGE_OPCODES: OpcodeSet = opcodes([opcode::JUMP, opcode::JUMPI]);
574
575/// The instructions at which the inspector records comparison operands.
576const CMP_OPCODES: OpcodeSet = opcodes([
577    opcode::EQ,
578    opcode::LT,
579    opcode::GT,
580    opcode::SLT,
581    opcode::SGT,
582    opcode::ISZERO,
583    opcode::SUB,
584    opcode::JUMPI,
585]);
586
587#[derive(Clone, Copy, Debug, PartialEq, Eq)]
588struct CmpSiteKey {
589    address: Address,
590    pc: usize,
591    opcode: u8,
592}
593
594impl Hash for CmpSiteKey {
595    /// Hashes a 16-byte digest of the site, for the same reason as [`EdgeKey`].
596    #[inline]
597    fn hash<H: Hasher>(&self, state: &mut H) {
598        let address = u64::from_be_bytes(self.address.0[12..].try_into().unwrap());
599        state.write_u64(address);
600        state.write_u64(self.pc as u64 ^ u64::from(self.opcode).rotate_left(56));
601    }
602}
603
604impl CmpSiteKey {
605    const fn new(cmp: &CmpOperands) -> Self {
606        Self { address: cmp.address, pc: cmp.pc, opcode: cmp.opcode }
607    }
608}
609
610const FNV_OFFSET_BASIS: u64 = 0xcbf29ce484222325;
611const FNV_PRIME: u64 = 0x100000001b3;
612
613fn hash_bytes(hash: &mut u64, bytes: &[u8]) {
614    for byte in bytes {
615        *hash ^= u64::from(*byte);
616        *hash = hash.wrapping_mul(FNV_PRIME);
617    }
618}
619
620#[cfg(test)]
621mod tests {
622    use super::*;
623    use crate::inspector::tests::{BRANCH, TARGET, inspect};
624    use foundry_evm_core::evm::{FoundryEvmNetwork, TransactionRequestFor};
625
626    fn dense_counts(inspector: &EdgeCovInspector) -> Vec<u8> {
627        inspector.dense_hits().into_iter().map(|hit| hit.count).collect()
628    }
629
630    #[test]
631    fn cmp_operands_defaults_and_clones() {
632        let cmp = CmpOperands {
633            op1: U256::from(123),
634            op2: U256::from(456),
635            pc: 42,
636            address: Address::repeat_byte(0xaa),
637            opcode: opcode::EQ,
638        };
639
640        assert_eq!(cmp.op1, U256::from(123));
641        assert_eq!(cmp.op2, U256::from(456));
642        assert_eq!(cmp.pc, 42);
643
644        assert_eq!(CmpOperands::default(), CmpOperands::default());
645        let cloned = cmp;
646        assert_eq!(cloned, cmp);
647    }
648
649    #[test]
650    fn cmp_log_starts_empty_and_is_returned_by_into_parts() {
651        let inspector = EdgeCovInspector::new();
652
653        assert!(inspector.get_cmp_log().is_empty());
654
655        let (coverage, cmp_log) = inspector.into_parts();
656        assert_eq!(coverage, EdgeCoverage::CollisionFree(Vec::new()));
657        assert!(cmp_log.is_empty());
658    }
659
660    #[test]
661    fn cmp_log_only_does_not_collect_edges() {
662        let mut inspector = EdgeCovInspector::with_cmp_log_only();
663        let addr = Address::ZERO;
664
665        inspector.store_hit(addr, 0, 0, U256::ONE);
666        inspector.store_cmp(CmpOperands {
667            op1: U256::from(123),
668            op2: U256::from(456),
669            pc: 42,
670            address: addr,
671            opcode: opcode::EQ,
672        });
673
674        let (coverage, cmp_log) = inspector.into_parts();
675        assert_eq!(coverage, EdgeCoverage::CollisionFree(Vec::new()));
676        assert_eq!(cmp_log.len(), 1);
677    }
678
679    #[test]
680    fn collision_free_ids() {
681        let mut inspector = EdgeCovInspector::new();
682        let addr = Address::ZERO;
683
684        inspector.store_hit(addr, 0, 0, U256::from(10));
685        inspector.store_hit(addr, 0, 0, U256::from(20));
686        inspector.store_hit(addr, 0, 1, U256::from(10));
687
688        assert_eq!(inspector.edge_count(), 3);
689        assert_eq!(dense_counts(&inspector), [1, 1, 1]);
690    }
691
692    #[test]
693    fn same_edge_increments_same_dense_slot() {
694        let mut inspector = EdgeCovInspector::new();
695        let addr = Address::ZERO;
696
697        for _ in 0..5 {
698            inspector.store_hit(addr, 0, 42, U256::from(100));
699        }
700
701        assert_eq!(inspector.edge_count(), 1);
702        assert_eq!(dense_counts(&inspector), [5]);
703    }
704
705    #[test]
706    fn edge_index_map_keeps_indices_stable() {
707        let addr = Address::ZERO;
708        let mut indices = EdgeIndexMap::default();
709        let first = EdgeKey::new(addr, 0, 0, U256::from(10), false);
710        let second = EdgeKey::new(addr, 0, 0, U256::from(20), false);
711
712        assert_eq!(indices.edge_index(first), 0);
713        assert_eq!(indices.edge_index(second), 1);
714        assert_eq!(indices.edge_index(first), 0);
715        assert_eq!(indices.edge_count(), 2);
716    }
717
718    #[test]
719    fn hitcount_neverzero_on_wrap() {
720        let mut inspector = EdgeCovInspector::new();
721        let addr = Address::ZERO;
722
723        for _ in 0..256 {
724            inspector.store_hit(addr, 0, 0, U256::ONE);
725        }
726
727        assert_eq!(inspector.edge_count(), 1);
728        assert_eq!(dense_counts(&inspector), [1]);
729    }
730
731    #[test]
732    fn reset_clears_dense_hitcounts() {
733        let mut inspector = EdgeCovInspector::new();
734        let addr = Address::ZERO;
735
736        inspector.store_hit(addr, 0, 0, U256::ONE);
737        inspector.store_hit(addr, 0, 0, U256::from(2));
738        assert_eq!(inspector.edge_count(), 2);
739        assert_eq!(dense_counts(&inspector), [1, 1]);
740
741        inspector.reset();
742        assert_eq!(inspector.edge_count(), 0);
743        assert!(inspector.dense_hits().is_empty());
744
745        inspector.store_hit(addr, 0, 0, U256::ONE);
746        assert_eq!(inspector.edge_count(), 1);
747        assert_eq!(dense_counts(&inspector), [1]);
748    }
749
750    #[test]
751    fn hash_ids_use_stable_encoding() {
752        let mut inspector = EdgeCovInspector::with_config(EdgeCovConfig::legacy_hash_ids());
753        let addr = Address::ZERO;
754        let pc = 42;
755        let jump_dest = U256::from(100);
756
757        inspector.store_hit(addr, 0, pc, jump_dest);
758
759        assert_eq!(inspector.hitcount[65235], 1);
760        assert_eq!(inspector.hitcount.iter().filter(|&&count| count != 0).count(), 1);
761    }
762
763    #[test]
764    fn call_depth_option_delineates_same_edge() {
765        let addr = Address::ZERO;
766
767        let mut without_depth = EdgeCovInspector::new();
768        without_depth.store_hit(addr, 0, 0, U256::ONE);
769        without_depth.store_hit(addr, 1, 0, U256::ONE);
770        assert_eq!(without_depth.edge_count(), 1);
771        assert_eq!(dense_counts(&without_depth), [2]);
772
773        let mut with_depth =
774            EdgeCovInspector::with_config(EdgeCovConfig::new(EdgeCovKind::CollisionFree, true));
775        with_depth.store_hit(addr, 0, 0, U256::ONE);
776        with_depth.store_hit(addr, 1, 0, U256::ONE);
777        assert_eq!(with_depth.edge_count(), 2);
778        assert_eq!(dense_counts(&with_depth), [1, 1]);
779    }
780
781    #[test]
782    fn edges_keep_their_addresses_across_many_contracts() {
783        // More contracts than a packed edge can index, visited in turn twice, as a multicall does.
784        let addresses =
785            (0..5000u32).map(|i| Address::left_padding_from(&i.to_be_bytes())).collect::<Vec<_>>();
786        let config = EdgeCovConfig::new(EdgeCovKind::CollisionFree, false);
787        let mut inspector = EdgeCovInspector::with_config(config);
788        for _ in 0..2 {
789            for &address in &addresses {
790                inspector.store_hit(address, 1, 7, U256::from(42));
791            }
792        }
793
794        let expected = addresses
795            .iter()
796            .map(|&address| EdgeCovHit {
797                edge: EdgeKey::new(address, 1, 7, U256::from(42), false),
798                count: 2,
799            })
800            .collect::<Vec<_>>();
801        assert_eq!(inspector.dense_hits(), expected);
802        assert_eq!(inspector.addresses.len(), addresses.len());
803    }
804
805    #[test]
806    fn edges_report_their_keys_whether_packed_or_not() {
807        let first = Address::repeat_byte(0x11);
808        let second = Address::repeat_byte(0x22);
809        // The last three do not fit a packed edge: their jump destination, pc and depth are out
810        // of its range.
811        let edges = [
812            (first, 1, 7, U256::from(42)),
813            (second, 2, 7, U256::from(42)),
814            (first, 3, (1 << 20) - 1, U256::from((1 << 20) - 1)),
815            (second, 1, 7, U256::MAX),
816            (first, 1, 1 << 20, U256::ONE),
817            (second, 1 << 12, 7, U256::ONE),
818        ];
819        for include_depth in [false, true] {
820            let config = EdgeCovConfig::new(EdgeCovKind::CollisionFree, include_depth);
821            let mut inspector = EdgeCovInspector::with_config(config);
822            let mut expected = Vec::new();
823            for (address, depth, pc, jump_dest) in edges {
824                inspector.store_hit(address, depth, pc, jump_dest);
825                inspector.store_hit(address, depth, pc, jump_dest);
826                let edge = EdgeKey::new(address, depth, pc, jump_dest, include_depth);
827                expected.push(EdgeCovHit { edge, count: 2 });
828            }
829            expected.sort_by_key(|hit| hit.edge);
830            // The depth only takes part in the key when it is part of the edge identity.
831            assert_eq!(inspector.wide_hitcount.len(), if include_depth { 3 } else { 2 });
832            assert_eq!(inspector.dense_hits(), expected);
833        }
834    }
835
836    #[test]
837    fn reset_clears_hitcount_and_cmp_log() {
838        let mut inspector = EdgeCovInspector::with_cmp_log();
839
840        inspector.store_hit(Address::ZERO, 0, 0, U256::ONE);
841        inspector.store_cmp(CmpOperands {
842            op1: U256::from(123),
843            op2: U256::from(456),
844            pc: 42,
845            address: Address::ZERO,
846            opcode: opcode::EQ,
847        });
848
849        inspector.reset();
850
851        assert!(inspector.dense_hits().is_empty());
852        assert!(inspector.get_cmp_log().is_empty());
853    }
854
855    #[test]
856    fn cmp_log_is_capped_per_site() {
857        let mut inspector = EdgeCovInspector::with_cmp_log();
858
859        for i in 0..usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) + 1 {
860            inspector.store_cmp(CmpOperands {
861                op1: U256::from(i),
862                op2: U256::from(i + 1),
863                pc: 42,
864                address: Address::ZERO,
865                opcode: opcode::EQ,
866            });
867        }
868
869        assert_eq!(inspector.get_cmp_log().len(), usize::from(MAX_CMP_OBSERVATIONS_PER_SITE));
870    }
871
872    #[test]
873    fn cmp_log_caps_sites_without_starving_later_observations() {
874        let mut inspector = EdgeCovInspector::with_cmp_log();
875
876        for i in 0..usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) * 2 {
877            inspector.store_cmp(CmpOperands {
878                op1: U256::from(i),
879                op2: U256::from(i + 1),
880                pc: 1,
881                address: Address::ZERO,
882                opcode: opcode::EQ,
883            });
884        }
885        inspector.store_cmp(CmpOperands {
886            op1: U256::from(123),
887            op2: U256::from(456),
888            pc: 2,
889            address: Address::ZERO,
890            opcode: opcode::EQ,
891        });
892
893        assert_eq!(inspector.get_cmp_log().len(), usize::from(MAX_CMP_OBSERVATIONS_PER_SITE) + 1);
894        assert_eq!(inspector.get_cmp_log().last().unwrap().pc, 2);
895    }
896
897    fn edge_coverage_suite<FEN: FoundryEvmNetwork>()
898    where
899        TransactionRequestFor<FEN>: Default,
900    {
901        for (input, jump_dest) in [(1u64, 10u64), (2, 9)] {
902            let inspector =
903                EdgeCovInspector::with_config(EdgeCovConfig::new(EdgeCovKind::CollisionFree, true));
904            let mut inspector_with_cmp = inspector.clone();
905            inspector_with_cmp.enable_cmp_log(true);
906            let (status, inspector) = inspect::<FEN, _>(BRANCH, U256::from(input), inspector);
907            assert!(status);
908            // The top-level frame has depth 1.
909            let edge = EdgeKey {
910                address: TARGET,
911                depth: Some(1),
912                pc: 8,
913                jump_dest: U256::from(jump_dest),
914            };
915            assert_eq!(inspector.dense_hits(), [EdgeCovHit { edge, count: 1 }]);
916
917            let (_, inspector) = inspect::<FEN, _>(BRANCH, U256::from(input), inspector_with_cmp);
918            assert_eq!(
919                inspector.get_cmp_log(),
920                [CmpOperands {
921                    op1: U256::ONE,
922                    op2: U256::from(input),
923                    pc: 5,
924                    address: TARGET,
925                    opcode: opcode::EQ,
926                }]
927            );
928        }
929    }
930
931    #[test]
932    fn edge_coverage() {
933        edge_coverage_suite::<foundry_evm_core::evm::EthEvmNetwork>();
934        edge_coverage_suite::<foundry_evm_core::evm::TempoEvmNetwork>();
935        #[cfg(feature = "optimism")]
936        edge_coverage_suite::<foundry_evm_core::evm::OpEvmNetwork>();
937        #[cfg(feature = "base")]
938        edge_coverage_suite::<foundry_evm_core::evm::BaseEvmNetwork>();
939        #[cfg(feature = "monad")]
940        edge_coverage_suite::<foundry_evm_core::evm::MonadEvmNetwork>();
941    }
942
943    #[test]
944    fn sub_is_logged_only_when_next_jumpi_branches_on_its_nonzero_result() {
945        let mut inspector = EdgeCovInspector::with_cmp_log();
946        let address = Address::repeat_byte(0xaa);
947        let sub = CmpOperands {
948            op1: U256::from(7),
949            op2: U256::from(42),
950            pc: 3,
951            address,
952            opcode: opcode::SUB,
953        };
954        let result = sub.op1.wrapping_sub(sub.op2);
955
956        inspector.last_sub = Some(sub);
957        inspector.store_sub_branch(result, Address::ZERO);
958        inspector.last_sub = Some(CmpOperands { op2: sub.op1, ..sub });
959        inspector.store_sub_branch(U256::ZERO, address);
960        assert!(inspector.get_cmp_log().is_empty());
961
962        inspector.last_sub = Some(sub);
963        inspector.store_sub_branch(result, address);
964        inspector.store_sub_branch(result, address);
965        assert_eq!(inspector.get_cmp_log(), [sub]);
966    }
967}