]>
Commit | Line | Data |
---|---|---|
dfeec247 | 1 | use crate::infer::opaque_types::required_region_bounds; |
9fa01778 | 2 | use crate::infer::InferCtxt; |
60c5eb7d | 3 | use crate::traits::{self, AssocTypeBoundData}; |
74b04a01 XL |
4 | use rustc::middle::lang_items; |
5 | use rustc::ty::subst::SubstsRef; | |
6 | use rustc::ty::{self, ToPredicate, Ty, TyCtxt, TypeFoldable, WithConstness}; | |
dfeec247 XL |
7 | use rustc_hir as hir; |
8 | use rustc_hir::def_id::DefId; | |
9 | use rustc_span::symbol::{kw, Ident}; | |
10 | use rustc_span::Span; | |
e9174d1e SL |
11 | |
12 | /// Returns the set of obligations needed to make `ty` well-formed. | |
13 | /// If `ty` contains unresolved inference variables, this may include | |
14 | /// further WF obligations. However, if `ty` IS an unresolved | |
15 | /// inference variable, returns `None`, because we are not able to | |
16 | /// make any progress at all. This is to prevent "livelock" where we | |
17 | /// say "$0 is WF if $0 is WF". | |
dc9dc135 XL |
18 | pub fn obligations<'a, 'tcx>( |
19 | infcx: &InferCtxt<'a, 'tcx>, | |
20 | param_env: ty::ParamEnv<'tcx>, | |
21 | body_id: hir::HirId, | |
22 | ty: Ty<'tcx>, | |
23 | span: Span, | |
24 | ) -> Option<Vec<traits::PredicateObligation<'tcx>>> { | |
dfeec247 | 25 | let mut wf = WfPredicates { infcx, param_env, body_id, span, out: vec![], item: None }; |
e9174d1e SL |
26 | if wf.compute(ty) { |
27 | debug!("wf::obligations({:?}, body_id={:?}) = {:?}", ty, body_id, wf.out); | |
74b04a01 | 28 | |
e9174d1e SL |
29 | let result = wf.normalize(); |
30 | debug!("wf::obligations({:?}, body_id={:?}) ~~> {:?}", ty, body_id, result); | |
31 | Some(result) | |
32 | } else { | |
33 | None // no progress made, return None | |
34 | } | |
35 | } | |
36 | ||
37 | /// Returns the obligations that make this trait reference | |
38 | /// well-formed. For example, if there is a trait `Set` defined like | |
39 | /// `trait Set<K:Eq>`, then the trait reference `Foo: Set<Bar>` is WF | |
40 | /// if `Bar: Eq`. | |
dc9dc135 XL |
41 | pub fn trait_obligations<'a, 'tcx>( |
42 | infcx: &InferCtxt<'a, 'tcx>, | |
43 | param_env: ty::ParamEnv<'tcx>, | |
44 | body_id: hir::HirId, | |
45 | trait_ref: &ty::TraitRef<'tcx>, | |
46 | span: Span, | |
dfeec247 | 47 | item: Option<&'tcx hir::Item<'tcx>>, |
dc9dc135 | 48 | ) -> Vec<traits::PredicateObligation<'tcx>> { |
e74abb32 | 49 | let mut wf = WfPredicates { infcx, param_env, body_id, span, out: vec![], item }; |
3b2f2976 | 50 | wf.compute_trait_ref(trait_ref, Elaborate::All); |
e9174d1e SL |
51 | wf.normalize() |
52 | } | |
53 | ||
dc9dc135 XL |
54 | pub fn predicate_obligations<'a, 'tcx>( |
55 | infcx: &InferCtxt<'a, 'tcx>, | |
56 | param_env: ty::ParamEnv<'tcx>, | |
57 | body_id: hir::HirId, | |
58 | predicate: &ty::Predicate<'tcx>, | |
59 | span: Span, | |
60 | ) -> Vec<traits::PredicateObligation<'tcx>> { | |
e74abb32 | 61 | let mut wf = WfPredicates { infcx, param_env, body_id, span, out: vec![], item: None }; |
e9174d1e SL |
62 | |
63 | // (*) ok to skip binders, because wf code is prepared for it | |
64 | match *predicate { | |
dfeec247 | 65 | ty::Predicate::Trait(ref t, _) => { |
3b2f2976 | 66 | wf.compute_trait_ref(&t.skip_binder().trait_ref, Elaborate::None); // (*) |
e9174d1e | 67 | } |
dfeec247 | 68 | ty::Predicate::RegionOutlives(..) => {} |
e9174d1e SL |
69 | ty::Predicate::TypeOutlives(ref t) => { |
70 | wf.compute(t.skip_binder().0); | |
71 | } | |
72 | ty::Predicate::Projection(ref t) => { | |
73 | let t = t.skip_binder(); // (*) | |
74 | wf.compute_projection(t.projection_ty); | |
75 | wf.compute(t.ty); | |
76 | } | |
77 | ty::Predicate::WellFormed(t) => { | |
78 | wf.compute(t); | |
79 | } | |
dfeec247 XL |
80 | ty::Predicate::ObjectSafe(_) => {} |
81 | ty::Predicate::ClosureKind(..) => {} | |
cc61c64b XL |
82 | ty::Predicate::Subtype(ref data) => { |
83 | wf.compute(data.skip_binder().a); // (*) | |
84 | wf.compute(data.skip_binder().b); // (*) | |
85 | } | |
ea8adc8c XL |
86 | ty::Predicate::ConstEvaluatable(def_id, substs) => { |
87 | let obligations = wf.nominal_obligations(def_id, substs); | |
88 | wf.out.extend(obligations); | |
89 | ||
90 | for ty in substs.types() { | |
91 | wf.compute(ty); | |
92 | } | |
93 | } | |
e9174d1e SL |
94 | } |
95 | ||
96 | wf.normalize() | |
97 | } | |
98 | ||
dc9dc135 XL |
99 | struct WfPredicates<'a, 'tcx> { |
100 | infcx: &'a InferCtxt<'a, 'tcx>, | |
7cac9316 | 101 | param_env: ty::ParamEnv<'tcx>, |
9fa01778 | 102 | body_id: hir::HirId, |
e9174d1e SL |
103 | span: Span, |
104 | out: Vec<traits::PredicateObligation<'tcx>>, | |
dfeec247 | 105 | item: Option<&'tcx hir::Item<'tcx>>, |
e9174d1e SL |
106 | } |
107 | ||
3b2f2976 XL |
108 | /// Controls whether we "elaborate" supertraits and so forth on the WF |
109 | /// predicates. This is a kind of hack to address #43784. The | |
110 | /// underlying problem in that issue was a trait structure like: | |
111 | /// | |
112 | /// ``` | |
113 | /// trait Foo: Copy { } | |
114 | /// trait Bar: Foo { } | |
115 | /// impl<T: Bar> Foo for T { } | |
116 | /// impl<T> Bar for T { } | |
117 | /// ``` | |
118 | /// | |
119 | /// Here, in the `Foo` impl, we will check that `T: Copy` holds -- but | |
120 | /// we decide that this is true because `T: Bar` is in the | |
121 | /// where-clauses (and we can elaborate that to include `T: | |
122 | /// Copy`). This wouldn't be a problem, except that when we check the | |
123 | /// `Bar` impl, we decide that `T: Foo` must hold because of the `Foo` | |
124 | /// impl. And so nowhere did we check that `T: Copy` holds! | |
125 | /// | |
126 | /// To resolve this, we elaborate the WF requirements that must be | |
127 | /// proven when checking impls. This means that (e.g.) the `impl Bar | |
128 | /// for T` will be forced to prove not only that `T: Foo` but also `T: | |
129 | /// Copy` (which it won't be able to do, because there is no `Copy` | |
130 | /// impl for `T`). | |
131 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] | |
132 | enum Elaborate { | |
133 | All, | |
134 | None, | |
135 | } | |
136 | ||
dc9dc135 | 137 | impl<'a, 'tcx> WfPredicates<'a, 'tcx> { |
e9174d1e | 138 | fn cause(&mut self, code: traits::ObligationCauseCode<'tcx>) -> traits::ObligationCause<'tcx> { |
9cc50fc6 | 139 | traits::ObligationCause::new(self.span, self.body_id, code) |
e9174d1e SL |
140 | } |
141 | ||
142 | fn normalize(&mut self) -> Vec<traits::PredicateObligation<'tcx>> { | |
143 | let cause = self.cause(traits::MiscObligation); | |
144 | let infcx = &mut self.infcx; | |
7cac9316 | 145 | let param_env = self.param_env; |
74b04a01 XL |
146 | let mut obligations = Vec::with_capacity(self.out.len()); |
147 | for pred in &self.out { | |
148 | assert!(!pred.has_escaping_bound_vars()); | |
149 | let mut selcx = traits::SelectionContext::new(infcx); | |
150 | let i = obligations.len(); | |
151 | let value = | |
152 | traits::normalize_to(&mut selcx, param_env, cause.clone(), pred, &mut obligations); | |
153 | obligations.insert(i, value); | |
154 | } | |
155 | obligations | |
e9174d1e SL |
156 | } |
157 | ||
e74abb32 | 158 | /// Pushes the obligations required for `trait_ref` to be WF into `self.out`. |
3b2f2976 | 159 | fn compute_trait_ref(&mut self, trait_ref: &ty::TraitRef<'tcx>, elaborate: Elaborate) { |
e74abb32 | 160 | let tcx = self.infcx.tcx; |
e9174d1e | 161 | let obligations = self.nominal_obligations(trait_ref.def_id, trait_ref.substs); |
e9174d1e SL |
162 | |
163 | let cause = self.cause(traits::MiscObligation); | |
7cac9316 | 164 | let param_env = self.param_env; |
3b2f2976 | 165 | |
e74abb32 | 166 | let item = &self.item; |
dfeec247 XL |
167 | let extend_cause_with_original_assoc_item_obligation = |
168 | |cause: &mut traits::ObligationCause<'_>, | |
169 | pred: &ty::Predicate<'_>, | |
74b04a01 | 170 | trait_assoc_items: &[ty::AssocItem]| { |
dfeec247 XL |
171 | let trait_item = tcx |
172 | .hir() | |
173 | .as_local_hir_id(trait_ref.def_id) | |
174 | .and_then(|trait_id| tcx.hir().find(trait_id)); | |
175 | let (trait_name, trait_generics) = match trait_item { | |
176 | Some(hir::Node::Item(hir::Item { | |
177 | ident, | |
178 | kind: hir::ItemKind::Trait(.., generics, _, _), | |
179 | .. | |
180 | })) | |
181 | | Some(hir::Node::Item(hir::Item { | |
182 | ident, | |
183 | kind: hir::ItemKind::TraitAlias(generics, _), | |
184 | .. | |
185 | })) => (Some(ident), Some(generics)), | |
186 | _ => (None, None), | |
187 | }; | |
188 | ||
189 | let item_span = item.map(|i| tcx.sess.source_map().def_span(i.span)); | |
190 | match pred { | |
191 | ty::Predicate::Projection(proj) => { | |
192 | // The obligation comes not from the current `impl` nor the `trait` being | |
193 | // implemented, but rather from a "second order" obligation, like in | |
194 | // `src/test/ui/associated-types/point-at-type-on-obligation-failure.rs`: | |
195 | // | |
196 | // error[E0271]: type mismatch resolving `<Foo2 as Bar2>::Ok == ()` | |
197 | // --> $DIR/point-at-type-on-obligation-failure.rs:13:5 | |
198 | // | | |
199 | // LL | type Ok; | |
200 | // | -- associated type defined here | |
201 | // ... | |
202 | // LL | impl Bar for Foo { | |
203 | // | ---------------- in this `impl` item | |
204 | // LL | type Ok = (); | |
205 | // | ^^^^^^^^^^^^^ expected `u32`, found `()` | |
206 | // | | |
207 | // = note: expected type `u32` | |
208 | // found type `()` | |
209 | // | |
210 | // FIXME: we would want to point a span to all places that contributed to this | |
211 | // obligation. In the case above, it should be closer to: | |
212 | // | |
213 | // error[E0271]: type mismatch resolving `<Foo2 as Bar2>::Ok == ()` | |
214 | // --> $DIR/point-at-type-on-obligation-failure.rs:13:5 | |
215 | // | | |
216 | // LL | type Ok; | |
217 | // | -- associated type defined here | |
218 | // LL | type Sibling: Bar2<Ok=Self::Ok>; | |
219 | // | -------------------------------- obligation set here | |
220 | // ... | |
221 | // LL | impl Bar for Foo { | |
222 | // | ---------------- in this `impl` item | |
223 | // LL | type Ok = (); | |
224 | // | ^^^^^^^^^^^^^ expected `u32`, found `()` | |
225 | // ... | |
226 | // LL | impl Bar2 for Foo2 { | |
227 | // | ---------------- in this `impl` item | |
228 | // LL | type Ok = u32; | |
229 | // | -------------- obligation set here | |
230 | // | | |
231 | // = note: expected type `u32` | |
232 | // found type `()` | |
233 | if let Some(hir::ItemKind::Impl { items, .. }) = item.map(|i| &i.kind) { | |
234 | let trait_assoc_item = tcx.associated_item(proj.projection_def_id()); | |
74b04a01 XL |
235 | if let Some(impl_item) = |
236 | items.iter().find(|item| item.ident == trait_assoc_item.ident) | |
dfeec247 XL |
237 | { |
238 | cause.span = impl_item.span; | |
239 | cause.code = traits::AssocTypeBound(Box::new(AssocTypeBoundData { | |
240 | impl_span: item_span, | |
241 | original: trait_assoc_item.ident.span, | |
242 | bounds: vec![], | |
243 | })); | |
244 | } | |
e74abb32 XL |
245 | } |
246 | } | |
dfeec247 XL |
247 | ty::Predicate::Trait(proj, _) => { |
248 | // An associated item obligation born out of the `trait` failed to be met. | |
249 | // Point at the `impl` that failed the obligation, the associated item that | |
250 | // needed to meet the obligation, and the definition of that associated item, | |
251 | // which should hold the obligation in most cases. An example can be seen in | |
252 | // `src/test/ui/associated-types/point-at-type-on-obligation-failure-2.rs`: | |
253 | // | |
254 | // error[E0277]: the trait bound `bool: Bar` is not satisfied | |
255 | // --> $DIR/point-at-type-on-obligation-failure-2.rs:8:5 | |
256 | // | | |
257 | // LL | type Assoc: Bar; | |
258 | // | ----- associated type defined here | |
259 | // ... | |
260 | // LL | impl Foo for () { | |
261 | // | --------------- in this `impl` item | |
262 | // LL | type Assoc = bool; | |
263 | // | ^^^^^^^^^^^^^^^^^^ the trait `Bar` is not implemented for `bool` | |
264 | // | |
265 | // If the obligation comes from the where clause in the `trait`, we point at it: | |
266 | // | |
267 | // error[E0277]: the trait bound `bool: Bar` is not satisfied | |
268 | // --> $DIR/point-at-type-on-obligation-failure-2.rs:8:5 | |
269 | // | | |
270 | // | trait Foo where <Self as Foo>>::Assoc: Bar { | |
271 | // | -------------------------- restricted in this bound | |
272 | // LL | type Assoc; | |
273 | // | ----- associated type defined here | |
274 | // ... | |
275 | // LL | impl Foo for () { | |
276 | // | --------------- in this `impl` item | |
277 | // LL | type Assoc = bool; | |
278 | // | ^^^^^^^^^^^^^^^^^^ the trait `Bar` is not implemented for `bool` | |
279 | if let ( | |
280 | ty::Projection(ty::ProjectionTy { item_def_id, .. }), | |
281 | Some(hir::ItemKind::Impl { items, .. }), | |
282 | ) = (&proj.skip_binder().self_ty().kind, item.map(|i| &i.kind)) | |
e74abb32 | 283 | { |
dfeec247 | 284 | if let Some((impl_item, trait_assoc_item)) = trait_assoc_items |
74b04a01 XL |
285 | .iter() |
286 | .find(|i| i.def_id == *item_def_id) | |
dfeec247 XL |
287 | .and_then(|trait_assoc_item| { |
288 | items | |
289 | .iter() | |
74b04a01 | 290 | .find(|i| i.ident == trait_assoc_item.ident) |
dfeec247 XL |
291 | .map(|impl_item| (impl_item, trait_assoc_item)) |
292 | }) | |
293 | { | |
294 | let bounds = trait_generics | |
295 | .map(|generics| { | |
296 | get_generic_bound_spans( | |
297 | &generics, | |
298 | trait_name, | |
299 | trait_assoc_item.ident, | |
300 | ) | |
301 | }) | |
302 | .unwrap_or_else(Vec::new); | |
303 | cause.span = impl_item.span; | |
304 | cause.code = traits::AssocTypeBound(Box::new(AssocTypeBoundData { | |
305 | impl_span: item_span, | |
306 | original: trait_assoc_item.ident.span, | |
307 | bounds, | |
308 | })); | |
309 | } | |
e74abb32 XL |
310 | } |
311 | } | |
dfeec247 | 312 | _ => {} |
e74abb32 | 313 | } |
dfeec247 | 314 | }; |
e74abb32 | 315 | |
3b2f2976 | 316 | if let Elaborate::All = elaborate { |
74b04a01 XL |
317 | // FIXME: Make `extend_cause_with_original_assoc_item_obligation` take an iterator |
318 | // instead of a slice. | |
319 | let trait_assoc_items: Vec<_> = | |
320 | tcx.associated_items(trait_ref.def_id).in_definition_order().copied().collect(); | |
e74abb32 | 321 | |
dfeec247 | 322 | let predicates = obligations.iter().map(|obligation| obligation.predicate).collect(); |
e74abb32 | 323 | let implied_obligations = traits::elaborate_predicates(tcx, predicates); |
3b2f2976 | 324 | let implied_obligations = implied_obligations.map(|pred| { |
e74abb32 XL |
325 | let mut cause = cause.clone(); |
326 | extend_cause_with_original_assoc_item_obligation( | |
327 | &mut cause, | |
328 | &pred, | |
74b04a01 | 329 | &*trait_assoc_items, |
e74abb32 XL |
330 | ); |
331 | traits::Obligation::new(cause, param_env, pred) | |
3b2f2976 XL |
332 | }); |
333 | self.out.extend(implied_obligations); | |
334 | } | |
335 | ||
336 | self.out.extend(obligations); | |
337 | ||
dfeec247 XL |
338 | self.out.extend(trait_ref.substs.types().filter(|ty| !ty.has_escaping_bound_vars()).map( |
339 | |ty| traits::Obligation::new(cause.clone(), param_env, ty::Predicate::WellFormed(ty)), | |
340 | )); | |
e9174d1e SL |
341 | } |
342 | ||
343 | /// Pushes the obligations required for `trait_ref::Item` to be WF | |
344 | /// into `self.out`. | |
345 | fn compute_projection(&mut self, data: ty::ProjectionTy<'tcx>) { | |
346 | // A projection is well-formed if (a) the trait ref itself is | |
a7813a04 | 347 | // WF and (b) the trait-ref holds. (It may also be |
e9174d1e | 348 | // normalizable and be WF that way.) |
041b39d2 | 349 | let trait_ref = data.trait_ref(self.infcx.tcx); |
3b2f2976 | 350 | self.compute_trait_ref(&trait_ref, Elaborate::None); |
e9174d1e | 351 | |
a1dfa0c6 | 352 | if !data.has_escaping_bound_vars() { |
dfeec247 | 353 | let predicate = trait_ref.without_const().to_predicate(); |
e9174d1e | 354 | let cause = self.cause(traits::ProjectionWf(data)); |
7cac9316 | 355 | self.out.push(traits::Obligation::new(cause, self.param_env, predicate)); |
e9174d1e SL |
356 | } |
357 | } | |
358 | ||
0731742a | 359 | /// Pushes the obligations required for an array length to be WF |
ea8adc8c | 360 | /// into `self.out`. |
532ac7d7 | 361 | fn compute_array_len(&mut self, constant: ty::Const<'tcx>) { |
dfeec247 XL |
362 | if let ty::ConstKind::Unevaluated(def_id, substs, promoted) = constant.val { |
363 | assert!(promoted.is_none()); | |
364 | ||
8faf50e0 XL |
365 | let obligations = self.nominal_obligations(def_id, substs); |
366 | self.out.extend(obligations); | |
367 | ||
368 | let predicate = ty::Predicate::ConstEvaluatable(def_id, substs); | |
369 | let cause = self.cause(traits::MiscObligation); | |
dfeec247 | 370 | self.out.push(traits::Obligation::new(cause, self.param_env, predicate)); |
ea8adc8c XL |
371 | } |
372 | } | |
373 | ||
9e0c209e | 374 | fn require_sized(&mut self, subty: Ty<'tcx>, cause: traits::ObligationCauseCode<'tcx>) { |
a1dfa0c6 | 375 | if !subty.has_escaping_bound_vars() { |
a7813a04 | 376 | let cause = self.cause(cause); |
476ff2be | 377 | let trait_ref = ty::TraitRef { |
e1599b0c | 378 | def_id: self.infcx.tcx.require_lang_item(lang_items::SizedTraitLangItem, None), |
476ff2be SL |
379 | substs: self.infcx.tcx.mk_substs_trait(subty, &[]), |
380 | }; | |
dfeec247 XL |
381 | self.out.push(traits::Obligation::new( |
382 | cause, | |
383 | self.param_env, | |
384 | trait_ref.without_const().to_predicate(), | |
385 | )); | |
a7813a04 XL |
386 | } |
387 | } | |
388 | ||
9fa01778 | 389 | /// Pushes new obligations into `out`. Returns `true` if it was able |
e9174d1e SL |
390 | /// to generate all the predicates needed to validate that `ty0` |
391 | /// is WF. Returns false if `ty0` is an unresolved type variable, | |
392 | /// in which case we are not able to simplify at all. | |
393 | fn compute(&mut self, ty0: Ty<'tcx>) -> bool { | |
394 | let mut subtys = ty0.walk(); | |
7cac9316 | 395 | let param_env = self.param_env; |
e9174d1e | 396 | while let Some(ty) = subtys.next() { |
e74abb32 | 397 | match ty.kind { |
dfeec247 XL |
398 | ty::Bool |
399 | | ty::Char | |
400 | | ty::Int(..) | |
401 | | ty::Uint(..) | |
402 | | ty::Float(..) | |
403 | | ty::Error | |
404 | | ty::Str | |
405 | | ty::GeneratorWitness(..) | |
406 | | ty::Never | |
407 | | ty::Param(_) | |
408 | | ty::Bound(..) | |
409 | | ty::Placeholder(..) | |
410 | | ty::Foreign(..) => { | |
e9174d1e SL |
411 | // WfScalar, WfParameter, etc |
412 | } | |
413 | ||
b7449926 | 414 | ty::Slice(subty) => { |
ea8adc8c XL |
415 | self.require_sized(subty, traits::SliceOrArrayElem); |
416 | } | |
417 | ||
b7449926 | 418 | ty::Array(subty, len) => { |
9e0c209e | 419 | self.require_sized(subty, traits::SliceOrArrayElem); |
0731742a | 420 | self.compute_array_len(*len); |
a7813a04 XL |
421 | } |
422 | ||
b7449926 | 423 | ty::Tuple(ref tys) => { |
a7813a04 XL |
424 | if let Some((_last, rest)) = tys.split_last() { |
425 | for elem in rest { | |
48663c56 | 426 | self.require_sized(elem.expect_ty(), traits::TupleElem); |
e9174d1e | 427 | } |
9cc50fc6 | 428 | } |
e9174d1e SL |
429 | } |
430 | ||
b7449926 | 431 | ty::RawPtr(_) => { |
e9174d1e SL |
432 | // simple cases that are WF if their type args are WF |
433 | } | |
434 | ||
b7449926 | 435 | ty::Projection(data) => { |
e9174d1e SL |
436 | subtys.skip_current_subtree(); // subtree handled by compute_projection |
437 | self.compute_projection(data); | |
438 | } | |
439 | ||
0bf4aa26 XL |
440 | ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"), |
441 | ||
b7449926 | 442 | ty::Adt(def, substs) => { |
e9174d1e SL |
443 | // WfNominalType |
444 | let obligations = self.nominal_obligations(def.did, substs); | |
445 | self.out.extend(obligations); | |
446 | } | |
447 | ||
0731742a XL |
448 | ty::FnDef(did, substs) => { |
449 | let obligations = self.nominal_obligations(did, substs); | |
450 | self.out.extend(obligations); | |
451 | } | |
452 | ||
b7449926 | 453 | ty::Ref(r, rty, _) => { |
e9174d1e | 454 | // WfReference |
a1dfa0c6 | 455 | if !r.has_escaping_bound_vars() && !rty.has_escaping_bound_vars() { |
e9174d1e | 456 | let cause = self.cause(traits::ReferenceOutlivesReferent(ty)); |
dfeec247 XL |
457 | self.out.push(traits::Obligation::new( |
458 | cause, | |
459 | param_env, | |
460 | ty::Predicate::TypeOutlives(ty::Binder::dummy(ty::OutlivesPredicate( | |
461 | rty, r, | |
462 | ))), | |
463 | )); | |
e9174d1e SL |
464 | } |
465 | } | |
466 | ||
b7449926 | 467 | ty::Generator(..) => { |
ff7c6d11 XL |
468 | // Walk ALL the types in the generator: this will |
469 | // include the upvar types as well as the yield | |
470 | // type. Note that this is mildly distinct from | |
471 | // the closure case, where we have to be careful | |
472 | // about the signature of the closure. We don't | |
473 | // have the problem of implied bounds here since | |
474 | // generators don't take arguments. | |
475 | } | |
476 | ||
b7449926 | 477 | ty::Closure(def_id, substs) => { |
ff7c6d11 XL |
478 | // Only check the upvar types for WF, not the rest |
479 | // of the types within. This is needed because we | |
480 | // capture the signature and it may not be WF | |
481 | // without the implied bounds. Consider a closure | |
482 | // like `|x: &'a T|` -- it may be that `T: 'a` is | |
483 | // not known to hold in the creator's context (and | |
484 | // indeed the closure may not be invoked by its | |
485 | // creator, but rather turned to someone who *can* | |
486 | // verify that). | |
487 | // | |
488 | // The special treatment of closures here really | |
489 | // ought not to be necessary either; the problem | |
490 | // is related to #25860 -- there is no way for us | |
491 | // to express a fn type complete with the implied | |
492 | // bounds that it is assuming. I think in reality | |
493 | // the WF rules around fn are a bit messed up, and | |
494 | // that is the rot problem: `fn(&'a T)` should | |
495 | // probably always be WF, because it should be | |
496 | // shorthand for something like `where(T: 'a) { | |
497 | // fn(&'a T) }`, as discussed in #25860. | |
9cc50fc6 | 498 | // |
ff7c6d11 XL |
499 | // Note that we are also skipping the generic |
500 | // types. This is consistent with the `outlives` | |
501 | // code, but anyway doesn't matter: within the fn | |
502 | // body where they are created, the generics will | |
503 | // always be WF, and outside of that fn body we | |
504 | // are not directly inspecting closure types | |
505 | // anyway, except via auto trait matching (which | |
506 | // only inspects the upvar types). | |
507 | subtys.skip_current_subtree(); // subtree handled by compute_projection | |
e74abb32 | 508 | for upvar_ty in substs.as_closure().upvar_tys(def_id, self.infcx.tcx) { |
ff7c6d11 XL |
509 | self.compute(upvar_ty); |
510 | } | |
e9174d1e SL |
511 | } |
512 | ||
0731742a | 513 | ty::FnPtr(_) => { |
54a0048b | 514 | // let the loop iterate into the argument/return |
9cc50fc6 | 515 | // types appearing in the fn signature |
e9174d1e SL |
516 | } |
517 | ||
b7449926 | 518 | ty::Opaque(did, substs) => { |
5bcae85e SL |
519 | // all of the requirements on type parameters |
520 | // should've been checked by the instantiation | |
521 | // of whatever returned this exact `impl Trait`. | |
8faf50e0 | 522 | |
416331ca | 523 | // for named opaque `impl Trait` types we still need to check them |
dfeec247 | 524 | if ty::is_impl_trait_defn(self.infcx.tcx, did).is_none() { |
8faf50e0 XL |
525 | let obligations = self.nominal_obligations(did, substs); |
526 | self.out.extend(obligations); | |
527 | } | |
5bcae85e SL |
528 | } |
529 | ||
b7449926 | 530 | ty::Dynamic(data, r) => { |
e9174d1e SL |
531 | // WfObject |
532 | // | |
533 | // Here, we defer WF checking due to higher-ranked | |
534 | // regions. This is perhaps not ideal. | |
476ff2be | 535 | self.from_object_ty(ty, data, r); |
e9174d1e SL |
536 | |
537 | // FIXME(#27579) RFC also considers adding trait | |
538 | // obligations that don't refer to Self and | |
539 | // checking those | |
540 | ||
dfeec247 | 541 | let defer_to_coercion = self.infcx.tcx.features().object_safe_for_dispatch; |
e74abb32 XL |
542 | |
543 | if !defer_to_coercion { | |
544 | let cause = self.cause(traits::MiscObligation); | |
dfeec247 XL |
545 | let component_traits = data.auto_traits().chain(data.principal_def_id()); |
546 | self.out.extend(component_traits.map(|did| { | |
547 | traits::Obligation::new( | |
e74abb32 XL |
548 | cause.clone(), |
549 | param_env, | |
dfeec247 XL |
550 | ty::Predicate::ObjectSafe(did), |
551 | ) | |
552 | })); | |
e74abb32 | 553 | } |
e9174d1e SL |
554 | } |
555 | ||
556 | // Inference variables are the complicated case, since we don't | |
557 | // know what type they are. We do two things: | |
558 | // | |
559 | // 1. Check if they have been resolved, and if so proceed with | |
560 | // THAT type. | |
561 | // 2. If not, check whether this is the type that we | |
562 | // started with (ty0). In that case, we've made no | |
563 | // progress at all, so return false. Otherwise, | |
564 | // we've at least simplified things (i.e., we went | |
565 | // from `Vec<$0>: WF` to `$0: WF`, so we can | |
566 | // register a pending obligation and keep | |
567 | // moving. (Goal is that an "inductive hypothesis" | |
568 | // is satisfied to ensure termination.) | |
b7449926 | 569 | ty::Infer(_) => { |
e9174d1e | 570 | let ty = self.infcx.shallow_resolve(ty); |
dfeec247 XL |
571 | if let ty::Infer(_) = ty.kind { |
572 | // not yet resolved... | |
573 | if ty == ty0 { | |
574 | // ...this is the type we started from! no progress. | |
e9174d1e SL |
575 | return false; |
576 | } | |
577 | ||
578 | let cause = self.cause(traits::MiscObligation); | |
dfeec247 XL |
579 | self.out.push( |
580 | // ...not the type we started from, so we made progress. | |
581 | traits::Obligation::new( | |
582 | cause, | |
583 | self.param_env, | |
584 | ty::Predicate::WellFormed(ty), | |
585 | ), | |
586 | ); | |
e9174d1e SL |
587 | } else { |
588 | // Yes, resolved, proceed with the | |
589 | // result. Should never return false because | |
b7449926 | 590 | // `ty` is not a Infer. |
e9174d1e SL |
591 | assert!(self.compute(ty)); |
592 | } | |
593 | } | |
594 | } | |
595 | } | |
596 | ||
597 | // if we made it through that loop above, we made progress! | |
598 | return true; | |
599 | } | |
600 | ||
dfeec247 XL |
601 | fn nominal_obligations( |
602 | &mut self, | |
603 | def_id: DefId, | |
604 | substs: SubstsRef<'tcx>, | |
605 | ) -> Vec<traits::PredicateObligation<'tcx>> { | |
606 | let predicates = self.infcx.tcx.predicates_of(def_id).instantiate(self.infcx.tcx, substs); | |
e9174d1e | 607 | let cause = self.cause(traits::ItemObligation(def_id)); |
dfeec247 XL |
608 | predicates |
609 | .predicates | |
610 | .into_iter() | |
611 | .map(|pred| traits::Obligation::new(cause.clone(), self.param_env, pred)) | |
612 | .filter(|pred| !pred.has_escaping_bound_vars()) | |
613 | .collect() | |
e9174d1e SL |
614 | } |
615 | ||
dfeec247 XL |
616 | fn from_object_ty( |
617 | &mut self, | |
618 | ty: Ty<'tcx>, | |
619 | data: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>, | |
620 | region: ty::Region<'tcx>, | |
621 | ) { | |
e9174d1e SL |
622 | // Imagine a type like this: |
623 | // | |
624 | // trait Foo { } | |
625 | // trait Bar<'c> : 'c { } | |
626 | // | |
627 | // &'b (Foo+'c+Bar<'d>) | |
628 | // ^ | |
629 | // | |
630 | // In this case, the following relationships must hold: | |
631 | // | |
632 | // 'b <= 'c | |
633 | // 'd <= 'c | |
634 | // | |
635 | // The first conditions is due to the normal region pointer | |
636 | // rules, which say that a reference cannot outlive its | |
637 | // referent. | |
638 | // | |
639 | // The final condition may be a bit surprising. In particular, | |
640 | // you may expect that it would have been `'c <= 'd`, since | |
641 | // usually lifetimes of outer things are conservative | |
642 | // approximations for inner things. However, it works somewhat | |
643 | // differently with trait objects: here the idea is that if the | |
644 | // user specifies a region bound (`'c`, in this case) it is the | |
645 | // "master bound" that *implies* that bounds from other traits are | |
646 | // all met. (Remember that *all bounds* in a type like | |
647 | // `Foo+Bar+Zed` must be met, not just one, hence if we write | |
648 | // `Foo<'x>+Bar<'y>`, we know that the type outlives *both* 'x and | |
649 | // 'y.) | |
650 | // | |
651 | // Note: in fact we only permit builtin traits, not `Bar<'d>`, I | |
652 | // am looking forward to the future here. | |
532ac7d7 | 653 | if !data.has_escaping_bound_vars() && !region.has_escaping_bound_vars() { |
dfeec247 | 654 | let implicit_bounds = object_region_bounds(self.infcx.tcx, data); |
e9174d1e | 655 | |
476ff2be | 656 | let explicit_bound = region; |
e9174d1e | 657 | |
0bf4aa26 | 658 | self.out.reserve(implicit_bounds.len()); |
e9174d1e | 659 | for implicit_bound in implicit_bounds { |
c30ab7b3 | 660 | let cause = self.cause(traits::ObjectTypeBound(ty, explicit_bound)); |
dfeec247 XL |
661 | let outlives = |
662 | ty::Binder::dummy(ty::OutlivesPredicate(explicit_bound, implicit_bound)); | |
663 | self.out.push(traits::Obligation::new( | |
664 | cause, | |
665 | self.param_env, | |
666 | outlives.to_predicate(), | |
667 | )); | |
e9174d1e SL |
668 | } |
669 | } | |
670 | } | |
671 | } | |
672 | ||
9fa01778 | 673 | /// Given an object type like `SomeTrait + Send`, computes the lifetime |
e9174d1e SL |
674 | /// bounds that must hold on the elided self type. These are derived |
675 | /// from the declarations of `SomeTrait`, `Send`, and friends -- if | |
676 | /// they declare `trait SomeTrait : 'static`, for example, then | |
677 | /// `'static` would appear in the list. The hard work is done by | |
dfeec247 | 678 | /// `infer::required_region_bounds`, see that for more information. |
dc9dc135 XL |
679 | pub fn object_region_bounds<'tcx>( |
680 | tcx: TyCtxt<'tcx>, | |
681 | existential_predicates: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>, | |
682 | ) -> Vec<ty::Region<'tcx>> { | |
e9174d1e SL |
683 | // Since we don't actually *know* the self type for an object, |
684 | // this "open(err)" serves as a kind of dummy standin -- basically | |
0bf4aa26 | 685 | // a placeholder type. |
48663c56 | 686 | let open_ty = tcx.mk_ty_infer(ty::FreshTy(0)); |
e9174d1e | 687 | |
dfeec247 XL |
688 | let predicates = existential_predicates |
689 | .iter() | |
690 | .filter_map(|predicate| { | |
691 | if let ty::ExistentialPredicate::Projection(_) = *predicate.skip_binder() { | |
692 | None | |
693 | } else { | |
694 | Some(predicate.with_self_ty(tcx, open_ty)) | |
695 | } | |
696 | }) | |
697 | .collect(); | |
e9174d1e | 698 | |
dfeec247 | 699 | required_region_bounds(tcx, open_ty, predicates) |
e9174d1e | 700 | } |
60c5eb7d XL |
701 | |
702 | /// Find the span of a generic bound affecting an associated type. | |
703 | fn get_generic_bound_spans( | |
dfeec247 | 704 | generics: &hir::Generics<'_>, |
60c5eb7d XL |
705 | trait_name: Option<&Ident>, |
706 | assoc_item_name: Ident, | |
707 | ) -> Vec<Span> { | |
708 | let mut bounds = vec![]; | |
709 | for clause in generics.where_clause.predicates.iter() { | |
710 | if let hir::WherePredicate::BoundPredicate(pred) = clause { | |
711 | match &pred.bounded_ty.kind { | |
712 | hir::TyKind::Path(hir::QPath::Resolved(Some(ty), path)) => { | |
713 | let mut s = path.segments.iter(); | |
714 | if let (a, Some(b), None) = (s.next(), s.next(), s.next()) { | |
715 | if a.map(|s| &s.ident) == trait_name | |
716 | && b.ident == assoc_item_name | |
717 | && is_self_path(&ty.kind) | |
718 | { | |
719 | // `<Self as Foo>::Bar` | |
720 | bounds.push(pred.span); | |
721 | } | |
722 | } | |
723 | } | |
724 | hir::TyKind::Path(hir::QPath::TypeRelative(ty, segment)) => { | |
725 | if segment.ident == assoc_item_name { | |
726 | if is_self_path(&ty.kind) { | |
727 | // `Self::Bar` | |
728 | bounds.push(pred.span); | |
729 | } | |
730 | } | |
731 | } | |
732 | _ => {} | |
733 | } | |
734 | } | |
735 | } | |
736 | bounds | |
737 | } | |
738 | ||
dfeec247 | 739 | fn is_self_path(kind: &hir::TyKind<'_>) -> bool { |
60c5eb7d XL |
740 | match kind { |
741 | hir::TyKind::Path(hir::QPath::Resolved(None, path)) => { | |
742 | let mut s = path.segments.iter(); | |
743 | if let (Some(segment), None) = (s.next(), s.next()) { | |
744 | if segment.ident.name == kw::SelfUpper { | |
745 | // `type(Self)` | |
746 | return true; | |
747 | } | |
748 | } | |
749 | } | |
750 | _ => {} | |
751 | } | |
752 | false | |
753 | } |