hir_ty/diagnostics/match_check/
pat_analysis.rs

Help
1//! Interface with `rustc_pattern_analysis`.
2
3use std::cell::LazyCell;
4use std::fmt;
5
6use hir_def::{DefWithBodyId, EnumId, EnumVariantId, HasModule, LocalFieldId, ModuleId, VariantId};
7use intern::sym;
8use rustc_pattern_analysis::{
9    Captures, IndexVec, PatCx, PrivateUninhabitedField,
10    constructor::{Constructor, ConstructorSet, VariantVisibility},
11    usefulness::{PlaceValidity, UsefulnessReport, compute_match_usefulness},
12};
13use smallvec::{SmallVec, smallvec};
14use stdx::never;
15
16use crate::{
17    AdtId, Interner, Scalar, Ty, TyExt, TyKind,
18    db::HirDatabase,
19    infer::normalize,
20    inhabitedness::{is_enum_variant_uninhabited_from, is_ty_uninhabited_from},
21};
22
23use super::{FieldPat, Pat, PatKind, is_box};
24
25use Constructor::*;
26
27// Re-export r-a-specific versions of all these types.
28pub(crate) type DeconstructedPat<'db> =
29    rustc_pattern_analysis::pat::DeconstructedPat<MatchCheckCtx<'db>>;
30pub(crate) type MatchArm<'db> = rustc_pattern_analysis::MatchArm<'db, MatchCheckCtx<'db>>;
31pub(crate) type WitnessPat<'db> = rustc_pattern_analysis::pat::WitnessPat<MatchCheckCtx<'db>>;
32
33/// [Constructor] uses this in unimplemented variants.
34/// It allows porting match expressions from upstream algorithm without losing semantics.
35#[derive(Copy, Clone, Debug, PartialEq, Eq)]
36pub(crate) enum Void {}
37
38/// An index type for enum variants. This ranges from 0 to `variants.len()`, whereas `EnumVariantId`
39/// can take arbitrary large values (and hence mustn't be used with `IndexVec`/`BitSet`).
40#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
41pub(crate) struct EnumVariantContiguousIndex(usize);
42
43impl EnumVariantContiguousIndex {
44    fn from_enum_variant_id(db: &dyn HirDatabase, target_evid: EnumVariantId) -> Self {
45        // Find the index of this variant in the list of variants.
46        use hir_def::Lookup;
47        let i = target_evid.lookup(db.upcast()).index as usize;
48        EnumVariantContiguousIndex(i)
49    }
50
51    fn to_enum_variant_id(self, db: &dyn HirDatabase, eid: EnumId) -> EnumVariantId {
52        db.enum_variants(eid).variants[self.0].0
53    }
54}
55
56impl rustc_pattern_analysis::Idx for EnumVariantContiguousIndex {
57    fn new(idx: usize) -> Self {
58        EnumVariantContiguousIndex(idx)
59    }
60
61    fn index(self) -> usize {
62        self.0
63    }
64}
65
66#[derive(Clone)]
67pub(crate) struct MatchCheckCtx<'db> {
68    module: ModuleId,
69    body: DefWithBodyId,
70    pub(crate) db: &'db dyn HirDatabase,
71    exhaustive_patterns: bool,
72}
73
74impl<'db> MatchCheckCtx<'db> {
75    pub(crate) fn new(module: ModuleId, body: DefWithBodyId, db: &'db dyn HirDatabase) -> Self {
76        let def_map = db.crate_def_map(module.krate());
77        let exhaustive_patterns = def_map.is_unstable_feature_enabled(&sym::exhaustive_patterns);
78        Self { module, body, db, exhaustive_patterns }
79    }
80
81    pub(crate) fn compute_match_usefulness(
82        &self,
83        arms: &[MatchArm<'db>],
84        scrut_ty: Ty,
85        known_valid_scrutinee: Option<bool>,
86    ) -> Result<UsefulnessReport<'db, Self>, ()> {
87        if scrut_ty.contains_unknown() {
88            return Err(());
89        }
90        for arm in arms {
91            if arm.pat.ty().contains_unknown() {
92                return Err(());
93            }
94        }
95
96        let place_validity = PlaceValidity::from_bool(known_valid_scrutinee.unwrap_or(true));
97        // Measured to take ~100ms on modern hardware.
98        let complexity_limit = 500000;
99        compute_match_usefulness(self, arms, scrut_ty, place_validity, complexity_limit)
100    }
101
102    fn is_uninhabited(&self, ty: &Ty) -> bool {
103        is_ty_uninhabited_from(self.db, ty, self.module)
104    }
105
106    /// Returns whether the given ADT is from another crate declared `#[non_exhaustive]`.
107    fn is_foreign_non_exhaustive(&self, adt: hir_def::AdtId) -> bool {
108        let is_local = adt.krate(self.db.upcast()) == self.module.krate();
109        !is_local && self.db.attrs(adt.into()).by_key(&sym::non_exhaustive).exists()
110    }
111
112    fn variant_id_for_adt(
113        db: &'db dyn HirDatabase,
114        ctor: &Constructor<Self>,
115        adt: hir_def::AdtId,
116    ) -> Option<VariantId> {
117        match ctor {
118            Variant(id) => {
119                let hir_def::AdtId::EnumId(eid) = adt else {
120                    panic!("bad constructor {ctor:?} for adt {adt:?}")
121                };
122                Some(id.to_enum_variant_id(db, eid).into())
123            }
124            Struct | UnionField => match adt {
125                hir_def::AdtId::EnumId(_) => None,
126                hir_def::AdtId::StructId(id) => Some(id.into()),
127                hir_def::AdtId::UnionId(id) => Some(id.into()),
128            },
129            _ => panic!("bad constructor {ctor:?} for adt {adt:?}"),
130        }
131    }
132
133    // This lists the fields of a variant along with their types.
134    fn list_variant_fields<'a>(
135        &'a self,
136        ty: &'a Ty,
137        variant: VariantId,
138    ) -> impl Iterator<Item = (LocalFieldId, Ty)> + Captures<'a> + Captures<'db> {
139        let (_, substs) = ty.as_adt().unwrap();
140
141        let field_tys = self.db.field_types(variant);
142        let fields_len = variant.variant_data(self.db.upcast()).fields().len() as u32;
143
144        (0..fields_len).map(|idx| LocalFieldId::from_raw(idx.into())).map(move |fid| {
145            let ty = field_tys[fid].clone().substitute(Interner, substs);
146            let ty = normalize(self.db, self.db.trait_environment_for_body(self.body), ty);
147            (fid, ty)
148        })
149    }
150
151    pub(crate) fn lower_pat(&self, pat: &Pat) -> DeconstructedPat<'db> {
152        let singleton = |pat: DeconstructedPat<'db>| vec![pat.at_index(0)];
153        let ctor;
154        let mut fields: Vec<_>;
155        let arity;
156
157        match pat.kind.as_ref() {
158            PatKind::Binding { subpattern: Some(subpat), .. } => return self.lower_pat(subpat),
159            PatKind::Binding { subpattern: None, .. } | PatKind::Wild => {
160                ctor = Wildcard;
161                fields = Vec::new();
162                arity = 0;
163            }
164            PatKind::Deref { subpattern } => {
165                ctor = match pat.ty.kind(Interner) {
166                    // This is a box pattern.
167                    TyKind::Adt(adt, _) if is_box(self.db, adt.0) => Struct,
168                    TyKind::Ref(..) => Ref,
169                    _ => {
170                        never!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, &pat.ty);
171                        Wildcard
172                    }
173                };
174                fields = singleton(self.lower_pat(subpattern));
175                arity = 1;
176            }
177            PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => {
178                fields = subpatterns
179                    .iter()
180                    .map(|pat| {
181                        let idx: u32 = pat.field.into_raw().into();
182                        self.lower_pat(&pat.pattern).at_index(idx as usize)
183                    })
184                    .collect();
185                match pat.ty.kind(Interner) {
186                    TyKind::Tuple(_, substs) => {
187                        ctor = Struct;
188                        arity = substs.len(Interner);
189                    }
190                    TyKind::Adt(adt, _) if is_box(self.db, adt.0) => {
191                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
192                        // patterns. If we're here we can assume this is a box pattern.
193                        // FIXME(Nadrieril): A `Box` can in theory be matched either with `Box(_,
194                        // _)` or a box pattern. As a hack to avoid an ICE with the former, we
195                        // ignore other fields than the first one. This will trigger an error later
196                        // anyway.
197                        // See https://github.com/rust-lang/rust/issues/82772 ,
198                        // explanation: https://github.com/rust-lang/rust/pull/82789#issuecomment-796921977
199                        // The problem is that we can't know from the type whether we'll match
200                        // normally or through box-patterns. We'll have to figure out a proper
201                        // solution when we introduce generalized deref patterns. Also need to
202                        // prevent mixing of those two options.
203                        fields.retain(|ipat| ipat.idx == 0);
204                        ctor = Struct;
205                        arity = 1;
206                    }
207                    &TyKind::Adt(AdtId(adt), _) => {
208                        ctor = match pat.kind.as_ref() {
209                            PatKind::Leaf { .. } if matches!(adt, hir_def::AdtId::UnionId(_)) => {
210                                UnionField
211                            }
212                            PatKind::Leaf { .. } => Struct,
213                            PatKind::Variant { enum_variant, .. } => {
214                                Variant(EnumVariantContiguousIndex::from_enum_variant_id(
215                                    self.db,
216                                    *enum_variant,
217                                ))
218                            }
219                            _ => {
220                                never!();
221                                Wildcard
222                            }
223                        };
224                        let variant = Self::variant_id_for_adt(self.db, &ctor, adt).unwrap();
225                        arity = variant.variant_data(self.db.upcast()).fields().len();
226                    }
227                    _ => {
228                        never!("pattern has unexpected type: pat: {:?}, ty: {:?}", pat, &pat.ty);
229                        ctor = Wildcard;
230                        fields.clear();
231                        arity = 0;
232                    }
233                }
234            }
235            &PatKind::LiteralBool { value } => {
236                ctor = Bool(value);
237                fields = Vec::new();
238                arity = 0;
239            }
240            PatKind::Never => {
241                ctor = Never;
242                fields = Vec::new();
243                arity = 0;
244            }
245            PatKind::Or { pats } => {
246                ctor = Or;
247                fields = pats
248                    .iter()
249                    .enumerate()
250                    .map(|(i, pat)| self.lower_pat(pat).at_index(i))
251                    .collect();
252                arity = pats.len();
253            }
254        }
255        DeconstructedPat::new(ctor, fields, arity, pat.ty.clone(), ())
256    }
257
258    pub(crate) fn hoist_witness_pat(&self, pat: &WitnessPat<'db>) -> Pat {
259        let mut subpatterns = pat.iter_fields().map(|p| self.hoist_witness_pat(p));
260        let kind = match pat.ctor() {
261            &Bool(value) => PatKind::LiteralBool { value },
262            IntRange(_) => unimplemented!(),
263            Struct | Variant(_) | UnionField => match pat.ty().kind(Interner) {
264                TyKind::Tuple(..) => PatKind::Leaf {
265                    subpatterns: subpatterns
266                        .zip(0u32..)
267                        .map(|(p, i)| FieldPat {
268                            field: LocalFieldId::from_raw(i.into()),
269                            pattern: p,
270                        })
271                        .collect(),
272                },
273                TyKind::Adt(adt, _) if is_box(self.db, adt.0) => {
274                    // Without `box_patterns`, the only legal pattern of type `Box` is `_` (outside
275                    // of `std`). So this branch is only reachable when the feature is enabled and
276                    // the pattern is a box pattern.
277                    PatKind::Deref { subpattern: subpatterns.next().unwrap() }
278                }
279                TyKind::Adt(adt, substs) => {
280                    let variant = Self::variant_id_for_adt(self.db, pat.ctor(), adt.0).unwrap();
281                    let subpatterns = self
282                        .list_variant_fields(pat.ty(), variant)
283                        .zip(subpatterns)
284                        .map(|((field, _ty), pattern)| FieldPat { field, pattern })
285                        .collect();
286
287                    if let VariantId::EnumVariantId(enum_variant) = variant {
288                        PatKind::Variant { substs: substs.clone(), enum_variant, subpatterns }
289                    } else {
290                        PatKind::Leaf { subpatterns }
291                    }
292                }
293                _ => {
294                    never!("unexpected ctor for type {:?} {:?}", pat.ctor(), pat.ty());
295                    PatKind::Wild
296                }
297            },
298            // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should
299            // be careful to reconstruct the correct constant pattern here. However a string
300            // literal pattern will never be reported as a non-exhaustiveness witness, so we
301            // ignore this issue.
302            Ref => PatKind::Deref { subpattern: subpatterns.next().unwrap() },
303            Slice(_) => unimplemented!(),
304            &Str(void) => match void {},
305            Wildcard | NonExhaustive | Hidden | PrivateUninhabited => PatKind::Wild,
306            Never => PatKind::Never,
307            Missing | F16Range(..) | F32Range(..) | F64Range(..) | F128Range(..) | Opaque(..)
308            | Or => {
309                never!("can't convert to pattern: {:?}", pat.ctor());
310                PatKind::Wild
311            }
312        };
313        Pat { ty: pat.ty().clone(), kind: Box::new(kind) }
314    }
315}
316
317impl PatCx for MatchCheckCtx<'_> {
318    type Error = ();
319    type Ty = Ty;
320    type VariantIdx = EnumVariantContiguousIndex;
321    type StrLit = Void;
322    type ArmData = ();
323    type PatData = ();
324
325    fn is_exhaustive_patterns_feature_on(&self) -> bool {
326        self.exhaustive_patterns
327    }
328
329    fn ctor_arity(
330        &self,
331        ctor: &rustc_pattern_analysis::constructor::Constructor<Self>,
332        ty: &Self::Ty,
333    ) -> usize {
334        match ctor {
335            Struct | Variant(_) | UnionField => match *ty.kind(Interner) {
336                TyKind::Tuple(arity, ..) => arity,
337                TyKind::Adt(AdtId(adt), ..) => {
338                    if is_box(self.db, adt) {
339                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
340                        // patterns. If we're here we can assume this is a box pattern.
341                        1
342                    } else {
343                        let variant = Self::variant_id_for_adt(self.db, ctor, adt).unwrap();
344                        variant.variant_data(self.db.upcast()).fields().len()
345                    }
346                }
347                _ => {
348                    never!("Unexpected type for `Single` constructor: {:?}", ty);
349                    0
350                }
351            },
352            Ref => 1,
353            Slice(..) => unimplemented!(),
354            Never | Bool(..) | IntRange(..) | F16Range(..) | F32Range(..) | F64Range(..)
355            | F128Range(..) | Str(..) | Opaque(..) | NonExhaustive | PrivateUninhabited
356            | Hidden | Missing | Wildcard => 0,
357            Or => {
358                never!("The `Or` constructor doesn't have a fixed arity");
359                0
360            }
361        }
362    }
363
364    fn ctor_sub_tys(
365        &self,
366        ctor: &rustc_pattern_analysis::constructor::Constructor<Self>,
367        ty: &Self::Ty,
368    ) -> impl ExactSizeIterator<Item = (Self::Ty, PrivateUninhabitedField)> {
369        let single = |ty| smallvec![(ty, PrivateUninhabitedField(false))];
370        let tys: SmallVec<[_; 2]> = match ctor {
371            Struct | Variant(_) | UnionField => match ty.kind(Interner) {
372                TyKind::Tuple(_, substs) => {
373                    let tys = substs.iter(Interner).map(|ty| ty.assert_ty_ref(Interner));
374                    tys.cloned().map(|ty| (ty, PrivateUninhabitedField(false))).collect()
375                }
376                TyKind::Ref(.., rty) => single(rty.clone()),
377                &TyKind::Adt(AdtId(adt), ref substs) => {
378                    if is_box(self.db, adt) {
379                        // The only legal patterns of type `Box` (outside `std`) are `_` and box
380                        // patterns. If we're here we can assume this is a box pattern.
381                        let subst_ty = substs.at(Interner, 0).assert_ty_ref(Interner).clone();
382                        single(subst_ty)
383                    } else {
384                        let variant = Self::variant_id_for_adt(self.db, ctor, adt).unwrap();
385
386                        let visibilities = LazyCell::new(|| self.db.field_visibilities(variant));
387
388                        self.list_variant_fields(ty, variant)
389                            .map(move |(fid, ty)| {
390                                let is_visible = || {
391                                    matches!(adt, hir_def::AdtId::EnumId(..))
392                                        || visibilities[fid]
393                                            .is_visible_from(self.db.upcast(), self.module)
394                                };
395                                let is_uninhabited = self.is_uninhabited(&ty);
396                                let private_uninhabited = is_uninhabited && !is_visible();
397                                (ty, PrivateUninhabitedField(private_uninhabited))
398                            })
399                            .collect()
400                    }
401                }
402                ty_kind => {
403                    never!("Unexpected type for `{:?}` constructor: {:?}", ctor, ty_kind);
404                    single(ty.clone())
405                }
406            },
407            Ref => match ty.kind(Interner) {
408                TyKind::Ref(.., rty) => single(rty.clone()),
409                ty_kind => {
410                    never!("Unexpected type for `{:?}` constructor: {:?}", ctor, ty_kind);
411                    single(ty.clone())
412                }
413            },
414            Slice(_) => unreachable!("Found a `Slice` constructor in match checking"),
415            Never | Bool(..) | IntRange(..) | F16Range(..) | F32Range(..) | F64Range(..)
416            | F128Range(..) | Str(..) | Opaque(..) | NonExhaustive | PrivateUninhabited
417            | Hidden | Missing | Wildcard => {
418                smallvec![]
419            }
420            Or => {
421                never!("called `Fields::wildcards` on an `Or` ctor");
422                smallvec![]
423            }
424        };
425        tys.into_iter()
426    }
427
428    fn ctors_for_ty(
429        &self,
430        ty: &Self::Ty,
431    ) -> Result<rustc_pattern_analysis::constructor::ConstructorSet<Self>, Self::Error> {
432        let cx = self;
433
434        // Unhandled types are treated as non-exhaustive. Being explicit here instead of falling
435        // to catchall arm to ease further implementation.
436        let unhandled = || ConstructorSet::Unlistable;
437
438        // This determines the set of all possible constructors for the type `ty`. For numbers,
439        // arrays and slices we use ranges and variable-length slices when appropriate.
440        //
441        // If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that
442        // are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the
443        // returned list of constructors.
444        // Invariant: this is empty if and only if the type is uninhabited (as determined by
445        // `cx.is_uninhabited()`).
446        Ok(match ty.kind(Interner) {
447            TyKind::Scalar(Scalar::Bool) => ConstructorSet::Bool,
448            TyKind::Scalar(Scalar::Char) => unhandled(),
449            TyKind::Scalar(Scalar::Int(..) | Scalar::Uint(..)) => unhandled(),
450            TyKind::Array(..) | TyKind::Slice(..) => unhandled(),
451            &TyKind::Adt(AdtId(adt @ hir_def::AdtId::EnumId(enum_id)), ref subst) => {
452                let enum_data = cx.db.enum_variants(enum_id);
453                let is_declared_nonexhaustive = cx.is_foreign_non_exhaustive(adt);
454
455                if enum_data.variants.is_empty() && !is_declared_nonexhaustive {
456                    ConstructorSet::NoConstructors
457                } else {
458                    let mut variants = IndexVec::with_capacity(enum_data.variants.len());
459                    for &(variant, _) in enum_data.variants.iter() {
460                        let is_uninhabited =
461                            is_enum_variant_uninhabited_from(cx.db, variant, subst, cx.module);
462                        let visibility = if is_uninhabited {
463                            VariantVisibility::Empty
464                        } else {
465                            VariantVisibility::Visible
466                        };
467                        variants.push(visibility);
468                    }
469
470                    ConstructorSet::Variants { variants, non_exhaustive: is_declared_nonexhaustive }
471                }
472            }
473            TyKind::Adt(AdtId(hir_def::AdtId::UnionId(_)), _) => ConstructorSet::Union,
474            TyKind::Adt(..) | TyKind::Tuple(..) => {
475                ConstructorSet::Struct { empty: cx.is_uninhabited(ty) }
476            }
477            TyKind::Ref(..) => ConstructorSet::Ref,
478            TyKind::Never => ConstructorSet::NoConstructors,
479            // This type is one for which we cannot list constructors, like `str` or `f64`.
480            _ => ConstructorSet::Unlistable,
481        })
482    }
483
484    fn write_variant_name(
485        f: &mut fmt::Formatter<'_>,
486        _ctor: &Constructor<Self>,
487        _ty: &Self::Ty,
488    ) -> fmt::Result {
489        write!(f, "<write_variant_name unsupported>")
490        // We lack the database here ...
491        // let variant = ty.as_adt().and_then(|(adt, _)| Self::variant_id_for_adt(db, ctor, adt));
492
493        // if let Some(variant) = variant {
494        //     match variant {
495        //         VariantId::EnumVariantId(v) => {
496        //             write!(f, "{}", db.enum_variant_data(v).name.display(db.upcast()))?;
497        //         }
498        //         VariantId::StructId(s) => {
499        //             write!(f, "{}", db.struct_data(s).name.display(db.upcast()))?
500        //         }
501        //         VariantId::UnionId(u) => {
502        //             write!(f, "{}", db.union_data(u).name.display(db.upcast()))?
503        //         }
504        //     }
505        // }
506        // Ok(())
507    }
508
509    fn bug(&self, fmt: fmt::Arguments<'_>) {
510        never!("{}", fmt)
511    }
512
513    fn complexity_exceeded(&self) -> Result<(), Self::Error> {
514        Err(())
515    }
516}
517
518impl fmt::Debug for MatchCheckCtx<'_> {
519    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
520        f.debug_struct("MatchCheckCtx").finish()
521    }
522}
hir_ty/diagnostics/match_check/pat_analysis.rs

hir_ty/diagnostics/match_check/
pat_analysis.rs
