diff options
author | gfreezy <[email protected]> | 2018-12-21 14:27:04 +0000 |
---|---|---|
committer | gfreezy <[email protected]> | 2018-12-21 14:27:04 +0000 |
commit | 792dabc0a6a198d0fdeb6449b457a4e61009178e (patch) | |
tree | e706fdada931060f8541fa2c2cdb8838d15c1b29 | |
parent | 463e5af3f2ff54b74e4aeb73e75047c00b6339be (diff) |
When constructing a crate graph, detect and forbid cycles.
fixed #300
-rw-r--r-- | crates/ra_db/src/input.rs | 58 |
1 files changed, 52 insertions, 6 deletions
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 @@ | |||
7 | /// actual IO is done and lowered to input. | 7 | /// actual IO is done and lowered to input. |
8 | use std::sync::Arc; | 8 | use std::sync::Arc; |
9 | 9 | ||
10 | use rustc_hash::{FxHashMap}; | ||
11 | use relative_path::RelativePathBuf; | 10 | use relative_path::RelativePathBuf; |
12 | use ra_syntax::SmolStr; | 11 | use rustc_hash::FxHashMap; |
13 | use salsa; | 12 | use salsa; |
14 | 13 | ||
14 | use ra_syntax::SmolStr; | ||
15 | |||
15 | /// `FileId` is an integer which uniquely identifies a file. File paths are | 16 | /// `FileId` is an integer which uniquely identifies a file. File paths are |
16 | /// messy and system-dependent, so most of the code should work directly with | 17 | /// messy and system-dependent, so most of the code should work directly with |
17 | /// `FileId`, without inspecting the path. The mapping between `FileId` and path | 18 | /// `FileId`, without inspecting the path. The mapping between `FileId` and path |
@@ -92,10 +93,10 @@ impl CrateGraph { | |||
92 | assert!(prev.is_none()); | 93 | assert!(prev.is_none()); |
93 | crate_id | 94 | crate_id |
94 | } | 95 | } |
95 | // FIXME: check that we don't have cycles here. | ||
96 | // Just a simple depth first search from `to` should work, | ||
97 | // the graph is small. | ||
98 | pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { | 96 | pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { |
97 | if self.dfs(from, to) { | ||
98 | panic!("Cycle dependencies found.") | ||
99 | } | ||
99 | self.arena.get_mut(&from).unwrap().add_dep(name, to) | 100 | self.arena.get_mut(&from).unwrap().add_dep(name, to) |
100 | } | 101 | } |
101 | pub fn crate_root(&self, crate_id: CrateId) -> FileId { | 102 | pub fn crate_root(&self, crate_id: CrateId) -> FileId { |
@@ -111,11 +112,56 @@ impl CrateGraph { | |||
111 | pub fn dependencies<'a>( | 112 | pub fn dependencies<'a>( |
112 | &'a self, | 113 | &'a self, |
113 | crate_id: CrateId, | 114 | crate_id: CrateId, |
114 | ) -> impl Iterator<Item = &'a Dependency> + 'a { | 115 | ) -> impl Iterator<Item=&'a Dependency> + 'a { |
115 | self.arena[&crate_id].dependencies.iter() | 116 | self.arena[&crate_id].dependencies.iter() |
116 | } | 117 | } |
118 | fn dfs(&self, target: CrateId, from: CrateId) -> bool { | ||
119 | for dep in self.dependencies(from) { | ||
120 | let crate_id = dep.crate_id(); | ||
121 | if crate_id == target { | ||
122 | return true; | ||
123 | } | ||
124 | if self.arena.contains_key(&crate_id) { | ||
125 | if self.dfs(target, crate_id) { | ||
126 | return true; | ||
127 | } | ||
128 | } | ||
129 | } | ||
130 | return false; | ||
131 | } | ||
117 | } | 132 | } |
118 | 133 | ||
134 | |||
135 | mod test { | ||
136 | use super::{CrateGraph, FxHashMap, FileId, SmolStr}; | ||
137 | #[test] | ||
138 | #[should_panic] | ||
139 | fn it_should_painc_because_of_cycle_dependencies() { | ||
140 | let mut graph = CrateGraph { | ||
141 | arena: FxHashMap::default() | ||
142 | }; | ||
143 | let crate1 = graph.add_crate_root(FileId(1u32)); | ||
144 | let crate2 = graph.add_crate_root(FileId(2u32)); | ||
145 | let crate3 = graph.add_crate_root(FileId(3u32)); | ||
146 | graph.add_dep(crate1, SmolStr::new("crate2"), crate2); | ||
147 | graph.add_dep(crate2, SmolStr::new("crate3"), crate3); | ||
148 | graph.add_dep(crate3, SmolStr::new("crate1"), crate1); | ||
149 | } | ||
150 | |||
151 | #[test] | ||
152 | fn it_works() { | ||
153 | let mut graph = CrateGraph { | ||
154 | arena: FxHashMap::default() | ||
155 | }; | ||
156 | let crate1 = graph.add_crate_root(FileId(1u32)); | ||
157 | let crate2 = graph.add_crate_root(FileId(2u32)); | ||
158 | let crate3 = graph.add_crate_root(FileId(3u32)); | ||
159 | graph.add_dep(crate1, SmolStr::new("crate2"), crate2); | ||
160 | graph.add_dep(crate2, SmolStr::new("crate3"), crate3); | ||
161 | } | ||
162 | } | ||
163 | |||
164 | |||
119 | salsa::query_group! { | 165 | salsa::query_group! { |
120 | pub trait FilesDatabase: salsa::Database { | 166 | pub trait FilesDatabase: salsa::Database { |
121 | /// Text of the file. | 167 | /// Text of the file. |