hir_ty/
inhabitedness.rs

Help
1//! Type inhabitedness logic.
2use std::ops::ControlFlow::{self, Break, Continue};
3
4use chalk_ir::{
5    DebruijnIndex,
6    visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
7};
8use hir_def::{AdtId, EnumVariantId, ModuleId, VariantId, visibility::Visibility};
9use rustc_hash::FxHashSet;
10
11use crate::{
12    Binders, Interner, Substitution, Ty, TyKind, consteval::try_const_usize, db::HirDatabase,
13};
14
15// FIXME: Turn this into a query, it can be quite slow
16/// Checks whether a type is visibly uninhabited from a particular module.
17pub(crate) fn is_ty_uninhabited_from(db: &dyn HirDatabase, ty: &Ty, target_mod: ModuleId) -> bool {
18    let _p = tracing::info_span!("is_ty_uninhabited_from", ?ty).entered();
19    let mut uninhabited_from =
20        UninhabitedFrom { target_mod, db, max_depth: 500, recursive_ty: FxHashSet::default() };
21    let inhabitedness = ty.visit_with(&mut uninhabited_from, DebruijnIndex::INNERMOST);
22    inhabitedness == BREAK_VISIBLY_UNINHABITED
23}
24
25// FIXME: Turn this into a query, it can be quite slow
26/// Checks whether a variant is visibly uninhabited from a particular module.
27pub(crate) fn is_enum_variant_uninhabited_from(
28    db: &dyn HirDatabase,
29    variant: EnumVariantId,
30    subst: &Substitution,
31    target_mod: ModuleId,
32) -> bool {
33    let _p = tracing::info_span!("is_enum_variant_uninhabited_from").entered();
34
35    let mut uninhabited_from =
36        UninhabitedFrom { target_mod, db, max_depth: 500, recursive_ty: FxHashSet::default() };
37    let inhabitedness = uninhabited_from.visit_variant(variant.into(), subst);
38    inhabitedness == BREAK_VISIBLY_UNINHABITED
39}
40
41struct UninhabitedFrom<'a> {
42    target_mod: ModuleId,
43    recursive_ty: FxHashSet<Ty>,
44    // guard for preventing stack overflow in non trivial non terminating types
45    max_depth: usize,
46    db: &'a dyn HirDatabase,
47}
48
49const CONTINUE_OPAQUELY_INHABITED: ControlFlow<VisiblyUninhabited> = Continue(());
50const BREAK_VISIBLY_UNINHABITED: ControlFlow<VisiblyUninhabited> = Break(VisiblyUninhabited);
51#[derive(PartialEq, Eq)]
52struct VisiblyUninhabited;
53
54impl TypeVisitor<Interner> for UninhabitedFrom<'_> {
55    type BreakTy = VisiblyUninhabited;
56
57    fn as_dyn(&mut self) -> &mut dyn TypeVisitor<Interner, BreakTy = VisiblyUninhabited> {
58        self
59    }
60
61    fn visit_ty(
62        &mut self,
63        ty: &Ty,
64        outer_binder: DebruijnIndex,
65    ) -> ControlFlow<VisiblyUninhabited> {
66        if self.recursive_ty.contains(ty) || self.max_depth == 0 {
67            // rustc considers recursive types always inhabited. I think it is valid to consider
68            // recursive types as always uninhabited, but we should do what rustc is doing.
69            return CONTINUE_OPAQUELY_INHABITED;
70        }
71        self.recursive_ty.insert(ty.clone());
72        self.max_depth -= 1;
73        let r = match ty.kind(Interner) {
74            TyKind::Adt(adt, subst) => self.visit_adt(adt.0, subst),
75            TyKind::Never => BREAK_VISIBLY_UNINHABITED,
76            TyKind::Tuple(..) => ty.super_visit_with(self, outer_binder),
77            TyKind::Array(item_ty, len) => match try_const_usize(self.db, len) {
78                Some(0) | None => CONTINUE_OPAQUELY_INHABITED,
79                Some(1..) => item_ty.super_visit_with(self, outer_binder),
80            },
81            _ => CONTINUE_OPAQUELY_INHABITED,
82        };
83        self.recursive_ty.remove(ty);
84        self.max_depth += 1;
85        r
86    }
87
88    fn interner(&self) -> Interner {
89        Interner
90    }
91}
92
93impl UninhabitedFrom<'_> {
94    fn visit_adt(&mut self, adt: AdtId, subst: &Substitution) -> ControlFlow<VisiblyUninhabited> {
95        // An ADT is uninhabited iff all its variants uninhabited.
96        match adt {
97            // rustc: For now, `union`s are never considered uninhabited.
98            AdtId::UnionId(_) => CONTINUE_OPAQUELY_INHABITED,
99            AdtId::StructId(s) => self.visit_variant(s.into(), subst),
100            AdtId::EnumId(e) => {
101                let enum_data = self.db.enum_variants(e);
102
103                for &(variant, _) in enum_data.variants.iter() {
104                    let variant_inhabitedness = self.visit_variant(variant.into(), subst);
105                    match variant_inhabitedness {
106                        Break(VisiblyUninhabited) => (),
107                        Continue(()) => return CONTINUE_OPAQUELY_INHABITED,
108                    }
109                }
110                BREAK_VISIBLY_UNINHABITED
111            }
112        }
113    }
114
115    fn visit_variant(
116        &mut self,
117        variant: VariantId,
118        subst: &Substitution,
119    ) -> ControlFlow<VisiblyUninhabited> {
120        let variant_data = self.db.variant_fields(variant);
121        let fields = variant_data.fields();
122        if fields.is_empty() {
123            return CONTINUE_OPAQUELY_INHABITED;
124        }
125
126        let is_enum = matches!(variant, VariantId::EnumVariantId(..));
127        let field_tys = self.db.field_types(variant);
128        let field_vis = if is_enum { None } else { Some(self.db.field_visibilities(variant)) };
129
130        for (fid, _) in fields.iter() {
131            self.visit_field(field_vis.as_ref().map(|it| it[fid]), &field_tys[fid], subst)?;
132        }
133        CONTINUE_OPAQUELY_INHABITED
134    }
135
136    fn visit_field(
137        &mut self,
138        vis: Option<Visibility>,
139        ty: &Binders<Ty>,
140        subst: &Substitution,
141    ) -> ControlFlow<VisiblyUninhabited> {
142        if vis.is_none_or(|it| it.is_visible_from(self.db, self.target_mod)) {
143            let ty = ty.clone().substitute(Interner, subst);
144            ty.visit_with(self, DebruijnIndex::INNERMOST)
145        } else {
146            CONTINUE_OPAQUELY_INHABITED
147        }
148    }
149}
hir_ty/inhabitedness.rs

hir_ty/
inhabitedness.rs
