rustc_next_trait_solver/solve/assembly/
mod.rs

Help
1//! Code shared by trait and projection goals for candidate assembly.
2
3pub(super) mod structural_traits;
4
5use derive_where::derive_where;
6use rustc_type_ir::fold::TypeFoldable;
7use rustc_type_ir::inherent::*;
8use rustc_type_ir::lang_items::TraitSolverLangItem;
9use rustc_type_ir::visit::TypeVisitableExt as _;
10use rustc_type_ir::{self as ty, Interner, TypingMode, Upcast as _, elaborate};
11use tracing::{debug, instrument};
12
13use super::trait_goals::TraitGoalProvenVia;
14use crate::delegate::SolverDelegate;
15use crate::solve::inspect::ProbeKind;
16use crate::solve::{
17    BuiltinImplSource, CandidateSource, CanonicalResponse, Certainty, EvalCtxt, Goal, GoalSource,
18    MaybeCause, NoSolution, QueryResult,
19};
20
21enum AliasBoundKind {
22    SelfBounds,
23    NonSelfBounds,
24}
25
26/// A candidate is a possible way to prove a goal.
27///
28/// It consists of both the `source`, which describes how that goal would be proven,
29/// and the `result` when using the given `source`.
30#[derive_where(Clone, Debug; I: Interner)]
31pub(super) struct Candidate<I: Interner> {
32    pub(super) source: CandidateSource<I>,
33    pub(super) result: CanonicalResponse<I>,
34}
35
36/// Methods used to assemble candidates for either trait or projection goals.
37pub(super) trait GoalKind<D, I = <D as SolverDelegate>::Interner>:
38    TypeFoldable<I> + Copy + Eq + std::fmt::Display
39where
40    D: SolverDelegate<Interner = I>,
41    I: Interner,
42{
43    fn self_ty(self) -> I::Ty;
44
45    fn trait_ref(self, cx: I) -> ty::TraitRef<I>;
46
47    fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self;
48
49    fn trait_def_id(self, cx: I) -> I::DefId;
50
51    /// Try equating an assumption predicate against a goal's predicate. If it
52    /// holds, then execute the `then` callback, which should do any additional
53    /// work, then produce a response (typically by executing
54    /// [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]).
55    fn probe_and_match_goal_against_assumption(
56        ecx: &mut EvalCtxt<'_, D>,
57        source: CandidateSource<I>,
58        goal: Goal<I, Self>,
59        assumption: I::Clause,
60        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
61    ) -> Result<Candidate<I>, NoSolution>;
62
63    /// Consider a clause, which consists of a "assumption" and some "requirements",
64    /// to satisfy a goal. If the requirements hold, then attempt to satisfy our
65    /// goal by equating it with the assumption.
66    fn probe_and_consider_implied_clause(
67        ecx: &mut EvalCtxt<'_, D>,
68        parent_source: CandidateSource<I>,
69        goal: Goal<I, Self>,
70        assumption: I::Clause,
71        requirements: impl IntoIterator<Item = (GoalSource, Goal<I, I::Predicate>)>,
72    ) -> Result<Candidate<I>, NoSolution> {
73        Self::probe_and_match_goal_against_assumption(ecx, parent_source, goal, assumption, |ecx| {
74            for (nested_source, goal) in requirements {
75                ecx.add_goal(nested_source, goal);
76            }
77            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
78        })
79    }
80
81    /// Consider a clause specifically for a `dyn Trait` self type. This requires
82    /// additionally checking all of the supertraits and object bounds to hold,
83    /// since they're not implied by the well-formedness of the object type.
84    fn probe_and_consider_object_bound_candidate(
85        ecx: &mut EvalCtxt<'_, D>,
86        source: CandidateSource<I>,
87        goal: Goal<I, Self>,
88        assumption: I::Clause,
89    ) -> Result<Candidate<I>, NoSolution> {
90        Self::probe_and_match_goal_against_assumption(ecx, source, goal, assumption, |ecx| {
91            let cx = ecx.cx();
92            let ty::Dynamic(bounds, _, _) = goal.predicate.self_ty().kind() else {
93                panic!("expected object type in `probe_and_consider_object_bound_candidate`");
94            };
95            ecx.add_goals(
96                GoalSource::ImplWhereBound,
97                structural_traits::predicates_for_object_candidate(
98                    ecx,
99                    goal.param_env,
100                    goal.predicate.trait_ref(cx),
101                    bounds,
102                ),
103            );
104            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
105        })
106    }
107
108    /// Assemble additional assumptions for an alias that are not included
109    /// in the item bounds of the alias. For now, this is limited to the
110    /// `explicit_implied_const_bounds` for an associated type.
111    fn consider_additional_alias_assumptions(
112        ecx: &mut EvalCtxt<'_, D>,
113        goal: Goal<I, Self>,
114        alias_ty: ty::AliasTy<I>,
115    ) -> Vec<Candidate<I>>;
116
117    fn consider_impl_candidate(
118        ecx: &mut EvalCtxt<'_, D>,
119        goal: Goal<I, Self>,
120        impl_def_id: I::DefId,
121    ) -> Result<Candidate<I>, NoSolution>;
122
123    /// If the predicate contained an error, we want to avoid emitting unnecessary trait
124    /// errors but still want to emit errors for other trait goals. We have some special
125    /// handling for this case.
126    ///
127    /// Trait goals always hold while projection goals never do. This is a bit arbitrary
128    /// but prevents incorrect normalization while hiding any trait errors.
129    fn consider_error_guaranteed_candidate(
130        ecx: &mut EvalCtxt<'_, D>,
131        guar: I::ErrorGuaranteed,
132    ) -> Result<Candidate<I>, NoSolution>;
133
134    /// A type implements an `auto trait` if its components do as well.
135    ///
136    /// These components are given by built-in rules from
137    /// [`structural_traits::instantiate_constituent_tys_for_auto_trait`].
138    fn consider_auto_trait_candidate(
139        ecx: &mut EvalCtxt<'_, D>,
140        goal: Goal<I, Self>,
141    ) -> Result<Candidate<I>, NoSolution>;
142
143    /// A trait alias holds if the RHS traits and `where` clauses hold.
144    fn consider_trait_alias_candidate(
145        ecx: &mut EvalCtxt<'_, D>,
146        goal: Goal<I, Self>,
147    ) -> Result<Candidate<I>, NoSolution>;
148
149    /// A type is `Sized` if its tail component is `Sized`.
150    ///
151    /// These components are given by built-in rules from
152    /// [`structural_traits::instantiate_constituent_tys_for_sized_trait`].
153    fn consider_builtin_sized_candidate(
154        ecx: &mut EvalCtxt<'_, D>,
155        goal: Goal<I, Self>,
156    ) -> Result<Candidate<I>, NoSolution>;
157
158    /// A type is `Copy` or `Clone` if its components are `Copy` or `Clone`.
159    ///
160    /// These components are given by built-in rules from
161    /// [`structural_traits::instantiate_constituent_tys_for_copy_clone_trait`].
162    fn consider_builtin_copy_clone_candidate(
163        ecx: &mut EvalCtxt<'_, D>,
164        goal: Goal<I, Self>,
165    ) -> Result<Candidate<I>, NoSolution>;
166
167    /// A type is a `FnPtr` if it is of `FnPtr` type.
168    fn consider_builtin_fn_ptr_trait_candidate(
169        ecx: &mut EvalCtxt<'_, D>,
170        goal: Goal<I, Self>,
171    ) -> Result<Candidate<I>, NoSolution>;
172
173    /// A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
174    /// family of traits where `A` is given by the signature of the type.
175    fn consider_builtin_fn_trait_candidates(
176        ecx: &mut EvalCtxt<'_, D>,
177        goal: Goal<I, Self>,
178        kind: ty::ClosureKind,
179    ) -> Result<Candidate<I>, NoSolution>;
180
181    /// An async closure is known to implement the `AsyncFn<A>` family of traits
182    /// where `A` is given by the signature of the type.
183    fn consider_builtin_async_fn_trait_candidates(
184        ecx: &mut EvalCtxt<'_, D>,
185        goal: Goal<I, Self>,
186        kind: ty::ClosureKind,
187    ) -> Result<Candidate<I>, NoSolution>;
188
189    /// Compute the built-in logic of the `AsyncFnKindHelper` helper trait, which
190    /// is used internally to delay computation for async closures until after
191    /// upvar analysis is performed in HIR typeck.
192    fn consider_builtin_async_fn_kind_helper_candidate(
193        ecx: &mut EvalCtxt<'_, D>,
194        goal: Goal<I, Self>,
195    ) -> Result<Candidate<I>, NoSolution>;
196
197    /// `Tuple` is implemented if the `Self` type is a tuple.
198    fn consider_builtin_tuple_candidate(
199        ecx: &mut EvalCtxt<'_, D>,
200        goal: Goal<I, Self>,
201    ) -> Result<Candidate<I>, NoSolution>;
202
203    /// `Pointee` is always implemented.
204    ///
205    /// See the projection implementation for the `Metadata` types for all of
206    /// the built-in types. For structs, the metadata type is given by the struct
207    /// tail.
208    fn consider_builtin_pointee_candidate(
209        ecx: &mut EvalCtxt<'_, D>,
210        goal: Goal<I, Self>,
211    ) -> Result<Candidate<I>, NoSolution>;
212
213    /// A coroutine (that comes from an `async` desugaring) is known to implement
214    /// `Future<Output = O>`, where `O` is given by the coroutine's return type
215    /// that was computed during type-checking.
216    fn consider_builtin_future_candidate(
217        ecx: &mut EvalCtxt<'_, D>,
218        goal: Goal<I, Self>,
219    ) -> Result<Candidate<I>, NoSolution>;
220
221    /// A coroutine (that comes from a `gen` desugaring) is known to implement
222    /// `Iterator<Item = O>`, where `O` is given by the generator's yield type
223    /// that was computed during type-checking.
224    fn consider_builtin_iterator_candidate(
225        ecx: &mut EvalCtxt<'_, D>,
226        goal: Goal<I, Self>,
227    ) -> Result<Candidate<I>, NoSolution>;
228
229    /// A coroutine (that comes from a `gen` desugaring) is known to implement
230    /// `FusedIterator`
231    fn consider_builtin_fused_iterator_candidate(
232        ecx: &mut EvalCtxt<'_, D>,
233        goal: Goal<I, Self>,
234    ) -> Result<Candidate<I>, NoSolution>;
235
236    fn consider_builtin_async_iterator_candidate(
237        ecx: &mut EvalCtxt<'_, D>,
238        goal: Goal<I, Self>,
239    ) -> Result<Candidate<I>, NoSolution>;
240
241    /// A coroutine (that doesn't come from an `async` or `gen` desugaring) is known to
242    /// implement `Coroutine<R, Yield = Y, Return = O>`, given the resume, yield,
243    /// and return types of the coroutine computed during type-checking.
244    fn consider_builtin_coroutine_candidate(
245        ecx: &mut EvalCtxt<'_, D>,
246        goal: Goal<I, Self>,
247    ) -> Result<Candidate<I>, NoSolution>;
248
249    fn consider_builtin_discriminant_kind_candidate(
250        ecx: &mut EvalCtxt<'_, D>,
251        goal: Goal<I, Self>,
252    ) -> Result<Candidate<I>, NoSolution>;
253
254    fn consider_builtin_async_destruct_candidate(
255        ecx: &mut EvalCtxt<'_, D>,
256        goal: Goal<I, Self>,
257    ) -> Result<Candidate<I>, NoSolution>;
258
259    fn consider_builtin_destruct_candidate(
260        ecx: &mut EvalCtxt<'_, D>,
261        goal: Goal<I, Self>,
262    ) -> Result<Candidate<I>, NoSolution>;
263
264    fn consider_builtin_transmute_candidate(
265        ecx: &mut EvalCtxt<'_, D>,
266        goal: Goal<I, Self>,
267    ) -> Result<Candidate<I>, NoSolution>;
268
269    fn consider_builtin_bikeshed_guaranteed_no_drop_candidate(
270        ecx: &mut EvalCtxt<'_, D>,
271        goal: Goal<I, Self>,
272    ) -> Result<Candidate<I>, NoSolution>;
273
274    /// Consider (possibly several) candidates to upcast or unsize a type to another
275    /// type, excluding the coercion of a sized type into a `dyn Trait`.
276    ///
277    /// We return the `BuiltinImplSource` for each candidate as it is needed
278    /// for unsize coercion in hir typeck and because it is difficult to
279    /// otherwise recompute this for codegen. This is a bit of a mess but the
280    /// easiest way to maintain the existing behavior for now.
281    fn consider_structural_builtin_unsize_candidates(
282        ecx: &mut EvalCtxt<'_, D>,
283        goal: Goal<I, Self>,
284    ) -> Vec<Candidate<I>>;
285}
286
287impl<D, I> EvalCtxt<'_, D>
288where
289    D: SolverDelegate<Interner = I>,
290    I: Interner,
291{
292    pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<D>>(
293        &mut self,
294        goal: Goal<I, G>,
295    ) -> Vec<Candidate<I>> {
296        let Ok(normalized_self_ty) =
297            self.structurally_normalize_ty(goal.param_env, goal.predicate.self_ty())
298        else {
299            return vec![];
300        };
301
302        if normalized_self_ty.is_ty_var() {
303            debug!("self type has been normalized to infer");
304            return self.forced_ambiguity(MaybeCause::Ambiguity).into_iter().collect();
305        }
306
307        let goal: Goal<I, G> =
308            goal.with(self.cx(), goal.predicate.with_self_ty(self.cx(), normalized_self_ty));
309        // Vars that show up in the rest of the goal substs may have been constrained by
310        // normalizing the self type as well, since type variables are not uniquified.
311        let goal = self.resolve_vars_if_possible(goal);
312
313        let mut candidates = vec![];
314
315        if let TypingMode::Coherence = self.typing_mode() {
316            if let Ok(candidate) = self.consider_coherence_unknowable_candidate(goal) {
317                return vec![candidate];
318            }
319        }
320
321        self.assemble_impl_candidates(goal, &mut candidates);
322
323        self.assemble_builtin_impl_candidates(goal, &mut candidates);
324
325        self.assemble_alias_bound_candidates(goal, &mut candidates);
326
327        self.assemble_object_bound_candidates(goal, &mut candidates);
328
329        self.assemble_param_env_candidates(goal, &mut candidates);
330
331        candidates
332    }
333
334    pub(super) fn forced_ambiguity(
335        &mut self,
336        cause: MaybeCause,
337    ) -> Result<Candidate<I>, NoSolution> {
338        // This may fail if `try_evaluate_added_goals` overflows because it
339        // fails to reach a fixpoint but ends up getting an error after
340        // running for some additional step.
341        //
342        // cc trait-system-refactor-initiative#105
343        let source = CandidateSource::BuiltinImpl(BuiltinImplSource::Misc);
344        let certainty = Certainty::Maybe(cause);
345        self.probe_trait_candidate(source)
346            .enter(|this| this.evaluate_added_goals_and_make_canonical_response(certainty))
347    }
348
349    #[instrument(level = "trace", skip_all)]
350    fn assemble_impl_candidates<G: GoalKind<D>>(
351        &mut self,
352        goal: Goal<I, G>,
353        candidates: &mut Vec<Candidate<I>>,
354    ) {
355        let cx = self.cx();
356        cx.for_each_relevant_impl(
357            goal.predicate.trait_def_id(cx),
358            goal.predicate.self_ty(),
359            |impl_def_id| {
360                // For every `default impl`, there's always a non-default `impl`
361                // that will *also* apply. There's no reason to register a candidate
362                // for this impl, since it is *not* proof that the trait goal holds.
363                if cx.impl_is_default(impl_def_id) {
364                    return;
365                }
366
367                match G::consider_impl_candidate(self, goal, impl_def_id) {
368                    Ok(candidate) => candidates.push(candidate),
369                    Err(NoSolution) => (),
370                }
371            },
372        );
373    }
374
375    #[instrument(level = "trace", skip_all)]
376    fn assemble_builtin_impl_candidates<G: GoalKind<D>>(
377        &mut self,
378        goal: Goal<I, G>,
379        candidates: &mut Vec<Candidate<I>>,
380    ) {
381        let cx = self.cx();
382        let trait_def_id = goal.predicate.trait_def_id(cx);
383
384        // N.B. When assembling built-in candidates for lang items that are also
385        // `auto` traits, then the auto trait candidate that is assembled in
386        // `consider_auto_trait_candidate` MUST be disqualified to remain sound.
387        //
388        // Instead of adding the logic here, it's a better idea to add it in
389        // `EvalCtxt::disqualify_auto_trait_candidate_due_to_possible_impl` in
390        // `solve::trait_goals` instead.
391        let result = if let Err(guar) = goal.predicate.error_reported() {
392            G::consider_error_guaranteed_candidate(self, guar)
393        } else if cx.trait_is_auto(trait_def_id) {
394            G::consider_auto_trait_candidate(self, goal)
395        } else if cx.trait_is_alias(trait_def_id) {
396            G::consider_trait_alias_candidate(self, goal)
397        } else {
398            match cx.as_lang_item(trait_def_id) {
399                Some(TraitSolverLangItem::Sized) => G::consider_builtin_sized_candidate(self, goal),
400                Some(TraitSolverLangItem::Copy | TraitSolverLangItem::Clone) => {
401                    G::consider_builtin_copy_clone_candidate(self, goal)
402                }
403                Some(TraitSolverLangItem::Fn) => {
404                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::Fn)
405                }
406                Some(TraitSolverLangItem::FnMut) => {
407                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::FnMut)
408                }
409                Some(TraitSolverLangItem::FnOnce) => {
410                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::FnOnce)
411                }
412                Some(TraitSolverLangItem::AsyncFn) => {
413                    G::consider_builtin_async_fn_trait_candidates(self, goal, ty::ClosureKind::Fn)
414                }
415                Some(TraitSolverLangItem::AsyncFnMut) => {
416                    G::consider_builtin_async_fn_trait_candidates(
417                        self,
418                        goal,
419                        ty::ClosureKind::FnMut,
420                    )
421                }
422                Some(TraitSolverLangItem::AsyncFnOnce) => {
423                    G::consider_builtin_async_fn_trait_candidates(
424                        self,
425                        goal,
426                        ty::ClosureKind::FnOnce,
427                    )
428                }
429                Some(TraitSolverLangItem::FnPtrTrait) => {
430                    G::consider_builtin_fn_ptr_trait_candidate(self, goal)
431                }
432                Some(TraitSolverLangItem::AsyncFnKindHelper) => {
433                    G::consider_builtin_async_fn_kind_helper_candidate(self, goal)
434                }
435                Some(TraitSolverLangItem::Tuple) => G::consider_builtin_tuple_candidate(self, goal),
436                Some(TraitSolverLangItem::PointeeTrait) => {
437                    G::consider_builtin_pointee_candidate(self, goal)
438                }
439                Some(TraitSolverLangItem::Future) => {
440                    G::consider_builtin_future_candidate(self, goal)
441                }
442                Some(TraitSolverLangItem::Iterator) => {
443                    G::consider_builtin_iterator_candidate(self, goal)
444                }
445                Some(TraitSolverLangItem::FusedIterator) => {
446                    G::consider_builtin_fused_iterator_candidate(self, goal)
447                }
448                Some(TraitSolverLangItem::AsyncIterator) => {
449                    G::consider_builtin_async_iterator_candidate(self, goal)
450                }
451                Some(TraitSolverLangItem::Coroutine) => {
452                    G::consider_builtin_coroutine_candidate(self, goal)
453                }
454                Some(TraitSolverLangItem::DiscriminantKind) => {
455                    G::consider_builtin_discriminant_kind_candidate(self, goal)
456                }
457                Some(TraitSolverLangItem::AsyncDestruct) => {
458                    G::consider_builtin_async_destruct_candidate(self, goal)
459                }
460                Some(TraitSolverLangItem::Destruct) => {
461                    G::consider_builtin_destruct_candidate(self, goal)
462                }
463                Some(TraitSolverLangItem::TransmuteTrait) => {
464                    G::consider_builtin_transmute_candidate(self, goal)
465                }
466                Some(TraitSolverLangItem::BikeshedGuaranteedNoDrop) => {
467                    G::consider_builtin_bikeshed_guaranteed_no_drop_candidate(self, goal)
468                }
469                _ => Err(NoSolution),
470            }
471        };
472
473        candidates.extend(result);
474
475        // There may be multiple unsize candidates for a trait with several supertraits:
476        // `trait Foo: Bar<A> + Bar<B>` and `dyn Foo: Unsize<dyn Bar<_>>`
477        if cx.is_lang_item(trait_def_id, TraitSolverLangItem::Unsize) {
478            candidates.extend(G::consider_structural_builtin_unsize_candidates(self, goal));
479        }
480    }
481
482    #[instrument(level = "trace", skip_all)]
483    fn assemble_param_env_candidates<G: GoalKind<D>>(
484        &mut self,
485        goal: Goal<I, G>,
486        candidates: &mut Vec<Candidate<I>>,
487    ) {
488        for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
489            candidates.extend(G::probe_and_consider_implied_clause(
490                self,
491                CandidateSource::ParamEnv(i),
492                goal,
493                assumption,
494                [],
495            ));
496        }
497    }
498
499    #[instrument(level = "trace", skip_all)]
500    fn assemble_alias_bound_candidates<G: GoalKind<D>>(
501        &mut self,
502        goal: Goal<I, G>,
503        candidates: &mut Vec<Candidate<I>>,
504    ) {
505        let () = self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| {
506            ecx.assemble_alias_bound_candidates_recur(
507                goal.predicate.self_ty(),
508                goal,
509                candidates,
510                AliasBoundKind::SelfBounds,
511            );
512        });
513    }
514
515    /// For some deeply nested `<T>::A::B::C::D` rigid associated type,
516    /// we should explore the item bounds for all levels, since the
517    /// `associated_type_bounds` feature means that a parent associated
518    /// type may carry bounds for a nested associated type.
519    ///
520    /// If we have a projection, check that its self type is a rigid projection.
521    /// If so, continue searching by recursively calling after normalization.
522    // FIXME: This may recurse infinitely, but I can't seem to trigger it without
523    // hitting another overflow error something. Add a depth parameter needed later.
524    fn assemble_alias_bound_candidates_recur<G: GoalKind<D>>(
525        &mut self,
526        self_ty: I::Ty,
527        goal: Goal<I, G>,
528        candidates: &mut Vec<Candidate<I>>,
529        consider_self_bounds: AliasBoundKind,
530    ) {
531        let (kind, alias_ty) = match self_ty.kind() {
532            ty::Bool
533            | ty::Char
534            | ty::Int(_)
535            | ty::Uint(_)
536            | ty::Float(_)
537            | ty::Adt(_, _)
538            | ty::Foreign(_)
539            | ty::Str
540            | ty::Array(_, _)
541            | ty::Pat(_, _)
542            | ty::Slice(_)
543            | ty::RawPtr(_, _)
544            | ty::Ref(_, _, _)
545            | ty::FnDef(_, _)
546            | ty::FnPtr(..)
547            | ty::UnsafeBinder(_)
548            | ty::Dynamic(..)
549            | ty::Closure(..)
550            | ty::CoroutineClosure(..)
551            | ty::Coroutine(..)
552            | ty::CoroutineWitness(..)
553            | ty::Never
554            | ty::Tuple(_)
555            | ty::Param(_)
556            | ty::Placeholder(..)
557            | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
558            | ty::Error(_) => return,
559            ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) | ty::Bound(..) => {
560                panic!("unexpected self type for `{goal:?}`")
561            }
562
563            ty::Infer(ty::TyVar(_)) => {
564                // If we hit infer when normalizing the self type of an alias,
565                // then bail with ambiguity. We should never encounter this on
566                // the *first* iteration of this recursive function.
567                if let Ok(result) =
568                    self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
569                {
570                    candidates.push(Candidate { source: CandidateSource::AliasBound, result });
571                }
572                return;
573            }
574
575            ty::Alias(kind @ (ty::Projection | ty::Opaque), alias_ty) => (kind, alias_ty),
576            ty::Alias(ty::Inherent | ty::Weak, _) => {
577                self.cx().delay_bug(format!("could not normalize {self_ty:?}, it is not WF"));
578                return;
579            }
580        };
581
582        match consider_self_bounds {
583            AliasBoundKind::SelfBounds => {
584                for assumption in self
585                    .cx()
586                    .item_self_bounds(alias_ty.def_id)
587                    .iter_instantiated(self.cx(), alias_ty.args)
588                {
589                    candidates.extend(G::probe_and_consider_implied_clause(
590                        self,
591                        CandidateSource::AliasBound,
592                        goal,
593                        assumption,
594                        [],
595                    ));
596                }
597            }
598            AliasBoundKind::NonSelfBounds => {
599                for assumption in self
600                    .cx()
601                    .item_non_self_bounds(alias_ty.def_id)
602                    .iter_instantiated(self.cx(), alias_ty.args)
603                {
604                    candidates.extend(G::probe_and_consider_implied_clause(
605                        self,
606                        CandidateSource::AliasBound,
607                        goal,
608                        assumption,
609                        [],
610                    ));
611                }
612            }
613        }
614
615        candidates.extend(G::consider_additional_alias_assumptions(self, goal, alias_ty));
616
617        if kind != ty::Projection {
618            return;
619        }
620
621        // Recurse on the self type of the projection.
622        match self.structurally_normalize_ty(goal.param_env, alias_ty.self_ty()) {
623            Ok(next_self_ty) => self.assemble_alias_bound_candidates_recur(
624                next_self_ty,
625                goal,
626                candidates,
627                AliasBoundKind::NonSelfBounds,
628            ),
629            Err(NoSolution) => {}
630        }
631    }
632
633    #[instrument(level = "trace", skip_all)]
634    fn assemble_object_bound_candidates<G: GoalKind<D>>(
635        &mut self,
636        goal: Goal<I, G>,
637        candidates: &mut Vec<Candidate<I>>,
638    ) {
639        let cx = self.cx();
640        if !cx.trait_may_be_implemented_via_object(goal.predicate.trait_def_id(cx)) {
641            return;
642        }
643
644        let self_ty = goal.predicate.self_ty();
645        let bounds = match self_ty.kind() {
646            ty::Bool
647            | ty::Char
648            | ty::Int(_)
649            | ty::Uint(_)
650            | ty::Float(_)
651            | ty::Adt(_, _)
652            | ty::Foreign(_)
653            | ty::Str
654            | ty::Array(_, _)
655            | ty::Pat(_, _)
656            | ty::Slice(_)
657            | ty::RawPtr(_, _)
658            | ty::Ref(_, _, _)
659            | ty::FnDef(_, _)
660            | ty::FnPtr(..)
661            | ty::UnsafeBinder(_)
662            | ty::Alias(..)
663            | ty::Closure(..)
664            | ty::CoroutineClosure(..)
665            | ty::Coroutine(..)
666            | ty::CoroutineWitness(..)
667            | ty::Never
668            | ty::Tuple(_)
669            | ty::Param(_)
670            | ty::Placeholder(..)
671            | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
672            | ty::Error(_) => return,
673            ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
674            | ty::Bound(..) => panic!("unexpected self type for `{goal:?}`"),
675            ty::Dynamic(bounds, ..) => bounds,
676        };
677
678        // Do not consider built-in object impls for dyn-incompatible types.
679        if bounds.principal_def_id().is_some_and(|def_id| !cx.trait_is_dyn_compatible(def_id)) {
680            return;
681        }
682
683        // Consider all of the auto-trait and projection bounds, which don't
684        // need to be recorded as a `BuiltinImplSource::Object` since they don't
685        // really have a vtable base...
686        for bound in bounds.iter() {
687            match bound.skip_binder() {
688                ty::ExistentialPredicate::Trait(_) => {
689                    // Skip principal
690                }
691                ty::ExistentialPredicate::Projection(_)
692                | ty::ExistentialPredicate::AutoTrait(_) => {
693                    candidates.extend(G::probe_and_consider_object_bound_candidate(
694                        self,
695                        CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
696                        goal,
697                        bound.with_self_ty(cx, self_ty),
698                    ));
699                }
700            }
701        }
702
703        // FIXME: We only need to do *any* of this if we're considering a trait goal,
704        // since we don't need to look at any supertrait or anything if we are doing
705        // a projection goal.
706        if let Some(principal) = bounds.principal() {
707            let principal_trait_ref = principal.with_self_ty(cx, self_ty);
708            for (idx, assumption) in elaborate::supertraits(cx, principal_trait_ref).enumerate() {
709                candidates.extend(G::probe_and_consider_object_bound_candidate(
710                    self,
711                    CandidateSource::BuiltinImpl(BuiltinImplSource::Object(idx)),
712                    goal,
713                    assumption.upcast(cx),
714                ));
715            }
716        }
717    }
718
719    /// In coherence we have to not only care about all impls we know about, but
720    /// also consider impls which may get added in a downstream or sibling crate
721    /// or which an upstream impl may add in a minor release.
722    ///
723    /// To do so we return a single ambiguous candidate in case such an unknown
724    /// impl could apply to the current goal.
725    #[instrument(level = "trace", skip_all)]
726    fn consider_coherence_unknowable_candidate<G: GoalKind<D>>(
727        &mut self,
728        goal: Goal<I, G>,
729    ) -> Result<Candidate<I>, NoSolution> {
730        self.probe_trait_candidate(CandidateSource::CoherenceUnknowable).enter(|ecx| {
731            let cx = ecx.cx();
732            let trait_ref = goal.predicate.trait_ref(cx);
733            if ecx.trait_ref_is_knowable(goal.param_env, trait_ref)? {
734                Err(NoSolution)
735            } else {
736                // While the trait bound itself may be unknowable, we may be able to
737                // prove that a super trait is not implemented. For this, we recursively
738                // prove the super trait bounds of the current goal.
739                //
740                // We skip the goal itself as that one would cycle.
741                let predicate: I::Predicate = trait_ref.upcast(cx);
742                ecx.add_goals(
743                    GoalSource::Misc,
744                    elaborate::elaborate(cx, [predicate])
745                        .skip(1)
746                        .map(|predicate| goal.with(cx, predicate)),
747                );
748                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
749            }
750        })
751    }
752
753    /// We sadly can't simply take all possible candidates for normalization goals
754    /// and check whether they result in the same constraints. We want to make sure
755    /// that trying to normalize an alias doesn't result in constraints which aren't
756    /// otherwise required.
757    ///
758    /// Most notably, when proving a trait goal by via a where-bound, we should not
759    /// normalize via impls which have stricter region constraints than the where-bound:
760    ///
761    /// ```rust
762    /// trait Trait<'a> {
763    ///     type Assoc;
764    /// }
765    ///
766    /// impl<'a, T: 'a> Trait<'a> for T {
767    ///     type Assoc = u32;
768    /// }
769    ///
770    /// fn with_bound<'a, T: Trait<'a>>(_value: T::Assoc) {}
771    /// ```
772    ///
773    /// The where-bound of `with_bound` doesn't specify the associated type, so we would
774    /// only be able to normalize `<T as Trait<'a>>::Assoc` by using the impl. This impl
775    /// adds a `T: 'a` bound however, which would result in a region error. Given that the
776    /// user explicitly wrote that `T: Trait<'a>` holds, this is undesirable and we instead
777    /// treat the alias as rigid.
778    ///
779    /// See trait-system-refactor-initiative#124 for more details.
780    #[instrument(level = "debug", skip(self, inject_normalize_to_rigid_candidate), ret)]
781    pub(super) fn merge_candidates(
782        &mut self,
783        proven_via: Option<TraitGoalProvenVia>,
784        candidates: Vec<Candidate<I>>,
785        inject_normalize_to_rigid_candidate: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
786    ) -> QueryResult<I> {
787        let Some(proven_via) = proven_via else {
788            // We don't care about overflow. If proving the trait goal overflowed, then
789            // it's enough to report an overflow error for that, we don't also have to
790            // overflow during normalization.
791            return Ok(self.make_ambiguous_response_no_constraints(MaybeCause::Ambiguity));
792        };
793
794        let responses: Vec<_> = match proven_via {
795            // Even when a trait bound has been proven using a where-bound, we
796            // still need to consider alias-bounds for normalization, see
797            // tests/ui/next-solver/alias-bound-shadowed-by-env.rs.
798            //
799            // FIXME(const_trait_impl): should this behavior also be used by
800            // constness checking. Doing so is *at least theoretically* breaking,
801            // see github.com/rust-lang/rust/issues/133044#issuecomment-2500709754
802            TraitGoalProvenVia::ParamEnv | TraitGoalProvenVia::AliasBound => {
803                let mut candidates_from_env: Vec<_> = candidates
804                    .iter()
805                    .filter(|c| {
806                        matches!(
807                            c.source,
808                            CandidateSource::AliasBound | CandidateSource::ParamEnv(_)
809                        )
810                    })
811                    .map(|c| c.result)
812                    .collect();
813
814                // If the trait goal has been proven by using the environment, we want to treat
815                // aliases as rigid if there are no applicable projection bounds in the environment.
816                if candidates_from_env.is_empty() {
817                    if let Ok(response) = inject_normalize_to_rigid_candidate(self) {
818                        candidates_from_env.push(response);
819                    }
820                }
821                candidates_from_env
822            }
823            TraitGoalProvenVia::Misc => candidates.iter().map(|c| c.result).collect(),
824        };
825
826        self.try_merge_responses(&responses).map_or_else(|| self.flounder(&responses), Ok)
827    }
828}
rustc_next_trait_solver/solve/assembly/mod.rs

rustc_next_trait_solver/solve/assembly/
mod.rs
