]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | // Copyright 2012-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. | |
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 middle::def_id::DefId; | |
12 | use middle::infer::InferCtxt; | |
13 | use middle::ty::outlives::{self, Component}; | |
14 | use middle::subst::Substs; | |
15 | use middle::traits; | |
9cc50fc6 | 16 | use middle::ty::{self, ToPredicate, Ty, TypeFoldable}; |
e9174d1e | 17 | use std::iter::once; |
e9174d1e SL |
18 | use syntax::ast; |
19 | use syntax::codemap::Span; | |
20 | use util::common::ErrorReported; | |
21 | ||
22 | /// Returns the set of obligations needed to make `ty` well-formed. | |
23 | /// If `ty` contains unresolved inference variables, this may include | |
24 | /// further WF obligations. However, if `ty` IS an unresolved | |
25 | /// inference variable, returns `None`, because we are not able to | |
26 | /// make any progress at all. This is to prevent "livelock" where we | |
27 | /// say "$0 is WF if $0 is WF". | |
28 | pub fn obligations<'a,'tcx>(infcx: &InferCtxt<'a, 'tcx>, | |
29 | body_id: ast::NodeId, | |
30 | ty: Ty<'tcx>, | |
9cc50fc6 | 31 | span: Span) |
e9174d1e SL |
32 | -> Option<Vec<traits::PredicateObligation<'tcx>>> |
33 | { | |
34 | let mut wf = WfPredicates { infcx: infcx, | |
35 | body_id: body_id, | |
36 | span: span, | |
9cc50fc6 | 37 | out: vec![] }; |
e9174d1e SL |
38 | if wf.compute(ty) { |
39 | debug!("wf::obligations({:?}, body_id={:?}) = {:?}", ty, body_id, wf.out); | |
40 | let result = wf.normalize(); | |
41 | debug!("wf::obligations({:?}, body_id={:?}) ~~> {:?}", ty, body_id, result); | |
42 | Some(result) | |
43 | } else { | |
44 | None // no progress made, return None | |
45 | } | |
46 | } | |
47 | ||
48 | /// Returns the obligations that make this trait reference | |
49 | /// well-formed. For example, if there is a trait `Set` defined like | |
50 | /// `trait Set<K:Eq>`, then the trait reference `Foo: Set<Bar>` is WF | |
51 | /// if `Bar: Eq`. | |
52 | pub fn trait_obligations<'a,'tcx>(infcx: &InferCtxt<'a, 'tcx>, | |
53 | body_id: ast::NodeId, | |
54 | trait_ref: &ty::TraitRef<'tcx>, | |
9cc50fc6 | 55 | span: Span) |
e9174d1e SL |
56 | -> Vec<traits::PredicateObligation<'tcx>> |
57 | { | |
9cc50fc6 | 58 | let mut wf = WfPredicates { infcx: infcx, body_id: body_id, span: span, out: vec![] }; |
e9174d1e SL |
59 | wf.compute_trait_ref(trait_ref); |
60 | wf.normalize() | |
61 | } | |
62 | ||
63 | pub fn predicate_obligations<'a,'tcx>(infcx: &InferCtxt<'a, 'tcx>, | |
64 | body_id: ast::NodeId, | |
65 | predicate: &ty::Predicate<'tcx>, | |
9cc50fc6 | 66 | span: Span) |
e9174d1e SL |
67 | -> Vec<traits::PredicateObligation<'tcx>> |
68 | { | |
9cc50fc6 | 69 | let mut wf = WfPredicates { infcx: infcx, body_id: body_id, span: span, out: vec![] }; |
e9174d1e SL |
70 | |
71 | // (*) ok to skip binders, because wf code is prepared for it | |
72 | match *predicate { | |
73 | ty::Predicate::Trait(ref t) => { | |
74 | wf.compute_trait_ref(&t.skip_binder().trait_ref); // (*) | |
75 | } | |
76 | ty::Predicate::Equate(ref t) => { | |
77 | wf.compute(t.skip_binder().0); | |
78 | wf.compute(t.skip_binder().1); | |
79 | } | |
80 | ty::Predicate::RegionOutlives(..) => { | |
81 | } | |
82 | ty::Predicate::TypeOutlives(ref t) => { | |
83 | wf.compute(t.skip_binder().0); | |
84 | } | |
85 | ty::Predicate::Projection(ref t) => { | |
86 | let t = t.skip_binder(); // (*) | |
87 | wf.compute_projection(t.projection_ty); | |
88 | wf.compute(t.ty); | |
89 | } | |
90 | ty::Predicate::WellFormed(t) => { | |
91 | wf.compute(t); | |
92 | } | |
93 | ty::Predicate::ObjectSafe(_) => { | |
94 | } | |
95 | } | |
96 | ||
97 | wf.normalize() | |
98 | } | |
99 | ||
100 | /// Implied bounds are region relationships that we deduce | |
101 | /// automatically. The idea is that (e.g.) a caller must check that a | |
102 | /// function's argument types are well-formed immediately before | |
103 | /// calling that fn, and hence the *callee* can assume that its | |
104 | /// argument types are well-formed. This may imply certain relationships | |
105 | /// between generic parameters. For example: | |
106 | /// | |
107 | /// fn foo<'a,T>(x: &'a T) | |
108 | /// | |
109 | /// can only be called with a `'a` and `T` such that `&'a T` is WF. | |
110 | /// For `&'a T` to be WF, `T: 'a` must hold. So we can assume `T: 'a`. | |
111 | #[derive(Debug)] | |
112 | pub enum ImpliedBound<'tcx> { | |
113 | RegionSubRegion(ty::Region, ty::Region), | |
114 | RegionSubParam(ty::Region, ty::ParamTy), | |
115 | RegionSubProjection(ty::Region, ty::ProjectionTy<'tcx>), | |
116 | } | |
117 | ||
118 | /// Compute the implied bounds that a callee/impl can assume based on | |
119 | /// the fact that caller/projector has ensured that `ty` is WF. See | |
120 | /// the `ImpliedBound` type for more details. | |
121 | pub fn implied_bounds<'a,'tcx>( | |
122 | infcx: &'a InferCtxt<'a,'tcx>, | |
123 | body_id: ast::NodeId, | |
124 | ty: Ty<'tcx>, | |
125 | span: Span) | |
126 | -> Vec<ImpliedBound<'tcx>> | |
127 | { | |
128 | // Sometimes when we ask what it takes for T: WF, we get back that | |
129 | // U: WF is required; in that case, we push U onto this stack and | |
130 | // process it next. Currently (at least) these resulting | |
131 | // predicates are always guaranteed to be a subset of the original | |
132 | // type, so we need not fear non-termination. | |
133 | let mut wf_types = vec![ty]; | |
134 | ||
135 | let mut implied_bounds = vec![]; | |
136 | ||
137 | while let Some(ty) = wf_types.pop() { | |
138 | // Compute the obligations for `ty` to be well-formed. If `ty` is | |
139 | // an unresolved inference variable, just substituted an empty set | |
140 | // -- because the return type here is going to be things we *add* | |
141 | // to the environment, it's always ok for this set to be smaller | |
142 | // than the ultimate set. (Note: normally there won't be | |
143 | // unresolved inference variables here anyway, but there might be | |
144 | // during typeck under some circumstances.) | |
9cc50fc6 | 145 | let obligations = obligations(infcx, body_id, ty, span).unwrap_or(vec![]); |
e9174d1e SL |
146 | |
147 | // From the full set of obligations, just filter down to the | |
148 | // region relationships. | |
149 | implied_bounds.extend( | |
150 | obligations | |
151 | .into_iter() | |
152 | .flat_map(|obligation| { | |
153 | assert!(!obligation.has_escaping_regions()); | |
154 | match obligation.predicate { | |
155 | ty::Predicate::Trait(..) | | |
156 | ty::Predicate::Equate(..) | | |
157 | ty::Predicate::Projection(..) | | |
158 | ty::Predicate::ObjectSafe(..) => | |
159 | vec![], | |
160 | ||
161 | ty::Predicate::WellFormed(subty) => { | |
162 | wf_types.push(subty); | |
163 | vec![] | |
164 | } | |
165 | ||
166 | ty::Predicate::RegionOutlives(ref data) => | |
167 | match infcx.tcx.no_late_bound_regions(data) { | |
168 | None => | |
169 | vec![], | |
170 | Some(ty::OutlivesPredicate(r_a, r_b)) => | |
171 | vec![ImpliedBound::RegionSubRegion(r_b, r_a)], | |
172 | }, | |
173 | ||
174 | ty::Predicate::TypeOutlives(ref data) => | |
175 | match infcx.tcx.no_late_bound_regions(data) { | |
176 | None => vec![], | |
177 | Some(ty::OutlivesPredicate(ty_a, r_b)) => { | |
178 | let components = outlives::components(infcx, ty_a); | |
179 | implied_bounds_from_components(r_b, components) | |
180 | } | |
181 | }, | |
182 | }})); | |
183 | } | |
184 | ||
185 | implied_bounds | |
186 | } | |
187 | ||
188 | /// When we have an implied bound that `T: 'a`, we can further break | |
189 | /// this down to determine what relationships would have to hold for | |
190 | /// `T: 'a` to hold. We get to assume that the caller has validated | |
191 | /// those relationships. | |
192 | fn implied_bounds_from_components<'tcx>(sub_region: ty::Region, | |
193 | sup_components: Vec<Component<'tcx>>) | |
194 | -> Vec<ImpliedBound<'tcx>> | |
195 | { | |
196 | sup_components | |
197 | .into_iter() | |
198 | .flat_map(|component| { | |
199 | match component { | |
200 | Component::Region(r) => | |
201 | vec!(ImpliedBound::RegionSubRegion(sub_region, r)), | |
202 | Component::Param(p) => | |
203 | vec!(ImpliedBound::RegionSubParam(sub_region, p)), | |
204 | Component::Projection(p) => | |
205 | vec!(ImpliedBound::RegionSubProjection(sub_region, p)), | |
206 | Component::EscapingProjection(_) => | |
207 | // If the projection has escaping regions, don't | |
208 | // try to infer any implied bounds even for its | |
209 | // free components. This is conservative, because | |
210 | // the caller will still have to prove that those | |
211 | // free components outlive `sub_region`. But the | |
212 | // idea is that the WAY that the caller proves | |
213 | // that may change in the future and we want to | |
214 | // give ourselves room to get smarter here. | |
215 | vec!(), | |
216 | Component::UnresolvedInferenceVariable(..) => | |
217 | vec!(), | |
e9174d1e SL |
218 | } |
219 | }) | |
220 | .collect() | |
221 | } | |
222 | ||
223 | struct WfPredicates<'a,'tcx:'a> { | |
224 | infcx: &'a InferCtxt<'a, 'tcx>, | |
225 | body_id: ast::NodeId, | |
226 | span: Span, | |
227 | out: Vec<traits::PredicateObligation<'tcx>>, | |
e9174d1e SL |
228 | } |
229 | ||
230 | impl<'a,'tcx> WfPredicates<'a,'tcx> { | |
e9174d1e | 231 | fn cause(&mut self, code: traits::ObligationCauseCode<'tcx>) -> traits::ObligationCause<'tcx> { |
9cc50fc6 | 232 | traits::ObligationCause::new(self.span, self.body_id, code) |
e9174d1e SL |
233 | } |
234 | ||
235 | fn normalize(&mut self) -> Vec<traits::PredicateObligation<'tcx>> { | |
236 | let cause = self.cause(traits::MiscObligation); | |
237 | let infcx = &mut self.infcx; | |
238 | self.out.iter() | |
239 | .inspect(|pred| assert!(!pred.has_escaping_regions())) | |
240 | .flat_map(|pred| { | |
241 | let mut selcx = traits::SelectionContext::new(infcx); | |
242 | let pred = traits::normalize(&mut selcx, cause.clone(), pred); | |
243 | once(pred.value).chain(pred.obligations) | |
244 | }) | |
245 | .collect() | |
246 | } | |
247 | ||
e9174d1e SL |
248 | /// Pushes the obligations required for `trait_ref` to be WF into |
249 | /// `self.out`. | |
250 | fn compute_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>) { | |
251 | let obligations = self.nominal_obligations(trait_ref.def_id, trait_ref.substs); | |
252 | self.out.extend(obligations); | |
253 | ||
254 | let cause = self.cause(traits::MiscObligation); | |
255 | self.out.extend( | |
256 | trait_ref.substs.types | |
257 | .as_slice() | |
258 | .iter() | |
259 | .filter(|ty| !ty.has_escaping_regions()) | |
260 | .map(|ty| traits::Obligation::new(cause.clone(), | |
261 | ty::Predicate::WellFormed(ty)))); | |
262 | } | |
263 | ||
264 | /// Pushes the obligations required for `trait_ref::Item` to be WF | |
265 | /// into `self.out`. | |
266 | fn compute_projection(&mut self, data: ty::ProjectionTy<'tcx>) { | |
267 | // A projection is well-formed if (a) the trait ref itself is | |
268 | // WF WF and (b) the trait-ref holds. (It may also be | |
269 | // normalizable and be WF that way.) | |
270 | ||
271 | self.compute_trait_ref(&data.trait_ref); | |
272 | ||
273 | if !data.has_escaping_regions() { | |
274 | let predicate = data.trait_ref.to_predicate(); | |
275 | let cause = self.cause(traits::ProjectionWf(data)); | |
276 | self.out.push(traits::Obligation::new(cause, predicate)); | |
277 | } | |
278 | } | |
279 | ||
280 | /// Push new obligations into `out`. Returns true if it was able | |
281 | /// to generate all the predicates needed to validate that `ty0` | |
282 | /// is WF. Returns false if `ty0` is an unresolved type variable, | |
283 | /// in which case we are not able to simplify at all. | |
284 | fn compute(&mut self, ty0: Ty<'tcx>) -> bool { | |
285 | let mut subtys = ty0.walk(); | |
286 | while let Some(ty) = subtys.next() { | |
287 | match ty.sty { | |
288 | ty::TyBool | | |
289 | ty::TyChar | | |
290 | ty::TyInt(..) | | |
291 | ty::TyUint(..) | | |
292 | ty::TyFloat(..) | | |
293 | ty::TyError | | |
294 | ty::TyStr | | |
295 | ty::TyParam(_) => { | |
296 | // WfScalar, WfParameter, etc | |
297 | } | |
298 | ||
299 | ty::TySlice(subty) | | |
300 | ty::TyArray(subty, _) => { | |
9cc50fc6 SL |
301 | if !subty.has_escaping_regions() { |
302 | let cause = self.cause(traits::SliceOrArrayElem); | |
303 | match traits::trait_ref_for_builtin_bound(self.infcx.tcx, | |
304 | ty::BoundSized, | |
305 | subty) { | |
306 | Ok(trait_ref) => { | |
307 | self.out.push( | |
308 | traits::Obligation::new(cause, | |
309 | trait_ref.to_predicate())); | |
e9174d1e | 310 | } |
9cc50fc6 | 311 | Err(ErrorReported) => { } |
e9174d1e | 312 | } |
9cc50fc6 | 313 | } |
e9174d1e SL |
314 | } |
315 | ||
316 | ty::TyBox(_) | | |
317 | ty::TyTuple(_) | | |
318 | ty::TyRawPtr(_) => { | |
319 | // simple cases that are WF if their type args are WF | |
320 | } | |
321 | ||
322 | ty::TyProjection(data) => { | |
323 | subtys.skip_current_subtree(); // subtree handled by compute_projection | |
324 | self.compute_projection(data); | |
325 | } | |
326 | ||
327 | ty::TyEnum(def, substs) | | |
328 | ty::TyStruct(def, substs) => { | |
329 | // WfNominalType | |
330 | let obligations = self.nominal_obligations(def.did, substs); | |
331 | self.out.extend(obligations); | |
332 | } | |
333 | ||
334 | ty::TyRef(r, mt) => { | |
335 | // WfReference | |
336 | if !r.has_escaping_regions() && !mt.ty.has_escaping_regions() { | |
337 | let cause = self.cause(traits::ReferenceOutlivesReferent(ty)); | |
338 | self.out.push( | |
339 | traits::Obligation::new( | |
340 | cause, | |
341 | ty::Predicate::TypeOutlives( | |
342 | ty::Binder( | |
343 | ty::OutlivesPredicate(mt.ty, *r))))); | |
344 | } | |
345 | } | |
346 | ||
347 | ty::TyClosure(..) => { | |
348 | // the types in a closure are always the types of | |
349 | // local variables (or possibly references to local | |
9cc50fc6 SL |
350 | // variables), we'll walk those. |
351 | // | |
352 | // (Though, local variables are probably not | |
353 | // needed, as they are separately checked w/r/t | |
354 | // WFedness.) | |
e9174d1e SL |
355 | } |
356 | ||
357 | ty::TyBareFn(..) => { | |
9cc50fc6 SL |
358 | // let the loop iterator into the argument/return |
359 | // types appearing in the fn signature | |
e9174d1e SL |
360 | } |
361 | ||
362 | ty::TyTrait(ref data) => { | |
363 | // WfObject | |
364 | // | |
365 | // Here, we defer WF checking due to higher-ranked | |
366 | // regions. This is perhaps not ideal. | |
367 | self.from_object_ty(ty, data); | |
368 | ||
369 | // FIXME(#27579) RFC also considers adding trait | |
370 | // obligations that don't refer to Self and | |
371 | // checking those | |
372 | ||
373 | let cause = self.cause(traits::MiscObligation); | |
374 | self.out.push( | |
375 | traits::Obligation::new( | |
376 | cause, | |
377 | ty::Predicate::ObjectSafe(data.principal_def_id()))); | |
e9174d1e SL |
378 | } |
379 | ||
380 | // Inference variables are the complicated case, since we don't | |
381 | // know what type they are. We do two things: | |
382 | // | |
383 | // 1. Check if they have been resolved, and if so proceed with | |
384 | // THAT type. | |
385 | // 2. If not, check whether this is the type that we | |
386 | // started with (ty0). In that case, we've made no | |
387 | // progress at all, so return false. Otherwise, | |
388 | // we've at least simplified things (i.e., we went | |
389 | // from `Vec<$0>: WF` to `$0: WF`, so we can | |
390 | // register a pending obligation and keep | |
391 | // moving. (Goal is that an "inductive hypothesis" | |
392 | // is satisfied to ensure termination.) | |
393 | ty::TyInfer(_) => { | |
394 | let ty = self.infcx.shallow_resolve(ty); | |
395 | if let ty::TyInfer(_) = ty.sty { // not yet resolved... | |
396 | if ty == ty0 { // ...this is the type we started from! no progress. | |
397 | return false; | |
398 | } | |
399 | ||
400 | let cause = self.cause(traits::MiscObligation); | |
401 | self.out.push( // ...not the type we started from, so we made progress. | |
402 | traits::Obligation::new(cause, ty::Predicate::WellFormed(ty))); | |
403 | } else { | |
404 | // Yes, resolved, proceed with the | |
405 | // result. Should never return false because | |
406 | // `ty` is not a TyInfer. | |
407 | assert!(self.compute(ty)); | |
408 | } | |
409 | } | |
410 | } | |
411 | } | |
412 | ||
413 | // if we made it through that loop above, we made progress! | |
414 | return true; | |
415 | } | |
416 | ||
417 | fn nominal_obligations(&mut self, | |
418 | def_id: DefId, | |
419 | substs: &Substs<'tcx>) | |
420 | -> Vec<traits::PredicateObligation<'tcx>> | |
421 | { | |
422 | let predicates = | |
423 | self.infcx.tcx.lookup_predicates(def_id) | |
424 | .instantiate(self.infcx.tcx, substs); | |
425 | let cause = self.cause(traits::ItemObligation(def_id)); | |
426 | predicates.predicates | |
427 | .into_iter() | |
428 | .map(|pred| traits::Obligation::new(cause.clone(), pred)) | |
429 | .filter(|pred| !pred.has_escaping_regions()) | |
430 | .collect() | |
431 | } | |
432 | ||
433 | fn from_object_ty(&mut self, ty: Ty<'tcx>, data: &ty::TraitTy<'tcx>) { | |
434 | // Imagine a type like this: | |
435 | // | |
436 | // trait Foo { } | |
437 | // trait Bar<'c> : 'c { } | |
438 | // | |
439 | // &'b (Foo+'c+Bar<'d>) | |
440 | // ^ | |
441 | // | |
442 | // In this case, the following relationships must hold: | |
443 | // | |
444 | // 'b <= 'c | |
445 | // 'd <= 'c | |
446 | // | |
447 | // The first conditions is due to the normal region pointer | |
448 | // rules, which say that a reference cannot outlive its | |
449 | // referent. | |
450 | // | |
451 | // The final condition may be a bit surprising. In particular, | |
452 | // you may expect that it would have been `'c <= 'd`, since | |
453 | // usually lifetimes of outer things are conservative | |
454 | // approximations for inner things. However, it works somewhat | |
455 | // differently with trait objects: here the idea is that if the | |
456 | // user specifies a region bound (`'c`, in this case) it is the | |
457 | // "master bound" that *implies* that bounds from other traits are | |
458 | // all met. (Remember that *all bounds* in a type like | |
459 | // `Foo+Bar+Zed` must be met, not just one, hence if we write | |
460 | // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and | |
461 | // 'y.) | |
462 | // | |
463 | // Note: in fact we only permit builtin traits, not `Bar<'d>`, I | |
464 | // am looking forward to the future here. | |
465 | ||
466 | if !data.has_escaping_regions() { | |
467 | let implicit_bounds = | |
468 | object_region_bounds(self.infcx.tcx, | |
469 | &data.principal, | |
470 | data.bounds.builtin_bounds); | |
471 | ||
472 | let explicit_bound = data.bounds.region_bound; | |
473 | ||
474 | for implicit_bound in implicit_bounds { | |
475 | let cause = self.cause(traits::ReferenceOutlivesReferent(ty)); | |
476 | let outlives = ty::Binder(ty::OutlivesPredicate(explicit_bound, implicit_bound)); | |
477 | self.out.push(traits::Obligation::new(cause, outlives.to_predicate())); | |
478 | } | |
479 | } | |
480 | } | |
481 | } | |
482 | ||
483 | /// Given an object type like `SomeTrait+Send`, computes the lifetime | |
484 | /// bounds that must hold on the elided self type. These are derived | |
485 | /// from the declarations of `SomeTrait`, `Send`, and friends -- if | |
486 | /// they declare `trait SomeTrait : 'static`, for example, then | |
487 | /// `'static` would appear in the list. The hard work is done by | |
488 | /// `ty::required_region_bounds`, see that for more information. | |
489 | pub fn object_region_bounds<'tcx>( | |
490 | tcx: &ty::ctxt<'tcx>, | |
491 | principal: &ty::PolyTraitRef<'tcx>, | |
492 | others: ty::BuiltinBounds) | |
493 | -> Vec<ty::Region> | |
494 | { | |
495 | // Since we don't actually *know* the self type for an object, | |
496 | // this "open(err)" serves as a kind of dummy standin -- basically | |
497 | // a skolemized type. | |
498 | let open_ty = tcx.mk_infer(ty::FreshTy(0)); | |
499 | ||
500 | // Note that we preserve the overall binding levels here. | |
501 | assert!(!open_ty.has_escaping_regions()); | |
502 | let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty)); | |
503 | let trait_refs = vec!(ty::Binder(ty::TraitRef::new(principal.0.def_id, substs))); | |
504 | ||
505 | let mut predicates = others.to_predicates(tcx, open_ty); | |
506 | predicates.extend(trait_refs.iter().map(|t| t.to_predicate())); | |
507 | ||
508 | tcx.required_region_bounds(open_ty, predicates) | |
509 | } |