aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir
diff options
context:
space:
mode:
authorbors[bot] <bors[bot]@users.noreply.github.com>2019-04-14 15:06:48 +0100
committerbors[bot] <bors[bot]@users.noreply.github.com>2019-04-14 15:06:48 +0100
commitfcbd0269545f2b6687a64a868654c74f876b7851 (patch)
treecb439cc77b5445f00cda86e932c199cb69ae47d6 /crates/ra_hir
parent23b876bc3b00c53ce24b8a99b4f4bf190fc6300e (diff)
parent8bcbcc454cbb48b897083c122566c0b4c2b780aa (diff)
Merge #1120
1120: More trait infrastructure r=matklad a=flodiebold This adds enough trait infrastructure to be able to make some deductions about type variables when resolving trait methods, while at the same time doing as little as possible that will be later replaced by Chalk :smile: E.g. (as the tests show) if we have ```rust trait Trait<T> { fn method(self) -> T } impl Trait<u32> for S {} ... S.method() ``` we can infer that the return type is `u32`. On the other hand the unification logic is so primitive that we can't handle e.g. `impl<T> Trait<T> for S<T>`. It's all quite hacky, I plan to refactor the parts that will stay, while hopefully the other parts will be replaced soon :slightly_smiling_face: In particular, we need to handle 'containers' (impls and trait defs) more cleanly, and I need to reorganize the method resolution / type inference code... Co-authored-by: Florian Diebold <[email protected]>
Diffstat (limited to 'crates/ra_hir')
-rw-r--r--crates/ra_hir/src/code_model_api.rs84
-rw-r--r--crates/ra_hir/src/db.rs7
-rw-r--r--crates/ra_hir/src/generics.rs37
-rw-r--r--crates/ra_hir/src/impl_block.rs30
-rw-r--r--crates/ra_hir/src/lib.rs5
-rw-r--r--crates/ra_hir/src/traits.rs33
-rw-r--r--crates/ra_hir/src/ty.rs33
-rw-r--r--crates/ra_hir/src/ty/infer.rs243
-rw-r--r--crates/ra_hir/src/ty/lower.rs109
-rw-r--r--crates/ra_hir/src/ty/method_resolution.rs58
-rw-r--r--crates/ra_hir/src/ty/tests.rs51
-rw-r--r--crates/ra_hir/src/ty/traits.rs112
12 files changed, 582 insertions, 220 deletions
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 5d8cf57b6..8f1ed1086 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -11,7 +11,7 @@ use crate::{
11 expr::{Body, BodySourceMap}, 11 expr::{Body, BodySourceMap},
12 ty::InferenceResult, 12 ty::InferenceResult,
13 adt::{EnumVariantId, StructFieldId, VariantDef}, 13 adt::{EnumVariantId, StructFieldId, VariantDef},
14 generics::GenericParams, 14 generics::HasGenericParams,
15 docs::{Documentation, Docs, docs_from_ast}, 15 docs::{Documentation, Docs, docs_from_ast},
16 ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeAliasId}, 16 ids::{FunctionId, StructId, EnumId, AstItemDef, ConstId, StaticId, TraitId, TypeAliasId},
17 impl_block::ImplBlock, 17 impl_block::ImplBlock,
@@ -189,12 +189,12 @@ impl Module {
189 } 189 }
190 } 190 }
191 191
192 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver { 192 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
193 let def_map = db.crate_def_map(self.krate); 193 let def_map = db.crate_def_map(self.krate);
194 Resolver::default().push_module_scope(def_map, self.module_id) 194 Resolver::default().push_module_scope(def_map, self.module_id)
195 } 195 }
196 196
197 pub fn declarations(self, db: &impl HirDatabase) -> Vec<ModuleDef> { 197 pub fn declarations(self, db: &impl DefDatabase) -> Vec<ModuleDef> {
198 let def_map = db.crate_def_map(self.krate); 198 let def_map = db.crate_def_map(self.krate);
199 def_map[self.module_id] 199 def_map[self.module_id]
200 .scope 200 .scope
@@ -299,10 +299,6 @@ impl Struct {
299 .map(|(id, _)| StructField { parent: (*self).into(), id }) 299 .map(|(id, _)| StructField { parent: (*self).into(), id })
300 } 300 }
301 301
302 pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
303 db.generic_params((*self).into())
304 }
305
306 pub fn ty(&self, db: &impl HirDatabase) -> Ty { 302 pub fn ty(&self, db: &impl HirDatabase) -> Ty {
307 db.type_for_def((*self).into(), Namespace::Types) 303 db.type_for_def((*self).into(), Namespace::Types)
308 } 304 }
@@ -363,10 +359,6 @@ impl Enum {
363 .map(|(id, _)| EnumVariant { parent: *self, id }) 359 .map(|(id, _)| EnumVariant { parent: *self, id })
364 } 360 }
365 361
366 pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
367 db.generic_params((*self).into())
368 }
369
370 pub fn ty(&self, db: &impl HirDatabase) -> Ty { 362 pub fn ty(&self, db: &impl HirDatabase) -> Ty {
371 db.type_for_def((*self).into(), Namespace::Types) 363 db.type_for_def((*self).into(), Namespace::Types)
372 } 364 }
@@ -537,24 +529,32 @@ impl Function {
537 db.infer((*self).into()) 529 db.infer((*self).into())
538 } 530 }
539 531
540 pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
541 db.generic_params((*self).into())
542 }
543
544 /// The containing impl block, if this is a method. 532 /// The containing impl block, if this is a method.
545 pub fn impl_block(&self, db: &impl DefDatabase) -> Option<ImplBlock> { 533 pub fn impl_block(&self, db: &impl DefDatabase) -> Option<ImplBlock> {
546 let module_impls = db.impls_in_module(self.module(db)); 534 let module_impls = db.impls_in_module(self.module(db));
547 ImplBlock::containing(module_impls, (*self).into()) 535 ImplBlock::containing(module_impls, (*self).into())
548 } 536 }
549 537
538 /// The containing trait, if this is a trait method definition.
539 pub fn parent_trait(&self, db: &impl DefDatabase) -> Option<Trait> {
540 db.trait_items_index(self.module(db)).get_parent_trait((*self).into())
541 }
542
543 pub fn container(&self, db: &impl DefDatabase) -> Option<Container> {
544 if let Some(impl_block) = self.impl_block(db) {
545 Some(impl_block.into())
546 } else if let Some(trait_) = self.parent_trait(db) {
547 Some(trait_.into())
548 } else {
549 None
550 }
551 }
552
550 // FIXME: move to a more general type for 'body-having' items 553 // FIXME: move to a more general type for 'body-having' items
551 /// Builds a resolver for code inside this item. 554 /// Builds a resolver for code inside this item.
552 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver { 555 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver {
553 // take the outer scope... 556 // take the outer scope...
554 let r = self 557 let r = self.container(db).map_or_else(|| self.module(db).resolver(db), |c| c.resolver(db));
555 .impl_block(db)
556 .map(|ib| ib.resolver(db))
557 .unwrap_or_else(|| self.module(db).resolver(db));
558 // ...and add generic params, if present 558 // ...and add generic params, if present
559 let p = self.generic_params(db); 559 let p = self.generic_params(db);
560 let r = if !p.params.is_empty() { r.push_generic_params_scope(p) } else { r }; 560 let r = if !p.params.is_empty() { r.push_generic_params_scope(p) } else { r };
@@ -684,10 +684,6 @@ impl Trait {
684 self.id.module(db) 684 self.id.module(db)
685 } 685 }
686 686
687 pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
688 db.generic_params((*self).into())
689 }
690
691 pub fn name(self, db: &impl DefDatabase) -> Option<Name> { 687 pub fn name(self, db: &impl DefDatabase) -> Option<Name> {
692 self.trait_data(db).name().clone() 688 self.trait_data(db).name().clone()
693 } 689 }
@@ -699,6 +695,14 @@ impl Trait {
699 pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> { 695 pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
700 db.trait_data(self) 696 db.trait_data(self)
701 } 697 }
698
699 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
700 let r = self.module(db).resolver(db);
701 // add generic params, if present
702 let p = self.generic_params(db);
703 let r = if !p.params.is_empty() { r.push_generic_params_scope(p) } else { r };
704 r
705 }
702} 706}
703 707
704impl Docs for Trait { 708impl Docs for Trait {
@@ -717,10 +721,6 @@ impl TypeAlias {
717 self.id.source(db) 721 self.id.source(db)
718 } 722 }
719 723
720 pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
721 db.generic_params((*self).into())
722 }
723
724 pub fn module(&self, db: &impl DefDatabase) -> Module { 724 pub fn module(&self, db: &impl DefDatabase) -> Module {
725 self.id.module(db) 725 self.id.module(db)
726 } 726 }
@@ -731,6 +731,21 @@ impl TypeAlias {
731 ImplBlock::containing(module_impls, (*self).into()) 731 ImplBlock::containing(module_impls, (*self).into())
732 } 732 }
733 733
734 /// The containing trait, if this is a trait method definition.
735 pub fn parent_trait(&self, db: &impl DefDatabase) -> Option<Trait> {
736 db.trait_items_index(self.module(db)).get_parent_trait((*self).into())
737 }
738
739 pub fn container(&self, db: &impl DefDatabase) -> Option<Container> {
740 if let Some(impl_block) = self.impl_block(db) {
741 Some(impl_block.into())
742 } else if let Some(trait_) = self.parent_trait(db) {
743 Some(trait_.into())
744 } else {
745 None
746 }
747 }
748
734 pub fn type_ref(self, db: &impl DefDatabase) -> Arc<TypeRef> { 749 pub fn type_ref(self, db: &impl DefDatabase) -> Arc<TypeRef> {
735 db.type_alias_ref(self) 750 db.type_alias_ref(self)
736 } 751 }
@@ -754,3 +769,18 @@ impl Docs for TypeAlias {
754 docs_from_ast(&*self.source(db).1) 769 docs_from_ast(&*self.source(db).1)
755 } 770 }
756} 771}
772
773pub enum Container {
774 Trait(Trait),
775 ImplBlock(ImplBlock),
776}
777impl_froms!(Container: Trait, ImplBlock);
778
779impl Container {
780 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
781 match self {
782 Container::Trait(trait_) => trait_.resolver(db),
783 Container::ImplBlock(impl_block) => impl_block.resolver(db),
784 }
785 }
786}
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index e23e2bb2b..18627bbc2 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -53,6 +53,9 @@ pub trait DefDatabase: SourceDatabase {
53 #[salsa::invoke(crate::traits::TraitData::trait_data_query)] 53 #[salsa::invoke(crate::traits::TraitData::trait_data_query)]
54 fn trait_data(&self, t: Trait) -> Arc<TraitData>; 54 fn trait_data(&self, t: Trait) -> Arc<TraitData>;
55 55
56 #[salsa::invoke(crate::traits::TraitItemsIndex::trait_items_index)]
57 fn trait_items_index(&self, module: Module) -> crate::traits::TraitItemsIndex;
58
56 #[salsa::invoke(crate::source_id::AstIdMap::ast_id_map_query)] 59 #[salsa::invoke(crate::source_id::AstIdMap::ast_id_map_query)]
57 fn ast_id_map(&self, file_id: HirFileId) -> Arc<AstIdMap>; 60 fn ast_id_map(&self, file_id: HirFileId) -> Arc<AstIdMap>;
58 61
@@ -128,8 +131,8 @@ pub trait HirDatabase: DefDatabase {
128 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] 131 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
129 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>; 132 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
130 133
131 #[salsa::invoke(crate::ty::method_resolution::implements)] 134 #[salsa::invoke(crate::ty::traits::implements)]
132 fn implements(&self, trait_ref: TraitRef) -> bool; 135 fn implements(&self, trait_ref: TraitRef) -> Option<crate::ty::traits::Solution>;
133} 136}
134 137
135#[test] 138#[test]
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 84fe94289..5625c2459 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};
9 9
10use crate::{ 10use crate::{
11 db::DefDatabase, 11 db::DefDatabase,
12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock 12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container
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, ...).
@@ -27,6 +27,7 @@ pub struct GenericParams {
27 pub(crate) params: Vec<GenericParam>, 27 pub(crate) params: Vec<GenericParam>,
28} 28}
29 29
30// FIXME: consts can have type parameters from their parents (i.e. associated consts of traits)
30#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)] 31#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
31pub enum GenericDef { 32pub enum GenericDef {
32 Function(Function), 33 Function(Function),
@@ -45,18 +46,22 @@ impl GenericParams {
45 ) -> Arc<GenericParams> { 46 ) -> Arc<GenericParams> {
46 let mut generics = GenericParams::default(); 47 let mut generics = GenericParams::default();
47 let parent = match def { 48 let parent = match def {
48 GenericDef::Function(it) => it.impl_block(db), 49 GenericDef::Function(it) => it.container(db).map(GenericDef::from),
49 GenericDef::TypeAlias(it) => it.impl_block(db), 50 GenericDef::TypeAlias(it) => it.container(db).map(GenericDef::from),
50 GenericDef::Struct(_) | GenericDef::Enum(_) | GenericDef::Trait(_) => None, 51 GenericDef::Struct(_) | GenericDef::Enum(_) | GenericDef::Trait(_) => None,
51 GenericDef::ImplBlock(_) => None, 52 GenericDef::ImplBlock(_) => None,
52 }; 53 };
53 generics.parent_params = parent.map(|p| p.generic_params(db)); 54 generics.parent_params = parent.map(|p| db.generic_params(p));
54 let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32; 55 let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32;
55 match def { 56 match def {
56 GenericDef::Function(it) => generics.fill(&*it.source(db).1, start), 57 GenericDef::Function(it) => generics.fill(&*it.source(db).1, start),
57 GenericDef::Struct(it) => generics.fill(&*it.source(db).1, start), 58 GenericDef::Struct(it) => generics.fill(&*it.source(db).1, start),
58 GenericDef::Enum(it) => generics.fill(&*it.source(db).1, start), 59 GenericDef::Enum(it) => generics.fill(&*it.source(db).1, start),
59 GenericDef::Trait(it) => generics.fill(&*it.source(db).1, start), 60 GenericDef::Trait(it) => {
61 // traits get the Self type as an implicit first type parameter
62 generics.params.push(GenericParam { idx: start, name: Name::self_type() });
63 generics.fill(&*it.source(db).1, start + 1);
64 }
60 GenericDef::TypeAlias(it) => generics.fill(&*it.source(db).1, start), 65 GenericDef::TypeAlias(it) => generics.fill(&*it.source(db).1, start),
61 GenericDef::ImplBlock(it) => generics.fill(&*it.source(db).1, start), 66 GenericDef::ImplBlock(it) => generics.fill(&*it.source(db).1, start),
62 } 67 }
@@ -104,3 +109,25 @@ impl GenericParams {
104 vec 109 vec
105 } 110 }
106} 111}
112
113impl From<Container> for GenericDef {
114 fn from(c: Container) -> Self {
115 match c {
116 Container::Trait(trait_) => trait_.into(),
117 Container::ImplBlock(impl_block) => impl_block.into(),
118 }
119 }
120}
121
122pub trait HasGenericParams {
123 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>;
124}
125
126impl<T> HasGenericParams for T
127where
128 T: Into<GenericDef>,
129{
130 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams> {
131 db.generic_params(self.into())
132 }
133}
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index b306874cc..a8a466e43 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -9,16 +9,15 @@ use ra_syntax::{
9 9
10use crate::{ 10use crate::{
11 Const, TypeAlias, Function, HirFileId, 11 Const, TypeAlias, Function, HirFileId,
12 HirDatabase, DefDatabase, 12 HirDatabase, DefDatabase, TraitRef,
13 ModuleDef, Trait, Resolution,
14 type_ref::TypeRef, 13 type_ref::TypeRef,
15 ids::LocationCtx, 14 ids::LocationCtx,
16 resolve::Resolver, 15 resolve::Resolver,
17 ty::Ty, generics::GenericParams, 16 ty::Ty,
17 generics::HasGenericParams,
18 code_model_api::{Module, ModuleSource}
18}; 19};
19 20
20use crate::code_model_api::{Module, ModuleSource};
21
22#[derive(Debug, Default, PartialEq, Eq)] 21#[derive(Debug, Default, PartialEq, Eq)]
23pub struct ImplSourceMap { 22pub struct ImplSourceMap {
24 map: ArenaMap<ImplId, AstPtr<ast::ImplBlock>>, 23 map: ArenaMap<ImplId, AstPtr<ast::ImplBlock>>,
@@ -73,7 +72,7 @@ impl ImplBlock {
73 self.module 72 self.module
74 } 73 }
75 74
76 pub fn target_trait_ref(&self, db: &impl DefDatabase) -> Option<TypeRef> { 75 pub fn target_trait(&self, db: &impl DefDatabase) -> Option<TypeRef> {
77 db.impls_in_module(self.module).impls[self.impl_id].target_trait().cloned() 76 db.impls_in_module(self.module).impls[self.impl_id].target_trait().cloned()
78 } 77 }
79 78
@@ -85,27 +84,16 @@ impl ImplBlock {
85 Ty::from_hir(db, &self.resolver(db), &self.target_type(db)) 84 Ty::from_hir(db, &self.resolver(db), &self.target_type(db))
86 } 85 }
87 86
88 pub fn target_trait(&self, db: &impl HirDatabase) -> Option<Trait> { 87 pub fn target_trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
89 if let Some(TypeRef::Path(path)) = self.target_trait_ref(db) { 88 let target_ty = self.target_ty(db);
90 let resolver = self.resolver(db); 89 TraitRef::from_hir(db, &self.resolver(db), &self.target_trait(db)?, Some(target_ty))
91 if let Some(Resolution::Def(ModuleDef::Trait(tr))) =
92 resolver.resolve_path(db, &path).take_types()
93 {
94 return Some(tr);
95 }
96 }
97 None
98 } 90 }
99 91
100 pub fn items(&self, db: &impl DefDatabase) -> Vec<ImplItem> { 92 pub fn items(&self, db: &impl DefDatabase) -> Vec<ImplItem> {
101 db.impls_in_module(self.module).impls[self.impl_id].items().to_vec() 93 db.impls_in_module(self.module).impls[self.impl_id].items().to_vec()
102 } 94 }
103 95
104 pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> { 96 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
105 db.generic_params((*self).into())
106 }
107
108 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver {
109 let r = self.module().resolver(db); 97 let r = self.module().resolver(db);
110 // add generic params, if present 98 // add generic params, if present
111 let p = self.generic_params(db); 99 let p = self.generic_params(db);
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index a9db23060..9292de1b5 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -61,12 +61,13 @@ pub use self::{
61 source_id::{AstIdMap, ErasedFileAstId}, 61 source_id::{AstIdMap, ErasedFileAstId},
62 ids::{HirFileId, MacroDefId, MacroCallId, MacroCallLoc}, 62 ids::{HirFileId, MacroDefId, MacroCallId, MacroCallLoc},
63 nameres::{PerNs, Namespace, ImportId}, 63 nameres::{PerNs, Namespace, ImportId},
64 ty::{Ty, ApplicationTy, TypeCtor, Substs, display::HirDisplay, CallableDef}, 64 ty::{Ty, ApplicationTy, TypeCtor, TraitRef, Substs, display::HirDisplay, CallableDef},
65 impl_block::{ImplBlock, ImplItem}, 65 impl_block::{ImplBlock, ImplItem},
66 docs::{Docs, Documentation}, 66 docs::{Docs, Documentation},
67 adt::AdtDef, 67 adt::AdtDef,
68 expr::ExprScopes, 68 expr::ExprScopes,
69 resolve::Resolution, 69 resolve::Resolution,
70 generics::{GenericParams, GenericParam, HasGenericParams},
70 source_binder::{SourceAnalyzer, PathResolution, ScopeEntryWithSyntax}, 71 source_binder::{SourceAnalyzer, PathResolution, ScopeEntryWithSyntax},
71}; 72};
72 73
@@ -78,5 +79,5 @@ pub use self::code_model_api::{
78 Function, FnSignature, 79 Function, FnSignature,
79 StructField, FieldSource, 80 StructField, FieldSource,
80 Static, Const, ConstSignature, 81 Static, Const, ConstSignature,
81 Trait, TypeAlias, 82 Trait, TypeAlias, Container,
82}; 83};
diff --git a/crates/ra_hir/src/traits.rs b/crates/ra_hir/src/traits.rs
index 725bdd5cb..15f0977b7 100644
--- a/crates/ra_hir/src/traits.rs
+++ b/crates/ra_hir/src/traits.rs
@@ -1,10 +1,11 @@
1//! HIR for trait definitions. 1//! HIR for trait definitions.
2 2
3use std::sync::Arc; 3use std::sync::Arc;
4use rustc_hash::FxHashMap;
4 5
5use ra_syntax::ast::{self, NameOwner}; 6use ra_syntax::ast::{self, NameOwner};
6 7
7use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationCtx, name::AsName}; 8use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationCtx, name::AsName, Module};
8 9
9#[derive(Debug, Clone, PartialEq, Eq)] 10#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct TraitData { 11pub struct TraitData {
@@ -49,4 +50,34 @@ pub enum TraitItem {
49 TypeAlias(TypeAlias), 50 TypeAlias(TypeAlias),
50 // Existential 51 // Existential
51} 52}
53// FIXME: not every function, ... is actually a trait item. maybe we should make
54// sure that you can only turn actual trait items into TraitItems. This would
55// require not implementing From, and instead having some checked way of
56// casting them.
52impl_froms!(TraitItem: Function, Const, TypeAlias); 57impl_froms!(TraitItem: Function, Const, TypeAlias);
58
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct TraitItemsIndex {
61 traits_by_def: FxHashMap<TraitItem, Trait>,
62}
63
64impl TraitItemsIndex {
65 pub(crate) fn trait_items_index(db: &impl DefDatabase, module: Module) -> TraitItemsIndex {
66 let mut index = TraitItemsIndex { traits_by_def: FxHashMap::default() };
67 for decl in module.declarations(db) {
68 match decl {
69 crate::ModuleDef::Trait(tr) => {
70 for item in tr.trait_data(db).items() {
71 index.traits_by_def.insert(*item, tr);
72 }
73 }
74 _ => {}
75 }
76 }
77 index
78 }
79
80 pub(crate) fn get_parent_trait(&self, item: TraitItem) -> Option<Trait> {
81 self.traits_by_def.get(&item).cloned()
82 }
83}
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index ecf13fbc3..12e10c751 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -5,6 +5,7 @@ mod autoderef;
5pub(crate) mod primitive; 5pub(crate) mod primitive;
6#[cfg(test)] 6#[cfg(test)]
7mod tests; 7mod tests;
8pub(crate) mod traits;
8pub(crate) mod method_resolution; 9pub(crate) mod method_resolution;
9mod op; 10mod op;
10mod lower; 11mod lower;
@@ -145,6 +146,10 @@ impl Substs {
145 Substs(Arc::new([ty])) 146 Substs(Arc::new([ty]))
146 } 147 }
147 148
149 pub fn prefix(&self, n: usize) -> Substs {
150 Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into())
151 }
152
148 pub fn iter(&self) -> impl Iterator<Item = &Ty> { 153 pub fn iter(&self) -> impl Iterator<Item = &Ty> {
149 self.0.iter() 154 self.0.iter()
150 } 155 }
@@ -170,6 +175,12 @@ impl Substs {
170 } 175 }
171} 176}
172 177
178impl From<Vec<Ty>> for Substs {
179 fn from(v: Vec<Ty>) -> Self {
180 Substs(v.into())
181 }
182}
183
173/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait. 184/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
174/// Name to be bikeshedded: TraitBound? TraitImplements? 185/// Name to be bikeshedded: TraitBound? TraitImplements?
175#[derive(Clone, PartialEq, Eq, Debug, Hash)] 186#[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -210,6 +221,14 @@ impl FnSig {
210 &self.params_and_return[self.params_and_return.len() - 1] 221 &self.params_and_return[self.params_and_return.len() - 1]
211 } 222 }
212 223
224 /// Applies the given substitutions to all types in this signature and
225 /// returns the result.
226 pub fn subst(&self, substs: &Substs) -> FnSig {
227 let result: Vec<_> =
228 self.params_and_return.iter().map(|ty| ty.clone().subst(substs)).collect();
229 FnSig { params_and_return: result.into() }
230 }
231
213 pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { 232 pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
214 // Without an Arc::make_mut_slice, we can't avoid the clone here: 233 // Without an Arc::make_mut_slice, we can't avoid the clone here:
215 let mut v: Vec<_> = self.params_and_return.iter().cloned().collect(); 234 let mut v: Vec<_> = self.params_and_return.iter().cloned().collect();
@@ -309,6 +328,20 @@ impl Ty {
309 } 328 }
310 } 329 }
311 330
331 fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> {
332 match self {
333 Ty::Apply(a_ty) => match a_ty.ctor {
334 TypeCtor::FnPtr => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)),
335 TypeCtor::FnDef(def) => {
336 let sig = db.callable_item_signature(def);
337 Some(sig.subst(&a_ty.parameters))
338 }
339 _ => None,
340 },
341 _ => None,
342 }
343 }
344
312 /// If this is a type with type parameters (an ADT or function), replaces 345 /// If this is a type with type parameters (an ADT or function), replaces
313 /// the `Substs` for these type parameters with the given ones. (So e.g. if 346 /// the `Substs` for these type parameters with the given ones. (So e.g. if
314 /// `self` is `Option<_>` and the substs contain `u32`, we'll have 347 /// `self` is `Option<_>` and the substs contain `u32`, we'll have
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 28947be51..651a78fe5 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -20,9 +20,9 @@ use std::sync::Arc;
20use std::mem; 20use std::mem;
21 21
22use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError}; 22use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError};
23use ra_arena::map::ArenaMap;
24use rustc_hash::FxHashMap; 23use rustc_hash::FxHashMap;
25 24
25use ra_arena::map::ArenaMap;
26use test_utils::tested_by; 26use test_utils::tested_by;
27 27
28use crate::{ 28use crate::{
@@ -33,15 +33,18 @@ use crate::{
33 ImplItem, 33 ImplItem,
34 type_ref::{TypeRef, Mutability}, 34 type_ref::{TypeRef, Mutability},
35 expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat,Array, self}, 35 expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat,Array, self},
36 generics::GenericParams, 36 generics::{GenericParams, HasGenericParams},
37 path::{GenericArgs, GenericArg}, 37 path::{GenericArgs, GenericArg},
38 adt::VariantDef, 38 adt::VariantDef,
39 resolve::{Resolver, Resolution}, 39 resolve::{Resolver, Resolution},
40 nameres::Namespace, 40 nameres::Namespace,
41 ty::infer::diagnostics::InferenceDiagnostic,
42 diagnostics::DiagnosticSink, 41 diagnostics::DiagnosticSink,
43}; 42};
44use super::{Ty, TypableDef, Substs, primitive, op, FnSig, ApplicationTy, TypeCtor}; 43use super::{
44 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
45 traits::{ Solution, Obligation, Guidance},
46};
47use self::diagnostics::InferenceDiagnostic;
45 48
46/// The entry point of type inference. 49/// The entry point of type inference.
47pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { 50pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
@@ -153,6 +156,7 @@ struct InferenceContext<'a, D: HirDatabase> {
153 body: Arc<Body>, 156 body: Arc<Body>,
154 resolver: Resolver, 157 resolver: Resolver,
155 var_unification_table: InPlaceUnificationTable<TypeVarId>, 158 var_unification_table: InPlaceUnificationTable<TypeVarId>,
159 obligations: Vec<Obligation>,
156 method_resolutions: FxHashMap<ExprId, Function>, 160 method_resolutions: FxHashMap<ExprId, Function>,
157 field_resolutions: FxHashMap<ExprId, StructField>, 161 field_resolutions: FxHashMap<ExprId, StructField>,
158 assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>, 162 assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>,
@@ -173,6 +177,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
173 type_of_pat: ArenaMap::default(), 177 type_of_pat: ArenaMap::default(),
174 diagnostics: Vec::default(), 178 diagnostics: Vec::default(),
175 var_unification_table: InPlaceUnificationTable::new(), 179 var_unification_table: InPlaceUnificationTable::new(),
180 obligations: Vec::default(),
176 return_ty: Ty::Unknown, // set in collect_fn_signature 181 return_ty: Ty::Unknown, // set in collect_fn_signature
177 db, 182 db,
178 body, 183 body,
@@ -181,6 +186,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
181 } 186 }
182 187
183 fn resolve_all(mut self) -> InferenceResult { 188 fn resolve_all(mut self) -> InferenceResult {
189 // FIXME resolve obligations as well (use Guidance if necessary)
184 let mut tv_stack = Vec::new(); 190 let mut tv_stack = Vec::new();
185 let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default()); 191 let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default());
186 for ty in expr_types.values_mut() { 192 for ty in expr_types.values_mut() {
@@ -311,11 +317,49 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
311 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) 317 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
312 } 318 }
313 319
320 fn resolve_obligations_as_possible(&mut self) {
321 let obligations = mem::replace(&mut self.obligations, Vec::new());
322 for obligation in obligations {
323 // FIXME resolve types in the obligation first
324 let (solution, var_mapping) = match &obligation {
325 Obligation::Trait(tr) => {
326 let (tr, var_mapping) = super::traits::canonicalize(tr.clone());
327 (self.db.implements(tr), var_mapping)
328 }
329 };
330 match solution {
331 Some(Solution::Unique(substs)) => {
332 for (i, subst) in substs.0.iter().enumerate() {
333 let uncanonical = var_mapping[i];
334 // FIXME the subst may contain type variables, which would need to be mapped back as well
335 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
336 }
337 }
338 Some(Solution::Ambig(Guidance::Definite(substs))) => {
339 for (i, subst) in substs.0.iter().enumerate() {
340 let uncanonical = var_mapping[i];
341 // FIXME the subst may contain type variables, which would need to be mapped back as well
342 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
343 }
344 self.obligations.push(obligation);
345 }
346 Some(_) => {
347 self.obligations.push(obligation);
348 }
349 None => {
350 // FIXME obligation cannot be fulfilled => diagnostic
351 }
352 }
353 }
354 }
355
314 /// Resolves the type as far as currently possible, replacing type variables 356 /// Resolves the type as far as currently possible, replacing type variables
315 /// by their known types. All types returned by the infer_* functions should 357 /// by their known types. All types returned by the infer_* functions should
316 /// be resolved as far as possible, i.e. contain no type variables with 358 /// be resolved as far as possible, i.e. contain no type variables with
317 /// known type. 359 /// known type.
318 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 360 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
361 self.resolve_obligations_as_possible();
362
319 ty.fold(&mut |ty| match ty { 363 ty.fold(&mut |ty| match ty {
320 Ty::Infer(tv) => { 364 Ty::Infer(tv) => {
321 let inner = tv.to_inner(); 365 let inner = tv.to_inner();
@@ -420,6 +464,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
420 for segment in &path.segments[remaining_index..] { 464 for segment in &path.segments[remaining_index..] {
421 let ty = match resolved { 465 let ty = match resolved {
422 Resolution::Def(def) => { 466 Resolution::Def(def) => {
467 // FIXME resolve associated items from traits as well
423 let typable: Option<TypableDef> = def.into(); 468 let typable: Option<TypableDef> = def.into();
424 let typable = typable?; 469 let typable = typable?;
425 470
@@ -709,13 +754,21 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
709 fn substs_for_method_call( 754 fn substs_for_method_call(
710 &mut self, 755 &mut self,
711 def_generics: Option<Arc<GenericParams>>, 756 def_generics: Option<Arc<GenericParams>>,
712 generic_args: &Option<GenericArgs>, 757 generic_args: Option<&GenericArgs>,
758 receiver_ty: &Ty,
713 ) -> Substs { 759 ) -> Substs {
714 let (parent_param_count, param_count) = 760 let (parent_param_count, param_count) =
715 def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len())); 761 def_generics.as_ref().map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
716 let mut substs = Vec::with_capacity(parent_param_count + param_count); 762 let mut substs = Vec::with_capacity(parent_param_count + param_count);
717 for _ in 0..parent_param_count { 763 // Parent arguments are unknown, except for the receiver type
718 substs.push(Ty::Unknown); 764 if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
765 for param in &parent_generics.params {
766 if param.name.as_known_name() == Some(crate::KnownName::SelfType) {
767 substs.push(receiver_ty.clone());
768 } else {
769 substs.push(Ty::Unknown);
770 }
771 }
719 } 772 }
720 // handle provided type arguments 773 // handle provided type arguments
721 if let Some(generic_args) = generic_args { 774 if let Some(generic_args) = generic_args {
@@ -737,6 +790,83 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
737 Substs(substs.into()) 790 Substs(substs.into())
738 } 791 }
739 792
793 fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
794 match callable_ty {
795 Ty::Apply(a_ty) => match a_ty.ctor {
796 TypeCtor::FnDef(def) => {
797 // add obligation for trait implementation, if this is a trait method
798 // FIXME also register obligations from where clauses from the trait or impl and method
799 match def {
800 CallableDef::Function(f) => {
801 if let Some(trait_) = f.parent_trait(self.db) {
802 // construct a TraitDef
803 let substs = a_ty.parameters.prefix(
804 trait_.generic_params(self.db).count_params_including_parent(),
805 );
806 self.obligations
807 .push(Obligation::Trait(TraitRef { trait_, substs }));
808 }
809 }
810 CallableDef::Struct(_) | CallableDef::EnumVariant(_) => {}
811 }
812 }
813 _ => {}
814 },
815 _ => {}
816 }
817 }
818
819 fn infer_method_call(
820 &mut self,
821 tgt_expr: ExprId,
822 receiver: ExprId,
823 args: &[ExprId],
824 method_name: &Name,
825 generic_args: Option<&GenericArgs>,
826 ) -> Ty {
827 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
828 let resolved = receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
829 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
830 Some((ty, func)) => {
831 self.write_method_resolution(tgt_expr, func);
832 (
833 ty,
834 self.db.type_for_def(func.into(), Namespace::Values),
835 Some(func.generic_params(self.db)),
836 )
837 }
838 None => (receiver_ty, Ty::Unknown, None),
839 };
840 let substs =
841 self.substs_for_method_call(def_generics.clone(), generic_args, &derefed_receiver_ty);
842 let method_ty = method_ty.apply_substs(substs);
843 let method_ty = self.insert_type_vars(method_ty);
844 self.register_obligations_for_call(&method_ty);
845 let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
846 Some(sig) => {
847 if !sig.params().is_empty() {
848 (sig.params()[0].clone(), sig.params()[1..].to_vec(), sig.ret().clone())
849 } else {
850 (Ty::Unknown, Vec::new(), sig.ret().clone())
851 }
852 }
853 None => (Ty::Unknown, Vec::new(), Ty::Unknown),
854 };
855 // Apply autoref so the below unification works correctly
856 // FIXME: return correct autorefs from lookup_method
857 let actual_receiver_ty = match expected_receiver_ty.as_reference() {
858 Some((_, mutability)) => Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty),
859 _ => derefed_receiver_ty,
860 };
861 self.unify(&expected_receiver_ty, &actual_receiver_ty);
862
863 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
864 for (arg, param) in args.iter().zip(param_iter) {
865 self.infer_expr(*arg, &Expectation::has_type(param));
866 }
867 ret_ty
868 }
869
740 fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { 870 fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
741 let body = Arc::clone(&self.body); // avoid borrow checker problem 871 let body = Arc::clone(&self.body); // avoid borrow checker problem
742 let ty = match &body[tgt_expr] { 872 let ty = match &body[tgt_expr] {
@@ -793,102 +923,23 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
793 } 923 }
794 Expr::Call { callee, args } => { 924 Expr::Call { callee, args } => {
795 let callee_ty = self.infer_expr(*callee, &Expectation::none()); 925 let callee_ty = self.infer_expr(*callee, &Expectation::none());
796 let (param_tys, ret_ty) = match &callee_ty { 926 let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
797 Ty::Apply(a_ty) => match a_ty.ctor { 927 Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
798 TypeCtor::FnPtr => { 928 None => {
799 let sig = FnSig::from_fn_ptr_substs(&a_ty.parameters); 929 // Not callable
800 (sig.params().to_vec(), sig.ret().clone()) 930 // FIXME: report an error
801 }
802 TypeCtor::FnDef(def) => {
803 let sig = self.db.callable_item_signature(def);
804 let ret_ty = sig.ret().clone().subst(&a_ty.parameters);
805 let param_tys = sig
806 .params()
807 .iter()
808 .map(|ty| ty.clone().subst(&a_ty.parameters))
809 .collect();
810 (param_tys, ret_ty)
811 }
812 _ => (Vec::new(), Ty::Unknown),
813 },
814 _ => {
815 // not callable
816 // FIXME report an error?
817 (Vec::new(), Ty::Unknown) 931 (Vec::new(), Ty::Unknown)
818 } 932 }
819 }; 933 };
934 // FIXME register obligations from where clauses from the function
820 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown)); 935 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
821 for (arg, param) in args.iter().zip(param_iter) { 936 for (arg, param) in args.iter().zip(param_iter) {
822 self.infer_expr(*arg, &Expectation::has_type(param)); 937 self.infer_expr(*arg, &Expectation::has_type(param));
823 } 938 }
824 ret_ty 939 ret_ty
825 } 940 }
826 Expr::MethodCall { receiver, args, method_name, generic_args } => { 941 Expr::MethodCall { receiver, args, method_name, generic_args } => self
827 let receiver_ty = self.infer_expr(*receiver, &Expectation::none()); 942 .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
828 let resolved =
829 receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
830 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
831 Some((ty, func)) => {
832 self.write_method_resolution(tgt_expr, func);
833 (
834 ty,
835 self.db.type_for_def(func.into(), Namespace::Values),
836 Some(func.generic_params(self.db)),
837 )
838 }
839 None => (receiver_ty, Ty::Unknown, None),
840 };
841 let substs = self.substs_for_method_call(def_generics, generic_args);
842 let method_ty = method_ty.apply_substs(substs);
843 let method_ty = self.insert_type_vars(method_ty);
844 let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty {
845 Ty::Apply(a_ty) => match a_ty.ctor {
846 TypeCtor::FnPtr => {
847 let sig = FnSig::from_fn_ptr_substs(&a_ty.parameters);
848 if !sig.params().is_empty() {
849 (
850 sig.params()[0].clone(),
851 sig.params()[1..].to_vec(),
852 sig.ret().clone(),
853 )
854 } else {
855 (Ty::Unknown, Vec::new(), sig.ret().clone())
856 }
857 }
858 TypeCtor::FnDef(def) => {
859 let sig = self.db.callable_item_signature(def);
860 let ret_ty = sig.ret().clone().subst(&a_ty.parameters);
861
862 if !sig.params().is_empty() {
863 let mut params_iter = sig
864 .params()
865 .iter()
866 .map(|ty| ty.clone().subst(&a_ty.parameters));
867 let receiver_ty = params_iter.next().unwrap();
868 (receiver_ty, params_iter.collect(), ret_ty)
869 } else {
870 (Ty::Unknown, Vec::new(), ret_ty)
871 }
872 }
873 _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
874 },
875 _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
876 };
877 // Apply autoref so the below unification works correctly
878 let actual_receiver_ty = match expected_receiver_ty.as_reference() {
879 Some((_, mutability)) => {
880 Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty)
881 }
882 _ => derefed_receiver_ty,
883 };
884 self.unify(&expected_receiver_ty, &actual_receiver_ty);
885
886 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
887 for (arg, param) in args.iter().zip(param_iter) {
888 self.infer_expr(*arg, &Expectation::has_type(param));
889 }
890 ret_ty
891 }
892 Expr::Match { expr, arms } => { 943 Expr::Match { expr, arms } => {
893 let expected = if expected.ty == Ty::Unknown { 944 let expected = if expected.ty == Ty::Unknown {
894 Expectation::has_type(self.new_type_var()) 945 Expectation::has_type(self.new_type_var())
@@ -1180,7 +1231,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
1180 1231
1181/// The ID of a type variable. 1232/// The ID of a type variable.
1182#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] 1233#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
1183pub struct TypeVarId(u32); 1234pub struct TypeVarId(pub(super) u32);
1184 1235
1185impl UnifyKey for TypeVarId { 1236impl UnifyKey for TypeVarId {
1186 type Value = TypeVarValue; 1237 type Value = TypeVarValue;
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 003a89f0d..7fac084ce 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -5,6 +5,7 @@
5//! - Building the type for an item: This happens through the `type_for_def` query. 5//! - Building the type for an item: This happens through the `type_for_def` query.
6//! 6//!
7//! This usually involves resolving names, collecting generic arguments etc. 7//! This usually involves resolving names, collecting generic arguments etc.
8use std::iter;
8 9
9use crate::{ 10use crate::{
10 Function, Struct, StructField, Enum, EnumVariant, Path, 11 Function, Struct, StructField, Enum, EnumVariant, Path,
@@ -15,11 +16,11 @@ use crate::{
15 name::KnownName, 16 name::KnownName,
16 nameres::Namespace, 17 nameres::Namespace,
17 resolve::{Resolver, Resolution}, 18 resolve::{Resolver, Resolution},
18 path::{ PathSegment, GenericArg}, 19 path::{PathSegment, GenericArg},
19 generics::GenericParams, 20 generics::{GenericParams, HasGenericParams},
20 adt::VariantDef, 21 adt::VariantDef, Trait
21}; 22};
22use super::{Ty, primitive, FnSig, Substs, TypeCtor}; 23use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef};
23 24
24impl Ty { 25impl Ty {
25 pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self { 26 pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
@@ -115,7 +116,6 @@ impl Ty {
115 segment: &PathSegment, 116 segment: &PathSegment,
116 resolved: TypableDef, 117 resolved: TypableDef,
117 ) -> Substs { 118 ) -> Substs {
118 let mut substs = Vec::new();
119 let def_generics = match resolved { 119 let def_generics = match resolved {
120 TypableDef::Function(func) => func.generic_params(db), 120 TypableDef::Function(func) => func.generic_params(db),
121 TypableDef::Struct(s) => s.generic_params(db), 121 TypableDef::Struct(s) => s.generic_params(db),
@@ -124,28 +124,7 @@ impl Ty {
124 TypableDef::TypeAlias(t) => t.generic_params(db), 124 TypableDef::TypeAlias(t) => t.generic_params(db),
125 TypableDef::Const(_) | TypableDef::Static(_) => GenericParams::default().into(), 125 TypableDef::Const(_) | TypableDef::Static(_) => GenericParams::default().into(),
126 }; 126 };
127 let parent_param_count = def_generics.count_parent_params(); 127 substs_from_path_segment(db, resolver, segment, &def_generics, false)
128 substs.extend((0..parent_param_count).map(|_| Ty::Unknown));
129 if let Some(generic_args) = &segment.args_and_bindings {
130 // if args are provided, it should be all of them, but we can't rely on that
131 let param_count = def_generics.params.len();
132 for arg in generic_args.args.iter().take(param_count) {
133 match arg {
134 GenericArg::Type(type_ref) => {
135 let ty = Ty::from_hir(db, resolver, type_ref);
136 substs.push(ty);
137 }
138 }
139 }
140 }
141 // add placeholders for args that were not provided
142 // FIXME: handle defaults
143 let supplied_params = substs.len();
144 for _ in supplied_params..def_generics.count_params_including_parent() {
145 substs.push(Ty::Unknown);
146 }
147 assert_eq!(substs.len(), def_generics.count_params_including_parent());
148 Substs(substs.into())
149 } 128 }
150 129
151 /// Collect generic arguments from a path into a `Substs`. See also 130 /// Collect generic arguments from a path into a `Substs`. See also
@@ -185,6 +164,82 @@ impl Ty {
185 } 164 }
186} 165}
187 166
167pub(super) fn substs_from_path_segment(
168 db: &impl HirDatabase,
169 resolver: &Resolver,
170 segment: &PathSegment,
171 def_generics: &GenericParams,
172 add_self_param: bool,
173) -> Substs {
174 let mut substs = Vec::new();
175 let parent_param_count = def_generics.count_parent_params();
176 substs.extend(iter::repeat(Ty::Unknown).take(parent_param_count));
177 if add_self_param {
178 // FIXME this add_self_param argument is kind of a hack: Traits have the
179 // Self type as an implicit first type parameter, but it can't be
180 // actually provided in the type arguments
181 // (well, actually sometimes it can, in the form of type-relative paths: `<Foo as Default>::default()`)
182 substs.push(Ty::Unknown);
183 }
184 if let Some(generic_args) = &segment.args_and_bindings {
185 // if args are provided, it should be all of them, but we can't rely on that
186 let self_param_correction = if add_self_param { 1 } else { 0 };
187 let param_count = def_generics.params.len() - self_param_correction;
188 for arg in generic_args.args.iter().take(param_count) {
189 match arg {
190 GenericArg::Type(type_ref) => {
191 let ty = Ty::from_hir(db, resolver, type_ref);
192 substs.push(ty);
193 }
194 }
195 }
196 }
197 // add placeholders for args that were not provided
198 // FIXME: handle defaults
199 let supplied_params = substs.len();
200 for _ in supplied_params..def_generics.count_params_including_parent() {
201 substs.push(Ty::Unknown);
202 }
203 assert_eq!(substs.len(), def_generics.count_params_including_parent());
204 Substs(substs.into())
205}
206
207impl TraitRef {
208 pub(crate) fn from_hir(
209 db: &impl HirDatabase,
210 resolver: &Resolver,
211 type_ref: &TypeRef,
212 explicit_self_ty: Option<Ty>,
213 ) -> Option<Self> {
214 let path = match type_ref {
215 TypeRef::Path(path) => path,
216 _ => return None,
217 };
218 let resolved = match resolver.resolve_path(db, &path).take_types()? {
219 Resolution::Def(ModuleDef::Trait(tr)) => tr,
220 _ => return None,
221 };
222 let mut substs = Self::substs_from_path(db, resolver, path, resolved);
223 if let Some(self_ty) = explicit_self_ty {
224 // FIXME this could be nicer
225 let mut substs_vec = substs.0.to_vec();
226 substs_vec[0] = self_ty;
227 substs.0 = substs_vec.into();
228 }
229 Some(TraitRef { trait_: resolved, substs })
230 }
231
232 fn substs_from_path(
233 db: &impl HirDatabase,
234 resolver: &Resolver,
235 path: &Path,
236 resolved: Trait,
237 ) -> Substs {
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)
240 }
241}
242
188/// Build the declared type of an item. This depends on the namespace; e.g. for 243/// Build the declared type of an item. This depends on the namespace; e.g. for
189/// `struct Foo(usize)`, we have two types: The type of the struct itself, and 244/// `struct Foo(usize)`, we have two types: The type of the struct itself, and
190/// the constructor function `(usize) -> Foo` which lives in the values 245/// the constructor function `(usize) -> Foo` which lives in the values
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index bb23246a6..6b7918187 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -10,10 +10,12 @@ use crate::{
10 HirDatabase, Module, Crate, Name, Function, Trait, 10 HirDatabase, Module, Crate, Name, Function, Trait,
11 impl_block::{ImplId, ImplBlock, ImplItem}, 11 impl_block::{ImplId, ImplBlock, ImplItem},
12 ty::{Ty, TypeCtor}, 12 ty::{Ty, TypeCtor},
13 nameres::CrateModuleId, resolve::Resolver, traits::TraitItem 13 nameres::CrateModuleId,
14 14 resolve::Resolver,
15 traits::TraitItem,
16 generics::HasGenericParams,
15}; 17};
16use super::{ TraitRef, Substs}; 18use super::{TraitRef, Substs};
17 19
18/// This is used as a key for indexing impls. 20/// This is used as a key for indexing impls.
19#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 21#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -72,9 +74,9 @@ impl CrateImplBlocks {
72 74
73 let target_ty = impl_block.target_ty(db); 75 let target_ty = impl_block.target_ty(db);
74 76
75 if let Some(tr) = impl_block.target_trait(db) { 77 if let Some(tr) = impl_block.target_trait_ref(db) {
76 self.impls_by_trait 78 self.impls_by_trait
77 .entry(tr) 79 .entry(tr.trait_)
78 .or_insert_with(Vec::new) 80 .or_insert_with(Vec::new)
79 .push((module.module_id, impl_id)); 81 .push((module.module_id, impl_id));
80 } else { 82 } else {
@@ -108,20 +110,6 @@ impl CrateImplBlocks {
108 } 110 }
109} 111}
110 112
111/// Rudimentary check whether an impl exists for a given type and trait; this
112/// will actually be done by chalk.
113pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> bool {
114 // FIXME use all trait impls in the whole crate graph
115 let krate = trait_ref.trait_.module(db).krate(db);
116 let krate = match krate {
117 Some(krate) => krate,
118 None => return false,
119 };
120 let crate_impl_blocks = db.impls_in_crate(krate);
121 let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_);
122 impl_blocks.any(|impl_block| &impl_block.target_ty(db) == trait_ref.self_ty())
123}
124
125fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> { 113fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> {
126 match ty { 114 match ty {
127 Ty::Apply(a_ty) => match a_ty.ctor { 115 Ty::Apply(a_ty) => match a_ty.ctor {
@@ -142,6 +130,7 @@ impl Ty {
142 resolver: &Resolver, 130 resolver: &Resolver,
143 ) -> Option<(Ty, Function)> { 131 ) -> Option<(Ty, Function)> {
144 // FIXME: trait methods should be used before autoderefs 132 // FIXME: trait methods should be used before autoderefs
133 // (and we need to do autoderefs for trait method calls as well)
145 let inherent_method = self.clone().iterate_methods(db, |ty, f| { 134 let inherent_method = self.clone().iterate_methods(db, |ty, f| {
146 let sig = f.signature(db); 135 let sig = f.signature(db);
147 if sig.name() == name && sig.has_self_param() { 136 if sig.name() == name && sig.has_self_param() {
@@ -174,22 +163,15 @@ impl Ty {
174 } 163 }
175 } 164 }
176 } 165 }
177 // FIXME:
178 // - we might not actually be able to determine fully that the type
179 // implements the trait here; it's enough if we (well, Chalk) determine
180 // that it's possible.
181 // - when the trait method is picked, we need to register an
182 // 'obligation' somewhere so that we later check that it's really
183 // implemented
184 // - both points go for additional requirements from where clauses as
185 // well (in fact, the 'implements' condition could just be considered a
186 // 'where Self: Trait' clause)
187 candidates.retain(|(t, _m)| { 166 candidates.retain(|(t, _m)| {
188 let trait_ref = TraitRef { trait_: *t, substs: Substs::single(self.clone()) }; 167 let trait_ref =
189 db.implements(trait_ref) 168 TraitRef { trait_: *t, substs: fresh_substs_for_trait(db, *t, self.clone()) };
169 let (trait_ref, _) = super::traits::canonicalize(trait_ref);
170 db.implements(trait_ref).is_some()
190 }); 171 });
191 // FIXME if there's multiple candidates here, that's an ambiguity error 172 // FIXME if there's multiple candidates here, that's an ambiguity error
192 let (_chosen_trait, chosen_method) = candidates.first()?; 173 let (_chosen_trait, chosen_method) = candidates.first()?;
174 // FIXME return correct receiver type
193 Some((self.clone(), *chosen_method)) 175 Some((self.clone(), *chosen_method))
194 } 176 }
195 177
@@ -252,3 +234,17 @@ impl Ty {
252 None 234 None
253 } 235 }
254} 236}
237
238/// This creates Substs for a trait with the given Self type and type variables
239/// for all other parameters. This is kind of a hack since these aren't 'real'
240/// type variables; the resulting trait reference is just used for the
241/// preliminary method candidate check.
242fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
243 let mut substs = Vec::new();
244 let generics = tr.generic_params(db);
245 substs.push(self_ty);
246 substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map(
247 |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))),
248 ));
249 substs.into()
250}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index d7c2ca132..291bc9ae5 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -1926,8 +1926,8 @@ fn test() {
1926} 1926}
1927"#), 1927"#),
1928 @r###" 1928 @r###"
1929[31; 35) 'self': &{unknown} 1929[31; 35) 'self': &Self
1930[110; 114) 'self': &{unknown} 1930[110; 114) 'self': &Self
1931[170; 228) '{ ...i128 }': () 1931[170; 228) '{ ...i128 }': ()
1932[176; 178) 'S1': S1 1932[176; 178) 'S1': S1
1933[176; 187) 'S1.method()': u32 1933[176; 187) 'S1.method()': u32
@@ -1972,8 +1972,8 @@ mod bar_test {
1972} 1972}
1973"#), 1973"#),
1974 @r###" 1974 @r###"
1975[63; 67) 'self': &{unknown} 1975[63; 67) 'self': &Self
1976[169; 173) 'self': &{unknown} 1976[169; 173) 'self': &Self
1977[300; 337) '{ ... }': () 1977[300; 337) '{ ... }': ()
1978[310; 311) 'S': S 1978[310; 311) 'S': S
1979[310; 320) 'S.method()': u32 1979[310; 320) 'S.method()': u32
@@ -1998,10 +1998,45 @@ fn test() {
1998} 1998}
1999"#), 1999"#),
2000 @r###" 2000 @r###"
2001[33; 37) 'self': &{unknown} 2001[33; 37) 'self': &Self
2002[92; 111) '{ ...d(); }': () 2002[92; 111) '{ ...d(); }': ()
2003[98; 99) 'S': S 2003[98; 99) 'S': S
2004[98; 108) 'S.method()': {unknown}"### 2004[98; 108) 'S.method()': u32"###
2005 );
2006}
2007
2008#[test]
2009fn infer_trait_method_generic_more_params() {
2010 // the trait implementation is intentionally incomplete -- it shouldn't matter
2011 assert_snapshot_matches!(
2012 infer(r#"
2013trait Trait<T1, T2, T3> {
2014 fn method1(&self) -> (T1, T2, T3);
2015 fn method2(&self) -> (T3, T2, T1);
2016}
2017struct S1;
2018impl Trait<u8, u16, u32> for S1 {}
2019struct S2;
2020impl<T> Trait<i8, i16, T> for S2 {}
2021fn test() {
2022 S1.method1(); // u8, u16, u32
2023 S1.method2(); // u32, u16, u8
2024 S2.method1(); // i8, i16, {unknown}
2025 S2.method2(); // {unknown}, i16, i8
2026}
2027"#),
2028 @r###"
2029[43; 47) 'self': &Self
2030[82; 86) 'self': &Self
2031[210; 361) '{ ..., i8 }': ()
2032[216; 218) 'S1': S1
2033[216; 228) 'S1.method1()': (u8, u16, u32)
2034[250; 252) 'S1': S1
2035[250; 262) 'S1.method2()': (u32, u16, u8)
2036[284; 286) 'S2': S2
2037[284; 296) 'S2.method1()': (i8, i16, {unknown})
2038[324; 326) 'S2': S2
2039[324; 336) 'S2.method2()': ({unknown}, i16, i8)"###
2005 ); 2040 );
2006} 2041}
2007 2042
@@ -2020,7 +2055,7 @@ fn test() {
2020} 2055}
2021"#), 2056"#),
2022 @r###" 2057 @r###"
2023[33; 37) 'self': &{unknown} 2058[33; 37) 'self': &Self
2024[102; 127) '{ ...d(); }': () 2059[102; 127) '{ ...d(); }': ()
2025[108; 109) 'S': S<u32>(T) -> S<T> 2060[108; 109) 'S': S<u32>(T) -> S<T>
2026[108; 115) 'S(1u32)': S<u32> 2061[108; 115) 'S(1u32)': S<u32>
@@ -2168,7 +2203,7 @@ fn test() {
2168} 2203}
2169"#), 2204"#),
2170 @r###" 2205 @r###"
2171[29; 33) 'self': {unknown} 2206[29; 33) 'self': Self
2172[107; 198) '{ ...(S); }': () 2207[107; 198) '{ ...(S); }': ()
2173[117; 118) 'x': u32 2208[117; 118) 'x': u32
2174[126; 127) 'S': S 2209[126; 127) 'S': S
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
new file mode 100644
index 000000000..f8c3958bd
--- /dev/null
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -0,0 +1,112 @@
1//! Stuff that will probably mostly replaced by Chalk.
2use std::collections::HashMap;
3
4use crate::db::HirDatabase;
5use super::{ TraitRef, Substs, infer::{ TypeVarId, InferTy}, Ty};
6
7// Copied (and simplified) from Chalk
8
9#[derive(Clone, Debug, PartialEq, Eq)]
10/// A (possible) solution for a proposed goal. Usually packaged in a `Result`,
11/// where `Err` represents definite *failure* to prove a goal.
12pub enum Solution {
13 /// The goal indeed holds, and there is a unique value for all existential
14 /// variables.
15 Unique(Substs),
16
17 /// The goal may be provable in multiple ways, but regardless we may have some guidance
18 /// for type inference.
19 Ambig(Guidance),
20}
21
22#[derive(Clone, Debug, PartialEq, Eq)]
23/// When a goal holds ambiguously (e.g., because there are multiple possible
24/// solutions), we issue a set of *guidance* back to type inference.
25pub enum Guidance {
26 /// The existential variables *must* have the given values if the goal is
27 /// ever to hold, but that alone isn't enough to guarantee the goal will
28 /// actually hold.
29 Definite(Substs),
30
31 /// There are multiple plausible values for the existentials, but the ones
32 /// here are suggested as the preferred choice heuristically. These should
33 /// be used for inference fallback only.
34 Suggested(Substs),
35
36 /// There's no useful information to feed back to type inference
37 Unknown,
38}
39
40/// 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
42/// 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)]
46pub enum Obligation {
47 /// Prove that a certain type implements a trait (the type is the `Self` type
48 /// parameter to the `TraitRef`).
49 Trait(TraitRef),
50}
51
52/// Rudimentary check whether an impl exists for a given type and trait; this
53/// will actually be done by chalk.
54pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> {
55 // FIXME use all trait impls in the whole crate graph
56 let krate = trait_ref.trait_.module(db).krate(db);
57 let krate = match krate {
58 Some(krate) => krate,
59 None => return None,
60 };
61 let crate_impl_blocks = db.impls_in_crate(krate);
62 let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_);
63 impl_blocks
64 .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?))
65}
66
67pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) {
68 let mut canonical = HashMap::new(); // mapping uncanonical -> canonical
69 let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense)
70 let mut substs = trait_ref.substs.0.to_vec();
71 for ty in &mut substs {
72 ty.walk_mut(&mut |ty| match ty {
73 Ty::Infer(InferTy::TypeVar(tv)) => {
74 let tv: &mut TypeVarId = tv;
75 *tv = *canonical.entry(*tv).or_insert_with(|| {
76 let i = uncanonical.len();
77 uncanonical.push(*tv);
78 TypeVarId(i as u32)
79 });
80 }
81 _ => {}
82 });
83 }
84 (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
85}
86
87fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> {
88 if tr1.trait_ != tr2.trait_ {
89 return None;
90 }
91 let mut solution_substs = Vec::new();
92 for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) {
93 // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass
94 match (t1, t2) {
95 (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => {
96 // type variable (or similar) in the impl, we just assume it works
97 }
98 (Ty::Infer(InferTy::TypeVar(v1)), _) => {
99 // type variable in the query and fixed type in the impl, record its value
100 solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown);
101 solution_substs[v1.0 as usize] = t2.clone();
102 }
103 _ => {
104 // check that they're equal (actually we'd have to recurse etc.)
105 if t1 != t2 {
106 return None;
107 }
108 }
109 }
110 }
111 Some(Solution::Unique(solution_substs.into()))
112}