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 boundaries = self.boundaries(input);
374
375        if boundaries.is_empty() {
376            self.record_lookup(false);
377            return PrefixLookup::Miss(Vec::new());
378        }
379
380        let prefix_hashes: Vec<_> = hash_prefixes(self.hasher(), input, &boundaries).collect();
381
382        for &(boundary_pos, hash_bytes) in prefix_hashes.iter().rev() {
383            if let Some(entry) = self.cache.cache.get(&hash_bytes) {
384                self.record_lookup(true);
385                // Share cached tokens to avoid copying the prefix during lookup.
386                let &(deepest_boundary, deepest_hash) =
387                    prefix_hashes.last().expect("prefix hashes is non-empty");
388                return PrefixLookup::Hit(PrefixMatch {
389                    tokens: entry.tokens,
390                    prefix_len: boundary_pos,
391                    deepest_boundary,
392                    deepest_hash: Some(deepest_hash),
393                });
394            }
395        }
396
397        self.record_lookup(false);
398        PrefixLookup::Miss(prefix_hashes)
399    }
400
401    /// Insert prefix entries at every special-token boundary (e.g. to pre-seed the cache).
402    ///
403    /// Uses incremental hashing and incremental tokenization (per-segment encode of the
404    /// delta text between adjacent boundaries) so populating N entries costs one full
405    /// re-tokenize total, split across the segments. The miss path uses
406    /// [`Self::populate_and_encode`] instead, which reuses this same work to *also* return
407    /// the full token vector (avoiding a redundant second tokenization).
408    pub fn insert_at_boundaries<E: Encoder + ?Sized>(
409        &self,
410        input: &str,
411        tokenizer: &E,
412    ) -> anyhow::Result<()> {
413        let boundaries = self.boundaries(input);
414        if boundaries.is_empty() {
415            return Ok(());
416        }
417        self.populate_boundaries(
418            input,
419            hash_prefixes(self.hasher(), input, &boundaries),
420            tokenizer,
421        )?;
422        Ok(())
423    }
424
425    /// Miss-path encode: tokenize `input` exactly once, caching the cumulative prefix at
426    /// every special-token boundary as we go, and return the full token-id vector. This
427    /// replaces a separate full `encode` + [`Self::insert_at_boundaries`], which together
428    /// tokenized the input ~twice (once for the result, once split across segments).
429    ///
430    /// The concatenation of the per-segment encodes equals an uncached `encode(input)`
431    /// because special tokens are atomic in BPE — the same invariant the hit path relies
432    /// on. Returns token-ids only; the caller wraps them in [`crate::Encoding::Sp`].
433    pub fn populate_and_encode<E: Encoder + ?Sized>(
434        &self,
435        input: &str,
436        tokenizer: &E,
437    ) -> anyhow::Result<Vec<TokenIdType>> {
438        let boundaries = self.boundaries(input);
439        self.populate_and_encode_with_hashes(
440            input,
441            hash_prefixes(self.hasher(), input, &boundaries),
442            tokenizer,
443        )
444    }
445
446    /// Populate a miss using sorted boundary hashes, then encode the tail.
447    /// All offsets and digests must describe this same input; public callers compute
448    /// them lazily, while CachedTokenizer supplies hashes retained from lookup.
449    pub(super) fn populate_and_encode_with_hashes<E: Encoder + ?Sized>(
450        &self,
451        input: &str,
452        prefix_hashes: impl Iterator<Item = (usize, Blake3Hash)>,
453        tokenizer: &E,
454    ) -> anyhow::Result<Vec<TokenIdType>> {
455        let (mut running, tail_start) =
456            self.populate_boundaries(input, prefix_hashes, tokenizer)?;
457        if tail_start == 0 {
458            return Ok(tokenizer.encode(input)?.token_ids().to_vec());
459        }
460
461        let tail = tokenizer.encode(&input[tail_start..])?;
462        running.extend_from_slice(tail.token_ids());
463        Ok(running)
464    }
465
466    /// Tokenize each segment and cache its cumulative prefix with the supplied digest.
467    /// Return the running tokens and last boundary. Earlier entries survive later encode failures.
468    fn populate_boundaries<E: Encoder + ?Sized>(
469        &self,
470        input: &str,
471        prefix_hashes: impl Iterator<Item = (usize, Blake3Hash)>,
472        tokenizer: &E,
473    ) -> anyhow::Result<(Vec<TokenIdType>, usize)> {
474        #[cfg(debug_assertions)]
475        let mut validation_hasher = self.hasher();
476        let mut running_tokens: Vec<TokenIdType> = Vec::new();
477        let mut last_pos = 0;
478
479        for (boundary_pos, hash_bytes) in prefix_hashes {
480            #[cfg(debug_assertions)]
481            {
482                validation_hasher.update(&input.as_bytes()[last_pos..boundary_pos]);
483                debug_assert_eq!(hash_bytes, *validation_hasher.finalize().as_bytes());
484            }
485
486            // Incremental tokenization. Dynamo's Encoder has no `add_special_tokens`
487            // parameter — equivalent to upstream always passing `false` past the first
488            // segment (which is also what Dynamo's HF impl always does for the first).
489            let seg = tokenizer.encode(&input[last_pos..boundary_pos])?;
490            running_tokens.extend_from_slice(seg.token_ids());
491
492            let prefix_tokens: Arc<[TokenIdType]> = running_tokens.as_slice().into();
493            self.insert(hash_bytes, prefix_tokens);
494
495            last_pos = boundary_pos;
496        }
497
498        Ok((running_tokens, last_pos))
499    }
500
501    /// Extend the cache on a *partial* hit so the next turn of a growing conversation
502    /// hits deeper. Given the `(prefix_tokens, prefix_len, deepest_boundary)` returned by
503    /// [`longest_prefix_match`], tokenize the remaining suffix and cache the cumulative
504    /// prefix at the suffix's **deepest** special-token boundary, then return the full
505    /// merged token vector.
506    ///
507    /// Deepest-only is intentional: in an append-only conversation the next turn always
508    /// reaches the deepest boundary, so caching it bounds per-turn work to the newest
509    /// exchange; shallow/branching coverage already comes from the miss path's
510    /// [`insert_at_boundaries`]. Splitting at special-token boundaries is correctness-safe
511    /// because special tokens are atomic in BPE
512    /// (`tokenize(a) + tokenize(b) == tokenize(a + b)`).
513    ///
514    /// Note: unlike the read-only fast path, this **writes** to the cache on a hit
515    /// (one insert + possible eviction). It relies on the same best-effort memory
516    /// accounting as [`insert_at_boundaries`].
517    pub fn extend_after_match<E: Encoder + ?Sized>(
518        &self,
519        input: &str,
520        prefix_tokens: Arc<[TokenIdType]>,
521        prefix_len: usize,
522        deepest_boundary: usize,
523        tokenizer: &E,
524    ) -> anyhow::Result<Vec<TokenIdType>> {
525        self.extend_after_match_with_hash(
526            input,
527            PrefixMatch {
528                tokens: prefix_tokens,
529                prefix_len,
530                deepest_boundary,
531                deepest_hash: None,
532            },
533            tokenizer,
534        )
535    }
536
537    /// Extend a partial hit, reusing lookup's deepest digest for the new entry.
538    /// `matched` must describe this same input. The public compatibility wrapper alone
539    /// omits the digest and computes it here when an insertion is needed.
540    pub(super) fn extend_after_match_with_hash<E: Encoder + ?Sized>(
541        &self,
542        input: &str,
543        matched: PrefixMatch,
544        tokenizer: &E,
545    ) -> anyhow::Result<Vec<TokenIdType>> {
546        let PrefixMatch {
547            tokens: prefix_tokens,
548            prefix_len,
549            deepest_boundary,
550            deepest_hash,
551        } = matched;
552        // Boundaries exclude input.len(), so the trailing segment is nonempty.
553        let deepest = (deepest_boundary > prefix_len).then_some(deepest_boundary);
554
555        let Some(deepest) = deepest else {
556            let suffix_enc = tokenizer.encode(&input[prefix_len..])?;
557            // Reserve once to avoid copying the cached prefix during vector growth.
558            let mut merged = Vec::with_capacity(prefix_tokens.len() + suffix_enc.token_ids().len());
559            merged.extend_from_slice(&prefix_tokens);
560            merged.extend_from_slice(suffix_enc.token_ids());
561            return Ok(merged);
562        };
563
564        // Encode both segments first to reserve capacity without recopying the prefix.
565        let seg_a = tokenizer.encode(&input[prefix_len..deepest])?;
566        let seg_b = tokenizer.encode(&input[deepest..])?;
567        let mut cumulative = Vec::with_capacity(
568            prefix_tokens.len() + seg_a.token_ids().len() + seg_b.token_ids().len(),
569        );
570        cumulative.extend_from_slice(&prefix_tokens);
571        cumulative.extend_from_slice(seg_a.token_ids());
572
573        let hash_bytes =
574            deepest_hash.unwrap_or_else(|| self.hash_prefix(&input.as_bytes()[..deepest]));
575        debug_assert_eq!(hash_bytes, self.hash_prefix(&input.as_bytes()[..deepest]));
576
577        // Copy only the populated prefix, excluding capacity reserved for the tail.
578        let tokens: Arc<[TokenIdType]> = cumulative.as_slice().into();
579        self.insert(hash_bytes, tokens);
580
581        cumulative.extend_from_slice(seg_b.token_ids());
582        Ok(cumulative)
583    }
584
585    fn storage_stats(&self) -> SharedTokenizerCacheStats {
586        if self.shared {
587            self.cache.namespace_stats(&self.namespace_hash)
588        } else {
589            self.cache.stats()
590        }
591    }
592
593    /// Number of live entries. Shared caches scan this namespace after maintenance;
594    /// private caches use Moka's entry count. Concurrent writes can change the result.
595    pub fn len(&self) -> usize {
596        self.storage_stats().entries
597    }
598
599    pub fn is_empty(&self) -> bool {
600        if !self.shared {
601            return self.len() == 0;
602        }
603        self.cache.cache.run_pending_tasks();
604        !self
605            .cache
606            .cache
607            .iter()
608            .any(|(_, entry)| entry.namespace == self.namespace_hash)
609    }
610
611    pub fn stats(&self) -> L1CacheStats {
612        let storage = self.storage_stats();
613        let hits = self.hits.load(Ordering::Relaxed);
614        let misses = self.misses.load(Ordering::Relaxed);
615        let total_requests = hits + misses;
616
617        L1CacheStats {
618            hits,
619            misses,
620            entries: storage.entries,
621            memory_bytes: storage.memory_bytes,
622            hit_rate: if total_requests > 0 {
623                hits as f64 / total_requests as f64
624            } else {
625                0.0
626            },
627        }
628    }
629}
630
631#[derive(Debug, Clone, Default)]
632pub struct L1CacheStats {
633    pub hits: u64,
634    pub misses: u64,
635    pub entries: usize,
636    pub memory_bytes: usize,
637    pub hit_rate: f64,
638}
639
640#[cfg(test)]
641mod tests {
642    use std::sync::Arc;
643
644    use super::*;
645    use crate::{HuggingFaceTokenizer, traits::Tokenizer};
646
647    // TinyLlama: real Llama BPE with `<s>` and `</s>` as added tokens with
648    // `special: true, normalized: false` — atomic in BPE, safe boundary points.
649    const TINYLLAMA_PATH: &str = concat!(
650        env!("CARGO_MANIFEST_DIR"),
651        "/tests/data/sample-models/TinyLlama_v1.1/tokenizer.json"
652    );
653
654    const SPECIALS: &[&str] = &["<s>", "</s>"];
655
656    fn load_tokenizer() -> Arc<dyn Tokenizer> {
657        Arc::new(HuggingFaceTokenizer::from_file(TINYLLAMA_PATH).expect("load TinyLlama"))
658    }
659
660    /// An `L1Cache` over the TinyLlama [`SPECIALS`] with the given byte budget.
661    fn test_cache(max_memory: usize) -> L1Cache {
662        L1Cache::new(
663            max_memory,
664            SPECIALS.iter().map(|s| (*s).to_string()).collect(),
665        )
666    }
667
668    #[test]
669    fn prefix_hash_length_delimits_the_namespace() {
670        let storage = SharedTokenizerCache::new(1024);
671        let mut hashes = Vec::new();
672        for (namespace, prefix) in [("", "abc"), ("a", "bc"), ("ab", "c")] {
673            let cache = L1Cache::new_with_cache(storage.clone(), vec![], namespace.as_bytes());
674            let bytes = [
675                (namespace.len() as u64).to_le_bytes().as_slice(),
676                namespace.as_bytes(),
677                prefix.as_bytes(),
678            ]
679            .concat();
680            let expected = *blake3::hash(&bytes).as_bytes();
681            assert_eq!(cache.hash_prefix(prefix.as_bytes()), expected);
682            assert!(!hashes.contains(&expected));
683            hashes.push(expected);
684        }
685    }
686
687    #[test]
688    fn boundaries_are_after_each_special_token_occurrence() {
689        let input = "<s>system\nHi</s><s>user\nHello</s>";
690        let bounds = find_special_token_boundaries(input, SPECIALS);
691        // Drop the trailing boundary (==text.len()), so 3 not 4 boundaries.
692        assert_eq!(bounds.len(), 3);
693        for w in bounds.windows(2) {
694            assert!(w[0] < w[1], "boundaries must be strictly increasing");
695        }
696        assert!(bounds.iter().all(|&b| b < input.len()));
697    }
698
699    #[test]
700    fn no_special_tokens_yields_no_boundaries() {
701        assert!(find_special_token_boundaries("plain text", &[]).is_empty());
702    }
703
704    #[test]
705    fn unsafe_overlap_detects_containment_crossing_and_self_overlap() {
706        let cases = [
707            (vec!["〈|", "〈|EOS|〉"], Some(("〈|", "〈|EOS|〉"))),
708            (vec!["ab", "bc"], Some(("ab", "bc"))),
709            (vec!["|◊|"], Some(("|◊|", "|◊|"))),
710            (vec!["<s>", "<s>"], None),
711        ];
712
713        for (tokens, expected) in cases {
714            let tokens: Vec<String> = tokens.into_iter().map(String::from).collect();
715            assert_eq!(first_unsafe_overlap(&tokens), expected);
716        }
717    }
718
719    #[test]
720    fn llama_numbered_special_tokens_do_not_trigger_overlap_guard() {
721        let mut llama: Vec<String> = [
722            "<|begin_of_text|>",
723            "<|end_of_text|>",
724            "<|start_header_id|>",
725            "<|end_header_id|>",
726            "<|eot_id|>",
727        ]
728        .into_iter()
729        .map(String::from)
730        .collect();
731        llama.extend((0..251).map(|id| format!("<|reserved_special_token_{id}|>")));
732
733        assert_eq!(first_unsafe_overlap(&llama), None);
734    }
735
736    #[test]
737    fn insert_then_lookup_finds_shared_prefix() {
738        let cache = test_cache(1024 * 1024);
739        let tokenizer = load_tokenizer();
740
741        let warm = "<s>system\nYou are helpful.</s><s>user\nHi</s>";
742        cache
743            .insert_at_boundaries(warm, tokenizer.as_ref())
744            .unwrap();
745        assert!(!cache.is_empty());
746
747        let target = "<s>system\nYou are helpful.</s><s>user\nDifferent question</s>";
748        let (tokens, offset, _deepest) = cache
749            .longest_prefix_match(target)
750            .expect("shared prefix should match");
751        assert!(offset > 0);
752        assert!(!tokens.is_empty());
753    }
754
755    #[test]
756    fn miss_increments_misses_counter() {
757        let cache = test_cache(1024 * 1024);
758        assert!(
759            cache
760                .longest_prefix_match("plain text no specials")
761                .is_none()
762        );
763        assert_eq!(cache.stats().misses, 1);
764    }
765
766    #[test]
767    fn hit_increments_hits_counter() {
768        let cache = test_cache(1024 * 1024);
769        let tokenizer = load_tokenizer();
770        let warm = "<s>system\nA.</s><s>user\nB</s>";
771        cache
772            .insert_at_boundaries(warm, tokenizer.as_ref())
773            .unwrap();
774        let _ = cache.longest_prefix_match(warm);
775        assert!(cache.stats().hits >= 1);
776    }
777
778    #[test]
779    fn merge_invariant_holds_against_uncached_encode() {
780        // Load-bearing correctness check: cached prefix + fresh suffix encode must
781        // equal plain encode of the full input. Relies on `<s>`/`</s>` being atomic
782        // in TinyLlama's BPE (they are).
783        let cache = test_cache(1024 * 1024);
784        let tokenizer = load_tokenizer();
785
786        let template = "<s>system\nYou are helpful.</s><s>user\n";
787        let warm = format!("{template}First.</s>");
788        cache
789            .insert_at_boundaries(&warm, tokenizer.as_ref())
790            .unwrap();
791
792        let target = format!("{template}A completely different second question.</s>");
793        let (prefix_tokens, prefix_len, _deepest) = cache
794            .longest_prefix_match(&target)
795            .expect("should find prefix");
796
797        let suffix = &target[prefix_len..];
798        let suffix_enc = tokenizer.encode(suffix).unwrap();
799        // longest_prefix_match returns the shared `Arc<[u32]>`; copy into a Vec to append the suffix.
800        let mut merged = prefix_tokens.to_vec();
801        merged.extend_from_slice(suffix_enc.token_ids());
802
803        let plain = tokenizer.encode(&target).unwrap();
804        assert_eq!(
805            merged,
806            plain.token_ids(),
807            "merged tokens must equal plain encode"
808        );
809    }
810
811    #[test]
812    fn eviction_respects_memory_budget() {
813        // 4 KB budget — tight enough to force eviction after a few inserts.
814        let cache = test_cache(4 * 1024);
815        let tokenizer = load_tokenizer();
816        for i in 0..50 {
817            let input =
818                format!("<s>system\nPersona {i} chatty.</s><s>user\nTurn {i} content here.</s>");
819            cache
820                .insert_at_boundaries(&input, tokenizer.as_ref())
821                .unwrap();
822        }
823        let stats = cache.stats();
824        assert!(
825            stats.memory_bytes <= 4 * 1024,
826            "memory_bytes={} exceeds budget",
827            stats.memory_bytes
828        );
829    }
830
831    #[test]
832    fn concurrent_inserts_and_lookups_do_not_corrupt() {
833        use std::thread;
834
835        let cache = Arc::new(test_cache(1024 * 1024));
836        let tokenizer = load_tokenizer();
837
838        let mut handles = vec![];
839        for i in 0..10 {
840            let cache_c = cache.clone();
841            let tok = tokenizer.clone();
842            handles.push(thread::spawn(move || {
843                let input = format!("<s>system\nThread {i}.</s><s>user\nThread {i} body.</s>");
844                cache_c.insert_at_boundaries(&input, tok.as_ref()).unwrap();
845                let r = cache_c.longest_prefix_match(&input);
846                assert!(r.is_some(), "thread {i} expected match after insert");
847            }));
848        }
849        for h in handles {
850            h.join().unwrap();
851        }
852        assert!(cache.stats().memory_bytes > 0);
853        assert!(cache.stats().hits >= 10);
854    }
855
856    /// Build an append-only multi-turn conversation. `turns[i]` is the full prompt at
857    /// turn `i`: the system prompt, `i + 1` completed user/assistant exchanges, and a
858    /// diverging open user turn (no trailing special, so the deepest boundary is the
859    /// `<s>` that opens it). Each `turns[i]` shares a strictly longer `</s>`-bounded
860    /// prefix with `turns[i + 1]`.
861    fn growing_chat_turns(n: usize) -> Vec<String> {
862        let mut convo = String::from("<s>system\nYou are a helpful assistant.</s>");
863        let mut turns = Vec::with_capacity(n);
864        for i in 0..n {
865            convo.push_str(&format!(
866                "<s>user\nQuestion {i} please answer it.</s><s>assistant\nDetailed answer {i} follows here.</s>"
867            ));
868            turns.push(format!("{convo}<s>user\nFollow-up {i}"));
869        }
870        turns
871    }
872
873    #[test]
874    fn extend_on_hit_advances_match_depth_each_turn() {
875        // The load-bearing behavioral proof. Without extension the match offset is
876        // pinned at turn-1 depth (hits never insert); with extension it advances every
877        // turn, so the suffix re-tokenized per turn shrinks instead of growing.
878        let tok = load_tokenizer();
879        let turns = growing_chat_turns(5);
880
881        // EXTEND OFF: seed turn 0 via the miss path, then only look up (never insert).
882        let off = test_cache(8 * 1024 * 1024);
883        off.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
884        let pinned = off.longest_prefix_match(&turns[1]).expect("hit").1;
885        for t in &turns[1..] {
886            let (_toks, offset, _deepest) = off.longest_prefix_match(t).expect("hit");
887            assert_eq!(
888                offset, pinned,
889                "extend-off offset must stay pinned at turn-1 depth"
890            );
891        }
892
893        // EXTEND ON: each hit caches the deepest boundary, so the next turn hits deeper.
894        let on = test_cache(8 * 1024 * 1024);
895        on.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
896        let mut prev = 0usize;
897        for (i, t) in turns.iter().enumerate().skip(1) {
898            let (prefix_tokens, offset, deepest) = on.longest_prefix_match(t).expect("hit");
899            assert!(
900                offset > prev,
901                "turn {i}: extend-on offset {offset} must exceed previous {prev}"
902            );
903            prev = offset;
904
905            // Extending must also preserve byte-exact correctness vs an uncached encode.
906            let merged = on
907                .extend_after_match(t, prefix_tokens, offset, deepest, tok.as_ref())
908                .unwrap();
909            let plain = tok.encode(t).unwrap();
910            assert_eq!(
911                merged,
912                plain.token_ids(),
913                "turn {i}: extend merge must equal plain encode"
914            );
915        }
916
917        assert!(
918            prev > pinned,
919            "extend-on frontier ({prev}) must reach deeper than pinned extend-off depth ({pinned})"
920        );
921    }
922
923    #[test]
924    fn extend_on_hit_respects_budget_and_stays_correct() {
925        // Tiny budget forces eviction (and over-budget skips) while extending; every
926        // turn's encode must stay correct and memory must stay within budget.
927        let tok = load_tokenizer();
928        let cache = test_cache(4 * 1024);
929        let turns = growing_chat_turns(20);
930        cache.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
931
932        for t in &turns[1..] {
933            let merged = match cache.longest_prefix_match(t) {
934                Some((prefix_tokens, offset, deepest)) => cache
935                    .extend_after_match(t, prefix_tokens, offset, deepest, tok.as_ref())
936                    .unwrap(),
937                None => {
938                    // Full miss under eviction pressure — mirror the miss path.
939                    let enc = tok.encode(t).unwrap();
940                    cache.insert_at_boundaries(t, tok.as_ref()).unwrap();
941                    enc.token_ids().to_vec()
942                }
943            };
944            let plain = tok.encode(t).unwrap();
945            assert_eq!(
946                merged,
947                plain.token_ids(),
948                "encode must stay correct under eviction pressure"
949            );
950            assert!(
951                cache.stats().memory_bytes <= 4 * 1024,
952                "memory_bytes={} exceeds budget",
953                cache.stats().memory_bytes
954            );
955        }
956    }
957
958    #[test]
959    fn concurrent_extend_on_hit_does_not_corrupt() {
960        use std::thread;
961
962        let tok = load_tokenizer();
963        let cache = Arc::new(test_cache(8 * 1024 * 1024));
964        let turns = growing_chat_turns(8);
965        // Seed turn 0 so every thread gets at least a partial hit.
966        cache.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
967
968        let mut handles = vec![];
969        for _ in 0..8 {
970            let cache_c = cache.clone();
971            let tok_c = tok.clone();
972            let turns_c = turns.clone();
973            handles.push(thread::spawn(move || {
974                for t in &turns_c[1..] {
975                    if let PrefixLookup::Hit(matched) = cache_c.lookup_prefix(t) {
976                        let merged = cache_c
977                            .extend_after_match_with_hash(t, matched, tok_c.as_ref())
978                            .unwrap();
979                        let plain = tok_c.encode(t).unwrap();
980                        assert_eq!(
981                            merged,
982                            plain.token_ids(),
983                            "concurrent extend must stay correct"
984                        );
985                    }
986                }
987            }));
988        }
989        for h in handles {
990            h.join().unwrap();
991        }
992        assert!(cache.stats().memory_bytes > 0);
993    }
994
995    #[test]
996    fn extend_after_match_persists_correct_deepest_entry() {
997        let tok = load_tokenizer();
998        for unicode in [false, true] {
999            let turns: Vec<_> = growing_chat_turns(3)
1000                .into_iter()
1001                .map(|t| {
1002                    if unicode {
1003                        t.replace("system", "system 世界 🦀")
1004                    } else {
1005                        t
1006                    }
1007                })
1008                .collect();
1009
1010            let cache = test_cache(8 * 1024 * 1024);
1011            cache.insert_at_boundaries(&turns[0], tok.as_ref()).unwrap();
1012
1013            let PrefixLookup::Hit(matched) = cache.lookup_prefix(&turns[1]) else {
1014                panic!("partial hit on turns[1]");
1015            };
1016            let prefix_len = matched.prefix_len;
1017            let deepest_boundary = matched.deepest_boundary;
1018            assert!(deepest_boundary > prefix_len);
1019            assert_eq!(
1020                matched.deepest_hash,
1021                Some(cache.hash_prefix(&turns[1].as_bytes()[..deepest_boundary]))
1022            );
1023            assert_ne!(
1024                matched.deepest_hash,
1025                Some(cache.hash_prefix(&turns[1].as_bytes()[..prefix_len]))
1026            );
1027            let entries_before = cache.stats().entries;
1028
1029            let _merged = cache
1030                .extend_after_match_with_hash(&turns[1], matched, tok.as_ref())
1031                .unwrap();
1032
1033            assert_eq!(
1034                cache.stats().entries,
1035                entries_before + 1,
1036                "extend must persist exactly one (deepest) entry"
1037            );
1038
1039            let deepest = find_special_token_boundaries(&turns[1], SPECIALS)
1040                .into_iter()
1041                .rev()
1042                .find(|&b| b > prefix_len)
1043                .expect("a deeper boundary must exist in the appended turn");
1044            assert_eq!(
1045                deepest_boundary, deepest,
1046                "longest_prefix_match must return the deepest boundary used by extend"
1047            );
1048
1049            let (saved_tokens, saved_offset, _deepest) = cache
1050                .longest_prefix_match(&turns[1])
1051                .expect("hit after extend");
1052            assert_eq!(
1053                saved_offset, deepest,
1054                "lookup must now hit at the just-saved deepest boundary"
1055            );
1056            let expected = tok.encode(&turns[1][..deepest]).unwrap();
1057            assert_eq!(
1058                &*saved_tokens,
1059                expected.token_ids(),
1060                "persisted entry tokens must equal the uncached encode of the cached prefix"
1061            );
1062        }
1063    }
1064
1065    #[test]
1066    fn extend_without_deeper_boundary_does_not_insert() {
1067        let tok = load_tokenizer();
1068        let cache = test_cache(8 * 1024 * 1024);
1069        cache.insert_at_boundaries("<s>seed", tok.as_ref()).unwrap();
1070        for input in ["<s>世界", "<s>世界</s>"] {
1071            let PrefixLookup::Hit(matched) = cache.lookup_prefix(input) else {
1072                panic!("expected hit");
1073            };
1074            assert_eq!(matched.prefix_len, matched.deepest_boundary);
1075            let entries = cache.len();
1076            let merged = cache
1077                .extend_after_match_with_hash(input, matched, tok.as_ref())
1078                .unwrap();
1079            assert_eq!(merged, tok.encode(input).unwrap().token_ids());
1080            assert_eq!(cache.len(), entries);
1081        }
1082    }
1083
1084    struct FailAt {
1085        call: std::sync::atomic::AtomicUsize,
1086        fail_at: usize,
1087    }
1088    impl Encoder for FailAt {
1089        fn encode(&self, _: &str) -> crate::Result<crate::Encoding> {
1090            if self.call.fetch_add(1, Ordering::Relaxed) == self.fail_at {
1091                anyhow::bail!("suffix failed");
1092            }
1093            Ok(crate::Encoding::Sp(vec![1]))
1094        }
1095        fn encode_batch(&self, inputs: &[&str]) -> crate::Result<Vec<crate::Encoding>> {
1096            inputs.iter().map(|s| self.encode(s)).collect()
1097        }
1098    }
1099
1100    #[test]
1101    fn hash_reuse_does_not_insert_when_either_suffix_encode_fails() {
1102        let tok = load_tokenizer();
1103        let cache = test_cache(8 * 1024 * 1024);
1104        cache.insert_at_boundaries("<s>seed", tok.as_ref()).unwrap();
1105        let input = "<s>世界</s><s>tail";
1106        for fail_at in [0, 1] {
1107            let PrefixLookup::Hit(matched) = cache.lookup_prefix(input) else {
1108                panic!("expected hit");
1109            };
1110            let entries = cache.len();
1111            let error = cache
1112                .extend_after_match_with_hash(
1113                    input,
1114                    matched,
1115                    &FailAt {
1116                        call: 0.into(),
1117                        fail_at,
1118                    },
1119                )
1120                .unwrap_err();
1121            assert_eq!(error.to_string(), "suffix failed");
1122            assert_eq!(cache.len(), entries);
1123        }
1124    }
1125
1126    #[test]
1127    #[cfg(debug_assertions)]
1128    fn reused_hashes_reject_mismatched_input_before_insertion() {
1129        use std::panic::{AssertUnwindSafe, catch_unwind};
1130
1131        let tok = load_tokenizer();
1132        let cache = test_cache(8 * 1024 * 1024);
1133        cache.insert_at_boundaries("<s>seed", tok.as_ref()).unwrap();
1134        let PrefixLookup::Hit(matched) = cache.lookup_prefix("<s>世界</s><s>tail") else {
1135            panic!("expected hit");
1136        };
1137        let entries = cache.len();
1138        assert!(
1139            catch_unwind(AssertUnwindSafe(|| {
1140                cache.extend_after_match_with_hash("<s>日本</s><s>tail", matched, tok.as_ref())
1141            }))
1142            .is_err()
1143        );
1144        assert_eq!(cache.len(), entries);
1145
1146        let cache = test_cache(8 * 1024 * 1024);
1147        let PrefixLookup::Miss(hashes) = cache.lookup_prefix("a<s>世界</s>tail") else {
1148            panic!("expected miss");
1149        };
1150        assert!(
1151            catch_unwind(AssertUnwindSafe(|| {
1152                cache.populate_and_encode_with_hashes(
1153                    "b<s>世界</s>tail",
1154                    hashes.into_iter(),
1155                    tok.as_ref(),
1156                )
1157            }))
1158            .is_err()
1159        );
1160        assert!(cache.is_empty());
1161    }
1162
1163    #[test]
1164    fn boundaries_detected_for_multibyte_deepseek_tool_tokens() {
1165        // `find_special_token_boundaries` keys off byte offsets; DeepSeek's tool tokens use
1166        // multibyte code points (| = U+FF5C, ▁ = U+2581, 3 bytes each). A boundary must
1167        // land immediately after each occurrence at a valid char boundary, so the cache can
1168        // split a tool-call block at its special tokens without panicking on a slice.
1169        let specials = &["<|tool▁calls▁begin|>", "<|tool▁call▁end|>"];
1170        let text = "<|tool▁calls▁begin|>payload<|tool▁call▁end|>tail";
1171        let bounds = find_special_token_boundaries(text, specials);
1172
1173        let after_begin = "<|tool▁calls▁begin|>".len();
1174        let after_end = text.find("<|tool▁call▁end|>").unwrap() + "<|tool▁call▁end|>".len();
1175        assert_eq!(bounds, vec![after_begin, after_end]);
1176        for &b in &bounds {
1177            assert!(
1178                text.is_char_boundary(b),
1179                "boundary {b} is not a char boundary"
1180            );
1181            let _ = &text[..b]; // must not panic
1182        }
1183    }
1184
1185    fn populate_miss<E: Encoder + ?Sized>(
1186        cache: &L1Cache,
1187        input: &str,
1188        tokenizer: &E,
1189        reuse_hashes: bool,
1190    ) -> anyhow::Result<Vec<TokenIdType>> {
1191        if reuse_hashes {
1192            let PrefixLookup::Miss(hashes) = cache.lookup_prefix(input) else {
1193                panic!("expected miss");
1194            };
1195            cache.populate_and_encode_with_hashes(input, hashes.into_iter(), tokenizer)
1196        } else {
1197            cache.populate_and_encode(input, tokenizer)
1198        }
1199    }
1200
1201    #[test]
1202    fn populate_and_encode_matches_uncached_and_seeds_cache() {
1203        let tok = load_tokenizer();
1204        for input in [
1205            "<s>system\nYou are helpful.</s><s>user\nHello there, friend.</s>",
1206            "<s>system\n世界 🦀</s><s>user\nこんにちは</s>tail",
1207        ] {
1208            let plain = tok.encode(input).unwrap();
1209            let boundaries = find_special_token_boundaries(input, SPECIALS);
1210            for reuse_hashes in [false, true] {
1211                let cache = test_cache(8 * 1024 * 1024);
1212                let got = populate_miss(&cache, input, tok.as_ref(), reuse_hashes).unwrap();
1213                assert_eq!(
1214                    got,
1215                    plain.token_ids(),
1216                    "fused miss encode must equal uncached encode"
1217                );
1218
1219                let mut expected_bytes = 0;
1220                for &boundary in &boundaries {
1221                    let hash = cache.hash_prefix(&input.as_bytes()[..boundary]);
1222                    let saved = cache
1223                        .cache
1224                        .cache
1225                        .get(&hash)
1226                        .expect("every prefix is cached");
1227                    let expected = tok.encode(&input[..boundary]).unwrap();
1228                    assert_eq!(&*saved.tokens, expected.token_ids());
1229                    expected_bytes += size_of_val(expected.token_ids());
1230                }
1231                let stats = cache.stats();
1232                assert_eq!(stats.entries, boundaries.len());
1233                assert_eq!(stats.memory_bytes, expected_bytes);
1234                assert_eq!(stats.hits, 0);
1235                assert_eq!(stats.misses, u64::from(reuse_hashes));
1236                let (_t, offset, deepest) = cache
1237                    .longest_prefix_match(input)
1238                    .expect("hit after populate");
1239                assert_eq!(offset, *boundaries.last().unwrap());
1240                assert_eq!(deepest, offset);
1241            }
1242        }
1243    }
1244
1245    #[test]
1246    fn populate_and_encode_handles_inputs_without_special_tokens() {
1247        let tok = load_tokenizer();
1248        for input in ["", "plain text with no special tokens at all", "<s>"] {
1249            for reuse_hashes in [false, true] {
1250                let cache = test_cache(8 * 1024 * 1024);
1251                let got = populate_miss(&cache, input, tok.as_ref(), reuse_hashes).unwrap();
1252                let plain = tok.encode(input).unwrap();
1253                assert_eq!(got, plain.token_ids());
1254                assert!(cache.is_empty(), "nothing cacheable without boundaries");
1255                assert_eq!(cache.stats().misses, u64::from(reuse_hashes));
1256            }
1257        }
1258    }
1259
1260    #[test]
1261    fn populate_and_encode_handles_trailing_special_token() {
1262        // The boundary at input.len() is excluded, leaving the final `</s>` in the tail.
1263        let tok = load_tokenizer();
1264        let input = "<s>system\nDone.</s>";
1265        for reuse_hashes in [false, true] {
1266            let cache = test_cache(8 * 1024 * 1024);
1267            let got = populate_miss(&cache, input, tok.as_ref(), reuse_hashes).unwrap();
1268            let plain = tok.encode(input).unwrap();
1269            assert_eq!(
1270                got,
1271                plain.token_ids(),
1272                "tail-segment assembly must be exact"
1273            );
1274        }
1275    }
1276
1277    #[test]
1278    fn miss_encode_failure_retains_only_completed_prefixes() {
1279        let input = "<s>世界</s><s>tail";
1280        let boundaries = find_special_token_boundaries(input, SPECIALS);
1281        for fail_at in 0..=boundaries.len() {
1282            for reuse_hashes in [false, true] {
1283                let cache = test_cache(8 * 1024 * 1024);
1284                let encoder = FailAt {
1285                    call: 0.into(),
1286                    fail_at,
1287                };
1288                let error = populate_miss(&cache, input, &encoder, reuse_hashes).unwrap_err();
1289                assert_eq!(error.to_string(), "suffix failed");
1290                assert_eq!(cache.len(), fail_at);
1291                for (index, &boundary) in boundaries.iter().enumerate() {
1292                    let hash = cache.hash_prefix(&input.as_bytes()[..boundary]);
1293                    let saved = cache.cache.cache.get(&hash);
1294                    if index < fail_at {
1295                        assert_eq!(&*saved.unwrap().tokens, vec![1; index + 1]);
1296                    } else {
1297                        assert!(saved.is_none());
1298                    }
1299                }
1300            }
1301        }
1302    }
1303}