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, Ty, 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> TyCtxt<'a, 'gcx, 'tcx> {
66 /// Checks whether a type is visibly uninhabited from a particular module.
72 /// pub struct SecretlyUninhabited {
79 /// pub struct AlsoSecretlyUninhabited {
87 /// x: a::b::SecretlyUninhabited,
88 /// y: c::AlsoSecretlyUninhabited,
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
97 /// let foo_result: Result<T, Foo> = ... ;
98 /// let Ok(t) = foo_result;
100 /// This code should only compile in modules where the uninhabitedness of Foo is
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.
108 self.ty_inhabitedness_forest(ty).contains(self, module)
111 pub fn is_ty_uninhabited_from_all_modules(self, ty: Ty<'tcx>) -> bool {
112 !self.ty_inhabitedness_forest(ty).is_empty()
115 fn ty_inhabitedness_forest(self, ty: Ty<'tcx>) -> DefIdForest {
116 ty.uninhabited_from(&mut FxHashMap(), self)
119 pub fn is_enum_variant_uninhabited_from(self,
121 variant: &'tcx VariantDef,
122 substs: &'tcx Substs<'tcx>)
125 self.variant_inhabitedness_forest(variant, substs).contains(self, module)
128 pub fn is_variant_uninhabited_from_all_modules(self,
129 variant: &'tcx VariantDef,
130 substs: &'tcx Substs<'tcx>)
133 !self.variant_inhabitedness_forest(variant, substs).is_empty()
136 fn variant_inhabitedness_forest(self, variant: &'tcx VariantDef, substs: &'tcx Substs<'tcx>)
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();
142 // Compute inhabitedness forest:
143 variant.uninhabited_from(&mut FxHashMap(), self, substs, adt_kind)
147 impl<'a, 'gcx, 'tcx> AdtDef {
148 /// Calculate the forest of DefIds from which this adt is visibly uninhabited.
151 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
152 tcx: TyCtxt<'a, 'gcx, 'tcx>,
153 substs: &'tcx Substs<'tcx>) -> DefIdForest
155 DefIdForest::intersection(tcx, self.variants.iter().map(|v| {
156 v.uninhabited_from(visited, tcx, substs, self.adt_kind())
161 impl<'a, 'gcx, 'tcx> VariantDef {
162 /// Calculate the forest of DefIds from which this variant is visibly uninhabited.
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
172 DefIdForest::intersection(tcx, self.fields.iter().map(|f| {
173 f.uninhabited_from(visited, tcx, substs, false)
177 DefIdForest::union(tcx, self.fields.iter().map(|f| {
178 f.uninhabited_from(visited, tcx, substs, false)
182 DefIdForest::union(tcx, self.fields.iter().map(|f| {
183 f.uninhabited_from(visited, tcx, substs, true)
190 impl<'a, 'gcx, 'tcx> FieldDef {
191 /// Calculate the forest of DefIds from which this field is visibly uninhabited.
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
199 let mut data_uninhabitedness = move || {
200 self.ty(tcx, substs).uninhabited_from(visited, tcx)
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.
206 data_uninhabitedness()
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)
215 Visibility::Public => data_uninhabitedness(),
221 impl<'a, 'gcx, 'tcx> TyS<'tcx> {
222 /// Calculate the forest of DefIds from which this type is visibly uninhabited.
225 visited: &mut FxHashMap<DefId, FxHashSet<&'tcx Substs<'tcx>>>,
226 tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
229 TyAdt(def, substs) => {
231 let substs_set = visited.entry(def.did).or_insert(FxHashSet::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
236 return DefIdForest::empty();
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:
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)))>
247 let error = format!("reached recursion limit while checking \
248 inhabitedness of `{}`", self);
249 tcx.sess.fatal(&error);
252 let ret = def.uninhabited_from(visited, tcx, substs);
253 let substs_set = visited.get_mut(&def.did).unwrap();
254 substs_set.remove(substs);
258 TyNever => DefIdForest::full(tcx),
259 TyTuple(ref tys, _) => {
260 DefIdForest::union(tcx, tys.iter().map(|ty| {
261 ty.uninhabited_from(visited, tcx)
264 TyArray(ty, len) => {
265 if len.val.to_const_int().and_then(|i| i.to_u64()) == Some(0) {
268 ty.uninhabited_from(visited, tcx)
271 TyRef(_, ref tm) => {
272 tm.ty.uninhabited_from(visited, tcx)
275 _ => DefIdForest::empty(),