ferrite-model 0.1.0

GGUF parsing and tokenization for the Ferrite inference engine
Documentation
use super::{TokenizationControl, TokenizerError};
use std::collections::BTreeMap;

#[derive(Clone, Debug, PartialEq, Eq)]
pub(super) struct BpeMetadata {
    token_to_id: BTreeMap<String, usize>,
    pair_merges: BTreeMap<String, BTreeMap<String, RankedBpeMerge>>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct RankedBpeMerge {
    rank: usize,
    merged: String,
}

impl BpeMetadata {
    pub(super) fn new(tokens: &[String], merges: &[String]) -> Result<Self, TokenizerError> {
        let token_to_id = tokens
            .iter()
            .enumerate()
            .map(|(id, token)| (token.clone(), id))
            .collect::<BTreeMap<_, _>>();
        let mut pair_merges: BTreeMap<String, BTreeMap<String, RankedBpeMerge>> = BTreeMap::new();
        for (rank, merge) in merges.iter().enumerate() {
            let Some((left, right)) = parse_merge(merge) else {
                return Err(TokenizerError::new(format!(
                    "invalid BPE merge rule {merge:?}"
                )));
            };
            let merged = format!("{left}{right}");
            if token_to_id.contains_key(merged.as_str()) {
                pair_merges
                    .entry(left.to_owned())
                    .or_default()
                    .entry(right.to_owned())
                    .or_insert(RankedBpeMerge { rank, merged });
            }
        }
        Ok(Self {
            token_to_id,
            pair_merges,
        })
    }
}

pub(super) fn decode(ids: &[usize], tokens: &[String]) -> Result<String, TokenizerError> {
    let mut bytes = Vec::new();
    for id in ids {
        let token = tokens
            .get(*id)
            .ok_or_else(|| TokenizerError::new(format!("token id {id} is out of bounds")))?;
        for value in token.chars() {
            bytes.push(unicode_to_byte(value)?);
        }
    }
    String::from_utf8(bytes).map_err(|error| {
        let message = format!("BPE decoded invalid UTF-8: {error}");
        if error.utf8_error().error_len().is_none() {
            TokenizerError::incomplete_utf8(message)
        } else {
            TokenizerError::new(message)
        }
    })
}

pub(super) fn encode_with_cancellation(
    input: &str,
    metadata: &BpeMetadata,
    mut on_cancellation_poll: impl FnMut() -> TokenizationControl,
) -> Result<Vec<usize>, TokenizerError> {
    if on_cancellation_poll() == TokenizationControl::Cancel {
        return Err(TokenizerError::cancelled());
    }
    let mut symbols = seed_symbols(input, &metadata.token_to_id, &mut on_cancellation_poll)?;

    while let Some(candidate) = best_active_merge(&symbols, &metadata.pair_merges) {
        if on_cancellation_poll() == TokenizationControl::Cancel {
            return Err(TokenizerError::cancelled());
        }
        apply_merge(
            &mut symbols,
            &candidate.left,
            &candidate.right,
            &candidate.merged,
        );
    }

    symbols
        .iter()
        .map(|symbol| {
            metadata
                .token_to_id
                .get(symbol.as_str())
                .copied()
                .ok_or_else(|| TokenizerError::new(format!("BPE token {symbol:?} is not in vocab")))
        })
        .collect()
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct ActiveMerge {
    rank: usize,
    left: String,
    right: String,
    merged: String,
}

fn best_active_merge(
    symbols: &[String],
    pair_merges: &BTreeMap<String, BTreeMap<String, RankedBpeMerge>>,
) -> Option<ActiveMerge> {
    let mut best = None;
    for pair in symbols.windows(2) {
        let left = &pair[0];
        let right = &pair[1];
        let Some(ranked) = pair_merges
            .get(left.as_str())
            .and_then(|right_merges| right_merges.get(right.as_str()))
        else {
            continue;
        };

        if best
            .as_ref()
            .is_none_or(|current: &ActiveMerge| ranked.rank < current.rank)
        {
            best = Some(ActiveMerge {
                rank: ranked.rank,
                left: left.clone(),
                right: right.clone(),
                merged: ranked.merged.clone(),
            });
        }
    }
    best
}

fn seed_symbols(
    input: &str,
    token_to_id: &BTreeMap<String, usize>,
    on_cancellation_poll: &mut impl FnMut() -> TokenizationControl,
) -> Result<Vec<String>, TokenizerError> {
    let mut symbols = Vec::with_capacity(input.len());
    for (index, byte) in input.as_bytes().iter().enumerate() {
        if index % 1024 == 0 && on_cancellation_poll() == TokenizationControl::Cancel {
            return Err(TokenizerError::cancelled());
        }
        let symbol = byte_to_unicode(*byte)?.to_string();
        if token_to_id.contains_key(symbol.as_str()) {
            symbols.push(symbol);
        } else {
            return Err(TokenizerError::new(format!(
                "no BPE seed token matches {symbol:?}"
            )));
        }
    }
    Ok(symbols)
}

fn byte_to_unicode(byte: u8) -> Result<char, TokenizerError> {
    let code_point =
        if (33..=126).contains(&byte) || (161..=172).contains(&byte) || (174..=255).contains(&byte)
        {
            return Ok(byte as char);
        } else if byte <= 32 {
            u32::from(byte) + 256
        } else if byte <= 160 {
            u32::from(byte) + 162
        } else {
            323
        };

    char::from_u32(code_point).ok_or_else(|| {
        TokenizerError::new(format!(
            "GPT-2 byte mapping produced invalid code point {code_point}"
        ))
    })
}

fn unicode_to_byte(value: char) -> Result<u8, TokenizerError> {
    let code_point = value as u32;
    let byte = if (33..=126).contains(&code_point)
        || (161..=172).contains(&code_point)
        || (174..=255).contains(&code_point)
    {
        code_point
    } else if (256..=288).contains(&code_point) {
        code_point - 256
    } else if (289..=322).contains(&code_point) {
        code_point - 162
    } else if code_point == 323 {
        173
    } else {
        return Err(TokenizerError::new(format!(
            "BPE token character {value:?} is not in the GPT-2 byte alphabet"
        )));
    };

    u8::try_from(byte).map_err(|error| {
        TokenizerError::new(format!(
            "GPT-2 byte mapping produced invalid byte {byte}: {error}"
        ))
    })
}

fn parse_merge(merge: &str) -> Option<(&str, &str)> {
    let mut parts = merge.split(' ');
    let left = parts.next()?;
    let right = parts.next()?;
    if left.is_empty() || right.is_empty() || parts.next().is_some() {
        return None;
    }
    Some((left, right))
}

fn apply_merge(symbols: &mut Vec<String>, left: &str, right: &str, merged: &str) {
    let mut index = 0usize;
    while index + 1 < symbols.len() {
        if symbols[index] == left && symbols[index + 1] == right {
            symbols[index] = merged.to_owned();
            symbols.remove(index + 1);
        } else {
            index += 1;
        }
    }
}