diff options
Diffstat (limited to 'compiler/rustc_pattern_analysis/src/constructor.rs')
| -rw-r--r-- | compiler/rustc_pattern_analysis/src/constructor.rs | 1021 |
1 files changed, 1021 insertions, 0 deletions
diff --git a/compiler/rustc_pattern_analysis/src/constructor.rs b/compiler/rustc_pattern_analysis/src/constructor.rs new file mode 100644 index 000000000..af0a7497a --- /dev/null +++ b/compiler/rustc_pattern_analysis/src/constructor.rs @@ -0,0 +1,1021 @@ +//! As explained in [`crate::usefulness`], values and patterns are made from constructors applied to +//! fields. This file defines a `Constructor` enum and various operations to manipulate them. +//! +//! There are two important bits of core logic in this file: constructor inclusion and constructor +//! splitting. Constructor inclusion, i.e. whether a constructor is included in/covered by another, +//! is straightforward and defined in [`Constructor::is_covered_by`]. +//! +//! Constructor splitting is mentioned in [`crate::usefulness`] but not detailed. We describe it +//! precisely here. +//! +//! +//! +//! # Constructor grouping and splitting +//! +//! As explained in the corresponding section in [`crate::usefulness`], to make usefulness tractable +//! we need to group together constructors that have the same effect when they are used to +//! specialize the matrix. +//! +//! Example: +//! ```compile_fail,E0004 +//! match (0, false) { +//! (0 ..=100, true) => {} +//! (50..=150, false) => {} +//! (0 ..=200, _) => {} +//! } +//! ``` +//! +//! In this example we can restrict specialization to 5 cases: `0..50`, `50..=100`, `101..=150`, +//! `151..=200` and `200..`. +//! +//! In [`crate::usefulness`], we had said that `specialize` only takes value-only constructors. We +//! now relax this restriction: we allow `specialize` to take constructors like `0..50` as long as +//! we're careful to only do that with constructors that make sense. For example, `specialize(0..50, +//! (0..=100, true))` is sensible, but `specialize(50..=200, (0..=100, true))` is not. +//! +//! Constructor splitting looks at the constructors in the first column of the matrix and constructs +//! such a sensible set of constructors. Formally, we want to find a smallest disjoint set of +//! constructors: +//! - Whose union covers the whole type, and +//! - That have no non-trivial intersection with any of the constructors in the column (i.e. they're +//! each either disjoint with or covered by any given column constructor). +//! +//! We compute this in two steps: first [`TypeCx::ctors_for_ty`] determines the +//! set of all possible constructors for the type. Then [`ConstructorSet::split`] looks at the +//! column of constructors and splits the set into groups accordingly. The precise invariants of +//! [`ConstructorSet::split`] is described in [`SplitConstructorSet`]. +//! +//! Constructor splitting has two interesting special cases: integer range splitting (see +//! [`IntRange::split`]) and slice splitting (see [`Slice::split`]). +//! +//! +//! +//! # The `Missing` constructor +//! +//! We detail a special case of constructor splitting that is a bit subtle. Take the following: +//! +//! ``` +//! enum Direction { North, South, East, West } +//! # let wind = (Direction::North, 0u8); +//! match wind { +//! (Direction::North, 50..) => {} +//! (_, _) => {} +//! } +//! ``` +//! +//! Here we expect constructor splitting to output two cases: `North`, and "everything else". This +//! "everything else" is represented by [`Constructor::Missing`]. Unlike other constructors, it's a +//! bit contextual: to know the exact list of constructors it represents we have to look at the +//! column. In practice however we don't need to, because by construction it only matches rows that +//! have wildcards. This is how this constructor is special: the only constructor that covers it is +//! `Wildcard`. +//! +//! The only place where we care about which constructors `Missing` represents is in diagnostics +//! (see `crate::usefulness::WitnessMatrix::apply_constructor`). +//! +//! We choose whether to specialize with `Missing` in +//! `crate::usefulness::compute_exhaustiveness_and_usefulness`. +//! +//! +//! +//! ## Empty types, empty constructors, and the `exhaustive_patterns` feature +//! +//! An empty type is a type that has no valid value, like `!`, `enum Void {}`, or `Result<!, !>`. +//! They require careful handling. +//! +//! First, for soundness reasons related to the possible existence of invalid values, by default we +//! don't treat empty types as empty. We force them to be matched with wildcards. Except if the +//! `exhaustive_patterns` feature is turned on, in which case we do treat them as empty. And also +//! except if the type has no constructors (like `enum Void {}` but not like `Result<!, !>`), we +//! specifically allow `match void {}` to be exhaustive. There are additionally considerations of +//! place validity that are handled in `crate::usefulness`. Yes this is a bit tricky. +//! +//! The second thing is that regardless of the above, it is always allowed to use all the +//! constructors of a type. For example, all the following is ok: +//! +//! ```rust,ignore(example) +//! # #![feature(never_type)] +//! # #![feature(exhaustive_patterns)] +//! fn foo(x: Option<!>) { +//! match x { +//! None => {} +//! Some(_) => {} +//! } +//! } +//! fn bar(x: &[!]) -> u32 { +//! match x { +//! [] => 1, +//! [_] => 2, +//! [_, _] => 3, +//! } +//! } +//! ``` +//! +//! Moreover, take the following: +//! +//! ```rust +//! # #![feature(never_type)] +//! # #![feature(exhaustive_patterns)] +//! # let x = None::<!>; +//! match x { +//! None => {} +//! } +//! ``` +//! +//! On a normal type, we would identify `Some` as missing and tell the user. If `x: Option<!>` +//! however (and `exhaustive_patterns` is on), it's ok to omit `Some`. When listing the constructors +//! of a type, we must therefore track which can be omitted. +//! +//! Let's call "empty" a constructor that matches no valid value for the type, like `Some` for the +//! type `Option<!>`. What this all means is that `ConstructorSet` must know which constructors are +//! empty. The difference between empty and nonempty constructors is that empty constructors need +//! not be present for the match to be exhaustive. +//! +//! A final remark: empty constructors of arity 0 break specialization, we must avoid them. The +//! reason is that if we specialize by them, nothing remains to witness the emptiness; the rest of +//! the algorithm can't distinguish them from a nonempty constructor. The only known case where this +//! could happen is the `[..]` pattern on `[!; N]` with `N > 0` so we must take care to not emit it. +//! +//! This is all handled by [`TypeCx::ctors_for_ty`] and +//! [`ConstructorSet::split`]. The invariants of [`SplitConstructorSet`] are also of interest. +//! +//! +//! +//! ## Opaque patterns +//! +//! Some patterns, such as constants that are not allowed to be matched structurally, cannot be +//! inspected, which we handle with `Constructor::Opaque`. Since we know nothing of these patterns, +//! we assume they never cover each other. In order to respect the invariants of +//! [`SplitConstructorSet`], we give each `Opaque` constructor a unique id so we can recognize it. + +use std::cmp::{self, max, min, Ordering}; +use std::fmt; +use std::iter::once; + +use smallvec::SmallVec; + +use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS}; +use rustc_index::bit_set::{BitSet, GrowableBitSet}; +use rustc_index::IndexVec; + +use self::Constructor::*; +use self::MaybeInfiniteInt::*; +use self::SliceKind::*; + +use crate::usefulness::PlaceCtxt; +use crate::TypeCx; + +/// Whether we have seen a constructor in the column or not. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +enum Presence { + Unseen, + Seen, +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum RangeEnd { + Included, + Excluded, +} + +impl fmt::Display for RangeEnd { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str(match self { + RangeEnd::Included => "..=", + RangeEnd::Excluded => "..", + }) + } +} + +/// 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 enum MaybeInfiniteInt { + NegInfinity, + /// Encoded value. DO NOT CONSTRUCT BY HAND; use `new_finite`. + #[non_exhaustive] + Finite(u128), + /// The integer after `u128::MAX`. We need it to represent `x..=u128::MAX` as an exclusive range. + JustAfterMax, + PosInfinity, +} + +impl MaybeInfiniteInt { + pub fn new_finite_uint(bits: u128) -> Self { + Finite(bits) + } + pub fn new_finite_int(bits: u128, size: u64) -> Self { + // Perform a shift if the underlying types are signed, which makes the interval arithmetic + // type-independent. + let bias = 1u128 << (size - 1); + Finite(bits ^ bias) + } + + pub fn as_finite_uint(self) -> Option<u128> { + match self { + Finite(bits) => Some(bits), + _ => None, + } + } + pub fn as_finite_int(self, size: u64) -> Option<u128> { + // We decode the shift. + match self { + Finite(bits) => { + let bias = 1u128 << (size - 1); + Some(bits ^ bias) + } + _ => None, + } + } + + /// Note: this will not turn a finite value into an infinite one or vice-versa. + pub fn minus_one(self) -> Self { + match self { + Finite(n) => match n.checked_sub(1) { + Some(m) => Finite(m), + None => panic!("Called `MaybeInfiniteInt::minus_one` on 0"), + }, + JustAfterMax => Finite(u128::MAX), + x => x, + } + } + /// Note: this will not turn a finite value into an infinite one or vice-versa. + pub fn plus_one(self) -> Self { + match self { + Finite(n) => match n.checked_add(1) { + Some(m) => Finite(m), + None => JustAfterMax, + }, + JustAfterMax => panic!("Called `MaybeInfiniteInt::plus_one` on u128::MAX+1"), + 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 struct IntRange { + pub lo: MaybeInfiniteInt, // Must not be `PosInfinity`. + pub hi: MaybeInfiniteInt, // Must not be `NegInfinity`. +} + +impl IntRange { + /// Best effort; will not know that e.g. `255u8..` is a singleton. + pub 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] + pub fn from_singleton(x: MaybeInfiniteInt) -> IntRange { + IntRange { lo: x, hi: x.plus_one() } + } + + #[inline] + pub 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. + panic!("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. This was decided in <https://github.com/rust-lang/rfcs/pull/2591>. + /// + /// 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) + }) + } +} + +/// 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)] +pub 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 struct Slice { + /// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`. + pub(crate) array_len: Option<usize>, + /// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`. + pub(crate) kind: SliceKind, +} + +impl Slice { + pub fn new(array_len: Option<usize>, kind: SliceKind) -> Self { + let kind = match (array_len, kind) { + // If the middle `..` has length 0, we effectively have a fixed-length pattern. + (Some(len), VarLen(prefix, suffix)) if prefix + suffix == len => FixedLen(len), + (Some(len), VarLen(prefix, suffix)) if prefix + suffix > len => panic!( + "Slice pattern of length {} longer than its array length {len}", + prefix + suffix + ), + _ => kind, + }; + Slice { array_len, kind } + } + + pub(crate) 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 = GrowableBitSet::new_empty(); + match &mut max_slice { + VarLen(max_prefix_len, max_suffix_len) => { + // A length larger than any fixed-length slice encountered. + // We start at 1 in case the subtype is empty because in that case the zero-length + // slice must be treated separately from the rest. + let mut fixed_len_upper_bound = 1; + // We grow `max_slice` to be larger than all slices encountered, as described above. + // `L` is `max_slice.arity()`. For diagnostics, we keep the prefix and suffix + // lengths separate. + for slice in column_slices { + match slice.kind { + FixedLen(len) => { + fixed_len_upper_bound = cmp::max(fixed_len_upper_bound, len + 1); + 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); + } + } + } + // If `fixed_len_upper_bound >= L`, we set `L` to `fixed_len_upper_bound`. + if let Some(delta) = + fixed_len_upper_bound.checked_sub(*max_prefix_len + *max_suffix_len) + { + *max_prefix_len += delta + } + + // 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 globally unique id to distinguish `Opaque` patterns. +#[derive(Clone, Debug, PartialEq, Eq)] +pub struct OpaqueId(u32); + +impl OpaqueId { + pub fn new() -> Self { + use std::sync::atomic::{AtomicU32, Ordering}; + static OPAQUE_ID: AtomicU32 = AtomicU32::new(0); + OpaqueId(OPAQUE_ID.fetch_add(1, Ordering::SeqCst)) + } +} + +/// 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 enum Constructor<Cx: TypeCx> { + /// Tuples and structs. + Struct, + /// Enum variants. + Variant(Cx::VariantIdx), + /// References + Ref, + /// Array and slice patterns. + Slice(Slice), + /// Union field accesses. + UnionField, + /// 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(Cx::StrLit), + /// 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. + /// Carries an id that must be unique within a match. We need this to ensure the invariants of + /// [`SplitConstructorSet`]. + Opaque(OpaqueId), + /// 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 at the + /// top of the file. + Missing, +} + +impl<Cx: TypeCx> Constructor<Cx> { + pub(crate) fn is_non_exhaustive(&self) -> bool { + matches!(self, NonExhaustive) + } + + pub(crate) fn as_variant(&self) -> Option<Cx::VariantIdx> { + match self { + Variant(i) => Some(*i), + _ => None, + } + } + fn as_bool(&self) -> Option<bool> { + match self { + Bool(b) => Some(*b), + _ => None, + } + } + pub(crate) 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, + } + } + + /// The number of fields for this constructor. This must be kept in sync with + /// `Fields::wildcards`. + pub(crate) fn arity(&self, pcx: &PlaceCtxt<'_, '_, Cx>) -> usize { + pcx.ctor_arity(self) + } + + /// 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(crate) fn is_covered_by<'p>(&self, pcx: &PlaceCtxt<'_, 'p, Cx>, other: &Self) -> bool { + match (self, other) { + (Wildcard, _) => pcx + .mcx + .tycx + .bug(format_args!("Constructor splitting should not have returned `Wildcard`")), + // Wildcards cover anything + (_, Wildcard) => true, + // Only a wildcard pattern can match these special constructors. + (Missing { .. } | NonExhaustive | Hidden, _) => false, + + (Struct, Struct) => true, + (Ref, Ref) => true, + (UnionField, UnionField) => 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), + + // Opaque constructors don't interact with anything unless they come from the + // syntactically identical pattern. + (Opaque(self_id), Opaque(other_id)) => self_id == other_id, + (Opaque(..), _) | (_, Opaque(..)) => false, + + _ => pcx.mcx.tycx.bug(format_args!( + "trying to compare incompatible constructors {self:?} and {other:?}" + )), + } + } +} + +#[derive(Debug, Clone, Copy)] +pub enum VariantVisibility { + /// Variant that doesn't fit the other cases, i.e. most variants. + Visible, + /// Variant behind an unstable gate or with the `#[doc(hidden)]` attribute. It will not be + /// mentioned in diagnostics unless the user mentioned it first. + Hidden, + /// Variant that matches no value. E.g. `Some::<Option<!>>` if the `exhaustive_patterns` feature + /// is enabled. Like `Hidden`, it will not be mentioned in diagnostics unless the user mentioned + /// it first. + Empty, +} + +/// Describes the set of all constructors for a type. For details, in particular about the emptiness +/// of constructors, see the top of the file. +/// +/// In terms of division of responsibility, [`ConstructorSet::split`] handles all of the +/// `exhaustive_patterns` feature. +#[derive(Debug)] +pub enum ConstructorSet<Cx: TypeCx> { + /// The type is a tuple or struct. `empty` tracks whether the type is empty. + Struct { empty: bool }, + /// This type has the following list of constructors. If `variants` is empty and + /// `non_exhaustive` is false, don't use this; use `NoConstructors` instead. + Variants { variants: IndexVec<Cx::VariantIdx, VariantVisibility>, non_exhaustive: bool }, + /// The type is `&T`. + Ref, + /// The type is a union. + Union, + /// 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. `array_len` is the compile-time length of the array, if + /// known. If `subtype_is_empty`, all constructors are empty except possibly the zero-length + /// slice `[]`. + Slice { array_len: Option<usize>, subtype_is_empty: bool }, + /// The constructors cannot be listed, and the type cannot be matched exhaustively. E.g. `str`, + /// floats. + Unlistable, + /// The type has no constructors (not even empty ones). This is `!` and empty enums. + NoConstructors, +} + +/// 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, if we discard wildcards from the column, this respects the following constraints: +/// 1. the union of `present`, `missing` and `missing_empty` covers all the constructors of the type +/// 2. each constructor in `present` is covered by something in the column +/// 3. no constructor in `missing` or `missing_empty` is covered by anything in the column +/// 4. each constructor in the column is equal to the union of one or more constructors in `present` +/// 5. `missing` does not contain empty constructors (see discussion about emptiness at the top of +/// the file); +/// 6. `missing_empty` contains only empty constructors +/// 7. constructors in `present`, `missing` and `missing_empty` are split for the column; in other +/// words, they are either fully included in or fully disjoint from each constructor in the +/// column. In yet other words, there are no non-trivial intersections like between `0..10` and +/// `5..15`. +/// +/// We must be particularly careful with weird constructors like `Opaque`: they're not formally part +/// of the `ConstructorSet` for the type, yet if we forgot to include them in `present` we would be +/// ignoring any row with `Opaque`s in the algorithm. Hence the importance of point 4. +#[derive(Debug)] +pub(crate) struct SplitConstructorSet<Cx: TypeCx> { + pub(crate) present: SmallVec<[Constructor<Cx>; 1]>, + pub(crate) missing: Vec<Constructor<Cx>>, + pub(crate) missing_empty: Vec<Constructor<Cx>>, +} + +impl<Cx: TypeCx> ConstructorSet<Cx> { + /// This analyzes a column of 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. This can get subtle; see [`SplitConstructorSet`] for details of this operation + /// and its invariants. + #[instrument(level = "debug", skip(self, pcx, ctors), ret)] + pub(crate) fn split<'a>( + &self, + pcx: &PlaceCtxt<'_, '_, Cx>, + ctors: impl Iterator<Item = &'a Constructor<Cx>> + Clone, + ) -> SplitConstructorSet<Cx> + where + Cx: 'a, + { + let mut present: SmallVec<[_; 1]> = SmallVec::new(); + // Empty constructors found missing. + let mut missing_empty = Vec::new(); + // Nonempty constructors found missing. + let mut missing = Vec::new(); + // Constructors in `ctors`, except wildcards and opaques. + let mut seen = Vec::new(); + for ctor in ctors.cloned() { + match ctor { + Opaque(..) => present.push(ctor), + Wildcard => {} // discard wildcards + _ => seen.push(ctor), + } + } + + match self { + ConstructorSet::Struct { empty } => { + if !seen.is_empty() { + present.push(Struct); + } else if *empty { + missing_empty.push(Struct); + } else { + missing.push(Struct); + } + } + ConstructorSet::Ref => { + if !seen.is_empty() { + present.push(Ref); + } else { + missing.push(Ref); + } + } + ConstructorSet::Union => { + if !seen.is_empty() { + present.push(UnionField); + } else { + missing.push(UnionField); + } + } + ConstructorSet::Variants { variants, non_exhaustive } => { + let mut seen_set: BitSet<_> = BitSet::new_empty(variants.len()); + for idx in seen.iter().map(|c| c.as_variant().unwrap()) { + seen_set.insert(idx); + } + let mut skipped_a_hidden_variant = false; + + for (idx, visibility) in variants.iter_enumerated() { + let ctor = Variant(idx); + if seen_set.contains(idx) { + present.push(ctor); + } else { + // We only put visible variants directly into `missing`. + match visibility { + VariantVisibility::Visible => missing.push(ctor), + VariantVisibility::Hidden => skipped_a_hidden_variant = true, + VariantVisibility::Empty => missing_empty.push(ctor), + } + } + } + + 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.iter().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.iter().map(|ctor| *ctor.as_int_range().unwrap()).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, subtype_is_empty } => { + let seen_slices = seen.iter().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::Seen => present.push(ctor), + Presence::Unseen => { + if *subtype_is_empty && splitted_slice.arity() != 0 { + // We have subpatterns of an empty type, so the constructor is + // empty. + missing_empty.push(ctor); + } else { + missing.push(ctor); + } + } + } + } + } + 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); + missing.push(NonExhaustive); + } + ConstructorSet::NoConstructors => { + // In a `MaybeInvalid` place even an empty pattern may be reachable. We therefore + // add a dummy empty constructor here, which will be ignored if the place is + // `ValidOnly`. + missing_empty.push(NonExhaustive); + } + } + + // We have now grouped all the constructors into 3 buckets: present, missing, missing_empty. + // In the absence of the `exhaustive_patterns` feature however, we don't count nested empty + // types as empty. Only non-nested `!` or `enum Foo {}` are considered empty. + if !pcx.mcx.tycx.is_exhaustive_patterns_feature_on() + && !(pcx.is_scrutinee && matches!(self, Self::NoConstructors)) + { + // Treat all missing constructors as nonempty. + // This clears `missing_empty`. + missing.append(&mut missing_empty); + } + + SplitConstructorSet { present, missing, missing_empty } + } +} |