turtle_build/
module_dependency.rs

1use petgraph::{Graph, algo::is_cyclic_directed};
2use std::{
3    collections::HashMap,
4    path::{Path, PathBuf},
5};
6use thiserror::Error;
7
8/// A module dependency map.
9pub type ModuleDependencyMap = HashMap<PathBuf, HashMap<String, PathBuf>>;
10
11/// Validates module dependencies.
12pub fn validate_modules(modules: &ModuleDependencyMap) -> Result<(), ModuleDependencyError> {
13    if is_module_dependency_circular(modules) {
14        return Err(ModuleDependencyError::CircularDependency);
15    }
16
17    Ok(())
18}
19
20fn is_module_dependency_circular(modules: &ModuleDependencyMap) -> bool {
21    let mut graph = Graph::<&Path, ()>::new();
22    let mut indices = HashMap::<&Path, _>::new();
23
24    for output in modules.keys() {
25        indices.insert(output, graph.add_node(output));
26    }
27
28    for (output, build) in modules {
29        for input in build.values() {
30            graph.add_edge(indices[output.as_path()], indices[input.as_path()], ());
31        }
32    }
33
34    is_cyclic_directed(&graph)
35}
36
37#[derive(Clone, Debug, Eq, Error, PartialEq)]
38pub enum ModuleDependencyError {
39    #[error("build file dependency cycle detected")]
40    CircularDependency,
41}
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn validate_empty() {
49        assert_eq!(validate_modules(&Default::default()), Ok(()));
50    }
51
52    #[test]
53    fn validate_module() {
54        assert_eq!(
55            validate_modules(&[("foo".into(), Default::default())].into_iter().collect()),
56            Ok(())
57        );
58    }
59
60    #[test]
61    fn validate_circular_module() {
62        assert_eq!(
63            validate_modules(
64                &[(
65                    "foo".into(),
66                    [("foo".into(), "foo".into())].into_iter().collect()
67                )]
68                .into_iter()
69                .collect()
70            ),
71            Err(ModuleDependencyError::CircularDependency)
72        );
73    }
74
75    #[test]
76    fn validate_two_modules() {
77        assert_eq!(
78            validate_modules(
79                &[
80                    (
81                        "foo".into(),
82                        [("bar".into(), "bar".into())].into_iter().collect()
83                    ),
84                    ("bar".into(), Default::default(),)
85                ]
86                .into_iter()
87                .collect()
88            ),
89            Ok(())
90        );
91    }
92
93    #[test]
94    fn validate_two_circular_modules() {
95        assert_eq!(
96            validate_modules(
97                &[
98                    (
99                        "foo".into(),
100                        [("bar".into(), "bar".into())].into_iter().collect()
101                    ),
102                    (
103                        "bar".into(),
104                        [("foo".into(), "foo".into())].into_iter().collect()
105                    ),
106                ]
107                .into_iter()
108                .collect()
109            ),
110            Err(ModuleDependencyError::CircularDependency)
111        );
112    }
113}
turtle_build/module_dependency.rs

turtle_build/
module_dependency.rs
