Skip to main content

dynamo_tokenizers/cache/
l1.rs

1// SPDX-FileCopyrightText: Copyright (c) 2025-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0
3//
4// SPDX-FileCopyrightText: Copyright (c) 2024 Simo Lin, Chang Su, Keyang Ru (llm-tokenizer authors)
5//
6// Portions adapted from sgl-project/llm-tokenizer v1.3.2 (Apache-2.0).
7// Upstream: https://github.com/lightseekorg/smg
8// Modifications: removed `add_special_tokens` plumbing (Dynamo's Encoder has no such
9// flag), bound `insert_at_boundaries` on `Encoder` rather than `Tokenizer`, retargeted
10// imports onto `crate::traits`.
11
12//! L1 Cache: Special-token boundary prefix cache
13//!
14//! Caches tokenization results at ALL special token boundaries.
15//! Special tokens (like `<|im_start|>`, `<|im_end|>`) are atomic in BPE tokenizers
16//! (`special: true, normalized: false`), making them the ONLY safe split points that
17//! guarantee correctness: `tokenize(prefix) + tokenize(suffix) == tokenize(prefix + suffix)`.
18//!
19//! No fallback to whitespace/punctuation — better to not cache than risk corruption.
20//!
21//! Storage and eviction are delegated to a weighted [`moka`] `sync::Cache` (W-TinyLFU):
22//! entries are keyed by the blake3 digest of a namespace and `input[0..boundary]`,
23//! weighed by their resident token-vector bytes, so the byte budget is enforced — and recency/frequency
24//! tracked — by moka rather than by hand.
25
26use std::{
27    hash::BuildHasherDefault,
28    mem::size_of_val,
29    sync::{
30        Arc,
31        atomic::{AtomicU64, Ordering},
32    },
33};
34
35use aho_corasick::AhoCorasick;
36use moka::sync::Cache;
37use rustc_hash::FxHasher;
38
39use crate::{TokenIdType, traits::Encoder};
40
41/// Hash type for cache keys
42type Blake3Hash = [u8; 32];
43
44/// First byte hashed for a segment key (see [`L1Cache::segment_key`]).
45const SEGMENT_KEY_TAG: u8 = 0xFF;
46
47/// Keys are blake3 digests (already uniformly distributed), so a fast non-DoS-resistant
48/// hasher suffices — no need for the default SipHash.
49type PrefixHasher = BuildHasherDefault<FxHasher>;
50
51/// Weighted W-TinyLFU cache mapping a prefix's blake3 digest to its cumulative tokens.
52type PrefixCache = Cache<Blake3Hash, CachedPrefix, PrefixHasher>;
53
54#[derive(Clone)]
55struct CachedPrefix {
56    namespace: Blake3Hash,
57    tokens: Arc<[TokenIdType]>,
58}
59
60impl CachedPrefix {
61    fn weight(&self) -> u32 {
62        size_of_val(self.tokens.as_ref()).min(u32::MAX as usize) as u32
63    }
64}
65
66/// Shared storage and eviction budget for any number of cached tokenizers.
67///
68/// Clones share the same entries and capacity. The budget counts token-ID payloads,
69/// excluding keys, metadata, and tokenizer objects. Moka enforces it on a best-effort
70/// basis through deferred maintenance; it is not a process-memory limit.
71#[derive(Clone)]
72pub struct SharedTokenizerCache {
73    cache: PrefixCache,
74}
75
76/// Storage statistics after pending maintenance. Concurrent writes can change them.
77#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
78pub struct SharedTokenizerCacheStats {
79    pub entries: usize,
80    pub memory_bytes: usize,
81}
82
83impl SharedTokenizerCache {
84    pub fn new(max_memory_bytes: usize) -> Self {
85        Self {
86            cache: Cache::builder()
87                .max_capacity(max_memory_bytes as u64)
88                .weigher(|_key: &Blake3Hash, entry: &CachedPrefix| entry.weight())
89                .build_with_hasher(PrefixHasher::default()),
90        }
91    }
92
93    /// Combined token-ID byte budget for all namespaces.
94    pub fn max_memory_bytes(&self) -> usize {
95        self.cache.policy().max_capacity().expect("capacity is set") as usize
96    }
97
98    /// Combined storage usage for all namespaces.
99    pub fn stats(&self) -> SharedTokenizerCacheStats {
100        self.cache.run_pending_tasks();
101        SharedTokenizerCacheStats {
102            entries: self.cache.entry_count() as usize,
103            memory_bytes: self.cache.weighted_size() as usize,
104        }
105    }
106
107    fn namespace_stats(&self, namespace: &Blake3Hash) -> SharedTokenizerCacheStats {
108        self.cache.run_pending_tasks();
109        let mut stats = SharedTokenizerCacheStats::default();
110        for (_, entry) in &self.cache {
111            if &entry.namespace == namespace {
112                stats.entries += 1;
113                stats.memory_bytes += entry.weight() as usize;
114            }
115        }
116        stats
117    }
118}
119
120fn namespace_hasher(namespace: &[u8]) -> blake3::Hasher {
121    let mut hasher = blake3::Hasher::new();
122    // Frame the namespace so its end cannot be confused with the prefix's start.
123    hasher.update(&(namespace.len() as u64).to_le_bytes());
124    hasher.update(namespace);
125    hasher
126}
127
128/// Request-local lookup result. The deepest digest can differ from the matched key.
129pub(super) struct PrefixMatch {
130    pub(super) tokens: Arc<[TokenIdType]>,
131    pub(super) prefix_len: usize,
132    deepest_boundary: usize,
133    deepest_hash: Option<Blake3Hash>,
134}
135
136/// A miss retains lookup's boundary hashes for population without another input scan.
137pub(super) enum PrefixLookup {
138    Hit(PrefixMatch),
139    Miss(Vec<(usize, Blake3Hash)>),
140}
141
142/// Hash sorted boundary prefixes incrementally.
143fn hash_prefixes<'a>(
144    mut hasher: blake3::Hasher,
145    input: &'a str,
146    boundaries: &'a [usize],
147) -> impl Iterator<Item = (usize, Blake3Hash)> + 'a {
148    let mut last_pos = 0;
149    boundaries.iter().map(move |&boundary_pos| {
150        hasher.update(&input.as_bytes()[last_pos..boundary_pos]);
151        last_pos = boundary_pos;
152        (boundary_pos, *hasher.finalize().as_bytes())
153    })
154}
155
156/// Positions immediately after each special-token occurrence in `text`.
157///
158/// Callers supply token strings that the inner tokenizer treats as atomic, so a boundary
159/// immediately after a selected occurrence is a safe split point:
160/// `tokenize(prefix) + tokenize(suffix) == tokenize(prefix + suffix)`. The overlapping scan
161/// is safe only when registered special-token occurrences cannot overlap; construction
162/// screens out other sets with [`first_unsafe_overlap`]. A boundary at the end of the input
163/// is omitted because there is no suffix to encode.
164fn boundaries_with(text: &str, matcher: &AhoCorasick) -> Vec<usize> {
165    let mut boundaries: Vec<usize> = matcher
166        .find_overlapping_iter(text)
167        .map(|m| m.end())
168        .filter(|&end| end < text.len())
169        .collect();
170    boundaries.sort_unstable();
171    boundaries.dedup();
172    boundaries
173}
174
175fn has_nontrivial_self_overlap(token: &str) -> bool {
176    let bytes = token.as_bytes();
177    (1..bytes.len()).any(|overlap| bytes[bytes.len() - overlap..] == bytes[..overlap])
178}
179
180fn tokens_can_overlap(a: &str, b: &str) -> bool {
181    if a.contains(b) || b.contains(a) {
182        return true;
183    }
184
185    let a = a.as_bytes();
186    let b = b.as_bytes();
187    let max_overlap = a.len().min(b.len());
188    (1..max_overlap).any(|overlap| {
189        a[a.len() - overlap..] == b[..overlap] || b[b.len() - overlap..] == a[..overlap]
190    })
191}
192
193/// Returns the first pair of special tokens whose occurrences can overlap.
194///
195/// [`boundaries_with`] reports the end of *every* occurrence of *every* special token.
196/// That equals the tokenizer's own segmentation only when occurrences cannot overlap;
197/// otherwise a reported boundary can land strictly inside the span the tokenizer actually
198/// consumed, and splitting there breaks the module invariant
199/// `tokenize(prefix) + tokenize(suffix) == tokenize(prefix + suffix)`.
200pub(super) fn first_unsafe_overlap(special_tokens: &[String]) -> Option<(&str, &str)> {
201    for (index, token) in special_tokens.iter().enumerate() {
202        if token.is_empty() {
203            continue;
204        }
205        if has_nontrivial_self_overlap(token) {
206            return Some((token, token));
207        }
208        for other in &special_tokens[index + 1..] {
209            if !other.is_empty() && token != other && tokens_can_overlap(token, other) {
210                return Some((token, other));
211            }
212        }
213    }
214
215    None
216}
217
218/// Test-only reference: build a one-off automaton and find boundaries. Production goes
219/// through [`L1Cache::boundaries`], which reuses a process-once automaton.
220#[cfg(test)]
221fn find_special_token_boundaries(text: &str, special_tokens: &[&str]) -> Vec<usize> {
222    if special_tokens.is_empty() {
223        return Vec::new();
224    }
225    let matcher = AhoCorasick::new(special_tokens)
226        .expect("special tokens form a valid Aho-Corasick automaton");
227    boundaries_with(text, &matcher)
228}
229
230/// Optional per-event observer. `on_hit` runs after each cache hit, `on_miss`
231/// after each miss — wired by `CachedTokenizer::with_observer` to push events
232/// straight into Prometheus counters without a periodic sampling step.
233pub type CacheEventFn = Arc<dyn Fn() + Send + Sync>;
234
235/// L1 cache: prefix matching at special-token boundaries, backed by a weighted W-TinyLFU
236/// [`moka`] cache that owns storage, recency/frequency tracking, and eviction. Hit/miss
237/// counts (our notion of a *prefix* hit) are tracked separately for metrics.
238pub struct L1Cache {
239    cache: SharedTokenizerCache,
240    shared: bool,
241    namespace: Vec<u8>,
242    namespace_hash: Blake3Hash,
243    /// Aho-Corasick automaton over the special tokens, built once at construction (`None`
244    /// when there are no special tokens). Lets boundary detection be a single pass.
245    matcher: Option<AhoCorasick>,
246    hits: AtomicU64,
247    misses: AtomicU64,
248    on_hit: Option<CacheEventFn>,
249    on_miss: Option<CacheEventFn>,
250}
251
252impl L1Cache {
253    /// `special_tokens` is the atomic special-token set whose boundaries the cache splits
254    /// at; an empty set leaves L1 inert (no boundaries, no entries).
255    pub fn new(max_memory: usize, special_tokens: Vec<String>) -> Self {
256        Self {
257            shared: false,
258            ..Self::new_with_cache(SharedTokenizerCache::new(max_memory), special_tokens, b"")
259        }
260    }
261
262    /// Use shared storage. Equal namespaces must describe identical tokenizer behavior.
263    pub fn new_with_cache(
264        cache: SharedTokenizerCache,
265        mut special_tokens: Vec<String>,
266        namespace: &[u8],
267    ) -> Self {
268        special_tokens.retain(|token| !token.is_empty());
269
270        // Build the boundary automaton once; `None` when there are no special tokens.
271        let matcher = (!special_tokens.is_empty()).then(|| {
272            AhoCorasick::new(&special_tokens)
273                .expect("special tokens form a valid Aho-Corasick automaton")
274        });
275
276        Self {
277            cache,
278            shared: true,
279            namespace: namespace.to_vec(),
280            namespace_hash: *namespace_hasher(namespace).finalize().as_bytes(),
281            matcher,
282            hits: AtomicU64::new(0),
283            misses: AtomicU64::new(0),
284            on_hit: None,
285            on_miss: None,
286        }
287    }
288
289    fn hasher(&self) -> blake3::Hasher {
290        namespace_hasher(&self.namespace)
291    }
292
293    fn hash_prefix(&self, prefix: &[u8]) -> Blake3Hash {
294        let mut hasher = self.hasher();
295        hasher.update(prefix);
296        *hasher.finalize().as_bytes()
297    }
298
299    pub(super) fn insert(&self, hash: Blake3Hash, tokens: Arc<[TokenIdType]>) {
300        self.cache.cache.insert(
301            hash,
302            CachedPrefix {
303                namespace: self.namespace_hash,
304                tokens,
305            },
306        );
307    }
308
309    /// Key of one renderer segment's tokens.
310    ///
311    /// Prefix keys hash UTF-8 text, which never contains the byte `0xFF`; starting the
312    /// segment key with it keeps the two key spaces disjoint within a namespace.
313    pub(super) fn segment_key(&self, text: &str, allow_special: bool) -> Blake3Hash {
314        let mut hasher = self.hasher();
315        hasher.update(&[SEGMENT_KEY_TAG, allow_special as u8]);
316        hasher.update(text.as_bytes());
317        *hasher.finalize().as_bytes()
318    }
319
320    pub(super) fn get(&self, key: &Blake3Hash) -> Option<Arc<[TokenIdType]>> {
321        self.cache.cache.get(key).map(|entry| entry.tokens)
322    }
323
324    /// Count one lookup in the hit / miss counters and notify the observers.
325    pub(super) fn record_lookup(&self, hit: bool) {
326        if hit {
327            self.hits.fetch_add(1, Ordering::Relaxed);
328            if let Some(cb) = &self.on_hit {
329                cb();
330            }
331        } else {
332            self.misses.fetch_add(1, Ordering::Relaxed);
333            if let Some(cb) = &self.on_miss {
334                cb();
335            }
336        }
337    }
338
339    /// Install hit/miss callbacks. Replaces any previously-set observers.
340    pub fn set_observer(&mut self, on_hit: CacheEventFn, on_miss: CacheEventFn) {
341        self.on_hit = Some(on_hit);
342        self.on_miss = Some(on_miss);
343    }
344
345    /// Special-token boundaries in `text` via the process-once Aho-Corasick automaton built
346    /// at construction — a single pass over the input rather than one `str::find` sweep per
347    /// token. Empty when the cache has no special tokens.
348    fn boundaries(&self, text: &str) -> Vec<usize> {
349        match &self.matcher {
350            Some(matcher) => boundaries_with(text, matcher),
351            None => Vec::new(),
352        }
353    }
354
355    /// Try to find the longest prefix match at a special-token boundary.
356    ///
357    /// Returns `(cached_tokens, byte_offset, deepest_boundary)` if found. The caller
358    /// extends the cached tokens with a fresh encode of `input[byte_offset..]`;
359    /// `deepest_boundary` is the deepest special-token boundary in `input` (end-exclusive),
360    /// handed back so [`extend_after_match`] need not rescan the input for it.
361    pub fn longest_prefix_match(&self, input: &str) -> Option<(Arc<[TokenIdType]>, usize, usize)> {
362        match self.lookup_prefix(input) {
363            PrefixLookup::Hit(matched) => {
364                Some((matched.tokens, matched.prefix_len, matched.deepest_boundary))
365            }
366            PrefixLookup::Miss(_) => None,
367        }
368    }
369
370    /// Look up the longest cached prefix, retaining hashes for extension or population.
371    /// The returned offsets and digests must be used with this same input.
372    pub(super) fn lookup_prefix(&self, input: &str) -> PrefixLookup {
373        let lookup = self.find_prefix(input);
374        self.record_lookup(matches!(lookup, PrefixLookup::Hit(_)));
375        lookup
376    }
377
378    /// [`Self::lookup_prefix`] without counting the lookup, for a caller that counts
379    /// several as one.
380    pub(super) fn find_prefix(&self, input: &str) -> PrefixLookup {
381        let boundaries = self.boundaries(input);
382
383        if boundaries.is_empty() {
384            return PrefixLookup::Miss(Vec::new());
385        }
386
387        let prefix_hashes: Vec<_> = hash_prefixes(self.hasher(), input, &boundaries).collect();
388
389        for &(boundary_pos, hash_bytes) in prefix_hashes.iter().rev() {
390            if let Some(entry) = self.cache.cache.get(&hash_bytes) {
391                // Share cached tokens to avoid copying the prefix during lookup.
392                let &(deepest_boundary, deepest_hash) =
393                    prefix_hashes.last().expect("prefix hashes is non-empty");
394                return PrefixLookup::Hit(PrefixMatch {
395                    tokens: entry.tokens,
396                    prefix_len: boundary_pos,
397                    deepest_boundary,
398                    deepest_hash: Some(deepest_hash),
399                });
400            }
401        }
402
403        PrefixLookup::Miss(prefix_hashes)
404    }
405
406    /// Insert prefix entries at every special-token boundary (e.g. to pre-seed the cache).
407    ///
408    /// Uses incremental hashing and incremental tokenization (per-segment encode of the
409    /// delta text between adjacent boundaries) so populating N entries costs one full
410    /// re-tokenize total, split across the segments. The miss path uses
411    /// [`Self::populate_and_encode`] instead, which reuses this same work to *also* return
412    /// the full token vector (avoiding a redundant second tokenization).
413    pub fn insert_at_boundaries<E: Encoder + ?Sized>(
414        &self,
415        input: &str,
416        tokenizer: &E,
417    ) -> anyhow::Result<()> {
418        let boundaries = self.boundaries(input);
419        if boundaries.is_empty() {
420            return Ok(());
421        }
422        self.populate_boundaries(
423            input,
424            hash_prefixes(self.hasher(), input, &boundaries),
425            tokenizer,
426        )?;
427        Ok(())
428    }
429
430    /// Miss-path encode: tokenize `input` exactly once, caching the cumulative prefix at
431    /// every special-token boundary as we go, and return the full token-id vector. This
432    /// replaces a separate full `encode` + [`Self::insert_at_boundaries`], which together
433    /// tokenized the input ~twice (once for the result, once split across segments).
434    ///
435    /// The concatenation of the per-segment encodes equals an uncached `encode(input)`
436    /// because special tokens are atomic in BPE — the same invariant the hit path relies
437    /// on. Returns token-ids only; the caller wraps them in [`crate::Encoding::Sp`].
438    pub fn populate_and_encode<E: Encoder + ?Sized>(
439        &self,
440        input: &str,
441        tokenizer: &E,
442    ) -> anyhow::Result<Vec<TokenIdType>> {
443        let boundaries = self.boundaries(input);
444        self.populate_and_encode_with_hashes(
445            input,
446            hash_prefixes(self.hasher(), input, &boundaries),
447            tokenizer,
448        )
449    }
450
451    /// Populate a miss using sorted boundary hashes, then encode the tail.
452    /// All offsets and digests must describe this same input; public callers compute
453    /// them lazily, while CachedTokenizer supplies hashes retained from lookup.
454    pub(super) fn populate_and_encode_with_hashes<E: Encoder + ?Sized>(
455        &self,
456        input: &str,
457        prefix_hashes: impl Iterator<Item = (usize, Blake3Hash)>,
458        tokenizer: &E,
459    ) -> anyhow::Result<Vec<TokenIdType>> {
460        let (mut running, tail_start) =
461            self.populate_boundaries(input, prefix_hashes, tokenizer)?;
462        if tail_start == 0 {
463            return Ok(tokenizer.encode(input)?.token_ids().to_vec());
464        }
465
466        let tail = tokenizer.encode(&input[tail_start..])?;
467        running.extend_from_slice(tail.token_ids());
468        Ok(running)
469    }
470
471    /// Tokenize each segment and cache its cumulative prefix with the supplied digest.
472    /// Return the running tokens and last boundary. Earlier entries survive later encode failures.
473    fn populate_boundaries<E: Encoder + ?Sized>(
474        &self,
475        input: &str,
476        prefix_hashes: impl Iterator<Item = (usize, Blake3Hash)>,
477        tokenizer: &E,
478    ) -> anyhow::Result<(Vec<TokenIdType>, usize)> {
479        #[cfg(debug_assertions)]
480        let mut validation_hasher = self.hasher();
481        let mut running_tokens: Vec<TokenIdType> = Vec::new();
482        let mut last_pos = 0;
483
484        for (boundary_pos, hash_bytes) in prefix_hashes {
485            #[cfg(debug_assertions)]
486            {
487                validation_hasher.update(&input.as_bytes()[last_pos..boundary_pos]);
488                debug_assert_eq!(hash_bytes, *validation_hasher.finalize().as_bytes());
489            }
490
491            // Incremental tokenization. Dynamo's Encoder has no `add_special_tokens`
492            // parameter — equivalent to upstream always passing `false` past the first
493            // segment (which is also what Dynamo's HF impl always does for the first).
494            let seg = tokenizer.encode(&input[last_pos..boundary_pos])?;
495            running_tokens.extend_from_slice(seg.token_ids());
496
497            let prefix_tokens: Arc<[TokenIdType]> = running_tokens.as_slice().into();
498            self.insert(hash_bytes, prefix_tokens);
499
500            last_pos = boundary_pos;
501        }
502
503        Ok((running_tokens, last_pos))
504    }
505
506    /// Extend the cache on a *partial* hit so the next turn of a growing conversation
507    /// hits deeper. Given the `(prefix_tokens, prefix_len, deepest_boundary)` returned by
508    /// [`longest_prefix_match`], tokenize the remaining suffix and cache the cumulative
509    /// prefix at the suffix's **deepest** special-token boundary, then return the full
510    /// merged token vector.
511    ///
512    /// Deepest-only is intentional: in an append-only conversation the next turn always
513    /// reaches the deepest boundary, so caching it bounds per-turn work to the newest
514    /// exchange; shallow/branching coverage already comes from the miss path's
515    /// [`insert_at_boundaries`]. Splitting at special-token boundaries is correctness-safe
516    /// because special tokens are atomic in BPE
517    /// (`tokenize(a) + tokenize(b) == tokenize(a + b)`).
518    ///
519    /// Note: unlike the read-only fast path, this **writes** to the cache on a hit
520    /// (one insert + possible eviction). It relies on the same best-effort memory
521    /// accounting as [`insert_at_boundaries`].
522    pub fn extend_after_match<E: Encoder + ?Sized>(
523        &self,
524        input: &str,
525        prefix_tokens: Arc<[TokenIdType]>,
526        prefix_len: usize,
527        deepest_boundary: usize,
528        tokenizer: &E,
529    ) -> anyhow::Result<Vec<TokenIdType>> {
530        self.extend_after_match_with_hash(
531            input,
532            PrefixMatch {
533                tokens: prefix_tokens,
534                prefix_len,
535                deepest_boundary,
536                deepest_hash: None,
537            },
538            tokenizer,
539        )
540    }
541
542    /// Extend a partial hit, reusing lookup's deepest digest for the new entry.
543    /// `matched` must describe this same input. The public compatibility wrapper alone
544    /// omits the digest and computes it here when an insertion is needed.
545    pub(super) fn extend_after_match_with_hash<E: Encoder + ?Sized>(
546        &self,
547        input: &str,
548        matched: PrefixMatch,
549        tokenizer: &E,
550    ) -> anyhow::Result<Vec<TokenIdType>> {
551        let PrefixMatch {
552            tokens: prefix_tokens,
553            prefix_len,
554            deepest_boundary,
555            deepest_hash,
556        } = matched;
557        // Boundaries exclude input.len(), so the trailing segment is nonempty.
558        let deepest = (deepest_boundary > prefix_len).then_some(deepest_boundary);
559
560        let Some(deepest) = deepest else {
561            let suffix_enc = tokenizer.encode(&input[prefix_len..])?;
562            // Reserve once to avoid copying the cached prefix during vector growth.
563            let mut merged = Vec::with_capacity(prefix_tokens.len() + suffix_enc.token_ids().len());
564            merged.extend_from_slice(&prefix_tokens);
565            merged.extend_from_slice(suffix_enc.token_ids());
566            return Ok(merged);
567        };
568
569        // Encode both segments first to reserve capacity without recopying the prefix.
570        let seg_a = tokenizer.encode(&input[prefix_len..deepest])?;
571        let seg_b = tokenizer.encode(&input[deepest..])?;
572        let mut cumulative = Vec::with_capacity(
573            prefix_tokens.len() + seg_a.token_ids().len() + seg_b.token_ids().len(),
574        );
575        cumulative.extend_from_slice(&prefix_tokens);
576        cumulative.extend_from_slice(seg_a.token_ids());
577
578        let hash_bytes =
579            deepest_hash.unwrap_or_else(|| self.hash_prefix(&input.as_bytes()[..deepest]));
580        debug_assert_eq!(hash_bytes, self.hash_prefix(&input.as_bytes()[..deepest]));
581
582        // Copy only the populated prefix, excluding capacity reserved for the tail.
583        let tokens: Arc<[TokenIdType]> = cumulative.as_slice().into();
584        self.insert(hash_bytes, tokens);
585
586        cumulative.extend_from_slice(seg_b.token_ids());
587        Ok(cumulative)
588    }
589
590    fn storage_stats(&self) -> SharedTokenizerCacheStats {
591        if self.shared {
592            self.cache.namespace_stats(&self.namespace_hash)
593        } else {
594            self.cache.stats()
595        }
596    }
597
598    /// Number of live entries. Shared caches scan this namespace after maintenance;
599    /// private caches use Moka's entry count. Concurrent writes can change the result.
600    pub fn len(&self) -> usize {
601        self.storage_stats().entries
602    }
603
604    pub fn is_empty(&self) -> bool {
605        if !self.shared {
606            return self.len() == 0;
607        }
608        self.cache.cache.run_pending_tasks();
609        !self
610            .cache
611            .cache
612            .iter()
613            .any(|(_, entry)| entry.namespace == self.namespace_hash)
614    }
615
616    pub fn stats(&self) -> L1CacheStats {
617        let storage = self.storage_stats();
618        let hits = self.hits.load(Ordering::Relaxed);
619        let misses = self.misses.load(Ordering::Relaxed);
620        let total_requests = hits + misses;
621
622        L1CacheStats {
623            hits,
624            misses,
625            entries: storage.entries,
626            memory_bytes: storage.memory_bytes,
627            hit_rate: if total_requests > 0 {
628                hits as f64 / total_requests as f64
629            } else {
630                0.0
631            },
632        }
633    }
634}
635
636#[derive(Debug, Clone, Default)]
637pub struct L1CacheStats {
638    pub hits: u64,
639    pub misses: u64,
640    pub entries: usize,
641    pub memory_bytes: usize,
642    pub hit_rate: f64,
643}
644
645#[cfg(test)]
646mod tests {
647    use std::sync::Arc;
648
649    use super::*;
650    use crate::{HuggingFaceTokenizer, traits::Tokenizer};
651
652    // TinyLlama: real Llama BPE with `<s>` and `</s>` as added tokens with
653    // `special: true, normalized: false` — atomic in BPE, safe boundary points.
654    const TINYLLAMA_PATH: &str = concat!(
655        env!("CARGO_MANIFEST_DIR"),
656        "/tests/data/sample-models/TinyLlama_v1.1/tokenizer.json"
657    );
658
659    const SPECIALS: &[&str] = &["<s>", "</s>"];
660
661    fn load_tokenizer() -> Arc<dyn Tokenizer> {
662        Arc::new(HuggingFaceTokenizer::from_file(TINYLLAMA_PATH).expect("load TinyLlama"))
663    }
664
665    /// An `L1Cache` over the TinyLlama [`SPECIALS`] with the given byte budget.
666    fn test_cache(max_memory: usize) -> L1Cache {
667        L1Cache::new(
668            max_memory,
669            SPECIALS.iter().map(|s| (*s).to_string()).collect(),
670        )
671    }
672
673    #[test]
674    fn prefix_hash_length_delimits_the_namespace() {
675        let storage = SharedTokenizerCache::new(1024);
676        let mut hashes = Vec::new();
677        for (namespace, prefix) in [("", "abc"), ("a", "bc"), ("ab", "c")] {
678            let cache = L1Cache::new_with_cache(storage.clone(), vec![], namespace.as_bytes());
679            let bytes = [
680                (namespace.len() as u64).to_le_bytes().as_slice(),
681                namespace.as_bytes(),
682                prefix.as_bytes(),
683            ]
684            .concat();
685            let expected = *blake3::hash(&bytes).as_bytes();
686            assert_eq!(cache.hash_prefix(prefix.as_bytes()), expected);
687            assert!(!hashes.contains(&expected));
688            hashes.push(expected);
689        }
690    }
691
692    #[test]
693    fn boundaries_are_after_each_special_token_occurrence() {
694        let input = "<s>system\nHi</s><s>user\nHello</s>";
695        let bounds = find_special_token_boundaries(input, SPECIALS);
696        // Drop the trailing boundary (==text.len()), so 3 not 4 boundaries.
697        assert_eq!(bounds.len(), 3);
698        for w in bounds.windows(2) {
699            assert!(w[0] < w[1], "boundaries must be strictly increasing");
700        }
701        assert!(bounds.iter().all(|&b| b < input.len()));
702    }
703
704    #[test]
705    fn no_special_tokens_yields_no_boundaries() {
706        assert!(find_special_token_boundaries("plain text", &[]).is_empty());
707    }
708
709    #[test]
710    fn unsafe_overlap_detects_containment_crossing_and_self_overlap() {
711        let cases = [
712            (vec!["〈|", "〈|EOS|〉"], Some(("〈|", "〈|EOS|〉"))),
713            (vec!["ab", "bc"], Some(("ab", "bc"))),
714            (vec!["|◊|"], Some(("|◊|", "|◊|"))),
715            (vec!["<s>", "<s>"], None),
716        ];
717
718        for (tokens, expected) in cases {
719            let tokens: Vec<String> = tokens.into_iter().map(String::from).collect();
720            assert_eq!(first_unsafe_overlap(&tokens), expected);
721        }
722    }
723
724    #[test]
725    fn llama_numbered_special_tokens_do_not_trigger_overlap_guard() {
726        let mut llama: Vec<String> = [
727            "<|begin_of_text|>",
728            "<|end_of_text|>",
729            "<|start_header_id|>",
730            "<|end_header_id|>",
731            "<|eot_id|>",
732        ]
733        .into_iter()
734        .map(String::from)
735        .collect();
736        llama.extend((0..251).map(|id| format!("<|reserved_special_token_{id}|>")));
737
738        assert_eq!(first_unsafe_overlap(&llama), None);
739    }
740
741    #[test]
742    fn insert_then_lookup_finds_shared_prefix() {
743        let cache = test_cache(1024 * 1024);
744        let tokenizer = load_tokenizer();
745
746        let warm = "<s>system\nYou are helpful.</s><s>user\nHi</s>";
747        cache
748            .insert_at_boundaries(warm, tokenizer.as_ref())
749            .unwrap();
750        assert!(!cache.is_empty());
751
752        let target = "<s>system\nYou are helpful.</s><s>user\nDifferent question</s>";
753        let (tokens, offset, _deepest) = cache
754            .longest_prefix_match(target)
755            .expect("shared prefix should match");
756        assert!(offset > 0);
757        assert!(!tokens.is_empty());
758    }
759
760    #[test]
761    fn miss_increments_misses_counter() {
762        let cache = test_cache(1024 * 1024);
763        assert!(
764            cache
765                .longest_prefix_match("plain text no specials")
766                .is_none()
767        );
768        assert_eq!(cache.stats().misses, 1);
769    }
770
771    #[test]
772    fn hit_increments_hits_counter() {
773        let cache = test_cache(1024 * 1024);
774        let tokenizer = load_tokenizer();
775        let warm = "<s>system\nA.</s><s>user\nB</s>";
776        cache
777            .insert_at_boundaries(warm, tokenizer.as_ref())
778            .unwrap();
779        let _ = cache.longest_prefix_match(warm);
780        assert!(cache.stats().hits >= 1);
781    }
782
783    #[test]
784    fn merge_invariant_holds_against_uncached_encode() {
785        // Load-bearing correctness check: cached prefix + fresh suffix encode must
786        // equal plain encode of the full input. Relies on `<s>`/`</s>` being atomic
787        // in TinyLlama's BPE (they are).
788        let cache = test_cache(1024 * 1024);
789        let tokenizer = load_tokenizer();
790
791        let template = "<s>system\nYou are helpful.</s><s>user\n";
792        let warm = format!("{template}First.</s>");
793        cache
794            .insert_at_boundaries(&warm, tokenizer.as_ref())
795            .unwrap();
796
797        let target = format!("{template}A completely different second question.</s>");
798        let (prefix_tokens, prefix_len, _deepest) = cache
799            .longest_prefix_match(&target)
800            .expect("should find prefix");
801
802        let suffix = &target[prefix_len..];
803        let suffix_enc = tokenizer.encode(suffix).unwrap();
804        // longest_prefix_match returns the shared `Arc<[u32]>`; copy into a Vec to append the suffix.
805        let mut merged = prefix_tokens.to_vec();
806        merged.extend_from_slice(suffix_enc.token_ids());
807
808        let plain = tokenizer.encode(&target).unwrap();
809        assert_eq!(
810            merged,
811            plain.token_ids(),
812            "merged tokens must equal plain encode"
813        );
814    }
815
816    #[test]
817    fn eviction_respects_memory_budget() {
818        // 4 KB budget — tight enough to force eviction after a few inserts.
819        let cache = test_cache(4 * 1024);
820        let tokenizer = load_tokenizer();
821        for i in 0..50 {
822            let input =
823                format!("<s>system\nPersona {i} chatty.</s><s>user\nTurn {i} content here.</s>");
824            cache
825                .insert_at_boundaries(&input, tokenizer.as_ref())
826                .unwrap();
827        }
828        let stats = cache.stats();
829        assert!(
830            stats.memory_bytes <= 4 * 1024,
831            "memory_bytes={} exceeds budget",
832            stats.memory_bytes
833        );
834    }
835
836    #[test]
837    fn concurrent_inserts_and_lookups_do_not_corrupt() {
838        use std::thread;
839
840        let cache = Arc::new(test_cache(1024 * 1024));
841        let tokenizer = load_tokenizer();
842
843        let mut handles = vec![];
844        for i in 0..10 {
845            let cache_c = cache.clone();
846            let tok = tokenizer.clone();
847            handles.push(thread::spawn(move || {
848                let input = format!("<s>system\nThread {i}.</s><s>user\nThread {i} body.</s>");
849                cache_c.insert_at_boundaries(&input, tok.as_ref()).unwrap();
850                let r = cache_c.longest_prefix_match(&input);
851                assert!(r.is_some(), "thread {i} expected match after insert");
852            }));
853        }
854        for h in handles {
855            h.join().unwrap();
856        }
857        assert!(cache.stats().memory_bytes > 0);
858        assert!(cache.stats().hits >= 10);
859    }
860
861    /// Build an append-only multi-turn conversation. `turns[i]` is the full prompt at
862    /// turn `i`: the system prompt, `i + 1` completed user/assistant exchanges, and a
863    /// diverging open user turn (no trailing special, so the deepest boundary is the
864    /// `<s>` that opens it). Each `turns[i]` shares a strictly longer `</s>`-bounded
865    /// prefix with `turns[i + 1]`.
866    fn growing_chat_turns(n: usize) -> Vec<String> {
867        let mut convo = String::from("<s>system\nYou are a helpful assistant.</s>");
868        let mut turns = Vec::with_capacity(n);
869        for i in 0..n {
870            convo.push_str(&format!(
871                "<s>user\nQuestion {i} please answer it.</s><s>assistant\nDetailed answer {i} follows here.</s>"
872            ));
873            turns.push(format!("{convo}<s>user\nFollow-up {i}"));
874        }
875        turns
876    }
877
878    #[test]
879    fn extend_on_hit_advances_match_depth_each_turn() {
880        // The load-bearing behavioral proof. Without extension the match offset is
881        // pinned at turn-1 depth (hits never insert); with extension it advances every
882        // turn, so the suffix re-tokenized per turn shrinks instead of growing.
883        let tok = load_tokenizer();
884        let turns = growing_chat_turns(5);
885
886        // EXTEND OFF: seed turn 0 via the miss path, then only look up (never insert).
887        let off = test_cache(8 * 1024 * 1024);
888        off.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
889        let pinned = off.longest_prefix_match(&turns[1]).expect("hit").1;
890        for t in &turns[1..] {
891            let (_toks, offset, _deepest) = off.longest_prefix_match(t).expect("hit");
892            assert_eq!(
893                offset, pinned,
894                "extend-off offset must stay pinned at turn-1 depth"
895            );
896        }
897
898        // EXTEND ON: each hit caches the deepest boundary, so the next turn hits deeper.
899        let on = test_cache(8 * 1024 * 1024);
900        on.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
901        let mut prev = 0usize;
902        for (i, t) in turns.iter().enumerate().skip(1) {
903            let (prefix_tokens, offset, deepest) = on.longest_prefix_match(t).expect("hit");
904            assert!(
905                offset > prev,
906                "turn {i}: extend-on offset {offset} must exceed previous {prev}"
907            );
908            prev = offset;
909
910            // Extending must also preserve byte-exact correctness vs an uncached encode.
911            let merged = on
912                .extend_after_match(t, prefix_tokens, offset, deepest, tok.as_ref())
913                .unwrap();
914            let plain = tok.encode(t).unwrap();
915            assert_eq!(
916                merged,
917                plain.token_ids(),
918                "turn {i}: extend merge must equal plain encode"
919            );
920        }
921
922        assert!(
923            prev > pinned,
924            "extend-on frontier ({prev}) must reach deeper than pinned extend-off depth ({pinned})"
925        );
926    }
927
928    #[test]
929    fn extend_on_hit_respects_budget_and_stays_correct() {
930        // Tiny budget forces eviction (and over-budget skips) while extending; every
931        // turn's encode must stay correct and memory must stay within budget.
932        let tok = load_tokenizer();
933        let cache = test_cache(4 * 1024);
934        let turns = growing_chat_turns(20);
935        cache.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
936
937        for t in &turns[1..] {
938            let merged = match cache.longest_prefix_match(t) {
939                Some((prefix_tokens, offset, deepest)) => cache
940                    .extend_after_match(t, prefix_tokens, offset, deepest, tok.as_ref())
941                    .unwrap(),
942                None => {
943                    // Full miss under eviction pressure — mirror the miss path.
944                    let enc = tok.encode(t).unwrap();
945                    cache.insert_at_boundaries(t, tok.as_ref()).unwrap();
946                    enc.token_ids().to_vec()
947                }
948            };
949            let plain = tok.encode(t).unwrap();
950            assert_eq!(
951                merged,
952                plain.token_ids(),
953                "encode must stay correct under eviction pressure"
954            );
955            assert!(
956                cache.stats().memory_bytes <= 4 * 1024,
957                "memory_bytes={} exceeds budget",
958                cache.stats().memory_bytes
959            );
960        }
961    }
962
963    #[test]
964    fn concurrent_extend_on_hit_does_not_corrupt() {
965        use std::thread;
966
967        let tok = load_tokenizer();
968        let cache = Arc::new(test_cache(8 * 1024 * 1024));
969        let turns = growing_chat_turns(8);
970        // Seed turn 0 so every thread gets at least a partial hit.
971        cache.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
972
973        let mut handles = vec![];
974        for _ in 0..8 {
975            let cache_c = cache.clone();
976            let tok_c = tok.clone();
977            let turns_c = turns.clone();
978            handles.push(thread::spawn(move || {
979                for t in &turns_c[1..] {
980                    if let PrefixLookup::Hit(matched) = cache_c.lookup_prefix(t) {
981                        let merged = cache_c
982                            .extend_after_match_with_hash(t, matched, tok_c.as_ref())
983                            .unwrap();
984                        let plain = tok_c.encode(t).unwrap();
985                        assert_eq!(
986                            merged,
987                            plain.token_ids(),
988                            "concurrent extend must stay correct"
989                        );
990                    }
991                }
992            }));
993        }
994        for h in handles {
995            h.join().unwrap();
996        }
997        assert!(cache.stats().memory_bytes > 0);
998    }
999
1000    #[test]
1001    fn extend_after_match_persists_correct_deepest_entry() {
1002        let tok = load_tokenizer();
1003        for unicode in [false, true] {
1004            let turns: Vec<_> = growing_chat_turns(3)
1005                .into_iter()
1006                .map(|t| {
1007                    if unicode {
1008                        t.replace("system", "system 世界 🦀")
1009                    } else {
1010                        t
1011                    }
1012                })
1013                .collect();
1014
1015            let cache = test_cache(8 * 1024 * 1024);
1016            cache.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
1017
1018            let PrefixLookup::Hit(matched) = cache.lookup_prefix(&turns[1]) else {
1019                panic!("partial hit on turns[1]");
1020            };
1021            let prefix_len = matched.prefix_len;
1022            let deepest_boundary = matched.deepest_boundary;
1023            assert!(deepest_boundary > prefix_len);
1024            assert_eq!(
1025                matched.deepest_hash,
1026                Some(cache.hash_prefix(&turns[1].as_bytes()[..deepest_boundary]))
1027            );
1028            assert_ne!(
1029                matched.deepest_hash,
1030                Some(cache.hash_prefix(&turns[1].as_bytes()[..prefix_len]))
1031            );
1032            let entries_before = cache.stats().entries;
1033
1034            let _merged = cache
1035                .extend_after_match_with_hash(&turns[1], matched, tok.as_ref())
1036                .unwrap();
1037
1038            assert_eq!(
1039                cache.stats().entries,
1040                entries_before + 1,
1041                "extend must persist exactly one (deepest) entry"
1042            );
1043
1044            let deepest = find_special_token_boundaries(&turns[1], SPECIALS)
1045                .into_iter()
1046                .rev()
1047                .find(|&b| b > prefix_len)
1048                .expect("a deeper boundary must exist in the appended turn");
1049            assert_eq!(
1050                deepest_boundary, deepest,
1051                "longest_prefix_match must return the deepest boundary used by extend"
1052            );
1053
1054            let (saved_tokens, saved_offset, _deepest) = cache
1055                .longest_prefix_match(&turns[1])
1056                .expect("hit after extend");
1057            assert_eq!(
1058                saved_offset, deepest,
1059                "lookup must now hit at the just-saved deepest boundary"
1060            );
1061            let expected = tok.encode(&turns[1][..deepest]).unwrap();
1062            assert_eq!(
1063                &*saved_tokens,
1064                expected.token_ids(),
1065                "persisted entry tokens must equal the uncached encode of the cached prefix"
1066            );
1067        }
1068    }
1069
1070    #[test]
1071    fn extend_without_deeper_boundary_does_not_insert() {
1072        let tok = load_tokenizer();
1073        let cache = test_cache(8 * 1024 * 1024);
1074        cache.insert_at_boundaries("<s>seed", tok.as_ref()).unwrap();
1075        for input in ["<s>世界", "<s>世界</s>"] {
1076            let PrefixLookup::Hit(matched) = cache.lookup_prefix(input) else {
1077                panic!("expected hit");
1078            };
1079            assert_eq!(matched.prefix_len, matched.deepest_boundary);
1080            let entries = cache.len();
1081            let merged = cache
1082                .extend_after_match_with_hash(input, matched, tok.as_ref())
1083                .unwrap();
1084            assert_eq!(merged, tok.encode(input).unwrap().token_ids());
1085            assert_eq!(cache.len(), entries);
1086        }
1087    }
1088
1089    struct FailAt {
1090        call: std::sync::atomic::AtomicUsize,
1091        fail_at: usize,
1092    }
1093    impl Encoder for FailAt {
1094        fn encode(&self, _: &str) -> crate::Result<crate::Encoding> {
1095            if self.call.fetch_add(1, Ordering::Relaxed) == self.fail_at {
1096                anyhow::bail!("suffix failed");
1097            }
1098            Ok(crate::Encoding::Sp(vec![1]))
1099        }
1100        fn encode_batch(&self, inputs: &[&str]) -> crate::Result<Vec<crate::Encoding>> {
1101            inputs.iter().map(|s| self.encode(s)).collect()
1102        }
1103    }
1104
1105    #[test]
1106    fn hash_reuse_does_not_insert_when_either_suffix_encode_fails() {
1107        let tok = load_tokenizer();
1108        let cache = test_cache(8 * 1024 * 1024);
1109        cache.insert_at_boundaries("<s>seed", tok.as_ref()).unwrap();
1110        let input = "<s>世界</s><s>tail";
1111        for fail_at in [0, 1] {
1112            let PrefixLookup::Hit(matched) = cache.lookup_prefix(input) else {
1113                panic!("expected hit");
1114            };
1115            let entries = cache.len();
1116            let error = cache
1117                .extend_after_match_with_hash(
1118                    input,
1119                    matched,
1120                    &FailAt {
1121                        call: 0.into(),
1122                        fail_at,
1123                    },
1124                )
1125                .unwrap_err();
1126            assert_eq!(error.to_string(), "suffix failed");
1127            assert_eq!(cache.len(), entries);
1128        }
1129    }
1130
1131    #[test]
1132    #[cfg(debug_assertions)]
1133    fn reused_hashes_reject_mismatched_input_before_insertion() {
1134        use std::panic::{AssertUnwindSafe, catch_unwind};
1135
1136        let tok = load_tokenizer();
1137        let cache = test_cache(8 * 1024 * 1024);
1138        cache.insert_at_boundaries("<s>seed", tok.as_ref()).unwrap();
1139        let PrefixLookup::Hit(matched) = cache.lookup_prefix("<s>世界</s><s>tail") else {
1140            panic!("expected hit");
1141        };
1142        let entries = cache.len();
1143        assert!(
1144            catch_unwind(AssertUnwindSafe(|| {
1145                cache.extend_after_match_with_hash("<s>日本</s><s>tail", matched, tok.as_ref())
1146            }))
1147            .is_err()
1148        );
1149        assert_eq!(cache.len(), entries);
1150
1151        let cache = test_cache(8 * 1024 * 1024);
1152        let PrefixLookup::Miss(hashes) = cache.lookup_prefix("a<s>世界</s>tail") else {
1153            panic!("expected miss");
1154        };
1155        assert!(
1156            catch_unwind(AssertUnwindSafe(|| {
1157                cache.populate_and_encode_with_hashes(
1158                    "b<s>世界</s>tail",
1159                    hashes.into_iter(),
1160                    tok.as_ref(),
1161                )
1162            }))
1163            .is_err()
1164        );
1165        assert!(cache.is_empty());
1166    }
1167
1168    #[test]
1169    fn boundaries_detected_for_multibyte_deepseek_tool_tokens() {
1170        // `find_special_token_boundaries` keys off byte offsets; DeepSeek's tool tokens use
1171        // multibyte code points (| = U+FF5C, ▁ = U+2581, 3 bytes each). A boundary must
1172        // land immediately after each occurrence at a valid char boundary, so the cache can
1173        // split a tool-call block at its special tokens without panicking on a slice.
1174        let specials = &["<|tool▁calls▁begin|>", "<|tool▁call▁end|>"];
1175        let text = "<|tool▁calls▁begin|>payload<|tool▁call▁end|>tail";
1176        let bounds = find_special_token_boundaries(text, specials);
1177
1178        let after_begin = "<|tool▁calls▁begin|>".len();
1179        let after_end = text.find("<|tool▁call▁end|>").unwrap() + "<|tool▁call▁end|>".len();
1180        assert_eq!(bounds, vec![after_begin, after_end]);
1181        for &b in &bounds {
1182            assert!(
1183                text.is_char_boundary(b),
1184                "boundary {b} is not a char boundary"
1185            );
1186            let _ = &text[..b]; // must not panic
1187        }
1188    }
1189
1190    fn populate_miss<E: Encoder + ?Sized>(
1191        cache: &L1Cache,
1192        input: &str,
1193        tokenizer: &E,
1194        reuse_hashes: bool,
1195    ) -> anyhow::Result<Vec<TokenIdType>> {
1196        if reuse_hashes {
1197            let PrefixLookup::Miss(hashes) = cache.lookup_prefix(input) else {
1198                panic!("expected miss");
1199            };
1200            cache.populate_and_encode_with_hashes(input, hashes.into_iter(), tokenizer)
1201        } else {
1202            cache.populate_and_encode(input, tokenizer)
1203        }
1204    }
1205
1206    #[test]
1207    fn populate_and_encode_matches_uncached_and_seeds_cache() {
1208        let tok = load_tokenizer();
1209        for input in [
1210            "<s>system\nYou are helpful.</s><s>user\nHello there, friend.</s>",
1211            "<s>system\n世界 🦀</s><s>user\nこんにちは</s>tail",
1212        ] {
1213            let plain = tok.encode(input).unwrap();
1214            let boundaries = find_special_token_boundaries(input, SPECIALS);
1215            for reuse_hashes in [false, true] {
1216                let cache = test_cache(8 * 1024 * 1024);
1217                let got = populate_miss(&cache, input, tok.as_ref(), reuse_hashes).unwrap();
1218                assert_eq!(
1219                    got,
1220                    plain.token_ids(),
1221                    "fused miss encode must equal uncached encode"
1222                );
1223
1224                let mut expected_bytes = 0;
1225                for &boundary in &boundaries {
1226                    let hash = cache.hash_prefix(&input.as_bytes()[..boundary]);
1227                    let saved = cache
1228                        .cache
1229                        .cache
1230                        .get(&hash)
1231                        .expect("every prefix is cached");
1232                    let expected = tok.encode(&input[..boundary]).unwrap();
1233                    assert_eq!(&*saved.tokens, expected.token_ids());
1234                    expected_bytes += size_of_val(expected.token_ids());
1235                }
1236                let stats = cache.stats();
1237                assert_eq!(stats.entries, boundaries.len());
1238                assert_eq!(stats.memory_bytes, expected_bytes);
1239                assert_eq!(stats.hits, 0);
1240                assert_eq!(stats.misses, u64::from(reuse_hashes));
1241                let (_t, offset, deepest) = cache
1242                    .longest_prefix_match(input)
1243                    .expect("hit after populate");
1244                assert_eq!(offset, *boundaries.last().unwrap());
1245                assert_eq!(deepest, offset);
1246            }
1247        }
1248    }
1249
1250    #[test]
1251    fn populate_and_encode_handles_inputs_without_special_tokens() {
1252        let tok = load_tokenizer();
1253        for input in ["", "plain text with no special tokens at all", "<s>"] {
1254            for reuse_hashes in [false, true] {
1255                let cache = test_cache(8 * 1024 * 1024);
1256                let got = populate_miss(&cache, input, tok.as_ref(), reuse_hashes).unwrap();
1257                let plain = tok.encode(input).unwrap();
1258                assert_eq!(got, plain.token_ids());
1259                assert!(cache.is_empty(), "nothing cacheable without boundaries");
1260                assert_eq!(cache.stats().misses, u64::from(reuse_hashes));
1261            }
1262        }
1263    }
1264
1265    #[test]
1266    fn populate_and_encode_handles_trailing_special_token() {
1267        // The boundary at input.len() is excluded, leaving the final `</s>` in the tail.
1268        let tok = load_tokenizer();
1269        let input = "<s>system\nDone.</s>";
1270        for reuse_hashes in [false, true] {
1271            let cache = test_cache(8 * 1024 * 1024);
1272            let got = populate_miss(&cache, input, tok.as_ref(), reuse_hashes).unwrap();
1273            let plain = tok.encode(input).unwrap();
1274            assert_eq!(
1275                got,
1276                plain.token_ids(),
1277                "tail-segment assembly must be exact"
1278            );
1279        }
1280    }
1281
1282    #[test]
1283    fn miss_encode_failure_retains_only_completed_prefixes() {
1284        let input = "<s>世界</s><s>tail";
1285        let boundaries = find_special_token_boundaries(input, SPECIALS);
1286        for fail_at in 0..=boundaries.len() {
1287            for reuse_hashes in [false, true] {
1288                let cache = test_cache(8 * 1024 * 1024);
1289                let encoder = FailAt {
1290                    call: 0.into(),
1291                    fail_at,
1292                };
1293                let error = populate_miss(&cache, input, &encoder, reuse_hashes).unwrap_err();
1294                assert_eq!(error.to_string(), "suffix failed");
1295                assert_eq!(cache.len(), fail_at);
1296                for (index, &boundary) in boundaries.iter().enumerate() {
1297                    let hash = cache.hash_prefix(&input.as_bytes()[..boundary]);
1298                    let saved = cache.cache.cache.get(&hash);
1299                    if index < fail_at {
1300                        assert_eq!(&*saved.unwrap().tokens, vec![1; index + 1]);
1301                    } else {
1302                        assert!(saved.is_none());
1303                    }
1304                }
1305            }
1306        }
1307    }
1308}