diff options
Diffstat (limited to 'compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs')
| -rw-r--r-- | compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs | 1923 |
1 files changed, 1071 insertions, 852 deletions
diff --git a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs index b79beb1c5..0c7c2c6f9 100644 --- a/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs +++ b/compiler/rustc_mir_build/src/thir/pattern/deconstruct_pat.rs @@ -39,35 +39,35 @@ //! //! 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 [`SplitWildcard`]; for integer ranges, see [`SplitIntRange`]; for slices, see -//! [`SplitVarLenSlice`]. +//! 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 std::ops::RangeInclusive; use smallvec::{smallvec, SmallVec}; +use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS}; use rustc_data_structures::captures::Captures; -use rustc_hir::{HirId, RangeEnd}; +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::thir::{FieldPat, Pat, PatKind, PatRange}; +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_session::lint; use rustc_span::{Span, DUMMY_SP}; -use rustc_target::abi::{FieldIdx, Integer, Size, VariantIdx, FIRST_VARIANT}; +use rustc_target::abi::{FieldIdx, Integer, VariantIdx, FIRST_VARIANT}; use self::Constructor::*; +use self::MaybeInfiniteInt::*; use self::SliceKind::*; -use super::compare_const_vals; use super::usefulness::{MatchCheckCtxt, PatCtxt}; -use crate::errors::{Overlap, OverlappingRangeEndpoints}; /// 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>> { @@ -86,324 +86,317 @@ fn expand_or_pat<'p, 'tcx>(pat: &'p Pat<'tcx>) -> Vec<&'p Pat<'tcx>> { pats } -/// An inclusive interval, used for precise integer exhaustiveness checking. -/// `IntRange`s always store a contiguous range. This means that values are -/// encoded such that `0` encodes the minimum value for the integer, -/// regardless of the signedness. -/// For example, the pattern `-128..=127i8` is encoded as `0..=255`. -/// This makes comparisons and arithmetic on interval endpoints much more -/// straightforward. See `signed_bias` for details. -/// -/// `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, PartialEq, Eq)] -pub(crate) struct IntRange { - range: RangeInclusive<u128>, - /// Keeps the bias used for encoding the range. It depends on the type of the range and - /// possibly the pointer size of the current architecture. The algorithm ensures we never - /// compare `IntRange`s with different types/architectures. - bias: u128, +/// Whether we have seen a constructor in the column or not. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +enum Presence { + Unseen, + Seen, } -impl IntRange { - #[inline] - fn is_integral(ty: Ty<'_>) -> bool { - matches!(ty.kind(), ty::Char | ty::Int(_) | ty::Uint(_) | ty::Bool) - } - - fn is_singleton(&self) -> bool { - self.range.start() == self.range.end() - } - - fn boundaries(&self) -> (u128, u128) { - (*self.range.start(), *self.range.end()) - } +/// 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, +} - #[inline] - fn integral_size_and_signed_bias(tcx: TyCtxt<'_>, ty: Ty<'_>) -> Option<(Size, u128)> { +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::Bool => Some((Size::from_bytes(1), 0)), - ty::Char => Some((Size::from_bytes(4), 0)), ty::Int(ity) => { - let size = Integer::from_int_ty(&tcx, ity).size(); - Some((size, 1u128 << (size.bits() as u128 - 1))) + let bits = Integer::from_int_ty(&tcx, ity).size().bits() as u128; + 1u128 << (bits - 1) } - ty::Uint(uty) => Some((Integer::from_uint_ty(&tcx, uty).size(), 0)), - _ => None, + _ => 0, } } - #[inline] - fn from_constant<'tcx>( + 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>, - value: mir::Const<'tcx>, - ) -> Option<IntRange> { - let ty = value.ty(); - let (target_size, bias) = Self::integral_size_and_signed_bias(tcx, ty)?; - let val = match value { - mir::Const::Ty(c) if let ty::ConstKind::Value(valtree) = c.kind() => { - valtree.unwrap_leaf().to_bits(target_size).ok() - }, - // This is a more general form of the previous case. - _ => value.try_eval_bits(tcx, param_env), - }?; - - let val = val ^ bias; - Some(IntRange { range: val..=val, bias }) + ) -> 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, + } } - #[inline] - fn from_range<'tcx>( - tcx: TyCtxt<'tcx>, - lo: u128, - hi: u128, + /// 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>, - end: &RangeEnd, - ) -> Option<IntRange> { - Self::is_integral(ty).then(|| { - // Perform a shift if the underlying types are signed, - // which makes the interval arithmetic simpler. - let bias = IntRange::signed_bias(tcx, ty); - let (lo, hi) = (lo ^ bias, hi ^ bias); - let offset = (*end == RangeEnd::Excluded) as u128; - if lo > hi || (lo == hi && *end == RangeEnd::Excluded) { - // This should have been caught earlier by E0030. - bug!("malformed range pattern: {}..={}", lo, (hi - offset)); + 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, + } } - IntRange { range: lo..=(hi - offset), bias } - }) + JustAfterMax | PosInfinity => PatRangeBoundary::PosInfinity, + } } - // The return value of `signed_bias` should be XORed with an endpoint 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, + /// 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, } } - - fn is_subrange(&self, other: &Self) -> bool { - other.range.start() <= self.range.start() && self.range.end() <= other.range.end() + /// 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, + } } +} - fn intersection(&self, other: &Self) -> Option<Self> { - let (lo, hi) = self.boundaries(); - let (other_lo, other_hi) = other.boundaries(); - if lo <= other_hi && other_lo <= hi { - Some(IntRange { range: max(lo, other_lo)..=min(hi, other_hi), bias: self.bias }) - } else { - None - } +/// 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(_)) } - fn suspicious_intersection(&self, other: &Self) -> bool { - // `false` in the following cases: - // 1 ---- // 1 ---------- // 1 ---- // 1 ---- - // 2 ---------- // 2 ---- // 2 ---- // 2 ---- - // - // The following are currently `false`, but could be `true` in the future (#64007): - // 1 --------- // 1 --------- - // 2 ---------- // 2 ---------- - // - // `true` in the following cases: - // 1 ------- // 1 ------- - // 2 -------- // 2 ------- - let (lo, hi) = self.boundaries(); - let (other_lo, other_hi) = other.boundaries(); - (lo == other_hi || hi == other_lo) && !self.is_singleton() && !other.is_singleton() + /// 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 } - /// Only used for displaying the range properly. - fn to_pat<'tcx>(&self, tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> { - let (lo, hi) = self.boundaries(); + #[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() } + } - let bias = self.bias; - let (lo, hi) = (lo ^ bias, hi ^ bias); + #[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 } + } - let env = ty::ParamEnv::empty().and(ty); - let lo_const = mir::Const::from_bits(tcx, lo, env); - let hi_const = mir::Const::from_bits(tcx, hi, env); + fn is_subrange(&self, other: &Self) -> bool { + other.lo <= self.lo && self.hi <= other.hi + } - let kind = if lo == hi { - PatKind::Constant { value: lo_const } + 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 { - PatKind::Range(Box::new(PatRange { - lo: lo_const, - hi: hi_const, - end: RangeEnd::Included, - })) - }; - - Pat { ty, span: DUMMY_SP, kind } + None + } } - /// Lint on likely incorrect range patterns (#63987) - pub(super) fn lint_overlapping_range_endpoints<'a, 'p: 'a, 'tcx: 'a>( + /// 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, - pcx: &PatCtxt<'_, 'p, 'tcx>, - pats: impl Iterator<Item = &'a DeconstructedPat<'p, 'tcx>>, - column_count: usize, - lint_root: HirId, - ) { - if self.is_singleton() { - return; - } - - if column_count != 1 { - // FIXME: for now, only check for overlapping ranges on simple range - // patterns. Otherwise with the current logic the following is detected - // as overlapping: - // ``` - // match (0u8, true) { - // (0 ..= 125, false) => {} - // (125 ..= 255, true) => {} - // _ => {} - // } - // ``` - return; - } - - let overlap: Vec<_> = pats - .filter_map(|pat| Some((pat.ctor().as_int_range()?, pat.span()))) - .filter(|(range, _)| self.suspicious_intersection(range)) - .map(|(range, span)| Overlap { - range: self.intersection(&range).unwrap().to_pat(pcx.cx.tcx, pcx.ty), - span, - }) + 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) + }) + } - if !overlap.is_empty() { - pcx.cx.tcx.emit_spanned_lint( - lint::builtin::OVERLAPPING_RANGE_ENDPOINTS, - lint_root, - pcx.span, - OverlappingRangeEndpoints { overlap, range: pcx.span }, - ); + /// 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)) } } - - /// See `Constructor::is_covered_by` - fn is_covered_by(&self, other: &Self) -> bool { - if self.intersection(other).is_some() { - // Constructor splitting should ensure that all intersections we encounter are actually - // inclusions. - assert!(self.is_subrange(other)); - true + /// 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 { - false - } + // 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 is often not what we want: e.g. `false` is converted into the range `0..=0` and -/// would be displayed as such. To render properly, convert to a pattern first. +/// 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 { - let (lo, hi) = self.boundaries(); - let bias = self.bias; - let (lo, hi) = (lo ^ bias, hi ^ bias); - write!(f, "{lo}")?; - write!(f, "{}", RangeEnd::Included)?; - write!(f, "{hi}") - } -} - -/// Represents a border between 2 integers. Because the intervals spanning borders must be able to -/// cover every integer, we need to be able to represent 2^128 + 1 such borders. -#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] -enum IntBorder { - JustBefore(u128), - AfterMax, -} - -/// A range of integers that is partitioned into disjoint subranges. This does constructor -/// splitting for integer ranges as explained at the top of the file. -/// -/// This is fed multiple ranges, and returns an output that covers the input, but is split so that -/// the only intersections between an output range and a seen range are inclusions. No output range -/// straddles the boundary of one of the inputs. -/// -/// The following input: -/// ```text -/// |-------------------------| // `self` -/// |------| |----------| |----| -/// |-------| |-------| -/// ``` -/// would be iterated over as follows: -/// ```text -/// ||---|--||-|---|---|---|--| -/// ``` -#[derive(Debug, Clone)] -struct SplitIntRange { - /// The range we are splitting - range: IntRange, - /// The borders of ranges we have seen. They are all contained within `range`. This is kept - /// sorted. - borders: Vec<IntBorder>, -} - -impl SplitIntRange { - fn new(range: IntRange) -> Self { - SplitIntRange { range, borders: Vec::new() } - } - - /// Internal use - fn to_borders(r: IntRange) -> [IntBorder; 2] { - use IntBorder::*; - let (lo, hi) = r.boundaries(); - let lo = JustBefore(lo); - let hi = match hi.checked_add(1) { - Some(m) => JustBefore(m), - None => AfterMax, - }; - [lo, hi] - } - - /// Add ranges relative to which we split. - fn split(&mut self, ranges: impl Iterator<Item = IntRange>) { - let this_range = &self.range; - let included_ranges = ranges.filter_map(|r| this_range.intersection(&r)); - let included_borders = included_ranges.flat_map(|r| { - let borders = Self::to_borders(r); - once(borders[0]).chain(once(borders[1])) - }); - self.borders.extend(included_borders); - self.borders.sort_unstable(); - } - - /// Iterate over the contained ranges. - fn iter(&self) -> impl Iterator<Item = IntRange> + Captures<'_> { - use IntBorder::*; - - let self_range = Self::to_borders(self.range.clone()); - // Start with the start of the range. - let mut prev_border = self_range[0]; - self.borders - .iter() - .copied() - // End with the end of the range. - .chain(once(self_range[1])) - // List pairs of adjacent borders. - .map(move |border| { - let ret = (prev_border, border); - prev_border = border; - ret - }) - // Skip duplicates. - .filter(|(prev_border, border)| prev_border != border) - // Finally, convert to ranges. - .map(move |(prev_border, border)| { - let range = match (prev_border, border) { - (JustBefore(n), JustBefore(m)) if n < m => n..=(m - 1), - (JustBefore(n), AfterMax) => n..=u128::MAX, - _ => unreachable!(), // Ruled out by the sorting and filtering we did - }; - IntRange { range, bias: self.range.bias } - }) + if let Finite(lo) = self.lo { + write!(f, "{lo}")?; + } + write!(f, "{}", RangeEnd::Excluded)?; + if let Finite(hi) = self.hi { + write!(f, "{hi}")?; + } + Ok(()) } } @@ -463,142 +456,164 @@ impl Slice { 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] | ...`. The corresponding value constructors are fixed-length array constructors above a -/// given minimum length. 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] => {} -/// [_, _, _, _, _ ] => {} -/// # _ => {} -/// # }} -/// ``` -/// -/// If we went above length 5, we would simply be inserting more columns full of wildcards in the -/// middle. This means that the set of witnesses for length `l >= 5` if equivalent to the set for -/// any other `l' >= 5`: simply add or remove wildcards in the middle to convert between them. -/// -/// 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. Therefore a -/// variable-length slice can be split into a variable-length slice of minimal length `L`, and many -/// fixed-length slices of lengths `< L`. -/// -/// For each variable-length 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 added/removed without affecting them - creating equivalent patterns from any -/// sufficiently-large length. -/// -/// Of course, if fixed-length patterns exist, we must be sure that our length is large enough to -/// miss them all, so we can pick `L = max(max(FIXED_LEN)+1, max(PREFIX_LEN) + max(SUFFIX_LEN))` -/// -/// `max_slice` below will be made to have arity `L`. -#[derive(Debug)] -struct SplitVarLenSlice { - /// If the type is an array, this is its size. - array_len: Option<usize>, - /// The arity of the input slice. - arity: usize, - /// The smallest slice bigger than any slice seen. `max_slice.arity()` is the length `L` - /// described above. - max_slice: SliceKind, -} - -impl SplitVarLenSlice { - fn new(prefix: usize, suffix: usize, array_len: Option<usize>) -> Self { - SplitVarLenSlice { array_len, arity: prefix + suffix, max_slice: VarLen(prefix, suffix) } - } - - /// Pass a set of slices relative to which to split this one. - fn split(&mut self, slices: impl Iterator<Item = SliceKind>) { - let VarLen(max_prefix_len, max_suffix_len) = &mut self.max_slice else { - // No need to split - return; - }; - // We grow `self.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 slices { - match slice { - FixedLen(len) => { - max_fixed_len = cmp::max(max_fixed_len, len); + /// 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); + } + } } - VarLen(prefix, suffix) => { - *max_prefix_len = cmp::max(*max_prefix_len, prefix); - *max_suffix_len = cmp::max(*max_suffix_len, 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 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 self.max_slice.arity() >= len => self.max_slice = FixedLen(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), + _ => {} + } - /// Iterate over the partition of this slice. - fn iter(&self) -> impl Iterator<Item = Slice> + Captures<'_> { - let 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 cover all arities in the range `(self.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..self.max_slice.arity(), + 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(self.max_slice)) - .map(move |kind| Slice::new(self.array_len, kind)) + + 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)) + }) } } @@ -616,10 +631,13 @@ pub(super) enum Constructor<'tcx> { 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`). - FloatRange(mir::Const<'tcx>, mir::Const<'tcx>, RangeEnd), + 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. @@ -628,66 +646,50 @@ pub(super) enum Constructor<'tcx> { /// 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, - /// Stands for constructors that are not seen in the matrix, as explained in the documentation - /// for [`SplitWildcard`]. The carried `bool` is used for the `non_exhaustive_omitted_patterns` - /// lint. - Missing { nonexhaustive_enum_missing_real_variants: bool }, - /// Wildcard pattern. - Wildcard, - /// Or-pattern. - Or, + /// 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_wildcard(&self) -> bool { - matches!(self, Wildcard) - } - pub(super) fn is_non_exhaustive(&self) -> bool { matches!(self, NonExhaustive) } - fn as_int_range(&self) -> Option<&IntRange> { + pub(super) fn as_variant(&self) -> Option<VariantIdx> { match self { - IntRange(range) => Some(range), + Variant(i) => Some(*i), _ => None, } } - - fn as_slice(&self) -> Option<Slice> { + fn as_bool(&self) -> Option<bool> { match self { - Slice(slice) => Some(*slice), + Bool(b) => Some(*b), _ => None, } } - - /// Checks if the `Constructor` is a variant and `TyCtxt::eval_stability` returns - /// `EvalResult::Deny { .. }`. - /// - /// This means that the variant has a stdlib unstable feature marking it. - pub(super) fn is_unstable_variant(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> bool { - if let Constructor::Variant(idx) = self && let ty::Adt(adt, _) = pcx.ty.kind() { - let variant_def_id = adt.variant(*idx).def_id; - // Filter variants that depend on a disabled unstable feature. - return matches!( - pcx.cx.tcx.eval_stability(variant_def_id, None, DUMMY_SP, None), - EvalResult::Deny { .. } - ); + pub(super) fn as_int_range(&self) -> Option<&IntRange> { + match self { + IntRange(range) => Some(range), + _ => None, } - false } - - /// Checks if the `Constructor` is a `Constructor::Variant` with a `#[doc(hidden)]` - /// attribute from a type not local to the current crate. - pub(super) fn is_doc_hidden_variant(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> bool { - if let Constructor::Variant(idx) = self && let ty::Adt(adt, _) = pcx.ty.kind() { - let variant_def_id = adt.variants()[*idx].def_id; - return pcx.cx.tcx.is_doc_hidden(variant_def_id) && !variant_def_id.is_local(); + fn as_slice(&self) -> Option<Slice> { + match self { + Slice(slice) => Some(*slice), + _ => None, } - false } fn variant_index_for_adt(&self, adt: ty::AdtDef<'tcx>) -> VariantIdx { @@ -721,30 +723,33 @@ impl<'tcx> Constructor<'tcx> { _ => bug!("Unexpected type for `Single` constructor: {:?}", pcx.ty), }, Slice(slice) => slice.arity(), - Str(..) - | FloatRange(..) + Bool(..) | IntRange(..) - | NonExhaustive + | 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. + /// 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 wrt 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. + /// 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 and - /// diagnostics. Eg. for the `_` case, we ignore the constructors already present in the - /// matrix, unless all of them are. + /// 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>, @@ -755,23 +760,68 @@ impl<'tcx> Constructor<'tcx> { { match self { Wildcard => { - let mut split_wildcard = SplitWildcard::new(pcx); - split_wildcard.split(pcx, ctors); - split_wildcard.into_ctors(pcx) + 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. In particular, we don't do the overlapping - // ranges check. - IntRange(ctor_range) if !ctor_range.is_singleton() => { - let mut split_range = SplitIntRange::new(ctor_range.clone()); - let int_ranges = ctors.filter_map(|ctor| ctor.as_int_range()); - split_range.split(int_ranges.cloned()); - split_range.iter().map(IntRange).collect() + // 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(Slice { kind: VarLen(self_prefix, self_suffix), array_len }) => { - let mut split_self = SplitVarLenSlice::new(self_prefix, self_suffix, array_len); - let slices = ctors.filter_map(|c| c.as_slice()).map(|s| s.kind); - split_self.split(slices); - split_self.iter().map(Slice).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()], @@ -788,28 +838,29 @@ impl<'tcx> Constructor<'tcx> { match (self, other) { // Wildcards cover anything (_, Wildcard) => true, - // The missing ctors are not covered by anything in the matrix except wildcards. - (Missing { .. } | Wildcard, _) => false, + // 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, - - (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range), - ( - FloatRange(self_from, self_to, self_end), - FloatRange(other_from, other_to, other_end), - ) => { - match ( - compare_const_vals(pcx.cx.tcx, *self_to, *other_to, pcx.cx.param_env), - compare_const_vals(pcx.cx.tcx, *self_from, *other_from, pcx.cx.param_env), - ) { - (Some(to), Some(from)) => { - (from == Ordering::Greater || from == Ordering::Equal) - && (to == Ordering::Less - || (other_end == self_end && to == Ordering::Equal)) + (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, } - _ => false, - } } (Str(self_val), Str(other_val)) => { // FIXME Once valtrees are available we can directly use the bytes @@ -820,8 +871,6 @@ impl<'tcx> Constructor<'tcx> { // We are trying to inspect an opaque constant. Thus we skip the row. (Opaque, _) | (_, Opaque) => false, - // Only a wildcard pattern can match the special extra constructor. - (NonExhaustive, _) => false, _ => span_bug!( pcx.span, @@ -831,96 +880,131 @@ impl<'tcx> Constructor<'tcx> { ), } } +} - /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is - /// assumed to be built from `matrix.head_ctors()` with wildcards and opaques filtered out, - /// and `self` is assumed to have been split from a wildcard. - fn is_covered_by_any<'p>( - &self, - pcx: &PatCtxt<'_, 'p, 'tcx>, - used_ctors: &[Constructor<'tcx>], - ) -> bool { - if used_ctors.is_empty() { - return false; - } - - // This must be kept in sync with `is_covered_by`. - match self { - // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s. - Single => !used_ctors.is_empty(), - Variant(vid) => used_ctors.iter().any(|c| matches!(c, Variant(i) if i == vid)), - IntRange(range) => used_ctors - .iter() - .filter_map(|c| c.as_int_range()) - .any(|other| range.is_covered_by(other)), - Slice(slice) => used_ctors - .iter() - .filter_map(|c| c.as_slice()) - .any(|other| slice.is_covered_by(other)), - // This constructor is never covered by anything else - NonExhaustive => false, - Str(..) | FloatRange(..) | Opaque | Missing { .. } | Wildcard | Or => { - span_bug!(pcx.span, "found unexpected ctor in all_ctors: {:?}", self) - } - } - } +/// 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, } -/// A wildcard constructor that we split relative to the constructors in the matrix, as explained -/// at the top of the file. +/// Describes the result of analyzing the constructors in a column of a match. /// -/// A constructor that is not present in the matrix rows will only be covered by the rows that have -/// wildcards. Thus we can group all of those constructors together; we call them "missing -/// constructors". Splitting a wildcard would therefore list all present constructors individually -/// (or grouped if they are integers or slices), and then all missing constructors together as a -/// group. +/// `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. /// -/// However we can go further: since any constructor will match the wildcard rows, and having more -/// rows can only reduce the amount of usefulness witnesses, we can skip the present constructors -/// and only try the missing ones. -/// This will not preserve the whole list of witnesses, but will preserve whether the list is empty -/// or not. In fact this is quite natural from the point of view of diagnostics too. This is done -/// in `to_ctors`: in some cases we only return `Missing`. +/// 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 SplitWildcard<'tcx> { - /// Constructors (other than wildcards and opaques) seen in the matrix. - matrix_ctors: Vec<Constructor<'tcx>>, - /// All the constructors for this type - all_ctors: SmallVec<[Constructor<'tcx>; 1]>, +pub(super) struct SplitConstructorSet<'tcx> { + pub(super) present: SmallVec<[Constructor<'tcx>; 1]>, + pub(super) missing: Vec<Constructor<'tcx>>, } -impl<'tcx> SplitWildcard<'tcx> { - pub(super) fn new<'p>(pcx: &PatCtxt<'_, 'p, 'tcx>) -> Self { - debug!("SplitWildcard::new({:?})", pcx.ty); - let cx = pcx.cx; +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( - // `unwrap()` is ok because we know the type is an integer. - IntRange::from_range(cx.tcx, start, end, pcx.ty, &RangeEnd::Included).unwrap(), + 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 `pcx.ty`. For numbers, + // 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 empty if and only if the type is uninhabited (as determined by + // Invariant: this is `Uninhabited` if and only if the type is uninhabited (as determined by // `cx.is_uninhabited()`). - let all_ctors = match pcx.ty.kind() { - ty::Bool => smallvec![make_range(0, 1)], + 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) { - smallvec![] + Self::Uninhabited } else { - smallvec![Slice(Slice::new(Some(len), VarLen(0, 0)))] + Self::Slice(Some(len)) } } // Treat arrays of a constant but unknown length like slices. ty::Array(sub_ty, _) | ty::Slice(sub_ty) => { - let kind = if cx.is_uninhabited(*sub_ty) { FixedLen(0) } else { VarLen(0, 0) }; - smallvec![Slice(Slice::new(None, kind))] + 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 @@ -939,19 +1023,14 @@ impl<'tcx> SplitWildcard<'tcx> { // // 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(pcx.ty); - - let is_exhaustive_pat_feature = cx.tcx.features().exhaustive_patterns; - - // If `exhaustive_patterns` is disabled and our scrutinee is an empty enum, we treat it - // as though it had an "unknown" constructor to avoid exposing its emptiness. The - // exception is if the pattern is at the top level, because we want empty matches to be - // considered exhaustive. - let is_secretly_empty = - def.variants().is_empty() && !is_exhaustive_pat_feature && !pcx.is_top_level; + let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive_enum(ty); - let mut ctors: SmallVec<[_; 1]> = - def.variants() + 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 @@ -961,135 +1040,188 @@ impl<'tcx> SplitWildcard<'tcx> { .instantiate(cx.tcx, args) .apply(cx.tcx, cx.param_env, cx.module) }) - .map(|(idx, _)| Variant(idx)) - .collect(); + .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, + } + } - if is_secretly_empty || is_declared_nonexhaustive { - ctors.push(NonExhaustive); + /// 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); } - ctors } - ty::Char => { - smallvec![ - // The valid Unicode Scalar Value ranges. - make_range('\u{0000}' as u128, '\u{D7FF}' as u128), - make_range('\u{E000}' as u128, '\u{10FFFF}' as u128), - ] + 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); + } } - ty::Int(_) | ty::Uint(_) - if pcx.ty.is_ptr_sized_integral() - && !cx.tcx.features().precise_pointer_size_matching => - { - // `usize`/`isize` are not allowed to be matched exhaustively unless the - // `precise_pointer_size_matching` feature is enabled. So we treat those types like - // `#[non_exhaustive]` enums by returning a special unmatchable constructor. - smallvec![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)); + } } - &ty::Int(ity) => { - let bits = Integer::from_int_ty(&cx.tcx, ity).size().bits() as u128; - let min = 1u128 << (bits - 1); - let max = min - 1; - smallvec![make_range(min, max)] + 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)), + } + } + } } - &ty::Uint(uty) => { - let size = Integer::from_uint_ty(&cx.tcx, uty).size(); - let max = size.truncate(u128::MAX); - smallvec![make_range(0, max)] + &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 => {} + } + } } - // If `exhaustive_patterns` is disabled and our scrutinee is the never type, we cannot + 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. - ty::Never if !cx.tcx.features().exhaustive_patterns && !pcx.is_top_level => { - smallvec![NonExhaustive] + ConstructorSet::Uninhabited + if !pcx.cx.tcx.features().exhaustive_patterns && !pcx.is_top_level => + { + missing.push(NonExhaustive); } - ty::Never => smallvec![], - _ if cx.is_uninhabited(pcx.ty) => smallvec![], - ty::Adt(..) | ty::Tuple(..) | ty::Ref(..) => smallvec![Single], - // This type is one for which we cannot list constructors, like `str` or `f64`. - _ => smallvec![NonExhaustive], - }; + ConstructorSet::Uninhabited => {} + } - SplitWildcard { matrix_ctors: Vec::new(), all_ctors } + SplitConstructorSet { present, missing } } - /// Pass a set of constructors relative to which to split this one. Don't call twice, it won't - /// do what you want. - pub(super) fn split<'a>( - &mut self, + /// 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, - ) where + ) -> Vec<Constructor<'tcx>> + where 'tcx: 'a, { - // Since `all_ctors` never contains wildcards, this won't recurse further. - self.all_ctors = - self.all_ctors.iter().flat_map(|ctor| ctor.split(pcx, ctors.clone())).collect(); - self.matrix_ctors = ctors.filter(|c| !matches!(c, Wildcard | Opaque)).cloned().collect(); - } - - /// Whether there are any value constructors for this type that are not present in the matrix. - fn any_missing(&self, pcx: &PatCtxt<'_, '_, 'tcx>) -> bool { - self.iter_missing(pcx).next().is_some() - } - - /// Iterate over the constructors for this type that are not present in the matrix. - pub(super) fn iter_missing<'a, 'p>( - &'a self, - pcx: &'a PatCtxt<'a, 'p, 'tcx>, - ) -> impl Iterator<Item = &'a Constructor<'tcx>> + Captures<'p> { - self.all_ctors.iter().filter(move |ctor| !ctor.is_covered_by_any(pcx, &self.matrix_ctors)) - } - - /// Return the set of constructors resulting from splitting the wildcard. As explained at the - /// top of the file, if any constructors are missing we can ignore the present ones. - fn into_ctors(self, pcx: &PatCtxt<'_, '_, 'tcx>) -> SmallVec<[Constructor<'tcx>; 1]> { - if self.any_missing(pcx) { - // Some constructors are missing, thus we can specialize with the special `Missing` - // constructor, which stands for those constructors that are not seen in the matrix, - // and matches the same rows as any of them (namely the wildcard rows). See the top of - // the file for details. - // However, when all constructors are missing we can also specialize with the full - // `Wildcard` constructor. The difference will depend on what we want 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 - // sometimes prefer reporting the list of constructors instead of just `_`. - let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(pcx.ty); - let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing { - if pcx.is_non_exhaustive { - Missing { - nonexhaustive_enum_missing_real_variants: self - .iter_missing(pcx) - .any(|c| !(c.is_non_exhaustive() || c.is_unstable_variant(pcx))), - } - } else { - Missing { nonexhaustive_enum_missing_real_variants: false } - } - } else { - Wildcard - }; - return smallvec![ctor]; - } - - // All the constructors are present in the matrix, so we just go through them all. - self.all_ctors + self.split(pcx, ctors).missing } } @@ -1202,11 +1334,14 @@ impl<'p, 'tcx> Fields<'p, 'tcx> { } _ => bug!("bad slice pattern {:?} {:?}", constructor, pcx), }, - Str(..) - | FloatRange(..) + Bool(..) | IntRange(..) - | NonExhaustive + | F32Range(..) + | F64Range(..) + | Str(..) | Opaque + | NonExhaustive + | Hidden | Missing { .. } | Wildcard => Fields::empty(), Or => { @@ -1227,9 +1362,10 @@ impl<'p, 'tcx> Fields<'p, 'tcx> { /// Values and patterns can be represented as a constructor applied to some fields. This represents /// a pattern in this form. -/// This also keeps track of whether the pattern has been found reachable during analysis. For this -/// reason we should be careful not to clone patterns for which we care about that. Use -/// `clone_and_forget_reachability` if you're sure. +/// 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>, @@ -1252,26 +1388,13 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { DeconstructedPat { ctor, fields, ty, span, reachable: Cell::new(false) } } - /// 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<'_, 'p, 'tcx>, ctor: Constructor<'tcx>) -> Self { - let fields = Fields::wildcards(pcx, &ctor); - DeconstructedPat::new(ctor, fields, pcx.ty, pcx.span) - } - - /// Clone this value. This method emphasizes that cloning loses reachability information and - /// should be done carefully. - pub(super) fn clone_and_forget_reachability(&self) -> Self { - DeconstructedPat::new(self.ctor.clone(), self.fields, self.ty, self.span) - } - 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, .. } => return mkpat(subpattern), + 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; @@ -1343,50 +1466,95 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { } } PatKind::Constant { value } => { - if let Some(int_range) = IntRange::from_constant(cx.tcx, cx.param_env, *value) { - ctor = IntRange(int_range); - fields = Fields::empty(); - } else { - match pat.ty.kind() { - ty::Float(_) => { - ctor = FloatRange(*value, *value, RangeEnd::Included); - 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(); - } + 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 = lo.ty(); - ctor = if let Some(int_range) = IntRange::from_range( - cx.tcx, - lo.eval_bits(cx.tcx, cx.param_env), - hi.eval_bits(cx.tcx, cx.param_env), - ty, - &end, - ) { - IntRange(int_range) - } else { - FloatRange(lo, hi, end) + 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(); } @@ -1412,103 +1580,24 @@ impl<'p, 'tcx> DeconstructedPat<'p, 'tcx> { 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(crate) fn to_pat(&self, cx: &MatchCheckCtxt<'p, 'tcx>) -> Pat<'tcx> { - let is_wildcard = |pat: &Pat<'_>| { - matches!(pat.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild) - }; - let mut subpatterns = self.iter_fields().map(|p| Box::new(p.to_pat(cx))); - let kind = match &self.ctor { - 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 }, - &FloatRange(lo, hi, end) => PatKind::Range(Box::new(PatRange { lo, hi, end })), - IntRange(range) => return range.to_pat(cx.tcx, self.ty), - Wildcard | NonExhaustive => 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`" - ), - Opaque | Or => { - bug!("can't convert to pattern: {:?}", self) - } - }; - - Pat { ty: self.ty, span: DUMMY_SP, kind } - } - 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 @@ -1673,21 +1762,151 @@ impl<'p, 'tcx> fmt::Debug for DeconstructedPat<'p, 'tcx> { } write!(f, "]") } - &FloatRange(lo, hi, end) => { - write!(f, "{lo}")?; - write!(f, "{end}")?; - write!(f, "{hi}") - } - IntRange(range) => write!(f, "{range:?}"), // Best-effort, will render e.g. `false` as `0..=0` - Wildcard | Missing { .. } | NonExhaustive => write!(f, "_ : {:?}", self.ty), + 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(()) } - Str(value) => write!(f, "{value}"), - Opaque => write!(f, "<constant pattern>"), + 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() + } +} |