#
cargo/util/
graph.rs

    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}