1use 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
41type Blake3Hash = [u8; 32];
43
44const SEGMENT_KEY_TAG: u8 = 0xFF;
46
47type PrefixHasher = BuildHasherDefault<FxHasher>;
50
51type 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#[derive(Clone)]
72pub struct SharedTokenizerCache {
73 cache: PrefixCache,
74}
75
76#[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 pub fn max_memory_bytes(&self) -> usize {
95 self.cache.policy().max_capacity().expect("capacity is set") as usize
96 }
97
98 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 hasher.update(&(namespace.len() as u64).to_le_bytes());
124 hasher.update(namespace);
125 hasher
126}
127
128pub(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
136pub(super) enum PrefixLookup {
138 Hit(PrefixMatch),
139 Miss(Vec<(usize, Blake3Hash)>),
140}
141
142fn 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
156fn 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
193pub(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#[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
230pub type CacheEventFn = Arc<dyn Fn() + Send + Sync>;
234
235pub struct L1Cache {
239 cache: SharedTokenizerCache,
240 shared: bool,
241 namespace: Vec<u8>,
242 namespace_hash: Blake3Hash,
243 matcher: Option<AhoCorasick>,
246 hits: AtomicU64,
247 misses: AtomicU64,
248 on_hit: Option<CacheEventFn>,
249 on_miss: Option<CacheEventFn>,
250}
251
252impl L1Cache {
253 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 let tok = load_tokenizer();
884 let turns = growing_chat_turns(5);
885
886 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 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 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 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 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 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 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]; }
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 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}