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::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    let mut pc = 0;
97    let mut cumulative_push_size = 0;
98    while pc < bytecode.len() {
99        let op = bytecode[pc];
100
101        // We found a push, so we do some PC -> IC translation accounting, but we also check if
102        // this push is coupled with the JUMPI we are interested in.
103
104        // Check if Opcode is PUSH
105        if (opcode::PUSH1..=opcode::PUSH32).contains(&op) {
106            let element = if let Some(element) = source_map.get(pc - cumulative_push_size) {
107                element
108            } else {
109                // NOTE(onbjerg): For some reason the last few bytes of the bytecode do not have
110                // a source map associated, so at that point we just stop searching
111                break;
112            };
113
114            // Do push byte accounting
115            let push_size = (op - opcode::PUSH1 + 1) as usize;
116            pc += push_size;
117            cumulative_push_size += push_size;
118
119            // Check if we are in the source range we are interested in, and if the next opcode
120            // is a JUMPI
121            if is_in_source_range(element, loc) && bytecode[pc + 1] == opcode::JUMPI {
122                // We do not support program counters bigger than usize. This is also an
123                // assumption in REVM, so this is just a sanity check.
124                ensure!(push_size <= 8, "jump destination overflow");
125
126                // Convert the push bytes for the second branch's PC to a usize
127                let push_bytes_start = pc - push_size + 1;
128                let push_bytes = &bytecode[push_bytes_start..push_bytes_start + push_size];
129                let mut pc_bytes = [0u8; 8];
130                pc_bytes[8 - push_size..].copy_from_slice(push_bytes);
131                let pc_jump = u64::from_be_bytes(pc_bytes);
132                let pc_jump = u32::try_from(pc_jump).expect("PC is too big");
133                anchors = Some((
134                    ItemAnchor {
135                        item_id,
136                        // The first branch is the opcode directly after JUMPI
137                        instruction: (pc + 2) as u32,
138                    },
139                    ItemAnchor { item_id, instruction: pc_jump },
140                ));
141            }
142        }
143        pc += 1;
144    }
145
146    anchors.ok_or_else(|| eyre::eyre!("Could not detect branches in source: {}", loc))
147}
148
149/// Calculates whether `element` is within the range of the target `location`.
150fn is_in_source_range(element: &SourceElement, location: &SourceLocation) -> bool {
151    // Source IDs must match.
152    let source_ids_match = element.index_i32() == location.source_id as i32;
153    if !source_ids_match {
154        return false;
155    }
156
157    // Needed because some source ranges in the source map mark the entire contract...
158    let is_within_start = element.offset() >= location.bytes.start;
159    if !is_within_start {
160        return false;
161    }
162
163    let start_of_ranges = location.bytes.start.max(element.offset());
164    let end_of_ranges =
165        (location.bytes.start + location.len()).min(element.offset() + element.length());
166    let within_ranges = start_of_ranges <= end_of_ranges;
167    if !within_ranges {
168        return false;
169    }
170
171    true
172}
foundry_evm_coverage/anchors.rs

foundry_evm_coverage/
anchors.rs
