weirflow 0.1.0

GPU-first dataflow analysis primitives for Vyre and Santh compiler pipelines.
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

//! Reusable CSR fixtures for Weir dataflow tests.

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

use rand::{Rng, SeedableRng};

#[derive(Clone, Debug)]
pub struct CsrGraphFixture {
    pub node_count: u32,
    pub edge_offsets: Vec<u32>,
    pub edge_targets: Vec<u32>,
    pub edge_kind_mask: Vec<u32>,
    pub expected_reachability: Vec<HashSet<u32>>,
}

pub struct CsrFactory;

impl CsrFactory {
    pub fn random_valid(node_count: u32, edge_probability: f64, seed: u64) -> CsrGraphFixture {
        let mut rng = rand::rngs::StdRng::seed_from_u64(seed);
        let probability = edge_probability.clamp(0.0, 1.0);
        let mut adjacency = vec![Vec::new(); node_count as usize];
        for src in 0..node_count {
            for dst in 0..node_count {
                if rng.random::<f64>() < probability {
                    adjacency[src as usize].push(dst);
                }
            }
            adjacency[src as usize].sort_unstable();
            adjacency[src as usize].dedup();
        }
        fixture_from_adjacency(adjacency)
    }

    pub fn adversarial_empty_rows() -> CsrGraphFixture {
        fixture_from_adjacency(vec![vec![1], Vec::new(), vec![0]])
    }

    pub fn adversarial_non_monotonic_offsets() -> CsrGraphFixture {
        CsrGraphFixture {
            node_count: 3,
            edge_offsets: vec![0, 2, 1, 3],
            edge_targets: vec![1, 2, 0],
            edge_kind_mask: vec![u32::MAX; 3],
            expected_reachability: Vec::new(),
        }
    }

    pub fn adversarial_oob_targets() -> CsrGraphFixture {
        CsrGraphFixture {
            node_count: 3,
            edge_offsets: vec![0, 1, 2, 3],
            edge_targets: vec![1, 99, 0],
            edge_kind_mask: vec![u32::MAX; 3],
            expected_reachability: Vec::new(),
        }
    }

    pub fn adversarial_terminal_mismatch() -> CsrGraphFixture {
        CsrGraphFixture {
            node_count: 3,
            edge_offsets: vec![0, 1, 2, 4],
            edge_targets: vec![1, 2, 0],
            edge_kind_mask: vec![u32::MAX; 3],
            expected_reachability: Vec::new(),
        }
    }
}

fn fixture_from_adjacency(adjacency: Vec<Vec<u32>>) -> CsrGraphFixture {
    let node_count = adjacency.len() as u32;
    let mut edge_offsets = Vec::with_capacity(adjacency.len() + 1);
    let mut edge_targets = Vec::new();
    edge_offsets.push(0);
    for targets in &adjacency {
        edge_targets.extend(targets.iter().copied());
        edge_offsets.push(edge_targets.len() as u32);
    }
    let edge_kind_mask = vec![u32::MAX; edge_targets.len()];
    let expected_reachability = reachability_sets(&adjacency);
    CsrGraphFixture {
        node_count,
        edge_offsets,
        edge_targets,
        edge_kind_mask,
        expected_reachability,
    }
}

fn reachability_sets(adjacency: &[Vec<u32>]) -> Vec<HashSet<u32>> {
    let mut out = Vec::with_capacity(adjacency.len());
    for start in 0..adjacency.len() as u32 {
        let mut seen = HashSet::new();
        let mut queue = VecDeque::new();
        seen.insert(start);
        queue.push_back(start);
        while let Some(node) = queue.pop_front() {
            let Some(targets) = adjacency.get(node as usize) else {
                continue;
            };
            for &target in targets {
                if (target as usize) < adjacency.len() && seen.insert(target) {
                    queue.push_back(target);
                }
            }
        }
        out.push(seen);
    }
    out
}