hir_ty/next_solver/infer/
select.rs

1#![expect(dead_code, reason = "this is used by rustc")]
2
3use std::ops::ControlFlow;
4
5use hir_def::TraitId;
6use macros::{TypeFoldable, TypeVisitable};
7use rustc_type_ir::{
8    Interner,
9    solve::{BuiltinImplSource, CandidateSource, Certainty, inspect::ProbeKind},
10};
11
12use crate::{
13    Span,
14    db::InternedOpaqueTyId,
15    next_solver::{
16        AnyImplId, Const, ErrorGuaranteed, GenericArgs, Goal, TraitRef, Ty, TypeError,
17        infer::{
18            InferCtxt,
19            select::EvaluationResult::*,
20            traits::{Obligation, ObligationCause, PredicateObligation, TraitObligation},
21        },
22        inspect::{InspectCandidate, InspectGoal, ProofTreeVisitor},
23    },
24};
25
26#[derive(Clone, Debug, PartialEq, Eq)]
27pub enum SelectionError<'db> {
28    /// The trait is not implemented.
29    Unimplemented,
30    /// After a closure impl has selected, its "outputs" were evaluated
31    /// (which for closures includes the "input" type params) and they
32    /// didn't resolve. See `confirm_poly_trait_refs` for more.
33    SignatureMismatch(Box<SignatureMismatchData<'db>>),
34    /// The trait pointed by `DefId` is dyn-incompatible.
35    TraitDynIncompatible(TraitId),
36    /// A given constant couldn't be evaluated.
37    NotConstEvaluatable(NotConstEvaluatable),
38    /// Exceeded the recursion depth during type projection.
39    Overflow(OverflowError),
40    /// Computing an opaque type's hidden type caused an error (e.g. a cycle error).
41    /// We can thus not know whether the hidden type implements an auto trait, so
42    /// we should not presume anything about it.
43    OpaqueTypeAutoTraitLeakageUnknown(InternedOpaqueTyId<'db>),
44    /// Error for a `ConstArgHasType` goal
45    ConstArgHasWrongType { ct: Const<'db>, ct_ty: Ty<'db>, expected_ty: Ty<'db> },
46}
47
48#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
49pub enum NotConstEvaluatable {
50    Error(ErrorGuaranteed),
51    MentionsInfer,
52    MentionsParam,
53}
54
55/// The result of trait evaluation. The order is important
56/// here as the evaluation of a list is the maximum of the
57/// evaluations.
58///
59/// The evaluation results are ordered:
60///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
61///       implies `EvaluatedToAmbig` implies `EvaluatedToAmbigStackDependent`
62///     - the "union" of evaluation results is equal to their maximum -
63///     all the "potential success" candidates can potentially succeed,
64///     so they are noops when unioned with a definite error, and within
65///     the categories it's easy to see that the unions are correct.
66#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
67pub enum EvaluationResult {
68    /// Evaluation successful.
69    EvaluatedToOk,
70    /// Evaluation successful, but there were unevaluated region obligations.
71    EvaluatedToOkModuloRegions,
72    /// Evaluation successful, but need to rerun because opaque types got
73    /// hidden types assigned without it being known whether the opaque types
74    /// are within their defining scope
75    EvaluatedToOkModuloOpaqueTypes,
76    /// Evaluation is known to be ambiguous -- it *might* hold for some
77    /// assignment of inference variables, but it might not.
78    ///
79    /// While this has the same meaning as `EvaluatedToAmbigStackDependent` -- we can't
80    /// know whether this obligation holds or not -- it is the result we
81    /// would get with an empty stack, and therefore is cacheable.
82    EvaluatedToAmbig,
83    /// Evaluation failed because of recursion involving inference
84    /// variables. We are somewhat imprecise there, so we don't actually
85    /// know the real result.
86    ///
87    /// This can't be trivially cached because the result depends on the
88    /// stack results.
89    EvaluatedToAmbigStackDependent,
90    /// Evaluation failed.
91    EvaluatedToErr,
92}
93
94impl EvaluationResult {
95    /// Returns `true` if this evaluation result is known to apply, even
96    /// considering outlives constraints.
97    pub(crate) fn must_apply_considering_regions(self) -> bool {
98        self == EvaluatedToOk
99    }
100
101    /// Returns `true` if this evaluation result is known to apply, ignoring
102    /// outlives constraints.
103    pub(crate) fn must_apply_modulo_regions(self) -> bool {
104        self <= EvaluatedToOkModuloRegions
105    }
106
107    pub(crate) fn may_apply(self) -> bool {
108        match self {
109            EvaluatedToOkModuloOpaqueTypes
110            | EvaluatedToOk
111            | EvaluatedToOkModuloRegions
112            | EvaluatedToAmbig
113            | EvaluatedToAmbigStackDependent => true,
114
115            EvaluatedToErr => false,
116        }
117    }
118
119    pub(crate) fn is_stack_dependent(self) -> bool {
120        match self {
121            EvaluatedToAmbigStackDependent => true,
122
123            EvaluatedToOkModuloOpaqueTypes
124            | EvaluatedToOk
125            | EvaluatedToOkModuloRegions
126            | EvaluatedToAmbig
127            | EvaluatedToErr => false,
128        }
129    }
130}
131
132/// Indicates that trait evaluation caused overflow and in which pass.
133#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
134pub enum OverflowError {
135    Error(ErrorGuaranteed),
136    Canonical,
137}
138
139#[derive(Clone, Debug, PartialEq, Eq)]
140pub struct SignatureMismatchData<'db> {
141    pub(crate) found_trait_ref: TraitRef<'db>,
142    pub(crate) expected_trait_ref: TraitRef<'db>,
143    pub(crate) terr: TypeError<'db>,
144}
145
146/// When performing resolution, it is typically the case that there
147/// can be one of three outcomes:
148///
149/// - `Ok(Some(r))`: success occurred with result `r`
150/// - `Ok(None)`: could not definitely determine anything, usually due
151///   to inconclusive type inference.
152/// - `Err(e)`: error `e` occurred
153pub(crate) type SelectionResult<'db, T> = Result<Option<T>, SelectionError<'db>>;
154
155/// Given the successful resolution of an obligation, the `ImplSource`
156/// indicates where the impl comes from.
157///
158/// For example, the obligation may be satisfied by a specific impl (case A),
159/// or it may be relative to some bound that is in scope (case B).
160///
161/// ```ignore (illustrative)
162/// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
163/// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
164/// impl Clone for i32 { ... }                   // Impl_3
165///
166/// fn foo<T: Clone>(concrete: Option<Box<i32>>, param: T, mixed: Option<T>) {
167///     // Case A: ImplSource points at a specific impl. Only possible when
168///     // type is concretely known. If the impl itself has bounded
169///     // type parameters, ImplSource will carry resolutions for those as well:
170///     concrete.clone(); // ImplSource(Impl_1, [ImplSource(Impl_2, [ImplSource(Impl_3)])])
171///
172///     // Case B: ImplSource must be provided by caller. This applies when
173///     // type is a type parameter.
174///     param.clone();    // ImplSource::Param
175///
176///     // Case C: A mix of cases A and B.
177///     mixed.clone();    // ImplSource(Impl_1, [ImplSource::Param])
178/// }
179/// ```
180///
181/// ### The type parameter `N`
182///
183/// See explanation on `ImplSourceUserDefinedData`.
184#[derive(Debug, Clone, PartialEq, Eq, Hash, TypeVisitable, TypeFoldable)]
185pub(crate) enum ImplSource<'db, N> {
186    /// ImplSource identifying a particular impl.
187    UserDefined(ImplSourceUserDefinedData<'db, N>),
188
189    /// Successful resolution to an obligation provided by the caller
190    /// for some type parameter. The `Vec<N>` represents the
191    /// obligations incurred from normalizing the where-clause (if
192    /// any).
193    Param(Vec<N>),
194
195    /// Successful resolution for a builtin impl.
196    Builtin(BuiltinImplSource, Vec<N>),
197}
198
199impl<'db, N> ImplSource<'db, N> {
200    pub(crate) fn nested_obligations(self) -> Vec<N> {
201        match self {
202            ImplSource::UserDefined(i) => i.nested,
203            ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
204        }
205    }
206
207    pub(crate) fn borrow_nested_obligations(&self) -> &[N] {
208        match self {
209            ImplSource::UserDefined(i) => &i.nested,
210            ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
211        }
212    }
213
214    pub(crate) fn borrow_nested_obligations_mut(&mut self) -> &mut [N] {
215        match self {
216            ImplSource::UserDefined(i) => &mut i.nested,
217            ImplSource::Param(n) | ImplSource::Builtin(_, n) => n,
218        }
219    }
220
221    pub(crate) fn map<M, F>(self, f: F) -> ImplSource<'db, M>
222    where
223        F: FnMut(N) -> M,
224    {
225        match self {
226            ImplSource::UserDefined(i) => ImplSource::UserDefined(ImplSourceUserDefinedData {
227                impl_def_id: i.impl_def_id,
228                args: i.args,
229                nested: i.nested.into_iter().map(f).collect(),
230            }),
231            ImplSource::Param(n) => ImplSource::Param(n.into_iter().map(f).collect()),
232            ImplSource::Builtin(source, n) => {
233                ImplSource::Builtin(source, n.into_iter().map(f).collect())
234            }
235        }
236    }
237}
238
239/// Identifies a particular impl in the source, along with a set of
240/// generic parameters from the impl's type/lifetime parameters. The
241/// `nested` vector corresponds to the nested obligations attached to
242/// the impl's type parameters.
243///
244/// The type parameter `N` indicates the type used for "nested
245/// obligations" that are required by the impl. During type-check, this
246/// is `Obligation`, as one might expect. During codegen, however, this
247/// is `()`, because codegen only requires a shallow resolution of an
248/// impl, and nested obligations are satisfied later.
249#[derive(Debug, Clone, PartialEq, Eq, Hash, TypeVisitable, TypeFoldable)]
250pub(crate) struct ImplSourceUserDefinedData<'db, N> {
251    #[type_visitable(ignore)]
252    #[type_foldable(identity)]
253    pub(crate) impl_def_id: AnyImplId,
254    pub(crate) args: GenericArgs<'db>,
255    pub(crate) nested: Vec<N>,
256}
257
258pub(crate) type Selection<'db> = ImplSource<'db, PredicateObligation<'db>>;
259
260impl<'db> InferCtxt<'db> {
261    pub(crate) fn select(
262        &self,
263        obligation: &TraitObligation<'db>,
264    ) -> SelectionResult<'db, Selection<'db>> {
265        self.visit_proof_tree(
266            Goal::new(self.interner, obligation.param_env, obligation.predicate),
267            &mut Select { span: obligation.cause.span() },
268        )
269        .break_value()
270        .unwrap()
271    }
272}
273
274struct Select {
275    span: Span,
276}
277
278impl<'db> ProofTreeVisitor<'db> for Select {
279    type Result = ControlFlow<SelectionResult<'db, Selection<'db>>>;
280
281    fn span(&self) -> Span {
282        self.span
283    }
284
285    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'db>) -> Self::Result {
286        let mut candidates = goal.candidates();
287        candidates.retain(|cand| cand.result().is_ok());
288
289        // No candidates -- not implemented.
290        if candidates.is_empty() {
291            return ControlFlow::Break(Err(SelectionError::Unimplemented));
292        }
293
294        // One candidate, no need to winnow.
295        if candidates.len() == 1 {
296            return ControlFlow::Break(Ok(to_selection(
297                self.span,
298                candidates.into_iter().next().unwrap(),
299            )));
300        }
301
302        // Don't winnow until `Certainty::Yes` -- we don't need to winnow until
303        // codegen, and only on the good path.
304        if matches!(goal.result().unwrap(), Certainty::Maybe { .. }) {
305            return ControlFlow::Break(Ok(None));
306        }
307
308        // We need to winnow. See comments on `candidate_should_be_dropped_in_favor_of`.
309        let mut i = 0;
310        while i < candidates.len() {
311            let should_drop_i = (0..candidates.len())
312                .filter(|&j| i != j)
313                .any(|j| candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j]));
314            if should_drop_i {
315                candidates.swap_remove(i);
316            } else {
317                i += 1;
318                if i > 1 {
319                    return ControlFlow::Break(Ok(None));
320                }
321            }
322        }
323
324        ControlFlow::Break(Ok(to_selection(self.span, candidates.into_iter().next().unwrap())))
325    }
326}
327
328/// This is a lot more limited than the old solver's equivalent method. This may lead to more `Ok(None)`
329/// results when selecting traits in polymorphic contexts, but we should never rely on the lack of ambiguity,
330/// and should always just gracefully fail here. We shouldn't rely on this incompleteness.
331fn candidate_should_be_dropped_in_favor_of<'db>(
332    victim: &InspectCandidate<'_, 'db>,
333    other: &InspectCandidate<'_, 'db>,
334) -> bool {
335    // Don't winnow until `Certainty::Yes` -- we don't need to winnow until
336    // codegen, and only on the good path.
337    if matches!(other.result().unwrap(), Certainty::Maybe { .. }) {
338        return false;
339    }
340
341    let ProbeKind::TraitCandidate { source: victim_source, result: _ } = victim.kind() else {
342        return false;
343    };
344    let ProbeKind::TraitCandidate { source: other_source, result: _ } = other.kind() else {
345        return false;
346    };
347
348    match (victim_source, other_source) {
349        (_, CandidateSource::CoherenceUnknowable) | (CandidateSource::CoherenceUnknowable, _) => {
350            panic!("should not have assembled a CoherenceUnknowable candidate")
351        }
352
353        // In the old trait solver, we arbitrarily choose lower vtable candidates
354        // over higher ones.
355        (
356            CandidateSource::BuiltinImpl(BuiltinImplSource::Object(a)),
357            CandidateSource::BuiltinImpl(BuiltinImplSource::Object(b)),
358        ) => a >= b,
359        (
360            CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(a)),
361            CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting(b)),
362        ) => a >= b,
363        // Prefer dyn candidates over non-dyn candidates. This is necessary to
364        // handle the unsoundness between `impl<T: ?Sized> Any for T` and `dyn Any: Any`.
365        (
366            CandidateSource::Impl(_)
367            | CandidateSource::ParamEnv(_)
368            | CandidateSource::AliasBound(_),
369            CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }),
370        ) => true,
371
372        // Prefer specializing candidates over specialized candidates.
373        (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => {
374            victim.goal().infcx().interner.impl_specializes(other_def_id, victim_def_id)
375        }
376
377        _ => false,
378    }
379}
380
381fn to_selection<'db>(span: Span, cand: InspectCandidate<'_, 'db>) -> Option<Selection<'db>> {
382    if let Certainty::Maybe { .. } = cand.shallow_certainty() {
383        return None;
384    }
385
386    let nested = match cand.result().expect("expected positive result") {
387        Certainty::Yes => Vec::new(),
388        Certainty::Maybe { .. } => cand
389            .instantiate_nested_goals(span)
390            .into_iter()
391            .map(|nested| {
392                Obligation::new(
393                    nested.infcx().interner,
394                    ObligationCause::dummy(),
395                    nested.goal().param_env,
396                    nested.goal().predicate,
397                )
398            })
399            .collect(),
400    };
401
402    Some(match cand.kind() {
403        ProbeKind::TraitCandidate { source, result: _ } => match source {
404            CandidateSource::Impl(impl_def_id) => {
405                // FIXME: Remove this in favor of storing this in the tree
406                // For impl candidates, we do the rematch manually to compute the args.
407                ImplSource::UserDefined(ImplSourceUserDefinedData {
408                    impl_def_id,
409                    args: cand.instantiate_impl_args(span),
410                    nested,
411                })
412            }
413            CandidateSource::BuiltinImpl(builtin) => ImplSource::Builtin(builtin, nested),
414            CandidateSource::ParamEnv(_) | CandidateSource::AliasBound(_) => {
415                ImplSource::Param(nested)
416            }
417            CandidateSource::CoherenceUnknowable => {
418                panic!("didn't expect to select an unknowable candidate")
419            }
420        },
421        ProbeKind::NormalizedSelfTyAssembly
422        | ProbeKind::UnsizeAssembly
423        | ProbeKind::ProjectionCompatibility
424        | ProbeKind::OpaqueTypeStorageLookup { result: _ }
425        | ProbeKind::Root { result: _ }
426        | ProbeKind::ShadowedEnvProbing
427        | ProbeKind::RigidAlias { result: _ } => {
428            panic!("didn't expect to assemble trait candidate from {:#?}", cand.kind())
429        }
430    })
431}
hir_ty/next_solver/infer/select.rs

hir_ty/next_solver/infer/
select.rs
