aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir')
-rw-r--r--crates/ra_hir/Cargo.toml6
-rw-r--r--crates/ra_hir/src/code_model_api.rs6
-rw-r--r--crates/ra_hir/src/db.rs39
-rw-r--r--crates/ra_hir/src/expr.rs42
-rw-r--r--crates/ra_hir/src/generics.rs11
-rw-r--r--crates/ra_hir/src/ids.rs89
-rw-r--r--crates/ra_hir/src/resolve.rs3
-rw-r--r--crates/ra_hir/src/source_binder.rs11
-rw-r--r--crates/ra_hir/src/ty.rs112
-rw-r--r--crates/ra_hir/src/ty/infer.rs52
-rw-r--r--crates/ra_hir/src/ty/infer/unify.rs122
-rw-r--r--crates/ra_hir/src/ty/lower.rs37
-rw-r--r--crates/ra_hir/src/ty/method_resolution.rs223
-rw-r--r--crates/ra_hir/src/ty/tests.rs2
-rw-r--r--crates/ra_hir/src/ty/traits.rs223
-rw-r--r--crates/ra_hir/src/ty/traits/chalk.rs333
16 files changed, 966 insertions, 345 deletions
diff --git a/crates/ra_hir/Cargo.toml b/crates/ra_hir/Cargo.toml
index a2858dad9..68ffcb2e9 100644
--- a/crates/ra_hir/Cargo.toml
+++ b/crates/ra_hir/Cargo.toml
@@ -19,7 +19,11 @@ ra_db = { path = "../ra_db" }
19mbe = { path = "../ra_mbe", package = "ra_mbe" } 19mbe = { path = "../ra_mbe", package = "ra_mbe" }
20tt = { path = "../ra_tt", package = "ra_tt" } 20tt = { path = "../ra_tt", package = "ra_tt" }
21test_utils = { path = "../test_utils" } 21test_utils = { path = "../test_utils" }
22ra_prof = {path = "../ra_prof" } 22ra_prof = { path = "../ra_prof" }
23
24chalk-solve = { git = "https://github.com/rust-lang/chalk.git" }
25chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git" }
26chalk-ir = { git = "https://github.com/rust-lang/chalk.git" }
23 27
24[dev-dependencies] 28[dev-dependencies]
25flexi_logger = "0.11.0" 29flexi_logger = "0.11.0"
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 8f1ed1086..9dcae50a5 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -9,7 +9,7 @@ use crate::{
9 type_ref::TypeRef, 9 type_ref::TypeRef,
10 nameres::{ModuleScope, Namespace, ImportId, CrateModuleId}, 10 nameres::{ModuleScope, Namespace, ImportId, CrateModuleId},
11 expr::{Body, BodySourceMap}, 11 expr::{Body, BodySourceMap},
12 ty::InferenceResult, 12 ty::{ TraitRef, InferenceResult},
13 adt::{EnumVariantId, StructFieldId, VariantDef}, 13 adt::{EnumVariantId, StructFieldId, VariantDef},
14 generics::HasGenericParams, 14 generics::HasGenericParams,
15 docs::{Documentation, Docs, docs_from_ast}, 15 docs::{Documentation, Docs, docs_from_ast},
@@ -696,6 +696,10 @@ impl Trait {
696 db.trait_data(self) 696 db.trait_data(self)
697 } 697 }
698 698
699 pub fn trait_ref(self, db: &impl HirDatabase) -> TraitRef {
700 TraitRef::for_trait(db, self)
701 }
702
699 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { 703 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
700 let r = self.module(db).resolver(db); 704 let r = self.module(db).resolver(db);
701 // add generic params, if present 705 // add generic params, if present
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 8af0a3176..8aaf0375a 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -1,4 +1,4 @@
1use std::sync::Arc; 1use std::sync::{Arc, Mutex};
2 2
3use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast}; 3use ra_syntax::{SyntaxNode, TreeArc, SourceFile, SmolStr, ast};
4use ra_db::{SourceDatabase, salsa}; 4use ra_db::{SourceDatabase, salsa};
@@ -8,16 +8,16 @@ use crate::{
8 Function, FnSignature, ExprScopes, TypeAlias, 8 Function, FnSignature, ExprScopes, TypeAlias,
9 Struct, Enum, StructField, 9 Struct, Enum, StructField,
10 Const, ConstSignature, Static, 10 Const, ConstSignature, Static,
11 DefWithBody, 11 DefWithBody, Trait,
12 ids,
12 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, 13 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap},
13 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig}, 14 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor},
14 adt::{StructData, EnumData}, 15 adt::{StructData, EnumData},
15 impl_block::{ModuleImplBlocks, ImplSourceMap}, 16 impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
16 generics::{GenericParams, GenericDef}, 17 generics::{GenericParams, GenericDef},
17 type_ref::TypeRef, 18 type_ref::TypeRef,
18 traits::TraitData, Trait, ty::TraitRef, 19 traits::TraitData,
19 lang_item::{LangItems, LangItemTarget}, 20 lang_item::{LangItems, LangItemTarget},
20 ids
21}; 21};
22 22
23#[salsa::query_group(DefDatabaseStorage)] 23#[salsa::query_group(DefDatabaseStorage)]
@@ -39,10 +39,22 @@ pub trait DefDatabase: SourceDatabase {
39 #[salsa::interned] 39 #[salsa::interned]
40 fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId; 40 fn intern_type_alias(&self, loc: ids::ItemLoc<ast::TypeAliasDef>) -> ids::TypeAliasId;
41 41
42 // Interned IDs for Chalk integration
43 #[salsa::interned]
44 fn intern_type_ctor(&self, type_ctor: TypeCtor) -> ids::TypeCtorId;
45 #[salsa::interned]
46 fn intern_impl_block(&self, impl_block: ImplBlock) -> ids::GlobalImplId;
47
42 #[salsa::invoke(crate::ids::macro_def_query)] 48 #[salsa::invoke(crate::ids::macro_def_query)]
43 fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>; 49 fn macro_def(&self, macro_id: MacroDefId) -> Option<Arc<mbe::MacroRules>>;
44 50
45 #[salsa::invoke(HirFileId::hir_parse_query)] 51 #[salsa::invoke(crate::ids::macro_arg_query)]
52 fn macro_arg(&self, macro_call: ids::MacroCallId) -> Option<Arc<tt::Subtree>>;
53
54 #[salsa::invoke(crate::ids::macro_expand_query)]
55 fn macro_expand(&self, macro_call: ids::MacroCallId) -> Result<Arc<tt::Subtree>, String>;
56
57 #[salsa::invoke(crate::ids::HirFileId::hir_parse_query)]
46 fn hir_parse(&self, file_id: HirFileId) -> TreeArc<SourceFile>; 58 fn hir_parse(&self, file_id: HirFileId) -> TreeArc<SourceFile>;
47 59
48 #[salsa::invoke(crate::adt::StructData::struct_data_query)] 60 #[salsa::invoke(crate::adt::StructData::struct_data_query)]
@@ -138,8 +150,17 @@ pub trait HirDatabase: DefDatabase {
138 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)] 150 #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
139 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>; 151 fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
140 152
141 #[salsa::invoke(crate::ty::traits::implements)] 153 #[salsa::invoke(crate::ty::traits::impls_for_trait)]
142 fn implements(&self, trait_ref: TraitRef) -> Option<crate::ty::traits::Solution>; 154 fn impls_for_trait(&self, krate: Crate, trait_: Trait) -> Arc<[ImplBlock]>;
155
156 /// This provides the Chalk trait solver instance. Because Chalk always
157 /// works from a specific crate, this query is keyed on the crate; and
158 /// because Chalk does its own internal caching, the solver is wrapped in a
159 /// Mutex and the query is marked volatile, to make sure the cached state is
160 /// thrown away when input facts change.
161 #[salsa::invoke(crate::ty::traits::solver)]
162 #[salsa::volatile]
163 fn solver(&self, krate: Crate) -> Arc<Mutex<crate::ty::traits::Solver>>;
143} 164}
144 165
145#[test] 166#[test]
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
index cdadf3ba6..692da2895 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir/src/expr.rs
@@ -5,14 +5,13 @@ use rustc_hash::FxHashMap;
5 5
6use ra_arena::{Arena, RawId, impl_arena_id, map::ArenaMap}; 6use ra_arena::{Arena, RawId, impl_arena_id, map::ArenaMap};
7use ra_syntax::{ 7use ra_syntax::{
8 SyntaxNodePtr, AstPtr, AstNode,TreeArc, 8 SyntaxNodePtr, AstPtr, AstNode,
9 ast::{self, LoopBodyOwner, ArgListOwner, NameOwner, LiteralKind,ArrayExprKind, TypeAscriptionOwner} 9 ast::{self, LoopBodyOwner, ArgListOwner, NameOwner, LiteralKind,ArrayExprKind, TypeAscriptionOwner}
10}; 10};
11 11
12use crate::{ 12use crate::{
13 Path, Name, HirDatabase, Resolver,DefWithBody, Either, HirFileId, 13 Path, Name, HirDatabase, Resolver,DefWithBody, Either, HirFileId,
14 name::AsName, 14 name::AsName,
15 ids::{MacroCallId},
16 type_ref::{Mutability, TypeRef}, 15 type_ref::{Mutability, TypeRef},
17}; 16};
18use crate::{path::GenericArgs, ty::primitive::{IntTy, UncertainIntTy, FloatTy, UncertainFloatTy}}; 17use crate::{path::GenericArgs, ty::primitive::{IntTy, UncertainIntTy, FloatTy, UncertainFloatTy}};
@@ -826,21 +825,20 @@ where
826 .with_file_id(self.current_file_id); 825 .with_file_id(self.current_file_id);
827 826
828 if let Some(call_id) = self.resolver.resolve_macro_call(self.db, path, ast_id) { 827 if let Some(call_id) = self.resolver.resolve_macro_call(self.db, path, ast_id) {
829 if let Some(expr) = expand_macro_to_expr(self.db, call_id, e.token_tree()) { 828 if let Some(tt) = self.db.macro_expand(call_id).ok() {
830 log::debug!("macro expansion {}", expr.syntax().debug_dump()); 829 if let Some(expr) = mbe::token_tree_to_expr(&tt).ok() {
831 let old_file_id = 830 log::debug!("macro expansion {}", expr.syntax().debug_dump());
832 std::mem::replace(&mut self.current_file_id, call_id.into()); 831 let old_file_id =
833 let id = self.collect_expr(&expr); 832 std::mem::replace(&mut self.current_file_id, call_id.into());
834 self.current_file_id = old_file_id; 833 let id = self.collect_expr(&expr);
835 id 834 self.current_file_id = old_file_id;
836 } else { 835 return id;
837 // FIXME: Instead of just dropping the error from expansion 836 }
838 // report it
839 self.alloc_expr(Expr::Missing, syntax_ptr)
840 } 837 }
841 } else {
842 self.alloc_expr(Expr::Missing, syntax_ptr)
843 } 838 }
839 // FIXME: Instead of just dropping the error from expansion
840 // report it
841 self.alloc_expr(Expr::Missing, syntax_ptr)
844 } 842 }
845 } 843 }
846 } 844 }
@@ -999,20 +997,6 @@ where
999 } 997 }
1000} 998}
1001 999
1002fn expand_macro_to_expr(
1003 db: &impl HirDatabase,
1004 macro_call: MacroCallId,
1005 args: Option<&ast::TokenTree>,
1006) -> Option<TreeArc<ast::Expr>> {
1007 let rules = db.macro_def(macro_call.loc(db).def)?;
1008
1009 let args = mbe::ast_to_token_tree(args?)?.0;
1010
1011 let expanded = rules.expand(&args).ok()?;
1012
1013 mbe::token_tree_to_expr(&expanded).ok()
1014}
1015
1016pub(crate) fn body_with_source_map_query( 1000pub(crate) fn body_with_source_map_query(
1017 db: &impl HirDatabase, 1001 db: &impl HirDatabase,
1018 def: DefWithBody, 1002 def: DefWithBody,
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 1c71e21ea..2e52c5871 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -9,7 +9,7 @@ use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner};
9 9
10use crate::{ 10use crate::{
11 db::DefDatabase, 11 db::DefDatabase,
12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef 12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef
13}; 13};
14 14
15/// Data about a generic parameter (to a function, struct, impl, ...). 15/// Data about a generic parameter (to a function, struct, impl, ...).
@@ -157,6 +157,15 @@ impl From<Container> for GenericDef {
157 } 157 }
158} 158}
159 159
160impl From<crate::adt::AdtDef> for GenericDef {
161 fn from(adt: crate::adt::AdtDef) -> Self {
162 match adt {
163 AdtDef::Struct(s) => s.into(),
164 AdtDef::Enum(e) => e.into(),
165 }
166 }
167}
168
160pub trait HasGenericParams { 169pub trait HasGenericParams {
161 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>; 170 fn generic_params(self, db: &impl DefDatabase) -> Arc<GenericParams>;
162} 171}
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index b0e9b1f9a..ff4a81e59 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -63,47 +63,27 @@ impl HirFileId {
63 match file_id.0 { 63 match file_id.0 {
64 HirFileIdRepr::File(file_id) => db.parse(file_id), 64 HirFileIdRepr::File(file_id) => db.parse(file_id),
65 HirFileIdRepr::Macro(macro_call_id) => { 65 HirFileIdRepr::Macro(macro_call_id) => {
66 parse_macro(db, macro_call_id).unwrap_or_else(|err| { 66 match db.macro_expand(macro_call_id) {
67 // Note: 67 Ok(tt) => mbe::token_tree_to_ast_item_list(&tt),
68 // The final goal we would like to make all parse_macro success, 68 Err(err) => {
69 // such that the following log will not call anyway. 69 // Note:
70 log::warn!( 70 // The final goal we would like to make all parse_macro success,
71 "fail on macro_parse: (reason: {}) {}", 71 // such that the following log will not call anyway.
72 err, 72 log::warn!(
73 macro_call_id.debug_dump(db) 73 "fail on macro_parse: (reason: {}) {}",
74 ); 74 err,
75 75 macro_call_id.debug_dump(db)
76 // returning an empty string looks fishy... 76 );
77 SourceFile::parse("") 77
78 }) 78 // returning an empty string looks fishy...
79 SourceFile::parse("")
80 }
81 }
79 } 82 }
80 } 83 }
81 } 84 }
82} 85}
83 86
84fn parse_macro(
85 db: &impl DefDatabase,
86 macro_call_id: MacroCallId,
87) -> Result<TreeArc<SourceFile>, String> {
88 let loc = macro_call_id.loc(db);
89 let macro_call = loc.ast_id.to_node(db);
90 let (macro_arg, _) = macro_call
91 .token_tree()
92 .and_then(mbe::ast_to_token_tree)
93 .ok_or("Fail to args in to tt::TokenTree")?;
94
95 let macro_rules = db.macro_def(loc.def).ok_or("Fail to find macro definition")?;
96 let tt = macro_rules.expand(&macro_arg).map_err(|err| format!("{:?}", err))?;
97
98 // Set a hard limit for the expanded tt
99 let count = tt.count();
100 if count > 65536 {
101 return Err(format!("Total tokens count exceed limit : count = {}", count));
102 }
103
104 Ok(mbe::token_tree_to_ast_item_list(&tt))
105}
106
107#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 87#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
108enum HirFileIdRepr { 88enum HirFileIdRepr {
109 File(FileId), 89 File(FileId),
@@ -139,6 +119,31 @@ pub(crate) fn macro_def_query(db: &impl DefDatabase, id: MacroDefId) -> Option<A
139 Some(Arc::new(rules)) 119 Some(Arc::new(rules))
140} 120}
141 121
122pub(crate) fn macro_arg_query(db: &impl DefDatabase, id: MacroCallId) -> Option<Arc<tt::Subtree>> {
123 let loc = id.loc(db);
124 let macro_call = loc.ast_id.to_node(db);
125 let arg = macro_call.token_tree()?;
126 let (tt, _) = mbe::ast_to_token_tree(arg)?;
127 Some(Arc::new(tt))
128}
129
130pub(crate) fn macro_expand_query(
131 db: &impl DefDatabase,
132 id: MacroCallId,
133) -> Result<Arc<tt::Subtree>, String> {
134 let loc = id.loc(db);
135 let macro_arg = db.macro_arg(id).ok_or("Fail to args in to tt::TokenTree")?;
136
137 let macro_rules = db.macro_def(loc.def).ok_or("Fail to find macro definition")?;
138 let tt = macro_rules.expand(&macro_arg).map_err(|err| format!("{:?}", err))?;
139 // Set a hard limit for the expanded tt
140 let count = tt.count();
141 if count > 65536 {
142 return Err(format!("Total tokens count exceed limit : count = {}", count));
143 }
144 Ok(Arc::new(tt))
145}
146
142macro_rules! impl_intern_key { 147macro_rules! impl_intern_key {
143 ($name:ident) => { 148 ($name:ident) => {
144 impl salsa::InternKey for $name { 149 impl salsa::InternKey for $name {
@@ -349,3 +354,15 @@ impl MacroCallId {
349 ) 354 )
350 } 355 }
351} 356}
357
358/// This exists just for Chalk, because Chalk just has a single `StructId` where
359/// we have different kinds of ADTs, primitive types and special type
360/// constructors like tuples and function pointers.
361#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
362pub struct TypeCtorId(salsa::InternId);
363impl_intern_key!(TypeCtorId);
364
365/// This exists just for Chalk, because our ImplIds are only unique per module.
366#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
367pub struct GlobalImplId(salsa::InternId);
368impl_intern_key!(GlobalImplId);
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index bc9170cdc..707556ef8 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -6,7 +6,7 @@ use ra_syntax::ast;
6use rustc_hash::FxHashMap; 6use rustc_hash::FxHashMap;
7 7
8use crate::{ 8use crate::{
9 ModuleDef, 9 ModuleDef, Trait,
10 code_model_api::Crate, 10 code_model_api::Crate,
11 MacroCallId, 11 MacroCallId,
12 MacroCallLoc, 12 MacroCallLoc,
@@ -18,7 +18,6 @@ use crate::{
18 expr::{scope::{ExprScopes, ScopeId}, PatId}, 18 expr::{scope::{ExprScopes, ScopeId}, PatId},
19 impl_block::ImplBlock, 19 impl_block::ImplBlock,
20 path::Path, 20 path::Path,
21 Trait,
22}; 21};
23 22
24#[derive(Debug, Clone, Default)] 23#[derive(Debug, Clone, Default)]
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 06d99351e..31bf13425 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -387,7 +387,16 @@ impl SourceAnalyzer {
387 name: Option<&Name>, 387 name: Option<&Name>,
388 callback: impl FnMut(&Ty, Function) -> Option<T>, 388 callback: impl FnMut(&Ty, Function) -> Option<T>,
389 ) -> Option<T> { 389 ) -> Option<T> {
390 ty.iterate_method_candidates(db, &self.resolver, name, callback) 390 // There should be no inference vars in types passed here
391 // FIXME check that?
392 let canonical = crate::ty::Canonical { value: ty, num_vars: 0 };
393 crate::ty::method_resolution::iterate_method_candidates(
394 &canonical,
395 db,
396 &self.resolver,
397 name,
398 callback,
399 )
391 } 400 }
392 401
393 #[cfg(test)] 402 #[cfg(test)]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 12e10c751..f4eee835f 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -13,9 +13,10 @@ mod infer;
13pub(crate) mod display; 13pub(crate) mod display;
14 14
15use std::sync::Arc; 15use std::sync::Arc;
16use std::ops::Deref;
16use std::{fmt, mem}; 17use std::{fmt, mem};
17 18
18use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait}; 19use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
19use display::{HirDisplay, HirFormatter}; 20use display::{HirDisplay, HirFormatter};
20 21
21pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig}; 22pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig};
@@ -81,13 +82,13 @@ pub enum TypeCtor {
81 /// fn foo() -> i32 { 1 } 82 /// fn foo() -> i32 { 1 }
82 /// let bar: fn() -> i32 = foo; 83 /// let bar: fn() -> i32 = foo;
83 /// ``` 84 /// ```
84 FnPtr, 85 FnPtr { num_args: u16 },
85 86
86 /// The never type `!`. 87 /// The never type `!`.
87 Never, 88 Never,
88 89
89 /// A tuple type. For example, `(i32, bool)`. 90 /// A tuple type. For example, `(i32, bool)`.
90 Tuple, 91 Tuple { cardinality: u16 },
91} 92}
92 93
93/// A nominal type with (maybe 0) type parameters. This might be a primitive 94/// A nominal type with (maybe 0) type parameters. This might be a primitive
@@ -118,9 +119,14 @@ pub enum Ty {
118 /// surrounding impl, then the current function). 119 /// surrounding impl, then the current function).
119 idx: u32, 120 idx: u32,
120 /// The name of the parameter, for displaying. 121 /// The name of the parameter, for displaying.
122 // FIXME get rid of this
121 name: Name, 123 name: Name,
122 }, 124 },
123 125
126 /// A bound type variable. Only used during trait resolution to represent
127 /// Chalk variables.
128 Bound(u32),
129
124 /// A type variable used during type checking. Not to be confused with a 130 /// A type variable used during type checking. Not to be confused with a
125 /// type parameter. 131 /// type parameter.
126 Infer(InferTy), 132 Infer(InferTy),
@@ -150,14 +156,6 @@ impl Substs {
150 Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into()) 156 Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into())
151 } 157 }
152 158
153 pub fn iter(&self) -> impl Iterator<Item = &Ty> {
154 self.0.iter()
155 }
156
157 pub fn len(&self) -> usize {
158 self.0.len()
159 }
160
161 pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { 159 pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
162 // Without an Arc::make_mut_slice, we can't avoid the clone here: 160 // Without an Arc::make_mut_slice, we can't avoid the clone here:
163 let mut v: Vec<_> = self.0.iter().cloned().collect(); 161 let mut v: Vec<_> = self.0.iter().cloned().collect();
@@ -173,6 +171,30 @@ impl Substs {
173 } 171 }
174 &self.0[0] 172 &self.0[0]
175 } 173 }
174
175 /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
176 pub fn identity(generic_params: &GenericParams) -> Substs {
177 Substs(
178 generic_params
179 .params_including_parent()
180 .into_iter()
181 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
182 .collect::<Vec<_>>()
183 .into(),
184 )
185 }
186
187 /// Return Substs that replace each parameter by a bound variable.
188 pub fn bound_vars(generic_params: &GenericParams) -> Substs {
189 Substs(
190 generic_params
191 .params_including_parent()
192 .into_iter()
193 .map(|p| Ty::Bound(p.idx))
194 .collect::<Vec<_>>()
195 .into(),
196 )
197 }
176} 198}
177 199
178impl From<Vec<Ty>> for Substs { 200impl From<Vec<Ty>> for Substs {
@@ -181,6 +203,14 @@ impl From<Vec<Ty>> for Substs {
181 } 203 }
182} 204}
183 205
206impl Deref for Substs {
207 type Target = [Ty];
208
209 fn deref(&self) -> &[Ty] {
210 &self.0
211 }
212}
213
184/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait. 214/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
185/// Name to be bikeshedded: TraitBound? TraitImplements? 215/// Name to be bikeshedded: TraitBound? TraitImplements?
186#[derive(Clone, PartialEq, Eq, Debug, Hash)] 216#[derive(Clone, PartialEq, Eq, Debug, Hash)]
@@ -192,10 +222,29 @@ pub struct TraitRef {
192 222
193impl TraitRef { 223impl TraitRef {
194 pub fn self_ty(&self) -> &Ty { 224 pub fn self_ty(&self) -> &Ty {
195 &self.substs.0[0] 225 &self.substs[0]
226 }
227
228 pub fn subst(mut self, substs: &Substs) -> TraitRef {
229 self.substs.walk_mut(&mut |ty_mut| {
230 let ty = mem::replace(ty_mut, Ty::Unknown);
231 *ty_mut = ty.subst(substs);
232 });
233 self
196 } 234 }
197} 235}
198 236
237/// Basically a claim (currently not validated / checked) that the contained
238/// type / trait ref contains no inference variables; any inference variables it
239/// contained have been replaced by bound variables, and `num_vars` tells us how
240/// many there are. This is used to erase irrelevant differences between types
241/// before using them in queries.
242#[derive(Debug, Clone, PartialEq, Eq, Hash)]
243pub(crate) struct Canonical<T> {
244 pub value: T,
245 pub num_vars: usize,
246}
247
199/// A function signature as seen by type inference: Several parameter types and 248/// A function signature as seen by type inference: Several parameter types and
200/// one return type. 249/// one return type.
201#[derive(Clone, PartialEq, Eq, Debug)] 250#[derive(Clone, PartialEq, Eq, Debug)]
@@ -250,7 +299,7 @@ impl Ty {
250 Ty::Apply(ApplicationTy { ctor, parameters }) 299 Ty::Apply(ApplicationTy { ctor, parameters })
251 } 300 }
252 pub fn unit() -> Self { 301 pub fn unit() -> Self {
253 Ty::apply(TypeCtor::Tuple, Substs::empty()) 302 Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
254 } 303 }
255 304
256 pub fn walk(&self, f: &mut impl FnMut(&Ty)) { 305 pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
@@ -260,7 +309,7 @@ impl Ty {
260 t.walk(f); 309 t.walk(f);
261 } 310 }
262 } 311 }
263 Ty::Param { .. } | Ty::Infer(_) | Ty::Unknown => {} 312 Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
264 } 313 }
265 f(self); 314 f(self);
266 } 315 }
@@ -270,7 +319,7 @@ impl Ty {
270 Ty::Apply(a_ty) => { 319 Ty::Apply(a_ty) => {
271 a_ty.parameters.walk_mut(f); 320 a_ty.parameters.walk_mut(f);
272 } 321 }
273 Ty::Param { .. } | Ty::Infer(_) | Ty::Unknown => {} 322 Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
274 } 323 }
275 f(self); 324 f(self);
276 } 325 }
@@ -303,7 +352,9 @@ impl Ty {
303 352
304 pub fn as_tuple(&self) -> Option<&Substs> { 353 pub fn as_tuple(&self) -> Option<&Substs> {
305 match self { 354 match self {
306 Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple, parameters }) => Some(parameters), 355 Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
356 Some(parameters)
357 }
307 _ => None, 358 _ => None,
308 } 359 }
309 } 360 }
@@ -331,7 +382,7 @@ impl Ty {
331 fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> { 382 fn callable_sig(&self, db: &impl HirDatabase) -> Option<FnSig> {
332 match self { 383 match self {
333 Ty::Apply(a_ty) => match a_ty.ctor { 384 Ty::Apply(a_ty) => match a_ty.ctor {
334 TypeCtor::FnPtr => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)), 385 TypeCtor::FnPtr { .. } => Some(FnSig::from_fn_ptr_substs(&a_ty.parameters)),
335 TypeCtor::FnDef(def) => { 386 TypeCtor::FnDef(def) => {
336 let sig = db.callable_item_signature(def); 387 let sig = db.callable_item_signature(def);
337 Some(sig.subst(&a_ty.parameters)) 388 Some(sig.subst(&a_ty.parameters))
@@ -362,16 +413,20 @@ impl Ty {
362 pub fn subst(self, substs: &Substs) -> Ty { 413 pub fn subst(self, substs: &Substs) -> Ty {
363 self.fold(&mut |ty| match ty { 414 self.fold(&mut |ty| match ty {
364 Ty::Param { idx, name } => { 415 Ty::Param { idx, name } => {
365 if (idx as usize) < substs.0.len() { 416 substs.get(idx as usize).cloned().unwrap_or(Ty::Param { idx, name })
366 substs.0[idx as usize].clone()
367 } else {
368 Ty::Param { idx, name }
369 }
370 } 417 }
371 ty => ty, 418 ty => ty,
372 }) 419 })
373 } 420 }
374 421
422 /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
423 pub fn subst_bound_vars(self, substs: &Substs) -> Ty {
424 self.fold(&mut |ty| match ty {
425 Ty::Bound(idx) => substs.get(idx as usize).cloned().unwrap_or(Ty::Bound(idx)),
426 ty => ty,
427 })
428 }
429
375 /// Returns the type parameters of this type if it has some (i.e. is an ADT 430 /// Returns the type parameters of this type if it has some (i.e. is an ADT
376 /// or function); so if `self` is `Option<u32>`, this returns the `u32`. 431 /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
377 fn substs(&self) -> Option<Substs> { 432 fn substs(&self) -> Option<Substs> {
@@ -413,17 +468,17 @@ impl HirDisplay for ApplicationTy {
413 write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?; 468 write!(f, "&{}{}", m.as_keyword_for_ref(), t.display(f.db))?;
414 } 469 }
415 TypeCtor::Never => write!(f, "!")?, 470 TypeCtor::Never => write!(f, "!")?,
416 TypeCtor::Tuple => { 471 TypeCtor::Tuple { .. } => {
417 let ts = &self.parameters; 472 let ts = &self.parameters;
418 if ts.0.len() == 1 { 473 if ts.len() == 1 {
419 write!(f, "({},)", ts.0[0].display(f.db))?; 474 write!(f, "({},)", ts[0].display(f.db))?;
420 } else { 475 } else {
421 write!(f, "(")?; 476 write!(f, "(")?;
422 f.write_joined(&*ts.0, ", ")?; 477 f.write_joined(&*ts.0, ", ")?;
423 write!(f, ")")?; 478 write!(f, ")")?;
424 } 479 }
425 } 480 }
426 TypeCtor::FnPtr => { 481 TypeCtor::FnPtr { .. } => {
427 let sig = FnSig::from_fn_ptr_substs(&self.parameters); 482 let sig = FnSig::from_fn_ptr_substs(&self.parameters);
428 write!(f, "fn(")?; 483 write!(f, "fn(")?;
429 f.write_joined(sig.params(), ", ")?; 484 f.write_joined(sig.params(), ", ")?;
@@ -440,7 +495,7 @@ impl HirDisplay for ApplicationTy {
440 CallableDef::Function(_) => write!(f, "fn {}", name)?, 495 CallableDef::Function(_) => write!(f, "fn {}", name)?,
441 CallableDef::Struct(_) | CallableDef::EnumVariant(_) => write!(f, "{}", name)?, 496 CallableDef::Struct(_) | CallableDef::EnumVariant(_) => write!(f, "{}", name)?,
442 } 497 }
443 if self.parameters.0.len() > 0 { 498 if self.parameters.len() > 0 {
444 write!(f, "<")?; 499 write!(f, "<")?;
445 f.write_joined(&*self.parameters.0, ", ")?; 500 f.write_joined(&*self.parameters.0, ", ")?;
446 write!(f, ">")?; 501 write!(f, ">")?;
@@ -456,7 +511,7 @@ impl HirDisplay for ApplicationTy {
456 } 511 }
457 .unwrap_or_else(Name::missing); 512 .unwrap_or_else(Name::missing);
458 write!(f, "{}", name)?; 513 write!(f, "{}", name)?;
459 if self.parameters.0.len() > 0 { 514 if self.parameters.len() > 0 {
460 write!(f, "<")?; 515 write!(f, "<")?;
461 f.write_joined(&*self.parameters.0, ", ")?; 516 f.write_joined(&*self.parameters.0, ", ")?;
462 write!(f, ">")?; 517 write!(f, ">")?;
@@ -472,6 +527,7 @@ impl HirDisplay for Ty {
472 match self { 527 match self {
473 Ty::Apply(a_ty) => a_ty.hir_fmt(f)?, 528 Ty::Apply(a_ty) => a_ty.hir_fmt(f)?,
474 Ty::Param { name, .. } => write!(f, "{}", name)?, 529 Ty::Param { name, .. } => write!(f, "{}", name)?,
530 Ty::Bound(idx) => write!(f, "?{}", idx)?,
475 Ty::Unknown => write!(f, "{{unknown}}")?, 531 Ty::Unknown => write!(f, "{{unknown}}")?,
476 Ty::Infer(..) => write!(f, "_")?, 532 Ty::Infer(..) => write!(f, "_")?,
477 } 533 }
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index c7772a7f6..edce1afe7 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -44,9 +44,12 @@ use crate::{
44}; 44};
45use super::{ 45use super::{
46 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef, 46 Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
47 traits::{ Solution, Obligation, Guidance}, 47 traits::{Solution, Obligation, Guidance},
48 method_resolution,
48}; 49};
49 50
51mod unify;
52
50/// The entry point of type inference. 53/// The entry point of type inference.
51pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> { 54pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
52 db.check_canceled(); 55 db.check_canceled();
@@ -321,30 +324,29 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
321 fn resolve_obligations_as_possible(&mut self) { 324 fn resolve_obligations_as_possible(&mut self) {
322 let obligations = mem::replace(&mut self.obligations, Vec::new()); 325 let obligations = mem::replace(&mut self.obligations, Vec::new());
323 for obligation in obligations { 326 for obligation in obligations {
324 // FIXME resolve types in the obligation first 327 let (solution, canonicalized) = match &obligation {
325 let (solution, var_mapping) = match &obligation {
326 Obligation::Trait(tr) => { 328 Obligation::Trait(tr) => {
327 let (tr, var_mapping) = super::traits::canonicalize(tr.clone()); 329 let canonicalized = self.canonicalizer().canonicalize_trait_ref(tr.clone());
328 (self.db.implements(tr), var_mapping) 330 (
331 super::traits::implements(
332 self.db,
333 self.resolver.krate().unwrap(),
334 canonicalized.value.clone(),
335 ),
336 canonicalized,
337 )
329 } 338 }
330 }; 339 };
331 match solution { 340 match solution {
332 Some(Solution::Unique(substs)) => { 341 Some(Solution::Unique(substs)) => {
333 for (i, subst) in substs.0.iter().enumerate() { 342 canonicalized.apply_solution(self, substs.0);
334 let uncanonical = var_mapping[i];
335 // FIXME the subst may contain type variables, which would need to be mapped back as well
336 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
337 }
338 } 343 }
339 Some(Solution::Ambig(Guidance::Definite(substs))) => { 344 Some(Solution::Ambig(Guidance::Definite(substs))) => {
340 for (i, subst) in substs.0.iter().enumerate() { 345 canonicalized.apply_solution(self, substs.0);
341 let uncanonical = var_mapping[i];
342 // FIXME the subst may contain type variables, which would need to be mapped back as well
343 self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
344 }
345 self.obligations.push(obligation); 346 self.obligations.push(obligation);
346 } 347 }
347 Some(_) => { 348 Some(_) => {
349 // FIXME use this when trying to resolve everything at the end
348 self.obligations.push(obligation); 350 self.obligations.push(obligation);
349 } 351 }
350 None => { 352 None => {
@@ -737,14 +739,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
737 }; 739 };
738 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown)); 740 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
739 741
740 let inner_tys = args 742 let inner_tys: Substs = args
741 .iter() 743 .iter()
742 .zip(expectations_iter) 744 .zip(expectations_iter)
743 .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm)) 745 .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
744 .collect::<Vec<_>>() 746 .collect::<Vec<_>>()
745 .into(); 747 .into();
746 748
747 Ty::apply(TypeCtor::Tuple, Substs(inner_tys)) 749 Ty::apply(TypeCtor::Tuple { cardinality: inner_tys.len() as u16 }, inner_tys)
748 } 750 }
749 Pat::Ref { pat, mutability } => { 751 Pat::Ref { pat, mutability } => {
750 let expectation = match expected.as_reference() { 752 let expectation = match expected.as_reference() {
@@ -877,9 +879,16 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
877 generic_args: Option<&GenericArgs>, 879 generic_args: Option<&GenericArgs>,
878 ) -> Ty { 880 ) -> Ty {
879 let receiver_ty = self.infer_expr(receiver, &Expectation::none()); 881 let receiver_ty = self.infer_expr(receiver, &Expectation::none());
880 let resolved = receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver); 882 let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
883 let resolved = method_resolution::lookup_method(
884 &canonicalized_receiver.value,
885 self.db,
886 method_name,
887 &self.resolver,
888 );
881 let (derefed_receiver_ty, method_ty, def_generics) = match resolved { 889 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
882 Some((ty, func)) => { 890 Some((ty, func)) => {
891 let ty = canonicalized_receiver.decanonicalize_ty(ty);
883 self.write_method_resolution(tgt_expr, func); 892 self.write_method_resolution(tgt_expr, func);
884 ( 893 (
885 ty, 894 ty,
@@ -1064,7 +1073,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
1064 .autoderef(self.db) 1073 .autoderef(self.db)
1065 .find_map(|derefed_ty| match derefed_ty { 1074 .find_map(|derefed_ty| match derefed_ty {
1066 Ty::Apply(a_ty) => match a_ty.ctor { 1075 Ty::Apply(a_ty) => match a_ty.ctor {
1067 TypeCtor::Tuple => { 1076 TypeCtor::Tuple { .. } => {
1068 let i = name.to_string().parse::<usize>().ok(); 1077 let i = name.to_string().parse::<usize>().ok();
1069 i.and_then(|i| a_ty.parameters.0.get(i).cloned()) 1078 i.and_then(|i| a_ty.parameters.0.get(i).cloned())
1070 } 1079 }
@@ -1175,7 +1184,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
1175 ty_vec.push(self.infer_expr(*arg, &Expectation::none())); 1184 ty_vec.push(self.infer_expr(*arg, &Expectation::none()));
1176 } 1185 }
1177 1186
1178 Ty::apply(TypeCtor::Tuple, Substs(ty_vec.into())) 1187 Ty::apply(
1188 TypeCtor::Tuple { cardinality: ty_vec.len() as u16 },
1189 Substs(ty_vec.into()),
1190 )
1179 } 1191 }
1180 Expr::Array(array) => { 1192 Expr::Array(array) => {
1181 let elem_ty = match &expected.ty { 1193 let elem_ty = match &expected.ty {
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
new file mode 100644
index 000000000..8ca7e957d
--- /dev/null
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -0,0 +1,122 @@
1//! Unification and canonicalization logic.
2
3use crate::db::HirDatabase;
4use crate::ty::{Ty, Canonical, TraitRef, InferTy};
5use super::InferenceContext;
6
7impl<'a, D: HirDatabase> InferenceContext<'a, D> {
8 pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
9 where
10 'a: 'b,
11 {
12 Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
13 }
14}
15
16pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
17where
18 'a: 'b,
19{
20 ctx: &'b mut InferenceContext<'a, D>,
21 free_vars: Vec<InferTy>,
22 /// A stack of type variables that is used to detect recursive types (which
23 /// are an error, but we need to protect against them to avoid stack
24 /// overflows).
25 var_stack: Vec<super::TypeVarId>,
26}
27
28pub(super) struct Canonicalized<T> {
29 pub value: Canonical<T>,
30 free_vars: Vec<InferTy>,
31}
32
33impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
34where
35 'a: 'b,
36{
37 fn add(&mut self, free_var: InferTy) -> usize {
38 self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
39 let next_index = self.free_vars.len();
40 self.free_vars.push(free_var);
41 next_index
42 })
43 }
44
45 fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty {
46 ty.fold(&mut |ty| match ty {
47 Ty::Infer(tv) => {
48 let inner = tv.to_inner();
49 if self.var_stack.contains(&inner) {
50 // recursive type
51 return tv.fallback_value();
52 }
53 if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() {
54 self.var_stack.push(inner);
55 let result = self.do_canonicalize_ty(known_ty.clone());
56 self.var_stack.pop();
57 result
58 } else {
59 let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner));
60 let position = self.add(free_var);
61 Ty::Bound(position as u32)
62 }
63 }
64 _ => ty,
65 })
66 }
67
68 fn do_canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> TraitRef {
69 let substs = trait_ref
70 .substs
71 .iter()
72 .map(|ty| self.do_canonicalize_ty(ty.clone()))
73 .collect::<Vec<_>>();
74 TraitRef { trait_: trait_ref.trait_, substs: substs.into() }
75 }
76
77 fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
78 Canonicalized {
79 value: Canonical { value: result, num_vars: self.free_vars.len() },
80 free_vars: self.free_vars,
81 }
82 }
83
84 pub fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
85 let result = self.do_canonicalize_ty(ty);
86 self.into_canonicalized(result)
87 }
88
89 pub fn canonicalize_trait_ref(mut self, trait_ref: TraitRef) -> Canonicalized<TraitRef> {
90 let result = self.do_canonicalize_trait_ref(trait_ref);
91 self.into_canonicalized(result)
92 }
93}
94
95impl<T> Canonicalized<T> {
96 pub fn decanonicalize_ty(&self, ty: Ty) -> Ty {
97 ty.fold(&mut |ty| match ty {
98 Ty::Bound(idx) => {
99 if (idx as usize) < self.free_vars.len() {
100 Ty::Infer(self.free_vars[idx as usize].clone())
101 } else {
102 Ty::Bound(idx)
103 }
104 }
105 ty => ty,
106 })
107 }
108
109 pub fn apply_solution(
110 &self,
111 ctx: &mut InferenceContext<'_, impl HirDatabase>,
112 solution: Canonical<Vec<Ty>>,
113 ) {
114 // the solution may contain new variables, which we need to convert to new inference vars
115 let new_vars =
116 (0..solution.num_vars).map(|_| ctx.new_type_var()).collect::<Vec<_>>().into();
117 for (i, ty) in solution.value.into_iter().enumerate() {
118 let var = self.free_vars[i].clone();
119 ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
120 }
121 }
122}
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 7fac084ce..8bab7e54b 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -29,7 +29,10 @@ impl Ty {
29 TypeRef::Tuple(inner) => { 29 TypeRef::Tuple(inner) => {
30 let inner_tys = 30 let inner_tys =
31 inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); 31 inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
32 Ty::apply(TypeCtor::Tuple, Substs(inner_tys.into())) 32 Ty::apply(
33 TypeCtor::Tuple { cardinality: inner_tys.len() as u16 },
34 Substs(inner_tys.into()),
35 )
33 } 36 }
34 TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path), 37 TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path),
35 TypeRef::RawPtr(inner, mutability) => { 38 TypeRef::RawPtr(inner, mutability) => {
@@ -53,7 +56,7 @@ impl Ty {
53 let inner_tys = 56 let inner_tys =
54 params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>(); 57 params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
55 let sig = Substs(inner_tys.into()); 58 let sig = Substs(inner_tys.into());
56 Ty::apply(TypeCtor::FnPtr, sig) 59 Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig)
57 } 60 }
58 TypeRef::Error => Ty::Unknown, 61 TypeRef::Error => Ty::Unknown,
59 } 62 }
@@ -238,6 +241,11 @@ impl TraitRef {
238 let segment = path.segments.last().expect("path should have at least one segment"); 241 let segment = path.segments.last().expect("path should have at least one segment");
239 substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true) 242 substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true)
240 } 243 }
244
245 pub(crate) fn for_trait(db: &impl HirDatabase, trait_: Trait) -> TraitRef {
246 let substs = Substs::identity(&trait_.generic_params(db));
247 TraitRef { trait_, substs }
248 }
241} 249}
242 250
243/// Build the declared type of an item. This depends on the namespace; e.g. for 251/// Build the declared type of an item. This depends on the namespace; e.g. for
@@ -299,7 +307,7 @@ fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig {
299/// function body. 307/// function body.
300fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty { 308fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty {
301 let generics = def.generic_params(db); 309 let generics = def.generic_params(db);
302 let substs = make_substs(&generics); 310 let substs = Substs::identity(&generics);
303 Ty::apply(TypeCtor::FnDef(def.into()), substs) 311 Ty::apply(TypeCtor::FnDef(def.into()), substs)
304} 312}
305 313
@@ -341,7 +349,7 @@ fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty {
341 return type_for_struct(db, def); // Unit struct 349 return type_for_struct(db, def); // Unit struct
342 } 350 }
343 let generics = def.generic_params(db); 351 let generics = def.generic_params(db);
344 let substs = make_substs(&generics); 352 let substs = Substs::identity(&generics);
345 Ty::apply(TypeCtor::FnDef(def.into()), substs) 353 Ty::apply(TypeCtor::FnDef(def.into()), substs)
346} 354}
347 355
@@ -357,7 +365,7 @@ fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant)
357 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref)) 365 .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
358 .collect::<Vec<_>>(); 366 .collect::<Vec<_>>();
359 let generics = def.parent_enum(db).generic_params(db); 367 let generics = def.parent_enum(db).generic_params(db);
360 let substs = make_substs(&generics); 368 let substs = Substs::identity(&generics);
361 let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs); 369 let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs);
362 FnSig::from_params_and_return(params, ret) 370 FnSig::from_params_and_return(params, ret)
363} 371}
@@ -369,36 +377,25 @@ fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) ->
369 return type_for_enum(db, def.parent_enum(db)); // Unit variant 377 return type_for_enum(db, def.parent_enum(db)); // Unit variant
370 } 378 }
371 let generics = def.parent_enum(db).generic_params(db); 379 let generics = def.parent_enum(db).generic_params(db);
372 let substs = make_substs(&generics); 380 let substs = Substs::identity(&generics);
373 Ty::apply(TypeCtor::FnDef(def.into()), substs) 381 Ty::apply(TypeCtor::FnDef(def.into()), substs)
374} 382}
375 383
376fn make_substs(generics: &GenericParams) -> Substs {
377 Substs(
378 generics
379 .params_including_parent()
380 .into_iter()
381 .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
382 .collect::<Vec<_>>()
383 .into(),
384 )
385}
386
387fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty { 384fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty {
388 let generics = s.generic_params(db); 385 let generics = s.generic_params(db);
389 Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) 386 Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
390} 387}
391 388
392fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty { 389fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty {
393 let generics = s.generic_params(db); 390 let generics = s.generic_params(db);
394 Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics)) 391 Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
395} 392}
396 393
397fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty { 394fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty {
398 let generics = t.generic_params(db); 395 let generics = t.generic_params(db);
399 let resolver = t.resolver(db); 396 let resolver = t.resolver(db);
400 let type_ref = t.type_ref(db); 397 let type_ref = t.type_ref(db);
401 let substs = make_substs(&generics); 398 let substs = Substs::identity(&generics);
402 let inner = Ty::from_hir(db, &resolver, &type_ref); 399 let inner = Ty::from_hir(db, &resolver, &type_ref);
403 inner.subst(&substs) 400 inner.subst(&substs)
404} 401}
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index ea6e0dc0f..607e9ba79 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -16,7 +16,7 @@ use crate::{
16 generics::HasGenericParams, 16 generics::HasGenericParams,
17 ty::primitive::{UncertainIntTy, UncertainFloatTy} 17 ty::primitive::{UncertainIntTy, UncertainFloatTy}
18}; 18};
19use super::{TraitRef, Substs}; 19use super::{TraitRef, Canonical};
20 20
21/// This is used as a key for indexing impls. 21/// This is used as a key for indexing impls.
22#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 22#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -130,124 +130,122 @@ fn def_crate(db: &impl HirDatabase, cur_crate: Crate, ty: &Ty) -> Option<Crate>
130 } 130 }
131} 131}
132 132
133impl Ty { 133/// Look up the method with the given name, returning the actual autoderefed
134 /// Look up the method with the given name, returning the actual autoderefed 134/// receiver type (but without autoref applied yet).
135 /// receiver type (but without autoref applied yet). 135pub(crate) fn lookup_method(
136 pub(crate) fn lookup_method( 136 ty: &Canonical<Ty>,
137 self, 137 db: &impl HirDatabase,
138 db: &impl HirDatabase, 138 name: &Name,
139 name: &Name, 139 resolver: &Resolver,
140 resolver: &Resolver, 140) -> Option<(Ty, Function)> {
141 ) -> Option<(Ty, Function)> { 141 iterate_method_candidates(ty, db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
142 self.iterate_method_candidates(db, resolver, Some(name), |ty, f| Some((ty.clone(), f))) 142}
143 }
144 143
145 // This would be nicer if it just returned an iterator, but that runs into 144// This would be nicer if it just returned an iterator, but that runs into
146 // lifetime problems, because we need to borrow temp `CrateImplBlocks`. 145// lifetime problems, because we need to borrow temp `CrateImplBlocks`.
147 pub(crate) fn iterate_method_candidates<T>( 146pub(crate) fn iterate_method_candidates<T>(
148 self, 147 ty: &Canonical<Ty>,
149 db: &impl HirDatabase, 148 db: &impl HirDatabase,
150 resolver: &Resolver, 149 resolver: &Resolver,
151 name: Option<&Name>, 150 name: Option<&Name>,
152 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 151 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
153 ) -> Option<T> { 152) -> Option<T> {
154 // For method calls, rust first does any number of autoderef, and then one 153 // For method calls, rust first does any number of autoderef, and then one
155 // autoref (i.e. when the method takes &self or &mut self). We just ignore 154 // autoref (i.e. when the method takes &self or &mut self). We just ignore
156 // the autoref currently -- when we find a method matching the given name, 155 // the autoref currently -- when we find a method matching the given name,
157 // we assume it fits. 156 // we assume it fits.
158 157
159 // Also note that when we've got a receiver like &S, even if the method we 158 // Also note that when we've got a receiver like &S, even if the method we
160 // find in the end takes &self, we still do the autoderef step (just as 159 // find in the end takes &self, we still do the autoderef step (just as
161 // rustc does an autoderef and then autoref again). 160 // rustc does an autoderef and then autoref again).
162 161
163 let krate = resolver.krate()?; 162 let krate = resolver.krate()?;
164 for derefed_ty in self.autoderef(db) { 163 for derefed_ty in ty.value.clone().autoderef(db) {
165 if let Some(result) = 164 let derefed_ty = Canonical { value: derefed_ty, num_vars: ty.num_vars };
166 derefed_ty.iterate_inherent_methods(db, name, krate, &mut callback) 165 if let Some(result) = iterate_inherent_methods(&derefed_ty, db, name, krate, &mut callback)
167 { 166 {
168 return Some(result); 167 return Some(result);
169 } 168 }
170 if let Some(result) = 169 if let Some(result) =
171 derefed_ty.iterate_trait_method_candidates(db, resolver, name, &mut callback) 170 iterate_trait_method_candidates(&derefed_ty, db, resolver, name, &mut callback)
172 { 171 {
173 return Some(result); 172 return Some(result);
174 }
175 } 173 }
176 None
177 } 174 }
175 None
176}
178 177
179 fn iterate_trait_method_candidates<T>( 178fn iterate_trait_method_candidates<T>(
180 &self, 179 ty: &Canonical<Ty>,
181 db: &impl HirDatabase, 180 db: &impl HirDatabase,
182 resolver: &Resolver, 181 resolver: &Resolver,
183 name: Option<&Name>, 182 name: Option<&Name>,
184 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 183 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
185 ) -> Option<T> { 184) -> Option<T> {
186 'traits: for t in resolver.traits_in_scope() { 185 let krate = resolver.krate()?;
187 let data = t.trait_data(db); 186 'traits: for t in resolver.traits_in_scope() {
188 // we'll be lazy about checking whether the type implements the 187 let data = t.trait_data(db);
189 // trait, but if we find out it doesn't, we'll skip the rest of the 188 // we'll be lazy about checking whether the type implements the
190 // iteration 189 // trait, but if we find out it doesn't, we'll skip the rest of the
191 let mut known_implemented = false; 190 // iteration
192 for item in data.items() { 191 let mut known_implemented = false;
193 match item { 192 for item in data.items() {
194 &TraitItem::Function(m) => { 193 match item {
195 let sig = m.signature(db); 194 &TraitItem::Function(m) => {
196 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { 195 let sig = m.signature(db);
197 if !known_implemented { 196 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
198 let trait_ref = TraitRef { 197 if !known_implemented {
199 trait_: t, 198 let trait_ref = canonical_trait_ref(db, t, ty.clone());
200 substs: fresh_substs_for_trait(db, t, self.clone()), 199 // FIXME cache this implements check (without solution) in a query?
201 }; 200 if super::traits::implements(db, krate, trait_ref).is_none() {
202 let (trait_ref, _) = super::traits::canonicalize(trait_ref); 201 continue 'traits;
203 if db.implements(trait_ref).is_none() {
204 continue 'traits;
205 }
206 }
207 known_implemented = true;
208 if let Some(result) = callback(self, m) {
209 return Some(result);
210 } 202 }
211 } 203 }
204 known_implemented = true;
205 if let Some(result) = callback(&ty.value, m) {
206 return Some(result);
207 }
212 } 208 }
213 _ => {}
214 } 209 }
210 _ => {}
215 } 211 }
216 } 212 }
217 None
218 } 213 }
214 None
215}
219 216
220 fn iterate_inherent_methods<T>( 217fn iterate_inherent_methods<T>(
221 &self, 218 ty: &Canonical<Ty>,
222 db: &impl HirDatabase, 219 db: &impl HirDatabase,
223 name: Option<&Name>, 220 name: Option<&Name>,
224 krate: Crate, 221 krate: Crate,
225 mut callback: impl FnMut(&Ty, Function) -> Option<T>, 222 mut callback: impl FnMut(&Ty, Function) -> Option<T>,
226 ) -> Option<T> { 223) -> Option<T> {
227 let krate = match def_crate(db, krate, self) { 224 let krate = match def_crate(db, krate, &ty.value) {
228 Some(krate) => krate, 225 Some(krate) => krate,
229 None => return None, 226 None => return None,
230 }; 227 };
231 let impls = db.impls_in_crate(krate); 228 let impls = db.impls_in_crate(krate);
232 229
233 for impl_block in impls.lookup_impl_blocks(self) { 230 for impl_block in impls.lookup_impl_blocks(&ty.value) {
234 for item in impl_block.items(db) { 231 for item in impl_block.items(db) {
235 match item { 232 match item {
236 ImplItem::Method(f) => { 233 ImplItem::Method(f) => {
237 let sig = f.signature(db); 234 let sig = f.signature(db);
238 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() { 235 if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
239 if let Some(result) = callback(self, f) { 236 if let Some(result) = callback(&ty.value, f) {
240 return Some(result); 237 return Some(result);
241 }
242 } 238 }
243 } 239 }
244 _ => {}
245 } 240 }
241 _ => {}
246 } 242 }
247 } 243 }
248 None
249 } 244 }
245 None
246}
250 247
248impl Ty {
251 // This would be nicer if it just returned an iterator, but that runs into 249 // This would be nicer if it just returned an iterator, but that runs into
252 // lifetime problems, because we need to borrow temp `CrateImplBlocks`. 250 // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
253 pub fn iterate_impl_items<T>( 251 pub fn iterate_impl_items<T>(
@@ -271,15 +269,26 @@ impl Ty {
271} 269}
272 270
273/// This creates Substs for a trait with the given Self type and type variables 271/// This creates Substs for a trait with the given Self type and type variables
274/// for all other parameters. This is kind of a hack since these aren't 'real' 272/// for all other parameters, to query Chalk with it.
275/// type variables; the resulting trait reference is just used for the 273fn canonical_trait_ref(
276/// preliminary method candidate check. 274 db: &impl HirDatabase,
277fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs { 275 trait_: Trait,
276 self_ty: Canonical<Ty>,
277) -> Canonical<TraitRef> {
278 let mut substs = Vec::new(); 278 let mut substs = Vec::new();
279 let generics = tr.generic_params(db); 279 let generics = trait_.generic_params(db);
280 substs.push(self_ty); 280 let num_vars = self_ty.num_vars;
281 substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map( 281 substs.push(self_ty.value);
282 |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))), 282 substs.extend(
283 )); 283 generics
284 substs.into() 284 .params_including_parent()
285 .into_iter()
286 .skip(1)
287 .enumerate()
288 .map(|(i, _p)| Ty::Bound((i + num_vars) as u32)),
289 );
290 Canonical {
291 num_vars: substs.len() - 1 + self_ty.num_vars,
292 value: TraitRef { trait_, substs: substs.into() },
293 }
285} 294}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index c76a5012f..0aecde37c 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2140,7 +2140,7 @@ fn test() {
2140[102; 127) '{ ...d(); }': () 2140[102; 127) '{ ...d(); }': ()
2141[108; 109) 'S': S<u32>(T) -> S<T> 2141[108; 109) 'S': S<u32>(T) -> S<T>
2142[108; 115) 'S(1u32)': S<u32> 2142[108; 115) 'S(1u32)': S<u32>
2143[108; 124) 'S(1u32...thod()': {unknown} 2143[108; 124) 'S(1u32...thod()': u32
2144[110; 114) '1u32': u32"### 2144[110; 114) '1u32': u32"###
2145 ); 2145 );
2146} 2146}
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 06f483899..a1ed0c028 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -1,47 +1,65 @@
1//! Stuff that will probably mostly replaced by Chalk. 1//! Trait solving using Chalk.
2use std::collections::HashMap; 2use std::sync::{Arc, Mutex};
3 3
4use crate::{db::HirDatabase, generics::HasGenericParams}; 4use log::debug;
5use super::{TraitRef, Substs, infer::{TypeVarId, InferTy}, Ty}; 5use chalk_ir::cast::Cast;
6 6
7// Copied (and simplified) from Chalk 7use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
8use super::{TraitRef, Ty, Canonical};
8 9
9#[derive(Clone, Debug, PartialEq, Eq)] 10use self::chalk::{ToChalk, from_chalk};
10/// A (possible) solution for a proposed goal. Usually packaged in a `Result`,
11/// where `Err` represents definite *failure* to prove a goal.
12pub enum Solution {
13 /// The goal indeed holds, and there is a unique value for all existential
14 /// variables.
15 Unique(Substs),
16 11
17 /// The goal may be provable in multiple ways, but regardless we may have some guidance 12mod chalk;
18 /// for type inference. 13
19 Ambig(Guidance), 14pub(crate) type Solver = chalk_solve::Solver;
15
16#[derive(Debug, Copy, Clone)]
17struct ChalkContext<'a, DB> {
18 db: &'a DB,
19 krate: Crate,
20} 20}
21 21
22#[derive(Clone, Debug, PartialEq, Eq)] 22pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> {
23/// When a goal holds ambiguously (e.g., because there are multiple possible 23 // krate parameter is just so we cache a unique solver per crate
24/// solutions), we issue a set of *guidance* back to type inference. 24 let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 };
25pub enum Guidance { 25 Arc::new(Mutex::new(solver_choice.into_solver()))
26 /// The existential variables *must* have the given values if the goal is 26}
27 /// ever to hold, but that alone isn't enough to guarantee the goal will
28 /// actually hold.
29 Definite(Substs),
30 27
31 /// There are multiple plausible values for the existentials, but the ones 28/// Collects impls for the given trait in the whole dependency tree of `krate`.
32 /// here are suggested as the preferred choice heuristically. These should 29pub(crate) fn impls_for_trait(
33 /// be used for inference fallback only. 30 db: &impl HirDatabase,
34 Suggested(Substs), 31 krate: Crate,
32 trait_: Trait,
33) -> Arc<[ImplBlock]> {
34 let mut impls = Vec::new();
35 // We call the query recursively here. On the one hand, this means we can
36 // reuse results from queries for different crates; on the other hand, this
37 // will only ever get called for a few crates near the root of the tree (the
38 // ones the user is editing), so this may actually be a waste of memory. I'm
39 // doing it like this mainly for simplicity for now.
40 for dep in krate.dependencies(db) {
41 impls.extend(db.impls_for_trait(dep.krate, trait_).iter());
42 }
43 let crate_impl_blocks = db.impls_in_crate(krate);
44 impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_));
45 impls.into()
46}
35 47
36 /// There's no useful information to feed back to type inference 48fn solve(
37 Unknown, 49 db: &impl HirDatabase,
50 krate: Crate,
51 goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal>>,
52) -> Option<chalk_solve::Solution> {
53 let context = ChalkContext { db, krate };
54 let solver = db.solver(krate);
55 let solution = solver.lock().unwrap().solve(&context, goal);
56 debug!("solve({:?}) => {:?}", goal, solution);
57 solution
38} 58}
39 59
40/// Something that needs to be proven (by Chalk) during type checking, e.g. that 60/// Something that needs to be proven (by Chalk) during type checking, e.g. that
41/// a certain type implements a certain trait. Proving the Obligation might 61/// a certain type implements a certain trait. Proving the Obligation might
42/// result in additional information about inference variables. 62/// result in additional information about inference variables.
43///
44/// This might be handled by Chalk when we integrate it?
45#[derive(Clone, Debug, PartialEq, Eq)] 63#[derive(Clone, Debug, PartialEq, Eq)]
46pub enum Obligation { 64pub enum Obligation {
47 /// Prove that a certain type implements a trait (the type is the `Self` type 65 /// Prove that a certain type implements a trait (the type is the `Self` type
@@ -49,67 +67,94 @@ pub enum Obligation {
49 Trait(TraitRef), 67 Trait(TraitRef),
50} 68}
51 69
52/// Rudimentary check whether an impl exists for a given type and trait; this 70/// Check using Chalk whether trait is implemented for given parameters including `Self` type.
53/// will actually be done by chalk. 71pub(crate) fn implements(
54pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> { 72 db: &impl HirDatabase,
55 // FIXME use all trait impls in the whole crate graph 73 krate: Crate,
56 let krate = trait_ref.trait_.module(db).krate(db); 74 trait_ref: Canonical<TraitRef>,
57 let krate = match krate { 75) -> Option<Solution> {
58 Some(krate) => krate, 76 let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast();
59 None => return None, 77 debug!("goal: {:?}", goal);
60 }; 78 let env = chalk_ir::Environment::new();
61 let crate_impl_blocks = db.impls_in_crate(krate); 79 let in_env = chalk_ir::InEnvironment::new(&env, goal);
62 let mut impl_blocks = crate_impl_blocks 80 let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT);
63 .lookup_impl_blocks_for_trait(&trait_ref.trait_) 81 let canonical =
64 // we don't handle where clauses at all, waiting for Chalk for that 82 chalk_ir::Canonical { value: in_env, binders: vec![parameter; trait_ref.num_vars] };
65 .filter(|impl_block| impl_block.generic_params(db).where_predicates.is_empty()); 83 // We currently don't deal with universes (I think / hope they're not yet
66 impl_blocks 84 // relevant for our use cases?)
67 .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?)) 85 let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
86 let solution = solve(db, krate, &u_canonical);
87 solution.map(|solution| solution_from_chalk(db, solution))
68} 88}
69 89
70pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) { 90fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
71 let mut canonical = HashMap::new(); // mapping uncanonical -> canonical 91 let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
72 let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense) 92 let value = subst
73 let mut substs = trait_ref.substs.0.to_vec(); 93 .value
74 for ty in &mut substs { 94 .parameters
75 ty.walk_mut(&mut |ty| match ty { 95 .into_iter()
76 Ty::Infer(InferTy::TypeVar(tv)) => { 96 .map(|p| {
77 let tv: &mut TypeVarId = tv; 97 let ty = match p {
78 *tv = *canonical.entry(*tv).or_insert_with(|| { 98 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
79 let i = uncanonical.len(); 99 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
80 uncanonical.push(*tv); 100 };
81 TypeVarId(i as u32) 101 ty
82 }); 102 })
83 } 103 .collect();
84 _ => {} 104 let result = Canonical { value, num_vars: subst.binders.len() };
85 }); 105 SolutionVariables(result)
106 };
107 match solution {
108 chalk_solve::Solution::Unique(constr_subst) => {
109 let subst = chalk_ir::Canonical {
110 value: constr_subst.value.subst,
111 binders: constr_subst.binders,
112 };
113 Solution::Unique(convert_subst(subst))
114 }
115 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => {
116 Solution::Ambig(Guidance::Definite(convert_subst(subst)))
117 }
118 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => {
119 Solution::Ambig(Guidance::Suggested(convert_subst(subst)))
120 }
121 chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => {
122 Solution::Ambig(Guidance::Unknown)
123 }
86 } 124 }
87 (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
88} 125}
89 126
90fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> { 127#[derive(Clone, Debug, PartialEq, Eq)]
91 if tr1.trait_ != tr2.trait_ { 128pub(crate) struct SolutionVariables(pub Canonical<Vec<Ty>>);
92 return None; 129
93 } 130#[derive(Clone, Debug, PartialEq, Eq)]
94 let mut solution_substs = Vec::new(); 131/// A (possible) solution for a proposed goal.
95 for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) { 132pub(crate) enum Solution {
96 // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass 133 /// The goal indeed holds, and there is a unique value for all existential
97 match (t1, t2) { 134 /// variables.
98 (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => { 135 Unique(SolutionVariables),
99 // type variable (or similar) in the impl, we just assume it works 136
100 } 137 /// The goal may be provable in multiple ways, but regardless we may have some guidance
101 (Ty::Infer(InferTy::TypeVar(v1)), _) => { 138 /// for type inference. In this case, we don't return any lifetime
102 // type variable in the query and fixed type in the impl, record its value 139 /// constraints, since we have not "committed" to any particular solution
103 solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown); 140 /// yet.
104 solution_substs[v1.0 as usize] = t2.clone(); 141 Ambig(Guidance),
105 } 142}
106 _ => { 143
107 // check that they're equal (actually we'd have to recurse etc.) 144#[derive(Clone, Debug, PartialEq, Eq)]
108 if t1 != t2 { 145/// When a goal holds ambiguously (e.g., because there are multiple possible
109 return None; 146/// solutions), we issue a set of *guidance* back to type inference.
110 } 147pub(crate) enum Guidance {
111 } 148 /// The existential variables *must* have the given values if the goal is
112 } 149 /// ever to hold, but that alone isn't enough to guarantee the goal will
113 } 150 /// actually hold.
114 Some(Solution::Unique(solution_substs.into())) 151 Definite(SolutionVariables),
152
153 /// There are multiple plausible values for the existentials, but the ones
154 /// here are suggested as the preferred choice heuristically. These should
155 /// be used for inference fallback only.
156 Suggested(SolutionVariables),
157
158 /// There's no useful information to feed back to type inference
159 Unknown,
115} 160}
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
new file mode 100644
index 000000000..8b77d21b4
--- /dev/null
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -0,0 +1,333 @@
1//! Conversion code from/to Chalk.
2use std::sync::Arc;
3
4use log::debug;
5
6use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
7use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
8
9use ra_db::salsa::{InternId, InternKey};
10
11use crate::{
12 Trait, HasGenericParams, ImplBlock,
13 db::HirDatabase,
14 ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs},
15};
16use super::ChalkContext;
17
18pub(super) trait ToChalk {
19 type Chalk;
20 fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk;
21 fn from_chalk(db: &impl HirDatabase, chalk: Self::Chalk) -> Self;
22}
23
24pub(super) fn from_chalk<T, ChalkT>(db: &impl HirDatabase, chalk: ChalkT) -> T
25where
26 T: ToChalk<Chalk = ChalkT>,
27{
28 T::from_chalk(db, chalk)
29}
30
31impl ToChalk for Ty {
32 type Chalk = chalk_ir::Ty;
33 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Ty {
34 match self {
35 Ty::Apply(apply_ty) => {
36 let struct_id = apply_ty.ctor.to_chalk(db);
37 let name = TypeName::TypeKindId(struct_id.into());
38 let parameters = apply_ty.parameters.to_chalk(db);
39 chalk_ir::ApplicationTy { name, parameters }.cast()
40 }
41 Ty::Param { idx, .. } => {
42 PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }.to_ty()
43 }
44 Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize),
45 Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
46 // FIXME this is clearly incorrect, but probably not too incorrect
47 // and I'm not sure what to actually do with Ty::Unknown
48 Ty::Unknown => PlaceholderIndex { ui: UniverseIndex::ROOT, idx: 0 }.to_ty(),
49 }
50 }
51 fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self {
52 match chalk {
53 chalk_ir::Ty::Apply(apply_ty) => {
54 match apply_ty.name {
55 TypeName::TypeKindId(TypeKindId::StructId(struct_id)) => {
56 let ctor = from_chalk(db, struct_id);
57 let parameters = from_chalk(db, apply_ty.parameters);
58 Ty::Apply(ApplicationTy { ctor, parameters })
59 }
60 // FIXME handle TypeKindId::Trait/Type here
61 TypeName::TypeKindId(_) => unimplemented!(),
62 TypeName::AssociatedType(_) => unimplemented!(),
63 TypeName::Placeholder(idx) => {
64 assert_eq!(idx.ui, UniverseIndex::ROOT);
65 Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() }
66 }
67 }
68 }
69 chalk_ir::Ty::Projection(_) => unimplemented!(),
70 chalk_ir::Ty::UnselectedProjection(_) => unimplemented!(),
71 chalk_ir::Ty::ForAll(_) => unimplemented!(),
72 chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32),
73 chalk_ir::Ty::InferenceVar(_iv) => panic!("unexpected chalk infer ty"),
74 }
75 }
76}
77
78impl ToChalk for Substs {
79 type Chalk = Vec<chalk_ir::Parameter>;
80
81 fn to_chalk(self, db: &impl HirDatabase) -> Vec<Parameter> {
82 self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect()
83 }
84
85 fn from_chalk(db: &impl HirDatabase, parameters: Vec<chalk_ir::Parameter>) -> Substs {
86 parameters
87 .into_iter()
88 .map(|p| match p {
89 chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
90 chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
91 })
92 .collect::<Vec<_>>()
93 .into()
94 }
95}
96
97impl ToChalk for TraitRef {
98 type Chalk = chalk_ir::TraitRef;
99
100 fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef {
101 let trait_id = self.trait_.to_chalk(db);
102 let parameters = self.substs.to_chalk(db);
103 chalk_ir::TraitRef { trait_id, parameters }
104 }
105
106 fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef) -> Self {
107 let trait_ = from_chalk(db, trait_ref.trait_id);
108 let substs = from_chalk(db, trait_ref.parameters);
109 TraitRef { trait_, substs }
110 }
111}
112
113impl ToChalk for Trait {
114 type Chalk = chalk_ir::TraitId;
115
116 fn to_chalk(self, _db: &impl HirDatabase) -> chalk_ir::TraitId {
117 self.id.into()
118 }
119
120 fn from_chalk(_db: &impl HirDatabase, trait_id: chalk_ir::TraitId) -> Trait {
121 Trait { id: trait_id.into() }
122 }
123}
124
125impl ToChalk for TypeCtor {
126 type Chalk = chalk_ir::StructId;
127
128 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::StructId {
129 db.intern_type_ctor(self).into()
130 }
131
132 fn from_chalk(db: &impl HirDatabase, struct_id: chalk_ir::StructId) -> TypeCtor {
133 db.lookup_intern_type_ctor(struct_id.into())
134 }
135}
136
137impl ToChalk for ImplBlock {
138 type Chalk = chalk_ir::ImplId;
139
140 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ImplId {
141 db.intern_impl_block(self).into()
142 }
143
144 fn from_chalk(db: &impl HirDatabase, impl_id: chalk_ir::ImplId) -> ImplBlock {
145 db.lookup_intern_impl_block(impl_id.into())
146 }
147}
148
149fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
150 chalk_ir::Binders {
151 value,
152 binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
153 }
154}
155
156impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
157where
158 DB: HirDatabase,
159{
160 fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> {
161 unimplemented!()
162 }
163 fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
164 debug!("trait_datum {:?}", trait_id);
165 let trait_: Trait = from_chalk(self.db, trait_id);
166 let generic_params = trait_.generic_params(self.db);
167 let bound_vars = Substs::bound_vars(&generic_params);
168 let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db);
169 let flags = chalk_rust_ir::TraitFlags {
170 // FIXME set these flags correctly
171 auto: false,
172 marker: false,
173 upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
174 fundamental: false,
175 };
176 let where_clauses = Vec::new(); // FIXME add where clauses
177 let associated_ty_ids = Vec::new(); // FIXME add associated tys
178 let trait_datum_bound =
179 chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids };
180 let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) };
181 Arc::new(trait_datum)
182 }
183 fn struct_datum(&self, struct_id: chalk_ir::StructId) -> Arc<StructDatum> {
184 debug!("struct_datum {:?}", struct_id);
185 let type_ctor = from_chalk(self.db, struct_id);
186 // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor
187 // FIXME extract this to a method on Ty
188 let (num_params, upstream) = match type_ctor {
189 TypeCtor::Bool
190 | TypeCtor::Char
191 | TypeCtor::Int(_)
192 | TypeCtor::Float(_)
193 | TypeCtor::Never
194 | TypeCtor::Str => (0, true),
195 TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true),
196 TypeCtor::FnPtr { num_args } => (num_args as usize + 1, true),
197 TypeCtor::Tuple { cardinality } => (cardinality as usize, true),
198 TypeCtor::FnDef(_) => unimplemented!(),
199 TypeCtor::Adt(adt) => {
200 let generic_params = adt.generic_params(self.db);
201 (
202 generic_params.count_params_including_parent(),
203 adt.krate(self.db) != Some(self.krate),
204 )
205 }
206 };
207 let flags = chalk_rust_ir::StructFlags {
208 upstream,
209 // FIXME set fundamental flag correctly
210 fundamental: false,
211 };
212 let where_clauses = Vec::new(); // FIXME add where clauses
213 let self_ty = chalk_ir::ApplicationTy {
214 name: TypeName::TypeKindId(type_ctor.to_chalk(self.db).into()),
215 parameters: (0..num_params).map(|i| chalk_ir::Ty::BoundVar(i).cast()).collect(),
216 };
217 let struct_datum_bound = chalk_rust_ir::StructDatumBound {
218 self_ty,
219 fields: Vec::new(), // FIXME add fields (only relevant for auto traits)
220 where_clauses,
221 flags,
222 };
223 let struct_datum = StructDatum { binders: make_binders(struct_datum_bound, num_params) };
224 Arc::new(struct_datum)
225 }
226 fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
227 debug!("impl_datum {:?}", impl_id);
228 let impl_block: ImplBlock = from_chalk(self.db, impl_id);
229 let generic_params = impl_block.generic_params(self.db);
230 let bound_vars = Substs::bound_vars(&generic_params);
231 let trait_ref = impl_block
232 .target_trait_ref(self.db)
233 .expect("FIXME handle unresolved impl block trait ref")
234 .subst(&bound_vars);
235 let impl_type = if impl_block.module().krate(self.db) == Some(self.krate) {
236 chalk_rust_ir::ImplType::Local
237 } else {
238 chalk_rust_ir::ImplType::External
239 };
240 let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
241 // FIXME handle negative impls (impl !Sync for Foo)
242 trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)),
243 where_clauses: Vec::new(), // FIXME add where clauses
244 associated_ty_values: Vec::new(), // FIXME add associated type values
245 impl_type,
246 };
247 let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) };
248 Arc::new(impl_datum)
249 }
250 fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec<ImplId> {
251 debug!("impls_for_trait {:?}", trait_id);
252 let trait_ = from_chalk(self.db, trait_id);
253 self.db
254 .impls_for_trait(self.krate, trait_)
255 .iter()
256 // FIXME temporary hack -- as long as we're not lowering where clauses
257 // correctly, ignore impls with them completely so as to not treat
258 // impl<T> Trait for T where T: ... as a blanket impl on all types
259 .filter(|impl_block| impl_block.generic_params(self.db).where_predicates.is_empty())
260 .map(|impl_block| impl_block.to_chalk(self.db))
261 .collect()
262 }
263 fn impl_provided_for(
264 &self,
265 auto_trait_id: chalk_ir::TraitId,
266 struct_id: chalk_ir::StructId,
267 ) -> bool {
268 debug!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id);
269 false // FIXME
270 }
271 fn type_name(&self, _id: TypeKindId) -> Identifier {
272 unimplemented!()
273 }
274 fn split_projection<'p>(
275 &self,
276 projection: &'p ProjectionTy,
277 ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) {
278 debug!("split_projection {:?}", projection);
279 unimplemented!()
280 }
281 fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause> {
282 debug!("custom_clauses");
283 vec![]
284 }
285 fn all_structs(&self) -> Vec<chalk_ir::StructId> {
286 debug!("all_structs");
287 // FIXME
288 vec![]
289 }
290}
291
292fn id_from_chalk<T: InternKey>(chalk_id: chalk_ir::RawId) -> T {
293 T::from_intern_id(InternId::from(chalk_id.index))
294}
295fn id_to_chalk<T: InternKey>(salsa_id: T) -> chalk_ir::RawId {
296 chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() }
297}
298
299impl From<chalk_ir::TraitId> for crate::ids::TraitId {
300 fn from(trait_id: chalk_ir::TraitId) -> Self {
301 id_from_chalk(trait_id.0)
302 }
303}
304
305impl From<crate::ids::TraitId> for chalk_ir::TraitId {
306 fn from(trait_id: crate::ids::TraitId) -> Self {
307 chalk_ir::TraitId(id_to_chalk(trait_id))
308 }
309}
310
311impl From<chalk_ir::StructId> for crate::ids::TypeCtorId {
312 fn from(struct_id: chalk_ir::StructId) -> Self {
313 id_from_chalk(struct_id.0)
314 }
315}
316
317impl From<crate::ids::TypeCtorId> for chalk_ir::StructId {
318 fn from(type_ctor_id: crate::ids::TypeCtorId) -> Self {
319 chalk_ir::StructId(id_to_chalk(type_ctor_id))
320 }
321}
322
323impl From<chalk_ir::ImplId> for crate::ids::GlobalImplId {
324 fn from(impl_id: chalk_ir::ImplId) -> Self {
325 id_from_chalk(impl_id.0)
326 }
327}
328
329impl From<crate::ids::GlobalImplId> for chalk_ir::ImplId {
330 fn from(impl_id: crate::ids::GlobalImplId) -> Self {
331 chalk_ir::ImplId(id_to_chalk(impl_id))
332 }
333}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 12:41:03 +0000