yo-common 0.3.8

//! Redis's glob matching, which is what `KEYS`, `SCAN MATCH`, `CONFIG GET` and
//! `COMMAND LIST FILTERBY PATTERN` all mean by a pattern.
//!
//! It is not a regular expression and it is not the shell's glob either. There
//! are four things in it: `*` for any run of bytes, `?` for one byte, `[...]`
//! for a class, and a backslash for the byte after it. Everything else is a
//! literal, including the bytes that are special in a regular expression, so
//! `user.*` matches `user.1` and does not match `userX1`.
//!
//! Bytes rather than characters, the same as Redis. A pattern is matched
//! against a key, a key is arbitrary bytes, and deciding what a character is
//! would mean deciding what encoding a key is in, which nobody can do.

/// Whether `text` matches `pattern`.
///
/// The `*` case backtracks: on a mismatch the search goes back to the last star
/// and gives it one more byte. That is quadratic on a pattern built to be slow,
/// such as a run of stars against a long key, and it is what Redis does. The
/// difference is that Redis walks the whole keyspace with it and this walks a
/// list of settings, so the pathological case is not reachable from a client
/// until `KEYS` lands, at which point the cost is the keyspace scan and not
/// this.
#[must_use]
pub fn matches(pattern: &[u8], text: &[u8]) -> bool {
    matches_nocase(pattern, text, false)
}

/// Whether `text` matches `pattern`, optionally ignoring ASCII case.
///
/// `ARGREP GLOB` is the one caller that asks for the fold. Redis folds in three
/// of the four places a byte is compared: a literal, an escaped literal and both
/// ends of a range. The one it leaves alone is an escaped byte inside a class,
/// so `[\A]` under `NOCASE` matches an `A` and not an `a`, which reads like an
/// oversight and is old enough to be relied on.
///
/// The fold is ASCII only, deliberately, because the subject is arbitrary bytes
/// and folding by a locale would make the answer depend on the machine.
#[must_use]
pub fn matches_nocase(pattern: &[u8], text: &[u8], nocase: bool) -> bool {
    let (mut p, mut t) = (0usize, 0usize);
    // Where to go back to when a `*` has to give up a byte. `None` until the
    // first star, which is what makes a pattern without one a straight walk.
    let mut star: Option<usize> = None;
    let mut mark = 0usize;
    while t < text.len() {
        let mut step = false;
        if p < pattern.len() {
            match pattern[p] {
                b'*' => {
                    star = Some(p);
                    mark = t;
                    p += 1;
                    continue;
                }
                b'?' => {
                    p += 1;
                    t += 1;
                    continue;
                }
                b'[' => {
                    let (next, hit) = class(pattern, p, text[t], nocase);
                    if hit {
                        p = next;
                        step = true;
                    }
                }
                b'\\' if p + 1 < pattern.len() => {
                    if same(pattern[p + 1], text[t], nocase) {
                        p += 2;
                        step = true;
                    }
                }
                c => {
                    if same(c, text[t], nocase) {
                        p += 1;
                        step = true;
                    }
                }
            }
        }
        if step {
            t += 1;
            continue;
        }
        match star {
            Some(at) => {
                p = at + 1;
                mark += 1;
                t = mark;
            }
            None => return false,
        }
    }
    // Trailing stars match nothing, which is the one place a pattern is allowed
    // to be longer than what it matched.
    while p < pattern.len() && pattern[p] == b'*' {
        p += 1;
    }
    p == pattern.len()
}

/// Match one byte against the class starting at `p`, which is a `[`.
///
/// Answers where the class ends and whether the byte belongs to it. A class
/// with no closing bracket ends at the end of the pattern rather than being an
/// error, which is Redis's reading and means a stray bracket in a key pattern
/// is never a refusal.
fn class(pattern: &[u8], p: usize, c: u8, nocase: bool) -> (usize, bool) {
    let mut i = p + 1;
    let negate = i < pattern.len() && pattern[i] == b'^';
    if negate {
        i += 1;
    }
    let mut hit = false;
    while i < pattern.len() && pattern[i] != b']' {
        if pattern[i] == b'\\' && i + 1 < pattern.len() {
            i += 1;
            // The one comparison Redis does not fold.
            hit |= pattern[i] == c;
            i += 1;
        } else if i + 2 < pattern.len() && pattern[i + 1] == b'-' && pattern[i + 2] != b']' {
            let (mut lo, mut hi) = (pattern[i], pattern[i + 2]);
            // Redis puts the ends the right way round before it folds them and
            // not after, so `[Z-a]` under NOCASE is the empty range `z` to `a`
            // rather than the whole of the alphabet.
            if lo > hi {
                core::mem::swap(&mut lo, &mut hi);
            }
            let (lo, hi, c) = if nocase {
                (fold(lo), fold(hi), fold(c))
            } else {
                (lo, hi, c)
            };
            hit |= c >= lo && c <= hi;
            i += 3;
        } else {
            hit |= same(pattern[i], c, nocase);
            i += 1;
        }
    }
    let next = if i < pattern.len() { i + 1 } else { i };
    (next, hit != negate)
}

/// One ASCII letter in lower case, and every other byte as it was.
fn fold(b: u8) -> u8 {
    b.to_ascii_lowercase()
}

/// Whether two bytes are the same, ASCII case aside when asked.
fn same(a: u8, b: u8, nocase: bool) -> bool {
    a == b || (nocase && fold(a) == fold(b))
}

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

    #[test]
    fn a_pattern_without_a_wildcard_is_an_equality_test() {
        assert!(matches(b"maxmemory", b"maxmemory"));
        assert!(!matches(b"maxmemory", b"maxmemory-policy"));
        assert!(!matches(b"maxmemory-policy", b"maxmemory"));
        assert!(matches(b"", b""));
        assert!(!matches(b"", b"x"));
    }

    #[test]
    fn stars_match_any_run_including_none() {
        assert!(matches(b"*", b""));
        assert!(matches(b"*", b"anything at all"));
        assert!(matches(b"maxmemory*", b"maxmemory"));
        assert!(matches(b"maxmemory*", b"maxmemory-policy"));
        assert!(matches(b"*policy", b"maxmemory-policy"));
        assert!(matches(b"max*policy", b"maxmemory-policy"));
        assert!(!matches(b"max*policy", b"maxmemory-clients"));
        assert!(matches(b"a**b", b"ab"));
    }

    #[test]
    fn a_question_mark_is_exactly_one_byte() {
        assert!(matches(b"h?llo", b"hello"));
        assert!(!matches(b"h?llo", b"hllo"));
        assert!(!matches(b"h?llo", b"heello"));
    }

    #[test]
    fn classes_do_ranges_and_negation() {
        assert!(matches(b"h[ae]llo", b"hello"));
        assert!(matches(b"h[ae]llo", b"hallo"));
        assert!(!matches(b"h[ae]llo", b"hillo"));
        assert!(matches(b"h[^e]llo", b"hallo"));
        assert!(!matches(b"h[^e]llo", b"hello"));
        assert!(matches(b"key[0-9]", b"key7"));
        assert!(!matches(b"key[0-9]", b"keyx"));
        // A range the wrong way round is read as if it were the right way
        // round, which is what Redis does rather than matching nothing.
        assert!(matches(b"key[9-0]", b"key7"));
    }

    #[test]
    fn a_backslash_takes_the_special_out_of_the_next_byte() {
        assert!(matches(br"a\*b", b"a*b"));
        assert!(!matches(br"a\*b", b"axxb"));
        assert!(matches(br"a\\b", br"a\b"));
    }

    /// The pattern that would run away if the backtracking were wrong. It
    /// answers rather than hanging, which is the whole point of the test.
    #[test]
    fn a_pattern_built_to_be_slow_still_answers() {
        let pattern = b"*a*a*a*a*a*b";
        let text = vec![b'a'; 64];
        assert!(!matches(pattern, &text));
    }

    #[test]
    fn nocase_folds_everything_except_an_escape_inside_a_class() {
        assert!(matches_nocase(b"HELLO", b"hello", true));
        assert!(matches_nocase(b"h*O", b"hello", true));
        assert!(matches_nocase(b"h[AE]llo", b"hello", true));
        assert!(matches_nocase(b"KEY[A-Z]", b"keyx", true));
        assert!(matches_nocase(br"a\Bc", b"abc", true));
        assert!(!matches_nocase(b"HELLO", b"hello", false));
        // The odd one out. Redis compares an escaped class item raw, so the
        // fold does not reach it.
        assert!(!matches_nocase(br"a[\B]c", b"abc", true));
        assert!(matches_nocase(br"a[\B]c", b"aBc", true));
        // The ends of a range are put in order before they are folded, which
        // makes this one empty rather than everything from Z to a.
        assert!(!matches_nocase(b"[Z-a]", b"b", true));
    }

    /// Not an error, and not a match for a bracket that is not there.
    #[test]
    fn a_class_that_is_never_closed_ends_at_the_end() {
        assert!(matches(b"a[bc", b"ab"));
        assert!(!matches(b"a[bc", b"ax"));
    }
}