mod unicode_class;
use crate::ExatokError;
use unicode_class::{L, LL, LM_LO, LU_LT, M, N, WS, ascii_class, class_of};
const O200K_LEADING: u8 = LU_LT | LM_LO | M;
const O200K_TRAILING: u8 = LL | LM_LO | M;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum SplitPattern {
Gpt2,
Cl100kBase,
O200kBase,
}
impl SplitPattern {
pub const ALL: [Self; 3] = [Self::Gpt2, Self::Cl100kBase, Self::O200kBase];
#[must_use]
pub const fn name(self) -> &'static str {
match self {
Self::Gpt2 => "gpt2",
Self::Cl100kBase => "cl100k_base",
Self::O200kBase => "o200k_base",
}
}
#[must_use]
pub const fn pattern(self) -> &'static str {
match self {
Self::Gpt2 => {
r"'(?:[sdmt]|ll|ve|re)| ?\p{L}++| ?\p{N}++| ?[^\s\p{L}\p{N}]++|\s++$|\s+(?!\S)|\s"
}
Self::Cl100kBase => {
r"'(?i:[sdmt]|ll|ve|re)|[^\r\n\p{L}\p{N}]?+\p{L}++|\p{N}{1,3}+| ?[^\s\p{L}\p{N}]++[\r\n]*+|\s++$|\s*[\r\n]|\s+(?!\S)|\s"
}
Self::O200kBase => {
concat!(
r"[^\r\n\p{L}\p{N}]?[\p{Lu}\p{Lt}\p{Lm}\p{Lo}\p{M}]*[\p{Ll}\p{Lm}\p{Lo}\p{M}]+(?i:'s|'t|'re|'ve|'m|'ll|'d)?",
r"|[^\r\n\p{L}\p{N}]?[\p{Lu}\p{Lt}\p{Lm}\p{Lo}\p{M}]+[\p{Ll}\p{Lm}\p{Lo}\p{M}]*(?i:'s|'t|'re|'ve|'m|'ll|'d)?",
r"|\p{N}{1,3}",
r"| ?[^\s\p{L}\p{N}]+[\r\n/]*",
r"|\s*[\r\n]+",
r"|\s+(?!\S)",
r"|\s+",
)
}
}
}
#[must_use]
pub const fn digit_run_cap(self) -> Option<usize> {
match self {
Self::Gpt2 => None,
Self::Cl100kBase | Self::O200kBase => Some(3),
}
}
}
#[must_use]
pub const fn unicode_version() -> &'static str {
unicode_class::UNICODE_VERSION
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Span {
pub start: usize,
pub end: usize,
}
impl Span {
#[must_use]
pub const fn len(self) -> usize {
self.end - self.start
}
#[must_use]
pub const fn is_empty(self) -> bool {
self.start == self.end
}
#[must_use]
pub fn bytes<'input>(self, input: &'input [u8]) -> Option<&'input [u8]> {
input.get(self.start..self.end)
}
}
#[derive(Debug, Clone)]
pub struct Pretokens<'input> {
cursor: Cursor<'input>,
pattern: SplitPattern,
at: usize,
}
impl Iterator for Pretokens<'_> {
type Item = Span;
fn next(&mut self) -> Option<Span> {
if self.at >= self.cursor.input.len() {
return None;
}
let start = self.at;
let end = match self.pattern {
SplitPattern::Gpt2 => self.cursor.gpt2_end(start),
SplitPattern::Cl100kBase => self.cursor.cl100k_end(start),
SplitPattern::O200kBase => self.cursor.o200k_end(start),
};
self.at = end;
Some(Span { start, end })
}
}
#[must_use]
pub const fn pretokens(pattern: SplitPattern, input: &[u8]) -> Pretokens<'_> {
Pretokens {
cursor: Cursor { input },
pattern,
at: 0,
}
}
pub fn pretokenize(pattern: SplitPattern, input: &[u8], out: &mut Vec<Span>) {
out.extend(pretokens(pattern, input));
}
#[must_use]
pub fn spans(pattern: SplitPattern, input: &[u8]) -> Vec<Span> {
pretokens(pattern, input).collect()
}
pub fn segment_starts(
pattern: SplitPattern,
input: &[u8],
out: &mut Vec<u32>,
) -> Result<(), ExatokError> {
let total = checked_total(input.len())?;
for span in pretokens(pattern, input) {
out.push(span.start as u32);
}
out.push(total);
Ok(())
}
fn checked_total(len: usize) -> Result<u32, ExatokError> {
u32::try_from(len).map_err(|_| {
ExatokError::Backend(format!(
"input is {} bytes, past the u32 addressing limit of {} for a device \
segment-start buffer. Fix: shard the input below 4 GiB per dispatch.",
len,
u32::MAX
))
})
}
#[derive(Debug, Clone, Copy)]
struct Unit {
len: usize,
class: u8,
}
const END: Unit = Unit { len: 0, class: 0 };
const MALFORMED: Unit = Unit { len: 1, class: 0 };
const fn is(unit: Unit, bits: u8) -> bool {
unit.len != 0 && unit.class & bits != 0
}
const fn is_not(unit: Unit, bits: u8) -> bool {
unit.len != 0 && unit.class & bits == 0
}
#[derive(Debug, Clone, Copy)]
struct WhitespaceRun {
end: usize,
last: usize,
through_break: Option<usize>,
}
#[derive(Debug, Clone)]
struct Cursor<'input> {
input: &'input [u8],
}
impl Cursor<'_> {
#[inline]
fn unit(&self, at: usize) -> Unit {
match self.input.get(at) {
None => END,
Some(&lead) if lead < 0x80 => Unit { len: 1, class: ascii_class(lead) },
Some(_) => self.multibyte_unit(at),
}
}
#[inline(never)]
fn multibyte_unit(&self, at: usize) -> Unit {
let Some(rest) = self.input.get(at..) else {
return END;
};
let Some(&lead) = rest.first() else {
return END;
};
let (len, low, high, mut scalar) = match lead {
0xC2..=0xDF => (2, 0x80, 0xBF, u32::from(lead & 0x1F)),
0xE0 => (3, 0xA0, 0xBF, u32::from(lead & 0x0F)),
0xE1..=0xEC => (3, 0x80, 0xBF, u32::from(lead & 0x0F)),
0xED => (3, 0x80, 0x9F, u32::from(lead & 0x0F)),
0xEE..=0xEF => (3, 0x80, 0xBF, u32::from(lead & 0x0F)),
0xF0 => (4, 0x90, 0xBF, u32::from(lead & 0x07)),
0xF1..=0xF3 => (4, 0x80, 0xBF, u32::from(lead & 0x07)),
0xF4 => (4, 0x80, 0x8F, u32::from(lead & 0x07)),
_ => return MALFORMED,
};
let Some(sequence) = rest.get(..len) else {
return MALFORMED;
};
if sequence[1] < low || sequence[1] > high {
return MALFORMED;
}
scalar = (scalar << 6) | u32::from(sequence[1] & 0x3F);
for &byte in &sequence[2..] {
if byte & 0xC0 != 0x80 {
return MALFORMED;
}
scalar = (scalar << 6) | u32::from(byte & 0x3F);
}
Unit {
len,
class: class_of(scalar),
}
}
fn run_end(&self, at: usize, bits: u8) -> usize {
let mut pos = at;
loop {
let unit = self.unit(pos);
if !is(unit, bits) {
return pos;
}
pos += unit.len;
}
}
fn other_run_end(&self, at: usize) -> usize {
let mut pos = at;
loop {
let unit = self.unit(pos);
if !is_not(unit, WS | L | N) {
return pos;
}
pos += unit.len;
}
}
fn byte_run_end(&self, at: usize, set: &[u8]) -> usize {
let mut pos = at;
while self.input.get(pos).is_some_and(|byte| set.contains(byte)) {
pos += 1;
}
pos
}
fn letter_len(&self, at: usize, letter: u8, fold: bool) -> Option<usize> {
match self.input.get(at) {
Some(&byte) if byte == letter => Some(1),
Some(&byte) if fold && byte | 0x20 == letter => Some(1),
Some(&0xC5) if fold && letter == b's' && self.input.get(at + 1) == Some(&0xBF) => {
Some(2)
}
_ => None,
}
}
#[inline]
fn contraction_end(&self, at: usize, fold: bool) -> Option<usize> {
if self.input.get(at) != Some(&b'\'') {
return None;
}
self.contraction_tail(at, fold)
}
fn contraction_tail(&self, at: usize, fold: bool) -> Option<usize> {
for letter in [b's', b'd', b'm', b't'] {
if let Some(len) = self.letter_len(at + 1, letter, fold) {
return Some(at + 1 + len);
}
}
for [first, second] in [[b'l', b'l'], [b'v', b'e'], [b'r', b'e']] {
if let Some(head) = self.letter_len(at + 1, first, fold) {
if let Some(tail) = self.letter_len(at + 1 + head, second, fold) {
return Some(at + 1 + head + tail);
}
}
}
None
}
fn punctuation_end(&self, at: usize, head: Unit, after: Unit, tail: &[u8]) -> Option<usize> {
let (start, first) =
if self.input.get(at) == Some(&b' ') { (at + 1, after) } else { (at, head) };
if !is_not(first, WS | L | N) {
return None;
}
Some(self.byte_run_end(self.other_run_end(start + first.len), tail))
}
fn whitespace_run(&self, at: usize, head: Unit, second: Option<Unit>) -> WhitespaceRun {
let mut pos = at;
let mut unit = head;
let mut second = second;
let mut last = at;
let mut through_break = None;
while is(unit, WS) {
if matches!(self.input.get(pos), Some(&b'\r' | &b'\n')) {
through_break = Some(pos + 1);
}
last = pos;
pos += unit.len;
unit = second.take().unwrap_or_else(|| self.unit(pos));
}
WhitespaceRun { end: pos, last, through_break }
}
const fn ws_giveback_or_one(run: WhitespaceRun, at: usize) -> usize {
if run.last == at { run.end } else { run.last }
}
fn gpt2_end(&self, at: usize) -> usize {
let head = self.unit(at);
if is(head, L) {
return self.run_end(at + head.len, L);
}
if is(head, N) {
return self.run_end(at + head.len, N);
}
if is_not(head, WS) {
return self
.contraction_end(at, false)
.unwrap_or_else(|| self.other_run_end(at + head.len));
}
let mut after = None;
if self.input.get(at) == Some(&b' ') {
let next = self.unit(at + 1);
after = Some(next);
if is(next, L) {
return self.run_end(at + 1 + next.len, L);
}
if is(next, N) {
return self.run_end(at + 1 + next.len, N);
}
if is_not(next, WS) {
return self.other_run_end(at + 1 + next.len);
}
}
let run = self.whitespace_run(at, head, after);
if run.end == self.input.len() {
return run.end;
}
Self::ws_giveback_or_one(run, at)
}
fn cl100k_end(&self, at: usize) -> usize {
let head = self.unit(at);
if is(head, L) {
return self.run_end(at + head.len, L);
}
if is(head, N) {
return self.run_end_capped(at, head, 3);
}
if matches!(self.input.get(at), Some(&b'\r' | &b'\n')) {
let run = self.whitespace_run(at, head, None);
if run.end == self.input.len() {
return run.end;
}
if let Some(end) = run.through_break {
return end;
}
return Self::ws_giveback_or_one(run, at);
}
let after = self.unit(at + head.len);
if is_not(head, WS) {
if let Some(end) = self.contraction_end(at, true) {
return end;
}
if is(after, L) {
return self.run_end(at + head.len + after.len, L);
}
return self.byte_run_end(self.other_run_end(at + head.len), b"\r\n");
}
if is(after, L) {
return self.run_end(at + head.len + after.len, L);
}
if let Some(end) = self.punctuation_end(at, head, after, b"\r\n") {
return end;
}
let run = self.whitespace_run(at, head, Some(after));
if run.end == self.input.len() {
return run.end;
}
if let Some(end) = run.through_break {
return end;
}
Self::ws_giveback_or_one(run, at)
}
fn run_end_capped(&self, at: usize, head: Unit, cap: usize) -> usize {
let mut pos = at + head.len;
let mut taken = 1;
while taken < cap {
let unit = self.unit(pos);
if !is(unit, N) {
break;
}
pos += unit.len;
taken += 1;
}
pos
}
fn o200k_lower_tail(&self, start: usize, first: Unit) -> Option<usize> {
let mut pos = start;
let mut unit = first;
let mut split = None;
loop {
if is(unit, O200K_TRAILING) {
split = Some(pos);
}
if !is(unit, O200K_LEADING) {
break;
}
pos += unit.len;
unit = self.unit(pos);
}
let split = split?;
let run_from =
if split == pos { pos + unit.len } else { split };
let end = self.run_end(run_from, O200K_TRAILING);
Some(self.contraction_end(end, true).unwrap_or(end))
}
fn o200k_upper_tail(&self, start: usize, first: Unit) -> Option<usize> {
if !is(first, O200K_LEADING) {
return None;
}
let leading_end = self.run_end(start + first.len, O200K_LEADING);
let end = self.run_end(leading_end, O200K_TRAILING);
Some(self.contraction_end(end, true).unwrap_or(end))
}
fn o200k_end(&self, at: usize) -> usize {
let head = self.unit(at);
let led =
is_not(head, L | N) && !matches!(self.input.get(at), Some(&b'\r' | &b'\n'));
let after = if led { self.unit(at + head.len) } else { END };
if led {
if let Some(end) = self.o200k_lower_tail(at + head.len, after) {
return end;
}
}
if let Some(end) = self.o200k_lower_tail(at, head) {
return end;
}
if led {
if let Some(end) = self.o200k_upper_tail(at + head.len, after) {
return end;
}
}
if let Some(end) = self.o200k_upper_tail(at, head) {
return end;
}
if is(head, N) {
return self.run_end_capped(at, head, 3);
}
if let Some(end) = self.punctuation_end(at, head, after, b"\r\n/") {
return end;
}
let run = self.whitespace_run(at, head, if led { Some(after) } else { None });
if let Some(end) = run.through_break {
return end;
}
if run.end == self.input.len() {
return run.end;
}
Self::ws_giveback_or_one(run, at)
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use super::*;
#[test]
fn decoder_rejects_overlongs_surrogates_and_out_of_range() {
let cursor = Cursor { input: b"" };
for (bytes, want_len, what) in [
(&[0x41][..], 1, "ascii"),
(&[0xC3, 0xA9][..], 2, "U+00E9"),
(&[0xE2, 0x82, 0xAC][..], 3, "U+20AC"),
(&[0xF0, 0x9F, 0x98, 0x80][..], 4, "U+1F600"),
(&[0xC0, 0xAF][..], 1, "overlong slash"),
(&[0xC1, 0xBF][..], 1, "overlong 0x7F"),
(&[0xE0, 0x80, 0xAF][..], 1, "overlong 3-byte"),
(&[0xF0, 0x80, 0x80, 0xAF][..], 1, "overlong 4-byte"),
(&[0xED, 0xA0, 0x80][..], 1, "surrogate U+D800"),
(&[0xED, 0xBF, 0xBF][..], 1, "surrogate U+DFFF"),
(&[0xF4, 0x90, 0x80, 0x80][..], 1, "above U+10FFFF"),
(&[0xF5, 0x80, 0x80, 0x80][..], 1, "lead 0xF5"),
(&[0xFF][..], 1, "lead 0xFF"),
(&[0x80][..], 1, "bare continuation"),
(&[0xE2, 0x82][..], 1, "truncated 3-byte"),
] {
let cursor = Cursor { input: bytes };
assert_eq!(
cursor.unit(0).len,
want_len,
"{what}: unit length for {bytes:02x?}"
);
}
assert_eq!(cursor.unit(0).len, 0, "end of input yields a zero-length unit");
}
#[test]
fn whitespace_letter_and_number_classes_are_disjoint() {
let mut buffer = [0u8; 4];
for scalar in (0u32..0x11_0000).filter(|cp| !(0xD800..0xE000).contains(cp)) {
let class = class_of(scalar);
let hits = u32::from(class & WS != 0) + u32::from(class & L != 0) + u32::from(class & N != 0);
assert!(
hits <= 1,
"U+{scalar:04X} is in {hits} of whitespace/letter/number (class {class:#b})"
);
let Some(ch) = char::from_u32(scalar) else {
continue;
};
let encoded = ch.encode_utf8(&mut buffer).as_bytes();
let cursor = Cursor { input: encoded };
for pattern in SplitPattern::ALL {
let end = match pattern {
SplitPattern::Gpt2 => cursor.gpt2_end(0),
SplitPattern::Cl100kBase => cursor.cl100k_end(0),
SplitPattern::O200kBase => cursor.o200k_end(0),
};
assert_eq!(
end,
encoded.len(),
"U+{scalar:04X} alone must be one whole pretoken under {}",
pattern.name()
);
}
}
}
#[test]
fn letter_bit_is_the_union_of_letter_subcategories() {
for scalar in (0u32..0x11_0000).filter(|cp| !(0xD800..0xE000).contains(cp)) {
let class = class_of(scalar);
assert_eq!(
class & L != 0,
class & (LU_LT | LL | LM_LO) != 0,
"U+{scalar:04X} disagrees on letterhood (class {class:#b})"
);
if class & M != 0 {
assert_eq!(class & L, 0, "U+{scalar:04X} is both a mark and a letter");
}
}
}
#[test]
fn checked_total_rejects_lengths_past_the_u32_addressing_limit() {
assert_eq!(checked_total(0).unwrap(), 0, "an empty input addresses fine");
assert_eq!(
checked_total(u32::MAX as usize).unwrap(),
u32::MAX,
"the largest addressable length is accepted, not rejected"
);
match checked_total(u32::MAX as usize + 1) {
Err(ExatokError::Backend(message)) => assert_eq!(
message,
"input is 4294967296 bytes, past the u32 addressing limit of \
4294967295 for a device segment-start buffer. Fix: shard the \
input below 4 GiB per dispatch."
),
other => panic!("expected a Backend error, got {other:?}"),
}
}
fn ends(pattern: SplitPattern, input: &[u8]) -> Vec<(usize, usize)> {
spans(pattern, input).into_iter().map(|s| (s.start, s.end)).collect()
}
fn boundary_cases() -> Vec<(SplitPattern, Vec<u8>, Vec<(usize, usize)>, &'static str)> {
let long_run: Vec<u8> = {
let mut v = vec![b' '; 64];
v.push(b'x');
v
};
vec![
(SplitPattern::Cl100kBase, b"a\xE6\xBC".to_vec(), vec![(0, 1), (1, 3)],
"multi-byte sequence split across the end of input"),
(SplitPattern::Cl100kBase, b"\xED\xA0\x80a".to_vec(), vec![(0, 3), (3, 4)],
"lone surrogate-shaped byte sequence"),
(SplitPattern::Cl100kBase, "漢字漢。".as_bytes().to_vec(), vec![(0, 9), (9, 12)],
"CJK run followed by CJK punctuation"),
(SplitPattern::Cl100kBase, long_run, vec![(0, 63), (63, 65)],
"very long whitespace run before a word"),
(SplitPattern::Cl100kBase, vec![b' '; 64], vec![(0, 64)],
"very long whitespace run at end of input"),
(SplitPattern::O200kBase, vec![b' '; 64], vec![(0, 64)],
"o200k reaches the same end without a dollar alternative"),
(SplitPattern::Cl100kBase, b"a \r\n b".to_vec(),
vec![(0, 1), (1, 4), (4, 6)], "whitespace run through its last line break"),
(SplitPattern::Cl100kBase, b"12345".to_vec(), vec![(0, 3), (3, 5)],
"input ending mid-class inside a capped digit run"),
(SplitPattern::Gpt2, b"12345".to_vec(), vec![(0, 5)],
"uncapped digit run ends at the input"),
(SplitPattern::Cl100kBase, b" !".to_vec(), vec![(0, 2)],
"a space leads the punctuation alternative"),
(SplitPattern::Cl100kBase, b"\t!".to_vec(), vec![(0, 1), (1, 2)],
"a tab does not lead the punctuation alternative"),
(SplitPattern::Cl100kBase, b"!ab".to_vec(), vec![(0, 3)],
"class-zero lead followed by letters"),
(SplitPattern::O200kBase, "\u{301}".as_bytes().to_vec(), vec![(0, 2)],
"o200k retries its lead for a lone combining mark"),
(SplitPattern::O200kBase, "\u{301}a".as_bytes().to_vec(), vec![(0, 3)],
"o200k spends its lead on a mark before a letter"),
]
}
#[test]
fn boundary_cases_split_to_exact_span_vectors() {
for (pattern, input, want, why) in boundary_cases() {
assert_eq!(
ends(pattern, &input),
want,
"{}: {why} for {input:02x?}",
pattern.name()
);
}
}
#[test]
fn spans_tile_every_boundary_case_under_every_pattern() {
let mut inputs: Vec<Vec<u8>> = boundary_cases().into_iter().map(|c| c.1).collect();
inputs.push(vec![b'\n'; 300]);
inputs.push(vec![b'\t'; 300]);
inputs.push("\u{a0}".repeat(300).into_bytes());
inputs.push("漢".repeat(300).into_bytes());
inputs.push(b"\r\n".repeat(150).to_vec());
inputs.push((0u8..=255).collect());
for input in &inputs {
for pattern in SplitPattern::ALL {
let got = spans(pattern, input);
let mut at = 0;
for span in &got {
assert_eq!(span.start, at, "{}: gap before {span:?}", pattern.name());
assert!(span.end > span.start, "{}: empty {span:?}", pattern.name());
at = span.end;
}
assert_eq!(
at,
input.len(),
"{}: spans stop short of the input",
pattern.name()
);
}
}
}
}