blob: 0c7c2c6f9b4b740a36460325dbc07606a018b845 [file] [log] [blame]
//! [`super::usefulness`] explains most of what is happening in this file. As explained there,
//! values and patterns are made from constructors applied to fields. This file defines a
//! `Constructor` enum, a `Fields` struct, and various operations to manipulate them and convert
//! them from/to patterns.
//!
//! There's one idea that is not detailed in [`super::usefulness`] because the details are not
//! needed there: _constructor splitting_.
//!
//! # Constructor splitting
//!
//! The idea is as follows: given a constructor `c` and a matrix, we want to specialize in turn
//! with all the value constructors that are covered by `c`, and compute usefulness for each.
//! Instead of listing all those constructors (which is intractable), we group those value
//! constructors together as much as possible. Example:
//!
//! ```compile_fail,E0004
//! match (0, false) {
//! (0 ..=100, true) => {} // `p_1`
//! (50..=150, false) => {} // `p_2`
//! (0 ..=200, _) => {} // `q`
//! }
//! ```
//!
//! The naive approach would try all numbers in the range `0..=200`. But we can be a lot more
//! clever: `0` and `1` for example will match the exact same rows, and return equivalent
//! witnesses. In fact all of `0..50` would. We can thus restrict our exploration to 4
//! constructors: `0..50`, `50..=100`, `101..=150` and `151..=200`. That is enough and infinitely
//! more tractable.
//!
//! We capture this idea in a function `split(p_1 ... p_n, c)` which returns a list of constructors
//! `c'` covered by `c`. Given such a `c'`, we require that all value ctors `c''` covered by `c'`
//! return an equivalent set of witnesses after specializing and computing usefulness.
//! In the example above, witnesses for specializing by `c''` covered by `0..50` will only differ
//! in their first element.
//!
//! We usually also ask that the `c'` together cover all of the original `c`. However we allow
//! skipping some constructors as long as it doesn't change whether the resulting list of witnesses
//! is empty of not. We use this in the wildcard `_` case.
//!
//! Splitting is implemented in the [`Constructor::split`] function. We don't do splitting for
//! or-patterns; instead we just try the alternatives one-by-one. For details on splitting
//! wildcards, see [`Constructor::split`]; for integer ranges, see
//! [`IntRange::split`]; for slices, see [`Slice::split`].
use std::cell::Cell;
use std::cmp::{self, max, min, Ordering};
use std::fmt;
use std::iter::once;
use smallvec::{smallvec, SmallVec};
use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS};
use rustc_data_structures::captures::Captures;
use rustc_data_structures::fx::FxHashSet;
use rustc_hir::RangeEnd;
use rustc_index::Idx;
use rustc_middle::middle::stability::EvalResult;
use rustc_middle::mir;
use rustc_middle::mir::interpret::Scalar;
use rustc_middle::thir::{FieldPat, Pat, PatKind, PatRange, PatRangeBoundary};
use rustc_middle::ty::layout::IntegerExt;
use rustc_middle::ty::{self, Ty, TyCtxt, VariantDef};
use rustc_span::{Span, DUMMY_SP};
use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT};
use self::Constructor::*;
use self::MaybeInfiniteInt::*;
use self::SliceKind::*;
use super::usefulness::{MatchCheckCtxt, PatCtxt};
/// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> {
fn expand<'p, 'tcx>(pat: &'p Pat<'tcx>, vec: &mut Vec<&'p Pat<'tcx>>) {
if let PatKind::Or { pats } = &pat.kind {
for pat in pats.iter() {
expand(&pat, vec);
}
} else {
vec.push(pat)
}
}
let mut pats = Vec::new();
expand(pat, &mut pats);
pats
}
/// Whether we have seen a constructor in the column or not.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum Presence {
Unseen,
Seen,
}
/// A possibly infinite integer. Values are encoded such that the ordering on `u128` matches the
/// natural order on the original type. For example, `-128i8` is encoded as `0` and `127i8` as
/// `255`. See `signed_bias` for details.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) enum MaybeInfiniteInt {
NegInfinity,
/// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite`.
Finite(u128),
/// The integer after `u128::MAX`. We need it to represent `x..=u128::MAX` as an exclusive range.
JustAfterMax,
PosInfinity,
}
impl MaybeInfiniteInt {
// The return value of `signed_bias` should be XORed with a value to encode/decode it.
fn signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> u128 {
match *ty.kind() {
ty::Int(ity) => {
let bits = Integer::from_int_ty(&tcx, ity).size().bits() as u128;
1u128 << (bits - 1)
}
_ => 0,
}
}
fn new_finite(tcx: TyCtxt<'_>, ty: Ty<'_>, bits: u128) -> Self {
let bias = Self::signed_bias(tcx, ty);
// Perform a shift if the underlying types are signed, which makes the interval arithmetic
// type-independent.
let x = bits ^ bias;
Finite(x)
}
fn from_pat_range_bdy<'tcx>(
bdy: PatRangeBoundary<'tcx>,
ty: Ty<'tcx>,
tcx: TyCtxt<'tcx>,
param_env: ty::ParamEnv<'tcx>,
) -> Self {
match bdy {
PatRangeBoundary::NegInfinity => NegInfinity,
PatRangeBoundary::Finite(value) => {
let bits = value.eval_bits(tcx, param_env);
Self::new_finite(tcx, ty, bits)
}
PatRangeBoundary::PosInfinity => PosInfinity,
}
}
/// Used only for diagnostics.
/// Note: it is possible to get `isize/usize::MAX+1` here, as explained in the doc for
/// [`IntRange::split`]. This cannot be represented as a `Const`, so we represent it with
/// `PosInfinity`.
fn to_diagnostic_pat_range_bdy<'tcx>(
self,
ty: Ty<'tcx>,
tcx: TyCtxt<'tcx>,
) -> PatRangeBoundary<'tcx> {
match self {
NegInfinity => PatRangeBoundary::NegInfinity,
Finite(x) => {
let bias = Self::signed_bias(tcx, ty);
let bits = x ^ bias;
let size = ty.primitive_size(tcx);
match Scalar::try_from_uint(bits, size) {
Some(scalar) => {
let value = mir::Const::from_scalar(tcx, scalar, ty);
PatRangeBoundary::Finite(value)
}
// The value doesn't fit. Since `x >= 0` and 0 always encodes the minimum value
// for a type, the problem isn't that the value is too small. So it must be too
// large.
None => PatRangeBoundary::PosInfinity,
}
}
JustAfterMax | PosInfinity => PatRangeBoundary::PosInfinity,
}
}
/// Note: this will not turn a finite value into an infinite one or vice-versa.
pub(crate) fn minus_one(self) -> Self {
match self {
Finite(n) => match n.checked_sub(1) {
Some(m) => Finite(m),
None => bug!(),
},
JustAfterMax => Finite(u128::MAX),
x => x,
}
}
/// Note: this will not turn a finite value into an infinite one or vice-versa.
pub(crate) fn plus_one(self) -> Self {
match self {
Finite(n) => match n.checked_add(1) {
Some(m) => Finite(m),
None => JustAfterMax,
},
JustAfterMax => bug!(),
x => x,
}
}
}
/// An exclusive interval, used for precise integer exhaustiveness checking. `IntRange`s always
/// store a contiguous range.
///
/// `IntRange` is never used to encode an empty range or a "range" that wraps around the (offset)
/// space: i.e., `range.lo < range.hi`.
#[derive(Clone, Copy, PartialEq, Eq)]
pub(crate) struct IntRange {
pub(crate) lo: MaybeInfiniteInt, // Must not be `PosInfinity`.
pub(crate) hi: MaybeInfiniteInt, // Must not be `NegInfinity`.
}
impl IntRange {
#[inline]
pub(super) fn is_integral(ty: Ty<'_>) -> bool {
matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_))
}
/// Best effort; will not know that e.g. `255u8..` is a singleton.
pub(super) fn is_singleton(&self) -> bool {
// Since `lo` and `hi` can't be the same `Infinity` and `plus_one` never changes from finite
// to infinite, this correctly only detects ranges that contain exacly one `Finite(x)`.
self.lo.plus_one() == self.hi
}
#[inline]
fn from_bits<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, bits: u128) -> IntRange {
let x = MaybeInfiniteInt::new_finite(tcx, ty, bits);
IntRange { lo: x, hi: x.plus_one() }
}
#[inline]
fn from_range(lo: MaybeInfiniteInt, mut hi: MaybeInfiniteInt, end: RangeEnd) -> IntRange {
if end == RangeEnd::Included {
hi = hi.plus_one();
}
if lo >= hi {
// This should have been caught earlier by E0030.
bug!("malformed range pattern: {lo:?}..{hi:?}");
}
IntRange { lo, hi }
}
fn is_subrange(&self, other: &Self) -> bool {
other.lo <= self.lo && self.hi <= other.hi
}
fn intersection(&self, other: &Self) -> Option<Self> {
if self.lo < other.hi && other.lo < self.hi {
Some(IntRange { lo: max(self.lo, other.lo), hi: min(self.hi, other.hi) })
} else {
None
}
}
/// Partition a range of integers into disjoint subranges. This does constructor splitting for
/// integer ranges as explained at the top of the file.
///
/// This returns an output that covers `self`. The output is split so that the only
/// intersections between an output range and a column range are inclusions. No output range
/// straddles the boundary of one of the inputs.
///
/// Additionally, we track for each output range whether it is covered by one of the column ranges or not.
///
/// The following input:
/// ```text
/// (--------------------------) // `self`
/// (------) (----------) (-)
/// (------) (--------)
/// ```
/// is first intersected with `self`:
/// ```text
/// (--------------------------) // `self`
/// (----) (----------) (-)
/// (------) (--------)
/// ```
/// and then iterated over as follows:
/// ```text
/// (-(--)-(-)-(------)-)--(-)-
/// ```
/// where each sequence of dashes is an output range, and dashes outside parentheses are marked
/// as `Presence::Missing`.
///
/// ## `isize`/`usize`
///
/// Whereas a wildcard of type `i32` stands for the range `i32::MIN..=i32::MAX`, a `usize`
/// wildcard stands for `0..PosInfinity` and a `isize` wildcard stands for
/// `NegInfinity..PosInfinity`. In other words, as far as `IntRange` is concerned, there are
/// values before `isize::MIN` and after `usize::MAX`/`isize::MAX`.
/// This is to avoid e.g. `0..(u32::MAX as usize)` from being exhaustive on one architecture and
/// not others. See discussions around the `precise_pointer_size_matching` feature for more
/// details.
///
/// These infinities affect splitting subtly: it is possible to get `NegInfinity..0` and
/// `usize::MAX+1..PosInfinity` in the output. Diagnostics must be careful to handle these
/// fictitious ranges sensibly.
fn split(
&self,
column_ranges: impl Iterator<Item = IntRange>,
) -> impl Iterator<Item = (Presence, IntRange)> {
// The boundaries of ranges in `column_ranges` intersected with `self`.
// We do parenthesis matching for input ranges. A boundary counts as +1 if it starts
// a range and -1 if it ends it. When the count is > 0 between two boundaries, we
// are within an input range.
let mut boundaries: Vec<(MaybeInfiniteInt, isize)> = column_ranges
.filter_map(|r| self.intersection(&r))
.flat_map(|r| [(r.lo, 1), (r.hi, -1)])
.collect();
// We sort by boundary, and for each boundary we sort the "closing parentheses" first. The
// order of +1/-1 for a same boundary value is actually irrelevant, because we only look at
// the accumulated count between distinct boundary values.
boundaries.sort_unstable();
// Accumulate parenthesis counts.
let mut paren_counter = 0isize;
// Gather pairs of adjacent boundaries.
let mut prev_bdy = self.lo;
boundaries
.into_iter()
// End with the end of the range. The count is ignored.
.chain(once((self.hi, 0)))
// List pairs of adjacent boundaries and the count between them.
.map(move |(bdy, delta)| {
// `delta` affects the count as we cross `bdy`, so the relevant count between
// `prev_bdy` and `bdy` is untouched by `delta`.
let ret = (prev_bdy, paren_counter, bdy);
prev_bdy = bdy;
paren_counter += delta;
ret
})
// Skip empty ranges.
.filter(|&(prev_bdy, _, bdy)| prev_bdy != bdy)
// Convert back to ranges.
.map(move |(prev_bdy, paren_count, bdy)| {
use Presence::*;
let presence = if paren_count > 0 { Seen } else { Unseen };
let range = IntRange { lo: prev_bdy, hi: bdy };
(presence, range)
})
}
/// Whether the range denotes the fictitious values before `isize::MIN` or after
/// `usize::MAX`/`isize::MAX` (see doc of [`IntRange::split`] for why these exist).
pub(crate) fn is_beyond_boundaries<'tcx>(&self, ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> bool {
ty.is_ptr_sized_integral() && !tcx.features().precise_pointer_size_matching && {
// The two invalid ranges are `NegInfinity..isize::MIN` (represented as
// `NegInfinity..0`), and `{u,i}size::MAX+1..PosInfinity`. `to_diagnostic_pat_range_bdy`
// converts `MAX+1` to `PosInfinity`, and we couldn't have `PosInfinity` in `self.lo`
// otherwise.
let lo = self.lo.to_diagnostic_pat_range_bdy(ty, tcx);
matches!(lo, PatRangeBoundary::PosInfinity)
|| matches!(self.hi, MaybeInfiniteInt::Finite(0))
}
}
/// Only used for displaying the range.
pub(super) fn to_diagnostic_pat<'tcx>(&self, ty: Ty<'tcx>, tcx: TyCtxt<'tcx>) -> Pat<'tcx> {
let kind = if matches!((self.lo, self.hi), (NegInfinity, PosInfinity)) {
PatKind::Wild
} else if self.is_singleton() {
let lo = self.lo.to_diagnostic_pat_range_bdy(ty, tcx);
let value = lo.as_finite().unwrap();
PatKind::Constant { value }
} else {
// We convert to an inclusive range for diagnostics.
let mut end = RangeEnd::Included;
let mut lo = self.lo.to_diagnostic_pat_range_bdy(ty, tcx);
if matches!(lo, PatRangeBoundary::PosInfinity) {
// The only reason to get `PosInfinity` here is the special case where
// `to_diagnostic_pat_range_bdy` found `{u,i}size::MAX+1`. So the range denotes the
// fictitious values after `{u,i}size::MAX` (see [`IntRange::split`] for why we do
// this). We show this to the user as `usize::MAX..` which is slightly incorrect but
// probably clear enough.
let c = ty.numeric_max_val(tcx).unwrap();
let value = mir::Const::from_ty_const(c, tcx);
lo = PatRangeBoundary::Finite(value);
}
let hi = if matches!(self.hi, MaybeInfiniteInt::Finite(0)) {
// The range encodes `..ty::MIN`, so we can't convert it to an inclusive range.
end = RangeEnd::Excluded;
self.hi
} else {
self.hi.minus_one()
};
let hi = hi.to_diagnostic_pat_range_bdy(ty, tcx);
PatKind::Range(Box::new(PatRange { lo, hi, end, ty }))
};
Pat { ty, span: DUMMY_SP, kind }
}
}
/// Note: this will render signed ranges incorrectly. To render properly, convert to a pattern
/// first.
impl fmt::Debug for IntRange {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if let Finite(lo) = self.lo {
write!(f, "{lo}")?;
}
write!(f, "{}", RangeEnd::Excluded)?;
if let Finite(hi) = self.hi {
write!(f, "{hi}")?;
}
Ok(())
}
}
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum SliceKind {
/// Patterns of length `n` (`[x, y]`).
FixedLen(usize),
/// Patterns using the `..` notation (`[x, .., y]`).
/// Captures any array constructor of `length >= i + j`.
/// In the case where `array_len` is `Some(_)`,
/// this indicates that we only care about the first `i` and the last `j` values of the array,
/// and everything in between is a wildcard `_`.
VarLen(usize, usize),
}
impl SliceKind {
fn arity(self) -> usize {
match self {
FixedLen(length) => length,
VarLen(prefix, suffix) => prefix + suffix,
}
}
/// Whether this pattern includes patterns of length `other_len`.
fn covers_length(self, other_len: usize) -> bool {
match self {
FixedLen(len) => len == other_len,
VarLen(prefix, suffix) => prefix + suffix <= other_len,
}
}
}
/// A constructor for array and slice patterns.
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub(super) struct Slice {
/// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`.
array_len: Option<usize>,
/// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`.
kind: SliceKind,
}
impl Slice {
fn new(array_len: Option<usize>, kind: SliceKind) -> Self {
let kind = match (array_len, kind) {
// If the middle `..` is empty, we effectively have a fixed-length pattern.
(Some(len), VarLen(prefix, suffix)) if prefix + suffix >= len => FixedLen(len),
_ => kind,
};
Slice { array_len, kind }
}
fn arity(self) -> usize {
self.kind.arity()
}
/// See `Constructor::is_covered_by`
fn is_covered_by(self, other: Self) -> bool {
other.kind.covers_length(self.arity())
}
/// This computes constructor splitting for variable-length slices, as explained at the top of
/// the file.
///
/// A slice pattern `[x, .., y]` behaves like the infinite or-pattern `[x, y] | [x, _, y] | [x,
/// _, _, y] | etc`. The corresponding value constructors are fixed-length array constructors of
/// corresponding lengths. We obviously can't list this infinitude of constructors.
/// Thankfully, it turns out that for each finite set of slice patterns, all sufficiently large
/// array lengths are equivalent.
///
/// Let's look at an example, where we are trying to split the last pattern:
/// ```
/// # fn foo(x: &[bool]) {
/// match x {
/// [true, true, ..] => {}
/// [.., false, false] => {}
/// [..] => {}
/// }
/// # }
/// ```
/// Here are the results of specialization for the first few lengths:
/// ```
/// # fn foo(x: &[bool]) { match x {
/// // length 0
/// [] => {}
/// // length 1
/// [_] => {}
/// // length 2
/// [true, true] => {}
/// [false, false] => {}
/// [_, _] => {}
/// // length 3
/// [true, true, _ ] => {}
/// [_, false, false] => {}
/// [_, _, _ ] => {}
/// // length 4
/// [true, true, _, _ ] => {}
/// [_, _, false, false] => {}
/// [_, _, _, _ ] => {}
/// // length 5
/// [true, true, _, _, _ ] => {}
/// [_, _, _, false, false] => {}
/// [_, _, _, _, _ ] => {}
/// # _ => {}
/// # }}
/// ```
///
/// We see that above length 4, we are simply inserting columns full of wildcards in the middle.
/// This means that specialization and witness computation with slices of length `l >= 4` will
/// give equivalent results regardless of `l`. This applies to any set of slice patterns: there
/// will be a length `L` above which all lengths behave the same. This is exactly what we need
/// for constructor splitting.
///
/// A variable-length slice pattern covers all lengths from its arity up to infinity. As we just
/// saw, we can split this in two: lengths below `L` are treated individually with a
/// fixed-length slice each; lengths above `L` are grouped into a single variable-length slice
/// constructor.
///
/// For each variable-length slice pattern `p` with a prefix of length `plâ‚š` and suffix of
/// length `slâ‚š`, only the first `plâ‚š` and the last `slâ‚š` elements are examined. Therefore, as
/// long as `L` is positive (to avoid concerns about empty types), all elements after the
/// maximum prefix length and before the maximum suffix length are not examined by any
/// variable-length pattern, and therefore can be ignored. This gives us a way to compute `L`.
///
/// Additionally, if fixed-length patterns exist, we must pick an `L` large enough to miss them,
/// so we can pick `L = max(max(FIXED_LEN)+1, max(PREFIX_LEN) + max(SUFFIX_LEN))`.
/// `max_slice` below will be made to have this arity `L`.
///
/// If `self` is fixed-length, it is returned as-is.
///
/// Additionally, we track for each output slice whether it is covered by one of the column slices or not.
fn split(
self,
column_slices: impl Iterator<Item = Slice>,
) -> impl Iterator<Item = (Presence, Slice)> {
// Range of lengths below `L`.
let smaller_lengths;
let arity = self.arity();
let mut max_slice = self.kind;
// Tracks the smallest variable-length slice we've seen. Any slice arity above it is
// therefore `Presence::Seen` in the column.
let mut min_var_len = usize::MAX;
// Tracks the fixed-length slices we've seen, to mark them as `Presence::Seen`.
let mut seen_fixed_lens = FxHashSet::default();
match &mut max_slice {
VarLen(max_prefix_len, max_suffix_len) => {
// We grow `max_slice` to be larger than all slices encountered, as described above.
// For diagnostics, we keep the prefix and suffix lengths separate, but grow them so that
// `L = max_prefix_len + max_suffix_len`.
let mut max_fixed_len = 0;
for slice in column_slices {
match slice.kind {
FixedLen(len) => {
max_fixed_len = cmp::max(max_fixed_len, len);
if arity <= len {
seen_fixed_lens.insert(len);
}
}
VarLen(prefix, suffix) => {
*max_prefix_len = cmp::max(*max_prefix_len, prefix);
*max_suffix_len = cmp::max(*max_suffix_len, suffix);
min_var_len = cmp::min(min_var_len, prefix + suffix);
}
}
}
// We want `L = max(L, max_fixed_len + 1)`, modulo the fact that we keep prefix and
// suffix separate.
if max_fixed_len + 1 >= *max_prefix_len + *max_suffix_len {
// The subtraction can't overflow thanks to the above check.
// The new `max_prefix_len` is larger than its previous value.
*max_prefix_len = max_fixed_len + 1 - *max_suffix_len;
}
// We cap the arity of `max_slice` at the array size.
match self.array_len {
Some(len) if max_slice.arity() >= len => max_slice = FixedLen(len),
_ => {}
}
smaller_lengths = match self.array_len {
// The only admissible fixed-length slice is one of the array size. Whether `max_slice`
// is fixed-length or variable-length, it will be the only relevant slice to output
// here.
Some(_) => 0..0, // empty range
// We need to cover all arities in the range `(arity..infinity)`. We split that
// range into two: lengths smaller than `max_slice.arity()` are treated
// independently as fixed-lengths slices, and lengths above are captured by
// `max_slice`.
None => self.arity()..max_slice.arity(),
};
}
FixedLen(_) => {
// No need to split here. We only track presence.
for slice in column_slices {
match slice.kind {
FixedLen(len) => {
if len == arity {
seen_fixed_lens.insert(len);
}
}
VarLen(prefix, suffix) => {
min_var_len = cmp::min(min_var_len, prefix + suffix);
}
}
}
smaller_lengths = 0..0;
}
};
smaller_lengths.map(FixedLen).chain(once(max_slice)).map(move |kind| {
let arity = kind.arity();
let seen = if min_var_len <= arity || seen_fixed_lens.contains(&arity) {
Presence::Seen
} else {
Presence::Unseen
};
(seen, Slice::new(self.array_len, kind))
})
}
}
/// A value can be decomposed into a constructor applied to some fields. This struct represents
/// the constructor. See also `Fields`.
///
/// `pat_constructor` retrieves the constructor corresponding to a pattern.
/// `specialize_constructor` returns the list of fields corresponding to a pattern, given a
/// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
/// `Fields`.
#[derive(Clone, Debug, PartialEq)]
pub(super) enum Constructor<'tcx> {
/// The constructor for patterns that have a single constructor, like tuples, struct patterns
/// and fixed-length arrays.
Single,
/// Enum variants.
Variant(VariantIdx),
/// Booleans
Bool(bool),
/// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
IntRange(IntRange),
/// Ranges of floating-point literal values (`2.0..=5.2`).
F32Range(IeeeFloat<SingleS>, IeeeFloat<SingleS>, RangeEnd),
F64Range(IeeeFloat<DoubleS>, IeeeFloat<DoubleS>, RangeEnd),
/// String literals. Strings are not quite the same as `&[u8]` so we treat them separately.
Str(mir::Const<'tcx>),
/// Array and slice patterns.
Slice(Slice),
/// Constants that must not be matched structurally. They are treated as black
/// boxes for the purposes of exhaustiveness: we must not inspect them, and they
/// don't count towards making a match exhaustive.
Opaque,
/// Or-pattern.
Or,
/// Wildcard pattern.
Wildcard,
/// Fake extra constructor for enums that aren't allowed to be matched exhaustively. Also used
/// for those types for which we cannot list constructors explicitly, like `f64` and `str`.
NonExhaustive,
/// Fake extra constructor for variants that should not be mentioned in diagnostics.
/// We use this for variants behind an unstable gate as well as
/// `#[doc(hidden)]` ones.
Hidden,
/// Fake extra constructor for constructors that are not seen in the matrix, as explained in the
/// code for [`Constructor::split`].
Missing,
}
impl<'tcx> Constructor<'tcx> {
pub(super) fn is_non_exhaustive(&self) -> bool {
matches!(self, NonExhaustive)
}
pub(super) fn as_variant(&self) -> Option<VariantIdx> {
match self {
Variant(i) => Some(*i),
_ => None,
}
}
fn as_bool(&self) -> Option<bool> {
match self {
Bool(b) => Some(*b),
_ => None,
}
}
pub(super) fn as_int_range(&self) -> Option<&IntRange> {
match self {
IntRange(range) => Some(range),
_ => None,
}
}
fn as_slice(&self) -> Option<Slice> {
match self {
Slice(slice) => Some(*slice),
_ => None,
}
}
fn variant_index_for_adt(&self, adt: ty::AdtDef<'tcx>) -> VariantIdx {
match *self {
Variant(idx) => idx,
Single => {
assert!(!adt.is_enum());
FIRST_VARIANT
}
_ => bug!("bad constructor {:?} for adt {:?}", self, adt),
}
}
/// The number of fields for this constructor. This must be kept in sync with
/// `Fields::wildcards`.
pub(super) fn arity(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> usize {
match self {
Single | Variant(_) => match pcx.ty.kind() {
ty::Tuple(fs) => fs.len(),
ty::Ref(..) => 1,
ty::Adt(adt, ..) => {
if adt.is_box() {
// The only legal patterns of type `Box` (outside `std`) are `_` and box
// patterns. If we're here we can assume this is a box pattern.
1
} else {
let variant = &adt.variant(self.variant_index_for_adt(*adt));
Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant).count()
}
}
_ => bug!("Unexpected type for `Single` constructor: {:?}", pcx.ty),
},
Slice(slice) => slice.arity(),
Bool(..)
| IntRange(..)
| F32Range(..)
| F64Range(..)
| Str(..)
| Opaque
| NonExhaustive
| Hidden
| Missing { .. }
| Wildcard => 0,
Or => bug!("The `Or` constructor doesn't have a fixed arity"),
}
}
/// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of
/// actual constructors (like variants, integers or fixed-sized slices). When specializing for
/// these constructors, we want to be specialising for the actual underlying constructors.
/// Naively, we would simply return the list of constructors they correspond to. We instead are
/// more clever: if there are constructors that we know will behave the same w.r.t. the current
/// matrix, we keep them grouped. For example, all slices of a sufficiently large length will
/// either be all useful or all non-useful with a given matrix.
///
/// See the branches for details on how the splitting is done.
///
/// This function may discard some irrelevant constructors if this preserves behavior. Eg. for
/// the `_` case, we ignore the constructors already present in the column, unless all of them
/// are.
pub(super) fn split<'a>(
&self,
pcx: &PatCtxt<'_, '_, 'tcx>,
ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
) -> SmallVec<[Self; 1]>
where
'tcx: 'a,
{
match self {
Wildcard => {
let split_set = ConstructorSet::for_ty(pcx.cx, pcx.ty).split(pcx, ctors);
if !split_set.missing.is_empty() {
// We are splitting a wildcard in order to compute its usefulness. Some constructors are
// not present in the column. The first thing we note is that specializing with any of
// the missing constructors would select exactly the rows with wildcards. Moreover, they
// would all return equivalent results. We can therefore group them all into a
// fictitious `Missing` constructor.
//
// As an important optimization, this function will skip all the present constructors.
// This is correct because specializing with any of the present constructors would
// select a strict superset of the wildcard rows, and thus would only find witnesses
// already found with the `Missing` constructor.
// This does mean that diagnostics are incomplete: in
// ```
// match x {
// Some(true) => {}
// }
// ```
// we report `None` as missing but not `Some(false)`.
//
// When all the constructors are missing we can equivalently return the `Wildcard`
// constructor on its own. The difference between `Wildcard` and `Missing` will then
// only be in diagnostics.
// If some constructors are missing, we typically want to report those constructors,
// e.g.:
// ```
// enum Direction { N, S, E, W }
// let Direction::N = ...;
// ```
// we can report 3 witnesses: `S`, `E`, and `W`.
//
// However, if the user didn't actually specify a constructor
// in this arm, e.g., in
// ```
// let x: (Direction, Direction, bool) = ...;
// let (_, _, false) = x;
// ```
// we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>,
// true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we
// prefer to report just a wildcard `_`.
//
// The exception is: if we are at the top-level, for example in an empty match, we
// usually prefer to report the full list of constructors.
let all_missing = split_set.present.is_empty();
let report_when_all_missing =
pcx.is_top_level && !IntRange::is_integral(pcx.ty);
let ctor =
if all_missing && !report_when_all_missing { Wildcard } else { Missing };
smallvec![ctor]
} else {
split_set.present
}
}
// Fast-track if the range is trivial.
IntRange(this_range) if !this_range.is_singleton() => {
let column_ranges = ctors.filter_map(|ctor| ctor.as_int_range()).cloned();
this_range.split(column_ranges).map(|(_, range)| IntRange(range)).collect()
}
Slice(this_slice @ Slice { kind: VarLen(..), .. }) => {
let column_slices = ctors.filter_map(|c| c.as_slice());
this_slice.split(column_slices).map(|(_, slice)| Slice(slice)).collect()
}
// Any other constructor can be used unchanged.
_ => smallvec![self.clone()],
}
}
/// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
/// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
/// this checks for inclusion.
// We inline because this has a single call site in `Matrix::specialize_constructor`.
#[inline]
pub(super) fn is_covered_by<'p>(&self, pcx: &PatCtxt<'_, 'p, 'tcx>, other: &Self) -> bool {
// This must be kept in sync with `is_covered_by_any`.
match (self, other) {
// Wildcards cover anything
(_, Wildcard) => true,
// Only a wildcard pattern can match these special constructors.
(Wildcard | Missing { .. } | NonExhaustive | Hidden, _) => false,
(Single, Single) => true,
(Variant(self_id), Variant(other_id)) => self_id == other_id,
(Bool(self_b), Bool(other_b)) => self_b == other_b,
(IntRange(self_range), IntRange(other_range)) => self_range.is_subrange(other_range),
(F32Range(self_from, self_to, self_end), F32Range(other_from, other_to, other_end)) => {
self_from.ge(other_from)
&& match self_to.partial_cmp(other_to) {
Some(Ordering::Less) => true,
Some(Ordering::Equal) => other_end == self_end,
_ => false,
}
}
(F64Range(self_from, self_to, self_end), F64Range(other_from, other_to, other_end)) => {
self_from.ge(other_from)
&& match self_to.partial_cmp(other_to) {
Some(Ordering::Less) => true,
Some(Ordering::Equal) => other_end == self_end,
_ => false,
}
}
(Str(self_val), Str(other_val)) => {
// FIXME Once valtrees are available we can directly use the bytes
// in the `Str` variant of the valtree for the comparison here.
self_val == other_val
}
(Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
// We are trying to inspect an opaque constant. Thus we skip the row.
(Opaque, _) | (_, Opaque) => false,
_ => span_bug!(
pcx.span,
"trying to compare incompatible constructors {:?} and {:?}",
self,
other
),
}
}
}
/// Describes the set of all constructors for a type.
#[derive(Debug)]
pub(super) enum ConstructorSet {
/// The type has a single constructor, e.g. `&T` or a struct.
Single,
/// This type has the following list of constructors.
/// Some variants are hidden, which means they won't be mentioned in diagnostics unless the user
/// mentioned them first. We use this for variants behind an unstable gate as well as
/// `#[doc(hidden)]` ones.
Variants {
visible_variants: Vec<VariantIdx>,
hidden_variants: Vec<VariantIdx>,
non_exhaustive: bool,
},
/// Booleans.
Bool,
/// The type is spanned by integer values. The range or ranges give the set of allowed values.
/// The second range is only useful for `char`.
Integers { range_1: IntRange, range_2: Option<IntRange> },
/// The type is matched by slices. The usize is the compile-time length of the array, if known.
Slice(Option<usize>),
/// The type is matched by slices whose elements are uninhabited.
SliceOfEmpty,
/// The constructors cannot be listed, and the type cannot be matched exhaustively. E.g. `str`,
/// floats.
Unlistable,
/// The type has no inhabitants.
Uninhabited,
}
/// Describes the result of analyzing the constructors in a column of a match.
///
/// `present` is morally the set of constructors present in the column, and `missing` is the set of
/// constructors that exist in the type but are not present in the column.
///
/// More formally, they respect the following constraints:
/// - the union of `present` and `missing` covers the whole type
/// - `present` and `missing` are disjoint
/// - neither contains wildcards
/// - each constructor in `present` is covered by some non-wildcard constructor in the column
/// - together, the constructors in `present` cover all the non-wildcard constructor in the column
/// - non-wildcards in the column do no cover anything in `missing`
/// - constructors in `present` and `missing` are split for the column; in other words, they are
/// either fully included in or disjoint from each constructor in the column. This avoids
/// non-trivial intersections like between `0..10` and `5..15`.
#[derive(Debug)]
pub(super) struct SplitConstructorSet<'tcx> {
pub(super) present: SmallVec<[Constructor<'tcx>; 1]>,
pub(super) missing: Vec<Constructor<'tcx>>,
}
impl ConstructorSet {
#[instrument(level = "debug", skip(cx), ret)]
pub(super) fn for_ty<'p, 'tcx>(cx: &MatchCheckCtxt<'p, 'tcx>, ty: Ty<'tcx>) -> Self {
let make_range = |start, end| {
IntRange::from_range(
MaybeInfiniteInt::new_finite(cx.tcx, ty, start),
MaybeInfiniteInt::new_finite(cx.tcx, ty, end),
RangeEnd::Included,
)
};
// This determines the set of all possible constructors for the type `ty`. For numbers,
// arrays and slices we use ranges and variable-length slices when appropriate.
//
// If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that
// are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the
// returned list of constructors.
// Invariant: this is `Uninhabited` if and only if the type is uninhabited (as determined by
// `cx.is_uninhabited()`).
match ty.kind() {
ty::Bool => Self::Bool,
ty::Char => {
// The valid Unicode Scalar Value ranges.
Self::Integers {
range_1: make_range('\u{0000}' as u128, '\u{D7FF}' as u128),
range_2: Some(make_range('\u{E000}' as u128, '\u{10FFFF}' as u128)),
}
}
&ty::Int(ity) => {
let range = if ty.is_ptr_sized_integral()
&& !cx.tcx.features().precise_pointer_size_matching
{
// The min/max values of `isize` are not allowed to be observed unless the
// `precise_pointer_size_matching` feature is enabled.
IntRange { lo: NegInfinity, hi: PosInfinity }
} else {
let bits = Integer::from_int_ty(&cx.tcx, ity).size().bits() as u128;
let min = 1u128 << (bits - 1);
let max = min - 1;
make_range(min, max)
};
Self::Integers { range_1: range, range_2: None }
}
&ty::Uint(uty) => {
let range = if ty.is_ptr_sized_integral()
&& !cx.tcx.features().precise_pointer_size_matching
{
// The max value of `usize` is not allowed to be observed unless the
// `precise_pointer_size_matching` feature is enabled.
let lo = MaybeInfiniteInt::new_finite(cx.tcx, ty, 0);
IntRange { lo, hi: PosInfinity }
} else {
let size = Integer::from_uint_ty(&cx.tcx, uty).size();
let max = size.truncate(u128::MAX);
make_range(0, max)
};
Self::Integers { range_1: range, range_2: None }
}
ty::Array(sub_ty, len) if len.try_eval_target_usize(cx.tcx, cx.param_env).is_some() => {
let len = len.eval_target_usize(cx.tcx, cx.param_env) as usize;
if len != 0 && cx.is_uninhabited(*sub_ty) {
Self::Uninhabited
} else {
Self::Slice(Some(len))
}
}
// Treat arrays of a constant but unknown length like slices.
ty::Array(sub_ty, _) | ty::Slice(sub_ty) => {
if cx.is_uninhabited(*sub_ty) {
Self::SliceOfEmpty
} else {
Self::Slice(None)
}
}
ty::Adt(def, args) if def.is_enum() => {
// If the enum is declared as `#[non_exhaustive]`, we treat it as if it had an
// additional "unknown" constructor.
// There is no point in enumerating all possible variants, because the user can't
// actually match against them all themselves. So we always return only the fictitious
// constructor.
// E.g., in an example like:
//
// ```
// let err: io::ErrorKind = ...;
// match err {
// io::ErrorKind::NotFound => {},
// }
// ```
//
// we don't want to show every possible IO error, but instead have only `_` as the
// witness.
let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(ty);
if def.variants().is_empty() && !is_declared_nonexhaustive {
Self::Uninhabited
} else {
let is_exhaustive_pat_feature = cx.tcx.features().exhaustive_patterns;
let (hidden_variants, visible_variants) = def
.variants()
.iter_enumerated()
.filter(|(_, v)| {
// If `exhaustive_patterns` is enabled, we exclude variants known to be
// uninhabited.
!is_exhaustive_pat_feature
|| v.inhabited_predicate(cx.tcx, *def)
.instantiate(cx.tcx, args)
.apply(cx.tcx, cx.param_env, cx.module)
})
.map(|(idx, _)| idx)
.partition(|idx| {
let variant_def_id = def.variant(*idx).def_id;
// Filter variants that depend on a disabled unstable feature.
let is_unstable = matches!(
cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None),
EvalResult::Deny { .. }
);
// Filter foreign `#[doc(hidden)]` variants.
let is_doc_hidden =
cx.tcx.is_doc_hidden(variant_def_id) && !variant_def_id.is_local();
is_unstable || is_doc_hidden
});
Self::Variants {
visible_variants,
hidden_variants,
non_exhaustive: is_declared_nonexhaustive,
}
}
}
ty::Never => Self::Uninhabited,
_ if cx.is_uninhabited(ty) => Self::Uninhabited,
ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => Self::Single,
// This type is one for which we cannot list constructors, like `str` or `f64`.
_ => Self::Unlistable,
}
}
/// This is the core logical operation of exhaustiveness checking. This analyzes a column a
/// constructors to 1/ determine which constructors of the type (if any) are missing; 2/ split
/// constructors to handle non-trivial intersections e.g. on ranges or slices.
#[instrument(level = "debug", skip(self, pcx, ctors), ret)]
pub(super) fn split<'a, 'tcx>(
&self,
pcx: &PatCtxt<'_, '_, 'tcx>,
ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
) -> SplitConstructorSet<'tcx>
where
'tcx: 'a,
{
let mut present: SmallVec<[_; 1]> = SmallVec::new();
let mut missing = Vec::new();
// Constructors in `ctors`, except wildcards.
let mut seen = ctors.filter(|c| !(matches!(c, Opaque | Wildcard)));
match self {
ConstructorSet::Single => {
if seen.next().is_none() {
missing.push(Single);
} else {
present.push(Single);
}
}
ConstructorSet::Variants { visible_variants, hidden_variants, non_exhaustive } => {
let seen_set: FxHashSet<_> = seen.map(|c| c.as_variant().unwrap()).collect();
let mut skipped_a_hidden_variant = false;
for variant in visible_variants {
let ctor = Variant(*variant);
if seen_set.contains(&variant) {
present.push(ctor);
} else {
missing.push(ctor);
}
}
for variant in hidden_variants {
let ctor = Variant(*variant);
if seen_set.contains(&variant) {
present.push(ctor);
} else {
skipped_a_hidden_variant = true;
}
}
if skipped_a_hidden_variant {
missing.push(Hidden);
}
if *non_exhaustive {
missing.push(NonExhaustive);
}
}
ConstructorSet::Bool => {
let mut seen_false = false;
let mut seen_true = false;
for b in seen.map(|ctor| ctor.as_bool().unwrap()) {
if b {
seen_true = true;
} else {
seen_false = true;
}
}
if seen_false {
present.push(Bool(false));
} else {
missing.push(Bool(false));
}
if seen_true {
present.push(Bool(true));
} else {
missing.push(Bool(true));
}
}
ConstructorSet::Integers { range_1, range_2 } => {
let seen_ranges: Vec<_> =
seen.map(|ctor| ctor.as_int_range().unwrap().clone()).collect();
for (seen, splitted_range) in range_1.split(seen_ranges.iter().cloned()) {
match seen {
Presence::Unseen => missing.push(IntRange(splitted_range)),
Presence::Seen => present.push(IntRange(splitted_range)),
}
}
if let Some(range_2) = range_2 {
for (seen, splitted_range) in range_2.split(seen_ranges.into_iter()) {
match seen {
Presence::Unseen => missing.push(IntRange(splitted_range)),
Presence::Seen => present.push(IntRange(splitted_range)),
}
}
}
}
&ConstructorSet::Slice(array_len) => {
let seen_slices = seen.map(|c| c.as_slice().unwrap());
let base_slice = Slice::new(array_len, VarLen(0, 0));
for (seen, splitted_slice) in base_slice.split(seen_slices) {
let ctor = Slice(splitted_slice);
match seen {
Presence::Unseen => missing.push(ctor),
Presence::Seen => present.push(ctor),
}
}
}
ConstructorSet::SliceOfEmpty => {
// This one is tricky because even though there's only one possible value of this
// type (namely `[]`), slice patterns of all lengths are allowed, they're just
// unreachable if length != 0.
// We still gather the seen constructors in `present`, but the only slice that can
// go in `missing` is `[]`.
let seen_slices = seen.map(|c| c.as_slice().unwrap());
let base_slice = Slice::new(None, VarLen(0, 0));
for (seen, splitted_slice) in base_slice.split(seen_slices) {
let ctor = Slice(splitted_slice);
match seen {
Presence::Seen => present.push(ctor),
Presence::Unseen if splitted_slice.arity() == 0 => {
missing.push(Slice(Slice::new(None, FixedLen(0))))
}
Presence::Unseen => {}
}
}
}
ConstructorSet::Unlistable => {
// Since we can't list constructors, we take the ones in the column. This might list
// some constructors several times but there's not much we can do.
present.extend(seen.cloned());
missing.push(NonExhaustive);
}
// If `exhaustive_patterns` is disabled and our scrutinee is an empty type, we cannot
// expose its emptiness. The exception is if the pattern is at the top level, because we
// want empty matches to be considered exhaustive.
ConstructorSet::Uninhabited
if !pcx.cx.tcx.features().exhaustive_patterns && !pcx.is_top_level =>
{
missing.push(NonExhaustive);
}
ConstructorSet::Uninhabited => {}
}
SplitConstructorSet { present, missing }
}
/// Compute the set of constructors missing from this column.
/// This is only used for reporting to the user.
pub(super) fn compute_missing<'a, 'tcx>(
&self,
pcx: &PatCtxt<'_, '_, 'tcx>,
ctors: impl Iterator<Item = &'a Constructor<'tcx>> + Clone,
) -> Vec<Constructor<'tcx>>
where
'tcx: 'a,
{
self.split(pcx, ctors).missing
}
}
/// A value can be decomposed into a constructor applied to some fields. This struct represents
/// those fields, generalized to allow patterns in each field. See also `Constructor`.
///
/// This is constructed for a constructor using [`Fields::wildcards()`]. The idea is that
/// [`Fields::wildcards()`] constructs a list of fields where all entries are wildcards, and then
/// given a pattern we fill some of the fields with its subpatterns.
/// In the following example `Fields::wildcards` returns `[_, _, _, _]`. Then in
/// `extract_pattern_arguments` we fill some of the entries, and the result is
/// `[Some(0), _, _, _]`.
/// ```compile_fail,E0004
/// # fn foo() -> [Option<u8>; 4] { [None; 4] }
/// let x: [Option<u8>; 4] = foo();
/// match x {
/// [Some(0), ..] => {}
/// }
/// ```
///
/// Note that the number of fields of a constructor may not match the fields declared in the
/// original struct/variant. This happens if a private or `non_exhaustive` field is uninhabited,
/// because the code mustn't observe that it is uninhabited. In that case that field is not
/// included in `fields`. For that reason, when you have a `FieldIdx` you must use
/// `index_with_declared_idx`.
#[derive(Debug, Clone, Copy)]
pub(super) struct Fields<'p, 'tcx> {
fields: &'p [DeconstructedPat<'p, 'tcx>],
}
impl<'p, 'tcx> Fields<'p, 'tcx> {
fn empty() -> Self {
Fields { fields: &[] }
}
fn singleton(cx: &MatchCheckCtxt<'p, 'tcx>, field: DeconstructedPat<'p, 'tcx>) -> Self {
let field: &_ = cx.pattern_arena.alloc(field);
Fields { fields: std::slice::from_ref(field) }
}
pub(super) fn from_iter(
cx: &MatchCheckCtxt<'p, 'tcx>,
fields: impl IntoIterator<Item = DeconstructedPat<'p, 'tcx>>,
) -> Self {
let fields: &[_] = cx.pattern_arena.alloc_from_iter(fields);
Fields { fields }
}
fn wildcards_from_tys(
cx: &MatchCheckCtxt<'p, 'tcx>,
tys: impl IntoIterator<Item = Ty<'tcx>>,
span: Span,
) -> Self {
Fields::from_iter(cx, tys.into_iter().map(|ty| DeconstructedPat::wildcard(ty, span)))
}
// In the cases of either a `#[non_exhaustive]` field list or a non-public field, we hide
// uninhabited fields in order not to reveal the uninhabitedness of the whole variant.
// This lists the fields we keep along with their types.
fn list_variant_nonhidden_fields<'a>(
cx: &'a MatchCheckCtxt<'p, 'tcx>,
ty: Ty<'tcx>,
variant: &'a VariantDef,
) -> impl Iterator<Item = (FieldIdx, Ty<'tcx>)> + Captures<'a> + Captures<'p> {
let ty::Adt(adt, args) = ty.kind() else { bug!() };
// Whether we must not match the fields of this variant exhaustively.
let is_non_exhaustive = variant.is_field_list_non_exhaustive() && !adt.did().is_local();
variant.fields.iter().enumerate().filter_map(move |(i, field)| {
let ty = field.ty(cx.tcx, args);
// `field.ty()` doesn't normalize after substituting.
let ty = cx.tcx.normalize_erasing_regions(cx.param_env, ty);
let is_visible = adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx);
let is_uninhabited = cx.is_uninhabited(ty);
if is_uninhabited && (!is_visible || is_non_exhaustive) {
None
} else {
Some((FieldIdx::new(i), ty))
}
})
}
/// Creates a new list of wildcard fields for a given constructor. The result must have a
/// length of `constructor.arity()`.
#[instrument(level = "trace")]
pub(super) fn wildcards(pcx: &PatCtxt<'_, 'p, 'tcx>, constructor: &Constructor<'tcx>) -> Self {
let ret = match constructor {
Single | Variant(_) => match pcx.ty.kind() {
ty::Tuple(fs) => Fields::wildcards_from_tys(pcx.cx, fs.iter(), pcx.span),
ty::Ref(_, rty, _) => Fields::wildcards_from_tys(pcx.cx, once(*rty), pcx.span),
ty::Adt(adt, args) => {
if adt.is_box() {
// The only legal patterns of type `Box` (outside `std`) are `_` and box
// patterns. If we're here we can assume this is a box pattern.
Fields::wildcards_from_tys(pcx.cx, once(args.type_at(0)), pcx.span)
} else {
let variant = &adt.variant(constructor.variant_index_for_adt(*adt));
let tys = Fields::list_variant_nonhidden_fields(pcx.cx, pcx.ty, variant)
.map(|(_, ty)| ty);
Fields::wildcards_from_tys(pcx.cx, tys, pcx.span)
}
}
_ => bug!("Unexpected type for `Single` constructor: {:?}", pcx),
},
Slice(slice) => match *pcx.ty.kind() {
ty::Slice(ty) | ty::Array(ty, _) => {
let arity = slice.arity();
Fields::wildcards_from_tys(pcx.cx, (0..arity).map(|_| ty), pcx.span)
}
_ => bug!("bad slice pattern {:?} {:?}", constructor, pcx),
},
Bool(..)
| IntRange(..)
| F32Range(..)
| F64Range(..)
| Str(..)
| Opaque
| NonExhaustive
| Hidden
| Missing { .. }
| Wildcard => Fields::empty(),
Or => {
bug!("called `Fields::wildcards` on an `Or` ctor")
}
};
debug!(?ret);
ret
}
/// Returns the list of patterns.
pub(super) fn iter_patterns<'a>(
&'a self,
) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
self.fields.iter()
}
}
/// Values and patterns can be represented as a constructor applied to some fields. This represents
/// a pattern in this form.
/// This also uses interior mutability to keep track of whether the pattern has been found reachable
/// during analysis. For this reason they cannot be cloned.
/// A `DeconstructedPat` will almost always come from user input; the only exception are some
/// `Wildcard`s introduced during specialization.
pub(crate) struct DeconstructedPat<'p, 'tcx> {
ctor: Constructor<'tcx>,
fields: Fields<'p, 'tcx>,
ty: Ty<'tcx>,
span: Span,
reachable: Cell<bool>,
}
impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> {
pub(super) fn wildcard(ty: Ty<'tcx>, span: Span) -> Self {
Self::new(Wildcard, Fields::empty(), ty, span)
}
pub(super) fn new(
ctor: Constructor<'tcx>,
fields: Fields<'p, 'tcx>,
ty: Ty<'tcx>,
span: Span,
) -> Self {
DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) }
}
pub(crate) fn from_pat(cx: &MatchCheckCtxt<'p, 'tcx>, pat: &Pat<'tcx>) -> Self {
let mkpat = |pat| DeconstructedPat::from_pat(cx, pat);
let ctor;
let fields;
match &pat.kind {
PatKind::AscribeUserType { subpattern, .. }
| PatKind::InlineConstant { subpattern, .. } => return mkpat(subpattern),
PatKind::Binding { subpattern: Some(subpat), .. } => return mkpat(subpat),
PatKind::Binding { subpattern: None, .. } | PatKind::Wild => {
ctor = Wildcard;
fields = Fields::empty();
}
PatKind::Deref { subpattern } => {
ctor = Single;
fields = Fields::singleton(cx, mkpat(subpattern));
}
PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
match pat.ty.kind() {
ty::Tuple(fs) => {
ctor = Single;
let mut wilds: SmallVec<[_; 2]> =
fs.iter().map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
for pat in subpatterns {
wilds[pat.field.index()] = mkpat(&pat.pattern);
}
fields = Fields::from_iter(cx, wilds);
}
ty::Adt(adt, args) if adt.is_box() => {
// The only legal patterns of type `Box` (outside `std`) are `_` and box
// patterns. If we're here we can assume this is a box pattern.
// FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_,
// _)` or a box pattern. As a hack to avoid an ICE with the former, we
// ignore other fields than the first one. This will trigger an error later
// anyway.
// See https://github.com/rust-lang/rust/issues/82772 ,
// explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977
// The problem is that we can't know from the type whether we'll match
// normally or through box-patterns. We'll have to figure out a proper
// solution when we introduce generalized deref patterns. Also need to
// prevent mixing of those two options.
let pattern = subpatterns.into_iter().find(|pat| pat.field.index() == 0);
let pat = if let Some(pat) = pattern {
mkpat(&pat.pattern)
} else {
DeconstructedPat::wildcard(args.type_at(0), pat.span)
};
ctor = Single;
fields = Fields::singleton(cx, pat);
}
ty::Adt(adt, _) => {
ctor = match pat.kind {
PatKind::Leaf { .. } => Single,
PatKind::Variant { variant_index, .. } => Variant(variant_index),
_ => bug!(),
};
let variant = &adt.variant(ctor.variant_index_for_adt(*adt));
// For each field in the variant, we store the relevant index into `self.fields` if any.
let mut field_id_to_id: Vec<Option<usize>> =
(0..variant.fields.len()).map(|_| None).collect();
let tys = Fields::list_variant_nonhidden_fields(cx, pat.ty, variant)
.enumerate()
.map(|(i, (field, ty))| {
field_id_to_id[field.index()] = Some(i);
ty
});
let mut wilds: SmallVec<[_; 2]> =
tys.map(|ty| DeconstructedPat::wildcard(ty, pat.span)).collect();
for pat in subpatterns {
if let Some(i) = field_id_to_id[pat.field.index()] {
wilds[i] = mkpat(&pat.pattern);
}
}
fields = Fields::from_iter(cx, wilds);
}
_ => bug!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, pat.ty),
}
}
PatKind::Constant { value } => {
match pat.ty.kind() {
ty::Bool => {
ctor = match value.try_eval_bool(cx.tcx, cx.param_env) {
Some(b) => Bool(b),
None => Opaque,
};
fields = Fields::empty();
}
ty::Char | ty::Int(_) | ty::Uint(_) => {
ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
Some(bits) => IntRange(IntRange::from_bits(cx.tcx, pat.ty, bits)),
None => Opaque,
};
fields = Fields::empty();
}
ty::Float(ty::FloatTy::F32) => {
ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
Some(bits) => {
use rustc_apfloat::Float;
let value = rustc_apfloat::ieee::Single::from_bits(bits);
F32Range(value, value, RangeEnd::Included)
}
None => Opaque,
};
fields = Fields::empty();
}
ty::Float(ty::FloatTy::F64) => {
ctor = match value.try_eval_bits(cx.tcx, cx.param_env) {
Some(bits) => {
use rustc_apfloat::Float;
let value = rustc_apfloat::ieee::Double::from_bits(bits);
F64Range(value, value, RangeEnd::Included)
}
None => Opaque,
};
fields = Fields::empty();
}
ty::Ref(_, t, _) if t.is_str() => {
// We want a `&str` constant to behave like a `Deref` pattern, to be compatible
// with other `Deref` patterns. This could have been done in `const_to_pat`,
// but that causes issues with the rest of the matching code.
// So here, the constructor for a `"foo"` pattern is `&` (represented by
// `Single`), and has one field. That field has constructor `Str(value)` and no
// fields.
// Note: `t` is `str`, not `&str`.
let subpattern =
DeconstructedPat::new(Str(*value), Fields::empty(), *t, pat.span);
ctor = Single;
fields = Fields::singleton(cx, subpattern)
}
// All constants that can be structurally matched have already been expanded
// into the corresponding `Pat`s by `const_to_pat`. Constants that remain are
// opaque.
_ => {
ctor = Opaque;
fields = Fields::empty();
}
}
}
PatKind::Range(box PatRange { lo, hi, end, .. }) => {
let ty = pat.ty;
ctor = match ty.kind() {
ty::Char | ty::Int(_) | ty::Uint(_) => {
let lo =
MaybeInfiniteInt::from_pat_range_bdy(*lo, ty, cx.tcx, cx.param_env);
let hi =
MaybeInfiniteInt::from_pat_range_bdy(*hi, ty, cx.tcx, cx.param_env);
IntRange(IntRange::from_range(lo, hi, *end))
}
ty::Float(fty) => {
use rustc_apfloat::Float;
let lo = lo.as_finite().map(|c| c.eval_bits(cx.tcx, cx.param_env));
let hi = hi.as_finite().map(|c| c.eval_bits(cx.tcx, cx.param_env));
match fty {
ty::FloatTy::F32 => {
use rustc_apfloat::ieee::Single;
let lo = lo.map(Single::from_bits).unwrap_or(-Single::INFINITY);
let hi = hi.map(Single::from_bits).unwrap_or(Single::INFINITY);
F32Range(lo, hi, *end)
}
ty::FloatTy::F64 => {
use rustc_apfloat::ieee::Double;
let lo = lo.map(Double::from_bits).unwrap_or(-Double::INFINITY);
let hi = hi.map(Double::from_bits).unwrap_or(Double::INFINITY);
F64Range(lo, hi, *end)
}
}
}
_ => bug!("invalid type for range pattern: {}", ty),
};
fields = Fields::empty();
}
PatKind::Array { prefix, slice, suffix } | PatKind::Slice { prefix, slice, suffix } => {
let array_len = match pat.ty.kind() {
ty::Array(_, length) => {
Some(length.eval_target_usize(cx.tcx, cx.param_env) as usize)
}
ty::Slice(_) => None,
_ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty),
};
let kind = if slice.is_some() {
VarLen(prefix.len(), suffix.len())
} else {
FixedLen(prefix.len() + suffix.len())
};
ctor = Slice(Slice::new(array_len, kind));
fields =
Fields::from_iter(cx, prefix.iter().chain(suffix.iter()).map(|p| mkpat(&*p)));
}
PatKind::Or { .. } => {
ctor = Or;
let pats = expand_or_pat(pat);
fields = Fields::from_iter(cx, pats.into_iter().map(mkpat));
}
PatKind::Error(_) => {
ctor = Opaque;
fields = Fields::empty();
}
}
DeconstructedPat::new(ctor, fields, pat.ty, pat.span)
}
pub(super) fn is_or_pat(&self) -> bool {
matches!(self.ctor, Or)
}
pub(super) fn flatten_or_pat(&'p self) -> SmallVec<[&'p Self; 1]> {
if self.is_or_pat() {
self.iter_fields().flat_map(|p| p.flatten_or_pat()).collect()
} else {
smallvec![self]
}
}
pub(super) fn ctor(&self) -> &Constructor<'tcx> {
&self.ctor
}
pub(super) fn ty(&self) -> Ty<'tcx> {
self.ty
}
pub(super) fn span(&self) -> Span {
self.span
}
pub(super) fn iter_fields<'a>(
&'a self,
) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Captures<'a> {
self.fields.iter_patterns()
}
/// Specialize this pattern with a constructor.
/// `other_ctor` can be different from `self.ctor`, but must be covered by it.
pub(super) fn specialize<'a>(
&'a self,
pcx: &PatCtxt<'_, 'p, 'tcx>,
other_ctor: &Constructor<'tcx>,
) -> SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]> {
match (&self.ctor, other_ctor) {
(Wildcard, _) => {
// We return a wildcard for each field of `other_ctor`.
Fields::wildcards(pcx, other_ctor).iter_patterns().collect()
}
(Slice(self_slice), Slice(other_slice))
if self_slice.arity() != other_slice.arity() =>
{
// The only tricky case: two slices of different arity. Since `self_slice` covers
// `other_slice`, `self_slice` must be `VarLen`, i.e. of the form
// `[prefix, .., suffix]`. Moreover `other_slice` is guaranteed to have a larger
// arity. So we fill the middle part with enough wildcards to reach the length of
// the new, larger slice.
match self_slice.kind {
FixedLen(_) => bug!("{:?} doesn't cover {:?}", self_slice, other_slice),
VarLen(prefix, suffix) => {
let (ty::Slice(inner_ty) | ty::Array(inner_ty, _)) = *self.ty.kind() else {
bug!("bad slice pattern {:?} {:?}", self.ctor, self.ty);
};
let prefix = &self.fields.fields[..prefix];
let suffix = &self.fields.fields[self_slice.arity() - suffix..];
let wildcard: &_ = pcx
.cx
.pattern_arena
.alloc(DeconstructedPat::wildcard(inner_ty, pcx.span));
let extra_wildcards = other_slice.arity() - self_slice.arity();
let extra_wildcards = (0..extra_wildcards).map(|_| wildcard);
prefix.iter().chain(extra_wildcards).chain(suffix).collect()
}
}
}
_ => self.fields.iter_patterns().collect(),
}
}
/// We keep track for each pattern if it was ever reachable during the analysis. This is used
/// with `unreachable_spans` to report unreachable subpatterns arising from or patterns.
pub(super) fn set_reachable(&self) {
self.reachable.set(true)
}
pub(super) fn is_reachable(&self) -> bool {
self.reachable.get()
}
/// Report the spans of subpatterns that were not reachable, if any.
pub(super) fn unreachable_spans(&self) -> Vec<Span> {
let mut spans = Vec::new();
self.collect_unreachable_spans(&mut spans);
spans
}
fn collect_unreachable_spans(&self, spans: &mut Vec<Span>) {
// We don't look at subpatterns if we already reported the whole pattern as unreachable.
if !self.is_reachable() {
spans.push(self.span);
} else {
for p in self.iter_fields() {
p.collect_unreachable_spans(spans);
}
}
}
}
/// This is mostly copied from the `Pat` impl. This is best effort and not good enough for a
/// `Display` impl.
impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// Printing lists is a chore.
let mut first = true;
let mut start_or_continue = |s| {
if first {
first = false;
""
} else {
s
}
};
let mut start_or_comma = || start_or_continue(", ");
match &self.ctor {
Single | Variant(_) => match self.ty.kind() {
ty::Adt(def, _) if def.is_box() => {
// Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
// of `std`). So this branch is only reachable when the feature is enabled and
// the pattern is a box pattern.
let subpattern = self.iter_fields().next().unwrap();
write!(f, "box {subpattern:?}")
}
ty::Adt(..) | ty::Tuple(..) => {
let variant = match self.ty.kind() {
ty::Adt(adt, _) => Some(adt.variant(self.ctor.variant_index_for_adt(*adt))),
ty::Tuple(_) => None,
_ => unreachable!(),
};
if let Some(variant) = variant {
write!(f, "{}", variant.name)?;
}
// Without `cx`, we can't know which field corresponds to which, so we can't
// get the names of the fields. Instead we just display everything as a tuple
// struct, which should be good enough.
write!(f, "(")?;
for p in self.iter_fields() {
write!(f, "{}", start_or_comma())?;
write!(f, "{p:?}")?;
}
write!(f, ")")
}
// Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
// be careful to detect strings here. However a string literal pattern will never
// be reported as a non-exhaustiveness witness, so we can ignore this issue.
ty::Ref(_, _, mutbl) => {
let subpattern = self.iter_fields().next().unwrap();
write!(f, "&{}{:?}", mutbl.prefix_str(), subpattern)
}
_ => write!(f, "_"),
},
Slice(slice) => {
let mut subpatterns = self.fields.iter_patterns();
write!(f, "[")?;
match slice.kind {
FixedLen(_) => {
for p in subpatterns {
write!(f, "{}{:?}", start_or_comma(), p)?;
}
}
VarLen(prefix_len, _) => {
for p in subpatterns.by_ref().take(prefix_len) {
write!(f, "{}{:?}", start_or_comma(), p)?;
}
write!(f, "{}", start_or_comma())?;
write!(f, "..")?;
for p in subpatterns {
write!(f, "{}{:?}", start_or_comma(), p)?;
}
}
}
write!(f, "]")
}
Bool(b) => write!(f, "{b}"),
// Best-effort, will render signed ranges incorrectly
IntRange(range) => write!(f, "{range:?}"),
F32Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
F64Range(lo, hi, end) => write!(f, "{lo}{end}{hi}"),
Str(value) => write!(f, "{value}"),
Opaque => write!(f, "<constant pattern>"),
Or => {
for pat in self.iter_fields() {
write!(f, "{}{:?}", start_or_continue(" | "), pat)?;
}
Ok(())
}
Wildcard | Missing { .. } | NonExhaustive | Hidden => write!(f, "_ : {:?}", self.ty),
}
}
}
/// Same idea as `DeconstructedPat`, except this is a fictitious pattern built up for diagnostics
/// purposes. As such they don't use interning and can be cloned.
#[derive(Debug, Clone)]
pub(crate) struct WitnessPat<'tcx> {
ctor: Constructor<'tcx>,
pub(crate) fields: Vec<WitnessPat<'tcx>>,
ty: Ty<'tcx>,
}
impl<'tcx> WitnessPat<'tcx> {
pub(super) fn new(ctor: Constructor<'tcx>, fields: Vec<Self>, ty: Ty<'tcx>) -> Self {
Self { ctor, fields, ty }
}
pub(super) fn wildcard(ty: Ty<'tcx>) -> Self {
Self::new(Wildcard, Vec::new(), ty)
}
/// Construct a pattern that matches everything that starts with this constructor.
/// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
/// `Some(_)`.
pub(super) fn wild_from_ctor(pcx: &PatCtxt<'_, '_, 'tcx>, ctor: Constructor<'tcx>) -> Self {
// Reuse `Fields::wildcards` to get the types.
let fields = Fields::wildcards(pcx, &ctor)
.iter_patterns()
.map(|deco_pat| Self::wildcard(deco_pat.ty()))
.collect();
Self::new(ctor, fields, pcx.ty)
}
pub(super) fn ctor(&self) -> &Constructor<'tcx> {
&self.ctor
}
pub(super) fn ty(&self) -> Ty<'tcx> {
self.ty
}
/// Convert back to a `thir::Pat` for diagnostic purposes. This panics for patterns that don't
/// appear in diagnostics, like float ranges.
pub(crate) fn to_diagnostic_pat(&self, cx: &MatchCheckCtxt<'_, 'tcx>) -> Pat<'tcx> {
let is_wildcard = |pat: &Pat<'_>| matches!(pat.kind, PatKind::Wild);
let mut subpatterns = self.iter_fields().map(|p| Box::new(p.to_diagnostic_pat(cx)));
let kind = match &self.ctor {
Bool(b) => PatKind::Constant { value: mir::Const::from_bool(cx.tcx, *b) },
IntRange(range) => return range.to_diagnostic_pat(self.ty, cx.tcx),
Single | Variant(_) => match self.ty.kind() {
ty::Tuple(..) => PatKind::Leaf {
subpatterns: subpatterns
.enumerate()
.map(|(i, pattern)| FieldPat { field: FieldIdx::new(i), pattern })
.collect(),
},
ty::Adt(adt_def, _) if adt_def.is_box() => {
// Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
// of `std`). So this branch is only reachable when the feature is enabled and
// the pattern is a box pattern.
PatKind::Deref { subpattern: subpatterns.next().unwrap() }
}
ty::Adt(adt_def, args) => {
let variant_index = self.ctor.variant_index_for_adt(*adt_def);
let variant = &adt_def.variant(variant_index);
let subpatterns = Fields::list_variant_nonhidden_fields(cx, self.ty, variant)
.zip(subpatterns)
.map(|((field, _ty), pattern)| FieldPat { field, pattern })
.collect();
if adt_def.is_enum() {
PatKind::Variant { adt_def: *adt_def, args, variant_index, subpatterns }
} else {
PatKind::Leaf { subpatterns }
}
}
// Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
// be careful to reconstruct the correct constant pattern here. However a string
// literal pattern will never be reported as a non-exhaustiveness witness, so we
// ignore this issue.
ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
_ => bug!("unexpected ctor for type {:?} {:?}", self.ctor, self.ty),
},
Slice(slice) => {
match slice.kind {
FixedLen(_) => PatKind::Slice {
prefix: subpatterns.collect(),
slice: None,
suffix: Box::new([]),
},
VarLen(prefix, _) => {
let mut subpatterns = subpatterns.peekable();
let mut prefix: Vec<_> = subpatterns.by_ref().take(prefix).collect();
if slice.array_len.is_some() {
// Improves diagnostics a bit: if the type is a known-size array, instead
// of reporting `[x, _, .., _, y]`, we prefer to report `[x, .., y]`.
// This is incorrect if the size is not known, since `[_, ..]` captures
// arrays of lengths `>= 1` whereas `[..]` captures any length.
while !prefix.is_empty() && is_wildcard(prefix.last().unwrap()) {
prefix.pop();
}
while subpatterns.peek().is_some()
&& is_wildcard(subpatterns.peek().unwrap())
{
subpatterns.next();
}
}
let suffix: Box<[_]> = subpatterns.collect();
let wild = Pat::wildcard_from_ty(self.ty);
PatKind::Slice {
prefix: prefix.into_boxed_slice(),
slice: Some(Box::new(wild)),
suffix,
}
}
}
}
&Str(value) => PatKind::Constant { value },
Wildcard | NonExhaustive | Hidden => PatKind::Wild,
Missing { .. } => bug!(
"trying to convert a `Missing` constructor into a `Pat`; this is probably a bug,
`Missing` should have been processed in `apply_constructors`"
),
F32Range(..) | F64Range(..) | Opaque | Or => {
bug!("can't convert to pattern: {:?}", self)
}
};
Pat { ty: self.ty, span: DUMMY_SP, kind }
}
pub(super) fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a WitnessPat<'tcx>> {
self.fields.iter()
}
}