From 77f67ca7e2caac6d94215834981ae3f6fb908443 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Sun, 13 Jan 2019 12:27:26 +0300 Subject: gracefully handle cycles in crate graph rust-lang/rust has absolutely weird setup with rustc-workspace-shim, which leads to real cycles. --- crates/ra_db/src/input.rs | 82 +++++++++++++++++++++++++++-------------------- 1 file changed, 48 insertions(+), 34 deletions(-) (limited to 'crates/ra_db/src') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index 023183e29..2b761ea0c 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -53,6 +53,9 @@ pub struct CrateGraph { arena: FxHashMap, } +#[derive(Debug)] +pub struct CyclicDependencies; + #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct CrateId(pub u32); @@ -94,12 +97,16 @@ impl CrateGraph { assert!(prev.is_none()); crate_id } - pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { - let mut visited = FxHashSet::default(); - if self.dfs_find(from, to, &mut visited) { - panic!("Cycle dependencies found.") + pub fn add_dep( + &mut self, + from: CrateId, + name: SmolStr, + to: CrateId, + ) -> Result<(), CyclicDependencies> { + if self.dfs_find(from, to, &mut FxHashSet::default()) { + return Err(CyclicDependencies); } - self.arena.get_mut(&from).unwrap().add_dep(name, to) + Ok(self.arena.get_mut(&from).unwrap().add_dep(name, to)) } pub fn is_empty(&self) -> bool { self.arena.is_empty() @@ -139,35 +146,6 @@ impl CrateGraph { } } -#[cfg(test)] -mod tests { - use super::{CrateGraph, FxHashMap, FileId, SmolStr}; - - #[test] - #[should_panic] - fn it_should_painc_because_of_cycle_dependencies() { - let mut graph = CrateGraph::default(); - let crate1 = graph.add_crate_root(FileId(1u32)); - let crate2 = graph.add_crate_root(FileId(2u32)); - let crate3 = graph.add_crate_root(FileId(3u32)); - graph.add_dep(crate1, SmolStr::new("crate2"), crate2); - graph.add_dep(crate2, SmolStr::new("crate3"), crate3); - graph.add_dep(crate3, SmolStr::new("crate1"), crate1); - } - - #[test] - fn it_works() { - let mut graph = CrateGraph { - arena: FxHashMap::default(), - }; - let crate1 = graph.add_crate_root(FileId(1u32)); - let crate2 = graph.add_crate_root(FileId(2u32)); - let crate3 = graph.add_crate_root(FileId(3u32)); - graph.add_dep(crate1, SmolStr::new("crate2"), crate2); - graph.add_dep(crate2, SmolStr::new("crate3"), crate3); - } -} - salsa::query_group! { pub trait FilesDatabase: salsa::Database { /// Text of the file. @@ -209,3 +187,39 @@ salsa::query_group! { } } } + +#[cfg(test)] +mod tests { + use super::{CrateGraph, FileId, SmolStr}; + + #[test] + fn it_should_painc_because_of_cycle_dependencies() { + let mut graph = CrateGraph::default(); + let crate1 = graph.add_crate_root(FileId(1u32)); + let crate2 = graph.add_crate_root(FileId(2u32)); + let crate3 = graph.add_crate_root(FileId(3u32)); + assert!(graph + .add_dep(crate1, SmolStr::new("crate2"), crate2) + .is_ok()); + assert!(graph + .add_dep(crate2, SmolStr::new("crate3"), crate3) + .is_ok()); + assert!(graph + .add_dep(crate3, SmolStr::new("crate1"), crate1) + .is_err()); + } + + #[test] + fn it_works() { + let mut graph = CrateGraph::default(); + let crate1 = graph.add_crate_root(FileId(1u32)); + let crate2 = graph.add_crate_root(FileId(2u32)); + let crate3 = graph.add_crate_root(FileId(3u32)); + assert!(graph + .add_dep(crate1, SmolStr::new("crate2"), crate2) + .is_ok()); + assert!(graph + .add_dep(crate2, SmolStr::new("crate3"), crate3) + .is_ok()); + } +} -- cgit v1.2.3