use super::*;
#[test]
fn fixed_point_forward_graph_packs_invariant_buffers_once() {
let graph = FixedPointForwardGraph::new(
"fixed_point_forward_graph_test",
2,
&[0, 1, 1],
&[1],
&[vyre_primitives::predicate::edge_kind::CONTROL],
)
.expect("valid graph must pack");
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
assert!(graph.retained_bytes() >= 28);
}
#[test]
fn fixed_point_forward_graph_construction_uses_single_in_place_packing_boundary() {
let source = include_str!("../graph.rs");
assert!(
!source.contains("pack_u32(normalized_graph")
&& !source.contains("pack_repeated_u32(0, nodes)"),
"Fix: initial fixed-point graph construction must use the same in-place packing boundary as replacement so buffer-packing optimizations land once."
);
}
#[test]
fn fixed_point_forward_graph_replace_reuses_packed_buffer_allocations() {
let mut graph = FixedPointForwardGraph::new(
"fixed_point_forward_graph_replace_test",
4,
&[0, 2, 3, 3, 3],
&[1, 2, 3],
&[
vyre_primitives::predicate::edge_kind::CONTROL,
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
vyre_primitives::predicate::edge_kind::CONTROL,
],
)
.expect("initial graph must pack");
let pg_nodes_ptr = graph.pg_nodes_bytes.as_ptr() as usize;
let edge_offsets_ptr = graph.edge_offsets_bytes.as_ptr() as usize;
let edge_targets_ptr = graph.edge_targets_bytes.as_ptr() as usize;
let edge_kind_ptr = graph.edge_kind_mask_bytes.as_ptr() as usize;
let pg_tags_ptr = graph.pg_node_tags_bytes.as_ptr() as usize;
let normalized_offsets_capacity = graph.normalized_graph.edge_offsets_capacity();
let normalized_targets_capacity = graph.normalized_graph.edge_targets_capacity();
let normalized_masks_capacity = graph.normalized_graph.edge_kind_mask_capacity();
let normalized_row_capacity = graph.normalization_scratch.row_capacity();
let retained = graph.retained_bytes();
let original_hash = graph.stable_layout_hash();
graph
.replace(
"fixed_point_forward_graph_replace_test",
4,
&[0, 1, 1, 2, 2],
&[2, 3],
&[
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
vyre_primitives::predicate::edge_kind::CONTROL,
],
)
.expect("replacement graph must repack into retained buffers");
assert_eq!(graph.node_count(), 4);
assert_eq!(graph.edge_count(), 2);
assert_ne!(graph.stable_layout_hash(), original_hash);
assert_eq!(graph.pg_nodes_bytes.as_ptr() as usize, pg_nodes_ptr);
assert_eq!(graph.edge_offsets_bytes.as_ptr() as usize, edge_offsets_ptr);
assert_eq!(graph.edge_targets_bytes.as_ptr() as usize, edge_targets_ptr);
assert_eq!(graph.edge_kind_mask_bytes.as_ptr() as usize, edge_kind_ptr);
assert_eq!(graph.pg_node_tags_bytes.as_ptr() as usize, pg_tags_ptr);
assert!(graph.normalized_graph.edge_offsets_capacity() >= normalized_offsets_capacity);
assert!(graph.normalized_graph.edge_targets_capacity() >= normalized_targets_capacity);
assert!(graph.normalized_graph.edge_kind_mask_capacity() >= normalized_masks_capacity);
assert!(graph.normalization_scratch.row_capacity() >= normalized_row_capacity);
assert_eq!(graph.retained_bytes(), retained);
}
#[test]
fn fixed_point_forward_graph_normalizes_equivalent_rows_for_cache_hits() {
let unsorted_with_duplicate = FixedPointForwardGraph::new(
"fixed_point_forward_graph_normalize_test",
3,
&[0, 3, 4, 4],
&[2, 1, 1, 2],
&[
vyre_primitives::predicate::edge_kind::CONTROL,
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
vyre_primitives::predicate::edge_kind::CONTROL,
],
)
.expect("valid unsorted graph must normalize");
let already_canonical = FixedPointForwardGraph::new(
"fixed_point_forward_graph_normalize_test",
3,
&[0, 2, 3, 3],
&[1, 2, 2],
&[
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
vyre_primitives::predicate::edge_kind::CONTROL,
vyre_primitives::predicate::edge_kind::CONTROL,
],
)
.expect("valid canonical graph must pack");
assert_eq!(unsorted_with_duplicate.edge_count(), 3);
assert_eq!(
unsorted_with_duplicate.edge_offsets_bytes,
already_canonical.edge_offsets_bytes
);
assert_eq!(
unsorted_with_duplicate.edge_targets_bytes,
already_canonical.edge_targets_bytes
);
assert_eq!(
unsorted_with_duplicate.edge_kind_mask_bytes,
already_canonical.edge_kind_mask_bytes
);
assert_eq!(
unsorted_with_duplicate.stable_layout_hash(),
already_canonical.stable_layout_hash()
);
}
#[test]
fn fixed_point_forward_graph_masks_edge_kinds_while_reusing_buffers() {
let mut graph = FixedPointForwardGraph::new_with_edge_kind_mask(
"fixed_point_forward_graph_masked_test",
2,
&[0, 1, 1],
&[1],
&[vyre_primitives::predicate::edge_kind::CONTROL
| vyre_primitives::predicate::edge_kind::ASSIGNMENT],
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
)
.expect("initial masked graph must pack");
let edge_kind_ptr = graph.edge_kind_mask_bytes.as_ptr() as usize;
let retained = graph.retained_bytes();
graph
.replace_with_edge_kind_mask(
"fixed_point_forward_graph_masked_test",
2,
&[0, 1, 1],
&[1],
&[vyre_primitives::predicate::edge_kind::DOMINANCE],
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
)
.expect("replacement masked graph must repack into retained buffers");
assert_eq!(graph.edge_count(), 0);
assert_eq!(graph.edge_kind_mask_bytes.as_ptr() as usize, edge_kind_ptr);
assert_eq!(graph.retained_bytes(), retained);
assert!(graph.edge_kind_mask_bytes.is_empty());
assert_eq!(
graph.edge_offsets_bytes,
vyre_primitives::wire::pack_u32_slice(&[0u32, 0, 0])
);
}
#[test]
fn fixed_point_masked_graph_drops_dead_edges_for_stable_cache_identity() {
let with_dead_edges = FixedPointForwardGraph::new_with_edge_kind_mask(
"fixed_point_masked_dead_edges_cache_identity_test",
3,
&[0, 2, 3, 3],
&[1, 2, 2],
&[
vyre_primitives::predicate::edge_kind::CONTROL,
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
vyre_primitives::predicate::edge_kind::CONTROL,
],
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
)
.expect("masked graph with dead edges must pack");
let already_filtered = FixedPointForwardGraph::new_with_edge_kind_mask(
"fixed_point_masked_dead_edges_cache_identity_test",
3,
&[0, 1, 1, 1],
&[2],
&[vyre_primitives::predicate::edge_kind::ASSIGNMENT],
vyre_primitives::predicate::edge_kind::ASSIGNMENT,
)
.expect("already-filtered graph must pack");
assert_eq!(with_dead_edges.edge_count(), 1);
assert_eq!(
with_dead_edges.stable_layout_hash(),
already_filtered.stable_layout_hash()
);
}
#[test]
fn fixed_point_forward_graph_hash_is_cached_and_shared_layout_based() {
let graph = FixedPointForwardGraph::new(
"fixed_point_forward_graph_cached_hash_test",
2,
&[0, 1, 1],
&[1],
&[vyre_primitives::predicate::edge_kind::CONTROL],
)
.expect("valid graph must pack");
assert_eq!(
graph.stable_layout_hash(),
crate::graph_layout::stable_csr_layout_hash(
graph.node_count(),
graph.edge_count(),
&[0, 1, 1],
&[1],
&[vyre_primitives::predicate::edge_kind::CONTROL],
)
);
}
#[test]
fn generated_fixed_point_graph_packing_matches_independent_csr_canonicalization() {
for case in 0..4096u32 {
let (node_count, edge_offsets, edge_targets, edge_kind_mask) = generated_csr_case(case);
let graph = FixedPointForwardGraph::new(
"generated_fixed_point_graph_canonicalization_matrix",
node_count,
&edge_offsets,
&edge_targets,
&edge_kind_mask,
)
.unwrap_or_else(|error| panic!("case {case} unmasked graph rejected: {error}"));
let expected = independent_canonical_csr(
node_count,
&edge_offsets,
&edge_targets,
&edge_kind_mask,
None,
);
assert_packed_graph_matches(case, &graph, &expected);
let allowed_mask = generated_allowed_mask(case);
let masked = FixedPointForwardGraph::new_with_edge_kind_mask(
"generated_fixed_point_graph_masked_canonicalization_matrix",
node_count,
&edge_offsets,
&edge_targets,
&edge_kind_mask,
allowed_mask,
)
.unwrap_or_else(|error| panic!("case {case} masked graph rejected: {error}"));
let expected_masked = independent_canonical_csr(
node_count,
&edge_offsets,
&edge_targets,
&edge_kind_mask,
Some(allowed_mask),
);
assert_packed_graph_matches(case, &masked, &expected_masked);
}
}
fn generated_csr_case(case: u32) -> (u32, Vec<u32>, Vec<u32>, Vec<u32>) {
let node_count = 1 + (case % 19);
let mut state = case.wrapping_mul(0x9E37_79B9).wrapping_add(0xA5A5_5A5A);
let mut offsets = Vec::with_capacity(node_count as usize + 1);
let mut targets = Vec::new();
let mut masks = Vec::new();
offsets.push(0);
for node in 0..node_count {
state = mix_u32(state ^ node.rotate_left(7));
let row_len = (state % 7) as usize;
let mut previous_target = node % node_count;
for edge_index in 0..row_len {
state = mix_u32(state.wrapping_add((edge_index as u32 + 1) * 0x45D9_F3B));
let duplicate_previous = edge_index != 0 && (state & 0b11) == 0;
let target = if duplicate_previous {
previous_target
} else {
state.rotate_left((edge_index as u32) & 15) % node_count
};
previous_target = target;
targets.push(target);
masks.push(generated_edge_mask(state ^ node ^ edge_index as u32));
}
offsets.push(targets.len() as u32);
}
(node_count, offsets, targets, masks)
}
fn generated_edge_mask(seed: u32) -> u32 {
match seed % 7 {
0 => vyre_primitives::predicate::edge_kind::CONTROL,
1 => vyre_primitives::predicate::edge_kind::ASSIGNMENT,
2 => vyre_primitives::predicate::edge_kind::DOMINANCE,
3 => {
vyre_primitives::predicate::edge_kind::CONTROL
| vyre_primitives::predicate::edge_kind::ASSIGNMENT
}
4 => {
vyre_primitives::predicate::edge_kind::ASSIGNMENT
| vyre_primitives::predicate::edge_kind::DOMINANCE
}
5 => {
vyre_primitives::predicate::edge_kind::CONTROL
| vyre_primitives::predicate::edge_kind::DOMINANCE
}
_ => {
vyre_primitives::predicate::edge_kind::CONTROL
| vyre_primitives::predicate::edge_kind::ASSIGNMENT
| vyre_primitives::predicate::edge_kind::DOMINANCE
}
}
}
fn generated_allowed_mask(case: u32) -> u32 {
match case % 6 {
0 => vyre_primitives::predicate::edge_kind::CONTROL,
1 => vyre_primitives::predicate::edge_kind::ASSIGNMENT,
2 => vyre_primitives::predicate::edge_kind::DOMINANCE,
3 => {
vyre_primitives::predicate::edge_kind::CONTROL
| vyre_primitives::predicate::edge_kind::ASSIGNMENT
}
4 => {
vyre_primitives::predicate::edge_kind::ASSIGNMENT
| vyre_primitives::predicate::edge_kind::DOMINANCE
}
_ => {
vyre_primitives::predicate::edge_kind::CONTROL
| vyre_primitives::predicate::edge_kind::ASSIGNMENT
| vyre_primitives::predicate::edge_kind::DOMINANCE
}
}
}
fn independent_canonical_csr(
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
allowed_mask: Option<u32>,
) -> (Vec<u32>, Vec<u32>, Vec<u32>) {
let mut offsets = Vec::with_capacity(node_count as usize + 1);
let mut targets = Vec::new();
let mut masks = Vec::new();
offsets.push(0);
for node in 0..node_count as usize {
let start = edge_offsets[node] as usize;
let end = edge_offsets[node + 1] as usize;
let mut row = std::collections::BTreeMap::<u32, u32>::new();
for index in start..end {
let mapped =
allowed_mask.map_or(edge_kind_mask[index], |mask| edge_kind_mask[index] & mask);
if mapped == 0 {
continue;
}
row.entry(edge_targets[index])
.and_modify(|existing| *existing |= mapped)
.or_insert(mapped);
}
targets.extend(row.keys().copied());
masks.extend(row.values().copied());
offsets.push(targets.len() as u32);
}
(offsets, targets, masks)
}
fn assert_packed_graph_matches(
case: u32,
graph: &FixedPointForwardGraph,
expected: &(Vec<u32>, Vec<u32>, Vec<u32>),
) {
let (expected_offsets, expected_targets, expected_masks) = expected;
assert_eq!(
graph.node_count(),
expected_offsets.len() as u32 - 1,
"case {case} node count drifted"
);
assert_eq!(
graph.edge_count(),
expected_targets.len() as u32,
"case {case} edge count drifted"
);
assert_eq!(
unpack_u32_words(&graph.edge_offsets_bytes),
*expected_offsets,
"case {case} packed offsets drifted"
);
assert_eq!(
unpack_u32_words(&graph.edge_targets_bytes),
*expected_targets,
"case {case} packed targets drifted"
);
assert_eq!(
unpack_u32_words(&graph.edge_kind_mask_bytes),
*expected_masks,
"case {case} packed edge-kind masks drifted"
);
assert_eq!(
unpack_u32_words(&graph.pg_nodes_bytes),
vec![0u32; graph.node_count() as usize],
"case {case} packed ProgramGraph node slots must stay zero-initialized"
);
assert_eq!(
unpack_u32_words(&graph.pg_node_tags_bytes),
vec![0u32; graph.node_count() as usize],
"case {case} packed ProgramGraph node tags must stay zero-initialized"
);
assert_eq!(
graph.stable_layout_hash(),
crate::graph_layout::stable_csr_layout_hash(
graph.node_count(),
graph.edge_count(),
expected_offsets,
expected_targets,
expected_masks,
),
"case {case} stable layout hash drifted from shared graph identity"
);
}
fn unpack_u32_words(bytes: &[u8]) -> Vec<u32> {
vyre_primitives::wire::decode_u32_le_bytes_all(bytes)
}
fn mix_u32(mut value: u32) -> u32 {
value ^= value >> 16;
value = value.wrapping_mul(0x7FEB_352D);
value ^= value >> 15;
value = value.wrapping_mul(0x846C_A68B);
value ^ (value >> 16)
}