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, TyS};
  14 use ty::{DefId, Substs};
  15 use ty::{AdtKind, Visibility};
  16 use ty::TypeVariants::*;
  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> AdtDef {
  66     /// Calculate the forest of DefIds from which this adt is visibly uninhabited.
  67     pub fn uninhabited_from(
  68                 &self,
  69                 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
  70                 tcx: TyCtxt<'a, 'gcx, 'tcx>,
  71                 substs: &'tcx Substs<'tcx>) -> DefIdForest
  72     {
  73         DefIdForest::intersection(tcx, self.variants.iter().map(|v| {
  74             v.uninhabited_from(visited, tcx, substs, self.adt_kind())
  75         }))
  76     }
  77 }
  78
  79 impl<'a, 'gcx, 'tcx> VariantDef {
  80     /// Calculate the forest of DefIds from which this variant is visibly uninhabited.
  81     pub fn uninhabited_from(
  82                 &self,
  83                 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
  84                 tcx: TyCtxt<'a, 'gcx, 'tcx>,
  85                 substs: &'tcx Substs<'tcx>,
  86                 adt_kind: AdtKind) -> DefIdForest
  87     {
  88         match adt_kind {
  89             AdtKind::Union => {
  90                 DefIdForest::intersection(tcx, self.fields.iter().map(|f| {
  91                     f.uninhabited_from(visited, tcx, substs, false)
  92                 }))
  93             },
  94             AdtKind::Struct => {
  95                 DefIdForest::union(tcx, self.fields.iter().map(|f| {
  96                     f.uninhabited_from(visited, tcx, substs, false)
  97                 }))
  98             },
  99             AdtKind::Enum => {
 100                 DefIdForest::union(tcx, self.fields.iter().map(|f| {
 101                     f.uninhabited_from(visited, tcx, substs, true)
 102                 }))
 103             },
 104         }
 105     }
 106 }
 107
 108 impl<'a, 'gcx, 'tcx> FieldDef {
 109     /// Calculate the forest of DefIds from which this field is visibly uninhabited.
 110     pub fn uninhabited_from(
 111                 &self,
 112                 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 113                 tcx: TyCtxt<'a, 'gcx, 'tcx>,
 114                 substs: &'tcx Substs<'tcx>,
 115                 is_enum: bool) -> DefIdForest
 116     {
 117         let mut data_uninhabitedness = move || {
 118             self.ty(tcx, substs).uninhabited_from(visited, tcx)
 119         };
 120         // FIXME(canndrew): Currently enum fields are (incorrectly) stored with
 121         // Visibility::Invisible so we need to override self.vis if we're
 122         // dealing with an enum.
 123         if is_enum {
 124             data_uninhabitedness()
 125         } else {
 126             match self.vis {
 127                 Visibility::Invisible => DefIdForest::empty(),
 128                 Visibility::Restricted(from) => {
 129                     let forest = DefIdForest::from_id(from);
 130                     let iter = Some(forest).into_iter().chain(Some(data_uninhabitedness()));
 131                     DefIdForest::intersection(tcx, iter)
 132                 },
 133                 Visibility::Public => data_uninhabitedness(),
 134             }
 135         }
 136     }
 137 }
 138
 139 impl<'a, 'gcx, 'tcx> TyS<'tcx> {
 140     /// Calculate the forest of DefIds from which this type is visibly uninhabited.
 141     pub fn uninhabited_from(
 142                 &self,
 143                 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 144                 tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
 145     {
 146         match tcx.lift_to_global(&self) {
 147             Some(global_ty) => {
 148                 {
 149                     let cache = tcx.inhabitedness_cache.borrow();
 150                     if let Some(forest) = cache.get(&global_ty) {
 151                         return forest.clone();
 152                     }
 153                 }
 154                 let forest = global_ty.uninhabited_from_inner(visited, tcx);
 155                 let mut cache = tcx.inhabitedness_cache.borrow_mut();
 156                 cache.insert(global_ty, forest.clone());
 157                 forest
 158             },
 159             None => {
 160                 let forest = self.uninhabited_from_inner(visited, tcx);
 161                 forest
 162             },
 163         }
 164     }
 165
 166     fn uninhabited_from_inner(
 167                 &self,
 168                 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
 169                 tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
 170     {
 171         match self.sty {
 172             TyAdt(def, substs) => {
 173                 {
 174                     let mut substs_set = visited.entry(def.did).or_insert(FxHashSet::default());
 175                     if !substs_set.insert(substs) {
 176                         // We are already calculating the inhabitedness of this type.
 177                         // The type must contain a reference to itself. Break the
 178                         // infinite loop.
 179                         return DefIdForest::empty();
 180                     }
 181                     if substs_set.len() >= tcx.sess.recursion_limit.get() / 4 {
 182                         // We have gone very deep, reinstantiating this ADT inside
 183                         // itself with different type arguments. We are probably
 184                         // hitting an infinite loop. For example, it's possible to write:
 185                         //                a type Foo<T>
 186                         //      which contains a Foo<(T, T)>
 187                         //      which contains a Foo<((T, T), (T, T))>
 188                         //      which contains a Foo<(((T, T), (T, T)), ((T, T), (T, T)))>
 189                         //      etc.
 190                         let error = format!("reached recursion limit while checking \
 191                                              inhabitedness of `{}`", self);
 192                         tcx.sess.fatal(&error);
 193                     }
 194                 }
 195                 let ret = def.uninhabited_from(visited, tcx, substs);
 196                 let mut substs_set = visited.get_mut(&def.did).unwrap();
 197                 substs_set.remove(substs);
 198                 ret
 199             },
 200
 201             TyNever => DefIdForest::full(tcx),
 202             TyTuple(ref tys, _) => {
 203                 DefIdForest::union(tcx, tys.iter().map(|ty| {
 204                     ty.uninhabited_from(visited, tcx)
 205                 }))
 206             },
 207             TyArray(ty, len) => {
 208                 if len == 0 {
 209                     DefIdForest::empty()
 210                 } else {
 211                     ty.uninhabited_from(visited, tcx)
 212                 }
 213             }
 214             TyRef(_, ref tm) => {
 215                 tm.ty.uninhabited_from(visited, tcx)
 216             }
 217
 218             _ => DefIdForest::empty(),
 219         }
 220     }
 221 }
 222