rustc_next_trait_solver/solve/
search_graph.rs

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

rustc_next_trait_solver/solve/
search_graph.rs
