From bebee2106de7bbd20f54d7f55d5c56dba0d636b6 Mon Sep 17 00:00:00 2001 From: Lukas Wirth Date: Tue, 16 Mar 2021 15:53:34 +0100 Subject: Don't repeat work in transitive_reverse_dependencies --- crates/base_db/src/input.rs | 21 ++++++++++----------- 1 file changed, 10 insertions(+), 11 deletions(-) (limited to 'crates/base_db/src') diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs index 06f1c14f5..d0def2181 100644 --- a/crates/base_db/src/input.rs +++ b/crates/base_db/src/input.rs @@ -281,24 +281,23 @@ impl CrateGraph { ) -> impl Iterator + '_ { let mut worklist = vec![of]; let mut rev_deps = FxHashSet::default(); - let mut inverted_graph = FxHashMap::default(); + let mut inverted_graph = FxHashMap::<_, Vec<_>>::default(); self.arena.iter().for_each(|(&krate, data)| { - data.dependencies.iter().for_each(|dep| { - inverted_graph.entry(dep.crate_id).or_insert_with(Vec::default).push(krate) - }) + data.dependencies + .iter() + .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate)) }); while let Some(krate) = worklist.pop() { - if !rev_deps.insert(krate) { - continue; - } - - if let Some(rev_deps) = inverted_graph.get(&krate) { - worklist.extend(rev_deps); + if let Some(krate_rev_deps) = inverted_graph.get(&krate) { + krate_rev_deps + .iter() + .copied() + .filter(|&rev_dep| rev_deps.insert(rev_dep)) + .for_each(|rev_dep| worklist.push(rev_dep)); } } - rev_deps.remove(&of); rev_deps.into_iter() } -- cgit v1.2.3