parsli 0.0.2

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

use std::collections::HashMap;

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

use crate::Task;

/// Graph with support for resolving dependencies
#[derive(Clone)]
pub struct DependencyGraph {
    inner: StableGraph<String, ()>,
    nodes: HashMap<String, NodeIndex>,
}

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

    /// Push a dependency to the graph
    pub fn push(&mut self, name: &str, dep: &str) {
        self.find_or_add_edge(name.to_string(), dep.to_string());
    }

    /// Pop the first node that has no dependencies
    pub fn pop(&mut self) -> Option<String> {
        if self.is_empty() { return None; }
        let weight = self.toposort().first().unwrap().clone();
        let node = self.find_or_add_node(weight.clone());
        // TODO: remove from hashmap
        self.inner.remove_node(node)
    }

    /// Check if there are no more nodes left
    pub fn is_empty(&self) -> bool {
        self.inner.node_count() == 0
    }

    /// Removes all nodes that are not depended on by the specified weights
    pub fn retain_dependencies(&mut self, weights: Vec<String>) {
        // 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));
    }

    /// 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()
        }).rev().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.dependencies {
                g.find_or_add_edge(d, t.name.clone());
            }
        }
        g
    }
}*/