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