vexcore 0.1.0

Core library for vexillo.
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

use std::collections::{HashMap, HashSet, VecDeque};

use syn::Ident;


/// Dependency Graph Node.
/// Contains a set of dependencies, and a set of
/// dependents, representing edges in a dependency
/// graph.
#[derive(Default)]
struct DepNode<'a> {
    dependencies: HashSet<&'a Ident>,
    dependents: HashSet<&'a Ident>,
}

pub struct DepGraph<'a> {
    nodes: HashMap<&'a Ident, HashSet<&'a Ident>>,
}

impl<'a> DepGraph<'a> {
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Self {
            nodes: HashMap::new(),
        }
    }
    
    pub fn insert<It: IntoIterator<Item = &'a Ident>>(&mut self, ident: &'a Ident, dependencies: It) {
        let node_mut = self.nodes.entry(ident).or_insert_with(HashSet::new);
        node_mut.extend(dependencies);
    }
    
    pub fn sort(&self) -> Result<Vec<&'a Ident>, ()> {
        // By this point, the dependency graph has only been built with
        // nodes that have their edges defined by dependencies, but not
        // dependents.
        // This topological sort algorithm depends on knowing a node's
        // dependencies AND dependents.
        // A new graph needs to be rebuilt, by stepping through the
        // pre-built graph and iterating over each node(N)'s dependencies,
        // and inserting node(n) into the dependency node's dependents set.
        let mut full_graph = HashMap::new();
        for (&key, dependencies) in self.nodes.iter() {
            full_graph.entry(key).or_insert_with(|| DepNode {
                dependencies: HashSet::with_capacity(dependencies.len()),
                dependents: HashSet::new(),
            }).dependencies.extend(dependencies.iter().copied());
            for dep in dependencies.iter().copied() {
                let dep_node = full_graph.entry(dep).or_insert_with(|| DepNode {
                    dependencies: HashSet::new(),
                    dependents: HashSet::new(),
                });
                dep_node.dependents.insert(key);
            }
        }
        let mut order = Vec::with_capacity(full_graph.len());
        let mut queue = VecDeque::with_capacity(full_graph.len());
        let mut in_degrees = HashMap::with_capacity(full_graph.len());
        let mut total_degrees = 0usize;
        for (&key, node) in full_graph.iter() {
            if node.dependencies.len() == 0 {
                queue.push_back(key);
            } else {
                let node_dep_count = node.dependencies.len();
                total_degrees += node_dep_count;
                in_degrees.insert(key, node_dep_count);
            }
        }
        
        while let Some(next_key) = queue.pop_front() {
            order.push(next_key);
            for dep_node in full_graph[next_key].dependents.iter().copied() {
                let Some(degrees) = in_degrees.get_mut(dep_node) else {
                    unreachable!("in_degrees should always be valid.");
                };
                *degrees -= 1;
                total_degrees -= 1;
                if *degrees == 0 {
                    queue.push_back(dep_node);
                }
            }
        }
        if total_degrees > 0 {
            return Err(());
        }
        Ok(order)
    }
}

#[test]
fn dep_graph_test() {
    let i: [Ident; 8] = [
        syn::parse_quote!(i0),
        syn::parse_quote!(i1),
        syn::parse_quote!(i2),
        syn::parse_quote!(i3),
        syn::parse_quote!(i4),
        syn::parse_quote!(i5),
        syn::parse_quote!(i6),
        syn::parse_quote!(i7),
    ];
    // macro_rules! name {
    //     ($name:ident) => {
    //         let $name: Ident = syn::parse_quote!($name);
    //     };
    // }
    let mut graph = DepGraph::new();
    graph.insert(&i[0], []);
    graph.insert(&i[1], []);
    graph.insert(&i[2], [&i[1]]);
    graph.insert(&i[3], [&i[2]]);
    graph.insert(&i[4], [&i[3]]);
    graph.insert(&i[5], [&i[4]]);
    graph.insert(&i[6], [&i[5]]);
    graph.insert(&i[7], [&i[6]]);
    if let Ok(sort) = graph.sort() {
        assert_eq!(sort.len(), 8);
        for node in sort {
            println!("{node}");
        }
    } else {
        panic!("Cycle detected.");
    }
}

/*
ident: additions: [ident], removals: [ident]
ident: mask

*/