Skip to main content

laser_wire/filter/
text.rs

1use crate::error::InvalidError;
2use crate::limits::MAX_FILTER_STRING_BYTES;
3use regex::{Regex, RegexBuilder};
4use serde::{Deserialize, Serialize};
5
6/// Compiled text predicates (regex and glob) one filter may hold. With the
7/// program bound below, one compiled filter stays under 2 MiB of regex
8/// programs, and the per-shard cache of compiled filters stays bounded with
9/// it. Search time is linear in the value for each pattern, so a record costs
10/// at most this many passes over its text fields.
11pub const MAX_REGEX_PREDICATES: usize = 4;
12/// Compiled program bound for one regex or glob, NFA and lazy DFA each. This
13/// bounds memory. Time stays linear in the searched text because the engine
14/// never backtracks.
15const REGEX_SIZE_LIMIT: usize = 256 << 10;
16const REGEX_NEST_LIMIT: u32 = 64;
17const GLOB_ANY_RUN: char = '*';
18const GLOB_ANY_ONE: char = '?';
19const GLOB_ESCAPE: char = '\\';
20
21/// A text match against one payload field or one header. The value must be
22/// text: a missing value is unknown, and a value of another type is a type
23/// mismatch, which follows the filter's mismatch policy.
24#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
25#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
26pub struct TextPredicate {
27    /// A payload field path, or a header key for [`FilterExpr::HeaderText`](crate::filter::FilterExpr::HeaderText).
28    pub field: String,
29    pub kind: TextMatch,
30    pub pattern: String,
31    /// Regex uses the engine's Unicode folding. Other kinds lowercase both sides.
32    #[serde(default, skip_serializing_if = "std::ops::Not::not")]
33    pub case_insensitive: bool,
34}
35
36/// How a [`TextPredicate`] matches, from cheapest to most expensive.
37#[derive(
38    Clone,
39    Copy,
40    Debug,
41    PartialEq,
42    Eq,
43    Serialize,
44    Deserialize,
45    strum::Display,
46    strum::EnumString,
47    strum::VariantArray,
48)]
49#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
50#[serde(rename_all = "snake_case")]
51#[strum(serialize_all = "snake_case")]
52pub enum TextMatch {
53    /// The whole value equals the pattern.
54    Equals,
55    /// The value starts with the pattern.
56    Prefix,
57    /// The value ends with the pattern.
58    Suffix,
59    /// The pattern occurs anywhere in the value.
60    Contains,
61    /// The whole value matches a glob: `*` is any run of characters, `?` is
62    /// one character, and `\` escapes the next character.
63    Glob,
64    /// The value contains a match of a regular expression, run by the
65    /// server's Rust engine in time linear in the value. Lookaround,
66    /// backreferences, and inline flags are refused. `\d`, `\w`, `\s`, and
67    /// `\b` are Unicode-aware, and case-insensitive matching uses the
68    /// engine's simple case folding, where the other kinds lowercase both
69    /// sides. The server's verdict is the contract, and the Rust, Python, and
70    /// TypeScript local evaluators follow the same rules.
71    Regex,
72}
73
74/// A validated [`TextPredicate`] ready to run per record.
75#[derive(Clone, Debug)]
76pub struct TextMatcher {
77    kind: TextMatch,
78    /// The pattern as written, for explanations.
79    source: String,
80    case_insensitive: bool,
81    program: Program,
82}
83
84/// What one evaluation runs: a plain comparison against the pattern, lowercased
85/// when case-insensitive, or a compiled regex for the `glob` and `regex` kinds.
86#[derive(Clone, Debug)]
87enum Program {
88    Plain(String),
89    Compiled(Regex),
90}
91
92impl TextPredicate {
93    /// Compiling is the validation, so a predicate is checked exactly once.
94    pub fn validate(&self) -> Result<(), InvalidError> {
95        TextMatcher::compile(self).map(|_| ())
96    }
97}
98
99impl TextMatcher {
100    pub fn compile(predicate: &TextPredicate) -> Result<Self, InvalidError> {
101        if predicate.pattern.len() > MAX_FILTER_STRING_BYTES {
102            return Err(InvalidError::new(format!(
103                "a text pattern exceeds {MAX_FILTER_STRING_BYTES}B"
104            )));
105        }
106        let program = match predicate.kind {
107            TextMatch::Regex => Program::Compiled(compile_regex(
108                &predicate.pattern,
109                predicate.case_insensitive,
110            )?),
111            TextMatch::Glob => Program::Compiled(compile_glob(
112                &predicate.pattern,
113                predicate.case_insensitive,
114            )?),
115            _ if predicate.case_insensitive => Program::Plain(predicate.pattern.to_lowercase()),
116            _ => Program::Plain(predicate.pattern.clone()),
117        };
118        Ok(Self {
119            kind: predicate.kind,
120            source: predicate.pattern.clone(),
121            case_insensitive: predicate.case_insensitive,
122            program,
123        })
124    }
125
126    pub fn matches(&self, value: &str) -> bool {
127        let pattern = match &self.program {
128            Program::Compiled(regex) => {
129                return if self.kind == TextMatch::Glob && self.case_insensitive {
130                    regex.is_match(&value.to_lowercase())
131                } else {
132                    regex.is_match(value)
133                };
134            }
135            Program::Plain(pattern) => pattern.as_str(),
136        };
137        let folded;
138        let value = if self.case_insensitive {
139            folded = value.to_lowercase();
140            folded.as_str()
141        } else {
142            value
143        };
144        match self.kind {
145            TextMatch::Equals => value == pattern,
146            TextMatch::Prefix => value.starts_with(pattern),
147            TextMatch::Suffix => value.ends_with(pattern),
148            TextMatch::Contains => value.contains(pattern),
149            TextMatch::Glob | TextMatch::Regex => false,
150        }
151    }
152
153    pub fn kind(&self) -> TextMatch {
154        self.kind
155    }
156
157    /// The pattern as written, with its case mode, for explanations.
158    pub fn label(&self) -> String {
159        if self.case_insensitive {
160            format!("{:?} ignoring case", self.source)
161        } else {
162            format!("{:?}", self.source)
163        }
164    }
165}
166
167// A glob compiles to an anchored regex, so it runs in linear time like every
168// other kind. Case-insensitive globs lowercase their literals, and `matches`
169// lowercases the value, the same rule the plain kinds follow.
170fn compile_glob(pattern: &str, case_insensitive: bool) -> Result<Regex, InvalidError> {
171    let tokens = glob_tokens(pattern).ok_or_else(|| {
172        InvalidError::new("a glob pattern cannot end with an unescaped backslash")
173    })?;
174    let mut expression = String::from("\\A(?:");
175    for token in tokens {
176        match token {
177            GlobToken::AnyRun => expression.push_str(".*"),
178            GlobToken::AnyOne => expression.push('.'),
179            GlobToken::Literal(character) => {
180                let literal = character.to_string();
181                let literal = if case_insensitive {
182                    literal.to_lowercase()
183                } else {
184                    literal
185                };
186                expression.push_str(&regex::escape(&literal));
187            }
188        }
189    }
190    expression.push_str(")\\z");
191    RegexBuilder::new(&expression)
192        .dot_matches_new_line(true)
193        .size_limit(REGEX_SIZE_LIMIT)
194        .dfa_size_limit(REGEX_SIZE_LIMIT)
195        .nest_limit(REGEX_NEST_LIMIT)
196        .build()
197        .map_err(|error| InvalidError::new(format!("invalid glob: {error}")))
198}
199
200// Inline flags, lookaround, and backreferences have no shared meaning across
201// the SDK regex engines, so they are refused before the engine sees them.
202fn compile_regex(pattern: &str, case_insensitive: bool) -> Result<Regex, InvalidError> {
203    if let Some(construct) = unportable_regex_construct(pattern) {
204        return Err(InvalidError::new(format!(
205            "regex {construct} is not supported, write the pattern without it"
206        )));
207    }
208    RegexBuilder::new(pattern)
209        .case_insensitive(case_insensitive)
210        .size_limit(REGEX_SIZE_LIMIT)
211        .dfa_size_limit(REGEX_SIZE_LIMIT)
212        .nest_limit(REGEX_NEST_LIMIT)
213        .build()
214        .map_err(|error| InvalidError::new(format!("invalid regex: {error}")))
215}
216
217fn unportable_regex_construct(pattern: &str) -> Option<&'static str> {
218    let mut characters = pattern.chars().peekable();
219    let mut in_class = false;
220    while let Some(character) = characters.next() {
221        match character {
222            '\\' => match characters.next() {
223                Some('1'..='9') => return Some("backreferences"),
224                Some('k') => return Some("named backreferences"),
225                _ => {}
226            },
227            '[' => in_class = true,
228            ']' => in_class = false,
229            '(' if !in_class && characters.peek() == Some(&'?') => {
230                characters.next();
231                if characters.peek() != Some(&':') {
232                    return Some("groups starting with (? other than (?:");
233                }
234            }
235            _ => {}
236        }
237    }
238    None
239}
240
241/// One glob element, after escapes are resolved.
242#[derive(Clone, Copy, PartialEq, Eq)]
243enum GlobToken {
244    AnyRun,
245    AnyOne,
246    Literal(char),
247}
248
249fn glob_tokens(pattern: &str) -> Option<Vec<GlobToken>> {
250    let mut tokens = Vec::with_capacity(pattern.len());
251    let mut characters = pattern.chars();
252    while let Some(character) = characters.next() {
253        tokens.push(match character {
254            GLOB_ANY_RUN => GlobToken::AnyRun,
255            GLOB_ANY_ONE => GlobToken::AnyOne,
256            GLOB_ESCAPE => GlobToken::Literal(characters.next()?),
257            literal => GlobToken::Literal(literal),
258        });
259    }
260    Some(tokens)
261}
262
263// The classic two-pointer match: on a mismatch after a `*`, the star absorbs
264// one more character and matching resumes, which can repeat prefix comparisons on adversarial inputs.
265#[cfg(test)]
266fn glob_matches(pattern: &str, value: &str) -> bool {
267    let Some(tokens) = glob_tokens(pattern) else {
268        return false;
269    };
270    let text: Vec<char> = value.chars().collect();
271    let (mut token, mut position) = (0, 0);
272    let mut resume: Option<(usize, usize)> = None;
273    while position < text.len() {
274        match tokens.get(token) {
275            Some(GlobToken::AnyRun) => {
276                resume = Some((token, position));
277                token += 1;
278            }
279            Some(GlobToken::AnyOne) => {
280                token += 1;
281                position += 1;
282            }
283            Some(GlobToken::Literal(literal)) if *literal == text[position] => {
284                token += 1;
285                position += 1;
286            }
287            _ => match resume {
288                Some((star, absorbed)) => {
289                    token = star + 1;
290                    position = absorbed + 1;
291                    resume = Some((star, absorbed + 1));
292                }
293                None => return false,
294            },
295        }
296    }
297    tokens[token..]
298        .iter()
299        .all(|token| *token == GlobToken::AnyRun)
300}
301
302#[cfg(test)]
303mod tests {
304    use super::*;
305
306    fn matcher(kind: TextMatch, pattern: &str, case_insensitive: bool) -> TextMatcher {
307        TextMatcher::compile(&TextPredicate {
308            field: "type".to_owned(),
309            kind,
310            pattern: pattern.to_owned(),
311            case_insensitive,
312        })
313        .expect("the pattern compiles")
314    }
315
316    #[test]
317    fn given_each_kind_when_matching_event_types_then_should_follow_its_rule() {
318        let value = "metrics.cpu.v1.reported";
319        assert!(matcher(TextMatch::Equals, value, false).matches(value));
320        assert!(matcher(TextMatch::Prefix, "metrics.", false).matches(value));
321        assert!(matcher(TextMatch::Suffix, ".reported", false).matches(value));
322        assert!(matcher(TextMatch::Contains, ".v1.", false).matches(value));
323        assert!(matcher(TextMatch::Glob, "metrics.*.v?.reported", false).matches(value));
324        assert!(matcher(TextMatch::Regex, r"^metrics\.[a-z]+\.v[0-9]+\.", false).matches(value));
325        assert!(!matcher(TextMatch::Suffix, ".deleted", false).matches(value));
326        assert!(!matcher(TextMatch::Glob, "metrics.*", false).matches("storage.metrics.x"));
327    }
328
329    #[test]
330    fn given_case_insensitive_matching_when_the_case_differs_then_should_still_match() {
331        assert!(matcher(TextMatch::Equals, "Safe", true).matches("SAFE"));
332        assert!(matcher(TextMatch::Contains, "CPU", true).matches("metrics.cpu.v1"));
333        assert!(matcher(TextMatch::Glob, "METRICS.*", true).matches("metrics.x"));
334        assert!(matcher(TextMatch::Regex, "^metrics", true).matches("METRICS.x"));
335        assert!(!matcher(TextMatch::Equals, "Safe", false).matches("SAFE"));
336    }
337
338    #[test]
339    fn given_globs_with_escapes_and_stars_when_matching_then_should_match_the_whole_value() {
340        assert!(matcher(TextMatch::Glob, r"a\*b", false).matches("a*b"));
341        assert!(!matcher(TextMatch::Glob, r"a\*b", false).matches("axb"));
342        assert!(matcher(TextMatch::Glob, "*", false).matches(""));
343        assert!(matcher(TextMatch::Glob, "a*b*c", false).matches("aXXbYYbZc"));
344        assert!(!matcher(TextMatch::Glob, "a*b*c", false).matches("aXXbYY"));
345        assert!(matcher(TextMatch::Glob, "?", false).matches("ł"));
346    }
347
348    #[test]
349    fn given_glob_patterns_when_compiled_then_should_match_the_independent_original_oracle() {
350        for pattern in [
351            "", "*", "**", "?", "*?", "a*b*c", "*aaab", "a**b", r"a\*b", r"a\?b", r"a\\b", "*ł?",
352            "*\n*", "[a]", "(?x)",
353        ] {
354            let compiled = matcher(TextMatch::Glob, pattern, false);
355            for value in [
356                "",
357                "a",
358                "ab",
359                "ac",
360                "aaab",
361                "aaaaac",
362                "a*b",
363                "a?b",
364                r"a\b",
365                "aXXbYYbZc",
366                "ł🙂",
367                "aaał🙂",
368                "a\nb",
369                "[a]",
370                "(?x)",
371            ] {
372                assert_eq!(
373                    compiled.matches(value),
374                    glob_matches(pattern, value),
375                    "{pattern:?} {value:?}"
376                );
377            }
378        }
379        assert!(matcher(TextMatch::Glob, "İ?", true).matches("İx"));
380        assert_eq!(matcher(TextMatch::Glob, "a*", false).label(), "\"a*\"");
381    }
382
383    #[test]
384    fn given_a_long_repeated_prefix_when_matching_a_glob_then_should_reject_a_missing_suffix() {
385        let pattern = format!("*{}b", "a".repeat(256));
386        let value = "a".repeat(65_536);
387        assert!(!matcher(TextMatch::Glob, &pattern, false).matches(&value));
388    }
389
390    #[test]
391    fn given_unportable_or_broken_patterns_when_validated_then_should_refuse_them() {
392        for (kind, pattern) in [
393            (TextMatch::Regex, r"(a)\1"),
394            (TextMatch::Regex, "(?=a)"),
395            (TextMatch::Regex, "(?i)a"),
396            (TextMatch::Regex, "(?P<name>a)"),
397            (TextMatch::Regex, "("),
398            (TextMatch::Glob, "a\\"),
399        ] {
400            let predicate = TextPredicate {
401                field: "type".to_owned(),
402                kind,
403                pattern: pattern.to_owned(),
404                case_insensitive: false,
405            };
406            assert!(predicate.validate().is_err(), "{pattern}");
407        }
408        assert!(matcher(TextMatch::Regex, "(?:a|b)[(?]", false).matches("b?"));
409    }
410}