aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src
diff options
context:
space:
mode:
authorFlorian Diebold <[email protected]>2019-04-20 11:34:36 +0100
committerFlorian Diebold <[email protected]>2019-05-04 17:18:30 +0100
commitb9c0c2abb79769852119dc9a595e63ee74eeba03 (patch)
tree39bf8f14438771f20337eaf57c421aebe3e7dfdb /crates/ra_hir/src
parent6269791d3626b9a9e5ea6a11c15e14470c0809a0 (diff)
Chalk integration
- add proper canonicalization logic - add conversions from/to Chalk IR
Diffstat (limited to 'crates/ra_hir/src')
-rw-r--r--crates/ra_hir/src/code_model_api.rs6
-rw-r--r--crates/ra_hir/src/db.rs26
-rw-r--r--crates/ra_hir/src/generics.rs11
-rw-r--r--crates/ra_hir/src/ids.rs54
-rw-r--r--crates/ra_hir/src/resolve.rs3
-rw-r--r--crates/ra_hir/src/ty.rs49
-rw-r--r--crates/ra_hir/src/ty/infer.rs31
-rw-r--r--crates/ra_hir/src/ty/infer/unify.rs81
-rw-r--r--crates/ra_hir/src/ty/lower.rs30
-rw-r--r--crates/ra_hir/src/ty/method_resolution.rs29
-rw-r--r--crates/ra_hir/src/ty/tests.rs2
-rw-r--r--crates/ra_hir/src/ty/traits.rs493
12 files changed, 669 insertions, 146 deletions
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 8f1ed1086..9dcae50a5 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -9,7 +9,7 @@ use crate::{
9 type_ref::TypeRef, 9 type_ref::TypeRef,
10 nameres::{ModuleScope, Namespace, ImportId, CrateModuleId}, 10 nameres::{ModuleScope, Namespace, ImportId, CrateModuleId},
11 expr::{Body, BodySourceMap}, 11 expr::{Body, BodySourceMap},
12 ty::InferenceResult, 12 ty::{ TraitRef, InferenceResult},
13 adt::{EnumVariantId, StructFieldId, VariantDef}, 13 adt::{EnumVariantId, StructFieldId, VariantDef},
14 generics::HasGenericParams, 14 generics::HasGenericParams,
15 docs::{Documentation, Docs, docs_from_ast}, 15 docs::{Documentation, Docs, docs_from_ast},
@@ -696,6 +696,10 @@ impl Trait {
696 db.trait_data(self) 696 db.trait_data(self)
697 } 697 }
698 698
699 pub fn trait_ref(self, db: &impl HirDatabase) -> TraitRef {
700 TraitRef::for_trait(db, self)
701 }
702
699 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { 703 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
700 let r = self.module(db).resolver(db); 704 let r = self.module(db).resolver(db);
701 // add generic params, if present 705 // add generic params, if present
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 398e00c42..b2c4fccf2 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -1,4 +1,4 @@
1use std::sync::Arc; 1use std::sync::{Arc, Mutex};
2 2
3use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast}; 3use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast};
4use ra_db::{SourceDatabase, salsa}; 4use ra_db::{SourceDatabase, salsa};
@@ -8,16 +8,16 @@ use crate::{
8 Function, FnSignature, ExprScopes, TypeAlias, 8 Function, FnSignature, ExprScopes, TypeAlias,
9 Struct, Enum, StructField, 9 Struct, Enum, StructField,
10 Const, ConstSignature, Static, 10 Const, ConstSignature, Static,
11 DefWithBody, 11 DefWithBody, Trait,
12 ids,
12 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, 13 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap},
13 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig}, 14 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor},
14 adt::{StructData, EnumData}, 15 adt::{StructData, EnumData},
15 impl_block::{ModuleImplBlocks, ImplSourceMap}, 16 impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
16 generics::{GenericParams, GenericDef}, 17 generics::{GenericParams, GenericDef},
17 type_ref::TypeRef, 18 type_ref::TypeRef,
18 traits::TraitData, Trait, ty::TraitRef, 19 traits::TraitData,
19 lang_item::{LangItems, LangItemTarget}, 20 lang_item::{LangItems, LangItemTarget},
20 ids
21}; 21};
22 22
23#[salsa::query_group(DefDatabaseStorage)] 23#[salsa::query_group(DefDatabaseStorage)]
@@ -39,6 +39,12 @@ pub trait DefDatabase: SourceDatabase {
39 #[salsa::interned] 39 #[salsa::interned]
40 fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId; 40 fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId;
41 41
42 // Interned IDs for Chalk integration
43 #[salsa::interned]
44 fn intern_type_ctor(&self, type_ctor: TypeCtor) -> ids::TypeCtorId;
45 #[salsa::interned]
46 fn intern_impl_block(&self, impl_block: ImplBlock) -> ids::GlobalImplId;
47
42 #[salsa::invoke(crate::ids::macro_def_query)] 48 #[salsa::invoke(crate::ids::macro_def_query)]
43 fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>; 49 fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>;
44 50
@@ -144,8 +150,12 @@ pub trait HirDatabase: DefDatabase {
144 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] 150 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
145 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>; 151 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
146 152
147 #[salsa::invoke(crate::ty::traits::implements)] 153 #[salsa::invoke(crate::ty::traits::impls_for_trait)]
148 fn implements(&self, trait_ref: TraitRef) -> Option<crate::ty::traits::Solution>; 154 fn impls_for_trait(&self, krate: Crate, trait_: Trait) -> Arc<[ImplBlock]>;
155
156 #[salsa::invoke(crate::ty::traits::solver)]
157 #[salsa::volatile]
158 fn chalk_solver(&self, krate: Crate) -> Arc<Mutex<chalk_solve::Solver>>;
149} 159}
150 160
151#[test] 161#[test]
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 1c71e21ea..2e52c5871 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -9,7 +9,7 @@ use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner};
9 9
10use crate::{ 10use crate::{
11 db::DefDatabase, 11 db::DefDatabase,
12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef 12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef
13}; 13};
14 14
15/// Data about a generic parameter (to a function, struct, impl, ...). 15/// Data about a generic parameter (to a function, struct, impl, ...).
@@ -157,6 +157,15 @@ impl From<Container> for GenericDef {
157 } 157 }
158} 158}
159 159
160impl From<crate::adt::AdtDef> for GenericDef {
161 fn from(adt: crate::adt::AdtDef) -> Self {
162 match adt {
163 AdtDef::Struct(s) => s.into(),
164 AdtDef::Enum(e) => e.into(),
165 }
166 }
167}
168
160pub trait HasGenericParams { 169pub trait HasGenericParams {
161 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>; 170 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>;
162} 171}
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index 4102951c9..6875b006d 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -323,6 +323,25 @@ impl AstItemDef<ast::TraitDef> for TraitId {
323 } 323 }
324} 324}
325 325
326fn from_chalk<T: salsa::InternKey>(chalk_id: chalk_ir::RawId) -> T {
327 T::from_intern_id(salsa::InternId::from(chalk_id.index))
328}
329fn to_chalk<T: salsa::InternKey>(salsa_id: T) -> chalk_ir::RawId {
330 chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() }
331}
332
333impl From<chalk_ir::TraitId> for TraitId {
334 fn from(trait_id: chalk_ir::TraitId) -> Self {
335 from_chalk(trait_id.0)
336 }
337}
338
339impl From<TraitId> for chalk_ir::TraitId {
340 fn from(trait_id: TraitId) -> Self {
341 chalk_ir::TraitId(to_chalk(trait_id))
342 }
343}
344
326#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 345#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
327pub struct TypeAliasId(salsa::InternId); 346pub struct TypeAliasId(salsa::InternId);
328impl_intern_key!(TypeAliasId); 347impl_intern_key!(TypeAliasId);
@@ -354,3 +373,38 @@ impl MacroCallId {
354 ) 373 )
355 } 374 }
356} 375}
376
377/// This exists just for chalk, because chalk doesn't differentiate between
378/// enums and structs.
379#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
380pub struct TypeCtorId(salsa::InternId);
381impl_intern_key!(TypeCtorId);
382
383impl From<chalk_ir::StructId> for TypeCtorId {
384 fn from(struct_id: chalk_ir::StructId) -> Self {
385 from_chalk(struct_id.0)
386 }
387}
388
389impl From<TypeCtorId> for chalk_ir::StructId {
390 fn from(adt_id: TypeCtorId) -> Self {
391 chalk_ir::StructId(to_chalk(adt_id))
392 }
393}
394
395/// This exists just for chalk, because our ImplIds are only unique per module.
396#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
397pub struct GlobalImplId(salsa::InternId);
398impl_intern_key!(GlobalImplId);
399
400impl From<chalk_ir::ImplId> for GlobalImplId {
401 fn from(impl_id: chalk_ir::ImplId) -> Self {
402 from_chalk(impl_id.0)
403 }
404}
405
406impl From<GlobalImplId> for chalk_ir::ImplId {
407 fn from(impl_id: GlobalImplId) -> Self {
408 chalk_ir::ImplId(to_chalk(impl_id))
409 }
410}
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index bc9170cdc..707556ef8 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -6,7 +6,7 @@ use ra_syntax::ast;
6use rustc_hash::FxHashMap; 6use rustc_hash::FxHashMap;
7 7
8use crate::{ 8use crate::{
9 ModuleDef, 9 ModuleDef, Trait,
10 code_model_api::Crate, 10 code_model_api::Crate,
11 MacroCallId, 11 MacroCallId,
12 MacroCallLoc, 12 MacroCallLoc,
@@ -18,7 +18,6 @@ use crate::{
18 expr::{scope::{ExprScopes, ScopeId}, PatId}, 18 expr::{scope::{ExprScopes, ScopeId}, PatId},
19 impl_block::ImplBlock, 19 impl_block::ImplBlock,
20 path::Path, 20 path::Path,
21 Trait,
22}; 21};
23 22
24#[derive(Debug, Clone, Default)] 23#[derive(Debug, Clone, Default)]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 094de62a3..538148956 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -15,7 +15,7 @@ pub(crate) mod display;
15use std::sync::Arc; 15use std::sync::Arc;
16use std::{fmt, mem}; 16use std::{fmt, mem};
17 17
18use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait}; 18use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
19use display::{HirDisplay, HirFormatter}; 19use display::{HirDisplay, HirFormatter};
20 20
21pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig}; 21pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig};
@@ -118,6 +118,7 @@ pub enum Ty {
118 /// surrounding impl, then the current function). 118 /// surrounding impl, then the current function).
119 idx: u32, 119 idx: u32,
120 /// The name of the parameter, for displaying. 120 /// The name of the parameter, for displaying.
121 // FIXME get rid of this
121 name: Name, 122 name: Name,
122 }, 123 },
123 124
@@ -177,6 +178,30 @@ impl Substs {
177 } 178 }
178 &self.0[0] 179 &self.0[0]
179 } 180 }
181
182 /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
183 pub fn identity(generic_params: &GenericParams) -> Substs {
184 Substs(
185 generic_params
186 .params_including_parent()
187 .into_iter()
188 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
189 .collect::<Vec<_>>()
190 .into(),
191 )
192 }
193
194 /// Return Substs that replace each parameter by a bound variable.
195 pub fn bound_vars(generic_params: &GenericParams) -> Substs {
196 Substs(
197 generic_params
198 .params_including_parent()
199 .into_iter()
200 .map(|p| Ty::Bound(p.idx))
201 .collect::<Vec<_>>()
202 .into(),
203 )
204 }
180} 205}
181 206
182impl From<Vec<Ty>> for Substs { 207impl From<Vec<Ty>> for Substs {
@@ -198,6 +223,14 @@ impl TraitRef {
198 pub fn self_ty(&self) -> &Ty { 223 pub fn self_ty(&self) -> &Ty {
199 &self.substs.0[0] 224 &self.substs.0[0]
200 } 225 }
226
227 pub fn subst(mut self, substs: &Substs) -> TraitRef {
228 self.substs.walk_mut(&mut |ty_mut| {
229 let ty = mem::replace(ty_mut, Ty::Unknown);
230 *ty_mut = ty.subst(substs);
231 });
232 self
233 }
201} 234}
202 235
203/// A function signature as seen by type inference: Several parameter types and 236/// A function signature as seen by type inference: Several parameter types and
@@ -376,6 +409,20 @@ impl Ty {
376 }) 409 })
377 } 410 }
378 411
412 /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
413 pub fn subst_bound_vars(self, substs: &Substs) -> Ty {
414 self.fold(&mut |ty| match ty {
415 Ty::Bound(idx) => {
416 if (idx as usize) < substs.0.len() {
417 substs.0[idx as usize].clone()
418 } else {
419 Ty::Bound(idx)
420 }
421 }
422 ty => ty,
423 })
424 }
425
379 /// Returns the type parameters of this type if it has some (i.e. is an ADT 426 /// Returns the type parameters of this type if it has some (i.e. is an ADT
380 /// or function); so if `self` is `Option<u32>`, this returns the `u32`. 427 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
381 fn substs(&self) -> Option<Substs> { 428 fn substs(&self) -> Option<Substs> {
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index c7772a7f6..a6d08dbcb 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -44,9 +44,13 @@ use crate::{
44}; 44};
45use super::{ 45use super::{
46 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef, 46 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
47 traits::{ Solution, Obligation, Guidance}, 47 traits::{Solution, Obligation, Guidance},
48}; 48};
49 49
50mod unify;
51
52pub(super) use unify::Canonical;
53
50/// The entry point of type inference. 54/// The entry point of type inference.
51pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { 55pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
52 db.check_canceled(); 56 db.check_canceled();
@@ -321,30 +325,27 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
321 fn resolve_obligations_as_possible(&mut self) { 325 fn resolve_obligations_as_possible(&mut self) {
322 let obligations = mem::replace(&mut self.obligations, Vec::new()); 326 let obligations = mem::replace(&mut self.obligations, Vec::new());
323 for obligation in obligations { 327 for obligation in obligations {
324 // FIXME resolve types in the obligation first 328 let mut canonicalizer = self.canonicalizer();
325 let (solution, var_mapping) = match &obligation { 329 let solution = match &obligation {
326 Obligation::Trait(tr) => { 330 Obligation::Trait(tr) => {
327 let (tr, var_mapping) = super::traits::canonicalize(tr.clone()); 331 let canonical = canonicalizer.canonicalize_trait_ref(tr.clone());
328 (self.db.implements(tr), var_mapping) 332 super::traits::implements(
333 canonicalizer.ctx.db,
334 canonicalizer.ctx.resolver.krate().unwrap(),
335 canonical,
336 )
329 } 337 }
330 }; 338 };
331 match solution { 339 match solution {
332 Some(Solution::Unique(substs)) => { 340 Some(Solution::Unique(substs)) => {
333 for (i, subst) in substs.0.iter().enumerate() { 341 canonicalizer.apply_solution(substs.0);
334 let uncanonical = var_mapping[i];
335 // FIXME the subst may contain type variables, which would need to be mapped back as well
336 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
337 }
338 } 342 }
339 Some(Solution::Ambig(Guidance::Definite(substs))) => { 343 Some(Solution::Ambig(Guidance::Definite(substs))) => {
340 for (i, subst) in substs.0.iter().enumerate() { 344 canonicalizer.apply_solution(substs.0);
341 let uncanonical = var_mapping[i];
342 // FIXME the subst may contain type variables, which would need to be mapped back as well
343 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
344 }
345 self.obligations.push(obligation); 345 self.obligations.push(obligation);
346 } 346 }
347 Some(_) => { 347 Some(_) => {
348 // FIXME use this when trying to resolve everything at the end
348 self.obligations.push(obligation); 349 self.obligations.push(obligation);
349 } 350 }
350 None => { 351 None => {
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
new file mode 100644
index 000000000..7918b007b
--- /dev/null
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -0,0 +1,81 @@
1//! Unification and canonicalization logic.
2
3use super::{InferenceContext, Ty, TraitRef, InferTy, HirDatabase};
4
5impl<'a, D: HirDatabase> InferenceContext<'a, D> {
6 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
7 where
8 'a: 'b,
9 {
10 Canonicalizer { ctx: self, free_vars: Vec::new() }
11 }
12}
13
14// TODO improve the interface of this
15
16// TODO move further up?
17#[derive(Debug, Clone, PartialEq, Eq, Hash)]
18pub(crate) struct Canonical<T> {
19 pub value: T,
20 pub num_vars: usize,
21}
22
23pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
24where
25 'a: 'b,
26{
27 pub ctx: &'b mut InferenceContext<'a, D>,
28 pub free_vars: Vec<InferTy>,
29}
30
31impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
32where
33 'a: 'b,
34{
35 fn add(&mut self, free_var: InferTy) -> usize {
36 self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
37 let next_index = self.free_vars.len();
38 self.free_vars.push(free_var);
39 next_index
40 })
41 }
42
43 pub fn canonicalize_ty(&mut self, ty: Ty) -> Canonical<Ty> {
44 let value = ty.fold(&mut |ty| match ty {
45 Ty::Infer(tv) => {
46 let inner = tv.to_inner();
47 // TODO prevent infinite loops? => keep var stack
48 if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() {
49 self.canonicalize_ty(known_ty.clone()).value
50 } else {
51 let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner));
52 let position = self.add(free_var);
53 Ty::Bound(position as u32)
54 }
55 }
56 _ => ty,
57 });
58 Canonical { value, num_vars: self.free_vars.len() }
59 }
60
61 pub fn canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> Canonical<TraitRef> {
62 let substs = trait_ref
63 .substs
64 .0
65 .iter()
66 .map(|ty| self.canonicalize_ty(ty.clone()).value)
67 .collect::<Vec<_>>();
68 let value = TraitRef { trait_: trait_ref.trait_, substs: substs.into() };
69 Canonical { value, num_vars: self.free_vars.len() }
70 }
71
72 pub fn apply_solution(&mut self, solution: Canonical<Vec<Ty>>) {
73 // the solution may contain new variables, which we need to convert to new inference vars
74 let new_vars =
75 (0..solution.num_vars).map(|_| self.ctx.new_type_var()).collect::<Vec<_>>().into();
76 for (i, ty) in solution.value.into_iter().enumerate() {
77 let var = self.free_vars[i].clone();
78 self.ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
79 }
80 }
81}
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 7fac084ce..2bbd17068 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -238,6 +238,11 @@ impl TraitRef {
238 let segment = path.segments.last().expect("path should have at least one segment"); 238 let segment = path.segments.last().expect("path should have at least one segment");
239 substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true) 239 substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true)
240 } 240 }
241
242 pub(crate) fn for_trait(db: &impl HirDatabase, trait_: Trait) -> TraitRef {
243 let substs = Substs::identity(&trait_.generic_params(db));
244 TraitRef { trait_, substs }
245 }
241} 246}
242 247
243/// Build the declared type of an item. This depends on the namespace; e.g. for 248/// Build the declared type of an item. This depends on the namespace; e.g. for
@@ -299,7 +304,7 @@ fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig {
299/// function body. 304/// function body.
300fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { 305fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty {
301 let generics = def.generic_params(db); 306 let generics = def.generic_params(db);
302 let substs = make_substs(&generics); 307 let substs = Substs::identity(&generics);
303 Ty::apply(TypeCtor::FnDef(def.into()), substs) 308 Ty::apply(TypeCtor::FnDef(def.into()), substs)
304} 309}
305 310
@@ -341,7 +346,7 @@ fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty {
341 return type_for_struct(db, def); // Unit struct 346 return type_for_struct(db, def); // Unit struct
342 } 347 }
343 let generics = def.generic_params(db); 348 let generics = def.generic_params(db);
344 let substs = make_substs(&generics); 349 let substs = Substs::identity(&generics);
345 Ty::apply(TypeCtor::FnDef(def.into()), substs) 350 Ty::apply(TypeCtor::FnDef(def.into()), substs)
346} 351}
347 352
@@ -357,7 +362,7 @@ fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant)
357 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) 362 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
358 .collect::<Vec<_>>(); 363 .collect::<Vec<_>>();
359 let generics = def.parent_enum(db).generic_params(db); 364 let generics = def.parent_enum(db).generic_params(db);
360 let substs = make_substs(&generics); 365 let substs = Substs::identity(&generics);
361 let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs); 366 let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs);
362 FnSig::from_params_and_return(params, ret) 367 FnSig::from_params_and_return(params, ret)
363} 368}
@@ -369,36 +374,25 @@ fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) ->
369 return type_for_enum(db, def.parent_enum(db)); // Unit variant 374 return type_for_enum(db, def.parent_enum(db)); // Unit variant
370 } 375 }
371 let generics = def.parent_enum(db).generic_params(db); 376 let generics = def.parent_enum(db).generic_params(db);
372 let substs = make_substs(&generics); 377 let substs = Substs::identity(&generics);
373 Ty::apply(TypeCtor::FnDef(def.into()), substs) 378 Ty::apply(TypeCtor::FnDef(def.into()), substs)
374} 379}
375 380
376fn make_substs(generics: &GenericParams) -> Substs {
377 Substs(
378 generics
379 .params_including_parent()
380 .into_iter()
381 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
382 .collect::<Vec<_>>()
383 .into(),
384 )
385}
386
387fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { 381fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty {
388 let generics = s.generic_params(db); 382 let generics = s.generic_params(db);
389 Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) 383 Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
390} 384}
391 385
392fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { 386fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty {
393 let generics = s.generic_params(db); 387 let generics = s.generic_params(db);
394 Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) 388 Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
395} 389}
396 390
397fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty { 391fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty {
398 let generics = t.generic_params(db); 392 let generics = t.generic_params(db);
399 let resolver = t.resolver(db); 393 let resolver = t.resolver(db);
400 let type_ref = t.type_ref(db); 394 let type_ref = t.type_ref(db);
401 let substs = make_substs(&generics); 395 let substs = Substs::identity(&generics);
402 let inner = Ty::from_hir(db, &resolver, &type_ref); 396 let inner = Ty::from_hir(db, &resolver, &type_ref);
403 inner.subst(&substs) 397 inner.subst(&substs)
404} 398}
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index ea6e0dc0f..ea7da0b62 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -16,7 +16,7 @@ use crate::{
16 generics::HasGenericParams, 16 generics::HasGenericParams,
17 ty::primitive::{UncertainIntTy, UncertainFloatTy} 17 ty::primitive::{UncertainIntTy, UncertainFloatTy}
18}; 18};
19use super::{TraitRef, Substs}; 19use super::{TraitRef, infer::Canonical, Substs};
20 20
21/// This is used as a key for indexing impls. 21/// This is used as a key for indexing impls.
22#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 22#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -183,6 +183,7 @@ impl Ty {
183 name: Option<&Name>, 183 name: Option<&Name>,
184 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 184 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
185 ) -> Option<T> { 185 ) -> Option<T> {
186 let krate = resolver.krate()?;
186 'traits: for t in resolver.traits_in_scope() { 187 'traits: for t in resolver.traits_in_scope() {
187 let data = t.trait_data(db); 188 let data = t.trait_data(db);
188 // we'll be lazy about checking whether the type implements the 189 // we'll be lazy about checking whether the type implements the
@@ -195,12 +196,19 @@ impl Ty {
195 let sig = m.signature(db); 196 let sig = m.signature(db);
196 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { 197 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
197 if !known_implemented { 198 if !known_implemented {
199 // TODO the self type may contain type
200 // variables, so we need to do proper
201 // canonicalization here
198 let trait_ref = TraitRef { 202 let trait_ref = TraitRef {
199 trait_: t, 203 trait_: t,
200 substs: fresh_substs_for_trait(db, t, self.clone()), 204 substs: fresh_substs_for_trait(db, t, self.clone()),
201 }; 205 };
202 let (trait_ref, _) = super::traits::canonicalize(trait_ref); 206 let canonical = Canonical {
203 if db.implements(trait_ref).is_none() { 207 num_vars: trait_ref.substs.len(),
208 value: trait_ref,
209 };
210 // FIXME cache this implements check (without solution) in a query?
211 if super::traits::implements(db, krate, canonical).is_none() {
204 continue 'traits; 212 continue 'traits;
205 } 213 }
206 } 214 }
@@ -271,15 +279,18 @@ impl Ty {
271} 279}
272 280
273/// This creates Substs for a trait with the given Self type and type variables 281/// This creates Substs for a trait with the given Self type and type variables
274/// for all other parameters. This is kind of a hack since these aren't 'real' 282/// for all other parameters, to query Chalk with it.
275/// type variables; the resulting trait reference is just used for the
276/// preliminary method candidate check.
277fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs { 283fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
278 let mut substs = Vec::new(); 284 let mut substs = Vec::new();
279 let generics = tr.generic_params(db); 285 let generics = tr.generic_params(db);
280 substs.push(self_ty); 286 substs.push(self_ty);
281 substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map( 287 substs.extend(
282 |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))), 288 generics
283 )); 289 .params_including_parent()
290 .into_iter()
291 .skip(1)
292 .enumerate()
293 .map(|(i, _p)| Ty::Bound(i as u32)),
294 );
284 substs.into() 295 substs.into()
285} 296}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index c76a5012f..0aecde37c 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2140,7 +2140,7 @@ fn test() {
2140[102; 127) '{ ...d(); }': () 2140[102; 127) '{ ...d(); }': ()
2141[108; 109) 'S': S<u32>(T) -> S<T> 2141[108; 109) 'S': S<u32>(T) -> S<T>
2142[108; 115) 'S(1u32)': S<u32> 2142[108; 115) 'S(1u32)': S<u32>
2143[108; 124) 'S(1u32...thod()': {unknown} 2143[108; 124) 'S(1u32...thod()': u32
2144[110; 114) '1u32': u32"### 2144[110; 114) '1u32': u32"###
2145 ); 2145 );
2146} 2146}
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 06f483899..367322ed2 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -1,47 +1,329 @@
1//! Stuff that will probably mostly replaced by Chalk. 1//! Chalk integration.
2use std::collections::HashMap; 2use std::sync::{Arc, Mutex};
3 3
4use crate::{db::HirDatabase, generics::HasGenericParams}; 4use chalk_ir::{TypeId, TraitId, StructId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast};
5use super::{TraitRef, Substs, infer::{TypeVarId, InferTy}, Ty}; 5use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
6 6
7// Copied (and simplified) from Chalk 7use crate::{Crate, Trait, db::HirDatabase, HasGenericParams, ImplBlock};
8use super::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, infer::Canonical};
8 9
9#[derive(Clone, Debug, PartialEq, Eq)] 10#[derive(Debug, Copy, Clone)]
10/// A (possible) solution for a proposed goal. Usually packaged in a `Result`, 11struct ChalkContext<'a, DB> {
11/// where `Err` represents definite *failure* to prove a goal. 12 db: &'a DB,
12pub enum Solution { 13 krate: Crate,
13 /// The goal indeed holds, and there is a unique value for all existential 14}
14 /// variables.
15 Unique(Substs),
16 15
17 /// The goal may be provable in multiple ways, but regardless we may have some guidance 16pub(crate) trait ToChalk {
18 /// for type inference. 17 type Chalk;
19 Ambig(Guidance), 18 fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk;
19 fn from_chalk(db: &impl HirDatabase, chalk: Self::Chalk) -> Self;
20} 20}
21 21
22#[derive(Clone, Debug, PartialEq, Eq)] 22pub(crate) fn from_chalk<T, ChalkT>(db: &impl HirDatabase, chalk: ChalkT) -> T
23/// When a goal holds ambiguously (e.g., because there are multiple possible 23where
24/// solutions), we issue a set of *guidance* back to type inference. 24 T: ToChalk<Chalk = ChalkT>,
25pub enum Guidance { 25{
26 /// The existential variables *must* have the given values if the goal is 26 T::from_chalk(db, chalk)
27 /// ever to hold, but that alone isn't enough to guarantee the goal will 27}
28 /// actually hold.
29 Definite(Substs),
30 28
31 /// There are multiple plausible values for the existentials, but the ones 29impl ToChalk for Ty {
32 /// here are suggested as the preferred choice heuristically. These should 30 type Chalk = chalk_ir::Ty;
33 /// be used for inference fallback only. 31 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Ty {
34 Suggested(Substs), 32 match self {
33 Ty::Apply(apply_ty) => chalk_ir::Ty::Apply(apply_ty.to_chalk(db)),
34 Ty::Param { idx, .. } => {
35 chalk_ir::PlaceholderIndex { ui: chalk_ir::UniverseIndex::ROOT, idx: idx as usize }
36 .to_ty()
37 }
38 Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize),
39 Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
40 Ty::Unknown => unimplemented!(), // TODO turn into placeholder?
41 }
42 }
43 fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self {
44 match chalk {
45 chalk_ir::Ty::Apply(apply_ty) => {
46 match apply_ty.name {
47 // FIXME handle TypeKindId::Trait/Type here
48 chalk_ir::TypeName::TypeKindId(_) => Ty::Apply(from_chalk(db, apply_ty)),
49 chalk_ir::TypeName::AssociatedType(_) => unimplemented!(),
50 chalk_ir::TypeName::Placeholder(idx) => {
51 assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
52 Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() }
53 }
54 }
55 }
56 chalk_ir::Ty::Projection(_) => unimplemented!(),
57 chalk_ir::Ty::UnselectedProjection(_) => unimplemented!(),
58 chalk_ir::Ty::ForAll(_) => unimplemented!(),
59 chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32),
60 chalk_ir::Ty::InferenceVar(_iv) => panic!("unexpected chalk infer ty"),
61 }
62 }
63}
35 64
36 /// There's no useful information to feed back to type inference 65impl ToChalk for ApplicationTy {
37 Unknown, 66 type Chalk = chalk_ir::ApplicationTy;
67
68 fn to_chalk(self: ApplicationTy, db: &impl HirDatabase) -> chalk_ir::ApplicationTy {
69 let struct_id = self.ctor.to_chalk(db);
70 let name = chalk_ir::TypeName::TypeKindId(struct_id.into());
71 let parameters = self.parameters.to_chalk(db);
72 chalk_ir::ApplicationTy { name, parameters }
73 }
74
75 fn from_chalk(db: &impl HirDatabase, apply_ty: chalk_ir::ApplicationTy) -> ApplicationTy {
76 let ctor = match apply_ty.name {
77 chalk_ir::TypeName::TypeKindId(chalk_ir::TypeKindId::StructId(struct_id)) => {
78 from_chalk(db, struct_id)
79 }
80 chalk_ir::TypeName::TypeKindId(_) => unimplemented!(),
81 chalk_ir::TypeName::Placeholder(_) => unimplemented!(),
82 chalk_ir::TypeName::AssociatedType(_) => unimplemented!(),
83 };
84 let parameters = from_chalk(db, apply_ty.parameters);
85 ApplicationTy { ctor, parameters }
86 }
87}
88
89impl ToChalk for Substs {
90 type Chalk = Vec<chalk_ir::Parameter>;
91
92 fn to_chalk(self, db: &impl HirDatabase) -> Vec<chalk_ir::Parameter> {
93 self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect()
94 }
95
96 fn from_chalk(db: &impl HirDatabase, parameters: Vec<chalk_ir::Parameter>) -> Substs {
97 parameters
98 .into_iter()
99 .map(|p| match p {
100 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
101 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
102 })
103 .collect::<Vec<_>>()
104 .into()
105 }
106}
107
108impl ToChalk for TraitRef {
109 type Chalk = chalk_ir::TraitRef;
110
111 fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef {
112 let trait_id = self.trait_.to_chalk(db);
113 let parameters = self.substs.to_chalk(db);
114 chalk_ir::TraitRef { trait_id, parameters }
115 }
116
117 fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef) -> Self {
118 let trait_ = from_chalk(db, trait_ref.trait_id);
119 let substs = from_chalk(db, trait_ref.parameters);
120 TraitRef { trait_, substs }
121 }
122}
123
124impl ToChalk for Trait {
125 type Chalk = TraitId;
126
127 fn to_chalk(self, _db: &impl HirDatabase) -> TraitId {
128 self.id.into()
129 }
130
131 fn from_chalk(_db: &impl HirDatabase, trait_id: TraitId) -> Trait {
132 Trait { id: trait_id.into() }
133 }
134}
135
136impl ToChalk for TypeCtor {
137 type Chalk = chalk_ir::StructId;
138
139 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::StructId {
140 db.intern_type_ctor(self).into()
141 }
142
143 fn from_chalk(db: &impl HirDatabase, struct_id: chalk_ir::StructId) -> TypeCtor {
144 db.lookup_intern_type_ctor(struct_id.into())
145 }
146}
147
148impl ToChalk for ImplBlock {
149 type Chalk = chalk_ir::ImplId;
150
151 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ImplId {
152 db.intern_impl_block(self).into()
153 }
154
155 fn from_chalk(db: &impl HirDatabase, impl_id: chalk_ir::ImplId) -> ImplBlock {
156 db.lookup_intern_impl_block(impl_id.into())
157 }
158}
159
160fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
161 chalk_ir::Binders {
162 value,
163 binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
164 }
165}
166
167impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
168where
169 DB: HirDatabase,
170{
171 fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> {
172 unimplemented!()
173 }
174 fn trait_datum(&self, trait_id: TraitId) -> Arc<TraitDatum> {
175 eprintln!("trait_datum {:?}", trait_id);
176 let trait_: Trait = from_chalk(self.db, trait_id);
177 let generic_params = trait_.generic_params(self.db);
178 let bound_vars = Substs::bound_vars(&generic_params);
179 let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db);
180 let flags = chalk_rust_ir::TraitFlags {
181 // FIXME set these flags correctly
182 auto: false,
183 marker: false,
184 upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
185 fundamental: false,
186 };
187 let where_clauses = Vec::new(); // FIXME add where clauses
188 let trait_datum_bound = chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags };
189 let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) };
190 Arc::new(trait_datum)
191 }
192 fn struct_datum(&self, struct_id: StructId) -> Arc<StructDatum> {
193 eprintln!("struct_datum {:?}", struct_id);
194 let type_ctor = from_chalk(self.db, struct_id);
195 // TODO might be nicer if we can create a fake GenericParams for the TypeCtor
196 let (num_params, upstream) = match type_ctor {
197 TypeCtor::Bool
198 | TypeCtor::Char
199 | TypeCtor::Int(_)
200 | TypeCtor::Float(_)
201 | TypeCtor::Never
202 | TypeCtor::Str => (0, true),
203 TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true),
204 TypeCtor::FnPtr | TypeCtor::Tuple => unimplemented!(), // FIXME tuples and FnPtr are currently variadic... we need to make the parameter number explicit
205 TypeCtor::FnDef(_) => unimplemented!(),
206 TypeCtor::Adt(adt) => {
207 let generic_params = adt.generic_params(self.db);
208 (
209 generic_params.count_params_including_parent(),
210 adt.krate(self.db) != Some(self.krate),
211 )
212 }
213 };
214 let flags = chalk_rust_ir::StructFlags {
215 upstream,
216 // FIXME set fundamental flag correctly
217 fundamental: false,
218 };
219 let where_clauses = Vec::new(); // FIXME add where clauses
220 let ty = ApplicationTy {
221 ctor: type_ctor,
222 parameters: (0..num_params).map(|i| Ty::Bound(i as u32)).collect::<Vec<_>>().into(),
223 };
224 let struct_datum_bound = chalk_rust_ir::StructDatumBound {
225 self_ty: ty.to_chalk(self.db),
226 fields: Vec::new(), // FIXME add fields (only relevant for auto traits)
227 where_clauses,
228 flags,
229 };
230 let struct_datum = StructDatum { binders: make_binders(struct_datum_bound, num_params) };
231 Arc::new(struct_datum)
232 }
233 fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
234 eprintln!("impl_datum {:?}", impl_id);
235 let impl_block: ImplBlock = from_chalk(self.db, impl_id);
236 let generic_params = impl_block.generic_params(self.db);
237 let bound_vars = Substs::bound_vars(&generic_params);
238 let trait_ref = impl_block
239 .target_trait_ref(self.db)
240 .expect("FIXME handle unresolved impl block trait ref")
241 .subst(&bound_vars);
242 let impl_type = if impl_block.module().krate(self.db) == Some(self.krate) {
243 chalk_rust_ir::ImplType::Local
244 } else {
245 chalk_rust_ir::ImplType::External
246 };
247 let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
248 // FIXME handle negative impls (impl !Sync for Foo)
249 trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)),
250 where_clauses: Vec::new(), // FIXME add where clauses
251 associated_ty_values: Vec::new(), // FIXME add associated type values
252 impl_type,
253 };
254 let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) };
255 Arc::new(impl_datum)
256 }
257 fn impls_for_trait(&self, trait_id: TraitId) -> Vec<ImplId> {
258 eprintln!("impls_for_trait {:?}", trait_id);
259 let trait_ = from_chalk(self.db, trait_id);
260 self.db
261 .impls_for_trait(self.krate, trait_)
262 .iter()
263 // FIXME temporary hack -- as long as we're not lowering where clauses
264 // correctly, ignore impls with them completely so as to not treat
265 // impl<T> Trait for T where T: ... as a blanket impl on all types
266 .filter(|impl_block| impl_block.generic_params(self.db).where_predicates.is_empty())
267 .map(|impl_block| impl_block.to_chalk(self.db))
268 .collect()
269 }
270 fn impl_provided_for(&self, auto_trait_id: TraitId, struct_id: StructId) -> bool {
271 eprintln!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id);
272 false // FIXME
273 }
274 fn type_name(&self, _id: TypeKindId) -> Identifier {
275 unimplemented!()
276 }
277 fn split_projection<'p>(
278 &self,
279 projection: &'p ProjectionTy,
280 ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) {
281 eprintln!("split_projection {:?}", projection);
282 unimplemented!()
283 }
284}
285
286pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<chalk_solve::Solver>> {
287 // krate parameter is just so we cache a unique solver per crate
288 let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 };
289 Arc::new(Mutex::new(solver_choice.into_solver()))
290}
291
292/// Collects impls for the given trait in the whole dependency tree of `krate`.
293pub(crate) fn impls_for_trait(
294 db: &impl HirDatabase,
295 krate: Crate,
296 trait_: Trait,
297) -> Arc<[ImplBlock]> {
298 let mut impls = Vec::new();
299 // We call the query recursively here. On the one hand, this means we can
300 // reuse results from queries for different crates; on the other hand, this
301 // will only ever get called for a few crates near the root of the tree (the
302 // ones the user is editing), so this may actually be a waste of memory. I'm
303 // doing it like this mainly for simplicity for now.
304 for dep in krate.dependencies(db) {
305 impls.extend(db.impls_for_trait(dep.krate, trait_).iter());
306 }
307 let crate_impl_blocks = db.impls_in_crate(krate);
308 impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_));
309 impls.into()
310}
311
312fn solve(
313 db: &impl HirDatabase,
314 krate: Crate,
315 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal>>,
316) -> Option<chalk_solve::Solution> {
317 let context = ChalkContext { db, krate };
318 let solver = db.chalk_solver(krate);
319 let solution = solver.lock().unwrap().solve(&context, goal);
320 eprintln!("solve({:?}) => {:?}", goal, solution);
321 solution
38} 322}
39 323
40/// Something that needs to be proven (by Chalk) during type checking, e.g. that 324/// Something that needs to be proven (by Chalk) during type checking, e.g. that
41/// a certain type implements a certain trait. Proving the Obligation might 325/// a certain type implements a certain trait. Proving the Obligation might
42/// result in additional information about inference variables. 326/// result in additional information about inference variables.
43///
44/// This might be handled by Chalk when we integrate it?
45#[derive(Clone, Debug, PartialEq, Eq)] 327#[derive(Clone, Debug, PartialEq, Eq)]
46pub enum Obligation { 328pub enum Obligation {
47 /// Prove that a certain type implements a trait (the type is the `Self` type 329 /// Prove that a certain type implements a trait (the type is the `Self` type
@@ -49,67 +331,98 @@ pub enum Obligation {
49 Trait(TraitRef), 331 Trait(TraitRef),
50} 332}
51 333
52/// Rudimentary check whether an impl exists for a given type and trait; this 334/// Check using Chalk whether trait is implemented for given parameters including `Self` type.
53/// will actually be done by chalk. 335pub(crate) fn implements(
54pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> { 336 db: &impl HirDatabase,
55 // FIXME use all trait impls in the whole crate graph 337 krate: Crate,
56 let krate = trait_ref.trait_.module(db).krate(db); 338 trait_ref: Canonical<TraitRef>,
57 let krate = match krate { 339) -> Option<Solution> {
58 Some(krate) => krate, 340 let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast();
59 None => return None, 341 eprintln!("goal: {:?}", goal);
60 }; 342 let env = chalk_ir::Environment::new();
61 let crate_impl_blocks = db.impls_in_crate(krate); 343 let in_env = chalk_ir::InEnvironment::new(&env, goal);
62 let mut impl_blocks = crate_impl_blocks 344 let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT);
63 .lookup_impl_blocks_for_trait(&trait_ref.trait_) 345 let canonical =
64 // we don't handle where clauses at all, waiting for Chalk for that 346 chalk_ir::Canonical { value: in_env, binders: vec![parameter; trait_ref.num_vars] };
65 .filter(|impl_block| impl_block.generic_params(db).where_predicates.is_empty()); 347 // We currently don't deal with universes (I think / hope they're not yet
66 impl_blocks 348 // relevant for our use cases?)
67 .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?)) 349 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
68} 350 let solution = solve(db, krate, &u_canonical);
69 351 solution_from_chalk(db, solution)
70pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) {
71 let mut canonical = HashMap::new(); // mapping uncanonical -> canonical
72 let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense)
73 let mut substs = trait_ref.substs.0.to_vec();
74 for ty in &mut substs {
75 ty.walk_mut(&mut |ty| match ty {
76 Ty::Infer(InferTy::TypeVar(tv)) => {
77 let tv: &mut TypeVarId = tv;
78 *tv = *canonical.entry(*tv).or_insert_with(|| {
79 let i = uncanonical.len();
80 uncanonical.push(*tv);
81 TypeVarId(i as u32)
82 });
83 }
84 _ => {}
85 });
86 }
87 (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
88} 352}
89 353
90fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> { 354fn solution_from_chalk(
91 if tr1.trait_ != tr2.trait_ { 355 db: &impl HirDatabase,
92 return None; 356 solution: Option<chalk_solve::Solution>,
93 } 357) -> Option<Solution> {
94 let mut solution_substs = Vec::new(); 358 let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
95 for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) { 359 let value = subst
96 // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass 360 .value
97 match (t1, t2) { 361 .parameters
98 (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => { 362 .into_iter()
99 // type variable (or similar) in the impl, we just assume it works 363 .map(|p| {
100 } 364 let ty = match p {
101 (Ty::Infer(InferTy::TypeVar(v1)), _) => { 365 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
102 // type variable in the query and fixed type in the impl, record its value 366 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
103 solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown); 367 };
104 solution_substs[v1.0 as usize] = t2.clone(); 368 ty
105 } 369 })
106 _ => { 370 .collect();
107 // check that they're equal (actually we'd have to recurse etc.) 371 let result = Canonical { value, num_vars: subst.binders.len() };
108 if t1 != t2 { 372 SolutionVariables(result)
109 return None; 373 };
110 } 374 match solution {
111 } 375 Some(chalk_solve::Solution::Unique(constr_subst)) => {
376 let subst = chalk_ir::Canonical {
377 value: constr_subst.value.subst,
378 binders: constr_subst.binders,
379 };
380 Some(Solution::Unique(convert_subst(subst)))
381 }
382 Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst))) => {
383 Some(Solution::Ambig(Guidance::Definite(convert_subst(subst))))
384 }
385 Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst))) => {
386 Some(Solution::Ambig(Guidance::Suggested(convert_subst(subst))))
112 } 387 }
388 Some(chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown)) => {
389 Some(Solution::Ambig(Guidance::Unknown))
390 }
391 None => None,
113 } 392 }
114 Some(Solution::Unique(solution_substs.into())) 393}
394
395#[derive(Clone, Debug, PartialEq, Eq)]
396pub(crate) struct SolutionVariables(pub Canonical<Vec<Ty>>);
397
398#[derive(Clone, Debug, PartialEq, Eq)]
399/// A (possible) solution for a proposed goal.
400pub(crate) enum Solution {
401 /// The goal indeed holds, and there is a unique value for all existential
402 /// variables.
403 Unique(SolutionVariables),
404
405 /// The goal may be provable in multiple ways, but regardless we may have some guidance
406 /// for type inference. In this case, we don't return any lifetime
407 /// constraints, since we have not "committed" to any particular solution
408 /// yet.
409 Ambig(Guidance),
410}
411
412#[derive(Clone, Debug, PartialEq, Eq)]
413/// When a goal holds ambiguously (e.g., because there are multiple possible
414/// solutions), we issue a set of *guidance* back to type inference.
415pub(crate) enum Guidance {
416 /// The existential variables *must* have the given values if the goal is
417 /// ever to hold, but that alone isn't enough to guarantee the goal will
418 /// actually hold.
419 Definite(SolutionVariables),
420
421 /// There are multiple plausible values for the existentials, but the ones
422 /// here are suggested as the preferred choice heuristically. These should
423 /// be used for inference fallback only.
424 Suggested(SolutionVariables),
425
426 /// There's no useful information to feed back to type inference
427 Unknown,
115} 428}