]>
Commit | Line | Data |
---|---|---|
f035d41b XL |
1 | //! Confirmation. |
2 | //! | |
3 | //! Confirmation unifies the output type parameters of the trait | |
4 | //! with the values found in the obligation, possibly yielding a | |
5 | //! type error. See the [rustc dev guide] for more details. | |
6 | //! | |
7 | //! [rustc dev guide]: | |
8 | //! https://rustc-dev-guide.rust-lang.org/traits/resolution.html#confirmation | |
9 | use rustc_data_structures::stack::ensure_sufficient_stack; | |
3dfed10e | 10 | use rustc_hir::lang_items::LangItem; |
fc512014 | 11 | use rustc_hir::Constness; |
f035d41b XL |
12 | use rustc_index::bit_set::GrowableBitSet; |
13 | use rustc_infer::infer::InferOk; | |
29967ef6 | 14 | use rustc_infer::infer::LateBoundRegionConversionTime::HigherRankedType; |
f035d41b XL |
15 | use rustc_middle::ty::subst::{GenericArg, GenericArgKind, Subst, SubstsRef}; |
16 | use rustc_middle::ty::{self, Ty}; | |
17 | use rustc_middle::ty::{ToPolyTraitRef, ToPredicate, WithConstness}; | |
18 | use rustc_span::def_id::DefId; | |
19 | ||
29967ef6 | 20 | use crate::traits::project::{normalize_with_depth, normalize_with_depth_to}; |
f035d41b XL |
21 | use crate::traits::select::TraitObligationExt; |
22 | use crate::traits::util; | |
23 | use crate::traits::util::{closure_trait_ref_and_return_type, predicate_for_trait_def}; | |
1b1a35ee | 24 | use crate::traits::ImplSource; |
f035d41b XL |
25 | use crate::traits::Normalized; |
26 | use crate::traits::OutputTypeParameterMismatch; | |
27 | use crate::traits::Selection; | |
28 | use crate::traits::TraitNotObjectSafe; | |
29 | use crate::traits::{BuiltinDerivedObligation, ImplDerivedObligation}; | |
f035d41b XL |
30 | use crate::traits::{ |
31 | ImplSourceAutoImplData, ImplSourceBuiltinData, ImplSourceClosureData, | |
32 | ImplSourceDiscriminantKindData, ImplSourceFnPointerData, ImplSourceGeneratorData, | |
6a06907d XL |
33 | ImplSourceObjectData, ImplSourcePointeeData, ImplSourceTraitAliasData, |
34 | ImplSourceUserDefinedData, | |
f035d41b XL |
35 | }; |
36 | use crate::traits::{ObjectCastObligation, PredicateObligation, TraitObligation}; | |
37 | use crate::traits::{Obligation, ObligationCause}; | |
38 | use crate::traits::{SelectionError, Unimplemented}; | |
39 | ||
40 | use super::BuiltinImplConditions; | |
41 | use super::SelectionCandidate::{self, *}; | |
42 | use super::SelectionContext; | |
43 | ||
44 | use std::iter; | |
45 | ||
46 | impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | |
29967ef6 | 47 | #[instrument(level = "debug", skip(self))] |
f035d41b XL |
48 | pub(super) fn confirm_candidate( |
49 | &mut self, | |
50 | obligation: &TraitObligation<'tcx>, | |
51 | candidate: SelectionCandidate<'tcx>, | |
52 | ) -> Result<Selection<'tcx>, SelectionError<'tcx>> { | |
f035d41b XL |
53 | match candidate { |
54 | BuiltinCandidate { has_nested } => { | |
55 | let data = self.confirm_builtin_candidate(obligation, has_nested); | |
1b1a35ee | 56 | Ok(ImplSource::Builtin(data)) |
f035d41b XL |
57 | } |
58 | ||
59 | ParamCandidate(param) => { | |
fc512014 XL |
60 | let obligations = self.confirm_param_candidate(obligation, param.value); |
61 | Ok(ImplSource::Param(obligations, param.constness)) | |
f035d41b XL |
62 | } |
63 | ||
64 | ImplCandidate(impl_def_id) => { | |
1b1a35ee | 65 | Ok(ImplSource::UserDefined(self.confirm_impl_candidate(obligation, impl_def_id))) |
f035d41b XL |
66 | } |
67 | ||
68 | AutoImplCandidate(trait_def_id) => { | |
69 | let data = self.confirm_auto_impl_candidate(obligation, trait_def_id); | |
1b1a35ee | 70 | Ok(ImplSource::AutoImpl(data)) |
f035d41b XL |
71 | } |
72 | ||
29967ef6 XL |
73 | ProjectionCandidate(idx) => { |
74 | let obligations = self.confirm_projection_candidate(obligation, idx)?; | |
fc512014 XL |
75 | // FIXME(jschievink): constness |
76 | Ok(ImplSource::Param(obligations, Constness::NotConst)) | |
29967ef6 XL |
77 | } |
78 | ||
79 | ObjectCandidate(idx) => { | |
80 | let data = self.confirm_object_candidate(obligation, idx)?; | |
81 | Ok(ImplSource::Object(data)) | |
f035d41b XL |
82 | } |
83 | ||
84 | ClosureCandidate => { | |
85 | let vtable_closure = self.confirm_closure_candidate(obligation)?; | |
1b1a35ee | 86 | Ok(ImplSource::Closure(vtable_closure)) |
f035d41b XL |
87 | } |
88 | ||
89 | GeneratorCandidate => { | |
90 | let vtable_generator = self.confirm_generator_candidate(obligation)?; | |
1b1a35ee | 91 | Ok(ImplSource::Generator(vtable_generator)) |
f035d41b XL |
92 | } |
93 | ||
94 | FnPointerCandidate => { | |
95 | let data = self.confirm_fn_pointer_candidate(obligation)?; | |
1b1a35ee | 96 | Ok(ImplSource::FnPointer(data)) |
f035d41b XL |
97 | } |
98 | ||
99 | DiscriminantKindCandidate => { | |
1b1a35ee | 100 | Ok(ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData)) |
f035d41b XL |
101 | } |
102 | ||
6a06907d XL |
103 | PointeeCandidate => Ok(ImplSource::Pointee(ImplSourcePointeeData)), |
104 | ||
f035d41b XL |
105 | TraitAliasCandidate(alias_def_id) => { |
106 | let data = self.confirm_trait_alias_candidate(obligation, alias_def_id); | |
1b1a35ee | 107 | Ok(ImplSource::TraitAlias(data)) |
f035d41b XL |
108 | } |
109 | ||
f035d41b XL |
110 | BuiltinObjectCandidate => { |
111 | // This indicates something like `Trait + Send: Send`. In this case, we know that | |
112 | // this holds because that's what the object type is telling us, and there's really | |
113 | // no additional obligations to prove and no types in particular to unify, etc. | |
fc512014 | 114 | Ok(ImplSource::Param(Vec::new(), Constness::NotConst)) |
f035d41b XL |
115 | } |
116 | ||
117 | BuiltinUnsizeCandidate => { | |
118 | let data = self.confirm_builtin_unsize_candidate(obligation)?; | |
1b1a35ee | 119 | Ok(ImplSource::Builtin(data)) |
f035d41b XL |
120 | } |
121 | } | |
122 | } | |
123 | ||
29967ef6 XL |
124 | fn confirm_projection_candidate( |
125 | &mut self, | |
126 | obligation: &TraitObligation<'tcx>, | |
127 | idx: usize, | |
128 | ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
f035d41b | 129 | self.infcx.commit_unconditionally(|_| { |
29967ef6 XL |
130 | let tcx = self.tcx(); |
131 | ||
132 | let trait_predicate = self.infcx.shallow_resolve(obligation.predicate); | |
133 | let placeholder_trait_predicate = | |
fc512014 | 134 | self.infcx().replace_bound_vars_with_placeholders(trait_predicate); |
29967ef6 XL |
135 | let placeholder_self_ty = placeholder_trait_predicate.self_ty(); |
136 | let (def_id, substs) = match *placeholder_self_ty.kind() { | |
137 | ty::Projection(proj) => (proj.item_def_id, proj.substs), | |
138 | ty::Opaque(def_id, substs) => (def_id, substs), | |
139 | _ => bug!("projection candidate for unexpected type: {:?}", placeholder_self_ty), | |
140 | }; | |
141 | ||
142 | let candidate_predicate = tcx.item_bounds(def_id)[idx].subst(tcx, substs); | |
143 | let candidate = candidate_predicate | |
144 | .to_opt_poly_trait_ref() | |
145 | .expect("projection candidate is not a trait predicate"); | |
146 | let mut obligations = Vec::new(); | |
147 | let candidate = normalize_with_depth_to( | |
148 | self, | |
149 | obligation.param_env, | |
150 | obligation.cause.clone(), | |
151 | obligation.recursion_depth + 1, | |
fc512014 | 152 | candidate, |
29967ef6 XL |
153 | &mut obligations, |
154 | ); | |
155 | ||
156 | obligations.extend(self.infcx.commit_if_ok(|_| { | |
157 | self.infcx | |
158 | .at(&obligation.cause, obligation.param_env) | |
fc512014 | 159 | .sup(placeholder_trait_predicate.trait_ref.to_poly_trait_ref(), candidate.value) |
29967ef6 XL |
160 | .map(|InferOk { obligations, .. }| obligations) |
161 | .map_err(|_| Unimplemented) | |
162 | })?); | |
163 | ||
164 | if let ty::Projection(..) = placeholder_self_ty.kind() { | |
165 | for predicate in tcx.predicates_of(def_id).instantiate_own(tcx, substs).predicates { | |
166 | let normalized = normalize_with_depth_to( | |
167 | self, | |
168 | obligation.param_env, | |
169 | obligation.cause.clone(), | |
170 | obligation.recursion_depth + 1, | |
fc512014 | 171 | predicate, |
29967ef6 XL |
172 | &mut obligations, |
173 | ); | |
174 | obligations.push(Obligation::with_depth( | |
175 | obligation.cause.clone(), | |
176 | obligation.recursion_depth + 1, | |
177 | obligation.param_env, | |
178 | normalized, | |
179 | )); | |
180 | } | |
181 | } | |
182 | ||
183 | Ok(obligations) | |
f035d41b XL |
184 | }) |
185 | } | |
186 | ||
187 | fn confirm_param_candidate( | |
188 | &mut self, | |
189 | obligation: &TraitObligation<'tcx>, | |
190 | param: ty::PolyTraitRef<'tcx>, | |
191 | ) -> Vec<PredicateObligation<'tcx>> { | |
29967ef6 | 192 | debug!(?obligation, ?param, "confirm_param_candidate"); |
f035d41b XL |
193 | |
194 | // During evaluation, we already checked that this | |
195 | // where-clause trait-ref could be unified with the obligation | |
196 | // trait-ref. Repeat that unification now without any | |
197 | // transactional boundary; it should not fail. | |
198 | match self.match_where_clause_trait_ref(obligation, param) { | |
199 | Ok(obligations) => obligations, | |
200 | Err(()) => { | |
201 | bug!( | |
202 | "Where clause `{:?}` was applicable to `{:?}` but now is not", | |
203 | param, | |
204 | obligation | |
205 | ); | |
206 | } | |
207 | } | |
208 | } | |
209 | ||
210 | fn confirm_builtin_candidate( | |
211 | &mut self, | |
212 | obligation: &TraitObligation<'tcx>, | |
213 | has_nested: bool, | |
214 | ) -> ImplSourceBuiltinData<PredicateObligation<'tcx>> { | |
29967ef6 | 215 | debug!(?obligation, ?has_nested, "confirm_builtin_candidate"); |
f035d41b XL |
216 | |
217 | let lang_items = self.tcx().lang_items(); | |
218 | let obligations = if has_nested { | |
219 | let trait_def = obligation.predicate.def_id(); | |
220 | let conditions = if Some(trait_def) == lang_items.sized_trait() { | |
221 | self.sized_conditions(obligation) | |
222 | } else if Some(trait_def) == lang_items.copy_trait() { | |
223 | self.copy_clone_conditions(obligation) | |
224 | } else if Some(trait_def) == lang_items.clone_trait() { | |
225 | self.copy_clone_conditions(obligation) | |
226 | } else { | |
227 | bug!("unexpected builtin trait {:?}", trait_def) | |
228 | }; | |
229 | let nested = match conditions { | |
230 | BuiltinImplConditions::Where(nested) => nested, | |
231 | _ => bug!("obligation {:?} had matched a builtin impl but now doesn't", obligation), | |
232 | }; | |
233 | ||
234 | let cause = obligation.derived_cause(BuiltinDerivedObligation); | |
235 | ensure_sufficient_stack(|| { | |
236 | self.collect_predicates_for_types( | |
237 | obligation.param_env, | |
238 | cause, | |
239 | obligation.recursion_depth + 1, | |
240 | trait_def, | |
241 | nested, | |
242 | ) | |
243 | }) | |
244 | } else { | |
245 | vec![] | |
246 | }; | |
247 | ||
29967ef6 | 248 | debug!(?obligations); |
f035d41b XL |
249 | |
250 | ImplSourceBuiltinData { nested: obligations } | |
251 | } | |
252 | ||
253 | /// This handles the case where a `auto trait Foo` impl is being used. | |
254 | /// The idea is that the impl applies to `X : Foo` if the following conditions are met: | |
255 | /// | |
256 | /// 1. For each constituent type `Y` in `X`, `Y : Foo` holds | |
257 | /// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds. | |
258 | fn confirm_auto_impl_candidate( | |
259 | &mut self, | |
260 | obligation: &TraitObligation<'tcx>, | |
261 | trait_def_id: DefId, | |
262 | ) -> ImplSourceAutoImplData<PredicateObligation<'tcx>> { | |
29967ef6 | 263 | debug!(?obligation, ?trait_def_id, "confirm_auto_impl_candidate"); |
f035d41b | 264 | |
fc512014 XL |
265 | let self_ty = self.infcx.shallow_resolve(obligation.predicate.self_ty()); |
266 | let types = self.constituent_types_for_ty(self_ty); | |
f035d41b XL |
267 | self.vtable_auto_impl(obligation, trait_def_id, types) |
268 | } | |
269 | ||
270 | /// See `confirm_auto_impl_candidate`. | |
271 | fn vtable_auto_impl( | |
272 | &mut self, | |
273 | obligation: &TraitObligation<'tcx>, | |
274 | trait_def_id: DefId, | |
cdc7bbd5 | 275 | nested: ty::Binder<'tcx, Vec<Ty<'tcx>>>, |
f035d41b | 276 | ) -> ImplSourceAutoImplData<PredicateObligation<'tcx>> { |
29967ef6 | 277 | debug!(?nested, "vtable_auto_impl"); |
f035d41b XL |
278 | ensure_sufficient_stack(|| { |
279 | let cause = obligation.derived_cause(BuiltinDerivedObligation); | |
280 | let mut obligations = self.collect_predicates_for_types( | |
281 | obligation.param_env, | |
282 | cause, | |
283 | obligation.recursion_depth + 1, | |
284 | trait_def_id, | |
285 | nested, | |
286 | ); | |
287 | ||
288 | let trait_obligations: Vec<PredicateObligation<'_>> = | |
289 | self.infcx.commit_unconditionally(|_| { | |
290 | let poly_trait_ref = obligation.predicate.to_poly_trait_ref(); | |
fc512014 | 291 | let trait_ref = self.infcx.replace_bound_vars_with_placeholders(poly_trait_ref); |
f035d41b XL |
292 | let cause = obligation.derived_cause(ImplDerivedObligation); |
293 | self.impl_or_trait_obligations( | |
294 | cause, | |
295 | obligation.recursion_depth + 1, | |
296 | obligation.param_env, | |
297 | trait_def_id, | |
298 | &trait_ref.substs, | |
299 | ) | |
300 | }); | |
301 | ||
302 | // Adds the predicates from the trait. Note that this contains a `Self: Trait` | |
303 | // predicate as usual. It won't have any effect since auto traits are coinductive. | |
304 | obligations.extend(trait_obligations); | |
305 | ||
29967ef6 | 306 | debug!(?obligations, "vtable_auto_impl"); |
f035d41b XL |
307 | |
308 | ImplSourceAutoImplData { trait_def_id, nested: obligations } | |
309 | }) | |
310 | } | |
311 | ||
312 | fn confirm_impl_candidate( | |
313 | &mut self, | |
314 | obligation: &TraitObligation<'tcx>, | |
315 | impl_def_id: DefId, | |
316 | ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> { | |
29967ef6 | 317 | debug!(?obligation, ?impl_def_id, "confirm_impl_candidate"); |
f035d41b XL |
318 | |
319 | // First, create the substitutions by matching the impl again, | |
320 | // this time not in a probe. | |
321 | self.infcx.commit_unconditionally(|_| { | |
322 | let substs = self.rematch_impl(impl_def_id, obligation); | |
29967ef6 | 323 | debug!(?substs, "impl substs"); |
f035d41b XL |
324 | let cause = obligation.derived_cause(ImplDerivedObligation); |
325 | ensure_sufficient_stack(|| { | |
326 | self.vtable_impl( | |
327 | impl_def_id, | |
328 | substs, | |
329 | cause, | |
330 | obligation.recursion_depth + 1, | |
331 | obligation.param_env, | |
332 | ) | |
333 | }) | |
334 | }) | |
335 | } | |
336 | ||
337 | fn vtable_impl( | |
338 | &mut self, | |
339 | impl_def_id: DefId, | |
b9856134 | 340 | substs: Normalized<'tcx, SubstsRef<'tcx>>, |
f035d41b XL |
341 | cause: ObligationCause<'tcx>, |
342 | recursion_depth: usize, | |
343 | param_env: ty::ParamEnv<'tcx>, | |
344 | ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> { | |
29967ef6 | 345 | debug!(?impl_def_id, ?substs, ?recursion_depth, "vtable_impl"); |
f035d41b XL |
346 | |
347 | let mut impl_obligations = self.impl_or_trait_obligations( | |
348 | cause, | |
349 | recursion_depth, | |
350 | param_env, | |
351 | impl_def_id, | |
352 | &substs.value, | |
353 | ); | |
354 | ||
29967ef6 | 355 | debug!(?impl_obligations, "vtable_impl"); |
f035d41b XL |
356 | |
357 | // Because of RFC447, the impl-trait-ref and obligations | |
358 | // are sufficient to determine the impl substs, without | |
359 | // relying on projections in the impl-trait-ref. | |
360 | // | |
361 | // e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V` | |
b9856134 | 362 | impl_obligations.extend(substs.obligations); |
f035d41b | 363 | |
b9856134 | 364 | ImplSourceUserDefinedData { impl_def_id, substs: substs.value, nested: impl_obligations } |
f035d41b XL |
365 | } |
366 | ||
367 | fn confirm_object_candidate( | |
368 | &mut self, | |
369 | obligation: &TraitObligation<'tcx>, | |
29967ef6 XL |
370 | index: usize, |
371 | ) -> Result<ImplSourceObjectData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
372 | let tcx = self.tcx(); | |
373 | debug!(?obligation, ?index, "confirm_object_candidate"); | |
374 | ||
fc512014 | 375 | let trait_predicate = self.infcx.replace_bound_vars_with_placeholders(obligation.predicate); |
29967ef6 XL |
376 | let self_ty = self.infcx.shallow_resolve(trait_predicate.self_ty()); |
377 | let obligation_trait_ref = ty::Binder::dummy(trait_predicate.trait_ref); | |
fc512014 XL |
378 | let data = match *self_ty.kind() { |
379 | ty::Dynamic(data, ..) => data, | |
f035d41b XL |
380 | _ => span_bug!(obligation.cause.span, "object candidate with non-object"), |
381 | }; | |
382 | ||
fc512014 XL |
383 | let object_trait_ref = data.principal().unwrap_or_else(|| { |
384 | span_bug!(obligation.cause.span, "object candidate with no principal") | |
385 | }); | |
386 | let object_trait_ref = self | |
387 | .infcx | |
388 | .replace_bound_vars_with_fresh_vars( | |
389 | obligation.cause.span, | |
390 | HigherRankedType, | |
391 | object_trait_ref, | |
392 | ) | |
393 | .0; | |
394 | let object_trait_ref = object_trait_ref.with_self_ty(self.tcx(), self_ty); | |
29967ef6 | 395 | |
f035d41b | 396 | let mut nested = vec![]; |
f035d41b | 397 | |
29967ef6 | 398 | let mut supertraits = util::supertraits(tcx, ty::Binder::dummy(object_trait_ref)); |
f035d41b | 399 | |
29967ef6 XL |
400 | // For each of the non-matching predicates that |
401 | // we pass over, we sum up the set of number of vtable | |
402 | // entries, so that we can compute the offset for the selected | |
403 | // trait. | |
404 | let vtable_base = supertraits | |
405 | .by_ref() | |
406 | .take(index) | |
407 | .map(|t| super::util::count_own_vtable_entries(tcx, t)) | |
408 | .sum(); | |
f035d41b | 409 | |
29967ef6 XL |
410 | let unnormalized_upcast_trait_ref = |
411 | supertraits.next().expect("supertraits iterator no longer has as many elements"); | |
412 | ||
413 | let upcast_trait_ref = normalize_with_depth_to( | |
414 | self, | |
415 | obligation.param_env, | |
416 | obligation.cause.clone(), | |
417 | obligation.recursion_depth + 1, | |
fc512014 | 418 | unnormalized_upcast_trait_ref, |
29967ef6 XL |
419 | &mut nested, |
420 | ); | |
421 | ||
422 | nested.extend(self.infcx.commit_if_ok(|_| { | |
423 | self.infcx | |
424 | .at(&obligation.cause, obligation.param_env) | |
425 | .sup(obligation_trait_ref, upcast_trait_ref) | |
426 | .map(|InferOk { obligations, .. }| obligations) | |
427 | .map_err(|_| Unimplemented) | |
428 | })?); | |
429 | ||
430 | // Check supertraits hold. This is so that their associated type bounds | |
431 | // will be checked in the code below. | |
432 | for super_trait in tcx | |
433 | .super_predicates_of(trait_predicate.def_id()) | |
434 | .instantiate(tcx, trait_predicate.trait_ref.substs) | |
435 | .predicates | |
436 | .into_iter() | |
437 | { | |
5869c6ff | 438 | if let ty::PredicateKind::Trait(..) = super_trait.kind().skip_binder() { |
29967ef6 XL |
439 | let normalized_super_trait = normalize_with_depth_to( |
440 | self, | |
441 | obligation.param_env, | |
442 | obligation.cause.clone(), | |
443 | obligation.recursion_depth + 1, | |
fc512014 | 444 | super_trait, |
29967ef6 XL |
445 | &mut nested, |
446 | ); | |
447 | nested.push(Obligation::new( | |
448 | obligation.cause.clone(), | |
fc512014 | 449 | obligation.param_env, |
29967ef6 XL |
450 | normalized_super_trait, |
451 | )); | |
452 | } | |
f035d41b XL |
453 | } |
454 | ||
29967ef6 XL |
455 | let assoc_types: Vec<_> = tcx |
456 | .associated_items(trait_predicate.def_id()) | |
457 | .in_definition_order() | |
458 | .filter_map( | |
459 | |item| if item.kind == ty::AssocKind::Type { Some(item.def_id) } else { None }, | |
460 | ) | |
461 | .collect(); | |
462 | ||
463 | for assoc_type in assoc_types { | |
464 | if !tcx.generics_of(assoc_type).params.is_empty() { | |
cdc7bbd5 | 465 | tcx.sess.delay_span_bug( |
29967ef6 | 466 | obligation.cause.span, |
cdc7bbd5 | 467 | "GATs in trait object shouldn't have been considered", |
29967ef6 | 468 | ); |
cdc7bbd5 | 469 | return Err(SelectionError::Unimplemented); |
29967ef6 XL |
470 | } |
471 | // This maybe belongs in wf, but that can't (doesn't) handle | |
472 | // higher-ranked things. | |
473 | // Prevent, e.g., `dyn Iterator<Item = str>`. | |
474 | for bound in self.tcx().item_bounds(assoc_type) { | |
475 | let subst_bound = bound.subst(tcx, trait_predicate.trait_ref.substs); | |
476 | let normalized_bound = normalize_with_depth_to( | |
477 | self, | |
478 | obligation.param_env, | |
479 | obligation.cause.clone(), | |
480 | obligation.recursion_depth + 1, | |
fc512014 | 481 | subst_bound, |
29967ef6 XL |
482 | &mut nested, |
483 | ); | |
484 | nested.push(Obligation::new( | |
485 | obligation.cause.clone(), | |
fc512014 | 486 | obligation.param_env, |
29967ef6 XL |
487 | normalized_bound, |
488 | )); | |
489 | } | |
490 | } | |
491 | ||
492 | debug!(?nested, "object nested obligations"); | |
493 | Ok(ImplSourceObjectData { upcast_trait_ref, vtable_base, nested }) | |
f035d41b XL |
494 | } |
495 | ||
496 | fn confirm_fn_pointer_candidate( | |
497 | &mut self, | |
498 | obligation: &TraitObligation<'tcx>, | |
499 | ) -> Result<ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> | |
500 | { | |
29967ef6 | 501 | debug!(?obligation, "confirm_fn_pointer_candidate"); |
f035d41b XL |
502 | |
503 | // Okay to skip binder; it is reintroduced below. | |
504 | let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder()); | |
505 | let sig = self_ty.fn_sig(self.tcx()); | |
506 | let trait_ref = closure_trait_ref_and_return_type( | |
507 | self.tcx(), | |
508 | obligation.predicate.def_id(), | |
509 | self_ty, | |
510 | sig, | |
511 | util::TupleArgumentsFlag::Yes, | |
512 | ) | |
513 | .map_bound(|(trait_ref, _)| trait_ref); | |
514 | ||
29967ef6 XL |
515 | let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| { |
516 | normalize_with_depth( | |
f035d41b XL |
517 | self, |
518 | obligation.param_env, | |
519 | obligation.cause.clone(), | |
520 | obligation.recursion_depth + 1, | |
fc512014 | 521 | trait_ref, |
f035d41b XL |
522 | ) |
523 | }); | |
524 | ||
29967ef6 | 525 | obligations.extend(self.confirm_poly_trait_refs( |
f035d41b XL |
526 | obligation.cause.clone(), |
527 | obligation.param_env, | |
528 | obligation.predicate.to_poly_trait_ref(), | |
529 | trait_ref, | |
29967ef6 | 530 | )?); |
f035d41b XL |
531 | Ok(ImplSourceFnPointerData { fn_ty: self_ty, nested: obligations }) |
532 | } | |
533 | ||
534 | fn confirm_trait_alias_candidate( | |
535 | &mut self, | |
536 | obligation: &TraitObligation<'tcx>, | |
537 | alias_def_id: DefId, | |
538 | ) -> ImplSourceTraitAliasData<'tcx, PredicateObligation<'tcx>> { | |
29967ef6 | 539 | debug!(?obligation, ?alias_def_id, "confirm_trait_alias_candidate"); |
f035d41b XL |
540 | |
541 | self.infcx.commit_unconditionally(|_| { | |
fc512014 | 542 | let predicate = self.infcx().replace_bound_vars_with_placeholders(obligation.predicate); |
f035d41b XL |
543 | let trait_ref = predicate.trait_ref; |
544 | let trait_def_id = trait_ref.def_id; | |
545 | let substs = trait_ref.substs; | |
546 | ||
547 | let trait_obligations = self.impl_or_trait_obligations( | |
548 | obligation.cause.clone(), | |
549 | obligation.recursion_depth, | |
550 | obligation.param_env, | |
551 | trait_def_id, | |
552 | &substs, | |
553 | ); | |
554 | ||
29967ef6 | 555 | debug!(?trait_def_id, ?trait_obligations, "trait alias obligations"); |
f035d41b XL |
556 | |
557 | ImplSourceTraitAliasData { alias_def_id, substs, nested: trait_obligations } | |
558 | }) | |
559 | } | |
560 | ||
561 | fn confirm_generator_candidate( | |
562 | &mut self, | |
563 | obligation: &TraitObligation<'tcx>, | |
564 | ) -> Result<ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> | |
565 | { | |
566 | // Okay to skip binder because the substs on generator types never | |
567 | // touch bound regions, they just capture the in-scope | |
568 | // type/region parameters. | |
569 | let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder()); | |
1b1a35ee | 570 | let (generator_def_id, substs) = match *self_ty.kind() { |
f035d41b XL |
571 | ty::Generator(id, substs, _) => (id, substs), |
572 | _ => bug!("closure candidate for non-closure {:?}", obligation), | |
573 | }; | |
574 | ||
29967ef6 | 575 | debug!(?obligation, ?generator_def_id, ?substs, "confirm_generator_candidate"); |
f035d41b XL |
576 | |
577 | let trait_ref = self.generator_trait_ref_unnormalized(obligation, substs); | |
578 | let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| { | |
579 | normalize_with_depth( | |
580 | self, | |
581 | obligation.param_env, | |
582 | obligation.cause.clone(), | |
583 | obligation.recursion_depth + 1, | |
fc512014 | 584 | trait_ref, |
f035d41b XL |
585 | ) |
586 | }); | |
587 | ||
29967ef6 | 588 | debug!(?trait_ref, ?obligations, "generator candidate obligations"); |
f035d41b XL |
589 | |
590 | obligations.extend(self.confirm_poly_trait_refs( | |
591 | obligation.cause.clone(), | |
592 | obligation.param_env, | |
593 | obligation.predicate.to_poly_trait_ref(), | |
594 | trait_ref, | |
595 | )?); | |
596 | ||
597 | Ok(ImplSourceGeneratorData { generator_def_id, substs, nested: obligations }) | |
598 | } | |
599 | ||
600 | fn confirm_closure_candidate( | |
601 | &mut self, | |
602 | obligation: &TraitObligation<'tcx>, | |
603 | ) -> Result<ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
29967ef6 | 604 | debug!(?obligation, "confirm_closure_candidate"); |
f035d41b XL |
605 | |
606 | let kind = self | |
607 | .tcx() | |
608 | .fn_trait_kind_from_lang_item(obligation.predicate.def_id()) | |
609 | .unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation)); | |
610 | ||
611 | // Okay to skip binder because the substs on closure types never | |
612 | // touch bound regions, they just capture the in-scope | |
613 | // type/region parameters. | |
614 | let self_ty = self.infcx.shallow_resolve(obligation.self_ty().skip_binder()); | |
1b1a35ee | 615 | let (closure_def_id, substs) = match *self_ty.kind() { |
f035d41b XL |
616 | ty::Closure(id, substs) => (id, substs), |
617 | _ => bug!("closure candidate for non-closure {:?}", obligation), | |
618 | }; | |
619 | ||
620 | let trait_ref = self.closure_trait_ref_unnormalized(obligation, substs); | |
621 | let Normalized { value: trait_ref, mut obligations } = ensure_sufficient_stack(|| { | |
622 | normalize_with_depth( | |
623 | self, | |
624 | obligation.param_env, | |
625 | obligation.cause.clone(), | |
626 | obligation.recursion_depth + 1, | |
fc512014 | 627 | trait_ref, |
f035d41b XL |
628 | ) |
629 | }); | |
630 | ||
29967ef6 | 631 | debug!(?closure_def_id, ?trait_ref, ?obligations, "confirm closure candidate obligations"); |
f035d41b XL |
632 | |
633 | obligations.extend(self.confirm_poly_trait_refs( | |
634 | obligation.cause.clone(), | |
635 | obligation.param_env, | |
636 | obligation.predicate.to_poly_trait_ref(), | |
637 | trait_ref, | |
638 | )?); | |
639 | ||
640 | // FIXME: Chalk | |
641 | ||
642 | if !self.tcx().sess.opts.debugging_opts.chalk { | |
643 | obligations.push(Obligation::new( | |
644 | obligation.cause.clone(), | |
645 | obligation.param_env, | |
5869c6ff | 646 | ty::PredicateKind::ClosureKind(closure_def_id, substs, kind) |
f035d41b XL |
647 | .to_predicate(self.tcx()), |
648 | )); | |
649 | } | |
650 | ||
651 | Ok(ImplSourceClosureData { closure_def_id, substs, nested: obligations }) | |
652 | } | |
653 | ||
654 | /// In the case of closure types and fn pointers, | |
655 | /// we currently treat the input type parameters on the trait as | |
656 | /// outputs. This means that when we have a match we have only | |
657 | /// considered the self type, so we have to go back and make sure | |
658 | /// to relate the argument types too. This is kind of wrong, but | |
659 | /// since we control the full set of impls, also not that wrong, | |
660 | /// and it DOES yield better error messages (since we don't report | |
661 | /// errors as if there is no applicable impl, but rather report | |
662 | /// errors are about mismatched argument types. | |
663 | /// | |
664 | /// Here is an example. Imagine we have a closure expression | |
665 | /// and we desugared it so that the type of the expression is | |
666 | /// `Closure`, and `Closure` expects `i32` as argument. Then it | |
667 | /// is "as if" the compiler generated this impl: | |
668 | /// | |
669 | /// impl Fn(i32) for Closure { ... } | |
670 | /// | |
671 | /// Now imagine our obligation is `Closure: Fn(usize)`. So far | |
672 | /// we have matched the self type `Closure`. At this point we'll | |
673 | /// compare the `i32` to `usize` and generate an error. | |
674 | /// | |
675 | /// Note that this checking occurs *after* the impl has selected, | |
676 | /// because these output type parameters should not affect the | |
677 | /// selection of the impl. Therefore, if there is a mismatch, we | |
678 | /// report an error to the user. | |
679 | fn confirm_poly_trait_refs( | |
680 | &mut self, | |
681 | obligation_cause: ObligationCause<'tcx>, | |
682 | obligation_param_env: ty::ParamEnv<'tcx>, | |
683 | obligation_trait_ref: ty::PolyTraitRef<'tcx>, | |
684 | expected_trait_ref: ty::PolyTraitRef<'tcx>, | |
685 | ) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
686 | self.infcx | |
687 | .at(&obligation_cause, obligation_param_env) | |
688 | .sup(obligation_trait_ref, expected_trait_ref) | |
689 | .map(|InferOk { obligations, .. }| obligations) | |
690 | .map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e)) | |
691 | } | |
692 | ||
693 | fn confirm_builtin_unsize_candidate( | |
694 | &mut self, | |
695 | obligation: &TraitObligation<'tcx>, | |
696 | ) -> Result<ImplSourceBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> { | |
697 | let tcx = self.tcx(); | |
698 | ||
699 | // `assemble_candidates_for_unsizing` should ensure there are no late-bound | |
700 | // regions here. See the comment there for more details. | |
701 | let source = self.infcx.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap()); | |
702 | let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1); | |
703 | let target = self.infcx.shallow_resolve(target); | |
704 | ||
29967ef6 | 705 | debug!(?source, ?target, "confirm_builtin_unsize_candidate"); |
f035d41b XL |
706 | |
707 | let mut nested = vec![]; | |
1b1a35ee | 708 | match (source.kind(), target.kind()) { |
f035d41b XL |
709 | // Trait+Kx+'a -> Trait+Ky+'b (upcasts). |
710 | (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => { | |
711 | // See `assemble_candidates_for_unsizing` for more info. | |
fc512014 XL |
712 | let iter = data_a |
713 | .principal() | |
714 | .map(|b| b.map_bound(ty::ExistentialPredicate::Trait)) | |
715 | .into_iter() | |
716 | .chain( | |
717 | data_a | |
718 | .projection_bounds() | |
719 | .map(|b| b.map_bound(ty::ExistentialPredicate::Projection)), | |
720 | ) | |
721 | .chain( | |
722 | data_b | |
723 | .auto_traits() | |
724 | .map(ty::ExistentialPredicate::AutoTrait) | |
725 | .map(ty::Binder::dummy), | |
726 | ); | |
727 | let existential_predicates = tcx.mk_poly_existential_predicates(iter); | |
f035d41b XL |
728 | let source_trait = tcx.mk_dynamic(existential_predicates, r_b); |
729 | ||
730 | // Require that the traits involved in this upcast are **equal**; | |
731 | // only the **lifetime bound** is changed. | |
732 | let InferOk { obligations, .. } = self | |
733 | .infcx | |
734 | .at(&obligation.cause, obligation.param_env) | |
735 | .sup(target, source_trait) | |
736 | .map_err(|_| Unimplemented)?; | |
737 | nested.extend(obligations); | |
738 | ||
739 | // Register one obligation for 'a: 'b. | |
740 | let cause = ObligationCause::new( | |
741 | obligation.cause.span, | |
742 | obligation.cause.body_id, | |
743 | ObjectCastObligation(target), | |
744 | ); | |
745 | let outlives = ty::OutlivesPredicate(r_a, r_b); | |
746 | nested.push(Obligation::with_depth( | |
747 | cause, | |
748 | obligation.recursion_depth + 1, | |
749 | obligation.param_env, | |
cdc7bbd5 | 750 | obligation.predicate.rebind(outlives).to_predicate(tcx), |
f035d41b XL |
751 | )); |
752 | } | |
753 | ||
754 | // `T` -> `Trait` | |
755 | (_, &ty::Dynamic(ref data, r)) => { | |
756 | let mut object_dids = data.auto_traits().chain(data.principal_def_id()); | |
757 | if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) { | |
758 | return Err(TraitNotObjectSafe(did)); | |
759 | } | |
760 | ||
761 | let cause = ObligationCause::new( | |
762 | obligation.cause.span, | |
763 | obligation.cause.body_id, | |
764 | ObjectCastObligation(target), | |
765 | ); | |
766 | ||
767 | let predicate_to_obligation = |predicate| { | |
768 | Obligation::with_depth( | |
769 | cause.clone(), | |
770 | obligation.recursion_depth + 1, | |
771 | obligation.param_env, | |
772 | predicate, | |
773 | ) | |
774 | }; | |
775 | ||
776 | // Create obligations: | |
777 | // - Casting `T` to `Trait` | |
778 | // - For all the various builtin bounds attached to the object cast. (In other | |
779 | // words, if the object type is `Foo + Send`, this would create an obligation for | |
780 | // the `Send` check.) | |
781 | // - Projection predicates | |
782 | nested.extend( | |
783 | data.iter().map(|predicate| { | |
784 | predicate_to_obligation(predicate.with_self_ty(tcx, source)) | |
785 | }), | |
786 | ); | |
787 | ||
788 | // We can only make objects from sized types. | |
789 | let tr = ty::TraitRef::new( | |
3dfed10e | 790 | tcx.require_lang_item(LangItem::Sized, None), |
f035d41b XL |
791 | tcx.mk_substs_trait(source, &[]), |
792 | ); | |
793 | nested.push(predicate_to_obligation(tr.without_const().to_predicate(tcx))); | |
794 | ||
795 | // If the type is `Foo + 'a`, ensure that the type | |
796 | // being cast to `Foo + 'a` outlives `'a`: | |
797 | let outlives = ty::OutlivesPredicate(source, r); | |
798 | nested.push(predicate_to_obligation(ty::Binder::dummy(outlives).to_predicate(tcx))); | |
799 | } | |
800 | ||
801 | // `[T; n]` -> `[T]` | |
802 | (&ty::Array(a, _), &ty::Slice(b)) => { | |
803 | let InferOk { obligations, .. } = self | |
804 | .infcx | |
805 | .at(&obligation.cause, obligation.param_env) | |
806 | .eq(b, a) | |
807 | .map_err(|_| Unimplemented)?; | |
808 | nested.extend(obligations); | |
809 | } | |
810 | ||
811 | // `Struct<T>` -> `Struct<U>` | |
812 | (&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => { | |
813 | let maybe_unsizing_param_idx = |arg: GenericArg<'tcx>| match arg.unpack() { | |
1b1a35ee | 814 | GenericArgKind::Type(ty) => match ty.kind() { |
f035d41b XL |
815 | ty::Param(p) => Some(p.index), |
816 | _ => None, | |
817 | }, | |
818 | ||
819 | // Lifetimes aren't allowed to change during unsizing. | |
820 | GenericArgKind::Lifetime(_) => None, | |
821 | ||
822 | GenericArgKind::Const(ct) => match ct.val { | |
823 | ty::ConstKind::Param(p) => Some(p.index), | |
824 | _ => None, | |
825 | }, | |
826 | }; | |
827 | ||
5869c6ff XL |
828 | // FIXME(eddyb) cache this (including computing `unsizing_params`) |
829 | // by putting it in a query; it would only need the `DefId` as it | |
830 | // looks at declared field types, not anything substituted. | |
831 | ||
f035d41b XL |
832 | // The last field of the structure has to exist and contain type/const parameters. |
833 | let (tail_field, prefix_fields) = | |
834 | def.non_enum_variant().fields.split_last().ok_or(Unimplemented)?; | |
835 | let tail_field_ty = tcx.type_of(tail_field.did); | |
836 | ||
837 | let mut unsizing_params = GrowableBitSet::new_empty(); | |
5869c6ff XL |
838 | if tcx.features().relaxed_struct_unsize { |
839 | for arg in tail_field_ty.walk() { | |
840 | if let Some(i) = maybe_unsizing_param_idx(arg) { | |
841 | unsizing_params.insert(i); | |
842 | } | |
f035d41b | 843 | } |
f035d41b | 844 | |
5869c6ff XL |
845 | // Ensure none of the other fields mention the parameters used |
846 | // in unsizing. | |
847 | for field in prefix_fields { | |
848 | for arg in tcx.type_of(field.did).walk() { | |
849 | if let Some(i) = maybe_unsizing_param_idx(arg) { | |
850 | unsizing_params.remove(i); | |
851 | } | |
852 | } | |
853 | } | |
854 | ||
855 | if unsizing_params.is_empty() { | |
856 | return Err(Unimplemented); | |
857 | } | |
858 | } else { | |
859 | let mut found = false; | |
860 | for arg in tail_field_ty.walk() { | |
f035d41b | 861 | if let Some(i) = maybe_unsizing_param_idx(arg) { |
5869c6ff XL |
862 | unsizing_params.insert(i); |
863 | found = true; | |
864 | } | |
865 | } | |
866 | if !found { | |
867 | return Err(Unimplemented); | |
868 | } | |
869 | ||
870 | // Ensure none of the other fields mention the parameters used | |
871 | // in unsizing. | |
872 | // FIXME(eddyb) cache this (including computing `unsizing_params`) | |
873 | // by putting it in a query; it would only need the `DefId` as it | |
874 | // looks at declared field types, not anything substituted. | |
875 | for field in prefix_fields { | |
876 | for arg in tcx.type_of(field.did).walk() { | |
877 | if let Some(i) = maybe_unsizing_param_idx(arg) { | |
878 | if unsizing_params.contains(i) { | |
879 | return Err(Unimplemented); | |
880 | } | |
f035d41b XL |
881 | } |
882 | } | |
883 | } | |
884 | } | |
885 | ||
886 | // Extract `TailField<T>` and `TailField<U>` from `Struct<T>` and `Struct<U>`. | |
887 | let source_tail = tail_field_ty.subst(tcx, substs_a); | |
888 | let target_tail = tail_field_ty.subst(tcx, substs_b); | |
889 | ||
890 | // Check that the source struct with the target's | |
891 | // unsizing parameters is equal to the target. | |
892 | let substs = tcx.mk_substs(substs_a.iter().enumerate().map(|(i, k)| { | |
893 | if unsizing_params.contains(i as u32) { substs_b[i] } else { k } | |
894 | })); | |
895 | let new_struct = tcx.mk_adt(def, substs); | |
896 | let InferOk { obligations, .. } = self | |
897 | .infcx | |
898 | .at(&obligation.cause, obligation.param_env) | |
899 | .eq(target, new_struct) | |
900 | .map_err(|_| Unimplemented)?; | |
901 | nested.extend(obligations); | |
902 | ||
903 | // Construct the nested `TailField<T>: Unsize<TailField<U>>` predicate. | |
904 | nested.push(predicate_for_trait_def( | |
905 | tcx, | |
906 | obligation.param_env, | |
907 | obligation.cause.clone(), | |
908 | obligation.predicate.def_id(), | |
909 | obligation.recursion_depth + 1, | |
910 | source_tail, | |
911 | &[target_tail.into()], | |
912 | )); | |
913 | } | |
914 | ||
915 | // `(.., T)` -> `(.., U)` | |
916 | (&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => { | |
917 | assert_eq!(tys_a.len(), tys_b.len()); | |
918 | ||
919 | // The last field of the tuple has to exist. | |
920 | let (&a_last, a_mid) = tys_a.split_last().ok_or(Unimplemented)?; | |
921 | let &b_last = tys_b.last().unwrap(); | |
922 | ||
923 | // Check that the source tuple with the target's | |
924 | // last element is equal to the target. | |
925 | let new_tuple = tcx.mk_tup( | |
926 | a_mid.iter().map(|k| k.expect_ty()).chain(iter::once(b_last.expect_ty())), | |
927 | ); | |
928 | let InferOk { obligations, .. } = self | |
929 | .infcx | |
930 | .at(&obligation.cause, obligation.param_env) | |
931 | .eq(target, new_tuple) | |
932 | .map_err(|_| Unimplemented)?; | |
933 | nested.extend(obligations); | |
934 | ||
935 | // Construct the nested `T: Unsize<U>` predicate. | |
936 | nested.push(ensure_sufficient_stack(|| { | |
937 | predicate_for_trait_def( | |
938 | tcx, | |
939 | obligation.param_env, | |
940 | obligation.cause.clone(), | |
941 | obligation.predicate.def_id(), | |
942 | obligation.recursion_depth + 1, | |
943 | a_last.expect_ty(), | |
944 | &[b_last], | |
945 | ) | |
946 | })); | |
947 | } | |
948 | ||
949 | _ => bug!(), | |
950 | }; | |
951 | ||
952 | Ok(ImplSourceBuiltinData { nested }) | |
953 | } | |
954 | } |