From e97cd709cd91ccfafbd45bab8b2bf01f3ddf6a04 Mon Sep 17 00:00:00 2001 From: Lukas Wirth Date: Mon, 15 Mar 2021 17:43:46 +0100 Subject: Implement Crate::transitive_reverse_dependencies --- crates/base_db/src/input.rs | 28 ++++++++++++++++++++++++++++ crates/hir/src/lib.rs | 23 +++++++++++++++++++---- crates/ide/src/references.rs | 23 +++++++++++++++++++++++ crates/ide_db/src/search.rs | 2 +- 4 files changed, 71 insertions(+), 5 deletions(-) (limited to 'crates') 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 { deps.into_iter() } + /// Returns an iterator over all transitive reverse dependencies of the given crate. + pub fn transitive_reverse_dependencies( + &self, + of: CrateId, + ) -> impl Iterator + '_ { + let mut worklist = vec![of]; + let mut rev_deps = FxHashSet::default(); + let mut inverted_graph = FxHashMap::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) + }) + }); + + 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); + } + } + + rev_deps.remove(&of); + rev_deps.into_iter() + } + /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate /// come before the crate itself). pub fn crates_in_topological_order(&self) -> Vec { 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::{ InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty, TyDefId, TyKind, TyVariableKind, }; +use itertools::Itertools; use rustc_hash::FxHashSet; use stdx::{format_to, impl_from}; use syntax::{ @@ -139,7 +140,6 @@ impl Crate { .collect() } - // FIXME: add `transitive_reverse_dependencies`. pub fn reverse_dependencies(self, db: &dyn HirDatabase) -> Vec { let crate_graph = db.crate_graph(); crate_graph @@ -151,6 +151,14 @@ impl Crate { .collect() } + 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() + } + pub fn root_module(self, db: &dyn HirDatabase) -> Module { let def_map = db.crate_def_map(self.id); Module { id: def_map.module_id(def_map.root()) } @@ -1497,11 +1505,17 @@ impl Impl { }; let mut all = Vec::new(); - def_crates.into_iter().for_each(|id| { + def_crates.iter().for_each(|&id| { all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter)) }); let fp = TyFingerprint::for_impl(&ty.value); - for id in db.crate_graph().iter() { + for id in def_crates + .iter() + .flat_map(|&id| Crate { id }.transitive_reverse_dependencies(db)) + .map(|Crate { id }| id) + .chain(def_crates.iter().copied()) + .unique() + { match fp { Some(fp) => all.extend( db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter), @@ -1516,7 +1530,8 @@ 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.reverse_dependencies(db).into_iter().chain(Some(krate)) { + for Crate { id } in krate.transitive_reverse_dependencies(db).into_iter().chain(Some(krate)) + { let impls = db.trait_impls_in_crate(id); all.extend(impls.for_trait(trait_.id).map(Self::from)) } 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 } "#]], ); } + + #[test] + fn test_transitive() { + check( + r#" +//- /level3/level3.rs crate:level3 +pub struct Fo$0o; +//- /level2/level2.rs crate:level2 deps:level3 +pub use level3::Foo; +//- /level1/level1.rs crate:level1 deps:level2 +pub use level2::Foo; +//- /level0/level0.rs crate:level0 deps:level1 +pub use level1::Foo; +"#, + expect![[r#" + Foo Struct FileId(0) 0..15 11..14 + + FileId(1) 16..19 + FileId(2) 16..19 + FileId(3) 16..19 + "#]], + ); + } } 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 { let mut res = source_root.iter().map(|id| (id, None)).collect::>(); let krate = module.krate(); - for rev_dep in krate.reverse_dependencies(db) { + for rev_dep in krate.transitive_reverse_dependencies(db) { let root_file = rev_dep.root_file(db); let source_root_id = db.file_source_root(root_file); let source_root = db.source_root(source_root_id); -- cgit v1.2.3 From 75fafd6fcc010c71d770d19bea4b744b92c5267b Mon Sep 17 00:00:00 2001 From: Lukas Wirth Date: Tue, 16 Mar 2021 15:28:02 +0100 Subject: Add new_source_root meta to test fixtures --- crates/base_db/src/fixture.rs | 12 ++++++++++-- crates/ide/src/references.rs | 8 ++++---- crates/test_utils/src/fixture.rs | 15 ++++++++++++++- 3 files changed, 28 insertions(+), 7 deletions(-) (limited to 'crates') diff --git a/crates/base_db/src/fixture.rs b/crates/base_db/src/fixture.rs index 5c9824814..cad6866aa 100644 --- a/crates/base_db/src/fixture.rs +++ b/crates/base_db/src/fixture.rs @@ -57,7 +57,7 @@ //! fn insert_source_code_here() {} //! " //! ``` -use std::{str::FromStr, sync::Arc}; +use std::{mem, str::FromStr, sync::Arc}; use cfg::CfgOptions; use rustc_hash::FxHashMap; @@ -148,6 +148,7 @@ impl ChangeFixture { let mut file_set = FileSet::default(); let source_root_prefix = "/".to_string(); let mut file_id = FileId(0); + let mut roots = Vec::new(); let mut file_position = None; @@ -168,6 +169,10 @@ impl ChangeFixture { let meta = FileMeta::from(entry); assert!(meta.path.starts_with(&source_root_prefix)); + if meta.introduce_new_source_root { + roots.push(SourceRoot::new_local(mem::take(&mut file_set))); + } + if let Some(krate) = meta.krate { let crate_name = CrateName::normalize_dashes(&krate); let crate_id = crate_graph.add_crate_root( @@ -215,7 +220,8 @@ impl ChangeFixture { } } - change.set_roots(vec![SourceRoot::new_local(file_set)]); + roots.push(SourceRoot::new_local(mem::take(&mut file_set))); + change.set_roots(roots); change.set_crate_graph(crate_graph); ChangeFixture { file_position, files, change } @@ -229,6 +235,7 @@ struct FileMeta { cfg: CfgOptions, edition: Edition, env: Env, + introduce_new_source_root: bool, } impl From for FileMeta { @@ -247,6 +254,7 @@ impl From for FileMeta { .as_ref() .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()), env: f.env.into_iter().collect(), + introduce_new_source_root: f.introduce_new_source_root, } } } diff --git a/crates/ide/src/references.rs b/crates/ide/src/references.rs index fc85cd0ce..e10a3ccf7 100644 --- a/crates/ide/src/references.rs +++ b/crates/ide/src/references.rs @@ -1275,13 +1275,13 @@ fn foo(_: bool) -> bo$0ol { true } fn test_transitive() { check( r#" -//- /level3/level3.rs crate:level3 +//- /level3.rs new_source_root: crate:level3 pub struct Fo$0o; -//- /level2/level2.rs crate:level2 deps:level3 +//- /level2.rs new_source_root: crate:level2 deps:level3 pub use level3::Foo; -//- /level1/level1.rs crate:level1 deps:level2 +//- /level1.rs new_source_root: crate:level1 deps:level2 pub use level2::Foo; -//- /level0/level0.rs crate:level0 deps:level1 +//- /level0.rs new_source_root: crate:level0 deps:level1 pub use level1::Foo; "#, expect![[r#" diff --git a/crates/test_utils/src/fixture.rs b/crates/test_utils/src/fixture.rs index e3f57f3b2..6bc824e94 100644 --- a/crates/test_utils/src/fixture.rs +++ b/crates/test_utils/src/fixture.rs @@ -14,6 +14,7 @@ pub struct Fixture { pub cfg_key_values: Vec<(String, String)>, pub edition: Option, pub env: FxHashMap, + pub introduce_new_source_root: bool, } impl Fixture { @@ -70,6 +71,7 @@ impl Fixture { let mut cfg_atoms = Vec::new(); let mut cfg_key_values = Vec::new(); let mut env = FxHashMap::default(); + let mut introduce_new_source_root = false; for component in components[1..].iter() { let (key, value) = split_once(component, ':').unwrap(); match key { @@ -91,11 +93,22 @@ impl Fixture { } } } + "new_source_root" => introduce_new_source_root = true, _ => panic!("bad component: {:?}", component), } } - Fixture { path, text: String::new(), krate, deps, cfg_atoms, cfg_key_values, edition, env } + Fixture { + path, + text: String::new(), + krate, + deps, + cfg_atoms, + cfg_key_values, + edition, + env, + introduce_new_source_root, + } } } -- cgit v1.2.3 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') 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