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