syntaxmate 0.2.0

pub(crate) mod analysis;
pub mod ast;
pub mod backtrack;
pub(crate) mod bytecode;
pub mod captures;
pub(crate) mod case_fold;
pub mod dfa;
pub mod prefilter;
pub(crate) mod scanner;
pub(crate) mod skip_prefix;
pub(crate) mod start_class;
pub mod translate;

use std::{
    ops::Range,
    sync::{
        Arc,
        atomic::{AtomicU64, Ordering},
    },
};

use unicode_general_category::{GeneralCategory, get_general_category};

static NEXT_COMPILED_PATTERN_ID: AtomicU64 = AtomicU64::new(1);

/// Oniguruma's Unicode `word` character set.
///
/// TextMate regex offsets are exposed as UTF-16 indices, but matching happens
/// on Unicode characters. Internally Syntaxmate keeps UTF-8 byte offsets, so all
/// regex engines must agree on the character predicate while preserving byte
/// boundaries. Rust's `char::is_alphanumeric` omits combining marks and
/// connector punctuation (notably emoji variation selectors), both of which
/// Oniguruma includes in `\w` and word-boundary checks.
pub(crate) fn is_unicode_word_char(ch: char) -> bool {
    if ch.is_ascii() {
        return ch == '_' || ch.is_ascii_alphanumeric();
    }
    matches!(
        get_general_category(ch),
        GeneralCategory::LowercaseLetter
            | GeneralCategory::ModifierLetter
            | GeneralCategory::OtherLetter
            | GeneralCategory::TitlecaseLetter
            | GeneralCategory::UppercaseLetter
            | GeneralCategory::EnclosingMark
            | GeneralCategory::NonspacingMark
            | GeneralCategory::SpacingMark
            | GeneralCategory::DecimalNumber
            | GeneralCategory::LetterNumber
            | GeneralCategory::OtherNumber
            | GeneralCategory::ConnectorPunctuation
    )
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct CompiledPatternId(u64);

pub use ast::{ParsedRegex, RegexFeatures, parse};
pub use backtrack::{FallbackError, FallbackMatcher, FallbackReport};
pub use dfa::{
    AutomataBuildError, AutomataMatcher, LiteralMatcher, PatternSetMatcher, SimpleMatcher,
};
pub use translate::{AnchorStrategy, Route, Translation, translate};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct AnchorContext {
    pub allow_a: bool,
    pub allow_g: bool,
    pub g_pos: usize,
}

impl AnchorContext {
    pub fn start_of_file() -> Self {
        Self {
            allow_a: true,
            allow_g: false,
            g_pos: 0,
        }
    }

    pub fn line_start() -> Self {
        Self {
            allow_a: false,
            allow_g: false,
            g_pos: 0,
        }
    }

    pub fn continuation(g_pos: usize) -> Self {
        Self {
            allow_a: false,
            allow_g: true,
            g_pos,
        }
    }
}

impl Default for AnchorContext {
    fn default() -> Self {
        Self::line_start()
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct MatchResult {
    pub start: usize,
    pub end: usize,
    pub captures: Vec<Option<Range<usize>>>,
}

impl MatchResult {
    /// Group zero is always the whole match. Candidate selection can therefore
    /// omit its heap-backed capture vector and synthesize group zero from the
    /// span; only nonzero live groups require capture replay.
    pub(crate) fn capture(&self, group: usize) -> Option<Range<usize>> {
        if group == 0 {
            return self
                .captures
                .first()
                .cloned()
                .flatten()
                .or(Some(self.start..self.end));
        }
        self.captures.get(group).cloned().flatten()
    }

    pub(crate) fn capture_count(&self) -> usize {
        self.captures.len().max(1)
    }
}

pub trait Matcher {
    fn find(&self, line: &str, from: usize, ctx: AnchorContext) -> Option<MatchResult>;
}

#[derive(Debug, Clone)]
pub enum RegexMatcher {
    Automata(Box<AutomataMatcher>),
    Fallback(Box<FallbackMatcher>),
}

impl RegexMatcher {
    pub fn new(pattern: &str) -> Self {
        let translation = translate(pattern);
        Self::from_translation(pattern, translation).0
    }

    /// Builds the matcher for a translation. An automata matcher retains the
    /// translation; otherwise its translated spelling is handed back so the
    /// caller can keep it without copying.
    fn from_translation(pattern: &str, translation: Translation) -> (Self, Option<String>) {
        if matches!(&translation.route, Route::Dfa) {
            return match AutomataMatcher::from_translation(translation) {
                Ok(matcher) => (Self::Automata(Box::new(matcher)), None),
                Err(_) => {
                    let translated = translate(pattern).pattern;
                    (
                        Self::Fallback(Box::new(FallbackMatcher::new(pattern))),
                        Some(translated),
                    )
                }
            };
        }
        match AutomataMatcher::from_specialized_translation(translation) {
            Ok(matcher) => (Self::Automata(Box::new(matcher)), None),
            Err(translation) => (
                Self::Fallback(Box::new(FallbackMatcher::from_parsed(
                    translation.parsed,
                    backtrack::DEFAULT_STEP_BUDGET,
                ))),
                Some(translation.pattern),
            ),
        }
    }

    fn unanchored_literal(&self) -> Option<&str> {
        match self {
            Self::Automata(matcher) => matcher.unanchored_literal(),
            Self::Fallback(_) => None,
        }
    }

    fn restricted_start_bytes(&self) -> Option<Vec<u8>> {
        match self {
            Self::Automata(matcher) => matcher.restricted_start_bytes(),
            Self::Fallback(matcher) => matcher.restricted_start_bytes(),
        }
    }

    pub fn engine_name(&self) -> &'static str {
        match self {
            Self::Automata(_) => "dfa",
            Self::Fallback(_) => "fallback",
        }
    }

    pub fn prefilter_may_match(&self, line: &str, from: usize) -> Option<bool> {
        match self {
            Self::Automata(matcher) => matcher.prefilter_may_match(line, from),
            Self::Fallback(matcher) => matcher.prefilter_may_match(line, from),
        }
    }

    pub fn find_report(
        &self,
        line: &str,
        from: usize,
        ctx: AnchorContext,
    ) -> Result<(Option<MatchResult>, Option<usize>), FallbackError> {
        match self {
            Self::Automata(matcher) => Ok((matcher.find(line, from, ctx), None)),
            Self::Fallback(matcher) => matcher
                .try_find(line, from, ctx)
                .map(|report| (report.result, Some(report.steps))),
        }
    }

    pub(crate) fn find_report_for_selection(
        &self,
        line: &str,
        from: usize,
        ctx: AnchorContext,
    ) -> Result<(Option<MatchResult>, Option<usize>), FallbackError> {
        match self {
            Self::Automata(matcher) => matcher.find_report_for_selection(line, from, ctx),
            Self::Fallback(matcher) => matcher
                .try_find_for_selection(line, from, ctx)
                .map(|report| (report.result, Some(report.steps))),
        }
    }

    pub(crate) fn find_report_at(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
    ) -> Result<(Option<MatchResult>, Option<usize>), FallbackError> {
        match self {
            Self::Automata(matcher) => matcher.find_report_at(line, start, ctx),
            Self::Fallback(matcher) => matcher
                .try_find_at(line, start, ctx)
                .map(|report| (report.result, Some(report.steps))),
        }
    }

    /// See [`FallbackMatcher::selection_prefilter_viable`]. Specialized
    /// native engines never consult the prefilter and always report `true`.
    pub(crate) fn selection_prefilter_viable(
        &self,
        line: &str,
        start: usize,
        scratch: &mut bytecode::BytecodeScratch,
    ) -> bool {
        match self {
            Self::Automata(matcher) => matcher.selection_prefilter_viable(line, start, scratch),
            Self::Fallback(matcher) => matcher.selection_prefilter_viable(line, start, scratch),
        }
    }

    pub(crate) fn find_at_for_selection_with_scratch(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
        materialize_specialized_captures: bool,
        scratch: &mut bytecode::BytecodeScratch,
    ) -> Result<Option<MatchResult>, FallbackError> {
        match self {
            Self::Automata(matcher) => matcher.find_at_for_selection_with_scratch(
                line,
                start,
                ctx,
                materialize_specialized_captures,
                scratch,
            ),
            Self::Fallback(matcher) => matcher
                .try_find_at_without_captures_with_scratch(line, start, ctx, scratch)
                .map(|report| report.result),
        }
    }
}

/// Immutable regex data shared by individual candidate matching and the
/// ordered multi-pattern selector. Construction parses the source exactly
/// once; candidate-set construction only clones an `Arc` to this object.
#[derive(Debug)]
pub struct CompiledPattern {
    id: CompiledPatternId,
    /// Present when `matcher` does not retain its translation.
    translated_pattern: Option<String>,
    matcher: RegexMatcher,
    unanchored_literal: Option<String>,
    restricted_start_bytes: Option<Vec<u8>>,
    /// Also owns the pattern source.
    parsed: Arc<ParsedRegex>,
    /// Empty when a fallback `matcher` owns the layout instead, so its lazily
    /// compiled selection program can double as the capture program.
    live_captures: Box<[u32]>,
    capture_program: std::sync::OnceLock<Option<Arc<bytecode::Program>>>,
}

impl CompiledPattern {
    pub fn new(pattern: &str) -> Self {
        let translation = translate(pattern);
        let live_captures = (0..=translation.parsed.capture_count).collect::<Vec<_>>();
        Self::from_translation_with_live_captures(pattern, translation, live_captures)
    }

    pub(crate) fn new_with_live_captures(pattern: &str, live_captures: Vec<u32>) -> Self {
        let translation = translate(pattern);
        Self::from_translation_with_live_captures(pattern, translation, live_captures)
    }

    fn from_translation_with_live_captures(
        pattern: &str,
        translation: Translation,
        live_captures: Vec<u32>,
    ) -> Self {
        let parsed = Arc::clone(&translation.parsed);
        debug_assert_eq!(parsed.source, pattern);
        let (mut matcher, translated_pattern) =
            RegexMatcher::from_translation(pattern, translation);
        let mut live_captures = live_captures.into_boxed_slice();
        if let RegexMatcher::Fallback(fallback) = &mut matcher {
            live_captures = fallback.share_capture_layout(live_captures);
        }
        let unanchored_literal = matcher.unanchored_literal().map(str::to_owned);
        let restricted_start_bytes = matcher.restricted_start_bytes();
        Self {
            id: CompiledPatternId(NEXT_COMPILED_PATTERN_ID.fetch_add(1, Ordering::Relaxed)),
            translated_pattern,
            matcher,
            unanchored_literal,
            restricted_start_bytes,
            parsed,
            live_captures,
            capture_program: std::sync::OnceLock::new(),
        }
    }

    pub fn source(&self) -> &str {
        &self.parsed.source
    }

    fn live_captures(&self) -> &[u32] {
        match &self.matcher {
            RegexMatcher::Fallback(matcher) => matcher
                .shared_capture_layout()
                .unwrap_or(&self.live_captures),
            RegexMatcher::Automata(_) => &self.live_captures,
        }
    }

    pub fn id(&self) -> CompiledPatternId {
        self.id
    }

    /// Conservative charge used when admitting a compiled matcher to a
    /// long-lived prepared-language cache. The parser, native matcher,
    /// prefilters, and lazily compiled capture program all retain structures
    /// proportional to the source. Charging their potential expansion up
    /// front keeps later capture-program initialization inside the same bound.
    pub(crate) fn prepared_retained_bytes(&self) -> usize {
        const FIXED_ALLOCATION_CHARGE: usize = 16 * 1024;
        const SOURCE_EXPANSION_CHARGE: usize = 256;

        std::mem::size_of::<Self>()
            .saturating_add(FIXED_ALLOCATION_CHARGE)
            .saturating_add(self.source().len().saturating_mul(SOURCE_EXPANSION_CHARGE))
            .saturating_add(
                self.live_captures()
                    .len()
                    .saturating_mul(std::mem::size_of::<u32>()),
            )
    }

    pub fn matcher(&self) -> &RegexMatcher {
        &self.matcher
    }

    pub(crate) fn translated_pattern(&self) -> &str {
        match (&self.translated_pattern, &self.matcher) {
            (Some(translated), _) => translated,
            (None, RegexMatcher::Automata(matcher)) => &matcher.translation().pattern,
            (None, RegexMatcher::Fallback(_)) => {
                unreachable!("fallback matchers keep their spelling")
            }
        }
    }

    pub(crate) fn unanchored_literal(&self) -> Option<&str> {
        self.unanchored_literal.as_deref()
    }

    pub(crate) fn restricted_start_bytes(&self) -> Option<&[u8]> {
        self.restricted_start_bytes.as_deref()
    }

    pub(crate) fn start_class_mask(&self) -> u8 {
        self.parsed.analysis().start_class_mask()
    }

    pub(crate) fn skip_gate(&self) -> Option<&skip_prefix::SkipGate> {
        self.parsed.analysis().skip_gate()
    }

    pub(crate) fn parsed(&self) -> &ParsedRegex {
        &self.parsed
    }

    pub(crate) fn analysis(&self) -> &analysis::RegexAnalysis {
        self.parsed.analysis()
    }

    pub(crate) fn needs_capture_replay_after_selection(&self) -> bool {
        self.live_captures().iter().any(|group| *group != 0)
    }

    pub(crate) fn has_live_captures(&self, requested: Option<&[u32]>) -> bool {
        match requested {
            Some(requested) => self.live_captures() == requested,
            None => {
                let live = self.live_captures();
                live.len() == self.parsed.capture_count as usize + 1
                    && live.iter().copied().eq(0..=self.parsed.capture_count)
            }
        }
    }

    pub(crate) fn has_same_live_captures(&self, other: &Self) -> bool {
        self.live_captures() == other.live_captures()
    }

    pub(crate) fn find_live_captures_at_into(
        &self,
        line: &str,
        start: usize,
        ctx: AnchorContext,
        scratch: &mut bytecode::BytecodeScratch,
        capture_buffer: &mut Vec<Option<Range<usize>>>,
    ) -> Option<Result<(Option<MatchResult>, usize), FallbackError>> {
        use backtrack::{PositionEngineMode, StepBudget};

        if backtrack::capture_engine_mode() == PositionEngineMode::Recursive {
            return None;
        }
        let program = self
            .capture_program
            .get_or_init(|| {
                if let RegexMatcher::Fallback(matcher) = &self.matcher
                    && let Some(program) = matcher.shared_capture_program()
                {
                    return Some(program);
                }
                bytecode::Program::compile_captures_with_analysis(
                    &self.parsed,
                    self.parsed.analysis(),
                    self.live_captures(),
                )
                .ok()
                .map(Arc::new)
            })
            .as_deref()?;
        let mut budget = StepBudget::new(backtrack::DEFAULT_STEP_BUDGET);
        let end = match program.execute_capture_slots(line, start, ctx, &mut budget, scratch) {
            Ok(result) => result,
            Err(_) => {
                return Some(Err(FallbackError::BudgetExceeded {
                    steps: budget.used(),
                }));
            }
        };
        let result = end.map(|end| {
            capture_buffer.resize(self.parsed.capture_count as usize + 1, None);
            program.copy_capture_slots_into(start, end, scratch, capture_buffer);
            MatchResult {
                start,
                end,
                captures: std::mem::take(capture_buffer),
            }
        });
        Some(Ok((result, budget.used())))
    }
}

impl Matcher for RegexMatcher {
    fn find(&self, line: &str, from: usize, ctx: AnchorContext) -> Option<MatchResult> {
        match self {
            Self::Automata(matcher) => matcher.find(line, from, ctx),
            Self::Fallback(matcher) => matcher.find(line, from, ctx),
        }
    }
}

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

    #[test]
    fn routes_matcher() {
        assert_eq!(RegexMatcher::new("foo").engine_name(), "dfa");
        assert_eq!(RegexMatcher::new(r"foo(?=bar)").engine_name(), "fallback");
    }

    #[test]
    fn oniguruma_word_captures_keep_utf8_ranges_after_astral_characters() {
        let line = "🛰\u{fe0f}‿z";
        let matched = RegexMatcher::new(r"(🛰)(\w+)")
            .find(line, 0, AnchorContext::line_start())
            .expect("variation selector, connector punctuation, and letter are word chars");

        // vscode-oniguruma exposes these as UTF-16 0..2, 2..5. Syntaxmate's public
        // tokenizer contract is UTF-8 bytes, including all capture ranges.
        assert_eq!(matched.start..matched.end, 0..line.len());
        assert_eq!(matched.captures[0], Some(0..line.len()));
        assert_eq!(matched.captures[1], Some(0.."🛰".len()));
        assert_eq!(matched.captures[2], Some("🛰".len()..line.len()));
    }

    #[test]
    fn fallback_selection_program_doubles_as_capture_program() {
        fn replay(pattern: &CompiledPattern, line: &str, start: usize) -> MatchResult {
            let mut scratch = bytecode::BytecodeScratch::default();
            let mut captures = Vec::new();
            let (result, _) = pattern
                .find_live_captures_at_into(
                    line,
                    start,
                    AnchorContext::line_start(),
                    &mut scratch,
                    &mut captures,
                )
                .expect("bytecode capture replay")
                .expect("within budget");
            result.expect("pattern matches")
        }

        // Replayed groups outside choice points share one compiled program.
        let shared = CompiledPattern::new_with_live_captures(
            r"(&)(?=[a-z])(amp|lt|gt|quot|nbsp)(;)",
            vec![0, 1, 2, 3],
        );
        let RegexMatcher::Fallback(matcher) = shared.matcher() else {
            panic!("lookahead should route to the fallback matcher");
        };
        assert_eq!(
            replay(&shared, "x &lt; y", 2).captures,
            vec![Some(2..6), Some(2..3), Some(3..5), Some(5..6)]
        );
        let selection = matcher
            .shared_capture_program()
            .expect("selection program carries the live capture slots");
        let replayed = shared.capture_program.get().cloned().flatten();
        assert!(replayed.is_some_and(|program| Arc::ptr_eq(&program, &selection)));
        assert!(shared.has_live_captures(Some(&[0, 1, 2, 3])));

        // A replayed group under an alternation would block the selection
        // trie, so capture replay keeps its own program.
        let separate =
            CompiledPattern::new_with_live_captures(r"(?:(amp)|lt|gt|quot)(?=;)", vec![0, 1]);
        let RegexMatcher::Fallback(matcher) = separate.matcher() else {
            panic!("lookahead should route to the fallback matcher");
        };
        assert!(matcher.shared_capture_program().is_none());
        assert_eq!(
            replay(&separate, "amp;", 0).captures,
            vec![Some(0..3), Some(0..3)]
        );

        // Subroutine calls write the called group's capture on the shared
        // program's explicit call stack.
        let called = CompiledPattern::new_with_live_captures(r"(?<n>a|b)x\g<n>(?=;)", vec![0, 1]);
        let RegexMatcher::Fallback(matcher) = called.matcher() else {
            panic!("lookahead should route to the fallback matcher");
        };
        assert!(matcher.shared_capture_program().is_some());
        assert_eq!(
            replay(&called, "axb;", 0).captures,
            vec![Some(0..3), Some(2..3)]
        );
    }

    #[test]
    fn dfa_route_matches_nested_class_intersections() {
        let matcher = RegexMatcher::new(r"[a-z&&[^aeiou]]+");
        assert_eq!(matcher.engine_name(), "dfa");
        let matched = matcher
            .find("aei-bcdf", 0, AnchorContext::line_start())
            .expect("consonants should match");
        assert_eq!(matched.start..matched.end, 4..8);
    }

    #[test]
    fn dfa_route_literal_is_simple() {
        match RegexMatcher::new("keyword") {
            RegexMatcher::Automata(matcher) => assert!(matcher.is_simple()),
            RegexMatcher::Fallback(_) => panic!("expected dfa route"),
        }
    }

    #[test]
    fn all_core_fixture_regexes_are_routed() {
        use crate::engine::grammar::load_dev_grammar_from_str;
        use crate::engine::state::GrammarId;
        use crate::grammars::registry::CORE_ASSETS;

        let mut total = 0usize;
        let mut fallback = 0usize;
        for (index, asset) in CORE_ASSETS.iter().enumerate() {
            let grammar = load_dev_grammar_from_str(GrammarId(index as u16), asset.source)
                .unwrap_or_else(|error| panic!("{} grammar should parse: {error}", asset.language));
            for pattern in &grammar.patterns {
                total += 1;
                let translation = translate(pattern);
                if let Route::Fallback { reasons } = translation.route {
                    fallback += 1;
                    assert!(
                        !reasons.is_empty(),
                        "{} pattern {pattern:?} routed to fallback without reason",
                        asset.language
                    );
                }
            }
        }
        assert!(total > 0);
        assert!(fallback > 0);
    }
}