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