rusting_brain 3.0.0

A Rust deep-learning library for training and running transformer language models, dense and mixture-of-experts, on CPU or CUDA.
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
//! Byte-level byte-pair encoding, read from a `tokenizer.json`.
//!
//! A text-to-image model conditions on a prompt, and the prompt has to become
//! token ids the way the text encoder was trained to see them. Every encoder in
//! use here — CLIP, Qwen3, and the GPT-2 line generally — tokenizes with the
//! same algorithm: map the text's bytes into a printable alphabet, split it
//! into words, then merge adjacent symbol pairs in the order a merge table
//! lists them.
//!
//! This is a reader for the file Hugging Face publishes that table in. No new
//! dependency: the file is JSON, and the crate already reads JSON.
//!
//! [`Unigram`] beside it is the sentencepiece algorithm T5 tokenizes with,
//! which is a different model rather than a different table: the file lists a
//! score for every piece, and tokenizing is the highest-scoring way to cut the
//! text into pieces that are in the list.
//!
//! ponytail: the pre-tokenizer is the GPT-2 split rule written as a state
//! machine instead of the regular expression the reference uses, because the
//! crate has no regular-expression engine and this rule is small enough to
//! write out. Upgrade path if a checkpoint ever ships a different rule: read
//! `pre_tokenizer` out of the file and dispatch on it.

use crate::network::NetworkError;
use std::collections::HashMap;

/// A byte-level BPE tokenizer.
#[derive(Clone, Debug)]
pub struct Bpe {
    vocab: HashMap<String, u32>,
    tokens: Vec<String>,
    /// Merge priority: a lower rank is applied first.
    ranks: HashMap<(String, String), u32>,
    /// Tokens matched literally before anything else, longest first.
    specials: Vec<(String, u32)>,
    /// What CLIP appends to the last symbol of each word.
    end_of_word: Option<String>,
    lowercase: bool,
    byte_encoder: Vec<char>,
    byte_decoder: HashMap<char, u8>,
}

impl Bpe {
    /// Reads a `tokenizer.json`.
    pub fn from_file(path: impl AsRef<std::path::Path>) -> Result<Self, NetworkError> {
        let text = std::fs::read_to_string(path)?;
        Self::from_json(&text)
    }

    /// The same, from the file's contents.
    pub fn from_json(text: &str) -> Result<Self, NetworkError> {
        let json: serde_json::Value = serde_json::from_str(text)
            .map_err(|error| NetworkError::InvalidDataset(format!("tokenizer.json: {error}")))?;
        let model = json
            .get("model")
            .ok_or_else(|| NetworkError::InvalidDataset("tokenizer.json has no model".into()))?;

        let vocab: HashMap<String, u32> = model
            .get("vocab")
            .and_then(|vocab| vocab.as_object())
            .ok_or_else(|| NetworkError::InvalidDataset("the model has no vocabulary".into()))?
            .iter()
            .map(|(token, id)| {
                let id = id
                    .as_u64()
                    .ok_or_else(|| NetworkError::InvalidDataset(format!("{token} has no id")))?;
                Ok((token.clone(), id as u32))
            })
            .collect::<Result<_, NetworkError>>()?;

        let mut tokens =
            vec![String::new(); vocab.values().map(|id| *id as usize + 1).max().unwrap_or(0)];
        for (token, id) in &vocab {
            tokens[*id as usize] = token.clone();
        }

        // Merges are a list of "a b" strings in older files and of ["a", "b"]
        // pairs in newer ones.
        let mut ranks = HashMap::new();
        if let Some(merges) = model.get("merges").and_then(|merges| merges.as_array()) {
            for (rank, merge) in merges.iter().enumerate() {
                let pair = match merge {
                    serde_json::Value::String(merge) => {
                        let mut parts = merge.splitn(2, ' ');
                        match (parts.next(), parts.next()) {
                            (Some(first), Some(second)) => (first.to_string(), second.to_string()),
                            _ => continue,
                        }
                    }
                    serde_json::Value::Array(pair) if pair.len() == 2 => (
                        pair[0].as_str().unwrap_or_default().to_string(),
                        pair[1].as_str().unwrap_or_default().to_string(),
                    ),
                    _ => continue,
                };
                ranks.insert(pair, rank as u32);
            }
        }

        let mut specials: Vec<(String, u32)> = json
            .get("added_tokens")
            .and_then(|added| added.as_array())
            .map(|added| {
                added
                    .iter()
                    .filter_map(|token| {
                        Some((
                            token.get("content")?.as_str()?.to_string(),
                            token.get("id")?.as_u64()? as u32,
                        ))
                    })
                    .collect()
            })
            .unwrap_or_default();
        // Longest first, so `<|im_start|>` wins over a prefix of itself.
        specials.sort_by_key(|(token, _)| std::cmp::Reverse(token.len()));

        let end_of_word = model
            .get("end_of_word_suffix")
            .and_then(|suffix| suffix.as_str())
            .map(str::to_string);
        let lowercase = json
            .get("normalizer")
            .map(|normalizer| normalizer.to_string().contains("Lowercase"))
            .unwrap_or(false);

        // A file lists its added tokens separately, but they are part of the
        // vocabulary: a caller asking for `<|endoftext|>` by name has to find
        // it, and decoding has to print it.
        let mut vocab = vocab;
        for (token, id) in &specials {
            if tokens.len() <= *id as usize {
                tokens.resize(*id as usize + 1, String::new());
            }
            tokens[*id as usize] = token.clone();
            vocab.entry(token.clone()).or_insert(*id);
        }

        let byte_encoder = byte_alphabet();
        let byte_decoder = byte_encoder
            .iter()
            .enumerate()
            .map(|(byte, character)| (*character, byte as u8))
            .collect();

        Ok(Self {
            vocab,
            tokens,
            ranks,
            specials,
            end_of_word,
            lowercase,
            byte_encoder,
            byte_decoder,
        })
    }

    /// How many ids the vocabulary holds.
    pub fn vocab_size(&self) -> usize {
        self.tokens.len()
    }

    /// The id of a token written out in full, which is how a caller finds a
    /// special token such as `<|endoftext|>`.
    pub fn token_id(&self, token: &str) -> Option<u32> {
        self.vocab.get(token).copied()
    }

    /// Tokenizes text.
    pub fn encode(&self, text: &str) -> Result<Vec<u32>, NetworkError> {
        let owned;
        let text = if self.lowercase {
            owned = text.to_lowercase();
            &owned
        } else {
            text
        };

        let mut ids = Vec::new();
        let mut rest = text;
        while !rest.is_empty() {
            // A special token is matched literally wherever it appears, and
            // never merged into its neighbours.
            let special = self
                .specials
                .iter()
                .filter_map(|(token, id)| rest.find(token.as_str()).map(|at| (at, token, *id)))
                .min_by_key(|(at, token, _)| (*at, usize::MAX - token.len()));
            let (head, tail) = match special {
                Some((at, token, id)) => {
                    let head = &rest[..at];
                    let tail = &rest[at + token.len()..];
                    self.encode_plain(head, &mut ids)?;
                    ids.push(id);
                    ("", tail)
                }
                None => (rest, ""),
            };
            if !head.is_empty() {
                self.encode_plain(head, &mut ids)?;
            }
            rest = tail;
        }
        Ok(ids)
    }

    /// Encodes text that holds no special token.
    fn encode_plain(&self, text: &str, ids: &mut Vec<u32>) -> Result<(), NetworkError> {
        // CLIP marks the end of a word with a suffix instead of carrying the
        // space that precedes it, so its rule throws whitespace away rather
        // than joining it to the next word, and cuts a run of digits into
        // single digits. The GPT-2 rule keeps both.
        let words: Vec<String> = match self.end_of_word.is_some() {
            true => pre_tokenize(text)
                .iter()
                .map(|word| word.trim())
                .filter(|word| !word.is_empty())
                .flat_map(|word| match word.chars().all(char::is_numeric) {
                    true => word.chars().map(|digit| digit.to_string()).collect(),
                    false => vec![word.to_string()],
                })
                .collect(),
            false => pre_tokenize(text),
        };

        for word in words {
            // Bytes into the printable alphabet, so every input is spellable in
            // the vocabulary whatever it held.
            let mut symbols: Vec<String> = word
                .bytes()
                .map(|byte| self.byte_encoder[byte as usize].to_string())
                .collect();
            if symbols.is_empty() {
                continue;
            }
            if let Some(suffix) = &self.end_of_word {
                symbols
                    .last_mut()
                    .expect("the word is not empty")
                    .push_str(suffix);
            }

            self.merge(&mut symbols);

            for symbol in symbols {
                let id = self.vocab.get(&symbol).copied().ok_or_else(|| {
                    NetworkError::InvalidDataset(format!(
                        "the vocabulary has no token for {symbol:?}, so this file's merges and \
                         its vocabulary disagree"
                    ))
                })?;
                ids.push(id);
            }
        }
        Ok(())
    }

    /// Repeatedly joins the best-ranked adjacent pair, which is the whole of
    /// byte-pair encoding.
    fn merge(&self, symbols: &mut Vec<String>) {
        while symbols.len() > 1 {
            let best = symbols
                .windows(2)
                .enumerate()
                .filter_map(|(index, pair)| {
                    let rank = self.ranks.get(&(pair[0].clone(), pair[1].clone()))?;
                    Some((*rank, index))
                })
                .min();
            let Some((_, index)) = best else {
                return;
            };
            let second = symbols.remove(index + 1);
            symbols[index].push_str(&second);
        }
    }

    /// Turns ids back into text, which is what a round-trip check needs.
    pub fn decode(&self, ids: &[u32]) -> String {
        let mut bytes = Vec::new();
        for id in ids {
            let Some(token) = self.tokens.get(*id as usize) else {
                continue;
            };
            let token = match &self.end_of_word {
                Some(suffix) => token.replace(suffix.as_str(), " "),
                None => token.clone(),
            };
            if self.specials.iter().any(|(special, _)| *special == token) {
                bytes.extend_from_slice(token.as_bytes());
                continue;
            }
            for character in token.chars() {
                match self.byte_decoder.get(&character) {
                    Some(byte) => bytes.push(*byte),
                    // A special token written straight into the vocabulary is
                    // not in the byte alphabet, so it passes through as text.
                    None => bytes.extend_from_slice(character.to_string().as_bytes()),
                }
            }
        }
        String::from_utf8_lossy(&bytes).into_owned()
    }
}

/// The GPT-2 byte alphabet: every byte gets a printable character, so text in
/// any encoding survives the trip through a vocabulary of strings.
fn byte_alphabet() -> Vec<char> {
    let printable: Vec<u32> = (33..=126).chain(161..=172).chain(174..=255).collect();
    let mut alphabet = vec!['\0'; 256];
    let mut next = 0u32;
    for byte in 0..256u32 {
        let character = if printable.contains(&byte) {
            byte
        } else {
            let character = 256 + next;
            next += 1;
            character
        };
        alphabet[byte as usize] = char::from_u32(character).expect("a valid code point");
    }
    alphabet
}

/// Splits text the way GPT-2's pre-tokenizer does: contractions, then runs of
/// letters, digits or punctuation, each keeping the space in front of it.
fn pre_tokenize(text: &str) -> Vec<String> {
    const CONTRACTIONS: [&str; 7] = ["'s", "'t", "'re", "'ve", "'m", "'ll", "'d"];
    let characters: Vec<char> = text.chars().collect();
    let mut words = Vec::new();
    let mut index = 0;

    while index < characters.len() {
        let rest: String = characters[index..].iter().collect();
        if let Some(contraction) = CONTRACTIONS
            .iter()
            .find(|contraction| rest.starts_with(**contraction))
        {
            words.push((*contraction).to_string());
            index += contraction.chars().count();
            continue;
        }

        let start = index;
        // A single leading space belongs to the word that follows it.
        let space = characters[index] == ' ' && index + 1 < characters.len();
        let first = if space { index + 1 } else { index };
        let kind = characters
            .get(first)
            .copied()
            .map(classify)
            .unwrap_or(Kind::Space);

        if space && kind != Kind::Space {
            index += 1;
        } else if space {
            // Runs of whitespace stand alone, except that the last space goes
            // to the word after it.
            while index < characters.len() && characters[index].is_whitespace() {
                index += 1;
            }
            let trailing = index < characters.len();
            let end = if trailing && index - start > 1 {
                index - 1
            } else {
                index
            };
            words.push(characters[start..end].iter().collect());
            index = end;
            continue;
        }

        let body = index;
        while index < characters.len() && classify(characters[index]) == kind {
            index += 1;
        }
        if index == body {
            index += 1;
        }
        words.push(characters[start..index].iter().collect());
    }

    words
}

#[derive(Clone, Copy, PartialEq)]
enum Kind {
    Letter,
    Number,
    Other,
    Space,
}

fn classify(character: char) -> Kind {
    if character.is_alphabetic() {
        Kind::Letter
    } else if character.is_numeric() {
        Kind::Number
    } else if character.is_whitespace() {
        Kind::Space
    } else {
        Kind::Other
    }
}

/// A sentencepiece unigram tokenizer, which is what the T5 family uses.
///
/// Where byte-pair encoding builds tokens up by merging, unigram cuts the text
/// down: every piece in the vocabulary carries a score, and the tokenization is
/// the segmentation whose scores sum highest. That is one pass of Viterbi over
/// the string.
///
/// ponytail: the normalizer is whitespace folding and the sentencepiece space
/// marker, not the precompiled character map the file also carries. That map is
/// a serialized trie of Unicode foldings, and prompts in this field are the
/// text a person typed. Upgrade path if it ever matters: read `precompiled_
/// charsmap` and apply it before the split.
#[derive(Clone, Debug)]
pub struct Unigram {
    pieces: HashMap<String, (u32, f32)>,
    tokens: Vec<String>,
    unk: u32,
    /// What an unspellable character scores, which is below every real piece so
    /// that it is only ever used when nothing else fits.
    unk_score: f32,
    /// The longest piece in bytes, which bounds how far back Viterbi looks.
    longest: usize,
    specials: Vec<(String, u32)>,
    /// The character standing in for a space, `▁` in every published file.
    space: char,
    prefix_space: bool,
}

impl Unigram {
    /// Reads a `tokenizer.json`.
    pub fn from_file(path: impl AsRef<std::path::Path>) -> Result<Self, NetworkError> {
        Self::from_json(&std::fs::read_to_string(path)?)
    }

    /// The same, from the file's contents.
    pub fn from_json(text: &str) -> Result<Self, NetworkError> {
        let json: serde_json::Value = serde_json::from_str(text)
            .map_err(|error| NetworkError::InvalidDataset(format!("tokenizer.json: {error}")))?;
        let model = json
            .get("model")
            .ok_or_else(|| NetworkError::InvalidDataset("tokenizer.json has no model".into()))?;
        if model.get("type").and_then(|kind| kind.as_str()) != Some("Unigram") {
            return Err(NetworkError::InvalidDataset(
                "this tokenizer.json is not a unigram model".into(),
            ));
        }

        let entries = model
            .get("vocab")
            .and_then(|vocab| vocab.as_array())
            .ok_or_else(|| NetworkError::InvalidDataset("the model has no vocabulary".into()))?;
        let mut pieces = HashMap::with_capacity(entries.len());
        let mut tokens = Vec::with_capacity(entries.len());
        let mut lowest = 0.0f32;
        for (id, entry) in entries.iter().enumerate() {
            // Each entry is a `[piece, score]` pair.
            let piece = entry
                .get(0)
                .and_then(|piece| piece.as_str())
                .ok_or_else(|| {
                    NetworkError::InvalidDataset(format!("vocabulary entry {id} has no piece"))
                })?
                .to_string();
            let score = entry.get(1).and_then(|score| score.as_f64()).unwrap_or(0.0) as f32;
            lowest = lowest.min(score);
            pieces.insert(piece.clone(), (id as u32, score));
            tokens.push(piece);
        }
        let longest = tokens.iter().map(String::len).max().unwrap_or(1);

        let mut specials: Vec<(String, u32)> = json
            .get("added_tokens")
            .and_then(|added| added.as_array())
            .map(|added| {
                added
                    .iter()
                    .filter_map(|token| {
                        Some((
                            token.get("content")?.as_str()?.to_string(),
                            token.get("id")?.as_u64()? as u32,
                        ))
                    })
                    .collect()
            })
            .unwrap_or_default();
        specials.sort_by_key(|(token, _)| std::cmp::Reverse(token.len()));

        let metaspace = pre_tokenizer(&json, "Metaspace");
        Ok(Self {
            unk: model.get("unk_id").and_then(|id| id.as_u64()).unwrap_or(0) as u32,
            unk_score: lowest - 10.0,
            longest,
            specials,
            space: metaspace
                .as_ref()
                .and_then(|metaspace| metaspace.get("replacement"))
                .and_then(|replacement| replacement.as_str())
                .and_then(|replacement| replacement.chars().next())
                .unwrap_or('\u{2581}'),
            // Published files write this as a flag or as a "prepend_scheme",
            // and both mean the same thing.
            prefix_space: metaspace
                .as_ref()
                .map(|metaspace| {
                    metaspace
                        .get("add_prefix_space")
                        .and_then(|flag| flag.as_bool())
                        .unwrap_or_else(|| {
                            metaspace.get("prepend_scheme").and_then(|s| s.as_str())
                                != Some("never")
                        })
                })
                .unwrap_or(true),
            pieces,
            tokens,
        })
    }

    /// How many ids the vocabulary holds.
    pub fn vocab_size(&self) -> usize {
        self.tokens.len()
    }

    /// The id of a piece written out in full, which is how a caller finds a
    /// special token such as `</s>`.
    pub fn token_id(&self, token: &str) -> Option<u32> {
        self.pieces.get(token).map(|(id, _)| *id)
    }

    /// Tokenizes text.
    pub fn encode(&self, text: &str) -> Result<Vec<u32>, NetworkError> {
        let mut ids = Vec::new();
        let mut rest = text;
        while !rest.is_empty() {
            // A special token is matched literally, whatever the scores say.
            let special = self
                .specials
                .iter()
                .filter_map(|(token, id)| rest.find(token.as_str()).map(|at| (at, token, *id)))
                .min_by_key(|(at, token, _)| (*at, usize::MAX - token.len()));
            match special {
                Some((at, token, id)) => {
                    self.encode_plain(&rest[..at], &mut ids);
                    ids.push(id);
                    rest = &rest[at + token.len()..];
                }
                None => {
                    self.encode_plain(rest, &mut ids);
                    rest = "";
                }
            }
        }
        Ok(ids)
    }

    /// Turns ids back into text.
    pub fn decode(&self, ids: &[u32]) -> String {
        let text: String = ids
            .iter()
            .filter_map(|id| self.tokens.get(*id as usize))
            .map(String::as_str)
            .collect::<String>()
            .replace(self.space, " ");
        match self.prefix_space {
            true => text.strip_prefix(' ').unwrap_or(&text).to_string(),
            false => text,
        }
    }

    /// Encodes text that holds no special token: normalize, then Viterbi.
    fn encode_plain(&self, text: &str, ids: &mut Vec<u32>) {
        let text = self.normalize(text);
        if text.is_empty() {
            return;
        }

        // `best[at]` is the score of the best way to reach byte `at`, and
        // `from[at]` is the piece that got there.
        let mut best = vec![f32::NEG_INFINITY; text.len() + 1];
        let mut from: Vec<(usize, u32)> = vec![(0, self.unk); text.len() + 1];
        best[0] = 0.0;
        for end in 1..=text.len() {
            if !text.is_char_boundary(end) {
                continue;
            }
            let earliest = end.saturating_sub(self.longest);
            for start in earliest..end {
                if best[start] == f32::NEG_INFINITY || !text.is_char_boundary(start) {
                    continue;
                }
                let piece = &text[start..end];
                // Anything not in the vocabulary is only allowed as a single
                // character, standing for the unknown token.
                let (id, score) = match self.pieces.get(piece) {
                    Some((id, score)) => (*id, *score),
                    None if piece.chars().count() == 1 => (self.unk, self.unk_score),
                    None => continue,
                };
                let total = best[start] + score;
                if total > best[end] {
                    best[end] = total;
                    from[end] = (start, id);
                }
            }
        }

        let mut path = Vec::new();
        let mut at = text.len();
        while at > 0 {
            let (start, id) = from[at];
            path.push(id);
            at = start;
        }
        path.reverse();
        ids.extend(path);
    }

    /// Whitespace folding and the space marker, which is the part of the
    /// published normalizer that changes a prompt.
    fn normalize(&self, text: &str) -> String {
        let mut normalized = String::with_capacity(text.len() + 1);
        if self.prefix_space {
            normalized.push(self.space);
        }
        let mut spaced = self.prefix_space;
        for character in text.trim().chars() {
            match character.is_whitespace() {
                // Runs of whitespace fold to one marker, and a run next to the
                // prefix marker disappears into it.
                true if spaced => {}
                true => {
                    normalized.push(self.space);
                    spaced = true;
                }
                false => {
                    normalized.push(character);
                    spaced = false;
                }
            }
        }
        normalized
    }
}

/// The pre-tokenizer of this kind, whether the file holds one or a sequence of
/// them.
fn pre_tokenizer(json: &serde_json::Value, kind: &str) -> Option<serde_json::Value> {
    let is_kind =
        |value: &serde_json::Value| value.get("type").and_then(|name| name.as_str()) == Some(kind);
    let pre = json.get("pre_tokenizer")?;
    if is_kind(pre) {
        return Some(pre.clone());
    }
    pre.get("pretokenizers")?
        .as_array()?
        .iter()
        .find(|value| is_kind(value))
        .cloned()
}

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

    /// A vocabulary over the byte alphabet, plus whatever merges a test needs.
    pub(crate) fn tokenizer(merges: &[&str], extra: &[&str], suffix: Option<&str>) -> Bpe {
        Bpe::from_json(&tokenizer_json(merges, extra, suffix)).unwrap()
    }

    /// The same vocabulary, written where a loader will look for it.
    pub(crate) fn write(
        path: &std::path::Path,
        merges: &[&str],
        extra: &[&str],
        suffix: Option<&str>,
    ) {
        std::fs::write(path, tokenizer_json(merges, extra, suffix)).unwrap();
    }

    fn tokenizer_json(merges: &[&str], extra: &[&str], suffix: Option<&str>) -> String {
        let alphabet = byte_alphabet();
        let mut vocab = serde_json::Map::new();
        for (id, character) in alphabet.iter().enumerate() {
            vocab.insert(character.to_string(), serde_json::json!(id));
        }
        let mut next = alphabet.len();
        for token in extra {
            vocab.insert((*token).to_string(), serde_json::json!(next));
            next += 1;
        }
        let mut model = serde_json::json!({
            "vocab": vocab,
            "merges": merges.iter().map(|merge| serde_json::json!(merge)).collect::<Vec<_>>(),
        });
        if let Some(suffix) = suffix {
            model["end_of_word_suffix"] = serde_json::json!(suffix);
        }
        let json = serde_json::json!({
            "model": model,
            "added_tokens": [{"id": next, "content": "<|end|>"}],
        });
        json.to_string()
    }

    #[test]
    fn text_survives_the_round_trip_through_ids() {
        // No merges: every byte is its own token, which still has to decode
        // back to the original text.
        let bpe = tokenizer(&[], &[], None);
        for text in [
            "hello world",
            "a café, 3 times!",
            "  spaced\n\ttext",
            "日本語",
        ] {
            let ids = bpe.encode(text).unwrap();
            assert_eq!(bpe.decode(&ids), text, "{text:?}");
        }
    }

    #[test]
    fn merges_are_applied_in_rank_order() {
        // "lo" merges before "hel", so "hello" becomes he + l + lo.
        let bpe = tokenizer(&["l o", "h e", "he l"], &["lo", "he", "hel"], None);
        let ids = bpe.encode("hello").unwrap();
        assert_eq!(ids.len(), 2);
        assert_eq!(bpe.decode(&ids), "hello");

        // A word with no merge available stays one token per byte.
        assert_eq!(bpe.encode("xyz").unwrap().len(), 3);
    }

    #[test]
    fn the_pre_tokenizer_splits_the_way_gpt_two_does() {
        assert_eq!(pre_tokenize("Hello world"), vec!["Hello", " world"]);
        assert_eq!(
            pre_tokenize("it's a test, really!"),
            vec!["it", "'s", " a", " test", ",", " really", "!"]
        );
        assert_eq!(pre_tokenize("x  y"), vec!["x", " ", " y"]);
        assert_eq!(pre_tokenize("value = 42"), vec!["value", " =", " 42"]);
        assert_eq!(pre_tokenize("trailing  "), vec!["trailing", "  "]);
    }

    #[test]
    fn a_special_token_is_matched_whole_and_never_merged() {
        let bpe = tokenizer(&["h i"], &["hi"], None);
        let end = bpe.token_id("<|end|>").unwrap();
        let ids = bpe.encode("hi<|end|>hi").unwrap();

        assert_eq!(ids.len(), 3);
        assert_eq!(ids[1], end);
        assert_eq!(bpe.decode(&ids), "hi<|end|>hi");
    }

    #[test]
    fn a_word_suffix_vocabulary_marks_the_end_of_each_word() {
        // What CLIP does: the last symbol of a word carries `</w>`.
        let bpe = tokenizer(&[], &["a</w>", "b</w>"], Some("</w>"));
        let ids = bpe.encode("ab").unwrap();
        assert_eq!(ids.len(), 2);
        // The suffix decodes back to the space it stands for.
        assert_eq!(bpe.decode(&ids), "ab ");
    }

    #[test]
    fn a_word_suffix_vocabulary_drops_the_space_between_words() {
        // CLIP's own rule throws whitespace away and cuts digits apart. A
        // space that survives as its own token reaches the text encoder as a
        // word, and the prompt is then not the prompt that was asked for.
        let bpe = tokenizer(&[], &["a</w>", "b</w>", "1</w>", "2</w>"], Some("</w>"));
        let space = bpe
            .token_id("\u{0120}")
            .expect("the byte alphabet holds a space");

        let ids = bpe.encode("a b 12").unwrap();
        assert!(!ids.contains(&space), "{ids:?} carries a space as a token");
        // One token per word, and one per digit.
        assert_eq!(ids.len(), 4);
    }

    #[test]
    fn a_file_that_is_not_a_tokenizer_is_refused() {
        assert!(Bpe::from_json("{}").is_err());
        assert!(Bpe::from_json("{\"model\": {}}").is_err());
        assert!(Bpe::from_json("not json").is_err());
    }
    /// A unigram vocabulary over a handful of pieces, scored so that the long
    /// ones win where they fit.
    pub(crate) fn unigram_json() -> String {
        let vocab: Vec<serde_json::Value> = [
            ("<pad>", 0.0),
            ("</s>", 0.0),
            ("<unk>", 0.0),
            ("\u{2581}", -3.0),
            ("\u{2581}a", -1.5),
            ("\u{2581}ab", -0.6),
            ("\u{2581}abc", -0.4),
            ("b", -2.0),
            ("c", -2.0),
            ("\u{2581}c", -2.5),
        ]
        .iter()
        .map(|(piece, score)| serde_json::json!([piece, score]))
        .collect();
        serde_json::json!({
            "model": {"type": "Unigram", "unk_id": 2, "vocab": vocab},
            "pre_tokenizer": {"type": "Metaspace", "replacement": "\u{2581}",
                              "add_prefix_space": true},
            "added_tokens": [{"id": 1, "content": "</s>"}],
        })
        .to_string()
    }

    #[test]
    fn unigram_cuts_the_text_the_highest_scoring_way() {
        let tokenizer = Unigram::from_json(&unigram_json()).unwrap();

        // "▁abc" alone scores -0.4, which beats "▁ab" + "c" at -2.6.
        assert_eq!(tokenizer.encode("abc").unwrap(), vec![6]);
        // No piece spells "▁ac", so the best cut is "▁a" then "c".
        assert_eq!(tokenizer.encode("ac").unwrap(), vec![4, 8]);
        assert_eq!(tokenizer.decode(&[6]), "abc");
        assert_eq!(tokenizer.decode(&tokenizer.encode("a b").unwrap()), "a b");
    }

    #[test]
    fn unigram_folds_whitespace_and_keeps_special_tokens_whole() {
        let tokenizer = Unigram::from_json(&unigram_json()).unwrap();

        assert_eq!(
            tokenizer.encode("  ab \n c ").unwrap(),
            tokenizer.encode("ab c").unwrap()
        );
        let ids = tokenizer.encode("ab</s>").unwrap();
        assert_eq!(ids.last(), Some(&1));
        // A character no piece spells becomes the unknown token rather than
        // failing the prompt.
        assert_eq!(tokenizer.encode("\u{1F600}").unwrap(), vec![3, 2]);
    }

    #[test]
    fn unigram_refuses_a_file_that_is_not_one() {
        assert!(Unigram::from_json(&tokenizer_json(&[], &[], None)).is_err());
    }
}