aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--crates/hir_ty/src/infer/unify.rs123
1 files changed, 78 insertions, 45 deletions
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index a635501b5..00066975f 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -4,7 +4,6 @@ use std::{borrow::Cow, fmt, sync::Arc};
4 4
5use chalk_ir::{ 5use chalk_ir::{
6 cast::Cast, fold::Fold, interner::HasInterner, FloatTy, IntTy, TyVariableKind, UniverseIndex, 6 cast::Cast, fold::Fold, interner::HasInterner, FloatTy, IntTy, TyVariableKind, UniverseIndex,
7 VariableKind,
8}; 7};
9use chalk_solve::infer::ParameterEnaVariableExt; 8use chalk_solve::infer::ParameterEnaVariableExt;
10use ena::unify::UnifyKey; 9use ena::unify::UnifyKey;
@@ -12,7 +11,7 @@ use ena::unify::UnifyKey;
12use super::{InferOk, InferResult, InferenceContext, TypeError}; 11use super::{InferOk, InferResult, InferenceContext, TypeError};
13use crate::{ 12use crate::{
14 db::HirDatabase, fold_tys, static_lifetime, BoundVar, Canonical, DebruijnIndex, GenericArg, 13 db::HirDatabase, fold_tys, static_lifetime, BoundVar, Canonical, DebruijnIndex, GenericArg,
15 InferenceVar, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyKind, 14 InferenceVar, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyKind, VariableKind,
16}; 15};
17 16
18impl<'a> InferenceContext<'a> { 17impl<'a> InferenceContext<'a> {
@@ -112,19 +111,28 @@ pub(crate) fn unify(
112 } 111 }
113 // default any type vars that weren't unified back to their original bound vars 112 // default any type vars that weren't unified back to their original bound vars
114 // (kind of hacky) 113 // (kind of hacky)
115 for (i, var) in vars.iter(&Interner).enumerate() { 114 let find_var = |iv| {
116 let var = var.assert_ty_ref(&Interner); 115 vars.iter(&Interner).position(|v| match v.interned() {
117 if &*table.resolve_ty_shallow(var) == var { 116 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
118 table.unify( 117 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
119 var, 118 chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
120 &TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, i)).intern(&Interner), 119 } == Some(iv))
121 ); 120 };
122 } 121 let fallback = |iv, kind, default| match kind {
123 } 122 chalk_ir::VariableKind::Ty(_ty_kind) => find_var(iv).map_or(default, |i| {
123 BoundVar::new(DebruijnIndex::INNERMOST, i).to_ty(&Interner).cast(&Interner)
124 }),
125 chalk_ir::VariableKind::Lifetime => find_var(iv).map_or(default, |i| {
126 BoundVar::new(DebruijnIndex::INNERMOST, i).to_lifetime(&Interner).cast(&Interner)
127 }),
128 chalk_ir::VariableKind::Const(ty) => find_var(iv).map_or(default, |i| {
129 BoundVar::new(DebruijnIndex::INNERMOST, i).to_const(&Interner, ty).cast(&Interner)
130 }),
131 };
124 Some(Substitution::from_iter( 132 Some(Substitution::from_iter(
125 &Interner, 133 &Interner,
126 vars.iter(&Interner) 134 vars.iter(&Interner)
127 .map(|v| table.resolve_ty_completely(v.assert_ty_ref(&Interner).clone())), 135 .map(|v| table.resolve_with_fallback(v.assert_ty_ref(&Interner).clone(), fallback)),
128 )) 136 ))
129} 137}
130 138
@@ -201,8 +209,65 @@ impl<'a> InferenceTable<'a> {
201 self.new_var(TyVariableKind::General, true) 209 self.new_var(TyVariableKind::General, true)
202 } 210 }
203 211
212 pub(crate) fn resolve_with_fallback<T>(
213 &mut self,
214 t: T,
215 fallback: impl Fn(InferenceVar, VariableKind, GenericArg) -> GenericArg,
216 ) -> T::Result
217 where
218 T: HasInterner<Interner = Interner> + Fold<Interner>,
219 {
220 self.resolve_with_fallback_inner(&mut Vec::new(), t, &fallback)
221 }
222
223 fn resolve_with_fallback_inner<T>(
224 &mut self,
225 var_stack: &mut Vec<InferenceVar>,
226 t: T,
227 fallback: &impl Fn(InferenceVar, VariableKind, GenericArg) -> GenericArg,
228 ) -> T::Result
229 where
230 T: HasInterner<Interner = Interner> + Fold<Interner>,
231 {
232 fold_tys(
233 t,
234 |ty, _| match ty.kind(&Interner) {
235 &TyKind::InferenceVar(tv, kind) => {
236 if var_stack.contains(&tv) {
237 cov_mark::hit!(type_var_cycles_resolve_as_possible);
238 // recursive type
239 let default =
240 self.type_variable_table.fallback_value(tv, kind).cast(&Interner);
241 return fallback(tv, VariableKind::Ty(kind), default)
242 .assert_ty_ref(&Interner)
243 .clone();
244 }
245 if let Some(known_ty) = self.var_unification_table.probe_var(tv) {
246 // known_ty may contain other variables that are known by now
247 var_stack.push(tv);
248 let result = self.resolve_with_fallback_inner(
249 var_stack,
250 known_ty.assert_ty_ref(&Interner).clone(),
251 fallback,
252 );
253 var_stack.pop();
254 result
255 } else {
256 let default =
257 self.type_variable_table.fallback_value(tv, kind).cast(&Interner);
258 fallback(tv, VariableKind::Ty(kind), default)
259 .assert_ty_ref(&Interner)
260 .clone()
261 }
262 }
263 _ => ty,
264 },
265 DebruijnIndex::INNERMOST,
266 )
267 }
268
204 pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty { 269 pub(crate) fn resolve_ty_completely(&mut self, ty: Ty) -> Ty {
205 self.resolve_ty_completely_inner(&mut Vec::new(), ty) 270 self.resolve_with_fallback(ty, |_, _, d| d)
206 } 271 }
207 272
208 // FIXME get rid of this, instead resolve shallowly where necessary 273 // FIXME get rid of this, instead resolve shallowly where necessary
@@ -282,38 +347,6 @@ impl<'a> InferenceTable<'a> {
282 DebruijnIndex::INNERMOST, 347 DebruijnIndex::INNERMOST,
283 ) 348 )
284 } 349 }
285
286 /// Resolves the type completely; type variables without known type are
287 /// replaced by TyKind::Unknown.
288 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<InferenceVar>, ty: Ty) -> Ty {
289 // FIXME implement as a proper Folder, handle lifetimes and consts as well
290 fold_tys(
291 ty,
292 |ty, _| match ty.kind(&Interner) {
293 &TyKind::InferenceVar(tv, kind) => {
294 if tv_stack.contains(&tv) {
295 cov_mark::hit!(type_var_cycles_resolve_completely);
296 // recursive type
297 return self.type_variable_table.fallback_value(tv, kind);
298 }
299 if let Some(known_ty) = self.var_unification_table.probe_var(tv) {
300 // known_ty may contain other variables that are known by now
301 tv_stack.push(tv);
302 let result = self.resolve_ty_completely_inner(
303 tv_stack,
304 known_ty.assert_ty_ref(&Interner).clone(),
305 );
306 tv_stack.pop();
307 result
308 } else {
309 self.type_variable_table.fallback_value(tv, kind)
310 }
311 }
312 _ => ty,
313 },
314 DebruijnIndex::INNERMOST,
315 )
316 }
317} 350}
318 351
319impl<'a> fmt::Debug for InferenceTable<'a> { 352impl<'a> fmt::Debug for InferenceTable<'a> {