]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //! # Lattice Variables |
2 | //! | |
3 | //! This file contains generic code for operating on inference variables | |
9fa01778 | 4 | //! that are characterized by an upper- and lower-bound. The logic and |
1a4d82fc JJ |
5 | //! reasoning is explained in detail in the large comment in `infer.rs`. |
6 | //! | |
7 | //! The code in here is defined quite generically so that it can be | |
8 | //! applied both to type variables, which represent types being inferred, | |
9 | //! and fn variables, which represent function types being inferred. | |
10 | //! It may eventually be applied to their types as well, who knows. | |
11 | //! In some cases, the functions are also generic with respect to the | |
12 | //! operation on the lattice (GLB vs LUB). | |
13 | //! | |
14 | //! Although all the functions are generic, we generally write the | |
15 | //! comments in a way that is specific to type variables and the LUB | |
9fa01778 | 16 | //! operation. It's just easier that way. |
1a4d82fc JJ |
17 | //! |
18 | //! In general all of the functions are defined parametrically | |
19 | //! over a `LatticeValue`, which is a value defined with respect to | |
20 | //! a lattice. | |
21 | ||
c34b1796 | 22 | use super::InferCtxt; |
dc9dc135 | 23 | use super::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; |
1a4d82fc | 24 | |
9fa01778 XL |
25 | use crate::traits::ObligationCause; |
26 | use crate::ty::TyVar; | |
27 | use crate::ty::{self, Ty}; | |
28 | use crate::ty::relate::{RelateResult, TypeRelation}; | |
1a4d82fc | 29 | |
dc9dc135 XL |
30 | pub trait LatticeDir<'f, 'tcx>: TypeRelation<'tcx> { |
31 | fn infcx(&self) -> &'f InferCtxt<'f, 'tcx>; | |
c34b1796 | 32 | |
476ff2be SL |
33 | fn cause(&self) -> &ObligationCause<'tcx>; |
34 | ||
1a4d82fc JJ |
35 | // Relates the type `v` to `a` and `b` such that `v` represents |
36 | // the LUB/GLB of `a` and `b` as appropriate. | |
cc61c64b XL |
37 | // |
38 | // Subtle hack: ordering *may* be significant here. This method | |
3b2f2976 | 39 | // relates `v` to `a` first, which may help us to avoid unnecessary |
cc61c64b | 40 | // type variable obligations. See caller for details. |
5bcae85e | 41 | fn relate_bound(&mut self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()>; |
1a4d82fc JJ |
42 | } |
43 | ||
dc9dc135 XL |
44 | pub fn super_lattice_tys<'a, 'tcx: 'a, L>( |
45 | this: &mut L, | |
46 | a: Ty<'tcx>, | |
47 | b: Ty<'tcx>, | |
48 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
49 | where | |
50 | L: LatticeDir<'a, 'tcx>, | |
1a4d82fc | 51 | { |
62682a34 | 52 | debug!("{}.lattice_tys({:?}, {:?})", |
1a4d82fc | 53 | this.tag(), |
62682a34 SL |
54 | a, |
55 | b); | |
1a4d82fc JJ |
56 | |
57 | if a == b { | |
58 | return Ok(a); | |
59 | } | |
60 | ||
61 | let infcx = this.infcx(); | |
54a0048b SL |
62 | let a = infcx.type_variables.borrow_mut().replace_if_possible(a); |
63 | let b = infcx.type_variables.borrow_mut().replace_if_possible(b); | |
1a4d82fc | 64 | match (&a.sty, &b.sty) { |
cc61c64b XL |
65 | // If one side is known to be a variable and one is not, |
66 | // create a variable (`v`) to represent the LUB. Make sure to | |
67 | // relate `v` to the non-type-variable first (by passing it | |
68 | // first to `relate_bound`). Otherwise, we would produce a | |
69 | // subtype obligation that must then be processed. | |
70 | // | |
71 | // Example: if the LHS is a type variable, and RHS is | |
72 | // `Box<i32>`, then we current compare `v` to the RHS first, | |
73 | // which will instantiate `v` with `Box<i32>`. Then when `v` | |
74 | // is compared to the LHS, we instantiate LHS with `Box<i32>`. | |
75 | // But if we did in reverse order, we would create a `v <: | |
76 | // LHS` (or vice versa) constraint and then instantiate | |
77 | // `v`. This would require further processing to achieve same | |
78 | // end-result; in partiular, this screws up some of the logic | |
79 | // in coercion, which expects LUB to figure out that the LHS | |
80 | // is (e.g.) `Box<i32>`. A more obvious solution might be to | |
81 | // iterate on the subtype obligations that are returned, but I | |
82 | // think this suffices. -nmatsakis | |
b7449926 | 83 | (&ty::Infer(TyVar(..)), _) => { |
dc9dc135 XL |
84 | let v = infcx.next_ty_var(TypeVariableOrigin { |
85 | kind: TypeVariableOriginKind::LatticeVariable, | |
86 | span: this.cause().span, | |
87 | }); | |
cc61c64b XL |
88 | this.relate_bound(v, b, a)?; |
89 | Ok(v) | |
90 | } | |
b7449926 | 91 | (_, &ty::Infer(TyVar(..))) => { |
dc9dc135 XL |
92 | let v = infcx.next_ty_var(TypeVariableOrigin { |
93 | kind: TypeVariableOriginKind::LatticeVariable, | |
94 | span: this.cause().span, | |
95 | }); | |
54a0048b | 96 | this.relate_bound(v, a, b)?; |
1a4d82fc JJ |
97 | Ok(v) |
98 | } | |
99 | ||
100 | _ => { | |
a7813a04 | 101 | infcx.super_combine_tys(this, a, b) |
1a4d82fc JJ |
102 | } |
103 | } | |
104 | } |