aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty/src
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2020-04-11 17:21:28 +0100
committerGitHub <[email protected]>2020-04-11 17:21:28 +0100
commit11d400b63b07d3cffbe8d1363b802a2d52f5d786 (patch)
treed62db2469ddd7f8a0be7815d6170b304680f5e7a /crates/ra_hir_ty/src
parente7a68c8f55e0770fdeae508a1710509c13aaffa1 (diff)
parenta2783df3f00eb2cc8d6832f44fe8aa7ea3be46c8 (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/src')
-rw-r--r--crates/ra_hir_ty/src/db.rs9
-rw-r--r--crates/ra_hir_ty/src/method_resolution.rs45
-rw-r--r--crates/ra_hir_ty/src/traits.rs14
-rw-r--r--crates/ra_hir_ty/src/traits/chalk.rs11
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};
11use ra_prof::profile; 11use ra_prof::profile;
12 12
13use crate::{ 13use 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)]
46pub struct CrateImplDefs { 46pub 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
51impl CrateImplDefs { 51impl 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};
7use ra_prof::profile; 7use ra_prof::profile;
8use rustc_hash::FxHashSet; 8use rustc_hash::FxHashSet;
9 9
10use crate::{db::HirDatabase, DebruijnIndex}; 10use crate::{db::HirDatabase, method_resolution::TyFingerprint, DebruijnIndex};
11 11
12use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; 12use 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
17use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation}; 17use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
18use crate::{ 18use 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
23pub(super) mod tls; 23pub(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