1 // Copyright 2013 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.
13 use rustc::hir::def_id::DefId;
14 use rustc::hir::itemlikevisit::ItemLikeVisitor;
15 use rustc::ty::subst::{Kind, Subst, UnpackedKind};
16 use rustc::ty::{self, Ty, TyCtxt};
17 use rustc::util::nodemap::FxHashMap;
19 use super::explicit::ExplicitPredicatesMap;
22 /// Infer predicates for the items in the crate.
24 /// global_inferred_outlives: this is initially the empty map that
25 /// was generated by walking the items in the crate. This will
26 /// now be filled with inferred predicates.
27 pub fn infer_predicates<'tcx>(
28 tcx: TyCtxt<'_, 'tcx, 'tcx>,
29 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
30 ) -> FxHashMap<DefId, RequiredPredicates<'tcx>> {
31 debug!("infer_predicates");
33 let mut predicates_added = true;
35 let mut global_inferred_outlives = FxHashMap::default();
37 // If new predicates were added then we need to re-calculate
38 // all crates since there could be new implied predicates.
39 while predicates_added {
40 predicates_added = false;
42 let mut visitor = InferVisitor {
44 global_inferred_outlives: &mut global_inferred_outlives,
45 predicates_added: &mut predicates_added,
46 explicit_map: explicit_map,
49 // Visit all the crates and infer predicates
50 tcx.hir.krate().visit_all_item_likes(&mut visitor);
53 global_inferred_outlives
56 pub struct InferVisitor<'cx, 'tcx: 'cx> {
57 tcx: TyCtxt<'cx, 'tcx, 'tcx>,
58 global_inferred_outlives: &'cx mut FxHashMap<DefId, RequiredPredicates<'tcx>>,
59 predicates_added: &'cx mut bool,
60 explicit_map: &'cx mut ExplicitPredicatesMap<'tcx>,
63 impl<'cx, 'tcx> ItemLikeVisitor<'tcx> for InferVisitor<'cx, 'tcx> {
64 fn visit_item(&mut self, item: &hir::Item) {
65 let item_did = self.tcx.hir.local_def_id(item.id);
67 debug!("InferVisitor::visit_item(item={:?})", item_did);
72 .as_local_node_id(item_did)
73 .expect("expected local def-id");
74 let item = match self.tcx.hir.get(node_id) {
75 Node::Item(item) => item,
79 let mut item_required_predicates = RequiredPredicates::default();
81 hir::ItemKind::Union(..) | hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) => {
82 let adt_def = self.tcx.adt_def(item_did);
84 // Iterate over all fields in item_did
85 for field_def in adt_def.all_fields() {
86 // Calculating the predicate requirements necessary
89 // For field of type &'a T (reference) or Adt
90 // (struct/enum/union) there will be outlive
91 // requirements for adt_def.
92 let field_ty = self.tcx.type_of(field_def.did);
93 insert_required_predicates_to_be_wf(
96 self.global_inferred_outlives,
97 &mut item_required_predicates,
98 &mut self.explicit_map,
106 // If new predicates were added (`local_predicate_map` has more
107 // predicates than the `global_inferred_outlives`), the new predicates
108 // might result in implied predicates for their parent types.
109 // Therefore mark `predicates_added` as true and which will ensure
110 // we walk the crates again and re-calculate predicates for all
112 let item_predicates_len: usize = self
113 .global_inferred_outlives
117 if item_required_predicates.len() > item_predicates_len {
118 *self.predicates_added = true;
119 self.global_inferred_outlives
120 .insert(item_did, item_required_predicates);
124 fn visit_trait_item(&mut self, _trait_item: &'tcx hir::TraitItem) {}
126 fn visit_impl_item(&mut self, _impl_item: &'tcx hir::ImplItem) {}
129 fn insert_required_predicates_to_be_wf<'tcx>(
130 tcx: TyCtxt<'_, 'tcx, 'tcx>,
132 global_inferred_outlives: &FxHashMap<DefId, RequiredPredicates<'tcx>>,
133 required_predicates: &mut RequiredPredicates<'tcx>,
134 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
136 for ty in field_ty.walk() {
138 // The field is of type &'a T which means that we will have
139 // a predicate requirement of T: 'a (T outlives 'a).
141 // We also want to calculate potential predicates for the T
142 ty::Ref(region, rty, _) => {
144 insert_outlives_predicate(tcx, rty.into(), region, required_predicates);
147 // For each Adt (struct/enum/union) type `Foo<'a, T>`, we
148 // can load the current set of inferred and explicit
149 // predicates from `global_inferred_outlives` and filter the
150 // ones that are TypeOutlives.
151 ty::Adt(def, substs) => {
152 // First check the inferred predicates
156 // struct Foo<'a, T> {
157 // field1: Bar<'a, T>
160 // struct Bar<'b, U> {
164 // Here, when processing the type of `field1`, we would
165 // request the set of implicit predicates computed for `Bar`
166 // thus far. This will initially come back empty, but in next
167 // round we will get `U: 'b`. We then apply the substitution
168 // `['b => 'a, U => T]` and thus get the requirement that `T:
169 // 'a` holds for `Foo`.
171 if let Some(unsubstituted_predicates) = global_inferred_outlives.get(&def.did) {
172 for unsubstituted_predicate in unsubstituted_predicates {
173 // `unsubstituted_predicate` is `U: 'b` in the
174 // example above. So apply the substitution to
175 // get `T: 'a` (or `predicate`):
176 let predicate = unsubstituted_predicate.subst(tcx, substs);
177 insert_outlives_predicate(
186 // Check if the type has any explicit predicates that need
187 // to be added to `required_predicates`
188 // let _: () = substs.region_at(0);
189 check_explicit_predicates(
199 ty::Dynamic(obj, ..) => {
200 // This corresponds to `dyn Trait<..>`. In this case, we should
201 // use the explicit predicates as well.
204 debug!("field_ty = {}", &field_ty);
205 debug!("ty in field = {}", &ty);
206 if let Some(ex_trait_ref) = obj.principal() {
207 // Here, we are passing the type `usize` as a
208 // placeholder value with the function
209 // `with_self_ty`, since there is no concrete type
210 // `Self` for a `dyn Trait` at this
211 // stage. Therefore when checking explicit
212 // predicates in `check_explicit_predicates` we
213 // need to ignore checking the explicit_map for
215 let substs = ex_trait_ref
216 .with_self_ty(tcx, tcx.types.usize)
219 check_explicit_predicates(
221 &ex_trait_ref.skip_binder().def_id,
230 ty::Projection(obj) => {
231 // This corresponds to `<T as Foo<'a>>::Bar`. In this case, we should use the
232 // explicit predicates as well.
233 debug!("Projection");
234 check_explicit_predicates(
236 &tcx.associated_item(obj.item_def_id).container.id(),
249 pub struct IgnoreSelfTy(bool);
251 /// We also have to check the explicit predicates
252 /// declared on the type.
254 /// struct Foo<'a, T> {
258 /// struct Bar<U> where U: 'static, U: Foo {
262 /// Here, we should fetch the explicit predicates, which
263 /// will give us `U: 'static` and `U: Foo`. The latter we
264 /// can ignore, but we will want to process `U: 'static`,
265 /// applying the substitution as above.
266 pub fn check_explicit_predicates<'tcx>(
267 tcx: TyCtxt<'_, 'tcx, 'tcx>,
269 substs: &[Kind<'tcx>],
270 required_predicates: &mut RequiredPredicates<'tcx>,
271 explicit_map: &mut ExplicitPredicatesMap<'tcx>,
272 ignore_self_ty: IgnoreSelfTy,
274 debug!("def_id = {:?}", &def_id);
275 debug!("substs = {:?}", &substs);
276 debug!("explicit_map = {:?}", explicit_map);
277 debug!("required_predicates = {:?}", required_predicates);
278 let explicit_predicates = explicit_map.explicit_predicates_of(tcx, *def_id);
280 for outlives_predicate in explicit_predicates.iter() {
281 debug!("outlives_predicate = {:?}", &outlives_predicate);
283 // Careful: If we are inferring the effects of a `dyn Trait<..>`
284 // type, then when we look up the predicates for `Trait`,
285 // we may find some that reference `Self`. e.g., perhaps the
286 // definition of `Trait` was:
289 // trait Trait<'a, T> where Self: 'a { .. }
292 // we want to ignore such predicates here, because
293 // there is no type parameter for them to affect. Consider
294 // a struct containing `dyn Trait`:
297 // struct MyStruct<'x, X> { field: Box<dyn Trait<'x, X>> }
300 // The `where Self: 'a` predicate refers to the *existential, hidden type*
301 // that is represented by the `dyn Trait`, not to the `X` type parameter
302 // (or any other generic parameter) declared on `MyStruct`.
304 // Note that we do this check for self **before** applying `substs`. In the
305 // case that `substs` come from a `dyn Trait` type, our caller will have
306 // included `Self = dyn Trait<'x, X>` as the value for `Self`. If we were
307 // to apply the substs, and not filter this predicate, we might then falsely
308 // conclude that e.g. `X: 'x` was a reasonable inferred requirement.
309 if let UnpackedKind::Type(ty) = outlives_predicate.0.unpack() {
310 if ty.is_self() && ignore_self_ty.0 {
311 debug!("skipping self ty = {:?}", &ty);
316 let predicate = outlives_predicate.subst(tcx, substs);
317 debug!("predicate = {:?}", &predicate);
318 insert_outlives_predicate(tcx, predicate.0.into(), predicate.1, required_predicates);