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 crate::traits
::query
::evaluate_obligation
::InferCtxtExt
as _
;
23 use crate::traits
::select
::ProjectionMatchesProjection
;
24 use rustc_data_structures
::sso
::SsoHashSet
;
25 use rustc_data_structures
::stack
::ensure_sufficient_stack
;
26 use rustc_errors
::ErrorGuaranteed
;
27 use rustc_hir
::def
::DefKind
;
28 use rustc_hir
::def_id
::DefId
;
29 use rustc_hir
::lang_items
::LangItem
;
30 use rustc_infer
::infer
::resolve
::OpportunisticRegionResolver
;
31 use rustc_infer
::traits
::ObligationCauseCode
;
32 use rustc_middle
::traits
::select
::OverflowError
;
33 use rustc_middle
::ty
::fold
::{MaxUniverse, TypeFoldable, TypeFolder, TypeSuperFoldable}
;
34 use rustc_middle
::ty
::subst
::Subst
;
35 use rustc_middle
::ty
::{self, EarlyBinder, Term, ToPredicate, Ty, TyCtxt}
;
36 use rustc_span
::symbol
::sym
;
38 use std
::collections
::BTreeMap
;
40 pub use rustc_middle
::traits
::Reveal
;
42 pub type PolyProjectionObligation
<'tcx
> = Obligation
<'tcx
, ty
::PolyProjectionPredicate
<'tcx
>>;
44 pub type ProjectionObligation
<'tcx
> = Obligation
<'tcx
, ty
::ProjectionPredicate
<'tcx
>>;
46 pub type ProjectionTyObligation
<'tcx
> = Obligation
<'tcx
, ty
::ProjectionTy
<'tcx
>>;
48 pub(super) struct InProgress
;
50 /// When attempting to resolve `<T as TraitRef>::Name` ...
52 pub enum ProjectionError
<'tcx
> {
53 /// ...we found multiple sources of information and couldn't resolve the ambiguity.
56 /// ...an error occurred matching `T : TraitRef`
57 TraitSelectionError(SelectionError
<'tcx
>),
60 #[derive(PartialEq, Eq, Debug)]
61 enum ProjectionCandidate
<'tcx
> {
62 /// From a where-clause in the env or object type
63 ParamEnv(ty
::PolyProjectionPredicate
<'tcx
>),
65 /// From the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
66 TraitDef(ty
::PolyProjectionPredicate
<'tcx
>),
68 /// Bounds specified on an object type
69 Object(ty
::PolyProjectionPredicate
<'tcx
>),
71 /// From an "impl" (or a "pseudo-impl" returned by select)
72 Select(Selection
<'tcx
>),
75 enum ProjectionCandidateSet
<'tcx
> {
77 Single(ProjectionCandidate
<'tcx
>),
79 Error(SelectionError
<'tcx
>),
82 impl<'tcx
> ProjectionCandidateSet
<'tcx
> {
83 fn mark_ambiguous(&mut self) {
84 *self = ProjectionCandidateSet
::Ambiguous
;
87 fn mark_error(&mut self, err
: SelectionError
<'tcx
>) {
88 *self = ProjectionCandidateSet
::Error(err
);
91 // Returns true if the push was successful, or false if the candidate
92 // was discarded -- this could be because of ambiguity, or because
93 // a higher-priority candidate is already there.
94 fn push_candidate(&mut self, candidate
: ProjectionCandidate
<'tcx
>) -> bool
{
95 use self::ProjectionCandidate
::*;
96 use self::ProjectionCandidateSet
::*;
98 // This wacky variable is just used to try and
99 // make code readable and avoid confusing paths.
100 // It is assigned a "value" of `()` only on those
101 // paths in which we wish to convert `*self` to
102 // ambiguous (and return false, because the candidate
103 // was not used). On other paths, it is not assigned,
104 // and hence if those paths *could* reach the code that
105 // comes after the match, this fn would not compile.
106 let convert_to_ambiguous
;
110 *self = Single(candidate
);
115 // Duplicates can happen inside ParamEnv. In the case, we
116 // perform a lazy deduplication.
117 if current
== &candidate
{
121 // Prefer where-clauses. As in select, if there are multiple
122 // candidates, we prefer where-clause candidates over impls. This
123 // may seem a bit surprising, since impls are the source of
124 // "truth" in some sense, but in fact some of the impls that SEEM
125 // applicable are not, because of nested obligations. Where
126 // clauses are the safer choice. See the comment on
127 // `select::SelectionCandidate` and #21974 for more details.
128 match (current
, candidate
) {
129 (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous
= (),
130 (ParamEnv(..), _
) => return false,
131 (_
, ParamEnv(..)) => unreachable
!(),
132 (_
, _
) => convert_to_ambiguous
= (),
136 Ambiguous
| Error(..) => {
141 // We only ever get here when we moved from a single candidate
143 let () = convert_to_ambiguous
;
149 /// States returned from `poly_project_and_unify_type`. Takes the place
150 /// of the old return type, which was:
151 /// ```ignore (not-rust)
153 /// Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>,
154 /// MismatchedProjectionTypes<'tcx>,
157 pub(super) enum ProjectAndUnifyResult
<'tcx
> {
158 /// The projection bound holds subject to the given obligations. If the
159 /// projection cannot be normalized because the required trait bound does
160 /// not hold, this is returned, with `obligations` being a predicate that
161 /// cannot be proven.
162 Holds(Vec
<PredicateObligation
<'tcx
>>),
163 /// The projection cannot be normalized due to ambiguity. Resolving some
164 /// inference variables in the projection may fix this.
166 /// The project cannot be normalized because `poly_project_and_unify_type`
167 /// is called recursively while normalizing the same projection.
169 // the projection can be normalized, but is not equal to the expected type.
170 // Returns the type error that arose from the mismatch.
171 MismatchedProjectionTypes(MismatchedProjectionTypes
<'tcx
>),
174 /// Evaluates constraints of the form:
175 /// ```ignore (not-rust)
176 /// for<...> <T as Trait>::U == V
178 /// If successful, this may result in additional obligations. Also returns
179 /// the projection cache key used to track these additional obligations.
180 #[instrument(level = "debug", skip(selcx))]
181 pub(super) fn poly_project_and_unify_type
<'cx
, 'tcx
>(
182 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
183 obligation
: &PolyProjectionObligation
<'tcx
>,
184 ) -> ProjectAndUnifyResult
<'tcx
> {
185 let infcx
= selcx
.infcx();
186 let r
= infcx
.commit_if_ok(|_snapshot
| {
187 let old_universe
= infcx
.universe();
188 let placeholder_predicate
=
189 infcx
.replace_bound_vars_with_placeholders(obligation
.predicate
);
190 let new_universe
= infcx
.universe();
192 let placeholder_obligation
= obligation
.with(placeholder_predicate
);
193 match project_and_unify_type(selcx
, &placeholder_obligation
) {
194 ProjectAndUnifyResult
::MismatchedProjectionTypes(e
) => Err(e
),
195 ProjectAndUnifyResult
::Holds(obligations
)
196 if old_universe
!= new_universe
197 && selcx
.tcx().features().generic_associated_types_extended
=>
199 // If the `generic_associated_types_extended` feature is active, then we ignore any
200 // obligations references lifetimes from any universe greater than or equal to the
201 // universe just created. Otherwise, we can end up with something like `for<'a> I: 'a`,
202 // which isn't quite what we want. Ideally, we want either an implied
203 // `for<'a where I: 'a> I: 'a` or we want to "lazily" check these hold when we
204 // substitute concrete regions. There is design work to be done here; until then,
205 // however, this allows experimenting potential GAT features without running into
206 // well-formedness issues.
207 let new_obligations
= obligations
209 .filter(|obligation
| {
210 let mut visitor
= MaxUniverse
::new();
211 obligation
.predicate
.visit_with(&mut visitor
);
212 visitor
.max_universe() < new_universe
215 Ok(ProjectAndUnifyResult
::Holds(new_obligations
))
223 Err(err
) => ProjectAndUnifyResult
::MismatchedProjectionTypes(err
),
227 /// Evaluates constraints of the form:
228 /// ```ignore (not-rust)
229 /// <T as Trait>::U == V
231 /// If successful, this may result in additional obligations.
233 /// See [poly_project_and_unify_type] for an explanation of the return value.
234 #[tracing::instrument(level = "debug", skip(selcx))]
235 fn project_and_unify_type
<'cx
, 'tcx
>(
236 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
237 obligation
: &ProjectionObligation
<'tcx
>,
238 ) -> ProjectAndUnifyResult
<'tcx
> {
239 let mut obligations
= vec
![];
241 let infcx
= selcx
.infcx();
242 let normalized
= match opt_normalize_projection_type(
244 obligation
.param_env
,
245 obligation
.predicate
.projection_ty
,
246 obligation
.cause
.clone(),
247 obligation
.recursion_depth
,
251 Ok(None
) => return ProjectAndUnifyResult
::FailedNormalization
,
252 Err(InProgress
) => return ProjectAndUnifyResult
::Recursive
,
254 debug
!(?normalized
, ?obligations
, "project_and_unify_type result");
255 let actual
= obligation
.predicate
.term
;
256 // HACK: lazy TAIT would regress src/test/ui/impl-trait/nested-return-type2.rs, so we add
257 // a back-compat hack hat converts the RPITs into inference vars, just like they were before
259 // This does not affect TAITs in general, as tested in the nested-return-type-tait* tests.
260 let InferOk { value: actual, obligations: new }
=
261 selcx
.infcx().replace_opaque_types_with_inference_vars(
263 obligation
.cause
.body_id
,
264 obligation
.cause
.span
,
265 ObligationCauseCode
::MiscObligation
,
266 obligation
.param_env
,
268 obligations
.extend(new
);
270 match infcx
.at(&obligation
.cause
, obligation
.param_env
).eq(normalized
, actual
) {
271 Ok(InferOk { obligations: inferred_obligations, value: () }
) => {
272 obligations
.extend(inferred_obligations
);
273 ProjectAndUnifyResult
::Holds(obligations
)
276 debug
!("equating types encountered error {:?}", err
);
277 ProjectAndUnifyResult
::MismatchedProjectionTypes(MismatchedProjectionTypes { err }
)
282 /// Normalizes any associated type projections in `value`, replacing
283 /// them with a fully resolved type where possible. The return value
284 /// combines the normalized result and any additional obligations that
285 /// were incurred as result.
286 pub fn normalize
<'a
, 'b
, 'tcx
, T
>(
287 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
288 param_env
: ty
::ParamEnv
<'tcx
>,
289 cause
: ObligationCause
<'tcx
>,
291 ) -> Normalized
<'tcx
, T
>
293 T
: TypeFoldable
<'tcx
>,
295 let mut obligations
= Vec
::new();
296 let value
= normalize_to(selcx
, param_env
, cause
, value
, &mut obligations
);
297 Normalized { value, obligations }
300 pub fn normalize_to
<'a
, 'b
, 'tcx
, T
>(
301 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
302 param_env
: ty
::ParamEnv
<'tcx
>,
303 cause
: ObligationCause
<'tcx
>,
305 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
308 T
: TypeFoldable
<'tcx
>,
310 normalize_with_depth_to(selcx
, param_env
, cause
, 0, value
, obligations
)
313 /// As `normalize`, but with a custom depth.
314 pub fn normalize_with_depth
<'a
, 'b
, 'tcx
, T
>(
315 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
316 param_env
: ty
::ParamEnv
<'tcx
>,
317 cause
: ObligationCause
<'tcx
>,
320 ) -> Normalized
<'tcx
, T
>
322 T
: TypeFoldable
<'tcx
>,
324 let mut obligations
= Vec
::new();
325 let value
= normalize_with_depth_to(selcx
, param_env
, cause
, depth
, value
, &mut obligations
);
326 Normalized { value, obligations }
329 #[instrument(level = "info", skip(selcx, param_env, cause, obligations))]
330 pub fn normalize_with_depth_to
<'a
, 'b
, 'tcx
, T
>(
331 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
332 param_env
: ty
::ParamEnv
<'tcx
>,
333 cause
: ObligationCause
<'tcx
>,
336 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
339 T
: TypeFoldable
<'tcx
>,
341 debug
!(obligations
.len
= obligations
.len());
342 let mut normalizer
= AssocTypeNormalizer
::new(selcx
, param_env
, cause
, depth
, obligations
);
343 let result
= ensure_sufficient_stack(|| normalizer
.fold(value
));
344 debug
!(?result
, obligations
.len
= normalizer
.obligations
.len());
345 debug
!(?normalizer
.obligations
,);
349 #[instrument(level = "info", skip(selcx, param_env, cause, obligations))]
350 pub fn try_normalize_with_depth_to
<'a
, 'b
, 'tcx
, T
>(
351 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
352 param_env
: ty
::ParamEnv
<'tcx
>,
353 cause
: ObligationCause
<'tcx
>,
356 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
359 T
: TypeFoldable
<'tcx
>,
361 debug
!(obligations
.len
= obligations
.len());
362 let mut normalizer
= AssocTypeNormalizer
::new_without_eager_inference_replacement(
369 let result
= ensure_sufficient_stack(|| normalizer
.fold(value
));
370 debug
!(?result
, obligations
.len
= normalizer
.obligations
.len());
371 debug
!(?normalizer
.obligations
,);
375 pub(crate) fn needs_normalization
<'tcx
, T
: TypeFoldable
<'tcx
>>(value
: &T
, reveal
: Reveal
) -> bool
{
377 Reveal
::UserFacing
=> value
378 .has_type_flags(ty
::TypeFlags
::HAS_TY_PROJECTION
| ty
::TypeFlags
::HAS_CT_PROJECTION
),
379 Reveal
::All
=> value
.has_type_flags(
380 ty
::TypeFlags
::HAS_TY_PROJECTION
381 | ty
::TypeFlags
::HAS_TY_OPAQUE
382 | ty
::TypeFlags
::HAS_CT_PROJECTION
,
387 struct AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
388 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
389 param_env
: ty
::ParamEnv
<'tcx
>,
390 cause
: ObligationCause
<'tcx
>,
391 obligations
: &'a
mut Vec
<PredicateObligation
<'tcx
>>,
393 universes
: Vec
<Option
<ty
::UniverseIndex
>>,
394 /// If true, when a projection is unable to be completed, an inference
395 /// variable will be created and an obligation registered to project to that
396 /// inference variable. Also, constants will be eagerly evaluated.
397 eager_inference_replacement
: bool
,
400 impl<'a
, 'b
, 'tcx
> AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
402 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
403 param_env
: ty
::ParamEnv
<'tcx
>,
404 cause
: ObligationCause
<'tcx
>,
406 obligations
: &'a
mut Vec
<PredicateObligation
<'tcx
>>,
407 ) -> AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
408 AssocTypeNormalizer
{
415 eager_inference_replacement
: true,
419 fn new_without_eager_inference_replacement(
420 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
421 param_env
: ty
::ParamEnv
<'tcx
>,
422 cause
: ObligationCause
<'tcx
>,
424 obligations
: &'a
mut Vec
<PredicateObligation
<'tcx
>>,
425 ) -> AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
426 AssocTypeNormalizer
{
433 eager_inference_replacement
: false,
437 fn fold
<T
: TypeFoldable
<'tcx
>>(&mut self, value
: T
) -> T
{
438 let value
= self.selcx
.infcx().resolve_vars_if_possible(value
);
442 !value
.has_escaping_bound_vars(),
443 "Normalizing {:?} without wrapping in a `Binder`",
447 if !needs_normalization(&value
, self.param_env
.reveal()) {
450 value
.fold_with(self)
455 impl<'a
, 'b
, 'tcx
> TypeFolder
<'tcx
> for AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
456 fn tcx
<'c
>(&'c
self) -> TyCtxt
<'tcx
> {
460 fn fold_binder
<T
: TypeFoldable
<'tcx
>>(
462 t
: ty
::Binder
<'tcx
, T
>,
463 ) -> ty
::Binder
<'tcx
, T
> {
464 self.universes
.push(None
);
465 let t
= t
.super_fold_with(self);
466 self.universes
.pop();
470 fn fold_ty(&mut self, ty
: Ty
<'tcx
>) -> Ty
<'tcx
> {
471 if !needs_normalization(&ty
, self.param_env
.reveal()) {
475 // We try to be a little clever here as a performance optimization in
476 // cases where there are nested projections under binders.
479 // for<'a> fn(<T as Foo>::One<'a, Box<dyn Bar<'a, Item=<T as Foo>::Two<'a>>>>)
481 // We normalize the substs on the projection before the projecting, but
482 // if we're naive, we'll
483 // replace bound vars on inner, project inner, replace placeholders on inner,
484 // replace bound vars on outer, project outer, replace placeholders on outer
486 // However, if we're a bit more clever, we can replace the bound vars
487 // on the entire type before normalizing nested projections, meaning we
488 // replace bound vars on outer, project inner,
489 // project outer, replace placeholders on outer
491 // This is possible because the inner `'a` will already be a placeholder
492 // when we need to normalize the inner projection
494 // On the other hand, this does add a bit of complexity, since we only
495 // replace bound vars if the current type is a `Projection` and we need
496 // to make sure we don't forget to fold the substs regardless.
499 // This is really important. While we *can* handle this, this has
500 // severe performance implications for large opaque types with
501 // late-bound regions. See `issue-88862` benchmark.
502 ty
::Opaque(def_id
, substs
) if !substs
.has_escaping_bound_vars() => {
503 // Only normalize `impl Trait` outside of type inference, usually in codegen.
504 match self.param_env
.reveal() {
505 Reveal
::UserFacing
=> ty
.super_fold_with(self),
508 let recursion_limit
= self.tcx().recursion_limit();
509 if !recursion_limit
.value_within_limit(self.depth
) {
510 let obligation
= Obligation
::with_depth(
516 self.selcx
.infcx().report_overflow_error(&obligation
, true);
519 let substs
= substs
.fold_with(self);
520 let generic_ty
= self.tcx().bound_type_of(def_id
);
521 let concrete_ty
= generic_ty
.subst(self.tcx(), substs
);
523 let folded_ty
= self.fold_ty(concrete_ty
);
530 ty
::Projection(data
) if !data
.has_escaping_bound_vars() => {
531 // This branch is *mostly* just an optimization: when we don't
532 // have escaping bound vars, we don't need to replace them with
533 // placeholders (see branch below). *Also*, we know that we can
534 // register an obligation to *later* project, since we know
535 // there won't be bound vars there.
536 let data
= data
.fold_with(self);
537 let normalized_ty
= if self.eager_inference_replacement
{
538 normalize_projection_type(
544 &mut self.obligations
,
547 opt_normalize_projection_type(
553 &mut self.obligations
,
557 .unwrap_or_else(|| ty
::Term
::Ty(ty
.super_fold_with(self)))
563 obligations
.len
= ?
self.obligations
.len(),
564 "AssocTypeNormalizer: normalized type"
566 normalized_ty
.ty().unwrap()
569 ty
::Projection(data
) => {
570 // If there are escaping bound vars, we temporarily replace the
571 // bound vars with placeholders. Note though, that in the case
572 // that we still can't project for whatever reason (e.g. self
573 // type isn't known enough), we *can't* register an obligation
574 // and return an inference variable (since then that obligation
575 // would have bound vars and that's a can of worms). Instead,
576 // we just give up and fall back to pretending like we never tried!
578 // Note: this isn't necessarily the final approach here; we may
579 // want to figure out how to register obligations with escaping vars
580 // or handle this some other way.
582 let infcx
= self.selcx
.infcx();
583 let (data
, mapped_regions
, mapped_types
, mapped_consts
) =
584 BoundVarReplacer
::replace_bound_vars(infcx
, &mut self.universes
, data
);
585 let data
= data
.fold_with(self);
586 let normalized_ty
= opt_normalize_projection_type(
592 &mut self.obligations
,
596 .map(|term
| term
.ty().unwrap())
597 .map(|normalized_ty
| {
598 PlaceholderReplacer
::replace_placeholders(
607 .unwrap_or_else(|| ty
.super_fold_with(self));
613 obligations
.len
= ?
self.obligations
.len(),
614 "AssocTypeNormalizer: normalized type"
619 _
=> ty
.super_fold_with(self),
623 #[instrument(skip(self), level = "debug")]
624 fn fold_const(&mut self, constant
: ty
::Const
<'tcx
>) -> ty
::Const
<'tcx
> {
625 if self.selcx
.tcx().lazy_normalization() || !self.eager_inference_replacement
{
628 let constant
= constant
.super_fold_with(self);
630 debug
!("self.param_env: {:?}", self.param_env
);
631 constant
.eval(self.selcx
.tcx(), self.param_env
)
636 pub struct BoundVarReplacer
<'me
, 'tcx
> {
637 infcx
: &'me InferCtxt
<'me
, 'tcx
>,
638 // These three maps track the bound variable that were replaced by placeholders. It might be
639 // nice to remove these since we already have the `kind` in the placeholder; we really just need
640 // the `var` (but we *could* bring that into scope if we were to track them as we pass them).
641 mapped_regions
: BTreeMap
<ty
::PlaceholderRegion
, ty
::BoundRegion
>,
642 mapped_types
: BTreeMap
<ty
::PlaceholderType
, ty
::BoundTy
>,
643 mapped_consts
: BTreeMap
<ty
::PlaceholderConst
<'tcx
>, ty
::BoundVar
>,
644 // The current depth relative to *this* folding, *not* the entire normalization. In other words,
645 // the depth of binders we've passed here.
646 current_index
: ty
::DebruijnIndex
,
647 // The `UniverseIndex` of the binding levels above us. These are optional, since we are lazy:
648 // we don't actually create a universe until we see a bound var we have to replace.
649 universe_indices
: &'me
mut Vec
<Option
<ty
::UniverseIndex
>>,
652 impl<'me
, 'tcx
> BoundVarReplacer
<'me
, 'tcx
> {
653 /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that
654 /// use a binding level above `universe_indices.len()`, we fail.
655 pub fn replace_bound_vars
<T
: TypeFoldable
<'tcx
>>(
656 infcx
: &'me InferCtxt
<'me
, 'tcx
>,
657 universe_indices
: &'me
mut Vec
<Option
<ty
::UniverseIndex
>>,
661 BTreeMap
<ty
::PlaceholderRegion
, ty
::BoundRegion
>,
662 BTreeMap
<ty
::PlaceholderType
, ty
::BoundTy
>,
663 BTreeMap
<ty
::PlaceholderConst
<'tcx
>, ty
::BoundVar
>,
665 let mapped_regions
: BTreeMap
<ty
::PlaceholderRegion
, ty
::BoundRegion
> = BTreeMap
::new();
666 let mapped_types
: BTreeMap
<ty
::PlaceholderType
, ty
::BoundTy
> = BTreeMap
::new();
667 let mapped_consts
: BTreeMap
<ty
::PlaceholderConst
<'tcx
>, ty
::BoundVar
> = BTreeMap
::new();
669 let mut replacer
= BoundVarReplacer
{
674 current_index
: ty
::INNERMOST
,
678 let value
= value
.fold_with(&mut replacer
);
680 (value
, replacer
.mapped_regions
, replacer
.mapped_types
, replacer
.mapped_consts
)
683 fn universe_for(&mut self, debruijn
: ty
::DebruijnIndex
) -> ty
::UniverseIndex
{
684 let infcx
= self.infcx
;
686 self.universe_indices
.len() + self.current_index
.as_usize() - debruijn
.as_usize() - 1;
687 let universe
= self.universe_indices
[index
].unwrap_or_else(|| {
688 for i
in self.universe_indices
.iter_mut().take(index
+ 1) {
689 *i
= i
.or_else(|| Some(infcx
.create_next_universe()))
691 self.universe_indices
[index
].unwrap()
697 impl<'tcx
> TypeFolder
<'tcx
> for BoundVarReplacer
<'_
, 'tcx
> {
698 fn tcx
<'b
>(&'b
self) -> TyCtxt
<'tcx
> {
702 fn fold_binder
<T
: TypeFoldable
<'tcx
>>(
704 t
: ty
::Binder
<'tcx
, T
>,
705 ) -> ty
::Binder
<'tcx
, T
> {
706 self.current_index
.shift_in(1);
707 let t
= t
.super_fold_with(self);
708 self.current_index
.shift_out(1);
712 fn fold_region(&mut self, r
: ty
::Region
<'tcx
>) -> ty
::Region
<'tcx
> {
714 ty
::ReLateBound(debruijn
, _
)
715 if debruijn
.as_usize() + 1
716 > self.current_index
.as_usize() + self.universe_indices
.len() =>
718 bug
!("Bound vars outside of `self.universe_indices`");
720 ty
::ReLateBound(debruijn
, br
) if debruijn
>= self.current_index
=> {
721 let universe
= self.universe_for(debruijn
);
722 let p
= ty
::PlaceholderRegion { universe, name: br.kind }
;
723 self.mapped_regions
.insert(p
, br
);
724 self.infcx
.tcx
.mk_region(ty
::RePlaceholder(p
))
730 fn fold_ty(&mut self, t
: Ty
<'tcx
>) -> Ty
<'tcx
> {
732 ty
::Bound(debruijn
, _
)
733 if debruijn
.as_usize() + 1
734 > self.current_index
.as_usize() + self.universe_indices
.len() =>
736 bug
!("Bound vars outside of `self.universe_indices`");
738 ty
::Bound(debruijn
, bound_ty
) if debruijn
>= self.current_index
=> {
739 let universe
= self.universe_for(debruijn
);
740 let p
= ty
::PlaceholderType { universe, name: bound_ty.var }
;
741 self.mapped_types
.insert(p
, bound_ty
);
742 self.infcx
.tcx
.mk_ty(ty
::Placeholder(p
))
744 _
if t
.has_vars_bound_at_or_above(self.current_index
) => t
.super_fold_with(self),
749 fn fold_const(&mut self, ct
: ty
::Const
<'tcx
>) -> ty
::Const
<'tcx
> {
751 ty
::ConstKind
::Bound(debruijn
, _
)
752 if debruijn
.as_usize() + 1
753 > self.current_index
.as_usize() + self.universe_indices
.len() =>
755 bug
!("Bound vars outside of `self.universe_indices`");
757 ty
::ConstKind
::Bound(debruijn
, bound_const
) if debruijn
>= self.current_index
=> {
758 let universe
= self.universe_for(debruijn
);
759 let p
= ty
::PlaceholderConst
{
761 name
: ty
::BoundConst { var: bound_const, ty: ct.ty() }
,
763 self.mapped_consts
.insert(p
, bound_const
);
766 .mk_const(ty
::ConstS { kind: ty::ConstKind::Placeholder(p), ty: ct.ty() }
)
768 _
if ct
.has_vars_bound_at_or_above(self.current_index
) => ct
.super_fold_with(self),
774 // The inverse of `BoundVarReplacer`: replaces placeholders with the bound vars from which they came.
775 pub struct PlaceholderReplacer
<'me
, 'tcx
> {
776 infcx
: &'me InferCtxt
<'me
, 'tcx
>,
777 mapped_regions
: BTreeMap
<ty
::PlaceholderRegion
, ty
::BoundRegion
>,
778 mapped_types
: BTreeMap
<ty
::PlaceholderType
, ty
::BoundTy
>,
779 mapped_consts
: BTreeMap
<ty
::PlaceholderConst
<'tcx
>, ty
::BoundVar
>,
780 universe_indices
: &'me
[Option
<ty
::UniverseIndex
>],
781 current_index
: ty
::DebruijnIndex
,
784 impl<'me
, 'tcx
> PlaceholderReplacer
<'me
, 'tcx
> {
785 pub fn replace_placeholders
<T
: TypeFoldable
<'tcx
>>(
786 infcx
: &'me InferCtxt
<'me
, 'tcx
>,
787 mapped_regions
: BTreeMap
<ty
::PlaceholderRegion
, ty
::BoundRegion
>,
788 mapped_types
: BTreeMap
<ty
::PlaceholderType
, ty
::BoundTy
>,
789 mapped_consts
: BTreeMap
<ty
::PlaceholderConst
<'tcx
>, ty
::BoundVar
>,
790 universe_indices
: &'me
[Option
<ty
::UniverseIndex
>],
793 let mut replacer
= PlaceholderReplacer
{
799 current_index
: ty
::INNERMOST
,
801 value
.fold_with(&mut replacer
)
805 impl<'tcx
> TypeFolder
<'tcx
> for PlaceholderReplacer
<'_
, 'tcx
> {
806 fn tcx
<'b
>(&'b
self) -> TyCtxt
<'tcx
> {
810 fn fold_binder
<T
: TypeFoldable
<'tcx
>>(
812 t
: ty
::Binder
<'tcx
, T
>,
813 ) -> ty
::Binder
<'tcx
, T
> {
814 if !t
.has_placeholders() && !t
.has_infer_regions() {
817 self.current_index
.shift_in(1);
818 let t
= t
.super_fold_with(self);
819 self.current_index
.shift_out(1);
823 fn fold_region(&mut self, r0
: ty
::Region
<'tcx
>) -> ty
::Region
<'tcx
> {
829 .unwrap_region_constraints()
830 .opportunistic_resolve_region(self.infcx
.tcx
, r0
),
835 ty
::RePlaceholder(p
) => {
836 let replace_var
= self.mapped_regions
.get(&p
);
838 Some(replace_var
) => {
842 .position(|u
| matches
!(u
, Some(pu
) if *pu
== p
.universe
))
843 .unwrap_or_else(|| bug
!("Unexpected placeholder universe."));
844 let db
= ty
::DebruijnIndex
::from_usize(
845 self.universe_indices
.len() - index
+ self.current_index
.as_usize() - 1,
847 self.tcx().mk_region(ty
::ReLateBound(db
, *replace_var
))
855 debug
!(?r0
, ?r1
, ?r2
, "fold_region");
860 fn fold_ty(&mut self, ty
: Ty
<'tcx
>) -> Ty
<'tcx
> {
862 ty
::Placeholder(p
) => {
863 let replace_var
= self.mapped_types
.get(&p
);
865 Some(replace_var
) => {
869 .position(|u
| matches
!(u
, Some(pu
) if *pu
== p
.universe
))
870 .unwrap_or_else(|| bug
!("Unexpected placeholder universe."));
871 let db
= ty
::DebruijnIndex
::from_usize(
872 self.universe_indices
.len() - index
+ self.current_index
.as_usize() - 1,
874 self.tcx().mk_ty(ty
::Bound(db
, *replace_var
))
880 _
if ty
.has_placeholders() || ty
.has_infer_regions() => ty
.super_fold_with(self),
885 fn fold_const(&mut self, ct
: ty
::Const
<'tcx
>) -> ty
::Const
<'tcx
> {
886 if let ty
::ConstKind
::Placeholder(p
) = ct
.kind() {
887 let replace_var
= self.mapped_consts
.get(&p
);
889 Some(replace_var
) => {
893 .position(|u
| matches
!(u
, Some(pu
) if *pu
== p
.universe
))
894 .unwrap_or_else(|| bug
!("Unexpected placeholder universe."));
895 let db
= ty
::DebruijnIndex
::from_usize(
896 self.universe_indices
.len() - index
+ self.current_index
.as_usize() - 1,
898 self.tcx().mk_const(ty
::ConstS
{
899 kind
: ty
::ConstKind
::Bound(db
, *replace_var
),
906 ct
.super_fold_with(self)
911 /// The guts of `normalize`: normalize a specific projection like `<T
912 /// as Trait>::Item`. The result is always a type (and possibly
913 /// additional obligations). If ambiguity arises, which implies that
914 /// there are unresolved type variables in the projection, we will
915 /// substitute a fresh type variable `$X` and generate a new
916 /// obligation `<T as Trait>::Item == $X` for later.
917 pub fn normalize_projection_type
<'a
, 'b
, 'tcx
>(
918 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
919 param_env
: ty
::ParamEnv
<'tcx
>,
920 projection_ty
: ty
::ProjectionTy
<'tcx
>,
921 cause
: ObligationCause
<'tcx
>,
923 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
925 opt_normalize_projection_type(
935 .unwrap_or_else(move || {
936 // if we bottom out in ambiguity, create a type variable
937 // and a deferred predicate to resolve this when more type
938 // information is available.
942 .infer_projection(param_env
, projection_ty
, cause
, depth
+ 1, obligations
)
947 /// The guts of `normalize`: normalize a specific projection like `<T
948 /// as Trait>::Item`. The result is always a type (and possibly
949 /// additional obligations). Returns `None` in the case of ambiguity,
950 /// which indicates that there are unbound type variables.
952 /// This function used to return `Option<NormalizedTy<'tcx>>`, which contains a
953 /// `Ty<'tcx>` and an obligations vector. But that obligation vector was very
954 /// often immediately appended to another obligations vector. So now this
955 /// function takes an obligations vector and appends to it directly, which is
956 /// slightly uglier but avoids the need for an extra short-lived allocation.
957 #[instrument(level = "debug", skip(selcx, param_env, cause, obligations))]
958 fn opt_normalize_projection_type
<'a
, 'b
, 'tcx
>(
959 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
960 param_env
: ty
::ParamEnv
<'tcx
>,
961 projection_ty
: ty
::ProjectionTy
<'tcx
>,
962 cause
: ObligationCause
<'tcx
>,
964 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
965 ) -> Result
<Option
<Term
<'tcx
>>, InProgress
> {
966 let infcx
= selcx
.infcx();
967 // Don't use the projection cache in intercrate mode -
968 // the `infcx` may be re-used between intercrate in non-intercrate
969 // mode, which could lead to using incorrect cache results.
970 let use_cache
= !selcx
.is_intercrate();
972 let projection_ty
= infcx
.resolve_vars_if_possible(projection_ty
);
973 let cache_key
= ProjectionCacheKey
::new(projection_ty
);
975 // FIXME(#20304) For now, I am caching here, which is good, but it
976 // means we don't capture the type variables that are created in
977 // the case of ambiguity. Which means we may create a large stream
978 // of such variables. OTOH, if we move the caching up a level, we
979 // would not benefit from caching when proving `T: Trait<U=Foo>`
980 // bounds. It might be the case that we want two distinct caches,
981 // or else another kind of cache entry.
983 let cache_result
= if use_cache
{
984 infcx
.inner
.borrow_mut().projection_cache().try_start(cache_key
)
989 Ok(()) => debug
!("no cache"),
990 Err(ProjectionCacheEntry
::Ambiguous
) => {
991 // If we found ambiguity the last time, that means we will continue
992 // to do so until some type in the key changes (and we know it
993 // hasn't, because we just fully resolved it).
994 debug
!("found cache entry: ambiguous");
997 Err(ProjectionCacheEntry
::InProgress
) => {
998 // Under lazy normalization, this can arise when
999 // bootstrapping. That is, imagine an environment with a
1000 // where-clause like `A::B == u32`. Now, if we are asked
1001 // to normalize `A::B`, we will want to check the
1002 // where-clauses in scope. So we will try to unify `A::B`
1003 // with `A::B`, which can trigger a recursive
1006 debug
!("found cache entry: in-progress");
1008 // Cache that normalizing this projection resulted in a cycle. This
1009 // should ensure that, unless this happens within a snapshot that's
1010 // rolled back, fulfillment or evaluation will notice the cycle.
1013 infcx
.inner
.borrow_mut().projection_cache().recur(cache_key
);
1015 return Err(InProgress
);
1017 Err(ProjectionCacheEntry
::Recur
) => {
1018 debug
!("recur cache");
1019 return Err(InProgress
);
1021 Err(ProjectionCacheEntry
::NormalizedTy { ty, complete: _ }
) => {
1022 // This is the hottest path in this function.
1024 // If we find the value in the cache, then return it along
1025 // with the obligations that went along with it. Note
1026 // that, when using a fulfillment context, these
1027 // obligations could in principle be ignored: they have
1028 // already been registered when the cache entry was
1029 // created (and hence the new ones will quickly be
1030 // discarded as duplicated). But when doing trait
1031 // evaluation this is not the case, and dropping the trait
1032 // evaluations can causes ICEs (e.g., #43132).
1033 debug
!(?ty
, "found normalized ty");
1034 obligations
.extend(ty
.obligations
);
1035 return Ok(Some(ty
.value
));
1037 Err(ProjectionCacheEntry
::Error
) => {
1038 debug
!("opt_normalize_projection_type: found error");
1039 let result
= normalize_to_error(selcx
, param_env
, projection_ty
, cause
, depth
);
1040 obligations
.extend(result
.obligations
);
1041 return Ok(Some(result
.value
.into()));
1045 let obligation
= Obligation
::with_depth(cause
.clone(), depth
, param_env
, projection_ty
);
1047 match project(selcx
, &obligation
) {
1048 Ok(Projected
::Progress(Progress
{
1049 term
: projected_term
,
1050 obligations
: mut projected_obligations
,
1052 // if projection succeeded, then what we get out of this
1053 // is also non-normalized (consider: it was derived from
1054 // an impl, where-clause etc) and hence we must
1057 let projected_term
= selcx
.infcx().resolve_vars_if_possible(projected_term
);
1059 let mut result
= if projected_term
.has_projections() {
1060 let mut normalizer
= AssocTypeNormalizer
::new(
1065 &mut projected_obligations
,
1067 let normalized_ty
= normalizer
.fold(projected_term
);
1069 Normalized { value: normalized_ty, obligations: projected_obligations }
1071 Normalized { value: projected_term, obligations: projected_obligations }
1074 let mut deduped
: SsoHashSet
<_
> = Default
::default();
1075 result
.obligations
.drain_filter(|projected_obligation
| {
1076 if !deduped
.insert(projected_obligation
.clone()) {
1083 infcx
.inner
.borrow_mut().projection_cache().insert_term(cache_key
, result
.clone());
1085 obligations
.extend(result
.obligations
);
1086 Ok(Some(result
.value
))
1088 Ok(Projected
::NoProgress(projected_ty
)) => {
1089 let result
= Normalized { value: projected_ty, obligations: vec![] }
;
1091 infcx
.inner
.borrow_mut().projection_cache().insert_term(cache_key
, result
.clone());
1093 // No need to extend `obligations`.
1094 Ok(Some(result
.value
))
1096 Err(ProjectionError
::TooManyCandidates
) => {
1097 debug
!("opt_normalize_projection_type: too many candidates");
1099 infcx
.inner
.borrow_mut().projection_cache().ambiguous(cache_key
);
1103 Err(ProjectionError
::TraitSelectionError(_
)) => {
1104 debug
!("opt_normalize_projection_type: ERROR");
1105 // if we got an error processing the `T as Trait` part,
1106 // just return `ty::err` but add the obligation `T :
1107 // Trait`, which when processed will cause the error to be
1111 infcx
.inner
.borrow_mut().projection_cache().error(cache_key
);
1113 let result
= normalize_to_error(selcx
, param_env
, projection_ty
, cause
, depth
);
1114 obligations
.extend(result
.obligations
);
1115 Ok(Some(result
.value
.into()))
1120 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
1121 /// hold. In various error cases, we cannot generate a valid
1122 /// normalized projection. Therefore, we create an inference variable
1123 /// return an associated obligation that, when fulfilled, will lead to
1126 /// Note that we used to return `Error` here, but that was quite
1127 /// dubious -- the premise was that an error would *eventually* be
1128 /// reported, when the obligation was processed. But in general once
1129 /// you see an `Error` you are supposed to be able to assume that an
1130 /// error *has been* reported, so that you can take whatever heuristic
1131 /// paths you want to take. To make things worse, it was possible for
1132 /// cycles to arise, where you basically had a setup like `<MyType<$0>
1133 /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as
1134 /// Trait>::Foo> to `[type error]` would lead to an obligation of
1135 /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report
1136 /// an error for this obligation, but we legitimately should not,
1137 /// because it contains `[type error]`. Yuck! (See issue #29857 for
1138 /// one case where this arose.)
1139 fn normalize_to_error
<'a
, 'tcx
>(
1140 selcx
: &mut SelectionContext
<'a
, 'tcx
>,
1141 param_env
: ty
::ParamEnv
<'tcx
>,
1142 projection_ty
: ty
::ProjectionTy
<'tcx
>,
1143 cause
: ObligationCause
<'tcx
>,
1145 ) -> NormalizedTy
<'tcx
> {
1146 let trait_ref
= ty
::Binder
::dummy(projection_ty
.trait_ref(selcx
.tcx()));
1147 let trait_obligation
= Obligation
{
1149 recursion_depth
: depth
,
1151 predicate
: trait_ref
.without_const().to_predicate(selcx
.tcx()),
1153 let tcx
= selcx
.infcx().tcx
;
1154 let def_id
= projection_ty
.item_def_id
;
1155 let new_value
= selcx
.infcx().next_ty_var(TypeVariableOrigin
{
1156 kind
: TypeVariableOriginKind
::NormalizeProjectionType
,
1157 span
: tcx
.def_span(def_id
),
1159 Normalized { value: new_value, obligations: vec![trait_obligation] }
1162 enum Projected
<'tcx
> {
1163 Progress(Progress
<'tcx
>),
1164 NoProgress(ty
::Term
<'tcx
>),
1167 struct Progress
<'tcx
> {
1168 term
: ty
::Term
<'tcx
>,
1169 obligations
: Vec
<PredicateObligation
<'tcx
>>,
1172 impl<'tcx
> Progress
<'tcx
> {
1173 fn error(tcx
: TyCtxt
<'tcx
>) -> Self {
1174 Progress { term: tcx.ty_error().into(), obligations: vec![] }
1177 fn with_addl_obligations(mut self, mut obligations
: Vec
<PredicateObligation
<'tcx
>>) -> Self {
1178 self.obligations
.append(&mut obligations
);
1183 /// Computes the result of a projection type (if we can).
1186 /// - `obligation` must be fully normalized
1187 #[tracing::instrument(level = "info", skip(selcx))]
1188 fn project
<'cx
, 'tcx
>(
1189 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1190 obligation
: &ProjectionTyObligation
<'tcx
>,
1191 ) -> Result
<Projected
<'tcx
>, ProjectionError
<'tcx
>> {
1192 if !selcx
.tcx().recursion_limit().value_within_limit(obligation
.recursion_depth
) {
1193 // This should really be an immediate error, but some existing code
1194 // relies on being able to recover from this.
1195 return Err(ProjectionError
::TraitSelectionError(SelectionError
::Overflow(
1196 OverflowError
::Canonical
,
1200 if obligation
.predicate
.references_error() {
1201 return Ok(Projected
::Progress(Progress
::error(selcx
.tcx())));
1204 let mut candidates
= ProjectionCandidateSet
::None
;
1206 // Make sure that the following procedures are kept in order. ParamEnv
1207 // needs to be first because it has highest priority, and Select checks
1208 // the return value of push_candidate which assumes it's ran at last.
1209 assemble_candidates_from_param_env(selcx
, obligation
, &mut candidates
);
1211 assemble_candidates_from_trait_def(selcx
, obligation
, &mut candidates
);
1213 assemble_candidates_from_object_ty(selcx
, obligation
, &mut candidates
);
1215 if let ProjectionCandidateSet
::Single(ProjectionCandidate
::Object(_
)) = candidates
{
1216 // Avoid normalization cycle from selection (see
1217 // `assemble_candidates_from_object_ty`).
1218 // FIXME(lazy_normalization): Lazy normalization should save us from
1219 // having to special case this.
1221 assemble_candidates_from_impls(selcx
, obligation
, &mut candidates
);
1225 ProjectionCandidateSet
::Single(candidate
) => {
1226 Ok(Projected
::Progress(confirm_candidate(selcx
, obligation
, candidate
)))
1228 ProjectionCandidateSet
::None
=> Ok(Projected
::NoProgress(
1229 // FIXME(associated_const_generics): this may need to change in the future?
1230 // need to investigate whether or not this is fine.
1233 .mk_projection(obligation
.predicate
.item_def_id
, obligation
.predicate
.substs
)
1236 // Error occurred while trying to processing impls.
1237 ProjectionCandidateSet
::Error(e
) => Err(ProjectionError
::TraitSelectionError(e
)),
1238 // Inherent ambiguity that prevents us from even enumerating the
1240 ProjectionCandidateSet
::Ambiguous
=> Err(ProjectionError
::TooManyCandidates
),
1244 /// The first thing we have to do is scan through the parameter
1245 /// environment to see whether there are any projection predicates
1246 /// there that can answer this question.
1247 fn assemble_candidates_from_param_env
<'cx
, 'tcx
>(
1248 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1249 obligation
: &ProjectionTyObligation
<'tcx
>,
1250 candidate_set
: &mut ProjectionCandidateSet
<'tcx
>,
1252 assemble_candidates_from_predicates(
1256 ProjectionCandidate
::ParamEnv
,
1257 obligation
.param_env
.caller_bounds().iter(),
1262 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
1263 /// that the definition of `Foo` has some clues:
1265 /// ```ignore (illustrative)
1267 /// type FooT : Bar<BarT=i32>
1271 /// Here, for example, we could conclude that the result is `i32`.
1272 fn assemble_candidates_from_trait_def
<'cx
, 'tcx
>(
1273 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1274 obligation
: &ProjectionTyObligation
<'tcx
>,
1275 candidate_set
: &mut ProjectionCandidateSet
<'tcx
>,
1277 debug
!("assemble_candidates_from_trait_def(..)");
1279 let tcx
= selcx
.tcx();
1280 // Check whether the self-type is itself a projection.
1281 // If so, extract what we know from the trait and try to come up with a good answer.
1282 let bounds
= match *obligation
.predicate
.self_ty().kind() {
1283 ty
::Projection(ref data
) => tcx
.bound_item_bounds(data
.item_def_id
).subst(tcx
, data
.substs
),
1284 ty
::Opaque(def_id
, substs
) => tcx
.bound_item_bounds(def_id
).subst(tcx
, substs
),
1285 ty
::Infer(ty
::TyVar(_
)) => {
1286 // If the self-type is an inference variable, then it MAY wind up
1287 // being a projected type, so induce an ambiguity.
1288 candidate_set
.mark_ambiguous();
1294 assemble_candidates_from_predicates(
1298 ProjectionCandidate
::TraitDef
,
1304 /// In the case of a trait object like
1305 /// `<dyn Iterator<Item = ()> as Iterator>::Item` we can use the existential
1306 /// predicate in the trait object.
1308 /// We don't go through the select candidate for these bounds to avoid cycles:
1309 /// In the above case, `dyn Iterator<Item = ()>: Iterator` would create a
1310 /// nested obligation of `<dyn Iterator<Item = ()> as Iterator>::Item: Sized`,
1311 /// this then has to be normalized without having to prove
1312 /// `dyn Iterator<Item = ()>: Iterator` again.
1313 fn assemble_candidates_from_object_ty
<'cx
, 'tcx
>(
1314 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1315 obligation
: &ProjectionTyObligation
<'tcx
>,
1316 candidate_set
: &mut ProjectionCandidateSet
<'tcx
>,
1318 debug
!("assemble_candidates_from_object_ty(..)");
1320 let tcx
= selcx
.tcx();
1322 let self_ty
= obligation
.predicate
.self_ty();
1323 let object_ty
= selcx
.infcx().shallow_resolve(self_ty
);
1324 let data
= match object_ty
.kind() {
1325 ty
::Dynamic(data
, ..) => data
,
1326 ty
::Infer(ty
::TyVar(_
)) => {
1327 // If the self-type is an inference variable, then it MAY wind up
1328 // being an object type, so induce an ambiguity.
1329 candidate_set
.mark_ambiguous();
1334 let env_predicates
= data
1335 .projection_bounds()
1336 .filter(|bound
| bound
.item_def_id() == obligation
.predicate
.item_def_id
)
1337 .map(|p
| p
.with_self_ty(tcx
, object_ty
).to_predicate(tcx
));
1339 assemble_candidates_from_predicates(
1343 ProjectionCandidate
::Object
,
1349 #[tracing::instrument(
1351 skip(selcx
, candidate_set
, ctor
, env_predicates
, potentially_unnormalized_candidates
)
1353 fn assemble_candidates_from_predicates
<'cx
, 'tcx
>(
1354 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1355 obligation
: &ProjectionTyObligation
<'tcx
>,
1356 candidate_set
: &mut ProjectionCandidateSet
<'tcx
>,
1357 ctor
: fn(ty
::PolyProjectionPredicate
<'tcx
>) -> ProjectionCandidate
<'tcx
>,
1358 env_predicates
: impl Iterator
<Item
= ty
::Predicate
<'tcx
>>,
1359 potentially_unnormalized_candidates
: bool
,
1361 let infcx
= selcx
.infcx();
1362 for predicate
in env_predicates
{
1363 let bound_predicate
= predicate
.kind();
1364 if let ty
::PredicateKind
::Projection(data
) = predicate
.kind().skip_binder() {
1365 let data
= bound_predicate
.rebind(data
);
1366 if data
.projection_def_id() != obligation
.predicate
.item_def_id
{
1370 let is_match
= infcx
.probe(|_
| {
1371 selcx
.match_projection_projections(
1374 potentially_unnormalized_candidates
,
1379 ProjectionMatchesProjection
::Yes
=> {
1380 candidate_set
.push_candidate(ctor(data
));
1382 if potentially_unnormalized_candidates
1383 && !obligation
.predicate
.has_infer_types_or_consts()
1385 // HACK: Pick the first trait def candidate for a fully
1386 // inferred predicate. This is to allow duplicates that
1387 // differ only in normalization.
1391 ProjectionMatchesProjection
::Ambiguous
=> {
1392 candidate_set
.mark_ambiguous();
1394 ProjectionMatchesProjection
::No
=> {}
1400 #[tracing::instrument(level = "debug", skip(selcx, obligation, candidate_set))]
1401 fn assemble_candidates_from_impls
<'cx
, 'tcx
>(
1402 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1403 obligation
: &ProjectionTyObligation
<'tcx
>,
1404 candidate_set
: &mut ProjectionCandidateSet
<'tcx
>,
1406 // If we are resolving `<T as TraitRef<...>>::Item == Type`,
1407 // start out by selecting the predicate `T as TraitRef<...>`:
1408 let poly_trait_ref
= ty
::Binder
::dummy(obligation
.predicate
.trait_ref(selcx
.tcx()));
1409 let trait_obligation
= obligation
.with(poly_trait_ref
.to_poly_trait_predicate());
1410 let _
= selcx
.infcx().commit_if_ok(|_
| {
1411 let impl_source
= match selcx
.select(&trait_obligation
) {
1412 Ok(Some(impl_source
)) => impl_source
,
1414 candidate_set
.mark_ambiguous();
1418 debug
!(error
= ?e
, "selection error");
1419 candidate_set
.mark_error(e
);
1424 let eligible
= match &impl_source
{
1425 super::ImplSource
::Closure(_
)
1426 | super::ImplSource
::Generator(_
)
1427 | super::ImplSource
::FnPointer(_
)
1428 | super::ImplSource
::TraitAlias(_
) => true,
1429 super::ImplSource
::UserDefined(impl_data
) => {
1430 // We have to be careful when projecting out of an
1431 // impl because of specialization. If we are not in
1432 // codegen (i.e., projection mode is not "any"), and the
1433 // impl's type is declared as default, then we disable
1434 // projection (even if the trait ref is fully
1435 // monomorphic). In the case where trait ref is not
1436 // fully monomorphic (i.e., includes type parameters),
1437 // this is because those type parameters may
1438 // ultimately be bound to types from other crates that
1439 // may have specialized impls we can't see. In the
1440 // case where the trait ref IS fully monomorphic, this
1441 // is a policy decision that we made in the RFC in
1442 // order to preserve flexibility for the crate that
1443 // defined the specializable impl to specialize later
1444 // for existing types.
1446 // In either case, we handle this by not adding a
1447 // candidate for an impl if it contains a `default`
1450 // NOTE: This should be kept in sync with the similar code in
1451 // `rustc_ty_utils::instance::resolve_associated_item()`.
1453 assoc_def(selcx
, impl_data
.impl_def_id
, obligation
.predicate
.item_def_id
)
1454 .map_err(|ErrorGuaranteed { .. }
| ())?
;
1456 if node_item
.is_final() {
1457 // Non-specializable items are always projectable.
1460 // Only reveal a specializable default if we're past type-checking
1461 // and the obligation is monomorphic, otherwise passes such as
1462 // transmute checking and polymorphic MIR optimizations could
1463 // get a result which isn't correct for all monomorphizations.
1464 if obligation
.param_env
.reveal() == Reveal
::All
{
1465 // NOTE(eddyb) inference variables can resolve to parameters, so
1466 // assume `poly_trait_ref` isn't monomorphic, if it contains any.
1467 let poly_trait_ref
= selcx
.infcx().resolve_vars_if_possible(poly_trait_ref
);
1468 !poly_trait_ref
.still_further_specializable()
1471 assoc_ty
= ?selcx
.tcx().def_path_str(node_item
.item
.def_id
),
1472 ?obligation
.predicate
,
1473 "assemble_candidates_from_impls: not eligible due to default",
1479 super::ImplSource
::DiscriminantKind(..) => {
1480 // While `DiscriminantKind` is automatically implemented for every type,
1481 // the concrete discriminant may not be known yet.
1483 // Any type with multiple potential discriminant types is therefore not eligible.
1484 let self_ty
= selcx
.infcx().shallow_resolve(obligation
.predicate
.self_ty());
1486 match self_ty
.kind() {
1504 | ty
::GeneratorWitness(..)
1507 // Integers and floats always have `u8` as their discriminant.
1508 | ty
::Infer(ty
::InferTy
::IntVar(_
) | ty
::InferTy
::FloatVar(..)) => true,
1514 | ty
::Placeholder(..)
1516 | ty
::Error(_
) => false,
1519 super::ImplSource
::Pointee(..) => {
1520 // While `Pointee` is automatically implemented for every type,
1521 // the concrete metadata type may not be known yet.
1523 // Any type with multiple potential metadata types is therefore not eligible.
1524 let self_ty
= selcx
.infcx().shallow_resolve(obligation
.predicate
.self_ty());
1526 let tail
= selcx
.tcx().struct_tail_with_normalize(
1529 // We throw away any obligations we get from this, since we normalize
1530 // and confirm these obligations once again during confirmation
1531 normalize_with_depth(
1533 obligation
.param_env
,
1534 obligation
.cause
.clone(),
1535 obligation
.recursion_depth
+ 1,
1559 | ty
::GeneratorWitness(..)
1561 // Extern types have unit metadata, according to RFC 2850
1563 // If returned by `struct_tail_without_normalization` this is a unit struct
1564 // without any fields, or not a struct, and therefore is Sized.
1566 // If returned by `struct_tail_without_normalization` this is the empty tuple.
1568 // Integers and floats are always Sized, and so have unit type metadata.
1569 | ty
::Infer(ty
::InferTy
::IntVar(_
) | ty
::InferTy
::FloatVar(..)) => true,
1571 // type parameters, opaques, and unnormalized projections have pointer
1572 // metadata if they're known (e.g. by the param_env) to be sized
1573 ty
::Param(_
) | ty
::Projection(..) | ty
::Opaque(..)
1574 if selcx
.infcx().predicate_must_hold_modulo_regions(
1576 ty
::Binder
::dummy(ty
::TraitRef
::new(
1577 selcx
.tcx().require_lang_item(LangItem
::Sized
, None
),
1578 selcx
.tcx().mk_substs_trait(self_ty
, &[]),
1581 .to_predicate(selcx
.tcx()),
1588 // FIXME(compiler-errors): are Bound and Placeholder types ever known sized?
1590 | ty
::Projection(..)
1593 | ty
::Placeholder(..)
1596 if tail
.has_infer_types() {
1597 candidate_set
.mark_ambiguous();
1603 super::ImplSource
::Param(..) => {
1604 // This case tell us nothing about the value of an
1605 // associated type. Consider:
1608 // trait SomeTrait { type Foo; }
1609 // fn foo<T:SomeTrait>(...) { }
1612 // If the user writes `<T as SomeTrait>::Foo`, then the `T
1613 // : SomeTrait` binding does not help us decide what the
1614 // type `Foo` is (at least, not more specifically than
1615 // what we already knew).
1617 // But wait, you say! What about an example like this:
1620 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
1623 // Doesn't the `T : SomeTrait<Foo=usize>` predicate help
1624 // resolve `T::Foo`? And of course it does, but in fact
1625 // that single predicate is desugared into two predicates
1626 // in the compiler: a trait predicate (`T : SomeTrait`) and a
1627 // projection. And the projection where clause is handled
1628 // in `assemble_candidates_from_param_env`.
1631 super::ImplSource
::Object(_
) => {
1632 // Handled by the `Object` projection candidate. See
1633 // `assemble_candidates_from_object_ty` for an explanation of
1634 // why we special case object types.
1637 super::ImplSource
::AutoImpl(..)
1638 | super::ImplSource
::Builtin(..)
1639 | super::ImplSource
::TraitUpcasting(_
)
1640 | super::ImplSource
::ConstDestruct(_
) => {
1641 // These traits have no associated types.
1642 selcx
.tcx().sess
.delay_span_bug(
1643 obligation
.cause
.span
,
1644 &format
!("Cannot project an associated type from `{:?}`", impl_source
),
1651 if candidate_set
.push_candidate(ProjectionCandidate
::Select(impl_source
)) {
1662 fn confirm_candidate
<'cx
, 'tcx
>(
1663 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1664 obligation
: &ProjectionTyObligation
<'tcx
>,
1665 candidate
: ProjectionCandidate
<'tcx
>,
1666 ) -> Progress
<'tcx
> {
1667 debug
!(?obligation
, ?candidate
, "confirm_candidate");
1668 let mut progress
= match candidate
{
1669 ProjectionCandidate
::ParamEnv(poly_projection
)
1670 | ProjectionCandidate
::Object(poly_projection
) => {
1671 confirm_param_env_candidate(selcx
, obligation
, poly_projection
, false)
1674 ProjectionCandidate
::TraitDef(poly_projection
) => {
1675 confirm_param_env_candidate(selcx
, obligation
, poly_projection
, true)
1678 ProjectionCandidate
::Select(impl_source
) => {
1679 confirm_select_candidate(selcx
, obligation
, impl_source
)
1683 // When checking for cycle during evaluation, we compare predicates with
1684 // "syntactic" equality. Since normalization generally introduces a type
1685 // with new region variables, we need to resolve them to existing variables
1686 // when possible for this to work. See `auto-trait-projection-recursion.rs`
1687 // for a case where this matters.
1688 if progress
.term
.has_infer_regions() {
1690 progress
.term
.fold_with(&mut OpportunisticRegionResolver
::new(selcx
.infcx()));
1695 fn confirm_select_candidate
<'cx
, 'tcx
>(
1696 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1697 obligation
: &ProjectionTyObligation
<'tcx
>,
1698 impl_source
: Selection
<'tcx
>,
1699 ) -> Progress
<'tcx
> {
1701 super::ImplSource
::UserDefined(data
) => confirm_impl_candidate(selcx
, obligation
, data
),
1702 super::ImplSource
::Generator(data
) => confirm_generator_candidate(selcx
, obligation
, data
),
1703 super::ImplSource
::Closure(data
) => confirm_closure_candidate(selcx
, obligation
, data
),
1704 super::ImplSource
::FnPointer(data
) => confirm_fn_pointer_candidate(selcx
, obligation
, data
),
1705 super::ImplSource
::DiscriminantKind(data
) => {
1706 confirm_discriminant_kind_candidate(selcx
, obligation
, data
)
1708 super::ImplSource
::Pointee(data
) => confirm_pointee_candidate(selcx
, obligation
, data
),
1709 super::ImplSource
::Object(_
)
1710 | super::ImplSource
::AutoImpl(..)
1711 | super::ImplSource
::Param(..)
1712 | super::ImplSource
::Builtin(..)
1713 | super::ImplSource
::TraitUpcasting(_
)
1714 | super::ImplSource
::TraitAlias(..)
1715 | super::ImplSource
::ConstDestruct(_
) => {
1716 // we don't create Select candidates with this kind of resolution
1718 obligation
.cause
.span
,
1719 "Cannot project an associated type from `{:?}`",
1726 fn confirm_generator_candidate
<'cx
, 'tcx
>(
1727 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1728 obligation
: &ProjectionTyObligation
<'tcx
>,
1729 impl_source
: ImplSourceGeneratorData
<'tcx
, PredicateObligation
<'tcx
>>,
1730 ) -> Progress
<'tcx
> {
1731 let gen_sig
= impl_source
.substs
.as_generator().poly_sig();
1732 let Normalized { value: gen_sig, obligations }
= normalize_with_depth(
1734 obligation
.param_env
,
1735 obligation
.cause
.clone(),
1736 obligation
.recursion_depth
+ 1,
1740 debug
!(?obligation
, ?gen_sig
, ?obligations
, "confirm_generator_candidate");
1742 let tcx
= selcx
.tcx();
1744 let gen_def_id
= tcx
.require_lang_item(LangItem
::Generator
, None
);
1746 let predicate
= super::util
::generator_trait_ref_and_outputs(
1749 obligation
.predicate
.self_ty(),
1752 .map_bound(|(trait_ref
, yield_ty
, return_ty
)| {
1753 let name
= tcx
.associated_item(obligation
.predicate
.item_def_id
).name
;
1754 let ty
= if name
== sym
::Return
{
1756 } else if name
== sym
::Yield
{
1762 ty
::ProjectionPredicate
{
1763 projection_ty
: ty
::ProjectionTy
{
1764 substs
: trait_ref
.substs
,
1765 item_def_id
: obligation
.predicate
.item_def_id
,
1771 confirm_param_env_candidate(selcx
, obligation
, predicate
, false)
1772 .with_addl_obligations(impl_source
.nested
)
1773 .with_addl_obligations(obligations
)
1776 fn confirm_discriminant_kind_candidate
<'cx
, 'tcx
>(
1777 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1778 obligation
: &ProjectionTyObligation
<'tcx
>,
1779 _
: ImplSourceDiscriminantKindData
,
1780 ) -> Progress
<'tcx
> {
1781 let tcx
= selcx
.tcx();
1783 let self_ty
= selcx
.infcx().shallow_resolve(obligation
.predicate
.self_ty());
1784 // We get here from `poly_project_and_unify_type` which replaces bound vars
1785 // with placeholders
1786 debug_assert
!(!self_ty
.has_escaping_bound_vars());
1787 let substs
= tcx
.mk_substs([self_ty
.into()].iter());
1789 let discriminant_def_id
= tcx
.require_lang_item(LangItem
::Discriminant
, None
);
1791 let predicate
= ty
::ProjectionPredicate
{
1792 projection_ty
: ty
::ProjectionTy { substs, item_def_id: discriminant_def_id }
,
1793 term
: self_ty
.discriminant_ty(tcx
).into(),
1796 // We get here from `poly_project_and_unify_type` which replaces bound vars
1797 // with placeholders, so dummy is okay here.
1798 confirm_param_env_candidate(selcx
, obligation
, ty
::Binder
::dummy(predicate
), false)
1801 fn confirm_pointee_candidate
<'cx
, 'tcx
>(
1802 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1803 obligation
: &ProjectionTyObligation
<'tcx
>,
1804 _
: ImplSourcePointeeData
,
1805 ) -> Progress
<'tcx
> {
1806 let tcx
= selcx
.tcx();
1807 let self_ty
= selcx
.infcx().shallow_resolve(obligation
.predicate
.self_ty());
1809 let mut obligations
= vec
![];
1810 let (metadata_ty
, check_is_sized
) = self_ty
.ptr_metadata_ty(tcx
, |ty
| {
1811 normalize_with_depth_to(
1813 obligation
.param_env
,
1814 obligation
.cause
.clone(),
1815 obligation
.recursion_depth
+ 1,
1821 let sized_predicate
= ty
::Binder
::dummy(ty
::TraitRef
::new(
1822 tcx
.require_lang_item(LangItem
::Sized
, None
),
1823 tcx
.mk_substs_trait(self_ty
, &[]),
1827 obligations
.push(Obligation
::new(
1828 obligation
.cause
.clone(),
1829 obligation
.param_env
,
1834 let substs
= tcx
.mk_substs([self_ty
.into()].iter());
1835 let metadata_def_id
= tcx
.require_lang_item(LangItem
::Metadata
, None
);
1837 let predicate
= ty
::ProjectionPredicate
{
1838 projection_ty
: ty
::ProjectionTy { substs, item_def_id: metadata_def_id }
,
1839 term
: metadata_ty
.into(),
1842 confirm_param_env_candidate(selcx
, obligation
, ty
::Binder
::dummy(predicate
), false)
1843 .with_addl_obligations(obligations
)
1846 fn confirm_fn_pointer_candidate
<'cx
, 'tcx
>(
1847 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1848 obligation
: &ProjectionTyObligation
<'tcx
>,
1849 fn_pointer_impl_source
: ImplSourceFnPointerData
<'tcx
, PredicateObligation
<'tcx
>>,
1850 ) -> Progress
<'tcx
> {
1851 let fn_type
= selcx
.infcx().shallow_resolve(fn_pointer_impl_source
.fn_ty
);
1852 let sig
= fn_type
.fn_sig(selcx
.tcx());
1853 let Normalized { value: sig, obligations }
= normalize_with_depth(
1855 obligation
.param_env
,
1856 obligation
.cause
.clone(),
1857 obligation
.recursion_depth
+ 1,
1861 confirm_callable_candidate(selcx
, obligation
, sig
, util
::TupleArgumentsFlag
::Yes
)
1862 .with_addl_obligations(fn_pointer_impl_source
.nested
)
1863 .with_addl_obligations(obligations
)
1866 fn confirm_closure_candidate
<'cx
, 'tcx
>(
1867 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1868 obligation
: &ProjectionTyObligation
<'tcx
>,
1869 impl_source
: ImplSourceClosureData
<'tcx
, PredicateObligation
<'tcx
>>,
1870 ) -> Progress
<'tcx
> {
1871 let closure_sig
= impl_source
.substs
.as_closure().sig();
1872 let Normalized { value: closure_sig, obligations }
= normalize_with_depth(
1874 obligation
.param_env
,
1875 obligation
.cause
.clone(),
1876 obligation
.recursion_depth
+ 1,
1880 debug
!(?obligation
, ?closure_sig
, ?obligations
, "confirm_closure_candidate");
1882 confirm_callable_candidate(selcx
, obligation
, closure_sig
, util
::TupleArgumentsFlag
::No
)
1883 .with_addl_obligations(impl_source
.nested
)
1884 .with_addl_obligations(obligations
)
1887 fn confirm_callable_candidate
<'cx
, 'tcx
>(
1888 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1889 obligation
: &ProjectionTyObligation
<'tcx
>,
1890 fn_sig
: ty
::PolyFnSig
<'tcx
>,
1891 flag
: util
::TupleArgumentsFlag
,
1892 ) -> Progress
<'tcx
> {
1893 let tcx
= selcx
.tcx();
1895 debug
!(?obligation
, ?fn_sig
, "confirm_callable_candidate");
1897 let fn_once_def_id
= tcx
.require_lang_item(LangItem
::FnOnce
, None
);
1898 let fn_once_output_def_id
= tcx
.require_lang_item(LangItem
::FnOnceOutput
, None
);
1900 let predicate
= super::util
::closure_trait_ref_and_return_type(
1903 obligation
.predicate
.self_ty(),
1907 .map_bound(|(trait_ref
, ret_type
)| ty
::ProjectionPredicate
{
1908 projection_ty
: ty
::ProjectionTy
{
1909 substs
: trait_ref
.substs
,
1910 item_def_id
: fn_once_output_def_id
,
1912 term
: ret_type
.into(),
1915 confirm_param_env_candidate(selcx
, obligation
, predicate
, true)
1918 fn confirm_param_env_candidate
<'cx
, 'tcx
>(
1919 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1920 obligation
: &ProjectionTyObligation
<'tcx
>,
1921 poly_cache_entry
: ty
::PolyProjectionPredicate
<'tcx
>,
1922 potentially_unnormalized_candidate
: bool
,
1923 ) -> Progress
<'tcx
> {
1924 let infcx
= selcx
.infcx();
1925 let cause
= &obligation
.cause
;
1926 let param_env
= obligation
.param_env
;
1928 let cache_entry
= infcx
.replace_bound_vars_with_fresh_vars(
1930 LateBoundRegionConversionTime
::HigherRankedType
,
1934 let cache_projection
= cache_entry
.projection_ty
;
1935 let mut nested_obligations
= Vec
::new();
1936 let obligation_projection
= obligation
.predicate
;
1937 let obligation_projection
= ensure_sufficient_stack(|| {
1938 normalize_with_depth_to(
1940 obligation
.param_env
,
1941 obligation
.cause
.clone(),
1942 obligation
.recursion_depth
+ 1,
1943 obligation_projection
,
1944 &mut nested_obligations
,
1947 let cache_projection
= if potentially_unnormalized_candidate
{
1948 ensure_sufficient_stack(|| {
1949 normalize_with_depth_to(
1951 obligation
.param_env
,
1952 obligation
.cause
.clone(),
1953 obligation
.recursion_depth
+ 1,
1955 &mut nested_obligations
,
1962 debug
!(?cache_projection
, ?obligation_projection
);
1964 match infcx
.at(cause
, param_env
).eq(cache_projection
, obligation_projection
) {
1965 Ok(InferOk { value: _, obligations }
) => {
1966 nested_obligations
.extend(obligations
);
1967 assoc_ty_own_obligations(selcx
, obligation
, &mut nested_obligations
);
1968 // FIXME(associated_const_equality): Handle consts here as well? Maybe this progress type should just take
1970 Progress { term: cache_entry.term, obligations: nested_obligations }
1974 "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}",
1975 obligation
, poly_cache_entry
, e
,
1977 debug
!("confirm_param_env_candidate: {}", msg
);
1978 let err
= infcx
.tcx
.ty_error_with_message(obligation
.cause
.span
, &msg
);
1979 Progress { term: err.into(), obligations: vec![] }
1984 fn confirm_impl_candidate
<'cx
, 'tcx
>(
1985 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1986 obligation
: &ProjectionTyObligation
<'tcx
>,
1987 impl_impl_source
: ImplSourceUserDefinedData
<'tcx
, PredicateObligation
<'tcx
>>,
1988 ) -> Progress
<'tcx
> {
1989 let tcx
= selcx
.tcx();
1991 let ImplSourceUserDefinedData { impl_def_id, substs, mut nested }
= impl_impl_source
;
1992 let assoc_item_id
= obligation
.predicate
.item_def_id
;
1993 let trait_def_id
= tcx
.trait_id_of_impl(impl_def_id
).unwrap();
1995 let param_env
= obligation
.param_env
;
1996 let Ok(assoc_ty
) = assoc_def(selcx
, impl_def_id
, assoc_item_id
) else {
1997 return Progress { term: tcx.ty_error().into(), obligations: nested }
;
2000 if !assoc_ty
.item
.defaultness
.has_value() {
2001 // This means that the impl is missing a definition for the
2002 // associated type. This error will be reported by the type
2003 // checker method `check_impl_items_against_trait`, so here we
2004 // just return Error.
2006 "confirm_impl_candidate: no associated type {:?} for {:?}",
2007 assoc_ty
.item
.name
, obligation
.predicate
2009 return Progress { term: tcx.ty_error().into(), obligations: nested }
;
2011 // If we're trying to normalize `<Vec<u32> as X>::A<S>` using
2012 //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then:
2014 // * `obligation.predicate.substs` is `[Vec<u32>, S]`
2015 // * `substs` is `[u32]`
2016 // * `substs` ends up as `[u32, S]`
2017 let substs
= obligation
.predicate
.substs
.rebase_onto(tcx
, trait_def_id
, substs
);
2019 translate_substs(selcx
.infcx(), param_env
, impl_def_id
, substs
, assoc_ty
.defining_node
);
2020 let ty
= tcx
.type_of(assoc_ty
.item
.def_id
);
2021 let is_const
= matches
!(tcx
.def_kind(assoc_ty
.item
.def_id
), DefKind
::AssocConst
);
2022 let term
: ty
::Term
<'tcx
> = if is_const
{
2023 let identity_substs
=
2024 crate::traits
::InternalSubsts
::identity_for_item(tcx
, assoc_ty
.item
.def_id
);
2025 let did
= ty
::WithOptConstParam
::unknown(assoc_ty
.item
.def_id
);
2026 let kind
= ty
::ConstKind
::Unevaluated(ty
::Unevaluated
::new(did
, identity_substs
));
2027 tcx
.mk_const(ty
::ConstS { ty, kind }
).into()
2031 if substs
.len() != tcx
.generics_of(assoc_ty
.item
.def_id
).count() {
2032 let err
= tcx
.ty_error_with_message(
2033 obligation
.cause
.span
,
2034 "impl item and trait item have different parameter counts",
2036 Progress { term: err.into(), obligations: nested }
2038 assoc_ty_own_obligations(selcx
, obligation
, &mut nested
);
2039 Progress { term: EarlyBinder(term).subst(tcx, substs), obligations: nested }
2043 // Get obligations corresponding to the predicates from the where-clause of the
2044 // associated type itself.
2045 // Note: `feature(generic_associated_types)` is required to write such
2046 // predicates, even for non-generic associated types.
2047 fn assoc_ty_own_obligations
<'cx
, 'tcx
>(
2048 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
2049 obligation
: &ProjectionTyObligation
<'tcx
>,
2050 nested
: &mut Vec
<PredicateObligation
<'tcx
>>,
2052 let tcx
= selcx
.tcx();
2053 for predicate
in tcx
2054 .predicates_of(obligation
.predicate
.item_def_id
)
2055 .instantiate_own(tcx
, obligation
.predicate
.substs
)
2058 let normalized
= normalize_with_depth_to(
2060 obligation
.param_env
,
2061 obligation
.cause
.clone(),
2062 obligation
.recursion_depth
+ 1,
2066 nested
.push(Obligation
::with_depth(
2067 obligation
.cause
.clone(),
2068 obligation
.recursion_depth
+ 1,
2069 obligation
.param_env
,
2075 /// Locate the definition of an associated type in the specialization hierarchy,
2076 /// starting from the given impl.
2078 /// Based on the "projection mode", this lookup may in fact only examine the
2079 /// topmost impl. See the comments for `Reveal` for more details.
2081 selcx
: &SelectionContext
<'_
, '_
>,
2083 assoc_def_id
: DefId
,
2084 ) -> Result
<specialization_graph
::LeafDef
, ErrorGuaranteed
> {
2085 let tcx
= selcx
.tcx();
2086 let trait_def_id
= tcx
.impl_trait_ref(impl_def_id
).unwrap().def_id
;
2087 let trait_def
= tcx
.trait_def(trait_def_id
);
2089 // This function may be called while we are still building the
2090 // specialization graph that is queried below (via TraitDef::ancestors()),
2091 // so, in order to avoid unnecessary infinite recursion, we manually look
2092 // for the associated item at the given impl.
2093 // If there is no such item in that impl, this function will fail with a
2094 // cycle error if the specialization graph is currently being built.
2095 if let Some(&impl_item_id
) = tcx
.impl_item_implementor_ids(impl_def_id
).get(&assoc_def_id
) {
2096 let item
= tcx
.associated_item(impl_item_id
);
2097 let impl_node
= specialization_graph
::Node
::Impl(impl_def_id
);
2098 return Ok(specialization_graph
::LeafDef
{
2100 defining_node
: impl_node
,
2101 finalizing_node
: if item
.defaultness
.is_default() { None }
else { Some(impl_node) }
,
2105 let ancestors
= trait_def
.ancestors(tcx
, impl_def_id
)?
;
2106 if let Some(assoc_item
) = ancestors
.leaf_def(tcx
, assoc_def_id
) {
2109 // This is saying that neither the trait nor
2110 // the impl contain a definition for this
2111 // associated type. Normally this situation
2112 // could only arise through a compiler bug --
2113 // if the user wrote a bad item name, it
2114 // should have failed in astconv.
2116 "No associated type `{}` for {}",
2117 tcx
.item_name(assoc_def_id
),
2118 tcx
.def_path_str(impl_def_id
)
2123 pub(crate) trait ProjectionCacheKeyExt
<'cx
, 'tcx
>: Sized
{
2124 fn from_poly_projection_predicate(
2125 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
2126 predicate
: ty
::PolyProjectionPredicate
<'tcx
>,
2130 impl<'cx
, 'tcx
> ProjectionCacheKeyExt
<'cx
, 'tcx
> for ProjectionCacheKey
<'tcx
> {
2131 fn from_poly_projection_predicate(
2132 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
2133 predicate
: ty
::PolyProjectionPredicate
<'tcx
>,
2135 let infcx
= selcx
.infcx();
2136 // We don't do cross-snapshot caching of obligations with escaping regions,
2137 // so there's no cache key to use
2138 predicate
.no_bound_vars().map(|predicate
| {
2139 ProjectionCacheKey
::new(
2140 // We don't attempt to match up with a specific type-variable state
2141 // from a specific call to `opt_normalize_projection_type` - if
2142 // there's no precise match, the original cache entry is "stranded"
2144 infcx
.resolve_vars_if_possible(predicate
.projection_ty
),