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::{
6    AccessedOpaques, CanonicalInput, Certainty, NoSolution, QueryResult, RerunResultExt,
7};
8use rustc_type_ir::{Interner, MayBeErased, TypingMode};
9
10use crate::canonical::response_no_constraints_raw;
11use crate::delegate::SolverDelegate;
12use crate::solve::{
13    EvalCtxt, FIXPOINT_STEP_LIMIT, has_no_inference_or_external_constraints, inspect,
14};
15
16/// This type is never constructed. We only use it to implement `search_graph::Delegate`
17/// for all types which impl `SolverDelegate` and doing it directly fails in coherence.
18pub(super) struct SearchGraphDelegate<D: SolverDelegate> {
19    _marker: PhantomData<D>,
20}
21pub(super) type SearchGraph<D> = search_graph::SearchGraph<SearchGraphDelegate<D>>;
22impl<D, I> search_graph::Delegate for SearchGraphDelegate<D>
23where
24    D: SolverDelegate<Interner = I>,
25    I: Interner,
26{
27    type Cx = D::Interner;
28
29    const ENABLE_PROVISIONAL_CACHE: bool = true;
30    type ValidationScope = Infallible;
31    fn enter_validation_scope(
32        _cx: Self::Cx,
33        _input: CanonicalInput<I>,
34    ) -> Option<Self::ValidationScope> {
35        None
36    }
37
38    const FIXPOINT_STEP_LIMIT: usize = FIXPOINT_STEP_LIMIT;
39
40    type ProofTreeBuilder = inspect::ProofTreeBuilder<D>;
41    fn inspect_is_noop(inspect: &mut Self::ProofTreeBuilder) -> bool {
42        inspect.is_noop()
43    }
44
45    const DIVIDE_AVAILABLE_DEPTH_ON_OVERFLOW: usize = 4;
46
47    fn initial_provisional_result(
48        cx: I,
49        kind: PathKind,
50        input: CanonicalInput<I>,
51    ) -> (QueryResult<I>, AccessedOpaques<I>) {
52        match kind {
53            PathKind::Coinductive => response_no_constraints(cx, input, Certainty::Yes),
54            PathKind::Unknown | PathKind::ForcedAmbiguity => {
55                response_no_constraints(cx, input, Certainty::overflow(false))
56            }
57            // Even though we know these cycles to be unproductive, we still return
58            // overflow during coherence. This is both as we are not 100% confident in
59            // the implementation yet and any incorrect errors would be unsound there.
60            // The affected cases are also fairly artificial and not necessarily desirable
61            // so keeping this as ambiguity is fine for now.
62            //
63            // See `tests/ui/traits/next-solver/cycles/unproductive-in-coherence.rs` for an
64            // example where this would matter. We likely should change these cycles to `NoSolution`
65            // even in coherence once this is a bit more settled.
66            PathKind::Inductive => match input.typing_mode.0 {
67                TypingMode::Coherence => {
68                    response_no_constraints(cx, input, Certainty::overflow(false))
69                }
70                TypingMode::Typeck { .. }
71                | TypingMode::PostTypeckUntilBorrowck { .. }
72                | TypingMode::Reflection
73                | TypingMode::PostBorrowck { .. }
74                | TypingMode::PostAnalysis
75                | TypingMode::Codegen
76                | TypingMode::ErasedNotCoherence(MayBeErased) => {
77                    (Err(NoSolution), AccessedOpaques::default())
78                }
79            },
80        }
81    }
82
83    fn is_initial_provisional_result(
84        result: (QueryResult<I>, AccessedOpaques<I>),
85    ) -> Option<PathKind> {
86        match result.0 {
87            Ok(response) => {
88                if has_no_inference_or_external_constraints(response) {
89                    if response.value.certainty == Certainty::Yes {
90                        return Some(PathKind::Coinductive);
91                    } else if response.value.certainty == Certainty::overflow(false) {
92                        return Some(PathKind::Unknown);
93                    }
94                }
95
96                None
97            }
98            Err(NoSolution) => Some(PathKind::Inductive),
99        }
100    }
101
102    fn stack_overflow_result(
103        cx: I,
104        input: CanonicalInput<I>,
105    ) -> (QueryResult<I>, AccessedOpaques<I>) {
106        response_no_constraints(cx, input, Certainty::overflow(true))
107    }
108
109    const FIXPOINT_OVERFLOW_AMBIGUITY_KIND: Certainty = Certainty::overflow(false);
110    fn fixpoint_overflow_result(
111        cx: I,
112        input: CanonicalInput<I>,
113    ) -> (QueryResult<I>, AccessedOpaques<I>) {
114        response_no_constraints(cx, input, Certainty::overflow(false))
115    }
116
117    fn is_ambiguous_result(result: (QueryResult<I>, AccessedOpaques<I>)) -> Option<Certainty> {
118        result.0.ok().and_then(|response| {
119            if has_no_inference_or_external_constraints(response)
120                && #[allow(non_exhaustive_omitted_patterns)] match response.value.certainty {
    Certainty::Maybe { .. } => true,
    _ => false,
}matches!(response.value.certainty, Certainty::Maybe { .. })
121            {
122                Some(response.value.certainty)
123            } else {
124                None
125            }
126        })
127    }
128
129    fn compute_goal(
130        search_graph: &mut SearchGraph<D>,
131        cx: I,
132        input: CanonicalInput<I>,
133        inspect: &mut Self::ProofTreeBuilder,
134    ) -> (QueryResult<I>, AccessedOpaques<I>) {
135        EvalCtxt::enter_canonical(cx, search_graph, input, inspect, |ecx, goal| {
136            // if we're in `RerunNonErased`, don't even bother with inspect, and immediately return
137            let result = ecx.compute_goal(goal).map_err_to_rerun()?;
138
139            ecx.inspect.query_result(result);
140            result.map_err(Into::into)
141        })
142    }
143}
144
145fn response_no_constraints<I: Interner>(
146    cx: I,
147    input: CanonicalInput<I>,
148    certainty: Certainty,
149) -> (QueryResult<I>, AccessedOpaques<I>) {
150    (
151        Ok(response_no_constraints_raw(
152            cx,
153            input.canonical.max_universe,
154            input.canonical.var_kinds,
155            certainty,
156        )),
157        AccessedOpaques::default(),
158    )
159}
rustc_next_trait_solver/solve/search_graph.rs

rustc_next_trait_solver/solve/
search_graph.rs
