diff options
Diffstat (limited to 'compiler/rustc_mir_transform/src')
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/counters.rs | 5 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/graph.rs | 89 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/spans.rs | 244 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs | 192 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/coverage/tests.rs | 106 |
5 files changed, 278 insertions, 358 deletions
diff --git a/compiler/rustc_mir_transform/src/coverage/counters.rs b/compiler/rustc_mir_transform/src/coverage/counters.rs index b5968517d77..a8b0f4a8d6d 100644 --- a/compiler/rustc_mir_transform/src/coverage/counters.rs +++ b/compiler/rustc_mir_transform/src/coverage/counters.rs @@ -168,11 +168,6 @@ impl CoverageCounters { self.counter_increment_sites.len() } - #[cfg(test)] - pub(super) fn num_expressions(&self) -> usize { - self.expressions.len() - } - fn set_bcb_counter(&mut self, bcb: BasicCoverageBlock, counter_kind: BcbCounter) -> BcbCounter { if let Some(replaced) = self.bcb_counters[bcb].replace(counter_kind) { bug!( diff --git a/compiler/rustc_mir_transform/src/coverage/graph.rs b/compiler/rustc_mir_transform/src/coverage/graph.rs index fd74a2a97e2..360dccb240d 100644 --- a/compiler/rustc_mir_transform/src/coverage/graph.rs +++ b/compiler/rustc_mir_transform/src/coverage/graph.rs @@ -14,16 +14,16 @@ use std::ops::{Index, IndexMut}; /// A coverage-specific simplification of the MIR control flow graph (CFG). The `CoverageGraph`s /// nodes are `BasicCoverageBlock`s, which encompass one or more MIR `BasicBlock`s. #[derive(Debug)] -pub(super) struct CoverageGraph { +pub(crate) struct CoverageGraph { bcbs: IndexVec<BasicCoverageBlock, BasicCoverageBlockData>, bb_to_bcb: IndexVec<BasicBlock, Option<BasicCoverageBlock>>, - pub successors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, - pub predecessors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, + pub(crate) successors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, + pub(crate) predecessors: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, dominators: Option<Dominators<BasicCoverageBlock>>, } impl CoverageGraph { - pub fn from_mir(mir_body: &mir::Body<'_>) -> Self { + pub(crate) fn from_mir(mir_body: &mir::Body<'_>) -> Self { let (bcbs, bb_to_bcb) = Self::compute_basic_coverage_blocks(mir_body); // Pre-transform MIR `BasicBlock` successors and predecessors into the BasicCoverageBlock @@ -135,24 +135,28 @@ impl CoverageGraph { } #[inline(always)] - pub fn iter_enumerated( + pub(crate) fn iter_enumerated( &self, ) -> impl Iterator<Item = (BasicCoverageBlock, &BasicCoverageBlockData)> { self.bcbs.iter_enumerated() } #[inline(always)] - pub fn bcb_from_bb(&self, bb: BasicBlock) -> Option<BasicCoverageBlock> { + pub(crate) fn bcb_from_bb(&self, bb: BasicBlock) -> Option<BasicCoverageBlock> { if bb.index() < self.bb_to_bcb.len() { self.bb_to_bcb[bb] } else { None } } #[inline(always)] - pub fn dominates(&self, dom: BasicCoverageBlock, node: BasicCoverageBlock) -> bool { + pub(crate) fn dominates(&self, dom: BasicCoverageBlock, node: BasicCoverageBlock) -> bool { self.dominators.as_ref().unwrap().dominates(dom, node) } #[inline(always)] - pub fn cmp_in_dominator_order(&self, a: BasicCoverageBlock, b: BasicCoverageBlock) -> Ordering { + pub(crate) fn cmp_in_dominator_order( + &self, + a: BasicCoverageBlock, + b: BasicCoverageBlock, + ) -> Ordering { self.dominators.as_ref().unwrap().cmp_in_dominator_order(a, b) } @@ -166,7 +170,7 @@ impl CoverageGraph { /// /// FIXME: That assumption might not be true for [`TerminatorKind::Yield`]? #[inline(always)] - pub(super) fn bcb_has_multiple_in_edges(&self, bcb: BasicCoverageBlock) -> bool { + pub(crate) fn bcb_has_multiple_in_edges(&self, bcb: BasicCoverageBlock) -> bool { // Even though bcb0 conceptually has an extra virtual in-edge due to // being the entry point, we've already asserted that it has no _other_ // in-edges, so there's no possibility of it having _multiple_ in-edges. @@ -212,7 +216,7 @@ impl graph::StartNode for CoverageGraph { impl graph::Successors for CoverageGraph { #[inline] fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> { - self.successors[node].iter().cloned() + self.successors[node].iter().copied() } } @@ -227,7 +231,7 @@ rustc_index::newtype_index! { /// A node in the control-flow graph of CoverageGraph. #[orderable] #[debug_format = "bcb{}"] - pub(super) struct BasicCoverageBlock { + pub(crate) struct BasicCoverageBlock { const START_BCB = 0; } } @@ -259,23 +263,23 @@ rustc_index::newtype_index! { /// queries (`dominates()`, `predecessors`, `successors`, etc.) have branch (control flow) /// significance. #[derive(Debug, Clone)] -pub(super) struct BasicCoverageBlockData { - pub basic_blocks: Vec<BasicBlock>, +pub(crate) struct BasicCoverageBlockData { + pub(crate) basic_blocks: Vec<BasicBlock>, } impl BasicCoverageBlockData { - pub fn from(basic_blocks: Vec<BasicBlock>) -> Self { + fn from(basic_blocks: Vec<BasicBlock>) -> Self { assert!(basic_blocks.len() > 0); Self { basic_blocks } } #[inline(always)] - pub fn leader_bb(&self) -> BasicBlock { + pub(crate) fn leader_bb(&self) -> BasicBlock { self.basic_blocks[0] } #[inline(always)] - pub fn last_bb(&self) -> BasicBlock { + pub(crate) fn last_bb(&self) -> BasicBlock { *self.basic_blocks.last().unwrap() } } @@ -364,7 +368,7 @@ fn bcb_filtered_successors<'a, 'tcx>(terminator: &'a Terminator<'tcx>) -> Covera /// CoverageGraph outside all loops. This supports traversing the BCB CFG in a way that /// ensures a loop is completely traversed before processing Blocks after the end of the loop. #[derive(Debug)] -pub(super) struct TraversalContext { +struct TraversalContext { /// BCB with one or more incoming loop backedges, indicating which loop /// this context is for. /// @@ -375,7 +379,7 @@ pub(super) struct TraversalContext { worklist: VecDeque<BasicCoverageBlock>, } -pub(super) struct TraverseCoverageGraphWithLoops<'a> { +pub(crate) struct TraverseCoverageGraphWithLoops<'a> { basic_coverage_blocks: &'a CoverageGraph, backedges: IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>>, @@ -384,7 +388,7 @@ pub(super) struct TraverseCoverageGraphWithLoops<'a> { } impl<'a> TraverseCoverageGraphWithLoops<'a> { - pub(super) fn new(basic_coverage_blocks: &'a CoverageGraph) -> Self { + pub(crate) fn new(basic_coverage_blocks: &'a CoverageGraph) -> Self { let backedges = find_loop_backedges(basic_coverage_blocks); let worklist = VecDeque::from([basic_coverage_blocks.start_node()]); @@ -400,7 +404,7 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { /// For each loop on the loop context stack (top-down), yields a list of BCBs /// within that loop that have an outgoing edge back to the loop header. - pub(super) fn reloop_bcbs_per_loop(&self) -> impl Iterator<Item = &[BasicCoverageBlock]> { + pub(crate) fn reloop_bcbs_per_loop(&self) -> impl Iterator<Item = &[BasicCoverageBlock]> { self.context_stack .iter() .rev() @@ -408,39 +412,38 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { .map(|header_bcb| self.backedges[header_bcb].as_slice()) } - pub(super) fn next(&mut self) -> Option<BasicCoverageBlock> { + pub(crate) fn next(&mut self) -> Option<BasicCoverageBlock> { debug!( "TraverseCoverageGraphWithLoops::next - context_stack: {:?}", self.context_stack.iter().rev().collect::<Vec<_>>() ); while let Some(context) = self.context_stack.last_mut() { - if let Some(bcb) = context.worklist.pop_front() { - if !self.visited.insert(bcb) { - debug!("Already visited: {bcb:?}"); - continue; - } - debug!("Visiting {bcb:?}"); - - if self.backedges[bcb].len() > 0 { - debug!("{bcb:?} is a loop header! Start a new TraversalContext..."); - self.context_stack.push(TraversalContext { - loop_header: Some(bcb), - worklist: VecDeque::new(), - }); - } - self.add_successors_to_worklists(bcb); - return Some(bcb); - } else { - // Strip contexts with empty worklists from the top of the stack + let Some(bcb) = context.worklist.pop_front() else { + // This stack level is exhausted; pop it and try the next one. self.context_stack.pop(); + continue; + }; + + if !self.visited.insert(bcb) { + debug!("Already visited: {bcb:?}"); + continue; + } + debug!("Visiting {bcb:?}"); + + if self.backedges[bcb].len() > 0 { + debug!("{bcb:?} is a loop header! Start a new TraversalContext..."); + self.context_stack + .push(TraversalContext { loop_header: Some(bcb), worklist: VecDeque::new() }); } + self.add_successors_to_worklists(bcb); + return Some(bcb); } None } - pub fn add_successors_to_worklists(&mut self, bcb: BasicCoverageBlock) { + fn add_successors_to_worklists(&mut self, bcb: BasicCoverageBlock) { let successors = &self.basic_coverage_blocks.successors[bcb]; debug!("{:?} has {} successors:", bcb, successors.len()); @@ -494,11 +497,11 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { } } - pub fn is_complete(&self) -> bool { + pub(crate) fn is_complete(&self) -> bool { self.visited.count() == self.visited.domain_size() } - pub fn unvisited(&self) -> Vec<BasicCoverageBlock> { + pub(crate) fn unvisited(&self) -> Vec<BasicCoverageBlock> { let mut unvisited_set: BitSet<BasicCoverageBlock> = BitSet::new_filled(self.visited.domain_size()); unvisited_set.subtract(&self.visited); @@ -506,7 +509,7 @@ impl<'a> TraverseCoverageGraphWithLoops<'a> { } } -pub(super) fn find_loop_backedges( +fn find_loop_backedges( basic_coverage_blocks: &CoverageGraph, ) -> IndexVec<BasicCoverageBlock, Vec<BasicCoverageBlock>> { let num_bcbs = basic_coverage_blocks.num_nodes(); diff --git a/compiler/rustc_mir_transform/src/coverage/spans.rs b/compiler/rustc_mir_transform/src/coverage/spans.rs index bb6a666ff73..84a70d1f02d 100644 --- a/compiler/rustc_mir_transform/src/coverage/spans.rs +++ b/compiler/rustc_mir_transform/src/coverage/spans.rs @@ -1,9 +1,15 @@ +use std::collections::VecDeque; + +use rustc_data_structures::captures::Captures; +use rustc_data_structures::fx::FxHashSet; use rustc_middle::mir; use rustc_span::Span; use crate::coverage::graph::{BasicCoverageBlock, CoverageGraph}; use crate::coverage::mappings; -use crate::coverage::spans::from_mir::SpanFromMir; +use crate::coverage::spans::from_mir::{ + extract_covspans_and_holes_from_mir, ExtractedCovspans, Hole, SpanFromMir, +}; use crate::coverage::ExtractedHirInfo; mod from_mir; @@ -19,50 +25,181 @@ pub(super) fn extract_refined_covspans( basic_coverage_blocks: &CoverageGraph, code_mappings: &mut impl Extend<mappings::CodeMapping>, ) { - let sorted_span_buckets = - from_mir::mir_to_initial_sorted_coverage_spans(mir_body, hir_info, basic_coverage_blocks); - for bucket in sorted_span_buckets { - let refined_spans = refine_sorted_spans(bucket); - code_mappings.extend(refined_spans.into_iter().map(|RefinedCovspan { span, bcb }| { + let ExtractedCovspans { mut covspans, mut holes } = + extract_covspans_and_holes_from_mir(mir_body, hir_info, basic_coverage_blocks); + + // First, perform the passes that need macro information. + covspans.sort_by(|a, b| basic_coverage_blocks.cmp_in_dominator_order(a.bcb, b.bcb)); + remove_unwanted_macro_spans(&mut covspans); + split_visible_macro_spans(&mut covspans); + + // We no longer need the extra information in `SpanFromMir`, so convert to `Covspan`. + let mut covspans = covspans.into_iter().map(SpanFromMir::into_covspan).collect::<Vec<_>>(); + + let compare_covspans = |a: &Covspan, b: &Covspan| { + compare_spans(a.span, b.span) + // After deduplication, we want to keep only the most-dominated BCB. + .then_with(|| basic_coverage_blocks.cmp_in_dominator_order(a.bcb, b.bcb).reverse()) + }; + covspans.sort_by(compare_covspans); + + // Among covspans with the same span, keep only one, + // preferring the one with the most-dominated BCB. + // (Ideally we should try to preserve _all_ non-dominating BCBs, but that + // requires a lot more complexity in the span refiner, for little benefit.) + covspans.dedup_by(|b, a| a.span.source_equal(b.span)); + + // Sort the holes, and merge overlapping/adjacent holes. + 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 mut covspans in buckets { + // Make sure each individual bucket is internally sorted. + covspans.sort_by(compare_covspans); + let _span = debug_span!("processing bucket", ?covspans).entered(); + + let mut covspans = remove_unwanted_overlapping_spans(covspans); + debug!(?covspans, "after removing overlaps"); + + // 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 } })); } } -#[derive(Debug)] -struct RefinedCovspan { - span: Span, - bcb: BasicCoverageBlock, +/// Macros that expand into branches (e.g. `assert!`, `trace!`) tend to generate +/// multiple condition/consequent blocks that have the span of the whole macro +/// invocation, which is unhelpful. Keeping only the first such span seems to +/// give better mappings, so remove the others. +/// +/// (The input spans should be sorted in BCB dominator order, so that the +/// retained "first" span is likely to dominate the others.) +fn remove_unwanted_macro_spans(covspans: &mut Vec<SpanFromMir>) { + let mut seen_macro_spans = FxHashSet::default(); + covspans.retain(|covspan| { + // Ignore (retain) non-macro-expansion spans. + if covspan.visible_macro.is_none() { + return true; + } + + // Retain only the first macro-expanded covspan with this span. + seen_macro_spans.insert(covspan.span) + }); } -impl RefinedCovspan { - fn is_mergeable(&self, other: &Self) -> bool { - self.bcb == other.bcb - } +/// When a span corresponds to a macro invocation that is visible from the +/// function body, split it into two parts. The first part covers just the +/// macro name plus `!`, and the second part covers the rest of the macro +/// invocation. This seems to give better results for code that uses macros. +fn split_visible_macro_spans(covspans: &mut Vec<SpanFromMir>) { + let mut extra_spans = vec![]; - fn merge_from(&mut self, other: &Self) { - debug_assert!(self.is_mergeable(other)); - self.span = self.span.to(other.span); + covspans.retain(|covspan| { + let Some(visible_macro) = covspan.visible_macro else { return true }; + + let split_len = visible_macro.as_str().len() as u32 + 1; + let (before, after) = covspan.span.split_at(split_len); + if !covspan.span.contains(before) || !covspan.span.contains(after) { + // Something is unexpectedly wrong with the split point. + // The debug assertion in `split_at` will have already caught this, + // but in release builds it's safer to do nothing and maybe get a + // bug report for unexpected coverage, rather than risk an ICE. + return true; + } + + extra_spans.push(SpanFromMir::new(before, covspan.visible_macro, covspan.bcb)); + extra_spans.push(SpanFromMir::new(after, covspan.visible_macro, covspan.bcb)); + false // Discard the original covspan that we just split. + }); + + // The newly-split spans are added at the end, so any previous sorting + // is not preserved. + covspans.extend(extra_spans); +} + +/// Uses the holes to divide the given covspans into buckets, such that: +/// - No span in any hole overlaps a bucket (truncating the spans if necessary). +/// - The spans in each bucket are strictly after all spans in previous buckets, +/// and strictly before all spans in subsequent buckets. +/// +/// The resulting buckets are sorted relative to each other, but might not be +/// internally sorted. +#[instrument(level = "debug")] +fn divide_spans_into_buckets(input_covspans: Vec<Covspan>, holes: &[Hole]) -> Vec<Vec<Covspan>> { + debug_assert!(input_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())); + + // Now we're ready to start carving holes out of the initial coverage spans, + // and grouping them in buckets separated by the holes. + + let mut input_covspans = VecDeque::from(input_covspans); + let mut fragments = vec![]; + + // For each hole: + // - Identify the spans that are entirely or partly before the hole. + // - Put those spans in a corresponding bucket, truncated to the start of the hole. + // - If one of those spans also extends after the hole, put the rest of it + // in a "fragments" vector that is processed by the next hole. + let mut buckets = (0..holes.len()).map(|_| vec![]).collect::<Vec<_>>(); + for (hole, bucket) in holes.iter().zip(&mut buckets) { + let fragments_from_prev = std::mem::take(&mut fragments); + + // Only inspect spans that precede or overlap this hole, + // leaving the rest to be inspected by later holes. + // (This relies on the spans and holes both being sorted.) + let relevant_input_covspans = + drain_front_while(&mut input_covspans, |c| c.span.lo() < hole.span.hi()); + + for covspan in fragments_from_prev.into_iter().chain(relevant_input_covspans) { + let (before, after) = covspan.split_around_hole_span(hole.span); + bucket.extend(before); + fragments.extend(after); + } } + + // After finding the spans before each hole, any remaining fragments/spans + // form their own final bucket, after the final hole. + // (If there were no holes, this will just be all of the initial spans.) + fragments.extend(input_covspans); + buckets.push(fragments); + + buckets +} + +/// 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<T>, + mut pred_fn: impl FnMut(&T) -> bool, +) -> impl Iterator<Item = T> + Captures<'a> { + std::iter::from_fn(move || if pred_fn(queue.front()?) { queue.pop_front() } else { None }) } /// Takes one of the buckets of (sorted) spans extracted from MIR, and "refines" -/// those spans by removing spans that overlap in unwanted ways, and by merging -/// compatible adjacent spans. +/// those spans by removing spans that overlap in unwanted ways. #[instrument(level = "debug")] -fn refine_sorted_spans(sorted_spans: Vec<SpanFromMir>) -> Vec<RefinedCovspan> { +fn remove_unwanted_overlapping_spans(sorted_spans: Vec<Covspan>) -> Vec<Covspan> { + debug_assert!(sorted_spans.is_sorted_by(|a, b| compare_spans(a.span, b.span).is_le())); + // Holds spans that have been read from the input vector, but haven't yet // been committed to the output vector. let mut pending = vec![]; let mut refined = vec![]; for curr in sorted_spans { - pending.retain(|prev: &SpanFromMir| { + pending.retain(|prev: &Covspan| { if prev.span.hi() <= curr.span.lo() { // There's no overlap between the previous/current covspans, // so move the previous one into the refined list. - refined.push(RefinedCovspan { span: prev.span, bcb: prev.bcb }); + refined.push(prev.clone()); false } else { // Otherwise, retain the previous covspan only if it has the @@ -75,22 +212,57 @@ fn refine_sorted_spans(sorted_spans: Vec<SpanFromMir>) -> Vec<RefinedCovspan> { } // Drain the rest of the pending list into the refined list. - for prev in pending { - refined.push(RefinedCovspan { span: prev.span, bcb: prev.bcb }); + refined.extend(pending); + refined +} + +#[derive(Clone, Debug)] +struct Covspan { + span: Span, + bcb: BasicCoverageBlock, +} + +impl Covspan { + /// Splits this covspan into 0-2 parts: + /// - The part that is strictly before the hole span, if any. + /// - The part that is strictly after the hole span, if any. + fn split_around_hole_span(&self, hole_span: Span) -> (Option<Self>, Option<Self>) { + let before = try { + let span = self.span.trim_end(hole_span)?; + Self { span, ..*self } + }; + let after = try { + let span = self.span.trim_start(hole_span)?; + Self { span, ..*self } + }; + + (before, after) } - // Do one last merge pass, to simplify the output. - debug!(?refined, "before merge"); - refined.dedup_by(|b, a| { - if a.is_mergeable(b) { - debug!(?a, ?b, "merging list-adjacent refined spans"); - a.merge_from(b); - true - } else { - false + /// If `self` and `other` can be merged (i.e. they have the same BCB), + /// mutates `self.span` to also include `other.span` and returns true. + /// + /// Note that compatible covspans can be merged even if their underlying + /// spans are not overlapping/adjacent; any space between them will also be + /// part of the merged covspan. + fn merge_if_eligible(&mut self, other: &Self) -> bool { + if self.bcb != other.bcb { + return false; } - }); - debug!(?refined, "after merge"); - refined + self.span = self.span.to(other.span); + true + } +} + +/// Compares two spans in (lo ascending, hi descending) order. +fn compare_spans(a: Span, b: Span) -> std::cmp::Ordering { + // First sort by span start. + Ord::cmp(&a.lo(), &b.lo()) + // If span starts are the same, sort by span end in reverse order. + // This ensures that if spans A and B are adjacent in the list, + // and they overlap but are not equal, then either: + // - Span A extends further left, or + // - Both have the same start and span A extends further right + .then_with(|| Ord::cmp(&a.hi(), &b.hi()).reverse()) } diff --git a/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs b/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs index b1f71035dde..09deb7534bf 100644 --- a/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs +++ b/compiler/rustc_mir_transform/src/coverage/spans/from_mir.rs @@ -1,7 +1,3 @@ -use std::collections::VecDeque; - -use rustc_data_structures::captures::Captures; -use rustc_data_structures::fx::FxHashSet; use rustc_middle::bug; use rustc_middle::mir::coverage::CoverageKind; use rustc_middle::mir::{ @@ -13,25 +9,25 @@ use rustc_span::{ExpnKind, MacroKind, Span, Symbol}; use crate::coverage::graph::{ BasicCoverageBlock, BasicCoverageBlockData, CoverageGraph, START_BCB, }; +use crate::coverage::spans::Covspan; use crate::coverage::ExtractedHirInfo; +pub(crate) struct ExtractedCovspans { + pub(crate) covspans: Vec<SpanFromMir>, + pub(crate) holes: Vec<Hole>, +} + /// Traverses the MIR body to produce an initial collection of coverage-relevant /// spans, each associated with a node in the coverage graph (BCB) and possibly /// other metadata. -/// -/// The returned spans are divided into one or more buckets, such that: -/// - The spans in each bucket are strictly after all spans in previous buckets, -/// and strictly before all spans in subsequent buckets. -/// - The contents of each bucket are also sorted, in a specific order that is -/// expected by the subsequent span-refinement step. -pub(super) fn mir_to_initial_sorted_coverage_spans( +pub(crate) fn extract_covspans_and_holes_from_mir( mir_body: &mir::Body<'_>, hir_info: &ExtractedHirInfo, basic_coverage_blocks: &CoverageGraph, -) -> Vec<Vec<SpanFromMir>> { +) -> ExtractedCovspans { let &ExtractedHirInfo { body_span, .. } = hir_info; - let mut initial_spans = vec![]; + let mut covspans = vec![]; let mut holes = vec![]; for (bcb, bcb_data) in basic_coverage_blocks.iter_enumerated() { @@ -40,150 +36,21 @@ pub(super) fn mir_to_initial_sorted_coverage_spans( body_span, bcb, bcb_data, - &mut initial_spans, + &mut covspans, &mut holes, ); } // Only add the signature span if we found at least one span in the body. - if !initial_spans.is_empty() || !holes.is_empty() { + if !covspans.is_empty() || !holes.is_empty() { // If there is no usable signature span, add a fake one (before refinement) // to avoid an ugly gap between the body start and the first real span. // FIXME: Find a more principled way to solve this problem. let fn_sig_span = hir_info.fn_sig_span_extended.unwrap_or_else(|| body_span.shrink_to_lo()); - initial_spans.push(SpanFromMir::for_fn_sig(fn_sig_span)); - } - - initial_spans.sort_by(|a, b| basic_coverage_blocks.cmp_in_dominator_order(a.bcb, b.bcb)); - remove_unwanted_macro_spans(&mut initial_spans); - split_visible_macro_spans(&mut initial_spans); - - let compare_covspans = |a: &SpanFromMir, b: &SpanFromMir| { - compare_spans(a.span, b.span) - // After deduplication, we want to keep only the most-dominated BCB. - .then_with(|| basic_coverage_blocks.cmp_in_dominator_order(a.bcb, b.bcb).reverse()) - }; - initial_spans.sort_by(compare_covspans); - - // Among covspans with the same span, keep only one, - // preferring the one with the most-dominated BCB. - // (Ideally we should try to preserve _all_ non-dominating BCBs, but that - // requires a lot more complexity in the span refiner, for little benefit.) - initial_spans.dedup_by(|b, a| a.span.source_equal(b.span)); - - // Sort the holes, and merge overlapping/adjacent holes. - holes.sort_by(|a, b| compare_spans(a.span, b.span)); - holes.dedup_by(|b, a| a.merge_if_overlapping_or_adjacent(b)); - - // Now we're ready to start carving holes out of the initial coverage spans, - // and grouping them in buckets separated by the holes. - - let mut initial_spans = VecDeque::from(initial_spans); - let mut fragments: Vec<SpanFromMir> = vec![]; - - // For each hole: - // - Identify the spans that are entirely or partly before the hole. - // - Put those spans in a corresponding bucket, truncated to the start of the hole. - // - If one of those spans also extends after the hole, put the rest of it - // in a "fragments" vector that is processed by the next hole. - let mut buckets = (0..holes.len()).map(|_| vec![]).collect::<Vec<_>>(); - for (hole, bucket) in holes.iter().zip(&mut buckets) { - let fragments_from_prev = std::mem::take(&mut fragments); - - // Only inspect spans that precede or overlap this hole, - // leaving the rest to be inspected by later holes. - // (This relies on the spans and holes both being sorted.) - let relevant_initial_spans = - drain_front_while(&mut initial_spans, |c| c.span.lo() < hole.span.hi()); - - for covspan in fragments_from_prev.into_iter().chain(relevant_initial_spans) { - let (before, after) = covspan.split_around_hole_span(hole.span); - bucket.extend(before); - fragments.extend(after); - } + covspans.push(SpanFromMir::for_fn_sig(fn_sig_span)); } - // After finding the spans before each hole, any remaining fragments/spans - // form their own final bucket, after the final hole. - // (If there were no holes, this will just be all of the initial spans.) - fragments.extend(initial_spans); - buckets.push(fragments); - - // Make sure each individual bucket is still internally sorted. - for bucket in &mut buckets { - bucket.sort_by(compare_covspans); - } - buckets -} - -fn compare_spans(a: Span, b: Span) -> std::cmp::Ordering { - // First sort by span start. - Ord::cmp(&a.lo(), &b.lo()) - // If span starts are the same, sort by span end in reverse order. - // This ensures that if spans A and B are adjacent in the list, - // and they overlap but are not equal, then either: - // - Span A extends further left, or - // - Both have the same start and span A extends further right - .then_with(|| Ord::cmp(&a.hi(), &b.hi()).reverse()) -} - -/// 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<T>, - mut pred_fn: impl FnMut(&T) -> bool, -) -> impl Iterator<Item = T> + Captures<'a> { - std::iter::from_fn(move || if pred_fn(queue.front()?) { queue.pop_front() } else { None }) -} - -/// Macros that expand into branches (e.g. `assert!`, `trace!`) tend to generate -/// multiple condition/consequent blocks that have the span of the whole macro -/// invocation, which is unhelpful. Keeping only the first such span seems to -/// give better mappings, so remove the others. -/// -/// (The input spans should be sorted in BCB dominator order, so that the -/// retained "first" span is likely to dominate the others.) -fn remove_unwanted_macro_spans(initial_spans: &mut Vec<SpanFromMir>) { - let mut seen_macro_spans = FxHashSet::default(); - initial_spans.retain(|covspan| { - // Ignore (retain) non-macro-expansion spans. - if covspan.visible_macro.is_none() { - return true; - } - - // Retain only the first macro-expanded covspan with this span. - seen_macro_spans.insert(covspan.span) - }); -} - -/// When a span corresponds to a macro invocation that is visible from the -/// function body, split it into two parts. The first part covers just the -/// macro name plus `!`, and the second part covers the rest of the macro -/// invocation. This seems to give better results for code that uses macros. -fn split_visible_macro_spans(initial_spans: &mut Vec<SpanFromMir>) { - let mut extra_spans = vec![]; - - initial_spans.retain(|covspan| { - let Some(visible_macro) = covspan.visible_macro else { return true }; - - let split_len = visible_macro.as_str().len() as u32 + 1; - let (before, after) = covspan.span.split_at(split_len); - if !covspan.span.contains(before) || !covspan.span.contains(after) { - // Something is unexpectedly wrong with the split point. - // The debug assertion in `split_at` will have already caught this, - // but in release builds it's safer to do nothing and maybe get a - // bug report for unexpected coverage, rather than risk an ICE. - return true; - } - - extra_spans.push(SpanFromMir::new(before, covspan.visible_macro, covspan.bcb)); - extra_spans.push(SpanFromMir::new(after, covspan.visible_macro, covspan.bcb)); - false // Discard the original covspan that we just split. - }); - - // The newly-split spans are added at the end, so any previous sorting - // is not preserved. - initial_spans.extend(extra_spans); + ExtractedCovspans { covspans, holes } } // Generate a set of coverage spans from the filtered set of `Statement`s and `Terminator`s of @@ -402,12 +269,12 @@ fn unexpand_into_body_span_with_prev( } #[derive(Debug)] -struct Hole { - span: Span, +pub(crate) struct Hole { + pub(crate) span: Span, } impl Hole { - fn merge_if_overlapping_or_adjacent(&mut self, other: &mut Self) -> bool { + pub(crate) fn merge_if_overlapping_or_adjacent(&mut self, other: &mut Self) -> bool { if !self.span.overlaps_or_adjacent(other.span) { return false; } @@ -418,7 +285,7 @@ impl Hole { } #[derive(Debug)] -pub(super) struct SpanFromMir { +pub(crate) struct SpanFromMir { /// A span that has been extracted from MIR and then "un-expanded" back to /// within the current function's `body_span`. After various intermediate /// processing steps, this span is emitted as part of the final coverage @@ -426,9 +293,9 @@ pub(super) struct SpanFromMir { /// /// With the exception of `fn_sig_span`, this should always be contained /// within `body_span`. - pub(super) span: Span, - visible_macro: Option<Symbol>, - pub(super) bcb: BasicCoverageBlock, + pub(crate) span: Span, + pub(crate) visible_macro: Option<Symbol>, + pub(crate) bcb: BasicCoverageBlock, } impl SpanFromMir { @@ -436,23 +303,12 @@ impl SpanFromMir { Self::new(fn_sig_span, None, START_BCB) } - fn new(span: Span, visible_macro: Option<Symbol>, bcb: BasicCoverageBlock) -> Self { + pub(crate) fn new(span: Span, visible_macro: Option<Symbol>, bcb: BasicCoverageBlock) -> Self { Self { span, visible_macro, bcb } } - /// Splits this span into 0-2 parts: - /// - The part that is strictly before the hole span, if any. - /// - The part that is strictly after the hole span, if any. - fn split_around_hole_span(&self, hole_span: Span) -> (Option<Self>, Option<Self>) { - let before = try { - let span = self.span.trim_end(hole_span)?; - Self { span, ..*self } - }; - let after = try { - let span = self.span.trim_start(hole_span)?; - Self { span, ..*self } - }; - - (before, after) + pub(crate) fn into_covspan(self) -> Covspan { + let Self { span, visible_macro: _, bcb } = self; + Covspan { span, bcb } } } diff --git a/compiler/rustc_mir_transform/src/coverage/tests.rs b/compiler/rustc_mir_transform/src/coverage/tests.rs index ca64688e6b8..048547dc9f5 100644 --- a/compiler/rustc_mir_transform/src/coverage/tests.rs +++ b/compiler/rustc_mir_transform/src/coverage/tests.rs @@ -24,7 +24,6 @@ //! globals is comparatively simpler. The easiest way is to wrap the test in a closure argument //! to: `rustc_span::create_default_session_globals_then(|| { test_here(); })`. -use super::counters; use super::graph::{self, BasicCoverageBlock}; use itertools::Itertools; @@ -551,108 +550,3 @@ fn test_covgraph_switchint_loop_then_inner_loop_else_break() { assert_successors(&basic_coverage_blocks, bcb(5), &[bcb(1)]); assert_successors(&basic_coverage_blocks, bcb(6), &[bcb(4)]); } - -#[test] -fn test_find_loop_backedges_none() { - let mir_body = goto_switchint(); - let basic_coverage_blocks = graph::CoverageGraph::from_mir(&mir_body); - if false { - eprintln!( - "basic_coverage_blocks = {:?}", - basic_coverage_blocks.iter_enumerated().collect::<Vec<_>>() - ); - eprintln!("successors = {:?}", basic_coverage_blocks.successors); - } - let backedges = graph::find_loop_backedges(&basic_coverage_blocks); - assert_eq!( - backedges.iter_enumerated().map(|(_bcb, backedges)| backedges.len()).sum::<usize>(), - 0, - "backedges: {:?}", - backedges - ); -} - -#[test] -fn test_find_loop_backedges_one() { - let mir_body = switchint_then_loop_else_return(); - let basic_coverage_blocks = graph::CoverageGraph::from_mir(&mir_body); - let backedges = graph::find_loop_backedges(&basic_coverage_blocks); - assert_eq!( - backedges.iter_enumerated().map(|(_bcb, backedges)| backedges.len()).sum::<usize>(), - 1, - "backedges: {:?}", - backedges - ); - - assert_eq!(backedges[bcb(1)], &[bcb(3)]); -} - -#[test] -fn test_find_loop_backedges_two() { - let mir_body = switchint_loop_then_inner_loop_else_break(); - let basic_coverage_blocks = graph::CoverageGraph::from_mir(&mir_body); - let backedges = graph::find_loop_backedges(&basic_coverage_blocks); - assert_eq!( - backedges.iter_enumerated().map(|(_bcb, backedges)| backedges.len()).sum::<usize>(), - 2, - "backedges: {:?}", - backedges - ); - - assert_eq!(backedges[bcb(1)], &[bcb(5)]); - assert_eq!(backedges[bcb(4)], &[bcb(6)]); -} - -#[test] -fn test_traverse_coverage_with_loops() { - let mir_body = switchint_loop_then_inner_loop_else_break(); - let basic_coverage_blocks = graph::CoverageGraph::from_mir(&mir_body); - let mut traversed_in_order = Vec::new(); - let mut traversal = graph::TraverseCoverageGraphWithLoops::new(&basic_coverage_blocks); - while let Some(bcb) = traversal.next() { - traversed_in_order.push(bcb); - } - - // bcb0 is visited first. Then bcb1 starts the first loop, and all remaining nodes, *except* - // bcb6 are inside the first loop. - assert_eq!( - *traversed_in_order.last().expect("should have elements"), - bcb(6), - "bcb6 should not be visited until all nodes inside the first loop have been visited" - ); -} - -#[test] -fn test_make_bcb_counters() { - rustc_span::create_default_session_globals_then(|| { - let mir_body = goto_switchint(); - let basic_coverage_blocks = graph::CoverageGraph::from_mir(&mir_body); - // Historically this test would use `spans` internals to set up fake - // coverage spans for BCBs 1 and 2. Now we skip that step and just tell - // BCB counter construction that those BCBs have spans. - let bcb_has_coverage_spans = |bcb: BasicCoverageBlock| (1..=2).contains(&bcb.as_usize()); - let coverage_counters = counters::CoverageCounters::make_bcb_counters( - &basic_coverage_blocks, - bcb_has_coverage_spans, - ); - assert_eq!(coverage_counters.num_expressions(), 0); - - assert_eq!( - 0, // bcb1 has a `Counter` with id = 0 - match coverage_counters.bcb_counter(bcb(1)).expect("should have a counter") { - counters::BcbCounter::Counter { id, .. } => id, - _ => panic!("expected a Counter"), - } - .as_u32() - ); - - assert_eq!( - 1, // bcb2 has a `Counter` with id = 1 - match coverage_counters.bcb_counter(bcb(2)).expect("should have a counter") { - counters::BcbCounter::Counter { id, .. } => id, - _ => panic!("expected a Counter"), - } - .as_u32() - ); - }); -} |