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

rustc_infer/infer/relate/
lattice.rs
