bk_promql_parser/label/
matcher.rs

1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::fmt;
16use std::hash::{Hash, Hasher};
17
18use regex::Regex;
19
20use crate::parser::token::{token_display, TokenId, T_EQL, T_EQL_REGEX, T_NEQ, T_NEQ_REGEX};
21use crate::util::join_vector;
22
23#[derive(Debug, Clone)]
24pub enum MatchOp {
25    Equal,
26    NotEqual,
27    Re(Regex),
28    NotRe(Regex),
29}
30
31impl fmt::Display for MatchOp {
32    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
33        match self {
34            MatchOp::Equal => write!(f, "="),
35            MatchOp::NotEqual => write!(f, "!="),
36            MatchOp::Re(_reg) => write!(f, "=~"),
37            MatchOp::NotRe(_reg) => write!(f, "!~"),
38        }
39    }
40}
41
42impl PartialEq for MatchOp {
43    fn eq(&self, other: &Self) -> bool {
44        match (self, other) {
45            (MatchOp::Equal, MatchOp::Equal) => true,
46            (MatchOp::NotEqual, MatchOp::NotEqual) => true,
47            (MatchOp::Re(s), MatchOp::Re(o)) => s.as_str().eq(o.as_str()),
48            (MatchOp::NotRe(s), MatchOp::NotRe(o)) => s.as_str().eq(o.as_str()),
49            _ => false,
50        }
51    }
52}
53
54impl Eq for MatchOp {}
55
56impl Hash for MatchOp {
57    fn hash<H: Hasher>(&self, state: &mut H) {
58        match self {
59            MatchOp::Equal => "eq".hash(state),
60            MatchOp::NotEqual => "ne".hash(state),
61            MatchOp::Re(s) => format!("re:{}", s.as_str()).hash(state),
62            MatchOp::NotRe(s) => format!("nre:{}", s.as_str()).hash(state),
63        }
64    }
65}
66
67// Matcher models the matching of a label.
68#[derive(Debug, Clone, PartialEq, Eq, Hash)]
69pub struct Matcher {
70    pub op: MatchOp,
71    pub name: String,
72    pub value: String,
73    pub is_or: bool,
74}
75
76impl Matcher {
77    pub fn new(op: MatchOp, name: &str, value: &str) -> Self {
78        Self {
79            op,
80            name: name.into(),
81            value: value.into(),
82            is_or: false,
83        }
84    }
85
86    pub fn new_or(op: MatchOp, name: &str, value: &str) -> Self {
87        Self {
88            op,
89            name: name.into(),
90            value: value.into(),
91            is_or: true,
92        }
93    }
94
95    /// matches returns whether the matcher matches the given string value.
96    pub fn is_match(&self, s: &str) -> bool {
97        match &self.op {
98            MatchOp::Equal => self.value.eq(s),
99            MatchOp::NotEqual => self.value.ne(s),
100            MatchOp::Re(r) => r.is_match(s),
101            MatchOp::NotRe(r) => !r.is_match(s),
102        }
103    }
104
105    // Go and Rust handle the repeat pattern differently
106    // in Go the following is valid: `aaa{bbb}ccc`
107    // in Rust {bbb} is seen as an invalid repeat and must be ecaped \{bbb}
108    // This escapes the opening { if its not followed by valid repeat pattern (e.g. 4,6).
109    fn try_parse_re(re: &str) -> Result<Regex, String> {
110        Regex::new(re)
111            .or_else(|_| Regex::new(&try_escape_for_repeat_re(re)))
112            .map_err(|_| format!("illegal regex for {re}",))
113    }
114
115    pub fn new_matcher(id: TokenId, name: String, value: String) -> Result<Matcher, String> {
116        let op = Self::find_matcher_op(id, &value)?;
117        op.map(|op| Matcher::new(op, name.as_str(), value.as_str()))
118    }
119
120    pub fn new_matcher_or(id: TokenId, name: String, value: String) -> Result<Matcher, String> {
121        let op = Self::find_matcher_op(id, &value)?;
122        op.map(|op| Matcher::new_or(op, name.as_str(), value.as_str()))
123    }
124
125    fn find_matcher_op(id: TokenId, value: &str) -> Result<Result<MatchOp, String>, String> {
126        let op = match id {
127            T_EQL => Ok(MatchOp::Equal),
128            T_NEQ => Ok(MatchOp::NotEqual),
129            T_EQL_REGEX => Ok(MatchOp::Re(Matcher::try_parse_re(value)?)),
130            T_NEQ_REGEX => Ok(MatchOp::NotRe(Matcher::try_parse_re(value)?)),
131            _ => Err(format!("invalid match op {}", token_display(id))),
132        };
133        Ok(op)
134    }
135}
136
137impl fmt::Display for Matcher {
138    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
139        write!(f, "{}{}\"{}\"", self.name, self.op, self.value)
140    }
141}
142
143// Go and Rust handle the repeat pattern differently
144// in Go the following is valid: `aaa{bbb}ccc`
145// in Rust {bbb} is seen as an invalid repeat and must be ecaped \{bbb}
146// This escapes the opening { if its not followed by valid repeat pattern (e.g. 4,6).
147fn try_escape_for_repeat_re(re: &str) -> String {
148    fn is_repeat(chars: &mut std::str::Chars<'_>) -> (bool, String) {
149        let mut buf = String::new();
150        let mut comma_seen = false;
151        for c in chars.by_ref() {
152            buf.push(c);
153            match c {
154                ',' if comma_seen => {
155                    return (false, buf); // ,, is invalid
156                }
157                ',' if buf == "," => {
158                    return (false, buf); // {, is invalid
159                }
160                ',' if !comma_seen => comma_seen = true,
161                '}' if buf == "}" => {
162                    return (false, buf); // {} is invalid
163                }
164                '}' => {
165                    return (true, buf);
166                }
167                _ if c.is_ascii_digit() => continue,
168                _ => {
169                    return (false, buf); // false if visit non-digit char
170                }
171            }
172        }
173        (false, buf) // not ended with }
174    }
175
176    let mut result = String::with_capacity(re.len() + 1);
177    let mut chars = re.chars();
178
179    while let Some(c) = chars.next() {
180        match c {
181            '\\' => {
182                if let Some(cc) = chars.next() {
183                    result.push(c);
184                    result.push(cc);
185                }
186            }
187            '{' => {
188                let (is, s) = is_repeat(&mut chars);
189                if !is {
190                    result.push('\\');
191                }
192                result.push(c);
193                result.push_str(&s);
194            }
195            _ => result.push(c),
196        }
197    }
198    result
199}
200
201#[derive(Debug, Clone, PartialEq, Eq)]
202pub struct Matchers {
203    pub matchers: Vec<Matcher>,
204}
205
206impl Matchers {
207    pub fn empty() -> Self {
208        Self { matchers: vec![] }
209    }
210
211    pub fn one(matcher: Matcher) -> Self {
212        let matchers = vec![matcher];
213        Self { matchers }
214    }
215
216    pub fn new(matchers: Vec<Matcher>) -> Self {
217        Self { matchers }
218    }
219
220    pub fn append(mut self, matcher: Matcher) -> Self {
221        self.matchers.push(matcher);
222        self
223    }
224
225    /// Vector selectors must either specify a name or at least one label
226    /// matcher that does not match the empty string.
227    ///
228    /// The following expression is illegal:
229    /// {job=~".*"} # Bad!
230    pub fn is_empty_matchers(&self) -> bool {
231        self.matchers.is_empty() || self.matchers.iter().all(|m| m.is_match(""))
232    }
233
234    /// find the matcher's value whose name equals the specified name. This function
235    /// is designed to prepare error message of invalid promql expression.
236    pub(crate) fn find_matcher_value(&self, name: &str) -> Option<String> {
237        for m in &self.matchers {
238            if m.name.eq(name) {
239                return Some(m.value.clone());
240            }
241        }
242        None
243    }
244
245    /// find matchers whose name equals the specified name
246    pub fn find_matchers(&self, name: &str) -> Vec<Matcher> {
247        self.matchers
248            .iter()
249            .filter(|m| m.name.eq(name))
250            .cloned()
251            .collect()
252    }
253}
254
255impl fmt::Display for Matchers {
256    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
257        let not_contains_or = &self.matchers.iter().all(|matcher| !matcher.is_or);
258        if *not_contains_or {
259            write!(f, "{}", join_vector(&self.matchers, ",", true))
260        } else {
261            let matchers_str = self
262                .matchers
263                .iter()
264                .map(|matcher| {
265                    if matcher.is_or {
266                        format!(" or {}", matcher)
267                    } else {
268                        format!(",{}", matcher)
269                    }
270                })
271                .collect::<String>();
272            write!(f, "{}", matchers_str.trim_start_matches(','))
273        }
274    }
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280    use crate::parser::token;
281    use std::collections::hash_map::DefaultHasher;
282
283    fn hash<H>(op: H) -> u64
284    where
285        H: Hash,
286    {
287        let mut hasher = DefaultHasher::new();
288        op.hash(&mut hasher);
289        hasher.finish()
290    }
291
292    #[test]
293    fn test_new_matcher() {
294        assert_eq!(
295            Matcher::new_matcher(token::T_ADD, "".into(), "".into()),
296            Err(format!("invalid match op {}", token_display(token::T_ADD)))
297        )
298    }
299
300    #[test]
301    fn test_matcher_op_eq() {
302        assert_eq!(MatchOp::Equal, MatchOp::Equal);
303        assert_eq!(MatchOp::NotEqual, MatchOp::NotEqual);
304        assert_eq!(
305            MatchOp::Re(Regex::new("\\s+").unwrap()),
306            MatchOp::Re(Regex::new("\\s+").unwrap())
307        );
308        assert_eq!(
309            MatchOp::NotRe(Regex::new("\\s+").unwrap()),
310            MatchOp::NotRe(Regex::new("\\s+").unwrap())
311        );
312
313        assert_ne!(MatchOp::Equal, MatchOp::NotEqual);
314        assert_ne!(
315            MatchOp::NotEqual,
316            MatchOp::NotRe(Regex::new("\\s+").unwrap())
317        );
318        assert_ne!(
319            MatchOp::Re(Regex::new("\\s+").unwrap()),
320            MatchOp::NotRe(Regex::new("\\s+").unwrap())
321        );
322    }
323
324    #[test]
325    fn test_matchop_hash() {
326        assert_eq!(hash(MatchOp::Equal), hash(MatchOp::Equal));
327        assert_eq!(hash(MatchOp::NotEqual), hash(MatchOp::NotEqual));
328        assert_eq!(
329            hash(MatchOp::Re(Regex::new("\\s+").unwrap())),
330            hash(MatchOp::Re(Regex::new("\\s+").unwrap()))
331        );
332        assert_eq!(
333            hash(MatchOp::NotRe(Regex::new("\\s+").unwrap())),
334            hash(MatchOp::NotRe(Regex::new("\\s+").unwrap()))
335        );
336
337        assert_ne!(hash(MatchOp::Equal), hash(MatchOp::NotEqual));
338        assert_ne!(
339            hash(MatchOp::NotEqual),
340            hash(MatchOp::NotRe(Regex::new("\\s+").unwrap()))
341        );
342        assert_ne!(
343            hash(MatchOp::Re(Regex::new("\\s+").unwrap())),
344            hash(MatchOp::NotRe(Regex::new("\\s+").unwrap()))
345        );
346    }
347
348    #[test]
349    fn test_matcher_hash() {
350        assert_eq!(
351            hash(Matcher::new(MatchOp::Equal, "name", "value")),
352            hash(Matcher::new(MatchOp::Equal, "name", "value")),
353        );
354
355        assert_eq!(
356            hash(Matcher::new(MatchOp::NotEqual, "name", "value")),
357            hash(Matcher::new(MatchOp::NotEqual, "name", "value")),
358        );
359
360        assert_eq!(
361            hash(Matcher::new(
362                MatchOp::Re(Regex::new("\\s+").unwrap()),
363                "name",
364                "\\s+"
365            )),
366            hash(Matcher::new(
367                MatchOp::Re(Regex::new("\\s+").unwrap()),
368                "name",
369                "\\s+"
370            )),
371        );
372
373        assert_eq!(
374            hash(Matcher::new(
375                MatchOp::NotRe(Regex::new("\\s+").unwrap()),
376                "name",
377                "\\s+"
378            )),
379            hash(Matcher::new(
380                MatchOp::NotRe(Regex::new("\\s+").unwrap()),
381                "name",
382                "\\s+"
383            )),
384        );
385
386        assert_ne!(
387            hash(Matcher::new(MatchOp::Equal, "name", "value")),
388            hash(Matcher::new(MatchOp::NotEqual, "name", "value")),
389        );
390
391        assert_ne!(
392            hash(Matcher::new(
393                MatchOp::Re(Regex::new("\\s+").unwrap()),
394                "name",
395                "\\s+"
396            )),
397            hash(Matcher::new(
398                MatchOp::NotRe(Regex::new("\\s+").unwrap()),
399                "name",
400                "\\s+"
401            )),
402        );
403    }
404
405    #[test]
406    fn test_matcher_eq_ne() {
407        let op = MatchOp::Equal;
408        let matcher = Matcher::new(op, "name", "up");
409        assert!(matcher.is_match("up"));
410        assert!(!matcher.is_match("down"));
411
412        let op = MatchOp::NotEqual;
413        let matcher = Matcher::new(op, "name", "up");
414        assert!(matcher.is_match("foo"));
415        assert!(matcher.is_match("bar"));
416        assert!(!matcher.is_match("up"));
417    }
418
419    #[test]
420    fn test_matcher_re() {
421        let value = "api/v1/.*";
422        let re = Regex::new(value).unwrap();
423        let op = MatchOp::Re(re);
424        let matcher = Matcher::new(op, "name", value);
425        assert!(matcher.is_match("api/v1/query"));
426        assert!(matcher.is_match("api/v1/range_query"));
427        assert!(!matcher.is_match("api/v2"));
428    }
429
430    #[test]
431    fn test_eq_matcher_equality() {
432        assert_eq!(
433            Matcher::new(MatchOp::Equal, "code", "200"),
434            Matcher::new(MatchOp::Equal, "code", "200")
435        );
436
437        assert_ne!(
438            Matcher::new(MatchOp::Equal, "code", "200"),
439            Matcher::new(MatchOp::Equal, "code", "201")
440        );
441
442        assert_ne!(
443            Matcher::new(MatchOp::Equal, "code", "200"),
444            Matcher::new(MatchOp::NotEqual, "code", "200")
445        );
446    }
447
448    #[test]
449    fn test_ne_matcher_equality() {
450        assert_eq!(
451            Matcher::new(MatchOp::NotEqual, "code", "200"),
452            Matcher::new(MatchOp::NotEqual, "code", "200")
453        );
454
455        assert_ne!(
456            Matcher::new(MatchOp::NotEqual, "code", "200"),
457            Matcher::new(MatchOp::NotEqual, "code", "201")
458        );
459
460        assert_ne!(
461            Matcher::new(MatchOp::NotEqual, "code", "200"),
462            Matcher::new(MatchOp::Equal, "code", "200")
463        );
464    }
465
466    #[test]
467    fn test_re_matcher_equality() {
468        assert_eq!(
469            Matcher::new(MatchOp::Re(Regex::new("2??").unwrap()), "code", "2??",),
470            Matcher::new(MatchOp::Re(Regex::new("2??").unwrap()), "code", "2??",)
471        );
472
473        assert_ne!(
474            Matcher::new(MatchOp::Re(Regex::new("2??").unwrap()), "code", "2??",),
475            Matcher::new(MatchOp::Re(Regex::new("2??").unwrap()), "code", "2*?",)
476        );
477
478        assert_ne!(
479            Matcher::new(MatchOp::Re(Regex::new("2??").unwrap()), "code", "2??",),
480            Matcher::new(MatchOp::Equal, "code", "2??")
481        );
482    }
483
484    #[test]
485    fn test_not_re_matcher_equality() {
486        assert_eq!(
487            Matcher::new(MatchOp::NotRe(Regex::new("2??").unwrap()), "code", "2??",),
488            Matcher::new(MatchOp::NotRe(Regex::new("2??").unwrap()), "code", "2??",)
489        );
490
491        assert_ne!(
492            Matcher::new(MatchOp::NotRe(Regex::new("2??").unwrap()), "code", "2??",),
493            Matcher::new(MatchOp::NotRe(Regex::new("2?*").unwrap()), "code", "2*?",)
494        );
495
496        assert_ne!(
497            Matcher::new(MatchOp::NotRe(Regex::new("2??").unwrap()), "code", "2??",),
498            Matcher::new(MatchOp::Equal, "code", "2??")
499        );
500    }
501
502    #[test]
503    fn test_matchers_equality() {
504        assert_eq!(
505            Matchers::empty()
506                .append(Matcher::new(MatchOp::Equal, "name1", "val1"))
507                .append(Matcher::new(MatchOp::Equal, "name2", "val2")),
508            Matchers::empty()
509                .append(Matcher::new(MatchOp::Equal, "name1", "val1"))
510                .append(Matcher::new(MatchOp::Equal, "name2", "val2"))
511        );
512
513        assert_ne!(
514            Matchers::empty().append(Matcher::new(MatchOp::Equal, "name1", "val1")),
515            Matchers::empty().append(Matcher::new(MatchOp::Equal, "name2", "val2"))
516        );
517
518        assert_ne!(
519            Matchers::empty().append(Matcher::new(MatchOp::Equal, "name1", "val1")),
520            Matchers::empty().append(Matcher::new(MatchOp::NotEqual, "name1", "val1"))
521        );
522
523        assert_eq!(
524            Matchers::empty()
525                .append(Matcher::new(MatchOp::Equal, "name1", "val1"))
526                .append(Matcher::new(MatchOp::NotEqual, "name2", "val2"))
527                .append(Matcher::new(
528                    MatchOp::Re(Regex::new("\\d+").unwrap()),
529                    "name2",
530                    "\\d+"
531                ))
532                .append(Matcher::new(
533                    MatchOp::NotRe(Regex::new("\\d+").unwrap()),
534                    "name2",
535                    "\\d+"
536                )),
537            Matchers::empty()
538                .append(Matcher::new(MatchOp::Equal, "name1", "val1"))
539                .append(Matcher::new(MatchOp::NotEqual, "name2", "val2"))
540                .append(Matcher::new(
541                    MatchOp::Re(Regex::new("\\d+").unwrap()),
542                    "name2",
543                    "\\d+"
544                ))
545                .append(Matcher::new(
546                    MatchOp::NotRe(Regex::new("\\d+").unwrap()),
547                    "name2",
548                    "\\d+"
549                ))
550        );
551    }
552
553    #[test]
554    fn test_find_matchers() {
555        let matchers = Matchers::empty()
556            .append(Matcher::new(MatchOp::Equal, "foo", "bar"))
557            .append(Matcher::new(MatchOp::NotEqual, "foo", "bar"))
558            .append(Matcher::new_matcher(T_EQL_REGEX, "foo".into(), "bar".into()).unwrap())
559            .append(Matcher::new_matcher(T_NEQ_REGEX, "foo".into(), "bar".into()).unwrap())
560            .append(Matcher::new(MatchOp::Equal, "FOO", "bar"))
561            .append(Matcher::new(MatchOp::NotEqual, "bar", "bar"));
562
563        let ms = matchers.find_matchers("foo");
564        assert_eq!(4, ms.len());
565    }
566
567    #[test]
568    fn test_convert_re() {
569        assert_eq!(try_escape_for_repeat_re("abc{}"), r"abc\{}");
570        assert_eq!(try_escape_for_repeat_re("abc{def}"), r"abc\{def}");
571        assert_eq!(try_escape_for_repeat_re("abc{def"), r"abc\{def");
572        assert_eq!(try_escape_for_repeat_re("abc{1}"), "abc{1}");
573        assert_eq!(try_escape_for_repeat_re("abc{1,}"), "abc{1,}");
574        assert_eq!(try_escape_for_repeat_re("abc{1,2}"), "abc{1,2}");
575        assert_eq!(try_escape_for_repeat_re("abc{,2}"), r"abc\{,2}");
576        assert_eq!(try_escape_for_repeat_re("abc{{1,2}}"), r"abc\{{1,2}}");
577        assert_eq!(try_escape_for_repeat_re(r"abc\{abc"), r"abc\{abc");
578        assert_eq!(try_escape_for_repeat_re("abc{1a}"), r"abc\{1a}");
579        assert_eq!(try_escape_for_repeat_re("abc{1,a}"), r"abc\{1,a}");
580        assert_eq!(try_escape_for_repeat_re("abc{1,2a}"), r"abc\{1,2a}");
581        assert_eq!(try_escape_for_repeat_re("abc{1,2,3}"), r"abc\{1,2,3}");
582        assert_eq!(try_escape_for_repeat_re("abc{1,,2}"), r"abc\{1,,2}");
583    }
584}
bk_promql_parser/label/matcher.rs

bk_promql_parser/label/
matcher.rs
