dep_graph/
graph.rs

1use crate::{error::Error, Node};
2
3use std::collections::{HashMap, HashSet};
4use std::fmt;
5use std::hash::Hash;
6use std::sync::{Arc, RwLock};
7
8pub type InnerDependencyMap<I> = HashMap<I, HashSet<I>>;
9pub type DependencyMap<I> = Arc<RwLock<InnerDependencyMap<I>>>;
10
11/// Dependency graph
12pub struct DepGraph<I>
13where
14    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
15{
16    pub ready_nodes: Vec<I>,
17    pub deps: DependencyMap<I>,
18    pub rdeps: DependencyMap<I>,
19}
20
21impl<I> DepGraph<I>
22where
23    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
24{
25    /// Create a new DepGraph based on a vector of edges.
26    pub fn new(nodes: &[Node<I>]) -> Self {
27        let (deps, rdeps, ready_nodes) = DepGraph::parse_nodes(nodes);
28
29        DepGraph {
30            ready_nodes,
31            deps,
32            rdeps,
33        }
34    }
35
36    fn parse_nodes(nodes: &[Node<I>]) -> (DependencyMap<I>, DependencyMap<I>, Vec<I>) {
37        let mut deps = InnerDependencyMap::<I>::default();
38        let mut rdeps = InnerDependencyMap::<I>::default();
39        let mut ready_nodes = Vec::<I>::default();
40
41        for node in nodes {
42            deps.insert(node.id().clone(), node.deps().clone());
43
44            if node.deps().is_empty() {
45                ready_nodes.push(node.id().clone());
46            }
47
48            for node_dep in node.deps() {
49                if !rdeps.contains_key(node_dep) {
50                    let mut dep_rdeps = HashSet::new();
51                    dep_rdeps.insert(node.id().clone());
52                    rdeps.insert(node_dep.clone(), dep_rdeps.clone());
53                } else {
54                    let dep_rdeps = rdeps.get_mut(node_dep).unwrap();
55                    dep_rdeps.insert(node.id().clone());
56                }
57            }
58        }
59
60        (
61            Arc::new(RwLock::new(deps)),
62            Arc::new(RwLock::new(rdeps)),
63            ready_nodes,
64        )
65    }
66}
67
68impl<I> IntoIterator for DepGraph<I>
69where
70    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
71{
72    type Item = I;
73    type IntoIter = DepGraphIter<I>;
74
75    fn into_iter(self) -> Self::IntoIter {
76        DepGraphIter::<I>::new(self.ready_nodes.clone(), self.deps.clone(), self.rdeps)
77    }
78}
79
80#[derive(Clone)]
81pub struct DepGraphIter<I>
82where
83    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
84{
85    ready_nodes: Vec<I>,
86    deps: DependencyMap<I>,
87    rdeps: DependencyMap<I>,
88}
89
90impl<I> DepGraphIter<I>
91where
92    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
93{
94    pub fn new(ready_nodes: Vec<I>, deps: DependencyMap<I>, rdeps: DependencyMap<I>) -> Self {
95        Self {
96            ready_nodes,
97            deps,
98            rdeps,
99        }
100    }
101}
102
103impl<I> Iterator for DepGraphIter<I>
104where
105    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
106{
107    type Item = I;
108
109    fn next(&mut self) -> Option<Self::Item> {
110        if let Some(id) = self.ready_nodes.pop() {
111            // Remove dependencies and retrieve next available nodes, if any.
112            let next_nodes = remove_node_id::<I>(id.clone(), &self.deps, &self.rdeps).unwrap();
113
114            // Push ready nodes
115            self.ready_nodes.extend_from_slice(&next_nodes);
116
117            // Return the node ID
118            Some(id)
119        } else {
120            // No available node
121            None
122        }
123    }
124}
125
126/// Remove all references to the node ID in the dependencies.
127///
128pub fn remove_node_id<I>(
129    id: I,
130    deps: &DependencyMap<I>,
131    rdeps: &DependencyMap<I>,
132) -> Result<Vec<I>, Error>
133where
134    I: Clone + fmt::Debug + Eq + Hash + PartialEq + Send + Sync + 'static,
135{
136    let rdep_ids = {
137        match rdeps.read().unwrap().get(&id) {
138            Some(node) => node.clone(),
139            // If no node depends on a node, it will not appear
140            // in rdeps.
141            None => Default::default(),
142        }
143    };
144
145    let mut deps = deps.write().unwrap();
146    let next_nodes = rdep_ids
147        .iter()
148        .filter_map(|rdep_id| {
149            let rdep = match deps.get_mut(&rdep_id) {
150                Some(rdep) => rdep,
151                None => return None,
152            };
153
154            rdep.remove(&id);
155
156            if rdep.is_empty() {
157                Some(rdep_id.clone())
158            } else {
159                None
160            }
161        })
162        .collect();
163
164    // Remove the current node from the list of dependencies.
165    deps.remove(&id);
166
167    Ok(next_nodes)
168}
dep_graph/graph.rs

dep_graph/
graph.rs
