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

rustc_infer/infer/relate/
lattice.rs
