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::TraitSolverLangItem;
11use rustc_type_ir::{
12    self as ty, Interner, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt as _,
13    TypeVisitor, TypingMode, Upcast as _, elaborate,
14};
15use tracing::{debug, instrument};
16
17use super::trait_goals::TraitGoalProvenVia;
18use super::{has_only_region_constraints, inspect};
19use crate::delegate::SolverDelegate;
20use crate::solve::inspect::ProbeKind;
21use crate::solve::{
22    BuiltinImplSource, CandidateSource, CanonicalResponse, Certainty, EvalCtxt, Goal, GoalSource,
23    MaybeCause, NoSolution, ParamEnvSource, QueryResult,
24};
25
26enum AliasBoundKind {
27    SelfBounds,
28    NonSelfBounds,
29}
30
31/// A candidate is a possible way to prove a goal.
32///
33/// It consists of both the `source`, which describes how that goal would be proven,
34/// and the `result` when using the given `source`.
35#[derive_where(Clone, Debug; I: Interner)]
36pub(super) struct Candidate<I: Interner> {
37    pub(super) source: CandidateSource<I>,
38    pub(super) result: CanonicalResponse<I>,
39}
40
41/// Methods used to assemble candidates for either trait or projection goals.
42pub(super) trait GoalKind<D, I = <D as SolverDelegate>::Interner>:
43    TypeFoldable<I> + Copy + Eq + std::fmt::Display
44where
45    D: SolverDelegate<Interner = I>,
46    I: Interner,
47{
48    fn self_ty(self) -> I::Ty;
49
50    fn trait_ref(self, cx: I) -> ty::TraitRef<I>;
51
52    fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self;
53
54    fn trait_def_id(self, cx: I) -> I::DefId;
55
56    /// Consider a clause, which consists of a "assumption" and some "requirements",
57    /// to satisfy a goal. If the requirements hold, then attempt to satisfy our
58    /// goal by equating it with the assumption.
59    fn probe_and_consider_implied_clause(
60        ecx: &mut EvalCtxt<'_, D>,
61        parent_source: CandidateSource<I>,
62        goal: Goal<I, Self>,
63        assumption: I::Clause,
64        requirements: impl IntoIterator<Item = (GoalSource, Goal<I, I::Predicate>)>,
65    ) -> Result<Candidate<I>, NoSolution> {
66        Self::probe_and_match_goal_against_assumption(ecx, parent_source, goal, assumption, |ecx| {
67            for (nested_source, goal) in requirements {
68                ecx.add_goal(nested_source, goal);
69            }
70            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
71        })
72    }
73
74    /// Consider a clause specifically for a `dyn Trait` self type. This requires
75    /// additionally checking all of the supertraits and object bounds to hold,
76    /// since they're not implied by the well-formedness of the object type.
77    fn probe_and_consider_object_bound_candidate(
78        ecx: &mut EvalCtxt<'_, D>,
79        source: CandidateSource<I>,
80        goal: Goal<I, Self>,
81        assumption: I::Clause,
82    ) -> Result<Candidate<I>, NoSolution> {
83        Self::probe_and_match_goal_against_assumption(ecx, source, goal, assumption, |ecx| {
84            let cx = ecx.cx();
85            let ty::Dynamic(bounds, _, _) = goal.predicate.self_ty().kind() else {
86                panic!("expected object type in `probe_and_consider_object_bound_candidate`");
87            };
88            match structural_traits::predicates_for_object_candidate(
89                ecx,
90                goal.param_env,
91                goal.predicate.trait_ref(cx),
92                bounds,
93            ) {
94                Ok(requirements) => {
95                    ecx.add_goals(GoalSource::ImplWhereBound, requirements);
96                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
97                }
98                Err(_) => {
99                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
100                }
101            }
102        })
103    }
104
105    /// Assemble additional assumptions for an alias that are not included
106    /// in the item bounds of the alias. For now, this is limited to the
107    /// `explicit_implied_const_bounds` for an associated type.
108    fn consider_additional_alias_assumptions(
109        ecx: &mut EvalCtxt<'_, D>,
110        goal: Goal<I, Self>,
111        alias_ty: ty::AliasTy<I>,
112    ) -> Vec<Candidate<I>>;
113
114    fn probe_and_consider_param_env_candidate(
115        ecx: &mut EvalCtxt<'_, D>,
116        goal: Goal<I, Self>,
117        assumption: I::Clause,
118    ) -> Result<Candidate<I>, NoSolution> {
119        Self::fast_reject_assumption(ecx, goal, assumption)?;
120
121        // Dealing with `ParamEnv` candidates is a bit of a mess as we need to lazily
122        // check whether the candidate is global while considering normalization.
123        //
124        // We need to write into `source` inside of `match_assumption`, but need to access it
125        // in `probe` even if the candidate does not apply before we get there. We handle this
126        // by using a `Cell` here. We only ever write into it inside of `match_assumption`.
127        let source = Cell::new(CandidateSource::ParamEnv(ParamEnvSource::Global));
128        ecx.probe(|result: &QueryResult<I>| inspect::ProbeKind::TraitCandidate {
129            source: source.get(),
130            result: *result,
131        })
132        .enter(|ecx| {
133            Self::match_assumption(ecx, goal, assumption, |ecx| {
134                source.set(ecx.characterize_param_env_assumption(goal.param_env, assumption)?);
135                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
136            })
137        })
138        .map(|result| Candidate { source: source.get(), result })
139    }
140
141    /// Try equating an assumption predicate against a goal's predicate. If it
142    /// holds, then execute the `then` callback, which should do any additional
143    /// work, then produce a response (typically by executing
144    /// [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]).
145    fn probe_and_match_goal_against_assumption(
146        ecx: &mut EvalCtxt<'_, D>,
147        source: CandidateSource<I>,
148        goal: Goal<I, Self>,
149        assumption: I::Clause,
150        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
151    ) -> Result<Candidate<I>, NoSolution> {
152        Self::fast_reject_assumption(ecx, goal, assumption)?;
153
154        ecx.probe_trait_candidate(source)
155            .enter(|ecx| Self::match_assumption(ecx, goal, assumption, then))
156    }
157
158    /// Try to reject the assumption based off of simple heuristics, such as [`ty::ClauseKind`]
159    /// and `DefId`.
160    fn fast_reject_assumption(
161        ecx: &mut EvalCtxt<'_, D>,
162        goal: Goal<I, Self>,
163        assumption: I::Clause,
164    ) -> Result<(), NoSolution>;
165
166    /// Relate the goal and assumption.
167    fn match_assumption(
168        ecx: &mut EvalCtxt<'_, D>,
169        goal: Goal<I, Self>,
170        assumption: I::Clause,
171        then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
172    ) -> QueryResult<I>;
173
174    fn consider_impl_candidate(
175        ecx: &mut EvalCtxt<'_, D>,
176        goal: Goal<I, Self>,
177        impl_def_id: I::DefId,
178    ) -> Result<Candidate<I>, NoSolution>;
179
180    /// If the predicate contained an error, we want to avoid emitting unnecessary trait
181    /// errors but still want to emit errors for other trait goals. We have some special
182    /// handling for this case.
183    ///
184    /// Trait goals always hold while projection goals never do. This is a bit arbitrary
185    /// but prevents incorrect normalization while hiding any trait errors.
186    fn consider_error_guaranteed_candidate(
187        ecx: &mut EvalCtxt<'_, D>,
188        guar: I::ErrorGuaranteed,
189    ) -> Result<Candidate<I>, NoSolution>;
190
191    /// A type implements an `auto trait` if its components do as well.
192    ///
193    /// These components are given by built-in rules from
194    /// [`structural_traits::instantiate_constituent_tys_for_auto_trait`].
195    fn consider_auto_trait_candidate(
196        ecx: &mut EvalCtxt<'_, D>,
197        goal: Goal<I, Self>,
198    ) -> Result<Candidate<I>, NoSolution>;
199
200    /// A trait alias holds if the RHS traits and `where` clauses hold.
201    fn consider_trait_alias_candidate(
202        ecx: &mut EvalCtxt<'_, D>,
203        goal: Goal<I, Self>,
204    ) -> Result<Candidate<I>, NoSolution>;
205
206    /// A type is `Sized` if its tail component is `Sized`.
207    ///
208    /// These components are given by built-in rules from
209    /// [`structural_traits::instantiate_constituent_tys_for_sized_trait`].
210    fn consider_builtin_sized_candidate(
211        ecx: &mut EvalCtxt<'_, D>,
212        goal: Goal<I, Self>,
213    ) -> Result<Candidate<I>, NoSolution>;
214
215    /// A type is `Copy` or `Clone` if its components are `Copy` or `Clone`.
216    ///
217    /// These components are given by built-in rules from
218    /// [`structural_traits::instantiate_constituent_tys_for_copy_clone_trait`].
219    fn consider_builtin_copy_clone_candidate(
220        ecx: &mut EvalCtxt<'_, D>,
221        goal: Goal<I, Self>,
222    ) -> Result<Candidate<I>, NoSolution>;
223
224    /// A type is a `FnPtr` if it is of `FnPtr` type.
225    fn consider_builtin_fn_ptr_trait_candidate(
226        ecx: &mut EvalCtxt<'_, D>,
227        goal: Goal<I, Self>,
228    ) -> Result<Candidate<I>, NoSolution>;
229
230    /// A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>`
231    /// family of traits where `A` is given by the signature of the type.
232    fn consider_builtin_fn_trait_candidates(
233        ecx: &mut EvalCtxt<'_, D>,
234        goal: Goal<I, Self>,
235        kind: ty::ClosureKind,
236    ) -> Result<Candidate<I>, NoSolution>;
237
238    /// An async closure is known to implement the `AsyncFn<A>` family of traits
239    /// where `A` is given by the signature of the type.
240    fn consider_builtin_async_fn_trait_candidates(
241        ecx: &mut EvalCtxt<'_, D>,
242        goal: Goal<I, Self>,
243        kind: ty::ClosureKind,
244    ) -> Result<Candidate<I>, NoSolution>;
245
246    /// Compute the built-in logic of the `AsyncFnKindHelper` helper trait, which
247    /// is used internally to delay computation for async closures until after
248    /// upvar analysis is performed in HIR typeck.
249    fn consider_builtin_async_fn_kind_helper_candidate(
250        ecx: &mut EvalCtxt<'_, D>,
251        goal: Goal<I, Self>,
252    ) -> Result<Candidate<I>, NoSolution>;
253
254    /// `Tuple` is implemented if the `Self` type is a tuple.
255    fn consider_builtin_tuple_candidate(
256        ecx: &mut EvalCtxt<'_, D>,
257        goal: Goal<I, Self>,
258    ) -> Result<Candidate<I>, NoSolution>;
259
260    /// `Pointee` is always implemented.
261    ///
262    /// See the projection implementation for the `Metadata` types for all of
263    /// the built-in types. For structs, the metadata type is given by the struct
264    /// tail.
265    fn consider_builtin_pointee_candidate(
266        ecx: &mut EvalCtxt<'_, D>,
267        goal: Goal<I, Self>,
268    ) -> Result<Candidate<I>, NoSolution>;
269
270    /// A coroutine (that comes from an `async` desugaring) is known to implement
271    /// `Future<Output = O>`, where `O` is given by the coroutine's return type
272    /// that was computed during type-checking.
273    fn consider_builtin_future_candidate(
274        ecx: &mut EvalCtxt<'_, D>,
275        goal: Goal<I, Self>,
276    ) -> Result<Candidate<I>, NoSolution>;
277
278    /// A coroutine (that comes from a `gen` desugaring) is known to implement
279    /// `Iterator<Item = O>`, where `O` is given by the generator's yield type
280    /// that was computed during type-checking.
281    fn consider_builtin_iterator_candidate(
282        ecx: &mut EvalCtxt<'_, D>,
283        goal: Goal<I, Self>,
284    ) -> Result<Candidate<I>, NoSolution>;
285
286    /// A coroutine (that comes from a `gen` desugaring) is known to implement
287    /// `FusedIterator`
288    fn consider_builtin_fused_iterator_candidate(
289        ecx: &mut EvalCtxt<'_, D>,
290        goal: Goal<I, Self>,
291    ) -> Result<Candidate<I>, NoSolution>;
292
293    fn consider_builtin_async_iterator_candidate(
294        ecx: &mut EvalCtxt<'_, D>,
295        goal: Goal<I, Self>,
296    ) -> Result<Candidate<I>, NoSolution>;
297
298    /// A coroutine (that doesn't come from an `async` or `gen` desugaring) is known to
299    /// implement `Coroutine<R, Yield = Y, Return = O>`, given the resume, yield,
300    /// and return types of the coroutine computed during type-checking.
301    fn consider_builtin_coroutine_candidate(
302        ecx: &mut EvalCtxt<'_, D>,
303        goal: Goal<I, Self>,
304    ) -> Result<Candidate<I>, NoSolution>;
305
306    fn consider_builtin_discriminant_kind_candidate(
307        ecx: &mut EvalCtxt<'_, D>,
308        goal: Goal<I, Self>,
309    ) -> Result<Candidate<I>, NoSolution>;
310
311    fn consider_builtin_destruct_candidate(
312        ecx: &mut EvalCtxt<'_, D>,
313        goal: Goal<I, Self>,
314    ) -> Result<Candidate<I>, NoSolution>;
315
316    fn consider_builtin_transmute_candidate(
317        ecx: &mut EvalCtxt<'_, D>,
318        goal: Goal<I, Self>,
319    ) -> Result<Candidate<I>, NoSolution>;
320
321    fn consider_builtin_bikeshed_guaranteed_no_drop_candidate(
322        ecx: &mut EvalCtxt<'_, D>,
323        goal: Goal<I, Self>,
324    ) -> Result<Candidate<I>, NoSolution>;
325
326    /// Consider (possibly several) candidates to upcast or unsize a type to another
327    /// type, excluding the coercion of a sized type into a `dyn Trait`.
328    ///
329    /// We return the `BuiltinImplSource` for each candidate as it is needed
330    /// for unsize coercion in hir typeck and because it is difficult to
331    /// otherwise recompute this for codegen. This is a bit of a mess but the
332    /// easiest way to maintain the existing behavior for now.
333    fn consider_structural_builtin_unsize_candidates(
334        ecx: &mut EvalCtxt<'_, D>,
335        goal: Goal<I, Self>,
336    ) -> Vec<Candidate<I>>;
337}
338
339/// Allows callers of `assemble_and_evaluate_candidates` to choose whether to limit
340/// candidate assembly to param-env and alias-bound candidates.
341///
342/// On top of being a micro-optimization, as it avoids doing unnecessary work when
343/// a param-env trait bound candidate shadows impls for normalization, this is also
344/// required to prevent query cycles due to RPITIT inference. See the issue at:
345/// <https://github.com/rust-lang/trait-system-refactor-initiative/issues/173>.
346pub(super) enum AssembleCandidatesFrom {
347    All,
348    /// Only assemble candidates from the environment and alias bounds, ignoring
349    /// user-written and built-in impls. We only expect `ParamEnv` and `AliasBound`
350    /// candidates to be assembled.
351    EnvAndBounds,
352}
353
354impl<D, I> EvalCtxt<'_, D>
355where
356    D: SolverDelegate<Interner = I>,
357    I: Interner,
358{
359    pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<D>>(
360        &mut self,
361        goal: Goal<I, G>,
362        assemble_from: AssembleCandidatesFrom,
363    ) -> Vec<Candidate<I>> {
364        let Ok(normalized_self_ty) =
365            self.structurally_normalize_ty(goal.param_env, goal.predicate.self_ty())
366        else {
367            return vec![];
368        };
369
370        if normalized_self_ty.is_ty_var() {
371            debug!("self type has been normalized to infer");
372            return self.forced_ambiguity(MaybeCause::Ambiguity).into_iter().collect();
373        }
374
375        let goal: Goal<I, G> =
376            goal.with(self.cx(), goal.predicate.with_self_ty(self.cx(), normalized_self_ty));
377        // Vars that show up in the rest of the goal substs may have been constrained by
378        // normalizing the self type as well, since type variables are not uniquified.
379        let goal = self.resolve_vars_if_possible(goal);
380
381        let mut candidates = vec![];
382
383        if let TypingMode::Coherence = self.typing_mode() {
384            if let Ok(candidate) = self.consider_coherence_unknowable_candidate(goal) {
385                return vec![candidate];
386            }
387        }
388
389        self.assemble_alias_bound_candidates(goal, &mut candidates);
390        self.assemble_param_env_candidates(goal, &mut candidates);
391
392        match assemble_from {
393            AssembleCandidatesFrom::All => {
394                self.assemble_impl_candidates(goal, &mut candidates);
395                self.assemble_builtin_impl_candidates(goal, &mut candidates);
396                self.assemble_object_bound_candidates(goal, &mut candidates);
397            }
398            AssembleCandidatesFrom::EnvAndBounds => {}
399        }
400
401        candidates
402    }
403
404    pub(super) fn forced_ambiguity(
405        &mut self,
406        cause: MaybeCause,
407    ) -> Result<Candidate<I>, NoSolution> {
408        // This may fail if `try_evaluate_added_goals` overflows because it
409        // fails to reach a fixpoint but ends up getting an error after
410        // running for some additional step.
411        //
412        // cc trait-system-refactor-initiative#105
413        let source = CandidateSource::BuiltinImpl(BuiltinImplSource::Misc);
414        let certainty = Certainty::Maybe(cause);
415        self.probe_trait_candidate(source)
416            .enter(|this| this.evaluate_added_goals_and_make_canonical_response(certainty))
417    }
418
419    #[instrument(level = "trace", skip_all)]
420    fn assemble_impl_candidates<G: GoalKind<D>>(
421        &mut self,
422        goal: Goal<I, G>,
423        candidates: &mut Vec<Candidate<I>>,
424    ) {
425        let cx = self.cx();
426        cx.for_each_relevant_impl(
427            goal.predicate.trait_def_id(cx),
428            goal.predicate.self_ty(),
429            |impl_def_id| {
430                // For every `default impl`, there's always a non-default `impl`
431                // that will *also* apply. There's no reason to register a candidate
432                // for this impl, since it is *not* proof that the trait goal holds.
433                if cx.impl_is_default(impl_def_id) {
434                    return;
435                }
436
437                match G::consider_impl_candidate(self, goal, impl_def_id) {
438                    Ok(candidate) => candidates.push(candidate),
439                    Err(NoSolution) => (),
440                }
441            },
442        );
443    }
444
445    #[instrument(level = "trace", skip_all)]
446    fn assemble_builtin_impl_candidates<G: GoalKind<D>>(
447        &mut self,
448        goal: Goal<I, G>,
449        candidates: &mut Vec<Candidate<I>>,
450    ) {
451        let cx = self.cx();
452        let trait_def_id = goal.predicate.trait_def_id(cx);
453
454        // N.B. When assembling built-in candidates for lang items that are also
455        // `auto` traits, then the auto trait candidate that is assembled in
456        // `consider_auto_trait_candidate` MUST be disqualified to remain sound.
457        //
458        // Instead of adding the logic here, it's a better idea to add it in
459        // `EvalCtxt::disqualify_auto_trait_candidate_due_to_possible_impl` in
460        // `solve::trait_goals` instead.
461        let result = if let Err(guar) = goal.predicate.error_reported() {
462            G::consider_error_guaranteed_candidate(self, guar)
463        } else if cx.trait_is_auto(trait_def_id) {
464            G::consider_auto_trait_candidate(self, goal)
465        } else if cx.trait_is_alias(trait_def_id) {
466            G::consider_trait_alias_candidate(self, goal)
467        } else {
468            match cx.as_lang_item(trait_def_id) {
469                Some(TraitSolverLangItem::Sized) => G::consider_builtin_sized_candidate(self, goal),
470                Some(TraitSolverLangItem::Copy | TraitSolverLangItem::Clone) => {
471                    G::consider_builtin_copy_clone_candidate(self, goal)
472                }
473                Some(TraitSolverLangItem::Fn) => {
474                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::Fn)
475                }
476                Some(TraitSolverLangItem::FnMut) => {
477                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::FnMut)
478                }
479                Some(TraitSolverLangItem::FnOnce) => {
480                    G::consider_builtin_fn_trait_candidates(self, goal, ty::ClosureKind::FnOnce)
481                }
482                Some(TraitSolverLangItem::AsyncFn) => {
483                    G::consider_builtin_async_fn_trait_candidates(self, goal, ty::ClosureKind::Fn)
484                }
485                Some(TraitSolverLangItem::AsyncFnMut) => {
486                    G::consider_builtin_async_fn_trait_candidates(
487                        self,
488                        goal,
489                        ty::ClosureKind::FnMut,
490                    )
491                }
492                Some(TraitSolverLangItem::AsyncFnOnce) => {
493                    G::consider_builtin_async_fn_trait_candidates(
494                        self,
495                        goal,
496                        ty::ClosureKind::FnOnce,
497                    )
498                }
499                Some(TraitSolverLangItem::FnPtrTrait) => {
500                    G::consider_builtin_fn_ptr_trait_candidate(self, goal)
501                }
502                Some(TraitSolverLangItem::AsyncFnKindHelper) => {
503                    G::consider_builtin_async_fn_kind_helper_candidate(self, goal)
504                }
505                Some(TraitSolverLangItem::Tuple) => G::consider_builtin_tuple_candidate(self, goal),
506                Some(TraitSolverLangItem::PointeeTrait) => {
507                    G::consider_builtin_pointee_candidate(self, goal)
508                }
509                Some(TraitSolverLangItem::Future) => {
510                    G::consider_builtin_future_candidate(self, goal)
511                }
512                Some(TraitSolverLangItem::Iterator) => {
513                    G::consider_builtin_iterator_candidate(self, goal)
514                }
515                Some(TraitSolverLangItem::FusedIterator) => {
516                    G::consider_builtin_fused_iterator_candidate(self, goal)
517                }
518                Some(TraitSolverLangItem::AsyncIterator) => {
519                    G::consider_builtin_async_iterator_candidate(self, goal)
520                }
521                Some(TraitSolverLangItem::Coroutine) => {
522                    G::consider_builtin_coroutine_candidate(self, goal)
523                }
524                Some(TraitSolverLangItem::DiscriminantKind) => {
525                    G::consider_builtin_discriminant_kind_candidate(self, goal)
526                }
527                Some(TraitSolverLangItem::Destruct) => {
528                    G::consider_builtin_destruct_candidate(self, goal)
529                }
530                Some(TraitSolverLangItem::TransmuteTrait) => {
531                    G::consider_builtin_transmute_candidate(self, goal)
532                }
533                Some(TraitSolverLangItem::BikeshedGuaranteedNoDrop) => {
534                    G::consider_builtin_bikeshed_guaranteed_no_drop_candidate(self, goal)
535                }
536                _ => Err(NoSolution),
537            }
538        };
539
540        candidates.extend(result);
541
542        // There may be multiple unsize candidates for a trait with several supertraits:
543        // `trait Foo: Bar<A> + Bar<B>` and `dyn Foo: Unsize<dyn Bar<_>>`
544        if cx.is_lang_item(trait_def_id, TraitSolverLangItem::Unsize) {
545            candidates.extend(G::consider_structural_builtin_unsize_candidates(self, goal));
546        }
547    }
548
549    #[instrument(level = "trace", skip_all)]
550    fn assemble_param_env_candidates<G: GoalKind<D>>(
551        &mut self,
552        goal: Goal<I, G>,
553        candidates: &mut Vec<Candidate<I>>,
554    ) {
555        for assumption in goal.param_env.caller_bounds().iter() {
556            candidates.extend(G::probe_and_consider_param_env_candidate(self, goal, assumption));
557        }
558    }
559
560    #[instrument(level = "trace", skip_all)]
561    fn assemble_alias_bound_candidates<G: GoalKind<D>>(
562        &mut self,
563        goal: Goal<I, G>,
564        candidates: &mut Vec<Candidate<I>>,
565    ) {
566        let () = self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| {
567            ecx.assemble_alias_bound_candidates_recur(
568                goal.predicate.self_ty(),
569                goal,
570                candidates,
571                AliasBoundKind::SelfBounds,
572            );
573        });
574    }
575
576    /// For some deeply nested `<T>::A::B::C::D` rigid associated type,
577    /// we should explore the item bounds for all levels, since the
578    /// `associated_type_bounds` feature means that a parent associated
579    /// type may carry bounds for a nested associated type.
580    ///
581    /// If we have a projection, check that its self type is a rigid projection.
582    /// If so, continue searching by recursively calling after normalization.
583    // FIXME: This may recurse infinitely, but I can't seem to trigger it without
584    // hitting another overflow error something. Add a depth parameter needed later.
585    fn assemble_alias_bound_candidates_recur<G: GoalKind<D>>(
586        &mut self,
587        self_ty: I::Ty,
588        goal: Goal<I, G>,
589        candidates: &mut Vec<Candidate<I>>,
590        consider_self_bounds: AliasBoundKind,
591    ) {
592        let (kind, alias_ty) = match self_ty.kind() {
593            ty::Bool
594            | ty::Char
595            | ty::Int(_)
596            | ty::Uint(_)
597            | ty::Float(_)
598            | ty::Adt(_, _)
599            | ty::Foreign(_)
600            | ty::Str
601            | ty::Array(_, _)
602            | ty::Pat(_, _)
603            | ty::Slice(_)
604            | ty::RawPtr(_, _)
605            | ty::Ref(_, _, _)
606            | ty::FnDef(_, _)
607            | ty::FnPtr(..)
608            | ty::UnsafeBinder(_)
609            | ty::Dynamic(..)
610            | ty::Closure(..)
611            | ty::CoroutineClosure(..)
612            | ty::Coroutine(..)
613            | ty::CoroutineWitness(..)
614            | ty::Never
615            | ty::Tuple(_)
616            | ty::Param(_)
617            | ty::Placeholder(..)
618            | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
619            | ty::Error(_) => return,
620            ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) | ty::Bound(..) => {
621                panic!("unexpected self type for `{goal:?}`")
622            }
623
624            ty::Infer(ty::TyVar(_)) => {
625                // If we hit infer when normalizing the self type of an alias,
626                // then bail with ambiguity. We should never encounter this on
627                // the *first* iteration of this recursive function.
628                if let Ok(result) =
629                    self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
630                {
631                    candidates.push(Candidate { source: CandidateSource::AliasBound, result });
632                }
633                return;
634            }
635
636            ty::Alias(kind @ (ty::Projection | ty::Opaque), alias_ty) => (kind, alias_ty),
637            ty::Alias(ty::Inherent | ty::Free, _) => {
638                self.cx().delay_bug(format!("could not normalize {self_ty:?}, it is not WF"));
639                return;
640            }
641        };
642
643        match consider_self_bounds {
644            AliasBoundKind::SelfBounds => {
645                for assumption in self
646                    .cx()
647                    .item_self_bounds(alias_ty.def_id)
648                    .iter_instantiated(self.cx(), alias_ty.args)
649                {
650                    candidates.extend(G::probe_and_consider_implied_clause(
651                        self,
652                        CandidateSource::AliasBound,
653                        goal,
654                        assumption,
655                        [],
656                    ));
657                }
658            }
659            AliasBoundKind::NonSelfBounds => {
660                for assumption in self
661                    .cx()
662                    .item_non_self_bounds(alias_ty.def_id)
663                    .iter_instantiated(self.cx(), alias_ty.args)
664                {
665                    candidates.extend(G::probe_and_consider_implied_clause(
666                        self,
667                        CandidateSource::AliasBound,
668                        goal,
669                        assumption,
670                        [],
671                    ));
672                }
673            }
674        }
675
676        candidates.extend(G::consider_additional_alias_assumptions(self, goal, alias_ty));
677
678        if kind != ty::Projection {
679            return;
680        }
681
682        // Recurse on the self type of the projection.
683        match self.structurally_normalize_ty(goal.param_env, alias_ty.self_ty()) {
684            Ok(next_self_ty) => self.assemble_alias_bound_candidates_recur(
685                next_self_ty,
686                goal,
687                candidates,
688                AliasBoundKind::NonSelfBounds,
689            ),
690            Err(NoSolution) => {}
691        }
692    }
693
694    #[instrument(level = "trace", skip_all)]
695    fn assemble_object_bound_candidates<G: GoalKind<D>>(
696        &mut self,
697        goal: Goal<I, G>,
698        candidates: &mut Vec<Candidate<I>>,
699    ) {
700        let cx = self.cx();
701        if !cx.trait_may_be_implemented_via_object(goal.predicate.trait_def_id(cx)) {
702            return;
703        }
704
705        let self_ty = goal.predicate.self_ty();
706        let bounds = match self_ty.kind() {
707            ty::Bool
708            | ty::Char
709            | ty::Int(_)
710            | ty::Uint(_)
711            | ty::Float(_)
712            | ty::Adt(_, _)
713            | ty::Foreign(_)
714            | ty::Str
715            | ty::Array(_, _)
716            | ty::Pat(_, _)
717            | ty::Slice(_)
718            | ty::RawPtr(_, _)
719            | ty::Ref(_, _, _)
720            | ty::FnDef(_, _)
721            | ty::FnPtr(..)
722            | ty::UnsafeBinder(_)
723            | ty::Alias(..)
724            | ty::Closure(..)
725            | ty::CoroutineClosure(..)
726            | ty::Coroutine(..)
727            | ty::CoroutineWitness(..)
728            | ty::Never
729            | ty::Tuple(_)
730            | ty::Param(_)
731            | ty::Placeholder(..)
732            | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
733            | ty::Error(_) => return,
734            ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
735            | ty::Bound(..) => panic!("unexpected self type for `{goal:?}`"),
736            ty::Dynamic(bounds, ..) => bounds,
737        };
738
739        // Do not consider built-in object impls for dyn-incompatible types.
740        if bounds.principal_def_id().is_some_and(|def_id| !cx.trait_is_dyn_compatible(def_id)) {
741            return;
742        }
743
744        // Consider all of the auto-trait and projection bounds, which don't
745        // need to be recorded as a `BuiltinImplSource::Object` since they don't
746        // really have a vtable base...
747        for bound in bounds.iter() {
748            match bound.skip_binder() {
749                ty::ExistentialPredicate::Trait(_) => {
750                    // Skip principal
751                }
752                ty::ExistentialPredicate::Projection(_)
753                | ty::ExistentialPredicate::AutoTrait(_) => {
754                    candidates.extend(G::probe_and_consider_object_bound_candidate(
755                        self,
756                        CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
757                        goal,
758                        bound.with_self_ty(cx, self_ty),
759                    ));
760                }
761            }
762        }
763
764        // FIXME: We only need to do *any* of this if we're considering a trait goal,
765        // since we don't need to look at any supertrait or anything if we are doing
766        // a projection goal.
767        if let Some(principal) = bounds.principal() {
768            let principal_trait_ref = principal.with_self_ty(cx, self_ty);
769            for (idx, assumption) in elaborate::supertraits(cx, principal_trait_ref).enumerate() {
770                candidates.extend(G::probe_and_consider_object_bound_candidate(
771                    self,
772                    CandidateSource::BuiltinImpl(BuiltinImplSource::Object(idx)),
773                    goal,
774                    assumption.upcast(cx),
775                ));
776            }
777        }
778    }
779
780    /// In coherence we have to not only care about all impls we know about, but
781    /// also consider impls which may get added in a downstream or sibling crate
782    /// or which an upstream impl may add in a minor release.
783    ///
784    /// To do so we return a single ambiguous candidate in case such an unknown
785    /// impl could apply to the current goal.
786    #[instrument(level = "trace", skip_all)]
787    fn consider_coherence_unknowable_candidate<G: GoalKind<D>>(
788        &mut self,
789        goal: Goal<I, G>,
790    ) -> Result<Candidate<I>, NoSolution> {
791        self.probe_trait_candidate(CandidateSource::CoherenceUnknowable).enter(|ecx| {
792            let cx = ecx.cx();
793            let trait_ref = goal.predicate.trait_ref(cx);
794            if ecx.trait_ref_is_knowable(goal.param_env, trait_ref)? {
795                Err(NoSolution)
796            } else {
797                // While the trait bound itself may be unknowable, we may be able to
798                // prove that a super trait is not implemented. For this, we recursively
799                // prove the super trait bounds of the current goal.
800                //
801                // We skip the goal itself as that one would cycle.
802                let predicate: I::Predicate = trait_ref.upcast(cx);
803                ecx.add_goals(
804                    GoalSource::Misc,
805                    elaborate::elaborate(cx, [predicate])
806                        .skip(1)
807                        .map(|predicate| goal.with(cx, predicate)),
808                );
809                ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
810            }
811        })
812    }
813}
814
815pub(super) enum AllowInferenceConstraints {
816    Yes,
817    No,
818}
819
820impl<D, I> EvalCtxt<'_, D>
821where
822    D: SolverDelegate<Interner = I>,
823    I: Interner,
824{
825    /// Check whether we can ignore impl candidates due to specialization.
826    ///
827    /// This is only necessary for `feature(specialization)` and seems quite ugly.
828    pub(super) fn filter_specialized_impls(
829        &mut self,
830        allow_inference_constraints: AllowInferenceConstraints,
831        candidates: &mut Vec<Candidate<I>>,
832    ) {
833        match self.typing_mode() {
834            TypingMode::Coherence => return,
835            TypingMode::Analysis { .. }
836            | TypingMode::Borrowck { .. }
837            | TypingMode::PostBorrowckAnalysis { .. }
838            | TypingMode::PostAnalysis => {}
839        }
840
841        let mut i = 0;
842        'outer: while i < candidates.len() {
843            let CandidateSource::Impl(victim_def_id) = candidates[i].source else {
844                i += 1;
845                continue;
846            };
847
848            for (j, c) in candidates.iter().enumerate() {
849                if i == j {
850                    continue;
851                }
852
853                let CandidateSource::Impl(other_def_id) = c.source else {
854                    continue;
855                };
856
857                // See if we can toss out `victim` based on specialization.
858                //
859                // While this requires us to know *for sure* that the `lhs` impl applies
860                // we still use modulo regions here. This is fine as specialization currently
861                // assumes that specializing impls have to be always applicable, meaning that
862                // the only allowed region constraints may be constraints also present on the default impl.
863                if matches!(allow_inference_constraints, AllowInferenceConstraints::Yes)
864                    || has_only_region_constraints(c.result)
865                {
866                    if self.cx().impl_specializes(other_def_id, victim_def_id) {
867                        candidates.remove(i);
868                        continue 'outer;
869                    }
870                }
871            }
872
873            i += 1;
874        }
875    }
876
877    /// Assemble and merge candidates for goals which are related to an underlying trait
878    /// goal. Right now, this is normalizes-to and host effect goals.
879    ///
880    /// We sadly can't simply take all possible candidates for normalization goals
881    /// and check whether they result in the same constraints. We want to make sure
882    /// that trying to normalize an alias doesn't result in constraints which aren't
883    /// otherwise required.
884    ///
885    /// Most notably, when proving a trait goal by via a where-bound, we should not
886    /// normalize via impls which have stricter region constraints than the where-bound:
887    ///
888    /// ```rust
889    /// trait Trait<'a> {
890    ///     type Assoc;
891    /// }
892    ///
893    /// impl<'a, T: 'a> Trait<'a> for T {
894    ///     type Assoc = u32;
895    /// }
896    ///
897    /// fn with_bound<'a, T: Trait<'a>>(_value: T::Assoc) {}
898    /// ```
899    ///
900    /// The where-bound of `with_bound` doesn't specify the associated type, so we would
901    /// only be able to normalize `<T as Trait<'a>>::Assoc` by using the impl. This impl
902    /// adds a `T: 'a` bound however, which would result in a region error. Given that the
903    /// user explicitly wrote that `T: Trait<'a>` holds, this is undesirable and we instead
904    /// treat the alias as rigid.
905    ///
906    /// See trait-system-refactor-initiative#124 for more details.
907    #[instrument(level = "debug", skip(self, inject_normalize_to_rigid_candidate), ret)]
908    pub(super) fn assemble_and_merge_candidates<G: GoalKind<D>>(
909        &mut self,
910        proven_via: Option<TraitGoalProvenVia>,
911        goal: Goal<I, G>,
912        inject_normalize_to_rigid_candidate: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
913    ) -> QueryResult<I> {
914        let Some(proven_via) = proven_via else {
915            // We don't care about overflow. If proving the trait goal overflowed, then
916            // it's enough to report an overflow error for that, we don't also have to
917            // overflow during normalization.
918            //
919            // We use `forced_ambiguity` here over `make_ambiguous_response_no_constraints`
920            // because the former will also record a built-in candidate in the inspector.
921            return self.forced_ambiguity(MaybeCause::Ambiguity).map(|cand| cand.result);
922        };
923
924        match proven_via {
925            TraitGoalProvenVia::ParamEnv | TraitGoalProvenVia::AliasBound => {
926                // Even when a trait bound has been proven using a where-bound, we
927                // still need to consider alias-bounds for normalization, see
928                // `tests/ui/next-solver/alias-bound-shadowed-by-env.rs`.
929                let candidates_from_env_and_bounds: Vec<_> = self
930                    .assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::EnvAndBounds);
931
932                // We still need to prefer where-bounds over alias-bounds however.
933                // See `tests/ui/winnowing/norm-where-bound-gt-alias-bound.rs`.
934                let mut considered_candidates: Vec<_> = if candidates_from_env_and_bounds
935                    .iter()
936                    .any(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
937                {
938                    candidates_from_env_and_bounds
939                        .into_iter()
940                        .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
941                        .map(|c| c.result)
942                        .collect()
943                } else {
944                    candidates_from_env_and_bounds.into_iter().map(|c| c.result).collect()
945                };
946
947                // If the trait goal has been proven by using the environment, we want to treat
948                // aliases as rigid if there are no applicable projection bounds in the environment.
949                if considered_candidates.is_empty() {
950                    if let Ok(response) = inject_normalize_to_rigid_candidate(self) {
951                        considered_candidates.push(response);
952                    }
953                }
954
955                if let Some(response) = self.try_merge_responses(&considered_candidates) {
956                    Ok(response)
957                } else {
958                    self.flounder(&considered_candidates)
959                }
960            }
961            TraitGoalProvenVia::Misc => {
962                let mut candidates =
963                    self.assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::All);
964
965                // Prefer "orphaned" param-env normalization predicates, which are used
966                // (for example, and ideally only) when proving item bounds for an impl.
967                let candidates_from_env: Vec<_> = candidates
968                    .iter()
969                    .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
970                    .map(|c| c.result)
971                    .collect();
972                if let Some(response) = self.try_merge_responses(&candidates_from_env) {
973                    return Ok(response);
974                }
975
976                // We drop specialized impls to allow normalization via a final impl here. In case
977                // the specializing impl has different inference constraints from the specialized
978                // impl, proving the trait goal is already ambiguous, so we never get here. This
979                // means we can just ignore inference constraints and don't have to special-case
980                // constraining the normalized-to `term`.
981                self.filter_specialized_impls(AllowInferenceConstraints::Yes, &mut candidates);
982
983                let responses: Vec<_> = candidates.iter().map(|c| c.result).collect();
984                if let Some(response) = self.try_merge_responses(&responses) {
985                    Ok(response)
986                } else {
987                    self.flounder(&responses)
988                }
989            }
990        }
991    }
992
993    /// Compute whether a param-env assumption is global or non-global after normalizing it.
994    ///
995    /// This is necessary because, for example, given:
996    ///
997    /// ```ignore,rust
998    /// where
999    ///     T: Trait<Assoc = u32>,
1000    ///     i32: From<T::Assoc>,
1001    /// ```
1002    ///
1003    /// The `i32: From<T::Assoc>` bound is non-global before normalization, but is global after.
1004    /// Since the old trait solver normalized param-envs eagerly, we want to emulate this
1005    /// behavior lazily.
1006    fn characterize_param_env_assumption(
1007        &mut self,
1008        param_env: I::ParamEnv,
1009        assumption: I::Clause,
1010    ) -> Result<CandidateSource<I>, NoSolution> {
1011        // FIXME: This should be fixed, but it also requires changing the behavior
1012        // in the old solver which is currently relied on.
1013        if assumption.has_bound_vars() {
1014            return Ok(CandidateSource::ParamEnv(ParamEnvSource::NonGlobal));
1015        }
1016
1017        match assumption.visit_with(&mut FindParamInClause { ecx: self, param_env }) {
1018            ControlFlow::Break(Err(NoSolution)) => Err(NoSolution),
1019            ControlFlow::Break(Ok(())) => Ok(CandidateSource::ParamEnv(ParamEnvSource::NonGlobal)),
1020            ControlFlow::Continue(()) => Ok(CandidateSource::ParamEnv(ParamEnvSource::Global)),
1021        }
1022    }
1023}
1024
1025struct FindParamInClause<'a, 'b, D: SolverDelegate<Interner = I>, I: Interner> {
1026    ecx: &'a mut EvalCtxt<'b, D>,
1027    param_env: I::ParamEnv,
1028}
1029
1030impl<D, I> TypeVisitor<I> for FindParamInClause<'_, '_, D, I>
1031where
1032    D: SolverDelegate<Interner = I>,
1033    I: Interner,
1034{
1035    type Result = ControlFlow<Result<(), NoSolution>>;
1036
1037    fn visit_binder<T: TypeFoldable<I>>(&mut self, t: &ty::Binder<I, T>) -> Self::Result {
1038        self.ecx.enter_forall(t.clone(), |ecx, v| {
1039            v.visit_with(&mut FindParamInClause { ecx, param_env: self.param_env })
1040        })
1041    }
1042
1043    fn visit_ty(&mut self, ty: I::Ty) -> Self::Result {
1044        let Ok(ty) = self.ecx.structurally_normalize_ty(self.param_env, ty) else {
1045            return ControlFlow::Break(Err(NoSolution));
1046        };
1047
1048        if let ty::Placeholder(_) = ty.kind() {
1049            ControlFlow::Break(Ok(()))
1050        } else {
1051            ty.super_visit_with(self)
1052        }
1053    }
1054
1055    fn visit_const(&mut self, ct: I::Const) -> Self::Result {
1056        let Ok(ct) = self.ecx.structurally_normalize_const(self.param_env, ct) else {
1057            return ControlFlow::Break(Err(NoSolution));
1058        };
1059
1060        if let ty::ConstKind::Placeholder(_) = ct.kind() {
1061            ControlFlow::Break(Ok(()))
1062        } else {
1063            ct.super_visit_with(self)
1064        }
1065    }
1066
1067    fn visit_region(&mut self, r: I::Region) -> Self::Result {
1068        match self.ecx.eager_resolve_region(r).kind() {
1069            ty::ReStatic | ty::ReError(_) => ControlFlow::Continue(()),
1070            ty::ReVar(_) | ty::RePlaceholder(_) => ControlFlow::Break(Ok(())),
1071            ty::ReErased | ty::ReEarlyParam(_) | ty::ReLateParam(_) | ty::ReBound(..) => {
1072                unreachable!()
1073            }
1074        }
1075    }
1076}
rustc_next_trait_solver/solve/assembly/mod.rs

rustc_next_trait_solver/solve/assembly/
mod.rs
