aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_db/src
diff options
context:
space:
mode:
authorAleksey Kladov <[email protected]>2019-01-13 09:27:26 +0000
committerAleksey Kladov <[email protected]>2019-01-13 10:39:48 +0000
commit77f67ca7e2caac6d94215834981ae3f6fb908443 (patch)
tree6047b4e5101e39af9837f2e3192c4e29d94b7b96 /crates/ra_db/src
parent40686722ba0762c4af396da120331710edfeabe8 (diff)
gracefully handle cycles in crate graph
rust-lang/rust has absolutely weird setup with rustc-workspace-shim, which leads to real cycles.
Diffstat (limited to 'crates/ra_db/src')
-rw-r--r--crates/ra_db/src/input.rs82
1 files changed, 48 insertions, 34 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 {
53 arena: FxHashMap<CrateId, CrateData>, 53 arena: FxHashMap<CrateId, CrateData>,
54} 54}
55 55
56#[derive(Debug)]
57pub struct CyclicDependencies;
58
56#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] 59#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
57pub struct CrateId(pub u32); 60pub struct CrateId(pub u32);
58 61
@@ -94,12 +97,16 @@ impl CrateGraph {
94 assert!(prev.is_none()); 97 assert!(prev.is_none());
95 crate_id 98 crate_id
96 } 99 }
97 pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { 100 pub fn add_dep(
98 let mut visited = FxHashSet::default(); 101 &mut self,
99 if self.dfs_find(from, to, &mut visited) { 102 from: CrateId,
100 panic!("Cycle dependencies found.") 103 name: SmolStr,
104 to: CrateId,
105 ) -> Result<(), CyclicDependencies> {
106 if self.dfs_find(from, to, &mut FxHashSet::default()) {
107 return Err(CyclicDependencies);
101 } 108 }
102 self.arena.get_mut(&from).unwrap().add_dep(name, to) 109 Ok(self.arena.get_mut(&from).unwrap().add_dep(name, to))
103 } 110 }
104 pub fn is_empty(&self) -> bool { 111 pub fn is_empty(&self) -> bool {
105 self.arena.is_empty() 112 self.arena.is_empty()
@@ -139,35 +146,6 @@ impl CrateGraph {
139 } 146 }
140} 147}
141 148
142#[cfg(test)]
143mod tests {
144 use super::{CrateGraph, FxHashMap, FileId, SmolStr};
145
146 #[test]
147 #[should_panic]
148 fn it_should_painc_because_of_cycle_dependencies() {
149 let mut graph = CrateGraph::default();
150 let crate1 = graph.add_crate_root(FileId(1u32));
151 let crate2 = graph.add_crate_root(FileId(2u32));
152 let crate3 = graph.add_crate_root(FileId(3u32));
153 graph.add_dep(crate1, SmolStr::new("crate2"), crate2);
154 graph.add_dep(crate2, SmolStr::new("crate3"), crate3);
155 graph.add_dep(crate3, SmolStr::new("crate1"), crate1);
156 }
157
158 #[test]
159 fn it_works() {
160 let mut graph = CrateGraph {
161 arena: FxHashMap::default(),
162 };
163 let crate1 = graph.add_crate_root(FileId(1u32));
164 let crate2 = graph.add_crate_root(FileId(2u32));
165 let crate3 = graph.add_crate_root(FileId(3u32));
166 graph.add_dep(crate1, SmolStr::new("crate2"), crate2);
167 graph.add_dep(crate2, SmolStr::new("crate3"), crate3);
168 }
169}
170
171salsa::query_group! { 149salsa::query_group! {
172 pub trait FilesDatabase: salsa::Database { 150 pub trait FilesDatabase: salsa::Database {
173 /// Text of the file. 151 /// Text of the file.
@@ -209,3 +187,39 @@ salsa::query_group! {
209 } 187 }
210 } 188 }
211} 189}
190
191#[cfg(test)]
192mod tests {
193 use super::{CrateGraph, FileId, SmolStr};
194
195 #[test]
196 fn it_should_painc_because_of_cycle_dependencies() {
197 let mut graph = CrateGraph::default();
198 let crate1 = graph.add_crate_root(FileId(1u32));
199 let crate2 = graph.add_crate_root(FileId(2u32));
200 let crate3 = graph.add_crate_root(FileId(3u32));
201 assert!(graph
202 .add_dep(crate1, SmolStr::new("crate2"), crate2)
203 .is_ok());
204 assert!(graph
205 .add_dep(crate2, SmolStr::new("crate3"), crate3)
206 .is_ok());
207 assert!(graph
208 .add_dep(crate3, SmolStr::new("crate1"), crate1)
209 .is_err());
210 }
211
212 #[test]
213 fn it_works() {
214 let mut graph = CrateGraph::default();
215 let crate1 = graph.add_crate_root(FileId(1u32));
216 let crate2 = graph.add_crate_root(FileId(2u32));
217 let crate3 = graph.add_crate_root(FileId(3u32));
218 assert!(graph
219 .add_dep(crate1, SmolStr::new("crate2"), crate2)
220 .is_ok());
221 assert!(graph
222 .add_dep(crate2, SmolStr::new("crate3"), crate3)
223 .is_ok());
224 }
225}