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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

//! Property gates: CSR validation and normalization are panic-free and idempotent.
#![cfg(feature = "cpu-parity")]

use proptest::prelude::*;
use weir::graph_layout::CsrGraph;

fn build_valid_csr(node_count: u32, edges: &[(u32, u32, u32)]) -> (Vec<u32>, Vec<u32>, Vec<u32>) {
    let n = node_count as usize;
    if n == 0 {
        return (vec![0], Vec::new(), Vec::new());
    }
    let mut offsets = vec![0u32];
    let mut targets = Vec::new();
    let mut kinds = Vec::new();
    let mut per_row: Vec<Vec<(u32, u32)>> = vec![Vec::new(); n];
    for &(from, to, kind) in edges {
        if (from as usize) < n && (to as usize) < n {
            per_row[from as usize].push((to, kind));
        }
    }
    for row in &mut per_row {
        row.sort_unstable_by_key(|(t, _)| *t);
    }
    for row in per_row {
        for (t, k) in row {
            targets.push(t);
            kinds.push(k);
        }
        offsets.push(targets.len() as u32);
    }
    debug_assert_eq!(offsets.len(), n + 1);
    (offsets, targets, kinds)
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(128))]

    #[test]
    fn validate_accepts_well_formed_random_csr(
        node_count in 0u32..8,
        edges in proptest::collection::vec((0u32..8, 0u32..8, 1u32..4), 0..=16),
    ) {
        let node_count = node_count.min(7);
        let (offsets, targets, kinds) = build_valid_csr(node_count, &edges);
        let graph = CsrGraph::new(node_count, &offsets, &targets, &kinds);
        prop_assert!(graph.validate("proptest validate").is_ok());
    }

    #[test]
    fn normalize_is_idempotent_on_valid_csr(
        node_count in 1u32..6,
        edges in proptest::collection::vec((0u32..6, 0u32..6, 1u32..4), 0..=12),
    ) {
        let (offsets, targets, kinds) = build_valid_csr(node_count, &edges);
        let first = CsrGraph::new(node_count, &offsets, &targets, &kinds)
            .normalize("proptest normalize first")
            .expect("valid CSR must normalize");
        let second = CsrGraph::new(
            first.node_count(),
            first.edge_offsets(),
            first.edge_targets(),
            first.edge_kind_mask(),
        )
        .normalize("proptest normalize second")
        .expect("canonical CSR must re-normalize");
        prop_assert_eq!(first.stable_layout_hash(), second.stable_layout_hash());
        prop_assert_eq!(first.edge_targets(), second.edge_targets());
    }

    #[test]
    fn normalize_sorts_targets_per_row(
        node_count in 2u32..5,
        mut edges in proptest::collection::vec((0u32..4, 0u32..4, 1u32..4), 2..=8),
    ) {
        let node_count = node_count.min(4);
        for e in &mut edges {
            e.0 %= node_count;
            e.1 %= node_count;
        }
        let (offsets, targets, kinds) = build_valid_csr(node_count, &edges);
        let normalized = CsrGraph::new(node_count, &offsets, &targets, &kinds)
            .normalize("proptest sorted rows")
            .expect("normalize");
        let offs = normalized.edge_offsets();
        let tgts = normalized.edge_targets();
        for node in 0..node_count as usize {
            let start = offs[node] as usize;
            let end = offs[node + 1] as usize;
            for w in tgts[start..end].windows(2) {
                prop_assert!(w[0] < w[1], "normalized row must be strict-sorted unique");
            }
        }
    }

    #[test]
    fn validate_rejects_nonzero_first_offset(
        node_count in 1u32..4,
        tail in proptest::collection::vec(any::<u32>(), 1..=4),
    ) {
        let mut offsets = vec![1u32];
        offsets.extend(tail.iter().copied());
        while offsets.len() < (node_count as usize) + 1 {
            offsets.push(offsets.last().copied().unwrap_or(0));
        }
        let graph = CsrGraph::new(node_count, &offsets, &[], &[]);
        prop_assert!(graph.validate("proptest bad offset").is_err());
    }

    #[test]
    fn stable_hash_matches_normalized_layout(
        node_count in 1u32..5,
        edges in proptest::collection::vec((0u32..5, 0u32..5, 1u32..4), 1..=10),
    ) {
        let (offsets, targets, kinds) = build_valid_csr(node_count, &edges);
        let normalized = CsrGraph::new(node_count, &offsets, &targets, &kinds)
            .normalize("proptest hash")
            .expect("normalize");
        let direct = weir::graph_layout::stable_csr_layout_hash(
            normalized.node_count(),
            normalized.edge_count(),
            normalized.edge_offsets(),
            normalized.edge_targets(),
            normalized.edge_kind_mask(),
        );
        prop_assert_eq!(normalized.stable_layout_hash(), direct);
    }
}