use crate::pretokenize::{SplitPattern, spans};
use crate::reference::{HostMergeTable, MergeTable, encode};
use crate::{PairKey, Rank, TokenId, ExatokError};
#[must_use]
pub fn pretoken_ids(
pattern: SplitPattern,
input: &[u8],
bytes: &[TokenId; 256],
) -> Vec<Vec<TokenId>> {
spans(pattern, input)
.into_iter()
.map(|span| {
input[span.start..span.end]
.iter()
.map(|&byte| bytes[byte as usize])
.collect()
})
.collect()
}
#[must_use]
pub fn encode_bytes(
pattern: SplitPattern,
input: &[u8],
bytes: &[TokenId; 256],
table: &impl MergeTable,
) -> Vec<TokenId> {
encode(&pretoken_ids(pattern, input, bytes), table)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Segment {
pub offset: usize,
pub bytes: Vec<u8>,
pub ids: Vec<TokenId>,
}
#[must_use]
pub fn encode_segments(
pattern: SplitPattern,
input: &[u8],
bytes: &[TokenId; 256],
table: &impl MergeTable,
) -> Vec<Segment> {
spans(pattern, input)
.into_iter()
.map(|span| {
let piece = &input[span.start..span.end];
let start: Vec<TokenId> = piece.iter().map(|&byte| bytes[byte as usize]).collect();
Segment {
offset: span.start,
bytes: piece.to_vec(),
ids: encode(std::slice::from_ref(&start), table),
}
})
.collect()
}
#[must_use]
pub fn segment_ids(segments: &[Segment]) -> Vec<TokenId> {
segments
.iter()
.flat_map(|segment| segment.ids.iter().copied())
.collect()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct IdMismatch {
pub index: usize,
pub expected: Option<TokenId>,
pub actual: Option<TokenId>,
}
#[must_use]
pub fn first_mismatch(expected: &[TokenId], actual: &[TokenId]) -> Option<IdMismatch> {
let shared = expected.len().min(actual.len());
for index in 0..shared {
if expected[index] != actual[index] {
return Some(IdMismatch {
index,
expected: expected.get(index).copied(),
actual: actual.get(index).copied(),
});
}
}
if expected.len() == actual.len() {
return None;
}
Some(IdMismatch {
index: shared,
expected: expected.get(shared).copied(),
actual: actual.get(shared).copied(),
})
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Divergence {
pub index: usize,
pub expected: Option<TokenId>,
pub actual: Option<TokenId>,
pub pretoken_index: usize,
pub byte_offset: usize,
pub pretoken: Vec<u8>,
pub index_in_pretoken: usize,
}
fn quoted(bytes: &[u8]) -> String {
let mut out = String::with_capacity(bytes.len() + 2);
out.push('"');
for &byte in bytes {
match byte {
b'"' => out.push_str("\\\""),
b'\\' => out.push_str("\\\\"),
0x20..=0x7e => out.push(byte as char),
_ => {
use std::fmt::Write;
let _ = write!(out, "\\x{byte:02x}");
}
}
}
out.push('"');
out
}
impl std::fmt::Display for Divergence {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let show = |id: Option<TokenId>| match id {
Some(id) => id.0.to_string(),
None => "<stream ended>".to_owned(),
};
write!(
formatter,
"id {} differs: reference {}, exatok {}; byte offset {}, pretoken {} {}, id {} of \
that pretoken",
self.index,
show(self.expected),
show(self.actual),
self.byte_offset,
self.pretoken_index,
quoted(&self.pretoken),
self.index_in_pretoken
)
}
}
#[must_use]
pub fn first_divergence(expected: &[TokenId], segments: &[Segment]) -> Option<Divergence> {
let actual = segment_ids(segments);
let mismatch = first_mismatch(expected, &actual)?;
let mut base = 0usize;
let mut located = None;
for (index, segment) in segments.iter().enumerate() {
if mismatch.index < base + segment.ids.len() {
located = Some((index, mismatch.index - base));
break;
}
base += segment.ids.len();
}
let (pretoken_index, index_in_pretoken) = located.unwrap_or_else(|| {
let last = segments.len().saturating_sub(1);
(last, segments.last().map_or(0, |segment| segment.ids.len()))
});
let (byte_offset, pretoken) = segments.get(pretoken_index).map_or_else(
|| (0, Vec::new()),
|segment| (segment.offset, segment.bytes.clone()),
);
Some(Divergence {
index: mismatch.index,
expected: mismatch.expected,
actual: mismatch.actual,
pretoken_index,
byte_offset,
pretoken,
index_in_pretoken,
})
}
#[must_use]
pub fn compare(
pattern: SplitPattern,
input: &[u8],
bytes: &[TokenId; 256],
table: &impl MergeTable,
expected: &[TokenId],
) -> Option<Divergence> {
first_divergence(expected, &encode_segments(pattern, input, bytes, table))
}
pub fn with_rank_replaced(
artifact: &str,
table: &HostMergeTable,
pair: PairKey,
rank: Rank,
) -> Result<HostMergeTable, ExatokError> {
if table.lookup(pair).is_none() {
return Err(ExatokError::Artifact {
artifact: artifact.to_owned(),
location: format!("pair ({}, {})", pair.left().0, pair.right().0),
detail: "cannot replace the rank of a pair the table does not hold".to_owned(),
fix: "pick a pair that is present, so the corruption actually changes the table"
.to_owned(),
});
}
HostMergeTable::from_entries(
artifact,
table.iter().map(|(key, entry)| {
let replaced = if key == pair { rank } else { entry.rank };
(key, entry.id, replaced)
}),
)
}
pub fn without_pair(
artifact: &str,
table: &HostMergeTable,
pair: PairKey,
) -> Result<HostMergeTable, ExatokError> {
if table.lookup(pair).is_none() {
return Err(ExatokError::Artifact {
artifact: artifact.to_owned(),
location: format!("pair ({}, {})", pair.left().0, pair.right().0),
detail: "cannot remove a pair the table does not hold".to_owned(),
fix: "pick a pair that is present, so the removal actually changes the table"
.to_owned(),
});
}
HostMergeTable::from_entries(
artifact,
table
.iter()
.filter(|(key, _)| *key != pair)
.map(|(key, entry)| (key, entry.id, entry.rank)),
)
}
#[must_use]
pub fn first_merge(tokens: &[TokenId], table: &impl MergeTable) -> Option<PairKey> {
let mut best: Option<(Rank, PairKey)> = None;
for window in tokens.windows(2) {
let pair = PairKey::new(window[0], window[1]);
let rank = table.rank(pair);
if !rank.is_present() {
continue;
}
if best.is_none_or(|(current, _)| rank < current) {
best = Some((rank, pair));
}
}
best.map(|(_, pair)| pair)
}
pub fn decode_hex(artifact: &str, text: &str) -> Result<Vec<u8>, ExatokError> {
let error = |location: String, detail: String| ExatokError::Artifact {
artifact: artifact.to_owned(),
location,
detail,
fix: "store the field as an even-length string of characters 0-9 and a-f".to_owned(),
};
let raw = text.as_bytes();
if raw.len() % 2 != 0 {
return Err(error(
format!("length {}", raw.len()),
"hex string has an odd number of characters".to_owned(),
));
}
let mut out = Vec::with_capacity(raw.len() / 2);
for (index, chunk) in raw.chunks_exact(2).enumerate() {
let mut value = 0u8;
for (half, &character) in chunk.iter().enumerate() {
let digit = match character {
b'0'..=b'9' => character - b'0',
b'a'..=b'f' => character - b'a' + 10,
_ => {
return Err(error(
format!("character {}", index * 2 + half),
format!("{:?} is not a lowercase hex digit", character as char),
));
}
};
value = (value << 4) | digit;
}
out.push(value);
}
Ok(out)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Case {
pub name: &'static str,
pub concern: &'static str,
pub text: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ByteCase {
pub name: &'static str,
pub concern: &'static str,
pub bytes: Vec<u8>,
pub pretokens: Vec<Vec<u8>>,
}
#[must_use]
pub fn fixture_name(vocabulary: &str) -> String {
format!("parity_{vocabulary}.json")
}
#[must_use]
#[allow(clippy::too_many_lines)]
pub fn corpus() -> Vec<Case> {
let case = |name: &'static str, concern: &'static str, text: &str| Case {
name,
concern,
text: text.to_owned(),
};
vec![
case(
"ascii_prose",
"plain ASCII words and sentence punctuation, the base case every other case deviates from",
"The quick brown fox jumps over the lazy dog. Tokenizers must agree on \
every byte, not almost every byte.",
),
case(
"indented_source_spaces",
"space-indented code, where the non-monotonic whitespace merge ranks live",
"fn main() {\n let total = 0;\n if total > 0 {\n \
println!(\"total {total}\");\n }\n}\n",
),
case(
"indented_source_tabs",
"tab-indented code, a different whitespace token family than spaces",
"def main():\n\tif True:\n\t\treturn 1\n\treturn 0\n",
),
case(
"deep_indent_ladder",
"indent widths 4 through 24 in one input, the densest source of whitespace merges that lower their own rank",
"a\n b\n c\n d\n e\n f\n g\n",
),
case(
"whitespace_runs",
"space runs of length 1 through 8 between words, each a different whitespace token",
"a b c d e f g h i",
),
Case {
name: "long_space_run",
concern: "a 64-space run, far past any single whitespace token, so it must decompose exactly",
text: format!("start{}end", " ".repeat(64)),
},
case(
"trailing_whitespace",
"whitespace at end of input, the only place the pattern alternative \\s++$ applies",
"text with trailing spaces ",
),
case(
"newlines_only",
"input that is nothing but newlines, where \\s*[\\r\\n] and \\s+(?!\\S) compete",
"\n\n\n\n\n",
),
case(
"crlf_mixed",
"CRLF line endings including a blank line and a bare trailing CR",
"one\r\ntwo\r\n\r\nthree\r",
),
case(
"blank_lines_indented",
"whitespace-only lines mixing spaces and tabs, which the newline alternatives must absorb",
"a\n\n \n\tb\n",
),
case(
"contractions_ascii",
"every ASCII contraction alternative the split patterns enumerate",
"I'm sure it's John's, they're here, we'll go, I've seen, don't, can't, isn't, o'clock",
),
case(
"contractions_uppercase",
"uppercase contractions, which cl100k folds with (?i:) and gpt2 does not",
"IT'S HE'LL WE'VE THEY'RE DON'T I'M",
),
case(
"contraction_long_s",
"U+017F LATIN SMALL LETTER LONG S after an apostrophe, the only non-ASCII member of any fold class these patterns use",
"it'\u{17f} and it's",
),
case(
"digit_runs",
"digit runs of length 1 through 10, crossing the cl100k three-digit cap",
"1 12 123 1234 12345 123456 1234567890",
),
Case {
name: "long_digit_run",
concern: "a 50-digit run, so the three-digit cap fires sixteen times in one pretoken sequence",
text: "1234567890".repeat(5),
},
case(
"digits_in_text",
"digits fused to letters and punctuation, versions, hex, dates, and leading zeros",
"version 3.14159 built 20240630 at 0x7fff, port 8080, id 000123",
),
case(
"multibyte_utf8",
"two- and three-byte UTF-8 across Latin-1 supplement, Greek, Cyrillic, and punctuation",
"na\u{ef}ve caf\u{e9} r\u{e9}sum\u{e9} \u{3a9}\u{2248}\u{e7}\u{221a} \
\u{a1}Hola! \u{41f}\u{440}\u{438}\u{432}\u{435}\u{442} \u{43c}\u{438}\u{440} \
\u{ab}guillemets\u{bb} ellipsis\u{2026}",
),
case(
"cjk_mixed",
"CJK and Hangul, where every character is three UTF-8 bytes and no space separates words",
"\u{65e5}\u{672c}\u{8a9e}\u{306e}\u{30c8}\u{30fc}\u{30af}\u{30f3}\u{5316}\u{306f}\u{96e3}\u{3057}\u{3044}\u{3002}\
\u{4e2d}\u{6587}\u{5206}\u{8bcd}\u{4e5f}\u{4e00}\u{6837}\u{3002}\
\u{d55c}\u{ad6d}\u{c5b4}\u{b3c4} \u{b9c8}\u{cc2c}\u{ac00}\u{c9c0}\u{b2e4}.",
),
case(
"combining_marks",
"combining marks after base letters, which \\p{M} keeps inside the letter run",
"e\u{301}a\u{308}o\u{303} \u{915}\u{94d}\u{937} \u{5d0}\u{5b8}",
),
case(
"rtl_scripts",
"right-to-left Arabic and Hebrew, whose bytes carry no ASCII structure at all",
"\u{645}\u{631}\u{62d}\u{628}\u{627} \u{628}\u{627}\u{644}\u{639}\u{627}\u{644}\u{645} \
\u{5e9}\u{5dc}\u{5d5}\u{5dd} \u{5e2}\u{5d5}\u{5dc}\u{5dd}",
),
case(
"emoji_zwj",
"a four-person ZWJ family, a ZWJ flag with a variation selector, a skin-tone modifier, and a regional-indicator pair",
"\u{1f469}\u{200d}\u{1f469}\u{200d}\u{1f467}\u{200d}\u{1f466} family \
\u{1f3f3}\u{fe0f}\u{200d}\u{1f308} flag \u{1f44d}\u{1f3fd} thumbs \
\u{1f600} plain \u{1f1fa}\u{1f1f8} pair",
),
case(
"emoji_dense",
"ten adjacent four-byte emoji with no separator, so every merge candidate is a four-byte boundary",
"\u{1f600}\u{1f603}\u{1f604}\u{1f601}\u{1f606}\
\u{1f605}\u{1f923}\u{1f602}\u{1f642}\u{1f643}",
),
case(
"zero_width_and_bidi",
"zero-width space, zero-width joiner, BOM, and a bidi override, none of which are White_Space",
"a\u{200b}b\u{200d}c\u{feff}d\u{202e}e",
),
case(
"unicode_whitespace",
"non-ASCII White_Space characters, which \\s matches but [\\r\\n] does not",
"a\u{a0}b\u{2009}c\u{3000}d\u{2028}e\u{85}f",
),
case(
"control_chars",
"NUL, BEL, ESC, and DEL embedded in text, the bytes a naive reader would truncate on",
"a\u{0}b\u{7}c\u{1b}[0md\u{7f}e",
),
case(
"endoftext_literal",
"special-token spellings appearing as ordinary text, which encode_ordinary must not promote to a special id",
"before <|endoftext|> after <|fim_prefix|> <|im_start|>role<|im_end|>",
),
case(
"empty",
"empty input, which must produce zero ids rather than one empty pretoken",
"",
),
case(
"single_space",
"one space, the shortest input that is entirely whitespace",
" ",
),
Case {
name: "long_letter_run",
concern: "a 500-character single-class letter run, near the longest pretoken observed in real corpora",
text: "a".repeat(500),
},
Case {
name: "long_alternating_run",
concern: "500 characters alternating two letters, which defeats any repeated-token shortcut",
text: "ab".repeat(250),
},
Case {
name: "long_digit_wall",
concern: "500 digits with no separator, so the three-digit cap produces 167 consecutive pretokens under cl100k",
text: "9".repeat(500),
},
case(
"punctuation_dense",
"a long punctuation run, the alternative that greedily absorbs every non-letter non-digit non-space byte",
"!!!???...,,,;;;:::(){}[]<>/\\|@#$%^&*-_=+~`\"'",
),
case(
"mixed_case_identifiers",
"camel, snake, and screaming-snake identifiers, whose case boundaries split differently per pattern",
"CamelCaseIdentifier snake_case_name SCREAMING_SNAKE xmlHTTPRequest getURLFromID",
),
case(
"json_blob",
"JSON punctuation adjacency, where quotes, colons, and brackets crowd every letter run",
"{\"key\": [1, 2, 3], \"nested\": {\"a\": null, \"b\": true}}",
),
case(
"markdown_table",
"pipe-and-dash table rows, a punctuation-heavy shape with newline-terminated runs",
"| a | b |\n|---|---|\n| 1 | 2 |\n",
),
case(
"url_and_path",
"URLs and filesystem paths, including a Windows path whose separator is a backslash",
"https://example.com/a/b?c=d&e=f#g /usr/local/bin/python3 C:\\Windows\\System32",
),
Case {
name: "repeated_word",
concern: "the same word fifty times, so a per-pretoken cache bug would show as a wrong id late in the stream",
text: "token ".repeat(50),
},
case(
"scalar_extremes",
"the highest scalar value, the replacement character, and a noncharacter, all four-byte or three-byte UTF-8",
"edge \u{10ffff} \u{fffd} \u{fffe} done",
),
case(
"astral_letters",
"mathematical alphanumeric and enclosed astral letters, which are \\p{L} and \\p{N} outside the BMP",
"\u{1d573}\u{1d58a}\u{1d591}\u{1d591}\u{1d594} \
\u{1d7d8}\u{1d7d9}\u{1d7da} \u{1f130}\u{1f131}",
),
case(
"merge_tie_leftmost",
"odd-length runs of one repeated character, where the same pair ties at two overlapping positions and only the LEFTMOST occurrence may merge",
"aaaaa nnn ttt ^^^^^ zzz",
),
case(
"all_special_spellings",
"every special-token spelling of all four gated vocabularies, spaced and then adjacent, none of which encode_ordinary may promote to a special id",
"<|endoftext|> <|fim_prefix|> <|fim_middle|> <|fim_suffix|> <|endofprompt|> \
<|endoftext|><|endofprompt|>",
),
case(
"nul_bytes",
"a leading NUL, an interior NUL run, a NUL fused between letters, and a trailing NUL, the byte a C-string reader stops at",
"\u{0}lead \u{0}\u{0}\u{0} mid\u{0}end trail\u{0}",
),
]
}
#[must_use]
pub fn byte_corpus() -> Vec<ByteCase> {
let case = |name: &'static str, concern: &'static str, pretokens: &[&[u8]]| ByteCase {
name,
concern,
bytes: pretokens.concat(),
pretokens: pretokens.iter().map(|piece| piece.to_vec()).collect(),
};
let mut cases = vec![
case(
"bytes_lone_continuation",
"a continuation byte with no lead byte, the commonest way a truncated buffer arrives",
&[b"ab", b" \x80", b" cd"],
),
case(
"bytes_truncated_two_byte",
"a two-byte lead with its continuation missing, which a length-driven decoder would read past",
&[b"caf", b" \xc3", b" end"],
),
case(
"bytes_invalid_surrogate",
"the CESU-8 spelling of a surrogate, three bytes that each fail independently",
&[b"x", b" \xed\xa0\x80", b" y"],
),
case(
"bytes_surrogate_pair",
"a full CESU-8 surrogate pair, six bytes that a decoder may be tempted to fold back into one astral scalar",
&[b"x", b" \xed\xa0\xbd\xed\xb8\x80", b" y"],
),
case(
"bytes_never_valid_lead",
"0xFF and 0xFE, byte values that are not legal anywhere in UTF-8",
&[b"x", b" \xff\xfe", b" y"],
),
case(
"bytes_overlong",
"an overlong two-byte encoding of '/', the classic path-traversal smuggling shape",
&[b"x", b" \xc0\xaf", b" y"],
),
case(
"bytes_nul_and_continuation",
"NUL bytes flanking an unpaired continuation byte, so a resync that skips to the next lead byte would swallow the NULs too",
&[b"x", b" \x00\x80\x00", b" y"],
),
];
let mut long_run = vec![b' '];
for _ in 0..32 {
long_run.extend_from_slice(b"\xff\xfe");
}
let pretokens = vec![b"x".to_vec(), long_run, b" y".to_vec()];
cases.push(ByteCase {
name: "bytes_long_malformed_run",
concern: "a 65-byte run of never-valid lead bytes in one pretoken, far past any token in any vocabulary",
bytes: pretokens.concat(),
pretokens,
});
let mut over_cap = vec![b' '];
for _ in 0..130 {
over_cap.extend_from_slice(b"\xff\xfe");
}
let pretokens = vec![b"x".to_vec(), over_cap, b" y".to_vec()];
cases.push(ByteCase {
name: "bytes_over_cap_malformed_run",
concern: "a 261-byte single pretoken of never-valid lead bytes, past the device loop's 255-token cap, which prose needs 477 to 6553 bytes to reach",
bytes: pretokens.concat(),
pretokens,
});
cases
}
#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
mod tests {
use super::{
ByteCase, Case, Divergence, IdMismatch, Segment, byte_corpus, corpus, decode_hex,
encode_bytes, encode_segments, first_divergence, first_merge, first_mismatch,
fixture_name, segment_ids, with_rank_replaced, without_pair,
};
use crate::pretokenize::SplitPattern;
use crate::reference::{HostMergeTable, MergeTable};
use crate::vocab::{NAMED_VOCABULARIES, Source, Vocabulary};
use crate::{PairKey, Rank, TokenId, byte_token_ids};
const TINY: &str = "\
YQ== 0
Yg== 1
Yw== 2
YWI= 3
YWJj 4
";
fn tiny() -> Vocabulary {
Vocabulary::load_tiktoken(Source::new("tiny.tiktoken", TINY)).unwrap()
}
fn base64_line(bytes: &[u8]) -> String {
const ALPHABET: &[u8; 64] =
b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
let mut out = String::new();
for chunk in bytes.chunks(3) {
let mut group = [0u8; 3];
group[..chunk.len()].copy_from_slice(chunk);
let packed = (u32::from(group[0]) << 16) | (u32::from(group[1]) << 8) | u32::from(group[2]);
for slot in 0..4 {
if slot <= chunk.len() {
let index = (packed >> (18 - 6 * slot)) & 0x3f;
out.push(char::from(ALPHABET[index as usize]));
} else {
out.push('=');
}
}
}
out
}
#[test]
fn byte_token_ids_rejects_a_vocabulary_missing_a_byte() {
let error = byte_token_ids("tiny.tiktoken", &tiny()).unwrap_err();
let text = error.to_string();
assert!(
text.contains("byte 0x00"),
"the first missing byte must be named, got {text}"
);
assert!(
text.contains("no single-byte token"),
"the detail must say what is missing, got {text}"
);
}
#[test]
fn byte_token_ids_covers_every_byte_value_distinctly() {
let mut text = String::new();
for byte in 0..=u8::MAX {
text.push_str(&format!("{} {byte}\n", base64_line(&[byte])));
}
let vocabulary = Vocabulary::load_tiktoken(Source::new("bytes.tiktoken", &text)).unwrap();
let ids = byte_token_ids("bytes.tiktoken", &vocabulary).unwrap();
for byte in 0..=u8::MAX {
assert_eq!(
ids[byte as usize],
TokenId(u32::from(byte)),
"byte 0x{byte:02x} must map to its own rank"
);
}
}
#[test]
fn first_mismatch_reports_a_truncated_stream() {
let expected = [TokenId(7), TokenId(8), TokenId(9)];
let actual = [TokenId(7), TokenId(8)];
assert_eq!(
first_mismatch(&expected, &actual),
Some(IdMismatch {
index: 2,
expected: Some(TokenId(9)),
actual: None,
})
);
assert_eq!(
first_mismatch(&actual, &expected),
Some(IdMismatch {
index: 2,
expected: None,
actual: Some(TokenId(9)),
})
);
}
#[test]
fn first_mismatch_locates_the_differing_index() {
let expected = [TokenId(1), TokenId(2), TokenId(3)];
assert_eq!(first_mismatch(&expected, &expected), None);
assert_eq!(first_mismatch(&[], &[]), None);
let actual = [TokenId(1), TokenId(2), TokenId(4)];
assert_eq!(
first_mismatch(&expected, &actual),
Some(IdMismatch {
index: 2,
expected: Some(TokenId(3)),
actual: Some(TokenId(4)),
})
);
}
#[test]
fn with_rank_replaced_changes_one_rank_and_nothing_else() {
let vocabulary = tiny();
let table = vocabulary.merge_table();
let pair = PairKey::new(TokenId(0), TokenId(1));
let original = table.lookup(pair).unwrap();
assert_eq!(original.rank, Rank(3), "'ab' has rank 3 in the tiny file");
let corrupted = with_rank_replaced("tiny", table, pair, Rank(0)).unwrap();
assert_eq!(corrupted.len(), table.len(), "no entry may be added or lost");
let changed = corrupted.lookup(pair).unwrap();
assert_eq!(changed.rank, Rank(0), "the target rank must be replaced");
assert_eq!(changed.id, original.id, "the merged id must be untouched");
for (key, entry) in table.iter() {
if key == pair {
continue;
}
assert_eq!(
corrupted.lookup(key),
Some(entry),
"pair ({}, {}) must be unchanged",
key.left().0,
key.right().0
);
}
}
#[test]
fn with_rank_replaced_rejects_a_pair_the_table_lacks() {
let vocabulary = tiny();
let absent = PairKey::new(TokenId(2), TokenId(2));
let error =
with_rank_replaced("tiny", vocabulary.merge_table(), absent, Rank(1)).unwrap_err();
let text = error.to_string();
assert!(
text.contains("pair (2, 2)"),
"the absent pair must be named, got {text}"
);
}
#[test]
fn with_rank_replaced_rejects_the_absent_sentinel() {
let vocabulary = tiny();
let pair = PairKey::new(TokenId(0), TokenId(1));
let error =
with_rank_replaced("tiny", vocabulary.merge_table(), pair, Rank::ABSENT).unwrap_err();
assert!(
error.to_string().contains("ABSENT sentinel"),
"the sentinel must be named, got {error}"
);
}
#[test]
fn without_pair_removes_one_entry_and_changes_the_result() {
let vocabulary = tiny();
let table = vocabulary.merge_table();
let pair = PairKey::new(TokenId(0), TokenId(1));
let reduced = without_pair("tiny", table, pair).unwrap();
assert_eq!(reduced.len(), table.len() - 1, "exactly one entry goes");
assert_eq!(reduced.lookup(pair), None, "the target must be gone");
assert_eq!(
reduced.lookup(PairKey::new(TokenId(3), TokenId(2))),
table.lookup(PairKey::new(TokenId(3), TokenId(2))),
"'ab' + 'c' must survive the removal"
);
let raw = [TokenId(0), TokenId(1), TokenId(2)];
assert_eq!(
crate::reference::encode_pretoken(&raw, table),
vec![TokenId(4)],
"the intact table merges a b c into abc"
);
assert_eq!(
crate::reference::encode_pretoken(&raw, &reduced),
vec![TokenId(0), TokenId(1), TokenId(2)],
"without 'a' + 'b' nothing can merge at all"
);
}
#[test]
fn without_pair_rejects_a_pair_the_table_lacks() {
let vocabulary = tiny();
let error =
without_pair("tiny", vocabulary.merge_table(), PairKey::new(TokenId(2), TokenId(2)))
.unwrap_err();
assert!(
error.to_string().contains("pair (2, 2)"),
"the absent pair must be named, got {error}"
);
}
#[test]
fn first_merge_picks_the_leftmost_lowest_rank() {
let vocabulary = tiny();
let table = vocabulary.merge_table();
assert_eq!(
first_merge(&[TokenId(0), TokenId(1), TokenId(2)], table),
Some(PairKey::new(TokenId(0), TokenId(1)))
);
assert_eq!(
first_merge(&[TokenId(3), TokenId(2)], table),
Some(PairKey::new(TokenId(3), TokenId(2)))
);
assert_eq!(
first_merge(
&[TokenId(3), TokenId(2), TokenId(0), TokenId(1)],
table
),
Some(PairKey::new(TokenId(0), TokenId(1))),
"rank 3 at index 2 must beat rank 4 at index 0"
);
assert_eq!(first_merge(&[TokenId(1), TokenId(2)], table), None);
assert_eq!(first_merge(&[TokenId(0)], table), None);
assert_eq!(first_merge(&[], table), None);
}
#[test]
fn decode_hex_round_trips_every_byte_and_names_bad_input() {
let all: String = (0..=u8::MAX).map(|byte| format!("{byte:02x}")).collect();
let decoded = decode_hex("fixture", &all).unwrap();
assert_eq!(decoded, (0..=u8::MAX).collect::<Vec<u8>>());
assert_eq!(decode_hex("fixture", "").unwrap(), Vec::<u8>::new());
assert_eq!(decode_hex("fixture", "20c0af").unwrap(), b" \xc0\xaf");
let odd = decode_hex("fixture", "abc").unwrap_err().to_string();
assert!(odd.contains("length 3"), "got {odd}");
let upper = decode_hex("fixture", "0A").unwrap_err().to_string();
assert!(upper.contains("character 1"), "got {upper}");
let bad = decode_hex("fixture", "0g").unwrap_err().to_string();
assert!(bad.contains("'g'"), "got {bad}");
}
#[test]
fn corpus_names_are_unique_and_documented() {
let cases: Vec<Case> = corpus();
assert_eq!(cases.len(), 42, "the corpus size is pinned to the fixture");
let mut names: Vec<&str> = cases.iter().map(|case| case.name).collect();
names.sort_unstable();
let count = names.len();
names.dedup();
assert_eq!(names.len(), count, "case names must be unique");
for case in &cases {
assert!(
case.concern.len() > 30,
"{} needs a concern that names what it catches",
case.name
);
}
}
#[test]
fn corpus_pins_the_long_case_lengths() {
let cases = corpus();
let find = |name: &str| -> &Case {
cases
.iter()
.find(|case| case.name == name)
.unwrap_or_else(|| panic!("{name} must be in the corpus"))
};
assert_eq!(find("long_letter_run").text.len(), 500);
assert_eq!(find("long_alternating_run").text.len(), 500);
assert_eq!(find("long_digit_wall").text.len(), 500);
assert_eq!(find("long_space_run").text.len(), 72);
assert_eq!(find("long_digit_run").text.len(), 50);
assert_eq!(find("repeated_word").text.len(), 300);
assert_eq!(find("empty").text.len(), 0);
assert_eq!(find("single_space").text, " ");
assert_eq!(find("newlines_only").text, "\n\n\n\n\n");
}
#[test]
fn byte_corpus_is_malformed_and_reassembles() {
let cases: Vec<ByteCase> = byte_corpus();
assert_eq!(cases.len(), 9, "the byte corpus size is pinned to the fixture");
for case in &cases {
assert_eq!(
case.pretokens.concat(),
case.bytes,
"{} pretokens must reassemble the input",
case.name
);
assert!(
std::str::from_utf8(&case.bytes).is_err(),
"{} must be invalid UTF-8 or it belongs in the ordinary corpus",
case.name
);
}
assert_eq!(cases[0].bytes, b"ab \x80 cd");
assert_eq!(cases[5].bytes, b"x \xc0\xaf y");
assert_eq!(cases[7].bytes.len(), 68, "the long malformed run is 68 bytes");
assert_eq!(
cases[8].pretokens[1].len(),
261,
"the over-cap pretoken must stay past the device loop's 255-token cap"
);
}
#[test]
fn every_named_vocabulary_maps_to_a_distinct_fixture() {
let mut fixtures: Vec<String> = NAMED_VOCABULARIES
.iter()
.map(|vocabulary| fixture_name(vocabulary.name))
.collect();
fixtures.sort();
assert_eq!(
fixtures,
vec![
"parity_cl100k_base.json",
"parity_o200k_base.json",
"parity_p50k_base.json",
"parity_r50k_base.json",
]
);
}
#[test]
fn rebuilding_from_iter_is_the_identity() {
let vocabulary = tiny();
let table = vocabulary.merge_table();
let rebuilt = HostMergeTable::from_entries(
"tiny",
table.iter().map(|(key, entry)| (key, entry.id, entry.rank)),
)
.unwrap();
assert_eq!(&rebuilt, table);
}
fn segment_vocabulary() -> Vocabulary {
let mut text = String::new();
for byte in 0..=u8::MAX {
text.push_str(&format!("{} {byte}\n", base64_line(&[byte])));
}
text.push_str(&format!("{} 256\n", base64_line(b"ab")));
text.push_str(&format!("{} 257\n", base64_line(b" c")));
text.push_str(&format!("{} 258\n", base64_line(b" cd")));
Vocabulary::load_tiktoken(Source::new("segments.tiktoken", &text)).unwrap()
}
#[test]
fn encode_segments_records_offsets_bytes_and_ids() {
let vocabulary = segment_vocabulary();
let bytes = byte_token_ids("segments.tiktoken", &vocabulary).unwrap();
let table = vocabulary.merge_table();
let segments = encode_segments(SplitPattern::Gpt2, b"ab cd", &bytes, table);
assert_eq!(
segments,
vec![
Segment {
offset: 0,
bytes: b"ab".to_vec(),
ids: vec![TokenId(256)],
},
Segment {
offset: 2,
bytes: b" cd".to_vec(),
ids: vec![TokenId(258)],
},
]
);
assert_eq!(
segment_ids(&segments),
encode_bytes(SplitPattern::Gpt2, b"ab cd", &bytes, table),
"the located path and the flat path must agree id for id"
);
}
#[test]
fn first_divergence_locates_the_pretoken_and_byte_offset() {
let vocabulary = segment_vocabulary();
let bytes = byte_token_ids("segments.tiktoken", &vocabulary).unwrap();
let segments = encode_segments(SplitPattern::Gpt2, b"ab cd", &bytes, vocabulary.merge_table());
let planted = [TokenId(256), TokenId(99)];
assert_eq!(
first_divergence(&planted, &segments),
Some(Divergence {
index: 1,
expected: Some(TokenId(99)),
actual: Some(TokenId(258)),
pretoken_index: 1,
byte_offset: 2,
pretoken: b" cd".to_vec(),
index_in_pretoken: 0,
})
);
assert_eq!(
first_divergence(&[TokenId(256), TokenId(258)], &segments),
None,
"equal streams must not report a divergence"
);
}
#[test]
fn first_divergence_reports_a_stream_that_ended_early() {
let vocabulary = segment_vocabulary();
let bytes = byte_token_ids("segments.tiktoken", &vocabulary).unwrap();
let segments = encode_segments(SplitPattern::Gpt2, b"ab cd", &bytes, vocabulary.merge_table());
let longer = [TokenId(256), TokenId(258), TokenId(7)];
assert_eq!(
first_divergence(&longer, &segments),
Some(Divergence {
index: 2,
expected: Some(TokenId(7)),
actual: None,
pretoken_index: 1,
byte_offset: 2,
pretoken: b" cd".to_vec(),
index_in_pretoken: 1,
})
);
assert_eq!(
first_divergence(&[TokenId(9)], &[]),
Some(Divergence {
index: 0,
expected: Some(TokenId(9)),
actual: None,
pretoken_index: 0,
byte_offset: 0,
pretoken: Vec::new(),
index_in_pretoken: 0,
}),
"empty input still has to report the reference's first id"
);
}
#[test]
fn divergence_display_states_offset_pretoken_and_both_ids() {
let report = Divergence {
index: 137,
expected: Some(TokenId(9857)),
actual: Some(TokenId(1234)),
pretoken_index: 42,
byte_offset: 613,
pretoken: b" \x80\"a".to_vec(),
index_in_pretoken: 3,
}
.to_string();
assert_eq!(
report,
"id 137 differs: reference 9857, exatok 1234; byte offset 613, pretoken 42 \
\" \\x80\\\"a\", id 3 of that pretoken"
);
let ended = Divergence {
index: 2,
expected: Some(TokenId(7)),
actual: None,
pretoken_index: 1,
byte_offset: 2,
pretoken: b" cd".to_vec(),
index_in_pretoken: 1,
}
.to_string();
assert!(
ended.contains("exatok <stream ended>"),
"a missing id must read as an ended stream, got {ended}"
);
}
#[test]
fn every_shipping_special_spelling_is_in_the_corpus() {
let cases = corpus();
let carrier = cases
.iter()
.find(|case| case.name == "all_special_spellings")
.expect("the corpus must carry the special spellings case");
let mut spellings = 0usize;
for vocabulary in NAMED_VOCABULARIES {
let specials = crate::specials::specials_for(vocabulary.name)
.unwrap_or_else(|| panic!("{} has no specials entry", vocabulary.name));
assert!(
!specials.tokens.is_empty(),
"{} must declare its special tokens",
vocabulary.name
);
for (spelling, reserved) in specials.tokens {
assert!(
carrier.text.contains(spelling),
"{} registers {spelling}, which {} does not carry",
vocabulary.name,
carrier.name
);
assert!(
*reserved > 0,
"{} reserves id 0 for {spelling}, which is a single-byte token",
vocabulary.name
);
spellings += 1;
}
}
assert_eq!(
spellings, 9,
"the four vocabularies register 9 spellings in total: 5, 1, 1, 2"
);
}
#[test]
fn corpus_tie_case_uses_odd_length_repeated_runs() {
let cases = corpus();
let tie = cases
.iter()
.find(|case| case.name == "merge_tie_leftmost")
.expect("the corpus must carry the tie case");
let runs: Vec<&str> = tie.text.split(' ').collect();
assert_eq!(runs.len(), 5, "the tie case holds five runs: {runs:?}");
for run in runs {
let first = run.as_bytes()[0];
assert!(
run.len() % 2 == 1 && run.len() >= 3,
"{run:?} must be an odd run of at least 3 for the tie to overlap"
);
assert!(
run.bytes().all(|byte| byte == first),
"{run:?} must repeat one character, or the tying pair is not the same pair"
);
}
}
#[test]
fn corpus_nul_case_covers_every_nul_position() {
let cases = corpus();
let nul = cases
.iter()
.find(|case| case.name == "nul_bytes")
.expect("the corpus must carry the NUL case");
let raw = nul.text.as_bytes();
assert_eq!(raw.first(), Some(&0), "a NUL must lead the input");
assert_eq!(raw.last(), Some(&0), "a NUL must end the input");
assert_eq!(
raw.iter().filter(|&&byte| byte == 0).count(),
6,
"the case pins six NULs: leading, a run of three, one fused, one trailing"
);
assert!(
raw.windows(3).any(|window| window == [0, 0, 0]),
"an interior run of three NULs must survive"
);
}
}