nandi.uk
Fork of daniellemaywood.uk/gleam — Wasm codegen work
5.0 kB
174 lines
1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2020 The Gleam contributors
3
4use ecow::EcoString;
5use petgraph::{Direction, algo::Cycle, graph::NodeIndex};
6use std::collections::{HashMap, HashSet};
7
8#[cfg(test)]
9use pretty_assertions::assert_eq;
10
11/// Take a sequence of values and their deps, and return the values in
12/// order so that deps come before the dependents.
13///
14/// Any deps that are not nodes are ignored and presumed to be nodes
15/// that do not need processing.
16///
17/// Errors if there are duplicate values, unknown deps, or cycles.
18///
19pub fn toposort_deps(inputs: Vec<(EcoString, Vec<EcoString>)>) -> Result<Vec<EcoString>, Error> {
20 let mut graph = petgraph::Graph::<(), ()>::with_capacity(inputs.len(), inputs.len() * 5);
21 let mut values = HashMap::with_capacity(inputs.len());
22 let mut indexes = HashMap::with_capacity(inputs.len());
23
24 for (value, _deps) in &inputs {
25 let index = graph.add_node(());
26 let _ = indexes.insert(value.clone(), index);
27 let _ = values.insert(index, value.clone());
28 }
29
30 for (value, deps) in inputs {
31 let &from_index = indexes.get(&value).expect("Finding index for value");
32 for &to_index in deps.into_iter().filter_map(|dep| indexes.get(&dep)) {
33 let _ = graph.add_edge(from_index, to_index, ());
34 }
35 }
36
37 match petgraph::algo::toposort(&graph, None) {
38 Err(e) => Err(Error::Cycle(import_cycle(e, &graph, values))),
39
40 Ok(seq) => Ok(seq
41 .into_iter()
42 .map(|i| values.remove(&i).expect("Finding value for index"))
43 .rev()
44 .collect()),
45 }
46}
47
48fn import_cycle(
49 cycle: Cycle<NodeIndex>,
50 graph: &petgraph::Graph<(), ()>,
51 mut values: HashMap<NodeIndex, EcoString>,
52) -> Vec<EcoString> {
53 let origin = cycle.node_id();
54 let mut path = vec![];
55 let _ = find_cycle(origin, origin, graph, &mut path, &mut HashSet::new());
56 path.iter()
57 .map(|index| {
58 values
59 .remove(index)
60 .expect("dep_tree::import_cycle(): cannot find values for index")
61 })
62 .collect()
63}
64
65fn find_cycle(
66 origin: NodeIndex,
67 parent: NodeIndex,
68 graph: &petgraph::Graph<(), ()>,
69 path: &mut Vec<NodeIndex>,
70 seen: &mut HashSet<NodeIndex>,
71) -> bool {
72 let _ = seen.insert(parent);
73 for node in graph.neighbors_directed(parent, Direction::Outgoing) {
74 if node == origin {
75 path.push(node);
76 return true;
77 }
78 if seen.contains(&node) {
79 continue;
80 }
81 if find_cycle(origin, node, graph, path, seen) {
82 path.push(node);
83 return true;
84 }
85 }
86 false
87}
88
89#[derive(Debug, PartialEq)]
90pub enum Error {
91 Cycle(Vec<EcoString>),
92}
93
94#[cfg(test)]
95mod tests {
96 use super::{assert_eq, *};
97
98 #[test]
99 fn toposort_deps_test() {
100 // All deps are nodes
101 assert_eq!(
102 toposort_deps(vec![
103 ("a".into(), vec!["b".into()]),
104 ("c".into(), vec![]),
105 ("b".into(), vec!["c".into()])
106 ]),
107 Ok(vec!["c".into(), "b".into(), "a".into()])
108 );
109
110 // No deps
111 assert_eq!(
112 toposort_deps(vec![
113 ("no-deps-1".into(), vec![]),
114 ("no-deps-2".into(), vec![])
115 ]),
116 Ok(vec!["no-deps-1".into(), "no-deps-2".into(),])
117 );
118
119 // Some deps are not nodes (and thus are ignored)
120 assert_eq!(
121 toposort_deps(vec![
122 ("a".into(), vec!["b".into(), "z".into()]),
123 ("b".into(), vec!["x".into()])
124 ]),
125 Ok(vec!["b".into(), "a".into()])
126 );
127 }
128
129 #[test]
130 fn cycle_detection() {
131 // a ---+
132 // ^ |
133 // | v
134 // +----+
135 assert_eq!(
136 toposort_deps(vec![("a".into(), vec!["a".into()])]),
137 Err(Error::Cycle(vec!["a".into()]))
138 );
139
140 // a -> b -> c
141 // ^ v
142 // | |
143 // +---------+
144 assert_eq!(
145 toposort_deps(vec![
146 ("a".into(), vec!["b".into()]),
147 ("b".into(), vec!["c".into()]),
148 ("c".into(), vec!["a".into()]),
149 ]),
150 Err(Error::Cycle(vec!["c".into(), "b".into(), "a".into()]))
151 );
152
153 // a -> b <- e
154 // | | ^
155 // v v |
156 // f c -> d
157 assert_eq!(
158 toposort_deps(vec![
159 ("a".into(), vec!["b".into()]),
160 ("b".into(), vec!["c".into()]),
161 ("c".into(), vec!["d".into()]),
162 ("d".into(), vec!["e".into()]),
163 ("e".into(), vec!["b".into()]),
164 ("a".into(), vec!["f".into()]),
165 ]),
166 Err(Error::Cycle(vec![
167 "e".into(),
168 "d".into(),
169 "c".into(),
170 "b".into(),
171 ]))
172 );
173 }
174}