weir/ifds_resident_direct_batch/
graph_key.rs

1#![allow(clippy::too_many_arguments)]
2
3use super::sizing::graph_hash;
4
5/// Opaque identity for a stable direct-resident IFDS graph.
6///
7/// Build this once for an invariant graph, then pass it to
8/// [`DirectResidentIfdsBatch::solve_many_with_graph_key`] or
9/// [`DirectResidentIfdsBatch::solve_with_graph_key`] to avoid re-hashing every
10/// edge family at the call site. The keyed solve path still checks the
11/// graph dimensions, edge-family lengths, and edge-family hash before touching resident cache
12/// state.
13#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
14pub struct DirectResidentIfdsGraphKey {
15    pub(crate) num_procs: u32,
16    pub(crate) blocks_per_proc: u32,
17    pub(crate) facts_per_proc: u32,
18    pub(crate) intra_len: usize,
19    pub(crate) inter_len: usize,
20    pub(crate) gen_len: usize,
21    pub(crate) kill_len: usize,
22    pub(crate) graph_hash: u64,
23}
24
25/// Borrowed direct-resident IFDS graph identity plus edge families.
26///
27/// This is the repeated-solve hot-path handle: construction hashes invariant
28/// edge families once, then the borrow prevents callers from mutating those
29/// slices while repeated solves use the cached identity.
30#[derive(Clone, Copy, Debug, PartialEq)]
31pub struct DirectResidentIfdsGraph<'a> {
32    pub(crate) key: DirectResidentIfdsGraphKey,
33    pub(crate) intra_edges: &'a [(u32, u32, u32)],
34    pub(crate) inter_edges: &'a [(u32, u32, u32, u32)],
35    pub(crate) flow_gen: &'a [(u32, u32, u32)],
36    pub(crate) flow_kill: &'a [(u32, u32, u32)],
37}
38
39impl DirectResidentIfdsGraphKey {
40    /// Build a stable graph key from IFDS dimensions and invariant edge
41    /// families.
42    #[must_use]
43    pub fn from_edges(
44        num_procs: u32,
45        blocks_per_proc: u32,
46        facts_per_proc: u32,
47        intra_edges: &[(u32, u32, u32)],
48        inter_edges: &[(u32, u32, u32, u32)],
49        flow_gen: &[(u32, u32, u32)],
50        flow_kill: &[(u32, u32, u32)],
51    ) -> Self {
52        Self {
53            num_procs,
54            blocks_per_proc,
55            facts_per_proc,
56            intra_len: intra_edges.len(),
57            inter_len: inter_edges.len(),
58            gen_len: flow_gen.len(),
59            kill_len: flow_kill.len(),
60            graph_hash: graph_hash(intra_edges, inter_edges, flow_gen, flow_kill),
61        }
62    }
63
64    pub(crate) fn validate_edges(
65        self,
66        num_procs: u32,
67        blocks_per_proc: u32,
68        facts_per_proc: u32,
69        intra_edges: &[(u32, u32, u32)],
70        inter_edges: &[(u32, u32, u32, u32)],
71        flow_gen: &[(u32, u32, u32)],
72        flow_kill: &[(u32, u32, u32)],
73    ) -> Result<(), String> {
74        if self.num_procs != num_procs
75            || self.blocks_per_proc != blocks_per_proc
76            || self.facts_per_proc != facts_per_proc
77            || self.intra_len != intra_edges.len()
78            || self.inter_len != inter_edges.len()
79            || self.gen_len != flow_gen.len()
80            || self.kill_len != flow_kill.len()
81        {
82            return Err(
83                "weir direct resident IFDS graph key does not match supplied graph dimensions or edge-family lengths. Fix: rebuild DirectResidentIfdsGraphKey after changing the IFDS graph."
84                    .to_string(),
85            );
86        }
87        let supplied_hash = graph_hash(intra_edges, inter_edges, flow_gen, flow_kill);
88        if self.graph_hash != supplied_hash {
89            return Err(
90                "weir direct resident IFDS graph key does not match supplied edge contents. Fix: rebuild DirectResidentIfdsGraphKey after changing any IFDS edge family."
91                    .to_string(),
92            );
93        }
94        Ok(())
95    }
96}
97
98impl<'a> DirectResidentIfdsGraph<'a> {
99    /// Build a borrowed graph view and stable key from IFDS dimensions and
100    /// invariant edge families.
101    #[must_use]
102    pub fn from_edges(
103        num_procs: u32,
104        blocks_per_proc: u32,
105        facts_per_proc: u32,
106        intra_edges: &'a [(u32, u32, u32)],
107        inter_edges: &'a [(u32, u32, u32, u32)],
108        flow_gen: &'a [(u32, u32, u32)],
109        flow_kill: &'a [(u32, u32, u32)],
110    ) -> Self {
111        Self {
112            key: DirectResidentIfdsGraphKey::from_edges(
113                num_procs,
114                blocks_per_proc,
115                facts_per_proc,
116                intra_edges,
117                inter_edges,
118                flow_gen,
119                flow_kill,
120            ),
121            intra_edges,
122            inter_edges,
123            flow_gen,
124            flow_kill,
125        }
126    }
127
128    /// Return the stable direct-resident graph cache key for this borrowed
129    /// graph view.
130    #[must_use]
131    pub fn key(self) -> DirectResidentIfdsGraphKey {
132        self.key
133    }
134}
weir/ifds_resident_direct_batch/graph_key.rs

weir/ifds_resident_direct_batch/
graph_key.rs
