xianyun_core/
toposort.rs

1//! Port of `internal/toposort`: orders the nodes of a directed acyclic graph
2//! so that every node follows the nodes it depends on, using Kahn's algorithm.
3
4use std::fmt::Debug;
5use std::hash::Hash;
6use thiserror::Error;
7
8#[derive(Debug, Error, PartialEq, Eq)]
9pub enum ToposortError<N: Debug> {
10    #[error("dependency cycle detected: {0:?}")]
11    Cycle(Vec<N>),
12}
13
14/// Orders `nodes` so that each follows the nodes `deps` says it depends on.
15/// The order among nodes the dependencies leave free is unspecified. A
16/// dependency outside the node set is ignored; a node depending on itself is
17/// a cycle.
18pub fn sort<N, F>(nodes: &[N], deps: F) -> Result<Vec<N>, ToposortError<N>>
19where
20    N: Clone + Eq + Hash + Debug,
21    F: Fn(&N) -> Vec<N>,
22{
23    if nodes.is_empty() {
24        return Ok(Vec::new());
25    }
26
27    let mut indegree: std::collections::HashMap<N, usize> =
28        nodes.iter().map(|n| (n.clone(), 0)).collect();
29    let mut dependents: std::collections::HashMap<N, Vec<N>> = std::collections::HashMap::new();
30
31    for n in nodes {
32        for d in deps(n) {
33            if !indegree.contains_key(&d) {
34                continue;
35            }
36            *indegree.get_mut(n).unwrap() += 1;
37            dependents.entry(d).or_default().push(n.clone());
38        }
39    }
40
41    let mut queue: std::collections::VecDeque<N> =
42        nodes.iter().filter(|n| indegree[n] == 0).cloned().collect();
43
44    let mut result = Vec::with_capacity(nodes.len());
45
46    while let Some(n) = queue.pop_front() {
47        result.push(n.clone());
48
49        if let Some(deps_of_n) = dependents.get(&n) {
50            for dependent in deps_of_n.clone() {
51                let entry = indegree.get_mut(&dependent).unwrap();
52                *entry -= 1;
53                if *entry == 0 {
54                    queue.push_back(dependent);
55                }
56            }
57        }
58    }
59
60    if result.len() != nodes.len() {
61        let cycle: Vec<N> = nodes.iter().filter(|n| indegree[n] > 0).cloned().collect();
62        return Err(ToposortError::Cycle(cycle));
63    }
64
65    Ok(result)
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71    use std::collections::HashMap;
72
73    // Port of TestSort.
74    #[test]
75    fn sort_fixed_order_cases() {
76        struct Case {
77            name: &'static str,
78            nodes: Vec<&'static str>,
79            deps: HashMap<&'static str, Vec<&'static str>>,
80            want: Vec<&'static str>,
81        }
82
83        let cases = vec![
84            Case {
85                name: "dependency comes first",
86                nodes: vec!["app", "db"],
87                deps: HashMap::from([("app", vec!["db"])]),
88                want: vec!["db", "app"],
89            },
90            Case {
91                name: "chain is ordered end to end",
92                nodes: vec!["c", "b", "a"],
93                deps: HashMap::from([("c", vec!["b"]), ("b", vec!["a"])]),
94                want: vec!["a", "b", "c"],
95            },
96            Case {
97                name: "dependency outside the node set is ignored",
98                nodes: vec!["a", "b"],
99                deps: HashMap::from([("a", vec!["elsewhere"]), ("b", vec!["a"])]),
100                want: vec!["a", "b"],
101            },
102        ];
103
104        for case in cases {
105            let got = sort(&case.nodes, |n| {
106                case.deps.get(n).cloned().unwrap_or_default()
107            })
108            .unwrap_or_else(|e| panic!("{}: {e}", case.name));
109            assert_eq!(got, case.want, "{}", case.name);
110        }
111    }
112
113    // Port of TestSort_IndependentNodesAllComeThrough.
114    #[test]
115    fn sort_independent_nodes_all_come_through() {
116        let nodes = vec!["c", "a", "b"];
117        let mut got = sort(&nodes, |_| Vec::new()).unwrap();
118        got.sort_unstable();
119        let mut want = nodes.clone();
120        want.sort_unstable();
121        assert_eq!(got, want);
122    }
123
124    // Port of TestSort_DiamondResolvesBranchesBeforeTip.
125    #[test]
126    fn sort_diamond_resolves_branches_before_tip() {
127        let nodes = vec!["tip", "left", "right", "base"];
128        let deps: HashMap<&str, Vec<&str>> = HashMap::from([
129            ("tip", vec!["left", "right"]),
130            ("left", vec!["base"]),
131            ("right", vec!["base"]),
132        ]);
133
134        let got = sort(&nodes, |n| deps.get(n).cloned().unwrap_or_default()).unwrap();
135        assert_eq!(got.len(), nodes.len());
136        assert_eq!(got[0], "base");
137        assert_eq!(got[3], "tip");
138        let mut middle = got[1..3].to_vec();
139        middle.sort_unstable();
140        assert_eq!(middle, vec!["left", "right"]);
141    }
142
143    // Port of TestSort_CycleNamesItsNodes.
144    #[test]
145    fn sort_cycle_names_its_nodes() {
146        let nodes = vec!["alpha", "beta", "gamma"];
147        let deps: HashMap<&str, Vec<&str>> =
148            HashMap::from([("alpha", vec!["beta"]), ("beta", vec!["alpha"])]);
149
150        let err = sort(&nodes, |n| deps.get(n).cloned().unwrap_or_default()).unwrap_err();
151        let msg = err.to_string();
152        assert!(msg.contains("alpha"));
153        assert!(msg.contains("beta"));
154        assert!(
155            !msg.contains("gamma"),
156            "a node outside the cycle is not blamed"
157        );
158    }
159
160    // Port of TestSort_SelfDependencyIsACycle.
161    #[test]
162    fn sort_self_dependency_is_a_cycle() {
163        let nodes = vec!["a"];
164        let err = sort(&nodes, |_| vec!["a"]).unwrap_err();
165        assert!(matches!(err, ToposortError::Cycle(_)));
166    }
167}
xianyun_core/toposort.rs

xianyun_core/
toposort.rs
