aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir/src')
-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}