aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
authorbors[bot] <bors[bot]@users.noreply.github.com>2019-05-12 18:45:34 +0100
committerbors[bot] <bors[bot]@users.noreply.github.com>2019-05-12 18:45:34 +0100
commit1944fc2c2b9ed5d9414afbc1b167e628d6e4e7f9 (patch)
tree50999df2191aa13204ca05f255ebe2b2105a1832 /crates
parent940c538ecf42a53e5a0e0e9ebad7267c1fe843ca (diff)
parentcbe75676b90d93e5b0ac461dce2d916cef4c0476 (diff)
Merge #1262
1262: Where clauses and other Chalk improvements r=matklad a=flodiebold This adds support for where clauses to the Chalk integration; it also adds FnDef lowering and partly handles auto traits. One thing I'm not sure about is the error handling -- what do we do if we can't resolve a trait reference in a where clause? For impls, I think it's clear we need to disregard the impl for trait solving. I've solved this for now by introducing an 'unknown trait' that has no impls, so if we encounter an unknown trait we can use that and basically get a where clause that's always false. (The alternative would be somehow not returning the impl to Chalk at all, but we would need to know that we need to do that in `impls_for_trait` already, and we don't resolve anything there.) A bit surprisingly, this has almost no impact on the type inference stats for RA, probably because of missing edge cases. Probably impl Trait support and closure support will do more. Co-authored-by: Florian Diebold <[email protected]>
Diffstat (limited to 'crates')
-rw-r--r--crates/ra_hir/src/code_model_api.rs4
-rw-r--r--crates/ra_hir/src/db.rs5
-rw-r--r--crates/ra_hir/src/generics.rs62
-rw-r--r--crates/ra_hir/src/impl_block.rs8
-rw-r--r--crates/ra_hir/src/marks.rs1
-rw-r--r--crates/ra_hir/src/traits.rs8
-rw-r--r--crates/ra_hir/src/ty.rs31
-rw-r--r--crates/ra_hir/src/ty/lower.rs53
-rw-r--r--crates/ra_hir/src/ty/tests.rs131
-rw-r--r--crates/ra_hir/src/ty/traits.rs9
-rw-r--r--crates/ra_hir/src/ty/traits/chalk.rs150
-rw-r--r--crates/ra_syntax/src/ast/extensions.rs10
12 files changed, 416 insertions, 56 deletions
diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 55e1793c5..0c4a80bfa 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -703,6 +703,10 @@ impl Trait {
703 TraitRef::for_trait(db, self) 703 TraitRef::for_trait(db, self)
704 } 704 }
705 705
706 pub fn is_auto(self, db: &impl DefDatabase) -> bool {
707 self.trait_data(db).is_auto()
708 }
709
706 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { 710 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
707 let r = self.module(db).resolver(db); 711 let r = self.module(db).resolver(db);
708 // add generic params, if present 712 // add generic params, if present
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 689dd6225..8f98ca3a5 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -11,7 +11,7 @@ use crate::{
11 DefWithBody, Trait, 11 DefWithBody, Trait,
12 ids, 12 ids,
13 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap}, 13 nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap},
14 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor}, 14 ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor, GenericPredicate},
15 adt::{StructData, EnumData}, 15 adt::{StructData, EnumData},
16 impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock}, 16 impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
17 generics::{GenericParams, GenericDef}, 17 generics::{GenericParams, GenericDef},
@@ -138,6 +138,9 @@ pub trait HirDatabase: DefDatabase {
138 #[salsa::invoke(crate::ty::callable_item_sig)] 138 #[salsa::invoke(crate::ty::callable_item_sig)]
139 fn callable_item_signature(&self, def: CallableDef) -> FnSig; 139 fn callable_item_signature(&self, def: CallableDef) -> FnSig;
140 140
141 #[salsa::invoke(crate::ty::generic_predicates)]
142 fn generic_predicates(&self, def: GenericDef) -> Arc<[GenericPredicate]>;
143
141 #[salsa::invoke(crate::expr::body_with_source_map_query)] 144 #[salsa::invoke(crate::expr::body_with_source_map_query)]
142 fn body_with_source_map( 145 fn body_with_source_map(
143 &self, 146 &self,
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 2e52c5871..c29b96f50 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -8,7 +8,7 @@ use std::sync::Arc;
8use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner}; 8use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner};
9 9
10use crate::{ 10use crate::{
11 db::DefDatabase, 11 db::{ HirDatabase, DefDatabase},
12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef 12 Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef
13}; 13};
14 14
@@ -32,8 +32,8 @@ pub struct GenericParams {
32/// where clauses like `where T: Foo + Bar` are turned into multiple of these. 32/// where clauses like `where T: Foo + Bar` are turned into multiple of these.
33#[derive(Clone, PartialEq, Eq, Debug)] 33#[derive(Clone, PartialEq, Eq, Debug)]
34pub struct WherePredicate { 34pub struct WherePredicate {
35 type_ref: TypeRef, 35 pub(crate) type_ref: TypeRef,
36 trait_ref: Path, 36 pub(crate) trait_ref: Path,
37} 37}
38 38
39// FIXME: consts can have type parameters from their parents (i.e. associated consts of traits) 39// FIXME: consts can have type parameters from their parents (i.e. associated consts of traits)
@@ -90,8 +90,17 @@ impl GenericParams {
90 fn fill_params(&mut self, params: &ast::TypeParamList, start: u32) { 90 fn fill_params(&mut self, params: &ast::TypeParamList, start: u32) {
91 for (idx, type_param) in params.type_params().enumerate() { 91 for (idx, type_param) in params.type_params().enumerate() {
92 let name = type_param.name().map(AsName::as_name).unwrap_or_else(Name::missing); 92 let name = type_param.name().map(AsName::as_name).unwrap_or_else(Name::missing);
93 let param = GenericParam { idx: idx as u32 + start, name }; 93 let param = GenericParam { idx: idx as u32 + start, name: name.clone() };
94 self.params.push(param); 94 self.params.push(param);
95
96 let type_ref = TypeRef::Path(name.into());
97 for bound in type_param
98 .type_bound_list()
99 .iter()
100 .flat_map(|type_bound_list| type_bound_list.bounds())
101 {
102 self.add_where_predicate_from_bound(bound, type_ref.clone());
103 }
95 } 104 }
96 } 105 }
97 106
@@ -101,26 +110,28 @@ impl GenericParams {
101 Some(type_ref) => type_ref, 110 Some(type_ref) => type_ref,
102 None => continue, 111 None => continue,
103 }; 112 };
113 let type_ref = TypeRef::from_ast(type_ref);
104 for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) { 114 for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
105 let path = bound 115 self.add_where_predicate_from_bound(bound, type_ref.clone());
106 .type_ref()
107 .and_then(|tr| match tr.kind() {
108 ast::TypeRefKind::PathType(path) => path.path(),
109 _ => None,
110 })
111 .and_then(Path::from_ast);
112 let path = match path {
113 Some(p) => p,
114 None => continue,
115 };
116 self.where_predicates.push(WherePredicate {
117 type_ref: TypeRef::from_ast(type_ref),
118 trait_ref: path,
119 });
120 } 116 }
121 } 117 }
122 } 118 }
123 119
120 fn add_where_predicate_from_bound(&mut self, bound: &ast::TypeBound, type_ref: TypeRef) {
121 let path = bound
122 .type_ref()
123 .and_then(|tr| match tr.kind() {
124 ast::TypeRefKind::PathType(path) => path.path(),
125 _ => None,
126 })
127 .and_then(Path::from_ast);
128 let path = match path {
129 Some(p) => p,
130 None => return,
131 };
132 self.where_predicates.push(WherePredicate { type_ref, trait_ref: path });
133 }
134
124 pub(crate) fn find_by_name(&self, name: &Name) -> Option<&GenericParam> { 135 pub(crate) fn find_by_name(&self, name: &Name) -> Option<&GenericParam> {
125 self.params.iter().find(|p| &p.name == name) 136 self.params.iter().find(|p| &p.name == name)
126 } 137 }
@@ -148,6 +159,19 @@ impl GenericParams {
148 } 159 }
149} 160}
150 161
162impl GenericDef {
163 pub(crate) fn resolver(&self, db: &impl HirDatabase) -> crate::Resolver {
164 match self {
165 GenericDef::Function(inner) => inner.resolver(db),
166 GenericDef::Struct(inner) => inner.resolver(db),
167 GenericDef::Enum(inner) => inner.resolver(db),
168 GenericDef::Trait(inner) => inner.resolver(db),
169 GenericDef::TypeAlias(inner) => inner.resolver(db),
170 GenericDef::ImplBlock(inner) => inner.resolver(db),
171 }
172 }
173}
174
151impl From<Container> for GenericDef { 175impl From<Container> for GenericDef {
152 fn from(c: Container) -> Self { 176 fn from(c: Container) -> Self {
153 match c { 177 match c {
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index a8a466e43..b7dd775f1 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -93,6 +93,10 @@ impl ImplBlock {
93 db.impls_in_module(self.module).impls[self.impl_id].items().to_vec() 93 db.impls_in_module(self.module).impls[self.impl_id].items().to_vec()
94 } 94 }
95 95
96 pub fn is_negative(&self, db: &impl DefDatabase) -> bool {
97 db.impls_in_module(self.module).impls[self.impl_id].negative
98 }
99
96 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver { 100 pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
97 let r = self.module().resolver(db); 101 let r = self.module().resolver(db);
98 // add generic params, if present 102 // add generic params, if present
@@ -108,6 +112,7 @@ pub struct ImplData {
108 target_trait: Option<TypeRef>, 112 target_trait: Option<TypeRef>,
109 target_type: TypeRef, 113 target_type: TypeRef,
110 items: Vec<ImplItem>, 114 items: Vec<ImplItem>,
115 negative: bool,
111} 116}
112 117
113impl ImplData { 118impl ImplData {
@@ -120,6 +125,7 @@ impl ImplData {
120 let target_trait = node.target_trait().map(TypeRef::from_ast); 125 let target_trait = node.target_trait().map(TypeRef::from_ast);
121 let target_type = TypeRef::from_ast_opt(node.target_type()); 126 let target_type = TypeRef::from_ast_opt(node.target_type());
122 let ctx = LocationCtx::new(db, module, file_id); 127 let ctx = LocationCtx::new(db, module, file_id);
128 let negative = node.is_negative();
123 let items = if let Some(item_list) = node.item_list() { 129 let items = if let Some(item_list) = node.item_list() {
124 item_list 130 item_list
125 .impl_items() 131 .impl_items()
@@ -132,7 +138,7 @@ impl ImplData {
132 } else { 138 } else {
133 Vec::new() 139 Vec::new()
134 }; 140 };
135 ImplData { target_trait, target_type, items } 141 ImplData { target_trait, target_type, items, negative }
136 } 142 }
137 143
138 pub fn target_trait(&self) -> Option<&TypeRef> { 144 pub fn target_trait(&self) -> Option<&TypeRef> {
diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs
index 5b6400042..2d831f0d8 100644
--- a/crates/ra_hir/src/marks.rs
+++ b/crates/ra_hir/src/marks.rs
@@ -9,4 +9,5 @@ test_utils::marks!(
9 glob_across_crates 9 glob_across_crates
10 std_prelude 10 std_prelude
11 match_ergonomics_ref 11 match_ergonomics_ref
12 trait_resolution_on_fn_type
12); 13);
diff --git a/crates/ra_hir/src/traits.rs b/crates/ra_hir/src/traits.rs
index 15f0977b7..dfe883fa4 100644
--- a/crates/ra_hir/src/traits.rs
+++ b/crates/ra_hir/src/traits.rs
@@ -11,6 +11,7 @@ use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationC
11pub struct TraitData { 11pub struct TraitData {
12 name: Option<Name>, 12 name: Option<Name>,
13 items: Vec<TraitItem>, 13 items: Vec<TraitItem>,
14 auto: bool,
14} 15}
15 16
16impl TraitData { 17impl TraitData {
@@ -19,6 +20,7 @@ impl TraitData {
19 let name = node.name().map(|n| n.as_name()); 20 let name = node.name().map(|n| n.as_name());
20 let module = tr.module(db); 21 let module = tr.module(db);
21 let ctx = LocationCtx::new(db, module, file_id); 22 let ctx = LocationCtx::new(db, module, file_id);
23 let auto = node.is_auto();
22 let items = if let Some(item_list) = node.item_list() { 24 let items = if let Some(item_list) = node.item_list() {
23 item_list 25 item_list
24 .impl_items() 26 .impl_items()
@@ -31,7 +33,7 @@ impl TraitData {
31 } else { 33 } else {
32 Vec::new() 34 Vec::new()
33 }; 35 };
34 Arc::new(TraitData { name, items }) 36 Arc::new(TraitData { name, items, auto })
35 } 37 }
36 38
37 pub(crate) fn name(&self) -> &Option<Name> { 39 pub(crate) fn name(&self) -> &Option<Name> {
@@ -41,6 +43,10 @@ impl TraitData {
41 pub(crate) fn items(&self) -> &[TraitItem] { 43 pub(crate) fn items(&self) -> &[TraitItem] {
42 &self.items 44 &self.items
43 } 45 }
46
47 pub(crate) fn is_auto(&self) -> bool {
48 self.auto
49 }
44} 50}
45 51
46#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 52#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 12429a668..cfe07156b 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -19,7 +19,7 @@ use std::{fmt, mem};
19use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams}; 19use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
20use display::{HirDisplay, HirFormatter}; 20use display::{HirDisplay, HirFormatter};
21 21
22pub(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, generic_predicates};
23pub(crate) use infer::{infer, InferenceResult, InferTy}; 23pub(crate) use infer::{infer, InferenceResult, InferTy};
24pub use lower::CallableDef; 24pub use lower::CallableDef;
25 25
@@ -234,6 +234,35 @@ impl TraitRef {
234 } 234 }
235} 235}
236 236
237/// Like `generics::WherePredicate`, but with resolved types: A condition on the
238/// parameters of a generic item.
239#[derive(Debug, Clone, PartialEq, Eq, Hash)]
240pub enum GenericPredicate {
241 /// The given trait needs to be implemented for its type parameters.
242 Implemented(TraitRef),
243 /// We couldn't resolve the trait reference. (If some type parameters can't
244 /// be resolved, they will just be Unknown).
245 Error,
246}
247
248impl GenericPredicate {
249 pub fn is_error(&self) -> bool {
250 match self {
251 GenericPredicate::Error => true,
252 _ => false,
253 }
254 }
255
256 pub fn subst(self, substs: &Substs) -> GenericPredicate {
257 match self {
258 GenericPredicate::Implemented(trait_ref) => {
259 GenericPredicate::Implemented(trait_ref.subst(substs))
260 }
261 GenericPredicate::Error => self,
262 }
263 }
264}
265
237/// Basically a claim (currently not validated / checked) that the contained 266/// Basically a claim (currently not validated / checked) that the contained
238/// type / trait ref contains no inference variables; any inference variables it 267/// 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 268/// contained have been replaced by bound variables, and `num_vars` tells us how
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 8bab7e54b..09d26ce5a 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -5,6 +5,7 @@
5//! - Building the type for an item: This happens through the `type_for_def` query. 5//! - Building the type for an item: This happens through the `type_for_def` query.
6//! 6//!
7//! This usually involves resolving names, collecting generic arguments etc. 7//! This usually involves resolving names, collecting generic arguments etc.
8use std::sync::Arc;
8use std::iter; 9use std::iter;
9 10
10use crate::{ 11use crate::{
@@ -18,9 +19,9 @@ use crate::{
18 resolve::{Resolver, Resolution}, 19 resolve::{Resolver, Resolution},
19 path::{PathSegment, GenericArg}, 20 path::{PathSegment, GenericArg},
20 generics::{GenericParams, HasGenericParams}, 21 generics::{GenericParams, HasGenericParams},
21 adt::VariantDef, Trait 22 adt::VariantDef, Trait, generics::{ WherePredicate, GenericDef}
22}; 23};
23use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef}; 24use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef, GenericPredicate};
24 25
25impl Ty { 26impl Ty {
26 pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self { 27 pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
@@ -208,16 +209,12 @@ pub(super) fn substs_from_path_segment(
208} 209}
209 210
210impl TraitRef { 211impl TraitRef {
211 pub(crate) fn from_hir( 212 pub(crate) fn from_path(
212 db: &impl HirDatabase, 213 db: &impl HirDatabase,
213 resolver: &Resolver, 214 resolver: &Resolver,
214 type_ref: &TypeRef, 215 path: &Path,
215 explicit_self_ty: Option<Ty>, 216 explicit_self_ty: Option<Ty>,
216 ) -> Option<Self> { 217 ) -> Option<Self> {
217 let path = match type_ref {
218 TypeRef::Path(path) => path,
219 _ => return None,
220 };
221 let resolved = match resolver.resolve_path(db, &path).take_types()? { 218 let resolved = match resolver.resolve_path(db, &path).take_types()? {
222 Resolution::Def(ModuleDef::Trait(tr)) => tr, 219 Resolution::Def(ModuleDef::Trait(tr)) => tr,
223 _ => return None, 220 _ => return None,
@@ -232,6 +229,19 @@ impl TraitRef {
232 Some(TraitRef { trait_: resolved, substs }) 229 Some(TraitRef { trait_: resolved, substs })
233 } 230 }
234 231
232 pub(crate) fn from_hir(
233 db: &impl HirDatabase,
234 resolver: &Resolver,
235 type_ref: &TypeRef,
236 explicit_self_ty: Option<Ty>,
237 ) -> Option<Self> {
238 let path = match type_ref {
239 TypeRef::Path(path) => path,
240 _ => return None,
241 };
242 TraitRef::from_path(db, resolver, path, explicit_self_ty)
243 }
244
235 fn substs_from_path( 245 fn substs_from_path(
236 db: &impl HirDatabase, 246 db: &impl HirDatabase,
237 resolver: &Resolver, 247 resolver: &Resolver,
@@ -246,6 +256,15 @@ impl TraitRef {
246 let substs = Substs::identity(&trait_.generic_params(db)); 256 let substs = Substs::identity(&trait_.generic_params(db));
247 TraitRef { trait_, substs } 257 TraitRef { trait_, substs }
248 } 258 }
259
260 pub(crate) fn for_where_predicate(
261 db: &impl HirDatabase,
262 resolver: &Resolver,
263 pred: &WherePredicate,
264 ) -> Option<TraitRef> {
265 let self_ty = Ty::from_hir(db, resolver, &pred.type_ref);
266 TraitRef::from_path(db, resolver, &pred.trait_ref, Some(self_ty))
267 }
249} 268}
250 269
251/// Build the declared type of an item. This depends on the namespace; e.g. for 270/// Build the declared type of an item. This depends on the namespace; e.g. for
@@ -294,6 +313,24 @@ pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty {
294 Ty::from_hir(db, &resolver, type_ref) 313 Ty::from_hir(db, &resolver, type_ref)
295} 314}
296 315
316/// Resolve the where clause(s) of an item with generics.
317pub(crate) fn generic_predicates(
318 db: &impl HirDatabase,
319 def: GenericDef,
320) -> Arc<[GenericPredicate]> {
321 let resolver = def.resolver(db);
322 let generic_params = def.generic_params(db);
323 let predicates = generic_params
324 .where_predicates
325 .iter()
326 .map(|pred| {
327 TraitRef::for_where_predicate(db, &resolver, pred)
328 .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
329 })
330 .collect::<Vec<_>>();
331 predicates.into()
332}
333
297fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig { 334fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig {
298 let signature = def.signature(db); 335 let signature = def.signature(db);
299 let resolver = def.resolver(db); 336 let resolver = def.resolver(db);
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index a38fe35c7..59c85daed 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2502,6 +2502,21 @@ fn test() { (&S).foo()<|>; }
2502} 2502}
2503 2503
2504#[test] 2504#[test]
2505fn method_resolution_where_clause_for_unknown_trait() {
2506 // The blanket impl shouldn't apply because we can't even resolve UnknownTrait
2507 let t = type_at(
2508 r#"
2509//- /main.rs
2510trait Trait { fn foo(self) -> u128; }
2511struct S;
2512impl<T> Trait for T where T: UnknownTrait {}
2513fn test() { (&S).foo()<|>; }
2514"#,
2515 );
2516 assert_eq!(t, "{unknown}");
2517}
2518
2519#[test]
2505fn method_resolution_where_clause_not_met() { 2520fn method_resolution_where_clause_not_met() {
2506 // The blanket impl shouldn't apply because we can't prove S: Clone 2521 // The blanket impl shouldn't apply because we can't prove S: Clone
2507 let t = type_at( 2522 let t = type_at(
@@ -2510,12 +2525,122 @@ fn method_resolution_where_clause_not_met() {
2510trait Clone {} 2525trait Clone {}
2511trait Trait { fn foo(self) -> u128; } 2526trait Trait { fn foo(self) -> u128; }
2512struct S; 2527struct S;
2513impl S { fn foo(self) -> i8 { 0 } } 2528impl<T> Trait for T where T: Clone {}
2514impl<T> Trait for T where T: Clone { fn foo(self) -> u128 { 0 } }
2515fn test() { (&S).foo()<|>; } 2529fn test() { (&S).foo()<|>; }
2516"#, 2530"#,
2517 ); 2531 );
2518 assert_eq!(t, "i8"); 2532 // This is also to make sure that we don't resolve to the foo method just
2533 // because that's the only method named foo we can find, which would make
2534 // the below tests not work
2535 assert_eq!(t, "{unknown}");
2536}
2537
2538#[test]
2539fn method_resolution_where_clause_inline_not_met() {
2540 // The blanket impl shouldn't apply because we can't prove S: Clone
2541 let t = type_at(
2542 r#"
2543//- /main.rs
2544trait Clone {}
2545trait Trait { fn foo(self) -> u128; }
2546struct S;
2547impl<T: Clone> Trait for T {}
2548fn test() { (&S).foo()<|>; }
2549"#,
2550 );
2551 assert_eq!(t, "{unknown}");
2552}
2553
2554#[test]
2555fn method_resolution_where_clause_1() {
2556 let t = type_at(
2557 r#"
2558//- /main.rs
2559trait Clone {}
2560trait Trait { fn foo(self) -> u128; }
2561struct S;
2562impl Clone for S {};
2563impl<T> Trait for T where T: Clone {}
2564fn test() { S.foo()<|>; }
2565"#,
2566 );
2567 assert_eq!(t, "u128");
2568}
2569
2570#[test]
2571fn method_resolution_where_clause_2() {
2572 let t = type_at(
2573 r#"
2574//- /main.rs
2575trait Into<T> { fn into(self) -> T; }
2576trait From<T> { fn from(other: T) -> Self; }
2577struct S1;
2578struct S2;
2579impl From<S2> for S1 {};
2580impl<T, U> Into<U> for T where U: From<T> {}
2581fn test() { S2.into()<|>; }
2582"#,
2583 );
2584 assert_eq!(t, "S1");
2585}
2586
2587#[test]
2588fn method_resolution_where_clause_inline() {
2589 let t = type_at(
2590 r#"
2591//- /main.rs
2592trait Into<T> { fn into(self) -> T; }
2593trait From<T> { fn from(other: T) -> Self; }
2594struct S1;
2595struct S2;
2596impl From<S2> for S1 {};
2597impl<T, U: From<T>> Into<U> for T {}
2598fn test() { S2.into()<|>; }
2599"#,
2600 );
2601 assert_eq!(t, "S1");
2602}
2603
2604#[test]
2605fn method_resolution_encountering_fn_type() {
2606 covers!(trait_resolution_on_fn_type);
2607 type_at(
2608 r#"
2609//- /main.rs
2610fn foo() {}
2611trait FnOnce { fn call(self); }
2612fn test() { foo.call()<|>; }
2613"#,
2614 );
2615}
2616
2617#[test]
2618fn method_resolution_slow() {
2619 // this can get quite slow if we set the solver size limit too high
2620 let t = type_at(
2621 r#"
2622//- /main.rs
2623trait Send {}
2624
2625struct S1; impl Send for S1;
2626struct S2; impl Send for S2;
2627struct U1;
2628
2629trait Trait { fn method(self); }
2630
2631struct X1<A, B> {}
2632impl<A, B> Send for X1<A, B> where A: Send, B: Send {}
2633
2634struct S<B, C> {}
2635
2636trait Fn {}
2637
2638impl<B, C> Trait for S<B, C> where C: Fn, B: Send {}
2639
2640fn test() { (S {}).method()<|>; }
2641"#,
2642 );
2643 assert_eq!(t, "{unknown}");
2519} 2644}
2520 2645
2521fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String { 2646fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 4bbc99f0e..4260f7ef7 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -14,6 +14,11 @@ mod chalk;
14 14
15pub(crate) type Solver = chalk_solve::Solver; 15pub(crate) type Solver = chalk_solve::Solver;
16 16
17/// This controls the maximum size of types Chalk considers. If we set this too
18/// high, we can run into slow edge cases; if we set it too low, Chalk won't
19/// find some solutions.
20const CHALK_SOLVER_MAX_SIZE: usize = 2;
21
17#[derive(Debug, Copy, Clone)] 22#[derive(Debug, Copy, Clone)]
18struct ChalkContext<'a, DB> { 23struct ChalkContext<'a, DB> {
19 db: &'a DB, 24 db: &'a DB,
@@ -22,7 +27,8 @@ struct ChalkContext<'a, DB> {
22 27
23pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> { 28pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> {
24 // krate parameter is just so we cache a unique solver per crate 29 // krate parameter is just so we cache a unique solver per crate
25 let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 }; 30 let solver_choice = chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE };
31 debug!("Creating new solver for crate {:?}", _krate);
26 Arc::new(Mutex::new(solver_choice.into_solver())) 32 Arc::new(Mutex::new(solver_choice.into_solver()))
27} 33}
28 34
@@ -53,6 +59,7 @@ fn solve(
53) -> Option<chalk_solve::Solution> { 59) -> Option<chalk_solve::Solution> {
54 let context = ChalkContext { db, krate }; 60 let context = ChalkContext { db, krate };
55 let solver = db.solver(krate); 61 let solver = db.solver(krate);
62 debug!("solve goal: {:?}", goal);
56 let solution = solver.lock().unwrap().solve(&context, goal); 63 let solution = solver.lock().unwrap().solve(&context, goal);
57 debug!("solve({:?}) => {:?}", goal, solution); 64 debug!("solve({:?}) => {:?}", goal, solution);
58 solution 65 solution
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 8b77d21b4..027c5ec4c 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -6,15 +6,22 @@ use log::debug;
6use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName}; 6use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
7use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum}; 7use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
8 8
9use test_utils::tested_by;
9use ra_db::salsa::{InternId, InternKey}; 10use ra_db::salsa::{InternId, InternKey};
10 11
11use crate::{ 12use crate::{
12 Trait, HasGenericParams, ImplBlock, 13 Trait, HasGenericParams, ImplBlock,
13 db::HirDatabase, 14 db::HirDatabase,
14 ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs}, 15 ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef},
16 ty::display::HirDisplay,
17 generics::GenericDef,
15}; 18};
16use super::ChalkContext; 19use super::ChalkContext;
17 20
21/// This represents a trait whose name we could not resolve.
22const UNKNOWN_TRAIT: chalk_ir::TraitId =
23 chalk_ir::TraitId(chalk_ir::RawId { index: u32::max_value() });
24
18pub(super) trait ToChalk { 25pub(super) trait ToChalk {
19 type Chalk; 26 type Chalk;
20 fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk; 27 fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk;
@@ -45,7 +52,10 @@ impl ToChalk for Ty {
45 Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"), 52 Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
46 // FIXME this is clearly incorrect, but probably not too incorrect 53 // FIXME this is clearly incorrect, but probably not too incorrect
47 // and I'm not sure what to actually do with Ty::Unknown 54 // and I'm not sure what to actually do with Ty::Unknown
48 Ty::Unknown => PlaceholderIndex { ui: UniverseIndex::ROOT, idx: 0 }.to_ty(), 55 // maybe an alternative would be `for<T> T`? (meaningless in rust, but expressible in chalk's Ty)
56 Ty::Unknown => {
57 PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::max_value() }.to_ty()
58 }
49 } 59 }
50 } 60 }
51 fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self { 61 fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self {
@@ -146,6 +156,33 @@ impl ToChalk for ImplBlock {
146 } 156 }
147} 157}
148 158
159impl ToChalk for GenericPredicate {
160 type Chalk = chalk_ir::QuantifiedWhereClause;
161
162 fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::QuantifiedWhereClause {
163 match self {
164 GenericPredicate::Implemented(trait_ref) => {
165 make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0)
166 }
167 GenericPredicate::Error => {
168 let impossible_trait_ref = chalk_ir::TraitRef {
169 trait_id: UNKNOWN_TRAIT,
170 parameters: vec![Ty::Unknown.to_chalk(db).cast()],
171 };
172 make_binders(chalk_ir::WhereClause::Implemented(impossible_trait_ref), 0)
173 }
174 }
175 }
176
177 fn from_chalk(
178 _db: &impl HirDatabase,
179 _where_clause: chalk_ir::QuantifiedWhereClause,
180 ) -> GenericPredicate {
181 // This should never need to be called
182 unimplemented!()
183 }
184}
185
149fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> { 186fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
150 chalk_ir::Binders { 187 chalk_ir::Binders {
151 value, 188 value,
@@ -153,6 +190,19 @@ fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
153 } 190 }
154} 191}
155 192
193fn convert_where_clauses(
194 db: &impl HirDatabase,
195 def: GenericDef,
196 substs: &Substs,
197) -> Vec<chalk_ir::QuantifiedWhereClause> {
198 let generic_predicates = db.generic_predicates(def);
199 let mut result = Vec::with_capacity(generic_predicates.len());
200 for pred in generic_predicates.iter() {
201 result.push(pred.clone().subst(substs).to_chalk(db));
202 }
203 result
204}
205
156impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB> 206impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
157where 207where
158 DB: HirDatabase, 208 DB: HirDatabase,
@@ -162,18 +212,35 @@ where
162 } 212 }
163 fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> { 213 fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
164 debug!("trait_datum {:?}", trait_id); 214 debug!("trait_datum {:?}", trait_id);
215 if trait_id == UNKNOWN_TRAIT {
216 let trait_datum_bound = chalk_rust_ir::TraitDatumBound {
217 trait_ref: chalk_ir::TraitRef {
218 trait_id: UNKNOWN_TRAIT,
219 parameters: vec![chalk_ir::Ty::BoundVar(0).cast()],
220 },
221 associated_ty_ids: Vec::new(),
222 where_clauses: Vec::new(),
223 flags: chalk_rust_ir::TraitFlags {
224 auto: false,
225 marker: false,
226 upstream: true,
227 fundamental: false,
228 },
229 };
230 return Arc::new(TraitDatum { binders: make_binders(trait_datum_bound, 1) });
231 }
165 let trait_: Trait = from_chalk(self.db, trait_id); 232 let trait_: Trait = from_chalk(self.db, trait_id);
166 let generic_params = trait_.generic_params(self.db); 233 let generic_params = trait_.generic_params(self.db);
167 let bound_vars = Substs::bound_vars(&generic_params); 234 let bound_vars = Substs::bound_vars(&generic_params);
168 let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db); 235 let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db);
169 let flags = chalk_rust_ir::TraitFlags { 236 let flags = chalk_rust_ir::TraitFlags {
237 auto: trait_.is_auto(self.db),
238 upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
170 // FIXME set these flags correctly 239 // FIXME set these flags correctly
171 auto: false,
172 marker: false, 240 marker: false,
173 upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
174 fundamental: false, 241 fundamental: false,
175 }; 242 };
176 let where_clauses = Vec::new(); // FIXME add where clauses 243 let where_clauses = convert_where_clauses(self.db, trait_.into(), &bound_vars);
177 let associated_ty_ids = Vec::new(); // FIXME add associated tys 244 let associated_ty_ids = Vec::new(); // FIXME add associated tys
178 let trait_datum_bound = 245 let trait_datum_bound =
179 chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids }; 246 chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids };
@@ -185,21 +252,48 @@ where
185 let type_ctor = from_chalk(self.db, struct_id); 252 let type_ctor = from_chalk(self.db, struct_id);
186 // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor 253 // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor
187 // FIXME extract this to a method on Ty 254 // FIXME extract this to a method on Ty
188 let (num_params, upstream) = match type_ctor { 255 let (num_params, where_clauses, upstream) = match type_ctor {
189 TypeCtor::Bool 256 TypeCtor::Bool
190 | TypeCtor::Char 257 | TypeCtor::Char
191 | TypeCtor::Int(_) 258 | TypeCtor::Int(_)
192 | TypeCtor::Float(_) 259 | TypeCtor::Float(_)
193 | TypeCtor::Never 260 | TypeCtor::Never
194 | TypeCtor::Str => (0, true), 261 | TypeCtor::Str => (0, vec![], true),
195 TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true), 262 TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => {
196 TypeCtor::FnPtr { num_args } => (num_args as usize + 1, true), 263 (1, vec![], true)
197 TypeCtor::Tuple { cardinality } => (cardinality as usize, true), 264 }
198 TypeCtor::FnDef(_) => unimplemented!(), 265 TypeCtor::FnPtr { num_args } => (num_args as usize + 1, vec![], true),
266 TypeCtor::Tuple { cardinality } => (cardinality as usize, vec![], true),
267 TypeCtor::FnDef(callable) => {
268 tested_by!(trait_resolution_on_fn_type);
269 let krate = match callable {
270 CallableDef::Function(f) => f.module(self.db).krate(self.db),
271 CallableDef::Struct(s) => s.module(self.db).krate(self.db),
272 CallableDef::EnumVariant(v) => {
273 v.parent_enum(self.db).module(self.db).krate(self.db)
274 }
275 };
276 let generic_def: GenericDef = match callable {
277 CallableDef::Function(f) => f.into(),
278 CallableDef::Struct(s) => s.into(),
279 CallableDef::EnumVariant(v) => v.parent_enum(self.db).into(),
280 };
281 let generic_params = generic_def.generic_params(self.db);
282 let bound_vars = Substs::bound_vars(&generic_params);
283 let where_clauses = convert_where_clauses(self.db, generic_def, &bound_vars);
284 (
285 generic_params.count_params_including_parent(),
286 where_clauses,
287 krate != Some(self.krate),
288 )
289 }
199 TypeCtor::Adt(adt) => { 290 TypeCtor::Adt(adt) => {
200 let generic_params = adt.generic_params(self.db); 291 let generic_params = adt.generic_params(self.db);
292 let bound_vars = Substs::bound_vars(&generic_params);
293 let where_clauses = convert_where_clauses(self.db, adt.into(), &bound_vars);
201 ( 294 (
202 generic_params.count_params_including_parent(), 295 generic_params.count_params_including_parent(),
296 where_clauses,
203 adt.krate(self.db) != Some(self.krate), 297 adt.krate(self.db) != Some(self.krate),
204 ) 298 )
205 } 299 }
@@ -209,7 +303,6 @@ where
209 // FIXME set fundamental flag correctly 303 // FIXME set fundamental flag correctly
210 fundamental: false, 304 fundamental: false,
211 }; 305 };
212 let where_clauses = Vec::new(); // FIXME add where clauses
213 let self_ty = chalk_ir::ApplicationTy { 306 let self_ty = chalk_ir::ApplicationTy {
214 name: TypeName::TypeKindId(type_ctor.to_chalk(self.db).into()), 307 name: TypeName::TypeKindId(type_ctor.to_chalk(self.db).into()),
215 parameters: (0..num_params).map(|i| chalk_ir::Ty::BoundVar(i).cast()).collect(), 308 parameters: (0..num_params).map(|i| chalk_ir::Ty::BoundVar(i).cast()).collect(),
@@ -237,10 +330,23 @@ where
237 } else { 330 } else {
238 chalk_rust_ir::ImplType::External 331 chalk_rust_ir::ImplType::External
239 }; 332 };
333 let where_clauses = convert_where_clauses(self.db, impl_block.into(), &bound_vars);
334 let negative = impl_block.is_negative(self.db);
335 debug!(
336 "impl {:?}: {}{} where {:?}",
337 impl_id,
338 if negative { "!" } else { "" },
339 trait_ref.display(self.db),
340 where_clauses
341 );
342 let trait_ref = trait_ref.to_chalk(self.db);
240 let impl_datum_bound = chalk_rust_ir::ImplDatumBound { 343 let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
241 // FIXME handle negative impls (impl !Sync for Foo) 344 trait_ref: if negative {
242 trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)), 345 chalk_rust_ir::PolarizedTraitRef::Negative(trait_ref)
243 where_clauses: Vec::new(), // FIXME add where clauses 346 } else {
347 chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref)
348 },
349 where_clauses,
244 associated_ty_values: Vec::new(), // FIXME add associated type values 350 associated_ty_values: Vec::new(), // FIXME add associated type values
245 impl_type, 351 impl_type,
246 }; 352 };
@@ -249,16 +355,18 @@ where
249 } 355 }
250 fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec<ImplId> { 356 fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec<ImplId> {
251 debug!("impls_for_trait {:?}", trait_id); 357 debug!("impls_for_trait {:?}", trait_id);
358 if trait_id == UNKNOWN_TRAIT {
359 return Vec::new();
360 }
252 let trait_ = from_chalk(self.db, trait_id); 361 let trait_ = from_chalk(self.db, trait_id);
253 self.db 362 let result: Vec<_> = self
363 .db
254 .impls_for_trait(self.krate, trait_) 364 .impls_for_trait(self.krate, trait_)
255 .iter() 365 .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)) 366 .map(|impl_block| impl_block.to_chalk(self.db))
261 .collect() 367 .collect();
368 debug!("impls_for_trait returned {} impls", result.len());
369 result
262 } 370 }
263 fn impl_provided_for( 371 fn impl_provided_for(
264 &self, 372 &self,
diff --git a/crates/ra_syntax/src/ast/extensions.rs b/crates/ra_syntax/src/ast/extensions.rs
index 9cbd2c6b8..f3466c585 100644
--- a/crates/ra_syntax/src/ast/extensions.rs
+++ b/crates/ra_syntax/src/ast/extensions.rs
@@ -170,6 +170,10 @@ impl ast::ImplBlock {
170 let second = types.next(); 170 let second = types.next();
171 (first, second) 171 (first, second)
172 } 172 }
173
174 pub fn is_negative(&self) -> bool {
175 self.syntax().children_with_tokens().any(|t| t.kind() == EXCL)
176 }
173} 177}
174 178
175#[derive(Debug, Clone, PartialEq, Eq)] 179#[derive(Debug, Clone, PartialEq, Eq)]
@@ -348,3 +352,9 @@ impl ast::WherePred {
348 .find(|it| it.kind() == LIFETIME) 352 .find(|it| it.kind() == LIFETIME)
349 } 353 }
350} 354}
355
356impl ast::TraitDef {
357 pub fn is_auto(&self) -> bool {
358 self.syntax().children_with_tokens().any(|t| t.kind() == AUTO_KW)
359 }
360}