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 +++- 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 + '_ { 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 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 + '_ { 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 +---- 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 + '_ { + 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); -- 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/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