rustc_next_trait_solver/solve/
search_graph.rs

1use std::convert::Infallible;
2use std::marker::PhantomData;
3
4use rustc_type_ir::search_graph::{self, PathKind};
5use rustc_type_ir::solve::{CanonicalInput, Certainty, NoSolution, QueryResult};
6use rustc_type_ir::{Interner, TypingMode};
7
8use super::inspect::ProofTreeBuilder;
9use super::{FIXPOINT_STEP_LIMIT, has_no_inference_or_external_constraints};
10use crate::delegate::SolverDelegate;
11
12/// This type is never constructed. We only use it to implement `search_graph::Delegate`
13/// for all types which impl `SolverDelegate` and doing it directly fails in coherence.
14pub(super) struct SearchGraphDelegate<D: SolverDelegate> {
15    _marker: PhantomData<D>,
16}
17pub(super) type SearchGraph<D> = search_graph::SearchGraph<SearchGraphDelegate<D>>;
18impl<D, I> search_graph::Delegate for SearchGraphDelegate<D>
19where
20    D: SolverDelegate<Interner = I>,
21    I: Interner,
22{
23    type Cx = D::Interner;
24
25    const ENABLE_PROVISIONAL_CACHE: bool = true;
26    type ValidationScope = Infallible;
27    fn enter_validation_scope(
28        _cx: Self::Cx,
29        _input: CanonicalInput<I>,
30    ) -> Option<Self::ValidationScope> {
31        None
32    }
33
34    const FIXPOINT_STEP_LIMIT: usize = FIXPOINT_STEP_LIMIT;
35
36    type ProofTreeBuilder = ProofTreeBuilder<D>;
37    fn inspect_is_noop(inspect: &mut Self::ProofTreeBuilder) -> bool {
38        inspect.is_noop()
39    }
40
41    const DIVIDE_AVAILABLE_DEPTH_ON_OVERFLOW: usize = 4;
42
43    fn initial_provisional_result(
44        cx: I,
45        kind: PathKind,
46        input: CanonicalInput<I>,
47    ) -> QueryResult<I> {
48        match kind {
49            PathKind::Coinductive => response_no_constraints(cx, input, Certainty::Yes),
50            PathKind::Unknown => response_no_constraints(cx, input, Certainty::overflow(false)),
51            // Even though we know these cycles to be unproductive, we still return
52            // overflow during coherence. This is both as we are not 100% confident in
53            // the implementation yet and any incorrect errors would be unsound there.
54            // The affected cases are also fairly artificial and not necessarily desirable
55            // so keeping this as ambiguity is fine for now.
56            //
57            // See `tests/ui/traits/next-solver/cycles/unproductive-in-coherence.rs` for an
58            // example where this would matter. We likely should change these cycles to `NoSolution`
59            // even in coherence once this is a bit more settled.
60            PathKind::Inductive => match input.typing_mode {
61                TypingMode::Coherence => {
62                    response_no_constraints(cx, input, Certainty::overflow(false))
63                }
64                TypingMode::Analysis { .. }
65                | TypingMode::Borrowck { .. }
66                | TypingMode::PostBorrowckAnalysis { .. }
67                | TypingMode::PostAnalysis => Err(NoSolution),
68            },
69        }
70    }
71
72    fn is_initial_provisional_result(
73        cx: Self::Cx,
74        kind: PathKind,
75        input: CanonicalInput<I>,
76        result: QueryResult<I>,
77    ) -> bool {
78        Self::initial_provisional_result(cx, kind, input) == result
79    }
80
81    fn on_stack_overflow(
82        cx: I,
83        inspect: &mut ProofTreeBuilder<D>,
84        input: CanonicalInput<I>,
85    ) -> QueryResult<I> {
86        inspect.canonical_goal_evaluation_overflow();
87        response_no_constraints(cx, input, Certainty::overflow(true))
88    }
89
90    fn on_fixpoint_overflow(cx: I, input: CanonicalInput<I>) -> QueryResult<I> {
91        response_no_constraints(cx, input, Certainty::overflow(false))
92    }
93
94    fn is_ambiguous_result(result: QueryResult<I>) -> bool {
95        result.is_ok_and(|response| {
96            has_no_inference_or_external_constraints(response)
97                && matches!(response.value.certainty, Certainty::Maybe(_))
98        })
99    }
100
101    fn propagate_ambiguity(
102        cx: I,
103        for_input: CanonicalInput<I>,
104        from_result: QueryResult<I>,
105    ) -> QueryResult<I> {
106        let certainty = from_result.unwrap().value.certainty;
107        response_no_constraints(cx, for_input, certainty)
108    }
109}
110
111fn response_no_constraints<I: Interner>(
112    cx: I,
113    input: CanonicalInput<I>,
114    certainty: Certainty,
115) -> QueryResult<I> {
116    Ok(super::response_no_constraints_raw(
117        cx,
118        input.canonical.max_universe,
119        input.canonical.variables,
120        certainty,
121    ))
122}
rustc_next_trait_solver/solve/search_graph.rs

rustc_next_trait_solver/solve/
search_graph.rs
