parsli 0.0.1

Parallel status lines for Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

use std::collections::HashMap;

use petgraph::algo::toposort;
use petgraph::dot::{Config, Dot};
use petgraph::Graph;
use petgraph::graph::{EdgeIndex, Node, NodeIndex};
use petgraph::visit::{Control, depth_first_search, DfsEvent, Visitable, VisitMap};

use crate::task::Task;

#[derive(Clone)]
pub struct DependencyGraph {
    inner: Graph<String, ()>,
    nodes: HashMap<String, NodeIndex>,
}

impl DependencyGraph {
    pub fn new() -> Self {
        Self { inner: Default::default(), nodes: Default::default() }
    }

    /// Removes all nodes that are not depended on by the specified weights
    pub fn retain_dependencies(&mut self, weights: Vec<String>) {
        // Make reverse dependency graph
        self.inner.reverse();
        // Traverse tree to find required nodes
        let mut vm = self.inner.visit_map();
        for w in weights {
            let node = self.find_or_add_node(w);
            depth_first_search(&self.inner, Some(node), |event| {
                if let DfsEvent::Discover(n, _time) = event {
                    if vm.is_visited(&n) { return Control::<NodeIndex>::Prune }
                    vm.visit(n);
                }
                Control::<NodeIndex>::Continue
            });
        }
        // Remove unvisited nodes
        self.inner.retain_nodes(|_fg, n| vm.is_visited(&n));
        // Undo reverse dependency graph
        self.inner.reverse();
    }

    /// Return a vector with topologically sorted weights
    pub fn toposort(&self) -> Vec<String> {
        toposort(&self.inner, None).unwrap().iter().map(|n| {
            self.inner.node_weight(*n).unwrap().clone()
        }).collect()
    }

    /// Add a node from a weight or return the existing one
    fn find_or_add_node(&mut self, weight: String) -> NodeIndex {
        let entry = self.nodes.entry(weight.clone());
        *entry.or_insert_with(|| self.inner.add_node(weight))
    }

    /// Add an edge from two weights or return the existing one
    fn find_or_add_edge(&mut self, weight0: String, weight1: String) -> EdgeIndex {
        let node0 = self.find_or_add_node(weight0);
        let node1 = self.find_or_add_node(weight1);
        self.inner.find_edge(node0, node1).unwrap_or_else(|| self.inner.add_edge(node0, node1, ()))
    }
}

impl ToString for DependencyGraph {
    /// Render this graph to a dot representation
    fn to_string(&self) -> String {
        format!("{:?}", Dot::with_config(&self.inner, &[Config::EdgeNoLabel]))
    }
}

impl From<Vec<Task>> for DependencyGraph {
    /// Convert the tasks to a dependency graph
    fn from(mut tasks: Vec<Task>) -> Self {
        let mut g = Self::new();
        for t in tasks.drain(..) {
            for d in t.deps {
                g.find_or_add_edge(d, t.name.clone());
            }
        }
        g
    }
}