Skip to main content

dynamo_tokenizers/
lib.rs

1// SPDX-FileCopyrightText: Copyright (c) 2024-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4pub mod basetenkenizer;
5pub mod cache;
6pub mod fastokens;
7pub mod hf;
8pub mod tekken;
9pub mod tiktoken;
10
11// TODO: Add tokenizer benchmarks
12// TODO: Enable README.md as a module doc
13// #[doc = include_str!("../README.md")]
14
15use std::hash::{DefaultHasher, Hash, Hasher};
16use std::sync::Arc;
17use std::{fs::File, io::BufReader, ops::Deref, path::Path};
18
19use anyhow::Context as _;
20pub use anyhow::{Error, Result};
21
22pub use basetenkenizer::BasetenTokenizer;
23pub use cache::{
24    CacheTokenUsage, CacheTokenUsageFn, CachedTokenizer, L1CacheStats, SharedTokenizerCache,
25    SharedTokenizerCacheStats,
26};
27pub use fastokens::{FastTikTokenTokenizer, FastTokenizer};
28pub use hf::HuggingFaceTokenizer;
29pub use tekken::TekkenTokenizer;
30pub use tiktoken::TikTokenTokenizer;
31pub use traits::DecodeResult;
32
33pub type TokenIdType = u32;
34
35/// A rendered prompt segment with an explicit trust boundary for special tokens.
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37pub struct EncodeSegment<'a> {
38    pub text: &'a str,
39    /// Recognize added/control tokens in this trusted renderer output.
40    ///
41    /// Set this to `false` for user, tool, and attribute content so text that
42    /// resembles a control token is encoded as ordinary text.
43    pub allow_special: bool,
44}
45
46impl<'a> EncodeSegment<'a> {
47    pub const fn new(text: &'a str, allow_special: bool) -> Self {
48        Self {
49            text,
50            allow_special,
51        }
52    }
53
54    pub const fn ordinary(text: &'a str) -> Self {
55        Self::new(text, false)
56    }
57
58    pub const fn control(text: &'a str) -> Self {
59        Self::new(text, true)
60    }
61}
62
63/// Represents the type of tokenizer being used
64#[derive(Debug)]
65pub enum TokenizerType {
66    HuggingFace(String),
67    TikToken(String),
68}
69
70/// character offsets in the original text
71pub type Offsets = (usize, usize);
72
73/// Contains the results of tokenizing text: token IDs, string tokens, and their spans
74#[derive(Debug, Clone)]
75pub enum Encoding {
76    /// Hugging Face
77    Hf(Box<tokenizers::tokenizer::Encoding>),
78    /// Sentence Piece
79    Sp(Vec<TokenIdType>),
80}
81
82impl Encoding {
83    pub fn token_ids(&self) -> &[u32] {
84        match self {
85            Encoding::Hf(inner) => inner.get_ids(),
86            Encoding::Sp(inner) => inner,
87        }
88    }
89}
90
91impl Hash for Encoding {
92    fn hash<H: Hasher>(&self, state: &mut H) {
93        self.token_ids().hash(state);
94    }
95}
96
97pub mod traits {
98    use super::*;
99
100    pub trait Encoder: Send + Sync {
101        fn encode(&self, input: &str) -> Result<Encoding>;
102        fn encode_batch(&self, inputs: &[&str]) -> Result<Vec<Encoding>>;
103
104        /// Encode Kimi K3-style renderer segments while preserving trusted
105        /// control-token and untrusted content boundaries.
106        ///
107        /// Each segment controls whether added/control tokens are recognized
108        /// through [`EncodeSegment::allow_special`]. This prevents text in user,
109        /// tool, or attribute content from becoming structural when it happens
110        /// to resemble a control token.
111        ///
112        /// The Baseten and TikToken backends preserve legacy tiktoken behavior
113        /// by splitting each segment into chunks of at most 400,000 characters
114        /// and splitting whitespace/non-whitespace runs at 25,000 characters.
115        /// Baseten encodes independent chunks through the Rayon thread pool,
116        /// then concatenates them in input order, and applies tokenizer
117        /// post-processing once after all segment IDs have been joined.
118        /// TikToken classifies whitespace like the reference Kimi tokenizer
119        /// (Python's `str.isspace`), while Baseten uses `char::is_whitespace`;
120        /// the two differ only on runs of U+001C..U+001F.
121        ///
122        /// Backends must not implement this by flattening the segments first,
123        /// because that discards the special-token trust boundary.
124        fn encode_segments(&self, _segments: &[EncodeSegment<'_>]) -> Result<Encoding> {
125            Err(Error::msg(
126                "tokenizer backend does not support segmented encoding",
127            ))
128        }
129    }
130
131    /// Result of decoding token IDs to text.
132    ///
133    /// Distinguishes between fully valid UTF-8 output and output that contains
134    /// trailing incomplete multi-byte sequences (represented as U+FFFD).
135    /// This lets callers like `DecodeStream::step()` decide whether to emit or
136    /// buffer without resorting to hardcoded replacement-character string checks.
137    #[derive(Debug, Clone, PartialEq, Eq, strum::EnumIs)]
138    pub enum DecodeResult {
139        /// No trailing incomplete multi-byte sequences (text does not end with U+FFFD).
140        /// Note: the string may still contain *interior* U+FFFD characters from
141        /// mid-stream invalid byte sequences; only trailing status is tracked here.
142        Complete(String),
143        /// The decoded string ends with U+FFFD, indicating incomplete trailing
144        /// multi-byte bytes that may be completed by subsequent tokens.
145        Partial(String),
146    }
147
148    impl DecodeResult {
149        /// Returns a reference to the inner string.
150        pub fn as_str(&self) -> &str {
151            match self {
152                DecodeResult::Complete(s) | DecodeResult::Partial(s) => s,
153            }
154        }
155
156        /// Construct from a decoded string: `Partial` if it ends with U+FFFD, else `Complete`.
157        pub fn from_decoded(text: String) -> Self {
158            if text.ends_with('\u{FFFD}') {
159                DecodeResult::Partial(text)
160            } else {
161                DecodeResult::Complete(text)
162            }
163        }
164    }
165
166    impl From<String> for DecodeResult {
167        fn from(text: String) -> Self {
168            DecodeResult::from_decoded(text)
169        }
170    }
171
172    impl From<DecodeResult> for String {
173        fn from(result: DecodeResult) -> Self {
174            match result {
175                DecodeResult::Complete(s) | DecodeResult::Partial(s) => s,
176            }
177        }
178    }
179
180    /// Implementations must ensure that partial multi-byte sequences produce U+FFFD
181    /// (`\u{FFFD}`) in the output rather than returning `Err`. This is commonly achieved
182    /// via `String::from_utf8_lossy` (tiktoken) or library-internal byte-fallback handling
183    /// (HuggingFace). `DecodeStream::step()` relies on `DecodeResult::Partial` to detect
184    /// incomplete sequences and buffer tokens until the full character arrives.
185    pub trait Decoder: Send + Sync {
186        /// Whether appending tokens can still reinterpret the decoded suffix.
187        /// Callers must buffer an unstable suffix until a boundary or end of input.
188        fn has_unstable_suffix(
189            &self,
190            _token_ids: &[TokenIdType],
191            _skip_special_tokens: bool,
192        ) -> bool {
193            false
194        }
195
196        fn decode(
197            &self,
198            token_ids: &[TokenIdType],
199            skip_special_tokens: bool,
200        ) -> Result<DecodeResult>;
201    }
202
203    pub trait Tokenizer: Encoder + Decoder {
204        /// Validate that this tokenizer can be safely wrapped in the prefix cache.
205        ///
206        /// Implementations must explicitly opt in by returning `Ok(())`, or
207        /// return an error explaining why the tokenizer is incompatible.
208        fn validate_prefix_cache(&self) -> Result<()> {
209            Err(Error::msg("tokenizer does not support prefix caching"))
210        }
211
212        /// Apply construction-time [`TokenizerOptions`].
213        ///
214        /// The default implementation ignores the options — correct for
215        /// tokenizers with no applicable option.
216        fn with_options(self, options: TokenizerOptions) -> Self
217        where
218            Self: Sized,
219        {
220            let _ = options;
221            self
222        }
223        /// Vocabulary cardinality including added tokens, when the backend
224        /// can expose one. `None` for backends without a bounded id space or
225        /// vocabulary introspection.
226        fn vocab_size(&self) -> Option<usize> {
227            None
228        }
229
230        /// Resolve a token string to its vocabulary id, when the backend
231        /// supports lookup. `Ok(None)` when the token is not in the
232        /// vocabulary. `Err` when this backend cannot do id lookup at all —
233        /// kept distinct from a genuine vocabulary miss so callers can tell
234        /// "unsupported" from "looked up, not found".
235        ///
236        /// Defaults to unsupported, matching `encode_segments` and
237        /// `validate_prefix_cache`: only backends that can perform lookup
238        /// need to override it.
239        fn token_to_id(&self, _token: &str) -> Result<Option<TokenIdType>> {
240            Err(Error::msg(
241                "tokenizer backend does not support token lookup",
242            ))
243        }
244
245        /// Ids of added tokens marked special (e.g. BOS/EOS/PAD/control
246        /// tokens), as distinct from ordinary vocabulary tokens. `Ok(vec![])`
247        /// for backends that genuinely have none, or that do not distinguish
248        /// special from ordinary vocabulary ids. `Err` when the backend
249        /// cannot enumerate added tokens at all — an empty `Vec` alone
250        /// cannot carry that distinction.
251        ///
252        /// Defaults to unsupported, matching `token_to_id`: only backends
253        /// that can enumerate special ids need to override it.
254        fn special_token_ids(&self) -> Result<Vec<TokenIdType>> {
255            Err(Error::msg(
256                "tokenizer backend does not support special token enumeration",
257            ))
258        }
259
260        /// Count of special tokens `encode`'s `add_special_tokens: true`
261        /// path would add to a bare encoding (e.g. BOS/EOS), available
262        /// without performing an encode. `Ok(0)` for backends that
263        /// genuinely add none. `Err` when the backend cannot determine this
264        /// at all — a plain `0` alone cannot carry that distinction, and
265        /// this value feeds token-budget accounting where a silent `0`
266        /// would under-count rather than fail loudly.
267        ///
268        /// Defaults to unsupported, matching `token_to_id`: only backends
269        /// that can determine this count need to override it.
270        fn num_special_tokens_added(&self) -> Result<usize> {
271            Err(Error::msg(
272                "tokenizer backend does not support special token accounting",
273            ))
274        }
275        // fn make_unique_clone(&self) -> Box<dyn Tokenizer>;
276    }
277}
278
279pub fn file_json_field<T: serde::de::DeserializeOwned>(
280    json_file_path: &Path,
281    field_name: &str,
282) -> anyhow::Result<T> {
283    let file = File::open(json_file_path)
284        .with_context(|| format!("Failed to open file: {:?}", json_file_path))?;
285    let reader = BufReader::new(file);
286
287    let json_data: serde_json::Value = serde_json::from_reader(reader)
288        .with_context(|| format!("Failed to parse JSON from file: {:?}", json_file_path))?;
289
290    let map = json_data.as_object().ok_or_else(|| {
291        anyhow::anyhow!("JSON root is not an object in file: {:?}", json_file_path)
292    })?;
293
294    let field_value = map.get(field_name).ok_or_else(|| {
295        anyhow::anyhow!(
296            "Field '{}' not found in JSON file: {:?}",
297            field_name,
298            json_file_path
299        )
300    })?;
301
302    serde_json::from_value(field_value.clone()).with_context(|| {
303        format!(
304            "Failed to deserialize field '{}' (value: {:?}) to the expected type from file: {:?}",
305            field_name, field_value, json_file_path
306        )
307    })
308}
309
310pub fn log_json_err(filename: &str, json: &str, err: &serde_json::Error) {
311    const ERROR_PREFIX: &str = ">>     ";
312
313    if !(err.is_syntax() || err.is_data()) {
314        return;
315    }
316
317    let line = err.line().saturating_sub(1);
318    let column = err.column().saturating_sub(1);
319
320    let json_lines: Vec<&str> = json.lines().collect();
321    if json_lines.is_empty() {
322        tracing::error!("JSON parsing error in {filename}: File is empty.");
323        return;
324    }
325
326    let start_index = line.saturating_sub(2);
327    let end_index = line.saturating_add(3).min(json_lines.len());
328
329    let mut context_lines: Vec<String> = (start_index..end_index)
330        .map(|i| {
331            if i == line {
332                format!("{ERROR_PREFIX}{}", json_lines[i])
333            } else {
334                format!("{:06} {}", i + 1, json_lines[i])
335            }
336        })
337        .collect();
338
339    let col_indicator = "_".to_string().repeat(column + ERROR_PREFIX.len()) + "^";
340    let error_in_context_idx = line - start_index;
341    if error_in_context_idx < context_lines.len() {
342        context_lines.insert(error_in_context_idx + 1, col_indicator);
343    }
344
345    tracing::error!(
346        "JSON parsing error in {filename}: Line {}, column {}:\n{}",
347        err.line(),
348        err.column(),
349        context_lines.join("\n")
350    );
351}
352
353impl Encoding {
354    pub fn get_hash(&self) -> u64 {
355        let mut hasher = DefaultHasher::new();
356        self.hash(&mut hasher);
357        hasher.finish()
358    }
359}
360
361/// Construction options for [`Tokenizer::from_file_with_options`] /
362/// [`create_tokenizer_from_file`], applied to concrete tokenizers via
363/// [`traits::Tokenizer::with_options`].
364#[derive(Debug, Clone, Copy, Default)]
365pub struct TokenizerOptions {
366    /// Ask the tokenizer to add its declared special tokens (e.g. BOS/EOS via
367    /// its post-processor) during `encode`, `encode_batch`, and supported
368    /// `encode_segments` calls.
369    /// Defaults to `false`, the historical behavior.
370    ///
371    /// Applicable to Hugging Face and Baseten tokenizers.
372    pub add_special_tokens: bool,
373}
374
375/// Main tokenizer wrapper that provides a unified interface for different tokenizer implementations
376#[derive(Clone)]
377pub struct Tokenizer(Arc<dyn traits::Tokenizer>);
378
379impl Tokenizer {
380    pub fn from_file(file_path: &str) -> Result<Tokenizer> {
381        Ok(Tokenizer(create_tokenizer_from_file(file_path)?))
382    }
383
384    pub fn from_file_with_options(file_path: &str, options: TokenizerOptions) -> Result<Tokenizer> {
385        Ok(Tokenizer(create_tokenizer_from_file_with_options(
386            file_path, options,
387        )?))
388    }
389
390    /// Create a stateful sequence object for decoding token_ids into text.
391    /// Append the result of [`DecodeStream::finish`] when input ends; `step` may
392    /// retain a trailing byte-fallback run even when it currently forms valid UTF-8.
393    pub fn decode_stream(
394        &self,
395        prompt_token_ids: &[TokenIdType],
396        skip_special_tokens: bool,
397    ) -> DecodeStream {
398        DecodeStream::new(self.0.clone(), prompt_token_ids, skip_special_tokens)
399    }
400}
401
402impl Deref for Tokenizer {
403    type Target = Arc<dyn traits::Tokenizer>;
404
405    fn deref(&self) -> &Self::Target {
406        &self.0
407    }
408}
409
410impl From<Arc<dyn traits::Tokenizer>> for Tokenizer {
411    fn from(tokenizer: Arc<dyn traits::Tokenizer>) -> Self {
412        Tokenizer(tokenizer)
413    }
414}
415
416impl<T> From<Arc<T>> for Tokenizer
417where
418    T: traits::Tokenizer + 'static, // 'static is required to ensure T can be safely put into an Arc
419{
420    fn from(tokenizer: Arc<T>) -> Self {
421        Tokenizer(tokenizer)
422    }
423}
424
425/// Create a tokenizer from a file path to a tokenizer file.
426/// The file extension is used to determine the tokenizer type.
427/// Supported file types are:
428/// - `tekken.json` / `tekken_*.json`: Mistral Tekken tokenizer
429/// - json: HuggingFace tokenizer
430/// - model, tiktoken: tiktoken BPE tokenizer (requires `config.json` with a supported
431///   `model_type` in the same directory; currently: kimi, kimi_k2, kimi_k25, kimi_k3, kimi_k31)
432pub fn create_tokenizer_from_file(file_path: &str) -> Result<Arc<dyn traits::Tokenizer>> {
433    create_tokenizer_from_file_with_options(file_path, Default::default())
434}
435
436/// Create a tokenizer from a file path to a tokenizer file with additional tokenizer option.
437/// The file extension is used to determine the tokenizer type.
438/// Supported file types are:
439/// - `tekken.json` / `tekken_*.json`: Mistral Tekken tokenizer
440/// - json: HuggingFace tokenizer
441/// - model, tiktoken: tiktoken BPE tokenizer (requires `config.json` with a supported
442///   `model_type` in the same directory; currently: kimi, kimi_k2, kimi_k25, kimi_k3, kimi_k31)
443pub fn create_tokenizer_from_file_with_options(
444    file_path: &str,
445    options: TokenizerOptions,
446) -> Result<Arc<dyn traits::Tokenizer>> {
447    use traits::Tokenizer as _;
448
449    let path = Path::new(file_path);
450    if TekkenTokenizer::is_tekken_file(path) {
451        let tokenizer = TekkenTokenizer::from_file(file_path)?.with_options(options);
452        return Ok(Arc::new(tokenizer));
453    }
454
455    let extension = path
456        .extension()
457        .and_then(std::ffi::OsStr::to_str)
458        .ok_or_else(|| Error::msg("Failed to read file extension".to_string()))?;
459
460    match extension {
461        "json" => {
462            let tokenizer = HuggingFaceTokenizer::from_file(file_path)?.with_options(options);
463            Ok(Arc::new(tokenizer))
464        }
465        "model" | "tiktoken" => {
466            let tokenizer = TikTokenTokenizer::from_file_auto(file_path)?.with_options(options);
467            Ok(Arc::new(tokenizer))
468        }
469        _ => Err(Error::msg(format!(
470            "Unsupported tokenizer file type: .{extension}"
471        ))),
472    }
473}
474
475// With incremental detokenization, we need to consider the final context tokens when handling the initial decode tokens.
476// This is the initial offset from the end of the context that we start decoding from.
477// Both Huggingface TGI and vLLM use this same value.
478// See: https://github.com/huggingface/text-generation-inference/blob/24c2bff65924801ddf90fa24fcc72752d4f45538/server/text_generation_server/models/mamba.py#L169
479// and https://github.com/vllm-project/vllm/blob/da2705198fa19030a25d0bea437f7be6547d47d4/vllm/transformers_utils/detokenizer_utils.py#L51
480const INITIAL_INCREMENTAL_DETOKENIZATION_OFFSET: usize = 5;
481
482/// DecodeStream will keep the state necessary to produce individual chunks of
483/// strings given an input stream of token_ids.
484///
485/// This is necessary because decoding in general cannot achieve that since strings
486/// depend on surrounding ids to provide a valid string. Typically stripping extra spaces.
487pub struct DecodeStream {
488    /// The tokenizer used to decode token_ids
489    tokenizer: Arc<dyn traits::Tokenizer>,
490
491    skip_special_tokens: bool,
492    /// A temporary buffer of the necessary token_ids needed
493    /// to produce valid string chunks.
494    /// This typically contains 3 parts:
495    ///  - read
496    ///  - prefix
497    ///  - rest
498    ///
499    /// Read is the bit necessary to surround the prefix
500    /// so decoding the whole ids produces a valid prefix.
501    /// Prefix is the previously produced string, kept around to trim off of
502    /// the next valid chunk
503    all_token_ids: Vec<u32>,
504
505    prefix_offset: usize,
506
507    read_offset: usize,
508
509    /// Whether any generated text has already been returned to the caller.
510    has_emitted: bool,
511}
512
513impl DecodeStream {
514    pub fn new(
515        tokenizer: Arc<dyn traits::Tokenizer>,
516        prompt_token_ids: &[TokenIdType],
517        skip_special_tokens: bool,
518    ) -> Self {
519        // Earlier prompt tokens are never read by incremental decoding. Keep the
520        // same context suffix and rebase its offsets before copying it.
521        let context_start = prompt_token_ids
522            .len()
523            .saturating_sub(INITIAL_INCREMENTAL_DETOKENIZATION_OFFSET);
524        let prompt_token_ids = prompt_token_ids[context_start..].to_vec();
525        let num_input_tokens = prompt_token_ids.len();
526        Self {
527            tokenizer,
528            skip_special_tokens,
529            all_token_ids: prompt_token_ids,
530            prefix_offset: 0,
531            read_offset: num_input_tokens,
532            has_emitted: false,
533        }
534    }
535
536    /// Step appends a token_id to the internal state and tries to produce a text chunk.
537    ///
538    /// Implementation directly copied from Huggingface's TGI:
539    /// https://github.com/huggingface/text-generation-inference/blob/24c2bff65924801ddf90fa24fcc72752d4f45538/server/text_generation_server/models/model.py#L144
540    ///
541    /// Returning `None` means the given id is not enough to produce a chunk.
542    /// This typically happens with `byte_fallback` options where some tokens do not
543    /// represent valid UTF-8, and only follow-up token_ids will help produce
544    /// a valid chunk.
545    ///
546    /// An error is terminal for this stream because the token may already have
547    /// been appended to its internal state.
548    pub fn step(&mut self, id: u32) -> Result<Option<String>> {
549        self.all_token_ids.push(id);
550
551        if self.tokenizer.has_unstable_suffix(
552            &self.all_token_ids[self.read_offset..],
553            self.skip_special_tokens,
554        ) {
555            return Ok(None);
556        }
557        self.decode_pending(false)
558    }
559
560    /// Decode the remaining suffix once no further tokens can reinterpret it.
561    /// Call this at end-of-input and append its output after all `step` chunks.
562    /// Dropping the stream without finishing discards any buffered text.
563    pub fn finish(&mut self) -> Result<Option<String>> {
564        self.decode_pending(true)
565    }
566
567    fn decode_pending(&mut self, finishing: bool) -> Result<Option<String>> {
568        if self.read_offset == self.all_token_ids.len() {
569            return Ok(None);
570        }
571
572        let prefix_text: String = self
573            .tokenizer
574            .decode(
575                &self.all_token_ids[self.prefix_offset..self.read_offset],
576                self.skip_special_tokens,
577            )?
578            .into();
579
580        let new_result = self.tokenizer.decode(
581            &self.all_token_ids[self.prefix_offset..],
582            self.skip_special_tokens,
583        )?;
584
585        let new_text = new_result.as_str();
586        let is_partial = new_result.is_partial() && !finishing;
587
588        // Once generated text has been returned, decoding must remain append-only.
589        // A complete rewrite cannot be repaired after the caller has seen the old text.
590        if self.has_emitted && !is_partial && !new_text.starts_with(prefix_text.as_str()) {
591            return Err(Error::msg(
592                "incremental decoding rewrote already emitted text",
593            ));
594        }
595
596        if new_text.len() > prefix_text.len() && !is_partial {
597            let requested_split = prefix_text.len();
598            let split = if self.has_emitted {
599                // starts_with() guarantees this is a character boundary and preserves
600                // everything already returned to the caller.
601                requested_split
602            } else {
603                // Rewinding into prompt context is safe because prompt text was not
604                // returned by this stream.
605                new_text.floor_char_boundary(requested_split)
606            };
607
608            let emitted = new_text[split..].to_string();
609
610            self.prefix_offset = self.read_offset;
611            self.read_offset = self.all_token_ids.len();
612            self.has_emitted = true;
613
614            Ok(Some(emitted))
615        } else {
616            Ok(None)
617        }
618    }
619}
620
621#[cfg(test)]
622mod decode_stream_unicode_tests {
623    use super::{DecodeResult, DecodeStream, Encoding, Result, TokenIdType};
624    use std::sync::Arc;
625
626    struct RewritingTokenizer {
627        prefix_text: &'static str,
628        rewritten_text: &'static str,
629        prefix_is_partial: bool,
630    }
631
632    impl super::traits::Encoder for RewritingTokenizer {
633        fn encode(&self, _input: &str) -> Result<Encoding> {
634            Ok(Encoding::Sp(vec![]))
635        }
636
637        fn encode_batch(&self, _inputs: &[&str]) -> Result<Vec<Encoding>> {
638            Ok(vec![])
639        }
640    }
641
642    impl super::traits::Decoder for RewritingTokenizer {
643        fn decode(
644            &self,
645            token_ids: &[TokenIdType],
646            _skip_special_tokens: bool,
647        ) -> Result<DecodeResult> {
648            let result = match token_ids.len() {
649                1 if self.prefix_is_partial => DecodeResult::Partial(self.prefix_text.to_string()),
650                1 => DecodeResult::Complete(self.prefix_text.to_string()),
651                2 => DecodeResult::Complete(self.rewritten_text.to_string()),
652                _ => DecodeResult::Complete(String::new()),
653            };
654            Ok(result)
655        }
656    }
657
658    impl super::traits::Tokenizer for RewritingTokenizer {}
659
660    #[test]
661    fn prompt_suffix_preserves_decode_inputs_and_output() {
662        let tokenizer: Arc<dyn super::traits::Tokenizer> = Arc::new(
663            super::HuggingFaceTokenizer::from_file(concat!(
664                env!("CARGO_MANIFEST_DIR"),
665                "/tests/data/minimal-bpe/tokenizer.json"
666            ))
667            .unwrap(),
668        );
669        for prompt_len in [0usize, 1, 4, 5, 6, 775_168] {
670            let prompt: Vec<_> = (0..prompt_len)
671                .map(|index| 1 + (index % 22) as u32)
672                .collect();
673            for skip_special_tokens in [false, true] {
674                let mut stream = DecodeStream::new(tokenizer.clone(), &prompt, skip_special_tokens);
675                // Reconstruct the previous full-prompt state as a parity oracle.
676                let mut full = DecodeStream {
677                    tokenizer: tokenizer.clone(),
678                    skip_special_tokens,
679                    all_token_ids: prompt.clone(),
680                    prefix_offset: prompt_len
681                        .saturating_sub(super::INITIAL_INCREMENTAL_DETOKENIZATION_OFFSET),
682                    read_offset: prompt_len,
683                    has_emitted: false,
684                };
685                assert!(stream.all_token_ids.capacity() <= 5);
686                for token in [5, 9, 12, 12, 13, 0, 1, 17, 13, 14, 12, 8, 2] {
687                    assert_eq!(
688                        &stream.all_token_ids[stream.prefix_offset..stream.read_offset],
689                        &full.all_token_ids[full.prefix_offset..full.read_offset],
690                    );
691                    assert_eq!(
692                        &stream.all_token_ids[stream.prefix_offset..],
693                        &full.all_token_ids[full.prefix_offset..],
694                    );
695                    let actual = stream.step(token).map_err(|error| error.to_string());
696                    let expected = full.step(token).map_err(|error| error.to_string());
697                    assert_eq!(actual, expected, "prompt length {prompt_len}");
698                    if actual.is_err() {
699                        break;
700                    }
701                }
702            }
703        }
704    }
705
706    #[test]
707    fn allows_boundary_recovery_before_generated_text_is_emitted() {
708        for (prefix_text, rewritten_text, expected) in [
709            ("㺄馉凓鄗\u{FFFD}", "㺄馉凓鄗𫷲", "𫷲"),
710            (
711                "JUnitworkflow Completion intuition\u{FFFD}",
712                "JUnitworkflow Completion intuition𝟙",
713                "𝟙",
714            ),
715        ] {
716            let tokenizer: Arc<dyn super::traits::Tokenizer> = Arc::new(RewritingTokenizer {
717                prefix_text,
718                rewritten_text,
719                prefix_is_partial: true,
720            });
721            let mut stream = DecodeStream::new(tokenizer, &[1], false);
722
723            assert_eq!(stream.step(2).unwrap(), Some(expected.to_string()));
724        }
725    }
726
727    #[test]
728    fn errors_when_incremental_decode_rewrites_emitted_text() {
729        for (prefix_text, rewritten_text) in [
730            ("abcde", "abcdXY"),
731            ("abcde", "abcdX"),
732            ("abcde", "abcd"),
733            ("㺄馉凓鄗abc", "㺄馉凓鄗𫷲"),
734            (
735                "JUnitworkflow Completion intuitionabc",
736                "JUnitworkflow Completion intuition𝟙",
737            ),
738        ] {
739            let tokenizer: Arc<dyn super::traits::Tokenizer> = Arc::new(RewritingTokenizer {
740                prefix_text,
741                rewritten_text,
742                prefix_is_partial: false,
743            });
744            let mut stream = DecodeStream::new(tokenizer, &[], false);
745
746            assert_eq!(stream.step(1).unwrap(), Some(prefix_text.to_string()));
747
748            let error = stream.step(2).unwrap_err();
749            assert!(error.to_string().contains("already emitted text"));
750        }
751    }
752
753    #[test]
754    fn emits_suffix_when_incremental_decode_preserves_emitted_text() {
755        let tokenizer: Arc<dyn super::traits::Tokenizer> = Arc::new(RewritingTokenizer {
756            prefix_text: "abcde",
757            rewritten_text: "abcdeXY",
758            prefix_is_partial: false,
759        });
760        let mut stream = DecodeStream::new(tokenizer, &[], false);
761
762        assert_eq!(stream.step(1).unwrap(), Some("abcde".to_string()));
763        assert_eq!(stream.step(2).unwrap(), Some("XY".to_string()));
764    }
765}
766
767/// Maintains state for an ongoing sequence of tokens and their decoded text
768pub struct Sequence {
769    /// Encodes text -> token_ids
770    tokenizer: Tokenizer,
771
772    /// The current sequence of token ids
773    token_ids: Vec<TokenIdType>,
774
775    /// The position in the current sequence the last decoded token completed
776    prefix_offset: usize,
777
778    /// Current position in the sequence
779    read_offset: usize,
780}
781
782impl std::fmt::Debug for Sequence {
783    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
784        f.debug_struct("Sequence")
785            .field("tokenizer", &"Arc<dyn Tokenizer>")
786            .field(
787                "token_ids",
788                &format_args!("{}", {
789                    let token_ids = self.token_ids();
790                    if token_ids.len() <= 20 {
791                        format!("{:?}", token_ids)
792                    } else {
793                        let first_ten = &token_ids[..10];
794                        let last_ten = &token_ids[token_ids.len() - 10..];
795                        format!("{:?} ... {:?}", first_ten, last_ten)
796                    }
797                }),
798            )
799            .field("prefix_offset", &self.prefix_offset)
800            .field("read_offset", &self.read_offset)
801            .field("token count", &self.token_ids.len())
802            .finish()
803    }
804}
805
806impl Sequence {
807    pub fn new(tokenizer: Tokenizer) -> Self {
808        Self {
809            tokenizer,
810            token_ids: Vec::new(),
811            prefix_offset: 0,
812            read_offset: 0,
813        }
814    }
815
816    pub fn is_empty(&self) -> bool {
817        self.token_ids.is_empty()
818    }
819
820    pub fn len(&self) -> usize {
821        self.token_ids.len()
822    }
823
824    pub fn clear(&mut self) {
825        self.token_ids.clear();
826        self.prefix_offset = 0;
827        self.read_offset = 0;
828    }
829
830    pub fn append_text(&mut self, input: &str) -> Result<()> {
831        // let tokenizer = self.tokenizer.read().map_err(|err| {
832        //     Error::msg(format!("Failed to acquire read lock on tokenizer: {}", err))
833        // })?;
834
835        let encoding = self.tokenizer.encode(input)?;
836        self.token_ids.extend(encoding.token_ids());
837        Ok(())
838    }
839
840    // Based on
841    // https://github.com/huggingface/text-generation-inference/blob/v0.9.4/server/text_generation_server/models/model.py#L62C9-L62C15
842    // under Apache 2.0 license
843    pub fn append_token_id(&mut self, token_id: TokenIdType) -> Result<String> {
844        self.token_ids.push(token_id);
845        // log::trace!("pushed token_id: {}", token_id);
846
847        let prefix_text: String = self
848            .tokenizer
849            .decode(&self.token_ids[self.prefix_offset..self.read_offset], false)?
850            .into();
851
852        let new_result = self
853            .tokenizer
854            .decode(&self.token_ids[self.prefix_offset..], false)?;
855
856        let new_text = new_result.as_str();
857
858        // if the end character of the previous returned sequence is a multi-byte character
859        // then we can not split the text on that byte offset, so we roll back to the byte offset
860        // of the start of that character
861        let mut prefix_text_len = prefix_text.len();
862        while !new_text.is_char_boundary(prefix_text_len) && prefix_text_len > 0 {
863            prefix_text_len -= 1;
864        }
865        let prefix_text_len = prefix_text_len;
866
867        if new_text.len() > prefix_text.len() {
868            if new_result.is_partial() {
869                return Ok("".to_string());
870            } else {
871                // shift and update the state
872                let new_text = new_text[prefix_text_len..]
873                    .to_string()
874                    .replace('\u{FFFD}', "");
875                self.prefix_offset = self.read_offset;
876                self.read_offset = self.token_ids.len();
877                return Ok(new_text);
878            }
879        }
880
881        Ok("".to_string())
882    }
883
884    pub fn tokenizer(&self) -> Tokenizer {
885        self.tokenizer.clone()
886    }
887
888    pub fn token_ids(&self) -> &[TokenIdType] {
889        &self.token_ids
890    }
891
892    pub fn text(&self) -> Result<String> {
893        // let tokenizer = self.tokenizer.read().map_err(|err| {
894        //     Error::msg(format!("Failed to acquire read lock on tokenizer: {}", err))
895        // })?;
896        Ok(self.tokenizer.decode(&self.token_ids, false)?.into())
897    }
898}
899
900/// The output conditions/values of a SequenceDecoder::add_token_id operation.
901/// Result of decoding a token, indicating whether text was produced or a stop condition was met
902pub enum SequenceDecoderOutput {
903    /// The text for the appended token_id
904    Text(String),
905
906    /// A sequence of token_ids has been partially matched a stop sequence, so the text is held
907    /// until either a match or a divergence
908    Held,
909
910    /// Indicates that a stop sequence has been matched and the decoder is stopped.
911    /// Subsequent calls to append_token_id will return an error
912    Stopped,
913
914    /// Indicates that a stop token_id has been matched and the decoder is stopped.
915    /// Subsequent calls to append_token_id will return an error
916    /// The text for the stop token_id is returned
917    StoppedWithText(String),
918}
919
920/// A Sequence for decoding a stream of token ids into text and detecting stop sequences.
921/// A stop sequence is either a matching token_id or a sequence of texts/strings which match.
922/// Matches happen first at the token-level, then at the sequence-level. Hidden takes precedence
923/// over visible. For example, if you put the same token_id in both `stop_token_ids_visible` and
924/// `stop_token_ids_hidden`, the token_id will be treated as hidden.
925#[derive(Debug)]
926pub struct StopSequenceDecoder {
927    // The current sequence of token ids
928    sequence: Sequence,
929
930    // Stop Tokens - the presence of any one of these should trigger a stop
931    // If found, the text for the matched token will be returned
932    stop_token_ids_visible: Vec<TokenIdType>,
933
934    // Stop Tokens - the presence of any one of these should trigger a stop
935    // If found, the text for the matched token will NOT be returned
936    stop_token_ids_hidden: Vec<TokenIdType>,
937
938    // Stop Words - the presence of any one of these should trigger a stop
939    // If found, the text for the matched token will be returned
940    #[allow(dead_code)]
941    stop_sequences_visible: Vec<String>,
942
943    // Stop Words - the presence of any one of these should trigger a stop
944    // If found, the text for the matched token will NOT be returned
945    stop_sequences_hidden: Vec<String>,
946
947    // If the decoder has observed and returned a stop SequenceDecoderOutput,
948    // futhur calls to append_token_id will return an error
949    stopped: bool,
950
951    // text jail - if a partial stop sequence is being observed, we hold/jail the text
952    // until either the stop sequence is matched or the sequence is reset by a divergence
953    state: String,
954}
955
956impl StopSequenceDecoder {
957    /// Builder object for configurating a StopSequenceDecoder
958    pub fn builder(tokenizer: Tokenizer) -> StopSequenceDecoderBuilder {
959        StopSequenceDecoderBuilder::new(tokenizer)
960    }
961
962    /// Add a token_id to the sequence and return the SequenceDecoderOutput
963    pub fn append_token_id(&mut self, token_id: TokenIdType) -> Result<SequenceDecoderOutput> {
964        if self.stopped {
965            return Err(Error::msg("Decoder is stopped"));
966        }
967
968        // update the sequence
969        let text = self.sequence.append_token_id(token_id)?;
970
971        // append the text to the state
972        self.state.push_str(text.as_str());
973
974        let mut stop: bool = false;
975        let mut visible: bool = false;
976
977        if self.stop_token_ids_visible.contains(&token_id) {
978            stop = true;
979            visible = true;
980        }
981
982        if self.stop_token_ids_hidden.contains(&token_id) {
983            stop = true;
984            visible = false;
985        }
986
987        if stop {
988            self.stopped = true;
989            let state = std::mem::take(&mut self.state);
990            if visible {
991                return Ok(SequenceDecoderOutput::StoppedWithText(state));
992            }
993            return Ok(SequenceDecoderOutput::Stopped);
994        }
995
996        // determine if state matches any of the stop sequences
997        for stop_sequence in self.stop_sequences_hidden.iter() {
998            if stop_sequence.starts_with(&self.state) {
999                if stop_sequence == &self.state {
1000                    // on matched stop sequence, we do NOT return the jailed stop sequence
1001                    self.stopped = true;
1002                    return Ok(SequenceDecoderOutput::Stopped);
1003                } else {
1004                    return Ok(SequenceDecoderOutput::Held);
1005                }
1006            }
1007        }
1008
1009        let state = std::mem::take(&mut self.state);
1010        Ok(SequenceDecoderOutput::Text(state))
1011    }
1012
1013    pub fn is_empty(&self) -> bool {
1014        self.sequence.token_ids.is_empty()
1015    }
1016
1017    pub fn len(&self) -> usize {
1018        self.sequence.token_ids.len()
1019    }
1020
1021    pub fn is_complete(&self) -> bool {
1022        self.stopped
1023    }
1024
1025    pub fn close(&mut self) {
1026        self.stopped = true;
1027    }
1028}
1029
1030pub struct StopSequenceDecoderBuilder {
1031    tokenizer: Tokenizer,
1032    stop_token_ids_visible: Vec<TokenIdType>,
1033    stop_token_ids_hidden: Vec<TokenIdType>,
1034    stop_sequences_visible: Vec<String>,
1035    stop_sequences_hidden: Vec<String>,
1036}
1037
1038impl StopSequenceDecoderBuilder {
1039    pub fn new(tokenizer: Tokenizer) -> Self {
1040        Self {
1041            tokenizer,
1042            stop_token_ids_visible: Vec::new(),
1043            stop_token_ids_hidden: Vec::new(),
1044            stop_sequences_visible: Vec::new(),
1045            stop_sequences_hidden: Vec::new(),
1046        }
1047    }
1048
1049    /// Adds a visible stop token id to the StopSequenceDecoder
1050    pub fn add_stop_token_id_visible(mut self, token_id: TokenIdType) -> Self {
1051        self.stop_token_ids_visible.push(token_id);
1052        self
1053    }
1054
1055    /// Adds a list of visible stop token ids to the StopSequenceDecoder
1056    /// Each token_id is added as for an individual match
1057    pub fn add_stop_token_ids_visible(mut self, token_ids: &[TokenIdType]) -> Self {
1058        self.stop_token_ids_visible.extend(token_ids);
1059        self
1060    }
1061
1062    /// Adds a hidden stop token id to the StopSequenceDecoder
1063    pub fn add_stop_token_id_hidden(mut self, token_id: TokenIdType) -> Self {
1064        self.stop_token_ids_hidden.push(token_id);
1065        self
1066    }
1067
1068    /// Adds a list of hidden stop token ids to the StopSequenceDecoder
1069    /// Each token_id is added as for an individual match
1070    pub fn add_stop_token_ids_hidden(mut self, token_ids: &[TokenIdType]) -> Self {
1071        self.stop_token_ids_hidden.extend(token_ids);
1072        self
1073    }
1074
1075    pub fn add_stop_sequence_visible(mut self, text: &str) -> Self {
1076        self.stop_sequences_visible.push(text.to_string());
1077        self
1078    }
1079
1080    pub fn add_stop_sequences_visible(mut self, strings: &[&str]) -> Self {
1081        self.stop_sequences_visible
1082            .extend(strings.iter().map(|text| text.to_string()));
1083        self
1084    }
1085
1086    pub fn add_stop_sequence_hidden(mut self, text: &str) -> Self {
1087        self.stop_sequences_hidden.push(text.to_string());
1088        self
1089    }
1090
1091    pub fn add_stop_sequences_hidden(mut self, strings: &[&str]) -> Self {
1092        self.stop_sequences_hidden
1093            .extend(strings.iter().map(|text| text.to_string()));
1094        self
1095    }
1096
1097    pub fn build(self) -> Result<StopSequenceDecoder> {
1098        Ok(StopSequenceDecoder {
1099            sequence: Sequence::new(self.tokenizer.clone()),
1100            stop_token_ids_visible: self.stop_token_ids_visible,
1101            stop_token_ids_hidden: self.stop_token_ids_hidden,
1102            stop_sequences_visible: self.stop_sequences_visible,
1103            stop_sequences_hidden: self.stop_sequences_hidden,
1104            stopped: false,
1105            state: String::new(),
1106        })
1107    }
1108}