turtle_build/
module_dependency.rs

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

turtle_build/
module_dependency.rs
