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