foundry_evm_coverage/
anchors.rs

1use super::{CoverageItemKind, ItemAnchor, SourceLocation};
2use crate::analysis::SourceAnalysis;
3use alloy_primitives::map::rustc_hash::FxHashSet;
4use eyre::ensure;
5use foundry_compilers::artifacts::sourcemap::{SourceElement, SourceMap};
6use foundry_evm_core::{bytecode::InstIter, ic::IcPcMap};
7use revm::bytecode::opcode;
8
9/// Attempts to find anchors for the given items using the given source map and bytecode.
10pub fn find_anchors(
11    bytecode: &[u8],
12    source_map: &SourceMap,
13    ic_pc_map: &IcPcMap,
14    analysis: &SourceAnalysis,
15) -> Vec<ItemAnchor> {
16    let mut seen_sources = FxHashSet::default();
17    source_map
18        .iter()
19        .filter_map(|element| element.index())
20        .filter(|&source| seen_sources.insert(source))
21        .flat_map(|source| analysis.items_for_source_enumerated(source))
22        .filter_map(|(item_id, item)| {
23            match item.kind {
24                CoverageItemKind::Branch { path_id, is_first_opcode: false, .. } => {
25                    find_anchor_branch(bytecode, source_map, item_id, &item.loc).map(|anchors| {
26                        match path_id {
27                            0 => anchors.0,
28                            1 => anchors.1,
29                            _ => panic!("too many path IDs for branch"),
30                        }
31                    })
32                }
33                _ => find_anchor_simple(source_map, ic_pc_map, item_id, &item.loc),
34            }
35            .inspect_err(|err| warn!(%item, %err, "could not find anchor"))
36            .ok()
37        })
38        .collect()
39}
40
41/// Find an anchor representing the first opcode within the given source range.
42pub fn find_anchor_simple(
43    source_map: &SourceMap,
44    ic_pc_map: &IcPcMap,
45    item_id: u32,
46    loc: &SourceLocation,
47) -> eyre::Result<ItemAnchor> {
48    let instruction =
49        source_map.iter().position(|element| is_in_source_range(element, loc)).ok_or_else(
50            || eyre::eyre!("Could not find anchor: No matching instruction in range {loc}"),
51        )?;
52
53    Ok(ItemAnchor {
54        instruction: ic_pc_map.get(instruction as u32).ok_or_else(|| {
55            eyre::eyre!("We found an anchor, but we can't translate it to a program counter")
56        })?,
57        item_id,
58    })
59}
60
61/// Finds the anchor corresponding to a branch item.
62///
63/// This finds the relevant anchors for a branch coverage item. These anchors
64/// are found using the bytecode of the contract in the range of the branching node.
65///
66/// For `IfStatement` nodes, the template is generally:
67/// ```text
68/// <condition>
69/// PUSH <ic if false>
70/// JUMPI
71/// <true branch>
72/// <...>
73/// <false branch>
74/// ```
75///
76/// For `assert` and `require`, the template is generally:
77///
78/// ```text
79/// PUSH <ic if true>
80/// JUMPI
81/// <revert>
82/// <...>
83/// <true branch>
84/// ```
85///
86/// This function will look for the last JUMPI instruction, backtrack to find the program
87/// counter of the first branch, and return an item for that program counter, and the
88/// program counter immediately after the JUMPI instruction.
89pub fn find_anchor_branch(
90    bytecode: &[u8],
91    source_map: &SourceMap,
92    item_id: u32,
93    loc: &SourceLocation,
94) -> eyre::Result<(ItemAnchor, ItemAnchor)> {
95    let mut anchors: Option<(ItemAnchor, ItemAnchor)> = None;
96    for (ic, (pc, inst)) in InstIter::new(bytecode).with_pc().enumerate() {
97        // We found a push, so we do some PC -> IC translation accounting, but we also check if
98        // this push is coupled with the JUMPI we are interested in.
99
100        // Check if Opcode is PUSH
101        if (opcode::PUSH1..=opcode::PUSH32).contains(&inst.opcode.get()) {
102            let Some(element) = source_map.get(ic) else {
103                // NOTE(onbjerg): For some reason the last few bytes of the bytecode do not have
104                // a source map associated, so at that point we just stop searching
105                break;
106            };
107
108            // Check if we are in the source range we are interested in, and if the next opcode
109            // is a JUMPI
110            let next_pc = pc + inst.immediate.len() + 1;
111            let push_size = inst.immediate.len();
112            if bytecode.get(next_pc).copied() == Some(opcode::JUMPI)
113                && is_in_source_range(element, loc)
114            {
115                // We do not support program counters bigger than u32.
116                ensure!(push_size <= 4, "jump destination overflow");
117
118                // Convert the push bytes for the second branch's PC to a u32.
119                let mut pc_bytes = [0u8; 4];
120                pc_bytes[4 - push_size..].copy_from_slice(inst.immediate);
121                let pc_jump = u32::from_be_bytes(pc_bytes);
122                anchors = Some((
123                    ItemAnchor {
124                        item_id,
125                        // The first branch is the opcode directly after JUMPI
126                        instruction: (next_pc + 1) as u32,
127                    },
128                    ItemAnchor { item_id, instruction: pc_jump },
129                ));
130            }
131        }
132    }
133
134    anchors.ok_or_else(|| eyre::eyre!("Could not detect branches in source: {}", loc))
135}
136
137/// Calculates whether `element` is within the range of the target `location`.
138fn is_in_source_range(element: &SourceElement, location: &SourceLocation) -> bool {
139    // Source IDs must match.
140    let source_ids_match = element.index_i32() == location.source_id as i32;
141    if !source_ids_match {
142        return false;
143    }
144
145    // Needed because some source ranges in the source map mark the entire contract...
146    let is_within_start = element.offset() >= location.bytes.start;
147    if !is_within_start {
148        return false;
149    }
150
151    let start_of_ranges = location.bytes.start.max(element.offset());
152    let end_of_ranges =
153        (location.bytes.start + location.len()).min(element.offset() + element.length());
154    let within_ranges = start_of_ranges <= end_of_ranges;
155    if !within_ranges {
156        return false;
157    }
158
159    true
160}
foundry_evm_coverage/anchors.rs

foundry_evm_coverage/
anchors.rs
