aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src/ty
diff options
context:
space:
mode:
authorbors[bot] <bors[bot]@users.noreply.github.com>2019-04-14 15:06:48 +0100
committerbors[bot] <bors[bot]@users.noreply.github.com>2019-04-14 15:06:48 +0100
commitfcbd0269545f2b6687a64a868654c74f876b7851 (patch)
treecb439cc77b5445f00cda86e932c199cb69ae47d6 /crates/ra_hir/src/ty
parent23b876bc3b00c53ce24b8a99b4f4bf190fc6300e (diff)
parent8bcbcc454cbb48b897083c122566c0b4c2b780aa (diff)
Merge #1120
1120: More trait infrastructure r=matklad a=flodiebold This adds enough trait infrastructure to be able to make some deductions about type variables when resolving trait methods, while at the same time doing as little as possible that will be later replaced by Chalk :smile: E.g. (as the tests show) if we have ```rust trait Trait<T> { fn method(self) -> T } impl Trait<u32> for S {} ... S.method() ``` we can infer that the return type is `u32`. On the other hand the unification logic is so primitive that we can't handle e.g. `impl<T> Trait<T> for S<T>`. It's all quite hacky, I plan to refactor the parts that will stay, while hopefully the other parts will be replaced soon :slightly_smiling_face: In particular, we need to handle 'containers' (impls and trait defs) more cleanly, and I need to reorganize the method resolution / type inference code... Co-authored-by: Florian Diebold <[email protected]>
Diffstat (limited to 'crates/ra_hir/src/ty')
-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
5 files changed, 411 insertions, 162 deletions
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}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-05 05:51:14 +0000