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.
6 //! There's one idea that is not detailed in [`super::usefulness`] because the details are not
7 //! needed there: _constructor splitting_.
9 //! # Constructor splitting
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:
17 //! match (0, false) {
18 //! (0 ..=100, true) => {} // `p_1`
19 //! (50..=150, false) => {} // `p_2`
20 //! (0 ..=200, _) => {} // `q`
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
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.
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.
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`].
45 use self::Constructor::*;
46 use self::SliceKind::*;
48 use super::compare_const_vals;
49 use super::usefulness::{MatchCheckCtxt, PatCtxt};
50 use super::{FieldPat, Pat, PatKind, PatRange};
52 use rustc_data_structures::captures::Captures;
53 use rustc_index::vec::Idx;
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};
66 use smallvec::{smallvec, SmallVec};
67 use std::cmp::{self, max, min, Ordering};
68 use std::iter::{once, IntoIterator};
69 use std::ops::RangeInclusive;
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.
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>,
88 fn is_integral(ty: Ty<'_>) -> bool {
89 matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_) | ty::Bool)
92 fn is_singleton(&self) -> bool {
93 self.range.start() == self.range.end()
96 fn boundaries(&self) -> (u128, u128) {
97 (*self.range.start(), *self.range.end())
101 fn integral_size_and_signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> Option<(Size, u128)> {
103 ty::Bool => Some((Size::from_bytes(1), 0)),
104 ty::Char => Some((Size::from_bytes(4), 0)),
106 let size = Integer::from_attr(&tcx, SignedInt(ity)).size();
107 Some((size, 1u128 << (size.bits() as u128 - 1)))
109 ty::Uint(uty) => Some((Integer::from_attr(&tcx, UnsignedInt(uty)).size(), 0)),
117 param_env: ty::ParamEnv<'tcx>,
119 ) -> Option<IntRange> {
120 if let Some((target_size, bias)) = Self::integral_size_and_signed_bias(tcx, value.ty) {
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) {
132 // This is a more general form of the previous case.
133 value.try_eval_bits(tcx, param_env, ty)
135 let val = val ^ bias;
136 Some(IntRange { range: val..=val })
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));
160 Some(IntRange { range: lo..=(hi - offset) })
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 {
170 let bits = Integer::from_attr(&tcx, SignedInt(ity)).size().bits() as u128;
177 fn is_subrange(&self, other: &Self) -> bool {
178 other.range.start() <= self.range.start() && self.range.end() <= other.range.end()
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) })
191 fn suspicious_intersection(&self, other: &Self) -> bool {
192 // `false` in the following cases:
193 // 1 ---- // 1 ---------- // 1 ---- // 1 ----
194 // 2 ---------- // 2 ---- // 2 ---- // 2 ----
196 // The following are currently `false`, but could be `true` in the future (#64007):
197 // 1 --------- // 1 ---------
198 // 2 ---------- // 2 ----------
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()
208 fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> {
209 let (lo, hi) = self.boundaries();
211 let bias = IntRange::signed_bias(tcx, ty);
212 let (lo, hi) = (lo ^ bias, hi ^ bias);
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);
218 let kind = if lo == hi {
219 PatKind::Constant { value: lo_const }
221 PatKind::Range(PatRange { lo: lo_const, hi: hi_const, end: RangeEnd::Included })
224 Pat { ty, span: DUMMY_SP, kind: Box::new(kind) }
227 /// Lint on likely incorrect range patterns (#63987)
228 pub(super) fn lint_overlapping_range_endpoints<'a, 'tcx: 'a>(
230 pcx: PatCtxt<'_, '_, 'tcx>,
231 ctors: impl Iterator<Item = (&'a Constructor<'tcx>, Span)>,
235 if self.is_singleton() {
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
244 // match (0u8, true) {
245 // (0 ..= 125, false) => {}
246 // (125 ..= 255, true) => {}
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))
259 if !overlaps.is_empty() {
260 pcx.cx.tcx.struct_span_lint_hir(
261 lint::builtin::OVERLAPPING_RANGE_ENDPOINTS,
265 let mut err = lint.build("multiple patterns overlap on their endpoints");
266 for (int_range, span) in overlaps {
270 "this range overlaps on `{}`...",
271 int_range.to_pat(pcx.cx.tcx, pcx.ty)
275 err.span_label(pcx.span, "... with this range");
276 err.note("you likely meant to write mutually exclusive ranges");
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
288 assert!(self.is_subrange(other));
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)]
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.
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.
311 /// The following input:
313 /// |-------------------------| // `self`
314 /// |------| |----------| |----|
315 /// |-------| |-------|
317 /// would be iterated over as follows:
319 /// ||---|--||-|---|---|---|--|
321 #[derive(Debug, Clone)]
322 struct SplitIntRange {
323 /// The range we are splitting
325 /// The borders of ranges we have seen. They are all contained within `range`. This is kept
327 borders: Vec<IntBorder>,
331 fn new(range: IntRange) -> Self {
332 SplitIntRange { range, borders: Vec::new() }
336 fn to_borders(r: IntRange) -> [IntBorder; 2] {
338 let (lo, hi) = r.boundaries();
339 let lo = JustBefore(lo);
340 let hi = match hi.checked_add(1) {
341 Some(m) => JustBefore(m),
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]))
355 self.borders.extend(included_borders);
356 self.borders.sort_unstable();
359 /// Iterate over the contained ranges.
360 fn iter<'a>(&'a self) -> impl Iterator<Item = IntRange> + Captures<'a> {
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];
369 // End with the end of the range.
370 .chain(once(self_range[1]))
371 // List pairs of adjacent borders.
373 let ret = (prev_border, border);
374 prev_border = border;
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
391 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
393 /// Patterns of length `n` (`[x, y]`).
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 `_`.
404 fn arity(self) -> u64 {
406 FixedLen(length) => length,
407 VarLen(prefix, suffix) => prefix + suffix,
411 /// Whether this pattern includes patterns of length `other_len`.
412 fn covers_length(self, other_len: u64) -> bool {
414 FixedLen(len) => len == other_len,
415 VarLen(prefix, suffix) => prefix + suffix <= other_len,
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]`.
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),
436 Slice { array_len, kind }
439 fn arity(self) -> u64 {
443 /// See `Constructor::is_covered_by`
444 fn is_covered_by(self, other: Self) -> bool {
445 other.kind.covers_length(self.arity())
449 /// This computes constructor splitting for variable-length slices, as explained at the top of the
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
458 /// Let's look at an example, where we are trying to split the last pattern:
461 /// [true, true, ..] => {}
462 /// [.., false, false] => {}
466 /// Here are the results of specialization for the first few lengths:
473 /// [true, true] => {}
474 /// [false, false] => {}
477 /// [true, true, _ ] => {}
478 /// [_, false, false] => {}
481 /// [true, true, _, _ ] => {}
482 /// [_, _, false, false] => {}
483 /// [_, _, _, _ ] => {}
485 /// [true, true, _, _, _ ] => {}
486 /// [_, _, _, false, false] => {}
487 /// [_, _, _, _, _ ] => {}
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.
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`.
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.
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))`
509 /// `max_slice` below will be made to have arity `L`.
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.
516 /// The smallest slice bigger than any slice seen. `max_slice.arity()` is the length `L`
518 max_slice: SliceKind,
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) }
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
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 {
539 max_fixed_len = cmp::max(max_fixed_len, len);
541 VarLen(prefix, suffix) => {
542 *max_prefix_len = cmp::max(*max_prefix_len, prefix);
543 *max_suffix_len = cmp::max(*max_suffix_len, suffix);
547 // We want `L = max(L, max_fixed_len + 1)`, modulo the fact that we keep prefix and
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;
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),
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
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(),
576 .chain(once(self.max_slice))
577 .map(move |kind| Slice::new(self.array_len, kind))
581 /// A value can be decomposed into a constructor applied to some fields. This struct represents
582 /// the constructor. See also `Fields`.
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
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.
595 /// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
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.
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.
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`.
610 /// Stands for constructors that are not seen in the matrix, as explained in the documentation
611 /// for [`SplitWildcard`].
613 /// Wildcard pattern.
617 impl<'tcx> Constructor<'tcx> {
618 pub(super) fn is_wildcard(&self) -> bool {
619 matches!(self, Wildcard)
622 fn as_int_range(&self) -> Option<&IntRange> {
624 IntRange(range) => Some(range),
629 fn as_slice(&self) -> Option<Slice> {
631 Slice(slice) => Some(*slice),
636 fn variant_index_for_adt(&self, adt: &'tcx ty::AdtDef) -> VariantIdx {
638 Variant(id) => adt.variant_index_with_id(id),
640 assert!(!adt.is_enum());
643 _ => bug!("bad constructor {:?} for adt {:?}", self, adt),
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)
656 PatKind::Constant { value } => {
657 if let Some(int_range) = IntRange::from_const(cx.tcx, cx.param_env, value) {
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
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
673 &PatKind::Range(PatRange { lo, hi, end }) => {
675 if let Some(int_range) = IntRange::from_range(
677 lo.eval_bits(cx.tcx, cx.param_env, lo.ty),
678 hi.eval_bits(cx.tcx, cx.param_env, hi.ty),
684 FloatRange(lo, hi, end)
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),
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)
698 FixedLen(prefix + suffix)
700 Slice(Slice::new(array_len, kind))
702 PatKind::Or { .. } => bug!("Or-pattern should have been expanded earlier on."),
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.
714 /// See the branches for details on how the splitting is done.
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>(
721 pcx: PatCtxt<'_, '_, 'tcx>,
722 ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
723 ) -> SmallVec<[Self; 1]>
729 let mut split_wildcard = SplitWildcard::new(pcx);
730 split_wildcard.split(pcx, ctors);
731 split_wildcard.into_ctors(pcx)
733 // Fast-track if the range is trivial. In particular, we don't do the overlapping
735 IntRange(ctor_range) if !ctor_range.is_singleton() => {
736 let mut split_range = SplitIntRange::new(ctor_range.clone());
737 let int_ranges = ctors.filter_map(|ctor| ctor.as_int_range());
738 split_range.split(int_ranges.cloned());
739 split_range.iter().map(IntRange).collect()
741 &Slice(Slice { kind: VarLen(self_prefix, self_suffix), array_len }) => {
742 let mut split_self = SplitVarLenSlice::new(self_prefix, self_suffix, array_len);
743 let slices = ctors.filter_map(|c| c.as_slice()).map(|s| s.kind);
744 split_self.split(slices);
745 split_self.iter().map(Slice).collect()
747 // Any other constructor can be used unchanged.
748 _ => smallvec![self.clone()],
752 /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
753 /// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
754 /// this checks for inclusion.
755 // We inline because this has a single call site in `Matrix::specialize_constructor`.
757 pub(super) fn is_covered_by<'p>(&self, pcx: PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool {
758 // This must be kept in sync with `is_covered_by_any`.
759 match (self, other) {
760 // Wildcards cover anything
761 (_, Wildcard) => true,
762 // The missing ctors are not covered by anything in the matrix except wildcards.
763 (Missing | Wildcard, _) => false,
765 (Single, Single) => true,
766 (Variant(self_id), Variant(other_id)) => self_id == other_id,
768 (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range),
770 FloatRange(self_from, self_to, self_end),
771 FloatRange(other_from, other_to, other_end),
774 compare_const_vals(pcx.cx.tcx, self_to, other_to, pcx.cx.param_env, pcx.ty),
775 compare_const_vals(pcx.cx.tcx, self_from, other_from, pcx.cx.param_env, pcx.ty),
777 (Some(to), Some(from)) => {
778 (from == Ordering::Greater || from == Ordering::Equal)
779 && (to == Ordering::Less
780 || (other_end == self_end && to == Ordering::Equal))
785 (Str(self_val), Str(other_val)) => {
786 // FIXME: there's probably a more direct way of comparing for equality
787 match compare_const_vals(pcx.cx.tcx, self_val, other_val, pcx.cx.param_env, pcx.ty)
789 Some(comparison) => comparison == Ordering::Equal,
793 (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
795 // We are trying to inspect an opaque constant. Thus we skip the row.
796 (Opaque, _) | (_, Opaque) => false,
797 // Only a wildcard pattern can match the special extra constructor.
798 (NonExhaustive, _) => false,
802 "trying to compare incompatible constructors {:?} and {:?}",
809 /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is
810 /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is
811 /// assumed to have been split from a wildcard.
812 fn is_covered_by_any<'p>(
814 pcx: PatCtxt<'_, 'p, 'tcx>,
815 used_ctors: &[Constructor<'tcx>],
817 if used_ctors.is_empty() {
821 // This must be kept in sync with `is_covered_by`.
823 // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s.
824 Single => !used_ctors.is_empty(),
825 Variant(_) => used_ctors.iter().any(|c| c == self),
826 IntRange(range) => used_ctors
828 .filter_map(|c| c.as_int_range())
829 .any(|other| range.is_covered_by(other)),
830 Slice(slice) => used_ctors
832 .filter_map(|c| c.as_slice())
833 .any(|other| slice.is_covered_by(other)),
834 // This constructor is never covered by anything else
835 NonExhaustive => false,
836 Str(..) | FloatRange(..) | Opaque | Missing | Wildcard => {
837 span_bug!(pcx.span, "found unexpected ctor in all_ctors: {:?}", self)
843 /// A wildcard constructor that we split relative to the constructors in the matrix, as explained
844 /// at the top of the file.
846 /// A constructor that is not present in the matrix rows will only be covered by the rows that have
847 /// wildcards. Thus we can group all of those constructors together; we call them "missing
848 /// constructors". Splitting a wildcard would therefore list all present constructors individually
849 /// (or grouped if they are integers or slices), and then all missing constructors together as a
852 /// However we can go further: since any constructor will match the wildcard rows, and having more
853 /// rows can only reduce the amount of usefulness witnesses, we can skip the present constructors
854 /// and only try the missing ones.
855 /// This will not preserve the whole list of witnesses, but will preserve whether the list is empty
856 /// or not. In fact this is quite natural from the point of view of diagnostics too. This is done
857 /// in `to_ctors`: in some cases we only return `Missing`.
859 pub(super) struct SplitWildcard<'tcx> {
860 /// Constructors seen in the matrix.
861 matrix_ctors: Vec<Constructor<'tcx>>,
862 /// All the constructors for this type
863 all_ctors: SmallVec<[Constructor<'tcx>; 1]>,
866 impl<'tcx> SplitWildcard<'tcx> {
867 pub(super) fn new<'p>(pcx: PatCtxt<'_, 'p, 'tcx>) -> Self {
868 debug!("SplitWildcard::new({:?})", pcx.ty);
870 let make_range = |start, end| {
872 // `unwrap()` is ok because we know the type is an integer.
873 IntRange::from_range(cx.tcx, start, end, pcx.ty, &RangeEnd::Included).unwrap(),
876 // This determines the set of all possible constructors for the type `pcx.ty`. For numbers,
877 // arrays and slices we use ranges and variable-length slices when appropriate.
879 // If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that
880 // are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the
881 // returned list of constructors.
882 // Invariant: this is empty if and only if the type is uninhabited (as determined by
883 // `cx.is_uninhabited()`).
884 let all_ctors = match pcx.ty.kind() {
885 ty::Bool => smallvec![make_range(0, 1)],
886 ty::Array(sub_ty, len) if len.try_eval_usize(cx.tcx, cx.param_env).is_some() => {
887 let len = len.eval_usize(cx.tcx, cx.param_env);
888 if len != 0 && cx.is_uninhabited(sub_ty) {
891 smallvec![Slice(Slice::new(Some(len), VarLen(0, 0)))]
894 // Treat arrays of a constant but unknown length like slices.
895 ty::Array(sub_ty, _) | ty::Slice(sub_ty) => {
896 let kind = if cx.is_uninhabited(sub_ty) { FixedLen(0) } else { VarLen(0, 0) };
897 smallvec![Slice(Slice::new(None, kind))]
899 ty::Adt(def, substs) if def.is_enum() => {
900 // If the enum is declared as `#[non_exhaustive]`, we treat it as if it had an
901 // additional "unknown" constructor.
902 // There is no point in enumerating all possible variants, because the user can't
903 // actually match against them all themselves. So we always return only the fictitious
905 // E.g., in an example like:
908 // let err: io::ErrorKind = ...;
910 // io::ErrorKind::NotFound => {},
914 // we don't want to show every possible IO error, but instead have only `_` as the
916 let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(pcx.ty);
918 // If `exhaustive_patterns` is disabled and our scrutinee is an empty enum, we treat it
919 // as though it had an "unknown" constructor to avoid exposing its emptiness. The
920 // exception is if the pattern is at the top level, because we want empty matches to be
921 // considered exhaustive.
922 let is_secretly_empty = def.variants.is_empty()
923 && !cx.tcx.features().exhaustive_patterns
924 && !pcx.is_top_level;
926 if is_secretly_empty || is_declared_nonexhaustive {
927 smallvec![NonExhaustive]
928 } else if cx.tcx.features().exhaustive_patterns {
929 // If `exhaustive_patterns` is enabled, we exclude variants known to be
934 !v.uninhabited_from(cx.tcx, substs, def.adt_kind(), cx.param_env)
935 .contains(cx.tcx, cx.module)
937 .map(|v| Variant(v.def_id))
940 def.variants.iter().map(|v| Variant(v.def_id)).collect()
945 // The valid Unicode Scalar Value ranges.
946 make_range('\u{0000}' as u128, '\u{D7FF}' as u128),
947 make_range('\u{E000}' as u128, '\u{10FFFF}' as u128),
950 ty::Int(_) | ty::Uint(_)
951 if pcx.ty.is_ptr_sized_integral()
952 && !cx.tcx.features().precise_pointer_size_matching =>
954 // `usize`/`isize` are not allowed to be matched exhaustively unless the
955 // `precise_pointer_size_matching` feature is enabled. So we treat those types like
956 // `#[non_exhaustive]` enums by returning a special unmatcheable constructor.
957 smallvec![NonExhaustive]
960 let bits = Integer::from_attr(&cx.tcx, SignedInt(ity)).size().bits() as u128;
961 let min = 1u128 << (bits - 1);
963 smallvec![make_range(min, max)]
966 let size = Integer::from_attr(&cx.tcx, UnsignedInt(uty)).size();
967 let max = size.truncate(u128::MAX);
968 smallvec![make_range(0, max)]
970 // If `exhaustive_patterns` is disabled and our scrutinee is the never type, we cannot
971 // expose its emptiness. The exception is if the pattern is at the top level, because we
972 // want empty matches to be considered exhaustive.
973 ty::Never if !cx.tcx.features().exhaustive_patterns && !pcx.is_top_level => {
974 smallvec![NonExhaustive]
976 ty::Never => smallvec![],
977 _ if cx.is_uninhabited(pcx.ty) => smallvec![],
978 ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => smallvec![Single],
979 // This type is one for which we cannot list constructors, like `str` or `f64`.
980 _ => smallvec![NonExhaustive],
982 SplitWildcard { matrix_ctors: Vec::new(), all_ctors }
985 /// Pass a set of constructors relative to which to split this one. Don't call twice, it won't
986 /// do what you want.
987 pub(super) fn split<'a>(
989 pcx: PatCtxt<'_, '_, 'tcx>,
990 ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
994 // Since `all_ctors` never contains wildcards, this won't recurse further.
996 self.all_ctors.iter().flat_map(|ctor| ctor.split(pcx, ctors.clone())).collect();
997 self.matrix_ctors = ctors.filter(|c| !c.is_wildcard()).cloned().collect();
1000 /// Whether there are any value constructors for this type that are not present in the matrix.
1001 fn any_missing(&self, pcx: PatCtxt<'_, '_, 'tcx>) -> bool {
1002 self.iter_missing(pcx).next().is_some()
1005 /// Iterate over the constructors for this type that are not present in the matrix.
1006 pub(super) fn iter_missing<'a, 'p>(
1008 pcx: PatCtxt<'a, 'p, 'tcx>,
1009 ) -> impl Iterator<Item = &'a Constructor<'tcx>> + Captures<'p> {
1010 self.all_ctors.iter().filter(move |ctor| !ctor.is_covered_by_any(pcx, &self.matrix_ctors))
1013 /// Return the set of constructors resulting from splitting the wildcard. As explained at the
1014 /// top of the file, if any constructors are missing we can ignore the present ones.
1015 fn into_ctors(self, pcx: PatCtxt<'_, '_, 'tcx>) -> SmallVec<[Constructor<'tcx>; 1]> {
1016 if self.any_missing(pcx) {
1017 // Some constructors are missing, thus we can specialize with the special `Missing`
1018 // constructor, which stands for those constructors that are not seen in the matrix,
1019 // and matches the same rows as any of them (namely the wildcard rows). See the top of
1020 // the file for details.
1021 // However, when all constructors are missing we can also specialize with the full
1022 // `Wildcard` constructor. The difference will depend on what we want in diagnostics.
1024 // If some constructors are missing, we typically want to report those constructors,
1027 // enum Direction { N, S, E, W }
1028 // let Direction::N = ...;
1030 // we can report 3 witnesses: `S`, `E`, and `W`.
1032 // However, if the user didn't actually specify a constructor
1033 // in this arm, e.g., in
1035 // let x: (Direction, Direction, bool) = ...;
1036 // let (_, _, false) = x;
1038 // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>,
1039 // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we
1040 // prefer to report just a wildcard `_`.
1042 // The exception is: if we are at the top-level, for example in an empty match, we
1043 // sometimes prefer reporting the list of constructors instead of just `_`.
1044 let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(pcx.ty);
1045 let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing {
1050 return smallvec![ctor];
1053 // All the constructors are present in the matrix, so we just go through them all.
1058 /// Some fields need to be explicitly hidden away in certain cases; see the comment above the
1059 /// `Fields` struct. This struct represents such a potentially-hidden field.
1060 #[derive(Debug, Copy, Clone)]
1061 pub(super) enum FilteredField<'p, 'tcx> {
1062 Kept(&'p Pat<'tcx>),
1066 impl<'p, 'tcx> FilteredField<'p, 'tcx> {
1067 fn kept(self) -> Option<&'p Pat<'tcx>> {
1069 FilteredField::Kept(p) => Some(p),
1070 FilteredField::Hidden => None,
1075 /// A value can be decomposed into a constructor applied to some fields. This struct represents
1076 /// those fields, generalized to allow patterns in each field. See also `Constructor`.
1077 /// This is constructed from a constructor using [`Fields::wildcards()`].
1079 /// If a private or `non_exhaustive` field is uninhabited, the code mustn't observe that it is
1080 /// uninhabited. For that, we filter these fields out of the matrix. This is handled automatically
1081 /// in `Fields`. This filtering is uncommon in practice, because uninhabited fields are rarely used,
1082 /// so we avoid it when possible to preserve performance.
1083 #[derive(Debug, Clone)]
1084 pub(super) enum Fields<'p, 'tcx> {
1085 /// Lists of patterns that don't contain any filtered fields.
1086 /// `Slice` and `Vec` behave the same; the difference is only to avoid allocating and
1087 /// triple-dereferences when possible. Frankly this is premature optimization, I (Nadrieril)
1088 /// have not measured if it really made a difference.
1089 Slice(&'p [Pat<'tcx>]),
1090 Vec(SmallVec<[&'p Pat<'tcx>; 2]>),
1091 /// Patterns where some of the fields need to be hidden. For all intents and purposes we only
1092 /// care about the non-hidden fields. We need to keep the real field index for those fields;
1093 /// we're morally storing a `Vec<(usize, &Pat)>` but what we do is more convenient.
1094 /// `len` counts the number of non-hidden fields
1096 fields: SmallVec<[FilteredField<'p, 'tcx>; 2]>,
1101 impl<'p, 'tcx> Fields<'p, 'tcx> {
1102 /// Internal use. Use `Fields::wildcards()` instead.
1103 /// Must not be used if the pattern is a field of a struct/tuple/variant.
1104 fn from_single_pattern(pat: &'p Pat<'tcx>) -> Self {
1105 Fields::Slice(std::slice::from_ref(pat))
1108 /// Convenience; internal use.
1109 fn wildcards_from_tys(
1110 cx: &MatchCheckCtxt<'p, 'tcx>,
1111 tys: impl IntoIterator<Item = Ty<'tcx>>,
1113 let wilds = tys.into_iter().map(Pat::wildcard_from_ty);
1114 let pats = cx.pattern_arena.alloc_from_iter(wilds);
1118 /// Creates a new list of wildcard fields for a given constructor.
1119 pub(super) fn wildcards(pcx: PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self {
1122 let wildcard_from_ty = |ty| &*cx.pattern_arena.alloc(Pat::wildcard_from_ty(ty));
1124 let ret = match constructor {
1125 Single | Variant(_) => match ty.kind() {
1126 ty::Tuple(ref fs) => {
1127 Fields::wildcards_from_tys(cx, fs.into_iter().map(|ty| ty.expect_ty()))
1129 ty::Ref(_, rty, _) => Fields::from_single_pattern(wildcard_from_ty(rty)),
1130 ty::Adt(adt, substs) => {
1132 // Use T as the sub pattern type of Box<T>.
1133 Fields::from_single_pattern(wildcard_from_ty(substs.type_at(0)))
1135 let variant = &adt.variants[constructor.variant_index_for_adt(adt)];
1136 // Whether we must not match the fields of this variant exhaustively.
1137 let is_non_exhaustive =
1138 variant.is_field_list_non_exhaustive() && !adt.did.is_local();
1139 let field_tys = variant.fields.iter().map(|field| field.ty(cx.tcx, substs));
1140 // In the following cases, we don't need to filter out any fields. This is
1141 // the vast majority of real cases, since uninhabited fields are uncommon.
1142 let has_no_hidden_fields = (adt.is_enum() && !is_non_exhaustive)
1143 || !field_tys.clone().any(|ty| cx.is_uninhabited(ty));
1145 if has_no_hidden_fields {
1146 Fields::wildcards_from_tys(cx, field_tys)
1149 let fields = variant
1153 let ty = field.ty(cx.tcx, substs);
1154 let is_visible = adt.is_enum()
1155 || field.vis.is_accessible_from(cx.module, cx.tcx);
1156 let is_uninhabited = cx.is_uninhabited(ty);
1158 // In the cases of either a `#[non_exhaustive]` field list
1159 // or a non-public field, we hide uninhabited fields in
1160 // order not to reveal the uninhabitedness of the whole
1162 if is_uninhabited && (!is_visible || is_non_exhaustive) {
1163 FilteredField::Hidden
1166 FilteredField::Kept(wildcard_from_ty(ty))
1170 Fields::Filtered { fields, len }
1174 _ => bug!("Unexpected type for `Single` constructor: {:?}", ty),
1176 Slice(slice) => match *ty.kind() {
1177 ty::Slice(ty) | ty::Array(ty, _) => {
1178 let arity = slice.arity();
1179 Fields::wildcards_from_tys(cx, (0..arity).map(|_| ty))
1181 _ => bug!("bad slice pattern {:?} {:?}", constructor, ty),
1183 Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing
1184 | Wildcard => Fields::Slice(&[]),
1186 debug!("Fields::wildcards({:?}, {:?}) = {:#?}", constructor, ty, ret);
1190 /// Apply a constructor to a list of patterns, yielding a new pattern. `self`
1191 /// must have as many elements as this constructor's arity.
1193 /// This is roughly the inverse of `specialize_constructor`.
1196 /// `ctor`: `Constructor::Single`
1197 /// `ty`: `Foo(u32, u32, u32)`
1198 /// `self`: `[10, 20, _]`
1199 /// returns `Foo(10, 20, _)`
1201 /// `ctor`: `Constructor::Variant(Option::Some)`
1202 /// `ty`: `Option<bool>`
1203 /// `self`: `[false]`
1204 /// returns `Some(false)`
1205 pub(super) fn apply(self, pcx: PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Pat<'tcx> {
1206 let subpatterns_and_indices = self.patterns_and_indices();
1207 let mut subpatterns = subpatterns_and_indices.iter().map(|&(_, p)| p).cloned();
1209 let pat = match ctor {
1210 Single | Variant(_) => match pcx.ty.kind() {
1211 ty::Adt(..) | ty::Tuple(..) => {
1212 // We want the real indices here.
1213 let subpatterns = subpatterns_and_indices
1215 .map(|&(field, p)| FieldPat { field, pattern: p.clone() })
1218 if let ty::Adt(adt, substs) = pcx.ty.kind() {
1223 variant_index: ctor.variant_index_for_adt(adt),
1227 PatKind::Leaf { subpatterns }
1230 PatKind::Leaf { subpatterns }
1233 // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
1234 // be careful to reconstruct the correct constant pattern here. However a string
1235 // literal pattern will never be reported as a non-exhaustiveness witness, so we
1236 // can ignore this issue.
1237 ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
1238 ty::Slice(_) | ty::Array(..) => bug!("bad slice pattern {:?} {:?}", ctor, pcx.ty),
1241 Slice(slice) => match slice.kind {
1243 PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] }
1245 VarLen(prefix, _) => {
1246 let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix as usize).collect();
1247 if slice.array_len.is_some() {
1248 // Improves diagnostics a bit: if the type is a known-size array, instead
1249 // of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`.
1250 // This is incorrect if the size is not known, since `[_, ..]` captures
1251 // arrays of lengths `>= 1` whereas `[..]` captures any length.
1252 while !prefix.is_empty() && prefix.last().unwrap().is_wildcard() {
1256 let suffix: Vec<_> = if slice.array_len.is_some() {
1258 subpatterns.skip_while(Pat::is_wildcard).collect()
1260 subpatterns.collect()
1262 let wild = Pat::wildcard_from_ty(pcx.ty);
1263 PatKind::Slice { prefix, slice: Some(wild), suffix }
1266 &Str(value) => PatKind::Constant { value },
1267 &FloatRange(lo, hi, end) => PatKind::Range(PatRange { lo, hi, end }),
1268 IntRange(range) => return range.to_pat(pcx.cx.tcx, pcx.ty),
1269 NonExhaustive => PatKind::Wild,
1270 Wildcard => return Pat::wildcard_from_ty(pcx.ty),
1271 Opaque => bug!("we should not try to apply an opaque constructor"),
1273 "trying to apply the `Missing` constructor; this should have been done in `apply_constructors`"
1277 Pat { ty: pcx.ty, span: DUMMY_SP, kind: Box::new(pat) }
1280 /// Returns the number of patterns. This is the same as the arity of the constructor used to
1281 /// construct `self`.
1282 pub(super) fn len(&self) -> usize {
1284 Fields::Slice(pats) => pats.len(),
1285 Fields::Vec(pats) => pats.len(),
1286 Fields::Filtered { len, .. } => *len,
1290 /// Returns the list of patterns along with the corresponding field indices.
1291 fn patterns_and_indices(&self) -> SmallVec<[(Field, &'p Pat<'tcx>); 2]> {
1293 Fields::Slice(pats) => {
1294 pats.iter().enumerate().map(|(i, p)| (Field::new(i), p)).collect()
1296 Fields::Vec(pats) => {
1297 pats.iter().copied().enumerate().map(|(i, p)| (Field::new(i), p)).collect()
1299 Fields::Filtered { fields, .. } => {
1300 // Indices must be relative to the full list of patterns
1304 .filter_map(|(i, p)| Some((Field::new(i), p.kept()?)))
1310 /// Returns the list of patterns.
1311 pub(super) fn into_patterns(self) -> SmallVec<[&'p Pat<'tcx>; 2]> {
1313 Fields::Slice(pats) => pats.iter().collect(),
1314 Fields::Vec(pats) => pats,
1315 Fields::Filtered { fields, .. } => fields.iter().filter_map(|p| p.kept()).collect(),
1319 /// Overrides some of the fields with the provided patterns. Exactly like
1320 /// `replace_fields_indexed`, except that it takes `FieldPat`s as input.
1321 fn replace_with_fieldpats(
1323 new_pats: impl IntoIterator<Item = &'p FieldPat<'tcx>>,
1325 self.replace_fields_indexed(
1326 new_pats.into_iter().map(|pat| (pat.field.index(), &pat.pattern)),
1330 /// Overrides some of the fields with the provided patterns. This is used when a pattern
1331 /// defines some fields but not all, for example `Foo { field1: Some(_), .. }`: here we start
1332 /// with a `Fields` that is just one wildcard per field of the `Foo` struct, and override the
1333 /// entry corresponding to `field1` with the pattern `Some(_)`. This is also used for slice
1334 /// patterns for the same reason.
1335 fn replace_fields_indexed(
1337 new_pats: impl IntoIterator<Item = (usize, &'p Pat<'tcx>)>,
1339 let mut fields = self.clone();
1340 if let Fields::Slice(pats) = fields {
1341 fields = Fields::Vec(pats.iter().collect());
1345 Fields::Vec(pats) => {
1346 for (i, pat) in new_pats {
1350 Fields::Filtered { fields, .. } => {
1351 for (i, pat) in new_pats {
1352 if let FilteredField::Kept(p) = &mut fields[i] {
1357 Fields::Slice(_) => unreachable!(),
1362 /// Replaces contained fields with the given list of patterns. There must be `len()` patterns
1364 pub(super) fn replace_fields(
1366 cx: &MatchCheckCtxt<'p, 'tcx>,
1367 pats: impl IntoIterator<Item = Pat<'tcx>>,
1369 let pats: &[_] = cx.pattern_arena.alloc_from_iter(pats);
1372 Fields::Filtered { fields, len } => {
1373 let mut pats = pats.iter();
1374 let mut fields = fields.clone();
1375 for f in &mut fields {
1376 if let FilteredField::Kept(p) = f {
1377 // We take one input pattern for each `Kept` field, in order.
1378 *p = pats.next().unwrap();
1381 Fields::Filtered { fields, len: *len }
1383 _ => Fields::Slice(pats),
1387 /// Replaces contained fields with the arguments of the given pattern. Only use on a pattern
1388 /// that is compatible with the constructor used to build `self`.
1389 /// This is meant to be used on the result of `Fields::wildcards()`. The idea is that
1390 /// `wildcards` constructs a list of fields where all entries are wildcards, and the pattern
1391 /// provided to this function fills some of the fields with non-wildcards.
1392 /// In the following example `Fields::wildcards` would return `[_, _, _, _]`. If we call
1393 /// `replace_with_pattern_arguments` on it with the pattern, the result will be `[Some(0), _,
1396 /// let x: [Option<u8>; 4] = foo();
1398 /// [Some(0), ..] => {}
1401 /// This is guaranteed to preserve the number of patterns in `self`.
1402 pub(super) fn replace_with_pattern_arguments(&self, pat: &'p Pat<'tcx>) -> Self {
1403 match pat.kind.as_ref() {
1404 PatKind::Deref { subpattern } => {
1405 assert_eq!(self.len(), 1);
1406 Fields::from_single_pattern(subpattern)
1408 PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
1409 self.replace_with_fieldpats(subpatterns)
1411 PatKind::Array { prefix, suffix, .. } | PatKind::Slice { prefix, suffix, .. } => {
1412 // Number of subpatterns for the constructor
1413 let ctor_arity = self.len();
1415 // Replace the prefix and the suffix with the given patterns, leaving wildcards in
1416 // the middle if there was a subslice pattern `..`.
1417 let prefix = prefix.iter().enumerate();
1419 suffix.iter().enumerate().map(|(i, p)| (ctor_arity - suffix.len() + i, p));
1420 self.replace_fields_indexed(prefix.chain(suffix))