]>
Commit | Line | Data |
---|---|---|
f9f354fc XL |
1 | use chalk_ir::cast::Cast; |
2 | use chalk_ir::interner::Interner; | |
3 | use chalk_ir::*; | |
4 | use ena::unify::{UnifyKey, UnifyValue}; | |
5 | use std::cmp::min; | |
6 | use std::fmt; | |
7 | use std::marker::PhantomData; | |
8 | use std::u32; | |
9 | ||
10 | /// Wrapper around `chalk_ir::InferenceVar` for coherence purposes. | |
11 | /// An inference variable represents an unknown term -- either a type | |
12 | /// or a lifetime. The variable itself is just an index into the | |
13 | /// unification table; the unification table maps it to an | |
14 | /// `InferenceValue`. | |
15 | /// | |
16 | /// Inference variables can be in one of two states (represents by the variants | |
17 | /// of an `InferenceValue`): | |
18 | /// | |
19 | /// - Unbound(`ui`). In this case, the value of the variable is not yet known. We carry | |
20 | /// along a universe index `ui` that tracks the universe in which the variable was | |
21 | /// created; this determines what names may appear in the variable's value. | |
22 | /// - In this state, we do **not** track the kind of this variable | |
23 | /// (i.e., whether it represents a type or a lifetime). There is | |
24 | /// no need: if it represents a lifetime, for example, then there | |
25 | /// should only ever be constraints that relate it to other | |
26 | /// lifetimes, or use it in lifetime position. | |
27 | /// - Bound. In this case, the value of the variable is known. We | |
28 | /// carry along the value. We discard the universe index in which | |
29 | /// the variable was created, since that was only needed to help us | |
30 | /// reject illegal values. Once the value of a variable is known, it | |
31 | /// can never change. | |
32 | /// - The value we actually store for variables is a | |
f035d41b | 33 | /// `ir::GenericArg`, and hence it does carry along the kind of the |
f9f354fc XL |
34 | /// variable via the enum variant. However, we should always know |
35 | /// the kind of the variable from context, and hence we typically | |
36 | /// "downcast" the resulting variable using | |
37 | /// e.g. `value.ty().unwrap()`. | |
38 | #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |
3dfed10e | 39 | pub struct EnaVariable<I: Interner> { |
f9f354fc XL |
40 | var: InferenceVar, |
41 | phantom: PhantomData<I>, | |
42 | } | |
43 | ||
44 | impl<I: Interner> From<InferenceVar> for EnaVariable<I> { | |
45 | fn from(var: InferenceVar) -> EnaVariable<I> { | |
46 | EnaVariable { | |
47 | var, | |
48 | phantom: PhantomData, | |
49 | } | |
50 | } | |
51 | } | |
52 | ||
5869c6ff XL |
53 | impl<I: Interner> From<EnaVariable<I>> for InferenceVar { |
54 | fn from(ena_var: EnaVariable<I>) -> InferenceVar { | |
55 | ena_var.var | |
56 | } | |
57 | } | |
58 | ||
f9f354fc XL |
59 | impl<I: Interner> EnaVariable<I> { |
60 | /// Convert this inference variable into a type. When using this | |
61 | /// method, naturally you should know from context that the kind | |
62 | /// of this inference variable is a type (we can't check it). | |
a2a8927a | 63 | pub fn to_ty_with_kind(self, interner: I, kind: TyVariableKind) -> Ty<I> { |
f035d41b XL |
64 | self.var.to_ty(interner, kind) |
65 | } | |
66 | ||
29967ef6 | 67 | /// Same as `to_ty_with_kind`, but the kind is set to `TyVariableKind::General`. |
f035d41b XL |
68 | /// This should be used instead of `to_ty_with_kind` when creating a new |
69 | /// inference variable (when the kind is not known). | |
a2a8927a | 70 | pub fn to_ty(self, interner: I) -> Ty<I> { |
29967ef6 | 71 | self.var.to_ty(interner, TyVariableKind::General) |
f9f354fc XL |
72 | } |
73 | ||
74 | /// Convert this inference variable into a lifetime. When using this | |
75 | /// method, naturally you should know from context that the kind | |
76 | /// of this inference variable is a lifetime (we can't check it). | |
a2a8927a | 77 | pub fn to_lifetime(self, interner: I) -> Lifetime<I> { |
f9f354fc XL |
78 | self.var.to_lifetime(interner) |
79 | } | |
f035d41b XL |
80 | |
81 | /// Convert this inference variable into a const. When using this | |
82 | /// method, naturally you should know from context that the kind | |
83 | /// of this inference variable is a const (we can't check it). | |
a2a8927a | 84 | pub fn to_const(self, interner: I, ty: Ty<I>) -> Const<I> { |
f035d41b XL |
85 | self.var.to_const(interner, ty) |
86 | } | |
f9f354fc XL |
87 | } |
88 | ||
89 | impl<I: Interner> UnifyKey for EnaVariable<I> { | |
90 | type Value = InferenceValue<I>; | |
91 | ||
92 | fn index(&self) -> u32 { | |
93 | self.var.index() | |
94 | } | |
95 | ||
96 | fn from_index(u: u32) -> Self { | |
97 | EnaVariable::from(InferenceVar::from(u)) | |
98 | } | |
99 | ||
100 | fn tag() -> &'static str { | |
101 | "EnaVariable" | |
102 | } | |
103 | } | |
104 | ||
105 | /// The value of an inference variable. We start out as `Unbound` with a | |
106 | /// universe index; when the inference variable is assigned a value, it becomes | |
107 | /// bound and records that value. See `EnaVariable` for more details. | |
108 | #[derive(Clone, Debug, PartialEq, Eq)] | |
3dfed10e | 109 | pub enum InferenceValue<I: Interner> { |
f9f354fc | 110 | Unbound(UniverseIndex), |
f035d41b | 111 | Bound(GenericArg<I>), |
f9f354fc XL |
112 | } |
113 | ||
114 | impl<I: Interner> InferenceValue<I> { | |
a2a8927a | 115 | pub fn from_ty(interner: I, ty: Ty<I>) -> Self { |
f9f354fc XL |
116 | InferenceValue::Bound(ty.cast(interner)) |
117 | } | |
118 | ||
a2a8927a | 119 | pub fn from_lifetime(interner: I, lifetime: Lifetime<I>) -> Self { |
f9f354fc XL |
120 | InferenceValue::Bound(lifetime.cast(interner)) |
121 | } | |
f035d41b | 122 | |
a2a8927a | 123 | pub fn from_const(interner: I, constant: Const<I>) -> Self { |
f035d41b XL |
124 | InferenceValue::Bound(constant.cast(interner)) |
125 | } | |
f9f354fc XL |
126 | } |
127 | ||
128 | impl<I: Interner> UnifyValue for InferenceValue<I> { | |
129 | type Error = (InferenceValue<I>, InferenceValue<I>); | |
130 | ||
131 | fn unify_values( | |
132 | a: &InferenceValue<I>, | |
133 | b: &InferenceValue<I>, | |
134 | ) -> Result<InferenceValue<I>, (InferenceValue<I>, InferenceValue<I>)> { | |
135 | match (a, b) { | |
136 | (&InferenceValue::Unbound(ui_a), &InferenceValue::Unbound(ui_b)) => { | |
137 | Ok(InferenceValue::Unbound(min(ui_a, ui_b))) | |
138 | } | |
139 | (bound @ &InferenceValue::Bound(_), &InferenceValue::Unbound(_)) | |
140 | | (&InferenceValue::Unbound(_), bound @ &InferenceValue::Bound(_)) => Ok(bound.clone()), | |
141 | (&InferenceValue::Bound(_), &InferenceValue::Bound(_)) => { | |
142 | panic!("we should not be asked to unify two bound things") | |
143 | } | |
144 | } | |
145 | } | |
146 | } | |
147 | ||
148 | impl<I: Interner> fmt::Debug for EnaVariable<I> { | |
149 | fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> { | |
150 | write!(fmt, "{:?}", self.var) | |
151 | } | |
152 | } |