| //! 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 std::mem; |
| |
| use smallvec::SmallVec; |
| |
| use rustc_apfloat::ieee::{DoubleS, IeeeFloat, SingleS}; |
| use rustc_index::bit_set::GrowableBitSet; |
| |
| use self::Constructor::*; |
| use self::MaybeInfiniteInt::*; |
| use self::SliceKind::*; |
| |
| use crate::index; |
| 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 self.is_singleton() { |
| // Only finite ranges can be singletons. |
| let Finite(lo) = self.lo else { unreachable!() }; |
| write!(f, "{lo}")?; |
| } else { |
| 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`. |
| 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> Clone for Constructor<Cx> { |
| fn clone(&self) -> Self { |
| match self { |
| Constructor::Struct => Constructor::Struct, |
| Constructor::Variant(idx) => Constructor::Variant(idx.clone()), |
| Constructor::Ref => Constructor::Ref, |
| Constructor::Slice(slice) => Constructor::Slice(slice.clone()), |
| Constructor::UnionField => Constructor::UnionField, |
| Constructor::Bool(b) => Constructor::Bool(b.clone()), |
| Constructor::IntRange(range) => Constructor::IntRange(range.clone()), |
| Constructor::F32Range(lo, hi, end) => { |
| Constructor::F32Range(lo.clone(), hi.clone(), end.clone()) |
| } |
| Constructor::F64Range(lo, hi, end) => { |
| Constructor::F64Range(lo.clone(), hi.clone(), end.clone()) |
| } |
| Constructor::Str(value) => Constructor::Str(value.clone()), |
| Constructor::Opaque(inner) => Constructor::Opaque(inner.clone()), |
| Constructor::Or => Constructor::Or, |
| Constructor::Wildcard => Constructor::Wildcard, |
| Constructor::NonExhaustive => Constructor::NonExhaustive, |
| Constructor::Hidden => Constructor::Hidden, |
| Constructor::Missing => Constructor::Missing, |
| } |
| } |
| } |
| |
| impl<Cx: TypeCx> fmt::Debug for Constructor<Cx> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| match self { |
| Constructor::Struct => f.debug_tuple("Struct").finish(), |
| Constructor::Variant(idx) => f.debug_tuple("Variant").field(idx).finish(), |
| Constructor::Ref => f.debug_tuple("Ref").finish(), |
| Constructor::Slice(slice) => f.debug_tuple("Slice").field(slice).finish(), |
| Constructor::UnionField => f.debug_tuple("UnionField").finish(), |
| Constructor::Bool(b) => f.debug_tuple("Bool").field(b).finish(), |
| Constructor::IntRange(range) => f.debug_tuple("IntRange").field(range).finish(), |
| Constructor::F32Range(lo, hi, end) => { |
| f.debug_tuple("F32Range").field(lo).field(hi).field(end).finish() |
| } |
| Constructor::F64Range(lo, hi, end) => { |
| f.debug_tuple("F64Range").field(lo).field(hi).field(end).finish() |
| } |
| Constructor::Str(value) => f.debug_tuple("Str").field(value).finish(), |
| Constructor::Opaque(inner) => f.debug_tuple("Opaque").field(inner).finish(), |
| Constructor::Or => f.debug_tuple("Or").finish(), |
| Constructor::Wildcard => f.debug_tuple("Wildcard").finish(), |
| Constructor::NonExhaustive => f.debug_tuple("NonExhaustive").finish(), |
| Constructor::Hidden => f.debug_tuple("Hidden").finish(), |
| Constructor::Missing => f.debug_tuple("Missing").finish(), |
| } |
| } |
| } |
| |
| impl<Cx: TypeCx> PartialEq for Constructor<Cx> { |
| fn eq(&self, other: &Self) -> bool { |
| (mem::discriminant(self) == mem::discriminant(other)) |
| && match (self, other) { |
| (Constructor::Struct, Constructor::Struct) => true, |
| (Constructor::Variant(self_variant), Constructor::Variant(other_variant)) => { |
| self_variant == other_variant |
| } |
| (Constructor::Ref, Constructor::Ref) => true, |
| (Constructor::Slice(self_slice), Constructor::Slice(other_slice)) => { |
| self_slice == other_slice |
| } |
| (Constructor::UnionField, Constructor::UnionField) => true, |
| (Constructor::Bool(self_b), Constructor::Bool(other_b)) => self_b == other_b, |
| (Constructor::IntRange(self_range), Constructor::IntRange(other_range)) => { |
| self_range == other_range |
| } |
| ( |
| Constructor::F32Range(self_lo, self_hi, self_end), |
| Constructor::F32Range(other_lo, other_hi, other_end), |
| ) => self_lo == other_lo && self_hi == other_hi && self_end == other_end, |
| ( |
| Constructor::F64Range(self_lo, self_hi, self_end), |
| Constructor::F64Range(other_lo, other_hi, other_end), |
| ) => self_lo == other_lo && self_hi == other_hi && self_end == other_end, |
| (Constructor::Str(self_value), Constructor::Str(other_value)) => { |
| self_value == other_value |
| } |
| (Constructor::Opaque(self_inner), Constructor::Opaque(other_inner)) => { |
| self_inner == other_inner |
| } |
| (Constructor::Or, Constructor::Or) => true, |
| (Constructor::Wildcard, Constructor::Wildcard) => true, |
| (Constructor::NonExhaustive, Constructor::NonExhaustive) => true, |
| (Constructor::Hidden, Constructor::Hidden) => true, |
| (Constructor::Missing, Constructor::Missing) => true, |
| _ => unreachable!(), |
| } |
| } |
| } |
| |
| 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, cx: &Cx, ty: &Cx::Ty) -> usize { |
| cx.ctor_arity(self, ty) |
| } |
| |
| /// 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(&self, cx: &Cx, other: &Self) -> bool { |
| match (self, other) { |
| (Wildcard, _) => { |
| cx.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, |
| |
| _ => cx.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: index::IdxContainer<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 struct SplitConstructorSet<Cx: TypeCx> { |
| pub present: SmallVec<[Constructor<Cx>; 1]>, |
| pub missing: Vec<Constructor<Cx>>, |
| pub 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, ctors), ret)] |
| pub fn split<'a>( |
| &self, |
| 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 = index::IdxSet::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); |
| } |
| } |
| |
| SplitConstructorSet { present, missing, missing_empty } |
| } |
| } |
