src/devices/lib/bind/src/dependency_graph.rs

// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

use std::collections::{HashMap, HashSet};
use std::fmt::Debug;
use std::hash::Hash;
use std::mem;

pub struct DependencyGraph<K: Eq + Hash, V> {
    // Storage for all nodes in the graph.
    nodes: Vec<Node<K, V>>,

    // Maps keys to the corresponding index in |nodes|.
    indices: HashMap<K, usize>,

    // Maps nodes to their children using an index into |nodes|.
    children: HashMap<usize, HashSet<usize>>,

    // Maps nodes to their parents using an index into |nodes|.
    parents: HashMap<usize, HashSet<usize>>,
}

enum Node<K, V> {
    // The root node has no data or key.
    Root,

    // Data nodes have a key and a value.
    Data(K, V),

    // Zombie nodes have been removed from the graph. This is used to avoid index updates to the
    // graph's storage vector when removing a node.
    Zombie,
}

#[derive(Debug, Clone, PartialEq)]
pub enum DependencyError<K: Clone + Debug + PartialEq> {
    MissingDependency(K),
    CircularDependency,
}

impl<K: Eq + Hash + Clone + Debug, V> DependencyGraph<K, V> {
    const ROOT_INDEX: usize = 0;

    /// Constructs a dependency graph and populates it with a root node.
    pub fn new() -> DependencyGraph<K, V> {
        Self {
            nodes: vec![Node::Root],
            indices: HashMap::new(),
            children: HashMap::new(),
            parents: HashMap::new(),
        }
    }

    /// Insert a node into the graph with |key| and attach |data| to the node.
    ///
    /// If the node already exists, it is replaced.
    pub fn insert_node(&mut self, key: K, data: V) {
        let index = self.nodes.len();
        self.nodes.push(Node::Data(key.clone(), data));
        if let Some(previous) = self.indices.insert(key, index) {
            self.nodes[previous] = Node::Zombie;
        }
    }

    /// Inserts an edge from the root of the graph to the node with key |to|.
    ///
    /// If |to| doesn't exist in the graph, return a MissingDependency error.
    pub fn insert_edge_from_root(&mut self, to: &K) -> Result<(), DependencyError<K>> {
        let to_index = self.get_index(to)?;
        self.children.entry(Self::ROOT_INDEX).or_insert(HashSet::new()).insert(to_index);
        self.parents.entry(to_index).or_insert(HashSet::new()).insert(Self::ROOT_INDEX);
        Ok(())
    }

    /// Inserts an edge from the root of the graph from the node with key |from| to the node with
    /// key |to|.
    ///
    /// If either |from| or |to| doesn't exist in the graph, return a MissingDependency error.
    pub fn insert_edge(&mut self, from: &K, to: &K) -> Result<(), DependencyError<K>> {
        let from_index = self.get_index(from)?;
        let to_index = self.get_index(to)?;
        self.children.entry(from_index).or_insert(HashSet::new()).insert(to_index);
        self.parents.entry(to_index).or_insert(HashSet::new()).insert(from_index);
        Ok(())
    }

    /// Resolve the dependency graph, returning the data associated with each node in a path from
    /// the root node to its dependencies. For each node in the path all of its dependencies must
    /// appear after its position in the path. Any node that has no dependency chain from the root
    /// is pruned from the path.
    ///
    /// If no such path is possible return a CircularDependency error.
    pub fn resolve(mut self) -> Result<Vec<V>, DependencyError<K>> {
        // This is a minor variation on Kahn's algorithm. We do not start by finding all nodes with
        // no incoming edges because we know that the root node has no incoming edges, and that all
        // other such nodes will be pruned.
        self.prune_orphans()?;

        let mut result = vec![];
        let mut next_indices = vec![Self::ROOT_INDEX];
        while let Some(index) = next_indices.pop() {
            if let Some(data) = self.remove(index) {
                result.push(data);
            }

            for child_index in self.children.entry(index).or_default().clone() {
                self.remove_edge(index, child_index)?;
                if self.is_orphaned(&self.nodes[child_index]) {
                    next_indices.push(child_index);
                }
            }
        }
        if self.is_empty() {
            Ok(result)
        } else {
            Err(DependencyError::CircularDependency)
        }
    }
}

impl<K: Eq + Hash + Clone + Debug, V> DependencyGraph<K, V> {
    fn get_index(&self, key: &K) -> Result<usize, DependencyError<K>> {
        let index = self.indices.get(key).ok_or(DependencyError::MissingDependency(key.clone()))?;
        Ok(*index)
    }

    fn remove_edge(
        &mut self,
        from_index: usize,
        to_index: usize,
    ) -> Result<(), DependencyError<K>> {
        let to_parents =
            self.parents.get_mut(&to_index).expect("remove_edge called with invalid to_index");
        to_parents.remove(&from_index);
        let from_children =
            self.children.get_mut(&from_index).expect("remove_edge called with invalid from_index");
        from_children.remove(&to_index);
        Ok(())
    }

    fn is_orphaned(&self, node: &Node<K, V>) -> bool {
        match node {
            Node::Data(key, _) => {
                let index = self.indices.get(key).expect("Key exists in node but not in graph");
                self.parents.get(index).map(|vs| vs.is_empty()).unwrap_or(true)
            }
            Node::Root => false,
            Node::Zombie => false,
        }
    }

    fn remove(&mut self, index: usize) -> Option<V> {
        // Pull out the node while maintaining all the other indices.
        match mem::replace(&mut self.nodes[index], Node::Zombie) {
            Node::Data(_, data) => Some(data),
            _ => None,
        }
    }

    // Prune all orphaned nodes (nodes with no parents). This removes nodes that have no path from
    // the root node.
    fn prune_orphans(&mut self) -> Result<(), DependencyError<K>> {
        while let Some((index, _)) =
            self.nodes.iter().enumerate().find(|(_, node)| self.is_orphaned(node))
        {
            self.remove(index);

            // Remove child edges.
            let child_indices = self.children.entry(index).or_default().clone();
            for child_index in child_indices {
                self.remove_edge(index, child_index)?;
            }
        }

        Ok(())
    }

    fn is_empty(&self) -> bool {
        self.children.values().all(|xs| xs.is_empty())
            && self.parents.values().all(|xs| xs.is_empty())
    }
}

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

    #[test]
    fn simple() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(2, "two");
        graph.insert_node(3, "three");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
        assert_eq!(graph.insert_edge(&2, &3), Ok(()));

        assert_eq!(graph.resolve(), Ok(vec!["one", "two", "three",]));
    }

    #[test]
    fn empty() {
        let graph: DependencyGraph<usize, usize> = DependencyGraph::new();
        assert!(graph.resolve().unwrap().is_empty());
    }

    #[test]
    fn insert_replaces() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(1, "two");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));

        assert_eq!(graph.resolve(), Ok(vec!["two"]));
    }

    #[test]
    fn branching_edges_from_root() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(2, "two");
        graph.insert_node(3, "three");
        graph.insert_node(4, "four");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));
        assert_eq!(graph.insert_edge_from_root(&2), Ok(()));

        assert_eq!(graph.insert_edge(&1, &3), Ok(()));
        assert_eq!(graph.insert_edge(&2, &4), Ok(()));

        let result = graph.resolve().unwrap();
        assert!(result.contains(&"one"));
        assert!(result.contains(&"two"));
        assert!(result.contains(&"three"));
        assert!(result.contains(&"four"));
        assert!(
            result.iter().position(|&x| x == "one") < result.iter().position(|&x| x == "three")
        );
        assert!(result.iter().position(|&x| x == "two") < result.iter().position(|&x| x == "four"));
    }

    #[test]
    fn branching_edges() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(2, "two");
        graph.insert_node(3, "three");
        graph.insert_node(4, "four");
        graph.insert_node(5, "five");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));

        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
        assert_eq!(graph.insert_edge(&2, &3), Ok(()));

        assert_eq!(graph.insert_edge(&1, &4), Ok(()));
        assert_eq!(graph.insert_edge(&4, &5), Ok(()));

        let result = graph.resolve().unwrap();
        assert!(result.contains(&"one"));
        assert!(result.contains(&"two"));
        assert!(result.contains(&"three"));
        assert!(result.contains(&"four"));
        assert!(result.contains(&"five"));
        assert_eq!(result[0], "one");
        assert!(
            result.iter().position(|&x| x == "two") < result.iter().position(|&x| x == "three")
        );
        assert!(
            result.iter().position(|&x| x == "four") < result.iter().position(|&x| x == "five")
        );
    }

    #[test]
    fn multiple_incoming_edges() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(2, "two");
        graph.insert_node(3, "three");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));

        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
        assert_eq!(graph.insert_edge(&1, &3), Ok(()));
        assert_eq!(graph.insert_edge(&2, &3), Ok(()));

        assert_eq!(graph.resolve(), Ok(vec!["one", "two", "three",]));
    }

    #[test]
    fn prunes_disconnected_graph() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(2, "two");
        graph.insert_node(3, "three");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));

        assert_eq!(graph.insert_edge(&2, &3), Ok(()));

        assert_eq!(graph.resolve(), Ok(vec!["one"]));
    }

    #[test]
    fn circular_dependency() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");
        graph.insert_node(2, "two");
        graph.insert_node(3, "three");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));

        assert_eq!(graph.insert_edge(&1, &2), Ok(()));
        assert_eq!(graph.insert_edge(&2, &3), Ok(()));
        assert_eq!(graph.insert_edge(&3, &1), Ok(()));

        assert_eq!(graph.resolve(), Err(DependencyError::CircularDependency));
    }

    #[test]
    fn missing_root_dependency() {
        let mut graph: DependencyGraph<usize, usize> = DependencyGraph::new();

        assert_eq!(graph.insert_edge_from_root(&1), Err(DependencyError::MissingDependency(1)));
    }

    #[test]
    fn missing_dependency() {
        let mut graph = DependencyGraph::new();

        graph.insert_node(1, "one");

        assert_eq!(graph.insert_edge_from_root(&1), Ok(()));

        assert_eq!(graph.insert_edge(&1, &2), Err(DependencyError::MissingDependency(2)));
        assert_eq!(graph.insert_edge(&2, &1), Err(DependencyError::MissingDependency(2)));
    }
}