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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//! Exploded-supergraph (IFDS encoding) substrate consumer.
//!
//! Wires `vyre_primitives::graph::exploded::build_cpu_reference` (zero
//! prior consumers) into the substrate so the optimizer can build
//! interprocedural-dataflow graphs directly. The IFDS encoding packs
//! `(proc_id, block_id, fact_id)` into a u32 node id, then composes
//! intra-/inter-procedural edges + GEN/KILL flow into a CSR ready for
//! reachability/closure analysis.
use vyre_primitives::graph::exploded::{build_cpu_reference, dense_to_encoded, encoded_to_dense};
/// Build an exploded supergraph and return its CSR `(row_ptr, col_idx)`.
/// Inputs match the underlying primitive's contract; the wrapper bumps
/// the dataflow-fixpoint observability counter so dispatch-time IFDS
/// graph builds are visible in dashboards.
#[must_use]
pub fn build_ifds_csr(
num_procs: u32,
blocks_per_proc: u32,
facts_per_proc: u32,
intra_edges: &[(u32, u32, u32)],
inter_edges: &[(u32, u32, u32, u32)],
flow_gen: &[(u32, u32, u32)],
flow_kill: &[(u32, u32, u32)],
) -> (Vec<u32>, Vec<u32>) {
use crate::observability::{bump, dataflow_fixpoint_calls};
bump(&dataflow_fixpoint_calls);
build_cpu_reference(
num_procs,
blocks_per_proc,
facts_per_proc,
intra_edges,
inter_edges,
flow_gen,
flow_kill,
)
}
/// Total node count of the exploded supergraph for the given
/// dimensions. Equivalent to `row_ptr.len() - 1` after the CSR is
/// built; useful when the caller needs to size frontier bitsets
/// before invoking [`build_ifds_csr`].
#[must_use]
pub fn ifds_node_count(num_procs: u32, blocks_per_proc: u32, facts_per_proc: u32) -> u32 {
num_procs
.saturating_mul(blocks_per_proc)
.saturating_mul(facts_per_proc)
}
/// Helper: round-trip a dense index through the packed encoding and
/// back. Used by callers that emit findings keyed on the packed id
/// but operate on dense indices internally.
#[must_use]
pub fn round_trip_dense(dense: u32, blocks_per_proc: u32, facts_per_proc: u32) -> Option<u32> {
let encoded = dense_to_encoded(dense, blocks_per_proc, facts_per_proc)?;
encoded_to_dense(encoded, blocks_per_proc, facts_per_proc)
}
#[cfg(test)]
mod tests {
use super::*;
/// Two procs, 2 blocks each, 2 facts each. One intra edge per
/// proc, no inter, no flow. The CSR row count must equal the
/// total node count.
#[test]
fn csr_row_count_matches_node_count() {
let (row_ptr, _) = build_ifds_csr(2, 2, 2, &[(0, 0, 1), (1, 0, 1)], &[], &[], &[]);
// Total = 2 * 2 * 2 = 8.
assert_eq!(row_ptr.len(), 9);
assert_eq!(ifds_node_count(2, 2, 2), 8);
}
/// Closure-bar: substrate output equals primitive output.
#[test]
fn matches_primitive_directly() {
let intra = vec![(0, 0, 1), (1, 0, 1)];
let inter = vec![(0, 1, 1, 0)];
let gen = vec![(0, 0, 1)];
let kill = vec![(1, 0, 0)];
let via_substrate = build_ifds_csr(2, 2, 2, &intra, &inter, &gen, &kill);
let via_primitive = build_cpu_reference(2, 2, 2, &intra, &inter, &gen, &kill);
assert_eq!(via_substrate, via_primitive);
}
/// Empty graph (no procs) is degenerate; CSR is `(vec![0], vec![])`.
/// Common bug: emit `vec![]` instead of `vec![0]` for row_ptr,
/// breaking downstream CSR walkers that assume `row_ptr[0] = 0`.
#[test]
fn empty_graph_yields_singleton_row_ptr() {
let (row_ptr, col_idx) = build_ifds_csr(0, 0, 0, &[], &[], &[], &[]);
assert_eq!(row_ptr, vec![0u32]);
assert!(col_idx.is_empty());
}
/// Adversarial: KILL must suppress fact propagation along an
/// intra edge. (proc 0, block 0, fact 1) is killed → no edge
/// emitted from (0, 0, 1) to (0, 1, 1).
#[test]
fn kill_suppresses_fact_propagation() {
let intra = vec![(0, 0, 1)];
let kill = vec![(0, 0, 1)];
let (row_ptr, col_idx) = build_ifds_csr(1, 2, 2, &intra, &[], &[], &kill);
// Node (0, 0, 1) is at dense index 0 * 4 + 0 * 2 + 1 = 1.
let src = 1usize;
let row_start = row_ptr[src] as usize;
let row_end = row_ptr[src + 1] as usize;
let neighbors = &col_idx[row_start..row_end];
// Should have NO edge to (0, 1, 1) (= dense 0*4 + 1*2 + 1 = 3).
assert!(!neighbors.contains(&3), "killed fact must not propagate");
}
/// Adversarial: GEN must inject the new fact along the intra
/// edge. (proc 0, block 0, gen fact 1) → edge from (0, 0, 0)
/// (the 0-fact) to (0, 1, 1).
#[test]
fn gen_injects_new_fact() {
let intra = vec![(0, 0, 1)];
let gen = vec![(0, 0, 1)];
let (row_ptr, col_idx) = build_ifds_csr(1, 2, 2, &intra, &[], &gen, &[]);
// 0-fact at (0, 0, 0) → dense index 0.
let row_start = row_ptr[0] as usize;
let row_end = row_ptr[1] as usize;
let neighbors = &col_idx[row_start..row_end];
// Edge to (0, 1, 1) → dense 3.
assert!(neighbors.contains(&3), "gen must emit edge to new fact");
}
/// Round-trip dense ↔ encoded must be identity for valid indices.
#[test]
fn round_trip_dense_is_identity() {
let blocks_per_proc = 4;
let facts_per_proc = 8;
for dense in 0..32 {
assert_eq!(
round_trip_dense(dense, blocks_per_proc, facts_per_proc),
Some(dense)
);
}
}
/// Adversarial: inter-procedural edge propagates EVERY fact
/// (IFDS upper bound). For 2 facts, expect 2 edges from
/// (sp, sb, *) to (dp, db, *).
#[test]
fn inter_edge_propagates_every_fact() {
let inter = vec![(0, 0, 1, 1)];
let (row_ptr, col_idx) = build_ifds_csr(2, 2, 2, &[], &inter, &[], &[]);
let dense_src_f0 = 0; // (0, 0, 0)
let dense_src_f1 = 1; // (0, 0, 1)
let row0 = &col_idx[row_ptr[dense_src_f0] as usize..row_ptr[dense_src_f0 + 1] as usize];
let row1 = &col_idx[row_ptr[dense_src_f1] as usize..row_ptr[dense_src_f1 + 1] as usize];
// (1, 1, 0) = 1*4 + 1*2 + 0 = 6
// (1, 1, 1) = 1*4 + 1*2 + 1 = 7
assert!(row0.contains(&6), "fact 0 must propagate via inter edge");
assert!(row1.contains(&7), "fact 1 must propagate via inter edge");
}
}