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

hir_ty/diagnostics/match_check/
pat_analysis.rs
