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
39type EdgeAnchor = (ItemAnchor, Option<u32>, Vec<(u32, bool)>);
42
43fn jump_destination(immediate: &[u8]) -> eyre::Result<u32> {
45 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
52pub 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 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 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 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 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
168pub 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
190const MAX_TRACE_HOPS: usize = 8;
192
193struct AnchorIndex<'a> {
195 bytecode: &'a [u8],
196 source_map: &'a SourceMap,
197 pcs: Vec<u32>,
199 ic_pc_map: &'a IcPcMap,
200 entries: Vec<(i32, u32, usize)>,
202 branches: Vec<(usize, usize, &'a [u8])>,
204 reverting_runs: Vec<Range<usize>>,
206 fallen_into: Vec<(usize, usize)>,
212 jumps: Vec<(u32, usize)>,
214 address_pushes: Vec<(u32, usize)>,
217 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 let mut pushes = Vec::new();
235 let mut falls_through = Vec::new();
236 let mut opcodes = Vec::new();
237 let mut jumpdests = Vec::new();
239 let mut run_ends = Vec::new();
241 let mut conditional_jumps = Vec::new();
242 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 fn if_edge(
736 &self,
737 item_id: u32,
738 path_id: u32,
739 loc: &SourceLocation,
740 arms: &IfArms,
741 ) -> Option<EdgeAnchor> {
742 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 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 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 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 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 fn trace(&self, pc: u32) -> Vec<usize> {
855 let mut trace = Vec::new();
856 let mut next = self.pcs.binary_search(&pc).ok();
857 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 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 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 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 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 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
1027fn 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
1080fn 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
1086fn 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
1093fn is_in_source_range(element: &SourceElement, location: &SourceLocation) -> bool {
1095 let source_ids_match = element.index_i32() == location.source_id as i32;
1097 if !source_ids_match {
1098 return false;
1099 }
1100
1101 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 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 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 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 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 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 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 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 (&solc[..], "10:20:0;;;;;;;;;", [(5, None), (7, Some(4))]),
1290 (&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 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 (&body_is_taken[..], "10:20:0;;;50:5:0;-1:-1:-1;22:5:0;", [(6, Some(4)), (5, None)]),
1334 (&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 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 ("12:5:0;25:2:0;12:5:0;50:5:0;;50:5:0;", [(7, Some(4)), (5, None)]),
1367 ("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 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 ("12:5:0;;;25:2:0;;;26:3:0;;50:5:0;", [(5, None), (12, Some(4))]),
1403 ("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 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 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 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 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 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 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 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 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 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 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 let false_falls_through = [(5, None), (8, Some(4))];
1609 let true_falls_through = [(8, Some(4)), (5, None)];
1610 for (source_map, expected) in [
1614 ("12:3:0;;10:40:0;36:3:0;;0:100:0;-1:-1:-1;22:3:0;;", false_falls_through),
1616 ("12:3:0;;10:40:0;22:3:0;;0:100:0;-1:-1:-1;36:3:0;;", true_falls_through),
1618 ("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 ("12:3:0;;10:40:0;0:100:0;;0:100:0;-1:-1:-1;22:3:0;;", false_falls_through),
1623 ("12:3:0;;10:40:0;22:3:0;;0:100:0;-1:-1:-1;0:100:0;;", true_falls_through),
1625 ("12:3:0;;10:40:0;0:100:0;;0:100:0;-1:-1:-1;36:3:0;;", true_falls_through),
1627 ("12:3:0;;10:40:0;36:3:0;;0:100:0;-1:-1:-1;0:100:0;;", false_falls_through),
1629 ("12:3:0;;10:40:0;0:100:0;;0:100:0;-1:-1:-1;0:100:0;;", false_falls_through),
1631 ("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 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 (
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 (
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 (
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 (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 for (bytecode, source_map, expected) in [
1941 (
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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 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 ("15:5:0;;;10:20:0;;0:100:0;", 3),
2180 ("15:5:0;;;10:5:0;;0:100:0;", 0),
2182 ("15:5:0;;;10:20:0;;12:3:0;", 0),
2184 ("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 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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 (
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 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 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 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 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 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 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 let taken = [(8, Some(4))];
2530 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 (&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 (&after_then_exit[..], "12:3:0;;10:61:0;80:5:0;;;0:100:0;;", &taken),
2540 (&after_then_exit[..], "12:3:0;;10:60:0;80:5:0;;;5:3:0;;", &taken),
2542 (&after_then_exit[..], "12:3:0;45:5:0;10:60:0;80:5:0;;;85:5:0;;", &taken),
2544 (&after_then_exit[..], "12:3:0;;10:60:0;80:5:0;;;85:5:0;;", &[]),
2546 (&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 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 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 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 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 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 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 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 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 assert!(anchors("12:3:0;;10:60:0;105:3:0;;;105:3:0;;;", true, false).is_empty());
2634 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 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 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 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 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 assert_eq!(entered(&[opcode::PUSH1, 5, opcode::POP]), (1, None));
2708
2709 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 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}