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