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