diff options
Diffstat (limited to 'crates/hir_ty/src/infer/unify.rs')
-rw-r--r-- | crates/hir_ty/src/infer/unify.rs | 861 |
1 files changed, 382 insertions, 479 deletions
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs index d8e0b4320..21d3fb54e 100644 --- a/crates/hir_ty/src/infer/unify.rs +++ b/crates/hir_ty/src/infer/unify.rs | |||
@@ -1,177 +1,95 @@ | |||
1 | //! Unification and canonicalization logic. | 1 | //! Unification and canonicalization logic. |
2 | 2 | ||
3 | use std::borrow::Cow; | 3 | use std::{fmt, mem, sync::Arc}; |
4 | 4 | ||
5 | use chalk_ir::{ | 5 | use chalk_ir::{ |
6 | cast::Cast, fold::Fold, interner::HasInterner, FloatTy, IntTy, TyVariableKind, UniverseIndex, | 6 | cast::Cast, fold::Fold, interner::HasInterner, zip::Zip, FloatTy, IntTy, TyVariableKind, |
7 | VariableKind, | 7 | UniverseIndex, |
8 | }; | 8 | }; |
9 | use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; | 9 | use chalk_solve::infer::ParameterEnaVariableExt; |
10 | use ena::unify::UnifyKey; | ||
10 | 11 | ||
11 | use super::{DomainGoal, InferenceContext}; | 12 | use super::{InferOk, InferResult, InferenceContext, TypeError}; |
12 | use crate::{ | 13 | use crate::{ |
13 | fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, | 14 | db::HirDatabase, fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, |
14 | DebruijnIndex, FnPointer, FnSubst, InEnvironment, InferenceVar, Interner, Scalar, Substitution, | 15 | DebruijnIndex, GenericArg, Goal, Guidance, InEnvironment, InferenceVar, Interner, ProjectionTy, |
15 | Ty, TyExt, TyKind, WhereClause, | 16 | Scalar, Solution, Substitution, TraitEnvironment, Ty, TyKind, VariableKind, |
16 | }; | 17 | }; |
17 | 18 | ||
18 | impl<'a> InferenceContext<'a> { | 19 | impl<'a> InferenceContext<'a> { |
19 | pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b> | 20 | pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>( |
21 | &mut self, | ||
22 | t: T, | ||
23 | ) -> Canonicalized<T::Result> | ||
20 | where | 24 | where |
21 | 'a: 'b, | 25 | T::Result: HasInterner<Interner = Interner>, |
22 | { | 26 | { |
23 | Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() } | 27 | // try to resolve obligations before canonicalizing, since this might |
28 | // result in new knowledge about variables | ||
29 | self.resolve_obligations_as_possible(); | ||
30 | self.table.canonicalize(t) | ||
24 | } | 31 | } |
25 | } | 32 | } |
26 | 33 | ||
27 | pub(super) struct Canonicalizer<'a, 'b> | 34 | #[derive(Debug, Clone)] |
28 | where | ||
29 | 'a: 'b, | ||
30 | { | ||
31 | ctx: &'b mut InferenceContext<'a>, | ||
32 | free_vars: Vec<(InferenceVar, TyVariableKind)>, | ||
33 | /// A stack of type variables that is used to detect recursive types (which | ||
34 | /// are an error, but we need to protect against them to avoid stack | ||
35 | /// overflows). | ||
36 | var_stack: Vec<TypeVarId>, | ||
37 | } | ||
38 | |||
39 | #[derive(Debug)] | ||
40 | pub(super) struct Canonicalized<T> | 35 | pub(super) struct Canonicalized<T> |
41 | where | 36 | where |
42 | T: HasInterner<Interner = Interner>, | 37 | T: HasInterner<Interner = Interner>, |
43 | { | 38 | { |
44 | pub(super) value: Canonical<T>, | 39 | pub(super) value: Canonical<T>, |
45 | free_vars: Vec<(InferenceVar, TyVariableKind)>, | 40 | free_vars: Vec<GenericArg>, |
46 | } | ||
47 | |||
48 | impl<'a, 'b> Canonicalizer<'a, 'b> { | ||
49 | fn add(&mut self, free_var: InferenceVar, kind: TyVariableKind) -> usize { | ||
50 | self.free_vars.iter().position(|&(v, _)| v == free_var).unwrap_or_else(|| { | ||
51 | let next_index = self.free_vars.len(); | ||
52 | self.free_vars.push((free_var, kind)); | ||
53 | next_index | ||
54 | }) | ||
55 | } | ||
56 | |||
57 | fn do_canonicalize<T: Fold<Interner, Result = T> + HasInterner<Interner = Interner>>( | ||
58 | &mut self, | ||
59 | t: T, | ||
60 | binders: DebruijnIndex, | ||
61 | ) -> T { | ||
62 | fold_tys( | ||
63 | t, | ||
64 | |ty, binders| match ty.kind(&Interner) { | ||
65 | &TyKind::InferenceVar(var, kind) => { | ||
66 | let inner = from_inference_var(var); | ||
67 | if self.var_stack.contains(&inner) { | ||
68 | // recursive type | ||
69 | return self.ctx.table.type_variable_table.fallback_value(var, kind); | ||
70 | } | ||
71 | if let Some(known_ty) = | ||
72 | self.ctx.table.var_unification_table.inlined_probe_value(inner).known() | ||
73 | { | ||
74 | self.var_stack.push(inner); | ||
75 | let result = self.do_canonicalize(known_ty.clone(), binders); | ||
76 | self.var_stack.pop(); | ||
77 | result | ||
78 | } else { | ||
79 | let root = self.ctx.table.var_unification_table.find(inner); | ||
80 | let position = self.add(to_inference_var(root), kind); | ||
81 | TyKind::BoundVar(BoundVar::new(binders, position)).intern(&Interner) | ||
82 | } | ||
83 | } | ||
84 | _ => ty, | ||
85 | }, | ||
86 | binders, | ||
87 | ) | ||
88 | } | ||
89 | |||
90 | fn into_canonicalized<T: HasInterner<Interner = Interner>>( | ||
91 | self, | ||
92 | result: T, | ||
93 | ) -> Canonicalized<T> { | ||
94 | let kinds = self | ||
95 | .free_vars | ||
96 | .iter() | ||
97 | .map(|&(_, k)| chalk_ir::WithKind::new(VariableKind::Ty(k), UniverseIndex::ROOT)); | ||
98 | Canonicalized { | ||
99 | value: Canonical { | ||
100 | value: result, | ||
101 | binders: CanonicalVarKinds::from_iter(&Interner, kinds), | ||
102 | }, | ||
103 | free_vars: self.free_vars, | ||
104 | } | ||
105 | } | ||
106 | |||
107 | pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> { | ||
108 | let result = self.do_canonicalize(ty, DebruijnIndex::INNERMOST); | ||
109 | self.into_canonicalized(result) | ||
110 | } | ||
111 | |||
112 | pub(crate) fn canonicalize_obligation( | ||
113 | mut self, | ||
114 | obligation: InEnvironment<DomainGoal>, | ||
115 | ) -> Canonicalized<InEnvironment<DomainGoal>> { | ||
116 | let result = match obligation.goal { | ||
117 | DomainGoal::Holds(wc) => { | ||
118 | DomainGoal::Holds(self.do_canonicalize(wc, DebruijnIndex::INNERMOST)) | ||
119 | } | ||
120 | _ => unimplemented!(), | ||
121 | }; | ||
122 | self.into_canonicalized(InEnvironment { goal: result, environment: obligation.environment }) | ||
123 | } | ||
124 | } | 41 | } |
125 | 42 | ||
126 | impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { | 43 | impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { |
127 | pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty { | 44 | pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty { |
128 | crate::fold_free_vars(ty, |bound, _binders| { | 45 | chalk_ir::Substitute::apply(&self.free_vars, ty, &Interner) |
129 | let (v, k) = self.free_vars[bound.index]; | ||
130 | TyKind::InferenceVar(v, k).intern(&Interner) | ||
131 | }) | ||
132 | } | 46 | } |
133 | 47 | ||
134 | pub(super) fn apply_solution( | 48 | pub(super) fn apply_solution( |
135 | &self, | 49 | &self, |
136 | ctx: &mut InferenceContext<'_>, | 50 | ctx: &mut InferenceTable, |
137 | solution: Canonical<Substitution>, | 51 | solution: Canonical<Substitution>, |
138 | ) { | 52 | ) { |
139 | // the solution may contain new variables, which we need to convert to new inference vars | 53 | // the solution may contain new variables, which we need to convert to new inference vars |
140 | let new_vars = Substitution::from_iter( | 54 | let new_vars = Substitution::from_iter( |
141 | &Interner, | 55 | &Interner, |
142 | solution.binders.iter(&Interner).map(|k| match k.kind { | 56 | solution.binders.iter(&Interner).map(|k| match k.kind { |
143 | VariableKind::Ty(TyVariableKind::General) => { | 57 | VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(&Interner), |
144 | ctx.table.new_type_var().cast(&Interner) | 58 | VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(&Interner), |
145 | } | 59 | VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(&Interner), |
146 | VariableKind::Ty(TyVariableKind::Integer) => { | ||
147 | ctx.table.new_integer_var().cast(&Interner) | ||
148 | } | ||
149 | VariableKind::Ty(TyVariableKind::Float) => { | ||
150 | ctx.table.new_float_var().cast(&Interner) | ||
151 | } | ||
152 | // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere | 60 | // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere |
153 | VariableKind::Lifetime => static_lifetime().cast(&Interner), | 61 | VariableKind::Lifetime => static_lifetime().cast(&Interner), |
154 | _ => panic!("const variable in solution"), | 62 | _ => panic!("const variable in solution"), |
155 | }), | 63 | }), |
156 | ); | 64 | ); |
157 | for (i, ty) in solution.value.iter(&Interner).enumerate() { | 65 | for (i, v) in solution.value.iter(&Interner).enumerate() { |
158 | let (v, k) = self.free_vars[i]; | 66 | let var = self.free_vars[i].clone(); |
159 | // eagerly replace projections in the type; we may be getting types | 67 | if let Some(ty) = v.ty(&Interner) { |
160 | // e.g. from where clauses where this hasn't happened yet | 68 | // eagerly replace projections in the type; we may be getting types |
161 | let ty = ctx.normalize_associated_types_in( | 69 | // e.g. from where clauses where this hasn't happened yet |
162 | new_vars.apply(ty.assert_ty_ref(&Interner).clone(), &Interner), | 70 | let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner)); |
163 | ); | 71 | ctx.unify(var.assert_ty_ref(&Interner), &ty); |
164 | ctx.table.unify(&TyKind::InferenceVar(v, k).intern(&Interner), &ty); | 72 | } else { |
73 | let _ = ctx.try_unify(&var, &new_vars.apply(v.clone(), &Interner)); | ||
74 | } | ||
165 | } | 75 | } |
166 | } | 76 | } |
167 | } | 77 | } |
168 | 78 | ||
169 | pub fn could_unify(t1: &Ty, t2: &Ty) -> bool { | 79 | pub fn could_unify( |
170 | InferenceTable::new().unify(t1, t2) | 80 | db: &dyn HirDatabase, |
81 | env: Arc<TraitEnvironment>, | ||
82 | tys: &Canonical<(Ty, Ty)>, | ||
83 | ) -> bool { | ||
84 | unify(db, env, tys).is_some() | ||
171 | } | 85 | } |
172 | 86 | ||
173 | pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { | 87 | pub(crate) fn unify( |
174 | let mut table = InferenceTable::new(); | 88 | db: &dyn HirDatabase, |
89 | env: Arc<TraitEnvironment>, | ||
90 | tys: &Canonical<(Ty, Ty)>, | ||
91 | ) -> Option<Substitution> { | ||
92 | let mut table = InferenceTable::new(db, env); | ||
175 | let vars = Substitution::from_iter( | 93 | let vars = Substitution::from_iter( |
176 | &Interner, | 94 | &Interner, |
177 | tys.binders | 95 | tys.binders |
@@ -187,77 +105,151 @@ pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { | |||
187 | } | 105 | } |
188 | // default any type vars that weren't unified back to their original bound vars | 106 | // default any type vars that weren't unified back to their original bound vars |
189 | // (kind of hacky) | 107 | // (kind of hacky) |
190 | for (i, var) in vars.iter(&Interner).enumerate() { | 108 | let find_var = |iv| { |
191 | let var = var.assert_ty_ref(&Interner); | 109 | vars.iter(&Interner).position(|v| match v.interned() { |
192 | if &*table.resolve_ty_shallow(var) == var { | 110 | chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner), |
193 | table.unify( | 111 | chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner), |
194 | var, | 112 | chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner), |
195 | &TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, i)).intern(&Interner), | 113 | } == Some(iv)) |
196 | ); | 114 | }; |
197 | } | 115 | let fallback = |iv, kind, default, binder| match kind { |
198 | } | 116 | chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv) |
117 | .map_or(default, |i| BoundVar::new(binder, i).to_ty(&Interner).cast(&Interner)), | ||
118 | chalk_ir::VariableKind::Lifetime => find_var(iv) | ||
119 | .map_or(default, |i| BoundVar::new(binder, i).to_lifetime(&Interner).cast(&Interner)), | ||
120 | chalk_ir::VariableKind::Const(ty) => find_var(iv) | ||
121 | .map_or(default, |i| BoundVar::new(binder, i).to_const(&Interner, ty).cast(&Interner)), | ||
122 | }; | ||
199 | Some(Substitution::from_iter( | 123 | Some(Substitution::from_iter( |
200 | &Interner, | 124 | &Interner, |
201 | vars.iter(&Interner) | 125 | vars.iter(&Interner) |
202 | .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())), | 126 | .map(|v| table.resolve_with_fallback(v.assert_ty_ref(&Interner).clone(), fallback)), |
203 | )) | 127 | )) |
204 | } | 128 | } |
205 | 129 | ||
206 | #[derive(Clone, Debug)] | 130 | #[derive(Copy, Clone, Debug)] |
207 | pub(super) struct TypeVariableTable { | 131 | pub(crate) struct TypeVariableData { |
208 | inner: Vec<TypeVariableData>, | 132 | diverging: bool, |
209 | } | 133 | } |
210 | 134 | ||
211 | impl TypeVariableTable { | 135 | type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>; |
212 | fn push(&mut self, data: TypeVariableData) { | 136 | |
213 | self.inner.push(data); | 137 | #[derive(Clone)] |
138 | pub(crate) struct InferenceTable<'a> { | ||
139 | pub(crate) db: &'a dyn HirDatabase, | ||
140 | pub(crate) trait_env: Arc<TraitEnvironment>, | ||
141 | var_unification_table: ChalkInferenceTable, | ||
142 | type_variable_table: Vec<TypeVariableData>, | ||
143 | pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>, | ||
144 | } | ||
145 | |||
146 | impl<'a> InferenceTable<'a> { | ||
147 | pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self { | ||
148 | InferenceTable { | ||
149 | db, | ||
150 | trait_env, | ||
151 | var_unification_table: ChalkInferenceTable::new(), | ||
152 | type_variable_table: Vec::new(), | ||
153 | pending_obligations: Vec::new(), | ||
154 | } | ||
214 | } | 155 | } |
215 | 156 | ||
216 | pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { | 157 | /// Chalk doesn't know about the `diverging` flag, so when it unifies two |
217 | self.inner[from_inference_var(iv).0 as usize].diverging = diverging; | 158 | /// type variables of which one is diverging, the chosen root might not be |
159 | /// diverging and we have no way of marking it as such at that time. This | ||
160 | /// function goes through all type variables and make sure their root is | ||
161 | /// marked as diverging if necessary, so that resolving them gives the right | ||
162 | /// result. | ||
163 | pub(super) fn propagate_diverging_flag(&mut self) { | ||
164 | for i in 0..self.type_variable_table.len() { | ||
165 | if !self.type_variable_table[i].diverging { | ||
166 | continue; | ||
167 | } | ||
168 | let v = InferenceVar::from(i as u32); | ||
169 | let root = self.var_unification_table.inference_var_root(v); | ||
170 | if let Some(data) = self.type_variable_table.get_mut(root.index() as usize) { | ||
171 | data.diverging = true; | ||
172 | } | ||
173 | } | ||
218 | } | 174 | } |
219 | 175 | ||
220 | fn is_diverging(&mut self, iv: InferenceVar) -> bool { | 176 | pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { |
221 | self.inner[from_inference_var(iv).0 as usize].diverging | 177 | self.type_variable_table[iv.index() as usize].diverging = diverging; |
222 | } | 178 | } |
223 | 179 | ||
224 | fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { | 180 | fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { |
225 | match kind { | 181 | match kind { |
226 | _ if self.inner[from_inference_var(iv).0 as usize].diverging => TyKind::Never, | 182 | _ if self |
183 | .type_variable_table | ||
184 | .get(iv.index() as usize) | ||
185 | .map_or(false, |data| data.diverging) => | ||
186 | { | ||
187 | TyKind::Never | ||
188 | } | ||
227 | TyVariableKind::General => TyKind::Error, | 189 | TyVariableKind::General => TyKind::Error, |
228 | TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), | 190 | TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), |
229 | TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), | 191 | TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), |
230 | } | 192 | } |
231 | .intern(&Interner) | 193 | .intern(&Interner) |
232 | } | 194 | } |
233 | } | ||
234 | 195 | ||
235 | #[derive(Copy, Clone, Debug)] | 196 | pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>( |
236 | pub(crate) struct TypeVariableData { | 197 | &mut self, |
237 | diverging: bool, | 198 | t: T, |
238 | } | 199 | ) -> Canonicalized<T::Result> |
200 | where | ||
201 | T::Result: HasInterner<Interner = Interner>, | ||
202 | { | ||
203 | let result = self.var_unification_table.canonicalize(&Interner, t); | ||
204 | let free_vars = result | ||
205 | .free_vars | ||
206 | .into_iter() | ||
207 | .map(|free_var| free_var.to_generic_arg(&Interner)) | ||
208 | .collect(); | ||
209 | Canonicalized { value: result.quantified, free_vars } | ||
210 | } | ||
211 | |||
212 | /// Recurses through the given type, normalizing associated types mentioned | ||
213 | /// in it by replacing them by type variables and registering obligations to | ||
214 | /// resolve later. This should be done once for every type we get from some | ||
215 | /// type annotation (e.g. from a let type annotation, field type or function | ||
216 | /// call). `make_ty` handles this already, but e.g. for field types we need | ||
217 | /// to do it as well. | ||
218 | pub(super) fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { | ||
219 | fold_tys( | ||
220 | ty, | ||
221 | |ty, _| match ty.kind(&Interner) { | ||
222 | TyKind::Alias(AliasTy::Projection(proj_ty)) => { | ||
223 | self.normalize_projection_ty(proj_ty.clone()) | ||
224 | } | ||
225 | _ => ty, | ||
226 | }, | ||
227 | DebruijnIndex::INNERMOST, | ||
228 | ) | ||
229 | } | ||
239 | 230 | ||
240 | #[derive(Clone, Debug)] | 231 | pub(super) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty { |
241 | pub(crate) struct InferenceTable { | 232 | let var = self.new_type_var(); |
242 | pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, | 233 | let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() }; |
243 | pub(super) type_variable_table: TypeVariableTable, | 234 | let obligation = alias_eq.cast(&Interner); |
244 | pub(super) revision: u32, | 235 | self.register_obligation(obligation); |
245 | } | 236 | var |
237 | } | ||
246 | 238 | ||
247 | impl InferenceTable { | 239 | fn extend_type_variable_table(&mut self, to_index: usize) { |
248 | pub(crate) fn new() -> Self { | 240 | self.type_variable_table.extend( |
249 | InferenceTable { | 241 | (0..1 + to_index - self.type_variable_table.len()) |
250 | var_unification_table: InPlaceUnificationTable::new(), | 242 | .map(|_| TypeVariableData { diverging: false }), |
251 | type_variable_table: TypeVariableTable { inner: Vec::new() }, | 243 | ); |
252 | revision: 0, | ||
253 | } | ||
254 | } | 244 | } |
255 | 245 | ||
256 | fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { | 246 | fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { |
257 | self.type_variable_table.push(TypeVariableData { diverging }); | 247 | let var = self.var_unification_table.new_variable(UniverseIndex::ROOT); |
258 | let key = self.var_unification_table.new_key(TypeVarValue::Unknown); | 248 | // Chalk might have created some type variables for its own purposes that we don't know about... |
259 | assert_eq!(key.0 as usize, self.type_variable_table.inner.len() - 1); | 249 | self.extend_type_variable_table(var.index() as usize); |
260 | TyKind::InferenceVar(to_inference_var(key), kind).intern(&Interner) | 250 | assert_eq!(var.index() as usize, self.type_variable_table.len() - 1); |
251 | self.type_variable_table[var.index() as usize].diverging = diverging; | ||
252 | var.to_ty_with_kind(&Interner, kind) | ||
261 | } | 253 | } |
262 | 254 | ||
263 | pub(crate) fn new_type_var(&mut self) -> Ty { | 255 | pub(crate) fn new_type_var(&mut self) -> Ty { |
@@ -276,350 +268,261 @@ impl InferenceTable { | |||
276 | self.new_var(TyVariableKind::General, true) | 268 | self.new_var(TyVariableKind::General, true) |
277 | } | 269 | } |
278 | 270 | ||
279 | pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { | 271 | pub(crate) fn resolve_with_fallback<T>( |
280 | self.resolve_ty_completely_inner(&mut Vec::new(), ty) | 272 | &mut self, |
273 | t: T, | ||
274 | fallback: impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, | ||
275 | ) -> T::Result | ||
276 | where | ||
277 | T: HasInterner<Interner = Interner> + Fold<Interner>, | ||
278 | { | ||
279 | self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback) | ||
281 | } | 280 | } |
282 | 281 | ||
283 | pub(crate) fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { | 282 | fn resolve_with_fallback_inner<T>( |
284 | self.resolve_ty_as_possible_inner(&mut Vec::new(), ty) | 283 | &mut self, |
284 | var_stack: &mut Vec<InferenceVar>, | ||
285 | t: T, | ||
286 | fallback: &impl Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg, | ||
287 | ) -> T::Result | ||
288 | where | ||
289 | T: HasInterner<Interner = Interner> + Fold<Interner>, | ||
290 | { | ||
291 | t.fold_with( | ||
292 | &mut resolve::Resolver { table: self, var_stack, fallback }, | ||
293 | DebruijnIndex::INNERMOST, | ||
294 | ) | ||
295 | .expect("fold failed unexpectedly") | ||
285 | } | 296 | } |
286 | 297 | ||
287 | pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | 298 | pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { |
288 | self.unify_inner(ty1, ty2, 0) | 299 | self.resolve_with_fallback(ty, |_, _, d, _| d) |
289 | } | 300 | } |
290 | 301 | ||
291 | pub(crate) fn unify_substs( | 302 | /// Unify two types and register new trait goals that arise from that. |
292 | &mut self, | 303 | pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { |
293 | substs1: &Substitution, | 304 | let result = if let Ok(r) = self.try_unify(ty1, ty2) { |
294 | substs2: &Substitution, | 305 | r |
295 | depth: usize, | 306 | } else { |
296 | ) -> bool { | 307 | return false; |
297 | substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| { | 308 | }; |
298 | self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth) | 309 | self.register_infer_ok(result); |
299 | }) | 310 | true |
300 | } | 311 | } |
301 | 312 | ||
302 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | 313 | /// Unify two types and return new trait goals arising from it, so the |
303 | if depth > 1000 { | 314 | /// caller needs to deal with them. |
304 | // prevent stackoverflows | 315 | pub(crate) fn try_unify<T: Zip<Interner>>(&mut self, t1: &T, t2: &T) -> InferResult { |
305 | panic!("infinite recursion in unification"); | 316 | match self.var_unification_table.relate( |
306 | } | 317 | &Interner, |
307 | if ty1 == ty2 { | 318 | &self.db, |
308 | return true; | 319 | &self.trait_env.env, |
309 | } | 320 | chalk_ir::Variance::Invariant, |
310 | // try to resolve type vars first | 321 | t1, |
311 | let ty1 = self.resolve_ty_shallow(ty1); | 322 | t2, |
312 | let ty2 = self.resolve_ty_shallow(ty2); | 323 | ) { |
313 | if ty1.equals_ctor(&ty2) { | 324 | Ok(result) => Ok(InferOk { goals: result.goals }), |
314 | match (ty1.kind(&Interner), ty2.kind(&Interner)) { | 325 | Err(chalk_ir::NoSolution) => Err(TypeError), |
315 | (TyKind::Adt(_, substs1), TyKind::Adt(_, substs2)) | ||
316 | | (TyKind::FnDef(_, substs1), TyKind::FnDef(_, substs2)) | ||
317 | | ( | ||
318 | TyKind::Function(FnPointer { substitution: FnSubst(substs1), .. }), | ||
319 | TyKind::Function(FnPointer { substitution: FnSubst(substs2), .. }), | ||
320 | ) | ||
321 | | (TyKind::Tuple(_, substs1), TyKind::Tuple(_, substs2)) | ||
322 | | (TyKind::OpaqueType(_, substs1), TyKind::OpaqueType(_, substs2)) | ||
323 | | (TyKind::AssociatedType(_, substs1), TyKind::AssociatedType(_, substs2)) | ||
324 | | (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) => { | ||
325 | self.unify_substs(substs1, substs2, depth + 1) | ||
326 | } | ||
327 | (TyKind::Array(ty1, c1), TyKind::Array(ty2, c2)) if c1 == c2 => { | ||
328 | self.unify_inner(ty1, ty2, depth + 1) | ||
329 | } | ||
330 | (TyKind::Ref(_, _, ty1), TyKind::Ref(_, _, ty2)) | ||
331 | | (TyKind::Raw(_, ty1), TyKind::Raw(_, ty2)) | ||
332 | | (TyKind::Slice(ty1), TyKind::Slice(ty2)) => self.unify_inner(ty1, ty2, depth + 1), | ||
333 | _ => true, /* we checked equals_ctor already */ | ||
334 | } | ||
335 | } else if let (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) = | ||
336 | (ty1.kind(&Interner), ty2.kind(&Interner)) | ||
337 | { | ||
338 | self.unify_substs(substs1, substs2, depth + 1) | ||
339 | } else { | ||
340 | self.unify_inner_trivial(&ty1, &ty2, depth) | ||
341 | } | 326 | } |
342 | } | 327 | } |
343 | 328 | ||
344 | pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | 329 | /// If `ty` is a type variable with known type, returns that type; |
345 | match (ty1.kind(&Interner), ty2.kind(&Interner)) { | 330 | /// otherwise, return ty. |
346 | (TyKind::Error, _) | (_, TyKind::Error) => true, | 331 | pub(crate) fn resolve_ty_shallow(&mut self, ty: &Ty) -> Ty { |
332 | self.var_unification_table.normalize_ty_shallow(&Interner, ty).unwrap_or_else(|| ty.clone()) | ||
333 | } | ||
347 | 334 | ||
348 | (TyKind::Placeholder(p1), TyKind::Placeholder(p2)) if *p1 == *p2 => true, | 335 | pub(crate) fn register_obligation(&mut self, goal: Goal) { |
336 | let in_env = InEnvironment::new(&self.trait_env.env, goal); | ||
337 | self.register_obligation_in_env(in_env) | ||
338 | } | ||
349 | 339 | ||
350 | (TyKind::Dyn(dyn1), TyKind::Dyn(dyn2)) | 340 | fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) { |
351 | if dyn1.bounds.skip_binders().interned().len() | 341 | let canonicalized = self.canonicalize(goal); |
352 | == dyn2.bounds.skip_binders().interned().len() => | 342 | if !self.try_resolve_obligation(&canonicalized) { |
353 | { | 343 | self.pending_obligations.push(canonicalized); |
354 | for (pred1, pred2) in dyn1 | 344 | } |
355 | .bounds | 345 | } |
356 | .skip_binders() | ||
357 | .interned() | ||
358 | .iter() | ||
359 | .zip(dyn2.bounds.skip_binders().interned().iter()) | ||
360 | { | ||
361 | if !self.unify_preds(pred1.skip_binders(), pred2.skip_binders(), depth + 1) { | ||
362 | return false; | ||
363 | } | ||
364 | } | ||
365 | true | ||
366 | } | ||
367 | 346 | ||
368 | ( | 347 | pub(crate) fn register_infer_ok(&mut self, infer_ok: InferOk) { |
369 | TyKind::InferenceVar(tv1, TyVariableKind::General), | 348 | infer_ok.goals.into_iter().for_each(|goal| self.register_obligation_in_env(goal)); |
370 | TyKind::InferenceVar(tv2, TyVariableKind::General), | 349 | } |
371 | ) | ||
372 | | ( | ||
373 | TyKind::InferenceVar(tv1, TyVariableKind::Integer), | ||
374 | TyKind::InferenceVar(tv2, TyVariableKind::Integer), | ||
375 | ) | ||
376 | | ( | ||
377 | TyKind::InferenceVar(tv1, TyVariableKind::Float), | ||
378 | TyKind::InferenceVar(tv2, TyVariableKind::Float), | ||
379 | ) if self.type_variable_table.is_diverging(*tv1) | ||
380 | == self.type_variable_table.is_diverging(*tv2) => | ||
381 | { | ||
382 | // both type vars are unknown since we tried to resolve them | ||
383 | if !self | ||
384 | .var_unification_table | ||
385 | .unioned(from_inference_var(*tv1), from_inference_var(*tv2)) | ||
386 | { | ||
387 | self.var_unification_table | ||
388 | .union(from_inference_var(*tv1), from_inference_var(*tv2)); | ||
389 | self.revision += 1; | ||
390 | } | ||
391 | true | ||
392 | } | ||
393 | 350 | ||
394 | // The order of MaybeNeverTypeVar matters here. | 351 | pub(crate) fn resolve_obligations_as_possible(&mut self) { |
395 | // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar. | 352 | let _span = profile::span("resolve_obligations_as_possible"); |
396 | // Unifying MaybeNeverTypeVar and other concrete type will let the former become it. | 353 | let mut changed = true; |
397 | (TyKind::InferenceVar(tv, TyVariableKind::General), other) | 354 | let mut obligations = Vec::new(); |
398 | | (other, TyKind::InferenceVar(tv, TyVariableKind::General)) | 355 | while changed { |
399 | | ( | 356 | changed = false; |
400 | TyKind::InferenceVar(tv, TyVariableKind::Integer), | 357 | mem::swap(&mut self.pending_obligations, &mut obligations); |
401 | other @ TyKind::Scalar(Scalar::Int(_)), | 358 | for canonicalized in obligations.drain(..) { |
402 | ) | 359 | if !self.check_changed(&canonicalized) { |
403 | | ( | 360 | self.pending_obligations.push(canonicalized); |
404 | other @ TyKind::Scalar(Scalar::Int(_)), | 361 | continue; |
405 | TyKind::InferenceVar(tv, TyVariableKind::Integer), | 362 | } |
406 | ) | 363 | changed = true; |
407 | | ( | 364 | let uncanonical = chalk_ir::Substitute::apply( |
408 | TyKind::InferenceVar(tv, TyVariableKind::Integer), | 365 | &canonicalized.free_vars, |
409 | other @ TyKind::Scalar(Scalar::Uint(_)), | 366 | canonicalized.value.value, |
410 | ) | 367 | &Interner, |
411 | | ( | ||
412 | other @ TyKind::Scalar(Scalar::Uint(_)), | ||
413 | TyKind::InferenceVar(tv, TyVariableKind::Integer), | ||
414 | ) | ||
415 | | ( | ||
416 | TyKind::InferenceVar(tv, TyVariableKind::Float), | ||
417 | other @ TyKind::Scalar(Scalar::Float(_)), | ||
418 | ) | ||
419 | | ( | ||
420 | other @ TyKind::Scalar(Scalar::Float(_)), | ||
421 | TyKind::InferenceVar(tv, TyVariableKind::Float), | ||
422 | ) => { | ||
423 | // the type var is unknown since we tried to resolve it | ||
424 | self.var_unification_table.union_value( | ||
425 | from_inference_var(*tv), | ||
426 | TypeVarValue::Known(other.clone().intern(&Interner)), | ||
427 | ); | 368 | ); |
428 | self.revision += 1; | 369 | self.register_obligation_in_env(uncanonical); |
429 | true | ||
430 | } | 370 | } |
431 | |||
432 | _ => false, | ||
433 | } | 371 | } |
434 | } | 372 | } |
435 | 373 | ||
436 | fn unify_preds(&mut self, pred1: &WhereClause, pred2: &WhereClause, depth: usize) -> bool { | 374 | /// This checks whether any of the free variables in the `canonicalized` |
437 | match (pred1, pred2) { | 375 | /// have changed (either been unified with another variable, or with a |
438 | (WhereClause::Implemented(tr1), WhereClause::Implemented(tr2)) | 376 | /// value). If this is not the case, we don't need to try to solve the goal |
439 | if tr1.trait_id == tr2.trait_id => | 377 | /// again -- it'll give the same result as last time. |
440 | { | 378 | fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool { |
441 | self.unify_substs(&tr1.substitution, &tr2.substitution, depth + 1) | 379 | canonicalized.free_vars.iter().any(|var| { |
380 | let iv = match var.data(&Interner) { | ||
381 | chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner), | ||
382 | chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner), | ||
383 | chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner), | ||
442 | } | 384 | } |
443 | ( | 385 | .expect("free var is not inference var"); |
444 | WhereClause::AliasEq(AliasEq { alias: alias1, ty: ty1 }), | 386 | if self.var_unification_table.probe_var(iv).is_some() { |
445 | WhereClause::AliasEq(AliasEq { alias: alias2, ty: ty2 }), | 387 | return true; |
446 | ) => { | ||
447 | let (substitution1, substitution2) = match (alias1, alias2) { | ||
448 | (AliasTy::Projection(projection_ty1), AliasTy::Projection(projection_ty2)) | ||
449 | if projection_ty1.associated_ty_id == projection_ty2.associated_ty_id => | ||
450 | { | ||
451 | (&projection_ty1.substitution, &projection_ty2.substitution) | ||
452 | } | ||
453 | (AliasTy::Opaque(opaque1), AliasTy::Opaque(opaque2)) | ||
454 | if opaque1.opaque_ty_id == opaque2.opaque_ty_id => | ||
455 | { | ||
456 | (&opaque1.substitution, &opaque2.substitution) | ||
457 | } | ||
458 | _ => return false, | ||
459 | }; | ||
460 | self.unify_substs(&substitution1, &substitution2, depth + 1) | ||
461 | && self.unify_inner(&ty1, &ty2, depth + 1) | ||
462 | } | 388 | } |
463 | _ => false, | 389 | let root = self.var_unification_table.inference_var_root(iv); |
464 | } | 390 | iv != root |
391 | }) | ||
465 | } | 392 | } |
466 | 393 | ||
467 | /// If `ty` is a type variable with known type, returns that type; | 394 | fn try_resolve_obligation( |
468 | /// otherwise, return ty. | 395 | &mut self, |
469 | pub(crate) fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | 396 | canonicalized: &Canonicalized<InEnvironment<Goal>>, |
470 | let mut ty = Cow::Borrowed(ty); | 397 | ) -> bool { |
471 | // The type variable could resolve to a int/float variable. Hence try | 398 | let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value.clone()); |
472 | // resolving up to three times; each type of variable shouldn't occur | 399 | |
473 | // more than once | 400 | match solution { |
474 | for i in 0..3 { | 401 | Some(Solution::Unique(canonical_subst)) => { |
475 | if i > 0 { | 402 | canonicalized.apply_solution( |
476 | cov_mark::hit!(type_var_resolves_to_int_var); | 403 | self, |
404 | Canonical { | ||
405 | binders: canonical_subst.binders, | ||
406 | // FIXME: handle constraints | ||
407 | value: canonical_subst.value.subst, | ||
408 | }, | ||
409 | ); | ||
410 | true | ||
477 | } | 411 | } |
478 | match ty.kind(&Interner) { | 412 | Some(Solution::Ambig(Guidance::Definite(substs))) => { |
479 | TyKind::InferenceVar(tv, _) => { | 413 | canonicalized.apply_solution(self, substs); |
480 | let inner = from_inference_var(*tv); | 414 | false |
481 | match self.var_unification_table.inlined_probe_value(inner).known() { | 415 | } |
482 | Some(known_ty) => { | 416 | Some(_) => { |
483 | // The known_ty can't be a type var itself | 417 | // FIXME use this when trying to resolve everything at the end |
484 | ty = Cow::Owned(known_ty.clone()); | 418 | false |
485 | } | 419 | } |
486 | _ => return ty, | 420 | None => { |
487 | } | 421 | // FIXME obligation cannot be fulfilled => diagnostic |
488 | } | 422 | true |
489 | _ => return ty, | ||
490 | } | 423 | } |
491 | } | 424 | } |
492 | log::error!("Inference variable still not resolved: {:?}", ty); | ||
493 | ty | ||
494 | } | ||
495 | |||
496 | /// Resolves the type as far as currently possible, replacing type variables | ||
497 | /// by their known types. All types returned by the infer_* functions should | ||
498 | /// be resolved as far as possible, i.e. contain no type variables with | ||
499 | /// known type. | ||
500 | fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
501 | fold_tys( | ||
502 | ty, | ||
503 | |ty, _| match ty.kind(&Interner) { | ||
504 | &TyKind::InferenceVar(tv, kind) => { | ||
505 | let inner = from_inference_var(tv); | ||
506 | if tv_stack.contains(&inner) { | ||
507 | cov_mark::hit!(type_var_cycles_resolve_as_possible); | ||
508 | // recursive type | ||
509 | return self.type_variable_table.fallback_value(tv, kind); | ||
510 | } | ||
511 | if let Some(known_ty) = | ||
512 | self.var_unification_table.inlined_probe_value(inner).known() | ||
513 | { | ||
514 | // known_ty may contain other variables that are known by now | ||
515 | tv_stack.push(inner); | ||
516 | let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); | ||
517 | tv_stack.pop(); | ||
518 | result | ||
519 | } else { | ||
520 | ty | ||
521 | } | ||
522 | } | ||
523 | _ => ty, | ||
524 | }, | ||
525 | DebruijnIndex::INNERMOST, | ||
526 | ) | ||
527 | } | ||
528 | |||
529 | /// Resolves the type completely; type variables without known type are | ||
530 | /// replaced by TyKind::Unknown. | ||
531 | fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
532 | fold_tys( | ||
533 | ty, | ||
534 | |ty, _| match ty.kind(&Interner) { | ||
535 | &TyKind::InferenceVar(tv, kind) => { | ||
536 | let inner = from_inference_var(tv); | ||
537 | if tv_stack.contains(&inner) { | ||
538 | cov_mark::hit!(type_var_cycles_resolve_completely); | ||
539 | // recursive type | ||
540 | return self.type_variable_table.fallback_value(tv, kind); | ||
541 | } | ||
542 | if let Some(known_ty) = | ||
543 | self.var_unification_table.inlined_probe_value(inner).known() | ||
544 | { | ||
545 | // known_ty may contain other variables that are known by now | ||
546 | tv_stack.push(inner); | ||
547 | let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); | ||
548 | tv_stack.pop(); | ||
549 | result | ||
550 | } else { | ||
551 | self.type_variable_table.fallback_value(tv, kind) | ||
552 | } | ||
553 | } | ||
554 | _ => ty, | ||
555 | }, | ||
556 | DebruijnIndex::INNERMOST, | ||
557 | ) | ||
558 | } | 425 | } |
559 | } | 426 | } |
560 | 427 | ||
561 | /// The ID of a type variable. | 428 | impl<'a> fmt::Debug for InferenceTable<'a> { |
562 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | 429 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
563 | pub(super) struct TypeVarId(pub(super) u32); | 430 | f.debug_struct("InferenceTable").field("num_vars", &self.type_variable_table.len()).finish() |
564 | |||
565 | impl UnifyKey for TypeVarId { | ||
566 | type Value = TypeVarValue; | ||
567 | |||
568 | fn index(&self) -> u32 { | ||
569 | self.0 | ||
570 | } | ||
571 | |||
572 | fn from_index(i: u32) -> Self { | ||
573 | TypeVarId(i) | ||
574 | } | 431 | } |
575 | |||
576 | fn tag() -> &'static str { | ||
577 | "TypeVarId" | ||
578 | } | ||
579 | } | ||
580 | |||
581 | fn from_inference_var(var: InferenceVar) -> TypeVarId { | ||
582 | TypeVarId(var.index()) | ||
583 | } | ||
584 | |||
585 | fn to_inference_var(TypeVarId(index): TypeVarId) -> InferenceVar { | ||
586 | index.into() | ||
587 | } | ||
588 | |||
589 | /// The value of a type variable: either we already know the type, or we don't | ||
590 | /// know it yet. | ||
591 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
592 | pub(super) enum TypeVarValue { | ||
593 | Known(Ty), | ||
594 | Unknown, | ||
595 | } | 432 | } |
596 | 433 | ||
597 | impl TypeVarValue { | 434 | mod resolve { |
598 | fn known(&self) -> Option<&Ty> { | 435 | use super::InferenceTable; |
599 | match self { | 436 | use crate::{ |
600 | TypeVarValue::Known(ty) => Some(ty), | 437 | ConcreteConst, Const, ConstData, ConstValue, DebruijnIndex, GenericArg, InferenceVar, |
601 | TypeVarValue::Unknown => None, | 438 | Interner, Ty, TyVariableKind, VariableKind, |
439 | }; | ||
440 | use chalk_ir::{ | ||
441 | cast::Cast, | ||
442 | fold::{Fold, Folder}, | ||
443 | Fallible, | ||
444 | }; | ||
445 | use hir_def::type_ref::ConstScalar; | ||
446 | |||
447 | pub(super) struct Resolver<'a, 'b, F> { | ||
448 | pub(super) table: &'a mut InferenceTable<'b>, | ||
449 | pub(super) var_stack: &'a mut Vec<InferenceVar>, | ||
450 | pub(super) fallback: F, | ||
451 | } | ||
452 | impl<'a, 'b, 'i, F> Folder<'i, Interner> for Resolver<'a, 'b, F> | ||
453 | where | ||
454 | F: Fn(InferenceVar, VariableKind, GenericArg, DebruijnIndex) -> GenericArg + 'i, | ||
455 | { | ||
456 | fn as_dyn(&mut self) -> &mut dyn Folder<'i, Interner> { | ||
457 | self | ||
602 | } | 458 | } |
603 | } | ||
604 | } | ||
605 | |||
606 | impl UnifyValue for TypeVarValue { | ||
607 | type Error = NoError; | ||
608 | 459 | ||
609 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | 460 | fn interner(&self) -> &'i Interner { |
610 | match (value1, value2) { | 461 | &Interner |
611 | // We should never equate two type variables, both of which have | 462 | } |
612 | // known types. Instead, we recursively equate those types. | ||
613 | (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( | ||
614 | "equating two type variables, both of which have known types: {:?} and {:?}", | ||
615 | t1, t2 | ||
616 | ), | ||
617 | 463 | ||
618 | // If one side is known, prefer that one. | 464 | fn fold_inference_ty( |
619 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | 465 | &mut self, |
620 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | 466 | var: InferenceVar, |
467 | kind: TyVariableKind, | ||
468 | outer_binder: DebruijnIndex, | ||
469 | ) -> Fallible<Ty> { | ||
470 | let var = self.table.var_unification_table.inference_var_root(var); | ||
471 | if self.var_stack.contains(&var) { | ||
472 | // recursive type | ||
473 | let default = self.table.fallback_value(var, kind).cast(&Interner); | ||
474 | return Ok((self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) | ||
475 | .assert_ty_ref(&Interner) | ||
476 | .clone()); | ||
477 | } | ||
478 | let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) { | ||
479 | // known_ty may contain other variables that are known by now | ||
480 | self.var_stack.push(var); | ||
481 | let result = | ||
482 | known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly"); | ||
483 | self.var_stack.pop(); | ||
484 | result.assert_ty_ref(&Interner).clone() | ||
485 | } else { | ||
486 | let default = self.table.fallback_value(var, kind).cast(&Interner); | ||
487 | (self.fallback)(var, VariableKind::Ty(kind), default, outer_binder) | ||
488 | .assert_ty_ref(&Interner) | ||
489 | .clone() | ||
490 | }; | ||
491 | Ok(result) | ||
492 | } | ||
621 | 493 | ||
622 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | 494 | fn fold_inference_const( |
495 | &mut self, | ||
496 | ty: Ty, | ||
497 | var: InferenceVar, | ||
498 | outer_binder: DebruijnIndex, | ||
499 | ) -> Fallible<Const> { | ||
500 | let var = self.table.var_unification_table.inference_var_root(var); | ||
501 | let default = ConstData { | ||
502 | ty: ty.clone(), | ||
503 | value: ConstValue::Concrete(ConcreteConst { interned: ConstScalar::Unknown }), | ||
504 | } | ||
505 | .intern(&Interner) | ||
506 | .cast(&Interner); | ||
507 | if self.var_stack.contains(&var) { | ||
508 | // recursive | ||
509 | return Ok((self.fallback)(var, VariableKind::Const(ty), default, outer_binder) | ||
510 | .assert_const_ref(&Interner) | ||
511 | .clone()); | ||
512 | } | ||
513 | let result = if let Some(known_ty) = self.table.var_unification_table.probe_var(var) { | ||
514 | // known_ty may contain other variables that are known by now | ||
515 | self.var_stack.push(var); | ||
516 | let result = | ||
517 | known_ty.fold_with(self, outer_binder).expect("fold failed unexpectedly"); | ||
518 | self.var_stack.pop(); | ||
519 | result.assert_const_ref(&Interner).clone() | ||
520 | } else { | ||
521 | (self.fallback)(var, VariableKind::Const(ty), default, outer_binder) | ||
522 | .assert_const_ref(&Interner) | ||
523 | .clone() | ||
524 | }; | ||
525 | Ok(result) | ||
623 | } | 526 | } |
624 | } | 527 | } |
625 | } | 528 | } |