From 792dabc0a6a198d0fdeb6449b457a4e61009178e Mon Sep 17 00:00:00 2001 From: gfreezy Date: Fri, 21 Dec 2018 22:27:04 +0800 Subject: When constructing a crate graph, detect and forbid cycles. fixed #300 --- crates/ra_db/src/input.rs | 58 ++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 52 insertions(+), 6 deletions(-) (limited to 'crates') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index f12dd9345..f220eda9e 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -7,11 +7,12 @@ /// actual IO is done and lowered to input. use std::sync::Arc; -use rustc_hash::{FxHashMap}; use relative_path::RelativePathBuf; -use ra_syntax::SmolStr; +use rustc_hash::FxHashMap; use salsa; +use ra_syntax::SmolStr; + /// `FileId` is an integer which uniquely identifies a file. File paths are /// messy and system-dependent, so most of the code should work directly with /// `FileId`, without inspecting the path. The mapping between `FileId` and path @@ -92,10 +93,10 @@ impl CrateGraph { assert!(prev.is_none()); crate_id } - // FIXME: check that we don't have cycles here. - // Just a simple depth first search from `to` should work, - // the graph is small. pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { + if self.dfs(from, to) { + panic!("Cycle dependencies found.") + } self.arena.get_mut(&from).unwrap().add_dep(name, to) } pub fn crate_root(&self, crate_id: CrateId) -> FileId { @@ -111,11 +112,56 @@ impl CrateGraph { pub fn dependencies<'a>( &'a self, crate_id: CrateId, - ) -> impl Iterator + 'a { + ) -> impl Iterator + 'a { self.arena[&crate_id].dependencies.iter() } + fn dfs(&self, target: CrateId, from: CrateId) -> bool { + for dep in self.dependencies(from) { + let crate_id = dep.crate_id(); + if crate_id == target { + return true; + } + if self.arena.contains_key(&crate_id) { + if self.dfs(target, crate_id) { + return true; + } + } + } + return false; + } } + +mod test { + use super::{CrateGraph, FxHashMap, FileId, SmolStr}; + #[test] + #[should_panic] + fn it_should_painc_because_of_cycle_dependencies() { + 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); + 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. -- cgit v1.2.3 From 77eaa208ed2f423572fbeb8096f8c180d22c78fd Mon Sep 17 00:00:00 2001 From: gfreezy Date: Fri, 21 Dec 2018 22:30:41 +0800 Subject: rename to dfs_find --- crates/ra_db/src/input.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'crates') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index f220eda9e..f6d11844a 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -94,7 +94,7 @@ impl CrateGraph { crate_id } pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { - if self.dfs(from, to) { + if self.dfs_find(from, to) { panic!("Cycle dependencies found.") } self.arena.get_mut(&from).unwrap().add_dep(name, to) @@ -115,14 +115,14 @@ impl CrateGraph { ) -> impl Iterator + 'a { self.arena[&crate_id].dependencies.iter() } - fn dfs(&self, target: CrateId, from: CrateId) -> bool { + fn dfs_find(&self, target: CrateId, from: CrateId) -> bool { for dep in self.dependencies(from) { let crate_id = dep.crate_id(); if crate_id == target { return true; } if self.arena.contains_key(&crate_id) { - if self.dfs(target, crate_id) { + if self.dfs_find(target, crate_id) { return true; } } -- cgit v1.2.3 From 66d15bb2dafefe74c34e636ceb242f056f7b43dc Mon Sep 17 00:00:00 2001 From: gfreezy Date: Fri, 21 Dec 2018 22:45:38 +0800 Subject: add #[cfg(test)] --- crates/ra_db/src/input.rs | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'crates') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index f6d11844a..ee4de6fa9 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -132,7 +132,8 @@ impl CrateGraph { } -mod test { +#[cfg(test)] +mod tests { use super::{CrateGraph, FxHashMap, FileId, SmolStr}; #[test] #[should_panic] -- cgit v1.2.3 From 0267df38156d5d67f0b636913a3fe54d84d906ab Mon Sep 17 00:00:00 2001 From: gfreezy Date: Sat, 22 Dec 2018 15:30:58 +0800 Subject: not visit the same crateId only once --- crates/ra_db/src/input.rs | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-) (limited to 'crates') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index ee4de6fa9..e9a991a57 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -12,6 +12,7 @@ use rustc_hash::FxHashMap; use salsa; use ra_syntax::SmolStr; +use rustc_hash::FxHashSet; /// `FileId` is an integer which uniquely identifies a file. File paths are /// messy and system-dependent, so most of the code should work directly with @@ -94,8 +95,9 @@ impl CrateGraph { crate_id } pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { - if self.dfs_find(from, to) { - panic!("Cycle dependencies found.") + let mut visited = FxHashSet::default(); + if self.dfs_find(from, to, &mut visited) { + panic!("Cycle dependencies found.") } self.arena.get_mut(&from).unwrap().add_dep(name, to) } @@ -112,35 +114,36 @@ impl CrateGraph { pub fn dependencies<'a>( &'a self, crate_id: CrateId, - ) -> impl Iterator + 'a { + ) -> impl Iterator + 'a { self.arena[&crate_id].dependencies.iter() } - fn dfs_find(&self, target: CrateId, from: CrateId) -> bool { + fn dfs_find(&self, target: CrateId, from: CrateId, visited: &mut FxHashSet) -> bool { + if visited.contains(&from) { + return false; + } for dep in self.dependencies(from) { let crate_id = dep.crate_id(); if crate_id == target { return true; } - if self.arena.contains_key(&crate_id) { - if self.dfs_find(target, crate_id) { - return true; - } + + if self.dfs_find(target, crate_id, visited) { + return true; } } + visited.insert(from); return false; } } - #[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 { - arena: FxHashMap::default() - }; + 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)); @@ -152,7 +155,7 @@ mod tests { #[test] fn it_works() { let mut graph = CrateGraph { - arena: FxHashMap::default() + arena: FxHashMap::default(), }; let crate1 = graph.add_crate_root(FileId(1u32)); let crate2 = graph.add_crate_root(FileId(2u32)); @@ -162,7 +165,6 @@ mod tests { } } - salsa::query_group! { pub trait FilesDatabase: salsa::Database { /// Text of the file. -- cgit v1.2.3 From c0add813e9005a3356c7a8062c9a9c8f8bca6895 Mon Sep 17 00:00:00 2001 From: gfreezy Date: Sat, 22 Dec 2018 22:40:41 +0800 Subject: mark as visited on entry instead of left --- crates/ra_db/src/input.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'crates') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index e9a991a57..f445e03bc 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -118,9 +118,10 @@ impl CrateGraph { self.arena[&crate_id].dependencies.iter() } fn dfs_find(&self, target: CrateId, from: CrateId, visited: &mut FxHashSet) -> bool { - if visited.contains(&from) { + if !visited.insert(from) { return false; } + for dep in self.dependencies(from) { let crate_id = dep.crate_id(); if crate_id == target { @@ -131,7 +132,6 @@ impl CrateGraph { return true; } } - visited.insert(from); return false; } } -- cgit v1.2.3