exatok 0.1.1

Exact GPU-resident BPE tokenizer whose token ids match tiktoken byte for byte
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
//! Device-resident merge-rank table. OWNER: GpuHash.
//!
//! Composes `vyre_primitives::hash::table`. That table is u32-keyed while a
//! pair key needs 36+ bits, so this module probes on
//! [`crate::PairKey::probe_hash`] and verifies the full 64-bit key on hit.
//!
//! Acceptance: a full vocabulary uploaded and looked up on device returns
//! ranks identical to a host map for present pairs and the miss sentinel for
//! absent ones, including at maximum table load.
//!
//! # Wide-key open addressing
//!
//! `vyre_primitives::hash::table::hash_lookup` compares one u32 slot key
//! against one u32 query, so it cannot host a 64-bit pair key: two distinct
//! pairs sharing a probe hash would be indistinguishable and one would return
//! the other's rank. This module keeps the same bounded-linear-probe protocol
//! and stores the key as two u32 words, `key_lo` (the right token) and `key_hi`
//! (the left token). A slot is a hit only when BOTH words equal the query, so a
//! probe-hash collision walks on to the next slot instead of returning a wrong
//! rank.
//!
//! Two u32 words rather than one [`vyre::ir::DataType::U64`] because vyre
//! emulates `U64` as `vec2<u32>` anyway, so the split form costs nothing and
//! keeps every load on the natively supported word type.
//!
//! # Slot layout
//!
//! One slot is [`SLOT_WORDS`] contiguous u32 words, interleaved rather than
//! split into four parallel planes:
//!
//! ```text
//!   slot s  ->  [ key_lo | key_hi | rank | merged id ]
//!               s*4 + 0    +1       +2     +3
//! ```
//!
//! A probe is a random access, so the layout decides how many memory
//! transactions it costs. Four planes would put one slot's four words in four
//! distant lines, four transactions per probe, on the single hottest lookup in
//! the tokenizer (measured at 1.53 to 3.02 pair-table probes per input byte).
//! Interleaved, a slot is 16 contiguous bytes: one transaction, and the next
//! slot in the probe walk usually arrives in the same line, which is exactly
//! what bounded linear probing wants.
//!
//! # Occupancy without a key sentinel
//!
//! `hash_insert` reserves `u32::MAX` and `u32::MAX - 1` as key sentinels. A
//! pair key cannot afford that: `(TokenId(u32::MAX), TokenId(u32::MAX))` is a
//! representable pair and must be storable. Occupancy therefore lives in the
//! rank word: a slot is empty exactly when its rank is [`Rank::ABSENT`], which
//! is already the miss sentinel and is never a real merge rank. The key words
//! carry no reserved value at all, so every pair key is storable, and an
//! all-zero empty slot cannot be mistaken for a hit on
//! `(TokenId(0), TokenId(0))`.
//!
//! # Probe bound
//!
//! Lookup probes at most [`RankTable::window`] slots from the home slot, which
//! is the longest probe any key in THAT table actually needed. Sound in both
//! directions: a present key is inside the bound by construction, and an absent
//! key is a miss wherever the walk stops. So the bound is measured, not guessed,
//! and a real vocabulary runs 12 iterations where the [`MAX_PROBE_LENGTH`] cap
//! would have run 32. The cap only decides when construction gives up on a
//! capacity and rehashes into a larger one.
//!
//! Load factor decides that bound. Measured over 446189 keys shaped like a real
//! derived pair table (the dense 256x256 byte-pair block plus a diffuse fill
//! over the o200k id range), the longest probe is 28 slots at load 0.43 and 9 to
//! 14 slots at load 0.25. Since the probe bound is what every lane pays on the
//! hottest lookup, [`RankTable::from_entries`] sizes for load 0.25.
//!
//! Insertion is host-side: a merge table is built once from a vocabulary
//! artifact and uploaded read-only, so device-side CAS insertion would buy
//! nothing and cost a probe of atomics.
//!
//! # Relationship to the host oracle
//!
//! [`RankTable`] implements [`MergeTable`], so the exact words uploaded to the
//! device also drive [`crate::reference::encode_pretoken`]. A parity failure is
//! then a real device divergence rather than two tables that were never the
//! same table.

use vyre::ir::model::expr::GeneratorRef;
use vyre::ir::{BufferDecl, DataType, Expr, Node, Program};
use vyre_driver::DispatchConfig;
use vyre_libs::region::{wrap_anonymous, wrap_child};
use vyre_primitives::hash::fnv1a::{fnv1a32_initial_expr, fnv1a32_update_byte_expr};

use crate::reference::{MergeEntry, MergeTable};
use crate::{PairKey, Rank, TokenId, ExatokError};

/// Op id of the standalone lookup program.
///
/// `exatok::` because this crate is a Tier 4 external pack. A `vyre-libs::`
/// prefix is reserved for Tier 3 and the tier audit greps for it.
pub const LOOKUP_OP_ID: &str = "exatok::gpu_rank_table::lookup";

/// Op id of the probe fragment, emitted as a child region of whichever op
/// composes it.
pub const PROBE_OP_ID: &str = "exatok::gpu_rank_table::probe";

/// u32 words per slot: `key_lo`, `key_hi`, `rank`, `merged id`.
pub const SLOT_WORDS: u32 = 4;

/// Word offset of the right token within a slot.
pub const SLOT_KEY_LO: u32 = 0;
/// Word offset of the left token within a slot.
pub const SLOT_KEY_HI: u32 = 1;
/// Word offset of the rank, which is also the occupancy marker.
pub const SLOT_RANK: u32 = 2;
/// Word offset of the merged token id.
pub const SLOT_ID: u32 = 3;

/// Longest probe construction will tolerate before growing the table.
///
/// One warp's worth. This is a CAP, not the device loop bound: the bound is
/// [`RankTable::window`], the longest probe the built table actually needs. When
/// a key cannot be placed within this many slots of its home,
/// [`RankTable::from_entries`] doubles the capacity and rehashes rather than
/// widening the loop every lane pays for.
pub const MAX_PROBE_LENGTH: u32 = 32;

/// Largest table capacity this module will allocate, in slots.
///
/// 2^24 slots is 2^26 words, so a `with_count` that still fits u32, and holds
/// four times the rows of the largest published BPE vocabulary at the build
/// load factor.
pub const MAX_CAPACITY: u32 = 1 << 24;

/// Query buffer holding each pair's right token.
pub const PAIR_LO_BUFFER: &str = "pair_lo";
/// Query buffer holding each pair's left token.
pub const PAIR_HI_BUFFER: &str = "pair_hi";
/// Uploaded table: `capacity * SLOT_WORDS` interleaved words.
pub const TABLE_SLOTS_BUFFER: &str = "table_slots";
/// Sole output buffer, `2 * lanes` words: ranks in `[0, lanes)`, merged ids in
/// `[lanes, 2 * lanes)`.
///
/// Two contiguous planes rather than one interleaved pair per lane, and one
/// buffer rather than two, because vyre admits at most one output marker per
/// program (V022). The rank plane stays contiguous so a consumer reducing over
/// ranks reads a dense range instead of striding past ids it does not want.
pub const OUT_BUFFER: &str = "out_probe";

/// Workgroup width of [`lookup_program`].
pub const LOOKUP_WORKGROUP: u32 = 256;

/// Slots per row [`RankTable::from_entries`] sizes for, before rounding up to a
/// power of two. Four pins the load factor into `(0.125, 0.25]`.
const SLOTS_PER_ROW: u64 = 4;

/// Artifact name used by diagnostics that describe the table itself rather than
/// a row of some named vocabulary file.
const TABLE_ARTIFACT: &str = "merge rank table";

/// Outcome of placing one row into a table.
///
/// Separate from `Result` because [`RankTable::from_entries`] treats an
/// exhausted probe window as "grow and retry" while a duplicate pair is fatal,
/// and a single error type would collapse the two.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Placement {
    /// The row now owns a slot.
    Placed,
    /// The pair is already in the table, holding the rank carried here.
    Duplicate(Rank),
    /// Every slot within [`MAX_PROBE_LENGTH`] of the home slot is occupied by
    /// another key.
    WindowExhausted,
}

/// A host-built merge-rank table, laid out exactly as the words uploaded to the
/// device.
///
/// Capacity is always a power of two so the home slot is a mask rather than a
/// modulo, which matters on device where integer division is microcoded.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RankTable {
    capacity: u32,
    limit: u32,
    len: u32,
    max_probe: u32,
    slots: Vec<u32>,
}

impl RankTable {
    /// Allocate an empty table with exactly `capacity` slots.
    ///
    /// `capacity` MUST be a non-zero power of two no greater than
    /// [`MAX_CAPACITY`]. Prefer [`RankTable::from_entries`], which sizes and
    /// grows the table; this is for callers that need an exact capacity.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Artifact`] when `capacity` is zero, not a power
    /// of two, or above [`MAX_CAPACITY`].
    pub fn with_capacity(capacity: u32) -> Result<Self, ExatokError> {
        if capacity == 0 || !capacity.is_power_of_two() {
            return Err(ExatokError::Artifact {
                artifact: TABLE_ARTIFACT.to_owned(),
                location: format!("capacity {capacity}"),
                detail: "table capacity must be a non-zero power of two so the home slot is a bit mask".to_owned(),
                fix: "round the capacity up with u32::next_power_of_two, or call RankTable::from_entries which sizes it".to_owned(),
            });
        }
        if capacity > MAX_CAPACITY {
            return Err(ExatokError::Artifact {
                artifact: TABLE_ARTIFACT.to_owned(),
                location: format!("capacity {capacity}"),
                detail: format!("capacity exceeds the {MAX_CAPACITY} slot ceiling"),
                fix: "shard the merge table across several uploads, or raise gpu_rank_table::MAX_CAPACITY after checking device memory".to_owned(),
            });
        }
        let mut slots = vec![0_u32; capacity as usize * SLOT_WORDS as usize];
        for slot in 0..capacity as usize {
            slots[slot * SLOT_WORDS as usize + SLOT_RANK as usize] = Rank::ABSENT.0;
        }
        Ok(Self {
            capacity,
            limit: capacity.min(MAX_PROBE_LENGTH),
            len: 0,
            max_probe: 0,
            slots,
        })
    }

    /// Build a table from `(pair, merged id, rank)` triples.
    ///
    /// Same input shape as [`crate::reference::HostMergeTable::from_entries`],
    /// so one parsed vocabulary drives the host oracle and the device upload
    /// without a second conversion. `artifact` names the source for error
    /// reporting, for example `cl100k_base.tiktoken`.
    ///
    /// Sizes capacity for a load factor of at most 1/4 and doubles it if any key
    /// would land further than [`MAX_PROBE_LENGTH`] from its home slot, so a
    /// successful build bounds every lookup by [`RankTable::window`].
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Artifact`] when a row carries [`Rank::ABSENT`]
    /// (the empty-slot marker, not a rank), when two rows share a pair, or when
    /// no capacity up to [`MAX_CAPACITY`] admits every key.
    pub fn from_entries(
        artifact: &str,
        entries: impl IntoIterator<Item = (PairKey, TokenId, Rank)>,
    ) -> Result<Self, ExatokError> {
        let rows: Vec<(PairKey, TokenId, Rank)> = entries.into_iter().collect();
        for &(pair, _, rank) in &rows {
            if !rank.is_present() {
                return Err(absent_rank_error(artifact, pair));
            }
        }
        let mut capacity = Self::capacity_for(rows.len())?;
        loop {
            let mut table = Self::with_capacity(capacity)?;
            let mut exhausted = false;
            for &(pair, id, rank) in &rows {
                match table.place(pair, id, rank) {
                    Placement::Placed => {}
                    Placement::Duplicate(existing) => {
                        return Err(duplicate_error(artifact, pair, existing, rank));
                    }
                    Placement::WindowExhausted => {
                        exhausted = true;
                        break;
                    }
                }
            }
            if !exhausted {
                return Ok(table);
            }
            capacity = capacity
                .checked_mul(2)
                .filter(|grown| *grown <= MAX_CAPACITY)
                .ok_or_else(|| ExatokError::Artifact {
                    artifact: artifact.to_owned(),
                    location: format!("{} rows at capacity {capacity}", rows.len()),
                    detail: format!(
                        "a key still exceeded the {MAX_PROBE_LENGTH} slot probe cap at the {MAX_CAPACITY} slot ceiling"
                    ),
                    fix: "shard the merge table, or widen gpu_rank_table::MAX_PROBE_LENGTH".to_owned(),
                })?;
        }
    }

    /// Record one merge, keeping the table valid for device lookup.
    ///
    /// Same signature as [`crate::reference::HostMergeTable::insert`]. The table
    /// is left unchanged when a check fails.
    ///
    /// # Errors
    ///
    /// Returns [`ExatokError::Artifact`] when `rank` is [`Rank::ABSENT`], when
    /// `pair` is already present, or when every slot in the pair's probe window
    /// is taken. Insertion never grows the table, so a full window is reported
    /// rather than silently rehashed: [`RankTable::from_entries`] is the growing
    /// path.
    pub fn insert(
        &mut self,
        artifact: &str,
        pair: PairKey,
        id: TokenId,
        rank: Rank,
    ) -> Result<(), ExatokError> {
        if !rank.is_present() {
            return Err(absent_rank_error(artifact, pair));
        }
        match self.place(pair, id, rank) {
            Placement::Placed => Ok(()),
            Placement::Duplicate(existing) => Err(duplicate_error(artifact, pair, existing, rank)),
            Placement::WindowExhausted => Err(ExatokError::Artifact {
                artifact: artifact.to_owned(),
                location: format!(
                    "{} at home slot {}",
                    pair_location(pair),
                    self.home_slot(pair)
                ),
                detail: format!(
                    "all {} slots within {MAX_PROBE_LENGTH} of the home slot are occupied ({} of {} slots used)",
                    self.limit, self.len, self.capacity
                ),
                fix: "rebuild with RankTable::from_entries, which sizes capacity for the row count and grows on window exhaustion".to_owned(),
            }),
        }
    }

    /// Home slot for `pair`: the probe hash masked to the capacity.
    ///
    /// Public so a caller can construct two pairs that collide here and prove
    /// the full-key verification separates them.
    #[must_use]
    pub fn home_slot(&self, pair: PairKey) -> u32 {
        pair.probe_hash() & (self.capacity - 1)
    }

    /// Slot count. Always a power of two.
    #[must_use]
    pub const fn capacity(&self) -> u32 {
        self.capacity
    }

    /// Slots a lookup probes from the home slot, on host and on device.
    ///
    /// The longest probe any key in this table needed, recorded at insertion,
    /// and therefore the exact trip count [`lookup_program`] must use. Sound in
    /// both directions: a present key is inside this bound by construction, and
    /// an absent key is a miss wherever the walk stops. One for an empty table,
    /// never above `min(capacity, MAX_PROBE_LENGTH)`.
    ///
    /// Read this AFTER the last [`RankTable::insert`]: a later insert can widen
    /// it, and a program built against the older, narrower bound would then miss
    /// on a key the table really holds.
    #[must_use]
    pub const fn window(&self) -> u32 {
        if self.max_probe == 0 {
            1
        } else {
            self.max_probe
        }
    }

    /// Occupied slot count.
    #[must_use]
    pub const fn len(&self) -> u32 {
        self.len
    }

    /// True when no row has been inserted.
    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// The uploaded words, `capacity * SLOT_WORDS` of them, ready for
    /// [`TABLE_SLOTS_BUFFER`].
    #[must_use]
    pub fn slot_words(&self) -> &[u32] {
        &self.slots
    }

    /// Pack every input buffer of [`lookup_program`] in declaration order.
    ///
    /// The returned vector is the `inputs` argument of
    /// `VyreBackend::dispatch`; [`OUT_BUFFER`] is backend-allocated.
    #[must_use]
    pub fn dispatch_inputs(&self, pairs: &[PairKey]) -> Vec<Vec<u8>> {
        let (pair_lo, pair_hi) = pack_pair_columns(pairs);
        let pack = vyre_primitives::wire::pack_u32_slice;
        vec![pack(&pair_lo), pack(&pair_hi), pack(&self.slots)]
    }

    /// Build the lookup program matching this table's capacity and probe bound.
    ///
    /// # Errors
    ///
    /// Propagates [`lookup_program`]'s errors, so a zero-lane dispatch is
    /// refused.
    pub fn lookup_program(&self, lanes: u32) -> Result<Program, ExatokError> {
        lookup_program(self.capacity, self.window(), lanes)
    }

    /// Smallest admissible capacity for `rows` at the build load factor.
    fn capacity_for(rows: usize) -> Result<u32, ExatokError> {
        let rows = rows as u64;
        let target = rows
            .saturating_mul(SLOTS_PER_ROW)
            .max(1)
            .next_power_of_two();
        u32::try_from(target)
            .ok()
            .filter(|capacity| *capacity <= MAX_CAPACITY)
            .ok_or_else(|| ExatokError::Artifact {
                artifact: TABLE_ARTIFACT.to_owned(),
                location: format!("{rows} rows"),
                detail: format!(
                    "a quarter-load table for {rows} rows needs {target} slots, above the {MAX_CAPACITY} slot ceiling"
                ),
                fix: "shard the merge table across several uploads".to_owned(),
            })
    }

    /// First word of `slot`.
    const fn base(slot: u32) -> usize {
        slot as usize * SLOT_WORDS as usize
    }

    /// Place a row at the first empty slot in its probe window.
    fn place(&mut self, pair: PairKey, id: TokenId, rank: Rank) -> Placement {
        let (lo, hi) = split_key(pair);
        let home = self.home_slot(pair);
        let mask = self.capacity - 1;
        for step in 0..self.limit {
            let base = Self::base((home + step) & mask);
            if self.slots[base + SLOT_RANK as usize] == Rank::ABSENT.0 {
                self.slots[base + SLOT_KEY_LO as usize] = lo;
                self.slots[base + SLOT_KEY_HI as usize] = hi;
                self.slots[base + SLOT_RANK as usize] = rank.0;
                self.slots[base + SLOT_ID as usize] = id.0;
                self.len += 1;
                self.max_probe = self.max_probe.max(step + 1);
                return Placement::Placed;
            }
            if self.slots[base + SLOT_KEY_LO as usize] == lo
                && self.slots[base + SLOT_KEY_HI as usize] == hi
            {
                return Placement::Duplicate(Rank(self.slots[base + SLOT_RANK as usize]));
            }
        }
        Placement::WindowExhausted
    }
}

impl MergeTable for RankTable {
    /// Host mirror of the device probe, step for step, so a disagreement
    /// between this and a device lookup is a real divergence rather than two
    /// different algorithms.
    fn lookup(&self, pair: PairKey) -> Option<MergeEntry> {
        let (lo, hi) = split_key(pair);
        let home = self.home_slot(pair);
        let mask = self.capacity - 1;
        for step in 0..self.window() {
            let base = Self::base((home + step) & mask);
            let rank = self.slots[base + SLOT_RANK as usize];
            if rank == Rank::ABSENT.0 {
                return None;
            }
            if self.slots[base + SLOT_KEY_LO as usize] == lo
                && self.slots[base + SLOT_KEY_HI as usize] == hi
            {
                return Some(MergeEntry {
                    id: TokenId(self.slots[base + SLOT_ID as usize]),
                    rank: Rank(rank),
                });
            }
        }
        None
    }
}

/// Split a pair key into the two u32 words a slot stores.
///
/// `lo` is the right token, `hi` is the left token, matching the little-endian
/// byte order [`PairKey::probe_hash`] hashes over.
#[must_use]
pub const fn split_key(pair: PairKey) -> (u32, u32) {
    (pair.right().0, pair.left().0)
}

/// Split `pairs` into the `(lo, hi)` query buffers [`lookup_program`] reads.
///
/// Two sequential buffers rather than interleaved: a warp reads 32 consecutive
/// words from each, so both layouts cost the same transactions here. The
/// interleaving in the TABLE is what pays, because that access is random.
#[must_use]
pub fn pack_pair_columns(pairs: &[PairKey]) -> (Vec<u32>, Vec<u32>) {
    let mut lo = Vec::with_capacity(pairs.len());
    let mut hi = Vec::with_capacity(pairs.len());
    for pair in pairs {
        let (pair_lo, pair_hi) = split_key(*pair);
        lo.push(pair_lo);
        hi.push(pair_hi);
    }
    (lo, hi)
}

/// Name of the variable [`probe_nodes`] binds the found rank to.
#[must_use]
pub fn probe_rank_var(prefix: &str) -> String {
    format!("{prefix}_rank")
}

/// Name of the variable [`probe_nodes`] binds the found merged id to.
#[must_use]
pub fn probe_id_var(prefix: &str) -> String {
    format!("{prefix}_id")
}

/// Probe fragment: look one pair up in an uploaded table.
///
/// Binds `probe_rank_var(prefix)` to the pair's rank, or [`Rank::ABSENT`] on a
/// miss, and `probe_id_var(prefix)` to the merged token id, which is only
/// meaningful when the rank is present (it stays zero on a miss). Every other
/// name the fragment binds is prefixed, so the merge loop can inline several
/// probes in one scope.
///
/// `capacity` MUST be the power-of-two [`RankTable::capacity`] of the uploaded
/// table and `window` its [`RankTable::window`]: a device window shorter than
/// the host one turns a legitimately placed key into a miss.
///
/// This is the composition point for the merge loop, which holds tokens in a
/// device buffer and forms pairs in registers. Use [`probe_child`] to get the
/// same body inside its own provenance region, and use it instead of
/// materializing a query buffer and calling [`lookup_program`], which exists
/// for parity testing and standalone dispatch.
#[must_use]
pub fn probe_nodes(
    prefix: &str,
    slots: &str,
    capacity: u32,
    window: u32,
    key_lo: Expr,
    key_hi: Expr,
) -> Vec<Node> {
    let mask = capacity.wrapping_sub(1);
    let lo_var = format!("{prefix}_query_lo");
    let hi_var = format!("{prefix}_query_hi");
    let home_var = format!("{prefix}_home");
    let done_var = format!("{prefix}_done");
    let step_var = format!("{prefix}_step");
    let base_var = format!("{prefix}_base");
    let slot_rank_var = format!("{prefix}_slot_rank");
    let rank_var = probe_rank_var(prefix);
    let id_var = probe_id_var(prefix);

    let slot_rank = Expr::var(slot_rank_var.as_str());
    let base = Expr::var(base_var.as_str());
    let word = |offset: u32| Expr::load(slots, Expr::add(base.clone(), Expr::u32(offset)));
    let occupied = Expr::ne(slot_rank.clone(), Expr::u32(Rank::ABSENT.0));
    let key_matches = Expr::and(
        Expr::eq(word(SLOT_KEY_LO), Expr::var(lo_var.as_str())),
        Expr::eq(word(SLOT_KEY_HI), Expr::var(hi_var.as_str())),
    );

    vec![
        Node::let_bind(lo_var.as_str(), key_lo),
        Node::let_bind(hi_var.as_str(), key_hi),
        Node::let_bind(
            home_var.as_str(),
            Expr::bitand(
                probe_hash_expr(Expr::var(lo_var.as_str()), Expr::var(hi_var.as_str())),
                Expr::u32(mask),
            ),
        ),
        Node::let_bind(rank_var.as_str(), Expr::u32(Rank::ABSENT.0)),
        Node::let_bind(id_var.as_str(), Expr::u32(0)),
        Node::let_bind(done_var.as_str(), Expr::u32(0)),
        Node::loop_for(
            step_var.as_str(),
            Expr::u32(0),
            Expr::u32(window),
            vec![Node::if_then(
                Expr::eq(Expr::var(done_var.as_str()), Expr::u32(0)),
                vec![
                    Node::let_bind(
                        base_var.as_str(),
                        Expr::mul(
                            Expr::bitand(
                                Expr::add(
                                    Expr::var(home_var.as_str()),
                                    Expr::var(step_var.as_str()),
                                ),
                                Expr::u32(mask),
                            ),
                            Expr::u32(SLOT_WORDS),
                        ),
                    ),
                    Node::let_bind(slot_rank_var.as_str(), word(SLOT_RANK)),
                    // An empty slot ends the chain: any key that hashes here and
                    // was placed later probed past a slot occupied at the time,
                    // so nothing reachable lives beyond a hole.
                    Node::if_then(
                        Expr::eq(slot_rank.clone(), Expr::u32(Rank::ABSENT.0)),
                        vec![Node::assign(done_var.as_str(), Expr::u32(1))],
                    ),
                    // Verify the FULL 64-bit key. Matching only the probe hash
                    // would hand back a colliding pair's rank.
                    Node::if_then(
                        Expr::and(occupied, key_matches),
                        vec![
                            Node::assign(rank_var.as_str(), slot_rank),
                            Node::assign(id_var.as_str(), word(SLOT_ID)),
                            Node::assign(done_var.as_str(), Expr::u32(1)),
                        ],
                    ),
                ],
            )],
        ),
    ]
}

/// [`probe_nodes`] plus `then`, inside one region tagged as a child of
/// `parent_op_id`.
///
/// `then` runs after the probe, in the SAME scope, so it can read
/// [`probe_rank_var`] and [`probe_id_var`]. It has to live inside the region
/// rather than after it: a `Node::Region` opens a binding scope, so a consumer
/// placed as the region's sibling fails IR validation with an undeclared
/// variable, and there is no way to hoist a binding out of a region.
///
/// A composing op MUST use this rather than splicing the raw fragment: the
/// region chain is what lets `cargo xtask print-composition` walk from the
/// parent op down to this probe, and a `None` source region breaks that walk.
#[must_use]
pub fn probe_child(
    parent_op_id: &str,
    prefix: &str,
    slots: &str,
    capacity: u32,
    window: u32,
    key_lo: Expr,
    key_hi: Expr,
    then: Vec<Node>,
) -> Node {
    let mut body = probe_nodes(prefix, slots, capacity, window, key_lo, key_hi);
    body.extend(then);
    wrap_child(
        PROBE_OP_ID,
        GeneratorRef {
            name: parent_op_id.to_owned(),
        },
        body,
    )
}

/// Device probe hash over the two key words.
///
/// Byte for byte the same function as [`PairKey::probe_hash`]: FNV-1a32 over the
/// little-endian bytes of `(left << 32) | right`, which is `lo`'s four bytes then
/// `hi`'s four. Built from
/// `vyre_primitives::hash::fnv1a::fnv1a32_update_byte_expr` so the constants
/// cannot fork from the ones the rest of the stack probes with.
fn probe_hash_expr(key_lo: Expr, key_hi: Expr) -> Expr {
    let mut hash = fnv1a32_initial_expr();
    for word in [key_lo, key_hi] {
        // fnv1a32_update_byte_expr masks its byte argument to 0xFF, so the
        // shifted word needs no further masking.
        hash = fnv1a32_update_byte_expr(hash, word.clone());
        for shift in [8_u32, 16, 24] {
            hash = fnv1a32_update_byte_expr(hash, Expr::shr(word.clone(), Expr::u32(shift)));
        }
    }
    hash
}

/// Build the standalone lookup program: one rank and one merged id per query
/// lane.
///
/// Reads `lanes` pair keys from [`PAIR_LO_BUFFER`] and [`PAIR_HI_BUFFER`],
/// probes [`TABLE_SLOTS_BUFFER`], and writes both planes of [`OUT_BUFFER`]. A
/// miss writes [`Rank::ABSENT`] into the rank plane and leaves the id plane zero.
///
/// Prefer [`RankTable::lookup_program`], which supplies `capacity` and `window`
/// from the table being uploaded and so cannot pair a program with a table it
/// does not match.
///
/// # Errors
///
/// Returns [`ExatokError::Artifact`] when `capacity` is not a non-zero power of
/// two, when it exceeds [`MAX_CAPACITY`], when `window` is zero or above
/// `min(capacity, MAX_PROBE_LENGTH)`, or when `lanes` is zero.
pub fn lookup_program(capacity: u32, window: u32, lanes: u32) -> Result<Program, ExatokError> {
    if capacity == 0 || !capacity.is_power_of_two() || capacity > MAX_CAPACITY {
        return Err(ExatokError::Artifact {
            artifact: TABLE_ARTIFACT.to_owned(),
            location: format!("lookup program capacity {capacity}"),
            detail: format!(
                "capacity must be a non-zero power of two no greater than {MAX_CAPACITY}"
            ),
            fix: "pass RankTable::capacity() of the table being uploaded".to_owned(),
        });
    }
    let max_window = capacity.min(MAX_PROBE_LENGTH);
    if window == 0 || window > max_window {
        return Err(ExatokError::Artifact {
            artifact: TABLE_ARTIFACT.to_owned(),
            location: format!("lookup program probe window {window}"),
            detail: format!(
                "probe window must be between 1 and {max_window} for a {capacity} slot table"
            ),
            fix: "pass RankTable::window() of the table being uploaded".to_owned(),
        });
    }
    if lanes == 0 {
        return Err(ExatokError::Artifact {
            artifact: TABLE_ARTIFACT.to_owned(),
            location: "lookup program lane count 0".to_owned(),
            detail: "a zero-length dispatch declares zero-element buffers, which no backend can bind".to_owned(),
            fix: "skip the dispatch when there are no pairs to look up".to_owned(),
        });
    }
    let words = capacity
        .checked_mul(SLOT_WORDS)
        .ok_or_else(|| ExatokError::Artifact {
            artifact: TABLE_ARTIFACT.to_owned(),
            location: format!("lookup program capacity {capacity}"),
            detail: "capacity times SLOT_WORDS overflows a u32 buffer element count".to_owned(),
            fix: "shard the merge table across several uploads".to_owned(),
        })?;
    let out_words = lanes.checked_mul(2).ok_or_else(|| ExatokError::Artifact {
        artifact: TABLE_ARTIFACT.to_owned(),
        location: format!("lookup program lane count {lanes}"),
        detail: "two output words per lane overflows a u32 buffer element count".to_owned(),
        fix: "split the query batch across several dispatches".to_owned(),
    })?;

    let lane = Expr::var("lane");
    // The lane guard is a Node, not an Expr::and, on purpose: a data-flow guard
    // still evaluates the loads for lanes past `lanes`, which reads off the end
    // of the query buffers on a real GPU. Over-firing is normal, not exotic: the
    // dispatch is rounded up to a whole number of workgroups, so a lane count
    // that is not a multiple of LOOKUP_WORKGROUP always launches surplus lanes.
    let body = vec![
        Node::let_bind("lane", Expr::gid_x()),
        Node::if_then(
            Expr::lt(lane.clone(), Expr::u32(lanes)),
            vec![probe_child(
                LOOKUP_OP_ID,
                "probe",
                TABLE_SLOTS_BUFFER,
                capacity,
                window,
                Expr::load(PAIR_LO_BUFFER, lane.clone()),
                Expr::load(PAIR_HI_BUFFER, lane.clone()),
                vec![
                    Node::store(
                        OUT_BUFFER,
                        lane.clone(),
                        Expr::var(probe_rank_var("probe").as_str()),
                    ),
                    Node::store(
                        OUT_BUFFER,
                        Expr::add(lane, Expr::u32(lanes)),
                        Expr::var(probe_id_var("probe").as_str()),
                    ),
                ],
            )],
        ),
    ];

    Ok(Program::wrapped(
        vec![
            BufferDecl::read(PAIR_LO_BUFFER, 0, DataType::U32).with_count(lanes),
            BufferDecl::read(PAIR_HI_BUFFER, 1, DataType::U32).with_count(lanes),
            BufferDecl::read(TABLE_SLOTS_BUFFER, 2, DataType::U32).with_count(words),
            BufferDecl::output(OUT_BUFFER, 3, DataType::U32).with_count(out_words),
        ],
        [LOOKUP_WORKGROUP, 1, 1],
        vec![wrap_anonymous(LOOKUP_OP_ID, body)],
    )
    .with_entry_op_id(LOOKUP_OP_ID))
}

/// Dispatch policy for [`lookup_program`] at `lanes` query lanes.
///
/// States the element grid explicitly rather than leaving it to buffer-shape
/// inference. Inference happens to land on `lanes` here only because a guarded
/// store leaves the output the widest buffer at `2 * lanes`, and half of that is
/// the lane count: a coincidence of this program's shape, not a rule, and it
/// would silently over-fire or under-fire the moment the planes changed size.
#[must_use]
pub fn lookup_dispatch_config(lanes: u32) -> DispatchConfig {
    let mut config = DispatchConfig::default();
    config.dispatch_elements = Some(lanes);
    config
}

/// Human-readable pair, matching `reference`'s diagnostic wording.
fn pair_location(pair: PairKey) -> String {
    format!("pair ({}, {})", pair.left().0, pair.right().0)
}

/// Diagnostic for a row whose rank collides with the empty-slot marker.
fn absent_rank_error(artifact: &str, pair: PairKey) -> ExatokError {
    ExatokError::Artifact {
        artifact: artifact.to_owned(),
        location: pair_location(pair),
        detail: "merge rank equals the ABSENT sentinel u32::MAX, which marks an empty slot in the rank word".to_owned(),
        fix: "renumber merges so every real rank stays below u32::MAX, keeping the sentinel unused so a min reduction skips unmergeable pairs".to_owned(),
    }
}

/// Diagnostic for two rows keyed on the same pair.
fn duplicate_error(
    artifact: &str,
    pair: PairKey,
    existing: Rank,
    repeated: Rank,
) -> ExatokError {
    ExatokError::Artifact {
        artifact: artifact.to_owned(),
        location: pair_location(pair),
        detail: format!(
            "duplicate merge: rank {} already recorded, rank {} seen again",
            existing.0, repeated.0
        ),
        fix: "remove the repeated pair from the merge list so exactly one rank governs it"
            .to_owned(),
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
mod tests {
    use super::*;

    /// The device probe hash and [`PairKey::probe_hash`] must be one function.
    /// vyre's FNV-1a constants are the ones the emitted expression tree uses;
    /// if exatok's host copy drifted from them, every host-computed home slot
    /// would point at a different slot than the device probes and the table
    /// would miss on keys it actually contains.
    #[test]
    fn host_and_device_fnv1a_constants_are_the_same_values() {
        assert_eq!(crate::FNV1A32_OFFSET_BASIS, 0x811c_9dc5);
        assert_eq!(
            crate::FNV1A32_OFFSET_BASIS,
            vyre_primitives::hash::fnv1a::FNV1A32_OFFSET
        );
        assert_eq!(crate::FNV1A32_PRIME, 0x0100_0193);
        assert_eq!(
            crate::FNV1A32_PRIME,
            vyre_primitives::hash::fnv1a::FNV1A32_PRIME
        );
    }

    /// The empty-slot marker is the rank word's [`Rank::ABSENT`], which is also
    /// the value `vyre_primitives::hash::table` writes on a miss. Locks the two
    /// together: if the primitive's miss value changed, a lookup fragment
    /// composed from it would report a real rank of `MISS_VALUE` as a miss, or
    /// an empty slot as rank zero.
    #[test]
    fn empty_slot_marker_equals_the_primitive_miss_value() {
        assert_eq!(Rank::ABSENT.0, vyre_primitives::hash::table::MISS_VALUE);
    }

    /// `split_key` must put the right token in the low word and the left in the
    /// high word, matching the little-endian bytes `probe_hash` digests.
    /// Swapping them would make the device hash a different byte sequence than
    /// the host, so every lookup would probe the wrong home slot.
    #[test]
    fn split_key_puts_right_token_in_the_low_word() {
        let pair = PairKey::new(TokenId(0xAAAA_BBBB), TokenId(0x1111_2222));
        assert_eq!(split_key(pair), (0x1111_2222, 0xAAAA_BBBB));
        assert_eq!(
            pair.bits().to_le_bytes(),
            [0x22, 0x22, 0x11, 0x11, 0xBB, 0xBB, 0xAA, 0xAA]
        );
    }

    /// A fresh table must read as all-empty. The rank word carries occupancy,
    /// so a `vec![0; _]` that forgot to stamp `Rank::ABSENT` would make every
    /// slot look occupied by `(TokenId(0), TokenId(0))` with rank 0, and the
    /// first lookup of any pair would either return rank 0 or stall the probe
    /// walk on a wall of fake entries.
    #[test]
    fn a_fresh_table_stamps_absent_into_every_rank_word() {
        let table = RankTable::with_capacity(8).unwrap();
        assert_eq!(table.slot_words().len(), 8 * SLOT_WORDS as usize);
        for slot in 0..8_u32 {
            let base = RankTable::base(slot);
            assert_eq!(table.slot_words()[base + SLOT_KEY_LO as usize], 0);
            assert_eq!(table.slot_words()[base + SLOT_KEY_HI as usize], 0);
            assert_eq!(
                table.slot_words()[base + SLOT_RANK as usize],
                Rank::ABSENT.0,
                "slot {slot} rank word must start ABSENT"
            );
            assert_eq!(table.slot_words()[base + SLOT_ID as usize], 0);
        }
        assert_eq!(table.len(), 0);
        assert!(
            table.is_empty(),
            "is_empty() must agree with the exact len()==0 pinned above"
        );
    }

    /// One inserted row must occupy exactly its four words in exactly the
    /// documented order. The device reads these offsets as literals, so a
    /// transposition here (id where the rank belongs) would return a token id
    /// as a merge rank and reorder every merge.
    #[test]
    fn an_inserted_row_lands_in_the_documented_word_order() {
        let mut table = RankTable::with_capacity(16).unwrap();
        let pair = PairKey::new(TokenId(0x0001_0203), TokenId(0x0405_0607));
        table
            .insert("unit", pair, TokenId(9_999), Rank(1_234))
            .unwrap();
        let base = RankTable::base(table.home_slot(pair));
        assert_eq!(table.slot_words()[base + SLOT_KEY_LO as usize], 0x0405_0607);
        assert_eq!(table.slot_words()[base + SLOT_KEY_HI as usize], 0x0001_0203);
        assert_eq!(table.slot_words()[base + SLOT_RANK as usize], 1_234);
        assert_eq!(table.slot_words()[base + SLOT_ID as usize], 9_999);
        assert_eq!(table.len(), 1);
    }

    /// Capacity sizing must keep the build load factor at or below 1/4 and stay
    /// a power of two. At load 0.43 the measured longest probe over 446189 real
    /// shaped keys is 28 slots against a 32 cap, so a looser factor puts every
    /// larger vocabulary into rehash-or-fail territory.
    #[test]
    fn build_capacity_stays_a_power_of_two_at_or_below_quarter_load() {
        assert_eq!(RankTable::capacity_for(0).unwrap(), 1);
        assert_eq!(RankTable::capacity_for(1).unwrap(), 4);
        assert_eq!(RankTable::capacity_for(3).unwrap(), 16);
        assert_eq!(RankTable::capacity_for(50_000).unwrap(), 262_144);
        assert_eq!(RankTable::capacity_for(446_189).unwrap(), 2_097_152);
        for rows in [1_usize, 7, 100, 4_096, 50_000, 233_378, 446_189] {
            let capacity = RankTable::capacity_for(rows).unwrap();
            assert!(capacity.is_power_of_two(), "rows={rows} capacity={capacity}");
            assert!(
                u64::from(capacity) >= (rows as u64) * SLOTS_PER_ROW,
                "rows={rows} capacity={capacity} is above quarter load"
            );
        }
    }

    /// A capacity above the module ceiling must be refused at construction
    /// instead of attempting a multi-gigabyte allocation.
    #[test]
    fn capacity_above_the_ceiling_is_refused() {
        let err = RankTable::with_capacity(MAX_CAPACITY * 2).unwrap_err();
        assert!(
            err.to_string().contains("slot ceiling"),
            "wrong diagnostic: {err}"
        );
        let err = RankTable::capacity_for(1 << 30).unwrap_err();
        assert!(
            err.to_string().contains("slot ceiling"),
            "wrong diagnostic: {err}"
        );
    }

    /// A non-power-of-two capacity must be refused: the home slot is a bit
    /// mask, so capacity 100 would fold slots 100..127 onto 0..27 and lose
    /// every key placed there.
    #[test]
    fn non_power_of_two_capacity_is_refused() {
        for capacity in [0_u32, 3, 100, 1000] {
            let err = RankTable::with_capacity(capacity).unwrap_err();
            assert!(
                err.to_string().contains("power of two"),
                "capacity {capacity} gave the wrong diagnostic: {err}"
            );
        }
    }

    /// The probe bound is the table's measured longest probe, not the cap. An
    /// empty table reports 1 rather than 0 so the device loop still inspects the
    /// home slot, and the bound grows only as far as insertions force it.
    #[test]
    fn probe_bound_tracks_the_longest_probe_actually_needed() {
        let mut table = RankTable::with_capacity(1024).unwrap();
        assert_eq!(table.window(), 1);
        table
            .insert("unit", PairKey::new(TokenId(1), TokenId(2)), TokenId(3), Rank(0))
            .unwrap();
        assert_eq!(table.window(), 1, "one key sits in its own home slot");

        // Force a collision chain: fill the home slot of `victim`, then insert
        // `victim` itself, which must land one step later and widen the bound.
        let victim = PairKey::new(TokenId(700), TokenId(800));
        let home = table.home_slot(victim);
        let squatter = (0_u32..)
            .map(|n| PairKey::new(TokenId(900_000 + n), TokenId(7)))
            .find(|candidate| table.home_slot(*candidate) == home)
            .unwrap();
        table
            .insert("unit", squatter, TokenId(11), Rank(11))
            .unwrap();
        table.insert("unit", victim, TokenId(22), Rank(22)).unwrap();
        assert_eq!(table.window(), 2);
        assert_eq!(table.rank(victim), Rank(22));
        assert_eq!(table.rank(squatter), Rank(11));
    }

    /// A window outside the table's real bound must be refused when building
    /// the program. Passing the 32-slot cap for a table whose bound is 12 only
    /// wastes iterations, but passing a bound SHORTER than the table's turns
    /// present keys into misses, and that is a silent wrong-answer bug.
    #[test]
    fn lookup_program_refuses_a_window_outside_the_table_bound() {
        assert!(lookup_program(1024, 0, 8).is_err());
        assert!(lookup_program(1024, MAX_PROBE_LENGTH + 1, 8).is_err());
        assert!(lookup_program(4, 5, 8).is_err(), "window must clamp to capacity");
        assert!(lookup_program(1024, MAX_PROBE_LENGTH, 8).is_ok());
        assert!(lookup_program(4, 4, 8).is_ok());
    }

    /// The probe fragment must be emitted as a region that names its parent op,
    /// and the `then` body must land INSIDE that region.
    ///
    /// `print-composition` walks the parent chain; a `None` source region makes
    /// the probe look like an unattributed body and breaks the tier audit. The
    /// placement half matters just as much: a `then` body emitted as the region's
    /// sibling cannot see the probe's bindings, and the program fails IR
    /// validation with an undeclared `probe_rank` instead of running.
    #[test]
    fn probe_child_nests_its_consumer_inside_a_region_naming_its_parent() {
        let node = probe_child(
            LOOKUP_OP_ID,
            "probe",
            TABLE_SLOTS_BUFFER,
            1024,
            8,
            Expr::u32(1),
            Expr::u32(2),
            vec![Node::store(
                OUT_BUFFER,
                Expr::u32(0),
                Expr::var(probe_rank_var("probe").as_str()),
            )],
        );
        let bare = probe_nodes("probe", TABLE_SLOTS_BUFFER, 1024, 8, Expr::u32(1), Expr::u32(2));
        match node {
            Node::Region {
                generator,
                source_region,
                body,
                ..
            } => {
                assert_eq!(generator.as_str(), PROBE_OP_ID);
                assert_eq!(
                    source_region.map(|parent| parent.name),
                    Some(LOOKUP_OP_ID.to_owned())
                );
                assert_eq!(
                    body.len(),
                    bare.len() + 1,
                    "the region must hold the probe fragment plus the one consumer node"
                );
                assert!(
                    matches!(body.last(), Some(Node::Store { buffer, .. }) if buffer == OUT_BUFFER),
                    "the consumer must be the region's last node, not its sibling"
                );
            }
            other => panic!("probe_child must emit a Region, got {other:?}"),
        }
    }

    /// Op ids must carry the Tier 4 `exatok::` prefix. The tier audit is
    /// grep-based, so a `vyre-libs::` prefix here would file this crate's ops
    /// under Tier 3 and let them escape external-pack review.
    #[test]
    fn op_ids_use_the_tier_four_exatok_prefix() {
        for id in [LOOKUP_OP_ID, PROBE_OP_ID] {
            assert!(id.starts_with("exatok::gpu_rank_table::"), "bad op id: {id}");
            assert!(!id.contains("vyre-libs::"), "bad op id: {id}");
        }
    }
}