diff options
Diffstat (limited to 'crates')
-rw-r--r-- | crates/ra_assists/src/fill_match_arms.rs | 79 | ||||
-rw-r--r-- | crates/ra_hir/src/code_model_api.rs | 4 | ||||
-rw-r--r-- | crates/ra_hir/src/ty.rs | 1468 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/infer.rs | 1099 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/lower.rs | 333 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/op.rs | 81 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap | 8 | ||||
-rw-r--r-- | crates/ra_hir/src/ty/tests.rs | 1 |
8 files changed, 1618 insertions, 1455 deletions
diff --git a/crates/ra_assists/src/fill_match_arms.rs b/crates/ra_assists/src/fill_match_arms.rs index d8e40b4b7..6bf6e7332 100644 --- a/crates/ra_assists/src/fill_match_arms.rs +++ b/crates/ra_assists/src/fill_match_arms.rs | |||
@@ -28,6 +28,10 @@ pub(crate) fn fill_match_arms(mut ctx: AssistCtx<impl HirDatabase>) -> Option<As | |||
28 | let match_expr_ty = infer_result[node_expr].clone(); | 28 | let match_expr_ty = infer_result[node_expr].clone(); |
29 | let enum_def = match match_expr_ty { | 29 | let enum_def = match match_expr_ty { |
30 | Ty::Adt { def_id: AdtDef::Enum(e), .. } => e, | 30 | Ty::Adt { def_id: AdtDef::Enum(e), .. } => e, |
31 | Ty::Ref(adt, _) => match *adt { | ||
32 | Ty::Adt { def_id: AdtDef::Enum(e), .. } => e, | ||
33 | _ => return None, | ||
34 | }, | ||
31 | _ => return None, | 35 | _ => return None, |
32 | }; | 36 | }; |
33 | let enum_name = enum_def.name(ctx.db)?; | 37 | let enum_name = enum_def.name(ctx.db)?; |
@@ -119,6 +123,81 @@ mod tests { | |||
119 | "#, | 123 | "#, |
120 | ); | 124 | ); |
121 | } | 125 | } |
126 | |||
127 | #[test] | ||
128 | fn test_fill_match_arm_refs() { | ||
129 | check_assist( | ||
130 | fill_match_arms, | ||
131 | r#" | ||
132 | enum A { | ||
133 | As, | ||
134 | } | ||
135 | |||
136 | fn foo(a: &A) { | ||
137 | match a<|> { | ||
138 | } | ||
139 | } | ||
140 | "#, | ||
141 | r#" | ||
142 | enum A { | ||
143 | As, | ||
144 | } | ||
145 | |||
146 | fn foo(a: &A) { | ||
147 | match <|>a { | ||
148 | A::As => (), | ||
149 | } | ||
150 | } | ||
151 | "#, | ||
152 | ); | ||
153 | |||
154 | check_assist( | ||
155 | fill_match_arms, | ||
156 | r#" | ||
157 | enum A { | ||
158 | Es{x: usize, y: usize} | ||
159 | } | ||
160 | |||
161 | fn foo(a: &mut A) { | ||
162 | match a<|> { | ||
163 | } | ||
164 | } | ||
165 | "#, | ||
166 | r#" | ||
167 | enum A { | ||
168 | Es{x: usize, y: usize} | ||
169 | } | ||
170 | |||
171 | fn foo(a: &mut A) { | ||
172 | match <|>a { | ||
173 | A::Es{x, y} => (), | ||
174 | } | ||
175 | } | ||
176 | "#, | ||
177 | ); | ||
178 | |||
179 | check_assist( | ||
180 | fill_match_arms, | ||
181 | r#" | ||
182 | enum E { X, Y} | ||
183 | |||
184 | fn main() { | ||
185 | match &E::X<|> | ||
186 | } | ||
187 | "#, | ||
188 | r#" | ||
189 | enum E { X, Y} | ||
190 | |||
191 | fn main() { | ||
192 | match <|>&E::X { | ||
193 | E::X => (), | ||
194 | E::Y => (), | ||
195 | } | ||
196 | } | ||
197 | "#, | ||
198 | ); | ||
199 | } | ||
200 | |||
122 | #[test] | 201 | #[test] |
123 | fn fill_match_arms_no_body() { | 202 | fn fill_match_arms_no_body() { |
124 | check_assist( | 203 | check_assist( |
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs index 9da8a482d..9d0b40ce0 100644 --- a/crates/ra_hir/src/code_model_api.rs +++ b/crates/ra_hir/src/code_model_api.rs | |||
@@ -483,6 +483,10 @@ impl Function { | |||
483 | db.body_hir(*self) | 483 | db.body_hir(*self) |
484 | } | 484 | } |
485 | 485 | ||
486 | pub fn ty(&self, db: &impl HirDatabase) -> Ty { | ||
487 | db.type_for_def((*self).into(), Namespace::Values) | ||
488 | } | ||
489 | |||
486 | pub fn scopes(&self, db: &impl HirDatabase) -> ScopesWithSyntaxMapping { | 490 | pub fn scopes(&self, db: &impl HirDatabase) -> ScopesWithSyntaxMapping { |
487 | let scopes = db.expr_scopes(*self); | 491 | let scopes = db.expr_scopes(*self); |
488 | let syntax_mapping = db.body_syntax_mapping(*self); | 492 | let syntax_mapping = db.body_syntax_mapping(*self); |
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs index 34f9ccd07..e505c86e3 100644 --- a/crates/ra_hir/src/ty.rs +++ b/crates/ra_hir/src/ty.rs | |||
@@ -1,171 +1,24 @@ | |||
1 | //! The type system. We currently use this to infer types for completion. | 1 | //! The type system. We currently use this to infer types for completion, hover |
2 | //! | 2 | //! information and various assists. |
3 | //! For type inference, compare the implementations in rustc (the various | ||
4 | //! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and | ||
5 | //! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for | ||
6 | //! inference here is the `infer` function, which infers the types of all | ||
7 | //! expressions in a given function. | ||
8 | //! | ||
9 | //! The central struct here is `Ty`, which represents a type. During inference, | ||
10 | //! it can contain type 'variables' which represent currently unknown types; as | ||
11 | //! we walk through the expressions, we might determine that certain variables | ||
12 | //! need to be equal to each other, or to certain types. To record this, we use | ||
13 | //! the union-find implementation from the `ena` crate, which is extracted from | ||
14 | //! rustc. | ||
15 | 3 | ||
16 | mod autoderef; | 4 | mod autoderef; |
17 | pub(crate) mod primitive; | 5 | pub(crate) mod primitive; |
18 | #[cfg(test)] | 6 | #[cfg(test)] |
19 | mod tests; | 7 | mod tests; |
20 | pub(crate) mod method_resolution; | 8 | pub(crate) mod method_resolution; |
9 | mod op; | ||
10 | mod lower; | ||
11 | mod infer; | ||
21 | 12 | ||
22 | use std::borrow::Cow; | ||
23 | use std::iter::repeat; | ||
24 | use std::ops::Index; | ||
25 | use std::sync::Arc; | 13 | use std::sync::Arc; |
26 | use std::{fmt, mem}; | 14 | use std::{fmt, mem}; |
27 | 15 | ||
28 | use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError}; | ||
29 | use ra_arena::map::ArenaMap; | ||
30 | use join_to_string::join; | 16 | use join_to_string::join; |
31 | use rustc_hash::FxHashMap; | ||
32 | 17 | ||
33 | use test_utils::tested_by; | 18 | use crate::{Name, AdtDef, type_ref::Mutability}; |
34 | 19 | ||
35 | use crate::{ | 20 | pub(crate) use lower::{TypableDef, CallableDef, type_for_def, type_for_field}; |
36 | Function, Struct, StructField, Enum, EnumVariant, Path, Name, | 21 | pub(crate) use infer::{infer, InferenceResult, InferTy}; |
37 | FnSignature, ModuleDef, AdtDef, | ||
38 | HirDatabase, | ||
39 | type_ref::{TypeRef, Mutability}, | ||
40 | name::{KnownName}, | ||
41 | expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat, self}, | ||
42 | generics::GenericParams, | ||
43 | path::{ GenericArgs, GenericArg}, | ||
44 | adt::VariantDef, | ||
45 | resolve::{Resolver, Resolution}, nameres::Namespace | ||
46 | }; | ||
47 | |||
48 | /// The ID of a type variable. | ||
49 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | ||
50 | pub struct TypeVarId(u32); | ||
51 | |||
52 | impl UnifyKey for TypeVarId { | ||
53 | type Value = TypeVarValue; | ||
54 | |||
55 | fn index(&self) -> u32 { | ||
56 | self.0 | ||
57 | } | ||
58 | |||
59 | fn from_index(i: u32) -> Self { | ||
60 | TypeVarId(i) | ||
61 | } | ||
62 | |||
63 | fn tag() -> &'static str { | ||
64 | "TypeVarId" | ||
65 | } | ||
66 | } | ||
67 | |||
68 | /// The value of a type variable: either we already know the type, or we don't | ||
69 | /// know it yet. | ||
70 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
71 | pub enum TypeVarValue { | ||
72 | Known(Ty), | ||
73 | Unknown, | ||
74 | } | ||
75 | |||
76 | impl TypeVarValue { | ||
77 | fn known(&self) -> Option<&Ty> { | ||
78 | match self { | ||
79 | TypeVarValue::Known(ty) => Some(ty), | ||
80 | TypeVarValue::Unknown => None, | ||
81 | } | ||
82 | } | ||
83 | } | ||
84 | |||
85 | impl UnifyValue for TypeVarValue { | ||
86 | type Error = NoError; | ||
87 | |||
88 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | ||
89 | match (value1, value2) { | ||
90 | // We should never equate two type variables, both of which have | ||
91 | // known types. Instead, we recursively equate those types. | ||
92 | (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( | ||
93 | "equating two type variables, both of which have known types: {:?} and {:?}", | ||
94 | t1, t2 | ||
95 | ), | ||
96 | |||
97 | // If one side is known, prefer that one. | ||
98 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | ||
99 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | ||
100 | |||
101 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | ||
102 | } | ||
103 | } | ||
104 | } | ||
105 | |||
106 | /// The kinds of placeholders we need during type inference. There's separate | ||
107 | /// values for general types, and for integer and float variables. The latter | ||
108 | /// two are used for inference of literal values (e.g. `100` could be one of | ||
109 | /// several integer types). | ||
110 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] | ||
111 | pub enum InferTy { | ||
112 | TypeVar(TypeVarId), | ||
113 | IntVar(TypeVarId), | ||
114 | FloatVar(TypeVarId), | ||
115 | } | ||
116 | |||
117 | impl InferTy { | ||
118 | fn to_inner(self) -> TypeVarId { | ||
119 | match self { | ||
120 | InferTy::TypeVar(ty) | InferTy::IntVar(ty) | InferTy::FloatVar(ty) => ty, | ||
121 | } | ||
122 | } | ||
123 | |||
124 | fn fallback_value(self) -> Ty { | ||
125 | match self { | ||
126 | InferTy::TypeVar(..) => Ty::Unknown, | ||
127 | InferTy::IntVar(..) => { | ||
128 | Ty::Int(primitive::UncertainIntTy::Signed(primitive::IntTy::I32)) | ||
129 | } | ||
130 | InferTy::FloatVar(..) => { | ||
131 | Ty::Float(primitive::UncertainFloatTy::Known(primitive::FloatTy::F64)) | ||
132 | } | ||
133 | } | ||
134 | } | ||
135 | } | ||
136 | |||
137 | /// When inferring an expression, we propagate downward whatever type hint we | ||
138 | /// are able in the form of an `Expectation`. | ||
139 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
140 | struct Expectation { | ||
141 | ty: Ty, | ||
142 | // TODO: In some cases, we need to be aware whether the expectation is that | ||
143 | // the type match exactly what we passed, or whether it just needs to be | ||
144 | // coercible to the expected type. See Expectation::rvalue_hint in rustc. | ||
145 | } | ||
146 | |||
147 | impl Expectation { | ||
148 | /// The expectation that the type of the expression needs to equal the given | ||
149 | /// type. | ||
150 | fn has_type(ty: Ty) -> Self { | ||
151 | Expectation { ty } | ||
152 | } | ||
153 | |||
154 | /// This expresses no expectation on the type. | ||
155 | fn none() -> Self { | ||
156 | Expectation { ty: Ty::Unknown } | ||
157 | } | ||
158 | } | ||
159 | |||
160 | /// A list of substitutions for generic parameters. | ||
161 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
162 | pub struct Substs(Arc<[Ty]>); | ||
163 | |||
164 | impl Substs { | ||
165 | pub fn empty() -> Substs { | ||
166 | Substs(Arc::new([])) | ||
167 | } | ||
168 | } | ||
169 | 22 | ||
170 | /// A type. This is based on the `TyKind` enum in rustc (librustc/ty/sty.rs). | 23 | /// A type. This is based on the `TyKind` enum in rustc (librustc/ty/sty.rs). |
171 | /// | 24 | /// |
@@ -295,6 +148,16 @@ pub enum Ty { | |||
295 | Unknown, | 148 | Unknown, |
296 | } | 149 | } |
297 | 150 | ||
151 | /// A list of substitutions for generic parameters. | ||
152 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
153 | pub struct Substs(Arc<[Ty]>); | ||
154 | |||
155 | impl Substs { | ||
156 | pub fn empty() -> Substs { | ||
157 | Substs(Arc::new([])) | ||
158 | } | ||
159 | } | ||
160 | |||
298 | /// A function signature. | 161 | /// A function signature. |
299 | #[derive(Clone, PartialEq, Eq, Debug)] | 162 | #[derive(Clone, PartialEq, Eq, Debug)] |
300 | pub struct FnSig { | 163 | pub struct FnSig { |
@@ -303,150 +166,6 @@ pub struct FnSig { | |||
303 | } | 166 | } |
304 | 167 | ||
305 | impl Ty { | 168 | impl Ty { |
306 | pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self { | ||
307 | match type_ref { | ||
308 | TypeRef::Never => Ty::Never, | ||
309 | TypeRef::Tuple(inner) => { | ||
310 | let inner_tys = | ||
311 | inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); | ||
312 | Ty::Tuple(inner_tys.into()) | ||
313 | } | ||
314 | TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path), | ||
315 | TypeRef::RawPtr(inner, mutability) => { | ||
316 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
317 | Ty::RawPtr(Arc::new(inner_ty), *mutability) | ||
318 | } | ||
319 | TypeRef::Array(inner) => { | ||
320 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
321 | Ty::Array(Arc::new(inner_ty)) | ||
322 | } | ||
323 | TypeRef::Slice(inner) => { | ||
324 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
325 | Ty::Slice(Arc::new(inner_ty)) | ||
326 | } | ||
327 | TypeRef::Reference(inner, mutability) => { | ||
328 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
329 | Ty::Ref(Arc::new(inner_ty), *mutability) | ||
330 | } | ||
331 | TypeRef::Placeholder => Ty::Unknown, | ||
332 | TypeRef::Fn(params) => { | ||
333 | let mut inner_tys = | ||
334 | params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); | ||
335 | let return_ty = | ||
336 | inner_tys.pop().expect("TypeRef::Fn should always have at least return type"); | ||
337 | let sig = FnSig { input: inner_tys, output: return_ty }; | ||
338 | Ty::FnPtr(Arc::new(sig)) | ||
339 | } | ||
340 | TypeRef::Error => Ty::Unknown, | ||
341 | } | ||
342 | } | ||
343 | |||
344 | pub(crate) fn from_hir_path(db: &impl HirDatabase, resolver: &Resolver, path: &Path) -> Self { | ||
345 | if let Some(name) = path.as_ident() { | ||
346 | // TODO handle primitive type names in resolver as well? | ||
347 | if let Some(int_ty) = primitive::UncertainIntTy::from_name(name) { | ||
348 | return Ty::Int(int_ty); | ||
349 | } else if let Some(float_ty) = primitive::UncertainFloatTy::from_name(name) { | ||
350 | return Ty::Float(float_ty); | ||
351 | } else if let Some(known) = name.as_known_name() { | ||
352 | match known { | ||
353 | KnownName::Bool => return Ty::Bool, | ||
354 | KnownName::Char => return Ty::Char, | ||
355 | KnownName::Str => return Ty::Str, | ||
356 | _ => {} | ||
357 | } | ||
358 | } | ||
359 | } | ||
360 | |||
361 | // Resolve the path (in type namespace) | ||
362 | let resolution = resolver.resolve_path(db, path).take_types(); | ||
363 | |||
364 | let def = match resolution { | ||
365 | Some(Resolution::Def(def)) => def, | ||
366 | Some(Resolution::LocalBinding(..)) => { | ||
367 | // this should never happen | ||
368 | panic!("path resolved to local binding in type ns"); | ||
369 | } | ||
370 | Some(Resolution::GenericParam(idx)) => { | ||
371 | return Ty::Param { | ||
372 | idx, | ||
373 | // TODO: maybe return name in resolution? | ||
374 | name: path | ||
375 | .as_ident() | ||
376 | .expect("generic param should be single-segment path") | ||
377 | .clone(), | ||
378 | }; | ||
379 | } | ||
380 | Some(Resolution::SelfType(impl_block)) => { | ||
381 | return impl_block.target_ty(db); | ||
382 | } | ||
383 | None => return Ty::Unknown, | ||
384 | }; | ||
385 | |||
386 | let typable: TypableDef = match def.into() { | ||
387 | None => return Ty::Unknown, | ||
388 | Some(it) => it, | ||
389 | }; | ||
390 | let ty = db.type_for_def(typable, Namespace::Types); | ||
391 | let substs = Ty::substs_from_path(db, resolver, path, typable); | ||
392 | ty.apply_substs(substs) | ||
393 | } | ||
394 | |||
395 | /// Collect generic arguments from a path into a `Substs`. See also | ||
396 | /// `create_substs_for_ast_path` and `def_to_ty` in rustc. | ||
397 | fn substs_from_path( | ||
398 | db: &impl HirDatabase, | ||
399 | resolver: &Resolver, | ||
400 | path: &Path, | ||
401 | resolved: TypableDef, | ||
402 | ) -> Substs { | ||
403 | let mut substs = Vec::new(); | ||
404 | let last = path.segments.last().expect("path should have at least one segment"); | ||
405 | let (def_generics, segment) = match resolved { | ||
406 | TypableDef::Function(func) => (func.generic_params(db), last), | ||
407 | TypableDef::Struct(s) => (s.generic_params(db), last), | ||
408 | TypableDef::Enum(e) => (e.generic_params(db), last), | ||
409 | TypableDef::EnumVariant(var) => { | ||
410 | // the generic args for an enum variant may be either specified | ||
411 | // on the segment referring to the enum, or on the segment | ||
412 | // referring to the variant. So `Option::<T>::None` and | ||
413 | // `Option::None::<T>` are both allowed (though the former is | ||
414 | // preferred). See also `def_ids_for_path_segments` in rustc. | ||
415 | let len = path.segments.len(); | ||
416 | let segment = if len >= 2 && path.segments[len - 2].args_and_bindings.is_some() { | ||
417 | // Option::<T>::None | ||
418 | &path.segments[len - 2] | ||
419 | } else { | ||
420 | // Option::None::<T> | ||
421 | last | ||
422 | }; | ||
423 | (var.parent_enum(db).generic_params(db), segment) | ||
424 | } | ||
425 | }; | ||
426 | let parent_param_count = def_generics.count_parent_params(); | ||
427 | substs.extend((0..parent_param_count).map(|_| Ty::Unknown)); | ||
428 | if let Some(generic_args) = &segment.args_and_bindings { | ||
429 | // if args are provided, it should be all of them, but we can't rely on that | ||
430 | let param_count = def_generics.params.len(); | ||
431 | for arg in generic_args.args.iter().take(param_count) { | ||
432 | match arg { | ||
433 | GenericArg::Type(type_ref) => { | ||
434 | let ty = Ty::from_hir(db, resolver, type_ref); | ||
435 | substs.push(ty); | ||
436 | } | ||
437 | } | ||
438 | } | ||
439 | } | ||
440 | // add placeholders for args that were not provided | ||
441 | // TODO: handle defaults | ||
442 | let supplied_params = substs.len(); | ||
443 | for _ in supplied_params..def_generics.count_params_including_parent() { | ||
444 | substs.push(Ty::Unknown); | ||
445 | } | ||
446 | assert_eq!(substs.len(), def_generics.count_params_including_parent()); | ||
447 | Substs(substs.into()) | ||
448 | } | ||
449 | |||
450 | pub fn unit() -> Self { | 169 | pub fn unit() -> Self { |
451 | Ty::Tuple(Arc::new([])) | 170 | Ty::Tuple(Arc::new([])) |
452 | } | 171 | } |
@@ -652,1154 +371,3 @@ impl fmt::Display for Ty { | |||
652 | } | 371 | } |
653 | } | 372 | } |
654 | } | 373 | } |
655 | |||
656 | // Functions returning declared types for items | ||
657 | |||
658 | /// Compute the declared type of a function. This should not need to look at the | ||
659 | /// function body. | ||
660 | fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { | ||
661 | let signature = def.signature(db); | ||
662 | let resolver = def.resolver(db); | ||
663 | let generics = def.generic_params(db); | ||
664 | let name = def.name(db); | ||
665 | let input = | ||
666 | signature.params().iter().map(|tr| Ty::from_hir(db, &resolver, tr)).collect::<Vec<_>>(); | ||
667 | let output = Ty::from_hir(db, &resolver, signature.ret_type()); | ||
668 | let sig = Arc::new(FnSig { input, output }); | ||
669 | let substs = make_substs(&generics); | ||
670 | Ty::FnDef { def: def.into(), sig, name, substs } | ||
671 | } | ||
672 | |||
673 | /// Compute the type of a tuple struct constructor. | ||
674 | fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty { | ||
675 | let var_data = def.variant_data(db); | ||
676 | let fields = match var_data.fields() { | ||
677 | Some(fields) => fields, | ||
678 | None => return type_for_struct(db, def), // Unit struct | ||
679 | }; | ||
680 | let resolver = def.resolver(db); | ||
681 | let generics = def.generic_params(db); | ||
682 | let name = def.name(db).unwrap_or_else(Name::missing); | ||
683 | let input = fields | ||
684 | .iter() | ||
685 | .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) | ||
686 | .collect::<Vec<_>>(); | ||
687 | let output = type_for_struct(db, def); | ||
688 | let sig = Arc::new(FnSig { input, output }); | ||
689 | let substs = make_substs(&generics); | ||
690 | Ty::FnDef { def: def.into(), sig, name, substs } | ||
691 | } | ||
692 | |||
693 | /// Compute the type of a tuple enum variant constructor. | ||
694 | fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) -> Ty { | ||
695 | let var_data = def.variant_data(db); | ||
696 | let fields = match var_data.fields() { | ||
697 | Some(fields) => fields, | ||
698 | None => return type_for_enum(db, def.parent_enum(db)), // Unit variant | ||
699 | }; | ||
700 | let resolver = def.parent_enum(db).resolver(db); | ||
701 | let generics = def.parent_enum(db).generic_params(db); | ||
702 | let name = def.name(db).unwrap_or_else(Name::missing); | ||
703 | let input = fields | ||
704 | .iter() | ||
705 | .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) | ||
706 | .collect::<Vec<_>>(); | ||
707 | let substs = make_substs(&generics); | ||
708 | let output = type_for_enum(db, def.parent_enum(db)).apply_substs(substs.clone()); | ||
709 | let sig = Arc::new(FnSig { input, output }); | ||
710 | Ty::FnDef { def: def.into(), sig, name, substs } | ||
711 | } | ||
712 | |||
713 | fn make_substs(generics: &GenericParams) -> Substs { | ||
714 | Substs( | ||
715 | generics | ||
716 | .params_including_parent() | ||
717 | .into_iter() | ||
718 | .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() }) | ||
719 | .collect::<Vec<_>>() | ||
720 | .into(), | ||
721 | ) | ||
722 | } | ||
723 | |||
724 | fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { | ||
725 | let generics = s.generic_params(db); | ||
726 | Ty::Adt { | ||
727 | def_id: s.into(), | ||
728 | name: s.name(db).unwrap_or_else(Name::missing), | ||
729 | substs: make_substs(&generics), | ||
730 | } | ||
731 | } | ||
732 | |||
733 | fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { | ||
734 | let generics = s.generic_params(db); | ||
735 | Ty::Adt { | ||
736 | def_id: s.into(), | ||
737 | name: s.name(db).unwrap_or_else(Name::missing), | ||
738 | substs: make_substs(&generics), | ||
739 | } | ||
740 | } | ||
741 | |||
742 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] | ||
743 | pub enum TypableDef { | ||
744 | Function(Function), | ||
745 | Struct(Struct), | ||
746 | Enum(Enum), | ||
747 | EnumVariant(EnumVariant), | ||
748 | } | ||
749 | impl_froms!(TypableDef: Function, Struct, Enum, EnumVariant); | ||
750 | |||
751 | impl From<ModuleDef> for Option<TypableDef> { | ||
752 | fn from(def: ModuleDef) -> Option<TypableDef> { | ||
753 | let res = match def { | ||
754 | ModuleDef::Function(f) => f.into(), | ||
755 | ModuleDef::Struct(s) => s.into(), | ||
756 | ModuleDef::Enum(e) => e.into(), | ||
757 | ModuleDef::EnumVariant(v) => v.into(), | ||
758 | ModuleDef::Const(_) | ||
759 | | ModuleDef::Static(_) | ||
760 | | ModuleDef::Module(_) | ||
761 | | ModuleDef::Trait(_) | ||
762 | | ModuleDef::Type(_) => return None, | ||
763 | }; | ||
764 | Some(res) | ||
765 | } | ||
766 | } | ||
767 | |||
768 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] | ||
769 | pub enum CallableDef { | ||
770 | Function(Function), | ||
771 | Struct(Struct), | ||
772 | EnumVariant(EnumVariant), | ||
773 | } | ||
774 | impl_froms!(CallableDef: Function, Struct, EnumVariant); | ||
775 | |||
776 | pub(super) fn type_for_def(db: &impl HirDatabase, def: TypableDef, ns: Namespace) -> Ty { | ||
777 | match (def, ns) { | ||
778 | (TypableDef::Function(f), Namespace::Values) => type_for_fn(db, f), | ||
779 | (TypableDef::Struct(s), Namespace::Types) => type_for_struct(db, s), | ||
780 | (TypableDef::Struct(s), Namespace::Values) => type_for_struct_constructor(db, s), | ||
781 | (TypableDef::Enum(e), Namespace::Types) => type_for_enum(db, e), | ||
782 | (TypableDef::EnumVariant(v), Namespace::Values) => type_for_enum_variant_constructor(db, v), | ||
783 | |||
784 | // 'error' cases: | ||
785 | (TypableDef::Function(_), Namespace::Types) => Ty::Unknown, | ||
786 | (TypableDef::Enum(_), Namespace::Values) => Ty::Unknown, | ||
787 | (TypableDef::EnumVariant(_), Namespace::Types) => Ty::Unknown, | ||
788 | } | ||
789 | } | ||
790 | |||
791 | pub(super) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty { | ||
792 | let parent_def = field.parent_def(db); | ||
793 | let resolver = match parent_def { | ||
794 | VariantDef::Struct(it) => it.resolver(db), | ||
795 | VariantDef::EnumVariant(it) => it.parent_enum(db).resolver(db), | ||
796 | }; | ||
797 | let var_data = parent_def.variant_data(db); | ||
798 | let type_ref = &var_data.fields().unwrap()[field.id].type_ref; | ||
799 | Ty::from_hir(db, &resolver, type_ref) | ||
800 | } | ||
801 | |||
802 | /// The result of type inference: A mapping from expressions and patterns to types. | ||
803 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
804 | pub struct InferenceResult { | ||
805 | /// For each method call expr, records the function it resolves to. | ||
806 | method_resolutions: FxHashMap<ExprId, Function>, | ||
807 | /// For each field access expr, records the field it resolves to. | ||
808 | field_resolutions: FxHashMap<ExprId, StructField>, | ||
809 | type_of_expr: ArenaMap<ExprId, Ty>, | ||
810 | type_of_pat: ArenaMap<PatId, Ty>, | ||
811 | } | ||
812 | |||
813 | impl InferenceResult { | ||
814 | pub fn method_resolution(&self, expr: ExprId) -> Option<Function> { | ||
815 | self.method_resolutions.get(&expr).map(|it| *it) | ||
816 | } | ||
817 | pub fn field_resolution(&self, expr: ExprId) -> Option<StructField> { | ||
818 | self.field_resolutions.get(&expr).map(|it| *it) | ||
819 | } | ||
820 | } | ||
821 | |||
822 | impl Index<ExprId> for InferenceResult { | ||
823 | type Output = Ty; | ||
824 | |||
825 | fn index(&self, expr: ExprId) -> &Ty { | ||
826 | self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown) | ||
827 | } | ||
828 | } | ||
829 | |||
830 | impl Index<PatId> for InferenceResult { | ||
831 | type Output = Ty; | ||
832 | |||
833 | fn index(&self, pat: PatId) -> &Ty { | ||
834 | self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown) | ||
835 | } | ||
836 | } | ||
837 | |||
838 | /// The inference context contains all information needed during type inference. | ||
839 | #[derive(Clone, Debug)] | ||
840 | struct InferenceContext<'a, D: HirDatabase> { | ||
841 | db: &'a D, | ||
842 | body: Arc<Body>, | ||
843 | resolver: Resolver, | ||
844 | var_unification_table: InPlaceUnificationTable<TypeVarId>, | ||
845 | method_resolutions: FxHashMap<ExprId, Function>, | ||
846 | field_resolutions: FxHashMap<ExprId, StructField>, | ||
847 | type_of_expr: ArenaMap<ExprId, Ty>, | ||
848 | type_of_pat: ArenaMap<PatId, Ty>, | ||
849 | /// The return type of the function being inferred. | ||
850 | return_ty: Ty, | ||
851 | } | ||
852 | |||
853 | fn binary_op_return_ty(op: BinaryOp, rhs_ty: Ty) -> Ty { | ||
854 | match op { | ||
855 | BinaryOp::BooleanOr | ||
856 | | BinaryOp::BooleanAnd | ||
857 | | BinaryOp::EqualityTest | ||
858 | | BinaryOp::NegatedEqualityTest | ||
859 | | BinaryOp::LesserEqualTest | ||
860 | | BinaryOp::GreaterEqualTest | ||
861 | | BinaryOp::LesserTest | ||
862 | | BinaryOp::GreaterTest => Ty::Bool, | ||
863 | BinaryOp::Assignment | ||
864 | | BinaryOp::AddAssign | ||
865 | | BinaryOp::SubAssign | ||
866 | | BinaryOp::DivAssign | ||
867 | | BinaryOp::MulAssign | ||
868 | | BinaryOp::RemAssign | ||
869 | | BinaryOp::ShrAssign | ||
870 | | BinaryOp::ShlAssign | ||
871 | | BinaryOp::BitAndAssign | ||
872 | | BinaryOp::BitOrAssign | ||
873 | | BinaryOp::BitXorAssign => Ty::unit(), | ||
874 | BinaryOp::Addition | ||
875 | | BinaryOp::Subtraction | ||
876 | | BinaryOp::Multiplication | ||
877 | | BinaryOp::Division | ||
878 | | BinaryOp::Remainder | ||
879 | | BinaryOp::LeftShift | ||
880 | | BinaryOp::RightShift | ||
881 | | BinaryOp::BitwiseAnd | ||
882 | | BinaryOp::BitwiseOr | ||
883 | | BinaryOp::BitwiseXor => match rhs_ty { | ||
884 | Ty::Int(..) | ||
885 | | Ty::Float(..) | ||
886 | | Ty::Infer(InferTy::IntVar(..)) | ||
887 | | Ty::Infer(InferTy::FloatVar(..)) => rhs_ty, | ||
888 | _ => Ty::Unknown, | ||
889 | }, | ||
890 | BinaryOp::RangeRightOpen | BinaryOp::RangeRightClosed => Ty::Unknown, | ||
891 | } | ||
892 | } | ||
893 | |||
894 | fn binary_op_rhs_expectation(op: BinaryOp, lhs_ty: Ty) -> Ty { | ||
895 | match op { | ||
896 | BinaryOp::BooleanAnd | BinaryOp::BooleanOr => Ty::Bool, | ||
897 | BinaryOp::Assignment | BinaryOp::EqualityTest => match lhs_ty { | ||
898 | Ty::Int(..) | Ty::Float(..) | Ty::Str | Ty::Char | Ty::Bool => lhs_ty, | ||
899 | _ => Ty::Unknown, | ||
900 | }, | ||
901 | BinaryOp::LesserEqualTest | ||
902 | | BinaryOp::GreaterEqualTest | ||
903 | | BinaryOp::LesserTest | ||
904 | | BinaryOp::GreaterTest | ||
905 | | BinaryOp::AddAssign | ||
906 | | BinaryOp::SubAssign | ||
907 | | BinaryOp::DivAssign | ||
908 | | BinaryOp::MulAssign | ||
909 | | BinaryOp::RemAssign | ||
910 | | BinaryOp::ShrAssign | ||
911 | | BinaryOp::ShlAssign | ||
912 | | BinaryOp::BitAndAssign | ||
913 | | BinaryOp::BitOrAssign | ||
914 | | BinaryOp::BitXorAssign | ||
915 | | BinaryOp::Addition | ||
916 | | BinaryOp::Subtraction | ||
917 | | BinaryOp::Multiplication | ||
918 | | BinaryOp::Division | ||
919 | | BinaryOp::Remainder | ||
920 | | BinaryOp::LeftShift | ||
921 | | BinaryOp::RightShift | ||
922 | | BinaryOp::BitwiseAnd | ||
923 | | BinaryOp::BitwiseOr | ||
924 | | BinaryOp::BitwiseXor => match lhs_ty { | ||
925 | Ty::Int(..) | Ty::Float(..) => lhs_ty, | ||
926 | _ => Ty::Unknown, | ||
927 | }, | ||
928 | _ => Ty::Unknown, | ||
929 | } | ||
930 | } | ||
931 | |||
932 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | ||
933 | fn new(db: &'a D, body: Arc<Body>, resolver: Resolver) -> Self { | ||
934 | InferenceContext { | ||
935 | method_resolutions: FxHashMap::default(), | ||
936 | field_resolutions: FxHashMap::default(), | ||
937 | type_of_expr: ArenaMap::default(), | ||
938 | type_of_pat: ArenaMap::default(), | ||
939 | var_unification_table: InPlaceUnificationTable::new(), | ||
940 | return_ty: Ty::Unknown, // set in collect_fn_signature | ||
941 | db, | ||
942 | body, | ||
943 | resolver, | ||
944 | } | ||
945 | } | ||
946 | |||
947 | fn resolve_all(mut self) -> InferenceResult { | ||
948 | let mut tv_stack = Vec::new(); | ||
949 | let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default()); | ||
950 | for ty in expr_types.values_mut() { | ||
951 | let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); | ||
952 | *ty = resolved; | ||
953 | } | ||
954 | let mut pat_types = mem::replace(&mut self.type_of_pat, ArenaMap::default()); | ||
955 | for ty in pat_types.values_mut() { | ||
956 | let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); | ||
957 | *ty = resolved; | ||
958 | } | ||
959 | InferenceResult { | ||
960 | method_resolutions: self.method_resolutions, | ||
961 | field_resolutions: self.field_resolutions, | ||
962 | type_of_expr: expr_types, | ||
963 | type_of_pat: pat_types, | ||
964 | } | ||
965 | } | ||
966 | |||
967 | fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) { | ||
968 | self.type_of_expr.insert(expr, ty); | ||
969 | } | ||
970 | |||
971 | fn write_method_resolution(&mut self, expr: ExprId, func: Function) { | ||
972 | self.method_resolutions.insert(expr, func); | ||
973 | } | ||
974 | |||
975 | fn write_field_resolution(&mut self, expr: ExprId, field: StructField) { | ||
976 | self.field_resolutions.insert(expr, field); | ||
977 | } | ||
978 | |||
979 | fn write_pat_ty(&mut self, pat: PatId, ty: Ty) { | ||
980 | self.type_of_pat.insert(pat, ty); | ||
981 | } | ||
982 | |||
983 | fn make_ty(&mut self, type_ref: &TypeRef) -> Ty { | ||
984 | let ty = Ty::from_hir( | ||
985 | self.db, | ||
986 | // TODO use right resolver for block | ||
987 | &self.resolver, | ||
988 | type_ref, | ||
989 | ); | ||
990 | let ty = self.insert_type_vars(ty); | ||
991 | ty | ||
992 | } | ||
993 | |||
994 | fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { | ||
995 | substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) | ||
996 | } | ||
997 | |||
998 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
999 | self.unify_inner(ty1, ty2, 0) | ||
1000 | } | ||
1001 | |||
1002 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | ||
1003 | if depth > 1000 { | ||
1004 | // prevent stackoverflows | ||
1005 | panic!("infinite recursion in unification"); | ||
1006 | } | ||
1007 | if ty1 == ty2 { | ||
1008 | return true; | ||
1009 | } | ||
1010 | // try to resolve type vars first | ||
1011 | let ty1 = self.resolve_ty_shallow(ty1); | ||
1012 | let ty2 = self.resolve_ty_shallow(ty2); | ||
1013 | match (&*ty1, &*ty2) { | ||
1014 | (Ty::Unknown, ..) => true, | ||
1015 | (.., Ty::Unknown) => true, | ||
1016 | (Ty::Int(t1), Ty::Int(t2)) => match (t1, t2) { | ||
1017 | (primitive::UncertainIntTy::Unknown, _) | ||
1018 | | (_, primitive::UncertainIntTy::Unknown) => true, | ||
1019 | _ => t1 == t2, | ||
1020 | }, | ||
1021 | (Ty::Float(t1), Ty::Float(t2)) => match (t1, t2) { | ||
1022 | (primitive::UncertainFloatTy::Unknown, _) | ||
1023 | | (_, primitive::UncertainFloatTy::Unknown) => true, | ||
1024 | _ => t1 == t2, | ||
1025 | }, | ||
1026 | (Ty::Bool, _) | (Ty::Str, _) | (Ty::Never, _) | (Ty::Char, _) => ty1 == ty2, | ||
1027 | ( | ||
1028 | Ty::Adt { def_id: def_id1, substs: substs1, .. }, | ||
1029 | Ty::Adt { def_id: def_id2, substs: substs2, .. }, | ||
1030 | ) if def_id1 == def_id2 => self.unify_substs(substs1, substs2, depth + 1), | ||
1031 | (Ty::Slice(t1), Ty::Slice(t2)) => self.unify_inner(t1, t2, depth + 1), | ||
1032 | (Ty::RawPtr(t1, m1), Ty::RawPtr(t2, m2)) if m1 == m2 => { | ||
1033 | self.unify_inner(t1, t2, depth + 1) | ||
1034 | } | ||
1035 | (Ty::Ref(t1, m1), Ty::Ref(t2, m2)) if m1 == m2 => self.unify_inner(t1, t2, depth + 1), | ||
1036 | (Ty::FnPtr(sig1), Ty::FnPtr(sig2)) if sig1 == sig2 => true, | ||
1037 | (Ty::Tuple(ts1), Ty::Tuple(ts2)) if ts1.len() == ts2.len() => { | ||
1038 | ts1.iter().zip(ts2.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth + 1)) | ||
1039 | } | ||
1040 | (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2))) | ||
1041 | | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2))) | ||
1042 | | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) => { | ||
1043 | // both type vars are unknown since we tried to resolve them | ||
1044 | self.var_unification_table.union(*tv1, *tv2); | ||
1045 | true | ||
1046 | } | ||
1047 | (Ty::Infer(InferTy::TypeVar(tv)), other) | ||
1048 | | (other, Ty::Infer(InferTy::TypeVar(tv))) | ||
1049 | | (Ty::Infer(InferTy::IntVar(tv)), other) | ||
1050 | | (other, Ty::Infer(InferTy::IntVar(tv))) | ||
1051 | | (Ty::Infer(InferTy::FloatVar(tv)), other) | ||
1052 | | (other, Ty::Infer(InferTy::FloatVar(tv))) => { | ||
1053 | // the type var is unknown since we tried to resolve it | ||
1054 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); | ||
1055 | true | ||
1056 | } | ||
1057 | _ => false, | ||
1058 | } | ||
1059 | } | ||
1060 | |||
1061 | fn new_type_var(&mut self) -> Ty { | ||
1062 | Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
1063 | } | ||
1064 | |||
1065 | fn new_integer_var(&mut self) -> Ty { | ||
1066 | Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
1067 | } | ||
1068 | |||
1069 | fn new_float_var(&mut self) -> Ty { | ||
1070 | Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
1071 | } | ||
1072 | |||
1073 | /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. | ||
1074 | fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { | ||
1075 | match ty { | ||
1076 | Ty::Unknown => self.new_type_var(), | ||
1077 | Ty::Int(primitive::UncertainIntTy::Unknown) => self.new_integer_var(), | ||
1078 | Ty::Float(primitive::UncertainFloatTy::Unknown) => self.new_float_var(), | ||
1079 | _ => ty, | ||
1080 | } | ||
1081 | } | ||
1082 | |||
1083 | fn insert_type_vars(&mut self, ty: Ty) -> Ty { | ||
1084 | ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) | ||
1085 | } | ||
1086 | |||
1087 | /// Resolves the type as far as currently possible, replacing type variables | ||
1088 | /// by their known types. All types returned by the infer_* functions should | ||
1089 | /// be resolved as far as possible, i.e. contain no type variables with | ||
1090 | /// known type. | ||
1091 | fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
1092 | ty.fold(&mut |ty| match ty { | ||
1093 | Ty::Infer(tv) => { | ||
1094 | let inner = tv.to_inner(); | ||
1095 | if tv_stack.contains(&inner) { | ||
1096 | tested_by!(type_var_cycles_resolve_as_possible); | ||
1097 | // recursive type | ||
1098 | return tv.fallback_value(); | ||
1099 | } | ||
1100 | if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() { | ||
1101 | // known_ty may contain other variables that are known by now | ||
1102 | tv_stack.push(inner); | ||
1103 | let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone()); | ||
1104 | tv_stack.pop(); | ||
1105 | result | ||
1106 | } else { | ||
1107 | ty | ||
1108 | } | ||
1109 | } | ||
1110 | _ => ty, | ||
1111 | }) | ||
1112 | } | ||
1113 | |||
1114 | /// If `ty` is a type variable with known type, returns that type; | ||
1115 | /// otherwise, return ty. | ||
1116 | fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | ||
1117 | let mut ty = Cow::Borrowed(ty); | ||
1118 | // The type variable could resolve to a int/float variable. Hence try | ||
1119 | // resolving up to three times; each type of variable shouldn't occur | ||
1120 | // more than once | ||
1121 | for i in 0..3 { | ||
1122 | if i > 0 { | ||
1123 | tested_by!(type_var_resolves_to_int_var); | ||
1124 | } | ||
1125 | match &*ty { | ||
1126 | Ty::Infer(tv) => { | ||
1127 | let inner = tv.to_inner(); | ||
1128 | match self.var_unification_table.probe_value(inner).known() { | ||
1129 | Some(known_ty) => { | ||
1130 | // The known_ty can't be a type var itself | ||
1131 | ty = Cow::Owned(known_ty.clone()); | ||
1132 | } | ||
1133 | _ => return ty, | ||
1134 | } | ||
1135 | } | ||
1136 | _ => return ty, | ||
1137 | } | ||
1138 | } | ||
1139 | log::error!("Inference variable still not resolved: {:?}", ty); | ||
1140 | ty | ||
1141 | } | ||
1142 | |||
1143 | /// Resolves the type completely; type variables without known type are | ||
1144 | /// replaced by Ty::Unknown. | ||
1145 | fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
1146 | ty.fold(&mut |ty| match ty { | ||
1147 | Ty::Infer(tv) => { | ||
1148 | let inner = tv.to_inner(); | ||
1149 | if tv_stack.contains(&inner) { | ||
1150 | tested_by!(type_var_cycles_resolve_completely); | ||
1151 | // recursive type | ||
1152 | return tv.fallback_value(); | ||
1153 | } | ||
1154 | if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() { | ||
1155 | // known_ty may contain other variables that are known by now | ||
1156 | tv_stack.push(inner); | ||
1157 | let result = self.resolve_ty_completely(tv_stack, known_ty.clone()); | ||
1158 | tv_stack.pop(); | ||
1159 | result | ||
1160 | } else { | ||
1161 | tv.fallback_value() | ||
1162 | } | ||
1163 | } | ||
1164 | _ => ty, | ||
1165 | }) | ||
1166 | } | ||
1167 | |||
1168 | fn infer_path_expr(&mut self, resolver: &Resolver, path: &Path) -> Option<Ty> { | ||
1169 | let resolved = resolver.resolve_path_segments(self.db, &path); | ||
1170 | |||
1171 | let (def, remaining_index) = resolved.into_inner(); | ||
1172 | |||
1173 | log::debug!( | ||
1174 | "path {:?} resolved to {:?} with remaining index {:?}", | ||
1175 | path, | ||
1176 | def, | ||
1177 | remaining_index | ||
1178 | ); | ||
1179 | |||
1180 | // if the remaining_index is None, we expect the path | ||
1181 | // to be fully resolved, in this case we continue with | ||
1182 | // the default by attempting to `take_values´ from the resolution. | ||
1183 | // Otherwise the path was partially resolved, which means | ||
1184 | // we might have resolved into a type for which | ||
1185 | // we may find some associated item starting at the | ||
1186 | // path.segment pointed to by `remaining_index´ | ||
1187 | let resolved = | ||
1188 | if remaining_index.is_none() { def.take_values()? } else { def.take_types()? }; | ||
1189 | |||
1190 | match resolved { | ||
1191 | Resolution::Def(def) => { | ||
1192 | let typable: Option<TypableDef> = def.into(); | ||
1193 | let typable = typable?; | ||
1194 | |||
1195 | if let Some(remaining_index) = remaining_index { | ||
1196 | let ty = self.db.type_for_def(typable, Namespace::Types); | ||
1197 | // TODO: Keep resolving the segments | ||
1198 | // if we have more segments to process | ||
1199 | let segment = &path.segments[remaining_index]; | ||
1200 | |||
1201 | log::debug!("looking for path segment: {:?}", segment); | ||
1202 | |||
1203 | // Attempt to find an impl_item for the type which has a name matching | ||
1204 | // the current segment | ||
1205 | let ty = ty.iterate_impl_items(self.db, |item| match item { | ||
1206 | crate::ImplItem::Method(func) => { | ||
1207 | let sig = func.signature(self.db); | ||
1208 | if segment.name == *sig.name() { | ||
1209 | return Some(type_for_fn(self.db, func)); | ||
1210 | } | ||
1211 | None | ||
1212 | } | ||
1213 | |||
1214 | // TODO: Resolve associated const | ||
1215 | crate::ImplItem::Const(_) => None, | ||
1216 | |||
1217 | // TODO: Resolve associated types | ||
1218 | crate::ImplItem::Type(_) => None, | ||
1219 | }); | ||
1220 | ty | ||
1221 | } else { | ||
1222 | let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable); | ||
1223 | let ty = self.db.type_for_def(typable, Namespace::Values).apply_substs(substs); | ||
1224 | let ty = self.insert_type_vars(ty); | ||
1225 | Some(ty) | ||
1226 | } | ||
1227 | } | ||
1228 | Resolution::LocalBinding(pat) => { | ||
1229 | let ty = self.type_of_pat.get(pat)?; | ||
1230 | let ty = self.resolve_ty_as_possible(&mut vec![], ty.clone()); | ||
1231 | Some(ty) | ||
1232 | } | ||
1233 | Resolution::GenericParam(..) => { | ||
1234 | // generic params can't refer to values... yet | ||
1235 | None | ||
1236 | } | ||
1237 | Resolution::SelfType(_) => { | ||
1238 | log::error!("path expr {:?} resolved to Self type in values ns", path); | ||
1239 | None | ||
1240 | } | ||
1241 | } | ||
1242 | } | ||
1243 | |||
1244 | fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantDef>) { | ||
1245 | let path = match path { | ||
1246 | Some(path) => path, | ||
1247 | None => return (Ty::Unknown, None), | ||
1248 | }; | ||
1249 | let resolver = &self.resolver; | ||
1250 | let typable: Option<TypableDef> = match resolver.resolve_path(self.db, &path).take_types() { | ||
1251 | Some(Resolution::Def(def)) => def.into(), | ||
1252 | Some(Resolution::LocalBinding(..)) => { | ||
1253 | // this cannot happen | ||
1254 | log::error!("path resolved to local binding in type ns"); | ||
1255 | return (Ty::Unknown, None); | ||
1256 | } | ||
1257 | Some(Resolution::GenericParam(..)) => { | ||
1258 | // generic params can't be used in struct literals | ||
1259 | return (Ty::Unknown, None); | ||
1260 | } | ||
1261 | Some(Resolution::SelfType(..)) => { | ||
1262 | // TODO this is allowed in an impl for a struct, handle this | ||
1263 | return (Ty::Unknown, None); | ||
1264 | } | ||
1265 | None => return (Ty::Unknown, None), | ||
1266 | }; | ||
1267 | let def = match typable { | ||
1268 | None => return (Ty::Unknown, None), | ||
1269 | Some(it) => it, | ||
1270 | }; | ||
1271 | // TODO remove the duplication between here and `Ty::from_path`? | ||
1272 | let substs = Ty::substs_from_path(self.db, resolver, path, def); | ||
1273 | match def { | ||
1274 | TypableDef::Struct(s) => { | ||
1275 | let ty = s.ty(self.db); | ||
1276 | let ty = self.insert_type_vars(ty.apply_substs(substs)); | ||
1277 | (ty, Some(s.into())) | ||
1278 | } | ||
1279 | TypableDef::EnumVariant(var) => { | ||
1280 | let ty = var.parent_enum(self.db).ty(self.db); | ||
1281 | let ty = self.insert_type_vars(ty.apply_substs(substs)); | ||
1282 | (ty, Some(var.into())) | ||
1283 | } | ||
1284 | TypableDef::Function(_) | TypableDef::Enum(_) => (Ty::Unknown, None), | ||
1285 | } | ||
1286 | } | ||
1287 | |||
1288 | fn infer_tuple_struct_pat( | ||
1289 | &mut self, | ||
1290 | path: Option<&Path>, | ||
1291 | subpats: &[PatId], | ||
1292 | expected: &Ty, | ||
1293 | ) -> Ty { | ||
1294 | let (ty, def) = self.resolve_variant(path); | ||
1295 | |||
1296 | self.unify(&ty, expected); | ||
1297 | |||
1298 | let substs = ty.substs().unwrap_or_else(Substs::empty); | ||
1299 | |||
1300 | for (i, &subpat) in subpats.iter().enumerate() { | ||
1301 | let expected_ty = def | ||
1302 | .and_then(|d| d.field(self.db, &Name::tuple_field_name(i))) | ||
1303 | .map_or(Ty::Unknown, |field| field.ty(self.db)) | ||
1304 | .subst(&substs); | ||
1305 | self.infer_pat(subpat, &expected_ty); | ||
1306 | } | ||
1307 | |||
1308 | ty | ||
1309 | } | ||
1310 | |||
1311 | fn infer_struct_pat(&mut self, path: Option<&Path>, subpats: &[FieldPat], expected: &Ty) -> Ty { | ||
1312 | let (ty, def) = self.resolve_variant(path); | ||
1313 | |||
1314 | self.unify(&ty, expected); | ||
1315 | |||
1316 | let substs = ty.substs().unwrap_or_else(Substs::empty); | ||
1317 | |||
1318 | for subpat in subpats { | ||
1319 | let matching_field = def.and_then(|it| it.field(self.db, &subpat.name)); | ||
1320 | let expected_ty = | ||
1321 | matching_field.map_or(Ty::Unknown, |field| field.ty(self.db)).subst(&substs); | ||
1322 | self.infer_pat(subpat.pat, &expected_ty); | ||
1323 | } | ||
1324 | |||
1325 | ty | ||
1326 | } | ||
1327 | |||
1328 | fn infer_pat(&mut self, pat: PatId, expected: &Ty) -> Ty { | ||
1329 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
1330 | |||
1331 | let ty = match &body[pat] { | ||
1332 | Pat::Tuple(ref args) => { | ||
1333 | let expectations = match *expected { | ||
1334 | Ty::Tuple(ref tuple_args) => &**tuple_args, | ||
1335 | _ => &[], | ||
1336 | }; | ||
1337 | let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown)); | ||
1338 | |||
1339 | let inner_tys = args | ||
1340 | .iter() | ||
1341 | .zip(expectations_iter) | ||
1342 | .map(|(&pat, ty)| self.infer_pat(pat, ty)) | ||
1343 | .collect::<Vec<_>>() | ||
1344 | .into(); | ||
1345 | |||
1346 | Ty::Tuple(inner_tys) | ||
1347 | } | ||
1348 | Pat::Ref { pat, mutability } => { | ||
1349 | let expectation = match *expected { | ||
1350 | Ty::Ref(ref sub_ty, exp_mut) => { | ||
1351 | if *mutability != exp_mut { | ||
1352 | // TODO: emit type error? | ||
1353 | } | ||
1354 | &**sub_ty | ||
1355 | } | ||
1356 | _ => &Ty::Unknown, | ||
1357 | }; | ||
1358 | let subty = self.infer_pat(*pat, expectation); | ||
1359 | Ty::Ref(subty.into(), *mutability) | ||
1360 | } | ||
1361 | Pat::TupleStruct { path: ref p, args: ref subpats } => { | ||
1362 | self.infer_tuple_struct_pat(p.as_ref(), subpats, expected) | ||
1363 | } | ||
1364 | Pat::Struct { path: ref p, args: ref fields } => { | ||
1365 | self.infer_struct_pat(p.as_ref(), fields, expected) | ||
1366 | } | ||
1367 | Pat::Path(path) => { | ||
1368 | // TODO use correct resolver for the surrounding expression | ||
1369 | let resolver = self.resolver.clone(); | ||
1370 | self.infer_path_expr(&resolver, &path).unwrap_or(Ty::Unknown) | ||
1371 | } | ||
1372 | Pat::Bind { mode, name: _name, subpat } => { | ||
1373 | let inner_ty = if let Some(subpat) = subpat { | ||
1374 | self.infer_pat(*subpat, expected) | ||
1375 | } else { | ||
1376 | expected.clone() | ||
1377 | }; | ||
1378 | let inner_ty = self.insert_type_vars_shallow(inner_ty); | ||
1379 | |||
1380 | let bound_ty = match mode { | ||
1381 | BindingAnnotation::Ref => Ty::Ref(inner_ty.clone().into(), Mutability::Shared), | ||
1382 | BindingAnnotation::RefMut => Ty::Ref(inner_ty.clone().into(), Mutability::Mut), | ||
1383 | BindingAnnotation::Mutable | BindingAnnotation::Unannotated => inner_ty.clone(), | ||
1384 | }; | ||
1385 | let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty); | ||
1386 | self.write_pat_ty(pat, bound_ty); | ||
1387 | return inner_ty; | ||
1388 | } | ||
1389 | _ => Ty::Unknown, | ||
1390 | }; | ||
1391 | // use a new type variable if we got Ty::Unknown here | ||
1392 | let ty = self.insert_type_vars_shallow(ty); | ||
1393 | self.unify(&ty, expected); | ||
1394 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | ||
1395 | self.write_pat_ty(pat, ty.clone()); | ||
1396 | ty | ||
1397 | } | ||
1398 | |||
1399 | fn substs_for_method_call( | ||
1400 | &mut self, | ||
1401 | def_generics: Option<Arc<GenericParams>>, | ||
1402 | generic_args: &Option<GenericArgs>, | ||
1403 | ) -> Substs { | ||
1404 | let (parent_param_count, param_count) = | ||
1405 | def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len())); | ||
1406 | let mut substs = Vec::with_capacity(parent_param_count + param_count); | ||
1407 | for _ in 0..parent_param_count { | ||
1408 | substs.push(Ty::Unknown); | ||
1409 | } | ||
1410 | // handle provided type arguments | ||
1411 | if let Some(generic_args) = generic_args { | ||
1412 | // if args are provided, it should be all of them, but we can't rely on that | ||
1413 | for arg in generic_args.args.iter().take(param_count) { | ||
1414 | match arg { | ||
1415 | GenericArg::Type(type_ref) => { | ||
1416 | let ty = self.make_ty(type_ref); | ||
1417 | substs.push(ty); | ||
1418 | } | ||
1419 | } | ||
1420 | } | ||
1421 | }; | ||
1422 | let supplied_params = substs.len(); | ||
1423 | for _ in supplied_params..parent_param_count + param_count { | ||
1424 | substs.push(Ty::Unknown); | ||
1425 | } | ||
1426 | assert_eq!(substs.len(), parent_param_count + param_count); | ||
1427 | Substs(substs.into()) | ||
1428 | } | ||
1429 | |||
1430 | fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { | ||
1431 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
1432 | let ty = match &body[tgt_expr] { | ||
1433 | Expr::Missing => Ty::Unknown, | ||
1434 | Expr::If { condition, then_branch, else_branch } => { | ||
1435 | // if let is desugared to match, so this is always simple if | ||
1436 | self.infer_expr(*condition, &Expectation::has_type(Ty::Bool)); | ||
1437 | let then_ty = self.infer_expr(*then_branch, expected); | ||
1438 | match else_branch { | ||
1439 | Some(else_branch) => { | ||
1440 | self.infer_expr(*else_branch, expected); | ||
1441 | } | ||
1442 | None => { | ||
1443 | // no else branch -> unit | ||
1444 | self.unify(&then_ty, &Ty::unit()); // actually coerce | ||
1445 | } | ||
1446 | }; | ||
1447 | then_ty | ||
1448 | } | ||
1449 | Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected), | ||
1450 | Expr::Loop { body } => { | ||
1451 | self.infer_expr(*body, &Expectation::has_type(Ty::unit())); | ||
1452 | // TODO handle break with value | ||
1453 | Ty::Never | ||
1454 | } | ||
1455 | Expr::While { condition, body } => { | ||
1456 | // while let is desugared to a match loop, so this is always simple while | ||
1457 | self.infer_expr(*condition, &Expectation::has_type(Ty::Bool)); | ||
1458 | self.infer_expr(*body, &Expectation::has_type(Ty::unit())); | ||
1459 | Ty::unit() | ||
1460 | } | ||
1461 | Expr::For { iterable, body, pat } => { | ||
1462 | let _iterable_ty = self.infer_expr(*iterable, &Expectation::none()); | ||
1463 | self.infer_pat(*pat, &Ty::Unknown); | ||
1464 | self.infer_expr(*body, &Expectation::has_type(Ty::unit())); | ||
1465 | Ty::unit() | ||
1466 | } | ||
1467 | Expr::Lambda { body, args, arg_types } => { | ||
1468 | assert_eq!(args.len(), arg_types.len()); | ||
1469 | |||
1470 | for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) { | ||
1471 | let expected = if let Some(type_ref) = arg_type { | ||
1472 | let ty = self.make_ty(type_ref); | ||
1473 | ty | ||
1474 | } else { | ||
1475 | Ty::Unknown | ||
1476 | }; | ||
1477 | self.infer_pat(*arg_pat, &expected); | ||
1478 | } | ||
1479 | |||
1480 | // TODO: infer lambda type etc. | ||
1481 | let _body_ty = self.infer_expr(*body, &Expectation::none()); | ||
1482 | Ty::Unknown | ||
1483 | } | ||
1484 | Expr::Call { callee, args } => { | ||
1485 | let callee_ty = self.infer_expr(*callee, &Expectation::none()); | ||
1486 | let (param_tys, ret_ty) = match &callee_ty { | ||
1487 | Ty::FnPtr(sig) => (sig.input.clone(), sig.output.clone()), | ||
1488 | Ty::FnDef { substs, sig, .. } => { | ||
1489 | let ret_ty = sig.output.clone().subst(&substs); | ||
1490 | let param_tys = | ||
1491 | sig.input.iter().map(|ty| ty.clone().subst(&substs)).collect(); | ||
1492 | (param_tys, ret_ty) | ||
1493 | } | ||
1494 | _ => { | ||
1495 | // not callable | ||
1496 | // TODO report an error? | ||
1497 | (Vec::new(), Ty::Unknown) | ||
1498 | } | ||
1499 | }; | ||
1500 | let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown)); | ||
1501 | for (arg, param) in args.iter().zip(param_iter) { | ||
1502 | self.infer_expr(*arg, &Expectation::has_type(param)); | ||
1503 | } | ||
1504 | ret_ty | ||
1505 | } | ||
1506 | Expr::MethodCall { receiver, args, method_name, generic_args } => { | ||
1507 | let receiver_ty = self.infer_expr(*receiver, &Expectation::none()); | ||
1508 | let resolved = receiver_ty.clone().lookup_method(self.db, method_name); | ||
1509 | let (derefed_receiver_ty, method_ty, def_generics) = match resolved { | ||
1510 | Some((ty, func)) => { | ||
1511 | self.write_method_resolution(tgt_expr, func); | ||
1512 | ( | ||
1513 | ty, | ||
1514 | self.db.type_for_def(func.into(), Namespace::Values), | ||
1515 | Some(func.generic_params(self.db)), | ||
1516 | ) | ||
1517 | } | ||
1518 | None => (Ty::Unknown, receiver_ty, None), | ||
1519 | }; | ||
1520 | let substs = self.substs_for_method_call(def_generics, generic_args); | ||
1521 | let method_ty = method_ty.apply_substs(substs); | ||
1522 | let method_ty = self.insert_type_vars(method_ty); | ||
1523 | let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty { | ||
1524 | Ty::FnPtr(sig) => { | ||
1525 | if !sig.input.is_empty() { | ||
1526 | (sig.input[0].clone(), sig.input[1..].to_vec(), sig.output.clone()) | ||
1527 | } else { | ||
1528 | (Ty::Unknown, Vec::new(), sig.output.clone()) | ||
1529 | } | ||
1530 | } | ||
1531 | Ty::FnDef { substs, sig, .. } => { | ||
1532 | let ret_ty = sig.output.clone().subst(&substs); | ||
1533 | |||
1534 | if !sig.input.is_empty() { | ||
1535 | let mut arg_iter = sig.input.iter().map(|ty| ty.clone().subst(&substs)); | ||
1536 | let receiver_ty = arg_iter.next().unwrap(); | ||
1537 | (receiver_ty, arg_iter.collect(), ret_ty) | ||
1538 | } else { | ||
1539 | (Ty::Unknown, Vec::new(), ret_ty) | ||
1540 | } | ||
1541 | } | ||
1542 | _ => (Ty::Unknown, Vec::new(), Ty::Unknown), | ||
1543 | }; | ||
1544 | // Apply autoref so the below unification works correctly | ||
1545 | let actual_receiver_ty = match expected_receiver_ty { | ||
1546 | Ty::Ref(_, mutability) => Ty::Ref(Arc::new(derefed_receiver_ty), mutability), | ||
1547 | _ => derefed_receiver_ty, | ||
1548 | }; | ||
1549 | self.unify(&expected_receiver_ty, &actual_receiver_ty); | ||
1550 | |||
1551 | let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown)); | ||
1552 | for (arg, param) in args.iter().zip(param_iter) { | ||
1553 | self.infer_expr(*arg, &Expectation::has_type(param)); | ||
1554 | } | ||
1555 | ret_ty | ||
1556 | } | ||
1557 | Expr::Match { expr, arms } => { | ||
1558 | let expected = if expected.ty == Ty::Unknown { | ||
1559 | Expectation::has_type(self.new_type_var()) | ||
1560 | } else { | ||
1561 | expected.clone() | ||
1562 | }; | ||
1563 | let input_ty = self.infer_expr(*expr, &Expectation::none()); | ||
1564 | |||
1565 | for arm in arms { | ||
1566 | for &pat in &arm.pats { | ||
1567 | let _pat_ty = self.infer_pat(pat, &input_ty); | ||
1568 | } | ||
1569 | if let Some(guard_expr) = arm.guard { | ||
1570 | self.infer_expr(guard_expr, &Expectation::has_type(Ty::Bool)); | ||
1571 | } | ||
1572 | self.infer_expr(arm.expr, &expected); | ||
1573 | } | ||
1574 | |||
1575 | expected.ty | ||
1576 | } | ||
1577 | Expr::Path(p) => { | ||
1578 | // TODO this could be more efficient... | ||
1579 | let resolver = expr::resolver_for_expr(self.body.clone(), self.db, tgt_expr); | ||
1580 | self.infer_path_expr(&resolver, p).unwrap_or(Ty::Unknown) | ||
1581 | } | ||
1582 | Expr::Continue => Ty::Never, | ||
1583 | Expr::Break { expr } => { | ||
1584 | if let Some(expr) = expr { | ||
1585 | // TODO handle break with value | ||
1586 | self.infer_expr(*expr, &Expectation::none()); | ||
1587 | } | ||
1588 | Ty::Never | ||
1589 | } | ||
1590 | Expr::Return { expr } => { | ||
1591 | if let Some(expr) = expr { | ||
1592 | self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone())); | ||
1593 | } | ||
1594 | Ty::Never | ||
1595 | } | ||
1596 | Expr::StructLit { path, fields, spread } => { | ||
1597 | let (ty, def_id) = self.resolve_variant(path.as_ref()); | ||
1598 | let substs = ty.substs().unwrap_or_else(Substs::empty); | ||
1599 | for field in fields { | ||
1600 | let field_ty = def_id | ||
1601 | .and_then(|it| it.field(self.db, &field.name)) | ||
1602 | .map_or(Ty::Unknown, |field| field.ty(self.db)) | ||
1603 | .subst(&substs); | ||
1604 | self.infer_expr(field.expr, &Expectation::has_type(field_ty)); | ||
1605 | } | ||
1606 | if let Some(expr) = spread { | ||
1607 | self.infer_expr(*expr, &Expectation::has_type(ty.clone())); | ||
1608 | } | ||
1609 | ty | ||
1610 | } | ||
1611 | Expr::Field { expr, name } => { | ||
1612 | let receiver_ty = self.infer_expr(*expr, &Expectation::none()); | ||
1613 | let ty = receiver_ty | ||
1614 | .autoderef(self.db) | ||
1615 | .find_map(|derefed_ty| match derefed_ty { | ||
1616 | Ty::Tuple(fields) => { | ||
1617 | let i = name.to_string().parse::<usize>().ok(); | ||
1618 | i.and_then(|i| fields.get(i).cloned()) | ||
1619 | } | ||
1620 | Ty::Adt { def_id: AdtDef::Struct(s), ref substs, .. } => { | ||
1621 | s.field(self.db, name).map(|field| { | ||
1622 | self.write_field_resolution(tgt_expr, field); | ||
1623 | field.ty(self.db).subst(substs) | ||
1624 | }) | ||
1625 | } | ||
1626 | _ => None, | ||
1627 | }) | ||
1628 | .unwrap_or(Ty::Unknown); | ||
1629 | self.insert_type_vars(ty) | ||
1630 | } | ||
1631 | Expr::Try { expr } => { | ||
1632 | let _inner_ty = self.infer_expr(*expr, &Expectation::none()); | ||
1633 | Ty::Unknown | ||
1634 | } | ||
1635 | Expr::Cast { expr, type_ref } => { | ||
1636 | let _inner_ty = self.infer_expr(*expr, &Expectation::none()); | ||
1637 | let cast_ty = self.make_ty(type_ref); | ||
1638 | // TODO check the cast... | ||
1639 | cast_ty | ||
1640 | } | ||
1641 | Expr::Ref { expr, mutability } => { | ||
1642 | let expectation = if let Ty::Ref(ref subty, expected_mutability) = expected.ty { | ||
1643 | if expected_mutability == Mutability::Mut && *mutability == Mutability::Shared { | ||
1644 | // TODO: throw type error - expected mut reference but found shared ref, | ||
1645 | // which cannot be coerced | ||
1646 | } | ||
1647 | Expectation::has_type((**subty).clone()) | ||
1648 | } else { | ||
1649 | Expectation::none() | ||
1650 | }; | ||
1651 | // TODO reference coercions etc. | ||
1652 | let inner_ty = self.infer_expr(*expr, &expectation); | ||
1653 | Ty::Ref(Arc::new(inner_ty), *mutability) | ||
1654 | } | ||
1655 | Expr::UnaryOp { expr, op } => { | ||
1656 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); | ||
1657 | match op { | ||
1658 | UnaryOp::Deref => { | ||
1659 | if let Some(derefed_ty) = inner_ty.builtin_deref() { | ||
1660 | derefed_ty | ||
1661 | } else { | ||
1662 | // TODO Deref::deref | ||
1663 | Ty::Unknown | ||
1664 | } | ||
1665 | } | ||
1666 | UnaryOp::Neg => { | ||
1667 | match inner_ty { | ||
1668 | Ty::Int(primitive::UncertainIntTy::Unknown) | ||
1669 | | Ty::Int(primitive::UncertainIntTy::Signed(..)) | ||
1670 | | Ty::Infer(InferTy::IntVar(..)) | ||
1671 | | Ty::Infer(InferTy::FloatVar(..)) | ||
1672 | | Ty::Float(..) => inner_ty, | ||
1673 | // TODO: resolve ops::Neg trait | ||
1674 | _ => Ty::Unknown, | ||
1675 | } | ||
1676 | } | ||
1677 | UnaryOp::Not => { | ||
1678 | match inner_ty { | ||
1679 | Ty::Bool | Ty::Int(_) | Ty::Infer(InferTy::IntVar(..)) => inner_ty, | ||
1680 | // TODO: resolve ops::Not trait for inner_ty | ||
1681 | _ => Ty::Unknown, | ||
1682 | } | ||
1683 | } | ||
1684 | } | ||
1685 | } | ||
1686 | Expr::BinaryOp { lhs, rhs, op } => match op { | ||
1687 | Some(op) => { | ||
1688 | let lhs_expectation = match op { | ||
1689 | BinaryOp::BooleanAnd | BinaryOp::BooleanOr => { | ||
1690 | Expectation::has_type(Ty::Bool) | ||
1691 | } | ||
1692 | _ => Expectation::none(), | ||
1693 | }; | ||
1694 | let lhs_ty = self.infer_expr(*lhs, &lhs_expectation); | ||
1695 | // TODO: find implementation of trait corresponding to operation | ||
1696 | // symbol and resolve associated `Output` type | ||
1697 | let rhs_expectation = binary_op_rhs_expectation(*op, lhs_ty); | ||
1698 | let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation)); | ||
1699 | |||
1700 | // TODO: similar as above, return ty is often associated trait type | ||
1701 | binary_op_return_ty(*op, rhs_ty) | ||
1702 | } | ||
1703 | _ => Ty::Unknown, | ||
1704 | }, | ||
1705 | Expr::Tuple { exprs } => { | ||
1706 | let mut ty_vec = Vec::with_capacity(exprs.len()); | ||
1707 | for arg in exprs.iter() { | ||
1708 | ty_vec.push(self.infer_expr(*arg, &Expectation::none())); | ||
1709 | } | ||
1710 | |||
1711 | Ty::Tuple(Arc::from(ty_vec)) | ||
1712 | } | ||
1713 | Expr::Array { exprs } => { | ||
1714 | let elem_ty = match &expected.ty { | ||
1715 | Ty::Slice(inner) | Ty::Array(inner) => Ty::clone(&inner), | ||
1716 | _ => self.new_type_var(), | ||
1717 | }; | ||
1718 | |||
1719 | for expr in exprs.iter() { | ||
1720 | self.infer_expr(*expr, &Expectation::has_type(elem_ty.clone())); | ||
1721 | } | ||
1722 | |||
1723 | Ty::Array(Arc::new(elem_ty)) | ||
1724 | } | ||
1725 | Expr::Literal(lit) => match lit { | ||
1726 | Literal::Bool(..) => Ty::Bool, | ||
1727 | Literal::String(..) => Ty::Ref(Arc::new(Ty::Str), Mutability::Shared), | ||
1728 | Literal::ByteString(..) => { | ||
1729 | let byte_type = Arc::new(Ty::Int(primitive::UncertainIntTy::Unsigned( | ||
1730 | primitive::UintTy::U8, | ||
1731 | ))); | ||
1732 | let slice_type = Arc::new(Ty::Slice(byte_type)); | ||
1733 | Ty::Ref(slice_type, Mutability::Shared) | ||
1734 | } | ||
1735 | Literal::Char(..) => Ty::Char, | ||
1736 | Literal::Int(_v, ty) => Ty::Int(*ty), | ||
1737 | Literal::Float(_v, ty) => Ty::Float(*ty), | ||
1738 | }, | ||
1739 | }; | ||
1740 | // use a new type variable if we got Ty::Unknown here | ||
1741 | let ty = self.insert_type_vars_shallow(ty); | ||
1742 | self.unify(&ty, &expected.ty); | ||
1743 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | ||
1744 | self.write_expr_ty(tgt_expr, ty.clone()); | ||
1745 | ty | ||
1746 | } | ||
1747 | |||
1748 | fn infer_block( | ||
1749 | &mut self, | ||
1750 | statements: &[Statement], | ||
1751 | tail: Option<ExprId>, | ||
1752 | expected: &Expectation, | ||
1753 | ) -> Ty { | ||
1754 | for stmt in statements { | ||
1755 | match stmt { | ||
1756 | Statement::Let { pat, type_ref, initializer } => { | ||
1757 | let decl_ty = | ||
1758 | type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown); | ||
1759 | let decl_ty = self.insert_type_vars(decl_ty); | ||
1760 | let ty = if let Some(expr) = initializer { | ||
1761 | let expr_ty = self.infer_expr(*expr, &Expectation::has_type(decl_ty)); | ||
1762 | expr_ty | ||
1763 | } else { | ||
1764 | decl_ty | ||
1765 | }; | ||
1766 | |||
1767 | self.infer_pat(*pat, &ty); | ||
1768 | } | ||
1769 | Statement::Expr(expr) => { | ||
1770 | self.infer_expr(*expr, &Expectation::none()); | ||
1771 | } | ||
1772 | } | ||
1773 | } | ||
1774 | let ty = if let Some(expr) = tail { self.infer_expr(expr, expected) } else { Ty::unit() }; | ||
1775 | ty | ||
1776 | } | ||
1777 | |||
1778 | fn collect_fn_signature(&mut self, signature: &FnSignature) { | ||
1779 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
1780 | for (type_ref, pat) in signature.params().iter().zip(body.params()) { | ||
1781 | let ty = self.make_ty(type_ref); | ||
1782 | |||
1783 | self.infer_pat(*pat, &ty); | ||
1784 | } | ||
1785 | self.return_ty = self.make_ty(signature.ret_type()); | ||
1786 | } | ||
1787 | |||
1788 | fn infer_body(&mut self) { | ||
1789 | self.infer_expr(self.body.body_expr(), &Expectation::has_type(self.return_ty.clone())); | ||
1790 | } | ||
1791 | } | ||
1792 | |||
1793 | pub fn infer(db: &impl HirDatabase, func: Function) -> Arc<InferenceResult> { | ||
1794 | db.check_canceled(); | ||
1795 | let body = func.body(db); | ||
1796 | let resolver = func.resolver(db); | ||
1797 | let mut ctx = InferenceContext::new(db, body, resolver); | ||
1798 | |||
1799 | let signature = func.signature(db); | ||
1800 | ctx.collect_fn_signature(&signature); | ||
1801 | |||
1802 | ctx.infer_body(); | ||
1803 | |||
1804 | Arc::new(ctx.resolve_all()) | ||
1805 | } | ||
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs new file mode 100644 index 000000000..13080b5aa --- /dev/null +++ b/crates/ra_hir/src/ty/infer.rs | |||
@@ -0,0 +1,1099 @@ | |||
1 | //! Type inference, i.e. the process of walking through the code and determining | ||
2 | //! the type of each expression and pattern. | ||
3 | //! | ||
4 | //! For type inference, compare the implementations in rustc (the various | ||
5 | //! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and | ||
6 | //! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for | ||
7 | //! inference here is the `infer` function, which infers the types of all | ||
8 | //! expressions in a given function. | ||
9 | //! | ||
10 | //! During inference, types (i.e. the `Ty` struct) can contain type 'variables' | ||
11 | //! which represent currently unknown types; as we walk through the expressions, | ||
12 | //! we might determine that certain variables need to be equal to each other, or | ||
13 | //! to certain types. To record this, we use the union-find implementation from | ||
14 | //! the `ena` crate, which is extracted from rustc. | ||
15 | |||
16 | use std::borrow::Cow; | ||
17 | use std::iter::repeat; | ||
18 | use std::ops::Index; | ||
19 | use std::sync::Arc; | ||
20 | use std::mem; | ||
21 | |||
22 | use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError}; | ||
23 | use ra_arena::map::ArenaMap; | ||
24 | use rustc_hash::FxHashMap; | ||
25 | |||
26 | use test_utils::tested_by; | ||
27 | |||
28 | use crate::{ | ||
29 | Function, StructField, Path, Name, | ||
30 | FnSignature, AdtDef, | ||
31 | HirDatabase, | ||
32 | type_ref::{TypeRef, Mutability}, | ||
33 | expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat, self}, | ||
34 | generics::GenericParams, | ||
35 | path::{GenericArgs, GenericArg}, | ||
36 | adt::VariantDef, | ||
37 | resolve::{Resolver, Resolution}, | ||
38 | nameres::Namespace | ||
39 | }; | ||
40 | use super::{Ty, TypableDef, Substs, primitive, op}; | ||
41 | |||
42 | /// The entry point of type inference. | ||
43 | pub fn infer(db: &impl HirDatabase, func: Function) -> Arc<InferenceResult> { | ||
44 | db.check_canceled(); | ||
45 | let body = func.body(db); | ||
46 | let resolver = func.resolver(db); | ||
47 | let mut ctx = InferenceContext::new(db, body, resolver); | ||
48 | |||
49 | let signature = func.signature(db); | ||
50 | ctx.collect_fn_signature(&signature); | ||
51 | |||
52 | ctx.infer_body(); | ||
53 | |||
54 | Arc::new(ctx.resolve_all()) | ||
55 | } | ||
56 | |||
57 | /// The result of type inference: A mapping from expressions and patterns to types. | ||
58 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
59 | pub struct InferenceResult { | ||
60 | /// For each method call expr, records the function it resolves to. | ||
61 | method_resolutions: FxHashMap<ExprId, Function>, | ||
62 | /// For each field access expr, records the field it resolves to. | ||
63 | field_resolutions: FxHashMap<ExprId, StructField>, | ||
64 | pub(super) type_of_expr: ArenaMap<ExprId, Ty>, | ||
65 | pub(super) type_of_pat: ArenaMap<PatId, Ty>, | ||
66 | } | ||
67 | |||
68 | impl InferenceResult { | ||
69 | pub fn method_resolution(&self, expr: ExprId) -> Option<Function> { | ||
70 | self.method_resolutions.get(&expr).map(|it| *it) | ||
71 | } | ||
72 | pub fn field_resolution(&self, expr: ExprId) -> Option<StructField> { | ||
73 | self.field_resolutions.get(&expr).map(|it| *it) | ||
74 | } | ||
75 | } | ||
76 | |||
77 | impl Index<ExprId> for InferenceResult { | ||
78 | type Output = Ty; | ||
79 | |||
80 | fn index(&self, expr: ExprId) -> &Ty { | ||
81 | self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown) | ||
82 | } | ||
83 | } | ||
84 | |||
85 | impl Index<PatId> for InferenceResult { | ||
86 | type Output = Ty; | ||
87 | |||
88 | fn index(&self, pat: PatId) -> &Ty { | ||
89 | self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown) | ||
90 | } | ||
91 | } | ||
92 | |||
93 | /// The inference context contains all information needed during type inference. | ||
94 | #[derive(Clone, Debug)] | ||
95 | struct InferenceContext<'a, D: HirDatabase> { | ||
96 | db: &'a D, | ||
97 | body: Arc<Body>, | ||
98 | resolver: Resolver, | ||
99 | var_unification_table: InPlaceUnificationTable<TypeVarId>, | ||
100 | method_resolutions: FxHashMap<ExprId, Function>, | ||
101 | field_resolutions: FxHashMap<ExprId, StructField>, | ||
102 | type_of_expr: ArenaMap<ExprId, Ty>, | ||
103 | type_of_pat: ArenaMap<PatId, Ty>, | ||
104 | /// The return type of the function being inferred. | ||
105 | return_ty: Ty, | ||
106 | } | ||
107 | |||
108 | impl<'a, D: HirDatabase> InferenceContext<'a, D> { | ||
109 | fn new(db: &'a D, body: Arc<Body>, resolver: Resolver) -> Self { | ||
110 | InferenceContext { | ||
111 | method_resolutions: FxHashMap::default(), | ||
112 | field_resolutions: FxHashMap::default(), | ||
113 | type_of_expr: ArenaMap::default(), | ||
114 | type_of_pat: ArenaMap::default(), | ||
115 | var_unification_table: InPlaceUnificationTable::new(), | ||
116 | return_ty: Ty::Unknown, // set in collect_fn_signature | ||
117 | db, | ||
118 | body, | ||
119 | resolver, | ||
120 | } | ||
121 | } | ||
122 | |||
123 | fn resolve_all(mut self) -> InferenceResult { | ||
124 | let mut tv_stack = Vec::new(); | ||
125 | let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default()); | ||
126 | for ty in expr_types.values_mut() { | ||
127 | let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); | ||
128 | *ty = resolved; | ||
129 | } | ||
130 | let mut pat_types = mem::replace(&mut self.type_of_pat, ArenaMap::default()); | ||
131 | for ty in pat_types.values_mut() { | ||
132 | let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown)); | ||
133 | *ty = resolved; | ||
134 | } | ||
135 | InferenceResult { | ||
136 | method_resolutions: self.method_resolutions, | ||
137 | field_resolutions: self.field_resolutions, | ||
138 | type_of_expr: expr_types, | ||
139 | type_of_pat: pat_types, | ||
140 | } | ||
141 | } | ||
142 | |||
143 | fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) { | ||
144 | self.type_of_expr.insert(expr, ty); | ||
145 | } | ||
146 | |||
147 | fn write_method_resolution(&mut self, expr: ExprId, func: Function) { | ||
148 | self.method_resolutions.insert(expr, func); | ||
149 | } | ||
150 | |||
151 | fn write_field_resolution(&mut self, expr: ExprId, field: StructField) { | ||
152 | self.field_resolutions.insert(expr, field); | ||
153 | } | ||
154 | |||
155 | fn write_pat_ty(&mut self, pat: PatId, ty: Ty) { | ||
156 | self.type_of_pat.insert(pat, ty); | ||
157 | } | ||
158 | |||
159 | fn make_ty(&mut self, type_ref: &TypeRef) -> Ty { | ||
160 | let ty = Ty::from_hir( | ||
161 | self.db, | ||
162 | // TODO use right resolver for block | ||
163 | &self.resolver, | ||
164 | type_ref, | ||
165 | ); | ||
166 | let ty = self.insert_type_vars(ty); | ||
167 | ty | ||
168 | } | ||
169 | |||
170 | fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool { | ||
171 | substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth)) | ||
172 | } | ||
173 | |||
174 | fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool { | ||
175 | self.unify_inner(ty1, ty2, 0) | ||
176 | } | ||
177 | |||
178 | fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool { | ||
179 | if depth > 1000 { | ||
180 | // prevent stackoverflows | ||
181 | panic!("infinite recursion in unification"); | ||
182 | } | ||
183 | if ty1 == ty2 { | ||
184 | return true; | ||
185 | } | ||
186 | // try to resolve type vars first | ||
187 | let ty1 = self.resolve_ty_shallow(ty1); | ||
188 | let ty2 = self.resolve_ty_shallow(ty2); | ||
189 | match (&*ty1, &*ty2) { | ||
190 | (Ty::Unknown, ..) => true, | ||
191 | (.., Ty::Unknown) => true, | ||
192 | (Ty::Int(t1), Ty::Int(t2)) => match (t1, t2) { | ||
193 | (primitive::UncertainIntTy::Unknown, _) | ||
194 | | (_, primitive::UncertainIntTy::Unknown) => true, | ||
195 | _ => t1 == t2, | ||
196 | }, | ||
197 | (Ty::Float(t1), Ty::Float(t2)) => match (t1, t2) { | ||
198 | (primitive::UncertainFloatTy::Unknown, _) | ||
199 | | (_, primitive::UncertainFloatTy::Unknown) => true, | ||
200 | _ => t1 == t2, | ||
201 | }, | ||
202 | (Ty::Bool, _) | (Ty::Str, _) | (Ty::Never, _) | (Ty::Char, _) => ty1 == ty2, | ||
203 | ( | ||
204 | Ty::Adt { def_id: def_id1, substs: substs1, .. }, | ||
205 | Ty::Adt { def_id: def_id2, substs: substs2, .. }, | ||
206 | ) if def_id1 == def_id2 => self.unify_substs(substs1, substs2, depth + 1), | ||
207 | (Ty::Slice(t1), Ty::Slice(t2)) => self.unify_inner(t1, t2, depth + 1), | ||
208 | (Ty::RawPtr(t1, m1), Ty::RawPtr(t2, m2)) if m1 == m2 => { | ||
209 | self.unify_inner(t1, t2, depth + 1) | ||
210 | } | ||
211 | (Ty::Ref(t1, m1), Ty::Ref(t2, m2)) if m1 == m2 => self.unify_inner(t1, t2, depth + 1), | ||
212 | (Ty::FnPtr(sig1), Ty::FnPtr(sig2)) if sig1 == sig2 => true, | ||
213 | (Ty::Tuple(ts1), Ty::Tuple(ts2)) if ts1.len() == ts2.len() => { | ||
214 | ts1.iter().zip(ts2.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth + 1)) | ||
215 | } | ||
216 | (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2))) | ||
217 | | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2))) | ||
218 | | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) => { | ||
219 | // both type vars are unknown since we tried to resolve them | ||
220 | self.var_unification_table.union(*tv1, *tv2); | ||
221 | true | ||
222 | } | ||
223 | (Ty::Infer(InferTy::TypeVar(tv)), other) | ||
224 | | (other, Ty::Infer(InferTy::TypeVar(tv))) | ||
225 | | (Ty::Infer(InferTy::IntVar(tv)), other) | ||
226 | | (other, Ty::Infer(InferTy::IntVar(tv))) | ||
227 | | (Ty::Infer(InferTy::FloatVar(tv)), other) | ||
228 | | (other, Ty::Infer(InferTy::FloatVar(tv))) => { | ||
229 | // the type var is unknown since we tried to resolve it | ||
230 | self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone())); | ||
231 | true | ||
232 | } | ||
233 | _ => false, | ||
234 | } | ||
235 | } | ||
236 | |||
237 | fn new_type_var(&mut self) -> Ty { | ||
238 | Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
239 | } | ||
240 | |||
241 | fn new_integer_var(&mut self) -> Ty { | ||
242 | Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
243 | } | ||
244 | |||
245 | fn new_float_var(&mut self) -> Ty { | ||
246 | Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown))) | ||
247 | } | ||
248 | |||
249 | /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it. | ||
250 | fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty { | ||
251 | match ty { | ||
252 | Ty::Unknown => self.new_type_var(), | ||
253 | Ty::Int(primitive::UncertainIntTy::Unknown) => self.new_integer_var(), | ||
254 | Ty::Float(primitive::UncertainFloatTy::Unknown) => self.new_float_var(), | ||
255 | _ => ty, | ||
256 | } | ||
257 | } | ||
258 | |||
259 | fn insert_type_vars(&mut self, ty: Ty) -> Ty { | ||
260 | ty.fold(&mut |ty| self.insert_type_vars_shallow(ty)) | ||
261 | } | ||
262 | |||
263 | /// Resolves the type as far as currently possible, replacing type variables | ||
264 | /// by their known types. All types returned by the infer_* functions should | ||
265 | /// be resolved as far as possible, i.e. contain no type variables with | ||
266 | /// known type. | ||
267 | fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
268 | ty.fold(&mut |ty| match ty { | ||
269 | Ty::Infer(tv) => { | ||
270 | let inner = tv.to_inner(); | ||
271 | if tv_stack.contains(&inner) { | ||
272 | tested_by!(type_var_cycles_resolve_as_possible); | ||
273 | // recursive type | ||
274 | return tv.fallback_value(); | ||
275 | } | ||
276 | if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() { | ||
277 | // known_ty may contain other variables that are known by now | ||
278 | tv_stack.push(inner); | ||
279 | let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone()); | ||
280 | tv_stack.pop(); | ||
281 | result | ||
282 | } else { | ||
283 | ty | ||
284 | } | ||
285 | } | ||
286 | _ => ty, | ||
287 | }) | ||
288 | } | ||
289 | |||
290 | /// If `ty` is a type variable with known type, returns that type; | ||
291 | /// otherwise, return ty. | ||
292 | fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> { | ||
293 | let mut ty = Cow::Borrowed(ty); | ||
294 | // The type variable could resolve to a int/float variable. Hence try | ||
295 | // resolving up to three times; each type of variable shouldn't occur | ||
296 | // more than once | ||
297 | for i in 0..3 { | ||
298 | if i > 0 { | ||
299 | tested_by!(type_var_resolves_to_int_var); | ||
300 | } | ||
301 | match &*ty { | ||
302 | Ty::Infer(tv) => { | ||
303 | let inner = tv.to_inner(); | ||
304 | match self.var_unification_table.probe_value(inner).known() { | ||
305 | Some(known_ty) => { | ||
306 | // The known_ty can't be a type var itself | ||
307 | ty = Cow::Owned(known_ty.clone()); | ||
308 | } | ||
309 | _ => return ty, | ||
310 | } | ||
311 | } | ||
312 | _ => return ty, | ||
313 | } | ||
314 | } | ||
315 | log::error!("Inference variable still not resolved: {:?}", ty); | ||
316 | ty | ||
317 | } | ||
318 | |||
319 | /// Resolves the type completely; type variables without known type are | ||
320 | /// replaced by Ty::Unknown. | ||
321 | fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty { | ||
322 | ty.fold(&mut |ty| match ty { | ||
323 | Ty::Infer(tv) => { | ||
324 | let inner = tv.to_inner(); | ||
325 | if tv_stack.contains(&inner) { | ||
326 | tested_by!(type_var_cycles_resolve_completely); | ||
327 | // recursive type | ||
328 | return tv.fallback_value(); | ||
329 | } | ||
330 | if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() { | ||
331 | // known_ty may contain other variables that are known by now | ||
332 | tv_stack.push(inner); | ||
333 | let result = self.resolve_ty_completely(tv_stack, known_ty.clone()); | ||
334 | tv_stack.pop(); | ||
335 | result | ||
336 | } else { | ||
337 | tv.fallback_value() | ||
338 | } | ||
339 | } | ||
340 | _ => ty, | ||
341 | }) | ||
342 | } | ||
343 | |||
344 | fn infer_path_expr(&mut self, resolver: &Resolver, path: &Path) -> Option<Ty> { | ||
345 | let resolved = resolver.resolve_path_segments(self.db, &path); | ||
346 | |||
347 | let (def, remaining_index) = resolved.into_inner(); | ||
348 | |||
349 | log::debug!( | ||
350 | "path {:?} resolved to {:?} with remaining index {:?}", | ||
351 | path, | ||
352 | def, | ||
353 | remaining_index | ||
354 | ); | ||
355 | |||
356 | // if the remaining_index is None, we expect the path | ||
357 | // to be fully resolved, in this case we continue with | ||
358 | // the default by attempting to `take_values´ from the resolution. | ||
359 | // Otherwise the path was partially resolved, which means | ||
360 | // we might have resolved into a type for which | ||
361 | // we may find some associated item starting at the | ||
362 | // path.segment pointed to by `remaining_index´ | ||
363 | let mut resolved = | ||
364 | if remaining_index.is_none() { def.take_values()? } else { def.take_types()? }; | ||
365 | |||
366 | let remaining_index = remaining_index.unwrap_or(path.segments.len()); | ||
367 | |||
368 | // resolve intermediate segments | ||
369 | for segment in &path.segments[remaining_index..] { | ||
370 | let ty = match resolved { | ||
371 | Resolution::Def(def) => { | ||
372 | let typable: Option<TypableDef> = def.into(); | ||
373 | let typable = typable?; | ||
374 | |||
375 | let substs = | ||
376 | Ty::substs_from_path_segment(self.db, &self.resolver, segment, typable); | ||
377 | self.db.type_for_def(typable, Namespace::Types).apply_substs(substs) | ||
378 | } | ||
379 | Resolution::LocalBinding(_) => { | ||
380 | // can't have a local binding in an associated item path | ||
381 | return None; | ||
382 | } | ||
383 | Resolution::GenericParam(..) => { | ||
384 | // TODO associated item of generic param | ||
385 | return None; | ||
386 | } | ||
387 | Resolution::SelfType(_) => { | ||
388 | // TODO associated item of self type | ||
389 | return None; | ||
390 | } | ||
391 | }; | ||
392 | |||
393 | // Attempt to find an impl_item for the type which has a name matching | ||
394 | // the current segment | ||
395 | log::debug!("looking for path segment: {:?}", segment); | ||
396 | let item = ty.iterate_impl_items(self.db, |item| match item { | ||
397 | crate::ImplItem::Method(func) => { | ||
398 | let sig = func.signature(self.db); | ||
399 | if segment.name == *sig.name() { | ||
400 | return Some(func); | ||
401 | } | ||
402 | None | ||
403 | } | ||
404 | |||
405 | // TODO: Resolve associated const | ||
406 | crate::ImplItem::Const(_) => None, | ||
407 | |||
408 | // TODO: Resolve associated types | ||
409 | crate::ImplItem::Type(_) => None, | ||
410 | })?; | ||
411 | resolved = Resolution::Def(item.into()); | ||
412 | } | ||
413 | |||
414 | match resolved { | ||
415 | Resolution::Def(def) => { | ||
416 | let typable: Option<TypableDef> = def.into(); | ||
417 | let typable = typable?; | ||
418 | |||
419 | let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable); | ||
420 | let ty = self.db.type_for_def(typable, Namespace::Values).apply_substs(substs); | ||
421 | let ty = self.insert_type_vars(ty); | ||
422 | Some(ty) | ||
423 | } | ||
424 | Resolution::LocalBinding(pat) => { | ||
425 | let ty = self.type_of_pat.get(pat)?; | ||
426 | let ty = self.resolve_ty_as_possible(&mut vec![], ty.clone()); | ||
427 | Some(ty) | ||
428 | } | ||
429 | Resolution::GenericParam(..) => { | ||
430 | // generic params can't refer to values... yet | ||
431 | None | ||
432 | } | ||
433 | Resolution::SelfType(_) => { | ||
434 | log::error!("path expr {:?} resolved to Self type in values ns", path); | ||
435 | None | ||
436 | } | ||
437 | } | ||
438 | } | ||
439 | |||
440 | fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantDef>) { | ||
441 | let path = match path { | ||
442 | Some(path) => path, | ||
443 | None => return (Ty::Unknown, None), | ||
444 | }; | ||
445 | let resolver = &self.resolver; | ||
446 | let typable: Option<TypableDef> = match resolver.resolve_path(self.db, &path).take_types() { | ||
447 | Some(Resolution::Def(def)) => def.into(), | ||
448 | Some(Resolution::LocalBinding(..)) => { | ||
449 | // this cannot happen | ||
450 | log::error!("path resolved to local binding in type ns"); | ||
451 | return (Ty::Unknown, None); | ||
452 | } | ||
453 | Some(Resolution::GenericParam(..)) => { | ||
454 | // generic params can't be used in struct literals | ||
455 | return (Ty::Unknown, None); | ||
456 | } | ||
457 | Some(Resolution::SelfType(..)) => { | ||
458 | // TODO this is allowed in an impl for a struct, handle this | ||
459 | return (Ty::Unknown, None); | ||
460 | } | ||
461 | None => return (Ty::Unknown, None), | ||
462 | }; | ||
463 | let def = match typable { | ||
464 | None => return (Ty::Unknown, None), | ||
465 | Some(it) => it, | ||
466 | }; | ||
467 | // TODO remove the duplication between here and `Ty::from_path`? | ||
468 | let substs = Ty::substs_from_path(self.db, resolver, path, def); | ||
469 | match def { | ||
470 | TypableDef::Struct(s) => { | ||
471 | let ty = s.ty(self.db); | ||
472 | let ty = self.insert_type_vars(ty.apply_substs(substs)); | ||
473 | (ty, Some(s.into())) | ||
474 | } | ||
475 | TypableDef::EnumVariant(var) => { | ||
476 | let ty = var.parent_enum(self.db).ty(self.db); | ||
477 | let ty = self.insert_type_vars(ty.apply_substs(substs)); | ||
478 | (ty, Some(var.into())) | ||
479 | } | ||
480 | TypableDef::Function(_) | TypableDef::Enum(_) => (Ty::Unknown, None), | ||
481 | } | ||
482 | } | ||
483 | |||
484 | fn infer_tuple_struct_pat( | ||
485 | &mut self, | ||
486 | path: Option<&Path>, | ||
487 | subpats: &[PatId], | ||
488 | expected: &Ty, | ||
489 | ) -> Ty { | ||
490 | let (ty, def) = self.resolve_variant(path); | ||
491 | |||
492 | self.unify(&ty, expected); | ||
493 | |||
494 | let substs = ty.substs().unwrap_or_else(Substs::empty); | ||
495 | |||
496 | for (i, &subpat) in subpats.iter().enumerate() { | ||
497 | let expected_ty = def | ||
498 | .and_then(|d| d.field(self.db, &Name::tuple_field_name(i))) | ||
499 | .map_or(Ty::Unknown, |field| field.ty(self.db)) | ||
500 | .subst(&substs); | ||
501 | self.infer_pat(subpat, &expected_ty); | ||
502 | } | ||
503 | |||
504 | ty | ||
505 | } | ||
506 | |||
507 | fn infer_struct_pat(&mut self, path: Option<&Path>, subpats: &[FieldPat], expected: &Ty) -> Ty { | ||
508 | let (ty, def) = self.resolve_variant(path); | ||
509 | |||
510 | self.unify(&ty, expected); | ||
511 | |||
512 | let substs = ty.substs().unwrap_or_else(Substs::empty); | ||
513 | |||
514 | for subpat in subpats { | ||
515 | let matching_field = def.and_then(|it| it.field(self.db, &subpat.name)); | ||
516 | let expected_ty = | ||
517 | matching_field.map_or(Ty::Unknown, |field| field.ty(self.db)).subst(&substs); | ||
518 | self.infer_pat(subpat.pat, &expected_ty); | ||
519 | } | ||
520 | |||
521 | ty | ||
522 | } | ||
523 | |||
524 | fn infer_pat(&mut self, pat: PatId, expected: &Ty) -> Ty { | ||
525 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
526 | |||
527 | let ty = match &body[pat] { | ||
528 | Pat::Tuple(ref args) => { | ||
529 | let expectations = match *expected { | ||
530 | Ty::Tuple(ref tuple_args) => &**tuple_args, | ||
531 | _ => &[], | ||
532 | }; | ||
533 | let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown)); | ||
534 | |||
535 | let inner_tys = args | ||
536 | .iter() | ||
537 | .zip(expectations_iter) | ||
538 | .map(|(&pat, ty)| self.infer_pat(pat, ty)) | ||
539 | .collect::<Vec<_>>() | ||
540 | .into(); | ||
541 | |||
542 | Ty::Tuple(inner_tys) | ||
543 | } | ||
544 | Pat::Ref { pat, mutability } => { | ||
545 | let expectation = match *expected { | ||
546 | Ty::Ref(ref sub_ty, exp_mut) => { | ||
547 | if *mutability != exp_mut { | ||
548 | // TODO: emit type error? | ||
549 | } | ||
550 | &**sub_ty | ||
551 | } | ||
552 | _ => &Ty::Unknown, | ||
553 | }; | ||
554 | let subty = self.infer_pat(*pat, expectation); | ||
555 | Ty::Ref(subty.into(), *mutability) | ||
556 | } | ||
557 | Pat::TupleStruct { path: ref p, args: ref subpats } => { | ||
558 | self.infer_tuple_struct_pat(p.as_ref(), subpats, expected) | ||
559 | } | ||
560 | Pat::Struct { path: ref p, args: ref fields } => { | ||
561 | self.infer_struct_pat(p.as_ref(), fields, expected) | ||
562 | } | ||
563 | Pat::Path(path) => { | ||
564 | // TODO use correct resolver for the surrounding expression | ||
565 | let resolver = self.resolver.clone(); | ||
566 | self.infer_path_expr(&resolver, &path).unwrap_or(Ty::Unknown) | ||
567 | } | ||
568 | Pat::Bind { mode, name: _name, subpat } => { | ||
569 | let inner_ty = if let Some(subpat) = subpat { | ||
570 | self.infer_pat(*subpat, expected) | ||
571 | } else { | ||
572 | expected.clone() | ||
573 | }; | ||
574 | let inner_ty = self.insert_type_vars_shallow(inner_ty); | ||
575 | |||
576 | let bound_ty = match mode { | ||
577 | BindingAnnotation::Ref => Ty::Ref(inner_ty.clone().into(), Mutability::Shared), | ||
578 | BindingAnnotation::RefMut => Ty::Ref(inner_ty.clone().into(), Mutability::Mut), | ||
579 | BindingAnnotation::Mutable | BindingAnnotation::Unannotated => inner_ty.clone(), | ||
580 | }; | ||
581 | let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty); | ||
582 | self.write_pat_ty(pat, bound_ty); | ||
583 | return inner_ty; | ||
584 | } | ||
585 | _ => Ty::Unknown, | ||
586 | }; | ||
587 | // use a new type variable if we got Ty::Unknown here | ||
588 | let ty = self.insert_type_vars_shallow(ty); | ||
589 | self.unify(&ty, expected); | ||
590 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | ||
591 | self.write_pat_ty(pat, ty.clone()); | ||
592 | ty | ||
593 | } | ||
594 | |||
595 | fn substs_for_method_call( | ||
596 | &mut self, | ||
597 | def_generics: Option<Arc<GenericParams>>, | ||
598 | generic_args: &Option<GenericArgs>, | ||
599 | ) -> Substs { | ||
600 | let (parent_param_count, param_count) = | ||
601 | def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len())); | ||
602 | let mut substs = Vec::with_capacity(parent_param_count + param_count); | ||
603 | for _ in 0..parent_param_count { | ||
604 | substs.push(Ty::Unknown); | ||
605 | } | ||
606 | // handle provided type arguments | ||
607 | if let Some(generic_args) = generic_args { | ||
608 | // if args are provided, it should be all of them, but we can't rely on that | ||
609 | for arg in generic_args.args.iter().take(param_count) { | ||
610 | match arg { | ||
611 | GenericArg::Type(type_ref) => { | ||
612 | let ty = self.make_ty(type_ref); | ||
613 | substs.push(ty); | ||
614 | } | ||
615 | } | ||
616 | } | ||
617 | }; | ||
618 | let supplied_params = substs.len(); | ||
619 | for _ in supplied_params..parent_param_count + param_count { | ||
620 | substs.push(Ty::Unknown); | ||
621 | } | ||
622 | assert_eq!(substs.len(), parent_param_count + param_count); | ||
623 | Substs(substs.into()) | ||
624 | } | ||
625 | |||
626 | fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty { | ||
627 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
628 | let ty = match &body[tgt_expr] { | ||
629 | Expr::Missing => Ty::Unknown, | ||
630 | Expr::If { condition, then_branch, else_branch } => { | ||
631 | // if let is desugared to match, so this is always simple if | ||
632 | self.infer_expr(*condition, &Expectation::has_type(Ty::Bool)); | ||
633 | let then_ty = self.infer_expr(*then_branch, expected); | ||
634 | match else_branch { | ||
635 | Some(else_branch) => { | ||
636 | self.infer_expr(*else_branch, expected); | ||
637 | } | ||
638 | None => { | ||
639 | // no else branch -> unit | ||
640 | self.unify(&then_ty, &Ty::unit()); // actually coerce | ||
641 | } | ||
642 | }; | ||
643 | then_ty | ||
644 | } | ||
645 | Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected), | ||
646 | Expr::Loop { body } => { | ||
647 | self.infer_expr(*body, &Expectation::has_type(Ty::unit())); | ||
648 | // TODO handle break with value | ||
649 | Ty::Never | ||
650 | } | ||
651 | Expr::While { condition, body } => { | ||
652 | // while let is desugared to a match loop, so this is always simple while | ||
653 | self.infer_expr(*condition, &Expectation::has_type(Ty::Bool)); | ||
654 | self.infer_expr(*body, &Expectation::has_type(Ty::unit())); | ||
655 | Ty::unit() | ||
656 | } | ||
657 | Expr::For { iterable, body, pat } => { | ||
658 | let _iterable_ty = self.infer_expr(*iterable, &Expectation::none()); | ||
659 | self.infer_pat(*pat, &Ty::Unknown); | ||
660 | self.infer_expr(*body, &Expectation::has_type(Ty::unit())); | ||
661 | Ty::unit() | ||
662 | } | ||
663 | Expr::Lambda { body, args, arg_types } => { | ||
664 | assert_eq!(args.len(), arg_types.len()); | ||
665 | |||
666 | for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) { | ||
667 | let expected = if let Some(type_ref) = arg_type { | ||
668 | let ty = self.make_ty(type_ref); | ||
669 | ty | ||
670 | } else { | ||
671 | Ty::Unknown | ||
672 | }; | ||
673 | self.infer_pat(*arg_pat, &expected); | ||
674 | } | ||
675 | |||
676 | // TODO: infer lambda type etc. | ||
677 | let _body_ty = self.infer_expr(*body, &Expectation::none()); | ||
678 | Ty::Unknown | ||
679 | } | ||
680 | Expr::Call { callee, args } => { | ||
681 | let callee_ty = self.infer_expr(*callee, &Expectation::none()); | ||
682 | let (param_tys, ret_ty) = match &callee_ty { | ||
683 | Ty::FnPtr(sig) => (sig.input.clone(), sig.output.clone()), | ||
684 | Ty::FnDef { substs, sig, .. } => { | ||
685 | let ret_ty = sig.output.clone().subst(&substs); | ||
686 | let param_tys = | ||
687 | sig.input.iter().map(|ty| ty.clone().subst(&substs)).collect(); | ||
688 | (param_tys, ret_ty) | ||
689 | } | ||
690 | _ => { | ||
691 | // not callable | ||
692 | // TODO report an error? | ||
693 | (Vec::new(), Ty::Unknown) | ||
694 | } | ||
695 | }; | ||
696 | let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown)); | ||
697 | for (arg, param) in args.iter().zip(param_iter) { | ||
698 | self.infer_expr(*arg, &Expectation::has_type(param)); | ||
699 | } | ||
700 | ret_ty | ||
701 | } | ||
702 | Expr::MethodCall { receiver, args, method_name, generic_args } => { | ||
703 | let receiver_ty = self.infer_expr(*receiver, &Expectation::none()); | ||
704 | let resolved = receiver_ty.clone().lookup_method(self.db, method_name); | ||
705 | let (derefed_receiver_ty, method_ty, def_generics) = match resolved { | ||
706 | Some((ty, func)) => { | ||
707 | self.write_method_resolution(tgt_expr, func); | ||
708 | ( | ||
709 | ty, | ||
710 | self.db.type_for_def(func.into(), Namespace::Values), | ||
711 | Some(func.generic_params(self.db)), | ||
712 | ) | ||
713 | } | ||
714 | None => (Ty::Unknown, receiver_ty, None), | ||
715 | }; | ||
716 | let substs = self.substs_for_method_call(def_generics, generic_args); | ||
717 | let method_ty = method_ty.apply_substs(substs); | ||
718 | let method_ty = self.insert_type_vars(method_ty); | ||
719 | let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty { | ||
720 | Ty::FnPtr(sig) => { | ||
721 | if !sig.input.is_empty() { | ||
722 | (sig.input[0].clone(), sig.input[1..].to_vec(), sig.output.clone()) | ||
723 | } else { | ||
724 | (Ty::Unknown, Vec::new(), sig.output.clone()) | ||
725 | } | ||
726 | } | ||
727 | Ty::FnDef { substs, sig, .. } => { | ||
728 | let ret_ty = sig.output.clone().subst(&substs); | ||
729 | |||
730 | if !sig.input.is_empty() { | ||
731 | let mut arg_iter = sig.input.iter().map(|ty| ty.clone().subst(&substs)); | ||
732 | let receiver_ty = arg_iter.next().unwrap(); | ||
733 | (receiver_ty, arg_iter.collect(), ret_ty) | ||
734 | } else { | ||
735 | (Ty::Unknown, Vec::new(), ret_ty) | ||
736 | } | ||
737 | } | ||
738 | _ => (Ty::Unknown, Vec::new(), Ty::Unknown), | ||
739 | }; | ||
740 | // Apply autoref so the below unification works correctly | ||
741 | let actual_receiver_ty = match expected_receiver_ty { | ||
742 | Ty::Ref(_, mutability) => Ty::Ref(Arc::new(derefed_receiver_ty), mutability), | ||
743 | _ => derefed_receiver_ty, | ||
744 | }; | ||
745 | self.unify(&expected_receiver_ty, &actual_receiver_ty); | ||
746 | |||
747 | let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown)); | ||
748 | for (arg, param) in args.iter().zip(param_iter) { | ||
749 | self.infer_expr(*arg, &Expectation::has_type(param)); | ||
750 | } | ||
751 | ret_ty | ||
752 | } | ||
753 | Expr::Match { expr, arms } => { | ||
754 | let expected = if expected.ty == Ty::Unknown { | ||
755 | Expectation::has_type(self.new_type_var()) | ||
756 | } else { | ||
757 | expected.clone() | ||
758 | }; | ||
759 | let input_ty = self.infer_expr(*expr, &Expectation::none()); | ||
760 | |||
761 | for arm in arms { | ||
762 | for &pat in &arm.pats { | ||
763 | let _pat_ty = self.infer_pat(pat, &input_ty); | ||
764 | } | ||
765 | if let Some(guard_expr) = arm.guard { | ||
766 | self.infer_expr(guard_expr, &Expectation::has_type(Ty::Bool)); | ||
767 | } | ||
768 | self.infer_expr(arm.expr, &expected); | ||
769 | } | ||
770 | |||
771 | expected.ty | ||
772 | } | ||
773 | Expr::Path(p) => { | ||
774 | // TODO this could be more efficient... | ||
775 | let resolver = expr::resolver_for_expr(self.body.clone(), self.db, tgt_expr); | ||
776 | self.infer_path_expr(&resolver, p).unwrap_or(Ty::Unknown) | ||
777 | } | ||
778 | Expr::Continue => Ty::Never, | ||
779 | Expr::Break { expr } => { | ||
780 | if let Some(expr) = expr { | ||
781 | // TODO handle break with value | ||
782 | self.infer_expr(*expr, &Expectation::none()); | ||
783 | } | ||
784 | Ty::Never | ||
785 | } | ||
786 | Expr::Return { expr } => { | ||
787 | if let Some(expr) = expr { | ||
788 | self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone())); | ||
789 | } | ||
790 | Ty::Never | ||
791 | } | ||
792 | Expr::StructLit { path, fields, spread } => { | ||
793 | let (ty, def_id) = self.resolve_variant(path.as_ref()); | ||
794 | let substs = ty.substs().unwrap_or_else(Substs::empty); | ||
795 | for field in fields { | ||
796 | let field_ty = def_id | ||
797 | .and_then(|it| it.field(self.db, &field.name)) | ||
798 | .map_or(Ty::Unknown, |field| field.ty(self.db)) | ||
799 | .subst(&substs); | ||
800 | self.infer_expr(field.expr, &Expectation::has_type(field_ty)); | ||
801 | } | ||
802 | if let Some(expr) = spread { | ||
803 | self.infer_expr(*expr, &Expectation::has_type(ty.clone())); | ||
804 | } | ||
805 | ty | ||
806 | } | ||
807 | Expr::Field { expr, name } => { | ||
808 | let receiver_ty = self.infer_expr(*expr, &Expectation::none()); | ||
809 | let ty = receiver_ty | ||
810 | .autoderef(self.db) | ||
811 | .find_map(|derefed_ty| match derefed_ty { | ||
812 | Ty::Tuple(fields) => { | ||
813 | let i = name.to_string().parse::<usize>().ok(); | ||
814 | i.and_then(|i| fields.get(i).cloned()) | ||
815 | } | ||
816 | Ty::Adt { def_id: AdtDef::Struct(s), ref substs, .. } => { | ||
817 | s.field(self.db, name).map(|field| { | ||
818 | self.write_field_resolution(tgt_expr, field); | ||
819 | field.ty(self.db).subst(substs) | ||
820 | }) | ||
821 | } | ||
822 | _ => None, | ||
823 | }) | ||
824 | .unwrap_or(Ty::Unknown); | ||
825 | self.insert_type_vars(ty) | ||
826 | } | ||
827 | Expr::Try { expr } => { | ||
828 | let _inner_ty = self.infer_expr(*expr, &Expectation::none()); | ||
829 | Ty::Unknown | ||
830 | } | ||
831 | Expr::Cast { expr, type_ref } => { | ||
832 | let _inner_ty = self.infer_expr(*expr, &Expectation::none()); | ||
833 | let cast_ty = self.make_ty(type_ref); | ||
834 | // TODO check the cast... | ||
835 | cast_ty | ||
836 | } | ||
837 | Expr::Ref { expr, mutability } => { | ||
838 | let expectation = if let Ty::Ref(ref subty, expected_mutability) = expected.ty { | ||
839 | if expected_mutability == Mutability::Mut && *mutability == Mutability::Shared { | ||
840 | // TODO: throw type error - expected mut reference but found shared ref, | ||
841 | // which cannot be coerced | ||
842 | } | ||
843 | Expectation::has_type((**subty).clone()) | ||
844 | } else { | ||
845 | Expectation::none() | ||
846 | }; | ||
847 | // TODO reference coercions etc. | ||
848 | let inner_ty = self.infer_expr(*expr, &expectation); | ||
849 | Ty::Ref(Arc::new(inner_ty), *mutability) | ||
850 | } | ||
851 | Expr::UnaryOp { expr, op } => { | ||
852 | let inner_ty = self.infer_expr(*expr, &Expectation::none()); | ||
853 | match op { | ||
854 | UnaryOp::Deref => { | ||
855 | if let Some(derefed_ty) = inner_ty.builtin_deref() { | ||
856 | derefed_ty | ||
857 | } else { | ||
858 | // TODO Deref::deref | ||
859 | Ty::Unknown | ||
860 | } | ||
861 | } | ||
862 | UnaryOp::Neg => { | ||
863 | match inner_ty { | ||
864 | Ty::Int(primitive::UncertainIntTy::Unknown) | ||
865 | | Ty::Int(primitive::UncertainIntTy::Signed(..)) | ||
866 | | Ty::Infer(InferTy::IntVar(..)) | ||
867 | | Ty::Infer(InferTy::FloatVar(..)) | ||
868 | | Ty::Float(..) => inner_ty, | ||
869 | // TODO: resolve ops::Neg trait | ||
870 | _ => Ty::Unknown, | ||
871 | } | ||
872 | } | ||
873 | UnaryOp::Not => { | ||
874 | match inner_ty { | ||
875 | Ty::Bool | Ty::Int(_) | Ty::Infer(InferTy::IntVar(..)) => inner_ty, | ||
876 | // TODO: resolve ops::Not trait for inner_ty | ||
877 | _ => Ty::Unknown, | ||
878 | } | ||
879 | } | ||
880 | } | ||
881 | } | ||
882 | Expr::BinaryOp { lhs, rhs, op } => match op { | ||
883 | Some(op) => { | ||
884 | let lhs_expectation = match op { | ||
885 | BinaryOp::BooleanAnd | BinaryOp::BooleanOr => { | ||
886 | Expectation::has_type(Ty::Bool) | ||
887 | } | ||
888 | _ => Expectation::none(), | ||
889 | }; | ||
890 | let lhs_ty = self.infer_expr(*lhs, &lhs_expectation); | ||
891 | // TODO: find implementation of trait corresponding to operation | ||
892 | // symbol and resolve associated `Output` type | ||
893 | let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty); | ||
894 | let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation)); | ||
895 | |||
896 | // TODO: similar as above, return ty is often associated trait type | ||
897 | op::binary_op_return_ty(*op, rhs_ty) | ||
898 | } | ||
899 | _ => Ty::Unknown, | ||
900 | }, | ||
901 | Expr::Tuple { exprs } => { | ||
902 | let mut ty_vec = Vec::with_capacity(exprs.len()); | ||
903 | for arg in exprs.iter() { | ||
904 | ty_vec.push(self.infer_expr(*arg, &Expectation::none())); | ||
905 | } | ||
906 | |||
907 | Ty::Tuple(Arc::from(ty_vec)) | ||
908 | } | ||
909 | Expr::Array { exprs } => { | ||
910 | let elem_ty = match &expected.ty { | ||
911 | Ty::Slice(inner) | Ty::Array(inner) => Ty::clone(&inner), | ||
912 | _ => self.new_type_var(), | ||
913 | }; | ||
914 | |||
915 | for expr in exprs.iter() { | ||
916 | self.infer_expr(*expr, &Expectation::has_type(elem_ty.clone())); | ||
917 | } | ||
918 | |||
919 | Ty::Array(Arc::new(elem_ty)) | ||
920 | } | ||
921 | Expr::Literal(lit) => match lit { | ||
922 | Literal::Bool(..) => Ty::Bool, | ||
923 | Literal::String(..) => Ty::Ref(Arc::new(Ty::Str), Mutability::Shared), | ||
924 | Literal::ByteString(..) => { | ||
925 | let byte_type = Arc::new(Ty::Int(primitive::UncertainIntTy::Unsigned( | ||
926 | primitive::UintTy::U8, | ||
927 | ))); | ||
928 | let slice_type = Arc::new(Ty::Slice(byte_type)); | ||
929 | Ty::Ref(slice_type, Mutability::Shared) | ||
930 | } | ||
931 | Literal::Char(..) => Ty::Char, | ||
932 | Literal::Int(_v, ty) => Ty::Int(*ty), | ||
933 | Literal::Float(_v, ty) => Ty::Float(*ty), | ||
934 | }, | ||
935 | }; | ||
936 | // use a new type variable if we got Ty::Unknown here | ||
937 | let ty = self.insert_type_vars_shallow(ty); | ||
938 | self.unify(&ty, &expected.ty); | ||
939 | let ty = self.resolve_ty_as_possible(&mut vec![], ty); | ||
940 | self.write_expr_ty(tgt_expr, ty.clone()); | ||
941 | ty | ||
942 | } | ||
943 | |||
944 | fn infer_block( | ||
945 | &mut self, | ||
946 | statements: &[Statement], | ||
947 | tail: Option<ExprId>, | ||
948 | expected: &Expectation, | ||
949 | ) -> Ty { | ||
950 | for stmt in statements { | ||
951 | match stmt { | ||
952 | Statement::Let { pat, type_ref, initializer } => { | ||
953 | let decl_ty = | ||
954 | type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown); | ||
955 | let decl_ty = self.insert_type_vars(decl_ty); | ||
956 | let ty = if let Some(expr) = initializer { | ||
957 | let expr_ty = self.infer_expr(*expr, &Expectation::has_type(decl_ty)); | ||
958 | expr_ty | ||
959 | } else { | ||
960 | decl_ty | ||
961 | }; | ||
962 | |||
963 | self.infer_pat(*pat, &ty); | ||
964 | } | ||
965 | Statement::Expr(expr) => { | ||
966 | self.infer_expr(*expr, &Expectation::none()); | ||
967 | } | ||
968 | } | ||
969 | } | ||
970 | let ty = if let Some(expr) = tail { self.infer_expr(expr, expected) } else { Ty::unit() }; | ||
971 | ty | ||
972 | } | ||
973 | |||
974 | fn collect_fn_signature(&mut self, signature: &FnSignature) { | ||
975 | let body = Arc::clone(&self.body); // avoid borrow checker problem | ||
976 | for (type_ref, pat) in signature.params().iter().zip(body.params()) { | ||
977 | let ty = self.make_ty(type_ref); | ||
978 | |||
979 | self.infer_pat(*pat, &ty); | ||
980 | } | ||
981 | self.return_ty = self.make_ty(signature.ret_type()); | ||
982 | } | ||
983 | |||
984 | fn infer_body(&mut self) { | ||
985 | self.infer_expr(self.body.body_expr(), &Expectation::has_type(self.return_ty.clone())); | ||
986 | } | ||
987 | } | ||
988 | |||
989 | /// The ID of a type variable. | ||
990 | #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] | ||
991 | pub struct TypeVarId(u32); | ||
992 | |||
993 | impl UnifyKey for TypeVarId { | ||
994 | type Value = TypeVarValue; | ||
995 | |||
996 | fn index(&self) -> u32 { | ||
997 | self.0 | ||
998 | } | ||
999 | |||
1000 | fn from_index(i: u32) -> Self { | ||
1001 | TypeVarId(i) | ||
1002 | } | ||
1003 | |||
1004 | fn tag() -> &'static str { | ||
1005 | "TypeVarId" | ||
1006 | } | ||
1007 | } | ||
1008 | |||
1009 | /// The value of a type variable: either we already know the type, or we don't | ||
1010 | /// know it yet. | ||
1011 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
1012 | pub enum TypeVarValue { | ||
1013 | Known(Ty), | ||
1014 | Unknown, | ||
1015 | } | ||
1016 | |||
1017 | impl TypeVarValue { | ||
1018 | fn known(&self) -> Option<&Ty> { | ||
1019 | match self { | ||
1020 | TypeVarValue::Known(ty) => Some(ty), | ||
1021 | TypeVarValue::Unknown => None, | ||
1022 | } | ||
1023 | } | ||
1024 | } | ||
1025 | |||
1026 | impl UnifyValue for TypeVarValue { | ||
1027 | type Error = NoError; | ||
1028 | |||
1029 | fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> { | ||
1030 | match (value1, value2) { | ||
1031 | // We should never equate two type variables, both of which have | ||
1032 | // known types. Instead, we recursively equate those types. | ||
1033 | (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!( | ||
1034 | "equating two type variables, both of which have known types: {:?} and {:?}", | ||
1035 | t1, t2 | ||
1036 | ), | ||
1037 | |||
1038 | // If one side is known, prefer that one. | ||
1039 | (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()), | ||
1040 | (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()), | ||
1041 | |||
1042 | (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown), | ||
1043 | } | ||
1044 | } | ||
1045 | } | ||
1046 | |||
1047 | /// The kinds of placeholders we need during type inference. There's separate | ||
1048 | /// values for general types, and for integer and float variables. The latter | ||
1049 | /// two are used for inference of literal values (e.g. `100` could be one of | ||
1050 | /// several integer types). | ||
1051 | #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)] | ||
1052 | pub enum InferTy { | ||
1053 | TypeVar(TypeVarId), | ||
1054 | IntVar(TypeVarId), | ||
1055 | FloatVar(TypeVarId), | ||
1056 | } | ||
1057 | |||
1058 | impl InferTy { | ||
1059 | fn to_inner(self) -> TypeVarId { | ||
1060 | match self { | ||
1061 | InferTy::TypeVar(ty) | InferTy::IntVar(ty) | InferTy::FloatVar(ty) => ty, | ||
1062 | } | ||
1063 | } | ||
1064 | |||
1065 | fn fallback_value(self) -> Ty { | ||
1066 | match self { | ||
1067 | InferTy::TypeVar(..) => Ty::Unknown, | ||
1068 | InferTy::IntVar(..) => { | ||
1069 | Ty::Int(primitive::UncertainIntTy::Signed(primitive::IntTy::I32)) | ||
1070 | } | ||
1071 | InferTy::FloatVar(..) => { | ||
1072 | Ty::Float(primitive::UncertainFloatTy::Known(primitive::FloatTy::F64)) | ||
1073 | } | ||
1074 | } | ||
1075 | } | ||
1076 | } | ||
1077 | |||
1078 | /// When inferring an expression, we propagate downward whatever type hint we | ||
1079 | /// are able in the form of an `Expectation`. | ||
1080 | #[derive(Clone, PartialEq, Eq, Debug)] | ||
1081 | struct Expectation { | ||
1082 | ty: Ty, | ||
1083 | // TODO: In some cases, we need to be aware whether the expectation is that | ||
1084 | // the type match exactly what we passed, or whether it just needs to be | ||
1085 | // coercible to the expected type. See Expectation::rvalue_hint in rustc. | ||
1086 | } | ||
1087 | |||
1088 | impl Expectation { | ||
1089 | /// The expectation that the type of the expression needs to equal the given | ||
1090 | /// type. | ||
1091 | fn has_type(ty: Ty) -> Self { | ||
1092 | Expectation { ty } | ||
1093 | } | ||
1094 | |||
1095 | /// This expresses no expectation on the type. | ||
1096 | fn none() -> Self { | ||
1097 | Expectation { ty: Ty::Unknown } | ||
1098 | } | ||
1099 | } | ||
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs new file mode 100644 index 000000000..63e13a30e --- /dev/null +++ b/crates/ra_hir/src/ty/lower.rs | |||
@@ -0,0 +1,333 @@ | |||
1 | //! Methods for lowering the HIR to types. There are two main cases here: | ||
2 | //! | ||
3 | //! - Lowering a type reference like `&usize` or `Option<foo::bar::Baz>` to a | ||
4 | //! type: The entry point for this is `Ty::from_hir`. | ||
5 | //! - Building the type for an item: This happens through the `type_for_def` query. | ||
6 | //! | ||
7 | //! This usually involves resolving names, collecting generic arguments etc. | ||
8 | |||
9 | use std::sync::Arc; | ||
10 | |||
11 | use crate::{ | ||
12 | Function, Struct, StructField, Enum, EnumVariant, Path, Name, | ||
13 | ModuleDef, | ||
14 | HirDatabase, | ||
15 | type_ref::TypeRef, | ||
16 | name::KnownName, | ||
17 | nameres::Namespace, | ||
18 | resolve::{Resolver, Resolution}, | ||
19 | path::{ PathSegment, GenericArg}, | ||
20 | generics::GenericParams, | ||
21 | adt::VariantDef, | ||
22 | }; | ||
23 | use super::{Ty, primitive, FnSig, Substs}; | ||
24 | |||
25 | impl Ty { | ||
26 | pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self { | ||
27 | match type_ref { | ||
28 | TypeRef::Never => Ty::Never, | ||
29 | TypeRef::Tuple(inner) => { | ||
30 | let inner_tys = | ||
31 | inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); | ||
32 | Ty::Tuple(inner_tys.into()) | ||
33 | } | ||
34 | TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path), | ||
35 | TypeRef::RawPtr(inner, mutability) => { | ||
36 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
37 | Ty::RawPtr(Arc::new(inner_ty), *mutability) | ||
38 | } | ||
39 | TypeRef::Array(inner) => { | ||
40 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
41 | Ty::Array(Arc::new(inner_ty)) | ||
42 | } | ||
43 | TypeRef::Slice(inner) => { | ||
44 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
45 | Ty::Slice(Arc::new(inner_ty)) | ||
46 | } | ||
47 | TypeRef::Reference(inner, mutability) => { | ||
48 | let inner_ty = Ty::from_hir(db, resolver, inner); | ||
49 | Ty::Ref(Arc::new(inner_ty), *mutability) | ||
50 | } | ||
51 | TypeRef::Placeholder => Ty::Unknown, | ||
52 | TypeRef::Fn(params) => { | ||
53 | let mut inner_tys = | ||
54 | params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); | ||
55 | let return_ty = | ||
56 | inner_tys.pop().expect("TypeRef::Fn should always have at least return type"); | ||
57 | let sig = FnSig { input: inner_tys, output: return_ty }; | ||
58 | Ty::FnPtr(Arc::new(sig)) | ||
59 | } | ||
60 | TypeRef::Error => Ty::Unknown, | ||
61 | } | ||
62 | } | ||
63 | |||
64 | pub(crate) fn from_hir_path(db: &impl HirDatabase, resolver: &Resolver, path: &Path) -> Self { | ||
65 | if let Some(name) = path.as_ident() { | ||
66 | // TODO handle primitive type names in resolver as well? | ||
67 | if let Some(int_ty) = primitive::UncertainIntTy::from_name(name) { | ||
68 | return Ty::Int(int_ty); | ||
69 | } else if let Some(float_ty) = primitive::UncertainFloatTy::from_name(name) { | ||
70 | return Ty::Float(float_ty); | ||
71 | } else if let Some(known) = name.as_known_name() { | ||
72 | match known { | ||
73 | KnownName::Bool => return Ty::Bool, | ||
74 | KnownName::Char => return Ty::Char, | ||
75 | KnownName::Str => return Ty::Str, | ||
76 | _ => {} | ||
77 | } | ||
78 | } | ||
79 | } | ||
80 | |||
81 | // Resolve the path (in type namespace) | ||
82 | let resolution = resolver.resolve_path(db, path).take_types(); | ||
83 | |||
84 | let def = match resolution { | ||
85 | Some(Resolution::Def(def)) => def, | ||
86 | Some(Resolution::LocalBinding(..)) => { | ||
87 | // this should never happen | ||
88 | panic!("path resolved to local binding in type ns"); | ||
89 | } | ||
90 | Some(Resolution::GenericParam(idx)) => { | ||
91 | return Ty::Param { | ||
92 | idx, | ||
93 | // TODO: maybe return name in resolution? | ||
94 | name: path | ||
95 | .as_ident() | ||
96 | .expect("generic param should be single-segment path") | ||
97 | .clone(), | ||
98 | }; | ||
99 | } | ||
100 | Some(Resolution::SelfType(impl_block)) => { | ||
101 | return impl_block.target_ty(db); | ||
102 | } | ||
103 | None => return Ty::Unknown, | ||
104 | }; | ||
105 | |||
106 | let typable: TypableDef = match def.into() { | ||
107 | None => return Ty::Unknown, | ||
108 | Some(it) => it, | ||
109 | }; | ||
110 | let ty = db.type_for_def(typable, Namespace::Types); | ||
111 | let substs = Ty::substs_from_path(db, resolver, path, typable); | ||
112 | ty.apply_substs(substs) | ||
113 | } | ||
114 | |||
115 | pub(super) fn substs_from_path_segment( | ||
116 | db: &impl HirDatabase, | ||
117 | resolver: &Resolver, | ||
118 | segment: &PathSegment, | ||
119 | resolved: TypableDef, | ||
120 | ) -> Substs { | ||
121 | let mut substs = Vec::new(); | ||
122 | let def_generics = match resolved { | ||
123 | TypableDef::Function(func) => func.generic_params(db), | ||
124 | TypableDef::Struct(s) => s.generic_params(db), | ||
125 | TypableDef::Enum(e) => e.generic_params(db), | ||
126 | TypableDef::EnumVariant(var) => var.parent_enum(db).generic_params(db), | ||
127 | }; | ||
128 | let parent_param_count = def_generics.count_parent_params(); | ||
129 | substs.extend((0..parent_param_count).map(|_| Ty::Unknown)); | ||
130 | if let Some(generic_args) = &segment.args_and_bindings { | ||
131 | // if args are provided, it should be all of them, but we can't rely on that | ||
132 | let param_count = def_generics.params.len(); | ||
133 | for arg in generic_args.args.iter().take(param_count) { | ||
134 | match arg { | ||
135 | GenericArg::Type(type_ref) => { | ||
136 | let ty = Ty::from_hir(db, resolver, type_ref); | ||
137 | substs.push(ty); | ||
138 | } | ||
139 | } | ||
140 | } | ||
141 | } | ||
142 | // add placeholders for args that were not provided | ||
143 | // TODO: handle defaults | ||
144 | let supplied_params = substs.len(); | ||
145 | for _ in supplied_params..def_generics.count_params_including_parent() { | ||
146 | substs.push(Ty::Unknown); | ||
147 | } | ||
148 | assert_eq!(substs.len(), def_generics.count_params_including_parent()); | ||
149 | Substs(substs.into()) | ||
150 | } | ||
151 | |||
152 | /// Collect generic arguments from a path into a `Substs`. See also | ||
153 | /// `create_substs_for_ast_path` and `def_to_ty` in rustc. | ||
154 | pub(super) fn substs_from_path( | ||
155 | db: &impl HirDatabase, | ||
156 | resolver: &Resolver, | ||
157 | path: &Path, | ||
158 | resolved: TypableDef, | ||
159 | ) -> Substs { | ||
160 | let last = path.segments.last().expect("path should have at least one segment"); | ||
161 | let segment = match resolved { | ||
162 | TypableDef::Function(_) => last, | ||
163 | TypableDef::Struct(_) => last, | ||
164 | TypableDef::Enum(_) => last, | ||
165 | TypableDef::EnumVariant(_) => { | ||
166 | // the generic args for an enum variant may be either specified | ||
167 | // on the segment referring to the enum, or on the segment | ||
168 | // referring to the variant. So `Option::<T>::None` and | ||
169 | // `Option::None::<T>` are both allowed (though the former is | ||
170 | // preferred). See also `def_ids_for_path_segments` in rustc. | ||
171 | let len = path.segments.len(); | ||
172 | let segment = if len >= 2 && path.segments[len - 2].args_and_bindings.is_some() { | ||
173 | // Option::<T>::None | ||
174 | &path.segments[len - 2] | ||
175 | } else { | ||
176 | // Option::None::<T> | ||
177 | last | ||
178 | }; | ||
179 | segment | ||
180 | } | ||
181 | }; | ||
182 | Ty::substs_from_path_segment(db, resolver, segment, resolved) | ||
183 | } | ||
184 | } | ||
185 | |||
186 | /// Build the declared type of an item. This depends on the namespace; e.g. for | ||
187 | /// `struct Foo(usize)`, we have two types: The type of the struct itself, and | ||
188 | /// the constructor function `(usize) -> Foo` which lives in the values | ||
189 | /// namespace. | ||
190 | pub(crate) fn type_for_def(db: &impl HirDatabase, def: TypableDef, ns: Namespace) -> Ty { | ||
191 | match (def, ns) { | ||
192 | (TypableDef::Function(f), Namespace::Values) => type_for_fn(db, f), | ||
193 | (TypableDef::Struct(s), Namespace::Types) => type_for_struct(db, s), | ||
194 | (TypableDef::Struct(s), Namespace::Values) => type_for_struct_constructor(db, s), | ||
195 | (TypableDef::Enum(e), Namespace::Types) => type_for_enum(db, e), | ||
196 | (TypableDef::EnumVariant(v), Namespace::Values) => type_for_enum_variant_constructor(db, v), | ||
197 | |||
198 | // 'error' cases: | ||
199 | (TypableDef::Function(_), Namespace::Types) => Ty::Unknown, | ||
200 | (TypableDef::Enum(_), Namespace::Values) => Ty::Unknown, | ||
201 | (TypableDef::EnumVariant(_), Namespace::Types) => Ty::Unknown, | ||
202 | } | ||
203 | } | ||
204 | |||
205 | /// Build the type of a specific field of a struct or enum variant. | ||
206 | pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty { | ||
207 | let parent_def = field.parent_def(db); | ||
208 | let resolver = match parent_def { | ||
209 | VariantDef::Struct(it) => it.resolver(db), | ||
210 | VariantDef::EnumVariant(it) => it.parent_enum(db).resolver(db), | ||
211 | }; | ||
212 | let var_data = parent_def.variant_data(db); | ||
213 | let type_ref = &var_data.fields().unwrap()[field.id].type_ref; | ||
214 | Ty::from_hir(db, &resolver, type_ref) | ||
215 | } | ||
216 | |||
217 | /// Build the declared type of a function. This should not need to look at the | ||
218 | /// function body. | ||
219 | fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { | ||
220 | let signature = def.signature(db); | ||
221 | let resolver = def.resolver(db); | ||
222 | let generics = def.generic_params(db); | ||
223 | let name = def.name(db); | ||
224 | let input = | ||
225 | signature.params().iter().map(|tr| Ty::from_hir(db, &resolver, tr)).collect::<Vec<_>>(); | ||
226 | let output = Ty::from_hir(db, &resolver, signature.ret_type()); | ||
227 | let sig = Arc::new(FnSig { input, output }); | ||
228 | let substs = make_substs(&generics); | ||
229 | Ty::FnDef { def: def.into(), sig, name, substs } | ||
230 | } | ||
231 | |||
232 | /// Build the type of a tuple struct constructor. | ||
233 | fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty { | ||
234 | let var_data = def.variant_data(db); | ||
235 | let fields = match var_data.fields() { | ||
236 | Some(fields) => fields, | ||
237 | None => return type_for_struct(db, def), // Unit struct | ||
238 | }; | ||
239 | let resolver = def.resolver(db); | ||
240 | let generics = def.generic_params(db); | ||
241 | let name = def.name(db).unwrap_or_else(Name::missing); | ||
242 | let input = fields | ||
243 | .iter() | ||
244 | .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) | ||
245 | .collect::<Vec<_>>(); | ||
246 | let output = type_for_struct(db, def); | ||
247 | let sig = Arc::new(FnSig { input, output }); | ||
248 | let substs = make_substs(&generics); | ||
249 | Ty::FnDef { def: def.into(), sig, name, substs } | ||
250 | } | ||
251 | |||
252 | /// Build the type of a tuple enum variant constructor. | ||
253 | fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) -> Ty { | ||
254 | let var_data = def.variant_data(db); | ||
255 | let fields = match var_data.fields() { | ||
256 | Some(fields) => fields, | ||
257 | None => return type_for_enum(db, def.parent_enum(db)), // Unit variant | ||
258 | }; | ||
259 | let resolver = def.parent_enum(db).resolver(db); | ||
260 | let generics = def.parent_enum(db).generic_params(db); | ||
261 | let name = def.name(db).unwrap_or_else(Name::missing); | ||
262 | let input = fields | ||
263 | .iter() | ||
264 | .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) | ||
265 | .collect::<Vec<_>>(); | ||
266 | let substs = make_substs(&generics); | ||
267 | let output = type_for_enum(db, def.parent_enum(db)).apply_substs(substs.clone()); | ||
268 | let sig = Arc::new(FnSig { input, output }); | ||
269 | Ty::FnDef { def: def.into(), sig, name, substs } | ||
270 | } | ||
271 | |||
272 | fn make_substs(generics: &GenericParams) -> Substs { | ||
273 | Substs( | ||
274 | generics | ||
275 | .params_including_parent() | ||
276 | .into_iter() | ||
277 | .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() }) | ||
278 | .collect::<Vec<_>>() | ||
279 | .into(), | ||
280 | ) | ||
281 | } | ||
282 | |||
283 | fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { | ||
284 | let generics = s.generic_params(db); | ||
285 | Ty::Adt { | ||
286 | def_id: s.into(), | ||
287 | name: s.name(db).unwrap_or_else(Name::missing), | ||
288 | substs: make_substs(&generics), | ||
289 | } | ||
290 | } | ||
291 | |||
292 | fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { | ||
293 | let generics = s.generic_params(db); | ||
294 | Ty::Adt { | ||
295 | def_id: s.into(), | ||
296 | name: s.name(db).unwrap_or_else(Name::missing), | ||
297 | substs: make_substs(&generics), | ||
298 | } | ||
299 | } | ||
300 | |||
301 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] | ||
302 | pub enum TypableDef { | ||
303 | Function(Function), | ||
304 | Struct(Struct), | ||
305 | Enum(Enum), | ||
306 | EnumVariant(EnumVariant), | ||
307 | } | ||
308 | impl_froms!(TypableDef: Function, Struct, Enum, EnumVariant); | ||
309 | |||
310 | impl From<ModuleDef> for Option<TypableDef> { | ||
311 | fn from(def: ModuleDef) -> Option<TypableDef> { | ||
312 | let res = match def { | ||
313 | ModuleDef::Function(f) => f.into(), | ||
314 | ModuleDef::Struct(s) => s.into(), | ||
315 | ModuleDef::Enum(e) => e.into(), | ||
316 | ModuleDef::EnumVariant(v) => v.into(), | ||
317 | ModuleDef::Const(_) | ||
318 | | ModuleDef::Static(_) | ||
319 | | ModuleDef::Module(_) | ||
320 | | ModuleDef::Trait(_) | ||
321 | | ModuleDef::Type(_) => return None, | ||
322 | }; | ||
323 | Some(res) | ||
324 | } | ||
325 | } | ||
326 | |||
327 | #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] | ||
328 | pub enum CallableDef { | ||
329 | Function(Function), | ||
330 | Struct(Struct), | ||
331 | EnumVariant(EnumVariant), | ||
332 | } | ||
333 | impl_froms!(CallableDef: Function, Struct, EnumVariant); | ||
diff --git a/crates/ra_hir/src/ty/op.rs b/crates/ra_hir/src/ty/op.rs new file mode 100644 index 000000000..8703cf236 --- /dev/null +++ b/crates/ra_hir/src/ty/op.rs | |||
@@ -0,0 +1,81 @@ | |||
1 | use crate::expr::BinaryOp; | ||
2 | use super::{Ty, InferTy}; | ||
3 | |||
4 | pub(super) fn binary_op_return_ty(op: BinaryOp, rhs_ty: Ty) -> Ty { | ||
5 | match op { | ||
6 | BinaryOp::BooleanOr | ||
7 | | BinaryOp::BooleanAnd | ||
8 | | BinaryOp::EqualityTest | ||
9 | | BinaryOp::NegatedEqualityTest | ||
10 | | BinaryOp::LesserEqualTest | ||
11 | | BinaryOp::GreaterEqualTest | ||
12 | | BinaryOp::LesserTest | ||
13 | | BinaryOp::GreaterTest => Ty::Bool, | ||
14 | BinaryOp::Assignment | ||
15 | | BinaryOp::AddAssign | ||
16 | | BinaryOp::SubAssign | ||
17 | | BinaryOp::DivAssign | ||
18 | | BinaryOp::MulAssign | ||
19 | | BinaryOp::RemAssign | ||
20 | | BinaryOp::ShrAssign | ||
21 | | BinaryOp::ShlAssign | ||
22 | | BinaryOp::BitAndAssign | ||
23 | | BinaryOp::BitOrAssign | ||
24 | | BinaryOp::BitXorAssign => Ty::unit(), | ||
25 | BinaryOp::Addition | ||
26 | | BinaryOp::Subtraction | ||
27 | | BinaryOp::Multiplication | ||
28 | | BinaryOp::Division | ||
29 | | BinaryOp::Remainder | ||
30 | | BinaryOp::LeftShift | ||
31 | | BinaryOp::RightShift | ||
32 | | BinaryOp::BitwiseAnd | ||
33 | | BinaryOp::BitwiseOr | ||
34 | | BinaryOp::BitwiseXor => match rhs_ty { | ||
35 | Ty::Int(..) | ||
36 | | Ty::Float(..) | ||
37 | | Ty::Infer(InferTy::IntVar(..)) | ||
38 | | Ty::Infer(InferTy::FloatVar(..)) => rhs_ty, | ||
39 | _ => Ty::Unknown, | ||
40 | }, | ||
41 | BinaryOp::RangeRightOpen | BinaryOp::RangeRightClosed => Ty::Unknown, | ||
42 | } | ||
43 | } | ||
44 | |||
45 | pub(super) fn binary_op_rhs_expectation(op: BinaryOp, lhs_ty: Ty) -> Ty { | ||
46 | match op { | ||
47 | BinaryOp::BooleanAnd | BinaryOp::BooleanOr => Ty::Bool, | ||
48 | BinaryOp::Assignment | BinaryOp::EqualityTest => match lhs_ty { | ||
49 | Ty::Int(..) | Ty::Float(..) | Ty::Str | Ty::Char | Ty::Bool => lhs_ty, | ||
50 | _ => Ty::Unknown, | ||
51 | }, | ||
52 | BinaryOp::LesserEqualTest | ||
53 | | BinaryOp::GreaterEqualTest | ||
54 | | BinaryOp::LesserTest | ||
55 | | BinaryOp::GreaterTest | ||
56 | | BinaryOp::AddAssign | ||
57 | | BinaryOp::SubAssign | ||
58 | | BinaryOp::DivAssign | ||
59 | | BinaryOp::MulAssign | ||
60 | | BinaryOp::RemAssign | ||
61 | | BinaryOp::ShrAssign | ||
62 | | BinaryOp::ShlAssign | ||
63 | | BinaryOp::BitAndAssign | ||
64 | | BinaryOp::BitOrAssign | ||
65 | | BinaryOp::BitXorAssign | ||
66 | | BinaryOp::Addition | ||
67 | | BinaryOp::Subtraction | ||
68 | | BinaryOp::Multiplication | ||
69 | | BinaryOp::Division | ||
70 | | BinaryOp::Remainder | ||
71 | | BinaryOp::LeftShift | ||
72 | | BinaryOp::RightShift | ||
73 | | BinaryOp::BitwiseAnd | ||
74 | | BinaryOp::BitwiseOr | ||
75 | | BinaryOp::BitwiseXor => match lhs_ty { | ||
76 | Ty::Int(..) | Ty::Float(..) => lhs_ty, | ||
77 | _ => Ty::Unknown, | ||
78 | }, | ||
79 | _ => Ty::Unknown, | ||
80 | } | ||
81 | } | ||
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap index fe5d6590e..44694dfdb 100644 --- a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap +++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap | |||
@@ -1,5 +1,5 @@ | |||
1 | --- | 1 | --- |
2 | created: "2019-02-21T10:25:18.568887300Z" | 2 | created: "2019-02-23T21:58:35.844769207Z" |
3 | creator: [email protected] | 3 | creator: [email protected] |
4 | source: crates/ra_hir/src/ty/tests.rs | 4 | source: crates/ra_hir/src/ty/tests.rs |
5 | expression: "&result" | 5 | expression: "&result" |
@@ -9,8 +9,8 @@ expression: "&result" | |||
9 | [92; 103) 'Gen { val }': Gen<T> | 9 | [92; 103) 'Gen { val }': Gen<T> |
10 | [98; 101) 'val': T | 10 | [98; 101) 'val': T |
11 | [123; 155) '{ ...32); }': () | 11 | [123; 155) '{ ...32); }': () |
12 | [133; 134) 'a': Gen<[unknown]> | 12 | [133; 134) 'a': Gen<u32> |
13 | [137; 146) 'Gen::make': fn make<[unknown]>(T) -> Gen<T> | 13 | [137; 146) 'Gen::make': fn make<u32>(T) -> Gen<T> |
14 | [137; 152) 'Gen::make(0u32)': Gen<[unknown]> | 14 | [137; 152) 'Gen::make(0u32)': Gen<u32> |
15 | [147; 151) '0u32': u32 | 15 | [147; 151) '0u32': u32 |
16 | 16 | ||
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index 77aeca669..d0da34677 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs | |||
@@ -719,7 +719,6 @@ fn test() { | |||
719 | } | 719 | } |
720 | 720 | ||
721 | #[test] | 721 | #[test] |
722 | #[ignore] // FIXME: After https://github.com/rust-analyzer/rust-analyzer/pull/866 is merged | ||
723 | fn infer_associated_method_generics() { | 722 | fn infer_associated_method_generics() { |
724 | check_inference( | 723 | check_inference( |
725 | "infer_associated_method_generics", | 724 | "infer_associated_method_generics", |