sockudo_filter/
lib.rs

1pub mod node;
2mod ops;
3
4pub use node::FilterNode;
5pub use ops::{CompareOp, LogicalOp};
6
7use ahash::AHashMap as HashMap;
8use memchr::memmem;
9use std::collections::BTreeMap; // SIMD-accelerated substring search
10
11/// Trait for map types that can be used with filter matching
12/// Supports both HashMap and BTreeMap
13pub trait TagMap {
14    fn get_tag(&self, key: &str) -> Option<&String>;
15    fn contains_tag(&self, key: &str) -> bool;
16}
17
18impl TagMap for HashMap<String, String> {
19    #[inline]
20    fn get_tag(&self, key: &str) -> Option<&String> {
21        self.get(key)
22    }
23
24    #[inline]
25    fn contains_tag(&self, key: &str) -> bool {
26        self.contains_key(key)
27    }
28}
29
30impl TagMap for BTreeMap<String, String> {
31    #[inline]
32    fn get_tag(&self, key: &str) -> Option<&String> {
33        self.get(key)
34    }
35
36    #[inline]
37    fn contains_tag(&self, key: &str) -> bool {
38        self.contains_key(key)
39    }
40}
41
42/// Matches a filter node against publication tags with zero allocations.
43///
44/// This function is designed to be called in the hot path during message broadcasting,
45/// so it must not allocate any memory during evaluation.
46///
47/// # Arguments
48/// * `filter` - The filter node to evaluate
49/// * `tags` - Publication tags to match against (supports HashMap or BTreeMap)
50///
51/// # Returns
52/// `true` if the filter matches, `false` otherwise
53#[inline]
54pub fn matches<T: TagMap>(filter: &FilterNode, tags: &T) -> bool {
55    match filter.logical_op() {
56        Some(LogicalOp::And) => {
57            // Early exit on first false
58            for child in filter.nodes() {
59                if !matches(child, tags) {
60                    return false;
61                }
62            }
63            true
64        }
65        Some(LogicalOp::Or) => {
66            // Early exit on first true
67            for child in filter.nodes() {
68                if matches(child, tags) {
69                    return true;
70                }
71            }
72            false
73        }
74        Some(LogicalOp::Not) => {
75            // NOT should have exactly one child
76            if let Some(child) = filter.nodes().first() {
77                !matches(child, tags)
78            } else {
79                false
80            }
81        }
82        None => {
83            // Leaf node - perform comparison
84            evaluate_comparison(filter, tags)
85        }
86    }
87}
88
89/// Evaluates a comparison operation (leaf node) with zero allocations.
90#[inline]
91fn evaluate_comparison<T: TagMap>(filter: &FilterNode, tags: &T) -> bool {
92    let key = filter.key();
93    let tag_value = tags.get_tag(key);
94
95    match filter.compare_op() {
96        CompareOp::Equal => {
97            if let Some(val) = tag_value {
98                val == filter.val()
99            } else {
100                false
101            }
102        }
103        CompareOp::NotEqual => {
104            if let Some(val) = tag_value {
105                val != filter.val()
106            } else {
107                true
108            }
109        }
110        CompareOp::In => {
111            if let Some(val) = tag_value {
112                // Use binary search for O(log n) lookup if sorted (large value sets)
113                // Otherwise fall back to linear search for small sets
114                if filter.is_sorted() {
115                    filter.vals().binary_search(val).is_ok()
116                } else {
117                    filter.vals().iter().any(|v| v == val)
118                }
119            } else {
120                false
121            }
122        }
123        CompareOp::NotIn => {
124            if let Some(val) = tag_value {
125                // Use binary search for O(log n) lookup if sorted (large value sets)
126                if filter.is_sorted() {
127                    filter.vals().binary_search(val).is_err()
128                } else {
129                    !filter.vals().iter().any(|v| v == val)
130                }
131            } else {
132                true
133            }
134        }
135        CompareOp::Exists => tag_value.is_some(),
136        CompareOp::NotExists => tag_value.is_none(),
137        CompareOp::StartsWith => {
138            if let Some(val) = tag_value {
139                // Fast path: Use built-in for short strings (CPU cache friendly)
140                // SIMD path: Use memchr for longer strings (>16 bytes)
141                let filter_val = filter.val();
142                if filter_val.len() <= 16 {
143                    val.starts_with(filter_val)
144                } else {
145                    val.as_bytes().starts_with(filter_val.as_bytes())
146                }
147            } else {
148                false
149            }
150        }
151        CompareOp::EndsWith => {
152            if let Some(val) = tag_value {
153                // Fast path: Use built-in for short strings
154                let filter_val = filter.val();
155                if filter_val.len() <= 16 {
156                    val.ends_with(filter_val)
157                } else {
158                    val.as_bytes().ends_with(filter_val.as_bytes())
159                }
160            } else {
161                false
162            }
163        }
164        CompareOp::Contains => {
165            if let Some(val) = tag_value {
166                // SIMD-optimized substring search using memchr (up to 10x faster)
167                let filter_val = filter.val();
168                if filter_val.is_empty() {
169                    true
170                } else if filter_val.len() == 1 {
171                    // Single byte search (fastest SIMD path)
172                    memchr::memchr(filter_val.as_bytes()[0], val.as_bytes()).is_some()
173                } else {
174                    // Multi-byte substring search with SIMD
175                    memmem::find(val.as_bytes(), filter_val.as_bytes()).is_some()
176                }
177            } else {
178                false
179            }
180        }
181        CompareOp::GreaterThan => compare_numeric(tag_value, filter.val(), |a, b| a > b),
182        CompareOp::GreaterThanOrEqual => compare_numeric(tag_value, filter.val(), |a, b| a >= b),
183        CompareOp::LessThan => compare_numeric(tag_value, filter.val(), |a, b| a < b),
184        CompareOp::LessThanOrEqual => compare_numeric(tag_value, filter.val(), |a, b| a <= b),
185    }
186}
187
188/// Compares two string values as numbers with zero allocations.
189/// Uses a simple decimal comparison that handles both integers and decimals.
190#[inline]
191fn compare_numeric<F>(tag_value: Option<&String>, filter_val: &str, cmp: F) -> bool
192where
193    F: Fn(f64, f64) -> bool,
194{
195    if let Some(val) = tag_value {
196        // Fast path: try to parse both as f64
197        if let (Ok(a), Ok(b)) = (val.parse::<f64>(), filter_val.parse::<f64>()) {
198            cmp(a, b)
199        } else {
200            false
201        }
202    } else {
203        false
204    }
205}
206
207#[cfg(test)]
208mod tests {
209    use crate::node::FilterNodeBuilder;
210
211    use super::*;
212
213    fn tags(pairs: &[(&str, &str)]) -> HashMap<String, String> {
214        pairs
215            .iter()
216            .map(|(k, v)| (k.to_string(), v.to_string()))
217            .collect()
218    }
219
220    #[test]
221    fn test_equal() {
222        let filter = FilterNodeBuilder::eq("event_type", "goal");
223        let matching_tags = tags(&[("event_type", "goal")]);
224        let non_matching_tags = tags(&[("event_type", "shot")]);
225
226        assert!(matches(&filter, &matching_tags));
227        assert!(!matches(&filter, &non_matching_tags));
228    }
229
230    #[test]
231    fn test_not_equal() {
232        let filter = FilterNodeBuilder::neq("event_type", "goal");
233        let matching_tags = tags(&[("event_type", "shot")]);
234        let non_matching_tags = tags(&[("event_type", "goal")]);
235
236        assert!(matches(&filter, &matching_tags));
237        assert!(!matches(&filter, &non_matching_tags));
238    }
239
240    #[test]
241    fn test_in() {
242        let filter = FilterNodeBuilder::in_set("event_type", &["goal", "shot"]);
243        let matching_goal = tags(&[("event_type", "goal")]);
244        let matching_shot = tags(&[("event_type", "shot")]);
245        let non_matching = tags(&[("event_type", "pass")]);
246
247        assert!(matches(&filter, &matching_goal));
248        assert!(matches(&filter, &matching_shot));
249        assert!(!matches(&filter, &non_matching));
250    }
251
252    #[test]
253    fn test_and() {
254        let filter = FilterNodeBuilder::and(vec![
255            FilterNodeBuilder::eq("event_type", "shot"),
256            FilterNodeBuilder::gte("xG", "0.8"),
257        ]);
258
259        let matching = tags(&[("event_type", "shot"), ("xG", "0.85")]);
260        let non_matching_type = tags(&[("event_type", "pass"), ("xG", "0.85")]);
261        let non_matching_value = tags(&[("event_type", "shot"), ("xG", "0.3")]);
262
263        assert!(matches(&filter, &matching));
264        assert!(!matches(&filter, &non_matching_type));
265        assert!(!matches(&filter, &non_matching_value));
266    }
267
268    #[test]
269    fn test_or() {
270        let filter = FilterNodeBuilder::or(vec![
271            FilterNodeBuilder::eq("event_type", "goal"),
272            FilterNodeBuilder::and(vec![
273                FilterNodeBuilder::eq("event_type", "shot"),
274                FilterNodeBuilder::gte("xG", "0.8"),
275            ]),
276        ]);
277
278        let matching_goal = tags(&[("event_type", "goal")]);
279        let matching_shot = tags(&[("event_type", "shot"), ("xG", "0.85")]);
280        let non_matching = tags(&[("event_type", "shot"), ("xG", "0.3")]);
281
282        assert!(matches(&filter, &matching_goal));
283        assert!(matches(&filter, &matching_shot));
284        assert!(!matches(&filter, &non_matching));
285    }
286
287    #[test]
288    fn test_not() {
289        let filter = FilterNodeBuilder::not(FilterNodeBuilder::eq("event_type", "goal"));
290
291        let matching = tags(&[("event_type", "shot")]);
292        let non_matching = tags(&[("event_type", "goal")]);
293
294        assert!(matches(&filter, &matching));
295        assert!(!matches(&filter, &non_matching));
296    }
297
298    #[test]
299    fn test_not_in() {
300        let filter = FilterNodeBuilder::nin("event_type", &["goal", "shot"]);
301        let matching = tags(&[("event_type", "pass")]);
302        let non_matching = tags(&[("event_type", "goal")]);
303
304        assert!(matches(&filter, &matching));
305        assert!(!matches(&filter, &non_matching));
306    }
307
308    #[test]
309    fn test_exists() {
310        let filter = FilterNodeBuilder::exists("event_type");
311        let matching = tags(&[("event_type", "goal")]);
312        let non_matching = tags(&[("other_key", "value")]);
313
314        assert!(matches(&filter, &matching));
315        assert!(!matches(&filter, &non_matching));
316    }
317
318    #[test]
319    fn test_not_exists() {
320        let filter = FilterNodeBuilder::not_exists("event_type");
321        let matching = tags(&[("other_key", "value")]);
322        let non_matching = tags(&[("event_type", "goal")]);
323
324        assert!(matches(&filter, &matching));
325        assert!(!matches(&filter, &non_matching));
326    }
327
328    #[test]
329    fn test_starts_with() {
330        let filter = FilterNodeBuilder::starts_with("ticker", "GOO");
331        let matching = tags(&[("ticker", "GOOGLE")]);
332        let non_matching = tags(&[("ticker", "AAPL")]);
333
334        assert!(matches(&filter, &matching));
335        assert!(!matches(&filter, &non_matching));
336    }
337
338    #[test]
339    fn test_ends_with() {
340        let filter = FilterNodeBuilder::ends_with("ticker", "LE");
341        let matching = tags(&[("ticker", "GOOGLE")]);
342        let non_matching = tags(&[("ticker", "AAPL")]);
343
344        assert!(matches(&filter, &matching));
345        assert!(!matches(&filter, &non_matching));
346    }
347
348    #[test]
349    fn test_contains() {
350        let filter = FilterNodeBuilder::contains("ticker", "OOG");
351        let matching = tags(&[("ticker", "GOOGLE")]);
352        let non_matching = tags(&[("ticker", "AAPL")]);
353
354        assert!(matches(&filter, &matching));
355        assert!(!matches(&filter, &non_matching));
356    }
357
358    #[test]
359    fn test_greater_than() {
360        let filter = FilterNodeBuilder::gt("xG", "0.5");
361        let matching = tags(&[("xG", "0.85")]);
362        let non_matching = tags(&[("xG", "0.3")]);
363        let equal = tags(&[("xG", "0.5")]);
364
365        assert!(matches(&filter, &matching));
366        assert!(!matches(&filter, &non_matching));
367        assert!(!matches(&filter, &equal));
368    }
369
370    #[test]
371    fn test_greater_than_or_equal() {
372        let filter = FilterNodeBuilder::gte("xG", "0.5");
373        let matching_greater = tags(&[("xG", "0.85")]);
374        let matching_equal = tags(&[("xG", "0.5")]);
375        let non_matching = tags(&[("xG", "0.3")]);
376
377        assert!(matches(&filter, &matching_greater));
378        assert!(matches(&filter, &matching_equal));
379        assert!(!matches(&filter, &non_matching));
380    }
381
382    #[test]
383    fn test_less_than() {
384        let filter = FilterNodeBuilder::lt("xG", "0.5");
385        let matching = tags(&[("xG", "0.3")]);
386        let non_matching = tags(&[("xG", "0.85")]);
387        let equal = tags(&[("xG", "0.5")]);
388
389        assert!(matches(&filter, &matching));
390        assert!(!matches(&filter, &non_matching));
391        assert!(!matches(&filter, &equal));
392    }
393
394    #[test]
395    fn test_less_than_or_equal() {
396        let filter = FilterNodeBuilder::lte("xG", "0.5");
397        let matching_less = tags(&[("xG", "0.3")]);
398        let matching_equal = tags(&[("xG", "0.5")]);
399        let non_matching = tags(&[("xG", "0.85")]);
400
401        assert!(matches(&filter, &matching_less));
402        assert!(matches(&filter, &matching_equal));
403        assert!(!matches(&filter, &non_matching));
404    }
405
406    #[test]
407    fn test_complex_nested() {
408        let filter = FilterNodeBuilder::or(vec![
409            FilterNodeBuilder::eq("event_type", "goal"),
410            FilterNodeBuilder::and(vec![
411                FilterNodeBuilder::eq("event_type", "shot"),
412                FilterNodeBuilder::gte("xG", "0.8"),
413                FilterNodeBuilder::neq("outcome", "saved"),
414            ]),
415        ]);
416
417        let matching_goal = tags(&[("event_type", "goal")]);
418        let matching_dangerous_shot =
419            tags(&[("event_type", "shot"), ("xG", "0.85"), ("outcome", "goal")]);
420        let non_matching_saved_shot =
421            tags(&[("event_type", "shot"), ("xG", "0.85"), ("outcome", "saved")]);
422        let non_matching_low_xg = tags(&[("event_type", "shot"), ("xG", "0.3")]);
423
424        assert!(matches(&filter, &matching_goal));
425        assert!(matches(&filter, &matching_dangerous_shot));
426        assert!(!matches(&filter, &non_matching_saved_shot));
427        assert!(!matches(&filter, &non_matching_low_xg));
428    }
429
430    #[test]
431    fn test_numeric_comparison_integers() {
432        let filter = FilterNodeBuilder::gt("count", "42");
433        let matching = tags(&[("count", "100")]);
434        let non_matching = tags(&[("count", "10")]);
435
436        assert!(matches(&filter, &matching));
437        assert!(!matches(&filter, &non_matching));
438    }
439
440    #[test]
441    fn test_numeric_comparison_decimals() {
442        let filter = FilterNodeBuilder::gte("price", "99.5");
443        let matching_greater = tags(&[("price", "150.25")]);
444        let matching_equal = tags(&[("price", "99.5")]);
445        let non_matching = tags(&[("price", "50.0")]);
446
447        assert!(matches(&filter, &matching_greater));
448        assert!(matches(&filter, &matching_equal));
449        assert!(!matches(&filter, &non_matching));
450    }
451
452    #[test]
453    fn test_missing_key_in_comparison() {
454        let filter = FilterNodeBuilder::eq("event_type", "goal");
455        let empty_tags = tags(&[]);
456
457        assert!(!matches(&filter, &empty_tags));
458    }
459
460    #[test]
461    fn test_missing_key_in_numeric_comparison() {
462        let filter = FilterNodeBuilder::gt("count", "42");
463        let empty_tags = tags(&[]);
464
465        assert!(!matches(&filter, &empty_tags));
466    }
467
468    #[test]
469    fn test_and_filter_with_numeric_deserialization() {
470        let json = r#"{
471            "op": "and",
472            "nodes": [
473                {
474                    "key": "user_id",
475                    "cmp": "eq",
476                    "val": 12345
477                },
478                {
479                    "key": "status",
480                    "cmp": "eq",
481                    "val": "premium"
482                }
483            ]
484        }"#;
485
486        let filter: FilterNode = sonic_rs::from_str(json).unwrap();
487
488        let matching_tags = tags(&[("user_id", "12345"), ("status", "premium")]);
489        let non_matching_user = tags(&[("user_id", "99999"), ("status", "premium")]);
490        let non_matching_status = tags(&[("user_id", "12345"), ("status", "basic")]);
491
492        assert!(matches(&filter, &matching_tags));
493        assert!(!matches(&filter, &non_matching_user));
494        assert!(!matches(&filter, &non_matching_status));
495    }
496
497    #[test]
498    fn test_numeric_val_deserialization() {
499        let json = r#"{"key":"count","cmp":"eq","val":100}"#;
500        let filter: FilterNode = sonic_rs::from_str(json).unwrap();
501
502        assert_eq!(
503            filter.val,
504            Some("100".to_string()),
505            "Numeric val should be converted to string"
506        );
507
508        let test_tags = tags(&[("count", "100")]);
509        assert!(
510            matches(&filter, &test_tags),
511            "Filter with numeric val should match string tag"
512        );
513
514        let json_float = r#"{"key":"temperature","cmp":"eq","val":98.6}"#;
515        let filter_float: FilterNode = sonic_rs::from_str(json_float).unwrap();
516        assert_eq!(filter_float.val, Some("98.6".to_string()));
517
518        let temp_tags = tags(&[("temperature", "98.6")]);
519        assert!(matches(&filter_float, &temp_tags));
520    }
521}
sockudo_filter/lib.rs

sockudo_filter/
lib.rs
