aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty/src')
-rw-r--r--crates/hir_ty/src/db.rs6
-rw-r--r--crates/hir_ty/src/infer.rs84
-rw-r--r--crates/hir_ty/src/infer/coerce.rs7
-rw-r--r--crates/hir_ty/src/infer/expr.rs6
-rw-r--r--crates/hir_ty/src/infer/path.rs2
-rw-r--r--crates/hir_ty/src/infer/unify.rs173
-rw-r--r--crates/hir_ty/src/lib.rs3
-rw-r--r--crates/hir_ty/src/lower.rs4
-rw-r--r--crates/hir_ty/src/method_resolution.rs48
-rw-r--r--crates/hir_ty/src/traits.rs40
10 files changed, 234 insertions, 139 deletions
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index f773aa621..be5b9110e 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -134,14 +134,14 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
134 fn trait_solve( 134 fn trait_solve(
135 &self, 135 &self,
136 krate: CrateId, 136 krate: CrateId,
137 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 137 goal: crate::Canonical<crate::InEnvironment<crate::Goal>>,
138 ) -> Option<crate::Solution>; 138 ) -> Option<crate::Solution>;
139 139
140 #[salsa::invoke(crate::traits::trait_solve_query)] 140 #[salsa::invoke(crate::traits::trait_solve_query)]
141 fn trait_solve_query( 141 fn trait_solve_query(
142 &self, 142 &self,
143 krate: CrateId, 143 krate: CrateId,
144 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 144 goal: crate::Canonical<crate::InEnvironment<crate::Goal>>,
145 ) -> Option<crate::Solution>; 145 ) -> Option<crate::Solution>;
146 146
147 #[salsa::invoke(chalk_db::program_clauses_for_chalk_env_query)] 147 #[salsa::invoke(chalk_db::program_clauses_for_chalk_env_query)]
@@ -168,7 +168,7 @@ fn infer_wait(db: &dyn HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult>
168fn trait_solve_wait( 168fn trait_solve_wait(
169 db: &dyn HirDatabase, 169 db: &dyn HirDatabase,
170 krate: CrateId, 170 krate: CrateId,
171 goal: crate::Canonical<crate::InEnvironment<crate::DomainGoal>>, 171 goal: crate::Canonical<crate::InEnvironment<crate::Goal>>,
172) -> Option<crate::Solution> { 172) -> Option<crate::Solution> {
173 let _p = profile::span("trait_solve::wait"); 173 let _p = profile::span("trait_solve::wait");
174 db.trait_solve_query(krate, goal) 174 db.trait_solve_query(krate, goal)
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 7898740be..97e7c5f8c 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -14,7 +14,7 @@
14//! the `ena` crate, which is extracted from rustc. 14//! the `ena` crate, which is extracted from rustc.
15 15
16use std::borrow::Cow; 16use std::borrow::Cow;
17use std::mem; 17
18use std::ops::Index; 18use std::ops::Index;
19use std::sync::Arc; 19use std::sync::Arc;
20 20
@@ -27,8 +27,8 @@ use hir_def::{
27 path::{path, Path}, 27 path::{path, Path},
28 resolver::{HasResolver, Resolver, TypeNs}, 28 resolver::{HasResolver, Resolver, TypeNs},
29 type_ref::TypeRef, 29 type_ref::TypeRef,
30 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, Lookup, TraitId, 30 AdtId, AssocItemId, DefWithBodyId, EnumVariantId, FieldId, FunctionId, HasModule, Lookup,
31 TypeAliasId, VariantId, 31 TraitId, TypeAliasId, VariantId,
32}; 32};
33use hir_expand::{diagnostics::DiagnosticSink, name::name}; 33use hir_expand::{diagnostics::DiagnosticSink, name::name};
34use la_arena::ArenaMap; 34use la_arena::ArenaMap;
@@ -36,13 +36,11 @@ use rustc_hash::FxHashMap;
36use stdx::impl_from; 36use stdx::impl_from;
37use syntax::SmolStr; 37use syntax::SmolStr;
38 38
39use super::{ 39use super::{DomainGoal, InEnvironment, ProjectionTy, TraitEnvironment, TraitRef, Ty};
40 DomainGoal, Guidance, InEnvironment, ProjectionTy, Solution, TraitEnvironment, TraitRef, Ty,
41};
42use crate::{ 40use crate::{
43 db::HirDatabase, fold_tys, infer::diagnostics::InferenceDiagnostic, 41 db::HirDatabase, fold_tys, infer::diagnostics::InferenceDiagnostic,
44 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Canonical, Interner, 42 lower::ImplTraitLoweringMode, to_assoc_type_id, AliasEq, AliasTy, Interner, TyBuilder, TyExt,
45 TyBuilder, TyExt, TyKind, 43 TyKind,
46}; 44};
47 45
48// This lint has a false positive here. See the link below for details. 46// This lint has a false positive here. See the link below for details.
@@ -227,8 +225,6 @@ struct InferenceContext<'a> {
227 resolver: Resolver, 225 resolver: Resolver,
228 table: unify::InferenceTable<'a>, 226 table: unify::InferenceTable<'a>,
229 trait_env: Arc<TraitEnvironment>, 227 trait_env: Arc<TraitEnvironment>,
230 obligations: Vec<DomainGoal>,
231 last_obligations_check: Option<u32>,
232 result: InferenceResult, 228 result: InferenceResult,
233 /// The return type of the function being inferred, or the closure if we're 229 /// The return type of the function being inferred, or the closure if we're
234 /// currently within one. 230 /// currently within one.
@@ -260,15 +256,15 @@ fn find_breakable<'c>(
260 256
261impl<'a> InferenceContext<'a> { 257impl<'a> InferenceContext<'a> {
262 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self { 258 fn new(db: &'a dyn HirDatabase, owner: DefWithBodyId, resolver: Resolver) -> Self {
263 let trait_env = 259 let krate = owner.module(db.upcast()).krate();
264 owner.as_generic_def_id().map_or_else(Default::default, |d| db.trait_environment(d)); 260 let trait_env = owner
261 .as_generic_def_id()
262 .map_or_else(|| Arc::new(TraitEnvironment::empty(krate)), |d| db.trait_environment(d));
265 InferenceContext { 263 InferenceContext {
266 result: InferenceResult::default(), 264 result: InferenceResult::default(),
267 table: unify::InferenceTable::new(db, trait_env.clone()), 265 table: unify::InferenceTable::new(db, trait_env.clone()),
268 obligations: Vec::default(),
269 last_obligations_check: None,
270 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature
271 trait_env, 266 trait_env,
267 return_ty: TyKind::Error.intern(&Interner), // set in collect_fn_signature
272 db, 268 db,
273 owner, 269 owner,
274 body: db.body(owner), 270 body: db.body(owner),
@@ -284,6 +280,7 @@ impl<'a> InferenceContext<'a> {
284 280
285 fn resolve_all(mut self) -> InferenceResult { 281 fn resolve_all(mut self) -> InferenceResult {
286 // FIXME resolve obligations as well (use Guidance if necessary) 282 // FIXME resolve obligations as well (use Guidance if necessary)
283 self.table.resolve_obligations_as_possible();
287 284
288 // make sure diverging type variables are marked as such 285 // make sure diverging type variables are marked as such
289 self.table.propagate_diverging_flag(); 286 self.table.propagate_diverging_flag();
@@ -357,44 +354,11 @@ impl<'a> InferenceContext<'a> {
357 } 354 }
358 355
359 fn resolve_obligations_as_possible(&mut self) { 356 fn resolve_obligations_as_possible(&mut self) {
360 let _span = profile::span("resolve_obligations_as_possible"); 357 self.table.resolve_obligations_as_possible();
361
362 let obligations = mem::replace(&mut self.obligations, Vec::new());
363 for obligation in obligations {
364 let in_env = InEnvironment::new(&self.trait_env.env, obligation.clone());
365 let canonicalized = self.canonicalize(in_env);
366 let solution =
367 self.db.trait_solve(self.resolver.krate().unwrap(), canonicalized.value.clone());
368
369 match solution {
370 Some(Solution::Unique(canonical_subst)) => {
371 canonicalized.apply_solution(
372 self,
373 Canonical {
374 binders: canonical_subst.binders,
375 // FIXME: handle constraints
376 value: canonical_subst.value.subst,
377 },
378 );
379 }
380 Some(Solution::Ambig(Guidance::Definite(substs))) => {
381 canonicalized.apply_solution(self, substs);
382 self.obligations.push(obligation);
383 }
384 Some(_) => {
385 // FIXME use this when trying to resolve everything at the end
386 self.obligations.push(obligation);
387 }
388 None => {
389 // FIXME obligation cannot be fulfilled => diagnostic
390 }
391 };
392 }
393 } 358 }
394 359
395 fn push_obligation(&mut self, o: DomainGoal) { 360 fn push_obligation(&mut self, o: DomainGoal) {
396 self.obligations.push(o); 361 self.table.register_obligation(o.cast(&Interner));
397 self.last_obligations_check = None;
398 } 362 }
399 363
400 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { 364 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
@@ -467,25 +431,7 @@ impl<'a> InferenceContext<'a> {
467 /// call). `make_ty` handles this already, but e.g. for field types we need 431 /// call). `make_ty` handles this already, but e.g. for field types we need
468 /// to do it as well. 432 /// to do it as well.
469 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty { 433 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
470 let ty = self.resolve_ty_as_possible(ty); 434 self.table.normalize_associated_types_in(ty)
471 fold_tys(
472 ty,
473 |ty, _| match ty.kind(&Interner) {
474 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
475 self.normalize_projection_ty(proj_ty.clone())
476 }
477 _ => ty,
478 },
479 DebruijnIndex::INNERMOST,
480 )
481 }
482
483 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
484 let var = self.table.new_type_var();
485 let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
486 let obligation = alias_eq.cast(&Interner);
487 self.push_obligation(obligation);
488 var
489 } 435 }
490 436
491 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) { 437 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index 4d80b4a08..911343cb9 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -402,12 +402,15 @@ impl<'a> InferenceContext<'a> {
402 // solve `CoerceUnsized` and `Unsize` goals at this point and leaves the 402 // solve `CoerceUnsized` and `Unsize` goals at this point and leaves the
403 // rest for later. Also, there's some logic about sized type variables. 403 // rest for later. Also, there's some logic about sized type variables.
404 // Need to find out in what cases this is necessary 404 // Need to find out in what cases this is necessary
405 let solution = self.db.trait_solve(krate, canonicalized.value.clone()).ok_or(TypeError)?; 405 let solution = self
406 .db
407 .trait_solve(krate, canonicalized.value.clone().cast(&Interner))
408 .ok_or(TypeError)?;
406 409
407 match solution { 410 match solution {
408 Solution::Unique(v) => { 411 Solution::Unique(v) => {
409 canonicalized.apply_solution( 412 canonicalized.apply_solution(
410 self, 413 &mut self.table,
411 Canonical { 414 Canonical {
412 binders: v.binders, 415 binders: v.binders,
413 // FIXME handle constraints 416 // FIXME handle constraints
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index f439169ea..6eaccd9b4 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -99,9 +99,9 @@ impl<'a> InferenceContext<'a> {
99 environment: trait_env, 99 environment: trait_env,
100 }; 100 };
101 let canonical = self.canonicalize(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.cast(&Interner)).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.table.normalize_projection_ty(projection);
105 Some((arg_tys, return_ty)) 105 Some((arg_tys, return_ty))
106 } else { 106 } else {
107 None 107 None
@@ -306,7 +306,7 @@ impl<'a> InferenceContext<'a> {
306 self.resolver.krate(), 306 self.resolver.krate(),
307 InEnvironment { 307 InEnvironment {
308 goal: canonicalized.value.clone(), 308 goal: canonicalized.value.clone(),
309 environment: self.trait_env.env.clone(), 309 environment: self.table.trait_env.env.clone(),
310 }, 310 },
311 ); 311 );
312 let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs 312 let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index bc64b612b..fd366e121 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -225,7 +225,7 @@ impl<'a> InferenceContext<'a> {
225 method_resolution::iterate_method_candidates( 225 method_resolution::iterate_method_candidates(
226 &canonical_ty.value, 226 &canonical_ty.value,
227 self.db, 227 self.db,
228 self.trait_env.clone(), 228 self.table.trait_env.clone(),
229 krate, 229 krate,
230 &traits_in_scope, 230 &traits_in_scope,
231 None, 231 None,
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index 93cd54f0d..75e04e8b5 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -1,6 +1,6 @@
1//! Unification and canonicalization logic. 1//! Unification and canonicalization logic.
2 2
3use std::{borrow::Cow, fmt, sync::Arc}; 3use std::{borrow::Cow, fmt, mem, sync::Arc};
4 4
5use chalk_ir::{ 5use chalk_ir::{
6 cast::Cast, fold::Fold, interner::HasInterner, zip::Zip, FloatTy, IntTy, TyVariableKind, 6 cast::Cast, fold::Fold, interner::HasInterner, zip::Zip, FloatTy, IntTy, TyVariableKind,
@@ -11,8 +11,9 @@ use ena::unify::UnifyKey;
11 11
12use super::{InferOk, InferResult, InferenceContext, TypeError}; 12use super::{InferOk, InferResult, InferenceContext, TypeError};
13use crate::{ 13use crate::{
14 db::HirDatabase, fold_tys, static_lifetime, BoundVar, Canonical, DebruijnIndex, GenericArg, 14 db::HirDatabase, fold_tys, static_lifetime, AliasEq, AliasTy, BoundVar, Canonical,
15 InferenceVar, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyKind, VariableKind, 15 DebruijnIndex, GenericArg, Goal, Guidance, InEnvironment, InferenceVar, Interner, ProjectionTy,
16 Scalar, Solution, Substitution, TraitEnvironment, Ty, TyKind, VariableKind,
16}; 17};
17 18
18impl<'a> InferenceContext<'a> { 19impl<'a> InferenceContext<'a> {
@@ -23,17 +24,11 @@ impl<'a> InferenceContext<'a> {
23 where 24 where
24 T::Result: HasInterner<Interner = Interner>, 25 T::Result: HasInterner<Interner = Interner>,
25 { 26 {
26 let result = self.table.var_unification_table.canonicalize(&Interner, t); 27 self.table.canonicalize(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 }
33 } 28 }
34} 29}
35 30
36#[derive(Debug)] 31#[derive(Debug, Clone)]
37pub(super) struct Canonicalized<T> 32pub(super) struct Canonicalized<T>
38where 33where
39 T: HasInterner<Interner = Interner>, 34 T: HasInterner<Interner = Interner>,
@@ -49,22 +44,16 @@ impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
49 44
50 pub(super) fn apply_solution( 45 pub(super) fn apply_solution(
51 &self, 46 &self,
52 ctx: &mut InferenceContext<'_>, 47 ctx: &mut InferenceTable,
53 solution: Canonical<Substitution>, 48 solution: Canonical<Substitution>,
54 ) { 49 ) {
55 // the solution may contain new variables, which we need to convert to new inference vars 50 // the solution may contain new variables, which we need to convert to new inference vars
56 let new_vars = Substitution::from_iter( 51 let new_vars = Substitution::from_iter(
57 &Interner, 52 &Interner,
58 solution.binders.iter(&Interner).map(|k| match k.kind { 53 solution.binders.iter(&Interner).map(|k| match k.kind {
59 VariableKind::Ty(TyVariableKind::General) => { 54 VariableKind::Ty(TyVariableKind::General) => ctx.new_type_var().cast(&Interner),
60 ctx.table.new_type_var().cast(&Interner) 55 VariableKind::Ty(TyVariableKind::Integer) => ctx.new_integer_var().cast(&Interner),
61 } 56 VariableKind::Ty(TyVariableKind::Float) => ctx.new_float_var().cast(&Interner),
62 VariableKind::Ty(TyVariableKind::Integer) => {
63 ctx.table.new_integer_var().cast(&Interner)
64 }
65 VariableKind::Ty(TyVariableKind::Float) => {
66 ctx.table.new_float_var().cast(&Interner)
67 }
68 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere 57 // Chalk can sometimes return new lifetime variables. We just use the static lifetime everywhere
69 VariableKind::Lifetime => static_lifetime().cast(&Interner), 58 VariableKind::Lifetime => static_lifetime().cast(&Interner),
70 _ => panic!("const variable in solution"), 59 _ => panic!("const variable in solution"),
@@ -76,9 +65,9 @@ impl<T: HasInterner<Interner = Interner>> Canonicalized<T> {
76 // eagerly replace projections in the type; we may be getting types 65 // eagerly replace projections in the type; we may be getting types
77 // e.g. from where clauses where this hasn't happened yet 66 // e.g. from where clauses where this hasn't happened yet
78 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner)); 67 let ty = ctx.normalize_associated_types_in(new_vars.apply(ty.clone(), &Interner));
79 ctx.table.unify(var.assert_ty_ref(&Interner), &ty); 68 ctx.unify(var.assert_ty_ref(&Interner), &ty);
80 } else { 69 } else {
81 let _ = ctx.table.unify_inner(&var, &new_vars.apply(v.clone(), &Interner)); 70 let _ = ctx.unify_inner(&var, &new_vars.apply(v.clone(), &Interner));
82 } 71 }
83 } 72 }
84 } 73 }
@@ -167,10 +156,11 @@ type ChalkInferenceTable = chalk_solve::infer::InferenceTable<Interner>;
167 156
168#[derive(Clone)] 157#[derive(Clone)]
169pub(crate) struct InferenceTable<'a> { 158pub(crate) struct InferenceTable<'a> {
170 db: &'a dyn HirDatabase, 159 pub db: &'a dyn HirDatabase,
171 trait_env: Arc<TraitEnvironment>, 160 pub trait_env: Arc<TraitEnvironment>,
172 pub(super) var_unification_table: ChalkInferenceTable, 161 pub(super) var_unification_table: ChalkInferenceTable,
173 pub(super) type_variable_table: TypeVariableTable, 162 pub(super) type_variable_table: TypeVariableTable,
163 pending_obligations: Vec<Canonicalized<InEnvironment<Goal>>>,
174} 164}
175 165
176impl<'a> InferenceTable<'a> { 166impl<'a> InferenceTable<'a> {
@@ -180,6 +170,7 @@ impl<'a> InferenceTable<'a> {
180 trait_env, 170 trait_env,
181 var_unification_table: ChalkInferenceTable::new(), 171 var_unification_table: ChalkInferenceTable::new(),
182 type_variable_table: TypeVariableTable { inner: Vec::new() }, 172 type_variable_table: TypeVariableTable { inner: Vec::new() },
173 pending_obligations: Vec::new(),
183 } 174 }
184 } 175 }
185 176
@@ -202,6 +193,50 @@ impl<'a> InferenceTable<'a> {
202 } 193 }
203 } 194 }
204 195
196 pub(super) fn canonicalize<T: Fold<Interner> + HasInterner<Interner = Interner>>(
197 &mut self,
198 t: T,
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 let ty = self.resolve_ty_as_possible(ty);
220 fold_tys(
221 ty,
222 |ty, _| match ty.kind(&Interner) {
223 TyKind::Alias(AliasTy::Projection(proj_ty)) => {
224 self.normalize_projection_ty(proj_ty.clone())
225 }
226 _ => ty,
227 },
228 DebruijnIndex::INNERMOST,
229 )
230 }
231
232 pub(super) fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
233 let var = self.new_type_var();
234 let alias_eq = AliasEq { alias: AliasTy::Projection(proj_ty), ty: var.clone() };
235 let obligation = alias_eq.cast(&Interner);
236 self.register_obligation(obligation);
237 var
238 }
239
205 fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty { 240 fn new_var(&mut self, kind: TyVariableKind, diverging: bool) -> Ty {
206 let var = self.var_unification_table.new_variable(UniverseIndex::ROOT); 241 let var = self.var_unification_table.new_variable(UniverseIndex::ROOT);
207 // Chalk might have created some type variables for its own purposes that we don't know about... 242 // Chalk might have created some type variables for its own purposes that we don't know about...
@@ -341,6 +376,94 @@ impl<'a> InferenceTable<'a> {
341 DebruijnIndex::INNERMOST, 376 DebruijnIndex::INNERMOST,
342 ) 377 )
343 } 378 }
379
380 pub fn register_obligation(&mut self, goal: Goal) {
381 let in_env = InEnvironment::new(&self.trait_env.env, goal);
382 self.register_obligation_in_env(in_env)
383 }
384
385 fn register_obligation_in_env(&mut self, goal: InEnvironment<Goal>) {
386 let canonicalized = self.canonicalize(goal);
387 if !self.try_resolve_obligation(&canonicalized) {
388 self.pending_obligations.push(canonicalized);
389 }
390 }
391
392 pub fn resolve_obligations_as_possible(&mut self) {
393 let _span = profile::span("resolve_obligations_as_possible");
394 let mut changed = true;
395 let mut obligations = Vec::new();
396 while changed {
397 changed = false;
398 mem::swap(&mut self.pending_obligations, &mut obligations);
399 for canonicalized in obligations.drain(..) {
400 if !self.check_changed(&canonicalized) {
401 self.pending_obligations.push(canonicalized);
402 continue;
403 }
404 changed = true;
405 let uncanonical = chalk_ir::Substitute::apply(
406 &canonicalized.free_vars,
407 canonicalized.value.value,
408 &Interner,
409 );
410 self.register_obligation_in_env(uncanonical);
411 }
412 }
413 }
414
415 /// This checks whether any of the free variables in the `canonicalized`
416 /// have changed (either been unified with another variable, or with a
417 /// value). If this is not the case, we don't need to try to solve the goal
418 /// again -- it'll give the same result as last time.
419 fn check_changed(&mut self, canonicalized: &Canonicalized<InEnvironment<Goal>>) -> bool {
420 canonicalized.free_vars.iter().any(|var| {
421 let iv = match var.data(&Interner) {
422 chalk_ir::GenericArgData::Ty(ty) => ty.inference_var(&Interner),
423 chalk_ir::GenericArgData::Lifetime(lt) => lt.inference_var(&Interner),
424 chalk_ir::GenericArgData::Const(c) => c.inference_var(&Interner),
425 }
426 .expect("free var is not inference var");
427 if self.var_unification_table.probe_var(iv).is_some() {
428 return true;
429 }
430 let root = self.var_unification_table.inference_var_root(iv);
431 iv != root
432 })
433 }
434
435 fn try_resolve_obligation(
436 &mut self,
437 canonicalized: &Canonicalized<InEnvironment<Goal>>,
438 ) -> bool {
439 let solution = self.db.trait_solve(self.trait_env.krate, canonicalized.value.clone());
440
441 match solution {
442 Some(Solution::Unique(canonical_subst)) => {
443 canonicalized.apply_solution(
444 self,
445 Canonical {
446 binders: canonical_subst.binders,
447 // FIXME: handle constraints
448 value: canonical_subst.value.subst,
449 },
450 );
451 true
452 }
453 Some(Solution::Ambig(Guidance::Definite(substs))) => {
454 canonicalized.apply_solution(self, substs);
455 false
456 }
457 Some(_) => {
458 // FIXME use this when trying to resolve everything at the end
459 false
460 }
461 None => {
462 // FIXME obligation cannot be fulfilled => diagnostic
463 true
464 }
465 }
466 }
344} 467}
345 468
346impl<'a> fmt::Debug for InferenceTable<'a> { 469impl<'a> fmt::Debug for InferenceTable<'a> {
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 56f60c46b..72093d75a 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -45,7 +45,7 @@ use hir_def::{
45}; 45};
46use stdx::always; 46use stdx::always;
47 47
48use crate::{db::HirDatabase, display::HirDisplay, utils::generics}; 48use crate::{db::HirDatabase, utils::generics};
49 49
50pub use autoderef::autoderef; 50pub use autoderef::autoderef;
51pub use builder::TyBuilder; 51pub use builder::TyBuilder;
@@ -114,6 +114,7 @@ pub type FnSig = chalk_ir::FnSig<Interner>;
114 114
115pub type InEnvironment<T> = chalk_ir::InEnvironment<T>; 115pub type InEnvironment<T> = chalk_ir::InEnvironment<T>;
116pub type DomainGoal = chalk_ir::DomainGoal<Interner>; 116pub type DomainGoal = chalk_ir::DomainGoal<Interner>;
117pub type Goal = chalk_ir::Goal<Interner>;
117pub type AliasEq = chalk_ir::AliasEq<Interner>; 118pub type AliasEq = chalk_ir::AliasEq<Interner>;
118pub type Solution = chalk_solve::Solution<Interner>; 119pub type Solution = chalk_solve::Solution<Interner>;
119pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>; 120pub type ConstrainedSubst = chalk_ir::ConstrainedSubst<Interner>;
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index bd8bb6028..8a375b973 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -1035,9 +1035,11 @@ pub(crate) fn trait_environment_query(
1035 clauses.push(program_clause.into_from_env_clause(&Interner)); 1035 clauses.push(program_clause.into_from_env_clause(&Interner));
1036 } 1036 }
1037 1037
1038 let krate = def.module(db.upcast()).krate();
1039
1038 let env = chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses); 1040 let env = chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses);
1039 1041
1040 Arc::new(TraitEnvironment { traits_from_clauses: traits_in_scope, env }) 1042 Arc::new(TraitEnvironment { krate, traits_from_clauses: traits_in_scope, env })
1041} 1043}
1042 1044
1043/// Resolve the where clause(s) of an item with generics. 1045/// Resolve the where clause(s) of an item with generics.
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 37e1f89d8..08e385a42 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -577,6 +577,7 @@ fn iterate_method_candidates_by_receiver(
577 if iterate_inherent_methods( 577 if iterate_inherent_methods(
578 self_ty, 578 self_ty,
579 db, 579 db,
580 env.clone(),
580 name, 581 name,
581 Some(receiver_ty), 582 Some(receiver_ty),
582 krate, 583 krate,
@@ -613,8 +614,16 @@ fn iterate_method_candidates_for_self_ty(
613 name: Option<&Name>, 614 name: Option<&Name>,
614 mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool, 615 mut callback: &mut dyn FnMut(&Ty, AssocItemId) -> bool,
615) -> bool { 616) -> bool {
616 if iterate_inherent_methods(self_ty, db, name, None, krate, visible_from_module, &mut callback) 617 if iterate_inherent_methods(
617 { 618 self_ty,
619 db,
620 env.clone(),
621 name,
622 None,
623 krate,
624 visible_from_module,
625 &mut callback,
626 ) {
618 return true; 627 return true;
619 } 628 }
620 iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback) 629 iterate_trait_method_candidates(self_ty, db, env, krate, traits_in_scope, name, None, callback)
@@ -653,12 +662,12 @@ fn iterate_trait_method_candidates(
653 for (_name, item) in data.items.iter() { 662 for (_name, item) in data.items.iter() {
654 // Don't pass a `visible_from_module` down to `is_valid_candidate`, 663 // Don't pass a `visible_from_module` down to `is_valid_candidate`,
655 // since only inherent methods should be included into visibility checking. 664 // since only inherent methods should be included into visibility checking.
656 if !is_valid_candidate(db, name, receiver_ty, *item, self_ty, None) { 665 if !is_valid_candidate(db, env.clone(), name, receiver_ty, *item, self_ty, None) {
657 continue; 666 continue;
658 } 667 }
659 if !known_implemented { 668 if !known_implemented {
660 let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone()); 669 let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone());
661 if db.trait_solve(krate, goal).is_none() { 670 if db.trait_solve(krate, goal.cast(&Interner)).is_none() {
662 continue 'traits; 671 continue 'traits;
663 } 672 }
664 } 673 }
@@ -675,6 +684,7 @@ fn iterate_trait_method_candidates(
675fn iterate_inherent_methods( 684fn iterate_inherent_methods(
676 self_ty: &Canonical<Ty>, 685 self_ty: &Canonical<Ty>,
677 db: &dyn HirDatabase, 686 db: &dyn HirDatabase,
687 env: Arc<TraitEnvironment>,
678 name: Option<&Name>, 688 name: Option<&Name>,
679 receiver_ty: Option<&Canonical<Ty>>, 689 receiver_ty: Option<&Canonical<Ty>>,
680 krate: CrateId, 690 krate: CrateId,
@@ -690,14 +700,24 @@ fn iterate_inherent_methods(
690 700
691 for &impl_def in impls.for_self_ty(&self_ty.value) { 701 for &impl_def in impls.for_self_ty(&self_ty.value) {
692 for &item in db.impl_data(impl_def).items.iter() { 702 for &item in db.impl_data(impl_def).items.iter() {
693 if !is_valid_candidate(db, name, receiver_ty, item, self_ty, visible_from_module) { 703 if !is_valid_candidate(
704 db,
705 env.clone(),
706 name,
707 receiver_ty,
708 item,
709 self_ty,
710 visible_from_module,
711 ) {
694 continue; 712 continue;
695 } 713 }
696 // we have to check whether the self type unifies with the type 714 // we have to check whether the self type unifies with the type
697 // that the impl is for. If we have a receiver type, this 715 // that the impl is for. If we have a receiver type, this
698 // already happens in `is_valid_candidate` above; if not, we 716 // already happens in `is_valid_candidate` above; if not, we
699 // check it here 717 // check it here
700 if receiver_ty.is_none() && inherent_impl_substs(db, impl_def, self_ty).is_none() { 718 if receiver_ty.is_none()
719 && inherent_impl_substs(db, env.clone(), impl_def, self_ty).is_none()
720 {
701 cov_mark::hit!(impl_self_type_match_without_receiver); 721 cov_mark::hit!(impl_self_type_match_without_receiver);
702 continue; 722 continue;
703 } 723 }
@@ -722,7 +742,7 @@ pub fn resolve_indexing_op(
722 let deref_chain = autoderef_method_receiver(db, krate, ty); 742 let deref_chain = autoderef_method_receiver(db, krate, ty);
723 for ty in deref_chain { 743 for ty in deref_chain {
724 let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone()); 744 let goal = generic_implements_goal(db, env.clone(), index_trait, ty.clone());
725 if db.trait_solve(krate, goal).is_some() { 745 if db.trait_solve(krate, goal.cast(&Interner)).is_some() {
726 return Some(ty); 746 return Some(ty);
727 } 747 }
728 } 748 }
@@ -731,6 +751,7 @@ pub fn resolve_indexing_op(
731 751
732fn is_valid_candidate( 752fn is_valid_candidate(
733 db: &dyn HirDatabase, 753 db: &dyn HirDatabase,
754 env: Arc<TraitEnvironment>,
734 name: Option<&Name>, 755 name: Option<&Name>,
735 receiver_ty: Option<&Canonical<Ty>>, 756 receiver_ty: Option<&Canonical<Ty>>,
736 item: AssocItemId, 757 item: AssocItemId,
@@ -749,7 +770,7 @@ fn is_valid_candidate(
749 if !data.has_self_param() { 770 if !data.has_self_param() {
750 return false; 771 return false;
751 } 772 }
752 let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) { 773 let transformed_receiver_ty = match transform_receiver_ty(db, env, m, self_ty) {
753 Some(ty) => ty, 774 Some(ty) => ty,
754 None => return false, 775 None => return false,
755 }; 776 };
@@ -776,6 +797,7 @@ fn is_valid_candidate(
776 797
777pub(crate) fn inherent_impl_substs( 798pub(crate) fn inherent_impl_substs(
778 db: &dyn HirDatabase, 799 db: &dyn HirDatabase,
800 env: Arc<TraitEnvironment>,
779 impl_id: ImplId, 801 impl_id: ImplId,
780 self_ty: &Canonical<Ty>, 802 self_ty: &Canonical<Ty>,
781) -> Option<Substitution> { 803) -> Option<Substitution> {
@@ -798,8 +820,7 @@ pub(crate) fn inherent_impl_substs(
798 binders: CanonicalVarKinds::from_iter(&Interner, kinds), 820 binders: CanonicalVarKinds::from_iter(&Interner, kinds),
799 value: (self_ty_with_vars, self_ty.value.clone()), 821 value: (self_ty_with_vars, self_ty.value.clone()),
800 }; 822 };
801 let trait_env = Arc::new(TraitEnvironment::default()); // FIXME 823 let substs = super::infer::unify(db, env, &tys)?;
802 let substs = super::infer::unify(db, trait_env, &tys)?;
803 // We only want the substs for the vars we added, not the ones from self_ty. 824 // We only want the substs for the vars we added, not the ones from self_ty.
804 // Also, if any of the vars we added are still in there, we replace them by 825 // Also, if any of the vars we added are still in there, we replace them by
805 // Unknown. I think this can only really happen if self_ty contained 826 // Unknown. I think this can only really happen if self_ty contained
@@ -824,6 +845,7 @@ fn fallback_bound_vars(s: Substitution, num_vars_to_keep: usize) -> Substitution
824 845
825fn transform_receiver_ty( 846fn transform_receiver_ty(
826 db: &dyn HirDatabase, 847 db: &dyn HirDatabase,
848 env: Arc<TraitEnvironment>,
827 function_id: FunctionId, 849 function_id: FunctionId,
828 self_ty: &Canonical<Ty>, 850 self_ty: &Canonical<Ty>,
829) -> Option<Ty> { 851) -> Option<Ty> {
@@ -833,7 +855,7 @@ fn transform_receiver_ty(
833 .fill_with_unknown() 855 .fill_with_unknown()
834 .build(), 856 .build(),
835 AssocContainerId::ImplId(impl_id) => { 857 AssocContainerId::ImplId(impl_id) => {
836 let impl_substs = inherent_impl_substs(db, impl_id, &self_ty)?; 858 let impl_substs = inherent_impl_substs(db, env, impl_id, &self_ty)?;
837 TyBuilder::subst_for_def(db, function_id) 859 TyBuilder::subst_for_def(db, function_id)
838 .use_parent_substs(&impl_substs) 860 .use_parent_substs(&impl_substs)
839 .fill_with_unknown() 861 .fill_with_unknown()
@@ -853,7 +875,7 @@ pub fn implements_trait(
853 trait_: TraitId, 875 trait_: TraitId,
854) -> bool { 876) -> bool {
855 let goal = generic_implements_goal(db, env, trait_, ty.clone()); 877 let goal = generic_implements_goal(db, env, trait_, ty.clone());
856 let solution = db.trait_solve(krate, goal); 878 let solution = db.trait_solve(krate, goal.cast(&Interner));
857 879
858 solution.is_some() 880 solution.is_some()
859} 881}
@@ -866,7 +888,7 @@ pub fn implements_trait_unique(
866 trait_: TraitId, 888 trait_: TraitId,
867) -> bool { 889) -> bool {
868 let goal = generic_implements_goal(db, env, trait_, ty.clone()); 890 let goal = generic_implements_goal(db, env, trait_, ty.clone());
869 let solution = db.trait_solve(krate, goal); 891 let solution = db.trait_solve(krate, goal.cast(&Interner));
870 892
871 matches!(solution, Some(crate::Solution::Unique(_))) 893 matches!(solution, Some(crate::Solution::Unique(_)))
872} 894}
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index 9936d0803..294cb531c 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -2,7 +2,7 @@
2 2
3use std::env::var; 3use std::env::var;
4 4
5use chalk_ir::cast::Cast; 5use chalk_ir::GoalData;
6use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver}; 6use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver};
7 7
8use base_db::CrateId; 8use base_db::CrateId;
@@ -10,7 +10,7 @@ use hir_def::{lang_item::LangItemTarget, TraitId};
10use stdx::panic_context; 10use stdx::panic_context;
11 11
12use crate::{ 12use crate::{
13 db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Guidance, HirDisplay, InEnvironment, 13 db::HirDatabase, AliasEq, AliasTy, Canonical, DomainGoal, Goal, Guidance, InEnvironment,
14 Interner, Solution, TraitRefExt, Ty, TyKind, WhereClause, 14 Interner, Solution, TraitRefExt, Ty, TyKind, WhereClause,
15}; 15};
16 16
@@ -38,6 +38,7 @@ fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
38/// we assume that `T: Default`. 38/// we assume that `T: Default`.
39#[derive(Debug, Clone, PartialEq, Eq, Hash)] 39#[derive(Debug, Clone, PartialEq, Eq, Hash)]
40pub struct TraitEnvironment { 40pub struct TraitEnvironment {
41 pub krate: CrateId,
41 // When we're using Chalk's Ty we can make this a BTreeMap since it's Ord, 42 // When we're using Chalk's Ty we can make this a BTreeMap since it's Ord,
42 // but for now it's too annoying... 43 // but for now it's too annoying...
43 pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>, 44 pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
@@ -45,6 +46,14 @@ pub struct TraitEnvironment {
45} 46}
46 47
47impl TraitEnvironment { 48impl TraitEnvironment {
49 pub fn empty(krate: CrateId) -> Self {
50 TraitEnvironment {
51 krate,
52 traits_from_clauses: Vec::new(),
53 env: chalk_ir::Environment::new(&Interner),
54 }
55 }
56
48 pub(crate) fn traits_in_scope_from_clauses<'a>( 57 pub(crate) fn traits_in_scope_from_clauses<'a>(
49 &'a self, 58 &'a self,
50 ty: &'a Ty, 59 ty: &'a Ty,
@@ -59,34 +68,25 @@ impl TraitEnvironment {
59 } 68 }
60} 69}
61 70
62impl Default for TraitEnvironment {
63 fn default() -> Self {
64 TraitEnvironment {
65 traits_from_clauses: Vec::new(),
66 env: chalk_ir::Environment::new(&Interner),
67 }
68 }
69}
70
71/// Solve a trait goal using Chalk. 71/// Solve a trait goal using Chalk.
72pub(crate) fn trait_solve_query( 72pub(crate) fn trait_solve_query(
73 db: &dyn HirDatabase, 73 db: &dyn HirDatabase,
74 krate: CrateId, 74 krate: CrateId,
75 goal: Canonical<InEnvironment<DomainGoal>>, 75 goal: Canonical<InEnvironment<Goal>>,
76) -> Option<Solution> { 76) -> Option<Solution> {
77 let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal { 77 let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal.data(&Interner) {
78 DomainGoal::Holds(WhereClause::Implemented(it)) => { 78 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => {
79 db.trait_data(it.hir_trait_id()).name.to_string() 79 db.trait_data(it.hir_trait_id()).name.to_string()
80 } 80 }
81 DomainGoal::Holds(WhereClause::AliasEq(_)) => "alias_eq".to_string(), 81 GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_string(),
82 _ => "??".to_string(), 82 _ => "??".to_string(),
83 }); 83 });
84 log::info!("trait_solve_query({})", goal.value.goal.display(db)); 84 log::info!("trait_solve_query({:?})", goal.value.goal);
85 85
86 if let DomainGoal::Holds(WhereClause::AliasEq(AliasEq { 86 if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
87 alias: AliasTy::Projection(projection_ty), 87 alias: AliasTy::Projection(projection_ty),
88 .. 88 ..
89 })) = &goal.value.goal 89 }))) = &goal.value.goal.data(&Interner)
90 { 90 {
91 if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(&Interner).kind(&Interner) { 91 if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(&Interner).kind(&Interner) {
92 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible 92 // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
@@ -94,11 +94,9 @@ pub(crate) fn trait_solve_query(
94 } 94 }
95 } 95 }
96 96
97 let canonical = goal.cast(&Interner);
98
99 // We currently don't deal with universes (I think / hope they're not yet 97 // We currently don't deal with universes (I think / hope they're not yet
100 // relevant for our use cases?) 98 // relevant for our use cases?)
101 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; 99 let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 };
102 solve(db, krate, &u_canonical) 100 solve(db, krate, &u_canonical)
103} 101}
104 102