]>
Commit | Line | Data |
---|---|---|
fc512014 XL |
1 | //! [`super::usefulness`] explains most of what is happening in this file. As explained there, |
2 | //! values and patterns are made from constructors applied to fields. This file defines a | |
3 | //! `Constructor` enum, a `Fields` struct, and various operations to manipulate them and convert | |
4 | //! them from/to patterns. | |
5 | //! | |
6 | //! There's one idea that is not detailed in [`super::usefulness`] because the details are not | |
7 | //! needed there: _constructor splitting_. | |
8 | //! | |
9 | //! # Constructor splitting | |
10 | //! | |
11 | //! The idea is as follows: given a constructor `c` and a matrix, we want to specialize in turn | |
12 | //! with all the value constructors that are covered by `c`, and compute usefulness for each. | |
13 | //! Instead of listing all those constructors (which is intractable), we group those value | |
14 | //! constructors together as much as possible. Example: | |
15 | //! | |
16 | //! ``` | |
17 | //! match (0, false) { | |
18 | //! (0 ..=100, true) => {} // `p_1` | |
19 | //! (50..=150, false) => {} // `p_2` | |
20 | //! (0 ..=200, _) => {} // `q` | |
21 | //! } | |
22 | //! ``` | |
23 | //! | |
24 | //! The naive approach would try all numbers in the range `0..=200`. But we can be a lot more | |
25 | //! clever: `0` and `1` for example will match the exact same rows, and return equivalent | |
26 | //! witnesses. In fact all of `0..50` would. We can thus restrict our exploration to 4 | |
27 | //! constructors: `0..50`, `50..=100`, `101..=150` and `151..=200`. That is enough and infinitely | |
28 | //! more tractable. | |
29 | //! | |
30 | //! We capture this idea in a function `split(p_1 ... p_n, c)` which returns a list of constructors | |
31 | //! `c'` covered by `c`. Given such a `c'`, we require that all value ctors `c''` covered by `c'` | |
32 | //! return an equivalent set of witnesses after specializing and computing usefulness. | |
33 | //! In the example above, witnesses for specializing by `c''` covered by `0..50` will only differ | |
34 | //! in their first element. | |
35 | //! | |
36 | //! We usually also ask that the `c'` together cover all of the original `c`. However we allow | |
37 | //! skipping some constructors as long as it doesn't change whether the resulting list of witnesses | |
38 | //! is empty of not. We use this in the wildcard `_` case. | |
39 | //! | |
40 | //! Splitting is implemented in the [`Constructor::split`] function. We don't do splitting for | |
41 | //! or-patterns; instead we just try the alternatives one-by-one. For details on splitting | |
42 | //! wildcards, see [`SplitWildcard`]; for integer ranges, see [`SplitIntRange`]; for slices, see | |
43 | //! [`SplitVarLenSlice`]. | |
44 | ||
45 | use self::Constructor::*; | |
46 | use self::SliceKind::*; | |
47 | ||
48 | use super::compare_const_vals; | |
49 | use super::usefulness::{MatchCheckCtxt, PatCtxt}; | |
50 | use super::{FieldPat, Pat, PatKind, PatRange}; | |
51 | ||
52 | use rustc_data_structures::captures::Captures; | |
53 | use rustc_index::vec::Idx; | |
54 | ||
55 | use rustc_attr::{SignedInt, UnsignedInt}; | |
56 | use rustc_hir::def_id::DefId; | |
57 | use rustc_hir::{HirId, RangeEnd}; | |
58 | use rustc_middle::mir::interpret::ConstValue; | |
59 | use rustc_middle::mir::Field; | |
60 | use rustc_middle::ty::layout::IntegerExt; | |
61 | use rustc_middle::ty::{self, Const, Ty, TyCtxt}; | |
62 | use rustc_session::lint; | |
63 | use rustc_span::{Span, DUMMY_SP}; | |
64 | use rustc_target::abi::{Integer, Size, VariantIdx}; | |
65 | ||
66 | use smallvec::{smallvec, SmallVec}; | |
67 | use std::cmp::{self, max, min, Ordering}; | |
68 | use std::iter::{once, IntoIterator}; | |
69 | use std::ops::RangeInclusive; | |
70 | ||
71 | /// An inclusive interval, used for precise integer exhaustiveness checking. | |
72 | /// `IntRange`s always store a contiguous range. This means that values are | |
73 | /// encoded such that `0` encodes the minimum value for the integer, | |
74 | /// regardless of the signedness. | |
75 | /// For example, the pattern `-128..=127i8` is encoded as `0..=255`. | |
76 | /// This makes comparisons and arithmetic on interval endpoints much more | |
77 | /// straightforward. See `signed_bias` for details. | |
78 | /// | |
79 | /// `IntRange` is never used to encode an empty range or a "range" that wraps | |
80 | /// around the (offset) space: i.e., `range.lo <= range.hi`. | |
81 | #[derive(Clone, Debug, PartialEq, Eq)] | |
82 | pub(super) struct IntRange { | |
83 | range: RangeInclusive<u128>, | |
84 | } | |
85 | ||
86 | impl IntRange { | |
87 | #[inline] | |
88 | fn is_integral(ty: Ty<'_>) -> bool { | |
89 | matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_) | ty::Bool) | |
90 | } | |
91 | ||
92 | fn is_singleton(&self) -> bool { | |
93 | self.range.start() == self.range.end() | |
94 | } | |
95 | ||
96 | fn boundaries(&self) -> (u128, u128) { | |
97 | (*self.range.start(), *self.range.end()) | |
98 | } | |
99 | ||
100 | #[inline] | |
101 | fn integral_size_and_signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> Option<(Size, u128)> { | |
102 | match *ty.kind() { | |
103 | ty::Bool => Some((Size::from_bytes(1), 0)), | |
104 | ty::Char => Some((Size::from_bytes(4), 0)), | |
105 | ty::Int(ity) => { | |
106 | let size = Integer::from_attr(&tcx, SignedInt(ity)).size(); | |
107 | Some((size, 1u128 << (size.bits() as u128 - 1))) | |
108 | } | |
109 | ty::Uint(uty) => Some((Integer::from_attr(&tcx, UnsignedInt(uty)).size(), 0)), | |
110 | _ => None, | |
111 | } | |
112 | } | |
113 | ||
114 | #[inline] | |
115 | fn from_const<'tcx>( | |
116 | tcx: TyCtxt<'tcx>, | |
117 | param_env: ty::ParamEnv<'tcx>, | |
118 | value: &Const<'tcx>, | |
119 | ) -> Option<IntRange> { | |
120 | if let Some((target_size, bias)) = Self::integral_size_and_signed_bias(tcx, value.ty) { | |
121 | let ty = value.ty; | |
122 | let val = (|| { | |
123 | if let ty::ConstKind::Value(ConstValue::Scalar(scalar)) = value.val { | |
124 | // For this specific pattern we can skip a lot of effort and go | |
125 | // straight to the result, after doing a bit of checking. (We | |
126 | // could remove this branch and just fall through, which | |
127 | // is more general but much slower.) | |
128 | if let Ok(bits) = scalar.to_bits_or_ptr(target_size, &tcx) { | |
129 | return Some(bits); | |
130 | } | |
131 | } | |
132 | // This is a more general form of the previous case. | |
133 | value.try_eval_bits(tcx, param_env, ty) | |
134 | })()?; | |
135 | let val = val ^ bias; | |
136 | Some(IntRange { range: val..=val }) | |
137 | } else { | |
138 | None | |
139 | } | |
140 | } | |
141 | ||
142 | #[inline] | |
143 | fn from_range<'tcx>( | |
144 | tcx: TyCtxt<'tcx>, | |
145 | lo: u128, | |
146 | hi: u128, | |
147 | ty: Ty<'tcx>, | |
148 | end: &RangeEnd, | |
149 | ) -> Option<IntRange> { | |
150 | if Self::is_integral(ty) { | |
151 | // Perform a shift if the underlying types are signed, | |
152 | // which makes the interval arithmetic simpler. | |
153 | let bias = IntRange::signed_bias(tcx, ty); | |
154 | let (lo, hi) = (lo ^ bias, hi ^ bias); | |
155 | let offset = (*end == RangeEnd::Excluded) as u128; | |
156 | if lo > hi || (lo == hi && *end == RangeEnd::Excluded) { | |
157 | // This should have been caught earlier by E0030. | |
158 | bug!("malformed range pattern: {}..={}", lo, (hi - offset)); | |
159 | } | |
160 | Some(IntRange { range: lo..=(hi - offset) }) | |
161 | } else { | |
162 | None | |
163 | } | |
164 | } | |
165 | ||
166 | // The return value of `signed_bias` should be XORed with an endpoint to encode/decode it. | |
167 | fn signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> u128 { | |
168 | match *ty.kind() { | |
169 | ty::Int(ity) => { | |
170 | let bits = Integer::from_attr(&tcx, SignedInt(ity)).size().bits() as u128; | |
171 | 1u128 << (bits - 1) | |
172 | } | |
173 | _ => 0, | |
174 | } | |
175 | } | |
176 | ||
177 | fn is_subrange(&self, other: &Self) -> bool { | |
178 | other.range.start() <= self.range.start() && self.range.end() <= other.range.end() | |
179 | } | |
180 | ||
181 | fn intersection(&self, other: &Self) -> Option<Self> { | |
182 | let (lo, hi) = self.boundaries(); | |
183 | let (other_lo, other_hi) = other.boundaries(); | |
184 | if lo <= other_hi && other_lo <= hi { | |
185 | Some(IntRange { range: max(lo, other_lo)..=min(hi, other_hi) }) | |
186 | } else { | |
187 | None | |
188 | } | |
189 | } | |
190 | ||
191 | fn suspicious_intersection(&self, other: &Self) -> bool { | |
192 | // `false` in the following cases: | |
193 | // 1 ---- // 1 ---------- // 1 ---- // 1 ---- | |
194 | // 2 ---------- // 2 ---- // 2 ---- // 2 ---- | |
195 | // | |
196 | // The following are currently `false`, but could be `true` in the future (#64007): | |
197 | // 1 --------- // 1 --------- | |
198 | // 2 ---------- // 2 ---------- | |
199 | // | |
200 | // `true` in the following cases: | |
201 | // 1 ------- // 1 ------- | |
202 | // 2 -------- // 2 ------- | |
203 | let (lo, hi) = self.boundaries(); | |
204 | let (other_lo, other_hi) = other.boundaries(); | |
205 | (lo == other_hi || hi == other_lo) && !self.is_singleton() && !other.is_singleton() | |
206 | } | |
207 | ||
208 | fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> { | |
209 | let (lo, hi) = self.boundaries(); | |
210 | ||
211 | let bias = IntRange::signed_bias(tcx, ty); | |
212 | let (lo, hi) = (lo ^ bias, hi ^ bias); | |
213 | ||
214 | let env = ty::ParamEnv::empty().and(ty); | |
215 | let lo_const = ty::Const::from_bits(tcx, lo, env); | |
216 | let hi_const = ty::Const::from_bits(tcx, hi, env); | |
217 | ||
218 | let kind = if lo == hi { | |
219 | PatKind::Constant { value: lo_const } | |
220 | } else { | |
221 | PatKind::Range(PatRange { lo: lo_const, hi: hi_const, end: RangeEnd::Included }) | |
222 | }; | |
223 | ||
224 | Pat { ty, span: DUMMY_SP, kind: Box::new(kind) } | |
225 | } | |
226 | ||
227 | /// Lint on likely incorrect range patterns (#63987) | |
228 | pub(super) fn lint_overlapping_range_endpoints<'a, 'tcx: 'a>( | |
229 | &self, | |
230 | pcx: PatCtxt<'_, '_, 'tcx>, | |
231 | ctors: impl Iterator<Item = (&'a Constructor<'tcx>, Span)>, | |
232 | column_count: usize, | |
233 | hir_id: HirId, | |
234 | ) { | |
235 | if self.is_singleton() { | |
236 | return; | |
237 | } | |
238 | ||
239 | if column_count != 1 { | |
240 | // FIXME: for now, only check for overlapping ranges on simple range | |
241 | // patterns. Otherwise with the current logic the following is detected | |
242 | // as overlapping: | |
243 | // ``` | |
244 | // match (0u8, true) { | |
245 | // (0 ..= 125, false) => {} | |
246 | // (125 ..= 255, true) => {} | |
247 | // _ => {} | |
248 | // } | |
249 | // ``` | |
250 | return; | |
251 | } | |
252 | ||
253 | let overlaps: Vec<_> = ctors | |
254 | .filter_map(|(ctor, span)| Some((ctor.as_int_range()?, span))) | |
255 | .filter(|(range, _)| self.suspicious_intersection(range)) | |
256 | .map(|(range, span)| (self.intersection(&range).unwrap(), span)) | |
257 | .collect(); | |
258 | ||
259 | if !overlaps.is_empty() { | |
260 | pcx.cx.tcx.struct_span_lint_hir( | |
261 | lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, | |
262 | hir_id, | |
263 | pcx.span, | |
264 | |lint| { | |
265 | let mut err = lint.build("multiple patterns overlap on their endpoints"); | |
266 | for (int_range, span) in overlaps { | |
267 | err.span_label( | |
268 | span, | |
269 | &format!( | |
270 | "this range overlaps on `{}`...", | |
271 | int_range.to_pat(pcx.cx.tcx, pcx.ty) | |
272 | ), | |
273 | ); | |
274 | } | |
275 | err.span_label(pcx.span, "... with this range"); | |
276 | err.note("you likely meant to write mutually exclusive ranges"); | |
277 | err.emit(); | |
278 | }, | |
279 | ); | |
280 | } | |
281 | } | |
282 | ||
283 | /// See `Constructor::is_covered_by` | |
284 | fn is_covered_by(&self, other: &Self) -> bool { | |
285 | if self.intersection(other).is_some() { | |
286 | // Constructor splitting should ensure that all intersections we encounter are actually | |
287 | // inclusions. | |
288 | assert!(self.is_subrange(other)); | |
289 | true | |
290 | } else { | |
291 | false | |
292 | } | |
293 | } | |
294 | } | |
295 | ||
296 | /// Represents a border between 2 integers. Because the intervals spanning borders must be able to | |
297 | /// cover every integer, we need to be able to represent 2^128 + 1 such borders. | |
298 | #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] | |
299 | enum IntBorder { | |
300 | JustBefore(u128), | |
301 | AfterMax, | |
302 | } | |
303 | ||
304 | /// A range of integers that is partitioned into disjoint subranges. This does constructor | |
305 | /// splitting for integer ranges as explained at the top of the file. | |
306 | /// | |
307 | /// This is fed multiple ranges, and returns an output that covers the input, but is split so that | |
308 | /// the only intersections between an output range and a seen range are inclusions. No output range | |
309 | /// straddles the boundary of one of the inputs. | |
310 | /// | |
311 | /// The following input: | |
312 | /// ``` | |
313 | /// |-------------------------| // `self` | |
314 | /// |------| |----------| |----| | |
315 | /// |-------| |-------| | |
316 | /// ``` | |
317 | /// would be iterated over as follows: | |
318 | /// ``` | |
319 | /// ||---|--||-|---|---|---|--| | |
320 | /// ``` | |
321 | #[derive(Debug, Clone)] | |
322 | struct SplitIntRange { | |
323 | /// The range we are splitting | |
324 | range: IntRange, | |
325 | /// The borders of ranges we have seen. They are all contained within `range`. This is kept | |
326 | /// sorted. | |
327 | borders: Vec<IntBorder>, | |
328 | } | |
329 | ||
330 | impl SplitIntRange { | |
331 | fn new(r: IntRange) -> Self { | |
332 | SplitIntRange { range: r.clone(), borders: Vec::new() } | |
333 | } | |
334 | ||
335 | /// Internal use | |
336 | fn to_borders(r: IntRange) -> [IntBorder; 2] { | |
337 | use IntBorder::*; | |
338 | let (lo, hi) = r.boundaries(); | |
339 | let lo = JustBefore(lo); | |
340 | let hi = match hi.checked_add(1) { | |
341 | Some(m) => JustBefore(m), | |
342 | None => AfterMax, | |
343 | }; | |
344 | [lo, hi] | |
345 | } | |
346 | ||
347 | /// Add ranges relative to which we split. | |
348 | fn split(&mut self, ranges: impl Iterator<Item = IntRange>) { | |
349 | let this_range = &self.range; | |
350 | let included_ranges = ranges.filter_map(|r| this_range.intersection(&r)); | |
351 | let included_borders = included_ranges.flat_map(|r| { | |
352 | let borders = Self::to_borders(r); | |
353 | once(borders[0]).chain(once(borders[1])) | |
354 | }); | |
355 | self.borders.extend(included_borders); | |
356 | self.borders.sort_unstable(); | |
357 | } | |
358 | ||
359 | /// Iterate over the contained ranges. | |
360 | fn iter<'a>(&'a self) -> impl Iterator<Item = IntRange> + Captures<'a> { | |
361 | use IntBorder::*; | |
362 | ||
363 | let self_range = Self::to_borders(self.range.clone()); | |
364 | // Start with the start of the range. | |
365 | let mut prev_border = self_range[0]; | |
366 | self.borders | |
367 | .iter() | |
368 | .copied() | |
369 | // End with the end of the range. | |
370 | .chain(once(self_range[1])) | |
371 | // List pairs of adjacent borders. | |
372 | .map(move |border| { | |
373 | let ret = (prev_border, border); | |
374 | prev_border = border; | |
375 | ret | |
376 | }) | |
377 | // Skip duplicates. | |
378 | .filter(|(prev_border, border)| prev_border != border) | |
379 | // Finally, convert to ranges. | |
380 | .map(|(prev_border, border)| { | |
381 | let range = match (prev_border, border) { | |
382 | (JustBefore(n), JustBefore(m)) if n < m => n..=(m - 1), | |
383 | (JustBefore(n), AfterMax) => n..=u128::MAX, | |
384 | _ => unreachable!(), // Ruled out by the sorting and filtering we did | |
385 | }; | |
386 | IntRange { range } | |
387 | }) | |
388 | } | |
389 | } | |
390 | ||
391 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
392 | enum SliceKind { | |
393 | /// Patterns of length `n` (`[x, y]`). | |
394 | FixedLen(u64), | |
395 | /// Patterns using the `..` notation (`[x, .., y]`). | |
396 | /// Captures any array constructor of `length >= i + j`. | |
397 | /// In the case where `array_len` is `Some(_)`, | |
398 | /// this indicates that we only care about the first `i` and the last `j` values of the array, | |
399 | /// and everything in between is a wildcard `_`. | |
400 | VarLen(u64, u64), | |
401 | } | |
402 | ||
403 | impl SliceKind { | |
404 | fn arity(self) -> u64 { | |
405 | match self { | |
406 | FixedLen(length) => length, | |
407 | VarLen(prefix, suffix) => prefix + suffix, | |
408 | } | |
409 | } | |
410 | ||
411 | /// Whether this pattern includes patterns of length `other_len`. | |
412 | fn covers_length(self, other_len: u64) -> bool { | |
413 | match self { | |
414 | FixedLen(len) => len == other_len, | |
415 | VarLen(prefix, suffix) => prefix + suffix <= other_len, | |
416 | } | |
417 | } | |
418 | } | |
419 | ||
420 | /// A constructor for array and slice patterns. | |
421 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
422 | pub(super) struct Slice { | |
423 | /// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`. | |
424 | array_len: Option<u64>, | |
425 | /// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`. | |
426 | kind: SliceKind, | |
427 | } | |
428 | ||
429 | impl Slice { | |
430 | fn new(array_len: Option<u64>, kind: SliceKind) -> Self { | |
431 | let kind = match (array_len, kind) { | |
432 | // If the middle `..` is empty, we effectively have a fixed-length pattern. | |
433 | (Some(len), VarLen(prefix, suffix)) if prefix + suffix >= len => FixedLen(len), | |
434 | _ => kind, | |
435 | }; | |
436 | Slice { array_len, kind } | |
437 | } | |
438 | ||
439 | fn arity(self) -> u64 { | |
440 | self.kind.arity() | |
441 | } | |
442 | ||
443 | /// See `Constructor::is_covered_by` | |
444 | fn is_covered_by(self, other: Self) -> bool { | |
445 | other.kind.covers_length(self.arity()) | |
446 | } | |
447 | } | |
448 | ||
449 | /// This computes constructor splitting for variable-length slices, as explained at the top of the | |
450 | /// file. | |
451 | /// | |
452 | /// A slice pattern `[x, .., y]` behaves like the infinite or-pattern `[x, y] | [x, _, y] | [x, _, | |
453 | /// _, y] | ...`. The corresponding value constructors are fixed-length array constructors above a | |
454 | /// given minimum length. We obviously can't list this infinitude of constructors. Thankfully, | |
455 | /// it turns out that for each finite set of slice patterns, all sufficiently large array lengths | |
456 | /// are equivalent. | |
457 | /// | |
458 | /// Let's look at an example, where we are trying to split the last pattern: | |
459 | /// ``` | |
460 | /// match x { | |
461 | /// [true, true, ..] => {} | |
462 | /// [.., false, false] => {} | |
463 | /// [..] => {} | |
464 | /// } | |
465 | /// ``` | |
466 | /// Here are the results of specialization for the first few lengths: | |
467 | /// ``` | |
468 | /// // length 0 | |
469 | /// [] => {} | |
470 | /// // length 1 | |
471 | /// [_] => {} | |
472 | /// // length 2 | |
473 | /// [true, true] => {} | |
474 | /// [false, false] => {} | |
475 | /// [_, _] => {} | |
476 | /// // length 3 | |
477 | /// [true, true, _ ] => {} | |
478 | /// [_, false, false] => {} | |
479 | /// [_, _, _ ] => {} | |
480 | /// // length 4 | |
481 | /// [true, true, _, _ ] => {} | |
482 | /// [_, _, false, false] => {} | |
483 | /// [_, _, _, _ ] => {} | |
484 | /// // length 5 | |
485 | /// [true, true, _, _, _ ] => {} | |
486 | /// [_, _, _, false, false] => {} | |
487 | /// [_, _, _, _, _ ] => {} | |
488 | /// ``` | |
489 | /// | |
490 | /// If we went above length 5, we would simply be inserting more columns full of wildcards in the | |
491 | /// middle. This means that the set of witnesses for length `l >= 5` if equivalent to the set for | |
492 | /// any other `l' >= 5`: simply add or remove wildcards in the middle to convert between them. | |
493 | /// | |
494 | /// This applies to any set of slice patterns: there will be a length `L` above which all lengths | |
495 | /// behave the same. This is exactly what we need for constructor splitting. Therefore a | |
496 | /// variable-length slice can be split into a variable-length slice of minimal length `L`, and many | |
497 | /// fixed-length slices of lengths `< L`. | |
498 | /// | |
499 | /// For each variable-length pattern `p` with a prefix of length `plâ‚š` and suffix of length `slâ‚š`, | |
500 | /// only the first `plâ‚š` and the last `slâ‚š` elements are examined. Therefore, as long as `L` is | |
501 | /// positive (to avoid concerns about empty types), all elements after the maximum prefix length | |
502 | /// and before the maximum suffix length are not examined by any variable-length pattern, and | |
503 | /// therefore can be added/removed without affecting them - creating equivalent patterns from any | |
504 | /// sufficiently-large length. | |
505 | /// | |
506 | /// Of course, if fixed-length patterns exist, we must be sure that our length is large enough to | |
507 | /// miss them all, so we can pick `L = max(max(FIXED_LEN)+1, max(PREFIX_LEN) + max(SUFFIX_LEN))` | |
508 | /// | |
509 | /// `max_slice` below will be made to have arity `L`. | |
510 | #[derive(Debug)] | |
511 | struct SplitVarLenSlice { | |
512 | /// If the type is an array, this is its size. | |
513 | array_len: Option<u64>, | |
514 | /// The arity of the input slice. | |
515 | arity: u64, | |
516 | /// The smallest slice bigger than any slice seen. `max_slice.arity()` is the length `L` | |
517 | /// described above. | |
518 | max_slice: SliceKind, | |
519 | } | |
520 | ||
521 | impl SplitVarLenSlice { | |
522 | fn new(prefix: u64, suffix: u64, array_len: Option<u64>) -> Self { | |
523 | SplitVarLenSlice { array_len, arity: prefix + suffix, max_slice: VarLen(prefix, suffix) } | |
524 | } | |
525 | ||
526 | /// Pass a set of slices relative to which to split this one. | |
527 | fn split(&mut self, slices: impl Iterator<Item = SliceKind>) { | |
528 | let (max_prefix_len, max_suffix_len) = match &mut self.max_slice { | |
529 | VarLen(prefix, suffix) => (prefix, suffix), | |
530 | FixedLen(_) => return, // No need to split | |
531 | }; | |
532 | // We grow `self.max_slice` to be larger than all slices encountered, as described above. | |
533 | // For diagnostics, we keep the prefix and suffix lengths separate, but grow them so that | |
534 | // `L = max_prefix_len + max_suffix_len`. | |
535 | let mut max_fixed_len = 0; | |
536 | for slice in slices { | |
537 | match slice { | |
538 | FixedLen(len) => { | |
539 | max_fixed_len = cmp::max(max_fixed_len, len); | |
540 | } | |
541 | VarLen(prefix, suffix) => { | |
542 | *max_prefix_len = cmp::max(*max_prefix_len, prefix); | |
543 | *max_suffix_len = cmp::max(*max_suffix_len, suffix); | |
544 | } | |
545 | } | |
546 | } | |
547 | // We want `L = max(L, max_fixed_len + 1)`, modulo the fact that we keep prefix and | |
548 | // suffix separate. | |
549 | if max_fixed_len + 1 >= *max_prefix_len + *max_suffix_len { | |
550 | // The subtraction can't overflow thanks to the above check. | |
551 | // The new `max_prefix_len` is larger than its previous value. | |
552 | *max_prefix_len = max_fixed_len + 1 - *max_suffix_len; | |
553 | } | |
554 | ||
555 | // We cap the arity of `max_slice` at the array size. | |
556 | match self.array_len { | |
557 | Some(len) if self.max_slice.arity() >= len => self.max_slice = FixedLen(len), | |
558 | _ => {} | |
559 | } | |
560 | } | |
561 | ||
562 | /// Iterate over the partition of this slice. | |
563 | fn iter<'a>(&'a self) -> impl Iterator<Item = Slice> + Captures<'a> { | |
564 | let smaller_lengths = match self.array_len { | |
565 | // The only admissible fixed-length slice is one of the array size. Whether `max_slice` | |
566 | // is fixed-length or variable-length, it will be the only relevant slice to output | |
567 | // here. | |
568 | Some(_) => (0..0), // empty range | |
569 | // We cover all arities in the range `(self.arity..infinity)`. We split that range into | |
570 | // two: lengths smaller than `max_slice.arity()` are treated independently as | |
571 | // fixed-lengths slices, and lengths above are captured by `max_slice`. | |
572 | None => self.arity..self.max_slice.arity(), | |
573 | }; | |
574 | smaller_lengths | |
575 | .map(FixedLen) | |
576 | .chain(once(self.max_slice)) | |
577 | .map(move |kind| Slice::new(self.array_len, kind)) | |
578 | } | |
579 | } | |
580 | ||
581 | /// A value can be decomposed into a constructor applied to some fields. This struct represents | |
582 | /// the constructor. See also `Fields`. | |
583 | /// | |
584 | /// `pat_constructor` retrieves the constructor corresponding to a pattern. | |
585 | /// `specialize_constructor` returns the list of fields corresponding to a pattern, given a | |
586 | /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and | |
587 | /// `Fields`. | |
588 | #[derive(Clone, Debug, PartialEq)] | |
589 | pub(super) enum Constructor<'tcx> { | |
590 | /// The constructor for patterns that have a single constructor, like tuples, struct patterns | |
591 | /// and fixed-length arrays. | |
592 | Single, | |
593 | /// Enum variants. | |
594 | Variant(DefId), | |
595 | /// Ranges of integer literal values (`2`, `2..=5` or `2..5`). | |
596 | IntRange(IntRange), | |
597 | /// Ranges of floating-point literal values (`2.0..=5.2`). | |
598 | FloatRange(&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>, RangeEnd), | |
599 | /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately. | |
600 | Str(&'tcx ty::Const<'tcx>), | |
601 | /// Array and slice patterns. | |
602 | Slice(Slice), | |
603 | /// Constants that must not be matched structurally. They are treated as black | |
604 | /// boxes for the purposes of exhaustiveness: we must not inspect them, and they | |
605 | /// don't count towards making a match exhaustive. | |
606 | Opaque, | |
607 | /// Fake extra constructor for enums that aren't allowed to be matched exhaustively. Also used | |
608 | /// for those types for which we cannot list constructors explicitly, like `f64` and `str`. | |
609 | NonExhaustive, | |
610 | /// Stands for constructors that are not seen in the matrix, as explained in the documentation | |
611 | /// for [`SplitWildcard`]. | |
612 | Missing, | |
613 | /// Wildcard pattern. | |
614 | Wildcard, | |
615 | } | |
616 | ||
617 | impl<'tcx> Constructor<'tcx> { | |
618 | pub(super) fn is_wildcard(&self) -> bool { | |
619 | matches!(self, Wildcard) | |
620 | } | |
621 | ||
622 | fn as_int_range(&self) -> Option<&IntRange> { | |
623 | match self { | |
624 | IntRange(range) => Some(range), | |
625 | _ => None, | |
626 | } | |
627 | } | |
628 | ||
629 | fn as_slice(&self) -> Option<Slice> { | |
630 | match self { | |
631 | Slice(slice) => Some(*slice), | |
632 | _ => None, | |
633 | } | |
634 | } | |
635 | ||
636 | fn variant_index_for_adt(&self, adt: &'tcx ty::AdtDef) -> VariantIdx { | |
637 | match *self { | |
638 | Variant(id) => adt.variant_index_with_id(id), | |
639 | Single => { | |
640 | assert!(!adt.is_enum()); | |
641 | VariantIdx::new(0) | |
642 | } | |
643 | _ => bug!("bad constructor {:?} for adt {:?}", self, adt), | |
644 | } | |
645 | } | |
646 | ||
647 | /// Determines the constructor that the given pattern can be specialized to. | |
648 | pub(super) fn from_pat<'p>(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &'p Pat<'tcx>) -> Self { | |
649 | match pat.kind.as_ref() { | |
650 | PatKind::AscribeUserType { .. } => bug!(), // Handled by `expand_pattern` | |
651 | PatKind::Binding { .. } | PatKind::Wild => Wildcard, | |
652 | PatKind::Leaf { .. } | PatKind::Deref { .. } => Single, | |
653 | &PatKind::Variant { adt_def, variant_index, .. } => { | |
654 | Variant(adt_def.variants[variant_index].def_id) | |
655 | } | |
656 | PatKind::Constant { value } => { | |
657 | if let Some(int_range) = IntRange::from_const(cx.tcx, cx.param_env, value) { | |
658 | IntRange(int_range) | |
659 | } else { | |
660 | match pat.ty.kind() { | |
661 | ty::Float(_) => FloatRange(value, value, RangeEnd::Included), | |
662 | // In `expand_pattern`, we convert string literals to `&CONST` patterns with | |
663 | // `CONST` a pattern of type `str`. In truth this contains a constant of type | |
664 | // `&str`. | |
665 | ty::Str => Str(value), | |
666 | // All constants that can be structurally matched have already been expanded | |
667 | // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are | |
668 | // opaque. | |
669 | _ => Opaque, | |
670 | } | |
671 | } | |
672 | } | |
673 | &PatKind::Range(PatRange { lo, hi, end }) => { | |
674 | let ty = lo.ty; | |
675 | if let Some(int_range) = IntRange::from_range( | |
676 | cx.tcx, | |
677 | lo.eval_bits(cx.tcx, cx.param_env, lo.ty), | |
678 | hi.eval_bits(cx.tcx, cx.param_env, hi.ty), | |
679 | ty, | |
680 | &end, | |
681 | ) { | |
682 | IntRange(int_range) | |
683 | } else { | |
684 | FloatRange(lo, hi, end) | |
685 | } | |
686 | } | |
687 | PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => { | |
688 | let array_len = match pat.ty.kind() { | |
689 | ty::Array(_, length) => Some(length.eval_usize(cx.tcx, cx.param_env)), | |
690 | ty::Slice(_) => None, | |
691 | _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty), | |
692 | }; | |
693 | let prefix = prefix.len() as u64; | |
694 | let suffix = suffix.len() as u64; | |
695 | let kind = if slice.is_some() { | |
696 | VarLen(prefix, suffix) | |
697 | } else { | |
698 | FixedLen(prefix + suffix) | |
699 | }; | |
700 | Slice(Slice::new(array_len, kind)) | |
701 | } | |
702 | PatKind::Or { .. } => bug!("Or-pattern should have been expanded earlier on."), | |
703 | } | |
704 | } | |
705 | ||
706 | /// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of actual | |
707 | /// constructors (like variants, integers or fixed-sized slices). When specializing for these | |
708 | /// constructors, we want to be specialising for the actual underlying constructors. | |
709 | /// Naively, we would simply return the list of constructors they correspond to. We instead are | |
710 | /// more clever: if there are constructors that we know will behave the same wrt the current | |
711 | /// matrix, we keep them grouped. For example, all slices of a sufficiently large length | |
712 | /// will either be all useful or all non-useful with a given matrix. | |
713 | /// | |
714 | /// See the branches for details on how the splitting is done. | |
715 | /// | |
716 | /// This function may discard some irrelevant constructors if this preserves behavior and | |
717 | /// diagnostics. Eg. for the `_` case, we ignore the constructors already present in the | |
718 | /// matrix, unless all of them are. | |
719 | pub(super) fn split<'a>( | |
720 | &self, | |
721 | pcx: PatCtxt<'_, '_, 'tcx>, | |
722 | ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, | |
723 | ) -> SmallVec<[Self; 1]> | |
724 | where | |
725 | 'tcx: 'a, | |
726 | { | |
727 | debug!("Constructor::split({:#?})", self); | |
728 | ||
729 | match self { | |
730 | Wildcard => { | |
731 | let mut split_wildcard = SplitWildcard::new(pcx); | |
732 | split_wildcard.split(pcx, ctors); | |
733 | split_wildcard.into_ctors(pcx) | |
734 | } | |
735 | // Fast-track if the range is trivial. In particular, we don't do the overlapping | |
736 | // ranges check. | |
737 | IntRange(ctor_range) if !ctor_range.is_singleton() => { | |
738 | let mut split_range = SplitIntRange::new(ctor_range.clone()); | |
739 | let int_ranges = ctors.filter_map(|ctor| ctor.as_int_range()); | |
740 | split_range.split(int_ranges.cloned()); | |
741 | split_range.iter().map(IntRange).collect() | |
742 | } | |
743 | &Slice(Slice { kind: VarLen(self_prefix, self_suffix), array_len }) => { | |
744 | let mut split_self = SplitVarLenSlice::new(self_prefix, self_suffix, array_len); | |
745 | let slices = ctors.filter_map(|c| c.as_slice()).map(|s| s.kind); | |
746 | split_self.split(slices); | |
747 | split_self.iter().map(Slice).collect() | |
748 | } | |
749 | // Any other constructor can be used unchanged. | |
750 | _ => smallvec![self.clone()], | |
751 | } | |
752 | } | |
753 | ||
754 | /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`. | |
755 | /// For the simple cases, this is simply checking for equality. For the "grouped" constructors, | |
756 | /// this checks for inclusion. | |
757 | // We inline because this has a single call site in `Matrix::specialize_constructor`. | |
758 | #[inline] | |
759 | pub(super) fn is_covered_by<'p>(&self, pcx: PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool { | |
760 | // This must be kept in sync with `is_covered_by_any`. | |
761 | match (self, other) { | |
762 | // Wildcards cover anything | |
763 | (_, Wildcard) => true, | |
764 | // The missing ctors are not covered by anything in the matrix except wildcards. | |
765 | (Missing | Wildcard, _) => false, | |
766 | ||
767 | (Single, Single) => true, | |
768 | (Variant(self_id), Variant(other_id)) => self_id == other_id, | |
769 | ||
770 | (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range), | |
771 | ( | |
772 | FloatRange(self_from, self_to, self_end), | |
773 | FloatRange(other_from, other_to, other_end), | |
774 | ) => { | |
775 | match ( | |
776 | compare_const_vals(pcx.cx.tcx, self_to, other_to, pcx.cx.param_env, pcx.ty), | |
777 | compare_const_vals(pcx.cx.tcx, self_from, other_from, pcx.cx.param_env, pcx.ty), | |
778 | ) { | |
779 | (Some(to), Some(from)) => { | |
780 | (from == Ordering::Greater || from == Ordering::Equal) | |
781 | && (to == Ordering::Less | |
782 | || (other_end == self_end && to == Ordering::Equal)) | |
783 | } | |
784 | _ => false, | |
785 | } | |
786 | } | |
787 | (Str(self_val), Str(other_val)) => { | |
788 | // FIXME: there's probably a more direct way of comparing for equality | |
789 | match compare_const_vals(pcx.cx.tcx, self_val, other_val, pcx.cx.param_env, pcx.ty) | |
790 | { | |
791 | Some(comparison) => comparison == Ordering::Equal, | |
792 | None => false, | |
793 | } | |
794 | } | |
795 | (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice), | |
796 | ||
797 | // We are trying to inspect an opaque constant. Thus we skip the row. | |
798 | (Opaque, _) | (_, Opaque) => false, | |
799 | // Only a wildcard pattern can match the special extra constructor. | |
800 | (NonExhaustive, _) => false, | |
801 | ||
802 | _ => span_bug!( | |
803 | pcx.span, | |
804 | "trying to compare incompatible constructors {:?} and {:?}", | |
805 | self, | |
806 | other | |
807 | ), | |
808 | } | |
809 | } | |
810 | ||
811 | /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is | |
812 | /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is | |
813 | /// assumed to have been split from a wildcard. | |
814 | fn is_covered_by_any<'p>( | |
815 | &self, | |
816 | pcx: PatCtxt<'_, 'p, 'tcx>, | |
817 | used_ctors: &[Constructor<'tcx>], | |
818 | ) -> bool { | |
819 | if used_ctors.is_empty() { | |
820 | return false; | |
821 | } | |
822 | ||
823 | // This must be kept in sync with `is_covered_by`. | |
824 | match self { | |
825 | // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s. | |
826 | Single => !used_ctors.is_empty(), | |
827 | Variant(_) => used_ctors.iter().any(|c| c == self), | |
828 | IntRange(range) => used_ctors | |
829 | .iter() | |
830 | .filter_map(|c| c.as_int_range()) | |
831 | .any(|other| range.is_covered_by(other)), | |
832 | Slice(slice) => used_ctors | |
833 | .iter() | |
834 | .filter_map(|c| c.as_slice()) | |
835 | .any(|other| slice.is_covered_by(other)), | |
836 | // This constructor is never covered by anything else | |
837 | NonExhaustive => false, | |
838 | Str(..) | FloatRange(..) | Opaque | Missing | Wildcard => { | |
839 | span_bug!(pcx.span, "found unexpected ctor in all_ctors: {:?}", self) | |
840 | } | |
841 | } | |
842 | } | |
843 | } | |
844 | ||
845 | /// A wildcard constructor that we split relative to the constructors in the matrix, as explained | |
846 | /// at the top of the file. | |
847 | /// | |
848 | /// A constructor that is not present in the matrix rows will only be covered by the rows that have | |
849 | /// wildcards. Thus we can group all of those constructors together; we call them "missing | |
850 | /// constructors". Splitting a wildcard would therefore list all present constructors individually | |
851 | /// (or grouped if they are integers or slices), and then all missing constructors together as a | |
852 | /// group. | |
853 | /// | |
854 | /// However we can go further: since any constructor will match the wildcard rows, and having more | |
855 | /// rows can only reduce the amount of usefulness witnesses, we can skip the present constructors | |
856 | /// and only try the missing ones. | |
857 | /// This will not preserve the whole list of witnesses, but will preserve whether the list is empty | |
858 | /// or not. In fact this is quite natural from the point of view of diagnostics too. This is done | |
859 | /// in `to_ctors`: in some cases we only return `Missing`. | |
860 | #[derive(Debug)] | |
861 | pub(super) struct SplitWildcard<'tcx> { | |
862 | /// Constructors seen in the matrix. | |
863 | matrix_ctors: Vec<Constructor<'tcx>>, | |
864 | /// All the constructors for this type | |
865 | all_ctors: SmallVec<[Constructor<'tcx>; 1]>, | |
866 | } | |
867 | ||
868 | impl<'tcx> SplitWildcard<'tcx> { | |
869 | pub(super) fn new<'p>(pcx: PatCtxt<'_, 'p, 'tcx>) -> Self { | |
870 | debug!("SplitWildcard::new({:?})", pcx.ty); | |
871 | let cx = pcx.cx; | |
872 | let make_range = |start, end| { | |
873 | IntRange( | |
874 | // `unwrap()` is ok because we know the type is an integer. | |
875 | IntRange::from_range(cx.tcx, start, end, pcx.ty, &RangeEnd::Included).unwrap(), | |
876 | ) | |
877 | }; | |
878 | // This determines the set of all possible constructors for the type `pcx.ty`. For numbers, | |
879 | // arrays and slices we use ranges and variable-length slices when appropriate. | |
880 | // | |
881 | // If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that | |
882 | // are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the | |
883 | // returned list of constructors. | |
884 | // Invariant: this is empty if and only if the type is uninhabited (as determined by | |
885 | // `cx.is_uninhabited()`). | |
886 | let all_ctors = match pcx.ty.kind() { | |
887 | ty::Bool => smallvec![make_range(0, 1)], | |
888 | ty::Array(sub_ty, len) if len.try_eval_usize(cx.tcx, cx.param_env).is_some() => { | |
889 | let len = len.eval_usize(cx.tcx, cx.param_env); | |
890 | if len != 0 && cx.is_uninhabited(sub_ty) { | |
891 | smallvec![] | |
892 | } else { | |
893 | smallvec![Slice(Slice::new(Some(len), VarLen(0, 0)))] | |
894 | } | |
895 | } | |
896 | // Treat arrays of a constant but unknown length like slices. | |
897 | ty::Array(sub_ty, _) | ty::Slice(sub_ty) => { | |
898 | let kind = if cx.is_uninhabited(sub_ty) { FixedLen(0) } else { VarLen(0, 0) }; | |
899 | smallvec![Slice(Slice::new(None, kind))] | |
900 | } | |
901 | ty::Adt(def, substs) if def.is_enum() => { | |
902 | // If the enum is declared as `#[non_exhaustive]`, we treat it as if it had an | |
903 | // additional "unknown" constructor. | |
904 | // There is no point in enumerating all possible variants, because the user can't | |
905 | // actually match against them all themselves. So we always return only the fictitious | |
906 | // constructor. | |
907 | // E.g., in an example like: | |
908 | // | |
909 | // ``` | |
910 | // let err: io::ErrorKind = ...; | |
911 | // match err { | |
912 | // io::ErrorKind::NotFound => {}, | |
913 | // } | |
914 | // ``` | |
915 | // | |
916 | // we don't want to show every possible IO error, but instead have only `_` as the | |
917 | // witness. | |
918 | let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(pcx.ty); | |
919 | ||
920 | // If `exhaustive_patterns` is disabled and our scrutinee is an empty enum, we treat it | |
921 | // as though it had an "unknown" constructor to avoid exposing its emptiness. The | |
922 | // exception is if the pattern is at the top level, because we want empty matches to be | |
923 | // considered exhaustive. | |
924 | let is_secretly_empty = def.variants.is_empty() | |
925 | && !cx.tcx.features().exhaustive_patterns | |
926 | && !pcx.is_top_level; | |
927 | ||
928 | if is_secretly_empty || is_declared_nonexhaustive { | |
929 | smallvec![NonExhaustive] | |
930 | } else if cx.tcx.features().exhaustive_patterns { | |
931 | // If `exhaustive_patterns` is enabled, we exclude variants known to be | |
932 | // uninhabited. | |
933 | def.variants | |
934 | .iter() | |
935 | .filter(|v| { | |
936 | !v.uninhabited_from(cx.tcx, substs, def.adt_kind(), cx.param_env) | |
937 | .contains(cx.tcx, cx.module) | |
938 | }) | |
939 | .map(|v| Variant(v.def_id)) | |
940 | .collect() | |
941 | } else { | |
942 | def.variants.iter().map(|v| Variant(v.def_id)).collect() | |
943 | } | |
944 | } | |
945 | ty::Char => { | |
946 | smallvec![ | |
947 | // The valid Unicode Scalar Value ranges. | |
948 | make_range('\u{0000}' as u128, '\u{D7FF}' as u128), | |
949 | make_range('\u{E000}' as u128, '\u{10FFFF}' as u128), | |
950 | ] | |
951 | } | |
952 | ty::Int(_) | ty::Uint(_) | |
953 | if pcx.ty.is_ptr_sized_integral() | |
954 | && !cx.tcx.features().precise_pointer_size_matching => | |
955 | { | |
956 | // `usize`/`isize` are not allowed to be matched exhaustively unless the | |
957 | // `precise_pointer_size_matching` feature is enabled. So we treat those types like | |
958 | // `#[non_exhaustive]` enums by returning a special unmatcheable constructor. | |
959 | smallvec![NonExhaustive] | |
960 | } | |
961 | &ty::Int(ity) => { | |
962 | let bits = Integer::from_attr(&cx.tcx, SignedInt(ity)).size().bits() as u128; | |
963 | let min = 1u128 << (bits - 1); | |
964 | let max = min - 1; | |
965 | smallvec![make_range(min, max)] | |
966 | } | |
967 | &ty::Uint(uty) => { | |
968 | let size = Integer::from_attr(&cx.tcx, UnsignedInt(uty)).size(); | |
969 | let max = size.truncate(u128::MAX); | |
970 | smallvec![make_range(0, max)] | |
971 | } | |
972 | // If `exhaustive_patterns` is disabled and our scrutinee is the never type, we cannot | |
973 | // expose its emptiness. The exception is if the pattern is at the top level, because we | |
974 | // want empty matches to be considered exhaustive. | |
975 | ty::Never if !cx.tcx.features().exhaustive_patterns && !pcx.is_top_level => { | |
976 | smallvec![NonExhaustive] | |
977 | } | |
978 | ty::Never => smallvec![], | |
979 | _ if cx.is_uninhabited(pcx.ty) => smallvec![], | |
980 | ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => smallvec![Single], | |
981 | // This type is one for which we cannot list constructors, like `str` or `f64`. | |
982 | _ => smallvec![NonExhaustive], | |
983 | }; | |
984 | SplitWildcard { matrix_ctors: Vec::new(), all_ctors } | |
985 | } | |
986 | ||
987 | /// Pass a set of constructors relative to which to split this one. Don't call twice, it won't | |
988 | /// do what you want. | |
989 | pub(super) fn split<'a>( | |
990 | &mut self, | |
991 | pcx: PatCtxt<'_, '_, 'tcx>, | |
992 | ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, | |
993 | ) where | |
994 | 'tcx: 'a, | |
995 | { | |
996 | // Since `all_ctors` never contains wildcards, this won't recurse further. | |
997 | self.all_ctors = | |
998 | self.all_ctors.iter().flat_map(|ctor| ctor.split(pcx, ctors.clone())).collect(); | |
999 | self.matrix_ctors = ctors.filter(|c| !c.is_wildcard()).cloned().collect(); | |
1000 | } | |
1001 | ||
1002 | /// Whether there are any value constructors for this type that are not present in the matrix. | |
1003 | fn any_missing(&self, pcx: PatCtxt<'_, '_, 'tcx>) -> bool { | |
1004 | self.iter_missing(pcx).next().is_some() | |
1005 | } | |
1006 | ||
1007 | /// Iterate over the constructors for this type that are not present in the matrix. | |
1008 | pub(super) fn iter_missing<'a, 'p>( | |
1009 | &'a self, | |
1010 | pcx: PatCtxt<'a, 'p, 'tcx>, | |
1011 | ) -> impl Iterator<Item = &'a Constructor<'tcx>> + Captures<'p> { | |
1012 | self.all_ctors.iter().filter(move |ctor| !ctor.is_covered_by_any(pcx, &self.matrix_ctors)) | |
1013 | } | |
1014 | ||
1015 | /// Return the set of constructors resulting from splitting the wildcard. As explained at the | |
1016 | /// top of the file, if any constructors are missing we can ignore the present ones. | |
1017 | fn into_ctors(self, pcx: PatCtxt<'_, '_, 'tcx>) -> SmallVec<[Constructor<'tcx>; 1]> { | |
1018 | if self.any_missing(pcx) { | |
1019 | // Some constructors are missing, thus we can specialize with the special `Missing` | |
1020 | // constructor, which stands for those constructors that are not seen in the matrix, | |
1021 | // and matches the same rows as any of them (namely the wildcard rows). See the top of | |
1022 | // the file for details. | |
1023 | // However, when all constructors are missing we can also specialize with the full | |
1024 | // `Wildcard` constructor. The difference will depend on what we want in diagnostics. | |
1025 | ||
1026 | // If some constructors are missing, we typically want to report those constructors, | |
1027 | // e.g.: | |
1028 | // ``` | |
1029 | // enum Direction { N, S, E, W } | |
1030 | // let Direction::N = ...; | |
1031 | // ``` | |
1032 | // we can report 3 witnesses: `S`, `E`, and `W`. | |
1033 | // | |
1034 | // However, if the user didn't actually specify a constructor | |
1035 | // in this arm, e.g., in | |
1036 | // ``` | |
1037 | // let x: (Direction, Direction, bool) = ...; | |
1038 | // let (_, _, false) = x; | |
1039 | // ``` | |
1040 | // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>, | |
1041 | // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we | |
1042 | // prefer to report just a wildcard `_`. | |
1043 | // | |
1044 | // The exception is: if we are at the top-level, for example in an empty match, we | |
1045 | // sometimes prefer reporting the list of constructors instead of just `_`. | |
1046 | let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(pcx.ty); | |
1047 | let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing { | |
1048 | Missing | |
1049 | } else { | |
1050 | Wildcard | |
1051 | }; | |
1052 | return smallvec![ctor]; | |
1053 | } | |
1054 | ||
1055 | // All the constructors are present in the matrix, so we just go through them all. | |
1056 | self.all_ctors | |
1057 | } | |
1058 | } | |
1059 | ||
1060 | /// Some fields need to be explicitly hidden away in certain cases; see the comment above the | |
1061 | /// `Fields` struct. This struct represents such a potentially-hidden field. | |
1062 | #[derive(Debug, Copy, Clone)] | |
1063 | pub(super) enum FilteredField<'p, 'tcx> { | |
1064 | Kept(&'p Pat<'tcx>), | |
1065 | Hidden, | |
1066 | } | |
1067 | ||
1068 | impl<'p, 'tcx> FilteredField<'p, 'tcx> { | |
1069 | fn kept(self) -> Option<&'p Pat<'tcx>> { | |
1070 | match self { | |
1071 | FilteredField::Kept(p) => Some(p), | |
1072 | FilteredField::Hidden => None, | |
1073 | } | |
1074 | } | |
1075 | } | |
1076 | ||
1077 | /// A value can be decomposed into a constructor applied to some fields. This struct represents | |
1078 | /// those fields, generalized to allow patterns in each field. See also `Constructor`. | |
1079 | /// This is constructed from a constructor using [`Fields::wildcards()`]. | |
1080 | /// | |
1081 | /// If a private or `non_exhaustive` field is uninhabited, the code mustn't observe that it is | |
1082 | /// uninhabited. For that, we filter these fields out of the matrix. This is handled automatically | |
1083 | /// in `Fields`. This filtering is uncommon in practice, because uninhabited fields are rarely used, | |
1084 | /// so we avoid it when possible to preserve performance. | |
1085 | #[derive(Debug, Clone)] | |
1086 | pub(super) enum Fields<'p, 'tcx> { | |
1087 | /// Lists of patterns that don't contain any filtered fields. | |
1088 | /// `Slice` and `Vec` behave the same; the difference is only to avoid allocating and | |
1089 | /// triple-dereferences when possible. Frankly this is premature optimization, I (Nadrieril) | |
1090 | /// have not measured if it really made a difference. | |
1091 | Slice(&'p [Pat<'tcx>]), | |
1092 | Vec(SmallVec<[&'p Pat<'tcx>; 2]>), | |
1093 | /// Patterns where some of the fields need to be hidden. For all intents and purposes we only | |
1094 | /// care about the non-hidden fields. We need to keep the real field index for those fields; | |
1095 | /// we're morally storing a `Vec<(usize, &Pat)>` but what we do is more convenient. | |
1096 | /// `len` counts the number of non-hidden fields | |
1097 | Filtered { | |
1098 | fields: SmallVec<[FilteredField<'p, 'tcx>; 2]>, | |
1099 | len: usize, | |
1100 | }, | |
1101 | } | |
1102 | ||
1103 | impl<'p, 'tcx> Fields<'p, 'tcx> { | |
1104 | /// Internal use. Use `Fields::wildcards()` instead. | |
1105 | /// Must not be used if the pattern is a field of a struct/tuple/variant. | |
1106 | fn from_single_pattern(pat: &'p Pat<'tcx>) -> Self { | |
1107 | Fields::Slice(std::slice::from_ref(pat)) | |
1108 | } | |
1109 | ||
1110 | /// Convenience; internal use. | |
1111 | fn wildcards_from_tys( | |
1112 | cx: &MatchCheckCtxt<'p, 'tcx>, | |
1113 | tys: impl IntoIterator<Item = Ty<'tcx>>, | |
1114 | ) -> Self { | |
1115 | let wilds = tys.into_iter().map(Pat::wildcard_from_ty); | |
1116 | let pats = cx.pattern_arena.alloc_from_iter(wilds); | |
1117 | Fields::Slice(pats) | |
1118 | } | |
1119 | ||
1120 | /// Creates a new list of wildcard fields for a given constructor. | |
1121 | pub(super) fn wildcards(pcx: PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self { | |
1122 | let ty = pcx.ty; | |
1123 | let cx = pcx.cx; | |
1124 | let wildcard_from_ty = |ty| &*cx.pattern_arena.alloc(Pat::wildcard_from_ty(ty)); | |
1125 | ||
1126 | let ret = match constructor { | |
1127 | Single | Variant(_) => match ty.kind() { | |
1128 | ty::Tuple(ref fs) => { | |
1129 | Fields::wildcards_from_tys(cx, fs.into_iter().map(|ty| ty.expect_ty())) | |
1130 | } | |
1131 | ty::Ref(_, rty, _) => Fields::from_single_pattern(wildcard_from_ty(rty)), | |
1132 | ty::Adt(adt, substs) => { | |
1133 | if adt.is_box() { | |
1134 | // Use T as the sub pattern type of Box<T>. | |
1135 | Fields::from_single_pattern(wildcard_from_ty(substs.type_at(0))) | |
1136 | } else { | |
1137 | let variant = &adt.variants[constructor.variant_index_for_adt(adt)]; | |
1138 | // Whether we must not match the fields of this variant exhaustively. | |
1139 | let is_non_exhaustive = | |
1140 | variant.is_field_list_non_exhaustive() && !adt.did.is_local(); | |
1141 | let field_tys = variant.fields.iter().map(|field| field.ty(cx.tcx, substs)); | |
1142 | // In the following cases, we don't need to filter out any fields. This is | |
1143 | // the vast majority of real cases, since uninhabited fields are uncommon. | |
1144 | let has_no_hidden_fields = (adt.is_enum() && !is_non_exhaustive) | |
1145 | || !field_tys.clone().any(|ty| cx.is_uninhabited(ty)); | |
1146 | ||
1147 | if has_no_hidden_fields { | |
1148 | Fields::wildcards_from_tys(cx, field_tys) | |
1149 | } else { | |
1150 | let mut len = 0; | |
1151 | let fields = variant | |
1152 | .fields | |
1153 | .iter() | |
1154 | .map(|field| { | |
1155 | let ty = field.ty(cx.tcx, substs); | |
1156 | let is_visible = adt.is_enum() | |
1157 | || field.vis.is_accessible_from(cx.module, cx.tcx); | |
1158 | let is_uninhabited = cx.is_uninhabited(ty); | |
1159 | ||
1160 | // In the cases of either a `#[non_exhaustive]` field list | |
1161 | // or a non-public field, we hide uninhabited fields in | |
1162 | // order not to reveal the uninhabitedness of the whole | |
1163 | // variant. | |
1164 | if is_uninhabited && (!is_visible || is_non_exhaustive) { | |
1165 | FilteredField::Hidden | |
1166 | } else { | |
1167 | len += 1; | |
1168 | FilteredField::Kept(wildcard_from_ty(ty)) | |
1169 | } | |
1170 | }) | |
1171 | .collect(); | |
1172 | Fields::Filtered { fields, len } | |
1173 | } | |
1174 | } | |
1175 | } | |
1176 | _ => bug!("Unexpected type for `Single` constructor: {:?}", ty), | |
1177 | }, | |
1178 | Slice(slice) => match *ty.kind() { | |
1179 | ty::Slice(ty) | ty::Array(ty, _) => { | |
1180 | let arity = slice.arity(); | |
1181 | Fields::wildcards_from_tys(cx, (0..arity).map(|_| ty)) | |
1182 | } | |
1183 | _ => bug!("bad slice pattern {:?} {:?}", constructor, ty), | |
1184 | }, | |
1185 | Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing | |
1186 | | Wildcard => Fields::Slice(&[]), | |
1187 | }; | |
1188 | debug!("Fields::wildcards({:?}, {:?}) = {:#?}", constructor, ty, ret); | |
1189 | ret | |
1190 | } | |
1191 | ||
1192 | /// Apply a constructor to a list of patterns, yielding a new pattern. `self` | |
1193 | /// must have as many elements as this constructor's arity. | |
1194 | /// | |
1195 | /// This is roughly the inverse of `specialize_constructor`. | |
1196 | /// | |
1197 | /// Examples: | |
1198 | /// `ctor`: `Constructor::Single` | |
1199 | /// `ty`: `Foo(u32, u32, u32)` | |
1200 | /// `self`: `[10, 20, _]` | |
1201 | /// returns `Foo(10, 20, _)` | |
1202 | /// | |
1203 | /// `ctor`: `Constructor::Variant(Option::Some)` | |
1204 | /// `ty`: `Option<bool>` | |
1205 | /// `self`: `[false]` | |
1206 | /// returns `Some(false)` | |
1207 | pub(super) fn apply(self, pcx: PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Pat<'tcx> { | |
1208 | let subpatterns_and_indices = self.patterns_and_indices(); | |
1209 | let mut subpatterns = subpatterns_and_indices.iter().map(|&(_, p)| p).cloned(); | |
1210 | ||
1211 | let pat = match ctor { | |
1212 | Single | Variant(_) => match pcx.ty.kind() { | |
1213 | ty::Adt(..) | ty::Tuple(..) => { | |
1214 | // We want the real indices here. | |
1215 | let subpatterns = subpatterns_and_indices | |
1216 | .iter() | |
1217 | .map(|&(field, p)| FieldPat { field, pattern: p.clone() }) | |
1218 | .collect(); | |
1219 | ||
1220 | if let ty::Adt(adt, substs) = pcx.ty.kind() { | |
1221 | if adt.is_enum() { | |
1222 | PatKind::Variant { | |
1223 | adt_def: adt, | |
1224 | substs, | |
1225 | variant_index: ctor.variant_index_for_adt(adt), | |
1226 | subpatterns, | |
1227 | } | |
1228 | } else { | |
1229 | PatKind::Leaf { subpatterns } | |
1230 | } | |
1231 | } else { | |
1232 | PatKind::Leaf { subpatterns } | |
1233 | } | |
1234 | } | |
1235 | // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should | |
1236 | // be careful to reconstruct the correct constant pattern here. However a string | |
1237 | // literal pattern will never be reported as a non-exhaustiveness witness, so we | |
1238 | // can ignore this issue. | |
1239 | ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() }, | |
1240 | ty::Slice(_) | ty::Array(..) => bug!("bad slice pattern {:?} {:?}", ctor, pcx.ty), | |
1241 | _ => PatKind::Wild, | |
1242 | }, | |
1243 | Slice(slice) => match slice.kind { | |
1244 | FixedLen(_) => { | |
1245 | PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] } | |
1246 | } | |
1247 | VarLen(prefix, _) => { | |
1248 | let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix as usize).collect(); | |
1249 | if slice.array_len.is_some() { | |
1250 | // Improves diagnostics a bit: if the type is a known-size array, instead | |
1251 | // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`. | |
1252 | // This is incorrect if the size is not known, since `[_, ..]` captures | |
1253 | // arrays of lengths `>= 1` whereas `[..]` captures any length. | |
1254 | while !prefix.is_empty() && prefix.last().unwrap().is_wildcard() { | |
1255 | prefix.pop(); | |
1256 | } | |
1257 | } | |
1258 | let suffix: Vec<_> = if slice.array_len.is_some() { | |
1259 | // Same as above. | |
1260 | subpatterns.skip_while(Pat::is_wildcard).collect() | |
1261 | } else { | |
1262 | subpatterns.collect() | |
1263 | }; | |
1264 | let wild = Pat::wildcard_from_ty(pcx.ty); | |
1265 | PatKind::Slice { prefix, slice: Some(wild), suffix } | |
1266 | } | |
1267 | }, | |
1268 | &Str(value) => PatKind::Constant { value }, | |
1269 | &FloatRange(lo, hi, end) => PatKind::Range(PatRange { lo, hi, end }), | |
1270 | IntRange(range) => return range.to_pat(pcx.cx.tcx, pcx.ty), | |
1271 | NonExhaustive => PatKind::Wild, | |
1272 | Wildcard => return Pat::wildcard_from_ty(pcx.ty), | |
1273 | Opaque => bug!("we should not try to apply an opaque constructor"), | |
1274 | Missing => bug!( | |
1275 | "trying to apply the `Missing` constructor; this should have been done in `apply_constructors`" | |
1276 | ), | |
1277 | }; | |
1278 | ||
1279 | Pat { ty: pcx.ty, span: DUMMY_SP, kind: Box::new(pat) } | |
1280 | } | |
1281 | ||
1282 | /// Returns the number of patterns. This is the same as the arity of the constructor used to | |
1283 | /// construct `self`. | |
1284 | pub(super) fn len(&self) -> usize { | |
1285 | match self { | |
1286 | Fields::Slice(pats) => pats.len(), | |
1287 | Fields::Vec(pats) => pats.len(), | |
1288 | Fields::Filtered { len, .. } => *len, | |
1289 | } | |
1290 | } | |
1291 | ||
1292 | /// Returns the list of patterns along with the corresponding field indices. | |
1293 | fn patterns_and_indices(&self) -> SmallVec<[(Field, &'p Pat<'tcx>); 2]> { | |
1294 | match self { | |
1295 | Fields::Slice(pats) => { | |
1296 | pats.iter().enumerate().map(|(i, p)| (Field::new(i), p)).collect() | |
1297 | } | |
1298 | Fields::Vec(pats) => { | |
1299 | pats.iter().copied().enumerate().map(|(i, p)| (Field::new(i), p)).collect() | |
1300 | } | |
1301 | Fields::Filtered { fields, .. } => { | |
1302 | // Indices must be relative to the full list of patterns | |
1303 | fields | |
1304 | .iter() | |
1305 | .enumerate() | |
1306 | .filter_map(|(i, p)| Some((Field::new(i), p.kept()?))) | |
1307 | .collect() | |
1308 | } | |
1309 | } | |
1310 | } | |
1311 | ||
1312 | /// Returns the list of patterns. | |
1313 | pub(super) fn into_patterns(self) -> SmallVec<[&'p Pat<'tcx>; 2]> { | |
1314 | match self { | |
1315 | Fields::Slice(pats) => pats.iter().collect(), | |
1316 | Fields::Vec(pats) => pats, | |
1317 | Fields::Filtered { fields, .. } => fields.iter().filter_map(|p| p.kept()).collect(), | |
1318 | } | |
1319 | } | |
1320 | ||
1321 | /// Overrides some of the fields with the provided patterns. Exactly like | |
1322 | /// `replace_fields_indexed`, except that it takes `FieldPat`s as input. | |
1323 | fn replace_with_fieldpats( | |
1324 | &self, | |
1325 | new_pats: impl IntoIterator<Item = &'p FieldPat<'tcx>>, | |
1326 | ) -> Self { | |
1327 | self.replace_fields_indexed( | |
1328 | new_pats.into_iter().map(|pat| (pat.field.index(), &pat.pattern)), | |
1329 | ) | |
1330 | } | |
1331 | ||
1332 | /// Overrides some of the fields with the provided patterns. This is used when a pattern | |
1333 | /// defines some fields but not all, for example `Foo { field1: Some(_), .. }`: here we start | |
1334 | /// with a `Fields` that is just one wildcard per field of the `Foo` struct, and override the | |
1335 | /// entry corresponding to `field1` with the pattern `Some(_)`. This is also used for slice | |
1336 | /// patterns for the same reason. | |
1337 | fn replace_fields_indexed( | |
1338 | &self, | |
1339 | new_pats: impl IntoIterator<Item = (usize, &'p Pat<'tcx>)>, | |
1340 | ) -> Self { | |
1341 | let mut fields = self.clone(); | |
1342 | if let Fields::Slice(pats) = fields { | |
1343 | fields = Fields::Vec(pats.iter().collect()); | |
1344 | } | |
1345 | ||
1346 | match &mut fields { | |
1347 | Fields::Vec(pats) => { | |
1348 | for (i, pat) in new_pats { | |
1349 | pats[i] = pat | |
1350 | } | |
1351 | } | |
1352 | Fields::Filtered { fields, .. } => { | |
1353 | for (i, pat) in new_pats { | |
1354 | if let FilteredField::Kept(p) = &mut fields[i] { | |
1355 | *p = pat | |
1356 | } | |
1357 | } | |
1358 | } | |
1359 | Fields::Slice(_) => unreachable!(), | |
1360 | } | |
1361 | fields | |
1362 | } | |
1363 | ||
1364 | /// Replaces contained fields with the given list of patterns. There must be `len()` patterns | |
1365 | /// in `pats`. | |
1366 | pub(super) fn replace_fields( | |
1367 | &self, | |
1368 | cx: &MatchCheckCtxt<'p, 'tcx>, | |
1369 | pats: impl IntoIterator<Item = Pat<'tcx>>, | |
1370 | ) -> Self { | |
1371 | let pats: &[_] = cx.pattern_arena.alloc_from_iter(pats); | |
1372 | ||
1373 | match self { | |
1374 | Fields::Filtered { fields, len } => { | |
1375 | let mut pats = pats.iter(); | |
1376 | let mut fields = fields.clone(); | |
1377 | for f in &mut fields { | |
1378 | if let FilteredField::Kept(p) = f { | |
1379 | // We take one input pattern for each `Kept` field, in order. | |
1380 | *p = pats.next().unwrap(); | |
1381 | } | |
1382 | } | |
1383 | Fields::Filtered { fields, len: *len } | |
1384 | } | |
1385 | _ => Fields::Slice(pats), | |
1386 | } | |
1387 | } | |
1388 | ||
1389 | /// Replaces contained fields with the arguments of the given pattern. Only use on a pattern | |
1390 | /// that is compatible with the constructor used to build `self`. | |
1391 | /// This is meant to be used on the result of `Fields::wildcards()`. The idea is that | |
1392 | /// `wildcards` constructs a list of fields where all entries are wildcards, and the pattern | |
1393 | /// provided to this function fills some of the fields with non-wildcards. | |
1394 | /// In the following example `Fields::wildcards` would return `[_, _, _, _]`. If we call | |
1395 | /// `replace_with_pattern_arguments` on it with the pattern, the result will be `[Some(0), _, | |
1396 | /// _, _]`. | |
1397 | /// ```rust | |
1398 | /// let x: [Option<u8>; 4] = foo(); | |
1399 | /// match x { | |
1400 | /// [Some(0), ..] => {} | |
1401 | /// } | |
1402 | /// ``` | |
1403 | /// This is guaranteed to preserve the number of patterns in `self`. | |
1404 | pub(super) fn replace_with_pattern_arguments(&self, pat: &'p Pat<'tcx>) -> Self { | |
1405 | match pat.kind.as_ref() { | |
1406 | PatKind::Deref { subpattern } => { | |
1407 | assert_eq!(self.len(), 1); | |
1408 | Fields::from_single_pattern(subpattern) | |
1409 | } | |
1410 | PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => { | |
1411 | self.replace_with_fieldpats(subpatterns) | |
1412 | } | |
1413 | PatKind::Array { prefix, suffix, .. } | PatKind::Slice { prefix, suffix, .. } => { | |
1414 | // Number of subpatterns for the constructor | |
1415 | let ctor_arity = self.len(); | |
1416 | ||
1417 | // Replace the prefix and the suffix with the given patterns, leaving wildcards in | |
1418 | // the middle if there was a subslice pattern `..`. | |
1419 | let prefix = prefix.iter().enumerate(); | |
1420 | let suffix = | |
1421 | suffix.iter().enumerate().map(|(i, p)| (ctor_arity - suffix.len() + i, p)); | |
1422 | self.replace_fields_indexed(prefix.chain(suffix)) | |
1423 | } | |
1424 | _ => self.clone(), | |
1425 | } | |
1426 | } | |
1427 | } |