coverage: Instead of splitting, just discard any span that overlaps a hole

10 files changed, 63 insertions, 88 deletions

diff --git a/compiler/rustc_mir_transform/src/coverage/spans.rs b/compiler/rustc_mir_transform/src/coverage/spans.rs
index 8befe9c5d8d..b1f613432a8 100644
--- a/compiler/rustc_mir_transform/src/coverage/spans.rs
+++ b/compiler/rustc_mir_transform/src/coverage/spans.rs
@@ -1,4 +1,5 @@
 use std::collections::VecDeque;
+use std::iter;
 
 use rustc_data_structures::fx::FxHashSet;
 use rustc_middle::mir;
@@ -83,9 +84,7 @@ pub(super) fn extract_refined_covspans(
     // 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);
+    for covspans in buckets {
         let _span = debug_span!("processing bucket", ?covspans).entered();
 
         let mut covspans = remove_unwanted_overlapping_spans(covspans);
@@ -161,50 +160,37 @@ fn split_visible_macro_spans(covspans: &mut Vec<SpanFromMir>) {
 }
 
 /// 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).
+/// - 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.
 ///
-/// The resulting buckets are sorted relative to each other, but might not be
-/// internally sorted.
+/// 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<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.
+    // Now we're ready to start grouping spans into buckets separated by 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.
+    // - 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::<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);
-        }
+        bucket.extend(
+            drain_front_while(&mut input_covspans, |c| c.span.lo() < hole.span.hi())
+                .filter(|c| !c.span.overlaps(hole.span)),
+        );
     }
 
-    // After finding the spans before each hole, any remaining fragments/spans
-    // form their own final bucket, after the final hole.
+    // 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.)
-    fragments.extend(input_covspans);
-    buckets.push(fragments);
+    buckets.push(Vec::from(input_covspans));
 
     buckets
 }
@@ -215,7 +201,7 @@ fn drain_front_while<'a, T>(
     queue: &'a mut VecDeque<T>,
     mut pred_fn: impl FnMut(&T) -> bool,
 ) -> impl Iterator<Item = T> {
-    std::iter::from_fn(move || if pred_fn(queue.front()?) { queue.pop_front() } else { None })
+    iter::from_fn(move || queue.pop_front_if(|x| pred_fn(x)))
 }
 
 /// Takes one of the buckets of (sorted) spans extracted from MIR, and "refines"
@@ -258,22 +244,6 @@ struct Covspan {
 }
 
 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)
-    }
-
     /// 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.
     ///
diff --git a/compiler/rustc_mir_transform/src/lib.rs b/compiler/rustc_mir_transform/src/lib.rs
index 205d388f4fb..c372b77ad25 100644
--- a/compiler/rustc_mir_transform/src/lib.rs
+++ b/compiler/rustc_mir_transform/src/lib.rs
@@ -12,6 +12,7 @@
 #![feature(map_try_insert)]
 #![feature(never_type)]
 #![feature(try_blocks)]
+#![feature(vec_deque_pop_if)]
 #![feature(yeet_expr)]
 // tidy-alphabetical-end
 
diff --git a/tests/coverage/async_block.cov-map b/tests/coverage/async_block.cov-map
index 5eb69e668ca..d9196f446f1 100644
--- a/tests/coverage/async_block.cov-map
+++ b/tests/coverage/async_block.cov-map
@@ -1,5 +1,5 @@
 Function name: async_block::main
-Raw bytes (36): 0x[01, 01, 01, 05, 01, 06, 01, 07, 01, 00, 0b, 02, 01, 09, 00, 0a, 05, 00, 0e, 00, 13, 02, 00, 14, 01, 16, 02, 07, 0a, 02, 06, 01, 03, 01, 00, 02]
+Raw bytes (36): 0x[01, 01, 01, 05, 01, 06, 01, 07, 01, 00, 0b, 02, 01, 09, 00, 0a, 05, 00, 0e, 00, 13, 02, 01, 0d, 00, 13, 02, 07, 09, 00, 22, 01, 02, 01, 00, 02]
 Number of files: 1
 - file 0 => global file 1
 Number of expressions: 1
@@ -9,11 +9,11 @@ Number of file 0 mappings: 6
 - Code(Expression(0, Sub)) at (prev + 1, 9) to (start + 0, 10)
     = (c1 - c0)
 - Code(Counter(1)) at (prev + 0, 14) to (start + 0, 19)
-- Code(Expression(0, Sub)) at (prev + 0, 20) to (start + 1, 22)
+- Code(Expression(0, Sub)) at (prev + 1, 13) to (start + 0, 19)
     = (c1 - c0)
-- Code(Expression(0, Sub)) at (prev + 7, 10) to (start + 2, 6)
+- Code(Expression(0, Sub)) at (prev + 7, 9) to (start + 0, 34)
     = (c1 - c0)
-- Code(Counter(0)) at (prev + 3, 1) to (start + 0, 2)
+- Code(Counter(0)) at (prev + 2, 1) to (start + 0, 2)
 Highest counter ID seen: c1
 
 Function name: async_block::main::{closure#0}
diff --git a/tests/coverage/async_block.coverage b/tests/coverage/async_block.coverage
index 9e3294492cd..4e00024aebd 100644
--- a/tests/coverage/async_block.coverage
+++ b/tests/coverage/async_block.coverage
@@ -15,6 +15,6 @@
    LL|     12|            }
    LL|     16|        };
    LL|     16|        executor::block_on(future);
-   LL|     16|    }
+   LL|       |    }
    LL|      1|}
 
diff --git a/tests/coverage/async_closure.cov-map b/tests/coverage/async_closure.cov-map
index 0e1d9877830..a4ef0ceeb6d 100644
--- a/tests/coverage/async_closure.cov-map
+++ b/tests/coverage/async_closure.cov-map
@@ -30,21 +30,23 @@ Number of file 0 mappings: 2
 Highest counter ID seen: c0
 
 Function name: async_closure::main::{closure#0}
-Raw bytes (9): 0x[01, 01, 00, 01, 01, 0b, 23, 00, 24]
+Raw bytes (14): 0x[01, 01, 00, 02, 01, 0b, 22, 00, 23, 01, 00, 23, 00, 24]
 Number of files: 1
 - file 0 => global file 1
 Number of expressions: 0
-Number of file 0 mappings: 1
-- Code(Counter(0)) at (prev + 11, 35) to (start + 0, 36)
+Number of file 0 mappings: 2
+- Code(Counter(0)) at (prev + 11, 34) to (start + 0, 35)
+- Code(Counter(0)) at (prev + 0, 35) to (start + 0, 36)
 Highest counter ID seen: c0
 
 Function name: async_closure::main::{closure#0}
-Raw bytes (9): 0x[01, 01, 00, 01, 01, 0b, 23, 00, 24]
+Raw bytes (14): 0x[01, 01, 00, 02, 01, 0b, 22, 00, 23, 01, 00, 23, 00, 24]
 Number of files: 1
 - file 0 => global file 1
 Number of expressions: 0
-Number of file 0 mappings: 1
-- Code(Counter(0)) at (prev + 11, 35) to (start + 0, 36)
+Number of file 0 mappings: 2
+- Code(Counter(0)) at (prev + 11, 34) to (start + 0, 35)
+- Code(Counter(0)) at (prev + 0, 35) to (start + 0, 36)
 Highest counter ID seen: c0
 
 Function name: async_closure::main::{closure#0}::{closure#0}::<i16>
diff --git a/tests/coverage/async_closure.coverage b/tests/coverage/async_closure.coverage
index 10a8ea14504..5aed131de2e 100644
--- a/tests/coverage/async_closure.coverage
+++ b/tests/coverage/async_closure.coverage
@@ -9,7 +9,6 @@
    LL|       |
    LL|      1|pub fn main() {
    LL|      2|    let async_closure = async || {};
-                                               ^1
   ------------------
   | async_closure::main::{closure#0}:
   |   LL|      1|    let async_closure = async || {};
@@ -17,6 +16,9 @@
   | async_closure::main::{closure#0}:
   |   LL|      1|    let async_closure = async || {};
   ------------------
+  | async_closure::main::{closure#0}::{closure#0}::<i16>:
+  |   LL|      1|    let async_closure = async || {};
+  ------------------
    LL|      1|    executor::block_on(async_closure());
    LL|      1|    executor::block_on(call_once(async_closure));
    LL|      1|}
diff --git a/tests/coverage/closure.cov-map b/tests/coverage/closure.cov-map
index fa20c8cf6d7..2d784ba09b6 100644
--- a/tests/coverage/closure.cov-map
+++ b/tests/coverage/closure.cov-map
@@ -1,15 +1,15 @@
 Function name: closure::main
-Raw bytes (126): 0x[01, 01, 01, 01, 05, 18, 01, 09, 01, 0f, 0d, 01, 16, 0e, 06, 0a, 01, 10, 05, 13, 0d, 01, 1a, 0e, 06, 0a, 01, 10, 05, 0c, 16, 01, 16, 05, 0d, 18, 01, 19, 09, 01, 1e, 01, 04, 09, 00, 29, 01, 01, 09, 00, 2d, 01, 01, 09, 00, 24, 01, 05, 09, 00, 24, 01, 02, 09, 00, 21, 01, 04, 09, 00, 21, 01, 04, 09, 00, 28, 01, 09, 09, 00, 32, 01, 04, 09, 00, 33, 01, 07, 09, 00, 4b, 01, 08, 09, 00, 48, 01, 0a, 09, 00, 47, 01, 08, 09, 00, 44, 01, 0a, 08, 00, 10, 05, 00, 11, 04, 06, 02, 04, 05, 00, 06, 01, 01, 05, 03, 02]
+Raw bytes (126): 0x[01, 01, 01, 01, 05, 18, 01, 09, 01, 0d, 1b, 01, 1a, 05, 02, 0a, 01, 0c, 05, 11, 1b, 01, 1e, 05, 02, 0a, 01, 0c, 05, 0c, 16, 01, 16, 05, 0d, 18, 01, 19, 09, 01, 1e, 01, 04, 09, 00, 29, 01, 01, 09, 00, 2d, 01, 01, 09, 00, 24, 01, 05, 09, 00, 24, 01, 02, 09, 00, 21, 01, 04, 09, 00, 21, 01, 04, 09, 00, 28, 01, 09, 09, 00, 32, 01, 04, 09, 00, 33, 01, 07, 09, 00, 4b, 01, 08, 09, 00, 48, 01, 0a, 09, 00, 47, 01, 08, 09, 00, 44, 01, 0a, 08, 00, 10, 05, 00, 11, 04, 06, 02, 04, 05, 00, 06, 01, 01, 05, 03, 02]
 Number of files: 1
 - file 0 => global file 1
 Number of expressions: 1
 - expression 0 operands: lhs = Counter(0), rhs = Counter(1)
 Number of file 0 mappings: 24
-- Code(Counter(0)) at (prev + 9, 1) to (start + 15, 13)
-- Code(Counter(0)) at (prev + 22, 14) to (start + 6, 10)
-- Code(Counter(0)) at (prev + 16, 5) to (start + 19, 13)
-- Code(Counter(0)) at (prev + 26, 14) to (start + 6, 10)
-- Code(Counter(0)) at (prev + 16, 5) to (start + 12, 22)
+- Code(Counter(0)) at (prev + 9, 1) to (start + 13, 27)
+- Code(Counter(0)) at (prev + 26, 5) to (start + 2, 10)
+- Code(Counter(0)) at (prev + 12, 5) to (start + 17, 27)
+- Code(Counter(0)) at (prev + 30, 5) to (start + 2, 10)
+- Code(Counter(0)) at (prev + 12, 5) to (start + 12, 22)
 - Code(Counter(0)) at (prev + 22, 5) to (start + 13, 24)
 - Code(Counter(0)) at (prev + 25, 9) to (start + 1, 30)
 - Code(Counter(0)) at (prev + 4, 9) to (start + 0, 41)
diff --git a/tests/coverage/closure.coverage b/tests/coverage/closure.coverage
index 3eac52eb723..2deeb9806c4 100644
--- a/tests/coverage/closure.coverage
+++ b/tests/coverage/closure.coverage
@@ -20,18 +20,18 @@
    LL|      1|        some_string
    LL|      1|            .
    LL|      1|            unwrap_or_else
-   LL|      1|        (
-   LL|      1|            ||
+   LL|       |        (
+   LL|       |            ||
    LL|      0|            {
    LL|      0|                let mut countdown = 0;
    LL|      0|                if is_false {
    LL|      0|                    countdown = 10;
    LL|      0|                }
    LL|      0|                "alt string 1".to_owned()
-   LL|      1|            }
-   LL|      1|        )
-   LL|      1|    );
-   LL|      1|
+   LL|      0|            }
+   LL|       |        )
+   LL|       |    );
+   LL|       |
    LL|      1|    some_string = Some(String::from("the string content"));
    LL|      1|    let
    LL|      1|        a
@@ -62,8 +62,8 @@
    LL|      1|        some_string
    LL|      1|            .
    LL|      1|            unwrap_or_else
-   LL|      1|        (
-   LL|      1|            ||
+   LL|       |        (
+   LL|       |            ||
    LL|      1|            {
    LL|      1|                let mut countdown = 0;
    LL|      1|                if is_false {
@@ -71,9 +71,9 @@
    LL|      1|                }
    LL|      1|                "alt string 3".to_owned()
    LL|      1|            }
-   LL|      1|        )
-   LL|      1|    );
-   LL|      1|
+   LL|       |        )
+   LL|       |    );
+   LL|       |
    LL|      1|    some_string = None;
    LL|      1|    let
    LL|      1|        a
diff --git a/tests/coverage/holes.cov-map b/tests/coverage/holes.cov-map
index 8ff291d2d7d..6e2d243e8dd 100644
--- a/tests/coverage/holes.cov-map
+++ b/tests/coverage/holes.cov-map
@@ -8,7 +8,7 @@ Number of file 0 mappings: 1
 Highest counter ID seen: (none)
 
 Function name: holes::main
-Raw bytes (69): 0x[01, 01, 00, 0d, 01, 08, 01, 01, 11, 01, 05, 05, 00, 11, 01, 07, 09, 00, 11, 01, 09, 05, 00, 11, 01, 04, 05, 00, 11, 01, 07, 05, 00, 11, 01, 06, 05, 00, 11, 01, 04, 05, 00, 11, 01, 04, 05, 00, 11, 01, 06, 05, 03, 0f, 01, 0a, 05, 03, 0f, 01, 0a, 05, 0c, 0d, 01, 0f, 0e, 05, 02]
+Raw bytes (69): 0x[01, 01, 00, 0d, 01, 08, 01, 01, 11, 01, 05, 05, 00, 11, 01, 07, 09, 00, 11, 01, 09, 05, 00, 11, 01, 04, 05, 00, 11, 01, 07, 05, 00, 11, 01, 06, 05, 00, 11, 01, 04, 05, 00, 11, 01, 04, 05, 00, 11, 01, 06, 05, 03, 0f, 01, 0a, 05, 03, 0f, 01, 0a, 05, 06, 27, 01, 13, 05, 01, 02]
 Number of files: 1
 - file 0 => global file 1
 Number of expressions: 0
@@ -24,8 +24,8 @@ Number of file 0 mappings: 13
 - Code(Counter(0)) at (prev + 4, 5) to (start + 0, 17)
 - Code(Counter(0)) at (prev + 6, 5) to (start + 3, 15)
 - Code(Counter(0)) at (prev + 10, 5) to (start + 3, 15)
-- Code(Counter(0)) at (prev + 10, 5) to (start + 12, 13)
-- Code(Counter(0)) at (prev + 15, 14) to (start + 5, 2)
+- Code(Counter(0)) at (prev + 10, 5) to (start + 6, 39)
+- Code(Counter(0)) at (prev + 19, 5) to (start + 1, 2)
 Highest counter ID seen: c0
 
 Function name: holes::main::_unused_fn (unused)
diff --git a/tests/coverage/holes.coverage b/tests/coverage/holes.coverage
index 1b45c12156a..a6a02f1b9d0 100644
--- a/tests/coverage/holes.coverage
+++ b/tests/coverage/holes.coverage
@@ -84,18 +84,18 @@
    LL|      1|    // `nested_filter::OnlyBodies` or equivalent.
    LL|      1|    #[rustfmt::skip]
    LL|      1|    let _const_block_inside_anon_const =
-   LL|      1|        [
-   LL|      1|            0
-   LL|      1|            ;
-   LL|      1|            7
-   LL|      1|            +
-   LL|      1|            const
+   LL|       |        [
+   LL|       |            0
+   LL|       |            ;
+   LL|       |            7
+   LL|       |            +
+   LL|       |            const
    LL|       |            {
    LL|       |                3
-   LL|      1|            }
-   LL|      1|        ]
-   LL|      1|        ;
-   LL|      1|
+   LL|       |            }
+   LL|       |        ]
+   LL|       |        ;
+   LL|       |
    LL|      1|    black_box(());
    LL|      1|}