bind/compiler/
dependency_graph.rs

1// Copyright 2019 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::collections::{HashMap, HashSet};
6use std::fmt::Debug;
7use std::hash::Hash;
8use std::mem;
9
10pub struct DependencyGraph<K: Eq + Hash, V> {
11    // Storage for all nodes in the graph.
12    nodes: Vec<Node<K, V>>,
13
14    // Maps keys to the corresponding index in |nodes|.
15    indices: HashMap<K, usize>,
16
17    // Maps nodes to their children using an index into |nodes|.
18    children: HashMap<usize, HashSet<usize>>,
19
20    // Maps nodes to their parents using an index into |nodes|.
21    parents: HashMap<usize, HashSet<usize>>,
22}
23
24enum Node<K, V> {
25    // The root node has no data or key.
26    Root,
27
28    // Data nodes have a key and a value.
29    Data(K, V),
30
31    // Zombie nodes have been removed from the graph. This is used to avoid index updates to the
32    // graph's storage vector when removing a node.
33    Zombie,
34}
35
36#[derive(Debug, Clone, PartialEq)]
37pub enum DependencyError<K: Clone + Debug + PartialEq> {
38    MissingDependency(K),
39    CircularDependency,
40}
41
42impl<K: Eq + Hash + Clone + Debug, V> DependencyGraph<K, V> {
43    const ROOT_INDEX: usize = 0;
44
45    /// Constructs a dependency graph and populates it with a root node.
46    pub fn new() -> DependencyGraph<K, V> {
47        Self {
48            nodes: vec![Node::Root],
49            indices: HashMap::new(),
50            children: HashMap::new(),
51            parents: HashMap::new(),
52        }
53    }
54
55    /// Insert a node into the graph with |key| and attach |data| to the node.
56    ///
57    /// If the node already exists, it is replaced.
58    pub fn insert_node(&mut self, key: K, data: V) {
59        let index = self.nodes.len();
60        self.nodes.push(Node::Data(key.clone(), data));
61        if let Some(previous) = self.indices.insert(key, index) {
62            self.nodes[previous] = Node::Zombie;
63        }
64    }
65
66    /// Inserts an edge from the root of the graph to the node with key |to|.
67    ///
68    /// If |to| doesn't exist in the graph, return a MissingDependency error.
69    pub fn insert_edge_from_root(&mut self, to: &K) -> Result<(), DependencyError<K>> {
70        let to_index = self.get_index(to)?;
71        self.children.entry(Self::ROOT_INDEX).or_insert(HashSet::new()).insert(to_index);
72        self.parents.entry(to_index).or_insert(HashSet::new()).insert(Self::ROOT_INDEX);
73        Ok(())
74    }
75
76    /// Inserts an edge from the root of the graph from the node with key |from| to the node with
77    /// key |to|.
78    ///
79    /// If either |from| or |to| doesn't exist in the graph, return a MissingDependency error.
80    pub fn insert_edge(&mut self, from: &K, to: &K) -> Result<(), DependencyError<K>> {
81        let from_index = self.get_index(from)?;
82        let to_index = self.get_index(to)?;
83        self.children.entry(from_index).or_insert(HashSet::new()).insert(to_index);
84        self.parents.entry(to_index).or_insert(HashSet::new()).insert(from_index);
85        Ok(())
86    }
87
88    /// Resolve the dependency graph, returning the data associated with each node in a path from
89    /// the root node to its dependencies. For each node in the path all of its dependencies must
90    /// appear after its position in the path. Any node that has no dependency chain from the root
91    /// is pruned from the path.
92    ///
93    /// If no such path is possible return a CircularDependency error.
94    pub fn resolve(mut self) -> Result<Vec<V>, DependencyError<K>> {
95        // This is a minor variation on Kahn's algorithm. We do not start by finding all nodes with
96        // no incoming edges because we know that the root node has no incoming edges, and that all
97        // other such nodes will be pruned.
98        self.prune_orphans()?;
99
100        let mut result = vec![];
101        let mut next_indices = vec![Self::ROOT_INDEX];
102        while let Some(index) = next_indices.pop() {
103            if let Some(data) = self.remove(index) {
104                result.push(data);
105            }
106
107            for child_index in self.children.entry(index).or_default().clone() {
108                self.remove_edge(index, child_index)?;
109                if self.is_orphaned(&self.nodes[child_index]) {
110                    next_indices.push(child_index);
111                }
112            }
113        }
114        if self.is_empty() {
115            Ok(result)
116        } else {
117            Err(DependencyError::CircularDependency)
118        }
119    }
120}
121
122impl<K: Eq + Hash + Clone + Debug, V> DependencyGraph<K, V> {
123    fn get_index(&self, key: &K) -> Result<usize, DependencyError<K>> {
124        let index = self.indices.get(key).ok_or(DependencyError::MissingDependency(key.clone()))?;
125        Ok(*index)
126    }
127
128    fn remove_edge(
129        &mut self,
130        from_index: usize,
131        to_index: usize,
132    ) -> Result<(), DependencyError<K>> {
133        let to_parents =
134            self.parents.get_mut(&to_index).expect("remove_edge called with invalid to_index");
135        to_parents.remove(&from_index);
136        let from_children =
137            self.children.get_mut(&from_index).expect("remove_edge called with invalid from_index");
138        from_children.remove(&to_index);
139        Ok(())
140    }
141
142    fn is_orphaned(&self, node: &Node<K, V>) -> bool {
143        match node {
144            Node::Data(key, _) => {
145                let index = self.indices.get(key).expect("Key exists in node but not in graph");
146                self.parents.get(index).map(|vs| vs.is_empty()).unwrap_or(true)
147            }
148            Node::Root => false,
149            Node::Zombie => false,
150        }
151    }
152
153    fn remove(&mut self, index: usize) -> Option<V> {
154        // Pull out the node while maintaining all the other indices.
155        match mem::replace(&mut self.nodes[index], Node::Zombie) {
156            Node::Data(_, data) => Some(data),
157            _ => None,
158        }
159    }
160
161    // Prune all orphaned nodes (nodes with no parents). This removes nodes that have no path from
162    // the root node.
163    fn prune_orphans(&mut self) -> Result<(), DependencyError<K>> {
164        while let Some((index, _)) =
165            self.nodes.iter().enumerate().find(|(_, node)| self.is_orphaned(node))
166        {
167            self.remove(index);
168
169            // Remove child edges.
170            let child_indices = self.children.entry(index).or_default().clone();
171            for child_index in child_indices {
172                self.remove_edge(index, child_index)?;
173            }
174        }
175
176        Ok(())
177    }
178
179    fn is_empty(&self) -> bool {
180        self.children.values().all(|xs| xs.is_empty())
181            && self.parents.values().all(|xs| xs.is_empty())
182    }
183}
184
185#[cfg(test)]
186mod test {
187    use super::*;
188
189    #[test]
190    fn simple() {
191        let mut graph = DependencyGraph::new();
192
193        graph.insert_node(1, "one");
194        graph.insert_node(2, "two");
195        graph.insert_node(3, "three");
196
197        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
198        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
199        assert_eq!(graph.insert_edge(&2, &3), Ok(()));
200
201        assert_eq!(graph.resolve(), Ok(vec!["one", "two", "three",]));
202    }
203
204    #[test]
205    fn empty() {
206        let graph: DependencyGraph<usize, usize> = DependencyGraph::new();
207        assert!(graph.resolve().unwrap().is_empty());
208    }
209
210    #[test]
211    fn insert_replaces() {
212        let mut graph = DependencyGraph::new();
213
214        graph.insert_node(1, "one");
215        graph.insert_node(1, "two");
216
217        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
218
219        assert_eq!(graph.resolve(), Ok(vec!["two"]));
220    }
221
222    #[test]
223    fn branching_edges_from_root() {
224        let mut graph = DependencyGraph::new();
225
226        graph.insert_node(1, "one");
227        graph.insert_node(2, "two");
228        graph.insert_node(3, "three");
229        graph.insert_node(4, "four");
230
231        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
232        assert_eq!(graph.insert_edge_from_root(&2), Ok(()));
233
234        assert_eq!(graph.insert_edge(&1, &3), Ok(()));
235        assert_eq!(graph.insert_edge(&2, &4), Ok(()));
236
237        let result = graph.resolve().unwrap();
238        assert!(result.contains(&"one"));
239        assert!(result.contains(&"two"));
240        assert!(result.contains(&"three"));
241        assert!(result.contains(&"four"));
242        assert!(
243            result.iter().position(|&x| x == "one") < result.iter().position(|&x| x == "three")
244        );
245        assert!(result.iter().position(|&x| x == "two") < result.iter().position(|&x| x == "four"));
246    }
247
248    #[test]
249    fn branching_edges() {
250        let mut graph = DependencyGraph::new();
251
252        graph.insert_node(1, "one");
253        graph.insert_node(2, "two");
254        graph.insert_node(3, "three");
255        graph.insert_node(4, "four");
256        graph.insert_node(5, "five");
257
258        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
259
260        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
261        assert_eq!(graph.insert_edge(&2, &3), Ok(()));
262
263        assert_eq!(graph.insert_edge(&1, &4), Ok(()));
264        assert_eq!(graph.insert_edge(&4, &5), Ok(()));
265
266        let result = graph.resolve().unwrap();
267        assert!(result.contains(&"one"));
268        assert!(result.contains(&"two"));
269        assert!(result.contains(&"three"));
270        assert!(result.contains(&"four"));
271        assert!(result.contains(&"five"));
272        assert_eq!(result[0], "one");
273        assert!(
274            result.iter().position(|&x| x == "two") < result.iter().position(|&x| x == "three")
275        );
276        assert!(
277            result.iter().position(|&x| x == "four") < result.iter().position(|&x| x == "five")
278        );
279    }
280
281    #[test]
282    fn multiple_incoming_edges() {
283        let mut graph = DependencyGraph::new();
284
285        graph.insert_node(1, "one");
286        graph.insert_node(2, "two");
287        graph.insert_node(3, "three");
288
289        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
290
291        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
292        assert_eq!(graph.insert_edge(&1, &3), Ok(()));
293        assert_eq!(graph.insert_edge(&2, &3), Ok(()));
294
295        assert_eq!(graph.resolve(), Ok(vec!["one", "two", "three",]));
296    }
297
298    #[test]
299    fn prunes_disconnected_graph() {
300        let mut graph = DependencyGraph::new();
301
302        graph.insert_node(1, "one");
303        graph.insert_node(2, "two");
304        graph.insert_node(3, "three");
305
306        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
307
308        assert_eq!(graph.insert_edge(&2, &3), Ok(()));
309
310        assert_eq!(graph.resolve(), Ok(vec!["one"]));
311    }
312
313    #[test]
314    fn circular_dependency() {
315        let mut graph = DependencyGraph::new();
316
317        graph.insert_node(1, "one");
318        graph.insert_node(2, "two");
319        graph.insert_node(3, "three");
320
321        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
322
323        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
324        assert_eq!(graph.insert_edge(&2, &3), Ok(()));
325        assert_eq!(graph.insert_edge(&3, &1), Ok(()));
326
327        assert_eq!(graph.resolve(), Err(DependencyError::CircularDependency));
328    }
329
330    #[test]
331    fn missing_root_dependency() {
332        let mut graph: DependencyGraph<usize, usize> = DependencyGraph::new();
333
334        assert_eq!(graph.insert_edge_from_root(&1), Err(DependencyError::MissingDependency(1)));
335    }
336
337    #[test]
338    fn missing_dependency() {
339        let mut graph = DependencyGraph::new();
340
341        graph.insert_node(1, "one");
342
343        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
344
345        assert_eq!(graph.insert_edge(&1, &2), Err(DependencyError::MissingDependency(2)));
346        assert_eq!(graph.insert_edge(&2, &1), Err(DependencyError::MissingDependency(2)));
347    }
348}
bind/compiler/dependency_graph.rs

bind/compiler/
dependency_graph.rs
