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