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