aboutsummaryrefslogtreecommitdiff
path: root/crates/base_db/src
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2021-03-16 14:54:12 +0000
committerGitHub <[email protected]>2021-03-16 14:54:12 +0000
commit979e788957ced1957ee9ac1da70fb97abf9fe2b1 (patch)
tree1777ab043cb0750854b27a8aec805454de5c3277 /crates/base_db/src
parentb4ed3e1551f828d44dcd8e0caf08420438e5eb1a (diff)
parentbebee2106de7bbd20f54d7f55d5c56dba0d636b6 (diff)
Merge #8034
8034: Implement Crate::transitive_reverse_dependencies r=matklad a=Veykril changelog internal Implement Crate::transitive_reverse_dependencies Co-authored-by: Lukas Wirth <[email protected]>
Diffstat (limited to 'crates/base_db/src')
-rw-r--r--crates/base_db/src/fixture.rs12
-rw-r--r--crates/base_db/src/input.rs27
2 files changed, 37 insertions, 2 deletions
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 @@
57//! fn insert_source_code_here() {} 57//! fn insert_source_code_here() {}
58//! " 58//! "
59//! ``` 59//! ```
60use std::{str::FromStr, sync::Arc}; 60use std::{mem, str::FromStr, sync::Arc};
61 61
62use cfg::CfgOptions; 62use cfg::CfgOptions;
63use rustc_hash::FxHashMap; 63use rustc_hash::FxHashMap;
@@ -148,6 +148,7 @@ impl ChangeFixture {
148 let mut file_set = FileSet::default(); 148 let mut file_set = FileSet::default();
149 let source_root_prefix = "/".to_string(); 149 let source_root_prefix = "/".to_string();
150 let mut file_id = FileId(0); 150 let mut file_id = FileId(0);
151 let mut roots = Vec::new();
151 152
152 let mut file_position = None; 153 let mut file_position = None;
153 154
@@ -168,6 +169,10 @@ impl ChangeFixture {
168 let meta = FileMeta::from(entry); 169 let meta = FileMeta::from(entry);
169 assert!(meta.path.starts_with(&source_root_prefix)); 170 assert!(meta.path.starts_with(&source_root_prefix));
170 171
172 if meta.introduce_new_source_root {
173 roots.push(SourceRoot::new_local(mem::take(&mut file_set)));
174 }
175
171 if let Some(krate) = meta.krate { 176 if let Some(krate) = meta.krate {
172 let crate_name = CrateName::normalize_dashes(&krate); 177 let crate_name = CrateName::normalize_dashes(&krate);
173 let crate_id = crate_graph.add_crate_root( 178 let crate_id = crate_graph.add_crate_root(
@@ -215,7 +220,8 @@ impl ChangeFixture {
215 } 220 }
216 } 221 }
217 222
218 change.set_roots(vec![SourceRoot::new_local(file_set)]); 223 roots.push(SourceRoot::new_local(mem::take(&mut file_set)));
224 change.set_roots(roots);
219 change.set_crate_graph(crate_graph); 225 change.set_crate_graph(crate_graph);
220 226
221 ChangeFixture { file_position, files, change } 227 ChangeFixture { file_position, files, change }
@@ -229,6 +235,7 @@ struct FileMeta {
229 cfg: CfgOptions, 235 cfg: CfgOptions,
230 edition: Edition, 236 edition: Edition,
231 env: Env, 237 env: Env,
238 introduce_new_source_root: bool,
232} 239}
233 240
234impl From<Fixture> for FileMeta { 241impl From<Fixture> for FileMeta {
@@ -247,6 +254,7 @@ impl From<Fixture> for FileMeta {
247 .as_ref() 254 .as_ref()
248 .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()), 255 .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()),
249 env: f.env.into_iter().collect(), 256 env: f.env.into_iter().collect(),
257 introduce_new_source_root: f.introduce_new_source_root,
250 } 258 }
251 } 259 }
252} 260}
diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
index b5f7e4200..d0def2181 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -274,6 +274,33 @@ 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::<_, Vec<_>>::default();
285 self.arena.iter().for_each(|(&krate, data)| {
286 data.dependencies
287 .iter()
288 .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate))
289 });
290
291 while let Some(krate) = worklist.pop() {
292 if let Some(krate_rev_deps) = inverted_graph.get(&krate) {
293 krate_rev_deps
294 .iter()
295 .copied()
296 .filter(|&rev_dep| rev_deps.insert(rev_dep))
297 .for_each(|rev_dep| worklist.push(rev_dep));
298 }
299 }
300
301 rev_deps.into_iter()
302 }
303
277 /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate 304 /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
278 /// come before the crate itself). 305 /// come before the crate itself).
279 pub fn crates_in_topological_order(&self) -> Vec<CrateId> { 306 pub fn crates_in_topological_order(&self) -> Vec<CrateId> {