]>
Commit | Line | Data |
---|---|---|
29967ef6 | 1 | use super::debug::term_type; |
fc512014 | 2 | use super::graph::{BasicCoverageBlock, BasicCoverageBlockData, CoverageGraph, START_BCB}; |
29967ef6 | 3 | |
5099ac24 | 4 | use itertools::Itertools; |
29967ef6 | 5 | use rustc_data_structures::graph::WithNumNodes; |
c295e0f8 | 6 | use rustc_middle::mir::spanview::source_range_no_file; |
29967ef6 XL |
7 | use rustc_middle::mir::{ |
8 | self, AggregateKind, BasicBlock, FakeReadCause, Rvalue, Statement, StatementKind, Terminator, | |
9 | TerminatorKind, | |
10 | }; | |
11 | use rustc_middle::ty::TyCtxt; | |
29967ef6 | 12 | use rustc_span::source_map::original_sp; |
17df50a5 | 13 | use rustc_span::{BytePos, ExpnKind, MacroKind, Span, Symbol}; |
29967ef6 | 14 | |
17df50a5 | 15 | use std::cell::RefCell; |
29967ef6 XL |
16 | use std::cmp::Ordering; |
17 | ||
18 | #[derive(Debug, Copy, Clone)] | |
fc512014 | 19 | pub(super) enum CoverageStatement { |
29967ef6 XL |
20 | Statement(BasicBlock, Span, usize), |
21 | Terminator(BasicBlock, Span), | |
22 | } | |
23 | ||
24 | impl CoverageStatement { | |
a2a8927a | 25 | pub fn format<'tcx>(&self, tcx: TyCtxt<'tcx>, mir_body: &mir::Body<'tcx>) -> String { |
29967ef6 XL |
26 | match *self { |
27 | Self::Statement(bb, span, stmt_index) => { | |
28 | let stmt = &mir_body[bb].statements[stmt_index]; | |
29 | format!( | |
30 | "{}: @{}[{}]: {:?}", | |
5099ac24 | 31 | source_range_no_file(tcx, span), |
29967ef6 XL |
32 | bb.index(), |
33 | stmt_index, | |
34 | stmt | |
35 | ) | |
36 | } | |
37 | Self::Terminator(bb, span) => { | |
38 | let term = mir_body[bb].terminator(); | |
39 | format!( | |
40 | "{}: @{}.{}: {:?}", | |
5099ac24 | 41 | source_range_no_file(tcx, span), |
29967ef6 XL |
42 | bb.index(), |
43 | term_type(&term.kind), | |
44 | term.kind | |
45 | ) | |
46 | } | |
47 | } | |
48 | } | |
49 | ||
5e7ed085 | 50 | pub fn span(&self) -> Span { |
29967ef6 | 51 | match self { |
5e7ed085 | 52 | Self::Statement(_, span, _) | Self::Terminator(_, span) => *span, |
29967ef6 XL |
53 | } |
54 | } | |
55 | } | |
56 | ||
57 | /// A BCB is deconstructed into one or more `Span`s. Each `Span` maps to a `CoverageSpan` that | |
58 | /// references the originating BCB and one or more MIR `Statement`s and/or `Terminator`s. | |
59 | /// Initially, the `Span`s come from the `Statement`s and `Terminator`s, but subsequent | |
60 | /// transforms can combine adjacent `Span`s and `CoverageSpan` from the same BCB, merging the | |
61 | /// `CoverageStatement` vectors, and the `Span`s to cover the extent of the combined `Span`s. | |
62 | /// | |
63 | /// Note: A `CoverageStatement` merged into another CoverageSpan may come from a `BasicBlock` that | |
64 | /// is not part of the `CoverageSpan` bcb if the statement was included because it's `Span` matches | |
65 | /// or is subsumed by the `Span` associated with this `CoverageSpan`, and it's `BasicBlock` | |
9ffffee4 | 66 | /// `dominates()` the `BasicBlock`s in this `CoverageSpan`. |
29967ef6 | 67 | #[derive(Debug, Clone)] |
fc512014 | 68 | pub(super) struct CoverageSpan { |
29967ef6 | 69 | pub span: Span, |
17df50a5 XL |
70 | pub expn_span: Span, |
71 | pub current_macro_or_none: RefCell<Option<Option<Symbol>>>, | |
29967ef6 XL |
72 | pub bcb: BasicCoverageBlock, |
73 | pub coverage_statements: Vec<CoverageStatement>, | |
74 | pub is_closure: bool, | |
75 | } | |
76 | ||
77 | impl CoverageSpan { | |
fc512014 | 78 | pub fn for_fn_sig(fn_sig_span: Span) -> Self { |
17df50a5 XL |
79 | Self { |
80 | span: fn_sig_span, | |
81 | expn_span: fn_sig_span, | |
82 | current_macro_or_none: Default::default(), | |
83 | bcb: START_BCB, | |
84 | coverage_statements: vec![], | |
85 | is_closure: false, | |
86 | } | |
fc512014 XL |
87 | } |
88 | ||
29967ef6 | 89 | pub fn for_statement( |
a2a8927a | 90 | statement: &Statement<'_>, |
29967ef6 | 91 | span: Span, |
17df50a5 | 92 | expn_span: Span, |
29967ef6 XL |
93 | bcb: BasicCoverageBlock, |
94 | bb: BasicBlock, | |
95 | stmt_index: usize, | |
96 | ) -> Self { | |
97 | let is_closure = match statement.kind { | |
3c0e092e XL |
98 | StatementKind::Assign(box (_, Rvalue::Aggregate(box ref kind, _))) => { |
99 | matches!(kind, AggregateKind::Closure(_, _) | AggregateKind::Generator(_, _, _)) | |
100 | } | |
29967ef6 XL |
101 | _ => false, |
102 | }; | |
103 | ||
104 | Self { | |
105 | span, | |
17df50a5 XL |
106 | expn_span, |
107 | current_macro_or_none: Default::default(), | |
29967ef6 XL |
108 | bcb, |
109 | coverage_statements: vec![CoverageStatement::Statement(bb, span, stmt_index)], | |
110 | is_closure, | |
111 | } | |
112 | } | |
113 | ||
17df50a5 XL |
114 | pub fn for_terminator( |
115 | span: Span, | |
116 | expn_span: Span, | |
117 | bcb: BasicCoverageBlock, | |
118 | bb: BasicBlock, | |
119 | ) -> Self { | |
29967ef6 XL |
120 | Self { |
121 | span, | |
17df50a5 XL |
122 | expn_span, |
123 | current_macro_or_none: Default::default(), | |
29967ef6 XL |
124 | bcb, |
125 | coverage_statements: vec![CoverageStatement::Terminator(bb, span)], | |
126 | is_closure: false, | |
127 | } | |
128 | } | |
129 | ||
130 | pub fn merge_from(&mut self, mut other: CoverageSpan) { | |
131 | debug_assert!(self.is_mergeable(&other)); | |
132 | self.span = self.span.to(other.span); | |
29967ef6 XL |
133 | self.coverage_statements.append(&mut other.coverage_statements); |
134 | } | |
135 | ||
136 | pub fn cutoff_statements_at(&mut self, cutoff_pos: BytePos) { | |
137 | self.coverage_statements.retain(|covstmt| covstmt.span().hi() <= cutoff_pos); | |
138 | if let Some(highest_covstmt) = | |
139 | self.coverage_statements.iter().max_by_key(|covstmt| covstmt.span().hi()) | |
140 | { | |
141 | self.span = self.span.with_hi(highest_covstmt.span().hi()); | |
142 | } | |
143 | } | |
144 | ||
145 | #[inline] | |
146 | pub fn is_mergeable(&self, other: &Self) -> bool { | |
147 | self.is_in_same_bcb(other) && !(self.is_closure || other.is_closure) | |
148 | } | |
149 | ||
150 | #[inline] | |
151 | pub fn is_in_same_bcb(&self, other: &Self) -> bool { | |
152 | self.bcb == other.bcb | |
153 | } | |
154 | ||
a2a8927a | 155 | pub fn format<'tcx>(&self, tcx: TyCtxt<'tcx>, mir_body: &mir::Body<'tcx>) -> String { |
29967ef6 XL |
156 | format!( |
157 | "{}\n {}", | |
5099ac24 | 158 | source_range_no_file(tcx, self.span), |
a2a8927a | 159 | self.format_coverage_statements(tcx, mir_body).replace('\n', "\n "), |
29967ef6 XL |
160 | ) |
161 | } | |
162 | ||
a2a8927a | 163 | pub fn format_coverage_statements<'tcx>( |
29967ef6 XL |
164 | &self, |
165 | tcx: TyCtxt<'tcx>, | |
a2a8927a | 166 | mir_body: &mir::Body<'tcx>, |
29967ef6 XL |
167 | ) -> String { |
168 | let mut sorted_coverage_statements = self.coverage_statements.clone(); | |
169 | sorted_coverage_statements.sort_unstable_by_key(|covstmt| match *covstmt { | |
170 | CoverageStatement::Statement(bb, _, index) => (bb, index), | |
171 | CoverageStatement::Terminator(bb, _) => (bb, usize::MAX), | |
172 | }); | |
5099ac24 | 173 | sorted_coverage_statements.iter().map(|covstmt| covstmt.format(tcx, mir_body)).join("\n") |
29967ef6 | 174 | } |
17df50a5 XL |
175 | |
176 | /// If the span is part of a macro, returns the macro name symbol. | |
177 | pub fn current_macro(&self) -> Option<Symbol> { | |
178 | self.current_macro_or_none | |
179 | .borrow_mut() | |
180 | .get_or_insert_with(|| { | |
136023e0 XL |
181 | if let ExpnKind::Macro(MacroKind::Bang, current_macro) = |
182 | self.expn_span.ctxt().outer_expn_data().kind | |
17df50a5 XL |
183 | { |
184 | return Some(current_macro); | |
185 | } | |
186 | None | |
187 | }) | |
188 | .map(|symbol| symbol) | |
189 | } | |
190 | ||
191 | /// If the span is part of a macro, and the macro is visible (expands directly to the given | |
192 | /// body_span), returns the macro name symbol. | |
193 | pub fn visible_macro(&self, body_span: Span) -> Option<Symbol> { | |
5e7ed085 FG |
194 | if let Some(current_macro) = self.current_macro() && self |
195 | .expn_span | |
196 | .parent_callsite() | |
197 | .unwrap_or_else(|| bug!("macro must have a parent")) | |
923072b8 | 198 | .eq_ctxt(body_span) |
5e7ed085 FG |
199 | { |
200 | return Some(current_macro); | |
17df50a5 XL |
201 | } |
202 | None | |
203 | } | |
204 | ||
205 | pub fn is_macro_expansion(&self) -> bool { | |
206 | self.current_macro().is_some() | |
207 | } | |
29967ef6 XL |
208 | } |
209 | ||
210 | /// Converts the initial set of `CoverageSpan`s (one per MIR `Statement` or `Terminator`) into a | |
211 | /// minimal set of `CoverageSpan`s, using the BCB CFG to determine where it is safe and useful to: | |
212 | /// | |
213 | /// * Remove duplicate source code coverage regions | |
214 | /// * Merge spans that represent continuous (both in source code and control flow), non-branching | |
215 | /// execution | |
216 | /// * Carve out (leave uncovered) any span that will be counted by another MIR (notably, closures) | |
217 | pub struct CoverageSpans<'a, 'tcx> { | |
218 | /// The MIR, used to look up `BasicBlockData`. | |
219 | mir_body: &'a mir::Body<'tcx>, | |
220 | ||
fc512014 XL |
221 | /// A `Span` covering the signature of function for the MIR. |
222 | fn_sig_span: Span, | |
223 | ||
29967ef6 XL |
224 | /// A `Span` covering the function body of the MIR (typically from left curly brace to right |
225 | /// curly brace). | |
226 | body_span: Span, | |
227 | ||
228 | /// The BasicCoverageBlock Control Flow Graph (BCB CFG). | |
229 | basic_coverage_blocks: &'a CoverageGraph, | |
230 | ||
231 | /// The initial set of `CoverageSpan`s, sorted by `Span` (`lo` and `hi`) and by relative | |
232 | /// dominance between the `BasicCoverageBlock`s of equal `Span`s. | |
233 | sorted_spans_iter: Option<std::vec::IntoIter<CoverageSpan>>, | |
234 | ||
235 | /// The current `CoverageSpan` to compare to its `prev`, to possibly merge, discard, force the | |
236 | /// discard of the `prev` (and or `pending_dups`), or keep both (with `prev` moved to | |
237 | /// `pending_dups`). If `curr` is not discarded or merged, it becomes `prev` for the next | |
238 | /// iteration. | |
239 | some_curr: Option<CoverageSpan>, | |
240 | ||
17df50a5 XL |
241 | /// The original `span` for `curr`, in case `curr.span()` is modified. The `curr_original_span` |
242 | /// **must not be mutated** (except when advancing to the next `curr`), even if `curr.span()` | |
243 | /// is mutated. | |
29967ef6 XL |
244 | curr_original_span: Span, |
245 | ||
246 | /// The CoverageSpan from a prior iteration; typically assigned from that iteration's `curr`. | |
247 | /// If that `curr` was discarded, `prev` retains its value from the previous iteration. | |
248 | some_prev: Option<CoverageSpan>, | |
249 | ||
17df50a5 XL |
250 | /// Assigned from `curr_original_span` from the previous iteration. The `prev_original_span` |
251 | /// **must not be mutated** (except when advancing to the next `prev`), even if `prev.span()` | |
252 | /// is mutated. | |
29967ef6 XL |
253 | prev_original_span: Span, |
254 | ||
17df50a5 XL |
255 | /// A copy of the expn_span from the prior iteration. |
256 | prev_expn_span: Option<Span>, | |
257 | ||
29967ef6 XL |
258 | /// One or more `CoverageSpan`s with the same `Span` but different `BasicCoverageBlock`s, and |
259 | /// no `BasicCoverageBlock` in this list dominates another `BasicCoverageBlock` in the list. | |
260 | /// If a new `curr` span also fits this criteria (compared to an existing list of | |
261 | /// `pending_dups`), that `curr` `CoverageSpan` moves to `prev` before possibly being added to | |
262 | /// the `pending_dups` list, on the next iteration. As a result, if `prev` and `pending_dups` | |
263 | /// have the same `Span`, the criteria for `pending_dups` holds for `prev` as well: a `prev` | |
264 | /// with a matching `Span` does not dominate any `pending_dup` and no `pending_dup` dominates a | |
265 | /// `prev` with a matching `Span`) | |
266 | pending_dups: Vec<CoverageSpan>, | |
267 | ||
268 | /// The final `CoverageSpan`s to add to the coverage map. A `Counter` or `Expression` | |
269 | /// will also be injected into the MIR for each `CoverageSpan`. | |
270 | refined_spans: Vec<CoverageSpan>, | |
271 | } | |
272 | ||
273 | impl<'a, 'tcx> CoverageSpans<'a, 'tcx> { | |
fc512014 XL |
274 | /// Generate a minimal set of `CoverageSpan`s, each representing a contiguous code region to be |
275 | /// counted. | |
276 | /// | |
277 | /// The basic steps are: | |
278 | /// | |
279 | /// 1. Extract an initial set of spans from the `Statement`s and `Terminator`s of each | |
280 | /// `BasicCoverageBlockData`. | |
281 | /// 2. Sort the spans by span.lo() (starting position). Spans that start at the same position | |
282 | /// are sorted with longer spans before shorter spans; and equal spans are sorted | |
283 | /// (deterministically) based on "dominator" relationship (if any). | |
284 | /// 3. Traverse the spans in sorted order to identify spans that can be dropped (for instance, | |
285 | /// if another span or spans are already counting the same code region), or should be merged | |
286 | /// into a broader combined span (because it represents a contiguous, non-branching, and | |
287 | /// uninterrupted region of source code). | |
288 | /// | |
289 | /// Closures are exposed in their enclosing functions as `Assign` `Rvalue`s, and since | |
290 | /// closures have their own MIR, their `Span` in their enclosing function should be left | |
291 | /// "uncovered". | |
292 | /// | |
293 | /// Note the resulting vector of `CoverageSpan`s may not be fully sorted (and does not need | |
294 | /// to be). | |
295 | pub(super) fn generate_coverage_spans( | |
29967ef6 | 296 | mir_body: &'a mir::Body<'tcx>, |
cdc7bbd5 | 297 | fn_sig_span: Span, // Ensured to be same SourceFile and SyntaxContext as `body_span` |
29967ef6 XL |
298 | body_span: Span, |
299 | basic_coverage_blocks: &'a CoverageGraph, | |
300 | ) -> Vec<CoverageSpan> { | |
301 | let mut coverage_spans = CoverageSpans { | |
302 | mir_body, | |
fc512014 | 303 | fn_sig_span, |
29967ef6 XL |
304 | body_span, |
305 | basic_coverage_blocks, | |
306 | sorted_spans_iter: None, | |
307 | refined_spans: Vec::with_capacity(basic_coverage_blocks.num_nodes() * 2), | |
308 | some_curr: None, | |
309 | curr_original_span: Span::with_root_ctxt(BytePos(0), BytePos(0)), | |
310 | some_prev: None, | |
311 | prev_original_span: Span::with_root_ctxt(BytePos(0), BytePos(0)), | |
17df50a5 | 312 | prev_expn_span: None, |
29967ef6 XL |
313 | pending_dups: Vec::new(), |
314 | }; | |
315 | ||
316 | let sorted_spans = coverage_spans.mir_to_initial_sorted_coverage_spans(); | |
317 | ||
318 | coverage_spans.sorted_spans_iter = Some(sorted_spans.into_iter()); | |
29967ef6 XL |
319 | |
320 | coverage_spans.to_refined_spans() | |
321 | } | |
322 | ||
29967ef6 | 323 | fn mir_to_initial_sorted_coverage_spans(&self) -> Vec<CoverageSpan> { |
064997fb FG |
324 | let mut initial_spans = |
325 | Vec::<CoverageSpan>::with_capacity(self.mir_body.basic_blocks.len() * 2); | |
29967ef6 | 326 | for (bcb, bcb_data) in self.basic_coverage_blocks.iter_enumerated() { |
a2a8927a | 327 | initial_spans.extend(self.bcb_to_initial_coverage_spans(bcb, bcb_data)); |
29967ef6 XL |
328 | } |
329 | ||
330 | if initial_spans.is_empty() { | |
331 | // This can happen if, for example, the function is unreachable (contains only a | |
332 | // `BasicBlock`(s) with an `Unreachable` terminator). | |
333 | return initial_spans; | |
334 | } | |
335 | ||
fc512014 XL |
336 | initial_spans.push(CoverageSpan::for_fn_sig(self.fn_sig_span)); |
337 | ||
29967ef6 XL |
338 | initial_spans.sort_unstable_by(|a, b| { |
339 | if a.span.lo() == b.span.lo() { | |
340 | if a.span.hi() == b.span.hi() { | |
341 | if a.is_in_same_bcb(b) { | |
342 | Some(Ordering::Equal) | |
343 | } else { | |
9c376795 FG |
344 | // Sort equal spans by dominator relationship (so dominators always come |
345 | // before the dominated equal spans). When later comparing two spans in | |
346 | // order, the first will either dominate the second, or they will have no | |
347 | // dominator relationship. | |
348 | self.basic_coverage_blocks.dominators().rank_partial_cmp(a.bcb, b.bcb) | |
29967ef6 XL |
349 | } |
350 | } else { | |
351 | // Sort hi() in reverse order so shorter spans are attempted after longer spans. | |
352 | // This guarantees that, if a `prev` span overlaps, and is not equal to, a | |
353 | // `curr` span, the prev span either extends further left of the curr span, or | |
354 | // they start at the same position and the prev span extends further right of | |
355 | // the end of the curr span. | |
356 | b.span.hi().partial_cmp(&a.span.hi()) | |
357 | } | |
358 | } else { | |
359 | a.span.lo().partial_cmp(&b.span.lo()) | |
360 | } | |
361 | .unwrap() | |
362 | }); | |
363 | ||
364 | initial_spans | |
365 | } | |
366 | ||
367 | /// Iterate through the sorted `CoverageSpan`s, and return the refined list of merged and | |
368 | /// de-duplicated `CoverageSpan`s. | |
369 | fn to_refined_spans(mut self) -> Vec<CoverageSpan> { | |
370 | while self.next_coverage_span() { | |
17df50a5 XL |
371 | if self.some_prev.is_none() { |
372 | debug!(" initial span"); | |
373 | self.check_invoked_macro_name_span(); | |
374 | } else if self.curr().is_mergeable(self.prev()) { | |
29967ef6 XL |
375 | debug!(" same bcb (and neither is a closure), merge with prev={:?}", self.prev()); |
376 | let prev = self.take_prev(); | |
377 | self.curr_mut().merge_from(prev); | |
17df50a5 | 378 | self.check_invoked_macro_name_span(); |
29967ef6 XL |
379 | // Note that curr.span may now differ from curr_original_span |
380 | } else if self.prev_ends_before_curr() { | |
381 | debug!( | |
382 | " different bcbs and disjoint spans, so keep curr for next iter, and add \ | |
383 | prev={:?}", | |
384 | self.prev() | |
385 | ); | |
386 | let prev = self.take_prev(); | |
17df50a5 XL |
387 | self.push_refined_span(prev); |
388 | self.check_invoked_macro_name_span(); | |
29967ef6 XL |
389 | } else if self.prev().is_closure { |
390 | // drop any equal or overlapping span (`curr`) and keep `prev` to test again in the | |
391 | // next iter | |
392 | debug!( | |
393 | " curr overlaps a closure (prev). Drop curr and keep prev for next iter. \ | |
394 | prev={:?}", | |
395 | self.prev() | |
396 | ); | |
fc512014 | 397 | self.take_curr(); |
29967ef6 XL |
398 | } else if self.curr().is_closure { |
399 | self.carve_out_span_for_closure(); | |
400 | } else if self.prev_original_span == self.curr().span { | |
17df50a5 XL |
401 | // Note that this compares the new (`curr`) span to `prev_original_span`. |
402 | // In this branch, the actual span byte range of `prev_original_span` is not | |
403 | // important. What is important is knowing whether the new `curr` span was | |
404 | // **originally** the same as the original span of `prev()`. The original spans | |
405 | // reflect their original sort order, and for equal spans, conveys a partial | |
406 | // ordering based on CFG dominator priority. | |
407 | if self.prev().is_macro_expansion() && self.curr().is_macro_expansion() { | |
408 | // Macros that expand to include branching (such as | |
409 | // `assert_eq!()`, `assert_ne!()`, `info!()`, `debug!()`, or | |
9ffffee4 | 410 | // `trace!()`) typically generate callee spans with identical |
17df50a5 XL |
411 | // ranges (typically the full span of the macro) for all |
412 | // `BasicBlocks`. This makes it impossible to distinguish | |
413 | // the condition (`if val1 != val2`) from the optional | |
414 | // branched statements (such as the call to `panic!()` on | |
415 | // assert failure). In this case it is better (or less | |
416 | // worse) to drop the optional branch bcbs and keep the | |
417 | // non-conditional statements, to count when reached. | |
418 | debug!( | |
419 | " curr and prev are part of a macro expansion, and curr has the same span \ | |
420 | as prev, but is in a different bcb. Drop curr and keep prev for next iter. \ | |
421 | prev={:?}", | |
422 | self.prev() | |
423 | ); | |
424 | self.take_curr(); | |
425 | } else { | |
426 | self.hold_pending_dups_unless_dominated(); | |
427 | } | |
29967ef6 XL |
428 | } else { |
429 | self.cutoff_prev_at_overlapping_curr(); | |
17df50a5 | 430 | self.check_invoked_macro_name_span(); |
29967ef6 XL |
431 | } |
432 | } | |
433 | ||
434 | debug!(" AT END, adding last prev={:?}", self.prev()); | |
435 | let prev = self.take_prev(); | |
17df50a5 | 436 | let pending_dups = self.pending_dups.split_off(0); |
29967ef6 XL |
437 | for dup in pending_dups { |
438 | debug!(" ...adding at least one pending dup={:?}", dup); | |
17df50a5 | 439 | self.push_refined_span(dup); |
29967ef6 | 440 | } |
fc512014 XL |
441 | |
442 | // Async functions wrap a closure that implements the body to be executed. The enclosing | |
443 | // function is called and returns an `impl Future` without initially executing any of the | |
444 | // body. To avoid showing the return from the enclosing function as a "covered" return from | |
445 | // the closure, the enclosing function's `TerminatorKind::Return`s `CoverageSpan` is | |
446 | // excluded. The closure's `Return` is the only one that will be counted. This provides | |
447 | // adequate coverage, and more intuitive counts. (Avoids double-counting the closing brace | |
448 | // of the function body.) | |
17df50a5 | 449 | let body_ends_with_closure = if let Some(last_covspan) = self.refined_spans.last() { |
fc512014 XL |
450 | last_covspan.is_closure && last_covspan.span.hi() == self.body_span.hi() |
451 | } else { | |
452 | false | |
453 | }; | |
454 | ||
455 | if !body_ends_with_closure { | |
17df50a5 | 456 | self.push_refined_span(prev); |
29967ef6 | 457 | } |
29967ef6 XL |
458 | |
459 | // Remove `CoverageSpan`s derived from closures, originally added to ensure the coverage | |
460 | // regions for the current function leave room for the closure's own coverage regions | |
461 | // (injected separately, from the closure's own MIR). | |
17df50a5 XL |
462 | self.refined_spans.retain(|covspan| !covspan.is_closure); |
463 | self.refined_spans | |
464 | } | |
465 | ||
466 | fn push_refined_span(&mut self, covspan: CoverageSpan) { | |
467 | let len = self.refined_spans.len(); | |
468 | if len > 0 { | |
469 | let last = &mut self.refined_spans[len - 1]; | |
470 | if last.is_mergeable(&covspan) { | |
471 | debug!( | |
472 | "merging new refined span with last refined span, last={:?}, covspan={:?}", | |
473 | last, covspan | |
474 | ); | |
475 | last.merge_from(covspan); | |
476 | return; | |
477 | } | |
478 | } | |
479 | self.refined_spans.push(covspan) | |
480 | } | |
481 | ||
482 | fn check_invoked_macro_name_span(&mut self) { | |
483 | if let Some(visible_macro) = self.curr().visible_macro(self.body_span) { | |
484 | if self.prev_expn_span.map_or(true, |prev_expn_span| { | |
485 | self.curr().expn_span.ctxt() != prev_expn_span.ctxt() | |
486 | }) { | |
487 | let merged_prefix_len = self.curr_original_span.lo() - self.curr().span.lo(); | |
488 | let after_macro_bang = | |
04454e1e | 489 | merged_prefix_len + BytePos(visible_macro.as_str().len() as u32 + 1); |
17df50a5 XL |
490 | let mut macro_name_cov = self.curr().clone(); |
491 | self.curr_mut().span = | |
492 | self.curr().span.with_lo(self.curr().span.lo() + after_macro_bang); | |
493 | macro_name_cov.span = | |
494 | macro_name_cov.span.with_hi(macro_name_cov.span.lo() + after_macro_bang); | |
495 | debug!( | |
496 | " and curr starts a new macro expansion, so add a new span just for \ | |
497 | the macro `{}!`, new span={:?}", | |
498 | visible_macro, macro_name_cov | |
499 | ); | |
500 | self.push_refined_span(macro_name_cov); | |
501 | } | |
502 | } | |
29967ef6 XL |
503 | } |
504 | ||
505 | // Generate a set of `CoverageSpan`s from the filtered set of `Statement`s and `Terminator`s of | |
506 | // the `BasicBlock`(s) in the given `BasicCoverageBlockData`. One `CoverageSpan` is generated | |
507 | // for each `Statement` and `Terminator`. (Note that subsequent stages of coverage analysis will | |
508 | // merge some `CoverageSpan`s, at which point a `CoverageSpan` may represent multiple | |
509 | // `Statement`s and/or `Terminator`s.) | |
510 | fn bcb_to_initial_coverage_spans( | |
511 | &self, | |
512 | bcb: BasicCoverageBlock, | |
513 | bcb_data: &'a BasicCoverageBlockData, | |
514 | ) -> Vec<CoverageSpan> { | |
515 | bcb_data | |
516 | .basic_blocks | |
517 | .iter() | |
518 | .flat_map(|&bb| { | |
519 | let data = &self.mir_body[bb]; | |
520 | data.statements | |
521 | .iter() | |
522 | .enumerate() | |
523 | .filter_map(move |(index, statement)| { | |
17df50a5 XL |
524 | filtered_statement_span(statement).map(|span| { |
525 | CoverageSpan::for_statement( | |
526 | statement, | |
527 | function_source_span(span, self.body_span), | |
528 | span, | |
529 | bcb, | |
530 | bb, | |
531 | index, | |
532 | ) | |
29967ef6 XL |
533 | }) |
534 | }) | |
17df50a5 XL |
535 | .chain(filtered_terminator_span(data.terminator()).map(|span| { |
536 | CoverageSpan::for_terminator( | |
537 | function_source_span(span, self.body_span), | |
538 | span, | |
539 | bcb, | |
540 | bb, | |
541 | ) | |
542 | })) | |
29967ef6 XL |
543 | }) |
544 | .collect() | |
545 | } | |
546 | ||
547 | fn curr(&self) -> &CoverageSpan { | |
548 | self.some_curr | |
549 | .as_ref() | |
550 | .unwrap_or_else(|| bug!("invalid attempt to unwrap a None some_curr")) | |
551 | } | |
552 | ||
553 | fn curr_mut(&mut self) -> &mut CoverageSpan { | |
554 | self.some_curr | |
555 | .as_mut() | |
556 | .unwrap_or_else(|| bug!("invalid attempt to unwrap a None some_curr")) | |
557 | } | |
558 | ||
559 | fn prev(&self) -> &CoverageSpan { | |
560 | self.some_prev | |
561 | .as_ref() | |
562 | .unwrap_or_else(|| bug!("invalid attempt to unwrap a None some_prev")) | |
563 | } | |
564 | ||
565 | fn prev_mut(&mut self) -> &mut CoverageSpan { | |
566 | self.some_prev | |
567 | .as_mut() | |
568 | .unwrap_or_else(|| bug!("invalid attempt to unwrap a None some_prev")) | |
569 | } | |
570 | ||
571 | fn take_prev(&mut self) -> CoverageSpan { | |
572 | self.some_prev.take().unwrap_or_else(|| bug!("invalid attempt to unwrap a None some_prev")) | |
573 | } | |
574 | ||
575 | /// If there are `pending_dups` but `prev` is not a matching dup (`prev.span` doesn't match the | |
576 | /// `pending_dups` spans), then one of the following two things happened during the previous | |
577 | /// iteration: | |
578 | /// * the previous `curr` span (which is now `prev`) was not a duplicate of the pending_dups | |
579 | /// (in which case there should be at least two spans in `pending_dups`); or | |
580 | /// * the `span` of `prev` was modified by `curr_mut().merge_from(prev)` (in which case | |
581 | /// `pending_dups` could have as few as one span) | |
582 | /// In either case, no more spans will match the span of `pending_dups`, so | |
583 | /// add the `pending_dups` if they don't overlap `curr`, and clear the list. | |
584 | fn check_pending_dups(&mut self) { | |
5e7ed085 FG |
585 | if let Some(dup) = self.pending_dups.last() && dup.span != self.prev().span { |
586 | debug!( | |
587 | " SAME spans, but pending_dups are NOT THE SAME, so BCBs matched on \ | |
588 | previous iteration, or prev started a new disjoint span" | |
589 | ); | |
590 | if dup.span.hi() <= self.curr().span.lo() { | |
591 | let pending_dups = self.pending_dups.split_off(0); | |
592 | for dup in pending_dups.into_iter() { | |
593 | debug!(" ...adding at least one pending={:?}", dup); | |
594 | self.push_refined_span(dup); | |
29967ef6 | 595 | } |
5e7ed085 FG |
596 | } else { |
597 | self.pending_dups.clear(); | |
29967ef6 XL |
598 | } |
599 | } | |
600 | } | |
601 | ||
602 | /// Advance `prev` to `curr` (if any), and `curr` to the next `CoverageSpan` in sorted order. | |
603 | fn next_coverage_span(&mut self) -> bool { | |
604 | if let Some(curr) = self.some_curr.take() { | |
17df50a5 | 605 | self.prev_expn_span = Some(curr.expn_span); |
29967ef6 XL |
606 | self.some_prev = Some(curr); |
607 | self.prev_original_span = self.curr_original_span; | |
608 | } | |
609 | while let Some(curr) = self.sorted_spans_iter.as_mut().unwrap().next() { | |
610 | debug!("FOR curr={:?}", curr); | |
17df50a5 | 611 | if self.some_prev.is_some() && self.prev_starts_after_next(&curr) { |
29967ef6 XL |
612 | debug!( |
613 | " prev.span starts after curr.span, so curr will be dropped (skipping past \ | |
614 | closure?); prev={:?}", | |
615 | self.prev() | |
616 | ); | |
617 | } else { | |
618 | // Save a copy of the original span for `curr` in case the `CoverageSpan` is changed | |
619 | // by `self.curr_mut().merge_from(prev)`. | |
620 | self.curr_original_span = curr.span; | |
621 | self.some_curr.replace(curr); | |
622 | self.check_pending_dups(); | |
623 | return true; | |
624 | } | |
625 | } | |
626 | false | |
627 | } | |
628 | ||
629 | /// If called, then the next call to `next_coverage_span()` will *not* update `prev` with the | |
630 | /// `curr` coverage span. | |
fc512014 XL |
631 | fn take_curr(&mut self) -> CoverageSpan { |
632 | self.some_curr.take().unwrap_or_else(|| bug!("invalid attempt to unwrap a None some_curr")) | |
29967ef6 XL |
633 | } |
634 | ||
635 | /// Returns true if the curr span should be skipped because prev has already advanced beyond the | |
636 | /// end of curr. This can only happen if a prior iteration updated `prev` to skip past a region | |
637 | /// of code, such as skipping past a closure. | |
638 | fn prev_starts_after_next(&self, next_curr: &CoverageSpan) -> bool { | |
639 | self.prev().span.lo() > next_curr.span.lo() | |
640 | } | |
641 | ||
642 | /// Returns true if the curr span starts past the end of the prev span, which means they don't | |
643 | /// overlap, so we now know the prev can be added to the refined coverage spans. | |
644 | fn prev_ends_before_curr(&self) -> bool { | |
645 | self.prev().span.hi() <= self.curr().span.lo() | |
646 | } | |
647 | ||
fc512014 XL |
648 | /// If `prev`s span extends left of the closure (`curr`), carve out the closure's span from |
649 | /// `prev`'s span. (The closure's coverage counters will be injected when processing the | |
650 | /// closure's own MIR.) Add the portion of the span to the left of the closure; and if the span | |
651 | /// extends to the right of the closure, update `prev` to that portion of the span. For any | |
652 | /// `pending_dups`, repeat the same process. | |
29967ef6 XL |
653 | fn carve_out_span_for_closure(&mut self) { |
654 | let curr_span = self.curr().span; | |
655 | let left_cutoff = curr_span.lo(); | |
656 | let right_cutoff = curr_span.hi(); | |
657 | let has_pre_closure_span = self.prev().span.lo() < right_cutoff; | |
658 | let has_post_closure_span = self.prev().span.hi() > right_cutoff; | |
659 | let mut pending_dups = self.pending_dups.split_off(0); | |
660 | if has_pre_closure_span { | |
661 | let mut pre_closure = self.prev().clone(); | |
662 | pre_closure.span = pre_closure.span.with_hi(left_cutoff); | |
663 | debug!(" prev overlaps a closure. Adding span for pre_closure={:?}", pre_closure); | |
664 | if !pending_dups.is_empty() { | |
665 | for mut dup in pending_dups.iter().cloned() { | |
666 | dup.span = dup.span.with_hi(left_cutoff); | |
667 | debug!(" ...and at least one pre_closure dup={:?}", dup); | |
17df50a5 | 668 | self.push_refined_span(dup); |
29967ef6 XL |
669 | } |
670 | } | |
17df50a5 | 671 | self.push_refined_span(pre_closure); |
29967ef6 XL |
672 | } |
673 | if has_post_closure_span { | |
17df50a5 XL |
674 | // Mutate `prev.span()` to start after the closure (and discard curr). |
675 | // (**NEVER** update `prev_original_span` because it affects the assumptions | |
676 | // about how the `CoverageSpan`s are ordered.) | |
29967ef6 | 677 | self.prev_mut().span = self.prev().span.with_lo(right_cutoff); |
17df50a5 | 678 | debug!(" Mutated prev.span to start after the closure. prev={:?}", self.prev()); |
29967ef6 | 679 | for dup in pending_dups.iter_mut() { |
17df50a5 | 680 | debug!(" ...and at least one overlapping dup={:?}", dup); |
29967ef6 XL |
681 | dup.span = dup.span.with_lo(right_cutoff); |
682 | } | |
683 | self.pending_dups.append(&mut pending_dups); | |
fc512014 | 684 | let closure_covspan = self.take_curr(); |
17df50a5 | 685 | self.push_refined_span(closure_covspan); // since self.prev() was already updated |
29967ef6 XL |
686 | } else { |
687 | pending_dups.clear(); | |
688 | } | |
689 | } | |
690 | ||
691 | /// Called if `curr.span` equals `prev_original_span` (and potentially equal to all | |
17df50a5 XL |
692 | /// `pending_dups` spans, if any). Keep in mind, `prev.span()` may have been changed. |
693 | /// If prev.span() was merged into other spans (with matching BCB, for instance), | |
694 | /// `prev.span.hi()` will be greater than (further right of) `prev_original_span.hi()`. | |
695 | /// If prev.span() was split off to the right of a closure, prev.span().lo() will be | |
696 | /// greater than prev_original_span.lo(). The actual span of `prev_original_span` is | |
9ffffee4 | 697 | /// not as important as knowing that `prev()` **used to have the same span** as `curr()`, |
5e7ed085 | 698 | /// which means their sort order is still meaningful for determining the dominator |
17df50a5 | 699 | /// relationship. |
29967ef6 XL |
700 | /// |
701 | /// When two `CoverageSpan`s have the same `Span`, dominated spans can be discarded; but if | |
702 | /// neither `CoverageSpan` dominates the other, both (or possibly more than two) are held, | |
703 | /// until their disposition is determined. In this latter case, the `prev` dup is moved into | |
704 | /// `pending_dups` so the new `curr` dup can be moved to `prev` for the next iteration. | |
705 | fn hold_pending_dups_unless_dominated(&mut self) { | |
706 | // Equal coverage spans are ordered by dominators before dominated (if any), so it should be | |
707 | // impossible for `curr` to dominate any previous `CoverageSpan`. | |
9ffffee4 | 708 | debug_assert!(!self.span_bcb_dominates(self.curr(), self.prev())); |
29967ef6 XL |
709 | |
710 | let initial_pending_count = self.pending_dups.len(); | |
711 | if initial_pending_count > 0 { | |
712 | let mut pending_dups = self.pending_dups.split_off(0); | |
9ffffee4 | 713 | pending_dups.retain(|dup| !self.span_bcb_dominates(dup, self.curr())); |
29967ef6 XL |
714 | self.pending_dups.append(&mut pending_dups); |
715 | if self.pending_dups.len() < initial_pending_count { | |
716 | debug!( | |
717 | " discarded {} of {} pending_dups that dominated curr", | |
718 | initial_pending_count - self.pending_dups.len(), | |
719 | initial_pending_count | |
720 | ); | |
721 | } | |
722 | } | |
723 | ||
9ffffee4 | 724 | if self.span_bcb_dominates(self.prev(), self.curr()) { |
29967ef6 XL |
725 | debug!( |
726 | " different bcbs but SAME spans, and prev dominates curr. Discard prev={:?}", | |
727 | self.prev() | |
728 | ); | |
729 | self.cutoff_prev_at_overlapping_curr(); | |
5e7ed085 | 730 | // If one span dominates the other, associate the span with the code from the dominated |
29967ef6 XL |
731 | // block only (`curr`), and discard the overlapping portion of the `prev` span. (Note |
732 | // that if `prev.span` is wider than `prev_original_span`, a `CoverageSpan` will still | |
733 | // be created for `prev`s block, for the non-overlapping portion, left of `curr.span`.) | |
734 | // | |
735 | // For example: | |
736 | // match somenum { | |
737 | // x if x < 1 => { ... } | |
738 | // }... | |
739 | // | |
740 | // The span for the first `x` is referenced by both the pattern block (every time it is | |
741 | // evaluated) and the arm code (only when matched). The counter will be applied only to | |
742 | // the dominated block. This allows coverage to track and highlight things like the | |
743 | // assignment of `x` above, if the branch is matched, making `x` available to the arm | |
744 | // code; and to track and highlight the question mark `?` "try" operator at the end of | |
745 | // a function call returning a `Result`, so the `?` is covered when the function returns | |
746 | // an `Err`, and not counted as covered if the function always returns `Ok`. | |
747 | } else { | |
748 | // Save `prev` in `pending_dups`. (`curr` will become `prev` in the next iteration.) | |
749 | // If the `curr` CoverageSpan is later discarded, `pending_dups` can be discarded as | |
750 | // well; but if `curr` is added to refined_spans, the `pending_dups` will also be added. | |
751 | debug!( | |
752 | " different bcbs but SAME spans, and neither dominates, so keep curr for \ | |
753 | next iter, and, pending upcoming spans (unless overlapping) add prev={:?}", | |
754 | self.prev() | |
755 | ); | |
756 | let prev = self.take_prev(); | |
757 | self.pending_dups.push(prev); | |
758 | } | |
759 | } | |
760 | ||
761 | /// `curr` overlaps `prev`. If `prev`s span extends left of `curr`s span, keep _only_ | |
762 | /// statements that end before `curr.lo()` (if any), and add the portion of the | |
763 | /// combined span for those statements. Any other statements have overlapping spans | |
764 | /// that can be ignored because `curr` and/or other upcoming statements/spans inside | |
765 | /// the overlap area will produce their own counters. This disambiguation process | |
766 | /// avoids injecting multiple counters for overlapping spans, and the potential for | |
767 | /// double-counting. | |
768 | fn cutoff_prev_at_overlapping_curr(&mut self) { | |
769 | debug!( | |
770 | " different bcbs, overlapping spans, so ignore/drop pending and only add prev \ | |
771 | if it has statements that end before curr; prev={:?}", | |
772 | self.prev() | |
773 | ); | |
774 | if self.pending_dups.is_empty() { | |
775 | let curr_span = self.curr().span; | |
776 | self.prev_mut().cutoff_statements_at(curr_span.lo()); | |
777 | if self.prev().coverage_statements.is_empty() { | |
778 | debug!(" ... no non-overlapping statements to add"); | |
779 | } else { | |
780 | debug!(" ... adding modified prev={:?}", self.prev()); | |
781 | let prev = self.take_prev(); | |
17df50a5 | 782 | self.push_refined_span(prev); |
29967ef6 XL |
783 | } |
784 | } else { | |
785 | // with `pending_dups`, `prev` cannot have any statements that don't overlap | |
786 | self.pending_dups.clear(); | |
787 | } | |
788 | } | |
789 | ||
9ffffee4 FG |
790 | fn span_bcb_dominates(&self, dom_covspan: &CoverageSpan, covspan: &CoverageSpan) -> bool { |
791 | self.basic_coverage_blocks.dominates(dom_covspan.bcb, covspan.bcb) | |
29967ef6 XL |
792 | } |
793 | } | |
794 | ||
17df50a5 XL |
795 | /// If the MIR `Statement` has a span contributive to computing coverage spans, |
796 | /// return it; otherwise return `None`. | |
a2a8927a | 797 | pub(super) fn filtered_statement_span(statement: &Statement<'_>) -> Option<Span> { |
29967ef6 XL |
798 | match statement.kind { |
799 | // These statements have spans that are often outside the scope of the executed source code | |
800 | // for their parent `BasicBlock`. | |
801 | StatementKind::StorageLive(_) | |
802 | | StatementKind::StorageDead(_) | |
803 | // Coverage should not be encountered, but don't inject coverage coverage | |
804 | | StatementKind::Coverage(_) | |
9ffffee4 FG |
805 | // Ignore `ConstEvalCounter`s |
806 | | StatementKind::ConstEvalCounter | |
29967ef6 XL |
807 | // Ignore `Nop`s |
808 | | StatementKind::Nop => None, | |
809 | ||
810 | // FIXME(#78546): MIR InstrumentCoverage - Can the source_info.span for `FakeRead` | |
811 | // statements be more consistent? | |
812 | // | |
813 | // FakeReadCause::ForGuardBinding, in this example: | |
814 | // match somenum { | |
815 | // x if x < 1 => { ... } | |
816 | // }... | |
817 | // The BasicBlock within the match arm code included one of these statements, but the span | |
818 | // for it covered the `1` in this source. The actual statements have nothing to do with that | |
819 | // source span: | |
820 | // FakeRead(ForGuardBinding, _4); | |
821 | // where `_4` is: | |
822 | // _4 = &_1; (at the span for the first `x`) | |
823 | // and `_1` is the `Place` for `somenum`. | |
824 | // | |
825 | // If and when the Issue is resolved, remove this special case match pattern: | |
cdc7bbd5 | 826 | StatementKind::FakeRead(box (cause, _)) if cause == FakeReadCause::ForGuardBinding => None, |
29967ef6 XL |
827 | |
828 | // Retain spans from all other statements | |
cdc7bbd5 | 829 | StatementKind::FakeRead(box (_, _)) // Not including `ForGuardBinding` |
f2b60f7d | 830 | | StatementKind::Intrinsic(..) |
29967ef6 XL |
831 | | StatementKind::Assign(_) |
832 | | StatementKind::SetDiscriminant { .. } | |
04454e1e | 833 | | StatementKind::Deinit(..) |
29967ef6 | 834 | | StatementKind::Retag(_, _) |
353b0b11 | 835 | | StatementKind::PlaceMention(..) |
29967ef6 | 836 | | StatementKind::AscribeUserType(_, _) => { |
17df50a5 | 837 | Some(statement.source_info.span) |
29967ef6 XL |
838 | } |
839 | } | |
840 | } | |
841 | ||
17df50a5 XL |
842 | /// If the MIR `Terminator` has a span contributive to computing coverage spans, |
843 | /// return it; otherwise return `None`. | |
a2a8927a | 844 | pub(super) fn filtered_terminator_span(terminator: &Terminator<'_>) -> Option<Span> { |
29967ef6 XL |
845 | match terminator.kind { |
846 | // These terminators have spans that don't positively contribute to computing a reasonable | |
847 | // span of actually executed source code. (For example, SwitchInt terminators extracted from | |
848 | // an `if condition { block }` has a span that includes the executed block, if true, | |
849 | // but for coverage, the code region executed, up to *and* through the SwitchInt, | |
850 | // actually stops before the if's block.) | |
851 | TerminatorKind::Unreachable // Unreachable blocks are not connected to the MIR CFG | |
852 | | TerminatorKind::Assert { .. } | |
853 | | TerminatorKind::Drop { .. } | |
29967ef6 XL |
854 | | TerminatorKind::SwitchInt { .. } |
855 | // For `FalseEdge`, only the `real` branch is taken, so it is similar to a `Goto`. | |
fc512014 XL |
856 | | TerminatorKind::FalseEdge { .. } |
857 | | TerminatorKind::Goto { .. } => None, | |
29967ef6 | 858 | |
cdc7bbd5 XL |
859 | // Call `func` operand can have a more specific span when part of a chain of calls |
860 | | TerminatorKind::Call { ref func, .. } => { | |
861 | let mut span = terminator.source_info.span; | |
862 | if let mir::Operand::Constant(box constant) = func { | |
863 | if constant.span.lo() > span.lo() { | |
864 | span = span.with_lo(constant.span.lo()); | |
865 | } | |
866 | } | |
17df50a5 | 867 | Some(span) |
cdc7bbd5 XL |
868 | } |
869 | ||
29967ef6 XL |
870 | // Retain spans from all other terminators |
871 | TerminatorKind::Resume | |
353b0b11 | 872 | | TerminatorKind::Terminate |
29967ef6 | 873 | | TerminatorKind::Return |
29967ef6 XL |
874 | | TerminatorKind::Yield { .. } |
875 | | TerminatorKind::GeneratorDrop | |
876 | | TerminatorKind::FalseUnwind { .. } | |
877 | | TerminatorKind::InlineAsm { .. } => { | |
17df50a5 | 878 | Some(terminator.source_info.span) |
29967ef6 XL |
879 | } |
880 | } | |
881 | } | |
882 | ||
17df50a5 XL |
883 | /// Returns an extrapolated span (pre-expansion[^1]) corresponding to a range |
884 | /// within the function's body source. This span is guaranteed to be contained | |
885 | /// within, or equal to, the `body_span`. If the extrapolated span is not | |
886 | /// contained within the `body_span`, the `body_span` is returned. | |
887 | /// | |
888 | /// [^1]Expansions result from Rust syntax including macros, syntactic sugar, | |
889 | /// etc.). | |
29967ef6 | 890 | #[inline] |
17df50a5 XL |
891 | pub(super) fn function_source_span(span: Span, body_span: Span) -> Span { |
892 | let original_span = original_sp(span, body_span).with_ctxt(body_span.ctxt()); | |
893 | if body_span.contains(original_span) { original_span } else { body_span } | |
29967ef6 | 894 | } |