hir_ty/diagnostics/match_check/
pat_analysis.rs

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

hir_ty/diagnostics/match_check/
pat_analysis.rs
