snaptokens 0.2.2

Fast BPE tokenization from local Hugging Face tokenizer.json files
Documentation
pub(crate) mod byte_level;
mod scanner;
mod split;

use crate::{json_structs::PreTokenizerConfig, pre_tokenized::PreTokenizedString};

pub use self::{
    byte_level::ByteLevel,
    split::{Split, SplitBehavior},
};

pub(crate) use self::byte_level::BYTE_TO_CHAR;

/// Receives borrowed pre-token ranges from a scanner without a closure trampoline.
pub(crate) trait FusedPieceSink {
    /// Queue one non-empty range from `input` without revalidating it.
    ///
    /// # Safety
    ///
    /// `start..end` must be an in-bounds UTF-8 range of `input`.
    unsafe fn push_piece(&mut self, input: &str, start: usize, end: usize);

    /// Queue every trusted boundary bit while advancing the pending start.
    #[inline(always)]
    unsafe fn push_mask(
        &mut self,
        input: &str,
        mask_base: usize,
        start: &mut usize,
        mut mask: u64,
    ) {
        while mask != 0 {
            let end = mask_base + mask.trailing_zeros() as usize;
            mask &= mask - 1;
            unsafe { self.push_piece(input, *start, end) };
            *start = end;
        }
    }
}

/// Errors from constructing or running a pre-tokenizer.
#[derive(Debug, thiserror::Error)]
pub enum Error {
    /// A JSON value could not be deserialized into the expected type (e.g. an
    /// unrecognized pattern format or behavior string).
    #[error("invalid config value: {0}")]
    Json(#[from] serde_json::Error),

    /// A supported pre-tokenizer has a configuration this scanner cannot run.
    #[error("unsupported pre-tokenizer configuration: {0}")]
    Unsupported(String),
}

/// A compiled pre-tokenizer ready for use.
#[derive(Clone, Debug)]
pub enum PreTokenizer {
    ByteLevel(ByteLevel),
    Split(Split),
    Sequence(Vec<PreTokenizer>),
}

/// Borrowed Split stages that can stream directly into bulk ByteLevel.
#[derive(Clone, Copy)]
pub(crate) struct FusedSplits<'a> {
    steps: &'a [PreTokenizer],
}

impl<'a> FusedSplits<'a> {
    /// Return the only Split when the fused pipeline has exactly one stage.
    pub(crate) fn single(self) -> Option<&'a Split> {
        match self.steps {
            [PreTokenizer::Split(split)] => Some(split),
            _ => None,
        }
    }

    /// Apply every Split stage to the materialized fallback representation.
    pub(crate) fn pre_tokenize(self, pts: &mut PreTokenizedString) -> Result<(), Error> {
        for step in self.steps {
            let PreTokenizer::Split(split) = step else {
                unreachable!("fused Split chain was validated at construction");
            };
            split.pre_tokenize(pts)?;
        }
        Ok(())
    }

    /// Visit final ranges after applying every isolated Split in sequence.
    pub(crate) fn for_each_piece(self, input: &str, mut emit: impl FnMut(&str, usize, usize)) {
        if let Some(split) = self.single() {
            split.for_each_fused_piece(input, emit);
            return;
        }
        if self.is_deepseek() {
            scanner::for_each_deepseek_piece(input, |start, end| emit(input, start, end));
            return;
        }
        visit_fused_splits(self.steps, input, 0, input.len(), &mut emit);
    }

    /// Stream fixed mask-scanner pieces directly into a concrete sink.
    #[inline(always)]
    pub(crate) fn stream_into(self, input: &str, sink: &mut impl FusedPieceSink) {
        if let Some(split) = self.single()
            && let Some(pattern) = split.pattern_id()
            && scanner::stream_mask_matches(pattern, input, sink)
        {
            return;
        }
        self.for_each_piece(input, |input, start, end| {
            // SAFETY: every Split emitter returns exact ranges of `input`.
            unsafe { sink.push_piece(input, start, end) }
        });
    }

    /// Return whether these are the exact three DeepSeek Split grammars.
    fn is_deepseek(self) -> bool {
        match self.steps {
            [
                PreTokenizer::Split(numbers),
                PreTokenizer::Split(cjk),
                PreTokenizer::Split(main),
            ] => {
                numbers.pattern_id() == Some(scanner::PatternId::DeepSeekNumber)
                    && cjk.pattern_id() == Some(scanner::PatternId::DeepSeekCjk)
                    && main.pattern_id() == Some(scanner::PatternId::DeepSeekMain)
            }
            _ => false,
        }
    }
}

/// Recursively refine one borrowed range through the remaining Split stages.
fn visit_fused_splits(
    steps: &[PreTokenizer],
    input: &str,
    start: usize,
    end: usize,
    emit: &mut dyn FnMut(&str, usize, usize),
) {
    let Some((step, remaining)) = steps.split_first() else {
        emit(input, start, end);
        return;
    };
    let PreTokenizer::Split(split) = step else {
        unreachable!("fused Split chain was validated at construction");
    };
    split.for_each_fused_piece(&input[start..end], |_, piece_start, piece_end| {
        visit_fused_splits(
            remaining,
            input,
            start + piece_start,
            start + piece_end,
            emit,
        );
    });
}

impl PreTokenizer {
    /// Build a pre-tokenizer from its JSON configuration.
    pub fn from_config(config: PreTokenizerConfig) -> Result<Self, Error> {
        match config {
            PreTokenizerConfig::ByteLevel(bl) => Ok(Self::ByteLevel(bl)),
            PreTokenizerConfig::Split(s) => Ok(Self::Split(s)),
            PreTokenizerConfig::Sequence { pretokenizers } => {
                let steps = pretokenizers
                    .into_iter()
                    .map(Self::from_config)
                    .collect::<Result<Vec<_>, _>>()?;
                Ok(Self::Sequence(steps))
            }
        }
    }

    /// Refine the splits of `pts` in place.
    pub fn pre_tokenize(&self, pts: &mut PreTokenizedString) -> Result<(), Error> {
        match self {
            Self::ByteLevel(bl) => bl.pre_tokenize(pts),
            Self::Split(s) => s.pre_tokenize(pts),
            Self::Sequence(steps) => {
                for step in steps {
                    step.pre_tokenize(pts)?;
                }
                Ok(())
            }
        }
    }

    /// Return a bulk ByteLevel step and any Splits that can stream into it.
    pub(crate) fn fused_byte_level(&self) -> Option<(Option<FusedSplits<'_>>, &ByteLevel)> {
        match self {
            Self::ByteLevel(byte_level) if byte_level.can_fuse() => Some((None, byte_level)),
            Self::Sequence(steps) => {
                let (last, split_steps) = steps.split_last()?;
                let Self::ByteLevel(byte_level) = last else {
                    return None;
                };
                if split_steps.is_empty()
                    || !byte_level.is_bulk_only()
                    || !split_steps.iter().all(
                        |step| matches!(step, Self::Split(split) if split.supports_fused_stream()),
                    )
                {
                    return None;
                }
                Some((Some(FusedSplits { steps: split_steps }), byte_level))
            }
            _ => None,
        }
    }

    /// Return whether this pipeline contains a ByteLevel step at any depth.
    pub(crate) fn contains_byte_level(&self) -> bool {
        match self {
            Self::ByteLevel(_) => true,
            Self::Split(_) => false,
            Self::Sequence(steps) => steps.iter().any(Self::contains_byte_level),
        }
    }
}

#[cfg(test)]
mod tests {
    use serde_json::json;

    use super::*;

    /// Compare the one-pass DeepSeek scanner with the generic three-Split pipeline.
    #[test]
    fn deepseek_fused_scanner_matches_split_chain() {
        let patterns = [
            scanner::DEEPSEEK_NUMBER_PATTERN,
            scanner::DEEPSEEK_CJK_PATTERN,
            scanner::DEEPSEEK_MAIN_PATTERN,
        ];
        let steps: Vec<_> = patterns
            .into_iter()
            .map(|pattern| {
                PreTokenizer::Split(
                    Split::from_config(&json!({"Regex": pattern}), "Isolated", false).unwrap(),
                )
            })
            .collect();
        let fused = FusedSplits { steps: &steps };

        let compare = |input: &str| {
            let mut expected = Vec::new();
            visit_fused_splits(&steps, input, 0, input.len(), &mut |_, start, end| {
                expected.push((start, end));
            });
            let mut actual = Vec::new();
            fused.for_each_piece(input, |_, start, end| actual.push((start, end)));
            assert_eq!(actual, expected, "DeepSeek pieces diverged on {input:?}");
        };

        for input in [
            "a  1 日本語・テスト\n",
            "cafe\u{301} \u{301}leading ١٢٣٤",
            "x\0\0b \u{200b}word 3.14159",
            "\u{3040}あ ゛カナ 一二三123",
            "@user #tag <|endoftext|>",
        ] {
            compare(input);
        }

        let atoms = [
            "a", "Z", "é", "١", " ", "\t", "\n", "\u{301}", ".", "☃", "\0", "\u{200b}", "一", "あ",
            "・",
        ];
        let mut state = 0xDEE9_5EEC_u64;
        for _ in 0..1_000 {
            state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
            let length = 1 + (state as usize % 39);
            let mut input = String::new();
            for _ in 0..length {
                state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
                input.push_str(atoms[state as usize % atoms.len()]);
            }
            compare(&input);
        }
    }
}