autarkie 0.3.0

autarkie - instant grammar fuzzing using 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

use petgraph::graphmap::GraphMap;
use petgraph::visit::IntoNeighbors;
use petgraph::Directed;
use std::collections::HashSet;
use std::fmt::Debug;

/// Find cycles in type tree to find which types are recursive
pub fn find_cycles<N: Copy + Eq + std::hash::Hash + Ord + Debug, E>(
    graph: &GraphMap<N, E, Directed>,
) -> HashSet<Vec<N>> {
    let mut cycles = HashSet::new();
    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    let mut done = HashSet::new();
    for node in graph.nodes() {
        visited.drain();
        if !done.contains(&node) {
            dfs_cycle(graph, node, &mut visited, &mut stack, &mut cycles);
        }
        done.insert(node);
    }

    cycles
}

fn dfs_cycle<N: Copy + Eq + std::hash::Hash + Ord + Debug, E>(
    graph: &GraphMap<N, E, Directed>,
    node: N,
    visited: &mut HashSet<N>,
    stack: &mut Vec<N>,
    cycles: &mut HashSet<Vec<N>>,
) {
    visited.insert(node);
    stack.push(node);
    for neighbor in graph.neighbors(node) {
        if !visited.contains(&neighbor) {
            dfs_cycle(graph, neighbor, visited, stack, cycles);
        } else if stack.contains(&neighbor) {
            let cycle_start = stack.iter().position(|&x| x == neighbor).unwrap();
            let cycle = stack[cycle_start..].to_vec();
            cycles.insert(cycle);
        }
    }

    stack.pop();
}