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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 let tok = load_tokenizer();
879 let turns = growing_chat_turns(5);
880
881 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 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 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 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 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 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 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]; }
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 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}