wasmtime_environ/graphs/

scc.rs

//! Strongly-connected components.
//!
//! This module implements [Tarjan's algorithm] for finding strongly-connected
//! components.
//!
//! This algorithm takes `O(V+E)` time and uses `O(V+E)` space.
//!
//! Tarjan's algorithm is usually presented as a recursive algorithm, but we do
//! not trust the input and cannot recurse over it for fear of blowing the
//! stack. Therefore, this implementation is iterative.
//!
//! [Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

use super::*;
use crate::{
    EntityRef, EntitySet, PrimaryMap, SecondaryMap, non_max::NonMaxU32,
    packed_option::PackedOption, prelude::*,
};
use alloc::collections::BTreeSet;
use core::{
    cmp,
    fmt::{self, Debug},
    hash::Hash,
    iter,
    ops::Range,
};

/// A strongly-connected component.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Scc(u32);
crate::entity_impl!(Scc);

/// The set of strongly-connected components for a graph of `Node`s.
pub struct StronglyConnectedComponents<Node>
where
    Node: EntityRef,
{
    /// A map from a component to the range of `self.component_nodes` that make
    /// up that component's nodes.
    components: PrimaryMap<Scc, Range<u32>>,

    /// The data storage for the values of `self.components`.
    component_nodes: Vec<Node>,
}

impl<Node> Debug for StronglyConnectedComponents<Node>
where
    Node: EntityRef + Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        struct Map<'a, Node: EntityRef + Debug>(&'a StronglyConnectedComponents<Node>);

        impl<'a, Node> Debug for Map<'a, Node>
        where
            Node: EntityRef + Debug,
        {
            fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> fmt::Result {
                f.debug_map().entries(self.0.iter()).finish()
            }
        }

        f.debug_struct("StronglyConnectedComponents")
            .field("components", &Map(self))
            .finish()
    }
}

impl<Node> StronglyConnectedComponents<Node>
where
    Node: EntityRef + Debug,
{
    /// Find the strongly-connected for the given graph.
    pub fn new<G>(graph: G) -> Self
    where
        G: Graph<Node>,
    {
        let nodes = graph.nodes();

        // The resulting components and their nodes.
        let mut component_nodes = vec![];
        let mut components = PrimaryMap::<Scc, Range<u32>>::new();

        // The DFS index counter.
        let mut index = NonMaxU32::default();

        // The DFS index and the earliest on-stack node reachable from each
        // node.
        let (min, max) = nodes.size_hint();
        let capacity = max.unwrap_or_else(|| 2 * min);
        let mut indices = SecondaryMap::<Node, Option<NonMaxU32>>::with_capacity(capacity);
        let mut lowlinks = SecondaryMap::<Node, Option<NonMaxU32>>::with_capacity(capacity);

        // The stack of nodes we are currently finding an SCC for. Not the same
        // as the DFS stack: we only pop from this stack once we find the root
        // of an SCC.
        let mut stack = vec![];
        let mut on_stack = EntitySet::<Node>::new();

        let mut dfs = Dfs::new(nodes);
        while let Some(event) = dfs.next(
            &graph,
            // We have seen the node before if we have assigned it a DFS index.
            |node| indices[node].is_some(),
        ) {
            match event {
                DfsEvent::Pre(node) => {
                    debug_assert!(indices[node].is_none());
                    debug_assert!(lowlinks[node].is_none());

                    // Assign an index to this node.
                    indices[node] = Some(index);

                    // Its current lowlink is itself. This will get updated to
                    // be accurate as we visit the node's successors.
                    lowlinks[node] = Some(index);

                    // Increment the DFS counter.
                    index = NonMaxU32::new(index.get() + 1).unwrap();

                    // Push the node onto the SCC stack.
                    stack.push(node);
                    let is_newly_on_stack = on_stack.insert(node);
                    debug_assert!(is_newly_on_stack);
                }

                DfsEvent::AfterEdge(node, succ) => {
                    debug_assert!(indices[node].is_some());
                    debug_assert!(lowlinks[node].is_some());
                    debug_assert!(lowlinks[node] <= indices[node]);
                    debug_assert!(indices[succ].is_some());
                    debug_assert!(lowlinks[succ].is_some());
                    debug_assert!(lowlinks[succ] <= indices[succ]);

                    // If the successor is still on the SCC stack, then it is
                    // part of the same SCC as this node, so propagate its
                    // lowlink to this node's lowlink.
                    if on_stack.contains(succ) {
                        lowlinks[node] =
                            Some(cmp::min(lowlinks[node].unwrap(), lowlinks[succ].unwrap()));
                    }
                }

                DfsEvent::Post(node) => {
                    debug_assert!(indices[node].is_some());
                    debug_assert!(lowlinks[node].is_some());

                    // If this node's index is the same as its lowlink, then it
                    // is the root of a component. Pop this component's elements
                    // from the SCC stack and push them into our result data
                    // structures.
                    if indices[node] == lowlinks[node] {
                        let mut done = false;
                        components.push(extend_with_range(
                            &mut component_nodes,
                            iter::from_fn(|| {
                                if done {
                                    return None;
                                }
                                let v = stack.pop().unwrap();
                                let was_on_stack = on_stack.remove(v);
                                debug_assert!(was_on_stack);
                                if v == node {
                                    done = true;
                                }
                                Some(v)
                            }),
                        ));
                    }
                }
            }
        }

        Self {
            components,
            component_nodes,
        }
    }

    /// Get the number of components.
    pub fn len(&self) -> usize {
        self.components.len()
    }

    fn node_range(&self, range: Range<u32>) -> &[Node] {
        let start = usize::try_from(range.start).unwrap();
        let end = usize::try_from(range.end).unwrap();
        &self.component_nodes[start..end]
    }

    /// Iterate over each strongly-connnected component and the `Node`s that are
    /// members of it.
    ///
    /// Iteration happens in reverse-topological order (successors are visited
    /// before predecessors in the resulting SCC DAG).
    pub fn iter(&self) -> impl ExactSizeIterator<Item = (Scc, &[Node])> + '_ {
        self.components
            .iter()
            .map(|(component, range)| (component, self.node_range(range.clone())))
    }

    /// Iterate over each strongly-connected component.
    ///
    /// Iteration happens in reverse-topological order (successors are visited
    /// before predecessors in the resulting SCC DAG).
    pub fn keys(&self) -> impl ExactSizeIterator<Item = Scc> {
        self.components.keys()
    }

    /// Iterate over the `Node`s that make up each strongly-connected component.
    ///
    /// Iteration happens in reverse-topological order (successors are visited
    /// before predecessors in the resulting SCC DAG).
    #[cfg(test)]
    pub fn values(&self) -> impl ExactSizeIterator<Item = &[Node]> + '_ {
        self.components
            .values()
            .map(|range| self.node_range(range.clone()))
    }

    /// Get the `Node`s that make up the given strongly-connected component.
    pub fn nodes(&self, component: Scc) -> &[Node] {
        let range = self.components[component].clone();
        self.node_range(range)
    }

    /// Get this set of strongly-connected components' "evaporation".
    ///
    /// Given an input graph `G`, we can construct a new graph where the new
    /// graph's nodes are the strongly-connected components of `G` and there is
    /// an edge `scc(a) --> scc(b)` for every edge `a --> b` in the input graph
    /// `G` where `scc(a) != scc(b)` and `scc` is the function from a node to
    /// its strongly-connected component. This new graph is known as the
    /// "condensation" of `G`.
    ///
    /// In the following diagram, the solid lines are the input graph and the
    /// dotted lines show its condensation:
    ///
    /// ```text
    /// ...............
    /// :             :
    /// :    ,-----.  :
    /// :    |     |  :
    /// :    V     |  :
    /// :  +---+   |  :
    /// :  | a |---'  :
    /// :  +---+      :
    /// :    |        :
    /// :....|........:
    ///      |  :
    ///      |  :
    ///      |  :
    ///      |  V
    /// .....|..............       ....................
    /// :    |             :       :                  :
    /// :    V             :......>:                  :
    /// :  +---+    +---+  :       :  +---+    +---+  :
    /// :  | b |<-->| c |------------>| d |<-->| e |  :
    /// :  +---+    +---+  :       :  +---+    +---+  :
    /// :    |             :       :             |    :
    /// :....|.............:       :.............|....:
    ///      |  :                          :     |
    ///      |  :                          :     |
    ///      |  :                          :     |
    ///      |  V                          :     |
    /// .....|........................     :     |
    /// :    |                       :     :     |
    /// :    | ,----------------.    :     :     |
    /// :    | |                |    :<....:     |
    /// :    V |                V    :           |
    /// :   +---+    +---+    +---+  :           |
    /// :   | f |<---| g |<---| h |<-------------'
    /// :   +---+    +---+    +---+  :
    /// :                            :
    /// :............................:
    /// ```
    ///
    /// Note that a graph's condensation is always acyclic, because the
    /// strongly-conneted components encapsulate and hide any cycles from the
    /// input graph.
    ///
    /// I am not aware of an existing name for the reverse (or transpose)
    /// condensation, where each of the condensation's edges `a --> b` are
    /// flipped into `b --> a`, so, at cfallin's brilliant suggestion, I have
    /// decided to call it an "evaporation".
    ///
    /// In the context of a call graph, the condensation allows us to derive a
    /// partial dependency ordering for bottom-up inlining:
    ///
    /// * An edge `scc({a,b,...}) --> scc({c,d,...})` means that the functions
    ///   `{c,d,...}` should be processed for inlining before functions
    ///   `{a,b,...}`, since some functions in `{a,b,...}` call some functions
    ///   in `{c,d,...}` and we might want to inline these calls but only after
    ///   `{c,d,...}` have already had their calls inlined.
    ///
    /// * Functions within an SCC are unordered (and we probably don't want to
    ///   inline between them at all, or only want to do so in a very limited
    ///   manner, since their members are mutually recursive).
    ///
    /// A call graph's evaporation, by flipping edges from pointing to an SCC's
    /// dependencies to pointing to its dependers, allows us to answer the
    /// question "given that I've finished processing calls in `scc({e,f,...})`
    /// for inlining, which other SCCs are now potentially ready for
    /// processing?".
    pub fn evaporation<G>(&self, graph: G) -> Evaporation
    where
        G: Graph<Node>,
    {
        log::trace!("Creating the evaporation of {self:#?}");

        let node_to_component: SecondaryMap<Node, PackedOption<Scc>> = self
            .iter()
            .flat_map(|(c, nodes)| {
                nodes
                    .iter()
                    .copied()
                    .map(move |node| (node, PackedOption::from(Some(c))))
            })
            .collect();

        // Create a set of all reverse dependencies. This set contains an entry
        // `(to, from)` for all `from --> to` edges in the SCC's condensation.
        //
        // Note that we use a `BTreeSet` so that the results are ordered, all
        // edges `a --> *` are contiguous for each component `a`, and we can
        // therefore pack them densely in the resulting `Evaporation`.
        let mut reverse_edge_set = BTreeSet::<(Scc, Scc)>::new();
        for (from_component, nodes) in self.iter() {
            for node in nodes {
                for succ in graph.successors(*node) {
                    let to_component = node_to_component[succ].unwrap();
                    if to_component == from_component {
                        continue;
                    }
                    reverse_edge_set.insert((to_component, from_component));
                }
            }
        }

        // Convert the `reverse_edge_set` into our densely-packed
        // representation.
        let mut reverse_edges =
            SecondaryMap::<Scc, Range<u32>>::with_capacity(self.components.len());
        let mut reverse_edge_elems = Vec::with_capacity(reverse_edge_set.len());
        for (to_node, from_node) in reverse_edge_set {
            let range = extend_with_range(&mut reverse_edge_elems, Some(from_node));

            if reverse_edges[to_node] == Range::default() {
                reverse_edges[to_node] = range;
            } else {
                debug_assert_eq!(reverse_edges[to_node].end, range.start);
                reverse_edges[to_node].end = range.end;
            }
        }

        let result = Evaporation {
            reverse_edges,
            reverse_edge_elems,
        };
        log::trace!("  -> {result:#?}");
        result
    }
}

/// The "evaporation" of a graph and its strongly-connected components.
///
/// Created by `StronglyConnectedComponents::evaporation`; see that method's
/// documentation for more details.
pub struct Evaporation {
    reverse_edges: SecondaryMap<Scc, Range<u32>>,
    reverse_edge_elems: Vec<Scc>,
}

impl Debug for Evaporation {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        struct Map<'a>(&'a Evaporation);

        impl<'a> Debug for Map<'a> {
            fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
                f.debug_map()
                    .entries(
                        self.0
                            .reverse_edges
                            .keys()
                            .map(|k| (k, self.0.reverse_edges(k))),
                    )
                    .finish()
            }
        }

        f.debug_struct("Evaporation")
            .field("reverse_edges", &Map(self))
            .finish()
    }
}

impl Evaporation {
    /// Get the reverse dependencies of the given strongly-connected component.
    ///
    /// The result is all of the SCCs whose members have edges in the original
    /// graph to one or more of this SCC's members.
    pub fn reverse_edges(&self, component: Scc) -> &[Scc] {
        let Range { start, end } = self.reverse_edges[component].clone();
        let start = usize::try_from(start).unwrap();
        let end = usize::try_from(end).unwrap();
        &self.reverse_edge_elems[start..end]
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
    pub struct Node(u32);
    crate::entity_impl!(Node);

    #[derive(Debug)]
    struct Graph {
        edges: SecondaryMap<Node, Vec<Node>>,
    }

    impl Default for Graph {
        fn default() -> Self {
            let _ = env_logger::try_init();
            Self {
                edges: Default::default(),
            }
        }
    }

    impl Graph {
        fn define(&mut self, node: u32, edges: impl IntoIterator<Item = u32>) -> &mut Self {
            assert!(self.edges[Node::from_u32(node)].is_empty());
            self.edges[Node::from_u32(node)].extend(edges.into_iter().map(|v| Node::from_u32(v)));
            self
        }
    }

    impl super::Graph<Node> for Graph {
        type NodesIter<'a>
            = cranelift_entity::Keys<Node>
        where
            Self: 'a;

        fn nodes(&self) -> Self::NodesIter<'_> {
            self.edges.keys()
        }

        type SuccessorsIter<'a>
            = core::iter::Copied<core::slice::Iter<'a, Node>>
        where
            Self: 'a;

        fn successors(&self, node: Node) -> Self::SuccessorsIter<'_> {
            self.edges[node].iter().copied()
        }
    }

    fn components(graph: &Graph) -> Vec<Vec<u32>> {
        let components = StronglyConnectedComponents::new(graph);
        components
            .values()
            .map(|vs| vs.iter().map(|v| v.as_u32()).collect::<Vec<_>>())
            .collect()
    }

    #[test]
    fn test_empty() {
        let graph = Graph::default();
        assert!(components(&graph).is_empty());
    }

    #[test]
    fn test_single_node() {
        // +---+
        // | 0 |
        // +---+
        let mut graph = Graph::default();
        graph.define(0, []);

        assert_eq!(components(&graph), vec![vec![0]]);
    }

    #[test]
    fn test_single_node_cycle() {
        //   ,---.
        //   |   |
        //   V   |
        // +---+ |
        // | 0 |-'
        // +---+
        let mut graph = Graph::default();
        graph.define(0, [0]);

        assert_eq!(components(&graph), vec![vec![0]]);
    }

    #[test]
    fn test_disconnected_nodes() {
        // +---+     +---+
        // | 0 |     | 1 |
        // +---+     +---+
        let mut graph = Graph::default();
        graph.define(0, []);
        graph.define(1, []);
        assert_eq!(components(&graph), vec![vec![1], vec![0]]);
    }

    #[test]
    fn test_chained_nodes() {
        // +---+   +---+   +---+   +---+
        // | 0 |<--| 1 |<--| 2 |<--| 3 |
        // +---+   +---+   +---+   +---+
        let mut graph = Graph::default();
        graph.define(0, []);
        graph.define(1, [0]);
        graph.define(2, [1]);
        graph.define(3, [2]);
        assert_eq!(components(&graph), vec![vec![0], vec![1], vec![2], vec![3]]);
    }

    #[test]
    fn test_simple_multi_node_cycle() {
        //   ,-----------------------.
        //   |                       |
        //   |                       V
        // +---+   +---+   +---+   +---+
        // | 0 |<--| 1 |<--| 2 |<--| 3 |
        // +---+   +---+   +---+   +---+
        let mut graph = Graph::default();
        graph.define(0, [3]);
        graph.define(1, [0]);
        graph.define(2, [1]);
        graph.define(3, [2]);
        assert_eq!(components(&graph), vec![vec![0, 1, 2, 3]]);
    }

    #[test]
    fn test_complicated_multi_node_cycle() {
        //   ,---------------.
        //   |               |
        //   |               V
        // +---+   +---+   +---+   +---+   +---+
        // | 0 |<--| 1 |<--| 2 |<--| 3 |<--| 4 |
        // +---+   +---+   +---+   +---+   +---+
        //                   |               ^
        //                   |               |
        //                   `---------------'
        let mut graph = Graph::default();
        graph.define(0, [3]);
        graph.define(1, [0]);
        graph.define(2, [1, 4]);
        graph.define(3, [2]);
        graph.define(4, [3]);
        assert_eq!(components(&graph), vec![vec![0, 1, 2, 3, 4]]);
    }

    #[test]
    fn test_disconnected_cycles() {
        // +---+           +---+
        // | 0 |           | 1 |
        // +---+           +---+
        //   ^               ^
        //   |               |
        //   V               V
        // +---+           +---+
        // | 2 |           | 3 |
        // +---+           +---+
        let mut graph = Graph::default();
        graph.define(0, [2]);
        graph.define(1, [3]);
        graph.define(2, [0]);
        graph.define(3, [1]);
        assert_eq!(components(&graph), vec![vec![1, 3], vec![0, 2]]);
    }

    #[test]
    fn test_chain_of_cycles() {
        //   ,-----.
        //   |     |
        //   V     |
        // +---+   |
        // | 0 |---'
        // +---+
        //   |
        //   V
        // +---+    +---+
        // | 1 |<-->| 2 |
        // +---+    +---+
        //  |
        //  | ,----------------.
        //  | |                |
        //  V |                V
        // +---+    +---+    +---+
        // | 3 |<---| 4 |<---| 5 |
        // +---+    +---+    +---+
        let mut graph = Graph::default();
        graph.define(0, [0, 1]);
        graph.define(1, [2, 3]);
        graph.define(2, [1]);
        graph.define(3, [5]);
        graph.define(4, [3]);
        graph.define(5, [4]);
        assert_eq!(components(&graph), vec![vec![3, 4, 5], vec![1, 2], vec![0]]);
    }

    #[test]
    fn test_multiple_edges_to_same_component() {
        // +---+           +---+
        // | 0 |           | 1 |
        // +---+           +---+
        //   ^               ^
        //   |               |
        //   V               V
        // +---+           +---+
        // | 2 |           | 3 |
        // +---+           +---+
        //   |               |
        //   `------. ,------'
        //          | |
        //          V V
        //         +---+
        //         | 4 |
        //         +---+
        //           ^
        //           |
        //           V
        //         +---+
        //         | 5 |
        //         +---+
        let mut graph = Graph::default();
        graph.define(0, [2]);
        graph.define(1, [3]);
        graph.define(2, [0, 4]);
        graph.define(3, [1, 4]);
        graph.define(4, [5]);
        graph.define(5, [4]);
        assert_eq!(components(&graph), vec![vec![4, 5], vec![1, 3], vec![0, 2]]);
    }

    #[test]
    fn test_duplicate_edges() {
        // +---+           +---+
        // | 0 |           | 1 |
        // +---+           +---+
        //   ^               ^
        //   |               |
        //   V               V
        // +---+           +---+
        // | 2 |---------->| 3 |
        // +---+           +---+
        //   |               ^
        //   `---------------'
        let mut graph = Graph::default();
        graph.define(0, [2]);
        graph.define(1, [3]);
        graph.define(2, [0, 3, 3]);
        graph.define(3, [1]);
        assert_eq!(components(&graph), vec![vec![1, 3], vec![0, 2]]);
    }
}