guard-core-engine 4.2.0

//! Bounded scan windows ported from `guard_core/detection_engine/scan_window.py`
//! (spec 4.0.2).
//!
//! Several built-in detection patterns have the shape
//! `literal_prefix + unbounded_negated_class + terminator`. When the
//! terminator is absent, the regex engine rescans to end-of-input from every
//! prefix occurrence, which is quadratic in input length. This module locates
//! prefix and terminator occurrences with linear passes, then runs the
//! caller's UNMODIFIED pattern against a bounded span per prefix candidate:
//! from that candidate to the rightmost terminator occurrence reachable from
//! it. The pattern itself is never rewritten.

use regex::Regex;

use super::pyregex::{Candidate, PyRegex};

/// Python `pattern.match(text, start, end)`: anchored at `start`, the string
/// effectively truncated at `end`.
fn match_span(re: &Regex, haystack: &str, start: usize, end: usize) -> Option<Candidate> {
    if start > end {
        return None;
    }
    let truncated = &haystack[..end];
    let m = re.find_at(truncated, start)?;
    if m.start() != start {
        return None;
    }
    Some(Candidate::new(m.start(), m.end()))
}

#[must_use]
pub fn bounded_finditer(
    haystack: &str,
    compiled: &PyRegex,
    prefix: &PyRegex,
    terminator: &PyRegex,
) -> Vec<Candidate> {
    bounded_finditer_guarded(haystack, compiled, prefix, terminator, |_, _| true)
}

/// `bounded_finditer` with a per-candidate guard (the reference runs the
/// UNMODIFIED pattern inside the window; a guard failure abandons the prefix
/// candidate exactly like a failed window match).
#[must_use]
pub fn bounded_finditer_guarded(
    haystack: &str,
    compiled: &PyRegex,
    prefix: &PyRegex,
    terminator: &PyRegex,
    guard: impl Fn(&str, Candidate) -> bool,
) -> Vec<Candidate> {
    let terminator_ends: Vec<usize> = terminator
        .re()
        .find_iter(haystack)
        .map(|m| m.end())
        .collect();
    if terminator_ends.is_empty() {
        return Vec::new();
    }
    let ceiling = terminator_ends[terminator_ends.len() - 1];

    let prefix_starts: Vec<usize> = prefix.re().find_iter(haystack).map(|m| m.start()).collect();
    if prefix_starts.is_empty() {
        return Vec::new();
    }

    let mut matches = Vec::new();
    let mut search_from = 0;
    let mut start_index = 0;
    loop {
        while start_index < prefix_starts.len() && prefix_starts[start_index] < search_from {
            start_index += 1;
        }
        let mut found: Option<Candidate> = None;
        for (offset, &start) in prefix_starts.iter().enumerate().skip(start_index) {
            if start >= ceiling {
                break;
            }
            if let Some(m) = match_span(compiled.re(), haystack, start, ceiling)
                && guard(haystack, m)
            {
                start_index = offset;
                found = Some(m);
                break;
            }
        }
        let Some(m) = found else {
            return matches;
        };
        matches.push(m);
        search_from = if m.end > m.start { m.end } else { m.start + 1 };
    }
}

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

    #[test]
    fn finds_matches_inside_window() {
        let compiled = PyRegex::compile(r"<script[^>]*>[^<]*<\/script\s*>", false).unwrap();
        let prefix = PyRegex::compile("<script", false).unwrap();
        let terminator = PyRegex::compile(r"<\/script\s*>", false).unwrap();
        let text = "junk <script>a</script> tail <script>b</script>";
        let ms = bounded_finditer(text, &compiled, &prefix, &terminator);
        assert_eq!(ms.len(), 2);
        assert_eq!(ms[0].text(text), "<script>a</script>");
        assert_eq!(ms[1].text(text), "<script>b</script>");
    }

    #[test]
    fn no_terminator_no_match() {
        let compiled = PyRegex::compile(r"<script[^>]*>[^<]*<\/script\s*>", false).unwrap();
        let prefix = PyRegex::compile("<script", false).unwrap();
        let terminator = PyRegex::compile(r"<\/script\s*>", false).unwrap();
        assert!(bounded_finditer("<script>a", &compiled, &prefix, &terminator).is_empty());
    }
}