use std::{
cell::RefCell,
cmp::Reverse,
collections::{BinaryHeap, HashMap},
fmt,
mem::MaybeUninit,
sync::{
Mutex,
atomic::{AtomicUsize, Ordering},
},
};
use bincode::{Decode, Encode};
use daachorse::{DoubleArrayAhoCorasick, DoubleArrayAhoCorasickBuilder};
use dary_heap::QuaternaryHeap;
use serde::Deserialize;
use serde_json::Value;
use super::Result;
use crate::pre_tokenizers::{BYTE_TO_CHAR, FusedPieceSink};
type TokenId = u32;
type ParsedMergeMap = HashMap<(u32, u32), (u32, u32)>;
type Vocab = HashMap<String, u32>;
const INVALID_TOKEN: u32 = u32::MAX;
const DENSE_MERGE_BITS: u32 = 9;
const DENSE_MERGE_LIMIT: u32 = 1 << DENSE_MERGE_BITS;
const DENSE_MERGE_SIZE: usize = 1 << (DENSE_MERGE_BITS * 2);
const DENSE_RANKED_BITS: u32 = 10;
const DENSE_RANKED_LIMIT: u32 = 1 << DENSE_RANKED_BITS;
const DENSE_RANKED_SIZE: usize = 1 << (DENSE_RANKED_BITS * 2);
const FUSED_CACHE_BACKING_SEED_LIMIT: usize = 160 * 1024;
const EMPTY_KEY: u64 = u64::MAX;
#[derive(Clone, PartialEq)]
pub struct BigramBridgeTable {
bridgeable: Box<[bool; 65536]>,
}
impl BigramBridgeTable {
#[inline(always)]
pub fn is_bridgeable(&self, prev: u8, cur: u8) -> bool {
self.bridgeable[prev as usize * 256 + cur as usize]
}
}
fn build_bigram_bridge_table(id_to_token: &[String], byte_fallback: bool) -> BigramBridgeTable {
let mut bridgeable = Box::new([false; 65536]);
for token_str in id_to_token {
let bytes = token_str.as_bytes();
for window in bytes.windows(2) {
let prev = window[0] as usize;
let cur = window[1] as usize;
bridgeable[prev * 256 + cur] = true;
}
if byte_fallback && memchr::memchr(b'<', bytes).is_some() {
let mut previous = None;
let mut remaining = bytes;
while !remaining.is_empty() {
let (byte, width) = parse_byte_fallback_prefix(remaining)
.map_or((remaining[0], 1), |byte| (byte, 6));
if let Some(previous) = previous {
bridgeable[previous as usize * 256 + byte as usize] = true;
}
previous = Some(byte);
remaining = &remaining[width..];
}
}
}
BigramBridgeTable { bridgeable }
}
fn parse_byte_fallback_prefix(bytes: &[u8]) -> Option<u8> {
if bytes.len() < 6 || &bytes[..3] != b"<0x" || bytes[5] != b'>' {
return None;
}
let digits = std::str::from_utf8(&bytes[3..5]).ok()?;
u8::from_str_radix(digits, 16).ok()
}
#[inline(always)]
fn pack_pair(t1: u32, t2: u32) -> u64 {
(t1 as u64) << 32 | t2 as u64
}
#[inline(always)]
fn fx_hash(key: u64) -> u64 {
key.wrapping_mul(0x517cc1b727220a95)
}
#[inline(always)]
fn fx_hash_bytes(bytes: &[u8], mut state: u64) -> u64 {
let mut i = 0;
while i + 8 <= bytes.len() {
let word = u64::from_ne_bytes(bytes[i..i + 8].try_into().unwrap());
state = state.wrapping_add(word).wrapping_mul(0x517cc1b727220a95);
i += 8;
}
while i < bytes.len() {
state = state
.wrapping_add(bytes[i] as u64)
.wrapping_mul(0x517cc1b727220a95);
i += 1;
}
state
}
struct FxBuildHasher;
impl std::hash::BuildHasher for FxBuildHasher {
type Hasher = FxStrHasher;
fn build_hasher(&self) -> FxStrHasher {
FxStrHasher(0)
}
}
struct FxStrHasher(u64);
impl std::hash::Hasher for FxStrHasher {
#[inline]
fn finish(&self) -> u64 {
self.0
}
#[inline]
fn write(&mut self, bytes: &[u8]) {
self.0 = fx_hash_bytes(bytes, self.0);
}
}
type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;
const FLAT_CACHE_BITS: usize = 18;
const FLAT_CACHE_SIZE: usize = 1 << FLAT_CACHE_BITS;
const EMPTY_SHORT_KEY: u128 = 0;
const FRONT_CACHE_BITS: u32 = 21;
const FRONT_CACHE_SIZE: usize = 1 << FRONT_CACHE_BITS;
const PARALLEL_FRONT_CACHE_BITS: u32 = 19;
const PARALLEL_FRONT_CACHE_SIZE: usize = 1 << PARALLEL_FRONT_CACHE_BITS;
const FUSED_PIECE_BATCH: usize = 256;
const FUSED_PIECE_CAPACITY: usize = FUSED_PIECE_BATCH + 64;
#[inline(always)]
fn pack_short_key(key: &str) -> Option<u128> {
let bytes = key.as_bytes();
if bytes.is_empty() || bytes.len() > 15 {
return None;
}
let mut packed = (bytes.len() as u128) << 120;
for (shift, &byte) in bytes.iter().enumerate() {
packed |= (byte as u128) << (shift * 8);
}
Some(packed)
}
#[inline(always)]
const fn short_key_masks(len: usize) -> (u64, u64) {
let bits = (len * 8) as u32;
let low = if len < 8 {
u64::MAX >> (64u32.wrapping_sub(bits) & 63)
} else {
u64::MAX
};
let high = if len > 8 {
u64::MAX >> (128u32.wrapping_sub(bits) & 63)
} else {
0
};
(low, high)
}
#[inline(always)]
fn pack_short_range(input: &str, start: usize, end: usize) -> u128 {
let len = end - start;
debug_assert_ne!(len, 0);
if len > 15 {
return EMPTY_SHORT_KEY;
}
if start + 16 <= input.len() {
return unsafe { pack_short_range_inbounds(input, start, len) };
}
pack_short_range_tail(input, start, end)
}
#[inline(always)]
unsafe fn pack_short_range_inbounds(input: &str, start: usize, len: usize) -> u128 {
debug_assert!((1..=15).contains(&len));
debug_assert!(start + 16 <= input.len());
#[cfg(target_arch = "aarch64")]
unsafe {
use core::arch::aarch64::*;
const LANES: [u8; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
let raw = vld1q_u8(input.as_ptr().add(start));
let live = vcltq_u8(vld1q_u8(LANES.as_ptr()), vdupq_n_u8(len as u8));
let packed = vsetq_lane_u8::<15>(len as u8, vandq_u8(raw, live));
let words = vreinterpretq_u64_u8(packed);
let low = vgetq_lane_u64::<0>(words);
let high = vgetq_lane_u64::<1>(words);
(low as u128) | (high as u128) << 64
}
#[cfg(target_arch = "x86_64")]
unsafe {
use core::arch::x86_64::*;
const LANES: [i8; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
let raw = _mm_loadu_si128(input.as_ptr().add(start).cast());
let indices = _mm_loadu_si128(LANES.as_ptr().cast());
let live = _mm_cmpgt_epi8(_mm_set1_epi8(len as i8), indices);
let tag = _mm_slli_si128::<15>(_mm_cvtsi64_si128(len as i64));
let packed = _mm_or_si128(_mm_and_si128(raw, live), tag);
let low = _mm_cvtsi128_si64(packed) as u64;
let high = _mm_cvtsi128_si64(_mm_srli_si128::<8>(packed)) as u64;
(low as u128) | (high as u128) << 64
}
#[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
{
let word = unsafe { (input.as_ptr().add(start) as *const u128).read_unaligned() };
let (low_mask, high_mask) = short_key_masks(len);
let low = (word as u64) & low_mask;
let high = ((word >> 64) as u64) & high_mask;
(low as u128) | (high as u128) << 64 | (len as u128) << 120
}
}
#[cold]
#[inline(never)]
fn pack_short_range_tail(input: &str, start: usize, end: usize) -> u128 {
let len = end - start;
if input.len() >= 16 {
let window_start = input.len() - 16;
let word = unsafe { (input.as_ptr().add(window_start) as *const u128).read_unaligned() };
let shift = (start - window_start) * 8;
let word = word >> shift;
let (low_mask, high_mask) = short_key_masks(len);
let low = (word as u64) & low_mask;
let high = ((word >> 64) as u64) & high_mask;
return (low as u128) | (high as u128) << 64 | (len as u128) << 120;
}
pack_short_key(&input[start..end]).unwrap_or(EMPTY_SHORT_KEY)
}
#[inline(always)]
fn packed_key_hash(key: u128) -> u64 {
#[cfg(all(target_arch = "aarch64", target_feature = "crc"))]
{
use core::arch::aarch64::__crc32d;
let crc = unsafe { __crc32d(__crc32d(0, key as u64), (key >> 64) as u64) };
crc as u64
}
#[cfg(not(all(target_arch = "aarch64", target_feature = "crc")))]
{
let low = key as u64;
let high = (key >> 64) as u64;
let mut hash = (low ^ high.rotate_right(25)).wrapping_mul(0x9E37_79B9_7F4A_7C15);
hash ^= hash >> 32;
hash
}
}
#[inline(always)]
fn front_cache_index(key: u128, mask: usize) -> usize {
packed_key_hash(key) as usize & mask
}
#[inline(always)]
fn flat_cache_index(key: u128) -> usize {
packed_key_hash(key) as usize & (FLAT_CACHE_SIZE - 1)
}
#[derive(Clone, Copy, Default)]
#[repr(C)]
struct FrontCacheSlot {
key: [u64; 2],
value: u64,
extension: u64,
}
const _: () = assert!(std::mem::size_of::<FrontCacheSlot>() == 32);
#[inline(always)]
fn append_front_value(out: &mut Vec<u32>, value: u64, extension: u64) {
debug_assert!(out.capacity() - out.len() >= 4);
let ids = ((value >> 8) & 0x00ff_ffff) | (value & 0xffff_ffff_0000_0000);
let start = out.len();
unsafe {
(out.as_mut_ptr().add(start) as *mut u64).write_unaligned(ids);
(out.as_mut_ptr().add(start + 2) as *mut u64).write_unaligned(extension);
out.set_len(start + (value as u8 as usize));
}
}
#[inline(always)]
fn append_inline_value(out: &mut Vec<u32>, ids: &[u32; 2], len: usize) {
debug_assert!(len <= 2 && out.capacity() - out.len() >= 2);
let start = out.len();
unsafe {
std::ptr::copy_nonoverlapping(ids.as_ptr(), out.as_mut_ptr().add(start), 2);
out.set_len(start + len);
}
}
#[derive(Clone, Copy)]
#[repr(C)]
struct CacheSlot {
key: u128,
ids: [u32; 2],
offset: u32,
len: u16,
_padding: u16,
}
const FLAT_CACHE_MAX_LOAD: usize = FLAT_CACHE_SIZE * 3 / 4;
struct FlatCache {
bpe_id: usize,
front: Vec<FrontCacheSlot>,
front_mask: usize,
slots: Vec<CacheSlot>,
pool: Vec<u32>,
long: FxHashMap<Box<str>, (u32, u16)>,
count: usize,
}
impl FlatCache {
fn new() -> Self {
Self::with_front_size(FRONT_CACHE_SIZE)
}
fn new_parallel() -> Self {
Self::with_front_size(PARALLEL_FRONT_CACHE_SIZE)
}
fn with_front_size(front_size: usize) -> Self {
debug_assert!(front_size.is_power_of_two());
Self {
bpe_id: 0,
front: vec![FrontCacheSlot::default(); front_size],
front_mask: front_size - 1,
slots: vec![
CacheSlot {
key: EMPTY_SHORT_KEY,
ids: [0; 2],
offset: 0,
len: 0,
_padding: 0,
};
FLAT_CACHE_SIZE
],
pool: Vec::with_capacity(256 * 1024),
long: HashMap::with_hasher(FxBuildHasher),
count: 0,
}
}
#[inline(always)]
fn front_index(&self, key: u128) -> usize {
front_cache_index(key, self.front_mask)
}
fn clear(&mut self) {
self.front.fill(FrontCacheSlot::default());
self.clear_backing();
}
fn clear_backing(&mut self) {
for slot in &mut self.slots {
slot.key = EMPTY_SHORT_KEY;
}
self.pool.clear();
self.long.clear();
self.count = 0;
}
#[inline(always)]
fn prefetch_front(&self, slot: *const FrontCacheSlot) {
#[cfg(target_arch = "aarch64")]
unsafe {
core::arch::asm!(
"prfm pldl1keep, [{ptr}]",
ptr = in(reg) slot,
options(readonly, nostack, preserves_flags)
);
}
#[cfg(target_arch = "x86_64")]
unsafe {
use core::arch::x86_64::{_MM_HINT_T0, _mm_prefetch};
_mm_prefetch(slot.cast(), _MM_HINT_T0);
}
#[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
let _ = slot;
}
#[inline(always)]
fn get(&mut self, key: &str, out: &mut Vec<u32>) -> bool {
let packed = pack_short_key(key).unwrap_or(EMPTY_SHORT_KEY);
out.reserve(4);
self.get_piece(key, packed, out)
}
#[inline(always)]
fn get_piece(&mut self, key: &str, packed: u128, out: &mut Vec<u32>) -> bool {
if packed != EMPTY_SHORT_KEY {
return self.get_packed(packed, out);
}
let Some(&(offset, len)) = self.long.get(key) else {
return false;
};
let start = offset as usize;
out.extend_from_slice(unsafe { self.pool.get_unchecked(start..start + len as usize) });
true
}
#[inline(always)]
fn get_packed(&mut self, packed: u128, out: &mut Vec<u32>) -> bool {
self.get_front_packed(packed, out) || self.get_packed_backing(packed, out)
}
#[inline(always)]
fn get_front_packed(&self, packed: u128, out: &mut Vec<u32>) -> bool {
let Some((value, extension)) = self.front_packed_value(packed) else {
return false;
};
append_front_value(out, value, extension);
true
}
#[inline(always)]
fn front_packed_value(&self, packed: u128) -> Option<(u64, u64)> {
if packed == EMPTY_SHORT_KEY {
return None;
}
let index = self.front_index(packed);
let slot = unsafe { self.front.as_ptr().add(index) };
let key = [packed as u64, (packed >> 64) as u64];
let (value, extension, found) = self.front_packed_value_at(key, slot);
found.then_some((value, extension))
}
#[inline(always)]
fn front_packed_value_at(
&self,
key: [u64; 2],
slot: *const FrontCacheSlot,
) -> (u64, u64, bool) {
debug_assert_ne!(key, [0; 2]);
let slot = unsafe { &*slot };
(slot.value, slot.extension, slot.key == key)
}
#[inline(always)]
fn get_packed_backing(&mut self, packed: u128, out: &mut Vec<u32>) -> bool {
let mut idx = flat_cache_index(packed);
loop {
let slot = unsafe { *self.slots.get_unchecked(idx) };
if slot.key == packed {
let output_start = out.len();
if slot.len <= 2 {
append_inline_value(out, &slot.ids, slot.len as usize);
} else {
let start = slot.offset as usize;
let end = start + slot.len as usize;
out.extend_from_slice(unsafe { self.pool.get_unchecked(start..end) });
}
if slot.len <= 4 {
self.insert_front(packed, &out[output_start..]);
}
return true;
}
if slot.key == EMPTY_SHORT_KEY {
return false;
}
idx = (idx + 1) & (FLAT_CACHE_SIZE - 1);
}
}
#[inline(always)]
fn insert(&mut self, key: &str, ids: &[u32]) {
let packed = pack_short_key(key).unwrap_or(EMPTY_SHORT_KEY);
self.insert_piece(key, packed, ids);
}
#[inline(always)]
fn insert_piece(&mut self, key: &str, packed: u128, ids: &[u32]) {
if packed != EMPTY_SHORT_KEY {
self.insert_packed(packed, ids);
return;
}
let Ok(offset) = u32::try_from(self.pool.len()) else {
return;
};
let Ok(len) = u16::try_from(ids.len()) else {
return;
};
self.pool.extend_from_slice(ids);
self.long.insert(key.into(), (offset, len));
}
#[inline(always)]
fn insert_packed(&mut self, packed: u128, ids: &[u32]) {
if self.insert_packed_backing(packed, ids) {
self.insert_front(packed, ids);
}
}
fn insert_packed_backing(&mut self, packed: u128, ids: &[u32]) -> bool {
if packed == EMPTY_SHORT_KEY {
return false;
}
let Ok(len) = u16::try_from(ids.len()) else {
return false;
};
if self.count >= FLAT_CACHE_MAX_LOAD {
self.clear_backing();
}
let mut idx = flat_cache_index(packed);
loop {
let slot = unsafe { *self.slots.get_unchecked(idx) };
if slot.key == EMPTY_SHORT_KEY {
self.count += 1;
let offset = self.store_spilled(ids);
let slot = unsafe { self.slots.get_unchecked_mut(idx) };
slot.key = packed;
slot.ids[..ids.len().min(2)].copy_from_slice(&ids[..ids.len().min(2)]);
slot.offset = offset;
slot.len = len;
return true;
}
if slot.key == packed {
let offset = self.store_spilled(ids);
let slot = unsafe { self.slots.get_unchecked_mut(idx) };
slot.ids[..ids.len().min(2)].copy_from_slice(&ids[..ids.len().min(2)]);
slot.offset = offset;
slot.len = len;
return true;
}
idx = (idx + 1) & (FLAT_CACHE_SIZE - 1);
}
}
#[inline(always)]
fn store_spilled(&mut self, ids: &[u32]) -> u32 {
if ids.len() <= 2 {
return 0;
}
let offset = self.pool.len() as u32;
self.pool.extend_from_slice(ids);
offset
}
#[inline(always)]
fn insert_front(&mut self, key: u128, ids: &[u32]) {
if !(1..=4).contains(&ids.len()) || ids[0] >= 1 << 24 {
return;
}
let second = ids.get(1).copied().unwrap_or(0);
let third = ids.get(2).copied().unwrap_or(0);
let fourth = ids.get(3).copied().unwrap_or(0);
let value = ids.len() as u64 | (ids[0] as u64) << 8 | (second as u64) << 32;
let extension = third as u64 | (fourth as u64) << 32;
let slot = FrontCacheSlot {
key: [key as u64, (key >> 64) as u64],
value,
extension,
};
let index = self.front_index(key);
self.front[index] = slot;
}
}
thread_local! {
static TL_BPE_CACHE: RefCell<FlatCache> = RefCell::new(FlatCache::new());
static TL_FUSED_CACHE: RefCell<FlatCache> = RefCell::new(FlatCache::new());
static TL_FUSED_PARALLEL_CACHE: RefCell<FlatCache> = RefCell::new(FlatCache::new_parallel());
}
#[derive(Clone, Copy)]
struct FusedPiece {
slot: *const FrontCacheSlot,
key: [u64; 2],
}
const _: () = assert!(std::mem::size_of::<FusedPiece>() == 24);
pub(crate) struct FusedStream<'a> {
model: &'a Bpe,
cache: &'a mut FlatCache,
out: &'a mut Vec<u32>,
error: Option<String>,
pending: &'a mut [MaybeUninit<FusedPiece>; FUSED_PIECE_CAPACITY],
pending_len: usize,
}
impl FusedStream<'_> {
#[inline(always)]
pub(crate) fn push_id(&mut self, id: u32) {
self.flush();
if self.error.is_none() {
self.out.push(id);
}
}
#[inline(always)]
pub(crate) fn flush_pending(&mut self) {
self.flush();
}
#[inline(always)]
pub(crate) fn output_len(&mut self) -> usize {
self.flush_pending();
self.out.len()
}
#[inline(always)]
pub(crate) unsafe fn push(&mut self, input: &str, start: usize, end: usize) {
if self.pending_len >= FUSED_PIECE_BATCH {
self.flush();
if self.error.is_some() {
return;
}
}
let len = end - start;
if len > 15 {
self.push_long(input, start, end);
return;
}
let front = self.cache.front.as_ptr();
let pending = unsafe {
self.pending
.as_mut_ptr()
.add(self.pending_len)
.cast::<FusedPiece>()
};
unsafe { self.push_short::<false>(input, start, end, front, pending) };
self.pending_len += 1;
}
#[inline(always)]
unsafe fn push_short<const INBOUNDS: bool>(
&mut self,
input: &str,
start: usize,
end: usize,
front: *const FrontCacheSlot,
pending: *mut FusedPiece,
) {
let len = end - start;
debug_assert!(len <= 15);
let packed = if INBOUNDS {
unsafe { pack_short_range_inbounds(input, start, len) }
} else {
pack_short_range(input, start, end)
};
let index = self.cache.front_index(packed);
let slot = unsafe { front.add(index) };
unsafe {
pending.write(FusedPiece {
slot,
key: [packed as u64, (packed >> 64) as u64],
})
};
self.cache.prefetch_front(slot);
}
#[cold]
#[inline(never)]
fn push_long(&mut self, input: &str, start: usize, end: usize) {
self.flush();
if self.error.is_none()
&& let Err(current) = self.model.tokenize_fused_cache_miss(
self.cache,
input,
start..end,
EMPTY_SHORT_KEY,
self.out,
false,
)
{
self.error = Some(current);
}
}
#[inline(never)]
fn flush(&mut self) {
let count = std::mem::take(&mut self.pending_len);
if count == 0 || self.error.is_some() {
return;
}
let out = &mut *self.out;
out.reserve(4 * count);
let mut destination = unsafe { out.as_mut_ptr().add(out.len()) };
let pending = unsafe {
std::slice::from_raw_parts(self.pending.as_ptr().cast::<FusedPiece>(), count)
};
for (index, &piece) in pending.iter().enumerate() {
let (value, extension, found) = self.cache.front_packed_value_at(piece.key, piece.slot);
let ids = ((value >> 8) & 0x00ff_ffff) | (value & 0xffff_ffff_0000_0000);
unsafe {
(destination as *mut u64).write_unaligned(ids);
(destination.add(2) as *mut u64).write_unaligned(extension);
destination = destination.add(if found { value as u8 as usize } else { 0 });
}
if found {
continue;
}
unsafe { out.set_len(destination.offset_from(out.as_ptr()) as usize) };
let packed = piece.key[0] as u128 | (piece.key[1] as u128) << 64;
let result = if self.cache.get_packed_backing(packed, out) {
Ok(())
} else {
let bytes = packed.to_le_bytes();
let len = (piece.key[1] >> 56) as usize;
let input = unsafe { std::str::from_utf8_unchecked(&bytes[..len]) };
self.model
.tokenize_fused_uncached(self.cache, input, 0..len, packed, out, false)
};
if let Err(current) = result {
self.error = Some(current);
return;
}
out.reserve(4 * (count - index - 1));
destination = unsafe { out.as_mut_ptr().add(out.len()) };
}
unsafe { out.set_len(destination.offset_from(out.as_ptr()) as usize) };
}
}
impl FusedPieceSink for FusedStream<'_> {
#[inline(always)]
unsafe fn push_piece(&mut self, input: &str, start: usize, end: usize) {
unsafe { self.push(input, start, end) };
}
#[inline(always)]
unsafe fn push_mask(&mut self, input: &str, mask_base: usize, start: &mut usize, mask: u64) {
let inbounds = input.len().saturating_sub(mask_base) >= 78;
let first_end = mask_base + mask.trailing_zeros() as usize;
let mut nearby = mask << 1;
nearby |= nearby << 1;
nearby |= nearby << 2;
nearby |= nearby << 4;
nearby |= nearby << 7;
let all_short = first_end - *start <= 15 && mask & (mask - 1) & !nearby == 0;
if all_short && inbounds {
unsafe { self.push_mask_ranges::<true, true>(input, mask_base, start, mask) };
} else if all_short {
unsafe { self.push_mask_ranges::<false, true>(input, mask_base, start, mask) };
} else if inbounds {
unsafe { self.push_mask_ranges::<true, false>(input, mask_base, start, mask) };
} else {
unsafe { self.push_mask_ranges::<false, false>(input, mask_base, start, mask) };
}
}
}
impl FusedStream<'_> {
#[inline(always)]
unsafe fn push_mask_ranges<const INBOUNDS: bool, const ALL_SHORT: bool>(
&mut self,
input: &str,
mask_base: usize,
start: &mut usize,
mut mask: u64,
) {
if self.pending_len >= FUSED_PIECE_BATCH {
self.flush();
}
let front = self.cache.front.as_ptr();
let pending_base = self.pending.as_mut_ptr().cast::<FusedPiece>();
let mut pending = unsafe { pending_base.add(self.pending_len) };
while mask != 0 {
let end = mask_base + mask.trailing_zeros() as usize;
mask &= mask - 1;
if !ALL_SHORT && end - *start > 15 {
self.pending_len = unsafe { pending.offset_from(pending_base) as usize };
self.push_long(input, *start, end);
pending = pending_base;
} else {
unsafe { self.push_short::<INBOUNDS>(input, *start, end, front, pending) };
pending = unsafe { pending.add(1) };
}
*start = end;
}
self.pending_len = unsafe { pending.offset_from(pending_base) as usize };
}
}
const CACHE_SHARDS: usize = 64;
struct SharedCache {
shards: Vec<Mutex<FxHashMap<String, Vec<u32>>>>,
}
impl SharedCache {
fn new() -> Self {
Self {
shards: (0..CACHE_SHARDS)
.map(|_| Mutex::new(HashMap::with_hasher(FxBuildHasher)))
.collect(),
}
}
#[inline]
fn shard_index(key: &str) -> usize {
let bytes = key.as_bytes();
let mut h: u64 = bytes.len() as u64;
for &b in &bytes[..bytes.len().min(8)] {
h = h.wrapping_add(b as u64).wrapping_mul(0x9E3779B97F4A7C15);
}
h as usize & (CACHE_SHARDS - 1)
}
#[inline]
fn get_into(&self, key: &str, out: &mut Vec<u32>) -> bool {
let shard = self.shards[Self::shard_index(key)].lock().unwrap();
if let Some(ids) = shard.get(key) {
out.extend_from_slice(ids);
true
} else {
false
}
}
fn insert(&self, key: String, value: Vec<u32>) {
self.shards[Self::shard_index(&key)]
.lock()
.unwrap()
.insert(key, value);
}
}
#[derive(Deserialize)]
struct RawBpe {
#[serde(default)]
vocab: Vocab,
#[serde(default)]
merges: Vec<Value>,
#[serde(default)]
byte_fallback: bool,
#[serde(default)]
ignore_merges: bool,
}
#[derive(Encode, Decode)]
struct ResolvedMerge {
left: u32,
right: u32,
rank: u32,
merged: u32,
}
#[derive(Encode, Decode)]
struct ResolvedDecomposition {
unmerge_map: Vec<(TokenId, TokenId)>,
is_orphan: Vec<bool>,
}
impl ResolvedDecomposition {
fn validate(
self,
vocab_size: usize,
merge_map: &ParsedMergeMap,
ignore_merges: bool,
) -> Result<Self> {
if self.unmerge_map.len() != vocab_size || self.is_orphan.len() != vocab_size {
return Err("invalid .tkz decomposition length".into());
}
if ignore_merges && self.is_orphan.iter().any(|&is_orphan| is_orphan) {
return Err("ignore_merges .tkz model contains an orphan token".into());
}
for (token, &(left, right)) in self.unmerge_map.iter().enumerate() {
if left as usize >= vocab_size || right as usize >= vocab_size {
return Err("out-of-range .tkz decomposition token".into());
}
let token = token as TokenId;
if (left, right) == (token, token) {
continue;
}
if self.is_orphan[token as usize]
|| merge_map
.get(&(left, right))
.is_none_or(|&(_, merged)| merged != token)
{
return Err("invalid .tkz decomposition pair".into());
}
}
Ok(self)
}
}
#[derive(Encode, Decode)]
pub(crate) struct ResolvedBpe {
id_to_token: Vec<String>,
merges: Vec<ResolvedMerge>,
decomposition: ResolvedDecomposition,
ranked_slot_indices: Vec<u32>,
byte_fallback: bool,
ignore_merges: bool,
}
static BPE_ID_COUNTER: AtomicUsize = AtomicUsize::new(1);
#[derive(Clone, Copy, Eq, PartialEq)]
#[repr(C)]
struct MergeEntry {
key: u64,
val: u64,
}
impl MergeEntry {
#[inline(always)]
fn new(rank: u32, pos: u32, left_c: u32, right_c: u32) -> Self {
Self {
key: (rank as u64) << 32 | pos as u64,
val: (left_c as u64) << 32 | right_c as u64,
}
}
#[inline(always)]
fn pos(&self) -> u32 {
self.key as u32
}
#[inline(always)]
fn left_c(&self) -> u32 {
(self.val >> 32) as u32
}
#[inline(always)]
fn right_c(&self) -> u32 {
self.val as u32
}
}
impl Ord for MergeEntry {
#[inline(always)]
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.key.cmp(&other.key)
}
}
impl PartialOrd for MergeEntry {
#[inline(always)]
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
#[derive(Clone, Copy)]
struct MergeSymbol {
c: u32,
prev: i32,
next: i32,
}
#[derive(Default)]
struct MergeScratch {
symbols: Vec<MergeSymbol>,
heap: BinaryHeap<Reverse<MergeEntry>>,
heap_buf: Vec<Reverse<MergeEntry>>,
}
#[derive(Default)]
struct EncodedMergeScratch {
symbols: Vec<MergeSymbol>,
heap: QuaternaryHeap<Reverse<MergeEntry>>,
}
impl EncodedMergeScratch {
#[inline(always)]
fn push_encoded_symbol(&mut self, token: TokenId) {
let index = self.symbols.len() as i32;
if let Some(previous) = self.symbols.last_mut() {
previous.next = index;
}
self.symbols.push(MergeSymbol {
c: token,
prev: index - 1,
next: -1,
});
}
}
macro_rules! run_merge_loop_body {
($bpe:ident, $scratch:ident, $out:ident) => {{
let symbols = &mut $scratch.symbols;
let heap = &mut $scratch.heap;
while let Some(Reverse(entry)) = heap.pop() {
let pos = entry.pos() as usize;
let sym = symbols[pos];
let left_c = entry.left_c();
let right_c = entry.right_c();
if sym.c != left_c {
continue;
}
let next_idx = sym.next;
if next_idx < 0 {
continue;
}
let next_idx = next_idx as usize;
let next_sym = symbols[next_idx];
if next_sym.c != right_c {
continue;
}
let new_id = match $bpe.merge_adj.get(left_c, right_c) {
Some((_, nid)) => nid,
None => continue,
};
symbols[pos].c = new_id;
symbols[pos].next = next_sym.next;
if next_sym.next >= 0 {
symbols[next_sym.next as usize].prev = pos as i32;
}
symbols[next_idx].c = INVALID_TOKEN;
if sym.prev >= 0 {
let prev_c = symbols[sym.prev as usize].c;
if let Some((rank, _)) = $bpe.merge_adj.get(prev_c, new_id) {
heap.push(Reverse(MergeEntry::new(
rank,
sym.prev as u32,
prev_c,
new_id,
)));
}
}
let new_next = symbols[pos].next;
if new_next >= 0 {
let next_c = symbols[new_next as usize].c;
if let Some((rank, _)) = $bpe.merge_adj.get(new_id, next_c) {
heap.push(Reverse(MergeEntry::new(rank, pos as u32, new_id, next_c)));
}
}
}
let mut index = 0_i32;
while index >= 0 {
let symbol = symbols[index as usize];
$out.push(symbol.c);
index = symbol.next;
}
}};
}
thread_local! {
static TL_MERGE_SCRATCH: RefCell<MergeScratch> = RefCell::new(MergeScratch::default());
static TL_ENCODED_MERGE_SCRATCH: RefCell<EncodedMergeScratch> =
RefCell::new(EncodedMergeScratch::default());
}
#[derive(Clone, Copy, PartialEq)]
#[repr(C)]
struct RankedMergeSlot {
key: u64,
rank: u32,
id: u32,
}
#[derive(Clone, PartialEq)]
struct RankedMergeMap {
mask: usize,
slots: Vec<RankedMergeSlot>,
}
impl RankedMergeMap {
fn from_parsed(parsed: &ParsedMergeMap) -> Self {
if parsed.is_empty() {
return Self {
mask: 0,
slots: Vec::new(),
};
}
let capacity = (parsed.len() * 2).next_power_of_two();
let mask = capacity - 1;
let mut slots = vec![
RankedMergeSlot {
key: EMPTY_KEY,
rank: 0,
id: 0
};
capacity
];
for (&(t1, t2), &(rank, merged_id)) in parsed {
let key = pack_pair(t1, t2);
let mut idx = fx_hash(key) as usize & mask;
loop {
if slots[idx].key == EMPTY_KEY {
slots[idx] = RankedMergeSlot {
key,
rank,
id: merged_id,
};
break;
}
idx = (idx + 1) & mask;
}
}
Self { mask, slots }
}
fn from_cached_indices(merges: &[(ResolvedMerge, u32)]) -> Result<Self> {
if merges.is_empty() {
return Ok(Self {
mask: 0,
slots: Vec::new(),
});
}
let capacity = merges
.len()
.checked_mul(2)
.and_then(usize::checked_next_power_of_two)
.ok_or("ranked .tkz table capacity overflow")?;
let mask = capacity - 1;
let empty = RankedMergeSlot {
key: EMPTY_KEY,
rank: 0,
id: 0,
};
let mut slots = vec![empty; capacity];
for (merge, slot_index) in merges {
let slot = slots
.get_mut(*slot_index as usize)
.ok_or("out-of-range ranked .tkz slot")?;
if slot.key != EMPTY_KEY {
return Err("duplicate ranked .tkz slot".into());
}
*slot = RankedMergeSlot {
key: pack_pair(merge.left, merge.right),
rank: merge.rank,
id: merge.merged,
};
}
let first_empty = slots
.iter()
.position(|slot| slot.key == EMPTY_KEY)
.ok_or("ranked .tkz table has no empty slot")?;
let mut cluster_start = 1;
for step in 1..capacity {
let slot = slots[(first_empty + step) & mask];
if slot.key == EMPTY_KEY {
cluster_start = step + 1;
continue;
}
let home = fx_hash(slot.key) as usize & mask;
let relative_home = home.wrapping_add(capacity).wrapping_sub(first_empty) & mask;
if relative_home < cluster_start || relative_home > step {
return Err("invalid ranked .tkz probe chain".into());
}
}
Ok(Self { mask, slots })
}
#[inline(always)]
fn get(&self, t1: u32, t2: u32) -> Option<(u32, u32)> {
if self.slots.is_empty() {
return None;
}
let key = pack_pair(t1, t2);
let mut idx = fx_hash(key) as usize & self.mask;
loop {
let slot = unsafe { self.slots.get_unchecked(idx) };
if slot.key == key {
return Some((slot.rank, slot.id));
}
if slot.key == EMPTY_KEY {
return None;
}
idx = (idx + 1) & self.mask;
}
}
fn len(&self) -> usize {
self.slots
.iter()
.filter(|slot| slot.key != EMPTY_KEY)
.count()
}
}
#[derive(Clone)]
struct MergeAdjacency {
offsets: Vec<u32>,
data: Vec<(u32, u32, u32)>, }
impl MergeAdjacency {
fn from_parsed(parsed: &ParsedMergeMap, vocab_size: usize) -> Self {
let mut counts = vec![0u32; vocab_size];
for &(left, _right) in parsed.keys() {
counts[left as usize] += 1;
}
let mut offsets = Vec::with_capacity(vocab_size + 1);
offsets.push(0u32);
let mut running = 0u32;
for &c in &counts {
running += c;
offsets.push(running);
}
let mut data = vec![(0u32, 0u32, 0u32); running as usize];
let mut write_pos = offsets[..vocab_size].to_vec();
for (&(left, right), &(rank, merged_id)) in parsed {
let idx = write_pos[left as usize] as usize;
data[idx] = (right, rank, merged_id);
write_pos[left as usize] += 1;
}
for i in 0..vocab_size {
let start = offsets[i] as usize;
let end = offsets[i + 1] as usize;
data[start..end].sort_unstable_by_key(|&(neighbor, _, _)| neighbor);
}
Self { offsets, data }
}
#[inline(always)]
fn get(&self, left: u32, right: u32) -> Option<(u32, u32)> {
let start = unsafe { *self.offsets.get_unchecked(left as usize) } as usize;
let end = unsafe { *self.offsets.get_unchecked(left as usize + 1) } as usize;
let slice = unsafe { self.data.get_unchecked(start..end) };
match slice.binary_search_by_key(&right, |&(n, _, _)| n) {
Ok(idx) => {
let entry = unsafe { slice.get_unchecked(idx) };
Some((entry.1, entry.2))
}
Err(_) => None,
}
}
}
#[derive(Deserialize)]
#[serde(try_from = "RawBpe")]
pub struct Bpe {
#[serde(skip)]
id: usize,
daac: DoubleArrayAhoCorasick<TokenId>,
unmerge_map: Vec<(TokenId, TokenId)>,
token_lens: Vec<u16>,
shared_cache: SharedCache,
fused_shared_cache: SharedCache,
id_to_token: Vec<String>,
token_to_id: HashMap<String, u32>,
byte_to_initial_token: [u32; 256],
byte_fallback_token_ids: [u32; 256],
single_char_token: [u32; 128],
ranked_merge_map: RankedMergeMap,
byte_pair_initial: Vec<(u32, u32)>,
dense_merge: Vec<u64>,
dense_ranked_merge: Vec<u32>,
ranked_merges: bool,
fused_cache_seeds: Vec<(u128, u32)>,
merge_adj: MergeAdjacency,
ignore_merges: bool,
byte_fallback: bool,
pub bigram_bridge_table: BigramBridgeTable,
}
impl TryFrom<RawBpe> for Bpe {
type Error = String;
fn try_from(raw: RawBpe) -> Result<Self> {
let merge_map = parse_merges(&raw.vocab, &raw.merges)?;
Self::build(
raw.vocab,
merge_map,
raw.byte_fallback,
raw.ignore_merges,
None,
)
}
}
enum Decomposition {
Pair(TokenId, TokenId),
CharsNotInVocab,
Stuck,
}
fn encoding_decomposition(text: &str, vocab: &Vocab, merge_map: &ParsedMergeMap) -> Decomposition {
let mut tokens: Vec<TokenId> = Vec::new();
for ch in text.chars() {
let mut buf = [0u8; 4];
let s = ch.encode_utf8(&mut buf);
match vocab.get(s) {
Some(&tid) => tokens.push(tid),
None => return Decomposition::CharsNotInVocab,
}
}
if tokens.len() < 2 {
return Decomposition::CharsNotInVocab;
}
loop {
let mut best_rank = u32::MAX;
let mut best_pos = usize::MAX;
let mut best_new = 0;
for i in 0..tokens.len() - 1 {
let pair = (tokens[i], tokens[i + 1]);
if let Some(&(rank, new_id)) = merge_map.get(&pair)
&& rank < best_rank
{
best_rank = rank;
best_pos = i;
best_new = new_id;
}
}
if best_pos == usize::MAX {
return Decomposition::Stuck;
}
if tokens.len() == 2 {
return Decomposition::Pair(tokens[0], tokens[1]);
}
tokens[best_pos] = best_new;
tokens.remove(best_pos + 1);
}
}
fn parse_merges(vocab: &Vocab, merges: &[Value]) -> Result<ParsedMergeMap> {
let mut merge_map = ParsedMergeMap::with_capacity(merges.len());
let mut merged = String::new();
for (rank, entry) in merges.iter().enumerate() {
let (left, right) = parse_merge_entry(entry)?;
let &left_id = vocab
.get(left)
.ok_or_else(|| format!("merge token not in vocab: {left:?}"))?;
let &right_id = vocab
.get(right)
.ok_or_else(|| format!("merge token not in vocab: {right:?}"))?;
merged.clear();
merged.push_str(left);
merged.push_str(right);
let &merged_id = vocab
.get(merged.as_str())
.ok_or_else(|| format!("merged token not in vocab: {merged:?}"))?;
merge_map.insert((left_id, right_id), (rank as u32, merged_id));
}
Ok(merge_map)
}
fn parse_merge_entry(entry: &Value) -> Result<(&str, &str)> {
match entry {
Value::String(s) => {
let (left, right) = s
.split_once(' ')
.ok_or_else(|| format!("invalid merge entry (no space): {s:?}"))?;
Ok((left, right))
}
Value::Array(arr) if arr.len() == 2 => {
let left = arr[0]
.as_str()
.ok_or_else(|| format!("merge element not a string: {:?}", arr[0]))?;
let right = arr[1]
.as_str()
.ok_or_else(|| format!("merge element not a string: {:?}", arr[1]))?;
Ok((left, right))
}
_ => Err(format!("unrecognized merge entry format: {entry:?}")),
}
}
impl Bpe {
pub(crate) fn resolved_config(&self) -> ResolvedBpe {
let mut merges = self
.ranked_merge_map
.slots
.iter()
.enumerate()
.filter(|(_, slot)| slot.key != EMPTY_KEY)
.map(|(slot_index, slot)| {
(
ResolvedMerge {
left: (slot.key >> 32) as u32,
right: slot.key as u32,
rank: slot.rank,
merged: slot.id,
},
slot_index as u32,
)
})
.collect::<Vec<_>>();
merges.sort_unstable_by_key(|(merge, _)| merge.rank);
let (merges, ranked_slot_indices) = merges.into_iter().unzip();
let is_orphan = self
.unmerge_map
.iter()
.enumerate()
.map(|(token, &pair)| {
let token = token as TokenId;
pair == (token, token)
&& self.next_match(&self.id_to_token[token as usize]) != Some(token)
})
.collect();
ResolvedBpe {
id_to_token: self.id_to_token.clone(),
merges,
decomposition: ResolvedDecomposition {
unmerge_map: self.unmerge_map.clone(),
is_orphan,
},
ranked_slot_indices,
byte_fallback: self.byte_fallback,
ignore_merges: self.ignore_merges,
}
}
pub(crate) fn from_resolved(resolved: ResolvedBpe) -> Result<Self> {
let ResolvedBpe {
id_to_token,
merges,
decomposition,
ranked_slot_indices,
byte_fallback,
ignore_merges,
} = resolved;
let vocab_size = id_to_token.len();
if vocab_size == 0 || vocab_size > u32::MAX as usize {
return Err("invalid .tkz vocabulary size".into());
}
let vocab = id_to_token
.into_iter()
.enumerate()
.map(|(id, token)| (token, id as u32))
.collect::<Vocab>();
if vocab.len() != vocab_size {
return Err("duplicate token text in .tkz vocabulary".into());
}
if merges.len() != ranked_slot_indices.len() {
return Err("ranked .tkz index count mismatch".into());
}
let mut merges = merges
.into_iter()
.zip(ranked_slot_indices)
.collect::<Vec<_>>();
merges.sort_unstable_by_key(|(merge, _)| merge.rank);
if merges
.windows(2)
.any(|pair| pair[0].0.rank == pair[1].0.rank)
{
return Err("duplicate merge rank in .tkz model".into());
}
let mut merge_map = ParsedMergeMap::with_capacity(merges.len());
for (expected_rank, (merge, _)) in merges.iter().enumerate() {
if merge.left as usize >= vocab_size
|| merge.right as usize >= vocab_size
|| merge.merged as usize >= vocab_size
{
return Err("out-of-range merge token in .tkz model".into());
}
if merge.rank as usize != expected_rank {
return Err("out-of-range ranked .tkz token".into());
}
if merge_map
.insert((merge.left, merge.right), (merge.rank, merge.merged))
.is_some()
{
return Err("duplicate merge pair in .tkz model".into());
}
}
let decomposition = decomposition.validate(vocab_size, &merge_map, ignore_merges)?;
let ranked_merge_map = RankedMergeMap::from_cached_indices(&merges)?;
Self::build(
vocab,
merge_map,
byte_fallback,
ignore_merges,
Some((decomposition, ranked_merge_map)),
)
}
pub fn bigram_bridge_table(&self) -> Option<&BigramBridgeTable> {
(!self.ignore_merges).then_some(&self.bigram_bridge_table)
}
pub fn new(vocab: &Vocab, merge_map: ParsedMergeMap) -> Result<Self> {
if vocab.is_empty() {
return Err("cannot build Bpe with empty vocabulary".into());
}
let vocab_size = vocab.len();
if merge_map.iter().any(|(&(left, right), &(_, merged))| {
left as usize >= vocab_size
|| right as usize >= vocab_size
|| merged as usize >= vocab_size
}) {
return Err("merge token id exceeds vocabulary size".into());
}
Self::build(vocab.clone(), merge_map, false, false, None)
}
fn build(
vocab: Vocab,
merge_map: ParsedMergeMap,
byte_fallback: bool,
ignore_merges: bool,
cached_tables: Option<(ResolvedDecomposition, RankedMergeMap)>,
) -> Result<Self> {
if vocab.is_empty() {
return Err("cannot build Bpe with empty vocabulary".into());
}
let (decomposition, ranked_merge_map) = cached_tables.unzip();
let mut ordered_tokens = vec![None; vocab.len()];
for (text, &token) in &vocab {
let slot = ordered_tokens.get_mut(token as usize).ok_or_else(|| {
format!("non-contiguous tokens - token id {token} exceeds vocabulary size")
})?;
if slot.replace(text.as_str()).is_some() {
return Err(format!("duplicate token id {token}"));
}
}
let id_to_token = ordered_tokens
.into_iter()
.enumerate()
.map(|(token, text)| {
text.ok_or_else(|| format!("non-contiguous tokens - token {token} is missing"))
.map(str::to_owned)
})
.collect::<std::result::Result<Vec<_>, _>>()?;
let max_token =
u32::try_from(id_to_token.len() - 1).map_err(|_| "vocabulary exceeds u32 token IDs")?;
let (unmerge_map, mut is_orphan) = if let Some(decomposition) = decomposition {
(decomposition.unmerge_map, decomposition.is_orphan)
} else {
let mut unmerge_map = (0..=max_token).map(|t| (t, t)).collect::<Vec<_>>();
let mut is_orphan = vec![false; (max_token + 1) as usize];
for (tid, text) in id_to_token.iter().enumerate() {
if text.chars().count() < 2 {
continue;
}
match encoding_decomposition(text, &vocab, &merge_map) {
Decomposition::Pair(left, right) => {
unmerge_map[tid] = (left, right);
}
Decomposition::Stuck => {
is_orphan[tid] = true;
}
Decomposition::CharsNotInVocab => {}
}
}
(unmerge_map, is_orphan)
};
if ignore_merges {
is_orphan.fill(false);
}
let ranked_merge_map =
ranked_merge_map.unwrap_or_else(|| RankedMergeMap::from_parsed(&merge_map));
let mut byte_to_initial_token = [INVALID_TOKEN; 256];
for byte_val in 0u16..256 {
let ch = BYTE_TO_CHAR[byte_val as usize];
let mut buf = [0u8; 4];
let s = ch.encode_utf8(&mut buf);
if let Some(&id) = vocab.get(s) {
byte_to_initial_token[byte_val as usize] = id;
}
}
let mut byte_fallback_token_ids = [INVALID_TOKEN; 256];
if byte_fallback {
for byte_val in 0u16..256 {
let token = format!("<0x{byte_val:02X}>");
if let Some(&id) = vocab.get(token.as_str()) {
byte_fallback_token_ids[byte_val as usize] = id;
}
}
}
let (daac, byte_pair_initial) = rayon::join(
|| {
let patterns = id_to_token
.iter()
.enumerate()
.filter_map(|(token, pattern)| {
(!is_orphan[token]).then_some((pattern, token as TokenId))
});
DoubleArrayAhoCorasickBuilder::new()
.match_kind(daachorse::MatchKind::LeftmostLongest)
.build_with_values(patterns)
.map_err(|e| format!("error building DAAC: {e}"))
},
|| {
let mut table = vec![(u32::MAX, 0u32); 65536];
for b1 in 0u16..256 {
let t1 = byte_to_initial_token[b1 as usize];
if t1 == INVALID_TOKEN {
continue;
}
for b2 in 0u16..256 {
let t2 = byte_to_initial_token[b2 as usize];
if t2 == INVALID_TOKEN {
continue;
}
if let Some((rank, new_id)) = ranked_merge_map.get(t1, t2) {
table[b1 as usize * 256 + b2 as usize] = (rank, new_id);
}
}
}
table
},
);
let daac = daac?;
let token_lens = id_to_token
.iter()
.enumerate()
.map(|(token, text)| {
u16::try_from(text.len())
.map_err(|_| format!("token {token} length {} exceeds u16::MAX", text.len()))
})
.collect::<std::result::Result<Vec<_>, _>>()?;
let mut single_char_token = [INVALID_TOKEN; 128];
for (byte, slot) in single_char_token.iter_mut().enumerate() {
let ch = byte as u8 as char;
let mut buf = [0u8; 1];
if let Some(&id) = vocab.get(ch.encode_utf8(&mut buf) as &str) {
*slot = id;
}
}
let vocab_size = id_to_token.len();
let merge_adj = MergeAdjacency::from_parsed(&merge_map, vocab_size);
let rank_offset = merge_map
.values()
.find_map(|&(rank, id)| (rank == 0).then_some(id));
let ranked_merges = rank_offset.is_some_and(|offset| {
merge_map
.values()
.all(|&(rank, id)| rank.checked_add(offset) == Some(id))
});
let dense_ranked_merge = if ranked_merges
&& !byte_fallback
&& byte_to_initial_token
.iter()
.all(|&id| id < DENSE_RANKED_LIMIT)
{
let mut table = vec![u32::MAX; DENSE_RANKED_SIZE];
for (&(left, right), &(_, id)) in &merge_map {
if left < DENSE_RANKED_LIMIT && right < DENSE_RANKED_LIMIT {
let index = (left << DENSE_RANKED_BITS | right) as usize;
table[index] = id;
}
}
table
} else {
Vec::new()
};
let dense_merge = if dense_ranked_merge.is_empty()
&& !byte_fallback
&& byte_to_initial_token
.iter()
.all(|&id| id < DENSE_MERGE_LIMIT)
{
let mut table = vec![u64::MAX; DENSE_MERGE_SIZE];
for (&(left, right), &(rank, id)) in &merge_map {
if left < DENSE_MERGE_LIMIT && right < DENSE_MERGE_LIMIT {
let index = (left << DENSE_MERGE_BITS | right) as usize;
table[index] = (rank as u64) << 32 | id as u64;
}
}
table
} else {
Vec::new()
};
let fused_cache_seeds = if byte_fallback {
Vec::new()
} else {
let mut inverse = [u16::MAX; 324];
for (byte, &ch) in BYTE_TO_CHAR.iter().enumerate() {
inverse[ch as usize] = byte as u16;
}
id_to_token
.iter()
.enumerate()
.filter_map(|(id, token)| {
if !ignore_merges && is_orphan[id] {
return None;
}
let mut bytes = [0u8; 15];
let mut len = 0;
for ch in token.chars() {
let byte = inverse.get(ch as usize).copied().unwrap_or(u16::MAX);
if byte == u16::MAX || len == bytes.len() {
return None;
}
bytes[len] = byte as u8;
len += 1;
}
let text = std::str::from_utf8(&bytes[..len]).ok()?;
pack_short_key(text).map(|key| (key, id as u32))
})
.collect()
};
let bigram_bridge_table = build_bigram_bridge_table(&id_to_token, byte_fallback);
Ok(Self {
id: BPE_ID_COUNTER.fetch_add(1, Ordering::Relaxed),
daac,
unmerge_map,
token_lens,
shared_cache: SharedCache::new(),
fused_shared_cache: SharedCache::new(),
id_to_token,
token_to_id: vocab,
byte_to_initial_token,
byte_fallback_token_ids,
single_char_token,
ranked_merge_map,
byte_pair_initial,
dense_merge,
dense_ranked_merge,
ranked_merges,
fused_cache_seeds,
merge_adj,
ignore_merges,
byte_fallback,
bigram_bridge_table,
})
}
pub fn is_compatible_token_pair(&self, mut t1: TokenId, mut t2: TokenId) -> bool {
if t1 == INVALID_TOKEN {
return false;
}
let mut limit = u32::MAX;
loop {
if let Some((_rank, t)) = self.ranked_merge_map.get(t1, t2)
&& t < limit
{
return false;
}
if t1 > t2 {
limit = t1;
t1 = self.unmerge_map[t1 as usize].1;
if t1 == limit {
limit = t2 + 1;
t2 = self.unmerge_map[t2 as usize].0;
if t2 + 1 == limit {
return true;
}
}
} else {
limit = t2 + 1;
t2 = self.unmerge_map[t2 as usize].0;
if t2 + 1 == limit {
limit = t1;
t1 = self.unmerge_map[t1 as usize].1;
if t1 == limit {
return true;
}
}
}
}
}
fn next_match(&self, input: &str) -> Option<TokenId> {
let m = self.daac.leftmost_find_iter(input).next()?;
(m.start() == 0).then(|| m.value())
}
pub fn tokenize(&self, input: &str) -> Result<Vec<TokenId>> {
let mut out = Vec::new();
self.tokenize_into(input, &mut out)?;
Ok(out)
}
#[inline(always)]
pub fn tokenize_into(&self, input: &str, out: &mut Vec<u32>) -> Result<()> {
if input.is_empty() {
return Ok(());
}
if let Some(token) = self.next_match(input)
&& self.token_lens[token as usize] as usize == input.len()
{
out.push(token);
return Ok(());
}
let bpe_id = self.id;
let hit = TL_BPE_CACHE.with(|c| {
let mut c = c.borrow_mut();
if c.bpe_id != bpe_id {
return false;
}
c.get(input, out)
});
if hit {
return Ok(());
}
let start = out.len();
if self.shared_cache.get_into(input, out) {
TL_BPE_CACHE.with(|c| {
let mut c = c.borrow_mut();
if c.bpe_id != bpe_id {
c.bpe_id = bpe_id;
c.clear();
}
c.insert(input, &out[start..]);
});
return Ok(());
}
self.merge_all_encoded_into(input, out)?;
let ids = &out[start..];
TL_BPE_CACHE.with(|c| {
let mut c = c.borrow_mut();
if c.bpe_id != bpe_id {
c.bpe_id = bpe_id;
c.clear();
}
c.insert(input, ids);
});
self.shared_cache.insert(input.to_string(), ids.to_vec());
Ok(())
}
fn merge_all_encoded_into(&self, input: &str, out: &mut Vec<u32>) -> Result<()> {
if input.is_empty() {
return Ok(());
}
TL_ENCODED_MERGE_SCRATCH.with(|s| {
let mut scratch = s.borrow_mut();
scratch.symbols.clear();
scratch.heap.clear();
for ch in input.chars() {
let mut buf = [0u8; 4];
let s = ch.encode_utf8(&mut buf);
let found = if ch.is_ascii() {
let id = self.single_char_token[ch as usize];
(id != INVALID_TOKEN).then_some(id)
} else {
self.token_to_id.get(s).copied()
};
if let Some(id) = found {
scratch.push_encoded_symbol(id);
continue;
}
if !self.byte_fallback {
return Err(format!("character {ch:?} not in vocabulary"));
}
for &byte in s.as_bytes() {
let id = self.byte_fallback_token_ids[byte as usize];
if id == INVALID_TOKEN {
return Err(format!(
"byte fallback token <0x{byte:02X}> not in vocabulary"
));
}
scratch.push_encoded_symbol(id);
}
}
let n = scratch.symbols.len();
if n == 1 {
out.push(scratch.symbols[0].c);
return Ok(());
}
self.init_merge_heap(&mut scratch, n);
self.run_encoded_merge_loop(&mut scratch, out);
Ok(())
})
}
fn merge_all_raw_into(&self, raw_input: &str, out: &mut Vec<u32>) -> Result<()> {
if raw_input.is_empty() {
return Ok(());
}
if !self.byte_fallback && (2..=15).contains(&raw_input.len()) {
return if self.ranked_merges {
self.merge_short_raw_into::<16, true>(raw_input.as_bytes(), out)
} else {
self.merge_short_raw_into::<16, false>(raw_input.as_bytes(), out)
};
}
if (!self.dense_merge.is_empty() || !self.dense_ranked_merge.is_empty())
&& (16..=31).contains(&raw_input.len())
{
return if self.ranked_merges {
self.merge_short_raw_into::<32, true>(raw_input.as_bytes(), out)
} else {
self.merge_short_raw_into::<32, false>(raw_input.as_bytes(), out)
};
}
TL_MERGE_SCRATCH.with(|s| {
let mut scratch = s.borrow_mut();
scratch.symbols.clear();
scratch.heap.clear();
scratch.heap_buf.clear();
let bytes = raw_input.as_bytes();
let n = bytes.len();
let mut prev_byte = 0u8;
for (i, &byte) in bytes.iter().enumerate() {
let id = self.byte_to_initial_token[byte as usize];
if id == INVALID_TOKEN {
return Err(format!("byte 0x{byte:02x} has no token in vocabulary"));
}
scratch.symbols.push(MergeSymbol {
c: id,
prev: if i == 0 { -1 } else { (i - 1) as i32 },
next: if i == n - 1 { -1 } else { (i + 1) as i32 },
});
if i > 0 {
let (rank, _new_id) =
self.byte_pair_initial[prev_byte as usize * 256 + byte as usize];
if rank != u32::MAX {
scratch.heap_buf.push(Reverse(MergeEntry::new(
rank,
(i - 1) as u32,
self.byte_to_initial_token[prev_byte as usize],
id,
)));
}
}
prev_byte = byte;
}
if n == 1 {
out.push(scratch.symbols[0].c);
return Ok(());
}
let mut tmp = std::mem::take(&mut scratch.heap_buf);
scratch.heap.extend(tmp.drain(..));
scratch.heap_buf = tmp;
self.run_merge_loop(&mut scratch, out);
Ok(())
})
}
#[inline]
fn merge_short_raw_into<const CAPACITY: usize, const RANKED: bool>(
&self,
bytes: &[u8],
out: &mut Vec<u32>,
) -> Result<()> {
let n = bytes.len();
debug_assert!((2..CAPACITY).contains(&n));
let mut symbols = [0u32; CAPACITY];
let mut next = [0u8; CAPACITY];
let mut prev = [0u8; CAPACITY];
let mut ranks = [u32::MAX; CAPACITY];
let mut merged = [0u32; CAPACITY];
for (i, &byte) in bytes.iter().enumerate() {
let id = self.byte_to_initial_token[byte as usize];
if id == INVALID_TOKEN {
return Err(format!("byte 0x{byte:02x} has no token in vocabulary"));
}
symbols[i] = id;
next[i] = (i + 1) as u8;
prev[i] = (i as u8).wrapping_sub(1);
if i > 0 {
let pair = self.byte_pair_initial[bytes[i - 1] as usize * 256 + byte as usize];
ranks[i - 1] = if RANKED && pair.0 != u32::MAX {
pair.1
} else {
pair.0
};
if !RANKED {
merged[i - 1] = pair.1;
}
}
}
loop {
let mut best_rank = u32::MAX;
let mut best = 0;
for (i, &rank) in ranks[..n - 1].iter().enumerate() {
if rank < best_rank {
best_rank = rank;
best = i;
}
}
if best_rank == u32::MAX {
break;
}
symbols[best] = if RANKED { best_rank } else { merged[best] };
let dead = next[best] as usize;
let right = next[dead] as usize;
next[best] = right as u8;
ranks[dead] = u32::MAX;
if right < n {
prev[right] = best as u8;
if let Some((rank, id)) =
self.short_merge_lookup::<RANKED>(symbols[best], symbols[right])
{
ranks[best] = if RANKED { id } else { rank };
if !RANKED {
merged[best] = id;
}
} else {
ranks[best] = u32::MAX;
}
} else {
ranks[best] = u32::MAX;
}
let left = prev[best] as usize;
if left < n {
if let Some((rank, id)) =
self.short_merge_lookup::<RANKED>(symbols[left], symbols[best])
{
ranks[left] = if RANKED { id } else { rank };
if !RANKED {
merged[left] = id;
}
} else {
ranks[left] = u32::MAX;
}
}
}
let mut i = 0;
while i < n {
out.push(symbols[i]);
i = next[i] as usize;
}
Ok(())
}
#[inline(always)]
fn short_merge_lookup<const RANKED: bool>(&self, left: u32, right: u32) -> Option<(u32, u32)> {
if RANKED
&& !self.dense_ranked_merge.is_empty()
&& left < DENSE_RANKED_LIMIT
&& right < DENSE_RANKED_LIMIT
{
let index = (left << DENSE_RANKED_BITS | right) as usize;
let id = unsafe { *self.dense_ranked_merge.get_unchecked(index) };
return (id != u32::MAX).then_some((id, id));
}
if !self.dense_merge.is_empty() && left < DENSE_MERGE_LIMIT && right < DENSE_MERGE_LIMIT {
let index = (left << DENSE_MERGE_BITS | right) as usize;
let packed = unsafe { *self.dense_merge.get_unchecked(index) };
return (packed != u64::MAX).then_some(((packed >> 32) as u32, packed as u32));
}
self.merge_adj.get(left, right)
}
#[inline(always)]
fn init_merge_heap(&self, scratch: &mut EncodedMergeScratch, n: usize) {
let symbols = &scratch.symbols;
scratch.heap.extend((0..n - 1).filter_map(|i| {
let left = symbols[i].c;
let right = symbols[i + 1].c;
self.merge_adj
.get(left, right)
.map(|(rank, _new_id)| Reverse(MergeEntry::new(rank, i as u32, left, right)))
}));
}
#[inline(always)]
fn run_merge_loop(&self, scratch: &mut MergeScratch, out: &mut Vec<u32>) {
run_merge_loop_body!(self, scratch, out);
}
#[inline(always)]
fn run_encoded_merge_loop(&self, scratch: &mut EncodedMergeScratch, out: &mut Vec<u32>) {
run_merge_loop_body!(self, scratch, out);
}
#[inline(always)]
pub fn tokenize_into_fused(&self, raw_input: &str, out: &mut Vec<u32>) -> Result<()> {
if raw_input.is_empty() {
return Ok(());
}
let bpe_id = self.id;
let hit = TL_FUSED_CACHE.with(|c| {
let mut c = c.borrow_mut();
if c.bpe_id != bpe_id {
self.prepare_fused_cache(&mut c);
}
c.get(raw_input, out)
});
if hit {
return Ok(());
}
let start = out.len();
if self.fused_shared_cache.get_into(raw_input, out) {
TL_FUSED_CACHE.with(|c| {
let mut c = c.borrow_mut();
if c.bpe_id != bpe_id {
self.prepare_fused_cache(&mut c);
}
c.insert(raw_input, &out[start..]);
});
return Ok(());
}
if self.ignore_merges {
let mut encoded = String::with_capacity(raw_input.len());
for &byte in raw_input.as_bytes() {
encoded.push(BYTE_TO_CHAR[byte as usize]);
}
if let Some(&id) = self.token_to_id.get(encoded.as_str()) {
out.push(id);
return Ok(());
}
}
self.merge_all_raw_into(raw_input, out)?;
let ids = &out[start..];
TL_FUSED_CACHE.with(|c| {
let mut c = c.borrow_mut();
if c.bpe_id != bpe_id {
self.prepare_fused_cache(&mut c);
}
c.insert(raw_input, ids);
});
self.fused_shared_cache
.insert(raw_input.to_string(), ids.to_vec());
Ok(())
}
pub(crate) fn tokenize_fused_stream(
&self,
input: &str,
out: &mut Vec<u32>,
use_parallel_cache: bool,
scan: impl FnOnce(&mut FusedStream<'_>),
) -> Result<()> {
out.reserve(input.len().saturating_add(3));
if use_parallel_cache {
return TL_FUSED_PARALLEL_CACHE
.with(|cache| self.tokenize_fused_stream_with_cache(out, cache, scan));
}
TL_FUSED_CACHE.with(|cache| self.tokenize_fused_stream_with_cache(out, cache, scan))
}
fn tokenize_fused_stream_with_cache(
&self,
out: &mut Vec<u32>,
cache: &RefCell<FlatCache>,
scan: impl FnOnce(&mut FusedStream<'_>),
) -> Result<()> {
let bpe_id = self.id;
let mut cache = cache.borrow_mut();
if cache.bpe_id != bpe_id {
self.prepare_fused_cache(&mut cache);
}
let mut pending = MaybeUninit::<[MaybeUninit<FusedPiece>; FUSED_PIECE_CAPACITY]>::uninit();
let pending = unsafe { &mut *pending.as_mut_ptr() };
let mut stream = FusedStream {
model: self,
cache: &mut cache,
out,
error: None,
pending,
pending_len: 0,
};
scan(&mut stream);
if stream.pending_len != 0 {
stream.flush();
}
stream.error.map_or(Ok(()), Err)
}
#[inline(always)]
fn tokenize_fused_cached(
&self,
cache: &mut FlatCache,
input: &str,
range: std::ops::Range<usize>,
packed: u128,
out: &mut Vec<u32>,
use_shared_cache: bool,
) -> Result<()> {
if range.is_empty() {
return Ok(());
}
if cache.get_front_packed(packed, out) {
return Ok(());
}
self.tokenize_fused_cache_miss(cache, input, range, packed, out, use_shared_cache)
}
#[cold]
#[inline(never)]
fn tokenize_fused_cache_miss(
&self,
cache: &mut FlatCache,
input: &str,
range: std::ops::Range<usize>,
packed: u128,
out: &mut Vec<u32>,
use_shared_cache: bool,
) -> Result<()> {
if packed != EMPTY_SHORT_KEY && cache.get_packed_backing(packed, out) {
return Ok(());
}
self.tokenize_fused_uncached(cache, input, range, packed, out, use_shared_cache)
}
#[cold]
#[inline(never)]
fn tokenize_fused_uncached(
&self,
cache: &mut FlatCache,
input: &str,
range: std::ops::Range<usize>,
packed: u128,
out: &mut Vec<u32>,
use_shared_cache: bool,
) -> Result<()> {
let text = &input[range];
if packed == EMPTY_SHORT_KEY && cache.get_piece(text, packed, out) {
return Ok(());
}
let start = out.len();
if use_shared_cache && self.fused_shared_cache.get_into(text, out) {
cache.insert_piece(text, packed, &out[start..]);
return Ok(());
}
if self.ignore_merges {
let mut encoded = String::with_capacity(text.len());
for &byte in text.as_bytes() {
encoded.push(BYTE_TO_CHAR[byte as usize]);
}
if let Some(&id) = self.token_to_id.get(encoded.as_str()) {
out.push(id);
cache.insert_piece(text, packed, &out[start..]);
return Ok(());
}
}
self.merge_all_raw_into(text, out)?;
cache.insert_piece(text, packed, &out[start..]);
if use_shared_cache {
self.fused_shared_cache
.insert(text.to_string(), out[start..].to_vec());
}
Ok(())
}
fn prepare_fused_cache(&self, cache: &mut FlatCache) {
cache.bpe_id = self.id;
cache.clear();
for &(key, id) in self.fused_cache_seeds.iter().rev() {
cache.insert_front(key, &[id]);
}
if cache.front.len() == PARALLEL_FRONT_CACHE_SIZE {
for &(key, id) in self.fused_cache_seeds.iter().rev() {
let slot = &cache.front[cache.front_index(key)];
if slot.key != [key as u64, (key >> 64) as u64] {
cache.insert_packed_backing(key, &[id]);
}
}
} else {
for &(key, id) in self.fused_cache_seeds.iter().rev() {
if id as usize >= FUSED_CACHE_BACKING_SEED_LIMIT {
continue;
}
cache.insert_packed_backing(key, &[id]);
}
}
}
pub fn tokenize_batch_fused(
&self,
buffer: &str,
splits: &[crate::pre_tokenized::Split],
out: &mut Vec<u32>,
) -> Result<()> {
out.reserve(buffer.len().saturating_add(splits.len()).saturating_add(3));
let bpe_id = self.id;
TL_FUSED_CACHE.with(|c| {
let mut cache = c.borrow_mut();
if cache.bpe_id != bpe_id {
self.prepare_fused_cache(&mut cache);
}
for split in splits {
if let Some(id) = split.token_id {
out.push(id);
} else if !split.range.is_empty() {
let packed = pack_short_range(buffer, split.range.start, split.range.end);
self.tokenize_fused_cached(
&mut cache,
buffer,
split.range.clone(),
packed,
out,
true,
)?;
}
}
Ok(())
})
}
pub fn id_to_token(&self, id: u32) -> Option<&str> {
self.id_to_token.get(id as usize).map(String::as_str)
}
pub fn token_to_id(&self, token: &str) -> Option<u32> {
self.token_to_id.get(token).copied()
}
pub fn vocab_size(&self) -> usize {
self.id_to_token.len()
}
}
impl Clone for Bpe {
fn clone(&self) -> Self {
Self {
id: BPE_ID_COUNTER.fetch_add(1, Ordering::Relaxed),
daac: self.daac.clone(),
unmerge_map: self.unmerge_map.clone(),
token_lens: self.token_lens.clone(),
shared_cache: SharedCache::new(),
fused_shared_cache: SharedCache::new(),
id_to_token: self.id_to_token.clone(),
token_to_id: self.token_to_id.clone(),
byte_to_initial_token: self.byte_to_initial_token,
byte_fallback_token_ids: self.byte_fallback_token_ids,
single_char_token: self.single_char_token,
ranked_merge_map: self.ranked_merge_map.clone(),
byte_pair_initial: self.byte_pair_initial.clone(),
dense_merge: self.dense_merge.clone(),
dense_ranked_merge: self.dense_ranked_merge.clone(),
ranked_merges: self.ranked_merges,
fused_cache_seeds: self.fused_cache_seeds.clone(),
merge_adj: self.merge_adj.clone(),
ignore_merges: self.ignore_merges,
byte_fallback: self.byte_fallback,
bigram_bridge_table: self.bigram_bridge_table.clone(),
}
}
}
impl fmt::Debug for Bpe {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Bpe")
.field("vocab_size", &self.token_lens.len())
.field("merges", &self.ranked_merge_map.len())
.finish()
}
}
impl PartialEq for Bpe {
fn eq(&self, other: &Self) -> bool {
self.daac == other.daac
&& self.ranked_merge_map == other.ranked_merge_map
&& self.unmerge_map == other.unmerge_map
&& self.token_lens == other.token_lens
&& self.ignore_merges == other.ignore_merges
&& self.byte_fallback == other.byte_fallback
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::json_structs::ModelConfig;
fn test_bpe() -> Bpe {
let vocab: Vocab = [
("a", 0),
("b", 1),
("c", 2),
("d", 3),
("ab", 4),
("cd", 5),
("abcd", 6),
]
.into_iter()
.map(|(s, id)| (s.to_string(), id))
.collect();
let merges: Vec<Value> = vec![
Value::String("a b".into()),
Value::String("c d".into()),
Value::String("ab cd".into()),
];
let merge_map = parse_merges(&vocab, &merges).unwrap();
Bpe::new(&vocab, merge_map).unwrap()
}
#[test]
fn empty_input() {
let bpe = test_bpe();
assert_eq!(bpe.tokenize("").unwrap(), Vec::<u32>::new());
}
#[test]
fn single_char() {
let bpe = test_bpe();
assert_eq!(bpe.tokenize("a").unwrap(), vec![0]);
assert_eq!(bpe.tokenize("d").unwrap(), vec![3]);
}
#[test]
fn simple_merge() {
let bpe = test_bpe();
assert_eq!(bpe.tokenize("ab").unwrap(), vec![4]);
assert_eq!(bpe.tokenize("cd").unwrap(), vec![5]);
}
#[test]
fn chained_merge() {
let bpe = test_bpe();
assert_eq!(bpe.tokenize("abcd").unwrap(), vec![6]);
}
#[test]
fn partial_merge() {
let bpe = test_bpe();
assert_eq!(bpe.tokenize("abc").unwrap(), vec![4, 2]);
}
#[test]
fn repeated_merge() {
let bpe = test_bpe();
assert_eq!(bpe.tokenize("abab").unwrap(), vec![4, 4]);
}
#[test]
fn deserialize_from_json() {
let json = serde_json::json!({
"type": "BPE",
"vocab": {"a": 0, "b": 1, "ab": 2},
"merges": ["a b"]
});
let config: ModelConfig = serde_json::from_value(json).unwrap();
assert!(matches!(config, ModelConfig::Bpe(_)));
}
#[test]
fn deserialize_array_merges() {
let json = serde_json::json!({
"type": "BPE",
"vocab": {"a": 0, "b": 1, "ab": 2},
"merges": [["a", "b"]]
});
let config: ModelConfig = serde_json::from_value(json).unwrap();
let ModelConfig::Bpe(bpe) = config;
assert_eq!(bpe.tokenize("ab").unwrap(), vec![2]);
}
#[test]
fn cache_returns_same_result() {
let vocab: Vocab = [("a", 0), ("b", 1), ("ab", 2)]
.into_iter()
.map(|(s, id)| (s.to_string(), id))
.collect();
let merges = vec![Value::String("a b".into())];
let merge_map = parse_merges(&vocab, &merges).unwrap();
let bpe = Bpe::new(&vocab, merge_map).unwrap();
let first = bpe.tokenize("ab").unwrap();
let second = bpe.tokenize("ab").unwrap();
assert_eq!(first, second);
assert_eq!(first, vec![2]);
}
#[test]
fn flat_cache_preserves_front_and_long_values() {
let mut cache = FlatCache::new();
let short = "four-token-hit";
let short_ids = [1, 2, 3, 4];
let packed = pack_short_key(short).unwrap();
cache.insert(short, &short_ids);
let front_index = cache.front_index(packed);
cache.front[front_index] = FrontCacheSlot::default();
let mut out = Vec::new();
assert!(cache.get(short, &mut out));
assert_eq!(out, short_ids);
out.clear();
assert!(cache.get(short, &mut out));
assert_eq!(out, short_ids);
let long = "a fused cache key longer than fifteen bytes";
let long_ids = [5, 6, 7];
cache.insert(long, &long_ids);
out.clear();
assert!(cache.get(long, &mut out));
assert_eq!(out, long_ids);
cache.clear();
out.clear();
assert!(!cache.get(short, &mut out));
assert!(!cache.get(long, &mut out));
}
#[test]
fn rejects_out_of_range_merge_token_ids() {
let vocab: Vocab = [("a".to_string(), 0), ("b".to_string(), 1)]
.into_iter()
.collect();
for (left, right, merged) in [(2, 1, 0), (0, 2, 0), (0, 1, 2)] {
let merge_map = HashMap::from([((left, right), (0, merged))]);
assert_eq!(
Bpe::new(&vocab, merge_map).unwrap_err(),
"merge token id exceeds vocabulary size"
);
}
}
#[test]
fn rejects_corrupt_cached_ranked_merge_table() {
let mut resolved = test_bpe().resolved_config();
resolved.ranked_slot_indices[0] = u32::MAX;
assert!(Bpe::from_resolved(resolved).is_err());
}
}