Skip to main content

rustc_next_trait_solver/solve/assembly/
mod.rs

1//! Code shared by trait and projection goals for candidate assembly.
2
3pub(super) mod structural_traits;
4
5use std::cell::Cell;
6use std::ops::ControlFlow;
7
8use derive_where::derive_where;
9use rustc_type_ir::inherent::*;
10use rustc_type_ir::lang_items::SolverTraitLangItem;
11use rustc_type_ir::search_graph::CandidateHeadUsages;
12use rustc_type_ir::solve::{
13    AliasBoundKind, MaybeInfo, NoSolutionOrRerunNonErased, QueryResultOrRerunNonErased,
14    RerunNonErased, RerunReason, RerunResultExt, SizedTraitKind, StalledOnCoroutines,
15};
16use rustc_type_ir::{
17    self as ty, AliasTy, CallerBoundsIterator, Const, Interner, MayBeErased, Region, TypeFlags,
18    TypeFoldable, TypeFolder, TypeSuperFoldable, TypeSuperVisitable, TypeVisitable,
19    TypeVisitableExt, TypeVisitor, TypingMode, Unnormalized, Upcast, elaborate,
20};
21use tracing::{debug, instrument};
22
23use super::trait_goals::TraitGoalProvenVia;
24use super::{has_only_region_constraints, inspect};
25use crate::delegate::SolverDelegate;
26use crate::solve::assembly::structural_traits::NoUniqueSolutionOrRerunNonErased;
27use crate::solve::inspect::ProbeKind;
28use crate::solve::{
29    BuiltinImplSource, CandidateSource, CanonicalResponse, Certainty, EvalCtxt, Goal, GoalSource,
30    MaybeCause, NoSolution, OpaqueTypesJank, ParamEnvSource, QueryResult,
31    has_no_inference_or_external_constraints,
32};
33
34/// A candidate is a possible way to prove a goal.
35///
36/// It consists of both the `source`, which describes how that goal would be proven,
37/// and the `result` when using the given `source`.
38#[automatically_derived]
impl<I: Interner> ::core::fmt::Debug for Candidate<I> where I: Interner {
    fn fmt(&self, __f: &mut ::core::fmt::Formatter<'_>)
        -> ::core::fmt::Result {
        match self {
            Candidate {
                source: ref __field_source,
                result: ref __field_result,
                head_usages: ref __field_head_usages } => {
                let mut __builder =
                    ::core::fmt::Formatter::debug_struct(__f, "Candidate");
                ::core::fmt::DebugStruct::field(&mut __builder, "source",
                    __field_source);
                ::core::fmt::DebugStruct::field(&mut __builder, "result",
                    __field_result);
                ::core::fmt::DebugStruct::field(&mut __builder, "head_usages",
                    __field_head_usages);
                ::core::fmt::DebugStruct::finish(&mut __builder)
            }
        }
    }
}#[derive_where(Debug; I: Interner)]
39pub(super) struct Candidate<I: Interner> {
40    pub(super) source: CandidateSource<I>,
41    pub(super) result: CanonicalResponse<I>,
42    pub(super) head_usages: CandidateHeadUsages,
43}
44
45/// Methods used to assemble candidates for either trait or projection goals.
46pub(super) trait GoalKind<D, I = <D as SolverDelegate>::Interner>:
47    TypeFoldable<I> + Copy + Eq + std::fmt::Display
48where
49    D: SolverDelegate<Interner = I>,
50    I: Interner,
51{
52    fn self_ty(self) -> I::Ty;
53
54    fn trait_ref(self, cx: I) -> ty::TraitRef<I>;
55
56    fn with_replaced_self_ty(self, cx: I, self_ty: I::Ty) -> Self;
57
58    fn trait_def_id(self, cx: I) -> I::TraitId;
59
60    /// Consider a clause, which consists of a "assumption" and some "requirements",
61    /// to satisfy a goal. If the requirements hold, then attempt to satisfy our
62    /// goal by equating it with the assumption.
63    fn probe_and_consider_implied_clause(
64        ecx: &mut EvalCtxt<'_, D>,
65        parent_source: CandidateSource<I>,
66        goal: Goal<I, Self>,
67        assumption: I::Clause,
68        requirements: impl IntoIterator<Item = (GoalSource, Goal<I, I::Predicate>)>,
69    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased> {
70        Self::probe_and_match_goal_against_assumption(ecx, parent_source, goal, assumption, |ecx| {
71            for (nested_source, goal) in requirements {
72                ecx.add_goal(nested_source, goal)?;
73            }
74            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
75        })
76    }
77
78    /// Consider a clause specifically for a `dyn Trait` self type. This requires
79    /// additionally checking all of the supertraits and object bounds to hold,
80    /// since they're not implied by the well-formedness of the object type.
81    /// `NormalizesTo` overrides this to not check the supertraits for backwards
82    /// compatibility with the old solver. cc trait-system-refactor-initiative#245.
83    fn probe_and_consider_object_bound_candidate(
84        ecx: &mut EvalCtxt<'_, D>,
85        source: CandidateSource<I>,
86        goal: Goal<I, Self>,
87        assumption: I::Clause,
88    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased> {
89        // We inline much of `probe_and_match_goal_against_assumption` and
90        // `TraitPredicate::match_assumption` here, as we never encounter
91        // `Sized` or `MetaSized` goals here, and we need to equate `goal`
92        // and `assumption`'s trait refs directly inside this function in
93        // order to prevent unsoundness (see below).
94
95        let goal_lang_item = ecx.cx().as_trait_lang_item(goal.predicate.trait_def_id(ecx.cx()));
96        Self::fast_reject_assumption(ecx, goal, goal_lang_item, assumption)?;
97
98        ecx.probe_trait_candidate(source).enter(|ecx| {
99            let cx = ecx.cx();
100            let ty::Dynamic(bounds, _) = goal.predicate.self_ty().kind() else {
101                {
    ::core::panicking::panic_fmt(format_args!("expected object type in `probe_and_consider_object_bound_candidate`"));
};panic!("expected object type in `probe_and_consider_object_bound_candidate`");
102            };
103
104            let trait_ref = assumption.kind().map_bound(|clause| match clause {
105                ty::ClauseKind::Trait(pred) => pred.trait_ref,
106                ty::ClauseKind::Projection(proj) => proj.projection_term.trait_ref(cx),
107
108                ty::ClauseKind::RegionOutlives(..)
109                | ty::ClauseKind::TypeOutlives(..)
110                | ty::ClauseKind::ConstArgHasType(..)
111                | ty::ClauseKind::WellFormed(..)
112                | ty::ClauseKind::ConstEvaluatable(..)
113                | ty::ClauseKind::HostEffect(..)
114                | ty::ClauseKind::UnstableFeature(..) => {
115                    {
    ::core::panicking::panic_fmt(format_args!("internal error: entered unreachable code: {0}",
            format_args!("expected trait or projection predicate as an assumption")));
}unreachable!("expected trait or projection predicate as an assumption")
116                }
117            });
118
119            // If we need to prove `dyn for<'x> Trait<'x> + '?temp: Trait<'static>` with
120            //
121            // ```rs
122            // trait Trait<'a>: 'a {}
123            // ```
124            //
125            // we have the goal's trait ref as `Trait<'static>` and a theoretical impl
126            // resembling:
127            //
128            // ```rs
129            // impl<'s, 'hr> Trait<'hr> for dyn for<'x> Trait<'x> + 's
130            // where
131            //     dyn for<'a> Trait<'a> + 's: 'hr
132            // {}
133            // ```
134            //
135            // where 'hr is our bound var. The where-clause elaborates to `'s: 'hr`;
136            // in this case we have 's := '?temp. Instantiating the binder gives us
137            // 'hr := '?infer, and our goal has 'hr := 'static, so we need to equate
138            // the instantiated trait ref to the goal in order to get '?infer := 'static,
139            // since what we want is the constraint `'?temp: 'static`.
140            //
141            // If we instead passed the binder to predicates_for_object_candidate and let
142            // it instantiate the binder itself, we would lose '?infer := 'static, since
143            // predicates_for_object_candidate has no way of equating the trait ref with
144            // the goal. We would simply have 'hr := '?infer, giving us the constraint
145            // `?temp: '?infer`, which is satisfiable for any lifetime, leading to
146            // unsoundness: trait-system-refactor-initiative#295.
147            let trait_ref = ecx.instantiate_binder_with_infer(trait_ref);
148            ecx.eq(goal.param_env, goal.predicate.trait_ref(cx), trait_ref)?;
149
150            match structural_traits::predicates_for_object_candidate(
151                ecx,
152                goal.param_env,
153                trait_ref,
154                bounds,
155            ) {
156                Ok(requirements) => {
157                    ecx.add_goals(GoalSource::ImplWhereBound, requirements)?;
158                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
159                }
160                Err(NoUniqueSolutionOrRerunNonErased::Ambiguous) => {
161                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
162                }
163                Err(NoUniqueSolutionOrRerunNonErased::NoSolution(no_solution)) => {
164                    Err(no_solution.into())
165                }
166                Err(NoUniqueSolutionOrRerunNonErased::RerunNonErased(rerun)) => Err(rerun.into()),
167            }
168        })
169    }
170
171    /// Assemble additional assumptions for an alias that are not included
172    /// in the item bounds of the alias. For now, this is limited to the
173    /// `explicit_implied_const_bounds` for an associated type.
174    fn consider_additional_alias_assumptions(
175        ecx: &mut EvalCtxt<'_, D>,
176        goal: Goal<I, Self>,
177        alias_ty: ty::AliasTy<I>,
178    ) -> Vec<Candidate<I>>;
179
180    fn probe_and_consider_param_env_candidate(
181        ecx: &mut EvalCtxt<'_, D>,
182        goal: Goal<I, Self>,
183        assumption: I::Clause,
184    ) -> Result<Result<Candidate<I>, CandidateHeadUsages>, RerunNonErased> {
185        // Dealing with `ParamEnv` candidates is a bit of a mess as we need to lazily
186        // check whether the candidate is global while considering normalization.
187        //
188        // We need to write into `source` inside of `match_assumption`, but need to access it
189        // in `probe` even if the candidate does not apply before we get there. We handle this
190        // by using a `Cell` here. We only ever write into it inside of `match_assumption`.
191        let source = Cell::new(CandidateSource::ParamEnv(ParamEnvSource::Global));
192        let (result, head_usages) = ecx
193            .probe(|result: &QueryResult<I>| inspect::ProbeKind::TraitCandidate {
194                source: source.get(),
195                result: *result,
196            })
197            .enter_single_candidate(|ecx| {
198                Self::match_assumption(
199                    ecx,
200                    goal,
201                    assumption,
202                    |ecx| -> Result<_, NoSolutionOrRerunNonErased> {
203                        ecx.try_evaluate_added_goals()?;
204                        let (src, certainty) =
205                            ecx.characterize_param_env_assumption(goal.param_env, assumption)?;
206                        source.set(src);
207                        ecx.evaluate_added_goals_and_make_canonical_response(certainty)
208                    },
209                )
210            });
211
212        Ok(match result.map_err_to_rerun()? {
213            Ok(result) => Ok(Candidate { source: source.get(), result, head_usages }),
214            Err(NoSolution) => Err(head_usages),
215        })
216    }
217
218    /// Try equating an assumption predicate against a goal's predicate. If it
219    /// holds, then execute the `then` callback, which should do any additional
220    /// work, then produce a response (typically by executing
221    /// [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]).
222    fn probe_and_match_goal_against_assumption(
223        ecx: &mut EvalCtxt<'_, D>,
224        source: CandidateSource<I>,
225        goal: Goal<I, Self>,
226        assumption: I::Clause,
227        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResultOrRerunNonErased<I>,
228    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased> {
229        let goal_lang_item = ecx.cx().as_trait_lang_item(goal.predicate.trait_def_id(ecx.cx()));
230        Self::fast_reject_assumption(ecx, goal, goal_lang_item, assumption)?;
231
232        ecx.probe_trait_candidate(source)
233            .enter(|ecx| Self::match_assumption(ecx, goal, assumption, then))
234    }
235
236    /// Try to reject the assumption based off of simple heuristics, such as [`ty::ClauseKind`]
237    /// and `DefId`.
238    fn fast_reject_assumption(
239        ecx: &mut EvalCtxt<'_, D>,
240        goal: Goal<I, Self>,
241        goal_lang_item: Option<SolverTraitLangItem>,
242        assumption: I::Clause,
243    ) -> Result<(), NoSolution>;
244
245    /// Relate the goal and assumption.
246    fn match_assumption(
247        ecx: &mut EvalCtxt<'_, D>,
248        goal: Goal<I, Self>,
249        assumption: I::Clause,
250        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResultOrRerunNonErased<I>,
251    ) -> QueryResultOrRerunNonErased<I>;
252
253    /// Note: `goal_trait_ref` is derived from `goal`. Nonetheless, because
254    /// `consider_impl_candidate` is always called in a loop, we precompute `goal_trait_ref` once
255    /// and pass it in next to `goal` because the computation is expensive and loop-invariant.
256    fn consider_impl_candidate(
257        ecx: &mut EvalCtxt<'_, D>,
258        goal: Goal<I, Self>,
259        goal_trait_ref: ty::TraitRef<I>,
260        impl_def_id: I::ImplId,
261        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResultOrRerunNonErased<I>,
262    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
263
264    /// If the predicate contained an error, we want to avoid emitting unnecessary trait
265    /// errors but still want to emit errors for other trait goals. We have some special
266    /// handling for this case.
267    ///
268    /// Trait goals always hold while projection goals never do. This is a bit arbitrary
269    /// but prevents incorrect normalization while hiding any trait errors.
270    fn consider_error_guaranteed_candidate(
271        ecx: &mut EvalCtxt<'_, D>,
272        goal: Goal<I, Self>,
273        guar: I::ErrorGuaranteed,
274    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
275
276    /// A type implements an `auto trait` if its components do as well.
277    ///
278    /// These components are given by built-in rules from
279    /// [`structural_traits::instantiate_constituent_tys_for_auto_trait`].
280    fn consider_auto_trait_candidate(
281        ecx: &mut EvalCtxt<'_, D>,
282        goal: Goal<I, Self>,
283    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
284
285    /// A trait alias holds if the RHS traits and `where` clauses hold.
286    fn consider_trait_alias_candidate(
287        ecx: &mut EvalCtxt<'_, D>,
288        goal: Goal<I, Self>,
289    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
290
291    /// A type is `Sized` if its tail component is `Sized` and a type is `MetaSized` if its tail
292    /// component is `MetaSized`.
293    ///
294    /// These components are given by built-in rules from
295    /// [`structural_traits::instantiate_constituent_tys_for_sizedness_trait`].
296    fn consider_builtin_sizedness_candidates(
297        ecx: &mut EvalCtxt<'_, D>,
298        goal: Goal<I, Self>,
299        sizedness: SizedTraitKind,
300    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
301
302    /// A type is `Copy` or `Clone` if its components are `Copy` or `Clone`.
303    ///
304    /// These components are given by built-in rules from
305    /// [`structural_traits::instantiate_constituent_tys_for_copy_clone_trait`].
306    fn consider_builtin_copy_clone_candidate(
307        ecx: &mut EvalCtxt<'_, D>,
308        goal: Goal<I, Self>,
309    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
310
311    /// A type is a `FnPtr` if it is of `FnPtr` type.
312    fn consider_builtin_fn_ptr_trait_candidate(
313        ecx: &mut EvalCtxt<'_, D>,
314        goal: Goal<I, Self>,
315    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
316
317    /// A type is a `FnStatic` if it is of `FnDef` type.
318    fn consider_builtin_fn_static_trait_candidate(
319        ecx: &mut EvalCtxt<'_, D>,
320        goal: Goal<I, Self>,
321    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
322
323    /// A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
324    /// family of traits where `A` is given by the signature of the type.
325    fn consider_builtin_fn_trait_candidates(
326        ecx: &mut EvalCtxt<'_, D>,
327        goal: Goal<I, Self>,
328        kind: ty::ClosureKind,
329    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
330
331    /// An async closure is known to implement the `AsyncFn<A>` family of traits
332    /// where `A` is given by the signature of the type.
333    fn consider_builtin_async_fn_trait_candidates(
334        ecx: &mut EvalCtxt<'_, D>,
335        goal: Goal<I, Self>,
336        kind: ty::ClosureKind,
337    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
338
339    /// Compute the built-in logic of the `AsyncFnKindHelper` helper trait, which
340    /// is used internally to delay computation for async closures until after
341    /// upvar analysis is performed in HIR typeck.
342    fn consider_builtin_async_fn_kind_helper_candidate(
343        ecx: &mut EvalCtxt<'_, D>,
344        goal: Goal<I, Self>,
345    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
346
347    /// `Tuple` is implemented if the `Self` type is a tuple.
348    fn consider_builtin_tuple_candidate(
349        ecx: &mut EvalCtxt<'_, D>,
350        goal: Goal<I, Self>,
351    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
352
353    /// `Pointee` is always implemented.
354    ///
355    /// See the projection implementation for the `Metadata` types for all of
356    /// the built-in types. For structs, the metadata type is given by the struct
357    /// tail.
358    fn consider_builtin_pointee_candidate(
359        ecx: &mut EvalCtxt<'_, D>,
360        goal: Goal<I, Self>,
361    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
362
363    /// A coroutine (that comes from an `async` desugaring) is known to implement
364    /// `Future<Output = O>`, where `O` is given by the coroutine's return type
365    /// that was computed during type-checking.
366    fn consider_builtin_future_candidate(
367        ecx: &mut EvalCtxt<'_, D>,
368        goal: Goal<I, Self>,
369    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
370
371    /// A coroutine (that comes from a `gen` desugaring) is known to implement
372    /// `Iterator<Item = O>`, where `O` is given by the generator's yield type
373    /// that was computed during type-checking.
374    fn consider_builtin_iterator_candidate(
375        ecx: &mut EvalCtxt<'_, D>,
376        goal: Goal<I, Self>,
377    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
378
379    /// A coroutine (that comes from a `gen` desugaring) is known to implement
380    /// `FusedIterator`
381    fn consider_builtin_fused_iterator_candidate(
382        ecx: &mut EvalCtxt<'_, D>,
383        goal: Goal<I, Self>,
384    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
385
386    fn consider_builtin_async_iterator_candidate(
387        ecx: &mut EvalCtxt<'_, D>,
388        goal: Goal<I, Self>,
389    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
390
391    /// A coroutine (that doesn't come from an `async` or `gen` desugaring) is known to
392    /// implement `Coroutine<R, Yield = Y, Return = O>`, given the resume, yield,
393    /// and return types of the coroutine computed during type-checking.
394    fn consider_builtin_coroutine_candidate(
395        ecx: &mut EvalCtxt<'_, D>,
396        goal: Goal<I, Self>,
397    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
398
399    fn consider_builtin_discriminant_kind_candidate(
400        ecx: &mut EvalCtxt<'_, D>,
401        goal: Goal<I, Self>,
402    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
403
404    fn consider_builtin_destruct_candidate(
405        ecx: &mut EvalCtxt<'_, D>,
406        goal: Goal<I, Self>,
407    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
408
409    fn consider_builtin_transmute_candidate(
410        ecx: &mut EvalCtxt<'_, D>,
411        goal: Goal<I, Self>,
412    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
413
414    fn consider_builtin_bikeshed_guaranteed_no_drop_candidate(
415        ecx: &mut EvalCtxt<'_, D>,
416        goal: Goal<I, Self>,
417    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
418
419    fn consider_builtin_try_as_dyn_candidate(
420        ecx: &mut EvalCtxt<'_, D>,
421        goal: Goal<I, Self>,
422    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
423
424    /// Consider (possibly several) candidates to upcast or unsize a type to another
425    /// type, excluding the coercion of a sized type into a `dyn Trait`.
426    ///
427    /// We return the `BuiltinImplSource` for each candidate as it is needed
428    /// for unsize coercion in hir typeck and because it is difficult to
429    /// otherwise recompute this for codegen. This is a bit of a mess but the
430    /// easiest way to maintain the existing behavior for now.
431    fn consider_structural_builtin_unsize_candidates(
432        ecx: &mut EvalCtxt<'_, D>,
433        goal: Goal<I, Self>,
434    ) -> Result<Vec<Candidate<I>>, RerunNonErased>;
435
436    fn consider_builtin_field_candidate(
437        ecx: &mut EvalCtxt<'_, D>,
438        goal: Goal<I, Self>,
439    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased>;
440}
441
442/// Allows callers of `assemble_and_evaluate_candidates` to choose whether to limit
443/// candidate assembly to param-env and alias-bound candidates.
444///
445/// On top of being a micro-optimization, as it avoids doing unnecessary work when
446/// a param-env trait bound candidate shadows impls for normalization, this is also
447/// required to prevent query cycles due to RPITIT inference. See the issue at:
448/// <https://github.com/rust-lang/trait-system-refactor-initiative/issues/173>.
449pub(super) enum AssembleCandidatesFrom {
450    All,
451    /// Only assemble candidates from the environment and alias bounds, ignoring
452    /// user-written and built-in impls. We only expect `ParamEnv` and `AliasBound`
453    /// candidates to be assembled.
454    EnvAndBounds,
455}
456
457impl AssembleCandidatesFrom {
458    fn should_assemble_impl_candidates(&self) -> bool {
459        match self {
460            AssembleCandidatesFrom::All => true,
461            AssembleCandidatesFrom::EnvAndBounds => false,
462        }
463    }
464}
465
466/// This is currently used to track the [CandidateHeadUsages] of all failed `ParamEnv`
467/// candidates. This is then used to ignore their head usages in case there's another
468/// always applicable `ParamEnv` candidate. Look at how `param_env_head_usages` is
469/// used in the code for more details.
470///
471/// We could easily extend this to also ignore head usages of other ignored candidates.
472/// However, we currently don't have any tests where this matters and the complexity of
473/// doing so does not feel worth it for now.
474#[derive(#[automatically_derived]impl ::core::fmt::Debug for FailedCandidateInfo {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field1_finish(f,
            "FailedCandidateInfo param_env_head_usages",
            &&self.param_env_head_usages)
    }
}Debug)]
475pub(super) struct FailedCandidateInfo {
476    pub param_env_head_usages: CandidateHeadUsages,
477}
478
479impl<D, I> EvalCtxt<'_, D>
480where
481    D: SolverDelegate<Interner = I>,
482    I: Interner,
483{
484    // FIXME(#155443): This function should only ever return an error
485    // as we want to force a rerun when accessing opaques. We should change
486    // this file to revert all the newly added places which return `NoSolution`.
487    pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<D>>(
488        &mut self,
489        goal: Goal<I, G>,
490        assemble_from: AssembleCandidatesFrom,
491    ) -> Result<(Vec<Candidate<I>>, FailedCandidateInfo), RerunNonErased> {
492        let mut candidates = ::alloc::vec::Vec::new()vec![];
493        let mut failed_candidate_info =
494            FailedCandidateInfo { param_env_head_usages: CandidateHeadUsages::default() };
495        let Ok(normalized_self_ty) =
496            self.structurally_normalize_ty(goal.param_env, goal.predicate.self_ty())
497        else {
498            return Ok((candidates, failed_candidate_info));
499        };
500
501        let goal: Goal<I, G> = goal
502            .with(self.cx(), goal.predicate.with_replaced_self_ty(self.cx(), normalized_self_ty));
503
504        if normalized_self_ty.is_ty_var() {
505            {
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event /rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs:505",
                        "rustc_next_trait_solver::solve::assembly",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(505u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                        ::tracing_core::field::FieldSet::new(&["message"],
                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("self type has been normalized to infer")
                                            as &dyn ::tracing::field::Value))])
            });
    } else { ; }
};debug!("self type has been normalized to infer");
506            self.try_assemble_bounds_via_registered_opaques(goal, assemble_from, &mut candidates)?;
507            return Ok((candidates, failed_candidate_info));
508        }
509
510        // Vars that show up in the rest of the goal substs may have been constrained by
511        // normalizing the self type as well, since type variables are not uniquified.
512        let goal = self.deeply_resolve_ignoring_regions(goal);
513
514        if self.typing_mode().is_coherence()
515            && let Ok(candidate) = self.consider_coherence_unknowable_candidate(goal)
516        {
517            candidates.push(candidate);
518            return Ok((candidates, failed_candidate_info));
519        }
520
521        self.assemble_alias_bound_candidates(goal, &mut candidates)?;
522        self.assemble_param_env_candidates(goal, &mut candidates, &mut failed_candidate_info)?;
523
524        match assemble_from {
525            AssembleCandidatesFrom::All => {
526                self.assemble_builtin_impl_candidates(goal, &mut candidates)?;
527                // For performance we only assemble impls if there are no candidates
528                // which would shadow them. This is necessary to avoid hangs in rayon,
529                // see trait-system-refactor-initiative#109 for more details.
530                //
531                // We always assemble builtin impls as trivial builtin impls have a higher
532                // priority than where-clauses.
533                //
534                // We only do this if any such candidate applies without any constraints
535                // as we may want to weaken inference guidance in the future and don't want
536                // to worry about causing major performance regressions when doing so.
537                // See trait-system-refactor-initiative#226 for some ideas here.
538                let assemble_impls = match self.typing_mode() {
539                    TypingMode::Coherence => true,
540                    TypingMode::Typeck { .. }
541                    | TypingMode::PostTypeckThroughBorrowck { .. }
542                    | TypingMode::Reflection
543                    | TypingMode::PostBorrowck { .. }
544                    | TypingMode::PostAnalysis
545                    | TypingMode::Codegen
546                    | TypingMode::ErasedNotCoherence(MayBeErased) => !candidates.iter().any(|c| {
547                        #[allow(non_exhaustive_omitted_patterns)] match c.source {
    CandidateSource::ParamEnv(ParamEnvSource::NonGlobal) |
        CandidateSource::AliasBound(_) => true,
    _ => false,
}matches!(
548                            c.source,
549                            CandidateSource::ParamEnv(ParamEnvSource::NonGlobal)
550                                | CandidateSource::AliasBound(_)
551                        ) && has_no_inference_or_external_constraints(c.result)
552                    }),
553                };
554                if assemble_impls {
555                    self.assemble_impl_candidates(goal, &mut candidates)?;
556                    self.assemble_object_bound_candidates(goal, &mut candidates);
557                }
558            }
559            AssembleCandidatesFrom::EnvAndBounds => {
560                // This is somewhat inconsistent and may make #57893 slightly easier to exploit.
561                // However, it matches the behavior of the old solver. See
562                // `tests/ui/traits/next-solver/normalization-shadowing/use_object_if_empty_env.rs`.
563                if #[allow(non_exhaustive_omitted_patterns)] match normalized_self_ty.kind() {
    ty::Dynamic(..) => true,
    _ => false,
}matches!(normalized_self_ty.kind(), ty::Dynamic(..))
564                    && !candidates.iter().any(|c| #[allow(non_exhaustive_omitted_patterns)] match c.source {
    CandidateSource::ParamEnv(_) => true,
    _ => false,
}matches!(c.source, CandidateSource::ParamEnv(_)))
565                {
566                    self.assemble_object_bound_candidates(goal, &mut candidates);
567                }
568            }
569        }
570
571        Ok((candidates, failed_candidate_info))
572    }
573
574    pub(super) fn forced_ambiguity(
575        &mut self,
576        maybe: MaybeInfo,
577    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased> {
578        // This may fail if `try_evaluate_added_goals` overflows because it
579        // fails to reach a fixpoint but ends up getting an error after
580        // running for some additional step.
581        //
582        // FIXME(@lcnr): While I believe an error here to be possible, we
583        // currently don't have any test which actually triggers it. @lqd
584        // created a minimization for an ICE in typenum, but that one no
585        // longer fails here. cc trait-system-refactor-initiative#105.
586        let source = CandidateSource::BuiltinImpl(BuiltinImplSource::Misc);
587        let certainty = Certainty::Maybe(maybe);
588        self.probe_trait_candidate(source)
589            .enter(|this| this.evaluate_added_goals_and_make_canonical_response(certainty))
590    }
591
592    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::TRACE <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::TRACE <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("assemble_impl_candidates",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::TRACE,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(592u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[],
                                        ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{ meta.fields().value_set_all(&[]) })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return: Result<(), RerunNonErased> =
                loop {};
            return __tracing_attr_fake_return;
        }
        {
            let cx = self.cx();
            let goal_trait_ref = goal.predicate.trait_ref(cx);
            cx.for_each_relevant_impl(goal_trait_ref,
                |impl_def_id| -> Result<_, _>
                    {
                        match G::consider_impl_candidate(self, goal, goal_trait_ref,
                                        impl_def_id,
                                        |ecx|
                                            {
                                                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                                            }).map_err_to_rerun()? {
                            Ok(candidate) => candidates.push(candidate),
                            Err(NoSolution) => {}
                        }
                        Ok(())
                    })
        }
    }
}#[instrument(level = "trace", skip_all)]
593    fn assemble_impl_candidates<G: GoalKind<D>>(
594        &mut self,
595        goal: Goal<I, G>,
596        candidates: &mut Vec<Candidate<I>>,
597    ) -> Result<(), RerunNonErased> {
598        let cx = self.cx();
599        let goal_trait_ref = goal.predicate.trait_ref(cx);
600        cx.for_each_relevant_impl(goal_trait_ref, |impl_def_id| -> Result<_, _> {
601            match G::consider_impl_candidate(self, goal, goal_trait_ref, impl_def_id, |ecx| {
602                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
603            })
604            .map_err_to_rerun()?
605            {
606                Ok(candidate) => candidates.push(candidate),
607                Err(NoSolution) => {}
608            }
609
610            Ok(())
611        })
612    }
613
614    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::TRACE <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::TRACE <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("assemble_builtin_impl_candidates",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::TRACE,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(614u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[],
                                        ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{ meta.fields().value_set_all(&[]) })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return: Result<(), RerunNonErased> =
                loop {};
            return __tracing_attr_fake_return;
        }
        {
            let cx = self.cx();
            let trait_def_id = goal.predicate.trait_def_id(cx);
            if self.typing_mode().is_reflection() { return Ok(()); }
            let result =
                if let ty::Error(guar) = goal.predicate.self_ty().kind() {
                    G::consider_error_guaranteed_candidate(self, goal, guar)
                } else if cx.trait_is_auto(trait_def_id) {
                    G::consider_auto_trait_candidate(self, goal)
                } else if cx.trait_is_alias(trait_def_id) {
                    G::consider_trait_alias_candidate(self, goal)
                } else {
                    match cx.as_trait_lang_item(trait_def_id) {
                        Some(SolverTraitLangItem::Sized) => {
                            G::consider_builtin_sizedness_candidates(self, goal,
                                SizedTraitKind::Sized)
                        }
                        Some(SolverTraitLangItem::MetaSized) => {
                            G::consider_builtin_sizedness_candidates(self, goal,
                                SizedTraitKind::MetaSized)
                        }
                        Some(SolverTraitLangItem::PointeeSized) => {
                            {
                                ::core::panicking::panic_fmt(format_args!("internal error: entered unreachable code: {0}",
                                        format_args!("`PointeeSized` is removed during lowering")));
                            };
                        }
                        Some(SolverTraitLangItem::Copy | SolverTraitLangItem::Clone
                            | SolverTraitLangItem::TrivialClone) =>
                            G::consider_builtin_copy_clone_candidate(self, goal),
                        Some(SolverTraitLangItem::Fn) => {
                            G::consider_builtin_fn_trait_candidates(self, goal,
                                ty::ClosureKind::Fn)
                        }
                        Some(SolverTraitLangItem::FnMut) => {
                            G::consider_builtin_fn_trait_candidates(self, goal,
                                ty::ClosureKind::FnMut)
                        }
                        Some(SolverTraitLangItem::FnOnce) => {
                            G::consider_builtin_fn_trait_candidates(self, goal,
                                ty::ClosureKind::FnOnce)
                        }
                        Some(SolverTraitLangItem::AsyncFn) => {
                            G::consider_builtin_async_fn_trait_candidates(self, goal,
                                ty::ClosureKind::Fn)
                        }
                        Some(SolverTraitLangItem::AsyncFnMut) => {
                            G::consider_builtin_async_fn_trait_candidates(self, goal,
                                ty::ClosureKind::FnMut)
                        }
                        Some(SolverTraitLangItem::AsyncFnOnce) => {
                            G::consider_builtin_async_fn_trait_candidates(self, goal,
                                ty::ClosureKind::FnOnce)
                        }
                        Some(SolverTraitLangItem::FnPtrTrait) => {
                            G::consider_builtin_fn_ptr_trait_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::FnAddrTrait) => {
                            if #[allow(non_exhaustive_omitted_patterns)] match goal.predicate.self_ty().kind()
                                    {
                                    ty::FnDef(..) => true,
                                    _ => false,
                                } {
                                G::consider_builtin_fn_static_trait_candidate(self, goal)
                            } else {
                                G::consider_builtin_fn_ptr_trait_candidate(self, goal)
                            }
                        }
                        Some(SolverTraitLangItem::AsyncFnKindHelper) => {
                            G::consider_builtin_async_fn_kind_helper_candidate(self,
                                goal)
                        }
                        Some(SolverTraitLangItem::Tuple) =>
                            G::consider_builtin_tuple_candidate(self, goal),
                        Some(SolverTraitLangItem::PointeeTrait) => {
                            G::consider_builtin_pointee_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::Future) => {
                            G::consider_builtin_future_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::Iterator) => {
                            G::consider_builtin_iterator_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::FusedIterator) => {
                            G::consider_builtin_fused_iterator_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::AsyncIterator) => {
                            G::consider_builtin_async_iterator_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::Coroutine) => {
                            G::consider_builtin_coroutine_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::DiscriminantKind) => {
                            G::consider_builtin_discriminant_kind_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::Destruct) => {
                            G::consider_builtin_destruct_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::TransmuteTrait) => {
                            G::consider_builtin_transmute_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::BikeshedGuaranteedNoDrop) => {
                            G::consider_builtin_bikeshed_guaranteed_no_drop_candidate(self,
                                goal)
                        }
                        Some(SolverTraitLangItem::TryAsDyn) => {
                            G::consider_builtin_try_as_dyn_candidate(self, goal)
                        }
                        Some(SolverTraitLangItem::Field) =>
                            G::consider_builtin_field_candidate(self, goal),
                        _ => Err(NoSolution.into()),
                    }
                };
            candidates.extend(result);
            if cx.is_trait_lang_item(trait_def_id,
                    SolverTraitLangItem::Unsize) {
                candidates.extend(G::consider_structural_builtin_unsize_candidates(self,
                            goal)?);
            }
            Ok(())
        }
    }
}#[instrument(level = "trace", skip_all)]
615    fn assemble_builtin_impl_candidates<G: GoalKind<D>>(
616        &mut self,
617        goal: Goal<I, G>,
618        candidates: &mut Vec<Candidate<I>>,
619    ) -> Result<(), RerunNonErased> {
620        let cx = self.cx();
621        let trait_def_id = goal.predicate.trait_def_id(cx);
622
623        // Builtin impls regularly are not `is_fully_generic_for_reflection`, so instead
624        // of trying to handle these manually, we just reject all builtin impls in reflection
625        // mode. We can probably lift this restriction for specific cases, but this is safer.
626        // See `try_as_dyn_builtin_impl` for how just allowing all builtin impls is unsound.
627        if self.typing_mode().is_reflection() {
628            return Ok(());
629        }
630
631        // N.B. When assembling built-in candidates for lang items that are also
632        // `auto` traits, then the auto trait candidate that is assembled in
633        // `consider_auto_trait_candidate` MUST be disqualified to remain sound.
634        //
635        // Instead of adding the logic here, it's a better idea to add it in
636        // `EvalCtxt::disqualify_auto_trait_candidate_due_to_possible_impl` in
637        // `solve::trait_goals` instead.
638        let result = if let ty::Error(guar) = goal.predicate.self_ty().kind() {
639            G::consider_error_guaranteed_candidate(self, goal, guar)
640        } else if cx.trait_is_auto(trait_def_id) {
641            G::consider_auto_trait_candidate(self, goal)
642        } else if cx.trait_is_alias(trait_def_id) {
643            G::consider_trait_alias_candidate(self, goal)
644        } else {
645            match cx.as_trait_lang_item(trait_def_id) {
646                Some(SolverTraitLangItem::Sized) => {
647                    G::consider_builtin_sizedness_candidates(self, goal, SizedTraitKind::Sized)
648                }
649                Some(SolverTraitLangItem::MetaSized) => {
650                    G::consider_builtin_sizedness_candidates(self, goal, SizedTraitKind::MetaSized)
651                }
652                Some(SolverTraitLangItem::PointeeSized) => {
653                    unreachable!("`PointeeSized` is removed during lowering");
654                }
655                Some(
656                    SolverTraitLangItem::Copy
657                    | SolverTraitLangItem::Clone
658                    | SolverTraitLangItem::TrivialClone,
659                ) => G::consider_builtin_copy_clone_candidate(self, goal),
660                Some(SolverTraitLangItem::Fn) => {
661                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::Fn)
662                }
663                Some(SolverTraitLangItem::FnMut) => {
664                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::FnMut)
665                }
666                Some(SolverTraitLangItem::FnOnce) => {
667                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::FnOnce)
668                }
669                Some(SolverTraitLangItem::AsyncFn) => {
670                    G::consider_builtin_async_fn_trait_candidates(self, goal, ty::ClosureKind::Fn)
671                }
672                Some(SolverTraitLangItem::AsyncFnMut) => {
673                    G::consider_builtin_async_fn_trait_candidates(
674                        self,
675                        goal,
676                        ty::ClosureKind::FnMut,
677                    )
678                }
679                Some(SolverTraitLangItem::AsyncFnOnce) => {
680                    G::consider_builtin_async_fn_trait_candidates(
681                        self,
682                        goal,
683                        ty::ClosureKind::FnOnce,
684                    )
685                }
686                Some(SolverTraitLangItem::FnPtrTrait) => {
687                    G::consider_builtin_fn_ptr_trait_candidate(self, goal)
688                }
689                Some(SolverTraitLangItem::FnAddrTrait) => {
690                    if matches!(goal.predicate.self_ty().kind(), ty::FnDef(..)) {
691                        G::consider_builtin_fn_static_trait_candidate(self, goal)
692                    } else {
693                        G::consider_builtin_fn_ptr_trait_candidate(self, goal)
694                    }
695                }
696                Some(SolverTraitLangItem::AsyncFnKindHelper) => {
697                    G::consider_builtin_async_fn_kind_helper_candidate(self, goal)
698                }
699                Some(SolverTraitLangItem::Tuple) => G::consider_builtin_tuple_candidate(self, goal),
700                Some(SolverTraitLangItem::PointeeTrait) => {
701                    G::consider_builtin_pointee_candidate(self, goal)
702                }
703                Some(SolverTraitLangItem::Future) => {
704                    G::consider_builtin_future_candidate(self, goal)
705                }
706                Some(SolverTraitLangItem::Iterator) => {
707                    G::consider_builtin_iterator_candidate(self, goal)
708                }
709                Some(SolverTraitLangItem::FusedIterator) => {
710                    G::consider_builtin_fused_iterator_candidate(self, goal)
711                }
712                Some(SolverTraitLangItem::AsyncIterator) => {
713                    G::consider_builtin_async_iterator_candidate(self, goal)
714                }
715                Some(SolverTraitLangItem::Coroutine) => {
716                    G::consider_builtin_coroutine_candidate(self, goal)
717                }
718                Some(SolverTraitLangItem::DiscriminantKind) => {
719                    G::consider_builtin_discriminant_kind_candidate(self, goal)
720                }
721                Some(SolverTraitLangItem::Destruct) => {
722                    G::consider_builtin_destruct_candidate(self, goal)
723                }
724                Some(SolverTraitLangItem::TransmuteTrait) => {
725                    G::consider_builtin_transmute_candidate(self, goal)
726                }
727                Some(SolverTraitLangItem::BikeshedGuaranteedNoDrop) => {
728                    G::consider_builtin_bikeshed_guaranteed_no_drop_candidate(self, goal)
729                }
730                Some(SolverTraitLangItem::TryAsDyn) => {
731                    G::consider_builtin_try_as_dyn_candidate(self, goal)
732                }
733                Some(SolverTraitLangItem::Field) => G::consider_builtin_field_candidate(self, goal),
734                _ => Err(NoSolution.into()),
735            }
736        };
737
738        candidates.extend(result);
739
740        // There may be multiple unsize candidates for a trait with several supertraits:
741        // `trait Foo: Bar<A> + Bar<B>` and `dyn Foo: Unsize<dyn Bar<_>>`
742        if cx.is_trait_lang_item(trait_def_id, SolverTraitLangItem::Unsize) {
743            candidates.extend(G::consider_structural_builtin_unsize_candidates(self, goal)?);
744        }
745
746        Ok(())
747    }
748
749    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::TRACE <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::TRACE <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("assemble_param_env_candidates",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::TRACE,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(749u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[],
                                        ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{ meta.fields().value_set_all(&[]) })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return: Result<(), RerunNonErased> =
                loop {};
            return __tracing_attr_fake_return;
        }
        {
            let goal_lang_item =
                self.cx().as_trait_lang_item(goal.predicate.trait_def_id(self.cx()));
            for assumption in
                goal.param_env.caller_bounds().all_clauses(self.cx()).iter() {
                match G::fast_reject_assumption(self, goal, goal_lang_item,
                        assumption) {
                    Ok(()) => {
                        match G::probe_and_consider_param_env_candidate(self, goal,
                                    assumption)? {
                            Ok(candidate) => candidates.push(candidate),
                            Err(head_usages) => {
                                failed_candidate_info.param_env_head_usages.merge_usages(head_usages)
                            }
                        }
                    }
                    Err(NoSolution) => {}
                }
            }
            Ok(())
        }
    }
}#[instrument(level = "trace", skip_all)]
750    fn assemble_param_env_candidates<G: GoalKind<D>>(
751        &mut self,
752        goal: Goal<I, G>,
753        candidates: &mut Vec<Candidate<I>>,
754        failed_candidate_info: &mut FailedCandidateInfo,
755    ) -> Result<(), RerunNonErased> {
756        let goal_lang_item = self.cx().as_trait_lang_item(goal.predicate.trait_def_id(self.cx()));
757
758        for assumption in goal.param_env.caller_bounds().all_clauses(self.cx()).iter() {
759            match G::fast_reject_assumption(self, goal, goal_lang_item, assumption) {
760                Ok(()) => {
761                    match G::probe_and_consider_param_env_candidate(self, goal, assumption)? {
762                        Ok(candidate) => candidates.push(candidate),
763                        Err(head_usages) => {
764                            failed_candidate_info.param_env_head_usages.merge_usages(head_usages)
765                        }
766                    }
767                }
768                Err(NoSolution) => {}
769            }
770        }
771
772        Ok(())
773    }
774
775    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::TRACE <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::TRACE <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("assemble_alias_bound_candidates",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::TRACE,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(775u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[],
                                        ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{ meta.fields().value_set_all(&[]) })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return: Result<(), RerunNonErased> =
                loop {};
            return __tracing_attr_fake_return;
        }
        {
            let res =
                self.probe(|_|
                            ProbeKind::NormalizedSelfTyAssembly).enter(|ecx|
                        {
                            ecx.assemble_alias_bound_candidates_recur(goal.predicate.self_ty(),
                                    goal, candidates, AliasBoundKind::SelfBounds)?;
                            Ok(())
                        });
            match res {
                Ok(_) => Ok(()),
                Err(NoSolutionOrRerunNonErased::RerunNonErased(e)) => Err(e),
                Err(NoSolutionOrRerunNonErased::NoSolution(NoSolution)) => {
                    ::core::panicking::unreachable_default_msg()
                }
            }
        }
    }
}#[instrument(level = "trace", skip_all)]
776    fn assemble_alias_bound_candidates<G: GoalKind<D>>(
777        &mut self,
778        goal: Goal<I, G>,
779        candidates: &mut Vec<Candidate<I>>,
780    ) -> Result<(), RerunNonErased> {
781        let res = self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| {
782            ecx.assemble_alias_bound_candidates_recur(
783                goal.predicate.self_ty(),
784                goal,
785                candidates,
786                AliasBoundKind::SelfBounds,
787            )?;
788            Ok(())
789        });
790
791        // always returns Ok
792        match res {
793            Ok(_) => Ok(()),
794            Err(NoSolutionOrRerunNonErased::RerunNonErased(e)) => Err(e),
795            Err(NoSolutionOrRerunNonErased::NoSolution(NoSolution)) => {
796                unreachable!()
797            }
798        }
799    }
800
801    /// For some deeply nested `<T>::A::B::C::D` rigid associated type,
802    /// we should explore the item bounds for all levels, since the
803    /// `associated_type_bounds` feature means that a parent associated
804    /// type may carry bounds for a nested associated type.
805    ///
806    /// If we have a projection, check that its self type is a rigid projection.
807    /// If so, continue searching by recursively calling after normalization.
808    // FIXME: This may recurse infinitely, but I can't seem to trigger it without
809    // hitting another overflow error something. Add a depth parameter needed later.
810    fn assemble_alias_bound_candidates_recur<G: GoalKind<D>>(
811        &mut self,
812        self_ty: I::Ty,
813        goal: Goal<I, G>,
814        candidates: &mut Vec<Candidate<I>>,
815        consider_self_bounds: AliasBoundKind,
816    ) -> Result<(), RerunNonErased> {
817        let (alias_ty, def_id) = match self_ty.kind() {
818            ty::Bool
819            | ty::Char
820            | ty::Int(_)
821            | ty::Uint(_)
822            | ty::Float(_)
823            | ty::Adt(_, _)
824            | ty::Foreign(_)
825            | ty::Str
826            | ty::Array(_, _)
827            | ty::Pat(_, _)
828            | ty::Slice(_)
829            | ty::RawPtr(_, _)
830            | ty::Ref(_, _, _)
831            | ty::FnDef(_, _)
832            | ty::FnPtr(..)
833            | ty::UnsafeBinder(_)
834            | ty::Dynamic(..)
835            | ty::Closure(..)
836            | ty::CoroutineClosure(..)
837            | ty::Coroutine(..)
838            | ty::CoroutineWitness(..)
839            | ty::Never
840            | ty::Tuple(_)
841            | ty::Param(_)
842            | ty::Placeholder(..)
843            | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
844            | ty::Error(_) => return Ok(()),
845            ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) | ty::Bound(..) => {
846                {
    ::core::panicking::panic_fmt(format_args!("unexpected self type for `{0:?}`",
            goal));
}panic!("unexpected self type for `{goal:?}`")
847            }
848
849            ty::Infer(ty::TyVar(_)) => {
850                // If we hit infer when normalizing the self type of an alias,
851                // then bail with ambiguity. We should never encounter this on
852                // the *first* iteration of this recursive function.
853                if let Ok(result) =
854                    self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
855                {
856                    candidates.push(Candidate {
857                        source: CandidateSource::AliasBound(consider_self_bounds),
858                        result,
859                        head_usages: CandidateHeadUsages::default(),
860                    });
861                }
862                return Ok(());
863            }
864
865            ty::Alias(
866                ty::IsRigid::Yes,
867                alias_ty @ AliasTy { kind: ty::Projection { def_id }, .. },
868            ) => (alias_ty, def_id.into()),
869
870            ty::Alias(ty::IsRigid::Yes, alias_ty @ AliasTy { kind: ty::Opaque { def_id }, .. }) => {
871                (alias_ty, def_id.into())
872            }
873
874            ty::Alias(ty::IsRigid::No, _) => {
    ::core::panicking::panic_fmt(format_args!("internal error: entered unreachable code: {0}",
            format_args!("non-rigid self type: {0:?}", self_ty)));
}unreachable!("non-rigid self type: {self_ty:?}"),
875
876            ty::Alias(
877                ty::IsRigid::Yes,
878                AliasTy { kind: ty::Inherent { .. } | ty::Free { .. }, .. },
879            ) => {
880                self.cx().delay_bug(::alloc::__export::must_use({
        ::alloc::fmt::format(format_args!("could not normalize {0:?}, it is not WF",
                self_ty))
    })format!("could not normalize {self_ty:?}, it is not WF"));
881                return Ok(());
882            }
883
884            // FIXME(scrabsha)
885            ty::View(..) => ::core::panicking::unimplemented_default_msg()unimplemented!(),
886        };
887
888        match consider_self_bounds {
889            AliasBoundKind::SelfBounds => {
890                for assumption in self
891                    .cx()
892                    .item_self_bounds(def_id)
893                    .iter_instantiated(self.cx(), alias_ty.args)
894                    .map(Unnormalized::skip_norm_wip)
895                {
896                    candidates.extend(G::probe_and_consider_implied_clause(
897                        self,
898                        CandidateSource::AliasBound(consider_self_bounds),
899                        goal,
900                        assumption,
901                        [],
902                    ));
903                }
904            }
905            AliasBoundKind::NonSelfBounds => {
906                for assumption in self
907                    .cx()
908                    .item_non_self_bounds(def_id)
909                    .iter_instantiated(self.cx(), alias_ty.args)
910                    .map(Unnormalized::skip_norm_wip)
911                {
912                    candidates.extend(G::probe_and_consider_implied_clause(
913                        self,
914                        CandidateSource::AliasBound(consider_self_bounds),
915                        goal,
916                        assumption,
917                        [],
918                    ));
919                }
920            }
921        }
922
923        candidates.extend(G::consider_additional_alias_assumptions(self, goal, alias_ty));
924
925        let Some(projection_ty) = alias_ty.try_to_projection() else {
926            return Ok(());
927        };
928
929        // Recurse on the self type of the projection.
930        match self.structurally_normalize_ty(goal.param_env, projection_ty.projection_self_ty()) {
931            Ok(next_self_ty) => self.assemble_alias_bound_candidates_recur(
932                next_self_ty,
933                goal,
934                candidates,
935                AliasBoundKind::NonSelfBounds,
936            ),
937            Err(NoSolutionOrRerunNonErased::NoSolution(NoSolution)) => Ok(()),
938            Err(NoSolutionOrRerunNonErased::RerunNonErased(e)) => Err(e),
939        }
940    }
941
942    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::TRACE <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::TRACE <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("assemble_object_bound_candidates",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::TRACE,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(942u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[],
                                        ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{ meta.fields().value_set_all(&[]) })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return: () = loop {};
            return __tracing_attr_fake_return;
        }
        {
            let cx = self.cx();
            if cx.is_sizedness_trait(goal.predicate.trait_def_id(cx)) {
                return;
            }
            if self.typing_mode().is_reflection() { return; }
            let self_ty = goal.predicate.self_ty();
            let bounds =
                match self_ty.kind() {
                    ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) |
                        ty::Float(_) | ty::Adt(_, _) | ty::Foreign(_) | ty::Str |
                        ty::Array(_, _) | ty::Pat(_, _) | ty::Slice(_) |
                        ty::RawPtr(_, _) | ty::Ref(_, _, _) | ty::FnDef(_, _) |
                        ty::FnPtr(..) | ty::UnsafeBinder(_) | ty::Alias(..) |
                        ty::Closure(..) | ty::CoroutineClosure(..) |
                        ty::Coroutine(..) | ty::CoroutineWitness(..) | ty::Never |
                        ty::Tuple(_) | ty::Param(_) | ty::Placeholder(..) |
                        ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Error(_) =>
                        return,
                    ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_)
                        | ty::FreshFloatTy(_)) | ty::Bound(..) => {
                        ::core::panicking::panic_fmt(format_args!("unexpected self type for `{0:?}`",
                                goal));
                    }
                    ty::Dynamic(bounds, ..) => bounds,
                    ty::View(..) =>
                        ::core::panicking::unimplemented_default_msg(),
                };
            if bounds.principal_def_id().is_some_and(|def_id|
                        !cx.trait_is_dyn_compatible(def_id)) {
                return;
            }
            for bound in bounds.iter() {
                match bound.skip_binder() {
                    ty::ExistentialPredicate::Trait(_) => {}
                    ty::ExistentialPredicate::Projection(_) |
                        ty::ExistentialPredicate::AutoTrait(_) => {
                        candidates.extend(G::probe_and_consider_object_bound_candidate(self,
                                CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), goal,
                                bound.with_self_ty(cx, self_ty)));
                    }
                }
            }
            if let Some(principal) = bounds.principal() {
                let principal_trait_ref = principal.with_self_ty(cx, self_ty);
                for (idx, assumption) in
                    elaborate::supertraits(cx, principal_trait_ref).enumerate()
                    {
                    candidates.extend(G::probe_and_consider_object_bound_candidate(self,
                            CandidateSource::BuiltinImpl(BuiltinImplSource::Object(idx)),
                            goal, assumption.upcast(cx)));
                }
            }
        }
    }
}#[instrument(level = "trace", skip_all)]
943    fn assemble_object_bound_candidates<G: GoalKind<D>>(
944        &mut self,
945        goal: Goal<I, G>,
946        candidates: &mut Vec<Candidate<I>>,
947    ) {
948        let cx = self.cx();
949        if cx.is_sizedness_trait(goal.predicate.trait_def_id(cx)) {
950            // `dyn MetaSized` is valid, but should get its `MetaSized` impl from
951            // being `dyn` (SizedCandidate), not from the object candidate.
952            return;
953        }
954
955        // Builtin impls regularly are not `is_fully_generic_for_reflection`, so instead
956        // of trying to handle these manually, we just reject all builtin impls in reflection
957        // mode. We can probably lift this restriction for specific cases, but this is safer.
958        // See `try_as_dyn_builtin_impl` for how just allowing all builtin impls is unsound.
959        if self.typing_mode().is_reflection() {
960            return;
961        }
962
963        let self_ty = goal.predicate.self_ty();
964        let bounds = match self_ty.kind() {
965            ty::Bool
966            | ty::Char
967            | ty::Int(_)
968            | ty::Uint(_)
969            | ty::Float(_)
970            | ty::Adt(_, _)
971            | ty::Foreign(_)
972            | ty::Str
973            | ty::Array(_, _)
974            | ty::Pat(_, _)
975            | ty::Slice(_)
976            | ty::RawPtr(_, _)
977            | ty::Ref(_, _, _)
978            | ty::FnDef(_, _)
979            | ty::FnPtr(..)
980            | ty::UnsafeBinder(_)
981            | ty::Alias(..)
982            | ty::Closure(..)
983            | ty::CoroutineClosure(..)
984            | ty::Coroutine(..)
985            | ty::CoroutineWitness(..)
986            | ty::Never
987            | ty::Tuple(_)
988            | ty::Param(_)
989            | ty::Placeholder(..)
990            | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
991            | ty::Error(_) => return,
992            ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
993            | ty::Bound(..) => panic!("unexpected self type for `{goal:?}`"),
994            ty::Dynamic(bounds, ..) => bounds,
995
996            // FIXME(scrabsha)
997            ty::View(..) => unimplemented!(),
998        };
999
1000        // Do not consider built-in object impls for dyn-incompatible types.
1001        if bounds.principal_def_id().is_some_and(|def_id| !cx.trait_is_dyn_compatible(def_id)) {
1002            return;
1003        }
1004
1005        // Consider all of the auto-trait and projection bounds, which don't
1006        // need to be recorded as a `BuiltinImplSource::Object` since they don't
1007        // really have a vtable base...
1008        for bound in bounds.iter() {
1009            match bound.skip_binder() {
1010                ty::ExistentialPredicate::Trait(_) => {
1011                    // Skip principal
1012                }
1013                ty::ExistentialPredicate::Projection(_)
1014                | ty::ExistentialPredicate::AutoTrait(_) => {
1015                    candidates.extend(G::probe_and_consider_object_bound_candidate(
1016                        self,
1017                        CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
1018                        goal,
1019                        bound.with_self_ty(cx, self_ty),
1020                    ));
1021                }
1022            }
1023        }
1024
1025        // FIXME: We only need to do *any* of this if we're considering a trait goal,
1026        // since we don't need to look at any supertrait or anything if we are doing
1027        // a projection goal.
1028        if let Some(principal) = bounds.principal() {
1029            let principal_trait_ref = principal.with_self_ty(cx, self_ty);
1030            for (idx, assumption) in elaborate::supertraits(cx, principal_trait_ref).enumerate() {
1031                candidates.extend(G::probe_and_consider_object_bound_candidate(
1032                    self,
1033                    CandidateSource::BuiltinImpl(BuiltinImplSource::Object(idx)),
1034                    goal,
1035                    assumption.upcast(cx),
1036                ));
1037            }
1038        }
1039    }
1040
1041    /// In coherence we have to not only care about all impls we know about, but
1042    /// also consider impls which may get added in a downstream or sibling crate
1043    /// or which an upstream impl may add in a minor release.
1044    ///
1045    /// To do so we return a single ambiguous candidate in case such an unknown
1046    /// impl could apply to the current goal.
1047    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::TRACE <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::TRACE <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("consider_coherence_unknowable_candidate",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::TRACE,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(1047u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[],
                                        ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::TRACE <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{ meta.fields().value_set_all(&[]) })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return:
                    Result<Candidate<I>, NoSolutionOrRerunNonErased> = loop {};
            return __tracing_attr_fake_return;
        }
        {
            self.probe_trait_candidate(CandidateSource::CoherenceUnknowable).enter(|ecx|
                    {
                        let cx = ecx.cx();
                        let trait_ref = goal.predicate.trait_ref(cx);
                        if ecx.trait_ref_is_knowable(goal.param_env, trait_ref)? {
                            Err(NoSolution.into())
                        } else {
                            let predicate: I::Predicate = trait_ref.upcast(cx);
                            ecx.add_goals(GoalSource::Misc,
                                    elaborate::elaborate(cx,
                                                [predicate]).skip(1).map(|predicate|
                                            goal.with(cx, predicate)))?;
                            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                        }
                    })
        }
    }
}#[instrument(level = "trace", skip_all)]
1048    fn consider_coherence_unknowable_candidate<G: GoalKind<D>>(
1049        &mut self,
1050        goal: Goal<I, G>,
1051    ) -> Result<Candidate<I>, NoSolutionOrRerunNonErased> {
1052        self.probe_trait_candidate(CandidateSource::CoherenceUnknowable).enter(|ecx| {
1053            let cx = ecx.cx();
1054            let trait_ref = goal.predicate.trait_ref(cx);
1055            if ecx.trait_ref_is_knowable(goal.param_env, trait_ref)? {
1056                Err(NoSolution.into())
1057            } else {
1058                // While the trait bound itself may be unknowable, we may be able to
1059                // prove that a super trait is not implemented. For this, we recursively
1060                // prove the super trait bounds of the current goal.
1061                //
1062                // We skip the goal itself as that one would cycle.
1063                let predicate: I::Predicate = trait_ref.upcast(cx);
1064                ecx.add_goals(
1065                    GoalSource::Misc,
1066                    elaborate::elaborate(cx, [predicate])
1067                        .skip(1)
1068                        .map(|predicate| goal.with(cx, predicate)),
1069                )?;
1070                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
1071            }
1072        })
1073    }
1074}
1075
1076pub(super) enum AllowInferenceConstraints {
1077    Yes,
1078    No,
1079}
1080
1081impl<D, I> EvalCtxt<'_, D>
1082where
1083    D: SolverDelegate<Interner = I>,
1084    I: Interner,
1085{
1086    /// Check whether we can ignore impl candidates due to specialization.
1087    ///
1088    /// This is only necessary for `feature(specialization)` and seems quite ugly.
1089    pub(super) fn filter_specialized_impls(
1090        &mut self,
1091        allow_inference_constraints: AllowInferenceConstraints,
1092        candidates: &mut Vec<Candidate<I>>,
1093    ) {
1094        if self.typing_mode().is_coherence() {
1095            return;
1096        }
1097
1098        let mut i = 0;
1099        'outer: while i < candidates.len() {
1100            let CandidateSource::Impl(victim_def_id) = candidates[i].source else {
1101                i += 1;
1102                continue;
1103            };
1104
1105            for (j, c) in candidates.iter().enumerate() {
1106                if i == j {
1107                    continue;
1108                }
1109
1110                let CandidateSource::Impl(other_def_id) = c.source else {
1111                    continue;
1112                };
1113
1114                // See if we can toss out `victim` based on specialization.
1115                //
1116                // While this requires us to know *for sure* that the `lhs` impl applies
1117                // we still use modulo regions here. This is fine as specialization currently
1118                // assumes that specializing impls have to be always applicable, meaning that
1119                // the only allowed region constraints may be constraints also present on the default impl.
1120                //
1121                // If both impls have the same response, dropping victim doesn't change the
1122                // result. We need to do so here as we don't merge distinct impl candidates.
1123                if #[allow(non_exhaustive_omitted_patterns)] match allow_inference_constraints {
    AllowInferenceConstraints::Yes => true,
    _ => false,
}matches!(allow_inference_constraints, AllowInferenceConstraints::Yes)
1124                    || has_only_region_constraints(c.result)
1125                    || c.result == candidates[i].result
1126                {
1127                    if self.cx().impl_specializes(other_def_id, victim_def_id) {
1128                        candidates.remove(i);
1129                        continue 'outer;
1130                    }
1131                }
1132            }
1133
1134            i += 1;
1135        }
1136    }
1137
1138    /// If the self type is the hidden type of an opaque, try to assemble
1139    /// candidates for it by consider its item bounds and by using blanket
1140    /// impls. This is used to incompletely guide type inference when handling
1141    /// non-defining uses in the defining scope.
1142    ///
1143    /// We otherwise just fail fail with ambiguity. Even if we're using an
1144    /// opaque type item bound or a blank impls, we still force its certainty
1145    /// to be `Maybe` so that we properly prove this goal later.
1146    ///
1147    /// See <https://github.com/rust-lang/trait-system-refactor-initiative/issues/182>
1148    /// for why this is necessary.
1149    {}
#[allow(clippy :: suspicious_else_formatting)]
{
    let __tracing_attr_span;
    let __tracing_attr_guard;
    if ::tracing::Level::INFO <= ::tracing::level_filters::STATIC_MAX_LEVEL &&
                ::tracing::Level::INFO <=
                    ::tracing::level_filters::LevelFilter::current() ||
            { false } {
        __tracing_attr_span =
            {
                use ::tracing::__macro_support::Callsite as _;
                static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                    {
                        static META: ::tracing::Metadata<'static> =
                            {
                                ::tracing_core::metadata::Metadata::new("try_assemble_bounds_via_registered_opaques",
                                    "rustc_next_trait_solver::solve::assembly",
                                    ::tracing::Level::INFO,
                                    ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                    ::tracing_core::__macro_support::Option::Some(1149u32),
                                    ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                    ::tracing_core::field::FieldSet::new(&[{
                                                        const NAME:
                                                            ::tracing::__macro_support::FieldName<{
                                                                ::tracing::__macro_support::FieldName::len("goal")
                                                            }> =
                                                            ::tracing::__macro_support::FieldName::new("goal");
                                                        NAME.as_str()
                                                    },
                                                    {
                                                        const NAME:
                                                            ::tracing::__macro_support::FieldName<{
                                                                ::tracing::__macro_support::FieldName::len("candidates")
                                                            }> =
                                                            ::tracing::__macro_support::FieldName::new("candidates");
                                                        NAME.as_str()
                                                    }], ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                    ::tracing::metadata::Kind::SPAN)
                            };
                        ::tracing::callsite::DefaultCallsite::new(&META)
                    };
                let mut interest = ::tracing::subscriber::Interest::never();
                if ::tracing::Level::INFO <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::INFO <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            { interest = __CALLSITE.interest(); !interest.is_never() }
                        &&
                        ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                            interest) {
                    let meta = __CALLSITE.metadata();
                    ::tracing::Span::new(meta,
                        &{
                                #[allow(unused_imports)]
                                use ::tracing::field::{debug, display, Value};
                                meta.fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&::tracing::field::debug(&goal)
                                                            as &dyn ::tracing::field::Value)),
                                                (::tracing::__macro_support::Option::Some(&::tracing::field::debug(&candidates)
                                                            as &dyn ::tracing::field::Value))])
                            })
                } else {
                    let span =
                        ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                    {};
                    span
                }
            };
        __tracing_attr_guard = __tracing_attr_span.enter();
    }

    #[warn(clippy :: suspicious_else_formatting)]
    {

        #[allow(unknown_lints, unreachable_code, clippy ::
        diverging_sub_expression, clippy :: empty_loop, clippy ::
        let_unit_value, clippy :: let_with_type_underscore, clippy ::
        needless_return, clippy :: unreachable)]
        if false {
            let __tracing_attr_fake_return: Result<(), RerunNonErased> =
                loop {};
            return __tracing_attr_fake_return;
        }
        {
            let self_ty = goal.predicate.self_ty();
            let opaque_types =
                match self.typing_mode() {
                    TypingMode::Typeck { .. } =>
                        self.opaques_with_sub_unified_hidden_type(self_ty),
                    TypingMode::Coherence |
                        TypingMode::PostTypeckThroughBorrowck { .. } |
                        TypingMode::PostBorrowck { .. } | TypingMode::PostAnalysis |
                        TypingMode::Reflection | TypingMode::Codegen =>
                        ::alloc::vec::Vec::new(),
                    TypingMode::ErasedNotCoherence(MayBeErased) => {
                        self.opaque_accesses.rerun_if_any_opaque_has_infer_as_hidden_type(RerunReason::SelfTyInfer)?;
                        Vec::new()
                    }
                };
            if opaque_types.is_empty() {
                candidates.extend(self.forced_ambiguity(MaybeInfo::AMBIGUOUS));
                return Ok(());
            }
            for &opaque_ty in &opaque_types {
                {
                    use ::tracing::__macro_support::Callsite as _;
                    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                        {
                            static META: ::tracing::Metadata<'static> =
                                {
                                    ::tracing_core::metadata::Metadata::new("event /rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs:1179",
                                        "rustc_next_trait_solver::solve::assembly",
                                        ::tracing::Level::DEBUG,
                                        ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                        ::tracing_core::__macro_support::Option::Some(1179u32),
                                        ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                        ::tracing_core::field::FieldSet::new(&["message"],
                                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                        ::tracing::metadata::Kind::EVENT)
                                };
                            ::tracing::callsite::DefaultCallsite::new(&META)
                        };
                    let enabled =
                        ::tracing::Level::DEBUG <=
                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                ::tracing::Level::DEBUG <=
                                    ::tracing::level_filters::LevelFilter::current() &&
                            {
                                let interest = __CALLSITE.interest();
                                !interest.is_never() &&
                                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                                        interest)
                            };
                    if enabled {
                        (|value_set: ::tracing::field::ValueSet|
                                    {
                                        let meta = __CALLSITE.metadata();
                                        ::tracing::Event::dispatch(meta, &value_set);
                                        ;
                                    })({
                                #[allow(unused_imports)]
                                use ::tracing::field::{debug, display, Value};
                                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("self ty is sub unified with {0:?}",
                                                                    opaque_ty) as &dyn ::tracing::field::Value))])
                            });
                    } else { ; }
                };
                struct ReplaceOpaque<I: Interner> {
                    cx: I,
                    opaque_ty: ty::OpaqueAliasTy<I>,
                    self_ty: I::Ty,
                }
                impl<I: Interner> TypeFolder<I> for ReplaceOpaque<I> {
                    fn cx(&self) -> I { self.cx }
                    fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
                        if let ty::Alias(is_rigid, alias_ty) = ty.kind() &&
                                let Some(opaque_ty) = alias_ty.try_to_opaque() {
                            if opaque_ty == self.opaque_ty {
                                if true {
                                    {
                                        match (&is_rigid, &ty::IsRigid::No) {
                                            (left_val, right_val) => {
                                                if !(*left_val == *right_val) {
                                                    let kind = ::core::panicking::AssertKind::Eq;
                                                    ::core::panicking::assert_failed(kind, &*left_val,
                                                        &*right_val, ::core::option::Option::None);
                                                }
                                            }
                                        }
                                    };
                                };
                                return self.self_ty;
                            }
                        }
                        ty.super_fold_with(self)
                    }
                }
                for item_bound in
                    self.cx().item_self_bounds(opaque_ty.kind.into()).iter_instantiated(self.cx(),
                            opaque_ty.args).map(Unnormalized::skip_norm_wip) {
                    let assumption =
                        item_bound.fold_with(&mut ReplaceOpaque {
                                    cx: self.cx(),
                                    opaque_ty,
                                    self_ty,
                                });
                    candidates.extend(G::probe_and_match_goal_against_assumption(self,
                            CandidateSource::AliasBound(AliasBoundKind::SelfBounds),
                            goal, assumption,
                            |ecx|
                                {
                                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                                }));
                }
            }
            if assemble_from.should_assemble_impl_candidates() {
                let cx = self.cx();
                let goal_trait_ref = goal.predicate.trait_ref(cx);
                cx.for_each_blanket_impl(goal.predicate.trait_def_id(cx),
                        |impl_def_id|
                            {
                                match G::consider_impl_candidate(self, goal, goal_trait_ref,
                                                impl_def_id,
                                                |ecx|
                                                    {
                                                        if ecx.shallow_resolve(self_ty).is_ty_var() {
                                                            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                                                        } else { Err(NoSolution.into()) }
                                                    }).map_err_to_rerun()? {
                                    Ok(candidate) => candidates.push(candidate),
                                    Err(NoSolution) => {}
                                }
                                Ok(())
                            })?;
            }
            if candidates.is_empty() {
                let source =
                    CandidateSource::BuiltinImpl(BuiltinImplSource::Misc);
                let certainty =
                    Certainty::Maybe(MaybeInfo {
                            cause: MaybeCause::Ambiguity,
                            opaque_types_jank: OpaqueTypesJank::ErrorIfRigidSelfTy,
                            stalled_on_coroutines: StalledOnCoroutines::No,
                        });
                candidates.extend(self.probe_trait_candidate(source).enter(|this|
                            {
                                this.evaluate_added_goals_and_make_canonical_response(certainty)
                            }));
            }
            Ok(())
        }
    }
}#[tracing::instrument(skip(self, assemble_from))]
1150    fn try_assemble_bounds_via_registered_opaques<G: GoalKind<D>>(
1151        &mut self,
1152        goal: Goal<I, G>,
1153        assemble_from: AssembleCandidatesFrom,
1154        candidates: &mut Vec<Candidate<I>>,
1155    ) -> Result<(), RerunNonErased> {
1156        let self_ty = goal.predicate.self_ty();
1157        // We only use this hack during HIR typeck.
1158        let opaque_types = match self.typing_mode() {
1159            TypingMode::Typeck { .. } => self.opaques_with_sub_unified_hidden_type(self_ty),
1160            TypingMode::Coherence
1161            | TypingMode::PostTypeckThroughBorrowck { .. }
1162            | TypingMode::PostBorrowck { .. }
1163            | TypingMode::PostAnalysis
1164            | TypingMode::Reflection
1165            | TypingMode::Codegen => vec![],
1166            TypingMode::ErasedNotCoherence(MayBeErased) => {
1167                self.opaque_accesses
1168                    .rerun_if_any_opaque_has_infer_as_hidden_type(RerunReason::SelfTyInfer)?;
1169                Vec::new()
1170            }
1171        };
1172
1173        if opaque_types.is_empty() {
1174            candidates.extend(self.forced_ambiguity(MaybeInfo::AMBIGUOUS));
1175            return Ok(());
1176        }
1177
1178        for &opaque_ty in &opaque_types {
1179            debug!("self ty is sub unified with {opaque_ty:?}");
1180
1181            struct ReplaceOpaque<I: Interner> {
1182                cx: I,
1183                opaque_ty: ty::OpaqueAliasTy<I>,
1184                self_ty: I::Ty,
1185            }
1186            impl<I: Interner> TypeFolder<I> for ReplaceOpaque<I> {
1187                fn cx(&self) -> I {
1188                    self.cx
1189                }
1190                fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
1191                    if let ty::Alias(is_rigid, alias_ty) = ty.kind()
1192                        && let Some(opaque_ty) = alias_ty.try_to_opaque()
1193                    {
1194                        if opaque_ty == self.opaque_ty {
1195                            debug_assert_eq!(is_rigid, ty::IsRigid::No);
1196                            return self.self_ty;
1197                        }
1198                    }
1199                    ty.super_fold_with(self)
1200                }
1201            }
1202
1203            // We look at all item-bounds of the opaque, replacing the
1204            // opaque with the current self type before considering
1205            // them as a candidate. Imagine we've got `?x: Trait<?y>`
1206            // and `?x` has been sub-unified with the hidden type of
1207            // `impl Trait<u32>`, We take the item bound `opaque: Trait<u32>`
1208            // and replace all occurrences of `opaque` with `?x`. This results
1209            // in a `?x: Trait<u32>` alias-bound candidate.
1210            for item_bound in self
1211                .cx()
1212                .item_self_bounds(opaque_ty.kind.into())
1213                .iter_instantiated(self.cx(), opaque_ty.args)
1214                .map(Unnormalized::skip_norm_wip)
1215            {
1216                let assumption =
1217                    item_bound.fold_with(&mut ReplaceOpaque { cx: self.cx(), opaque_ty, self_ty });
1218                candidates.extend(G::probe_and_match_goal_against_assumption(
1219                    self,
1220                    CandidateSource::AliasBound(AliasBoundKind::SelfBounds),
1221                    goal,
1222                    assumption,
1223                    |ecx| {
1224                        // We want to reprove this goal once we've inferred the
1225                        // hidden type, so we force the certainty to `Maybe`.
1226                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
1227                    },
1228                ));
1229            }
1230        }
1231
1232        // If the self type is sub unified with any opaque type, we also look at blanket
1233        // impls for it.
1234        //
1235        // See tests/ui/impl-trait/non-defining-uses/use-blanket-impl.rs for an example.
1236        if assemble_from.should_assemble_impl_candidates() {
1237            let cx = self.cx();
1238            let goal_trait_ref = goal.predicate.trait_ref(cx);
1239
1240            cx.for_each_blanket_impl(goal.predicate.trait_def_id(cx), |impl_def_id| {
1241                match G::consider_impl_candidate(self, goal, goal_trait_ref, impl_def_id, |ecx| {
1242                    if ecx.shallow_resolve(self_ty).is_ty_var() {
1243                        // We force the certainty of impl candidates to be `Maybe`.
1244                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
1245                    } else {
1246                        // We don't want to use impls if they constrain the opaque.
1247                        //
1248                        // FIXME(trait-system-refactor-initiative#229): This isn't
1249                        // perfect yet as it still allows us to incorrectly constrain
1250                        // other inference variables.
1251                        Err(NoSolution.into())
1252                    }
1253                })
1254                .map_err_to_rerun()?
1255                {
1256                    Ok(candidate) => candidates.push(candidate),
1257                    Err(NoSolution) => {}
1258                }
1259
1260                Ok(())
1261            })?;
1262        }
1263
1264        if candidates.is_empty() {
1265            let source = CandidateSource::BuiltinImpl(BuiltinImplSource::Misc);
1266            let certainty = Certainty::Maybe(MaybeInfo {
1267                cause: MaybeCause::Ambiguity,
1268                opaque_types_jank: OpaqueTypesJank::ErrorIfRigidSelfTy,
1269                stalled_on_coroutines: StalledOnCoroutines::No,
1270            });
1271            candidates
1272                .extend(self.probe_trait_candidate(source).enter(|this| {
1273                    this.evaluate_added_goals_and_make_canonical_response(certainty)
1274                }));
1275        }
1276
1277        Ok(())
1278    }
1279
1280    /// Assemble and merge candidates for goals which are related to an underlying trait
1281    /// goal. Right now, this is normalizes-to and host effect goals.
1282    ///
1283    /// We sadly can't simply take all possible candidates for normalization goals
1284    /// and check whether they result in the same constraints. We want to make sure
1285    /// that trying to normalize an alias doesn't result in constraints which aren't
1286    /// otherwise required.
1287    ///
1288    /// Most notably, when proving a trait goal by via a where-bound, we should not
1289    /// normalize via impls which have stricter region constraints than the where-bound:
1290    ///
1291    /// ```rust
1292    /// trait Trait<'a> {
1293    ///     type Assoc;
1294    /// }
1295    ///
1296    /// impl<'a, T: 'a> Trait<'a> for T {
1297    ///     type Assoc = u32;
1298    /// }
1299    ///
1300    /// fn with_bound<'a, T: Trait<'a>>(_value: T::Assoc) {}
1301    /// ```
1302    ///
1303    /// The where-bound of `with_bound` doesn't specify the associated type, so we would
1304    /// only be able to normalize `<T as Trait<'a>>::Assoc` by using the impl. This impl
1305    /// adds a `T: 'a` bound however, which would result in a region error. Given that the
1306    /// user explicitly wrote that `T: Trait<'a>` holds, this is undesirable and we instead
1307    /// treat the alias as rigid.
1308    ///
1309    /// See trait-system-refactor-initiative#124 for more details.
1310    {}
let __tracing_attr_span;
let __tracing_attr_guard;
if ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL &&
            ::tracing::Level::DEBUG <=
                ::tracing::level_filters::LevelFilter::current() || { false }
    {
    __tracing_attr_span =
        {
            use ::tracing::__macro_support::Callsite as _;
            static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                {
                    static META: ::tracing::Metadata<'static> =
                        {
                            ::tracing_core::metadata::Metadata::new("assemble_and_merge_candidates",
                                "rustc_next_trait_solver::solve::assembly",
                                ::tracing::Level::DEBUG,
                                ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                ::tracing_core::__macro_support::Option::Some(1310u32),
                                ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                ::tracing_core::field::FieldSet::new(&[{
                                                    const NAME:
                                                        ::tracing::__macro_support::FieldName<{
                                                            ::tracing::__macro_support::FieldName::len("proven_via")
                                                        }> =
                                                        ::tracing::__macro_support::FieldName::new("proven_via");
                                                    NAME.as_str()
                                                },
                                                {
                                                    const NAME:
                                                        ::tracing::__macro_support::FieldName<{
                                                            ::tracing::__macro_support::FieldName::len("goal")
                                                        }> =
                                                        ::tracing::__macro_support::FieldName::new("goal");
                                                    NAME.as_str()
                                                }], ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                ::tracing::metadata::Kind::SPAN)
                        };
                    ::tracing::callsite::DefaultCallsite::new(&META)
                };
            let mut interest = ::tracing::subscriber::Interest::never();
            if ::tracing::Level::DEBUG <=
                                ::tracing::level_filters::STATIC_MAX_LEVEL &&
                            ::tracing::Level::DEBUG <=
                                ::tracing::level_filters::LevelFilter::current() &&
                        { interest = __CALLSITE.interest(); !interest.is_never() }
                    &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest) {
                let meta = __CALLSITE.metadata();
                ::tracing::Span::new(meta,
                    &{
                            #[allow(unused_imports)]
                            use ::tracing::field::{debug, display, Value};
                            meta.fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&::tracing::field::Empty
                                                        as &dyn ::tracing::field::Value)),
                                            (::tracing::__macro_support::Option::Some(&::tracing::field::Empty
                                                        as &dyn ::tracing::field::Value))])
                        })
            } else {
                let span =
                    ::tracing::__macro_support::__disabled_span(__CALLSITE.metadata());
                {};
                span
            }
        };
    __tracing_attr_guard = __tracing_attr_span.enter();
}
#[allow(clippy :: redundant_closure_call)]
let x =
    (move ||
                {

                    #[allow(unknown_lints, unreachable_code, clippy ::
                    diverging_sub_expression, clippy :: empty_loop, clippy ::
                    let_unit_value, clippy :: let_with_type_underscore, clippy
                    :: needless_return, clippy :: unreachable)]
                    if false {
                        let __tracing_attr_fake_return:
                                QueryResultOrRerunNonErased<I> = loop {};
                        return __tracing_attr_fake_return;
                    }
                    {
                        let Some(proven_via) =
                            proven_via else {
                                return self.forced_ambiguity(MaybeInfo::AMBIGUOUS).map(|cand|
                                            cand.result);
                            };
                        match proven_via {
                            TraitGoalProvenVia::ParamEnv |
                                TraitGoalProvenVia::AliasBound => {
                                let (mut candidates, _) =
                                    self.assemble_and_evaluate_candidates(goal,
                                            AssembleCandidatesFrom::EnvAndBounds)?;
                                {
                                    use ::tracing::__macro_support::Callsite as _;
                                    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
                                        {
                                            static META: ::tracing::Metadata<'static> =
                                                {
                                                    ::tracing_core::metadata::Metadata::new("event /rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs:1344",
                                                        "rustc_next_trait_solver::solve::assembly",
                                                        ::tracing::Level::DEBUG,
                                                        ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                                                        ::tracing_core::__macro_support::Option::Some(1344u32),
                                                        ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                                                        ::tracing_core::field::FieldSet::new(&[{
                                                                            const NAME:
                                                                                ::tracing::__macro_support::FieldName<{
                                                                                    ::tracing::__macro_support::FieldName::len("candidates")
                                                                                }> =
                                                                                ::tracing::__macro_support::FieldName::new("candidates");
                                                                            NAME.as_str()
                                                                        }], ::tracing_core::callsite::Identifier(&__CALLSITE)),
                                                        ::tracing::metadata::Kind::EVENT)
                                                };
                                            ::tracing::callsite::DefaultCallsite::new(&META)
                                        };
                                    let enabled =
                                        ::tracing::Level::DEBUG <=
                                                    ::tracing::level_filters::STATIC_MAX_LEVEL &&
                                                ::tracing::Level::DEBUG <=
                                                    ::tracing::level_filters::LevelFilter::current() &&
                                            {
                                                let interest = __CALLSITE.interest();
                                                !interest.is_never() &&
                                                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                                                        interest)
                                            };
                                    if enabled {
                                        (|value_set: ::tracing::field::ValueSet|
                                                    {
                                                        let meta = __CALLSITE.metadata();
                                                        ::tracing::Event::dispatch(meta, &value_set);
                                                        ;
                                                    })({
                                                #[allow(unused_imports)]
                                                use ::tracing::field::{debug, display, Value};
                                                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&::tracing::field::debug(&candidates)
                                                                            as &dyn ::tracing::field::Value))])
                                            });
                                    } else { ; }
                                };
                                if candidates.is_empty() {
                                    return inject_normalize_to_rigid_candidate(self);
                                }
                                if let Some(result) =
                                        inject_forced_ambiguity_candidate(self) {
                                    return result;
                                }
                                if candidates.iter().any(|c|
                                            #[allow(non_exhaustive_omitted_patterns)] match c.source {
                                                CandidateSource::ParamEnv(_) => true,
                                                _ => false,
                                            }) {
                                    candidates.retain(|c|
                                            #[allow(non_exhaustive_omitted_patterns)] match c.source {
                                                CandidateSource::ParamEnv(_) => true,
                                                _ => false,
                                            });
                                }
                                if let Some(response) =
                                        self.try_merge_candidates(&candidates) {
                                    Ok(response)
                                } else { self.flounder(&candidates).map_err(Into::into) }
                            }
                            TraitGoalProvenVia::Misc => {
                                let (mut candidates, _) =
                                    self.assemble_and_evaluate_candidates(goal,
                                            AssembleCandidatesFrom::All)?;
                                if candidates.iter().any(|c|
                                            #[allow(non_exhaustive_omitted_patterns)] match c.source {
                                                CandidateSource::ParamEnv(_) => true,
                                                _ => false,
                                            }) {
                                    candidates.retain(|c|
                                            #[allow(non_exhaustive_omitted_patterns)] match c.source {
                                                CandidateSource::ParamEnv(_) => true,
                                                _ => false,
                                            });
                                }
                                self.filter_specialized_impls(AllowInferenceConstraints::Yes,
                                    &mut candidates);
                                if let Some(response) =
                                        self.try_merge_candidates(&candidates) {
                                    Ok(response)
                                } else { self.flounder(&candidates).map_err(Into::into) }
                            }
                        }
                    }
                })();
{
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event /rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs:1310",
                        "rustc_next_trait_solver::solve::assembly",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("/rustc-dev/5f4effd579500175af844241eb179e756190f1e7/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(1310u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_next_trait_solver::solve::assembly"),
                        ::tracing_core::field::FieldSet::new(&[{
                                            const NAME:
                                                ::tracing::__macro_support::FieldName<{
                                                    ::tracing::__macro_support::FieldName::len("return")
                                                }> =
                                                ::tracing::__macro_support::FieldName::new("return");
                                            NAME.as_str()
                                        }], ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&::tracing::field::debug(&x)
                                            as &dyn ::tracing::field::Value))])
            });
    } else { ; }
};
x;#[instrument(level = "debug", skip_all, fields(proven_via, goal), ret)]
1311    pub(super) fn assemble_and_merge_candidates<G: GoalKind<D>>(
1312        &mut self,
1313        proven_via: Option<TraitGoalProvenVia>,
1314        goal: Goal<I, G>,
1315        inject_forced_ambiguity_candidate: impl FnOnce(
1316            &mut EvalCtxt<'_, D>,
1317        ) -> Option<
1318            Result<CanonicalResponse<I>, NoSolutionOrRerunNonErased>,
1319        >,
1320        inject_normalize_to_rigid_candidate: impl FnOnce(
1321            &mut EvalCtxt<'_, D>,
1322        ) -> Result<
1323            CanonicalResponse<I>,
1324            NoSolutionOrRerunNonErased,
1325        >,
1326    ) -> QueryResultOrRerunNonErased<I> {
1327        let Some(proven_via) = proven_via else {
1328            // We don't care about overflow. If proving the trait goal overflowed, then
1329            // it's enough to report an overflow error for that, we don't also have to
1330            // overflow during normalization.
1331            //
1332            // We use `forced_ambiguity` here over `make_ambiguous_response_no_constraints`
1333            // because the former will also record a built-in candidate in the inspector.
1334            return self.forced_ambiguity(MaybeInfo::AMBIGUOUS).map(|cand| cand.result);
1335        };
1336
1337        match proven_via {
1338            TraitGoalProvenVia::ParamEnv | TraitGoalProvenVia::AliasBound => {
1339                // Even when a trait bound has been proven using a where-bound, we
1340                // still need to consider alias-bounds for normalization, see
1341                // `tests/ui/next-solver/alias-bound-shadowed-by-env.rs`.
1342                let (mut candidates, _) = self
1343                    .assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::EnvAndBounds)?;
1344                debug!(?candidates);
1345
1346                // If the trait goal has been proven by using the environment, we want to treat
1347                // aliases as rigid if there are no applicable projection bounds in the environment.
1348                if candidates.is_empty() {
1349                    return inject_normalize_to_rigid_candidate(self);
1350                }
1351
1352                // If we're normalizing an GAT, we bail if using a where-bound would constrain
1353                // its generic arguments.
1354                if let Some(result) = inject_forced_ambiguity_candidate(self) {
1355                    return result;
1356                }
1357
1358                // We still need to prefer where-bounds over alias-bounds however.
1359                // See `tests/ui/winnowing/norm-where-bound-gt-alias-bound.rs`.
1360                if candidates.iter().any(|c| matches!(c.source, CandidateSource::ParamEnv(_))) {
1361                    candidates.retain(|c| matches!(c.source, CandidateSource::ParamEnv(_)));
1362                }
1363
1364                if let Some(response) = self.try_merge_candidates(&candidates) {
1365                    Ok(response)
1366                } else {
1367                    self.flounder(&candidates).map_err(Into::into)
1368                }
1369            }
1370            TraitGoalProvenVia::Misc => {
1371                let (mut candidates, _) =
1372                    self.assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::All)?;
1373
1374                // Prefer "orphaned" param-env normalization predicates, which are used
1375                // (for example, and ideally only) when proving item bounds for an impl.
1376                if candidates.iter().any(|c| matches!(c.source, CandidateSource::ParamEnv(_))) {
1377                    candidates.retain(|c| matches!(c.source, CandidateSource::ParamEnv(_)));
1378                }
1379
1380                // We drop specialized impls to allow normalization via a final impl here. In case
1381                // the specializing impl has different inference constraints from the specialized
1382                // impl, proving the trait goal is already ambiguous, so we never get here. This
1383                // means we can just ignore inference constraints and don't have to special-case
1384                // constraining the normalized-to `term`.
1385                self.filter_specialized_impls(AllowInferenceConstraints::Yes, &mut candidates);
1386                if let Some(response) = self.try_merge_candidates(&candidates) {
1387                    Ok(response)
1388                } else {
1389                    self.flounder(&candidates).map_err(Into::into)
1390                }
1391            }
1392        }
1393    }
1394
1395    /// Compute whether a param-env assumption is global or non-global after normalizing it.
1396    ///
1397    /// This is necessary because, for example, given:
1398    ///
1399    /// ```ignore,rust
1400    /// where
1401    ///     T: Trait<Assoc = u32>,
1402    ///     i32: From<T::Assoc>,
1403    /// ```
1404    ///
1405    /// The `i32: From<T::Assoc>` bound is non-global before normalization, but is global after.
1406    /// Since the old trait solver normalized param-envs eagerly, we want to emulate this
1407    /// behavior lazily.
1408    fn characterize_param_env_assumption(
1409        &mut self,
1410        param_env: I::ParamEnv,
1411        assumption: I::Clause,
1412    ) -> Result<(CandidateSource<I>, Certainty), NoSolution> {
1413        // FIXME: This should be fixed, but it also requires changing the behavior
1414        // in the old solver which is currently relied on.
1415        if assumption.has_bound_vars() {
1416            return Ok((CandidateSource::ParamEnv(ParamEnvSource::NonGlobal), Certainty::Yes));
1417        }
1418
1419        match assumption.visit_with(&mut FindParamInClause {
1420            ecx: self,
1421            param_env,
1422            universes: ::alloc::vec::Vec::new()vec![],
1423            recursion_depth: 0,
1424        }) {
1425            ControlFlow::Break(Err(NoSolution)) => Err(NoSolution),
1426            ControlFlow::Break(Ok(certainty)) => {
1427                Ok((CandidateSource::ParamEnv(ParamEnvSource::NonGlobal), certainty))
1428            }
1429            ControlFlow::Continue(()) => {
1430                Ok((CandidateSource::ParamEnv(ParamEnvSource::Global), Certainty::Yes))
1431            }
1432        }
1433    }
1434}
1435
1436struct FindParamInClause<'a, 'b, D: SolverDelegate<Interner = I>, I: Interner> {
1437    ecx: &'a mut EvalCtxt<'b, D>,
1438    param_env: I::ParamEnv,
1439    universes: Vec<Option<ty::UniverseIndex>>,
1440    recursion_depth: usize,
1441}
1442
1443impl<D, I> TypeVisitor<I> for FindParamInClause<'_, '_, D, I>
1444where
1445    D: SolverDelegate<Interner = I>,
1446    I: Interner,
1447{
1448    // - `Continue(())`: no generic parameter was found, the type is global
1449    // - `Break(Ok(Certainty::Yes))`: a generic parameter was found, the type is non-global
1450    // - `Break(Ok(Certainty::Maybe(_)))`: the recursion limit reached, assume that the type is non-global
1451    // - `Break(Err(NoSolution))`: normalization failed
1452    type Result = ControlFlow<Result<Certainty, NoSolution>>;
1453
1454    fn visit_binder<T: TypeVisitable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
1455        self.universes.push(None);
1456        t.super_visit_with(self)?;
1457        self.universes.pop();
1458        ControlFlow::Continue(())
1459    }
1460
1461    fn visit_ty(&mut self, ty: I::Ty) -> Self::Result {
1462        let ty = self.ecx.replace_bound_vars(ty, &mut self.universes);
1463        let Ok(ty) = self.ecx.structurally_normalize_ty(self.param_env, ty) else {
1464            return ControlFlow::Break(Err(NoSolution));
1465        };
1466
1467        match ty.kind() {
1468            ty::Placeholder(p) => {
1469                if p.universe() == ty::UniverseIndex::ROOT {
1470                    ControlFlow::Break(Ok(Certainty::Yes))
1471                } else {
1472                    ControlFlow::Continue(())
1473                }
1474            }
1475            ty::Infer(_) => ControlFlow::Break(Ok(Certainty::AMBIGUOUS)),
1476            _ if ty.has_type_flags(
1477                TypeFlags::HAS_PLACEHOLDER | TypeFlags::HAS_INFER | TypeFlags::HAS_ALIAS,
1478            ) =>
1479            {
1480                self.recursion_depth += 1;
1481                if self.recursion_depth > self.ecx.cx().recursion_limit() {
1482                    return ControlFlow::Break(Ok(Certainty::Maybe(MaybeInfo {
1483                        cause: MaybeCause::Overflow {
1484                            suggest_increasing_limit: true,
1485                            keep_constraints: false,
1486                        },
1487                        opaque_types_jank: OpaqueTypesJank::AllGood,
1488                        stalled_on_coroutines: StalledOnCoroutines::No,
1489                    })));
1490                }
1491                let result = ty.super_visit_with(self);
1492                self.recursion_depth -= 1;
1493                result
1494            }
1495            _ => ControlFlow::Continue(()),
1496        }
1497    }
1498
1499    fn visit_const(&mut self, ct: Const<I>) -> Self::Result {
1500        let ct = self.ecx.replace_bound_vars(ct, &mut self.universes);
1501        let Ok(ct) = self.ecx.structurally_normalize_const(self.param_env, ct) else {
1502            return ControlFlow::Break(Err(NoSolution));
1503        };
1504
1505        match ct.kind() {
1506            ty::ConstKind::Placeholder(p) => {
1507                if p.universe() == ty::UniverseIndex::ROOT {
1508                    ControlFlow::Break(Ok(Certainty::Yes))
1509                } else {
1510                    ControlFlow::Continue(())
1511                }
1512            }
1513            ty::ConstKind::Infer(_) => ControlFlow::Break(Ok(Certainty::AMBIGUOUS)),
1514            _ if ct.has_type_flags(
1515                TypeFlags::HAS_PLACEHOLDER | TypeFlags::HAS_INFER | TypeFlags::HAS_ALIAS,
1516            ) =>
1517            {
1518                // FIXME(mgca): we should also check the recursion limit here
1519                ct.super_visit_with(self)
1520            }
1521            _ => ControlFlow::Continue(()),
1522        }
1523    }
1524
1525    fn visit_region(&mut self, r: Region<I>) -> Self::Result {
1526        match self.ecx.eager_resolve_region(r).kind() {
1527            ty::ReStatic | ty::ReError(_) | ty::ReBound(..) => ControlFlow::Continue(()),
1528            ty::RePlaceholder(p) => {
1529                if p.universe() == ty::UniverseIndex::ROOT {
1530                    ControlFlow::Break(Ok(Certainty::Yes))
1531                } else {
1532                    ControlFlow::Continue(())
1533                }
1534            }
1535            ty::ReVar(_) => ControlFlow::Break(Ok(Certainty::Yes)),
1536            ty::ReErased | ty::ReEarlyParam(_) | ty::ReLateParam(_) => {
1537                {
    ::core::panicking::panic_fmt(format_args!("internal error: entered unreachable code: {0}",
            format_args!("unexpected region in param-env clause")));
}unreachable!("unexpected region in param-env clause")
1538            }
1539        }
1540    }
1541}