aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir')
-rw-r--r--crates/ra_hir/Cargo.toml20
-rw-r--r--crates/ra_hir/src/code_model.rs47
-rw-r--r--crates/ra_hir/src/db.rs117
-rw-r--r--crates/ra_hir/src/diagnostics.rs91
-rw-r--r--crates/ra_hir/src/expr.rs146
-rw-r--r--crates/ra_hir/src/lib.rs9
-rw-r--r--crates/ra_hir/src/marks.rs9
-rw-r--r--crates/ra_hir/src/source_binder.rs22
-rw-r--r--crates/ra_hir/src/test_db.rs123
-rw-r--r--crates/ra_hir/src/ty.rs1111
-rw-r--r--crates/ra_hir/src/ty/autoderef.rs108
-rw-r--r--crates/ra_hir/src/ty/display.rs93
-rw-r--r--crates/ra_hir/src/ty/infer.rs723
-rw-r--r--crates/ra_hir/src/ty/infer/coerce.rs357
-rw-r--r--crates/ra_hir/src/ty/infer/expr.rs689
-rw-r--r--crates/ra_hir/src/ty/infer/pat.rs189
-rw-r--r--crates/ra_hir/src/ty/infer/path.rs273
-rw-r--r--crates/ra_hir/src/ty/infer/unify.rs166
-rw-r--r--crates/ra_hir/src/ty/lower.rs760
-rw-r--r--crates/ra_hir/src/ty/method_resolution.rs362
-rw-r--r--crates/ra_hir/src/ty/op.rs50
-rw-r--r--crates/ra_hir/src/ty/primitive.rs3
-rw-r--r--crates/ra_hir/src/ty/tests.rs4896
-rw-r--r--crates/ra_hir/src/ty/tests/coercion.rs369
-rw-r--r--crates/ra_hir/src/ty/tests/never_type.rs246
-rw-r--r--crates/ra_hir/src/ty/traits.rs328
-rw-r--r--crates/ra_hir/src/ty/traits/chalk.rs906
-rw-r--r--crates/ra_hir/src/ty/utils.rs75
-rw-r--r--crates/ra_hir/src/util.rs12
29 files changed, 46 insertions, 12254 deletions
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index caba85a4f..e79361e7c 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -8,31 +8,11 @@ authors = ["rust-analyzer developers"]
8doctest = false 8doctest = false
9 9
10[dependencies] 10[dependencies]
11arrayvec = "0.5.1"
12log = "0.4.5" 11log = "0.4.5"
13rustc-hash = "1.0" 12rustc-hash = "1.0"
14parking_lot = "0.10.0"
15ena = "0.13"
16once_cell = "1.0.1"
17 13
18ra_syntax = { path = "../ra_syntax" } 14ra_syntax = { path = "../ra_syntax" }
19ra_arena = { path = "../ra_arena" }
20ra_cfg = { path = "../ra_cfg" }
21ra_db = { path = "../ra_db" } 15ra_db = { path = "../ra_db" }
22mbe = { path = "../ra_mbe", package = "ra_mbe" }
23tt = { path = "../ra_tt", package = "ra_tt" }
24hir_expand = { path = "../ra_hir_expand", package = "ra_hir_expand" } 16hir_expand = { path = "../ra_hir_expand", package = "ra_hir_expand" }
25hir_def = { path = "../ra_hir_def", package = "ra_hir_def" } 17hir_def = { path = "../ra_hir_def", package = "ra_hir_def" }
26hir_ty = { path = "../ra_hir_ty", package = "ra_hir_ty" } 18hir_ty = { path = "../ra_hir_ty", package = "ra_hir_ty" }
27test_utils = { path = "../test_utils" }
28ra_prof = { path = "../ra_prof" }
29
30# https://github.com/rust-lang/chalk/pull/294
31chalk-solve = { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
32chalk-rust-ir = { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
33chalk-ir = { git = "https://github.com/jackh726/chalk.git", rev = "095cd38a4f16337913bba487f2055b9ca0179f30" }
34
35lalrpop-intern = "0.15.1"
36
37[dev-dependencies]
38insta = "0.12.0"
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index 52ad4e5d1..87c78d98e 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -6,8 +6,10 @@ use std::sync::Arc;
6 6
7use hir_def::{ 7use hir_def::{
8 adt::VariantData, 8 adt::VariantData,
9 body::{Body, BodySourceMap},
9 builtin_type::BuiltinType, 10 builtin_type::BuiltinType,
10 docs::Documentation, 11 docs::Documentation,
12 expr::{BindingAnnotation, Pat, PatId},
11 per_ns::PerNs, 13 per_ns::PerNs,
12 resolver::HasResolver, 14 resolver::HasResolver,
13 type_ref::{Mutability, TypeRef}, 15 type_ref::{Mutability, TypeRef},
@@ -20,12 +22,12 @@ use hir_expand::{
20 name::{self, AsName}, 22 name::{self, AsName},
21 AstId, MacroDefId, 23 AstId, MacroDefId,
22}; 24};
25use hir_ty::expr::ExprValidator;
23use ra_db::{CrateId, Edition, FileId, FilePosition}; 26use ra_db::{CrateId, Edition, FileId, FilePosition};
24use ra_syntax::{ast, AstNode, SyntaxNode}; 27use ra_syntax::{ast, AstNode, SyntaxNode};
25 28
26use crate::{ 29use crate::{
27 db::{DefDatabase, HirDatabase}, 30 db::{DefDatabase, HirDatabase},
28 expr::{BindingAnnotation, Body, BodySourceMap, ExprValidator, Pat, PatId},
29 ty::display::HirFormatter, 31 ty::display::HirFormatter,
30 ty::{ 32 ty::{
31 self, InEnvironment, InferenceResult, TraitEnvironment, TraitRef, Ty, TyDefId, TypeCtor, 33 self, InEnvironment, InferenceResult, TraitEnvironment, TraitRef, Ty, TyDefId, TypeCtor,
@@ -353,8 +355,8 @@ impl Struct {
353 .map(|(id, _)| StructField { parent: self.into(), id }) 355 .map(|(id, _)| StructField { parent: self.into(), id })
354 } 356 }
355 357
356 pub fn ty(self, db: &impl HirDatabase) -> Ty { 358 pub fn ty(self, db: &impl HirDatabase) -> Type {
357 db.ty(self.id.into()) 359 Type::from_def(db, self.id.module(db).krate, self.id)
358 } 360 }
359 361
360 pub fn constructor_ty(self, db: &impl HirDatabase) -> Ty { 362 pub fn constructor_ty(self, db: &impl HirDatabase) -> Ty {
@@ -380,8 +382,8 @@ impl Union {
380 Module { id: self.id.module(db) } 382 Module { id: self.id.module(db) }
381 } 383 }
382 384
383 pub fn ty(self, db: &impl HirDatabase) -> Ty { 385 pub fn ty(self, db: &impl HirDatabase) -> Type {
384 db.ty(self.id.into()) 386 Type::from_def(db, self.id.module(db).krate, self.id)
385 } 387 }
386 388
387 pub fn fields(self, db: &impl HirDatabase) -> Vec<StructField> { 389 pub fn fields(self, db: &impl HirDatabase) -> Vec<StructField> {
@@ -441,8 +443,8 @@ impl Enum {
441 .map(|(id, _)| EnumVariant { parent: self, id }) 443 .map(|(id, _)| EnumVariant { parent: self, id })
442 } 444 }
443 445
444 pub fn ty(self, db: &impl HirDatabase) -> Ty { 446 pub fn ty(self, db: &impl HirDatabase) -> Type {
445 db.ty(self.id.into()) 447 Type::from_def(db, self.id.module(db).krate, self.id)
446 } 448 }
447} 449}
448 450
@@ -640,7 +642,7 @@ impl Function {
640 pub fn diagnostics(self, db: &impl HirDatabase, sink: &mut DiagnosticSink) { 642 pub fn diagnostics(self, db: &impl HirDatabase, sink: &mut DiagnosticSink) {
641 let infer = self.infer(db); 643 let infer = self.infer(db);
642 infer.add_diagnostics(db, self.id, sink); 644 infer.add_diagnostics(db, self.id, sink);
643 let mut validator = ExprValidator::new(self, infer, sink); 645 let mut validator = ExprValidator::new(self.id, infer, sink);
644 validator.validate_body(db); 646 validator.validate_body(db);
645 } 647 }
646} 648}
@@ -946,13 +948,12 @@ impl ImplBlock {
946 db.impl_data(self.id).target_type.clone() 948 db.impl_data(self.id).target_type.clone()
947 } 949 }
948 950
949 pub fn target_ty(&self, db: &impl HirDatabase) -> Ty { 951 pub fn target_ty(&self, db: &impl HirDatabase) -> Type {
950 Ty::from_hir(db, &self.id.resolver(db), &self.target_type(db)) 952 let impl_data = db.impl_data(self.id);
951 } 953 let resolver = self.id.resolver(db);
952 954 let environment = TraitEnvironment::lower(db, &resolver);
953 pub fn target_trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> { 955 let ty = Ty::from_hir(db, &resolver, &impl_data.target_type);
954 let target_ty = self.target_ty(db); 956 Type { krate: self.id.module(db).krate, ty: InEnvironment { value: ty, environment } }
955 TraitRef::from_hir(db, &self.id.resolver(db), &self.target_trait(db)?, Some(target_ty))
956 } 957 }
957 958
958 pub fn items(&self, db: &impl DefDatabase) -> Vec<AssocItem> { 959 pub fn items(&self, db: &impl DefDatabase) -> Vec<AssocItem> {
@@ -1130,6 +1131,22 @@ impl Type {
1130 Some(adt.into()) 1131 Some(adt.into())
1131 } 1132 }
1132 1133
1134 // FIXME: provide required accessors such that it becomes implementable from outside.
1135 pub fn is_equal_for_find_impls(&self, other: &Type) -> bool {
1136 match (&self.ty.value, &other.ty.value) {
1137 (Ty::Apply(a_original_ty), Ty::Apply(ty::ApplicationTy { ctor, parameters })) => {
1138 match ctor {
1139 TypeCtor::Ref(..) => match parameters.as_single() {
1140 Ty::Apply(a_ty) => a_original_ty.ctor == a_ty.ctor,
1141 _ => false,
1142 },
1143 _ => a_original_ty.ctor == *ctor,
1144 }
1145 }
1146 _ => false,
1147 }
1148 }
1149
1133 fn derived(&self, ty: Ty) -> Type { 1150 fn derived(&self, ty: Ty) -> Type {
1134 Type { 1151 Type {
1135 krate: self.krate, 1152 krate: self.krate,
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index e192c8f47..bfae3660b 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -1,18 +1,5 @@
1//! FIXME: write short doc here 1//! FIXME: write short doc here
2 2
3use std::sync::Arc;
4
5use hir_def::{DefWithBodyId, GenericDefId, ImplId, LocalStructFieldId, TraitId, VariantId};
6use ra_arena::map::ArenaMap;
7use ra_db::{salsa, CrateId};
8
9use crate::ty::{
10 method_resolution::CrateImplBlocks,
11 traits::{AssocTyValue, Impl},
12 CallableDef, FnSig, GenericPredicate, InferenceResult, Substs, Ty, TyDefId, TypeCtor,
13 ValueTyDefId,
14};
15
16pub use hir_def::db::{ 3pub use hir_def::db::{
17 BodyQuery, BodyWithSourceMapQuery, ConstDataQuery, CrateDefMapQuery, CrateLangItemsQuery, 4 BodyQuery, BodyWithSourceMapQuery, ConstDataQuery, CrateDefMapQuery, CrateLangItemsQuery,
18 DefDatabase, DefDatabaseStorage, DocumentationQuery, EnumDataQuery, ExprScopesQuery, 5 DefDatabase, DefDatabaseStorage, DocumentationQuery, EnumDataQuery, ExprScopesQuery,
@@ -24,104 +11,12 @@ pub use hir_expand::db::{
24 AstDatabase, AstDatabaseStorage, AstIdMapQuery, MacroArgQuery, MacroDefQuery, MacroExpandQuery, 11 AstDatabase, AstDatabaseStorage, AstIdMapQuery, MacroArgQuery, MacroDefQuery, MacroExpandQuery,
25 ParseMacroQuery, 12 ParseMacroQuery,
26}; 13};
27 14pub use hir_ty::db::{
28#[salsa::query_group(HirDatabaseStorage)] 15 AssociatedTyDataQuery, CallableItemSignatureQuery, FieldTypesQuery, GenericDefaultsQuery,
29#[salsa::requires(salsa::Database)] 16 GenericPredicatesQuery, HirDatabase, HirDatabaseStorage, ImplDatumQuery, ImplsForTraitQuery,
30pub trait HirDatabase: DefDatabase { 17 ImplsInCrateQuery, InferQuery, StructDatumQuery, TraitDatumQuery, TraitSolveQuery, TyQuery,
31 #[salsa::invoke(crate::ty::infer_query)] 18 ValueTyQuery,
32 fn infer(&self, def: DefWithBodyId) -> Arc<InferenceResult>; 19};
33
34 #[salsa::invoke(crate::ty::ty_query)]
35 fn ty(&self, def: TyDefId) -> Ty;
36
37 #[salsa::invoke(crate::ty::value_ty_query)]
38 fn value_ty(&self, def: ValueTyDefId) -> Ty;
39
40 #[salsa::invoke(crate::ty::field_types_query)]
41 fn field_types(&self, var: VariantId) -> Arc<ArenaMap<LocalStructFieldId, Ty>>;
42
43 #[salsa::invoke(crate::ty::callable_item_sig)]
44 fn callable_item_signature(&self, def: CallableDef) -> FnSig;
45
46 #[salsa::invoke(crate::ty::generic_predicates_for_param_query)]
47 fn generic_predicates_for_param(
48 &self,
49 def: GenericDefId,
50 param_idx: u32,
51 ) -> Arc<[GenericPredicate]>;
52
53 #[salsa::invoke(crate::ty::generic_predicates_query)]
54 fn generic_predicates(&self, def: GenericDefId) -> Arc<[GenericPredicate]>;
55
56 #[salsa::invoke(crate::ty::generic_defaults_query)]
57 fn generic_defaults(&self, def: GenericDefId) -> Substs;
58
59 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
60 fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplBlocks>;
61
62 #[salsa::invoke(crate::ty::traits::impls_for_trait_query)]
63 fn impls_for_trait(&self, krate: CrateId, trait_: TraitId) -> Arc<[ImplId]>;
64
65 /// This provides the Chalk trait solver instance. Because Chalk always
66 /// works from a specific crate, this query is keyed on the crate; and
67 /// because Chalk does its own internal caching, the solver is wrapped in a
68 /// Mutex and the query does an untracked read internally, to make sure the
69 /// cached state is thrown away when input facts change.
70 #[salsa::invoke(crate::ty::traits::trait_solver_query)]
71 fn trait_solver(&self, krate: CrateId) -> crate::ty::traits::TraitSolver;
72
73 // Interned IDs for Chalk integration
74 #[salsa::interned]
75 fn intern_type_ctor(&self, type_ctor: TypeCtor) -> crate::ty::TypeCtorId;
76 #[salsa::interned]
77 fn intern_chalk_impl(&self, impl_: Impl) -> crate::ty::traits::GlobalImplId;
78 #[salsa::interned]
79 fn intern_assoc_ty_value(
80 &self,
81 assoc_ty_value: AssocTyValue,
82 ) -> crate::ty::traits::AssocTyValueId;
83
84 #[salsa::invoke(crate::ty::traits::chalk::associated_ty_data_query)]
85 fn associated_ty_data(
86 &self,
87 id: chalk_ir::TypeId,
88 ) -> Arc<chalk_rust_ir::AssociatedTyDatum<chalk_ir::family::ChalkIr>>;
89
90 #[salsa::invoke(crate::ty::traits::chalk::trait_datum_query)]
91 fn trait_datum(
92 &self,
93 krate: CrateId,
94 trait_id: chalk_ir::TraitId,
95 ) -> Arc<chalk_rust_ir::TraitDatum<chalk_ir::family::ChalkIr>>;
96
97 #[salsa::invoke(crate::ty::traits::chalk::struct_datum_query)]
98 fn struct_datum(
99 &self,
100 krate: CrateId,
101 struct_id: chalk_ir::StructId,
102 ) -> Arc<chalk_rust_ir::StructDatum<chalk_ir::family::ChalkIr>>;
103
104 #[salsa::invoke(crate::ty::traits::chalk::impl_datum_query)]
105 fn impl_datum(
106 &self,
107 krate: CrateId,
108 impl_id: chalk_ir::ImplId,
109 ) -> Arc<chalk_rust_ir::ImplDatum<chalk_ir::family::ChalkIr>>;
110
111 #[salsa::invoke(crate::ty::traits::chalk::associated_ty_value_query)]
112 fn associated_ty_value(
113 &self,
114 krate: CrateId,
115 id: chalk_rust_ir::AssociatedTyValueId,
116 ) -> Arc<chalk_rust_ir::AssociatedTyValue<chalk_ir::family::ChalkIr>>;
117
118 #[salsa::invoke(crate::ty::traits::trait_solve_query)]
119 fn trait_solve(
120 &self,
121 krate: CrateId,
122 goal: crate::ty::Canonical<crate::ty::InEnvironment<crate::ty::Obligation>>,
123 ) -> Option<crate::ty::traits::Solution>;
124}
125 20
126#[test] 21#[test]
127fn hir_database_is_object_safe() { 22fn hir_database_is_object_safe() {
diff --git a/crates/ra_hir/src/diagnostics.rs b/crates/ra_hir/src/diagnostics.rs
index 6db499e06..a9040ea3d 100644
--- a/crates/ra_hir/src/diagnostics.rs
+++ b/crates/ra_hir/src/diagnostics.rs
@@ -1,93 +1,4 @@
1//! FIXME: write short doc here 1//! FIXME: write short doc here
2
3use std::any::Any;
4
5use hir_expand::HirFileId;
6use ra_syntax::{ast, AstNode, AstPtr, SyntaxNodePtr};
7
8use crate::{db::AstDatabase, Name, Source};
9
10pub use hir_def::diagnostics::UnresolvedModule; 2pub use hir_def::diagnostics::UnresolvedModule;
11pub use hir_expand::diagnostics::{AstDiagnostic, Diagnostic, DiagnosticSink}; 3pub use hir_expand::diagnostics::{AstDiagnostic, Diagnostic, DiagnosticSink};
12 4pub use hir_ty::diagnostics::{MissingFields, MissingOkInTailExpr, NoSuchField};
13#[derive(Debug)]
14pub struct NoSuchField {
15 pub file: HirFileId,
16 pub field: AstPtr<ast::RecordField>,
17}
18
19impl Diagnostic for NoSuchField {
20 fn message(&self) -> String {
21 "no such field".to_string()
22 }
23
24 fn source(&self) -> Source<SyntaxNodePtr> {
25 Source { file_id: self.file, value: self.field.into() }
26 }
27
28 fn as_any(&self) -> &(dyn Any + Send + 'static) {
29 self
30 }
31}
32
33#[derive(Debug)]
34pub struct MissingFields {
35 pub file: HirFileId,
36 pub field_list: AstPtr<ast::RecordFieldList>,
37 pub missed_fields: Vec<Name>,
38}
39
40impl Diagnostic for MissingFields {
41 fn message(&self) -> String {
42 use std::fmt::Write;
43 let mut message = String::from("Missing structure fields:\n");
44 for field in &self.missed_fields {
45 write!(message, "- {}\n", field).unwrap();
46 }
47 message
48 }
49 fn source(&self) -> Source<SyntaxNodePtr> {
50 Source { file_id: self.file, value: self.field_list.into() }
51 }
52 fn as_any(&self) -> &(dyn Any + Send + 'static) {
53 self
54 }
55}
56
57impl AstDiagnostic for MissingFields {
58 type AST = ast::RecordFieldList;
59
60 fn ast(&self, db: &impl AstDatabase) -> Self::AST {
61 let root = db.parse_or_expand(self.source().file_id).unwrap();
62 let node = self.source().value.to_node(&root);
63 ast::RecordFieldList::cast(node).unwrap()
64 }
65}
66
67#[derive(Debug)]
68pub struct MissingOkInTailExpr {
69 pub file: HirFileId,
70 pub expr: AstPtr<ast::Expr>,
71}
72
73impl Diagnostic for MissingOkInTailExpr {
74 fn message(&self) -> String {
75 "wrap return expression in Ok".to_string()
76 }
77 fn source(&self) -> Source<SyntaxNodePtr> {
78 Source { file_id: self.file, value: self.expr.into() }
79 }
80 fn as_any(&self) -> &(dyn Any + Send + 'static) {
81 self
82 }
83}
84
85impl AstDiagnostic for MissingOkInTailExpr {
86 type AST = ast::Expr;
87
88 fn ast(&self, db: &impl AstDatabase) -> Self::AST {
89 let root = db.parse_or_expand(self.file).unwrap();
90 let node = self.source().value.to_node(&root);
91 ast::Expr::cast(node).unwrap()
92 }
93}
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
deleted file mode 100644
index 5c82c23d6..000000000
--- a/crates/ra_hir/src/expr.rs
+++ /dev/null
@@ -1,146 +0,0 @@
1//! FIXME: write short doc here
2
3use std::sync::Arc;
4
5use hir_def::{path::known, resolver::HasResolver, AdtId};
6use hir_expand::diagnostics::DiagnosticSink;
7use ra_syntax::ast;
8use ra_syntax::AstPtr;
9use rustc_hash::FxHashSet;
10
11use crate::{
12 db::HirDatabase,
13 diagnostics::{MissingFields, MissingOkInTailExpr},
14 ty::{ApplicationTy, InferenceResult, Ty, TypeCtor},
15 Function, Name, Path, Struct,
16};
17
18pub use hir_def::{
19 body::{
20 scope::{ExprScopes, ScopeEntry, ScopeId},
21 Body, BodySourceMap, ExprPtr, ExprSource, PatPtr, PatSource,
22 },
23 expr::{
24 ArithOp, Array, BinaryOp, BindingAnnotation, CmpOp, Expr, ExprId, Literal, LogicOp,
25 MatchArm, Ordering, Pat, PatId, RecordFieldPat, RecordLitField, Statement, UnaryOp,
26 },
27};
28
29pub(crate) struct ExprValidator<'a, 'b: 'a> {
30 func: Function,
31 infer: Arc<InferenceResult>,
32 sink: &'a mut DiagnosticSink<'b>,
33}
34
35impl<'a, 'b> ExprValidator<'a, 'b> {
36 pub(crate) fn new(
37 func: Function,
38 infer: Arc<InferenceResult>,
39 sink: &'a mut DiagnosticSink<'b>,
40 ) -> ExprValidator<'a, 'b> {
41 ExprValidator { func, infer, sink }
42 }
43
44 pub(crate) fn validate_body(&mut self, db: &impl HirDatabase) {
45 let body = self.func.body(db);
46
47 for e in body.exprs.iter() {
48 if let (id, Expr::RecordLit { path, fields, spread }) = e {
49 self.validate_record_literal(id, path, fields, *spread, db);
50 }
51 }
52
53 let body_expr = &body[body.body_expr];
54 if let Expr::Block { statements: _, tail: Some(t) } = body_expr {
55 self.validate_results_in_tail_expr(body.body_expr, *t, db);
56 }
57 }
58
59 fn validate_record_literal(
60 &mut self,
61 id: ExprId,
62 _path: &Option<Path>,
63 fields: &[RecordLitField],
64 spread: Option<ExprId>,
65 db: &impl HirDatabase,
66 ) {
67 if spread.is_some() {
68 return;
69 }
70
71 let struct_def = match self.infer[id].as_adt() {
72 Some((AdtId::StructId(s), _)) => Struct::from(s),
73 _ => return,
74 };
75
76 let lit_fields: FxHashSet<_> = fields.iter().map(|f| &f.name).collect();
77 let missed_fields: Vec<Name> = struct_def
78 .fields(db)
79 .iter()
80 .filter_map(|f| {
81 let name = f.name(db);
82 if lit_fields.contains(&name) {
83 None
84 } else {
85 Some(name)
86 }
87 })
88 .collect();
89 if missed_fields.is_empty() {
90 return;
91 }
92 let source_map = self.func.body_source_map(db);
93
94 if let Some(source_ptr) = source_map.expr_syntax(id) {
95 if let Some(expr) = source_ptr.value.a() {
96 let root = source_ptr.file_syntax(db);
97 if let ast::Expr::RecordLit(record_lit) = expr.to_node(&root) {
98 if let Some(field_list) = record_lit.record_field_list() {
99 self.sink.push(MissingFields {
100 file: source_ptr.file_id,
101 field_list: AstPtr::new(&field_list),
102 missed_fields,
103 })
104 }
105 }
106 }
107 }
108 }
109
110 fn validate_results_in_tail_expr(
111 &mut self,
112 body_id: ExprId,
113 id: ExprId,
114 db: &impl HirDatabase,
115 ) {
116 // the mismatch will be on the whole block currently
117 let mismatch = match self.infer.type_mismatch_for_expr(body_id) {
118 Some(m) => m,
119 None => return,
120 };
121
122 let std_result_path = known::std_result_result();
123
124 let resolver = self.func.id.resolver(db);
125 let std_result_enum = match resolver.resolve_known_enum(db, &std_result_path) {
126 Some(it) => it,
127 _ => return,
128 };
129
130 let std_result_ctor = TypeCtor::Adt(AdtId::EnumId(std_result_enum));
131 let params = match &mismatch.expected {
132 Ty::Apply(ApplicationTy { ctor, parameters }) if ctor == &std_result_ctor => parameters,
133 _ => return,
134 };
135
136 if params.len() == 2 && &params[0] == &mismatch.actual {
137 let source_map = self.func.body_source_map(db);
138
139 if let Some(source_ptr) = source_map.expr_syntax(id) {
140 if let Some(expr) = source_ptr.value.a() {
141 self.sink.push(MissingOkInTailExpr { file: source_ptr.file_id, expr });
142 }
143 }
144 }
145 }
146}
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index b88e4c745..3c12c61f0 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -32,20 +32,13 @@ pub mod db;
32pub mod source_binder; 32pub mod source_binder;
33 33
34mod ty; 34mod ty;
35mod expr;
36pub mod diagnostics; 35pub mod diagnostics;
37mod util;
38 36
39mod from_id; 37mod from_id;
40mod code_model; 38mod code_model;
41 39
42pub mod from_source; 40pub mod from_source;
43 41
44#[cfg(test)]
45mod test_db;
46#[cfg(test)]
47mod marks;
48
49pub use crate::{ 42pub use crate::{
50 code_model::{ 43 code_model::{
51 src::HasSource, Adt, AssocItem, AttrDef, Const, Container, Crate, CrateDependency, 44 src::HasSource, Adt, AssocItem, AttrDef, Const, Container, Crate, CrateDependency,
@@ -53,7 +46,6 @@ pub use crate::{
53 HasAttrs, ImplBlock, Import, Local, MacroDef, Module, ModuleDef, ModuleSource, ScopeDef, 46 HasAttrs, ImplBlock, Import, Local, MacroDef, Module, ModuleDef, ModuleSource, ScopeDef,
54 Static, Struct, StructField, Trait, Type, TypeAlias, Union, VariantDef, 47 Static, Struct, StructField, Trait, Type, TypeAlias, Union, VariantDef,
55 }, 48 },
56 expr::ExprScopes,
57 from_source::FromSource, 49 from_source::FromSource,
58 source_binder::{PathResolution, ScopeEntryWithSyntax, SourceAnalyzer}, 50 source_binder::{PathResolution, ScopeEntryWithSyntax, SourceAnalyzer},
59 ty::{ 51 ty::{
@@ -64,6 +56,7 @@ pub use crate::{
64}; 56};
65 57
66pub use hir_def::{ 58pub use hir_def::{
59 body::scope::ExprScopes,
67 builtin_type::BuiltinType, 60 builtin_type::BuiltinType,
68 docs::Documentation, 61 docs::Documentation,
69 path::{Path, PathKind}, 62 path::{Path, PathKind},
diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs
deleted file mode 100644
index 0f754eb9c..000000000
--- a/crates/ra_hir/src/marks.rs
+++ /dev/null
@@ -1,9 +0,0 @@
1//! See test_utils/src/marks.rs
2
3test_utils::marks!(
4 type_var_cycles_resolve_completely
5 type_var_cycles_resolve_as_possible
6 type_var_resolves_to_int_var
7 match_ergonomics_ref
8 coerce_merge_fail_fallback
9);
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 05f5bca57..76c493f1a 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -8,6 +8,10 @@
8use std::sync::Arc; 8use std::sync::Arc;
9 9
10use hir_def::{ 10use hir_def::{
11 body::{
12 scope::{ExprScopes, ScopeId},
13 BodySourceMap,
14 },
11 expr::{ExprId, PatId}, 15 expr::{ExprId, PatId},
12 path::known, 16 path::known,
13 resolver::{self, resolver_for_scope, HasResolver, Resolver, TypeNs, ValueNs}, 17 resolver::{self, resolver_for_scope, HasResolver, Resolver, TypeNs, ValueNs},
@@ -25,7 +29,6 @@ use ra_syntax::{
25 29
26use crate::{ 30use crate::{
27 db::HirDatabase, 31 db::HirDatabase,
28 expr::{BodySourceMap, ExprScopes, ScopeId},
29 ty::{ 32 ty::{
30 method_resolution::{self, implements_trait}, 33 method_resolution::{self, implements_trait},
31 InEnvironment, TraitEnvironment, Ty, 34 InEnvironment, TraitEnvironment, Ty,
@@ -91,7 +94,7 @@ pub struct SourceAnalyzer {
91 body_owner: Option<DefWithBody>, 94 body_owner: Option<DefWithBody>,
92 body_source_map: Option<Arc<BodySourceMap>>, 95 body_source_map: Option<Arc<BodySourceMap>>,
93 infer: Option<Arc<crate::ty::InferenceResult>>, 96 infer: Option<Arc<crate::ty::InferenceResult>>,
94 scopes: Option<Arc<crate::expr::ExprScopes>>, 97 scopes: Option<Arc<ExprScopes>>,
95} 98}
96 99
97#[derive(Debug, Clone, PartialEq, Eq)] 100#[derive(Debug, Clone, PartialEq, Eq)]
@@ -455,21 +458,6 @@ impl SourceAnalyzer {
455 macro_file_kind: to_macro_file_kind(macro_call.value), 458 macro_file_kind: to_macro_file_kind(macro_call.value),
456 }) 459 })
457 } 460 }
458
459 #[cfg(test)]
460 pub(crate) fn body_source_map(&self) -> Arc<BodySourceMap> {
461 self.body_source_map.clone().unwrap()
462 }
463
464 #[cfg(test)]
465 pub(crate) fn inference_result(&self) -> Arc<crate::ty::InferenceResult> {
466 self.infer.clone().unwrap()
467 }
468
469 #[cfg(test)]
470 pub(crate) fn analyzed_declaration(&self) -> Option<DefWithBody> {
471 self.body_owner
472 }
473} 461}
474 462
475fn scope_for( 463fn scope_for(
diff --git a/crates/ra_hir/src/test_db.rs b/crates/ra_hir/src/test_db.rs
deleted file mode 100644
index a2071f71c..000000000
--- a/crates/ra_hir/src/test_db.rs
+++ /dev/null
@@ -1,123 +0,0 @@
1//! Database used for testing `hir`.
2
3use std::{panic, sync::Arc};
4
5use hir_def::{db::DefDatabase, ModuleId};
6use hir_expand::diagnostics::DiagnosticSink;
7use parking_lot::Mutex;
8use ra_db::{salsa, CrateId, FileId, FileLoader, FileLoaderDelegate, RelativePath, SourceDatabase};
9
10use crate::{db, debug::HirDebugHelper};
11
12#[salsa::database(
13 ra_db::SourceDatabaseExtStorage,
14 ra_db::SourceDatabaseStorage,
15 db::InternDatabaseStorage,
16 db::AstDatabaseStorage,
17 db::DefDatabaseStorage,
18 db::HirDatabaseStorage
19)]
20#[derive(Debug, Default)]
21pub struct TestDB {
22 events: Mutex<Option<Vec<salsa::Event<TestDB>>>>,
23 runtime: salsa::Runtime<TestDB>,
24}
25
26impl salsa::Database for TestDB {
27 fn salsa_runtime(&self) -> &salsa::Runtime<TestDB> {
28 &self.runtime
29 }
30
31 fn salsa_runtime_mut(&mut self) -> &mut salsa::Runtime<Self> {
32 &mut self.runtime
33 }
34
35 fn salsa_event(&self, event: impl Fn() -> salsa::Event<TestDB>) {
36 let mut events = self.events.lock();
37 if let Some(events) = &mut *events {
38 events.push(event());
39 }
40 }
41}
42
43impl salsa::ParallelDatabase for TestDB {
44 fn snapshot(&self) -> salsa::Snapshot<TestDB> {
45 salsa::Snapshot::new(TestDB {
46 events: Default::default(),
47 runtime: self.runtime.snapshot(self),
48 })
49 }
50}
51
52impl panic::RefUnwindSafe for TestDB {}
53
54impl FileLoader for TestDB {
55 fn file_text(&self, file_id: FileId) -> Arc<String> {
56 FileLoaderDelegate(self).file_text(file_id)
57 }
58 fn resolve_relative_path(
59 &self,
60 anchor: FileId,
61 relative_path: &RelativePath,
62 ) -> Option<FileId> {
63 FileLoaderDelegate(self).resolve_relative_path(anchor, relative_path)
64 }
65 fn relevant_crates(&self, file_id: FileId) -> Arc<Vec<CrateId>> {
66 FileLoaderDelegate(self).relevant_crates(file_id)
67 }
68}
69
70// FIXME: improve `WithFixture` to bring useful hir debugging back
71impl HirDebugHelper for TestDB {
72 fn crate_name(&self, _krate: CrateId) -> Option<String> {
73 None
74 }
75
76 fn file_path(&self, _file_id: FileId) -> Option<String> {
77 None
78 }
79}
80
81impl TestDB {
82 pub fn diagnostics(&self) -> String {
83 let mut buf = String::new();
84 let crate_graph = self.crate_graph();
85 for krate in crate_graph.iter().next() {
86 let crate_def_map = self.crate_def_map(krate);
87 for (module_id, _) in crate_def_map.modules.iter() {
88 let module_id = ModuleId { krate, module_id };
89 let module = crate::Module::from(module_id);
90 module.diagnostics(
91 self,
92 &mut DiagnosticSink::new(|d| {
93 buf += &format!("{:?}: {}\n", d.syntax_node(self).text(), d.message());
94 }),
95 )
96 }
97 }
98 buf
99 }
100}
101
102impl TestDB {
103 pub fn log(&self, f: impl FnOnce()) -> Vec<salsa::Event<TestDB>> {
104 *self.events.lock() = Some(Vec::new());
105 f();
106 self.events.lock().take().unwrap()
107 }
108
109 pub fn log_executed(&self, f: impl FnOnce()) -> Vec<String> {
110 let events = self.log(f);
111 events
112 .into_iter()
113 .filter_map(|e| match e.kind {
114 // This pretty horrible, but `Debug` is the only way to inspect
115 // QueryDescriptor at the moment.
116 salsa::EventKind::WillExecute { database_key } => {
117 Some(format!("{:?}", database_key))
118 }
119 _ => None,
120 })
121 .collect()
122 }
123}
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index e4ba8afa6..4ed69c00d 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -1,1113 +1,4 @@
1//! The type system. We currently use this to infer types for completion, hover 1//! The type system. We currently use this to infer types for completion, hover
2//! information and various assists. 2//! information and various assists.
3 3
4mod autoderef; 4pub use hir_ty::*;
5pub(crate) mod primitive;
6pub(crate) mod traits;
7pub(crate) mod method_resolution;
8mod op;
9mod lower;
10mod infer;
11pub(crate) mod display;
12pub(crate) mod utils;
13
14#[cfg(test)]
15mod tests;
16
17use std::ops::Deref;
18use std::sync::Arc;
19use std::{fmt, iter, mem};
20
21use hir_def::{
22 expr::ExprId, generics::GenericParams, type_ref::Mutability, AdtId, ContainerId, DefWithBodyId,
23 GenericDefId, HasModule, Lookup, TraitId, TypeAliasId,
24};
25use hir_expand::name::Name;
26use ra_db::{impl_intern_key, salsa, CrateId};
27
28use crate::{
29 db::HirDatabase,
30 ty::primitive::{FloatTy, IntTy, Uncertain},
31 util::make_mut_slice,
32};
33use display::{HirDisplay, HirFormatter};
34
35pub(crate) use autoderef::autoderef;
36pub(crate) use infer::{infer_query, InferTy, InferenceResult};
37pub use lower::CallableDef;
38pub(crate) use lower::{
39 callable_item_sig, field_types_query, generic_defaults_query,
40 generic_predicates_for_param_query, generic_predicates_query, ty_query, value_ty_query,
41 TyDefId, ValueTyDefId,
42};
43pub(crate) use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
44
45/// A type constructor or type name: this might be something like the primitive
46/// type `bool`, a struct like `Vec`, or things like function pointers or
47/// tuples.
48#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
49pub enum TypeCtor {
50 /// The primitive boolean type. Written as `bool`.
51 Bool,
52
53 /// The primitive character type; holds a Unicode scalar value
54 /// (a non-surrogate code point). Written as `char`.
55 Char,
56
57 /// A primitive integer type. For example, `i32`.
58 Int(Uncertain<IntTy>),
59
60 /// A primitive floating-point type. For example, `f64`.
61 Float(Uncertain<FloatTy>),
62
63 /// Structures, enumerations and unions.
64 Adt(AdtId),
65
66 /// The pointee of a string slice. Written as `str`.
67 Str,
68
69 /// The pointee of an array slice. Written as `[T]`.
70 Slice,
71
72 /// An array with the given length. Written as `[T; n]`.
73 Array,
74
75 /// A raw pointer. Written as `*mut T` or `*const T`
76 RawPtr(Mutability),
77
78 /// A reference; a pointer with an associated lifetime. Written as
79 /// `&'a mut T` or `&'a T`.
80 Ref(Mutability),
81
82 /// The anonymous type of a function declaration/definition. Each
83 /// function has a unique type, which is output (for a function
84 /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
85 ///
86 /// This includes tuple struct / enum variant constructors as well.
87 ///
88 /// For example the type of `bar` here:
89 ///
90 /// ```
91 /// fn foo() -> i32 { 1 }
92 /// let bar = foo; // bar: fn() -> i32 {foo}
93 /// ```
94 FnDef(CallableDef),
95
96 /// A pointer to a function. Written as `fn() -> i32`.
97 ///
98 /// For example the type of `bar` here:
99 ///
100 /// ```
101 /// fn foo() -> i32 { 1 }
102 /// let bar: fn() -> i32 = foo;
103 /// ```
104 FnPtr { num_args: u16 },
105
106 /// The never type `!`.
107 Never,
108
109 /// A tuple type. For example, `(i32, bool)`.
110 Tuple { cardinality: u16 },
111
112 /// Represents an associated item like `Iterator::Item`. This is used
113 /// when we have tried to normalize a projection like `T::Item` but
114 /// couldn't find a better representation. In that case, we generate
115 /// an **application type** like `(Iterator::Item)<T>`.
116 AssociatedType(TypeAliasId),
117
118 /// The type of a specific closure.
119 ///
120 /// The closure signature is stored in a `FnPtr` type in the first type
121 /// parameter.
122 Closure { def: DefWithBodyId, expr: ExprId },
123}
124
125/// This exists just for Chalk, because Chalk just has a single `StructId` where
126/// we have different kinds of ADTs, primitive types and special type
127/// constructors like tuples and function pointers.
128#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
129pub struct TypeCtorId(salsa::InternId);
130impl_intern_key!(TypeCtorId);
131
132impl TypeCtor {
133 pub fn num_ty_params(self, db: &impl HirDatabase) -> usize {
134 match self {
135 TypeCtor::Bool
136 | TypeCtor::Char
137 | TypeCtor::Int(_)
138 | TypeCtor::Float(_)
139 | TypeCtor::Str
140 | TypeCtor::Never => 0,
141 TypeCtor::Slice
142 | TypeCtor::Array
143 | TypeCtor::RawPtr(_)
144 | TypeCtor::Ref(_)
145 | TypeCtor::Closure { .. } // 1 param representing the signature of the closure
146 => 1,
147 TypeCtor::Adt(adt) => {
148 let generic_params = db.generic_params(AdtId::from(adt).into());
149 generic_params.count_params_including_parent()
150 }
151 TypeCtor::FnDef(callable) => {
152 let generic_params = db.generic_params(callable.into());
153 generic_params.count_params_including_parent()
154 }
155 TypeCtor::AssociatedType(type_alias) => {
156 let generic_params = db.generic_params(type_alias.into());
157 generic_params.count_params_including_parent()
158 }
159 TypeCtor::FnPtr { num_args } => num_args as usize + 1,
160 TypeCtor::Tuple { cardinality } => cardinality as usize,
161 }
162 }
163
164 pub fn krate(self, db: &impl HirDatabase) -> Option<CrateId> {
165 match self {
166 TypeCtor::Bool
167 | TypeCtor::Char
168 | TypeCtor::Int(_)
169 | TypeCtor::Float(_)
170 | TypeCtor::Str
171 | TypeCtor::Never
172 | TypeCtor::Slice
173 | TypeCtor::Array
174 | TypeCtor::RawPtr(_)
175 | TypeCtor::Ref(_)
176 | TypeCtor::FnPtr { .. }
177 | TypeCtor::Tuple { .. } => None,
178 // Closure's krate is irrelevant for coherence I would think?
179 TypeCtor::Closure { .. } => None,
180 TypeCtor::Adt(adt) => Some(adt.module(db).krate),
181 TypeCtor::FnDef(callable) => Some(callable.krate(db)),
182 TypeCtor::AssociatedType(type_alias) => Some(type_alias.lookup(db).module(db).krate),
183 }
184 }
185
186 pub fn as_generic_def(self) -> Option<GenericDefId> {
187 match self {
188 TypeCtor::Bool
189 | TypeCtor::Char
190 | TypeCtor::Int(_)
191 | TypeCtor::Float(_)
192 | TypeCtor::Str
193 | TypeCtor::Never
194 | TypeCtor::Slice
195 | TypeCtor::Array
196 | TypeCtor::RawPtr(_)
197 | TypeCtor::Ref(_)
198 | TypeCtor::FnPtr { .. }
199 | TypeCtor::Tuple { .. }
200 | TypeCtor::Closure { .. } => None,
201 TypeCtor::Adt(adt) => Some(adt.into()),
202 TypeCtor::FnDef(callable) => Some(callable.into()),
203 TypeCtor::AssociatedType(type_alias) => Some(type_alias.into()),
204 }
205 }
206}
207
208/// A nominal type with (maybe 0) type parameters. This might be a primitive
209/// type like `bool`, a struct, tuple, function pointer, reference or
210/// several other things.
211#[derive(Clone, PartialEq, Eq, Debug, Hash)]
212pub struct ApplicationTy {
213 pub ctor: TypeCtor,
214 pub parameters: Substs,
215}
216
217/// A "projection" type corresponds to an (unnormalized)
218/// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
219/// trait and all its parameters are fully known.
220#[derive(Clone, PartialEq, Eq, Debug, Hash)]
221pub struct ProjectionTy {
222 pub associated_ty: TypeAliasId,
223 pub parameters: Substs,
224}
225
226impl ProjectionTy {
227 pub fn trait_ref(&self, db: &impl HirDatabase) -> TraitRef {
228 TraitRef { trait_: self.trait_(db).into(), substs: self.parameters.clone() }
229 }
230
231 fn trait_(&self, db: &impl HirDatabase) -> TraitId {
232 match self.associated_ty.lookup(db).container {
233 ContainerId::TraitId(it) => it,
234 _ => panic!("projection ty without parent trait"),
235 }
236 }
237}
238
239impl TypeWalk for ProjectionTy {
240 fn walk(&self, f: &mut impl FnMut(&Ty)) {
241 self.parameters.walk(f);
242 }
243
244 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
245 self.parameters.walk_mut_binders(f, binders);
246 }
247}
248
249/// A type.
250///
251/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
252/// the same thing (but in a different way).
253///
254/// This should be cheap to clone.
255#[derive(Clone, PartialEq, Eq, Debug, Hash)]
256pub enum Ty {
257 /// A nominal type with (maybe 0) type parameters. This might be a primitive
258 /// type like `bool`, a struct, tuple, function pointer, reference or
259 /// several other things.
260 Apply(ApplicationTy),
261
262 /// A "projection" type corresponds to an (unnormalized)
263 /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
264 /// trait and all its parameters are fully known.
265 Projection(ProjectionTy),
266
267 /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
268 Param {
269 /// The index of the parameter (starting with parameters from the
270 /// surrounding impl, then the current function).
271 idx: u32,
272 /// The name of the parameter, for displaying.
273 // FIXME get rid of this
274 name: Name,
275 },
276
277 /// A bound type variable. Used during trait resolution to represent Chalk
278 /// variables, and in `Dyn` and `Opaque` bounds to represent the `Self` type.
279 Bound(u32),
280
281 /// A type variable used during type checking. Not to be confused with a
282 /// type parameter.
283 Infer(InferTy),
284
285 /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
286 ///
287 /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
288 /// represents the `Self` type inside the bounds. This is currently
289 /// implicit; Chalk has the `Binders` struct to make it explicit, but it
290 /// didn't seem worth the overhead yet.
291 Dyn(Arc<[GenericPredicate]>),
292
293 /// An opaque type (`impl Trait`).
294 ///
295 /// The predicates are quantified over the `Self` type; see `Ty::Dyn` for
296 /// more.
297 Opaque(Arc<[GenericPredicate]>),
298
299 /// A placeholder for a type which could not be computed; this is propagated
300 /// to avoid useless error messages. Doubles as a placeholder where type
301 /// variables are inserted before type checking, since we want to try to
302 /// infer a better type here anyway -- for the IDE use case, we want to try
303 /// to infer as much as possible even in the presence of type errors.
304 Unknown,
305}
306
307/// A list of substitutions for generic parameters.
308#[derive(Clone, PartialEq, Eq, Debug, Hash)]
309pub struct Substs(Arc<[Ty]>);
310
311impl TypeWalk for Substs {
312 fn walk(&self, f: &mut impl FnMut(&Ty)) {
313 for t in self.0.iter() {
314 t.walk(f);
315 }
316 }
317
318 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
319 for t in make_mut_slice(&mut self.0) {
320 t.walk_mut_binders(f, binders);
321 }
322 }
323}
324
325impl Substs {
326 pub fn empty() -> Substs {
327 Substs(Arc::new([]))
328 }
329
330 pub fn single(ty: Ty) -> Substs {
331 Substs(Arc::new([ty]))
332 }
333
334 pub fn prefix(&self, n: usize) -> Substs {
335 Substs(self.0[..std::cmp::min(self.0.len(), n)].into())
336 }
337
338 pub fn as_single(&self) -> &Ty {
339 if self.0.len() != 1 {
340 panic!("expected substs of len 1, got {:?}", self);
341 }
342 &self.0[0]
343 }
344
345 /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
346 pub fn identity(generic_params: &GenericParams) -> Substs {
347 Substs(
348 generic_params
349 .params_including_parent()
350 .into_iter()
351 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
352 .collect(),
353 )
354 }
355
356 /// Return Substs that replace each parameter by a bound variable.
357 pub fn bound_vars(generic_params: &GenericParams) -> Substs {
358 Substs(
359 generic_params
360 .params_including_parent()
361 .into_iter()
362 .map(|p| Ty::Bound(p.idx))
363 .collect(),
364 )
365 }
366
367 pub fn build_for_def(db: &impl HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder {
368 let def = def.into();
369 let params = db.generic_params(def);
370 let param_count = params.count_params_including_parent();
371 Substs::builder(param_count)
372 }
373
374 pub fn build_for_generics(generic_params: &GenericParams) -> SubstsBuilder {
375 Substs::builder(generic_params.count_params_including_parent())
376 }
377
378 pub fn build_for_type_ctor(db: &impl HirDatabase, type_ctor: TypeCtor) -> SubstsBuilder {
379 Substs::builder(type_ctor.num_ty_params(db))
380 }
381
382 fn builder(param_count: usize) -> SubstsBuilder {
383 SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
384 }
385}
386
387#[derive(Debug, Clone)]
388pub struct SubstsBuilder {
389 vec: Vec<Ty>,
390 param_count: usize,
391}
392
393impl SubstsBuilder {
394 pub fn build(self) -> Substs {
395 assert_eq!(self.vec.len(), self.param_count);
396 Substs(self.vec.into())
397 }
398
399 pub fn push(mut self, ty: Ty) -> Self {
400 self.vec.push(ty);
401 self
402 }
403
404 fn remaining(&self) -> usize {
405 self.param_count - self.vec.len()
406 }
407
408 pub fn fill_with_bound_vars(self, starting_from: u32) -> Self {
409 self.fill((starting_from..).map(Ty::Bound))
410 }
411
412 pub fn fill_with_params(self) -> Self {
413 let start = self.vec.len() as u32;
414 self.fill((start..).map(|idx| Ty::Param { idx, name: Name::missing() }))
415 }
416
417 pub fn fill_with_unknown(self) -> Self {
418 self.fill(iter::repeat(Ty::Unknown))
419 }
420
421 pub fn fill(mut self, filler: impl Iterator<Item = Ty>) -> Self {
422 self.vec.extend(filler.take(self.remaining()));
423 assert_eq!(self.remaining(), 0);
424 self
425 }
426
427 pub fn use_parent_substs(mut self, parent_substs: &Substs) -> Self {
428 assert!(self.vec.is_empty());
429 assert!(parent_substs.len() <= self.param_count);
430 self.vec.extend(parent_substs.iter().cloned());
431 self
432 }
433}
434
435impl Deref for Substs {
436 type Target = [Ty];
437
438 fn deref(&self) -> &[Ty] {
439 &self.0
440 }
441}
442
443/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
444/// Name to be bikeshedded: TraitBound? TraitImplements?
445#[derive(Clone, PartialEq, Eq, Debug, Hash)]
446pub struct TraitRef {
447 /// FIXME name?
448 pub trait_: TraitId,
449 pub substs: Substs,
450}
451
452impl TraitRef {
453 pub fn self_ty(&self) -> &Ty {
454 &self.substs[0]
455 }
456}
457
458impl TypeWalk for TraitRef {
459 fn walk(&self, f: &mut impl FnMut(&Ty)) {
460 self.substs.walk(f);
461 }
462
463 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
464 self.substs.walk_mut_binders(f, binders);
465 }
466}
467
468/// Like `generics::WherePredicate`, but with resolved types: A condition on the
469/// parameters of a generic item.
470#[derive(Debug, Clone, PartialEq, Eq, Hash)]
471pub enum GenericPredicate {
472 /// The given trait needs to be implemented for its type parameters.
473 Implemented(TraitRef),
474 /// An associated type bindings like in `Iterator<Item = T>`.
475 Projection(ProjectionPredicate),
476 /// We couldn't resolve the trait reference. (If some type parameters can't
477 /// be resolved, they will just be Unknown).
478 Error,
479}
480
481impl GenericPredicate {
482 pub fn is_error(&self) -> bool {
483 match self {
484 GenericPredicate::Error => true,
485 _ => false,
486 }
487 }
488
489 pub fn is_implemented(&self) -> bool {
490 match self {
491 GenericPredicate::Implemented(_) => true,
492 _ => false,
493 }
494 }
495
496 pub fn trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
497 match self {
498 GenericPredicate::Implemented(tr) => Some(tr.clone()),
499 GenericPredicate::Projection(proj) => Some(proj.projection_ty.trait_ref(db)),
500 GenericPredicate::Error => None,
501 }
502 }
503}
504
505impl TypeWalk for GenericPredicate {
506 fn walk(&self, f: &mut impl FnMut(&Ty)) {
507 match self {
508 GenericPredicate::Implemented(trait_ref) => trait_ref.walk(f),
509 GenericPredicate::Projection(projection_pred) => projection_pred.walk(f),
510 GenericPredicate::Error => {}
511 }
512 }
513
514 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
515 match self {
516 GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
517 GenericPredicate::Projection(projection_pred) => {
518 projection_pred.walk_mut_binders(f, binders)
519 }
520 GenericPredicate::Error => {}
521 }
522 }
523}
524
525/// Basically a claim (currently not validated / checked) that the contained
526/// type / trait ref contains no inference variables; any inference variables it
527/// contained have been replaced by bound variables, and `num_vars` tells us how
528/// many there are. This is used to erase irrelevant differences between types
529/// before using them in queries.
530#[derive(Debug, Clone, PartialEq, Eq, Hash)]
531pub struct Canonical<T> {
532 pub value: T,
533 pub num_vars: usize,
534}
535
536/// A function signature as seen by type inference: Several parameter types and
537/// one return type.
538#[derive(Clone, PartialEq, Eq, Debug)]
539pub struct FnSig {
540 params_and_return: Arc<[Ty]>,
541}
542
543impl FnSig {
544 pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty) -> FnSig {
545 params.push(ret);
546 FnSig { params_and_return: params.into() }
547 }
548
549 pub fn from_fn_ptr_substs(substs: &Substs) -> FnSig {
550 FnSig { params_and_return: Arc::clone(&substs.0) }
551 }
552
553 pub fn params(&self) -> &[Ty] {
554 &self.params_and_return[0..self.params_and_return.len() - 1]
555 }
556
557 pub fn ret(&self) -> &Ty {
558 &self.params_and_return[self.params_and_return.len() - 1]
559 }
560}
561
562impl TypeWalk for FnSig {
563 fn walk(&self, f: &mut impl FnMut(&Ty)) {
564 for t in self.params_and_return.iter() {
565 t.walk(f);
566 }
567 }
568
569 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
570 for t in make_mut_slice(&mut self.params_and_return) {
571 t.walk_mut_binders(f, binders);
572 }
573 }
574}
575
576impl Ty {
577 pub fn simple(ctor: TypeCtor) -> Ty {
578 Ty::Apply(ApplicationTy { ctor, parameters: Substs::empty() })
579 }
580 pub fn apply_one(ctor: TypeCtor, param: Ty) -> Ty {
581 Ty::Apply(ApplicationTy { ctor, parameters: Substs::single(param) })
582 }
583 pub fn apply(ctor: TypeCtor, parameters: Substs) -> Ty {
584 Ty::Apply(ApplicationTy { ctor, parameters })
585 }
586 pub fn unit() -> Self {
587 Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
588 }
589
590 pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
591 match self {
592 Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
593 Some((parameters.as_single(), *mutability))
594 }
595 _ => None,
596 }
597 }
598
599 pub fn as_adt(&self) -> Option<(AdtId, &Substs)> {
600 match self {
601 Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(adt_def), parameters }) => {
602 Some((*adt_def, parameters))
603 }
604 _ => None,
605 }
606 }
607
608 pub fn as_tuple(&self) -> Option<&Substs> {
609 match self {
610 Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
611 Some(parameters)
612 }
613 _ => None,
614 }
615 }
616
617 pub fn as_callable(&self) -> Option<(CallableDef, &Substs)> {
618 match self {
619 Ty::Apply(ApplicationTy { ctor: TypeCtor::FnDef(callable_def), parameters }) => {
620 Some((*callable_def, parameters))
621 }
622 _ => None,
623 }
624 }
625
626 fn builtin_deref(&self) -> Option<Ty> {
627 match self {
628 Ty::Apply(a_ty) => match a_ty.ctor {
629 TypeCtor::Ref(..) => Some(Ty::clone(a_ty.parameters.as_single())),
630 TypeCtor::RawPtr(..) => Some(Ty::clone(a_ty.parameters.as_single())),
631 _ => None,
632 },
633 _ => None,
634 }
635 }
636
637 fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> {
638 match self {
639 Ty::Apply(a_ty) => match a_ty.ctor {
640 TypeCtor::FnPtr { .. } => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)),
641 TypeCtor::FnDef(def) => {
642 let sig = db.callable_item_signature(def);
643 Some(sig.subst(&a_ty.parameters))
644 }
645 TypeCtor::Closure { .. } => {
646 let sig_param = &a_ty.parameters[0];
647 sig_param.callable_sig(db)
648 }
649 _ => None,
650 },
651 _ => None,
652 }
653 }
654
655 /// If this is a type with type parameters (an ADT or function), replaces
656 /// the `Substs` for these type parameters with the given ones. (So e.g. if
657 /// `self` is `Option<_>` and the substs contain `u32`, we'll have
658 /// `Option<u32>` afterwards.)
659 pub fn apply_substs(self, substs: Substs) -> Ty {
660 match self {
661 Ty::Apply(ApplicationTy { ctor, parameters: previous_substs }) => {
662 assert_eq!(previous_substs.len(), substs.len());
663 Ty::Apply(ApplicationTy { ctor, parameters: substs })
664 }
665 _ => self,
666 }
667 }
668
669 /// Returns the type parameters of this type if it has some (i.e. is an ADT
670 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
671 pub fn substs(&self) -> Option<Substs> {
672 match self {
673 Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
674 _ => None,
675 }
676 }
677
678 /// If this is an `impl Trait` or `dyn Trait`, returns that trait.
679 pub fn inherent_trait(&self) -> Option<TraitId> {
680 match self {
681 Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
682 predicates.iter().find_map(|pred| match pred {
683 GenericPredicate::Implemented(tr) => Some(tr.trait_),
684 _ => None,
685 })
686 }
687 _ => None,
688 }
689 }
690}
691
692/// This allows walking structures that contain types to do something with those
693/// types, similar to Chalk's `Fold` trait.
694pub trait TypeWalk {
695 fn walk(&self, f: &mut impl FnMut(&Ty));
696 fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
697 self.walk_mut_binders(&mut |ty, _binders| f(ty), 0);
698 }
699 /// Walk the type, counting entered binders.
700 ///
701 /// `Ty::Bound` variables use DeBruijn indexing, which means that 0 refers
702 /// to the innermost binder, 1 to the next, etc.. So when we want to
703 /// substitute a certain bound variable, we can't just walk the whole type
704 /// and blindly replace each instance of a certain index; when we 'enter'
705 /// things that introduce new bound variables, we have to keep track of
706 /// that. Currently, the only thing that introduces bound variables on our
707 /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
708 /// variable for the self type.
709 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize);
710
711 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
712 where
713 Self: Sized,
714 {
715 self.walk_mut(&mut |ty_mut| {
716 let ty = mem::replace(ty_mut, Ty::Unknown);
717 *ty_mut = f(ty);
718 });
719 self
720 }
721
722 /// Replaces type parameters in this type using the given `Substs`. (So e.g.
723 /// if `self` is `&[T]`, where type parameter T has index 0, and the
724 /// `Substs` contain `u32` at index 0, we'll have `&[u32]` afterwards.)
725 fn subst(self, substs: &Substs) -> Self
726 where
727 Self: Sized,
728 {
729 self.fold(&mut |ty| match ty {
730 Ty::Param { idx, name } => {
731 substs.get(idx as usize).cloned().unwrap_or(Ty::Param { idx, name })
732 }
733 ty => ty,
734 })
735 }
736
737 /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
738 fn subst_bound_vars(mut self, substs: &Substs) -> Self
739 where
740 Self: Sized,
741 {
742 self.walk_mut_binders(
743 &mut |ty, binders| match ty {
744 &mut Ty::Bound(idx) => {
745 if idx as usize >= binders && (idx as usize - binders) < substs.len() {
746 *ty = substs.0[idx as usize - binders].clone();
747 }
748 }
749 _ => {}
750 },
751 0,
752 );
753 self
754 }
755
756 /// Shifts up `Ty::Bound` vars by `n`.
757 fn shift_bound_vars(self, n: i32) -> Self
758 where
759 Self: Sized,
760 {
761 self.fold(&mut |ty| match ty {
762 Ty::Bound(idx) => {
763 assert!(idx as i32 >= -n);
764 Ty::Bound((idx as i32 + n) as u32)
765 }
766 ty => ty,
767 })
768 }
769}
770
771impl TypeWalk for Ty {
772 fn walk(&self, f: &mut impl FnMut(&Ty)) {
773 match self {
774 Ty::Apply(a_ty) => {
775 for t in a_ty.parameters.iter() {
776 t.walk(f);
777 }
778 }
779 Ty::Projection(p_ty) => {
780 for t in p_ty.parameters.iter() {
781 t.walk(f);
782 }
783 }
784 Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
785 for p in predicates.iter() {
786 p.walk(f);
787 }
788 }
789 Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
790 }
791 f(self);
792 }
793
794 fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
795 match self {
796 Ty::Apply(a_ty) => {
797 a_ty.parameters.walk_mut_binders(f, binders);
798 }
799 Ty::Projection(p_ty) => {
800 p_ty.parameters.walk_mut_binders(f, binders);
801 }
802 Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
803 for p in make_mut_slice(predicates) {
804 p.walk_mut_binders(f, binders + 1);
805 }
806 }
807 Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
808 }
809 f(self, binders);
810 }
811}
812
813impl HirDisplay for &Ty {
814 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
815 HirDisplay::hir_fmt(*self, f)
816 }
817}
818
819impl HirDisplay for ApplicationTy {
820 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
821 if f.should_truncate() {
822 return write!(f, "…");
823 }
824
825 match self.ctor {
826 TypeCtor::Bool => write!(f, "bool")?,
827 TypeCtor::Char => write!(f, "char")?,
828 TypeCtor::Int(t) => write!(f, "{}", t)?,
829 TypeCtor::Float(t) => write!(f, "{}", t)?,
830 TypeCtor::Str => write!(f, "str")?,
831 TypeCtor::Slice => {
832 let t = self.parameters.as_single();
833 write!(f, "[{}]", t.display(f.db))?;
834 }
835 TypeCtor::Array => {
836 let t = self.parameters.as_single();
837 write!(f, "[{};_]", t.display(f.db))?;
838 }
839 TypeCtor::RawPtr(m) => {
840 let t = self.parameters.as_single();
841 write!(f, "*{}{}", m.as_keyword_for_ptr(), t.display(f.db))?;
842 }
843 TypeCtor::Ref(m) => {
844 let t = self.parameters.as_single();
845 write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?;
846 }
847 TypeCtor::Never => write!(f, "!")?,
848 TypeCtor::Tuple { .. } => {
849 let ts = &self.parameters;
850 if ts.len() == 1 {
851 write!(f, "({},)", ts[0].display(f.db))?;
852 } else {
853 write!(f, "(")?;
854 f.write_joined(&*ts.0, ", ")?;
855 write!(f, ")")?;
856 }
857 }
858 TypeCtor::FnPtr { .. } => {
859 let sig = FnSig::from_fn_ptr_substs(&self.parameters);
860 write!(f, "fn(")?;
861 f.write_joined(sig.params(), ", ")?;
862 write!(f, ") -> {}", sig.ret().display(f.db))?;
863 }
864 TypeCtor::FnDef(def) => {
865 let sig = f.db.callable_item_signature(def);
866 let name = match def {
867 CallableDef::FunctionId(ff) => f.db.function_data(ff).name.clone(),
868 CallableDef::StructId(s) => {
869 f.db.struct_data(s).name.clone().unwrap_or_else(Name::missing)
870 }
871 CallableDef::EnumVariantId(e) => {
872 let enum_data = f.db.enum_data(e.parent);
873 enum_data.variants[e.local_id].name.clone().unwrap_or_else(Name::missing)
874 }
875 };
876 match def {
877 CallableDef::FunctionId(_) => write!(f, "fn {}", name)?,
878 CallableDef::StructId(_) | CallableDef::EnumVariantId(_) => {
879 write!(f, "{}", name)?
880 }
881 }
882 if self.parameters.len() > 0 {
883 write!(f, "<")?;
884 f.write_joined(&*self.parameters.0, ", ")?;
885 write!(f, ">")?;
886 }
887 write!(f, "(")?;
888 f.write_joined(sig.params(), ", ")?;
889 write!(f, ") -> {}", sig.ret().display(f.db))?;
890 }
891 TypeCtor::Adt(def_id) => {
892 let name = match def_id {
893 AdtId::StructId(it) => f.db.struct_data(it).name.clone(),
894 AdtId::UnionId(it) => f.db.union_data(it).name.clone(),
895 AdtId::EnumId(it) => f.db.enum_data(it).name.clone(),
896 }
897 .unwrap_or_else(Name::missing);
898 write!(f, "{}", name)?;
899 if self.parameters.len() > 0 {
900 write!(f, "<")?;
901 f.write_joined(&*self.parameters.0, ", ")?;
902 write!(f, ">")?;
903 }
904 }
905 TypeCtor::AssociatedType(type_alias) => {
906 let trait_ = match type_alias.lookup(f.db).container {
907 ContainerId::TraitId(it) => it,
908 _ => panic!("not an associated type"),
909 };
910 let trait_name = f.db.trait_data(trait_).name.clone().unwrap_or_else(Name::missing);
911 let name = f.db.type_alias_data(type_alias).name.clone();
912 write!(f, "{}::{}", trait_name, name)?;
913 if self.parameters.len() > 0 {
914 write!(f, "<")?;
915 f.write_joined(&*self.parameters.0, ", ")?;
916 write!(f, ">")?;
917 }
918 }
919 TypeCtor::Closure { .. } => {
920 let sig = self.parameters[0]
921 .callable_sig(f.db)
922 .expect("first closure parameter should contain signature");
923 write!(f, "|")?;
924 f.write_joined(sig.params(), ", ")?;
925 write!(f, "| -> {}", sig.ret().display(f.db))?;
926 }
927 }
928 Ok(())
929 }
930}
931
932impl HirDisplay for ProjectionTy {
933 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
934 if f.should_truncate() {
935 return write!(f, "…");
936 }
937
938 let trait_name =
939 f.db.trait_data(self.trait_(f.db)).name.clone().unwrap_or_else(Name::missing);
940 write!(f, "<{} as {}", self.parameters[0].display(f.db), trait_name,)?;
941 if self.parameters.len() > 1 {
942 write!(f, "<")?;
943 f.write_joined(&self.parameters[1..], ", ")?;
944 write!(f, ">")?;
945 }
946 write!(f, ">::{}", f.db.type_alias_data(self.associated_ty).name)?;
947 Ok(())
948 }
949}
950
951impl HirDisplay for Ty {
952 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
953 if f.should_truncate() {
954 return write!(f, "…");
955 }
956
957 match self {
958 Ty::Apply(a_ty) => a_ty.hir_fmt(f)?,
959 Ty::Projection(p_ty) => p_ty.hir_fmt(f)?,
960 Ty::Param { name, .. } => write!(f, "{}", name)?,
961 Ty::Bound(idx) => write!(f, "?{}", idx)?,
962 Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
963 match self {
964 Ty::Dyn(_) => write!(f, "dyn ")?,
965 Ty::Opaque(_) => write!(f, "impl ")?,
966 _ => unreachable!(),
967 };
968 // Note: This code is written to produce nice results (i.e.
969 // corresponding to surface Rust) for types that can occur in
970 // actual Rust. It will have weird results if the predicates
971 // aren't as expected (i.e. self types = $0, projection
972 // predicates for a certain trait come after the Implemented
973 // predicate for that trait).
974 let mut first = true;
975 let mut angle_open = false;
976 for p in predicates.iter() {
977 match p {
978 GenericPredicate::Implemented(trait_ref) => {
979 if angle_open {
980 write!(f, ">")?;
981 }
982 if !first {
983 write!(f, " + ")?;
984 }
985 // We assume that the self type is $0 (i.e. the
986 // existential) here, which is the only thing that's
987 // possible in actual Rust, and hence don't print it
988 write!(
989 f,
990 "{}",
991 f.db.trait_data(trait_ref.trait_)
992 .name
993 .clone()
994 .unwrap_or_else(Name::missing)
995 )?;
996 if trait_ref.substs.len() > 1 {
997 write!(f, "<")?;
998 f.write_joined(&trait_ref.substs[1..], ", ")?;
999 // there might be assoc type bindings, so we leave the angle brackets open
1000 angle_open = true;
1001 }
1002 }
1003 GenericPredicate::Projection(projection_pred) => {
1004 // in types in actual Rust, these will always come
1005 // after the corresponding Implemented predicate
1006 if angle_open {
1007 write!(f, ", ")?;
1008 } else {
1009 write!(f, "<")?;
1010 angle_open = true;
1011 }
1012 let name =
1013 f.db.type_alias_data(projection_pred.projection_ty.associated_ty)
1014 .name
1015 .clone();
1016 write!(f, "{} = ", name)?;
1017 projection_pred.ty.hir_fmt(f)?;
1018 }
1019 GenericPredicate::Error => {
1020 if angle_open {
1021 // impl Trait<X, {error}>
1022 write!(f, ", ")?;
1023 } else if !first {
1024 // impl Trait + {error}
1025 write!(f, " + ")?;
1026 }
1027 p.hir_fmt(f)?;
1028 }
1029 }
1030 first = false;
1031 }
1032 if angle_open {
1033 write!(f, ">")?;
1034 }
1035 }
1036 Ty::Unknown => write!(f, "{{unknown}}")?,
1037 Ty::Infer(..) => write!(f, "_")?,
1038 }
1039 Ok(())
1040 }
1041}
1042
1043impl TraitRef {
1044 fn hir_fmt_ext(&self, f: &mut HirFormatter<impl HirDatabase>, use_as: bool) -> fmt::Result {
1045 if f.should_truncate() {
1046 return write!(f, "…");
1047 }
1048
1049 self.substs[0].hir_fmt(f)?;
1050 if use_as {
1051 write!(f, " as ")?;
1052 } else {
1053 write!(f, ": ")?;
1054 }
1055 write!(f, "{}", f.db.trait_data(self.trait_).name.clone().unwrap_or_else(Name::missing))?;
1056 if self.substs.len() > 1 {
1057 write!(f, "<")?;
1058 f.write_joined(&self.substs[1..], ", ")?;
1059 write!(f, ">")?;
1060 }
1061 Ok(())
1062 }
1063}
1064
1065impl HirDisplay for TraitRef {
1066 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
1067 self.hir_fmt_ext(f, false)
1068 }
1069}
1070
1071impl HirDisplay for &GenericPredicate {
1072 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
1073 HirDisplay::hir_fmt(*self, f)
1074 }
1075}
1076
1077impl HirDisplay for GenericPredicate {
1078 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
1079 if f.should_truncate() {
1080 return write!(f, "…");
1081 }
1082
1083 match self {
1084 GenericPredicate::Implemented(trait_ref) => trait_ref.hir_fmt(f)?,
1085 GenericPredicate::Projection(projection_pred) => {
1086 write!(f, "<")?;
1087 projection_pred.projection_ty.trait_ref(f.db).hir_fmt_ext(f, true)?;
1088 write!(
1089 f,
1090 ">::{} = {}",
1091 f.db.type_alias_data(projection_pred.projection_ty.associated_ty).name,
1092 projection_pred.ty.display(f.db)
1093 )?;
1094 }
1095 GenericPredicate::Error => write!(f, "{{error}}")?,
1096 }
1097 Ok(())
1098 }
1099}
1100
1101impl HirDisplay for Obligation {
1102 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
1103 match self {
1104 Obligation::Trait(tr) => write!(f, "Implements({})", tr.display(f.db)),
1105 Obligation::Projection(proj) => write!(
1106 f,
1107 "Normalize({} => {})",
1108 proj.projection_ty.display(f.db),
1109 proj.ty.display(f.db)
1110 ),
1111 }
1112 }
1113}
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
deleted file mode 100644
index ae68234ac..000000000
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ /dev/null
@@ -1,108 +0,0 @@
1//! In certain situations, rust automatically inserts derefs as necessary: for
2//! example, field accesses `foo.bar` still work when `foo` is actually a
3//! reference to a type with the field `bar`. This is an approximation of the
4//! logic in rustc (which lives in librustc_typeck/check/autoderef.rs).
5
6use std::iter::successors;
7
8use hir_def::lang_item::LangItemTarget;
9use hir_expand::name;
10use log::{info, warn};
11use ra_db::CrateId;
12
13use crate::db::HirDatabase;
14
15use super::{
16 traits::{InEnvironment, Solution},
17 Canonical, Substs, Ty, TypeWalk,
18};
19
20const AUTODEREF_RECURSION_LIMIT: usize = 10;
21
22pub(crate) fn autoderef<'a>(
23 db: &'a impl HirDatabase,
24 krate: Option<CrateId>,
25 ty: InEnvironment<Canonical<Ty>>,
26) -> impl Iterator<Item = Canonical<Ty>> + 'a {
27 let InEnvironment { value: ty, environment } = ty;
28 successors(Some(ty), move |ty| {
29 deref(db, krate?, InEnvironment { value: ty, environment: environment.clone() })
30 })
31 .take(AUTODEREF_RECURSION_LIMIT)
32}
33
34pub(crate) fn deref(
35 db: &impl HirDatabase,
36 krate: CrateId,
37 ty: InEnvironment<&Canonical<Ty>>,
38) -> Option<Canonical<Ty>> {
39 if let Some(derefed) = ty.value.value.builtin_deref() {
40 Some(Canonical { value: derefed, num_vars: ty.value.num_vars })
41 } else {
42 deref_by_trait(db, krate, ty)
43 }
44}
45
46fn deref_by_trait(
47 db: &impl HirDatabase,
48 krate: CrateId,
49 ty: InEnvironment<&Canonical<Ty>>,
50) -> Option<Canonical<Ty>> {
51 let deref_trait = match db.lang_item(krate.into(), "deref".into())? {
52 LangItemTarget::TraitId(it) => it,
53 _ => return None,
54 };
55 let target = db.trait_data(deref_trait).associated_type_by_name(&name::TARGET_TYPE)?;
56
57 let generic_params = db.generic_params(target.into());
58 if generic_params.count_params_including_parent() != 1 {
59 // the Target type + Deref trait should only have one generic parameter,
60 // namely Deref's Self type
61 return None;
62 }
63
64 // FIXME make the Canonical handling nicer
65
66 let parameters = Substs::build_for_generics(&generic_params)
67 .push(ty.value.value.clone().shift_bound_vars(1))
68 .build();
69
70 let projection = super::traits::ProjectionPredicate {
71 ty: Ty::Bound(0),
72 projection_ty: super::ProjectionTy { associated_ty: target, parameters },
73 };
74
75 let obligation = super::Obligation::Projection(projection);
76
77 let in_env = InEnvironment { value: obligation, environment: ty.environment };
78
79 let canonical = super::Canonical { num_vars: 1 + ty.value.num_vars, value: in_env };
80
81 let solution = db.trait_solve(krate.into(), canonical)?;
82
83 match &solution {
84 Solution::Unique(vars) => {
85 // FIXME: vars may contain solutions for any inference variables
86 // that happened to be inside ty. To correctly handle these, we
87 // would have to pass the solution up to the inference context, but
88 // that requires a larger refactoring (especially if the deref
89 // happens during method resolution). So for the moment, we just
90 // check that we're not in the situation we're we would actually
91 // need to handle the values of the additional variables, i.e.
92 // they're just being 'passed through'. In the 'standard' case where
93 // we have `impl<T> Deref for Foo<T> { Target = T }`, that should be
94 // the case.
95 for i in 1..vars.0.num_vars {
96 if vars.0.value[i] != Ty::Bound((i - 1) as u32) {
97 warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.value, solution);
98 return None;
99 }
100 }
101 Some(Canonical { value: vars.0.value[0].clone(), num_vars: vars.0.num_vars })
102 }
103 Solution::Ambig(_) => {
104 info!("Ambiguous solution for derefing {:?}: {:?}", ty.value, solution);
105 None
106 }
107 }
108}
diff --git a/crates/ra_hir/src/ty/display.rs b/crates/ra_hir/src/ty/display.rs
deleted file mode 100644
index 9bb3ece6c..000000000
--- a/crates/ra_hir/src/ty/display.rs
+++ /dev/null
@@ -1,93 +0,0 @@
1//! FIXME: write short doc here
2
3use std::fmt;
4
5use crate::db::HirDatabase;
6
7pub struct HirFormatter<'a, 'b, DB> {
8 pub db: &'a DB,
9 fmt: &'a mut fmt::Formatter<'b>,
10 buf: String,
11 curr_size: usize,
12 max_size: Option<usize>,
13}
14
15pub trait HirDisplay {
16 fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result;
17
18 fn display<'a, DB>(&'a self, db: &'a DB) -> HirDisplayWrapper<'a, DB, Self>
19 where
20 Self: Sized,
21 {
22 HirDisplayWrapper(db, self, None)
23 }
24
25 fn display_truncated<'a, DB>(
26 &'a self,
27 db: &'a DB,
28 max_size: Option<usize>,
29 ) -> HirDisplayWrapper<'a, DB, Self>
30 where
31 Self: Sized,
32 {
33 HirDisplayWrapper(db, self, max_size)
34 }
35}
36
37impl<'a, 'b, DB> HirFormatter<'a, 'b, DB>
38where
39 DB: HirDatabase,
40{
41 pub fn write_joined<T: HirDisplay>(
42 &mut self,
43 iter: impl IntoIterator<Item = T>,
44 sep: &str,
45 ) -> fmt::Result {
46 let mut first = true;
47 for e in iter {
48 if !first {
49 write!(self, "{}", sep)?;
50 }
51 first = false;
52 e.hir_fmt(self)?;
53 }
54 Ok(())
55 }
56
57 /// This allows using the `write!` macro directly with a `HirFormatter`.
58 pub fn write_fmt(&mut self, args: fmt::Arguments) -> fmt::Result {
59 // We write to a buffer first to track output size
60 self.buf.clear();
61 fmt::write(&mut self.buf, args)?;
62 self.curr_size += self.buf.len();
63
64 // Then we write to the internal formatter from the buffer
65 self.fmt.write_str(&self.buf)
66 }
67
68 pub fn should_truncate(&self) -> bool {
69 if let Some(max_size) = self.max_size {
70 self.curr_size >= max_size
71 } else {
72 false
73 }
74 }
75}
76
77pub struct HirDisplayWrapper<'a, DB, T>(&'a DB, &'a T, Option<usize>);
78
79impl<'a, DB, T> fmt::Display for HirDisplayWrapper<'a, DB, T>
80where
81 DB: HirDatabase,
82 T: HirDisplay,
83{
84 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
85 self.1.hir_fmt(&mut HirFormatter {
86 db: self.0,
87 fmt: f,
88 buf: String::with_capacity(20),
89 curr_size: 0,
90 max_size: self.2,
91 })
92 }
93}
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
deleted file mode 100644
index 59e4e5f36..000000000
--- a/crates/ra_hir/src/ty/infer.rs
+++ /dev/null
@@ -1,723 +0,0 @@
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::mem;
18use std::ops::Index;
19use std::sync::Arc;
20
21use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
22use rustc_hash::FxHashMap;
23
24use hir_def::{
25 body::Body,
26 data::{ConstData, FunctionData},
27 expr::{BindingAnnotation, ExprId, PatId},
28 path::{known, Path},
29 resolver::{HasResolver, Resolver, TypeNs},
30 type_ref::{Mutability, TypeRef},
31 AdtId, AssocItemId, DefWithBodyId, FunctionId, StructFieldId, TypeAliasId, VariantId,
32};
33use hir_expand::{diagnostics::DiagnosticSink, name};
34use ra_arena::map::ArenaMap;
35use ra_prof::profile;
36use test_utils::tested_by;
37
38use super::{
39 primitive::{FloatTy, IntTy},
40 traits::{Guidance, Obligation, ProjectionPredicate, Solution},
41 ApplicationTy, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor,
42 TypeWalk, Uncertain,
43};
44use crate::{db::HirDatabase, ty::infer::diagnostics::InferenceDiagnostic};
45
46macro_rules! ty_app {
47 ($ctor:pat, $param:pat) => {
48 crate::ty::Ty::Apply(crate::ty::ApplicationTy { ctor: $ctor, parameters: $param })
49 };
50 ($ctor:pat) => {
51 ty_app!($ctor, _)
52 };
53}
54
55mod unify;
56mod path;
57mod expr;
58mod pat;
59mod coerce;
60
61/// The entry point of type inference.
62pub fn infer_query(db: &impl HirDatabase, def: DefWithBodyId) -> Arc<InferenceResult> {
63 let _p = profile("infer_query");
64 let resolver = def.resolver(db);
65 let mut ctx = InferenceContext::new(db, def, resolver);
66
67 match def {
68 DefWithBodyId::ConstId(c) => ctx.collect_const(&db.const_data(c)),
69 DefWithBodyId::FunctionId(f) => ctx.collect_fn(&db.function_data(f)),
70 DefWithBodyId::StaticId(s) => ctx.collect_const(&db.static_data(s)),
71 }
72
73 ctx.infer_body();
74
75 Arc::new(ctx.resolve_all())
76}
77
78#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
79enum ExprOrPatId {
80 ExprId(ExprId),
81 PatId(PatId),
82}
83
84impl_froms!(ExprOrPatId: ExprId, PatId);
85
86/// Binding modes inferred for patterns.
87/// https://doc.rust-lang.org/reference/patterns.html#binding-modes
88#[derive(Copy, Clone, Debug, Eq, PartialEq)]
89enum BindingMode {
90 Move,
91 Ref(Mutability),
92}
93
94impl BindingMode {
95 pub fn convert(annotation: BindingAnnotation) -> BindingMode {
96 match annotation {
97 BindingAnnotation::Unannotated | BindingAnnotation::Mutable => BindingMode::Move,
98 BindingAnnotation::Ref => BindingMode::Ref(Mutability::Shared),
99 BindingAnnotation::RefMut => BindingMode::Ref(Mutability::Mut),
100 }
101 }
102}
103
104impl Default for BindingMode {
105 fn default() -> Self {
106 BindingMode::Move
107 }
108}
109
110/// A mismatch between an expected and an inferred type.
111#[derive(Clone, PartialEq, Eq, Debug, Hash)]
112pub struct TypeMismatch {
113 pub expected: Ty,
114 pub actual: Ty,
115}
116
117/// The result of type inference: A mapping from expressions and patterns to types.
118#[derive(Clone, PartialEq, Eq, Debug, Default)]
119pub struct InferenceResult {
120 /// For each method call expr, records the function it resolves to.
121 method_resolutions: FxHashMap<ExprId, FunctionId>,
122 /// For each field access expr, records the field it resolves to.
123 field_resolutions: FxHashMap<ExprId, StructFieldId>,
124 /// For each field in record literal, records the field it resolves to.
125 record_field_resolutions: FxHashMap<ExprId, StructFieldId>,
126 /// For each struct literal, records the variant it resolves to.
127 variant_resolutions: FxHashMap<ExprOrPatId, VariantId>,
128 /// For each associated item record what it resolves to
129 assoc_resolutions: FxHashMap<ExprOrPatId, AssocItemId>,
130 diagnostics: Vec<InferenceDiagnostic>,
131 pub(super) type_of_expr: ArenaMap<ExprId, Ty>,
132 pub(super) type_of_pat: ArenaMap<PatId, Ty>,
133 pub(super) type_mismatches: ArenaMap<ExprId, TypeMismatch>,
134}
135
136impl InferenceResult {
137 pub fn method_resolution(&self, expr: ExprId) -> Option<FunctionId> {
138 self.method_resolutions.get(&expr).copied()
139 }
140 pub fn field_resolution(&self, expr: ExprId) -> Option<StructFieldId> {
141 self.field_resolutions.get(&expr).copied()
142 }
143 pub fn record_field_resolution(&self, expr: ExprId) -> Option<StructFieldId> {
144 self.record_field_resolutions.get(&expr).copied()
145 }
146 pub fn variant_resolution_for_expr(&self, id: ExprId) -> Option<VariantId> {
147 self.variant_resolutions.get(&id.into()).copied()
148 }
149 pub fn variant_resolution_for_pat(&self, id: PatId) -> Option<VariantId> {
150 self.variant_resolutions.get(&id.into()).copied()
151 }
152 pub fn assoc_resolutions_for_expr(&self, id: ExprId) -> Option<AssocItemId> {
153 self.assoc_resolutions.get(&id.into()).copied()
154 }
155 pub fn assoc_resolutions_for_pat(&self, id: PatId) -> Option<AssocItemId> {
156 self.assoc_resolutions.get(&id.into()).copied()
157 }
158 pub fn type_mismatch_for_expr(&self, expr: ExprId) -> Option<&TypeMismatch> {
159 self.type_mismatches.get(expr)
160 }
161 pub(crate) fn add_diagnostics(
162 &self,
163 db: &impl HirDatabase,
164 owner: FunctionId,
165 sink: &mut DiagnosticSink,
166 ) {
167 self.diagnostics.iter().for_each(|it| it.add_to(db, owner, sink))
168 }
169}
170
171impl Index<ExprId> for InferenceResult {
172 type Output = Ty;
173
174 fn index(&self, expr: ExprId) -> &Ty {
175 self.type_of_expr.get(expr).unwrap_or(&Ty::Unknown)
176 }
177}
178
179impl Index<PatId> for InferenceResult {
180 type Output = Ty;
181
182 fn index(&self, pat: PatId) -> &Ty {
183 self.type_of_pat.get(pat).unwrap_or(&Ty::Unknown)
184 }
185}
186
187/// The inference context contains all information needed during type inference.
188#[derive(Clone, Debug)]
189struct InferenceContext<'a, D: HirDatabase> {
190 db: &'a D,
191 owner: DefWithBodyId,
192 body: Arc<Body>,
193 resolver: Resolver,
194 var_unification_table: InPlaceUnificationTable<TypeVarId>,
195 trait_env: Arc<TraitEnvironment>,
196 obligations: Vec<Obligation>,
197 result: InferenceResult,
198 /// The return type of the function being inferred.
199 return_ty: Ty,
200
201 /// Impls of `CoerceUnsized` used in coercion.
202 /// (from_ty_ctor, to_ty_ctor) => coerce_generic_index
203 // FIXME: Use trait solver for this.
204 // Chalk seems unable to work well with builtin impl of `Unsize` now.
205 coerce_unsized_map: FxHashMap<(TypeCtor, TypeCtor), usize>,
206}
207
208impl<'a, D: HirDatabase> InferenceContext<'a, D> {
209 fn new(db: &'a D, owner: DefWithBodyId, resolver: Resolver) -> Self {
210 InferenceContext {
211 result: InferenceResult::default(),
212 var_unification_table: InPlaceUnificationTable::new(),
213 obligations: Vec::default(),
214 return_ty: Ty::Unknown, // set in collect_fn_signature
215 trait_env: TraitEnvironment::lower(db, &resolver),
216 coerce_unsized_map: Self::init_coerce_unsized_map(db, &resolver),
217 db,
218 owner,
219 body: db.body(owner.into()),
220 resolver,
221 }
222 }
223
224 fn resolve_all(mut self) -> InferenceResult {
225 // FIXME resolve obligations as well (use Guidance if necessary)
226 let mut result = mem::replace(&mut self.result, InferenceResult::default());
227 let mut tv_stack = Vec::new();
228 for ty in result.type_of_expr.values_mut() {
229 let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
230 *ty = resolved;
231 }
232 for ty in result.type_of_pat.values_mut() {
233 let resolved = self.resolve_ty_completely(&mut tv_stack, mem::replace(ty, Ty::Unknown));
234 *ty = resolved;
235 }
236 result
237 }
238
239 fn write_expr_ty(&mut self, expr: ExprId, ty: Ty) {
240 self.result.type_of_expr.insert(expr, ty);
241 }
242
243 fn write_method_resolution(&mut self, expr: ExprId, func: FunctionId) {
244 self.result.method_resolutions.insert(expr, func);
245 }
246
247 fn write_field_resolution(&mut self, expr: ExprId, field: StructFieldId) {
248 self.result.field_resolutions.insert(expr, field);
249 }
250
251 fn write_variant_resolution(&mut self, id: ExprOrPatId, variant: VariantId) {
252 self.result.variant_resolutions.insert(id, variant);
253 }
254
255 fn write_assoc_resolution(&mut self, id: ExprOrPatId, item: AssocItemId) {
256 self.result.assoc_resolutions.insert(id, item.into());
257 }
258
259 fn write_pat_ty(&mut self, pat: PatId, ty: Ty) {
260 self.result.type_of_pat.insert(pat, ty);
261 }
262
263 fn push_diagnostic(&mut self, diagnostic: InferenceDiagnostic) {
264 self.result.diagnostics.push(diagnostic);
265 }
266
267 fn make_ty(&mut self, type_ref: &TypeRef) -> Ty {
268 let ty = Ty::from_hir(
269 self.db,
270 // FIXME use right resolver for block
271 &self.resolver,
272 type_ref,
273 );
274 let ty = self.insert_type_vars(ty);
275 self.normalize_associated_types_in(ty)
276 }
277
278 fn unify_substs(&mut self, substs1: &Substs, substs2: &Substs, depth: usize) -> bool {
279 substs1.0.iter().zip(substs2.0.iter()).all(|(t1, t2)| self.unify_inner(t1, t2, depth))
280 }
281
282 fn unify(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
283 self.unify_inner(ty1, ty2, 0)
284 }
285
286 fn unify_inner(&mut self, ty1: &Ty, ty2: &Ty, depth: usize) -> bool {
287 if depth > 1000 {
288 // prevent stackoverflows
289 panic!("infinite recursion in unification");
290 }
291 if ty1 == ty2 {
292 return true;
293 }
294 // try to resolve type vars first
295 let ty1 = self.resolve_ty_shallow(ty1);
296 let ty2 = self.resolve_ty_shallow(ty2);
297 match (&*ty1, &*ty2) {
298 (Ty::Apply(a_ty1), Ty::Apply(a_ty2)) if a_ty1.ctor == a_ty2.ctor => {
299 self.unify_substs(&a_ty1.parameters, &a_ty2.parameters, depth + 1)
300 }
301 _ => self.unify_inner_trivial(&ty1, &ty2),
302 }
303 }
304
305 fn unify_inner_trivial(&mut self, ty1: &Ty, ty2: &Ty) -> bool {
306 match (ty1, ty2) {
307 (Ty::Unknown, _) | (_, Ty::Unknown) => true,
308
309 (Ty::Infer(InferTy::TypeVar(tv1)), Ty::Infer(InferTy::TypeVar(tv2)))
310 | (Ty::Infer(InferTy::IntVar(tv1)), Ty::Infer(InferTy::IntVar(tv2)))
311 | (Ty::Infer(InferTy::FloatVar(tv1)), Ty::Infer(InferTy::FloatVar(tv2)))
312 | (
313 Ty::Infer(InferTy::MaybeNeverTypeVar(tv1)),
314 Ty::Infer(InferTy::MaybeNeverTypeVar(tv2)),
315 ) => {
316 // both type vars are unknown since we tried to resolve them
317 self.var_unification_table.union(*tv1, *tv2);
318 true
319 }
320
321 // The order of MaybeNeverTypeVar matters here.
322 // Unifying MaybeNeverTypeVar and TypeVar will let the latter become MaybeNeverTypeVar.
323 // Unifying MaybeNeverTypeVar and other concrete type will let the former become it.
324 (Ty::Infer(InferTy::TypeVar(tv)), other)
325 | (other, Ty::Infer(InferTy::TypeVar(tv)))
326 | (Ty::Infer(InferTy::MaybeNeverTypeVar(tv)), other)
327 | (other, Ty::Infer(InferTy::MaybeNeverTypeVar(tv)))
328 | (Ty::Infer(InferTy::IntVar(tv)), other @ ty_app!(TypeCtor::Int(_)))
329 | (other @ ty_app!(TypeCtor::Int(_)), Ty::Infer(InferTy::IntVar(tv)))
330 | (Ty::Infer(InferTy::FloatVar(tv)), other @ ty_app!(TypeCtor::Float(_)))
331 | (other @ ty_app!(TypeCtor::Float(_)), Ty::Infer(InferTy::FloatVar(tv))) => {
332 // the type var is unknown since we tried to resolve it
333 self.var_unification_table.union_value(*tv, TypeVarValue::Known(other.clone()));
334 true
335 }
336
337 _ => false,
338 }
339 }
340
341 fn new_type_var(&mut self) -> Ty {
342 Ty::Infer(InferTy::TypeVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
343 }
344
345 fn new_integer_var(&mut self) -> Ty {
346 Ty::Infer(InferTy::IntVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
347 }
348
349 fn new_float_var(&mut self) -> Ty {
350 Ty::Infer(InferTy::FloatVar(self.var_unification_table.new_key(TypeVarValue::Unknown)))
351 }
352
353 fn new_maybe_never_type_var(&mut self) -> Ty {
354 Ty::Infer(InferTy::MaybeNeverTypeVar(
355 self.var_unification_table.new_key(TypeVarValue::Unknown),
356 ))
357 }
358
359 /// Replaces Ty::Unknown by a new type var, so we can maybe still infer it.
360 fn insert_type_vars_shallow(&mut self, ty: Ty) -> Ty {
361 match ty {
362 Ty::Unknown => self.new_type_var(),
363 Ty::Apply(ApplicationTy { ctor: TypeCtor::Int(Uncertain::Unknown), .. }) => {
364 self.new_integer_var()
365 }
366 Ty::Apply(ApplicationTy { ctor: TypeCtor::Float(Uncertain::Unknown), .. }) => {
367 self.new_float_var()
368 }
369 _ => ty,
370 }
371 }
372
373 fn insert_type_vars(&mut self, ty: Ty) -> Ty {
374 ty.fold(&mut |ty| self.insert_type_vars_shallow(ty))
375 }
376
377 fn resolve_obligations_as_possible(&mut self) {
378 let obligations = mem::replace(&mut self.obligations, Vec::new());
379 for obligation in obligations {
380 let in_env = InEnvironment::new(self.trait_env.clone(), obligation.clone());
381 let canonicalized = self.canonicalizer().canonicalize_obligation(in_env);
382 let solution = self
383 .db
384 .trait_solve(self.resolver.krate().unwrap().into(), canonicalized.value.clone());
385
386 match solution {
387 Some(Solution::Unique(substs)) => {
388 canonicalized.apply_solution(self, substs.0);
389 }
390 Some(Solution::Ambig(Guidance::Definite(substs))) => {
391 canonicalized.apply_solution(self, substs.0);
392 self.obligations.push(obligation);
393 }
394 Some(_) => {
395 // FIXME use this when trying to resolve everything at the end
396 self.obligations.push(obligation);
397 }
398 None => {
399 // FIXME obligation cannot be fulfilled => diagnostic
400 }
401 };
402 }
403 }
404
405 /// Resolves the type as far as currently possible, replacing type variables
406 /// by their known types. All types returned by the infer_* functions should
407 /// be resolved as far as possible, i.e. contain no type variables with
408 /// known type.
409 fn resolve_ty_as_possible(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
410 self.resolve_obligations_as_possible();
411
412 ty.fold(&mut |ty| match ty {
413 Ty::Infer(tv) => {
414 let inner = tv.to_inner();
415 if tv_stack.contains(&inner) {
416 tested_by!(type_var_cycles_resolve_as_possible);
417 // recursive type
418 return tv.fallback_value();
419 }
420 if let Some(known_ty) =
421 self.var_unification_table.inlined_probe_value(inner).known()
422 {
423 // known_ty may contain other variables that are known by now
424 tv_stack.push(inner);
425 let result = self.resolve_ty_as_possible(tv_stack, known_ty.clone());
426 tv_stack.pop();
427 result
428 } else {
429 ty
430 }
431 }
432 _ => ty,
433 })
434 }
435
436 /// If `ty` is a type variable with known type, returns that type;
437 /// otherwise, return ty.
438 fn resolve_ty_shallow<'b>(&mut self, ty: &'b Ty) -> Cow<'b, Ty> {
439 let mut ty = Cow::Borrowed(ty);
440 // The type variable could resolve to a int/float variable. Hence try
441 // resolving up to three times; each type of variable shouldn't occur
442 // more than once
443 for i in 0..3 {
444 if i > 0 {
445 tested_by!(type_var_resolves_to_int_var);
446 }
447 match &*ty {
448 Ty::Infer(tv) => {
449 let inner = tv.to_inner();
450 match self.var_unification_table.inlined_probe_value(inner).known() {
451 Some(known_ty) => {
452 // The known_ty can't be a type var itself
453 ty = Cow::Owned(known_ty.clone());
454 }
455 _ => return ty,
456 }
457 }
458 _ => return ty,
459 }
460 }
461 log::error!("Inference variable still not resolved: {:?}", ty);
462 ty
463 }
464
465 /// Recurses through the given type, normalizing associated types mentioned
466 /// in it by replacing them by type variables and registering obligations to
467 /// resolve later. This should be done once for every type we get from some
468 /// type annotation (e.g. from a let type annotation, field type or function
469 /// call). `make_ty` handles this already, but e.g. for field types we need
470 /// to do it as well.
471 fn normalize_associated_types_in(&mut self, ty: Ty) -> Ty {
472 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
473 ty.fold(&mut |ty| match ty {
474 Ty::Projection(proj_ty) => self.normalize_projection_ty(proj_ty),
475 _ => ty,
476 })
477 }
478
479 fn normalize_projection_ty(&mut self, proj_ty: ProjectionTy) -> Ty {
480 let var = self.new_type_var();
481 let predicate = ProjectionPredicate { projection_ty: proj_ty, ty: var.clone() };
482 let obligation = Obligation::Projection(predicate);
483 self.obligations.push(obligation);
484 var
485 }
486
487 /// Resolves the type completely; type variables without known type are
488 /// replaced by Ty::Unknown.
489 fn resolve_ty_completely(&mut self, tv_stack: &mut Vec<TypeVarId>, ty: Ty) -> Ty {
490 ty.fold(&mut |ty| match ty {
491 Ty::Infer(tv) => {
492 let inner = tv.to_inner();
493 if tv_stack.contains(&inner) {
494 tested_by!(type_var_cycles_resolve_completely);
495 // recursive type
496 return tv.fallback_value();
497 }
498 if let Some(known_ty) =
499 self.var_unification_table.inlined_probe_value(inner).known()
500 {
501 // known_ty may contain other variables that are known by now
502 tv_stack.push(inner);
503 let result = self.resolve_ty_completely(tv_stack, known_ty.clone());
504 tv_stack.pop();
505 result
506 } else {
507 tv.fallback_value()
508 }
509 }
510 _ => ty,
511 })
512 }
513
514 fn resolve_variant(&mut self, path: Option<&Path>) -> (Ty, Option<VariantId>) {
515 let path = match path {
516 Some(path) => path,
517 None => return (Ty::Unknown, None),
518 };
519 let resolver = &self.resolver;
520 // FIXME: this should resolve assoc items as well, see this example:
521 // https://play.rust-lang.org/?gist=087992e9e22495446c01c0d4e2d69521
522 match resolver.resolve_path_in_type_ns_fully(self.db, &path) {
523 Some(TypeNs::AdtId(AdtId::StructId(strukt))) => {
524 let substs = Ty::substs_from_path(self.db, resolver, path, strukt.into());
525 let ty = self.db.ty(strukt.into());
526 let ty = self.insert_type_vars(ty.apply_substs(substs));
527 (ty, Some(strukt.into()))
528 }
529 Some(TypeNs::EnumVariantId(var)) => {
530 let substs = Ty::substs_from_path(self.db, resolver, path, var.into());
531 let ty = self.db.ty(var.parent.into());
532 let ty = self.insert_type_vars(ty.apply_substs(substs));
533 (ty, Some(var.into()))
534 }
535 Some(_) | None => (Ty::Unknown, None),
536 }
537 }
538
539 fn collect_const(&mut self, data: &ConstData) {
540 self.return_ty = self.make_ty(&data.type_ref);
541 }
542
543 fn collect_fn(&mut self, data: &FunctionData) {
544 let body = Arc::clone(&self.body); // avoid borrow checker problem
545 for (type_ref, pat) in data.params.iter().zip(body.params.iter()) {
546 let ty = self.make_ty(type_ref);
547
548 self.infer_pat(*pat, &ty, BindingMode::default());
549 }
550 self.return_ty = self.make_ty(&data.ret_type);
551 }
552
553 fn infer_body(&mut self) {
554 self.infer_expr(self.body.body_expr, &Expectation::has_type(self.return_ty.clone()));
555 }
556
557 fn resolve_into_iter_item(&self) -> Option<TypeAliasId> {
558 let path = known::std_iter_into_iterator();
559 let trait_ = self.resolver.resolve_known_trait(self.db, &path)?;
560 self.db.trait_data(trait_).associated_type_by_name(&name::ITEM_TYPE)
561 }
562
563 fn resolve_ops_try_ok(&self) -> Option<TypeAliasId> {
564 let path = known::std_ops_try();
565 let trait_ = self.resolver.resolve_known_trait(self.db, &path)?;
566 self.db.trait_data(trait_).associated_type_by_name(&name::OK_TYPE)
567 }
568
569 fn resolve_future_future_output(&self) -> Option<TypeAliasId> {
570 let path = known::std_future_future();
571 let trait_ = self.resolver.resolve_known_trait(self.db, &path)?;
572 self.db.trait_data(trait_).associated_type_by_name(&name::OUTPUT_TYPE)
573 }
574
575 fn resolve_boxed_box(&self) -> Option<AdtId> {
576 let path = known::std_boxed_box();
577 let struct_ = self.resolver.resolve_known_struct(self.db, &path)?;
578 Some(struct_.into())
579 }
580}
581
582/// The ID of a type variable.
583#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
584pub struct TypeVarId(pub(super) u32);
585
586impl UnifyKey for TypeVarId {
587 type Value = TypeVarValue;
588
589 fn index(&self) -> u32 {
590 self.0
591 }
592
593 fn from_index(i: u32) -> Self {
594 TypeVarId(i)
595 }
596
597 fn tag() -> &'static str {
598 "TypeVarId"
599 }
600}
601
602/// The value of a type variable: either we already know the type, or we don't
603/// know it yet.
604#[derive(Clone, PartialEq, Eq, Debug)]
605pub enum TypeVarValue {
606 Known(Ty),
607 Unknown,
608}
609
610impl TypeVarValue {
611 fn known(&self) -> Option<&Ty> {
612 match self {
613 TypeVarValue::Known(ty) => Some(ty),
614 TypeVarValue::Unknown => None,
615 }
616 }
617}
618
619impl UnifyValue for TypeVarValue {
620 type Error = NoError;
621
622 fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
623 match (value1, value2) {
624 // We should never equate two type variables, both of which have
625 // known types. Instead, we recursively equate those types.
626 (TypeVarValue::Known(t1), TypeVarValue::Known(t2)) => panic!(
627 "equating two type variables, both of which have known types: {:?} and {:?}",
628 t1, t2
629 ),
630
631 // If one side is known, prefer that one.
632 (TypeVarValue::Known(..), TypeVarValue::Unknown) => Ok(value1.clone()),
633 (TypeVarValue::Unknown, TypeVarValue::Known(..)) => Ok(value2.clone()),
634
635 (TypeVarValue::Unknown, TypeVarValue::Unknown) => Ok(TypeVarValue::Unknown),
636 }
637 }
638}
639
640/// The kinds of placeholders we need during type inference. There's separate
641/// values for general types, and for integer and float variables. The latter
642/// two are used for inference of literal values (e.g. `100` could be one of
643/// several integer types).
644#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
645pub enum InferTy {
646 TypeVar(TypeVarId),
647 IntVar(TypeVarId),
648 FloatVar(TypeVarId),
649 MaybeNeverTypeVar(TypeVarId),
650}
651
652impl InferTy {
653 fn to_inner(self) -> TypeVarId {
654 match self {
655 InferTy::TypeVar(ty)
656 | InferTy::IntVar(ty)
657 | InferTy::FloatVar(ty)
658 | InferTy::MaybeNeverTypeVar(ty) => ty,
659 }
660 }
661
662 fn fallback_value(self) -> Ty {
663 match self {
664 InferTy::TypeVar(..) => Ty::Unknown,
665 InferTy::IntVar(..) => Ty::simple(TypeCtor::Int(Uncertain::Known(IntTy::i32()))),
666 InferTy::FloatVar(..) => Ty::simple(TypeCtor::Float(Uncertain::Known(FloatTy::f64()))),
667 InferTy::MaybeNeverTypeVar(..) => Ty::simple(TypeCtor::Never),
668 }
669 }
670}
671
672/// When inferring an expression, we propagate downward whatever type hint we
673/// are able in the form of an `Expectation`.
674#[derive(Clone, PartialEq, Eq, Debug)]
675struct Expectation {
676 ty: Ty,
677 // FIXME: In some cases, we need to be aware whether the expectation is that
678 // the type match exactly what we passed, or whether it just needs to be
679 // coercible to the expected type. See Expectation::rvalue_hint in rustc.
680}
681
682impl Expectation {
683 /// The expectation that the type of the expression needs to equal the given
684 /// type.
685 fn has_type(ty: Ty) -> Self {
686 Expectation { ty }
687 }
688
689 /// This expresses no expectation on the type.
690 fn none() -> Self {
691 Expectation { ty: Ty::Unknown }
692 }
693}
694
695mod diagnostics {
696 use hir_def::{expr::ExprId, FunctionId, HasSource, Lookup};
697 use hir_expand::diagnostics::DiagnosticSink;
698
699 use crate::{db::HirDatabase, diagnostics::NoSuchField};
700
701 #[derive(Debug, PartialEq, Eq, Clone)]
702 pub(super) enum InferenceDiagnostic {
703 NoSuchField { expr: ExprId, field: usize },
704 }
705
706 impl InferenceDiagnostic {
707 pub(super) fn add_to(
708 &self,
709 db: &impl HirDatabase,
710 owner: FunctionId,
711 sink: &mut DiagnosticSink,
712 ) {
713 match self {
714 InferenceDiagnostic::NoSuchField { expr, field } => {
715 let file = owner.lookup(db).source(db).file_id;
716 let (_, source_map) = db.body_with_source_map(owner.into());
717 let field = source_map.field_syntax(*expr, *field);
718 sink.push(NoSuchField { file, field })
719 }
720 }
721 }
722 }
723}
diff --git a/crates/ra_hir/src/ty/infer/coerce.rs b/crates/ra_hir/src/ty/infer/coerce.rs
deleted file mode 100644
index 3fb5d8a83..000000000
--- a/crates/ra_hir/src/ty/infer/coerce.rs
+++ /dev/null
@@ -1,357 +0,0 @@
1//! Coercion logic. Coercions are certain type conversions that can implicitly
2//! happen in certain places, e.g. weakening `&mut` to `&` or deref coercions
3//! like going from `&Vec<T>` to `&[T]`.
4//!
5//! See: https://doc.rust-lang.org/nomicon/coercions.html
6
7use hir_def::{
8 lang_item::LangItemTarget,
9 resolver::{HasResolver, Resolver},
10 type_ref::Mutability,
11 AdtId,
12};
13use rustc_hash::FxHashMap;
14use test_utils::tested_by;
15
16use crate::{
17 db::HirDatabase,
18 ty::{autoderef, Substs, TraitRef, Ty, TypeCtor, TypeWalk},
19};
20
21use super::{InEnvironment, InferTy, InferenceContext, TypeVarValue};
22
23impl<'a, D: HirDatabase> InferenceContext<'a, D> {
24 /// Unify two types, but may coerce the first one to the second one
25 /// using "implicit coercion rules" if needed.
26 pub(super) fn coerce(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
27 let from_ty = self.resolve_ty_shallow(from_ty).into_owned();
28 let to_ty = self.resolve_ty_shallow(to_ty);
29 self.coerce_inner(from_ty, &to_ty)
30 }
31
32 /// Merge two types from different branches, with possible implicit coerce.
33 ///
34 /// Note that it is only possible that one type are coerced to another.
35 /// Coercing both types to another least upper bound type is not possible in rustc,
36 /// which will simply result in "incompatible types" error.
37 pub(super) fn coerce_merge_branch<'t>(&mut self, ty1: &Ty, ty2: &Ty) -> Ty {
38 if self.coerce(ty1, ty2) {
39 ty2.clone()
40 } else if self.coerce(ty2, ty1) {
41 ty1.clone()
42 } else {
43 tested_by!(coerce_merge_fail_fallback);
44 // For incompatible types, we use the latter one as result
45 // to be better recovery for `if` without `else`.
46 ty2.clone()
47 }
48 }
49
50 pub(super) fn init_coerce_unsized_map(
51 db: &'a D,
52 resolver: &Resolver,
53 ) -> FxHashMap<(TypeCtor, TypeCtor), usize> {
54 let krate = resolver.krate().unwrap();
55 let impls = match db.lang_item(krate.into(), "coerce_unsized".into()) {
56 Some(LangItemTarget::TraitId(trait_)) => {
57 db.impls_for_trait(krate.into(), trait_.into())
58 }
59 _ => return FxHashMap::default(),
60 };
61
62 impls
63 .iter()
64 .filter_map(|&impl_id| {
65 let impl_data = db.impl_data(impl_id);
66 let resolver = impl_id.resolver(db);
67 let target_ty = Ty::from_hir(db, &resolver, &impl_data.target_type);
68
69 // `CoerseUnsized` has one generic parameter for the target type.
70 let trait_ref = TraitRef::from_hir(
71 db,
72 &resolver,
73 impl_data.target_trait.as_ref()?,
74 Some(target_ty),
75 )?;
76 let cur_from_ty = trait_ref.substs.0.get(0)?;
77 let cur_to_ty = trait_ref.substs.0.get(1)?;
78
79 match (&cur_from_ty, cur_to_ty) {
80 (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => {
81 // FIXME: We return the first non-equal bound as the type parameter to coerce to unsized type.
82 // This works for smart-pointer-like coercion, which covers all impls from std.
83 st1.iter().zip(st2.iter()).enumerate().find_map(|(i, (ty1, ty2))| {
84 match (ty1, ty2) {
85 (Ty::Param { idx: p1, .. }, Ty::Param { idx: p2, .. })
86 if p1 != p2 =>
87 {
88 Some(((*ctor1, *ctor2), i))
89 }
90 _ => None,
91 }
92 })
93 }
94 _ => None,
95 }
96 })
97 .collect()
98 }
99
100 fn coerce_inner(&mut self, mut from_ty: Ty, to_ty: &Ty) -> bool {
101 match (&from_ty, to_ty) {
102 // Never type will make type variable to fallback to Never Type instead of Unknown.
103 (ty_app!(TypeCtor::Never), Ty::Infer(InferTy::TypeVar(tv))) => {
104 let var = self.new_maybe_never_type_var();
105 self.var_unification_table.union_value(*tv, TypeVarValue::Known(var));
106 return true;
107 }
108 (ty_app!(TypeCtor::Never), _) => return true,
109
110 // Trivial cases, this should go after `never` check to
111 // avoid infer result type to be never
112 _ => {
113 if self.unify_inner_trivial(&from_ty, &to_ty) {
114 return true;
115 }
116 }
117 }
118
119 // Pointer weakening and function to pointer
120 match (&mut from_ty, to_ty) {
121 // `*mut T`, `&mut T, `&T`` -> `*const T`
122 // `&mut T` -> `&T`
123 // `&mut T` -> `*mut T`
124 (ty_app!(c1@TypeCtor::RawPtr(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
125 | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::RawPtr(Mutability::Shared)))
126 | (ty_app!(c1@TypeCtor::Ref(_)), ty_app!(c2@TypeCtor::Ref(Mutability::Shared)))
127 | (ty_app!(c1@TypeCtor::Ref(Mutability::Mut)), ty_app!(c2@TypeCtor::RawPtr(_))) => {
128 *c1 = *c2;
129 }
130
131 // Illegal mutablity conversion
132 (
133 ty_app!(TypeCtor::RawPtr(Mutability::Shared)),
134 ty_app!(TypeCtor::RawPtr(Mutability::Mut)),
135 )
136 | (
137 ty_app!(TypeCtor::Ref(Mutability::Shared)),
138 ty_app!(TypeCtor::Ref(Mutability::Mut)),
139 ) => return false,
140
141 // `{function_type}` -> `fn()`
142 (ty_app!(TypeCtor::FnDef(_)), ty_app!(TypeCtor::FnPtr { .. })) => {
143 match from_ty.callable_sig(self.db) {
144 None => return false,
145 Some(sig) => {
146 let num_args = sig.params_and_return.len() as u16 - 1;
147 from_ty =
148 Ty::apply(TypeCtor::FnPtr { num_args }, Substs(sig.params_and_return));
149 }
150 }
151 }
152
153 _ => {}
154 }
155
156 if let Some(ret) = self.try_coerce_unsized(&from_ty, &to_ty) {
157 return ret;
158 }
159
160 // Auto Deref if cannot coerce
161 match (&from_ty, to_ty) {
162 // FIXME: DerefMut
163 (ty_app!(TypeCtor::Ref(_), st1), ty_app!(TypeCtor::Ref(_), st2)) => {
164 self.unify_autoderef_behind_ref(&st1[0], &st2[0])
165 }
166
167 // Otherwise, normal unify
168 _ => self.unify(&from_ty, to_ty),
169 }
170 }
171
172 /// Coerce a type using `from_ty: CoerceUnsized<ty_ty>`
173 ///
174 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.CoerceUnsized.html
175 fn try_coerce_unsized(&mut self, from_ty: &Ty, to_ty: &Ty) -> Option<bool> {
176 let (ctor1, st1, ctor2, st2) = match (from_ty, to_ty) {
177 (ty_app!(ctor1, st1), ty_app!(ctor2, st2)) => (ctor1, st1, ctor2, st2),
178 _ => return None,
179 };
180
181 let coerce_generic_index = *self.coerce_unsized_map.get(&(*ctor1, *ctor2))?;
182
183 // Check `Unsize` first
184 match self.check_unsize_and_coerce(
185 st1.0.get(coerce_generic_index)?,
186 st2.0.get(coerce_generic_index)?,
187 0,
188 ) {
189 Some(true) => {}
190 ret => return ret,
191 }
192
193 let ret = st1
194 .iter()
195 .zip(st2.iter())
196 .enumerate()
197 .filter(|&(idx, _)| idx != coerce_generic_index)
198 .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
199
200 Some(ret)
201 }
202
203 /// Check if `from_ty: Unsize<to_ty>`, and coerce to `to_ty` if it holds.
204 ///
205 /// It should not be directly called. It is only used by `try_coerce_unsized`.
206 ///
207 /// See: https://doc.rust-lang.org/nightly/std/marker/trait.Unsize.html
208 fn check_unsize_and_coerce(&mut self, from_ty: &Ty, to_ty: &Ty, depth: usize) -> Option<bool> {
209 if depth > 1000 {
210 panic!("Infinite recursion in coercion");
211 }
212
213 match (&from_ty, &to_ty) {
214 // `[T; N]` -> `[T]`
215 (ty_app!(TypeCtor::Array, st1), ty_app!(TypeCtor::Slice, st2)) => {
216 Some(self.unify(&st1[0], &st2[0]))
217 }
218
219 // `T` -> `dyn Trait` when `T: Trait`
220 (_, Ty::Dyn(_)) => {
221 // FIXME: Check predicates
222 Some(true)
223 }
224
225 // `(..., T)` -> `(..., U)` when `T: Unsize<U>`
226 (
227 ty_app!(TypeCtor::Tuple { cardinality: len1 }, st1),
228 ty_app!(TypeCtor::Tuple { cardinality: len2 }, st2),
229 ) => {
230 if len1 != len2 || *len1 == 0 {
231 return None;
232 }
233
234 match self.check_unsize_and_coerce(
235 st1.last().unwrap(),
236 st2.last().unwrap(),
237 depth + 1,
238 ) {
239 Some(true) => {}
240 ret => return ret,
241 }
242
243 let ret = st1[..st1.len() - 1]
244 .iter()
245 .zip(&st2[..st2.len() - 1])
246 .all(|(ty1, ty2)| self.unify(ty1, ty2));
247
248 Some(ret)
249 }
250
251 // Foo<..., T, ...> is Unsize<Foo<..., U, ...>> if:
252 // - T: Unsize<U>
253 // - Foo is a struct
254 // - Only the last field of Foo has a type involving T
255 // - T is not part of the type of any other fields
256 // - Bar<T>: Unsize<Bar<U>>, if the last field of Foo has type Bar<T>
257 (
258 ty_app!(TypeCtor::Adt(AdtId::StructId(struct1)), st1),
259 ty_app!(TypeCtor::Adt(AdtId::StructId(struct2)), st2),
260 ) if struct1 == struct2 => {
261 let field_tys = self.db.field_types((*struct1).into());
262 let struct_data = self.db.struct_data(*struct1);
263
264 let mut fields = struct_data.variant_data.fields().iter();
265 let (last_field_id, _data) = fields.next_back()?;
266
267 // Get the generic parameter involved in the last field.
268 let unsize_generic_index = {
269 let mut index = None;
270 let mut multiple_param = false;
271 field_tys[last_field_id].walk(&mut |ty| match ty {
272 &Ty::Param { idx, .. } => {
273 if index.is_none() {
274 index = Some(idx);
275 } else if Some(idx) != index {
276 multiple_param = true;
277 }
278 }
279 _ => {}
280 });
281
282 if multiple_param {
283 return None;
284 }
285 index?
286 };
287
288 // Check other fields do not involve it.
289 let mut multiple_used = false;
290 fields.for_each(|(field_id, _data)| {
291 field_tys[field_id].walk(&mut |ty| match ty {
292 &Ty::Param { idx, .. } if idx == unsize_generic_index => {
293 multiple_used = true
294 }
295 _ => {}
296 })
297 });
298 if multiple_used {
299 return None;
300 }
301
302 let unsize_generic_index = unsize_generic_index as usize;
303
304 // Check `Unsize` first
305 match self.check_unsize_and_coerce(
306 st1.get(unsize_generic_index)?,
307 st2.get(unsize_generic_index)?,
308 depth + 1,
309 ) {
310 Some(true) => {}
311 ret => return ret,
312 }
313
314 // Then unify other parameters
315 let ret = st1
316 .iter()
317 .zip(st2.iter())
318 .enumerate()
319 .filter(|&(idx, _)| idx != unsize_generic_index)
320 .all(|(_, (ty1, ty2))| self.unify(ty1, ty2));
321
322 Some(ret)
323 }
324
325 _ => None,
326 }
327 }
328
329 /// Unify `from_ty` to `to_ty` with optional auto Deref
330 ///
331 /// Note that the parameters are already stripped the outer reference.
332 fn unify_autoderef_behind_ref(&mut self, from_ty: &Ty, to_ty: &Ty) -> bool {
333 let canonicalized = self.canonicalizer().canonicalize_ty(from_ty.clone());
334 let to_ty = self.resolve_ty_shallow(&to_ty);
335 // FIXME: Auto DerefMut
336 for derefed_ty in autoderef::autoderef(
337 self.db,
338 self.resolver.krate(),
339 InEnvironment {
340 value: canonicalized.value.clone(),
341 environment: self.trait_env.clone(),
342 },
343 ) {
344 let derefed_ty = canonicalized.decanonicalize_ty(derefed_ty.value);
345 match (&*self.resolve_ty_shallow(&derefed_ty), &*to_ty) {
346 // Stop when constructor matches.
347 (ty_app!(from_ctor, st1), ty_app!(to_ctor, st2)) if from_ctor == to_ctor => {
348 // It will not recurse to `coerce`.
349 return self.unify_substs(st1, st2, 0);
350 }
351 _ => {}
352 }
353 }
354
355 false
356 }
357}
diff --git a/crates/ra_hir/src/ty/infer/expr.rs b/crates/ra_hir/src/ty/infer/expr.rs
deleted file mode 100644
index f9ededa23..000000000
--- a/crates/ra_hir/src/ty/infer/expr.rs
+++ /dev/null
@@ -1,689 +0,0 @@
1//! Type inference for expressions.
2
3use std::iter::{repeat, repeat_with};
4use std::sync::Arc;
5
6use hir_def::{
7 builtin_type::Signedness,
8 expr::{Array, BinaryOp, Expr, ExprId, Literal, Statement, UnaryOp},
9 generics::GenericParams,
10 path::{GenericArg, GenericArgs},
11 resolver::resolver_for_expr,
12 AdtId, ContainerId, Lookup, StructFieldId,
13};
14use hir_expand::name::{self, Name};
15
16use crate::{
17 db::HirDatabase,
18 ty::{
19 autoderef, method_resolution, op, traits::InEnvironment, utils::variant_data, CallableDef,
20 InferTy, IntTy, Mutability, Obligation, ProjectionPredicate, ProjectionTy, Substs,
21 TraitRef, Ty, TypeCtor, TypeWalk, Uncertain,
22 },
23};
24
25use super::{BindingMode, Expectation, InferenceContext, InferenceDiagnostic, TypeMismatch};
26
27impl<'a, D: HirDatabase> InferenceContext<'a, D> {
28 pub(super) fn infer_expr(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
29 let ty = self.infer_expr_inner(tgt_expr, expected);
30 let could_unify = self.unify(&ty, &expected.ty);
31 if !could_unify {
32 self.result.type_mismatches.insert(
33 tgt_expr,
34 TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() },
35 );
36 }
37 let ty = self.resolve_ty_as_possible(&mut vec![], ty);
38 ty
39 }
40
41 /// Infer type of expression with possibly implicit coerce to the expected type.
42 /// Return the type after possible coercion.
43 fn infer_expr_coerce(&mut self, expr: ExprId, expected: &Expectation) -> Ty {
44 let ty = self.infer_expr_inner(expr, &expected);
45 let ty = if !self.coerce(&ty, &expected.ty) {
46 self.result
47 .type_mismatches
48 .insert(expr, TypeMismatch { expected: expected.ty.clone(), actual: ty.clone() });
49 // Return actual type when type mismatch.
50 // This is needed for diagnostic when return type mismatch.
51 ty
52 } else if expected.ty == Ty::Unknown {
53 ty
54 } else {
55 expected.ty.clone()
56 };
57
58 self.resolve_ty_as_possible(&mut vec![], ty)
59 }
60
61 fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
62 let body = Arc::clone(&self.body); // avoid borrow checker problem
63 let ty = match &body[tgt_expr] {
64 Expr::Missing => Ty::Unknown,
65 Expr::If { condition, then_branch, else_branch } => {
66 // if let is desugared to match, so this is always simple if
67 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
68
69 let then_ty = self.infer_expr_inner(*then_branch, &expected);
70 let else_ty = match else_branch {
71 Some(else_branch) => self.infer_expr_inner(*else_branch, &expected),
72 None => Ty::unit(),
73 };
74
75 self.coerce_merge_branch(&then_ty, &else_ty)
76 }
77 Expr::Block { statements, tail } => self.infer_block(statements, *tail, expected),
78 Expr::TryBlock { body } => {
79 let _inner = self.infer_expr(*body, expected);
80 // FIXME should be std::result::Result<{inner}, _>
81 Ty::Unknown
82 }
83 Expr::Loop { body } => {
84 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
85 // FIXME handle break with value
86 Ty::simple(TypeCtor::Never)
87 }
88 Expr::While { condition, body } => {
89 // while let is desugared to a match loop, so this is always simple while
90 self.infer_expr(*condition, &Expectation::has_type(Ty::simple(TypeCtor::Bool)));
91 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
92 Ty::unit()
93 }
94 Expr::For { iterable, body, pat } => {
95 let iterable_ty = self.infer_expr(*iterable, &Expectation::none());
96
97 let pat_ty = match self.resolve_into_iter_item() {
98 Some(into_iter_item_alias) => {
99 let pat_ty = self.new_type_var();
100 let projection = ProjectionPredicate {
101 ty: pat_ty.clone(),
102 projection_ty: ProjectionTy {
103 associated_ty: into_iter_item_alias,
104 parameters: Substs::single(iterable_ty),
105 },
106 };
107 self.obligations.push(Obligation::Projection(projection));
108 self.resolve_ty_as_possible(&mut vec![], pat_ty)
109 }
110 None => Ty::Unknown,
111 };
112
113 self.infer_pat(*pat, &pat_ty, BindingMode::default());
114 self.infer_expr(*body, &Expectation::has_type(Ty::unit()));
115 Ty::unit()
116 }
117 Expr::Lambda { body, args, arg_types } => {
118 assert_eq!(args.len(), arg_types.len());
119
120 let mut sig_tys = Vec::new();
121
122 for (arg_pat, arg_type) in args.iter().zip(arg_types.iter()) {
123 let expected = if let Some(type_ref) = arg_type {
124 self.make_ty(type_ref)
125 } else {
126 Ty::Unknown
127 };
128 let arg_ty = self.infer_pat(*arg_pat, &expected, BindingMode::default());
129 sig_tys.push(arg_ty);
130 }
131
132 // add return type
133 let ret_ty = self.new_type_var();
134 sig_tys.push(ret_ty.clone());
135 let sig_ty = Ty::apply(
136 TypeCtor::FnPtr { num_args: sig_tys.len() as u16 - 1 },
137 Substs(sig_tys.into()),
138 );
139 let closure_ty = Ty::apply_one(
140 TypeCtor::Closure { def: self.owner.into(), expr: tgt_expr },
141 sig_ty,
142 );
143
144 // Eagerly try to relate the closure type with the expected
145 // type, otherwise we often won't have enough information to
146 // infer the body.
147 self.coerce(&closure_ty, &expected.ty);
148
149 self.infer_expr(*body, &Expectation::has_type(ret_ty));
150 closure_ty
151 }
152 Expr::Call { callee, args } => {
153 let callee_ty = self.infer_expr(*callee, &Expectation::none());
154 let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
155 Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
156 None => {
157 // Not callable
158 // FIXME: report an error
159 (Vec::new(), Ty::Unknown)
160 }
161 };
162 self.register_obligations_for_call(&callee_ty);
163 self.check_call_arguments(args, &param_tys);
164 let ret_ty = self.normalize_associated_types_in(ret_ty);
165 ret_ty
166 }
167 Expr::MethodCall { receiver, args, method_name, generic_args } => self
168 .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
169 Expr::Match { expr, arms } => {
170 let input_ty = self.infer_expr(*expr, &Expectation::none());
171
172 let mut result_ty = self.new_maybe_never_type_var();
173
174 for arm in arms {
175 for &pat in &arm.pats {
176 let _pat_ty = self.infer_pat(pat, &input_ty, BindingMode::default());
177 }
178 if let Some(guard_expr) = arm.guard {
179 self.infer_expr(
180 guard_expr,
181 &Expectation::has_type(Ty::simple(TypeCtor::Bool)),
182 );
183 }
184
185 let arm_ty = self.infer_expr_inner(arm.expr, &expected);
186 result_ty = self.coerce_merge_branch(&result_ty, &arm_ty);
187 }
188
189 result_ty
190 }
191 Expr::Path(p) => {
192 // FIXME this could be more efficient...
193 let resolver = resolver_for_expr(self.db, self.owner.into(), tgt_expr);
194 self.infer_path(&resolver, p, tgt_expr.into()).unwrap_or(Ty::Unknown)
195 }
196 Expr::Continue => Ty::simple(TypeCtor::Never),
197 Expr::Break { expr } => {
198 if let Some(expr) = expr {
199 // FIXME handle break with value
200 self.infer_expr(*expr, &Expectation::none());
201 }
202 Ty::simple(TypeCtor::Never)
203 }
204 Expr::Return { expr } => {
205 if let Some(expr) = expr {
206 self.infer_expr(*expr, &Expectation::has_type(self.return_ty.clone()));
207 }
208 Ty::simple(TypeCtor::Never)
209 }
210 Expr::RecordLit { path, fields, spread } => {
211 let (ty, def_id) = self.resolve_variant(path.as_ref());
212 if let Some(variant) = def_id {
213 self.write_variant_resolution(tgt_expr.into(), variant);
214 }
215
216 self.unify(&ty, &expected.ty);
217
218 let substs = ty.substs().unwrap_or_else(Substs::empty);
219 let field_types =
220 def_id.map(|it| self.db.field_types(it.into())).unwrap_or_default();
221 let variant_data = def_id.map(|it| variant_data(self.db, it));
222 for (field_idx, field) in fields.iter().enumerate() {
223 let field_def =
224 variant_data.as_ref().and_then(|it| match it.field(&field.name) {
225 Some(local_id) => {
226 Some(StructFieldId { parent: def_id.unwrap(), local_id })
227 }
228 None => {
229 self.push_diagnostic(InferenceDiagnostic::NoSuchField {
230 expr: tgt_expr,
231 field: field_idx,
232 });
233 None
234 }
235 });
236 if let Some(field_def) = field_def {
237 self.result.record_field_resolutions.insert(field.expr, field_def);
238 }
239 let field_ty = field_def
240 .map_or(Ty::Unknown, |it| field_types[it.local_id].clone())
241 .subst(&substs);
242 self.infer_expr_coerce(field.expr, &Expectation::has_type(field_ty));
243 }
244 if let Some(expr) = spread {
245 self.infer_expr(*expr, &Expectation::has_type(ty.clone()));
246 }
247 ty
248 }
249 Expr::Field { expr, name } => {
250 let receiver_ty = self.infer_expr(*expr, &Expectation::none());
251 let canonicalized = self.canonicalizer().canonicalize_ty(receiver_ty);
252 let ty = autoderef::autoderef(
253 self.db,
254 self.resolver.krate(),
255 InEnvironment {
256 value: canonicalized.value.clone(),
257 environment: self.trait_env.clone(),
258 },
259 )
260 .find_map(|derefed_ty| match canonicalized.decanonicalize_ty(derefed_ty.value) {
261 Ty::Apply(a_ty) => match a_ty.ctor {
262 TypeCtor::Tuple { .. } => name
263 .as_tuple_index()
264 .and_then(|idx| a_ty.parameters.0.get(idx).cloned()),
265 TypeCtor::Adt(AdtId::StructId(s)) => {
266 self.db.struct_data(s).variant_data.field(name).map(|local_id| {
267 let field = StructFieldId { parent: s.into(), local_id }.into();
268 self.write_field_resolution(tgt_expr, field);
269 self.db.field_types(s.into())[field.local_id]
270 .clone()
271 .subst(&a_ty.parameters)
272 })
273 }
274 // FIXME:
275 TypeCtor::Adt(AdtId::UnionId(_)) => None,
276 _ => None,
277 },
278 _ => None,
279 })
280 .unwrap_or(Ty::Unknown);
281 let ty = self.insert_type_vars(ty);
282 self.normalize_associated_types_in(ty)
283 }
284 Expr::Await { expr } => {
285 let inner_ty = self.infer_expr(*expr, &Expectation::none());
286 let ty = match self.resolve_future_future_output() {
287 Some(future_future_output_alias) => {
288 let ty = self.new_type_var();
289 let projection = ProjectionPredicate {
290 ty: ty.clone(),
291 projection_ty: ProjectionTy {
292 associated_ty: future_future_output_alias,
293 parameters: Substs::single(inner_ty),
294 },
295 };
296 self.obligations.push(Obligation::Projection(projection));
297 self.resolve_ty_as_possible(&mut vec![], ty)
298 }
299 None => Ty::Unknown,
300 };
301 ty
302 }
303 Expr::Try { expr } => {
304 let inner_ty = self.infer_expr(*expr, &Expectation::none());
305 let ty = match self.resolve_ops_try_ok() {
306 Some(ops_try_ok_alias) => {
307 let ty = self.new_type_var();
308 let projection = ProjectionPredicate {
309 ty: ty.clone(),
310 projection_ty: ProjectionTy {
311 associated_ty: ops_try_ok_alias,
312 parameters: Substs::single(inner_ty),
313 },
314 };
315 self.obligations.push(Obligation::Projection(projection));
316 self.resolve_ty_as_possible(&mut vec![], ty)
317 }
318 None => Ty::Unknown,
319 };
320 ty
321 }
322 Expr::Cast { expr, type_ref } => {
323 let _inner_ty = self.infer_expr(*expr, &Expectation::none());
324 let cast_ty = self.make_ty(type_ref);
325 // FIXME check the cast...
326 cast_ty
327 }
328 Expr::Ref { expr, mutability } => {
329 let expectation =
330 if let Some((exp_inner, exp_mutability)) = &expected.ty.as_reference() {
331 if *exp_mutability == Mutability::Mut && *mutability == Mutability::Shared {
332 // FIXME: throw type error - expected mut reference but found shared ref,
333 // which cannot be coerced
334 }
335 Expectation::has_type(Ty::clone(exp_inner))
336 } else {
337 Expectation::none()
338 };
339 // FIXME reference coercions etc.
340 let inner_ty = self.infer_expr(*expr, &expectation);
341 Ty::apply_one(TypeCtor::Ref(*mutability), inner_ty)
342 }
343 Expr::Box { expr } => {
344 let inner_ty = self.infer_expr(*expr, &Expectation::none());
345 if let Some(box_) = self.resolve_boxed_box() {
346 Ty::apply_one(TypeCtor::Adt(box_), inner_ty)
347 } else {
348 Ty::Unknown
349 }
350 }
351 Expr::UnaryOp { expr, op } => {
352 let inner_ty = self.infer_expr(*expr, &Expectation::none());
353 match op {
354 UnaryOp::Deref => match self.resolver.krate() {
355 Some(krate) => {
356 let canonicalized = self.canonicalizer().canonicalize_ty(inner_ty);
357 match autoderef::deref(
358 self.db,
359 krate,
360 InEnvironment {
361 value: &canonicalized.value,
362 environment: self.trait_env.clone(),
363 },
364 ) {
365 Some(derefed_ty) => {
366 canonicalized.decanonicalize_ty(derefed_ty.value)
367 }
368 None => Ty::Unknown,
369 }
370 }
371 None => Ty::Unknown,
372 },
373 UnaryOp::Neg => {
374 match &inner_ty {
375 Ty::Apply(a_ty) => match a_ty.ctor {
376 TypeCtor::Int(Uncertain::Unknown)
377 | TypeCtor::Int(Uncertain::Known(IntTy {
378 signedness: Signedness::Signed,
379 ..
380 }))
381 | TypeCtor::Float(..) => inner_ty,
382 _ => Ty::Unknown,
383 },
384 Ty::Infer(InferTy::IntVar(..)) | Ty::Infer(InferTy::FloatVar(..)) => {
385 inner_ty