rustc_trait_selection/solve/
select.rs

1use 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    /// Do not use this directly. This is called from [`crate::traits::SelectionContext::select`].
20    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        // No candidates -- not implemented.
51        if candidates.is_empty() {
52            return ControlFlow::Break(Err(SelectionError::Unimplemented));
53        }
54
55        // One candidate, no need to winnow.
56        if candidates.len() == 1 {
57            return ControlFlow::Break(Ok(to_selection(
58                self.span,
59                candidates.into_iter().next().unwrap(),
60            )));
61        }
62
63        // Don't winnow until `Certainty::Yes` -- we don't need to winnow until
64        // codegen, and only on the good path.
65        if matches!(goal.result().unwrap(), Certainty::Maybe(..)) {
66            return ControlFlow::Break(Ok(None));
67        }
68
69        // We need to winnow. See comments on `candidate_should_be_dropped_in_favor_of`.
70        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
89/// This is a lot more limited than the old solver's equivalent method. This may lead to more `Ok(None)`
90/// results when selecting traits in polymorphic contexts, but we should never rely on the lack of ambiguity,
91/// and should always just gracefully fail here. We shouldn't rely on this incompleteness.
92fn candidate_should_be_dropped_in_favor_of<'tcx>(
93    victim: &inspect::InspectCandidate<'_, 'tcx>,
94    other: &inspect::InspectCandidate<'_, 'tcx>,
95) -> bool {
96    // Don't winnow until `Certainty::Yes` -- we don't need to winnow until
97    // codegen, and only on the good path.
98    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        // In the old trait solver, we arbitrarily choose lower vtable candidates
117        // over higher ones.
118        (
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        // Prefer dyn candidates over non-dyn candidates. This is necessary to
127        // handle the unsoundness between `impl<T: ?Sized> Any for T` and `dyn Any: Any`.
128        (
129            CandidateSource::Impl(_) | CandidateSource::ParamEnv(_) | CandidateSource::AliasBound,
130            CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }),
131        ) => true,
132
133        // Prefer specializing candidates over specialized candidates.
134        (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                // FIXME: Remove this in favor of storing this in the tree
170                // For impl candidates, we do the rematch manually to compute the args.
171                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}
rustc_trait_selection/solve/select.rs

rustc_trait_selection/solve/
select.rs
