rustik-highlight 0.1.0

//! Pattern compilation and matching for TextMate grammars.
//!
//! Raw TextMate patterns compile into a tree of [`Pattern`] values grouped into
//! [`PatternSet`]s. Each set keeps a combined Oniguruma [`RegSet`] so that
//! finding the next match in a line is one regex search regardless of how many
//! patterns share that nesting level. Begin/end rules carry their end pattern
//! on the same node; static end patterns are precompiled, while dynamic ones
//! are resolved against the begin match the first time they are needed and
//! cached for subsequent lines.

use super::end::{EndPattern, EndRegex, EndRegexCache};
use super::*;

/// Capture-group index → interned scope id mapping.
pub(super) type Captures = BTreeMap<usize, ScopeId>;

/// A scope assigned by a pattern.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(super) enum Scope {
    /// Pattern names no scope.
    None,
    /// Pattern names a visible scope that emits spans.
    Visible(ScopeId),
    /// Pattern names a structural scope used only to hold parser state.
    Structural(ScopeId),
}

/// Capture-scope mappings for a pattern's three regex slots.
#[derive(Debug, Default)]
pub(super) struct PatternCaptures {
    /// Captures applied to a single match rule.
    pub(super) matched: Captures,
    /// Captures applied to a begin-match rule.
    pub(super) begin: Captures,
    /// Captures applied to an end-match rule.
    pub(super) end: Captures,
}

/// Match form used by a compiled pattern.
#[derive(Debug)]
enum PatternBody {
    /// Single regex match rule.
    Match {
        /// Regex source.
        source: String,
    },
    /// Stateful begin/end rule.
    BeginEnd {
        /// Begin regex source (also the entry inside the parent set's RegSet).
        begin_source: String,
        /// End regex (compiled now or deferred until begin captures are known).
        end: EndPattern,
    },
}

/// Compiled patterns at one nesting level plus their combined search regex.
#[derive(Debug)]
pub(super) struct PatternSet {
    /// Patterns in declaration order.
    patterns: Vec<Pattern>,
    /// Combined RegSet covering each pattern's match or begin source.
    regexes: Option<RegSet>,
}

/// Result of compiling one raw pattern.
enum Compiled {
    /// Pattern compiled to a single rule and should be added to the parent set.
    Rule(Pattern),
    /// Pattern was a grouping (no match/begin-end of its own); its nested patterns
    /// should be inlined directly into the parent set.
    Inline(Vec<Pattern>),
    /// Pattern was malformed and should be ignored.
    Skip,
}

/// One compiled TextMate pattern with its scope, captures, and nested rules.
///
/// A [`Pattern`] is what the grammar tokenizer matches against the source text.
/// One match produces a [`Match`] (the higher-level result with emitted spans),
/// which wraps the underlying [`RegexMatch`] (raw capture positions).
#[derive(Debug)]
pub(super) struct Pattern {
    /// Stable rule id used to reopen this pattern from line state.
    id: usize,
    /// Scope assigned by this pattern.
    pub(super) scope: Scope,
    /// Per-slot capture-scope mappings.
    pub(super) captures: PatternCaptures,
    /// Match form (single match or begin/end pair).
    body: PatternBody,
    /// Patterns that may match inside this one.
    pub(super) nested: PatternSet,
}

/// Begin/end rule pushed onto the parser stack and held across line boundaries.
///
/// The matching [`Pattern`] is recovered through `Grammar::pattern_by_rule`, so
/// the open rule itself only stores what cannot be derived from the grammar:
/// the rule's id and the resolved end-regex source for dynamic end patterns.
#[derive(Clone, Debug, Eq, PartialEq)]
pub(super) struct OpenRule {
    /// Compiled rule id.
    pub(super) rule_id: usize,
    /// Resolved end-regex source (populated only for dynamic end patterns).
    pub(super) dynamic_end: Option<String>,
}

/// Result of one pattern matching in a line: the byte range it covered, the
/// scope spans it emitted, and any begin/end rule it pushed onto the stack.
pub(super) struct Match {
    /// Start byte of the match in the line.
    pub(super) start: usize,
    /// End byte of the match (or of the same-line close, for begin/end rules).
    end: usize,
    /// Scope spans emitted by the match and its captures.
    pub(super) spans: Vec<ScopeSpan>,
    /// New rule pushed onto the parser stack, when this match opened one.
    open_rule: Option<OpenRule>,
}

/// Raw regex hit: byte range plus the positions of any retained capture groups.
pub(super) struct RegexMatch {
    /// Start byte of the full regex match.
    pub(super) start: usize,
    /// End byte of the full regex match.
    end: usize,
    /// Byte ranges for capture groups by capture index, when captures were retained.
    captures: Vec<Option<(usize, usize)>>,
}

/// Builder-time table that assigns stable ids to scope names.
#[derive(Default)]
pub(super) struct ScopeInterner {
    /// Interned scope names in id order.
    pub(super) scopes: Vec<String>,
    /// Lookup table from scope name to interned id.
    ids: BTreeMap<String, ScopeId>,
}

/// End match found before any nested match on the current line.
struct EndOnLine {
    /// The regex match that closed the rule.
    matched: RegexMatch,
    /// Spans emitted by nested patterns scanned while looking for the end.
    spans: Vec<ScopeSpan>,
}

impl Scope {
    /// Builds a scope from an optional raw TextMate name.
    fn from_raw(name: Option<&str>, interner: &mut ScopeInterner) -> Self {
        let Some(name) = name else { return Self::None };
        let id = interner.intern(name);
        if name.starts_with("meta.structure.") {
            Self::Structural(id)
        } else {
            Self::Visible(id)
        }
    }

    /// Returns the interned scope id, regardless of visibility.
    pub(super) fn id(self) -> Option<ScopeId> {
        match self {
            Self::None => None,
            Self::Visible(id) | Self::Structural(id) => Some(id),
        }
    }

    /// Pushes a span for this scope's region when it is visible and non-empty.
    pub(super) fn push_visible(self, spans: &mut Vec<ScopeSpan>, start: usize, end: usize) {
        if let Self::Visible(scope) = self
            && start < end
        {
            spans.push(ScopeSpan { start, end, scope });
        }
    }
}

impl ScopeInterner {
    /// Returns the id for a scope, inserting it when needed.
    fn intern(&mut self, scope: &str) -> ScopeId {
        if let Some(id) = self.ids.get(scope) {
            return *id;
        }
        let id = ScopeId::new(self.scopes.len());
        self.scopes.push(scope.to_owned());
        self.ids.insert(scope.to_owned(), id);
        id
    }

    /// Converts raw capture maps into interned capture scopes.
    fn captures(&mut self, raw: Option<&BTreeMap<String, RawCapture>>) -> Captures {
        raw.into_iter()
            .flat_map(BTreeMap::iter)
            .filter_map(|(index, capture)| {
                let index = index.parse().ok()?;
                let name = capture.name.as_ref()?;
                let scope = self.intern(name);
                Some((index, scope))
            })
            .collect()
    }
}

impl PatternSet {
    /// Creates an empty pattern set.
    pub(super) fn empty() -> Self {
        Self {
            patterns: Vec::new(),
            regexes: None,
        }
    }

    /// Compiles raw TextMate patterns into a regex-searchable pattern set.
    pub(super) fn compile(
        raw: &RawGrammar,
        patterns: &[RawPattern],
        next_rule: &mut usize,
        depth: usize,
        interner: &mut ScopeInterner,
    ) -> Result<Self, Error> {
        if depth > MAX_INCLUDE_DEPTH {
            return Ok(Self::empty());
        }
        let mut compiled = Vec::new();
        for pattern in patterns {
            if let Some(include) = &pattern.include {
                let expanded = expand_include(raw, include, next_rule, depth, interner)?;
                compiled.extend(expanded);
                continue;
            }
            match Pattern::compile(raw, pattern, next_rule, depth, interner)? {
                Compiled::Rule(pattern) => compiled.push(pattern),
                Compiled::Inline(patterns) => compiled.extend(patterns),
                Compiled::Skip => {}
            }
        }
        Ok(Self::new(compiled))
    }

    /// Builds a pattern set and its combined regex search set.
    fn new(patterns: Vec<Pattern>) -> Self {
        let sources: Vec<&str> = patterns.iter().map(Pattern::search_source).collect();
        let regexes = (!sources.is_empty())
            .then(|| RegSet::new(&sources).ok())
            .flatten();

        Self { patterns, regexes }
    }

    /// Walks the rule tree to collect index paths from rule ids back to patterns.
    pub(super) fn collect_rule_paths(&self, total_rules: usize) -> Vec<Box<[usize]>> {
        let mut paths = vec![Box::default(); total_rules];
        let mut current = Vec::new();
        self.fill_rule_paths(&mut current, &mut paths);
        paths
    }

    /// Recursively fills `paths[rule_id]` with the index path to that pattern.
    fn fill_rule_paths(&self, current: &mut Vec<usize>, paths: &mut [Box<[usize]>]) {
        for (index, pattern) in self.patterns.iter().enumerate() {
            current.push(index);
            if let Some(slot) = paths.get_mut(pattern.id) {
                *slot = current.as_slice().into();
            }
            pattern.nested.fill_rule_paths(current, paths);
            current.pop();
        }
    }

    /// Returns a nested compiled pattern by index path.
    pub(super) fn pattern_at(&self, path: &[usize]) -> Option<&Pattern> {
        let (last, rest) = path.split_last()?;
        let mut current = self;
        for &index in rest {
            current = &current.patterns.get(index)?.nested;
        }
        current.patterns.get(*last)
    }

    /// Finds the next pattern match at or after `pos`.
    pub(super) fn find_next(
        &self,
        line: &str,
        pos: usize,
        cache: &mut EndRegexCache,
    ) -> Option<Match> {
        if pos > line.len() || !line.is_char_boundary(pos) {
            return None;
        }
        let regexes = self.regexes.as_ref()?;
        let (entry, captures) = regexes.captures_with_options(
            line,
            pos,
            line.len(),
            RegSetLead::Position,
            SearchOptions::SEARCH_OPTION_NONE,
        )?;
        let pattern = self.patterns.get(entry)?;
        let regex_match = RegexMatch::from_captures(captures, pattern.needs_match_captures())?;

        pattern.match_result(regex_match, line, cache)
    }
}

/// Expands a single include directive into compiled patterns.
fn expand_include(
    raw: &RawGrammar,
    include: &str,
    next_rule: &mut usize,
    depth: usize,
    interner: &mut ScopeInterner,
) -> Result<Vec<Pattern>, Error> {
    // `$base` should reference the outermost grammar across cross-grammar
    // includes, but the registry does not yet support that, so it is
    // collapsed to `$self` (the current grammar's root patterns).
    if include == "$self" || include == "$base" {
        let set = PatternSet::compile(raw, &raw.patterns, next_rule, depth + 1, interner)?;
        return Ok(set.patterns);
    }
    let Some(name) = include.strip_prefix('#') else {
        return Ok(Vec::new());
    };
    let Some(pattern) = raw
        .repository
        .as_ref()
        .and_then(|repository| repository.get(name))
    else {
        return Ok(Vec::new());
    };
    let set = PatternSet::compile(
        raw,
        std::slice::from_ref(pattern),
        next_rule,
        depth + 1,
        interner,
    )?;
    Ok(set.patterns)
}

impl Pattern {
    /// Compiles one raw pattern.
    ///
    /// Returns [`Compiled::Inline`] for grouping patterns (no match/begin-end of
    /// their own) so the parent set absorbs their nested patterns rather than
    /// keeping a placeholder node.
    fn compile(
        raw: &RawGrammar,
        pattern: &RawPattern,
        next_rule: &mut usize,
        depth: usize,
        interner: &mut ScopeInterner,
    ) -> Result<Compiled, Error> {
        let scope = Scope::from_raw(pattern.name.as_deref(), interner);
        let nested = PatternSet::compile(
            raw,
            pattern.patterns.as_deref().unwrap_or_default(),
            next_rule,
            depth + 1,
            interner,
        )?;

        let body = match (&pattern.match_rule, &pattern.begin, &pattern.end) {
            (Some(source), _, _) => {
                if Regex::new(source).is_err() {
                    return Ok(Compiled::Skip);
                }
                PatternBody::Match {
                    source: source.clone(),
                }
            }
            (None, Some(begin), Some(end)) => {
                if Regex::new(begin).is_err() {
                    return Ok(Compiled::Skip);
                }
                let Some(end) = EndPattern::compile(end) else {
                    return Ok(Compiled::Skip);
                };
                PatternBody::BeginEnd {
                    begin_source: begin.clone(),
                    end,
                }
            }
            _ => return Ok(Compiled::Inline(nested.patterns)),
        };
        let id = *next_rule;
        *next_rule += 1;

        Ok(Compiled::Rule(Self {
            id,
            scope,
            captures: PatternCaptures {
                matched: interner.captures(pattern.captures.as_ref()),
                begin: interner.captures(pattern.begin_captures.as_ref()),
                end: interner.captures(pattern.end_captures.as_ref()),
            },
            body,
            nested,
        }))
    }

    /// Returns the active end regex when reopening this pattern from line state.
    pub(super) fn resume_end<'pat>(
        &'pat self,
        dynamic_end: Option<&str>,
        cache: &mut EndRegexCache,
    ) -> Option<EndRegex<'pat>> {
        let PatternBody::BeginEnd { end, .. } = &self.body else {
            return None;
        };
        end.resume(dynamic_end, cache)
    }

    /// Adds capture-group spans plus the pattern's own scope span for one regex match.
    pub(super) fn append_match_spans(
        &self,
        matched: &RegexMatch,
        captures: &Captures,
        spans: &mut Vec<ScopeSpan>,
    ) {
        for (index, scope) in captures {
            if let Some(Some((start, end))) = matched.captures.get(*index)
                && start < end
            {
                spans.push(ScopeSpan {
                    start: *start,
                    end: *end,
                    scope: *scope,
                });
            }
        }
        if let Some(scope) = self.scope.id() {
            spans.push(ScopeSpan {
                start: matched.start,
                end: matched.end,
                scope,
            });
        }
        spans.sort_by_key(|span| (span.start, span.end));
    }

    /// Whether match-time regex captures must be retained.
    fn needs_match_captures(&self) -> bool {
        match &self.body {
            PatternBody::Match { .. } => !self.captures.matched.is_empty(),
            PatternBody::BeginEnd { end, .. } => {
                !self.captures.begin.is_empty() || end.is_dynamic()
            }
        }
    }

    /// The regex source used in the parent set's combined `RegSet`.
    fn search_source(&self) -> &str {
        match &self.body {
            PatternBody::Match { source } => source,
            PatternBody::BeginEnd { begin_source, .. } => begin_source,
        }
    }

    /// Builds a [`Match`] for one regex hit, dispatching by body kind.
    fn match_result(
        &self,
        regex_match: RegexMatch,
        line: &str,
        cache: &mut EndRegexCache,
    ) -> Option<Match> {
        match &self.body {
            PatternBody::Match { .. } => Some(self.simple_match(regex_match)),
            PatternBody::BeginEnd { end, .. } => self.begin_match(end, regex_match, line, cache),
        }
    }

    /// Builds a match for a single-line match rule.
    fn simple_match(&self, regex_match: RegexMatch) -> Match {
        let mut spans = Vec::new();
        self.append_match_spans(&regex_match, &self.captures.matched, &mut spans);
        Match {
            start: regex_match.start,
            end: regex_match.end,
            spans,
            open_rule: None,
        }
    }

    /// Builds a match for a begin/end rule, eagerly closing on the same line if possible.
    fn begin_match(
        &self,
        end_pattern: &EndPattern,
        begin: RegexMatch,
        line: &str,
        cache: &mut EndRegexCache,
    ) -> Option<Match> {
        let end_regex = end_pattern.resolve_for_begin(&begin, line, cache)?;
        let dynamic_end = end_regex.dynamic_source();
        let same_line_end = self.find_same_line_end(&end_regex, line, begin.end, cache);

        let mut spans = Vec::new();
        self.append_match_spans(&begin, &self.captures.begin, &mut spans);

        let (end_byte, open_rule) = if let Some(close) = &same_line_end {
            self.scope
                .push_visible(&mut spans, begin.end, close.matched.start);
            spans.extend(close.spans.iter().copied());
            self.append_match_spans(&close.matched, &self.captures.end, &mut spans);
            (close.matched.end, None)
        } else {
            // The begin region is already covered by `append_match_spans` above;
            // the rest of the line is emitted by the tokenizer once this rule
            // is pushed and the next event is handled inside it.
            (
                begin.end,
                Some(OpenRule {
                    rule_id: self.id,
                    dynamic_end,
                }),
            )
        };

        Some(Match {
            start: begin.start,
            end: end_byte,
            spans,
            open_rule,
        })
    }

    /// Finds the first end match on the line, scanning past nested matches that occur before it.
    fn find_same_line_end(
        &self,
        end: &EndRegex<'_>,
        line: &str,
        mut pos: usize,
        cache: &mut EndRegexCache,
    ) -> Option<EndOnLine> {
        let end_regex = end.regex();
        let end_source = end.source();
        let capture_end = !self.captures.end.is_empty();
        let mut spans = Vec::new();
        loop {
            let matched = RegexMatch::find(end_regex, line, pos, capture_end)?;
            // Skip escaped quote-character ends — only `"` and `'` are handled.
            // Other end-pattern shapes are matched literally without escape awareness.
            if is_simple_quote(end_source) && is_escaped_at(line, matched.start) {
                pos = matched.next_pos(line);
                continue;
            }
            let nested_match = self.nested.find_next(line, pos, cache);
            let Some(nested_match) = nested_match else {
                return Some(EndOnLine { matched, spans });
            };
            if nested_match.start >= matched.start {
                return Some(EndOnLine { matched, spans });
            }
            pos = nested_match.next_pos(line);
            spans.extend(nested_match.spans);
        }
    }
}

/// Whether `source` is a single literal quote pattern.
fn is_simple_quote(source: &str) -> bool {
    matches!(source, "\"" | "'")
}

/// Whether the byte at `pos` is preceded by an odd number of backslashes.
fn is_escaped_at(line: &str, pos: usize) -> bool {
    if pos > line.len() || !line.is_char_boundary(pos) {
        return false;
    }
    line[..pos]
        .bytes()
        .rev()
        .take_while(|byte| *byte == b'\\')
        .count()
        % 2
        == 1
}

impl Match {
    /// Returns the next byte position after this match, ensuring forward progress.
    pub(super) fn next_pos(&self, line: &str) -> usize {
        next_pos_after(line, self.start, self.end)
    }

    /// Returns the open rule pushed onto the parser stack by this match, if any.
    pub(super) fn open_rule(&self) -> Option<OpenRule> {
        self.open_rule.clone()
    }
}

impl RegexMatch {
    /// Finds one regex match starting at `pos`.
    pub(super) fn find(regex: &Regex, line: &str, pos: usize, keep_captures: bool) -> Option<Self> {
        if pos > line.len() || !line.is_char_boundary(pos) {
            return None;
        }
        let mut region = Region::new();
        let _ = regex.search_with_options(
            line,
            pos,
            line.len(),
            SearchOptions::SEARCH_OPTION_NONE,
            Some(&mut region),
        )?;
        let (start, end) = region.pos(0)?;
        if start > end || end > line.len() {
            return None;
        }
        let captures = if keep_captures {
            (0..region.len())
                .map(|index| {
                    region.pos(index).and_then(|(start, end)| {
                        (start <= end && end <= line.len()).then_some((start, end))
                    })
                })
                .collect()
        } else {
            Vec::new()
        };
        Some(Self {
            start,
            end,
            captures,
        })
    }

    /// Builds a match record from Oniguruma captures.
    fn from_captures(captures: onig::Captures<'_>, keep_captures: bool) -> Option<Self> {
        let (start, end) = captures.pos(0)?;
        let captures = if keep_captures {
            (0..captures.len())
                .map(|index| captures.pos(index))
                .collect()
        } else {
            Vec::new()
        };
        Some(Self {
            start,
            end,
            captures,
        })
    }

    /// Returns the next byte position after this regex match.
    pub(super) fn next_pos(&self, line: &str) -> usize {
        next_pos_after(line, self.start, self.end)
    }

    /// Returns the captured text for one group, or `None` when the group is unset.
    pub(super) fn capture_text<'a>(&self, index: usize, line: &'a str) -> Option<&'a str> {
        let (start, end) = self.captures.get(index)?.as_ref().copied()?;
        line.get(start..end)
    }

    /// Substitutes this match's captures into a regex template containing
    /// backslash-prefixed numeric backreferences (`\1`, `\2`, …).
    ///
    /// Captured text is regex-escaped before substitution so that metacharacters
    /// in the source line are matched literally on the next invocation.
    pub(super) fn expand_backrefs(&self, template: &str, line: &str) -> String {
        let mut resolved = String::new();
        let mut chars = template.chars();
        while let Some(ch) = chars.next() {
            if ch != '\\' {
                resolved.push(ch);
                continue;
            }
            let Some(next) = chars.next() else {
                resolved.push(ch);
                break;
            };
            if let Some(index) = next.to_digit(10)
                && let Some(text) = self.capture_text(index as usize, line)
            {
                push_regex_escaped(&mut resolved, text);
            } else {
                resolved.push(ch);
                resolved.push(next);
            }
        }
        resolved
    }
}

/// Appends `input` to `out`, escaping any regex metacharacters.
fn push_regex_escaped(out: &mut String, input: &str) {
    const META: &[char] = &[
        '\\', '.', '+', '*', '?', '(', ')', '|', '[', ']', '{', '}', '^', '$',
    ];
    for ch in input.chars() {
        if META.contains(&ch) {
            out.push('\\');
        }
        out.push(ch);
    }
}

/// Returns a forward-progress position after a possibly-empty regex match.
fn next_pos_after(line: &str, start: usize, end: usize) -> usize {
    if end > start {
        end
    } else {
        next_char_boundary(line, start.saturating_add(1))
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod tests {
    use std::str::FromStr;

    use super::*;

    #[test]
    fn invalid_regex_offsets_are_ignored() {
        let regex = Regex::new("\"").unwrap();

        assert!(RegexMatch::find(&regex, r#"      "patterns": ["#, usize::MAX, true).is_none());
        assert!(RegexMatch::find(&regex, "é", 1, true).is_none());
    }

    #[test]
    fn regex_match_offsets_are_absolute_after_full_line_search() {
        let regex = Regex::new("(bar)").unwrap();
        let matched = RegexMatch::find(&regex, "foobar", 3, true).unwrap();

        assert_eq!(matched.start, 3);
        assert_eq!(matched.end, 6);
        assert_eq!(matched.captures[1], Some((3, 6)));
    }

    #[test]
    fn line_tokenizer_caches_dynamic_end_regexes() {
        let grammar = Grammar::from_str(
            r#"{
                "name":"Demo",
                "scopeName":"source.demo",
                "patterns":[
                    {
                        "begin":"<([A-Za-z.]+)>",
                        "end":"</\\1>",
                        "name":"meta.tag.demo"
                    }
                ],
                "repository":{}
            }"#,
        )
        .unwrap();
        let mut tokenizer = LineTokenizer::new(&grammar);
        let mut state = LineState::default();
        let mut spans = Vec::new();

        tokenizer.tokenize_line_into(&mut state, "<foo.bar>", &mut spans);
        assert_eq!(tokenizer.end_regex_cache_len(), 1);

        tokenizer.tokenize_line_into(&mut state, "body", &mut spans);
        assert_eq!(tokenizer.end_regex_cache_len(), 1);

        tokenizer.tokenize_line_into(&mut state, "</foo.bar>", &mut spans);
        assert!(state.is_empty());
        assert_eq!(tokenizer.end_regex_cache_len(), 1);
    }
}