Factor out slice constructor struct and simplify

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() {