aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJonas Schievink <[email protected]>2020-07-01 16:15:20 +0100
committerJonas Schievink <[email protected]>2020-07-01 16:15:20 +0100
commit6bde542a39fe63298a31b838e59705797ed8a2cf (patch)
treeda737bc4b3e1d80782ae4adc132d99c0413aa1d0
parent07ba986db7b9f7c275bc2b6a32487e0aa8b70864 (diff)
Split `CrateImplDefs` in inherent and trait impls
This makes the intention of inherent vs. trait impls somewhat more clear and also fixes (?) an issue where trait impls with an unresolved trait were added as inherent impls instead (hence the test changes).
-rw-r--r--crates/ra_hir/src/code_model.rs16
-rw-r--r--crates/ra_hir/src/db.rs8
-rw-r--r--crates/ra_hir_ty/src/db.rs13
-rw-r--r--crates/ra_hir_ty/src/method_resolution.rs192
-rw-r--r--crates/ra_hir_ty/src/traits/chalk.rs10
-rw-r--r--crates/ra_ide/src/goto_implementation.rs4
-rw-r--r--crates/ra_ide_db/src/change.rs5
7 files changed, 130 insertions, 118 deletions
diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs
index e09eb77c2..cc72964ff 100644
--- a/crates/ra_hir/src/code_model.rs
+++ b/crates/ra_hir/src/code_model.rs
@@ -1053,12 +1053,14 @@ pub struct ImplDef {
1053 1053
1054impl ImplDef { 1054impl ImplDef {
1055 pub fn all_in_crate(db: &dyn HirDatabase, krate: Crate) -> Vec<ImplDef> { 1055 pub fn all_in_crate(db: &dyn HirDatabase, krate: Crate) -> Vec<ImplDef> {
1056 let impls = db.impls_in_crate(krate.id); 1056 let inherent = db.inherent_impls_in_crate(krate.id);
1057 impls.all_impls().map(Self::from).collect() 1057 let trait_ = db.trait_impls_in_crate(krate.id);
1058
1059 inherent.all_impls().chain(trait_.all_impls()).map(Self::from).collect()
1058 } 1060 }
1059 pub fn for_trait(db: &dyn HirDatabase, krate: Crate, trait_: Trait) -> Vec<ImplDef> { 1061 pub fn for_trait(db: &dyn HirDatabase, krate: Crate, trait_: Trait) -> Vec<ImplDef> {
1060 let impls = db.impls_in_crate(krate.id); 1062 let impls = db.trait_impls_in_crate(krate.id);
1061 impls.lookup_impl_defs_for_trait(trait_.id).map(Self::from).collect() 1063 impls.for_trait(trait_.id).map(Self::from).collect()
1062 } 1064 }
1063 1065
1064 pub fn target_trait(self, db: &dyn HirDatabase) -> Option<TypeRef> { 1066 pub fn target_trait(self, db: &dyn HirDatabase) -> Option<TypeRef> {
@@ -1303,10 +1305,10 @@ impl Type {
1303 mut callback: impl FnMut(AssocItem) -> Option<T>, 1305 mut callback: impl FnMut(AssocItem) -> Option<T>,
1304 ) -> Option<T> { 1306 ) -> Option<T> {
1305 for krate in self.ty.value.def_crates(db, krate.id)? { 1307 for krate in self.ty.value.def_crates(db, krate.id)? {
1306 let impls = db.impls_in_crate(krate); 1308 let impls = db.inherent_impls_in_crate(krate);
1307 1309
1308 for impl_def in impls.lookup_impl_defs(&self.ty.value) { 1310 for impl_def in impls.for_self_ty(&self.ty.value) {
1309 for &item in db.impl_data(impl_def).items.iter() { 1311 for &item in db.impl_data(*impl_def).items.iter() {
1310 if let Some(result) = callback(item.into()) { 1312 if let Some(result) = callback(item.into()) {
1311 return Some(result); 1313 return Some(result);
1312 } 1314 }
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index bb67952de..cb48ca065 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,10 +16,10 @@ pub use hir_expand::db::{
16pub use hir_ty::db::{ 16pub use hir_ty::db::{
17 AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery, 17 AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery,
18 GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase, 18 GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase,
19 HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery, 19 HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, InferQueryQuery,
20 ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, 20 InherentImplsInCrateQuery, InternAssocTyValueQuery, InternChalkImplQuery, InternTypeCtorQuery,
21 InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, 21 InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, TraitDatumQuery,
22 TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery, 22 TraitImplsInCrateQuery, TraitImplsInDepsQuery, TraitSolveQuery, TyQuery, ValueTyQuery,
23}; 23};
24 24
25#[test] 25#[test]
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index cad553273..dc06c0ee7 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -11,7 +11,7 @@ use ra_db::{impl_intern_key, salsa, CrateId, Upcast};
11use ra_prof::profile; 11use ra_prof::profile;
12 12
13use crate::{ 13use crate::{
14 method_resolution::CrateImplDefs, 14 method_resolution::{InherentImpls, TraitImpls},
15 traits::{chalk, AssocTyValue, Impl}, 15 traits::{chalk, AssocTyValue, Impl},
16 Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig, 16 Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig,
17 ReturnTypeImplTraits, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId, 17 ReturnTypeImplTraits, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId,
@@ -67,11 +67,14 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
67 #[salsa::invoke(crate::lower::generic_defaults_query)] 67 #[salsa::invoke(crate::lower::generic_defaults_query)]
68 fn generic_defaults(&self, def: GenericDefId) -> Arc<[Binders<Ty>]>; 68 fn generic_defaults(&self, def: GenericDefId) -> Arc<[Binders<Ty>]>;
69 69
70 #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)] 70 #[salsa::invoke(InherentImpls::inherent_impls_in_crate_query)]
71 fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>; 71 fn inherent_impls_in_crate(&self, krate: CrateId) -> Arc<InherentImpls>;
72 72
73 #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)] 73 #[salsa::invoke(TraitImpls::trait_impls_in_crate_query)]
74 fn impls_from_deps(&self, krate: CrateId) -> Arc<CrateImplDefs>; 74 fn trait_impls_in_crate(&self, krate: CrateId) -> Arc<TraitImpls>;
75
76 #[salsa::invoke(TraitImpls::trait_impls_in_deps_query)]
77 fn trait_impls_in_deps(&self, krate: CrateId) -> Arc<TraitImpls>;
75 78
76 // Interned IDs for Chalk integration 79 // Interned IDs for Chalk integration
77 #[salsa::interned] 80 #[salsa::interned]
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index 201604e1d..5dbabd12b 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,81 +38,55 @@ impl TyFingerprint {
38 } 38 }
39} 39}
40 40
41/// A queryable and mergeable collection of impls. 41/// Trait impls defined or available in some crate.
42#[derive(Debug, PartialEq, Eq)] 42#[derive(Debug, Eq, PartialEq)]
43pub struct CrateImplDefs { 43pub struct TraitImpls {
44 inherent_impls: FxHashMap<TyFingerprint, Vec<ImplId>>, 44 // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
45 impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>, 45 map: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
46} 46}
47 47
48impl CrateImplDefs { 48impl TraitImpls {
49 pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<CrateImplDefs> { 49 pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
50 let _p = profile("impls_in_crate_query"); 50 let _p = profile("trait_impls_in_crate_query");
51 let mut res = CrateImplDefs { 51 let mut impls = Self { map: FxHashMap::default() };
52 inherent_impls: FxHashMap::default(),
53 impls_by_trait: FxHashMap::default(),
54 };
55 res.fill(db, krate);
56 52
57 Arc::new(res) 53 let crate_def_map = db.crate_def_map(krate);
54 for (_module_id, module_data) in crate_def_map.modules.iter() {
55 for impl_id in module_data.scope.impls() {
56 let target_trait = match db.impl_trait(impl_id) {
57 Some(tr) => tr.value.trait_,
58 None => continue,
59 };
60 let self_ty = db.impl_self_ty(impl_id);
61 let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
62 impls
63 .map
64 .entry(target_trait)
65 .or_default()
66 .entry(self_ty_fp)
67 .or_default()
68 .push(impl_id);
69 }
70 }
71
72 Arc::new(impls)
58 } 73 }
59 74
60 /// Collects all impls from transitive dependencies of `krate` that may be used by `krate`. 75 pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
61 /// 76 let _p = profile("trait_impls_in_deps_query");
62 /// The full set of impls that can be used by `krate` is the returned map plus all the impls
63 /// from `krate` itself.
64 pub(crate) fn impls_from_deps_query(
65 db: &dyn HirDatabase,
66 krate: CrateId,
67 ) -> Arc<CrateImplDefs> {
68 let _p = profile("impls_from_deps_query");
69 let crate_graph = db.crate_graph(); 77 let crate_graph = db.crate_graph();
70 let mut res = CrateImplDefs { 78 let mut res = Self { map: FxHashMap::default() };
71 inherent_impls: FxHashMap::default(),
72 impls_by_trait: FxHashMap::default(),
73 };
74 79
75 for krate in crate_graph.transitive_deps(krate) { 80 for krate in crate_graph.transitive_deps(krate) {
76 res.merge(&db.impls_in_crate(krate)); 81 res.merge(&db.trait_impls_in_crate(krate));
77 } 82 }
78 83
79 Arc::new(res) 84 Arc::new(res)
80 } 85 }
81 86
82 fn fill(&mut self, db: &dyn HirDatabase, krate: CrateId) {
83 let crate_def_map = db.crate_def_map(krate);
84 for (_module_id, module_data) in crate_def_map.modules.iter() {
85 for impl_id in module_data.scope.impls() {
86 match db.impl_trait(impl_id) {
87 Some(tr) => {
88 let self_ty = db.impl_self_ty(impl_id);
89 let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
90 self.impls_by_trait
91 .entry(tr.value.trait_)
92 .or_default()
93 .entry(self_ty_fp)
94 .or_default()
95 .push(impl_id);
96 }
97 None => {
98 let self_ty = db.impl_self_ty(impl_id);
99 if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
100 self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id);
101 }
102 }
103 }
104 }
105 }
106 }
107
108 fn merge(&mut self, other: &Self) { 87 fn merge(&mut self, other: &Self) {
109 for (fp, impls) in &other.inherent_impls { 88 for (trait_, other_map) in &other.map {
110 let vec = self.inherent_impls.entry(*fp).or_default(); 89 let map = self.map.entry(*trait_).or_default();
111 vec.extend(impls);
112 }
113
114 for (trait_, other_map) in &other.impls_by_trait {
115 let map = self.impls_by_trait.entry(*trait_).or_default();
116 for (fp, impls) in other_map { 90 for (fp, impls) in other_map {
117 let vec = map.entry(*fp).or_default(); 91 let vec = map.entry(*fp).or_default();
118 vec.extend(impls); 92 vec.extend(impls);
@@ -120,45 +94,75 @@ impl CrateImplDefs {
120 } 94 }
121 } 95 }
122 96
123 pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ { 97 /// Queries all impls of the given trait.
124 let fingerprint = TyFingerprint::for_impl(ty); 98 pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
125 fingerprint.and_then(|f| self.inherent_impls.get(&f)).into_iter().flatten().copied() 99 self.map
126 } 100 .get(&trait_)
127
128 pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ {
129 self.impls_by_trait
130 .get(&tr)
131 .into_iter() 101 .into_iter()
132 .flat_map(|m| m.values().flat_map(|v| v.iter().copied())) 102 .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
133 } 103 }
134 104
135 pub fn lookup_impl_defs_for_trait_and_ty( 105 /// Queries all impls of `trait_` that may apply to `self_ty`.
106 pub fn for_trait_and_self_ty(
136 &self, 107 &self,
137 tr: TraitId, 108 trait_: TraitId,
138 fp: TyFingerprint, 109 self_ty: TyFingerprint,
139 ) -> impl Iterator<Item = ImplId> + '_ { 110 ) -> impl Iterator<Item = ImplId> + '_ {
140 self.impls_by_trait 111 self.map
141 .get(&tr) 112 .get(&trait_)
142 .and_then(|m| m.get(&Some(fp)))
143 .into_iter() 113 .into_iter()
144 .flatten() 114 .flat_map(move |map| map.get(&None).into_iter().chain(map.get(&Some(self_ty))))
145 .copied() 115 .flat_map(|v| v.iter().copied())
146 .chain( 116 }
147 self.impls_by_trait 117
148 .get(&tr) 118 pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
149 .and_then(|m| m.get(&None)) 119 self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
150 .into_iter() 120 }
151 .flatten() 121}
152 .copied(), 122
153 ) 123/// Inherent impls defined in some crate.
124///
125/// Inherent impls can only be defined in the crate that also defines the self type of the impl
126/// (note that some primitives are considered to be defined by both libcore and liballoc).
127///
128/// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a
129/// single crate.
130#[derive(Debug, Eq, PartialEq)]
131pub struct InherentImpls {
132 map: FxHashMap<TyFingerprint, Vec<ImplId>>,
133}
134
135impl InherentImpls {
136 pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
137 let mut map: FxHashMap<_, Vec<_>> = FxHashMap::default();
138
139 let crate_def_map = db.crate_def_map(krate);
140 for (_module_id, module_data) in crate_def_map.modules.iter() {
141 for impl_id in module_data.scope.impls() {
142 let data = db.impl_data(impl_id);
143 if data.target_trait.is_some() {
144 continue;
145 }
146
147 let self_ty = db.impl_self_ty(impl_id);
148 if let Some(fp) = TyFingerprint::for_impl(&self_ty.value) {
149 map.entry(fp).or_default().push(impl_id);
150 }
151 }
152 }
153
154 Arc::new(Self { map })
155 }
156
157 pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
158 match TyFingerprint::for_impl(self_ty) {
159 Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
160 None => &[],
161 }
154 } 162 }
155 163
156 pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a { 164 pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
157 self.inherent_impls 165 self.map.values().flat_map(|v| v.iter().copied())
158 .values()
159 .chain(self.impls_by_trait.values().flat_map(|m| m.values()))
160 .flatten()
161 .copied()
162 } 166 }
163} 167}
164 168
@@ -515,9 +519,9 @@ fn iterate_inherent_methods(
515 None => return false, 519 None => return false,
516 }; 520 };
517 for krate in def_crates { 521 for krate in def_crates {
518 let impls = db.impls_in_crate(krate); 522 let impls = db.inherent_impls_in_crate(krate);
519 523
520 for impl_def in impls.lookup_impl_defs(&self_ty.value) { 524 for &impl_def in impls.for_self_ty(&self_ty.value) {
521 for &item in db.impl_data(impl_def).items.iter() { 525 for &item in db.impl_data(impl_def).items.iter() {
522 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) { 526 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
523 continue; 527 continue;
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 8ef4941c0..c97b81d57 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -77,8 +77,8 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
77 // Note: Since we're using impls_for_trait, only impls where the trait 77 // Note: Since we're using impls_for_trait, only impls where the trait
78 // can be resolved should ever reach Chalk. `impl_datum` relies on that 78 // can be resolved should ever reach Chalk. `impl_datum` relies on that
79 // and will panic if the trait can't be resolved. 79 // and will panic if the trait can't be resolved.
80 let in_deps = self.db.impls_from_deps(self.krate); 80 let in_deps = self.db.trait_impls_in_deps(self.krate);
81 let in_self = self.db.impls_in_crate(self.krate); 81 let in_self = self.db.trait_impls_in_crate(self.krate);
82 let impl_maps = [in_deps, in_self]; 82 let impl_maps = [in_deps, in_self];
83 83
84 let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db); 84 let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db);
@@ -87,14 +87,12 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
87 Some(fp) => impl_maps 87 Some(fp) => impl_maps
88 .iter() 88 .iter()
89 .flat_map(|crate_impl_defs| { 89 .flat_map(|crate_impl_defs| {
90 crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp).map(id_to_chalk) 90 crate_impl_defs.for_trait_and_self_ty(trait_, fp).map(id_to_chalk)
91 }) 91 })
92 .collect(), 92 .collect(),
93 None => impl_maps 93 None => impl_maps
94 .iter() 94 .iter()
95 .flat_map(|crate_impl_defs| { 95 .flat_map(|crate_impl_defs| crate_impl_defs.for_trait(trait_).map(id_to_chalk))
96 crate_impl_defs.lookup_impl_defs_for_trait(trait_).map(id_to_chalk)
97 })
98 .collect(), 96 .collect(),
99 }; 97 };
100 98
diff --git a/crates/ra_ide/src/goto_implementation.rs b/crates/ra_ide/src/goto_implementation.rs
index 99a7022a4..9acc960fc 100644
--- a/crates/ra_ide/src/goto_implementation.rs
+++ b/crates/ra_ide/src/goto_implementation.rs
@@ -219,6 +219,10 @@ impl T for &Foo {}
219 #[derive(Copy)] 219 #[derive(Copy)]
220//^^^^^^^^^^^^^^^ 220//^^^^^^^^^^^^^^^
221struct Foo<|>; 221struct Foo<|>;
222
223mod marker {
224 trait Copy {}
225}
222"#, 226"#,
223 ); 227 );
224 } 228 }
diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs
index b507000f2..dbe6eacc5 100644
--- a/crates/ra_ide_db/src/change.rs
+++ b/crates/ra_ide_db/src/change.rs
@@ -243,8 +243,9 @@ impl RootDatabase {
243 hir::db::GenericPredicatesForParamQuery 243 hir::db::GenericPredicatesForParamQuery
244 hir::db::GenericPredicatesQuery 244 hir::db::GenericPredicatesQuery
245 hir::db::GenericDefaultsQuery 245 hir::db::GenericDefaultsQuery
246 hir::db::ImplsInCrateQuery 246 hir::db::InherentImplsInCrateQuery
247 hir::db::ImplsFromDepsQuery 247 hir::db::TraitImplsInCrateQuery
248 hir::db::TraitImplsInDepsQuery
248 hir::db::InternTypeCtorQuery 249 hir::db::InternTypeCtorQuery
249 hir::db::InternTypeParamIdQuery 250 hir::db::InternTypeParamIdQuery
250 hir::db::InternChalkImplQuery 251 hir::db::InternChalkImplQuery