From 77a7ae4e9fcbf3be3988c98015d7f52137bb237c Mon Sep 17 00:00:00 2001 From: Zalathar Date: Thu, 17 Apr 2025 17:03:08 +1000 Subject: coverage: Handle hole spans without dividing spans into buckets Because we no longer merge non-adjacent spans, there is no need to use buckets to prevent merging across hole spans. --- compiler/rustc_mir_transform/src/coverage/spans.rs | 92 ++++++++-------------- 1 file changed, 33 insertions(+), 59 deletions(-) (limited to 'compiler/rustc_mir_transform/src/coverage/spans.rs') diff --git a/compiler/rustc_mir_transform/src/coverage/spans.rs b/compiler/rustc_mir_transform/src/coverage/spans.rs index e6e7e2920ec..ec76076020e 100644 --- a/compiler/rustc_mir_transform/src/coverage/spans.rs +++ b/compiler/rustc_mir_transform/src/coverage/spans.rs @@ -1,11 +1,8 @@ -use std::collections::VecDeque; -use std::iter; - use rustc_data_structures::fx::FxHashSet; use rustc_middle::mir; use rustc_middle::ty::TyCtxt; use rustc_span::{DesugaringKind, ExpnKind, MacroKind, Span}; -use tracing::{debug, debug_span, instrument}; +use tracing::instrument; use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph}; use crate::coverage::spans::from_mir::{Hole, RawSpanFromMir, SpanFromMir}; @@ -83,24 +80,17 @@ pub(super) fn extract_refined_covspans<'tcx>( holes.sort_by(|a, b| compare_spans(a.span, b.span)); holes.dedup_by(|b, a| a.merge_if_overlapping_or_adjacent(b)); - // Split the covspans into separate buckets that don't overlap any holes. - let buckets = divide_spans_into_buckets(covspans, &holes); - - for covspans in buckets { - let _span = debug_span!("processing bucket", ?covspans).entered(); + // Discard any span that overlaps with a hole. + discard_spans_overlapping_holes(&mut covspans, &holes); - let mut covspans = remove_unwanted_overlapping_spans(covspans); - debug!(?covspans, "after removing overlaps"); + // Perform more refinement steps after holes have been dealt with. + let mut covspans = remove_unwanted_overlapping_spans(covspans); + covspans.dedup_by(|b, a| a.merge_if_eligible(b)); - // Do one last merge pass, to simplify the output. - covspans.dedup_by(|b, a| a.merge_if_eligible(b)); - debug!(?covspans, "after merge"); - - code_mappings.extend(covspans.into_iter().map(|Covspan { span, bcb }| { - // Each span produced by the refiner represents an ordinary code region. - mappings::CodeMapping { span, bcb } - })); - } + code_mappings.extend(covspans.into_iter().map(|Covspan { span, bcb }| { + // Each span produced by the refiner represents an ordinary code region. + mappings::CodeMapping { span, bcb } + })); } /// Macros that expand into branches (e.g. `assert!`, `trace!`) tend to generate @@ -142,52 +132,36 @@ fn shrink_visible_macro_spans(tcx: TyCtxt<'_>, covspans: &mut Vec) } } -/// Uses the holes to divide the given covspans into buckets, such that: -/// - No span in any hole overlaps a bucket (discarding spans if necessary). -/// - The spans in each bucket are strictly after all spans in previous buckets, -/// and strictly before all spans in subsequent buckets. +/// Discard all covspans that overlap a hole. /// -/// The lists of covspans and holes must be sorted. -/// The resulting buckets are sorted relative to each other, and each bucket's -/// contents are sorted. -#[instrument(level = "debug")] -fn divide_spans_into_buckets(input_covspans: Vec, holes: &[Hole]) -> Vec> { - debug_assert!(input_covspans.is_sorted_by(|a, b| compare_spans(a.span, b.span).is_le())); +/// The lists of covspans and holes must be sorted, and any holes that overlap +/// with each other must have already been merged. +fn discard_spans_overlapping_holes(covspans: &mut Vec, holes: &[Hole]) { + debug_assert!(covspans.is_sorted_by(|a, b| compare_spans(a.span, b.span).is_le())); debug_assert!(holes.is_sorted_by(|a, b| compare_spans(a.span, b.span).is_le())); + debug_assert!(holes.array_windows().all(|[a, b]| !a.span.overlaps_or_adjacent(b.span))); + + let mut curr_hole = 0usize; + let mut overlaps_hole = |covspan: &Covspan| -> bool { + while let Some(hole) = holes.get(curr_hole) { + // Both lists are sorted, so we can permanently skip any holes that + // end before the start of the current span. + if hole.span.hi() <= covspan.span.lo() { + curr_hole += 1; + continue; + } - // Now we're ready to start grouping spans into buckets separated by holes. - - let mut input_covspans = VecDeque::from(input_covspans); - - // For each hole: - // - Identify the spans that are entirely or partly before the hole. - // - Discard any that overlap with the hole. - // - Add the remaining identified spans to the corresponding bucket. - let mut buckets = (0..holes.len()).map(|_| vec![]).collect::>(); - for (hole, bucket) in holes.iter().zip(&mut buckets) { - bucket.extend( - drain_front_while(&mut input_covspans, |c| c.span.lo() < hole.span.hi()) - .filter(|c| !c.span.overlaps(hole.span)), - ); - } - - // Any remaining spans form their own final bucket, after the final hole. - // (If there were no holes, this will just be all of the initial spans.) - buckets.push(Vec::from(input_covspans)); + return hole.span.overlaps(covspan.span); + } - buckets -} + // No holes left, so this covspan doesn't overlap with any holes. + false + }; -/// Similar to `.drain(..)`, but stops just before it would remove an item not -/// satisfying the predicate. -fn drain_front_while<'a, T>( - queue: &'a mut VecDeque, - mut pred_fn: impl FnMut(&T) -> bool, -) -> impl Iterator { - iter::from_fn(move || queue.pop_front_if(|x| pred_fn(x))) + covspans.retain(|covspan| !overlaps_hole(covspan)); } -/// Takes one of the buckets of (sorted) spans extracted from MIR, and "refines" +/// Takes a list of sorted spans extracted from MIR, and "refines" /// those spans by removing spans that overlap in unwanted ways. #[instrument(level = "debug")] fn remove_unwanted_overlapping_spans(sorted_spans: Vec) -> Vec { -- cgit 1.4.1-3-g733a5