]>
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; | |
c295e0f8 | 49 | use super::usefulness::{MatchCheckCtxt, PatCtxt}; |
fc512014 XL |
50 | |
51 | use rustc_data_structures::captures::Captures; | |
52 | use rustc_index::vec::Idx; | |
53 | ||
fc512014 | 54 | use rustc_hir::{HirId, RangeEnd}; |
fc512014 | 55 | use rustc_middle::mir::Field; |
17df50a5 | 56 | use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange}; |
fc512014 | 57 | use rustc_middle::ty::layout::IntegerExt; |
c295e0f8 XL |
58 | use rustc_middle::ty::{self, Const, Ty, TyCtxt, VariantDef}; |
59 | use rustc_middle::{middle::stability::EvalResult, mir::interpret::ConstValue}; | |
fc512014 XL |
60 | use rustc_session::lint; |
61 | use rustc_span::{Span, DUMMY_SP}; | |
62 | use rustc_target::abi::{Integer, Size, VariantIdx}; | |
63 | ||
64 | use smallvec::{smallvec, SmallVec}; | |
c295e0f8 | 65 | use std::cell::Cell; |
fc512014 | 66 | use std::cmp::{self, max, min, Ordering}; |
c295e0f8 | 67 | use std::fmt; |
fc512014 XL |
68 | use std::iter::{once, IntoIterator}; |
69 | use std::ops::RangeInclusive; | |
70 | ||
c295e0f8 XL |
71 | /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. |
72 | fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> { | |
73 | fn expand<'p, 'tcx>(pat: &'p Pat<'tcx>, vec: &mut Vec<&'p Pat<'tcx>>) { | |
74 | if let PatKind::Or { pats } = pat.kind.as_ref() { | |
75 | for pat in pats { | |
76 | expand(pat, vec); | |
77 | } | |
78 | } else { | |
79 | vec.push(pat) | |
80 | } | |
81 | } | |
82 | ||
83 | let mut pats = Vec::new(); | |
84 | expand(pat, &mut pats); | |
85 | pats | |
86 | } | |
87 | ||
fc512014 XL |
88 | /// An inclusive interval, used for precise integer exhaustiveness checking. |
89 | /// `IntRange`s always store a contiguous range. This means that values are | |
90 | /// encoded such that `0` encodes the minimum value for the integer, | |
91 | /// regardless of the signedness. | |
92 | /// For example, the pattern `-128..=127i8` is encoded as `0..=255`. | |
93 | /// This makes comparisons and arithmetic on interval endpoints much more | |
94 | /// straightforward. See `signed_bias` for details. | |
95 | /// | |
96 | /// `IntRange` is never used to encode an empty range or a "range" that wraps | |
97 | /// around the (offset) space: i.e., `range.lo <= range.hi`. | |
c295e0f8 | 98 | #[derive(Clone, PartialEq, Eq)] |
fc512014 XL |
99 | pub(super) struct IntRange { |
100 | range: RangeInclusive<u128>, | |
c295e0f8 XL |
101 | /// Keeps the bias used for encoding the range. It depends on the type of the range and |
102 | /// possibly the pointer size of the current architecture. The algorithm ensures we never | |
103 | /// compare `IntRange`s with different types/architectures. | |
104 | bias: u128, | |
fc512014 XL |
105 | } |
106 | ||
107 | impl IntRange { | |
108 | #[inline] | |
109 | fn is_integral(ty: Ty<'_>) -> bool { | |
110 | matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_) | ty::Bool) | |
111 | } | |
112 | ||
113 | fn is_singleton(&self) -> bool { | |
114 | self.range.start() == self.range.end() | |
115 | } | |
116 | ||
117 | fn boundaries(&self) -> (u128, u128) { | |
118 | (*self.range.start(), *self.range.end()) | |
119 | } | |
120 | ||
121 | #[inline] | |
122 | fn integral_size_and_signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> Option<(Size, u128)> { | |
123 | match *ty.kind() { | |
124 | ty::Bool => Some((Size::from_bytes(1), 0)), | |
125 | ty::Char => Some((Size::from_bytes(4), 0)), | |
126 | ty::Int(ity) => { | |
5869c6ff | 127 | let size = Integer::from_int_ty(&tcx, ity).size(); |
fc512014 XL |
128 | Some((size, 1u128 << (size.bits() as u128 - 1))) |
129 | } | |
5869c6ff | 130 | ty::Uint(uty) => Some((Integer::from_uint_ty(&tcx, uty).size(), 0)), |
fc512014 XL |
131 | _ => None, |
132 | } | |
133 | } | |
134 | ||
135 | #[inline] | |
136 | fn from_const<'tcx>( | |
137 | tcx: TyCtxt<'tcx>, | |
138 | param_env: ty::ParamEnv<'tcx>, | |
139 | value: &Const<'tcx>, | |
140 | ) -> Option<IntRange> { | |
141 | if let Some((target_size, bias)) = Self::integral_size_and_signed_bias(tcx, value.ty) { | |
142 | let ty = value.ty; | |
143 | let val = (|| { | |
144 | if let ty::ConstKind::Value(ConstValue::Scalar(scalar)) = value.val { | |
145 | // For this specific pattern we can skip a lot of effort and go | |
146 | // straight to the result, after doing a bit of checking. (We | |
147 | // could remove this branch and just fall through, which | |
148 | // is more general but much slower.) | |
136023e0 | 149 | if let Ok(bits) = scalar.to_bits_or_ptr_internal(target_size) { |
fc512014 XL |
150 | return Some(bits); |
151 | } | |
152 | } | |
153 | // This is a more general form of the previous case. | |
154 | value.try_eval_bits(tcx, param_env, ty) | |
155 | })()?; | |
156 | let val = val ^ bias; | |
c295e0f8 | 157 | Some(IntRange { range: val..=val, bias }) |
fc512014 XL |
158 | } else { |
159 | None | |
160 | } | |
161 | } | |
162 | ||
163 | #[inline] | |
164 | fn from_range<'tcx>( | |
165 | tcx: TyCtxt<'tcx>, | |
166 | lo: u128, | |
167 | hi: u128, | |
168 | ty: Ty<'tcx>, | |
169 | end: &RangeEnd, | |
170 | ) -> Option<IntRange> { | |
171 | if Self::is_integral(ty) { | |
172 | // Perform a shift if the underlying types are signed, | |
173 | // which makes the interval arithmetic simpler. | |
174 | let bias = IntRange::signed_bias(tcx, ty); | |
175 | let (lo, hi) = (lo ^ bias, hi ^ bias); | |
176 | let offset = (*end == RangeEnd::Excluded) as u128; | |
177 | if lo > hi || (lo == hi && *end == RangeEnd::Excluded) { | |
178 | // This should have been caught earlier by E0030. | |
179 | bug!("malformed range pattern: {}..={}", lo, (hi - offset)); | |
180 | } | |
c295e0f8 | 181 | Some(IntRange { range: lo..=(hi - offset), bias }) |
fc512014 XL |
182 | } else { |
183 | None | |
184 | } | |
185 | } | |
186 | ||
187 | // The return value of `signed_bias` should be XORed with an endpoint to encode/decode it. | |
188 | fn signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> u128 { | |
189 | match *ty.kind() { | |
190 | ty::Int(ity) => { | |
5869c6ff | 191 | let bits = Integer::from_int_ty(&tcx, ity).size().bits() as u128; |
fc512014 XL |
192 | 1u128 << (bits - 1) |
193 | } | |
194 | _ => 0, | |
195 | } | |
196 | } | |
197 | ||
198 | fn is_subrange(&self, other: &Self) -> bool { | |
199 | other.range.start() <= self.range.start() && self.range.end() <= other.range.end() | |
200 | } | |
201 | ||
202 | fn intersection(&self, other: &Self) -> Option<Self> { | |
203 | let (lo, hi) = self.boundaries(); | |
204 | let (other_lo, other_hi) = other.boundaries(); | |
205 | if lo <= other_hi && other_lo <= hi { | |
c295e0f8 | 206 | Some(IntRange { range: max(lo, other_lo)..=min(hi, other_hi), bias: self.bias }) |
fc512014 XL |
207 | } else { |
208 | None | |
209 | } | |
210 | } | |
211 | ||
212 | fn suspicious_intersection(&self, other: &Self) -> bool { | |
213 | // `false` in the following cases: | |
214 | // 1 ---- // 1 ---------- // 1 ---- // 1 ---- | |
215 | // 2 ---------- // 2 ---- // 2 ---- // 2 ---- | |
216 | // | |
217 | // The following are currently `false`, but could be `true` in the future (#64007): | |
218 | // 1 --------- // 1 --------- | |
219 | // 2 ---------- // 2 ---------- | |
220 | // | |
221 | // `true` in the following cases: | |
222 | // 1 ------- // 1 ------- | |
223 | // 2 -------- // 2 ------- | |
224 | let (lo, hi) = self.boundaries(); | |
225 | let (other_lo, other_hi) = other.boundaries(); | |
226 | (lo == other_hi || hi == other_lo) && !self.is_singleton() && !other.is_singleton() | |
227 | } | |
228 | ||
c295e0f8 | 229 | /// Only used for displaying the range properly. |
fc512014 XL |
230 | fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> { |
231 | let (lo, hi) = self.boundaries(); | |
232 | ||
c295e0f8 | 233 | let bias = self.bias; |
fc512014 XL |
234 | let (lo, hi) = (lo ^ bias, hi ^ bias); |
235 | ||
236 | let env = ty::ParamEnv::empty().and(ty); | |
237 | let lo_const = ty::Const::from_bits(tcx, lo, env); | |
238 | let hi_const = ty::Const::from_bits(tcx, hi, env); | |
239 | ||
240 | let kind = if lo == hi { | |
241 | PatKind::Constant { value: lo_const } | |
242 | } else { | |
243 | PatKind::Range(PatRange { lo: lo_const, hi: hi_const, end: RangeEnd::Included }) | |
244 | }; | |
245 | ||
246 | Pat { ty, span: DUMMY_SP, kind: Box::new(kind) } | |
247 | } | |
248 | ||
249 | /// Lint on likely incorrect range patterns (#63987) | |
c295e0f8 | 250 | pub(super) fn lint_overlapping_range_endpoints<'a, 'p: 'a, 'tcx: 'a>( |
fc512014 | 251 | &self, |
c295e0f8 XL |
252 | pcx: PatCtxt<'_, 'p, 'tcx>, |
253 | pats: impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>>, | |
fc512014 XL |
254 | column_count: usize, |
255 | hir_id: HirId, | |
256 | ) { | |
257 | if self.is_singleton() { | |
258 | return; | |
259 | } | |
260 | ||
261 | if column_count != 1 { | |
262 | // FIXME: for now, only check for overlapping ranges on simple range | |
263 | // patterns. Otherwise with the current logic the following is detected | |
264 | // as overlapping: | |
265 | // ``` | |
266 | // match (0u8, true) { | |
267 | // (0 ..= 125, false) => {} | |
268 | // (125 ..= 255, true) => {} | |
269 | // _ => {} | |
270 | // } | |
271 | // ``` | |
272 | return; | |
273 | } | |
274 | ||
c295e0f8 XL |
275 | let overlaps: Vec<_> = pats |
276 | .filter_map(|pat| Some((pat.ctor().as_int_range()?, pat.span()))) | |
fc512014 XL |
277 | .filter(|(range, _)| self.suspicious_intersection(range)) |
278 | .map(|(range, span)| (self.intersection(&range).unwrap(), span)) | |
279 | .collect(); | |
280 | ||
281 | if !overlaps.is_empty() { | |
282 | pcx.cx.tcx.struct_span_lint_hir( | |
283 | lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, | |
284 | hir_id, | |
285 | pcx.span, | |
286 | |lint| { | |
287 | let mut err = lint.build("multiple patterns overlap on their endpoints"); | |
288 | for (int_range, span) in overlaps { | |
289 | err.span_label( | |
290 | span, | |
291 | &format!( | |
292 | "this range overlaps on `{}`...", | |
293 | int_range.to_pat(pcx.cx.tcx, pcx.ty) | |
294 | ), | |
295 | ); | |
296 | } | |
297 | err.span_label(pcx.span, "... with this range"); | |
298 | err.note("you likely meant to write mutually exclusive ranges"); | |
299 | err.emit(); | |
300 | }, | |
301 | ); | |
302 | } | |
303 | } | |
304 | ||
305 | /// See `Constructor::is_covered_by` | |
306 | fn is_covered_by(&self, other: &Self) -> bool { | |
307 | if self.intersection(other).is_some() { | |
308 | // Constructor splitting should ensure that all intersections we encounter are actually | |
309 | // inclusions. | |
310 | assert!(self.is_subrange(other)); | |
311 | true | |
312 | } else { | |
313 | false | |
314 | } | |
315 | } | |
316 | } | |
317 | ||
c295e0f8 XL |
318 | /// Note: this is often not what we want: e.g. `false` is converted into the range `0..=0` and |
319 | /// would be displayed as such. To render properly, convert to a pattern first. | |
320 | impl fmt::Debug for IntRange { | |
321 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
322 | let (lo, hi) = self.boundaries(); | |
323 | let bias = self.bias; | |
324 | let (lo, hi) = (lo ^ bias, hi ^ bias); | |
325 | write!(f, "{}", lo)?; | |
326 | write!(f, "{}", RangeEnd::Included)?; | |
327 | write!(f, "{}", hi) | |
328 | } | |
329 | } | |
330 | ||
fc512014 XL |
331 | /// Represents a border between 2 integers. Because the intervals spanning borders must be able to |
332 | /// cover every integer, we need to be able to represent 2^128 + 1 such borders. | |
333 | #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] | |
334 | enum IntBorder { | |
335 | JustBefore(u128), | |
336 | AfterMax, | |
337 | } | |
338 | ||
339 | /// A range of integers that is partitioned into disjoint subranges. This does constructor | |
340 | /// splitting for integer ranges as explained at the top of the file. | |
341 | /// | |
342 | /// This is fed multiple ranges, and returns an output that covers the input, but is split so that | |
343 | /// the only intersections between an output range and a seen range are inclusions. No output range | |
344 | /// straddles the boundary of one of the inputs. | |
345 | /// | |
346 | /// The following input: | |
347 | /// ``` | |
348 | /// |-------------------------| // `self` | |
349 | /// |------| |----------| |----| | |
350 | /// |-------| |-------| | |
351 | /// ``` | |
352 | /// would be iterated over as follows: | |
353 | /// ``` | |
354 | /// ||---|--||-|---|---|---|--| | |
355 | /// ``` | |
356 | #[derive(Debug, Clone)] | |
357 | struct SplitIntRange { | |
358 | /// The range we are splitting | |
359 | range: IntRange, | |
360 | /// The borders of ranges we have seen. They are all contained within `range`. This is kept | |
361 | /// sorted. | |
362 | borders: Vec<IntBorder>, | |
363 | } | |
364 | ||
365 | impl SplitIntRange { | |
5869c6ff XL |
366 | fn new(range: IntRange) -> Self { |
367 | SplitIntRange { range, borders: Vec::new() } | |
fc512014 XL |
368 | } |
369 | ||
370 | /// Internal use | |
371 | fn to_borders(r: IntRange) -> [IntBorder; 2] { | |
372 | use IntBorder::*; | |
373 | let (lo, hi) = r.boundaries(); | |
374 | let lo = JustBefore(lo); | |
375 | let hi = match hi.checked_add(1) { | |
376 | Some(m) => JustBefore(m), | |
377 | None => AfterMax, | |
378 | }; | |
379 | [lo, hi] | |
380 | } | |
381 | ||
382 | /// Add ranges relative to which we split. | |
383 | fn split(&mut self, ranges: impl Iterator<Item = IntRange>) { | |
384 | let this_range = &self.range; | |
385 | let included_ranges = ranges.filter_map(|r| this_range.intersection(&r)); | |
386 | let included_borders = included_ranges.flat_map(|r| { | |
387 | let borders = Self::to_borders(r); | |
388 | once(borders[0]).chain(once(borders[1])) | |
389 | }); | |
390 | self.borders.extend(included_borders); | |
391 | self.borders.sort_unstable(); | |
392 | } | |
393 | ||
394 | /// Iterate over the contained ranges. | |
395 | fn iter<'a>(&'a self) -> impl Iterator<Item = IntRange> + Captures<'a> { | |
396 | use IntBorder::*; | |
397 | ||
398 | let self_range = Self::to_borders(self.range.clone()); | |
399 | // Start with the start of the range. | |
400 | let mut prev_border = self_range[0]; | |
401 | self.borders | |
402 | .iter() | |
403 | .copied() | |
404 | // End with the end of the range. | |
405 | .chain(once(self_range[1])) | |
406 | // List pairs of adjacent borders. | |
407 | .map(move |border| { | |
408 | let ret = (prev_border, border); | |
409 | prev_border = border; | |
410 | ret | |
411 | }) | |
412 | // Skip duplicates. | |
413 | .filter(|(prev_border, border)| prev_border != border) | |
414 | // Finally, convert to ranges. | |
c295e0f8 | 415 | .map(move |(prev_border, border)| { |
fc512014 XL |
416 | let range = match (prev_border, border) { |
417 | (JustBefore(n), JustBefore(m)) if n < m => n..=(m - 1), | |
418 | (JustBefore(n), AfterMax) => n..=u128::MAX, | |
419 | _ => unreachable!(), // Ruled out by the sorting and filtering we did | |
420 | }; | |
c295e0f8 | 421 | IntRange { range, bias: self.range.bias } |
fc512014 XL |
422 | }) |
423 | } | |
424 | } | |
425 | ||
426 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
427 | enum SliceKind { | |
428 | /// Patterns of length `n` (`[x, y]`). | |
c295e0f8 | 429 | FixedLen(usize), |
fc512014 XL |
430 | /// Patterns using the `..` notation (`[x, .., y]`). |
431 | /// Captures any array constructor of `length >= i + j`. | |
432 | /// In the case where `array_len` is `Some(_)`, | |
433 | /// this indicates that we only care about the first `i` and the last `j` values of the array, | |
434 | /// and everything in between is a wildcard `_`. | |
c295e0f8 | 435 | VarLen(usize, usize), |
fc512014 XL |
436 | } |
437 | ||
438 | impl SliceKind { | |
c295e0f8 | 439 | fn arity(self) -> usize { |
fc512014 XL |
440 | match self { |
441 | FixedLen(length) => length, | |
442 | VarLen(prefix, suffix) => prefix + suffix, | |
443 | } | |
444 | } | |
445 | ||
446 | /// Whether this pattern includes patterns of length `other_len`. | |
c295e0f8 | 447 | fn covers_length(self, other_len: usize) -> bool { |
fc512014 XL |
448 | match self { |
449 | FixedLen(len) => len == other_len, | |
450 | VarLen(prefix, suffix) => prefix + suffix <= other_len, | |
451 | } | |
452 | } | |
453 | } | |
454 | ||
455 | /// A constructor for array and slice patterns. | |
456 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
457 | pub(super) struct Slice { | |
458 | /// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`. | |
c295e0f8 | 459 | array_len: Option<usize>, |
fc512014 XL |
460 | /// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`. |
461 | kind: SliceKind, | |
462 | } | |
463 | ||
464 | impl Slice { | |
c295e0f8 | 465 | fn new(array_len: Option<usize>, kind: SliceKind) -> Self { |
fc512014 XL |
466 | let kind = match (array_len, kind) { |
467 | // If the middle `..` is empty, we effectively have a fixed-length pattern. | |
468 | (Some(len), VarLen(prefix, suffix)) if prefix + suffix >= len => FixedLen(len), | |
469 | _ => kind, | |
470 | }; | |
471 | Slice { array_len, kind } | |
472 | } | |
473 | ||
c295e0f8 | 474 | fn arity(self) -> usize { |
fc512014 XL |
475 | self.kind.arity() |
476 | } | |
477 | ||
478 | /// See `Constructor::is_covered_by` | |
479 | fn is_covered_by(self, other: Self) -> bool { | |
480 | other.kind.covers_length(self.arity()) | |
481 | } | |
482 | } | |
483 | ||
484 | /// This computes constructor splitting for variable-length slices, as explained at the top of the | |
485 | /// file. | |
486 | /// | |
487 | /// A slice pattern `[x, .., y]` behaves like the infinite or-pattern `[x, y] | [x, _, y] | [x, _, | |
488 | /// _, y] | ...`. The corresponding value constructors are fixed-length array constructors above a | |
489 | /// given minimum length. We obviously can't list this infinitude of constructors. Thankfully, | |
490 | /// it turns out that for each finite set of slice patterns, all sufficiently large array lengths | |
491 | /// are equivalent. | |
492 | /// | |
493 | /// Let's look at an example, where we are trying to split the last pattern: | |
494 | /// ``` | |
495 | /// match x { | |
496 | /// [true, true, ..] => {} | |
497 | /// [.., false, false] => {} | |
498 | /// [..] => {} | |
499 | /// } | |
500 | /// ``` | |
501 | /// Here are the results of specialization for the first few lengths: | |
502 | /// ``` | |
503 | /// // length 0 | |
504 | /// [] => {} | |
505 | /// // length 1 | |
506 | /// [_] => {} | |
507 | /// // length 2 | |
508 | /// [true, true] => {} | |
509 | /// [false, false] => {} | |
510 | /// [_, _] => {} | |
511 | /// // length 3 | |
512 | /// [true, true, _ ] => {} | |
513 | /// [_, false, false] => {} | |
514 | /// [_, _, _ ] => {} | |
515 | /// // length 4 | |
516 | /// [true, true, _, _ ] => {} | |
517 | /// [_, _, false, false] => {} | |
518 | /// [_, _, _, _ ] => {} | |
519 | /// // length 5 | |
520 | /// [true, true, _, _, _ ] => {} | |
521 | /// [_, _, _, false, false] => {} | |
522 | /// [_, _, _, _, _ ] => {} | |
523 | /// ``` | |
524 | /// | |
525 | /// If we went above length 5, we would simply be inserting more columns full of wildcards in the | |
526 | /// middle. This means that the set of witnesses for length `l >= 5` if equivalent to the set for | |
527 | /// any other `l' >= 5`: simply add or remove wildcards in the middle to convert between them. | |
528 | /// | |
529 | /// This applies to any set of slice patterns: there will be a length `L` above which all lengths | |
530 | /// behave the same. This is exactly what we need for constructor splitting. Therefore a | |
531 | /// variable-length slice can be split into a variable-length slice of minimal length `L`, and many | |
532 | /// fixed-length slices of lengths `< L`. | |
533 | /// | |
534 | /// For each variable-length pattern `p` with a prefix of length `plâ‚š` and suffix of length `slâ‚š`, | |
535 | /// only the first `plâ‚š` and the last `slâ‚š` elements are examined. Therefore, as long as `L` is | |
536 | /// positive (to avoid concerns about empty types), all elements after the maximum prefix length | |
537 | /// and before the maximum suffix length are not examined by any variable-length pattern, and | |
538 | /// therefore can be added/removed without affecting them - creating equivalent patterns from any | |
539 | /// sufficiently-large length. | |
540 | /// | |
541 | /// Of course, if fixed-length patterns exist, we must be sure that our length is large enough to | |
542 | /// miss them all, so we can pick `L = max(max(FIXED_LEN)+1, max(PREFIX_LEN) + max(SUFFIX_LEN))` | |
543 | /// | |
544 | /// `max_slice` below will be made to have arity `L`. | |
545 | #[derive(Debug)] | |
546 | struct SplitVarLenSlice { | |
547 | /// If the type is an array, this is its size. | |
c295e0f8 | 548 | array_len: Option<usize>, |
fc512014 | 549 | /// The arity of the input slice. |
c295e0f8 | 550 | arity: usize, |
fc512014 XL |
551 | /// The smallest slice bigger than any slice seen. `max_slice.arity()` is the length `L` |
552 | /// described above. | |
553 | max_slice: SliceKind, | |
554 | } | |
555 | ||
556 | impl SplitVarLenSlice { | |
c295e0f8 | 557 | fn new(prefix: usize, suffix: usize, array_len: Option<usize>) -> Self { |
fc512014 XL |
558 | SplitVarLenSlice { array_len, arity: prefix + suffix, max_slice: VarLen(prefix, suffix) } |
559 | } | |
560 | ||
561 | /// Pass a set of slices relative to which to split this one. | |
562 | fn split(&mut self, slices: impl Iterator<Item = SliceKind>) { | |
563 | let (max_prefix_len, max_suffix_len) = match &mut self.max_slice { | |
564 | VarLen(prefix, suffix) => (prefix, suffix), | |
565 | FixedLen(_) => return, // No need to split | |
566 | }; | |
567 | // We grow `self.max_slice` to be larger than all slices encountered, as described above. | |
568 | // For diagnostics, we keep the prefix and suffix lengths separate, but grow them so that | |
569 | // `L = max_prefix_len + max_suffix_len`. | |
570 | let mut max_fixed_len = 0; | |
571 | for slice in slices { | |
572 | match slice { | |
573 | FixedLen(len) => { | |
574 | max_fixed_len = cmp::max(max_fixed_len, len); | |
575 | } | |
576 | VarLen(prefix, suffix) => { | |
577 | *max_prefix_len = cmp::max(*max_prefix_len, prefix); | |
578 | *max_suffix_len = cmp::max(*max_suffix_len, suffix); | |
579 | } | |
580 | } | |
581 | } | |
582 | // We want `L = max(L, max_fixed_len + 1)`, modulo the fact that we keep prefix and | |
583 | // suffix separate. | |
584 | if max_fixed_len + 1 >= *max_prefix_len + *max_suffix_len { | |
585 | // The subtraction can't overflow thanks to the above check. | |
586 | // The new `max_prefix_len` is larger than its previous value. | |
587 | *max_prefix_len = max_fixed_len + 1 - *max_suffix_len; | |
588 | } | |
589 | ||
590 | // We cap the arity of `max_slice` at the array size. | |
591 | match self.array_len { | |
592 | Some(len) if self.max_slice.arity() >= len => self.max_slice = FixedLen(len), | |
593 | _ => {} | |
594 | } | |
595 | } | |
596 | ||
597 | /// Iterate over the partition of this slice. | |
598 | fn iter<'a>(&'a self) -> impl Iterator<Item = Slice> + Captures<'a> { | |
599 | let smaller_lengths = match self.array_len { | |
600 | // The only admissible fixed-length slice is one of the array size. Whether `max_slice` | |
601 | // is fixed-length or variable-length, it will be the only relevant slice to output | |
602 | // here. | |
603 | Some(_) => (0..0), // empty range | |
604 | // We cover all arities in the range `(self.arity..infinity)`. We split that range into | |
605 | // two: lengths smaller than `max_slice.arity()` are treated independently as | |
606 | // fixed-lengths slices, and lengths above are captured by `max_slice`. | |
607 | None => self.arity..self.max_slice.arity(), | |
608 | }; | |
609 | smaller_lengths | |
610 | .map(FixedLen) | |
611 | .chain(once(self.max_slice)) | |
612 | .map(move |kind| Slice::new(self.array_len, kind)) | |
613 | } | |
614 | } | |
615 | ||
616 | /// A value can be decomposed into a constructor applied to some fields. This struct represents | |
617 | /// the constructor. See also `Fields`. | |
618 | /// | |
619 | /// `pat_constructor` retrieves the constructor corresponding to a pattern. | |
620 | /// `specialize_constructor` returns the list of fields corresponding to a pattern, given a | |
621 | /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and | |
622 | /// `Fields`. | |
623 | #[derive(Clone, Debug, PartialEq)] | |
624 | pub(super) enum Constructor<'tcx> { | |
625 | /// The constructor for patterns that have a single constructor, like tuples, struct patterns | |
626 | /// and fixed-length arrays. | |
627 | Single, | |
628 | /// Enum variants. | |
17df50a5 | 629 | Variant(VariantIdx), |
fc512014 XL |
630 | /// Ranges of integer literal values (`2`, `2..=5` or `2..5`). |
631 | IntRange(IntRange), | |
632 | /// Ranges of floating-point literal values (`2.0..=5.2`). | |
633 | FloatRange(&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>, RangeEnd), | |
634 | /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately. | |
635 | Str(&'tcx ty::Const<'tcx>), | |
636 | /// Array and slice patterns. | |
637 | Slice(Slice), | |
638 | /// Constants that must not be matched structurally. They are treated as black | |
639 | /// boxes for the purposes of exhaustiveness: we must not inspect them, and they | |
640 | /// don't count towards making a match exhaustive. | |
641 | Opaque, | |
642 | /// Fake extra constructor for enums that aren't allowed to be matched exhaustively. Also used | |
643 | /// for those types for which we cannot list constructors explicitly, like `f64` and `str`. | |
644 | NonExhaustive, | |
645 | /// Stands for constructors that are not seen in the matrix, as explained in the documentation | |
c295e0f8 XL |
646 | /// for [`SplitWildcard`]. The carried `bool` is used for the `non_exhaustive_omitted_patterns` |
647 | /// lint. | |
648 | Missing { nonexhaustive_enum_missing_real_variants: bool }, | |
fc512014 XL |
649 | /// Wildcard pattern. |
650 | Wildcard, | |
c295e0f8 XL |
651 | /// Or-pattern. |
652 | Or, | |
fc512014 XL |
653 | } |
654 | ||
655 | impl<'tcx> Constructor<'tcx> { | |
656 | pub(super) fn is_wildcard(&self) -> bool { | |
657 | matches!(self, Wildcard) | |
658 | } | |
659 | ||
c295e0f8 XL |
660 | pub(super) fn is_non_exhaustive(&self) -> bool { |
661 | matches!(self, NonExhaustive) | |
662 | } | |
663 | ||
fc512014 XL |
664 | fn as_int_range(&self) -> Option<&IntRange> { |
665 | match self { | |
666 | IntRange(range) => Some(range), | |
667 | _ => None, | |
668 | } | |
669 | } | |
670 | ||
671 | fn as_slice(&self) -> Option<Slice> { | |
672 | match self { | |
673 | Slice(slice) => Some(*slice), | |
674 | _ => None, | |
675 | } | |
676 | } | |
677 | ||
c295e0f8 XL |
678 | /// Checks if the `Constructor` is a variant and `TyCtxt::eval_stability` returns |
679 | /// `EvalResult::Deny { .. }`. | |
680 | /// | |
681 | /// This means that the variant has a stdlib unstable feature marking it. | |
682 | pub(super) fn is_unstable_variant(&self, pcx: PatCtxt<'_, '_, 'tcx>) -> bool { | |
683 | if let Constructor::Variant(idx) = self { | |
684 | if let ty::Adt(adt, _) = pcx.ty.kind() { | |
685 | let variant_def_id = adt.variants[*idx].def_id; | |
686 | // Filter variants that depend on a disabled unstable feature. | |
687 | return matches!( | |
688 | pcx.cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None), | |
689 | EvalResult::Deny { .. } | |
690 | ); | |
691 | } | |
692 | } | |
693 | false | |
694 | } | |
695 | ||
696 | /// Checks if the `Constructor` is a `Constructor::Variant` with a `#[doc(hidden)]` | |
697 | /// attribute. | |
698 | pub(super) fn is_doc_hidden_variant(&self, pcx: PatCtxt<'_, '_, 'tcx>) -> bool { | |
699 | if let Constructor::Variant(idx) = self { | |
700 | if let ty::Adt(adt, _) = pcx.ty.kind() { | |
701 | let variant_def_id = adt.variants[*idx].def_id; | |
702 | return pcx.cx.tcx.is_doc_hidden(variant_def_id); | |
703 | } | |
704 | } | |
705 | false | |
706 | } | |
707 | ||
fc512014 XL |
708 | fn variant_index_for_adt(&self, adt: &'tcx ty::AdtDef) -> VariantIdx { |
709 | match *self { | |
17df50a5 | 710 | Variant(idx) => idx, |
fc512014 XL |
711 | Single => { |
712 | assert!(!adt.is_enum()); | |
713 | VariantIdx::new(0) | |
714 | } | |
715 | _ => bug!("bad constructor {:?} for adt {:?}", self, adt), | |
716 | } | |
717 | } | |
718 | ||
c295e0f8 XL |
719 | /// The number of fields for this constructor. This must be kept in sync with |
720 | /// `Fields::wildcards`. | |
721 | pub(super) fn arity(&self, pcx: PatCtxt<'_, '_, 'tcx>) -> usize { | |
722 | match self { | |
723 | Single | Variant(_) => match pcx.ty.kind() { | |
724 | ty::Tuple(fs) => fs.len(), | |
725 | ty::Ref(..) => 1, | |
726 | ty::Adt(adt, ..) => { | |
727 | if adt.is_box() { | |
728 | // The only legal patterns of type `Box` (outside `std`) are `_` and box | |
729 | // patterns. If we're here we can assume this is a box pattern. | |
730 | 1 | |
731 | } else { | |
732 | let variant = &adt.variants[self.variant_index_for_adt(adt)]; | |
733 | Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant).count() | |
fc512014 XL |
734 | } |
735 | } | |
c295e0f8 XL |
736 | _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx.ty), |
737 | }, | |
738 | Slice(slice) => slice.arity(), | |
739 | Str(..) | |
740 | | FloatRange(..) | |
741 | | IntRange(..) | |
742 | | NonExhaustive | |
743 | | Opaque | |
744 | | Missing { .. } | |
745 | | Wildcard => 0, | |
746 | Or => bug!("The `Or` constructor doesn't have a fixed arity"), | |
fc512014 XL |
747 | } |
748 | } | |
749 | ||
750 | /// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of actual | |
751 | /// constructors (like variants, integers or fixed-sized slices). When specializing for these | |
752 | /// constructors, we want to be specialising for the actual underlying constructors. | |
753 | /// Naively, we would simply return the list of constructors they correspond to. We instead are | |
754 | /// more clever: if there are constructors that we know will behave the same wrt the current | |
755 | /// matrix, we keep them grouped. For example, all slices of a sufficiently large length | |
756 | /// will either be all useful or all non-useful with a given matrix. | |
757 | /// | |
758 | /// See the branches for details on how the splitting is done. | |
759 | /// | |
760 | /// This function may discard some irrelevant constructors if this preserves behavior and | |
761 | /// diagnostics. Eg. for the `_` case, we ignore the constructors already present in the | |
762 | /// matrix, unless all of them are. | |
763 | pub(super) fn split<'a>( | |
764 | &self, | |
765 | pcx: PatCtxt<'_, '_, 'tcx>, | |
766 | ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, | |
767 | ) -> SmallVec<[Self; 1]> | |
768 | where | |
769 | 'tcx: 'a, | |
770 | { | |
fc512014 XL |
771 | match self { |
772 | Wildcard => { | |
773 | let mut split_wildcard = SplitWildcard::new(pcx); | |
774 | split_wildcard.split(pcx, ctors); | |
775 | split_wildcard.into_ctors(pcx) | |
776 | } | |
777 | // Fast-track if the range is trivial. In particular, we don't do the overlapping | |
778 | // ranges check. | |
779 | IntRange(ctor_range) if !ctor_range.is_singleton() => { | |
780 | let mut split_range = SplitIntRange::new(ctor_range.clone()); | |
781 | let int_ranges = ctors.filter_map(|ctor| ctor.as_int_range()); | |
782 | split_range.split(int_ranges.cloned()); | |
783 | split_range.iter().map(IntRange).collect() | |
784 | } | |
785 | &Slice(Slice { kind: VarLen(self_prefix, self_suffix), array_len }) => { | |
786 | let mut split_self = SplitVarLenSlice::new(self_prefix, self_suffix, array_len); | |
787 | let slices = ctors.filter_map(|c| c.as_slice()).map(|s| s.kind); | |
788 | split_self.split(slices); | |
789 | split_self.iter().map(Slice).collect() | |
790 | } | |
791 | // Any other constructor can be used unchanged. | |
792 | _ => smallvec![self.clone()], | |
793 | } | |
794 | } | |
795 | ||
796 | /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`. | |
797 | /// For the simple cases, this is simply checking for equality. For the "grouped" constructors, | |
798 | /// this checks for inclusion. | |
799 | // We inline because this has a single call site in `Matrix::specialize_constructor`. | |
800 | #[inline] | |
801 | pub(super) fn is_covered_by<'p>(&self, pcx: PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool { | |
802 | // This must be kept in sync with `is_covered_by_any`. | |
803 | match (self, other) { | |
804 | // Wildcards cover anything | |
805 | (_, Wildcard) => true, | |
806 | // The missing ctors are not covered by anything in the matrix except wildcards. | |
c295e0f8 | 807 | (Missing { .. } | Wildcard, _) => false, |
fc512014 XL |
808 | |
809 | (Single, Single) => true, | |
810 | (Variant(self_id), Variant(other_id)) => self_id == other_id, | |
811 | ||
812 | (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range), | |
813 | ( | |
814 | FloatRange(self_from, self_to, self_end), | |
815 | FloatRange(other_from, other_to, other_end), | |
816 | ) => { | |
817 | match ( | |
818 | compare_const_vals(pcx.cx.tcx, self_to, other_to, pcx.cx.param_env, pcx.ty), | |
819 | compare_const_vals(pcx.cx.tcx, self_from, other_from, pcx.cx.param_env, pcx.ty), | |
820 | ) { | |
821 | (Some(to), Some(from)) => { | |
822 | (from == Ordering::Greater || from == Ordering::Equal) | |
823 | && (to == Ordering::Less | |
824 | || (other_end == self_end && to == Ordering::Equal)) | |
825 | } | |
826 | _ => false, | |
827 | } | |
828 | } | |
829 | (Str(self_val), Str(other_val)) => { | |
830 | // FIXME: there's probably a more direct way of comparing for equality | |
831 | match compare_const_vals(pcx.cx.tcx, self_val, other_val, pcx.cx.param_env, pcx.ty) | |
832 | { | |
833 | Some(comparison) => comparison == Ordering::Equal, | |
834 | None => false, | |
835 | } | |
836 | } | |
837 | (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice), | |
838 | ||
839 | // We are trying to inspect an opaque constant. Thus we skip the row. | |
840 | (Opaque, _) | (_, Opaque) => false, | |
841 | // Only a wildcard pattern can match the special extra constructor. | |
842 | (NonExhaustive, _) => false, | |
843 | ||
844 | _ => span_bug!( | |
845 | pcx.span, | |
846 | "trying to compare incompatible constructors {:?} and {:?}", | |
847 | self, | |
848 | other | |
849 | ), | |
850 | } | |
851 | } | |
852 | ||
853 | /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is | |
854 | /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is | |
855 | /// assumed to have been split from a wildcard. | |
856 | fn is_covered_by_any<'p>( | |
857 | &self, | |
858 | pcx: PatCtxt<'_, 'p, 'tcx>, | |
859 | used_ctors: &[Constructor<'tcx>], | |
860 | ) -> bool { | |
861 | if used_ctors.is_empty() { | |
862 | return false; | |
863 | } | |
864 | ||
865 | // This must be kept in sync with `is_covered_by`. | |
866 | match self { | |
867 | // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s. | |
868 | Single => !used_ctors.is_empty(), | |
c295e0f8 | 869 | Variant(vid) => used_ctors.iter().any(|c| matches!(c, Variant(i) if i == vid)), |
fc512014 XL |
870 | IntRange(range) => used_ctors |
871 | .iter() | |
872 | .filter_map(|c| c.as_int_range()) | |
873 | .any(|other| range.is_covered_by(other)), | |
874 | Slice(slice) => used_ctors | |
875 | .iter() | |
876 | .filter_map(|c| c.as_slice()) | |
877 | .any(|other| slice.is_covered_by(other)), | |
878 | // This constructor is never covered by anything else | |
879 | NonExhaustive => false, | |
c295e0f8 | 880 | Str(..) | FloatRange(..) | Opaque | Missing { .. } | Wildcard | Or => { |
fc512014 XL |
881 | span_bug!(pcx.span, "found unexpected ctor in all_ctors: {:?}", self) |
882 | } | |
883 | } | |
884 | } | |
885 | } | |
886 | ||
887 | /// A wildcard constructor that we split relative to the constructors in the matrix, as explained | |
888 | /// at the top of the file. | |
889 | /// | |
890 | /// A constructor that is not present in the matrix rows will only be covered by the rows that have | |
891 | /// wildcards. Thus we can group all of those constructors together; we call them "missing | |
892 | /// constructors". Splitting a wildcard would therefore list all present constructors individually | |
893 | /// (or grouped if they are integers or slices), and then all missing constructors together as a | |
894 | /// group. | |
895 | /// | |
896 | /// However we can go further: since any constructor will match the wildcard rows, and having more | |
897 | /// rows can only reduce the amount of usefulness witnesses, we can skip the present constructors | |
898 | /// and only try the missing ones. | |
899 | /// This will not preserve the whole list of witnesses, but will preserve whether the list is empty | |
900 | /// or not. In fact this is quite natural from the point of view of diagnostics too. This is done | |
901 | /// in `to_ctors`: in some cases we only return `Missing`. | |
902 | #[derive(Debug)] | |
903 | pub(super) struct SplitWildcard<'tcx> { | |
904 | /// Constructors seen in the matrix. | |
905 | matrix_ctors: Vec<Constructor<'tcx>>, | |
906 | /// All the constructors for this type | |
907 | all_ctors: SmallVec<[Constructor<'tcx>; 1]>, | |
908 | } | |
909 | ||
910 | impl<'tcx> SplitWildcard<'tcx> { | |
911 | pub(super) fn new<'p>(pcx: PatCtxt<'_, 'p, 'tcx>) -> Self { | |
912 | debug!("SplitWildcard::new({:?})", pcx.ty); | |
913 | let cx = pcx.cx; | |
914 | let make_range = |start, end| { | |
915 | IntRange( | |
916 | // `unwrap()` is ok because we know the type is an integer. | |
917 | IntRange::from_range(cx.tcx, start, end, pcx.ty, &RangeEnd::Included).unwrap(), | |
918 | ) | |
919 | }; | |
920 | // This determines the set of all possible constructors for the type `pcx.ty`. For numbers, | |
921 | // arrays and slices we use ranges and variable-length slices when appropriate. | |
922 | // | |
923 | // If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that | |
924 | // are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the | |
925 | // returned list of constructors. | |
926 | // Invariant: this is empty if and only if the type is uninhabited (as determined by | |
927 | // `cx.is_uninhabited()`). | |
928 | let all_ctors = match pcx.ty.kind() { | |
929 | ty::Bool => smallvec![make_range(0, 1)], | |
930 | ty::Array(sub_ty, len) if len.try_eval_usize(cx.tcx, cx.param_env).is_some() => { | |
c295e0f8 | 931 | let len = len.eval_usize(cx.tcx, cx.param_env) as usize; |
fc512014 XL |
932 | if len != 0 && cx.is_uninhabited(sub_ty) { |
933 | smallvec![] | |
934 | } else { | |
935 | smallvec![Slice(Slice::new(Some(len), VarLen(0, 0)))] | |
936 | } | |
937 | } | |
938 | // Treat arrays of a constant but unknown length like slices. | |
939 | ty::Array(sub_ty, _) | ty::Slice(sub_ty) => { | |
940 | let kind = if cx.is_uninhabited(sub_ty) { FixedLen(0) } else { VarLen(0, 0) }; | |
941 | smallvec![Slice(Slice::new(None, kind))] | |
942 | } | |
943 | ty::Adt(def, substs) if def.is_enum() => { | |
944 | // If the enum is declared as `#[non_exhaustive]`, we treat it as if it had an | |
945 | // additional "unknown" constructor. | |
946 | // There is no point in enumerating all possible variants, because the user can't | |
947 | // actually match against them all themselves. So we always return only the fictitious | |
948 | // constructor. | |
949 | // E.g., in an example like: | |
950 | // | |
951 | // ``` | |
952 | // let err: io::ErrorKind = ...; | |
953 | // match err { | |
954 | // io::ErrorKind::NotFound => {}, | |
955 | // } | |
956 | // ``` | |
957 | // | |
958 | // we don't want to show every possible IO error, but instead have only `_` as the | |
959 | // witness. | |
960 | let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(pcx.ty); | |
961 | ||
c295e0f8 XL |
962 | let is_exhaustive_pat_feature = cx.tcx.features().exhaustive_patterns; |
963 | ||
fc512014 XL |
964 | // If `exhaustive_patterns` is disabled and our scrutinee is an empty enum, we treat it |
965 | // as though it had an "unknown" constructor to avoid exposing its emptiness. The | |
966 | // exception is if the pattern is at the top level, because we want empty matches to be | |
967 | // considered exhaustive. | |
c295e0f8 XL |
968 | let is_secretly_empty = |
969 | def.variants.is_empty() && !is_exhaustive_pat_feature && !pcx.is_top_level; | |
970 | ||
971 | let mut ctors: SmallVec<[_; 1]> = def | |
972 | .variants | |
973 | .iter_enumerated() | |
974 | .filter(|(_, v)| { | |
975 | // If `exhaustive_patterns` is enabled, we exclude variants known to be | |
976 | // uninhabited. | |
977 | let is_uninhabited = is_exhaustive_pat_feature | |
978 | && v.uninhabited_from(cx.tcx, substs, def.adt_kind(), cx.param_env) | |
979 | .contains(cx.tcx, cx.module); | |
980 | !is_uninhabited | |
981 | }) | |
982 | .map(|(idx, _)| Variant(idx)) | |
983 | .collect(); | |
fc512014 XL |
984 | |
985 | if is_secretly_empty || is_declared_nonexhaustive { | |
c295e0f8 | 986 | ctors.push(NonExhaustive); |
fc512014 | 987 | } |
c295e0f8 | 988 | ctors |
fc512014 XL |
989 | } |
990 | ty::Char => { | |
991 | smallvec![ | |
992 | // The valid Unicode Scalar Value ranges. | |
993 | make_range('\u{0000}' as u128, '\u{D7FF}' as u128), | |
994 | make_range('\u{E000}' as u128, '\u{10FFFF}' as u128), | |
995 | ] | |
996 | } | |
997 | ty::Int(_) | ty::Uint(_) | |
998 | if pcx.ty.is_ptr_sized_integral() | |
999 | && !cx.tcx.features().precise_pointer_size_matching => | |
1000 | { | |
1001 | // `usize`/`isize` are not allowed to be matched exhaustively unless the | |
1002 | // `precise_pointer_size_matching` feature is enabled. So we treat those types like | |
1003 | // `#[non_exhaustive]` enums by returning a special unmatcheable constructor. | |
1004 | smallvec![NonExhaustive] | |
1005 | } | |
1006 | &ty::Int(ity) => { | |
5869c6ff | 1007 | let bits = Integer::from_int_ty(&cx.tcx, ity).size().bits() as u128; |
fc512014 XL |
1008 | let min = 1u128 << (bits - 1); |
1009 | let max = min - 1; | |
1010 | smallvec![make_range(min, max)] | |
1011 | } | |
1012 | &ty::Uint(uty) => { | |
5869c6ff | 1013 | let size = Integer::from_uint_ty(&cx.tcx, uty).size(); |
fc512014 XL |
1014 | let max = size.truncate(u128::MAX); |
1015 | smallvec![make_range(0, max)] | |
1016 | } | |
1017 | // If `exhaustive_patterns` is disabled and our scrutinee is the never type, we cannot | |
1018 | // expose its emptiness. The exception is if the pattern is at the top level, because we | |
1019 | // want empty matches to be considered exhaustive. | |
1020 | ty::Never if !cx.tcx.features().exhaustive_patterns && !pcx.is_top_level => { | |
1021 | smallvec![NonExhaustive] | |
1022 | } | |
1023 | ty::Never => smallvec![], | |
1024 | _ if cx.is_uninhabited(pcx.ty) => smallvec![], | |
1025 | ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => smallvec![Single], | |
1026 | // This type is one for which we cannot list constructors, like `str` or `f64`. | |
1027 | _ => smallvec![NonExhaustive], | |
1028 | }; | |
c295e0f8 | 1029 | |
fc512014 XL |
1030 | SplitWildcard { matrix_ctors: Vec::new(), all_ctors } |
1031 | } | |
1032 | ||
1033 | /// Pass a set of constructors relative to which to split this one. Don't call twice, it won't | |
1034 | /// do what you want. | |
1035 | pub(super) fn split<'a>( | |
1036 | &mut self, | |
1037 | pcx: PatCtxt<'_, '_, 'tcx>, | |
1038 | ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone, | |
1039 | ) where | |
1040 | 'tcx: 'a, | |
1041 | { | |
1042 | // Since `all_ctors` never contains wildcards, this won't recurse further. | |
1043 | self.all_ctors = | |
1044 | self.all_ctors.iter().flat_map(|ctor| ctor.split(pcx, ctors.clone())).collect(); | |
1045 | self.matrix_ctors = ctors.filter(|c| !c.is_wildcard()).cloned().collect(); | |
1046 | } | |
1047 | ||
1048 | /// Whether there are any value constructors for this type that are not present in the matrix. | |
1049 | fn any_missing(&self, pcx: PatCtxt<'_, '_, 'tcx>) -> bool { | |
1050 | self.iter_missing(pcx).next().is_some() | |
1051 | } | |
1052 | ||
1053 | /// Iterate over the constructors for this type that are not present in the matrix. | |
1054 | pub(super) fn iter_missing<'a, 'p>( | |
1055 | &'a self, | |
1056 | pcx: PatCtxt<'a, 'p, 'tcx>, | |
1057 | ) -> impl Iterator<Item = &'a Constructor<'tcx>> + Captures<'p> { | |
1058 | self.all_ctors.iter().filter(move |ctor| !ctor.is_covered_by_any(pcx, &self.matrix_ctors)) | |
1059 | } | |
1060 | ||
1061 | /// Return the set of constructors resulting from splitting the wildcard. As explained at the | |
1062 | /// top of the file, if any constructors are missing we can ignore the present ones. | |
1063 | fn into_ctors(self, pcx: PatCtxt<'_, '_, 'tcx>) -> SmallVec<[Constructor<'tcx>; 1]> { | |
1064 | if self.any_missing(pcx) { | |
1065 | // Some constructors are missing, thus we can specialize with the special `Missing` | |
1066 | // constructor, which stands for those constructors that are not seen in the matrix, | |
1067 | // and matches the same rows as any of them (namely the wildcard rows). See the top of | |
1068 | // the file for details. | |
1069 | // However, when all constructors are missing we can also specialize with the full | |
1070 | // `Wildcard` constructor. The difference will depend on what we want in diagnostics. | |
1071 | ||
1072 | // If some constructors are missing, we typically want to report those constructors, | |
1073 | // e.g.: | |
1074 | // ``` | |
1075 | // enum Direction { N, S, E, W } | |
1076 | // let Direction::N = ...; | |
1077 | // ``` | |
1078 | // we can report 3 witnesses: `S`, `E`, and `W`. | |
1079 | // | |
1080 | // However, if the user didn't actually specify a constructor | |
1081 | // in this arm, e.g., in | |
1082 | // ``` | |
1083 | // let x: (Direction, Direction, bool) = ...; | |
1084 | // let (_, _, false) = x; | |
1085 | // ``` | |
1086 | // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>, | |
1087 | // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we | |
1088 | // prefer to report just a wildcard `_`. | |
1089 | // | |
1090 | // The exception is: if we are at the top-level, for example in an empty match, we | |
1091 | // sometimes prefer reporting the list of constructors instead of just `_`. | |
1092 | let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(pcx.ty); | |
1093 | let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing { | |
c295e0f8 XL |
1094 | if pcx.is_non_exhaustive { |
1095 | Missing { | |
1096 | nonexhaustive_enum_missing_real_variants: self | |
1097 | .iter_missing(pcx) | |
1098 | .any(|c| !(c.is_non_exhaustive() || c.is_unstable_variant(pcx))), | |
1099 | } | |
1100 | } else { | |
1101 | Missing { nonexhaustive_enum_missing_real_variants: false } | |
1102 | } | |
fc512014 XL |
1103 | } else { |
1104 | Wildcard | |
1105 | }; | |
1106 | return smallvec![ctor]; | |
1107 | } | |
1108 | ||
1109 | // All the constructors are present in the matrix, so we just go through them all. | |
1110 | self.all_ctors | |
1111 | } | |
1112 | } | |
1113 | ||
fc512014 XL |
1114 | /// A value can be decomposed into a constructor applied to some fields. This struct represents |
1115 | /// those fields, generalized to allow patterns in each field. See also `Constructor`. | |
fc512014 | 1116 | /// |
c295e0f8 XL |
1117 | /// This is constructed for a constructor using [`Fields::wildcards()`]. The idea is that |
1118 | /// [`Fields::wildcards()`] constructs a list of fields where all entries are wildcards, and then | |
1119 | /// given a pattern we fill some of the fields with its subpatterns. | |
1120 | /// In the following example `Fields::wildcards` returns `[_, _, _, _]`. Then in | |
1121 | /// `extract_pattern_arguments` we fill some of the entries, and the result is | |
1122 | /// `[Some(0), _, _, _]`. | |
1123 | /// ```rust | |
1124 | /// let x: [Option<u8>; 4] = foo(); | |
1125 | /// match x { | |
1126 | /// [Some(0), ..] => {} | |
1127 | /// } | |
1128 | /// ``` | |
1129 | /// | |
1130 | /// Note that the number of fields of a constructor may not match the fields declared in the | |
1131 | /// original struct/variant. This happens if a private or `non_exhaustive` field is uninhabited, | |
1132 | /// because the code mustn't observe that it is uninhabited. In that case that field is not | |
1133 | /// included in `fields`. For that reason, when you have a `mir::Field` you must use | |
1134 | /// `index_with_declared_idx`. | |
1135 | #[derive(Debug, Clone, Copy)] | |
1136 | pub(super) struct Fields<'p, 'tcx> { | |
1137 | fields: &'p [DeconstructedPat<'p, 'tcx>], | |
fc512014 XL |
1138 | } |
1139 | ||
1140 | impl<'p, 'tcx> Fields<'p, 'tcx> { | |
c295e0f8 XL |
1141 | fn empty() -> Self { |
1142 | Fields { fields: &[] } | |
1143 | } | |
1144 | ||
1145 | fn singleton(cx: &MatchCheckCtxt<'p, 'tcx>, field: DeconstructedPat<'p, 'tcx>) -> Self { | |
1146 | let field: &_ = cx.pattern_arena.alloc(field); | |
1147 | Fields { fields: std::slice::from_ref(field) } | |
1148 | } | |
1149 | ||
1150 | pub(super) fn from_iter( | |
1151 | cx: &MatchCheckCtxt<'p, 'tcx>, | |
1152 | fields: impl IntoIterator<Item = DeconstructedPat<'p, 'tcx>>, | |
1153 | ) -> Self { | |
1154 | let fields: &[_] = cx.pattern_arena.alloc_from_iter(fields); | |
1155 | Fields { fields } | |
fc512014 XL |
1156 | } |
1157 | ||
fc512014 XL |
1158 | fn wildcards_from_tys( |
1159 | cx: &MatchCheckCtxt<'p, 'tcx>, | |
1160 | tys: impl IntoIterator<Item = Ty<'tcx>>, | |
1161 | ) -> Self { | |
c295e0f8 | 1162 | Fields::from_iter(cx, tys.into_iter().map(DeconstructedPat::wildcard)) |
fc512014 XL |
1163 | } |
1164 | ||
c295e0f8 XL |
1165 | // In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide |
1166 | // uninhabited fields in order not to reveal the uninhabitedness of the whole variant. | |
1167 | // This lists the fields we keep along with their types. | |
1168 | fn list_variant_nonhidden_fields<'a>( | |
1169 | cx: &'a MatchCheckCtxt<'p, 'tcx>, | |
1170 | ty: Ty<'tcx>, | |
1171 | variant: &'a VariantDef, | |
1172 | ) -> impl Iterator<Item = (Field, Ty<'tcx>)> + Captures<'a> + Captures<'p> { | |
1173 | let (adt, substs) = match ty.kind() { | |
1174 | ty::Adt(adt, substs) => (adt, substs), | |
1175 | _ => bug!(), | |
1176 | }; | |
1177 | // Whether we must not match the fields of this variant exhaustively. | |
1178 | let is_non_exhaustive = variant.is_field_list_non_exhaustive() && !adt.did.is_local(); | |
1179 | ||
1180 | variant.fields.iter().enumerate().filter_map(move |(i, field)| { | |
1181 | let ty = field.ty(cx.tcx, substs); | |
1182 | // `field.ty()` doesn't normalize after substituting. | |
1183 | let ty = cx.tcx.normalize_erasing_regions(cx.param_env, ty); | |
1184 | let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx); | |
1185 | let is_uninhabited = cx.is_uninhabited(ty); | |
1186 | ||
1187 | if is_uninhabited && (!is_visible || is_non_exhaustive) { | |
1188 | None | |
1189 | } else { | |
1190 | Some((Field::new(i), ty)) | |
1191 | } | |
1192 | }) | |
1193 | } | |
fc512014 | 1194 | |
c295e0f8 XL |
1195 | /// Creates a new list of wildcard fields for a given constructor. The result must have a |
1196 | /// length of `constructor.arity()`. | |
1197 | pub(super) fn wildcards( | |
1198 | cx: &MatchCheckCtxt<'p, 'tcx>, | |
1199 | ty: Ty<'tcx>, | |
1200 | constructor: &Constructor<'tcx>, | |
1201 | ) -> Self { | |
fc512014 XL |
1202 | let ret = match constructor { |
1203 | Single | Variant(_) => match ty.kind() { | |
c295e0f8 XL |
1204 | ty::Tuple(fs) => Fields::wildcards_from_tys(cx, fs.iter().map(|ty| ty.expect_ty())), |
1205 | ty::Ref(_, rty, _) => Fields::wildcards_from_tys(cx, once(*rty)), | |
fc512014 XL |
1206 | ty::Adt(adt, substs) => { |
1207 | if adt.is_box() { | |
c295e0f8 XL |
1208 | // The only legal patterns of type `Box` (outside `std`) are `_` and box |
1209 | // patterns. If we're here we can assume this is a box pattern. | |
1210 | Fields::wildcards_from_tys(cx, once(substs.type_at(0))) | |
fc512014 XL |
1211 | } else { |
1212 | let variant = &adt.variants[constructor.variant_index_for_adt(adt)]; | |
c295e0f8 XL |
1213 | let tys = Fields::list_variant_nonhidden_fields(cx, ty, variant) |
1214 | .map(|(_, ty)| ty); | |
1215 | Fields::wildcards_from_tys(cx, tys) | |
fc512014 XL |
1216 | } |
1217 | } | |
1218 | _ => bug!("Unexpected type for `Single` constructor: {:?}", ty), | |
1219 | }, | |
1220 | Slice(slice) => match *ty.kind() { | |
1221 | ty::Slice(ty) | ty::Array(ty, _) => { | |
1222 | let arity = slice.arity(); | |
1223 | Fields::wildcards_from_tys(cx, (0..arity).map(|_| ty)) | |
1224 | } | |
1225 | _ => bug!("bad slice pattern {:?} {:?}", constructor, ty), | |
1226 | }, | |
c295e0f8 XL |
1227 | Str(..) |
1228 | | FloatRange(..) | |
1229 | | IntRange(..) | |
1230 | | NonExhaustive | |
1231 | | Opaque | |
1232 | | Missing { .. } | |
1233 | | Wildcard => Fields::empty(), | |
1234 | Or => { | |
1235 | bug!("called `Fields::wildcards` on an `Or` ctor") | |
1236 | } | |
fc512014 XL |
1237 | }; |
1238 | debug!("Fields::wildcards({:?}, {:?}) = {:#?}", constructor, ty, ret); | |
1239 | ret | |
1240 | } | |
1241 | ||
c295e0f8 XL |
1242 | /// Returns the list of patterns. |
1243 | pub(super) fn iter_patterns<'a>( | |
1244 | &'a self, | |
1245 | ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> { | |
1246 | self.fields.iter() | |
1247 | } | |
1248 | } | |
fc512014 | 1249 | |
c295e0f8 XL |
1250 | /// Values and patterns can be represented as a constructor applied to some fields. This represents |
1251 | /// a pattern in this form. | |
1252 | /// This also keeps track of whether the pattern has been found reachable during analysis. For this | |
1253 | /// reason we should be careful not to clone patterns for which we care about that. Use | |
1254 | /// `clone_and_forget_reachability` if you're sure. | |
1255 | pub(crate) struct DeconstructedPat<'p, 'tcx> { | |
1256 | ctor: Constructor<'tcx>, | |
1257 | fields: Fields<'p, 'tcx>, | |
1258 | ty: Ty<'tcx>, | |
1259 | span: Span, | |
1260 | reachable: Cell<bool>, | |
1261 | } | |
1262 | ||
1263 | impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { | |
1264 | pub(super) fn wildcard(ty: Ty<'tcx>) -> Self { | |
1265 | Self::new(Wildcard, Fields::empty(), ty, DUMMY_SP) | |
1266 | } | |
1267 | ||
1268 | pub(super) fn new( | |
1269 | ctor: Constructor<'tcx>, | |
1270 | fields: Fields<'p, 'tcx>, | |
1271 | ty: Ty<'tcx>, | |
1272 | span: Span, | |
1273 | ) -> Self { | |
1274 | DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) } | |
1275 | } | |
1276 | ||
1277 | /// Construct a pattern that matches everything that starts with this constructor. | |
1278 | /// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern | |
1279 | /// `Some(_)`. | |
1280 | pub(super) fn wild_from_ctor(pcx: PatCtxt<'_, 'p, 'tcx>, ctor: Constructor<'tcx>) -> Self { | |
1281 | let fields = Fields::wildcards(pcx.cx, pcx.ty, &ctor); | |
1282 | DeconstructedPat::new(ctor, fields, pcx.ty, DUMMY_SP) | |
1283 | } | |
1284 | ||
1285 | /// Clone this value. This method emphasizes that cloning loses reachability information and | |
1286 | /// should be done carefully. | |
1287 | pub(super) fn clone_and_forget_reachability(&self) -> Self { | |
1288 | DeconstructedPat::new(self.ctor.clone(), self.fields, self.ty, self.span) | |
1289 | } | |
1290 | ||
1291 | pub(crate) fn from_pat(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &Pat<'tcx>) -> Self { | |
1292 | let mkpat = |pat| DeconstructedPat::from_pat(cx, pat); | |
1293 | let ctor; | |
1294 | let fields; | |
1295 | match pat.kind.as_ref() { | |
1296 | PatKind::AscribeUserType { subpattern, .. } => return mkpat(subpattern), | |
1297 | PatKind::Binding { subpattern: Some(subpat), .. } => return mkpat(subpat), | |
1298 | PatKind::Binding { subpattern: None, .. } | PatKind::Wild => { | |
1299 | ctor = Wildcard; | |
1300 | fields = Fields::empty(); | |
1301 | } | |
1302 | PatKind::Deref { subpattern } => { | |
1303 | ctor = Single; | |
1304 | fields = Fields::singleton(cx, mkpat(subpattern)); | |
1305 | } | |
1306 | PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => { | |
1307 | match pat.ty.kind() { | |
1308 | ty::Tuple(fs) => { | |
1309 | ctor = Single; | |
1310 | let mut wilds: SmallVec<[_; 2]> = fs | |
1311 | .iter() | |
1312 | .map(|ty| ty.expect_ty()) | |
1313 | .map(DeconstructedPat::wildcard) | |
1314 | .collect(); | |
1315 | for pat in subpatterns { | |
1316 | wilds[pat.field.index()] = mkpat(&pat.pattern); | |
1317 | } | |
1318 | fields = Fields::from_iter(cx, wilds); | |
1319 | } | |
1320 | ty::Adt(adt, substs) if adt.is_box() => { | |
1321 | // The only legal patterns of type `Box` (outside `std`) are `_` and box | |
1322 | // patterns. If we're here we can assume this is a box pattern. | |
1323 | // FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_, | |
1324 | // _)` or a box pattern. As a hack to avoid an ICE with the former, we | |
1325 | // ignore other fields than the first one. This will trigger an error later | |
1326 | // anyway. | |
1327 | // See https://github.com/rust-lang/rust/issues/82772 , | |
1328 | // explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977 | |
1329 | // The problem is that we can't know from the type whether we'll match | |
1330 | // normally or through box-patterns. We'll have to figure out a proper | |
1331 | // solution when we introduce generalized deref patterns. Also need to | |
1332 | // prevent mixing of those two options. | |
1333 | let pat = subpatterns.into_iter().find(|pat| pat.field.index() == 0); | |
1334 | let pat = if let Some(pat) = pat { | |
1335 | mkpat(&pat.pattern) | |
fc512014 | 1336 | } else { |
c295e0f8 XL |
1337 | DeconstructedPat::wildcard(substs.type_at(0)) |
1338 | }; | |
1339 | ctor = Single; | |
1340 | fields = Fields::singleton(cx, pat); | |
1341 | } | |
1342 | ty::Adt(adt, _) => { | |
1343 | ctor = match pat.kind.as_ref() { | |
1344 | PatKind::Leaf { .. } => Single, | |
1345 | PatKind::Variant { variant_index, .. } => Variant(*variant_index), | |
1346 | _ => bug!(), | |
1347 | }; | |
1348 | let variant = &adt.variants[ctor.variant_index_for_adt(adt)]; | |
1349 | // For each field in the variant, we store the relevant index into `self.fields` if any. | |
1350 | let mut field_id_to_id: Vec<Option<usize>> = | |
1351 | (0..variant.fields.len()).map(|_| None).collect(); | |
1352 | let tys = Fields::list_variant_nonhidden_fields(cx, pat.ty, variant) | |
1353 | .enumerate() | |
1354 | .map(|(i, (field, ty))| { | |
1355 | field_id_to_id[field.index()] = Some(i); | |
1356 | ty | |
1357 | }); | |
1358 | let mut wilds: SmallVec<[_; 2]> = | |
1359 | tys.map(DeconstructedPat::wildcard).collect(); | |
1360 | for pat in subpatterns { | |
1361 | if let Some(i) = field_id_to_id[pat.field.index()] { | |
1362 | wilds[i] = mkpat(&pat.pattern); | |
1363 | } | |
1364 | } | |
1365 | fields = Fields::from_iter(cx, wilds); | |
1366 | } | |
1367 | _ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, pat.ty), | |
1368 | } | |
1369 | } | |
1370 | PatKind::Constant { value } => { | |
1371 | if let Some(int_range) = IntRange::from_const(cx.tcx, cx.param_env, value) { | |
1372 | ctor = IntRange(int_range); | |
1373 | fields = Fields::empty(); | |
1374 | } else { | |
1375 | match pat.ty.kind() { | |
1376 | ty::Float(_) => { | |
1377 | ctor = FloatRange(value, value, RangeEnd::Included); | |
1378 | fields = Fields::empty(); | |
1379 | } | |
1380 | ty::Ref(_, t, _) if t.is_str() => { | |
1381 | // We want a `&str` constant to behave like a `Deref` pattern, to be compatible | |
1382 | // with other `Deref` patterns. This could have been done in `const_to_pat`, | |
1383 | // but that causes issues with the rest of the matching code. | |
1384 | // So here, the constructor for a `"foo"` pattern is `&` (represented by | |
1385 | // `Single`), and has one field. That field has constructor `Str(value)` and no | |
1386 | // fields. | |
1387 | // Note: `t` is `str`, not `&str`. | |
1388 | let subpattern = | |
1389 | DeconstructedPat::new(Str(value), Fields::empty(), t, pat.span); | |
1390 | ctor = Single; | |
1391 | fields = Fields::singleton(cx, subpattern) | |
fc512014 | 1392 | } |
c295e0f8 XL |
1393 | // All constants that can be structurally matched have already been expanded |
1394 | // into the corresponding `Pat`s by `const_to_pat`. Constants that remain are | |
1395 | // opaque. | |
1396 | _ => { | |
1397 | ctor = Opaque; | |
1398 | fields = Fields::empty(); | |
1399 | } | |
1400 | } | |
1401 | } | |
1402 | } | |
1403 | &PatKind::Range(PatRange { lo, hi, end }) => { | |
1404 | let ty = lo.ty; | |
1405 | ctor = if let Some(int_range) = IntRange::from_range( | |
1406 | cx.tcx, | |
1407 | lo.eval_bits(cx.tcx, cx.param_env, lo.ty), | |
1408 | hi.eval_bits(cx.tcx, cx.param_env, hi.ty), | |
1409 | ty, | |
1410 | &end, | |
1411 | ) { | |
1412 | IntRange(int_range) | |
1413 | } else { | |
1414 | FloatRange(lo, hi, end) | |
1415 | }; | |
1416 | fields = Fields::empty(); | |
1417 | } | |
1418 | PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => { | |
1419 | let array_len = match pat.ty.kind() { | |
1420 | ty::Array(_, length) => Some(length.eval_usize(cx.tcx, cx.param_env) as usize), | |
1421 | ty::Slice(_) => None, | |
1422 | _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty), | |
1423 | }; | |
1424 | let kind = if slice.is_some() { | |
1425 | VarLen(prefix.len(), suffix.len()) | |
1426 | } else { | |
1427 | FixedLen(prefix.len() + suffix.len()) | |
1428 | }; | |
1429 | ctor = Slice(Slice::new(array_len, kind)); | |
1430 | fields = Fields::from_iter(cx, prefix.iter().chain(suffix).map(mkpat)); | |
1431 | } | |
1432 | PatKind::Or { .. } => { | |
1433 | ctor = Or; | |
1434 | let pats = expand_or_pat(pat); | |
1435 | fields = Fields::from_iter(cx, pats.into_iter().map(mkpat)); | |
1436 | } | |
1437 | } | |
1438 | DeconstructedPat::new(ctor, fields, pat.ty, pat.span) | |
1439 | } | |
1440 | ||
1441 | pub(crate) fn to_pat(&self, cx: &MatchCheckCtxt<'p, 'tcx>) -> Pat<'tcx> { | |
1442 | let is_wildcard = |pat: &Pat<'_>| { | |
1443 | matches!(*pat.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild) | |
1444 | }; | |
1445 | let mut subpatterns = self.iter_fields().map(|p| p.to_pat(cx)); | |
1446 | let pat = match &self.ctor { | |
1447 | Single | Variant(_) => match self.ty.kind() { | |
1448 | ty::Tuple(..) => PatKind::Leaf { | |
1449 | subpatterns: subpatterns | |
1450 | .enumerate() | |
1451 | .map(|(i, p)| FieldPat { field: Field::new(i), pattern: p }) | |
1452 | .collect(), | |
1453 | }, | |
1454 | ty::Adt(adt_def, _) if adt_def.is_box() => { | |
1455 | // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside | |
1456 | // of `std`). So this branch is only reachable when the feature is enabled and | |
1457 | // the pattern is a box pattern. | |
1458 | PatKind::Deref { subpattern: subpatterns.next().unwrap() } | |
1459 | } | |
1460 | ty::Adt(adt_def, substs) => { | |
1461 | let variant_index = self.ctor.variant_index_for_adt(adt_def); | |
1462 | let variant = &adt_def.variants[variant_index]; | |
1463 | let subpatterns = Fields::list_variant_nonhidden_fields(cx, self.ty, variant) | |
1464 | .zip(subpatterns) | |
1465 | .map(|((field, _ty), pattern)| FieldPat { field, pattern }) | |
1466 | .collect(); | |
1467 | ||
1468 | if adt_def.is_enum() { | |
1469 | PatKind::Variant { adt_def, substs, variant_index, subpatterns } | |
fc512014 XL |
1470 | } else { |
1471 | PatKind::Leaf { subpatterns } | |
1472 | } | |
1473 | } | |
1474 | // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should | |
1475 | // be careful to reconstruct the correct constant pattern here. However a string | |
1476 | // literal pattern will never be reported as a non-exhaustiveness witness, so we | |
c295e0f8 | 1477 | // ignore this issue. |
fc512014 | 1478 | ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() }, |
c295e0f8 | 1479 | _ => bug!("unexpected ctor for type {:?} {:?}", self.ctor, self.ty), |
fc512014 | 1480 | }, |
c295e0f8 XL |
1481 | Slice(slice) => { |
1482 | match slice.kind { | |
1483 | FixedLen(_) => PatKind::Slice { | |
1484 | prefix: subpatterns.collect(), | |
1485 | slice: None, | |
1486 | suffix: vec![], | |
1487 | }, | |
1488 | VarLen(prefix, _) => { | |
1489 | let mut subpatterns = subpatterns.peekable(); | |
1490 | let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect(); | |
1491 | if slice.array_len.is_some() { | |
1492 | // Improves diagnostics a bit: if the type is a known-size array, instead | |
1493 | // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`. | |
1494 | // This is incorrect if the size is not known, since `[_, ..]` captures | |
1495 | // arrays of lengths `>= 1` whereas `[..]` captures any length. | |
1496 | while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) { | |
1497 | prefix.pop(); | |
1498 | } | |
1499 | while subpatterns.peek().is_some() | |
1500 | && is_wildcard(subpatterns.peek().unwrap()) | |
1501 | { | |
1502 | subpatterns.next(); | |
1503 | } | |
fc512014 | 1504 | } |
c295e0f8 XL |
1505 | let suffix: Vec<_> = subpatterns.collect(); |
1506 | let wild = Pat::wildcard_from_ty(self.ty); | |
1507 | PatKind::Slice { prefix, slice: Some(wild), suffix } | |
fc512014 | 1508 | } |
fc512014 | 1509 | } |
c295e0f8 | 1510 | } |
fc512014 XL |
1511 | &Str(value) => PatKind::Constant { value }, |
1512 | &FloatRange(lo, hi, end) => PatKind::Range(PatRange { lo, hi, end }), | |
c295e0f8 XL |
1513 | IntRange(range) => return range.to_pat(cx.tcx, self.ty), |
1514 | Wildcard | NonExhaustive => PatKind::Wild, | |
1515 | Missing { .. } => bug!( | |
1516 | "trying to convert a `Missing` constructor into a `Pat`; this is probably a bug, | |
1517 | `Missing` should have been processed in `apply_constructors`" | |
fc512014 | 1518 | ), |
c295e0f8 XL |
1519 | Opaque | Or => { |
1520 | bug!("can't convert to pattern: {:?}", self) | |
1521 | } | |
fc512014 XL |
1522 | }; |
1523 | ||
c295e0f8 | 1524 | Pat { ty: self.ty, span: DUMMY_SP, kind: Box::new(pat) } |
fc512014 XL |
1525 | } |
1526 | ||
c295e0f8 XL |
1527 | pub(super) fn is_or_pat(&self) -> bool { |
1528 | matches!(self.ctor, Or) | |
fc512014 XL |
1529 | } |
1530 | ||
c295e0f8 XL |
1531 | pub(super) fn ctor(&self) -> &Constructor<'tcx> { |
1532 | &self.ctor | |
fc512014 | 1533 | } |
c295e0f8 XL |
1534 | pub(super) fn ty(&self) -> Ty<'tcx> { |
1535 | self.ty | |
fc512014 | 1536 | } |
c295e0f8 XL |
1537 | pub(super) fn span(&self) -> Span { |
1538 | self.span | |
fc512014 XL |
1539 | } |
1540 | ||
c295e0f8 XL |
1541 | pub(super) fn iter_fields<'a>( |
1542 | &'a self, | |
1543 | ) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> { | |
1544 | self.fields.iter_patterns() | |
1545 | } | |
fc512014 | 1546 | |
c295e0f8 XL |
1547 | /// Specialize this pattern with a constructor. |
1548 | /// `other_ctor` can be different from `self.ctor`, but must be covered by it. | |
1549 | pub(super) fn specialize<'a>( | |
1550 | &'a self, | |
1551 | cx: &MatchCheckCtxt<'p, 'tcx>, | |
1552 | other_ctor: &Constructor<'tcx>, | |
1553 | ) -> SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]> { | |
1554 | match (&self.ctor, other_ctor) { | |
1555 | (Wildcard, _) => { | |
1556 | // We return a wildcard for each field of `other_ctor`. | |
1557 | Fields::wildcards(cx, self.ty, other_ctor).iter_patterns().collect() | |
fc512014 | 1558 | } |
c295e0f8 XL |
1559 | (Slice(self_slice), Slice(other_slice)) |
1560 | if self_slice.arity() != other_slice.arity() => | |
1561 | { | |
1562 | // The only tricky case: two slices of different arity. Since `self_slice` covers | |
1563 | // `other_slice`, `self_slice` must be `VarLen`, i.e. of the form | |
1564 | // `[prefix, .., suffix]`. Moreover `other_slice` is guaranteed to have a larger | |
1565 | // arity. So we fill the middle part with enough wildcards to reach the length of | |
1566 | // the new, larger slice. | |
1567 | match self_slice.kind { | |
1568 | FixedLen(_) => bug!("{:?} doesn't cover {:?}", self_slice, other_slice), | |
1569 | VarLen(prefix, suffix) => { | |
1570 | let inner_ty = match *self.ty.kind() { | |
1571 | ty::Slice(ty) | ty::Array(ty, _) => ty, | |
1572 | _ => bug!("bad slice pattern {:?} {:?}", self.ctor, self.ty), | |
1573 | }; | |
1574 | let prefix = &self.fields.fields[..prefix]; | |
1575 | let suffix = &self.fields.fields[self_slice.arity() - suffix..]; | |
1576 | let wildcard: &_ = | |
1577 | cx.pattern_arena.alloc(DeconstructedPat::wildcard(inner_ty)); | |
1578 | let extra_wildcards = other_slice.arity() - self_slice.arity(); | |
1579 | let extra_wildcards = (0..extra_wildcards).map(|_| wildcard); | |
1580 | prefix.iter().chain(extra_wildcards).chain(suffix).collect() | |
fc512014 XL |
1581 | } |
1582 | } | |
1583 | } | |
c295e0f8 | 1584 | _ => self.fields.iter_patterns().collect(), |
fc512014 | 1585 | } |
fc512014 XL |
1586 | } |
1587 | ||
c295e0f8 XL |
1588 | /// We keep track for each pattern if it was ever reachable during the analysis. This is used |
1589 | /// with `unreachable_spans` to report unreachable subpatterns arising from or patterns. | |
1590 | pub(super) fn set_reachable(&self) { | |
1591 | self.reachable.set(true) | |
1592 | } | |
1593 | pub(super) fn is_reachable(&self) -> bool { | |
1594 | self.reachable.get() | |
1595 | } | |
fc512014 | 1596 | |
c295e0f8 XL |
1597 | /// Report the spans of subpatterns that were not reachable, if any. |
1598 | pub(super) fn unreachable_spans(&self) -> Vec<Span> { | |
1599 | let mut spans = Vec::new(); | |
1600 | self.collect_unreachable_spans(&mut spans); | |
1601 | spans | |
1602 | } | |
1603 | ||
1604 | fn collect_unreachable_spans(&self, spans: &mut Vec<Span>) { | |
1605 | // We don't look at subpatterns if we already reported the whole pattern as unreachable. | |
1606 | if !self.is_reachable() { | |
1607 | spans.push(self.span); | |
1608 | } else { | |
1609 | for p in self.iter_fields() { | |
1610 | p.collect_unreachable_spans(spans); | |
fc512014 | 1611 | } |
fc512014 XL |
1612 | } |
1613 | } | |
c295e0f8 | 1614 | } |
fc512014 | 1615 | |
c295e0f8 XL |
1616 | /// This is mostly copied from the `Pat` impl. This is best effort and not good enough for a |
1617 | /// `Display` impl. | |
1618 | impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> { | |
1619 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1620 | // Printing lists is a chore. | |
1621 | let mut first = true; | |
1622 | let mut start_or_continue = |s| { | |
1623 | if first { | |
1624 | first = false; | |
1625 | "" | |
1626 | } else { | |
1627 | s | |
fc512014 | 1628 | } |
c295e0f8 XL |
1629 | }; |
1630 | let mut start_or_comma = || start_or_continue(", "); | |
1631 | ||
1632 | match &self.ctor { | |
1633 | Single | Variant(_) => match self.ty.kind() { | |
1634 | ty::Adt(def, _) if def.is_box() => { | |
1635 | // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside | |
1636 | // of `std`). So this branch is only reachable when the feature is enabled and | |
1637 | // the pattern is a box pattern. | |
1638 | let subpattern = self.iter_fields().next().unwrap(); | |
1639 | write!(f, "box {:?}", subpattern) | |
1640 | } | |
1641 | ty::Adt(..) | ty::Tuple(..) => { | |
1642 | let variant = match self.ty.kind() { | |
1643 | ty::Adt(adt, _) => { | |
1644 | Some(&adt.variants[self.ctor.variant_index_for_adt(adt)]) | |
1645 | } | |
1646 | ty::Tuple(_) => None, | |
1647 | _ => unreachable!(), | |
1648 | }; | |
1649 | ||
1650 | if let Some(variant) = variant { | |
1651 | write!(f, "{}", variant.ident)?; | |
1652 | } | |
1653 | ||
1654 | // Without `cx`, we can't know which field corresponds to which, so we can't | |
1655 | // get the names of the fields. Instead we just display everything as a suple | |
1656 | // struct, which should be good enough. | |
1657 | write!(f, "(")?; | |
1658 | for p in self.iter_fields() { | |
1659 | write!(f, "{}", start_or_comma())?; | |
1660 | write!(f, "{:?}", p)?; | |
1661 | } | |
1662 | write!(f, ")") | |
1663 | } | |
1664 | // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should | |
1665 | // be careful to detect strings here. However a string literal pattern will never | |
1666 | // be reported as a non-exhaustiveness witness, so we can ignore this issue. | |
1667 | ty::Ref(_, _, mutbl) => { | |
1668 | let subpattern = self.iter_fields().next().unwrap(); | |
1669 | write!(f, "&{}{:?}", mutbl.prefix_str(), subpattern) | |
1670 | } | |
1671 | _ => write!(f, "_"), | |
1672 | }, | |
1673 | Slice(slice) => { | |
1674 | let mut subpatterns = self.fields.iter_patterns(); | |
1675 | write!(f, "[")?; | |
1676 | match slice.kind { | |
1677 | FixedLen(_) => { | |
1678 | for p in subpatterns { | |
1679 | write!(f, "{}{:?}", start_or_comma(), p)?; | |
1680 | } | |
1681 | } | |
1682 | VarLen(prefix_len, _) => { | |
1683 | for p in subpatterns.by_ref().take(prefix_len) { | |
1684 | write!(f, "{}{:?}", start_or_comma(), p)?; | |
1685 | } | |
1686 | write!(f, "{}", start_or_comma())?; | |
1687 | write!(f, "..")?; | |
1688 | for p in subpatterns { | |
1689 | write!(f, "{}{:?}", start_or_comma(), p)?; | |
1690 | } | |
1691 | } | |
1692 | } | |
1693 | write!(f, "]") | |
1694 | } | |
1695 | &FloatRange(lo, hi, end) => { | |
1696 | write!(f, "{}", lo)?; | |
1697 | write!(f, "{}", end)?; | |
1698 | write!(f, "{}", hi) | |
fc512014 | 1699 | } |
c295e0f8 XL |
1700 | IntRange(range) => write!(f, "{:?}", range), // Best-effort, will render e.g. `false` as `0..=0` |
1701 | Wildcard | Missing { .. } | NonExhaustive => write!(f, "_ : {:?}", self.ty), | |
1702 | Or => { | |
1703 | for pat in self.iter_fields() { | |
1704 | write!(f, "{}{:?}", start_or_continue(" | "), pat)?; | |
1705 | } | |
1706 | Ok(()) | |
fc512014 | 1707 | } |
c295e0f8 XL |
1708 | Str(value) => write!(f, "{}", value), |
1709 | Opaque => write!(f, "<constant pattern>"), | |
fc512014 XL |
1710 | } |
1711 | } | |
1712 | } |