diff options
| -rw-r--r-- | src/librustc_mir/hair/pattern/_match.rs | 301 |
1 files changed, 160 insertions, 141 deletions
diff --git a/src/librustc_mir/hair/pattern/_match.rs b/src/librustc_mir/hair/pattern/_match.rs index 2ccddabfb2f..51ee1f29bf8 100644 --- a/src/librustc_mir/hair/pattern/_match.rs +++ b/src/librustc_mir/hair/pattern/_match.rs @@ -583,21 +583,110 @@ impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> { } } -#[derive(Copy, Clone, Debug, PartialEq)] +#[derive(Copy, Clone, Debug, PartialEq, Eq)] enum SliceKind { - /// Array patterns of length `n`. + /// Patterns of length `n` (`[x, y]`). FixedLen(u64), - /// Slice patterns. Captures any array constructor of `length >= i + j`. + /// 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(u64, u64), } -impl SliceKind { - fn arity(self) -> u64 { +/// A constructor for array and slice patterns. +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +struct Slice { + /// `None` if the matched value is a slice, `Some(n)` if it is an array of size `n`. + array_len: Option<u64>, + /// The kind of pattern it is: fixed-length `[x, y]` or variable length `[x, .., y]`. + kind: SliceKind, +} + +impl Slice { + /// Returns what patterns this constructor covers: either fixed-length patterns or + /// variable-length patterns. + fn pattern_kind(self) -> SliceKind { + match self { + Slice { array_len: Some(len), kind: VarLen(prefix, suffix) } + if prefix + suffix == len => + { + FixedLen(len) + } + _ => self.kind, + } + } + + /// Returns what values this constructor covers: either values of only one given length, or + /// values of length above a given length. + /// This is different from `pattern_kind()` because in some cases the pattern only takes into + /// account a subset of the entries of the array, but still only captures values of a given + /// length. + fn value_kind(self) -> SliceKind { match self { + Slice { array_len: Some(len), kind: VarLen(_, _) } => FixedLen(len), + _ => self.kind, + } + } + + fn arity(self) -> u64 { + match self.pattern_kind() { FixedLen(length) => length, VarLen(prefix, suffix) => prefix + suffix, } } + + /// Whether this pattern includes patterns of length `other_len`. + fn covers_length(self, other_len: u64) -> bool { + match self.value_kind() { + FixedLen(len) => len == other_len, + VarLen(prefix, suffix) => prefix + suffix <= other_len, + } + } + + /// Returns a collection of slices that spans the values covered by `self`, subtracted by the + /// values covered by `other`: i.e., `self \ other` (in set notation). + fn subtract(self, other: Self) -> SmallVec<[Self; 1]> { + // Remember, `VarLen(i, j)` covers the union of `FixedLen` from `i + j` to infinity. + // Naming: we remove the "neg" constructors from the "pos" ones. + match self.value_kind() { + FixedLen(pos_len) => { + if other.covers_length(pos_len) { + smallvec![] + } else { + smallvec![self] + } + } + VarLen(pos_prefix, pos_suffix) => { + let pos_len = pos_prefix + pos_suffix; + match other.value_kind() { + FixedLen(neg_len) => { + if neg_len < pos_len { + smallvec![self] + } else { + (pos_len..neg_len) + .map(FixedLen) + // We know that `neg_len + 1 >= pos_len >= pos_suffix`. + .chain(Some(VarLen(neg_len + 1 - pos_suffix, pos_suffix))) + .map(|kind| Slice { array_len: None, kind }) + .collect() + } + } + VarLen(neg_prefix, neg_suffix) => { + let neg_len = neg_prefix + neg_suffix; + if neg_len <= pos_len { + smallvec![] + } else { + (pos_len..neg_len) + .map(FixedLen) + .map(|kind| Slice { array_len: None, kind }) + .collect() + } + } + } + } + } + } } #[derive(Clone, Debug, PartialEq)] @@ -614,11 +703,7 @@ enum Constructor<'tcx> { /// Ranges of floating-point literal values (`2.0..=5.2`). FloatRange(&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>, RangeEnd), /// Array and slice patterns. - Slice { - // The length of the type of the pattern, if fixed. - type_len: Option<u64>, - kind: SliceKind, - }, + Slice(Slice), /// Fake extra constructor for enums that aren't allowed to be matched exhaustively. NonExhaustive, } @@ -626,7 +711,7 @@ enum Constructor<'tcx> { impl<'tcx> Constructor<'tcx> { fn is_slice(&self) -> bool { match self { - Slice { .. } => true, + Slice(_) => true, _ => false, } } @@ -655,104 +740,41 @@ impl<'tcx> Constructor<'tcx> { Single | Variant(_) | ConstantValue(..) | FloatRange(..) => { if other_ctors.iter().any(|c| c == self) { vec![] } else { vec![self.clone()] } } - &Slice { type_len: Some(self_len), .. } | &Slice { kind: FixedLen(self_len), .. } => { - let overlaps = |c: &Constructor<'_>| match *c { - Slice { type_len: Some(len), .. } | Slice { kind: FixedLen(len), .. } => { - len == self_len - } - Slice { type_len: None, kind: VarLen(prefix, suffix) } => { - prefix + suffix <= self_len + &Slice(slice) => match slice.value_kind() { + FixedLen(self_len) => { + let overlaps = |c: &Constructor<'_>| match *c { + Slice(other_slice) => other_slice.covers_length(self_len), + _ => false, + }; + if other_ctors.iter().any(overlaps) { vec![] } else { vec![Slice(slice)] } + } + VarLen(..) => { + let mut remaining_slices = vec![slice]; + + // For each used slice, subtract from the current set of slices. + // Naming: we remove the "neg" constructors from the "pos" ones. + for neg_ctor in other_ctors { + let neg_slice = match neg_ctor { + Slice(slice) => *slice, + // FIXME(#65413): If `neg_ctor` is not a slice, we assume it doesn't + // cover any value here. + _ => continue, + }; + remaining_slices = remaining_slices + .into_iter() + .flat_map(|pos_slice| pos_slice.subtract(neg_slice)) + .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_slices.is_empty() { + break; + } } - _ => false, - }; - if other_ctors.iter().any(overlaps) { vec![] } else { vec![self.clone()] } - } - Slice { type_len: None, kind: VarLen(..) } => { - 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, `VarLen(i, j)` covers the union of `FixedLen` 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 { - Slice { type_len: Some(pos_len), .. } - | Slice { kind: FixedLen(pos_len), .. } => match *neg_ctor { - Slice { type_len: Some(neg_len), .. } - | Slice { kind: FixedLen(neg_len), .. } - if neg_len == pos_len => - { - smallvec![] - } - Slice { - type_len: None, - kind: VarLen(neg_prefix, neg_suffix), - } if neg_prefix + neg_suffix <= pos_len => smallvec![], - _ => smallvec![pos_ctor], - }, - Slice { type_len: None, kind: VarLen(pos_prefix, pos_suffix) } => { - let pos_len = pos_prefix + pos_suffix; - match *neg_ctor { - Slice { type_len: Some(neg_len), .. } - | Slice { kind: FixedLen(neg_len), .. } - if neg_len >= pos_len => - { - (pos_len..neg_len) - .map(|l| Slice { - type_len: None, - kind: FixedLen(l), - }) - // We know that `neg_len + 1 >= pos_len >= - // pos_suffix`. - .chain(Some(Slice { - type_len: None, - kind: VarLen( - neg_len + 1 - pos_suffix, - pos_suffix, - ), - })) - .collect() - } - Slice { - type_len: None, - kind: VarLen(neg_prefix, neg_suffix), - } => { - let neg_len = neg_prefix + neg_suffix; - if neg_len <= pos_len { - smallvec![] - } else { - (pos_len..neg_len) - .map(|l| Slice { - type_len: None, - kind: FixedLen(l), - }) - .collect() - } - } - _ => smallvec![pos_ctor], - } - } - _ => bug!( - "unexpected ctor while subtracting from VarLen: {:?}", - 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_slices.into_iter().map(Slice).collect() } - - remaining_ctors - } + }, IntRange(self_range) => { let mut remaining_ranges = vec![self_range.clone()]; for other_ctor in other_ctors { @@ -845,7 +867,7 @@ impl<'tcx> Constructor<'tcx> { } _ => vec![], }, - Slice { .. } => match ty.kind { + Slice(_) => match ty.kind { ty::Slice(ty) | ty::Array(ty, _) => { let arity = self.arity(cx, ty); (0..arity).map(|_| Pat::wildcard_from_ty(ty)).collect() @@ -875,7 +897,7 @@ impl<'tcx> Constructor<'tcx> { } _ => 0, }, - Slice { kind, .. } => kind.arity(), + Slice(slice) => slice.arity(), ConstantValue(..) | FloatRange(..) | IntRange(..) | NonExhaustive => 0, } } @@ -930,20 +952,17 @@ impl<'tcx> Constructor<'tcx> { ty::Slice(_) | ty::Array(..) => bug!("bad slice pattern {:?} {:?}", self, ty), _ => PatKind::Wild, }, - Slice { kind: FixedLen(_), .. } => { - PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] } - } - Slice { type_len: Some(len), kind: VarLen(prefix, suffix) } - if prefix + suffix == *len => - { - PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] } - } - Slice { kind: VarLen(prefix, _), .. } => { - let prefix = subpatterns.by_ref().take(*prefix as usize).collect(); - let suffix = subpatterns.collect(); - let wild = Pat::wildcard_from_ty(ty); - PatKind::Slice { prefix, slice: Some(wild), suffix } - } + Slice(slice) => match slice.pattern_kind() { + FixedLen(_) => { + PatKind::Slice { prefix: subpatterns.collect(), slice: None, suffix: vec![] } + } + VarLen(prefix, _) => { + let prefix = subpatterns.by_ref().take(prefix 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 }, &FloatRange(lo, hi, end) => PatKind::Range(PatRange { lo, hi, end }), IntRange(range) => return range.to_pat(cx.tcx), @@ -1159,16 +1178,13 @@ fn all_constructors<'a, 'tcx>( if len != 0 && cx.is_uninhabited(sub_ty) { vec![] } else { - vec![Slice { type_len: Some(len), kind: VarLen(0, 0) }] + vec![Slice(Slice { array_len: Some(len), kind: VarLen(0, 0) })] } } // 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 { type_len: None, kind: FixedLen(0) }] - } else { - vec![Slice { type_len: None, kind: VarLen(0, 0) }] - } + let kind = if cx.is_uninhabited(sub_ty) { FixedLen(0) } else { VarLen(0, 0) }; + vec![Slice(Slice { array_len: None, kind })] } ty::Adt(def, substs) if def.is_enum() => { let ctors: Vec<_> = def @@ -1750,7 +1766,7 @@ fn pat_constructor<'tcx>( } PatKind::Array { ref prefix, ref slice, ref suffix } | PatKind::Slice { ref prefix, ref slice, ref suffix } => { - let type_len = match pat.ty.kind { + let array_len = match pat.ty.kind { ty::Array(_, length) => Some(length.eval_usize(tcx, param_env)), ty::Slice(_) => None, _ => span_bug!(pat.span, "bad ty {:?} for slice pattern", pat.ty), @@ -1759,7 +1775,7 @@ fn pat_constructor<'tcx>( let suffix = suffix.len() as u64; let kind = if slice.is_some() { VarLen(prefix, suffix) } else { FixedLen(prefix + suffix) }; - Some(Slice { type_len, kind }) + Some(Slice(Slice { array_len, kind })) } PatKind::Or { .. } => { bug!("support for or-patterns has not been fully implemented yet."); @@ -1975,7 +1991,7 @@ fn split_grouped_constructors<'p, 'tcx>( .map(IntRange), ); } - Slice { kind: VarLen(self_prefix, self_suffix), type_len } => { + Slice(Slice { array_len, kind: VarLen(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. @@ -2084,26 +2100,29 @@ fn split_grouped_constructors<'p, 'tcx>( max_prefix_len = max_fixed_len + 1 - max_suffix_len; } - match type_len { + match array_len { Some(len) => { let kind = if max_prefix_len + max_suffix_len < len { VarLen(max_prefix_len, max_suffix_len) } else { FixedLen(len) }; - split_ctors.push(Slice { type_len, kind }); + split_ctors.push(Slice(Slice { array_len, kind })); } None => { - // `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 VarLen constructor. + // `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 VarLen + // constructor. split_ctors.extend( (self_prefix + self_suffix..max_prefix_len + max_suffix_len) - .map(|len| Slice { type_len, kind: FixedLen(len) }), + .map(|len| Slice(Slice { array_len, kind: FixedLen(len) })), ); - split_ctors - .push(Slice { type_len, kind: VarLen(max_prefix_len, max_suffix_len) }); + split_ctors.push(Slice(Slice { + array_len, + kind: VarLen(max_prefix_len, max_suffix_len), + })); } } } @@ -2324,7 +2343,7 @@ fn specialize_one_pattern<'p, 'a: 'p, 'q: 'p, 'tcx>( PatKind::Array { ref prefix, ref slice, ref suffix } | PatKind::Slice { ref prefix, ref slice, ref suffix } => match *constructor { - Slice { .. } => { + Slice(_) => { let pat_len = prefix.len() + suffix.len(); if let Some(slice_count) = ctor_wild_subpatterns.len().checked_sub(pat_len) { if slice_count == 0 || slice.is_some() { |