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

foundry_evm_coverage/
anchors.rs
