compiler/rustc_middle/src/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
  46 use crate::ty::context::TyCtxt;
  47 use crate::ty::{self, DefId, Ty, VariantDef, Visibility};
  48
  49 use rustc_type_ir::sty::TyKind::*;
  50
  51 pub mod inhabited_predicate;
  52
  53 pub use inhabited_predicate::InhabitedPredicate;
  54
  55 pub(crate) fn provide(providers: &mut ty::query::Providers) {
  56     *providers =
  57         ty::query::Providers { inhabited_predicate_adt, inhabited_predicate_type, ..*providers };
  58 }
  59
  60 /// Returns an `InhabitedPredicate` that is generic over type parameters and
  61 /// requires calling [`InhabitedPredicate::subst`]
  62 fn inhabited_predicate_adt(tcx: TyCtxt<'_>, def_id: DefId) -> InhabitedPredicate<'_> {
  63     if let Some(def_id) = def_id.as_local() {
  64         if matches!(tcx.representability(def_id), ty::Representability::Infinite) {
  65             return InhabitedPredicate::True;
  66         }
  67     }
  68     let adt = tcx.adt_def(def_id);
  69     InhabitedPredicate::any(
  70         tcx,
  71         adt.variants().iter().map(|variant| variant.inhabited_predicate(tcx, adt)),
  72     )
  73 }
  74
  75 impl<'tcx> VariantDef {
  76     /// Calculates the forest of `DefId`s from which this variant is visibly uninhabited.
  77     pub fn inhabited_predicate(
  78         &self,
  79         tcx: TyCtxt<'tcx>,
  80         adt: ty::AdtDef<'_>,
  81     ) -> InhabitedPredicate<'tcx> {
  82         debug_assert!(!adt.is_union());
  83         if self.is_field_list_non_exhaustive() && !self.def_id.is_local() {
  84             // Non-exhaustive variants from other crates are always considered inhabited.
  85             return InhabitedPredicate::True;
  86         }
  87         InhabitedPredicate::all(
  88             tcx,
  89             self.fields.iter().map(|field| {
  90                 let pred = tcx.type_of(field.did).inhabited_predicate(tcx);
  91                 if adt.is_enum() {
  92                     return pred;
  93                 }
  94                 match field.vis {
  95                     Visibility::Public => pred,
  96                     Visibility::Restricted(from) => {
  97                         pred.or(tcx, InhabitedPredicate::NotInModule(from))
  98                     }
  99                 }
 100             }),
 101         )
 102     }
 103 }
 104
 105 impl<'tcx> Ty<'tcx> {
 106     pub fn inhabited_predicate(self, tcx: TyCtxt<'tcx>) -> InhabitedPredicate<'tcx> {
 107         match self.kind() {
 108             // For now, union`s are always considered inhabited
 109             Adt(adt, _) if adt.is_union() => InhabitedPredicate::True,
 110             // Non-exhaustive ADTs from other crates are always considered inhabited
 111             Adt(adt, _) if adt.is_variant_list_non_exhaustive() && !adt.did().is_local() => {
 112                 InhabitedPredicate::True
 113             }
 114             Never => InhabitedPredicate::False,
 115             Param(_) | Alias(ty::Projection, _) => InhabitedPredicate::GenericType(self),
 116             Tuple(tys) if tys.is_empty() => InhabitedPredicate::True,
 117             // use a query for more complex cases
 118             Adt(..) | Array(..) | Tuple(_) => tcx.inhabited_predicate_type(self),
 119             // references and other types are inhabited
 120             _ => InhabitedPredicate::True,
 121         }
 122     }
 123
 124     /// Checks whether a type is visibly uninhabited from a particular module.
 125     ///
 126     /// # Example
 127     /// ```
 128     /// #![feature(never_type)]
 129     /// # fn main() {}
 130     /// enum Void {}
 131     /// mod a {
 132     ///     pub mod b {
 133     ///         pub struct SecretlyUninhabited {
 134     ///             _priv: !,
 135     ///         }
 136     ///     }
 137     /// }
 138     ///
 139     /// mod c {
 140     ///     use super::Void;
 141     ///     pub struct AlsoSecretlyUninhabited {
 142     ///         _priv: Void,
 143     ///     }
 144     ///     mod d {
 145     ///     }
 146     /// }
 147     ///
 148     /// struct Foo {
 149     ///     x: a::b::SecretlyUninhabited,
 150     ///     y: c::AlsoSecretlyUninhabited,
 151     /// }
 152     /// ```
 153     /// In this code, the type `Foo` will only be visibly uninhabited inside the
 154     /// modules b, c and d. This effects pattern-matching on `Foo` or types that
 155     /// contain `Foo`.
 156     ///
 157     /// # Example
 158     /// ```ignore (illustrative)
 159     /// let foo_result: Result<T, Foo> = ... ;
 160     /// let Ok(t) = foo_result;
 161     /// ```
 162     /// This code should only compile in modules where the uninhabitedness of Foo is
 163     /// visible.
 164     pub fn is_inhabited_from(
 165         self,
 166         tcx: TyCtxt<'tcx>,
 167         module: DefId,
 168         param_env: ty::ParamEnv<'tcx>,
 169     ) -> bool {
 170         self.inhabited_predicate(tcx).apply(tcx, param_env, module)
 171     }
 172
 173     /// Returns true if the type is uninhabited without regard to visibility
 174     pub fn is_privately_uninhabited(
 175         self,
 176         tcx: TyCtxt<'tcx>,
 177         param_env: ty::ParamEnv<'tcx>,
 178     ) -> bool {
 179         !self.inhabited_predicate(tcx).apply_ignore_module(tcx, param_env)
 180     }
 181 }
 182
 183 /// N.B. this query should only be called through `Ty::inhabited_predicate`
 184 fn inhabited_predicate_type<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> InhabitedPredicate<'tcx> {
 185     match *ty.kind() {
 186         Adt(adt, substs) => tcx.inhabited_predicate_adt(adt.did()).subst(tcx, substs),
 187
 188         Tuple(tys) => {
 189             InhabitedPredicate::all(tcx, tys.iter().map(|ty| ty.inhabited_predicate(tcx)))
 190         }
 191
 192         // If we can evaluate the array length before having a `ParamEnv`, then
 193         // we can simplify the predicate. This is an optimization.
 194         Array(ty, len) => match len.kind().try_to_machine_usize(tcx) {
 195             Some(0) => InhabitedPredicate::True,
 196             Some(1..) => ty.inhabited_predicate(tcx),
 197             None => ty.inhabited_predicate(tcx).or(tcx, InhabitedPredicate::ConstIsZero(len)),
 198         },
 199
 200         _ => bug!("unexpected TyKind, use `Ty::inhabited_predicate`"),
 201     }
 202 }