aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir/src/ty
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir/src/ty')
-rw-r--r--crates/ra_hir/src/ty/infer.rs1099
-rw-r--r--crates/ra_hir/src/ty/lower.rs333
-rw-r--r--crates/ra_hir/src/ty/op.rs81
-rw-r--r--crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap8
-rw-r--r--crates/ra_hir/src/ty/tests.rs1
5 files changed, 1517 insertions, 5 deletions
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
new file mode 100644
index 000000000..13080b5aa
--- /dev/null
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -0,0 +1,1099 @@
1//! Type inference, i.e. the process of walking through the code and determining
2//! the type of each expression and pattern.
3//!
4//! For type inference, compare the implementations in rustc (the various
5//! check_* methods in librustc_typeck/check/mod.rs are a good entry point) and
6//! IntelliJ-Rust (org.rust.lang.core.types.infer). Our entry point for
7//! inference here is the `infer` function, which infers the types of all
8//! expressions in a given function.
9//!
10//! During inference, types (i.e. the `Ty` struct) can contain type 'variables'
11//! which represent currently unknown types; as we walk through the expressions,
12//! we might determine that certain variables need to be equal to each other, or
13//! to certain types. To record this, we use the union-find implementation from
14//! the `ena` crate, which is extracted from rustc.
15
16use std::borrow::Cow;
17use std::iter::repeat;
18use std::ops::Index;
19use std::sync::Arc;
20use std::mem;
21
22use ena::unify::{InPlaceUnificationTable, UnifyKey, UnifyValue, NoError};
23use ra_arena::map::ArenaMap;
24use rustc_hash::FxHashMap;
25
26use test_utils::tested_by;
27
28use crate::{
29 Function, StructField, Path, Name,
30 FnSignature, AdtDef,
31 HirDatabase,
32 type_ref::{TypeRef, Mutability},
33 expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat, self},
34 generics::GenericParams,
35 path::{GenericArgs, GenericArg},
36 adt::VariantDef,
37 resolve::{Resolver, Resolution},
38 nameres::Namespace
39};
40use super::{Ty, TypableDef, Substs, primitive, op};
41
42/// The entry point of type inference.
43pub fn infer(db: &impl HirDatabase, func: Function) -> Arc<InferenceResult> {
44 db.check_canceled();
45 let body = func.body(db);
46 let resolver = func.resolver(db);
47 let mut ctx = InferenceContext::new(db, body, resolver);
48
49 let signature = func.signature(db);
50 ctx.collect_fn_signature(&signature);
51
52 ctx.infer_body();
53
54 Arc::new(ctx.resolve_all())
55}
56
57/// The result of type inference: A mapping from expressions and patterns to types.
58#[derive(Clone, PartialEq, Eq, Debug)]
59pub struct InferenceResult {
60 /// For each method call expr, records the function it resolves to.
61 method_resolutions: FxHashMap<ExprId, Function>,
62 /// For each field access expr, records the field it resolves to.
63 field_resolutions: FxHashMap<ExprId, StructField>,
64 pub(super) type_of_expr: ArenaMap<ExprId, Ty>,
65 pub(super) type_of_pat: ArenaMap<PatId, Ty>,
66}
67
68impl InferenceResult {
69 pub fn method_resolution(&self, expr: ExprId) -> Option<Function> {
70 self.method_resolutions.get(&expr).map(|it| *it)
71 }
72 pub fn field_resolution(&self, expr: ExprId) -> Option<StructField> {
73 self.field_resolutions.get(&expr).map(|it| *it)
74 }
75}
76
77impl Index<ExprId> for InferenceResult {
78 type Output = Ty;
79
80 fn index(&self, expr: ExprId) -> &Ty {
81 self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown)
82 }
83}
84
85impl Index<PatId> for InferenceResult {
86 type Output = Ty;
87
88 fn index(&self, pat: PatId) -> &Ty {
89 self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown)
90 }
91}
92
93/// The inference context contains all information needed during type inference.
94#[derive(Clone, Debug)]
95struct InferenceContext<'a, D: HirDatabase> {
96 db: &'a D,
97 body: Arc<Body>,
98 resolver: Resolver,
99 var_unification_table: InPlaceUnificationTable<TypeVarId>,
100 method_resolutions: FxHashMap<ExprId, Function>,
101 field_resolutions: FxHashMap<ExprId, StructField>,
102 type_of_expr: ArenaMap<ExprId, Ty>,
103 type_of_pat: ArenaMap<PatId, Ty>,
104 /// The return type of the function being inferred.
105 return_ty: Ty,
106}
107
108impl<'a, D: HirDatabase> InferenceContext<'a, D> {
109 fn new(db: &'a D, body: Arc<Body>, resolver: Resolver) -> Self {
110 InferenceContext {
111 method_resolutions: FxHashMap::default(),
112 field_resolutions: FxHashMap::default(),
113 type_of_expr: ArenaMap::default(),
114 type_of_pat: ArenaMap::default(),
115 var_unification_table: InPlaceUnificationTable::new(),
116 return_ty: Ty::Unknown, // set in collect_fn_signature
117 db,
118 body,
119 resolver,
120 }
121 }
122
123 fn resolve_all(mut self) -> InferenceResult {
124 let mut tv_stack = Vec::new();
125 let mut expr_types = mem::replace(&mut self.type_of_expr, ArenaMap::default());
126 for ty in expr_types.values_mut() {
127 let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
128 *ty = resolved;
129 }
130 let mut pat_types = mem::replace(&mut self.type_of_pat, ArenaMap::default());
131 for ty in pat_types.values_mut() {
132 let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
133 *ty = resolved;
134 }
135 InferenceResult {
136 method_resolutions: self.method_resolutions,
137 field_resolutions: self.field_resolutions,
138 type_of_expr: expr_types,
139 type_of_pat: pat_types,
140 }
141 }
142
143 fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
144 self.type_of_expr.insert(expr, ty);
145 }
146
147 fn write_method_resolution(&mut self, expr: ExprId, func: Function) {
148 self.method_resolutions.insert(expr, func);
149 }
150
151 fn write_field_resolution(&mut self, expr: ExprId, field: StructField) {
152 self.field_resolutions.insert(expr, field);
153 }
154
155 fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
156 self.type_of_pat.insert(pat, ty);
157 }
158
159 fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
160 let ty = Ty::from_hir(
161 self.db,
162 // TODO use right resolver for block
163 &self.resolver,
164 type_ref,
165 );
166 let ty = self.insert_type_vars(ty);
167 ty
168 }
169
170 fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
171 substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
172 }
173
174 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
175 self.unify_inner(ty1, ty2, 0)
176 }
177
178 fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
179 if depth > 1000 {
180 // prevent stackoverflows
181 panic!("infinite recursion in unification");
182 }
183 if ty1 == ty2 {
184 return true;
185 }
186 // try to resolve type vars first
187 let ty1 = self.resolve_ty_shallow(ty1);
188 let ty2 = self.resolve_ty_shallow(ty2);
189 match (&*ty1, &*ty2) {
190 (Ty::Unknown, ..) => true,
191 (.., Ty::Unknown) => true,
192 (Ty::Int(t1), Ty::Int(t2)) => match (t1, t2) {
193 (primitive::UncertainIntTy::Unknown, _)
194 | (_, primitive::UncertainIntTy::Unknown) => true,
195 _ => t1 == t2,
196 },
197 (Ty::Float(t1), Ty::Float(t2)) => match (t1, t2) {
198 (primitive::UncertainFloatTy::Unknown, _)
199 | (_, primitive::UncertainFloatTy::Unknown) => true,
200 _ => t1 == t2,
201 },
202 (Ty::Bool, _) | (Ty::Str, _) | (Ty::Never, _) | (Ty::Char, _) => ty1 == ty2,
203 (
204 Ty::Adt { def_id: def_id1, substs: substs1, .. },
205 Ty::Adt { def_id: def_id2, substs: substs2, .. },
206 ) if def_id1 == def_id2 => self.unify_substs(substs1, substs2, depth + 1),
207 (Ty::Slice(t1), Ty::Slice(t2)) => self.unify_inner(t1, t2, depth + 1),
208 (Ty::RawPtr(t1, m1), Ty::RawPtr(t2, m2)) if m1 == m2 => {
209 self.unify_inner(t1, t2, depth + 1)
210 }
211 (Ty::Ref(t1, m1), Ty::Ref(t2, m2)) if m1 == m2 => self.unify_inner(t1, t2, depth + 1),
212 (Ty::FnPtr(sig1), Ty::FnPtr(sig2)) if sig1 == sig2 => true,
213 (Ty::Tuple(ts1), Ty::Tuple(ts2)) if ts1.len() == ts2.len() => {
214 ts1.iter().zip(ts2.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth + 1))
215 }
216 (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
217 | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
218 | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2))) => {
219 // both type vars are unknown since we tried to resolve them
220 self.var_unification_table.union(*tv1, *tv2);
221 true
222 }
223 (Ty::Infer(InferTy::TypeVar(tv)), other)
224 | (other, Ty::Infer(InferTy::TypeVar(tv)))
225 | (Ty::Infer(InferTy::IntVar(tv)), other)
226 | (other, Ty::Infer(InferTy::IntVar(tv)))
227 | (Ty::Infer(InferTy::FloatVar(tv)), other)
228 | (other, Ty::Infer(InferTy::FloatVar(tv))) => {
229 // the type var is unknown since we tried to resolve it
230 self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
231 true
232 }
233 _ => false,
234 }
235 }
236
237 fn new_type_var(&mut self) -> Ty {
238 Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
239 }
240
241 fn new_integer_var(&mut self) -> Ty {
242 Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
243 }
244
245 fn new_float_var(&mut self) -> Ty {
246 Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
247 }
248
249 /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
250 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
251 match ty {
252 Ty::Unknown => self.new_type_var(),
253 Ty::Int(primitive::UncertainIntTy::Unknown) => self.new_integer_var(),
254 Ty::Float(primitive::UncertainFloatTy::Unknown) => self.new_float_var(),
255 _ => ty,
256 }
257 }
258
259 fn insert_type_vars(&mut self, ty: Ty) -> Ty {
260 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
261 }
262
263 /// Resolves the type as far as currently possible, replacing type variables
264 /// by their known types. All types returned by the infer_* functions should
265 /// be resolved as far as possible, i.e. contain no type variables with
266 /// known type.
267 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
268 ty.fold(&mut |ty| match ty {
269 Ty::Infer(tv) => {
270 let inner = tv.to_inner();
271 if tv_stack.contains(&inner) {
272 tested_by!(type_var_cycles_resolve_as_possible);
273 // recursive type
274 return tv.fallback_value();
275 }
276 if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() {
277 // known_ty may contain other variables that are known by now
278 tv_stack.push(inner);
279 let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone());
280 tv_stack.pop();
281 result
282 } else {
283 ty
284 }
285 }
286 _ => ty,
287 })
288 }
289
290 /// If `ty` is a type variable with known type, returns that type;
291 /// otherwise, return ty.
292 fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
293 let mut ty = Cow::Borrowed(ty);
294 // The type variable could resolve to a int/float variable. Hence try
295 // resolving up to three times; each type of variable shouldn't occur
296 // more than once
297 for i in 0..3 {
298 if i > 0 {
299 tested_by!(type_var_resolves_to_int_var);
300 }
301 match &*ty {
302 Ty::Infer(tv) => {
303 let inner = tv.to_inner();
304 match self.var_unification_table.probe_value(inner).known() {
305 Some(known_ty) => {
306 // The known_ty can't be a type var itself
307 ty = Cow::Owned(known_ty.clone());
308 }
309 _ => return ty,
310 }
311 }
312 _ => return ty,
313 }
314 }
315 log::error!("Inference variable still not resolved: {:?}", ty);
316 ty
317 }
318
319 /// Resolves the type completely; type variables without known type are
320 /// replaced by Ty::Unknown.
321 fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
322 ty.fold(&mut |ty| match ty {
323 Ty::Infer(tv) => {
324 let inner = tv.to_inner();
325 if tv_stack.contains(&inner) {
326 tested_by!(type_var_cycles_resolve_completely);
327 // recursive type
328 return tv.fallback_value();
329 }
330 if let Some(known_ty) = self.var_unification_table.probe_value(inner).known() {
331 // known_ty may contain other variables that are known by now
332 tv_stack.push(inner);
333 let result = self.resolve_ty_completely(tv_stack, known_ty.clone());
334 tv_stack.pop();
335 result
336 } else {
337 tv.fallback_value()
338 }
339 }
340 _ => ty,
341 })
342 }
343
344 fn infer_path_expr(&mut self, resolver: &Resolver, path: &Path) -> Option<Ty> {
345 let resolved = resolver.resolve_path_segments(self.db, &path);
346
347 let (def, remaining_index) = resolved.into_inner();
348
349 log::debug!(
350 "path {:?} resolved to {:?} with remaining index {:?}",
351 path,
352 def,
353 remaining_index
354 );
355
356 // if the remaining_index is None, we expect the path
357 // to be fully resolved, in this case we continue with
358 // the default by attempting to `take_values´ from the resolution.
359 // Otherwise the path was partially resolved, which means
360 // we might have resolved into a type for which
361 // we may find some associated item starting at the
362 // path.segment pointed to by `remaining_index´
363 let mut resolved =
364 if remaining_index.is_none() { def.take_values()? } else { def.take_types()? };
365
366 let remaining_index = remaining_index.unwrap_or(path.segments.len());
367
368 // resolve intermediate segments
369 for segment in &path.segments[remaining_index..] {
370 let ty = match resolved {
371 Resolution::Def(def) => {
372 let typable: Option<TypableDef> = def.into();
373 let typable = typable?;
374
375 let substs =
376 Ty::substs_from_path_segment(self.db, &self.resolver, segment, typable);
377 self.db.type_for_def(typable, Namespace::Types).apply_substs(substs)
378 }
379 Resolution::LocalBinding(_) => {
380 // can't have a local binding in an associated item path
381 return None;
382 }
383 Resolution::GenericParam(..) => {
384 // TODO associated item of generic param
385 return None;
386 }
387 Resolution::SelfType(_) => {
388 // TODO associated item of self type
389 return None;
390 }
391 };
392
393 // Attempt to find an impl_item for the type which has a name matching
394 // the current segment
395 log::debug!("looking for path segment: {:?}", segment);
396 let item = ty.iterate_impl_items(self.db, |item| match item {
397 crate::ImplItem::Method(func) => {
398 let sig = func.signature(self.db);
399 if segment.name == *sig.name() {
400 return Some(func);
401 }
402 None
403 }
404
405 // TODO: Resolve associated const
406 crate::ImplItem::Const(_) => None,
407
408 // TODO: Resolve associated types
409 crate::ImplItem::Type(_) => None,
410 })?;
411 resolved = Resolution::Def(item.into());
412 }
413
414 match resolved {
415 Resolution::Def(def) => {
416 let typable: Option<TypableDef> = def.into();
417 let typable = typable?;
418
419 let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable);
420 let ty = self.db.type_for_def(typable, Namespace::Values).apply_substs(substs);
421 let ty = self.insert_type_vars(ty);
422 Some(ty)
423 }
424 Resolution::LocalBinding(pat) => {
425 let ty = self.type_of_pat.get(pat)?;
426 let ty = self.resolve_ty_as_possible(&mut vec![], ty.clone());
427 Some(ty)
428 }
429 Resolution::GenericParam(..) => {
430 // generic params can't refer to values... yet
431 None
432 }
433 Resolution::SelfType(_) => {
434 log::error!("path expr {:?} resolved to Self type in values ns", path);
435 None
436 }
437 }
438 }
439
440 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantDef>) {
441 let path = match path {
442 Some(path) => path,
443 None => return (Ty::Unknown, None),
444 };
445 let resolver = &self.resolver;
446 let typable: Option<TypableDef> = match resolver.resolve_path(self.db, &path).take_types() {
447 Some(Resolution::Def(def)) => def.into(),
448 Some(Resolution::LocalBinding(..)) => {
449 // this cannot happen
450 log::error!("path resolved to local binding in type ns");
451 return (Ty::Unknown, None);
452 }
453 Some(Resolution::GenericParam(..)) => {
454 // generic params can't be used in struct literals
455 return (Ty::Unknown, None);
456 }
457 Some(Resolution::SelfType(..)) => {
458 // TODO this is allowed in an impl for a struct, handle this
459 return (Ty::Unknown, None);
460 }
461 None => return (Ty::Unknown, None),
462 };
463 let def = match typable {
464 None => return (Ty::Unknown, None),
465 Some(it) => it,
466 };
467 // TODO remove the duplication between here and `Ty::from_path`?
468 let substs = Ty::substs_from_path(self.db, resolver, path, def);
469 match def {
470 TypableDef::Struct(s) => {
471 let ty = s.ty(self.db);
472 let ty = self.insert_type_vars(ty.apply_substs(substs));
473 (ty, Some(s.into()))
474 }
475 TypableDef::EnumVariant(var) => {
476 let ty = var.parent_enum(self.db).ty(self.db);
477 let ty = self.insert_type_vars(ty.apply_substs(substs));
478 (ty, Some(var.into()))
479 }
480 TypableDef::Function(_) | TypableDef::Enum(_) => (Ty::Unknown, None),
481 }
482 }
483
484 fn infer_tuple_struct_pat(
485 &mut self,
486 path: Option<&Path>,
487 subpats: &[PatId],
488 expected: &Ty,
489 ) -> Ty {
490 let (ty, def) = self.resolve_variant(path);
491
492 self.unify(&ty, expected);
493
494 let substs = ty.substs().unwrap_or_else(Substs::empty);
495
496 for (i, &subpat) in subpats.iter().enumerate() {
497 let expected_ty = def
498 .and_then(|d| d.field(self.db, &Name::tuple_field_name(i)))
499 .map_or(Ty::Unknown, |field| field.ty(self.db))
500 .subst(&substs);
501 self.infer_pat(subpat, &expected_ty);
502 }
503
504 ty
505 }
506
507 fn infer_struct_pat(&mut self, path: Option<&Path>, subpats: &[FieldPat], expected: &Ty) -> Ty {
508 let (ty, def) = self.resolve_variant(path);
509
510 self.unify(&ty, expected);
511
512 let substs = ty.substs().unwrap_or_else(Substs::empty);
513
514 for subpat in subpats {
515 let matching_field = def.and_then(|it| it.field(self.db, &subpat.name));
516 let expected_ty =
517 matching_field.map_or(Ty::Unknown, |field| field.ty(self.db)).subst(&substs);
518 self.infer_pat(subpat.pat, &expected_ty);
519 }
520
521 ty
522 }
523
524 fn infer_pat(&mut self, pat: PatId, expected: &Ty) -> Ty {
525 let body = Arc::clone(&self.body); // avoid borrow checker problem
526
527 let ty = match &body[pat] {
528 Pat::Tuple(ref args) => {
529 let expectations = match *expected {
530 Ty::Tuple(ref tuple_args) => &**tuple_args,
531 _ => &[],
532 };
533 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
534
535 let inner_tys = args
536 .iter()
537 .zip(expectations_iter)
538 .map(|(&pat, ty)| self.infer_pat(pat, ty))
539 .collect::<Vec<_>>()
540 .into();
541
542 Ty::Tuple(inner_tys)
543 }
544 Pat::Ref { pat, mutability } => {
545 let expectation = match *expected {
546 Ty::Ref(ref sub_ty, exp_mut) => {
547 if *mutability != exp_mut {
548 // TODO: emit type error?
549 }
550 &**sub_ty
551 }
552 _ => &Ty::Unknown,
553 };
554 let subty = self.infer_pat(*pat, expectation);
555 Ty::Ref(subty.into(), *mutability)
556 }
557 Pat::TupleStruct { path: ref p, args: ref subpats } => {
558 self.infer_tuple_struct_pat(p.as_ref(), subpats, expected)
559 }
560 Pat::Struct { path: ref p, args: ref fields } => {
561 self.infer_struct_pat(p.as_ref(), fields, expected)
562 }
563 Pat::Path(path) => {
564 // TODO use correct resolver for the surrounding expression
565 let resolver = self.resolver.clone();
566 self.infer_path_expr(&resolver, &path).unwrap_or(Ty::Unknown)
567 }
568 Pat::Bind { mode, name: _name, subpat } => {
569 let inner_ty = if let Some(subpat) = subpat {
570 self.infer_pat(*subpat, expected)
571 } else {
572 expected.clone()
573 };
574 let inner_ty = self.insert_type_vars_shallow(inner_ty);
575
576 let bound_ty = match mode {
577 BindingAnnotation::Ref => Ty::Ref(inner_ty.clone().into(), Mutability::Shared),
578 BindingAnnotation::RefMut => Ty::Ref(inner_ty.clone().into(), Mutability::Mut),
579 BindingAnnotation::Mutable | BindingAnnotation::Unannotated => inner_ty.clone(),
580 };
581 let bound_ty = self.resolve_ty_as_possible(&mut vec![], bound_ty);
582 self.write_pat_ty(pat, bound_ty);
583 return inner_ty;
584 }
585 _ => Ty::Unknown,
586 };
587 // use a new type variable if we got Ty::Unknown here
588 let ty = self.insert_type_vars_shallow(ty);
589 self.unify(&ty, expected);
590 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
591 self.write_pat_ty(pat, ty.clone());
592 ty
593 }
594
595 fn substs_for_method_call(
596 &mut self,
597 def_generics: Option<Arc<GenericParams>>,
598 generic_args: &Option<GenericArgs>,
599 ) -> Substs {
600 let (parent_param_count, param_count) =
601 def_generics.map_or((0, 0), |g| (g.count_parent_params(), g.params.len()));
602 let mut substs = Vec::with_capacity(parent_param_count + param_count);
603 for _ in 0..parent_param_count {
604 substs.push(Ty::Unknown);
605 }
606 // handle provided type arguments
607 if let Some(generic_args) = generic_args {
608 // if args are provided, it should be all of them, but we can't rely on that
609 for arg in generic_args.args.iter().take(param_count) {
610 match arg {
611 GenericArg::Type(type_ref) => {
612 let ty = self.make_ty(type_ref);
613 substs.push(ty);
614 }
615 }
616 }
617 };
618 let supplied_params = substs.len();
619 for _ in supplied_params..parent_param_count + param_count {
620 substs.push(Ty::Unknown);
621 }
622 assert_eq!(substs.len(), parent_param_count + param_count);
623 Substs(substs.into())
624 }
625
626 fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
627 let body = Arc::clone(&self.body); // avoid borrow checker problem
628 let ty = match &body[tgt_expr] {
629 Expr::Missing => Ty::Unknown,
630 Expr::If { condition, then_branch, else_branch } => {
631 // if let is desugared to match, so this is always simple if
632 self.infer_expr(*condition, &Expectation::has_type(Ty::Bool));
633 let then_ty = self.infer_expr(*then_branch, expected);
634 match else_branch {
635 Some(else_branch) => {
636 self.infer_expr(*else_branch, expected);
637 }
638 None => {
639 // no else branch -> unit
640 self.unify(&then_ty, &Ty::unit()); // actually coerce
641 }
642 };
643 then_ty
644 }
645 Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected),
646 Expr::Loop { body } => {
647 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
648 // TODO handle break with value
649 Ty::Never
650 }
651 Expr::While { condition, body } => {
652 // while let is desugared to a match loop, so this is always simple while
653 self.infer_expr(*condition, &Expectation::has_type(Ty::Bool));
654 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
655 Ty::unit()
656 }
657 Expr::For { iterable, body, pat } => {
658 let _iterable_ty = self.infer_expr(*iterable, &Expectation::none());
659 self.infer_pat(*pat, &Ty::Unknown);
660 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
661 Ty::unit()
662 }
663 Expr::Lambda { body, args, arg_types } => {
664 assert_eq!(args.len(), arg_types.len());
665
666 for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) {
667 let expected = if let Some(type_ref) = arg_type {
668 let ty = self.make_ty(type_ref);
669 ty
670 } else {
671 Ty::Unknown
672 };
673 self.infer_pat(*arg_pat, &expected);
674 }
675
676 // TODO: infer lambda type etc.
677 let _body_ty = self.infer_expr(*body, &Expectation::none());
678 Ty::Unknown
679 }
680 Expr::Call { callee, args } => {
681 let callee_ty = self.infer_expr(*callee, &Expectation::none());
682 let (param_tys, ret_ty) = match &callee_ty {
683 Ty::FnPtr(sig) => (sig.input.clone(), sig.output.clone()),
684 Ty::FnDef { substs, sig, .. } => {
685 let ret_ty = sig.output.clone().subst(&substs);
686 let param_tys =
687 sig.input.iter().map(|ty| ty.clone().subst(&substs)).collect();
688 (param_tys, ret_ty)
689 }
690 _ => {
691 // not callable
692 // TODO report an error?
693 (Vec::new(), Ty::Unknown)
694 }
695 };
696 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
697 for (arg, param) in args.iter().zip(param_iter) {
698 self.infer_expr(*arg, &Expectation::has_type(param));
699 }
700 ret_ty
701 }
702 Expr::MethodCall { receiver, args, method_name, generic_args } => {
703 let receiver_ty = self.infer_expr(*receiver, &Expectation::none());
704 let resolved = receiver_ty.clone().lookup_method(self.db, method_name);
705 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
706 Some((ty, func)) => {
707 self.write_method_resolution(tgt_expr, func);
708 (
709 ty,
710 self.db.type_for_def(func.into(), Namespace::Values),
711 Some(func.generic_params(self.db)),
712 )
713 }
714 None => (Ty::Unknown, receiver_ty, None),
715 };
716 let substs = self.substs_for_method_call(def_generics, generic_args);
717 let method_ty = method_ty.apply_substs(substs);
718 let method_ty = self.insert_type_vars(method_ty);
719 let (expected_receiver_ty, param_tys, ret_ty) = match &method_ty {
720 Ty::FnPtr(sig) => {
721 if !sig.input.is_empty() {
722 (sig.input[0].clone(), sig.input[1..].to_vec(), sig.output.clone())
723 } else {
724 (Ty::Unknown, Vec::new(), sig.output.clone())
725 }
726 }
727 Ty::FnDef { substs, sig, .. } => {
728 let ret_ty = sig.output.clone().subst(&substs);
729
730 if !sig.input.is_empty() {
731 let mut arg_iter = sig.input.iter().map(|ty| ty.clone().subst(&substs));
732 let receiver_ty = arg_iter.next().unwrap();
733 (receiver_ty, arg_iter.collect(), ret_ty)
734 } else {
735 (Ty::Unknown, Vec::new(), ret_ty)
736 }
737 }
738 _ => (Ty::Unknown, Vec::new(), Ty::Unknown),
739 };
740 // Apply autoref so the below unification works correctly
741 let actual_receiver_ty = match expected_receiver_ty {
742 Ty::Ref(_, mutability) => Ty::Ref(Arc::new(derefed_receiver_ty), mutability),
743 _ => derefed_receiver_ty,
744 };
745 self.unify(&expected_receiver_ty, &actual_receiver_ty);
746
747 let param_iter = param_tys.into_iter().chain(repeat(Ty::Unknown));
748 for (arg, param) in args.iter().zip(param_iter) {
749 self.infer_expr(*arg, &Expectation::has_type(param));
750 }
751 ret_ty
752 }
753 Expr::Match { expr, arms } => {
754 let expected = if expected.ty == Ty::Unknown {
755 Expectation::has_type(self.new_type_var())
756 } else {
757 expected.clone()
758 };
759 let input_ty = self.infer_expr(*expr, &Expectation::none());
760
761 for arm in arms {
762 for &pat in &arm.pats {
763 let _pat_ty = self.infer_pat(pat, &input_ty);
764 }
765 if let Some(guard_expr) = arm.guard {
766 self.infer_expr(guard_expr, &Expectation::has_type(Ty::Bool));
767 }
768 self.infer_expr(arm.expr, &expected);
769 }
770
771 expected.ty
772 }
773 Expr::Path(p) => {
774 // TODO this could be more efficient...
775 let resolver = expr::resolver_for_expr(self.body.clone(), self.db, tgt_expr);
776 self.infer_path_expr(&resolver, p).unwrap_or(Ty::Unknown)
777 }
778 Expr::Continue => Ty::Never,
779 Expr::Break { expr } => {
780 if let Some(expr) = expr {
781 // TODO handle break with value
782 self.infer_expr(*expr, &Expectation::none());
783 }
784 Ty::Never
785 }
786 Expr::Return { expr } => {
787 if let Some(expr) = expr {
788 self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
789 }
790 Ty::Never
791 }
792 Expr::StructLit { path, fields, spread } => {
793 let (ty, def_id) = self.resolve_variant(path.as_ref());
794 let substs = ty.substs().unwrap_or_else(Substs::empty);
795 for field in fields {
796 let field_ty = def_id
797 .and_then(|it| it.field(self.db, &field.name))
798 .map_or(Ty::Unknown, |field| field.ty(self.db))
799 .subst(&substs);
800 self.infer_expr(field.expr, &Expectation::has_type(field_ty));
801 }
802 if let Some(expr) = spread {
803 self.infer_expr(*expr, &Expectation::has_type(ty.clone()));
804 }
805 ty
806 }
807 Expr::Field { expr, name } => {
808 let receiver_ty = self.infer_expr(*expr, &Expectation::none());
809 let ty = receiver_ty
810 .autoderef(self.db)
811 .find_map(|derefed_ty| match derefed_ty {
812 Ty::Tuple(fields) => {
813 let i = name.to_string().parse::<usize>().ok();
814 i.and_then(|i| fields.get(i).cloned())
815 }
816 Ty::Adt { def_id: AdtDef::Struct(s), ref substs, .. } => {
817 s.field(self.db, name).map(|field| {
818 self.write_field_resolution(tgt_expr, field);
819 field.ty(self.db).subst(substs)
820 })
821 }
822 _ => None,
823 })
824 .unwrap_or(Ty::Unknown);
825 self.insert_type_vars(ty)
826 }
827 Expr::Try { expr } => {
828 let _inner_ty = self.infer_expr(*expr, &Expectation::none());
829 Ty::Unknown
830 }
831 Expr::Cast { expr, type_ref } => {
832 let _inner_ty = self.infer_expr(*expr, &Expectation::none());
833 let cast_ty = self.make_ty(type_ref);
834 // TODO check the cast...
835 cast_ty
836 }
837 Expr::Ref { expr, mutability } => {
838 let expectation = if let Ty::Ref(ref subty, expected_mutability) = expected.ty {
839 if expected_mutability == Mutability::Mut && *mutability == Mutability::Shared {
840 // TODO: throw type error - expected mut reference but found shared ref,
841 // which cannot be coerced
842 }
843 Expectation::has_type((**subty).clone())
844 } else {
845 Expectation::none()
846 };
847 // TODO reference coercions etc.
848 let inner_ty = self.infer_expr(*expr, &expectation);
849 Ty::Ref(Arc::new(inner_ty), *mutability)
850 }
851 Expr::UnaryOp { expr, op } => {
852 let inner_ty = self.infer_expr(*expr, &Expectation::none());
853 match op {
854 UnaryOp::Deref => {
855 if let Some(derefed_ty) = inner_ty.builtin_deref() {
856 derefed_ty
857 } else {
858 // TODO Deref::deref
859 Ty::Unknown
860 }
861 }
862 UnaryOp::Neg => {
863 match inner_ty {
864 Ty::Int(primitive::UncertainIntTy::Unknown)
865 | Ty::Int(primitive::UncertainIntTy::Signed(..))
866 | Ty::Infer(InferTy::IntVar(..))
867 | Ty::Infer(InferTy::FloatVar(..))
868 | Ty::Float(..) => inner_ty,
869 // TODO: resolve ops::Neg trait
870 _ => Ty::Unknown,
871 }
872 }
873 UnaryOp::Not => {
874 match inner_ty {
875 Ty::Bool | Ty::Int(_) | Ty::Infer(InferTy::IntVar(..)) => inner_ty,
876 // TODO: resolve ops::Not trait for inner_ty
877 _ => Ty::Unknown,
878 }
879 }
880 }
881 }
882 Expr::BinaryOp { lhs, rhs, op } => match op {
883 Some(op) => {
884 let lhs_expectation = match op {
885 BinaryOp::BooleanAnd | BinaryOp::BooleanOr => {
886 Expectation::has_type(Ty::Bool)
887 }
888 _ => Expectation::none(),
889 };
890 let lhs_ty = self.infer_expr(*lhs, &lhs_expectation);
891 // TODO: find implementation of trait corresponding to operation
892 // symbol and resolve associated `Output` type
893 let rhs_expectation = op::binary_op_rhs_expectation(*op, lhs_ty);
894 let rhs_ty = self.infer_expr(*rhs, &Expectation::has_type(rhs_expectation));
895
896 // TODO: similar as above, return ty is often associated trait type
897 op::binary_op_return_ty(*op, rhs_ty)
898 }
899 _ => Ty::Unknown,
900 },
901 Expr::Tuple { exprs } => {
902 let mut ty_vec = Vec::with_capacity(exprs.len());
903 for arg in exprs.iter() {
904 ty_vec.push(self.infer_expr(*arg, &Expectation::none()));
905 }
906
907 Ty::Tuple(Arc::from(ty_vec))
908 }
909 Expr::Array { exprs } => {
910 let elem_ty = match &expected.ty {
911 Ty::Slice(inner) | Ty::Array(inner) => Ty::clone(&inner),
912 _ => self.new_type_var(),
913 };
914
915 for expr in exprs.iter() {
916 self.infer_expr(*expr, &Expectation::has_type(elem_ty.clone()));
917 }
918
919 Ty::Array(Arc::new(elem_ty))
920 }
921 Expr::Literal(lit) => match lit {
922 Literal::Bool(..) => Ty::Bool,
923 Literal::String(..) => Ty::Ref(Arc::new(Ty::Str), Mutability::Shared),
924 Literal::ByteString(..) => {
925 let byte_type = Arc::new(Ty::Int(primitive::UncertainIntTy::Unsigned(
926 primitive::UintTy::U8,
927 )));
928 let slice_type = Arc::new(Ty::Slice(byte_type));
929 Ty::Ref(slice_type, Mutability::Shared)
930 }
931 Literal::Char(..) => Ty::Char,
932 Literal::Int(_v, ty) => Ty::Int(*ty),
933 Literal::Float(_v, ty) => Ty::Float(*ty),
934 },
935 };
936 // use a new type variable if we got Ty::Unknown here
937 let ty = self.insert_type_vars_shallow(ty);
938 self.unify(&ty, &expected.ty);
939 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
940 self.write_expr_ty(tgt_expr, ty.clone());
941 ty
942 }
943
944 fn infer_block(
945 &mut self,
946 statements: &[Statement],
947 tail: Option<ExprId>,
948 expected: &Expectation,
949 ) -> Ty {
950 for stmt in statements {
951 match stmt {
952 Statement::Let { pat, type_ref, initializer } => {
953 let decl_ty =
954 type_ref.as_ref().map(|tr| self.make_ty(tr)).unwrap_or(Ty::Unknown);
955 let decl_ty = self.insert_type_vars(decl_ty);
956 let ty = if let Some(expr) = initializer {
957 let expr_ty = self.infer_expr(*expr, &Expectation::has_type(decl_ty));
958 expr_ty
959 } else {
960 decl_ty
961 };
962
963 self.infer_pat(*pat, &ty);
964 }
965 Statement::Expr(expr) => {
966 self.infer_expr(*expr, &Expectation::none());
967 }
968 }
969 }
970 let ty = if let Some(expr) = tail { self.infer_expr(expr, expected) } else { Ty::unit() };
971 ty
972 }
973
974 fn collect_fn_signature(&mut self, signature: &FnSignature) {
975 let body = Arc::clone(&self.body); // avoid borrow checker problem
976 for (type_ref, pat) in signature.params().iter().zip(body.params()) {
977 let ty = self.make_ty(type_ref);
978
979 self.infer_pat(*pat, &ty);
980 }
981 self.return_ty = self.make_ty(signature.ret_type());
982 }
983
984 fn infer_body(&mut self) {
985 self.infer_expr(self.body.body_expr(), &Expectation::has_type(self.return_ty.clone()));
986 }
987}
988
989/// The ID of a type variable.
990#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
991pub struct TypeVarId(u32);
992
993impl UnifyKey for TypeVarId {
994 type Value = TypeVarValue;
995
996 fn index(&self) -> u32 {
997 self.0
998 }
999
1000 fn from_index(i: u32) -> Self {
1001 TypeVarId(i)
1002 }
1003
1004 fn tag() -> &'static str {
1005 "TypeVarId"
1006 }
1007}
1008
1009/// The value of a type variable: either we already know the type, or we don't
1010/// know it yet.
1011#[derive(Clone, PartialEq, Eq, Debug)]
1012pub enum TypeVarValue {
1013 Known(Ty),
1014 Unknown,
1015}
1016
1017impl TypeVarValue {
1018 fn known(&self) -> Option<&Ty> {
1019 match self {
1020 TypeVarValue::Known(ty) => Some(ty),
1021 TypeVarValue::Unknown => None,
1022 }
1023 }
1024}
1025
1026impl UnifyValue for TypeVarValue {
1027 type Error = NoError;
1028
1029 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
1030 match (value1, value2) {
1031 // We should never equate two type variables, both of which have
1032 // known types. Instead, we recursively equate those types.
1033 (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
1034 "equating two type variables, both of which have known types: {:?} and {:?}",
1035 t1, t2
1036 ),
1037
1038 // If one side is known, prefer that one.
1039 (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
1040 (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
1041
1042 (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
1043 }
1044 }
1045}
1046
1047/// The kinds of placeholders we need during type inference. There's separate
1048/// values for general types, and for integer and float variables. The latter
1049/// two are used for inference of literal values (e.g. `100` could be one of
1050/// several integer types).
1051#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1052pub enum InferTy {
1053 TypeVar(TypeVarId),
1054 IntVar(TypeVarId),
1055 FloatVar(TypeVarId),
1056}
1057
1058impl InferTy {
1059 fn to_inner(self) -> TypeVarId {
1060 match self {
1061 InferTy::TypeVar(ty) | InferTy::IntVar(ty) | InferTy::FloatVar(ty) => ty,
1062 }
1063 }
1064
1065 fn fallback_value(self) -> Ty {
1066 match self {
1067 InferTy::TypeVar(..) => Ty::Unknown,
1068 InferTy::IntVar(..) => {
1069 Ty::Int(primitive::UncertainIntTy::Signed(primitive::IntTy::I32))
1070 }
1071 InferTy::FloatVar(..) => {
1072 Ty::Float(primitive::UncertainFloatTy::Known(primitive::FloatTy::F64))
1073 }
1074 }
1075 }
1076}
1077
1078/// When inferring an expression, we propagate downward whatever type hint we
1079/// are able in the form of an `Expectation`.
1080#[derive(Clone, PartialEq, Eq, Debug)]
1081struct Expectation {
1082 ty: Ty,
1083 // TODO: In some cases, we need to be aware whether the expectation is that
1084 // the type match exactly what we passed, or whether it just needs to be
1085 // coercible to the expected type. See Expectation::rvalue_hint in rustc.
1086}
1087
1088impl Expectation {
1089 /// The expectation that the type of the expression needs to equal the given
1090 /// type.
1091 fn has_type(ty: Ty) -> Self {
1092 Expectation { ty }
1093 }
1094
1095 /// This expresses no expectation on the type.
1096 fn none() -> Self {
1097 Expectation { ty: Ty::Unknown }
1098 }
1099}
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
new file mode 100644
index 000000000..63e13a30e
--- /dev/null
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -0,0 +1,333 @@
1//! Methods for lowering the HIR to types. There are two main cases here:
2//!
3//! - Lowering a type reference like `&usize` or `Option<foo::bar::Baz>` to a
4//! type: The entry point for this is `Ty::from_hir`.
5//! - Building the type for an item: This happens through the `type_for_def` query.
6//!
7//! This usually involves resolving names, collecting generic arguments etc.
8
9use std::sync::Arc;
10
11use crate::{
12 Function, Struct, StructField, Enum, EnumVariant, Path, Name,
13 ModuleDef,
14 HirDatabase,
15 type_ref::TypeRef,
16 name::KnownName,
17 nameres::Namespace,
18 resolve::{Resolver, Resolution},
19 path::{ PathSegment, GenericArg},
20 generics::GenericParams,
21 adt::VariantDef,
22};
23use super::{Ty, primitive, FnSig, Substs};
24
25impl Ty {
26 pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
27 match type_ref {
28 TypeRef::Never => Ty::Never,
29 TypeRef::Tuple(inner) => {
30 let inner_tys =
31 inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
32 Ty::Tuple(inner_tys.into())
33 }
34 TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path),
35 TypeRef::RawPtr(inner, mutability) => {
36 let inner_ty = Ty::from_hir(db, resolver, inner);
37 Ty::RawPtr(Arc::new(inner_ty), *mutability)
38 }
39 TypeRef::Array(inner) => {
40 let inner_ty = Ty::from_hir(db, resolver, inner);
41 Ty::Array(Arc::new(inner_ty))
42 }
43 TypeRef::Slice(inner) => {
44 let inner_ty = Ty::from_hir(db, resolver, inner);
45 Ty::Slice(Arc::new(inner_ty))
46 }
47 TypeRef::Reference(inner, mutability) => {
48 let inner_ty = Ty::from_hir(db, resolver, inner);
49 Ty::Ref(Arc::new(inner_ty), *mutability)
50 }
51 TypeRef::Placeholder => Ty::Unknown,
52 TypeRef::Fn(params) => {
53 let mut inner_tys =
54 params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
55 let return_ty =
56 inner_tys.pop().expect("TypeRef::Fn should always have at least return type");
57 let sig = FnSig { input: inner_tys, output: return_ty };
58 Ty::FnPtr(Arc::new(sig))
59 }
60 TypeRef::Error => Ty::Unknown,
61 }
62 }
63
64 pub(crate) fn from_hir_path(db: &impl HirDatabase, resolver: &Resolver, path: &Path) -> Self {
65 if let Some(name) = path.as_ident() {
66 // TODO handle primitive type names in resolver as well?
67 if let Some(int_ty) = primitive::UncertainIntTy::from_name(name) {
68 return Ty::Int(int_ty);
69 } else if let Some(float_ty) = primitive::UncertainFloatTy::from_name(name) {
70 return Ty::Float(float_ty);
71 } else if let Some(known) = name.as_known_name() {
72 match known {
73 KnownName::Bool => return Ty::Bool,
74 KnownName::Char => return Ty::Char,
75 KnownName::Str => return Ty::Str,
76 _ => {}
77 }
78 }
79 }
80
81 // Resolve the path (in type namespace)
82 let resolution = resolver.resolve_path(db, path).take_types();
83
84 let def = match resolution {
85 Some(Resolution::Def(def)) => def,
86 Some(Resolution::LocalBinding(..)) => {
87 // this should never happen
88 panic!("path resolved to local binding in type ns");
89 }
90 Some(Resolution::GenericParam(idx)) => {
91 return Ty::Param {
92 idx,
93 // TODO: maybe return name in resolution?
94 name: path
95 .as_ident()
96 .expect("generic param should be single-segment path")
97 .clone(),
98 };
99 }
100 Some(Resolution::SelfType(impl_block)) => {
101 return impl_block.target_ty(db);
102 }
103 None => return Ty::Unknown,
104 };
105
106 let typable: TypableDef = match def.into() {
107 None => return Ty::Unknown,
108 Some(it) => it,
109 };
110 let ty = db.type_for_def(typable, Namespace::Types);
111 let substs = Ty::substs_from_path(db, resolver, path, typable);
112 ty.apply_substs(substs)
113 }
114
115 pub(super) fn substs_from_path_segment(
116 db: &impl HirDatabase,
117 resolver: &Resolver,
118 segment: &PathSegment,
119 resolved: TypableDef,
120 ) -> Substs {
121 let mut substs = Vec::new();
122 let def_generics = match resolved {
123 TypableDef::Function(func) => func.generic_params(db),
124 TypableDef::Struct(s) => s.generic_params(db),
125 TypableDef::Enum(e) => e.generic_params(db),
126 TypableDef::EnumVariant(var) => var.parent_enum(db).generic_params(db),
127 };
128 let parent_param_count = def_generics.count_parent_params();
129 substs.extend((0..parent_param_count).map(|_| Ty::Unknown));
130 if let Some(generic_args) = &segment.args_and_bindings {
131 // if args are provided, it should be all of them, but we can't rely on that
132 let param_count = def_generics.params.len();
133 for arg in generic_args.args.iter().take(param_count) {
134 match arg {
135 GenericArg::Type(type_ref) => {
136 let ty = Ty::from_hir(db, resolver, type_ref);
137 substs.push(ty);
138 }
139 }
140 }
141 }
142 // add placeholders for args that were not provided
143 // TODO: handle defaults
144 let supplied_params = substs.len();
145 for _ in supplied_params..def_generics.count_params_including_parent() {
146 substs.push(Ty::Unknown);
147 }
148 assert_eq!(substs.len(), def_generics.count_params_including_parent());
149 Substs(substs.into())
150 }
151
152 /// Collect generic arguments from a path into a `Substs`. See also
153 /// `create_substs_for_ast_path` and `def_to_ty` in rustc.
154 pub(super) fn substs_from_path(
155 db: &impl HirDatabase,
156 resolver: &Resolver,
157 path: &Path,
158 resolved: TypableDef,
159 ) -> Substs {
160 let last = path.segments.last().expect("path should have at least one segment");
161 let segment = match resolved {
162 TypableDef::Function(_) => last,
163 TypableDef::Struct(_) => last,
164 TypableDef::Enum(_) => last,
165 TypableDef::EnumVariant(_) => {
166 // the generic args for an enum variant may be either specified
167 // on the segment referring to the enum, or on the segment
168 // referring to the variant. So `Option::<T>::None` and
169 // `Option::None::<T>` are both allowed (though the former is
170 // preferred). See also `def_ids_for_path_segments` in rustc.
171 let len = path.segments.len();
172 let segment = if len >= 2 && path.segments[len - 2].args_and_bindings.is_some() {
173 // Option::<T>::None
174 &path.segments[len - 2]
175 } else {
176 // Option::None::<T>
177 last
178 };
179 segment
180 }
181 };
182 Ty::substs_from_path_segment(db, resolver, segment, resolved)
183 }
184}
185
186/// Build the declared type of an item. This depends on the namespace; e.g. for
187/// `struct Foo(usize)`, we have two types: The type of the struct itself, and
188/// the constructor function `(usize) -> Foo` which lives in the values
189/// namespace.
190pub(crate) fn type_for_def(db: &impl HirDatabase, def: TypableDef, ns: Namespace) -> Ty {
191 match (def, ns) {
192 (TypableDef::Function(f), Namespace::Values) => type_for_fn(db, f),
193 (TypableDef::Struct(s), Namespace::Types) => type_for_struct(db, s),
194 (TypableDef::Struct(s), Namespace::Values) => type_for_struct_constructor(db, s),
195 (TypableDef::Enum(e), Namespace::Types) => type_for_enum(db, e),
196 (TypableDef::EnumVariant(v), Namespace::Values) => type_for_enum_variant_constructor(db, v),
197
198 // 'error' cases:
199 (TypableDef::Function(_), Namespace::Types) => Ty::Unknown,
200 (TypableDef::Enum(_), Namespace::Values) => Ty::Unknown,
201 (TypableDef::EnumVariant(_), Namespace::Types) => Ty::Unknown,
202 }
203}
204
205/// Build the type of a specific field of a struct or enum variant.
206pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty {
207 let parent_def = field.parent_def(db);
208 let resolver = match parent_def {
209 VariantDef::Struct(it) => it.resolver(db),
210 VariantDef::EnumVariant(it) => it.parent_enum(db).resolver(db),
211 };
212 let var_data = parent_def.variant_data(db);
213 let type_ref = &var_data.fields().unwrap()[field.id].type_ref;
214 Ty::from_hir(db, &resolver, type_ref)
215}
216
217/// Build the declared type of a function. This should not need to look at the
218/// function body.
219fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty {
220 let signature = def.signature(db);
221 let resolver = def.resolver(db);
222 let generics = def.generic_params(db);
223 let name = def.name(db);
224 let input =
225 signature.params().iter().map(|tr| Ty::from_hir(db, &resolver, tr)).collect::<Vec<_>>();
226 let output = Ty::from_hir(db, &resolver, signature.ret_type());
227 let sig = Arc::new(FnSig { input, output });
228 let substs = make_substs(&generics);
229 Ty::FnDef { def: def.into(), sig, name, substs }
230}
231
232/// Build the type of a tuple struct constructor.
233fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty {
234 let var_data = def.variant_data(db);
235 let fields = match var_data.fields() {
236 Some(fields) => fields,
237 None => return type_for_struct(db, def), // Unit struct
238 };
239 let resolver = def.resolver(db);
240 let generics = def.generic_params(db);
241 let name = def.name(db).unwrap_or_else(Name::missing);
242 let input = fields
243 .iter()
244 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
245 .collect::<Vec<_>>();
246 let output = type_for_struct(db, def);
247 let sig = Arc::new(FnSig { input, output });
248 let substs = make_substs(&generics);
249 Ty::FnDef { def: def.into(), sig, name, substs }
250}
251
252/// Build the type of a tuple enum variant constructor.
253fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) -> Ty {
254 let var_data = def.variant_data(db);
255 let fields = match var_data.fields() {
256 Some(fields) => fields,
257 None => return type_for_enum(db, def.parent_enum(db)), // Unit variant
258 };
259 let resolver = def.parent_enum(db).resolver(db);
260 let generics = def.parent_enum(db).generic_params(db);
261 let name = def.name(db).unwrap_or_else(Name::missing);
262 let input = fields
263 .iter()
264 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
265 .collect::<Vec<_>>();
266 let substs = make_substs(&generics);
267 let output = type_for_enum(db, def.parent_enum(db)).apply_substs(substs.clone());
268 let sig = Arc::new(FnSig { input, output });
269 Ty::FnDef { def: def.into(), sig, name, substs }
270}
271
272fn make_substs(generics: &GenericParams) -> Substs {
273 Substs(
274 generics
275 .params_including_parent()
276 .into_iter()
277 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
278 .collect::<Vec<_>>()
279 .into(),
280 )
281}
282
283fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty {
284 let generics = s.generic_params(db);
285 Ty::Adt {
286 def_id: s.into(),
287 name: s.name(db).unwrap_or_else(Name::missing),
288 substs: make_substs(&generics),
289 }
290}
291
292fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty {
293 let generics = s.generic_params(db);
294 Ty::Adt {
295 def_id: s.into(),
296 name: s.name(db).unwrap_or_else(Name::missing),
297 substs: make_substs(&generics),
298 }
299}
300
301#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
302pub enum TypableDef {
303 Function(Function),
304 Struct(Struct),
305 Enum(Enum),
306 EnumVariant(EnumVariant),
307}
308impl_froms!(TypableDef: Function, Struct, Enum, EnumVariant);
309
310impl From<ModuleDef> for Option<TypableDef> {
311 fn from(def: ModuleDef) -> Option<TypableDef> {
312 let res = match def {
313 ModuleDef::Function(f) => f.into(),
314 ModuleDef::Struct(s) => s.into(),
315 ModuleDef::Enum(e) => e.into(),
316 ModuleDef::EnumVariant(v) => v.into(),
317 ModuleDef::Const(_)
318 | ModuleDef::Static(_)
319 | ModuleDef::Module(_)
320 | ModuleDef::Trait(_)
321 | ModuleDef::Type(_) => return None,
322 };
323 Some(res)
324 }
325}
326
327#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
328pub enum CallableDef {
329 Function(Function),
330 Struct(Struct),
331 EnumVariant(EnumVariant),
332}
333impl_froms!(CallableDef: Function, Struct, EnumVariant);
diff --git a/crates/ra_hir/src/ty/op.rs b/crates/ra_hir/src/ty/op.rs
new file mode 100644
index 000000000..8703cf236
--- /dev/null
+++ b/crates/ra_hir/src/ty/op.rs
@@ -0,0 +1,81 @@
1use crate::expr::BinaryOp;
2use super::{Ty, InferTy};
3
4pub(super) fn binary_op_return_ty(op: BinaryOp, rhs_ty: Ty) -> Ty {
5 match op {
6 BinaryOp::BooleanOr
7 | BinaryOp::BooleanAnd
8 | BinaryOp::EqualityTest
9 | BinaryOp::NegatedEqualityTest
10 | BinaryOp::LesserEqualTest
11 | BinaryOp::GreaterEqualTest
12 | BinaryOp::LesserTest
13 | BinaryOp::GreaterTest => Ty::Bool,
14 BinaryOp::Assignment
15 | BinaryOp::AddAssign
16 | BinaryOp::SubAssign
17 | BinaryOp::DivAssign
18 | BinaryOp::MulAssign
19 | BinaryOp::RemAssign
20 | BinaryOp::ShrAssign
21 | BinaryOp::ShlAssign
22 | BinaryOp::BitAndAssign
23 | BinaryOp::BitOrAssign
24 | BinaryOp::BitXorAssign => Ty::unit(),
25 BinaryOp::Addition
26 | BinaryOp::Subtraction
27 | BinaryOp::Multiplication
28 | BinaryOp::Division
29 | BinaryOp::Remainder
30 | BinaryOp::LeftShift
31 | BinaryOp::RightShift
32 | BinaryOp::BitwiseAnd
33 | BinaryOp::BitwiseOr
34 | BinaryOp::BitwiseXor => match rhs_ty {
35 Ty::Int(..)
36 | Ty::Float(..)
37 | Ty::Infer(InferTy::IntVar(..))
38 | Ty::Infer(InferTy::FloatVar(..)) => rhs_ty,
39 _ => Ty::Unknown,
40 },
41 BinaryOp::RangeRightOpen | BinaryOp::RangeRightClosed => Ty::Unknown,
42 }
43}
44
45pub(super) fn binary_op_rhs_expectation(op: BinaryOp, lhs_ty: Ty) -> Ty {
46 match op {
47 BinaryOp::BooleanAnd | BinaryOp::BooleanOr => Ty::Bool,
48 BinaryOp::Assignment | BinaryOp::EqualityTest => match lhs_ty {
49 Ty::Int(..) | Ty::Float(..) | Ty::Str | Ty::Char | Ty::Bool => lhs_ty,
50 _ => Ty::Unknown,
51 },
52 BinaryOp::LesserEqualTest
53 | BinaryOp::GreaterEqualTest
54 | BinaryOp::LesserTest
55 | BinaryOp::GreaterTest
56 | BinaryOp::AddAssign
57 | BinaryOp::SubAssign
58 | BinaryOp::DivAssign
59 | BinaryOp::MulAssign
60 | BinaryOp::RemAssign
61 | BinaryOp::ShrAssign
62 | BinaryOp::ShlAssign
63 | BinaryOp::BitAndAssign
64 | BinaryOp::BitOrAssign
65 | BinaryOp::BitXorAssign
66 | BinaryOp::Addition
67 | BinaryOp::Subtraction
68 | BinaryOp::Multiplication
69 | BinaryOp::Division
70 | BinaryOp::Remainder
71 | BinaryOp::LeftShift
72 | BinaryOp::RightShift
73 | BinaryOp::BitwiseAnd
74 | BinaryOp::BitwiseOr
75 | BinaryOp::BitwiseXor => match lhs_ty {
76 Ty::Int(..) | Ty::Float(..) => lhs_ty,
77 _ => Ty::Unknown,
78 },
79 _ => Ty::Unknown,
80 }
81}
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap
index fe5d6590e..44694dfdb 100644
--- a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap
@@ -1,5 +1,5 @@
1--- 1---
2created: "2019-02-21T10:25:18.568887300Z" 2created: "2019-02-23T21:58:35.844769207Z"
3creator: [email protected] 3creator: [email protected]
4source: crates/ra_hir/src/ty/tests.rs 4source: crates/ra_hir/src/ty/tests.rs
5expression: "&result" 5expression: "&result"
@@ -9,8 +9,8 @@ expression: "&result"
9[92; 103) 'Gen { val }': Gen<T> 9[92; 103) 'Gen { val }': Gen<T>
10[98; 101) 'val': T 10[98; 101) 'val': T
11[123; 155) '{ ...32); }': () 11[123; 155) '{ ...32); }': ()
12[133; 134) 'a': Gen<[unknown]> 12[133; 134) 'a': Gen<u32>
13[137; 146) 'Gen::make': fn make<[unknown]>(T) -> Gen<T> 13[137; 146) 'Gen::make': fn make<u32>(T) -> Gen<T>
14[137; 152) 'Gen::make(0u32)': Gen<[unknown]> 14[137; 152) 'Gen::make(0u32)': Gen<u32>
15[147; 151) '0u32': u32 15[147; 151) '0u32': u32
16 16
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 77aeca669..d0da34677 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -719,7 +719,6 @@ fn test() {
719} 719}
720 720
721#[test] 721#[test]
722#[ignore] // FIXME: After https://github.com/rust-analyzer/rust-analyzer/pull/866 is merged
723fn infer_associated_method_generics() { 722fn infer_associated_method_generics() {
724 check_inference( 723 check_inference(
725 "infer_associated_method_generics", 724 "infer_associated_method_generics",
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-01 11:10:20 +0000