hir_ty/next_solver/infer/relate/
lattice.rs

1//! # Lattice variables
2//!
3//! Generic code for operating on [lattices] of inference variables
4//! that are characterized by an upper- and lower-bound.
5//!
6//! The code is defined quite generically so that it can be
7//! applied both to type variables, which represent types being inferred,
8//! and fn variables, which represent function types being inferred.
9//! (It may eventually be applied to their types as well.)
10//! In some cases, the functions are also generic with respect to the
11//! operation on the lattice (GLB vs LUB).
12//!
13//! ## Note
14//!
15//! Although all the functions are generic, for simplicity, comments in the source code
16//! generally refer to type variables and the LUB operation.
17//!
18//! [lattices]: https://en.wikipedia.org/wiki/Lattice_(order)
19
20use rustc_type_ir::{
21    AliasRelationDirection, Interner, TypeVisitableExt, Upcast, Variance,
22    inherent::IntoKind,
23    relate::{
24        Relate, StructurallyRelateAliases, TypeRelation, VarianceDiagInfo,
25        combine::{
26            PredicateEmittingRelation, combine_ty_args, super_combine_consts, super_combine_tys,
27        },
28    },
29};
30
31use crate::{
32    Span,
33    next_solver::{
34        AliasTy, Binder, Const, DbInterner, GenericArgs, Goal, ParamEnv, Predicate, PredicateKind,
35        Region, SolverDefId, Ty, TyKind,
36        infer::{
37            InferCtxt, TypeTrace,
38            relate::RelateResult,
39            traits::{Obligation, PredicateObligations},
40        },
41    },
42};
43
44#[derive(Clone, Copy)]
45pub(crate) enum LatticeOpKind {
46    Glb,
47    Lub,
48}
49
50impl LatticeOpKind {
51    fn invert(self) -> Self {
52        match self {
53            LatticeOpKind::Glb => LatticeOpKind::Lub,
54            LatticeOpKind::Lub => LatticeOpKind::Glb,
55        }
56    }
57}
58
59/// A greatest lower bound" (common subtype) or least upper bound (common supertype).
60pub(crate) struct LatticeOp<'infcx, 'db> {
61    infcx: &'infcx InferCtxt<'db>,
62    // Immutable fields
63    trace: TypeTrace<'db>,
64    param_env: ParamEnv<'db>,
65    // Mutable fields
66    kind: LatticeOpKind,
67    obligations: PredicateObligations<'db>,
68}
69
70impl<'infcx, 'db> LatticeOp<'infcx, 'db> {
71    pub(crate) fn new(
72        infcx: &'infcx InferCtxt<'db>,
73        trace: TypeTrace<'db>,
74        param_env: ParamEnv<'db>,
75        kind: LatticeOpKind,
76    ) -> LatticeOp<'infcx, 'db> {
77        LatticeOp { infcx, trace, param_env, kind, obligations: PredicateObligations::new() }
78    }
79
80    pub(crate) fn into_obligations(self) -> PredicateObligations<'db> {
81        self.obligations
82    }
83}
84
85impl<'db> TypeRelation<DbInterner<'db>> for LatticeOp<'_, 'db> {
86    fn cx(&self) -> DbInterner<'db> {
87        self.infcx.interner
88    }
89
90    fn relate_ty_args(
91        &mut self,
92        a_ty: Ty<'db>,
93        b_ty: Ty<'db>,
94        def_id: SolverDefId<'db>,
95        a_args: GenericArgs<'db>,
96        b_args: GenericArgs<'db>,
97        mk: impl FnOnce(GenericArgs<'db>) -> Ty<'db>,
98    ) -> RelateResult<'db, Ty<'db>> {
99        let variances = self.cx().variances_of(def_id);
100        combine_ty_args(self.infcx, self, a_ty, b_ty, variances, a_args, b_args, mk)
101    }
102
103    fn relate_with_variance<T: Relate<DbInterner<'db>>>(
104        &mut self,
105        variance: Variance,
106        _info: VarianceDiagInfo<DbInterner<'db>>,
107        a: T,
108        b: T,
109    ) -> RelateResult<'db, T> {
110        match variance {
111            Variance::Invariant => {
112                self.obligations.extend(
113                    self.infcx.at(&self.trace.cause, self.param_env).eq(a, b)?.into_obligations(),
114                );
115                Ok(a)
116            }
117            Variance::Covariant => self.relate(a, b),
118            // FIXME(#41044) -- not correct, need test
119            Variance::Bivariant => Ok(a),
120            Variance::Contravariant => {
121                self.kind = self.kind.invert();
122                let res = self.relate(a, b);
123                self.kind = self.kind.invert();
124                res
125            }
126        }
127    }
128
129    /// Relates two types using a given lattice.
130    fn tys(&mut self, a: Ty<'db>, b: Ty<'db>) -> RelateResult<'db, Ty<'db>> {
131        if a == b {
132            return Ok(a);
133        }
134
135        let infcx = self.infcx;
136
137        let a = infcx.shallow_resolve(a);
138        let b = infcx.shallow_resolve(b);
139
140        match (a.kind(), b.kind()) {
141            // If one side is known to be a variable and one is not,
142            // create a variable (`v`) to represent the LUB. Make sure to
143            // relate `v` to the non-type-variable first (by passing it
144            // first to `relate_bound`). Otherwise, we would produce a
145            // subtype obligation that must then be processed.
146            //
147            // Example: if the LHS is a type variable, and RHS is
148            // `Box<i32>`, then we current compare `v` to the RHS first,
149            // which will instantiate `v` with `Box<i32>`. Then when `v`
150            // is compared to the LHS, we instantiate LHS with `Box<i32>`.
151            // But if we did in reverse order, we would create a `v <:
152            // LHS` (or vice versa) constraint and then instantiate
153            // `v`. This would require further processing to achieve same
154            // end-result; in particular, this screws up some of the logic
155            // in coercion, which expects LUB to figure out that the LHS
156            // is (e.g.) `Box<i32>`. A more obvious solution might be to
157            // iterate on the subtype obligations that are returned, but I
158            // think this suffices. -nmatsakis
159            (TyKind::Infer(rustc_type_ir::TyVar(..)), _) => {
160                let v = infcx.next_ty_var(self.span());
161                self.relate_bound(v, b, a)?;
162                Ok(v)
163            }
164            (_, TyKind::Infer(rustc_type_ir::TyVar(..))) => {
165                let v = infcx.next_ty_var(self.span());
166                self.relate_bound(v, a, b)?;
167                Ok(v)
168            }
169
170            (
171                TyKind::Alias(AliasTy { kind: rustc_type_ir::Opaque { def_id: a_def_id }, .. }),
172                TyKind::Alias(AliasTy { kind: rustc_type_ir::Opaque { def_id: b_def_id }, .. }),
173            ) if a_def_id == b_def_id => super_combine_tys(infcx, self, a, b),
174
175            _ => super_combine_tys(infcx, self, a, b),
176        }
177    }
178
179    fn regions(&mut self, a: Region<'db>, b: Region<'db>) -> RelateResult<'db, Region<'db>> {
180        let mut inner = self.infcx.inner.borrow_mut();
181        let mut constraints = inner.unwrap_region_constraints();
182        Ok(match self.kind {
183            // GLB(&'static u8, &'a u8) == &RegionLUB('static, 'a) u8 == &'static u8
184            LatticeOpKind::Glb => constraints.lub_regions(self.cx(), self.span(), a, b),
185
186            // LUB(&'static u8, &'a u8) == &RegionGLB('static, 'a) u8 == &'a u8
187            LatticeOpKind::Lub => constraints.glb_regions(self.cx(), self.span(), a, b),
188        })
189    }
190
191    fn consts(&mut self, a: Const<'db>, b: Const<'db>) -> RelateResult<'db, Const<'db>> {
192        super_combine_consts(self.infcx, self, a, b)
193    }
194
195    fn binders<T>(
196        &mut self,
197        a: Binder<'db, T>,
198        b: Binder<'db, T>,
199    ) -> RelateResult<'db, Binder<'db, T>>
200    where
201        T: Relate<DbInterner<'db>>,
202    {
203        // GLB/LUB of a binder and itself is just itself
204        if a == b {
205            return Ok(a);
206        }
207
208        if a.skip_binder().has_escaping_bound_vars() || b.skip_binder().has_escaping_bound_vars() {
209            // When higher-ranked types are involved, computing the GLB/LUB is
210            // very challenging, switch to invariance. This is obviously
211            // overly conservative but works ok in practice.
212            self.relate_with_variance(Variance::Invariant, VarianceDiagInfo::default(), a, b)?;
213            Ok(a)
214        } else {
215            Ok(Binder::dummy(self.relate(a.skip_binder(), b.skip_binder())?))
216        }
217    }
218}
219
220impl<'infcx, 'db> LatticeOp<'infcx, 'db> {
221    // Relates the type `v` to `a` and `b` such that `v` represents
222    // the LUB/GLB of `a` and `b` as appropriate.
223    //
224    // Subtle hack: ordering *may* be significant here. This method
225    // relates `v` to `a` first, which may help us to avoid unnecessary
226    // type variable obligations. See caller for details.
227    fn relate_bound(&mut self, v: Ty<'db>, a: Ty<'db>, b: Ty<'db>) -> RelateResult<'db, ()> {
228        let at = self.infcx.at(&self.trace.cause, self.param_env);
229        match self.kind {
230            LatticeOpKind::Glb => {
231                self.obligations.extend(at.sub(v, a)?.into_obligations());
232                self.obligations.extend(at.sub(v, b)?.into_obligations());
233            }
234            LatticeOpKind::Lub => {
235                self.obligations.extend(at.sub(a, v)?.into_obligations());
236                self.obligations.extend(at.sub(b, v)?.into_obligations());
237            }
238        }
239        Ok(())
240    }
241}
242
243impl<'db> PredicateEmittingRelation<InferCtxt<'db>> for LatticeOp<'_, 'db> {
244    fn span(&self) -> Span {
245        self.trace.cause.span()
246    }
247
248    fn structurally_relate_aliases(&self) -> StructurallyRelateAliases {
249        StructurallyRelateAliases::No
250    }
251
252    fn param_env(&self) -> ParamEnv<'db> {
253        self.param_env
254    }
255
256    fn register_predicates(
257        &mut self,
258        preds: impl IntoIterator<Item: Upcast<DbInterner<'db>, Predicate<'db>>>,
259    ) {
260        self.obligations.extend(preds.into_iter().map(|pred| {
261            Obligation::new(self.infcx.interner, self.trace.cause, self.param_env, pred)
262        }))
263    }
264
265    fn register_goals(&mut self, goals: impl IntoIterator<Item = Goal<'db, Predicate<'db>>>) {
266        self.obligations.extend(goals.into_iter().map(|goal| {
267            Obligation::new(self.infcx.interner, self.trace.cause, goal.param_env, goal.predicate)
268        }))
269    }
270
271    fn register_alias_relate_predicate(&mut self, a: Ty<'db>, b: Ty<'db>) {
272        self.register_predicates([Binder::dummy(PredicateKind::AliasRelate(
273            a.into(),
274            b.into(),
275            // FIXME(deferred_projection_equality): This isn't right, I think?
276            AliasRelationDirection::Equate,
277        ))]);
278    }
279}
hir_ty/next_solver/infer/relate/lattice.rs

hir_ty/next_solver/infer/relate/
lattice.rs
