aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_db/src
diff options
context:
space:
mode:
authorgfreezy <[email protected]>2018-12-22 07:30:58 +0000
committergfreezy <[email protected]>2018-12-22 07:30:58 +0000
commit0267df38156d5d67f0b636913a3fe54d84d906ab (patch)
treed7014b75e003366a7c99e8c9927e31a0b86ee5ad /crates/ra_db/src
parent66d15bb2dafefe74c34e636ceb242f056f7b43dc (diff)
not visit the same crateId only once
Diffstat (limited to 'crates/ra_db/src')
-rw-r--r--crates/ra_db/src/input.rs30
1 files changed, 16 insertions, 14 deletions
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;
12use salsa; 12use salsa;
13 13
14use ra_syntax::SmolStr; 14use ra_syntax::SmolStr;
15use rustc_hash::FxHashSet;
15 16
16/// `FileId` is an integer which uniquely identifies a file. File paths are 17/// `FileId` is an integer which uniquely identifies a file. File paths are
17/// messy and system-dependent, so most of the code should work directly with 18/// messy and system-dependent, so most of the code should work directly with
@@ -94,8 +95,9 @@ impl CrateGraph {
94 crate_id 95 crate_id
95 } 96 }
96 pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) { 97 pub fn add_dep(&mut self, from: CrateId, name: SmolStr, to: CrateId) {
97 if self.dfs_find(from, to) { 98 let mut visited = FxHashSet::default();
98 panic!("Cycle dependencies found.") 99 if self.dfs_find(from, to, &mut visited) {
100 panic!("Cycle dependencies found.")
99 } 101 }
100 self.arena.get_mut(&from).unwrap().add_dep(name, to) 102 self.arena.get_mut(&from).unwrap().add_dep(name, to)
101 } 103 }
@@ -112,35 +114,36 @@ impl CrateGraph {
112 pub fn dependencies<'a>( 114 pub fn dependencies<'a>(
113 &'a self, 115 &'a self,
114 crate_id: CrateId, 116 crate_id: CrateId,
115 ) -> impl Iterator<Item=&'a Dependency> + 'a { 117 ) -> impl Iterator<Item = &'a Dependency> + 'a {
116 self.arena[&crate_id].dependencies.iter() 118 self.arena[&crate_id].dependencies.iter()
117 } 119 }
118 fn dfs_find(&self, target: CrateId, from: CrateId) -> bool { 120 fn dfs_find(&self, target: CrateId, from: CrateId, visited: &mut FxHashSet<CrateId>) -> bool {
121 if visited.contains(&from) {
122 return false;
123 }
119 for dep in self.dependencies(from) { 124 for dep in self.dependencies(from) {
120 let crate_id = dep.crate_id(); 125 let crate_id = dep.crate_id();
121 if crate_id == target { 126 if crate_id == target {
122 return true; 127 return true;
123 } 128 }
124 if self.arena.contains_key(&crate_id) { 129
125 if self.dfs_find(target, crate_id) { 130 if self.dfs_find(target, crate_id, visited) {
126 return true; 131 return true;
127 }
128 } 132 }
129 } 133 }
134 visited.insert(from);
130 return false; 135 return false;
131 } 136 }
132} 137}
133 138
134
135#[cfg(test)] 139#[cfg(test)]
136mod tests { 140mod tests {
137 use super::{CrateGraph, FxHashMap, FileId, SmolStr}; 141 use super::{CrateGraph, FxHashMap, FileId, SmolStr};
142
138 #[test] 143 #[test]
139 #[should_panic] 144 #[should_panic]
140 fn it_should_painc_because_of_cycle_dependencies() { 145 fn it_should_painc_because_of_cycle_dependencies() {
141 let mut graph = CrateGraph { 146 let mut graph = CrateGraph::default();
142 arena: FxHashMap::default()
143 };
144 let crate1 = graph.add_crate_root(FileId(1u32)); 147 let crate1 = graph.add_crate_root(FileId(1u32));
145 let crate2 = graph.add_crate_root(FileId(2u32)); 148 let crate2 = graph.add_crate_root(FileId(2u32));
146 let crate3 = graph.add_crate_root(FileId(3u32)); 149 let crate3 = graph.add_crate_root(FileId(3u32));
@@ -152,7 +155,7 @@ mod tests {
152 #[test] 155 #[test]
153 fn it_works() { 156 fn it_works() {
154 let mut graph = CrateGraph { 157 let mut graph = CrateGraph {
155 arena: FxHashMap::default() 158 arena: FxHashMap::default(),
156 }; 159 };
157 let crate1 = graph.add_crate_root(FileId(1u32)); 160 let crate1 = graph.add_crate_root(FileId(1u32));
158 let crate2 = graph.add_crate_root(FileId(2u32)); 161 let crate2 = graph.add_crate_root(FileId(2u32));
@@ -162,7 +165,6 @@ mod tests {
162 } 165 }
163} 166}
164 167
165
166salsa::query_group! { 168salsa::query_group! {
167 pub trait FilesDatabase: salsa::Database { 169 pub trait FilesDatabase: salsa::Database {
168 /// Text of the file. 170 /// Text of the file.