compiler/rustc_middle/src/ty/inhabitedness/mod.rs

   1 pub use self::def_id_forest::DefIdForest;
   2
   3 use crate::ty;
   4 use crate::ty::context::TyCtxt;
   5 use crate::ty::TyKind::*;
   6 use crate::ty::{AdtDef, FieldDef, Ty, TyS, VariantDef};
   7 use crate::ty::{AdtKind, Visibility};
   8 use crate::ty::{DefId, SubstsRef};
   9 use rustc_data_structures::stack::ensure_sufficient_stack;
  10
  11 mod def_id_forest;
  12
  13 // The methods in this module calculate `DefIdForest`s of modules in which a
  14 // `AdtDef`/`VariantDef`/`FieldDef` is visibly uninhabited.
  15 //
  16 // # Example
  17 // ```rust
  18 // enum Void {}
  19 // mod a {
  20 //     pub mod b {
  21 //         pub struct SecretlyUninhabited {
  22 //             _priv: !,
  23 //         }
  24 //     }
  25 // }
  26 //
  27 // mod c {
  28 //     pub struct AlsoSecretlyUninhabited {
  29 //         _priv: Void,
  30 //     }
  31 //     mod d {
  32 //     }
  33 // }
  34 //
  35 // struct Foo {
  36 //     x: a::b::SecretlyUninhabited,
  37 //     y: c::AlsoSecretlyUninhabited,
  38 // }
  39 // ```
  40 // In this code, the type `Foo` will only be visibly uninhabited inside the
  41 // modules `b`, `c` and `d`. Calling `uninhabited_from` on `Foo` or its `AdtDef` will
  42 // return the forest of modules {`b`, `c`->`d`} (represented in a `DefIdForest` by the
  43 // set {`b`, `c`}).
  44 //
  45 // We need this information for pattern-matching on `Foo` or types that contain
  46 // `Foo`.
  47 //
  48 // # Example
  49 // ```rust
  50 // let foo_result: Result<T, Foo> = ... ;
  51 // let Ok(t) = foo_result;
  52 // ```
  53 // This code should only compile in modules where the uninhabitedness of `Foo` is
  54 // visible.
  55
  56 impl<'tcx> TyCtxt<'tcx> {
  57     /// Checks whether a type is visibly uninhabited from a particular module.
  58     ///
  59     /// # Example
  60     /// ```rust
  61     /// enum Void {}
  62     /// mod a {
  63     ///     pub mod b {
  64     ///         pub struct SecretlyUninhabited {
  65     ///             _priv: !,
  66     ///         }
  67     ///     }
  68     /// }
  69     ///
  70     /// mod c {
  71     ///     pub struct AlsoSecretlyUninhabited {
  72     ///         _priv: Void,
  73     ///     }
  74     ///     mod d {
  75     ///     }
  76     /// }
  77     ///
  78     /// struct Foo {
  79     ///     x: a::b::SecretlyUninhabited,
  80     ///     y: c::AlsoSecretlyUninhabited,
  81     /// }
  82     /// ```
  83     /// In this code, the type `Foo` will only be visibly uninhabited inside the
  84     /// modules b, c and d. This effects pattern-matching on `Foo` or types that
  85     /// contain `Foo`.
  86     ///
  87     /// # Example
  88     /// ```rust
  89     /// let foo_result: Result<T, Foo> = ... ;
  90     /// let Ok(t) = foo_result;
  91     /// ```
  92     /// This code should only compile in modules where the uninhabitedness of Foo is
  93     /// visible.
  94     pub fn is_ty_uninhabited_from(
  95         self,
  96         module: DefId,
  97         ty: Ty<'tcx>,
  98         param_env: ty::ParamEnv<'tcx>,
  99     ) -> bool {
 100         // To check whether this type is uninhabited at all (not just from the
 101         // given node), you could check whether the forest is empty.
 102         // ```
 103         // forest.is_empty()
 104         // ```
 105         ty.uninhabited_from(self, param_env).contains(self, module)
 106     }
 107
 108     pub fn is_ty_uninhabited_from_any_module(
 109         self,
 110         ty: Ty<'tcx>,
 111         param_env: ty::ParamEnv<'tcx>,
 112     ) -> bool {
 113         !ty.uninhabited_from(self, param_env).is_empty()
 114     }
 115 }
 116
 117 impl<'tcx> AdtDef {
 118     /// Calculates the forest of `DefId`s from which this ADT is visibly uninhabited.
 119     fn uninhabited_from(
 120         &self,
 121         tcx: TyCtxt<'tcx>,
 122         substs: SubstsRef<'tcx>,
 123         param_env: ty::ParamEnv<'tcx>,
 124     ) -> DefIdForest {
 125         // Non-exhaustive ADTs from other crates are always considered inhabited.
 126         if self.is_variant_list_non_exhaustive() && !self.did.is_local() {
 127             DefIdForest::empty()
 128         } else {
 129             DefIdForest::intersection(
 130                 tcx,
 131                 self.variants
 132                     .iter()
 133                     .map(|v| v.uninhabited_from(tcx, substs, self.adt_kind(), param_env)),
 134             )
 135         }
 136     }
 137 }
 138
 139 impl<'tcx> VariantDef {
 140     /// Calculates the forest of `DefId`s from which this variant is visibly uninhabited.
 141     pub fn uninhabited_from(
 142         &self,
 143         tcx: TyCtxt<'tcx>,
 144         substs: SubstsRef<'tcx>,
 145         adt_kind: AdtKind,
 146         param_env: ty::ParamEnv<'tcx>,
 147     ) -> DefIdForest {
 148         let is_enum = match adt_kind {
 149             // For now, `union`s are never considered uninhabited.
 150             // The precise semantics of inhabitedness with respect to unions is currently undecided.
 151             AdtKind::Union => return DefIdForest::empty(),
 152             AdtKind::Enum => true,
 153             AdtKind::Struct => false,
 154         };
 155         // Non-exhaustive variants from other crates are always considered inhabited.
 156         if self.is_field_list_non_exhaustive() && !self.def_id.is_local() {
 157             DefIdForest::empty()
 158         } else {
 159             DefIdForest::union(
 160                 tcx,
 161                 self.fields.iter().map(|f| f.uninhabited_from(tcx, substs, is_enum, param_env)),
 162             )
 163         }
 164     }
 165 }
 166
 167 impl<'tcx> FieldDef {
 168     /// Calculates the forest of `DefId`s from which this field is visibly uninhabited.
 169     fn uninhabited_from(
 170         &self,
 171         tcx: TyCtxt<'tcx>,
 172         substs: SubstsRef<'tcx>,
 173         is_enum: bool,
 174         param_env: ty::ParamEnv<'tcx>,
 175     ) -> DefIdForest {
 176         let data_uninhabitedness = move || self.ty(tcx, substs).uninhabited_from(tcx, param_env);
 177         // FIXME(canndrew): Currently enum fields are (incorrectly) stored with
 178         // `Visibility::Invisible` so we need to override `self.vis` if we're
 179         // dealing with an enum.
 180         if is_enum {
 181             data_uninhabitedness()
 182         } else {
 183             match self.vis {
 184                 Visibility::Invisible => DefIdForest::empty(),
 185                 Visibility::Restricted(from) => {
 186                     let forest = DefIdForest::from_id(from);
 187                     let iter = Some(forest).into_iter().chain(Some(data_uninhabitedness()));
 188                     DefIdForest::intersection(tcx, iter)
 189                 }
 190                 Visibility::Public => data_uninhabitedness(),
 191             }
 192         }
 193     }
 194 }
 195
 196 impl<'tcx> TyS<'tcx> {
 197     /// Calculates the forest of `DefId`s from which this type is visibly uninhabited.
 198     fn uninhabited_from(&self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> DefIdForest {
 199         match *self.kind() {
 200             Adt(def, substs) => {
 201                 ensure_sufficient_stack(|| def.uninhabited_from(tcx, substs, param_env))
 202             }
 203
 204             Never => DefIdForest::full(tcx),
 205
 206             Tuple(ref tys) => DefIdForest::union(
 207                 tcx,
 208                 tys.iter().map(|ty| ty.expect_ty().uninhabited_from(tcx, param_env)),
 209             ),
 210
 211             Array(ty, len) => match len.try_eval_usize(tcx, param_env) {
 212                 // If the array is definitely non-empty, it's uninhabited if
 213                 // the type of its elements is uninhabited.
 214                 Some(n) if n != 0 => ty.uninhabited_from(tcx, param_env),
 215                 _ => DefIdForest::empty(),
 216             },
 217
 218             // References to uninitialised memory is valid for any type, including
 219             // uninhabited types, in unsafe code, so we treat all references as
 220             // inhabited.
 221             // The precise semantics of inhabitedness with respect to references is currently
 222             // undecided.
 223             Ref(..) => DefIdForest::empty(),
 224
 225             _ => DefIdForest::empty(),
 226         }
 227     }
 228 }