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
//! Special-token registration for named vocabularies. OWNER: Main.
//!
//! A `.tiktoken` rank file contains no special tokens. They are assigned by the
//! reference tokenizer and must be registered separately, so a freshly loaded
//! vocabulary has none until something adds them.
//!
//! This lives in the library rather than in the binary on purpose. When the
//! table was in `src/main.rs` nothing under `tests/` could reach it, so the ids
//! below were verified only by running the CLI by hand. A wrong id would have
//! been caught by nobody. Here the suite guards it.
//!
//! Acceptance: for all four named vocabularies, registering these specials
//! reproduces the reference tokenizer's published `n_vocab` exactly.
//!
//! # Why `n_vocab` is the right check
//!
//! [`Vocabulary::n_vocab`] is the exclusive upper bound over ordinary AND
//! special ids, so it is a function of the id VALUES rather than of how many
//! were registered. A mistyped id therefore changes it, while a count check
//! would not notice.
//!
//! Two structures exist here and only one is obvious. In three of the four
//! vocabularies the specials sit ABOVE the ordinary range, so `n_vocab` is the
//! highest special id plus one. In `p50k_base` the ordinary entries reach 50280
//! while its only special is 50256, so `n_vocab` is 50281 and the specials do
//! not touch it. [`NamedSpecials::special_topped`] records which case each is.
//!
//! Note also that `n_vocab` is not entries plus specials: `cl100k_base` has
//! 100256 entries and 5 specials yet an `n_vocab` of 100277, because 16 ids
//! between the two ranges are reserved and unused. Any check derived from
//! addition would disagree with the published figure.
//!
//! # Three modes, and exatok used to ship only two of them
//!
//! Ordinary encoding can never produce a special id: it merges byte pairs
//! through the merge table and no special token appears there. The literal text
//! `<|endoftext|>` therefore encodes to its own bytes, seven ids on every
//! vocabulary here, which is exactly what the reference tokenizer's
//! `encode_ordinary` returns.
//!
//! [`encode_allowed`] is the second mode. A listed special is recognized BEFORE
//! pretokenization and emitted as its single id, so it can never be split, and
//! anything NOT listed is encoded as its ordinary bytes. Both are pinned per
//! vocabulary, because the silent failure is a special that encodes to its bytes
//! while it was allowed, or to its id while it was not.
//!
//! Be precise about which reference entry point that is, because the obvious
//! reading is wrong. [`encode_allowed`] is the reference tokenizer's
//! `encode(text, allowed_special=..., disallowed_special=())`, NOT its default
//! `encode(text, ...)`. The reference default is `disallowed_special="all"`,
//! meaning every special outside the allow-list, and on encountering one it
//! RAISES rather than encoding anything at all. [`encode_allowed`] is that
//! function with the guard removed, so it cannot express the default, and an
//! earlier version of this doc called it `encode` with an allow-list and misled
//! exactly the reader checking whether tiktoken code ports across.
//!
//! [`encode_checked`] is the third mode and the missing default: it returns
//! [`DisallowedSpecial`] naming the special and its byte offset instead of
//! encoding. Reach for it when unauthorized special text must be REJECTED.
//!
//! Note what the gap was and was not. [`encode_allowed`] encodes an unlisted
//! special as ORDINARY BYTES, so it never becomes a control token and no input
//! is ever silently promoted: that is the safe direction, and [`encode_checked`]
//! is not a patch for an injection defect. What was missing is the ability to
//! REFUSE, which a caller who validates untrusted text needs and could not get.

use crate::vocab::Vocabulary;
use crate::{TokenId, ExatokError};

/// One named vocabulary's special tokens.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct NamedSpecials {
    /// Artifact stem, for example `cl100k_base`.
    pub name: &'static str,
    /// Special token text and id, in the reference tokenizer's order.
    pub tokens: &'static [(&'static str, u32)],
    /// `n_vocab` the reference tokenizer publishes once these are registered.
    ///
    /// Carried here so the expected value lives beside the ids it is derived
    /// from. A test that recomputed it from this table could not detect a wrong
    /// id, because it would make the same mistake twice.
    pub n_vocab: usize,
    /// Whether the highest id in the whole vocabulary is a SPECIAL rather than
    /// an ordinary token.
    ///
    /// True for three of the four, where the specials sit above the ordinary
    /// range and so `n_vocab` is the highest special id plus one. False for
    /// `p50k_base`, whose ordinary range reaches 50280 while its only special
    /// is 50256, so `n_vocab` is set by the ordinary side. Recorded rather than
    /// assumed: the first version of this module claimed the special always
    /// tops the range, and `p50k_base` refuted it.
    pub special_topped: bool,
}

/// `cl100k_base`: GPT-4 era. Its specials skip 100261 through 100275.
pub const CL100K_BASE_SPECIALS: NamedSpecials = NamedSpecials {
    name: "cl100k_base",
    tokens: &[
        ("<|endoftext|>", 100_257),
        ("<|fim_prefix|>", 100_258),
        ("<|fim_middle|>", 100_259),
        ("<|fim_suffix|>", 100_260),
        ("<|endofprompt|>", 100_276),
    ],
    n_vocab: 100_277,
    special_topped: true,
};

/// `r50k_base`: GPT-2 era, one special.
pub const R50K_BASE_SPECIALS: NamedSpecials = NamedSpecials {
    name: "r50k_base",
    tokens: &[("<|endoftext|>", 50_256)],
    n_vocab: 50_257,
    special_topped: true,
};

/// `p50k_base`: the sparse id space, and the one vocabulary whose specials do
/// NOT top the range. Its ordinary entries reach 50280 while its only special
/// is 50256, sitting in a hole below them, so `n_vocab` is 50281 rather than
/// 50257.
pub const P50K_BASE_SPECIALS: NamedSpecials = NamedSpecials {
    name: "p50k_base",
    tokens: &[("<|endoftext|>", 50_256)],
    n_vocab: 50_281,
    special_topped: false,
};

/// `o200k_base`: GPT-4o era, two specials that are not adjacent.
pub const O200K_BASE_SPECIALS: NamedSpecials = NamedSpecials {
    name: "o200k_base",
    tokens: &[("<|endoftext|>", 199_999), ("<|endofprompt|>", 200_018)],
    n_vocab: 200_019,
    special_topped: true,
};

/// Every named vocabulary's specials, in the order [`crate::vocab::NAMED_VOCABULARIES`] lists them.
pub const NAMED_SPECIALS: [NamedSpecials; 4] = [
    CL100K_BASE_SPECIALS,
    R50K_BASE_SPECIALS,
    P50K_BASE_SPECIALS,
    O200K_BASE_SPECIALS,
];

/// The specials for `name`, if it is a named vocabulary.
#[must_use]
pub fn specials_for(name: &str) -> Option<NamedSpecials> {
    NAMED_SPECIALS
        .into_iter()
        .find(|specials| specials.name == name)
}

/// Register `name`'s special tokens on `vocabulary`.
///
/// An unrecognized name is not an error: a vocabulary loaded from an arbitrary
/// path has no published special set, and inventing one would be worse than
/// leaving it empty.
///
/// # Errors
///
/// Propagates [`ExatokError`] from [`Vocabulary::register_special`], which
/// rejects an id above the representable bound and a special whose id disagrees
/// with an existing registration.
pub fn register(vocabulary: &mut Vocabulary, name: &str) -> Result<(), ExatokError> {
    let Some(specials) = specials_for(name) else {
        return Ok(());
    };
    for (text, id) in specials.tokens {
        vocabulary.register_special(text, TokenId(*id))?;
    }
    Ok(())
}

impl NamedSpecials {
    /// These specials as an allow-list for [`encode_allowed`].
    #[must_use]
    pub fn allowed(&self) -> Vec<(&'static str, TokenId)> {
        self.tokens
            .iter()
            .map(|(text, id)| (*text, TokenId(*id)))
            .collect()
    }

    /// Split these specials into `(allowed, disallowed)` for [`encode_checked`],
    /// allowing exactly the texts in `allow`.
    ///
    /// This is the set difference the reference tokenizer computes for its
    /// default `disallowed_special="all"`, which it defines as
    /// `special_tokens_set - allowed_special`. It is provided rather than left to
    /// the caller because the difference is where fail-closed silently becomes
    /// fail-open: a hand-written `disallowed` list that omits one special lets
    /// that special through the guard as ordinary text, and the call still
    /// returns `Ok`, so nothing reports the hole.
    ///
    /// A name in `allow` that this vocabulary does not declare is ignored. It
    /// cannot appear in either output list, because both are built from
    /// [`NamedSpecials::tokens`], so a typo permits nothing.
    #[must_use]
    pub fn partition(
        &self,
        allow: &[&str],
    ) -> (Vec<(&'static str, TokenId)>, Vec<(&'static str, TokenId)>) {
        self.tokens
            .iter()
            .map(|(text, id)| (*text, TokenId(*id)))
            .partition(|(text, _)| allow.contains(text))
    }
}

/// The leftmost `candidates` entry matching at or after `from`, longest first.
///
/// Leftmost-longest rather than list order, so the result cannot depend on how a
/// caller happens to sort the list. This is the ONE statement of the matching
/// rule in this module: [`next_allowed_special`] and [`encode_checked`] both go
/// through it, so the allow-list scan and the disallow-list scan cannot drift
/// apart and start disagreeing about what "contains a special" means.
///
/// Leftmost-longest and the reference tokenizer's leftmost-first-alternative
/// agree on every shipping vocabulary because no declared special is a prefix of
/// another, which `no_declared_special_is_a_prefix_of_another` pins here and
/// `tests/specials_adversarial.rs` pins over the four real artifacts. Where a
/// prefix pair DOES exist the two rules diverge; that divergence is measured and
/// asserted from both sides in `tests/specials_adversarial.rs` rather than left
/// to this comment.
///
/// Returns the matched offset, the matched text, and its id. The text is carried
/// out rather than recomputed by the caller so an error path can name the
/// offending special without restating the match rule.
fn next_special<'t>(
    input: &[u8],
    from: usize,
    candidates: &[(&'t str, TokenId)],
) -> Option<(usize, &'t str, TokenId)> {
    (from..input.len()).find_map(|start| {
        candidates
            .iter()
            .filter(|(text, _)| input[start..].starts_with(text.as_bytes()))
            .max_by_key(|(text, _)| text.len())
            .map(|(text, id)| (start, *text, *id))
    })
}

/// The leftmost allowed special at or after `from`, as `(start, end, id)`.
///
/// A byte-span view of [`next_special`] for [`encode_allowed`], which needs the
/// resume offset rather than the matched text.
fn next_allowed_special(
    input: &[u8],
    from: usize,
    allowed: &[(&str, TokenId)],
) -> Option<(usize, usize, TokenId)> {
    next_special(input, from, allowed)
        .map(|(start, text, id)| (start, start + text.len(), id))
}

/// Encode `input`, emitting one id for each `allowed` special and ordinary ids
/// for everything between.
///
/// This is the reference tokenizer's
/// `encode(text, allowed_special=..., disallowed_special=())`, and NOT its
/// default `encode(text, ...)`: the default refuses unauthorized special text
/// instead of encoding it, and [`encode_checked`] is that mode. A special listed
/// in `allowed` is matched on the raw bytes before pretokenization, so it is
/// never split and never merges with its neighbours: the text around it is
/// encoded as independent spans, exactly as a hard boundary requires. A special
/// NOT listed encodes to its own ordinary bytes, which is why an empty `allowed`
/// list makes this `encode_ordinary`.
///
/// The ordinary spans go through [`crate::tokenizer::encode_bytes`] rather than
/// a second copy of the split-map-merge pipeline, so the ordinary half of this
/// function is the shipping host path and nothing else. It was
/// [`crate::parity::encode_bytes`] until a shipping join existed to point at,
/// which made shipping code depend on the parity harness module.
/// `tests/specials_exactness.rs` pins exact id vectors measured from the
/// reference tokenizer, so the two joins are held to the same ground truth.
#[must_use]
pub fn encode_allowed(
    pattern: crate::pretokenize::SplitPattern,
    input: &[u8],
    bytes: &[TokenId; 256],
    table: &impl crate::reference::MergeTable,
    allowed: &[(&str, TokenId)],
) -> Vec<TokenId> {
    let mut out = Vec::new();
    let mut at = 0;
    while let Some((start, end, id)) = next_allowed_special(input, at, allowed) {
        if start > at {
            out.extend(crate::tokenizer::encode_bytes(
                pattern,
                &input[at..start],
                bytes,
                table,
            ));
        }
        out.push(id);
        at = end;
    }
    if at < input.len() {
        out.extend(crate::tokenizer::encode_bytes(
            pattern,
            &input[at..],
            bytes,
            table,
        ));
    }
    out
}

/// A special token the caller refused, and where it was found.
///
/// Carries the byte offset as well as the text, which is what makes the report
/// actionable rather than merely correct: a caller rejecting a megabyte of
/// untrusted input needs to say WHERE, and searching for the text again would
/// find the first occurrence rather than the one that stopped the encode. They
/// differ whenever a run of specials is only partly disallowed.
///
/// The text is owned so the error outlives the borrowed disallow-list it came
/// from. That allocation is on the refusal path only; [`encode_checked`] returning
/// `Ok` allocates exactly what [`encode_allowed`] does.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DisallowedSpecial {
    /// Text of the special that was found, for example `<|endoftext|>`.
    pub text: String,
    /// Its id, so a diagnostic can name the id that would have been emitted had
    /// the caller allowed it.
    pub id: TokenId,
    /// Byte offset in the input where the text starts.
    pub at: usize,
}

impl std::fmt::Display for DisallowedSpecial {
    fn fmt(&self, out: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            out,
            "input carries disallowed special token {:?} (id {}) at byte offset {}. Fix: move it \
             into `allowed` to encode it as that id, drop it from `disallowed` to encode it as \
             ordinary text, or reject this input",
            self.text, self.id.0, self.at
        )
    }
}

/// Without this, `DisallowedSpecial` cannot cross a `Box<dyn Error>` or an
/// `anyhow::Error` boundary, and every consumer would hand-convert a type this
/// crate already calls an error. Mirrors [`crate::UnknownTokenId`], whose doc
/// records why `Display` alone is not enough.
impl std::error::Error for DisallowedSpecial {}

/// Encode `input`, refusing it if any `disallowed` special appears.
///
/// This is the reference tokenizer's DEFAULT `encode`, whose `disallowed_special`
/// is `"all"`: it searches the raw text for any special outside the allow-list
/// and raises on the first one instead of encoding anything. Use
/// [`NamedSpecials::partition`] to build the two lists, because the set
/// difference is where fail-closed silently becomes fail-open.
///
/// A special in NEITHER list is encoded as its ordinary bytes, exactly as
/// [`encode_allowed`] does. That is the reference tokenizer's third case,
/// `disallowed_special` naming a strict subset, and it is what lets a caller
/// tolerate one spelling while refusing the rest.
///
/// The check runs over the whole input BEFORE any encoding, so a refusal costs no
/// merge work and the returned offset is an offset into `input` rather than into
/// some span of it. `disallowed` is scanned by [`next_special`], the same
/// leftmost-longest rule [`encode_allowed`] matches with, so a special cannot be
/// invisible to the guard yet visible to the encoder.
///
/// # Errors
///
/// [`DisallowedSpecial`] naming the leftmost disallowed special and its byte
/// offset. Nothing is encoded: the refusal is total, because returning partial
/// ids alongside an error invites a caller to use them.
pub fn encode_checked(
    pattern: crate::pretokenize::SplitPattern,
    input: &[u8],
    bytes: &[TokenId; 256],
    table: &impl crate::reference::MergeTable,
    allowed: &[(&str, TokenId)],
    disallowed: &[(&str, TokenId)],
) -> Result<Vec<TokenId>, DisallowedSpecial> {
    if let Some((at, text, id)) = next_special(input, 0, disallowed) {
        return Err(DisallowedSpecial {
            text: text.to_owned(),
            id,
            at,
        });
    }
    Ok(encode_allowed(pattern, input, bytes, table, allowed))
}

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

    /// The table must cover exactly the vocabularies the `vocab` module names.
    ///
    /// If a fifth vocabulary is added to `NAMED_VOCABULARIES` without specials,
    /// the CLI would silently report it as having none. This fails instead.
    #[test]
    fn every_named_vocabulary_has_a_specials_entry() {
        for vocabulary in crate::vocab::NAMED_VOCABULARIES {
            assert!(
                specials_for(vocabulary.name).is_some(),
                "{} has no specials entry",
                vocabulary.name
            );
        }
        assert_eq!(NAMED_SPECIALS.len(), crate::vocab::NAMED_VOCABULARIES.len());
    }

    /// Every special id must sit below the published `n_vocab`, and where the
    /// specials top the range it must sit exactly one below.
    ///
    /// This is the arithmetic that makes a mistyped id detectable without
    /// loading an artifact, because `n_vocab` is an EXCLUSIVE upper bound.
    ///
    /// The first version asserted `highest + 1 == n_vocab` for all four and
    /// FAILED on `p50k_base` at 50257 against 50281. That was the doc being
    /// wrong rather than the data: `p50k_base` is the one vocabulary whose
    /// ordinary entries (to 50280) outrank its only special (50256), so its
    /// `n_vocab` is set by the ordinary side. The exception is now recorded in
    /// `special_topped` and asserted in BOTH directions, so flipping that flag
    /// on any vocabulary fails.
    #[test]
    fn special_ids_sit_below_n_vocab_and_top_it_exactly_where_they_should() {
        for specials in NAMED_SPECIALS {
            let highest = specials
                .tokens
                .iter()
                .map(|(_, id)| *id as usize)
                .max()
                .expect("every entry has at least one special");
            assert!(
                highest < specials.n_vocab,
                "{}: special {highest} is at or above n_vocab {}, so it is unrepresentable",
                specials.name,
                specials.n_vocab
            );
            if specials.special_topped {
                assert_eq!(
                    highest + 1,
                    specials.n_vocab,
                    "{}: specials top the range, so the highest must be n_vocab - 1",
                    specials.name
                );
            } else {
                assert!(
                    highest + 1 < specials.n_vocab,
                    "{}: specials do not top the range, so n_vocab must exceed the highest \
                     special by more than one",
                    specials.name
                );
            }
        }
        assert_eq!(
            NAMED_SPECIALS
                .iter()
                .filter(|specials| !specials.special_topped)
                .map(|specials| specials.name)
                .collect::<Vec<&str>>(),
            vec!["p50k_base"],
            "p50k_base is the only vocabulary whose specials do not top the id range"
        );
    }

    /// No vocabulary may register the same id or the same text twice.
    ///
    /// A duplicated id would make decoding ambiguous, and a duplicated text
    /// would make the second registration silently unreachable.
    #[test]
    fn special_ids_and_texts_are_unique_within_each_vocabulary() {
        for specials in NAMED_SPECIALS {
            let mut ids: Vec<u32> = specials.tokens.iter().map(|(_, id)| *id).collect();
            let count = ids.len();
            ids.sort_unstable();
            ids.dedup();
            assert_eq!(ids.len(), count, "{} has a duplicate id", specials.name);

            let mut texts: Vec<&str> = specials.tokens.iter().map(|(text, _)| *text).collect();
            texts.sort_unstable();
            texts.dedup();
            assert_eq!(texts.len(), count, "{} has a duplicate text", specials.name);
        }
    }

    /// Every special must be delimited, which is what keeps it off the encodable
    /// path: no pretoken of ordinary text produces these byte sequences as a
    /// single vocabulary entry.
    #[test]
    fn every_special_is_delimited() {
        for specials in NAMED_SPECIALS {
            for (text, _) in specials.tokens {
                assert!(
                    text.starts_with("<|") && text.ends_with("|>"),
                    "{}: {text} is not delimited",
                    specials.name
                );
            }
        }
    }

    /// An unknown name registers nothing rather than failing.
    ///
    /// A vocabulary loaded from an arbitrary path has no published special set,
    /// so this path must be a no-op. Pinned because turning it into an error
    /// would break `--vocab-path` entirely.
    #[test]
    fn an_unknown_name_registers_nothing() {
        let mut vocabulary = Vocabulary::default();
        register(&mut vocabulary, "not_a_vocabulary").unwrap();
        assert_eq!(vocabulary.special_len(), 0);
    }

    /// No declared special is a prefix of another, within a vocabulary.
    ///
    /// This is what makes [`encode_allowed`]'s leftmost-LONGEST rule agree with
    /// the reference tokenizer's leftmost-first-alternative rule on real data.
    /// If a future vocabulary ever declares a special that extends another, the
    /// two rules diverge and `encode_allowed` would silently stop matching the
    /// reference on that overlap, so this must fail rather than that happen.
    #[test]
    fn no_declared_special_is_a_prefix_of_another() {
        for specials in NAMED_SPECIALS {
            for (outer, _) in specials.tokens {
                for (inner, _) in specials.tokens {
                    if outer == inner {
                        continue;
                    }
                    assert!(
                        !outer.starts_with(inner),
                        "{}: {inner} is a prefix of {outer}, so leftmost-longest and \
                         leftmost-first disagree",
                        specials.name
                    );
                }
            }
        }
    }

    /// `allowed` carries every declared special across as an exact typed pair.
    ///
    /// Locks out a converter that drops entries, reorders them, or loses the id
    /// in the `u32` to `TokenId` hop. Any of those would make `encode_allowed`
    /// quietly refuse to recognize a special that is genuinely allowed.
    #[test]
    fn allowed_carries_every_declared_special_with_its_id() {
        assert_eq!(
            CL100K_BASE_SPECIALS.allowed(),
            vec![
                ("<|endoftext|>", TokenId(100_257)),
                ("<|fim_prefix|>", TokenId(100_258)),
                ("<|fim_middle|>", TokenId(100_259)),
                ("<|fim_suffix|>", TokenId(100_260)),
                ("<|endofprompt|>", TokenId(100_276)),
            ]
        );
        assert_eq!(
            P50K_BASE_SPECIALS.allowed(),
            vec![("<|endoftext|>", TokenId(50_256))]
        );
        for specials in NAMED_SPECIALS {
            assert_eq!(
                specials.allowed().len(),
                specials.tokens.len(),
                "{}: allow-list must not change length",
                specials.name
            );
        }
    }

    /// `partition` splits the declared specials into two exact, disjoint lists.
    ///
    /// The set difference is the whole safety property of [`encode_checked`], and
    /// getting it wrong is silent in the fail-OPEN direction: a special missing
    /// from `disallowed` passes the guard as ordinary text and the call still
    /// returns `Ok`. Pinned as exact vectors on the five-special vocabulary, in
    /// declaration order, so a `partition` that dropped an entry or leaked one
    /// into both halves fails here rather than at a caller.
    #[test]
    fn partition_splits_the_declared_specials_into_exact_disjoint_lists() {
        let (allowed, disallowed) =
            CL100K_BASE_SPECIALS.partition(&["<|fim_prefix|>", "<|endofprompt|>"]);
        assert_eq!(
            allowed,
            vec![
                ("<|fim_prefix|>", TokenId(100_258)),
                ("<|endofprompt|>", TokenId(100_276)),
            ]
        );
        assert_eq!(
            disallowed,
            vec![
                ("<|endoftext|>", TokenId(100_257)),
                ("<|fim_middle|>", TokenId(100_259)),
                ("<|fim_suffix|>", TokenId(100_260)),
            ],
            "everything not named must land in the disallow-list, in declaration order"
        );
    }

    /// An empty allow-list disallows every special; allowing all disallows none.
    ///
    /// These are the two ends a caller actually reaches for, and both are the
    /// dangerous ones to get backwards. An inverted `partition` would make
    /// `partition(&[])` return every special as ALLOWED, which turns the
    /// fail-closed entry point into an unconditional encode and would pass any
    /// test that only checked list lengths.
    #[test]
    fn partition_at_both_extremes_puts_every_special_on_the_expected_side() {
        for specials in NAMED_SPECIALS {
            let (none_allowed, all_disallowed) = specials.partition(&[]);
            assert_eq!(
                none_allowed,
                vec![],
                "{}: an empty allow-list must allow nothing",
                specials.name
            );
            assert_eq!(
                all_disallowed,
                specials.allowed(),
                "{}: an empty allow-list must disallow every declared special",
                specials.name
            );

            let every: Vec<&str> = specials.tokens.iter().map(|(text, _)| *text).collect();
            let (all_allowed, none_disallowed) = specials.partition(&every);
            assert_eq!(
                all_allowed,
                specials.allowed(),
                "{}: naming every special must allow every special",
                specials.name
            );
            assert_eq!(
                none_disallowed,
                vec![],
                "{}: naming every special must leave nothing disallowed",
                specials.name
            );
        }
    }

    /// An undeclared name in `allow` permits nothing.
    ///
    /// Locks out a `partition` that trusts `allow` as the allow-list instead of
    /// filtering the declared table by it. A typo would then permit a special
    /// this vocabulary does not have, which is harmless, OR fail to disallow the
    /// one that was meant, which is not: `<|endoftext>` differs from
    /// `<|endoftext|>` by one byte and must leave the real special disallowed.
    #[test]
    fn partition_ignores_a_name_the_vocabulary_does_not_declare() {
        let (allowed, disallowed) = CL100K_BASE_SPECIALS.partition(&["<|endoftext>", "<|nope|>"]);
        assert_eq!(allowed, vec![], "no undeclared name may become allowed");
        assert_eq!(
            disallowed,
            CL100K_BASE_SPECIALS.allowed(),
            "a typo must leave every real special disallowed"
        );
    }

    /// The scanner reports the matched TEXT alongside its offset and id.
    ///
    /// [`encode_checked`] names the offending special from this text, so a
    /// scanner returning the wrong entry's text would report a special that is
    /// not the one it stopped on. Checked where it can actually be wrong: two
    /// candidates of different length at different offsets, and a prefix pair at
    /// one offset where the LONGER text must be reported.
    #[test]
    fn the_scanner_reports_the_matched_text_with_its_offset_and_id() {
        let candidates = [("<|b|>", TokenId(2)), ("<|a|>", TokenId(1))];
        assert_eq!(
            next_special(b"zz<|b|>yy<|a|>", 0, &candidates),
            Some((2, "<|b|>", TokenId(2)))
        );
        assert_eq!(
            next_special(b"zz<|b|>yy<|a|>", 7, &candidates),
            Some((9, "<|a|>", TokenId(1))),
            "resuming past the first match must report the second, not the first"
        );
        let prefix_pair = [("<|x|>", TokenId(1)), ("<|x|>y", TokenId(2))];
        assert_eq!(
            next_special(b"<|x|>y", 0, &prefix_pair),
            Some((0, "<|x|>y", TokenId(2))),
            "the longest match at one offset must report its own text"
        );
        assert_eq!(next_special(b"nothing", 0, &candidates), None);
    }

    /// The scanner reports the LEFTMOST special, not the first one listed.
    ///
    /// Locks out a scanner that loops the allow-list outermost, which finds
    /// whichever special appears earliest in the LIST rather than earliest in the
    /// INPUT. That reorders the output ids whenever two specials both occur, and
    /// it is invisible on any input holding only one special.
    #[test]
    fn the_scanner_reports_the_leftmost_special_not_the_first_listed() {
        let allowed = [("<|b|>", TokenId(2)), ("<|a|>", TokenId(1))];
        // "<|a|>" sits at 0 but is listed second.
        assert_eq!(
            next_allowed_special(b"<|a|>xx<|b|>", 0, &allowed),
            Some((0, 5, TokenId(1)))
        );
        assert_eq!(
            next_allowed_special(b"zz<|b|>yy<|a|>", 0, &allowed),
            Some((2, 7, TokenId(2)))
        );
    }

    /// At one position the LONGEST allowed special wins.
    ///
    /// Locks out a scanner taking the first match at a position, which would
    /// emit the short special's id and then encode the remaining bytes of the
    /// long one as ordinary text: a wrong id followed by trailing garbage.
    #[test]
    fn the_scanner_prefers_the_longest_match_at_one_position() {
        let allowed = [("<|x|>", TokenId(1)), ("<|x|>y", TokenId(2))];
        assert_eq!(
            next_allowed_special(b"<|x|>y", 0, &allowed),
            Some((0, 6, TokenId(2))),
            "the 6-byte special must beat its own 5-byte prefix"
        );
        assert_eq!(
            next_allowed_special(b"<|x|>z", 0, &allowed),
            Some((0, 5, TokenId(1))),
            "without the trailing y only the short special matches"
        );
    }

    /// `from` skips a special already consumed, and absence is reported.
    ///
    /// Locks out a scan that restarts at zero every call, which would loop
    /// forever on the first special, and one that reports a match past the end
    /// of the input.
    #[test]
    fn the_scanner_honours_the_start_offset_and_reports_absence() {
        let allowed = [("<|a|>", TokenId(1))];
        assert_eq!(
            next_allowed_special(b"<|a|>tail", 0, &allowed),
            Some((0, 5, TokenId(1)))
        );
        assert_eq!(next_allowed_special(b"<|a|>tail", 5, &allowed), None);
        assert_eq!(next_allowed_special(b"nothing here", 0, &allowed), None);
        assert_eq!(next_allowed_special(b"", 0, &allowed), None);
        assert_eq!(
            next_allowed_special(b"<|a|>", 0, &[]),
            None,
            "an empty allow-list recognizes nothing"
        );
    }

    /// A truncated special is not a special.
    ///
    /// Locks out a prefix-only match: `<|endoftext|` without its closing `|>`
    /// must stay ordinary text, otherwise any text merely starting like a
    /// special would collapse to a single wrong id.
    #[test]
    fn a_truncated_special_is_not_matched() {
        let allowed = CL100K_BASE_SPECIALS.allowed();
        assert_eq!(next_allowed_special(b"<|endoftext|", 0, &allowed), None);
        assert_eq!(next_allowed_special(b"<|endoftext", 0, &allowed), None);
        assert_eq!(
            next_allowed_special(b"<|endoftext|>", 0, &allowed),
            Some((0, 13, TokenId(100_257))),
            "the complete form is 13 bytes and must match"
        );
    }
}