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
//! Reference-tokenizer parity support. OWNER: ParityGate.
//!
//! Builds a merge table from a real `.tiktoken` artifact by deriving pair
//! entries, and supplies the corpus the host encoder is gated against. This
//! is the crate's central exactness claim: without it every other test only
//! proves exatok agrees with itself.
//!
//! Acceptance: byte-exact token ids against fixtures generated from the
//! reference tokenizer, for more than one vocabulary family, plus a
//! deliberately corrupted rank proving the comparison can actually fail.
//!
//! # The whole host pipeline, in one place
//!
//! Nothing else in the crate joins the three host stages. [`crate::vocab`]
//! turns an artifact into a table, [`crate::pretokenize`] turns bytes into
//! spans, and [`crate::reference`] turns one pretoken's ids into merged ids;
//! [`encode_bytes`] is the composition, and it is the only thing a fixture
//! comparison can meaningfully be run against. A per-stage test can pass while
//! the joins are wrong: a byte-to-id map off by one, a span fed to the wrong
//! table, an encoder called per input instead of per pretoken.
//!
//! Pair derivation is *not* reimplemented here. [`crate::vocab::Vocabulary`]
//! already enumerates every split `t = a + b` with both halves in the
//! vocabulary, which is the derivation the reference tokenizer's runtime lookup
//! implies, so this module loads through it and asserts the resulting entry
//! count rather than deriving a second time.
//!
//! # A divergence has to be locatable, not just detectable
//!
//! [`compare`] and [`first_divergence`] report the first differing id with its
//! byte offset in the input, the pretoken carrying it, that pretoken's index,
//! and both ids. A verdict is not a diagnosis: the cl100k fixture pins 1211 ids
//! over 3593 corpus bytes, so "ascii_prose differs at id 11" means re-splitting
//! the input on paper before the debugging can even start. [`Segment`] keeps
//! the split beside the ids for exactly that reason, and the flattened segments
//! are asserted equal to [`encode_bytes`] so the report can never describe a
//! stream the gate did not compare.
//!
//! # Ground truth is generated once, offline
//!
//! Expected ids come from `tests/fixtures/parity_<vocabulary>.json`, written by
//! `python3 tests/fixtures/generate_parity_fixtures.py`. Tests read the fixture
//! and never invoke python, so the suite is hermetic: a machine with no python,
//! or a different `tiktoken`, still runs the same comparison against the same
//! recorded ids.
//!
//! [`corpus`] restates the fixture inputs in Rust on purpose. The fixture
//! carries the text it was generated from, so a test that compares the two
//! catches a fixture regenerated from a drifted corpus. Without that check a
//! renamed or shortened case would silently narrow the gate while still
//! reporting every case green.
//!
//! # Invalid UTF-8 has no reference output, and is still gated
//!
//! `tiktoken`'s entry point takes `str`, and its `_encode_bytes` fallback runs a
//! different algorithm for a malformed tail: it re-runs BPE across the last
//! pretoken boundary. [`crate::pretokenize`] instead specifies one byte of
//! recovery per malformed byte, placed in the `[^\s\p{L}\p{N}]` class. So
//! [`byte_corpus`] states its pretoken split from that rule directly and takes
//! ids from `tiktoken._educational.bpe_encode`, which is plain
//! leftmost-lowest-rank merging over arbitrary bytes. Both halves of the
//! pipeline are still checked against something outside exatok.

use crate::pretokenize::{SplitPattern, spans};
use crate::reference::{HostMergeTable, MergeTable, encode};
use crate::{PairKey, Rank, TokenId, ExatokError};

/// Split `input` and map each pretoken to its starting one-id-per-byte sequence.
///
/// Returned separately from [`encode_bytes`] so a test can assert the split
/// itself, which is the half of the pipeline a fixture of final ids cannot
/// localize: identical final ids can come from a wrong split whose merges
/// happen to reconverge.
#[must_use]
pub fn pretoken_ids(
    pattern: SplitPattern,
    input: &[u8],
    bytes: &[TokenId; 256],
) -> Vec<Vec<TokenId>> {
    spans(pattern, input)
        .into_iter()
        .map(|span| {
            input[span.start..span.end]
                .iter()
                .map(|&byte| bytes[byte as usize])
                .collect()
        })
        .collect()
}

/// Encode `input` end to end: split, map bytes to ids, merge per pretoken.
///
/// `table` is taken separately from the byte map so a deliberately corrupted
/// table can be driven through the identical path as the loaded one.
#[must_use]
pub fn encode_bytes(
    pattern: SplitPattern,
    input: &[u8],
    bytes: &[TokenId; 256],
    table: &impl MergeTable,
) -> Vec<TokenId> {
    encode(&pretoken_ids(pattern, input, bytes), table)
}

/// One pretoken's place in the input and the ids it merged to.
///
/// [`encode_bytes`] returns the flat stream the fixture pins, and a flat stream
/// cannot say WHERE it diverged: "id 137 of 1211" names no pretoken and no
/// byte, so every divergence turns into a manual bisection of the input.
/// Keeping the split beside the ids is what turns a failure into an address.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Segment {
    /// Byte offset of this pretoken's first byte in the input.
    pub offset: usize,
    /// This pretoken's bytes.
    pub bytes: Vec<u8>,
    /// Ids this pretoken merged to.
    pub ids: Vec<TokenId>,
}

/// Encode `input` keeping each pretoken's offset, bytes, and ids.
///
/// Merges through [`crate::reference::encode`] with a one-element slice rather
/// than through [`crate::reference::encode_pretoken`], because `encode` is the
/// loop [`encode_bytes`] runs and the two loops are separate copies. Calling
/// the other one here would let the located report describe ids the compared
/// stream never held.
#[must_use]
pub fn encode_segments(
    pattern: SplitPattern,
    input: &[u8],
    bytes: &[TokenId; 256],
    table: &impl MergeTable,
) -> Vec<Segment> {
    spans(pattern, input)
        .into_iter()
        .map(|span| {
            let piece = &input[span.start..span.end];
            let start: Vec<TokenId> = piece.iter().map(|&byte| bytes[byte as usize]).collect();
            Segment {
                offset: span.start,
                bytes: piece.to_vec(),
                ids: encode(std::slice::from_ref(&start), table),
            }
        })
        .collect()
}

/// Flatten `segments` into the id stream [`encode_bytes`] would produce.
#[must_use]
pub fn segment_ids(segments: &[Segment]) -> Vec<TokenId> {
    segments
        .iter()
        .flat_map(|segment| segment.ids.iter().copied())
        .collect()
}

/// First position where two id streams differ.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct IdMismatch {
    /// Index into both streams. Equal to the shorter length when one is a
    /// prefix of the other.
    pub index: usize,
    /// Id the reference has there, or `None` when the reference ended.
    pub expected: Option<TokenId>,
    /// Id exatok produced there, or `None` when exatok ended.
    pub actual: Option<TokenId>,
}

/// First index where `expected` and `actual` disagree, if any.
///
/// A length difference is a mismatch at the shorter length rather than a
/// separate outcome, so a truncated stream reports the position where it
/// stopped instead of only its size.
#[must_use]
pub fn first_mismatch(expected: &[TokenId], actual: &[TokenId]) -> Option<IdMismatch> {
    let shared = expected.len().min(actual.len());
    for index in 0..shared {
        if expected[index] != actual[index] {
            return Some(IdMismatch {
                index,
                expected: expected.get(index).copied(),
                actual: actual.get(index).copied(),
            });
        }
    }
    if expected.len() == actual.len() {
        return None;
    }
    Some(IdMismatch {
        index: shared,
        expected: expected.get(shared).copied(),
        actual: actual.get(shared).copied(),
    })
}

/// The first divergence between two id streams, located in the input.
///
/// Carries the address, not just the verdict: which pretoken, at which byte
/// offset, which id of that pretoken, and both ids. A boolean, or an id index
/// alone, leaves the reader bisecting a 3000-byte corpus by hand.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Divergence {
    /// Index into the whole id stream.
    pub index: usize,
    /// Id the reference has there, or `None` when the reference stream ended.
    pub expected: Option<TokenId>,
    /// Id exatok produced there, or `None` when exatok's stream ended.
    pub actual: Option<TokenId>,
    /// Index of the pretoken carrying the diverging id.
    pub pretoken_index: usize,
    /// Byte offset of that pretoken's first byte in the input.
    pub byte_offset: usize,
    /// That pretoken's bytes.
    pub pretoken: Vec<u8>,
    /// Index of the diverging id inside that pretoken's ids.
    pub index_in_pretoken: usize,
}

/// Render `bytes` so a malformed or control-heavy pretoken stays readable.
///
/// ASCII printables pass through and everything else becomes `\xNN`, because a
/// byte case is deliberately not valid UTF-8 and a lossy conversion would print
/// a replacement character where the interesting byte was.
fn quoted(bytes: &[u8]) -> String {
    let mut out = String::with_capacity(bytes.len() + 2);
    out.push('"');
    for &byte in bytes {
        match byte {
            b'"' => out.push_str("\\\""),
            b'\\' => out.push_str("\\\\"),
            0x20..=0x7e => out.push(byte as char),
            _ => {
                use std::fmt::Write;
                let _ = write!(out, "\\x{byte:02x}");
            }
        }
    }
    out.push('"');
    out
}

impl std::fmt::Display for Divergence {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let show = |id: Option<TokenId>| match id {
            Some(id) => id.0.to_string(),
            None => "<stream ended>".to_owned(),
        };
        write!(
            formatter,
            "id {} differs: reference {}, exatok {}; byte offset {}, pretoken {} {}, id {} of \
             that pretoken",
            self.index,
            show(self.expected),
            show(self.actual),
            self.byte_offset,
            self.pretoken_index,
            quoted(&self.pretoken),
            self.index_in_pretoken
        )
    }
}

/// Locate [`first_mismatch`] inside the pretoken split that produced `segments`.
///
/// Attribution uses exatok's own segmentation, which is the segmentation a
/// reader has to inspect: the reference stream is flat and carries no split.
/// When exatok's stream ended first the report names the LAST pretoken it
/// produced, with `index_in_pretoken` one past that pretoken's ids, since there
/// is no later pretoken to point at.
#[must_use]
pub fn first_divergence(expected: &[TokenId], segments: &[Segment]) -> Option<Divergence> {
    let actual = segment_ids(segments);
    let mismatch = first_mismatch(expected, &actual)?;
    let mut base = 0usize;
    let mut located = None;
    for (index, segment) in segments.iter().enumerate() {
        if mismatch.index < base + segment.ids.len() {
            located = Some((index, mismatch.index - base));
            break;
        }
        base += segment.ids.len();
    }
    let (pretoken_index, index_in_pretoken) = located.unwrap_or_else(|| {
        let last = segments.len().saturating_sub(1);
        (last, segments.last().map_or(0, |segment| segment.ids.len()))
    });
    let (byte_offset, pretoken) = segments.get(pretoken_index).map_or_else(
        || (0, Vec::new()),
        |segment| (segment.offset, segment.bytes.clone()),
    );
    Some(Divergence {
        index: mismatch.index,
        expected: mismatch.expected,
        actual: mismatch.actual,
        pretoken_index,
        byte_offset,
        pretoken,
        index_in_pretoken,
    })
}

/// Encode `input` and locate the first divergence from `expected`.
///
/// The whole comparison in one call, so a caller cannot accidentally compare a
/// stream from one table against segments from another.
#[must_use]
pub fn compare(
    pattern: SplitPattern,
    input: &[u8],
    bytes: &[TokenId; 256],
    table: &impl MergeTable,
    expected: &[TokenId],
) -> Option<Divergence> {
    first_divergence(expected, &encode_segments(pattern, input, bytes, table))
}

/// Copy `table` with the rank recorded for `pair` replaced by `rank`.
///
/// Exists so the gate can be shown to fail. A parity test that only ever runs
/// against a correct table cannot distinguish "the ids match" from "the
/// comparison is vacuous", and the cheapest way to tell them apart is to break
/// one entry and watch the comparison notice.
///
/// # Errors
///
/// [`ExatokError::Artifact`] when `pair` is absent, so corrupting nothing
/// cannot masquerade as a successful corruption, or when `rank` is the
/// [`Rank::ABSENT`] sentinel, which [`HostMergeTable`] rejects outright.
pub fn with_rank_replaced(
    artifact: &str,
    table: &HostMergeTable,
    pair: PairKey,
    rank: Rank,
) -> Result<HostMergeTable, ExatokError> {
    if table.lookup(pair).is_none() {
        return Err(ExatokError::Artifact {
            artifact: artifact.to_owned(),
            location: format!("pair ({}, {})", pair.left().0, pair.right().0),
            detail: "cannot replace the rank of a pair the table does not hold".to_owned(),
            fix: "pick a pair that is present, so the corruption actually changes the table"
                .to_owned(),
        });
    }
    HostMergeTable::from_entries(
        artifact,
        table.iter().map(|(key, entry)| {
            let replaced = if key == pair { rank } else { entry.rank };
            (key, entry.id, replaced)
        }),
    )
}

/// Copy `table` with `pair` removed entirely.
///
/// A second, structurally different corruption from [`with_rank_replaced`].
/// Replacing a rank changes merge ORDER; removing an entry changes what is
/// reachable at all, which is the shape of the real derivation bug: keep only
/// the canonical split of each token and the table is a strict subset of the
/// correct one, with every count and every id that survives still right.
///
/// # Errors
///
/// [`ExatokError::Artifact`] when `pair` is absent, so removing nothing cannot
/// be mistaken for a successful removal.
pub fn without_pair(
    artifact: &str,
    table: &HostMergeTable,
    pair: PairKey,
) -> Result<HostMergeTable, ExatokError> {
    if table.lookup(pair).is_none() {
        return Err(ExatokError::Artifact {
            artifact: artifact.to_owned(),
            location: format!("pair ({}, {})", pair.left().0, pair.right().0),
            detail: "cannot remove a pair the table does not hold".to_owned(),
            fix: "pick a pair that is present, so the removal actually changes the table"
                .to_owned(),
        });
    }
    HostMergeTable::from_entries(
        artifact,
        table
            .iter()
            .filter(|(key, _)| *key != pair)
            .map(|(key, entry)| (key, entry.id, entry.rank)),
    )
}

/// The pair the merge rule would apply first to `tokens`.
///
/// The leftmost occurrence of the lowest rank, which is the reference rule.
/// Exposed so a corruption experiment can target the merge that definitely
/// happens instead of guessing one, since a corruption of an unused entry
/// changes nothing and would make the experiment vacuous.
#[must_use]
pub fn first_merge(tokens: &[TokenId], table: &impl MergeTable) -> Option<PairKey> {
    let mut best: Option<(Rank, PairKey)> = None;
    for window in tokens.windows(2) {
        let pair = PairKey::new(window[0], window[1]);
        let rank = table.rank(pair);
        if !rank.is_present() {
            continue;
        }
        if best.is_none_or(|(current, _)| rank < current) {
            best = Some((rank, pair));
        }
    }
    best.map(|(_, pair)| pair)
}

/// Decode a lowercase hex byte string, as the fixture stores raw bytes.
///
/// Hex rather than base64 or a JSON string because a byte case is deliberately
/// not valid UTF-8 and must survive a round trip through JSON unchanged.
///
/// # Errors
///
/// [`ExatokError::Artifact`] on an odd length or a non-hex character, naming
/// the offending index.
pub fn decode_hex(artifact: &str, text: &str) -> Result<Vec<u8>, ExatokError> {
    let error = |location: String, detail: String| ExatokError::Artifact {
        artifact: artifact.to_owned(),
        location,
        detail,
        fix: "store the field as an even-length string of characters 0-9 and a-f".to_owned(),
    };
    let raw = text.as_bytes();
    if raw.len() % 2 != 0 {
        return Err(error(
            format!("length {}", raw.len()),
            "hex string has an odd number of characters".to_owned(),
        ));
    }
    let mut out = Vec::with_capacity(raw.len() / 2);
    for (index, chunk) in raw.chunks_exact(2).enumerate() {
        let mut value = 0u8;
        for (half, &character) in chunk.iter().enumerate() {
            let digit = match character {
                b'0'..=b'9' => character - b'0',
                b'a'..=b'f' => character - b'a' + 10,
                _ => {
                    return Err(error(
                        format!("character {}", index * 2 + half),
                        format!("{:?} is not a lowercase hex digit", character as char),
                    ));
                }
            };
            value = (value << 4) | digit;
        }
        out.push(value);
    }
    Ok(out)
}

/// One corpus input and what it exists to catch.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Case {
    /// Stable name, matched against the fixture.
    pub name: &'static str,
    /// The specific divergence this input would expose.
    pub concern: &'static str,
    /// Input text.
    pub text: String,
}

/// One byte-level corpus input, with its expected pretoken split.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ByteCase {
    /// Stable name, matched against the fixture.
    pub name: &'static str,
    /// The specific divergence this input would expose.
    pub concern: &'static str,
    /// Input bytes, not valid UTF-8.
    pub bytes: Vec<u8>,
    /// Pretokens the split pattern must produce, stated from the pattern.
    pub pretokens: Vec<Vec<u8>>,
}

/// Fixture file holding `vocabulary`'s expected ids.
///
/// A free function over the vocabulary NAME rather than a method on the
/// descriptor. The descriptor is a product type, reached by `exatok --vocab
/// cl100k_base`, and a method on it that names a test fixture would put
/// knowledge of this gate's corpus into the shipping path. The dependency has to
/// run one way: the gate knows about the product, and the product knows nothing
/// about the gate.
#[must_use]
pub fn fixture_name(vocabulary: &str) -> String {
    format!("parity_{vocabulary}.json")
}

/// The parity corpus.
///
/// Mirrors `CORPUS` in `tests/fixtures/generate_parity_fixtures.py` exactly.
/// The tests compare the two texts byte for byte, so the pair cannot drift
/// apart without a failure that names the case.
#[must_use]
#[allow(clippy::too_many_lines)]
pub fn corpus() -> Vec<Case> {
    let case = |name: &'static str, concern: &'static str, text: &str| Case {
        name,
        concern,
        text: text.to_owned(),
    };
    vec![
        case(
            "ascii_prose",
            "plain ASCII words and sentence punctuation, the base case every other case deviates from",
            "The quick brown fox jumps over the lazy dog. Tokenizers must agree on \
             every byte, not almost every byte.",
        ),
        case(
            "indented_source_spaces",
            "space-indented code, where the non-monotonic whitespace merge ranks live",
            "fn main() {\n    let total = 0;\n    if total > 0 {\n        \
             println!(\"total {total}\");\n    }\n}\n",
        ),
        case(
            "indented_source_tabs",
            "tab-indented code, a different whitespace token family than spaces",
            "def main():\n\tif True:\n\t\treturn 1\n\treturn 0\n",
        ),
        case(
            "deep_indent_ladder",
            "indent widths 4 through 24 in one input, the densest source of whitespace merges that lower their own rank",
            // One literal on purpose: a `\` line continuation would strip the
            // leading indent that this case exists to carry.
            "a\n    b\n        c\n            d\n                e\n                    f\n                        g\n",
        ),
        case(
            "whitespace_runs",
            "space runs of length 1 through 8 between words, each a different whitespace token",
            "a b  c   d    e     f      g       h        i",
        ),
        Case {
            name: "long_space_run",
            concern: "a 64-space run, far past any single whitespace token, so it must decompose exactly",
            text: format!("start{}end", " ".repeat(64)),
        },
        case(
            "trailing_whitespace",
            "whitespace at end of input, the only place the pattern alternative \\s++$ applies",
            "text with trailing spaces   ",
        ),
        case(
            "newlines_only",
            "input that is nothing but newlines, where \\s*[\\r\\n] and \\s+(?!\\S) compete",
            "\n\n\n\n\n",
        ),
        case(
            "crlf_mixed",
            "CRLF line endings including a blank line and a bare trailing CR",
            "one\r\ntwo\r\n\r\nthree\r",
        ),
        case(
            "blank_lines_indented",
            "whitespace-only lines mixing spaces and tabs, which the newline alternatives must absorb",
            "a\n\n    \n\tb\n",
        ),
        case(
            "contractions_ascii",
            "every ASCII contraction alternative the split patterns enumerate",
            "I'm sure it's John's, they're here, we'll go, I've seen, don't, can't, isn't, o'clock",
        ),
        case(
            "contractions_uppercase",
            "uppercase contractions, which cl100k folds with (?i:) and gpt2 does not",
            "IT'S HE'LL WE'VE THEY'RE DON'T I'M",
        ),
        case(
            "contraction_long_s",
            "U+017F LATIN SMALL LETTER LONG S after an apostrophe, the only non-ASCII member of any fold class these patterns use",
            "it'\u{17f} and it's",
        ),
        case(
            "digit_runs",
            "digit runs of length 1 through 10, crossing the cl100k three-digit cap",
            "1 12 123 1234 12345 123456 1234567890",
        ),
        Case {
            name: "long_digit_run",
            concern: "a 50-digit run, so the three-digit cap fires sixteen times in one pretoken sequence",
            text: "1234567890".repeat(5),
        },
        case(
            "digits_in_text",
            "digits fused to letters and punctuation, versions, hex, dates, and leading zeros",
            "version 3.14159 built 20240630 at 0x7fff, port 8080, id 000123",
        ),
        case(
            "multibyte_utf8",
            "two- and three-byte UTF-8 across Latin-1 supplement, Greek, Cyrillic, and punctuation",
            "na\u{ef}ve caf\u{e9} r\u{e9}sum\u{e9} \u{3a9}\u{2248}\u{e7}\u{221a} \
             \u{a1}Hola! \u{41f}\u{440}\u{438}\u{432}\u{435}\u{442} \u{43c}\u{438}\u{440} \
             \u{ab}guillemets\u{bb} ellipsis\u{2026}",
        ),
        case(
            "cjk_mixed",
            "CJK and Hangul, where every character is three UTF-8 bytes and no space separates words",
            "\u{65e5}\u{672c}\u{8a9e}\u{306e}\u{30c8}\u{30fc}\u{30af}\u{30f3}\u{5316}\u{306f}\u{96e3}\u{3057}\u{3044}\u{3002}\
             \u{4e2d}\u{6587}\u{5206}\u{8bcd}\u{4e5f}\u{4e00}\u{6837}\u{3002}\
             \u{d55c}\u{ad6d}\u{c5b4}\u{b3c4} \u{b9c8}\u{cc2c}\u{ac00}\u{c9c0}\u{b2e4}.",
        ),
        case(
            "combining_marks",
            "combining marks after base letters, which \\p{M} keeps inside the letter run",
            "e\u{301}a\u{308}o\u{303} \u{915}\u{94d}\u{937} \u{5d0}\u{5b8}",
        ),
        case(
            "rtl_scripts",
            "right-to-left Arabic and Hebrew, whose bytes carry no ASCII structure at all",
            "\u{645}\u{631}\u{62d}\u{628}\u{627} \u{628}\u{627}\u{644}\u{639}\u{627}\u{644}\u{645} \
             \u{5e9}\u{5dc}\u{5d5}\u{5dd} \u{5e2}\u{5d5}\u{5dc}\u{5dd}",
        ),
        case(
            "emoji_zwj",
            "a four-person ZWJ family, a ZWJ flag with a variation selector, a skin-tone modifier, and a regional-indicator pair",
            "\u{1f469}\u{200d}\u{1f469}\u{200d}\u{1f467}\u{200d}\u{1f466} family \
             \u{1f3f3}\u{fe0f}\u{200d}\u{1f308} flag \u{1f44d}\u{1f3fd} thumbs \
             \u{1f600} plain \u{1f1fa}\u{1f1f8} pair",
        ),
        case(
            "emoji_dense",
            "ten adjacent four-byte emoji with no separator, so every merge candidate is a four-byte boundary",
            "\u{1f600}\u{1f603}\u{1f604}\u{1f601}\u{1f606}\
             \u{1f605}\u{1f923}\u{1f602}\u{1f642}\u{1f643}",
        ),
        case(
            "zero_width_and_bidi",
            "zero-width space, zero-width joiner, BOM, and a bidi override, none of which are White_Space",
            "a\u{200b}b\u{200d}c\u{feff}d\u{202e}e",
        ),
        case(
            "unicode_whitespace",
            "non-ASCII White_Space characters, which \\s matches but [\\r\\n] does not",
            "a\u{a0}b\u{2009}c\u{3000}d\u{2028}e\u{85}f",
        ),
        case(
            "control_chars",
            "NUL, BEL, ESC, and DEL embedded in text, the bytes a naive reader would truncate on",
            "a\u{0}b\u{7}c\u{1b}[0md\u{7f}e",
        ),
        case(
            "endoftext_literal",
            "special-token spellings appearing as ordinary text, which encode_ordinary must not promote to a special id",
            "before <|endoftext|> after <|fim_prefix|> <|im_start|>role<|im_end|>",
        ),
        case(
            "empty",
            "empty input, which must produce zero ids rather than one empty pretoken",
            "",
        ),
        case(
            "single_space",
            "one space, the shortest input that is entirely whitespace",
            " ",
        ),
        Case {
            name: "long_letter_run",
            concern: "a 500-character single-class letter run, near the longest pretoken observed in real corpora",
            text: "a".repeat(500),
        },
        Case {
            name: "long_alternating_run",
            concern: "500 characters alternating two letters, which defeats any repeated-token shortcut",
            text: "ab".repeat(250),
        },
        Case {
            name: "long_digit_wall",
            concern: "500 digits with no separator, so the three-digit cap produces 167 consecutive pretokens under cl100k",
            text: "9".repeat(500),
        },
        case(
            "punctuation_dense",
            "a long punctuation run, the alternative that greedily absorbs every non-letter non-digit non-space byte",
            "!!!???...,,,;;;:::(){}[]<>/\\|@#$%^&*-_=+~`\"'",
        ),
        case(
            "mixed_case_identifiers",
            "camel, snake, and screaming-snake identifiers, whose case boundaries split differently per pattern",
            "CamelCaseIdentifier snake_case_name SCREAMING_SNAKE xmlHTTPRequest getURLFromID",
        ),
        case(
            "json_blob",
            "JSON punctuation adjacency, where quotes, colons, and brackets crowd every letter run",
            "{\"key\": [1, 2, 3], \"nested\": {\"a\": null, \"b\": true}}",
        ),
        case(
            "markdown_table",
            "pipe-and-dash table rows, a punctuation-heavy shape with newline-terminated runs",
            "| a | b |\n|---|---|\n| 1 | 2 |\n",
        ),
        case(
            "url_and_path",
            "URLs and filesystem paths, including a Windows path whose separator is a backslash",
            "https://example.com/a/b?c=d&e=f#g /usr/local/bin/python3 C:\\Windows\\System32",
        ),
        Case {
            name: "repeated_word",
            concern: "the same word fifty times, so a per-pretoken cache bug would show as a wrong id late in the stream",
            text: "token ".repeat(50),
        },
        case(
            "scalar_extremes",
            "the highest scalar value, the replacement character, and a noncharacter, all four-byte or three-byte UTF-8",
            "edge \u{10ffff} \u{fffd} \u{fffe} done",
        ),
        case(
            "astral_letters",
            "mathematical alphanumeric and enclosed astral letters, which are \\p{L} and \\p{N} outside the BMP",
            "\u{1d573}\u{1d58a}\u{1d591}\u{1d591}\u{1d594} \
             \u{1d7d8}\u{1d7d9}\u{1d7da} \u{1f130}\u{1f131}",
        ),
        case(
            "merge_tie_leftmost",
            "odd-length runs of one repeated character, where the same pair ties at two overlapping positions and only the LEFTMOST occurrence may merge",
            "aaaaa nnn ttt ^^^^^ zzz",
        ),
        case(
            "all_special_spellings",
            "every special-token spelling of all four gated vocabularies, spaced and then adjacent, none of which encode_ordinary may promote to a special id",
            "<|endoftext|> <|fim_prefix|> <|fim_middle|> <|fim_suffix|> <|endofprompt|> \
             <|endoftext|><|endofprompt|>",
        ),
        case(
            "nul_bytes",
            "a leading NUL, an interior NUL run, a NUL fused between letters, and a trailing NUL, the byte a C-string reader stops at",
            "\u{0}lead \u{0}\u{0}\u{0} mid\u{0}end trail\u{0}",
        ),
    ]
}

/// The invalid-UTF-8 corpus, with the pretoken split each input must produce.
///
/// Every malformed byte is one unit of no Unicode class, so it falls in the
/// ` ?[^\s\p{L}\p{N}]++` alternative. Each input surrounds its malformed run
/// with spaces, which makes the boundaries identical under `gpt2`,
/// `cl100k_base`, and `o200k_base`: the leading space joins the malformed run,
/// and the following space starts the next letter run.
#[must_use]
pub fn byte_corpus() -> Vec<ByteCase> {
    let case = |name: &'static str, concern: &'static str, pretokens: &[&[u8]]| ByteCase {
        name,
        concern,
        bytes: pretokens.concat(),
        pretokens: pretokens.iter().map(|piece| piece.to_vec()).collect(),
    };
    let mut cases = vec![
        case(
            "bytes_lone_continuation",
            "a continuation byte with no lead byte, the commonest way a truncated buffer arrives",
            &[b"ab", b" \x80", b" cd"],
        ),
        case(
            "bytes_truncated_two_byte",
            "a two-byte lead with its continuation missing, which a length-driven decoder would read past",
            &[b"caf", b" \xc3", b" end"],
        ),
        case(
            "bytes_invalid_surrogate",
            "the CESU-8 spelling of a surrogate, three bytes that each fail independently",
            &[b"x", b" \xed\xa0\x80", b" y"],
        ),
        case(
            "bytes_surrogate_pair",
            "a full CESU-8 surrogate pair, six bytes that a decoder may be tempted to fold back into one astral scalar",
            &[b"x", b" \xed\xa0\xbd\xed\xb8\x80", b" y"],
        ),
        case(
            "bytes_never_valid_lead",
            "0xFF and 0xFE, byte values that are not legal anywhere in UTF-8",
            &[b"x", b" \xff\xfe", b" y"],
        ),
        case(
            "bytes_overlong",
            "an overlong two-byte encoding of '/', the classic path-traversal smuggling shape",
            &[b"x", b" \xc0\xaf", b" y"],
        ),
        case(
            "bytes_nul_and_continuation",
            "NUL bytes flanking an unpaired continuation byte, so a resync that skips to the next lead byte would swallow the NULs too",
            &[b"x", b" \x00\x80\x00", b" y"],
        ),
    ];
    // A malformed run long enough that the pretoken cannot be a single token,
    // built rather than written out because a 65-byte escaped literal is
    // unreadable and easy to mistype. This is the byte-side counterpart of the
    // 500-character text runs: one long pretoken whose every merge candidate is
    // a byte pair no vocabulary was trained on.
    let mut long_run = vec![b' '];
    for _ in 0..32 {
        long_run.extend_from_slice(b"\xff\xfe");
    }
    let pretokens = vec![b"x".to_vec(), long_run, b" y".to_vec()];
    cases.push(ByteCase {
        name: "bytes_long_malformed_run",
        concern: "a 65-byte run of never-valid lead bytes in one pretoken, far past any token in any vocabulary",
        bytes: pretokens.concat(),
        pretokens,
    });
    // The tightest input that overruns the device loop's 255-token cap in ONE
    // pretoken. Never-merging bytes cost one token per byte, so 261 of them
    // reach 261 tokens, while a gpt2-pattern letter run needs 477 bytes and a
    // cl100k one 6553. Malformed input is 25x tighter than prose, so it is the
    // shape a dispatch bound has to be written against, and the host gate has
    // to record the reference ids for it or the device side has nothing to be
    // exact against at its own boundary. Measured by DifferentialFuzz: 256
    // bytes suffice under gpt2 and 259 under cl100k/o200k, so 261 clears all
    // four.
    let mut over_cap = vec![b' '];
    for _ in 0..130 {
        over_cap.extend_from_slice(b"\xff\xfe");
    }
    let pretokens = vec![b"x".to_vec(), over_cap, b" y".to_vec()];
    cases.push(ByteCase {
        name: "bytes_over_cap_malformed_run",
        concern: "a 261-byte single pretoken of never-valid lead bytes, past the device loop's 255-token cap, which prose needs 477 to 6553 bytes to reach",
        bytes: pretokens.concat(),
        pretokens,
    });
    cases
}

#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
mod tests {
    use super::{
        ByteCase, Case, Divergence, IdMismatch, Segment, byte_corpus, corpus, decode_hex,
        encode_bytes, encode_segments, first_divergence, first_merge, first_mismatch,
        fixture_name, segment_ids, with_rank_replaced, without_pair,
    };
    use crate::pretokenize::SplitPattern;
    use crate::reference::{HostMergeTable, MergeTable};
    use crate::vocab::{NAMED_VOCABULARIES, Source, Vocabulary};
    use crate::{PairKey, Rank, TokenId, byte_token_ids};

    /// A tiny vocabulary with the shape the real files have: the bytes `a`, `b`,
    /// `c` plus two multi-byte tokens, so pair derivation has something to do.
    const TINY: &str = "\
YQ== 0
Yg== 1
Yw== 2
YWI= 3
YWJj 4
";

    fn tiny() -> Vocabulary {
        Vocabulary::load_tiktoken(Source::new("tiny.tiktoken", TINY)).unwrap()
    }

    /// Standard padded base64, only what a one-byte token needs.
    ///
    /// Written here rather than reached for in `vocab`: that module's decoder is
    /// private and inverting it in the test would test the inverse, not the
    /// loader.
    fn base64_line(bytes: &[u8]) -> String {
        const ALPHABET: &[u8; 64] =
            b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
        let mut out = String::new();
        for chunk in bytes.chunks(3) {
            let mut group = [0u8; 3];
            group[..chunk.len()].copy_from_slice(chunk);
            let packed = (u32::from(group[0]) << 16) | (u32::from(group[1]) << 8) | u32::from(group[2]);
            for slot in 0..4 {
                if slot <= chunk.len() {
                    let index = (packed >> (18 - 6 * slot)) & 0x3f;
                    out.push(char::from(ALPHABET[index as usize]));
                } else {
                    out.push('=');
                }
            }
        }
        out
    }

    /// A byte with no single-byte token must be reported, not defaulted.
    ///
    /// Locks out a byte map built with `unwrap_or(TokenId(0))` or a `[TokenId;
    /// 256]` left at its initializer. Both silently encode the wrong string:
    /// every unmapped byte becomes whatever id sits at index zero, so the output
    /// is a valid id stream for a different input and the parity comparison
    /// blames the merge loop.
    #[test]
    fn byte_token_ids_rejects_a_vocabulary_missing_a_byte() {
        let error = byte_token_ids("tiny.tiktoken", &tiny()).unwrap_err();
        let text = error.to_string();
        assert!(
            text.contains("byte 0x00"),
            "the first missing byte must be named, got {text}"
        );
        assert!(
            text.contains("no single-byte token"),
            "the detail must say what is missing, got {text}"
        );
    }

    /// Every byte 0..=255 maps to its own distinct id on a complete vocabulary.
    ///
    /// Locks out an off-by-one in the index (`ids[byte as usize - 1]`) and a
    /// loop bound of `0..u8::MAX`, which leaves byte 0xFF at id zero. Both keep
    /// 255 of 256 bytes correct, so only a test that checks all 256 catches it.
    #[test]
    fn byte_token_ids_covers_every_byte_value_distinctly() {
        let mut text = String::new();
        for byte in 0..=u8::MAX {
            text.push_str(&format!("{} {byte}\n", base64_line(&[byte])));
        }
        let vocabulary = Vocabulary::load_tiktoken(Source::new("bytes.tiktoken", &text)).unwrap();
        let ids = byte_token_ids("bytes.tiktoken", &vocabulary).unwrap();
        for byte in 0..=u8::MAX {
            assert_eq!(
                ids[byte as usize],
                TokenId(u32::from(byte)),
                "byte 0x{byte:02x} must map to its own rank"
            );
        }
    }

    /// A shorter stream mismatches at the position where it stopped.
    ///
    /// Locks out comparing only `min(len)` elements, which reports a match when
    /// exatok drops trailing ids: dropping the last pretoken of a document is
    /// exactly the failure a prefix-only comparison hides.
    #[test]
    fn first_mismatch_reports_a_truncated_stream() {
        let expected = [TokenId(7), TokenId(8), TokenId(9)];
        let actual = [TokenId(7), TokenId(8)];
        assert_eq!(
            first_mismatch(&expected, &actual),
            Some(IdMismatch {
                index: 2,
                expected: Some(TokenId(9)),
                actual: None,
            })
        );
        assert_eq!(
            first_mismatch(&actual, &expected),
            Some(IdMismatch {
                index: 2,
                expected: None,
                actual: Some(TokenId(9)),
            })
        );
    }

    /// Equal streams mismatch nowhere, and a differing element reports its index.
    ///
    /// Locks out a comparison that always reports index zero, which would make
    /// every divergence report useless for locating the offending pretoken.
    #[test]
    fn first_mismatch_locates_the_differing_index() {
        let expected = [TokenId(1), TokenId(2), TokenId(3)];
        assert_eq!(first_mismatch(&expected, &expected), None);
        assert_eq!(first_mismatch(&[], &[]), None);
        let actual = [TokenId(1), TokenId(2), TokenId(4)];
        assert_eq!(
            first_mismatch(&expected, &actual),
            Some(IdMismatch {
                index: 2,
                expected: Some(TokenId(3)),
                actual: Some(TokenId(4)),
            })
        );
    }

    /// Replacing a rank changes exactly one entry and keeps every id.
    ///
    /// Locks out a corruption helper that rebuilds the table from the wrong
    /// side of the pair or overwrites the merged id as well. Either would make
    /// the corruption test pass for the wrong reason: the gate would be
    /// detecting a broken table shape, not a wrong rank.
    #[test]
    fn with_rank_replaced_changes_one_rank_and_nothing_else() {
        let vocabulary = tiny();
        let table = vocabulary.merge_table();
        let pair = PairKey::new(TokenId(0), TokenId(1));
        let original = table.lookup(pair).unwrap();
        assert_eq!(original.rank, Rank(3), "'ab' has rank 3 in the tiny file");

        let corrupted = with_rank_replaced("tiny", table, pair, Rank(0)).unwrap();
        assert_eq!(corrupted.len(), table.len(), "no entry may be added or lost");
        let changed = corrupted.lookup(pair).unwrap();
        assert_eq!(changed.rank, Rank(0), "the target rank must be replaced");
        assert_eq!(changed.id, original.id, "the merged id must be untouched");
        for (key, entry) in table.iter() {
            if key == pair {
                continue;
            }
            assert_eq!(
                corrupted.lookup(key),
                Some(entry),
                "pair ({}, {}) must be unchanged",
                key.left().0,
                key.right().0
            );
        }
    }

    /// Corrupting an absent pair is an error, not a silent no-op.
    ///
    /// Locks out the version of the corruption test that "passes" because it
    /// mutated nothing and then asserted the untouched table still matches. The
    /// gate would report itself provably fallible while proving nothing.
    #[test]
    fn with_rank_replaced_rejects_a_pair_the_table_lacks() {
        let vocabulary = tiny();
        let absent = PairKey::new(TokenId(2), TokenId(2));
        let error =
            with_rank_replaced("tiny", vocabulary.merge_table(), absent, Rank(1)).unwrap_err();
        let text = error.to_string();
        assert!(
            text.contains("pair (2, 2)"),
            "the absent pair must be named, got {text}"
        );
    }

    /// The ABSENT sentinel is rejected as a replacement rank.
    ///
    /// `HostMergeTable::insert` already refuses it; this pins that the helper
    /// propagates that refusal instead of building a table whose entry is both
    /// present and invisible to a minimum reduction.
    #[test]
    fn with_rank_replaced_rejects_the_absent_sentinel() {
        let vocabulary = tiny();
        let pair = PairKey::new(TokenId(0), TokenId(1));
        let error =
            with_rank_replaced("tiny", vocabulary.merge_table(), pair, Rank::ABSENT).unwrap_err();
        assert!(
            error.to_string().contains("ABSENT sentinel"),
            "the sentinel must be named, got {error}"
        );
    }

    /// Removing a pair drops exactly that entry and changes the encoding.
    ///
    /// Locks out a removal that filters on the wrong side of the key, which
    /// leaves the target present and every other entry gone. The encoding check
    /// is the part that matters: with `a`+`b` removed, `abc` can no longer form,
    /// which is exactly what a canonical-only derivation does on a real file.
    #[test]
    fn without_pair_removes_one_entry_and_changes_the_result() {
        let vocabulary = tiny();
        let table = vocabulary.merge_table();
        let pair = PairKey::new(TokenId(0), TokenId(1));
        let reduced = without_pair("tiny", table, pair).unwrap();

        assert_eq!(reduced.len(), table.len() - 1, "exactly one entry goes");
        assert_eq!(reduced.lookup(pair), None, "the target must be gone");
        assert_eq!(
            reduced.lookup(PairKey::new(TokenId(3), TokenId(2))),
            table.lookup(PairKey::new(TokenId(3), TokenId(2))),
            "'ab' + 'c' must survive the removal"
        );

        let raw = [TokenId(0), TokenId(1), TokenId(2)];
        assert_eq!(
            crate::reference::encode_pretoken(&raw, table),
            vec![TokenId(4)],
            "the intact table merges a b c into abc"
        );
        assert_eq!(
            crate::reference::encode_pretoken(&raw, &reduced),
            vec![TokenId(0), TokenId(1), TokenId(2)],
            "without 'a' + 'b' nothing can merge at all"
        );
    }

    /// Removing an absent pair is an error, not a silent copy.
    #[test]
    fn without_pair_rejects_a_pair_the_table_lacks() {
        let vocabulary = tiny();
        let error =
            without_pair("tiny", vocabulary.merge_table(), PairKey::new(TokenId(2), TokenId(2)))
                .unwrap_err();
        assert!(
            error.to_string().contains("pair (2, 2)"),
            "the absent pair must be named, got {error}"
        );
    }

    /// `first_merge` reports the leftmost lowest-rank pair, and nothing when none.
    ///
    /// Locks out a helper that returns the first mergeable pair in scan order
    /// rather than the lowest rank. Targeting the wrong pair would make a
    /// corruption experiment change an entry the encoding never consults, so the
    /// experiment would report "no divergence" and be read as confluence.
    ///
    /// The `[ab, c, a, b]` case is the one that discriminates. Every other state
    /// here offers at most ONE mergeable pair, so the minimum and the maximum
    /// coincide and the comparison direction cannot be observed: inverting the
    /// `<` to a `>` left this test green until this case was added. Here the
    /// lower-ranked candidate sits to the RIGHT of a higher-ranked one, so
    /// picking the highest rank, or simply the first pair found, both fail.
    #[test]
    fn first_merge_picks_the_leftmost_lowest_rank() {
        let vocabulary = tiny();
        let table = vocabulary.merge_table();
        // Derived from TINY: (a,b) -> "ab" rank 3, (ab,c) -> "abc" rank 4, and
        // (b,c) is absent because "bc" is not a token.
        assert_eq!(
            first_merge(&[TokenId(0), TokenId(1), TokenId(2)], table),
            Some(PairKey::new(TokenId(0), TokenId(1)))
        );
        assert_eq!(
            first_merge(&[TokenId(3), TokenId(2)], table),
            Some(PairKey::new(TokenId(3), TokenId(2)))
        );
        assert_eq!(
            first_merge(
                &[TokenId(3), TokenId(2), TokenId(0), TokenId(1)],
                table
            ),
            Some(PairKey::new(TokenId(0), TokenId(1))),
            "rank 3 at index 2 must beat rank 4 at index 0"
        );
        assert_eq!(first_merge(&[TokenId(1), TokenId(2)], table), None);
        assert_eq!(first_merge(&[TokenId(0)], table), None);
        assert_eq!(first_merge(&[], table), None);
    }

    /// Hex decoding is exact over every byte value and rejects malformed input.
    ///
    /// Locks out a decoder that swaps nibbles or accepts uppercase silently.
    /// The byte cases exist to pin behaviour on specific malformed bytes, so a
    /// nibble swap would test a different input than the fixture recorded.
    #[test]
    fn decode_hex_round_trips_every_byte_and_names_bad_input() {
        let all: String = (0..=u8::MAX).map(|byte| format!("{byte:02x}")).collect();
        let decoded = decode_hex("fixture", &all).unwrap();
        assert_eq!(decoded, (0..=u8::MAX).collect::<Vec<u8>>());
        assert_eq!(decode_hex("fixture", "").unwrap(), Vec::<u8>::new());
        assert_eq!(decode_hex("fixture", "20c0af").unwrap(), b" \xc0\xaf");

        let odd = decode_hex("fixture", "abc").unwrap_err().to_string();
        assert!(odd.contains("length 3"), "got {odd}");
        let upper = decode_hex("fixture", "0A").unwrap_err().to_string();
        assert!(upper.contains("character 1"), "got {upper}");
        let bad = decode_hex("fixture", "0g").unwrap_err().to_string();
        assert!(bad.contains("'g'"), "got {bad}");
    }

    /// Corpus case names are unique and every concern is a real sentence.
    ///
    /// A duplicate name makes the fixture cross-check ambiguous: two cases
    /// would map to one fixture entry and the second would never be compared.
    #[test]
    fn corpus_names_are_unique_and_documented() {
        let cases: Vec<Case> = corpus();
        assert_eq!(cases.len(), 42, "the corpus size is pinned to the fixture");
        let mut names: Vec<&str> = cases.iter().map(|case| case.name).collect();
        names.sort_unstable();
        let count = names.len();
        names.dedup();
        assert_eq!(names.len(), count, "case names must be unique");
        for case in &cases {
            assert!(
                case.concern.len() > 30,
                "{} needs a concern that names what it catches",
                case.name
            );
        }
    }

    /// The pinned corpus shapes are exactly the sizes their names claim.
    ///
    /// Locks out a corpus edited to a shorter run: `"a".repeat(50)` still
    /// exercises long-pretoken merging shallowly, so it would keep passing
    /// while quietly abandoning the 500-byte stress the GPU loop is sized for.
    #[test]
    fn corpus_pins_the_long_case_lengths() {
        let cases = corpus();
        let find = |name: &str| -> &Case {
            cases
                .iter()
                .find(|case| case.name == name)
                .unwrap_or_else(|| panic!("{name} must be in the corpus"))
        };
        assert_eq!(find("long_letter_run").text.len(), 500);
        assert_eq!(find("long_alternating_run").text.len(), 500);
        assert_eq!(find("long_digit_wall").text.len(), 500);
        assert_eq!(find("long_space_run").text.len(), 72);
        assert_eq!(find("long_digit_run").text.len(), 50);
        assert_eq!(find("repeated_word").text.len(), 300);
        assert_eq!(find("empty").text.len(), 0);
        assert_eq!(find("single_space").text, " ");
        assert_eq!(find("newlines_only").text, "\n\n\n\n\n");
    }

    /// Byte-case pretokens reassemble their input and are genuinely malformed.
    ///
    /// Locks out a byte case whose bytes are accidentally valid UTF-8, which
    /// would silently stop testing the malformed-byte path while still passing,
    /// and a declared split that does not cover the input.
    #[test]
    fn byte_corpus_is_malformed_and_reassembles() {
        let cases: Vec<ByteCase> = byte_corpus();
        assert_eq!(cases.len(), 9, "the byte corpus size is pinned to the fixture");
        for case in &cases {
            assert_eq!(
                case.pretokens.concat(),
                case.bytes,
                "{} pretokens must reassemble the input",
                case.name
            );
            assert!(
                std::str::from_utf8(&case.bytes).is_err(),
                "{} must be invalid UTF-8 or it belongs in the ordinary corpus",
                case.name
            );
        }
        assert_eq!(cases[0].bytes, b"ab \x80 cd");
        assert_eq!(cases[5].bytes, b"x \xc0\xaf y");
        assert_eq!(cases[7].bytes.len(), 68, "the long malformed run is 68 bytes");
        assert_eq!(
            cases[8].pretokens[1].len(),
            261,
            "the over-cap pretoken must stay past the device loop's 255-token cap"
        );
    }

    /// Every named vocabulary maps to a distinct fixture file.
    ///
    /// Locks out a copy-pasted descriptor: two vocabularies resolving to one
    /// fixture would compare one of them twice and never load the other, and the
    /// gate would report full coverage while covering three.
    ///
    /// The descriptors' own pinned counts and their artifact paths are asserted in
    /// `crate::vocab`, where they now live. This file keeps only the fixture
    /// mapping, which is the gate's concern.
    #[test]
    fn every_named_vocabulary_maps_to_a_distinct_fixture() {
        let mut fixtures: Vec<String> = NAMED_VOCABULARIES
            .iter()
            .map(|vocabulary| fixture_name(vocabulary.name))
            .collect();
        fixtures.sort();
        assert_eq!(
            fixtures,
            vec![
                "parity_cl100k_base.json",
                "parity_o200k_base.json",
                "parity_p50k_base.json",
                "parity_r50k_base.json",
            ]
        );
    }

    /// A table built from `iter()` round-trips, so corruption is the only change.
    ///
    /// Locks out a rebuild that reorders or loses entries: `with_rank_replaced`
    /// is only a valid experiment if an unmodified rebuild is the identity.
    #[test]
    fn rebuilding_from_iter_is_the_identity() {
        let vocabulary = tiny();
        let table = vocabulary.merge_table();
        let rebuilt = HostMergeTable::from_entries(
            "tiny",
            table.iter().map(|(key, entry)| (key, entry.id, entry.rank)),
        )
        .unwrap();
        assert_eq!(&rebuilt, table);
    }

    /// A vocabulary holding every single byte plus `ab`, ` c`, and ` cd`.
    ///
    /// Every byte is present so the byte map is complete, and the multi-byte
    /// tokens are chosen so both pretokens of `"ab cd"` actually merge: `ab`
    /// splits into `a` plus `b`, and ` cd` reaches its id through ` c` plus `d`.
    /// A vocabulary whose extra tokens had no derivable split would make every
    /// segment a run of single bytes and hide an offset bug.
    fn segment_vocabulary() -> Vocabulary {
        let mut text = String::new();
        for byte in 0..=u8::MAX {
            text.push_str(&format!("{} {byte}\n", base64_line(&[byte])));
        }
        text.push_str(&format!("{} 256\n", base64_line(b"ab")));
        text.push_str(&format!("{} 257\n", base64_line(b" c")));
        text.push_str(&format!("{} 258\n", base64_line(b" cd")));
        Vocabulary::load_tiktoken(Source::new("segments.tiktoken", &text)).unwrap()
    }

    /// Segments carry each pretoken's byte offset, bytes, and merged ids.
    ///
    /// Locks out the two ways a located report goes quietly wrong: an offset
    /// taken from the pretoken INDEX rather than the byte span, which is right
    /// only while every pretoken is one byte long, and ids merged per input
    /// instead of per pretoken, which would fuse across a boundary. Also pins
    /// that the flattened segments are exactly what `encode_bytes` returns, so
    /// the located report can never describe a stream the gate did not compare.
    #[test]
    fn encode_segments_records_offsets_bytes_and_ids() {
        let vocabulary = segment_vocabulary();
        let bytes = byte_token_ids("segments.tiktoken", &vocabulary).unwrap();
        let table = vocabulary.merge_table();
        let segments = encode_segments(SplitPattern::Gpt2, b"ab cd", &bytes, table);
        assert_eq!(
            segments,
            vec![
                Segment {
                    offset: 0,
                    bytes: b"ab".to_vec(),
                    ids: vec![TokenId(256)],
                },
                Segment {
                    offset: 2,
                    bytes: b" cd".to_vec(),
                    ids: vec![TokenId(258)],
                },
            ]
        );
        assert_eq!(
            segment_ids(&segments),
            encode_bytes(SplitPattern::Gpt2, b"ab cd", &bytes, table),
            "the located path and the flat path must agree id for id"
        );
    }

    /// A divergence names the pretoken, its byte offset, and both ids.
    ///
    /// This is the whole point of the located report: an id index alone says
    /// "id 1 of 2 differs", which for a 3000-byte corpus means bisecting by
    /// hand. Locks out attribution that always blames the first pretoken, and
    /// an offset that reports the id index instead of a byte position.
    #[test]
    fn first_divergence_locates_the_pretoken_and_byte_offset() {
        let vocabulary = segment_vocabulary();
        let bytes = byte_token_ids("segments.tiktoken", &vocabulary).unwrap();
        let segments = encode_segments(SplitPattern::Gpt2, b"ab cd", &bytes, vocabulary.merge_table());
        let planted = [TokenId(256), TokenId(99)];
        assert_eq!(
            first_divergence(&planted, &segments),
            Some(Divergence {
                index: 1,
                expected: Some(TokenId(99)),
                actual: Some(TokenId(258)),
                pretoken_index: 1,
                byte_offset: 2,
                pretoken: b" cd".to_vec(),
                index_in_pretoken: 0,
            })
        );
        assert_eq!(
            first_divergence(&[TokenId(256), TokenId(258)], &segments),
            None,
            "equal streams must not report a divergence"
        );
    }

    /// A stream that ends early is reported at the last pretoken produced.
    ///
    /// Locks out a locator that panics or reports offset zero when the index
    /// runs past every segment, which is exactly what happens when exatok
    /// drops a trailing pretoken: the report has to survive the case it exists
    /// to explain.
    #[test]
    fn first_divergence_reports_a_stream_that_ended_early() {
        let vocabulary = segment_vocabulary();
        let bytes = byte_token_ids("segments.tiktoken", &vocabulary).unwrap();
        let segments = encode_segments(SplitPattern::Gpt2, b"ab cd", &bytes, vocabulary.merge_table());
        let longer = [TokenId(256), TokenId(258), TokenId(7)];
        assert_eq!(
            first_divergence(&longer, &segments),
            Some(Divergence {
                index: 2,
                expected: Some(TokenId(7)),
                actual: None,
                pretoken_index: 1,
                byte_offset: 2,
                pretoken: b" cd".to_vec(),
                index_in_pretoken: 1,
            })
        );
        assert_eq!(
            first_divergence(&[TokenId(9)], &[]),
            Some(Divergence {
                index: 0,
                expected: Some(TokenId(9)),
                actual: None,
                pretoken_index: 0,
                byte_offset: 0,
                pretoken: Vec::new(),
                index_in_pretoken: 0,
            }),
            "empty input still has to report the reference's first id"
        );
    }

    /// The rendered report states offset, pretoken, and both ids in full.
    ///
    /// The struct is only useful if the panic message carries it. Locks out a
    /// `Display` that prints the id index alone, and one that renders a
    /// malformed pretoken through a lossy UTF-8 conversion: the byte cases are
    /// deliberately invalid, and `\u{fffd}` in the report would hide the exact
    /// byte that diverged.
    #[test]
    fn divergence_display_states_offset_pretoken_and_both_ids() {
        let report = Divergence {
            index: 137,
            expected: Some(TokenId(9857)),
            actual: Some(TokenId(1234)),
            pretoken_index: 42,
            byte_offset: 613,
            pretoken: b" \x80\"a".to_vec(),
            index_in_pretoken: 3,
        }
        .to_string();
        assert_eq!(
            report,
            "id 137 differs: reference 9857, exatok 1234; byte offset 613, pretoken 42 \
             \" \\x80\\\"a\", id 3 of that pretoken"
        );
        let ended = Divergence {
            index: 2,
            expected: Some(TokenId(7)),
            actual: None,
            pretoken_index: 1,
            byte_offset: 2,
            pretoken: b" cd".to_vec(),
            index_in_pretoken: 1,
        }
        .to_string();
        assert!(
            ended.contains("exatok <stream ended>"),
            "a missing id must read as an ended stream, got {ended}"
        );
    }

    /// Every SHIPPING special spelling is carried by the corpus.
    ///
    /// The special table lives in [`crate::specials`], which is what the CLI
    /// registers, so this reads it there rather than restating the spellings:
    /// a second list beside it would be the bug it is meant to catch. A
    /// reserved id is only proven unreachable if the spelling that would
    /// produce it is actually in the corpus, so a vocabulary gaining a special
    /// while the corpus case keeps the old list must fail here. Without this
    /// the new id would never be shown to stay out of ordinary text.
    #[test]
    fn every_shipping_special_spelling_is_in_the_corpus() {
        let cases = corpus();
        let carrier = cases
            .iter()
            .find(|case| case.name == "all_special_spellings")
            .expect("the corpus must carry the special spellings case");
        let mut spellings = 0usize;
        for vocabulary in NAMED_VOCABULARIES {
            let specials = crate::specials::specials_for(vocabulary.name)
                .unwrap_or_else(|| panic!("{} has no specials entry", vocabulary.name));
            assert!(
                !specials.tokens.is_empty(),
                "{} must declare its special tokens",
                vocabulary.name
            );
            for (spelling, reserved) in specials.tokens {
                assert!(
                    carrier.text.contains(spelling),
                    "{} registers {spelling}, which {} does not carry",
                    vocabulary.name,
                    carrier.name
                );
                assert!(
                    *reserved > 0,
                    "{} reserves id 0 for {spelling}, which is a single-byte token",
                    vocabulary.name
                );
                spellings += 1;
            }
        }
        assert_eq!(
            spellings, 9,
            "the four vocabularies register 9 spellings in total: 5, 1, 1, 2"
        );
    }

    /// The tie case is built from odd-length runs of one repeated character.
    ///
    /// An even-length run is confluent: leftmost and rightmost tie-breaking
    /// reach the same pairing, so an editor who "tidied" `aaaaa` to `aaaa`
    /// would silently delete the only case that can catch a rightward tie
    /// break, and every parity test would stay green.
    #[test]
    fn corpus_tie_case_uses_odd_length_repeated_runs() {
        let cases = corpus();
        let tie = cases
            .iter()
            .find(|case| case.name == "merge_tie_leftmost")
            .expect("the corpus must carry the tie case");
        let runs: Vec<&str> = tie.text.split(' ').collect();
        assert_eq!(runs.len(), 5, "the tie case holds five runs: {runs:?}");
        for run in runs {
            let first = run.as_bytes()[0];
            assert!(
                run.len() % 2 == 1 && run.len() >= 3,
                "{run:?} must be an odd run of at least 3 for the tie to overlap"
            );
            assert!(
                run.bytes().all(|byte| byte == first),
                "{run:?} must repeat one character, or the tying pair is not the same pair"
            );
        }
    }

    /// The NUL case carries NUL in every position a reader could truncate at.
    ///
    /// Locks out a corpus edit that drops the leading or trailing NUL. Interior
    /// NULs alone are the easy case: a length-driven reader handles them, and
    /// only a NUL at offset 0 or at the final byte distinguishes it from a
    /// C-string reader that stops at the first zero.
    #[test]
    fn corpus_nul_case_covers_every_nul_position() {
        let cases = corpus();
        let nul = cases
            .iter()
            .find(|case| case.name == "nul_bytes")
            .expect("the corpus must carry the NUL case");
        let raw = nul.text.as_bytes();
        assert_eq!(raw.first(), Some(&0), "a NUL must lead the input");
        assert_eq!(raw.last(), Some(&0), "a NUL must end the input");
        assert_eq!(
            raw.iter().filter(|&&byte| byte == 0).count(),
            6,
            "the case pins six NULs: leading, a run of three, one fused, one trailing"
        );
        assert!(
            raw.windows(3).any(|window| window == [0, 0, 0]),
            "an interior run of three NULs must survive"
        );
    }
}