rustc_middle/ty/inhabitedness/
mod.rs

1//! This module contains logic for determining whether a type is inhabited or
2//! uninhabited. The [`InhabitedPredicate`] type captures the minimum
3//! information needed to determine whether a type is inhabited given a
4//! `ParamEnv` and module ID.
5//!
6//! # Example
7//! ```rust
8//! #![feature(never_type)]
9//! mod a {
10//!     pub mod b {
11//!         pub struct SecretlyUninhabited {
12//!             _priv: !,
13//!         }
14//!     }
15//! }
16//!
17//! mod c {
18//!     enum Void {}
19//!     pub struct AlsoSecretlyUninhabited {
20//!         _priv: Void,
21//!     }
22//!     mod d {
23//!     }
24//! }
25//!
26//! struct Foo {
27//!     x: a::b::SecretlyUninhabited,
28//!     y: c::AlsoSecretlyUninhabited,
29//! }
30//! ```
31//! In this code, the type `Foo` will only be visibly uninhabited inside the
32//! modules `b`, `c` and `d`. Calling `inhabited_predicate` on `Foo` will
33//! return `NotInModule(b) AND NotInModule(c)`.
34//!
35//! We need this information for pattern-matching on `Foo` or types that contain
36//! `Foo`.
37//!
38//! # Example
39//! ```ignore(illustrative)
40//! let foo_result: Result<T, Foo> = ... ;
41//! let Ok(t) = foo_result;
42//! ```
43//! This code should only compile in modules where the uninhabitedness of `Foo`
44//! is visible.
45
46use rustc_span::sym;
47use rustc_type_ir::TyKind::*;
48use tracing::instrument;
49
50use crate::query::Providers;
51use crate::ty::context::TyCtxt;
52use crate::ty::{self, DefId, Ty, TypeVisitableExt, VariantDef, Visibility};
53
54pub mod inhabited_predicate;
55
56pub use inhabited_predicate::InhabitedPredicate;
57
58pub(crate) fn provide(providers: &mut Providers) {
59    *providers = Providers { inhabited_predicate_adt, inhabited_predicate_type, ..*providers };
60}
61
62/// Returns an `InhabitedPredicate` that is generic over type parameters and
63/// requires calling [`InhabitedPredicate::instantiate`]
64fn inhabited_predicate_adt(tcx: TyCtxt<'_>, def_id: DefId) -> InhabitedPredicate<'_> {
65    if let Some(def_id) = def_id.as_local() {
66        if matches!(tcx.representability(def_id), ty::Representability::Infinite(_)) {
67            return InhabitedPredicate::True;
68        }
69    }
70    let adt = tcx.adt_def(def_id);
71    InhabitedPredicate::any(
72        tcx,
73        adt.variants().iter().map(|variant| variant.inhabited_predicate(tcx, adt)),
74    )
75}
76
77impl<'tcx> VariantDef {
78    /// Calculates the forest of `DefId`s from which this variant is visibly uninhabited.
79    pub fn inhabited_predicate(
80        &self,
81        tcx: TyCtxt<'tcx>,
82        adt: ty::AdtDef<'_>,
83    ) -> InhabitedPredicate<'tcx> {
84        debug_assert!(!adt.is_union());
85        InhabitedPredicate::all(
86            tcx,
87            self.fields.iter().map(|field| {
88                // Unstable fields are always considered to be inhabited. In the future,
89                // this could be extended to be conditional on the field being unstable
90                // only within the module that's querying the inhabitedness, like:
91                //     `let pred = pred.or(InhabitedPredicate::IsUnstable(field.did));`
92                // but this is unnecessary for now, since it would only affect nightly-only
93                // code or code within the standard library itself.
94                // HACK: We filter out `rustc_private` fields since with the flag
95                // `-Zforce-unstable-if-unmarked` we consider all unmarked fields to be
96                // unstable when building the compiler.
97                if tcx
98                    .lookup_stability(field.did)
99                    .is_some_and(|stab| stab.is_unstable() && stab.feature != sym::rustc_private)
100                {
101                    return InhabitedPredicate::True;
102                }
103                let pred = tcx.type_of(field.did).instantiate_identity().inhabited_predicate(tcx);
104                if adt.is_enum() {
105                    return pred;
106                }
107                match field.vis {
108                    Visibility::Public => pred,
109                    Visibility::Restricted(from) => {
110                        pred.or(tcx, InhabitedPredicate::NotInModule(from))
111                    }
112                }
113            }),
114        )
115    }
116}
117
118impl<'tcx> Ty<'tcx> {
119    #[instrument(level = "debug", skip(tcx), ret)]
120    pub fn inhabited_predicate(self, tcx: TyCtxt<'tcx>) -> InhabitedPredicate<'tcx> {
121        debug_assert!(!self.has_infer());
122        match self.kind() {
123            // For now, unions are always considered inhabited
124            Adt(adt, _) if adt.is_union() => InhabitedPredicate::True,
125            // Non-exhaustive ADTs from other crates are always considered inhabited
126            Adt(adt, _) if adt.variant_list_has_applicable_non_exhaustive() => {
127                InhabitedPredicate::True
128            }
129            Never => InhabitedPredicate::False,
130            Param(_) | Alias(ty::Projection | ty::Weak, _) => InhabitedPredicate::GenericType(self),
131            Alias(ty::Opaque, alias_ty) => {
132                match alias_ty.def_id.as_local() {
133                    // Foreign opaque is considered inhabited.
134                    None => InhabitedPredicate::True,
135                    // Local opaque type may possibly be revealed.
136                    Some(local_def_id) => {
137                        let key = ty::OpaqueTypeKey { def_id: local_def_id, args: alias_ty.args };
138                        InhabitedPredicate::OpaqueType(key)
139                    }
140                }
141            }
142            // FIXME(inherent_associated_types): Most likely we can just map to `GenericType` like above.
143            // However it's unclear if the args passed to `InhabitedPredicate::instantiate` are of the correct
144            // format, i.e. don't contain parent args. If you hit this case, please verify this beforehand.
145            Alias(ty::Inherent, _) => {
146                bug!("unimplemented: inhabitedness checking for inherent projections")
147            }
148            Tuple(tys) if tys.is_empty() => InhabitedPredicate::True,
149            // use a query for more complex cases
150            Adt(..) | Array(..) | Tuple(_) => tcx.inhabited_predicate_type(self),
151            // references and other types are inhabited
152            _ => InhabitedPredicate::True,
153        }
154    }
155
156    /// Checks whether a type is visibly uninhabited from a particular module.
157    ///
158    /// # Example
159    /// ```
160    /// #![feature(never_type)]
161    /// # fn main() {}
162    /// enum Void {}
163    /// mod a {
164    ///     pub mod b {
165    ///         pub struct SecretlyUninhabited {
166    ///             _priv: !,
167    ///         }
168    ///     }
169    /// }
170    ///
171    /// mod c {
172    ///     use super::Void;
173    ///     pub struct AlsoSecretlyUninhabited {
174    ///         _priv: Void,
175    ///     }
176    ///     mod d {
177    ///     }
178    /// }
179    ///
180    /// struct Foo {
181    ///     x: a::b::SecretlyUninhabited,
182    ///     y: c::AlsoSecretlyUninhabited,
183    /// }
184    /// ```
185    /// In this code, the type `Foo` will only be visibly uninhabited inside the
186    /// modules b, c and d. This effects pattern-matching on `Foo` or types that
187    /// contain `Foo`.
188    ///
189    /// # Example
190    /// ```ignore (illustrative)
191    /// let foo_result: Result<T, Foo> = ... ;
192    /// let Ok(t) = foo_result;
193    /// ```
194    /// This code should only compile in modules where the uninhabitedness of Foo is
195    /// visible.
196    pub fn is_inhabited_from(
197        self,
198        tcx: TyCtxt<'tcx>,
199        module: DefId,
200        typing_env: ty::TypingEnv<'tcx>,
201    ) -> bool {
202        self.inhabited_predicate(tcx).apply(tcx, typing_env, module)
203    }
204
205    /// Returns true if the type is uninhabited without regard to visibility
206    pub fn is_privately_uninhabited(
207        self,
208        tcx: TyCtxt<'tcx>,
209        typing_env: ty::TypingEnv<'tcx>,
210    ) -> bool {
211        !self.inhabited_predicate(tcx).apply_ignore_module(tcx, typing_env)
212    }
213}
214
215/// N.B. this query should only be called through `Ty::inhabited_predicate`
216fn inhabited_predicate_type<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> InhabitedPredicate<'tcx> {
217    match *ty.kind() {
218        Adt(adt, args) => tcx.inhabited_predicate_adt(adt.did()).instantiate(tcx, args),
219
220        Tuple(tys) => {
221            InhabitedPredicate::all(tcx, tys.iter().map(|ty| ty.inhabited_predicate(tcx)))
222        }
223
224        // If we can evaluate the array length before having a `ParamEnv`, then
225        // we can simplify the predicate. This is an optimization.
226        Array(ty, len) => match len.try_to_target_usize(tcx) {
227            Some(0) => InhabitedPredicate::True,
228            Some(1..) => ty.inhabited_predicate(tcx),
229            None => ty.inhabited_predicate(tcx).or(tcx, InhabitedPredicate::ConstIsZero(len)),
230        },
231
232        _ => bug!("unexpected TyKind, use `Ty::inhabited_predicate`"),
233    }
234}