aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src/infer
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2020-08-13 15:35:29 +0100
committerAleksey Kladov <[email protected]>2020-08-13 15:35:29 +0100
commit6a77ec7bbe6ddbf663dce9529d11d1bb56c5489a (patch)
treeb6e3d7e0109eb82bca75b5ebc35a7d723542b8dd /crates/hir_ty/src/infer
parent50f8c1ebf23f634b68529603a917e3feeda457fa (diff)
Rename ra_hir_ty -> hir_ty
Diffstat (limited to 'crates/hir_ty/src/infer')
-rw-r--r--crates/hir_ty/src/infer/coerce.rs197
-rw-r--r--crates/hir_ty/src/infer/expr.rs873
-rw-r--r--crates/hir_ty/src/infer/pat.rs241
-rw-r--r--crates/hir_ty/src/infer/path.rs287
-rw-r--r--crates/hir_ty/src/infer/unify.rs474
5 files changed, 2072 insertions, 0 deletions
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
new file mode 100644
index 000000000..32c7c57cd
--- /dev/null
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -0,0 +1,197 @@
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, type_ref::Mutability};
8use test_utils::mark;
9
10use crate::{autoderef, traits::Solution, Obligation, Substs, TraitRef, Ty, TypeCtor};
11
12use super::{unify::TypeVarValue, InEnvironment, InferTy, InferenceContext};
13
14impl<'a> InferenceContext<'a> {
15 /// Unify two types, but may coerce the first one to the second one
16 /// using "implicit coercion rules" if needed.
17 pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
18 let from_ty = self.resolve_ty_shallow(from_ty).into_owned();
19 let to_ty = self.resolve_ty_shallow(to_ty);
20 self.coerce_inner(from_ty, &to_ty)
21 }
22
23 /// Merge two types from different branches, with possible coercion.
24 ///
25 /// Mostly this means trying to coerce one to the other, but
26 /// - if we have two function types for different functions, we need to
27 /// coerce both to function pointers;
28 /// - if we were concerned with lifetime subtyping, we'd need to look for a
29 /// least upper bound.
30 pub(super) fn coerce_merge_branch(&mut self, ty1: &Ty, ty2: &Ty) -> Ty {
31 if self.coerce(ty1, ty2) {
32 ty2.clone()
33 } else if self.coerce(ty2, ty1) {
34 ty1.clone()
35 } else {
36 if let (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnDef(_))) = (ty1, ty2) {
37 mark::hit!(coerce_fn_reification);
38 // Special case: two function types. Try to coerce both to
39 // pointers to have a chance at getting a match. See
40 // https://github.com/rust-lang/rust/blob/7b805396bf46dce972692a6846ce2ad8481c5f85/src/librustc_typeck/check/coercion.rs#L877-L916
41 let sig1 = ty1.callable_sig(self.db).expect("FnDef without callable sig");
42 let sig2 = ty2.callable_sig(self.db).expect("FnDef without callable sig");
43 let ptr_ty1 = Ty::fn_ptr(sig1);
44 let ptr_ty2 = Ty::fn_ptr(sig2);
45 self.coerce_merge_branch(&ptr_ty1, &ptr_ty2)
46 } else {
47 mark::hit!(coerce_merge_fail_fallback);
48 ty1.clone()
49 }
50 }
51 }
52
53 fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
54 match (&from_ty, to_ty) {
55 // Never type will make type variable to fallback to Never Type instead of Unknown.
56 (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
57 let var = self.table.new_maybe_never_type_var();
58 self.table.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
59 return true;
60 }
61 (ty_app!(TypeCtor::Never), _) => return true,
62
63 // Trivial cases, this should go after `never` check to
64 // avoid infer result type to be never
65 _ => {
66 if self.table.unify_inner_trivial(&from_ty, &to_ty, 0) {
67 return true;
68 }
69 }
70 }
71
72 // Pointer weakening and function to pointer
73 match (&mut from_ty, to_ty) {
74 // `*mut T`, `&mut T, `&T`` -> `*const T`
75 // `&mut T` -> `&T`
76 // `&mut T` -> `*mut T`
77 (ty_app!(c1@TypeCtor::RawPtr(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
78 | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
79 | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::Ref(Mutability::Shared)))
80 | (ty_app!(c1@TypeCtor::Ref(Mutability::Mut)), ty_app!(c2@TypeCtor::RawPtr(_))) => {
81 *c1 = *c2;
82 }
83
84 // Illegal mutablity conversion
85 (
86 ty_app!(TypeCtor::RawPtr(Mutability::Shared)),
87 ty_app!(TypeCtor::RawPtr(Mutability::Mut)),
88 )
89 | (
90 ty_app!(TypeCtor::Ref(Mutability::Shared)),
91 ty_app!(TypeCtor::Ref(Mutability::Mut)),
92 ) => return false,
93
94 // `{function_type}` -> `fn()`
95 (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnPtr { .. })) => {
96 match from_ty.callable_sig(self.db) {
97 None => return false,
98 Some(sig) => {
99 from_ty = Ty::fn_ptr(sig);
100 }
101 }
102 }
103
104 (ty_app!(TypeCtor::Closure { .. }, params), ty_app!(TypeCtor::FnPtr { .. })) => {
105 from_ty = params[0].clone();
106 }
107
108 _ => {}
109 }
110
111 if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) {
112 return ret;
113 }
114
115 // Auto Deref if cannot coerce
116 match (&from_ty, to_ty) {
117 // FIXME: DerefMut
118 (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => {
119 self.unify_autoderef_behind_ref(&st1[0], &st2[0])
120 }
121
122 // Otherwise, normal unify
123 _ => self.unify(&from_ty, to_ty),
124 }
125 }
126
127 /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>`
128 ///
129 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
130 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
131 let krate = self.resolver.krate().unwrap();
132 let coerce_unsized_trait = match self.db.lang_item(krate, "coerce_unsized".into()) {
133 Some(LangItemTarget::TraitId(trait_)) => trait_,
134 _ => return None,
135 };
136
137 let generic_params = crate::utils::generics(self.db.upcast(), coerce_unsized_trait.into());
138 if generic_params.len() != 2 {
139 // The CoerceUnsized trait should have two generic params: Self and T.
140 return None;
141 }
142
143 let substs = Substs::build_for_generics(&generic_params)
144 .push(from_ty.clone())
145 .push(to_ty.clone())
146 .build();
147 let trait_ref = TraitRef { trait_: coerce_unsized_trait, substs };
148 let goal = InEnvironment::new(self.trait_env.clone(), Obligation::Trait(trait_ref));
149
150 let canonicalizer = self.canonicalizer();
151 let canonicalized = canonicalizer.canonicalize_obligation(goal);
152
153 let solution = self.db.trait_solve(krate, canonicalized.value.clone())?;
154
155 match solution {
156 Solution::Unique(v) => {
157 canonicalized.apply_solution(self, v.0);
158 }
159 _ => return None,
160 };
161
162 Some(true)
163 }
164
165 /// Unify `from_ty` to `to_ty` with optional auto Deref
166 ///
167 /// Note that the parameters are already stripped the outer reference.
168 fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
169 let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone());
170 let to_ty = self.resolve_ty_shallow(&to_ty);
171 // FIXME: Auto DerefMut
172 for derefed_ty in autoderef::autoderef(
173 self.db,
174 self.resolver.krate(),
175 InEnvironment {
176 value: canonicalized.value.clone(),
177 environment: self.trait_env.clone(),
178 },
179 ) {
180 let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value);
181 match (&*self.resolve_ty_shallow(&derefed_ty), &*to_ty) {
182 // Stop when constructor matches.
183 (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => {
184 // It will not recurse to `coerce`.
185 return self.table.unify_substs(st1, st2, 0);
186 }
187 _ => {
188 if self.table.unify_inner_trivial(&derefed_ty, &to_ty, 0) {
189 return true;
190 }
191 }
192 }
193 }
194
195 false
196 }
197}
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
new file mode 100644
index 000000000..a2f849d02
--- /dev/null
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -0,0 +1,873 @@
1//! Type inference for expressions.
2
3use std::iter::{repeat, repeat_with};
4use std::{mem, sync::Arc};
5
6use hir_def::{
7 builtin_type::Signedness,
8 expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
9 path::{GenericArg, GenericArgs},
10 resolver::resolver_for_expr,
11 AdtId, AssocContainerId, FieldId, Lookup,
12};
13use hir_expand::name::{name, Name};
14use syntax::ast::RangeOp;
15
16use crate::{
17 autoderef, method_resolution, op,
18 traits::{FnTrait, InEnvironment},
19 utils::{generics, variant_data, Generics},
20 ApplicationTy, Binders, CallableDefId, InferTy, IntTy, Mutability, Obligation, Rawness, Substs,
21 TraitRef, Ty, TypeCtor,
22};
23
24use super::{
25 find_breakable, BindingMode, BreakableContext, Diverges, Expectation, InferenceContext,
26 InferenceDiagnostic, TypeMismatch,
27};
28
29impl<'a> InferenceContext<'a> {
30 pub(super) fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
31 let ty = self.infer_expr_inner(tgt_expr, expected);
32 if ty.is_never() {
33 // Any expression that produces a value of type `!` must have diverged
34 self.diverges = Diverges::Always;
35 }
36 let could_unify = self.unify(&ty, &expected.ty);
37 if !could_unify {
38 self.result.type_mismatches.insert(
39 tgt_expr,
40 TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() },
41 );
42 }
43 self.resolve_ty_as_possible(ty)
44 }
45
46 /// Infer type of expression with possibly implicit coerce to the expected type.
47 /// Return the type after possible coercion.
48 pub(super) fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
49 let ty = self.infer_expr_inner(expr, &expected);
50 let ty = if !self.coerce(&ty, &expected.coercion_target()) {
51 self.result
52 .type_mismatches
53 .insert(expr, TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() });
54 // Return actual type when type mismatch.
55 // This is needed for diagnostic when return type mismatch.
56 ty
57 } else if expected.coercion_target() == &Ty::Unknown {
58 ty
59 } else {
60 expected.ty.clone()
61 };
62
63 self.resolve_ty_as_possible(ty)
64 }
65
66 fn callable_sig_from_fn_trait(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
67 let krate = self.resolver.krate()?;
68 let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?;
69 let output_assoc_type =
70 self.db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
71 let generic_params = generics(self.db.upcast(), fn_once_trait.into());
72 if generic_params.len() != 2 {
73 return None;
74 }
75
76 let mut param_builder = Substs::builder(num_args);
77 let mut arg_tys = vec![];
78 for _ in 0..num_args {
79 let arg = self.table.new_type_var();
80 param_builder = param_builder.push(arg.clone());
81 arg_tys.push(arg);
82 }
83 let parameters = param_builder.build();
84 let arg_ty = Ty::Apply(ApplicationTy {
85 ctor: TypeCtor::Tuple { cardinality: num_args as u16 },
86 parameters,
87 });
88 let substs =
89 Substs::build_for_generics(&generic_params).push(ty.clone()).push(arg_ty).build();
90
91 let trait_env = Arc::clone(&self.trait_env);
92 let implements_fn_trait =
93 Obligation::Trait(TraitRef { trait_: fn_once_trait, substs: substs.clone() });
94 let goal = self.canonicalizer().canonicalize_obligation(InEnvironment {
95 value: implements_fn_trait.clone(),
96 environment: trait_env,
97 });
98 if self.db.trait_solve(krate, goal.value).is_some() {
99 self.obligations.push(implements_fn_trait);
100 let output_proj_ty =
101 crate::ProjectionTy { associated_ty: output_assoc_type, parameters: substs };
102 let return_ty = self.normalize_projection_ty(output_proj_ty);
103 Some((arg_tys, return_ty))
104 } else {
105 None
106 }
107 }
108
109 pub fn callable_sig(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
110 match ty.callable_sig(self.db) {
111 Some(sig) => Some((sig.params().to_vec(), sig.ret().clone())),
112 None => self.callable_sig_from_fn_trait(ty, num_args),
113 }
114 }
115
116 fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
117 let body = Arc::clone(&self.body); // avoid borrow checker problem
118 let ty = match &body[tgt_expr] {
119 Expr::Missing => Ty::Unknown,
120 Expr::If { condition, then_branch, else_branch } => {
121 // if let is desugared to match, so this is always simple if
122 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
123
124 let condition_diverges = mem::replace(&mut self.diverges, Diverges::Maybe);
125 let mut both_arms_diverge = Diverges::Always;
126
127 let then_ty = self.infer_expr_inner(*then_branch, &expected);
128 both_arms_diverge &= mem::replace(&mut self.diverges, Diverges::Maybe);
129 let else_ty = match else_branch {
130 Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
131 None => Ty::unit(),
132 };
133 both_arms_diverge &= self.diverges;
134
135 self.diverges = condition_diverges | both_arms_diverge;
136
137 self.coerce_merge_branch(&then_ty, &else_ty)
138 }
139 Expr::Block { statements, tail, .. } => {
140 // FIXME: Breakable block inference
141 self.infer_block(statements, *tail, expected)
142 }
143 Expr::Unsafe { body } => self.infer_expr(*body, expected),
144 Expr::TryBlock { body } => {
145 let _inner = self.infer_expr(*body, expected);
146 // FIXME should be std::result::Result<{inner}, _>
147 Ty::Unknown
148 }
149 Expr::Loop { body, label } => {
150 self.breakables.push(BreakableContext {
151 may_break: false,
152 break_ty: self.table.new_type_var(),
153 label: label.clone(),
154 });
155 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
156
157 let ctxt = self.breakables.pop().expect("breakable stack broken");
158 if ctxt.may_break {
159 self.diverges = Diverges::Maybe;
160 }
161
162 if ctxt.may_break {
163 ctxt.break_ty
164 } else {
165 Ty::simple(TypeCtor::Never)
166 }
167 }
168 Expr::While { condition, body, label } => {
169 self.breakables.push(BreakableContext {
170 may_break: false,
171 break_ty: Ty::Unknown,
172 label: label.clone(),
173 });
174 // while let is desugared to a match loop, so this is always simple while
175 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
176 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
177 let _ctxt = self.breakables.pop().expect("breakable stack broken");
178 // the body may not run, so it diverging doesn't mean we diverge
179 self.diverges = Diverges::Maybe;
180 Ty::unit()
181 }
182 Expr::For { iterable, body, pat, label } => {
183 let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
184
185 self.breakables.push(BreakableContext {
186 may_break: false,
187 break_ty: Ty::Unknown,
188 label: label.clone(),
189 });
190 let pat_ty =
191 self.resolve_associated_type(iterable_ty, self.resolve_into_iter_item());
192
193 self.infer_pat(*pat, &pat_ty, BindingMode::default());
194
195 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
196 let _ctxt = self.breakables.pop().expect("breakable stack broken");
197 // the body may not run, so it diverging doesn't mean we diverge
198 self.diverges = Diverges::Maybe;
199 Ty::unit()
200 }
201 Expr::Lambda { body, args, ret_type, arg_types } => {
202 assert_eq!(args.len(), arg_types.len());
203
204 let mut sig_tys = Vec::new();
205
206 // collect explicitly written argument types
207 for arg_type in arg_types.iter() {
208 let arg_ty = if let Some(type_ref) = arg_type {
209 self.make_ty(type_ref)
210 } else {
211 self.table.new_type_var()
212 };
213 sig_tys.push(arg_ty);
214 }
215
216 // add return type
217 let ret_ty = match ret_type {
218 Some(type_ref) => self.make_ty(type_ref),
219 None => self.table.new_type_var(),
220 };
221 sig_tys.push(ret_ty.clone());
222 let sig_ty = Ty::apply(
223 TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1, is_varargs: false },
224 Substs(sig_tys.clone().into()),
225 );
226 let closure_ty =
227 Ty::apply_one(TypeCtor::Closure { def: self.owner, expr: tgt_expr }, sig_ty);
228
229 // Eagerly try to relate the closure type with the expected
230 // type, otherwise we often won't have enough information to
231 // infer the body.
232 self.coerce(&closure_ty, &expected.ty);
233
234 // Now go through the argument patterns
235 for (arg_pat, arg_ty) in args.iter().zip(sig_tys) {
236 let resolved = self.resolve_ty_as_possible(arg_ty);
237 self.infer_pat(*arg_pat, &resolved, BindingMode::default());
238 }
239
240 let prev_diverges = mem::replace(&mut self.diverges, Diverges::Maybe);
241 let prev_ret_ty = mem::replace(&mut self.return_ty, ret_ty.clone());
242
243 self.infer_expr_coerce(*body, &Expectation::has_type(ret_ty));
244
245 self.diverges = prev_diverges;
246 self.return_ty = prev_ret_ty;
247
248 closure_ty
249 }
250 Expr::Call { callee, args } => {
251 let callee_ty = self.infer_expr(*callee, &Expectation::none());
252 let canonicalized = self.canonicalizer().canonicalize_ty(callee_ty.clone());
253 let mut derefs = autoderef(
254 self.db,
255 self.resolver.krate(),
256 InEnvironment {
257 value: canonicalized.value.clone(),
258 environment: self.trait_env.clone(),
259 },
260 );
261 let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs
262 .find_map(|callee_deref_ty| {
263 self.callable_sig(
264 &canonicalized.decanonicalize_ty(callee_deref_ty.value),
265 args.len(),
266 )
267 })
268 .unwrap_or((Vec::new(), Ty::Unknown));
269 self.register_obligations_for_call(&callee_ty);
270 self.check_call_arguments(args, &param_tys);
271 self.normalize_associated_types_in(ret_ty)
272 }
273 Expr::MethodCall { receiver, args, method_name, generic_args } => self
274 .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
275 Expr::Match { expr, arms } => {
276 let input_ty = self.infer_expr(*expr, &Expectation::none());
277
278 let mut result_ty = if arms.is_empty() {
279 Ty::simple(TypeCtor::Never)
280 } else {
281 self.table.new_type_var()
282 };
283
284 let matchee_diverges = self.diverges;
285 let mut all_arms_diverge = Diverges::Always;
286
287 for arm in arms {
288 self.diverges = Diverges::Maybe;
289 let _pat_ty = self.infer_pat(arm.pat, &input_ty, BindingMode::default());
290 if let Some(guard_expr) = arm.guard {
291 self.infer_expr(
292 guard_expr,
293 &Expectation::has_type(Ty::simple(TypeCtor::Bool)),
294 );
295 }
296
297 let arm_ty = self.infer_expr_inner(arm.expr, &expected);
298 all_arms_diverge &= self.diverges;
299 result_ty = self.coerce_merge_branch(&result_ty, &arm_ty);
300 }
301
302 self.diverges = matchee_diverges | all_arms_diverge;
303
304 result_ty
305 }
306 Expr::Path(p) => {
307 // FIXME this could be more efficient...
308 let resolver = resolver_for_expr(self.db.upcast(), self.owner, tgt_expr);
309 self.infer_path(&resolver, p, tgt_expr.into()).unwrap_or(Ty::Unknown)
310 }
311 Expr::Continue { .. } => Ty::simple(TypeCtor::Never),
312 Expr::Break { expr, label } => {
313 let val_ty = if let Some(expr) = expr {
314 self.infer_expr(*expr, &Expectation::none())
315 } else {
316 Ty::unit()
317 };
318
319 let last_ty =
320 if let Some(ctxt) = find_breakable(&mut self.breakables, label.as_ref()) {
321 ctxt.break_ty.clone()
322 } else {
323 Ty::Unknown
324 };
325
326 let merged_type = self.coerce_merge_branch(&last_ty, &val_ty);
327
328 if let Some(ctxt) = find_breakable(&mut self.breakables, label.as_ref()) {
329 ctxt.break_ty = merged_type;
330 ctxt.may_break = true;
331 } else {
332 self.push_diagnostic(InferenceDiagnostic::BreakOutsideOfLoop {
333 expr: tgt_expr,
334 });
335 }
336
337 Ty::simple(TypeCtor::Never)
338 }
339 Expr::Return { expr } => {
340 if let Some(expr) = expr {
341 self.infer_expr_coerce(*expr, &Expectation::has_type(self.return_ty.clone()));
342 } else {
343 let unit = Ty::unit();
344 self.coerce(&unit, &self.return_ty.clone());
345 }
346 Ty::simple(TypeCtor::Never)
347 }
348 Expr::RecordLit { path, fields, spread } => {
349 let (ty, def_id) = self.resolve_variant(path.as_ref());
350 if let Some(variant) = def_id {
351 self.write_variant_resolution(tgt_expr.into(), variant);
352 }
353
354 self.unify(&ty, &expected.ty);
355
356 let substs = ty.substs().unwrap_or_else(Substs::empty);
357 let field_types = def_id.map(|it| self.db.field_types(it)).unwrap_or_default();
358 let variant_data = def_id.map(|it| variant_data(self.db.upcast(), it));
359 for (field_idx, field) in fields.iter().enumerate() {
360 let field_def =
361 variant_data.as_ref().and_then(|it| match it.field(&field.name) {
362 Some(local_id) => Some(FieldId { parent: def_id.unwrap(), local_id }),
363 None => {
364 self.push_diagnostic(InferenceDiagnostic::NoSuchField {
365 expr: tgt_expr,
366 field: field_idx,
367 });
368 None
369 }
370 });
371 if let Some(field_def) = field_def {
372 self.result.record_field_resolutions.insert(field.expr, field_def);
373 }
374 let field_ty = field_def
375 .map_or(Ty::Unknown, |it| field_types[it.local_id].clone().subst(&substs));
376 self.infer_expr_coerce(field.expr, &Expectation::has_type(field_ty));
377 }
378 if let Some(expr) = spread {
379 self.infer_expr(*expr, &Expectation::has_type(ty.clone()));
380 }
381 ty
382 }
383 Expr::Field { expr, name } => {
384 let receiver_ty = self.infer_expr_inner(*expr, &Expectation::none());
385 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
386 let ty = autoderef::autoderef(
387 self.db,
388 self.resolver.krate(),
389 InEnvironment {
390 value: canonicalized.value.clone(),
391 environment: self.trait_env.clone(),
392 },
393 )
394 .find_map(|derefed_ty| match canonicalized.decanonicalize_ty(derefed_ty.value) {
395 Ty::Apply(a_ty) => match a_ty.ctor {
396 TypeCtor::Tuple { .. } => name
397 .as_tuple_index()
398 .and_then(|idx| a_ty.parameters.0.get(idx).cloned()),
399 TypeCtor::Adt(AdtId::StructId(s)) => {
400 self.db.struct_data(s).variant_data.field(name).map(|local_id| {
401 let field = FieldId { parent: s.into(), local_id };
402 self.write_field_resolution(tgt_expr, field);
403 self.db.field_types(s.into())[field.local_id]
404 .clone()
405 .subst(&a_ty.parameters)
406 })
407 }
408 TypeCtor::Adt(AdtId::UnionId(u)) => {
409 self.db.union_data(u).variant_data.field(name).map(|local_id| {
410 let field = FieldId { parent: u.into(), local_id };
411 self.write_field_resolution(tgt_expr, field);
412 self.db.field_types(u.into())[field.local_id]
413 .clone()
414 .subst(&a_ty.parameters)
415 })
416 }
417 _ => None,
418 },
419 _ => None,
420 })
421 .unwrap_or(Ty::Unknown);
422 let ty = self.insert_type_vars(ty);
423 self.normalize_associated_types_in(ty)
424 }
425 Expr::Await { expr } => {
426 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
427 self.resolve_associated_type(inner_ty, self.resolve_future_future_output())
428 }
429 Expr::Try { expr } => {
430 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
431 self.resolve_associated_type(inner_ty, self.resolve_ops_try_ok())
432 }
433 Expr::Cast { expr, type_ref } => {
434 let _inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
435 let cast_ty = self.make_ty(type_ref);
436 // FIXME check the cast...
437 cast_ty
438 }
439 Expr::Ref { expr, rawness, mutability } => {
440 let expectation = if let Some((exp_inner, exp_rawness, exp_mutability)) =
441 &expected.ty.as_reference_or_ptr()
442 {
443 if *exp_mutability == Mutability::Mut && *mutability == Mutability::Shared {
444 // FIXME: throw type error - expected mut reference but found shared ref,
445 // which cannot be coerced
446 }
447 if *exp_rawness == Rawness::Ref && *rawness == Rawness::RawPtr {
448 // FIXME: throw type error - expected reference but found ptr,
449 // which cannot be coerced
450 }
451 Expectation::rvalue_hint(Ty::clone(exp_inner))
452 } else {
453 Expectation::none()
454 };
455 let inner_ty = self.infer_expr_inner(*expr, &expectation);
456 let ty = match rawness {
457 Rawness::RawPtr => TypeCtor::RawPtr(*mutability),
458 Rawness::Ref => TypeCtor::Ref(*mutability),
459 };
460 Ty::apply_one(ty, inner_ty)
461 }
462 Expr::Box { expr } => {
463 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
464 if let Some(box_) = self.resolve_boxed_box() {
465 Ty::apply_one(TypeCtor::Adt(box_), inner_ty)
466 } else {
467 Ty::Unknown
468 }
469 }
470 Expr::UnaryOp { expr, op } => {
471 let inner_ty = self.infer_expr_inner(*expr, &Expectation::none());
472 match op {
473 UnaryOp::Deref => match self.resolver.krate() {
474 Some(krate) => {
475 let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty);
476 match autoderef::deref(
477 self.db,
478 krate,
479 InEnvironment {
480 value: &canonicalized.value,
481 environment: self.trait_env.clone(),
482 },
483 ) {
484 Some(derefed_ty) => {
485 canonicalized.decanonicalize_ty(derefed_ty.value)
486 }
487 None => Ty::Unknown,
488 }
489 }
490 None => Ty::Unknown,
491 },
492 UnaryOp::Neg => {
493 match &inner_ty {
494 // Fast path for builtins
495 Ty::Apply(ApplicationTy {
496 ctor: TypeCtor::Int(IntTy { signedness: Signedness::Signed, .. }),
497 ..
498 })
499 | Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(_), .. })
500 | Ty::Infer(InferTy::IntVar(..))
501 | Ty::Infer(InferTy::FloatVar(..)) => inner_ty,
502 // Otherwise we resolve via the std::ops::Neg trait
503 _ => self
504 .resolve_associated_type(inner_ty, self.resolve_ops_neg_output()),
505 }
506 }
507 UnaryOp::Not => {
508 match &inner_ty {
509 // Fast path for builtins
510 Ty::Apply(ApplicationTy { ctor: TypeCtor::Bool, .. })
511 | Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(_), .. })
512 | Ty::Infer(InferTy::IntVar(..)) => inner_ty,
513 // Otherwise we resolve via the std::ops::Not trait
514 _ => self
515 .resolve_associated_type(inner_ty, self.resolve_ops_not_output()),
516 }
517 }
518 }
519 }
520 Expr::BinaryOp { lhs, rhs, op } => match op {
521 Some(op) => {
522 let lhs_expectation = match op {
523 BinaryOp::LogicOp(..) => Expectation::has_type(Ty::simple(TypeCtor::Bool)),
524 _ => Expectation::none(),
525 };
526 let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
527 // FIXME: find implementation of trait corresponding to operation
528 // symbol and resolve associated `Output` type
529 let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty.clone());
530 let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation));
531
532 // FIXME: similar as above, return ty is often associated trait type
533 op::binary_op_return_ty(*op, lhs_ty, rhs_ty)
534 }
535 _ => Ty::Unknown,
536 },
537 Expr::Range { lhs, rhs, range_type } => {
538 let lhs_ty = lhs.map(|e| self.infer_expr_inner(e, &Expectation::none()));
539 let rhs_expect = lhs_ty
540 .as_ref()
541 .map_or_else(Expectation::none, |ty| Expectation::has_type(ty.clone()));
542 let rhs_ty = rhs.map(|e| self.infer_expr(e, &rhs_expect));
543 match (range_type, lhs_ty, rhs_ty) {
544 (RangeOp::Exclusive, None, None) => match self.resolve_range_full() {
545 Some(adt) => Ty::simple(TypeCtor::Adt(adt)),
546 None => Ty::Unknown,
547 },
548 (RangeOp::Exclusive, None, Some(ty)) => match self.resolve_range_to() {
549 Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
550 None => Ty::Unknown,
551 },
552 (RangeOp::Inclusive, None, Some(ty)) => {
553 match self.resolve_range_to_inclusive() {
554 Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
555 None => Ty::Unknown,
556 }
557 }
558 (RangeOp::Exclusive, Some(_), Some(ty)) => match self.resolve_range() {
559 Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
560 None => Ty::Unknown,
561 },
562 (RangeOp::Inclusive, Some(_), Some(ty)) => {
563 match self.resolve_range_inclusive() {
564 Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
565 None => Ty::Unknown,
566 }
567 }
568 (RangeOp::Exclusive, Some(ty), None) => match self.resolve_range_from() {
569 Some(adt) => Ty::apply_one(TypeCtor::Adt(adt), ty),
570 None => Ty::Unknown,
571 },
572 (RangeOp::Inclusive, _, None) => Ty::Unknown,
573 }
574 }
575 Expr::Index { base, index } => {
576 let base_ty = self.infer_expr_inner(*base, &Expectation::none());
577 let index_ty = self.infer_expr(*index, &Expectation::none());
578
579 if let (Some(index_trait), Some(krate)) =
580 (self.resolve_ops_index(), self.resolver.krate())
581 {
582 let canonicalized = self.canonicalizer().canonicalize_ty(base_ty);
583 let self_ty = method_resolution::resolve_indexing_op(
584 self.db,
585 &canonicalized.value,
586 self.trait_env.clone(),
587 krate,
588 index_trait,
589 );
590 let self_ty =
591 self_ty.map_or(Ty::Unknown, |t| canonicalized.decanonicalize_ty(t.value));
592 self.resolve_associated_type_with_params(
593 self_ty,
594 self.resolve_ops_index_output(),
595 &[index_ty],
596 )
597 } else {
598 Ty::Unknown
599 }
600 }
601 Expr::Tuple { exprs } => {
602 let mut tys = match &expected.ty {
603 ty_app!(TypeCtor::Tuple { .. }, st) => st
604 .iter()
605 .cloned()
606 .chain(repeat_with(|| self.table.new_type_var()))
607 .take(exprs.len())
608 .collect::<Vec<_>>(),
609 _ => (0..exprs.len()).map(|_| self.table.new_type_var()).collect(),
610 };
611
612 for (expr, ty) in exprs.iter().zip(tys.iter_mut()) {
613 self.infer_expr_coerce(*expr, &Expectation::has_type(ty.clone()));
614 }
615
616 Ty::apply(TypeCtor::Tuple { cardinality: tys.len() as u16 }, Substs(tys.into()))
617 }
618 Expr::Array(array) => {
619 let elem_ty = match &expected.ty {
620 ty_app!(TypeCtor::Array, st) | ty_app!(TypeCtor::Slice, st) => {
621 st.as_single().clone()
622 }
623 _ => self.table.new_type_var(),
624 };
625
626 match array {
627 Array::ElementList(items) => {
628 for expr in items.iter() {
629 self.infer_expr_coerce(*expr, &Expectation::has_type(elem_ty.clone()));
630 }
631 }
632 Array::Repeat { initializer, repeat } => {
633 self.infer_expr_coerce(
634 *initializer,
635 &Expectation::has_type(elem_ty.clone()),
636 );
637 self.infer_expr(
638 *repeat,
639 &Expectation::has_type(Ty::simple(TypeCtor::Int(IntTy::usize()))),
640 );
641 }
642 }
643
644 Ty::apply_one(TypeCtor::Array, elem_ty)
645 }
646 Expr::Literal(lit) => match lit {
647 Literal::Bool(..) => Ty::simple(TypeCtor::Bool),
648 Literal::String(..) => {
649 Ty::apply_one(TypeCtor::Ref(Mutability::Shared), Ty::simple(TypeCtor::Str))
650 }
651 Literal::ByteString(..) => {
652 let byte_type = Ty::simple(TypeCtor::Int(IntTy::u8()));
653 let array_type = Ty::apply_one(TypeCtor::Array, byte_type);
654 Ty::apply_one(TypeCtor::Ref(Mutability::Shared), array_type)
655 }
656 Literal::Char(..) => Ty::simple(TypeCtor::Char),
657 Literal::Int(_v, ty) => match ty {
658 Some(int_ty) => Ty::simple(TypeCtor::Int((*int_ty).into())),
659 None => self.table.new_integer_var(),
660 },
661 Literal::Float(_v, ty) => match ty {
662 Some(float_ty) => Ty::simple(TypeCtor::Float((*float_ty).into())),
663 None => self.table.new_float_var(),
664 },
665 },
666 };
667 // use a new type variable if we got Ty::Unknown here
668 let ty = self.insert_type_vars_shallow(ty);
669 let ty = self.resolve_ty_as_possible(ty);
670 self.write_expr_ty(tgt_expr, ty.clone());
671 ty
672 }
673
674 fn infer_block(
675 &mut self,
676 statements: &[Statement],
677 tail: Option<ExprId>,
678 expected: &Expectation,
679 ) -> Ty {
680 for stmt in statements {
681 match stmt {
682 Statement::Let { pat, type_ref, initializer } => {
683 let decl_ty =
684 type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown);
685
686 // Always use the declared type when specified
687 let mut ty = decl_ty.clone();
688
689 if let Some(expr) = initializer {
690 let actual_ty =
691 self.infer_expr_coerce(*expr, &Expectation::has_type(decl_ty.clone()));
692 if decl_ty == Ty::Unknown {
693 ty = actual_ty;
694 }
695 }
696
697 let ty = self.resolve_ty_as_possible(ty);
698 self.infer_pat(*pat, &ty, BindingMode::default());
699 }
700 Statement::Expr(expr) => {
701 self.infer_expr(*expr, &Expectation::none());
702 }
703 }
704 }
705
706 let ty = if let Some(expr) = tail {
707 self.infer_expr_coerce(expr, expected)
708 } else {
709 // Citing rustc: if there is no explicit tail expression,
710 // that is typically equivalent to a tail expression
711 // of `()` -- except if the block diverges. In that
712 // case, there is no value supplied from the tail
713 // expression (assuming there are no other breaks,
714 // this implies that the type of the block will be
715 // `!`).
716 if self.diverges.is_always() {
717 // we don't even make an attempt at coercion
718 self.table.new_maybe_never_type_var()
719 } else {
720 self.coerce(&Ty::unit(), expected.coercion_target());
721 Ty::unit()
722 }
723 };
724 ty
725 }
726
727 fn infer_method_call(
728 &mut self,
729 tgt_expr: ExprId,
730 receiver: ExprId,
731 args: &[ExprId],
732 method_name: &Name,
733 generic_args: Option<&GenericArgs>,
734 ) -> Ty {
735 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
736 let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
737
738 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast());
739
740 let resolved = self.resolver.krate().and_then(|krate| {
741 method_resolution::lookup_method(
742 &canonicalized_receiver.value,
743 self.db,
744 self.trait_env.clone(),
745 krate,
746 &traits_in_scope,
747 method_name,
748 )
749 });
750 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
751 Some((ty, func)) => {
752 let ty = canonicalized_receiver.decanonicalize_ty(ty);
753 self.write_method_resolution(tgt_expr, func);
754 (ty, self.db.value_ty(func.into()), Some(generics(self.db.upcast(), func.into())))
755 }
756 None => (receiver_ty, Binders::new(0, Ty::Unknown), None),
757 };
758 let substs = self.substs_for_method_call(def_generics, generic_args, &derefed_receiver_ty);
759 let method_ty = method_ty.subst(&substs);
760 let method_ty = self.insert_type_vars(method_ty);
761 self.register_obligations_for_call(&method_ty);
762 let (expected_receiver_ty, param_tys, ret_ty) = match method_ty.callable_sig(self.db) {
763 Some(sig) => {
764 if !sig.params().is_empty() {
765 (sig.params()[0].clone(), sig.params()[1..].to_vec(), sig.ret().clone())
766 } else {
767 (Ty::Unknown, Vec::new(), sig.ret().clone())
768 }
769 }
770 None => (Ty::Unknown, Vec::new(), Ty::Unknown),
771 };
772 // Apply autoref so the below unification works correctly
773 // FIXME: return correct autorefs from lookup_method
774 let actual_receiver_ty = match expected_receiver_ty.as_reference() {
775 Some((_, mutability)) => Ty::apply_one(TypeCtor::Ref(mutability), derefed_receiver_ty),
776 _ => derefed_receiver_ty,
777 };
778 self.unify(&expected_receiver_ty, &actual_receiver_ty);
779
780 self.check_call_arguments(args, &param_tys);
781 self.normalize_associated_types_in(ret_ty)
782 }
783
784 fn check_call_arguments(&mut self, args: &[ExprId], param_tys: &[Ty]) {
785 // Quoting https://github.com/rust-lang/rust/blob/6ef275e6c3cb1384ec78128eceeb4963ff788dca/src/librustc_typeck/check/mod.rs#L3325 --
786 // We do this in a pretty awful way: first we type-check any arguments
787 // that are not closures, then we type-check the closures. This is so
788 // that we have more information about the types of arguments when we
789 // type-check the functions. This isn't really the right way to do this.
790 for &check_closures in &[false, true] {
791 let param_iter = param_tys.iter().cloned().chain(repeat(Ty::Unknown));
792 for (&arg, param_ty) in args.iter().zip(param_iter) {
793 let is_closure = matches!(&self.body[arg], Expr::Lambda { .. });
794 if is_closure != check_closures {
795 continue;
796 }
797
798 let param_ty = self.normalize_associated_types_in(param_ty);
799 self.infer_expr_coerce(arg, &Expectation::has_type(param_ty.clone()));
800 }
801 }
802 }
803
804 fn substs_for_method_call(
805 &mut self,
806 def_generics: Option<Generics>,
807 generic_args: Option<&GenericArgs>,
808 receiver_ty: &Ty,
809 ) -> Substs {
810 let (parent_params, self_params, type_params, impl_trait_params) =
811 def_generics.as_ref().map_or((0, 0, 0, 0), |g| g.provenance_split());
812 assert_eq!(self_params, 0); // method shouldn't have another Self param
813 let total_len = parent_params + type_params + impl_trait_params;
814 let mut substs = Vec::with_capacity(total_len);
815 // Parent arguments are unknown, except for the receiver type
816 if let Some(parent_generics) = def_generics.as_ref().map(|p| p.iter_parent()) {
817 for (_id, param) in parent_generics {
818 if param.provenance == hir_def::generics::TypeParamProvenance::TraitSelf {
819 substs.push(receiver_ty.clone());
820 } else {
821 substs.push(Ty::Unknown);
822 }
823 }
824 }
825 // handle provided type arguments
826 if let Some(generic_args) = generic_args {
827 // if args are provided, it should be all of them, but we can't rely on that
828 for arg in generic_args.args.iter().take(type_params) {
829 match arg {
830 GenericArg::Type(type_ref) => {
831 let ty = self.make_ty(type_ref);
832 substs.push(ty);
833 }
834 }
835 }
836 };
837 let supplied_params = substs.len();
838 for _ in supplied_params..total_len {
839 substs.push(Ty::Unknown);
840 }
841 assert_eq!(substs.len(), total_len);
842 Substs(substs.into())
843 }
844
845 fn register_obligations_for_call(&mut self, callable_ty: &Ty) {
846 if let Ty::Apply(a_ty) = callable_ty {
847 if let TypeCtor::FnDef(def) = a_ty.ctor {
848 let generic_predicates = self.db.generic_predicates(def.into());
849 for predicate in generic_predicates.iter() {
850 let predicate = predicate.clone().subst(&a_ty.parameters);
851 if let Some(obligation) = Obligation::from_predicate(predicate) {
852 self.obligations.push(obligation);
853 }
854 }
855 // add obligation for trait implementation, if this is a trait method
856 match def {
857 CallableDefId::FunctionId(f) => {
858 if let AssocContainerId::TraitId(trait_) =
859 f.lookup(self.db.upcast()).container
860 {
861 // construct a TraitDef
862 let substs = a_ty
863 .parameters
864 .prefix(generics(self.db.upcast(), trait_.into()).len());
865 self.obligations.push(Obligation::Trait(TraitRef { trait_, substs }));
866 }
867 }
868 CallableDefId::StructId(_) | CallableDefId::EnumVariantId(_) => {}
869 }
870 }
871 }
872 }
873}
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
new file mode 100644
index 000000000..4dd4f9802
--- /dev/null
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -0,0 +1,241 @@
1//! Type inference for patterns.
2
3use std::iter::repeat;
4use std::sync::Arc;
5
6use hir_def::{
7 expr::{BindingAnnotation, Expr, Literal, Pat, PatId, RecordFieldPat},
8 path::Path,
9 type_ref::Mutability,
10 FieldId,
11};
12use hir_expand::name::Name;
13use test_utils::mark;
14
15use super::{BindingMode, Expectation, InferenceContext};
16use crate::{utils::variant_data, Substs, Ty, TypeCtor};
17
18impl<'a> InferenceContext<'a> {
19 fn infer_tuple_struct_pat(
20 &mut self,
21 path: Option<&Path>,
22 subpats: &[PatId],
23 expected: &Ty,
24 default_bm: BindingMode,
25 id: PatId,
26 ) -> Ty {
27 let (ty, def) = self.resolve_variant(path);
28 let var_data = def.map(|it| variant_data(self.db.upcast(), it));
29 if let Some(variant) = def {
30 self.write_variant_resolution(id.into(), variant);
31 }
32 self.unify(&ty, expected);
33
34 let substs = ty.substs().unwrap_or_else(Substs::empty);
35
36 let field_tys = def.map(|it| self.db.field_types(it)).unwrap_or_default();
37
38 for (i, &subpat) in subpats.iter().enumerate() {
39 let expected_ty = var_data
40 .as_ref()
41 .and_then(|d| d.field(&Name::new_tuple_field(i)))
42 .map_or(Ty::Unknown, |field| field_tys[field].clone().subst(&substs));
43 let expected_ty = self.normalize_associated_types_in(expected_ty);
44 self.infer_pat(subpat, &expected_ty, default_bm);
45 }
46
47 ty
48 }
49
50 fn infer_record_pat(
51 &mut self,
52 path: Option<&Path>,
53 subpats: &[RecordFieldPat],
54 expected: &Ty,
55 default_bm: BindingMode,
56 id: PatId,
57 ) -> Ty {
58 let (ty, def) = self.resolve_variant(path);
59 let var_data = def.map(|it| variant_data(self.db.upcast(), it));
60 if let Some(variant) = def {
61 self.write_variant_resolution(id.into(), variant);
62 }
63
64 self.unify(&ty, expected);
65
66 let substs = ty.substs().unwrap_or_else(Substs::empty);
67
68 let field_tys = def.map(|it| self.db.field_types(it)).unwrap_or_default();
69 for subpat in subpats {
70 let matching_field = var_data.as_ref().and_then(|it| it.field(&subpat.name));
71 if let Some(local_id) = matching_field {
72 let field_def = FieldId { parent: def.unwrap(), local_id };
73 self.result.record_field_pat_resolutions.insert(subpat.pat, field_def);
74 }
75
76 let expected_ty =
77 matching_field.map_or(Ty::Unknown, |field| field_tys[field].clone().subst(&substs));
78 let expected_ty = self.normalize_associated_types_in(expected_ty);
79 self.infer_pat(subpat.pat, &expected_ty, default_bm);
80 }
81
82 ty
83 }
84
85 pub(super) fn infer_pat(
86 &mut self,
87 pat: PatId,
88 mut expected: &Ty,
89 mut default_bm: BindingMode,
90 ) -> Ty {
91 let body = Arc::clone(&self.body); // avoid borrow checker problem
92
93 if is_non_ref_pat(&body, pat) {
94 while let Some((inner, mutability)) = expected.as_reference() {
95 expected = inner;
96 default_bm = match default_bm {
97 BindingMode::Move => BindingMode::Ref(mutability),
98 BindingMode::Ref(Mutability::Shared) => BindingMode::Ref(Mutability::Shared),
99 BindingMode::Ref(Mutability::Mut) => BindingMode::Ref(mutability),
100 }
101 }
102 } else if let Pat::Ref { .. } = &body[pat] {
103 mark::hit!(match_ergonomics_ref);
104 // When you encounter a `&pat` pattern, reset to Move.
105 // This is so that `w` is by value: `let (_, &w) = &(1, &2);`
106 default_bm = BindingMode::Move;
107 }
108
109 // Lose mutability.
110 let default_bm = default_bm;
111 let expected = expected;
112
113 let ty = match &body[pat] {
114 Pat::Tuple { ref args, .. } => {
115 let expectations = match expected.as_tuple() {
116 Some(parameters) => &*parameters.0,
117 _ => &[],
118 };
119 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
120
121 let inner_tys = args
122 .iter()
123 .zip(expectations_iter)
124 .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
125 .collect();
126
127 Ty::apply(TypeCtor::Tuple { cardinality: args.len() as u16 }, Substs(inner_tys))
128 }
129 Pat::Or(ref pats) => {
130 if let Some((first_pat, rest)) = pats.split_first() {
131 let ty = self.infer_pat(*first_pat, expected, default_bm);
132 for pat in rest {
133 self.infer_pat(*pat, expected, default_bm);
134 }
135 ty
136 } else {
137 Ty::Unknown
138 }
139 }
140 Pat::Ref { pat, mutability } => {
141 let expectation = match expected.as_reference() {
142 Some((inner_ty, exp_mut)) => {
143 if *mutability != exp_mut {
144 // FIXME: emit type error?
145 }
146 inner_ty
147 }
148 _ => &Ty::Unknown,
149 };
150 let subty = self.infer_pat(*pat, expectation, default_bm);
151 Ty::apply_one(TypeCtor::Ref(*mutability), subty)
152 }
153 Pat::TupleStruct { path: p, args: subpats, .. } => {
154 self.infer_tuple_struct_pat(p.as_ref(), subpats, expected, default_bm, pat)
155 }
156 Pat::Record { path: p, args: fields, ellipsis: _ } => {
157 self.infer_record_pat(p.as_ref(), fields, expected, default_bm, pat)
158 }
159 Pat::Path(path) => {
160 // FIXME use correct resolver for the surrounding expression
161 let resolver = self.resolver.clone();
162 self.infer_path(&resolver, &path, pat.into()).unwrap_or(Ty::Unknown)
163 }
164 Pat::Bind { mode, name: _, subpat } => {
165 let mode = if mode == &BindingAnnotation::Unannotated {
166 default_bm
167 } else {
168 BindingMode::convert(*mode)
169 };
170 let inner_ty = if let Some(subpat) = subpat {
171 self.infer_pat(*subpat, expected, default_bm)
172 } else {
173 expected.clone()
174 };
175 let inner_ty = self.insert_type_vars_shallow(inner_ty);
176
177 let bound_ty = match mode {
178 BindingMode::Ref(mutability) => {
179 Ty::apply_one(TypeCtor::Ref(mutability), inner_ty.clone())
180 }
181 BindingMode::Move => inner_ty.clone(),
182 };
183 let bound_ty = self.resolve_ty_as_possible(bound_ty);
184 self.write_pat_ty(pat, bound_ty);
185 return inner_ty;
186 }
187 Pat::Slice { prefix, slice, suffix } => {
188 let (container_ty, elem_ty) = match &expected {
189 ty_app!(TypeCtor::Array, st) => (TypeCtor::Array, st.as_single().clone()),
190 ty_app!(TypeCtor::Slice, st) => (TypeCtor::Slice, st.as_single().clone()),
191 _ => (TypeCtor::Slice, Ty::Unknown),
192 };
193
194 for pat_id in prefix.iter().chain(suffix) {
195 self.infer_pat(*pat_id, &elem_ty, default_bm);
196 }
197
198 let pat_ty = Ty::apply_one(container_ty, elem_ty);
199 if let Some(slice_pat_id) = slice {
200 self.infer_pat(*slice_pat_id, &pat_ty, default_bm);
201 }
202
203 pat_ty
204 }
205 Pat::Wild => expected.clone(),
206 Pat::Range { start, end } => {
207 let start_ty = self.infer_expr(*start, &Expectation::has_type(expected.clone()));
208 let end_ty = self.infer_expr(*end, &Expectation::has_type(start_ty));
209 end_ty
210 }
211 Pat::Lit(expr) => self.infer_expr(*expr, &Expectation::has_type(expected.clone())),
212 Pat::Missing => Ty::Unknown,
213 };
214 // use a new type variable if we got Ty::Unknown here
215 let ty = self.insert_type_vars_shallow(ty);
216 if !self.unify(&ty, expected) {
217 // FIXME record mismatch, we need to change the type of self.type_mismatches for that
218 }
219 let ty = self.resolve_ty_as_possible(ty);
220 self.write_pat_ty(pat, ty.clone());
221 ty
222 }
223}
224
225fn is_non_ref_pat(body: &hir_def::body::Body, pat: PatId) -> bool {
226 match &body[pat] {
227 Pat::Tuple { .. }
228 | Pat::TupleStruct { .. }
229 | Pat::Record { .. }
230 | Pat::Range { .. }
231 | Pat::Slice { .. } => true,
232 Pat::Or(pats) => pats.iter().all(|p| is_non_ref_pat(body, *p)),
233 // FIXME: Path/Lit might actually evaluate to ref, but inference is unimplemented.
234 Pat::Path(..) => true,
235 Pat::Lit(expr) => match body[*expr] {
236 Expr::Literal(Literal::String(..)) => false,
237 _ => true,
238 },
239 Pat::Wild | Pat::Bind { .. } | Pat::Ref { .. } | Pat::Missing => false,
240 }
241}
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
new file mode 100644
index 000000000..80d7ed10e
--- /dev/null
+++ b/crates/hir_ty/src/infer/path.rs
@@ -0,0 +1,287 @@
1//! Path expression resolution.
2
3use std::iter;
4
5use hir_def::{
6 path::{Path, PathSegment},
7 resolver::{ResolveValueResult, Resolver, TypeNs, ValueNs},
8 AdtId, AssocContainerId, AssocItemId, EnumVariantId, Lookup,
9};
10use hir_expand::name::Name;
11
12use crate::{method_resolution, Substs, Ty, ValueTyDefId};
13
14use super::{ExprOrPatId, InferenceContext, TraitRef};
15
16impl<'a> InferenceContext<'a> {
17 pub(super) fn infer_path(
18 &mut self,
19 resolver: &Resolver,
20 path: &Path,
21 id: ExprOrPatId,
22 ) -> Option<Ty> {
23 let ty = self.resolve_value_path(resolver, path, id)?;
24 let ty = self.insert_type_vars(ty);
25 let ty = self.normalize_associated_types_in(ty);
26 Some(ty)
27 }
28
29 fn resolve_value_path(
30 &mut self,
31 resolver: &Resolver,
32 path: &Path,
33 id: ExprOrPatId,
34 ) -> Option<Ty> {
35 let (value, self_subst) = if let Some(type_ref) = path.type_anchor() {
36 if path.segments().is_empty() {
37 // This can't actually happen syntax-wise
38 return None;
39 }
40 let ty = self.make_ty(type_ref);
41 let remaining_segments_for_ty = path.segments().take(path.segments().len() - 1);
42 let ctx = crate::lower::TyLoweringContext::new(self.db, &resolver);
43 let (ty, _) = Ty::from_type_relative_path(&ctx, ty, None, remaining_segments_for_ty);
44 self.resolve_ty_assoc_item(
45 ty,
46 &path.segments().last().expect("path had at least one segment").name,
47 id,
48 )?
49 } else {
50 let value_or_partial =
51 resolver.resolve_path_in_value_ns(self.db.upcast(), path.mod_path())?;
52
53 match value_or_partial {
54 ResolveValueResult::ValueNs(it) => (it, None),
55 ResolveValueResult::Partial(def, remaining_index) => {
56 self.resolve_assoc_item(def, path, remaining_index, id)?
57 }
58 }
59 };
60
61 let typable: ValueTyDefId = match value {
62 ValueNs::LocalBinding(pat) => {
63 let ty = self.result.type_of_pat.get(pat)?.clone();
64 let ty = self.resolve_ty_as_possible(ty);
65 return Some(ty);
66 }
67 ValueNs::FunctionId(it) => it.into(),
68 ValueNs::ConstId(it) => it.into(),
69 ValueNs::StaticId(it) => it.into(),
70 ValueNs::StructId(it) => {
71 self.write_variant_resolution(id, it.into());
72
73 it.into()
74 }
75 ValueNs::EnumVariantId(it) => {
76 self.write_variant_resolution(id, it.into());
77
78 it.into()
79 }
80 ValueNs::ImplSelf(impl_id) => {
81 let generics = crate::utils::generics(self.db.upcast(), impl_id.into());
82 let substs = Substs::type_params_for_generics(&generics);
83 let ty = self.db.impl_self_ty(impl_id).subst(&substs);
84 if let Some((AdtId::StructId(struct_id), substs)) = ty.as_adt() {
85 let ty = self.db.value_ty(struct_id.into()).subst(&substs);
86 return Some(ty);
87 } else {
88 // FIXME: diagnostic, invalid Self reference
89 return None;
90 }
91 }
92 };
93
94 let ty = self.db.value_ty(typable);
95 // self_subst is just for the parent
96 let parent_substs = self_subst.unwrap_or_else(Substs::empty);
97 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
98 let substs = Ty::substs_from_path(&ctx, path, typable, true);
99 let full_substs = Substs::builder(substs.len())
100 .use_parent_substs(&parent_substs)
101 .fill(substs.0[parent_substs.len()..].iter().cloned())
102 .build();
103 let ty = ty.subst(&full_substs);
104 Some(ty)
105 }
106
107 fn resolve_assoc_item(
108 &mut self,
109 def: TypeNs,
110 path: &Path,
111 remaining_index: usize,
112 id: ExprOrPatId,
113 ) -> Option<(ValueNs, Option<Substs>)> {
114 assert!(remaining_index < path.segments().len());
115 // there may be more intermediate segments between the resolved one and
116 // the end. Only the last segment needs to be resolved to a value; from
117 // the segments before that, we need to get either a type or a trait ref.
118
119 let resolved_segment = path.segments().get(remaining_index - 1).unwrap();
120 let remaining_segments = path.segments().skip(remaining_index);
121 let is_before_last = remaining_segments.len() == 1;
122
123 match (def, is_before_last) {
124 (TypeNs::TraitId(trait_), true) => {
125 let segment =
126 remaining_segments.last().expect("there should be at least one segment here");
127 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
128 let trait_ref = TraitRef::from_resolved_path(&ctx, trait_, resolved_segment, None);
129 self.resolve_trait_assoc_item(trait_ref, segment, id)
130 }
131 (def, _) => {
132 // Either we already have a type (e.g. `Vec::new`), or we have a
133 // trait but it's not the last segment, so the next segment
134 // should resolve to an associated type of that trait (e.g. `<T
135 // as Iterator>::Item::default`)
136 let remaining_segments_for_ty =
137 remaining_segments.take(remaining_segments.len() - 1);
138 let ctx = crate::lower::TyLoweringContext::new(self.db, &self.resolver);
139 let (ty, _) = Ty::from_partly_resolved_hir_path(
140 &ctx,
141 def,
142 resolved_segment,
143 remaining_segments_for_ty,
144 true,
145 );
146 if let Ty::Unknown = ty {
147 return None;
148 }
149
150 let ty = self.insert_type_vars(ty);
151 let ty = self.normalize_associated_types_in(ty);
152
153 let segment =
154 remaining_segments.last().expect("there should be at least one segment here");
155
156 self.resolve_ty_assoc_item(ty, &segment.name, id)
157 }
158 }
159 }
160
161 fn resolve_trait_assoc_item(
162 &mut self,
163 trait_ref: TraitRef,
164 segment: PathSegment<'_>,
165 id: ExprOrPatId,
166 ) -> Option<(ValueNs, Option<Substs>)> {
167 let trait_ = trait_ref.trait_;
168 let item =
169 self.db.trait_data(trait_).items.iter().map(|(_name, id)| (*id)).find_map(|item| {
170 match item {
171 AssocItemId::FunctionId(func) => {
172 if segment.name == &self.db.function_data(func).name {
173 Some(AssocItemId::FunctionId(func))
174 } else {
175 None
176 }
177 }
178
179 AssocItemId::ConstId(konst) => {
180 if self
181 .db
182 .const_data(konst)
183 .name
184 .as_ref()
185 .map_or(false, |n| n == segment.name)
186 {
187 Some(AssocItemId::ConstId(konst))
188 } else {
189 None
190 }
191 }
192 AssocItemId::TypeAliasId(_) => None,
193 }
194 })?;
195 let def = match item {
196 AssocItemId::FunctionId(f) => ValueNs::FunctionId(f),
197 AssocItemId::ConstId(c) => ValueNs::ConstId(c),
198 AssocItemId::TypeAliasId(_) => unreachable!(),
199 };
200
201 self.write_assoc_resolution(id, item);
202 Some((def, Some(trait_ref.substs)))
203 }
204
205 fn resolve_ty_assoc_item(
206 &mut self,
207 ty: Ty,
208 name: &Name,
209 id: ExprOrPatId,
210 ) -> Option<(ValueNs, Option<Substs>)> {
211 if let Ty::Unknown = ty {
212 return None;
213 }
214
215 if let Some(result) = self.resolve_enum_variant_on_ty(&ty, name, id) {
216 return Some(result);
217 }
218
219 let canonical_ty = self.canonicalizer().canonicalize_ty(ty.clone());
220 let krate = self.resolver.krate()?;
221 let traits_in_scope = self.resolver.traits_in_scope(self.db.upcast());
222
223 method_resolution::iterate_method_candidates(
224 &canonical_ty.value,
225 self.db,
226 self.trait_env.clone(),
227 krate,
228 &traits_in_scope,
229 Some(name),
230 method_resolution::LookupMode::Path,
231 move |_ty, item| {
232 let (def, container) = match item {
233 AssocItemId::FunctionId(f) => {
234 (ValueNs::FunctionId(f), f.lookup(self.db.upcast()).container)
235 }
236 AssocItemId::ConstId(c) => {
237 (ValueNs::ConstId(c), c.lookup(self.db.upcast()).container)
238 }
239 AssocItemId::TypeAliasId(_) => unreachable!(),
240 };
241 let substs = match container {
242 AssocContainerId::ImplId(impl_id) => {
243 let impl_substs = Substs::build_for_def(self.db, impl_id)
244 .fill(iter::repeat_with(|| self.table.new_type_var()))
245 .build();
246 let impl_self_ty = self.db.impl_self_ty(impl_id).subst(&impl_substs);
247 self.unify(&impl_self_ty, &ty);
248 Some(impl_substs)
249 }
250 AssocContainerId::TraitId(trait_) => {
251 // we're picking this method
252 let trait_substs = Substs::build_for_def(self.db, trait_)
253 .push(ty.clone())
254 .fill(std::iter::repeat_with(|| self.table.new_type_var()))
255 .build();
256 self.obligations.push(super::Obligation::Trait(TraitRef {
257 trait_,
258 substs: trait_substs.clone(),
259 }));
260 Some(trait_substs)
261 }
262 AssocContainerId::ContainerId(_) => None,
263 };
264
265 self.write_assoc_resolution(id, item);
266 Some((def, substs))
267 },
268 )
269 }
270
271 fn resolve_enum_variant_on_ty(
272 &mut self,
273 ty: &Ty,
274 name: &Name,
275 id: ExprOrPatId,
276 ) -> Option<(ValueNs, Option<Substs>)> {
277 let (enum_id, subst) = match ty.as_adt() {
278 Some((AdtId::EnumId(e), subst)) => (e, subst),
279 _ => return None,
280 };
281 let enum_data = self.db.enum_data(enum_id);
282 let local_id = enum_data.variant(name)?;
283 let variant = EnumVariantId { parent: enum_id, local_id };
284 self.write_variant_resolution(id, variant.into());
285 Some((ValueNs::EnumVariantId(variant), Some(subst.clone())))
286 }
287}
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
new file mode 100644
index 000000000..2e895d911
--- /dev/null
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -0,0 +1,474 @@
1//! Unification and canonicalization logic.
2
3use std::borrow::Cow;
4
5use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
6
7use test_utils::mark;
8
9use super::{InferenceContext, Obligation};
10use crate::{
11 BoundVar, Canonical, DebruijnIndex, GenericPredicate, InEnvironment, InferTy, Substs, Ty,
12 TyKind, TypeCtor, TypeWalk,
13};
14
15impl<'a> InferenceContext<'a> {
16 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b>
17 where
18 'a: 'b,
19 {
20 Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
21 }
22}
23
24pub(super) struct Canonicalizer<'a, 'b>
25where
26 'a: 'b,
27{
28 ctx: &'b mut InferenceContext<'a>,
29 free_vars: Vec<InferTy>,
30 /// A stack of type variables that is used to detect recursive types (which
31 /// are an error, but we need to protect against them to avoid stack
32 /// overflows).
33 var_stack: Vec<TypeVarId>,
34}
35
36#[derive(Debug)]
37pub(super) struct Canonicalized<T> {
38 pub value: Canonical<T>,
39 free_vars: Vec<InferTy>,
40}
41
42impl<'a, 'b> Canonicalizer<'a, 'b>
43where
44 'a: 'b,
45{
46 fn add(&mut self, free_var: InferTy) -> usize {
47 self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
48 let next_index = self.free_vars.len();
49 self.free_vars.push(free_var);
50 next_index
51 })
52 }
53
54 fn do_canonicalize<T: TypeWalk>(&mut self, t: T, binders: DebruijnIndex) -> T {
55 t.fold_binders(
56 &mut |ty, binders| match ty {
57 Ty::Infer(tv) => {
58 let inner = tv.to_inner();
59 if self.var_stack.contains(&inner) {
60 // recursive type
61 return tv.fallback_value();
62 }
63 if let Some(known_ty) =
64 self.ctx.table.var_unification_table.inlined_probe_value(inner).known()
65 {
66 self.var_stack.push(inner);
67 let result = self.do_canonicalize(known_ty.clone(), binders);
68 self.var_stack.pop();
69 result
70 } else {
71 let root = self.ctx.table.var_unification_table.find(inner);
72 let free_var = match tv {
73 InferTy::TypeVar(_) => InferTy::TypeVar(root),
74 InferTy::IntVar(_) => InferTy::IntVar(root),
75 InferTy::FloatVar(_) => InferTy::FloatVar(root),
76 InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root),
77 };
78 let position = self.add(free_var);
79 Ty::Bound(BoundVar::new(binders, position))
80 }
81 }
82 _ => ty,
83 },
84 binders,
85 )
86 }
87
88 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
89 let kinds = self
90 .free_vars
91 .iter()
92 .map(|v| match v {
93 // mapping MaybeNeverTypeVar to the same kind as general ones
94 // should be fine, because as opposed to int or float type vars,
95 // they don't restrict what kind of type can go into them, they
96 // just affect fallback.
97 InferTy::TypeVar(_) | InferTy::MaybeNeverTypeVar(_) => TyKind::General,
98 InferTy::IntVar(_) => TyKind::Integer,
99 InferTy::FloatVar(_) => TyKind::Float,
100 })
101 .collect();
102 Canonicalized { value: Canonical { value: result, kinds }, free_vars: self.free_vars }
103 }
104
105 pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
106 let result = self.do_canonicalize(ty, DebruijnIndex::INNERMOST);
107 self.into_canonicalized(result)
108 }
109
110 pub(crate) fn canonicalize_obligation(
111 mut self,
112 obligation: InEnvironment<Obligation>,
113 ) -> Canonicalized<InEnvironment<Obligation>> {
114 let result = match obligation.value {
115 Obligation::Trait(tr) => {
116 Obligation::Trait(self.do_canonicalize(tr, DebruijnIndex::INNERMOST))
117 }
118 Obligation::Projection(pr) => {
119 Obligation::Projection(self.do_canonicalize(pr, DebruijnIndex::INNERMOST))
120 }
121 };
122 self.into_canonicalized(InEnvironment {
123 value: result,
124 environment: obligation.environment,
125 })
126 }
127}
128
129impl<T> Canonicalized<T> {
130 pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
131 ty.walk_mut_binders(
132 &mut |ty, binders| {
133 if let &mut Ty::Bound(bound) = ty {
134 if bound.debruijn >= binders {
135 *ty = Ty::Infer(self.free_vars[bound.index]);
136 }
137 }
138 },
139 DebruijnIndex::INNERMOST,
140 );
141 ty
142 }
143
144 pub fn apply_solution(&self, ctx: &mut InferenceContext<'_>, solution: Canonical<Substs>) {
145 // the solution may contain new variables, which we need to convert to new inference vars
146 let new_vars = Substs(
147 solution
148 .kinds
149 .iter()
150 .map(|k| match k {
151 TyKind::General => ctx.table.new_type_var(),
152 TyKind::Integer => ctx.table.new_integer_var(),
153 TyKind::Float => ctx.table.new_float_var(),
154 })
155 .collect(),
156 );
157 for (i, ty) in solution.value.into_iter().enumerate() {
158 let var = self.free_vars[i];
159 // eagerly replace projections in the type; we may be getting types
160 // e.g. from where clauses where this hasn't happened yet
161 let ty = ctx.normalize_associated_types_in(ty.clone().subst_bound_vars(&new_vars));
162 ctx.table.unify(&Ty::Infer(var), &ty);
163 }
164 }
165}
166
167pub fn unify(tys: &Canonical<(Ty, Ty)>) -> Option<Substs> {
168 let mut table = InferenceTable::new();
169 let vars = Substs(
170 tys.kinds
171 .iter()
172 // we always use type vars here because we want everything to
173 // fallback to Unknown in the end (kind of hacky, as below)
174 .map(|_| table.new_type_var())
175 .collect(),
176 );
177 let ty1_with_vars = tys.value.0.clone().subst_bound_vars(&vars);
178 let ty2_with_vars = tys.value.1.clone().subst_bound_vars(&vars);
179 if !table.unify(&ty1_with_vars, &ty2_with_vars) {
180 return None;
181 }
182 // default any type vars that weren't unified back to their original bound vars
183 // (kind of hacky)
184 for (i, var) in vars.iter().enumerate() {
185 if &*table.resolve_ty_shallow(var) == var {
186 table.unify(var, &Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i)));
187 }
188 }
189 Some(
190 Substs::builder(tys.kinds.len())
191 .fill(vars.iter().map(|v| table.resolve_ty_completely(v.clone())))
192 .build(),
193 )
194}
195
196#[derive(Clone, Debug)]
197pub(crate) struct InferenceTable {
198 pub(super) var_unification_table: InPlaceUnificationTable<TypeVarId>,
199}
200
201impl InferenceTable {
202 pub fn new() -> Self {
203 InferenceTable { var_unification_table: InPlaceUnificationTable::new() }
204 }
205
206 pub fn new_type_var(&mut self) -> Ty {
207 Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
208 }
209
210 pub fn new_integer_var(&mut self) -> Ty {
211 Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
212 }
213
214 pub fn new_float_var(&mut self) -> Ty {
215 Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
216 }
217
218 pub fn new_maybe_never_type_var(&mut self) -> Ty {
219 Ty::Infer(InferTy::MaybeNeverTypeVar(
220 self.var_unification_table.new_key(TypeVarValue::Unknown),
221 ))
222 }
223
224 pub fn resolve_ty_completely(&mut self, ty: Ty) -> Ty {
225 self.resolve_ty_completely_inner(&mut Vec::new(), ty)
226 }
227
228 pub fn resolve_ty_as_possible(&mut self, ty: Ty) -> Ty {
229 self.resolve_ty_as_possible_inner(&mut Vec::new(), ty)
230 }
231
232 pub fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
233 self.unify_inner(ty1, ty2, 0)
234 }
235
236 pub fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
237 substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
238 }
239
240 fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
241 if depth > 1000 {
242 // prevent stackoverflows
243 panic!("infinite recursion in unification");
244 }
245 if ty1 == ty2 {
246 return true;
247 }
248 // try to resolve type vars first
249 let ty1 = self.resolve_ty_shallow(ty1);
250 let ty2 = self.resolve_ty_shallow(ty2);
251 match (&*ty1, &*ty2) {
252 (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
253 self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
254 }
255
256 _ => self.unify_inner_trivial(&ty1, &ty2, depth),
257 }
258 }
259
260 pub(super) fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
261 match (ty1, ty2) {
262 (Ty::Unknown, _) | (_, Ty::Unknown) => true,
263
264 (Ty::Placeholder(p1), Ty::Placeholder(p2)) if *p1 == *p2 => true,
265
266 (Ty::Dyn(dyn1), Ty::Dyn(dyn2)) if dyn1.len() == dyn2.len() => {
267 for (pred1, pred2) in dyn1.iter().zip(dyn2.iter()) {
268 if !self.unify_preds(pred1, pred2, depth + 1) {
269 return false;
270 }
271 }
272 true
273 }
274
275 (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
276 | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
277 | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
278 | (
279 Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)),
280 Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)),
281 ) => {
282 // both type vars are unknown since we tried to resolve them
283 self.var_unification_table.union(*tv1, *tv2);
284 true
285 }
286
287 // The order of MaybeNeverTypeVar matters here.
288 // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
289 // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
290 (Ty::Infer(InferTy::TypeVar(tv)), other)
291 | (other, Ty::Infer(InferTy::TypeVar(tv)))
292 | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other)
293 | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv)))
294 | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_)))
295 | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv)))
296 | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_)))
297 | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => {
298 // the type var is unknown since we tried to resolve it
299 self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
300 true
301 }
302
303 _ => false,
304 }
305 }
306
307 fn unify_preds(
308 &mut self,
309 pred1: &GenericPredicate,
310 pred2: &GenericPredicate,
311 depth: usize,
312 ) -> bool {
313 match (pred1, pred2) {
314 (GenericPredicate::Implemented(tr1), GenericPredicate::Implemented(tr2))
315 if tr1.trait_ == tr2.trait_ =>
316 {
317 self.unify_substs(&tr1.substs, &tr2.substs, depth + 1)
318 }
319 (GenericPredicate::Projection(proj1), GenericPredicate::Projection(proj2))
320 if proj1.projection_ty.associated_ty == proj2.projection_ty.associated_ty =>
321 {
322 self.unify_substs(
323 &proj1.projection_ty.parameters,
324 &proj2.projection_ty.parameters,
325 depth + 1,
326 ) && self.unify_inner(&proj1.ty, &proj2.ty, depth + 1)
327 }
328 _ => false,
329 }
330 }
331
332 /// If `ty` is a type variable with known type, returns that type;
333 /// otherwise, return ty.
334 pub fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
335 let mut ty = Cow::Borrowed(ty);
336 // The type variable could resolve to a int/float variable. Hence try
337 // resolving up to three times; each type of variable shouldn't occur
338 // more than once
339 for i in 0..3 {
340 if i > 0 {
341 mark::hit!(type_var_resolves_to_int_var);
342 }
343 match &*ty {
344 Ty::Infer(tv) => {
345 let inner = tv.to_inner();
346 match self.var_unification_table.inlined_probe_value(inner).known() {
347 Some(known_ty) => {
348 // The known_ty can't be a type var itself
349 ty = Cow::Owned(known_ty.clone());
350 }
351 _ => return ty,
352 }
353 }
354 _ => return ty,
355 }
356 }
357 log::error!("Inference variable still not resolved: {:?}", ty);
358 ty
359 }
360
361 /// Resolves the type as far as currently possible, replacing type variables
362 /// by their known types. All types returned by the infer_* functions should
363 /// be resolved as far as possible, i.e. contain no type variables with
364 /// known type.
365 fn resolve_ty_as_possible_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
366 ty.fold(&mut |ty| match ty {
367 Ty::Infer(tv) => {
368 let inner = tv.to_inner();
369 if tv_stack.contains(&inner) {
370 mark::hit!(type_var_cycles_resolve_as_possible);
371 // recursive type
372 return tv.fallback_value();
373 }
374 if let Some(known_ty) =
375 self.var_unification_table.inlined_probe_value(inner).known()
376 {
377 // known_ty may contain other variables that are known by now
378 tv_stack.push(inner);
379 let result = self.resolve_ty_as_possible_inner(tv_stack, known_ty.clone());
380 tv_stack.pop();
381 result
382 } else {
383 ty
384 }
385 }
386 _ => ty,
387 })
388 }
389
390 /// Resolves the type completely; type variables without known type are
391 /// replaced by Ty::Unknown.
392 fn resolve_ty_completely_inner(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
393 ty.fold(&mut |ty| match ty {
394 Ty::Infer(tv) => {
395 let inner = tv.to_inner();
396 if tv_stack.contains(&inner) {
397 mark::hit!(type_var_cycles_resolve_completely);
398 // recursive type
399 return tv.fallback_value();
400 }
401 if let Some(known_ty) =
402 self.var_unification_table.inlined_probe_value(inner).known()
403 {
404 // known_ty may contain other variables that are known by now
405 tv_stack.push(inner);
406 let result = self.resolve_ty_completely_inner(tv_stack, known_ty.clone());
407 tv_stack.pop();
408 result
409 } else {
410 tv.fallback_value()
411 }
412 }
413 _ => ty,
414 })
415 }
416}
417
418/// The ID of a type variable.
419#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
420pub struct TypeVarId(pub(super) u32);
421
422impl UnifyKey for TypeVarId {
423 type Value = TypeVarValue;
424
425 fn index(&self) -> u32 {
426 self.0
427 }
428
429 fn from_index(i: u32) -> Self {
430 TypeVarId(i)
431 }
432
433 fn tag() -> &'static str {
434 "TypeVarId"
435 }
436}
437
438/// The value of a type variable: either we already know the type, or we don't
439/// know it yet.
440#[derive(Clone, PartialEq, Eq, Debug)]
441pub enum TypeVarValue {
442 Known(Ty),
443 Unknown,
444}
445
446impl TypeVarValue {
447 fn known(&self) -> Option<&Ty> {
448 match self {
449 TypeVarValue::Known(ty) => Some(ty),
450 TypeVarValue::Unknown => None,
451 }
452 }
453}
454
455impl UnifyValue for TypeVarValue {
456 type Error = NoError;
457
458 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
459 match (value1, value2) {
460 // We should never equate two type variables, both of which have
461 // known types. Instead, we recursively equate those types.
462 (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
463 "equating two type variables, both of which have known types: {:?} and {:?}",
464 t1, t2
465 ),
466
467 // If one side is known, prefer that one.
468 (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
469 (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
470
471 (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
472 }
473 }
474}