aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty/src/infer
diff options
context:
space:
mode:
authorSeivan Heidari <[email protected]>2019-11-28 07:19:14 +0000
committerSeivan Heidari <[email protected]>2019-11-28 07:19:14 +0000
commit18a0937585b836ec5ed054b9ae48e0156ab6d9ef (patch)
tree9de2c0267ddcc00df717f90034d0843d751a851b /crates/ra_hir_ty/src/infer
parenta7394b44c870f585eacfeb3036a33471aff49ff8 (diff)
parent484acc8a61d599662ed63a4cbda091d38a982551 (diff)
Merge branch 'master' of https://github.com/rust-analyzer/rust-analyzer into feature/themes
Diffstat (limited to 'crates/ra_hir_ty/src/infer')
-rw-r--r--crates/ra_hir_ty/src/infer/coerce.rs344
-rw-r--r--crates/ra_hir_ty/src/infer/expr.rs686
-rw-r--r--crates/ra_hir_ty/src/infer/pat.rs186
-rw-r--r--crates/ra_hir_ty/src/infer/path.rs268
-rw-r--r--crates/ra_hir_ty/src/infer/unify.rs162
5 files changed, 1646 insertions, 0 deletions
diff --git a/crates/ra_hir_ty/src/infer/coerce.rs b/crates/ra_hir_ty/src/infer/coerce.rs
new file mode 100644
index 000000000..719a0f395
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/coerce.rs
@@ -0,0 +1,344 @@
1//! Coercion logic. Coercions are certain type conversions that can implicitly
2//! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions
3//! like going from `&Vec<T>` to `&[T]`.
4//!
5//! See: https://doc.rust-lang.org/nomicon/coercions.html
6
7use hir_def::{lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AdtId};
8use rustc_hash::FxHashMap;
9use test_utils::tested_by;
10
11use crate::{autoderef, db::HirDatabase, ImplTy, Substs, Ty, TypeCtor, TypeWalk};
12
13use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue};
14
15impl<'a, D: HirDatabase> InferenceContext<'a, D> {
16 /// Unify two types, but may coerce the first one to the second one
17 /// using "implicit coercion rules" if needed.
18 pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
19 let from_ty = self.resolve_ty_shallow(from_ty).into_owned();
20 let to_ty = self.resolve_ty_shallow(to_ty);
21 self.coerce_inner(from_ty, &to_ty)
22 }
23
24 /// Merge two types from different branches, with possible implicit coerce.
25 ///
26 /// Note that it is only possible that one type are coerced to another.
27 /// Coercing both types to another least upper bound type is not possible in rustc,
28 /// which will simply result in "incompatible types" error.
29 pub(super) fn coerce_merge_branch<'t>(&mut self, ty1: &Ty, ty2: &Ty) -> Ty {
30 if self.coerce(ty1, ty2) {
31 ty2.clone()
32 } else if self.coerce(ty2, ty1) {
33 ty1.clone()
34 } else {
35 tested_by!(coerce_merge_fail_fallback);
36 // For incompatible types, we use the latter one as result
37 // to be better recovery for `if` without `else`.
38 ty2.clone()
39 }
40 }
41
42 pub(super) fn init_coerce_unsized_map(
43 db: &'a D,
44 resolver: &Resolver,
45 ) -> FxHashMap<(TypeCtor, TypeCtor), usize> {
46 let krate = resolver.krate().unwrap();
47 let impls = match db.lang_item(krate.into(), "coerce_unsized".into()) {
48 Some(LangItemTarget::TraitId(trait_)) => {
49 db.impls_for_trait(krate.into(), trait_.into())
50 }
51 _ => return FxHashMap::default(),
52 };
53
54 impls
55 .iter()
56 .filter_map(|&impl_id| {
57 let trait_ref = match db.impl_ty(impl_id) {
58 ImplTy::TraitRef(it) => it,
59 ImplTy::Inherent(_) => return None,
60 };
61
62 // `CoerseUnsized` has one generic parameter for the target type.
63 let cur_from_ty = trait_ref.substs.0.get(0)?;
64 let cur_to_ty = trait_ref.substs.0.get(1)?;
65
66 match (&cur_from_ty, cur_to_ty) {
67 (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => {
68 // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type.
69 // This works for smart-pointer-like coercion, which covers all impls from std.
70 st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| {
71 match (ty1, ty2) {
72 (Ty::Param { idx: p1, .. }, Ty::Param { idx: p2, .. })
73 if p1 != p2 =>
74 {
75 Some(((*ctor1, *ctor2), i))
76 }
77 _ => None,
78 }
79 })
80 }
81 _ => None,
82 }
83 })
84 .collect()
85 }
86
87 fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
88 match (&from_ty, to_ty) {
89 // Never type will make type variable to fallback to Never Type instead of Unknown.
90 (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
91 let var = self.new_maybe_never_type_var();
92 self.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
93 return true;
94 }
95 (ty_app!(TypeCtor::Never), _) => return true,
96
97 // Trivial cases, this should go after `never` check to
98 // avoid infer result type to be never
99 _ => {
100 if self.unify_inner_trivial(&from_ty, &to_ty) {
101 return true;
102 }
103 }
104 }
105
106 // Pointer weakening and function to pointer
107 match (&mut from_ty, to_ty) {
108 // `*mut T`, `&mut T, `&T`` -> `*const T`
109 // `&mut T` -> `&T`
110 // `&mut T` -> `*mut T`
111 (ty_app!(c1@TypeCtor::RawPtr(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
112 | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
113 | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::Ref(Mutability::Shared)))
114 | (ty_app!(c1@TypeCtor::Ref(Mutability::Mut)), ty_app!(c2@TypeCtor::RawPtr(_))) => {
115 *c1 = *c2;
116 }
117
118 // Illegal mutablity conversion
119 (
120 ty_app!(TypeCtor::RawPtr(Mutability::Shared)),
121 ty_app!(TypeCtor::RawPtr(Mutability::Mut)),
122 )
123 | (
124 ty_app!(TypeCtor::Ref(Mutability::Shared)),
125 ty_app!(TypeCtor::Ref(Mutability::Mut)),
126 ) => return false,
127
128 // `{function_type}` -> `fn()`
129 (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnPtr { .. })) => {
130 match from_ty.callable_sig(self.db) {
131 None => return false,
132 Some(sig) => {
133 let num_args = sig.params_and_return.len() as u16 - 1;
134 from_ty =
135 Ty::apply(TypeCtor::FnPtr { num_args }, Substs(sig.params_and_return));
136 }
137 }
138 }
139
140 _ => {}
141 }
142
143 if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) {
144 return ret;
145 }
146
147 // Auto Deref if cannot coerce
148 match (&from_ty, to_ty) {
149 // FIXME: DerefMut
150 (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => {
151 self.unify_autoderef_behind_ref(&st1[0], &st2[0])
152 }
153
154 // Otherwise, normal unify
155 _ => self.unify(&from_ty, to_ty),
156 }
157 }
158
159 /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>`
160 ///
161 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
162 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
163 let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) {
164 (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2),
165 _ => return None,
166 };
167
168 let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?;
169
170 // Check `Unsize` first
171 match self.check_unsize_and_coerce(
172 st1.0.get(coerce_generic_index)?,
173 st2.0.get(coerce_generic_index)?,
174 0,
175 ) {
176 Some(true) => {}
177 ret => return ret,
178 }
179
180 let ret = st1
181 .iter()
182 .zip(st2.iter())
183 .enumerate()
184 .filter(|&(idx, _)| idx != coerce_generic_index)
185 .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
186
187 Some(ret)
188 }
189
190 /// Check if `from_ty: Unsize<to_ty>`, and coerce to `to_ty` if it holds.
191 ///
192 /// It should not be directly called. It is only used by `try_coerce_unsized`.
193 ///
194 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html
195 fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
196 if depth > 1000 {
197 panic!("Infinite recursion in coercion");
198 }
199
200 match (&from_ty, &to_ty) {
201 // `[T; N]` -> `[T]`
202 (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
203 Some(self.unify(&st1[0], &st2[0]))
204 }
205
206 // `T` -> `dyn Trait` when `T: Trait`
207 (_, Ty::Dyn(_)) => {
208 // FIXME: Check predicates
209 Some(true)
210 }
211
212 // `(..., T)` -> `(..., U)` when `T: Unsize<U>`
213 (
214 ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1),
215 ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2),
216 ) => {
217 if len1 != len2 || *len1 == 0 {
218 return None;
219 }
220
221 match self.check_unsize_and_coerce(
222 st1.last().unwrap(),
223 st2.last().unwrap(),
224 depth + 1,
225 ) {
226 Some(true) => {}
227 ret => return ret,
228 }
229
230 let ret = st1[..st1.len() - 1]
231 .iter()
232 .zip(&st2[..st2.len() - 1])
233 .all(|(ty1, ty2)| self.unify(ty1, ty2));
234
235 Some(ret)
236 }
237
238 // Foo<..., T, ...> is Unsize<Foo<..., U, ...>> if:
239 // - T: Unsize<U>
240 // - Foo is a struct
241 // - Only the last field of Foo has a type involving T
242 // - T is not part of the type of any other fields
243 // - Bar<T>: Unsize<Bar<U>>, if the last field of Foo has type Bar<T>
244 (
245 ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1),
246 ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2),
247 ) if struct1 == struct2 => {
248 let field_tys = self.db.field_types((*struct1).into());
249 let struct_data = self.db.struct_data(*struct1);
250
251 let mut fields = struct_data.variant_data.fields().iter();
252 let (last_field_id, _data) = fields.next_back()?;
253
254 // Get the generic parameter involved in the last field.
255 let unsize_generic_index = {
256 let mut index = None;
257 let mut multiple_param = false;
258 field_tys[last_field_id].walk(&mut |ty| match ty {
259 &Ty::Param { idx, .. } => {
260 if index.is_none() {
261 index = Some(idx);
262 } else if Some(idx) != index {
263 multiple_param = true;
264 }
265 }
266 _ => {}
267 });
268
269 if multiple_param {
270 return None;
271 }
272 index?
273 };
274
275 // Check other fields do not involve it.
276 let mut multiple_used = false;
277 fields.for_each(|(field_id, _data)| {
278 field_tys[field_id].walk(&mut |ty| match ty {
279 &Ty::Param { idx, .. } if idx == unsize_generic_index => {
280 multiple_used = true
281 }
282 _ => {}
283 })
284 });
285 if multiple_used {
286 return None;
287 }
288
289 let unsize_generic_index = unsize_generic_index as usize;
290
291 // Check `Unsize` first
292 match self.check_unsize_and_coerce(
293 st1.get(unsize_generic_index)?,
294 st2.get(unsize_generic_index)?,
295 depth + 1,
296 ) {
297 Some(true) => {}
298 ret => return ret,
299 }
300
301 // Then unify other parameters
302 let ret = st1
303 .iter()
304 .zip(st2.iter())
305 .enumerate()
306 .filter(|&(idx, _)| idx != unsize_generic_index)
307 .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
308
309 Some(ret)
310 }
311
312 _ => None,
313 }
314 }
315
316 /// Unify `from_ty` to `to_ty` with optional auto Deref
317 ///
318 /// Note that the parameters are already stripped the outer reference.
319 fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
320 let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone());
321 let to_ty = self.resolve_ty_shallow(&to_ty);
322 // FIXME: Auto DerefMut
323 for derefed_ty in autoderef::autoderef(
324 self.db,
325 self.resolver.krate(),
326 InEnvironment {
327 value: canonicalized.value.clone(),
328 environment: self.trait_env.clone(),
329 },
330 ) {
331 let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value);
332 match (&*self.resolve_ty_shallow(&derefed_ty), &*to_ty) {
333 // Stop when constructor matches.
334 (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => {
335 // It will not recurse to `coerce`.
336 return self.unify_substs(st1, st2, 0);
337 }
338 _ => {}
339 }
340 }
341
342 false
343 }
344}
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
new file mode 100644
index 000000000..2f9ca4bbb
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -0,0 +1,686 @@
1//! Type inference for expressions.
2
3use std::iter::{repeat, repeat_with};
4use std::sync::Arc;
5
6use hir_def::{
7 builtin_type::Signedness,
8 expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
9 generics::GenericParams,
10 path::{GenericArg, GenericArgs},
11 resolver::resolver_for_expr,
12 AdtId, ContainerId, Lookup, StructFieldId,
13};
14use hir_expand::name::{self, Name};
15
16use crate::{
17 autoderef, db::HirDatabase, method_resolution, op, traits::InEnvironment, utils::variant_data,
18 CallableDef, InferTy, IntTy, Mutability, Obligation, ProjectionPredicate, ProjectionTy, Substs,
19 TraitRef, Ty, TypeCtor, TypeWalk, Uncertain,
20};
21
22use super::{BindingMode, Expectation, InferenceContext, InferenceDiagnostic, TypeMismatch};
23
24impl<'a, D: HirDatabase> InferenceContext<'a, D> {
25 pub(super) fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
26 let ty = self.infer_expr_inner(tgt_expr, expected);
27 let could_unify = self.unify(&ty, &expected.ty);
28 if !could_unify {
29 self.result.type_mismatches.insert(
30 tgt_expr,
31 TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() },
32 );
33 }
34 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
35 ty
36 }
37
38 /// Infer type of expression with possibly implicit coerce to the expected type.
39 /// Return the type after possible coercion.
40 fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
41 let ty = self.infer_expr_inner(expr, &expected);
42 let ty = if !self.coerce(&ty, &expected.ty) {
43 self.result
44 .type_mismatches
45 .insert(expr, TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() });
46 // Return actual type when type mismatch.
47 // This is needed for diagnostic when return type mismatch.
48 ty
49 } else if expected.ty == Ty::Unknown {
50 ty
51 } else {
52 expected.ty.clone()
53 };
54
55 self.resolve_ty_as_possible(&mut vec![], ty)
56 }
57
58 fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
59 let body = Arc::clone(&self.body); // avoid borrow checker problem
60 let ty = match &body[tgt_expr] {
61 Expr::Missing => Ty::Unknown,
62 Expr::If { condition, then_branch, else_branch } => {
63 // if let is desugared to match, so this is always simple if
64 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
65
66 let then_ty = self.infer_expr_inner(*then_branch, &expected);
67 let else_ty = match else_branch {
68 Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
69 None => Ty::unit(),
70 };
71
72 self.coerce_merge_branch(&then_ty, &else_ty)
73 }
74 Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected),
75 Expr::TryBlock { body } => {
76 let _inner = self.infer_expr(*body, expected);
77 // FIXME should be std::result::Result<{inner}, _>
78 Ty::Unknown
79 }
80 Expr::Loop { body } => {
81 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
82 // FIXME handle break with value
83 Ty::simple(TypeCtor::Never)
84 }
85 Expr::While { condition, body } => {
86 // while let is desugared to a match loop, so this is always simple while
87 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
88 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
89 Ty::unit()
90 }
91 Expr::For { iterable, body, pat } => {
92 let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
93
94 let pat_ty = match self.resolve_into_iter_item() {
95 Some(into_iter_item_alias) => {
96 let pat_ty = self.new_type_var();
97 let projection = ProjectionPredicate {
98 ty: pat_ty.clone(),
99 projection_ty: ProjectionTy {
100 associated_ty: into_iter_item_alias,
101 parameters: Substs::single(iterable_ty),
102 },
103 };
104 self.obligations.push(Obligation::Projection(projection));
105 self.resolve_ty_as_possible(&mut vec![], pat_ty)
106 }
107 None => Ty::Unknown,
108 };
109
110 self.infer_pat(*pat, &pat_ty, BindingMode::default());
111 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
112 Ty::unit()
113 }
114 Expr::Lambda { body, args, arg_types } => {
115 assert_eq!(args.len(), arg_types.len());
116
117 let mut sig_tys = Vec::new();
118
119 for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) {
120 let expected = if let Some(type_ref) = arg_type {
121 self.make_ty(type_ref)
122 } else {
123 Ty::Unknown
124 };
125 let arg_ty = self.infer_pat(*arg_pat, &expected, BindingMode::default());
126 sig_tys.push(arg_ty);
127 }
128
129 // add return type
130 let ret_ty = self.new_type_var();
131 sig_tys.push(ret_ty.clone());
132 let sig_ty = Ty::apply(
133 TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 },
134 Substs(sig_tys.into()),
135 );
136 let closure_ty = Ty::apply_one(
137 TypeCtor::Closure { def: self.owner.into(), expr: tgt_expr },
138 sig_ty,
139 );
140
141 // Eagerly try to relate the closure type with the expected
142 // type, otherwise we often won't have enough information to
143 // infer the body.
144 self.coerce(&closure_ty, &expected.ty);
145
146 self.infer_expr(*body, &Expectation::has_type(ret_ty));
147 closure_ty
148 }
149 Expr::Call { callee, args } => {
150 let callee_ty = self.infer_expr(*callee, &Expectation::none());
151 let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
152 Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
153 None => {
154 // Not callable
155 // FIXME: report an error
156 (Vec::new(), Ty::Unknown)
157 }
158 };
159 self.register_obligations_for_call(&callee_ty);
160 self.check_call_arguments(args, &param_tys);
161 let ret_ty = self.normalize_associated_types_in(ret_ty);
162 ret_ty
163 }
164 Expr::MethodCall { receiver, args, method_name, generic_args } => self
165 .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
166 Expr::Match { expr, arms } => {
167 let input_ty = self.infer_expr(*expr, &Expectation::none());
168
169 let mut result_ty = self.new_maybe_never_type_var();
170
171 for arm in arms {
172 for &pat in &arm.pats {
173 let _pat_ty = self.infer_pat(pat, &input_ty, BindingMode::default());
174 }
175 if let Some(guard_expr) = arm.guard {
176 self.infer_expr(
177 guard_expr,
178 &Expectation::has_type(Ty::simple(TypeCtor::Bool)),
179 );
180 }
181
182 let arm_ty = self.infer_expr_inner(arm.expr, &expected);
183 result_ty = self.coerce_merge_branch(&result_ty, &arm_ty);
184 }
185
186 result_ty
187 }
188 Expr::Path(p) => {
189 // FIXME this could be more efficient...
190 let resolver = resolver_for_expr(self.db, self.owner.into(), tgt_expr);
191 self.infer_path(&resolver, p, tgt_expr.into()).unwrap_or(Ty::Unknown)
192 }
193 Expr::Continue => Ty::simple(TypeCtor::Never),
194 Expr::Break { expr } => {
195 if let Some(expr) = expr {
196 // FIXME handle break with value
197 self.infer_expr(*expr, &Expectation::none());
198 }
199 Ty::simple(TypeCtor::Never)
200 }
201 Expr::Return { expr } => {
202 if let Some(expr) = expr {
203 self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
204 }
205 Ty::simple(TypeCtor::Never)
206 }
207 Expr::RecordLit { path, fields, spread } => {
208 let (ty, def_id) = self.resolve_variant(path.as_ref());
209 if let Some(variant) = def_id {
210 self.write_variant_resolution(tgt_expr.into(), variant);
211 }
212
213 self.unify(&ty, &expected.ty);
214
215 let substs = ty.substs().unwrap_or_else(Substs::empty);
216 let field_types =
217 def_id.map(|it| self.db.field_types(it.into())).unwrap_or_default();
218 let variant_data = def_id.map(|it| variant_data(self.db, it));
219 for (field_idx, field) in fields.iter().enumerate() {
220 let field_def =
221 variant_data.as_ref().and_then(|it| match it.field(&field.name) {
222 Some(local_id) => {
223 Some(StructFieldId { parent: def_id.unwrap(), local_id })
224 }
225 None => {
226 self.push_diagnostic(InferenceDiagnostic::NoSuchField {
227 expr: tgt_expr,
228 field: field_idx,
229 });
230 None
231 }
232 });
233 if let Some(field_def) = field_def {
234 self.result.record_field_resolutions.insert(field.expr, field_def);
235 }
236 let field_ty = field_def
237 .map_or(Ty::Unknown, |it| field_types[it.local_id].clone())
238 .subst(&substs);
239 self.infer_expr_coerce(field.expr, &Expectation::has_type(field_ty));
240 }
241 if let Some(expr) = spread {
242 self.infer_expr(*expr, &Expectation::has_type(ty.clone()));
243 }
244 ty
245 }
246 Expr::Field { expr, name } => {
247 let receiver_ty = self.infer_expr(*expr, &Expectation::none());
248 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
249 let ty = autoderef::autoderef(
250 self.db,
251 self.resolver.krate(),
252 InEnvironment {
253 value: canonicalized.value.clone(),
254 environment: self.trait_env.clone(),
255 },
256 )
257 .find_map(|derefed_ty| match canonicalized.decanonicalize_ty(derefed_ty.value) {
258 Ty::Apply(a_ty) => match a_ty.ctor {
259 TypeCtor::Tuple { .. } => name
260 .as_tuple_index()
261 .and_then(|idx| a_ty.parameters.0.get(idx).cloned()),
262 TypeCtor::Adt(AdtId::StructId(s)) => {
263 self.db.struct_data(s).variant_data.field(name).map(|local_id| {
264 let field = StructFieldId { parent: s.into(), local_id }.into();
265 self.write_field_resolution(tgt_expr, field);
266 self.db.field_types(s.into())[field.local_id]
267 .clone()
268 .subst(&a_ty.parameters)
269 })
270 }
271 // FIXME:
272 TypeCtor::Adt(AdtId::UnionId(_)) => None,
273 _ => None,
274 },
275 _ => None,
276 })
277 .unwrap_or(Ty::Unknown);
278 let ty = self.insert_type_vars(ty);
279 self.normalize_associated_types_in(ty)
280 }
281 Expr::Await { expr } => {
282 let inner_ty = self.infer_expr(*expr, &Expectation::none());
283 let ty = match self.resolve_future_future_output() {
284 Some(future_future_output_alias) => {
285 let ty = self.new_type_var();
286 let projection = ProjectionPredicate {
287 ty: ty.clone(),
288 projection_ty: ProjectionTy {
289 associated_ty: future_future_output_alias,
290 parameters: Substs::single(inner_ty),
291 },
292 };
293 self.obligations.push(Obligation::Projection(projection));
294 self.resolve_ty_as_possible(&mut vec![], ty)
295 }
296 None => Ty::Unknown,
297 };
298 ty
299 }
300 Expr::Try { expr } => {
301 let inner_ty = self.infer_expr(*expr, &Expectation::none());
302 let ty = match self.resolve_ops_try_ok() {
303 Some(ops_try_ok_alias) => {
304 let ty = self.new_type_var();
305 let projection = ProjectionPredicate {
306 ty: ty.clone(),
307 projection_ty: ProjectionTy {
308 associated_ty: ops_try_ok_alias,
309 parameters: Substs::single(inner_ty),
310 },
311 };
312 self.obligations.push(Obligation::Projection(projection));
313 self.resolve_ty_as_possible(&mut vec![], ty)
314 }
315 None => Ty::Unknown,
316 };
317 ty
318 }
319 Expr::Cast { expr, type_ref } => {
320 let _inner_ty = self.infer_expr(*expr, &Expectation::none());
321 let cast_ty = self.make_ty(type_ref);
322 // FIXME check the cast...
323 cast_ty
324 }
325 Expr::Ref { expr, mutability } => {
326 let expectation =
327 if let Some((exp_inner, exp_mutability)) = &expected.ty.as_reference() {
328 if *exp_mutability == Mutability::Mut && *mutability == Mutability::Shared {
329 // FIXME: throw type error - expected mut reference but found shared ref,
330 // which cannot be coerced
331 }
332 Expectation::has_type(Ty::clone(exp_inner))
333 } else {
334 Expectation::none()
335 };
336 // FIXME reference coercions etc.
337 let inner_ty = self.infer_expr(*expr, &expectation);
338 Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
339 }
340 Expr::Box { expr } => {
341 let inner_ty = self.infer_expr(*expr, &Expectation::none());
342 if let Some(box_) = self.resolve_boxed_box() {
343 Ty::apply_one(TypeCtor::Adt(box_), inner_ty)
344 } else {
345 Ty::Unknown
346 }
347 }
348 Expr::UnaryOp { expr, op } => {
349 let inner_ty = self.infer_expr(*expr, &Expectation::none());
350 match op {
351 UnaryOp::Deref => match self.resolver.krate() {
352 Some(krate) => {
353 let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty);
354 match autoderef::deref(
355 self.db,
356 krate,
357 InEnvironment {
358 value: &canonicalized.value,
359 environment: self.trait_env.clone(),
360 },
361 ) {
362 Some(derefed_ty) => {
363 canonicalized.decanonicalize_ty(derefed_ty.value)
364 }
365 None => Ty::Unknown,
366 }
367 }
368 None => Ty::Unknown,
369 },
370 UnaryOp::Neg => {
371 match &inner_ty {
372 Ty::Apply(a_ty) => match a_ty.ctor {
373 TypeCtor::Int(Uncertain::Unknown)
374 | TypeCtor::Int(Uncertain::Known(IntTy {
375 signedness: Signedness::Signed,
376 ..
377 }))
378 | TypeCtor::Float(..) => inner_ty,
379 _ => Ty::Unknown,
380 },
381 Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => {
382 inner_ty
383 }
384 // FIXME: resolve ops::Neg trait
385 _ => Ty::Unknown,
386 }
387 }
388 UnaryOp::Not => {
389 match &inner_ty {
390 Ty::Apply(a_ty) => match a_ty.ctor {
391 TypeCtor::Bool | TypeCtor::Int(_) => inner_ty,
392 _ => Ty::Unknown,
393 },
394 Ty::Infer(InferTy::IntVar(..)) => inner_ty,
395 // FIXME: resolve ops::Not trait for inner_ty
396 _ => Ty::Unknown,
397 }
398 }
399 }
400 }
401 Expr::BinaryOp { lhs, rhs, op } => match op {
402 Some(op) => {
403 let lhs_expectation = match op {
404 BinaryOp::LogicOp(..) => Expectation::has_type(Ty::simple(TypeCtor::Bool)),
405 _ => Expectation::none(),
406 };
407 let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
408 // FIXME: find implementation of trait corresponding to operation
409 // symbol and resolve associated `Output` type
410 let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty);
411 let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation));
412
413 // FIXME: similar as above, return ty is often associated trait type
414 op::binary_op_return_ty(*op, rhs_ty)
415 }
416 _ => Ty::Unknown,
417 },
418 Expr::Index { base, index } => {
419 let _base_ty = self.infer_expr(*base, &Expectation::none());
420 let _index_ty = self.infer_expr(*index, &Expectation::none());
421 // FIXME: use `std::ops::Index::Output` to figure out the real return type
422 Ty::Unknown
423 }
424 Expr::Tuple { exprs } => {
425 let mut tys = match &expected.ty {
426 ty_app!(TypeCtor::Tuple { .. }, st) => st
427 .iter()
428 .cloned()
429 .chain(repeat_with(|| self.new_type_var()))
430 .take(exprs.len())
431 .collect::<Vec<_>>(),
432 _ => (0..exprs.len()).map(|_| self.new_type_var()).collect(),
433 };
434
435 for (expr, ty) in exprs.iter().zip(tys.iter_mut()) {
436 self.infer_expr_coerce(*expr, &Expectation::has_type(ty.clone()));
437 }
438
439 Ty::apply(TypeCtor::Tuple { cardinality: tys.len() as u16 }, Substs(tys.into()))
440 }
441 Expr::Array(array) => {
442 let elem_ty = match &expected.ty {
443 ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => {
444 st.as_single().clone()
445 }
446 _ => self.new_type_var(),
447 };
448
449 match array {
450 Array::ElementList(items) => {
451 for expr in items.iter() {
452 self.infer_expr_coerce(*expr, &Expectation::has_type(elem_ty.clone()));
453 }
454 }
455 Array::Repeat { initializer, repeat } => {
456 self.infer_expr_coerce(
457 *initializer,
458 &Expectation::has_type(elem_ty.clone()),
459 );
460 self.infer_expr(
461 *repeat,
462 &Expectation::has_type(Ty::simple(TypeCtor::Int(Uncertain::Known(
463 IntTy::usize(),
464 )))),
465 );
466 }
467 }
468
469 Ty::apply_one(TypeCtor::Array, elem_ty)
470 }
471 Expr::Literal(lit) => match lit {
472 Literal::Bool(..) => Ty::simple(TypeCtor::Bool),
473 Literal::String(..) => {
474 Ty::apply_one(TypeCtor::Ref(Mutability::Shared), Ty::simple(TypeCtor::Str))
475 }
476 Literal::ByteString(..) => {
477 let byte_type = Ty::simple(TypeCtor::Int(Uncertain::Known(IntTy::u8())));
478 let slice_type = Ty::apply_one(TypeCtor::Slice, byte_type);
479 Ty::apply_one(TypeCtor::Ref(Mutability::Shared), slice_type)
480 }
481 Literal::Char(..) => Ty::simple(TypeCtor::Char),
482 Literal::Int(_v, ty) => Ty::simple(TypeCtor::Int((*ty).into())),
483 Literal::Float(_v, ty) => Ty::simple(TypeCtor::Float((*ty).into())),
484 },
485 };
486 // use a new type variable if we got Ty::Unknown here
487 let ty = self.insert_type_vars_shallow(ty);
488 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
489 self.write_expr_ty(tgt_expr, ty.clone());
490 ty
491 }
492
493 fn infer_block(
494 &mut self,
495 statements: &[Statement],
496 tail: Option<ExprId>,
497 expected: &Expectation,
498 ) -> Ty {
499 let mut diverges = false;
500 for stmt in statements {
501 match stmt {
502 Statement::Let { pat, type_ref, initializer } => {
503 let decl_ty =
504 type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown);
505
506 // Always use the declared type when specified
507 let mut ty = decl_ty.clone();
508
509 if let Some(expr) = initializer {
510 let actual_ty =
511 self.infer_expr_coerce(*expr, &Expectation::has_type(decl_ty.clone()));
512 if decl_ty == Ty::Unknown {
513 ty = actual_ty;
514 }
515 }
516
517 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
518 self.infer_pat(*pat, &ty, BindingMode::default());
519 }
520 Statement::Expr(expr) => {
521 if let ty_app!(TypeCtor::Never) = self.infer_expr(*expr, &Expectation::none()) {
522 diverges = true;
523 }
524 }
525 }
526 }
527
528 let ty = if let Some(expr) = tail {
529 self.infer_expr_coerce(expr, expected)
530 } else {
531 self.coerce(&Ty::unit(), &expected.ty);
532 Ty::unit()
533 };
534 if diverges {
535 Ty::simple(TypeCtor::Never)
536 } else {
537 ty
538 }
539 }
540
541 fn infer_method_call(
542 &mut self,
543 tgt_expr: ExprId,
544 receiver: ExprId,
545 args: &[ExprId],
546 method_name: &Name,
547 generic_args: Option<&GenericArgs>,
548 ) -> Ty {
549 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
550 let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
551 let resolved = method_resolution::lookup_method(
552 &canonicalized_receiver.value,
553 self.db,
554 method_name,
555 &self.resolver,
556 );
557 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
558 Some((ty, func)) => {
559 let ty = canonicalized_receiver.decanonicalize_ty(ty);
560 self.write_method_resolution(tgt_expr, func);
561 (ty, self.db.value_ty(func.into()), Some(self.db.generic_params(func.into())))
562 }
563 None => (receiver_ty, Ty::Unknown, None),
564 };
565 let substs = self.substs_for_method_call(def_generics, generic_args, &derefed_receiver_ty);
566 let method_ty = method_ty.apply_substs(substs);
567 let method_ty = self.insert_type_vars(method_ty);
568 self.register_obligations_for_call(&method_ty);
569 let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
570 Some(sig) => {
571 if !sig.params().is_empty() {
572 (sig.params()[0].clone(), sig.params()[1..].to_vec(), sig.ret().clone())
573 } else {
574 (Ty::Unknown, Vec::new(), sig.ret().clone())
575 }
576 }
577 None => (Ty::Unknown, Vec::new(), Ty::Unknown),
578 };
579 // Apply autoref so the below unification works correctly
580 // FIXME: return correct autorefs from lookup_method
581 let actual_receiver_ty = match expected_receiver_ty.as_reference() {
582 Some((_, mutability)) => Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty),
583 _ => derefed_receiver_ty,
584 };
585 self.unify(&expected_receiver_ty, &actual_receiver_ty);
586
587 self.check_call_arguments(args, &param_tys);
588 let ret_ty = self.normalize_associated_types_in(ret_ty);
589 ret_ty
590 }
591
592 fn check_call_arguments(&mut self, args: &[ExprId], param_tys: &[Ty]) {
593 // Quoting https://github.com/rust-lang/rust/blob/6ef275e6c3cb1384ec78128eceeb4963ff788dca/src/librustc_typeck/check/mod.rs#L3325 --
594 // We do this in a pretty awful way: first we type-check any arguments
595 // that are not closures, then we type-check the closures. This is so
596 // that we have more information about the types of arguments when we
597 // type-check the functions. This isn't really the right way to do this.
598 for &check_closures in &[false, true] {
599 let param_iter = param_tys.iter().cloned().chain(repeat(Ty::Unknown));
600 for (&arg, param_ty) in args.iter().zip(param_iter) {
601 let is_closure = match &self.body[arg] {
602 Expr::Lambda { .. } => true,
603 _ => false,
604 };
605
606 if is_closure != check_closures {
607 continue;
608 }
609
610 let param_ty = self.normalize_associated_types_in(param_ty);
611 self.infer_expr_coerce(arg, &Expectation::has_type(param_ty.clone()));
612 }
613 }
614 }
615
616 fn substs_for_method_call(
617 &mut self,
618 def_generics: Option<Arc<GenericParams>>,
619 generic_args: Option<&GenericArgs>,
620 receiver_ty: &Ty,
621 ) -> Substs {
622 let (parent_param_count, param_count) =
623 def_generics.as_ref().map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
624 let mut substs = Vec::with_capacity(parent_param_count + param_count);
625 // Parent arguments are unknown, except for the receiver type
626 if let Some(parent_generics) = def_generics.and_then(|p| p.parent_params.clone()) {
627 for param in &parent_generics.params {
628 if param.name == name::SELF_TYPE {
629 substs.push(receiver_ty.clone());
630 } else {
631 substs.push(Ty::Unknown);
632 }
633 }
634 }
635 // handle provided type arguments
636 if let Some(generic_args) = generic_args {
637 // if args are provided, it should be all of them, but we can't rely on that
638 for arg in generic_args.args.iter().take(param_count) {
639 match arg {
640 GenericArg::Type(type_ref) => {
641 let ty = self.make_ty(type_ref);
642 substs.push(ty);
643 }
644 }
645 }
646 };
647 let supplied_params = substs.len();
648 for _ in supplied_params..parent_param_count + param_count {
649 substs.push(Ty::Unknown);
650 }
651 assert_eq!(substs.len(), parent_param_count + param_count);
652 Substs(substs.into())
653 }
654
655 fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
656 if let Ty::Apply(a_ty) = callable_ty {
657 if let TypeCtor::FnDef(def) = a_ty.ctor {
658 let generic_predicates = self.db.generic_predicates(def.into());
659 for predicate in generic_predicates.iter() {
660 let predicate = predicate.clone().subst(&a_ty.parameters);
661 if let Some(obligation) = Obligation::from_predicate(predicate) {
662 self.obligations.push(obligation);
663 }
664 }
665 // add obligation for trait implementation, if this is a trait method
666 match def {
667 CallableDef::FunctionId(f) => {
668 if let ContainerId::TraitId(trait_) = f.lookup(self.db).container {
669 // construct a TraitDef
670 let substs = a_ty.parameters.prefix(
671 self.db
672 .generic_params(trait_.into())
673 .count_params_including_parent(),
674 );
675 self.obligations.push(Obligation::Trait(TraitRef {
676 trait_: trait_.into(),
677 substs,
678 }));
679 }
680 }
681 CallableDef::StructId(_) | CallableDef::EnumVariantId(_) => {}
682 }
683 }
684 }
685 }
686}
diff --git a/crates/ra_hir_ty/src/infer/pat.rs b/crates/ra_hir_ty/src/infer/pat.rs
new file mode 100644
index 000000000..1ebb36239
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/pat.rs
@@ -0,0 +1,186 @@
1//! Type inference for patterns.
2
3use std::iter::repeat;
4use std::sync::Arc;
5
6use hir_def::{
7 expr::{BindingAnnotation, Pat, PatId, RecordFieldPat},
8 path::Path,
9 type_ref::Mutability,
10};
11use hir_expand::name::Name;
12use test_utils::tested_by;
13
14use super::{BindingMode, InferenceContext};
15use crate::{db::HirDatabase, utils::variant_data, Substs, Ty, TypeCtor, TypeWalk};
16
17impl<'a, D: HirDatabase> InferenceContext<'a, D> {
18 fn infer_tuple_struct_pat(
19 &mut self,
20 path: Option<&Path>,
21 subpats: &[PatId],
22 expected: &Ty,
23 default_bm: BindingMode,
24 ) -> Ty {
25 let (ty, def) = self.resolve_variant(path);
26 let var_data = def.map(|it| variant_data(self.db, it));
27 self.unify(&ty, expected);
28
29 let substs = ty.substs().unwrap_or_else(Substs::empty);
30
31 let field_tys = def.map(|it| self.db.field_types(it.into())).unwrap_or_default();
32
33 for (i, &subpat) in subpats.iter().enumerate() {
34 let expected_ty = var_data
35 .as_ref()
36 .and_then(|d| d.field(&Name::new_tuple_field(i)))
37 .map_or(Ty::Unknown, |field| field_tys[field].clone())
38 .subst(&substs);
39 let expected_ty = self.normalize_associated_types_in(expected_ty);
40 self.infer_pat(subpat, &expected_ty, default_bm);
41 }
42
43 ty
44 }
45
46 fn infer_record_pat(
47 &mut self,
48 path: Option<&Path>,
49 subpats: &[RecordFieldPat],
50 expected: &Ty,
51 default_bm: BindingMode,
52 id: PatId,
53 ) -> Ty {
54 let (ty, def) = self.resolve_variant(path);
55 let var_data = def.map(|it| variant_data(self.db, it));
56 if let Some(variant) = def {
57 self.write_variant_resolution(id.into(), variant);
58 }
59
60 self.unify(&ty, expected);
61
62 let substs = ty.substs().unwrap_or_else(Substs::empty);
63
64 let field_tys = def.map(|it| self.db.field_types(it.into())).unwrap_or_default();
65 for subpat in subpats {
66 let matching_field = var_data.as_ref().and_then(|it| it.field(&subpat.name));
67 let expected_ty =
68 matching_field.map_or(Ty::Unknown, |field| field_tys[field].clone()).subst(&substs);
69 let expected_ty = self.normalize_associated_types_in(expected_ty);
70 self.infer_pat(subpat.pat, &expected_ty, default_bm);
71 }
72
73 ty
74 }
75
76 pub(super) fn infer_pat(
77 &mut self,
78 pat: PatId,
79 mut expected: &Ty,
80 mut default_bm: BindingMode,
81 ) -> Ty {
82 let body = Arc::clone(&self.body); // avoid borrow checker problem
83
84 let is_non_ref_pat = match &body[pat] {
85 Pat::Tuple(..)
86 | Pat::TupleStruct { .. }
87 | Pat::Record { .. }
88 | Pat::Range { .. }
89 | Pat::Slice { .. } => true,
90 // FIXME: Path/Lit might actually evaluate to ref, but inference is unimplemented.
91 Pat::Path(..) | Pat::Lit(..) => true,
92 Pat::Wild | Pat::Bind { .. } | Pat::Ref { .. } | Pat::Missing => false,
93 };
94 if is_non_ref_pat {
95 while let Some((inner, mutability)) = expected.as_reference() {
96 expected = inner;
97 default_bm = match default_bm {
98 BindingMode::Move => BindingMode::Ref(mutability),
99 BindingMode::Ref(Mutability::Shared) => BindingMode::Ref(Mutability::Shared),
100 BindingMode::Ref(Mutability::Mut) => BindingMode::Ref(mutability),
101 }
102 }
103 } else if let Pat::Ref { .. } = &body[pat] {
104 tested_by!(match_ergonomics_ref);
105 // When you encounter a `&pat` pattern, reset to Move.
106 // This is so that `w` is by value: `let (_, &w) = &(1, &2);`
107 default_bm = BindingMode::Move;
108 }
109
110 // Lose mutability.
111 let default_bm = default_bm;
112 let expected = expected;
113
114 let ty = match &body[pat] {
115 Pat::Tuple(ref args) => {
116 let expectations = match expected.as_tuple() {
117 Some(parameters) => &*parameters.0,
118 _ => &[],
119 };
120 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
121
122 let inner_tys = args
123 .iter()
124 .zip(expectations_iter)
125 .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
126 .collect();
127
128 Ty::apply(TypeCtor::Tuple { cardinality: args.len() as u16 }, Substs(inner_tys))
129 }
130 Pat::Ref { pat, mutability } => {
131 let expectation = match expected.as_reference() {
132 Some((inner_ty, exp_mut)) => {
133 if *mutability != exp_mut {
134 // FIXME: emit type error?
135 }
136 inner_ty
137 }
138 _ => &Ty::Unknown,
139 };
140 let subty = self.infer_pat(*pat, expectation, default_bm);
141 Ty::apply_one(TypeCtor::Ref(*mutability), subty)
142 }
143 Pat::TupleStruct { path: p, args: subpats } => {
144 self.infer_tuple_struct_pat(p.as_ref(), subpats, expected, default_bm)
145 }
146 Pat::Record { path: p, args: fields } => {
147 self.infer_record_pat(p.as_ref(), fields, expected, default_bm, pat)
148 }
149 Pat::Path(path) => {
150 // FIXME use correct resolver for the surrounding expression
151 let resolver = self.resolver.clone();
152 self.infer_path(&resolver, &path, pat.into()).unwrap_or(Ty::Unknown)
153 }
154 Pat::Bind { mode, name: _, subpat } => {
155 let mode = if mode == &BindingAnnotation::Unannotated {
156 default_bm
157 } else {
158 BindingMode::convert(*mode)
159 };
160 let inner_ty = if let Some(subpat) = subpat {
161 self.infer_pat(*subpat, expected, default_bm)
162 } else {
163 expected.clone()
164 };
165 let inner_ty = self.insert_type_vars_shallow(inner_ty);
166
167 let bound_ty = match mode {
168 BindingMode::Ref(mutability) => {
169 Ty::apply_one(TypeCtor::Ref(mutability), inner_ty.clone())
170 }
171 BindingMode::Move => inner_ty.clone(),
172 };
173 let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty);
174 self.write_pat_ty(pat, bound_ty);
175 return inner_ty;
176 }
177 _ => Ty::Unknown,
178 };
179 // use a new type variable if we got Ty::Unknown here
180 let ty = self.insert_type_vars_shallow(ty);
181 self.unify(&ty, expected);
182 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
183 self.write_pat_ty(pat, ty.clone());
184 ty
185 }
186}
diff --git a/crates/ra_hir_ty/src/infer/path.rs b/crates/ra_hir_ty/src/infer/path.rs
new file mode 100644
index 000000000..14be66836
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/path.rs
@@ -0,0 +1,268 @@
1//! Path expression resolution.
2
3use hir_def::{
4 path::{Path, PathKind, PathSegment},
5 resolver::{ResolveValueResult, Resolver, TypeNs, ValueNs},
6 AssocItemId, ContainerId, Lookup,
7};
8use hir_expand::name::Name;
9
10use crate::{db::HirDatabase, method_resolution, Substs, Ty, TypeWalk, ValueTyDefId};
11
12use super::{ExprOrPatId, InferenceContext, TraitRef};
13
14impl<'a, D: HirDatabase> InferenceContext<'a, D> {
15 pub(super) fn infer_path(
16 &mut self,
17 resolver: &Resolver,
18 path: &Path,
19 id: ExprOrPatId,
20 ) -> Option<Ty> {
21 let ty = self.resolve_value_path(resolver, path, id)?;
22 let ty = self.insert_type_vars(ty);
23 let ty = self.normalize_associated_types_in(ty);
24 Some(ty)
25 }
26
27 fn resolve_value_path(
28 &mut self,
29 resolver: &Resolver,
30 path: &Path,
31 id: ExprOrPatId,
32 ) -> Option<Ty> {
33 let (value, self_subst) = if let PathKind::Type(type_ref) = &path.kind {
34 if path.segments.is_empty() {
35 // This can't actually happen syntax-wise
36 return None;
37 }
38 let ty = self.make_ty(type_ref);
39 let remaining_segments_for_ty = &path.segments[..path.segments.len() - 1];
40 let ty = Ty::from_type_relative_path(self.db, resolver, ty, remaining_segments_for_ty);
41 self.resolve_ty_assoc_item(
42 ty,
43 &path.segments.last().expect("path had at least one segment").name,
44 id,
45 )?
46 } else {
47 let value_or_partial = resolver.resolve_path_in_value_ns(self.db, &path)?;
48
49 match value_or_partial {
50 ResolveValueResult::ValueNs(it) => (it, None),
51 ResolveValueResult::Partial(def, remaining_index) => {
52 self.resolve_assoc_item(def, path, remaining_index, id)?
53 }
54 }
55 };
56
57 let typable: ValueTyDefId = match value {
58 ValueNs::LocalBinding(pat) => {
59 let ty = self.result.type_of_pat.get(pat)?.clone();
60 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
61 return Some(ty);
62 }
63 ValueNs::FunctionId(it) => it.into(),
64 ValueNs::ConstId(it) => it.into(),
65 ValueNs::StaticId(it) => it.into(),
66 ValueNs::StructId(it) => it.into(),
67 ValueNs::EnumVariantId(it) => it.into(),
68 };
69
70 let mut ty = self.db.value_ty(typable);
71 if let Some(self_subst) = self_subst {
72 ty = ty.subst(&self_subst);
73 }
74 let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable);
75 let ty = ty.subst(&substs);
76 Some(ty)
77 }
78
79 fn resolve_assoc_item(
80 &mut self,
81 def: TypeNs,
82 path: &Path,
83 remaining_index: usize,
84 id: ExprOrPatId,
85 ) -> Option<(ValueNs, Option<Substs>)> {
86 assert!(remaining_index < path.segments.len());
87 // there may be more intermediate segments between the resolved one and
88 // the end. Only the last segment needs to be resolved to a value; from
89 // the segments before that, we need to get either a type or a trait ref.
90
91 let resolved_segment = &path.segments[remaining_index - 1];
92 let remaining_segments = &path.segments[remaining_index..];
93 let is_before_last = remaining_segments.len() == 1;
94
95 match (def, is_before_last) {
96 (TypeNs::TraitId(trait_), true) => {
97 let segment =
98 remaining_segments.last().expect("there should be at least one segment here");
99 let trait_ref = TraitRef::from_resolved_path(
100 self.db,
101 &self.resolver,
102 trait_.into(),
103 resolved_segment,
104 None,
105 );
106 self.resolve_trait_assoc_item(trait_ref, segment, id)
107 }
108 (def, _) => {
109 // Either we already have a type (e.g. `Vec::new`), or we have a
110 // trait but it's not the last segment, so the next segment
111 // should resolve to an associated type of that trait (e.g. `<T
112 // as Iterator>::Item::default`)
113 let remaining_segments_for_ty = &remaining_segments[..remaining_segments.len() - 1];
114 let ty = Ty::from_partly_resolved_hir_path(
115 self.db,
116 &self.resolver,
117 def,
118 resolved_segment,
119 remaining_segments_for_ty,
120 );
121 if let Ty::Unknown = ty {
122 return None;
123 }
124
125 let ty = self.insert_type_vars(ty);
126 let ty = self.normalize_associated_types_in(ty);
127
128 let segment =
129 remaining_segments.last().expect("there should be at least one segment here");
130
131 self.resolve_ty_assoc_item(ty, &segment.name, id)
132 }
133 }
134 }
135
136 fn resolve_trait_assoc_item(
137 &mut self,
138 trait_ref: TraitRef,
139 segment: &PathSegment,
140 id: ExprOrPatId,
141 ) -> Option<(ValueNs, Option<Substs>)> {
142 let trait_ = trait_ref.trait_;
143 let item = self
144 .db
145 .trait_data(trait_)
146 .items
147 .iter()
148 .map(|(_name, id)| (*id).into())
149 .find_map(|item| match item {
150 AssocItemId::FunctionId(func) => {
151 if segment.name == self.db.function_data(func).name {
152 Some(AssocItemId::FunctionId(func))
153 } else {
154 None
155 }
156 }
157
158 AssocItemId::ConstId(konst) => {
159 if self.db.const_data(konst).name.as_ref().map_or(false, |n| n == &segment.name)
160 {
161 Some(AssocItemId::ConstId(konst))
162 } else {
163 None
164 }
165 }
166 AssocItemId::TypeAliasId(_) => None,
167 })?;
168 let def = match item {
169 AssocItemId::FunctionId(f) => ValueNs::FunctionId(f),
170 AssocItemId::ConstId(c) => ValueNs::ConstId(c),
171 AssocItemId::TypeAliasId(_) => unreachable!(),
172 };
173 let substs = Substs::build_for_def(self.db, item)
174 .use_parent_substs(&trait_ref.substs)
175 .fill_with_params()
176 .build();
177
178 self.write_assoc_resolution(id, item);
179 Some((def, Some(substs)))
180 }
181
182 fn resolve_ty_assoc_item(
183 &mut self,
184 ty: Ty,
185 name: &Name,
186 id: ExprOrPatId,
187 ) -> Option<(ValueNs, Option<Substs>)> {
188 if let Ty::Unknown = ty {
189 return None;
190 }
191
192 let canonical_ty = self.canonicalizer().canonicalize_ty(ty.clone());
193
194 method_resolution::iterate_method_candidates(
195 &canonical_ty.value,
196 self.db,
197 &self.resolver.clone(),
198 Some(name),
199 method_resolution::LookupMode::Path,
200 move |_ty, item| {
201 let (def, container) = match item {
202 AssocItemId::FunctionId(f) => {
203 (ValueNs::FunctionId(f), f.lookup(self.db).container)
204 }
205 AssocItemId::ConstId(c) => (ValueNs::ConstId(c), c.lookup(self.db).container),
206 AssocItemId::TypeAliasId(_) => unreachable!(),
207 };
208 let substs = match container {
209 ContainerId::ImplId(_) => self.find_self_types(&def, ty.clone()),
210 ContainerId::TraitId(trait_) => {
211 // we're picking this method
212 let trait_substs = Substs::build_for_def(self.db, trait_)
213 .push(ty.clone())
214 .fill(std::iter::repeat_with(|| self.new_type_var()))
215 .build();
216 let substs = Substs::build_for_def(self.db, item)
217 .use_parent_substs(&trait_substs)
218 .fill_with_params()
219 .build();
220 self.obligations.push(super::Obligation::Trait(TraitRef {
221 trait_,
222 substs: trait_substs,
223 }));
224 Some(substs)
225 }
226 ContainerId::ModuleId(_) => None,
227 };
228
229 self.write_assoc_resolution(id, item.into());
230 Some((def, substs))
231 },
232 )
233 }
234
235 fn find_self_types(&self, def: &ValueNs, actual_def_ty: Ty) -> Option<Substs> {
236 if let ValueNs::FunctionId(func) = *def {
237 // We only do the infer if parent has generic params
238 let gen = self.db.generic_params(func.into());
239 if gen.count_parent_params() == 0 {
240 return None;
241 }
242
243 let impl_id = match func.lookup(self.db).container {
244 ContainerId::ImplId(it) => it,
245 _ => return None,
246 };
247 let self_ty = self.db.impl_ty(impl_id).self_type().clone();
248 let self_ty_substs = self_ty.substs()?;
249 let actual_substs = actual_def_ty.substs()?;
250
251 let mut new_substs = vec![Ty::Unknown; gen.count_parent_params()];
252
253 // The following code *link up* the function actual parma type
254 // and impl_block type param index
255 self_ty_substs.iter().zip(actual_substs.iter()).for_each(|(param, pty)| {
256 if let Ty::Param { idx, .. } = param {
257 if let Some(s) = new_substs.get_mut(*idx as usize) {
258 *s = pty.clone();
259 }
260 }
261 });
262
263 Some(Substs(new_substs.into()))
264 } else {
265 None
266 }
267 }
268}
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
new file mode 100644
index 000000000..f3a875678
--- /dev/null
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -0,0 +1,162 @@
1//! Unification and canonicalization logic.
2
3use super::{InferenceContext, Obligation};
4use crate::{
5 db::HirDatabase, utils::make_mut_slice, Canonical, InEnvironment, InferTy, ProjectionPredicate,
6 ProjectionTy, Substs, TraitRef, Ty, TypeWalk,
7};
8
9impl<'a, D: HirDatabase> InferenceContext<'a, D> {
10 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
11 where
12 'a: 'b,
13 {
14 Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
15 }
16}
17
18pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
19where
20 'a: 'b,
21{
22 ctx: &'b mut InferenceContext<'a, D>,
23 free_vars: Vec<InferTy>,
24 /// A stack of type variables that is used to detect recursive types (which
25 /// are an error, but we need to protect against them to avoid stack
26 /// overflows).
27 var_stack: Vec<super::TypeVarId>,
28}
29
30pub(super) struct Canonicalized<T> {
31 pub value: Canonical<T>,
32 free_vars: Vec<InferTy>,
33}
34
35impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
36where
37 'a: 'b,
38{
39 fn add(&mut self, free_var: InferTy) -> usize {
40 self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
41 let next_index = self.free_vars.len();
42 self.free_vars.push(free_var);
43 next_index
44 })
45 }
46
47 fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty {
48 ty.fold(&mut |ty| match ty {
49 Ty::Infer(tv) => {
50 let inner = tv.to_inner();
51 if self.var_stack.contains(&inner) {
52 // recursive type
53 return tv.fallback_value();
54 }
55 if let Some(known_ty) =
56 self.ctx.var_unification_table.inlined_probe_value(inner).known()
57 {
58 self.var_stack.push(inner);
59 let result = self.do_canonicalize_ty(known_ty.clone());
60 self.var_stack.pop();
61 result
62 } else {
63 let root = self.ctx.var_unification_table.find(inner);
64 let free_var = match tv {
65 InferTy::TypeVar(_) => InferTy::TypeVar(root),
66 InferTy::IntVar(_) => InferTy::IntVar(root),
67 InferTy::FloatVar(_) => InferTy::FloatVar(root),
68 InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root),
69 };
70 let position = self.add(free_var);
71 Ty::Bound(position as u32)
72 }
73 }
74 _ => ty,
75 })
76 }
77
78 fn do_canonicalize_trait_ref(&mut self, mut trait_ref: TraitRef) -> TraitRef {
79 for ty in make_mut_slice(&mut trait_ref.substs.0) {
80 *ty = self.do_canonicalize_ty(ty.clone());
81 }
82 trait_ref
83 }
84
85 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
86 Canonicalized {
87 value: Canonical { value: result, num_vars: self.free_vars.len() },
88 free_vars: self.free_vars,
89 }
90 }
91
92 fn do_canonicalize_projection_ty(&mut self, mut projection_ty: ProjectionTy) -> ProjectionTy {
93 for ty in make_mut_slice(&mut projection_ty.parameters.0) {
94 *ty = self.do_canonicalize_ty(ty.clone());
95 }
96 projection_ty
97 }
98
99 fn do_canonicalize_projection_predicate(
100 &mut self,
101 projection: ProjectionPredicate,
102 ) -> ProjectionPredicate {
103 let ty = self.do_canonicalize_ty(projection.ty);
104 let projection_ty = self.do_canonicalize_projection_ty(projection.projection_ty);
105
106 ProjectionPredicate { ty, projection_ty }
107 }
108
109 // FIXME: add some point, we need to introduce a `Fold` trait that abstracts
110 // over all the things that can be canonicalized (like Chalk and rustc have)
111
112 pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
113 let result = self.do_canonicalize_ty(ty);
114 self.into_canonicalized(result)
115 }
116
117 pub(crate) fn canonicalize_obligation(
118 mut self,
119 obligation: InEnvironment<Obligation>,
120 ) -> Canonicalized<InEnvironment<Obligation>> {
121 let result = match obligation.value {
122 Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize_trait_ref(tr)),
123 Obligation::Projection(pr) => {
124 Obligation::Projection(self.do_canonicalize_projection_predicate(pr))
125 }
126 };
127 self.into_canonicalized(InEnvironment {
128 value: result,
129 environment: obligation.environment,
130 })
131 }
132}
133
134impl<T> Canonicalized<T> {
135 pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
136 ty.walk_mut_binders(
137 &mut |ty, binders| match ty {
138 &mut Ty::Bound(idx) => {
139 if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() {
140 *ty = Ty::Infer(self.free_vars[idx as usize - binders]);
141 }
142 }
143 _ => {}
144 },
145 0,
146 );
147 ty
148 }
149
150 pub fn apply_solution(
151 &self,
152 ctx: &mut InferenceContext<'_, impl HirDatabase>,
153 solution: Canonical<Vec<Ty>>,
154 ) {
155 // the solution may contain new variables, which we need to convert to new inference vars
156 let new_vars = Substs((0..solution.num_vars).map(|_| ctx.new_type_var()).collect());
157 for (i, ty) in solution.value.into_iter().enumerate() {
158 let var = self.free_vars[i];
159 ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
160 }
161 }
162}