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.
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.
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::*;
18 pub use self::def_id_forest::DefIdForest;
22 // The methods in this module calculate DefIdForests of modules in which a
23 // AdtDef/VariantDef/FieldDef is visibly uninhabited.
30 // pub struct SecretlyUninhabited {
37 // pub struct AlsoSecretlyUninhabited {
45 // x: a::b::SecretlyUninhabited,
46 // y: c::AlsoSecretlyUninhabited,
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
54 // We need this information for pattern-matching on Foo or types that contain
59 // let foo_result: Result<T, Foo> = ... ;
60 // let Ok(t) = foo_result;
62 // This code should only compile in modules where the uninhabitedness of Foo is
65 impl<'a, 'gcx, 'tcx> AdtDef {
66 /// Calculate the forest of DefIds from which this adt is visibly uninhabited.
67 pub fn uninhabited_from(
69 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
70 tcx: TyCtxt<'a, 'gcx, 'tcx>,
71 substs: &'tcx Substs<'tcx>) -> DefIdForest
73 DefIdForest::intersection(tcx, self.variants.iter().map(|v| {
74 v.uninhabited_from(visited, tcx, substs, self.adt_kind())
79 impl<'a, 'gcx, 'tcx> VariantDef {
80 /// Calculate the forest of DefIds from which this variant is visibly uninhabited.
81 pub fn uninhabited_from(
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
90 DefIdForest::intersection(tcx, self.fields.iter().map(|f| {
91 f.uninhabited_from(visited, tcx, substs, false)
95 DefIdForest::union(tcx, self.fields.iter().map(|f| {
96 f.uninhabited_from(visited, tcx, substs, false)
100 DefIdForest::union(tcx, self.fields.iter().map(|f| {
101 f.uninhabited_from(visited, tcx, substs, true)
108 impl<'a, 'gcx, 'tcx> FieldDef {
109 /// Calculate the forest of DefIds from which this field is visibly uninhabited.
110 pub fn uninhabited_from(
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
117 let mut data_uninhabitedness = move || {
118 self.ty(tcx, substs).uninhabited_from(visited, tcx)
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.
124 data_uninhabitedness()
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)
133 Visibility::Public => data_uninhabitedness(),
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(
143 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
144 tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
146 match tcx.lift_to_global(&self) {
149 let cache = tcx.inhabitedness_cache.borrow();
150 if let Some(forest) = cache.get(&global_ty) {
151 return forest.clone();
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());
160 let forest = self.uninhabited_from_inner(visited, tcx);
166 fn uninhabited_from_inner(
168 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
169 tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
172 TyAdt(def, substs) => {
174 let 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
179 return DefIdForest::empty();
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:
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)))>
190 let error = format!("reached recursion limit while checking \
191 inhabitedness of `{}`", self);
192 tcx.sess.fatal(&error);
195 let ret = def.uninhabited_from(visited, tcx, substs);
196 let substs_set = visited.get_mut(&def.did).unwrap();
197 substs_set.remove(substs);
201 TyNever => DefIdForest::full(tcx),
202 TyTuple(ref tys, _) => {
203 DefIdForest::union(tcx, tys.iter().map(|ty| {
204 ty.uninhabited_from(visited, tcx)
207 TyArray(ty, len) => {
208 if len.val.to_const_int().and_then(|i| i.to_u64()) == Some(0) {
211 ty.uninhabited_from(visited, tcx)
214 TyRef(_, ref tm) => {
215 tm.ty.uninhabited_from(visited, tcx)
218 _ => DefIdForest::empty(),