diff options
author | bors[bot] <26634292+bors[bot]@users.noreply.github.com> | 2020-04-11 17:21:28 +0100 |
---|---|---|
committer | GitHub <[email protected]> | 2020-04-11 17:21:28 +0100 |
commit | 11d400b63b07d3cffbe8d1363b802a2d52f5d786 (patch) | |
tree | d62db2469ddd7f8a0be7815d6170b304680f5e7a /crates/ra_hir_ty | |
parent | e7a68c8f55e0770fdeae508a1710509c13aaffa1 (diff) | |
parent | a2783df3f00eb2cc8d6832f44fe8aa7ea3be46c8 (diff) |
Merge #3944
3944: Look up trait impls by self type r=matklad a=flodiebold
This speeds up inference in analysis-stats by ~30% (even more with the recursive solver).
There's a slight difference in inferred types, which I think comes from pre-existing wrong handling of error types in impls, so I think it's fine.
Co-authored-by: Florian Diebold <[email protected]>
Diffstat (limited to 'crates/ra_hir_ty')
-rw-r--r-- | crates/ra_hir_ty/src/db.rs | 9 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/method_resolution.rs | 45 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/traits.rs | 14 | ||||
-rw-r--r-- | crates/ra_hir_ty/src/traits/chalk.rs | 11 |
4 files changed, 65 insertions, 14 deletions
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs index 1462b053f..33da16b48 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::{CrateImplDefs, TyFingerprint}, |
15 | traits::{chalk, AssocTyValue, Impl}, | 15 | traits::{chalk, AssocTyValue, Impl}, |
16 | Binders, CallableDef, GenericPredicate, InferenceResult, PolyFnSig, Substs, TraitRef, Ty, | 16 | Binders, CallableDef, GenericPredicate, InferenceResult, PolyFnSig, Substs, TraitRef, Ty, |
17 | TyDefId, TypeCtor, ValueTyDefId, | 17 | TyDefId, TypeCtor, ValueTyDefId, |
@@ -65,7 +65,12 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> { | |||
65 | fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>; | 65 | fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>; |
66 | 66 | ||
67 | #[salsa::invoke(crate::traits::impls_for_trait_query)] | 67 | #[salsa::invoke(crate::traits::impls_for_trait_query)] |
68 | fn impls_for_trait(&self, krate: CrateId, trait_: TraitId) -> Arc<[ImplId]>; | 68 | fn impls_for_trait( |
69 | &self, | ||
70 | krate: CrateId, | ||
71 | trait_: TraitId, | ||
72 | self_ty_fp: Option<TyFingerprint>, | ||
73 | ) -> Arc<[ImplId]>; | ||
69 | 74 | ||
70 | // Interned IDs for Chalk integration | 75 | // Interned IDs for Chalk integration |
71 | #[salsa::interned] | 76 | #[salsa::interned] |
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index 74a0bc7db..657284fd0 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs | |||
@@ -34,7 +34,7 @@ impl TyFingerprint { | |||
34 | /// Creates a TyFingerprint for looking up an impl. Only certain types can | 34 | /// Creates a TyFingerprint for looking up an impl. Only certain types can |
35 | /// have impls: if we have some `struct S`, we can have an `impl S`, but not | 35 | /// have impls: if we have some `struct S`, we can have an `impl S`, but not |
36 | /// `impl &S`. Hence, this will return `None` for reference types and such. | 36 | /// `impl &S`. Hence, this will return `None` for reference types and such. |
37 | fn for_impl(ty: &Ty) -> Option<TyFingerprint> { | 37 | pub(crate) fn for_impl(ty: &Ty) -> Option<TyFingerprint> { |
38 | match ty { | 38 | match ty { |
39 | Ty::Apply(a_ty) => Some(TyFingerprint::Apply(a_ty.ctor)), | 39 | Ty::Apply(a_ty) => Some(TyFingerprint::Apply(a_ty.ctor)), |
40 | _ => None, | 40 | _ => None, |
@@ -45,7 +45,7 @@ impl TyFingerprint { | |||
45 | #[derive(Debug, PartialEq, Eq)] | 45 | #[derive(Debug, PartialEq, Eq)] |
46 | pub struct CrateImplDefs { | 46 | pub struct CrateImplDefs { |
47 | impls: FxHashMap<TyFingerprint, Vec<ImplId>>, | 47 | impls: FxHashMap<TyFingerprint, Vec<ImplId>>, |
48 | impls_by_trait: FxHashMap<TraitId, Vec<ImplId>>, | 48 | impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>, |
49 | } | 49 | } |
50 | 50 | ||
51 | impl CrateImplDefs { | 51 | impl CrateImplDefs { |
@@ -59,7 +59,14 @@ impl CrateImplDefs { | |||
59 | for impl_id in module_data.scope.impls() { | 59 | for impl_id in module_data.scope.impls() { |
60 | match db.impl_trait(impl_id) { | 60 | match db.impl_trait(impl_id) { |
61 | Some(tr) => { | 61 | Some(tr) => { |
62 | res.impls_by_trait.entry(tr.value.trait_).or_default().push(impl_id); | 62 | let self_ty = db.impl_self_ty(impl_id); |
63 | let self_ty_fp = TyFingerprint::for_impl(&self_ty.value); | ||
64 | res.impls_by_trait | ||
65 | .entry(tr.value.trait_) | ||
66 | .or_default() | ||
67 | .entry(self_ty_fp) | ||
68 | .or_default() | ||
69 | .push(impl_id); | ||
63 | } | 70 | } |
64 | None => { | 71 | None => { |
65 | let self_ty = db.impl_self_ty(impl_id); | 72 | let self_ty = db.impl_self_ty(impl_id); |
@@ -79,11 +86,39 @@ impl CrateImplDefs { | |||
79 | } | 86 | } |
80 | 87 | ||
81 | pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ { | 88 | pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ { |
82 | self.impls_by_trait.get(&tr).into_iter().flatten().copied() | 89 | self.impls_by_trait |
90 | .get(&tr) | ||
91 | .into_iter() | ||
92 | .flat_map(|m| m.values().flat_map(|v| v.iter().copied())) | ||
93 | } | ||
94 | |||
95 | pub fn lookup_impl_defs_for_trait_and_ty( | ||
96 | &self, | ||
97 | tr: TraitId, | ||
98 | fp: TyFingerprint, | ||
99 | ) -> impl Iterator<Item = ImplId> + '_ { | ||
100 | self.impls_by_trait | ||
101 | .get(&tr) | ||
102 | .and_then(|m| m.get(&Some(fp))) | ||
103 | .into_iter() | ||
104 | .flatten() | ||
105 | .copied() | ||
106 | .chain( | ||
107 | self.impls_by_trait | ||
108 | .get(&tr) | ||
109 | .and_then(|m| m.get(&None)) | ||
110 | .into_iter() | ||
111 | .flatten() | ||
112 | .copied(), | ||
113 | ) | ||
83 | } | 114 | } |
84 | 115 | ||
85 | pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a { | 116 | pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a { |
86 | self.impls.values().chain(self.impls_by_trait.values()).flatten().copied() | 117 | self.impls |
118 | .values() | ||
119 | .chain(self.impls_by_trait.values().flat_map(|m| m.values())) | ||
120 | .flatten() | ||
121 | .copied() | ||
87 | } | 122 | } |
88 | } | 123 | } |
89 | 124 | ||
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs index 21e233379..43d8d1e80 100644 --- a/crates/ra_hir_ty/src/traits.rs +++ b/crates/ra_hir_ty/src/traits.rs | |||
@@ -7,7 +7,7 @@ use ra_db::{impl_intern_key, salsa, CrateId}; | |||
7 | use ra_prof::profile; | 7 | use ra_prof::profile; |
8 | use rustc_hash::FxHashSet; | 8 | use rustc_hash::FxHashSet; |
9 | 9 | ||
10 | use crate::{db::HirDatabase, DebruijnIndex}; | 10 | use crate::{db::HirDatabase, method_resolution::TyFingerprint, DebruijnIndex}; |
11 | 11 | ||
12 | use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; | 12 | use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; |
13 | 13 | ||
@@ -40,7 +40,12 @@ pub(crate) fn impls_for_trait_query( | |||
40 | db: &dyn HirDatabase, | 40 | db: &dyn HirDatabase, |
41 | krate: CrateId, | 41 | krate: CrateId, |
42 | trait_: TraitId, | 42 | trait_: TraitId, |
43 | self_ty_fp: Option<TyFingerprint>, | ||
43 | ) -> Arc<[ImplId]> { | 44 | ) -> Arc<[ImplId]> { |
45 | // FIXME: We could be a lot smarter here - because of the orphan rules and | ||
46 | // the fact that the trait and the self type need to be in the dependency | ||
47 | // tree of a crate somewhere for an impl to exist, we could skip looking in | ||
48 | // a lot of crates completely | ||
44 | let mut impls = FxHashSet::default(); | 49 | let mut impls = FxHashSet::default(); |
45 | // We call the query recursively here. On the one hand, this means we can | 50 | // We call the query recursively here. On the one hand, this means we can |
46 | // reuse results from queries for different crates; on the other hand, this | 51 | // reuse results from queries for different crates; on the other hand, this |
@@ -48,10 +53,13 @@ pub(crate) fn impls_for_trait_query( | |||
48 | // ones the user is editing), so this may actually be a waste of memory. I'm | 53 | // ones the user is editing), so this may actually be a waste of memory. I'm |
49 | // doing it like this mainly for simplicity for now. | 54 | // doing it like this mainly for simplicity for now. |
50 | for dep in &db.crate_graph()[krate].dependencies { | 55 | for dep in &db.crate_graph()[krate].dependencies { |
51 | impls.extend(db.impls_for_trait(dep.crate_id, trait_).iter()); | 56 | impls.extend(db.impls_for_trait(dep.crate_id, trait_, self_ty_fp).iter()); |
52 | } | 57 | } |
53 | let crate_impl_defs = db.impls_in_crate(krate); | 58 | let crate_impl_defs = db.impls_in_crate(krate); |
54 | impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_)); | 59 | match self_ty_fp { |
60 | Some(fp) => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp)), | ||
61 | None => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_)), | ||
62 | } | ||
55 | impls.into_iter().collect() | 63 | impls.into_iter().collect() |
56 | } | 64 | } |
57 | 65 | ||
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs index c5f1b5232..e05fea843 100644 --- a/crates/ra_hir_ty/src/traits/chalk.rs +++ b/crates/ra_hir_ty/src/traits/chalk.rs | |||
@@ -16,8 +16,8 @@ use ra_db::{ | |||
16 | 16 | ||
17 | use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation}; | 17 | use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation}; |
18 | use crate::{ | 18 | use crate::{ |
19 | db::HirDatabase, display::HirDisplay, utils::generics, ApplicationTy, GenericPredicate, | 19 | db::HirDatabase, display::HirDisplay, method_resolution::TyFingerprint, utils::generics, |
20 | ProjectionTy, Substs, TraitRef, Ty, TypeCtor, | 20 | ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor, |
21 | }; | 21 | }; |
22 | 22 | ||
23 | pub(super) mod tls; | 23 | pub(super) mod tls; |
@@ -647,19 +647,22 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> { | |||
647 | debug!("impls_for_trait {:?}", trait_id); | 647 | debug!("impls_for_trait {:?}", trait_id); |
648 | let trait_: hir_def::TraitId = from_chalk(self.db, trait_id); | 648 | let trait_: hir_def::TraitId = from_chalk(self.db, trait_id); |
649 | 649 | ||
650 | let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone()); | ||
651 | |||
652 | let self_ty_fp = TyFingerprint::for_impl(&ty); | ||
653 | |||
650 | // Note: Since we're using impls_for_trait, only impls where the trait | 654 | // Note: Since we're using impls_for_trait, only impls where the trait |
651 | // can be resolved should ever reach Chalk. `impl_datum` relies on that | 655 | // can be resolved should ever reach Chalk. `impl_datum` relies on that |
652 | // and will panic if the trait can't be resolved. | 656 | // and will panic if the trait can't be resolved. |
653 | let mut result: Vec<_> = self | 657 | let mut result: Vec<_> = self |
654 | .db | 658 | .db |
655 | .impls_for_trait(self.krate, trait_) | 659 | .impls_for_trait(self.krate, trait_, self_ty_fp) |
656 | .iter() | 660 | .iter() |
657 | .copied() | 661 | .copied() |
658 | .map(Impl::ImplDef) | 662 | .map(Impl::ImplDef) |
659 | .map(|impl_| impl_.to_chalk(self.db)) | 663 | .map(|impl_| impl_.to_chalk(self.db)) |
660 | .collect(); | 664 | .collect(); |
661 | 665 | ||
662 | let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone()); | ||
663 | let arg: Option<Ty> = | 666 | let arg: Option<Ty> = |
664 | parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone())); | 667 | parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone())); |
665 | 668 | ||