Skip to main content

zero_client/
like.rs

1//! `LIKE` and `ILIKE` (`packages/zql/src/builder/like.ts`).
2//!
3//! JS compiles a pattern without wildcards to a (lowercased) string
4//! comparison, and anything else to a non-Unicode `RegExp` with the `s` flag.
5//! That regexp works on UTF-16 code units: `_` matches one code unit (half of
6//! a surrogate pair), and `i` folds case per code unit through simple
7//! uppercasing. This reproduces both paths.
8
9use std::fmt;
10
11#[derive(Clone, Debug, PartialEq, Eq)]
12pub struct InvalidPattern(pub &'static str);
13
14impl fmt::Display for InvalidPattern {
15    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
16        f.write_str(self.0)
17    }
18}
19
20impl std::error::Error for InvalidPattern {}
21
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23enum Token {
24    /// `%`
25    Any,
26    /// `_`
27    One,
28    Unit(u16),
29}
30
31#[derive(Clone, Debug)]
32enum Matcher {
33    Exact(String),
34    Lowercased(String),
35    Wildcard {
36        tokens: Vec<Token>,
37        case_insensitive: bool,
38    },
39}
40
41/// A compiled `LIKE` or `ILIKE` pattern.
42#[derive(Clone, Debug)]
43pub struct LikePattern(Matcher);
44
45impl LikePattern {
46    pub fn new(pattern: &str, case_insensitive: bool) -> Result<Self, InvalidPattern> {
47        if !pattern.contains(['_', '%', '\\']) {
48            return Ok(LikePattern(if case_insensitive {
49                Matcher::Lowercased(pattern.to_lowercase())
50            } else {
51                Matcher::Exact(pattern.to_owned())
52            }));
53        }
54        let fold = |u: u16| if case_insensitive { canonicalize(u) } else { u };
55        let units: Vec<u16> = pattern.encode_utf16().collect();
56        let mut tokens = Vec::with_capacity(units.len());
57        let mut i = 0;
58        while i < units.len() {
59            tokens.push(match units[i] {
60                0x25 => Token::Any,
61                0x5F => Token::One,
62                0x5C => {
63                    i += 1;
64                    let Some(&u) = units.get(i) else {
65                        return Err(InvalidPattern(
66                            "LIKE pattern must not end with escape character",
67                        ));
68                    };
69                    Token::Unit(fold(u))
70                }
71                u => Token::Unit(fold(u)),
72            });
73            i += 1;
74        }
75        Ok(LikePattern(Matcher::Wildcard {
76            tokens,
77            case_insensitive,
78        }))
79    }
80
81    pub fn matches(&self, input: &str) -> bool {
82        match &self.0 {
83            Matcher::Exact(p) => input == p,
84            Matcher::Lowercased(p) => input.to_lowercase() == *p,
85            Matcher::Wildcard {
86                tokens,
87                case_insensitive,
88            } => {
89                let units: Vec<u16> = if *case_insensitive {
90                    input.encode_utf16().map(canonicalize).collect()
91                } else {
92                    input.encode_utf16().collect()
93                };
94                wildcard_match(tokens, &units)
95            }
96        }
97    }
98}
99
100/// Full-string wildcard match with backtracking to the last `%`.
101fn wildcard_match(p: &[Token], s: &[u16]) -> bool {
102    let (mut pi, mut si) = (0, 0);
103    let mut star: Option<(usize, usize)> = None;
104    while si < s.len() {
105        match p.get(pi) {
106            Some(Token::Any) => {
107                star = Some((pi, si));
108                pi += 1;
109                continue;
110            }
111            Some(Token::One) => {
112                pi += 1;
113                si += 1;
114                continue;
115            }
116            Some(Token::Unit(u)) if *u == s[si] => {
117                pi += 1;
118                si += 1;
119                continue;
120            }
121            _ => {}
122        }
123        let Some((sp, ss)) = star else { return false };
124        pi = sp + 1;
125        si = ss + 1;
126        star = Some((sp, ss + 1));
127    }
128    p[pi..].iter().all(|t| *t == Token::Any)
129}
130
131/// `Canonicalize` for a non-Unicode, ignore-case `RegExp`: uppercase the code
132/// unit if that yields exactly one code unit, unless it would map a non-ASCII
133/// unit to ASCII.
134fn canonicalize(unit: u16) -> u16 {
135    let Some(c) = char::from_u32(unit.into()) else {
136        return unit; // a lone surrogate
137    };
138    let mut upper = c.to_uppercase();
139    let (Some(u), None) = (upper.next(), upper.next()) else {
140        return unit;
141    };
142    match u16::try_from(u32::from(u)) {
143        Ok(cu) if !(unit >= 128 && cu < 128) => cu,
144        _ => unit,
145    }
146}
147
148/// Escapes the wildcards of `value` (`%` and `_`) for a `LIKE` pattern
149/// (`packages/zql/src/query/escape-like.ts`).
150pub fn escape_like(value: &str) -> String {
151    let mut out = String::with_capacity(value.len());
152    for c in value.chars() {
153        if c == '%' || c == '_' {
154            out.push('\\');
155        }
156        out.push(c);
157    }
158    out
159}