Skip to main content

foundry_evm_coverage/
anchors.rs

1use super::{
2    CoverageItemKind, ExecutionAnchor, ExecutionAnchorKind, ItemAnchor, ItemAnchors, SourceLocation,
3};
4use crate::analysis::{BranchKind, EmptySpecialFunctionKind, IfArms, SourceAnalysis, TernaryArms};
5use alloy_primitives::{U256, map::rustc_hash::FxHashSet};
6use evm2::interpreter::op as opcode;
7use eyre::ensure;
8use foundry_compilers::artifacts::sourcemap::{Jump, SourceElement, SourceMap};
9use foundry_evm_core::{bytecode::InstIter, ic::IcPcMap};
10use std::ops::Range;
11
12impl ItemAnchor {
13    fn from_instruction(
14        instruction: Option<usize>,
15        ic_pc_map: &IcPcMap,
16        item_id: u32,
17        loc: &SourceLocation,
18    ) -> eyre::Result<Self> {
19        let instruction = instruction.ok_or_else(|| {
20            eyre::eyre!("Could not find anchor: No matching instruction in range {loc}")
21        })?;
22        Ok(Self {
23            instruction: ic_pc_map.get(instruction as u32).ok_or_else(|| {
24                eyre::eyre!("We found an anchor, but we can't translate it to a program counter")
25            })?,
26            item_id,
27        })
28    }
29
30    fn from_branch(item_id: u32, next_pc: usize, immediate: &[u8]) -> eyre::Result<(Self, Self)> {
31        let pc_jump = jump_destination(immediate)?;
32        Ok((
33            Self { item_id, instruction: (next_pc + 1).try_into()? },
34            Self { item_id, instruction: pc_jump },
35        ))
36    }
37}
38
39/// An anchor with the conditional jump whose taken edge it counts and the jumps that enter the
40/// fallthrough from elsewhere, as in [`ItemAnchors::jumps`] and [`ItemAnchors::entries`].
41type EdgeAnchor = (ItemAnchor, Option<u32>, Vec<(u32, bool)>);
42
43/// Decodes a push immediate as a program counter.
44fn jump_destination(immediate: &[u8]) -> eyre::Result<u32> {
45    // We do not support program counters bigger than u32.
46    ensure!(immediate.len() <= 4, "jump destination overflow");
47    let mut pc_bytes = [0u8; 4];
48    pc_bytes[4 - immediate.len()..].copy_from_slice(immediate);
49    Ok(u32::from_be_bytes(pc_bytes))
50}
51
52/// Attempts to find anchors for the given items using the given source map and bytecode.
53pub fn find_anchors(
54    bytecode: &[u8],
55    source_map: &SourceMap,
56    ic_pc_map: &IcPcMap,
57    analysis: &SourceAnalysis,
58) -> ItemAnchors {
59    let mut anchors = ItemAnchors::default();
60    let index = AnchorIndex::new(bytecode, source_map, ic_pc_map);
61    // Path 0 is the fallthrough and path 1 the jump target, unless `swapped`. The jump target
62    // counts the jump's executions minus its fallthrough's.
63    let select_branch = |(fallthrough, taken): (ItemAnchor, ItemAnchor), path_id, swapped| {
64        let jump = Some(fallthrough.instruction - 1);
65        match (path_id, swapped) {
66            (0, false) | (1, true) => (fallthrough, None, Vec::new()),
67            (1, false) | (0, true) => (taken, jump, Vec::new()),
68            _ => panic!("too many path IDs for branch"),
69        }
70    };
71    let mut seen_sources = FxHashSet::default();
72    source_map
73        .iter()
74        .filter_map(|element| element.index())
75        .filter(|&source| seen_sources.insert(source))
76        .flat_map(|source| analysis.items_for_source_enumerated(source))
77        .filter_map(|(item_id, item)| {
78            if analysis.empty_special_function_kind(item_id).is_some() {
79                return None;
80            }
81            let anchor_loc = item.anchor_loc.as_ref().unwrap_or(&item.loc);
82            let recover = || {
83                let hints = analysis.anchor_hints(item_id)?;
84                if let Some(guard) = &hints.revert_guard
85                    && let Some((anchor, jump)) = index.revert_guard(item_id, guard)
86                {
87                    return Some((anchor, jump, vec![]));
88                }
89                hints.alias_function.as_ref().and_then(|function| {
90                    index.alias_return(item_id, function).map(|anchor| (anchor, None, vec![]))
91                })
92            };
93            if let CoverageItemKind::Branch { branch_id, path_id, .. } = item.kind
94                && let Some(BranchKind::If(arms)) =
95                    analysis.branch_kind(item.loc.source_id as u32, branch_id)
96            {
97                let arm = if path_id == 0 { Some(&arms.then_arm) } else { arms.else_arm.as_ref() };
98                // The first instruction of an arm with code anchors it. Without code, only the
99                // jump's edge can count it, and when that is ambiguous the arm stays unanchored
100                // instead of taking an instruction that runs with the jump, such as its target.
101                if !arm.is_some_and(|arm| index.has_own_code(arm)) {
102                    return index.if_edge(item_id, path_id, &item.loc, arms).or_else(recover);
103                }
104            }
105            match item.kind {
106                CoverageItemKind::Branch { path_id: 1, is_first_opcode: true, .. }
107                    if item.anchor_loc.is_some() =>
108                {
109                    index.simple(item_id, anchor_loc).map(|anchor| (anchor, None, vec![])).or_else(
110                        |_| {
111                            index
112                                .branch(item_id, &item.loc, false, None)
113                                .map(|anchors| select_branch(anchors, 1, false))
114                        },
115                    )
116                }
117                CoverageItemKind::Branch { branch_id, path_id, is_first_opcode: false } => {
118                    let kind = analysis.branch_kind(item.loc.source_id as u32, branch_id);
119                    let exact = matches!(kind, Some(BranchKind::Ternary(_)));
120                    // A Yul `if` owns the jump outside its body, not those of nested branches.
121                    let body = match kind {
122                        Some(BranchKind::YulIf(body)) => Some(body),
123                        _ => None,
124                    };
125                    index.branch(item_id, anchor_loc, exact, body).map(|anchors| {
126                        let entries = if body.is_some() {
127                            index.fallthrough_entries(&anchors).unwrap_or_default()
128                        } else {
129                            vec![]
130                        };
131                        // The failing side of a `require`, the false arm of a ternary and the body
132                        // of a Yul `if` are path 0, wherever the compiler placed them.
133                        let swapped = match kind {
134                            Some(BranchKind::Require) => index.taken_fails(&anchors, anchor_loc),
135                            Some(BranchKind::Ternary(arms)) => {
136                                index.true_arm_falls_through(&anchors, arms)
137                            }
138                            Some(BranchKind::YulIf(body)) => index
139                                .taken_starts_in(&anchors, body)
140                                .unwrap_or_else(|| index.jump_is_body(&anchors, body)),
141                            None | Some(BranchKind::If(_)) => false,
142                        };
143                        let (anchor, jump, _) = select_branch(anchors, path_id, swapped);
144                        (anchor, jump, entries)
145                    })
146                }
147                CoverageItemKind::Function { .. } => {
148                    index.function(item_id, anchor_loc).map(|anchor| (anchor, None, vec![]))
149                }
150                _ => index.simple(item_id, anchor_loc).map(|anchor| (anchor, None, vec![])),
151            }
152            .or_else(|error| recover().ok_or(error))
153            .inspect_err(|err| warn!(%item, %err, "could not find anchor"))
154            .ok()
155        })
156        .for_each(|(anchor, jump, entries)| {
157            if let Some(jump) = jump {
158                anchors.jumps.insert(anchors.anchors.len(), jump);
159            }
160            if !entries.is_empty() {
161                anchors.entries.insert(anchors.anchors.len(), entries);
162            }
163            anchors.anchors.push(anchor);
164        });
165    anchors
166}
167
168/// Finds execution-based anchors for empty constructors, receive functions, and fallbacks in a
169/// contract.
170pub fn find_execution_anchors(
171    source_id: u32,
172    contract_name: &str,
173    analysis: &SourceAnalysis,
174) -> Vec<ExecutionAnchor> {
175    analysis
176        .empty_special_function_ids(source_id, contract_name)
177        .filter_map(|item_id| {
178            analysis.empty_special_function_kind(item_id).map(|kind| ExecutionAnchor {
179                item_id,
180                kind: match kind {
181                    EmptySpecialFunctionKind::Constructor => ExecutionAnchorKind::Constructor,
182                    EmptySpecialFunctionKind::Receive => ExecutionAnchorKind::Receive,
183                    EmptySpecialFunctionKind::Fallback => ExecutionAnchorKind::Fallback,
184                },
185            })
186        })
187        .collect()
188}
189
190/// The most static jumps `AnchorIndex::trace` follows.
191const MAX_TRACE_HOPS: usize = 8;
192
193/// Source map and branch lookups precomputed once per bytecode.
194struct AnchorIndex<'a> {
195    bytecode: &'a [u8],
196    source_map: &'a SourceMap,
197    /// The program counter of every instruction, by instruction counter.
198    pcs: Vec<u32>,
199    ic_pc_map: &'a IcPcMap,
200    /// `(source id, offset, instruction)`, sorted for source range lookups.
201    entries: Vec<(i32, u32, usize)>,
202    /// `(ic, next pc, push immediate)` for every push that feeds a `JUMPI`.
203    branches: Vec<(usize, usize, &'a [u8])>,
204    /// Straight-line instruction ranges ending in REVERT or INVALID, ordered by start.
205    reverting_runs: Vec<Range<usize>>,
206    /// `(JUMPDEST, start of its straight-line run)` for every `JUMPDEST` that the previous
207    /// instruction falls through to, ordered. A run starts after a `JUMP`, `STOP`, `RETURN`,
208    /// `REVERT`, `INVALID`, `SELFDESTRUCT`, or a `JUMPI` that can skip to something other than a
209    /// failure stub or a block that jumps to one. A `JUMP` that no source element maps does not
210    /// end a run.
211    fallen_into: Vec<(usize, usize)>,
212    /// `(target pc, push instruction)` for every push that feeds a `JUMP` or `JUMPI`, sorted.
213    jumps: Vec<(u32, usize)>,
214    /// `(target pc, push instruction)` for every push of a `JUMPDEST` address, sorted. Unlike
215    /// `jumps`, this includes return addresses that code pushes before jumping to a helper.
216    address_pushes: Vec<(u32, usize)>,
217    /// Whether execution can fall through from the previous instruction into each instruction.
218    falls_through: Vec<bool>,
219}
220
221impl<'a> AnchorIndex<'a> {
222    fn new(bytecode: &'a [u8], source_map: &'a SourceMap, ic_pc_map: &'a IcPcMap) -> Self {
223        let mut entries = source_map
224            .iter()
225            .enumerate()
226            .map(|(instruction, element)| (element.index_i32(), element.offset(), instruction))
227            .collect::<Vec<_>>();
228        entries.sort_unstable();
229        let mut pcs = Vec::new();
230        let mut branches = Vec::new();
231        let mut reverting_runs = Vec::new();
232        let mut jumps = Vec::new();
233        // `(value, push instruction, feeds a jump)` for every push of at most four bytes.
234        let mut pushes = Vec::new();
235        let mut falls_through = Vec::new();
236        let mut opcodes = Vec::new();
237        // `(pc, instruction)` of every `JUMPDEST`.
238        let mut jumpdests = Vec::new();
239        // Instructions that end a straight-line run, and `(JUMPI, static target pc)` pairs.
240        let mut run_ends = Vec::new();
241        let mut conditional_jumps = Vec::new();
242        // `(run, static target pc)` of every run ending in a `JUMP`.
243        let mut jump_runs = Vec::new();
244        let mut run_start = 0;
245        let mut prev = opcode::STOP;
246        let mut prev_target = None;
247        for (ic, (pc, inst)) in InstIter::new(bytecode).with_pc().enumerate() {
248            opcodes.push(inst.opcode.get());
249            falls_through.push(!matches!(
250                prev,
251                opcode::JUMP
252                    | opcode::STOP
253                    | opcode::RETURN
254                    | opcode::REVERT
255                    | opcode::INVALID
256                    | opcode::SELFDESTRUCT
257            ));
258            pcs.push(pc as u32);
259            match inst.opcode.get() {
260                opcode::JUMPDEST => jumpdests.push((pc, ic)),
261                opcode::JUMPI => conditional_jumps.push((ic, prev_target)),
262                opcode::JUMP => {
263                    jump_runs.push((run_start..ic + 1, prev_target));
264                    // A compiler-generated helper, such as an ABI decoder, returns to the code
265                    // that called it, so its `JUMP` does not end the caller's run.
266                    if source_map.get(ic).is_none_or(|e| e.index().is_some()) {
267                        run_ends.push(ic);
268                    }
269                }
270                opcode::STOP
271                | opcode::RETURN
272                | opcode::REVERT
273                | opcode::INVALID
274                | opcode::SELFDESTRUCT => run_ends.push(ic),
275                _ => {}
276            }
277            prev_target = (opcode::PUSH1..=opcode::PUSH4)
278                .contains(&inst.opcode.get())
279                .then(|| inst.immediate.iter().fold(0, |acc, &byte| acc << 8 | byte as usize));
280            match inst.opcode.get() {
281                opcode::REVERT | opcode::INVALID => {
282                    reverting_runs.push(run_start..ic + 1);
283                    run_start = ic + 1;
284                }
285                // A JUMPDEST begins a basic block, so a failure stub led by one is part of its run.
286                // Adjacent JUMPDESTs share the run started by the first.
287                opcode::JUMPDEST if prev != opcode::JUMPDEST => run_start = ic,
288                opcode::JUMP
289                | opcode::JUMPI
290                | opcode::STOP
291                | opcode::RETURN
292                | opcode::SELFDESTRUCT => run_start = ic + 1,
293                _ => {}
294            }
295            prev = inst.opcode.get();
296            if (opcode::PUSH1..=opcode::PUSH32).contains(&inst.opcode.get()) {
297                // Stop where the source map ends.
298                if source_map.get(ic).is_none() {
299                    break;
300                }
301                let next_pc = pc + inst.immediate.len() + 1;
302                let jump = bytecode.get(next_pc).copied();
303                if jump == Some(opcode::JUMPI) {
304                    branches.push((ic, next_pc, inst.immediate));
305                }
306                if inst.immediate.len() <= 4 {
307                    let target = inst.immediate.iter().fold(0, |acc, &byte| acc << 8 | byte as u32);
308                    let feeds_jump = matches!(jump, Some(opcode::JUMP | opcode::JUMPI));
309                    pushes.push((target, ic, feeds_jump));
310                    if feeds_jump {
311                        jumps.push((target, ic));
312                    }
313                }
314            }
315        }
316        jumps.sort_unstable();
317        let jumpdest_at = |pc: Option<usize>| {
318            pc.and_then(|pc| jumpdests.binary_search_by_key(&pc, |&(pc, _)| pc).ok())
319                .map(|i| jumpdests[i].1)
320        };
321        // A push of a `JUMPDEST` address is a jump or a return address when it feeds a jump, or
322        // when the code after it reaches a `JUMP` or `JUMPI` before it halts, as a call does. Other
323        // pushes are constants.
324        let mut reaches_jump = vec![false; opcodes.len()];
325        let mut next = false;
326        for (ic, &op) in opcodes.iter().enumerate().rev() {
327            next = match op {
328                opcode::JUMP | opcode::JUMPI => true,
329                opcode::STOP
330                | opcode::RETURN
331                | opcode::REVERT
332                | opcode::INVALID
333                | opcode::SELFDESTRUCT => false,
334                _ => next,
335            };
336            reaches_jump[ic] = next;
337        }
338        let mut address_pushes = pushes
339            .into_iter()
340            .filter(|&(target, ic, feeds_jump)| {
341                jumpdest_at(Some(target as usize)).is_some() && (feeds_jump || reaches_jump[ic])
342            })
343            .map(|(target, ic, _)| (target, ic))
344            .collect::<Vec<_>>();
345        address_pushes.sort_unstable();
346        // A run that jumps to a failure stub, such as a panic helper call, is a failure stub too.
347        let failing_jump_runs = jump_runs
348            .into_iter()
349            .filter(|&(_, target)| {
350                jumpdest_at(target).is_some_and(|ic| in_reverting_run(&reverting_runs, ic))
351            })
352            .map(|(run, _)| run)
353            .collect::<Vec<_>>();
354        // A `JUMPI` ends a run unless it can only skip to a failure stub.
355        run_ends.extend(conditional_jumps.into_iter().filter_map(|(ic, target)| {
356            let fails = jumpdest_at(target).is_some_and(|ic| {
357                in_reverting_run(&reverting_runs, ic) || in_reverting_run(&failing_jump_runs, ic)
358            });
359            (!fails).then_some(ic)
360        }));
361        run_ends.sort_unstable();
362        let fallen_into = jumpdests
363            .iter()
364            .filter_map(|&(_, ic)| {
365                let run_start = run_ends.partition_point(|&end| end < ic).checked_sub(1);
366                let run_start = run_start.map_or(0, |i| run_ends[i] + 1);
367                (run_start < ic).then_some((ic, run_start))
368            })
369            .collect();
370        Self {
371            bytecode,
372            source_map,
373            pcs,
374            ic_pc_map,
375            entries,
376            branches,
377            reverting_runs,
378            fallen_into,
379            jumps,
380            address_pushes,
381            falls_through,
382        }
383    }
384
385    /// Returns the instructions whose source elements start in the byte range of `loc`.
386    fn instructions_starting_in(
387        &self,
388        loc: &SourceLocation,
389    ) -> impl Iterator<Item = usize> + Clone {
390        let source = loc.source_id as i32;
391        let start = self
392            .entries
393            .partition_point(|&(id, offset, _)| (id, offset) < (source, loc.bytes.start));
394        let end = self.entries.partition_point(|&(id, offset, _)| {
395            (id, offset) <= (source, loc.bytes.start + loc.len())
396        });
397        self.entries[start..end].iter().map(|&(_, _, instruction)| instruction)
398    }
399
400    /// Finds the entry opcode of the source range, preferring code outside a failure stub.
401    ///
402    /// The entry is the lowest instruction in the range that is not provably reached only from
403    /// inside the range. A compiler can lay out blocks that belong to the range before its entry,
404    /// such as the cleanup of a failed condition, and only code inside the range reaches those.
405    /// Dynamic jumps are not tracked, so an instruction with no known way in, such as the entry of
406    /// an internal function, counts as an entry.
407    fn simple(&self, item_id: u32, loc: &SourceLocation) -> eyre::Result<ItemAnchor> {
408        let candidates = self
409            .instructions_starting_in(loc)
410            .filter(|&instruction| is_in_source_range(&self.source_map[instruction], loc));
411        // Cold validation stubs can precede the statement's main code in the bytecode.
412        // A revert statement itself may have only failure-path candidates, so retain the fallback.
413        let mut live = candidates
414            .clone()
415            .filter(|&instruction| !in_reverting_run(&self.reverting_runs, instruction))
416            .collect::<Vec<_>>();
417        live.sort_unstable();
418        let instruction = live
419            .iter()
420            .copied()
421            .find(|&instruction| !self.is_entered_only_from_inside(instruction, loc))
422            .or_else(|| live.first().copied())
423            .or_else(|| candidates.min());
424        ItemAnchor::from_instruction(instruction, self.ic_pc_map, item_id, loc)
425    }
426
427    /// Returns whether the taken side of a `require` branch is its failing side.
428    ///
429    /// A side that starts inside the `require` span is the failing side, because the failure
430    /// code carries the span while the passing side continues with the next statement. If
431    /// neither side starts inside it, the side that reverts without another conditional branch
432    /// is. If both do, the source map cannot tell them apart, and the revert check cannot follow
433    /// the failure code's dynamic returns, so the positional default stays.
434    fn taken_fails(&self, anchors: &(ItemAnchor, ItemAnchor), loc: &SourceLocation) -> bool {
435        self.taken_starts_in(anchors, loc).unwrap_or_else(|| {
436            let (fallthrough, taken) = anchors;
437            self.fails(taken.instruction) && !self.fails(fallthrough.instruction)
438        })
439    }
440
441    /// Returns whether the taken side starts inside `loc` and the fallthrough does not, or `None`
442    /// when neither does. A fallthrough that starts inside `loc` wins, so the positional default
443    /// stays when both do.
444    fn taken_starts_in(
445        &self,
446        (fallthrough, taken): &(ItemAnchor, ItemAnchor),
447        loc: &SourceLocation,
448    ) -> Option<bool> {
449        match (self.starts_in(fallthrough.instruction, loc), self.starts_in(taken.instruction, loc))
450        {
451            (true, _) => Some(false),
452            (false, true) => Some(true),
453            (false, false) => None,
454        }
455    }
456
457    /// Returns whether the jump's own target push is mapped to `loc`, as when a body that is
458    /// only a `break`, `continue`, or `leave` becomes the conditional jump itself.
459    fn jump_is_body(
460        &self,
461        (fallthrough, _): &(ItemAnchor, ItemAnchor),
462        loc: &SourceLocation,
463    ) -> bool {
464        let jump = self.pcs.binary_search(&(fallthrough.instruction - 1)).ok();
465        jump.is_some_and(|jump| self.starts_in_range(jump - 1, loc))
466    }
467
468    /// Returns whether the first instruction at `pc` after any `JUMPDEST`s is mapped inside `loc`.
469    fn starts_in(&self, pc: u32, loc: &SourceLocation) -> bool {
470        let Ok(mut ic) = self.pcs.binary_search(&pc) else { return false };
471        while self.pcs.get(ic).is_some_and(|&p| self.bytecode[p as usize] == opcode::JUMPDEST) {
472            ic += 1;
473        }
474        self.maps_inside(ic, loc)
475    }
476
477    /// Returns whether the instruction `ic` is mapped inside `loc`.
478    fn maps_inside(&self, ic: usize, loc: &SourceLocation) -> bool {
479        self.source_map.get(ic).is_some_and(|element| is_within_source_span(element, loc))
480    }
481
482    /// Returns whether the code at `pc` reverts without another conditional branch or other halt.
483    ///
484    /// Follows static `PUSH target; JUMP` hops, which compilers use to share revert blocks.
485    fn fails(&self, pc: u32) -> bool {
486        let last = self.trace(pc).last().map(|&ic| self.bytecode[self.pcs[ic] as usize]);
487        matches!(last, Some(opcode::REVERT | opcode::INVALID))
488    }
489
490    /// Returns whether the true arm of a ternary is the fallthrough of its jump.
491    ///
492    /// A successor with code mapped inside one arm's span is that arm, because the arms carry their
493    /// own spans while the join point carries the enclosing expression's. An arm without code, such
494    /// as a literal already on the stack, has no successor of its own, so the other arm decides.
495    /// If neither arm has code, or the successors give conflicting answers, the positional default
496    /// stays: the true arm is the jump target.
497    fn true_arm_falls_through(
498        &self,
499        (fallthrough, taken): &(ItemAnchor, ItemAnchor),
500        arms: &TernaryArms,
501    ) -> bool {
502        let holds = |pc, arm| self.block_maps_inside(pc, arm);
503        let true_fallthrough = holds(fallthrough.instruction, &arms.true_arm);
504        let true_taken = holds(taken.instruction, &arms.true_arm);
505        let false_fallthrough = holds(fallthrough.instruction, &arms.false_arm);
506        let false_taken = holds(taken.instruction, &arms.false_arm);
507        let falls_through =
508            (true_fallthrough && !true_taken) || (false_taken && !false_fallthrough);
509        let is_taken = (true_taken && !true_fallthrough) || (false_fallthrough && !false_taken);
510        falls_through && !is_taken
511    }
512
513    /// Returns whether an instruction of the block at `pc` is mapped inside `loc`. The block runs
514    /// to the first jump or halt, so it covers the entry code of an arm, which can start with
515    /// instructions mapped to the enclosing expression. An arm that falls into the join point
516    /// also scans the code after it, which is mapped outside both arms.
517    fn block_maps_inside(&self, pc: u32, loc: &SourceLocation) -> bool {
518        let Ok(start) = self.pcs.binary_search(&pc) else { return false };
519        for (ic, &next) in self.pcs.iter().enumerate().skip(start) {
520            if self.source_map.get(ic).is_some_and(|element| is_within_source_span(element, loc)) {
521                return true;
522            }
523            if matches!(
524                self.bytecode[next as usize],
525                opcode::JUMP
526                    | opcode::JUMPI
527                    | opcode::STOP
528                    | opcode::RETURN
529                    | opcode::REVERT
530                    | opcode::INVALID
531                    | opcode::SELFDESTRUCT
532            ) {
533                break;
534            }
535        }
536        false
537    }
538
539    /// Finds the entry of a function.
540    ///
541    /// Compilers map the entry `JUMPDEST` to exactly the function's span, so it is preferred over
542    /// the lowest instruction in the span, which can belong to a body block laid out before the
543    /// entry. The entry is the exact-span instruction that code outside the function jumps to,
544    /// which excludes the function's exit label and inlined code. A public function can have two
545    /// such instructions, its ABI wrapper and its body. The wrapper falls through into the body,
546    /// which internal calls jump to, so the body runs on both paths and is preferred. Falls back
547    /// to [`Self::simple`] when there is none, as for inlined constructors and fallbacks, and for
548    /// functions that only their own modifier wrapper jumps to, such as with solc via-IR and the
549    /// optimizer.
550    fn function(&self, item_id: u32, loc: &SourceLocation) -> eyre::Result<ItemAnchor> {
551        let source = loc.source_id as i32;
552        let start = self
553            .entries
554            .partition_point(|&(id, offset, _)| (id, offset) < (source, loc.bytes.start));
555        let candidates = self.entries[start..]
556            .iter()
557            .take_while(|&&(id, offset, _)| (id, offset) == (source, loc.bytes.start))
558            .map(|&(_, _, instruction)| instruction)
559            .filter(|&instruction| {
560                self.source_map[instruction].length() == loc.len()
561                    && self.is_jumped_to_from_outside(instruction, loc)
562            })
563            .collect::<Vec<_>>();
564        // The lowest candidate can fall through into a later one.
565        let entry = candidates.iter().copied().min().map(|lowest| {
566            candidates
567                .iter()
568                .copied()
569                .filter(|&instruction| self.falls_through_into(lowest, instruction))
570                .min()
571                .unwrap_or(lowest)
572        });
573        match entry {
574            Some(_) => ItemAnchor::from_instruction(entry, self.ic_pc_map, item_id, loc),
575            None => self.simple(item_id, loc),
576        }
577    }
578
579    /// Returns whether execution can fall through from `from` into the `JUMPDEST` `to`.
580    fn falls_through_into(&self, from: usize, to: usize) -> bool {
581        self.fallen_into
582            .binary_search_by_key(&to, |&(jumpdest, _)| jumpdest)
583            .is_ok_and(|i| (self.fallen_into[i].1..to).contains(&from))
584    }
585
586    /// Returns whether every known way into `instruction` comes from an instruction mapped inside
587    /// `loc`, and there is at least one. The known ways in are falling through and a push of its
588    /// address, which is a static jump or a return address. A push takes the source element
589    /// given by [`Self::push_element`]. Unmapped instructions, such as the `JUMPDEST` that a
590    /// compiler puts before a loop body, belong to the block they lead, so the ways into that block
591    /// count.
592    fn is_entered_only_from_inside(&self, instruction: usize, loc: &SourceLocation) -> bool {
593        let inside = |element: &SourceElement| is_in_source_range(element, loc);
594        let (mut any, mut all) = (false, true);
595        let mut ic = instruction;
596        loop {
597            if let Some(pc) = self.ic_pc_map.get(ic as u32) {
598                let start = self.address_pushes.partition_point(|&(target, _)| target < pc);
599                for element in self.address_pushes[start..]
600                    .iter()
601                    .take_while(|&&(target, _)| target == pc)
602                    .filter_map(|&(_, push)| self.push_element(push))
603                {
604                    any = true;
605                    all &= inside(element);
606                }
607            }
608            let Some(prev) = ic.checked_sub(1) else {
609                // Execution starts at the first instruction.
610                return false;
611            };
612            if !self.falls_through.get(ic).copied().unwrap_or(false) {
613                break;
614            }
615            match self.source_map.get(prev) {
616                Some(element) if element.index().is_none() => ic = prev,
617                element => {
618                    any = true;
619                    all &= element.is_some_and(inside);
620                    break;
621                }
622            }
623        }
624        any && all
625    }
626
627    /// Returns whether a static jump mapped outside `loc` targets `instruction`.
628    fn is_jumped_to_from_outside(&self, instruction: usize, loc: &SourceLocation) -> bool {
629        let Some(pc) = self.ic_pc_map.get(instruction as u32) else { return false };
630        let start = self.jumps.partition_point(|&(target, _)| target < pc);
631        self.jumps[start..]
632            .iter()
633            .take_while(|&&(target, _)| target == pc)
634            .filter_map(|&(_, push)| self.push_element(push))
635            .any(|element| !is_within_source_span(element, loc))
636    }
637
638    /// Returns the source element that places the push `push`. An unmapped push, such as the
639    /// jump out of an `if` arm, belongs to the code it sits in, so it takes the element of the
640    /// nearest mapped instruction that falls through into it. A push with no such instruction has
641    /// no place and gives no evidence.
642    fn push_element(&self, push: usize) -> Option<&SourceElement> {
643        let mut ic = push;
644        loop {
645            let element = self.source_map.get(ic)?;
646            if element.index().is_some() {
647                return Some(element);
648            }
649            if !self.falls_through.get(ic).copied().unwrap_or(false) {
650                return None;
651            }
652            ic -= 1;
653        }
654    }
655
656    /// Returns the jumps that enter the fallthrough of a branch from elsewhere, as `(pc,
657    /// conditional)`, such as the back edge of a loop whose head the branch falls into, or a
658    /// `continue` that jumps to the code after the `if`. Their executions are not the
659    /// fallthrough's, but its hits count them. Fails when the entries cannot be told apart: the
660    /// branch's own jump targets the fallthrough, or a conditional jump's own fallthrough is a
661    /// `JUMPDEST` that others can enter. The branch then keeps its anchors without a discount.
662    fn fallthrough_entries(
663        &self,
664        (fallthrough, _): &(ItemAnchor, ItemAnchor),
665    ) -> eyre::Result<Vec<(u32, bool)>> {
666        let pc = fallthrough.instruction;
667        if self.bytecode.get(pc as usize) != Some(&opcode::JUMPDEST) {
668            return Ok(Vec::new());
669        }
670        let start = self.jumps.partition_point(|&(target, _)| target < pc);
671        self.jumps[start..]
672            .iter()
673            .take_while(|&&(target, _)| target == pc)
674            .map(|&(_, push)| {
675                let jump = self.pcs.get(push + 1).copied().unwrap_or_default();
676                let conditional = self.bytecode[jump as usize] == opcode::JUMPI;
677                ensure!(
678                    jump != pc - 1
679                        && (!conditional
680                            || self.bytecode.get(jump as usize + 1) != Some(&opcode::JUMPDEST)),
681                    "fallthrough entries cannot be told apart"
682                );
683                Ok((jump, conditional))
684            })
685            .collect()
686    }
687
688    /// Finds the fallthrough and taken anchors of a branch.
689    ///
690    /// `exact` matches only the jump mapped to exactly `loc`, so ternaries skip nested decisions.
691    /// Otherwise the last matching jump wins, preferring one mapped outside `nested`, the code
692    /// of the branch's body, which holds the jumps of nested branches and loops.
693    fn branch(
694        &self,
695        item_id: u32,
696        loc: &SourceLocation,
697        exact: bool,
698        nested: Option<&SourceLocation>,
699    ) -> eyre::Result<(ItemAnchor, ItemAnchor)> {
700        let mut own = None;
701        let mut anchors = None;
702        for &(ic, next_pc, immediate) in &self.branches {
703            let matches = if exact {
704                self.source_map.get(ic + 1).is_some_and(|jump| {
705                    jump.index() == Some(loc.source_id as u32)
706                        && jump.offset() == loc.bytes.start
707                        && jump.length() == loc.len()
708                })
709            } else {
710                is_in_source_range(&self.source_map[ic], loc)
711            };
712            if matches {
713                let found = ItemAnchor::from_branch(item_id, next_pc, immediate)?;
714                // Generated branch code can contain later jumps mapped to the ternary span.
715                if exact {
716                    return Ok(found);
717                }
718                if nested.is_none_or(|nested| !self.maps_inside(ic + 1, nested)) {
719                    own = Some(found);
720                } else {
721                    anchors = Some(found);
722                }
723            }
724        }
725        own.or(anchors).ok_or_else(|| eyre::eyre!("Could not detect branches in source: {}", loc))
726    }
727
728    /// Finds the anchor that counts the entries into an arm of an `if` that has no code of its
729    /// own, from the edge of the conditional jump that enters it, as `gcov` counts arcs.
730    ///
731    /// The `if`'s jump is the only one mapped inside the statement but outside its arms, which
732    /// hold the jumps of nested branches. Fails when the side that enters the arm is ambiguous
733    /// (see [`Self::then_is_taken`]), or when the fallthrough can be entered other than by falling
734    /// through, so that its hits do not split the jump's.
735    fn if_edge(
736        &self,
737        item_id: u32,
738        path_id: u32,
739        loc: &SourceLocation,
740        arms: &IfArms,
741    ) -> Option<EdgeAnchor> {
742        // The statement's span ends before the `;` that a jump's source element can include.
743        let mut jumps = self
744            .branches
745            .iter()
746            .filter(|&&(ic, ..)| {
747                self.source_map.get(ic + 1).is_some_and(|jump| {
748                    is_in_source_range(jump, loc)
749                        && !is_in_source_range(jump, &arms.then_arm)
750                        && arms.else_arm.as_ref().is_none_or(|arm| !is_in_source_range(jump, arm))
751                })
752            })
753            .collect::<Vec<_>>();
754        // A jump to a failure, such as an overflow check in the condition, cannot enter an arm,
755        // unless it is the only jump, as when the arm is a shared `revert`.
756        if jumps.len() > 1 {
757            jumps.retain(|&&(_, _, immediate)| {
758                jump_destination(immediate).is_ok_and(|target| !self.fails(target))
759            });
760        }
761        let &[&(_, jump, immediate)] = jumps.as_slice() else { return None };
762        let anchors = ItemAnchor::from_branch(item_id, jump, immediate).ok()?;
763        let (fallthrough, taken) = &anchors;
764        let pc = fallthrough.instruction;
765        let pushes = |pushes: &[(u32, usize)]| {
766            pushes.partition_point(|&(target, _)| target <= pc)
767                - pushes.partition_point(|&(target, _)| target < pc)
768        };
769        // A push of its address that no jump consumes, such as a return address, can enter it.
770        let op = self.bytecode.get(pc as usize)?;
771        if *op == opcode::JUMPDEST && pushes(&self.address_pushes) != pushes(&self.jumps) {
772            return None;
773        }
774        let entries = self.fallthrough_entries(&anchors).ok()?;
775        let arm_is_taken = self.then_is_taken(&anchors, arms)? ^ (path_id == 1);
776        Some(if arm_is_taken {
777            (taken.clone(), Some(jump as u32), entries)
778        } else {
779            (fallthrough.clone(), None, entries)
780        })
781    }
782
783    /// Returns whether the taken side of an `if`'s jump enters its then arm, or `None` when the
784    /// sides cannot be told apart.
785    ///
786    /// The code that each side runs alone, before it joins the other's, decides when an arm has
787    /// code there, including the code of the functions that the arm calls by name, which a
788    /// compiler can inline. An arm that is the jump itself is the taken side. An arm without code
789    /// is entered by the side that does not reach the next statement of the block, such as the loop
790    /// exit of a `break` or the increment of a `continue`, but only when the sides never meet and
791    /// the other side does not reach that statement either: a side that carries a value into the
792    /// join point, as with `if (c) { x = 2; }`, meets the other side's code.
793    fn then_is_taken(&self, anchors: &(ItemAnchor, ItemAnchor), arms: &IfArms) -> Option<bool> {
794        let (fallthrough, taken) =
795            (self.trace(anchors.0.instruction), self.trace(anchors.1.instruction));
796        let shared = |ic: &usize| fallthrough.contains(ic) && taken.contains(ic);
797        let alone = |trace: &[usize]| trace.iter().copied().take_while(|ic| !shared(ic)).count();
798        let (fallthrough_alone, taken_alone) =
799            (&fallthrough[..alone(&fallthrough)], &taken[..alone(&taken)]);
800        let taken_enters = |arm: &SourceLocation, callees: &[SourceLocation]| {
801            let holds = |trace: &[usize]| {
802                trace.iter().any(|&ic| {
803                    self.starts_in_range(ic, arm)
804                        || callees.iter().any(|callee| self.starts_in_range(ic, callee))
805                })
806            };
807            match (holds(fallthrough_alone), holds(taken_alone)) {
808                (false, true) => Some(true),
809                (true, false) => Some(false),
810                _ => None,
811            }
812        };
813        let then_taken = taken_enters(&arms.then_arm, &arms.then_callees);
814        let else_taken = arms
815            .else_arm
816            .as_ref()
817            .and_then(|arm| taken_enters(arm, &arms.else_callees))
818            .map(|taken| !taken);
819        match (then_taken, else_taken) {
820            (Some(then), Some(other)) if then != other => return None,
821            (Some(taken), _) | (None, Some(taken)) => return Some(taken),
822            (None, None) => {}
823        }
824        // An arm that is only a `break` or `continue` can become the jump itself.
825        let is_body = |arm| self.jump_is_body(anchors, arm);
826        match (is_body(&arms.then_arm), arms.else_arm.as_ref().is_some_and(is_body)) {
827            (true, false) => return Some(true),
828            (false, true) => return Some(false),
829            (true, true) => return None,
830            (false, false) => {}
831        }
832        let meet = fallthrough.len() > fallthrough_alone.len();
833        if arms.else_arm.is_some() || self.has_own_code(&arms.then_arm) || meet {
834            return None;
835        }
836        let after = arms.after.as_ref()?;
837        let starts_after = |trace: &[usize]| {
838            trace
839                .iter()
840                .find(|&&ic| self.bytecode[self.pcs[ic] as usize] != opcode::JUMPDEST)
841                .is_some_and(|&ic| self.starts_in_range(ic, after))
842        };
843        let reaches_after =
844            |trace: &[usize]| trace.iter().any(|&ic| self.starts_in_range(ic, after));
845        match (starts_after(&fallthrough), starts_after(&taken)) {
846            (true, false) if !reaches_after(&taken) => Some(true),
847            (false, true) if !reaches_after(&fallthrough) => Some(false),
848            _ => None,
849        }
850    }
851
852    /// Returns the instructions that run from `pc` up to the first conditional jump, dynamic jump,
853    /// or halt, following static `PUSH target; JUMP` hops.
854    fn trace(&self, pc: u32) -> Vec<usize> {
855        let mut trace = Vec::new();
856        let mut next = self.pcs.binary_search(&pc).ok();
857        // Bounds a cycle of static jumps.
858        for _ in 0..MAX_TRACE_HOPS {
859            let mut push = None;
860            while let Some(ic) = next {
861                let Some(&pc) = self.pcs.get(ic) else { return trace };
862                trace.push(ic);
863                next = Some(ic + 1);
864                match self.bytecode[pc as usize] {
865                    opcode::JUMP => {
866                        next = push.and_then(|target| self.pcs.binary_search(&target).ok());
867                        break;
868                    }
869                    opcode::JUMPI
870                    | opcode::STOP
871                    | opcode::RETURN
872                    | opcode::REVERT
873                    | opcode::INVALID
874                    | opcode::SELFDESTRUCT => return trace,
875                    op @ opcode::PUSH1..=opcode::PUSH4 => {
876                        let immediate = &self.bytecode[pc as usize + 1..];
877                        let len = (op - opcode::PUSH0) as usize;
878                        push = jump_destination(&immediate[..len]).ok();
879                    }
880                    _ => push = None,
881                }
882            }
883            if next.is_none() {
884                break;
885            }
886        }
887        trace
888    }
889
890    /// Returns whether the instruction `ic` is mapped to the byte range of `loc`, as
891    /// [`Self::simple`] matches, which tolerates a statement's span ending before its `;`.
892    fn starts_in_range(&self, ic: usize, loc: &SourceLocation) -> bool {
893        self.source_map.get(ic).is_some_and(|element| is_in_source_range(element, loc))
894    }
895
896    /// Returns whether an instruction mapped inside `loc` runs only when `loc` does. The pushes
897    /// that feed a conditional jump do not: they run with the jump, even when its target is the
898    /// body of a `break` or `continue`.
899    fn has_own_code(&self, loc: &SourceLocation) -> bool {
900        self.instructions_starting_in(loc).any(|ic| {
901            self.starts_in_range(ic, loc)
902                && self.branches.binary_search_by_key(&ic, |&(ic, ..)| ic).is_err()
903        })
904    }
905
906    /// An alias-only function has no instructions for some of its statements. Its unique normal
907    /// return proves those statements completed. Require an exact declaration location at the
908    /// entry, an explicit function-exit marker mapped to the declaration or the closing brace, and
909    /// a pure return stub; never infer hits for inlined or aborting code.
910    fn alias_return(&self, item_id: u32, function: &SourceLocation) -> Option<ItemAnchor> {
911        let exact = |element: &SourceElement| {
912            element.index() == Some(function.source_id as u32)
913                && element.offset() == function.bytes.start
914                && element.length() == function.len()
915        };
916        let closing_brace = |element: &SourceElement| {
917            element.index() == Some(function.source_id as u32)
918                && element.offset() == function.bytes.end.saturating_sub(1)
919                && element.length() == 1
920        };
921        let mut returns = Vec::new();
922        for (ic, (pc, instruction)) in InstIter::new(self.bytecode).with_pc().enumerate() {
923            if instruction.opcode.get() != opcode::JUMPDEST
924                || !self.source_map.get(ic).is_some_and(exact)
925            {
926                continue;
927            }
928            for (relative, (offset, instruction)) in
929                InstIter::new(&self.bytecode[pc..]).with_pc().enumerate().take(32)
930            {
931                match instruction.opcode.get() {
932                    opcode::JUMPDEST if relative == 0 => {}
933                    opcode::PUSH0
934                    | opcode::PUSH1..=opcode::PUSH32
935                    | opcode::DUP1..=opcode::DUP16
936                    | opcode::SWAP1..=opcode::SWAP16
937                    | opcode::POP => {}
938                    opcode::JUMP => {
939                        if self.source_map.get(ic + relative).is_some_and(|element| {
940                            (exact(element) || closing_brace(element))
941                                && element.jump() == Jump::Out
942                        }) {
943                            returns.push(pc + offset);
944                        }
945                        break;
946                    }
947                    _ => break,
948                }
949            }
950        }
951        let [pc] = returns.as_slice() else { return None };
952        Some(ItemAnchor { item_id, instruction: (*pc).try_into().ok()? })
953    }
954
955    /// A shared revert has no unique body location. Recover its controlling edge only when a
956    /// single decision matches the condition and exactly one successor emits the resolved error.
957    /// Payload matching determines polarity; source order and compiler identity do not.
958    fn revert_guard(
959        &self,
960        item_id: u32,
961        guard: &super::RevertGuard,
962    ) -> Option<(ItemAnchor, Option<u32>)> {
963        let loc = &guard.condition;
964        let mut decisions = self.branches.iter().filter(|&&(ic, _, _)| {
965            self.source_map.get(ic + 1).is_some_and(|jump| {
966                jump.index() == Some(loc.source_id as u32)
967                    && jump.offset() == loc.bytes.start
968                    && jump.length() == loc.len()
969            })
970        });
971        let &(_, jump_pc, immediate) = decisions.next()?;
972        if decisions.next().is_some() || self.bytecode.get(jump_pc + 1) == Some(&opcode::JUMPDEST) {
973            return None;
974        }
975        let (fallthrough, taken) = ItemAnchor::from_branch(item_id, jump_pc, immediate).ok()?;
976        let rejects = |pc| constant_revert_selector(self.bytecode, pc) == Some(guard.selector);
977        match (rejects(fallthrough.instruction as usize), rejects(taken.instruction as usize)) {
978            (true, false) if self.continues_after(taken.instruction as usize, guard) => {
979                Some((fallthrough, None))
980            }
981            (false, true) if self.continues_after(fallthrough.instruction as usize, guard) => {
982                Some((taken, Some(jump_pc.try_into().ok()?)))
983            }
984            _ => None,
985        }
986    }
987
988    /// The other successor must positively reach the source continuation in this same function.
989    /// An unsupported error stub is unknown, not evidence for the opposite branch's polarity.
990    fn continues_after(&self, start: usize, guard: &super::RevertGuard) -> bool {
991        for (ic, (_, instruction)) in InstIter::new(self.bytecode)
992            .with_pc()
993            .enumerate()
994            .skip_while(|(_, (pc, _))| *pc < start)
995            .take(32)
996        {
997            match instruction.opcode.get() {
998                opcode::JUMP
999                | opcode::JUMPI
1000                | opcode::REVERT
1001                | opcode::INVALID
1002                | opcode::STOP
1003                | opcode::RETURN
1004                | opcode::SELFDESTRUCT
1005                | opcode::CALL
1006                | opcode::STATICCALL
1007                | opcode::DELEGATECALL
1008                | opcode::CALLCODE => return false,
1009                _ => {}
1010            }
1011            if self.source_map.get(ic).is_some_and(|element| {
1012                element.index() == Some(guard.function.source_id as u32)
1013                    && element.offset() >= guard.statement.bytes.end
1014                    && element.offset() >= guard.function.bytes.start
1015                    && element
1016                        .offset()
1017                        .checked_add(element.length())
1018                        .is_some_and(|end| end <= guard.function.bytes.end)
1019            }) {
1020                return true;
1021            }
1022        }
1023        false
1024    }
1025}
1026
1027/// Recognizes a constant four-byte error payload in a small straight-line stub. Memory and the
1028/// incoming stack are unknown: only bytes explicitly stored by this stub can establish a selector.
1029/// Calls, branches, dynamic data, and unsupported operations deliberately leave it unrecognized.
1030fn constant_revert_selector(bytecode: &[u8], pc: usize) -> Option<[u8; 4]> {
1031    let mut stack = Vec::<U256>::new();
1032    let mut memory = [None; 64];
1033    for (_, inst) in InstIter::new(bytecode.get(pc..)?).with_pc().take(32) {
1034        match inst.opcode.get() {
1035            opcode::JUMPDEST => {}
1036            opcode::PUSH0 => stack.push(U256::ZERO),
1037            opcode::PUSH1..=opcode::PUSH32 => stack.push(U256::from_be_slice(inst.immediate)),
1038            opcode::DUP1..=opcode::DUP16 => {
1039                let depth = usize::from(inst.opcode.get() - opcode::DUP1) + 1;
1040                stack.push(*stack.get(stack.len().checked_sub(depth)?)?);
1041            }
1042            opcode::SWAP1..=opcode::SWAP16 => {
1043                let depth = usize::from(inst.opcode.get() - opcode::SWAP1) + 1;
1044                let top = stack.len().checked_sub(1)?;
1045                let other = top.checked_sub(depth)?;
1046                stack.swap(top, other);
1047            }
1048            opcode::SHL => {
1049                let shift = stack.pop()?;
1050                let value = stack.pop()?;
1051                stack.push(if shift < U256::from(256) {
1052                    value << shift.to::<usize>()
1053                } else {
1054                    U256::ZERO
1055                });
1056            }
1057            opcode::MSTORE => {
1058                let offset = usize::try_from(stack.pop()?).ok()?;
1059                let value = stack.pop()?.to_be_bytes::<32>();
1060                for (dest, byte) in
1061                    memory.get_mut(offset..offset.checked_add(32)?)?.iter_mut().zip(value)
1062                {
1063                    *dest = Some(byte);
1064                }
1065            }
1066            opcode::REVERT => {
1067                let offset = usize::try_from(stack.pop()?).ok()?;
1068                if stack.pop()? != U256::from(4) {
1069                    return None;
1070                }
1071                let bytes = memory.get(offset..offset.checked_add(4)?)?;
1072                return Some([bytes[0]?, bytes[1]?, bytes[2]?, bytes[3]?]);
1073            }
1074            _ => return None,
1075        }
1076    }
1077    None
1078}
1079
1080/// Returns whether `instruction` is in one of the ordered, disjoint `runs`.
1081fn in_reverting_run(runs: &[Range<usize>], instruction: usize) -> bool {
1082    let next = runs.partition_point(|run| run.end <= instruction);
1083    runs.get(next).is_some_and(|run| run.contains(&instruction))
1084}
1085
1086/// Calculates whether `element` is entirely inside the span of `location`.
1087fn is_within_source_span(element: &SourceElement, location: &SourceLocation) -> bool {
1088    element.index_i32() == location.source_id as i32
1089        && element.offset() >= location.bytes.start
1090        && element.offset() + element.length() <= location.bytes.start + location.len()
1091}
1092
1093/// Calculates whether `element` is within the range of the target `location`.
1094fn is_in_source_range(element: &SourceElement, location: &SourceLocation) -> bool {
1095    // Source IDs must match.
1096    let source_ids_match = element.index_i32() == location.source_id as i32;
1097    if !source_ids_match {
1098        return false;
1099    }
1100
1101    // Needed because some source ranges in the source map mark the entire contract...
1102    let is_within_start = element.offset() >= location.bytes.start;
1103    if !is_within_start {
1104        return false;
1105    }
1106
1107    let start_of_ranges = location.bytes.start.max(element.offset());
1108    let end_of_ranges =
1109        (location.bytes.start + location.len()).min(element.offset() + element.length());
1110    start_of_ranges <= end_of_ranges
1111}
1112
1113#[cfg(test)]
1114mod tests {
1115    use super::*;
1116    use crate::CoverageItem;
1117    use foundry_compilers::artifacts::sourcemap;
1118
1119    /// Returns the `(instruction, jump)` of each anchor of the branches of the given kinds at the
1120    /// given source offsets, each spanning 20 bytes. Branch `n` has items `2n` and `2n + 1` for
1121    /// its paths 0 and 1.
1122    fn branch_anchors(
1123        bytecode: &[u8],
1124        starts: &[(u32, BranchKind)],
1125        source_map: &str,
1126    ) -> Vec<(u32, Option<u32>)> {
1127        let anchors = find_branch_anchors(bytecode, starts, source_map);
1128        anchors
1129            .anchors
1130            .iter()
1131            .enumerate()
1132            .map(|(index, anchor)| {
1133                assert_eq!(anchor.item_id as usize, index);
1134                (anchor.instruction, anchors.jumps.get(&index).copied())
1135            })
1136            .collect()
1137    }
1138
1139    fn find_branch_anchors(
1140        bytecode: &[u8],
1141        starts: &[(u32, BranchKind)],
1142        source_map: &str,
1143    ) -> ItemAnchors {
1144        let items = starts
1145            .iter()
1146            .enumerate()
1147            .flat_map(|(branch_id, &(start, _))| {
1148                (0..2).map(move |path_id| CoverageItem {
1149                    kind: CoverageItemKind::Branch {
1150                        branch_id: branch_id as u32,
1151                        path_id,
1152                        is_first_opcode: false,
1153                    },
1154                    loc: location(start..start + 20),
1155                    anchor_loc: None,
1156                    hits: 0,
1157                })
1158            })
1159            .collect();
1160        let kinds = starts
1161            .iter()
1162            .enumerate()
1163            .map(|(id, (_, kind))| (id as u32, kind.clone()))
1164            .collect::<Vec<_>>();
1165        let analysis = SourceAnalysis::for_test(items, kinds);
1166        let source_map = sourcemap::parse(source_map).unwrap();
1167        let ic_pc_map = IcPcMap::new(bytecode);
1168        find_anchors(bytecode, &source_map, &ic_pc_map, &analysis)
1169    }
1170
1171    fn require_anchors(
1172        bytecode: &[u8],
1173        starts: &[u32],
1174        source_map: &str,
1175    ) -> Vec<(u32, Option<u32>)> {
1176        let starts = starts.iter().map(|&start| (start, BranchKind::Require)).collect::<Vec<_>>();
1177        branch_anchors(bytecode, &starts, source_map)
1178    }
1179
1180    #[test]
1181    fn require_paths_follow_the_failing_side() {
1182        // `cond; PUSH dest; JUMPI`, then the continuation or the revert.
1183        let solc = [
1184            opcode::PUSH1,
1185            0,
1186            opcode::PUSH1,
1187            8,
1188            opcode::JUMPI,
1189            opcode::PUSH0,
1190            opcode::PUSH0,
1191            opcode::REVERT,
1192            opcode::JUMPDEST,
1193            opcode::STOP,
1194        ];
1195        let solar = [
1196            opcode::PUSH1,
1197            0,
1198            opcode::PUSH1,
1199            6,
1200            opcode::JUMPI,
1201            opcode::STOP,
1202            opcode::JUMPDEST,
1203            opcode::PUSH0,
1204            opcode::PUSH0,
1205            opcode::REVERT,
1206        ];
1207        // Both sides revert, so the layout is ambiguous and the fallthrough is path 0.
1208        let both_revert = [
1209            opcode::PUSH1,
1210            0,
1211            opcode::PUSH1,
1212            8,
1213            opcode::JUMPI,
1214            opcode::PUSH0,
1215            opcode::PUSH0,
1216            opcode::REVERT,
1217            opcode::JUMPDEST,
1218            opcode::PUSH0,
1219            opcode::PUSH0,
1220            opcode::REVERT,
1221        ];
1222        // The taken side branches again before it can revert.
1223        let taken_branches = [
1224            opcode::PUSH1,
1225            0,
1226            opcode::PUSH1,
1227            6,
1228            opcode::JUMPI,
1229            opcode::STOP,
1230            opcode::JUMPDEST,
1231            opcode::PUSH1,
1232            0,
1233            opcode::PUSH1,
1234            14,
1235            opcode::JUMPI,
1236            opcode::STOP,
1237            opcode::STOP,
1238            opcode::JUMPDEST,
1239            opcode::PUSH0,
1240            opcode::PUSH0,
1241            opcode::REVERT,
1242        ];
1243        for (bytecode, expected) in [
1244            (&solc[..], [(5, None), (8, Some(4))]),
1245            (&solar[..], [(6, Some(4)), (5, None)]),
1246            (&both_revert[..], [(5, None), (8, Some(4))]),
1247            (&taken_branches[..], [(5, None), (6, Some(4))]),
1248        ] {
1249            let count = InstIter::new(bytecode).count();
1250            // Only the condition and the jump belong to the require.
1251            let source_map = format!("10:20:0;;;50:5:0{}", ";".repeat(count - 4));
1252            assert_eq!(require_anchors(bytecode, &[10], &source_map), expected);
1253        }
1254    }
1255
1256    #[test]
1257    fn require_paths_prefer_the_source_map() {
1258        // The success path of solc's `require(c, "m"); revert Foo();` reaches a straight-line
1259        // revert, while the failure code encodes the message through a dynamic jump. The failing
1260        // side is the one that starts inside the require.
1261        let solc = [
1262            opcode::PUSH1,
1263            0,
1264            opcode::PUSH1,
1265            7,
1266            opcode::JUMPI,
1267            opcode::PUSH0,
1268            opcode::JUMP,
1269            opcode::JUMPDEST,
1270            opcode::PUSH0,
1271            opcode::PUSH0,
1272            opcode::REVERT,
1273        ];
1274        // Solar's cold block follows an unmapped `JUMPDEST` and is not provably reverting.
1275        let solar = [
1276            opcode::PUSH1,
1277            0,
1278            opcode::PUSH1,
1279            6,
1280            opcode::JUMPI,
1281            opcode::STOP,
1282            opcode::JUMPDEST,
1283            opcode::PUSH0,
1284            opcode::JUMP,
1285        ];
1286        for (bytecode, source_map, expected) in [
1287            (&solc[..], "10:20:0;;;;;;50:13:0;;;", [(5, None), (7, Some(4))]),
1288            // Both sides start inside the span, as for `require(c, E(1)); assembly { invalid() }`.
1289            (&solc[..], "10:20:0;;;;;;;;;", [(5, None), (7, Some(4))]),
1290            // An element that starts inside the span but extends past it is not inside.
1291            (&solc[..], "10:20:0;;;15:40:0;;;50:13:0;;;", [(7, Some(4)), (5, None)]),
1292            (&solar[..], "10:20:0;;;50:5:0;-1:-1:-1;10:20:0;", [(6, Some(4)), (5, None)]),
1293        ] {
1294            assert_eq!(require_anchors(bytecode, &[10], source_map), expected);
1295        }
1296    }
1297
1298    #[test]
1299    fn yul_if_paths_follow_the_body() {
1300        // `cond; PUSH dest; JUMPI`, then the body or the code after the `if`. The `if` spans bytes
1301        // 10..30 and its body 20..30.
1302        let body_falls_through = [
1303            opcode::PUSH1,
1304            0,
1305            opcode::PUSH1,
1306            7,
1307            opcode::JUMPI,
1308            opcode::PUSH0,
1309            opcode::POP,
1310            opcode::JUMPDEST,
1311            opcode::STOP,
1312        ];
1313        let body_is_taken = [
1314            opcode::PUSH1,
1315            0,
1316            opcode::PUSH1,
1317            6,
1318            opcode::JUMPI,
1319            opcode::STOP,
1320            opcode::JUMPDEST,
1321            opcode::PUSH0,
1322            opcode::POP,
1323        ];
1324        let kind = BranchKind::YulIf(SourceLocation {
1325            source_id: 0,
1326            contract_name: "T".into(),
1327            bytes: 20..30,
1328            lines: 1..2,
1329        });
1330        for (bytecode, source_map, expected) in [
1331            (&body_falls_through[..], "10:20:0;;;22:5:0;;50:5:0;", [(5, None), (7, Some(4))]),
1332            // Solar can place the body at the jump target, behind an unmapped `JUMPDEST`.
1333            (&body_is_taken[..], "10:20:0;;;50:5:0;-1:-1:-1;22:5:0;", [(6, Some(4)), (5, None)]),
1334            // Without a single side in the body, path 0 is the fallthrough.
1335            (&body_falls_through[..], "10:20:0;;;50:5:0;;50:5:0;", [(5, None), (7, Some(4))]),
1336            (&body_falls_through[..], "10:20:0;;;22:5:0;;22:5:0;", [(5, None), (7, Some(4))]),
1337            (&body_is_taken[..], "10:20:0;;;50:5:0;-1:-1:-1;50:5:0;", [(5, None), (6, Some(4))]),
1338        ] {
1339            assert_eq!(branch_anchors(bytecode, &[(10, kind.clone())], source_map), expected);
1340        }
1341    }
1342
1343    #[test]
1344    fn yul_if_jump_only_body_is_the_taken_side() {
1345        // A body that is only a `continue` becomes the conditional jump itself, so neither side
1346        // starts in the body. The `if` spans bytes 10..30 and its body 22..30.
1347        let kind = BranchKind::YulIf(SourceLocation {
1348            source_id: 0,
1349            contract_name: "T".into(),
1350            bytes: 22..30,
1351            lines: 1..2,
1352        });
1353        let bytecode = [
1354            opcode::PUSH1,
1355            0,
1356            opcode::PUSH1,
1357            7,
1358            opcode::JUMPI,
1359            opcode::PUSH0,
1360            opcode::POP,
1361            opcode::JUMPDEST,
1362            opcode::STOP,
1363        ];
1364        for (source_map, expected) in [
1365            // The jump's push is mapped to the `continue`, inside the body.
1366            ("12:5:0;25:2:0;12:5:0;50:5:0;;50:5:0;", [(7, Some(4)), (5, None)]),
1367            // The push is mapped to the condition, so the positional default stays.
1368            ("12:5:0;;;50:5:0;;50:5:0;", [(5, None), (7, Some(4))]),
1369        ] {
1370            assert_eq!(branch_anchors(&bytecode, &[(10, kind.clone())], source_map), expected);
1371        }
1372    }
1373
1374    #[test]
1375    fn yul_if_takes_its_own_jump() {
1376        // An outer `if` whose body holds another conditional jump. The `if` spans bytes 10..30 and
1377        // its body 22..30. The outer jump is at pc 4 and the nested one at pc 9.
1378        let bytecode = [
1379            opcode::PUSH1,
1380            0,
1381            opcode::PUSH1,
1382            12,
1383            opcode::JUMPI,
1384            opcode::PUSH1,
1385            0,
1386            opcode::PUSH1,
1387            11,
1388            opcode::JUMPI,
1389            opcode::PUSH0,
1390            opcode::JUMPDEST,
1391            opcode::JUMPDEST,
1392            opcode::STOP,
1393        ];
1394        let kind = BranchKind::YulIf(SourceLocation {
1395            source_id: 0,
1396            contract_name: "T".into(),
1397            bytes: 22..30,
1398            lines: 1..2,
1399        });
1400        for (source_map, expected) in [
1401            // The nested jump is mapped inside the body, so the condition's jump is the `if`'s.
1402            ("12:5:0;;;25:2:0;;;26:3:0;;50:5:0;", [(5, None), (12, Some(4))]),
1403            // Without a jump outside the body, the last jump is the `if`'s.
1404            ("22:5:0;;;25:2:0;;;26:3:0;;50:5:0;", [(10, None), (11, Some(9))]),
1405        ] {
1406            assert_eq!(branch_anchors(&bytecode, &[(10, kind.clone())], source_map), expected);
1407        }
1408    }
1409
1410    #[test]
1411    fn yul_if_counts_entries_into_a_shared_fallthrough() {
1412        // An `if` whose body starts at a loop head. The `if` spans bytes 10..30 and its body
1413        // 22..30. The jump at pc 10 either returns to the head, which the `if` falls into, or
1414        // leaves the loop.
1415        let kind = BranchKind::YulIf(SourceLocation {
1416            source_id: 0,
1417            contract_name: "T".into(),
1418            bytes: 22..30,
1419            lines: 1..2,
1420        });
1421        let bytecode = |back_edge, jump| {
1422            [
1423                opcode::PUSH1,
1424                0,
1425                opcode::PUSH1,
1426                11,
1427                opcode::JUMPI,
1428                opcode::JUMPDEST,
1429                opcode::PUSH1,
1430                0,
1431                opcode::PUSH1,
1432                back_edge,
1433                jump,
1434                opcode::JUMPDEST,
1435                opcode::STOP,
1436            ]
1437        };
1438        let source_map = "12:5:0;;;25:2:0;;;;;;50:5:0;";
1439        let find =
1440            |bytecode: [u8; 13]| find_branch_anchors(&bytecode, &[(10, kind.clone())], source_map);
1441        // The back edge's executions are not the `if`'s, and both paths discount them.
1442        let anchors = find(bytecode(5, opcode::JUMP));
1443        assert_eq!(
1444            anchors.anchors.iter().map(|anchor| anchor.instruction).collect::<Vec<_>>(),
1445            [5, 11]
1446        );
1447        assert_eq!(anchors.jumps.get(&1), Some(&4));
1448        assert_eq!(anchors.entries.get(&0), Some(&vec![(10, false)]));
1449        assert_eq!(anchors.entries.get(&1), Some(&vec![(10, false)]));
1450        // A conditional jump back to the head counts its taken executions, unless its own
1451        // fallthrough is a `JUMPDEST`, which others can enter.
1452        let anchors = find(bytecode(5, opcode::JUMPI));
1453        assert_eq!(anchors.anchors.len(), 2);
1454        assert!(anchors.entries.is_empty());
1455        let conditional = [
1456            opcode::PUSH1,
1457            0,
1458            opcode::PUSH1,
1459            12,
1460            opcode::JUMPI,
1461            opcode::JUMPDEST,
1462            opcode::PUSH1,
1463            0,
1464            opcode::PUSH1,
1465            5,
1466            opcode::JUMPI,
1467            opcode::STOP,
1468            opcode::JUMPDEST,
1469            opcode::STOP,
1470        ];
1471        let anchors = find_branch_anchors(&conditional, &[(10, kind.clone())], source_map);
1472        assert_eq!(anchors.entries.get(&0), Some(&vec![(10, true)]));
1473        // A jump elsewhere leaves the fallthrough unshared.
1474        let anchors = find(bytecode(11, opcode::JUMP));
1475        assert_eq!(anchors.anchors.len(), 2);
1476        assert!(anchors.entries.is_empty());
1477    }
1478
1479    #[test]
1480    fn yul_if_body_at_the_jump_target_with_a_shared_skip_label() {
1481        // Solar's layout of `if c { ...; if d { break } continue }`. The body is the jump target,
1482        // behind a `JUMPDEST` mapped to the whole `if` (bytes 10..30, its body 22..30). The skip
1483        // side is an unmapped `JUMPDEST` that the body's own conditional jump also targets.
1484        let bytecode = [
1485            opcode::PUSH1,
1486            0,
1487            opcode::PUSH1,
1488            9,
1489            opcode::JUMPI,
1490            opcode::JUMPDEST,
1491            opcode::PUSH1,
1492            0,
1493            opcode::STOP,
1494            opcode::JUMPDEST,
1495            opcode::DUP1,
1496            opcode::PUSH1,
1497            0,
1498            opcode::PUSH1,
1499            5,
1500            opcode::JUMPI,
1501            opcode::PUSH0,
1502            opcode::STOP,
1503        ];
1504        let kind = BranchKind::YulIf(SourceLocation {
1505            source_id: 0,
1506            contract_name: "T".into(),
1507            bytes: 22..30,
1508            lines: 1..2,
1509        });
1510        let source_map = "12:5:0;;;-1:-1:-1;50:5:0;;10:20:0;25:2:0;;;;;";
1511        let anchors = find_branch_anchors(&bytecode, &[(10, kind)], source_map);
1512        // Path 0 is the jump target, which counts the jump's executions minus the skip side's,
1513        // and the skip side's hits discount the entries of the body's own jump.
1514        assert_eq!(
1515            anchors.anchors.iter().map(|anchor| anchor.instruction).collect::<Vec<_>>(),
1516            [9, 5]
1517        );
1518        assert_eq!(anchors.jumps.get(&0), Some(&4));
1519        assert_eq!(anchors.entries.get(&0), Some(&vec![(15, true)]));
1520        assert_eq!(anchors.entries.get(&1), Some(&vec![(15, true)]));
1521    }
1522
1523    #[test]
1524    fn requires_share_a_revert_block() {
1525        // Both requires jump to the same revert block, the first through a `PUSH; JUMP` stub.
1526        let bytecode = [
1527            opcode::PUSH1,
1528            0,
1529            opcode::PUSH1,
1530            15,
1531            opcode::JUMPI,
1532            opcode::PUSH1,
1533            0,
1534            opcode::PUSH1,
1535            19,
1536            opcode::JUMPI,
1537            opcode::STOP,
1538            opcode::INVALID,
1539            opcode::INVALID,
1540            opcode::INVALID,
1541            opcode::INVALID,
1542            opcode::JUMPDEST,
1543            opcode::PUSH1,
1544            19,
1545            opcode::JUMP,
1546            opcode::JUMPDEST,
1547            opcode::PUSH0,
1548            opcode::PUSH0,
1549            opcode::REVERT,
1550        ];
1551        // Each require maps its condition and jump. Other code lies outside both spans.
1552        let source_map = format!(
1553            "10:20:0;;;40:20:0;;;90:5:0{}",
1554            ";".repeat(InstIter::new(&bytecode).count() - 7)
1555        );
1556        assert_eq!(
1557            require_anchors(&bytecode, &[10, 40], &source_map),
1558            [(15, Some(4)), (5, None), (19, Some(9)), (10, None)]
1559        );
1560    }
1561
1562    fn location(bytes: Range<u32>) -> SourceLocation {
1563        SourceLocation { source_id: 0, contract_name: "T".into(), bytes, lines: 1..2 }
1564    }
1565
1566    /// Returns the `(instruction, jump)` of the anchors for the two paths of a ternary spanning
1567    /// bytes 10..50, with its true arm at 20..30 and its false arm at 35..45.
1568    fn ternary_anchors(bytecode: &[u8], source_map: &str) -> Vec<(u32, Option<u32>)> {
1569        let items = (0..2)
1570            .map(|path_id| CoverageItem {
1571                kind: CoverageItemKind::Branch { branch_id: 0, path_id, is_first_opcode: false },
1572                loc: location(10..50),
1573                anchor_loc: None,
1574                hits: 0,
1575            })
1576            .collect();
1577        let arms = TernaryArms { true_arm: location(20..30), false_arm: location(35..45) };
1578        let analysis = SourceAnalysis::for_test(items, vec![(0, BranchKind::Ternary(arms))]);
1579        let source_map = sourcemap::parse(source_map).unwrap();
1580        let ic_pc_map = IcPcMap::new(bytecode);
1581        let anchors = find_anchors(bytecode, &source_map, &ic_pc_map, &analysis);
1582        (0..anchors.anchors.len())
1583            .map(|i| (anchors.anchors[i].instruction, anchors.jumps.get(&i).copied()))
1584            .collect()
1585    }
1586
1587    #[test]
1588    fn ternary_paths_follow_the_arms() {
1589        // `cond; PUSH dest; JUMPI`, then the code of the fallthrough arm, then `dest`, which holds
1590        // the code of the jump target arm.
1591        let bytecode = [
1592            opcode::PUSH1,
1593            0,
1594            opcode::PUSH1,
1595            8,
1596            opcode::JUMPI,
1597            opcode::PUSH0,
1598            opcode::POP,
1599            opcode::STOP,
1600            opcode::JUMPDEST,
1601            opcode::PUSH1,
1602            0,
1603            opcode::POP,
1604            opcode::STOP,
1605        ];
1606        // Path 0 is the false arm and path 1 the true arm. `(pc, jump)` is the fallthrough for
1607        // `(5, None)` and the jump target for `(8, Some(4))`.
1608        let false_falls_through = [(5, None), (8, Some(4))];
1609        let true_falls_through = [(8, Some(4)), (5, None)];
1610        // The jump `10:40` is mapped exactly to the ternary, and the cond to `12:3`.
1611        // The arms' first instructions map to the enclosing `0:100`, as with solc via-IR, which
1612        // jumps over the arms' setup code: only a later instruction maps inside the arm.
1613        for (source_map, expected) in [
1614            // The true arm is the jump target, as with solc's legacy pipeline.
1615            ("12:3:0;;10:40:0;36:3:0;;0:100:0;-1:-1:-1;22:3:0;;", false_falls_through),
1616            // The true arm falls through.
1617            ("12:3:0;;10:40:0;22:3:0;;0:100:0;-1:-1:-1;36:3:0;;", true_falls_through),
1618            // Only the entry code of an arm maps inside it, after a first instruction outside it.
1619            ("12:3:0;;10:40:0;0:100:0;22:3:0;0:100:0;-1:-1:-1;36:3:0;;", true_falls_through),
1620            // The false arm has no code, as with a literal already on the stack: the fallthrough
1621            // reaches the join point, so the true arm is the jump target.
1622            ("12:3:0;;10:40:0;0:100:0;;0:100:0;-1:-1:-1;22:3:0;;", false_falls_through),
1623            // The same polarity, with the code of the arm that has code on the other side.
1624            ("12:3:0;;10:40:0;22:3:0;;0:100:0;-1:-1:-1;0:100:0;;", true_falls_through),
1625            // The true arm has no code and the false arm is the jump target.
1626            ("12:3:0;;10:40:0;0:100:0;;0:100:0;-1:-1:-1;36:3:0;;", true_falls_through),
1627            // The true arm has no code and the false arm falls through.
1628            ("12:3:0;;10:40:0;36:3:0;;0:100:0;-1:-1:-1;0:100:0;;", false_falls_through),
1629            // Neither arm has code, so the positional default stays.
1630            ("12:3:0;;10:40:0;0:100:0;;0:100:0;-1:-1:-1;0:100:0;;", false_falls_through),
1631            // Both successors map inside the same arm, so the positional default stays.
1632            ("12:3:0;;10:40:0;22:3:0;;0:100:0;-1:-1:-1;22:3:0;;", false_falls_through),
1633        ] {
1634            assert_eq!(ternary_anchors(&bytecode, source_map), expected, "{source_map}");
1635        }
1636    }
1637
1638    #[test]
1639    fn ternary_anchor_rejects_missing_node_mapping() {
1640        let loc =
1641            SourceLocation { source_id: 0, contract_name: "T".into(), bytes: 10..30, lines: 1..2 };
1642        let bytecode = [opcode::PUSH1, 6, opcode::JUMPI, opcode::PUSH1, 7, opcode::JUMPI];
1643        // A contained inner span must never substitute for the missing outer decision.
1644        let inner_only = sourcemap::parse("15:5:0;;;").unwrap();
1645        let ic_pc_map = IcPcMap::new(&bytecode);
1646        let index = AnchorIndex::new(&bytecode, &inner_only, &ic_pc_map);
1647        assert!(index.branch(0, &loc, true, None).is_err());
1648    }
1649
1650    fn source_location(start: u32, len: u32) -> SourceLocation {
1651        SourceLocation {
1652            source_id: 0,
1653            contract_name: "T".into(),
1654            bytes: start..start + len,
1655            lines: 1..2,
1656        }
1657    }
1658
1659    fn constant_error_stub() -> Vec<u8> {
1660        vec![
1661            opcode::PUSH4,
1662            0xe3,
1663            0x37,
1664            0x2e,
1665            0x2d,
1666            opcode::PUSH0,
1667            opcode::MSTORE,
1668            opcode::PUSH1,
1669            4,
1670            opcode::PUSH1,
1671            28,
1672            opcode::REVERT,
1673        ]
1674    }
1675
1676    #[test]
1677    fn shared_revert_guards_use_their_own_incoming_edge() {
1678        let mut bytecode = vec![
1679            opcode::PUSH0,
1680            opcode::ISZERO,
1681            opcode::PUSH1,
1682            12,
1683            opcode::JUMPI,
1684            opcode::PUSH0,
1685            opcode::ISZERO,
1686            opcode::PUSH1,
1687            12,
1688            opcode::JUMPI,
1689            opcode::POP,
1690            opcode::STOP,
1691            opcode::JUMPDEST,
1692        ];
1693        bytecode.extend(constant_error_stub());
1694        let text = InstIter::new(&bytecode)
1695            .enumerate()
1696            .map(|(ic, _)| match ic {
1697                0..=3 => "10:10:0",
1698                4..=7 => "30:10:0",
1699                8 => "50:10:0",
1700                _ => "-1:-1:-1",
1701            })
1702            .collect::<Vec<_>>()
1703            .join(";");
1704        let source_map = sourcemap::parse(&text).unwrap();
1705        let ic_pc_map = IcPcMap::new(&bytecode);
1706        let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1707        let mut anchors = ItemAnchors::default();
1708        for (item_id, start) in [(0, 10), (1, 30)] {
1709            let guard = super::super::RevertGuard {
1710                condition: source_location(start, 10),
1711                statement: source_location(start, 10),
1712                function: source_location(0, 100),
1713                selector: [0xe3, 0x37, 0x2e, 0x2d],
1714            };
1715            let (anchor, jump) = index.revert_guard(item_id, &guard).unwrap();
1716            anchors.jumps.insert(anchors.anchors.len(), jump.unwrap());
1717            anchors.anchors.push(anchor);
1718        }
1719        let ambiguous_text = InstIter::new(&bytecode)
1720            .enumerate()
1721            .map(|(ic, _)| if ic < 8 { "10:10:0" } else { "-1:-1:-1" })
1722            .collect::<Vec<_>>()
1723            .join(";");
1724        let ambiguous_map = sourcemap::parse(&ambiguous_text).unwrap();
1725        let ambiguous = AnchorIndex::new(&bytecode, &ambiguous_map, &ic_pc_map);
1726        let guard = super::super::RevertGuard {
1727            condition: source_location(10, 10),
1728            statement: source_location(10, 10),
1729            function: source_location(0, 100),
1730            selector: [0xe3, 0x37, 0x2e, 0x2d],
1731        };
1732        assert!(ambiguous.revert_guard(0, &guard).is_none());
1733        let mut hit_map = super::super::HitMap::new(alloy_primitives::Bytes::new());
1734        hit_map.hits(4, 1);
1735        hit_map.hits(9, 1);
1736        hit_map.hits(10, 1);
1737        hit_map.hits(12, 1);
1738        let hits = anchors
1739            .hits(&hit_map)
1740            .map(|(anchor, hits)| (anchor.item_id, hits.get()))
1741            .collect::<Vec<_>>();
1742        assert_eq!(hits, vec![(0, 1)], "the shared destination must not cover the other guard");
1743    }
1744
1745    #[test]
1746    fn revert_guard_rejects_ambiguous_payloads_and_decisions() {
1747        let mut bytecode = vec![opcode::PUSH0, opcode::PUSH1, 16, opcode::JUMPI];
1748        bytecode.extend(constant_error_stub());
1749        bytecode.push(opcode::JUMPDEST);
1750        bytecode.extend(constant_error_stub());
1751        let text = InstIter::new(&bytecode)
1752            .enumerate()
1753            .map(|(ic, _)| if ic < 3 { "10:10:0" } else { "-1:-1:-1" })
1754            .collect::<Vec<_>>()
1755            .join(";");
1756        let source_map = sourcemap::parse(&text).unwrap();
1757        let ic_pc_map = IcPcMap::new(&bytecode);
1758        let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1759        let guard = super::super::RevertGuard {
1760            condition: source_location(10, 10),
1761            statement: source_location(10, 10),
1762            function: source_location(0, 100),
1763            selector: [0xe3, 0x37, 0x2e, 0x2d],
1764        };
1765        assert!(index.revert_guard(0, &guard).is_none());
1766        assert!(
1767            constant_revert_selector(&[opcode::PUSH1, 4, opcode::PUSH0, opcode::REVERT], 0)
1768                .is_none(),
1769            "uninitialized memory is unknown"
1770        );
1771    }
1772
1773    #[test]
1774    fn revert_guard_does_not_treat_unknown_as_the_opposite_path() {
1775        let mut bytecode = vec![
1776            opcode::PUSH0,
1777            opcode::PUSH1,
1778            19,
1779            opcode::JUMPI,
1780            opcode::PUSH0,
1781            opcode::MLOAD,
1782            opcode::POP,
1783        ];
1784        bytecode.extend(constant_error_stub());
1785        bytecode.push(opcode::JUMPDEST);
1786        bytecode.extend(constant_error_stub());
1787        let text = InstIter::new(&bytecode)
1788            .enumerate()
1789            .map(|(ic, _)| if ic < 3 { "10:10:0" } else { "-1:-1:-1" })
1790            .collect::<Vec<_>>()
1791            .join(";");
1792        let source_map = sourcemap::parse(&text).unwrap();
1793        let ic_pc_map = IcPcMap::new(&bytecode);
1794        let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1795        let guard = super::super::RevertGuard {
1796            condition: source_location(10, 10),
1797            statement: source_location(10, 40),
1798            function: source_location(0, 100),
1799            selector: [0xe3, 0x37, 0x2e, 0x2d],
1800        };
1801        assert!(index.revert_guard(0, &guard).is_none());
1802    }
1803
1804    #[test]
1805    fn alias_statements_require_a_unique_normal_return() {
1806        let bytecode = [opcode::JUMPDEST, opcode::PUSH1, 42, opcode::SWAP1, opcode::JUMP];
1807        let source_map = sourcemap::parse("10:20:0;;;10:20:0:o").unwrap();
1808        let ic_pc_map = IcPcMap::new(&bytecode);
1809        let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1810        let anchor = index.alias_return(0, &source_location(10, 20)).unwrap();
1811        assert_eq!(anchor.instruction, 4);
1812        let anchors = ItemAnchors { anchors: vec![anchor], ..Default::default() };
1813        let uncalled = super::super::HitMap::new(alloy_primitives::Bytes::new());
1814        assert_eq!(anchors.hits(&uncalled).count(), 0);
1815
1816        let brace_map = sourcemap::parse("10:20:0;;;29:1:0:o").unwrap();
1817        let index = AnchorIndex::new(&bytecode, &brace_map, &ic_pc_map);
1818        assert_eq!(index.alias_return(0, &source_location(10, 20)).unwrap().instruction, 4);
1819        for other in ["28:1:0:o", "29:2:0:o", "29:1:1:o", "29:1:0:i"] {
1820            let source_map = sourcemap::parse(&format!("10:20:0;;;{other}")).unwrap();
1821            let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1822            assert!(index.alias_return(0, &source_location(10, 20)).is_none(), "{other}");
1823        }
1824        let brace_entry = sourcemap::parse("10:19:0;;;29:1:0:o").unwrap();
1825        let index = AnchorIndex::new(&bytecode, &brace_entry, &ic_pc_map);
1826        assert!(index.alias_return(0, &source_location(10, 20)).is_none());
1827        for unsupported in
1828            [opcode::MLOAD, opcode::JUMPI, opcode::CALL, opcode::INVALID, opcode::REVERT]
1829        {
1830            let bytecode = [opcode::JUMPDEST, unsupported, opcode::SWAP1, opcode::JUMP];
1831            let ic_pc_map = IcPcMap::new(&bytecode);
1832            let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1833            assert!(index.alias_return(0, &source_location(10, 20)).is_none());
1834        }
1835    }
1836
1837    #[test]
1838    fn statement_anchors_do_not_depend_on_cold_stub_order() {
1839        let loc =
1840            SourceLocation { source_id: 0, contract_name: "T".into(), bytes: 10..30, lines: 1..2 };
1841        for (bytecode, expected) in [
1842            (
1843                vec![
1844                    opcode::PUSH0,
1845                    opcode::PUSH0,
1846                    opcode::REVERT,
1847                    opcode::JUMPDEST,
1848                    opcode::PUSH0,
1849                    opcode::PUSH0,
1850                    opcode::RETURN,
1851                ],
1852                3,
1853            ),
1854            (
1855                vec![
1856                    opcode::PUSH0,
1857                    opcode::PUSH0,
1858                    opcode::RETURN,
1859                    opcode::JUMPDEST,
1860                    opcode::PUSH0,
1861                    opcode::PUSH0,
1862                    opcode::REVERT,
1863                ],
1864                0,
1865            ),
1866            (vec![opcode::PUSH0, opcode::PUSH0, opcode::INVALID], 0),
1867            (vec![opcode::PUSH0, opcode::PUSH0, opcode::REVERT], 0),
1868            (
1869                vec![
1870                    opcode::PUSH0,
1871                    opcode::PUSH1,
1872                    7,
1873                    opcode::JUMPI,
1874                    opcode::PUSH0,
1875                    opcode::PUSH0,
1876                    opcode::REVERT,
1877                    opcode::JUMPDEST,
1878                    opcode::STOP,
1879                ],
1880                0,
1881            ),
1882            // A JUMPDEST-led failure stub before the real code is skipped.
1883            (
1884                vec![
1885                    opcode::JUMPDEST,
1886                    opcode::PUSH0,
1887                    opcode::PUSH0,
1888                    opcode::REVERT,
1889                    opcode::JUMPDEST,
1890                    opcode::PUSH0,
1891                    opcode::PUSH0,
1892                    opcode::RETURN,
1893                ],
1894                4,
1895            ),
1896            // Code falling through into the stub's JUMPDEST is not part of the failure run.
1897            (
1898                vec![
1899                    opcode::PUSH0,
1900                    opcode::JUMPDEST,
1901                    opcode::PUSH0,
1902                    opcode::PUSH0,
1903                    opcode::REVERT,
1904                    opcode::JUMPDEST,
1905                    opcode::STOP,
1906                ],
1907                0,
1908            ),
1909            // Adjacent JUMPDESTs lead the same failure stub.
1910            (
1911                vec![
1912                    opcode::JUMPDEST,
1913                    opcode::JUMPDEST,
1914                    opcode::PUSH0,
1915                    opcode::PUSH0,
1916                    opcode::REVERT,
1917                    opcode::JUMPDEST,
1918                    opcode::STOP,
1919                ],
1920                5,
1921            ),
1922            // A JUMPDEST-led failure stub is still the fallback when it is the only candidate.
1923            (vec![opcode::JUMPDEST, opcode::PUSH0, opcode::PUSH0, opcode::REVERT], 0),
1924        ] {
1925            let count = InstIter::new(&bytecode).count();
1926            let source_map =
1927                sourcemap::parse(&format!("10:20:0{}", ";".repeat(count - 1))).unwrap();
1928            let ic_pc_map = IcPcMap::new(&bytecode);
1929            let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
1930            assert_eq!(index.simple(0, &loc).unwrap().instruction, expected);
1931        }
1932    }
1933
1934    #[test]
1935    fn statement_anchor_skips_blocks_reached_only_from_inside() {
1936        let loc =
1937            SourceLocation { source_id: 0, contract_name: "T".into(), bytes: 10..30, lines: 1..2 };
1938        // Code outside the span (`0:100`) jumps over a block that belongs to the span, and which
1939        // is laid out before the span's entry.
1940        for (bytecode, source_map, expected) in [
1941            // The entry falls through from outside, and the earlier block is only jumped to from
1942            // inside.
1943            (
1944                vec![
1945                    opcode::PUSH1,
1946                    5,
1947                    opcode::JUMP,
1948                    opcode::JUMPDEST,
1949                    opcode::STOP,
1950                    opcode::JUMPDEST,
1951                    opcode::PUSH1,
1952                    3,
1953                    opcode::JUMP,
1954                ],
1955                "0:100:0;;15:5:0;;0:100:0;12:3:0;",
1956                6,
1957            ),
1958            // A return address pushed from inside, before a call, does not make the earlier
1959            // block an entry.
1960            (
1961                vec![
1962                    opcode::PUSH1,
1963                    5,
1964                    opcode::JUMP,
1965                    opcode::JUMPDEST,
1966                    opcode::STOP,
1967                    opcode::JUMPDEST,
1968                    opcode::PUSH1,
1969                    3,
1970                    opcode::PUSH1,
1971                    5,
1972                    opcode::JUMP,
1973                ],
1974                "0:100:0;;15:5:0;;0:100:0;12:3:0;;;",
1975                6,
1976            ),
1977            // A constant that equals a `JUMPDEST` address, but is not a jump or return address, is
1978            // not a way in: the dynamically entered block stays the anchor.
1979            (
1980                vec![
1981                    opcode::PUSH0,
1982                    opcode::CALLDATALOAD,
1983                    opcode::JUMP,
1984                    opcode::JUMPDEST,
1985                    opcode::PUSH1,
1986                    3,
1987                    opcode::PUSH0,
1988                    opcode::MSTORE,
1989                    opcode::PUSH1,
1990                    0x20,
1991                    opcode::PUSH0,
1992                    opcode::RETURN,
1993                    opcode::JUMPDEST,
1994                    opcode::STOP,
1995                ],
1996                "0:100:0;;;15:5:0;;;;;;;;;;",
1997                3,
1998            ),
1999            // The entry is jumped to from outside.
2000            (
2001                vec![
2002                    opcode::PUSH1,
2003                    5,
2004                    opcode::JUMP,
2005                    opcode::JUMPDEST,
2006                    opcode::STOP,
2007                    opcode::JUMPDEST,
2008                    opcode::PUSH1,
2009                    3,
2010                    opcode::JUMP,
2011                ],
2012                "0:100:0;;15:5:0;;16:4:0;12:3:0;",
2013                5,
2014            ),
2015            // An unmapped `JUMPDEST` belongs to the block it leads, so it does not make the code
2016            // after it an entry.
2017            (
2018                vec![
2019                    opcode::PUSH1,
2020                    7,
2021                    opcode::JUMP,
2022                    opcode::JUMPDEST,
2023                    opcode::JUMPDEST,
2024                    opcode::PUSH0,
2025                    opcode::STOP,
2026                    opcode::JUMPDEST,
2027                    opcode::PUSH1,
2028                    3,
2029                    opcode::JUMP,
2030                ],
2031                "0:100:0;;15:5:0;-1:-1:-1;15:5:0;;16:4:0;12:3:0;",
2032                7,
2033            ),
2034            // A jump mapped to a longer span that starts inside the item, as the parent
2035            // expression's merge label does, does not make the earlier block an entry.
2036            (
2037                vec![
2038                    opcode::PUSH1,
2039                    5,
2040                    opcode::JUMP,
2041                    opcode::JUMPDEST,
2042                    opcode::STOP,
2043                    opcode::JUMPDEST,
2044                    opcode::PUSH1,
2045                    3,
2046                    opcode::JUMP,
2047                ],
2048                "0:100:0;;10:50:0;;16:4:0;10:50:0;",
2049                5,
2050            ),
2051            // A block that is also entered from outside, as a loop head is, stays an entry.
2052            (
2053                vec![opcode::JUMPDEST, opcode::JUMPDEST, opcode::PUSH1, 1, opcode::JUMP],
2054                "0:100:0;12:3:0;15:2:0;;",
2055                1,
2056            ),
2057            (
2058                vec![
2059                    opcode::PUSH1,
2060                    5,
2061                    opcode::JUMP,
2062                    opcode::JUMPDEST,
2063                    opcode::STOP,
2064                    opcode::JUMPDEST,
2065                    opcode::PUSH1,
2066                    3,
2067                    opcode::STOP,
2068                    opcode::PUSH1,
2069                    3,
2070                    opcode::STOP,
2071                ],
2072                "0:100:0;;15:5:0;;12:3:0;;;0:100:0;;",
2073                3,
2074            ),
2075            // An unmapped push belongs to the code it follows, so a join that only an unmapped
2076            // `PUSH; JUMP` out of the item's own code reaches is not an entry.
2077            (
2078                vec![
2079                    opcode::PUSH1,
2080                    5,
2081                    opcode::JUMP,
2082                    opcode::JUMPDEST,
2083                    opcode::STOP,
2084                    opcode::JUMPDEST,
2085                    opcode::PUSH0,
2086                    opcode::PUSH1,
2087                    3,
2088                    opcode::JUMP,
2089                ],
2090                "0:100:0;;15:5:0;;16:4:0;12:3:0;-1:-1:-1;",
2091                5,
2092            ),
2093            // The same push after code outside the item is a way in from outside.
2094            (
2095                vec![
2096                    opcode::PUSH1,
2097                    5,
2098                    opcode::JUMP,
2099                    opcode::JUMPDEST,
2100                    opcode::STOP,
2101                    opcode::JUMPDEST,
2102                    opcode::PUSH0,
2103                    opcode::PUSH1,
2104                    3,
2105                    opcode::JUMP,
2106                ],
2107                "0:100:0;;15:5:0;;16:4:0;0:100:0;-1:-1:-1;",
2108                3,
2109            ),
2110            // A push from outside to an unmapped `JUMPDEST` makes the block it leads an entry.
2111            (
2112                vec![
2113                    opcode::PUSH1,
2114                    4,
2115                    opcode::JUMP,
2116                    opcode::JUMPDEST,
2117                    opcode::JUMPDEST,
2118                    opcode::PUSH1,
2119                    3,
2120                    opcode::JUMP,
2121                ],
2122                "0:100:0;;15:5:0;-1:-1:-1;12:3:0;;",
2123                5,
2124            ),
2125            // A block that nothing is known to reach is an entry even when a later block is
2126            // entered from outside.
2127            (
2128                vec![
2129                    opcode::PUSH1,
2130                    7,
2131                    opcode::JUMP,
2132                    opcode::JUMPDEST,
2133                    opcode::STOP,
2134                    opcode::JUMPDEST,
2135                    opcode::STOP,
2136                    opcode::JUMPDEST,
2137                    opcode::PUSH1,
2138                    3,
2139                    opcode::JUMP,
2140                ],
2141                "0:100:0;;15:5:0;;16:4:0;;17:3:0;;",
2142                5,
2143            ),
2144            // The lowest instruction stays the anchor when nothing is known to reach it, as with
2145            // a function entered by a dynamic jump.
2146            (
2147                vec![opcode::STOP, opcode::JUMPDEST, opcode::PUSH0, opcode::STOP],
2148                "0:100:0;15:5:0;;",
2149                1,
2150            ),
2151        ] {
2152            let source_map = sourcemap::parse(source_map).unwrap();
2153            let ic_pc_map = IcPcMap::new(&bytecode);
2154            let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
2155            assert_eq!(index.simple(0, &loc).unwrap().instruction, expected, "{source_map:?}");
2156        }
2157    }
2158
2159    #[test]
2160    fn function_anchor_prefers_jumped_to_entry_over_earlier_body_block() {
2161        let loc =
2162            SourceLocation { source_id: 0, contract_name: "T".into(), bytes: 10..30, lines: 1..2 };
2163        // A body block (inner span) is laid out before the entry JUMPDEST (exact span), which a
2164        // call site jumps to.
2165        let bytecode = [
2166            opcode::JUMPDEST,
2167            opcode::PUSH0,
2168            opcode::STOP,
2169            opcode::JUMPDEST,
2170            opcode::PUSH0,
2171            opcode::STOP,
2172            opcode::PUSH1,
2173            3,
2174            opcode::JUMP,
2175        ];
2176        let ic_pc_map = IcPcMap::new(&bytecode);
2177        for (source_map, expected) in [
2178            // Call site outside the function.
2179            ("15:5:0;;;10:20:0;;0:100:0;", 3),
2180            // A same-start but shorter span is not the entry.
2181            ("15:5:0;;;10:5:0;;0:100:0;", 0),
2182            // The only jump is inside the function, so the JUMPDEST is its exit.
2183            ("15:5:0;;;10:20:0;;12:3:0;", 0),
2184            // An unmapped jump with no mapped code falling into it gives no evidence of a call.
2185            ("15:5:0;;;10:20:0;;;-1:-1:-1;", 0),
2186        ] {
2187            let source_map = sourcemap::parse(source_map).unwrap();
2188            let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
2189            assert_eq!(index.simple(0, &loc).unwrap().instruction, 0);
2190            assert_eq!(index.function(0, &loc).unwrap().instruction, expected, "{source_map:?}");
2191        }
2192
2193        // A lower exact-span `JUMPDEST` that nothing jumps to, such as a via-IR return point, and
2194        // an exact-span failure stub that only the function itself jumps to are not the entry.
2195        for (bytecode, source_map, expected) in [
2196            (
2197                vec![
2198                    opcode::JUMPDEST,
2199                    opcode::PUSH0,
2200                    opcode::STOP,
2201                    opcode::JUMPDEST,
2202                    opcode::PUSH0,
2203                    opcode::STOP,
2204                    opcode::PUSH1,
2205                    3,
2206                    opcode::JUMP,
2207                ],
2208                "10:20:0;;;;;;0:100:0;",
2209                3,
2210            ),
2211            (
2212                vec![
2213                    opcode::JUMPDEST,
2214                    opcode::PUSH0,
2215                    opcode::PUSH0,
2216                    opcode::REVERT,
2217                    opcode::JUMPDEST,
2218                    opcode::STOP,
2219                    opcode::PUSH1,
2220                    0,
2221                    opcode::JUMPI,
2222                    opcode::PUSH1,
2223                    4,
2224                    opcode::JUMP,
2225                ],
2226                "10:20:0;;;;;;12:3:0;;0:100:0;",
2227                4,
2228            ),
2229            // An unmapped jump belongs to the code it follows: inside the function it is not a
2230            // call from outside, so the lowest instruction stays the anchor.
2231            (
2232                vec![
2233                    opcode::JUMPDEST,
2234                    opcode::PUSH0,
2235                    opcode::STOP,
2236                    opcode::JUMPDEST,
2237                    opcode::PUSH0,
2238                    opcode::STOP,
2239                    opcode::JUMPDEST,
2240                    opcode::PUSH0,
2241                    opcode::PUSH1,
2242                    3,
2243                    opcode::JUMP,
2244                ],
2245                "15:5:0;;;10:20:0;;;12:3:0;;-1:-1:-1;",
2246                0,
2247            ),
2248            // After code outside the function it is a call from outside.
2249            (
2250                vec![
2251                    opcode::JUMPDEST,
2252                    opcode::PUSH0,
2253                    opcode::STOP,
2254                    opcode::JUMPDEST,
2255                    opcode::PUSH0,
2256                    opcode::STOP,
2257                    opcode::JUMPDEST,
2258                    opcode::PUSH0,
2259                    opcode::PUSH1,
2260                    3,
2261                    opcode::JUMP,
2262                ],
2263                "15:5:0;;;10:20:0;;;0:100:0;;-1:-1:-1;",
2264                3,
2265            ),
2266            // A public function's ABI wrapper (jumped to by the dispatcher) falls into its body
2267            // (jumped to by internal calls), which is the anchor that runs on both paths.
2268            (
2269                vec![
2270                    opcode::JUMPDEST,
2271                    opcode::PUSH0,
2272                    opcode::POP,
2273                    opcode::JUMPDEST,
2274                    opcode::PUSH0,
2275                    opcode::STOP,
2276                    opcode::PUSH1,
2277                    0,
2278                    opcode::JUMP,
2279                    opcode::PUSH1,
2280                    3,
2281                    opcode::JUMP,
2282                ],
2283                "10:20:0;;;;;;0:100:0;;;",
2284                3,
2285            ),
2286            // A `JUMPI` to a failure stub does not end the run, so the wrapper still falls into
2287            // the body.
2288            (
2289                vec![
2290                    opcode::JUMPDEST,
2291                    opcode::PUSH1,
2292                    13,
2293                    opcode::JUMPI,
2294                    opcode::JUMPDEST,
2295                    opcode::PUSH0,
2296                    opcode::STOP,
2297                    opcode::PUSH1,
2298                    0,
2299                    opcode::JUMP,
2300                    opcode::PUSH1,
2301                    4,
2302                    opcode::JUMP,
2303                    opcode::JUMPDEST,
2304                    opcode::PUSH0,
2305                    opcode::PUSH0,
2306                    opcode::REVERT,
2307                ],
2308                "10:20:0;;;;;;0:100:0;;;;10:20:0;;;",
2309                4,
2310            ),
2311            // A `JUMPI` to other code ends the run, as with `&&` and `||` join blocks, so the
2312            // lowest candidate does not fall into a tail shared with other code.
2313            (
2314                vec![
2315                    opcode::JUMPDEST,
2316                    opcode::PUSH1,
2317                    4,
2318                    opcode::JUMPI,
2319                    opcode::JUMPDEST,
2320                    opcode::PUSH0,
2321                    opcode::STOP,
2322                    opcode::PUSH1,
2323                    0,
2324                    opcode::JUMP,
2325                    opcode::PUSH1,
2326                    4,
2327                    opcode::JUMP,
2328                ],
2329                "10:20:0;;;;;;0:100:0;;;",
2330                0,
2331            ),
2332            // A `JUMPI` to a block that jumps to a failure stub, such as an optimized panic helper
2333            // call, does not end the run either.
2334            (
2335                vec![
2336                    opcode::JUMPDEST,
2337                    opcode::PUSH1,
2338                    13,
2339                    opcode::JUMPI,
2340                    opcode::JUMPDEST,
2341                    opcode::PUSH0,
2342                    opcode::STOP,
2343                    opcode::PUSH1,
2344                    0,
2345                    opcode::JUMP,
2346                    opcode::PUSH1,
2347                    4,
2348                    opcode::JUMP,
2349                    opcode::JUMPDEST,
2350                    opcode::PUSH1,
2351                    17,
2352                    opcode::JUMP,
2353                    opcode::JUMPDEST,
2354                    opcode::PUSH0,
2355                    opcode::PUSH0,
2356                    opcode::REVERT,
2357                ],
2358                "10:20:0;;;;;;0:100:0;;;;-1:-1:-1;;;;;;",
2359                4,
2360            ),
2361            // An unmapped helper `JUMP`, such as an ABI decoder returning to the wrapper, does not
2362            // end the run, but a mapped `JUMP` does.
2363            (
2364                vec![
2365                    opcode::JUMPDEST,
2366                    opcode::PUSH1,
2367                    4,
2368                    opcode::JUMP,
2369                    opcode::JUMPDEST,
2370                    opcode::PUSH0,
2371                    opcode::STOP,
2372                    opcode::PUSH1,
2373                    0,
2374                    opcode::JUMP,
2375                    opcode::PUSH1,
2376                    4,
2377                    opcode::JUMP,
2378                ],
2379                "10:20:0;;-1:-1:-1;10:20:0;;;0:100:0;;;",
2380                4,
2381            ),
2382            (
2383                vec![
2384                    opcode::JUMPDEST,
2385                    opcode::PUSH1,
2386                    4,
2387                    opcode::JUMP,
2388                    opcode::JUMPDEST,
2389                    opcode::PUSH0,
2390                    opcode::STOP,
2391                    opcode::PUSH1,
2392                    0,
2393                    opcode::JUMP,
2394                    opcode::PUSH1,
2395                    4,
2396                    opcode::JUMP,
2397                ],
2398                "10:20:0;;12:3:0;10:20:0;;;0:100:0;;;",
2399                0,
2400            ),
2401            // An exact-span block that other code jumps to, as an optimizer-merged exit, is not
2402            // preferred when no other candidate falls through into it.
2403            (
2404                vec![
2405                    opcode::JUMPDEST,
2406                    opcode::PUSH0,
2407                    opcode::JUMP,
2408                    opcode::JUMPDEST,
2409                    opcode::PUSH0,
2410                    opcode::JUMPDEST,
2411                    opcode::STOP,
2412                    opcode::PUSH1,
2413                    0,
2414                    opcode::JUMP,
2415                    opcode::PUSH1,
2416                    5,
2417                    opcode::JUMP,
2418                ],
2419                "10:20:0;;;12:3:0;;10:20:0;;0:100:0;;;",
2420                0,
2421            ),
2422        ] {
2423            let source_map = sourcemap::parse(source_map).unwrap();
2424            let ic_pc_map = IcPcMap::new(&bytecode);
2425            let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
2426            assert_eq!(index.function(0, &loc).unwrap().instruction, expected);
2427        }
2428
2429        // An exact-span instruction that nothing jumps to is not an entry, as in an inlined
2430        // constructor whose exact span only marks its trailing cleanup.
2431        let bytecode = [opcode::PUSH0, opcode::POP, opcode::PUSH0, opcode::POP, opcode::STOP];
2432        let source_map = sourcemap::parse("15:5:0;;10:20:0;;").unwrap();
2433        let ic_pc_map = IcPcMap::new(&bytecode);
2434        let index = AnchorIndex::new(&bytecode, &source_map, &ic_pc_map);
2435        assert_eq!(index.function(0, &loc).unwrap().instruction, 0);
2436    }
2437
2438    /// Returns the `(instruction, jump)` of the anchors for the paths of an `if` spanning bytes
2439    /// 10..70, with its then arm at 40..60 and, if given, its else arm at 61..69.
2440    fn if_anchors(bytecode: &[u8], source_map: &str, else_arm: bool) -> Vec<(u32, Option<u32>)> {
2441        let anchors = find_if_anchors(bytecode, source_map, else_arm);
2442        (0..anchors.anchors.len())
2443            .map(|i| (anchors.anchors[i].instruction, anchors.jumps.get(&i).copied()))
2444            .collect()
2445    }
2446
2447    fn find_if_anchors(bytecode: &[u8], source_map: &str, else_arm: bool) -> ItemAnchors {
2448        find_if_anchors_after(bytecode, source_map, else_arm, true)
2449    }
2450
2451    /// Like [`find_if_anchors`], with the next statement at 80..90 only if `after`.
2452    fn find_if_anchors_after(
2453        bytecode: &[u8],
2454        source_map: &str,
2455        else_arm: bool,
2456        after: bool,
2457    ) -> ItemAnchors {
2458        find_if_anchors_calling(bytecode, source_map, else_arm, after, None, None)
2459    }
2460
2461    /// Like [`find_if_anchors_after`], with the function that each arm calls at the given byte
2462    /// range.
2463    fn find_if_anchors_calling(
2464        bytecode: &[u8],
2465        source_map: &str,
2466        else_arm: bool,
2467        after: bool,
2468        then_callee: Option<Range<u32>>,
2469        else_callee: Option<Range<u32>>,
2470    ) -> ItemAnchors {
2471        let arms = IfArms {
2472            then_arm: location(40..60),
2473            else_arm: else_arm.then(|| location(61..69)),
2474            after: after.then(|| location(80..90)),
2475            then_callees: then_callee.into_iter().map(location).collect(),
2476            else_callees: else_callee.into_iter().map(location).collect(),
2477        };
2478        let items = (0..2 - u32::from(!else_arm))
2479            .map(|path_id| CoverageItem {
2480                kind: CoverageItemKind::Branch { branch_id: 0, path_id, is_first_opcode: true },
2481                loc: location(10..70),
2482                anchor_loc: Some(if path_id == 0 {
2483                    arms.then_arm.clone()
2484                } else {
2485                    arms.else_arm.clone().unwrap()
2486                }),
2487                hits: 0,
2488            })
2489            .collect();
2490        let analysis = SourceAnalysis::for_test(items, vec![(0, BranchKind::If(arms))]);
2491        let source_map = sourcemap::parse(source_map).unwrap();
2492        let ic_pc_map = IcPcMap::new(bytecode);
2493        find_anchors(bytecode, &source_map, &ic_pc_map, &analysis)
2494    }
2495
2496    #[test]
2497    fn if_arms_without_code_count_the_jump_edge() {
2498        // `cond; PUSH exit; JUMPI`, then the code after the `if` and, at `exit`, an epilogue. The
2499        // `if` is mapped to 10..70, its condition to 12..15, the code after it to 80..85, and the
2500        // epilogue to the enclosing function, as with a `break` that leaves a loop.
2501        let after_then_exit = [
2502            opcode::PUSH1,
2503            0,
2504            opcode::PUSH1,
2505            8,
2506            opcode::JUMPI,
2507            opcode::PUSH0,
2508            opcode::POP,
2509            opcode::STOP,
2510            opcode::JUMPDEST,
2511            opcode::PUSH0,
2512            opcode::RETURN,
2513        ];
2514        // The same code with the epilogue first, as when the compiler jumps over it.
2515        let exit_then_after = [
2516            opcode::PUSH1,
2517            0,
2518            opcode::PUSH1,
2519            8,
2520            opcode::JUMPI,
2521            opcode::PUSH0,
2522            opcode::PUSH0,
2523            opcode::RETURN,
2524            opcode::JUMPDEST,
2525            opcode::PUSH0,
2526            opcode::STOP,
2527        ];
2528        // The arm is the taken edge: its count is the jump's minus the fallthrough's.
2529        let taken = [(8, Some(4))];
2530        // The arm is the fallthrough edge: its count is the hits of the instruction after the jump.
2531        let fallthrough = [(5, None)];
2532        for (bytecode, source_map, expected) in [
2533            (&after_then_exit[..], "12:3:0;;10:60:0;80:5:0;;;0:100:0;;", &taken[..]),
2534            // A jump target push mapped inside the arm runs with the jump, so it is not the arm's.
2535            (&after_then_exit[..], "12:3:0;45:5:0;10:60:0;80:5:0;;;0:100:0;;", &taken),
2536            (&exit_then_after[..], "12:3:0;;10:60:0;0:100:0;;;80:5:0;;", &fallthrough),
2537            // The jump's element can run one byte past the span of an `if` without braces, which
2538            // ends before the `;`.
2539            (&after_then_exit[..], "12:3:0;;10:61:0;80:5:0;;;0:100:0;;", &taken),
2540            // The arm continues a loop at code mapped before the `if`.
2541            (&after_then_exit[..], "12:3:0;;10:60:0;80:5:0;;;5:3:0;;", &taken),
2542            // The push is the arm even when both sides reach code after the `if`.
2543            (&after_then_exit[..], "12:3:0;45:5:0;10:60:0;80:5:0;;;85:5:0;;", &taken),
2544            // Both sides reach code outside the `if`, so nothing tells the arm from the skip.
2545            (&after_then_exit[..], "12:3:0;;10:60:0;80:5:0;;;85:5:0;;", &[]),
2546            // The arm has code of its own, which anchors it as before.
2547            (&exit_then_after[..], "12:3:0;;10:60:0;45:5:0;;;80:5:0;;", &fallthrough),
2548        ] {
2549            assert_eq!(if_anchors(bytecode, source_map, false), expected, "{source_map}");
2550        }
2551    }
2552
2553    #[test]
2554    fn if_edges_follow_the_arm_with_code() {
2555        // An else arm with code tells the sides apart, so the then arm without code is the other.
2556        let bytecode = [
2557            opcode::PUSH1,
2558            0,
2559            opcode::PUSH1,
2560            8,
2561            opcode::JUMPI,
2562            opcode::PUSH0,
2563            opcode::POP,
2564            opcode::STOP,
2565            opcode::JUMPDEST,
2566            opcode::PUSH0,
2567            opcode::STOP,
2568        ];
2569        // Path 0 counts the jump's edge and path 1 anchors on the code of its own.
2570        assert_eq!(
2571            if_anchors(&bytecode, "12:3:0;;10:60:0;63:3:0;;;80:5:0;;", true),
2572            [(8, Some(4)), (5, None)]
2573        );
2574        // The else arm is the taken side, so path 0 is the fallthrough.
2575        assert_eq!(
2576            if_anchors(&bytecode, "12:3:0;;10:60:0;80:5:0;;;63:3:0;;", true),
2577            [(5, None), (8, None)]
2578        );
2579        // An arm with code on each side decides nothing alone, so nothing is guessed for it.
2580        assert_eq!(if_anchors(&bytecode, "12:3:0;;10:60:0;63:3:0;;;63:3:0;;", true), [(5, None)]);
2581    }
2582
2583    #[test]
2584    fn if_edges_follow_the_code_of_called_functions() {
2585        // Neither arm has code of its own: each calls a function that the compiler inlined, so
2586        // the source map attributes its code to the function. The then arm calls the function at
2587        // 100..110 and the else arm the one at 120..130.
2588        let bytecode = [
2589            opcode::PUSH1,
2590            0,
2591            opcode::PUSH1,
2592            8,
2593            opcode::JUMPI,
2594            opcode::PUSH0,
2595            opcode::POP,
2596            opcode::STOP,
2597            opcode::JUMPDEST,
2598            opcode::PUSH0,
2599            opcode::POP,
2600            opcode::STOP,
2601        ];
2602        // Each flag makes the arm call the function at 100..110 for the then arm and 120..130 for
2603        // the else arm.
2604        let anchors = |source_map, then_calls: bool, else_calls: bool| {
2605            let anchors = find_if_anchors_calling(
2606                &bytecode,
2607                source_map,
2608                true,
2609                true,
2610                then_calls.then_some(100..110),
2611                else_calls.then_some(120..130),
2612            );
2613            (0..anchors.anchors.len())
2614                .map(|i| (anchors.anchors[i].instruction, anchors.jumps.get(&i).copied()))
2615                .collect::<Vec<_>>()
2616        };
2617        // The taken side runs the then arm's function, so path 0 counts the jump's edge and path 1
2618        // the fallthrough, however the two are laid out.
2619        assert_eq!(
2620            anchors("12:3:0;;10:60:0;125:3:0;;;105:3:0;;;", true, true),
2621            [(8, Some(4)), (5, None)]
2622        );
2623        assert_eq!(
2624            anchors("12:3:0;;10:60:0;105:3:0;;;125:3:0;;;", true, true),
2625            [(5, None), (8, Some(4))]
2626        );
2627        // One arm's function is enough to tell the sides apart.
2628        assert_eq!(
2629            anchors("12:3:0;;10:60:0;125:3:0;;;105:3:0;;;", false, true),
2630            [(8, Some(4)), (5, None)]
2631        );
2632        // Both sides run the same function, so nothing is guessed.
2633        assert!(anchors("12:3:0;;10:60:0;105:3:0;;;105:3:0;;;", true, false).is_empty());
2634        // Neither arm calls a function that the code runs.
2635        assert!(anchors("12:3:0;;10:60:0;125:3:0;;;105:3:0;;;", false, false).is_empty());
2636        assert!(anchors("12:3:0;;10:60:0;225:3:0;;;205:3:0;;;", true, true).is_empty());
2637    }
2638
2639    #[test]
2640    fn if_edges_are_not_guessed_when_ambiguous() {
2641        // Without a next statement in the block, as when the `if` ends a loop body, the skip side
2642        // is not known to reach any code, so a `break` is told apart by its jump target only.
2643        let after_then_exit = [
2644            opcode::PUSH1,
2645            0,
2646            opcode::PUSH1,
2647            8,
2648            opcode::JUMPI,
2649            opcode::PUSH0,
2650            opcode::POP,
2651            opcode::STOP,
2652            opcode::JUMPDEST,
2653            opcode::PUSH0,
2654            opcode::RETURN,
2655        ];
2656        let anchors = find_if_anchors_after(
2657            &after_then_exit,
2658            "12:3:0;;10:60:0;80:5:0;;;0:100:0;;",
2659            false,
2660            false,
2661        );
2662        assert!(anchors.anchors.is_empty());
2663
2664        // The skip side runs code that is mapped to the function, and joins the other side's
2665        // code, as with `if (c) { x = 2; }` when the constant feeds the join point.
2666        let joined = [
2667            opcode::PUSH1,
2668            0,
2669            opcode::PUSH1,
2670            6,
2671            opcode::JUMPI,
2672            opcode::PUSH0,
2673            opcode::JUMPDEST,
2674            opcode::PUSH0,
2675            opcode::STOP,
2676        ];
2677        assert!(if_anchors(&joined, "12:3:0;;10:60:0;0:100:0;10:60:0;80:5:0;;", false).is_empty());
2678
2679        // The fallthrough is a `JUMPDEST` that other code can enter. A static jump to it is
2680        // discounted from its hits, but a push of its address that no jump consumes, such as a
2681        // return address, may enter it any number of times.
2682        let entered = |entry: &[u8]| {
2683            let mut bytecode = vec![
2684                opcode::PUSH1,
2685                0,
2686                opcode::PUSH1,
2687                8,
2688                opcode::JUMPI,
2689                opcode::JUMPDEST,
2690                opcode::PUSH0,
2691                opcode::RETURN,
2692                opcode::JUMPDEST,
2693                opcode::PUSH0,
2694                opcode::STOP,
2695            ];
2696            bytecode.extend_from_slice(entry);
2697            let source_map =
2698                format!("12:3:0;;10:60:0;0:100:0;;;80:5:0;;;{}", ";".repeat(entry.len()));
2699            let anchors = find_if_anchors(&bytecode, &source_map, false);
2700            (anchors.anchors.len(), anchors.entries.get(&0).cloned())
2701        };
2702        assert_eq!(entered(&[]), (1, None));
2703        // `PUSH1 5; JUMP` at pc 11 and 13.
2704        assert_eq!(entered(&[opcode::PUSH1, 5, opcode::JUMP]), (1, Some(vec![(13, false)])));
2705        assert_eq!(entered(&[opcode::PUSH1, 5, opcode::PUSH1, 0, opcode::JUMP]), (0, None));
2706        // A constant that no jump follows is not an entry.
2707        assert_eq!(entered(&[opcode::PUSH1, 5, opcode::POP]), (1, None));
2708
2709        // A second jump inside the `if` and outside its arms, as in `if (a && b)`, may enter the
2710        // arm too.
2711        let and = [
2712            opcode::PUSH1,
2713            0,
2714            opcode::PUSH1,
2715            13,
2716            opcode::JUMPI,
2717            opcode::PUSH1,
2718            0,
2719            opcode::PUSH1,
2720            13,
2721            opcode::JUMPI,
2722            opcode::PUSH0,
2723            opcode::POP,
2724            opcode::STOP,
2725            opcode::JUMPDEST,
2726            opcode::PUSH0,
2727            opcode::RETURN,
2728        ];
2729        assert!(if_anchors(&and, "12:3:0;;12:3:0;;;10:60:0;80:5:0;;;0:100:0;;", false).is_empty());
2730
2731        // A jump to a failure in the condition, such as an overflow check, cannot enter the arm.
2732        let checked = [
2733            opcode::PUSH1,
2734            0,
2735            opcode::PUSH1,
2736            16,
2737            opcode::JUMPI,
2738            opcode::PUSH1,
2739            0,
2740            opcode::PUSH1,
2741            13,
2742            opcode::JUMPI,
2743            opcode::PUSH0,
2744            opcode::POP,
2745            opcode::STOP,
2746            opcode::JUMPDEST,
2747            opcode::PUSH0,
2748            opcode::RETURN,
2749            opcode::JUMPDEST,
2750            opcode::PUSH0,
2751            opcode::PUSH0,
2752            opcode::REVERT,
2753        ];
2754        assert_eq!(
2755            if_anchors(&checked, "12:3:0;;12:3:0;;;10:60:0;80:5:0;;;0:100:0;;;0:100:0;;;", false),
2756            [(13, Some(9))]
2757        );
2758    }
2759}