1use rustc_type_ir::data_structures::IndexSet;
4use rustc_type_ir::fast_reject::DeepRejectCtxt;
5use rustc_type_ir::inherent::*;
6use rustc_type_ir::lang_items::TraitSolverLangItem;
7use rustc_type_ir::solve::{CanonicalResponse, SizedTraitKind};
8use rustc_type_ir::{
9 self as ty, Interner, Movability, TraitPredicate, TraitRef, TypeVisitableExt as _, TypingMode,
10 Upcast as _, elaborate,
11};
12use tracing::{debug, instrument, trace};
13
14use crate::delegate::SolverDelegate;
15use crate::solve::assembly::structural_traits::{self, AsyncCallableRelevantTypes};
16use crate::solve::assembly::{self, AllowInferenceConstraints, AssembleCandidatesFrom, Candidate};
17use crate::solve::inspect::ProbeKind;
18use crate::solve::{
19 BuiltinImplSource, CandidateSource, Certainty, EvalCtxt, Goal, GoalSource, MaybeCause,
20 NoSolution, ParamEnvSource, QueryResult, has_only_region_constraints,
21};
22
23impl<D, I> assembly::GoalKind<D> for TraitPredicate<I>
24where
25 D: SolverDelegate<Interner = I>,
26 I: Interner,
27{
28 fn self_ty(self) -> I::Ty {
29 self.self_ty()
30 }
31
32 fn trait_ref(self, _: I) -> ty::TraitRef<I> {
33 self.trait_ref
34 }
35
36 fn with_self_ty(self, cx: I, self_ty: I::Ty) -> Self {
37 self.with_self_ty(cx, self_ty)
38 }
39
40 fn trait_def_id(self, _: I) -> I::DefId {
41 self.def_id()
42 }
43
44 fn consider_additional_alias_assumptions(
45 _ecx: &mut EvalCtxt<'_, D>,
46 _goal: Goal<I, Self>,
47 _alias_ty: ty::AliasTy<I>,
48 ) -> Vec<Candidate<I>> {
49 vec![]
50 }
51
52 fn consider_impl_candidate(
53 ecx: &mut EvalCtxt<'_, D>,
54 goal: Goal<I, TraitPredicate<I>>,
55 impl_def_id: I::DefId,
56 ) -> Result<Candidate<I>, NoSolution> {
57 let cx = ecx.cx();
58
59 let impl_trait_ref = cx.impl_trait_ref(impl_def_id);
60 if !DeepRejectCtxt::relate_rigid_infer(ecx.cx())
61 .args_may_unify(goal.predicate.trait_ref.args, impl_trait_ref.skip_binder().args)
62 {
63 return Err(NoSolution);
64 }
65
66 let impl_polarity = cx.impl_polarity(impl_def_id);
69 let maximal_certainty = match (impl_polarity, goal.predicate.polarity) {
70 (ty::ImplPolarity::Reservation, _) => match ecx.typing_mode() {
73 TypingMode::Coherence => Certainty::AMBIGUOUS,
74 TypingMode::Analysis { .. }
75 | TypingMode::Borrowck { .. }
76 | TypingMode::PostBorrowckAnalysis { .. }
77 | TypingMode::PostAnalysis => return Err(NoSolution),
78 },
79
80 (ty::ImplPolarity::Positive, ty::PredicatePolarity::Positive)
82 | (ty::ImplPolarity::Negative, ty::PredicatePolarity::Negative) => Certainty::Yes,
83
84 (ty::ImplPolarity::Positive, ty::PredicatePolarity::Negative)
86 | (ty::ImplPolarity::Negative, ty::PredicatePolarity::Positive) => {
87 return Err(NoSolution);
88 }
89 };
90
91 ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| {
92 let impl_args = ecx.fresh_args_for_item(impl_def_id);
93 ecx.record_impl_args(impl_args);
94 let impl_trait_ref = impl_trait_ref.instantiate(cx, impl_args);
95
96 ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
97 let where_clause_bounds = cx
98 .predicates_of(impl_def_id)
99 .iter_instantiated(cx, impl_args)
100 .map(|pred| goal.with(cx, pred));
101 ecx.add_goals(GoalSource::ImplWhereBound, where_clause_bounds);
102
103 ecx.add_goals(
107 GoalSource::Misc,
108 cx.impl_super_outlives(impl_def_id)
109 .iter_instantiated(cx, impl_args)
110 .map(|pred| goal.with(cx, pred)),
111 );
112
113 ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty)
114 })
115 }
116
117 fn consider_error_guaranteed_candidate(
118 ecx: &mut EvalCtxt<'_, D>,
119 _guar: I::ErrorGuaranteed,
120 ) -> Result<Candidate<I>, NoSolution> {
121 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
122 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
123 }
124
125 fn fast_reject_assumption(
126 ecx: &mut EvalCtxt<'_, D>,
127 goal: Goal<I, Self>,
128 assumption: I::Clause,
129 ) -> Result<(), NoSolution> {
130 fn trait_def_id_matches<I: Interner>(
131 cx: I,
132 clause_def_id: I::DefId,
133 goal_def_id: I::DefId,
134 ) -> bool {
135 clause_def_id == goal_def_id
136 || (cx.is_lang_item(clause_def_id, TraitSolverLangItem::Sized)
141 && cx.is_lang_item(goal_def_id, TraitSolverLangItem::MetaSized))
142 }
143
144 if let Some(trait_clause) = assumption.as_trait_clause()
145 && trait_clause.polarity() == goal.predicate.polarity
146 && trait_def_id_matches(ecx.cx(), trait_clause.def_id(), goal.predicate.def_id())
147 && DeepRejectCtxt::relate_rigid_rigid(ecx.cx()).args_may_unify(
148 goal.predicate.trait_ref.args,
149 trait_clause.skip_binder().trait_ref.args,
150 )
151 {
152 return Ok(());
153 } else {
154 Err(NoSolution)
155 }
156 }
157
158 fn match_assumption(
159 ecx: &mut EvalCtxt<'_, D>,
160 goal: Goal<I, Self>,
161 assumption: I::Clause,
162 then: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
163 ) -> QueryResult<I> {
164 let trait_clause = assumption.as_trait_clause().unwrap();
165
166 if ecx.cx().is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::MetaSized)
170 && ecx.cx().is_lang_item(trait_clause.def_id(), TraitSolverLangItem::Sized)
171 {
172 let meta_sized_clause =
173 trait_predicate_with_def_id(ecx.cx(), trait_clause, goal.predicate.def_id());
174 return Self::match_assumption(ecx, goal, meta_sized_clause, then);
175 }
176
177 let assumption_trait_pred = ecx.instantiate_binder_with_infer(trait_clause);
178 ecx.eq(goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref)?;
179
180 then(ecx)
181 }
182
183 fn consider_auto_trait_candidate(
184 ecx: &mut EvalCtxt<'_, D>,
185 goal: Goal<I, Self>,
186 ) -> Result<Candidate<I>, NoSolution> {
187 let cx = ecx.cx();
188 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
189 return Err(NoSolution);
190 }
191
192 if let Some(result) = ecx.disqualify_auto_trait_candidate_due_to_possible_impl(goal) {
193 return result;
194 }
195
196 if cx.trait_is_unsafe(goal.predicate.def_id())
199 && goal.predicate.self_ty().has_unsafe_fields()
200 {
201 return Err(NoSolution);
202 }
203
204 if let ty::Alias(ty::Opaque, opaque_ty) = goal.predicate.self_ty().kind() {
220 debug_assert!(ecx.opaque_type_is_rigid(opaque_ty.def_id));
221 for item_bound in cx.item_self_bounds(opaque_ty.def_id).skip_binder() {
222 if item_bound
223 .as_trait_clause()
224 .is_some_and(|b| b.def_id() == goal.predicate.def_id())
225 {
226 return Err(NoSolution);
227 }
228 }
229 }
230
231 if let Some(cand) = ecx.try_stall_coroutine_witness(goal.predicate.self_ty()) {
233 return cand;
234 }
235
236 ecx.probe_and_evaluate_goal_for_constituent_tys(
237 CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
238 goal,
239 structural_traits::instantiate_constituent_tys_for_auto_trait,
240 )
241 }
242
243 fn consider_trait_alias_candidate(
244 ecx: &mut EvalCtxt<'_, D>,
245 goal: Goal<I, Self>,
246 ) -> Result<Candidate<I>, NoSolution> {
247 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
248 return Err(NoSolution);
249 }
250
251 let cx = ecx.cx();
252
253 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
254 let nested_obligations = cx
255 .predicates_of(goal.predicate.def_id())
256 .iter_instantiated(cx, goal.predicate.trait_ref.args)
257 .map(|p| goal.with(cx, p));
258 ecx.add_goals(GoalSource::Misc, nested_obligations);
264 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
265 })
266 }
267
268 fn consider_builtin_sizedness_candidates(
269 ecx: &mut EvalCtxt<'_, D>,
270 goal: Goal<I, Self>,
271 sizedness: SizedTraitKind,
272 ) -> Result<Candidate<I>, NoSolution> {
273 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
274 return Err(NoSolution);
275 }
276
277 ecx.probe_and_evaluate_goal_for_constituent_tys(
278 CandidateSource::BuiltinImpl(BuiltinImplSource::Trivial),
279 goal,
280 |ecx, ty| {
281 structural_traits::instantiate_constituent_tys_for_sizedness_trait(
282 ecx, sizedness, ty,
283 )
284 },
285 )
286 }
287
288 fn consider_builtin_copy_clone_candidate(
289 ecx: &mut EvalCtxt<'_, D>,
290 goal: Goal<I, Self>,
291 ) -> Result<Candidate<I>, NoSolution> {
292 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
293 return Err(NoSolution);
294 }
295
296 if let Some(cand) = ecx.try_stall_coroutine_witness(goal.predicate.self_ty()) {
298 return cand;
299 }
300
301 ecx.probe_and_evaluate_goal_for_constituent_tys(
302 CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
303 goal,
304 structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
305 )
306 }
307
308 fn consider_builtin_fn_ptr_trait_candidate(
309 ecx: &mut EvalCtxt<'_, D>,
310 goal: Goal<I, Self>,
311 ) -> Result<Candidate<I>, NoSolution> {
312 let self_ty = goal.predicate.self_ty();
313 match goal.predicate.polarity {
314 ty::PredicatePolarity::Positive => {
316 if self_ty.is_fn_ptr() {
317 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
318 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
319 })
320 } else {
321 Err(NoSolution)
322 }
323 }
324 ty::PredicatePolarity::Negative => {
326 if !self_ty.is_fn_ptr() && self_ty.is_known_rigid() {
329 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
330 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
331 })
332 } else {
333 Err(NoSolution)
334 }
335 }
336 }
337 }
338
339 fn consider_builtin_fn_trait_candidates(
340 ecx: &mut EvalCtxt<'_, D>,
341 goal: Goal<I, Self>,
342 goal_kind: ty::ClosureKind,
343 ) -> Result<Candidate<I>, NoSolution> {
344 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
345 return Err(NoSolution);
346 }
347
348 let cx = ecx.cx();
349 let tupled_inputs_and_output =
350 match structural_traits::extract_tupled_inputs_and_output_from_callable(
351 cx,
352 goal.predicate.self_ty(),
353 goal_kind,
354 )? {
355 Some(a) => a,
356 None => {
357 return ecx.forced_ambiguity(MaybeCause::Ambiguity);
358 }
359 };
360
361 let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| {
364 ty::TraitRef::new(cx, cx.require_lang_item(TraitSolverLangItem::Sized), [output])
365 });
366
367 let pred = tupled_inputs_and_output
368 .map_bound(|(inputs, _)| {
369 ty::TraitRef::new(cx, goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
370 })
371 .upcast(cx);
372 Self::probe_and_consider_implied_clause(
373 ecx,
374 CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
375 goal,
376 pred,
377 [(GoalSource::ImplWhereBound, goal.with(cx, output_is_sized_pred))],
378 )
379 }
380
381 fn consider_builtin_async_fn_trait_candidates(
382 ecx: &mut EvalCtxt<'_, D>,
383 goal: Goal<I, Self>,
384 goal_kind: ty::ClosureKind,
385 ) -> Result<Candidate<I>, NoSolution> {
386 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
387 return Err(NoSolution);
388 }
389
390 let cx = ecx.cx();
391 let (tupled_inputs_and_output_and_coroutine, nested_preds) =
392 structural_traits::extract_tupled_inputs_and_output_from_async_callable(
393 cx,
394 goal.predicate.self_ty(),
395 goal_kind,
396 Region::new_static(cx),
398 )?;
399
400 let output_is_sized_pred = tupled_inputs_and_output_and_coroutine.map_bound(
403 |AsyncCallableRelevantTypes { output_coroutine_ty, .. }| {
404 ty::TraitRef::new(
405 cx,
406 cx.require_lang_item(TraitSolverLangItem::Sized),
407 [output_coroutine_ty],
408 )
409 },
410 );
411
412 let pred = tupled_inputs_and_output_and_coroutine
413 .map_bound(|AsyncCallableRelevantTypes { tupled_inputs_ty, .. }| {
414 ty::TraitRef::new(
415 cx,
416 goal.predicate.def_id(),
417 [goal.predicate.self_ty(), tupled_inputs_ty],
418 )
419 })
420 .upcast(cx);
421 Self::probe_and_consider_implied_clause(
422 ecx,
423 CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
424 goal,
425 pred,
426 [goal.with(cx, output_is_sized_pred)]
427 .into_iter()
428 .chain(nested_preds.into_iter().map(|pred| goal.with(cx, pred)))
429 .map(|goal| (GoalSource::ImplWhereBound, goal)),
430 )
431 }
432
433 fn consider_builtin_async_fn_kind_helper_candidate(
434 ecx: &mut EvalCtxt<'_, D>,
435 goal: Goal<I, Self>,
436 ) -> Result<Candidate<I>, NoSolution> {
437 let [closure_fn_kind_ty, goal_kind_ty] = *goal.predicate.trait_ref.args.as_slice() else {
438 panic!();
439 };
440
441 let Some(closure_kind) = closure_fn_kind_ty.expect_ty().to_opt_closure_kind() else {
442 return Err(NoSolution);
444 };
445 let goal_kind = goal_kind_ty.expect_ty().to_opt_closure_kind().unwrap();
446 if closure_kind.extends(goal_kind) {
447 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
448 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
449 } else {
450 Err(NoSolution)
451 }
452 }
453
454 fn consider_builtin_tuple_candidate(
461 ecx: &mut EvalCtxt<'_, D>,
462 goal: Goal<I, Self>,
463 ) -> Result<Candidate<I>, NoSolution> {
464 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
465 return Err(NoSolution);
466 }
467
468 if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
469 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
470 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
471 } else {
472 Err(NoSolution)
473 }
474 }
475
476 fn consider_builtin_pointee_candidate(
477 ecx: &mut EvalCtxt<'_, D>,
478 goal: Goal<I, Self>,
479 ) -> Result<Candidate<I>, NoSolution> {
480 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
481 return Err(NoSolution);
482 }
483
484 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
485 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
486 }
487
488 fn consider_builtin_future_candidate(
489 ecx: &mut EvalCtxt<'_, D>,
490 goal: Goal<I, Self>,
491 ) -> Result<Candidate<I>, NoSolution> {
492 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
493 return Err(NoSolution);
494 }
495
496 let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
497 return Err(NoSolution);
498 };
499
500 let cx = ecx.cx();
502 if !cx.coroutine_is_async(def_id) {
503 return Err(NoSolution);
504 }
505
506 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
510 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
511 }
512
513 fn consider_builtin_iterator_candidate(
514 ecx: &mut EvalCtxt<'_, D>,
515 goal: Goal<I, Self>,
516 ) -> Result<Candidate<I>, NoSolution> {
517 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
518 return Err(NoSolution);
519 }
520
521 let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
522 return Err(NoSolution);
523 };
524
525 let cx = ecx.cx();
527 if !cx.coroutine_is_gen(def_id) {
528 return Err(NoSolution);
529 }
530
531 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
535 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
536 }
537
538 fn consider_builtin_fused_iterator_candidate(
539 ecx: &mut EvalCtxt<'_, D>,
540 goal: Goal<I, Self>,
541 ) -> Result<Candidate<I>, NoSolution> {
542 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
543 return Err(NoSolution);
544 }
545
546 let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
547 return Err(NoSolution);
548 };
549
550 let cx = ecx.cx();
552 if !cx.coroutine_is_gen(def_id) {
553 return Err(NoSolution);
554 }
555
556 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
558 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
559 }
560
561 fn consider_builtin_async_iterator_candidate(
562 ecx: &mut EvalCtxt<'_, D>,
563 goal: Goal<I, Self>,
564 ) -> Result<Candidate<I>, NoSolution> {
565 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
566 return Err(NoSolution);
567 }
568
569 let ty::Coroutine(def_id, _) = goal.predicate.self_ty().kind() else {
570 return Err(NoSolution);
571 };
572
573 let cx = ecx.cx();
575 if !cx.coroutine_is_async_gen(def_id) {
576 return Err(NoSolution);
577 }
578
579 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
583 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
584 }
585
586 fn consider_builtin_coroutine_candidate(
587 ecx: &mut EvalCtxt<'_, D>,
588 goal: Goal<I, Self>,
589 ) -> Result<Candidate<I>, NoSolution> {
590 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
591 return Err(NoSolution);
592 }
593
594 let self_ty = goal.predicate.self_ty();
595 let ty::Coroutine(def_id, args) = self_ty.kind() else {
596 return Err(NoSolution);
597 };
598
599 let cx = ecx.cx();
601 if !cx.is_general_coroutine(def_id) {
602 return Err(NoSolution);
603 }
604
605 let coroutine = args.as_coroutine();
606 Self::probe_and_consider_implied_clause(
607 ecx,
608 CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
609 goal,
610 ty::TraitRef::new(cx, goal.predicate.def_id(), [self_ty, coroutine.resume_ty()])
611 .upcast(cx),
612 [],
615 )
616 }
617
618 fn consider_builtin_discriminant_kind_candidate(
619 ecx: &mut EvalCtxt<'_, D>,
620 goal: Goal<I, Self>,
621 ) -> Result<Candidate<I>, NoSolution> {
622 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
623 return Err(NoSolution);
624 }
625
626 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
628 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
629 }
630
631 fn consider_builtin_destruct_candidate(
632 ecx: &mut EvalCtxt<'_, D>,
633 goal: Goal<I, Self>,
634 ) -> Result<Candidate<I>, NoSolution> {
635 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
636 return Err(NoSolution);
637 }
638
639 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
642 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
643 }
644
645 fn consider_builtin_transmute_candidate(
646 ecx: &mut EvalCtxt<'_, D>,
647 goal: Goal<I, Self>,
648 ) -> Result<Candidate<I>, NoSolution> {
649 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
650 return Err(NoSolution);
651 }
652
653 if goal.has_non_region_placeholders() {
655 return Err(NoSolution);
656 }
657
658 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
659 let assume = ecx.structurally_normalize_const(
660 goal.param_env,
661 goal.predicate.trait_ref.args.const_at(2),
662 )?;
663
664 let certainty = ecx.is_transmutable(
665 goal.predicate.trait_ref.args.type_at(0),
666 goal.predicate.trait_ref.args.type_at(1),
667 assume,
668 )?;
669 ecx.evaluate_added_goals_and_make_canonical_response(certainty)
670 })
671 }
672
673 fn consider_builtin_bikeshed_guaranteed_no_drop_candidate(
683 ecx: &mut EvalCtxt<'_, D>,
684 goal: Goal<I, Self>,
685 ) -> Result<Candidate<I>, NoSolution> {
686 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
687 return Err(NoSolution);
688 }
689
690 let cx = ecx.cx();
691 ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
692 let ty = goal.predicate.self_ty();
693 match ty.kind() {
694 ty::Ref(..) => {}
696 ty::Adt(def, _) if def.is_manually_drop() => {}
698 ty::Tuple(tys) => {
701 ecx.add_goals(
702 GoalSource::ImplWhereBound,
703 tys.iter().map(|elem_ty| {
704 goal.with(cx, ty::TraitRef::new(cx, goal.predicate.def_id(), [elem_ty]))
705 }),
706 );
707 }
708 ty::Array(elem_ty, _) => {
709 ecx.add_goal(
710 GoalSource::ImplWhereBound,
711 goal.with(cx, ty::TraitRef::new(cx, goal.predicate.def_id(), [elem_ty])),
712 );
713 }
714
715 ty::FnDef(..)
719 | ty::FnPtr(..)
720 | ty::Error(_)
721 | ty::Uint(_)
722 | ty::Int(_)
723 | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
724 | ty::Bool
725 | ty::Float(_)
726 | ty::Char
727 | ty::RawPtr(..)
728 | ty::Never
729 | ty::Pat(..)
730 | ty::Dynamic(..)
731 | ty::Str
732 | ty::Slice(_)
733 | ty::Foreign(..)
734 | ty::Adt(..)
735 | ty::Alias(..)
736 | ty::Param(_)
737 | ty::Placeholder(..)
738 | ty::Closure(..)
739 | ty::CoroutineClosure(..)
740 | ty::Coroutine(..)
741 | ty::UnsafeBinder(_)
742 | ty::CoroutineWitness(..) => {
743 ecx.add_goal(
744 GoalSource::ImplWhereBound,
745 goal.with(
746 cx,
747 ty::TraitRef::new(
748 cx,
749 cx.require_lang_item(TraitSolverLangItem::Copy),
750 [ty],
751 ),
752 ),
753 );
754 }
755
756 ty::Bound(..)
757 | ty::Infer(
758 ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_),
759 ) => {
760 panic!("unexpected type `{ty:?}`")
761 }
762 }
763
764 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
765 })
766 }
767
768 fn consider_structural_builtin_unsize_candidates(
776 ecx: &mut EvalCtxt<'_, D>,
777 goal: Goal<I, Self>,
778 ) -> Vec<Candidate<I>> {
779 if goal.predicate.polarity != ty::PredicatePolarity::Positive {
780 return vec![];
781 }
782
783 let result_to_single = |result| match result {
784 Ok(resp) => vec![resp],
785 Err(NoSolution) => vec![],
786 };
787
788 ecx.probe(|_| ProbeKind::UnsizeAssembly).enter(|ecx| {
789 let a_ty = goal.predicate.self_ty();
790 let Ok(b_ty) = ecx.structurally_normalize_ty(
793 goal.param_env,
794 goal.predicate.trait_ref.args.type_at(1),
795 ) else {
796 return vec![];
797 };
798
799 let goal = goal.with(ecx.cx(), (a_ty, b_ty));
800 match (a_ty.kind(), b_ty.kind()) {
801 (ty::Infer(ty::TyVar(..)), ..) => panic!("unexpected infer {a_ty:?} {b_ty:?}"),
802
803 (_, ty::Infer(ty::TyVar(..))) => {
804 result_to_single(ecx.forced_ambiguity(MaybeCause::Ambiguity))
805 }
806
807 (
809 ty::Dynamic(a_data, a_region, ty::Dyn),
810 ty::Dynamic(b_data, b_region, ty::Dyn),
811 ) => ecx.consider_builtin_dyn_upcast_candidates(
812 goal, a_data, a_region, b_data, b_region,
813 ),
814
815 (_, ty::Dynamic(b_region, b_data, ty::Dyn)) => result_to_single(
817 ecx.consider_builtin_unsize_to_dyn_candidate(goal, b_region, b_data),
818 ),
819
820 (ty::Array(a_elem_ty, ..), ty::Slice(b_elem_ty)) => {
822 result_to_single(ecx.consider_builtin_array_unsize(goal, a_elem_ty, b_elem_ty))
823 }
824
825 (ty::Adt(a_def, a_args), ty::Adt(b_def, b_args))
827 if a_def.is_struct() && a_def == b_def =>
828 {
829 result_to_single(
830 ecx.consider_builtin_struct_unsize(goal, a_def, a_args, b_args),
831 )
832 }
833
834 _ => vec![],
835 }
836 })
837 }
838}
839
840#[inline(always)]
846fn trait_predicate_with_def_id<I: Interner>(
847 cx: I,
848 clause: ty::Binder<I, ty::TraitPredicate<I>>,
849 did: I::DefId,
850) -> I::Clause {
851 clause
852 .map_bound(|c| TraitPredicate {
853 trait_ref: TraitRef::new_from_args(cx, did, c.trait_ref.args),
854 polarity: c.polarity,
855 })
856 .upcast(cx)
857}
858
859impl<D, I> EvalCtxt<'_, D>
860where
861 D: SolverDelegate<Interner = I>,
862 I: Interner,
863{
864 fn consider_builtin_dyn_upcast_candidates(
874 &mut self,
875 goal: Goal<I, (I::Ty, I::Ty)>,
876 a_data: I::BoundExistentialPredicates,
877 a_region: I::Region,
878 b_data: I::BoundExistentialPredicates,
879 b_region: I::Region,
880 ) -> Vec<Candidate<I>> {
881 let cx = self.cx();
882 let Goal { predicate: (a_ty, _b_ty), .. } = goal;
883
884 let mut responses = vec![];
885 let b_principal_def_id = b_data.principal_def_id();
888 if a_data.principal_def_id() == b_principal_def_id || b_principal_def_id.is_none() {
889 responses.extend(self.consider_builtin_upcast_to_principal(
890 goal,
891 CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
892 a_data,
893 a_region,
894 b_data,
895 b_region,
896 a_data.principal(),
897 ));
898 } else if let Some(a_principal) = a_data.principal() {
899 for (idx, new_a_principal) in
900 elaborate::supertraits(self.cx(), a_principal.with_self_ty(cx, a_ty))
901 .enumerate()
902 .skip(1)
903 {
904 responses.extend(self.consider_builtin_upcast_to_principal(
905 goal,
906 CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(idx)),
907 a_data,
908 a_region,
909 b_data,
910 b_region,
911 Some(new_a_principal.map_bound(|trait_ref| {
912 ty::ExistentialTraitRef::erase_self_ty(cx, trait_ref)
913 })),
914 ));
915 }
916 }
917
918 responses
919 }
920
921 fn consider_builtin_unsize_to_dyn_candidate(
922 &mut self,
923 goal: Goal<I, (I::Ty, I::Ty)>,
924 b_data: I::BoundExistentialPredicates,
925 b_region: I::Region,
926 ) -> Result<Candidate<I>, NoSolution> {
927 let cx = self.cx();
928 let Goal { predicate: (a_ty, _), .. } = goal;
929
930 if b_data.principal_def_id().is_some_and(|def_id| !cx.trait_is_dyn_compatible(def_id)) {
932 return Err(NoSolution);
933 }
934
935 self.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
936 ecx.add_goals(
939 GoalSource::ImplWhereBound,
940 b_data.iter().map(|pred| goal.with(cx, pred.with_self_ty(cx, a_ty))),
941 );
942
943 ecx.add_goal(
945 GoalSource::ImplWhereBound,
946 goal.with(
947 cx,
948 ty::TraitRef::new(cx, cx.require_lang_item(TraitSolverLangItem::Sized), [a_ty]),
949 ),
950 );
951
952 ecx.add_goal(GoalSource::Misc, goal.with(cx, ty::OutlivesPredicate(a_ty, b_region)));
954 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
955 })
956 }
957
958 fn consider_builtin_upcast_to_principal(
959 &mut self,
960 goal: Goal<I, (I::Ty, I::Ty)>,
961 source: CandidateSource<I>,
962 a_data: I::BoundExistentialPredicates,
963 a_region: I::Region,
964 b_data: I::BoundExistentialPredicates,
965 b_region: I::Region,
966 upcast_principal: Option<ty::Binder<I, ty::ExistentialTraitRef<I>>>,
967 ) -> Result<Candidate<I>, NoSolution> {
968 let param_env = goal.param_env;
969
970 let a_auto_traits: IndexSet<I::DefId> = a_data
974 .auto_traits()
975 .into_iter()
976 .chain(a_data.principal_def_id().into_iter().flat_map(|principal_def_id| {
977 elaborate::supertrait_def_ids(self.cx(), principal_def_id)
978 .filter(|def_id| self.cx().trait_is_auto(*def_id))
979 }))
980 .collect();
981
982 let projection_may_match =
987 |ecx: &mut EvalCtxt<'_, D>,
988 source_projection: ty::Binder<I, ty::ExistentialProjection<I>>,
989 target_projection: ty::Binder<I, ty::ExistentialProjection<I>>| {
990 source_projection.item_def_id() == target_projection.item_def_id()
991 && ecx
992 .probe(|_| ProbeKind::ProjectionCompatibility)
993 .enter(|ecx| -> Result<_, NoSolution> {
994 ecx.enter_forall(target_projection, |ecx, target_projection| {
995 let source_projection =
996 ecx.instantiate_binder_with_infer(source_projection);
997 ecx.eq(param_env, source_projection, target_projection)?;
998 ecx.try_evaluate_added_goals()
999 })
1000 })
1001 .is_ok()
1002 };
1003
1004 self.probe_trait_candidate(source).enter(|ecx| {
1005 for bound in b_data.iter() {
1006 match bound.skip_binder() {
1007 ty::ExistentialPredicate::Trait(target_principal) => {
1010 let source_principal = upcast_principal.unwrap();
1011 let target_principal = bound.rebind(target_principal);
1012 ecx.enter_forall(target_principal, |ecx, target_principal| {
1013 let source_principal =
1014 ecx.instantiate_binder_with_infer(source_principal);
1015 ecx.eq(param_env, source_principal, target_principal)?;
1016 ecx.try_evaluate_added_goals()
1017 })?;
1018 }
1019 ty::ExistentialPredicate::Projection(target_projection) => {
1025 let target_projection = bound.rebind(target_projection);
1026 let mut matching_projections =
1027 a_data.projection_bounds().into_iter().filter(|source_projection| {
1028 projection_may_match(ecx, *source_projection, target_projection)
1029 });
1030 let Some(source_projection) = matching_projections.next() else {
1031 return Err(NoSolution);
1032 };
1033 if matching_projections.next().is_some() {
1034 return ecx.evaluate_added_goals_and_make_canonical_response(
1035 Certainty::AMBIGUOUS,
1036 );
1037 }
1038 ecx.enter_forall(target_projection, |ecx, target_projection| {
1039 let source_projection =
1040 ecx.instantiate_binder_with_infer(source_projection);
1041 ecx.eq(param_env, source_projection, target_projection)?;
1042 ecx.try_evaluate_added_goals()
1043 })?;
1044 }
1045 ty::ExistentialPredicate::AutoTrait(def_id) => {
1047 if !a_auto_traits.contains(&def_id) {
1048 return Err(NoSolution);
1049 }
1050 }
1051 }
1052 }
1053
1054 ecx.add_goal(
1056 GoalSource::ImplWhereBound,
1057 Goal::new(ecx.cx(), param_env, ty::OutlivesPredicate(a_region, b_region)),
1058 );
1059
1060 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
1061 })
1062 }
1063
1064 fn consider_builtin_array_unsize(
1073 &mut self,
1074 goal: Goal<I, (I::Ty, I::Ty)>,
1075 a_elem_ty: I::Ty,
1076 b_elem_ty: I::Ty,
1077 ) -> Result<Candidate<I>, NoSolution> {
1078 self.eq(goal.param_env, a_elem_ty, b_elem_ty)?;
1079 self.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
1080 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
1081 }
1082
1083 fn consider_builtin_struct_unsize(
1097 &mut self,
1098 goal: Goal<I, (I::Ty, I::Ty)>,
1099 def: I::AdtDef,
1100 a_args: I::GenericArgs,
1101 b_args: I::GenericArgs,
1102 ) -> Result<Candidate<I>, NoSolution> {
1103 let cx = self.cx();
1104 let Goal { predicate: (_a_ty, b_ty), .. } = goal;
1105
1106 let unsizing_params = cx.unsizing_params_for_adt(def.def_id());
1107 if unsizing_params.is_empty() {
1110 return Err(NoSolution);
1111 }
1112
1113 let tail_field_ty = def.struct_tail_ty(cx).unwrap();
1114
1115 let a_tail_ty = tail_field_ty.instantiate(cx, a_args);
1116 let b_tail_ty = tail_field_ty.instantiate(cx, b_args);
1117
1118 let new_a_args = cx.mk_args_from_iter(a_args.iter().enumerate().map(|(i, a)| {
1122 if unsizing_params.contains(i as u32) { b_args.get(i).unwrap() } else { a }
1123 }));
1124 let unsized_a_ty = Ty::new_adt(cx, def, new_a_args);
1125
1126 self.eq(goal.param_env, unsized_a_ty, b_ty)?;
1129 self.add_goal(
1130 GoalSource::ImplWhereBound,
1131 goal.with(
1132 cx,
1133 ty::TraitRef::new(
1134 cx,
1135 cx.require_lang_item(TraitSolverLangItem::Unsize),
1136 [a_tail_ty, b_tail_ty],
1137 ),
1138 ),
1139 );
1140 self.probe_builtin_trait_candidate(BuiltinImplSource::Misc)
1141 .enter(|ecx| ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes))
1142 }
1143
1144 fn disqualify_auto_trait_candidate_due_to_possible_impl(
1149 &mut self,
1150 goal: Goal<I, TraitPredicate<I>>,
1151 ) -> Option<Result<Candidate<I>, NoSolution>> {
1152 let self_ty = goal.predicate.self_ty();
1153 let check_impls = || {
1154 let mut disqualifying_impl = None;
1155 self.cx().for_each_relevant_impl(
1156 goal.predicate.def_id(),
1157 goal.predicate.self_ty(),
1158 |impl_def_id| {
1159 disqualifying_impl = Some(impl_def_id);
1160 },
1161 );
1162 if let Some(def_id) = disqualifying_impl {
1163 trace!(?def_id, ?goal, "disqualified auto-trait implementation");
1164 return Some(Err(NoSolution));
1167 } else {
1168 None
1169 }
1170 };
1171
1172 match self_ty.kind() {
1173 ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => {
1179 Some(self.forced_ambiguity(MaybeCause::Ambiguity))
1180 }
1181
1182 ty::Foreign(..) if self.cx().is_default_trait(goal.predicate.def_id()) => check_impls(),
1185
1186 ty::Dynamic(..)
1189 | ty::Param(..)
1190 | ty::Foreign(..)
1191 | ty::Alias(ty::Projection | ty::Free | ty::Inherent, ..)
1192 | ty::Placeholder(..) => Some(Err(NoSolution)),
1193
1194 ty::Infer(_) | ty::Bound(_, _) => panic!("unexpected type `{self_ty:?}`"),
1195
1196 ty::Coroutine(def_id, _)
1200 if self.cx().is_lang_item(goal.predicate.def_id(), TraitSolverLangItem::Unpin) =>
1201 {
1202 match self.cx().coroutine_movability(def_id) {
1203 Movability::Static => Some(Err(NoSolution)),
1204 Movability::Movable => Some(
1205 self.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
1206 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
1207 }),
1208 ),
1209 }
1210 }
1211
1212 ty::Alias(..) => None,
1217
1218 ty::Bool
1227 | ty::Char
1228 | ty::Int(_)
1229 | ty::Uint(_)
1230 | ty::Float(_)
1231 | ty::Str
1232 | ty::Array(_, _)
1233 | ty::Pat(_, _)
1234 | ty::Slice(_)
1235 | ty::RawPtr(_, _)
1236 | ty::Ref(_, _, _)
1237 | ty::FnDef(_, _)
1238 | ty::FnPtr(..)
1239 | ty::Closure(..)
1240 | ty::CoroutineClosure(..)
1241 | ty::Coroutine(_, _)
1242 | ty::CoroutineWitness(..)
1243 | ty::Never
1244 | ty::Tuple(_)
1245 | ty::Adt(_, _)
1246 | ty::UnsafeBinder(_) => check_impls(),
1247 ty::Error(_) => None,
1248 }
1249 }
1250
1251 fn probe_and_evaluate_goal_for_constituent_tys(
1256 &mut self,
1257 source: CandidateSource<I>,
1258 goal: Goal<I, TraitPredicate<I>>,
1259 constituent_tys: impl Fn(
1260 &EvalCtxt<'_, D>,
1261 I::Ty,
1262 ) -> Result<ty::Binder<I, Vec<I::Ty>>, NoSolution>,
1263 ) -> Result<Candidate<I>, NoSolution> {
1264 self.probe_trait_candidate(source).enter(|ecx| {
1265 let goals =
1266 ecx.enter_forall(constituent_tys(ecx, goal.predicate.self_ty())?, |ecx, tys| {
1267 tys.into_iter()
1268 .map(|ty| goal.with(ecx.cx(), goal.predicate.with_self_ty(ecx.cx(), ty)))
1269 .collect::<Vec<_>>()
1270 });
1271 ecx.add_goals(GoalSource::ImplWhereBound, goals);
1272 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
1273 })
1274 }
1275}
1276
1277#[derive(Debug, Clone, Copy)]
1288pub(super) enum TraitGoalProvenVia {
1289 Misc,
1295 ParamEnv,
1296 AliasBound,
1297}
1298
1299impl<D, I> EvalCtxt<'_, D>
1300where
1301 D: SolverDelegate<Interner = I>,
1302 I: Interner,
1303{
1304 pub(super) fn unsound_prefer_builtin_dyn_impl(&mut self, candidates: &mut Vec<Candidate<I>>) {
1317 match self.typing_mode() {
1318 TypingMode::Coherence => return,
1319 TypingMode::Analysis { .. }
1320 | TypingMode::Borrowck { .. }
1321 | TypingMode::PostBorrowckAnalysis { .. }
1322 | TypingMode::PostAnalysis => {}
1323 }
1324
1325 if candidates
1326 .iter()
1327 .find(|c| {
1328 matches!(c.source, CandidateSource::BuiltinImpl(BuiltinImplSource::Object(_)))
1329 })
1330 .is_some_and(|c| has_only_region_constraints(c.result))
1331 {
1332 candidates.retain(|c| {
1333 if matches!(c.source, CandidateSource::Impl(_)) {
1334 debug!(?c, "unsoundly dropping impl in favor of builtin dyn-candidate");
1335 false
1336 } else {
1337 true
1338 }
1339 });
1340 }
1341 }
1342
1343 #[instrument(level = "debug", skip(self), ret)]
1344 pub(super) fn merge_trait_candidates(
1345 &mut self,
1346 mut candidates: Vec<Candidate<I>>,
1347 ) -> Result<(CanonicalResponse<I>, Option<TraitGoalProvenVia>), NoSolution> {
1348 if let TypingMode::Coherence = self.typing_mode() {
1349 let all_candidates: Vec<_> = candidates.into_iter().map(|c| c.result).collect();
1350 return if let Some(response) = self.try_merge_responses(&all_candidates) {
1351 Ok((response, Some(TraitGoalProvenVia::Misc)))
1352 } else {
1353 self.flounder(&all_candidates).map(|r| (r, None))
1354 };
1355 }
1356
1357 let mut trivial_builtin_impls = candidates.iter().filter(|c| {
1362 matches!(c.source, CandidateSource::BuiltinImpl(BuiltinImplSource::Trivial))
1363 });
1364 if let Some(candidate) = trivial_builtin_impls.next() {
1365 assert!(trivial_builtin_impls.next().is_none());
1368 return Ok((candidate.result, Some(TraitGoalProvenVia::Misc)));
1369 }
1370
1371 let has_non_global_where_bounds = candidates
1374 .iter()
1375 .any(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::NonGlobal)));
1376 if has_non_global_where_bounds {
1377 let where_bounds: Vec<_> = candidates
1378 .iter()
1379 .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_)))
1380 .map(|c| c.result)
1381 .collect();
1382 return if let Some(response) = self.try_merge_responses(&where_bounds) {
1383 Ok((response, Some(TraitGoalProvenVia::ParamEnv)))
1384 } else {
1385 Ok((self.bail_with_ambiguity(&where_bounds), None))
1386 };
1387 }
1388
1389 if candidates.iter().any(|c| matches!(c.source, CandidateSource::AliasBound)) {
1390 let alias_bounds: Vec<_> = candidates
1391 .iter()
1392 .filter(|c| matches!(c.source, CandidateSource::AliasBound))
1393 .map(|c| c.result)
1394 .collect();
1395 return if let Some(response) = self.try_merge_responses(&alias_bounds) {
1396 Ok((response, Some(TraitGoalProvenVia::AliasBound)))
1397 } else {
1398 Ok((self.bail_with_ambiguity(&alias_bounds), None))
1399 };
1400 }
1401
1402 self.filter_specialized_impls(AllowInferenceConstraints::No, &mut candidates);
1403 self.unsound_prefer_builtin_dyn_impl(&mut candidates);
1404
1405 let proven_via = if candidates
1410 .iter()
1411 .all(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)))
1412 {
1413 TraitGoalProvenVia::ParamEnv
1414 } else {
1415 candidates
1416 .retain(|c| !matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)));
1417 TraitGoalProvenVia::Misc
1418 };
1419
1420 let all_candidates: Vec<_> = candidates.into_iter().map(|c| c.result).collect();
1421 if let Some(response) = self.try_merge_responses(&all_candidates) {
1422 Ok((response, Some(proven_via)))
1423 } else {
1424 self.flounder(&all_candidates).map(|r| (r, None))
1425 }
1426 }
1427
1428 #[instrument(level = "trace", skip(self))]
1429 pub(super) fn compute_trait_goal(
1430 &mut self,
1431 goal: Goal<I, TraitPredicate<I>>,
1432 ) -> Result<(CanonicalResponse<I>, Option<TraitGoalProvenVia>), NoSolution> {
1433 let candidates = self.assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::All);
1434 self.merge_trait_candidates(candidates)
1435 }
1436
1437 fn try_stall_coroutine_witness(
1438 &mut self,
1439 self_ty: I::Ty,
1440 ) -> Option<Result<Candidate<I>, NoSolution>> {
1441 if let ty::CoroutineWitness(def_id, _) = self_ty.kind() {
1442 match self.typing_mode() {
1443 TypingMode::Analysis {
1444 defining_opaque_types_and_generators: stalled_generators,
1445 } => {
1446 if def_id.as_local().is_some_and(|def_id| stalled_generators.contains(&def_id))
1447 {
1448 return Some(self.forced_ambiguity(MaybeCause::Ambiguity));
1449 }
1450 }
1451 TypingMode::Coherence
1452 | TypingMode::PostAnalysis
1453 | TypingMode::Borrowck { defining_opaque_types: _ }
1454 | TypingMode::PostBorrowckAnalysis { defined_opaque_types: _ } => {}
1455 }
1456 }
1457
1458 None
1459 }
1460}