1use anyhow::{Ok, Result};
46use petgraph::{
47 algo::is_cyclic_directed,
48 graph::{DiGraph, NodeIndex},
49 visit::{IntoNodeReferences, NodeIndexable},
50 Direction, Graph,
51};
52use std::collections::{HashMap, HashSet};
53
54pub struct DependenciesBuilder {
55 all_elements: Vec<String>,
56 all_dependencies: Vec<String>,
57 graph: DiGraph<String, ()>,
58 dependency_map: HashMap<String, (NodeIndex, Vec<String>)>,
59}
60
61impl DependenciesBuilder {
62 pub fn add_element(mut self, name: String, dependecies: Vec<String>) -> Self {
63 self.all_dependencies.extend(dependecies.clone());
64
65 if let Some((graph_node, _)) = self.dependency_map.get(&name) {
66 self.dependency_map
67 .insert(name, (graph_node.to_owned(), dependecies));
68 } else {
69 self.all_elements.push(name.clone());
70 let node = self.graph.add_node(name.clone());
71 self.dependency_map.insert(name, (node, dependecies));
72 }
73 self
74 }
75
76 fn add_edges(&mut self) {
77 for (node, dependencies) in self.dependency_map.values() {
78 for dependency in dependencies {
79 let dependency_node = self.dependency_map[dependency].0;
80 self.graph.add_edge(*node, dependency_node, ());
81 }
82 }
83 }
84
85 fn dependencies_are_met(&self) -> bool {
86 let elements_set: HashSet<_> = self.all_elements.iter().collect();
87 self.all_dependencies
88 .iter()
89 .all(|dependency| elements_set.contains(dependency))
90 }
91
92 fn no_cyclic_dependencies(&self) -> bool {
93 !is_cyclic_directed(&self.graph)
94 }
95
96 fn validate(&mut self) -> Result<()> {
97 if !self.dependencies_are_met() {
98 return Err(anyhow::anyhow!(
99 "Some dependencies do not exist as elements"
100 ));
101 }
102 self.add_edges();
103 if !self.no_cyclic_dependencies() {
104 return Err(anyhow::anyhow!("Cyclic dependency detected"));
105 }
106 self.graph.clear_edges();
107
108 Ok(())
109 }
110
111 pub fn build(&mut self) -> Result<Dependencies> {
112 self.validate()?;
113 self.add_edges();
114 Ok(Dependencies {
115 graph: self.graph.clone(),
116 })
117 }
118}
119
120#[derive(Debug)]
121pub struct Dependencies {
122 graph: DiGraph<String, ()>,
123}
124
125impl Dependencies {
126 fn find_node_by_name(graph: Graph<String, ()>, name: &str) -> Option<NodeIndex> {
127 for (node_index, node_name) in graph.node_references() {
128 if node_name == name {
129 return Some(node_index);
130 }
131 }
132 None
133 }
134
135 pub fn generate_tranches(&self) -> Result<Vec<Vec<String>>> {
136 let mut tranches: Vec<Vec<String>> = vec![];
137 let mut traverse_graph = self.graph.clone();
138 while traverse_graph.node_count() > 0 {
139 let mut node_to_remove: Vec<(NodeIndex, String)> = vec![];
140 let mut new_layer: Vec<String> = Vec::new();
141 for (node_index, node_name) in traverse_graph.node_references() {
142 if traverse_graph
143 .neighbors_directed(node_index, Direction::Outgoing)
144 .count()
145 == 0
146 {
147 node_to_remove.push((node_index, node_name.to_string()));
148 }
149 }
150 for (_, node_name) in node_to_remove {
151 let node_index =
152 Dependencies::find_node_by_name(traverse_graph.clone(), &node_name)
153 .ok_or(anyhow::anyhow!("Node not found"))?;
154 traverse_graph
155 .remove_node(traverse_graph.from_index(traverse_graph.to_index(node_index)));
156
157 new_layer.push(node_name.to_string())
158 }
159 tranches.push(new_layer);
160 }
161 Ok(tranches)
162 }
163
164 pub fn builder() -> DependenciesBuilder {
165 DependenciesBuilder {
166 all_elements: Vec::new(),
167 all_dependencies: Vec::new(),
168 graph: DiGraph::new(),
169 dependency_map: HashMap::new(),
170 }
171 }
172}
173
174#[cfg(test)]
175mod tests {
176 use super::Dependencies;
177
178 #[test]
179 fn can_validate_simple_tree() {
180 let mut dependencies_builder = Dependencies::builder()
181 .add_element("a".to_string(), vec!["b".to_string(), "c".to_string()])
182 .add_element("b".to_string(), vec!["c".to_string()])
183 .add_element("c".to_string(), vec![]);
184
185 assert!(dependencies_builder.build().is_ok());
186 }
187
188 #[test]
189 fn can_validate_complex_tree() {
190 let mut dependencies_builder = Dependencies::builder()
191 .add_element("a".to_string(), vec!["b".to_string(), "c".to_string()])
192 .add_element("b".to_string(), vec!["c".to_string()])
193 .add_element("c".to_string(), vec!["d".to_string(), "e".to_string()])
194 .add_element("d".to_string(), vec!["e".to_string()])
195 .add_element("e".to_string(), vec![]);
196
197 assert!(dependencies_builder.build().is_ok());
198 }
199
200 #[test]
201 fn detects_missing_dependencies() {
202 let mut dependencies_builder = Dependencies::builder()
203 .add_element("a".to_string(), vec!["b".to_string(), "c".to_string()])
204 .add_element("b".to_string(), vec!["c".to_string()]);
205
206 assert_eq!(
207 dependencies_builder.build().unwrap_err().to_string(),
208 "Some dependencies do not exist as elements"
209 );
210 }
211
212 #[test]
213 fn detects_cyclic_dependencies() {
214 let mut dependencies_builder = Dependencies::builder()
215 .add_element("a".to_string(), vec!["b".to_string(), "c".to_string()])
216 .add_element("b".to_string(), vec!["c".to_string()])
217 .add_element("c".to_string(), vec!["a".to_string(), "b".to_string()]);
218
219 assert_eq!(
220 dependencies_builder.build().unwrap_err().to_string(),
221 "Cyclic dependency detected"
222 );
223 }
224
225 #[test]
226 fn can_divide_into_tranches() {
227 let mut dependencies_builder = Dependencies::builder()
228 .add_element("b".to_string(), vec!["d".to_string()])
229 .add_element("c".to_string(), vec!["d".to_string()])
230 .add_element(
231 "a".to_string(),
232 vec!["d".to_string(), "e".to_string(), "y".to_string()],
233 )
234 .add_element("d".to_string(), vec!["e".to_string()])
235 .add_element("e".to_string(), vec![])
236 .add_element("y".to_string(), vec![]);
237
238 let dependencies = dependencies_builder.build().unwrap();
239
240 insta::assert_debug_snapshot!(dependencies.generate_tranches().unwrap());
241 }
242
243 #[test]
244 fn can_update_dependecies_later() {
245 let mut dependencies_builder = Dependencies::builder()
246 .add_element("b".to_string(), vec!["d".to_string()])
247 .add_element("c".to_string(), vec!["d".to_string()])
248 .add_element(
249 "a".to_string(),
250 vec!["d".to_string(), "e".to_string(), "y".to_string()],
251 )
252 .add_element("d".to_string(), vec!["e".to_string()])
253 .add_element("e".to_string(), vec![])
254 .add_element("y".to_string(), vec![])
255 .add_element("e".to_string(), vec!["y".to_string()]);
256
257 let dependencies = dependencies_builder.build().unwrap();
258
259 insta::assert_debug_snapshot!(dependencies.generate_tranches().unwrap());
260 }
261
262 #[test]
263 fn dependecies_are_order_insensitive() {
264 let mut ordered_dependencies_builder = Dependencies::builder()
265 .add_element("machine1".to_string(), vec!["network1".to_string()])
266 .add_element(
267 "machine2".to_string(),
268 vec!["network1".to_string(), "network2".to_string()],
269 )
270 .add_element("machine3".to_string(), vec!["network2".to_string()])
271 .add_element("network1".to_string(), vec![])
272 .add_element("network2".to_string(), vec![]);
273
274 let ordered_dependecies = ordered_dependencies_builder.build().unwrap();
275
276 let mut dependencies_builder = Dependencies::builder()
277 .add_element("machine1".to_string(), vec!["network1".to_string()])
278 .add_element("network1".to_string(), vec![])
279 .add_element("network2".to_string(), vec![])
280 .add_element(
281 "machine2".to_string(),
282 vec!["network1".to_string(), "network2".to_string()],
283 )
284 .add_element("machine3".to_string(), vec!["network2".to_string()]);
285
286 let dependencies = dependencies_builder.build().unwrap();
287
288 println!("{:?}", ordered_dependecies.generate_tranches());
289 println!("{:?}", dependencies.generate_tranches());
290 assert_eq!(
291 ordered_dependecies.generate_tranches().unwrap().len(),
292 dependencies.generate_tranches().unwrap().len()
293 );
294 }
295}