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::{AccessedOpaques, Certainty, NoSolution, QueryResult, RerunResultExt};
6use rustc_type_ir::{Interner, MayBeErased, TypingMode};
7
8use crate::canonical::response_no_constraints_raw;
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: I::CanonicalInput,
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: I::CanonicalInput,
49    ) -> (QueryResult<I>, AccessedOpaques<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.0 {
65                TypingMode::Coherence => {
66                    response_no_constraints(cx, input, Certainty::overflow(false))
67                }
68                TypingMode::Typeck { .. }
69                | TypingMode::PostTypeckUntilBorrowck { .. }
70                | TypingMode::Reflection
71                | TypingMode::PostBorrowck { .. }
72                | TypingMode::PostAnalysis
73                | TypingMode::Codegen
74                | TypingMode::ErasedNotCoherence(MayBeErased) => {
75                    (Err(NoSolution), AccessedOpaques::default())
76                }
77            },
78        }
79    }
80
81    fn is_initial_provisional_result(
82        result: (QueryResult<I>, AccessedOpaques<I>),
83    ) -> Option<PathKind> {
84        match result.0 {
85            Ok(response) => {
86                if has_no_inference_or_external_constraints(response) {
87                    if response.value.certainty == Certainty::Yes {
88                        return Some(PathKind::Coinductive);
89                    } else if response.value.certainty == Certainty::overflow(false) {
90                        return Some(PathKind::Unknown);
91                    }
92                }
93
94                None
95            }
96            Err(NoSolution) => Some(PathKind::Inductive),
97        }
98    }
99
100    fn stack_overflow_result(
101        cx: I,
102        input: I::CanonicalInput,
103    ) -> (QueryResult<I>, AccessedOpaques<I>) {
104        response_no_constraints(cx, input, Certainty::overflow(true))
105    }
106
107    const FIXPOINT_OVERFLOW_AMBIGUITY_KIND: Certainty = Certainty::overflow(false);
108    fn fixpoint_overflow_result(
109        cx: I,
110        input: I::CanonicalInput,
111    ) -> (QueryResult<I>, AccessedOpaques<I>) {
112        response_no_constraints(cx, input, Certainty::overflow(false))
113    }
114
115    fn is_ambiguous_result(result: (QueryResult<I>, AccessedOpaques<I>)) -> Option<Certainty> {
116        result.0.ok().and_then(|response| {
117            if has_no_inference_or_external_constraints(response)
118                && #[allow(non_exhaustive_omitted_patterns)] match response.value.certainty {
    Certainty::Maybe { .. } => true,
    _ => false,
}matches!(response.value.certainty, Certainty::Maybe { .. })
119            {
120                Some(response.value.certainty)
121            } else {
122                None
123            }
124        })
125    }
126
127    fn compute_goal(
128        search_graph: &mut SearchGraph<D>,
129        cx: I,
130        input: I::CanonicalInput,
131        inspect: &mut Self::ProofTreeBuilder,
132    ) -> (QueryResult<I>, AccessedOpaques<I>) {
133        EvalCtxt::enter_canonical(cx, search_graph, input, inspect, |ecx, goal| {
134            // if we're in `RerunNonErased`, don't even bother with inspect, and immediately return
135            let result = ecx.compute_goal(goal).map_err_to_rerun()?;
136
137            ecx.inspect.query_result(result);
138            result.map_err(Into::into)
139        })
140    }
141}
142
143fn response_no_constraints<I: Interner>(
144    cx: I,
145    input: I::CanonicalInput,
146    certainty: Certainty,
147) -> (QueryResult<I>, AccessedOpaques<I>) {
148    (
149        Ok(response_no_constraints_raw(
150            cx,
151            input.canonical.max_universe,
152            input.canonical.var_kinds,
153            certainty,
154        )),
155        AccessedOpaques::default(),
156    )
157}
rustc_next_trait_solver/solve/search_graph.rs

rustc_next_trait_solver/solve/
search_graph.rs
