openlatch-client 0.1.18

//! The two-metacharacter glob matcher (D36).
//!
//! This is the *entire* pattern grammar of the policy engine. It is
//! deliberately tiny: the platform validates `match_pattern` against the same
//! grammar at authoring time, so a pattern the client accepts and a pattern the
//! platform accepts must never diverge.

/// Fully-anchored glob over the WHOLE normalized string. Exactly two
/// metacharacters, per PRD § "Evaluation Semantics":
///
/// - `*` — any sequence of characters, **including empty**. Crosses `/` and
///   every other character. This is NOT path-aware globbing.
/// - `?` — exactly one character.
///
/// Everything else is a literal, **including `[`, `]`, `\` and `.`**.
///
/// Case-sensitive. No character classes, no escapes, no alternation, no regex.
///
/// Anchoring surprises authors and is worth restating: `rm -rf /*` matches
/// `rm -rf /tmp` but does **not** match `sudo rm -rf /tmp`. A rule meant to
/// catch a command anywhere in the string must be written `*rm -rf*`.
///
/// # Rejected alternatives
///
/// - **`globset` / `regex`** — regex invites ReDoS on attacker-influenced
///   input, and both drag `regex-automata` + `aho-corasick` into the dependency
///   graph, which then has to be proven out of the `openlatch-hook` binary.
/// - **The `glob` crate** (already a dependency) — `glob::Pattern` also accepts
///   `[a-z]` character classes, which the PRD forbids. A rule author writing a
///   literal `[` would get surprising behaviour, and the client would then
///   accept patterns the platform's 422 validator rejects — splitting one
///   grammar across two implementations.
/// - **`wildmatch`** — correct grammar, but a whole new crate for ~40 lines.
///
/// # Algorithm
///
/// Linear two-pointer with backtrack-to-last-star. `O(n·m)` worst case but with
/// **no exponential blow-up** on the classic adversarial pattern `*a*a*a*b` —
/// the recursive formulation does blow up; this one does not. See
/// `adversarial_pattern_does_not_blow_up` below, which is the regression guard.
///
/// Operates on `char`s, **not bytes**: a multi-byte UTF-8 command must never
/// let `?` match half a character.
pub fn matches(pattern: &str, text: &str) -> bool {
    let p: Vec<char> = pattern.chars().collect();
    let t: Vec<char> = text.chars().collect();
    let (mut pi, mut ti) = (0usize, 0usize);
    // `star == usize::MAX` is the "no star seen yet" sentinel: a pattern long
    // enough for `usize::MAX` to be a real index cannot exist in memory.
    let (mut star, mut mark) = (usize::MAX, 0usize);

    while ti < t.len() {
        if pi < p.len() && (p[pi] == '?' || p[pi] == t[ti]) {
            pi += 1;
            ti += 1;
        } else if pi < p.len() && p[pi] == '*' {
            star = pi; // remember where the star was
            mark = ti; // and how much text it had consumed
            pi += 1; // try consuming zero characters first
        } else if star != usize::MAX {
            pi = star + 1; // backtrack: let the star eat one more char
            mark += 1;
            ti = mark;
        } else {
            return false;
        }
    }
    // Trailing stars in the pattern may match empty.
    while pi < p.len() && p[pi] == '*' {
        pi += 1;
    }
    pi == p.len()
}

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

    #[test]
    fn literal_match_is_exact_and_anchored() {
        assert!(matches("rm -rf /tmp", "rm -rf /tmp"));
        assert!(!matches("rm -rf /tmp", "rm -rf /tmp "));
        assert!(!matches("rm -rf", "rm -rf /tmp"));
        assert!(!matches("rf /tmp", "rm -rf /tmp"));
    }

    /// The PRD's own anchoring example — the single most surprising property of
    /// the grammar, so it is asserted verbatim.
    #[test]
    fn anchoring_prd_example() {
        assert!(matches("rm -rf /*", "rm -rf /tmp"));
        assert!(!matches("rm -rf /*", "sudo rm -rf /tmp"));
        assert!(matches("*rm -rf*", "rm -rf /tmp"));
        assert!(matches("*rm -rf*", "sudo rm -rf /tmp"));
    }

    #[test]
    fn star_matches_empty_sequence() {
        assert!(matches("*", ""));
        assert!(matches("a*", "a"));
        assert!(matches("*a", "a"));
        assert!(matches("a*b", "ab"));
        assert!(matches("**", ""));
        assert!(matches("a**b", "ab"));
        assert!(matches("a**", "a"));
    }

    #[test]
    fn star_crosses_slashes_and_spaces() {
        // Not path-aware: `*` eats `/` and whitespace like any other char.
        assert!(matches("curl*|*sh", "curl https://x.example/a/b | sh"));
        assert!(matches("*/etc/*", "cat /etc/shadow"));
    }

    #[test]
    fn question_mark_matches_exactly_one_char() {
        assert!(matches("a?c", "abc"));
        assert!(!matches("a?c", "ac")); // not zero
        assert!(!matches("a?c", "abbc")); // not two
        assert!(matches("???", "abc"));
        assert!(!matches("???", "ab"));
    }

    /// `[`, `]`, `\` and `.` are literals — there are no character classes and
    /// no escapes. A rule author writing `[a-z]` gets exactly that text.
    #[test]
    fn brackets_dots_and_backslashes_are_literals() {
        assert!(matches("[a-z]", "[a-z]"));
        assert!(!matches("[a-z]", "b"));
        assert!(matches("a.c", "a.c"));
        assert!(!matches("a.c", "abc")); // `.` is not "any char"
        assert!(matches("a\\*b", "a\\zzb")); // `\` does not escape the `*`
        assert!(!matches("a\\*b", "a*b")); // ...so `\*` is not a literal `*`
    }

    #[test]
    fn matching_is_case_sensitive() {
        assert!(!matches("rm -rf /*", "RM -RF /tmp"));
        assert!(!matches("*BASH*", "bash"));
    }

    /// `?` consumes one `char`, never one byte. Matching on bytes would let a
    /// pattern split a multi-byte code point.
    #[test]
    fn question_mark_matches_one_multibyte_char_not_one_byte() {
        assert!(matches("caf?", "café")); // 'é' is 2 bytes
        assert!(!matches("caf??", "café"));
        assert!(matches("?", "🦀")); // 4 bytes, one char
        assert!(!matches("??", "🦀"));
        assert!(matches("rm ?", "rm 日"));
    }

    #[test]
    fn empty_pattern_matches_only_empty_text() {
        assert!(matches("", ""));
        assert!(!matches("", "x"));
        assert!(!matches("x", ""));
        assert!(!matches("?", ""));
    }

    /// The anti-blow-up guard. The recursive formulation of this matcher is
    /// exponential on `*a*a*a…b` against a run of `a`s; the two-pointer with a
    /// single backtrack point is not. If someone "simplifies" this function
    /// into recursion, this test hangs instead of passing.
    #[test]
    fn adversarial_pattern_does_not_blow_up() {
        let pattern = "*a*a*a*a*a*a*b";
        let text = "a".repeat(40);
        let start = std::time::Instant::now();
        assert!(!matches(pattern, &text));
        assert!(
            start.elapsed() < std::time::Duration::from_secs(1),
            "matcher took {:?} — the backtracking guard is gone",
            start.elapsed()
        );

        // A longer run, still linear-ish. 4_000 chars against 7 stars.
        let long = "a".repeat(4_000);
        let start = std::time::Instant::now();
        assert!(!matches(pattern, &long));
        assert!(start.elapsed() < std::time::Duration::from_secs(1));
    }

    #[test]
    fn backtracking_finds_a_late_match() {
        // Requires the star to give back characters it greedily consumed.
        assert!(matches("*ab", "aaab"));
        assert!(matches("*a*b", "aaaxb"));
        assert!(matches("a*b*c", "axxbyyc"));
        assert!(!matches("a*b*c", "axxbyy"));
    }

    #[test]
    fn mixed_metacharacters() {
        assert!(matches("*rm -rf /?", "sudo rm -rf /x"));
        assert!(!matches("*rm -rf /?", "sudo rm -rf /"));
        assert!(matches(
            "git push*--force*",
            "git push origin main --force-with-lease"
        ));
    }
}