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