diff options
Diffstat (limited to 'crates/ra_hir_ty')
-rw-r--r-- | crates/ra_hir_ty/src/db.rs | 13 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/method_resolution.rs | 203 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/traits/chalk.rs | 10 |
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}; | |||
11 | use ra_prof::profile; | 11 | use ra_prof::profile; |
12 | 12 | ||
13 | use crate::{ | 13 | use 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)] |
43 | pub struct CrateImplDefs { | 43 | pub 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 | ||
48 | impl CrateImplDefs { | 48 | impl 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)] | ||
131 | pub struct InherentImpls { | ||
132 | map: FxHashMap<TyFingerprint, Vec<ImplId>>, | ||
133 | } | ||
134 | |||
135 | impl 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 | ||