From 45a8f37b6ae230db6c30c013f17d8aebac98a5e1 Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
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 +++-
1 file changed, 3 insertions(+), 1 deletion(-)
(limited to 'crates/base_db')
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<Item = CrateId> + '_ {
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
From 521a26b0d207fc6d9293e06ca2c9a669bb66ddc4 Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
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/base_db')
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<Item = CrateId> + '_ {
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 <aleksey.kladov@gmail.com>
Date: Tue, 23 Mar 2021 12:59:51 +0300
Subject: Align naming of deps and revdeps
---
crates/base_db/src/input.rs | 5 +----
1 file changed, 1 insertion(+), 4 deletions(-)
(limited to 'crates/base_db')
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<Item = CrateId> + '_ {
+ pub fn transitive_rev_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
let mut worklist = vec![of];
let mut rev_deps = FxHashSet::default();
rev_deps.insert(of);
--
cgit v1.2.3
From fa9c6eb4560c3c72a726dba4210af2edbb3dd4bb Mon Sep 17 00:00:00 2001
From: Aleksey Kladov <aleksey.kladov@gmail.com>
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/base_db')
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