aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src/method_resolution.rs
diff options
context:
space:
mode:
authorFlorian Diebold <[email protected]>2021-04-07 18:35:24 +0100
committerFlorian Diebold <[email protected]>2021-04-09 10:21:31 +0100
commitfdd721e9ef4d330351769a7498d459a198bf0a0b (patch)
tree5faf803211bb427d97d82e2e44ddc1b4ae6ca3c4 /crates/hir_ty/src/method_resolution.rs
parent354151df3556c5e2989746aa01a5aeb620ee9baa (diff)
Improve indexing of impls
Store impls for e.g. &Foo with the ones for Foo instead of the big "other" bucket. This can improve performance and simplifies the HIR impl search a bit.
Diffstat (limited to 'crates/hir_ty/src/method_resolution.rs')
-rw-r--r--crates/hir_ty/src/method_resolution.rs81
1 files changed, 63 insertions, 18 deletions
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index be3e4f09a..55c7b1a09 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -13,6 +13,7 @@ use hir_def::{
13}; 13};
14use hir_expand::name::Name; 14use hir_expand::name::Name;
15use rustc_hash::{FxHashMap, FxHashSet}; 15use rustc_hash::{FxHashMap, FxHashSet};
16use stdx::always;
16 17
17use crate::{ 18use crate::{
18 autoderef, 19 autoderef,
@@ -21,32 +22,36 @@ use crate::{
21 primitive::{self, FloatTy, IntTy, UintTy}, 22 primitive::{self, FloatTy, IntTy, UintTy},
22 static_lifetime, 23 static_lifetime,
23 utils::all_super_traits, 24 utils::all_super_traits,
24 AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId, 25 AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, ForeignDefId, InEnvironment, Interner,
25 InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder, 26 Scalar, Substitution, TraitEnvironment, TraitRefExt, Ty, TyBuilder, TyExt, TyKind,
26 TyExt, TyKind,
27}; 27};
28 28
29/// This is used as a key for indexing impls. 29/// This is used as a key for indexing impls.
30#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] 30#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
31pub enum TyFingerprint { 31pub enum TyFingerprint {
32 // These are lang item impls:
32 Str, 33 Str,
33 Slice, 34 Slice,
34 Array, 35 Array,
35 Never, 36 Never,
36 RawPtr(Mutability), 37 RawPtr(Mutability),
37 Scalar(Scalar), 38 Scalar(Scalar),
39 // These can have user-defined impls:
38 Adt(hir_def::AdtId), 40 Adt(hir_def::AdtId),
39 Dyn(TraitId), 41 Dyn(TraitId),
40 Tuple(usize),
41 ForeignType(ForeignDefId), 42 ForeignType(ForeignDefId),
42 FnPtr(usize, FnSig), 43 // These only exist for trait impls
44 Unit,
45 Unnameable,
46 Function(u32),
43} 47}
44 48
45impl TyFingerprint { 49impl TyFingerprint {
46 /// Creates a TyFingerprint for looking up an impl. Only certain types can 50 /// Creates a TyFingerprint for looking up an inherent impl. Only certain
47 /// have impls: if we have some `struct S`, we can have an `impl S`, but not 51 /// types can have inherent impls: if we have some `struct S`, we can have
48 /// `impl &S`. Hence, this will return `None` for reference types and such. 52 /// an `impl S`, but not `impl &S`. Hence, this will return `None` for
49 pub fn for_impl(ty: &Ty) -> Option<TyFingerprint> { 53 /// reference types and such.
54 pub fn for_inherent_impl(ty: &Ty) -> Option<TyFingerprint> {
50 let fp = match ty.kind(&Interner) { 55 let fp = match ty.kind(&Interner) {
51 TyKind::Str => TyFingerprint::Str, 56 TyKind::Str => TyFingerprint::Str,
52 TyKind::Never => TyFingerprint::Never, 57 TyKind::Never => TyFingerprint::Never,
@@ -54,17 +59,52 @@ impl TyFingerprint {
54 TyKind::Array(..) => TyFingerprint::Array, 59 TyKind::Array(..) => TyFingerprint::Array,
55 TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar), 60 TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
56 TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt), 61 TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
57 TyKind::Tuple(cardinality, _) => TyFingerprint::Tuple(*cardinality),
58 TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability), 62 TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
59 TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id), 63 TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
60 TyKind::Function(FnPointer { sig, substitution: substs, .. }) => {
61 TyFingerprint::FnPtr(substs.0.len(&Interner) - 1, *sig)
62 }
63 TyKind::Dyn(_) => ty.dyn_trait().map(|trait_| TyFingerprint::Dyn(trait_))?, 64 TyKind::Dyn(_) => ty.dyn_trait().map(|trait_| TyFingerprint::Dyn(trait_))?,
64 _ => return None, 65 _ => return None,
65 }; 66 };
66 Some(fp) 67 Some(fp)
67 } 68 }
69
70 /// Creates a TyFingerprint for looking up a trait impl.
71 pub fn for_trait_impl(ty: &Ty) -> Option<TyFingerprint> {
72 let fp = match ty.kind(&Interner) {
73 TyKind::Str => TyFingerprint::Str,
74 TyKind::Never => TyFingerprint::Never,
75 TyKind::Slice(..) => TyFingerprint::Slice,
76 TyKind::Array(..) => TyFingerprint::Array,
77 TyKind::Scalar(scalar) => TyFingerprint::Scalar(*scalar),
78 TyKind::Adt(AdtId(adt), _) => TyFingerprint::Adt(*adt),
79 TyKind::Raw(mutability, ..) => TyFingerprint::RawPtr(*mutability),
80 TyKind::Foreign(alias_id, ..) => TyFingerprint::ForeignType(*alias_id),
81 TyKind::Dyn(_) => ty.dyn_trait().map(|trait_| TyFingerprint::Dyn(trait_))?,
82 TyKind::Ref(_, _, ty) => return TyFingerprint::for_trait_impl(ty),
83 TyKind::Tuple(_, subst) => {
84 let first_ty = subst.interned().get(0).map(|arg| arg.assert_ty_ref(&Interner));
85 if let Some(ty) = first_ty {
86 return TyFingerprint::for_trait_impl(ty);
87 } else {
88 TyFingerprint::Unit
89 }
90 }
91 TyKind::AssociatedType(_, _)
92 | TyKind::OpaqueType(_, _)
93 | TyKind::FnDef(_, _)
94 | TyKind::Closure(_, _)
95 | TyKind::Generator(..)
96 | TyKind::GeneratorWitness(..) => TyFingerprint::Unnameable,
97 TyKind::Function(fn_ptr) => {
98 TyFingerprint::Function(fn_ptr.substitution.0.len(&Interner) as u32)
99 }
100 TyKind::Alias(_)
101 | TyKind::Placeholder(_)
102 | TyKind::BoundVar(_)
103 | TyKind::InferenceVar(_, _)
104 | TyKind::Error => return None,
105 };
106 Some(fp)
107 }
68} 108}
69 109
70pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [ 110pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [
@@ -112,7 +152,7 @@ impl TraitImpls {
112 None => continue, 152 None => continue,
113 }; 153 };
114 let self_ty = db.impl_self_ty(impl_id); 154 let self_ty = db.impl_self_ty(impl_id);
115 let self_ty_fp = TyFingerprint::for_impl(self_ty.skip_binders()); 155 let self_ty_fp = TyFingerprint::for_trait_impl(self_ty.skip_binders());
116 impls 156 impls
117 .map 157 .map
118 .entry(target_trait) 158 .entry(target_trait)
@@ -157,10 +197,13 @@ impl TraitImpls {
157 } 197 }
158 198
159 /// Queries all trait impls for the given type. 199 /// Queries all trait impls for the given type.
160 pub fn for_self_ty(&self, fp: TyFingerprint) -> impl Iterator<Item = ImplId> + '_ { 200 pub fn for_self_ty_without_blanket_impls(
201 &self,
202 fp: TyFingerprint,
203 ) -> impl Iterator<Item = ImplId> + '_ {
161 self.map 204 self.map
162 .values() 205 .values()
163 .flat_map(move |impls| impls.get(&None).into_iter().chain(impls.get(&Some(fp)))) 206 .flat_map(move |impls| impls.get(&Some(fp)).into_iter())
164 .flat_map(|it| it.iter().copied()) 207 .flat_map(|it| it.iter().copied())
165 } 208 }
166 209
@@ -215,7 +258,9 @@ impl InherentImpls {
215 } 258 }
216 259
217 let self_ty = db.impl_self_ty(impl_id); 260 let self_ty = db.impl_self_ty(impl_id);
218 if let Some(fp) = TyFingerprint::for_impl(self_ty.skip_binders()) { 261 let fp = TyFingerprint::for_inherent_impl(self_ty.skip_binders());
262 always!(fp.is_some());
263 if let Some(fp) = fp {
219 map.entry(fp).or_default().push(impl_id); 264 map.entry(fp).or_default().push(impl_id);
220 } 265 }
221 } 266 }
@@ -228,7 +273,7 @@ impl InherentImpls {
228 } 273 }
229 274
230 pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] { 275 pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] {
231 match TyFingerprint::for_impl(self_ty) { 276 match TyFingerprint::for_inherent_impl(self_ty) {
232 Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]), 277 Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]),
233 None => &[], 278 None => &[],
234 } 279 }