+/// Note: most tests relevant to this file can be found (at the time of writing)
+/// in src/tests/ui/pattern/usefulness.
+///
/// This file includes the logic for exhaustiveness and usefulness checking for
/// pattern-matching. Specifically, given a list of patterns for a type, we can
/// tell whether:
&self,
cx: &mut MatchCheckCtxt<'a, 'tcx>,
constructor: &Constructor<'tcx>,
- wild_patterns: &[&'q Pat<'tcx>],
+ ctor_wild_subpatterns: &[&'q Pat<'tcx>],
) -> Option<PatStack<'q, 'tcx>>
where
'a: 'q,
'p: 'q,
{
- specialize(cx, self, constructor, wild_patterns)
+ let new_heads = specialize_one_pattern(cx, self.head(), constructor, ctor_wild_subpatterns);
+ new_heads.map(|mut new_head| {
+ new_head.0.extend_from_slice(&self.0[1..]);
+ new_head
+ })
}
}
&self,
cx: &mut MatchCheckCtxt<'a, 'tcx>,
constructor: &Constructor<'tcx>,
- wild_patterns: &[&'q Pat<'tcx>],
+ ctor_wild_subpatterns: &[&'q Pat<'tcx>],
) -> Matrix<'q, 'tcx>
where
'a: 'q,
Matrix(
self.0
.iter()
- .filter_map(|r| r.specialize_constructor(cx, constructor, wild_patterns))
+ .filter_map(|r| r.specialize_constructor(cx, constructor, ctor_wild_subpatterns))
.collect(),
)
}
ConstantValue(&'tcx ty::Const<'tcx>, Span),
/// Ranges of literal values (`2..=5` and `2..5`).
ConstantRange(u128, u128, Ty<'tcx>, RangeEnd, Span),
- /// Array patterns of length n.
- Slice(u64),
+ /// Array patterns of length `n`.
+ FixedLenSlice(u64),
+ /// Slice patterns. Captures any array constructor of `length >= i + j`.
+ VarLenSlice(u64, u64),
+ /// Fake extra constructor for enums that aren't allowed to be matched exhaustively.
+ NonExhaustive,
}
// Ignore spans when comparing, they don't carry semantic information as they are only for lints.
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(Constructor::Single, Constructor::Single) => true,
+ (Constructor::NonExhaustive, Constructor::NonExhaustive) => true,
(Constructor::Variant(a), Constructor::Variant(b)) => a == b,
(Constructor::ConstantValue(a, _), Constructor::ConstantValue(b, _)) => a == b,
(
Constructor::ConstantRange(a_start, a_end, a_ty, a_range_end, _),
Constructor::ConstantRange(b_start, b_end, b_ty, b_range_end, _),
) => a_start == b_start && a_end == b_end && a_ty == b_ty && a_range_end == b_range_end,
- (Constructor::Slice(a), Constructor::Slice(b)) => a == b,
+ (Constructor::FixedLenSlice(a), Constructor::FixedLenSlice(b)) => a == b,
+ (
+ Constructor::VarLenSlice(a_prefix, a_suffix),
+ Constructor::VarLenSlice(b_prefix, b_suffix),
+ ) => a_prefix == b_prefix && a_suffix == b_suffix,
_ => false,
}
}
impl<'tcx> Constructor<'tcx> {
fn is_slice(&self) -> bool {
match self {
- Slice { .. } => true,
+ FixedLenSlice { .. } | VarLenSlice { .. } => true,
_ => false,
}
}
ty::Const::from_bits(tcx, *hi, ty),
)
}
- Constructor::Slice(val) => format!("[{}]", val),
+ Constructor::FixedLenSlice(val) => format!("[{}]", val),
+ Constructor::VarLenSlice(prefix, suffix) => format!("[{}, .., {}]", prefix, suffix),
_ => bug!("bad constructor being displayed: `{:?}", self),
}
}
+ // Returns the set of constructors covered by `self` but not by
+ // anything in `other_ctors`.
+ fn subtract_ctors(
+ &self,
+ tcx: TyCtxt<'tcx>,
+ param_env: ty::ParamEnv<'tcx>,
+ other_ctors: &Vec<Constructor<'tcx>>,
+ ) -> Vec<Constructor<'tcx>> {
+ match *self {
+ // Those constructors can only match themselves.
+ Single | Variant(_) => {
+ if other_ctors.iter().any(|c| c == self) {
+ vec![]
+ } else {
+ vec![self.clone()]
+ }
+ }
+ FixedLenSlice(self_len) => {
+ let overlaps = |c: &Constructor<'_>| match *c {
+ FixedLenSlice(other_len) => other_len == self_len,
+ VarLenSlice(prefix, suffix) => prefix + suffix <= self_len,
+ _ => false,
+ };
+ if other_ctors.iter().any(overlaps) { vec![] } else { vec![self.clone()] }
+ }
+ VarLenSlice(..) => {
+ let mut remaining_ctors = vec![self.clone()];
+
+ // For each used ctor, subtract from the current set of constructors.
+ // Naming: we remove the "neg" constructors from the "pos" ones.
+ // Remember, `VarLenSlice(i, j)` covers the union of `FixedLenSlice` from
+ // `i + j` to infinity.
+ for neg_ctor in other_ctors {
+ remaining_ctors = remaining_ctors
+ .into_iter()
+ .flat_map(|pos_ctor| -> SmallVec<[Constructor<'tcx>; 1]> {
+ // Compute `pos_ctor \ neg_ctor`.
+ match (&pos_ctor, neg_ctor) {
+ (&FixedLenSlice(pos_len), &VarLenSlice(neg_prefix, neg_suffix)) => {
+ let neg_len = neg_prefix + neg_suffix;
+ if neg_len <= pos_len {
+ smallvec![]
+ } else {
+ smallvec![pos_ctor]
+ }
+ }
+ (
+ &VarLenSlice(pos_prefix, pos_suffix),
+ &VarLenSlice(neg_prefix, neg_suffix),
+ ) => {
+ let neg_len = neg_prefix + neg_suffix;
+ let pos_len = pos_prefix + pos_suffix;
+ if neg_len <= pos_len {
+ smallvec![]
+ } else {
+ (pos_len..neg_len).map(FixedLenSlice).collect()
+ }
+ }
+ (&VarLenSlice(pos_prefix, pos_suffix), &FixedLenSlice(neg_len)) => {
+ let pos_len = pos_prefix + pos_suffix;
+ if neg_len < pos_len {
+ smallvec![pos_ctor]
+ } else {
+ (pos_len..neg_len)
+ .map(FixedLenSlice)
+ // We know that `neg_len + 1 >= pos_len >= pos_suffix`.
+ .chain(Some(VarLenSlice(
+ neg_len + 1 - pos_suffix,
+ pos_suffix,
+ )))
+ .collect()
+ }
+ }
+ _ if pos_ctor == *neg_ctor => smallvec![],
+ _ => smallvec![pos_ctor],
+ }
+ })
+ .collect();
+
+ // If the constructors that have been considered so far already cover
+ // the entire range of `self`, no need to look at more constructors.
+ if remaining_ctors.is_empty() {
+ break;
+ }
+ }
+
+ remaining_ctors
+ }
+ ConstantRange(..) | ConstantValue(..) => {
+ let mut remaining_ctors = vec![self.clone()];
+ for other_ctor in other_ctors {
+ if other_ctor == self {
+ // If a constructor appears in a `match` arm, we can
+ // eliminate it straight away.
+ remaining_ctors = vec![]
+ } else if let Some(interval) = IntRange::from_ctor(tcx, param_env, other_ctor) {
+ // Refine the required constructors for the type by subtracting
+ // the range defined by the current constructor pattern.
+ remaining_ctors = interval.subtract_from(tcx, param_env, remaining_ctors);
+ }
+
+ // If the constructor patterns that have been considered so far
+ // already cover the entire range of values, then we know the
+ // constructor is not missing, and we can move on to the next one.
+ if remaining_ctors.is_empty() {
+ break;
+ }
+ }
+
+ // If a constructor has not been matched, then it is missing.
+ // We add `remaining_ctors` instead of `self`, because then we can
+ // provide more detailed error information about precisely which
+ // ranges have been omitted.
+ remaining_ctors
+ }
+ // This constructor is never covered by anything else
+ NonExhaustive => vec![NonExhaustive],
+ }
+ }
+
/// This returns one wildcard pattern for each argument to this constructor.
fn wildcard_subpatterns<'a>(
&self,
cx: &MatchCheckCtxt<'a, 'tcx>,
ty: Ty<'tcx>,
- ) -> impl Iterator<Item = Pat<'tcx>> + DoubleEndedIterator {
- constructor_sub_pattern_tys(cx, self, ty).into_iter().map(|ty| Pat {
- ty,
- span: DUMMY_SP,
- kind: box PatKind::Wild,
- })
+ ) -> Vec<Pat<'tcx>> {
+ debug!("wildcard_subpatterns({:#?}, {:?})", self, ty);
+
+ match self {
+ Single | Variant(_) => match ty.kind {
+ ty::Tuple(ref fs) => {
+ fs.into_iter().map(|t| t.expect_ty()).map(Pat::wildcard_from_ty).collect()
+ }
+ ty::Ref(_, rty, _) => vec![Pat::wildcard_from_ty(rty)],
+ ty::Adt(adt, substs) => {
+ if adt.is_box() {
+ // Use T as the sub pattern type of Box<T>.
+ vec![Pat::wildcard_from_ty(substs.type_at(0))]
+ } else {
+ let variant = &adt.variants[self.variant_index_for_adt(cx, adt)];
+ let is_non_exhaustive =
+ variant.is_field_list_non_exhaustive() && !cx.is_local(ty);
+ variant
+ .fields
+ .iter()
+ .map(|field| {
+ let is_visible = adt.is_enum()
+ || field.vis.is_accessible_from(cx.module, cx.tcx);
+ let is_uninhabited = cx.is_uninhabited(field.ty(cx.tcx, substs));
+ match (is_visible, is_non_exhaustive, is_uninhabited) {
+ // Treat all uninhabited types in non-exhaustive variants as
+ // `TyErr`.
+ (_, true, true) => cx.tcx.types.err,
+ // Treat all non-visible fields as `TyErr`. They can't appear
+ // in any other pattern from this match (because they are
+ // private), so their type does not matter - but we don't want
+ // to know they are uninhabited.
+ (false, ..) => cx.tcx.types.err,
+ (true, ..) => {
+ let ty = field.ty(cx.tcx, substs);
+ match ty.kind {
+ // If the field type returned is an array of an unknown
+ // size return an TyErr.
+ ty::Array(_, len)
+ if len
+ .try_eval_usize(cx.tcx, cx.param_env)
+ .is_none() =>
+ {
+ cx.tcx.types.err
+ }
+ _ => ty,
+ }
+ }
+ }
+ })
+ .map(Pat::wildcard_from_ty)
+ .collect()
+ }
+ }
+ _ => vec![],
+ },
+ FixedLenSlice(_) | VarLenSlice(..) => match ty.kind {
+ ty::Slice(ty) | ty::Array(ty, _) => {
+ let arity = self.arity(cx, ty);
+ (0..arity).map(|_| Pat::wildcard_from_ty(ty)).collect()
+ }
+ _ => bug!("bad slice pattern {:?} {:?}", self, ty),
+ },
+ ConstantValue(..) | ConstantRange(..) | NonExhaustive => vec![],
+ }
}
/// This computes the arity of a constructor. The arity of a constructor
/// A struct pattern's arity is the number of fields it contains, etc.
fn arity<'a>(&self, cx: &MatchCheckCtxt<'a, 'tcx>, ty: Ty<'tcx>) -> u64 {
debug!("Constructor::arity({:#?}, {:?})", self, ty);
- match ty.kind {
- ty::Tuple(ref fs) => fs.len() as u64,
- ty::Slice(..) | ty::Array(..) => match *self {
- Slice(length) => length,
- ConstantValue(..) => 0,
- _ => bug!("bad slice pattern {:?} {:?}", self, ty),
+ match self {
+ Single | Variant(_) => match ty.kind {
+ ty::Tuple(ref fs) => fs.len() as u64,
+ ty::Slice(..) | ty::Array(..) => bug!("bad slice pattern {:?} {:?}", self, ty),
+ ty::Ref(..) => 1,
+ ty::Adt(adt, _) => {
+ adt.variants[self.variant_index_for_adt(cx, adt)].fields.len() as u64
+ }
+ _ => 0,
},
- ty::Ref(..) => 1,
- ty::Adt(adt, _) => {
- adt.variants[self.variant_index_for_adt(cx, adt)].fields.len() as u64
- }
- _ => 0,
+ FixedLenSlice(length) => *length,
+ VarLenSlice(prefix, suffix) => prefix + suffix,
+ ConstantValue(..) | ConstantRange(..) | NonExhaustive => 0,
}
}
/// must have as many elements as this constructor's arity.
///
/// Examples:
- /// self: Single
- /// ty: tuple of 3 elements
- /// pats: [10, 20, _] => (10, 20, _)
+ /// `self`: `Constructor::Single`
+ /// `ty`: `(u32, u32, u32)`
+ /// `pats`: `[10, 20, _]`
+ /// returns `(10, 20, _)`
///
- /// self: Option::Some
- /// ty: Option<bool>
- /// pats: [false] => Some(false)
+ /// `self`: `Constructor::Variant(Option::Some)`
+ /// `ty`: `Option<bool>`
+ /// `pats`: `[false]`
+ /// returns `Some(false)`
fn apply<'a>(
&self,
cx: &MatchCheckCtxt<'a, 'tcx>,
ty: Ty<'tcx>,
pats: impl IntoIterator<Item = Pat<'tcx>>,
) -> Pat<'tcx> {
- let mut pats = pats.into_iter();
- let pat = match ty.kind {
- ty::Adt(..) | ty::Tuple(..) => {
- let pats = pats
- .enumerate()
- .map(|(i, p)| FieldPat { field: Field::new(i), pattern: p })
- .collect();
-
- if let ty::Adt(adt, substs) = ty.kind {
- if adt.is_enum() {
- PatKind::Variant {
- adt_def: adt,
- substs,
- variant_index: self.variant_index_for_adt(cx, adt),
- subpatterns: pats,
+ let mut subpatterns = pats.into_iter();
+
+ let pat = match self {
+ Single | Variant(_) => match ty.kind {
+ ty::Adt(..) | ty::Tuple(..) => {
+ let subpatterns = subpatterns
+ .enumerate()
+ .map(|(i, p)| FieldPat { field: Field::new(i), pattern: p })
+ .collect();
+
+ if let ty::Adt(adt, substs) = ty.kind {
+ if adt.is_enum() {
+ PatKind::Variant {
+ adt_def: adt,
+ substs,
+ variant_index: self.variant_index_for_adt(cx, adt),
+ subpatterns,
+ }
+ } else {
+ PatKind::Leaf { subpatterns }
}
} else {
- PatKind::Leaf { subpatterns: pats }
+ PatKind::Leaf { subpatterns }
}
- } else {
- PatKind::Leaf { subpatterns: pats }
}
- }
-
- ty::Ref(..) => PatKind::Deref { subpattern: pats.nth(0).unwrap() },
-
- ty::Slice(_) | ty::Array(..) => {
- PatKind::Slice { prefix: pats.collect(), slice: None, suffix: vec![] }
- }
-
- _ => match *self {
- ConstantValue(value, _) => PatKind::Constant { value },
- ConstantRange(lo, hi, ty, end, _) => PatKind::Range(PatRange {
- lo: ty::Const::from_bits(cx.tcx, lo, ty::ParamEnv::empty().and(ty)),
- hi: ty::Const::from_bits(cx.tcx, hi, ty::ParamEnv::empty().and(ty)),
- end,
- }),
+ ty::Ref(..) => PatKind::Deref { subpattern: subpatterns.nth(0).unwrap() },
+ ty::Slice(_) | ty::Array(..) => bug!("bad slice pattern {:?} {:?}", self, ty),
_ => PatKind::Wild,
},
+ FixedLenSlice(_) => {
+ PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] }
+ }
+ &VarLenSlice(prefix_len, _) => {
+ let prefix = subpatterns.by_ref().take(prefix_len as usize).collect();
+ let suffix = subpatterns.collect();
+ let wild = Pat::wildcard_from_ty(ty);
+ PatKind::Slice { prefix, slice: Some(wild), suffix }
+ }
+ &ConstantValue(value, _) => PatKind::Constant { value },
+ &ConstantRange(lo, hi, ty, end, _) => PatKind::Range(PatRange {
+ lo: ty::Const::from_bits(cx.tcx, lo, ty::ParamEnv::empty().and(ty)),
+ hi: ty::Const::from_bits(cx.tcx, hi, ty::ParamEnv::empty().and(ty)),
+ end,
+ }),
+ NonExhaustive => PatKind::Wild,
};
Pat { ty, span: DUMMY_SP, kind: Box::new(pat) }
/// Like `apply`, but where all the subpatterns are wildcards `_`.
fn apply_wildcards<'a>(&self, cx: &MatchCheckCtxt<'a, 'tcx>, ty: Ty<'tcx>) -> Pat<'tcx> {
- let pats = self.wildcard_subpatterns(cx, ty).rev();
- self.apply(cx, ty, pats)
+ let subpatterns = self.wildcard_subpatterns(cx, ty).into_iter().rev();
+ self.apply(cx, ty, subpatterns)
}
}
}
impl<'tcx> Usefulness<'tcx> {
+ fn new_useful(preference: WitnessPreference) -> Self {
+ match preference {
+ ConstructWitness => UsefulWithWitness(vec![Witness(vec![])]),
+ LeaveOutWitness => Useful,
+ }
+ }
+
fn is_useful(&self) -> bool {
match *self {
NotUseful => false,
_ => true,
}
}
+
+ fn apply_constructor(
+ self,
+ cx: &MatchCheckCtxt<'_, 'tcx>,
+ ctor: &Constructor<'tcx>,
+ ty: Ty<'tcx>,
+ ) -> Self {
+ match self {
+ UsefulWithWitness(witnesses) => UsefulWithWitness(
+ witnesses
+ .into_iter()
+ .map(|witness| witness.apply_constructor(cx, &ctor, ty))
+ .collect(),
+ ),
+ x => x,
+ }
+ }
+
+ fn apply_wildcard(self, ty: Ty<'tcx>) -> Self {
+ match self {
+ UsefulWithWitness(witnesses) => {
+ let wild = Pat::wildcard_from_ty(ty);
+ UsefulWithWitness(
+ witnesses
+ .into_iter()
+ .map(|mut witness| {
+ witness.0.push(wild.clone());
+ witness
+ })
+ .collect(),
+ )
+ }
+ x => x,
+ }
+ }
+
+ fn apply_missing_ctors(
+ self,
+ cx: &MatchCheckCtxt<'_, 'tcx>,
+ ty: Ty<'tcx>,
+ missing_ctors: &MissingConstructors<'tcx>,
+ ) -> Self {
+ match self {
+ UsefulWithWitness(witnesses) => {
+ let new_patterns: Vec<_> =
+ missing_ctors.iter().map(|ctor| ctor.apply_wildcards(cx, ty)).collect();
+ // Add the new patterns to each witness
+ UsefulWithWitness(
+ witnesses
+ .into_iter()
+ .flat_map(|witness| {
+ new_patterns.iter().map(move |pat| {
+ let mut witness = witness.clone();
+ witness.0.push(pat.clone());
+ witness
+ })
+ })
+ .collect(),
+ )
+ }
+ x => x,
+ }
+ }
}
#[derive(Copy, Clone, Debug)]
#[derive(Copy, Clone, Debug)]
struct PatCtxt<'tcx> {
ty: Ty<'tcx>,
- max_slice_length: u64,
span: Span,
}
.collect(),
ty::Array(ref sub_ty, len) if len.try_eval_usize(cx.tcx, cx.param_env).is_some() => {
let len = len.eval_usize(cx.tcx, cx.param_env);
- if len != 0 && cx.is_uninhabited(sub_ty) { vec![] } else { vec![Slice(len)] }
+ if len != 0 && cx.is_uninhabited(sub_ty) { vec![] } else { vec![FixedLenSlice(len)] }
}
// Treat arrays of a constant but unknown length like slices.
ty::Array(ref sub_ty, _) | ty::Slice(ref sub_ty) => {
if cx.is_uninhabited(sub_ty) {
- vec![Slice(0)]
+ vec![FixedLenSlice(0)]
} else {
- (0..pcx.max_slice_length + 1).map(|length| Slice(length)).collect()
+ vec![VarLenSlice(0, 0)]
}
}
ty::Adt(def, substs) if def.is_enum() => def
}
}
};
- ctors
-}
-fn max_slice_length<'p, 'a, 'tcx, I>(cx: &mut MatchCheckCtxt<'a, 'tcx>, patterns: I) -> u64
-where
- I: Iterator<Item = &'p Pat<'tcx>>,
- 'tcx: 'p,
-{
- // The exhaustiveness-checking paper does not include any details on
- // checking variable-length slice patterns. However, they are matched
- // by an infinite collection of fixed-length array patterns.
- //
- // Checking the infinite set directly would take an infinite amount
- // of time. However, it turns out that for each finite set of
- // patterns `P`, all sufficiently large array lengths are equivalent:
- //
- // Each slice `s` with a "sufficiently-large" length `l ≥ L` that applies
- // to exactly the subset `Pₜ` of `P` can be transformed to a slice
- // `sₘ` for each sufficiently-large length `m` that applies to exactly
- // the same subset of `P`.
- //
- // Because of that, each witness for reachability-checking from one
- // of the sufficiently-large lengths can be transformed to an
- // equally-valid witness from any other length, so we only have
- // to check slice lengths from the "minimal sufficiently-large length"
- // and below.
- //
- // Note that the fact that there is a *single* `sₘ` for each `m`
- // not depending on the specific pattern in `P` is important: if
- // you look at the pair of patterns
- // `[true, ..]`
- // `[.., false]`
- // Then any slice of length ≥1 that matches one of these two
- // patterns can be trivially turned to a slice of any
- // other length ≥1 that matches them and vice-versa - for
- // but the slice from length 2 `[false, true]` that matches neither
- // of these patterns can't be turned to a slice from length 1 that
- // matches neither of these patterns, so we have to consider
- // slices from length 2 there.
- //
- // Now, to see that that length exists and find it, observe that slice
- // patterns are either "fixed-length" patterns (`[_, _, _]`) or
- // "variable-length" patterns (`[_, .., _]`).
- //
- // For fixed-length patterns, all slices with lengths *longer* than
- // the pattern's length have the same outcome (of not matching), so
- // as long as `L` is greater than the pattern's length we can pick
- // any `sₘ` from that length and get the same result.
- //
- // For variable-length patterns, the situation is more complicated,
- // because as seen above the precise value of `sₘ` matters.
- //
- // However, 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(FIXED_LEN+1 ∪ {max(PREFIX_LEN) + max(SUFFIX_LEN)})`
- //
- // for example, with the above pair of patterns, all elements
- // but the first and last can be added/removed, so any
- // witness of length ≥2 (say, `[false, false, true]`) can be
- // turned to a witness from any other length ≥2.
-
- let mut max_prefix_len = 0;
- let mut max_suffix_len = 0;
- let mut max_fixed_len = 0;
-
- for row in patterns {
- match *row.kind {
- PatKind::Constant { value } => {
- // extract the length of an array/slice from a constant
- match (value.val, &value.ty.kind) {
- (_, ty::Array(_, n)) => {
- max_fixed_len = cmp::max(max_fixed_len, n.eval_usize(cx.tcx, cx.param_env))
- }
- (ConstValue::Slice { start, end, .. }, ty::Slice(_)) => {
- max_fixed_len = cmp::max(max_fixed_len, (end - start) as u64)
- }
- _ => {}
- }
- }
- PatKind::Slice { ref prefix, slice: None, ref suffix } => {
- let fixed_len = prefix.len() as u64 + suffix.len() as u64;
- max_fixed_len = cmp::max(max_fixed_len, fixed_len);
- }
- PatKind::Slice { ref prefix, slice: Some(_), ref suffix } => {
- max_prefix_len = cmp::max(max_prefix_len, prefix.len() as u64);
- max_suffix_len = cmp::max(max_suffix_len, suffix.len() as u64);
- }
- _ => {}
- }
+ // FIXME: currently the only way I know of something can
+ // be a privately-empty enum is when the exhaustive_patterns
+ // feature flag is not present, so this is only
+ // needed for that case.
+ let is_privately_empty = ctors.is_empty() && !cx.is_uninhabited(pcx.ty);
+ let is_declared_nonexhaustive = cx.is_non_exhaustive_enum(pcx.ty) && !cx.is_local(pcx.ty);
+ let is_non_exhaustive = is_privately_empty
+ || is_declared_nonexhaustive
+ || (pcx.ty.is_ptr_sized_integral() && !cx.tcx.features().precise_pointer_size_matching);
+ if is_non_exhaustive {
+ // If our scrutinee is *privately* an empty enum, we must treat it as though it had an
+ // "unknown" constructor (in that case, all other patterns obviously can't be variants) to
+ // avoid exposing its emptyness. See the `match_privately_empty` test for details.
+ //
+ // If the enum is declared as `#[non_exhaustive]`, we treat it as if it had an additionnal
+ // "unknown" constructor. However there is no point in enumerating all possible variants,
+ // because the user can't actually match against them themselves. So we return only the
+ // fictitious constructor.
+ // E.g., in an example like:
+ // ```
+ // let err: io::ErrorKind = ...;
+ // match err {
+ // io::ErrorKind::NotFound => {},
+ // }
+ // ```
+ // we don't want to show every possible IO error, but instead have only `_` as the witness.
+ return vec![NonExhaustive];
}
- cmp::max(max_fixed_len + 1, max_prefix_len + max_suffix_len)
+ ctors
}
/// An inclusive interval, used for precise integer exhaustiveness checking.
}
}
-type MissingConstructors<'a, 'tcx, F> =
- std::iter::FlatMap<std::slice::Iter<'a, Constructor<'tcx>>, Vec<Constructor<'tcx>>, F>;
-// Compute a set of constructors equivalent to `all_ctors \ used_ctors`. This
-// returns an iterator, so that we only construct the whole set if needed.
-fn compute_missing_ctors<'a, 'tcx>(
+// A struct to compute a set of constructors equivalent to `all_ctors \ used_ctors`.
+struct MissingConstructors<'tcx> {
tcx: TyCtxt<'tcx>,
param_env: ty::ParamEnv<'tcx>,
- all_ctors: &'a Vec<Constructor<'tcx>>,
- used_ctors: &'a Vec<Constructor<'tcx>>,
-) -> MissingConstructors<'a, 'tcx, impl FnMut(&'a Constructor<'tcx>) -> Vec<Constructor<'tcx>>> {
- all_ctors.iter().flat_map(move |req_ctor| {
- let mut refined_ctors = vec![req_ctor.clone()];
- for used_ctor in used_ctors {
- if used_ctor == req_ctor {
- // If a constructor appears in a `match` arm, we can
- // eliminate it straight away.
- refined_ctors = vec![]
- } else if let Some(interval) = IntRange::from_ctor(tcx, param_env, used_ctor) {
- // Refine the required constructors for the type by subtracting
- // the range defined by the current constructor pattern.
- refined_ctors = interval.subtract_from(tcx, param_env, refined_ctors);
- }
+ all_ctors: Vec<Constructor<'tcx>>,
+ used_ctors: Vec<Constructor<'tcx>>,
+}
- // If the constructor patterns that have been considered so far
- // already cover the entire range of values, then we know the
- // constructor is not missing, and we can move on to the next one.
- if refined_ctors.is_empty() {
- break;
- }
- }
+impl<'tcx> MissingConstructors<'tcx> {
+ fn new(
+ tcx: TyCtxt<'tcx>,
+ param_env: ty::ParamEnv<'tcx>,
+ all_ctors: Vec<Constructor<'tcx>>,
+ used_ctors: Vec<Constructor<'tcx>>,
+ ) -> Self {
+ MissingConstructors { tcx, param_env, all_ctors, used_ctors }
+ }
- // If a constructor has not been matched, then it is missing.
- // We add `refined_ctors` instead of `req_ctor`, because then we can
- // provide more detailed error information about precisely which
- // ranges have been omitted.
- refined_ctors
- })
+ fn into_inner(self) -> (Vec<Constructor<'tcx>>, Vec<Constructor<'tcx>>) {
+ (self.all_ctors, self.used_ctors)
+ }
+
+ fn is_empty(&self) -> bool {
+ self.iter().next().is_none()
+ }
+ /// Whether this contains all the constructors for the given type or only a
+ /// subset.
+ fn all_ctors_are_missing(&self) -> bool {
+ self.used_ctors.is_empty()
+ }
+
+ /// Iterate over all_ctors \ used_ctors
+ fn iter<'a>(&'a self) -> impl Iterator<Item = Constructor<'tcx>> + Captures<'a> {
+ self.all_ctors.iter().flat_map(move |req_ctor| {
+ req_ctor.subtract_ctors(self.tcx, self.param_env, &self.used_ctors)
+ })
+ }
+}
+
+impl<'tcx> fmt::Debug for MissingConstructors<'tcx> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let ctors: Vec<_> = self.iter().collect();
+ write!(f, "{:?}", ctors)
+ }
}
/// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html.
cx: &mut MatchCheckCtxt<'a, 'tcx>,
matrix: &Matrix<'p, 'tcx>,
v: &PatStack<'_, 'tcx>,
- witness: WitnessPreference,
+ witness_preference: WitnessPreference,
hir_id: HirId,
) -> Usefulness<'tcx> {
let &Matrix(ref rows) = matrix;
// the type of the tuple we're checking is inhabited or not.
if v.is_empty() {
return if rows.is_empty() {
- match witness {
- ConstructWitness => UsefulWithWitness(vec![Witness(vec![])]),
- LeaveOutWitness => Useful,
- }
+ Usefulness::new_useful(witness_preference)
} else {
NotUseful
};
// introducing uninhabited patterns for inaccessible fields. We
// need to figure out how to model that.
ty,
- max_slice_length: max_slice_length(cx, matrix.heads().chain(Some(v.head()))),
span,
};
debug!("is_useful_expand_first_col: pcx={:#?}, expanding {:#?}", pcx, v.head());
- if let Some(constructors) = pat_constructors(cx, v.head(), pcx) {
- debug!("is_useful - expanding constructors: {:#?}", constructors);
+ if let Some(constructor) = pat_constructor(cx, v.head(), pcx) {
+ debug!("is_useful - expanding constructor: {:#?}", constructor);
split_grouped_constructors(
cx.tcx,
cx.param_env,
- constructors,
+ pcx,
+ vec![constructor],
matrix,
- pcx.ty,
pcx.span,
Some(hir_id),
)
.into_iter()
- .map(|c| is_useful_specialized(cx, matrix, v, c, pcx.ty, witness, hir_id))
+ .map(|c| is_useful_specialized(cx, matrix, v, c, pcx.ty, witness_preference, hir_id))
.find(|result| result.is_useful())
.unwrap_or(NotUseful)
} else {
debug!("is_useful - expanding wildcard");
let used_ctors: Vec<Constructor<'_>> =
- matrix.heads().flat_map(|p| pat_constructors(cx, p, pcx).unwrap_or(vec![])).collect();
+ matrix.heads().filter_map(|p| pat_constructor(cx, p, pcx)).collect();
debug!("used_ctors = {:#?}", used_ctors);
// `all_ctors` are all the constructors for the given type, which
// should all be represented (or caught with the wild pattern `_`).
// Therefore, if there is some pattern that is unmatched by `matrix`,
// it will still be unmatched if the first constructor is replaced by
// any of the constructors in `missing_ctors`
- //
- // However, if our scrutinee is *privately* an empty enum, we
- // must treat it as though it had an "unknown" constructor (in
- // that case, all other patterns obviously can't be variants)
- // to avoid exposing its emptyness. See the `match_privately_empty`
- // test for details.
- //
- // FIXME: currently the only way I know of something can
- // be a privately-empty enum is when the exhaustive_patterns
- // feature flag is not present, so this is only
- // needed for that case.
-
- // Missing constructors are those that are not matched by any
- // non-wildcard patterns in the current column. To determine if
- // the set is empty, we can check that `.peek().is_none()`, so
- // we only fully construct them on-demand, because they're rarely used and can be big.
- let mut missing_ctors =
- compute_missing_ctors(cx.tcx, cx.param_env, &all_ctors, &used_ctors).peekable();
-
- let is_privately_empty = all_ctors.is_empty() && !cx.is_uninhabited(pcx.ty);
- let is_declared_nonexhaustive = cx.is_non_exhaustive_enum(pcx.ty) && !cx.is_local(pcx.ty);
- debug!(
- "missing_ctors.empty()={:#?} is_privately_empty={:#?} is_declared_nonexhaustive={:#?}",
- missing_ctors.peek().is_none(),
- is_privately_empty,
- is_declared_nonexhaustive
- );
- // For privately empty and non-exhaustive enums, we work as if there were an "extra"
- // `_` constructor for the type, so we can never match over all constructors.
- let is_non_exhaustive = is_privately_empty
- || is_declared_nonexhaustive
- || (pcx.ty.is_ptr_sized_integral() && !cx.tcx.features().precise_pointer_size_matching);
-
- if missing_ctors.peek().is_none() && !is_non_exhaustive {
- drop(missing_ctors); // It was borrowing `all_ctors`, which we want to move.
- split_grouped_constructors(
- cx.tcx,
- cx.param_env,
- all_ctors,
- matrix,
- pcx.ty,
- DUMMY_SP,
- None,
- )
- .into_iter()
- .map(|c| is_useful_specialized(cx, matrix, v, c, pcx.ty, witness, hir_id))
- .find(|result| result.is_useful())
- .unwrap_or(NotUseful)
+ // Missing constructors are those that are not matched by any non-wildcard patterns in the
+ // current column. We only fully construct them on-demand, because they're rarely used and
+ // can be big.
+ let missing_ctors = MissingConstructors::new(cx.tcx, cx.param_env, all_ctors, used_ctors);
+
+ debug!("missing_ctors.empty()={:#?}", missing_ctors.is_empty(),);
+
+ if missing_ctors.is_empty() {
+ let (all_ctors, _) = missing_ctors.into_inner();
+ split_grouped_constructors(cx.tcx, cx.param_env, pcx, all_ctors, matrix, DUMMY_SP, None)
+ .into_iter()
+ .map(|c| {
+ is_useful_specialized(cx, matrix, v, c, pcx.ty, witness_preference, hir_id)
+ })
+ .find(|result| result.is_useful())
+ .unwrap_or(NotUseful)
} else {
let matrix = matrix.specialize_wildcard();
let v = v.to_tail();
- match is_useful(cx, &matrix, &v, witness, hir_id) {
- UsefulWithWitness(pats) => {
- let cx = &*cx;
- // In this case, there's at least one "free"
- // constructor that is only matched against by
- // wildcard patterns.
- //
- // There are 2 ways we can report a witness here.
- // Commonly, we can report all the "free"
- // constructors as witnesses, e.g., if we have:
- //
- // ```
- // enum Direction { N, S, E, W }
- // let Direction::N = ...;
- // ```
- //
- // we can report 3 witnesses: `S`, `E`, and `W`.
- //
- // However, there are 2 cases where we don't want
- // to do this and instead report a single `_` witness:
- //
- // 1) If the user is matching against a non-exhaustive
- // enum, there is no point in enumerating all possible
- // variants, because the user can't actually match
- // against them himself, e.g., in an example like:
- // ```
- // let err: io::ErrorKind = ...;
- // match err {
- // io::ErrorKind::NotFound => {},
- // }
- // ```
- // we don't want to show every possible IO error,
- // but instead have `_` as the witness (this is
- // actually *required* if the user specified *all*
- // IO errors, but is probably what we want in every
- // case).
- //
- // 2) 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)`. In this case,
- // `used_ctors` is empty.
- let new_patterns = if is_non_exhaustive || used_ctors.is_empty() {
- // All constructors are unused. Add a wild pattern
- // rather than each individual constructor.
- vec![Pat { ty: pcx.ty, span: DUMMY_SP, kind: box PatKind::Wild }]
- } else {
- // Construct for each missing constructor a "wild" version of this
- // constructor, that matches everything that can be built with
- // it. For example, if `ctor` is a `Constructor::Variant` for
- // `Option::Some`, we get the pattern `Some(_)`.
- missing_ctors.map(|ctor| ctor.apply_wildcards(cx, pcx.ty)).collect()
- };
- // Add the new patterns to each witness
- let new_witnesses = pats
- .into_iter()
- .flat_map(|witness| {
- new_patterns.iter().map(move |pat| {
- let mut witness = witness.clone();
- witness.0.push(pat.clone());
- witness
- })
- })
- .collect();
- UsefulWithWitness(new_witnesses)
- }
- result => result,
+ let usefulness = is_useful(cx, &matrix, &v, witness_preference, hir_id);
+
+ // In this case, there's at least one "free"
+ // constructor that is only matched against by
+ // wildcard patterns.
+ //
+ // There are 2 ways we can report a witness here.
+ // Commonly, we can report all the "free"
+ // constructors as witnesses, e.g., if we have:
+ //
+ // ```
+ // enum Direction { N, S, E, W }
+ // let Direction::N = ...;
+ // ```
+ //
+ // we can report 3 witnesses: `S`, `E`, and `W`.
+ //
+ // However, there is a case where we don't want
+ // to do this and instead report a single `_` witness:
+ // 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)`. In this case,
+ // `used_ctors` is empty.
+ if missing_ctors.all_ctors_are_missing() {
+ // All constructors are unused. Add a wild pattern
+ // rather than each individual constructor.
+ usefulness.apply_wildcard(pcx.ty)
+ } else {
+ // Construct for each missing constructor a "wild" version of this
+ // constructor, that matches everything that can be built with
+ // it. For example, if `ctor` is a `Constructor::Variant` for
+ // `Option::Some`, we get the pattern `Some(_)`.
+ usefulness.apply_missing_ctors(cx, pcx.ty, &missing_ctors)
}
}
}
v: &PatStack<'_, 'tcx>,
ctor: Constructor<'tcx>,
lty: Ty<'tcx>,
- witness: WitnessPreference,
+ witness_preference: WitnessPreference,
hir_id: HirId,
) -> Usefulness<'tcx> {
debug!("is_useful_specialized({:#?}, {:#?}, {:?})", v, ctor, lty);
- let wild_patterns_owned: Vec<_> = ctor.wildcard_subpatterns(cx, lty).collect();
- let wild_patterns: Vec<_> = wild_patterns_owned.iter().collect();
- let matrix = matrix.specialize_constructor(cx, &ctor, &wild_patterns);
- match v.specialize_constructor(cx, &ctor, &wild_patterns) {
- Some(v) => match is_useful(cx, &matrix, &v, witness, hir_id) {
- UsefulWithWitness(witnesses) => UsefulWithWitness(
- witnesses
- .into_iter()
- .map(|witness| witness.apply_constructor(cx, &ctor, lty))
- .collect(),
- ),
- result => result,
- },
- None => NotUseful,
- }
+ let ctor_wild_subpatterns_owned: Vec<_> = ctor.wildcard_subpatterns(cx, lty);
+ let ctor_wild_subpatterns: Vec<_> = ctor_wild_subpatterns_owned.iter().collect();
+ let matrix = matrix.specialize_constructor(cx, &ctor, &ctor_wild_subpatterns);
+ v.specialize_constructor(cx, &ctor, &ctor_wild_subpatterns)
+ .map(|v| is_useful(cx, &matrix, &v, witness_preference, hir_id))
+ .map(|u| u.apply_constructor(cx, &ctor, lty))
+ .unwrap_or(NotUseful)
}
-/// Determines the constructors that the given pattern can be specialized to.
-///
-/// In most cases, there's only one constructor that a specific pattern
-/// represents, such as a specific enum variant or a specific literal value.
-/// Slice patterns, however, can match slices of different lengths. For instance,
-/// `[a, b, tail @ ..]` can match a slice of length 2, 3, 4 and so on.
-///
+/// Determines the constructor that the given pattern can be specialized to.
/// Returns `None` in case of a catch-all, which can't be specialized.
-fn pat_constructors<'tcx>(
+fn pat_constructor<'tcx>(
cx: &mut MatchCheckCtxt<'_, 'tcx>,
pat: &Pat<'tcx>,
pcx: PatCtxt<'tcx>,
-) -> Option<Vec<Constructor<'tcx>>> {
+) -> Option<Constructor<'tcx>> {
match *pat.kind {
- PatKind::AscribeUserType { ref subpattern, .. } => pat_constructors(cx, subpattern, pcx),
+ PatKind::AscribeUserType { ref subpattern, .. } => pat_constructor(cx, subpattern, pcx),
PatKind::Binding { .. } | PatKind::Wild => None,
- PatKind::Leaf { .. } | PatKind::Deref { .. } => Some(vec![Single]),
+ PatKind::Leaf { .. } | PatKind::Deref { .. } => Some(Single),
PatKind::Variant { adt_def, variant_index, .. } => {
- Some(vec![Variant(adt_def.variants[variant_index].def_id)])
+ Some(Variant(adt_def.variants[variant_index].def_id))
}
- PatKind::Constant { value } => Some(vec![ConstantValue(value, pat.span)]),
- PatKind::Range(PatRange { lo, hi, end }) => Some(vec![ConstantRange(
+ PatKind::Constant { value } => Some(ConstantValue(value, pat.span)),
+ PatKind::Range(PatRange { lo, hi, end }) => Some(ConstantRange(
lo.eval_bits(cx.tcx, cx.param_env, lo.ty),
hi.eval_bits(cx.tcx, cx.param_env, hi.ty),
lo.ty,
end,
pat.span,
- )]),
+ )),
PatKind::Array { .. } => match pcx.ty.kind {
- ty::Array(_, length) => Some(vec![Slice(length.eval_usize(cx.tcx, cx.param_env))]),
+ ty::Array(_, length) => Some(FixedLenSlice(length.eval_usize(cx.tcx, cx.param_env))),
_ => span_bug!(pat.span, "bad ty {:?} for array pattern", pcx.ty),
},
PatKind::Slice { ref prefix, ref slice, ref suffix } => {
- let pat_len = prefix.len() as u64 + suffix.len() as u64;
+ let prefix = prefix.len() as u64;
+ let suffix = suffix.len() as u64;
if slice.is_some() {
- Some((pat_len..pcx.max_slice_length + 1).map(Slice).collect())
+ Some(VarLenSlice(prefix, suffix))
} else {
- Some(vec![Slice(pat_len)])
+ Some(FixedLenSlice(prefix + suffix))
}
}
PatKind::Or { .. } => {
}
}
-/// This computes the types of the sub patterns that a constructor should be
-/// expanded to.
-///
-/// For instance, a tuple pattern (43u32, 'a') has sub pattern types [u32, char].
-fn constructor_sub_pattern_tys<'a, 'tcx>(
- cx: &MatchCheckCtxt<'a, 'tcx>,
- ctor: &Constructor<'tcx>,
- ty: Ty<'tcx>,
-) -> Vec<Ty<'tcx>> {
- debug!("constructor_sub_pattern_tys({:#?}, {:?})", ctor, ty);
- match ty.kind {
- ty::Tuple(ref fs) => fs.into_iter().map(|t| t.expect_ty()).collect(),
- ty::Slice(ty) | ty::Array(ty, _) => match *ctor {
- Slice(length) => (0..length).map(|_| ty).collect(),
- ConstantValue(..) => vec![],
- _ => bug!("bad slice pattern {:?} {:?}", ctor, ty),
- },
- ty::Ref(_, rty, _) => vec![rty],
- ty::Adt(adt, substs) => {
- if adt.is_box() {
- // Use T as the sub pattern type of Box<T>.
- vec![substs.type_at(0)]
- } else {
- let variant = &adt.variants[ctor.variant_index_for_adt(cx, adt)];
- let is_non_exhaustive = variant.is_field_list_non_exhaustive() && !cx.is_local(ty);
- variant
- .fields
- .iter()
- .map(|field| {
- let is_visible =
- adt.is_enum() || field.vis.is_accessible_from(cx.module, cx.tcx);
- let is_uninhabited = cx.is_uninhabited(field.ty(cx.tcx, substs));
- match (is_visible, is_non_exhaustive, is_uninhabited) {
- // Treat all uninhabited types in non-exhaustive variants as `TyErr`.
- (_, true, true) => cx.tcx.types.err,
- // Treat all non-visible fields as `TyErr`. They can't appear in any
- // other pattern from this match (because they are private), so their
- // type does not matter - but we don't want to know they are
- // uninhabited.
- (false, ..) => cx.tcx.types.err,
- (true, ..) => {
- let ty = field.ty(cx.tcx, substs);
- match ty.kind {
- // If the field type returned is an array of an unknown size
- // return an TyErr.
- ty::Array(_, len)
- if len.try_eval_usize(cx.tcx, cx.param_env).is_none() =>
- {
- cx.tcx.types.err
- }
- _ => ty,
- }
- }
- }
- })
- .collect()
- }
- }
- _ => vec![],
- }
-}
-
// checks whether a constant is equal to a user-written slice pattern. Only supports byte slices,
// meaning all other types will compare unequal and thus equal patterns often do not cause the
// second pattern to lint about unreachable match arms.
///
/// `hir_id` is `None` when we're evaluating the wildcard pattern, do not lint for overlapping in
/// ranges that case.
+///
+/// This also splits variable-length slices into fixed-length slices.
fn split_grouped_constructors<'p, 'tcx>(
tcx: TyCtxt<'tcx>,
param_env: ty::ParamEnv<'tcx>,
+ pcx: PatCtxt<'tcx>,
ctors: Vec<Constructor<'tcx>>,
matrix: &Matrix<'p, 'tcx>,
- ty: Ty<'tcx>,
span: Span,
hir_id: Option<HirId>,
) -> Vec<Constructor<'tcx>> {
+ let ty = pcx.ty;
let mut split_ctors = Vec::with_capacity(ctors.len());
for ctor in ctors.into_iter() {
match ctor {
- // For now, only ranges may denote groups of "subconstructors", so we only need to
- // special-case constant ranges.
ConstantRange(..) if should_treat_range_exhaustively(tcx, &ctor) => {
// We only care about finding all the subranges within the range of the constructor
// range. Anything else is irrelevant, because it is guaranteed to result in
lint_overlapping_patterns(tcx, hir_id, ctor_range, ty, overlaps);
- // We're going to iterate through every pair of borders, making sure that each
- // represents an interval of nonnegative length, and convert each such interval
- // into a constructor.
+ // We're going to iterate through every adjacent pair of borders, making sure that
+ // each represents an interval of nonnegative length, and convert each such
+ // interval into a constructor.
for IntRange { range, .. } in
borders.windows(2).filter_map(|window| match (window[0], window[1]) {
(Border::JustBefore(n), Border::JustBefore(m)) => {
split_ctors.push(IntRange::range_to_ctor(tcx, ty, range, span));
}
}
+ VarLenSlice(self_prefix, self_suffix) => {
+ // The exhaustiveness-checking paper does not include any details on
+ // checking variable-length slice patterns. However, they are matched
+ // by an infinite collection of fixed-length array patterns.
+ //
+ // Checking the infinite set directly would take an infinite amount
+ // of time. However, it turns out that for each finite set of
+ // patterns `P`, all sufficiently large array lengths are equivalent:
+ //
+ // Each slice `s` with a "sufficiently-large" length `l ≥ L` that applies
+ // to exactly the subset `Pₜ` of `P` can be transformed to a slice
+ // `sₘ` for each sufficiently-large length `m` that applies to exactly
+ // the same subset of `P`.
+ //
+ // Because of that, each witness for reachability-checking from one
+ // of the sufficiently-large lengths can be transformed to an
+ // equally-valid witness from any other length, so we only have
+ // to check slice lengths from the "minimal sufficiently-large length"
+ // and below.
+ //
+ // Note that the fact that there is a *single* `sₘ` for each `m`
+ // not depending on the specific pattern in `P` is important: if
+ // you look at the pair of patterns
+ // `[true, ..]`
+ // `[.., false]`
+ // Then any slice of length ≥1 that matches one of these two
+ // patterns can be trivially turned to a slice of any
+ // other length ≥1 that matches them and vice-versa - for
+ // but the slice from length 2 `[false, true]` that matches neither
+ // of these patterns can't be turned to a slice from length 1 that
+ // matches neither of these patterns, so we have to consider
+ // slices from length 2 there.
+ //
+ // Now, to see that that length exists and find it, observe that slice
+ // patterns are either "fixed-length" patterns (`[_, _, _]`) or
+ // "variable-length" patterns (`[_, .., _]`).
+ //
+ // For fixed-length patterns, all slices with lengths *longer* than
+ // the pattern's length have the same outcome (of not matching), so
+ // as long as `L` is greater than the pattern's length we can pick
+ // any `sₘ` from that length and get the same result.
+ //
+ // For variable-length patterns, the situation is more complicated,
+ // because as seen above the precise value of `sₘ` matters.
+ //
+ // However, 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))`
+ //
+ // for example, with the above pair of patterns, all elements
+ // but the first and last can be added/removed, so any
+ // witness of length ≥2 (say, `[false, false, true]`) can be
+ // turned to a witness from any other length ≥2.
+
+ let mut max_prefix_len = self_prefix;
+ let mut max_suffix_len = self_suffix;
+ let mut max_fixed_len = 0;
+
+ for row in matrix.heads() {
+ match *row.kind {
+ PatKind::Constant { value } => {
+ // extract the length of an array/slice from a constant
+ match (value.val, &value.ty.kind) {
+ (_, ty::Array(_, n)) => {
+ max_fixed_len =
+ cmp::max(max_fixed_len, n.eval_usize(tcx, param_env))
+ }
+ (ConstValue::Slice { start, end, .. }, ty::Slice(_)) => {
+ max_fixed_len = cmp::max(max_fixed_len, (end - start) as u64)
+ }
+ _ => {}
+ }
+ }
+ PatKind::Slice { ref prefix, slice: None, ref suffix } => {
+ let fixed_len = prefix.len() as u64 + suffix.len() as u64;
+ max_fixed_len = cmp::max(max_fixed_len, fixed_len);
+ }
+ PatKind::Slice { ref prefix, slice: Some(_), ref suffix } => {
+ max_prefix_len = cmp::max(max_prefix_len, prefix.len() as u64);
+ max_suffix_len = cmp::max(max_suffix_len, suffix.len() as u64);
+ }
+ _ => {}
+ }
+ }
+
+ // For diagnostics, we keep the prefix and suffix lengths separate, so in the case
+ // where `max_fixed_len + 1` is the largest, we adapt `max_prefix_len` accordingly,
+ // so that `L = max_prefix_len + max_suffix_len`.
+ 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 also guaranteed to be larger than its previous
+ // value.
+ max_prefix_len = max_fixed_len + 1 - max_suffix_len;
+ }
+
+ // `ctor` originally covered the range `(self_prefix + self_suffix..infinity)`. We
+ // now split it into two: lengths smaller than `max_prefix_len + max_suffix_len`
+ // are treated independently as fixed-lengths slices, and lengths above are
+ // captured by a final VarLenSlice constructor.
+ split_ctors.extend(
+ (self_prefix + self_suffix..max_prefix_len + max_suffix_len).map(FixedLenSlice),
+ );
+ split_ctors.push(VarLenSlice(max_prefix_len, max_suffix_len));
+ }
// Any other constructor can be used unchanged.
_ => split_ctors.push(ctor),
}
fn patterns_for_variant<'p, 'a: 'p, 'tcx>(
cx: &mut MatchCheckCtxt<'a, 'tcx>,
subpatterns: &'p [FieldPat<'tcx>],
- wild_patterns: &[&'p Pat<'tcx>],
+ ctor_wild_subpatterns: &[&'p Pat<'tcx>],
is_non_exhaustive: bool,
) -> PatStack<'p, 'tcx> {
- let mut result = SmallVec::from_slice(wild_patterns);
+ let mut result = SmallVec::from_slice(ctor_wild_subpatterns);
for subpat in subpatterns {
if !is_non_exhaustive || !cx.is_uninhabited(subpat.pattern.ty) {
}
}
- debug!("patterns_for_variant({:#?}, {:#?}) = {:#?}", subpatterns, wild_patterns, result);
+ debug!(
+ "patterns_for_variant({:#?}, {:#?}) = {:#?}",
+ subpatterns, ctor_wild_subpatterns, result
+ );
PatStack::from_vec(result)
}
-/// This is the main specialization step. It expands the first pattern in the given row
+/// This is the main specialization step. It expands the pattern
/// into `arity` patterns based on the constructor. For most patterns, the step is trivial,
/// for instance tuple patterns are flattened and box patterns expand into their inner pattern.
+/// Returns `None` if the pattern does not have the given constructor.
///
/// OTOH, slice patterns with a subslice pattern (tail @ ..) can be expanded into multiple
/// different patterns.
/// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
/// fields filled with wild patterns.
-fn specialize<'p, 'a: 'p, 'q: 'p, 'tcx>(
+fn specialize_one_pattern<'p, 'a: 'p, 'q: 'p, 'tcx>(
cx: &mut MatchCheckCtxt<'a, 'tcx>,
- r: &PatStack<'q, 'tcx>,
+ mut pat: &'q Pat<'tcx>,
constructor: &Constructor<'tcx>,
- wild_patterns: &[&'p Pat<'tcx>],
+ ctor_wild_subpatterns: &[&'p Pat<'tcx>],
) -> Option<PatStack<'p, 'tcx>> {
- let pat = r.head();
+ while let PatKind::AscribeUserType { ref subpattern, .. } = *pat.kind {
+ pat = subpattern;
+ }
- let new_head = match *pat.kind {
- PatKind::AscribeUserType { ref subpattern, .. } => {
- specialize(cx, &PatStack::from_pattern(subpattern), constructor, wild_patterns)
- }
+ if let NonExhaustive = constructor {
+ // Only a wildcard pattern can match the special extra constructor
+ return if pat.is_wildcard() { Some(PatStack::default()) } else { None };
+ }
+
+ let result = match *pat.kind {
+ PatKind::AscribeUserType { .. } => bug!(), // Handled above
- PatKind::Binding { .. } | PatKind::Wild => Some(PatStack::from_slice(wild_patterns)),
+ PatKind::Binding { .. } | PatKind::Wild => {
+ Some(PatStack::from_slice(ctor_wild_subpatterns))
+ }
PatKind::Variant { adt_def, variant_index, ref subpatterns, .. } => {
let ref variant = adt_def.variants[variant_index];
let is_non_exhaustive = variant.is_field_list_non_exhaustive() && !cx.is_local(pat.ty);
Some(Variant(variant.def_id))
.filter(|variant_constructor| variant_constructor == constructor)
- .map(|_| patterns_for_variant(cx, subpatterns, wild_patterns, is_non_exhaustive))
+ .map(|_| {
+ patterns_for_variant(cx, subpatterns, ctor_wild_subpatterns, is_non_exhaustive)
+ })
}
PatKind::Leaf { ref subpatterns } => {
- Some(patterns_for_variant(cx, subpatterns, wild_patterns, false))
+ Some(patterns_for_variant(cx, subpatterns, ctor_wild_subpatterns, false))
}
PatKind::Deref { ref subpattern } => Some(PatStack::from_pattern(subpattern)),
constructor,
),
};
- if wild_patterns.len() as u64 == n {
+ if ctor_wild_subpatterns.len() as u64 == n {
// convert a constant slice/array pattern to a list of patterns.
let layout = cx.tcx.layout_of(cx.param_env.and(ty)).ok()?;
let ptr = Pointer::new(AllocId(0), offset);
PatKind::Array { ref prefix, ref slice, ref suffix }
| PatKind::Slice { ref prefix, ref slice, ref suffix } => match *constructor {
- Slice(..) => {
+ FixedLenSlice(..) | VarLenSlice(..) => {
let pat_len = prefix.len() + suffix.len();
- if let Some(slice_count) = wild_patterns.len().checked_sub(pat_len) {
+ if let Some(slice_count) = ctor_wild_subpatterns.len().checked_sub(pat_len) {
if slice_count == 0 || slice.is_some() {
Some(
prefix
.iter()
.chain(
- wild_patterns
+ ctor_wild_subpatterns
.iter()
.map(|p| *p)
.skip(prefix.len())
bug!("support for or-patterns has not been fully implemented yet.");
}
};
- debug!("specialize({:#?}, {:#?}) = {:#?}", r.head(), wild_patterns, new_head);
+ debug!("specialize({:#?}, {:#?}) = {:#?}", pat, ctor_wild_subpatterns, result);
- new_head.map(|head| {
- let mut head = head.0;
- head.extend_from_slice(&r.0[1..]);
- PatStack::from_vec(head)
- })
+ result
}
projects / rust.git / blobdiff