guard_core_engine/patterns/
scan_window.rs

1//! Bounded scan windows ported from `guard_core/detection_engine/scan_window.py`
2//! (spec 4.0.2).
3//!
4//! Several built-in detection patterns have the shape
5//! `literal_prefix + unbounded_negated_class + terminator`. When the
6//! terminator is absent, the regex engine rescans to end-of-input from every
7//! prefix occurrence, which is quadratic in input length. This module locates
8//! prefix and terminator occurrences with linear passes, then runs the
9//! caller's UNMODIFIED pattern against a bounded span per prefix candidate:
10//! from that candidate to the rightmost terminator occurrence reachable from
11//! it. The pattern itself is never rewritten.
12
13use regex::Regex;
14
15use super::pyregex::{Candidate, PyRegex};
16
17/// Python `pattern.match(text, start, end)`: anchored at `start`, the string
18/// effectively truncated at `end`.
19fn match_span(re: &Regex, haystack: &str, start: usize, end: usize) -> Option<Candidate> {
20    if start > end {
21        return None;
22    }
23    let truncated = &haystack[..end];
24    let m = re.find_at(truncated, start)?;
25    if m.start() != start {
26        return None;
27    }
28    Some(Candidate::new(m.start(), m.end()))
29}
30
31#[must_use]
32pub fn bounded_finditer(
33    haystack: &str,
34    compiled: &PyRegex,
35    prefix: &PyRegex,
36    terminator: &PyRegex,
37) -> Vec<Candidate> {
38    bounded_finditer_guarded(haystack, compiled, prefix, terminator, |_, _| true)
39}
40
41/// `bounded_finditer` with a per-candidate guard (the reference runs the
42/// UNMODIFIED pattern inside the window; a guard failure abandons the prefix
43/// candidate exactly like a failed window match).
44#[must_use]
45pub fn bounded_finditer_guarded(
46    haystack: &str,
47    compiled: &PyRegex,
48    prefix: &PyRegex,
49    terminator: &PyRegex,
50    guard: impl Fn(&str, Candidate) -> bool,
51) -> Vec<Candidate> {
52    let terminator_ends: Vec<usize> = terminator
53        .re()
54        .find_iter(haystack)
55        .map(|m| m.end())
56        .collect();
57    if terminator_ends.is_empty() {
58        return Vec::new();
59    }
60    let ceiling = terminator_ends[terminator_ends.len() - 1];
61
62    let prefix_starts: Vec<usize> = prefix.re().find_iter(haystack).map(|m| m.start()).collect();
63    if prefix_starts.is_empty() {
64        return Vec::new();
65    }
66
67    let mut matches = Vec::new();
68    let mut search_from = 0;
69    let mut start_index = 0;
70    loop {
71        while start_index < prefix_starts.len() && prefix_starts[start_index] < search_from {
72            start_index += 1;
73        }
74        let mut found: Option<Candidate> = None;
75        for (offset, &start) in prefix_starts.iter().enumerate().skip(start_index) {
76            if start >= ceiling {
77                break;
78            }
79            if let Some(m) = match_span(compiled.re(), haystack, start, ceiling)
80                && guard(haystack, m)
81            {
82                start_index = offset;
83                found = Some(m);
84                break;
85            }
86        }
87        let Some(m) = found else {
88            return matches;
89        };
90        matches.push(m);
91        search_from = if m.end > m.start { m.end } else { m.start + 1 };
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn finds_matches_inside_window() {
101        let compiled = PyRegex::compile(r"<script[^>]*>[^<]*<\/script\s*>", false).unwrap();
102        let prefix = PyRegex::compile("<script", false).unwrap();
103        let terminator = PyRegex::compile(r"<\/script\s*>", false).unwrap();
104        let text = "junk <script>a</script> tail <script>b</script>";
105        let ms = bounded_finditer(text, &compiled, &prefix, &terminator);
106        assert_eq!(ms.len(), 2);
107        assert_eq!(ms[0].text(text), "<script>a</script>");
108        assert_eq!(ms[1].text(text), "<script>b</script>");
109    }
110
111    #[test]
112    fn no_terminator_no_match() {
113        let compiled = PyRegex::compile(r"<script[^>]*>[^<]*<\/script\s*>", false).unwrap();
114        let prefix = PyRegex::compile("<script", false).unwrap();
115        let terminator = PyRegex::compile(r"<\/script\s*>", false).unwrap();
116        assert!(bounded_finditer("<script>a", &compiled, &prefix, &terminator).is_empty());
117    }
118}
guard_core_engine/patterns/scan_window.rs

guard_core_engine/patterns/
scan_window.rs
