1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317
//! As explained in [`crate::usefulness`], values and patterns are made from constructors applied to
//! fields. This file defines types that represent patterns in this way.
use std::fmt;
use smallvec::{smallvec, SmallVec};
use self::Constructor::*;
use crate::constructor::{Constructor, Slice, SliceKind};
use crate::{PatCx, PrivateUninhabitedField};
/// A globally unique id to distinguish patterns.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct PatId(u32);
impl PatId {
fn new() -> Self {
use std::sync::atomic::{AtomicU32, Ordering};
static PAT_ID: AtomicU32 = AtomicU32::new(0);
PatId(PAT_ID.fetch_add(1, Ordering::SeqCst))
}
}
/// A pattern with an index denoting which field it corresponds to.
pub struct IndexedPat<Cx: PatCx> {
pub idx: usize,
pub pat: DeconstructedPat<Cx>,
}
/// Values and patterns can be represented as a constructor applied to some fields. This represents
/// a pattern in this form. A `DeconstructedPat` will almost always come from user input; the only
/// exception are some `Wildcard`s introduced during pattern lowering.
pub struct DeconstructedPat<Cx: PatCx> {
ctor: Constructor<Cx>,
fields: Vec<IndexedPat<Cx>>,
/// The number of fields in this pattern. E.g. if the pattern is `SomeStruct { field12: true, ..
/// }` this would be the total number of fields of the struct.
/// This is also the same as `self.ctor.arity(self.ty)`.
arity: usize,
ty: Cx::Ty,
/// Extra data to store in a pattern.
data: Cx::PatData,
/// Globally-unique id used to track usefulness at the level of subpatterns.
pub(crate) uid: PatId,
}
impl<Cx: PatCx> DeconstructedPat<Cx> {
pub fn new(
ctor: Constructor<Cx>,
fields: Vec<IndexedPat<Cx>>,
arity: usize,
ty: Cx::Ty,
data: Cx::PatData,
) -> Self {
DeconstructedPat { ctor, fields, arity, ty, data, uid: PatId::new() }
}
pub fn at_index(self, idx: usize) -> IndexedPat<Cx> {
IndexedPat { idx, pat: self }
}
pub(crate) fn is_or_pat(&self) -> bool {
matches!(self.ctor, Or)
}
pub fn ctor(&self) -> &Constructor<Cx> {
&self.ctor
}
pub fn ty(&self) -> &Cx::Ty {
&self.ty
}
/// Returns the extra data stored in a pattern.
pub fn data(&self) -> &Cx::PatData {
&self.data
}
pub fn arity(&self) -> usize {
self.arity
}
pub fn iter_fields<'a>(&'a self) -> impl Iterator<Item = &'a IndexedPat<Cx>> {
self.fields.iter()
}
/// Specialize this pattern with a constructor.
/// `other_ctor` can be different from `self.ctor`, but must be covered by it.
pub(crate) fn specialize<'a>(
&'a self,
other_ctor: &Constructor<Cx>,
other_ctor_arity: usize,
) -> SmallVec<[PatOrWild<'a, Cx>; 2]> {
if matches!(other_ctor, PrivateUninhabited) {
// Skip this column.
return smallvec![];
}
// Start with a slice of wildcards of the appropriate length.
let mut fields: SmallVec<[_; 2]> = (0..other_ctor_arity).map(|_| PatOrWild::Wild).collect();
// Fill `fields` with our fields. The arities are known to be compatible.
match self.ctor {
// The only non-trivial case: two slices of different arity. `other_ctor` is guaranteed
// to have a larger arity, so we adjust the indices of the patterns in the suffix so
// that they are correctly positioned in the larger slice.
Slice(Slice { kind: SliceKind::VarLen(prefix, _), .. })
if self.arity != other_ctor_arity =>
{
for ipat in &self.fields {
let new_idx = if ipat.idx < prefix {
ipat.idx
} else {
// Adjust the indices in the suffix.
ipat.idx + other_ctor_arity - self.arity
};
fields[new_idx] = PatOrWild::Pat(&ipat.pat);
}
}
_ => {
for ipat in &self.fields {
fields[ipat.idx] = PatOrWild::Pat(&ipat.pat);
}
}
}
fields
}
/// Walk top-down and call `it` in each place where a pattern occurs
/// starting with the root pattern `walk` is called on. If `it` returns
/// false then we will descend no further but siblings will be processed.
pub fn walk<'a>(&'a self, it: &mut impl FnMut(&'a Self) -> bool) {
if !it(self) {
return;
}
for p in self.iter_fields() {
p.pat.walk(it)
}
}
}
/// This is best effort and not good enough for a `Display` impl.
impl<Cx: PatCx> fmt::Debug for DeconstructedPat<Cx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut fields: Vec<_> = (0..self.arity).map(|_| PatOrWild::Wild).collect();
for ipat in self.iter_fields() {
fields[ipat.idx] = PatOrWild::Pat(&ipat.pat);
}
self.ctor().fmt_fields(f, self.ty(), fields.into_iter())
}
}
/// Delegate to `uid`.
impl<Cx: PatCx> PartialEq for DeconstructedPat<Cx> {
fn eq(&self, other: &Self) -> bool {
self.uid == other.uid
}
}
/// Delegate to `uid`.
impl<Cx: PatCx> Eq for DeconstructedPat<Cx> {}
/// Delegate to `uid`.
impl<Cx: PatCx> std::hash::Hash for DeconstructedPat<Cx> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.uid.hash(state);
}
}
/// Represents either a pattern obtained from user input or a wildcard constructed during the
/// algorithm. Do not use `Wild` to represent a wildcard pattern comping from user input.
///
/// This is morally `Option<&'p DeconstructedPat>` where `None` is interpreted as a wildcard.
pub(crate) enum PatOrWild<'p, Cx: PatCx> {
/// A non-user-provided wildcard, created during specialization.
Wild,
/// A user-provided pattern.
Pat(&'p DeconstructedPat<Cx>),
}
impl<'p, Cx: PatCx> Clone for PatOrWild<'p, Cx> {
fn clone(&self) -> Self {
match self {
PatOrWild::Wild => PatOrWild::Wild,
PatOrWild::Pat(pat) => PatOrWild::Pat(pat),
}
}
}
impl<'p, Cx: PatCx> Copy for PatOrWild<'p, Cx> {}
impl<'p, Cx: PatCx> PatOrWild<'p, Cx> {
pub(crate) fn as_pat(&self) -> Option<&'p DeconstructedPat<Cx>> {
match self {
PatOrWild::Wild => None,
PatOrWild::Pat(pat) => Some(pat),
}
}
pub(crate) fn ctor(self) -> &'p Constructor<Cx> {
match self {
PatOrWild::Wild => &Wildcard,
PatOrWild::Pat(pat) => pat.ctor(),
}
}
pub(crate) fn is_or_pat(&self) -> bool {
match self {
PatOrWild::Wild => false,
PatOrWild::Pat(pat) => pat.is_or_pat(),
}
}
/// Expand this or-pattern into its alternatives. This only expands one or-pattern; use
/// `flatten_or_pat` to recursively expand nested or-patterns.
pub(crate) fn expand_or_pat(self) -> SmallVec<[Self; 1]> {
match self {
PatOrWild::Pat(pat) if pat.is_or_pat() => {
pat.iter_fields().map(|ipat| PatOrWild::Pat(&ipat.pat)).collect()
}
_ => smallvec![self],
}
}
/// Recursively expand this (possibly-nested) or-pattern into its alternatives.
pub(crate) fn flatten_or_pat(self) -> SmallVec<[Self; 1]> {
match self {
PatOrWild::Pat(pat) if pat.is_or_pat() => pat
.iter_fields()
.flat_map(|ipat| PatOrWild::Pat(&ipat.pat).flatten_or_pat())
.collect(),
_ => smallvec![self],
}
}
/// Specialize this pattern with a constructor.
/// `other_ctor` can be different from `self.ctor`, but must be covered by it.
pub(crate) fn specialize(
&self,
other_ctor: &Constructor<Cx>,
ctor_arity: usize,
) -> SmallVec<[PatOrWild<'p, Cx>; 2]> {
match self {
PatOrWild::Wild => (0..ctor_arity).map(|_| PatOrWild::Wild).collect(),
PatOrWild::Pat(pat) => pat.specialize(other_ctor, ctor_arity),
}
}
}
impl<'p, Cx: PatCx> fmt::Debug for PatOrWild<'p, Cx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
PatOrWild::Wild => write!(f, "_"),
PatOrWild::Pat(pat) => pat.fmt(f),
}
}
}
/// Same idea as `DeconstructedPat`, except this is a fictitious pattern built up for diagnostics
/// purposes. As such they don't use interning and can be cloned.
pub struct WitnessPat<Cx: PatCx> {
ctor: Constructor<Cx>,
pub(crate) fields: Vec<WitnessPat<Cx>>,
ty: Cx::Ty,
}
impl<Cx: PatCx> Clone for WitnessPat<Cx> {
fn clone(&self) -> Self {
Self { ctor: self.ctor.clone(), fields: self.fields.clone(), ty: self.ty.clone() }
}
}
impl<Cx: PatCx> WitnessPat<Cx> {
pub(crate) fn new(ctor: Constructor<Cx>, fields: Vec<Self>, ty: Cx::Ty) -> Self {
Self { ctor, fields, ty }
}
/// Create a wildcard pattern for this type. If the type is empty, we create a `!` pattern.
pub(crate) fn wildcard(cx: &Cx, ty: Cx::Ty) -> Self {
let is_empty = cx.ctors_for_ty(&ty).is_ok_and(|ctors| ctors.all_empty());
let ctor = if is_empty { Never } else { Wildcard };
Self::new(ctor, Vec::new(), ty)
}
/// Construct a pattern that matches everything that starts with this constructor.
/// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
/// `Some(_)`.
pub(crate) fn wild_from_ctor(cx: &Cx, ctor: Constructor<Cx>, ty: Cx::Ty) -> Self {
if matches!(ctor, Wildcard) {
return Self::wildcard(cx, ty);
}
let fields = cx
.ctor_sub_tys(&ctor, &ty)
.filter(|(_, PrivateUninhabitedField(skip))| !skip)
.map(|(ty, _)| Self::wildcard(cx, ty))
.collect();
Self::new(ctor, fields, ty)
}
pub fn ctor(&self) -> &Constructor<Cx> {
&self.ctor
}
pub fn ty(&self) -> &Cx::Ty {
&self.ty
}
pub fn is_never_pattern(&self) -> bool {
match self.ctor() {
Never => true,
Or => self.fields.iter().all(|p| p.is_never_pattern()),
_ => self.fields.iter().any(|p| p.is_never_pattern()),
}
}
pub fn iter_fields(&self) -> impl Iterator<Item = &WitnessPat<Cx>> {
self.fields.iter()
}
}
/// This is best effort and not good enough for a `Display` impl.
impl<Cx: PatCx> fmt::Debug for WitnessPat<Cx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
self.ctor().fmt_fields(f, self.ty(), self.fields.iter())
}
}