rustc_next_trait_solver/solve/
trait_goals.rs

1//! Dealing with trait goals, i.e. `T: Trait<'a, U>`.
2
3use rustc_type_ir::data_structures::IndexSet;
4use rustc_type_ir::fast_reject::DeepRejectCtxt;
5use rustc_type_ir::inherent::*;
6use rustc_type_ir::lang_items::TraitSolverLangItem;
7use rustc_type_ir::solve::{CanonicalResponse, SizedTraitKind};
8use rustc_type_ir::{
9    self as ty, Interner, Movability, TraitPredicate, TraitRef, TypeVisitableExt as _, TypingMode,
10    Upcast as _, elaborate,
11};
12use tracing::{debug, instrument, trace};
13
14use crate::delegate::SolverDelegate;
15use crate::solve::assembly::structural_traits::{self, AsyncCallableRelevantTypes};
16use crate::solve::assembly::{self, AllowInferenceConstraints, AssembleCandidatesFrom, Candidate};
17use crate::solve::inspect::ProbeKind;
18use crate::solve::{
19    BuiltinImplSource, CandidateSource, Certainty, EvalCtxt, Goal, GoalSource, MaybeCause,
20    NoSolution, ParamEnvSource, QueryResult, has_only_region_constraints,
21};
22
23impl<D, I> assembly::GoalKind<D> for TraitPredicate<I>
24where
25    D: SolverDelegate<Interner = I>,
26    I: Interner,
27{
28    fn self_ty(self) -> I::Ty {
29        self.self_ty()
30    }
31
32    fn trait_ref(self, _: I) -> ty::TraitRef<I> {
33        self.trait_ref
34    }
35
36    fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self {
37        self.with_self_ty(cx, self_ty)
38    }
39
40    fn trait_def_id(self, _: I) -> I::DefId {
41        self.def_id()
42    }
43
44    fn consider_additional_alias_assumptions(
45        _ecx: &mut EvalCtxt<'_, D>,
46        _goal: Goal<I, Self>,
47        _alias_ty: ty::AliasTy<I>,
48    ) -> Vec<Candidate<I>> {
49        vec![]
50    }
51
52    fn consider_impl_candidate(
53        ecx: &mut EvalCtxt<'_, D>,
54        goal: Goal<I, TraitPredicate<I>>,
55        impl_def_id: I::DefId,
56    ) -> Result<Candidate<I>, NoSolution> {
57        let cx = ecx.cx();
58
59        let impl_trait_ref = cx.impl_trait_ref(impl_def_id);
60        if !DeepRejectCtxt::relate_rigid_infer(ecx.cx())
61            .args_may_unify(goal.predicate.trait_ref.args, impl_trait_ref.skip_binder().args)
62        {
63            return Err(NoSolution);
64        }
65
66        // An upper bound of the certainty of this goal, used to lower the certainty
67        // of reservation impl to ambiguous during coherence.
68        let impl_polarity = cx.impl_polarity(impl_def_id);
69        let maximal_certainty = match (impl_polarity, goal.predicate.polarity) {
70            // In intercrate mode, this is ambiguous. But outside of intercrate,
71            // it's not a real impl.
72            (ty::ImplPolarity::Reservation, _) => match ecx.typing_mode() {
73                TypingMode::Coherence => Certainty::AMBIGUOUS,
74                TypingMode::Analysis { .. }
75                | TypingMode::Borrowck { .. }
76                | TypingMode::PostBorrowckAnalysis { .. }
77                | TypingMode::PostAnalysis => return Err(NoSolution),
78            },
79
80            // Impl matches polarity
81            (ty::ImplPolarity::Positive, ty::PredicatePolarity::Positive)
82            | (ty::ImplPolarity::Negative, ty::PredicatePolarity::Negative) => Certainty::Yes,
83
84            // Impl doesn't match polarity
85            (ty::ImplPolarity::Positive, ty::PredicatePolarity::Negative)
86            | (ty::ImplPolarity::Negative, ty::PredicatePolarity::Positive) => {
87                return Err(NoSolution);
88            }
89        };
90
91        ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| {
92            let impl_args = ecx.fresh_args_for_item(impl_def_id);
93            ecx.record_impl_args(impl_args);
94            let impl_trait_ref = impl_trait_ref.instantiate(cx, impl_args);
95
96            ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
97            let where_clause_bounds = cx
98                .predicates_of(impl_def_id)
99                .iter_instantiated(cx, impl_args)
100                .map(|pred| goal.with(cx, pred));
101            ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds);
102
103            // We currently elaborate all supertrait outlives obligations from impls.
104            // This can be removed when we actually do coinduction correctly, and prove
105            // all supertrait obligations unconditionally.
106            ecx.add_goals(
107                GoalSource::Misc,
108                cx.impl_super_outlives(impl_def_id)
109                    .iter_instantiated(cx, impl_args)
110                    .map(|pred| goal.with(cx, pred)),
111            );
112
113            ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty)
114        })
115    }
116
117    fn consider_error_guaranteed_candidate(
118        ecx: &mut EvalCtxt<'_, D>,
119        _guar: I::ErrorGuaranteed,
120    ) -> Result<Candidate<I>, NoSolution> {
121        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
122            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
123    }
124
125    fn fast_reject_assumption(
126        ecx: &mut EvalCtxt<'_, D>,
127        goal: Goal<I, Self>,
128        assumption: I::Clause,
129    ) -> Result<(), NoSolution> {
130        fn trait_def_id_matches<I: Interner>(
131            cx: I,
132            clause_def_id: I::DefId,
133            goal_def_id: I::DefId,
134        ) -> bool {
135            clause_def_id == goal_def_id
136            // PERF(sized-hierarchy): Sizedness supertraits aren't elaborated to improve perf, so
137            // check for a `MetaSized` supertrait being matched against a `Sized` assumption.
138            //
139            // `PointeeSized` bounds are syntactic sugar for a lack of bounds so don't need this.
140                || (cx.is_lang_item(clause_def_id, TraitSolverLangItem::Sized)
141                    && cx.is_lang_item(goal_def_id, TraitSolverLangItem::MetaSized))
142        }
143
144        if let Some(trait_clause) = assumption.as_trait_clause()
145            && trait_clause.polarity() == goal.predicate.polarity
146            && trait_def_id_matches(ecx.cx(), trait_clause.def_id(), goal.predicate.def_id())
147            && DeepRejectCtxt::relate_rigid_rigid(ecx.cx()).args_may_unify(
148                goal.predicate.trait_ref.args,
149                trait_clause.skip_binder().trait_ref.args,
150            )
151        {
152            return Ok(());
153        } else {
154            Err(NoSolution)
155        }
156    }
157
158    fn match_assumption(
159        ecx: &mut EvalCtxt<'_, D>,
160        goal: Goal<I, Self>,
161        assumption: I::Clause,
162        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
163    ) -> QueryResult<I> {
164        let trait_clause = assumption.as_trait_clause().unwrap();
165
166        // PERF(sized-hierarchy): Sizedness supertraits aren't elaborated to improve perf, so
167        // check for a `Sized` subtrait when looking for `MetaSized`. `PointeeSized` bounds
168        // are syntactic sugar for a lack of bounds so don't need this.
169        if ecx.cx().is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::MetaSized)
170            && ecx.cx().is_lang_item(trait_clause.def_id(), TraitSolverLangItem::Sized)
171        {
172            let meta_sized_clause =
173                trait_predicate_with_def_id(ecx.cx(), trait_clause, goal.predicate.def_id());
174            return Self::match_assumption(ecx, goal, meta_sized_clause, then);
175        }
176
177        let assumption_trait_pred = ecx.instantiate_binder_with_infer(trait_clause);
178        ecx.eq(goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref)?;
179
180        then(ecx)
181    }
182
183    fn consider_auto_trait_candidate(
184        ecx: &mut EvalCtxt<'_, D>,
185        goal: Goal<I, Self>,
186    ) -> Result<Candidate<I>, NoSolution> {
187        let cx = ecx.cx();
188        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
189            return Err(NoSolution);
190        }
191
192        if let Some(result) = ecx.disqualify_auto_trait_candidate_due_to_possible_impl(goal) {
193            return result;
194        }
195
196        // Only consider auto impls of unsafe traits when there are no unsafe
197        // fields.
198        if cx.trait_is_unsafe(goal.predicate.def_id())
199            && goal.predicate.self_ty().has_unsafe_fields()
200        {
201            return Err(NoSolution);
202        }
203
204        // We leak the implemented auto traits of opaques outside of their defining scope.
205        // This depends on `typeck` of the defining scope of that opaque, which may result in
206        // fatal query cycles.
207        //
208        // We only get to this point if we're outside of the defining scope as we'd otherwise
209        // be able to normalize the opaque type. We may also cycle in case `typeck` of a defining
210        // scope relies on the current context, e.g. either because it also leaks auto trait
211        // bounds of opaques defined in the current context or by evaluating the current item.
212        //
213        // To avoid this we don't try to leak auto trait bounds if they can also be proven via
214        // item bounds of the opaque. These bounds are always applicable as auto traits must not
215        // have any generic parameters. They would also get preferred over the impl candidate
216        // when merging candidates anyways.
217        //
218        // See tests/ui/impl-trait/auto-trait-leakage/avoid-query-cycle-via-item-bound.rs.
219        if let ty::Alias(ty::Opaque, opaque_ty) = goal.predicate.self_ty().kind() {
220            debug_assert!(ecx.opaque_type_is_rigid(opaque_ty.def_id));
221            for item_bound in cx.item_self_bounds(opaque_ty.def_id).skip_binder() {
222                if item_bound
223                    .as_trait_clause()
224                    .is_some_and(|b| b.def_id() == goal.predicate.def_id())
225                {
226                    return Err(NoSolution);
227                }
228            }
229        }
230
231        // We need to make sure to stall any coroutines we are inferring to avoid query cycles.
232        if let Some(cand) = ecx.try_stall_coroutine_witness(goal.predicate.self_ty()) {
233            return cand;
234        }
235
236        ecx.probe_and_evaluate_goal_for_constituent_tys(
237            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
238            goal,
239            structural_traits::instantiate_constituent_tys_for_auto_trait,
240        )
241    }
242
243    fn consider_trait_alias_candidate(
244        ecx: &mut EvalCtxt<'_, D>,
245        goal: Goal<I, Self>,
246    ) -> Result<Candidate<I>, NoSolution> {
247        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
248            return Err(NoSolution);
249        }
250
251        let cx = ecx.cx();
252
253        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
254            let nested_obligations = cx
255                .predicates_of(goal.predicate.def_id())
256                .iter_instantiated(cx, goal.predicate.trait_ref.args)
257                .map(|p| goal.with(cx, p));
258            // While you could think of trait aliases to have a single builtin impl
259            // which uses its implied trait bounds as where-clauses, using
260            // `GoalSource::ImplWhereClause` here would be incorrect, as we also
261            // impl them, which means we're "stepping out of the impl constructor"
262            // again. To handle this, we treat these cycles as ambiguous for now.
263            ecx.add_goals(GoalSource::Misc, nested_obligations);
264            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
265        })
266    }
267
268    fn consider_builtin_sizedness_candidates(
269        ecx: &mut EvalCtxt<'_, D>,
270        goal: Goal<I, Self>,
271        sizedness: SizedTraitKind,
272    ) -> Result<Candidate<I>, NoSolution> {
273        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
274            return Err(NoSolution);
275        }
276
277        ecx.probe_and_evaluate_goal_for_constituent_tys(
278            CandidateSource::BuiltinImpl(BuiltinImplSource::Trivial),
279            goal,
280            |ecx, ty| {
281                structural_traits::instantiate_constituent_tys_for_sizedness_trait(
282                    ecx, sizedness, ty,
283                )
284            },
285        )
286    }
287
288    fn consider_builtin_copy_clone_candidate(
289        ecx: &mut EvalCtxt<'_, D>,
290        goal: Goal<I, Self>,
291    ) -> Result<Candidate<I>, NoSolution> {
292        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
293            return Err(NoSolution);
294        }
295
296        // We need to make sure to stall any coroutines we are inferring to avoid query cycles.
297        if let Some(cand) = ecx.try_stall_coroutine_witness(goal.predicate.self_ty()) {
298            return cand;
299        }
300
301        ecx.probe_and_evaluate_goal_for_constituent_tys(
302            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
303            goal,
304            structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
305        )
306    }
307
308    fn consider_builtin_fn_ptr_trait_candidate(
309        ecx: &mut EvalCtxt<'_, D>,
310        goal: Goal<I, Self>,
311    ) -> Result<Candidate<I>, NoSolution> {
312        let self_ty = goal.predicate.self_ty();
313        match goal.predicate.polarity {
314            // impl FnPtr for FnPtr {}
315            ty::PredicatePolarity::Positive => {
316                if self_ty.is_fn_ptr() {
317                    ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
318                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
319                    })
320                } else {
321                    Err(NoSolution)
322                }
323            }
324            //  impl !FnPtr for T where T != FnPtr && T is rigid {}
325            ty::PredicatePolarity::Negative => {
326                // If a type is rigid and not a fn ptr, then we know for certain
327                // that it does *not* implement `FnPtr`.
328                if !self_ty.is_fn_ptr() && self_ty.is_known_rigid() {
329                    ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
330                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
331                    })
332                } else {
333                    Err(NoSolution)
334                }
335            }
336        }
337    }
338
339    fn consider_builtin_fn_trait_candidates(
340        ecx: &mut EvalCtxt<'_, D>,
341        goal: Goal<I, Self>,
342        goal_kind: ty::ClosureKind,
343    ) -> Result<Candidate<I>, NoSolution> {
344        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
345            return Err(NoSolution);
346        }
347
348        let cx = ecx.cx();
349        let tupled_inputs_and_output =
350            match structural_traits::extract_tupled_inputs_and_output_from_callable(
351                cx,
352                goal.predicate.self_ty(),
353                goal_kind,
354            )? {
355                Some(a) => a,
356                None => {
357                    return ecx.forced_ambiguity(MaybeCause::Ambiguity);
358                }
359            };
360
361        // A built-in `Fn` impl only holds if the output is sized.
362        // (FIXME: technically we only need to check this if the type is a fn ptr...)
363        let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| {
364            ty::TraitRef::new(cx, cx.require_lang_item(TraitSolverLangItem::Sized), [output])
365        });
366
367        let pred = tupled_inputs_and_output
368            .map_bound(|(inputs, _)| {
369                ty::TraitRef::new(cx, goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
370            })
371            .upcast(cx);
372        Self::probe_and_consider_implied_clause(
373            ecx,
374            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
375            goal,
376            pred,
377            [(GoalSource::ImplWhereBound, goal.with(cx, output_is_sized_pred))],
378        )
379    }
380
381    fn consider_builtin_async_fn_trait_candidates(
382        ecx: &mut EvalCtxt<'_, D>,
383        goal: Goal<I, Self>,
384        goal_kind: ty::ClosureKind,
385    ) -> Result<Candidate<I>, NoSolution> {
386        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
387            return Err(NoSolution);
388        }
389
390        let cx = ecx.cx();
391        let (tupled_inputs_and_output_and_coroutine, nested_preds) =
392            structural_traits::extract_tupled_inputs_and_output_from_async_callable(
393                cx,
394                goal.predicate.self_ty(),
395                goal_kind,
396                // This region doesn't matter because we're throwing away the coroutine type
397                Region::new_static(cx),
398            )?;
399
400        // A built-in `AsyncFn` impl only holds if the output is sized.
401        // (FIXME: technically we only need to check this if the type is a fn ptr...)
402        let output_is_sized_pred = tupled_inputs_and_output_and_coroutine.map_bound(
403            |AsyncCallableRelevantTypes { output_coroutine_ty, .. }| {
404                ty::TraitRef::new(
405                    cx,
406                    cx.require_lang_item(TraitSolverLangItem::Sized),
407                    [output_coroutine_ty],
408                )
409            },
410        );
411
412        let pred = tupled_inputs_and_output_and_coroutine
413            .map_bound(|AsyncCallableRelevantTypes { tupled_inputs_ty, .. }| {
414                ty::TraitRef::new(
415                    cx,
416                    goal.predicate.def_id(),
417                    [goal.predicate.self_ty(), tupled_inputs_ty],
418                )
419            })
420            .upcast(cx);
421        Self::probe_and_consider_implied_clause(
422            ecx,
423            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
424            goal,
425            pred,
426            [goal.with(cx, output_is_sized_pred)]
427                .into_iter()
428                .chain(nested_preds.into_iter().map(|pred| goal.with(cx, pred)))
429                .map(|goal| (GoalSource::ImplWhereBound, goal)),
430        )
431    }
432
433    fn consider_builtin_async_fn_kind_helper_candidate(
434        ecx: &mut EvalCtxt<'_, D>,
435        goal: Goal<I, Self>,
436    ) -> Result<Candidate<I>, NoSolution> {
437        let [closure_fn_kind_ty, goal_kind_ty] = *goal.predicate.trait_ref.args.as_slice() else {
438            panic!();
439        };
440
441        let Some(closure_kind) = closure_fn_kind_ty.expect_ty().to_opt_closure_kind() else {
442            // We don't need to worry about the self type being an infer var.
443            return Err(NoSolution);
444        };
445        let goal_kind = goal_kind_ty.expect_ty().to_opt_closure_kind().unwrap();
446        if closure_kind.extends(goal_kind) {
447            ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
448                .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
449        } else {
450            Err(NoSolution)
451        }
452    }
453
454    /// ```rust, ignore (not valid rust syntax)
455    /// impl Tuple for () {}
456    /// impl Tuple for (T1,) {}
457    /// impl Tuple for (T1, T2) {}
458    /// impl Tuple for (T1, .., Tn) {}
459    /// ```
460    fn consider_builtin_tuple_candidate(
461        ecx: &mut EvalCtxt<'_, D>,
462        goal: Goal<I, Self>,
463    ) -> Result<Candidate<I>, NoSolution> {
464        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
465            return Err(NoSolution);
466        }
467
468        if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
469            ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
470                .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
471        } else {
472            Err(NoSolution)
473        }
474    }
475
476    fn consider_builtin_pointee_candidate(
477        ecx: &mut EvalCtxt<'_, D>,
478        goal: Goal<I, Self>,
479    ) -> Result<Candidate<I>, NoSolution> {
480        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
481            return Err(NoSolution);
482        }
483
484        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
485            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
486    }
487
488    fn consider_builtin_future_candidate(
489        ecx: &mut EvalCtxt<'_, D>,
490        goal: Goal<I, Self>,
491    ) -> Result<Candidate<I>, NoSolution> {
492        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
493            return Err(NoSolution);
494        }
495
496        let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
497            return Err(NoSolution);
498        };
499
500        // Coroutines are not futures unless they come from `async` desugaring
501        let cx = ecx.cx();
502        if !cx.coroutine_is_async(def_id) {
503            return Err(NoSolution);
504        }
505
506        // Async coroutine unconditionally implement `Future`
507        // Technically, we need to check that the future output type is Sized,
508        // but that's already proven by the coroutine being WF.
509        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
510            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
511    }
512
513    fn consider_builtin_iterator_candidate(
514        ecx: &mut EvalCtxt<'_, D>,
515        goal: Goal<I, Self>,
516    ) -> Result<Candidate<I>, NoSolution> {
517        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
518            return Err(NoSolution);
519        }
520
521        let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
522            return Err(NoSolution);
523        };
524
525        // Coroutines are not iterators unless they come from `gen` desugaring
526        let cx = ecx.cx();
527        if !cx.coroutine_is_gen(def_id) {
528            return Err(NoSolution);
529        }
530
531        // Gen coroutines unconditionally implement `Iterator`
532        // Technically, we need to check that the iterator output type is Sized,
533        // but that's already proven by the coroutines being WF.
534        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
535            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
536    }
537
538    fn consider_builtin_fused_iterator_candidate(
539        ecx: &mut EvalCtxt<'_, D>,
540        goal: Goal<I, Self>,
541    ) -> Result<Candidate<I>, NoSolution> {
542        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
543            return Err(NoSolution);
544        }
545
546        let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
547            return Err(NoSolution);
548        };
549
550        // Coroutines are not iterators unless they come from `gen` desugaring
551        let cx = ecx.cx();
552        if !cx.coroutine_is_gen(def_id) {
553            return Err(NoSolution);
554        }
555
556        // Gen coroutines unconditionally implement `FusedIterator`.
557        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
558            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
559    }
560
561    fn consider_builtin_async_iterator_candidate(
562        ecx: &mut EvalCtxt<'_, D>,
563        goal: Goal<I, Self>,
564    ) -> Result<Candidate<I>, NoSolution> {
565        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
566            return Err(NoSolution);
567        }
568
569        let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
570            return Err(NoSolution);
571        };
572
573        // Coroutines are not iterators unless they come from `gen` desugaring
574        let cx = ecx.cx();
575        if !cx.coroutine_is_async_gen(def_id) {
576            return Err(NoSolution);
577        }
578
579        // Gen coroutines unconditionally implement `Iterator`
580        // Technically, we need to check that the iterator output type is Sized,
581        // but that's already proven by the coroutines being WF.
582        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
583            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
584    }
585
586    fn consider_builtin_coroutine_candidate(
587        ecx: &mut EvalCtxt<'_, D>,
588        goal: Goal<I, Self>,
589    ) -> Result<Candidate<I>, NoSolution> {
590        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
591            return Err(NoSolution);
592        }
593
594        let self_ty = goal.predicate.self_ty();
595        let ty::Coroutine(def_id, args) = self_ty.kind() else {
596            return Err(NoSolution);
597        };
598
599        // `async`-desugared coroutines do not implement the coroutine trait
600        let cx = ecx.cx();
601        if !cx.is_general_coroutine(def_id) {
602            return Err(NoSolution);
603        }
604
605        let coroutine = args.as_coroutine();
606        Self::probe_and_consider_implied_clause(
607            ecx,
608            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
609            goal,
610            ty::TraitRef::new(cx, goal.predicate.def_id(), [self_ty, coroutine.resume_ty()])
611                .upcast(cx),
612            // Technically, we need to check that the coroutine types are Sized,
613            // but that's already proven by the coroutine being WF.
614            [],
615        )
616    }
617
618    fn consider_builtin_discriminant_kind_candidate(
619        ecx: &mut EvalCtxt<'_, D>,
620        goal: Goal<I, Self>,
621    ) -> Result<Candidate<I>, NoSolution> {
622        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
623            return Err(NoSolution);
624        }
625
626        // `DiscriminantKind` is automatically implemented for every type.
627        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
628            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
629    }
630
631    fn consider_builtin_destruct_candidate(
632        ecx: &mut EvalCtxt<'_, D>,
633        goal: Goal<I, Self>,
634    ) -> Result<Candidate<I>, NoSolution> {
635        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
636            return Err(NoSolution);
637        }
638
639        // `Destruct` is automatically implemented for every type in
640        // non-const environments.
641        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
642            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
643    }
644
645    fn consider_builtin_transmute_candidate(
646        ecx: &mut EvalCtxt<'_, D>,
647        goal: Goal<I, Self>,
648    ) -> Result<Candidate<I>, NoSolution> {
649        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
650            return Err(NoSolution);
651        }
652
653        // `rustc_transmute` does not have support for type or const params
654        if goal.has_non_region_placeholders() {
655            return Err(NoSolution);
656        }
657
658        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
659            let assume = ecx.structurally_normalize_const(
660                goal.param_env,
661                goal.predicate.trait_ref.args.const_at(2),
662            )?;
663
664            let certainty = ecx.is_transmutable(
665                goal.predicate.trait_ref.args.type_at(0),
666                goal.predicate.trait_ref.args.type_at(1),
667                assume,
668            )?;
669            ecx.evaluate_added_goals_and_make_canonical_response(certainty)
670        })
671    }
672
673    /// NOTE: This is implemented as a built-in goal and not a set of impls like:
674    ///
675    /// ```rust,ignore (illustrative)
676    /// impl<T> BikeshedGuaranteedNoDrop for T where T: Copy {}
677    /// impl<T> BikeshedGuaranteedNoDrop for ManuallyDrop<T> {}
678    /// ```
679    ///
680    /// because these impls overlap, and I'd rather not build a coherence hack for
681    /// this harmless overlap.
682    fn consider_builtin_bikeshed_guaranteed_no_drop_candidate(
683        ecx: &mut EvalCtxt<'_, D>,
684        goal: Goal<I, Self>,
685    ) -> Result<Candidate<I>, NoSolution> {
686        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
687            return Err(NoSolution);
688        }
689
690        let cx = ecx.cx();
691        ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
692            let ty = goal.predicate.self_ty();
693            match ty.kind() {
694                // `&mut T` and `&T` always implement `BikeshedGuaranteedNoDrop`.
695                ty::Ref(..) => {}
696                // `ManuallyDrop<T>` always implements `BikeshedGuaranteedNoDrop`.
697                ty::Adt(def, _) if def.is_manually_drop() => {}
698                // Arrays and tuples implement `BikeshedGuaranteedNoDrop` only if
699                // their constituent types implement `BikeshedGuaranteedNoDrop`.
700                ty::Tuple(tys) => {
701                    ecx.add_goals(
702                        GoalSource::ImplWhereBound,
703                        tys.iter().map(|elem_ty| {
704                            goal.with(cx, ty::TraitRef::new(cx, goal.predicate.def_id(), [elem_ty]))
705                        }),
706                    );
707                }
708                ty::Array(elem_ty, _) => {
709                    ecx.add_goal(
710                        GoalSource::ImplWhereBound,
711                        goal.with(cx, ty::TraitRef::new(cx, goal.predicate.def_id(), [elem_ty])),
712                    );
713                }
714
715                // All other types implement `BikeshedGuaranteedNoDrop` only if
716                // they implement `Copy`. We could be smart here and short-circuit
717                // some trivially `Copy`/`!Copy` types, but there's no benefit.
718                ty::FnDef(..)
719                | ty::FnPtr(..)
720                | ty::Error(_)
721                | ty::Uint(_)
722                | ty::Int(_)
723                | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
724                | ty::Bool
725                | ty::Float(_)
726                | ty::Char
727                | ty::RawPtr(..)
728                | ty::Never
729                | ty::Pat(..)
730                | ty::Dynamic(..)
731                | ty::Str
732                | ty::Slice(_)
733                | ty::Foreign(..)
734                | ty::Adt(..)
735                | ty::Alias(..)
736                | ty::Param(_)
737                | ty::Placeholder(..)
738                | ty::Closure(..)
739                | ty::CoroutineClosure(..)
740                | ty::Coroutine(..)
741                | ty::UnsafeBinder(_)
742                | ty::CoroutineWitness(..) => {
743                    ecx.add_goal(
744                        GoalSource::ImplWhereBound,
745                        goal.with(
746                            cx,
747                            ty::TraitRef::new(
748                                cx,
749                                cx.require_lang_item(TraitSolverLangItem::Copy),
750                                [ty],
751                            ),
752                        ),
753                    );
754                }
755
756                ty::Bound(..)
757                | ty::Infer(
758                    ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_),
759                ) => {
760                    panic!("unexpected type `{ty:?}`")
761                }
762            }
763
764            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
765        })
766    }
767
768    /// ```ignore (builtin impl example)
769    /// trait Trait {
770    ///     fn foo(&self);
771    /// }
772    /// // results in the following builtin impl
773    /// impl<'a, T: Trait + 'a> Unsize<dyn Trait + 'a> for T {}
774    /// ```
775    fn consider_structural_builtin_unsize_candidates(
776        ecx: &mut EvalCtxt<'_, D>,
777        goal: Goal<I, Self>,
778    ) -> Vec<Candidate<I>> {
779        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
780            return vec![];
781        }
782
783        let result_to_single = |result| match result {
784            Ok(resp) => vec![resp],
785            Err(NoSolution) => vec![],
786        };
787
788        ecx.probe(|_| ProbeKind::UnsizeAssembly).enter(|ecx| {
789            let a_ty = goal.predicate.self_ty();
790            // We need to normalize the b_ty since it's matched structurally
791            // in the other functions below.
792            let Ok(b_ty) = ecx.structurally_normalize_ty(
793                goal.param_env,
794                goal.predicate.trait_ref.args.type_at(1),
795            ) else {
796                return vec![];
797            };
798
799            let goal = goal.with(ecx.cx(), (a_ty, b_ty));
800            match (a_ty.kind(), b_ty.kind()) {
801                (ty::Infer(ty::TyVar(..)), ..) => panic!("unexpected infer {a_ty:?} {b_ty:?}"),
802
803                (_, ty::Infer(ty::TyVar(..))) => {
804                    result_to_single(ecx.forced_ambiguity(MaybeCause::Ambiguity))
805                }
806
807                // Trait upcasting, or `dyn Trait + Auto + 'a` -> `dyn Trait + 'b`.
808                (
809                    ty::Dynamic(a_data, a_region, ty::Dyn),
810                    ty::Dynamic(b_data, b_region, ty::Dyn),
811                ) => ecx.consider_builtin_dyn_upcast_candidates(
812                    goal, a_data, a_region, b_data, b_region,
813                ),
814
815                // `T` -> `dyn Trait` unsizing.
816                (_, ty::Dynamic(b_region, b_data, ty::Dyn)) => result_to_single(
817                    ecx.consider_builtin_unsize_to_dyn_candidate(goal, b_region, b_data),
818                ),
819
820                // `[T; N]` -> `[T]` unsizing
821                (ty::Array(a_elem_ty, ..), ty::Slice(b_elem_ty)) => {
822                    result_to_single(ecx.consider_builtin_array_unsize(goal, a_elem_ty, b_elem_ty))
823                }
824
825                // `Struct<T>` -> `Struct<U>` where `T: Unsize<U>`
826                (ty::Adt(a_def, a_args), ty::Adt(b_def, b_args))
827                    if a_def.is_struct() && a_def == b_def =>
828                {
829                    result_to_single(
830                        ecx.consider_builtin_struct_unsize(goal, a_def, a_args, b_args),
831                    )
832                }
833
834                _ => vec![],
835            }
836        })
837    }
838}
839
840/// Small helper function to change the `def_id` of a trait predicate - this is not normally
841/// something that you want to do, as different traits will require different args and so making
842/// it easy to change the trait is something of a footgun, but it is useful in the narrow
843/// circumstance of changing from `MetaSized` to `Sized`, which happens as part of the lazy
844/// elaboration of sizedness candidates.
845#[inline(always)]
846fn trait_predicate_with_def_id<I: Interner>(
847    cx: I,
848    clause: ty::Binder<I, ty::TraitPredicate<I>>,
849    did: I::DefId,
850) -> I::Clause {
851    clause
852        .map_bound(|c| TraitPredicate {
853            trait_ref: TraitRef::new_from_args(cx, did, c.trait_ref.args),
854            polarity: c.polarity,
855        })
856        .upcast(cx)
857}
858
859impl<D, I> EvalCtxt<'_, D>
860where
861    D: SolverDelegate<Interner = I>,
862    I: Interner,
863{
864    /// Trait upcasting allows for coercions between trait objects:
865    /// ```ignore (builtin impl example)
866    /// trait Super {}
867    /// trait Trait: Super {}
868    /// // results in builtin impls upcasting to a super trait
869    /// impl<'a, 'b: 'a> Unsize<dyn Super + 'a> for dyn Trait + 'b {}
870    /// // and impls removing auto trait bounds.
871    /// impl<'a, 'b: 'a> Unsize<dyn Trait + 'a> for dyn Trait + Send + 'b {}
872    /// ```
873    fn consider_builtin_dyn_upcast_candidates(
874        &mut self,
875        goal: Goal<I, (I::Ty, I::Ty)>,
876        a_data: I::BoundExistentialPredicates,
877        a_region: I::Region,
878        b_data: I::BoundExistentialPredicates,
879        b_region: I::Region,
880    ) -> Vec<Candidate<I>> {
881        let cx = self.cx();
882        let Goal { predicate: (a_ty, _b_ty), .. } = goal;
883
884        let mut responses = vec![];
885        // If the principal def ids match (or are both none), then we're not doing
886        // trait upcasting. We're just removing auto traits (or shortening the lifetime).
887        let b_principal_def_id = b_data.principal_def_id();
888        if a_data.principal_def_id() == b_principal_def_id || b_principal_def_id.is_none() {
889            responses.extend(self.consider_builtin_upcast_to_principal(
890                goal,
891                CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
892                a_data,
893                a_region,
894                b_data,
895                b_region,
896                a_data.principal(),
897            ));
898        } else if let Some(a_principal) = a_data.principal() {
899            for (idx, new_a_principal) in
900                elaborate::supertraits(self.cx(), a_principal.with_self_ty(cx, a_ty))
901                    .enumerate()
902                    .skip(1)
903            {
904                responses.extend(self.consider_builtin_upcast_to_principal(
905                    goal,
906                    CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(idx)),
907                    a_data,
908                    a_region,
909                    b_data,
910                    b_region,
911                    Some(new_a_principal.map_bound(|trait_ref| {
912                        ty::ExistentialTraitRef::erase_self_ty(cx, trait_ref)
913                    })),
914                ));
915            }
916        }
917
918        responses
919    }
920
921    fn consider_builtin_unsize_to_dyn_candidate(
922        &mut self,
923        goal: Goal<I, (I::Ty, I::Ty)>,
924        b_data: I::BoundExistentialPredicates,
925        b_region: I::Region,
926    ) -> Result<Candidate<I>, NoSolution> {
927        let cx = self.cx();
928        let Goal { predicate: (a_ty, _), .. } = goal;
929
930        // Can only unsize to an dyn-compatible trait.
931        if b_data.principal_def_id().is_some_and(|def_id| !cx.trait_is_dyn_compatible(def_id)) {
932            return Err(NoSolution);
933        }
934
935        self.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
936            // Check that the type implements all of the predicates of the trait object.
937            // (i.e. the principal, all of the associated types match, and any auto traits)
938            ecx.add_goals(
939                GoalSource::ImplWhereBound,
940                b_data.iter().map(|pred| goal.with(cx, pred.with_self_ty(cx, a_ty))),
941            );
942
943            // The type must be `Sized` to be unsized.
944            ecx.add_goal(
945                GoalSource::ImplWhereBound,
946                goal.with(
947                    cx,
948                    ty::TraitRef::new(cx, cx.require_lang_item(TraitSolverLangItem::Sized), [a_ty]),
949                ),
950            );
951
952            // The type must outlive the lifetime of the `dyn` we're unsizing into.
953            ecx.add_goal(GoalSource::Misc, goal.with(cx, ty::OutlivesPredicate(a_ty, b_region)));
954            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
955        })
956    }
957
958    fn consider_builtin_upcast_to_principal(
959        &mut self,
960        goal: Goal<I, (I::Ty, I::Ty)>,
961        source: CandidateSource<I>,
962        a_data: I::BoundExistentialPredicates,
963        a_region: I::Region,
964        b_data: I::BoundExistentialPredicates,
965        b_region: I::Region,
966        upcast_principal: Option<ty::Binder<I, ty::ExistentialTraitRef<I>>>,
967    ) -> Result<Candidate<I>, NoSolution> {
968        let param_env = goal.param_env;
969
970        // We may upcast to auto traits that are either explicitly listed in
971        // the object type's bounds, or implied by the principal trait ref's
972        // supertraits.
973        let a_auto_traits: IndexSet<I::DefId> = a_data
974            .auto_traits()
975            .into_iter()
976            .chain(a_data.principal_def_id().into_iter().flat_map(|principal_def_id| {
977                elaborate::supertrait_def_ids(self.cx(), principal_def_id)
978                    .filter(|def_id| self.cx().trait_is_auto(*def_id))
979            }))
980            .collect();
981
982        // More than one projection in a_ty's bounds may match the projection
983        // in b_ty's bound. Use this to first determine *which* apply without
984        // having any inference side-effects. We process obligations because
985        // unification may initially succeed due to deferred projection equality.
986        let projection_may_match =
987            |ecx: &mut EvalCtxt<'_, D>,
988             source_projection: ty::Binder<I, ty::ExistentialProjection<I>>,
989             target_projection: ty::Binder<I, ty::ExistentialProjection<I>>| {
990                source_projection.item_def_id() == target_projection.item_def_id()
991                    && ecx
992                        .probe(|_| ProbeKind::ProjectionCompatibility)
993                        .enter(|ecx| -> Result<_, NoSolution> {
994                            ecx.enter_forall(target_projection, |ecx, target_projection| {
995                                let source_projection =
996                                    ecx.instantiate_binder_with_infer(source_projection);
997                                ecx.eq(param_env, source_projection, target_projection)?;
998                                ecx.try_evaluate_added_goals()
999                            })
1000                        })
1001                        .is_ok()
1002            };
1003
1004        self.probe_trait_candidate(source).enter(|ecx| {
1005            for bound in b_data.iter() {
1006                match bound.skip_binder() {
1007                    // Check that a's supertrait (upcast_principal) is compatible
1008                    // with the target (b_ty).
1009                    ty::ExistentialPredicate::Trait(target_principal) => {
1010                        let source_principal = upcast_principal.unwrap();
1011                        let target_principal = bound.rebind(target_principal);
1012                        ecx.enter_forall(target_principal, |ecx, target_principal| {
1013                            let source_principal =
1014                                ecx.instantiate_binder_with_infer(source_principal);
1015                            ecx.eq(param_env, source_principal, target_principal)?;
1016                            ecx.try_evaluate_added_goals()
1017                        })?;
1018                    }
1019                    // Check that b_ty's projection is satisfied by exactly one of
1020                    // a_ty's projections. First, we look through the list to see if
1021                    // any match. If not, error. Then, if *more* than one matches, we
1022                    // return ambiguity. Otherwise, if exactly one matches, equate
1023                    // it with b_ty's projection.
1024                    ty::ExistentialPredicate::Projection(target_projection) => {
1025                        let target_projection = bound.rebind(target_projection);
1026                        let mut matching_projections =
1027                            a_data.projection_bounds().into_iter().filter(|source_projection| {
1028                                projection_may_match(ecx, *source_projection, target_projection)
1029                            });
1030                        let Some(source_projection) = matching_projections.next() else {
1031                            return Err(NoSolution);
1032                        };
1033                        if matching_projections.next().is_some() {
1034                            return ecx.evaluate_added_goals_and_make_canonical_response(
1035                                Certainty::AMBIGUOUS,
1036                            );
1037                        }
1038                        ecx.enter_forall(target_projection, |ecx, target_projection| {
1039                            let source_projection =
1040                                ecx.instantiate_binder_with_infer(source_projection);
1041                            ecx.eq(param_env, source_projection, target_projection)?;
1042                            ecx.try_evaluate_added_goals()
1043                        })?;
1044                    }
1045                    // Check that b_ty's auto traits are present in a_ty's bounds.
1046                    ty::ExistentialPredicate::AutoTrait(def_id) => {
1047                        if !a_auto_traits.contains(&def_id) {
1048                            return Err(NoSolution);
1049                        }
1050                    }
1051                }
1052            }
1053
1054            // Also require that a_ty's lifetime outlives b_ty's lifetime.
1055            ecx.add_goal(
1056                GoalSource::ImplWhereBound,
1057                Goal::new(ecx.cx(), param_env, ty::OutlivesPredicate(a_region, b_region)),
1058            );
1059
1060            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
1061        })
1062    }
1063
1064    /// We have the following builtin impls for arrays:
1065    /// ```ignore (builtin impl example)
1066    /// impl<T: ?Sized, const N: usize> Unsize<[T]> for [T; N] {}
1067    /// ```
1068    /// While the impl itself could theoretically not be builtin,
1069    /// the actual unsizing behavior is builtin. Its also easier to
1070    /// make all impls of `Unsize` builtin as we're able to use
1071    /// `#[rustc_deny_explicit_impl]` in this case.
1072    fn consider_builtin_array_unsize(
1073        &mut self,
1074        goal: Goal<I, (I::Ty, I::Ty)>,
1075        a_elem_ty: I::Ty,
1076        b_elem_ty: I::Ty,
1077    ) -> Result<Candidate<I>, NoSolution> {
1078        self.eq(goal.param_env, a_elem_ty, b_elem_ty)?;
1079        self.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
1080            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
1081    }
1082
1083    /// We generate a builtin `Unsize` impls for structs with generic parameters only
1084    /// mentioned by the last field.
1085    /// ```ignore (builtin impl example)
1086    /// struct Foo<T, U: ?Sized> {
1087    ///     sized_field: Vec<T>,
1088    ///     unsizable: Box<U>,
1089    /// }
1090    /// // results in the following builtin impl
1091    /// impl<T: ?Sized, U: ?Sized, V: ?Sized> Unsize<Foo<T, V>> for Foo<T, U>
1092    /// where
1093    ///     Box<U>: Unsize<Box<V>>,
1094    /// {}
1095    /// ```
1096    fn consider_builtin_struct_unsize(
1097        &mut self,
1098        goal: Goal<I, (I::Ty, I::Ty)>,
1099        def: I::AdtDef,
1100        a_args: I::GenericArgs,
1101        b_args: I::GenericArgs,
1102    ) -> Result<Candidate<I>, NoSolution> {
1103        let cx = self.cx();
1104        let Goal { predicate: (_a_ty, b_ty), .. } = goal;
1105
1106        let unsizing_params = cx.unsizing_params_for_adt(def.def_id());
1107        // We must be unsizing some type parameters. This also implies
1108        // that the struct has a tail field.
1109        if unsizing_params.is_empty() {
1110            return Err(NoSolution);
1111        }
1112
1113        let tail_field_ty = def.struct_tail_ty(cx).unwrap();
1114
1115        let a_tail_ty = tail_field_ty.instantiate(cx, a_args);
1116        let b_tail_ty = tail_field_ty.instantiate(cx, b_args);
1117
1118        // Instantiate just the unsizing params from B into A. The type after
1119        // this instantiation must be equal to B. This is so we don't unsize
1120        // unrelated type parameters.
1121        let new_a_args = cx.mk_args_from_iter(a_args.iter().enumerate().map(|(i, a)| {
1122            if unsizing_params.contains(i as u32) { b_args.get(i).unwrap() } else { a }
1123        }));
1124        let unsized_a_ty = Ty::new_adt(cx, def, new_a_args);
1125
1126        // Finally, we require that `TailA: Unsize<TailB>` for the tail field
1127        // types.
1128        self.eq(goal.param_env, unsized_a_ty, b_ty)?;
1129        self.add_goal(
1130            GoalSource::ImplWhereBound,
1131            goal.with(
1132                cx,
1133                ty::TraitRef::new(
1134                    cx,
1135                    cx.require_lang_item(TraitSolverLangItem::Unsize),
1136                    [a_tail_ty, b_tail_ty],
1137                ),
1138            ),
1139        );
1140        self.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
1141            .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
1142    }
1143
1144    // Return `Some` if there is an impl (built-in or user provided) that may
1145    // hold for the self type of the goal, which for coherence and soundness
1146    // purposes must disqualify the built-in auto impl assembled by considering
1147    // the type's constituent types.
1148    fn disqualify_auto_trait_candidate_due_to_possible_impl(
1149        &mut self,
1150        goal: Goal<I, TraitPredicate<I>>,
1151    ) -> Option<Result<Candidate<I>, NoSolution>> {
1152        let self_ty = goal.predicate.self_ty();
1153        let check_impls = || {
1154            let mut disqualifying_impl = None;
1155            self.cx().for_each_relevant_impl(
1156                goal.predicate.def_id(),
1157                goal.predicate.self_ty(),
1158                |impl_def_id| {
1159                    disqualifying_impl = Some(impl_def_id);
1160                },
1161            );
1162            if let Some(def_id) = disqualifying_impl {
1163                trace!(?def_id, ?goal, "disqualified auto-trait implementation");
1164                // No need to actually consider the candidate here,
1165                // since we do that in `consider_impl_candidate`.
1166                return Some(Err(NoSolution));
1167            } else {
1168                None
1169            }
1170        };
1171
1172        match self_ty.kind() {
1173            // Stall int and float vars until they are resolved to a concrete
1174            // numerical type. That's because the check for impls below treats
1175            // int vars as matching any impl. Even if we filtered such impls,
1176            // we probably don't want to treat an `impl !AutoTrait for i32` as
1177            // disqualifying the built-in auto impl for `i64: AutoTrait` either.
1178            ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => {
1179                Some(self.forced_ambiguity(MaybeCause::Ambiguity))
1180            }
1181
1182            // Backward compatibility for default auto traits.
1183            // Test: ui/traits/default_auto_traits/extern-types.rs
1184            ty::Foreign(..) if self.cx().is_default_trait(goal.predicate.def_id()) => check_impls(),
1185
1186            // These types cannot be structurally decomposed into constituent
1187            // types, and therefore have no built-in auto impl.
1188            ty::Dynamic(..)
1189            | ty::Param(..)
1190            | ty::Foreign(..)
1191            | ty::Alias(ty::Projection | ty::Free | ty::Inherent, ..)
1192            | ty::Placeholder(..) => Some(Err(NoSolution)),
1193
1194            ty::Infer(_) | ty::Bound(_, _) => panic!("unexpected type `{self_ty:?}`"),
1195
1196            // Coroutines have one special built-in candidate, `Unpin`, which
1197            // takes precedence over the structural auto trait candidate being
1198            // assembled.
1199            ty::Coroutine(def_id, _)
1200                if self.cx().is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::Unpin) =>
1201            {
1202                match self.cx().coroutine_movability(def_id) {
1203                    Movability::Static => Some(Err(NoSolution)),
1204                    Movability::Movable => Some(
1205                        self.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
1206                            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
1207                        }),
1208                    ),
1209                }
1210            }
1211
1212            // If we still have an alias here, it must be rigid. For opaques, it's always
1213            // okay to consider auto traits because that'll reveal its hidden type. For
1214            // non-opaque aliases, we will not assemble any candidates since there's no way
1215            // to further look into its type.
1216            ty::Alias(..) => None,
1217
1218            // For rigid types, any possible implementation that could apply to
1219            // the type (even if after unification and processing nested goals
1220            // it does not hold) will disqualify the built-in auto impl.
1221            //
1222            // This differs from the current stable behavior and fixes #84857.
1223            // Due to breakage found via crater, we currently instead lint
1224            // patterns which can be used to exploit this unsoundness on stable,
1225            // see #93367 for more details.
1226            ty::Bool
1227            | ty::Char
1228            | ty::Int(_)
1229            | ty::Uint(_)
1230            | ty::Float(_)
1231            | ty::Str
1232            | ty::Array(_, _)
1233            | ty::Pat(_, _)
1234            | ty::Slice(_)
1235            | ty::RawPtr(_, _)
1236            | ty::Ref(_, _, _)
1237            | ty::FnDef(_, _)
1238            | ty::FnPtr(..)
1239            | ty::Closure(..)
1240            | ty::CoroutineClosure(..)
1241            | ty::Coroutine(_, _)
1242            | ty::CoroutineWitness(..)
1243            | ty::Never
1244            | ty::Tuple(_)
1245            | ty::Adt(_, _)
1246            | ty::UnsafeBinder(_) => check_impls(),
1247            ty::Error(_) => None,
1248        }
1249    }
1250
1251    /// Convenience function for traits that are structural, i.e. that only
1252    /// have nested subgoals that only change the self type. Unlike other
1253    /// evaluate-like helpers, this does a probe, so it doesn't need to be
1254    /// wrapped in one.
1255    fn probe_and_evaluate_goal_for_constituent_tys(
1256        &mut self,
1257        source: CandidateSource<I>,
1258        goal: Goal<I, TraitPredicate<I>>,
1259        constituent_tys: impl Fn(
1260            &EvalCtxt<'_, D>,
1261            I::Ty,
1262        ) -> Result<ty::Binder<I, Vec<I::Ty>>, NoSolution>,
1263    ) -> Result<Candidate<I>, NoSolution> {
1264        self.probe_trait_candidate(source).enter(|ecx| {
1265            let goals =
1266                ecx.enter_forall(constituent_tys(ecx, goal.predicate.self_ty())?, |ecx, tys| {
1267                    tys.into_iter()
1268                        .map(|ty| goal.with(ecx.cx(), goal.predicate.with_self_ty(ecx.cx(), ty)))
1269                        .collect::<Vec<_>>()
1270                });
1271            ecx.add_goals(GoalSource::ImplWhereBound, goals);
1272            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
1273        })
1274    }
1275}
1276
1277/// How we've proven this trait goal.
1278///
1279/// This is used by `NormalizesTo` goals to only normalize
1280/// by using the same 'kind of candidate' we've used to prove
1281/// its corresponding trait goal. Most notably, we do not
1282/// normalize by using an impl if the trait goal has been
1283/// proven via a `ParamEnv` candidate.
1284///
1285/// This is necessary to avoid unnecessary region constraints,
1286/// see trait-system-refactor-initiative#125 for more details.
1287#[derive(Debug, Clone, Copy)]
1288pub(super) enum TraitGoalProvenVia {
1289    /// We've proven the trait goal by something which is
1290    /// is not a non-global where-bound or an alias-bound.
1291    ///
1292    /// This means we don't disable any candidates during
1293    /// normalization.
1294    Misc,
1295    ParamEnv,
1296    AliasBound,
1297}
1298
1299impl<D, I> EvalCtxt<'_, D>
1300where
1301    D: SolverDelegate<Interner = I>,
1302    I: Interner,
1303{
1304    /// FIXME(#57893): For backwards compatibility with the old trait solver implementation,
1305    /// we need to handle overlap between builtin and user-written impls for trait objects.
1306    ///
1307    /// This overlap is unsound in general and something which we intend to fix separately.
1308    /// To avoid blocking the stabilization of the trait solver, we add this hack to avoid
1309    /// breakage in cases which are *mostly fine*™. Importantly, this preference is strictly
1310    /// weaker than the old behavior.
1311    ///
1312    /// We only prefer builtin over user-written impls if there are no inference constraints.
1313    /// Importantly, we also only prefer the builtin impls for trait goals, and not during
1314    /// normalization. This means the only case where this special-case results in exploitable
1315    /// unsoundness should be lifetime dependent user-written impls.
1316    pub(super) fn unsound_prefer_builtin_dyn_impl(&mut self, candidates: &mut Vec<Candidate<I>>) {
1317        match self.typing_mode() {
1318            TypingMode::Coherence => return,
1319            TypingMode::Analysis { .. }
1320            | TypingMode::Borrowck { .. }
1321            | TypingMode::PostBorrowckAnalysis { .. }
1322            | TypingMode::PostAnalysis => {}
1323        }
1324
1325        if candidates
1326            .iter()
1327            .find(|c| {
1328                matches!(c.source, CandidateSource::BuiltinImpl(BuiltinImplSource::Object(_)))
1329            })
1330            .is_some_and(|c| has_only_region_constraints(c.result))
1331        {
1332            candidates.retain(|c| {
1333                if matches!(c.source, CandidateSource::Impl(_)) {
1334                    debug!(?c, "unsoundly dropping impl in favor of builtin dyn-candidate");
1335                    false
1336                } else {
1337                    true
1338                }
1339            });
1340        }
1341    }
1342
1343    #[instrument(level = "debug", skip(self), ret)]
1344    pub(super) fn merge_trait_candidates(
1345        &mut self,
1346        mut candidates: Vec<Candidate<I>>,
1347    ) -> Result<(CanonicalResponse<I>, Option<TraitGoalProvenVia>), NoSolution> {
1348        if let TypingMode::Coherence = self.typing_mode() {
1349            let all_candidates: Vec<_> = candidates.into_iter().map(|c| c.result).collect();
1350            return if let Some(response) = self.try_merge_responses(&all_candidates) {
1351                Ok((response, Some(TraitGoalProvenVia::Misc)))
1352            } else {
1353                self.flounder(&all_candidates).map(|r| (r, None))
1354            };
1355        }
1356
1357        // We prefer trivial builtin candidates, i.e. builtin impls without any
1358        // nested requirements, over all others. This is a fix for #53123 and
1359        // prevents where-bounds from accidentally extending the lifetime of a
1360        // variable.
1361        let mut trivial_builtin_impls = candidates.iter().filter(|c| {
1362            matches!(c.source, CandidateSource::BuiltinImpl(BuiltinImplSource::Trivial))
1363        });
1364        if let Some(candidate) = trivial_builtin_impls.next() {
1365            // There should only ever be a single trivial builtin candidate
1366            // as they would otherwise overlap.
1367            assert!(trivial_builtin_impls.next().is_none());
1368            return Ok((candidate.result, Some(TraitGoalProvenVia::Misc)));
1369        }
1370
1371        // If there are non-global where-bounds, prefer where-bounds
1372        // (including global ones) over everything else.
1373        let has_non_global_where_bounds = candidates
1374            .iter()
1375            .any(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::NonGlobal)));
1376        if has_non_global_where_bounds {
1377            let where_bounds: Vec<_> = candidates
1378                .iter()
1379                .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
1380                .map(|c| c.result)
1381                .collect();
1382            return if let Some(response) = self.try_merge_responses(&where_bounds) {
1383                Ok((response, Some(TraitGoalProvenVia::ParamEnv)))
1384            } else {
1385                Ok((self.bail_with_ambiguity(&where_bounds), None))
1386            };
1387        }
1388
1389        if candidates.iter().any(|c| matches!(c.source, CandidateSource::AliasBound)) {
1390            let alias_bounds: Vec<_> = candidates
1391                .iter()
1392                .filter(|c| matches!(c.source, CandidateSource::AliasBound))
1393                .map(|c| c.result)
1394                .collect();
1395            return if let Some(response) = self.try_merge_responses(&alias_bounds) {
1396                Ok((response, Some(TraitGoalProvenVia::AliasBound)))
1397            } else {
1398                Ok((self.bail_with_ambiguity(&alias_bounds), None))
1399            };
1400        }
1401
1402        self.filter_specialized_impls(AllowInferenceConstraints::No, &mut candidates);
1403        self.unsound_prefer_builtin_dyn_impl(&mut candidates);
1404
1405        // If there are *only* global where bounds, then make sure to return that this
1406        // is still reported as being proven-via the param-env so that rigid projections
1407        // operate correctly. Otherwise, drop all global where-bounds before merging the
1408        // remaining candidates.
1409        let proven_via = if candidates
1410            .iter()
1411            .all(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)))
1412        {
1413            TraitGoalProvenVia::ParamEnv
1414        } else {
1415            candidates
1416                .retain(|c| !matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)));
1417            TraitGoalProvenVia::Misc
1418        };
1419
1420        let all_candidates: Vec<_> = candidates.into_iter().map(|c| c.result).collect();
1421        if let Some(response) = self.try_merge_responses(&all_candidates) {
1422            Ok((response, Some(proven_via)))
1423        } else {
1424            self.flounder(&all_candidates).map(|r| (r, None))
1425        }
1426    }
1427
1428    #[instrument(level = "trace", skip(self))]
1429    pub(super) fn compute_trait_goal(
1430        &mut self,
1431        goal: Goal<I, TraitPredicate<I>>,
1432    ) -> Result<(CanonicalResponse<I>, Option<TraitGoalProvenVia>), NoSolution> {
1433        let candidates = self.assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::All);
1434        self.merge_trait_candidates(candidates)
1435    }
1436
1437    fn try_stall_coroutine_witness(
1438        &mut self,
1439        self_ty: I::Ty,
1440    ) -> Option<Result<Candidate<I>, NoSolution>> {
1441        if let ty::CoroutineWitness(def_id, _) = self_ty.kind() {
1442            match self.typing_mode() {
1443                TypingMode::Analysis {
1444                    defining_opaque_types_and_generators: stalled_generators,
1445                } => {
1446                    if def_id.as_local().is_some_and(|def_id| stalled_generators.contains(&def_id))
1447                    {
1448                        return Some(self.forced_ambiguity(MaybeCause::Ambiguity));
1449                    }
1450                }
1451                TypingMode::Coherence
1452                | TypingMode::PostAnalysis
1453                | TypingMode::Borrowck { defining_opaque_types: _ }
1454                | TypingMode::PostBorrowckAnalysis { defined_opaque_types: _ } => {}
1455            }
1456        }
1457
1458        None
1459    }
1460}