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

rustc_next_trait_solver/solve/
search_graph.rs
