xlog_cuda/
joint_solver.rs

1//! Joint constraint solver — skeleton: deterministic component
2//! decomposition, pinned-width envelope, and typed fuel accounting.
3//!
4//! Decomposition, width bounding, and strategy selection are
5//! cold-path setup over the constraint graph. Solve execution
6//! (feasibility propagation, exact top-two/max-marginal dynamic
7//! programming, branch-and-bound) is device-resident and lands with
8//! the solve slice; nothing in this module emits solver outputs, so
9//! no host path here can become a solving fallback.
10
11/// Identity of the solver ABI and objective this module implements:
12/// deterministic component decomposition, exact top-two/max-marginal
13/// DP inside the pinned width envelope, exact branch-and-bound
14/// within device fuel, typed exhaustion beyond it. Carrier schemas
15/// and calibration artifacts bind to this identity; it changes
16/// whenever the ABI or objective changes.
17pub const SOLVER_ABI_IDENTITY: &str = "joint-solver/nary-device-components-dp-bb/5";
18
19/// Typed solver errors. Beyond fuel the solve refuses with the
20/// exact spent/limit literals — no partial emission, no
21/// approximation, no host fallback.
22#[derive(Debug, PartialEq, Eq)]
23pub enum SolverError {
24    /// The device fuel budget is exhausted.
25    ResourceExhausted { fuel_spent: u64, fuel_limit: u64 },
26}
27
28impl std::fmt::Display for SolverError {
29    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
30        match self {
31            SolverError::ResourceExhausted {
32                fuel_spent,
33                fuel_limit,
34            } => write!(
35                f,
36                "solver fuel exhausted: spent {fuel_spent} of {fuel_limit} node expansions"
37            ),
38        }
39    }
40}
41
42impl std::error::Error for SolverError {}
43
44/// Saturating feasibility count for a component: none, exactly one,
45/// or many satisfying assignments. Deliberately separate from score
46/// ambiguity — a component can be uniquely feasible with an
47/// ambiguous maximum, or plurally feasible with a unique maximum.
48#[derive(Debug, Clone, Copy, PartialEq, Eq)]
49pub enum Feasibility {
50    None,
51    One,
52    Many,
53}
54
55/// Solve strategy for one component, selected by the width bound
56/// against the pinned envelope: exact dynamic programming inside the
57/// envelope, exact branch-and-bound (within fuel) outside it.
58#[derive(Debug, Clone, Copy, PartialEq, Eq)]
59pub enum SolveStrategy {
60    ExactDp,
61    BranchAndBound,
62}
63
64/// One connected component of the constraint graph, in canonical
65/// form: variables ascending, edges normalized (low, high) and
66/// sorted, plus a deterministic elimination-order width bound.
67#[derive(Debug, Clone, PartialEq, Eq)]
68pub struct Component {
69    pub variables: Vec<u32>,
70    pub edges: Vec<(u32, u32)>,
71    pub width_bound: u32,
72}
73
74impl Component {
75    /// Strategy under a pinned width envelope. The bound is an
76    /// upper bound, so `ExactDp` selection is safe: true width can
77    /// only be smaller.
78    pub fn strategy(&self, pinned_width: u32) -> SolveStrategy {
79        if self.width_bound <= pinned_width {
80            SolveStrategy::ExactDp
81        } else {
82            SolveStrategy::BranchAndBound
83        }
84    }
85}
86
87/// Undirected constraint graph over entity variables. Self-loops
88/// are meaningless for binary constraints and rejected at
89/// construction; unconnected variables still form singleton
90/// components so no variable can silently drop out of the solve.
91pub struct ConstraintGraph {
92    num_variables: u32,
93    edges: Vec<(u32, u32)>,
94}
95
96impl ConstraintGraph {
97    pub fn new(num_variables: u32, edges: impl IntoIterator<Item = (u32, u32)>) -> Self {
98        let edges: Vec<(u32, u32)> = edges
99            .into_iter()
100            .map(|(a, b)| {
101                assert!(
102                    a < num_variables && b < num_variables,
103                    "constraint edge ({a}, {b}) references a variable outside 0..{num_variables}"
104                );
105                assert!(a != b, "self-loop constraint edge on variable {a}");
106                (a.min(b), a.max(b))
107            })
108            .collect();
109        Self {
110            num_variables,
111            edges,
112        }
113    }
114
115    /// Deterministic connected-component decomposition: union-find
116    /// over the edges, components ordered by their minimum variable
117    /// index, members ascending, edges normalized and sorted. The
118    /// same graph decomposes identically regardless of edge input
119    /// order.
120    pub fn decompose(&self) -> Vec<Component> {
121        let n = self.num_variables as usize;
122        let mut parent: Vec<u32> = (0..self.num_variables).collect();
123
124        fn find(parent: &mut [u32], x: u32) -> u32 {
125            let mut root = x;
126            while parent[root as usize] != root {
127                root = parent[root as usize];
128            }
129            let mut cur = x;
130            while parent[cur as usize] != root {
131                let next = parent[cur as usize];
132                parent[cur as usize] = root;
133                cur = next;
134            }
135            root
136        }
137
138        for &(a, b) in &self.edges {
139            let (ra, rb) = (find(&mut parent, a), find(&mut parent, b));
140            if ra != rb {
141                // Deterministic union: smaller root wins, so every
142                // component's representative is its minimum variable.
143                let (lo, hi) = (ra.min(rb), ra.max(rb));
144                parent[hi as usize] = lo;
145            }
146        }
147
148        let mut members: Vec<Vec<u32>> = vec![Vec::new(); n];
149        for v in 0..self.num_variables {
150            let root = find(&mut parent, v);
151            members[root as usize].push(v);
152        }
153        let mut component_edges: Vec<Vec<(u32, u32)>> = vec![Vec::new(); n];
154        for &(a, b) in &self.edges {
155            let root = find(&mut parent, a);
156            component_edges[root as usize].push((a, b));
157        }
158
159        (0..n)
160            .filter(|&root| !members[root].is_empty())
161            .map(|root| {
162                let variables = members[root].clone();
163                let mut edges = component_edges[root].clone();
164                edges.sort_unstable();
165                edges.dedup();
166                let width_bound = elimination_width_bound(&variables, &edges);
167                Component {
168                    variables,
169                    edges,
170                    width_bound,
171                }
172            })
173            .collect()
174    }
175}
176
177/// Deterministic upper bound on the component's treewidth via
178/// min-degree elimination (ties broken by variable index). An upper
179/// bound is the safe direction for strategy selection: it can send
180/// a narrow component to branch-and-bound, never a wide one to DP.
181fn elimination_width_bound(variables: &[u32], edges: &[(u32, u32)]) -> u32 {
182    use std::collections::{BTreeMap, BTreeSet};
183
184    let mut adj: BTreeMap<u32, BTreeSet<u32>> =
185        variables.iter().map(|&v| (v, BTreeSet::new())).collect();
186    for &(a, b) in edges {
187        adj.get_mut(&a).unwrap().insert(b);
188        adj.get_mut(&b).unwrap().insert(a);
189    }
190
191    let mut width = 0u32;
192    while !adj.is_empty() {
193        // Min degree, then min index: fully deterministic.
194        let (&v, _) = adj
195            .iter()
196            .min_by_key(|(idx, neigh)| (neigh.len(), **idx))
197            .expect("non-empty adjacency");
198        let neighbors: Vec<u32> = adj[&v].iter().copied().collect();
199        width = width.max(neighbors.len() as u32);
200        for &n in &neighbors {
201            let set = adj.get_mut(&n).expect("neighbor present");
202            set.remove(&v);
203            for &m in &neighbors {
204                if m != n {
205                    set.insert(m);
206                }
207            }
208        }
209        adj.remove(&v);
210    }
211    width
212}
213
214/// Test-only oracle for device component discovery. Production
215/// component membership is derived from carrier-owned arguments on
216/// the device and never accepts this host CSR representation.
217#[cfg(test)]
218fn candidate_components(num_entities: u32, pairs: &[(u32, u32)]) -> (Vec<u32>, Vec<u32>) {
219    let n = pairs.len();
220    let mut parent: Vec<u32> = (0..n as u32).collect();
221
222    fn find(parent: &mut [u32], x: u32) -> u32 {
223        let mut root = x;
224        while parent[root as usize] != root {
225            root = parent[root as usize];
226        }
227        let mut cur = x;
228        while parent[cur as usize] != root {
229            let next = parent[cur as usize];
230            parent[cur as usize] = root;
231            cur = next;
232        }
233        root
234    }
235
236    let mut entity_owner: Vec<Option<u32>> = vec![None; num_entities as usize];
237    for (i, &(head, tail)) in pairs.iter().enumerate() {
238        for entity in [head, tail] {
239            assert!(
240                entity < num_entities,
241                "candidate {i} references entity {entity} outside 0..{num_entities}"
242            );
243            match entity_owner[entity as usize] {
244                None => entity_owner[entity as usize] = Some(i as u32),
245                Some(owner) => {
246                    let (ra, rb) = (find(&mut parent, i as u32), find(&mut parent, owner));
247                    if ra != rb {
248                        let (lo, hi) = (ra.min(rb), ra.max(rb));
249                        parent[hi as usize] = lo;
250                    }
251                }
252            }
253        }
254    }
255
256    let mut members: Vec<Vec<u32>> = vec![Vec::new(); n];
257    for cand in 0..n as u32 {
258        let root = find(&mut parent, cand);
259        members[root as usize].push(cand);
260    }
261    let mut offsets = Vec::new();
262    let mut indices = Vec::new();
263    offsets.push(0u32);
264    for group in members.into_iter().filter(|g| !g.is_empty()) {
265        indices.extend_from_slice(&group);
266        offsets.push(indices.len() as u32);
267    }
268    (offsets, indices)
269}
270
271/// Fuel accounting for node expansions. The production counter is
272/// device-resident and read back once post-solve as bounded
273/// metadata; this meter is the typed refusal seam both sides share.
274/// Exhaustion saturates: once refused, every further charge refuses
275/// with the same literals, so no caller can slip work past the
276/// budget by retrying.
277#[derive(Debug)]
278pub struct FuelMeter {
279    limit: u64,
280    spent: u64,
281}
282
283impl FuelMeter {
284    pub fn new(limit: u64) -> Self {
285        Self { limit, spent: 0 }
286    }
287
288    pub fn spent(&self) -> u64 {
289        self.spent
290    }
291
292    /// Unspent budget.
293    pub fn remaining(&self) -> u64 {
294        self.limit - self.spent
295    }
296
297    /// Refund expansions that a prior authorization charged but the
298    /// device measurably did not spend. Callers refund at most
299    /// `authorized - measured` for one completed solve; the meter
300    /// saturates at zero rather than underflowing.
301    pub fn refund(&mut self, expansions: u64) {
302        self.spent = self.spent.saturating_sub(expansions);
303    }
304
305    /// Charge `expansions` node expansions. Refuses typed the
306    /// moment the budget would be exceeded; the overflowing charge
307    /// is not applied.
308    pub fn charge(&mut self, expansions: u64) -> Result<(), SolverError> {
309        let new_spent = self.spent.saturating_add(expansions);
310        if new_spent > self.limit {
311            return Err(SolverError::ResourceExhausted {
312                fuel_spent: self.spent,
313                fuel_limit: self.limit,
314            });
315        }
316        self.spent = new_spent;
317        Ok(())
318    }
319}
320
321#[cfg(test)]
322mod tests {
323    use super::*;
324
325    #[test]
326    fn solver_abi_identity_names_nary_device_component_contract() {
327        assert_eq!(
328            SOLVER_ABI_IDENTITY,
329            "joint-solver/nary-device-components-dp-bb/5"
330        );
331    }
332
333    #[test]
334    fn decomposition_is_deterministic_under_edge_order() {
335        let edges = [(3, 1), (7, 5), (1, 0), (5, 6)];
336        let mut reversed = edges;
337        reversed.reverse();
338        let a = ConstraintGraph::new(9, edges).decompose();
339        let b = ConstraintGraph::new(9, reversed).decompose();
340        assert_eq!(a, b, "edge input order must not change the decomposition");
341    }
342
343    #[test]
344    fn every_variable_lands_in_exactly_one_component() {
345        let graph = ConstraintGraph::new(6, [(0, 1), (4, 5)]);
346        let components = graph.decompose();
347        let mut seen: Vec<u32> = components
348            .iter()
349            .flat_map(|c| c.variables.iter().copied())
350            .collect();
351        seen.sort_unstable();
352        assert_eq!(seen, vec![0, 1, 2, 3, 4, 5]);
353        // Isolated variables 2 and 3 are singleton components, not
354        // silently dropped from the solve.
355        assert_eq!(components.len(), 4);
356        assert!(components
357            .iter()
358            .any(|c| c.variables == vec![2] && c.edges.is_empty()));
359    }
360
361    #[test]
362    fn components_are_canonical_and_ordered_by_minimum_variable() {
363        let graph = ConstraintGraph::new(7, [(6, 4), (2, 0), (4, 5)]);
364        let components = graph.decompose();
365        let mins: Vec<u32> = components.iter().map(|c| c.variables[0]).collect();
366        let mut sorted = mins.clone();
367        sorted.sort_unstable();
368        assert_eq!(mins, sorted, "components ordered by minimum variable");
369        for c in &components {
370            let mut vars = c.variables.clone();
371            vars.sort_unstable();
372            assert_eq!(vars, c.variables, "variables ascending");
373            let mut edges = c.edges.clone();
374            edges.sort_unstable();
375            assert_eq!(edges, c.edges, "edges normalized and sorted");
376            assert!(c.edges.iter().all(|(a, b)| a < b), "edges are (low, high)");
377        }
378    }
379
380    #[test]
381    fn width_bound_matches_known_graphs() {
382        // Path 0-1-2-3: treewidth 1.
383        let path = ConstraintGraph::new(4, [(0, 1), (1, 2), (2, 3)]).decompose();
384        assert_eq!(path[0].width_bound, 1);
385        // Star center 0: treewidth 1.
386        let star = ConstraintGraph::new(5, [(0, 1), (0, 2), (0, 3), (0, 4)]).decompose();
387        assert_eq!(star[0].width_bound, 1);
388        // Complete graph K4: treewidth 3.
389        let k4 =
390            ConstraintGraph::new(4, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]).decompose();
391        assert_eq!(k4[0].width_bound, 3);
392    }
393
394    #[test]
395    fn strategy_splits_on_the_pinned_envelope() {
396        let k4 =
397            ConstraintGraph::new(4, [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]).decompose();
398        assert_eq!(k4[0].strategy(3), SolveStrategy::ExactDp);
399        assert_eq!(k4[0].strategy(2), SolveStrategy::BranchAndBound);
400    }
401
402    #[test]
403    fn candidate_components_join_on_shared_entities_deterministically() {
404        // Candidates 0,1 share entity 1; candidate 2 is disjoint.
405        let pairs = [(0, 1), (1, 2), (3, 4)];
406        let (offsets, indices) = candidate_components(5, &pairs);
407        assert_eq!(offsets, vec![0, 2, 3]);
408        assert_eq!(indices, vec![0, 1, 2]);
409
410        // Same graph with pairs listed in reverse candidate roles:
411        // the grouping is identical because membership is by shared
412        // entity, not by input order of the pair fields.
413        let flipped = [(1, 0), (2, 1), (4, 3)];
414        let (offsets_f, indices_f) = candidate_components(5, &flipped);
415        assert_eq!((offsets_f, indices_f), (offsets, indices));
416
417        // Every candidate lands exactly once.
418        let (offsets, indices) = candidate_components(3, &[(0, 1), (1, 2), (0, 2)]);
419        assert_eq!(offsets, vec![0, 3]);
420        let mut sorted = indices.clone();
421        sorted.sort_unstable();
422        assert_eq!(sorted, vec![0, 1, 2]);
423    }
424
425    #[test]
426    fn fuel_refuses_typed_at_the_boundary_and_saturates() {
427        let mut fuel = FuelMeter::new(10);
428        fuel.charge(10).expect("exactly the budget is legal");
429        let err = fuel.charge(1).expect_err("beyond fuel must refuse");
430        assert_eq!(
431            err,
432            SolverError::ResourceExhausted {
433                fuel_spent: 10,
434                fuel_limit: 10
435            }
436        );
437        // The refused charge was not applied, and refusal repeats
438        // with identical literals — no retry can slip work through.
439        assert_eq!(fuel.spent(), 10);
440        assert_eq!(
441            fuel.charge(1).expect_err("still refused"),
442            SolverError::ResourceExhausted {
443                fuel_spent: 10,
444                fuel_limit: 10
445            }
446        );
447    }
448}
xlog_cuda/joint_solver.rs

xlog_cuda/
joint_solver.rs
