use std::collections::BTreeMap;
use crate::{PairKey, Rank, TokenId, ExatokError};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct MergeEntry {
pub id: TokenId,
pub rank: Rank,
}
pub trait MergeTable {
fn lookup(&self, pair: PairKey) -> Option<MergeEntry>;
fn rank(&self, pair: PairKey) -> Rank {
match self.lookup(pair) {
Some(entry) => entry.rank,
None => Rank::ABSENT,
}
}
}
impl<T: MergeTable + ?Sized> MergeTable for &T {
fn lookup(&self, pair: PairKey) -> Option<MergeEntry> {
(**self).lookup(pair)
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct HostMergeTable {
entries: BTreeMap<PairKey, MergeEntry>,
}
impl HostMergeTable {
#[must_use]
pub fn new() -> Self {
Self {
entries: BTreeMap::new(),
}
}
pub fn from_entries(
artifact: &str,
entries: impl IntoIterator<Item = (PairKey, TokenId, Rank)>,
) -> Result<Self, ExatokError> {
let mut table = Self::new();
for (pair, id, rank) in entries {
table.insert(artifact, pair, id, rank)?;
}
Ok(table)
}
pub fn insert(
&mut self,
artifact: &str,
pair: PairKey,
id: TokenId,
rank: Rank,
) -> Result<(), ExatokError> {
if !rank.is_present() {
return Err(ExatokError::Artifact {
artifact: artifact.to_owned(),
location: pair_location(pair),
detail: "merge rank equals the ABSENT sentinel u32::MAX".to_owned(),
fix: "renumber merges so every real rank stays below u32::MAX, \
keeping the sentinel unused so a min reduction skips \
unmergeable pairs"
.to_owned(),
});
}
if let Some(existing) = self.entries.get(&pair) {
return Err(ExatokError::Artifact {
artifact: artifact.to_owned(),
location: pair_location(pair),
detail: format!(
"duplicate merge: rank {} already recorded, rank {} seen again",
existing.rank.0, rank.0
),
fix: "remove the repeated pair from the merge list so exactly \
one rank governs it"
.to_owned(),
});
}
self.entries.insert(pair, MergeEntry { id, rank });
Ok(())
}
#[must_use]
pub fn len(&self) -> usize {
self.entries.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn iter(&self) -> impl Iterator<Item = (PairKey, MergeEntry)> + '_ {
self.entries.iter().map(|(&pair, &entry)| (pair, entry))
}
}
impl MergeTable for HostMergeTable {
fn lookup(&self, pair: PairKey) -> Option<MergeEntry> {
self.entries.get(&pair).copied()
}
}
fn pair_location(pair: PairKey) -> String {
format!("pair ({}, {})", pair.left().0, pair.right().0)
}
fn best_merge(tokens: &[TokenId], table: &impl MergeTable) -> Option<(usize, MergeEntry)> {
let mut best: Option<(usize, MergeEntry)> = None;
for (index, window) in tokens.windows(2).enumerate() {
let (Some(&left), Some(&right)) = (window.first(), window.get(1)) else {
continue;
};
let Some(entry) = table.lookup(PairKey::new(left, right)) else {
continue;
};
let wins = match best {
None => true,
Some((_, current)) => entry.rank < current.rank,
};
if wins {
best = Some((index, entry));
}
}
best
}
fn apply_merge(state: &mut Vec<TokenId>, index: usize, merged: TokenId) {
if index + 1 >= state.len() {
return;
}
state[index] = merged;
state.remove(index + 1);
}
fn merge_to_fixpoint(state: &mut Vec<TokenId>, table: &impl MergeTable) {
while let Some((index, entry)) = best_merge(state, table) {
apply_merge(state, index, entry.id);
}
}
#[must_use]
pub fn encode_pretoken(tokens: &[TokenId], table: &impl MergeTable) -> Vec<TokenId> {
let mut state = tokens.to_vec();
merge_to_fixpoint(&mut state, table);
state
}
#[must_use]
pub fn encode<S: AsRef<[TokenId]>>(pretokens: &[S], table: &impl MergeTable) -> Vec<TokenId> {
let mut ids = Vec::new();
let mut state: Vec<TokenId> = Vec::new();
for pretoken in pretokens {
state.clear();
state.extend_from_slice(pretoken.as_ref());
merge_to_fixpoint(&mut state, table);
ids.extend_from_slice(&state);
}
ids
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MergeStep {
pub index: usize,
pub pair: PairKey,
pub merged: TokenId,
pub rank: Rank,
pub state: Vec<TokenId>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MergeTrace {
initial: Vec<TokenId>,
steps: Vec<MergeStep>,
}
impl MergeTrace {
#[must_use]
pub fn initial(&self) -> &[TokenId] {
&self.initial
}
#[must_use]
pub fn steps(&self) -> &[MergeStep] {
&self.steps
}
#[must_use]
pub fn merge_count(&self) -> usize {
self.steps.len()
}
#[must_use]
pub fn final_state(&self) -> &[TokenId] {
match self.steps.last() {
Some(step) => &step.state,
None => &self.initial,
}
}
}
#[must_use]
pub fn trace_pretoken(tokens: &[TokenId], table: &impl MergeTable) -> MergeTrace {
let mut state = tokens.to_vec();
let mut steps = Vec::new();
while let Some((index, entry)) = best_merge(&state, table) {
let pair = match (state.get(index), state.get(index + 1)) {
(Some(&left), Some(&right)) => PairKey::new(left, right),
_ => break,
};
apply_merge(&mut state, index, entry.id);
steps.push(MergeStep {
index,
pair,
merged: entry.id,
rank: entry.rank,
state: state.clone(),
});
}
MergeTrace {
initial: tokens.to_vec(),
steps,
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use super::{
encode_pretoken, trace_pretoken, HostMergeTable, MergeEntry, MergeStep, MergeTable,
};
use crate::{PairKey, Rank, TokenId, ExatokError};
fn pair(left: u32, right: u32) -> PairKey {
PairKey::new(TokenId(left), TokenId(right))
}
#[test]
fn lookup_returns_exact_id_and_rank() {
let table = HostMergeTable::from_entries(
"synthetic",
[(pair(1, 2), TokenId(300), Rank(7))],
)
.unwrap();
assert_eq!(
table.lookup(pair(1, 2)),
Some(MergeEntry {
id: TokenId(300),
rank: Rank(7),
})
);
assert_eq!(table.rank(pair(1, 2)), Rank(7));
assert_eq!(table.len(), 1);
}
#[test]
fn missing_pair_reports_absent_sentinel() {
let table = HostMergeTable::new();
assert_eq!(table.lookup(pair(1, 2)), None);
assert_eq!(table.rank(pair(1, 2)), Rank::ABSENT);
assert_eq!(table.rank(pair(1, 2)).0, u32::MAX);
assert!(!table.rank(pair(1, 2)).is_present());
assert_eq!(table.len(), 0);
}
#[test]
fn absent_sentinel_rejected_as_real_rank() {
let error = HostMergeTable::from_entries(
"synthetic.tiktoken",
[(pair(1, 2), TokenId(9), Rank::ABSENT)],
)
.expect_err("ABSENT must not be accepted as a merge rank");
match error {
ExatokError::Artifact {
artifact,
location,
detail,
fix,
} => {
assert_eq!(artifact, "synthetic.tiktoken");
assert_eq!(location, "pair (1, 2)");
assert_eq!(detail, "merge rank equals the ABSENT sentinel u32::MAX");
assert_eq!(
fix,
"renumber merges so every real rank stays below u32::MAX, keeping \
the sentinel unused so a min reduction skips unmergeable pairs"
);
}
other => panic!("expected Artifact error, got {other:?}"),
}
}
#[test]
fn duplicate_pair_rejected_and_table_unchanged() {
let mut table =
HostMergeTable::from_entries("synthetic", [(pair(1, 2), TokenId(9), Rank(4))]).unwrap();
let error = table
.insert("synthetic", pair(1, 2), TokenId(11), Rank(6))
.expect_err("a duplicate pair must be rejected");
match error {
ExatokError::Artifact { detail, fix, .. } => {
assert_eq!(
detail,
"duplicate merge: rank 4 already recorded, rank 6 seen again"
);
assert_eq!(
fix,
"remove the repeated pair from the merge list so exactly one rank \
governs it"
);
}
other => panic!("expected Artifact error, got {other:?}"),
}
assert_eq!(table.len(), 1);
assert_eq!(
table.lookup(pair(1, 2)),
Some(MergeEntry {
id: TokenId(9),
rank: Rank(4),
})
);
}
#[test]
fn iter_is_ordered_by_packed_key() {
let table = HostMergeTable::from_entries(
"synthetic",
[
(pair(2, 0), TokenId(31), Rank(1)),
(pair(1, 9), TokenId(30), Rank(2)),
(pair(1, 3), TokenId(32), Rank(0)),
],
)
.unwrap();
let keys: Vec<(u32, u32)> = table
.iter()
.map(|(key, _)| (key.left().0, key.right().0))
.collect();
assert_eq!(keys, vec![(1, 3), (1, 9), (2, 0)]);
}
fn chain_table() -> HostMergeTable {
HostMergeTable::from_entries(
"synthetic.chain",
[
(pair(1, 2), TokenId(10), Rank(0)),
(pair(10, 3), TokenId(11), Rank(1)),
(pair(11, 4), TokenId(12), Rank(2)),
],
)
.unwrap()
}
#[test]
fn trace_final_state_matches_encode_pretoken() {
let table = chain_table();
let inputs: Vec<Vec<TokenId>> = vec![
vec![],
vec![TokenId(1)],
vec![TokenId(7), TokenId(8)],
vec![TokenId(1), TokenId(2)],
vec![TokenId(1), TokenId(2), TokenId(3)],
vec![TokenId(1), TokenId(2), TokenId(3), TokenId(4)],
vec![
TokenId(1),
TokenId(2),
TokenId(3),
TokenId(4),
TokenId(1),
TokenId(2),
],
];
for tokens in inputs {
let encoded = encode_pretoken(&tokens, &table);
let trace = trace_pretoken(&tokens, &table);
assert_eq!(
trace.final_state(),
encoded.as_slice(),
"trace and encoder disagree on {tokens:?}"
);
assert_eq!(trace.initial(), tokens.as_slice());
}
}
#[test]
fn trace_records_every_step_with_exact_indices_and_ranks() {
let table = chain_table();
let tokens = vec![TokenId(1), TokenId(2), TokenId(3), TokenId(4)];
let trace = trace_pretoken(&tokens, &table);
assert_eq!(encode_pretoken(&tokens, &table), vec![TokenId(12)]);
assert_eq!(trace.merge_count(), 3);
assert_eq!(trace.final_state(), &[TokenId(12)]);
let expected = [
MergeStep {
index: 0,
pair: pair(1, 2),
merged: TokenId(10),
rank: Rank(0),
state: vec![TokenId(10), TokenId(3), TokenId(4)],
},
MergeStep {
index: 0,
pair: pair(10, 3),
merged: TokenId(11),
rank: Rank(1),
state: vec![TokenId(11), TokenId(4)],
},
MergeStep {
index: 0,
pair: pair(11, 4),
merged: TokenId(12),
rank: Rank(2),
state: vec![TokenId(12)],
},
];
assert_eq!(trace.steps(), expected.as_slice());
}
#[test]
fn unmergeable_input_traces_no_steps_and_keeps_its_bytes() {
let table = chain_table();
let tokens = vec![TokenId(7), TokenId(8), TokenId(9)];
let trace = trace_pretoken(&tokens, &table);
assert_eq!(trace.merge_count(), 0);
assert!(trace.steps().is_empty());
assert_eq!(trace.final_state(), &[TokenId(7), TokenId(8), TokenId(9)]);
assert_eq!(
encode_pretoken(&tokens, &table),
vec![TokenId(7), TokenId(8), TokenId(9)]
);
}
}