1 //! Code for projecting associated types out of trait references.
3 use super::specialization_graph;
4 use super::translate_substs;
6 use super::MismatchedProjectionTypes;
8 use super::ObligationCause;
9 use super::PredicateObligation;
11 use super::SelectionContext;
12 use super::SelectionError;
14 ImplSourceClosureData, ImplSourceDiscriminantKindData, ImplSourceFnPointerData,
15 ImplSourceGeneratorData, ImplSourcePointeeData, ImplSourceUserDefinedData,
17 use super::{Normalized, NormalizedTy, ProjectionCacheEntry, ProjectionCacheKey};
19 use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
20 use crate::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
21 use crate::traits::error_reporting::InferCtxtExt as _;
22 use rustc_data_structures::sso::SsoHashSet;
23 use rustc_data_structures::stack::ensure_sufficient_stack;
24 use rustc_errors::ErrorReported;
25 use rustc_hir::def_id::DefId;
26 use rustc_hir::lang_items::LangItem;
27 use rustc_infer::infer::resolve::OpportunisticRegionResolver;
28 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
29 use rustc_middle::ty::subst::Subst;
30 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
31 use rustc_span::symbol::sym;
33 use std::collections::BTreeMap;
35 pub use rustc_middle::traits::Reveal;
37 pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>;
39 pub type ProjectionObligation<'tcx> = Obligation<'tcx, ty::ProjectionPredicate<'tcx>>;
41 pub type ProjectionTyObligation<'tcx> = Obligation<'tcx, ty::ProjectionTy<'tcx>>;
43 pub(super) struct InProgress;
45 /// When attempting to resolve `<T as TraitRef>::Name` ...
47 pub enum ProjectionTyError<'tcx> {
48 /// ...we found multiple sources of information and couldn't resolve the ambiguity.
51 /// ...an error occurred matching `T : TraitRef`
52 TraitSelectionError(SelectionError<'tcx>),
55 #[derive(PartialEq, Eq, Debug)]
56 enum ProjectionTyCandidate<'tcx> {
57 /// From a where-clause in the env or object type
58 ParamEnv(ty::PolyProjectionPredicate<'tcx>),
60 /// From the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
61 TraitDef(ty::PolyProjectionPredicate<'tcx>),
63 /// Bounds specified on an object type
64 Object(ty::PolyProjectionPredicate<'tcx>),
66 /// From an "impl" (or a "pseudo-impl" returned by select)
67 Select(Selection<'tcx>),
70 enum ProjectionTyCandidateSet<'tcx> {
72 Single(ProjectionTyCandidate<'tcx>),
74 Error(SelectionError<'tcx>),
77 impl<'tcx> ProjectionTyCandidateSet<'tcx> {
78 fn mark_ambiguous(&mut self) {
79 *self = ProjectionTyCandidateSet::Ambiguous;
82 fn mark_error(&mut self, err: SelectionError<'tcx>) {
83 *self = ProjectionTyCandidateSet::Error(err);
86 // Returns true if the push was successful, or false if the candidate
87 // was discarded -- this could be because of ambiguity, or because
88 // a higher-priority candidate is already there.
89 fn push_candidate(&mut self, candidate: ProjectionTyCandidate<'tcx>) -> bool {
90 use self::ProjectionTyCandidate::*;
91 use self::ProjectionTyCandidateSet::*;
93 // This wacky variable is just used to try and
94 // make code readable and avoid confusing paths.
95 // It is assigned a "value" of `()` only on those
96 // paths in which we wish to convert `*self` to
97 // ambiguous (and return false, because the candidate
98 // was not used). On other paths, it is not assigned,
99 // and hence if those paths *could* reach the code that
100 // comes after the match, this fn would not compile.
101 let convert_to_ambiguous;
105 *self = Single(candidate);
110 // Duplicates can happen inside ParamEnv. In the case, we
111 // perform a lazy deduplication.
112 if current == &candidate {
116 // Prefer where-clauses. As in select, if there are multiple
117 // candidates, we prefer where-clause candidates over impls. This
118 // may seem a bit surprising, since impls are the source of
119 // "truth" in some sense, but in fact some of the impls that SEEM
120 // applicable are not, because of nested obligations. Where
121 // clauses are the safer choice. See the comment on
122 // `select::SelectionCandidate` and #21974 for more details.
123 match (current, candidate) {
124 (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous = (),
125 (ParamEnv(..), _) => return false,
126 (_, ParamEnv(..)) => unreachable!(),
127 (_, _) => convert_to_ambiguous = (),
131 Ambiguous | Error(..) => {
136 // We only ever get here when we moved from a single candidate
138 let () = convert_to_ambiguous;
144 /// Evaluates constraints of the form:
146 /// for<...> <T as Trait>::U == V
148 /// If successful, this may result in additional obligations. Also returns
149 /// the projection cache key used to track these additional obligations.
153 /// - `Err(_)`: the projection can be normalized, but is not equal to the
155 /// - `Ok(Err(InProgress))`: this is called recursively while normalizing
156 /// the same projection.
157 /// - `Ok(Ok(None))`: The projection cannot be normalized due to ambiguity
158 /// (resolving some inference variables in the projection may fix this).
159 /// - `Ok(Ok(Some(obligations)))`: The projection bound holds subject to
160 /// the given obligations. If the projection cannot be normalized because
161 /// the required trait bound doesn't hold this returned with `obligations`
162 /// being a predicate that cannot be proven.
163 #[instrument(level = "debug", skip(selcx))]
164 pub(super) fn poly_project_and_unify_type<'cx, 'tcx>(
165 selcx: &mut SelectionContext<'cx, 'tcx>,
166 obligation: &PolyProjectionObligation<'tcx>,
168 Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
169 MismatchedProjectionTypes<'tcx>,
171 let infcx = selcx.infcx();
172 infcx.commit_if_ok(|_snapshot| {
173 let placeholder_predicate =
174 infcx.replace_bound_vars_with_placeholders(obligation.predicate);
176 let placeholder_obligation = obligation.with(placeholder_predicate);
177 let result = project_and_unify_type(selcx, &placeholder_obligation)?;
182 /// Evaluates constraints of the form:
184 /// <T as Trait>::U == V
186 /// If successful, this may result in additional obligations.
188 /// See [poly_project_and_unify_type] for an explanation of the return value.
189 fn project_and_unify_type<'cx, 'tcx>(
190 selcx: &mut SelectionContext<'cx, 'tcx>,
191 obligation: &ProjectionObligation<'tcx>,
193 Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
194 MismatchedProjectionTypes<'tcx>,
196 debug!(?obligation, "project_and_unify_type");
198 let mut obligations = vec![];
199 let normalized_ty = match opt_normalize_projection_type(
201 obligation.param_env,
202 obligation.predicate.projection_ty,
203 obligation.cause.clone(),
204 obligation.recursion_depth,
208 Ok(None) => return Ok(Ok(None)),
209 Err(InProgress) => return Ok(Err(InProgress)),
212 debug!(?normalized_ty, ?obligations, "project_and_unify_type result");
214 let infcx = selcx.infcx();
215 // FIXME(associated_const_equality): Handle consts here as well as types.
216 let obligation_pred_ty = obligation.predicate.term.ty().unwrap();
217 match infcx.at(&obligation.cause, obligation.param_env).eq(normalized_ty, obligation_pred_ty) {
218 Ok(InferOk { obligations: inferred_obligations, value: () }) => {
219 obligations.extend(inferred_obligations);
220 Ok(Ok(Some(obligations)))
223 debug!("project_and_unify_type: equating types encountered error {:?}", err);
224 Err(MismatchedProjectionTypes { err })
229 /// Normalizes any associated type projections in `value`, replacing
230 /// them with a fully resolved type where possible. The return value
231 /// combines the normalized result and any additional obligations that
232 /// were incurred as result.
233 pub fn normalize<'a, 'b, 'tcx, T>(
234 selcx: &'a mut SelectionContext<'b, 'tcx>,
235 param_env: ty::ParamEnv<'tcx>,
236 cause: ObligationCause<'tcx>,
238 ) -> Normalized<'tcx, T>
240 T: TypeFoldable<'tcx>,
242 let mut obligations = Vec::new();
243 let value = normalize_to(selcx, param_env, cause, value, &mut obligations);
244 Normalized { value, obligations }
247 pub fn normalize_to<'a, 'b, 'tcx, T>(
248 selcx: &'a mut SelectionContext<'b, 'tcx>,
249 param_env: ty::ParamEnv<'tcx>,
250 cause: ObligationCause<'tcx>,
252 obligations: &mut Vec<PredicateObligation<'tcx>>,
255 T: TypeFoldable<'tcx>,
257 normalize_with_depth_to(selcx, param_env, cause, 0, value, obligations)
260 /// As `normalize`, but with a custom depth.
261 pub fn normalize_with_depth<'a, 'b, 'tcx, T>(
262 selcx: &'a mut SelectionContext<'b, 'tcx>,
263 param_env: ty::ParamEnv<'tcx>,
264 cause: ObligationCause<'tcx>,
267 ) -> Normalized<'tcx, T>
269 T: TypeFoldable<'tcx>,
271 let mut obligations = Vec::new();
272 let value = normalize_with_depth_to(selcx, param_env, cause, depth, value, &mut obligations);
273 Normalized { value, obligations }
276 #[instrument(level = "info", skip(selcx, param_env, cause, obligations))]
277 pub fn normalize_with_depth_to<'a, 'b, 'tcx, T>(
278 selcx: &'a mut SelectionContext<'b, 'tcx>,
279 param_env: ty::ParamEnv<'tcx>,
280 cause: ObligationCause<'tcx>,
283 obligations: &mut Vec<PredicateObligation<'tcx>>,
286 T: TypeFoldable<'tcx>,
288 debug!(obligations.len = obligations.len());
289 let mut normalizer = AssocTypeNormalizer::new(selcx, param_env, cause, depth, obligations);
290 let result = ensure_sufficient_stack(|| normalizer.fold(value));
291 debug!(?result, obligations.len = normalizer.obligations.len());
292 debug!(?normalizer.obligations,);
296 pub(crate) fn needs_normalization<'tcx, T: TypeFoldable<'tcx>>(value: &T, reveal: Reveal) -> bool {
298 Reveal::UserFacing => value
299 .has_type_flags(ty::TypeFlags::HAS_TY_PROJECTION | ty::TypeFlags::HAS_CT_PROJECTION),
300 Reveal::All => value.has_type_flags(
301 ty::TypeFlags::HAS_TY_PROJECTION
302 | ty::TypeFlags::HAS_TY_OPAQUE
303 | ty::TypeFlags::HAS_CT_PROJECTION,
308 struct AssocTypeNormalizer<'a, 'b, 'tcx> {
309 selcx: &'a mut SelectionContext<'b, 'tcx>,
310 param_env: ty::ParamEnv<'tcx>,
311 cause: ObligationCause<'tcx>,
312 obligations: &'a mut Vec<PredicateObligation<'tcx>>,
314 universes: Vec<Option<ty::UniverseIndex>>,
317 impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> {
319 selcx: &'a mut SelectionContext<'b, 'tcx>,
320 param_env: ty::ParamEnv<'tcx>,
321 cause: ObligationCause<'tcx>,
323 obligations: &'a mut Vec<PredicateObligation<'tcx>>,
324 ) -> AssocTypeNormalizer<'a, 'b, 'tcx> {
325 AssocTypeNormalizer { selcx, param_env, cause, obligations, depth, universes: vec![] }
328 fn fold<T: TypeFoldable<'tcx>>(&mut self, value: T) -> T {
329 let value = self.selcx.infcx().resolve_vars_if_possible(value);
333 !value.has_escaping_bound_vars(),
334 "Normalizing {:?} without wrapping in a `Binder`",
338 if !needs_normalization(&value, self.param_env.reveal()) {
341 value.fold_with(self)
346 impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> {
347 fn tcx<'c>(&'c self) -> TyCtxt<'tcx> {
351 fn fold_binder<T: TypeFoldable<'tcx>>(
353 t: ty::Binder<'tcx, T>,
354 ) -> ty::Binder<'tcx, T> {
355 self.universes.push(None);
356 let t = t.super_fold_with(self);
357 self.universes.pop();
361 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
362 if !needs_normalization(&ty, self.param_env.reveal()) {
366 // We try to be a little clever here as a performance optimization in
367 // cases where there are nested projections under binders.
370 // for<'a> fn(<T as Foo>::One<'a, Box<dyn Bar<'a, Item=<T as Foo>::Two<'a>>>>)
372 // We normalize the substs on the projection before the projecting, but
373 // if we're naive, we'll
374 // replace bound vars on inner, project inner, replace placeholders on inner,
375 // replace bound vars on outer, project outer, replace placeholders on outer
377 // However, if we're a bit more clever, we can replace the bound vars
378 // on the entire type before normalizing nested projections, meaning we
379 // replace bound vars on outer, project inner,
380 // project outer, replace placeholders on outer
382 // This is possible because the inner `'a` will already be a placeholder
383 // when we need to normalize the inner projection
385 // On the other hand, this does add a bit of complexity, since we only
386 // replace bound vars if the current type is a `Projection` and we need
387 // to make sure we don't forget to fold the substs regardless.
390 // This is really important. While we *can* handle this, this has
391 // severe performance implications for large opaque types with
392 // late-bound regions. See `issue-88862` benchmark.
393 ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => {
394 // Only normalize `impl Trait` after type-checking, usually in codegen.
395 match self.param_env.reveal() {
396 Reveal::UserFacing => ty.super_fold_with(self),
399 let recursion_limit = self.tcx().recursion_limit();
400 if !recursion_limit.value_within_limit(self.depth) {
401 let obligation = Obligation::with_depth(
407 self.selcx.infcx().report_overflow_error(&obligation, true);
410 let substs = substs.super_fold_with(self);
411 let generic_ty = self.tcx().type_of(def_id);
412 let concrete_ty = generic_ty.subst(self.tcx(), substs);
414 let folded_ty = self.fold_ty(concrete_ty);
421 ty::Projection(data) if !data.has_escaping_bound_vars() => {
422 // This branch is *mostly* just an optimization: when we don't
423 // have escaping bound vars, we don't need to replace them with
424 // placeholders (see branch below). *Also*, we know that we can
425 // register an obligation to *later* project, since we know
426 // there won't be bound vars there.
428 let data = data.super_fold_with(self);
429 let normalized_ty = normalize_projection_type(
435 &mut self.obligations,
441 obligations.len = ?self.obligations.len(),
442 "AssocTypeNormalizer: normalized type"
447 ty::Projection(data) => {
448 // If there are escaping bound vars, we temporarily replace the
449 // bound vars with placeholders. Note though, that in the case
450 // that we still can't project for whatever reason (e.g. self
451 // type isn't known enough), we *can't* register an obligation
452 // and return an inference variable (since then that obligation
453 // would have bound vars and that's a can of worms). Instead,
454 // we just give up and fall back to pretending like we never tried!
456 // Note: this isn't necessarily the final approach here; we may
457 // want to figure out how to register obligations with escaping vars
458 // or handle this some other way.
460 let infcx = self.selcx.infcx();
461 let (data, mapped_regions, mapped_types, mapped_consts) =
462 BoundVarReplacer::replace_bound_vars(infcx, &mut self.universes, data);
463 let data = data.super_fold_with(self);
464 let normalized_ty = opt_normalize_projection_type(
470 &mut self.obligations,
474 .map(|normalized_ty| {
475 PlaceholderReplacer::replace_placeholders(
484 .unwrap_or_else(|| ty.super_fold_with(self));
490 obligations.len = ?self.obligations.len(),
491 "AssocTypeNormalizer: normalized type"
496 _ => ty.super_fold_with(self),
500 fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
501 if self.selcx.tcx().lazy_normalization() {
504 let constant = constant.super_fold_with(self);
505 constant.eval(self.selcx.tcx(), self.param_env)
510 pub struct BoundVarReplacer<'me, 'tcx> {
511 infcx: &'me InferCtxt<'me, 'tcx>,
512 // These three maps track the bound variable that were replaced by placeholders. It might be
513 // nice to remove these since we already have the `kind` in the placeholder; we really just need
514 // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
515 mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
516 mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>,
517 mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
518 // The current depth relative to *this* folding, *not* the entire normalization. In other words,
519 // the depth of binders we've passed here.
520 current_index: ty::DebruijnIndex,
521 // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
522 // we don't actually create a universe until we see a bound var we have to replace.
523 universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>,
526 impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> {
527 /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
528 /// use a binding level above `universe_indices.len()`, we fail.
529 pub fn replace_bound_vars<T: TypeFoldable<'tcx>>(
530 infcx: &'me InferCtxt<'me, 'tcx>,
531 universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>,
535 BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
536 BTreeMap<ty::PlaceholderType, ty::BoundTy>,
537 BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
539 let mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion> = BTreeMap::new();
540 let mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy> = BTreeMap::new();
541 let mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar> = BTreeMap::new();
543 let mut replacer = BoundVarReplacer {
548 current_index: ty::INNERMOST,
552 let value = value.super_fold_with(&mut replacer);
554 (value, replacer.mapped_regions, replacer.mapped_types, replacer.mapped_consts)
557 fn universe_for(&mut self, debruijn: ty::DebruijnIndex) -> ty::UniverseIndex {
558 let infcx = self.infcx;
560 self.universe_indices.len() + self.current_index.as_usize() - debruijn.as_usize() - 1;
561 let universe = self.universe_indices[index].unwrap_or_else(|| {
562 for i in self.universe_indices.iter_mut().take(index + 1) {
563 *i = i.or_else(|| Some(infcx.create_next_universe()))
565 self.universe_indices[index].unwrap()
571 impl<'tcx> TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> {
572 fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
576 fn fold_binder<T: TypeFoldable<'tcx>>(
578 t: ty::Binder<'tcx, T>,
579 ) -> ty::Binder<'tcx, T> {
580 self.current_index.shift_in(1);
581 let t = t.super_fold_with(self);
582 self.current_index.shift_out(1);
586 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
588 ty::ReLateBound(debruijn, _)
589 if debruijn.as_usize() + 1
590 > self.current_index.as_usize() + self.universe_indices.len() =>
592 bug!("Bound vars outside of `self.universe_indices`");
594 ty::ReLateBound(debruijn, br) if debruijn >= self.current_index => {
595 let universe = self.universe_for(debruijn);
596 let p = ty::PlaceholderRegion { universe, name: br.kind };
597 self.mapped_regions.insert(p, br);
598 self.infcx.tcx.mk_region(ty::RePlaceholder(p))
604 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
606 ty::Bound(debruijn, _)
607 if debruijn.as_usize() + 1
608 > self.current_index.as_usize() + self.universe_indices.len() =>
610 bug!("Bound vars outside of `self.universe_indices`");
612 ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
613 let universe = self.universe_for(debruijn);
614 let p = ty::PlaceholderType { universe, name: bound_ty.var };
615 self.mapped_types.insert(p, bound_ty);
616 self.infcx.tcx.mk_ty(ty::Placeholder(p))
618 _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self),
623 fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
625 ty::Const { val: ty::ConstKind::Bound(debruijn, _), ty: _ }
626 if debruijn.as_usize() + 1
627 > self.current_index.as_usize() + self.universe_indices.len() =>
629 bug!("Bound vars outside of `self.universe_indices`");
631 ty::Const { val: ty::ConstKind::Bound(debruijn, bound_const), ty }
632 if debruijn >= self.current_index =>
634 let universe = self.universe_for(debruijn);
635 let p = ty::PlaceholderConst {
637 name: ty::BoundConst { var: bound_const, ty },
639 self.mapped_consts.insert(p, bound_const);
640 self.infcx.tcx.mk_const(ty::Const { val: ty::ConstKind::Placeholder(p), ty })
642 _ if ct.has_vars_bound_at_or_above(self.current_index) => ct.super_fold_with(self),
648 // The inverse of `BoundVarReplacer`: replaces placeholders with the bound vars from which they came.
649 pub struct PlaceholderReplacer<'me, 'tcx> {
650 infcx: &'me InferCtxt<'me, 'tcx>,
651 mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
652 mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>,
653 mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
654 universe_indices: &'me Vec<Option<ty::UniverseIndex>>,
655 current_index: ty::DebruijnIndex,
658 impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> {
659 pub fn replace_placeholders<T: TypeFoldable<'tcx>>(
660 infcx: &'me InferCtxt<'me, 'tcx>,
661 mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>,
662 mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>,
663 mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>,
664 universe_indices: &'me Vec<Option<ty::UniverseIndex>>,
667 let mut replacer = PlaceholderReplacer {
673 current_index: ty::INNERMOST,
675 value.super_fold_with(&mut replacer)
679 impl<'tcx> TypeFolder<'tcx> for PlaceholderReplacer<'_, 'tcx> {
680 fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
684 fn fold_binder<T: TypeFoldable<'tcx>>(
686 t: ty::Binder<'tcx, T>,
687 ) -> ty::Binder<'tcx, T> {
688 if !t.has_placeholders() && !t.has_infer_regions() {
691 self.current_index.shift_in(1);
692 let t = t.super_fold_with(self);
693 self.current_index.shift_out(1);
697 fn fold_region(&mut self, r0: ty::Region<'tcx>) -> ty::Region<'tcx> {
703 .unwrap_region_constraints()
704 .opportunistic_resolve_region(self.infcx.tcx, r0),
709 ty::RePlaceholder(p) => {
710 let replace_var = self.mapped_regions.get(&p);
712 Some(replace_var) => {
716 .position(|u| matches!(u, Some(pu) if *pu == p.universe))
717 .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
718 let db = ty::DebruijnIndex::from_usize(
719 self.universe_indices.len() - index + self.current_index.as_usize() - 1,
721 self.tcx().mk_region(ty::ReLateBound(db, *replace_var))
729 debug!(?r0, ?r1, ?r2, "fold_region");
734 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
736 ty::Placeholder(p) => {
737 let replace_var = self.mapped_types.get(&p);
739 Some(replace_var) => {
743 .position(|u| matches!(u, Some(pu) if *pu == p.universe))
744 .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
745 let db = ty::DebruijnIndex::from_usize(
746 self.universe_indices.len() - index + self.current_index.as_usize() - 1,
748 self.tcx().mk_ty(ty::Bound(db, *replace_var))
754 _ if ty.has_placeholders() || ty.has_infer_regions() => ty.super_fold_with(self),
759 fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
760 if let ty::Const { val: ty::ConstKind::Placeholder(p), ty } = *ct {
761 let replace_var = self.mapped_consts.get(&p);
763 Some(replace_var) => {
767 .position(|u| matches!(u, Some(pu) if *pu == p.universe))
768 .unwrap_or_else(|| bug!("Unexpected placeholder universe."));
769 let db = ty::DebruijnIndex::from_usize(
770 self.universe_indices.len() - index + self.current_index.as_usize() - 1,
773 .mk_const(ty::Const { val: ty::ConstKind::Bound(db, *replace_var), ty })
778 ct.super_fold_with(self)
783 /// The guts of `normalize`: normalize a specific projection like `<T
784 /// as Trait>::Item`. The result is always a type (and possibly
785 /// additional obligations). If ambiguity arises, which implies that
786 /// there are unresolved type variables in the projection, we will
787 /// substitute a fresh type variable `$X` and generate a new
788 /// obligation `<T as Trait>::Item == $X` for later.
789 pub fn normalize_projection_type<'a, 'b, 'tcx>(
790 selcx: &'a mut SelectionContext<'b, 'tcx>,
791 param_env: ty::ParamEnv<'tcx>,
792 projection_ty: ty::ProjectionTy<'tcx>,
793 cause: ObligationCause<'tcx>,
795 obligations: &mut Vec<PredicateObligation<'tcx>>,
797 opt_normalize_projection_type(
807 .unwrap_or_else(move || {
808 // if we bottom out in ambiguity, create a type variable
809 // and a deferred predicate to resolve this when more type
810 // information is available.
812 selcx.infcx().infer_projection(param_env, projection_ty, cause, depth + 1, obligations)
816 /// The guts of `normalize`: normalize a specific projection like `<T
817 /// as Trait>::Item`. The result is always a type (and possibly
818 /// additional obligations). Returns `None` in the case of ambiguity,
819 /// which indicates that there are unbound type variables.
821 /// This function used to return `Option<NormalizedTy<'tcx>>`, which contains a
822 /// `Ty<'tcx>` and an obligations vector. But that obligation vector was very
823 /// often immediately appended to another obligations vector. So now this
824 /// function takes an obligations vector and appends to it directly, which is
825 /// slightly uglier but avoids the need for an extra short-lived allocation.
826 #[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
827 fn opt_normalize_projection_type<'a, 'b, 'tcx>(
828 selcx: &'a mut SelectionContext<'b, 'tcx>,
829 param_env: ty::ParamEnv<'tcx>,
830 projection_ty: ty::ProjectionTy<'tcx>,
831 cause: ObligationCause<'tcx>,
833 obligations: &mut Vec<PredicateObligation<'tcx>>,
834 ) -> Result<Option<Ty<'tcx>>, InProgress> {
835 let infcx = selcx.infcx();
836 // Don't use the projection cache in intercrate mode -
837 // the `infcx` may be re-used between intercrate in non-intercrate
838 // mode, which could lead to using incorrect cache results.
839 let use_cache = !selcx.is_intercrate();
841 let projection_ty = infcx.resolve_vars_if_possible(projection_ty);
842 let cache_key = ProjectionCacheKey::new(projection_ty);
844 // FIXME(#20304) For now, I am caching here, which is good, but it
845 // means we don't capture the type variables that are created in
846 // the case of ambiguity. Which means we may create a large stream
847 // of such variables. OTOH, if we move the caching up a level, we
848 // would not benefit from caching when proving `T: Trait<U=Foo>`
849 // bounds. It might be the case that we want two distinct caches,
850 // or else another kind of cache entry.
852 let cache_result = if use_cache {
853 infcx.inner.borrow_mut().projection_cache().try_start(cache_key)
858 Ok(()) => debug!("no cache"),
859 Err(ProjectionCacheEntry::Ambiguous) => {
860 // If we found ambiguity the last time, that means we will continue
861 // to do so until some type in the key changes (and we know it
862 // hasn't, because we just fully resolved it).
863 debug!("found cache entry: ambiguous");
866 Err(ProjectionCacheEntry::InProgress) => {
867 // Under lazy normalization, this can arise when
868 // bootstrapping. That is, imagine an environment with a
869 // where-clause like `A::B == u32`. Now, if we are asked
870 // to normalize `A::B`, we will want to check the
871 // where-clauses in scope. So we will try to unify `A::B`
872 // with `A::B`, which can trigger a recursive
875 debug!("found cache entry: in-progress");
877 // Cache that normalizing this projection resulted in a cycle. This
878 // should ensure that, unless this happens within a snapshot that's
879 // rolled back, fulfillment or evaluation will notice the cycle.
882 infcx.inner.borrow_mut().projection_cache().recur(cache_key);
884 return Err(InProgress);
886 Err(ProjectionCacheEntry::Recur) => {
887 debug!("recur cache");
888 return Err(InProgress);
890 Err(ProjectionCacheEntry::NormalizedTy { ty, complete: _ }) => {
891 // This is the hottest path in this function.
893 // If we find the value in the cache, then return it along
894 // with the obligations that went along with it. Note
895 // that, when using a fulfillment context, these
896 // obligations could in principle be ignored: they have
897 // already been registered when the cache entry was
898 // created (and hence the new ones will quickly be
899 // discarded as duplicated). But when doing trait
900 // evaluation this is not the case, and dropping the trait
901 // evaluations can causes ICEs (e.g., #43132).
902 debug!(?ty, "found normalized ty");
903 obligations.extend(ty.obligations);
904 return Ok(Some(ty.value));
906 Err(ProjectionCacheEntry::Error) => {
907 debug!("opt_normalize_projection_type: found error");
908 let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth);
909 obligations.extend(result.obligations);
910 return Ok(Some(result.value));
914 let obligation = Obligation::with_depth(cause.clone(), depth, param_env, projection_ty);
916 match project_type(selcx, &obligation) {
917 Ok(ProjectedTy::Progress(Progress {
919 obligations: mut projected_obligations,
921 // if projection succeeded, then what we get out of this
922 // is also non-normalized (consider: it was derived from
923 // an impl, where-clause etc) and hence we must
926 let projected_ty = selcx.infcx().resolve_vars_if_possible(projected_ty);
927 debug!(?projected_ty, ?depth, ?projected_obligations);
929 let mut result = if projected_ty.has_projections() {
930 let mut normalizer = AssocTypeNormalizer::new(
935 &mut projected_obligations,
937 let normalized_ty = normalizer.fold(projected_ty);
939 debug!(?normalized_ty, ?depth);
941 Normalized { value: normalized_ty, obligations: projected_obligations }
943 Normalized { value: projected_ty, obligations: projected_obligations }
946 let mut deduped: SsoHashSet<_> = Default::default();
947 result.obligations.drain_filter(|projected_obligation| {
948 if !deduped.insert(projected_obligation.clone()) {
955 infcx.inner.borrow_mut().projection_cache().insert_ty(cache_key, result.clone());
957 obligations.extend(result.obligations);
958 Ok(Some(result.value))
960 Ok(ProjectedTy::NoProgress(projected_ty)) => {
961 debug!(?projected_ty, "opt_normalize_projection_type: no progress");
962 let result = Normalized { value: projected_ty, obligations: vec![] };
964 infcx.inner.borrow_mut().projection_cache().insert_ty(cache_key, result.clone());
966 // No need to extend `obligations`.
967 Ok(Some(result.value))
969 Err(ProjectionTyError::TooManyCandidates) => {
970 debug!("opt_normalize_projection_type: too many candidates");
972 infcx.inner.borrow_mut().projection_cache().ambiguous(cache_key);
976 Err(ProjectionTyError::TraitSelectionError(_)) => {
977 debug!("opt_normalize_projection_type: ERROR");
978 // if we got an error processing the `T as Trait` part,
979 // just return `ty::err` but add the obligation `T :
980 // Trait`, which when processed will cause the error to be
984 infcx.inner.borrow_mut().projection_cache().error(cache_key);
986 let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth);
987 obligations.extend(result.obligations);
988 Ok(Some(result.value))
993 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
994 /// hold. In various error cases, we cannot generate a valid
995 /// normalized projection. Therefore, we create an inference variable
996 /// return an associated obligation that, when fulfilled, will lead to
999 /// Note that we used to return `Error` here, but that was quite
1000 /// dubious -- the premise was that an error would *eventually* be
1001 /// reported, when the obligation was processed. But in general once
1002 /// you see an `Error` you are supposed to be able to assume that an
1003 /// error *has been* reported, so that you can take whatever heuristic
1004 /// paths you want to take. To make things worse, it was possible for
1005 /// cycles to arise, where you basically had a setup like `<MyType<$0>
1006 /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
1007 /// Trait>::Foo> to `[type error]` would lead to an obligation of
1008 /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report
1009 /// an error for this obligation, but we legitimately should not,
1010 /// because it contains `[type error]`. Yuck! (See issue #29857 for
1011 /// one case where this arose.)
1012 fn normalize_to_error<'a, 'tcx>(
1013 selcx: &mut SelectionContext<'a, 'tcx>,
1014 param_env: ty::ParamEnv<'tcx>,
1015 projection_ty: ty::ProjectionTy<'tcx>,
1016 cause: ObligationCause<'tcx>,
1018 ) -> NormalizedTy<'tcx> {
1019 let trait_ref = ty::Binder::dummy(projection_ty.trait_ref(selcx.tcx()));
1020 let trait_obligation = Obligation {
1022 recursion_depth: depth,
1024 predicate: trait_ref.without_const().to_predicate(selcx.tcx()),
1026 let tcx = selcx.infcx().tcx;
1027 let def_id = projection_ty.item_def_id;
1028 let new_value = selcx.infcx().next_ty_var(TypeVariableOrigin {
1029 kind: TypeVariableOriginKind::NormalizeProjectionType,
1030 span: tcx.def_span(def_id),
1032 Normalized { value: new_value, obligations: vec![trait_obligation] }
1035 enum ProjectedTy<'tcx> {
1036 Progress(Progress<'tcx>),
1037 NoProgress(Ty<'tcx>),
1040 struct Progress<'tcx> {
1042 obligations: Vec<PredicateObligation<'tcx>>,
1045 impl<'tcx> Progress<'tcx> {
1046 fn error(tcx: TyCtxt<'tcx>) -> Self {
1047 Progress { ty: tcx.ty_error(), obligations: vec![] }
1050 fn with_addl_obligations(mut self, mut obligations: Vec<PredicateObligation<'tcx>>) -> Self {
1052 self.obligations.len = ?self.obligations.len(),
1053 obligations.len = obligations.len(),
1054 "with_addl_obligations"
1057 debug!(?self.obligations, ?obligations, "with_addl_obligations");
1059 self.obligations.append(&mut obligations);
1064 /// Computes the result of a projection type (if we can).
1067 /// - `obligation` must be fully normalized
1068 #[tracing::instrument(level = "info", skip(selcx))]
1069 fn project_type<'cx, 'tcx>(
1070 selcx: &mut SelectionContext<'cx, 'tcx>,
1071 obligation: &ProjectionTyObligation<'tcx>,
1072 ) -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>> {
1073 if !selcx.tcx().recursion_limit().value_within_limit(obligation.recursion_depth) {
1074 debug!("project: overflow!");
1075 // This should really be an immediate error, but some existing code
1076 // relies on being able to recover from this.
1077 return Err(ProjectionTyError::TraitSelectionError(SelectionError::Overflow));
1080 if obligation.predicate.references_error() {
1081 return Ok(ProjectedTy::Progress(Progress::error(selcx.tcx())));
1084 let mut candidates = ProjectionTyCandidateSet::None;
1086 // Make sure that the following procedures are kept in order. ParamEnv
1087 // needs to be first because it has highest priority, and Select checks
1088 // the return value of push_candidate which assumes it's ran at last.
1089 assemble_candidates_from_param_env(selcx, obligation, &mut candidates);
1091 assemble_candidates_from_trait_def(selcx, obligation, &mut candidates);
1093 assemble_candidates_from_object_ty(selcx, obligation, &mut candidates);
1095 if let ProjectionTyCandidateSet::Single(ProjectionTyCandidate::Object(_)) = candidates {
1096 // Avoid normalization cycle from selection (see
1097 // `assemble_candidates_from_object_ty`).
1098 // FIXME(lazy_normalization): Lazy normalization should save us from
1099 // having to special case this.
1101 assemble_candidates_from_impls(selcx, obligation, &mut candidates);
1105 ProjectionTyCandidateSet::Single(candidate) => {
1106 Ok(ProjectedTy::Progress(confirm_candidate(selcx, obligation, candidate)))
1108 ProjectionTyCandidateSet::None => Ok(ProjectedTy::NoProgress(
1111 .mk_projection(obligation.predicate.item_def_id, obligation.predicate.substs),
1113 // Error occurred while trying to processing impls.
1114 ProjectionTyCandidateSet::Error(e) => Err(ProjectionTyError::TraitSelectionError(e)),
1115 // Inherent ambiguity that prevents us from even enumerating the
1117 ProjectionTyCandidateSet::Ambiguous => Err(ProjectionTyError::TooManyCandidates),
1121 /// The first thing we have to do is scan through the parameter
1122 /// environment to see whether there are any projection predicates
1123 /// there that can answer this question.
1124 fn assemble_candidates_from_param_env<'cx, 'tcx>(
1125 selcx: &mut SelectionContext<'cx, 'tcx>,
1126 obligation: &ProjectionTyObligation<'tcx>,
1127 candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
1129 debug!("assemble_candidates_from_param_env(..)");
1130 assemble_candidates_from_predicates(
1134 ProjectionTyCandidate::ParamEnv,
1135 obligation.param_env.caller_bounds().iter(),
1140 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
1141 /// that the definition of `Foo` has some clues:
1145 /// type FooT : Bar<BarT=i32>
1149 /// Here, for example, we could conclude that the result is `i32`.
1150 fn assemble_candidates_from_trait_def<'cx, 'tcx>(
1151 selcx: &mut SelectionContext<'cx, 'tcx>,
1152 obligation: &ProjectionTyObligation<'tcx>,
1153 candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
1155 debug!("assemble_candidates_from_trait_def(..)");
1157 let tcx = selcx.tcx();
1158 // Check whether the self-type is itself a projection.
1159 // If so, extract what we know from the trait and try to come up with a good answer.
1160 let bounds = match *obligation.predicate.self_ty().kind() {
1161 ty::Projection(ref data) => tcx.item_bounds(data.item_def_id).subst(tcx, data.substs),
1162 ty::Opaque(def_id, substs) => tcx.item_bounds(def_id).subst(tcx, substs),
1163 ty::Infer(ty::TyVar(_)) => {
1164 // If the self-type is an inference variable, then it MAY wind up
1165 // being a projected type, so induce an ambiguity.
1166 candidate_set.mark_ambiguous();
1172 assemble_candidates_from_predicates(
1176 ProjectionTyCandidate::TraitDef,
1182 /// In the case of a trait object like
1183 /// `<dyn Iterator<Item = ()> as Iterator>::Item` we can use the existential
1184 /// predicate in the trait object.
1186 /// We don't go through the select candidate for these bounds to avoid cycles:
1187 /// In the above case, `dyn Iterator<Item = ()>: Iterator` would create a
1188 /// nested obligation of `<dyn Iterator<Item = ()> as Iterator>::Item: Sized`,
1189 /// this then has to be normalized without having to prove
1190 /// `dyn Iterator<Item = ()>: Iterator` again.
1191 fn assemble_candidates_from_object_ty<'cx, 'tcx>(
1192 selcx: &mut SelectionContext<'cx, 'tcx>,
1193 obligation: &ProjectionTyObligation<'tcx>,
1194 candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
1196 debug!("assemble_candidates_from_object_ty(..)");
1198 let tcx = selcx.tcx();
1200 let self_ty = obligation.predicate.self_ty();
1201 let object_ty = selcx.infcx().shallow_resolve(self_ty);
1202 let data = match object_ty.kind() {
1203 ty::Dynamic(data, ..) => data,
1204 ty::Infer(ty::TyVar(_)) => {
1205 // If the self-type is an inference variable, then it MAY wind up
1206 // being an object type, so induce an ambiguity.
1207 candidate_set.mark_ambiguous();
1212 let env_predicates = data
1213 .projection_bounds()
1214 .filter(|bound| bound.item_def_id() == obligation.predicate.item_def_id)
1215 .map(|p| p.with_self_ty(tcx, object_ty).to_predicate(tcx));
1217 assemble_candidates_from_predicates(
1221 ProjectionTyCandidate::Object,
1227 #[tracing::instrument(
1229 skip(selcx, candidate_set, ctor, env_predicates, potentially_unnormalized_candidates)
1231 fn assemble_candidates_from_predicates<'cx, 'tcx>(
1232 selcx: &mut SelectionContext<'cx, 'tcx>,
1233 obligation: &ProjectionTyObligation<'tcx>,
1234 candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
1235 ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>,
1236 env_predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
1237 potentially_unnormalized_candidates: bool,
1239 let infcx = selcx.infcx();
1240 for predicate in env_predicates {
1242 let bound_predicate = predicate.kind();
1243 if let ty::PredicateKind::Projection(data) = predicate.kind().skip_binder() {
1244 let data = bound_predicate.rebind(data);
1245 let same_def_id = data.projection_def_id() == obligation.predicate.item_def_id;
1247 let is_match = same_def_id
1248 && infcx.probe(|_| {
1249 selcx.match_projection_projections(
1252 potentially_unnormalized_candidates,
1256 debug!(?data, ?is_match, ?same_def_id);
1259 candidate_set.push_candidate(ctor(data));
1261 if potentially_unnormalized_candidates
1262 && !obligation.predicate.has_infer_types_or_consts()
1264 // HACK: Pick the first trait def candidate for a fully
1265 // inferred predicate. This is to allow duplicates that
1266 // differ only in normalization.
1274 #[tracing::instrument(level = "debug", skip(selcx, obligation, candidate_set))]
1275 fn assemble_candidates_from_impls<'cx, 'tcx>(
1276 selcx: &mut SelectionContext<'cx, 'tcx>,
1277 obligation: &ProjectionTyObligation<'tcx>,
1278 candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
1280 // If we are resolving `<T as TraitRef<...>>::Item == Type`,
1281 // start out by selecting the predicate `T as TraitRef<...>`:
1282 let poly_trait_ref = ty::Binder::dummy(obligation.predicate.trait_ref(selcx.tcx()));
1283 let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate());
1284 let _ = selcx.infcx().commit_if_ok(|_| {
1285 let impl_source = match selcx.select(&trait_obligation) {
1286 Ok(Some(impl_source)) => impl_source,
1288 candidate_set.mark_ambiguous();
1292 debug!(error = ?e, "selection error");
1293 candidate_set.mark_error(e);
1298 let eligible = match &impl_source {
1299 super::ImplSource::Closure(_)
1300 | super::ImplSource::Generator(_)
1301 | super::ImplSource::FnPointer(_)
1302 | super::ImplSource::TraitAlias(_) => {
1303 debug!(?impl_source);
1306 super::ImplSource::UserDefined(impl_data) => {
1307 // We have to be careful when projecting out of an
1308 // impl because of specialization. If we are not in
1309 // codegen (i.e., projection mode is not "any"), and the
1310 // impl's type is declared as default, then we disable
1311 // projection (even if the trait ref is fully
1312 // monomorphic). In the case where trait ref is not
1313 // fully monomorphic (i.e., includes type parameters),
1314 // this is because those type parameters may
1315 // ultimately be bound to types from other crates that
1316 // may have specialized impls we can't see. In the
1317 // case where the trait ref IS fully monomorphic, this
1318 // is a policy decision that we made in the RFC in
1319 // order to preserve flexibility for the crate that
1320 // defined the specializable impl to specialize later
1321 // for existing types.
1323 // In either case, we handle this by not adding a
1324 // candidate for an impl if it contains a `default`
1327 // NOTE: This should be kept in sync with the similar code in
1328 // `rustc_ty_utils::instance::resolve_associated_item()`.
1330 assoc_ty_def(selcx, impl_data.impl_def_id, obligation.predicate.item_def_id)
1331 .map_err(|ErrorReported| ())?;
1333 if node_item.is_final() {
1334 // Non-specializable items are always projectable.
1337 // Only reveal a specializable default if we're past type-checking
1338 // and the obligation is monomorphic, otherwise passes such as
1339 // transmute checking and polymorphic MIR optimizations could
1340 // get a result which isn't correct for all monomorphizations.
1341 if obligation.param_env.reveal() == Reveal::All {
1342 // NOTE(eddyb) inference variables can resolve to parameters, so
1343 // assume `poly_trait_ref` isn't monomorphic, if it contains any.
1344 let poly_trait_ref = selcx.infcx().resolve_vars_if_possible(poly_trait_ref);
1345 !poly_trait_ref.still_further_specializable()
1348 assoc_ty = ?selcx.tcx().def_path_str(node_item.item.def_id),
1349 ?obligation.predicate,
1350 "assemble_candidates_from_impls: not eligible due to default",
1356 super::ImplSource::DiscriminantKind(..) => {
1357 // While `DiscriminantKind` is automatically implemented for every type,
1358 // the concrete discriminant may not be known yet.
1360 // Any type with multiple potential discriminant types is therefore not eligible.
1361 let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
1363 match self_ty.kind() {
1381 | ty::GeneratorWitness(..)
1384 // Integers and floats always have `u8` as their discriminant.
1385 | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1391 | ty::Placeholder(..)
1393 | ty::Error(_) => false,
1396 super::ImplSource::Pointee(..) => {
1397 // While `Pointee` is automatically implemented for every type,
1398 // the concrete metadata type may not be known yet.
1400 // Any type with multiple potential metadata types is therefore not eligible.
1401 let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
1403 let tail = selcx.tcx().struct_tail_with_normalize(self_ty, |ty| {
1404 normalize_with_depth(
1406 obligation.param_env,
1407 obligation.cause.clone(),
1408 obligation.recursion_depth + 1,
1431 | ty::GeneratorWitness(..)
1433 // If returned by `struct_tail_without_normalization` this is a unit struct
1434 // without any fields, or not a struct, and therefore is Sized.
1436 // If returned by `struct_tail_without_normalization` this is the empty tuple.
1438 // Integers and floats are always Sized, and so have unit type metadata.
1439 | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
1445 | ty::Placeholder(..)
1448 if tail.has_infer_types() {
1449 candidate_set.mark_ambiguous();
1455 super::ImplSource::Param(..) => {
1456 // This case tell us nothing about the value of an
1457 // associated type. Consider:
1460 // trait SomeTrait { type Foo; }
1461 // fn foo<T:SomeTrait>(...) { }
1464 // If the user writes `<T as SomeTrait>::Foo`, then the `T
1465 // : SomeTrait` binding does not help us decide what the
1466 // type `Foo` is (at least, not more specifically than
1467 // what we already knew).
1469 // But wait, you say! What about an example like this:
1472 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1475 // Doesn't the `T : Sometrait<Foo=usize>` predicate help
1476 // resolve `T::Foo`? And of course it does, but in fact
1477 // that single predicate is desugared into two predicates
1478 // in the compiler: a trait predicate (`T : SomeTrait`) and a
1479 // projection. And the projection where clause is handled
1480 // in `assemble_candidates_from_param_env`.
1483 super::ImplSource::Object(_) => {
1484 // Handled by the `Object` projection candidate. See
1485 // `assemble_candidates_from_object_ty` for an explanation of
1486 // why we special case object types.
1489 super::ImplSource::AutoImpl(..)
1490 | super::ImplSource::Builtin(..)
1491 | super::ImplSource::TraitUpcasting(_)
1492 | super::ImplSource::ConstDrop(_) => {
1493 // These traits have no associated types.
1494 selcx.tcx().sess.delay_span_bug(
1495 obligation.cause.span,
1496 &format!("Cannot project an associated type from `{:?}`", impl_source),
1503 if candidate_set.push_candidate(ProjectionTyCandidate::Select(impl_source)) {
1514 fn confirm_candidate<'cx, 'tcx>(
1515 selcx: &mut SelectionContext<'cx, 'tcx>,
1516 obligation: &ProjectionTyObligation<'tcx>,
1517 candidate: ProjectionTyCandidate<'tcx>,
1518 ) -> Progress<'tcx> {
1519 debug!(?obligation, ?candidate, "confirm_candidate");
1520 let mut progress = match candidate {
1521 ProjectionTyCandidate::ParamEnv(poly_projection)
1522 | ProjectionTyCandidate::Object(poly_projection) => {
1523 confirm_param_env_candidate(selcx, obligation, poly_projection, false)
1526 ProjectionTyCandidate::TraitDef(poly_projection) => {
1527 confirm_param_env_candidate(selcx, obligation, poly_projection, true)
1530 ProjectionTyCandidate::Select(impl_source) => {
1531 confirm_select_candidate(selcx, obligation, impl_source)
1534 // When checking for cycle during evaluation, we compare predicates with
1535 // "syntactic" equality. Since normalization generally introduces a type
1536 // with new region variables, we need to resolve them to existing variables
1537 // when possible for this to work. See `auto-trait-projection-recursion.rs`
1538 // for a case where this matters.
1539 if progress.ty.has_infer_regions() {
1540 progress.ty = OpportunisticRegionResolver::new(selcx.infcx()).fold_ty(progress.ty);
1545 fn confirm_select_candidate<'cx, 'tcx>(
1546 selcx: &mut SelectionContext<'cx, 'tcx>,
1547 obligation: &ProjectionTyObligation<'tcx>,
1548 impl_source: Selection<'tcx>,
1549 ) -> Progress<'tcx> {
1551 super::ImplSource::UserDefined(data) => confirm_impl_candidate(selcx, obligation, data),
1552 super::ImplSource::Generator(data) => confirm_generator_candidate(selcx, obligation, data),
1553 super::ImplSource::Closure(data) => confirm_closure_candidate(selcx, obligation, data),
1554 super::ImplSource::FnPointer(data) => confirm_fn_pointer_candidate(selcx, obligation, data),
1555 super::ImplSource::DiscriminantKind(data) => {
1556 confirm_discriminant_kind_candidate(selcx, obligation, data)
1558 super::ImplSource::Pointee(data) => confirm_pointee_candidate(selcx, obligation, data),
1559 super::ImplSource::Object(_)
1560 | super::ImplSource::AutoImpl(..)
1561 | super::ImplSource::Param(..)
1562 | super::ImplSource::Builtin(..)
1563 | super::ImplSource::TraitUpcasting(_)
1564 | super::ImplSource::TraitAlias(..)
1565 | super::ImplSource::ConstDrop(_) => {
1566 // we don't create Select candidates with this kind of resolution
1568 obligation.cause.span,
1569 "Cannot project an associated type from `{:?}`",
1576 fn confirm_generator_candidate<'cx, 'tcx>(
1577 selcx: &mut SelectionContext<'cx, 'tcx>,
1578 obligation: &ProjectionTyObligation<'tcx>,
1579 impl_source: ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>,
1580 ) -> Progress<'tcx> {
1581 let gen_sig = impl_source.substs.as_generator().poly_sig();
1582 let Normalized { value: gen_sig, obligations } = normalize_with_depth(
1584 obligation.param_env,
1585 obligation.cause.clone(),
1586 obligation.recursion_depth + 1,
1590 debug!(?obligation, ?gen_sig, ?obligations, "confirm_generator_candidate");
1592 let tcx = selcx.tcx();
1594 let gen_def_id = tcx.require_lang_item(LangItem::Generator, None);
1596 let predicate = super::util::generator_trait_ref_and_outputs(
1599 obligation.predicate.self_ty(),
1602 .map_bound(|(trait_ref, yield_ty, return_ty)| {
1603 let name = tcx.associated_item(obligation.predicate.item_def_id).ident.name;
1604 let ty = if name == sym::Return {
1606 } else if name == sym::Yield {
1612 ty::ProjectionPredicate {
1613 projection_ty: ty::ProjectionTy {
1614 substs: trait_ref.substs,
1615 item_def_id: obligation.predicate.item_def_id,
1621 confirm_param_env_candidate(selcx, obligation, predicate, false)
1622 .with_addl_obligations(impl_source.nested)
1623 .with_addl_obligations(obligations)
1626 fn confirm_discriminant_kind_candidate<'cx, 'tcx>(
1627 selcx: &mut SelectionContext<'cx, 'tcx>,
1628 obligation: &ProjectionTyObligation<'tcx>,
1629 _: ImplSourceDiscriminantKindData,
1630 ) -> Progress<'tcx> {
1631 let tcx = selcx.tcx();
1633 let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
1634 // We get here from `poly_project_and_unify_type` which replaces bound vars
1635 // with placeholders
1636 debug_assert!(!self_ty.has_escaping_bound_vars());
1637 let substs = tcx.mk_substs([self_ty.into()].iter());
1639 let discriminant_def_id = tcx.require_lang_item(LangItem::Discriminant, None);
1641 let predicate = ty::ProjectionPredicate {
1642 projection_ty: ty::ProjectionTy { substs, item_def_id: discriminant_def_id },
1643 term: self_ty.discriminant_ty(tcx).into(),
1646 // We get here from `poly_project_and_unify_type` which replaces bound vars
1647 // with placeholders, so dummy is okay here.
1648 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1651 fn confirm_pointee_candidate<'cx, 'tcx>(
1652 selcx: &mut SelectionContext<'cx, 'tcx>,
1653 obligation: &ProjectionTyObligation<'tcx>,
1654 _: ImplSourcePointeeData,
1655 ) -> Progress<'tcx> {
1656 let tcx = selcx.tcx();
1657 let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty());
1659 let mut obligations = vec![];
1660 let metadata_ty = self_ty.ptr_metadata_ty(tcx, |ty| {
1661 normalize_with_depth_to(
1663 obligation.param_env,
1664 obligation.cause.clone(),
1665 obligation.recursion_depth + 1,
1671 let substs = tcx.mk_substs([self_ty.into()].iter());
1672 let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, None);
1674 let predicate = ty::ProjectionPredicate {
1675 projection_ty: ty::ProjectionTy { substs, item_def_id: metadata_def_id },
1676 term: metadata_ty.into(),
1679 confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false)
1680 .with_addl_obligations(obligations)
1683 fn confirm_fn_pointer_candidate<'cx, 'tcx>(
1684 selcx: &mut SelectionContext<'cx, 'tcx>,
1685 obligation: &ProjectionTyObligation<'tcx>,
1686 fn_pointer_impl_source: ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>,
1687 ) -> Progress<'tcx> {
1688 let fn_type = selcx.infcx().shallow_resolve(fn_pointer_impl_source.fn_ty);
1689 let sig = fn_type.fn_sig(selcx.tcx());
1690 let Normalized { value: sig, obligations } = normalize_with_depth(
1692 obligation.param_env,
1693 obligation.cause.clone(),
1694 obligation.recursion_depth + 1,
1698 confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes)
1699 .with_addl_obligations(fn_pointer_impl_source.nested)
1700 .with_addl_obligations(obligations)
1703 fn confirm_closure_candidate<'cx, 'tcx>(
1704 selcx: &mut SelectionContext<'cx, 'tcx>,
1705 obligation: &ProjectionTyObligation<'tcx>,
1706 impl_source: ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>,
1707 ) -> Progress<'tcx> {
1708 let closure_sig = impl_source.substs.as_closure().sig();
1709 let Normalized { value: closure_sig, obligations } = normalize_with_depth(
1711 obligation.param_env,
1712 obligation.cause.clone(),
1713 obligation.recursion_depth + 1,
1717 debug!(?obligation, ?closure_sig, ?obligations, "confirm_closure_candidate");
1719 confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No)
1720 .with_addl_obligations(impl_source.nested)
1721 .with_addl_obligations(obligations)
1724 fn confirm_callable_candidate<'cx, 'tcx>(
1725 selcx: &mut SelectionContext<'cx, 'tcx>,
1726 obligation: &ProjectionTyObligation<'tcx>,
1727 fn_sig: ty::PolyFnSig<'tcx>,
1728 flag: util::TupleArgumentsFlag,
1729 ) -> Progress<'tcx> {
1730 let tcx = selcx.tcx();
1732 debug!(?obligation, ?fn_sig, "confirm_callable_candidate");
1734 let fn_once_def_id = tcx.require_lang_item(LangItem::FnOnce, None);
1735 let fn_once_output_def_id = tcx.require_lang_item(LangItem::FnOnceOutput, None);
1737 let predicate = super::util::closure_trait_ref_and_return_type(
1740 obligation.predicate.self_ty(),
1744 .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate {
1745 projection_ty: ty::ProjectionTy {
1746 substs: trait_ref.substs,
1747 item_def_id: fn_once_output_def_id,
1749 term: ret_type.into(),
1752 confirm_param_env_candidate(selcx, obligation, predicate, true)
1755 fn confirm_param_env_candidate<'cx, 'tcx>(
1756 selcx: &mut SelectionContext<'cx, 'tcx>,
1757 obligation: &ProjectionTyObligation<'tcx>,
1758 poly_cache_entry: ty::PolyProjectionPredicate<'tcx>,
1759 potentially_unnormalized_candidate: bool,
1760 ) -> Progress<'tcx> {
1761 let infcx = selcx.infcx();
1762 let cause = &obligation.cause;
1763 let param_env = obligation.param_env;
1765 let (cache_entry, _) = infcx.replace_bound_vars_with_fresh_vars(
1767 LateBoundRegionConversionTime::HigherRankedType,
1771 let cache_projection = cache_entry.projection_ty;
1772 let mut nested_obligations = Vec::new();
1773 let obligation_projection = obligation.predicate;
1774 let obligation_projection = ensure_sufficient_stack(|| {
1775 normalize_with_depth_to(
1777 obligation.param_env,
1778 obligation.cause.clone(),
1779 obligation.recursion_depth + 1,
1780 obligation_projection,
1781 &mut nested_obligations,
1784 let cache_projection = if potentially_unnormalized_candidate {
1785 ensure_sufficient_stack(|| {
1786 normalize_with_depth_to(
1788 obligation.param_env,
1789 obligation.cause.clone(),
1790 obligation.recursion_depth + 1,
1792 &mut nested_obligations,
1799 debug!(?cache_projection, ?obligation_projection);
1801 match infcx.at(cause, param_env).eq(cache_projection, obligation_projection) {
1802 Ok(InferOk { value: _, obligations }) => {
1803 nested_obligations.extend(obligations);
1804 assoc_ty_own_obligations(selcx, obligation, &mut nested_obligations);
1805 // FIXME(associated_const_equality): Handle consts here as well? Maybe this progress type should just take
1807 Progress { ty: cache_entry.term.ty().unwrap(), obligations: nested_obligations }
1811 "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}",
1812 obligation, poly_cache_entry, e,
1814 debug!("confirm_param_env_candidate: {}", msg);
1815 let err = infcx.tcx.ty_error_with_message(obligation.cause.span, &msg);
1816 Progress { ty: err, obligations: vec![] }
1821 fn confirm_impl_candidate<'cx, 'tcx>(
1822 selcx: &mut SelectionContext<'cx, 'tcx>,
1823 obligation: &ProjectionTyObligation<'tcx>,
1824 impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>,
1825 ) -> Progress<'tcx> {
1826 let tcx = selcx.tcx();
1828 let ImplSourceUserDefinedData { impl_def_id, substs, mut nested } = impl_impl_source;
1829 let assoc_item_id = obligation.predicate.item_def_id;
1830 let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
1832 let param_env = obligation.param_env;
1833 let assoc_ty = match assoc_ty_def(selcx, impl_def_id, assoc_item_id) {
1834 Ok(assoc_ty) => assoc_ty,
1835 Err(ErrorReported) => return Progress { ty: tcx.ty_error(), obligations: nested },
1838 if !assoc_ty.item.defaultness.has_value() {
1839 // This means that the impl is missing a definition for the
1840 // associated type. This error will be reported by the type
1841 // checker method `check_impl_items_against_trait`, so here we
1842 // just return Error.
1844 "confirm_impl_candidate: no associated type {:?} for {:?}",
1845 assoc_ty.item.ident, obligation.predicate
1847 return Progress { ty: tcx.ty_error(), obligations: nested };
1849 // If we're trying to normalize `<Vec<u32> as X>::A<S>` using
1850 //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then:
1852 // * `obligation.predicate.substs` is `[Vec<u32>, S]`
1853 // * `substs` is `[u32]`
1854 // * `substs` ends up as `[u32, S]`
1855 let substs = obligation.predicate.substs.rebase_onto(tcx, trait_def_id, substs);
1857 translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.defining_node);
1858 let ty = tcx.type_of(assoc_ty.item.def_id);
1859 if substs.len() != tcx.generics_of(assoc_ty.item.def_id).count() {
1860 let err = tcx.ty_error_with_message(
1861 obligation.cause.span,
1862 "impl item and trait item have different parameter counts",
1864 Progress { ty: err, obligations: nested }
1866 assoc_ty_own_obligations(selcx, obligation, &mut nested);
1867 Progress { ty: ty.subst(tcx, substs), obligations: nested }
1871 // Get obligations corresponding to the predicates from the where-clause of the
1872 // associated type itself.
1873 // Note: `feature(generic_associated_types)` is required to write such
1874 // predicates, even for non-generic associcated types.
1875 fn assoc_ty_own_obligations<'cx, 'tcx>(
1876 selcx: &mut SelectionContext<'cx, 'tcx>,
1877 obligation: &ProjectionTyObligation<'tcx>,
1878 nested: &mut Vec<PredicateObligation<'tcx>>,
1880 let tcx = selcx.tcx();
1881 for predicate in tcx
1882 .predicates_of(obligation.predicate.item_def_id)
1883 .instantiate_own(tcx, obligation.predicate.substs)
1886 let normalized = normalize_with_depth_to(
1888 obligation.param_env,
1889 obligation.cause.clone(),
1890 obligation.recursion_depth + 1,
1894 nested.push(Obligation::with_depth(
1895 obligation.cause.clone(),
1896 obligation.recursion_depth + 1,
1897 obligation.param_env,
1903 /// Locate the definition of an associated type in the specialization hierarchy,
1904 /// starting from the given impl.
1906 /// Based on the "projection mode", this lookup may in fact only examine the
1907 /// topmost impl. See the comments for `Reveal` for more details.
1909 selcx: &SelectionContext<'_, '_>,
1911 assoc_ty_def_id: DefId,
1912 ) -> Result<specialization_graph::LeafDef, ErrorReported> {
1913 let tcx = selcx.tcx();
1914 let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id;
1915 let trait_def = tcx.trait_def(trait_def_id);
1917 // This function may be called while we are still building the
1918 // specialization graph that is queried below (via TraitDef::ancestors()),
1919 // so, in order to avoid unnecessary infinite recursion, we manually look
1920 // for the associated item at the given impl.
1921 // If there is no such item in that impl, this function will fail with a
1922 // cycle error if the specialization graph is currently being built.
1923 if let Some(&impl_item_id) = tcx.impl_item_implementor_ids(impl_def_id).get(&assoc_ty_def_id) {
1924 let item = tcx.associated_item(impl_item_id);
1925 let impl_node = specialization_graph::Node::Impl(impl_def_id);
1926 return Ok(specialization_graph::LeafDef {
1928 defining_node: impl_node,
1929 finalizing_node: if item.defaultness.is_default() { None } else { Some(impl_node) },
1933 let ancestors = trait_def.ancestors(tcx, impl_def_id)?;
1934 if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_ty_def_id) {
1937 // This is saying that neither the trait nor
1938 // the impl contain a definition for this
1939 // associated type. Normally this situation
1940 // could only arise through a compiler bug --
1941 // if the user wrote a bad item name, it
1942 // should have failed in astconv.
1944 "No associated type `{}` for {}",
1945 tcx.item_name(assoc_ty_def_id),
1946 tcx.def_path_str(impl_def_id)
1951 crate trait ProjectionCacheKeyExt<'cx, 'tcx>: Sized {
1952 fn from_poly_projection_predicate(
1953 selcx: &mut SelectionContext<'cx, 'tcx>,
1954 predicate: ty::PolyProjectionPredicate<'tcx>,
1958 impl<'cx, 'tcx> ProjectionCacheKeyExt<'cx, 'tcx> for ProjectionCacheKey<'tcx> {
1959 fn from_poly_projection_predicate(
1960 selcx: &mut SelectionContext<'cx, 'tcx>,
1961 predicate: ty::PolyProjectionPredicate<'tcx>,
1963 let infcx = selcx.infcx();
1964 // We don't do cross-snapshot caching of obligations with escaping regions,
1965 // so there's no cache key to use
1966 predicate.no_bound_vars().map(|predicate| {
1967 ProjectionCacheKey::new(
1968 // We don't attempt to match up with a specific type-variable state
1969 // from a specific call to `opt_normalize_projection_type` - if
1970 // there's no precise match, the original cache entry is "stranded"
1972 infcx.resolve_vars_if_possible(predicate.projection_ty),