hir_ty/next_solver/infer/
traits.rs

1//! Trait Resolution. See the [rustc-dev-guide] for more information on how this works.
2//!
3//! [rustc-dev-guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
4
5use std::{
6    cmp,
7    hash::{Hash, Hasher},
8};
9
10use hir_def::TraitId;
11use macros::{TypeFoldable, TypeVisitable};
12use rustc_type_ir::elaborate::Elaboratable;
13use rustc_type_ir::{
14    Upcast,
15    solve::{Certainty, NoSolution, inspect},
16};
17use tracing::debug;
18
19use crate::{
20    Span,
21    next_solver::{
22        Clause, DbInterner, Goal, ParamEnv, PolyTraitPredicate, Predicate, TraitPredicate,
23        TraitRef, Ty,
24    },
25};
26
27use super::InferCtxt;
28
29/// The reason why we incurred this obligation; used for error reporting.
30#[derive(Clone, Copy, Debug, PartialEq, Eq, TypeVisitable, TypeFoldable)]
31pub struct ObligationCause {
32    #[type_visitable(ignore)]
33    span: Span,
34}
35
36impl ObligationCause {
37    #[inline]
38    pub fn new<S: Into<Span>>(span: S) -> ObligationCause {
39        ObligationCause { span: span.into() }
40    }
41
42    #[inline]
43    pub fn dummy() -> ObligationCause {
44        ObligationCause::new(Span::Dummy)
45    }
46
47    #[inline]
48    pub(crate) fn span(&self) -> Span {
49        self.span
50    }
51}
52
53/// An `Obligation` represents some trait reference (e.g., `i32: Eq`) for
54/// which the "impl_source" must be found. The process of finding an "impl_source" is
55/// called "resolving" the `Obligation`. This process consists of
56/// either identifying an `impl` (e.g., `impl Eq for i32`) that
57/// satisfies the obligation, or else finding a bound that is in
58/// scope. The eventual result is usually a `Selection` (defined below).
59#[derive(Clone, Debug, TypeVisitable, TypeFoldable)]
60pub struct Obligation<'db, T> {
61    #[type_foldable(identity)]
62    #[type_visitable(ignore)]
63    /// The reason we have to prove this thing.
64    pub cause: ObligationCause,
65
66    /// The environment in which we should prove this thing.
67    pub param_env: ParamEnv<'db>,
68
69    /// The thing we are trying to prove.
70    pub predicate: T,
71
72    /// If we started proving this as a result of trying to prove
73    /// something else, track the total depth to ensure termination.
74    /// If this goes over a certain threshold, we abort compilation --
75    /// in such cases, we can not say whether or not the predicate
76    /// holds for certain. Stupid halting problem; such a drag.
77    pub recursion_depth: usize,
78}
79
80/// A callback that can be provided to `inspect_typeck`. Invoked on evaluation
81/// of root obligations.
82pub type ObligationInspector<'db> = fn(
83    &InferCtxt<'db>,
84    &PredicateObligation<'db>,
85    Result<Certainty, NoSolution>,
86    Option<inspect::GoalEvaluation<DbInterner<'db>>>,
87);
88
89/// For [`Obligation`], a sub-obligation is combined with the current obligation's
90/// param-env and cause code.
91impl<'db> Elaboratable<DbInterner<'db>> for PredicateObligation<'db> {
92    fn predicate(&self) -> Predicate<'db> {
93        self.predicate
94    }
95
96    fn child(&self, clause: Clause<'db>) -> Self {
97        Obligation {
98            cause: self.cause,
99            param_env: self.param_env,
100            recursion_depth: 0,
101            predicate: clause.as_predicate(),
102        }
103    }
104
105    fn child_with_derived_cause(
106        &self,
107        clause: Clause<'db>,
108        span: Span,
109        _parent_trait_pred: PolyTraitPredicate<'db>,
110        _index: usize,
111    ) -> Self {
112        let cause = ObligationCause::new(span);
113        Obligation {
114            cause,
115            param_env: self.param_env,
116            recursion_depth: 0,
117            predicate: clause.as_predicate(),
118        }
119    }
120}
121
122impl<'db, T: Copy> Obligation<'db, T> {
123    pub fn as_goal(&self) -> Goal<'db, T> {
124        Goal { param_env: self.param_env, predicate: self.predicate }
125    }
126}
127
128impl<'db, T: PartialEq> PartialEq<Obligation<'db, T>> for Obligation<'db, T> {
129    #[inline]
130    fn eq(&self, other: &Obligation<'db, T>) -> bool {
131        // Ignore `cause` and `recursion_depth`. This is a small performance
132        // win for a few crates, and a huge performance win for the crate in
133        // https://github.com/rust-lang/rustc-perf/pull/1680, which greatly
134        // stresses the trait system.
135        self.param_env == other.param_env && self.predicate == other.predicate
136    }
137}
138
139impl<'db, T: Eq> Eq for Obligation<'db, T> {}
140
141impl<'db, T: Hash> Hash for Obligation<'db, T> {
142    fn hash<H: Hasher>(&self, state: &mut H) {
143        // See the comment on `Obligation::eq`.
144        self.param_env.hash(state);
145        self.predicate.hash(state);
146    }
147}
148
149impl<'db, P> From<Obligation<'db, P>> for Goal<'db, P> {
150    fn from(value: Obligation<'db, P>) -> Self {
151        Goal { param_env: value.param_env, predicate: value.predicate }
152    }
153}
154
155pub(crate) type PredicateObligation<'db> = Obligation<'db, Predicate<'db>>;
156pub(crate) type TraitObligation<'db> = Obligation<'db, TraitPredicate<'db>>;
157
158pub(crate) type PredicateObligations<'db> = Vec<PredicateObligation<'db>>;
159
160impl<'db> PredicateObligation<'db> {
161    /// Flips the polarity of the inner predicate.
162    ///
163    /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
164    pub fn flip_polarity(&self, interner: DbInterner<'db>) -> Option<PredicateObligation<'db>> {
165        Some(PredicateObligation {
166            cause: self.cause,
167            param_env: self.param_env,
168            predicate: self.predicate.flip_polarity(interner)?,
169            recursion_depth: self.recursion_depth,
170        })
171    }
172}
173
174impl<'db, O> Obligation<'db, O> {
175    pub fn new(
176        interner: DbInterner<'db>,
177        cause: ObligationCause,
178        param_env: ParamEnv<'db>,
179        predicate: impl Upcast<DbInterner<'db>, O>,
180    ) -> Obligation<'db, O> {
181        Self::with_depth(interner, cause, 0, param_env, predicate)
182    }
183
184    /// We often create nested obligations without setting the correct depth.
185    ///
186    /// To deal with this evaluate and fulfill explicitly update the depth
187    /// of nested obligations using this function.
188    pub fn set_depth_from_parent(&mut self, parent_depth: usize) {
189        self.recursion_depth = cmp::max(parent_depth + 1, self.recursion_depth);
190    }
191
192    pub fn with_depth(
193        interner: DbInterner<'db>,
194        cause: ObligationCause,
195        recursion_depth: usize,
196        param_env: ParamEnv<'db>,
197        predicate: impl Upcast<DbInterner<'db>, O>,
198    ) -> Obligation<'db, O> {
199        let predicate = predicate.upcast(interner);
200        Obligation { cause, param_env, recursion_depth, predicate }
201    }
202
203    pub fn with<P>(
204        &self,
205        tcx: DbInterner<'db>,
206        value: impl Upcast<DbInterner<'db>, P>,
207    ) -> Obligation<'db, P> {
208        Obligation::with_depth(tcx, self.cause, self.recursion_depth, self.param_env, value)
209    }
210}
211
212/// Determines whether the type `ty` is known to meet `bound` and
213/// returns true if so. Returns false if `ty` either does not meet
214/// `bound` or is not known to meet bound (note that this is
215/// conservative towards *no impl*, which is the opposite of the
216/// `evaluate` methods).
217pub(crate) fn type_known_to_meet_bound_modulo_regions<'tcx>(
218    infcx: &InferCtxt<'tcx>,
219    param_env: ParamEnv<'tcx>,
220    ty: Ty<'tcx>,
221    def_id: TraitId,
222) -> bool {
223    let trait_ref = TraitRef::new(infcx.interner, def_id.into(), [ty]);
224    pred_known_to_hold_modulo_regions(infcx, param_env, trait_ref)
225}
226
227/// FIXME(@lcnr): this function doesn't seem right and shouldn't exist?
228///
229/// Ping me on zulip if you want to use this method and need help with finding
230/// an appropriate replacement.
231fn pred_known_to_hold_modulo_regions<'db>(
232    infcx: &InferCtxt<'db>,
233    param_env: ParamEnv<'db>,
234    pred: impl Upcast<DbInterner<'db>, Predicate<'db>>,
235) -> bool {
236    let obligation = Obligation::new(infcx.interner, ObligationCause::dummy(), param_env, pred);
237
238    let result = infcx.evaluate_obligation(&obligation);
239    debug!(?result);
240
241    result.must_apply_modulo_regions()
242}
hir_ty/next_solver/infer/traits.rs

hir_ty/next_solver/infer/
traits.rs
