Skip to main content

triblespace_gpu/
batch_confirm.rs

1//! Batched WGPU confirmation for [`SuccinctArchive`] queries.
2//!
3//! The engine's [`Constraint::confirm`] protocol is kill-only: a confirmer
4//! receives one [`Candidates`] region (read-only values and parent tags,
5//! killable liveness bits packed into `u32` words) and may only clear them.
6//! That contract makes the archive's per-candidate membership probes
7//! embarrassingly parallel — every candidate's verdict is independent, and
8//! merging GPU verdicts back is a plain word-wise AND.
9//!
10//! A region spans a whole [`Frontier`], so its candidates do **not** share
11//! one parent binding: entry `i` carries the frontier row it was proposed
12//! for, and it has to be checked against *that* row's bound values. This is
13//! what makes the batched tier reachable below the root — with a width-1
14//! frontier only the root's proposal is wide, and every deeper level offers
15//! the device a handful of candidates.
16//!
17//! [`WgpuSuccinctArchive`] wraps a CPU [`SuccinctArchive`] and keeps the
18//! structures the confirm probes touch resident on the default WGPU device:
19//! the value universe (as big-endian `u32` words for lexicographic binary
20//! search), the three axis occupancy boundaries, and the six Ring wavelet
21//! matrices. Its [`WgpuSuccinctArchiveConstraint`] mirrors the canonical
22//! constraint exactly, except that `confirm` calls whose region holds at
23//! least [`min_confirm_batch`](WgpuSuccinctArchive::min_confirm_batch) live
24//! candidates are evaluated on the device:
25//!
26//! * **Unbound membership** (no other position bound; the confirmed variable
27//!   is E, A, or V): one fused kernel per region — binary search of each
28//!   candidate value in the resident universe plus an axis-boundary
29//!   occupancy check — writes one packed verdict word per 32 candidates.
30//!   Parent tags do not enter: the verdict does not depend on the parent
31//!   binding.
32//! * **Range restriction** (one or two other positions bound): the host
33//!   ships a *parent table* — one row per distinct parent tag in the region,
34//!   holding that parent's bound values — plus one table slot per candidate.
35//!   The device resolves the table to one row band per parent out of the
36//!   same resident universe and boundary tables the probes use, then every
37//!   candidate reads its own parent's band through its slot. The host never
38//!   searches the universe or ranks a wavelet; it copies bound values and
39//!   assigns slots.
40//!
41//! Below the threshold, on any device error, and for every other protocol
42//! method, the wrapper defers to the canonical CPU constraint, so results are
43//! bit-identical either way. `tests/batch_confirm_parity.rs` holds the two
44//! paths to identical liveness words for every arm against a frontier of
45//! one; `tests/mixed_parent_parity.rs` does the same for engine-produced
46//! regions spanning many parents.
47//!
48//! # Packed verdict words
49//!
50//! Core's liveness is bit-packed: a `u32` carries
51//! [`LIVENESS_WORD_BITS`] candidates and a region does not start on a word
52//! boundary. So the verdict kernels write **packed** verdict words — the flat
53//! index is the bit position in the region's liveness word array, one
54//! `plane_ballot` per plane yields a whole 32-candidate word already in the
55//! right bit order, and one lane per word stores it. See
56//! `membership_confirm_ballot_kernel` for the layout argument and its
57//! store-exclusivity conditions, and
58//! `WgpuSuccinctArchive::require_plane_packing` for the device property they
59//! rest on.
60//!
61//! The probe-fill kernels stay **candidate**-indexed: their outputs feed
62//! Jerky's per-candidate rank batch, which knows nothing about liveness. Only
63//! their liveness *input* is bit-addressed, through `candidate_is_live`.
64//!
65//! The host merge — `live_words()`, [`and_words`], `set_live_words()` over a
66//! *private* copy — knows nothing about the packing, because those three are
67//! an abstraction over liveness *words* rather than over candidates. The
68//! device never touches the shared `ProposalBuffer` liveness, so a confirm
69//! cannot disturb the neighbouring regions that share its first and last
70//! word: the copy-in/copy-out boundary is the guard, `live_words()` zeroes the
71//! bits the region does not own on the way out, and `set_live_words()`
72//! refuses to write them on the way back in.
73
74// The `#[cube]` kernels below nest their guards rather than joining them
75// with `&&`. That is load-bearing, not style: a device `&&` evaluates both
76// sides, so `d < m && universe[d * 8] == ..` would index past the resident
77// universe for the `d == m` (value absent) case that the guard exists to
78// exclude. Nesting is uniform across the kernels so no reader has to work
79// out which guards may be joined and which may not.
80#![allow(clippy::collapsible_if)]
81
82use std::sync::atomic::{AtomicU64, Ordering};
83
84use cubecl::prelude::*;
85use cubecl::wgpu::WgpuRuntime;
86use jerky::bit_vector::BitVectorIndex;
87use jerky::bit_vector::{BitVector, Select};
88use jerky::gpu::{DeviceU32Buffer, GpuContext, GpuWaveletMatrix};
89use triblespace_core::blob::encodings::succinctarchive::{
90    SuccinctArchive, SuccinctArchiveConstraint, SuccinctRotation, Universe,
91};
92use triblespace_core::inline::encodings::genid::GenId;
93use triblespace_core::inline::{InlineEncoding, RawInline};
94use triblespace_core::query::{
95    and_words, Binding, Candidates, Constraint, Frontier, ProposalBuffer, RawTerm, Term,
96    TriblePattern, VariableId, VariableSet, LIVENESS_WORD_BITS,
97};
98
99const THREADS: u32 = super::THREADS;
100
101/// The core/device liveness geometry contract, made a compile error.
102///
103/// Every packed kernel below hardcodes 32 in three separate places: the
104/// ballot component it reads (`ballot[0]` covers lanes 0..32), the
105/// `UNIT_POS_PLANE == 0` store guard (one store per 32-candidate word), and
106/// the `b / 32` / `b % 32` arithmetic that turns a flat bit position into a
107/// word index and a bit within it. None of that is derived from core's
108/// [`LIVENESS_WORD_BITS`] — WGSL has no `u64`, and the ballot is a hardware
109/// primitive whose width is the plane's, not the liveness word's.
110///
111/// So if core ever widens its liveness word, this crate would keep writing
112/// 32-bit verdict words into a wider array. That does not fail to compile and
113/// does not crash: every buffer length still type-checks, every index stays
114/// in range, and the only symptom is **verdict bits landing on the wrong
115/// candidates** — silently wrong query answers, on the confirm path, with no
116/// diagnostic anywhere. Whoever widens the word should instead get a build
117/// failure that names the kernels they have to widen with it.
118///
119/// This is deliberately stronger than the assert it replaces on the
120/// pre-collapse branch, which only checked that two crates agreed on *which*
121/// of two liveness representations was compiled in. With one representation
122/// left there is no such choice; the geometry is the whole contract.
123const _: () = assert!(
124    LIVENESS_WORD_BITS == 32,
125    "packed confirm hardcodes 32 bits per liveness word: the plane ballot's \
126     component 0, the one-store-per-plane guard, and the bit/word arithmetic \
127     in the confirm kernels all assume it. Widen those with the word."
128);
129
130/// Condition (a) of the packed kernels' store-exclusivity invariant: each
131/// cube's range of flat indices starts on a 32-bit word boundary, so no
132/// verdict word is split across two cubes. It holds because the flat id is
133/// `linear_cube_index * CUBE_DIM + local_index` and `CUBE_DIM` is a multiple
134/// of 32. Nothing else would notice a change to `THREADS`; this would produce
135/// wrong query answers and no diagnostic, so make it a compile error instead.
136const _: () = assert!(
137    THREADS % 32 == 0,
138    "packed confirm needs a cube dim that is a multiple of the 32-bit liveness word"
139);
140
141/// Jerky's out-of-range marker for a batched rank result.
142const RANK_OUT_OF_RANGE: u32 = u32::MAX;
143
144/// Jerky's wavelet matrix resident on the default CubeCL WGPU device.
145pub type WgpuWaveletMatrix = GpuWaveletMatrix<WgpuRuntime>;
146
147/// Jerky's shared compatibility domain on the default CubeCL WGPU device.
148pub type WgpuContext = GpuContext<WgpuRuntime>;
149
150/// Default minimum number of live candidates in a confirm region before the
151/// verdicts are computed on WGPU; smaller regions run the canonical CPU
152/// probes.
153///
154/// Measured on an Apple M4 Max (Metal via wgpu, cubecl 0.10), release
155/// profile, with the two ignored sweep benchmarks. `cpu/gpu` is total CPU
156/// probe time over total device time for the same regions, so above 1.00 the
157/// device wins.
158///
159/// **Mixed-parent regions** — `mixed_parent_crossover_sweep` in
160/// `tests/mixed_parent_parity.rs`: a 414,801-trible / 81,632-value archive
161/// driven through a real [`Query`](triblespace_core::query::Query) whose
162/// variable order is pinned, over frontier widths 256…16384 and fanouts
163/// 1/4/16, so every routed range confirm sees a genuine batch of parents.
164/// The spread in each cell is across those sweep points.
165///
166/// | mean region | 1-bound arm | 2-bound arm |
167/// |------------:|------------:|------------:|
168/// |       1 024 | 0.16 – 0.21 |           — |
169/// |       4 096 | 0.42 – 0.81 | 0.56 – 0.65 |
170/// |      16 384 | 1.62 – 2.72 | 1.92 – 2.42 |
171/// |      65 536 | 3.58 – 6.82 | 5.75 – 6.84 |
172/// |     262 144 |        6.87 | 10.2 – 11.1 |
173///
174/// **Frontier of one** — `confirm_crossover_sweep` in
175/// `tests/batch_confirm_parity.rs`, a 262,135-trible / 68,422-value archive,
176/// one parent, which is where the membership arm is measured (it is
177/// parent-independent, so a batch tells it nothing new):
178///
179/// | region | membership | range |
180/// |-------:|-----------:|------:|
181/// |  1 024 |       0.04 |  0.14 |
182/// |  4 096 |       0.16 |  0.64 |
183/// | 16 384 |       0.72 |  2.02 |
184/// | 65 536 |       2.41 |  3.32 |
185///
186/// The device round trip is nearly flat (~1.2–2.6 ms) while CPU probe cost
187/// scales linearly, putting both range shapes' crossover at ~6–8k
188/// candidates. The lighter membership arm — one universe search and one
189/// boundary compare per candidate, no wavelet rank at all — is still at
190/// 0.72x at 16 384 and only wins from ~24k up, so it is membership, not the
191/// range shapes, that sets the knob.
192///
193/// 16384 is the single-knob compromise: the range shapes are a 1.6–2.7x win
194/// there and membership costs 1.4x, and it equals
195/// [`DEFAULT_FRONTIER_WIDTH`](triblespace_core::query::DEFAULT_FRONTIER_WIDTH),
196/// so a level whose rows each contribute one candidate already reaches the
197/// batched tier. Lowering it to the range shapes' own crossover would trade
198/// their gain for a deeper membership loss.
199///
200/// The number is unchanged from the pre-frontier measurement, but what it
201/// buys is not: resolving parent bands on the device rather than on the host
202/// took the mixed-parent range shapes from 1.6–5.4x to 2.7–11.1x at width
203/// 16384 (device time for a 262k-candidate 2-bound region: 13.4 ms → 7.3 ms),
204/// because the host no longer ranks a wavelet once per frontier row before
205/// it can dispatch.
206pub const DEFAULT_MIN_CONFIRM_BATCH: usize = 16384;
207
208/// Observational dispatch counters for one [`WgpuSuccinctArchive`].
209///
210/// Counters use relaxed atomics: snapshots taken after query completion are
211/// exact, concurrent snapshots are telemetry.
212#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
213pub struct WgpuConfirmStats {
214    /// Confirm calls whose verdicts were computed on the device.
215    pub gpu_confirms: u64,
216    /// Region entries (live and dead) shipped through device confirms.
217    pub gpu_candidates: u64,
218    /// Parent-table rows resolved on the device, summed over routed
219    /// confirms — one per distinct parent tag in a routed region, and the
220    /// measure of how wide the frontiers reaching the device actually are.
221    pub gpu_parents: u64,
222    /// Confirm calls routed to the canonical CPU constraint by the
223    /// live-candidate threshold.
224    pub cpu_fallback_confirms: u64,
225    /// Region entries handled by threshold fallbacks.
226    pub cpu_fallback_candidates: u64,
227    /// Device errors that demoted a routed confirm to the CPU path.
228    pub gpu_errors: u64,
229}
230
231#[derive(Default)]
232struct ConfirmStats {
233    gpu_confirms: AtomicU64,
234    gpu_candidates: AtomicU64,
235    gpu_parents: AtomicU64,
236    cpu_fallback_confirms: AtomicU64,
237    cpu_fallback_candidates: AtomicU64,
238    gpu_errors: AtomicU64,
239}
240
241impl ConfirmStats {
242    fn record_gpu(&self, candidates: usize, parents: usize) {
243        self.gpu_confirms.fetch_add(1, Ordering::Relaxed);
244        self.gpu_candidates
245            .fetch_add(candidates as u64, Ordering::Relaxed);
246        self.gpu_parents
247            .fetch_add(parents as u64, Ordering::Relaxed);
248    }
249
250    fn record_cpu(&self, candidates: usize) {
251        self.cpu_fallback_confirms.fetch_add(1, Ordering::Relaxed);
252        self.cpu_fallback_candidates
253            .fetch_add(candidates as u64, Ordering::Relaxed);
254    }
255
256    fn record_error(&self) {
257        self.gpu_errors.fetch_add(1, Ordering::Relaxed);
258    }
259
260    fn snapshot(&self) -> WgpuConfirmStats {
261        WgpuConfirmStats {
262            gpu_confirms: self.gpu_confirms.load(Ordering::Relaxed),
263            gpu_candidates: self.gpu_candidates.load(Ordering::Relaxed),
264            gpu_parents: self.gpu_parents.load(Ordering::Relaxed),
265            cpu_fallback_confirms: self.cpu_fallback_confirms.load(Ordering::Relaxed),
266            cpu_fallback_candidates: self.cpu_fallback_candidates.load(Ordering::Relaxed),
267            gpu_errors: self.gpu_errors.load(Ordering::Relaxed),
268        }
269    }
270
271    fn reset(&self) {
272        self.gpu_confirms.store(0, Ordering::Relaxed);
273        self.gpu_candidates.store(0, Ordering::Relaxed);
274        self.gpu_parents.store(0, Ordering::Relaxed);
275        self.cpu_fallback_confirms.store(0, Ordering::Relaxed);
276        self.cpu_fallback_candidates.store(0, Ordering::Relaxed);
277        self.gpu_errors.store(0, Ordering::Relaxed);
278    }
279}
280
281/// Byte-lexicographic three-way comparison between universe entry `d` and
282/// entry `i` of `probes`, both stored as 8 big-endian `u32` words.
283///
284/// Returns 0 when equal, 1 when the universe entry orders below the probe,
285/// 2 when it orders above.
286#[cube]
287fn value_order(universe: &Array<u32>, d: u32, probes: &Array<u32>, i: u32) -> u32 {
288    let mut order = u32::new(0);
289    let mut w = u32::new(0);
290    while w < 8u32 {
291        if order == 0u32 {
292            let dv = universe[(d * 8u32 + w) as usize];
293            let cv = probes[(i * 8u32 + w) as usize];
294            if dv < cv {
295                order = 1u32;
296            }
297            if dv > cv {
298                order = 2u32;
299            }
300        }
301        w += 1u32;
302    }
303    order
304}
305
306/// Lower-bound binary search for entry `i` of `probes` over the sorted
307/// resident universe of `m` entries. Returns `m` when every entry orders
308/// below the probe; equality still has to be checked at the returned slot.
309#[cube]
310fn universe_lower_bound(universe: &Array<u32>, m: u32, probes: &Array<u32>, i: u32) -> u32 {
311    let mut lo = u32::new(0);
312    let mut hi = m;
313    while lo < hi {
314        let mid = lo + (hi - lo) / 2u32;
315        if value_order(universe, mid, probes, i) == 1u32 {
316            lo = mid + 1u32;
317        } else {
318            hi = mid;
319        }
320    }
321    lo
322}
323
324/// The universe code of entry `i` of `probes`, or `m` when the value is
325/// absent from the universe.
326#[cube]
327fn universe_code(universe: &Array<u32>, m: u32, probes: &Array<u32>, i: u32) -> u32 {
328    let mut code = m;
329    let d = universe_lower_bound(universe, m, probes, i);
330    if d < m {
331        if value_order(universe, d, probes, i) == 0u32 {
332            code = d;
333        }
334    }
335    code
336}
337
338/// Whether candidate `i` of a region whose entry 0 sits at bit `bit_offset`
339/// is still live, read out of the region's packed liveness words.
340///
341/// The one place the device spells core's bit layout for *reading*: entry `i`
342/// is bit `bit_offset + i`, i.e. bit `(bit_offset + i) % 32` of word
343/// `(bit_offset + i) / 32`. Callers must have bounded `i` by the region's
344/// candidate count, which bounds the word index by `live`'s length.
345#[cube]
346fn candidate_is_live(live: &Array<u32>, bit_offset: u32, i: u32) -> u32 {
347    let b = bit_offset + i;
348    (live[(b / 32u32) as usize] >> (b % 32u32)) & 1u32
349}
350
351/// Packed verdict words for the unbound membership arms: a live candidate's
352/// bit survives exactly when its value occurs in the universe *and* the axis
353/// boundary table shows at least one row on the confirmed axis — the same
354/// probe as the CPU arm's `base_range(..).is_empty().not()`. One
355/// `plane_ballot` per plane, one store per 32 candidates.
356///
357/// # The flat index is a bit position, not a candidate
358///
359/// `ABSOLUTE_POS` is `b`, the bit position inside the region's liveness word
360/// array — candidate `i` is `b - bit_offset`, and bit `b` is bit `b % 32` of
361/// word `b / 32` *by construction*. That change of variable is the whole
362/// trick: a plane's 32 lanes cover `b .. b + 32`, so the hardware's ballot
363/// mask already carries each verdict in the bit its word wants it in. No
364/// rotation by `bit_offset`, no read-modify-write of a word two lanes share,
365/// no atomic. The price is that the dispatch covers `bit_offset + n` slots
366/// instead of `n` — at most 31 idle lanes, i.e. at most one extra cube.
367///
368/// Bit slots below `bit_offset`, or at and above `bit_offset + n`, belong to
369/// the *neighbouring* regions of the same buffer. They take verdict `false`,
370/// which is the value that survives both host masks unchanged: `live_words()`
371/// already handed those bits out as `0`, and `set_live_words()` will not write
372/// them back.
373///
374/// # Store exclusivity
375///
376/// Verdict word `w` is written by exactly one invocation of the whole
377/// dispatch — the one whose `b` equals `32 * w`. Three conditions buy that:
378///
379/// * **(a)** `CubeDim` is 1-D and a multiple of 32 (`THREADS == 64`), and the
380///   WGSL backend's flat id reduces to `linear_cube_index * CUBE_DIM +
381///   local_index`, so `ABSOLUTE_POS` is dense and every cube's range starts on
382///   a word boundary. This holds whether or not cubecl spreads the dispatch
383///   over 2 or 3 grid dimensions, because the `y`/`z` strides it uses are both
384///   multiples of `CUBE_DIM`.
385/// * **(b)** the plane is exactly 32 lanes, so one plane owns exactly one word
386///   and no word straddles two planes. Checked on the host in
387///   [`WgpuSuccinctArchive::require_plane_packing`]: below 32, two planes would
388///   each store the same word and the last writer would win; above 32, lane 32
389///   would need ballot component 1 and this kernel hardcodes component 0.
390/// * **(c)** `UNIT_POS_PLANE` (WGSL `subgroup_invocation_id`) is the lane's
391///   position in the linear order the flat id follows, so ballot bit `L` is the
392///   verdict of the lane whose `b` is `plane_base + L`. True on every Metal and
393///   CUDA adapter; *not* promised by the WGSL subgroups extension, whose
394///   invocation-to-subgroup mapping is implementation-defined. A violation
395///   produces wrong query answers and no diagnostic — the non-zero
396///   `bit_offset` bases in `tests/batch_confirm_parity.rs` are what would
397///   catch it.
398///
399/// Every word of `verdicts` is stored, which matters because `empty_u32`
400/// hands back uninitialized device memory: the dispatch rounds
401/// `bit_offset + n` up to whole cubes of 64 lanes, and that always contains
402/// the lane `b == 32 * w` for every `w < words`.
403///
404/// The `plane_ballot` sits at the kernel's top-level control flow, so every
405/// unit of every plane reaches it. That is deliberate rather than incidental:
406/// `cubecl-wgpu` never claims `Plane::NonUniformControlFlow` on the plain WGSL
407/// path this crate builds, so a ballot inside the liveness branch would be
408/// betting on semantics the backend does not promise. The branch costs nothing
409/// to keep *below* the ballot — dead candidates still skip the binary search.
410#[cube(launch_unchecked)]
411fn membership_confirm_ballot_kernel(
412    cands: &Array<u32>,
413    live: &Array<u32>,
414    universe: &Array<u32>,
415    bounds: &Array<u32>,
416    verdicts: &mut Array<u32>,
417    n: u32,
418    m: u32,
419    bit_offset: u32,
420) {
421    let b = ABSOLUTE_POS as u32;
422    let n_bits = bit_offset + n;
423    let words = (n_bits + 31u32) / 32u32;
424
425    let mut verdict = u32::new(0);
426    if b >= bit_offset {
427        if b < n_bits {
428            // `b < n_bits` bounds `b / 32` by `words`, so this load is in
429            // range; the bit it reads is candidate `b - bit_offset`.
430            let i = b - bit_offset;
431            if candidate_is_live(live, bit_offset, i) != 0u32 {
432                let d = universe_code(universe, m, cands, i);
433                if d < m {
434                    if bounds[(d + 1u32) as usize] > bounds[d as usize] {
435                        verdict = 1u32;
436                    }
437                }
438            }
439        }
440    }
441
442    // UNIFORM: reached by every unit of the plane, see the note above.
443    let ballot = plane_ballot(verdict != 0u32);
444
445    // One store per word. Deliberately not `plane_elect`, which returns the
446    // lowest *active* lane and so couples this store's correctness to the
447    // uniformity we are separately maintaining. With condition (b) the plane
448    // is 32 wide, so this is its lane 0 and its ballot occupies component 0 of
449    // the 128-bit result.
450    if UNIT_POS_PLANE == 0u32 {
451        let w = b / 32u32;
452        if w < words {
453            verdicts[w as usize] = ballot[0];
454        }
455    }
456}
457
458/// Writes candidate `i`'s rank-probe pair given the row band `start..end`
459/// its parent restricts the archive to: probe positions are the band, probe
460/// values the candidate's universe code. Dead, absent, or empty-band
461/// candidates get `flag = 0` and a harmless `(0, code 0)` pair — an empty
462/// band restricts to nothing, exactly as the CPU arm's
463/// `restrict_range(..).is_empty()` does.
464///
465/// `flags`, `positions` and `probes` are indexed by the **candidate**, not by
466/// a bit position: they feed Jerky's per-candidate rank batch. Only the
467/// liveness input is bit-addressed, at `bit_offset + i`.
468#[cube]
469#[allow(clippy::too_many_arguments)]
470fn emit_candidate_probe(
471    cands: &Array<u32>,
472    live: &Array<u32>,
473    universe: &Array<u32>,
474    i: u32,
475    m: u32,
476    bit_offset: u32,
477    start: u32,
478    end: u32,
479    flags: &mut Array<u32>,
480    positions: &mut Array<u32>,
481    probes: &mut Array<u32>,
482) {
483    let mut flag = u32::new(0);
484    let mut code = u32::new(0);
485    let mut lo = u32::new(0);
486    let mut hi = u32::new(0);
487    if candidate_is_live(live, bit_offset, i) != 0u32 {
488        if start < end {
489            let d = universe_code(universe, m, cands, i);
490            if d < m {
491                flag = 1u32;
492                code = d;
493                lo = start;
494                hi = end;
495            }
496        }
497    }
498    flags[i as usize] = flag;
499    positions[(2u32 * i) as usize] = lo;
500    positions[(2u32 * i + 1u32) as usize] = hi;
501    probes[(2u32 * i) as usize] = code;
502    probes[(2u32 * i + 1u32) as usize] = code;
503}
504
505/// Probe fill for the **single-bound** range arms. Each candidate reads its
506/// own parent's bound value through its table slot and resolves that
507/// parent's row band inline — the CPU arm's
508/// `base_range(domain, axis, value)`, read straight out of the resident
509/// boundary table instead of two `select1`s, with an absent value yielding
510/// an empty band exactly as `base_range`'s `else` branch does.
511///
512/// Resolving per candidate rather than per parent repeats one universe
513/// search for candidates that share a parent. That is deliberate: the search
514/// is a handful of coalesced compares in a thread that is running anyway,
515/// while a separate parent pass would cost a whole dispatch — measurably
516/// more than the redundancy at every region size above the routing
517/// threshold.
518#[cube(launch_unchecked)]
519fn base_probe_fill_kernel(
520    cands: &Array<u32>,
521    live: &Array<u32>,
522    universe: &Array<u32>,
523    slots: &Array<u32>,
524    parent_values: &Array<u32>,
525    bounds: &Array<u32>,
526    flags: &mut Array<u32>,
527    positions: &mut Array<u32>,
528    probes: &mut Array<u32>,
529    n: u32,
530    m: u32,
531    bit_offset: u32,
532) {
533    let i = ABSOLUTE_POS as u32;
534    if i < n {
535        let mut start = u32::new(0);
536        let mut end = u32::new(0);
537        if candidate_is_live(live, bit_offset, i) != 0u32 {
538            let slot = slots[i as usize];
539            let d = universe_code(universe, m, parent_values, slot);
540            if d < m {
541                start = bounds[d as usize];
542                end = bounds[(d + 1u32) as usize];
543            }
544        }
545        emit_candidate_probe(
546            cands, live, universe, i, m, bit_offset, start, end, flags, positions, probes,
547        );
548    }
549}
550
551/// Parent pass for the **double-bound** range arms: the outer bound value's
552/// base range becomes a rank probe pair on the inner rotation, the inner
553/// bound value's code the probe symbol. Either value absent from the
554/// universe clears the flag, which
555/// [`restrict_probe_fill_kernel`] reads as an empty band — the CPU arm's
556/// nested `restrict_range(.., base_range(..))` with both `else` branches
557/// folded into one.
558///
559/// This pass cannot be fused into the candidate kernel: its result *is* a
560/// wavelet rank, and that is a dispatch of its own.
561#[cube(launch_unchecked)]
562fn parent_restrict_probe_kernel(
563    universe: &Array<u32>,
564    outer_bounds: &Array<u32>,
565    outer_values: &Array<u32>,
566    inner_values: &Array<u32>,
567    codes: &mut Array<u32>,
568    flags: &mut Array<u32>,
569    positions: &mut Array<u32>,
570    probes: &mut Array<u32>,
571    p: u32,
572    m: u32,
573) {
574    let j = ABSOLUTE_POS as u32;
575    if j < p {
576        let mut flag = u32::new(0);
577        let mut code = u32::new(0);
578        let mut lo = u32::new(0);
579        let mut hi = u32::new(0);
580        let outer = universe_code(universe, m, outer_values, j);
581        if outer < m {
582            let inner = universe_code(universe, m, inner_values, j);
583            if inner < m {
584                flag = 1u32;
585                code = inner;
586                lo = outer_bounds[outer as usize];
587                hi = outer_bounds[(outer + 1u32) as usize];
588            }
589        }
590        codes[j as usize] = code;
591        flags[j as usize] = flag;
592        positions[(2u32 * j) as usize] = lo;
593        positions[(2u32 * j + 1u32) as usize] = hi;
594        probes[(2u32 * j) as usize] = code;
595        probes[(2u32 * j + 1u32) as usize] = code;
596    }
597}
598
599/// Probe fill for the **double-bound** range arms: each candidate folds its
600/// own parent's rank pair into that parent's row band —
601/// `restrict_range`'s `base + rank(r.start, d) .. base + rank(r.end, d)` —
602/// and emits its own probe against it.
603#[cube(launch_unchecked)]
604fn restrict_probe_fill_kernel(
605    cands: &Array<u32>,
606    live: &Array<u32>,
607    universe: &Array<u32>,
608    slots: &Array<u32>,
609    parent_flags: &Array<u32>,
610    parent_codes: &Array<u32>,
611    parent_ranks: &Array<u32>,
612    inner_bounds: &Array<u32>,
613    flags: &mut Array<u32>,
614    positions: &mut Array<u32>,
615    probes: &mut Array<u32>,
616    n: u32,
617    m: u32,
618    out_of_range: u32,
619    bit_offset: u32,
620) {
621    let i = ABSOLUTE_POS as u32;
622    if i < n {
623        let mut start = u32::new(0);
624        let mut end = u32::new(0);
625        if candidate_is_live(live, bit_offset, i) != 0u32 {
626            let slot = slots[i as usize];
627            if parent_flags[slot as usize] != 0u32 {
628                let lo = parent_ranks[(2u32 * slot) as usize];
629                let hi = parent_ranks[(2u32 * slot + 1u32) as usize];
630                // A band read out of the resident boundary tables is always
631                // a valid rank position, so `out_of_range` cannot occur
632                // here; an empty band is the kill-only reading if it ever
633                // did.
634                if lo != out_of_range {
635                    if hi != out_of_range {
636                        let base = inner_bounds[parent_codes[slot as usize] as usize];
637                        start = base + lo;
638                        end = base + hi;
639                    }
640                }
641            }
642        }
643        emit_candidate_probe(
644            cands, live, universe, i, m, bit_offset, start, end, flags, positions, probes,
645        );
646    }
647}
648
649/// Folds the batched wavelet ranks into packed verdict words: a flagged
650/// candidate survives exactly when its code occurs inside its parent's row
651/// band — `rank(r.start, d) != rank(r.end, d)`, the CPU arm's
652/// `restrict_range(..).is_empty().not()` with the shared `select1` base
653/// offset cancelled.
654///
655/// Identical in structure to `membership_confirm_ballot_kernel` — flat index
656/// is the bit position `b`, out-of-region slots vote `false`, one ballot per
657/// plane, one store per word — with the universe probe replaced by the rank
658/// comparison. Its store-exclusivity argument is the one documented there.
659/// Note that `flags` and `ranks` are still indexed by the **candidate**
660/// `b - bit_offset`, because the probe fills wrote them per-candidate.
661#[cube(launch_unchecked)]
662fn range_verdict_ballot_kernel(
663    flags: &Array<u32>,
664    ranks: &Array<u32>,
665    verdicts: &mut Array<u32>,
666    n: u32,
667    out_of_range: u32,
668    bit_offset: u32,
669) {
670    let b = ABSOLUTE_POS as u32;
671    let n_bits = bit_offset + n;
672    let words = (n_bits + 31u32) / 32u32;
673
674    let mut verdict = u32::new(0);
675    if b >= bit_offset {
676        if b < n_bits {
677            // `flags` already folded in liveness: the probe fill zeroed it for
678            // every dead, absent, or empty-band candidate.
679            let i = b - bit_offset;
680            if flags[i as usize] != 0u32 {
681                let lo = ranks[(2u32 * i) as usize];
682                let hi = ranks[(2u32 * i + 1u32) as usize];
683                // Same kill-only reading of an impossible out-of-range rank as
684                // in the parent fold.
685                if lo != out_of_range {
686                    if hi != out_of_range {
687                        if lo != hi {
688                            verdict = 1u32;
689                        }
690                    }
691                }
692            }
693        }
694    }
695
696    // UNIFORM: reached by every unit of the plane.
697    let ballot = plane_ballot(verdict != 0u32);
698
699    if UNIT_POS_PLANE == 0u32 {
700        let w = b / 32u32;
701        if w < words {
702            verdicts[w as usize] = ballot[0];
703        }
704    }
705}
706
707/// One of the three trible positions — which axis boundary table to read,
708/// and which position's value to take from a binding.
709#[derive(Clone, Copy, Debug, Eq, PartialEq)]
710enum Axis {
711    Entity,
712    Attribute,
713    Value,
714}
715
716/// What a routed confirm needs from each parent binding of the frontier.
717///
718/// The *bound set* is shared by every row of a frontier, so the arm — and
719/// therefore this plan — is classified once for the whole region. Only the
720/// bound *values*, and hence each parent's row band, vary by row.
721#[derive(Clone, Copy, Debug, Eq, PartialEq)]
722enum ConfirmPlan {
723    /// No other position is bound: an axis-occupancy probe per candidate,
724    /// identical for every parent.
725    Membership { axis: Axis },
726    /// One other position is bound: the parent's band is that value's base
727    /// range on `bound`; candidates probe `rotation`.
728    Base {
729        bound: Axis,
730        rotation: SuccinctRotation,
731    },
732    /// Two other positions are bound: the band is `outer`'s base range
733    /// narrowed through `inner_col` to `inner`'s value.
734    Restrict {
735        outer: Axis,
736        inner: Axis,
737        inner_col: SuccinctRotation,
738        rotation: SuccinctRotation,
739    },
740}
741
742/// Packs values into big-endian `u32` words, so the kernels' word-wise `u32`
743/// comparison equals byte-lexicographic order.
744fn pack_be_words(values: &[RawInline]) -> Vec<u32> {
745    let mut words = Vec::with_capacity(values.len() * 8);
746    for value in values {
747        for chunk in value.chunks_exact(4) {
748            words.push(u32::from_be_bytes(chunk.try_into().unwrap()));
749        }
750    }
751    words
752}
753
754fn count_live(cands: &Candidates<'_>) -> usize {
755    (0..cands.len()).filter(|&i| cands.is_live(i)).count()
756}
757
758/// The region's parent tags compacted into a table: one entry per *distinct*
759/// tag, in first-seen order, plus the table slot of every candidate.
760///
761/// Compacting matters twice over. The host resolves one band per table row
762/// rather than one per frontier row, so a region that touches three parents
763/// of a 16k-wide frontier costs three; and the device receives `slots.len()`
764/// plus `rows.len()` words instead of a band per candidate. Correct for any
765/// tag order — runs are the common shape, but nothing here assumes them.
766fn parent_table(
767    frontier: &Frontier<'_>,
768    cands: &Candidates<'_>,
769) -> jerky::Result<(Vec<u32>, Vec<u32>)> {
770    let width = frontier.len();
771    let mut slot_of_row = vec![u32::MAX; width];
772    let mut slots = Vec::with_capacity(cands.len());
773    let mut rows: Vec<u32> = Vec::new();
774    for &parent in cands.parents() {
775        let row = parent as usize;
776        if row >= width {
777            return Err(jerky::Error::invalid_argument(format!(
778                "candidate parent tag {parent} exceeds the {width} rows of its frontier"
779            )));
780        }
781        let mut slot = slot_of_row[row];
782        if slot == u32::MAX {
783            slot = rows.len() as u32;
784            slot_of_row[row] = slot;
785            rows.push(parent);
786        }
787        slots.push(slot);
788    }
789    Ok((slots, rows))
790}
791
792/// A [`SuccinctArchive`] whose confirm probes can run batched on the default
793/// CubeCL WGPU device.
794///
795/// Construction uploads the value universe (8 big-endian `u32` words per
796/// entry), one cumulative occupancy boundary table per axis
797/// (`bounds[d] = select1(d) - d`, so `bounds[d+1] > bounds[d]` iff code `d`
798/// occurs on that axis, and `bounds[d]..bounds[d+1]` *is* that code's base
799/// range), and the six Ring wavelet matrices. Planning, estimates, and
800/// proposals always use the wrapped CPU archive; only
801/// [`Constraint::confirm`] regions at or above
802/// [`min_confirm_batch`](Self::min_confirm_batch) live candidates dispatch to
803/// the device.
804pub struct WgpuSuccinctArchive<U>
805where
806    U: Universe,
807{
808    archive: SuccinctArchive<U>,
809    context: WgpuContext,
810    /// Resident universe image: `domain_len * 8` big-endian words, ascending.
811    universe_words: DeviceU32Buffer<WgpuRuntime>,
812    domain_len: usize,
813    /// Per-axis cumulative row counts, `domain_len + 1` words each.
814    e_bounds: DeviceU32Buffer<WgpuRuntime>,
815    a_bounds: DeviceU32Buffer<WgpuRuntime>,
816    v_bounds: DeviceU32Buffer<WgpuRuntime>,
817    /// Resident Ring columns in canonical [`SuccinctRotation`] order.
818    ring: [WgpuWaveletMatrix; SuccinctRotation::ALL.len()],
819    min_confirm_batch: usize,
820    stats: ConfirmStats,
821}
822
823fn axis_bounds<I: BitVectorIndex>(
824    context: &WgpuContext,
825    prefix: &BitVector<I>,
826    domain_len: usize,
827    axis: &'static str,
828) -> jerky::Result<DeviceU32Buffer<WgpuRuntime>> {
829    let mut bounds = Vec::with_capacity(domain_len + 1);
830    for d in 0..=domain_len {
831        let position = prefix.select1(d).ok_or_else(|| {
832            jerky::Error::invalid_argument(format!(
833                "{axis} prefix is missing delimiter {d} of {domain_len}"
834            ))
835        })?;
836        let count = position - d;
837        bounds.push(u32::try_from(count).map_err(|_| {
838            jerky::Error::invalid_argument(format!(
839                "{axis} prefix count {count} does not fit the resident u32 domain"
840            ))
841        })?);
842    }
843    context.upload_u32(&bounds)
844}
845
846impl<U> WgpuSuccinctArchive<U>
847where
848    U: Universe,
849{
850    /// Wraps `archive`, enqueueing its universe, axis boundaries, and Ring
851    /// columns on the default WGPU device.
852    ///
853    /// Fails when the archive exceeds the resident `u32` geometry (universe
854    /// or row count near `u32::MAX`) or when the universe's `access` order
855    /// is not strictly ascending — the [`Universe`] contract the device
856    /// binary search depends on, revalidated here because a violation would
857    /// silently corrupt query results.
858    pub fn new(archive: SuccinctArchive<U>) -> jerky::Result<Self> {
859        let domain_len = archive.domain.len();
860        let triple_count = archive.eav_c.len();
861        if domain_len >= (u32::MAX as usize) / 8 {
862            return Err(jerky::Error::invalid_argument(format!(
863                "universe of {domain_len} values does not fit the resident u32 domain"
864            )));
865        }
866        if triple_count >= u32::MAX as usize {
867            return Err(jerky::Error::invalid_argument(format!(
868                "archive of {triple_count} rows does not fit the resident u32 domain"
869            )));
870        }
871
872        let mut universe_values = Vec::with_capacity(domain_len);
873        for d in 0..domain_len {
874            let value = archive.domain.access(d);
875            if let Some(previous) = universe_values.last() {
876                if *previous >= value {
877                    return Err(jerky::Error::invalid_argument(format!(
878                        "universe access order is not strictly ascending at code {d}"
879                    )));
880                }
881            }
882            universe_values.push(value);
883        }
884        let universe_image = pack_be_words(&universe_values);
885
886        let context = WgpuContext::on_wgpu();
887        let universe_words = context.upload_u32(&universe_image)?;
888        let e_bounds = axis_bounds(&context, &archive.e_a, domain_len, "entity")?;
889        let a_bounds = axis_bounds(&context, &archive.a_a, domain_len, "attribute")?;
890        let v_bounds = axis_bounds(&context, &archive.v_a, domain_len, "value")?;
891        let ring = [
892            WgpuWaveletMatrix::with_context(context.clone(), &archive.eav_c)?,
893            WgpuWaveletMatrix::with_context(context.clone(), &archive.vea_c)?,
894            WgpuWaveletMatrix::with_context(context.clone(), &archive.ave_c)?,
895            WgpuWaveletMatrix::with_context(context.clone(), &archive.vae_c)?,
896            WgpuWaveletMatrix::with_context(context.clone(), &archive.eva_c)?,
897            WgpuWaveletMatrix::with_context(context.clone(), &archive.aev_c)?,
898        ];
899        Ok(Self {
900            archive,
901            context,
902            universe_words,
903            domain_len,
904            e_bounds,
905            a_bounds,
906            v_bounds,
907            ring,
908            min_confirm_batch: DEFAULT_MIN_CONFIRM_BATCH,
909            stats: ConfirmStats::default(),
910        })
911    }
912
913    /// Sets the minimum live-candidate region size dispatched to the device.
914    ///
915    /// Zero forces every routed confirm through WGPU (parity testing);
916    /// `usize::MAX` disables the device path without dropping residency.
917    pub fn with_min_confirm_batch(mut self, min_confirm_batch: usize) -> Self {
918        self.min_confirm_batch = min_confirm_batch;
919        self
920    }
921
922    /// Changes the minimum live-candidate region size dispatched to the device.
923    pub fn set_min_confirm_batch(&mut self, min_confirm_batch: usize) {
924        self.min_confirm_batch = min_confirm_batch;
925    }
926
927    /// Returns the minimum live-candidate region size dispatched to the device.
928    pub fn min_confirm_batch(&self) -> usize {
929        self.min_confirm_batch
930    }
931
932    /// Returns the canonical CPU archive wrapped by this adapter.
933    pub fn archive(&self) -> &SuccinctArchive<U> {
934        &self.archive
935    }
936
937    /// Removes the resident adapter and returns its canonical CPU archive.
938    pub fn into_archive(self) -> SuccinctArchive<U> {
939        self.archive
940    }
941
942    /// Returns the compatibility domain shared by all resident components.
943    pub fn context(&self) -> &WgpuContext {
944        &self.context
945    }
946
947    /// Returns a snapshot of this wrapper's confirm dispatch counters.
948    pub fn stats(&self) -> WgpuConfirmStats {
949        self.stats.snapshot()
950    }
951
952    /// Resets this wrapper's confirm dispatch counters.
953    pub fn reset_stats(&self) {
954        self.stats.reset();
955    }
956
957    /// Returns the resident last-column mirror of `rotation`.
958    pub fn ring_col(&self, rotation: SuccinctRotation) -> &WgpuWaveletMatrix {
959        &self.ring[rotation.index()]
960    }
961
962    fn axis_bounds_buffer(&self, axis: Axis) -> &DeviceU32Buffer<WgpuRuntime> {
963        match axis {
964            Axis::Entity => &self.e_bounds,
965            Axis::Attribute => &self.a_bounds,
966            Axis::Value => &self.v_bounds,
967        }
968    }
969
970    fn elemwise(&self, len: usize) -> (CubeCount, CubeDim) {
971        let cube_dim = CubeDim::new_1d(THREADS);
972        let cube_count =
973            cubecl::calculate_cube_count_elemwise(self.context.client(), len, cube_dim);
974        (cube_count, cube_dim)
975    }
976
977    /// Rejects a device whose planes are not exactly 32 lanes wide.
978    ///
979    /// The packed kernels put ballot bit `L` in word bit `L` and store one
980    /// word per plane from its lane 0, reading ballot component 0. That is
981    /// correct iff a plane is exactly 32 lanes: narrower and several planes
982    /// share a word, each storing it whole (lost update); wider and lane 32
983    /// stores the *next* word out of component 0 instead of component 1.
984    /// Neither failure has any symptom other than wrong query answers, and
985    /// the supported hardware (NVIDIA warps, Apple Silicon — where cubecl
986    /// hardcodes 32) always satisfies it, so this is a guard against a
987    /// surprise adapter rather than a portability layer. `Plane::Ops` is
988    /// checked in the same breath because without it the shader's
989    /// `enable subgroups;` directive is rejected at pipeline creation.
990    ///
991    /// Returning an error rather than branching keeps the demotion honest:
992    /// `Constraint::confirm` counts it as a device error and recomputes the
993    /// region on the CPU arm.
994    fn require_plane_packing(&self) -> jerky::Result<()> {
995        use cubecl::ir::features::Plane;
996
997        let properties = self.context.client().properties();
998        if !properties.features.plane.contains(Plane::Ops) {
999            return Err(jerky::Error::invalid_argument(
1000                "device does not support plane (subgroup) operations",
1001            ));
1002        }
1003        let (min, max) = (
1004            properties.hardware.plane_size_min,
1005            properties.hardware.plane_size_max,
1006        );
1007        if min != 32 || max != 32 {
1008            return Err(jerky::Error::invalid_argument(format!(
1009                "packed confirm needs a plane size of exactly 32, device reports {min}..={max}"
1010            )));
1011        }
1012        Ok(())
1013    }
1014
1015    /// Device evaluation of one unbound membership arm: one fused kernel,
1016    /// one readback, one AND into the region's liveness.
1017    ///
1018    /// The verdict buffer and its dispatch are sized from the region's *word*
1019    /// geometry — `bit_offset` and `live_word_len`, never the candidate count
1020    /// — because a region's candidates start at an arbitrary bit of its first
1021    /// word.
1022    fn confirm_membership_gpu(&self, axis: Axis, cands: &mut Candidates<'_>) -> jerky::Result<()> {
1023        let n = cands.len();
1024        self.require_plane_packing()?;
1025
1026        let bit_offset = cands.bit_offset();
1027        let words = cands.live_word_len();
1028        let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
1029        let mut live = cands.live_words();
1030        let live_words = self.context.upload_u32(&live)?;
1031        let mut verdict_words = self.context.empty_u32(words)?;
1032
1033        // Bit slots, not candidates: the kernel's flat index is a bit
1034        // position, and the region's first `bit_offset` bits belong to the
1035        // neighbour below it.
1036        let (cube_count, cube_dim) = self.elemwise(bit_offset + n);
1037        unsafe {
1038            membership_confirm_ballot_kernel::launch_unchecked::<WgpuRuntime>(
1039                self.context.client(),
1040                cube_count,
1041                cube_dim,
1042                cand_words.input_arg(),
1043                live_words.input_arg(),
1044                self.universe_words.input_arg(),
1045                self.axis_bounds_buffer(axis).input_arg(),
1046                verdict_words.output_arg(),
1047                n as u32,
1048                self.domain_len as u32,
1049                bit_offset as u32,
1050            )
1051        };
1052
1053        let verdicts = verdict_words.read();
1054        and_words(&mut live, &verdicts);
1055        cands.set_live_words(&live);
1056        Ok(())
1057    }
1058
1059    /// Device evaluation of one **single-bound** range arm: probe fill
1060    /// (which resolves each candidate's parent band inline), Jerky's batched
1061    /// wavelet rank, and verdict fold — three dispatches, one readback, one
1062    /// AND into the region's liveness.
1063    ///
1064    /// `slots` maps candidate `i` to its parent's row in `parent_values`, so
1065    /// one dispatch serves a region spanning the whole frontier.
1066    fn confirm_base_gpu(
1067        &self,
1068        axis: Axis,
1069        rotation: SuccinctRotation,
1070        slots: &[u32],
1071        parent_values: &[RawInline],
1072        cands: &mut Candidates<'_>,
1073    ) -> jerky::Result<()> {
1074        let n = cands.len();
1075        self.require_plane_packing()?;
1076
1077        let bit_offset = cands.bit_offset() as u32;
1078        let slot_words = self.context.upload_u32(slots)?;
1079        let value_words = self.context.upload_u32(&pack_be_words(parent_values))?;
1080        let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
1081        let live_words = self.context.upload_u32(&cands.live_words())?;
1082        let mut flags = self.context.empty_u32(n)?;
1083        let mut positions = self.context.empty_u32(2 * n)?;
1084        let mut probes = self.context.empty_u32(2 * n)?;
1085
1086        // The probe fill stays candidate-indexed (its outputs feed Jerky's
1087        // per-candidate rank batch); only the verdict fold indexes bits.
1088        let (cube_count, cube_dim) = self.elemwise(n);
1089        unsafe {
1090            base_probe_fill_kernel::launch_unchecked::<WgpuRuntime>(
1091                self.context.client(),
1092                cube_count,
1093                cube_dim,
1094                cand_words.input_arg(),
1095                live_words.input_arg(),
1096                self.universe_words.input_arg(),
1097                slot_words.input_arg(),
1098                value_words.input_arg(),
1099                self.axis_bounds_buffer(axis).input_arg(),
1100                flags.output_arg(),
1101                positions.output_arg(),
1102                probes.output_arg(),
1103                n as u32,
1104                self.domain_len as u32,
1105                bit_offset,
1106            )
1107        };
1108        self.fold_range_verdicts(rotation, &flags, &positions, &probes, cands)
1109    }
1110
1111    /// Device evaluation of one **double-bound** range arm. The parent bands
1112    /// need a wavelet rank of their own, so this shape pays a parent pass —
1113    /// probe fill and one batched rank over the *table*, not the region —
1114    /// before the candidate pass folds each parent's rank into its band.
1115    /// Five dispatches, still one readback.
1116    #[allow(clippy::too_many_arguments)]
1117    fn confirm_restrict_gpu(
1118        &self,
1119        outer: Axis,
1120        inner: Axis,
1121        inner_col: SuccinctRotation,
1122        rotation: SuccinctRotation,
1123        slots: &[u32],
1124        outer_values: &[RawInline],
1125        inner_values: &[RawInline],
1126        cands: &mut Candidates<'_>,
1127    ) -> jerky::Result<()> {
1128        let n = cands.len();
1129        self.require_plane_packing()?;
1130
1131        let bit_offset = cands.bit_offset() as u32;
1132        let p = outer_values.len();
1133        let outer_words = self.context.upload_u32(&pack_be_words(outer_values))?;
1134        let inner_words = self.context.upload_u32(&pack_be_words(inner_values))?;
1135        let mut parent_codes = self.context.empty_u32(p)?;
1136        let mut parent_flags = self.context.empty_u32(p)?;
1137        let mut parent_positions = self.context.empty_u32(2 * p)?;
1138        let mut parent_probes = self.context.empty_u32(2 * p)?;
1139        let mut parent_ranks = self.context.empty_u32(2 * p)?;
1140
1141        let (parent_count, cube_dim) = self.elemwise(p);
1142        unsafe {
1143            parent_restrict_probe_kernel::launch_unchecked::<WgpuRuntime>(
1144                self.context.client(),
1145                parent_count,
1146                cube_dim,
1147                self.universe_words.input_arg(),
1148                self.axis_bounds_buffer(outer).input_arg(),
1149                outer_words.input_arg(),
1150                inner_words.input_arg(),
1151                parent_codes.output_arg(),
1152                parent_flags.output_arg(),
1153                parent_positions.output_arg(),
1154                parent_probes.output_arg(),
1155                p as u32,
1156                self.domain_len as u32,
1157            )
1158        };
1159        self.ring_col(inner_col).rank_batch_into(
1160            &parent_positions,
1161            &parent_probes,
1162            &mut parent_ranks,
1163        )?;
1164
1165        let slot_words = self.context.upload_u32(slots)?;
1166        let cand_words = self.context.upload_u32(&pack_be_words(cands.values()))?;
1167        let live_words = self.context.upload_u32(&cands.live_words())?;
1168        let mut flags = self.context.empty_u32(n)?;
1169        let mut positions = self.context.empty_u32(2 * n)?;
1170        let mut probes = self.context.empty_u32(2 * n)?;
1171
1172        let (cube_count, cube_dim) = self.elemwise(n);
1173        unsafe {
1174            restrict_probe_fill_kernel::launch_unchecked::<WgpuRuntime>(
1175                self.context.client(),
1176                cube_count,
1177                cube_dim,
1178                cand_words.input_arg(),
1179                live_words.input_arg(),
1180                self.universe_words.input_arg(),
1181                slot_words.input_arg(),
1182                parent_flags.input_arg(),
1183                parent_codes.input_arg(),
1184                parent_ranks.input_arg(),
1185                self.axis_bounds_buffer(inner).input_arg(),
1186                flags.output_arg(),
1187                positions.output_arg(),
1188                probes.output_arg(),
1189                n as u32,
1190                self.domain_len as u32,
1191                RANK_OUT_OF_RANGE,
1192                bit_offset,
1193            )
1194        };
1195        self.fold_range_verdicts(rotation, &flags, &positions, &probes, cands)
1196    }
1197
1198    /// The tail both range arms share: Jerky's batched wavelet rank over the
1199    /// filled probes, the verdict fold, one readback, one word-wise AND into
1200    /// the region's liveness.
1201    fn fold_range_verdicts(
1202        &self,
1203        rotation: SuccinctRotation,
1204        flags: &DeviceU32Buffer<WgpuRuntime>,
1205        positions: &DeviceU32Buffer<WgpuRuntime>,
1206        probes: &DeviceU32Buffer<WgpuRuntime>,
1207        cands: &mut Candidates<'_>,
1208    ) -> jerky::Result<()> {
1209        let n = cands.len();
1210        let bit_offset = cands.bit_offset();
1211        let mut ranks = self.context.empty_u32(2 * n)?;
1212        let mut verdict_words = self.context.empty_u32(cands.live_word_len())?;
1213        self.ring_col(rotation)
1214            .rank_batch_into(positions, probes, &mut ranks)?;
1215
1216        // Bit slots, not candidates — see `membership_confirm_ballot_kernel`.
1217        let (cube_count, cube_dim) = self.elemwise(bit_offset + n);
1218        unsafe {
1219            range_verdict_ballot_kernel::launch_unchecked::<WgpuRuntime>(
1220                self.context.client(),
1221                cube_count,
1222                cube_dim,
1223                flags.input_arg(),
1224                ranks.input_arg(),
1225                verdict_words.output_arg(),
1226                n as u32,
1227                RANK_OUT_OF_RANGE,
1228                bit_offset as u32,
1229            )
1230        };
1231
1232        let verdicts = verdict_words.read();
1233        let mut live = cands.live_words();
1234        and_words(&mut live, &verdicts);
1235        cands.set_live_words(&live);
1236        Ok(())
1237    }
1238}
1239
1240impl<U> TriblePattern for WgpuSuccinctArchive<U>
1241where
1242    U: Universe + Send + Sync,
1243{
1244    type PatternConstraint<'a>
1245        = WgpuSuccinctArchiveConstraint<'a, U>
1246    where
1247        U: 'a;
1248
1249    fn pattern<'a, V: InlineEncoding>(
1250        &'a self,
1251        e: impl Into<Term<GenId>>,
1252        a: impl Into<Term<GenId>>,
1253        v: impl Into<Term<V>>,
1254    ) -> Self::PatternConstraint<'a> {
1255        WgpuSuccinctArchiveConstraint::new(e, a, v, self)
1256    }
1257}
1258
1259/// The canonical [`SuccinctArchiveConstraint`] with device-batched confirm.
1260///
1261/// Every protocol method except [`confirm`](Constraint::confirm) delegates to
1262/// the wrapped CPU constraint verbatim. `confirm` mirrors the CPU arm
1263/// dispatch; regions with at least
1264/// [`min_confirm_batch`](WgpuSuccinctArchive::min_confirm_batch) live
1265/// candidates run their probes on the device, everything else (including any
1266/// device error) falls back to the CPU arm. Both paths satisfy the kill-only
1267/// contract — the device path merges verdicts by word-wise AND, so it can
1268/// never revive a dead entry.
1269pub struct WgpuSuccinctArchiveConstraint<'a, U>
1270where
1271    U: Universe,
1272{
1273    inner: SuccinctArchiveConstraint<'a, U>,
1274    gpu: &'a WgpuSuccinctArchive<U>,
1275    term_e: RawTerm,
1276    term_a: RawTerm,
1277    term_v: RawTerm,
1278}
1279
1280impl<'a, U> WgpuSuccinctArchiveConstraint<'a, U>
1281where
1282    U: Universe,
1283{
1284    /// Builds the constraint over `gpu`'s wrapped archive. Each position
1285    /// takes a [`Term`]: a variable to solve for or a constant pinned at
1286    /// construction (constants never enter the variable set and enter the
1287    /// arm dispatch as born-bound, exactly as on the CPU constraint).
1288    pub fn new<V: InlineEncoding>(
1289        e: impl Into<Term<GenId>>,
1290        a: impl Into<Term<GenId>>,
1291        v: impl Into<Term<V>>,
1292        gpu: &'a WgpuSuccinctArchive<U>,
1293    ) -> Self {
1294        let e: Term<GenId> = e.into();
1295        let a: Term<GenId> = a.into();
1296        let v: Term<V> = v.into();
1297        WgpuSuccinctArchiveConstraint {
1298            inner: SuccinctArchiveConstraint::new(e, a, v, &gpu.archive),
1299            gpu,
1300            term_e: e.erase(),
1301            term_a: a.erase(),
1302            term_v: v.erase(),
1303        }
1304    }
1305
1306    fn term(&self, axis: Axis) -> &RawTerm {
1307        match axis {
1308            Axis::Entity => &self.term_e,
1309            Axis::Attribute => &self.term_a,
1310            Axis::Value => &self.term_v,
1311        }
1312    }
1313
1314    /// Which shape of probe this confirm is, classified once for the whole
1315    /// batch from any row — every row of a frontier shares its bound set, so
1316    /// they all classify the same.
1317    fn plan(&self, variable: VariableId, binding: &Binding) -> ConfirmPlan {
1318        let e_var = self.term_e.is_var(variable);
1319        let a_var = self.term_a.is_var(variable);
1320        let v_var = self.term_v.is_var(variable);
1321
1322        let e_bound = self.term_e.position_value(binding).is_some();
1323        let a_bound = self.term_a.position_value(binding).is_some();
1324        let v_bound = self.term_v.position_value(binding).is_some();
1325
1326        match (e_bound, a_bound, v_bound, e_var, a_var, v_var) {
1327            (false, false, false, true, false, false) => {
1328                ConfirmPlan::Membership { axis: Axis::Entity }
1329            }
1330            (false, false, false, false, true, false) => ConfirmPlan::Membership {
1331                axis: Axis::Attribute,
1332            },
1333            (false, false, false, false, false, true) => {
1334                ConfirmPlan::Membership { axis: Axis::Value }
1335            }
1336            (true, false, false, false, true, false) => ConfirmPlan::Base {
1337                bound: Axis::Entity,
1338                rotation: SuccinctRotation::Eva,
1339            },
1340            (true, false, false, false, false, true) => ConfirmPlan::Base {
1341                bound: Axis::Entity,
1342                rotation: SuccinctRotation::Eav,
1343            },
1344            (false, true, false, true, false, false) => ConfirmPlan::Base {
1345                bound: Axis::Attribute,
1346                rotation: SuccinctRotation::Ave,
1347            },
1348            (false, true, false, false, false, true) => ConfirmPlan::Base {
1349                bound: Axis::Attribute,
1350                rotation: SuccinctRotation::Aev,
1351            },
1352            (false, false, true, true, false, false) => ConfirmPlan::Base {
1353                bound: Axis::Value,
1354                rotation: SuccinctRotation::Vae,
1355            },
1356            (false, false, true, false, true, false) => ConfirmPlan::Base {
1357                bound: Axis::Value,
1358                rotation: SuccinctRotation::Vea,
1359            },
1360            (false, true, true, true, false, false) => ConfirmPlan::Restrict {
1361                outer: Axis::Attribute,
1362                inner: Axis::Value,
1363                inner_col: SuccinctRotation::Aev,
1364                rotation: SuccinctRotation::Vae,
1365            },
1366            (true, false, true, false, true, false) => ConfirmPlan::Restrict {
1367                outer: Axis::Entity,
1368                inner: Axis::Value,
1369                inner_col: SuccinctRotation::Eav,
1370                rotation: SuccinctRotation::Vea,
1371            },
1372            (true, true, false, false, false, true) => ConfirmPlan::Restrict {
1373                outer: Axis::Entity,
1374                inner: Axis::Attribute,
1375                inner_col: SuccinctRotation::Eva,
1376                rotation: SuccinctRotation::Aev,
1377            },
1378            _ => unreachable!("invalid trible constraint state"),
1379        }
1380    }
1381
1382    /// The `axis` position's value in each of the frontier rows named by
1383    /// `rows` — the parent table's payload.
1384    fn parent_values(
1385        &self,
1386        axis: Axis,
1387        frontier: &Frontier<'_>,
1388        rows: &[u32],
1389    ) -> jerky::Result<Vec<RawInline>> {
1390        let term = self.term(axis);
1391        let mut values = Vec::with_capacity(rows.len());
1392        for &row in rows {
1393            let binding = frontier.row(row as usize);
1394            let value = term.position_value(&binding).ok_or_else(|| {
1395                jerky::Error::invalid_argument(format!(
1396                    "frontier row {row} left a bound position of the arm unbound"
1397                ))
1398            })?;
1399            values.push(*value);
1400        }
1401        Ok(values)
1402    }
1403
1404    /// The device evaluation of one confirm call over a whole frontier,
1405    /// mirroring the CPU arm dispatch. Returns the number of parent-table
1406    /// rows the dispatch resolved.
1407    fn confirm_gpu(
1408        &self,
1409        variable: VariableId,
1410        frontier: &Frontier<'_>,
1411        cands: &mut Candidates<'_>,
1412    ) -> jerky::Result<usize> {
1413        match self.plan(variable, &frontier.row(0)) {
1414            ConfirmPlan::Membership { axis } => {
1415                self.gpu.confirm_membership_gpu(axis, cands)?;
1416                Ok(0)
1417            }
1418            ConfirmPlan::Base { bound, rotation } => {
1419                let (slots, rows) = parent_table(frontier, cands)?;
1420                let values = self.parent_values(bound, frontier, &rows)?;
1421                self.gpu
1422                    .confirm_base_gpu(bound, rotation, &slots, &values, cands)?;
1423                Ok(rows.len())
1424            }
1425            ConfirmPlan::Restrict {
1426                outer,
1427                inner,
1428                inner_col,
1429                rotation,
1430            } => {
1431                let (slots, rows) = parent_table(frontier, cands)?;
1432                let outer_values = self.parent_values(outer, frontier, &rows)?;
1433                let inner_values = self.parent_values(inner, frontier, &rows)?;
1434                self.gpu.confirm_restrict_gpu(
1435                    outer,
1436                    inner,
1437                    inner_col,
1438                    rotation,
1439                    &slots,
1440                    &outer_values,
1441                    &inner_values,
1442                    cands,
1443                )?;
1444                Ok(rows.len())
1445            }
1446        }
1447    }
1448}
1449
1450impl<'a, U> Constraint<'a> for WgpuSuccinctArchiveConstraint<'a, U>
1451where
1452    U: Universe,
1453{
1454    fn variables(&self) -> VariableSet {
1455        self.inner.variables()
1456    }
1457
1458    fn estimate(&self, variable: VariableId, binding: &Binding) -> Option<usize> {
1459        self.inner.estimate(variable, binding)
1460    }
1461
1462    fn propose(
1463        &self,
1464        variable: VariableId,
1465        frontier: &Frontier<'_>,
1466        proposals: &mut ProposalBuffer,
1467    ) {
1468        self.inner.propose(variable, frontier, proposals)
1469    }
1470
1471    fn confirm(&self, variable: VariableId, frontier: &Frontier<'_>, cands: &mut Candidates<'_>) {
1472        if !self.term_e.is_var(variable)
1473            && !self.term_a.is_var(variable)
1474            && !self.term_v.is_var(variable)
1475        {
1476            return;
1477        }
1478        if frontier.is_empty() || cands.is_empty() {
1479            return;
1480        }
1481        let live = count_live(cands);
1482        if live < self.gpu.min_confirm_batch {
1483            self.gpu.stats.record_cpu(cands.len());
1484            self.inner.confirm(variable, frontier, cands);
1485            return;
1486        }
1487        match self.confirm_gpu(variable, frontier, cands) {
1488            Ok(parents) => self.gpu.stats.record_gpu(cands.len(), parents),
1489            Err(_) => {
1490                // The helpers only write liveness after a complete verdict
1491                // readback, so a failed dispatch left the region untouched
1492                // and the CPU arm computes it from scratch.
1493                self.gpu.stats.record_error();
1494                self.inner.confirm(variable, frontier, cands);
1495            }
1496        }
1497    }
1498
1499    fn satisfied(&self, binding: &Binding) -> bool {
1500        self.inner.satisfied(binding)
1501    }
1502
1503    fn influence(&self, variable: VariableId) -> VariableSet {
1504        self.inner.influence(variable)
1505    }
1506}