]>
Commit | Line | Data |
---|---|---|
6d0f4579 AC |
1 | //! A graph-like structure used to represent a set of dependencies and in what |
2 | //! order they should be built. | |
3 | //! | |
4 | //! This structure is used to store the dependency graph and dynamically update | |
5 | //! it to figure out when a dependency should be built. | |
127fdfeb AC |
6 | //! |
7 | //! Dependencies in this queue are represented as a (node, edge) pair. This is | |
8 | //! used to model nodes which produce multiple outputs at different times but | |
9 | //! some nodes may only require one of the outputs and can start before the | |
10 | //! whole node is finished. | |
6d0f4579 | 11 | |
9e779198 | 12 | use std::collections::{HashMap, HashSet}; |
2874b68e | 13 | use std::hash::Hash; |
6d0f4579 | 14 | |
659f8244 | 15 | #[derive(Debug)] |
127fdfeb | 16 | pub struct DependencyQueue<N: Hash + Eq, E: Hash + Eq, V> { |
2874b68e | 17 | /// A list of all known keys to build. |
6d0f4579 AC |
18 | /// |
19 | /// The value of the hash map is list of dependencies which still need to be | |
20 | /// built before the package can be built. Note that the set is dynamically | |
21 | /// updated as more dependencies are built. | |
127fdfeb | 22 | dep_map: HashMap<N, (HashSet<(N, E)>, V)>, |
6d0f4579 AC |
23 | |
24 | /// A reverse mapping of a package to all packages that depend on that | |
25 | /// package. | |
26 | /// | |
27 | /// This map is statically known and does not get updated throughout the | |
28 | /// lifecycle of the DependencyQueue. | |
127fdfeb AC |
29 | /// |
30 | /// This is sort of like a `HashMap<(N, E), HashSet<N>>` map, but more | |
31 | /// easily indexable with just an `N` | |
32 | reverse_dep_map: HashMap<N, HashMap<E, HashSet<N>>>, | |
e54b5f87 | 33 | |
dd5aca30 | 34 | /// The relative priority of this package. Higher values should be scheduled sooner. |
35853c13 | 35 | priority: HashMap<N, usize>, |
dd5aca30 JM |
36 | |
37 | /// An expected cost for building this package. Used to determine priority. | |
38 | cost: HashMap<N, usize>, | |
6d0f4579 AC |
39 | } |
40 | ||
127fdfeb AC |
41 | impl<N: Hash + Eq, E: Hash + Eq, V> Default for DependencyQueue<N, E, V> { |
42 | fn default() -> DependencyQueue<N, E, V> { | |
33bcccbb LL |
43 | DependencyQueue::new() |
44 | } | |
45 | } | |
46 | ||
127fdfeb | 47 | impl<N: Hash + Eq, E: Hash + Eq, V> DependencyQueue<N, E, V> { |
6d0f4579 | 48 | /// Creates a new dependency queue with 0 packages. |
127fdfeb | 49 | pub fn new() -> DependencyQueue<N, E, V> { |
6d0f4579 | 50 | DependencyQueue { |
2874b68e | 51 | dep_map: HashMap::new(), |
6d0f4579 | 52 | reverse_dep_map: HashMap::new(), |
35853c13 | 53 | priority: HashMap::new(), |
dd5aca30 | 54 | cost: HashMap::new(), |
6d0f4579 AC |
55 | } |
56 | } | |
127fdfeb | 57 | } |
6d0f4579 | 58 | |
0bce4003 | 59 | impl<N: Hash + Eq + Clone, E: Eq + Hash + Clone, V> DependencyQueue<N, E, V> { |
154bcf6d | 60 | /// Adds a new node and its dependencies to this queue. |
127fdfeb AC |
61 | /// |
62 | /// The `key` specified is a new node in the dependency graph, and the node | |
63 | /// depend on all the dependencies iterated by `dependencies`. Each | |
64 | /// dependency is a node/edge pair, where edges can be thought of as | |
65 | /// productions from nodes (aka if it's just `()` it's just waiting for the | |
66 | /// node to finish). | |
6d0f4579 | 67 | /// |
127fdfeb AC |
68 | /// An optional `value` can also be associated with `key` which is reclaimed |
69 | /// when the node is ready to go. | |
dd5aca30 JM |
70 | /// |
71 | /// The cost parameter can be used to hint at the relative cost of building | |
72 | /// this node. This implementation does not care about the units of this value, so | |
73 | /// the calling code is free to use whatever they'd like. In general, higher cost | |
74 | /// nodes are expected to take longer to build. | |
75 | pub fn queue( | |
76 | &mut self, | |
77 | key: N, | |
78 | value: V, | |
79 | dependencies: impl IntoIterator<Item = (N, E)>, | |
80 | cost: usize, | |
81 | ) { | |
127fdfeb | 82 | assert!(!self.dep_map.contains_key(&key)); |
5834a767 | 83 | |
6d0f4579 | 84 | let mut my_dependencies = HashSet::new(); |
127fdfeb AC |
85 | for (dep, edge) in dependencies { |
86 | my_dependencies.insert((dep.clone(), edge.clone())); | |
87 | self.reverse_dep_map | |
88 | .entry(dep) | |
89 | .or_insert_with(HashMap::new) | |
90 | .entry(edge) | |
91 | .or_insert_with(HashSet::new) | |
92 | .insert(key.clone()); | |
6d0f4579 | 93 | } |
dd5aca30 JM |
94 | self.dep_map.insert(key.clone(), (my_dependencies, value)); |
95 | self.cost.insert(key, cost); | |
6d0f4579 AC |
96 | } |
97 | ||
e54b5f87 AC |
98 | /// All nodes have been added, calculate some internal metadata and prepare |
99 | /// for `dequeue`. | |
100 | pub fn queue_finished(&mut self) { | |
35853c13 | 101 | let mut out = HashMap::new(); |
e54b5f87 | 102 | for key in self.dep_map.keys() { |
35853c13 | 103 | depth(key, &self.reverse_dep_map, &mut out); |
e54b5f87 | 104 | } |
dd5aca30 JM |
105 | self.priority = out |
106 | .into_iter() | |
107 | .map(|(n, set)| { | |
108 | let total_cost = | |
109 | self.cost[&n] + set.iter().map(|key| self.cost[key]).sum::<usize>(); | |
110 | (n, total_cost) | |
111 | }) | |
112 | .collect(); | |
e54b5f87 | 113 | |
dd5aca30 JM |
114 | /// Creates a flattened reverse dependency list. For a given key, finds the |
115 | /// set of nodes which depend on it, including transitively. This is different | |
116 | /// from self.reverse_dep_map because self.reverse_dep_map only maps one level | |
117 | /// of reverse dependencies. | |
384056e0 | 118 | fn depth<'a, N: Hash + Eq + Clone, E: Hash + Eq + Clone>( |
127fdfeb AC |
119 | key: &N, |
120 | map: &HashMap<N, HashMap<E, HashSet<N>>>, | |
384056e0 AC |
121 | results: &'a mut HashMap<N, HashSet<N>>, |
122 | ) -> &'a HashSet<N> { | |
123 | if results.contains_key(key) { | |
124 | let depth = &results[key]; | |
0bce4003 | 125 | assert!(!depth.is_empty(), "cycle in DependencyQueue"); |
384056e0 | 126 | return depth; |
e54b5f87 | 127 | } |
0bce4003 | 128 | results.insert(key.clone(), HashSet::new()); |
e54b5f87 | 129 | |
35853c13 E |
130 | let mut set = HashSet::new(); |
131 | set.insert(key.clone()); | |
e54b5f87 | 132 | |
35853c13 | 133 | for dep in map |
ef0b4776 | 134 | .get(key) |
fecb7246 | 135 | .into_iter() |
127fdfeb | 136 | .flat_map(|it| it.values()) |
3fce5092 | 137 | .flatten() |
35853c13 | 138 | { |
384056e0 | 139 | set.extend(depth(dep, map, results).iter().cloned()) |
35853c13 | 140 | } |
e54b5f87 | 141 | |
384056e0 AC |
142 | let slot = results.get_mut(key).unwrap(); |
143 | *slot = set; | |
3fce5092 | 144 | &*slot |
e54b5f87 AC |
145 | } |
146 | } | |
147 | ||
6d0f4579 AC |
148 | /// Dequeues a package that is ready to be built. |
149 | /// | |
150 | /// A package is ready to be built when it has 0 un-built dependencies. If | |
151 | /// `None` is returned then no packages are ready to be built. | |
4ffe98ae RR |
152 | pub fn dequeue(&mut self) -> Option<(N, V, usize)> { |
153 | let (key, priority) = self | |
fecb7246 | 154 | .dep_map |
1e682848 | 155 | .iter() |
127fdfeb | 156 | .filter(|(_, (deps, _))| deps.is_empty()) |
4ffe98ae RR |
157 | .map(|(key, _)| (key.clone(), self.priority[key])) |
158 | .max_by_key(|(_, priority)| *priority)?; | |
edc6ebc5 | 159 | let (_, data) = self.dep_map.remove(&key).unwrap(); |
4ffe98ae | 160 | Some((key, data, priority)) |
6d0f4579 AC |
161 | } |
162 | ||
f7c91ba6 | 163 | /// Returns `true` if there are remaining packages to be built. |
715dcb8e | 164 | pub fn is_empty(&self) -> bool { |
127fdfeb | 165 | self.dep_map.is_empty() |
715dcb8e | 166 | } |
167 | ||
6d0f4579 | 168 | /// Returns the number of remaining packages to be built. |
55321111 | 169 | pub fn len(&self) -> usize { |
127fdfeb | 170 | self.dep_map.len() |
6d0f4579 AC |
171 | } |
172 | ||
127fdfeb | 173 | /// Indicate that something has finished. |
6d0f4579 | 174 | /// |
127fdfeb AC |
175 | /// Calling this function indicates that the `node` has produced `edge`. All |
176 | /// remaining work items which only depend on this node/edge pair are now | |
177 | /// candidates to start their job. | |
06644845 EH |
178 | /// |
179 | /// Returns the nodes that are now allowed to be dequeued as a result of | |
180 | /// finishing this node. | |
181 | pub fn finish(&mut self, node: &N, edge: &E) -> Vec<&N> { | |
182 | // hashset<Node> | |
127fdfeb AC |
183 | let reverse_deps = self.reverse_dep_map.get(node).and_then(|map| map.get(edge)); |
184 | let reverse_deps = match reverse_deps { | |
6d0f4579 | 185 | Some(deps) => deps, |
06644845 | 186 | None => return Vec::new(), |
6d0f4579 | 187 | }; |
127fdfeb | 188 | let key = (node.clone(), edge.clone()); |
06644845 | 189 | let mut result = Vec::new(); |
6d0f4579 | 190 | for dep in reverse_deps.iter() { |
06644845 EH |
191 | let edges = &mut self.dep_map.get_mut(dep).unwrap().0; |
192 | assert!(edges.remove(&key)); | |
193 | if edges.is_empty() { | |
194 | result.push(dep); | |
195 | } | |
6d0f4579 | 196 | } |
06644845 | 197 | result |
6d0f4579 AC |
198 | } |
199 | } | |
e54b5f87 AC |
200 | |
201 | #[cfg(test)] | |
202 | mod test { | |
e9428cba | 203 | use super::DependencyQueue; |
e54b5f87 AC |
204 | |
205 | #[test] | |
dd5aca30 | 206 | fn deep_first_equal_cost() { |
e54b5f87 AC |
207 | let mut q = DependencyQueue::new(); |
208 | ||
dd5aca30 JM |
209 | q.queue(1, (), vec![], 1); |
210 | q.queue(2, (), vec![(1, ())], 1); | |
211 | q.queue(3, (), vec![], 1); | |
212 | q.queue(4, (), vec![(2, ()), (3, ())], 1); | |
213 | q.queue(5, (), vec![(4, ()), (3, ())], 1); | |
e54b5f87 AC |
214 | q.queue_finished(); |
215 | ||
4ffe98ae RR |
216 | assert_eq!(q.dequeue(), Some((1, (), 5))); |
217 | assert_eq!(q.dequeue(), Some((3, (), 4))); | |
e54b5f87 | 218 | assert_eq!(q.dequeue(), None); |
127fdfeb | 219 | q.finish(&3, &()); |
e54b5f87 | 220 | assert_eq!(q.dequeue(), None); |
127fdfeb | 221 | q.finish(&1, &()); |
4ffe98ae | 222 | assert_eq!(q.dequeue(), Some((2, (), 4))); |
e54b5f87 | 223 | assert_eq!(q.dequeue(), None); |
127fdfeb | 224 | q.finish(&2, &()); |
4ffe98ae | 225 | assert_eq!(q.dequeue(), Some((4, (), 3))); |
e54b5f87 | 226 | assert_eq!(q.dequeue(), None); |
127fdfeb | 227 | q.finish(&4, &()); |
4ffe98ae | 228 | assert_eq!(q.dequeue(), Some((5, (), 2))); |
e54b5f87 | 229 | } |
dd5aca30 JM |
230 | |
231 | #[test] | |
232 | fn sort_by_highest_cost() { | |
233 | let mut q = DependencyQueue::new(); | |
234 | ||
235 | q.queue(1, (), vec![], 1); | |
236 | q.queue(2, (), vec![(1, ())], 1); | |
237 | q.queue(3, (), vec![], 4); | |
238 | q.queue(4, (), vec![(2, ()), (3, ())], 1); | |
239 | q.queue_finished(); | |
240 | ||
4ffe98ae RR |
241 | assert_eq!(q.dequeue(), Some((3, (), 9))); |
242 | assert_eq!(q.dequeue(), Some((1, (), 4))); | |
dd5aca30 JM |
243 | assert_eq!(q.dequeue(), None); |
244 | q.finish(&3, &()); | |
245 | assert_eq!(q.dequeue(), None); | |
246 | q.finish(&1, &()); | |
4ffe98ae | 247 | assert_eq!(q.dequeue(), Some((2, (), 3))); |
dd5aca30 JM |
248 | assert_eq!(q.dequeue(), None); |
249 | q.finish(&2, &()); | |
4ffe98ae | 250 | assert_eq!(q.dequeue(), Some((4, (), 2))); |
dd5aca30 JM |
251 | assert_eq!(q.dequeue(), None); |
252 | q.finish(&4, &()); | |
253 | assert_eq!(q.dequeue(), None); | |
254 | } | |
e54b5f87 | 255 | } |