rustc_trait_selection/solve/
select.rs1use std::ops::ControlFlow;
2
3use rustc_infer::infer::InferCtxt;
4use rustc_infer::traits::solve::inspect::ProbeKind;
5use rustc_infer::traits::solve::{CandidateSource, Certainty, Goal};
6use rustc_infer::traits::{
7 BuiltinImplSource, ImplSource, ImplSourceUserDefinedData, Obligation, ObligationCause,
8 Selection, SelectionError, SelectionResult, TraitObligation,
9};
10use rustc_macros::extension;
11use rustc_middle::{bug, span_bug};
12use rustc_span::Span;
13use thin_vec::thin_vec;
14
15use crate::solve::inspect::{self, ProofTreeInferCtxtExt};
16
17#[extension(pub trait InferCtxtSelectExt<'tcx>)]
18impl<'tcx> InferCtxt<'tcx> {
19 fn select_in_new_trait_solver(
21 &self,
22 obligation: &TraitObligation<'tcx>,
23 ) -> SelectionResult<'tcx, Selection<'tcx>> {
24 assert!(self.next_trait_solver());
25
26 self.visit_proof_tree(
27 Goal::new(self.tcx, obligation.param_env, obligation.predicate),
28 &mut Select { span: obligation.cause.span },
29 )
30 .break_value()
31 .unwrap()
32 }
33}
34
35struct Select {
36 span: Span,
37}
38
39impl<'tcx> inspect::ProofTreeVisitor<'tcx> for Select {
40 type Result = ControlFlow<SelectionResult<'tcx, Selection<'tcx>>>;
41
42 fn span(&self) -> Span {
43 self.span
44 }
45
46 fn visit_goal(&mut self, goal: &inspect::InspectGoal<'_, 'tcx>) -> Self::Result {
47 let mut candidates = goal.candidates();
48 candidates.retain(|cand| cand.result().is_ok());
49
50 if candidates.is_empty() {
52 return ControlFlow::Break(Err(SelectionError::Unimplemented));
53 }
54
55 if candidates.len() == 1 {
57 return ControlFlow::Break(Ok(to_selection(
58 self.span,
59 candidates.into_iter().next().unwrap(),
60 )));
61 }
62
63 if matches!(goal.result().unwrap(), Certainty::Maybe(..)) {
66 return ControlFlow::Break(Ok(None));
67 }
68
69 let mut i = 0;
71 while i < candidates.len() {
72 let should_drop_i = (0..candidates.len())
73 .filter(|&j| i != j)
74 .any(|j| candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j]));
75 if should_drop_i {
76 candidates.swap_remove(i);
77 } else {
78 i += 1;
79 if i > 1 {
80 return ControlFlow::Break(Ok(None));
81 }
82 }
83 }
84
85 ControlFlow::Break(Ok(to_selection(self.span, candidates.into_iter().next().unwrap())))
86 }
87}
88
89fn candidate_should_be_dropped_in_favor_of<'tcx>(
93 victim: &inspect::InspectCandidate<'_, 'tcx>,
94 other: &inspect::InspectCandidate<'_, 'tcx>,
95) -> bool {
96 if matches!(other.result().unwrap(), Certainty::Maybe(..)) {
99 return false;
100 }
101
102 let inspect::ProbeKind::TraitCandidate { source: victim_source, result: _ } = victim.kind()
103 else {
104 return false;
105 };
106 let inspect::ProbeKind::TraitCandidate { source: other_source, result: _ } = other.kind()
107 else {
108 return false;
109 };
110
111 match (victim_source, other_source) {
112 (_, CandidateSource::CoherenceUnknowable) | (CandidateSource::CoherenceUnknowable, _) => {
113 bug!("should not have assembled a CoherenceUnknowable candidate")
114 }
115
116 (
119 CandidateSource::BuiltinImpl(BuiltinImplSource::Object(a)),
120 CandidateSource::BuiltinImpl(BuiltinImplSource::Object(b)),
121 ) => a >= b,
122 (
123 CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(a)),
124 CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(b)),
125 ) => a >= b,
126 (
129 CandidateSource::Impl(_) | CandidateSource::ParamEnv(_) | CandidateSource::AliasBound,
130 CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }),
131 ) => true,
132
133 (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => {
135 victim.goal().infcx().tcx.specializes((other_def_id, victim_def_id))
136 }
137
138 _ => false,
139 }
140}
141
142fn to_selection<'tcx>(
143 span: Span,
144 cand: inspect::InspectCandidate<'_, 'tcx>,
145) -> Option<Selection<'tcx>> {
146 if let Certainty::Maybe(..) = cand.shallow_certainty() {
147 return None;
148 }
149
150 let nested = match cand.result().expect("expected positive result") {
151 Certainty::Yes => thin_vec![],
152 Certainty::Maybe(_) => cand
153 .instantiate_nested_goals(span)
154 .into_iter()
155 .map(|nested| {
156 Obligation::new(
157 nested.infcx().tcx,
158 ObligationCause::dummy_with_span(span),
159 nested.goal().param_env,
160 nested.goal().predicate,
161 )
162 })
163 .collect(),
164 };
165
166 Some(match cand.kind() {
167 ProbeKind::TraitCandidate { source, result: _ } => match source {
168 CandidateSource::Impl(impl_def_id) => {
169 ImplSource::UserDefined(ImplSourceUserDefinedData {
172 impl_def_id,
173 args: cand.instantiate_impl_args(span),
174 nested,
175 })
176 }
177 CandidateSource::BuiltinImpl(builtin) => ImplSource::Builtin(builtin, nested),
178 CandidateSource::ParamEnv(_) | CandidateSource::AliasBound => ImplSource::Param(nested),
179 CandidateSource::CoherenceUnknowable => {
180 span_bug!(span, "didn't expect to select an unknowable candidate")
181 }
182 },
183 ProbeKind::NormalizedSelfTyAssembly
184 | ProbeKind::UnsizeAssembly
185 | ProbeKind::ProjectionCompatibility
186 | ProbeKind::OpaqueTypeStorageLookup { result: _ }
187 | ProbeKind::Root { result: _ }
188 | ProbeKind::ShadowedEnvProbing
189 | ProbeKind::RigidAlias { result: _ } => {
190 span_bug!(span, "didn't expect to assemble trait candidate from {:#?}", cand.kind())
191 }
192 })
193}