cargo/util/
graph.rs

Help
1use std::borrow::Borrow;
2use std::collections::{BTreeMap, BTreeSet, VecDeque};
3use std::fmt;
4
5pub struct Graph<N: Clone, E: Clone> {
6    nodes: im_rc::OrdMap<N, im_rc::OrdMap<N, E>>,
7}
8
9impl<N: Eq + Ord + Clone, E: Default + Clone> Graph<N, E> {
10    pub fn new() -> Graph<N, E> {
11        Graph {
12            nodes: im_rc::OrdMap::new(),
13        }
14    }
15
16    pub fn add(&mut self, node: N) {
17        self.nodes.entry(node).or_insert_with(im_rc::OrdMap::new);
18    }
19
20    pub fn link(&mut self, node: N, child: N) -> &mut E {
21        self.nodes
22            .entry(node)
23            .or_insert_with(im_rc::OrdMap::new)
24            .entry(child)
25            .or_default()
26    }
27
28    /// Returns the graph obtained by reversing all edges.
29    pub fn reversed(&self) -> Graph<N, E> {
30        let mut ret = Graph::new();
31
32        for n in self.iter() {
33            ret.add(n.clone());
34            for (m, e) in self.edges(n) {
35                *ret.link(m.clone(), n.clone()) = e.clone();
36            }
37        }
38
39        ret
40    }
41
42    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
43    where
44        N: Borrow<Q>,
45        Q: Ord + Eq,
46    {
47        self.nodes.contains_key(k)
48    }
49
50    pub fn edge(&self, from: &N, to: &N) -> Option<&E> {
51        self.nodes.get(from)?.get(to)
52    }
53
54    pub fn edges(&self, from: &N) -> impl Iterator<Item = (&N, &E)> {
55        self.nodes.get(from).into_iter().flat_map(|x| x.iter())
56    }
57
58    /// A topological sort of the `Graph`
59    pub fn sort(&self) -> Vec<N> {
60        let mut ret = Vec::new();
61        let mut marks = BTreeSet::new();
62
63        for node in self.nodes.keys() {
64            self.sort_inner_visit(node, &mut ret, &mut marks);
65        }
66
67        ret
68    }
69
70    fn sort_inner_visit(&self, node: &N, dst: &mut Vec<N>, marks: &mut BTreeSet<N>) {
71        if !marks.insert(node.clone()) {
72            return;
73        }
74
75        for child in self.nodes[node].keys() {
76            self.sort_inner_visit(child, dst, marks);
77        }
78
79        dst.push(node.clone());
80    }
81
82    pub fn iter(&self) -> impl Iterator<Item = &N> {
83        self.nodes.keys()
84    }
85
86    pub fn len(&self) -> usize {
87        self.nodes.len()
88    }
89
90    /// Checks if there is a path from `from` to `to`.
91    pub fn is_path_from_to<'a>(&'a self, from: &'a N, to: &'a N) -> bool {
92        let mut stack = vec![from];
93        let mut seen = BTreeSet::new();
94        seen.insert(from);
95        while let Some(iter) = stack.pop().and_then(|p| self.nodes.get(p)) {
96            for p in iter.keys() {
97                if p == to {
98                    return true;
99                }
100                if seen.insert(p) {
101                    stack.push(p);
102                }
103            }
104        }
105        false
106    }
107
108    /// Resolves one of the paths from the given dependent package down to a leaf.
109    ///
110    /// The path return will be the shortest path, or more accurately one of the paths with the shortest length.
111    ///
112    /// Each element contains a node along with an edge except the first one.
113    /// The representation would look like:
114    ///
115    /// (Node0,) -> (Node1, Edge01) -> (Node2, Edge12)...
116    pub fn path_to_bottom<'a>(&'a self, pkg: &'a N) -> Vec<(&'a N, Option<&'a E>)> {
117        self.path_to(pkg, |s, p| s.edges(p))
118    }
119
120    /// Resolves one of the paths from the given dependent package up to the root.
121    ///
122    /// The path return will be the shortest path, or more accurately one of the paths with the shortest length.
123    ///
124    /// Each element contains a node along with an edge except the first one.
125    /// The representation would look like:
126    ///
127    /// (Node0,) -> (Node1, Edge01) -> (Node2, Edge12)...
128    pub fn path_to_top<'a>(&'a self, pkg: &'a N) -> Vec<(&'a N, Option<&'a E>)> {
129        self.path_to(pkg, |s, pk| {
130            // Note that this implementation isn't the most robust per se, we'll
131            // likely have to tweak this over time. For now though it works for what
132            // it's used for!
133            s.nodes
134                .iter()
135                .filter_map(|(p, adjacent)| adjacent.get(pk).map(|e| (p, e)))
136        })
137    }
138}
139
140impl<'s, N: Eq + Ord + Clone + 's, E: Default + Clone + 's> Graph<N, E> {
141    fn path_to<'a, F, I>(&'s self, pkg: &'a N, fn_edge: F) -> Vec<(&'a N, Option<&'a E>)>
142    where
143        I: Iterator<Item = (&'a N, &'a E)>,
144        F: Fn(&'s Self, &'a N) -> I,
145        'a: 's,
146    {
147        let mut back_link = BTreeMap::new();
148        let mut queue = VecDeque::from([pkg]);
149        let mut last = pkg;
150
151        while let Some(p) = queue.pop_front() {
152            last = p;
153            let mut out_edges = true;
154            for (child, edge) in fn_edge(&self, p) {
155                out_edges = false;
156                back_link.entry(child).or_insert_with(|| {
157                    queue.push_back(child);
158                    (p, edge)
159                });
160            }
161            if out_edges {
162                break;
163            }
164        }
165
166        let mut result = Vec::new();
167        let mut next = last;
168        while let Some((p, e)) = back_link.remove(&next) {
169            result.push((next, Some(e)));
170            next = p;
171        }
172        if result.iter().all(|(n, _)| n != &next) {
173            result.push((next, None));
174        }
175        result.reverse();
176        #[cfg(debug_assertions)]
177        {
178            for x in result.windows(2) {
179                let [(n2, _), (n1, Some(e12))] = x else {
180                    unreachable!()
181                };
182                assert!(std::ptr::eq(
183                    self.edge(n1, n2).or(self.edge(n2, n1)).unwrap(),
184                    *e12
185                ));
186            }
187            let last = result.last().unwrap().0;
188            let set: Vec<_> = result.iter().map(|(k, _)| k).collect();
189            if !fn_edge(&self, last)
190                .filter(|(e, _)| !set.contains(&e))
191                .next()
192                .is_none()
193            {
194                self.print_for_test();
195                unreachable!("The last element in the path should not have outgoing edges");
196            }
197        }
198        result
199    }
200}
201
202#[test]
203fn path_to_case() {
204    let mut new = Graph::new();
205    new.link(0, 3);
206    new.link(1, 0);
207    new.link(2, 0);
208    new.link(2, 1);
209    assert_eq!(
210        new.path_to_bottom(&2),
211        vec![(&2, None), (&0, Some(&())), (&3, Some(&()))]
212    );
213}
214
215#[test]
216fn path_to_self() {
217    // Extracted from #12941
218    let mut new: Graph<i32, ()> = Graph::new();
219    new.link(0, 0);
220    assert_eq!(new.path_to_bottom(&0), vec![(&0, Some(&()))]);
221}
222
223#[test]
224fn reverse() {
225    let mut new: Graph<i32, ()> = Graph::new();
226    new.link(0, 1);
227    new.link(0, 2);
228
229    let mut expected: Graph<i32, ()> = Graph::new();
230    expected.add(0);
231    expected.link(1, 0);
232    expected.link(2, 0);
233    assert_eq!(new.reversed(), expected);
234}
235
236impl<N: Eq + Ord + Clone, E: Default + Clone> Default for Graph<N, E> {
237    fn default() -> Graph<N, E> {
238        Graph::new()
239    }
240}
241
242impl<N: fmt::Display + Eq + Ord + Clone, E: Clone> fmt::Debug for Graph<N, E> {
243    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
244        writeln!(fmt, "Graph {{")?;
245
246        for (n, e) in &self.nodes {
247            writeln!(fmt, "  - {}", n)?;
248
249            for n in e.keys() {
250                writeln!(fmt, "    - {}", n)?;
251            }
252        }
253
254        write!(fmt, "}}")?;
255
256        Ok(())
257    }
258}
259
260impl<N: Eq + Ord + Clone, E: Clone> Graph<N, E> {
261    /// Prints the graph for constructing unit tests.
262    ///
263    /// For purposes of graph traversal algorithms the edge values do not matter,
264    /// and the only value of the node we care about is the order it gets compared in.
265    /// This constructs a graph with the same topology but with integer keys and unit edges.
266    #[cfg(debug_assertions)]
267    #[allow(clippy::print_stderr)]
268    fn print_for_test(&self) {
269        // Isolate and print a test case.
270        let names = self
271            .nodes
272            .keys()
273            .chain(self.nodes.values().flat_map(|vs| vs.keys()))
274            .collect::<BTreeSet<_>>()
275            .into_iter()
276            .collect::<Vec<_>>();
277        let mut new = Graph::new();
278        for n1 in self.nodes.keys() {
279            let name1 = names.binary_search(&n1).unwrap();
280            new.add(name1);
281            for n2 in self.nodes[n1].keys() {
282                let name2 = names.binary_search(&n2).unwrap();
283                *new.link(name1, name2) = ();
284            }
285        }
286        eprintln!("Graph for tests = {new:#?}");
287    }
288}
289
290impl<N: Eq + Ord + Clone, E: Eq + Clone> PartialEq for Graph<N, E> {
291    fn eq(&self, other: &Graph<N, E>) -> bool {
292        self.nodes.eq(&other.nodes)
293    }
294}
295impl<N: Eq + Ord + Clone, E: Eq + Clone> Eq for Graph<N, E> {}
296
297impl<N: Eq + Ord + Clone, E: Clone> Clone for Graph<N, E> {
298    fn clone(&self) -> Graph<N, E> {
299        Graph {
300            nodes: self.nodes.clone(),
301        }
302    }
303}
cargo/util/graph.rs

cargo/util/
graph.rs
