aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir_ty/src')
-rw-r--r--crates/ra_hir_ty/src/db.rs13
-rw-r--r--crates/ra_hir_ty/src/method_resolution.rs203
-rw-r--r--crates/ra_hir_ty/src/traits/chalk.rs10
3 files changed, 111 insertions, 115 deletions
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 c19519cf1..5dbabd12b 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,136 +38,131 @@ 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 each dependency, calculate `impls_from_deps` recursively, then add its own 80 for krate in crate_graph.transitive_deps(krate) {
76 // `impls_in_crate`. 81 res.merge(&db.trait_impls_in_crate(krate));
77 // As we might visit crates multiple times, `merge` has to deduplicate impls to avoid
78 // wasting memory.
79 for dep in &crate_graph[krate].dependencies {
80 res.merge(&db.impls_from_deps(dep.crate_id));
81 res.merge(&db.impls_in_crate(dep.crate_id));
82 } 82 }
83 83
84 Arc::new(res) 84 Arc::new(res)
85 } 85 }
86 86
87 fn fill(&mut self, db: &dyn HirDatabase, krate: CrateId) {
88 let crate_def_map = db.crate_def_map(krate);
89 for (_module_id, module_data) in crate_def_map.modules.iter() {
90 for impl_id in module_data.scope.impls() {
91 match db.impl_trait(impl_id) {
92 Some(tr) => {
93 let self_ty = db.impl_self_ty(impl_id);
94 let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
95 self.impls_by_trait
96 .entry(tr.value.trait_)
97 .or_default()
98 .entry(self_ty_fp)
99 .or_default()
100 .push(impl_id);
101 }
102 None => {
103 let self_ty = db.impl_self_ty(impl_id);
104 if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
105 self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id);
106 }
107 }
108 }
109 }
110 }
111 }
112
113 fn merge(&mut self, other: &Self) { 87 fn merge(&mut self, other: &Self) {
114 for (fp, impls) in &other.inherent_impls { 88 for (trait_, other_map) in &other.map {
115 let vec = self.inherent_impls.entry(*fp).or_default(); 89 let map = self.map.entry(*trait_).or_default();
116 vec.extend(impls);
117 vec.sort();
118 vec.dedup();
119 }
120
121 for (trait_, other_map) in &other.impls_by_trait {
122 let map = self.impls_by_trait.entry(*trait_).or_default();
123 for (fp, impls) in other_map { 90 for (fp, impls) in other_map {
124 let vec = map.entry(*fp).or_default(); 91 let vec = map.entry(*fp).or_default();
125 vec.extend(impls); 92 vec.extend(impls);
126 vec.sort();
127 vec.dedup();
128 } 93 }
129 } 94 }
130 } 95 }
131 96
132 pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ { 97 /// Queries all impls of the given trait.
133 let fingerprint = TyFingerprint::for_impl(ty); 98 pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
134 fingerprint.and_then(|f| self.inherent_impls.get(&f)).into_iter().flatten().copied() 99 self.map
135 } 100 .get(&trait_)
136
137 pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ {
138 self.impls_by_trait
139 .get(&tr)
140 .into_iter() 101 .into_iter()
141 .flat_map(|m| m.values().flat_map(|v| v.iter().copied())) 102 .flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
142 } 103 }
143 104
144 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(
145 &self, 107 &self,
146 tr: TraitId, 108 trait_: TraitId,
147 fp: TyFingerprint, 109 self_ty: TyFingerprint,
148 ) -> impl Iterator<Item = ImplId> + '_ { 110 ) -> impl Iterator<Item = ImplId> + '_ {
149 self.impls_by_trait 111 self.map
150 .get(&tr) 112 .get(&trait_)
151 .and_then(|m| m.get(&Some(fp)))
152 .into_iter() 113 .into_iter()
153 .flatten() 114 .flat_map(move |map| map.get(&None).into_iter().chain(map.get(&Some(self_ty))))
154 .copied() 115 .flat_map(|v| v.iter().copied())
155 .chain( 116 }
156 self.impls_by_trait 117
157 .get(&tr) 118 pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
158 .and_then(|m| m.get(&None)) 119 self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied()))
159 .into_iter() 120 }
160 .flatten() 121}
161 .copied(), 122
162 ) 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 }
163 } 162 }
164 163
165 pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a { 164 pub fn all_impls(&self) -> impl Iterator<Item = ImplId> + '_ {
166 self.inherent_impls 165 self.map.values().flat_map(|v| v.iter().copied())
167 .values()
168 .chain(self.impls_by_trait.values().flat_map(|m| m.values()))
169 .flatten()
170 .copied()
171 } 166 }
172} 167}
173 168
@@ -524,9 +519,9 @@ fn iterate_inherent_methods(
524 None => return false, 519 None => return false,
525 }; 520 };
526 for krate in def_crates { 521 for krate in def_crates {
527 let impls = db.impls_in_crate(krate); 522 let impls = db.inherent_impls_in_crate(krate);
528 523
529 for impl_def in impls.lookup_impl_defs(&self_ty.value) { 524 for &impl_def in impls.for_self_ty(&self_ty.value) {
530 for &item in db.impl_data(impl_def).items.iter() { 525 for &item in db.impl_data(impl_def).items.iter() {
531 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) { 526 if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
532 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