aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir
diff options
context:
space:
mode:
authorFlorian Diebold <[email protected]>2019-03-31 19:02:16 +0100
committerFlorian Diebold <[email protected]>2019-04-14 10:28:53 +0100
commita1ed53a4f183b5826162eb9e998207b92be9c57f (patch)
tree7c139a7dc38483188653c6d40583cddac9d23192 /crates/ra_hir
parent413c87f155ab6b389b1cc122b5739716acccb476 (diff)
More trait infrastructure
- make it possible to get parent trait from method - add 'obligation' machinery for checking that a type implements a trait (and inferring facts about type variables from that) - handle type parameters of traits (to a certain degree) - improve the hacky implements check to cover enough cases to exercise the handling of traits with type parameters - basic canonicalization (will probably also be done by Chalk)
Diffstat (limited to 'crates/ra_hir')
-rw-r--r--crates/ra_hir/src/code_model_api.rs17
-rw-r--r--crates/ra_hir/src/db.rs7
-rw-r--r--crates/ra_hir/src/generics.rs10
-rw-r--r--crates/ra_hir/src/impl_block.rs3
-rw-r--r--crates/ra_hir/src/traits.rs33
-rw-r--r--crates/ra_hir/src/ty.rs11
-rw-r--r--crates/ra_hir/src/ty/infer.rs84
-rw-r--r--crates/ra_hir/src/ty/lower.rs9
-rw-r--r--crates/ra_hir/src/ty/method_resolution.rs47
-rw-r--r--crates/ra_hir/src/ty/tests.rs51
-rw-r--r--crates/ra_hir/src/ty/traits.rs112
11 files changed, 333 insertions, 51 deletions
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 5d8cf57b6..b53fe1f63 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -194,7 +194,7 @@ impl Module {
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
@@ -547,13 +547,20 @@ impl Function {
547 ImplBlock::containing(module_impls, (*self).into()) 547 ImplBlock::containing(module_impls, (*self).into())
548 } 548 }
549 549
550 /// The containing trait, if this is a trait method definition.
551 pub fn parent_trait(&self, db: &impl DefDatabase) -> Option<Trait> {
552 db.trait_items_index(self.module(db)).get_parent_trait((*self).into())
553 }
554
550 // FIXME: move to a more general type for 'body-having' items 555 // FIXME: move to a more general type for 'body-having' items
551 /// Builds a resolver for code inside this item. 556 /// Builds a resolver for code inside this item.
552 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver { 557 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> Resolver {
553 // take the outer scope... 558 // take the outer scope...
559 // FIXME abstract over containers (trait/impl)
554 let r = self 560 let r = self
555 .impl_block(db) 561 .impl_block(db)
556 .map(|ib| ib.resolver(db)) 562 .map(|ib| ib.resolver(db))
563 .or_else(|| self.parent_trait(db).map(|tr| tr.resolver(db)))
557 .unwrap_or_else(|| self.module(db).resolver(db)); 564 .unwrap_or_else(|| self.module(db).resolver(db));
558 // ...and add generic params, if present 565 // ...and add generic params, if present
559 let p = self.generic_params(db); 566 let p = self.generic_params(db);
@@ -699,6 +706,14 @@ impl Trait {
699 pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> { 706 pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
700 db.trait_data(self) 707 db.trait_data(self)
701 } 708 }
709
710 pub fn resolver(&self, db: &impl HirDatabase) -> Resolver {
711 let r = self.module(db).resolver(db);
712 // add generic params, if present
713 let p = self.generic_params(db);
714 let r = if !p.params.is_empty() { r.push_generic_params_scope(p) } else { r };
715 r
716 }
702} 717}
703 718
704impl Docs for Trait { 719impl Docs for Trait {
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 4d82fe25f..51c846e91 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -45,12 +45,16 @@ impl GenericParams {
45 ) -> Arc<GenericParams> { 45 ) -> Arc<GenericParams> {
46 let mut generics = GenericParams::default(); 46 let mut generics = GenericParams::default();
47 let parent = match def { 47 let parent = match def {
48 GenericDef::Function(it) => it.impl_block(db), 48 // FIXME abstract over containers (trait/impl)
49 GenericDef::TypeAlias(it) => it.impl_block(db), 49 GenericDef::Function(it) => it
50 .impl_block(db)
51 .map(GenericDef::from)
52 .or_else(|| it.parent_trait(db).map(GenericDef::from)),
53 GenericDef::TypeAlias(it) => it.impl_block(db).map(GenericDef::from),
50 GenericDef::Struct(_) | GenericDef::Enum(_) | GenericDef::Trait(_) => None, 54 GenericDef::Struct(_) | GenericDef::Enum(_) | GenericDef::Trait(_) => None,
51 GenericDef::ImplBlock(_) => None, 55 GenericDef::ImplBlock(_) => None,
52 }; 56 };
53 generics.parent_params = parent.map(|p| p.generic_params(db)); 57 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; 58 let start = generics.parent_params.as_ref().map(|p| p.params.len()).unwrap_or(0) as u32;
55 match def { 59 match def {
56 GenericDef::Function(it) => generics.fill(&*it.source(db).1, start), 60 GenericDef::Function(it) => generics.fill(&*it.source(db).1, start),
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index 822a1a0db..42c02c9fb 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -84,7 +84,8 @@ impl ImplBlock {
84 } 84 }
85 85
86 pub fn target_trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> { 86 pub fn target_trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
87 TraitRef::from_hir(db, &self.resolver(db), &self.target_trait(db)?) 87 let target_ty = self.target_ty(db);
88 TraitRef::from_hir(db, &self.resolver(db), &self.target_trait(db)?, Some(target_ty))
88 } 89 }
89 90
90 pub fn items(&self, db: &impl DefDatabase) -> Vec<ImplItem> { 91 pub fn items(&self, db: &impl DefDatabase) -> Vec<ImplItem> {
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..aa43bc800 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)]
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 28947be51..3dec5936a 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -41,7 +41,7 @@ use crate::{
41 ty::infer::diagnostics::InferenceDiagnostic, 41 ty::infer::diagnostics::InferenceDiagnostic,
42 diagnostics::DiagnosticSink, 42 diagnostics::DiagnosticSink,
43}; 43};
44use super::{Ty, TypableDef, Substs, primitive, op, FnSig, ApplicationTy, TypeCtor}; 44use super::{Ty, TypableDef, Substs, primitive, op, FnSig, ApplicationTy, TypeCtor, traits::{ Solution, Obligation, Guidance}, CallableDef, TraitRef};
45 45
46/// The entry point of type inference. 46/// The entry point of type inference.
47pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { 47pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
@@ -153,6 +153,7 @@ struct InferenceContext<'a, D: HirDatabase> {
153 body: Arc<Body>, 153 body: Arc<Body>,
154 resolver: Resolver, 154 resolver: Resolver,
155 var_unification_table: InPlaceUnificationTable<TypeVarId>, 155 var_unification_table: InPlaceUnificationTable<TypeVarId>,
156 obligations: Vec<Obligation>,
156 method_resolutions: FxHashMap<ExprId, Function>, 157 method_resolutions: FxHashMap<ExprId, Function>,
157 field_resolutions: FxHashMap<ExprId, StructField>, 158 field_resolutions: FxHashMap<ExprId, StructField>,
158 assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>, 159 assoc_resolutions: FxHashMap<ExprOrPatId, ImplItem>,
@@ -173,6 +174,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
173 type_of_pat: ArenaMap::default(), 174 type_of_pat: ArenaMap::default(),
174 diagnostics: Vec::default(), 175 diagnostics: Vec::default(),
175 var_unification_table: InPlaceUnificationTable::new(), 176 var_unification_table: InPlaceUnificationTable::new(),
177 obligations: Vec::default(),
176 return_ty: Ty::Unknown, // set in collect_fn_signature 178 return_ty: Ty::Unknown, // set in collect_fn_signature
177 db, 179 db,
178 body, 180 body,
@@ -181,6 +183,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
181 } 183 }
182 184
183 fn resolve_all(mut self) -> InferenceResult { 185 fn resolve_all(mut self) -> InferenceResult {
186 // FIXME resolve obligations as well (use Guidance if necessary)
184 let mut tv_stack = Vec::new(); 187 let mut tv_stack = Vec::new();
185 let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default()); 188 let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default());
186 for ty in expr_types.values_mut() { 189 for ty in expr_types.values_mut() {
@@ -311,11 +314,49 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
311 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) 314 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
312 } 315 }
313 316
317 fn resolve_obligations_as_possible(&mut self) {
318 let obligations = mem::replace(&mut self.obligations, Vec::new());
319 for obligation in obligations {
320 // FIXME resolve types in the obligation first
321 let (solution, var_mapping) = match &obligation {
322 Obligation::Trait(tr) => {
323 let (tr, var_mapping) = super::traits::canonicalize(tr.clone());
324 (self.db.implements(tr), var_mapping)
325 }
326 };
327 match solution {
328 Some(Solution::Unique(substs)) => {
329 for (i, subst) in substs.0.iter().enumerate() {
330 let uncanonical = var_mapping[i];
331 // FIXME the subst may contain type variables, which would need to be mapped back as well
332 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
333 }
334 }
335 Some(Solution::Ambig(Guidance::Definite(substs))) => {
336 for (i, subst) in substs.0.iter().enumerate() {
337 let uncanonical = var_mapping[i];
338 // FIXME the subst may contain type variables, which would need to be mapped back as well
339 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
340 }
341 self.obligations.push(obligation);
342 }
343 Some(_) => {
344 self.obligations.push(obligation);
345 }
346 None => {
347 // FIXME obligation cannot be fulfilled => diagnostic
348 }
349 }
350 }
351 }
352
314 /// Resolves the type as far as currently possible, replacing type variables 353 /// Resolves the type as far as currently possible, replacing type variables
315 /// by their known types. All types returned by the infer_* functions should 354 /// 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 355 /// be resolved as far as possible, i.e. contain no type variables with
317 /// known type. 356 /// known type.
318 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { 357 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
358 self.resolve_obligations_as_possible();
359
319 ty.fold(&mut |ty| match ty { 360 ty.fold(&mut |ty| match ty {
320 Ty::Infer(tv) => { 361 Ty::Infer(tv) => {
321 let inner = tv.to_inner(); 362 let inner = tv.to_inner();
@@ -710,12 +751,19 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
710 &mut self, 751 &mut self,
711 def_generics: Option<Arc<GenericParams>>, 752 def_generics: Option<Arc<GenericParams>>,
712 generic_args: &Option<GenericArgs>, 753 generic_args: &Option<GenericArgs>,
754 receiver_ty: &Ty,
713 ) -> Substs { 755 ) -> Substs {
714 let (parent_param_count, param_count) = 756 let (parent_param_count, param_count) =
715 def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len())); 757 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); 758 let mut substs = Vec::with_capacity(parent_param_count + param_count);
717 for _ in 0..parent_param_count { 759 if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
718 substs.push(Ty::Unknown); 760 for param in &parent_generics.params {
761 if param.name.as_known_name() == Some(crate::KnownName::SelfType) {
762 substs.push(receiver_ty.clone());
763 } else {
764 substs.push(Ty::Unknown);
765 }
766 }
719 } 767 }
720 // handle provided type arguments 768 // handle provided type arguments
721 if let Some(generic_args) = generic_args { 769 if let Some(generic_args) = generic_args {
@@ -817,6 +865,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
817 (Vec::new(), Ty::Unknown) 865 (Vec::new(), Ty::Unknown)
818 } 866 }
819 }; 867 };
868 // FIXME register obligations from where clauses from the function
820 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown)); 869 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
821 for (arg, param) in args.iter().zip(param_iter) { 870 for (arg, param) in args.iter().zip(param_iter) {
822 self.infer_expr(*arg, &Expectation::has_type(param)); 871 self.infer_expr(*arg, &Expectation::has_type(param));
@@ -838,7 +887,11 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
838 } 887 }
839 None => (receiver_ty, Ty::Unknown, None), 888 None => (receiver_ty, Ty::Unknown, None),
840 }; 889 };
841 let substs = self.substs_for_method_call(def_generics, generic_args); 890 let substs = self.substs_for_method_call(
891 def_generics.clone(),
892 generic_args,
893 &derefed_receiver_ty,
894 );
842 let method_ty = method_ty.apply_substs(substs); 895 let method_ty = method_ty.apply_substs(substs);
843 let method_ty = self.insert_type_vars(method_ty); 896 let method_ty = self.insert_type_vars(method_ty);
844 let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty { 897 let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty {
@@ -859,6 +912,24 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
859 let sig = self.db.callable_item_signature(def); 912 let sig = self.db.callable_item_signature(def);
860 let ret_ty = sig.ret().clone().subst(&a_ty.parameters); 913 let ret_ty = sig.ret().clone().subst(&a_ty.parameters);
861 914
915 // add obligation for trait implementation, if this is a trait method
916 // FIXME also register obligations from where clauses from the trait or impl and method
917 match def {
918 CallableDef::Function(f) => {
919 if let Some(trait_) = f.parent_trait(self.db) {
920 // construct a TraitDef
921 let substs = a_ty.parameters.prefix(
922 def_generics
923 .expect("trait parent should always have generics")
924 .count_parent_params(),
925 );
926 self.obligations
927 .push(Obligation::Trait(TraitRef { trait_, substs }));
928 }
929 }
930 CallableDef::Struct(_) | CallableDef::EnumVariant(_) => {}
931 }
932
862 if !sig.params().is_empty() { 933 if !sig.params().is_empty() {
863 let mut params_iter = sig 934 let mut params_iter = sig
864 .params() 935 .params()
@@ -875,6 +946,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
875 _ => (Ty::Unknown, Vec::new(), Ty::Unknown), 946 _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
876 }; 947 };
877 // Apply autoref so the below unification works correctly 948 // Apply autoref so the below unification works correctly
949 // FIXME: return correct autorefs/derefs from lookup_method
878 let actual_receiver_ty = match expected_receiver_ty.as_reference() { 950 let actual_receiver_ty = match expected_receiver_ty.as_reference() {
879 Some((_, mutability)) => { 951 Some((_, mutability)) => {
880 Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty) 952 Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty)
@@ -1180,7 +1252,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
1180 1252
1181/// The ID of a type variable. 1253/// The ID of a type variable.
1182#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] 1254#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
1183pub struct TypeVarId(u32); 1255pub struct TypeVarId(pub(super) u32);
1184 1256
1185impl UnifyKey for TypeVarId { 1257impl UnifyKey for TypeVarId {
1186 type Value = TypeVarValue; 1258 type Value = TypeVarValue;
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 4523b3954..ccacb5e73 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -206,6 +206,7 @@ impl TraitRef {
206 db: &impl HirDatabase, 206 db: &impl HirDatabase,
207 resolver: &Resolver, 207 resolver: &Resolver,
208 type_ref: &TypeRef, 208 type_ref: &TypeRef,
209 explicit_self_ty: Option<Ty>,
209 ) -> Option<Self> { 210 ) -> Option<Self> {
210 let path = match type_ref { 211 let path = match type_ref {
211 TypeRef::Path(path) => path, 212 TypeRef::Path(path) => path,
@@ -215,7 +216,13 @@ impl TraitRef {
215 Resolution::Def(ModuleDef::Trait(tr)) => tr, 216 Resolution::Def(ModuleDef::Trait(tr)) => tr,
216 _ => return None, 217 _ => return None,
217 }; 218 };
218 let substs = Self::substs_from_path(db, resolver, path, resolved); 219 let mut substs = Self::substs_from_path(db, resolver, path, resolved);
220 if let Some(self_ty) = explicit_self_ty {
221 // FIXME this could be nicer
222 let mut substs_vec = substs.0.to_vec();
223 substs_vec[0] = self_ty;
224 substs.0 = substs_vec.into();
225 }
219 Some(TraitRef { trait_: resolved, substs }) 226 Some(TraitRef { trait_: resolved, substs })
220 } 227 }
221 228
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index aac7d6384..f69b8304b 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -108,20 +108,6 @@ impl CrateImplBlocks {
108 } 108 }
109} 109}
110 110
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> { 111fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> {
126 match ty { 112 match ty {
127 Ty::Apply(a_ty) => match a_ty.ctor { 113 Ty::Apply(a_ty) => match a_ty.ctor {
@@ -142,6 +128,7 @@ impl Ty {
142 resolver: &Resolver, 128 resolver: &Resolver,
143 ) -> Option<(Ty, Function)> { 129 ) -> Option<(Ty, Function)> {
144 // FIXME: trait methods should be used before autoderefs 130 // FIXME: trait methods should be used before autoderefs
131 // (and we need to do autoderefs for trait method calls as well)
145 let inherent_method = self.clone().iterate_methods(db, |ty, f| { 132 let inherent_method = self.clone().iterate_methods(db, |ty, f| {
146 let sig = f.signature(db); 133 let sig = f.signature(db);
147 if sig.name() == name && sig.has_self_param() { 134 if sig.name() == name && sig.has_self_param() {
@@ -174,24 +161,15 @@ impl Ty {
174 } 161 }
175 } 162 }
176 } 163 }
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)| { 164 candidates.retain(|(t, _m)| {
188 // FIXME construct substs of the correct length for the trait 165 let trait_ref =
189 // - check in rustc whether it does anything smarter than putting variables for everything 166 TraitRef { trait_: *t, substs: fresh_substs_for_trait(db, *t, self.clone()) };
190 let trait_ref = TraitRef { trait_: *t, substs: Substs::single(self.clone()) }; 167 let (trait_ref, _) = super::traits::canonicalize(trait_ref);
191 db.implements(trait_ref) 168 db.implements(trait_ref).is_some()
192 }); 169 });
193 // FIXME if there's multiple candidates here, that's an ambiguity error 170 // FIXME if there's multiple candidates here, that's an ambiguity error
194 let (_chosen_trait, chosen_method) = candidates.first()?; 171 let (_chosen_trait, chosen_method) = candidates.first()?;
172 // FIXME return correct receiver type
195 Some((self.clone(), *chosen_method)) 173 Some((self.clone(), *chosen_method))
196 } 174 }
197 175
@@ -254,3 +232,16 @@ impl Ty {
254 None 232 None
255 } 233 }
256} 234}
235
236fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
237 let mut substs = Vec::new();
238 let mut counter = 0;
239 let generics = tr.generic_params(db);
240 substs.push(self_ty);
241 substs.extend(generics.params_including_parent().into_iter().skip(1).map(|_p| {
242 let fresh_var = Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(counter)));
243 counter += 1;
244 fresh_var
245 }));
246 substs.into()
247}
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}