use crate::{PairKey, Rank, TokenId, ExatokError};
use core::fmt;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Merge {
pub id: TokenId,
pub rank: Rank,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ParentOrderViolation {
pub pair: PairKey,
pub rank: Rank,
pub operand: TokenId,
pub minted_at: Rank,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MergeTable {
universe: u32,
ranks: Vec<u32>,
ids: Vec<u32>,
}
impl MergeTable {
#[must_use]
pub fn new(universe: u32) -> Self {
let cells = (universe as usize) * (universe as usize);
Self {
universe,
ranks: vec![Rank::ABSENT.0; cells],
ids: vec![0; cells],
}
}
pub fn from_raw(universe: u32, rows: &[(u32, u32, u32, u32)]) -> Result<Self, ExatokError> {
let mut table = Self::new(universe);
for &(left, right, merged, rank) in rows {
table.insert(TokenId(left), TokenId(right), TokenId(merged), Rank(rank))?;
}
Ok(table)
}
#[must_use]
pub const fn universe(&self) -> u32 {
self.universe
}
fn cell(&self, left: TokenId, right: TokenId) -> Option<usize> {
if left.0 >= self.universe || right.0 >= self.universe {
return None;
}
Some((left.0 as usize) * (self.universe as usize) + (right.0 as usize))
}
pub fn insert(
&mut self,
left: TokenId,
right: TokenId,
merged: TokenId,
rank: Rank,
) -> Result<(), ExatokError> {
if !rank.is_present() {
return Err(ExatokError::Artifact {
artifact: "confluence merge table".to_owned(),
location: format!("pair ({}, {})", left.0, right.0),
detail: "rank equals Rank::ABSENT, which is the miss sentinel".to_owned(),
fix: "use a rank below u32::MAX so the min reduction can select it".to_owned(),
});
}
if merged.0 >= self.universe {
return Err(ExatokError::Artifact {
artifact: "confluence merge table".to_owned(),
location: format!("pair ({}, {})", left.0, right.0),
detail: format!(
"merged id {} is outside the operand universe 0..{}, so it could never be \
fused again",
merged.0, self.universe
),
fix: "widen the universe passed to MergeTable::new".to_owned(),
});
}
let Some(cell) = self.cell(left, right) else {
return Err(ExatokError::Artifact {
artifact: "confluence merge table".to_owned(),
location: format!("pair ({}, {})", left.0, right.0),
detail: format!("operand outside the universe 0..{}", self.universe),
fix: "widen the universe passed to MergeTable::new".to_owned(),
});
};
self.ranks[cell] = rank.0;
self.ids[cell] = merged.0;
Ok(())
}
pub fn remove(&mut self, left: TokenId, right: TokenId) {
if let Some(cell) = self.cell(left, right) {
self.ranks[cell] = Rank::ABSENT.0;
}
}
#[must_use]
pub fn lookup(&self, left: TokenId, right: TokenId) -> Option<Merge> {
let cell = self.cell(left, right)?;
let rank = self.ranks[cell];
if rank == Rank::ABSENT.0 {
return None;
}
Some(Merge {
id: TokenId(self.ids[cell]),
rank: Rank(rank),
})
}
#[must_use]
pub fn rank_of(&self, left: TokenId, right: TokenId) -> Rank {
match self.lookup(left, right) {
Some(merge) => merge.rank,
None => Rank::ABSENT,
}
}
pub fn entries(&self) -> impl Iterator<Item = (PairKey, Merge)> + '_ {
let stride = (self.universe as usize).max(1);
self.ranks
.iter()
.enumerate()
.filter_map(move |(cell, &rank)| {
if rank == Rank::ABSENT.0 {
return None;
}
let left = TokenId((cell / stride) as u32);
let right = TokenId((cell % stride) as u32);
Some((
PairKey::new(left, right),
Merge {
id: TokenId(self.ids[cell]),
rank: Rank(rank),
},
))
})
}
#[must_use]
pub fn entry_count(&self) -> usize {
self.ranks.iter().filter(|&&r| r != Rank::ABSENT.0).count()
}
#[must_use]
pub fn parent_order_violations(&self) -> Vec<ParentOrderViolation> {
let mut minted: Vec<Option<u32>> = vec![None; self.universe as usize];
for (_, merge) in self.entries() {
let slot = &mut minted[merge.id.0 as usize];
*slot = Some(match *slot {
Some(seen) if seen >= merge.rank.0 => seen,
_ => merge.rank.0,
});
}
let mut violations = Vec::new();
for (pair, merge) in self.entries() {
for operand in [pair.left(), pair.right()] {
let Some(minted_at) = minted[operand.0 as usize] else {
continue;
};
if merge.rank.0 <= minted_at {
violations.push(ParentOrderViolation {
pair,
rank: merge.rank,
operand,
minted_at: Rank(minted_at),
});
}
}
}
violations
}
#[must_use]
pub fn is_parent_ordered(&self) -> bool {
self.parent_order_violations().is_empty()
}
}
impl fmt::Display for MergeTable {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "universe {}:", self.universe)?;
for (pair, merge) in self.entries() {
write!(
f,
" ({},{})->{}@r{}",
pair.left().0,
pair.right().0,
merge.id.0,
merge.rank.0
)?;
}
Ok(())
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MergeTrace {
pub tokens: Vec<TokenId>,
pub passes: usize,
pub merges: usize,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RankPhase {
pub tokens: Vec<TokenId>,
pub rank: Rank,
pub merges: usize,
}
fn leftmost_lowest_rank(tokens: &[TokenId], table: &MergeTable) -> Option<(usize, Merge)> {
let mut best: Option<(usize, Merge)> = None;
for at in 0..tokens.len().saturating_sub(1) {
let Some(merge) = table.lookup(tokens[at], tokens[at + 1]) else {
continue;
};
let better = match best {
Some((_, incumbent)) => merge.rank.0 < incumbent.rank.0,
None => true,
};
if better {
best = Some((at, merge));
}
}
best
}
#[must_use]
pub fn sequential_leftmost_greedy(input: &[TokenId], table: &MergeTable) -> MergeTrace {
let mut tokens = input.to_vec();
let mut merges = 0usize;
while let Some((at, merge)) = leftmost_lowest_rank(&tokens, table) {
tokens[at] = merge.id;
tokens.remove(at + 1);
merges += 1;
}
MergeTrace {
tokens,
passes: merges,
merges,
}
}
#[must_use]
pub fn sequential_rank_phase(input: &[TokenId], table: &MergeTable) -> Option<RankPhase> {
let mut tokens = input.to_vec();
let (mut at, mut merge) = leftmost_lowest_rank(&tokens, table)?;
let rank = merge.rank;
let mut merges = 0usize;
loop {
if merge.rank != rank {
break;
}
tokens[at] = merge.id;
tokens.remove(at + 1);
merges += 1;
match leftmost_lowest_rank(&tokens, table) {
Some((next_at, next_merge)) => {
at = next_at;
merge = next_merge;
}
None => break,
}
}
Some(RankPhase {
tokens,
rank,
merges,
})
}
#[must_use]
pub fn single_rank_pass(tokens: &[TokenId], table: &MergeTable) -> Option<(Vec<TokenId>, usize)> {
let width = tokens.len().checked_sub(1)?;
if width == 0 {
return None;
}
let mut ranks = Vec::with_capacity(width);
let mut fused = Vec::with_capacity(width);
for at in 0..width {
match table.lookup(tokens[at], tokens[at + 1]) {
Some(merge) => {
ranks.push(merge.rank.0);
fused.push(merge.id);
}
None => {
ranks.push(Rank::ABSENT.0);
fused.push(tokens[at]);
}
}
}
let mut floor = Rank::ABSENT.0;
for &rank in &ranks {
if rank < floor {
floor = rank;
}
}
if floor == Rank::ABSENT.0 {
return None;
}
let mut out = Vec::with_capacity(tokens.len());
let mut merges = 0usize;
let mut at = 0usize;
while at < tokens.len() {
if at < width && ranks[at] == floor {
out.push(fused[at]);
at += 2;
merges += 1;
} else {
out.push(tokens[at]);
at += 1;
}
}
Some((out, merges))
}
#[must_use]
pub fn single_rank_multi_merge(input: &[TokenId], table: &MergeTable) -> MergeTrace {
let mut tokens = input.to_vec();
let mut passes = 0usize;
let mut merges = 0usize;
while let Some((next, pass_merges)) = single_rank_pass(&tokens, table) {
tokens = next;
passes += 1;
merges += pass_merges;
}
MergeTrace {
tokens,
passes,
merges,
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DivergenceKind {
FinalTokens,
Pass(usize),
}
impl fmt::Display for DivergenceKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::FinalTokens => write!(f, "final tokens"),
Self::Pass(index) => write!(f, "pass {index}"),
}
}
}
#[must_use]
pub const fn same_class(left: DivergenceKind, right: DivergenceKind) -> bool {
matches!(
(left, right),
(DivergenceKind::FinalTokens, DivergenceKind::FinalTokens)
| (DivergenceKind::Pass(_), DivergenceKind::Pass(_))
)
}
#[must_use]
pub fn classify(input: &[TokenId], table: &MergeTable) -> Option<DivergenceKind> {
let reference = sequential_leftmost_greedy(input, table);
let candidate = single_rank_multi_merge(input, table);
if reference.tokens != candidate.tokens {
return Some(DivergenceKind::FinalTokens);
}
let mut state = input.to_vec();
let mut index = 0usize;
loop {
match (
single_rank_pass(&state, table),
sequential_rank_phase(&state, table),
) {
(None, None) => return None,
(Some((next, _)), Some(phase)) if next == phase.tokens => {
state = next;
index += 1;
}
_ => return Some(DivergenceKind::Pass(index)),
}
}
}
#[derive(Debug, Clone)]
pub struct Divergence {
pub kind: DivergenceKind,
pub table: MergeTable,
pub input: Vec<TokenId>,
pub sequential: Vec<TokenId>,
pub multi: Vec<TokenId>,
pub violations: Vec<ParentOrderViolation>,
}
impl Divergence {
#[must_use]
pub fn capture(input: &[TokenId], table: &MergeTable) -> Option<Self> {
let kind = classify(input, table)?;
Some(Self {
kind,
table: table.clone(),
input: input.to_vec(),
sequential: sequential_leftmost_greedy(input, table).tokens,
multi: single_rank_multi_merge(input, table).tokens,
violations: table.parent_order_violations(),
})
}
}
fn render_ids(f: &mut fmt::Formatter<'_>, tokens: &[TokenId]) -> fmt::Result {
write!(f, "[")?;
for (position, token) in tokens.iter().enumerate() {
if position > 0 {
write!(f, ", ")?;
}
write!(f, "{}", token.0)?;
}
write!(f, "]")
}
impl fmt::Display for Divergence {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} diverged\n table: {}\n input: ", self.kind, self.table)?;
render_ids(f, &self.input)?;
write!(f, "\n sequential: ")?;
render_ids(f, &self.sequential)?;
write!(f, "\n multi-merge: ")?;
render_ids(f, &self.multi)?;
write!(f, "\n parent-order violations: {}", self.violations.len())?;
for violation in &self.violations {
write!(
f,
"\n ({},{})@r{} consumes {} minted at r{}",
violation.pair.left().0,
violation.pair.right().0,
violation.rank.0,
violation.operand.0,
violation.minted_at.0
)?;
}
Ok(())
}
}
#[must_use]
pub fn minimize(found: Divergence) -> Divergence {
let mut best = found;
loop {
let mut improved = false;
for cut in (0..best.input.len()).rev() {
let mut candidate = best.input.clone();
candidate.remove(cut);
let Some(shrunk) = Divergence::capture(&candidate, &best.table) else {
continue;
};
if same_class(shrunk.kind, best.kind) {
best = shrunk;
improved = true;
break;
}
}
if improved {
continue;
}
let keys: Vec<PairKey> = best.table.entries().map(|(key, _)| key).collect();
for key in keys {
let mut table = best.table.clone();
table.remove(key.left(), key.right());
let Some(shrunk) = Divergence::capture(&best.input, &table) else {
continue;
};
if same_class(shrunk.kind, best.kind) {
best = shrunk;
improved = true;
break;
}
}
if !improved {
break;
}
}
compact_ranks(best)
}
fn compact_ranks(found: Divergence) -> Divergence {
let rows: Vec<(PairKey, Merge)> = found.table.entries().collect();
let mut present: Vec<u32> = rows.iter().map(|(_, merge)| merge.rank.0).collect();
present.sort_unstable();
present.dedup();
let mut table = MergeTable::new(found.table.universe());
for (key, merge) in rows {
let Ok(index) = present.binary_search(&merge.rank.0) else {
return found;
};
let Ok(rank) = u32::try_from(index) else {
return found;
};
if table
.insert(key.left(), key.right(), merge.id, Rank(rank))
.is_err()
{
return found;
}
}
match Divergence::capture(&found.input, &table) {
Some(shrunk) if same_class(shrunk.kind, found.kind) => shrunk,
_ => found,
}
}
#[derive(Debug, Clone)]
pub struct SplitMix64 {
state: u64,
}
impl SplitMix64 {
#[must_use]
pub const fn new(seed: u64) -> Self {
Self { state: seed }
}
pub fn next_u64(&mut self) -> u64 {
self.state = self.state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = self.state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
pub fn below(&mut self, bound: u32) -> u32 {
if bound == 0 {
return 0;
}
(self.next_u64() % u64::from(bound)) as u32
}
pub fn shuffle<T>(&mut self, items: &mut [T]) {
if items.len() < 2 {
return;
}
for index in (1..items.len()).rev() {
let Ok(bound) = u32::try_from(index + 1) else {
continue;
};
items.swap(index, self.below(bound) as usize);
}
}
}
#[derive(Debug, Clone, Copy)]
pub struct UnconstrainedSpec {
pub base: u32,
pub merged: u32,
pub rank_pool: u32,
pub density_percent: u32,
}
#[must_use]
pub fn unconstrained_table(rng: &mut SplitMix64, spec: UnconstrainedSpec) -> MergeTable {
let universe = spec.base.saturating_add(spec.merged);
let mut table = MergeTable::new(universe);
for left in 0..universe {
for right in 0..universe {
if rng.below(100) >= spec.density_percent {
continue;
}
let rank = Rank(rng.below(spec.rank_pool.max(1)));
let merged = TokenId(rng.below(universe));
drop(table.insert(TokenId(left), TokenId(right), merged, rank));
}
}
table
}
#[derive(Debug, Clone, Copy)]
pub struct ParentOrderedSpec {
pub base: u32,
pub groups: u32,
pub per_group: u32,
}
impl ParentOrderedSpec {
#[must_use]
pub const fn universe(&self) -> u32 {
self.base
.saturating_add(self.groups.saturating_mul(self.per_group))
}
}
#[must_use]
pub fn parent_ordered_table(rng: &mut SplitMix64, spec: ParentOrderedSpec) -> MergeTable {
let mut table = MergeTable::new(spec.universe());
let mut operands: Vec<TokenId> = (0..spec.base).map(TokenId).collect();
let mut minted = spec.base;
for group in 0..spec.groups {
let mut fresh: Vec<TokenId> = Vec::new();
for _ in 0..spec.per_group {
let Ok(pool) = u32::try_from(operands.len()) else {
break;
};
if pool == 0 {
break;
}
let left = operands[rng.below(pool) as usize];
let right = operands[rng.below(pool) as usize];
if table.rank_of(left, right).is_present() {
continue;
}
if table
.insert(left, right, TokenId(minted), Rank(group))
.is_err()
{
continue;
}
fresh.push(TokenId(minted));
minted += 1;
}
operands.extend(fresh);
}
table
}
#[derive(Debug, Clone, Copy)]
pub struct StringVocabSpec {
pub alphabet: u32,
pub max_token_len: u32,
pub keep_percent: u32,
pub id_order: IdOrder,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum IdOrder {
Permuted,
ByLength,
}
#[must_use]
pub fn string_vocab_table(rng: &mut SplitMix64, spec: StringVocabSpec) -> MergeTable {
let alphabet = spec.alphabet.max(1);
let max_len = spec.max_token_len.max(1) as usize;
let mut kept: Vec<Vec<u32>> = Vec::new();
for len in 1..=max_len {
let mut token = vec![0u32; len];
loop {
if len == 1 || rng.below(100) < spec.keep_percent {
kept.push(token.clone());
}
let mut position = len;
let mut carried = true;
while position > 0 {
position -= 1;
if token[position] + 1 < alphabet {
token[position] += 1;
carried = false;
break;
}
token[position] = 0;
}
if carried {
break;
}
}
}
let mut longer: Vec<Vec<u32>> = kept.iter().filter(|t| t.len() > 1).cloned().collect();
rng.shuffle(&mut longer);
if spec.id_order == IdOrder::ByLength {
longer.sort_by_key(Vec::len);
}
let mut id_of: Vec<(Vec<u32>, u32)> = (0..alphabet).map(|s| (vec![s], s)).collect();
for (offset, token) in longer.iter().enumerate() {
let Ok(offset) = u32::try_from(offset) else {
continue;
};
id_of.push((token.clone(), alphabet + offset));
}
id_of.sort();
let universe = alphabet.saturating_add(u32::try_from(longer.len()).unwrap_or_default());
let lookup = |token: &[u32]| -> Option<u32> {
id_of
.binary_search_by(|(candidate, _)| candidate.as_slice().cmp(token))
.ok()
.map(|index| id_of[index].1)
};
let mut table = MergeTable::new(universe);
for (left_token, left_id) in &id_of {
for (right_token, right_id) in &id_of {
let mut joined = left_token.clone();
joined.extend_from_slice(right_token);
if joined.len() > max_len {
continue;
}
let Some(result) = lookup(&joined) else {
continue;
};
drop(table.insert(
TokenId(*left_id),
TokenId(*right_id),
TokenId(result),
Rank(result),
));
}
}
table
}
pub const CL100K_SPACE_RUN_IDS: [u32; 32] = [
220, 256, 262, 257, 415, 996, 286, 260, 692, 1881, 310, 1835, 1078, 2342, 394, 338, 1733, 4391,
504, 3909, 2611, 5291, 667, 5218, 3586, 6096, 1014, 6663, 4700, 7714, 1408, 792,
];
pub fn cl100k_space_run_table() -> Result<MergeTable, ExatokError> {
let runs = CL100K_SPACE_RUN_IDS.len();
let Ok(universe) = u32::try_from(runs) else {
return Err(ExatokError::Artifact {
artifact: "cl100k_base space runs".to_owned(),
location: "CL100K_SPACE_RUN_IDS".to_owned(),
detail: "run count does not fit in u32".to_owned(),
fix: "shorten the embedded run chain".to_owned(),
});
};
let mut table = MergeTable::new(universe);
for left in 1..=runs {
for right in 1..=runs {
let total = left + right;
if total > runs {
continue;
}
let Ok(left_slot) = u32::try_from(left - 1) else {
continue;
};
let Ok(right_slot) = u32::try_from(right - 1) else {
continue;
};
let Ok(result_slot) = u32::try_from(total - 1) else {
continue;
};
table.insert(
TokenId(left_slot),
TokenId(right_slot),
TokenId(result_slot),
Rank(CL100K_SPACE_RUN_IDS[total - 1]),
)?;
}
}
Ok(table)
}
pub fn all_pairs_tie_table(base: u32) -> Result<MergeTable, ExatokError> {
let universe = base.saturating_add(base.saturating_mul(base));
let mut table = MergeTable::new(universe);
let mut next = base;
for left in 0..base {
for right in 0..base {
table.insert(TokenId(left), TokenId(right), TokenId(next), Rank(0))?;
next += 1;
}
}
Ok(table)
}
pub fn cascade_table(levels: u32) -> Result<MergeTable, ExatokError> {
let mut table = MergeTable::new(levels.saturating_add(1));
for level in 0..levels {
table.insert(
TokenId(level),
TokenId(level),
TokenId(level + 1),
Rank(level),
)?;
}
Ok(table)
}
#[must_use]
pub fn ids(raw: &[u32]) -> Vec<TokenId> {
raw.iter().copied().map(TokenId).collect()
}
#[must_use]
pub fn sequence_count(alphabet: u32, min_len: usize, max_len: usize) -> usize {
let mut total = 0usize;
for len in min_len..=max_len {
let Ok(exp) = u32::try_from(len) else {
continue;
};
let Some(count) = (alphabet as usize).checked_pow(exp) else {
continue;
};
total = total.saturating_add(count);
}
total
}
pub fn for_each_sequence(
alphabet: u32,
min_len: usize,
max_len: usize,
visit: &mut impl FnMut(&[TokenId]),
) -> usize {
if alphabet == 0 {
return 0;
}
let mut visited = 0usize;
let mut buffer: Vec<TokenId> = Vec::with_capacity(max_len);
for len in min_len..=max_len {
if len == 0 {
continue;
}
buffer.clear();
buffer.resize(len, TokenId(0));
loop {
visit(&buffer);
visited += 1;
let mut position = len;
let mut carried = true;
while position > 0 {
position -= 1;
if buffer[position].0 + 1 < alphabet {
buffer[position].0 += 1;
carried = false;
break;
}
buffer[position].0 = 0;
}
if carried {
break;
}
}
}
visited
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SearchSpace {
pub alphabet: u32,
pub min_len: usize,
pub max_len: usize,
pub tables: usize,
pub sequences: usize,
pub cases: usize,
}
impl fmt::Display for SearchSpace {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"alphabet {}, lengths {}..={}, {} sequences x {} tables = {} cases",
self.alphabet, self.min_len, self.max_len, self.sequences, self.tables, self.cases
)
}
}
#[derive(Debug, Clone)]
pub struct SearchOutcome {
pub space: SearchSpace,
pub divergent_cases: usize,
pub parent_ordered_divergent_cases: usize,
pub final_token_cases: usize,
pub sequential_merges: usize,
pub multi_passes: usize,
pub samples: Vec<Divergence>,
}
impl SearchOutcome {
#[must_use]
pub const fn mean_sequential_merges_milli(&self) -> usize {
if self.space.cases == 0 {
return 0;
}
self.sequential_merges.saturating_mul(1000) / self.space.cases
}
#[must_use]
pub const fn mean_multi_passes_milli(&self) -> usize {
if self.space.cases == 0 {
return 0;
}
self.multi_passes.saturating_mul(1000) / self.space.cases
}
}
#[must_use]
pub fn search(
alphabet: u32,
min_len: usize,
max_len: usize,
tables: &[MergeTable],
sample_limit: usize,
) -> SearchOutcome {
let sequences = sequence_count(alphabet, min_len, max_len);
let mut divergent_cases = 0usize;
let mut parent_ordered_divergent_cases = 0usize;
let mut final_token_cases = 0usize;
let mut sequential_merges = 0usize;
let mut multi_passes = 0usize;
let mut samples: Vec<Divergence> = Vec::new();
for table in tables {
let parent_ordered = table.is_parent_ordered();
for_each_sequence(alphabet, min_len, max_len, &mut |sequence| {
let reference = sequential_leftmost_greedy(sequence, table);
let candidate = single_rank_multi_merge(sequence, table);
sequential_merges = sequential_merges.saturating_add(reference.merges);
multi_passes = multi_passes.saturating_add(candidate.passes);
let Some(kind) = classify(sequence, table) else {
return;
};
divergent_cases += 1;
if parent_ordered {
parent_ordered_divergent_cases += 1;
}
if kind == DivergenceKind::FinalTokens {
final_token_cases += 1;
}
if samples.len() < sample_limit {
if let Some(found) = Divergence::capture(sequence, table) {
samples.push(found);
}
}
});
}
SearchOutcome {
space: SearchSpace {
alphabet,
min_len,
max_len,
tables: tables.len(),
sequences,
cases: sequences.saturating_mul(tables.len()),
},
divergent_cases,
parent_ordered_divergent_cases,
final_token_cases,
sequential_merges,
multi_passes,
samples,
}
}
#[cfg(test)]
#[allow(
clippy::unwrap_used,
clippy::expect_used,
clippy::panic,
reason = "test code asserts on known-good values"
)]
mod tests {
use super::*;
#[test]
fn absent_pair_reports_the_miss_sentinel() {
let table = MergeTable::from_raw(4, &[(0, 1, 2, 7)]).unwrap();
assert_eq!(table.rank_of(TokenId(0), TokenId(1)), Rank(7));
assert_eq!(table.rank_of(TokenId(1), TokenId(0)), Rank::ABSENT);
assert_eq!(table.rank_of(TokenId(3), TokenId(3)), Rank::ABSENT);
assert_eq!(table.lookup(TokenId(1), TokenId(0)), None);
assert_eq!(
table.lookup(TokenId(0), TokenId(1)),
Some(Merge {
id: TokenId(2),
rank: Rank(7)
})
);
}
#[test]
fn an_absent_pair_loses_the_min_reduction_to_a_present_rank() {
let table = MergeTable::from_raw(4, &[(0, 0, 2, 5)]).unwrap();
assert_eq!(table.rank_of(TokenId(1), TokenId(0)), Rank::ABSENT);
assert_eq!(table.rank_of(TokenId(0), TokenId(0)), Rank(5));
assert_eq!(table.rank_of(TokenId(0), TokenId(1)), Rank::ABSENT);
let (next, merges) = single_rank_pass(&ids(&[1, 0, 0, 1]), &table).unwrap();
assert_eq!(next, ids(&[1, 2, 1]));
assert_eq!(merges, 1);
}
#[test]
fn out_of_universe_ids_miss_instead_of_aliasing() {
let table = MergeTable::from_raw(3, &[(0, 1, 2, 0)]).unwrap();
assert_eq!(table.rank_of(TokenId(3), TokenId(0)), Rank::ABSENT);
assert_eq!(table.rank_of(TokenId(0), TokenId(9)), Rank::ABSENT);
assert_eq!(table.entry_count(), 1);
}
#[test]
fn insert_rejects_the_sentinel_rank_and_out_of_range_ids() {
let mut table = MergeTable::new(3);
assert!(
table
.insert(TokenId(0), TokenId(1), TokenId(2), Rank::ABSENT)
.is_err()
);
assert!(
table
.insert(TokenId(0), TokenId(1), TokenId(3), Rank(0))
.is_err()
);
assert!(
table
.insert(TokenId(3), TokenId(1), TokenId(2), Rank(0))
.is_err()
);
assert_eq!(table.entry_count(), 0);
assert!(
table
.insert(TokenId(0), TokenId(1), TokenId(2), Rank(0))
.is_ok()
);
assert_eq!(table.entry_count(), 1);
}
#[test]
fn ranks_are_unbounded_while_operands_are_not() {
let mut table = MergeTable::new(2);
assert!(
table
.insert(TokenId(0), TokenId(0), TokenId(1), Rank(7714))
.is_ok()
);
assert_eq!(table.rank_of(TokenId(0), TokenId(0)), Rank(7714));
}
#[test]
fn entries_enumerate_in_packed_key_order() {
let table = MergeTable::from_raw(3, &[(2, 0, 1, 5), (0, 1, 2, 3), (1, 2, 0, 4)]).unwrap();
let listed: Vec<(u32, u32, u32, u32)> = table
.entries()
.map(|(pair, merge)| (pair.left().0, pair.right().0, merge.id.0, merge.rank.0))
.collect();
assert_eq!(listed, vec![(0, 1, 2, 3), (1, 2, 0, 4), (2, 0, 1, 5)]);
}
#[test]
fn parent_order_audit_reports_the_offending_operand() {
let table = MergeTable::from_raw(3, &[(0, 0, 1, 1), (1, 0, 2, 0)]).unwrap();
let violations = table.parent_order_violations();
assert_eq!(violations.len(), 1);
assert_eq!(violations[0].pair, PairKey::new(TokenId(1), TokenId(0)));
assert_eq!(violations[0].rank, Rank(0));
assert_eq!(violations[0].operand, TokenId(1));
assert_eq!(violations[0].minted_at, Rank(1));
assert!(!table.is_parent_ordered());
}
#[test]
fn parent_order_audit_requires_strictly_later_rank() {
let strict = MergeTable::from_raw(3, &[(0, 0, 1, 0), (1, 0, 2, 1)]).unwrap();
assert!(strict.is_parent_ordered());
let tied = MergeTable::from_raw(3, &[(0, 0, 1, 0), (1, 0, 2, 0)]).unwrap();
let violations = tied.parent_order_violations();
assert_eq!(violations.len(), 1);
assert_eq!(violations[0].rank, Rank(0));
assert_eq!(violations[0].minted_at, Rank(0));
}
#[test]
fn parent_order_audit_catches_self_feeding_entries() {
let table = MergeTable::from_raw(2, &[(0, 0, 0, 3)]).unwrap();
let violations = table.parent_order_violations();
assert_eq!(violations.len(), 2);
for violation in &violations {
assert_eq!(violation.operand, TokenId(0));
assert_eq!(violation.rank, Rank(3));
assert_eq!(violation.minted_at, Rank(3));
}
}
#[test]
fn sequential_takes_lowest_rank_before_leftmost() {
let table = MergeTable::from_raw(6, &[(0, 1, 4, 9), (1, 2, 5, 0)]).unwrap();
let trace = sequential_leftmost_greedy(&ids(&[0, 1, 2]), &table);
assert_eq!(trace.tokens, ids(&[0, 5]));
assert_eq!(trace.merges, 1);
}
#[test]
fn sequential_breaks_rank_ties_leftmost() {
let table = MergeTable::from_raw(7, &[(0, 1, 5, 4), (2, 3, 6, 4)]).unwrap();
let trace = sequential_leftmost_greedy(&ids(&[0, 1, 2, 3]), &table);
assert_eq!(trace.tokens, ids(&[5, 6]));
assert_eq!(trace.merges, 2);
let mirrored = sequential_leftmost_greedy(&ids(&[2, 3, 0, 1]), &table);
assert_eq!(mirrored.tokens, ids(&[6, 5]));
}
#[test]
fn sequential_recomputes_selection_after_each_fusion() {
let table = MergeTable::from_raw(3, &[(0, 0, 1, 5), (1, 0, 2, 0)]).unwrap();
let trace = sequential_leftmost_greedy(&ids(&[0, 0, 0]), &table);
assert_eq!(trace.tokens, ids(&[2]));
assert_eq!(trace.merges, 2);
}
#[test]
fn sequential_performs_exactly_one_merge_per_pass() {
let table = cascade_table(3).unwrap();
let trace = sequential_leftmost_greedy(&ids(&[0, 0, 0, 0]), &table);
assert_eq!(trace.tokens, ids(&[2]));
assert_eq!(trace.merges, 3);
assert_eq!(trace.passes, trace.merges);
}
#[test]
fn sequential_leaves_unmergeable_input_alone() {
let table = MergeTable::from_raw(4, &[(0, 1, 2, 0)]).unwrap();
for input in [ids(&[]), ids(&[0]), ids(&[1, 0]), ids(&[3, 3, 3])] {
let trace = sequential_leftmost_greedy(&input, &table);
assert_eq!(trace.tokens, input);
assert_eq!(trace.merges, 0);
assert_eq!(trace.passes, 0);
}
}
#[test]
fn multi_merge_skips_the_overlapping_occurrence() {
let table = MergeTable::from_raw(2, &[(0, 0, 1, 0)]).unwrap();
let (next, merges) = single_rank_pass(&ids(&[0, 0, 0, 0]), &table).unwrap();
assert_eq!(next, ids(&[1, 1]));
assert_eq!(merges, 2);
let (odd, odd_merges) = single_rank_pass(&ids(&[0, 0, 0, 0, 0]), &table).unwrap();
assert_eq!(odd, ids(&[1, 1, 0]));
assert_eq!(odd_merges, 2);
}
#[test]
fn multi_merge_pass_touches_only_the_minimum_rank() {
let table = MergeTable::from_raw(7, &[(0, 1, 5, 0), (2, 3, 6, 1)]).unwrap();
let (next, merges) = single_rank_pass(&ids(&[0, 1, 2, 3]), &table).unwrap();
assert_eq!(next, ids(&[5, 2, 3]));
assert_eq!(merges, 1);
}
#[test]
fn multi_merge_pass_reports_none_when_nothing_merges() {
let table = MergeTable::from_raw(4, &[(0, 1, 2, 0)]).unwrap();
assert!(single_rank_pass(&ids(&[]), &table).is_none());
assert!(single_rank_pass(&ids(&[0]), &table).is_none());
assert!(single_rank_pass(&ids(&[1, 0]), &table).is_none());
assert!(single_rank_pass(&ids(&[3, 3, 3]), &table).is_none());
}
#[test]
fn every_returned_pass_performs_at_least_one_merge() {
let mut rng = SplitMix64::new(0x5eed);
let table = unconstrained_table(
&mut rng,
UnconstrainedSpec {
base: 3,
merged: 3,
rank_pool: 2,
density_percent: 60,
},
);
let mut checked = 0usize;
for_each_sequence(6, 1, 5, &mut |sequence| {
let mut state = sequence.to_vec();
while let Some((next, merges)) = single_rank_pass(&state, &table) {
assert!(merges >= 1, "pass made no progress on {state:?}");
assert!(next.len() < state.len(), "pass did not shrink {state:?}");
state = next;
checked += 1;
}
});
assert_eq!(checked, 21287);
}
#[test]
fn multi_merge_pass_count_tracks_cascade_depth() {
let table = cascade_table(3).unwrap();
let trace = single_rank_multi_merge(&ids(&[0, 0, 0, 0]), &table);
assert_eq!(trace.tokens, ids(&[2]));
assert_eq!(trace.merges, 3);
assert_eq!(trace.passes, 2);
}
#[test]
fn rank_phase_stops_when_the_minimum_rank_moves() {
let table = cascade_table(3).unwrap();
let phase = sequential_rank_phase(&ids(&[0, 0, 0, 0]), &table).unwrap();
assert_eq!(phase.rank, Rank(0));
assert_eq!(phase.tokens, ids(&[1, 1]));
assert_eq!(phase.merges, 2);
assert!(sequential_rank_phase(&ids(&[3, 3]), &table).is_none());
}
#[test]
fn enumerator_visits_every_sequence_exactly_once() {
let mut seen: Vec<Vec<u32>> = Vec::new();
let visited = for_each_sequence(2, 1, 3, &mut |sequence| {
seen.push(sequence.iter().map(|t| t.0).collect());
});
assert_eq!(visited, 14);
assert_eq!(visited, sequence_count(2, 1, 3));
assert_eq!(seen[0], vec![0]);
assert_eq!(seen[1], vec![1]);
assert_eq!(seen[2], vec![0, 0]);
assert_eq!(seen[5], vec![1, 1]);
assert_eq!(seen[6], vec![0, 0, 0]);
assert_eq!(seen[13], vec![1, 1, 1]);
let mut deduped = seen.clone();
deduped.sort();
deduped.dedup();
assert_eq!(deduped.len(), 14);
assert_eq!(for_each_sequence(1, 1, 4, &mut |_| {}), 4);
assert_eq!(for_each_sequence(0, 1, 4, &mut |_| {}), 0);
assert_eq!(sequence_count(4, 1, 8), 87380);
assert_eq!(sequence_count(3, 1, 12), 797160);
}
#[test]
fn splitmix64_stream_is_fixed() {
let mut rng = SplitMix64::new(0);
assert_eq!(rng.next_u64(), 0xe220_a839_7b1d_cdaf);
assert_eq!(rng.next_u64(), 0x6e78_9e6a_a1b9_65f4);
assert_eq!(rng.next_u64(), 0x06c4_5d18_8009_454f);
assert_eq!(rng.next_u64(), 0xf88b_b8a8_724c_81ec);
let mut seeded = SplitMix64::new(0x243f_6a88_85a3_08d3);
assert_eq!(seeded.next_u64(), 0x2cb0_f69f_4abe_a221);
assert_eq!(seeded.next_u64(), 0x9417_0347_2314_8989);
let mut bounded = SplitMix64::new(0);
assert_eq!(
(0..4).map(|_| bounded.below(10)).collect::<Vec<_>>(),
vec![5, 0, 9, 4]
);
assert_eq!(bounded.below(0), 0);
assert_eq!(bounded.below(1), 0);
}
#[test]
fn shuffle_is_a_permutation() {
let mut rng = SplitMix64::new(7);
let mut items: Vec<u32> = (0..64).collect();
rng.shuffle(&mut items);
assert_ne!(items, (0..64).collect::<Vec<_>>());
let mut sorted = items.clone();
sorted.sort_unstable();
assert_eq!(sorted, (0..64).collect::<Vec<_>>());
let mut single = vec![9u32];
rng.shuffle(&mut single);
assert_eq!(single, vec![9]);
let mut empty: Vec<u32> = Vec::new();
rng.shuffle(&mut empty);
assert!(empty.is_empty());
}
#[test]
fn parent_ordered_generator_never_violates_parent_order() {
let mut nonempty = 0usize;
for seed in 0..256u64 {
for spec in [
ParentOrderedSpec {
base: 2,
groups: 2,
per_group: 1,
},
ParentOrderedSpec {
base: 2,
groups: 1,
per_group: 2,
},
ParentOrderedSpec {
base: 1,
groups: 3,
per_group: 1,
},
ParentOrderedSpec {
base: 4,
groups: 3,
per_group: 3,
},
] {
let mut rng = SplitMix64::new(seed);
let table = parent_ordered_table(&mut rng, spec);
assert_eq!(
table.parent_order_violations(),
Vec::new(),
"seed {seed} spec {spec:?} produced {table}"
);
assert_eq!(table.universe(), spec.universe());
if table.entry_count() > 0 {
nonempty += 1;
}
}
}
assert_eq!(nonempty, 1024);
}
#[test]
fn string_vocab_id_order_controls_rank_inversions() {
let spec = |id_order| StringVocabSpec {
alphabet: 2,
max_token_len: 5,
keep_percent: 100,
id_order,
};
let mut rng = SplitMix64::new(11);
let permuted = string_vocab_table(&mut rng, spec(IdOrder::Permuted));
assert_eq!(permuted.entry_count(), 4 + 2 * 8 + 3 * 16 + 4 * 32);
assert_eq!(permuted.universe(), 62);
assert!(
permuted.parent_order_violations().len() > 40,
"expected many inversions, got {}",
permuted.parent_order_violations().len()
);
assert!(!permuted.is_parent_ordered());
let mut rng = SplitMix64::new(11);
let by_length = string_vocab_table(&mut rng, spec(IdOrder::ByLength));
assert_eq!(by_length.entry_count(), permuted.entry_count());
assert_eq!(by_length.universe(), permuted.universe());
assert_eq!(
by_length.parent_order_violations(),
Vec::new(),
"length-ordered ids cannot invert: a concatenation is longer than \
either half, so it takes a higher id"
);
assert!(by_length.is_parent_ordered());
for table in [&permuted, &by_length] {
for (_, merge) in table.entries() {
assert_eq!(merge.rank.0, merge.id.0);
}
}
}
#[test]
fn cl100k_space_run_ids_are_the_real_non_monotonic_chain() {
assert_eq!(CL100K_SPACE_RUN_IDS[0], 220);
assert_eq!(CL100K_SPACE_RUN_IDS[1], 256);
assert_eq!(CL100K_SPACE_RUN_IDS[2], 262);
assert_eq!(CL100K_SPACE_RUN_IDS[3], 257);
assert_eq!(CL100K_SPACE_RUN_IDS[4], 415);
assert_eq!(CL100K_SPACE_RUN_IDS[5], 996);
assert_eq!(CL100K_SPACE_RUN_IDS[6], 286);
assert_eq!(CL100K_SPACE_RUN_IDS[7], 260);
assert!(CL100K_SPACE_RUN_IDS[3] < CL100K_SPACE_RUN_IDS[2]);
assert!(CL100K_SPACE_RUN_IDS[7] < CL100K_SPACE_RUN_IDS[6]);
let mut sorted = CL100K_SPACE_RUN_IDS;
sorted.sort_unstable();
assert_ne!(sorted, CL100K_SPACE_RUN_IDS);
}
#[test]
fn cl100k_space_run_table_carries_real_ranks() {
let table = cl100k_space_run_table().unwrap();
assert_eq!(table.universe(), 32);
assert_eq!(table.entry_count(), 496);
assert_eq!(table.rank_of(TokenId(0), TokenId(0)), Rank(256));
assert_eq!(table.rank_of(TokenId(0), TokenId(1)), Rank(262));
assert_eq!(table.rank_of(TokenId(2), TokenId(0)), Rank(257));
assert!(
table.rank_of(TokenId(2), TokenId(0)).0 < table.rank_of(TokenId(0), TokenId(1)).0,
"the 262 -> 257 inversion is the point of this table"
);
assert_eq!(table.rank_of(TokenId(0), TokenId(5)), Rank(286));
assert_eq!(table.rank_of(TokenId(6), TokenId(0)), Rank(260));
assert!(!table.is_parent_ordered());
}
#[test]
fn all_pairs_tie_table_is_complete() {
let table = all_pairs_tie_table(3).unwrap();
assert_eq!(table.entry_count(), 9);
assert_eq!(table.universe(), 12);
let mut minted = Vec::new();
for (pair, merge) in table.entries() {
assert_eq!(merge.rank, Rank(0));
assert!(pair.left().0 < 3 && pair.right().0 < 3);
minted.push(merge.id.0);
}
assert_eq!(minted, vec![3, 4, 5, 6, 7, 8, 9, 10, 11]);
assert!(table.is_parent_ordered());
}
#[test]
fn cascade_table_has_one_entry_per_level() {
let table = cascade_table(4).unwrap();
assert_eq!(table.entry_count(), 4);
assert_eq!(table.universe(), 5);
for level in 0..4 {
assert_eq!(
table.lookup(TokenId(level), TokenId(level)),
Some(Merge {
id: TokenId(level + 1),
rank: Rank(level)
})
);
}
assert!(table.is_parent_ordered());
assert_eq!(cascade_table(0).unwrap().entry_count(), 0);
}
#[test]
fn classify_separates_agreement_from_divergence() {
let good = cascade_table(3).unwrap();
assert_eq!(classify(&ids(&[0, 0, 0, 0]), &good), None);
let bad = MergeTable::from_raw(3, &[(0, 0, 1, 1), (1, 0, 2, 0)]).unwrap();
assert_eq!(
classify(&ids(&[0, 0, 0, 0]), &bad),
Some(DivergenceKind::FinalTokens)
);
}
#[test]
fn minimizer_shrinks_to_the_known_core() {
let padded = MergeTable::from_raw(
6,
&[
(0, 0, 1, 40),
(1, 0, 2, 10),
(4, 4, 5, 70),
(3, 3, 4, 60),
(2, 2, 3, 50),
],
)
.unwrap();
let found = Divergence::capture(&ids(&[0, 0, 0, 0, 0, 0]), &padded).unwrap();
assert_eq!(found.kind, DivergenceKind::FinalTokens);
let small = minimize(found);
assert_eq!(small.kind, DivergenceKind::FinalTokens);
assert_eq!(small.input, ids(&[0, 0, 0, 0]));
assert_eq!(small.table.entry_count(), 2);
assert_eq!(
small.table.lookup(TokenId(0), TokenId(0)),
Some(Merge {
id: TokenId(1),
rank: Rank(1)
})
);
assert_eq!(
small.table.lookup(TokenId(1), TokenId(0)),
Some(Merge {
id: TokenId(2),
rank: Rank(0)
})
);
assert_eq!(small.sequential, ids(&[2, 0]));
assert_eq!(small.multi, ids(&[1, 1]));
assert_eq!(small.violations.len(), 1);
}
}