use memchr::{memchr_iter, memmem};
use serde::Deserialize;
use serde_json::Value;
use crate::pre_tokenized::{PreTokenizedString, Split as PtSplit};
use super::{Error, scanner::PatternId};
#[derive(Clone, Debug, Deserialize)]
pub enum Pattern {
String(std::string::String),
Regex(std::string::String),
}
#[derive(Clone, Debug)]
enum Matcher {
Literal(Box<str>),
Fixed(PatternId),
}
impl Matcher {
fn from_pattern(pattern: Pattern) -> Result<Self, Error> {
match pattern {
Pattern::String(literal) => Ok(Self::Literal(literal.into_boxed_str())),
Pattern::Regex(source) => PatternId::from_source(&source)
.map(Self::Fixed)
.ok_or_else(|| Error::Unsupported(format!("Split regex pattern: {source}"))),
}
}
fn for_each_match(&self, input: &str, mut emit: impl FnMut(usize, usize)) {
match self {
Self::Fixed(pattern) => pattern.for_each_match(input, emit),
Self::Literal(literal) => {
let needle = literal.as_bytes();
if needle.is_empty() {
return;
}
if needle.len() == 1 {
for start in memchr_iter(needle[0], input.as_bytes()) {
emit(start, start + 1);
}
return;
}
for start in memmem::find_iter(input.as_bytes(), needle) {
emit(start, start + needle.len());
}
}
}
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Deserialize)]
pub enum SplitBehavior {
Removed,
#[default]
Isolated,
MergedWithPrevious,
MergedWithNext,
Contiguous,
}
#[derive(Deserialize)]
struct SplitRaw {
pattern: Pattern,
#[serde(default)]
behavior: SplitBehavior,
#[serde(default)]
invert: bool,
}
#[derive(Clone, Debug, Deserialize)]
#[serde(try_from = "SplitRaw")]
pub struct Split {
matcher: Matcher,
behavior: SplitBehavior,
invert: bool,
}
impl TryFrom<SplitRaw> for Split {
type Error = Error;
fn try_from(raw: SplitRaw) -> Result<Self, Error> {
Self::from_parts(raw.pattern, raw.behavior, raw.invert)
}
}
impl Split {
fn from_parts(pattern: Pattern, behavior: SplitBehavior, invert: bool) -> Result<Self, Error> {
Ok(Self {
matcher: Matcher::from_pattern(pattern)?,
behavior,
invert,
})
}
pub fn from_config(pattern: &Value, behavior: &str, invert: bool) -> Result<Self, Error> {
let pattern = serde_json::from_value(pattern.clone())?;
let behavior = serde_json::from_value(Value::String(behavior.to_string()))?;
Self::from_parts(pattern, behavior, invert)
}
pub(crate) fn supports_ascii_nfc_fusion(&self) -> bool {
self.behavior == SplitBehavior::Isolated
&& !self.invert
&& matches!(
self.matcher,
Matcher::Fixed(PatternId::Qwen | PatternId::QwenMark)
)
}
pub(crate) fn supports_fused_stream(&self) -> bool {
if !self.invert {
return self.behavior == SplitBehavior::Isolated
|| (self.behavior == SplitBehavior::MergedWithPrevious
&& matches!(self.matcher, Matcher::Fixed(PatternId::Kimi)));
}
self.behavior == SplitBehavior::Removed
&& matches!(
self.matcher,
Matcher::Fixed(PatternId::Llama | PatternId::LlamaContraction)
)
}
pub(crate) fn pattern_id(&self) -> Option<PatternId> {
match &self.matcher {
Matcher::Fixed(pattern) => Some(*pattern),
Matcher::Literal(_) => None,
}
}
pub(crate) fn for_each_fused_piece(
&self,
input: &str,
mut emit: impl FnMut(&str, usize, usize),
) {
debug_assert!(self.supports_fused_stream());
let must_cover_input = self.behavior != SplitBehavior::Isolated || self.invert;
let mut previous = 0;
self.matcher.for_each_match(input, |start, end| {
debug_assert!(!must_cover_input || start == previous);
if start > previous {
emit(input, previous, start);
}
emit(input, start, end);
previous = end;
});
debug_assert!(!must_cover_input || previous == input.len());
if previous < input.len() {
emit(input, previous, input.len());
}
}
pub fn pre_tokenize(&self, pts: &mut PreTokenizedString) -> Result<(), Error> {
if self.behavior == SplitBehavior::Isolated && !self.invert {
self.pre_tokenize_isolated(pts);
return Ok(());
}
if self.behavior == SplitBehavior::Removed && self.invert {
self.pre_tokenize_removed_inverted(pts);
return Ok(());
}
let mut new_splits = Vec::with_capacity(pts.splits().len().saturating_mul(2));
for split in pts.splits() {
if split.token_id.is_some() {
new_splits.push(split.clone());
continue;
}
let text = pts.split_text(split);
if text.is_empty() {
continue;
}
let base = split.range.start;
let segments = self.find_segments(text);
let ranges = self.apply_behavior(&segments);
for (start, end) in ranges {
if start < end {
new_splits.push(PtSplit {
range: (base + start)..(base + end),
token_id: None,
});
}
}
}
pts.refine_splits(new_splits);
Ok(())
}
pub(crate) fn append_ascii_splits(
&self,
input: &str,
base: usize,
output: &mut Vec<PtSplit>,
) -> bool {
debug_assert!(self.supports_ascii_nfc_fusion());
if input.is_empty() {
return true;
}
let Matcher::Fixed(pattern) = &self.matcher else {
unreachable!("eligible ASCII fusion requires a fixed scanner");
};
let mut previous = 0;
let complete = pattern.for_each_ascii_match(input, |start, end| {
if start > previous {
output.push(PtSplit {
range: (base + previous)..(base + start),
token_id: None,
});
}
output.push(PtSplit {
range: (base + start)..(base + end),
token_id: None,
});
previous = end;
});
if !complete {
return false;
}
if previous < input.len() {
output.push(PtSplit {
range: (base + previous)..(base + input.len()),
token_id: None,
});
}
true
}
fn pre_tokenize_isolated(&self, pts: &mut PreTokenizedString) {
let capacity = pts.buffer().len().div_ceil(4).max(pts.splits().len());
let mut new_splits = Vec::with_capacity(capacity);
for split in pts.splits() {
if split.token_id.is_some() {
new_splits.push(split.clone());
continue;
}
let text = pts.split_text(split);
if text.is_empty() {
continue;
}
let base = split.range.start;
self.for_each_fused_piece(text, |_, start, end| {
new_splits.push(PtSplit {
range: (base + start)..(base + end),
token_id: None,
});
});
}
pts.refine_splits(new_splits);
}
fn pre_tokenize_removed_inverted(&self, pts: &mut PreTokenizedString) {
let capacity = pts.buffer().len().div_ceil(4).max(pts.splits().len());
let mut new_splits = Vec::with_capacity(capacity);
for split in pts.splits() {
if split.token_id.is_some() {
new_splits.push(split.clone());
continue;
}
let text = pts.split_text(split);
let base = split.range.start;
self.matcher.for_each_match(text, |start, end| {
new_splits.push(PtSplit {
range: (base + start)..(base + end),
token_id: None,
});
});
}
pts.refine_splits(new_splits);
}
#[cfg(test)]
fn split<'a>(&self, input: &'a str) -> Vec<&'a str> {
let segments = self.find_segments(input);
self.apply_behavior(&segments)
.into_iter()
.filter(|&(start, end)| start < end)
.map(|(start, end)| &input[start..end])
.collect()
}
fn find_segments(&self, input: &str) -> Vec<(usize, usize, bool)> {
let mut segments = Vec::new();
let mut previous = 0;
self.matcher.for_each_match(input, |start, end| {
if start > previous {
segments.push((previous, start, false));
}
segments.push((start, end, true));
previous = end;
});
if previous < input.len() {
segments.push((previous, input.len(), false));
}
if self.invert {
for segment in &mut segments {
segment.2 = !segment.2;
}
}
segments
}
fn apply_behavior(&self, segments: &[(usize, usize, bool)]) -> Vec<(usize, usize)> {
match self.behavior {
SplitBehavior::Removed => segments
.iter()
.filter(|&&(_, _, is_match)| !is_match)
.map(|&(start, end, _)| (start, end))
.collect(),
SplitBehavior::Isolated => segments
.iter()
.map(|&(start, end, _)| (start, end))
.collect(),
SplitBehavior::Contiguous => {
let mut result: Vec<(usize, usize)> = Vec::new();
let mut previous_match = None;
for &(start, end, is_match) in segments {
if previous_match == Some(is_match) {
if let Some(last) = result.last_mut() {
last.1 = end;
}
} else {
result.push((start, end));
}
previous_match = Some(is_match);
}
result
}
SplitBehavior::MergedWithPrevious => {
let mut result: Vec<(usize, usize)> = Vec::new();
let mut previous_was_match = false;
for &(start, end, is_match) in segments {
if is_match && !previous_was_match {
if let Some(last) = result.last_mut() {
last.1 = end;
} else {
result.push((start, end));
}
} else {
result.push((start, end));
}
previous_was_match = is_match;
}
result
}
SplitBehavior::MergedWithNext => {
let mut result: Vec<(usize, usize)> = Vec::new();
let mut previous_was_match = false;
for &(start, end, is_match) in segments.iter().rev() {
if is_match && !previous_was_match {
if let Some(last) = result.last_mut() {
last.0 = start;
} else {
result.push((start, end));
}
} else {
result.push((start, end));
}
previous_was_match = is_match;
}
result.reverse();
result
}
}
}
}
#[cfg(test)]
mod tests {
use serde_json::json;
use tokenizers::{
OffsetReferential, OffsetType, PreTokenizedString as HfPreTokenizedString, PreTokenizer,
SplitDelimiterBehavior,
pre_tokenizers::split::{Split as HfSplit, SplitPattern},
};
use super::*;
use crate::pre_tokenizers::scanner::{
DEEPSEEK_CJK_PATTERN, DEEPSEEK_MAIN_PATTERN, DEEPSEEK_NUMBER_PATTERN,
GPT2_CASE_INSENSITIVE_PATTERN, GPT2_PATTERN, KIMI_PATTERN, LLAMA_CONTRACTION_PATTERN,
LLAMA_PATTERN, PHI_GLM_PATTERN, QWEN_MARK_PATTERN, QWEN_PATTERN,
};
fn hf_behavior(behavior: &str) -> SplitDelimiterBehavior {
match behavior {
"Removed" => SplitDelimiterBehavior::Removed,
"Isolated" => SplitDelimiterBehavior::Isolated,
"MergedWithPrevious" => SplitDelimiterBehavior::MergedWithPrevious,
"MergedWithNext" => SplitDelimiterBehavior::MergedWithNext,
"Contiguous" => SplitDelimiterBehavior::Contiguous,
_ => panic!("unknown behavior"),
}
}
fn hf_pieces(source: &str, behavior: &str, invert: bool, input: &str) -> Vec<String> {
let split = HfSplit::new(
SplitPattern::Regex(source.to_string()),
hf_behavior(behavior),
invert,
)
.unwrap();
let mut pts = HfPreTokenizedString::from(input);
split.pre_tokenize(&mut pts).unwrap();
pts.get_splits(OffsetReferential::Original, OffsetType::Byte)
.into_iter()
.map(|(piece, _, _)| piece.to_string())
.collect()
}
#[test]
fn literal_behaviors_match_expected_boundaries() {
let cases = [
("Removed", vec!["the", "final", "countdown"]),
("Isolated", vec!["the", "-", "final", "-", "-", "countdown"]),
(
"MergedWithPrevious",
vec!["the-", "final-", "-", "countdown"],
),
("MergedWithNext", vec!["the", "-final", "-", "-countdown"]),
("Contiguous", vec!["the", "-", "final", "--", "countdown"]),
];
for (behavior, expected) in cases {
let split = Split::from_config(&json!({"String": "-"}), behavior, false).unwrap();
assert_eq!(split.split("the-final--countdown"), expected);
}
let literal = Split::from_config(&json!({"String": "[a]"}), "Isolated", false).unwrap();
assert_eq!(literal.split("a[a]b"), vec!["a", "[a]", "b"]);
}
#[test]
fn fixed_scanners_match_hugging_face_on_semantic_edges() {
let patterns = [
(LLAMA_PATTERN, "Isolated", false),
(LLAMA_CONTRACTION_PATTERN, "Isolated", false),
(LLAMA_CONTRACTION_PATTERN, "Removed", true),
(KIMI_PATTERN, "Isolated", false),
(KIMI_PATTERN, "MergedWithPrevious", false),
(QWEN_PATTERN, "Isolated", false),
(QWEN_MARK_PATTERN, "Isolated", false),
(PHI_GLM_PATTERN, "Isolated", false),
(PHI_GLM_PATTERN, "Removed", true),
(DEEPSEEK_NUMBER_PATTERN, "Isolated", false),
(DEEPSEEK_CJK_PATTERN, "Isolated", false),
(DEEPSEEK_MAIN_PATTERN, "Isolated", false),
(GPT2_PATTERN, "Isolated", false),
(GPT2_CASE_INSENSITIVE_PATTERN, "Isolated", false),
];
let inputs = [
"I'm DON'T we're HTTPServer camelCase 12345",
" café\u{301} \u{01c5}uro 你好世界! \t\n trailing ",
"a.\n\nx",
"$True foo\tbar\r\n/baz 🚀",
"\u{216b}\u{b2} numbers\u{85}\u{a0}space\u{2028}line",
"\u{300}\u{301}\u{302}",
"汉字𠀀かなカナ mixedHan字word",
"\u{3}\u{b}BASKETBALL",
];
for (source, behavior, invert) in patterns {
let scanner = Split::from_config(&json!({"Regex": source}), behavior, invert).unwrap();
for input in inputs {
let actual: Vec<String> = if behavior == "Removed" && invert {
let mut pts = PreTokenizedString::from_text(input);
scanner.pre_tokenize(&mut pts).unwrap();
pts.splits()
.iter()
.map(|split| pts.split_text(split).to_string())
.collect()
} else {
scanner
.split(input)
.into_iter()
.map(str::to_string)
.collect()
};
let expected = hf_pieces(source, behavior, invert, input);
assert_eq!(actual, expected, "pattern={source:?}, input={input:?}");
}
}
}
#[test]
fn unsupported_regex_is_rejected_without_fallback() {
let error = Split::from_config(&json!({"Regex": "\\d+"}), "Isolated", false).unwrap_err();
assert!(matches!(error, Error::Unsupported(_)));
}
#[test]
fn pre_tokenize_preserves_added_tokens() {
let split = Split::from_config(&json!({"String": " "}), "Removed", false).unwrap();
let mut pts = PreTokenizedString::new(
"hello world".to_string(),
vec![
PtSplit {
range: 0..5,
token_id: None,
},
PtSplit {
range: 5..5,
token_id: Some(42),
},
PtSplit {
range: 5..11,
token_id: None,
},
],
);
split.pre_tokenize(&mut pts).unwrap();
assert!(pts.splits().iter().any(|piece| piece.token_id == Some(42)));
}
}