aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
authorLukas Wirth <[email protected]>2021-03-15 16:43:46 +0000
committerLukas Wirth <[email protected]>2021-03-15 17:28:31 +0000
commite97cd709cd91ccfafbd45bab8b2bf01f3ddf6a04 (patch)
treebb6e1bcfae7fd44a7a63be31a17dc6e68799e7d5 /crates
parenteec64ec01b0553aca855df8146965ed6c6746e7d (diff)
Implement Crate::transitive_reverse_dependencies
Diffstat (limited to 'crates')
-rw-r--r--crates/base_db/src/input.rs28
-rw-r--r--crates/hir/src/lib.rs23
-rw-r--r--crates/ide/src/references.rs23
-rw-r--r--crates/ide_db/src/search.rs2
4 files changed, 71 insertions, 5 deletions
diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
index b5f7e4200..06f1c14f5 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -274,6 +274,34 @@ impl CrateGraph {
274 deps.into_iter() 274 deps.into_iter()
275 } 275 }
276 276
277 /// Returns an iterator over all transitive reverse dependencies of the given crate.
278 pub fn transitive_reverse_dependencies(
279 &self,
280 of: CrateId,
281 ) -> impl Iterator<Item = CrateId> + '_ {
282 let mut worklist = vec![of];
283 let mut rev_deps = FxHashSet::default();
284 let mut inverted_graph = FxHashMap::default();
285 self.arena.iter().for_each(|(&krate, data)| {
286 data.dependencies.iter().for_each(|dep| {
287 inverted_graph.entry(dep.crate_id).or_insert_with(Vec::default).push(krate)
288 })
289 });
290
291 while let Some(krate) = worklist.pop() {
292 if !rev_deps.insert(krate) {
293 continue;
294 }
295
296 if let Some(rev_deps) = inverted_graph.get(&krate) {
297 worklist.extend(rev_deps);
298 }
299 }
300
301 rev_deps.remove(&of);
302 rev_deps.into_iter()
303 }
304
277 /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate 305 /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
278 /// come before the crate itself). 306 /// come before the crate itself).
279 pub fn crates_in_topological_order(&self) -> Vec<CrateId> { 307 pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index c5161dadd..079a5f7b8 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -58,6 +58,7 @@ use hir_ty::{
58 InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty, 58 InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty,
59 TyDefId, TyKind, TyVariableKind, 59 TyDefId, TyKind, TyVariableKind,
60}; 60};
61use itertools::Itertools;
61use rustc_hash::FxHashSet; 62use rustc_hash::FxHashSet;
62use stdx::{format_to, impl_from}; 63use stdx::{format_to, impl_from};
63use syntax::{ 64use syntax::{
@@ -139,7 +140,6 @@ impl Crate {
139 .collect() 140 .collect()
140 } 141 }
141 142
142 // FIXME: add `transitive_reverse_dependencies`.
143 pub fn reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> { 143 pub fn reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> {
144 let crate_graph = db.crate_graph(); 144 let crate_graph = db.crate_graph();
145 crate_graph 145 crate_graph
@@ -151,6 +151,14 @@ impl Crate {
151 .collect() 151 .collect()
152 } 152 }
153 153
154 pub fn transitive_reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> {
155 db.crate_graph()
156 .transitive_reverse_dependencies(self.id)
157 .into_iter()
158 .map(|id| Crate { id })
159 .collect()
160 }
161
154 pub fn root_module(self, db: &dyn HirDatabase) -> Module { 162 pub fn root_module(self, db: &dyn HirDatabase) -> Module {
155 let def_map = db.crate_def_map(self.id); 163 let def_map = db.crate_def_map(self.id);
156 Module { id: def_map.module_id(def_map.root()) } 164 Module { id: def_map.module_id(def_map.root()) }
@@ -1497,11 +1505,17 @@ impl Impl {
1497 }; 1505 };
1498 1506
1499 let mut all = Vec::new(); 1507 let mut all = Vec::new();
1500 def_crates.into_iter().for_each(|id| { 1508 def_crates.iter().for_each(|&id| {
1501 all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter)) 1509 all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter))
1502 }); 1510 });
1503 let fp = TyFingerprint::for_impl(&ty.value); 1511 let fp = TyFingerprint::for_impl(&ty.value);
1504 for id in db.crate_graph().iter() { 1512 for id in def_crates
1513 .iter()
1514 .flat_map(|&id| Crate { id }.transitive_reverse_dependencies(db))
1515 .map(|Crate { id }| id)
1516 .chain(def_crates.iter().copied())
1517 .unique()
1518 {
1505 match fp { 1519 match fp {
1506 Some(fp) => all.extend( 1520 Some(fp) => all.extend(
1507 db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter), 1521 db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter),
@@ -1516,7 +1530,8 @@ impl Impl {
1516 pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec<Impl> { 1530 pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec<Impl> {
1517 let krate = trait_.module(db).krate(); 1531 let krate = trait_.module(db).krate();
1518 let mut all = Vec::new(); 1532 let mut all = Vec::new();
1519 for Crate { id } in krate.reverse_dependencies(db).into_iter().chain(Some(krate)) { 1533 for Crate { id } in krate.transitive_reverse_dependencies(db).into_iter().chain(Some(krate))
1534 {
1520 let impls = db.trait_impls_in_crate(id); 1535 let impls = db.trait_impls_in_crate(id);
1521 all.extend(impls.for_trait(trait_.id).map(Self::from)) 1536 all.extend(impls.for_trait(trait_.id).map(Self::from))
1522 } 1537 }
diff --git a/crates/ide/src/references.rs b/crates/ide/src/references.rs
index ec7c7686d..fc85cd0ce 100644
--- a/crates/ide/src/references.rs
+++ b/crates/ide/src/references.rs
@@ -1270,4 +1270,27 @@ fn foo(_: bool) -> bo$0ol { true }
1270 "#]], 1270 "#]],
1271 ); 1271 );
1272 } 1272 }
1273
1274 #[test]
1275 fn test_transitive() {
1276 check(
1277 r#"
1278//- /level3/level3.rs crate:level3
1279pub struct Fo$0o;
1280//- /level2/level2.rs crate:level2 deps:level3
1281pub use level3::Foo;
1282//- /level1/level1.rs crate:level1 deps:level2
1283pub use level2::Foo;
1284//- /level0/level0.rs crate:level0 deps:level1
1285pub use level1::Foo;
1286"#,
1287 expect![[r#"
1288 Foo Struct FileId(0) 0..15 11..14
1289
1290 FileId(1) 16..19
1291 FileId(2) 16..19
1292 FileId(3) 16..19
1293 "#]],
1294 );
1295 }
1273} 1296}
diff --git a/crates/ide_db/src/search.rs b/crates/ide_db/src/search.rs
index d00a8b6e7..f56221a6c 100644
--- a/crates/ide_db/src/search.rs
+++ b/crates/ide_db/src/search.rs
@@ -260,7 +260,7 @@ impl Definition {
260 let mut res = source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>(); 260 let mut res = source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>();
261 261
262 let krate = module.krate(); 262 let krate = module.krate();
263 for rev_dep in krate.reverse_dependencies(db) { 263 for rev_dep in krate.transitive_reverse_dependencies(db) {
264 let root_file = rev_dep.root_file(db); 264 let root_file = rev_dep.root_file(db);
265 let source_root_id = db.file_source_root(root_file); 265 let source_root_id = db.file_source_root(root_file);
266 let source_root = db.source_root(source_root_id); 266 let source_root = db.source_root(source_root_id);