tellaro-query-language 2.0.0

//! Translate PCRE-flavoured regex into Lucene's regexp dialect.
//!
//! OpenSearch's `regexp` query runs Lucene's `RegExp` engine, which is a
//! finite-automaton matcher and **not** PCRE. Patterns that are perfectly valid
//! in Python, Go, or a Sigma `|re:` field are rejected outright, and the
//! rejection arrives at *search* time:
//!
//! ```text
//! RequestError(400, 'search_phase_execution_exception',
//!              "failed to create query: expected '\"' at position 86")
//! ```
//!
//! A rule carrying such a pattern validates, schedules, and throws on every run
//! while looking perfectly healthy. Seven rules in the shipped Windows corpus
//! were in exactly that state -- they had never matched anything and never said
//! so.
//!
//! Three differences cause nearly all of it.
//!
//! **A bare double quote is an operator.** Lucene uses `"..."` to mark a
//! literal run, so an unescaped `"` inside a pattern is a syntax error rather
//! than the character it looks like.
//!
//! **Shorthand classes do not exist.** `\d`, `\w`, `\s` and their negations are
//! PCRE conveniences with no Lucene equivalent; they must be spelled as
//! explicit character classes.
//!
//! **Matching is whole-term, not searching.** Lucene anchors implicitly, so
//! `abc` matches only the term "abc" -- never "xabcx". PCRE users write
//! unanchored patterns and expect a search, which is why this module wraps them
//! in `.*` unless the author anchored deliberately. Getting this wrong produces
//! no error at all, just a rule that quietly matches nothing.
//!
//! There is a fourth difference that produces no error at all. Lucene treats an
//! unknown escape as the literal character, so a PCRE `\A` (start of string)
//! becomes a literal "A" and the rule quietly matches something else entirely.
//! Anchors are translated here instead, because Lucene already anchors.
//!
//! Queries are emitted with `flags: NONE` so that Lucene's optional operators --
//! `~` complement, `&` intersection, `#` empty, `@` anystring and `<n-m>`
//! interval -- are literals. A pattern written for PCRE means the characters,
//! not the operators, and a stray `<` otherwise fails the query outright.
//!
//! What cannot be translated is refused rather than mangled. Lookaround and
//! backreferences need a backtracking engine; there is no automaton equivalent,
//! and silently dropping them would change what a detection means.
//!
//! # Parity
//!
//! This is a direct port of `src/tql/regex_compat.py` and must stay
//! byte-identical in behaviour. The shared fixture at
//! `cross_language_tests/fixtures/test_cases/opensearch/regex_translation.json`
//! is executed by both languages and is the guard against drift.

use crate::error::{Result, TqlError};

/// PCRE shorthand -> explicit class.
///
/// The third element is the form used when the shorthand appears inside an
/// existing `[...]`, where the brackets must not nest. `None` means the
/// shorthand is a negation and has no single-class spelling.
const SHORTHAND: &[(char, &str, Option<&str>)] = &[
    ('d', "[0-9]", Some("0-9")),
    ('D', "[^0-9]", None),
    ('w', "[A-Za-z0-9_]", Some("A-Za-z0-9_")),
    ('W', "[^A-Za-z0-9_]", None),
    ('s', "[ \t\n\r\u{0C}\u{0B}]", Some(" \t\n\r\u{0C}\u{0B}")),
    ('S', "[^ \t\n\r\u{0C}\u{0B}]", None),
];

/// Constructs with no finite-automaton equivalent. Translating these would
/// change the meaning of a detection, so they are refused.
const UNSUPPORTED: &[(&str, &str)] = &[
    ("(?=", "lookahead"),
    ("(?!", "negative lookahead"),
    ("(?<=", "lookbehind"),
    ("(?<!", "negative lookbehind"),
    ("(?P<", "named capture group"),
    ("(?P=", "named backreference"),
];

/// Inline flags Python's `re` accepts in a leading `(?...)` group.
const INLINE_FLAG_CHARS: &[char] = &['a', 'i', 'm', 's', 'u', 'x'];

fn shorthand(ch: char) -> Option<(&'static str, Option<&'static str>)> {
    SHORTHAND
        .iter()
        .find(|(key, _, _)| *key == ch)
        .map(|(_, full, inner)| (*full, *inner))
}

/// Escape-based constructs, detected inside the scanner rather than by
/// substring search, because escape state decides what they mean.
///
/// `\\B` is an escaped backslash followed by a literal B -- which is how every
/// Windows path in this corpus spells a directory starting with B
/// (`...\\BUnzip\\Setup.exe`). A naive substring scan reads that as a
/// word-boundary assertion and refuses a perfectly good rule.
///
/// `\A` and `\Z` are absent on purpose: they are anchors, and Lucene anchors
/// implicitly, so the scanner translates them rather than refusing.
fn unsupported_escape(ch: char) -> Option<&'static str> {
    match ch {
        'b' => Some("word boundary"),
        'B' => Some("non-word boundary"),
        _ => None,
    }
}

/// A pattern Lucene can execute, plus what had to change to get there.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LuceneRegex {
    /// The translated pattern, ready for a Lucene `regexp` query.
    pub pattern: String,
    /// True when a leading `(?i)` was lifted off the pattern; the caller must
    /// set `case_insensitive` on the emitted query to preserve the meaning.
    pub case_insensitive: bool,
    /// Human-readable description of every change made, for diagnostics.
    pub changes: Vec<String>,
}

impl LuceneRegex {
    /// True when translation had to alter the pattern.
    pub fn changed(&self) -> bool {
        !self.changes.is_empty()
    }
}

/// True when `pattern`'s SYNTAX needs no translation to run on Lucene.
///
/// Anchoring is not syntax, so it is excluded: wrapping a pattern in `.*`
/// changes what it matches but never whether Lucene can parse it.
pub fn is_lucene_safe(pattern: &str) -> bool {
    match to_lucene_regex(pattern, false) {
        Ok(translated) => !translated.changed(),
        Err(_) => false,
    }
}

/// Match a leading inline-flag group, mirroring Python's `^\(\?([aimsux]+)\)`.
///
/// Returns the flag characters and the index just past the closing paren.
/// `(?:` yields `None` because `:` is not a flag character, which is what keeps
/// non-capturing groups out of this branch.
fn match_inline_flags(chars: &[char]) -> Option<(Vec<char>, usize)> {
    if chars.len() < 4 || chars[0] != '(' || chars[1] != '?' {
        return None;
    }
    let mut end = 2;
    while end < chars.len() && INLINE_FLAG_CHARS.contains(&chars[end]) {
        end += 1;
    }
    if end == 2 || end >= chars.len() || chars[end] != ')' {
        return None;
    }
    Some((chars[2..end].to_vec(), end + 1))
}

/// Translate a PCRE-flavoured pattern into Lucene's regexp dialect.
///
/// # Arguments
///
/// * `pattern` - the source pattern, as written by a human or a Sigma rule.
/// * `anchor` - wrap the result in `.*` when the author did not anchor it.
///   Lucene matches whole terms, so an unanchored PCRE pattern that means
///   "search for this" silently matches nothing without the wrapping. Pass
///   `false` when the caller has already anchored deliberately.
///
/// # Errors
///
/// Returns [`TqlError::ValidationError`] when the pattern uses a construct with
/// no automaton equivalent. Refusing is deliberate -- a mangled detection is
/// worse than one that will not load.
pub fn to_lucene_regex(pattern: &str, anchor: bool) -> Result<LuceneRegex> {
    let mut changes: Vec<String> = Vec::new();
    let mut case_insensitive = false;

    let mut chars: Vec<char> = pattern.chars().collect();

    // Inline flags only bind for the whole pattern in Lucene's world, so lift a
    // leading (?i) onto the query and reject flags with no equivalent.
    if let Some((flags, end)) = match_inline_flags(&chars) {
        let mut unsupported: Vec<char> = flags.iter().copied().filter(|c| *c != 'i').collect();
        unsupported.sort_unstable();
        unsupported.dedup();
        if !unsupported.is_empty() {
            let joined: String = unsupported.into_iter().collect();
            return Err(TqlError::ValidationError(format!(
                "regex uses inline flag(s) '{joined}', which Lucene's engine does not support"
            )));
        }
        case_insensitive = flags.contains(&'i');
        chars = chars[end..].to_vec();
        changes.push("lifted (?i) to the query's case_insensitive flag".to_string());
    }

    // Group constructs are safe to detect by substring: `(` is never itself
    // escaped into existence. Escape-based constructs (\b, \B, backreferences)
    // are NOT -- `\\B` is an escaped backslash followed by a literal B, which is
    // how every Windows path in this corpus spells a directory beginning with B.
    // Those are detected inside the scanner, where escape state is known.
    let remaining: String = chars.iter().collect();
    for (token, label) in UNSUPPORTED {
        if remaining.contains(token) {
            return Err(TqlError::ValidationError(format!(
                "regex uses {label} ('{token}'), which has no equivalent in Lucene's \
                 finite-automaton engine; rewrite the pattern without it"
            )));
        }
    }

    let mut out: Vec<String> = Vec::new();
    let mut in_class = false;
    let mut anchored_start = false;
    let mut anchored_end = false;
    let mut i = 0usize;
    let length = chars.len();

    while i < length {
        let ch = chars[i];

        if ch == '\\' && i + 1 < length {
            let nxt = chars[i + 1];
            // \A and \Z are PCRE anchors. Lucene has no such escape and would
            // read them as the literal letters, so the rule would still run and
            // quietly match the wrong thing. Lucene anchors implicitly.
            if nxt == 'A' && i == 0 {
                anchored_start = true;
                changes.push(r"dropped \A (Lucene anchors implicitly)".to_string());
                i += 2;
                continue;
            }
            if (nxt == 'Z' || nxt == 'z') && i + 2 == length {
                anchored_end = true;
                changes.push(format!(r"dropped \{nxt} (Lucene anchors implicitly)"));
                i += 2;
                continue;
            }
            if let Some(label) = unsupported_escape(nxt) {
                return Err(TqlError::ValidationError(format!(
                    "regex uses {label} (\\{nxt}), which has no equivalent in Lucene's \
                     finite-automaton engine; rewrite the pattern without it"
                )));
            }
            if nxt.is_ascii_digit() && nxt != '0' {
                return Err(TqlError::ValidationError(
                    "regex uses a backreference, which has no equivalent in Lucene's \
                     finite-automaton engine"
                        .to_string(),
                ));
            }
            if let Some((full, inner)) = shorthand(nxt) {
                let emitted = if in_class {
                    let Some(inner) = inner else {
                        return Err(TqlError::ValidationError(format!(
                            "regex nests a negated shorthand class (\\{nxt}) inside [...], \
                             which cannot be expressed as a single Lucene character class"
                        )));
                    };
                    inner
                } else {
                    full
                };
                out.push(emitted.to_string());
                changes.push(format!("\\{nxt} -> {emitted}"));
                i += 2;
                continue;
            }
            // Any other escape passes through as-is; Lucene shares \\ semantics.
            // Pushed as ONE entry so a later look-back at the last entry can
            // tell an escaped `\|` from a bare alternation `|`.
            out.push(format!("{ch}{nxt}"));
            i += 2;
            continue;
        }

        if ch == ')' && !in_class && out.last().map(String::as_str) == Some("|") {
            // A trailing empty alternative -- `(X|)`, meaning "X or nothing" --
            // is ordinary PCRE and is how Sigma spells an optional run. Lucene
            // has no empty branch and rejects the whole query; `(X)?` is the
            // same language. (A LEADING empty branch, `(|X)`, Lucene accepts.)
            out.pop();
            out.push(")?".to_string());
            changes.push("(X|) -> (X)? (Lucene has no empty alternative)".to_string());
            i += 1;
            continue;
        }

        if ch == '[' && !in_class {
            in_class = true;
            out.push(ch.to_string());
            i += 1;
            continue;
        }

        if ch == ']' && in_class {
            in_class = false;
            out.push(ch.to_string());
            i += 1;
            continue;
        }

        if in_class {
            // Inside a class the only hazard is the quote operator.
            if ch == '"' {
                out.push("\\\"".to_string());
                changes.push("escaped a bare \" (Lucene quote operator)".to_string());
            } else {
                out.push(ch.to_string());
            }
            i += 1;
            continue;
        }

        if ch == '"' {
            out.push("\\\"".to_string());
            changes.push("escaped a bare \" (Lucene quote operator)".to_string());
            i += 1;
            continue;
        }

        if ch == '^' && i == 0 {
            anchored_start = true;
            changes.push("dropped ^ (Lucene anchors implicitly)".to_string());
            i += 1;
            continue;
        }

        if ch == '$' && i == length - 1 {
            anchored_end = true;
            changes.push("dropped $ (Lucene anchors implicitly)".to_string());
            i += 1;
            continue;
        }

        if ch == '(' && i + 2 < length && chars[i + 1] == '?' && chars[i + 2] == ':' {
            out.push("(".to_string());
            changes.push("(?: -> ( (Lucene has no non-capturing group)".to_string());
            i += 3;
            continue;
        }

        // Lazy and possessive quantifiers collapse to greedy. Lucene matches the
        // whole term, so which of several equally-valid matches wins is not
        // observable -- only whether the term matches at all.
        if matches!(ch, '*' | '+' | '?' | '}')
            && i + 1 < length
            && matches!(chars[i + 1], '?' | '+')
        {
            out.push(ch.to_string());
            changes.push(format!(
                "{ch}{} -> {ch} (no lazy/possessive quantifiers)",
                chars[i + 1]
            ));
            i += 2;
            continue;
        }

        out.push(ch.to_string());
        i += 1;
    }

    if in_class {
        return Err(TqlError::ValidationError(
            "regex has an unterminated character class '['".to_string(),
        ));
    }

    let mut translated: String = out.concat();

    // Lucene matches the ENTIRE term, so an anchor is not something to drop --
    // it is something to spell out. PCRE `^A` means "starts with A", which in a
    // whole-term engine is `A.*`; dropping the caret alone yields `A`, meaning
    // "exactly A", and the rule silently stops matching almost everything it
    // used to.
    //
    //     ^A$   exact       ->  A
    //     ^A    starts with ->  A.*
    //     A$    ends with   ->  .*A
    //     A     contains    ->  .*A.*   (only when `anchor` is set; otherwise the
    //                                    caller has taken responsibility)
    if anchored_start && anchored_end {
        // Exact match is what Lucene already does.
    } else if anchored_start {
        if !translated.ends_with(".*") {
            translated.push_str(".*");
            changes.push("^ became a trailing .* (Lucene matches whole terms)".to_string());
        }
    } else if anchored_end {
        if !translated.starts_with(".*") {
            translated = format!(".*{translated}");
            changes.push("$ became a leading .* (Lucene matches whole terms)".to_string());
        }
    } else if anchor {
        let before = translated.clone();
        if !translated.starts_with(".*") {
            translated = format!(".*{translated}");
        }
        if !translated.ends_with(".*") {
            translated.push_str(".*");
        }
        if translated != before {
            changes.push("wrapped in .* (Lucene matches whole terms, not substrings)".to_string());
        }
    }

    Ok(LuceneRegex {
        pattern: translated,
        case_insensitive,
        changes,
    })
}

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

    fn translate(pattern: &str) -> String {
        to_lucene_regex(pattern, false).unwrap().pattern
    }

    fn refusal(pattern: &str) -> String {
        match to_lucene_regex(pattern, false) {
            Ok(result) => panic!("expected a refusal, got {:?}", result.pattern),
            Err(e) => e.to_string(),
        }
    }

    // --- shorthand classes ------------------------------------------------

    #[test]
    fn shorthand_classes_become_explicit() {
        assert_eq!(translate(r"a\db"), "a[0-9]b");
        assert_eq!(translate(r"a\wb"), "a[A-Za-z0-9_]b");
        assert_eq!(translate(r"a\Db"), "a[^0-9]b");
        assert_eq!(translate(r"a\Wb"), "a[^A-Za-z0-9_]b");
        assert_eq!(translate(r"a\sb"), "a[ \t\n\r\u{0C}\u{0B}]b");
        assert_eq!(translate(r"a\Sb"), "a[^ \t\n\r\u{0C}\u{0B}]b");
    }

    #[test]
    fn shorthand_inside_a_class_does_not_nest_brackets() {
        // `[[0-9]-]` would be a different, broken class.
        assert_eq!(translate(r"[\d-]"), "[0-9-]");
    }

    #[test]
    fn negated_shorthand_inside_a_class_is_refused() {
        // `[\D]` cannot be spelled as one Lucene class, and guessing would
        // change what the rule matches.
        assert!(refusal(r"[\D]").contains("negated shorthand"));
    }

    // --- the operators Lucene reserves ------------------------------------

    #[test]
    fn bare_double_quote_is_escaped() {
        // Lucene uses "..." for a literal run, so an unescaped quote is a
        // syntax error. This is what made seven shipped rules throw every run.
        assert_eq!(translate("set \"abc\""), "set \\\"abc\\\"");
    }

    #[test]
    fn non_capturing_group_becomes_a_plain_group() {
        assert_eq!(translate(r"(?:ab|cd)"), "(ab|cd)");
    }

    #[test]
    fn lazy_quantifiers_become_greedy() {
        assert_eq!(translate(r"a+?b"), "a+b");
        assert_eq!(translate(r"a*?b"), "a*b");
        assert_eq!(translate(r"a{2,3}?b"), "a{2,3}b");
    }

    // --- anchors: the silent-failure cases --------------------------------

    #[test]
    fn both_anchors_mean_exact_match() {
        assert_eq!(translate("^abc$"), "abc");
    }

    #[test]
    fn leading_anchor_becomes_a_trailing_star() {
        assert_eq!(translate("^abc"), "abc.*");
    }

    #[test]
    fn trailing_anchor_becomes_a_leading_star() {
        assert_eq!(translate("abc$"), ".*abc");
    }

    #[test]
    fn pcre_string_anchors_are_translated_not_refused() {
        assert_eq!(translate(r"\Aabc\Z"), "abc");
        assert_eq!(translate(r"\Aabc\z"), "abc");
    }

    // --- escape state, not substring search -------------------------------

    #[test]
    fn escaped_backslash_before_b_is_a_path_not_a_word_boundary() {
        // `...\\BUnzip\\Setup.exe` is a Windows directory, not an assertion. A
        // substring check for `\B` refuses this perfectly good rule.
        let source = r":\\ProgramData\\OEM\\CareCenter_.*\\BUnzip\\Setup_msi\.exe";
        assert_eq!(translate(source), source);
    }

    #[test]
    fn real_word_boundary_is_still_refused() {
        assert!(refusal(r"foo\bbar").contains("word boundary"));
        assert!(refusal(r"foo\Bbar").contains("non-word boundary"));
    }

    #[test]
    fn escaped_backslash_before_a_digit_is_not_a_backreference() {
        // `C:\\1st Folder` is a path; `\1` is a backreference.
        assert_eq!(translate(r"C:\\1st"), r"C:\\1st");
        assert!(refusal(r"(a)\1").contains("backreference"));
    }

    // --- inline flags -----------------------------------------------------

    #[test]
    fn leading_case_insensitive_flag_is_lifted_to_the_query() {
        let result = to_lucene_regex(r"(?i)abc", false).unwrap();
        assert_eq!(result.pattern, "abc");
        assert!(result.case_insensitive);
    }

    #[test]
    fn unsupported_inline_flag_is_refused() {
        assert!(refusal(r"(?s)a.b").contains("inline flag"));
    }

    // --- constructs a finite automaton cannot express ---------------------

    #[test]
    fn lookaround_is_refused() {
        for source in [r"a(?=b)", r"a(?!b)", r"(?<=a)b", r"(?<!a)b"] {
            assert!(
                to_lucene_regex(source, false).is_err(),
                "{source} should be refused"
            );
        }
    }

    #[test]
    fn named_group_constructs_are_refused() {
        assert!(refusal(r"(?P<name>a)").contains("named capture group"));
        assert!(refusal(r"(?P=name)").contains("named backreference"));
    }

    // --- anchoring behaviour ----------------------------------------------

    #[test]
    fn anchor_true_wraps_an_unanchored_pattern() {
        assert_eq!(to_lucene_regex("abc", true).unwrap().pattern, ".*abc.*");
    }

    #[test]
    fn anchor_true_respects_a_deliberate_anchor() {
        assert_eq!(to_lucene_regex("^abc$", true).unwrap().pattern, "abc");
    }

    #[test]
    fn anchor_false_leaves_the_pattern_alone() {
        assert_eq!(to_lucene_regex("abc", false).unwrap().pattern, "abc");
    }

    // --- reporting --------------------------------------------------------

    #[test]
    fn a_clean_pattern_reports_no_changes() {
        let result = to_lucene_regex("[a-z]+foo", false).unwrap();
        assert!(!result.changed());
        assert!(is_lucene_safe("[a-z]+foo"));
        assert!(!is_lucene_safe(r"foo\bbar"));
    }

    #[test]
    fn a_translated_pattern_explains_itself() {
        let result = to_lucene_regex("(?:\\d)\"", false).unwrap();
        assert!(result.changed());
        let joined = result.changes.join("; ");
        assert!(joined.contains("\\d"), "{joined}");
        assert!(joined.contains("(?:"), "{joined}");
        assert!(joined.contains("quote"), "{joined}");
    }

    #[test]
    fn unterminated_class_is_refused() {
        assert!(refusal("[abc").contains("unterminated"));
    }

    // --- empty alternatives -----------------------------------------------

    #[test]
    fn trailing_empty_alternative_becomes_an_optional_group() {
        assert_eq!(translate(r"a(b|)c"), "a(b)?c");
    }

    #[test]
    fn escaped_pipe_is_not_mistaken_for_an_alternative() {
        // `\|` is a literal pipe. Looking back one character without tracking
        // escape state would rewrite `(a\|)` into `(a\)?` and change the pattern.
        assert_eq!(translate(r"(a\|)"), r"(a\|)");
    }

    #[test]
    fn leading_empty_alternative_is_left_alone() {
        // Lucene accepts `(|X)`, so there is nothing to fix.
        assert_eq!(translate(r"(|a)b"), "(|a)b");
    }

    #[test]
    fn a_lone_trailing_backslash_is_preserved() {
        // The `i + 1 < length` guard means a trailing `\` falls through to the
        // literal branch rather than reading past the end.
        assert_eq!(translate(r"abc\"), r"abc\");
    }
}