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;
13
14use crate::solve::inspect::{self, ProofTreeInferCtxtExt};
15
16#[extension(pub trait InferCtxtSelectExt<'tcx>)]
17impl<'tcx> InferCtxt<'tcx> {
18    /// Do not use this directly. This is called from [`crate::traits::SelectionContext::select`].
19    fn select_in_new_trait_solver(
20        &self,
21        obligation: &TraitObligation<'tcx>,
22    ) -> SelectionResult<'tcx, Selection<'tcx>> {
23        assert!(self.next_trait_solver());
24
25        self.visit_proof_tree(
26            Goal::new(self.tcx, obligation.param_env, obligation.predicate),
27            &mut Select { span: obligation.cause.span },
28        )
29        .break_value()
30        .unwrap()
31    }
32}
33
34struct Select {
35    span: Span,
36}
37
38impl<'tcx> inspect::ProofTreeVisitor<'tcx> for Select {
39    type Result = ControlFlow<SelectionResult<'tcx, Selection<'tcx>>>;
40
41    fn span(&self) -> Span {
42        self.span
43    }
44
45    fn visit_goal(&mut self, goal: &inspect::InspectGoal<'_, 'tcx>) -> Self::Result {
46        let mut candidates = goal.candidates();
47        candidates.retain(|cand| cand.result().is_ok());
48
49        // No candidates -- not implemented.
50        if candidates.is_empty() {
51            return ControlFlow::Break(Err(SelectionError::Unimplemented));
52        }
53
54        // One candidate, no need to winnow.
55        if candidates.len() == 1 {
56            return ControlFlow::Break(Ok(to_selection(
57                self.span,
58                candidates.into_iter().next().unwrap(),
59            )));
60        }
61
62        // Don't winnow until `Certainty::Yes` -- we don't need to winnow until
63        // codegen, and only on the good path.
64        if matches!(goal.result().unwrap(), Certainty::Maybe(..)) {
65            return ControlFlow::Break(Ok(None));
66        }
67
68        // We need to winnow. See comments on `candidate_should_be_dropped_in_favor_of`.
69        let mut i = 0;
70        while i < candidates.len() {
71            let should_drop_i = (0..candidates.len())
72                .filter(|&j| i != j)
73                .any(|j| candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j]));
74            if should_drop_i {
75                candidates.swap_remove(i);
76            } else {
77                i += 1;
78                if i > 1 {
79                    return ControlFlow::Break(Ok(None));
80                }
81            }
82        }
83
84        ControlFlow::Break(Ok(to_selection(self.span, candidates.into_iter().next().unwrap())))
85    }
86}
87
88/// This is a lot more limited than the old solver's equivalent method. This may lead to more `Ok(None)`
89/// results when selecting traits in polymorphic contexts, but we should never rely on the lack of ambiguity,
90/// and should always just gracefully fail here. We shouldn't rely on this incompleteness.
91fn candidate_should_be_dropped_in_favor_of<'tcx>(
92    victim: &inspect::InspectCandidate<'_, 'tcx>,
93    other: &inspect::InspectCandidate<'_, 'tcx>,
94) -> bool {
95    // Don't winnow until `Certainty::Yes` -- we don't need to winnow until
96    // codegen, and only on the good path.
97    if matches!(other.result().unwrap(), Certainty::Maybe(..)) {
98        return false;
99    }
100
101    let inspect::ProbeKind::TraitCandidate { source: victim_source, result: _ } = victim.kind()
102    else {
103        return false;
104    };
105    let inspect::ProbeKind::TraitCandidate { source: other_source, result: _ } = other.kind()
106    else {
107        return false;
108    };
109
110    match (victim_source, other_source) {
111        (_, CandidateSource::CoherenceUnknowable) | (CandidateSource::CoherenceUnknowable, _) => {
112            bug!("should not have assembled a CoherenceUnknowable candidate")
113        }
114
115        // In the old trait solver, we arbitrarily choose lower vtable candidates
116        // over higher ones.
117        (
118            CandidateSource::BuiltinImpl(BuiltinImplSource::Object(a)),
119            CandidateSource::BuiltinImpl(BuiltinImplSource::Object(b)),
120        ) => a >= b,
121        (
122            CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(a)),
123            CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(b)),
124        ) => a >= b,
125        // Prefer dyn candidates over non-dyn candidates. This is necessary to
126        // handle the unsoundness between `impl<T: ?Sized> Any for T` and `dyn Any: Any`.
127        (
128            CandidateSource::Impl(_) | CandidateSource::ParamEnv(_) | CandidateSource::AliasBound,
129            CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }),
130        ) => true,
131
132        // Prefer specializing candidates over specialized candidates.
133        (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => {
134            victim.goal().infcx().tcx.specializes((other_def_id, victim_def_id))
135        }
136
137        _ => false,
138    }
139}
140
141fn to_selection<'tcx>(
142    span: Span,
143    cand: inspect::InspectCandidate<'_, 'tcx>,
144) -> Option<Selection<'tcx>> {
145    if let Certainty::Maybe(..) = cand.shallow_certainty() {
146        return None;
147    }
148
149    let (nested, impl_args) = cand.instantiate_nested_goals_and_opt_impl_args(span);
150    let nested = nested
151        .into_iter()
152        .map(|nested| {
153            Obligation::new(
154                nested.infcx().tcx,
155                ObligationCause::dummy_with_span(span),
156                nested.goal().param_env,
157                nested.goal().predicate,
158            )
159        })
160        .collect();
161
162    Some(match cand.kind() {
163        ProbeKind::TraitCandidate { source, result: _ } => match source {
164            CandidateSource::Impl(impl_def_id) => {
165                // FIXME: Remove this in favor of storing this in the tree
166                // For impl candidates, we do the rematch manually to compute the args.
167                ImplSource::UserDefined(ImplSourceUserDefinedData {
168                    impl_def_id,
169                    args: impl_args.expect("expected recorded impl args for impl candidate"),
170                    nested,
171                })
172            }
173            CandidateSource::BuiltinImpl(builtin) => ImplSource::Builtin(builtin, nested),
174            CandidateSource::ParamEnv(_) | CandidateSource::AliasBound => ImplSource::Param(nested),
175            CandidateSource::CoherenceUnknowable => {
176                span_bug!(span, "didn't expect to select an unknowable candidate")
177            }
178        },
179        ProbeKind::NormalizedSelfTyAssembly
180        | ProbeKind::UnsizeAssembly
181        | ProbeKind::ProjectionCompatibility
182        | ProbeKind::OpaqueTypeStorageLookup { result: _ }
183        | ProbeKind::Root { result: _ }
184        | ProbeKind::ShadowedEnvProbing
185        | ProbeKind::RigidAlias { result: _ } => {
186            span_bug!(span, "didn't expect to assemble trait candidate from {:#?}", cand.kind())
187        }
188    })
189}
rustc_trait_selection/solve/select.rs

rustc_trait_selection/solve/
select.rs
