aozora 0.5.0

//! Tokenize stage — linear tokenization of sanitized source into a token stream.
//!
//! Walks the sanitize-stage text via the SIMD-accelerated
//! [`crate::scan`] module and exposes a stateful iterator yielding one
//! [`Token`] per delimiter or contiguous text run. Triggers are the
//! Aozora notation marker characters listed in [`TriggerKind`];
//! everything else flows into [`Token::Text`] runs.
//!
//! Two production-ready surfaces sit side by side:
//!
//! - [`tokenize`] — streaming `impl Iterator<Item = Token>`, kept for
//!   FFI / incremental / pull-based consumers that have no arena.
//! - `tokenize_in` — arena-batch `BumpVec<'a, Token>` allocated
//!   inside the caller's `Arena`; the scratch trigger /
//!   newline offset buffers used during the merge walk also live in
//!   the arena.
//!
//! The Aozora pipeline drives `tokenize_in` because it already owns an
//! arena; benchmarks and FFI shims that want lazy semantics use
//! `tokenize`. There is no third "heap-batch" entry point.
//!
//! ## Algorithm
//!
//! 1. [`crate::scan::scan_offsets`] returns the byte offsets of every
//!    trigger character in `source`. On `x86_64` this dispatches to
//!    Teddy (Hyperscan multi-pattern fingerprint matcher); on minimal
//!    hosts to a SIMD-free DFA. Both produce byte-identical output.
//! 2. A single [`memchr::memchr_iter`] sweep collects every newline
//!    offset. Together with step 1, source bytes are touched twice
//!    (once per scan), both at near memory-bandwidth speed.
//! 3. [`Iterator::next`] merge-walks the two sorted offset streams
//!    in event order, emitting `Text` / `Trigger` / `Newline` tokens.
//! 4. `≪` / `≫` (U+226A/U+226B) are ordinary single-character triggers
//!    (`AngleQuoteOpen` / `AngleQuoteClose`) — the aozora input encoding
//!    for a 底本's double-angle brackets `《`/`》`. No look-ahead merge.
//!
//! `［＃` is NOT emitted as a merged trigger: `Hash` after
//! `BracketOpen` is common but not universal (a stray `［` followed
//! by plain text is legal). The pair stage inspects the two tokens together.
//!
//! ## Backend
//!
//! Trigger detection uses Teddy (the [Hyperscan](https://intel.github.io/hyperscan/)
//! short-string algorithm via `aho-corasick::packed`); see
//! [`crate::scan`] for the full backend selection. The previous naive
//! per-codepoint walker ran at ~150 MiB/s; Teddy reaches 10–20 GiB/s
//! on Japanese text.

use crate::scan::scan_offsets;
use crate::spec::classify_trigger_bytes;
use crate::syntax::Span;

use super::token::{Token, TriggerKind};

/// Streaming tokeniser over sanitized source text.
///
/// The input is expected to already be sanitize-stage output (BOM-stripped,
/// LF-normalized). Giving raw source to this iterator is not wrong but
/// means diagnostics and positions reference pre-normalization bytes,
/// which will confuse downstream stages.
///
/// # Panics
///
/// Panics on construction if `source.len()` exceeds [`u32::MAX`]
/// (≈ 4 GiB). All aozora spans use `u32` offsets per the
/// [`crate::syntax::Span`] contract; inputs that large are rejected
/// loudly rather than silently truncated.
#[must_use]
pub(crate) fn tokenize(source: &str) -> Tokenizer<'_> {
    Tokenizer::new(source)
}

/// Streaming tokenize-stage tokeniser over the merge of two pre-collected
/// offset streams: trigger positions (from the SIMD scanner) and
/// newline positions (from `memchr`).
///
/// The single-slot `pending` buffer holds a Trigger / Newline that
/// was produced *together* with a closing Text run on the same
/// `next()` call: [`Iterator::next`] returns the Text first, then
/// the buffered event on the following call, preserving the legacy
/// emission order without paying for a `Vec` accumulator.
#[derive(Debug)]
pub(crate) struct Tokenizer<'s> {
    source: &'s str,
    /// Sorted ascending byte offsets where a trigger trigram begins.
    /// Materialised eagerly because the SIMD scanner is much faster
    /// than amortising its internal state across `next()` calls.
    trigger_offsets: Vec<u32>,
    /// Sorted ascending byte offsets of `\n` characters.
    newline_offsets: Vec<u32>,
    t_idx: usize,
    n_idx: usize,
    text_start: u32,
    pending: Option<Token>,
    finished: bool,
}

impl<'s> Tokenizer<'s> {
    fn new(source: &'s str) -> Self {
        assert!(
            u32::try_from(source.len()).is_ok(),
            "source too long for u32 span offsets ({} bytes)",
            source.len()
        );
        let trigger_offsets = scan_offsets(source);
        let bytes = source.as_bytes();
        // memchr_iter is internally vectorised (AVX2 on x86_64, NEON on
        // aarch64) — the same machine code memchr3 uses for trigger
        // candidates, here narrowed to the single newline byte.
        let mut newline_offsets: Vec<u32> = Vec::with_capacity(bytes.len() / 64);
        for n in memchr::memchr_iter(b'\n', bytes) {
            // source.len() <= u32::MAX is asserted at function entry.
            newline_offsets.push(u32::try_from(n).unwrap_or(u32::MAX));
        }
        Self {
            source,
            trigger_offsets,
            newline_offsets,
            t_idx: 0,
            n_idx: 0,
            text_start: 0,
            pending: None,
            finished: false,
        }
    }

    fn flush_text(&mut self, end: u32) -> Option<Token> {
        (end > self.text_start).then(|| {
            let tok = Token::Text {
                range: Span::new(self.text_start, end),
            };
            self.text_start = end;
            tok
        })
    }

    /// Pair a flushed Text token (if any) with the structural event
    /// that produced the flush. The Text comes first, the event is
    /// buffered for the next `next()` call — preserving emission
    /// order without intermediate allocation.
    fn pair_text_then(&mut self, text: Option<Token>, event: Token) -> Token {
        match text {
            Some(t) => {
                self.pending = Some(event);
                t
            }
            None => event,
        }
    }
}

impl Iterator for Tokenizer<'_> {
    type Item = Token;

    fn next(&mut self) -> Option<Token> {
        if let Some(tok) = self.pending.take() {
            return Some(tok);
        }
        if self.finished {
            return None;
        }

        let bytes = self.source.as_bytes();
        let t_offset = self.trigger_offsets.get(self.t_idx).copied();
        let n_offset = self.newline_offsets.get(self.n_idx).copied();

        let next_is_trigger = match (t_offset, n_offset) {
            (Some(t), Some(n)) => t.cmp(&n).is_lt(),
            (Some(_), None) => true,
            (None, Some(_)) => false,
            (None, None) => {
                // No more events: emit any trailing text once, then EOF.
                self.finished = true;
                // source.len() <= u32::MAX is asserted at construction.
                let total_len = u32::try_from(bytes.len()).unwrap_or(u32::MAX);
                return self.flush_text(total_len);
            }
        };

        if next_is_trigger {
            let t_pos = t_offset.expect("checked Some by next_is_trigger arm");
            let kind = trigger_kind_at(bytes, t_pos as usize);
            let byte_len = kind.source_byte_len();
            let trigger = Token::Trigger {
                kind,
                span: Span::new(t_pos, t_pos + byte_len),
            };
            let text = self.flush_text(t_pos);
            self.text_start = t_pos.saturating_add(byte_len);
            let previous = self.t_idx;
            self.t_idx = self.t_idx.saturating_add(1);
            assert!(self.t_idx > previous, "trigger cursor must advance");
            Some(self.pair_text_then(text, trigger))
        } else {
            let n_pos = n_offset.expect("checked Some by !next_is_trigger arm");
            let text = self.flush_text(n_pos);
            let nl = Token::Newline { pos: n_pos };
            self.text_start = n_pos.saturating_add(1);
            let previous = self.n_idx;
            self.n_idx = self.n_idx.saturating_add(1);
            assert!(self.n_idx > previous, "newline cursor must advance");
            Some(self.pair_text_then(text, nl))
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // Lower bound 0 (we may be at EOF after a final flush). Upper
        // bound is at most one event per remaining trigger / newline
        // plus interleaved text + the pending slot. For consumers this
        // is mainly a `Vec::with_capacity` hint, so over-estimating
        // is cheap.
        let triggers_left = self.trigger_offsets.len().saturating_sub(self.t_idx);
        let newlines_left = self.newline_offsets.len().saturating_sub(self.n_idx);
        // Each event contributes at most 2 tokens (text + structural).
        let upper = (triggers_left + newlines_left) * 2 + usize::from(self.pending.is_some()) + 1;
        (0, Some(upper))
    }
}

/// Look at the 3-byte window at `pos` and return its [`TriggerKind`].
/// Caller guarantees `pos + 3 <= bytes.len()` and that the window is
/// in fact a recognised trigger (the scanner's contract).
#[inline]
fn trigger_kind_at(bytes: &[u8], pos: usize) -> TriggerKind {
    let window: [u8; 3] = [bytes[pos], bytes[pos + 1], bytes[pos + 2]];
    classify_trigger_bytes(window).expect("scanner only emits classified positions")
}

#[cfg(test)]
mod tests {
    use super::*;

    fn collect(src: &str) -> Vec<Token> {
        tokenize(src).collect()
    }

    fn triggers(tokens: &[Token]) -> Vec<TriggerKind> {
        tokens
            .iter()
            .filter_map(|t| match t {
                Token::Trigger { kind, .. } => Some(*kind),
                _ => None,
            })
            .collect()
    }

    #[test]
    fn plain_text_is_one_text_token() {
        let toks = collect("hello world こんにちは");
        assert_eq!(toks.len(), 1);
        match &toks[0] {
            Token::Text { range } => {
                assert_eq!(range.start, 0);
                assert_eq!(range.end as usize, "hello world こんにちは".len());
            }
            other => panic!("expected Text, got {other:?}"),
        }
    }

    #[test]
    fn empty_input_yields_no_tokens() {
        assert!(collect("").is_empty());
    }

    #[test]
    fn single_newline_emits_newline_token() {
        let toks = collect("\n");
        assert_eq!(toks.len(), 1);
        assert!(matches!(toks[0], Token::Newline { pos: 0 }));
    }

    #[test]
    fn explicit_ruby_emits_bar_open_close() {
        let toks = collect("a｜漢字《かんじ》b");
        let kinds = triggers(&toks);
        assert_eq!(
            kinds,
            vec![
                TriggerKind::Bar,
                TriggerKind::RubyOpen,
                TriggerKind::RubyClose,
            ]
        );
    }

    #[test]
    fn angle_quote_brackets_are_single_triggers() {
        let toks = collect("≪強調≫");
        let kinds = triggers(&toks);
        assert_eq!(
            kinds,
            vec![TriggerKind::AngleQuoteOpen, TriggerKind::AngleQuoteClose,]
        );
    }

    #[test]
    fn bracket_annotation_emits_each_component_separately() {
        let toks = collect("［＃改ページ］");
        let kinds = triggers(&toks);
        assert_eq!(
            kinds,
            vec![
                TriggerKind::BracketOpen,
                TriggerKind::Hash,
                TriggerKind::BracketClose,
            ]
        );
    }

    #[test]
    fn gaiji_ref_mark_is_emitted() {
        let toks = collect("※［＃「木」、1-2-3］");
        let kinds = triggers(&toks);
        assert_eq!(
            kinds,
            vec![
                TriggerKind::RefMark,
                TriggerKind::BracketOpen,
                TriggerKind::Hash,
                TriggerKind::QuoteOpen,
                TriggerKind::QuoteClose,
                TriggerKind::BracketClose,
            ]
        );
    }

    #[test]
    fn tortoise_brackets_emit_dedicated_triggers() {
        let toks = collect("〔e^〕");
        let kinds = triggers(&toks);
        assert_eq!(
            kinds,
            vec![TriggerKind::TortoiseOpen, TriggerKind::TortoiseClose]
        );
    }

    #[test]
    fn text_between_triggers_is_preserved() {
        let toks = collect("a｜b《c》d");
        let text_ranges: Vec<Span> = toks
            .iter()
            .filter_map(|t| match t {
                Token::Text { range } => Some(*range),
                _ => None,
            })
            .collect();
        // "a"(0..1) before ｜, "b"(4..5) between ｜ and 《, "c"(8..9), "d"(12..13).
        assert_eq!(text_ranges.len(), 4);
        assert_eq!(text_ranges[0], Span::new(0, 1));
        assert_eq!(text_ranges[1], Span::new(4, 5));
        assert_eq!(text_ranges[2], Span::new(8, 9));
        assert_eq!(text_ranges[3], Span::new(12, 13));
    }

    #[test]
    fn adjacent_triggers_produce_no_empty_text_tokens() {
        let toks = collect("｜《》");
        for tok in &toks {
            if let Token::Text { range } = tok {
                assert!(
                    range.end > range.start,
                    "empty Text token leaked into stream: {tok:?}"
                );
            }
        }
    }

    #[test]
    fn newline_is_its_own_token_between_text_runs() {
        let toks = collect("line1\nline2");
        assert_eq!(toks.len(), 3);
        match &toks[0] {
            Token::Text { range } => assert_eq!(*range, Span::new(0, 5)),
            other => panic!("expected Text, got {other:?}"),
        }
        assert!(matches!(toks[1], Token::Newline { pos: 5 }));
        match &toks[2] {
            Token::Text { range } => assert_eq!(*range, Span::new(6, 11)),
            other => panic!("expected Text, got {other:?}"),
        }
    }

    #[test]
    fn size_hint_upper_bound_is_exact_at_construction() {
        // "｜《》" has exactly 3 triggers (Bar, RubyOpen, RubyClose) and
        // 0 newlines. Fresh from `tokenize`, before any `next()`:
        //   triggers_left = 3, newlines_left = 0, pending = None
        //   upper = (3 + 0) * 2 + 0 + 1 = 7
        // The exact `(0, Some(7))` pins the lower bound at 0, forbids a
        // `None` upper, and picks operands so every arithmetic mutation
        // (+↔*, *↔+, *↔/) yields a value other than 7:
        //   (3*0)*2+0+1 = 1, (3+0)+2+0+1 = 6, (3+0)/2+0+1 = 2,
        //   ((3+0)*2)*0+1 = 1, ((3+0)*2+0)*1 = 6.
        let tk = tokenize("｜《》");
        assert_eq!(tk.size_hint(), (0, Some(7)));
        assert_eq!(triggers(&tk.collect::<Vec<_>>()).len(), 3);
    }

    #[test]
    fn trigger_span_covers_all_constituent_bytes() {
        let toks = collect("≪ab≫");
        let open_span = toks
            .iter()
            .find_map(|t| match t {
                Token::Trigger {
                    kind: TriggerKind::AngleQuoteOpen,
                    span,
                } => Some(*span),
                _ => None,
            })
            .expect("AngleQuoteOpen present");
        // Single ≪ → 3 bytes starting at 0.
        assert_eq!(open_span, Span::new(0, 3));
    }
}