src/librustc/ty/inhabitedness/mod.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use util::nodemap::{FxHashMap, FxHashSet};
  12 use ty::context::TyCtxt;
  13 use ty::{AdtDef, VariantDef, FieldDef, Ty, TyS};
  14 use ty::{DefId, Substs};
  15 use ty::{AdtKind, Visibility};
  16 use ty::TyKind::*;
  17
  18 pub use self::def_id_forest::DefIdForest;
  19
  20 mod def_id_forest;
  21
  22 // The methods in this module calculate DefIdForests of modules in which a
  23 // AdtDef/VariantDef/FieldDef is visibly uninhabited.
  24 //
  25 // # Example
  26 // ```rust
  27 // enum Void {}
  28 // mod a {
  29 //     pub mod b {
  30 //         pub struct SecretlyUninhabited {
  31 //             _priv: !,
  32 //         }
  33 //     }
  34 // }
  35 //
  36 // mod c {
  37 //     pub struct AlsoSecretlyUninhabited {
  38 //         _priv: Void,
  39 //     }
  40 //     mod d {
  41 //     }
  42 // }
  43 //
  44 // struct Foo {
  45 //     x: a::b::SecretlyUninhabited,
  46 //     y: c::AlsoSecretlyUninhabited,
  47 // }
  48 // ```
  49 // In this code, the type Foo will only be visibly uninhabited inside the
  50 // modules b, c and d. Calling uninhabited_from on Foo or its AdtDef will
  51 // return the forest of modules {b, c->d} (represented in a DefIdForest by the
  52 // set {b, c})
  53 //
  54 // We need this information for pattern-matching on Foo or types that contain
  55 // Foo.
  56 //
  57 // # Example
  58 // ```rust
  59 // let foo_result: Result<T, Foo> = ... ;
  60 // let Ok(t) = foo_result;
  61 // ```
  62 // This code should only compile in modules where the uninhabitedness of Foo is
  63 // visible.
  64
  65 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
  66     /// Checks whether a type is visibly uninhabited from a particular module.
  67     /// # Example
  68     /// ```rust
  69     /// enum Void {}
  70     /// mod a {
  71     ///     pub mod b {
  72     ///         pub struct SecretlyUninhabited {
  73     ///             _priv: !,
  74     ///         }
  75     ///     }
  76     /// }
  77     ///
  78     /// mod c {
  79     ///     pub struct AlsoSecretlyUninhabited {
  80     ///         _priv: Void,
  81     ///     }
  82     ///     mod d {
  83     ///     }
  84     /// }
  85     ///
  86     /// struct Foo {
  87     ///     x: a::b::SecretlyUninhabited,
  88     ///     y: c::AlsoSecretlyUninhabited,
  89     /// }
  90     /// ```
  91     /// In this code, the type `Foo` will only be visibly uninhabited inside the
  92     /// modules b, c and d. This effects pattern-matching on `Foo` or types that
  93     /// contain `Foo`.
  94     ///
  95     /// # Example
  96     /// ```rust
  97     /// let foo_result: Result<T, Foo> = ... ;
  98     /// let Ok(t) = foo_result;
  99     /// ```
 100     /// This code should only compile in modules where the uninhabitedness of Foo is
 101     /// visible.
 102     pub fn is_ty_uninhabited_from(self, module: DefId, ty: Ty<'tcx>) -> bool {
 103         // To check whether this type is uninhabited at all (not just from the
 104         // given node) you could check whether the forest is empty.
 105         // ```
 106         // forest.is_empty()
 107         // ```
 108         self.ty_inhabitedness_forest(ty).contains(self, module)
 109     }
 110
 111     pub fn is_ty_uninhabited_from_all_modules(self, ty: Ty<'tcx>) -> bool {
 112         !self.ty_inhabitedness_forest(ty).is_empty()
 113     }
 114
 115     fn ty_inhabitedness_forest(self, ty: Ty<'tcx>) -> DefIdForest {
 116         ty.uninhabited_from(&mut FxHashMap::default(), self)
 117     }
 118
 119     pub fn is_enum_variant_uninhabited_from(self,
 120                                             module: DefId,
 121                                             variant: &'tcx VariantDef,
 122                                             substs: &'tcx Substs<'tcx>)
 123                                             -> bool
 124     {
 125         self.variant_inhabitedness_forest(variant, substs).contains(self, module)
 126     }
 127
 128     pub fn is_variant_uninhabited_from_all_modules(self,
 129                                                    variant: &'tcx VariantDef,
 130                                                    substs: &'tcx Substs<'tcx>)
 131                                                    -> bool
 132     {
 133         !self.variant_inhabitedness_forest(variant, substs).is_empty()
 134     }
 135
 136     fn variant_inhabitedness_forest(self, variant: &'tcx VariantDef, substs: &'tcx Substs<'tcx>)
 137                                     -> DefIdForest {
 138         // Determine the ADT kind:
 139         let adt_def_id = self.adt_def_id_of_variant(variant);
 140         let adt_kind = self.adt_def(adt_def_id).adt_kind();
 141
 142         // Compute inhabitedness forest:
 143         variant.uninhabited_from(&mut FxHashMap::default(), self, substs, adt_kind)
 144     }
 145 }
 146
 147 impl<'a, 'gcx, 'tcx> AdtDef {
 148     /// Calculate the forest of DefIds from which this adt is visibly uninhabited.
 149     fn uninhabited_from(
 150         &self,
 151         visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 152         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 153         substs: &'tcx Substs<'tcx>) -> DefIdForest
 154     {
 155         DefIdForest::intersection(tcx, self.variants.iter().map(|v| {
 156             v.uninhabited_from(visited, tcx, substs, self.adt_kind())
 157         }))
 158     }
 159 }
 160
 161 impl<'a, 'gcx, 'tcx> VariantDef {
 162     /// Calculate the forest of DefIds from which this variant is visibly uninhabited.
 163     fn uninhabited_from(
 164         &self,
 165         visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 166         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 167         substs: &'tcx Substs<'tcx>,
 168         adt_kind: AdtKind) -> DefIdForest
 169     {
 170         match adt_kind {
 171             AdtKind::Union => {
 172                 DefIdForest::intersection(tcx, self.fields.iter().map(|f| {
 173                     f.uninhabited_from(visited, tcx, substs, false)
 174                 }))
 175             },
 176             AdtKind::Struct => {
 177                 DefIdForest::union(tcx, self.fields.iter().map(|f| {
 178                     f.uninhabited_from(visited, tcx, substs, false)
 179                 }))
 180             },
 181             AdtKind::Enum => {
 182                 DefIdForest::union(tcx, self.fields.iter().map(|f| {
 183                     f.uninhabited_from(visited, tcx, substs, true)
 184                 }))
 185             },
 186         }
 187     }
 188 }
 189
 190 impl<'a, 'gcx, 'tcx> FieldDef {
 191     /// Calculate the forest of DefIds from which this field is visibly uninhabited.
 192     fn uninhabited_from(
 193         &self,
 194         visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 195         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 196         substs: &'tcx Substs<'tcx>,
 197         is_enum: bool) -> DefIdForest
 198     {
 199         let mut data_uninhabitedness = move || {
 200             self.ty(tcx, substs).uninhabited_from(visited, tcx)
 201         };
 202         // FIXME(canndrew): Currently enum fields are (incorrectly) stored with
 203         // Visibility::Invisible so we need to override self.vis if we're
 204         // dealing with an enum.
 205         if is_enum {
 206             data_uninhabitedness()
 207         } else {
 208             match self.vis {
 209                 Visibility::Invisible => DefIdForest::empty(),
 210                 Visibility::Restricted(from) => {
 211                     let forest = DefIdForest::from_id(from);
 212                     let iter = Some(forest).into_iter().chain(Some(data_uninhabitedness()));
 213                     DefIdForest::intersection(tcx, iter)
 214                 },
 215                 Visibility::Public => data_uninhabitedness(),
 216             }
 217         }
 218     }
 219 }
 220
 221 impl<'a, 'gcx, 'tcx> TyS<'tcx> {
 222     /// Calculate the forest of DefIds from which this type is visibly uninhabited.
 223     fn uninhabited_from(
 224         &self,
 225         visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 226         tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
 227     {
 228         match self.sty {
 229             Adt(def, substs) => {
 230                 {
 231                     let substs_set = visited.entry(def.did).or_default();
 232                     if !substs_set.insert(substs) {
 233                         // We are already calculating the inhabitedness of this type.
 234                         // The type must contain a reference to itself. Break the
 235                         // infinite loop.
 236                         return DefIdForest::empty();
 237                     }
 238                     if substs_set.len() >= tcx.sess.recursion_limit.get() / 4 {
 239                         // We have gone very deep, reinstantiating this ADT inside
 240                         // itself with different type arguments. We are probably
 241                         // hitting an infinite loop. For example, it's possible to write:
 242                         //                a type Foo<T>
 243                         //      which contains a Foo<(T, T)>
 244                         //      which contains a Foo<((T, T), (T, T))>
 245                         //      which contains a Foo<(((T, T), (T, T)), ((T, T), (T, T)))>
 246                         //      etc.
 247                         let error = format!("reached recursion limit while checking \
 248                                              inhabitedness of `{}`", self);
 249                         tcx.sess.fatal(&error);
 250                     }
 251                 }
 252                 let ret = def.uninhabited_from(visited, tcx, substs);
 253                 let substs_set = visited.get_mut(&def.did).unwrap();
 254                 substs_set.remove(substs);
 255                 ret
 256             },
 257
 258             Never => DefIdForest::full(tcx),
 259             Tuple(ref tys) => {
 260                 DefIdForest::union(tcx, tys.iter().map(|ty| {
 261                     ty.uninhabited_from(visited, tcx)
 262                 }))
 263             },
 264             Array(ty, len) => {
 265                 match len.assert_usize(tcx) {
 266                     // If the array is definitely non-empty, it's uninhabited if
 267                     // the type of its elements is uninhabited.
 268                     Some(n) if n != 0 => ty.uninhabited_from(visited, tcx),
 269                     _ => DefIdForest::empty()
 270                 }
 271             }
 272             Ref(_, ty, _) => {
 273                 ty.uninhabited_from(visited, tcx)
 274             }
 275
 276             _ => DefIdForest::empty(),
 277         }
 278     }
 279 }
 280