hir_ty/
inhabitedness.rs

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

hir_ty/
inhabitedness.rs
