foundry_evm_coverage/
anchors.rs

1use super::{
2    CoverageItemKind, ExecutionAnchor, ExecutionAnchorKind, ItemAnchor, ItemAnchors, SourceLocation,
3};
4use crate::analysis::{EmptySpecialFunctionKind, SourceAnalysis};
5use alloy_primitives::map::rustc_hash::FxHashSet;
6use eyre::ensure;
7use foundry_compilers::artifacts::sourcemap::{SourceElement, SourceMap};
8use foundry_evm_core::{bytecode::InstIter, ic::IcPcMap};
9use revm::bytecode::opcode;
10
11/// Attempts to find anchors for the given items using the given source map and bytecode.
12pub fn find_anchors(
13    bytecode: &[u8],
14    source_map: &SourceMap,
15    ic_pc_map: &IcPcMap,
16    analysis: &SourceAnalysis,
17) -> ItemAnchors {
18    let mut anchors = ItemAnchors::default();
19    let select_branch = |(fallthrough, taken): (ItemAnchor, ItemAnchor), path_id| match path_id {
20        0 => (fallthrough, None),
21        1 => (taken, Some(fallthrough.instruction - 1)),
22        _ => panic!("too many path IDs for branch"),
23    };
24    let mut seen_sources = FxHashSet::default();
25    source_map
26        .iter()
27        .filter_map(|element| element.index())
28        .filter(|&source| seen_sources.insert(source))
29        .flat_map(|source| analysis.items_for_source_enumerated(source))
30        .filter_map(|(item_id, item)| {
31            if analysis.empty_special_function_kind(item_id).is_some() {
32                return None;
33            }
34            let anchor_loc = item.anchor_loc.as_ref().unwrap_or(&item.loc);
35            match item.kind {
36                CoverageItemKind::Branch { path_id: 1, is_first_opcode: true, .. }
37                    if item.anchor_loc.is_some() =>
38                {
39                    find_anchor_simple(source_map, ic_pc_map, item_id, anchor_loc)
40                        .map(|anchor| (anchor, None))
41                        .or_else(|_| {
42                            find_anchor_branch(bytecode, source_map, item_id, &item.loc)
43                                .map(|anchors| select_branch(anchors, 1))
44                        })
45                }
46                CoverageItemKind::Branch { branch_id, path_id, is_first_opcode: false } => {
47                    let exact = analysis.is_ternary_branch(item.loc.source_id as u32, branch_id);
48                    find_anchor_branch_inner(bytecode, source_map, item_id, anchor_loc, exact)
49                        .map(|anchors| select_branch(anchors, path_id))
50                }
51                _ => find_anchor_simple(source_map, ic_pc_map, item_id, anchor_loc)
52                    .map(|anchor| (anchor, None)),
53            }
54            .inspect_err(|err| warn!(%item, %err, "could not find anchor"))
55            .ok()
56        })
57        .for_each(|(anchor, jump)| {
58            if let Some(jump) = jump {
59                anchors.jumps.insert(anchors.anchors.len(), jump);
60            }
61            anchors.anchors.push(anchor);
62        });
63    anchors
64}
65
66/// Finds execution-based anchors for empty constructors, receive functions, and fallbacks in a
67/// contract.
68pub fn find_execution_anchors(
69    source_id: u32,
70    contract_name: &str,
71    analysis: &SourceAnalysis,
72) -> Vec<ExecutionAnchor> {
73    analysis
74        .empty_special_function_ids(source_id, contract_name)
75        .filter_map(|item_id| {
76            analysis.empty_special_function_kind(item_id).map(|kind| ExecutionAnchor {
77                item_id,
78                kind: match kind {
79                    EmptySpecialFunctionKind::Constructor => ExecutionAnchorKind::Constructor,
80                    EmptySpecialFunctionKind::Receive => ExecutionAnchorKind::Receive,
81                    EmptySpecialFunctionKind::Fallback => ExecutionAnchorKind::Fallback,
82                },
83            })
84        })
85        .collect()
86}
87
88/// Find an anchor representing the first opcode within the given source range.
89pub fn find_anchor_simple(
90    source_map: &SourceMap,
91    ic_pc_map: &IcPcMap,
92    item_id: u32,
93    loc: &SourceLocation,
94) -> eyre::Result<ItemAnchor> {
95    let instruction =
96        source_map.iter().position(|element| is_in_source_range(element, loc)).ok_or_else(
97            || eyre::eyre!("Could not find anchor: No matching instruction in range {loc}"),
98        )?;
99
100    Ok(ItemAnchor {
101        instruction: ic_pc_map.get(instruction as u32).ok_or_else(|| {
102            eyre::eyre!("We found an anchor, but we can't translate it to a program counter")
103        })?,
104        item_id,
105    })
106}
107
108/// Finds the anchor corresponding to a branch item.
109///
110/// This finds the relevant anchors for a branch coverage item. These anchors
111/// are found using the bytecode of the contract in the range of the branching node.
112///
113/// For `IfStatement` nodes, the template is generally:
114/// ```text
115/// <condition>
116/// PUSH <ic if false>
117/// JUMPI
118/// <true branch>
119/// <...>
120/// <false branch>
121/// ```
122///
123/// For `assert` and `require`, the template is generally:
124///
125/// ```text
126/// PUSH <ic if true>
127/// JUMPI
128/// <revert>
129/// <...>
130/// <true branch>
131/// ```
132///
133/// This function will look for the last JUMPI instruction, backtrack to find the program
134/// counter of the first branch, and return an item for that program counter, and the
135/// program counter immediately after the JUMPI instruction.
136pub fn find_anchor_branch(
137    bytecode: &[u8],
138    source_map: &SourceMap,
139    item_id: u32,
140    loc: &SourceLocation,
141) -> eyre::Result<(ItemAnchor, ItemAnchor)> {
142    find_anchor_branch_inner(bytecode, source_map, item_id, loc, false)
143}
144
145/// Matches exact ternary spans to exclude nested decisions.
146fn find_anchor_branch_inner(
147    bytecode: &[u8],
148    source_map: &SourceMap,
149    item_id: u32,
150    loc: &SourceLocation,
151    exact: bool,
152) -> eyre::Result<(ItemAnchor, ItemAnchor)> {
153    let mut anchors: Option<(ItemAnchor, ItemAnchor)> = None;
154    for (ic, (pc, inst)) in InstIter::new(bytecode).with_pc().enumerate() {
155        // We found a push, so we do some PC -> IC translation accounting, but we also check if
156        // this push is coupled with the JUMPI we are interested in.
157
158        // Check if Opcode is PUSH
159        if (opcode::PUSH1..=opcode::PUSH32).contains(&inst.opcode.get()) {
160            let Some(element) = source_map.get(ic) else {
161                // NOTE(onbjerg): For some reason the last few bytes of the bytecode do not have
162                // a source map associated, so at that point we just stop searching
163                break;
164            };
165
166            // Check if we are in the source range we are interested in, and if the next opcode
167            // is a JUMPI
168            let next_pc = pc + inst.immediate.len() + 1;
169            let push_size = inst.immediate.len();
170            if bytecode.get(next_pc).copied() == Some(opcode::JUMPI)
171                && if exact {
172                    source_map.get(ic + 1).is_some_and(|jump| {
173                        jump.index() == Some(loc.source_id as u32)
174                            && jump.offset() == loc.bytes.start
175                            && jump.length() == loc.len()
176                    })
177                } else {
178                    is_in_source_range(element, loc)
179                }
180            {
181                // We do not support program counters bigger than u32.
182                ensure!(push_size <= 4, "jump destination overflow");
183
184                // Convert the push bytes for the second branch's PC to a u32.
185                let mut pc_bytes = [0u8; 4];
186                pc_bytes[4 - push_size..].copy_from_slice(inst.immediate);
187                let pc_jump = u32::from_be_bytes(pc_bytes);
188                let found = (
189                    ItemAnchor {
190                        item_id,
191                        // The first branch is the opcode directly after JUMPI
192                        instruction: (next_pc + 1).try_into()?,
193                    },
194                    ItemAnchor { item_id, instruction: pc_jump },
195                );
196                if exact {
197                    // Generated branch code can contain later jumps mapped to the ternary span.
198                    return Ok(found);
199                }
200                anchors = Some(found);
201            }
202        }
203    }
204
205    anchors.ok_or_else(|| eyre::eyre!("Could not detect branches in source: {}", loc))
206}
207
208/// Calculates whether `element` is within the range of the target `location`.
209fn is_in_source_range(element: &SourceElement, location: &SourceLocation) -> bool {
210    // Source IDs must match.
211    let source_ids_match = element.index_i32() == location.source_id as i32;
212    if !source_ids_match {
213        return false;
214    }
215
216    // Needed because some source ranges in the source map mark the entire contract...
217    let is_within_start = element.offset() >= location.bytes.start;
218    if !is_within_start {
219        return false;
220    }
221
222    let start_of_ranges = location.bytes.start.max(element.offset());
223    let end_of_ranges =
224        (location.bytes.start + location.len()).min(element.offset() + element.length());
225    start_of_ranges <= end_of_ranges
226}
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231    use foundry_compilers::artifacts::sourcemap;
232
233    #[test]
234    fn ternary_anchor_rejects_missing_node_mapping() {
235        let loc =
236            SourceLocation { source_id: 0, contract_name: "T".into(), bytes: 10..30, lines: 1..2 };
237        let bytecode = [opcode::PUSH1, 6, opcode::JUMPI, opcode::PUSH1, 7, opcode::JUMPI];
238        // A contained inner span must never substitute for the missing outer decision.
239        let inner_only = sourcemap::parse("15:5:0;;;").unwrap();
240        assert!(find_anchor_branch_inner(&bytecode, &inner_only, 0, &loc, true).is_err());
241    }
242}
foundry_evm_coverage/anchors.rs

foundry_evm_coverage/
anchors.rs
