snowstem 0.1.0

//! Runtime the generated algorithm modules drive.
//!
//! A Snowball program works on one word at a time through a cursor, a
//! forward limit, a backward limit and a bracketed slice. The generated
//! code owns the control flow and calls into this module for every
//! operation that touches the text: literal tests, grouping tests,
//! among-table lookup and slice replacement. Everything here runs on a
//! byte buffer that lives on the stack for words up to 64 bytes.

pub mod algorithms;

use alloc::borrow::Cow;
use alloc::string::String;
use core::ops::Deref;
use core::str::Chars;

/// The optional guard of an among entry, run once its literal matches.
pub type AmongGuard<T> = Option<&'static (dyn Fn(&mut SnowballEnv, &mut T) -> bool + Sync)>;

/// One entry of an among table: the literal, the index of the entry it
/// continues from on failure, the result code, and an optional guard.
pub struct Among<T: 'static>(pub &'static str, pub i32, pub i32, pub AmongGuard<T>);

/// Words up to this many bytes are edited in a stack buffer.
const INLINE: usize = 64;

/// Extra capacity reserved when a word moves to the heap, so later
/// edits that grow the word stay inside one allocation.
const SLACK: usize = 16;

enum Store {
    /// The input itself, untouched so far. Used for long words only.
    Shared,
    /// A copy of the word in a fixed stack buffer.
    Inline { len: u8, buf: [u8; INLINE] },
    /// A heap copy: a long word after its first edit, or the caller's
    /// buffer in `stem_into`.
    Heap(String),
}

/// View a stack buffer as text. Every edit splices valid UTF-8 at char
/// boundaries, so the bytes always form a valid string.
fn inline_str(bytes: &[u8]) -> &str {
    core::str::from_utf8(bytes).expect("stack buffer holds valid UTF-8")
}

/// The word being stemmed.
pub struct Text<'a> {
    source: &'a str,
    store: Store,
}

impl<'a> Text<'a> {
    fn new(source: &'a str) -> Self {
        let store = if source.len() <= INLINE {
            let mut buf = [0u8; INLINE];
            buf[..source.len()].copy_from_slice(source.as_bytes());
            Store::Inline {
                len: source.len() as u8,
                buf,
            }
        } else {
            Store::Shared
        };
        Text { source, store }
    }

    fn in_buffer(source: &'a str, mut buffer: String) -> Self {
        buffer.clear();
        buffer.push_str(source);
        Text {
            source,
            store: Store::Heap(buffer),
        }
    }

    /// The current bytes of the word.
    pub fn as_bytes(&self) -> &[u8] {
        match &self.store {
            Store::Shared => self.source.as_bytes(),
            Store::Inline { len, buf } => &buf[..usize::from(*len)],
            Store::Heap(s) => s.as_bytes(),
        }
    }

    fn as_str(&self) -> &str {
        match &self.store {
            Store::Shared => self.source,
            Store::Inline { len, buf } => inline_str(&buf[..usize::from(*len)]),
            Store::Heap(s) => s,
        }
    }

    /// The current characters of the word.
    pub fn chars(&self) -> Chars<'_> {
        self.as_str().chars()
    }

    /// Replace bytes `bra..ket` with `s`. Both bounds are char boundaries.
    fn replace(&mut self, bra: usize, ket: usize, s: &str) {
        if &self.as_bytes()[bra..ket] == s.as_bytes() {
            return;
        }
        let new_len = self.as_bytes().len() - (ket - bra) + s.len();
        if let Store::Inline { len, buf } = &mut self.store {
            if new_len <= INLINE {
                let old = usize::from(*len);
                buf.copy_within(ket..old, bra + s.len());
                buf[bra..bra + s.len()].copy_from_slice(s.as_bytes());
                *len = new_len as u8;
                return;
            }
        }
        if let Store::Heap(string) = &mut self.store {
            string.replace_range(bra..ket, s);
            return;
        }
        let current = self.as_str();
        let mut string = String::with_capacity(new_len + SLACK);
        string.push_str(&current[..bra]);
        string.push_str(s);
        string.push_str(&current[ket..]);
        self.store = Store::Heap(string);
    }

    fn finish(self) -> Cow<'a, str> {
        match self.store {
            Store::Shared => Cow::Borrowed(self.source),
            Store::Inline { len, buf } => {
                let bytes = &buf[..usize::from(len)];
                if bytes == self.source.as_bytes() {
                    Cow::Borrowed(self.source)
                } else {
                    Cow::Owned(String::from(inline_str(bytes)))
                }
            }
            Store::Heap(s) => Cow::Owned(s),
        }
    }

    fn finish_into(self, out: &mut String) {
        match self.store {
            Store::Heap(s) => *out = s,
            Store::Shared => {
                out.clear();
                out.push_str(self.source);
            }
            Store::Inline { len, buf } => {
                out.clear();
                out.push_str(inline_str(&buf[..usize::from(len)]));
            }
        }
    }
}

/// A Snowball string variable. Holds up to 15 bytes on the stack and
/// spills to the heap past that.
#[derive(Clone)]
pub enum StrBuf {
    Inline { len: u8, buf: [u8; 15] },
    Heap(String),
}

impl StrBuf {
    /// An empty variable.
    pub fn new() -> Self {
        StrBuf::Inline {
            len: 0,
            buf: [0; 15],
        }
    }

    fn copied_from(s: &str) -> Self {
        if s.len() <= 15 {
            let mut buf = [0u8; 15];
            buf[..s.len()].copy_from_slice(s.as_bytes());
            StrBuf::Inline {
                len: s.len() as u8,
                buf,
            }
        } else {
            StrBuf::Heap(String::from(s))
        }
    }
}

impl Default for StrBuf {
    fn default() -> Self {
        StrBuf::new()
    }
}

impl Deref for StrBuf {
    type Target = str;

    fn deref(&self) -> &str {
        match self {
            StrBuf::Inline { len, buf } => inline_str(&buf[..usize::from(*len)]),
            StrBuf::Heap(s) => s,
        }
    }
}

/// Per-call state of one stemming run.
pub struct SnowballEnv<'a> {
    pub current: Text<'a>,
    pub cursor: i32,
    pub limit: i32,
    pub limit_backward: i32,
    pub bra: i32,
    pub ket: i32,
}

/// Decode the char starting at byte `c`, returning the code point and
/// its width. `c` is a char boundary below `bytes.len()`.
fn char_at(bytes: &[u8], c: usize) -> (u32, usize) {
    let b0 = bytes[c];
    if b0 < 0xC0 {
        return (u32::from(b0), 1);
    }
    let b1 = u32::from(bytes[c + 1] & 0x3F);
    if b0 < 0xE0 {
        return ((u32::from(b0 & 0x1F) << 6) | b1, 2);
    }
    let b2 = u32::from(bytes[c + 2] & 0x3F);
    if b0 < 0xF0 {
        return ((u32::from(b0 & 0x0F) << 12) | (b1 << 6) | b2, 3);
    }
    let b3 = u32::from(bytes[c + 3] & 0x3F);
    (
        (u32::from(b0 & 0x07) << 18) | (b1 << 12) | (b2 << 6) | b3,
        4,
    )
}

/// Decode the char ending at byte `c`, returning the code point and
/// its width. `c` is a char boundary above 0.
fn char_before(bytes: &[u8], c: usize) -> (u32, usize) {
    let mut start = c - 1;
    while bytes[start] & 0xC0 == 0x80 {
        start -= 1;
    }
    let (ch, _) = char_at(bytes, start);
    (ch, c - start)
}

fn in_set(set: &[u8], min: u32, max: u32, ch: u32) -> bool {
    if ch < min || ch > max {
        return false;
    }
    let bit = ch - min;
    set[(bit >> 3) as usize] & (1 << (bit & 7)) != 0
}

impl<'a> SnowballEnv<'a> {
    fn with_text(current: Text<'a>) -> Self {
        let limit = current.as_bytes().len() as i32;
        SnowballEnv {
            current,
            cursor: 0,
            limit,
            limit_backward: 0,
            bra: 0,
            ket: 0,
        }
    }

    /// Run `algorithm` over `word` and hand back the stem, borrowing the
    /// input when the stem equals it.
    pub(crate) fn run(algorithm: fn(&mut SnowballEnv) -> bool, word: &'a str) -> Cow<'a, str> {
        let mut env = SnowballEnv::with_text(Text::new(word));
        algorithm(&mut env);
        env.current.finish()
    }

    /// Run `algorithm` over `word`, using `out` as the working buffer
    /// and leaving the stem in it.
    pub(crate) fn run_into(algorithm: fn(&mut SnowballEnv) -> bool, word: &str, out: &mut String) {
        let buffer = core::mem::take(out);
        let mut env = SnowballEnv::with_text(Text::in_buffer(word, buffer));
        algorithm(&mut env);
        env.current.finish_into(out);
    }

    fn replace_s(&mut self, bra: i32, ket: i32, s: &str) -> i32 {
        let adjustment = s.len() as i32 - (ket - bra);
        self.current.replace(bra as usize, ket as usize, s);
        if adjustment != 0 {
            self.limit += adjustment;
            if self.cursor >= ket {
                self.cursor += adjustment;
            } else if self.cursor > bra {
                self.cursor = bra;
            }
        }
        adjustment
    }

    /// Replace the bracketed slice with `s`.
    pub fn slice_from(&mut self, s: &str) {
        let (bra, ket) = (self.bra, self.ket);
        self.replace_s(bra, ket, s);
        self.ket = bra + s.len() as i32;
    }

    /// Delete the bracketed slice.
    pub fn slice_del(&mut self) {
        self.slice_from("");
    }

    /// Replace `bra..ket` with `s`, keeping the bracketed slice in step.
    pub fn insert(&mut self, bra: i32, ket: i32, s: &str) {
        let adjustment = self.replace_s(bra, ket, s);
        if bra <= self.ket {
            self.ket += adjustment;
            if bra <= self.bra {
                self.bra += adjustment;
            }
        }
    }

    /// Copy the bracketed slice into a string variable.
    pub fn slice_to(&self) -> StrBuf {
        let bytes = &self.current.as_bytes()[self.bra as usize..self.ket as usize];
        StrBuf::copied_from(inline_str(bytes))
    }

    /// Test for `s` at the cursor and step over it.
    pub fn eq_s(&mut self, s: &str) -> bool {
        let c = self.cursor as usize;
        let end = c + s.len();
        if end > self.limit as usize || &self.current.as_bytes()[c..end] != s.as_bytes() {
            return false;
        }
        self.cursor = end as i32;
        true
    }

    /// Test for `s` ending at the cursor and step back over it.
    pub fn eq_s_b(&mut self, s: &str) -> bool {
        let c = self.cursor as usize;
        let start = self.limit_backward as usize + s.len();
        if start > c || &self.current.as_bytes()[c - s.len()..c] != s.as_bytes() {
            return false;
        }
        self.cursor = (c - s.len()) as i32;
        true
    }

    /// Step the cursor forward one char. The caller checks the limit.
    pub fn next_char(&mut self) {
        let c = self.cursor as usize;
        let bytes = self.current.as_bytes();
        let mut n = c + 1;
        while n < bytes.len() && bytes[n] & 0xC0 == 0x80 {
            n += 1;
        }
        self.cursor = n as i32;
    }

    /// Step the cursor back one char. The caller checks the limit.
    pub fn previous_char(&mut self) {
        let bytes = self.current.as_bytes();
        let mut n = self.cursor as usize - 1;
        while bytes[n] & 0xC0 == 0x80 {
            n -= 1;
        }
        self.cursor = n as i32;
    }

    /// Move the cursor forward `delta` chars, failing at the limit.
    pub fn hop(&mut self, delta: i32) -> bool {
        let bytes = self.current.as_bytes();
        let l = self.limit as usize;
        let mut c = self.cursor as usize;
        for _ in 0..delta {
            if c >= l {
                return false;
            }
            c += 1;
            while c < l && bytes[c] & 0xC0 == 0x80 {
                c += 1;
            }
        }
        self.cursor = c as i32;
        true
    }

    /// Move the cursor back `delta` chars, failing at the backward limit.
    pub fn hop_back(&mut self, delta: i32) -> bool {
        let bytes = self.current.as_bytes();
        let lb = self.limit_backward as usize;
        let mut c = self.cursor as usize;
        for _ in 0..delta {
            if c <= lb {
                return false;
            }
            c -= 1;
            while c > lb && bytes[c] & 0xC0 == 0x80 {
                c -= 1;
            }
        }
        self.cursor = c as i32;
        true
    }

    fn peek(&self) -> Option<(u32, usize)> {
        if self.cursor >= self.limit {
            return None;
        }
        Some(char_at(self.current.as_bytes(), self.cursor as usize))
    }

    fn peek_back(&self) -> Option<(u32, usize)> {
        if self.cursor <= self.limit_backward {
            return None;
        }
        Some(char_before(self.current.as_bytes(), self.cursor as usize))
    }

    /// Step over the char at the cursor if it is in the grouping.
    pub fn in_grouping(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        match self.peek() {
            Some((ch, w)) if in_set(set, min, max, ch) => {
                self.cursor += w as i32;
                true
            }
            _ => false,
        }
    }

    /// Step over the char at the cursor if it is outside the grouping.
    pub fn out_grouping(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        match self.peek() {
            Some((ch, w)) if !in_set(set, min, max, ch) => {
                self.cursor += w as i32;
                true
            }
            _ => false,
        }
    }

    /// Step back over the char before the cursor if it is in the grouping.
    pub fn in_grouping_b(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        match self.peek_back() {
            Some((ch, w)) if in_set(set, min, max, ch) => {
                self.cursor -= w as i32;
                true
            }
            _ => false,
        }
    }

    /// Step back over the char before the cursor if it is outside the grouping.
    pub fn out_grouping_b(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        match self.peek_back() {
            Some((ch, w)) if !in_set(set, min, max, ch) => {
                self.cursor -= w as i32;
                true
            }
            _ => false,
        }
    }

    /// Advance while chars are in the grouping. Succeeds when a char
    /// outside it is reached, fails at the limit.
    pub fn go_in_grouping(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        while let Some((ch, w)) = self.peek() {
            if !in_set(set, min, max, ch) {
                return true;
            }
            self.cursor += w as i32;
        }
        false
    }

    /// Advance while chars are outside the grouping. Succeeds when a
    /// char inside it is reached, fails at the limit.
    pub fn go_out_grouping(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        while let Some((ch, w)) = self.peek() {
            if in_set(set, min, max, ch) {
                return true;
            }
            self.cursor += w as i32;
        }
        false
    }

    /// Backward form of [`go_in_grouping`](Self::go_in_grouping).
    pub fn go_in_grouping_b(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        while let Some((ch, w)) = self.peek_back() {
            if !in_set(set, min, max, ch) {
                return true;
            }
            self.cursor -= w as i32;
        }
        false
    }

    /// Backward form of [`go_out_grouping`](Self::go_out_grouping).
    pub fn go_out_grouping_b(&mut self, set: &[u8], min: u32, max: u32) -> bool {
        while let Some((ch, w)) = self.peek_back() {
            if in_set(set, min, max, ch) {
                return true;
            }
            self.cursor -= w as i32;
        }
        false
    }

    /// Find the longest among entry that matches forward from the cursor.
    /// Returns its result code, or 0 when nothing matches.
    pub fn find_among<T>(&mut self, amongs: &[Among<T>], context: &mut T) -> i32 {
        let c = self.cursor as usize;
        let l = self.limit as usize;
        let mut i = 0usize;
        let mut j = amongs.len();
        let mut common_i = 0usize;
        let mut common_j = 0usize;
        let mut first_key_inspected = false;
        loop {
            let k = i + ((j - i) >> 1);
            let w = amongs[k].0.as_bytes();
            let mut common = common_i.min(common_j);
            let mut diff = 0i32;
            for &wb in &w[common..] {
                if c + common == l {
                    diff = -1;
                    break;
                }
                diff = i32::from(self.current.as_bytes()[c + common]) - i32::from(wb);
                if diff != 0 {
                    break;
                }
                common += 1;
            }
            if diff < 0 {
                j = k;
                common_j = common;
            } else {
                i = k;
                common_i = common;
            }
            if j - i <= 1 {
                if i > 0 || j == i || first_key_inspected {
                    break;
                }
                first_key_inspected = true;
            }
        }
        loop {
            let w = &amongs[i];
            if common_i >= w.0.len() {
                self.cursor = (c + w.0.len()) as i32;
                match w.3 {
                    Some(guard) => {
                        if guard(self, context) {
                            self.cursor = (c + w.0.len()) as i32;
                            return w.2;
                        }
                    }
                    None => return w.2,
                }
            }
            if w.1 < 0 {
                return 0;
            }
            i = w.1 as usize;
        }
    }

    /// Find the longest among entry that matches backward from the cursor.
    /// Returns its result code, or 0 when nothing matches.
    pub fn find_among_b<T>(&mut self, amongs: &[Among<T>], context: &mut T) -> i32 {
        let c = self.cursor as usize;
        let lb = self.limit_backward as usize;
        let mut i = 0usize;
        let mut j = amongs.len();
        let mut common_i = 0usize;
        let mut common_j = 0usize;
        let mut first_key_inspected = false;
        loop {
            let k = i + ((j - i) >> 1);
            let w = amongs[k].0.as_bytes();
            let mut common = common_i.min(common_j);
            let mut diff = 0i32;
            for &wb in w[..w.len() - common].iter().rev() {
                if c - common == lb {
                    diff = -1;
                    break;
                }
                diff = i32::from(self.current.as_bytes()[c - common - 1]) - i32::from(wb);
                if diff != 0 {
                    break;
                }
                common += 1;
            }
            if diff < 0 {
                j = k;
                common_j = common;
            } else {
                i = k;
                common_i = common;
            }
            if j - i <= 1 {
                if i > 0 || j == i || first_key_inspected {
                    break;
                }
                first_key_inspected = true;
            }
        }
        loop {
            let w = &amongs[i];
            if common_i >= w.0.len() {
                self.cursor = (c - w.0.len()) as i32;
                match w.3 {
                    Some(guard) => {
                        if guard(self, context) {
                            self.cursor = (c - w.0.len()) as i32;
                            return w.2;
                        }
                    }
                    None => return w.2,
                }
            }
            if w.1 < 0 {
                return 0;
            }
            i = w.1 as usize;
        }
    }
}