aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
Diffstat (limited to 'crates')
-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
-rw-r--r--crates/ra_ide_api/src/change.rs1
-rw-r--r--crates/ra_ide_api/src/completion/complete_dot.rs2
-rw-r--r--crates/ra_mbe/src/lib.rs1158
-rw-r--r--crates/ra_mbe/src/mbe_expander.rs152
-rw-r--r--crates/ra_mbe/src/mbe_parser.rs38
-rw-r--r--crates/ra_mbe/src/subtree_source.rs223
-rw-r--r--crates/ra_mbe/src/syntax_bridge.rs137
-rw-r--r--crates/ra_mbe/src/tests.rs1399
-rw-r--r--crates/ra_mbe/src/tt_cursor.rs57
-rw-r--r--crates/ra_syntax/src/ast/generated.rs1
-rw-r--r--crates/ra_syntax/src/ast/traits.rs6
-rw-r--r--crates/ra_syntax/src/grammar.ron2
28 files changed, 2749 insertions, 1738 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}
diff --git a/crates/ra_ide_api/src/change.rs b/crates/ra_ide_api/src/change.rs
index 5bfdbe7e9..dc6a433c4 100644
--- a/crates/ra_ide_api/src/change.rs
+++ b/crates/ra_ide_api/src/change.rs
@@ -215,6 +215,7 @@ impl RootDatabase {
215 } 215 }
216 216
217 pub(crate) fn collect_garbage(&mut self) { 217 pub(crate) fn collect_garbage(&mut self) {
218 let _p = profile("RootDatabase::collect_garbage");
218 self.last_gc = time::Instant::now(); 219 self.last_gc = time::Instant::now();
219 220
220 let sweep = SweepStrategy::default().discard_values().sweep_all_revisions(); 221 let sweep = SweepStrategy::default().discard_values().sweep_all_revisions();
diff --git a/crates/ra_ide_api/src/completion/complete_dot.rs b/crates/ra_ide_api/src/completion/complete_dot.rs
index e34ddf24a..2e8084699 100644
--- a/crates/ra_ide_api/src/completion/complete_dot.rs
+++ b/crates/ra_ide_api/src/completion/complete_dot.rs
@@ -24,7 +24,7 @@ fn complete_fields(acc: &mut Completions, ctx: &CompletionContext, receiver: Ty)
24 } 24 }
25 } 25 }
26 // FIXME unions 26 // FIXME unions
27 TypeCtor::Tuple => { 27 TypeCtor::Tuple { .. } => {
28 for (i, ty) in a_ty.parameters.iter().enumerate() { 28 for (i, ty) in a_ty.parameters.iter().enumerate() {
29 acc.add_pos_field(ctx, i, ty); 29 acc.add_pos_field(ctx, i, ty);
30 } 30 }
diff --git a/crates/ra_mbe/src/lib.rs b/crates/ra_mbe/src/lib.rs
index be9ea3ebb..c146252a4 100644
--- a/crates/ra_mbe/src/lib.rs
+++ b/crates/ra_mbe/src/lib.rs
@@ -15,7 +15,6 @@ macro_rules! impl_froms {
15 } 15 }
16} 16}
17 17
18// mod tt_cursor;
19mod mbe_parser; 18mod mbe_parser;
20mod mbe_expander; 19mod mbe_expander;
21mod syntax_bridge; 20mod syntax_bridge;
@@ -99,13 +98,31 @@ pub(crate) struct Subtree {
99 pub(crate) token_trees: Vec<TokenTree>, 98 pub(crate) token_trees: Vec<TokenTree>,
100} 99}
101 100
102#[derive(Clone, Debug, PartialEq, Eq)] 101#[derive(Clone, Debug, Eq)]
103pub(crate) enum Separator { 102pub(crate) enum Separator {
104 Literal(tt::Literal), 103 Literal(tt::Literal),
105 Ident(tt::Ident), 104 Ident(tt::Ident),
106 Puncts(SmallVec<[tt::Punct; 3]>), 105 Puncts(SmallVec<[tt::Punct; 3]>),
107} 106}
108 107
108// Note that when we compare a Separator, we just care about its textual value.
109impl PartialEq for crate::Separator {
110 fn eq(&self, other: &crate::Separator) -> bool {
111 use crate::Separator::*;
112
113 match (self, other) {
114 (Ident(ref a), Ident(ref b)) => a.text == b.text,
115 (Literal(ref a), Literal(ref b)) => a.text == b.text,
116 (Puncts(ref a), Puncts(ref b)) if a.len() == b.len() => {
117 let a_iter = a.iter().map(|a| a.char);
118 let b_iter = b.iter().map(|b| b.char);
119 a_iter.eq(b_iter)
120 }
121 _ => false,
122 }
123 }
124}
125
109#[derive(Clone, Debug, PartialEq, Eq)] 126#[derive(Clone, Debug, PartialEq, Eq)]
110pub(crate) struct Repeat { 127pub(crate) struct Repeat {
111 pub(crate) subtree: Subtree, 128 pub(crate) subtree: Subtree,
@@ -137,1139 +154,4 @@ pub(crate) struct Var {
137} 154}
138 155
139#[cfg(test)] 156#[cfg(test)]
140mod tests { 157mod tests;
141 use ra_syntax::{ast, AstNode};
142
143 use super::*;
144
145 // Good first issue (although a slightly challenging one):
146 //
147 // * Pick a random test from here
148 // https://github.com/intellij-rust/intellij-rust/blob/c4e9feee4ad46e7953b1948c112533360b6087bb/src/test/kotlin/org/rust/lang/core/macros/RsMacroExpansionTest.kt
149 // * Port the test to rust and add it to this module
150 // * Make it pass :-)
151
152 #[test]
153 fn test_convert_tt() {
154 let macro_definition = r#"
155macro_rules! impl_froms {
156 ($e:ident: $($v:ident),*) => {
157 $(
158 impl From<$v> for $e {
159 fn from(it: $v) -> $e {
160 $e::$v(it)
161 }
162 }
163 )*
164 }
165}
166"#;
167
168 let macro_invocation = r#"
169impl_froms!(TokenTree: Leaf, Subtree);
170"#;
171
172 let source_file = ast::SourceFile::parse(macro_definition);
173 let macro_definition =
174 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
175
176 let source_file = ast::SourceFile::parse(macro_invocation);
177 let macro_invocation =
178 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
179
180 let (definition_tt, _) = ast_to_token_tree(macro_definition.token_tree().unwrap()).unwrap();
181 let (invocation_tt, _) = ast_to_token_tree(macro_invocation.token_tree().unwrap()).unwrap();
182 let rules = crate::MacroRules::parse(&definition_tt).unwrap();
183 let expansion = rules.expand(&invocation_tt).unwrap();
184 assert_eq!(
185 expansion.to_string(),
186 "impl From <Leaf > for TokenTree {fn from (it : Leaf) -> TokenTree {TokenTree ::Leaf (it)}} \
187 impl From <Subtree > for TokenTree {fn from (it : Subtree) -> TokenTree {TokenTree ::Subtree (it)}}"
188 )
189 }
190
191 pub(crate) fn create_rules(macro_definition: &str) -> MacroRules {
192 let source_file = ast::SourceFile::parse(macro_definition);
193 let macro_definition =
194 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
195
196 let (definition_tt, _) = ast_to_token_tree(macro_definition.token_tree().unwrap()).unwrap();
197 crate::MacroRules::parse(&definition_tt).unwrap()
198 }
199
200 pub(crate) fn expand(rules: &MacroRules, invocation: &str) -> tt::Subtree {
201 let source_file = ast::SourceFile::parse(invocation);
202 let macro_invocation =
203 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
204
205 let (invocation_tt, _) = ast_to_token_tree(macro_invocation.token_tree().unwrap()).unwrap();
206
207 rules.expand(&invocation_tt).unwrap()
208 }
209
210 pub(crate) fn expand_to_items(
211 rules: &MacroRules,
212 invocation: &str,
213 ) -> ra_syntax::TreeArc<ast::MacroItems> {
214 let expanded = expand(rules, invocation);
215 token_tree_to_macro_items(&expanded).unwrap()
216 }
217
218 #[allow(unused)]
219 pub(crate) fn expand_to_stmts(
220 rules: &MacroRules,
221 invocation: &str,
222 ) -> ra_syntax::TreeArc<ast::MacroStmts> {
223 let expanded = expand(rules, invocation);
224 token_tree_to_macro_stmts(&expanded).unwrap()
225 }
226
227 pub(crate) fn expand_to_expr(
228 rules: &MacroRules,
229 invocation: &str,
230 ) -> ra_syntax::TreeArc<ast::Expr> {
231 let expanded = expand(rules, invocation);
232 token_tree_to_expr(&expanded).unwrap()
233 }
234
235 pub(crate) fn assert_expansion(
236 rules: &MacroRules,
237 invocation: &str,
238 expansion: &str,
239 ) -> tt::Subtree {
240 let expanded = expand(rules, invocation);
241 assert_eq!(expanded.to_string(), expansion);
242
243 // FIXME: Temp comment below code
244 // It is because after the lexer change,
245 // The SyntaxNode structure cannot be matched easily
246
247 // let tree = token_tree_to_macro_items(&expanded);
248
249 // // Eat all white space by parse it back and forth
250 // // Because $crate will seperate in two token , will do some special treatment here
251 // let expansion = expansion.replace("$crate", "C_C__C");
252 // let expansion = ast::SourceFile::parse(&expansion);
253 // let expansion = syntax_node_to_token_tree(expansion.syntax()).unwrap().0;
254 // let file = token_tree_to_macro_items(&expansion);
255 // let file = file.unwrap().syntax().debug_dump().trim().to_string();
256 // let tree = tree.unwrap().syntax().debug_dump().trim().to_string();
257
258 // let file = file.replace("C_C__C", "$crate");
259 // assert_eq!(tree, file,);
260
261 expanded
262 }
263
264 #[test]
265 fn test_fail_match_pattern_by_first_token() {
266 let rules = create_rules(
267 r#"
268 macro_rules! foo {
269 ($ i:ident) => (
270 mod $ i {}
271 );
272 (= $ i:ident) => (
273 fn $ i() {}
274 );
275 (+ $ i:ident) => (
276 struct $ i;
277 )
278 }
279"#,
280 );
281
282 assert_expansion(&rules, "foo! { foo }", "mod foo {}");
283 assert_expansion(&rules, "foo! { = bar }", "fn bar () {}");
284 assert_expansion(&rules, "foo! { + Baz }", "struct Baz ;");
285 }
286
287 #[test]
288 fn test_fail_match_pattern_by_last_token() {
289 let rules = create_rules(
290 r#"
291 macro_rules! foo {
292 ($ i:ident) => (
293 mod $ i {}
294 );
295 ($ i:ident =) => (
296 fn $ i() {}
297 );
298 ($ i:ident +) => (
299 struct $ i;
300 )
301 }
302"#,
303 );
304
305 assert_expansion(&rules, "foo! { foo }", "mod foo {}");
306 assert_expansion(&rules, "foo! { bar = }", "fn bar () {}");
307 assert_expansion(&rules, "foo! { Baz + }", "struct Baz ;");
308 }
309
310 #[test]
311 fn test_fail_match_pattern_by_word_token() {
312 let rules = create_rules(
313 r#"
314 macro_rules! foo {
315 ($ i:ident) => (
316 mod $ i {}
317 );
318 (spam $ i:ident) => (
319 fn $ i() {}
320 );
321 (eggs $ i:ident) => (
322 struct $ i;
323 )
324 }
325"#,
326 );
327
328 assert_expansion(&rules, "foo! { foo }", "mod foo {}");
329 assert_expansion(&rules, "foo! { spam bar }", "fn bar () {}");
330 assert_expansion(&rules, "foo! { eggs Baz }", "struct Baz ;");
331 }
332
333 #[test]
334 fn test_match_group_pattern_by_separator_token() {
335 let rules = create_rules(
336 r#"
337 macro_rules! foo {
338 ($ ($ i:ident),*) => ($ (
339 mod $ i {}
340 )*);
341 ($ ($ i:ident)#*) => ($ (
342 fn $ i() {}
343 )*);
344 ($ i:ident ,# $ j:ident) => (
345 struct $ i;
346 struct $ j;
347 )
348 }
349"#,
350 );
351
352 assert_expansion(&rules, "foo! { foo, bar }", "mod foo {} mod bar {}");
353 assert_expansion(&rules, "foo! { foo# bar }", "fn foo () {} fn bar () {}");
354 assert_expansion(&rules, "foo! { Foo,# Bar }", "struct Foo ; struct Bar ;");
355 }
356
357 #[test]
358 fn test_match_group_pattern_with_multiple_defs() {
359 let rules = create_rules(
360 r#"
361 macro_rules! foo {
362 ($ ($ i:ident),*) => ( struct Bar { $ (
363 fn $ i {}
364 )*} );
365 }
366"#,
367 );
368
369 assert_expansion(&rules, "foo! { foo, bar }", "struct Bar {fn foo {} fn bar {}}");
370 }
371
372 #[test]
373 fn test_match_group_pattern_with_multiple_statement() {
374 let rules = create_rules(
375 r#"
376 macro_rules! foo {
377 ($ ($ i:ident),*) => ( fn baz { $ (
378 $ i ();
379 )*} );
380 }
381"#,
382 );
383
384 assert_expansion(&rules, "foo! { foo, bar }", "fn baz {foo () ; bar () ;}");
385 }
386
387 #[test]
388 fn test_match_group_pattern_with_multiple_statement_without_semi() {
389 let rules = create_rules(
390 r#"
391 macro_rules! foo {
392 ($ ($ i:ident),*) => ( fn baz { $ (
393 $i()
394 );*} );
395 }
396"#,
397 );
398
399 assert_expansion(&rules, "foo! { foo, bar }", "fn baz {foo () ;bar ()}");
400 }
401
402 #[test]
403 fn test_match_group_empty_fixed_token() {
404 let rules = create_rules(
405 r#"
406 macro_rules! foo {
407 ($ ($ i:ident)* #abc) => ( fn baz { $ (
408 $ i ();
409 )*} );
410 }
411"#,
412 );
413
414 assert_expansion(&rules, "foo! {#abc}", "fn baz {}");
415 }
416
417 #[test]
418 fn test_match_group_in_subtree() {
419 let rules = create_rules(
420 r#"
421 macro_rules! foo {
422 (fn $name:ident {$($i:ident)*} ) => ( fn $name() { $ (
423 $ i ();
424 )*} );
425 }"#,
426 );
427
428 assert_expansion(&rules, "foo! {fn baz {a b} }", "fn baz () {a () ; b () ;}");
429 }
430
431 #[test]
432 fn test_match_group_with_multichar_sep() {
433 let rules = create_rules(
434 r#"
435 macro_rules! foo {
436 (fn $name:ident {$($i:literal)*} ) => ( fn $name() -> bool { $($i)&&*} );
437 }"#,
438 );
439
440 assert_expansion(&rules, "foo! (fn baz {true true} )", "fn baz () -> bool {true &&true}");
441 }
442
443 #[test]
444 fn test_match_group_zero_match() {
445 let rules = create_rules(
446 r#"
447 macro_rules! foo {
448 ( $($i:ident)* ) => ();
449 }"#,
450 );
451
452 assert_expansion(&rules, "foo! ()", "");
453 }
454
455 #[test]
456 fn test_match_group_in_group() {
457 let rules = create_rules(
458 r#"
459 macro_rules! foo {
460 { $( ( $($i:ident)* ) )* } => ( $( ( $($i)* ) )* );
461 }"#,
462 );
463
464 assert_expansion(&rules, "foo! ( (a b) )", "(a b)");
465 }
466
467 #[test]
468 fn test_expand_to_item_list() {
469 let rules = create_rules(
470 "
471 macro_rules! structs {
472 ($($i:ident),*) => {
473 $(struct $i { field: u32 } )*
474 }
475 }
476 ",
477 );
478 let expansion = expand(&rules, "structs!(Foo, Bar)");
479 let tree = token_tree_to_macro_items(&expansion);
480 assert_eq!(
481 tree.unwrap().syntax().debug_dump().trim(),
482 r#"
483MACRO_ITEMS@[0; 40)
484 STRUCT_DEF@[0; 20)
485 STRUCT_KW@[0; 6) "struct"
486 NAME@[6; 9)
487 IDENT@[6; 9) "Foo"
488 NAMED_FIELD_DEF_LIST@[9; 20)
489 L_CURLY@[9; 10) "{"
490 NAMED_FIELD_DEF@[10; 19)
491 NAME@[10; 15)
492 IDENT@[10; 15) "field"
493 COLON@[15; 16) ":"
494 PATH_TYPE@[16; 19)
495 PATH@[16; 19)
496 PATH_SEGMENT@[16; 19)
497 NAME_REF@[16; 19)
498 IDENT@[16; 19) "u32"
499 R_CURLY@[19; 20) "}"
500 STRUCT_DEF@[20; 40)
501 STRUCT_KW@[20; 26) "struct"
502 NAME@[26; 29)
503 IDENT@[26; 29) "Bar"
504 NAMED_FIELD_DEF_LIST@[29; 40)
505 L_CURLY@[29; 30) "{"
506 NAMED_FIELD_DEF@[30; 39)
507 NAME@[30; 35)
508 IDENT@[30; 35) "field"
509 COLON@[35; 36) ":"
510 PATH_TYPE@[36; 39)
511 PATH@[36; 39)
512 PATH_SEGMENT@[36; 39)
513 NAME_REF@[36; 39)
514 IDENT@[36; 39) "u32"
515 R_CURLY@[39; 40) "}""#
516 .trim()
517 );
518 }
519
520 #[test]
521 fn test_expand_literals_to_token_tree() {
522 fn to_subtree(tt: &tt::TokenTree) -> &tt::Subtree {
523 if let tt::TokenTree::Subtree(subtree) = tt {
524 return &subtree;
525 }
526 unreachable!("It is not a subtree");
527 }
528
529 fn to_literal(tt: &tt::TokenTree) -> &tt::Literal {
530 if let tt::TokenTree::Leaf(tt::Leaf::Literal(lit)) = tt {
531 return lit;
532 }
533 unreachable!("It is not a literal");
534 }
535
536 let rules = create_rules(
537 r#"
538 macro_rules! literals {
539 ($i:ident) => {
540 {
541 let a = 'c';
542 let c = 1000;
543 let f = 12E+99_f64;
544 let s = "rust1";
545 }
546 }
547 }
548 "#,
549 );
550 let expansion = expand(&rules, "literals!(foo)");
551 let stm_tokens = &to_subtree(&expansion.token_trees[0]).token_trees;
552
553 // [let] [a] [=] ['c'] [;]
554 assert_eq!(to_literal(&stm_tokens[3]).text, "'c'");
555 // [let] [c] [=] [1000] [;]
556 assert_eq!(to_literal(&stm_tokens[5 + 3]).text, "1000");
557 // [let] [f] [=] [12E+99_f64] [;]
558 assert_eq!(to_literal(&stm_tokens[10 + 3]).text, "12E+99_f64");
559 // [let] [s] [=] ["rust1"] [;]
560 assert_eq!(to_literal(&stm_tokens[15 + 3]).text, "\"rust1\"");
561 }
562
563 #[test]
564 fn test_two_idents() {
565 let rules = create_rules(
566 r#"
567 macro_rules! foo {
568 ($ i:ident, $ j:ident) => {
569 fn foo() { let a = $ i; let b = $j; }
570 }
571 }
572"#,
573 );
574 assert_expansion(&rules, "foo! { foo, bar }", "fn foo () {let a = foo ; let b = bar ;}");
575 }
576
577 #[test]
578 fn test_tt_to_stmts() {
579 let rules = create_rules(
580 r#"
581 macro_rules! foo {
582 () => {
583 let a = 0;
584 a = 10 + 1;
585 a
586 }
587 }
588"#,
589 );
590
591 let expanded = expand(&rules, "foo!{}");
592 let stmts = token_tree_to_macro_stmts(&expanded);
593
594 assert_eq!(
595 stmts.unwrap().syntax().debug_dump().trim(),
596 r#"MACRO_STMTS@[0; 15)
597 LET_STMT@[0; 7)
598 LET_KW@[0; 3) "let"
599 BIND_PAT@[3; 4)
600 NAME@[3; 4)
601 IDENT@[3; 4) "a"
602 EQ@[4; 5) "="
603 LITERAL@[5; 6)
604 INT_NUMBER@[5; 6) "0"
605 SEMI@[6; 7) ";"
606 EXPR_STMT@[7; 14)
607 BIN_EXPR@[7; 13)
608 PATH_EXPR@[7; 8)
609 PATH@[7; 8)
610 PATH_SEGMENT@[7; 8)
611 NAME_REF@[7; 8)
612 IDENT@[7; 8) "a"
613 EQ@[8; 9) "="
614 BIN_EXPR@[9; 13)
615 LITERAL@[9; 11)
616 INT_NUMBER@[9; 11) "10"
617 PLUS@[11; 12) "+"
618 LITERAL@[12; 13)
619 INT_NUMBER@[12; 13) "1"
620 SEMI@[13; 14) ";"
621 EXPR_STMT@[14; 15)
622 PATH_EXPR@[14; 15)
623 PATH@[14; 15)
624 PATH_SEGMENT@[14; 15)
625 NAME_REF@[14; 15)
626 IDENT@[14; 15) "a""#,
627 );
628 }
629
630 // The following tests are port from intellij-rust directly
631 // https://github.com/intellij-rust/intellij-rust/blob/c4e9feee4ad46e7953b1948c112533360b6087bb/src/test/kotlin/org/rust/lang/core/macros/RsMacroExpansionTest.kt
632
633 #[test]
634 fn test_path() {
635 let rules = create_rules(
636 r#"
637 macro_rules! foo {
638 ($ i:path) => {
639 fn foo() { let a = $ i; }
640 }
641 }
642"#,
643 );
644 assert_expansion(&rules, "foo! { foo }", "fn foo () {let a = foo ;}");
645 assert_expansion(
646 &rules,
647 "foo! { bar::<u8>::baz::<u8> }",
648 "fn foo () {let a = bar ::< u8 >:: baz ::< u8 > ;}",
649 );
650 }
651
652 #[test]
653 fn test_two_paths() {
654 let rules = create_rules(
655 r#"
656 macro_rules! foo {
657 ($ i:path, $ j:path) => {
658 fn foo() { let a = $ i; let b = $j; }
659 }
660 }
661"#,
662 );
663 assert_expansion(&rules, "foo! { foo, bar }", "fn foo () {let a = foo ; let b = bar ;}");
664 }
665
666 #[test]
667 fn test_path_with_path() {
668 let rules = create_rules(
669 r#"
670 macro_rules! foo {
671 ($ i:path) => {
672 fn foo() { let a = $ i :: bar; }
673 }
674 }
675"#,
676 );
677 assert_expansion(&rules, "foo! { foo }", "fn foo () {let a = foo :: bar ;}");
678 }
679
680 #[test]
681 fn test_expr() {
682 let rules = create_rules(
683 r#"
684 macro_rules! foo {
685 ($ i:expr) => {
686 fn bar() { $ i; }
687 }
688 }
689"#,
690 );
691
692 assert_expansion(
693 &rules,
694 "foo! { 2 + 2 * baz(3).quux() }",
695 "fn bar () {2 + 2 * baz (3) . quux () ;}",
696 );
697 }
698
699 #[test]
700 fn test_expr_order() {
701 let rules = create_rules(
702 r#"
703 macro_rules! foo {
704 ($ i:expr) => {
705 fn bar() { $ i * 2; }
706 }
707 }
708"#,
709 );
710
711 assert_eq!(
712 expand_to_items(&rules, "foo! { 1 + 1 }").syntax().debug_dump().trim(),
713 r#"MACRO_ITEMS@[0; 15)
714 FN_DEF@[0; 15)
715 FN_KW@[0; 2) "fn"
716 NAME@[2; 5)
717 IDENT@[2; 5) "bar"
718 PARAM_LIST@[5; 7)
719 L_PAREN@[5; 6) "("
720 R_PAREN@[6; 7) ")"
721 BLOCK@[7; 15)
722 L_CURLY@[7; 8) "{"
723 EXPR_STMT@[8; 14)
724 BIN_EXPR@[8; 13)
725 BIN_EXPR@[8; 11)
726 LITERAL@[8; 9)
727 INT_NUMBER@[8; 9) "1"
728 PLUS@[9; 10) "+"
729 LITERAL@[10; 11)
730 INT_NUMBER@[10; 11) "1"
731 STAR@[11; 12) "*"
732 LITERAL@[12; 13)
733 INT_NUMBER@[12; 13) "2"
734 SEMI@[13; 14) ";"
735 R_CURLY@[14; 15) "}""#,
736 );
737 }
738
739 #[test]
740 fn test_last_expr() {
741 let rules = create_rules(
742 r#"
743 macro_rules! vec {
744 ($($item:expr),*) => {
745 {
746 let mut v = Vec::new();
747 $(
748 v.push($item);
749 )*
750 v
751 }
752 };
753 }
754"#,
755 );
756 assert_expansion(
757 &rules,
758 "vec!(1,2,3)",
759 "{let mut v = Vec :: new () ; v . push (1) ; v . push (2) ; v . push (3) ; v}",
760 );
761 }
762
763 #[test]
764 fn test_ty() {
765 let rules = create_rules(
766 r#"
767 macro_rules! foo {
768 ($ i:ty) => (
769 fn bar() -> $ i { unimplemented!() }
770 )
771 }
772"#,
773 );
774 assert_expansion(
775 &rules,
776 "foo! { Baz<u8> }",
777 "fn bar () -> Baz < u8 > {unimplemented ! ()}",
778 );
779 }
780
781 #[test]
782 fn test_ty_with_complex_type() {
783 let rules = create_rules(
784 r#"
785 macro_rules! foo {
786 ($ i:ty) => (
787 fn bar() -> $ i { unimplemented!() }
788 )
789 }
790"#,
791 );
792
793 // Reference lifetime struct with generic type
794 assert_expansion(
795 &rules,
796 "foo! { &'a Baz<u8> }",
797 "fn bar () -> & 'a Baz < u8 > {unimplemented ! ()}",
798 );
799
800 // extern "Rust" func type
801 assert_expansion(
802 &rules,
803 r#"foo! { extern "Rust" fn() -> Ret }"#,
804 r#"fn bar () -> extern "Rust" fn () -> Ret {unimplemented ! ()}"#,
805 );
806 }
807
808 #[test]
809 fn test_pat_() {
810 let rules = create_rules(
811 r#"
812 macro_rules! foo {
813 ($ i:pat) => { fn foo() { let $ i; } }
814 }
815"#,
816 );
817 assert_expansion(&rules, "foo! { (a, b) }", "fn foo () {let (a , b) ;}");
818 }
819
820 #[test]
821 fn test_stmt() {
822 let rules = create_rules(
823 r#"
824 macro_rules! foo {
825 ($ i:stmt) => (
826 fn bar() { $ i; }
827 )
828 }
829"#,
830 );
831 assert_expansion(&rules, "foo! { 2 }", "fn bar () {2 ;}");
832 assert_expansion(&rules, "foo! { let a = 0 }", "fn bar () {let a = 0 ;}");
833 }
834
835 #[test]
836 fn test_single_item() {
837 let rules = create_rules(
838 r#"
839 macro_rules! foo {
840 ($ i:item) => (
841 $ i
842 )
843 }
844"#,
845 );
846 assert_expansion(&rules, "foo! {mod c {}}", "mod c {}");
847 }
848
849 #[test]
850 fn test_all_items() {
851 let rules = create_rules(
852 r#"
853 macro_rules! foo {
854 ($ ($ i:item)*) => ($ (
855 $ i
856 )*)
857 }
858"#,
859 );
860 assert_expansion(&rules, r#"
861 foo! {
862 extern crate a;
863 mod b;
864 mod c {}
865 use d;
866 const E: i32 = 0;
867 static F: i32 = 0;
868 impl G {}
869 struct H;
870 enum I { Foo }
871 trait J {}
872 fn h() {}
873 extern {}
874 type T = u8;
875 }
876"#, r#"extern crate a ; mod b ; mod c {} use d ; const E : i32 = 0 ; static F : i32 = 0 ; impl G {} struct H ; enum I {Foo} trait J {} fn h () {} extern {} type T = u8 ;"#);
877 }
878
879 #[test]
880 fn test_block() {
881 let rules = create_rules(
882 r#"
883 macro_rules! foo {
884 ($ i:block) => { fn foo() $ i }
885 }
886"#,
887 );
888 assert_expansion(&rules, "foo! { { 1; } }", "fn foo () {1 ;}");
889 }
890
891 #[test]
892 fn test_meta() {
893 let rules = create_rules(
894 r#"
895 macro_rules! foo {
896 ($ i:meta) => (
897 #[$ i]
898 fn bar() {}
899 )
900 }
901"#,
902 );
903 assert_expansion(
904 &rules,
905 r#"foo! { cfg(target_os = "windows") }"#,
906 r#"# [cfg (target_os = "windows")] fn bar () {}"#,
907 );
908 }
909
910 #[test]
911 // fn test_tt_block() {
912 // let rules = create_rules(
913 // r#"
914 // macro_rules! foo {
915 // ($ i:tt) => { fn foo() $ i }
916 // }
917 // "#,
918 // );
919 // assert_expansion(&rules, r#"foo! { { 1; } }"#, r#"fn foo () {1 ;}"#);
920 // }
921
922 // #[test]
923 // fn test_tt_group() {
924 // let rules = create_rules(
925 // r#"
926 // macro_rules! foo {
927 // ($($ i:tt)*) => { $($ i)* }
928 // }
929 // "#,
930 // );
931 // assert_expansion(&rules, r#"foo! { fn foo() {} }"#, r#"fn foo () {}"#);
932 // }
933 #[test]
934 fn test_lifetime() {
935 let rules = create_rules(
936 r#"
937 macro_rules! foo {
938 ($ lt:lifetime) => { struct Ref<$ lt>{ s: &$ lt str } }
939 }
940"#,
941 );
942 assert_expansion(&rules, r#"foo!{'a}"#, r#"struct Ref <'a > {s : &'a str}"#);
943 }
944
945 #[test]
946 fn test_literal() {
947 let rules = create_rules(
948 r#"
949 macro_rules! foo {
950 ($ type:ty $ lit:literal) => { const VALUE: $ type = $ lit;};
951 }
952"#,
953 );
954 assert_expansion(&rules, r#"foo!(u8 0)"#, r#"const VALUE : u8 = 0 ;"#);
955 }
956
957 #[test]
958 fn test_vis() {
959 let rules = create_rules(
960 r#"
961 macro_rules! foo {
962 ($ vis:vis $ name:ident) => { $ vis fn $ name() {}};
963 }
964"#,
965 );
966 assert_expansion(&rules, r#"foo!(pub foo);"#, r#"pub fn foo () {}"#);
967 }
968
969 // The following tests are based on real world situations
970 #[test]
971 fn test_vec() {
972 let rules = create_rules(
973 r#"
974 macro_rules! vec {
975 ($($item:expr),*) => {
976 {
977 let mut v = Vec::new();
978 $(
979 v.push($item);
980 )*
981 v
982 }
983 };
984}
985"#,
986 );
987 assert_expansion(&rules, r#"vec!();"#, r#"{let mut v = Vec :: new () ; v}"#);
988 assert_expansion(
989 &rules,
990 r#"vec![1u32,2]"#,
991 r#"{let mut v = Vec :: new () ; v . push (1u32) ; v . push (2) ; v}"#,
992 );
993
994 assert_eq!(
995 expand_to_expr(&rules, r#"vec![1u32,2]"#).syntax().debug_dump().trim(),
996 r#"BLOCK_EXPR@[0; 45)
997 BLOCK@[0; 45)
998 L_CURLY@[0; 1) "{"
999 LET_STMT@[1; 20)
1000 LET_KW@[1; 4) "let"
1001 BIND_PAT@[4; 8)
1002 MUT_KW@[4; 7) "mut"
1003 NAME@[7; 8)
1004 IDENT@[7; 8) "v"
1005 EQ@[8; 9) "="
1006 CALL_EXPR@[9; 19)
1007 PATH_EXPR@[9; 17)
1008 PATH@[9; 17)
1009 PATH@[9; 12)
1010 PATH_SEGMENT@[9; 12)
1011 NAME_REF@[9; 12)
1012 IDENT@[9; 12) "Vec"
1013 COLONCOLON@[12; 14) "::"
1014 PATH_SEGMENT@[14; 17)
1015 NAME_REF@[14; 17)
1016 IDENT@[14; 17) "new"
1017 ARG_LIST@[17; 19)
1018 L_PAREN@[17; 18) "("
1019 R_PAREN@[18; 19) ")"
1020 SEMI@[19; 20) ";"
1021 EXPR_STMT@[20; 33)
1022 METHOD_CALL_EXPR@[20; 32)
1023 PATH_EXPR@[20; 21)
1024 PATH@[20; 21)
1025 PATH_SEGMENT@[20; 21)
1026 NAME_REF@[20; 21)
1027 IDENT@[20; 21) "v"
1028 DOT@[21; 22) "."
1029 NAME_REF@[22; 26)
1030 IDENT@[22; 26) "push"
1031 ARG_LIST@[26; 32)
1032 L_PAREN@[26; 27) "("
1033 LITERAL@[27; 31)
1034 INT_NUMBER@[27; 31) "1u32"
1035 R_PAREN@[31; 32) ")"
1036 SEMI@[32; 33) ";"
1037 EXPR_STMT@[33; 43)
1038 METHOD_CALL_EXPR@[33; 42)
1039 PATH_EXPR@[33; 34)
1040 PATH@[33; 34)
1041 PATH_SEGMENT@[33; 34)
1042 NAME_REF@[33; 34)
1043 IDENT@[33; 34) "v"
1044 DOT@[34; 35) "."
1045 NAME_REF@[35; 39)
1046 IDENT@[35; 39) "push"
1047 ARG_LIST@[39; 42)
1048 L_PAREN@[39; 40) "("
1049 LITERAL@[40; 41)
1050 INT_NUMBER@[40; 41) "2"
1051 R_PAREN@[41; 42) ")"
1052 SEMI@[42; 43) ";"
1053 PATH_EXPR@[43; 44)
1054 PATH@[43; 44)
1055 PATH_SEGMENT@[43; 44)
1056 NAME_REF@[43; 44)
1057 IDENT@[43; 44) "v"
1058 R_CURLY@[44; 45) "}""#
1059 );
1060 }
1061
1062 #[test]
1063 fn test_winapi_struct() {
1064 // from https://github.com/retep998/winapi-rs/blob/a7ef2bca086aae76cf6c4ce4c2552988ed9798ad/src/macros.rs#L366
1065
1066 let rules = create_rules(
1067 r#"
1068macro_rules! STRUCT {
1069 ($(#[$attrs:meta])* struct $name:ident {
1070 $($field:ident: $ftype:ty,)+
1071 }) => (
1072 #[repr(C)] #[derive(Copy)] $(#[$attrs])*
1073 pub struct $name {
1074 $(pub $field: $ftype,)+
1075 }
1076 impl Clone for $name {
1077 #[inline]
1078 fn clone(&self) -> $name { *self }
1079 }
1080 #[cfg(feature = "impl-default")]
1081 impl Default for $name {
1082 #[inline]
1083 fn default() -> $name { unsafe { $crate::_core::mem::zeroed() } }
1084 }
1085 );
1086}
1087"#,
1088 );
1089 // from https://github.com/retep998/winapi-rs/blob/a7ef2bca086aae76cf6c4ce4c2552988ed9798ad/src/shared/d3d9caps.rs
1090 assert_expansion(&rules, r#"STRUCT!{struct D3DVSHADERCAPS2_0 {Caps: u8,}}"#,
1091 "# [repr (C)] # [derive (Copy)] pub struct D3DVSHADERCAPS2_0 {pub Caps : u8 ,} impl Clone for D3DVSHADERCAPS2_0 {# [inline] fn clone (& self) -> D3DVSHADERCAPS2_0 {* self}} # [cfg (feature = \"impl-default\")] impl Default for D3DVSHADERCAPS2_0 {# [inline] fn default () -> D3DVSHADERCAPS2_0 {unsafe {$crate :: _core :: mem :: zeroed ()}}}");
1092 assert_expansion(&rules, r#"STRUCT!{#[cfg_attr(target_arch = "x86", repr(packed))] struct D3DCONTENTPROTECTIONCAPS {Caps : u8 ,}}"#,
1093 "# [repr (C)] # [derive (Copy)] # [cfg_attr (target_arch = \"x86\" , repr (packed))] pub struct D3DCONTENTPROTECTIONCAPS {pub Caps : u8 ,} impl Clone for D3DCONTENTPROTECTIONCAPS {# [inline] fn clone (& self) -> D3DCONTENTPROTECTIONCAPS {* self}} # [cfg (feature = \"impl-default\")] impl Default for D3DCONTENTPROTECTIONCAPS {# [inline] fn default () -> D3DCONTENTPROTECTIONCAPS {unsafe {$crate :: _core :: mem :: zeroed ()}}}");
1094 }
1095
1096 #[test]
1097 fn test_int_base() {
1098 let rules = create_rules(
1099 r#"
1100macro_rules! int_base {
1101 ($Trait:ident for $T:ident as $U:ident -> $Radix:ident) => {
1102 #[stable(feature = "rust1", since = "1.0.0")]
1103 impl fmt::$Trait for $T {
1104 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1105 $Radix.fmt_int(*self as $U, f)
1106 }
1107 }
1108 }
1109}
1110"#,
1111 );
1112
1113 assert_expansion(&rules, r#" int_base!{Binary for isize as usize -> Binary}"#,
1114 "# [stable (feature = \"rust1\" , since = \"1.0.0\")] impl fmt ::Binary for isize {fn fmt (& self , f : & mut fmt :: Formatter < \'_ >) -> fmt :: Result {Binary . fmt_int (* self as usize , f)}}"
1115 );
1116 }
1117
1118 #[test]
1119 fn test_generate_pattern_iterators() {
1120 // from https://github.com/rust-lang/rust/blob/316a391dcb7d66dc25f1f9a4ec9d368ef7615005/src/libcore/str/mod.rs
1121 let rules = create_rules(
1122 r#"
1123macro_rules! generate_pattern_iterators {
1124 { double ended; with $(#[$common_stability_attribute:meta])*,
1125 $forward_iterator:ident,
1126 $reverse_iterator:ident, $iterty:ty
1127 } => {
1128 fn foo(){}
1129 }
1130}
1131"#,
1132 );
1133
1134 assert_expansion(&rules, r#"generate_pattern_iterators ! ( double ended ; with # [ stable ( feature = "rust1" , since = "1.0.0" ) ] , Split , RSplit , & 'a str )"#,
1135 "fn foo () {}");
1136 }
1137
1138 #[test]
1139 fn test_impl_fn_for_zst() {
1140 // from https://github.com/rust-lang/rust/blob/5d20ff4d2718c820632b38c1e49d4de648a9810b/src/libcore/internal_macros.rs
1141 let rules = create_rules(
1142 r#"
1143macro_rules! impl_fn_for_zst {
1144 { $( $( #[$attr: meta] )*
1145 struct $Name: ident impl$( <$( $lifetime : lifetime ),+> )? Fn =
1146 |$( $arg: ident: $ArgTy: ty ),*| -> $ReturnTy: ty
1147$body: block; )+
1148 } => {
1149 $(
1150 $( #[$attr] )*
1151 struct $Name;
1152
1153 impl $( <$( $lifetime ),+> )? Fn<($( $ArgTy, )*)> for $Name {
1154 #[inline]
1155 extern "rust-call" fn call(&self, ($( $arg, )*): ($( $ArgTy, )*)) -> $ReturnTy {
1156 $body
1157 }
1158 }
1159
1160 impl $( <$( $lifetime ),+> )? FnMut<($( $ArgTy, )*)> for $Name {
1161 #[inline]
1162 extern "rust-call" fn call_mut(
1163 &mut self,
1164 ($( $arg, )*): ($( $ArgTy, )*)
1165 ) -> $ReturnTy {
1166 Fn::call(&*self, ($( $arg, )*))
1167 }
1168 }
1169
1170 impl $( <$( $lifetime ),+> )? FnOnce<($( $ArgTy, )*)> for $Name {
1171 type Output = $ReturnTy;
1172
1173 #[inline]
1174 extern "rust-call" fn call_once(self, ($( $arg, )*): ($( $ArgTy, )*)) -> $ReturnTy {
1175 Fn::call(&self, ($( $arg, )*))
1176 }
1177 }
1178 )+
1179}
1180 }
1181}
1182"#,
1183 );
1184
1185 assert_expansion(&rules, r#"
1186impl_fn_for_zst ! {
1187 # [ derive ( Clone ) ]
1188 struct CharEscapeDebugContinue impl Fn = | c : char | -> char :: EscapeDebug {
1189 c . escape_debug_ext ( false )
1190 } ;
1191
1192 # [ derive ( Clone ) ]
1193 struct CharEscapeUnicode impl Fn = | c : char | -> char :: EscapeUnicode {
1194 c . escape_unicode ( )
1195 } ;
1196 # [ derive ( Clone ) ]
1197 struct CharEscapeDefault impl Fn = | c : char | -> char :: EscapeDefault {
1198 c . escape_default ( )
1199 } ;
1200 }
1201"#,
1202 "# [derive (Clone)] struct CharEscapeDebugContinue ; impl Fn < (char ,) > for CharEscapeDebugContinue {# [inline] extern \"rust-call\" fn call (& self , (c ,) : (char ,)) -> char :: EscapeDebug {{c . escape_debug_ext (false)}}} impl FnMut < (char ,) > for CharEscapeDebugContinue {# [inline] extern \"rust-call\" fn call_mut (& mut self , (c ,) : (char ,)) -> char :: EscapeDebug {Fn :: call (&* self , (c ,))}} impl FnOnce < (char ,) > for CharEscapeDebugContinue {type Output = char :: EscapeDebug ; # [inline] extern \"rust-call\" fn call_once (self , (c ,) : (char ,)) -> char :: EscapeDebug {Fn :: call (& self , (c ,))}} # [derive (Clone)] struct CharEscapeUnicode ; impl Fn < (char ,) > for CharEscapeUnicode {# [inline] extern \"rust-call\" fn call (& self , (c ,) : (char ,)) -> char :: EscapeUnicode {{c . escape_unicode ()}}} impl FnMut < (char ,) > for CharEscapeUnicode {# [inline] extern \"rust-call\" fn call_mut (& mut self , (c ,) : (char ,)) -> char :: EscapeUnicode {Fn :: call (&* self , (c ,))}} impl FnOnce < (char ,) > for CharEscapeUnicode {type Output = char :: EscapeUnicode ; # [inline] extern \"rust-call\" fn call_once (self , (c ,) : (char ,)) -> char :: EscapeUnicode {Fn :: call (& self , (c ,))}} # [derive (Clone)] struct CharEscapeDefault ; impl Fn < (char ,) > for CharEscapeDefault {# [inline] extern \"rust-call\" fn call (& self , (c ,) : (char ,)) -> char :: EscapeDefault {{c . escape_default ()}}} impl FnMut < (char ,) > for CharEscapeDefault {# [inline] extern \"rust-call\" fn call_mut (& mut self , (c ,) : (char ,)) -> char :: EscapeDefault {Fn :: call (&* self , (c ,))}} impl FnOnce < (char ,) > for CharEscapeDefault {type Output = char :: EscapeDefault ; # [inline] extern \"rust-call\" fn call_once (self , (c ,) : (char ,)) -> char :: EscapeDefault {Fn :: call (& self , (c ,))}}");
1203 }
1204
1205 #[test]
1206 fn test_impl_nonzero_fmt() {
1207 // from https://github.com/rust-lang/rust/blob/316a391dcb7d66dc25f1f9a4ec9d368ef7615005/src/libcore/num/mod.rs#L12
1208 let rules = create_rules(
1209 r#"
1210 macro_rules! impl_nonzero_fmt {
1211 ( #[$stability: meta] ( $( $Trait: ident ),+ ) for $Ty: ident ) => {
1212 fn foo() {}
1213 }
1214 }
1215"#,
1216 );
1217
1218 assert_expansion(&rules, r#"impl_nonzero_fmt ! { # [ stable ( feature = "nonzero" , since = "1.28.0" ) ] ( Debug , Display , Binary , Octal , LowerHex , UpperHex ) for NonZeroU8 }"#,
1219 "fn foo () {}");
1220 }
1221
1222 #[test]
1223 fn test_cfg_if_items() {
1224 // from https://github.com/rust-lang/rust/blob/33fe1131cadba69d317156847be9a402b89f11bb/src/libstd/macros.rs#L986
1225 let rules = create_rules(
1226 r#"
1227 macro_rules! __cfg_if_items {
1228 (($($not:meta,)*) ; ) => {};
1229 (($($not:meta,)*) ; ( ($($m:meta),*) ($($it:item)*) ), $($rest:tt)*) => {
1230 __cfg_if_items! { ($($not,)* $($m,)*) ; $($rest)* }
1231 }
1232 }
1233"#,
1234 );
1235
1236 assert_expansion(&rules, r#"__cfg_if_items ! { ( rustdoc , ) ; ( ( ) ( # [ cfg ( any ( target_os = "redox" , unix ) ) ] # [ stable ( feature = "rust1" , since = "1.0.0" ) ] pub use sys :: ext as unix ; # [ cfg ( windows ) ] # [ stable ( feature = "rust1" , since = "1.0.0" ) ] pub use sys :: ext as windows ; # [ cfg ( any ( target_os = "linux" , target_os = "l4re" ) ) ] pub mod linux ; ) ) , }"#,
1237 "__cfg_if_items ! {(rustdoc , ) ; }");
1238 }
1239
1240 #[test]
1241 fn test_cfg_if_main() {
1242 // from https://github.com/rust-lang/rust/blob/3d211248393686e0f73851fc7548f6605220fbe1/src/libpanic_unwind/macros.rs#L9
1243 let rules = create_rules(
1244 r#"
1245 macro_rules! cfg_if {
1246 ($(
1247 if #[cfg($($meta:meta),*)] { $($it:item)* }
1248 ) else * else {
1249 $($it2:item)*
1250 }) => {
1251 __cfg_if_items! {
1252 () ;
1253 $( ( ($($meta),*) ($($it)*) ), )*
1254 ( () ($($it2)*) ),
1255 }
1256 }
1257 }
1258"#,
1259 );
1260
1261 assert_expansion(&rules, r#"
1262cfg_if ! {
1263 if # [ cfg ( target_env = "msvc" ) ] {
1264 // no extra unwinder support needed
1265 } else if # [ cfg ( all ( target_arch = "wasm32" , not ( target_os = "emscripten" ) ) ) ] {
1266 // no unwinder on the system!
1267 } else {
1268 mod libunwind ;
1269 pub use libunwind :: * ;
1270 }
1271 }
1272"#,
1273 "__cfg_if_items ! {() ; (() (mod libunwind ; pub use libunwind :: * ;)) ,}");
1274 }
1275}
diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs
index d5189b537..4b007647c 100644
--- a/crates/ra_mbe/src/mbe_expander.rs
+++ b/crates/ra_mbe/src/mbe_expander.rs
@@ -81,9 +81,29 @@ struct Bindings {
81enum Binding { 81enum Binding {
82 Simple(tt::TokenTree), 82 Simple(tt::TokenTree),
83 Nested(Vec<Binding>), 83 Nested(Vec<Binding>),
84 Empty,
84} 85}
85 86
86impl Bindings { 87impl Bindings {
88 fn push_optional(&mut self, name: &SmolStr) {
89 // FIXME: Do we have a better way to represent an empty token ?
90 // Insert an empty subtree for empty token
91 self.inner.insert(
92 name.clone(),
93 Binding::Simple(
94 tt::Subtree { delimiter: tt::Delimiter::None, token_trees: vec![] }.into(),
95 ),
96 );
97 }
98
99 fn push_empty(&mut self, name: &SmolStr) {
100 self.inner.insert(name.clone(), Binding::Empty);
101 }
102
103 fn contains(&self, name: &SmolStr) -> bool {
104 self.inner.contains_key(name)
105 }
106
87 fn get(&self, name: &SmolStr, nesting: &[usize]) -> Result<&tt::TokenTree, ExpandError> { 107 fn get(&self, name: &SmolStr, nesting: &[usize]) -> Result<&tt::TokenTree, ExpandError> {
88 let mut b = self 108 let mut b = self
89 .inner 109 .inner
@@ -96,6 +116,12 @@ impl Bindings {
96 "could not find nested binding `{}`", 116 "could not find nested binding `{}`",
97 name 117 name
98 )))?, 118 )))?,
119 Binding::Empty => {
120 return Err(ExpandError::BindingError(format!(
121 "could not find empty binding `{}`",
122 name
123 )))
124 }
99 }; 125 };
100 } 126 }
101 match b { 127 match b {
@@ -104,16 +130,26 @@ impl Bindings {
104 "expected simple binding, found nested binding `{}`", 130 "expected simple binding, found nested binding `{}`",
105 name 131 name
106 ))), 132 ))),
133 Binding::Empty => Err(ExpandError::BindingError(format!(
134 "expected simple binding, found empty binding `{}`",
135 name
136 ))),
107 } 137 }
108 } 138 }
109 139
110 fn push_nested(&mut self, nested: Bindings) -> Result<(), ExpandError> { 140 fn push_nested(&mut self, idx: usize, nested: Bindings) -> Result<(), ExpandError> {
111 for (key, value) in nested.inner { 141 for (key, value) in nested.inner {
112 if !self.inner.contains_key(&key) { 142 if !self.inner.contains_key(&key) {
113 self.inner.insert(key.clone(), Binding::Nested(Vec::new())); 143 self.inner.insert(key.clone(), Binding::Nested(Vec::new()));
114 } 144 }
115 match self.inner.get_mut(&key) { 145 match self.inner.get_mut(&key) {
116 Some(Binding::Nested(it)) => it.push(value), 146 Some(Binding::Nested(it)) => {
147 // insert empty nested bindings before this one
148 while it.len() < idx {
149 it.push(Binding::Nested(vec![]));
150 }
151 it.push(value);
152 }
117 _ => { 153 _ => {
118 return Err(ExpandError::BindingError(format!( 154 return Err(ExpandError::BindingError(format!(
119 "could not find binding `{}`", 155 "could not find binding `{}`",
@@ -130,6 +166,24 @@ impl Bindings {
130 } 166 }
131} 167}
132 168
169fn collect_vars(subtree: &crate::Subtree) -> Vec<SmolStr> {
170 let mut res = vec![];
171
172 for tkn in subtree.token_trees.iter() {
173 match tkn {
174 crate::TokenTree::Leaf(crate::Leaf::Var(crate::Var { text, .. })) => {
175 res.push(text.clone());
176 }
177 crate::TokenTree::Subtree(subtree) => {
178 res.extend(collect_vars(subtree));
179 }
180 _ => {}
181 }
182 }
183
184 res
185}
186
133fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings, ExpandError> { 187fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings, ExpandError> {
134 let mut res = Bindings::default(); 188 let mut res = Bindings::default();
135 for pat in pattern.token_trees.iter() { 189 for pat in pattern.token_trees.iter() {
@@ -178,10 +232,6 @@ fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings,
178 input.eat_meta().ok_or(ExpandError::UnexpectedToken)?.clone(); 232 input.eat_meta().ok_or(ExpandError::UnexpectedToken)?.clone();
179 res.inner.insert(text.clone(), Binding::Simple(meta.into())); 233 res.inner.insert(text.clone(), Binding::Simple(meta.into()));
180 } 234 }
181 // FIXME:
182 // Enable followiing code when everything is fixed
183 // At least we can dogfood itself to not stackoverflow
184 //
185 "tt" => { 235 "tt" => {
186 let token = input.eat().ok_or(ExpandError::UnexpectedToken)?.clone(); 236 let token = input.eat().ok_or(ExpandError::UnexpectedToken)?.clone();
187 res.inner.insert(text.clone(), Binding::Simple(token.into())); 237 res.inner.insert(text.clone(), Binding::Simple(token.into()));
@@ -206,8 +256,13 @@ fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings,
206 ); 256 );
207 } 257 }
208 "vis" => { 258 "vis" => {
209 let vis = input.eat_vis().ok_or(ExpandError::UnexpectedToken)?.clone(); 259 // `vis` is optional
210 res.inner.insert(text.clone(), Binding::Simple(vis.into())); 260 if let Some(vis) = input.try_eat_vis() {
261 let vis = vis.clone();
262 res.inner.insert(text.clone(), Binding::Simple(vis.into()));
263 } else {
264 res.push_optional(&text);
265 }
211 } 266 }
212 267
213 _ => return Err(ExpandError::UnexpectedToken), 268 _ => return Err(ExpandError::UnexpectedToken),
@@ -236,7 +291,6 @@ fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings,
236 loop { 291 loop {
237 match match_lhs(subtree, input) { 292 match match_lhs(subtree, input) {
238 Ok(nested) => { 293 Ok(nested) => {
239 counter += 1;
240 limit -= 1; 294 limit -= 1;
241 if limit == 0 { 295 if limit == 0 {
242 log::warn!("match_lhs excced in repeat pattern exceed limit => {:#?}\n{:#?}\n{:#?}\n{:#?}", subtree, input, kind, separator); 296 log::warn!("match_lhs excced in repeat pattern exceed limit => {:#?}\n{:#?}\n{:#?}\n{:#?}", subtree, input, kind, separator);
@@ -244,7 +298,8 @@ fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings,
244 } 298 }
245 299
246 memento = input.save(); 300 memento = input.save();
247 res.push_nested(nested)?; 301 res.push_nested(counter, nested)?;
302 counter += 1;
248 if counter == 1 { 303 if counter == 1 {
249 if let crate::RepeatKind::ZeroOrOne = kind { 304 if let crate::RepeatKind::ZeroOrOne = kind {
250 break; 305 break;
@@ -252,20 +307,9 @@ fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings,
252 } 307 }
253 308
254 if let Some(separator) = separator { 309 if let Some(separator) = separator {
255 use crate::Separator::*;
256
257 if !input 310 if !input
258 .eat_seperator() 311 .eat_seperator()
259 .map(|sep| match (sep, separator) { 312 .map(|sep| sep == *separator)
260 (Ident(ref a), Ident(ref b)) => a.text == b.text,
261 (Literal(ref a), Literal(ref b)) => a.text == b.text,
262 (Puncts(ref a), Puncts(ref b)) if a.len() == b.len() => {
263 let a_iter = a.iter().map(|a| a.char);
264 let b_iter = b.iter().map(|b| b.char);
265 a_iter.eq(b_iter)
266 }
267 _ => false,
268 })
269 .unwrap_or(false) 313 .unwrap_or(false)
270 { 314 {
271 input.rollback(memento); 315 input.rollback(memento);
@@ -284,6 +328,10 @@ fn match_lhs(pattern: &crate::Subtree, input: &mut TtCursor) -> Result<Bindings,
284 crate::RepeatKind::OneOrMore if counter == 0 => { 328 crate::RepeatKind::OneOrMore if counter == 0 => {
285 return Err(ExpandError::UnexpectedToken); 329 return Err(ExpandError::UnexpectedToken);
286 } 330 }
331 _ if counter == 0 => {
332 // Collect all empty variables in subtrees