gracefully handle cycles in crate graph

rust-lang/rust has absolutely weird setup with rustc-workspace-shim,
which leads to real cycles.

3 files changed, 78 insertions, 41 deletions

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<CrateId, CrateData>,
 }
 
+#[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());
+    }
+}
diff --git a/crates/ra_hir/src/nameres/tests.rs b/crates/ra_hir/src/nameres/tests.rs
index ba9fcb3d1..647fd92aa 100644
--- a/crates/ra_hir/src/nameres/tests.rs
+++ b/crates/ra_hir/src/nameres/tests.rs
@@ -235,7 +235,9 @@ fn item_map_across_crates() {
     let mut crate_graph = CrateGraph::default();
     let main_crate = crate_graph.add_crate_root(main_id);
     let lib_crate = crate_graph.add_crate_root(lib_id);
-    crate_graph.add_dep(main_crate, "test_crate".into(), lib_crate);
+    crate_graph
+        .add_dep(main_crate, "test_crate".into(), lib_crate)
+        .unwrap();
 
     db.set_crate_graph(crate_graph);
 
@@ -288,7 +290,9 @@ fn import_across_source_roots() {
     let mut crate_graph = CrateGraph::default();
     let main_crate = crate_graph.add_crate_root(main_id);
     let lib_crate = crate_graph.add_crate_root(lib_id);
-    crate_graph.add_dep(main_crate, "test_crate".into(), lib_crate);
+    crate_graph
+        .add_dep(main_crate, "test_crate".into(), lib_crate)
+        .unwrap();
 
     db.set_crate_graph(crate_graph);
 
@@ -330,7 +334,9 @@ fn reexport_across_crates() {
     let mut crate_graph = CrateGraph::default();
     let main_crate = crate_graph.add_crate_root(main_id);
     let lib_crate = crate_graph.add_crate_root(lib_id);
-    crate_graph.add_dep(main_crate, "test_crate".into(), lib_crate);
+    crate_graph
+        .add_dep(main_crate, "test_crate".into(), lib_crate)
+        .unwrap();
 
     db.set_crate_graph(crate_graph);
 
diff --git a/crates/ra_lsp_server/src/server_world.rs b/crates/ra_lsp_server/src/server_world.rs
index 4f3c231d3..d5dbf999f 100644
--- a/crates/ra_lsp_server/src/server_world.rs
+++ b/crates/ra_lsp_server/src/server_world.rs
@@ -73,7 +73,9 @@ impl ServerWorldState {
                     if let (Some(&from), Some(&to)) =
                         (sysroot_crates.get(&from), sysroot_crates.get(&to))
                     {
-                        crate_graph.add_dep(from, name.clone(), to);
+                        if let Err(_) = crate_graph.add_dep(from, name.clone(), to) {
+                            log::error!("cyclic dependency between sysroot crates")
+                        }
                     }
                 }
             }
@@ -108,11 +110,20 @@ impl ServerWorldState {
                 for &from in pkg_crates.get(&pkg).into_iter().flatten() {
                     if let Some(to) = lib_tgt {
                         if to != from {
-                            crate_graph.add_dep(from, pkg.name(&ws.cargo).into(), to);
+                            if let Err(_) =
+                                crate_graph.add_dep(from, pkg.name(&ws.cargo).into(), to)
+                            {
+                                log::error!(
+                                    "cyclic dependency between targets of {}",
+                                    pkg.name(&ws.cargo)
+                                )
+                            }
                         }
                     }
                     if let Some(std) = libstd {
-                        crate_graph.add_dep(from, "std".into(), std);
+                        if let Err(_) = crate_graph.add_dep(from, "std".into(), std) {
+                            log::error!("cyclic dependency on std for {}", pkg.name(&ws.cargo))
+                        }
                     }
                 }
             }
@@ -123,7 +134,13 @@ impl ServerWorldState {
                 for dep in pkg.dependencies(&ws.cargo) {
                     if let Some(&to) = pkg_to_lib_crate.get(&dep.pkg) {
                         for &from in pkg_crates.get(&pkg).into_iter().flatten() {
-                            crate_graph.add_dep(from, dep.name.clone(), to);
+                            if let Err(_) = crate_graph.add_dep(from, dep.name.clone(), to) {
+                                log::error!(
+                                    "cyclic dependency {} -> {}",
+                                    pkg.name(&ws.cargo),
+                                    dep.pkg.name(&ws.cargo)
+                                )
+                            }
                         }
                     }
                 }