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}
sockudo_filter/lib.rs

sockudo_filter/
lib.rs
