mz_repr/adt/
regex.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10//! Regular expressions.
11
12use std::borrow::Cow;
13use std::cmp::Ordering;
14use std::fmt;
15use std::hash::{Hash, Hasher};
16use std::ops::Deref;
17
18use regex::{Error, RegexBuilder};
19use serde::de::Error as DeError;
20use serde::ser::SerializeStruct;
21use serde::{Deserialize, Deserializer, Serialize, Serializer, de};
22
23/// The maximum size of a regex after compilation.
24/// This is the same as the `Regex` crate's default at the time of writing.
25///
26/// Note: This number is mentioned in our user-facing docs at the "String operators" in the function
27/// reference.
28const MAX_REGEX_SIZE_AFTER_COMPILATION: usize = 10 * 1024 * 1024;
29
30/// We also need a separate limit for the size of regexes before compilation. Even though the
31/// `Regex` crate promises that using its `size_limit` option (which we set to the other limit,
32/// `MAX_REGEX_SIZE_AFTER_COMPILATION`) would prevent excessive resource usage, this doesn't seem to
33/// be the case. Since we compile regexes in envd, we need strict limits to prevent envd OOMs.
34/// See <https://github.com/MaterializeInc/database-issues/issues/9907> for an example.
35///
36/// Note: This number is mentioned in our user-facing docs at the "String operators" in the function
37/// reference.
38const MAX_REGEX_SIZE_BEFORE_COMPILATION: usize = 1 * 1024 * 1024;
39
40/// A hashable, comparable, and serializable regular expression type.
41///
42/// The  [`regex::Regex`] type, the de facto standard regex type in Rust, does
43/// not implement [`PartialOrd`], [`Ord`] [`PartialEq`], [`Eq`], or [`Hash`].
44/// The omissions are reasonable. There is no natural definition of ordering for
45/// regexes. There *is* a natural definition of equality—whether two regexes
46/// describe the same regular language—but that is an expensive property to
47/// compute, and [`PartialEq`] is generally expected to be fast to compute.
48///
49/// This type wraps [`regex::Regex`] and imbues it with implementations of the
50/// above traits. Two regexes are considered equal iff their string
51/// representation is identical, plus flags, such as `case_insensitive`,
52/// are identical. The [`PartialOrd`], [`Ord`], and [`Hash`] implementations
53/// are similarly based upon the string representation plus flags. As
54/// mentioned above, this is not the natural equivalence relation for regexes: for
55/// example, the regexes `aa*` and `a+` define the same language, but would not
56/// compare as equal with this implementation of [`PartialEq`]. Still, it is
57/// often useful to have _some_ equivalence relation available (e.g., to store
58/// types containing regexes in a hashmap) even if the equivalence relation is
59/// imperfect.
60///
61/// [regex::Regex] is hard to serialize (because of the compiled code), so our approach is to
62/// instead serialize this wrapper struct, where we skip serializing the actual regex field, and
63/// we reconstruct the regex field from the other fields upon deserialization.
64/// (Earlier, serialization was buggy due to <https://github.com/tailhook/serde-regex/issues/14>,
65/// and also making the same mistake in our own protobuf serialization code.)
66#[derive(Debug, Clone)]
67pub struct Regex {
68    pub case_insensitive: bool,
69    pub dot_matches_new_line: bool,
70    pub regex: regex::Regex,
71}
72
73impl Regex {
74    /// A simple constructor for the default setting of `dot_matches_new_line: true`.
75    /// See <https://www.postgresql.org/docs/current/functions-matching.html#POSIX-MATCHING-RULES>
76    /// "newline-sensitive matching"
77    pub fn new(pattern: &str, case_insensitive: bool) -> Result<Regex, RegexCompilationError> {
78        Self::new_dot_matches_new_line(pattern, case_insensitive, true)
79    }
80
81    /// Allows explicitly setting `dot_matches_new_line`.
82    pub fn new_dot_matches_new_line(
83        pattern: &str,
84        case_insensitive: bool,
85        dot_matches_new_line: bool,
86    ) -> Result<Regex, RegexCompilationError> {
87        if pattern.len() > MAX_REGEX_SIZE_BEFORE_COMPILATION {
88            return Err(RegexCompilationError::PatternTooLarge {
89                pattern_size: pattern.len(),
90            });
91        }
92        let mut regex_builder = RegexBuilder::new(pattern);
93        regex_builder.case_insensitive(case_insensitive);
94        regex_builder.dot_matches_new_line(dot_matches_new_line);
95        regex_builder.size_limit(MAX_REGEX_SIZE_AFTER_COMPILATION);
96        Ok(Regex {
97            case_insensitive,
98            dot_matches_new_line,
99            regex: regex_builder.build()?,
100        })
101    }
102
103    /// Returns the pattern string of the regex.
104    pub fn pattern(&self) -> &str {
105        // `as_str` returns the raw pattern as provided during construction,
106        // and doesn't include any of the flags.
107        self.regex.as_str()
108    }
109}
110
111/// Error type for regex compilation failures.
112#[derive(Debug, Clone)]
113pub enum RegexCompilationError {
114    /// Wrapper for regex crate's Error type.
115    RegexError(Error),
116    /// Regex pattern size exceeds MAX_REGEX_SIZE_BEFORE_COMPILATION.
117    PatternTooLarge { pattern_size: usize },
118}
119
120impl fmt::Display for RegexCompilationError {
121    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122        match self {
123            RegexCompilationError::RegexError(e) => write!(f, "{}", e),
124            RegexCompilationError::PatternTooLarge {
125                pattern_size: patter_size,
126            } => write!(
127                f,
128                "regex pattern too large ({} bytes, max {} bytes)",
129                patter_size, MAX_REGEX_SIZE_BEFORE_COMPILATION
130            ),
131        }
132    }
133}
134
135impl From<Error> for RegexCompilationError {
136    fn from(e: Error) -> Self {
137        RegexCompilationError::RegexError(e)
138    }
139}
140
141impl PartialEq<Regex> for Regex {
142    fn eq(&self, other: &Regex) -> bool {
143        self.pattern() == other.pattern()
144            && self.case_insensitive == other.case_insensitive
145            && self.dot_matches_new_line == other.dot_matches_new_line
146    }
147}
148
149impl Eq for Regex {}
150
151impl PartialOrd for Regex {
152    fn partial_cmp(&self, other: &Regex) -> Option<Ordering> {
153        Some(self.cmp(other))
154    }
155}
156
157impl Ord for Regex {
158    fn cmp(&self, other: &Regex) -> Ordering {
159        (
160            self.pattern(),
161            self.case_insensitive,
162            self.dot_matches_new_line,
163        )
164            .cmp(&(
165                other.pattern(),
166                other.case_insensitive,
167                other.dot_matches_new_line,
168            ))
169    }
170}
171
172impl Hash for Regex {
173    fn hash<H: Hasher>(&self, hasher: &mut H) {
174        self.pattern().hash(hasher);
175        self.case_insensitive.hash(hasher);
176        self.dot_matches_new_line.hash(hasher);
177    }
178}
179
180impl Deref for Regex {
181    type Target = regex::Regex;
182
183    fn deref(&self) -> &regex::Regex {
184        &self.regex
185    }
186}
187
188impl Serialize for Regex {
189    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
190    where
191        S: Serializer,
192    {
193        let mut state = serializer.serialize_struct("Regex", 3)?;
194        state.serialize_field("pattern", &self.pattern())?;
195        state.serialize_field("case_insensitive", &self.case_insensitive)?;
196        state.serialize_field("dot_matches_new_line", &self.dot_matches_new_line)?;
197        state.end()
198    }
199}
200
201impl<'de> Deserialize<'de> for Regex {
202    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
203    where
204        D: Deserializer<'de>,
205    {
206        enum Field {
207            Pattern,
208            CaseInsensitive,
209            DotMatchesNewLine,
210        }
211
212        impl<'de> Deserialize<'de> for Field {
213            fn deserialize<D>(deserializer: D) -> Result<Field, D::Error>
214            where
215                D: Deserializer<'de>,
216            {
217                struct FieldVisitor;
218
219                impl<'de> de::Visitor<'de> for FieldVisitor {
220                    type Value = Field;
221
222                    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
223                        formatter.write_str(
224                            "pattern string or case_insensitive bool or dot_matches_new_line bool",
225                        )
226                    }
227
228                    fn visit_str<E>(self, value: &str) -> Result<Field, E>
229                    where
230                        E: de::Error,
231                    {
232                        match value {
233                            "pattern" => Ok(Field::Pattern),
234                            "case_insensitive" => Ok(Field::CaseInsensitive),
235                            "dot_matches_new_line" => Ok(Field::DotMatchesNewLine),
236                            _ => Err(de::Error::unknown_field(value, FIELDS)),
237                        }
238                    }
239                }
240
241                deserializer.deserialize_identifier(FieldVisitor)
242            }
243        }
244
245        struct RegexVisitor;
246
247        impl<'de> de::Visitor<'de> for RegexVisitor {
248            type Value = Regex;
249
250            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
251                formatter.write_str("Regex serialized by the manual Serialize impl from above")
252            }
253
254            fn visit_seq<V>(self, mut seq: V) -> Result<Regex, V::Error>
255            where
256                V: de::SeqAccess<'de>,
257            {
258                let pattern = seq
259                    .next_element::<Cow<str>>()?
260                    .ok_or_else(|| de::Error::invalid_length(0, &self))?;
261                let case_insensitive = seq
262                    .next_element()?
263                    .ok_or_else(|| de::Error::invalid_length(1, &self))?;
264                let dot_matches_new_line = seq
265                    .next_element()?
266                    .ok_or_else(|| de::Error::invalid_length(2, &self))?;
267                Regex::new_dot_matches_new_line(&pattern, case_insensitive, dot_matches_new_line)
268                    .map_err(|err| {
269                        V::Error::custom(format!(
270                            "Unable to recreate regex during deserialization: {}",
271                            err
272                        ))
273                    })
274            }
275
276            fn visit_map<V>(self, mut map: V) -> Result<Regex, V::Error>
277            where
278                V: de::MapAccess<'de>,
279            {
280                let mut pattern: Option<Cow<str>> = None;
281                let mut case_insensitive: Option<bool> = None;
282                let mut dot_matches_new_line: Option<bool> = None;
283                while let Some(key) = map.next_key()? {
284                    match key {
285                        Field::Pattern => {
286                            if pattern.is_some() {
287                                return Err(de::Error::duplicate_field("pattern"));
288                            }
289                            pattern = Some(map.next_value()?);
290                        }
291                        Field::CaseInsensitive => {
292                            if case_insensitive.is_some() {
293                                return Err(de::Error::duplicate_field("case_insensitive"));
294                            }
295                            case_insensitive = Some(map.next_value()?);
296                        }
297                        Field::DotMatchesNewLine => {
298                            if dot_matches_new_line.is_some() {
299                                return Err(de::Error::duplicate_field("dot_matches_new_line"));
300                            }
301                            dot_matches_new_line = Some(map.next_value()?);
302                        }
303                    }
304                }
305                let pattern = pattern.ok_or_else(|| de::Error::missing_field("pattern"))?;
306                let case_insensitive =
307                    case_insensitive.ok_or_else(|| de::Error::missing_field("case_insensitive"))?;
308                let dot_matches_new_line = dot_matches_new_line
309                    .ok_or_else(|| de::Error::missing_field("dot_matches_new_line"))?;
310                Regex::new_dot_matches_new_line(&pattern, case_insensitive, dot_matches_new_line)
311                    .map_err(|err| {
312                        V::Error::custom(format!(
313                            "Unable to recreate regex during deserialization: {}",
314                            err
315                        ))
316                    })
317            }
318        }
319
320        const FIELDS: &[&str] = &["pattern", "case_insensitive", "dot_matches_new_line"];
321        deserializer.deserialize_struct("Regex", FIELDS, RegexVisitor)
322    }
323}
324
325#[cfg(test)]
326mod tests {
327    use super::*;
328
329    /// This was failing before due to the derived serde serialization being incorrect, because of
330    /// <https://github.com/tailhook/serde-regex/issues/14>.
331    /// Nowadays, we use our own handwritten Serialize/Deserialize impls for our Regex wrapper struct.
332    #[mz_ore::test]
333    fn regex_serde_case_insensitive() {
334        let pattern = "AAA";
335        let orig_regex = Regex::new(pattern, true).unwrap();
336        let serialized: String = serde_json::to_string(&orig_regex).unwrap();
337        let roundtrip_result: Regex = serde_json::from_str(&serialized).unwrap();
338        // Equality test between orig and roundtrip_result wouldn't work, because Eq doesn't test
339        // the actual regex object. So test the actual regex functionality (concentrating on case
340        // sensitivity).
341        assert_eq!(orig_regex.regex.is_match("aaa"), true);
342        assert_eq!(roundtrip_result.regex.is_match("aaa"), true);
343        assert_eq!(pattern, roundtrip_result.pattern());
344    }
345
346    /// Test the roundtripping of `dot_matches_new_line`.
347    /// (Similar to the above `regex_serde_case_insensitive`.)
348    #[mz_ore::test]
349    fn regex_serde_dot_matches_new_line() {
350        {
351            // dot_matches_new_line: true
352            let pattern = "A.*B";
353            let orig_regex = Regex::new_dot_matches_new_line(pattern, true, true).unwrap();
354            let serialized: String = serde_json::to_string(&orig_regex).unwrap();
355            let roundtrip_result: Regex = serde_json::from_str(&serialized).unwrap();
356            assert_eq!(orig_regex.regex.is_match("axxx\nxxxb"), true);
357            assert_eq!(roundtrip_result.regex.is_match("axxx\nxxxb"), true);
358            assert_eq!(pattern, roundtrip_result.pattern());
359        }
360        {
361            // dot_matches_new_line: false
362            let pattern = "A.*B";
363            let orig_regex = Regex::new_dot_matches_new_line(pattern, true, false).unwrap();
364            let serialized: String = serde_json::to_string(&orig_regex).unwrap();
365            let roundtrip_result: Regex = serde_json::from_str(&serialized).unwrap();
366            assert_eq!(orig_regex.regex.is_match("axxx\nxxxb"), false);
367            assert_eq!(roundtrip_result.regex.is_match("axxx\nxxxb"), false);
368            assert_eq!(pattern, roundtrip_result.pattern());
369        }
370        {
371            // dot_matches_new_line: default
372            let pattern = "A.*B";
373            let orig_regex = Regex::new(pattern, true).unwrap();
374            let serialized: String = serde_json::to_string(&orig_regex).unwrap();
375            let roundtrip_result: Regex = serde_json::from_str(&serialized).unwrap();
376            assert_eq!(orig_regex.regex.is_match("axxx\nxxxb"), true);
377            assert_eq!(roundtrip_result.regex.is_match("axxx\nxxxb"), true);
378            assert_eq!(pattern, roundtrip_result.pattern());
379        }
380    }
381
382    #[mz_ore::test]
383    fn regex_serde_from_reader() {
384        let pattern = "A.*B";
385        let orig_regex = Regex::new_dot_matches_new_line(pattern, true, true).unwrap();
386
387        let serialized: String = serde_json::to_string(&orig_regex).unwrap();
388        let roundtrip_result: Regex = serde_json::from_reader(serialized.as_bytes()).unwrap();
389
390        assert_eq!(orig_regex.regex.is_match("axxx\nxxxb"), true);
391        assert_eq!(roundtrip_result.regex.is_match("axxx\nxxxb"), true);
392        assert_eq!(pattern, roundtrip_result.pattern());
393
394        let serialized = bincode::serialize(&orig_regex).unwrap();
395        let roundtrip_result: Regex = bincode::deserialize_from(&*serialized).unwrap();
396
397        assert_eq!(orig_regex.regex.is_match("axxx\nxxxb"), true);
398        assert_eq!(roundtrip_result.regex.is_match("axxx\nxxxb"), true);
399        assert_eq!(pattern, roundtrip_result.pattern());
400    }
401}
mz_repr/adt/regex.rs

mz_repr/adt/
regex.rs
