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