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
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
//! Merge selection and compaction programs. OWNER: GpuSelect.
//!
//! Composes `vyre_primitives::reduce` for the per-pass argmin over ranks and
//! for the stream compaction that removes merged elements.
//!
//! Acceptance: leftmost-minimum index is returned under ties, and compaction
//! preserves exact surviving order, both against a host oracle on random and
//! adversarial inputs.
//!
//! # The parallel dimension is across pretokens, not within one
//!
//! Measured pretoken sizes on real corpora with the real `cl100k` pattern:
//! mean 4.13 bytes on Rust source and 9.33 on prose, median 3, 99.08% at or
//! under 16 bytes, longest observed 506. Merging never crosses a pretoken
//! boundary. So a 1 GB input is a quarter of a billion INDEPENDENT tiny
//! sequences, and the merge loop's depth is bounded by the longest pretoken
//! rather than by the corpus.
//!
//! Every selection program here is therefore SEGMENTED: one workgroup per
//! pretoken, reducing over that pretoken's own rank window. A single global
//! minimum over the whole corpus would perform one merge per pass for the
//! entire input, which is the O(merges) barrier-pass shape that makes prior
//! GPU BPE work slow, and it comes from treating the corpus as one long array.
//!
//! # Array layout contract
//!
//! Rank, flag, and merged-id arrays are all length `n`, the token count. Slot
//! `i` describes the adjacent pair `(i, i + 1)`. The final slot of every
//! segment therefore names no pair and MUST carry [`Rank::ABSENT`], because
//! pair `(end - 1, end)` would straddle the boundary. Two properties follow
//! from that single invariant and are relied on throughout:
//!
//! * A selected index is never the last slot of its segment, so `index + 1` is
//!   always inside the same segment and a merge can never consume a token that
//!   belongs to the next pretoken.
//! * A run of equal-rank positions can never cross a segment boundary, so the
//!   multi-position selection below is segment-correct without knowing where
//!   the segments are.
//!
//! # Why two minima instead of one comparator
//!
//! A tree reduction carrying `(rank, index)` pairs needs a hand-written
//! comparator with a tie-break clause, and a wrong tie-break is invisible: it
//! yields a valid-looking but different tokenization.
//! [`segmented_argmin_leftmost`] instead runs two unsigned `min` reductions.
//! The first finds the minimum rank in the segment; the second finds the
//! minimum *index* among lanes holding that rank. Leftmost tie-breaking is
//! then a consequence of `min` over indices, so correctness rests only on
//! `min` being associative and commutative.
//!
//! # The sentinel collision
//!
//! [`Rank::ABSENT`] is `u32::MAX` and so is [`NO_MERGE_INDEX`]. On an
//! all-absent window the phase-one minimum is `u32::MAX`, at which point the
//! phase-two predicate `rank[i] == minimum` is true for *every* lane, the
//! index minimum is the window's first index, and the pass reports a merge
//! where none exists. Phase two is therefore skipped entirely when the
//! phase-one minimum is absent. This is the common case, not a corner case: at
//! a median pretoken length of 3, a fully converged or single-token segment is
//! entirely absent, and every segment ends absent by the layout contract.
//!
//! # No monotonicity assumption
//!
//! The minimum rank present in a sequence can DECREASE from one pass to the
//! next: in `cl100k_base`, `' '` + `'  '` yields `'   '` at rank 262, and then
//! `'   '` + `' '` yields `'    '` at rank 257. Nothing here sorts ranks,
//! caches a minimum across passes, or short-circuits on a rising rank; every
//! pass reads the rank array fresh.
//!
//! # Sequential is the default; multi-merge is not
//!
//! [`segmented_argmin_leftmost`] plus [`apply_argmin_merges`] is one merge per
//! pretoken per pass, which IS the reference algorithm, so its exactness needs
//! no reachability argument. `select_non_overlapping` and `apply_merges`
//! implement the multi-merge fast path and are deliberately NOT wired into
//! that default: single-rank left-biased multi-merge is exact on states
//! reachable from raw bytes but not on arbitrary states. That refutation, the
//! independent fatality of rank ties, and exactness over the reachable sweep
//! are measured in `tests/confluence_equivalence.rs`.
//!
//! This path is retained as the REFUTATION RECORD, not as a performance option.
//! That experiment needs a real multi-merge implementation to refute, and a
//! refutation of a strawman proves nothing, so the code earns its place for a
//! reason no throughput or depth measurement can strengthen or weaken.
//!
//! The pass-count figures are neither measured nor relevant. `21%` on the mean
//! and the `63 -> 17` worst-case depth are single-sourced from the wave brief
//! and asserted by no test here, so do not cite them as verified; read that as
//! "not worth verifying" rather than "should be verified", because no value of
//! either number changes any decision. `92.5%` of pretokens saving nothing is
//! Main's measurement, whose qualitative end (a left-recursive chain saves zero
//! passes) is locked by `pass_count_reduction_can_be_zero`.
//!
//! The feature stays OFF behind `#[cfg(feature = "multi-merge")]` on exactness
//! grounds that no benchmark can overturn. Byte-for-byte agreement with the
//! reference is the product contract, and multi-merge is refuted on arbitrary
//! states by a minimal four-token counterexample and is independently fatal on
//! rank ties. There is no speed at which an inexact tokenizer ships.

use std::sync::Arc;

use vyre::execution_plan::fusion::fuse_programs;
use vyre::ir::model::expr::{GeneratorRef, Ident};
use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
use vyre_libs::region::{tag_program, wrap_anonymous};
use vyre_primitives::reduce::multi_block_prefix_scan::multi_block_prefix_scan_sum_exclusive_u32;
use vyre_primitives::reduce::scatter::scatter;
use vyre_primitives::reduce::workgroup_tree::{min_u32_child, WorkgroupReductionScope};

use crate::{trap_program, Rank, TokenId};

/// Canonical op id for the per-segment leftmost-minimum rank selection.
pub const ARGMIN_OP_ID: &str = "exatok::gpu_select::segmented_argmin_leftmost";

/// Canonical op id for order-preserving removal compaction.
pub const COMPACT_OP_ID: &str = "exatok::gpu_select::compact_removed";

/// Canonical op id for rebasing a segment table after a compaction.
pub const REMAP_OP_ID: &str = "exatok::gpu_select::remap_segment_starts";

/// Canonical op id for applying one selected merge per segment.
pub const APPLY_ARGMIN_OP_ID: &str = "exatok::gpu_select::apply_argmin_merges";

/// Canonical op id for left-biased non-overlapping position selection.
#[cfg(feature = "multi-merge")]
pub const SELECT_OP_ID: &str = "exatok::gpu_select::select_non_overlapping";

/// Canonical op id for applying a batch of simultaneous merges.
#[cfg(feature = "multi-merge")]
pub const APPLY_MERGES_OP_ID: &str = "exatok::gpu_select::apply_merges";

/// Words each segment occupies in a [`segmented_argmin_leftmost`] output.
pub const ARGMIN_WORDS_PER_SEGMENT: u32 = 2;

/// Offset within a segment's argmin output words holding the selected index.
pub const ARGMIN_INDEX_SLOT: u32 = 0;

/// Offset within a segment's argmin output words holding the winning rank.
pub const ARGMIN_RANK_SLOT: u32 = 1;

/// Written to a segment's index slot when no pair in it is mergeable.
///
/// Distinct from index `0`, which is a real merge at the head of the array.
pub const NO_MERGE_INDEX: u32 = u32::MAX;

/// Lanes in the one workgroup that reduces one segment.
///
/// A 32-lane workgroup is exactly one subgroup on every GPU vyre targets, so
/// the reduction tree below is warp-synchronous and the 99%-case pretoken is
/// reduced without leaving the warp. Segments longer than 32 elements are
/// served by the same code path: each lane folds a strided slice first, with a
/// RUNTIME trip count taken from the segment table, so there is no length cap
/// and no separate tail path that only the rare long pretoken exercises.
pub const SEGMENT_LANES: u32 = 32;

/// Lane count for the flat element-per-lane passes.
///
/// Matches the geometry `vyre_primitives::reduce::scatter` declares, so fusing
/// against it does not widen a workgroup that reasons about its own width.
const FLAT_LANES: u32 = 256;

const RANK_SCRATCH: &str = "__exatok_argmin_rank_scratch";
const INDEX_SCRATCH: &str = "__exatok_argmin_index_scratch";

/// Largest array length these programs accept.
///
/// `n == u32::MAX` would make a real index collide with [`NO_MERGE_INDEX`] and
/// with the out-of-range slot that suppresses a dropped element's scatter, so
/// it is rejected rather than silently mis-reported.
pub const MAX_ELEMENTS: u32 = u32::MAX - 1;

// ---------------------------------------------------------------------------
// Segmented single-merge selection: leftmost minimum rank per segment.
// ---------------------------------------------------------------------------

/// Build a Program that writes, for every segment, the leftmost
/// minimum-rank pair index and that rank.
///
/// `ranks` holds one rank per token. `segment_starts` holds `num_segments + 1`
/// words: the first element index of each segment followed by a sentinel equal
/// to the total token count, which is exactly what
/// `pretokenize::segment_starts` emits. `out` holds
/// `num_segments * ARGMIN_WORDS_PER_SEGMENT` words: segment `s` writes its
/// index at `s * 2 + ARGMIN_INDEX_SLOT` (absolute, or [`NO_MERGE_INDEX`]) and
/// its rank at `s * 2 + ARGMIN_RANK_SLOT`.
///
/// Dispatch one workgroup per segment: `[num_segments, 1, 1]` workgroups of
/// [`SEGMENT_LANES`] lanes. On the reference interpreter that is
/// `DispatchConfig::dispatch_grid`; on CUDA it MUST be `grid_override` with
/// `workgroup_override` alongside, because the driver never reads
/// `dispatch_grid` and otherwise infers `ceil(ranks_len / SEGMENT_LANES)`
/// workgroups from the widest binding. That inference equals `num_segments`
/// only when the mean segment holds exactly [`SEGMENT_LANES`] tokens; real
/// pretokens hold a few, so an inferred grid is short by roughly
/// `SEGMENT_LANES / mean_segment_len` and the uncomputed segments read back
/// zero-filled, which decodes as a merge at index 0 at the best possible rank.
///
/// `num_segments == 0` is an empty input, not an error, and still answers the
/// question rather than leaving a zero-filled buffer that would read back as a
/// valid merge at index 0.
#[must_use]
pub fn segmented_argmin_leftmost(
    ranks: &str,
    segment_starts: &str,
    out: &str,
    num_segments: u32,
) -> Program {
    if num_segments > MAX_ELEMENTS / ARGMIN_WORDS_PER_SEGMENT {
        return trap_program(
            ARGMIN_OP_ID,
            out,
            DataType::U32,
            format!(
                "segmented_argmin_leftmost requires num_segments <= {}, got {num_segments}. \
                 Fix: shard the segment table; the output buffer is two words per segment.",
                MAX_ELEMENTS / ARGMIN_WORDS_PER_SEGMENT
            ),
        );
    }
    if num_segments == 0 {
        return no_merge_program(ARGMIN_OP_ID, out);
    }

    // `local` is not a free choice of name: `workgroup_tree::min_u32_child`
    // emits `Expr::var("local")` and requires the composing op to have bound it
    // to lane 0's `LocalId`, the same contract every vyre-primitives caller of
    // a child region follows.
    let lane = || Expr::var("local");
    let segment = || Expr::var("segment");
    let in_range = || Expr::lt(segment(), Expr::u32(num_segments));

    // Segment bounds and the runtime fold trip count. `rounds` is computed
    // from the table, not from a build-time maximum length, so a long pretoken
    // folds more elements per lane instead of being truncated.
    let bounds = || {
        vec![
            Node::let_bind("begin", Expr::load(segment_starts, segment())),
            Node::let_bind(
                "end",
                Expr::load(segment_starts, Expr::add(segment(), Expr::u32(1))),
            ),
            Node::let_bind(
                "rounds",
                Expr::div(
                    Expr::add(
                        Expr::sub(Expr::var("end"), Expr::var("begin")),
                        Expr::u32(SEGMENT_LANES - 1),
                    ),
                    Expr::u32(SEGMENT_LANES),
                ),
            ),
        ]
    };
    let strided_index = || {
        Node::let_bind(
            "element",
            Expr::add(
                Expr::var("begin"),
                Expr::add(
                    Expr::mul(Expr::var("round"), Expr::u32(SEGMENT_LANES)),
                    lane(),
                ),
            ),
        )
    };
    let element_in_segment = || Expr::lt(Expr::var("element"), Expr::var("end"));

    // Phase one: each lane folds its strided slice of the segment into a rank
    // minimum, then the warp tree folds the lanes. `Rank::ABSENT` is the
    // identity of an unsigned min, so absent pairs need no mask.
    let mut phase_one = bounds();
    phase_one.extend([
        Node::let_bind("rank_acc", Expr::u32(Rank::ABSENT.0)),
        Node::loop_for(
            "round",
            Expr::u32(0),
            Expr::var("rounds"),
            vec![
                strided_index(),
                Node::if_then(
                    element_in_segment(),
                    vec![Node::assign(
                        "rank_acc",
                        Expr::min(
                            Expr::var("rank_acc"),
                            Expr::load(ranks, Expr::var("element")),
                        ),
                    )],
                ),
            ],
        ),
        Node::store(RANK_SCRATCH, lane(), Expr::var("rank_acc")),
    ]);

    // Phase two: minimum INDEX among lanes whose rank equals the phase-one
    // minimum. Skipped when that minimum is absent, or the equality predicate
    // would match every lane of an all-absent window and report a merge.
    let mut phase_two = bounds();
    phase_two.extend([
        Node::let_bind("min_rank", Expr::load(RANK_SCRATCH, Expr::u32(0))),
        Node::let_bind("index_acc", Expr::u32(NO_MERGE_INDEX)),
        Node::if_then(
            Expr::ne(Expr::var("min_rank"), Expr::u32(Rank::ABSENT.0)),
            vec![Node::loop_for(
                "round",
                Expr::u32(0),
                Expr::var("rounds"),
                vec![
                    strided_index(),
                    Node::if_then(
                        element_in_segment(),
                        vec![Node::if_then(
                            Expr::eq(
                                Expr::load(ranks, Expr::var("element")),
                                Expr::var("min_rank"),
                            ),
                            vec![Node::assign(
                                "index_acc",
                                Expr::min(Expr::var("index_acc"), Expr::var("element")),
                            )],
                        )],
                    ),
                ],
            )],
        ),
        Node::store(INDEX_SCRATCH, lane(), Expr::var("index_acc")),
    ]);

    // Scratch is primed unconditionally, and the barriers sit OUTSIDE the
    // segment guard, so every lane of every dispatched workgroup reaches every
    // barrier and no tree ever folds an uninitialized slot. A barrier some
    // lanes skip is undefined, and an over-dispatched workgroup is normal:
    // `num_segments` rarely lands on a whole grid. Surplus workgroups are safe;
    // DEFICIENT dispatch is the unsafe direction and nothing here can detect
    // it, because a segment that never runs leaves its output words at zero,
    // which is a valid-looking merge. No reference-backend test can reach that
    // state either: `dispatch_grid` is honoured verbatim there, so under-
    // dispatch is unconstructible and only a CUDA caller can produce it.
    let out_base = || Expr::mul(segment(), Expr::u32(ARGMIN_WORDS_PER_SEGMENT));
    let body = vec![
        Node::let_bind("local", Expr::LocalId { axis: 0 }),
        Node::let_bind("segment", Expr::WorkgroupId { axis: 0 }),
        Node::store(RANK_SCRATCH, lane(), Expr::u32(Rank::ABSENT.0)),
        Node::store(INDEX_SCRATCH, lane(), Expr::u32(NO_MERGE_INDEX)),
        Node::if_then(in_range(), phase_one),
        Node::barrier(),
        min_u32_child(
            ARGMIN_OP_ID,
            SEGMENT_LANES,
            RANK_SCRATCH,
            WorkgroupReductionScope::EveryWorkgroup,
        ),
        Node::if_then(in_range(), phase_two),
        Node::barrier(),
        min_u32_child(
            ARGMIN_OP_ID,
            SEGMENT_LANES,
            INDEX_SCRATCH,
            WorkgroupReductionScope::EveryWorkgroup,
        ),
        Node::if_then(
            Expr::and(in_range(), Expr::eq(lane(), Expr::u32(0))),
            vec![
                Node::store(
                    out,
                    Expr::add(out_base(), Expr::u32(ARGMIN_INDEX_SLOT)),
                    Expr::load(INDEX_SCRATCH, Expr::u32(0)),
                ),
                Node::store(
                    out,
                    Expr::add(out_base(), Expr::u32(ARGMIN_RANK_SLOT)),
                    Expr::load(RANK_SCRATCH, Expr::u32(0)),
                ),
            ],
        ),
    ];

    Program::wrapped(
        vec![
            BufferDecl::storage(ranks, 0, BufferAccess::ReadOnly, DataType::U32),
            BufferDecl::storage(segment_starts, 1, BufferAccess::ReadOnly, DataType::U32)
                .with_count(num_segments + 1),
            BufferDecl::workgroup(RANK_SCRATCH, SEGMENT_LANES, DataType::U32),
            BufferDecl::workgroup(INDEX_SCRATCH, SEGMENT_LANES, DataType::U32),
            BufferDecl::output(out, 2, DataType::U32)
                .with_count(num_segments * ARGMIN_WORDS_PER_SEGMENT),
        ],
        [SEGMENT_LANES, 1, 1],
        vec![wrap_anonymous(ARGMIN_OP_ID, body)],
    )
}

/// One-lane program that reports "no mergeable pair" in the argmin ABI.
///
/// An empty input still has to answer the question, and answering it with a
/// zero-filled buffer would read back as a valid merge at index 0.
fn no_merge_program(op_id: &str, out: &str) -> Program {
    let body = vec![Node::if_then(
        Expr::eq(Expr::gid_x(), Expr::u32(0)),
        vec![
            Node::store(out, Expr::u32(ARGMIN_INDEX_SLOT), Expr::u32(NO_MERGE_INDEX)),
            Node::store(out, Expr::u32(ARGMIN_RANK_SLOT), Expr::u32(Rank::ABSENT.0)),
        ],
    )];
    Program::wrapped(
        vec![BufferDecl::output(out, 0, DataType::U32).with_count(ARGMIN_WORDS_PER_SEGMENT)],
        [1, 1, 1],
        vec![wrap_anonymous(op_id, body)],
    )
}

// ---------------------------------------------------------------------------
// Order-preserving compaction.
// ---------------------------------------------------------------------------

/// Buffer names a [`compact_removed`] program allocates for itself.
///
/// Exposed because a caller running the fused program has to bind them, and
/// because [`remap_segment_starts`] consumes [`Self::offsets`] to rebase the
/// segment table without recomputing the scan.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CompactScratch {
    /// Per-element survival flag, `1` to keep and `0` to drop.
    pub keep: String,
    /// Exclusive prefix sum of [`Self::keep`]: the destination slot, and also
    /// the count of survivors before each element.
    pub offsets: String,
    /// Scatter destination per element, out of range for a dropped element.
    pub slots: String,
}

impl CompactScratch {
    /// Derive scratch names from the compaction output name.
    ///
    /// Deriving rather than accepting them means two compactions writing
    /// different outputs can never alias each other's intermediates.
    #[must_use]
    pub fn for_output(compacted: &str) -> Self {
        Self {
            keep: format!("__{compacted}_wt_keep"),
            offsets: format!("__{compacted}_wt_offsets"),
            slots: format!("__{compacted}_wt_slots"),
        }
    }
}

/// Build a Program that copies every element with a zero removal flag into
/// `compacted`, preserving exact original order, and writes the survivor count
/// to `live_count[0]`.
///
/// `values` and `removed` are `n` words; a nonzero `removed[i]` drops element
/// `i`. `compacted` is `n` words, of which only `[0, live_count)` is defined:
/// the trailing slots keep whatever the caller left there, because zeroing
/// them would cost a full pass to no purpose.
///
/// # Composition
///
/// Flags pass, then `multi_block_prefix_scan_sum_exclusive_u32`, then a slot
/// pass, then `reduce::scatter`. The scan is the uncapped three-pass Blelloch
/// chain, so there is no element-count ceiling and no sequential fallback: for
/// `n` above one block the fused program carries GridSync barriers and the
/// driver splits it into ordered dispatch segments.
///
/// The fused entry is deliberately NOT re-wrapped in an outer Region. Each arm
/// already carries its own generator, and burying the chain's GridSync
/// barriers a further scope deep is a needless risk to the split pass.
#[must_use]
pub fn compact_removed(
    values: &str,
    removed: &str,
    compacted: &str,
    live_count: &str,
    n: u32,
) -> Program {
    let scratch = CompactScratch::for_output(compacted);
    compact_removed_with_scratch(values, removed, compacted, live_count, &scratch, n)
}

/// [`compact_removed`] against caller-owned scratch buffers.
#[must_use]
pub fn compact_removed_with_scratch(
    values: &str,
    removed: &str,
    compacted: &str,
    live_count: &str,
    scratch: &CompactScratch,
    n: u32,
) -> Program {
    if n > MAX_ELEMENTS {
        return trap_program(
            COMPACT_OP_ID,
            compacted,
            DataType::U32,
            format!(
                "compact_removed requires n <= {MAX_ELEMENTS}, got {n}. Fix: split the array; \
                 n == u32::MAX leaves no out-of-range slot to suppress a dropped element's scatter."
            ),
        );
    }
    if n == 0 {
        return empty_count_program(COMPACT_OP_ID, live_count);
    }

    let flags = flat_program(
        COMPACT_OP_ID,
        vec![
            BufferDecl::storage(removed, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
            BufferDecl::storage(&scratch.keep, 1, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
        ],
        n,
        vec![Node::if_then_else(
            Expr::eq(Expr::load(removed, Expr::gid_x()), Expr::u32(0)),
            vec![Node::store(&scratch.keep, Expr::gid_x(), Expr::u32(1))],
            vec![Node::store(&scratch.keep, Expr::gid_x(), Expr::u32(0))],
        )],
    );

    let offsets_scan = composed(
        COMPACT_OP_ID,
        multi_block_prefix_scan_sum_exclusive_u32(&scratch.keep, &scratch.offsets, n),
    );

    // A kept element scatters to its exclusive-scan offset. A dropped element
    // is aimed at slot `n`, which `reduce::scatter` guards away, so no dead
    // lane can land on a survivor's slot.
    let slots = flat_program(
        COMPACT_OP_ID,
        vec![
            BufferDecl::storage(&scratch.keep, 0, BufferAccess::ReadOnly, DataType::U32)
                .with_count(n),
            BufferDecl::storage(&scratch.offsets, 1, BufferAccess::ReadOnly, DataType::U32)
                .with_count(n),
            BufferDecl::storage(&scratch.slots, 2, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
            BufferDecl::storage(live_count, 3, BufferAccess::ReadWrite, DataType::U32)
                .with_count(1),
        ],
        n,
        vec![
            Node::let_bind("keep_flag", Expr::load(&scratch.keep, Expr::gid_x())),
            Node::let_bind("offset", Expr::load(&scratch.offsets, Expr::gid_x())),
            Node::if_then_else(
                Expr::ne(Expr::var("keep_flag"), Expr::u32(0)),
                vec![Node::store(
                    &scratch.slots,
                    Expr::gid_x(),
                    Expr::var("offset"),
                )],
                vec![Node::store(&scratch.slots, Expr::gid_x(), Expr::u32(n))],
            ),
            // The exclusive scan excludes the final element, so the survivor
            // count is the last offset plus the last flag.
            Node::if_then(
                Expr::eq(Expr::gid_x(), Expr::u32(n - 1)),
                vec![Node::store(
                    live_count,
                    Expr::u32(0),
                    Expr::add(Expr::var("offset"), Expr::var("keep_flag")),
                )],
            ),
        ],
    );

    let move_survivors = composed(COMPACT_OP_ID, scatter(values, &scratch.slots, compacted, n));

    fuse_or_trap(
        COMPACT_OP_ID,
        compacted,
        &[flags, offsets_scan, slots, move_survivors],
    )
}

/// Build a Program that rebases a segment table onto a compacted array.
///
/// A compaction shortens the token array, so the segment table that indexed
/// the old array is stale and the merge loop cannot take another pass without
/// this. The new start of segment `s` is the number of survivors before its
/// old start, which the compaction already computed: it is exactly
/// `offsets[old_start]`, the exclusive scan value there. `new_starts` receives
/// `num_segments + 1` words, with the trailing sentinel taken from
/// `live_count[0]`.
///
/// Pass [`CompactScratch::offsets`] and the `live_count` from the compaction
/// that produced the array; recomputing the scan here would be a second
/// implementation of the same quantity.
#[must_use]
pub fn remap_segment_starts(
    segment_starts: &str,
    offsets: &str,
    live_count: &str,
    new_starts: &str,
    num_segments: u32,
    n: u32,
) -> Program {
    if n > MAX_ELEMENTS {
        return trap_program(
            REMAP_OP_ID,
            new_starts,
            DataType::U32,
            format!(
                "remap_segment_starts requires n <= {MAX_ELEMENTS}, got {n}. \
                 Fix: shard the token array before compacting."
            ),
        );
    }
    let table_words = num_segments.saturating_add(1);
    let body = vec![
        Node::if_then(
            Expr::lt(Expr::gid_x(), Expr::u32(num_segments)),
            vec![Node::store(
                new_starts,
                Expr::gid_x(),
                Expr::load(offsets, Expr::load(segment_starts, Expr::gid_x())),
            )],
        ),
        // The sentinel is the new total, which is the survivor count. It is
        // NOT `offsets[n]`: the exclusive scan has no slot `n`.
        Node::if_then(
            Expr::eq(Expr::gid_x(), Expr::u32(num_segments)),
            vec![Node::store(
                new_starts,
                Expr::gid_x(),
                Expr::load(live_count, Expr::u32(0)),
            )],
        ),
    ];
    Program::wrapped(
        vec![
            BufferDecl::storage(segment_starts, 0, BufferAccess::ReadOnly, DataType::U32)
                .with_count(table_words),
            BufferDecl::storage(offsets, 1, BufferAccess::ReadOnly, DataType::U32).with_count(n),
            BufferDecl::storage(live_count, 2, BufferAccess::ReadOnly, DataType::U32).with_count(1),
            BufferDecl::storage(new_starts, 3, BufferAccess::ReadWrite, DataType::U32)
                .with_count(table_words),
        ],
        [FLAT_LANES, 1, 1],
        vec![wrap_anonymous(
            REMAP_OP_ID,
            vec![Node::if_then(
                Expr::lt(Expr::gid_x(), Expr::u32(table_words)),
                body,
            )],
        )],
    )
}

// ---------------------------------------------------------------------------
// The default merge pass: one merge per segment, applied through compaction.
// ---------------------------------------------------------------------------

/// Buffer names an [`apply_argmin_merges`] program allocates for itself.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ApplyArgminScratch {
    /// Token array with each selected pair's left member replaced by the
    /// merged id.
    pub staged: String,
    /// `1` where a token is the right member of a selected pair.
    pub removed: String,
    /// Scratch for the compaction that follows.
    pub compact: CompactScratch,
}

impl ApplyArgminScratch {
    /// Derive scratch names from the new-token-array name.
    #[must_use]
    pub fn for_output(out_tokens: &str) -> Self {
        Self {
            staged: format!("__{out_tokens}_wt_staged"),
            removed: format!("__{out_tokens}_wt_removed"),
            compact: CompactScratch::for_output(out_tokens),
        }
    }
}

/// Build a Program applying one merge per segment, as chosen by
/// [`segmented_argmin_leftmost`], and writing the resulting token array.
///
/// This is the DEFAULT and shipping merge pass. It performs exactly the
/// reference algorithm's next step in every segment at once, so its exactness
/// follows from the reference algorithm rather than from any property of the
/// state being merged.
///
/// `tokens` and `merged_ids` are `n` words; `merged_ids[p]` is the id the merge
/// table returns for pair `p`. `argmin_out` is the
/// [`segmented_argmin_leftmost`] output. `out_len[0]` receives the new token
/// count.
///
/// A segment reporting [`NO_MERGE_INDEX`] contributes nothing, which is how a
/// converged pretoken sits out the remaining passes while its neighbours keep
/// merging.
#[must_use]
pub fn apply_argmin_merges(
    tokens: &str,
    merged_ids: &str,
    argmin_out: &str,
    out_tokens: &str,
    out_len: &str,
    num_segments: u32,
    n: u32,
) -> Program {
    let scratch = ApplyArgminScratch::for_output(out_tokens);
    apply_argmin_merges_with_scratch(
        tokens,
        merged_ids,
        argmin_out,
        out_tokens,
        out_len,
        &scratch,
        num_segments,
        n,
    )
}

/// [`apply_argmin_merges`] against caller-owned scratch buffers.
#[must_use]
#[allow(clippy::too_many_arguments)]
pub fn apply_argmin_merges_with_scratch(
    tokens: &str,
    merged_ids: &str,
    argmin_out: &str,
    out_tokens: &str,
    out_len: &str,
    scratch: &ApplyArgminScratch,
    num_segments: u32,
    n: u32,
) -> Program {
    if n > MAX_ELEMENTS {
        return trap_program(
            APPLY_ARGMIN_OP_ID,
            out_tokens,
            DataType::U32,
            format!(
                "apply_argmin_merges requires n <= {MAX_ELEMENTS}, got {n}. \
                 Fix: shard the token array; the compaction it composes cannot address u32::MAX."
            ),
        );
    }
    if n == 0 || num_segments == 0 {
        return empty_count_program(APPLY_ARGMIN_OP_ID, out_len);
    }

    // Every token starts out surviving unchanged. Doing this as its own arm,
    // rather than as an else-branch of the per-segment arm, is what lets the
    // per-segment arm be one lane per SEGMENT instead of one lane per token
    // searching for its segment.
    let reset = flat_program(
        APPLY_ARGMIN_OP_ID,
        vec![
            BufferDecl::storage(tokens, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
            BufferDecl::storage(&scratch.staged, 1, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
            BufferDecl::storage(&scratch.removed, 2, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
        ],
        n,
        vec![
            Node::store(
                &scratch.staged,
                Expr::gid_x(),
                Expr::load(tokens, Expr::gid_x()),
            ),
            Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(0)),
        ],
    );

    // One lane per segment applies that segment's merge. `index + 1` is inside
    // the same segment because the segment's last slot is `Rank::ABSENT` by the
    // layout contract, so it can never be selected.
    let apply = flat_program(
        APPLY_ARGMIN_OP_ID,
        vec![
            BufferDecl::storage(merged_ids, 0, BufferAccess::ReadOnly, DataType::U32)
                .with_count(n),
            BufferDecl::storage(argmin_out, 1, BufferAccess::ReadOnly, DataType::U32)
                .with_count(num_segments * ARGMIN_WORDS_PER_SEGMENT),
            BufferDecl::storage(&scratch.staged, 2, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
            BufferDecl::storage(&scratch.removed, 3, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
        ],
        num_segments,
        vec![
            Node::let_bind(
                "merge_at",
                Expr::load(
                    argmin_out,
                    Expr::add(
                        Expr::mul(Expr::gid_x(), Expr::u32(ARGMIN_WORDS_PER_SEGMENT)),
                        Expr::u32(ARGMIN_INDEX_SLOT),
                    ),
                ),
            ),
            Node::if_then(
                Expr::ne(Expr::var("merge_at"), Expr::u32(NO_MERGE_INDEX)),
                vec![
                    Node::store(
                        &scratch.staged,
                        Expr::var("merge_at"),
                        Expr::load(merged_ids, Expr::var("merge_at")),
                    ),
                    Node::store(
                        &scratch.removed,
                        Expr::add(Expr::var("merge_at"), Expr::u32(1)),
                        Expr::u32(1),
                    ),
                ],
            ),
        ],
    );

    let compact = compact_removed_with_scratch(
        &scratch.staged,
        &scratch.removed,
        out_tokens,
        out_len,
        &scratch.compact,
        n,
    );

    fuse_or_trap(APPLY_ARGMIN_OP_ID, out_tokens, &[reset, apply, compact])
}

// ---------------------------------------------------------------------------
// Multi-merge fast path. Retained, default-off, not wired into the pass above.
// ---------------------------------------------------------------------------

/// Buffer names a [`select_non_overlapping`] program allocates for itself.
#[cfg(feature = "multi-merge")]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SelectScratch {
    /// `1` where the rank equals the target, else `0`.
    pub matches: String,
    /// `1` where a maximal run of matching positions begins, else `0`.
    pub run_starts: String,
    /// Exclusive prefix sum of [`Self::run_starts`].
    pub run_offsets: String,
    /// Run index to the position where that run begins.
    pub run_start_index: String,
}

#[cfg(feature = "multi-merge")]
impl SelectScratch {
    /// Derive scratch names from the selection output name.
    #[must_use]
    pub fn for_output(selected: &str) -> Self {
        Self {
            matches: format!("__{selected}_wt_matches"),
            run_starts: format!("__{selected}_wt_run_starts"),
            run_offsets: format!("__{selected}_wt_run_offsets"),
            run_start_index: format!("__{selected}_wt_run_start_index"),
        }
    }
}

/// Build a Program selecting the maximal left-biased set of non-overlapping
/// pair positions whose rank equals `target[target_slot]`.
///
/// NOT the default merge pass. See the module header: single-rank left-biased
/// multi-merge is exact on states reachable from raw bytes but not on
/// arbitrary states, so [`apply_argmin_merges`] ships instead. This is
/// retained for its worst-case pass-depth reduction and is enabled only behind
/// an exhaustive sweep plus a permanent differential.
///
/// Position `i` merges tokens `i` and `i + 1`, so positions `i` and `i + 1`
/// overlap and cannot both be selected. The rule is: walk left to right and
/// take a matching position unless its left neighbour was taken. `selected` is
/// `n` words of `0` or `1`.
///
/// Segment-correct without a segment table: a run of equal-rank positions
/// cannot cross a pretoken boundary, because the last slot of every segment is
/// `Rank::ABSENT` by the layout contract and an absent target selects nothing.
///
/// `target` is read from a buffer rather than baked in as a literal so a
/// device-resident loop can chain this off the [`ARGMIN_RANK_SLOT`] word of a
/// [`segmented_argmin_leftmost`] output with no host round trip. A target of
/// `Rank::ABSENT` selects nothing: without that guard an all-absent rank array
/// would match at every position and merge garbage, the same sentinel
/// collision the argmin guards in phase two.
///
/// # How the sequential rule becomes parallel
///
/// Inside a maximal run of matching positions starting at `s`, the rule takes
/// `s`, `s + 2`, `s + 4`, so position `i` is taken exactly when `i - s` is
/// even. `s` is recovered without a segmented scan: an exclusive prefix sum of
/// the run-start flags gives each run a dense index, a scatter writes each
/// run's starting position at that index, and every position in the run then
/// reads its own `s` back. That is one uncapped scan plus two flat passes, and
/// it reuses the same scan chain the compaction uses.
#[cfg(feature = "multi-merge")]
#[must_use]
pub fn select_non_overlapping(
    ranks: &str,
    target: &str,
    target_slot: u32,
    selected: &str,
    n: u32,
) -> Program {
    let scratch = SelectScratch::for_output(selected);
    select_non_overlapping_with_scratch(ranks, target, target_slot, selected, &scratch, n)
}

/// [`select_non_overlapping`] against caller-owned scratch buffers.
#[cfg(feature = "multi-merge")]
#[must_use]
pub fn select_non_overlapping_with_scratch(
    ranks: &str,
    target: &str,
    target_slot: u32,
    selected: &str,
    scratch: &SelectScratch,
    n: u32,
) -> Program {
    if n > MAX_ELEMENTS {
        return trap_program(
            SELECT_OP_ID,
            selected,
            DataType::U32,
            format!(
                "select_non_overlapping requires n <= {MAX_ELEMENTS}, got {n}. Fix: split the rank \
                 array; n == u32::MAX leaves no out-of-range slot to suppress a non-start lane's \
                 scatter."
            ),
        );
    }
    if n == 0 {
        return empty_flag_program(SELECT_OP_ID, selected);
    }

    let target_word = || Expr::load(target, Expr::u32(target_slot));
    let is_match = || {
        Expr::and(
            Expr::ne(target_word(), Expr::u32(Rank::ABSENT.0)),
            Expr::eq(Expr::load(ranks, Expr::gid_x()), target_word()),
        )
    };
    let previous_matches = || {
        Expr::eq(
            Expr::load(ranks, Expr::sub(Expr::gid_x(), Expr::u32(1))),
            target_word(),
        )
    };

    // Match and run-start flags in one pass. The `i == 0` case is an
    // `if_then_else` and not a `select` so the `ranks[i - 1]` load is never
    // evaluated at position 0, where the index would wrap to `0xFFFFFFFF`.
    let flags = flat_program(
        SELECT_OP_ID,
        vec![
            BufferDecl::storage(ranks, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
            BufferDecl::storage(target, 1, BufferAccess::ReadOnly, DataType::U32)
                .with_count(target_slot + 1),
            BufferDecl::storage(&scratch.matches, 2, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
            BufferDecl::storage(
                &scratch.run_starts,
                3,
                BufferAccess::ReadWrite,
                DataType::U32,
            )
            .with_count(n),
        ],
        n,
        vec![Node::if_then_else(
            is_match(),
            vec![
                Node::store(&scratch.matches, Expr::gid_x(), Expr::u32(1)),
                Node::if_then_else(
                    Expr::eq(Expr::gid_x(), Expr::u32(0)),
                    vec![Node::store(
                        &scratch.run_starts,
                        Expr::gid_x(),
                        Expr::u32(1),
                    )],
                    vec![Node::if_then_else(
                        previous_matches(),
                        vec![Node::store(
                            &scratch.run_starts,
                            Expr::gid_x(),
                            Expr::u32(0),
                        )],
                        vec![Node::store(
                            &scratch.run_starts,
                            Expr::gid_x(),
                            Expr::u32(1),
                        )],
                    )],
                ),
            ],
            vec![
                Node::store(&scratch.matches, Expr::gid_x(), Expr::u32(0)),
                Node::store(&scratch.run_starts, Expr::gid_x(), Expr::u32(0)),
            ],
        )],
    );

    let run_scan = composed(
        SELECT_OP_ID,
        multi_block_prefix_scan_sum_exclusive_u32(&scratch.run_starts, &scratch.run_offsets, n),
    );

    // Dense run index to the position where that run begins.
    let run_table = flat_program(
        SELECT_OP_ID,
        vec![
            BufferDecl::storage(
                &scratch.run_starts,
                0,
                BufferAccess::ReadOnly,
                DataType::U32,
            )
            .with_count(n),
            BufferDecl::storage(
                &scratch.run_offsets,
                1,
                BufferAccess::ReadOnly,
                DataType::U32,
            )
            .with_count(n),
            BufferDecl::storage(
                &scratch.run_start_index,
                2,
                BufferAccess::ReadWrite,
                DataType::U32,
            )
            .with_count(n),
        ],
        n,
        vec![Node::if_then(
            Expr::ne(Expr::load(&scratch.run_starts, Expr::gid_x()), Expr::u32(0)),
            vec![Node::store(
                &scratch.run_start_index,
                Expr::load(&scratch.run_offsets, Expr::gid_x()),
                Expr::gid_x(),
            )],
        )],
    );

    // A matching position's run index is the exclusive count of run starts
    // before it plus its own start flag, minus one. It is never negative,
    // because the run containing a matching position starts at or before it.
    let parity = flat_program(
        SELECT_OP_ID,
        vec![
            BufferDecl::storage(&scratch.matches, 0, BufferAccess::ReadOnly, DataType::U32)
                .with_count(n),
            BufferDecl::storage(
                &scratch.run_starts,
                1,
                BufferAccess::ReadOnly,
                DataType::U32,
            )
            .with_count(n),
            BufferDecl::storage(
                &scratch.run_offsets,
                2,
                BufferAccess::ReadOnly,
                DataType::U32,
            )
            .with_count(n),
            BufferDecl::storage(
                &scratch.run_start_index,
                3,
                BufferAccess::ReadOnly,
                DataType::U32,
            )
            .with_count(n),
            BufferDecl::storage(selected, 4, BufferAccess::ReadWrite, DataType::U32).with_count(n),
        ],
        n,
        vec![Node::if_then_else(
            Expr::ne(Expr::load(&scratch.matches, Expr::gid_x()), Expr::u32(0)),
            vec![
                Node::let_bind(
                    "run",
                    Expr::sub(
                        Expr::add(
                            Expr::load(&scratch.run_offsets, Expr::gid_x()),
                            Expr::load(&scratch.run_starts, Expr::gid_x()),
                        ),
                        Expr::u32(1),
                    ),
                ),
                Node::let_bind(
                    "run_start",
                    Expr::load(&scratch.run_start_index, Expr::var("run")),
                ),
                Node::if_then_else(
                    Expr::eq(
                        Expr::bitand(
                            Expr::sub(Expr::gid_x(), Expr::var("run_start")),
                            Expr::u32(1),
                        ),
                        Expr::u32(0),
                    ),
                    vec![Node::store(selected, Expr::gid_x(), Expr::u32(1))],
                    vec![Node::store(selected, Expr::gid_x(), Expr::u32(0))],
                ),
            ],
            vec![Node::store(selected, Expr::gid_x(), Expr::u32(0))],
        )],
    );

    fuse_or_trap(SELECT_OP_ID, selected, &[flags, run_scan, run_table, parity])
}

/// Buffer names an [`apply_merges`] program allocates for itself.
#[cfg(feature = "multi-merge")]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ApplyMergesScratch {
    /// Token array with every selected pair's left member overwritten by the
    /// merged id.
    pub staged: String,
    /// `1` where a token is the right member of a selected pair.
    pub removed: String,
    /// Scratch for the compaction that follows.
    pub compact: CompactScratch,
}

#[cfg(feature = "multi-merge")]
impl ApplyMergesScratch {
    /// Derive scratch names from the new-token-array name.
    #[must_use]
    pub fn for_output(out_tokens: &str) -> Self {
        Self {
            staged: format!("__{out_tokens}_wt_multi_staged"),
            removed: format!("__{out_tokens}_wt_multi_removed"),
            compact: CompactScratch::for_output(out_tokens),
        }
    }
}

/// Build a Program that applies every selected merge at once and writes the
/// resulting token array.
///
/// The multi-merge counterpart of [`apply_argmin_merges`], and like
/// [`select_non_overlapping`] it is retained rather than shipped.
///
/// `tokens`, `selected`, and `merged_ids` are `n` words indexed as the module
/// header describes, and the final slot of every segment MUST be unselected.
/// For a selected position `p`, `tokens[p]` becomes `merged_ids[p]` and
/// `tokens[p + 1]` is dropped. `out_len[0]` receives the new token count.
///
/// Correctness depends on `selected` being non-overlapping, which is exactly
/// what [`select_non_overlapping`] guarantees: if `p` and `p + 1` were both
/// selected then `tokens[p + 1]` would have to be both a dropped right member
/// and a surviving merged left member.
#[cfg(feature = "multi-merge")]
#[must_use]
pub fn apply_merges(
    tokens: &str,
    selected: &str,
    merged_ids: &str,
    out_tokens: &str,
    out_len: &str,
    n: u32,
) -> Program {
    let scratch = ApplyMergesScratch::for_output(out_tokens);
    apply_merges_with_scratch(
        tokens,
        selected,
        merged_ids,
        out_tokens,
        out_len,
        &scratch,
        n,
    )
}

/// [`apply_merges`] against caller-owned scratch buffers.
#[cfg(feature = "multi-merge")]
#[must_use]
#[allow(clippy::too_many_arguments)]
pub fn apply_merges_with_scratch(
    tokens: &str,
    selected: &str,
    merged_ids: &str,
    out_tokens: &str,
    out_len: &str,
    scratch: &ApplyMergesScratch,
    n: u32,
) -> Program {
    if n > MAX_ELEMENTS {
        return trap_program(
            APPLY_MERGES_OP_ID,
            out_tokens,
            DataType::U32,
            format!(
                "apply_merges requires n <= {MAX_ELEMENTS}, got {n}. Fix: split the token array; \
                 the compaction it composes cannot address n == u32::MAX."
            ),
        );
    }
    if n == 0 {
        return empty_count_program(APPLY_MERGES_OP_ID, out_len);
    }

    let stage = flat_program(
        APPLY_MERGES_OP_ID,
        vec![
            BufferDecl::storage(tokens, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
            BufferDecl::storage(selected, 1, BufferAccess::ReadOnly, DataType::U32).with_count(n),
            BufferDecl::storage(merged_ids, 2, BufferAccess::ReadOnly, DataType::U32)
                .with_count(n),
            BufferDecl::storage(&scratch.staged, 3, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
            BufferDecl::storage(&scratch.removed, 4, BufferAccess::ReadWrite, DataType::U32)
                .with_count(n),
        ],
        n,
        vec![
            Node::if_then_else(
                Expr::ne(Expr::load(selected, Expr::gid_x()), Expr::u32(0)),
                vec![Node::store(
                    &scratch.staged,
                    Expr::gid_x(),
                    Expr::load(merged_ids, Expr::gid_x()),
                )],
                vec![Node::store(
                    &scratch.staged,
                    Expr::gid_x(),
                    Expr::load(tokens, Expr::gid_x()),
                )],
            ),
            // `selected[i - 1]` sits under an `if_then_else`, not a `select`,
            // so position 0 never evaluates the wrapping load.
            Node::if_then_else(
                Expr::eq(Expr::gid_x(), Expr::u32(0)),
                vec![Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(0))],
                vec![Node::if_then_else(
                    Expr::ne(
                        Expr::load(selected, Expr::sub(Expr::gid_x(), Expr::u32(1))),
                        Expr::u32(0),
                    ),
                    vec![Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(1))],
                    vec![Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(0))],
                )],
            ),
        ],
    );

    let compact = compact_removed_with_scratch(
        &scratch.staged,
        &scratch.removed,
        out_tokens,
        out_len,
        &scratch.compact,
        n,
    );

    fuse_or_trap(APPLY_MERGES_OP_ID, out_tokens, &[stage, compact])
}

// ---------------------------------------------------------------------------
// Shared program construction.
// ---------------------------------------------------------------------------

/// One lane per element, guarded against the logical count.
fn flat_program(op_id: &str, buffers: Vec<BufferDecl>, count: u32, body: Vec<Node>) -> Program {
    Program::wrapped(
        buffers,
        [FLAT_LANES, 1, 1],
        vec![wrap_anonymous(
            op_id,
            vec![Node::if_then(
                Expr::lt(Expr::gid_x(), Expr::u32(count)),
                body,
            )],
        )],
    )
}

/// Re-root a `vyre_primitives` arm's Regions under `parent_op_id`.
///
/// The composition audit (`cargo xtask print-composition`) walks Region
/// `source_region` links, and a primitive builder's Regions point at nothing
/// because the builder does not know who called it. Without this the trail stops
/// at the arm and a composed chain reads as hand-written IR. Arms built here
/// pass `wrap_anonymous`, which is the correct root for a body this module
/// authors itself.
///
/// This attributes the WHOLE arm, not just its top level. `reparent_program_children`
/// rewrites only entry-level nodes, which is not enough for two independent
/// reasons found by `every_emitted_region_names_an_op`: a primitive that is
/// itself a fusion carries `vyre.program.root` BELOW its entry, and
/// `multi_block_prefix_scan` nests a real named Region
/// (`...::guarded_single_block`) inside an `If`, where no entry-level pass
/// reaches it. Both leave `source_region` None, and one unattributed Region
/// severs the walk for everything beneath it.
///
/// Reparenting nests the scan chain's GridSync barriers one Region deeper. That
/// is safe by construction: the driver's barrier hoist recurses through Region
/// and Block bodies and lifts an enclosed GridSync back to dispatch level, and
/// the reference interpreter flattens Region scopes around a GridSync at any
/// depth. `compact_removed` is exercised above one block precisely to hold that
/// claim to a result rather than to a reading of the pass. Note the two scan
/// paths are reached by DIFFERENT fixtures and neither subsumes the other: the
/// GridSync chain needs n > BLOCK_LANES (1024), while `guarded_single_block`
/// above is emitted only for n <= BLOCK_LANES, so the small n = 8 case is what
/// covers it.
fn composed(parent_op_id: &str, program: Program) -> Program {
    attribute_regions(program, parent_op_id)
}

/// Point every unattributed Region in `program` at `op_id`.
///
/// Two cases. An anonymous `vyre.program.root` marker names no op at all, so it
/// is renamed as well as reparented. A Region that already names a primitive
/// keeps its name, since the audit wants the primitive's identity, and only
/// gains the missing parent link. An existing parent is never overwritten:
/// `min_u32_child` already points its children at the composing op, and
/// clobbering that would relocate a correct edge.
///
/// The rewrite is structurally inert. It changes a generator name and a parent
/// link and never the node tree, so barrier placement, the driver's entry peel
/// (which matches on Region without reading its name) and `entry_needs_root_region`
/// are unaffected.
fn attribute_regions(program: Program, op_id: &str) -> Program {
    let parent = GeneratorRef {
        name: op_id.to_owned(),
    };
    program.map_entry(|entry| attribute_nodes(entry, &parent))
}

fn attribute_nodes(nodes: Vec<Node>, parent: &GeneratorRef) -> Vec<Node> {
    nodes
        .into_iter()
        .map(|node| match node {
            Node::Region {
                generator,
                source_region,
                body,
            } => {
                let anonymous = generator.as_ref() == Program::ROOT_REGION_GENERATOR;
                let own = generator.as_ref().starts_with("exatok::");
                Node::Region {
                    generator: if anonymous {
                        Ident::from(format!("inline::{}", parent.name))
                    } else {
                        generator
                    },
                    source_region: match source_region {
                        Some(existing) => Some(existing),
                        None if own => None,
                        None => Some(parent.clone()),
                    },
                    body: Arc::new(attribute_nodes(body.as_ref().clone(), parent)),
                }
            }
            Node::Block(body) => Node::Block(attribute_nodes(body, parent)),
            Node::Loop {
                var,
                from,
                to,
                body,
            } => Node::Loop {
                var,
                from,
                to,
                body: attribute_nodes(body, parent),
            },
            Node::If {
                cond,
                then,
                otherwise,
            } => Node::If {
                cond,
                then: attribute_nodes(then, parent),
                otherwise: attribute_nodes(otherwise, parent),
            },
            other => other,
        })
        .collect()
}

/// Fuse composed arms under a root Region that names `op_id`, lowering a
/// fusion failure to an explicit trap.
///
/// Fusion of these disjoint-buffer arms failing is a substrate bug. Returning
/// an empty Program instead would run cleanly and report zero survivors, which
/// reads as a correct compaction of an empty input.
///
/// # Why the fused entry is tagged rather than left anonymous
///
/// `fuse_programs` returns an entry of several nodes, so `Program::wrapped`
/// stamps the generic `vyre.program.root` marker over it. That root names no op,
/// which means the emitted IR does not state which exatok op produced it and
/// `cargo xtask print-composition` attributes the whole program to nothing. The
/// op id being correct in a constant is not the same as it being correct in the
/// IR, and the Tier 4 audit reads the IR. `tag_program` names the root, and
/// `attribute_regions` then reaches the Regions nested below it.
fn fuse_or_trap(op_id: &str, output: &str, arms: &[Program]) -> Program {
    match fuse_programs(arms) {
        Ok(program) => attribute_regions(tag_program(op_id, program), op_id),
        Err(error) => trap_program(
            op_id,
            output,
            DataType::U32,
            format!(
                "{op_id} could not fuse its {} arms: {error}. Fix: repair grid-sync fusion for \
                 multi-pass exatok selection; do not substitute an empty Program.",
                arms.len()
            ),
        ),
    }
}

/// One-lane program writing a zero count, for an empty input array.
fn empty_count_program(op_id: &str, count: &str) -> Program {
    Program::wrapped(
        vec![BufferDecl::output(count, 0, DataType::U32).with_count(1)],
        [1, 1, 1],
        vec![wrap_anonymous(
            op_id,
            vec![Node::if_then(
                Expr::eq(Expr::gid_x(), Expr::u32(0)),
                vec![Node::store(count, Expr::u32(0), Expr::u32(0))],
            )],
        )],
    )
}

/// One-lane no-op flag program, for an empty input array.
#[cfg(feature = "multi-merge")]
fn empty_flag_program(op_id: &str, flags: &str) -> Program {
    Program::wrapped(
        vec![BufferDecl::output(flags, 0, DataType::U32).with_count(1)],
        [1, 1, 1],
        vec![wrap_anonymous(
            op_id,
            vec![Node::if_then(
                Expr::eq(Expr::gid_x(), Expr::u32(0)),
                vec![Node::store(flags, Expr::u32(0), Expr::u32(0))],
            )],
        )],
    )
}

// ---------------------------------------------------------------------------
// Host oracles.
// ---------------------------------------------------------------------------

/// Leftmost minimum-rank pair index and its rank over one window, or `None`
/// when no pair in the window is mergeable.
///
/// `None` rather than a sentinel index so "nothing to merge" cannot be
/// confused with a merge at index 0.
#[must_use]
pub fn host_argmin_leftmost(ranks: &[Rank]) -> Option<(u32, Rank)> {
    let mut best: Option<(u32, Rank)> = None;
    for (index, &rank) in ranks.iter().enumerate() {
        if !rank.is_present() {
            continue;
        }
        let index = u32::try_from(index).ok()?;
        match best {
            // Strictly-less keeps the FIRST occurrence of a repeated minimum,
            // which is the leftmost tie-break the device must reproduce.
            Some((_, current)) if rank.0 >= current.0 => {}
            _ => best = Some((index, rank)),
        }
    }
    best
}

/// Per-segment leftmost minimum-rank selection, with ABSOLUTE indices.
///
/// The oracle for [`segmented_argmin_leftmost`]. Returns one entry per
/// segment, `None` for a segment with no mergeable pair. The outer `None`
/// means the segment table is malformed: fewer than two words, not starting at
/// zero, not ascending, or not ending at `ranks.len()`. Refusing a malformed
/// table matters because a silently clamped table would make a device
/// comparison pass on a shorter window than the caller asked for.
#[must_use]
pub fn host_segmented_argmin_leftmost(
    ranks: &[Rank],
    segment_starts: &[u32],
) -> Option<Vec<Option<(u32, Rank)>>> {
    let total = u32::try_from(ranks.len()).ok()?;
    if segment_starts.len() < 2 || segment_starts[0] != 0 || *segment_starts.last()? != total {
        return None;
    }
    if segment_starts.windows(2).any(|pair| pair[0] > pair[1]) {
        return None;
    }
    let mut out = Vec::with_capacity(segment_starts.len() - 1);
    for window in segment_starts.windows(2) {
        let (begin, end) = (window[0] as usize, window[1] as usize);
        out.push(
            host_argmin_leftmost(ranks.get(begin..end)?)
                .map(|(offset, rank)| (offset + window[0], rank)),
        );
    }
    Some(out)
}

/// Survivors of a removal pass in exact original order, and their count.
///
/// The oracle for [`compact_removed`]. `None` on a length mismatch: zipping
/// two unequal arrays would silently truncate and let a parity assertion pass
/// on a short comparison.
#[must_use]
pub fn host_compact_removed(values: &[u32], removed: &[u32]) -> Option<(Vec<u32>, u32)> {
    if values.len() != removed.len() {
        return None;
    }
    let survivors: Vec<u32> = values
        .iter()
        .zip(removed)
        .filter(|&(_, &flag)| flag == 0)
        .map(|(&value, _)| value)
        .collect();
    let count = u32::try_from(survivors.len()).ok()?;
    Some((survivors, count))
}

/// Segment table rebased onto a compacted array.
///
/// The oracle for [`remap_segment_starts`]. `None` when the table is malformed
/// or the flag array length disagrees with the table's total.
#[must_use]
pub fn host_remap_segment_starts(removed: &[u32], segment_starts: &[u32]) -> Option<Vec<u32>> {
    let total = u32::try_from(removed.len()).ok()?;
    if segment_starts.len() < 2 || segment_starts[0] != 0 || *segment_starts.last()? != total {
        return None;
    }
    // Survivors strictly before each index: the exclusive scan of keep flags.
    let mut survivors_before = Vec::with_capacity(removed.len() + 1);
    let mut running = 0u32;
    survivors_before.push(0);
    for &flag in removed {
        running += u32::from(flag == 0);
        survivors_before.push(running);
    }
    Some(
        segment_starts
            .iter()
            .map(|&start| survivors_before[start as usize])
            .collect(),
    )
}

/// One reference merge per segment, applied simultaneously: the new token
/// array and the rebased segment table.
///
/// The oracle for [`segmented_argmin_leftmost`] composed with
/// [`apply_argmin_merges`] and [`remap_segment_starts`], which together are
/// one pass of the default merge loop. `None` on a malformed segment table or
/// a length disagreement among the parallel arrays.
#[must_use]
pub fn host_argmin_merge_pass(
    tokens: &[TokenId],
    ranks: &[Rank],
    merged_ids: &[TokenId],
    segment_starts: &[u32],
) -> Option<(Vec<TokenId>, Vec<u32>)> {
    if tokens.len() != ranks.len() || tokens.len() != merged_ids.len() {
        return None;
    }
    let selections = host_segmented_argmin_leftmost(ranks, segment_starts)?;
    let mut staged: Vec<TokenId> = tokens.to_vec();
    let mut removed = vec![0u32; tokens.len()];
    for selection in selections.into_iter().flatten() {
        let index = selection.0 as usize;
        // A selected index is never a segment's last slot, so `index + 1` is
        // inside the same segment. Refuse rather than wrap if it is not.
        if index + 1 >= tokens.len() {
            return None;
        }
        staged[index] = merged_ids[index];
        removed[index + 1] = 1;
    }
    let survivors = staged
        .iter()
        .zip(&removed)
        .filter(|&(_, &flag)| flag == 0)
        .map(|(&token, _)| token)
        .collect();
    let new_starts = host_remap_segment_starts(&removed, segment_starts)?;
    Some((survivors, new_starts))
}

/// Per-position selection flags for the maximal left-biased non-overlapping
/// set of positions whose rank equals `target`.
///
/// The oracle for `select_non_overlapping`, written as the plain sequential
/// recurrence `take[i] = matches[i] && !take[i - 1]` so it shares no structure
/// with the parallel formulation it checks. An absent `target` selects
/// nothing.
#[must_use]
pub fn host_select_non_overlapping(ranks: &[Rank], target: Rank) -> Vec<u32> {
    let mut flags = Vec::with_capacity(ranks.len());
    let mut previous_taken = false;
    for &rank in ranks {
        let taken = target.is_present() && rank == target && !previous_taken;
        flags.push(u32::from(taken));
        previous_taken = taken;
    }
    flags
}

/// Indices selected by [`host_select_non_overlapping`].
#[must_use]
pub fn host_selected_indices(ranks: &[Rank], target: Rank) -> Vec<u32> {
    host_select_non_overlapping(ranks, target)
        .into_iter()
        .enumerate()
        .filter(|&(_, flag)| flag != 0)
        .filter_map(|(index, _)| u32::try_from(index).ok())
        .collect()
}

/// Token array after applying every selected merge simultaneously.
///
/// The oracle for `apply_merges`. `None` on a length mismatch, or when
/// `selected` overlaps or names the final slot, because both make the result
/// undefined rather than merely different.
#[must_use]
pub fn host_apply_merges(
    tokens: &[TokenId],
    selected: &[u32],
    merged_ids: &[TokenId],
) -> Option<Vec<TokenId>> {
    if tokens.len() != selected.len() || tokens.len() != merged_ids.len() {
        return None;
    }
    if selected.last().is_some_and(|&flag| flag != 0) {
        return None;
    }
    if selected.windows(2).any(|pair| pair[0] != 0 && pair[1] != 0) {
        return None;
    }
    let mut out = Vec::with_capacity(tokens.len());
    let mut position = 0usize;
    while position < tokens.len() {
        if selected[position] != 0 {
            out.push(merged_ids[position]);
            position += 2;
        } else {
            out.push(tokens[position]);
            position += 1;
        }
    }
    Some(out)
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Locks the leftmost tie-break in the oracle itself. A `<=` comparison
    /// here would silently make the oracle prefer the RIGHTMOST minimum, and
    /// then every device parity test would agree with a wrong reference.
    #[test]
    fn host_argmin_keeps_the_first_of_a_repeated_minimum() {
        let ranks = [Rank(5), Rank(2), Rank(9), Rank(2), Rank(2)];
        assert_eq!(host_argmin_leftmost(&ranks), Some((1, Rank(2))));
    }

    /// An all-absent window has no mergeable pair. Returning `Some((0, ...))`
    /// would drive a merge of tokens 0 and 1 that the reference never makes.
    #[test]
    fn host_argmin_reports_none_when_every_rank_is_absent() {
        let ranks = [Rank::ABSENT; 4];
        assert_eq!(host_argmin_leftmost(&ranks), None);
        assert_eq!(host_argmin_leftmost(&[]), None);
    }

    /// Segment indices must be ABSOLUTE. Returning a within-segment offset
    /// would address the first pretoken's tokens from every segment, silently
    /// merging the wrong pair everywhere except segment 0.
    #[test]
    fn host_segmented_argmin_reports_absolute_indices() {
        let ranks = [
            Rank(9),
            Rank(4),
            Rank::ABSENT,
            Rank(3),
            Rank(3),
            Rank::ABSENT,
        ];
        let starts = [0, 3, 6];
        assert_eq!(
            host_segmented_argmin_leftmost(&ranks, &starts),
            Some(vec![Some((1, Rank(4))), Some((3, Rank(3)))])
        );
    }

    /// A malformed table must be refused, not clamped: a table whose sentinel
    /// disagrees with the rank array would compare the device against a
    /// shorter window than it actually reduced.
    #[test]
    fn host_segmented_argmin_refuses_a_malformed_table() {
        let ranks = [Rank(1), Rank::ABSENT];
        assert_eq!(host_segmented_argmin_leftmost(&ranks, &[0, 1]), None);
        assert_eq!(host_segmented_argmin_leftmost(&ranks, &[1, 2]), None);
        assert_eq!(host_segmented_argmin_leftmost(&ranks, &[0]), None);
        assert_eq!(host_segmented_argmin_leftmost(&ranks, &[0, 2, 1]), None);
    }

    /// A mismatched flag array must not compare equal on a truncated prefix.
    #[test]
    fn host_compact_rejects_a_length_mismatch() {
        assert_eq!(host_compact_removed(&[1, 2, 3], &[0, 0]), None);
        assert_eq!(
            host_compact_removed(&[1, 2, 3], &[0, 1, 0]),
            Some((vec![1, 3], 2))
        );
    }

    /// The rebased table must count survivors STRICTLY before each start. Off
    /// by one here shifts every pretoken boundary by a token, which corrupts
    /// the next pass rather than failing.
    #[test]
    fn host_remap_counts_survivors_strictly_before_each_start() {
        // Removing index 1 shortens segment 0 from 3 tokens to 2, so segment 1
        // starts at 2 instead of 3 and the total drops from 5 to 4.
        let removed = [0, 1, 0, 0, 0];
        assert_eq!(
            host_remap_segment_starts(&removed, &[0, 3, 5]),
            Some(vec![0, 2, 4])
        );
        // A removal at the very start of a segment still leaves the boundary
        // where the earlier survivors end.
        assert_eq!(
            host_remap_segment_starts(&[0, 0, 1, 0, 0], &[0, 2, 5]),
            Some(vec![0, 2, 4])
        );
        assert_eq!(host_remap_segment_starts(&removed, &[0, 3, 4]), None);
    }

    /// One pass of the default loop must merge in EVERY segment at once, and
    /// rebase the table so a second pass is addressable.
    #[test]
    fn host_argmin_pass_merges_every_segment_and_rebases() {
        // Two pretokens of three tokens each. Segment 0 merges at index 0,
        // segment 1 merges at index 4.
        let tokens = [
            TokenId(1),
            TokenId(2),
            TokenId(3),
            TokenId(4),
            TokenId(5),
            TokenId(6),
        ];
        let ranks = [
            Rank(7),
            Rank(9),
            Rank::ABSENT,
            Rank(8),
            Rank(2),
            Rank::ABSENT,
        ];
        let merged = [
            TokenId(90),
            TokenId(91),
            TokenId(92),
            TokenId(93),
            TokenId(94),
            TokenId(95),
        ];
        assert_eq!(
            host_argmin_merge_pass(&tokens, &ranks, &merged, &[0, 3, 6]),
            Some((
                vec![TokenId(90), TokenId(3), TokenId(4), TokenId(94)],
                vec![0, 2, 4]
            ))
        );
    }

    /// A converged segment must sit out the pass without disturbing its
    /// neighbour, which is how the loop terminates per pretoken.
    #[test]
    fn host_argmin_pass_leaves_a_converged_segment_alone() {
        let tokens = [TokenId(1), TokenId(2), TokenId(3), TokenId(4)];
        let ranks = [Rank::ABSENT, Rank::ABSENT, Rank(5), Rank::ABSENT];
        let merged = [TokenId(80), TokenId(81), TokenId(82), TokenId(83)];
        assert_eq!(
            host_argmin_merge_pass(&tokens, &ranks, &merged, &[0, 2, 4]),
            Some((vec![TokenId(1), TokenId(2), TokenId(82)], vec![0, 2, 3]))
        );
    }

    /// The sequential recurrence must skip the position immediately after a
    /// take, which is the whole non-overlap property.
    #[test]
    fn host_selection_skips_the_neighbour_of_a_taken_position() {
        let ranks = [Rank(7), Rank(7), Rank(7), Rank(7)];
        assert_eq!(
            host_select_non_overlapping(&ranks, Rank(7)),
            vec![1, 0, 1, 0]
        );
        assert_eq!(host_selected_indices(&ranks, Rank(7)), vec![0, 2]);
    }

    /// An absent target must select nothing even though every slot equals it.
    #[test]
    fn host_selection_ignores_an_absent_target() {
        let ranks = [Rank::ABSENT, Rank::ABSENT, Rank::ABSENT];
        assert_eq!(
            host_select_non_overlapping(&ranks, Rank::ABSENT),
            vec![0, 0, 0]
        );
        assert!(host_selected_indices(&ranks, Rank::ABSENT).is_empty());
    }

    /// Overlapping selection has no defined result, so the oracle must refuse
    /// it rather than invent one and legitimise a broken selection kernel.
    #[test]
    fn host_apply_merges_refuses_overlapping_or_trailing_selection() {
        let tokens = [TokenId(1), TokenId(2), TokenId(3), TokenId(4)];
        let merged = [TokenId(10), TokenId(20), TokenId(30), TokenId(40)];
        assert_eq!(host_apply_merges(&tokens, &[1, 1, 0, 0], &merged), None);
        assert_eq!(host_apply_merges(&tokens, &[0, 0, 0, 1], &merged), None);
        assert_eq!(
            host_apply_merges(&tokens, &[1, 0, 1, 0], &merged),
            Some(vec![TokenId(10), TokenId(30)])
        );
    }

    /// This test is what stops the composition audit from being circular. Do
    /// not delete it as redundant with the two Tier 4 gates: those check that
    /// every Region HAS an attribution, this checks that the attribution is not
    /// manufactured.
    ///
    /// `attribute_regions` satisfies an audit, so it is only honest if the
    /// parent links it writes are TRUE. The dangerous failure is not a severed
    /// chain, which is visible, but a pass that reassigns EVERY parent to
    /// whichever op composed last: that yields a fully connected tree, both
    /// gates pass, and `print-composition` misattributes real work. The edge a
    /// clobber would relocate is the `min_u32_child` child, which points at its
    /// own composing op, so the run below deliberately composes under a
    /// DIFFERENT op id than that recorded parent.
    ///
    /// Both halves are asserted in one run because each alone is passable by a
    /// degenerate implementation: preservation alone passes a pass that writes
    /// nothing, and addition alone passes a pass that overwrites everything.
    /// The generator name is checked too, since a rewrite that flattened every
    /// generator to the composing op would erase which primitive produced the
    /// node, the one fact the audit exists to report.
    #[test]
    // `Program::new` preserves raw top-level entry nodes, which is what this
    // needs: `Program::wrapped` would add the root marker whose handling is
    // under test. Its deprecation note reserves `new` for exactly this case.
    #[allow(deprecated)]
    fn attribution_writes_missing_edges_without_relocating_existing_ones() {
        let owned = "vyre-primitives::reduce::min_u32_child";
        let unattributed =
            "vyre-primitives::reduce::multi_block_prefix_scan::guarded_single_block";
        let program = Program::new(
            vec![BufferDecl::output("out", 0, DataType::U32).with_count(1)],
            [1, 1, 1],
            vec![
                Node::Region {
                    generator: Ident::from(owned.to_owned()),
                    source_region: Some(GeneratorRef {
                        name: ARGMIN_OP_ID.to_owned(),
                    }),
                    body: Arc::new(vec![]),
                },
                Node::Region {
                    generator: Ident::from(unattributed.to_owned()),
                    source_region: None,
                    body: Arc::new(vec![]),
                },
            ],
        );

        // Compose under COMPACT_OP_ID while one child already claims ARGMIN_OP_ID.
        let attributed = attribute_regions(program, COMPACT_OP_ID);
        let entry = attributed.entry();
        assert_eq!(entry.len(), 2, "attribution must not add or drop nodes");

        match (&entry[0], &entry[1]) {
            (
                Node::Region {
                    generator: kept_name,
                    source_region: kept_parent,
                    ..
                },
                Node::Region {
                    generator: added_name,
                    source_region: added_parent,
                    ..
                },
            ) => {
                assert_eq!(kept_name.as_ref(), owned);
                assert_eq!(
                    kept_parent.as_ref().map(|parent| parent.name.as_str()),
                    Some(ARGMIN_OP_ID),
                    "an existing parent was relocated to the composing op"
                );
                assert_eq!(added_name.as_ref(), unattributed);
                assert_eq!(
                    added_parent.as_ref().map(|parent| parent.name.as_str()),
                    Some(COMPACT_OP_ID),
                    "a missing parent was not written"
                );
            }
            other => unreachable!("attribution changed the node shape: {other:?}"),
        }
    }

    /// Locks the reach of the rewrite into `If` and `Loop` bodies.
    ///
    /// The real violation was a named primitive Region nested inside an `If`
    /// guard, which an entry-level or Region-and-Block-only walk cannot see.
    ///
    /// The scan emits that arm only for SMALL inputs: `multi_block_prefix_scan`
    /// dispatches `try_guarded_single_block_scan` when `n <= BLOCK_LANES`
    /// (1024), and takes the three-pass Blelloch chain, whose Regions are
    /// `pass_a` and `pass_c`, above it. So `compact_removed` at n = 8 is what
    /// reaches `guarded_single_block`, and the n = 3 * 1024 + 7 case reaches the
    /// chain instead. The two fixtures cover DISJOINT scan paths and neither
    /// subsumes the other, which is why both stay in `emitted_programs`. This
    /// test pins the shape directly so the guarantee does not depend on either
    /// size continuing to route where it does today.
    #[test]
    // Raw entry nodes, per the note on the test above.
    #[allow(deprecated)]
    fn attribution_reaches_regions_nested_in_control_flow() {
        let nested = Node::Region {
            generator: Ident::from("vyre-primitives::guarded".to_owned()),
            source_region: None,
            body: Arc::new(vec![]),
        };
        let program = Program::new(
            vec![BufferDecl::output("out", 0, DataType::U32).with_count(1)],
            [1, 1, 1],
            vec![Node::If {
                cond: Expr::bool(true),
                then: vec![nested.clone()],
                otherwise: vec![Node::Loop {
                    var: Ident::from("i".to_owned()),
                    from: Expr::u32(0),
                    to: Expr::u32(1),
                    body: vec![nested],
                }],
            }],
        );

        let attributed = attribute_regions(program, COMPACT_OP_ID);
        let mut parents = Vec::new();
        collect_parents(attributed.entry(), &mut parents);
        assert_eq!(
            parents,
            vec![Some(COMPACT_OP_ID.to_owned()), Some(COMPACT_OP_ID.to_owned())]
        );
    }

    fn collect_parents(nodes: &[Node], out: &mut Vec<Option<String>>) {
        for node in nodes {
            match node {
                Node::Region {
                    source_region,
                    body,
                    ..
                } => {
                    out.push(source_region.as_ref().map(|parent| parent.name.clone()));
                    collect_parents(body.as_ref(), out);
                }
                Node::Block(body) => collect_parents(body, out),
                Node::Loop { body, .. } => collect_parents(body, out),
                Node::If {
                    then, otherwise, ..
                } => {
                    collect_parents(then, out);
                    collect_parents(otherwise, out);
                }
                _ => {}
            }
        }
    }
}