aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty')
-rw-r--r--crates/hir_ty/src/chalk_db.rs15
-rw-r--r--crates/hir_ty/src/db.rs4
-rw-r--r--crates/hir_ty/src/infer.rs18
-rw-r--r--crates/hir_ty/src/infer/coerce.rs10
-rw-r--r--crates/hir_ty/src/infer/expr.rs12
-rw-r--r--crates/hir_ty/src/infer/path.rs2
-rw-r--r--crates/hir_ty/src/infer/unify.rs499
-rw-r--r--crates/hir_ty/src/method_resolution.rs3
8 files changed, 125 insertions, 438 deletions
diff --git a/crates/hir_ty/src/chalk_db.rs b/crates/hir_ty/src/chalk_db.rs
index 8f054d06b..b108fd559 100644
--- a/crates/hir_ty/src/chalk_db.rs
+++ b/crates/hir_ty/src/chalk_db.rs
@@ -344,20 +344,20 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
344 } 344 }
345 345
346 fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> { 346 fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> {
347 self 347 &self.db
348 } 348 }
349} 349}
350 350
351impl<'a> chalk_ir::UnificationDatabase<Interner> for ChalkContext<'a> { 351impl<'a> chalk_ir::UnificationDatabase<Interner> for &'a dyn HirDatabase {
352 fn fn_def_variance( 352 fn fn_def_variance(
353 &self, 353 &self,
354 fn_def_id: chalk_ir::FnDefId<Interner>, 354 fn_def_id: chalk_ir::FnDefId<Interner>,
355 ) -> chalk_ir::Variances<Interner> { 355 ) -> chalk_ir::Variances<Interner> {
356 self.db.fn_def_variance(self.krate, fn_def_id) 356 HirDatabase::fn_def_variance(*self, fn_def_id)
357 } 357 }
358 358
359 fn adt_variance(&self, adt_id: chalk_ir::AdtId<Interner>) -> chalk_ir::Variances<Interner> { 359 fn adt_variance(&self, adt_id: chalk_ir::AdtId<Interner>) -> chalk_ir::Variances<Interner> {
360 self.db.adt_variance(self.krate, adt_id) 360 HirDatabase::adt_variance(*self, adt_id)
361 } 361 }
362} 362}
363 363
@@ -651,11 +651,7 @@ pub(crate) fn fn_def_datum_query(
651 Arc::new(datum) 651 Arc::new(datum)
652} 652}
653 653
654pub(crate) fn fn_def_variance_query( 654pub(crate) fn fn_def_variance_query(db: &dyn HirDatabase, fn_def_id: FnDefId) -> Variances {
655 db: &dyn HirDatabase,
656 _krate: CrateId,
657 fn_def_id: FnDefId,
658) -> Variances {
659 let callable_def: CallableDefId = from_chalk(db, fn_def_id); 655 let callable_def: CallableDefId = from_chalk(db, fn_def_id);
660 let generic_params = generics(db.upcast(), callable_def.into()); 656 let generic_params = generics(db.upcast(), callable_def.into());
661 Variances::from_iter( 657 Variances::from_iter(
@@ -666,7 +662,6 @@ pub(crate) fn fn_def_variance_query(
666 662
667pub(crate) fn adt_variance_query( 663pub(crate) fn adt_variance_query(
668 db: &dyn HirDatabase, 664 db: &dyn HirDatabase,
669 _krate: CrateId,
670 chalk_ir::AdtId(adt_id): AdtId, 665 chalk_ir::AdtId(adt_id): AdtId,
671) -> Variances { 666) -> Variances {
672 let generic_params = generics(db.upcast(), adt_id.into()); 667 let generic_params = generics(db.upcast(), adt_id.into());
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 9da0a02e3..f773aa621 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -117,10 +117,10 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
117 fn fn_def_datum(&self, krate: CrateId, fn_def_id: FnDefId) -> Arc<chalk_db::FnDefDatum>; 117 fn fn_def_datum(&self, krate: CrateId, fn_def_id: FnDefId) -> Arc<chalk_db::FnDefDatum>;
118 118
119 #[salsa::invoke(chalk_db::fn_def_variance_query)] 119 #[salsa::invoke(chalk_db::fn_def_variance_query)]
120 fn fn_def_variance(&self, krate: CrateId, fn_def_id: FnDefId) -> chalk_db::Variances; 120 fn fn_def_variance(&self, fn_def_id: FnDefId) -> chalk_db::Variances;
121 121
122 #[salsa::invoke(chalk_db::adt_variance_query)] 122 #[salsa::invoke(chalk_db::adt_variance_query)]
123 fn adt_variance(&self, krate: CrateId, adt_id: chalk_db::AdtId) -> chalk_db::Variances; 123 fn adt_variance(&self, adt_id: chalk_db::AdtId) -> chalk_db::Variances;
124 124
125 #[salsa::invoke(chalk_db::associated_ty_value_query)] 125 #[salsa::invoke(chalk_db::associated_ty_value_query)]
126 fn associated_ty_value( 126 fn associated_ty_value(
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 0ee851a74..2a82f1b47 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -217,7 +217,7 @@ struct InferenceContext<'a> {
217 owner: DefWithBodyId, 217 owner: DefWithBodyId,
218 body: Arc<Body>, 218 body: Arc<Body>,
219 resolver: Resolver, 219 resolver: Resolver,
220 table: unify::InferenceTable, 220 table: unify::InferenceTable<'a>,
221 trait_env: Arc<TraitEnvironment>, 221 trait_env: Arc<TraitEnvironment>,
222 obligations: Vec<DomainGoal>, 222 obligations: Vec<DomainGoal>,
223 last_obligations_check: Option<u32>, 223 last_obligations_check: Option<u32>,
@@ -252,15 +252,15 @@ fn find_breakable<'c>(
252 252
253impl<'a> InferenceContext<'a> { 253impl<'a> InferenceContext<'a> {
254 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self { 254 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self {
255 let trait_env =
256 owner.as_generic_def_id().map_or_else(Default::default, |d| db.trait_environment(d));
255 InferenceContext { 257 InferenceContext {
256 result: InferenceResult::default(), 258 result: InferenceResult::default(),
257 table: unify::InferenceTable::new(), 259 table: unify::InferenceTable::new(db, trait_env.clone()),
258 obligations: Vec::default(), 260 obligations: Vec::default(),
259 last_obligations_check: None, 261 last_obligations_check: None,
260 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature 262 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature
261 trait_env: owner 263 trait_env,
262 .as_generic_def_id()
263 .map_or_else(Default::default, |d| db.trait_environment(d)),
264 db, 264 db,
265 owner, 265 owner,
266 body: db.body(owner), 266 body: db.body(owner),
@@ -346,17 +346,12 @@ impl<'a> InferenceContext<'a> {
346 } 346 }
347 347
348 fn resolve_obligations_as_possible(&mut self) { 348 fn resolve_obligations_as_possible(&mut self) {
349 if self.last_obligations_check == Some(self.table.revision) {
350 // no change
351 return;
352 }
353 let _span = profile::span("resolve_obligations_as_possible"); 349 let _span = profile::span("resolve_obligations_as_possible");
354 350
355 self.last_obligations_check = Some(self.table.revision);
356 let obligations = mem::replace(&mut self.obligations, Vec::new()); 351 let obligations = mem::replace(&mut self.obligations, Vec::new());
357 for obligation in obligations { 352 for obligation in obligations {
358 let in_env = InEnvironment::new(&self.trait_env.env, obligation.clone()); 353 let in_env = InEnvironment::new(&self.trait_env.env, obligation.clone());
359 let canonicalized = self.canonicalizer().canonicalize_obligation(in_env); 354 let canonicalized = self.canonicalize(in_env);
360 let solution = 355 let solution =
361 self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone()); 356 self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone());
362 357
@@ -395,6 +390,7 @@ impl<'a> InferenceContext<'a> {
395 self.table.unify(ty1, ty2) 390 self.table.unify(ty1, ty2)
396 } 391 }
397 392
393 // FIXME get rid of this, instead resolve shallowly where necessary
398 /// Resolves the type as far as currently possible, replacing type variables 394 /// Resolves the type as far as currently possible, replacing type variables
399 /// by their known types. All types returned by the infer_* functions should 395 /// by their known types. All types returned by the infer_* functions should
400 /// be resolved as far as possible, i.e. contain no type variables with 396 /// be resolved as far as possible, i.e. contain no type variables with
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index 1f463a425..ae858b1b0 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -7,7 +7,7 @@
7use chalk_ir::{cast::Cast, Mutability, TyVariableKind}; 7use chalk_ir::{cast::Cast, Mutability, TyVariableKind};
8use hir_def::lang_item::LangItemTarget; 8use hir_def::lang_item::LangItemTarget;
9 9
10use crate::{autoderef, Canonical, Interner, Solution, Ty, TyBuilder, TyExt, TyKind}; 10use crate::{autoderef, Canonical, DomainGoal, Interner, Solution, Ty, TyBuilder, TyExt, TyKind};
11 11
12use super::{InEnvironment, InferenceContext}; 12use super::{InEnvironment, InferenceContext};
13 13
@@ -141,10 +141,10 @@ impl<'a> InferenceContext<'a> {
141 b.push(from_ty.clone()).push(to_ty.clone()).build() 141 b.push(from_ty.clone()).push(to_ty.clone()).build()
142 }; 142 };
143 143
144 let goal = InEnvironment::new(&self.trait_env.env, trait_ref.cast(&Interner)); 144 let goal: InEnvironment<DomainGoal> =
145 InEnvironment::new(&self.trait_env.env, trait_ref.cast(&Interner));
145 146
146 let canonicalizer = self.canonicalizer(); 147 let canonicalized = self.canonicalize(goal);
147 let canonicalized = canonicalizer.canonicalize_obligation(goal);
148 148
149 let solution = self.db.trait_solve(krate, canonicalized.value.clone())?; 149 let solution = self.db.trait_solve(krate, canonicalized.value.clone())?;
150 150
@@ -169,7 +169,7 @@ impl<'a> InferenceContext<'a> {
169 /// 169 ///
170 /// Note that the parameters are already stripped the outer reference. 170 /// Note that the parameters are already stripped the outer reference.
171 fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool { 171 fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
172 let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone()); 172 let canonicalized = self.canonicalize(from_ty.clone());
173 let to_ty = self.resolve_ty_shallow(&to_ty); 173 let to_ty = self.resolve_ty_shallow(&to_ty);
174 // FIXME: Auto DerefMut 174 // FIXME: Auto DerefMut
175 for derefed_ty in autoderef::autoderef( 175 for derefed_ty in autoderef::autoderef(
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 7278faeec..aab4d3153 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -98,7 +98,7 @@ impl<'a> InferenceContext<'a> {
98 goal: projection.trait_ref(self.db).cast(&Interner), 98 goal: projection.trait_ref(self.db).cast(&Interner),
99 environment: trait_env, 99 environment: trait_env,
100 }; 100 };
101 let canonical = self.canonicalizer().canonicalize_obligation(obligation.clone()); 101 let canonical = self.canonicalize(obligation.clone());
102 if self.db.trait_solve(krate, canonical.value).is_some() { 102 if self.db.trait_solve(krate, canonical.value).is_some() {
103 self.push_obligation(obligation.goal); 103 self.push_obligation(obligation.goal);
104 let return_ty = self.normalize_projection_ty(projection); 104 let return_ty = self.normalize_projection_ty(projection);
@@ -297,7 +297,7 @@ impl<'a> InferenceContext<'a> {
297 } 297 }
298 Expr::Call { callee, args } => { 298 Expr::Call { callee, args } => {
299 let callee_ty = self.infer_expr(*callee, &Expectation::none()); 299 let callee_ty = self.infer_expr(*callee, &Expectation::none());
300 let canonicalized = self.canonicalizer().canonicalize_ty(callee_ty.clone()); 300 let canonicalized = self.canonicalize(callee_ty.clone());
301 let mut derefs = autoderef( 301 let mut derefs = autoderef(
302 self.db, 302 self.db,
303 self.resolver.krate(), 303 self.resolver.krate(),
@@ -442,7 +442,7 @@ impl<'a> InferenceContext<'a> {
442 } 442 }
443 Expr::Field { expr, name } => { 443 Expr::Field { expr, name } => {
444 let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none()); 444 let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none());
445 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty); 445 let canonicalized = self.canonicalize(receiver_ty);
446 let ty = autoderef::autoderef( 446 let ty = autoderef::autoderef(
447 self.db, 447 self.db,
448 self.resolver.krate(), 448 self.resolver.krate(),
@@ -559,7 +559,7 @@ impl<'a> InferenceContext<'a> {
559 match op { 559 match op {
560 UnaryOp::Deref => match self.resolver.krate() { 560 UnaryOp::Deref => match self.resolver.krate() {
561 Some(krate) => { 561 Some(krate) => {
562 let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty); 562 let canonicalized = self.canonicalize(inner_ty);
563 match autoderef::deref( 563 match autoderef::deref(
564 self.db, 564 self.db,
565 krate, 565 krate,
@@ -676,7 +676,7 @@ impl<'a> InferenceContext<'a> {
676 if let (Some(index_trait), Some(krate)) = 676 if let (Some(index_trait), Some(krate)) =
677 (self.resolve_ops_index(), self.resolver.krate()) 677 (self.resolve_ops_index(), self.resolver.krate())
678 { 678 {
679 let canonicalized = self.canonicalizer().canonicalize_ty(base_ty); 679 let canonicalized = self.canonicalize(base_ty);
680 let self_ty = method_resolution::resolve_indexing_op( 680 let self_ty = method_resolution::resolve_indexing_op(
681 self.db, 681 self.db,
682 &canonicalized.value, 682 &canonicalized.value,
@@ -852,7 +852,7 @@ impl<'a> InferenceContext<'a> {
852 generic_args: Option<&GenericArgs>, 852 generic_args: Option<&GenericArgs>,
853 ) -> Ty { 853 ) -> Ty {
854 let receiver_ty = self.infer_expr(receiver, &Expectation::none()); 854 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
855 let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone()); 855 let canonicalized_receiver = self.canonicalize(receiver_ty.clone());
856 856
857 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast()); 857 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast());
858 858
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 495282eba..bc64b612b 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -218,7 +218,7 @@ impl<'a> InferenceContext<'a> {
218 return Some(result); 218 return Some(result);
219 } 219 }
220 220
221 let canonical_ty = self.canonicalizer().canonicalize_ty(ty.clone()); 221 let canonical_ty = self.canonicalize(ty.clone());
222 let krate = self.resolver.krate()?; 222 let krate = self.resolver.krate()?;
223 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast()); 223 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast());
224 224
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index d8e0b4320..9b28c76d6 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -1,133 +1,52 @@
1//! Unification and canonicalization logic. 1//! Unification and canonicalization logic.
2 2
3use std::borrow::Cow; 3use 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, 7 VariableKind,
8}; 8};
9use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; 9use chalk_solve::infer::ParameterEnaVariableExt;
10use ena::unify::UnifyKey;
10 11
11use super::{DomainGoal, InferenceContext}; 12use super::InferenceContext;
12use crate::{ 13use crate::{
13 fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical, CanonicalVarKinds, 14 db::HirDatabase, fold_tys, static_lifetime, BoundVar, Canonical, DebruijnIndex, GenericArg,
14 DebruijnIndex, FnPointer, FnSubst, InEnvironment, InferenceVar, Interner, Scalar, Substitution, 15 InferenceVar, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyKind,
15 Ty, TyExt, TyKind, WhereClause,
16}; 16};
17 17
18impl<'a> InferenceContext<'a> { 18impl<'a> InferenceContext<'a> {
19 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b> 19 pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
20 &mut self,
21 t: T,
22 ) -> Canonicalized<T::Result>
20 where 23 where
21 'a: 'b, 24 T::Result: HasInterner<Interner = Interner>,
22 { 25 {
23 Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() } 26 let result = self.table.var_unification_table.canonicalize(&Interner, t);
27 let free_vars = result
28 .free_vars
29 .into_iter()
30 .map(|free_var| free_var.to_generic_arg(&Interner))
31 .collect();
32 Canonicalized { value: result.quantified, free_vars }
24 } 33 }
25} 34}
26 35
27pub(super) struct Canonicalizer<'a, 'b>
28where
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)] 36#[derive(Debug)]
40pub(super) struct Canonicalized<T> 37pub(super) struct Canonicalized<T>
41where 38where
42 T: HasInterner<Interner = Interner>, 39 T: HasInterner<Interner = Interner>,
43{ 40{
44 pub(super) value: Canonical<T>, 41 pub(super) value: Canonical<T>,
45 free_vars: Vec<(InferenceVar, TyVariableKind)>, 42 free_vars: Vec<GenericArg>,
46}
47
48impl<'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} 43}
125 44
126impl<T: HasInterner<Interner = Interner>> Canonicalized<T> { 45impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
127 pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty { 46 pub(super) fn decanonicalize_ty(&self, ty: Ty) -> Ty {
128 crate::fold_free_vars(ty, |bound, _binders| { 47 crate::fold_free_vars(ty, |bound, _binders| {
129 let (v, k) = self.free_vars[bound.index]; 48 let var = self.free_vars[bound.index];
130 TyKind::InferenceVar(v, k).intern(&Interner) 49 var.assert_ty_ref(&Interner).clone()
131 }) 50 })
132 } 51 }
133 52
@@ -155,23 +74,29 @@ impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
155 }), 74 }),
156 ); 75 );
157 for (i, ty) in solution.value.iter(&Interner).enumerate() { 76 for (i, ty) in solution.value.iter(&Interner).enumerate() {
158 let (v, k) = self.free_vars[i]; 77 // FIXME: deal with non-type vars here -- the only problematic part is the normalization
78 // and maybe we don't need that with lazy normalization?
79 let var = self.free_vars[i];
159 // eagerly replace projections in the type; we may be getting types 80 // eagerly replace projections in the type; we may be getting types
160 // e.g. from where clauses where this hasn't happened yet 81 // e.g. from where clauses where this hasn't happened yet
161 let ty = ctx.normalize_associated_types_in( 82 let ty = ctx.normalize_associated_types_in(
162 new_vars.apply(ty.assert_ty_ref(&Interner).clone(), &Interner), 83 new_vars.apply(ty.assert_ty_ref(&Interner).clone(), &Interner),
163 ); 84 );
164 ctx.table.unify(&TyKind::InferenceVar(v, k).intern(&Interner), &ty); 85 ctx.table.unify(var.assert_ty_ref(&Interner), &ty);
165 } 86 }
166 } 87 }
167} 88}
168 89
169pub fn could_unify(t1: &Ty, t2: &Ty) -> bool { 90pub fn could_unify(db: &dyn HirDatabase, env: Arc<TraitEnvironment>, t1: &Ty, t2: &Ty) -> bool {
170 InferenceTable::new().unify(t1, t2) 91 InferenceTable::new(db, env).unify(t1, t2)
171} 92}
172 93
173pub(crate) fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substitution> { 94pub(crate) fn unify(
174 let mut table = InferenceTable::new(); 95 db: &dyn HirDatabase,
96 env: Arc<TraitEnvironment>,
97 tys: &Canonical<(Ty, Ty)>,
98) -> Option<Substitution> {
99 let mut table = InferenceTable::new(db, env);
175 let vars = Substitution::from_iter( 100 let vars = Substitution::from_iter(
176 &Interner, 101 &Interner,
177 tys.binders 102 tys.binders
@@ -214,16 +139,16 @@ impl TypeVariableTable {
214 } 139 }
215 140
216 pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) { 141 pub(super) fn set_diverging(&mut self, iv: InferenceVar, diverging: bool) {
217 self.inner[from_inference_var(iv).0 as usize].diverging = diverging; 142 self.inner[iv.index() as usize].diverging = diverging;
218 } 143 }
219 144
220 fn is_diverging(&mut self, iv: InferenceVar) -> bool { 145 fn is_diverging(&mut self, iv: InferenceVar) -> bool {
221 self.inner[from_inference_var(iv).0 as usize].diverging 146 self.inner[iv.index() as usize].diverging
222 } 147 }
223 148
224 fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty { 149 fn fallback_value(&self, iv: InferenceVar, kind: TyVariableKind) -> Ty {
225 match kind { 150 match kind {
226 _ if self.inner[from_inference_var(iv).0 as usize].diverging => TyKind::Never, 151 _ if self.inner[iv.index() as usize].diverging => TyKind::Never,
227 TyVariableKind::General => TyKind::Error, 152 TyVariableKind::General => TyKind::Error,
228 TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)), 153 TyVariableKind::Integer => TyKind::Scalar(Scalar::Int(IntTy::I32)),
229 TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)), 154 TyVariableKind::Float => TyKind::Scalar(Scalar::Float(FloatTy::F64)),
@@ -237,27 +162,35 @@ pub(crate) struct TypeVariableData {
237 diverging: bool, 162 diverging: bool,
238} 163}
239 164
240#[derive(Clone, Debug)] 165type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
241pub(crate) struct InferenceTable { 166
242 pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>, 167#[derive(Clone)]
168pub(crate) struct InferenceTable<'a> {
169 db: &'a dyn HirDatabase,
170 trait_env: Arc<TraitEnvironment>,
171 pub(super) var_unification_table: ChalkInferenceTable,
243 pub(super) type_variable_table: TypeVariableTable, 172 pub(super) type_variable_table: TypeVariableTable,
244 pub(super) revision: u32,
245} 173}
246 174
247impl InferenceTable { 175impl<'a> InferenceTable<'a> {
248 pub(crate) fn new() -> Self { 176 pub(crate) fn new(db: &'a dyn HirDatabase, trait_env: Arc<TraitEnvironment>) -> Self {
249 InferenceTable { 177 InferenceTable {
250 var_unification_table: InPlaceUnificationTable::new(), 178 db,
179 trait_env,
180 var_unification_table: ChalkInferenceTable::new(),
251 type_variable_table: TypeVariableTable { inner: Vec::new() }, 181 type_variable_table: TypeVariableTable { inner: Vec::new() },
252 revision: 0,
253 } 182 }
254 } 183 }
255 184
256 fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { 185 fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
257 self.type_variable_table.push(TypeVariableData { diverging }); 186 let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
258 let key = self.var_unification_table.new_key(TypeVarValue::Unknown); 187 self.type_variable_table.inner.extend(
259 assert_eq!(key.0 as usize, self.type_variable_table.inner.len() - 1); 188 (0..1 + var.index() as usize - self.type_variable_table.inner.len())
260 TyKind::InferenceVar(to_inference_var(key), kind).intern(&Interner) 189 .map(|_| TypeVariableData { diverging: false }),
190 );
191 assert_eq!(var.index() as usize, self.type_variable_table.inner.len() - 1);
192 self.type_variable_table.inner[var.index() as usize].diverging = diverging;
193 var.to_ty_with_kind(&Interner, kind)
261 } 194 }
262 195
263 pub(crate) fn new_type_var(&mut self) -> Ty { 196 pub(crate) fn new_type_var(&mut self) -> Ty {
@@ -280,240 +213,59 @@ impl InferenceTable {
280 self.resolve_ty_completely_inner(&mut Vec::new(), ty) 213 self.resolve_ty_completely_inner(&mut Vec::new(), ty)
281 } 214 }
282 215
216 // FIXME get rid of this, instead resolve shallowly where necessary
283 pub(crate) fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty { 217 pub(crate) fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
284 self.resolve_ty_as_possible_inner(&mut Vec::new(), ty) 218 self.resolve_ty_as_possible_inner(&mut Vec::new(), ty)
285 } 219 }
286 220
287 pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { 221 pub(crate) fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
288 self.unify_inner(ty1, ty2, 0) 222 let result = self.var_unification_table.relate(
289 } 223 &Interner,
290 224 &self.db,
291 pub(crate) fn unify_substs( 225 &self.trait_env.env,
292 &mut self, 226 chalk_ir::Variance::Invariant,
293 substs1: &Substitution, 227 ty1,
294 substs2: &Substitution, 228 ty2,
295 depth: usize, 229 );
296 ) -> bool { 230 let result = if let Ok(r) = result {
297 substs1.iter(&Interner).zip(substs2.iter(&Interner)).all(|(t1, t2)| { 231 r
298 self.unify_inner(t1.assert_ty_ref(&Interner), t2.assert_ty_ref(&Interner), depth)
299 })
300 }
301
302 fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
303 if depth > 1000 {
304 // prevent stackoverflows
305 panic!("infinite recursion in unification");
306 }
307 if ty1 == ty2 {
308 return true;
309 }
310 // try to resolve type vars first
311 let ty1 = self.resolve_ty_shallow(ty1);
312 let ty2 = self.resolve_ty_shallow(ty2);
313 if ty1.equals_ctor(&ty2) {
314 match (ty1.kind(&Interner), ty2.kind(&Interner)) {
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 { 232 } else {
340 self.unify_inner_trivial(&ty1, &ty2, depth) 233 return false;
341 } 234 };
342 } 235 // TODO deal with new goals
343 236 true
344 pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
345 match (ty1.kind(&Interner), ty2.kind(&Interner)) {
346 (TyKind::Error, _) | (_, TyKind::Error) => true,
347
348 (TyKind::Placeholder(p1), TyKind::Placeholder(p2)) if *p1 == *p2 => true,
349
350 (TyKind::Dyn(dyn1), TyKind::Dyn(dyn2))
351 if dyn1.bounds.skip_binders().interned().len()
352 == dyn2.bounds.skip_binders().interned().len() =>
353 {
354 for (pred1, pred2) in dyn1
355 .bounds
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
368 (
369 TyKind::InferenceVar(tv1, TyVariableKind::General),
370 TyKind::InferenceVar(tv2, TyVariableKind::General),
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
394 // The order of MaybeNeverTypeVar matters here.
395 // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
396 // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
397 (TyKind::InferenceVar(tv, TyVariableKind::General), other)
398 | (other, TyKind::InferenceVar(tv, TyVariableKind::General))
399 | (
400 TyKind::InferenceVar(tv, TyVariableKind::Integer),
401 other @ TyKind::Scalar(Scalar::Int(_)),
402 )
403 | (
404 other @ TyKind::Scalar(Scalar::Int(_)),
405 TyKind::InferenceVar(tv, TyVariableKind::Integer),
406 )
407 | (
408 TyKind::InferenceVar(tv, TyVariableKind::Integer),
409 other @ TyKind::Scalar(Scalar::Uint(_)),
410 )
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 );
428 self.revision += 1;
429 true
430 }
431
432 _ => false,
433 }
434 }
435
436 fn unify_preds(&mut self, pred1: &WhereClause, pred2: &WhereClause, depth: usize) -> bool {
437 match (pred1, pred2) {
438 (WhereClause::Implemented(tr1), WhereClause::Implemented(tr2))
439 if tr1.trait_id == tr2.trait_id =>
440 {
441 self.unify_substs(&tr1.substitution, &tr2.substitution, depth + 1)
442 }
443 (
444 WhereClause::AliasEq(AliasEq { alias: alias1, ty: ty1 }),
445 WhereClause::AliasEq(AliasEq { alias: alias2, ty: ty2 }),
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 }
463 _ => false,
464 }
465 } 237 }
466 238
467 /// If `ty` is a type variable with known type, returns that type; 239 /// If `ty` is a type variable with known type, returns that type;
468 /// otherwise, return ty. 240 /// otherwise, return ty.
241 // FIXME this could probably just return Ty
469 pub(crate) fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { 242 pub(crate) fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
470 let mut ty = Cow::Borrowed(ty); 243 self.var_unification_table
471 // The type variable could resolve to a int/float variable. Hence try 244 .normalize_ty_shallow(&Interner, ty)
472 // resolving up to three times; each type of variable shouldn't occur 245 .map_or(Cow::Borrowed(ty), Cow::Owned)
473 // more than once
474 for i in 0..3 {
475 if i > 0 {
476 cov_mark::hit!(type_var_resolves_to_int_var);
477 }
478 match ty.kind(&Interner) {
479 TyKind::InferenceVar(tv, _) => {
480 let inner = from_inference_var(*tv);
481 match self.var_unification_table.inlined_probe_value(inner).known() {
482 Some(known_ty) => {
483 // The known_ty can't be a type var itself
484 ty = Cow::Owned(known_ty.clone());
485 }
486 _ => return ty,
487 }
488 }
489 _ => return ty,
490 }
491 }
492 log::error!("Inference variable still not resolved: {:?}", ty);
493 ty
494 } 246 }
495 247
496 /// Resolves the type as far as currently possible, replacing type variables 248 /// Resolves the type as far as currently possible, replacing type variables
497 /// by their known types. All types returned by the infer_* functions should 249 /// 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 250 /// be resolved as far as possible, i.e. contain no type variables with
499 /// known type. 251 /// known type.
500 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 252 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<InferenceVar>, ty: Ty) -> Ty {
501 fold_tys( 253 fold_tys(
502 ty, 254 ty,
503 |ty, _| match ty.kind(&Interner) { 255 |ty, _| match ty.kind(&Interner) {
504 &TyKind::InferenceVar(tv, kind) => { 256 &TyKind::InferenceVar(tv, kind) => {
505 let inner = from_inference_var(tv); 257 if tv_stack.contains(&tv) {
506 if tv_stack.contains(&inner) {
507 cov_mark::hit!(type_var_cycles_resolve_as_possible); 258 cov_mark::hit!(type_var_cycles_resolve_as_possible);
508 // recursive type 259 // recursive type
509 return self.type_variable_table.fallback_value(tv, kind); 260 return self.type_variable_table.fallback_value(tv, kind);
510 } 261 }
511 if let Some(known_ty) = 262 if let Some(known_ty) = self.var_unification_table.probe_var(tv) {
512 self.var_unification_table.inlined_probe_value(inner).known()
513 {
514 // known_ty may contain other variables that are known by now 263 // known_ty may contain other variables that are known by now
515 tv_stack.push(inner); 264 tv_stack.push(tv);
516 let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone()); 265 let result = self.resolve_ty_as_possible_inner(
266 tv_stack,
267 known_ty.assert_ty_ref(&Interner).clone(),
268 );
517 tv_stack.pop(); 269 tv_stack.pop();
518 result 270 result
519 } else { 271 } else {
@@ -528,23 +280,24 @@ impl InferenceTable {
528 280
529 /// Resolves the type completely; type variables without known type are 281 /// Resolves the type completely; type variables without known type are
530 /// replaced by TyKind::Unknown. 282 /// replaced by TyKind::Unknown.
531 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 283 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<InferenceVar>, ty: Ty) -> Ty {
284 // FIXME implement as a proper Folder, handle lifetimes and consts as well
532 fold_tys( 285 fold_tys(
533 ty, 286 ty,
534 |ty, _| match ty.kind(&Interner) { 287 |ty, _| match ty.kind(&Interner) {
535 &TyKind::InferenceVar(tv, kind) => { 288 &TyKind::InferenceVar(tv, kind) => {
536 let inner = from_inference_var(tv); 289 if tv_stack.contains(&tv) {
537 if tv_stack.contains(&inner) {
538 cov_mark::hit!(type_var_cycles_resolve_completely); 290 cov_mark::hit!(type_var_cycles_resolve_completely);
539 // recursive type 291 // recursive type
540 return self.type_variable_table.fallback_value(tv, kind); 292 return self.type_variable_table.fallback_value(tv, kind);
541 } 293 }
542 if let Some(known_ty) = 294 if let Some(known_ty) = self.var_unification_table.probe_var(tv) {
543 self.var_unification_table.inlined_probe_value(inner).known()
544 {
545 // known_ty may contain other variables that are known by now 295 // known_ty may contain other variables that are known by now
546 tv_stack.push(inner); 296 tv_stack.push(tv);
547 let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone()); 297 let result = self.resolve_ty_completely_inner(
298 tv_stack,
299 known_ty.assert_ty_ref(&Interner).clone(),
300 );
548 tv_stack.pop(); 301 tv_stack.pop();
549 result 302 result
550 } else { 303 } else {
@@ -558,68 +311,10 @@ impl InferenceTable {
558 } 311 }
559} 312}
560 313
561/// The ID of a type variable. 314impl<'a> fmt::Debug for InferenceTable<'a> {
562#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] 315 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
563pub(super) struct TypeVarId(pub(super) u32); 316 f.debug_struct("InferenceTable")
564 317 .field("num_vars", &self.type_variable_table.inner.len())
565impl UnifyKey for TypeVarId { 318 .finish()
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 }
575
576 fn tag() -> &'static str {
577 "TypeVarId"
578 }
579}
580
581fn from_inference_var(var: InferenceVar) -> TypeVarId {
582 TypeVarId(var.index())
583}
584
585fn 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)]
592pub(super) enum TypeVarValue {
593 Known(Ty),
594 Unknown,
595}
596
597impl TypeVarValue {
598 fn known(&self) -> Option<&Ty> {
599 match self {
600 TypeVarValue::Known(ty) => Some(ty),
601 TypeVarValue::Unknown => None,
602 }
603 }
604}
605
606impl UnifyValue for TypeVarValue {
607 type Error = NoError;
608
609 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
610 match (value1, value2) {
611 // We should never equate two type variables, both of which have
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
618 // If one side is known, prefer that one.
619 (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
620 (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
621
622 (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
623 }
624 } 319 }
625} 320}
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 48bbcfd9f..37e1f89d8 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -798,7 +798,8 @@ pub(crate) fn inherent_impl_substs(
798 binders: CanonicalVarKinds::from_iter(&Interner, kinds), 798 binders: CanonicalVarKinds::from_iter(&Interner, kinds),
799 value: (self_ty_with_vars, self_ty.value.clone()), 799 value: (self_ty_with_vars, self_ty.value.clone()),
800 }; 800 };
801 let substs = super::infer::unify(&tys)?; 801 let trait_env = Arc::new(TraitEnvironment::default()); // FIXME
802 let substs = super::infer::unify(db, trait_env, &tys)?;
802 // We only want the substs for the vars we added, not the ones from self_ty. 803 // We only want the substs for the vars we added, not the ones from self_ty.
803 // Also, if any of the vars we added are still in there, we replace them by 804 // Also, if any of the vars we added are still in there, we replace them by
804 // Unknown. I think this can only really happen if self_ty contained 805 // Unknown. I think this can only really happen if self_ty contained