1 // Copyright 2012 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 // #![warn(deprecated_mode)]
13 use middle::infer::{InferCtxt, GenericKind};
14 use middle::subst::Substs;
16 use middle::ty::{self, RegionEscape, ToPolyTraitRef, ToPredicate, Ty};
17 use middle::ty_fold::{TypeFoldable, TypeFolder};
20 use syntax::codemap::Span;
22 use util::common::ErrorReported;
23 use util::nodemap::FnvHashSet;
25 // Helper functions related to manipulating region types.
28 pub enum Implication<'tcx> {
29 RegionSubRegion(Option<Ty<'tcx>>, ty::Region, ty::Region),
30 RegionSubGeneric(Option<Ty<'tcx>>, ty::Region, GenericKind<'tcx>),
31 Predicate(ast::DefId, ty::Predicate<'tcx>),
34 struct Implicator<'a, 'tcx: 'a> {
35 infcx: &'a InferCtxt<'a,'tcx>,
37 stack: Vec<(ty::Region, Option<Ty<'tcx>>)>,
39 out: Vec<Implication<'tcx>>,
40 visited: FnvHashSet<Ty<'tcx>>,
43 /// This routine computes the well-formedness constraints that must hold for the type `ty` to
44 /// appear in a context with lifetime `outer_region`
45 pub fn implications<'a,'tcx>(
46 infcx: &'a InferCtxt<'a,'tcx>,
49 outer_region: ty::Region,
51 -> Vec<Implication<'tcx>>
53 debug!("implications(body_id={}, ty={:?}, outer_region={:?})",
58 let mut stack = Vec::new();
59 stack.push((outer_region, None));
60 let mut wf = Implicator { infcx: infcx,
65 visited: FnvHashSet() };
66 wf.accumulate_from_ty(ty);
67 debug!("implications: out={:?}", wf.out);
71 impl<'a, 'tcx> Implicator<'a, 'tcx> {
72 fn tcx(&self) -> &'a ty::ctxt<'tcx> {
76 fn accumulate_from_ty(&mut self, ty: Ty<'tcx>) {
77 debug!("accumulate_from_ty(ty={:?})",
80 // When expanding out associated types, we can visit a cyclic
81 // set of types. Issue #23003.
82 if !self.visited.insert(ty) {
95 // No borrowed content reachable here.
98 ty::TyClosure(_, ref substs) => {
99 // FIXME(#27086). We do not accumulate from substs, since they
100 // don't represent reachable data. This means that, in
101 // practice, some of the lifetime parameters might not
102 // be in scope when the body runs, so long as there is
103 // no reachable data with that lifetime. For better or
104 // worse, this is consistent with fn types, however,
105 // which can also encapsulate data in this fashion
106 // (though it's somewhat harder, and typically
107 // requires virtual dispatch).
109 // Note that changing this (in a naive way, at least)
110 // causes regressions for what appears to be perfectly
111 // reasonable code like this:
114 // fn foo<'a>(p: &Data<'a>) {
115 // bar(|q: &mut Parser| q.read_addr())
117 // fn bar(p: Box<FnMut(&mut Parser)+'static>) {
121 // Note that `p` (and `'a`) are not used in the
122 // closure at all, but to meet the requirement that
123 // the closure type `C: 'static` (so it can be coerced
124 // to the object type), we get the requirement that
125 // `'a: 'static` since `'a` appears in the closure
128 // A smarter fix might "prune" unused `func_substs` --
129 // this would avoid breaking simple examples like
130 // this, but would still break others (which might
131 // indeed be invalid, depending on your POV). Pruning
132 // would be a subtle process, since we have to see
133 // what func/type parameters are used and unused,
134 // taking into consideration UFCS and so forth.
136 for &upvar_ty in &substs.upvar_tys {
137 self.accumulate_from_ty(upvar_ty);
141 ty::TyTrait(ref t) => {
142 let required_region_bounds =
143 object_region_bounds(self.tcx(), &t.principal, t.bounds.builtin_bounds);
144 self.accumulate_from_object_ty(ty, t.bounds.region_bound, required_region_bounds)
147 ty::TyEnum(def, substs) |
148 ty::TyStruct(def, substs) => {
149 let item_scheme = def.type_scheme(self.tcx());
150 self.accumulate_from_adt(ty, def.did, &item_scheme.generics, substs)
155 ty::TyRawPtr(ty::TypeAndMut { ty: t, .. }) |
157 self.accumulate_from_ty(t)
160 ty::TyRef(r_b, mt) => {
161 self.accumulate_from_rptr(ty, *r_b, mt.ty);
165 self.push_param_constraint_from_top(p);
168 ty::TyProjection(ref data) => {
169 // `<T as TraitRef<..>>::Name`
171 self.push_projection_constraint_from_top(data);
174 ty::TyTuple(ref tuptys) => {
175 for &tupty in tuptys {
176 self.accumulate_from_ty(tupty);
181 // This should not happen, BUT:
183 // Currently we uncover region relationships on
184 // entering the fn check. We should do this after
185 // the fn check, then we can call this case a bug().
190 fn accumulate_from_rptr(&mut self,
194 // We are walking down a type like this, and current
195 // position is indicated by caret:
200 // At this point, top of stack will be `'a`. We must
201 // require that `'a <= 'b`.
203 self.push_region_constraint_from_top(r_b);
205 // Now we push `'b` onto the stack, because it must
206 // constrain any borrowed content we find within `T`.
208 self.stack.push((r_b, Some(ty)));
209 self.accumulate_from_ty(ty_b);
210 self.stack.pop().unwrap();
213 /// Pushes a constraint that `r_b` must outlive the top region on the stack.
214 fn push_region_constraint_from_top(&mut self,
217 // Indicates that we have found borrowed content with a lifetime
218 // of at least `r_b`. This adds a constraint that `r_b` must
219 // outlive the region `r_a` on top of the stack.
221 // As an example, imagine walking a type like:
226 // when we hit the inner pointer (indicated by caret), `'a` will
227 // be on top of stack and `'b` will be the lifetime of the content
228 // we just found. So we add constraint that `'a <= 'b`.
230 let &(r_a, opt_ty) = self.stack.last().unwrap();
231 self.push_sub_region_constraint(opt_ty, r_a, r_b);
234 /// Pushes a constraint that `r_a <= r_b`, due to `opt_ty`
235 fn push_sub_region_constraint(&mut self,
236 opt_ty: Option<Ty<'tcx>>,
239 self.out.push(Implication::RegionSubRegion(opt_ty, r_a, r_b));
242 /// Pushes a constraint that `param_ty` must outlive the top region on the stack.
243 fn push_param_constraint_from_top(&mut self,
244 param_ty: ty::ParamTy) {
245 let &(region, opt_ty) = self.stack.last().unwrap();
246 self.push_param_constraint(region, opt_ty, param_ty);
249 /// Pushes a constraint that `projection_ty` must outlive the top region on the stack.
250 fn push_projection_constraint_from_top(&mut self,
251 projection_ty: &ty::ProjectionTy<'tcx>) {
252 let &(region, opt_ty) = self.stack.last().unwrap();
253 self.out.push(Implication::RegionSubGeneric(
254 opt_ty, region, GenericKind::Projection(projection_ty.clone())));
257 /// Pushes a constraint that `region <= param_ty`, due to `opt_ty`
258 fn push_param_constraint(&mut self,
260 opt_ty: Option<Ty<'tcx>>,
261 param_ty: ty::ParamTy) {
262 self.out.push(Implication::RegionSubGeneric(
263 opt_ty, region, GenericKind::Param(param_ty)));
266 fn accumulate_from_adt(&mut self,
269 _generics: &ty::Generics<'tcx>,
270 substs: &Substs<'tcx>)
273 self.tcx().lookup_predicates(def_id).instantiate(self.tcx(), substs);
274 let predicates = match self.fully_normalize(&predicates) {
275 Ok(predicates) => predicates,
276 Err(ErrorReported) => { return; }
279 for predicate in predicates.predicates.as_slice() {
281 ty::Predicate::Trait(ref data) => {
282 self.accumulate_from_assoc_types_transitive(data);
284 ty::Predicate::Equate(..) => { }
285 ty::Predicate::Projection(..) => { }
286 ty::Predicate::RegionOutlives(ref data) => {
287 match self.tcx().no_late_bound_regions(data) {
289 Some(ty::OutlivesPredicate(r_a, r_b)) => {
290 self.push_sub_region_constraint(Some(ty), r_b, r_a);
294 ty::Predicate::TypeOutlives(ref data) => {
295 match self.tcx().no_late_bound_regions(data) {
297 Some(ty::OutlivesPredicate(ty_a, r_b)) => {
298 self.stack.push((r_b, Some(ty)));
299 self.accumulate_from_ty(ty_a);
300 self.stack.pop().unwrap();
307 let obligations = predicates.predicates
309 .map(|pred| Implication::Predicate(def_id, pred));
310 self.out.extend(obligations);
312 let variances = self.tcx().item_variances(def_id);
313 self.accumulate_from_substs(substs, Some(&variances));
316 fn accumulate_from_substs(&mut self,
317 substs: &Substs<'tcx>,
318 variances: Option<&ty::ItemVariances>)
320 let mut tmp_variances = None;
321 let variances = variances.unwrap_or_else(|| {
322 tmp_variances = Some(ty::ItemVariances {
323 types: substs.types.map(|_| ty::Variance::Invariant),
324 regions: substs.regions().map(|_| ty::Variance::Invariant),
326 tmp_variances.as_ref().unwrap()
329 for (®ion, &variance) in substs.regions().iter().zip(&variances.regions) {
331 ty::Contravariant | ty::Invariant => {
332 // If any data with this lifetime is reachable
333 // within, it must be at least contravariant.
334 self.push_region_constraint_from_top(region)
336 ty::Covariant | ty::Bivariant => { }
340 for (&ty, &variance) in substs.types.iter().zip(&variances.types) {
342 ty::Covariant | ty::Invariant => {
343 // If any data of this type is reachable within,
344 // it must be at least covariant.
345 self.accumulate_from_ty(ty);
347 ty::Contravariant | ty::Bivariant => { }
352 /// Given that there is a requirement that `Foo<X> : 'a`, where
353 /// `Foo` is declared like `struct Foo<T> where T : SomeTrait`,
354 /// this code finds all the associated types defined in
355 /// `SomeTrait` (and supertraits) and adds a requirement that `<X
356 /// as SomeTrait>::N : 'a` (where `N` is some associated type
357 /// defined in `SomeTrait`). This rule only applies to
358 /// trait-bounds that are not higher-ranked, because we cannot
359 /// project out of a HRTB. This rule helps code using associated
360 /// types to compile, see Issue #22246 for an example.
361 fn accumulate_from_assoc_types_transitive(&mut self,
362 data: &ty::PolyTraitPredicate<'tcx>)
364 debug!("accumulate_from_assoc_types_transitive({:?})",
367 for poly_trait_ref in traits::supertraits(self.tcx(), data.to_poly_trait_ref()) {
368 match self.tcx().no_late_bound_regions(&poly_trait_ref) {
369 Some(trait_ref) => { self.accumulate_from_assoc_types(trait_ref); }
375 fn accumulate_from_assoc_types(&mut self,
376 trait_ref: ty::TraitRef<'tcx>)
378 debug!("accumulate_from_assoc_types({:?})",
381 let trait_def_id = trait_ref.def_id;
382 let trait_def = self.tcx().lookup_trait_def(trait_def_id);
383 let assoc_type_projections: Vec<_> =
384 trait_def.associated_type_names
386 .map(|&name| self.tcx().mk_projection(trait_ref.clone(), name))
388 debug!("accumulate_from_assoc_types: assoc_type_projections={:?}",
389 assoc_type_projections);
390 let tys = match self.fully_normalize(&assoc_type_projections) {
392 Err(ErrorReported) => { return; }
395 self.accumulate_from_ty(ty);
399 fn accumulate_from_object_ty(&mut self,
401 region_bound: ty::Region,
402 required_region_bounds: Vec<ty::Region>)
404 // Imagine a type like this:
407 // trait Bar<'c> : 'c { }
409 // &'b (Foo+'c+Bar<'d>)
412 // In this case, the following relationships must hold:
417 // The first conditions is due to the normal region pointer
418 // rules, which say that a reference cannot outlive its
421 // The final condition may be a bit surprising. In particular,
422 // you may expect that it would have been `'c <= 'd`, since
423 // usually lifetimes of outer things are conservative
424 // approximations for inner things. However, it works somewhat
425 // differently with trait objects: here the idea is that if the
426 // user specifies a region bound (`'c`, in this case) it is the
427 // "master bound" that *implies* that bounds from other traits are
428 // all met. (Remember that *all bounds* in a type like
429 // `Foo+Bar+Zed` must be met, not just one, hence if we write
430 // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and
433 // Note: in fact we only permit builtin traits, not `Bar<'d>`, I
434 // am looking forward to the future here.
436 // The content of this object type must outlive
437 // `bounds.region_bound`:
438 let r_c = region_bound;
439 self.push_region_constraint_from_top(r_c);
441 // And then, in turn, to be well-formed, the
442 // `region_bound` that user specified must imply the
443 // region bounds required from all of the trait types:
444 for &r_d in &required_region_bounds {
445 // Each of these is an instance of the `'c <= 'b`
447 self.out.push(Implication::RegionSubRegion(Some(ty), r_d, r_c));
451 fn fully_normalize<T>(&self, value: &T) -> Result<T,ErrorReported>
452 where T : TypeFoldable<'tcx> + ty::HasTypeFlags
455 traits::fully_normalize(self.infcx,
456 traits::ObligationCause::misc(self.span, self.body_id),
459 Ok(value) => Ok(value),
461 // I don't like reporting these errors here, but I
462 // don't know where else to report them just now. And
463 // I don't really expect errors to arise here
464 // frequently. I guess the best option would be to
465 // propagate them out.
466 traits::report_fulfillment_errors(self.infcx, &errors);
473 /// Given an object type like `SomeTrait+Send`, computes the lifetime
474 /// bounds that must hold on the elided self type. These are derived
475 /// from the declarations of `SomeTrait`, `Send`, and friends -- if
476 /// they declare `trait SomeTrait : 'static`, for example, then
477 /// `'static` would appear in the list. The hard work is done by
478 /// `ty::required_region_bounds`, see that for more information.
479 pub fn object_region_bounds<'tcx>(
480 tcx: &ty::ctxt<'tcx>,
481 principal: &ty::PolyTraitRef<'tcx>,
482 others: ty::BuiltinBounds)
485 // Since we don't actually *know* the self type for an object,
486 // this "open(err)" serves as a kind of dummy standin -- basically
487 // a skolemized type.
488 let open_ty = tcx.mk_infer(ty::FreshTy(0));
490 // Note that we preserve the overall binding levels here.
491 assert!(!open_ty.has_escaping_regions());
492 let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
493 let trait_refs = vec!(ty::Binder(ty::TraitRef::new(principal.0.def_id, substs)));
495 let mut predicates = others.to_predicates(tcx, open_ty);
496 predicates.extend(trait_refs.iter().map(|t| t.to_predicate()));
498 tcx.required_region_bounds(open_ty, predicates)