crepe 0.2.0

Datalog in Rust as a procedural macro
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

//! Handles stratification of Datalog programs

use petgraph::{algo, graphmap::DiGraphMap};
use std::collections::{HashMap, HashSet};
use std::slice::Iter;
use syn::Ident;

pub struct Strata {
    list: Vec<Vec<Ident>>,
    index: HashMap<Ident, usize>,
}

impl Strata {
    pub fn new(relations: HashSet<Ident>, dependencies: HashSet<(&Ident, &Ident)>) -> Self {
        let mut graph = DiGraphMap::new();
        for ident in relations.iter() {
            graph.add_node(ident);
        }
        for edge in dependencies {
            graph.add_edge(edge.0, edge.1, ());
        }

        // Strongly connected components, as a vector of vectors of `&Ident`s.
        //
        // These are given in reverse topological order, which is our intended
        // order of evaluation (dependencies before dependents).
        let scc = algo::kosaraju_scc(&graph);

        let mut list = Vec::new();
        let mut index = HashMap::new();
        for (i, stratum) in scc.into_iter().enumerate() {
            let mut current = Vec::new();
            for ident in stratum {
                index.insert(ident.clone(), i);
                current.push(ident.clone());
            }
            list.push(current);
        }

        Self { list, index }
    }

    pub fn iter(&self) -> Iter<'_, Vec<Ident>> {
        self.list.iter()
    }

    pub fn find_relation(&self, rel: &Ident) -> usize {
        *self.index.get(rel).expect("key not found in stratum index")
    }
}