nodedb_query/
metadata_filter.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Evaluation of `MetadataFilter` (nodedb-types) against a document.
4//!
5//! One evaluator serves every document shape: a field lookup closure
6//! resolves top-level fields. Adapters cover JSON documents (shape sync,
7//! vector post-filter), field maps (Lite edge properties) and plain-msgpack
8//! maps (Origin edge properties).
9//!
10//! Semantics:
11//! - `Eq` on a missing field matches only a `Null` value. `Ne` negates `Eq`.
12//! - `Gt`/`Gte`/`Lt`/`Lte` are false when the field is missing or null, the
13//!   value is null, or the pair has no order.
14//! - `In` on a missing field is false. `NotIn` on a missing field is true.
15//! - `And([])` is true. `Or([])` is false.
16//!
17//! Coercion, one rule for equality and order:
18//! - Numeric: numbers, decimals, numeric strings and bools (`true` = 1)
19//!   compare as numbers. Integer pairs compare exactly.
20//! - Instant: a typed instant compares with an instant or an ISO-8601 string
21//!   by epoch microseconds.
22//! - Text: strings, UUIDs and ULIDs order lexicographically.
23//! - Any other pair of different kinds is unequal and has no order. So
24//!   `{"score": "n/a"}` fails `score > 5`, and an array fails every order.
25
26use std::borrow::Cow;
27use std::cmp::Ordering;
28use std::collections::HashMap;
29use std::convert::Infallible;
30
31use nodedb_types::Value;
32use nodedb_types::filter::MetadataFilter;
33
34use crate::msgpack_scan::FieldIndex;
35use crate::msgpack_scan::reader::read_value;
36use crate::value_ops::{coerced_eq, involves_instant, numeric_order};
37
38/// A plain-msgpack property map the evaluator cannot read.
39#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
40pub enum PropertyMapError {
41    /// The bytes are not one well-formed MessagePack map.
42    #[error("property bytes are not a well-formed MessagePack map")]
43    NotAMap,
44    /// The map holds `field`, but its value does not decode.
45    #[error("property field '{field}' does not decode")]
46    Field { field: String },
47}
48
49/// Evaluate `filter` against a document whose top-level fields `lookup` resolves.
50pub fn matches_metadata_filter_with<'a, F>(lookup: &F, filter: &MetadataFilter) -> bool
51where
52    F: Fn(&str) -> Option<Cow<'a, Value>>,
53{
54    let infallible = |name: &str| Ok::<_, Infallible>(lookup(name));
55    match try_matches_metadata_filter_with(&infallible, filter) {
56        Ok(admitted) => admitted,
57        Err(never) => match never {},
58    }
59}
60
61/// Evaluate `filter` against a document whose top-level fields `lookup`
62/// resolves. A lookup error stops evaluation and returns that error.
63pub fn try_matches_metadata_filter_with<'a, F, E>(
64    lookup: &F,
65    filter: &MetadataFilter,
66) -> Result<bool, E>
67where
68    F: Fn(&str) -> Result<Option<Cow<'a, Value>>, E>,
69{
70    Ok(match filter {
71        MetadataFilter::Eq { field, value } => equals(lookup(field)?.as_deref(), value),
72        MetadataFilter::Ne { field, value } => !equals(lookup(field)?.as_deref(), value),
73        MetadataFilter::Gt { field, value } => {
74            ordered(lookup(field)?.as_deref(), value, |o| o == Ordering::Greater)
75        }
76        MetadataFilter::Gte { field, value } => {
77            ordered(lookup(field)?.as_deref(), value, |o| o != Ordering::Less)
78        }
79        MetadataFilter::Lt { field, value } => {
80            ordered(lookup(field)?.as_deref(), value, |o| o == Ordering::Less)
81        }
82        MetadataFilter::Lte { field, value } => {
83            ordered(lookup(field)?.as_deref(), value, |o| o != Ordering::Greater)
84        }
85        MetadataFilter::In { field, values } => {
86            lookup(field)?.is_some_and(|found| values.iter().any(|v| filter_eq(&found, v)))
87        }
88        MetadataFilter::NotIn { field, values } => {
89            lookup(field)?.is_none_or(|found| !values.iter().any(|v| filter_eq(&found, v)))
90        }
91        MetadataFilter::And(children) => {
92            for child in children {
93                if !try_matches_metadata_filter_with(lookup, child)? {
94                    return Ok(false);
95                }
96            }
97            true
98        }
99        MetadataFilter::Or(children) => {
100            for child in children {
101                if try_matches_metadata_filter_with(lookup, child)? {
102                    return Ok(true);
103                }
104            }
105            false
106        }
107        MetadataFilter::Not(inner) => !try_matches_metadata_filter_with(lookup, inner)?,
108        // `MetadataFilter` is `#[non_exhaustive]`: a variant this evaluator
109        // does not know admits nothing.
110        _ => false,
111    })
112}
113
114fn equals(found: Option<&Value>, value: &Value) -> bool {
115    match found {
116        Some(found) => filter_eq(found, value),
117        None => value.is_null(),
118    }
119}
120
121/// Equality under the module's coercion rule: [`coerced_eq`], plus text
122/// kinds equal by their text.
123fn filter_eq(a: &Value, b: &Value) -> bool {
124    coerced_eq(a, b) || matches!((text(a), text(b)), (Some(x), Some(y)) if x == y)
125}
126
127fn ordered(found: Option<&Value>, value: &Value, accept: impl Fn(Ordering) -> bool) -> bool {
128    match found {
129        Some(found) if !found.is_null() && !value.is_null() => {
130            filter_order(found, value).is_some_and(accept)
131        }
132        _ => false,
133    }
134}
135
136/// Order under the module's coercion rule. `None` for a pair of different
137/// kinds outside the coercions. NaN sorts above every number and equals NaN.
138fn filter_order(a: &Value, b: &Value) -> Option<Ordering> {
139    if involves_instant(a, b) {
140        return a.partial_cmp_coerced(b);
141    }
142    if let Some(order) = numeric_order(a, b) {
143        return Some(order);
144    }
145    match (text(a), text(b)) {
146        (Some(x), Some(y)) => Some(x.cmp(y)),
147        _ => None,
148    }
149}
150
151/// The text of a string-kind value: a string, UUID or ULID.
152fn text(v: &Value) -> Option<&str> {
153    match v {
154        Value::String(s) | Value::Uuid(s) | Value::Ulid(s) => Some(s),
155        _ => None,
156    }
157}
158
159/// `filter` against a field map (Lite edge properties).
160pub fn matches_metadata_fields(fields: &HashMap<String, Value>, filter: &MetadataFilter) -> bool {
161    matches_metadata_filter_with(&|name: &str| fields.get(name).map(Cow::Borrowed), filter)
162}
163
164/// Every filter of `filters` against a field map. An empty list admits.
165pub fn matches_all_fields(fields: &HashMap<String, Value>, filters: &[MetadataFilter]) -> bool {
166    filters.iter().all(|f| matches_metadata_fields(fields, f))
167}
168
169/// Every filter of `filters` against a plain-msgpack map. Decodes only the
170/// fields a filter names. Empty bytes evaluate as `{}`. An empty filter list
171/// admits without reading `doc`.
172///
173/// Bytes that are not one well-formed map, and a named field whose value
174/// does not decode, are an error: a property map the predicate cannot read
175/// is not a map the predicate admitted.
176pub fn matches_all_msgpack(
177    doc: &[u8],
178    filters: &[MetadataFilter],
179) -> Result<bool, PropertyMapError> {
180    if filters.is_empty() {
181        return Ok(true);
182    }
183    let index = if doc.is_empty() {
184        FieldIndex::empty()
185    } else {
186        FieldIndex::build(doc, 0).ok_or(PropertyMapError::NotAMap)?
187    };
188    let lookup = |name: &str| -> Result<Option<Cow<'static, Value>>, PropertyMapError> {
189        let Some((start, end)) = index.get(name) else {
190            return Ok(None);
191        };
192        let decoded = read_value(doc, start).or_else(|| {
193            doc.get(start..end)
194                .and_then(|bytes| nodedb_types::json_msgpack::value_from_msgpack(bytes).ok())
195        });
196        match decoded {
197            Some(value) => Ok(Some(Cow::Owned(value))),
198            None => Err(PropertyMapError::Field {
199                field: name.to_owned(),
200            }),
201        }
202    };
203    for filter in filters {
204        if !try_matches_metadata_filter_with(&lookup, filter)? {
205            return Ok(false);
206        }
207    }
208    Ok(true)
209}
210
211/// `filter` against a JSON document (shape-sync predicates, vector post-filter).
212pub fn matches_metadata_filter(doc: &serde_json::Value, filter: &MetadataFilter) -> bool {
213    let lookup = |name: &str| doc.get(name).map(|v| Cow::Owned(Value::from(v.clone())));
214    matches_metadata_filter_with(&lookup, filter)
215}
216
217#[cfg(test)]
218mod tests {
219    use super::*;
220    use nodedb_types::filter::MetadataFilter;
221    use nodedb_types::value::Value;
222    use serde_json::json;
223
224    fn gt(field: &str, value: Value) -> MetadataFilter {
225        MetadataFilter::Gt {
226            field: field.into(),
227            value,
228        }
229    }
230
231    fn lt(field: &str, value: Value) -> MetadataFilter {
232        MetadataFilter::Lt {
233            field: field.into(),
234            value,
235        }
236    }
237
238    fn ne(field: &str, value: Value) -> MetadataFilter {
239        MetadataFilter::Ne {
240            field: field.into(),
241            value,
242        }
243    }
244
245    #[test]
246    fn eq_match() {
247        let doc = json!({"status": "active", "age": 25});
248        let filter = MetadataFilter::eq("status", "active");
249        assert!(matches_metadata_filter(&doc, &filter));
250    }
251
252    #[test]
253    fn eq_no_match() {
254        let doc = json!({"status": "inactive"});
255        let filter = MetadataFilter::eq("status", "active");
256        assert!(!matches_metadata_filter(&doc, &filter));
257    }
258
259    #[test]
260    fn gt_numeric() {
261        let doc = json!({"age": 30});
262        assert!(matches_metadata_filter(
263            &doc,
264            &gt("age", Value::Integer(25))
265        ));
266    }
267
268    #[test]
269    fn and_filter() {
270        let doc = json!({"status": "active", "age": 30});
271        let filter = MetadataFilter::and(vec![
272            MetadataFilter::eq("status", "active"),
273            gt("age", Value::Integer(25)),
274        ]);
275        assert!(matches_metadata_filter(&doc, &filter));
276    }
277
278    #[test]
279    fn or_filter() {
280        let doc = json!({"status": "inactive", "age": 30});
281        let filter = MetadataFilter::or(vec![
282            MetadataFilter::eq("status", "active"),
283            gt("age", Value::Integer(25)),
284        ]);
285        assert!(matches_metadata_filter(&doc, &filter));
286    }
287
288    #[test]
289    fn not_filter() {
290        let doc = json!({"status": "active"});
291        let filter = MetadataFilter::Not(Box::new(MetadataFilter::eq("status", "inactive")));
292        assert!(matches_metadata_filter(&doc, &filter));
293    }
294
295    #[test]
296    fn in_filter() {
297        let doc = json!({"role": "admin"});
298        let filter = MetadataFilter::In {
299            field: "role".into(),
300            values: vec![Value::from("admin"), Value::from("superadmin")],
301        };
302        assert!(matches_metadata_filter(&doc, &filter));
303    }
304
305    #[test]
306    fn missing_field() {
307        let doc = json!({"name": "Alice"});
308        let filter = MetadataFilter::eq("status", "active");
309        assert!(!matches_metadata_filter(&doc, &filter));
310    }
311
312    #[test]
313    fn eq_and_ne_on_missing_field_and_null() {
314        let doc = json!({"present": null});
315        assert!(matches_metadata_filter(
316            &doc,
317            &MetadataFilter::eq("absent", Value::Null)
318        ));
319        assert!(matches_metadata_filter(
320            &doc,
321            &MetadataFilter::eq("present", Value::Null)
322        ));
323        assert!(!matches_metadata_filter(&doc, &ne("absent", Value::Null)));
324        assert!(matches_metadata_filter(
325            &doc,
326            &ne("absent", Value::from("x"))
327        ));
328        assert!(!matches_metadata_filter(
329            &doc,
330            &MetadataFilter::eq("absent", "x")
331        ));
332    }
333
334    #[test]
335    fn eq_coerces_numeric_strings_and_bools() {
336        let doc = json!({"n": "5", "flag": true});
337        assert!(matches_metadata_filter(
338            &doc,
339            &MetadataFilter::eq("n", Value::Integer(5))
340        ));
341        assert!(matches_metadata_filter(
342            &doc,
343            &MetadataFilter::eq("flag", Value::Integer(1))
344        ));
345    }
346
347    #[test]
348    fn ordered_comparisons_reject_missing_and_null() {
349        let doc = json!({"score": null});
350        for filter in [
351            gt("missing", Value::Integer(0)),
352            lt("missing", Value::Integer(100)),
353            MetadataFilter::Lte {
354                field: "missing".into(),
355                value: Value::Integer(100),
356            },
357            MetadataFilter::Gte {
358                field: "missing".into(),
359                value: Value::Integer(-100),
360            },
361            lt("score", Value::Integer(100)),
362            gt("score", Value::Integer(-100)),
363        ] {
364            assert!(!matches_metadata_filter(&doc, &filter), "{filter:?}");
365        }
366        let doc = json!({"score": 3});
367        assert!(!matches_metadata_filter(&doc, &lt("score", Value::Null)));
368    }
369
370    /// NaN sorts above every number and equals NaN, as in PostgreSQL.
371    #[test]
372    fn ordered_comparisons_place_nan_above_every_number() {
373        let fields = HashMap::from([("score".to_owned(), Value::Float(f64::NAN))]);
374        let nan_gte_nan = MetadataFilter::Gte {
375            field: "score".into(),
376            value: Value::Float(f64::NAN),
377        };
378        for filter in [gt("score", Value::Integer(0)), nan_gte_nan] {
379            assert!(matches_metadata_fields(&fields, &filter), "{filter:?}");
380        }
381        let nan_lte_zero = MetadataFilter::Lte {
382            field: "score".into(),
383            value: Value::Integer(0),
384        };
385        for filter in [lt("score", Value::Integer(0)), nan_lte_zero] {
386            assert!(!matches_metadata_fields(&fields, &filter), "{filter:?}");
387        }
388    }
389
390    #[test]
391    fn in_and_not_in_on_missing_field() {
392        let doc = json!({});
393        let values = vec![Value::from("a")];
394        assert!(!matches_metadata_filter(
395            &doc,
396            &MetadataFilter::In {
397                field: "k".into(),
398                values: values.clone(),
399            }
400        ));
401        assert!(matches_metadata_filter(
402            &doc,
403            &MetadataFilter::NotIn {
404                field: "k".into(),
405                values,
406            }
407        ));
408    }
409
410    #[test]
411    fn empty_and_admits_empty_or_rejects() {
412        let doc = json!({});
413        assert!(matches_metadata_filter(
414            &doc,
415            &MetadataFilter::And(Vec::new())
416        ));
417        assert!(!matches_metadata_filter(
418            &doc,
419            &MetadataFilter::Or(Vec::new())
420        ));
421    }
422
423    #[test]
424    fn nested_not() {
425        let doc = json!({"score": 9});
426        let filter = MetadataFilter::Not(Box::new(MetadataFilter::Not(Box::new(gt(
427            "score",
428            Value::Integer(5),
429        )))));
430        assert!(matches_metadata_filter(&doc, &filter));
431        let filter = MetadataFilter::Not(Box::new(MetadataFilter::Or(vec![
432            lt("score", Value::Integer(5)),
433            MetadataFilter::eq("score", Value::Integer(9)),
434        ])));
435        assert!(!matches_metadata_filter(&doc, &filter));
436    }
437
438    #[test]
439    fn msgpack_matches_field_map() {
440        let fields = HashMap::from([
441            ("score".to_owned(), Value::Integer(9)),
442            ("kind".to_owned(), Value::from("road")),
443            ("closed".to_owned(), Value::Bool(false)),
444        ]);
445        let bytes = nodedb_types::json_msgpack::value_to_msgpack(&Value::Object(fields.clone()))
446            .expect("encode");
447        let cases = [
448            vec![gt("score", Value::Integer(5))],
449            vec![lt("score", Value::Integer(5))],
450            vec![
451                MetadataFilter::In {
452                    field: "kind".into(),
453                    values: vec![Value::from("road"), Value::from("rail")],
454                },
455                MetadataFilter::Not(Box::new(MetadataFilter::eq("closed", true))),
456            ],
457            vec![MetadataFilter::eq("missing", Value::Null)],
458            vec![lt("missing", Value::Integer(5))],
459            Vec::new(),
460        ];
461        for filters in cases {
462            assert_eq!(
463                matches_all_msgpack(&bytes, &filters),
464                Ok(matches_all_fields(&fields, &filters)),
465                "{filters:?}"
466            );
467        }
468    }
469
470    #[test]
471    fn empty_msgpack_evaluates_as_empty_object() {
472        assert_eq!(
473            matches_all_msgpack(&[], &[MetadataFilter::eq("missing", Value::Null)]),
474            Ok(true)
475        );
476        assert_eq!(
477            matches_all_msgpack(&[], &[lt("score", Value::Integer(5))]),
478            Ok(false)
479        );
480        assert_eq!(matches_all_msgpack(&[], &[]), Ok(true));
481    }
482
483    /// `{"score": 9}` with the value's tag replaced by the reserved `0xc1`.
484    fn corrupt_score_map() -> Vec<u8> {
485        let mut bytes =
486            nodedb_types::json_msgpack::json_to_msgpack(&json!({"score": 9})).expect("encode");
487        let last = bytes.len() - 1;
488        bytes[last] = 0xc1;
489        bytes
490    }
491
492    #[test]
493    fn a_named_field_that_does_not_decode_is_an_error() {
494        let bytes = corrupt_score_map();
495        let result = matches_all_msgpack(&bytes, &[gt("score", Value::Integer(5))]);
496        assert!(result.is_err(), "{result:?}");
497        assert_eq!(
498            matches_all_msgpack(&bytes, &[]),
499            Ok(true),
500            "no filter reads nothing"
501        );
502    }
503
504    #[test]
505    fn bytes_that_are_not_a_map_are_an_error() {
506        let list = nodedb_types::json_msgpack::json_to_msgpack(&json!([1, 2])).expect("encode");
507        assert_eq!(
508            matches_all_msgpack(&list, &[MetadataFilter::eq("k", Value::Null)]),
509            Err(PropertyMapError::NotAMap)
510        );
511        // A map header that claims more entries than the bytes hold.
512        assert_eq!(
513            matches_all_msgpack(&[0x82, 0xa1, b'k', 0x01], &[gt("k", Value::Integer(0))]),
514            Err(PropertyMapError::NotAMap)
515        );
516    }
517
518    #[test]
519    fn integers_past_two_pow_53_filter_exactly() {
520        let fields = HashMap::from([("ts".to_owned(), Value::Integer(9_007_199_254_740_993))]);
521        let at = Value::Integer(9_007_199_254_740_992);
522        assert!(!matches_metadata_fields(
523            &fields,
524            &MetadataFilter::eq("ts", at.clone())
525        ));
526        assert!(matches_metadata_fields(&fields, &gt("ts", at.clone())));
527        assert!(!matches_metadata_fields(&fields, &lt("ts", at)));
528    }
529
530    /// Each pair of different kinds outside the coercions has no order.
531    #[test]
532    fn ordered_comparisons_across_kinds_are_unordered() {
533        let fields = HashMap::from([
534            ("text".to_owned(), Value::from("n/a")),
535            ("list".to_owned(), Value::Array(vec![Value::Integer(9)])),
536            ("num".to_owned(), Value::Integer(9)),
537            (
538                "obj".to_owned(),
539                Value::Object(HashMap::from([("a".to_owned(), Value::Integer(1))])),
540            ),
541            ("flag".to_owned(), Value::Bool(true)),
542        ]);
543        let unordered = [
544            ("text", Value::Integer(5)),
545            ("list", Value::Integer(5)),
546            ("num", Value::from("abc")),
547            ("num", Value::Array(vec![Value::Integer(1)])),
548            ("obj", Value::Integer(0)),
549            ("obj", Value::from("a")),
550            ("list", Value::from("a")),
551            ("flag", Value::from("yes")),
552        ];
553        for (field, value) in unordered {
554            for filter in [
555                gt(field, value.clone()),
556                lt(field, value.clone()),
557                MetadataFilter::Gte {
558                    field: field.into(),
559                    value: value.clone(),
560                },
561                MetadataFilter::Lte {
562                    field: field.into(),
563                    value: value.clone(),
564                },
565            ] {
566                assert!(!matches_metadata_fields(&fields, &filter), "{filter:?}");
567            }
568        }
569    }
570
571    /// The coercions order the same pairs that compare equal.
572    #[test]
573    fn coerced_kinds_order_and_compare_alike() {
574        let fields = HashMap::from([
575            ("n".to_owned(), Value::from("10")),
576            ("flag".to_owned(), Value::Bool(true)),
577            ("name".to_owned(), Value::from("bob")),
578            (
579                "id".to_owned(),
580                Value::Uuid("550e8400-e29b-41d4-a716-446655440000".into()),
581            ),
582        ]);
583        assert!(matches_metadata_fields(
584            &fields,
585            &gt("n", Value::Integer(9))
586        ));
587        assert!(matches_metadata_fields(
588            &fields,
589            &MetadataFilter::eq("n", Value::Integer(10))
590        ));
591        assert!(matches_metadata_fields(
592            &fields,
593            &gt("flag", Value::Integer(0))
594        ));
595        assert!(matches_metadata_fields(
596            &fields,
597            &MetadataFilter::eq("flag", Value::Integer(1))
598        ));
599        assert!(matches_metadata_fields(
600            &fields,
601            &gt("name", Value::from("alice"))
602        ));
603        assert!(matches_metadata_fields(
604            &fields,
605            &lt("name", Value::from("carol"))
606        ));
607        let id = Value::from("550e8400-e29b-41d4-a716-446655440000");
608        assert!(matches_metadata_fields(
609            &fields,
610            &MetadataFilter::eq("id", id.clone())
611        ));
612        assert!(matches_metadata_fields(
613            &fields,
614            &MetadataFilter::Gte {
615                field: "id".into(),
616                value: id,
617            }
618        ));
619    }
620
621    #[test]
622    fn a_non_numeric_string_fails_a_numeric_order_over_msgpack() {
623        let bytes =
624            nodedb_types::json_msgpack::json_to_msgpack(&json!({"score": "n/a"})).expect("encode");
625        assert_eq!(
626            matches_all_msgpack(&bytes, &[gt("score", Value::Integer(5))]),
627            Ok(false)
628        );
629        assert_eq!(
630            matches_all_msgpack(&bytes, &[lt("score", Value::Integer(5))]),
631            Ok(false)
632        );
633    }
634}
nodedb_query/metadata_filter.rs

nodedb_query/
metadata_filter.rs
