| 144 | } |
| 145 | |
| 146 | fn has_cycle(r: &Trace) -> bool { |
| 147 | use std::collections::HashSet; |
| 148 | fn dfs( |
| 149 | node: &str, |
| 150 | trace: &Trace, |
| 151 | visited: &mut HashSet<String>, |
| 152 | stack: &mut HashSet<String>, |
| 153 | ) -> bool { |
| 154 | if stack.contains(node) { |
| 155 | return true; |
| 156 | } |
| 157 | if visited.contains(node) { |
| 158 | return false; |
| 159 | } |
| 160 | visited.insert(node.to_string()); |
| 161 | stack.insert(node.to_string()); |
| 162 | if let Some(s) = trace.steps.get(node) { |
| 163 | for dep in &s.from_steps { |
| 164 | if dfs(dep, trace, visited, stack) { |
| 165 | return true; |
| 166 | } |
| 167 | } |
| 168 | } |
| 169 | stack.remove(node); |
| 170 | false |
| 171 | } |
| 172 | let mut visited = HashSet::new(); |
| 173 | let mut stack = HashSet::new(); |
| 174 | for step_id in r.steps.keys() { |
| 175 | if dfs(step_id, r, &mut visited, &mut stack) { |
| 176 | return true; |
| 177 | } |
| 178 | } |
| 179 | false |
| 180 | } |
| 181 | |
| 182 | #[cfg(test)] |
| 183 | mod tests { |