cargo/util/
graph.rs

1use std::borrow::Borrow;
2use std::collections::BTreeSet;
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_insert_with(Default::default)
26    }
27
28    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
29    where
30        N: Borrow<Q>,
31        Q: Ord + Eq,
32    {
33        self.nodes.contains_key(k)
34    }
35
36    pub fn edge(&self, from: &N, to: &N) -> Option<&E> {
37        self.nodes.get(from)?.get(to)
38    }
39
40    pub fn edges(&self, from: &N) -> impl Iterator<Item = &(N, E)> {
41        self.nodes.get(from).into_iter().flat_map(|x| x.iter())
42    }
43
44    /// A topological sort of the `Graph`
45    pub fn sort(&self) -> Vec<N> {
46        let mut ret = Vec::new();
47        let mut marks = BTreeSet::new();
48
49        for node in self.nodes.keys() {
50            self.sort_inner_visit(node, &mut ret, &mut marks);
51        }
52
53        ret
54    }
55
56    fn sort_inner_visit(&self, node: &N, dst: &mut Vec<N>, marks: &mut BTreeSet<N>) {
57        if !marks.insert(node.clone()) {
58            return;
59        }
60
61        for child in self.nodes[node].keys() {
62            self.sort_inner_visit(child, dst, marks);
63        }
64
65        dst.push(node.clone());
66    }
67
68    pub fn iter(&self) -> impl Iterator<Item = &N> {
69        self.nodes.keys()
70    }
71
72    /// Checks if there is a path from `from` to `to`.
73    pub fn is_path_from_to<'a>(&'a self, from: &'a N, to: &'a N) -> bool {
74        let mut stack = vec![from];
75        let mut seen = BTreeSet::new();
76        seen.insert(from);
77        while let Some(iter) = stack.pop().and_then(|p| self.nodes.get(p)) {
78            for p in iter.keys() {
79                if p == to {
80                    return true;
81                }
82                if seen.insert(p) {
83                    stack.push(p);
84                }
85            }
86        }
87        false
88    }
89
90    /// Resolves one of the paths from the given dependent package down to
91    /// a leaf.
92    pub fn path_to_bottom<'a>(&'a self, mut pkg: &'a N) -> Vec<&'a N> {
93        let mut result = vec![pkg];
94        while let Some(p) = self.nodes.get(pkg).and_then(|p| {
95            p.iter()
96                // Note that we can have "cycles" introduced through dev-dependency
97                // edges, so make sure we don't loop infinitely.
98                .find(|&(node, _)| !result.contains(&node))
99                .map(|(ref p, _)| p)
100        }) {
101            result.push(p);
102            pkg = p;
103        }
104        result
105    }
106
107    /// Resolves one of the paths from the given dependent package up to
108    /// the root.
109    pub fn path_to_top<'a>(&'a self, mut pkg: &'a N) -> Vec<&'a N> {
110        // Note that this implementation isn't the most robust per se, we'll
111        // likely have to tweak this over time. For now though it works for what
112        // it's used for!
113        let mut result = vec![pkg];
114        let first_pkg_depending_on = |pkg: &N, res: &[&N]| {
115            self.nodes
116                .iter()
117                .filter(|&(_, adjacent)| adjacent.contains_key(pkg))
118                // Note that we can have "cycles" introduced through dev-dependency
119                // edges, so make sure we don't loop infinitely.
120                .find(|&(node, _)| !res.contains(&node))
121                .map(|(ref p, _)| p)
122        };
123        while let Some(p) = first_pkg_depending_on(pkg, &result) {
124            result.push(p);
125            pkg = p;
126        }
127        result
128    }
129}
130
131impl<N: Eq + Ord + Clone, E: Default + Clone> Default for Graph<N, E> {
132    fn default() -> Graph<N, E> {
133        Graph::new()
134    }
135}
136
137impl<N: fmt::Display + Eq + Ord + Clone, E: Clone> fmt::Debug for Graph<N, E> {
138    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
139        writeln!(fmt, "Graph {{")?;
140
141        for (n, e) in &self.nodes {
142            writeln!(fmt, "  - {}", n)?;
143
144            for n in e.keys() {
145                writeln!(fmt, "    - {}", n)?;
146            }
147        }
148
149        write!(fmt, "}}")?;
150
151        Ok(())
152    }
153}
154
155impl<N: Eq + Ord + Clone, E: Eq + Clone> PartialEq for Graph<N, E> {
156    fn eq(&self, other: &Graph<N, E>) -> bool {
157        self.nodes.eq(&other.nodes)
158    }
159}
160impl<N: Eq + Ord + Clone, E: Eq + Clone> Eq for Graph<N, E> {}
161
162impl<N: Eq + Ord + Clone, E: Clone> Clone for Graph<N, E> {
163    fn clone(&self) -> Graph<N, E> {
164        Graph {
165            nodes: self.nodes.clone(),
166        }
167    }
168}
cargo/util/graph.rs

cargo/util/
graph.rs
