From 45a8f37b6ae230db6c30c013f17d8aebac98a5e1 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 23 Mar 2021 12:49:55 +0300 Subject: Compute more mathematically well-rounded notion of transitive deps By including the crate itself, we make the resulting set closed with respect to `transitve_reveres_dependencies` operation, as it becomes a proper transitive closure. This just feels more proper and mathy. And, indeed, this actually allows us to simplify call sites somewhat. --- crates/base_db/src/input.rs | 4 +++- crates/hir/src/lib.rs | 3 +-- crates/ide_db/src/search.rs | 4 +--- 3 files changed, 5 insertions(+), 6 deletions(-) (limited to 'crates') diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs index e9e8dfc2e..248ab1de2 100644 --- a/crates/base_db/src/input.rs +++ b/crates/base_db/src/input.rs @@ -274,13 +274,15 @@ impl CrateGraph { deps.into_iter() } - /// Returns an iterator over all transitive reverse dependencies of the given crate. + /// Returns all transitive reverse dependencies of the given crate, + /// including the crate itself. pub fn transitive_reverse_dependencies( &self, of: CrateId, ) -> impl Iterator + '_ { let mut worklist = vec![of]; let mut rev_deps = FxHashSet::default(); + rev_deps.insert(of); let mut inverted_graph = FxHashMap::<_, Vec<_>>::default(); self.arena.iter().for_each(|(&krate, data)| { data.dependencies diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs index 30b96d7e2..aefebde06 100644 --- a/crates/hir/src/lib.rs +++ b/crates/hir/src/lib.rs @@ -1572,8 +1572,7 @@ impl Impl { pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec { let krate = trait_.module(db).krate(); let mut all = Vec::new(); - for Crate { id } in krate.transitive_reverse_dependencies(db).into_iter().chain(Some(krate)) - { + for Crate { id } in krate.transitive_reverse_dependencies(db).into_iter() { let impls = db.trait_impls_in_crate(id); all.extend(impls.for_trait(trait_.id).map(Self::from)) } diff --git a/crates/ide_db/src/search.rs b/crates/ide_db/src/search.rs index 324817cd0..8e93de277 100644 --- a/crates/ide_db/src/search.rs +++ b/crates/ide_db/src/search.rs @@ -245,9 +245,7 @@ impl Definition { } if let Some(Visibility::Public) = vis { - let source_root_id = db.file_source_root(file_id); - let source_root = db.source_root(source_root_id); - let mut res = source_root.iter().map(|id| (id, None)).collect::>(); + let mut res = FxHashMap::default(); let krate = module.krate(); for rev_dep in krate.transitive_reverse_dependencies(db) { -- cgit v1.2.3 From 521a26b0d207fc6d9293e06ca2c9a669bb66ddc4 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 23 Mar 2021 12:58:48 +0300 Subject: Align semantics of deps and rev deps --- crates/base_db/src/input.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'crates') diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs index 248ab1de2..04a338d99 100644 --- a/crates/base_db/src/input.rs +++ b/crates/base_db/src/input.rs @@ -257,7 +257,8 @@ impl CrateGraph { self.arena.keys().copied() } - /// Returns an iterator over all transitive dependencies of the given crate. + /// Returns an iterator over all transitive dependencies of the given crate, + /// including the crate itself. pub fn transitive_deps(&self, of: CrateId) -> impl Iterator + '_ { let mut worklist = vec![of]; let mut deps = FxHashSet::default(); @@ -270,7 +271,6 @@ impl CrateGraph { worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id)); } - deps.remove(&of); deps.into_iter() } -- cgit v1.2.3 From ba48c0d8bd93a0cb5c141f9296843bf5028d960d Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 23 Mar 2021 12:59:51 +0300 Subject: Align naming of deps and revdeps --- crates/base_db/src/input.rs | 5 +---- crates/hir/src/lib.rs | 6 +----- 2 files changed, 2 insertions(+), 9 deletions(-) (limited to 'crates') diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs index 04a338d99..56fb4ad71 100644 --- a/crates/base_db/src/input.rs +++ b/crates/base_db/src/input.rs @@ -276,10 +276,7 @@ impl CrateGraph { /// Returns all transitive reverse dependencies of the given crate, /// including the crate itself. - pub fn transitive_reverse_dependencies( - &self, - of: CrateId, - ) -> impl Iterator + '_ { + pub fn transitive_rev_deps(&self, of: CrateId) -> impl Iterator + '_ { let mut worklist = vec![of]; let mut rev_deps = FxHashSet::default(); rev_deps.insert(of); diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs index aefebde06..68f4551c0 100644 --- a/crates/hir/src/lib.rs +++ b/crates/hir/src/lib.rs @@ -154,11 +154,7 @@ impl Crate { } pub fn transitive_reverse_dependencies(self, db: &dyn HirDatabase) -> Vec { - db.crate_graph() - .transitive_reverse_dependencies(self.id) - .into_iter() - .map(|id| Crate { id }) - .collect() + db.crate_graph().transitive_rev_deps(self.id).into_iter().map(|id| Crate { id }).collect() } pub fn root_module(self, db: &dyn HirDatabase) -> Module { -- cgit v1.2.3 From fa9c6eb4560c3c72a726dba4210af2edbb3dd4bb Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Tue, 23 Mar 2021 13:01:45 +0300 Subject: Improve readability --- crates/base_db/src/input.rs | 1 + 1 file changed, 1 insertion(+) (limited to 'crates') diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs index 56fb4ad71..07628935f 100644 --- a/crates/base_db/src/input.rs +++ b/crates/base_db/src/input.rs @@ -280,6 +280,7 @@ impl CrateGraph { let mut worklist = vec![of]; let mut rev_deps = FxHashSet::default(); rev_deps.insert(of); + let mut inverted_graph = FxHashMap::<_, Vec<_>>::default(); self.arena.iter().for_each(|(&krate, data)| { data.dependencies -- cgit v1.2.3