kanidmd_lib/
filter.rs

1//! [`Filter`]s are one of the three foundational concepts of the design in kanidm.
2//! They are used in nearly every aspect of the server to provide searching of
3//! datasets and assertion of entry properties.
4//!
5//! A filter is a logical statement of properties that an [`Entry`] and its
6//! AVAs must uphold to be considered true.
7//!
8//! [`Filter`]: struct.Filter.html
9//! [`Entry`]: ../entry/struct.Entry.html
10
11use std::cmp::{Ordering, PartialOrd};
12use std::collections::BTreeSet;
13use std::fmt;
14use std::hash::Hash;
15use std::iter;
16use std::num::NonZeroU8;
17use std::str::FromStr;
18use std::sync::Arc;
19
20use concread::arcache::{ARCache, ARCacheReadTxn};
21use hashbrown::HashMap;
22#[cfg(test)]
23use hashbrown::HashSet;
24use kanidm_proto::constants::ATTR_UUID;
25use kanidm_proto::internal::{Filter as ProtoFilter, OperationError, SchemaError};
26use kanidm_proto::scim_v1::{AttrPath as ScimAttrPath, ScimFilter};
27use ldap3_proto::proto::{LdapFilter, LdapSubstringFilter};
28use serde::Deserialize;
29use uuid::Uuid;
30
31use crate::be::{IdxKey, IdxKeyRef, IdxKeyToRef, IdxMeta, IdxSlope};
32use crate::idm::ldap::ldap_attr_filter_map;
33use crate::prelude::*;
34use crate::schema::SchemaTransaction;
35use crate::value::{IndexType, PartialValue};
36
37pub type ResolveFilterCache =
38    ARCache<(IdentityId, Arc<Filter<FilterValid>>), Arc<Filter<FilterValidResolved>>>;
39
40pub type ResolveFilterCacheReadTxn<'a> = ARCacheReadTxn<
41    'a,
42    (IdentityId, Arc<Filter<FilterValid>>),
43    Arc<Filter<FilterValidResolved>>,
44    (),
45>;
46
47// Default filter is safe, ignores all hidden types!
48
49// This is &Value so we can lazy const then clone, but perhaps we can reconsider
50// later if this should just take Value.
51pub fn f_eq(a: Attribute, v: PartialValue) -> FC {
52    FC::Eq(a, v)
53}
54
55pub fn f_sub(a: Attribute, v: PartialValue) -> FC {
56    FC::Cnt(a, v)
57}
58
59pub fn f_pres(a: Attribute) -> FC {
60    FC::Pres(a)
61}
62
63pub fn f_lt(a: Attribute, v: PartialValue) -> FC {
64    FC::LessThan(a, v)
65}
66
67pub fn f_or(vs: Vec<FC>) -> FC {
68    FC::Or(vs)
69}
70
71pub fn f_and(vs: Vec<FC>) -> FC {
72    FC::And(vs)
73}
74
75pub fn f_inc(vs: Vec<FC>) -> FC {
76    FC::Inclusion(vs)
77}
78
79pub fn f_andnot(fc: FC) -> FC {
80    FC::AndNot(Box::new(fc))
81}
82
83pub fn f_self() -> FC {
84    FC::SelfUuid
85}
86
87pub fn f_invalid(a: Attribute) -> FC {
88    FC::Invalid(a)
89}
90
91pub fn f_id(uuid: &str) -> FC {
92    let uf = Uuid::parse_str(uuid)
93        .ok()
94        .map(|u| FC::Eq(Attribute::Uuid, PartialValue::Uuid(u)));
95    let spnf = PartialValue::new_spn_s(uuid).map(|spn| FC::Eq(Attribute::Spn, spn));
96    let nf = FC::Eq(Attribute::Name, PartialValue::new_iname(uuid));
97    let f: Vec<_> = iter::once(uf)
98        .chain(iter::once(spnf))
99        .flatten()
100        .chain(iter::once(nf))
101        .collect();
102    FC::Or(f)
103}
104
105pub fn f_spn_name(id: &str) -> FC {
106    let spnf = PartialValue::new_spn_s(id).map(|spn| FC::Eq(Attribute::Spn, spn));
107    let nf = FC::Eq(Attribute::Name, PartialValue::new_iname(id));
108    let f: Vec<_> = iter::once(spnf).flatten().chain(iter::once(nf)).collect();
109    FC::Or(f)
110}
111
112/// This is the short-form for tests and internal filters that can then
113/// be transformed into a filter for the server to use.
114#[derive(Clone, Debug, Deserialize)]
115pub enum FC {
116    Eq(Attribute, PartialValue),
117    Cnt(Attribute, PartialValue),
118    Pres(Attribute),
119    LessThan(Attribute, PartialValue),
120    Or(Vec<FC>),
121    And(Vec<FC>),
122    Inclusion(Vec<FC>),
123    AndNot(Box<FC>),
124    SelfUuid,
125    Invalid(Attribute),
126    // Not(Box<FC>),
127}
128
129/// This is the filters internal representation
130#[derive(Clone, Hash, PartialEq, PartialOrd, Ord, Eq)]
131enum FilterComp {
132    // This is attr - value
133    Eq(Attribute, PartialValue),
134    Cnt(Attribute, PartialValue),
135    Stw(Attribute, PartialValue),
136    Enw(Attribute, PartialValue),
137    Pres(Attribute),
138    LessThan(Attribute, PartialValue),
139    Or(Vec<FilterComp>),
140    And(Vec<FilterComp>),
141    Inclusion(Vec<FilterComp>),
142    AndNot(Box<FilterComp>),
143    SelfUuid,
144    Invalid(Attribute),
145    // Does this mean we can add a true not to the type now?
146    // Not(Box<FilterComp>),
147}
148
149impl fmt::Debug for FilterComp {
150    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
151        match self {
152            FilterComp::Eq(attr, pv) => {
153                write!(f, "{attr} eq {pv:?}")
154            }
155            FilterComp::Cnt(attr, pv) => {
156                write!(f, "{attr} cnt {pv:?}")
157            }
158            FilterComp::Stw(attr, pv) => {
159                write!(f, "{attr} stw {pv:?}")
160            }
161            FilterComp::Enw(attr, pv) => {
162                write!(f, "{attr} enw {pv:?}")
163            }
164            FilterComp::Pres(attr) => {
165                write!(f, "{attr} pres")
166            }
167            FilterComp::LessThan(attr, pv) => {
168                write!(f, "{attr} lt {pv:?}")
169            }
170            FilterComp::And(list) => {
171                write!(f, "(")?;
172                for (i, fc) in list.iter().enumerate() {
173                    write!(f, "{fc:?}")?;
174                    if i != list.len() - 1 {
175                        write!(f, " and ")?;
176                    }
177                }
178                write!(f, ")")
179            }
180            FilterComp::Or(list) => {
181                write!(f, "(")?;
182                for (i, fc) in list.iter().enumerate() {
183                    write!(f, "{fc:?}")?;
184                    if i != list.len() - 1 {
185                        write!(f, " or ")?;
186                    }
187                }
188                write!(f, ")")
189            }
190            FilterComp::Inclusion(list) => {
191                write!(f, "(")?;
192                for (i, fc) in list.iter().enumerate() {
193                    write!(f, "{fc:?}")?;
194                    if i != list.len() - 1 {
195                        write!(f, " inc ")?;
196                    }
197                }
198                write!(f, ")")
199            }
200            FilterComp::AndNot(inner) => {
201                write!(f, "not ( {inner:?} )")
202            }
203            FilterComp::SelfUuid => {
204                write!(f, "uuid eq self")
205            }
206            FilterComp::Invalid(attr) => {
207                write!(f, "invalid ( {attr:?} )")
208            }
209        }
210    }
211}
212
213/// This is the fully resolved internal representation. Note the lack of Not and selfUUID
214/// because these are resolved into And(Pres(class), AndNot(term)) and Eq(uuid, ...) respectively.
215/// Importantly, we make this accessible to Entry so that it can then match on filters
216/// internally.
217///
218/// Each filter that has been resolved also has been enriched with metadata about its
219/// index, and index slope. For the purpose of this module, consider slope as a "weight"
220/// where small value - faster index, larger value - slower index. This metadata is extremely
221/// important for the query optimiser to make decisions about how to re-arrange queries
222/// correctly.
223#[derive(Clone, Eq)]
224pub enum FilterResolved {
225    // This is attr - value - indexed slope factor
226    Eq(Attribute, PartialValue, Option<NonZeroU8>),
227    Cnt(Attribute, PartialValue, Option<NonZeroU8>),
228    Stw(Attribute, PartialValue, Option<NonZeroU8>),
229    Enw(Attribute, PartialValue, Option<NonZeroU8>),
230    Pres(Attribute, Option<NonZeroU8>),
231    LessThan(Attribute, PartialValue, Option<NonZeroU8>),
232    Or(Vec<FilterResolved>, Option<NonZeroU8>),
233    And(Vec<FilterResolved>, Option<NonZeroU8>),
234    Invalid(Attribute),
235    // All terms must have 1 or more items, or the inclusion is false!
236    Inclusion(Vec<FilterResolved>, Option<NonZeroU8>),
237    AndNot(Box<FilterResolved>, Option<NonZeroU8>),
238}
239
240impl fmt::Debug for FilterResolved {
241    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
242        match self {
243            FilterResolved::Eq(attr, pv, idx) => {
244                write!(
245                    f,
246                    "(s{} {} eq {:?})",
247                    idx.unwrap_or(NonZeroU8::MAX),
248                    attr,
249                    pv
250                )
251            }
252            FilterResolved::Cnt(attr, pv, idx) => {
253                write!(
254                    f,
255                    "(s{} {} cnt {:?})",
256                    idx.unwrap_or(NonZeroU8::MAX),
257                    attr,
258                    pv
259                )
260            }
261            FilterResolved::Stw(attr, pv, idx) => {
262                write!(
263                    f,
264                    "(s{} {} stw {:?})",
265                    idx.unwrap_or(NonZeroU8::MAX),
266                    attr,
267                    pv
268                )
269            }
270            FilterResolved::Enw(attr, pv, idx) => {
271                write!(
272                    f,
273                    "(s{} {} enw {:?})",
274                    idx.unwrap_or(NonZeroU8::MAX),
275                    attr,
276                    pv
277                )
278            }
279            FilterResolved::Pres(attr, idx) => {
280                write!(f, "(s{} {} pres)", idx.unwrap_or(NonZeroU8::MAX), attr)
281            }
282            FilterResolved::LessThan(attr, pv, idx) => {
283                write!(
284                    f,
285                    "(s{} {} lt {:?})",
286                    idx.unwrap_or(NonZeroU8::MAX),
287                    attr,
288                    pv
289                )
290            }
291            FilterResolved::And(list, idx) => {
292                write!(f, "(s{} ", idx.unwrap_or(NonZeroU8::MAX))?;
293                for (i, fc) in list.iter().enumerate() {
294                    write!(f, "{fc:?}")?;
295                    if i != list.len() - 1 {
296                        write!(f, " and ")?;
297                    }
298                }
299                write!(f, ")")
300            }
301            FilterResolved::Or(list, idx) => {
302                write!(f, "(s{} ", idx.unwrap_or(NonZeroU8::MAX))?;
303                for (i, fc) in list.iter().enumerate() {
304                    write!(f, "{fc:?}")?;
305                    if i != list.len() - 1 {
306                        write!(f, " or ")?;
307                    }
308                }
309                write!(f, ")")
310            }
311            FilterResolved::Inclusion(list, idx) => {
312                write!(f, "(s{} ", idx.unwrap_or(NonZeroU8::MAX))?;
313                for (i, fc) in list.iter().enumerate() {
314                    write!(f, "{fc:?}")?;
315                    if i != list.len() - 1 {
316                        write!(f, " inc ")?;
317                    }
318                }
319                write!(f, ")")
320            }
321            FilterResolved::AndNot(inner, idx) => {
322                write!(f, "not (s{} {:?})", idx.unwrap_or(NonZeroU8::MAX), inner)
323            }
324            FilterResolved::Invalid(attr) => {
325                write!(f, "{attr} inv")
326            }
327        }
328    }
329}
330
331#[derive(Debug, Clone, PartialEq, Eq)]
332/// A filter before it's gone through schema validation
333pub struct FilterInvalid {
334    inner: FilterComp,
335}
336
337#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
338/// A filter after it's gone through schema validation
339pub struct FilterValid {
340    inner: FilterComp,
341}
342
343#[derive(Clone, PartialEq, Eq)]
344pub struct FilterValidResolved {
345    inner: FilterResolved,
346}
347
348#[derive(Debug)]
349pub enum FilterPlan {
350    Invalid,
351    EqIndexed(Attribute, String),
352    EqUnindexed(Attribute),
353    EqCorrupt(Attribute),
354    SubIndexed(Attribute, String),
355    SubUnindexed(Attribute),
356    SubCorrupt(Attribute),
357    PresIndexed(Attribute),
358    PresUnindexed(Attribute),
359    PresCorrupt(Attribute),
360    LessThanUnindexed(Attribute),
361    OrUnindexed(Vec<FilterPlan>),
362    OrIndexed(Vec<FilterPlan>),
363    OrPartial(Vec<FilterPlan>),
364    OrPartialThreshold(Vec<FilterPlan>),
365    AndEmptyCand(Vec<FilterPlan>),
366    AndIndexed(Vec<FilterPlan>),
367    AndUnindexed(Vec<FilterPlan>),
368    AndPartial(Vec<FilterPlan>),
369    AndPartialThreshold(Vec<FilterPlan>),
370    AndNot(Box<FilterPlan>),
371    InclusionInvalid(Vec<FilterPlan>),
372    InclusionIndexed(Vec<FilterPlan>),
373}
374
375// This difference in this is that we want to show unindexed elements more prominently
376// in the execution.
377
378fn fmt_filterplan_set(f: &mut fmt::Formatter<'_>, name: &str, plan: &[FilterPlan]) -> fmt::Result {
379    write!(f, "{name}(")?;
380    for item in plan {
381        write!(f, "{item}, ")?;
382    }
383    write!(f, ")")
384}
385
386impl fmt::Display for FilterPlan {
387    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
388        match self {
389            Self::Invalid => write!(f, "Invalid"),
390            Self::EqIndexed(attr, _) => write!(f, "EqIndexed({attr})"),
391            Self::EqCorrupt(attr) => write!(f, "EqCorrupt({attr})"),
392            Self::EqUnindexed(attr) => write!(f, "EqUnindexed({attr})"),
393
394            Self::SubIndexed(attr, _) => write!(f, "SubIndexed({attr})"),
395            Self::SubCorrupt(attr) => write!(f, "SubCorrupt({attr})"),
396            Self::SubUnindexed(attr) => write!(f, "SubUnindexed({attr})"),
397
398            Self::PresIndexed(attr) => write!(f, "PresIndexed({attr})"),
399            Self::PresCorrupt(attr) => write!(f, "PresCorrupt({attr})"),
400            Self::PresUnindexed(attr) => write!(f, "PresUnindexed({attr})"),
401
402            Self::LessThanUnindexed(attr) => write!(f, "LessThanUnindexed({attr})"),
403
404            Self::OrUnindexed(plan) => fmt_filterplan_set(f, "OrUnindexed", plan),
405            Self::OrIndexed(plan) => write!(f, "OrIndexed(len={})", plan.len()),
406            Self::OrPartial(plan) => fmt_filterplan_set(f, "OrPartial", plan),
407            Self::OrPartialThreshold(plan) => fmt_filterplan_set(f, "OrPartialThreshold", plan),
408
409            Self::AndEmptyCand(plan) => write!(f, "AndEmptyCand(len={})", plan.len()),
410            Self::AndUnindexed(plan) => fmt_filterplan_set(f, "AndUnindexed", plan),
411            Self::AndIndexed(plan) => write!(f, "AndIndexed(len={})", plan.len()),
412            Self::AndPartial(plan) => fmt_filterplan_set(f, "AndPartial", plan),
413            Self::AndPartialThreshold(plan) => fmt_filterplan_set(f, "AndPartialThreshold", plan),
414
415            Self::AndNot(plan) => write!(f, "AndNot({plan})"),
416
417            Self::InclusionInvalid(plan) => fmt_filterplan_set(f, "InclusionInvalid", plan),
418            Self::InclusionIndexed(plan) => write!(f, "InclusionIndexed(len={})", plan.len()),
419        }
420    }
421}
422
423/// A `Filter` is a logical set of assertions about the state of an [`Entry`] and
424/// it's avas. `Filter`s are built from a set of possible assertions.
425///
426/// * `Pres`ence. An ava of that attribute's name exists, with any value on the [`Entry`].
427/// * `Eq`uality. An ava of the attribute exists and contains this matching value.
428/// * `Sub`string. An ava of the attribute exists and has a substring containing the requested value.
429/// * `Or`. Contains multiple filters and asserts at least one is true.
430/// * `And`. Contains multiple filters and asserts all of them are true.
431/// * `AndNot`. This is different to a "logical not" operation. This asserts that a condition is not
432///   true in the current candidate set. A search of `AndNot` alone will yield not results, but an
433///   `AndNot` in an `And` query will assert that a condition can not hold.
434///
435/// `Filter`s for security reasons are validated by the schema to assert all requested attributes
436/// are valid and exist in the schema so that they can have their indexes correctly used. This avoids
437/// a denial of service attack that may lead to full-table scans.
438///
439/// This `Filter` validation state is in the `STATE` attribute and will be either `FilterInvalid`
440/// or `FilterValid`. The `Filter` must be checked by the schema to move to `FilterValid`. This
441/// helps to prevent errors at compile time to assert `Filters` are securely checked
442///
443/// [`Entry`]: ../entry/struct.Entry.html
444#[derive(Clone, Hash, Ord, Eq, PartialOrd, PartialEq)]
445pub struct Filter<STATE> {
446    state: STATE,
447}
448
449impl fmt::Debug for Filter<FilterValidResolved> {
450    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
451        writeln!(f, "Filter(Valid) {:?}", self.state.inner)
452    }
453}
454
455impl fmt::Debug for Filter<FilterValid> {
456    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
457        writeln!(f, "Filter(Valid) {:?}", self.state.inner)
458    }
459}
460
461impl fmt::Debug for Filter<FilterInvalid> {
462    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
463        writeln!(f, "Filter(Invalid) {:?}", self.state.inner)
464    }
465}
466
467impl Filter<FilterValidResolved> {
468    // Does this need mut self? Aren't we returning
469    // a new copied filter?
470
471    #[cfg(test)]
472    fn optimise(&self) -> Self {
473        // Apply optimisations to the filter
474        // An easy way would be imple partialOrd
475        // then do sort on the or/and/not
476        // as the general conditions we want
477        // to optimise on are in those ...
478        //
479        // The other big one is folding redundant
480        // terms down.
481        //
482        // If an or/not/and condition has no items, remove it
483        //
484        // If its the root item?
485
486        Filter {
487            state: FilterValidResolved {
488                inner: self.state.inner.optimise(),
489            },
490        }
491    }
492
493    // It's not possible to invalid a resolved filter, because we don't know
494    // what the origin of the Self or Not keywords were.
495    //
496    // Saying this, we have entry -> filter_from_attrs. Should that return
497    // a valid or validResolved? If it does valid resolved we need invalidate
498    // so we can down cast and then re-validate and re-resolve ...
499
500    // Allow the entry crate to read the internals of the filter.
501    // more likely, we should move entry matching HERE ...
502    pub fn to_inner(&self) -> &FilterResolved {
503        &self.state.inner
504    }
505}
506
507impl Filter<FilterValid> {
508    pub fn invalidate(self) -> Filter<FilterInvalid> {
509        // Just move the state.
510        Filter {
511            state: FilterInvalid {
512                inner: self.state.inner,
513            },
514        }
515    }
516
517    pub fn resolve(
518        &self,
519        ev: &Identity,
520        idxmeta: Option<&IdxMeta>,
521        mut rsv_cache: Option<&mut ResolveFilterCacheReadTxn<'_>>,
522    ) -> Result<Filter<FilterValidResolved>, OperationError> {
523        // Given a filter, resolve Not and SelfUuid to real terms.
524        //
525        // The benefit of moving optimisation to this step is from various inputs, we can
526        // get to a resolved + optimised filter, and then we can cache those outputs in many
527        // cases! The exception is *large* filters, especially from the memberof plugin. We
528        // want to skip these because they can really jam up the server.
529
530        // Don't cache anything unless we have valid indexing metadata.
531        let cacheable = idxmeta.is_some() && FilterResolved::resolve_cacheable(&self.state.inner);
532
533        let cache_key = if cacheable {
534            // do we have a cache?
535            if let Some(rcache) = rsv_cache.as_mut() {
536                // construct the key. For now it's expensive because we have to clone, but ... eh.
537                let cache_key = (ev.get_event_origin_id(), Arc::new(self.clone()));
538                if let Some(f) = rcache.get(&cache_key) {
539                    // Got it? Shortcut and return!
540                    trace!("shortcut: a resolved filter already exists.");
541                    return Ok(f.as_ref().clone());
542                };
543                // Not in cache? Set the cache_key.
544                Some(cache_key)
545            } else {
546                None
547            }
548        } else {
549            // Not cacheable, lets just bail.
550            None
551        };
552
553        // If we got here, nothing in cache - resolve it the hard way.
554
555        let resolved_filt = Filter {
556            state: FilterValidResolved {
557                inner: match idxmeta {
558                    Some(idx) => {
559                        FilterResolved::resolve_idx(self.state.inner.clone(), ev, &idx.idxkeys)
560                    }
561                    None => FilterResolved::resolve_no_idx(self.state.inner.clone(), ev),
562                }
563                .map(|f| {
564                    match idxmeta {
565                        // Do a proper optimise if we have idxmeta.
566                        Some(_) => f.optimise(),
567                        // Only do this if we don't have idxmeta.
568                        None => f.fast_optimise(),
569                    }
570                })
571                .ok_or(OperationError::FilterUuidResolution)?,
572            },
573        };
574
575        // Now it's computed, inject it. Remember, we won't have a cache_key here
576        // if cacheable == false.
577        if let Some(cache_key) = cache_key {
578            if let Some(rcache) = rsv_cache.as_mut() {
579                trace!(?resolved_filt, "inserting filter to resolved cache");
580                rcache.insert(cache_key, Arc::new(resolved_filt.clone()));
581            }
582        }
583
584        Ok(resolved_filt)
585    }
586
587    pub fn get_attr_set(&self) -> BTreeSet<Attribute> {
588        // Recurse through the filter getting an attribute set.
589        let mut r_set = BTreeSet::new();
590        self.state.inner.get_attr_set(&mut r_set);
591        r_set
592    }
593
594    /*
595     * CORRECTNESS: This is a transform on the "immutable" filtervalid type.
596     * We know this is correct because internally we can assert that the hidden
597     * and recycled types *must* be valid.
598     */
599
600    pub fn into_ignore_hidden(self) -> Self {
601        // Destructure the former filter, and surround it with an ignore_hidden.
602        Filter {
603            state: FilterValid {
604                inner: FilterComp::new_ignore_hidden(self.state.inner),
605            },
606        }
607    }
608
609    pub fn into_recycled(self) -> Self {
610        // Destructure the former filter and surround it with a recycled only query
611        Filter {
612            state: FilterValid {
613                inner: FilterComp::new_recycled(self.state.inner),
614            },
615        }
616    }
617}
618
619impl Filter<FilterInvalid> {
620    pub fn new(inner: FC) -> Self {
621        let fc = FilterComp::new(inner);
622        Filter {
623            state: FilterInvalid { inner: fc },
624        }
625    }
626
627    pub fn new_ignore_hidden(inner: FC) -> Self {
628        let fc = FilterComp::new(inner);
629        Filter {
630            state: FilterInvalid {
631                inner: FilterComp::new_ignore_hidden(fc),
632            },
633        }
634    }
635
636    pub fn new_recycled(inner: FC) -> Self {
637        // Create a filter that searches recycled items only.
638        let fc = FilterComp::new(inner);
639        Filter {
640            state: FilterInvalid {
641                inner: FilterComp::new_recycled(fc),
642            },
643        }
644    }
645
646    pub fn join_parts_and(a: Self, b: Self) -> Self {
647        // I regret this function so much, but then again ...
648        Filter {
649            state: FilterInvalid {
650                inner: FilterComp::And(vec![a.state.inner, b.state.inner]),
651            },
652        }
653    }
654
655    /// ⚠️  - Bypass the schema state machine and force the filter to be considered valid.
656    /// This is a TEST ONLY method and will never be exposed in production.
657    #[cfg(test)]
658    pub fn into_valid_resolved(self) -> Filter<FilterValidResolved> {
659        // There is a good reason this function only exists in tests ...
660        //
661        // YOLO.
662        // tl;dr - panic if there is a Self term because we don't have the QS
663        // to resolve the uuid. Perhaps in the future we can provide a uuid
664        // to this for the resolving to make it safer and test case usable.
665
666        // First we make a fake idx meta, which is meant to be "just enough" to make
667        // some core test idxs faster. This is never used in production, it's JUST for
668        // test case speedups.
669        let idxmeta = vec![
670            (Attribute::Uuid, IndexType::Equality),
671            (Attribute::Uuid, IndexType::Presence),
672            (Attribute::Name, IndexType::Equality),
673            (Attribute::Name, IndexType::SubString),
674            (Attribute::Name, IndexType::Presence),
675            (Attribute::Class, IndexType::Equality),
676            (Attribute::Class, IndexType::Presence),
677            (Attribute::Member, IndexType::Equality),
678            (Attribute::Member, IndexType::Presence),
679            (Attribute::MemberOf, IndexType::Equality),
680            (Attribute::MemberOf, IndexType::Presence),
681            (Attribute::DirectMemberOf, IndexType::Equality),
682            (Attribute::DirectMemberOf, IndexType::Presence),
683        ];
684
685        let idxmeta_ref = idxmeta.iter().map(|(attr, itype)| (attr, itype)).collect();
686
687        Filter {
688            state: FilterValidResolved {
689                inner: FilterResolved::from_invalid(self.state.inner, &idxmeta_ref),
690            },
691        }
692    }
693
694    /// ⚠️  - Bypass the schema state machine and force the filter to be considered valid.
695    /// This is a TEST ONLY method and will never be exposed in production.
696    #[cfg(test)]
697    pub fn into_valid(self) -> Filter<FilterValid> {
698        // There is a good reason this function only exists in tests ...
699        //
700        // YOLO.
701        // tl;dr - blindly accept that this filter and it's ava's MUST have
702        // been normalised and exist in schema. If they don't things may subtly
703        // break, fail, or explode. As subtle as an explosion can be.
704        Filter {
705            state: FilterValid {
706                inner: self.state.inner,
707            },
708        }
709    }
710
711    pub fn validate(
712        &self,
713        schema: &dyn SchemaTransaction,
714    ) -> Result<Filter<FilterValid>, SchemaError> {
715        // TODO: Add a schema validation cache that can return pre-validated filters.
716
717        Ok(Filter {
718            state: FilterValid {
719                inner: self.state.inner.validate(schema)?,
720            },
721        })
722    }
723
724    // This has to have two versions to account for ro/rw traits, because RS can't
725    // monomorphise on the trait to call clone_value. An option is to make a fn that
726    // takes "clone_value(t, a, v) instead, but that may have a similar issue.
727    #[instrument(name = "filter::from_ro", level = "trace", skip_all)]
728    pub fn from_ro(
729        ev: &Identity,
730        f: &ProtoFilter,
731        qs: &mut QueryServerReadTransaction,
732    ) -> Result<Self, OperationError> {
733        let depth = DEFAULT_LIMIT_FILTER_DEPTH_MAX as usize;
734        let mut elems = ev.limits().filter_max_elements;
735        Ok(Filter {
736            state: FilterInvalid {
737                inner: FilterComp::from_ro(f, qs, depth, &mut elems)?,
738            },
739        })
740    }
741
742    #[instrument(name = "filter::from_rw", level = "trace", skip_all)]
743    pub fn from_rw(
744        ev: &Identity,
745        f: &ProtoFilter,
746        qs: &mut QueryServerWriteTransaction,
747    ) -> Result<Self, OperationError> {
748        let depth = DEFAULT_LIMIT_FILTER_DEPTH_MAX as usize;
749        let mut elems = ev.limits().filter_max_elements;
750        Ok(Filter {
751            state: FilterInvalid {
752                inner: FilterComp::from_rw(f, qs, depth, &mut elems)?,
753            },
754        })
755    }
756
757    #[instrument(name = "filter::from_ldap_ro", level = "trace", skip_all)]
758    pub fn from_ldap_ro(
759        ev: &Identity,
760        f: &LdapFilter,
761        qs: &mut QueryServerReadTransaction,
762    ) -> Result<Self, OperationError> {
763        let depth = DEFAULT_LIMIT_FILTER_DEPTH_MAX as usize;
764        let mut elems = ev.limits().filter_max_elements;
765        Ok(Filter {
766            state: FilterInvalid {
767                inner: FilterComp::from_ldap_ro(f, qs, depth, &mut elems)?,
768            },
769        })
770    }
771
772    #[instrument(name = "filter::from_scim_ro", level = "trace", skip_all)]
773    pub fn from_scim_ro(
774        ev: &Identity,
775        f: &ScimFilter,
776        qs: &mut QueryServerReadTransaction,
777    ) -> Result<Self, OperationError> {
778        let depth = DEFAULT_LIMIT_FILTER_DEPTH_MAX as usize;
779        let mut elems = ev.limits().filter_max_elements;
780        Ok(Filter {
781            state: FilterInvalid {
782                inner: FilterComp::from_scim_ro(f, qs, depth, &mut elems)?,
783            },
784        })
785    }
786}
787
788impl FromStr for Filter<FilterInvalid> {
789    type Err = OperationError;
790    fn from_str(s: &str) -> Result<Self, Self::Err> {
791        let f: FC = serde_json::from_str(s).map_err(|_| OperationError::FilterParseError)?;
792        Ok(Filter {
793            state: FilterInvalid {
794                inner: FilterComp::new(f),
795            },
796        })
797    }
798}
799
800impl FilterComp {
801    fn new(fc: FC) -> Self {
802        match fc {
803            FC::Eq(a, v) => FilterComp::Eq(a, v),
804            FC::Cnt(a, v) => FilterComp::Cnt(a, v),
805            FC::Pres(a) => FilterComp::Pres(a),
806            FC::LessThan(a, v) => FilterComp::LessThan(a, v),
807            FC::Or(v) => FilterComp::Or(v.into_iter().map(FilterComp::new).collect()),
808            FC::And(v) => FilterComp::And(v.into_iter().map(FilterComp::new).collect()),
809            FC::Inclusion(v) => FilterComp::Inclusion(v.into_iter().map(FilterComp::new).collect()),
810            FC::AndNot(b) => FilterComp::AndNot(Box::new(FilterComp::new(*b))),
811            FC::SelfUuid => FilterComp::SelfUuid,
812            FC::Invalid(a) => FilterComp::Invalid(a),
813        }
814    }
815
816    fn new_ignore_hidden(fc: FilterComp) -> Self {
817        FilterComp::And(vec![
818            FilterComp::AndNot(Box::new(FilterComp::Or(vec![
819                FilterComp::Eq(Attribute::Class, EntryClass::Tombstone.into()),
820                FilterComp::Eq(Attribute::Class, EntryClass::Recycled.into()),
821            ]))),
822            fc,
823        ])
824    }
825
826    fn new_recycled(fc: FilterComp) -> Self {
827        FilterComp::And(vec![
828            FilterComp::Eq(Attribute::Class, EntryClass::Recycled.into()),
829            fc,
830        ])
831    }
832
833    fn get_attr_set(&self, r_set: &mut BTreeSet<Attribute>) {
834        match self {
835            FilterComp::Eq(attr, _)
836            | FilterComp::Cnt(attr, _)
837            | FilterComp::Stw(attr, _)
838            | FilterComp::Enw(attr, _)
839            | FilterComp::Pres(attr)
840            | FilterComp::LessThan(attr, _)
841            | FilterComp::Invalid(attr) => {
842                r_set.insert(attr.clone());
843            }
844            FilterComp::Or(vs) => vs.iter().for_each(|f| f.get_attr_set(r_set)),
845            FilterComp::And(vs) => vs.iter().for_each(|f| f.get_attr_set(r_set)),
846            FilterComp::Inclusion(vs) => vs.iter().for_each(|f| f.get_attr_set(r_set)),
847            FilterComp::AndNot(f) => f.get_attr_set(r_set),
848            FilterComp::SelfUuid => {
849                r_set.insert(Attribute::Uuid);
850            }
851        }
852    }
853
854    fn validate(&self, schema: &dyn SchemaTransaction) -> Result<FilterComp, SchemaError> {
855        // Optimisation is done at another stage.
856
857        // This probably needs some rework
858
859        // Getting this each recursion could be slow. Maybe
860        // we need an inner function that passes the reference?
861        let schema_attributes = schema.get_attributes();
862        // We used to check the attr_name by normalising it (lowercasing)
863        // but should we? I think we actually should just call a special
864        // handler on schema to fix it up.
865
866        match self {
867            FilterComp::Eq(attr, value) => {
868                // Check the requested attribute exists, and this PV type matches something
869                // that can be queried of the attribute.
870                match schema_attributes.get(attr) {
871                    Some(schema_a) => {
872                        schema_a
873                            .validate_partialvalue(attr, value)
874                            // Okay, it worked, transform to a filter component
875                            .map(|_| FilterComp::Eq(attr.clone(), value.clone()))
876                        // On error, pass the error back out.
877                    }
878                    None => Err(SchemaError::InvalidAttribute(attr.to_string())),
879                }
880            }
881            FilterComp::Cnt(attr, value) => {
882                match schema_attributes.get(attr) {
883                    Some(schema_a) => {
884                        schema_a
885                            .validate_partialvalue(attr, value)
886                            // Okay, it worked, transform to a filter component
887                            .map(|_| FilterComp::Cnt(attr.clone(), value.clone()))
888                        // On error, pass the error back out.
889                    }
890                    None => Err(SchemaError::InvalidAttribute(attr.to_string())),
891                }
892            }
893            FilterComp::Stw(attr, value) => {
894                match schema_attributes.get(attr) {
895                    Some(schema_a) => {
896                        schema_a
897                            .validate_partialvalue(attr, value)
898                            // Okay, it worked, transform to a filter component
899                            .map(|_| FilterComp::Stw(attr.clone(), value.clone()))
900                        // On error, pass the error back out.
901                    }
902                    None => Err(SchemaError::InvalidAttribute(attr.to_string())),
903                }
904            }
905            FilterComp::Enw(attr, value) => {
906                match schema_attributes.get(attr) {
907                    Some(schema_a) => {
908                        schema_a
909                            .validate_partialvalue(attr, value)
910                            // Okay, it worked, transform to a filter component
911                            .map(|_| FilterComp::Enw(attr.clone(), value.clone()))
912                        // On error, pass the error back out.
913                    }
914                    None => Err(SchemaError::InvalidAttribute(attr.to_string())),
915                }
916            }
917            FilterComp::Pres(attr) => {
918                match schema_attributes.get(attr) {
919                    Some(_attr_name) => {
920                        // Return our valid data
921                        Ok(FilterComp::Pres(attr.clone()))
922                    }
923                    None => Err(SchemaError::InvalidAttribute(attr.to_string())),
924                }
925            }
926            FilterComp::LessThan(attr, value) => {
927                match schema_attributes.get(attr) {
928                    Some(schema_a) => {
929                        schema_a
930                            .validate_partialvalue(attr, value)
931                            // Okay, it worked, transform to a filter component
932                            .map(|_| FilterComp::LessThan(attr.clone(), value.clone()))
933                        // On error, pass the error back out.
934                    }
935                    None => Err(SchemaError::InvalidAttribute(attr.to_string())),
936                }
937            }
938            FilterComp::Or(filters) => {
939                // * If all filters are okay, return Ok(Filter::Or())
940                // * Any filter is invalid, return the error.
941                // * An empty "or" is a valid filter in mathematical terms, but we throw an
942                //   error to warn the user because it's super unlikely they want that
943                if filters.is_empty() {
944                    return Err(SchemaError::EmptyFilter);
945                };
946                let x: Result<Vec<_>, _> = filters
947                    .iter()
948                    .map(|filter| filter.validate(schema))
949                    .collect();
950                // Now put the valid filters into the Filter
951                x.map(FilterComp::Or)
952            }
953            FilterComp::And(filters) => {
954                // * If all filters are okay, return Ok(Filter::Or())
955                // * Any filter is invalid, return the error.
956                // * An empty "and" is a valid filter in mathematical terms, but we throw an
957                //   error to warn the user because it's super unlikely they want that
958                if filters.is_empty() {
959                    return Err(SchemaError::EmptyFilter);
960                };
961                let x: Result<Vec<_>, _> = filters
962                    .iter()
963                    .map(|filter| filter.validate(schema))
964                    .collect();
965                // Now put the valid filters into the Filter
966                x.map(FilterComp::And)
967            }
968            FilterComp::Inclusion(filters) => {
969                if filters.is_empty() {
970                    return Err(SchemaError::EmptyFilter);
971                };
972                let x: Result<Vec<_>, _> = filters
973                    .iter()
974                    .map(|filter| filter.validate(schema))
975                    .collect();
976                // Now put the valid filters into the Filter
977                x.map(FilterComp::Inclusion)
978            }
979            FilterComp::AndNot(filter) => {
980                // Just validate the inner
981                filter
982                    .validate(schema)
983                    .map(|r_filter| FilterComp::AndNot(Box::new(r_filter)))
984            }
985            FilterComp::SelfUuid => {
986                // Pretty hard to mess this one up ;)
987                Ok(FilterComp::SelfUuid)
988            }
989            FilterComp::Invalid(attr) => {
990                // FilterComp may be invalid but Invalid is still a valid value.
991                // we continue the evaluation so OR queries can still succeed
992                Ok(FilterComp::Invalid(attr.clone()))
993            }
994        }
995    }
996
997    fn from_ro(
998        f: &ProtoFilter,
999        qs: &mut QueryServerReadTransaction,
1000        depth: usize,
1001        elems: &mut usize,
1002    ) -> Result<Self, OperationError> {
1003        let ndepth = depth.checked_sub(1).ok_or(OperationError::ResourceLimit)?;
1004        Ok(match f {
1005            ProtoFilter::Eq(a, v) => {
1006                let nk = Attribute::from(a.as_str());
1007                let v = qs.clone_partialvalue(&nk, v)?;
1008                FilterComp::Eq(nk, v)
1009            }
1010            ProtoFilter::Cnt(a, v) => {
1011                let nk = Attribute::from(a.as_str());
1012                let v = qs.clone_partialvalue(&nk, v)?;
1013                FilterComp::Cnt(nk, v)
1014            }
1015            ProtoFilter::Pres(a) => {
1016                let nk = Attribute::from(a.as_str());
1017                FilterComp::Pres(nk)
1018            }
1019            ProtoFilter::Or(l) => {
1020                *elems = (*elems)
1021                    .checked_sub(l.len())
1022                    .ok_or(OperationError::ResourceLimit)?;
1023                FilterComp::Or(
1024                    l.iter()
1025                        .map(|f| Self::from_ro(f, qs, ndepth, elems))
1026                        .collect::<Result<Vec<_>, _>>()?,
1027                )
1028            }
1029            ProtoFilter::And(l) => {
1030                *elems = (*elems)
1031                    .checked_sub(l.len())
1032                    .ok_or(OperationError::ResourceLimit)?;
1033                FilterComp::And(
1034                    l.iter()
1035                        .map(|f| Self::from_ro(f, qs, ndepth, elems))
1036                        .collect::<Result<Vec<_>, _>>()?,
1037                )
1038            }
1039            ProtoFilter::AndNot(l) => {
1040                *elems = (*elems)
1041                    .checked_sub(1)
1042                    .ok_or(OperationError::ResourceLimit)?;
1043                FilterComp::AndNot(Box::new(Self::from_ro(l, qs, ndepth, elems)?))
1044            }
1045            ProtoFilter::SelfUuid => FilterComp::SelfUuid,
1046        })
1047    }
1048
1049    fn from_rw(
1050        f: &ProtoFilter,
1051        qs: &mut QueryServerWriteTransaction,
1052        depth: usize,
1053        elems: &mut usize,
1054    ) -> Result<Self, OperationError> {
1055        let ndepth = depth.checked_sub(1).ok_or(OperationError::ResourceLimit)?;
1056        Ok(match f {
1057            ProtoFilter::Eq(a, v) => {
1058                let nk = Attribute::from(a.as_str());
1059                let v = qs.clone_partialvalue(&nk, v)?;
1060                FilterComp::Eq(nk, v)
1061            }
1062            ProtoFilter::Cnt(a, v) => {
1063                let nk = Attribute::from(a.as_str());
1064                let v = qs.clone_partialvalue(&nk, v)?;
1065                FilterComp::Cnt(nk, v)
1066            }
1067            ProtoFilter::Pres(a) => {
1068                let nk = Attribute::from(a.as_str());
1069                FilterComp::Pres(nk)
1070            }
1071            ProtoFilter::Or(l) => {
1072                *elems = (*elems)
1073                    .checked_sub(l.len())
1074                    .ok_or(OperationError::ResourceLimit)?;
1075                FilterComp::Or(
1076                    l.iter()
1077                        .map(|f| Self::from_rw(f, qs, ndepth, elems))
1078                        .collect::<Result<Vec<_>, _>>()?,
1079                )
1080            }
1081            ProtoFilter::And(l) => {
1082                *elems = (*elems)
1083                    .checked_sub(l.len())
1084                    .ok_or(OperationError::ResourceLimit)?;
1085                FilterComp::And(
1086                    l.iter()
1087                        .map(|f| Self::from_rw(f, qs, ndepth, elems))
1088                        .collect::<Result<Vec<_>, _>>()?,
1089                )
1090            }
1091            ProtoFilter::AndNot(l) => {
1092                *elems = (*elems)
1093                    .checked_sub(1)
1094                    .ok_or(OperationError::ResourceLimit)?;
1095
1096                FilterComp::AndNot(Box::new(Self::from_rw(l, qs, ndepth, elems)?))
1097            }
1098            ProtoFilter::SelfUuid => FilterComp::SelfUuid,
1099        })
1100    }
1101
1102    fn from_ldap_ro(
1103        f: &LdapFilter,
1104        qs: &mut QueryServerReadTransaction,
1105        depth: usize,
1106        elems: &mut usize,
1107    ) -> Result<Self, OperationError> {
1108        let ndepth = depth.checked_sub(1).ok_or(OperationError::ResourceLimit)?;
1109        *elems = (*elems)
1110            .checked_sub(1)
1111            .ok_or(OperationError::ResourceLimit)?;
1112        Ok(match f {
1113            LdapFilter::And(l) => FilterComp::And(
1114                l.iter()
1115                    .map(|f| Self::from_ldap_ro(f, qs, ndepth, elems))
1116                    .collect::<Result<Vec<_>, _>>()?,
1117            ),
1118            LdapFilter::Or(l) => FilterComp::Or(
1119                l.iter()
1120                    .map(|f| Self::from_ldap_ro(f, qs, ndepth, elems))
1121                    .collect::<Result<Vec<_>, _>>()?,
1122            ),
1123            LdapFilter::Not(l) => {
1124                FilterComp::AndNot(Box::new(Self::from_ldap_ro(l, qs, ndepth, elems)?))
1125            }
1126            LdapFilter::Equality(a, v) => {
1127                let a = ldap_attr_filter_map(a);
1128                let pv = qs.clone_partialvalue(&a, v);
1129
1130                match pv {
1131                    Ok(pv) => FilterComp::Eq(a, pv),
1132                    Err(_) if a == Attribute::Spn => FilterComp::Invalid(a),
1133                    Err(err) => return Err(err),
1134                }
1135            }
1136            LdapFilter::Present(a) => FilterComp::Pres(ldap_attr_filter_map(a)),
1137            LdapFilter::Substring(
1138                a,
1139                LdapSubstringFilter {
1140                    initial,
1141                    any,
1142                    final_,
1143                },
1144            ) => {
1145                let a = ldap_attr_filter_map(a);
1146
1147                let mut terms = Vec::with_capacity(any.len() + 2);
1148                if let Some(ini) = initial {
1149                    let v = qs.clone_partialvalue(&a, ini)?;
1150                    terms.push(FilterComp::Stw(a.clone(), v));
1151                }
1152
1153                for term in any.iter() {
1154                    let v = qs.clone_partialvalue(&a, term)?;
1155                    terms.push(FilterComp::Cnt(a.clone(), v));
1156                }
1157
1158                if let Some(fin) = final_ {
1159                    let v = qs.clone_partialvalue(&a, fin)?;
1160                    terms.push(FilterComp::Enw(a.clone(), v));
1161                }
1162
1163                FilterComp::And(terms)
1164            }
1165            LdapFilter::GreaterOrEqual(_, _) => {
1166                admin_error!("Unsupported filter operation - greater or equal");
1167                return Err(OperationError::FilterGeneration);
1168            }
1169            LdapFilter::LessOrEqual(_, _) => {
1170                admin_error!("Unsupported filter operation - less or equal");
1171                return Err(OperationError::FilterGeneration);
1172            }
1173            LdapFilter::Approx(_, _) => {
1174                admin_error!("Unsupported filter operation - approximate");
1175                return Err(OperationError::FilterGeneration);
1176            }
1177            LdapFilter::Extensible(_) => {
1178                admin_error!("Unsupported filter operation - extensible");
1179                return Err(OperationError::FilterGeneration);
1180            }
1181        })
1182    }
1183
1184    fn from_scim_ro(
1185        f: &ScimFilter,
1186        qs: &mut QueryServerReadTransaction,
1187        depth: usize,
1188        elems: &mut usize,
1189    ) -> Result<Self, OperationError> {
1190        let ndepth = depth.checked_sub(1).ok_or(OperationError::ResourceLimit)?;
1191        *elems = (*elems)
1192            .checked_sub(1)
1193            .ok_or(OperationError::ResourceLimit)?;
1194        Ok(match f {
1195            ScimFilter::Present(ScimAttrPath { a, s: None }) => FilterComp::Pres(a.clone()),
1196            ScimFilter::Equal(ScimAttrPath { a, s: None }, json_value) => {
1197                let pv = qs.resolve_scim_json_get(a, json_value)?;
1198                FilterComp::Eq(a.clone(), pv)
1199            }
1200            ScimFilter::Contains(ScimAttrPath { a, s: None }, json_value) => {
1201                let pv = qs.resolve_scim_json_get(a, json_value)?;
1202                FilterComp::Cnt(a.clone(), pv)
1203            }
1204            ScimFilter::StartsWith(ScimAttrPath { a, s: None }, json_value) => {
1205                let pv = qs.resolve_scim_json_get(a, json_value)?;
1206                FilterComp::Stw(a.clone(), pv)
1207            }
1208            ScimFilter::EndsWith(ScimAttrPath { a, s: None }, json_value) => {
1209                let pv = qs.resolve_scim_json_get(a, json_value)?;
1210                FilterComp::Enw(a.clone(), pv)
1211            }
1212            ScimFilter::Greater(ScimAttrPath { a, s: None }, json_value) => {
1213                let pv = qs.resolve_scim_json_get(a, json_value)?;
1214                // Greater is equivalent to "not equal or less than".
1215                FilterComp::And(vec![
1216                    FilterComp::Pres(a.clone()),
1217                    FilterComp::AndNot(Box::new(FilterComp::Or(vec![
1218                        FilterComp::LessThan(a.clone(), pv.clone()),
1219                        FilterComp::Eq(a.clone(), pv),
1220                    ]))),
1221                ])
1222            }
1223            ScimFilter::Less(ScimAttrPath { a, s: None }, json_value) => {
1224                let pv = qs.resolve_scim_json_get(a, json_value)?;
1225                FilterComp::LessThan(a.clone(), pv)
1226            }
1227            ScimFilter::GreaterOrEqual(ScimAttrPath { a, s: None }, json_value) => {
1228                let pv = qs.resolve_scim_json_get(a, json_value)?;
1229                // Greater or equal is equivalent to "not less than".
1230                FilterComp::And(vec![
1231                    FilterComp::Pres(a.clone()),
1232                    FilterComp::AndNot(Box::new(FilterComp::LessThan(a.clone(), pv.clone()))),
1233                ])
1234            }
1235            ScimFilter::LessOrEqual(ScimAttrPath { a, s: None }, json_value) => {
1236                let pv = qs.resolve_scim_json_get(a, json_value)?;
1237                FilterComp::Or(vec![
1238                    FilterComp::LessThan(a.clone(), pv.clone()),
1239                    FilterComp::Eq(a.clone(), pv),
1240                ])
1241            }
1242            ScimFilter::Not(f) => {
1243                let f = Self::from_scim_ro(f, qs, ndepth, elems)?;
1244                FilterComp::AndNot(Box::new(f))
1245            }
1246            ScimFilter::Or(left, right) => {
1247                let left = Self::from_scim_ro(left, qs, ndepth, elems)?;
1248                let right = Self::from_scim_ro(right, qs, ndepth, elems)?;
1249                FilterComp::Or(vec![left, right])
1250            }
1251            ScimFilter::And(left, right) => {
1252                let left = Self::from_scim_ro(left, qs, ndepth, elems)?;
1253                let right = Self::from_scim_ro(right, qs, ndepth, elems)?;
1254                FilterComp::And(vec![left, right])
1255            }
1256            ScimFilter::NotEqual(ScimAttrPath { s: None, .. }, _) => {
1257                error!("Unsupported filter operation - not-equal");
1258                return Err(OperationError::FilterGeneration);
1259            }
1260            ScimFilter::Present(ScimAttrPath { s: Some(_), .. })
1261            | ScimFilter::Equal(ScimAttrPath { s: Some(_), .. }, _)
1262            | ScimFilter::NotEqual(ScimAttrPath { s: Some(_), .. }, _)
1263            | ScimFilter::Contains(ScimAttrPath { s: Some(_), .. }, _)
1264            | ScimFilter::StartsWith(ScimAttrPath { s: Some(_), .. }, _)
1265            | ScimFilter::EndsWith(ScimAttrPath { s: Some(_), .. }, _)
1266            | ScimFilter::Greater(ScimAttrPath { s: Some(_), .. }, _)
1267            | ScimFilter::Less(ScimAttrPath { s: Some(_), .. }, _)
1268            | ScimFilter::GreaterOrEqual(ScimAttrPath { s: Some(_), .. }, _)
1269            | ScimFilter::LessOrEqual(ScimAttrPath { s: Some(_), .. }, _) => {
1270                error!("Unsupported filter operation - sub-attribute");
1271                return Err(OperationError::FilterGeneration);
1272            }
1273            ScimFilter::Complex(..) => {
1274                error!("Unsupported filter operation - complex");
1275                return Err(OperationError::FilterGeneration);
1276            }
1277        })
1278    }
1279}
1280
1281/* We only configure partial eq if cfg test on the invalid/valid types */
1282/*
1283impl PartialEq for Filter<FilterInvalid> {
1284    fn eq(&self, rhs: &Filter<FilterInvalid>) -> bool {
1285        self.state.inner == rhs.state.inner
1286    }
1287}
1288
1289impl PartialEq for Filter<FilterValid> {
1290    fn eq(&self, rhs: &Filter<FilterValid>) -> bool {
1291        self.state.inner == rhs.state.inner
1292    }
1293}
1294
1295impl PartialEq for Filter<FilterValidResolved> {
1296    fn eq(&self, rhs: &Filter<FilterValidResolved>) -> bool {
1297        self.state.inner == rhs.state.inner
1298    }
1299}
1300*/
1301
1302/*
1303 * Only needed in tests, in run time order only matters on the inner for
1304 * optimisation.
1305 */
1306#[cfg(test)]
1307impl PartialOrd for Filter<FilterValidResolved> {
1308    fn partial_cmp(&self, rhs: &Filter<FilterValidResolved>) -> Option<Ordering> {
1309        self.state.inner.partial_cmp(&rhs.state.inner)
1310    }
1311}
1312
1313impl PartialEq for FilterResolved {
1314    fn eq(&self, rhs: &FilterResolved) -> bool {
1315        match (self, rhs) {
1316            (FilterResolved::Eq(a1, v1, _), FilterResolved::Eq(a2, v2, _)) => a1 == a2 && v1 == v2,
1317            (FilterResolved::Cnt(a1, v1, _), FilterResolved::Cnt(a2, v2, _)) => {
1318                a1 == a2 && v1 == v2
1319            }
1320            (FilterResolved::Pres(a1, _), FilterResolved::Pres(a2, _)) => a1 == a2,
1321            (FilterResolved::LessThan(a1, v1, _), FilterResolved::LessThan(a2, v2, _)) => {
1322                a1 == a2 && v1 == v2
1323            }
1324            (FilterResolved::And(vs1, _), FilterResolved::And(vs2, _)) => vs1 == vs2,
1325            (FilterResolved::Or(vs1, _), FilterResolved::Or(vs2, _)) => vs1 == vs2,
1326            (FilterResolved::Inclusion(vs1, _), FilterResolved::Inclusion(vs2, _)) => vs1 == vs2,
1327            (FilterResolved::AndNot(f1, _), FilterResolved::AndNot(f2, _)) => f1 == f2,
1328            (_, _) => false,
1329        }
1330    }
1331}
1332
1333impl PartialOrd for FilterResolved {
1334    fn partial_cmp(&self, rhs: &FilterResolved) -> Option<Ordering> {
1335        Some(self.cmp(rhs))
1336    }
1337}
1338
1339impl Ord for FilterResolved {
1340    /// Ordering of filters for optimisation and subsequent dead term elimination.
1341    fn cmp(&self, rhs: &FilterResolved) -> Ordering {
1342        let left_slopey = self.get_slopeyness_factor();
1343        let right_slopey = rhs.get_slopeyness_factor();
1344
1345        let r = match (left_slopey, right_slopey) {
1346            (Some(sfl), Some(sfr)) => sfl.cmp(&sfr),
1347            (Some(_), None) => Ordering::Less,
1348            (None, Some(_)) => Ordering::Greater,
1349            (None, None) => Ordering::Equal,
1350        };
1351
1352        // If they are equal, compare other elements for determining the order. This is what
1353        // allows dead term elimination to occur.
1354        //
1355        // In almost all cases, we'll miss this step though as slopes will vary distinctly.
1356        //
1357        // We do NOT need to check for indexed vs unindexed here, we already did it in the slope check!
1358        if r == Ordering::Equal {
1359            match (self, rhs) {
1360                (FilterResolved::Eq(a1, v1, _), FilterResolved::Eq(a2, v2, _))
1361                | (FilterResolved::Cnt(a1, v1, _), FilterResolved::Cnt(a2, v2, _))
1362                | (FilterResolved::LessThan(a1, v1, _), FilterResolved::LessThan(a2, v2, _)) => {
1363                    match a1.cmp(a2) {
1364                        Ordering::Equal => v1.cmp(v2),
1365                        o => o,
1366                    }
1367                }
1368                (FilterResolved::Pres(a1, _), FilterResolved::Pres(a2, _)) => a1.cmp(a2),
1369                // Now sort these into the generally "best" order.
1370                (FilterResolved::Eq(_, _, _), _) => Ordering::Less,
1371                (_, FilterResolved::Eq(_, _, _)) => Ordering::Greater,
1372                (FilterResolved::Pres(_, _), _) => Ordering::Less,
1373                (_, FilterResolved::Pres(_, _)) => Ordering::Greater,
1374                (FilterResolved::LessThan(_, _, _), _) => Ordering::Less,
1375                (_, FilterResolved::LessThan(_, _, _)) => Ordering::Greater,
1376                (FilterResolved::Cnt(_, _, _), _) => Ordering::Less,
1377                (_, FilterResolved::Cnt(_, _, _)) => Ordering::Greater,
1378                // They can't be re-arranged, they don't move!
1379                (_, _) => Ordering::Equal,
1380            }
1381        } else {
1382            r
1383        }
1384    }
1385}
1386
1387impl FilterResolved {
1388    /// ⚠️  - Process a filter without verifying with schema.
1389    /// This is a TEST ONLY method and will never be exposed in production.
1390    #[cfg(test)]
1391    fn from_invalid(fc: FilterComp, idxmeta: &HashSet<(&Attribute, &IndexType)>) -> Self {
1392        match fc {
1393            FilterComp::Eq(a, v) => {
1394                let idx = idxmeta.contains(&(&a, &IndexType::Equality));
1395                let idx = NonZeroU8::new(idx as u8);
1396                FilterResolved::Eq(a, v, idx)
1397            }
1398            FilterComp::SelfUuid => panic!("Not possible to resolve SelfUuid in from_invalid!"),
1399            FilterComp::Invalid(attr) => FilterResolved::Invalid(attr),
1400            FilterComp::Cnt(a, v) => {
1401                let idx = idxmeta.contains(&(&a, &IndexType::SubString));
1402                let idx = NonZeroU8::new(idx as u8);
1403                FilterResolved::Cnt(a, v, idx)
1404            }
1405            FilterComp::Stw(a, v) => {
1406                let idx = idxmeta.contains(&(&a, &IndexType::SubString));
1407                let idx = NonZeroU8::new(idx as u8);
1408                FilterResolved::Stw(a, v, idx)
1409            }
1410            FilterComp::Enw(a, v) => {
1411                let idx = idxmeta.contains(&(&a, &IndexType::SubString));
1412                let idx = NonZeroU8::new(idx as u8);
1413                FilterResolved::Enw(a, v, idx)
1414            }
1415            FilterComp::Pres(a) => {
1416                let idx = idxmeta.contains(&(&a, &IndexType::Presence));
1417                FilterResolved::Pres(a, NonZeroU8::new(idx as u8))
1418            }
1419            FilterComp::LessThan(a, v) => {
1420                // let idx = idxmeta.contains(&(&a, &IndexType::ORDERING));
1421                // TODO: For now, don't emit ordering indexes.
1422                FilterResolved::LessThan(a, v, None)
1423            }
1424            FilterComp::Or(vs) => FilterResolved::Or(
1425                vs.into_iter()
1426                    .map(|v| FilterResolved::from_invalid(v, idxmeta))
1427                    .collect(),
1428                None,
1429            ),
1430            FilterComp::And(vs) => FilterResolved::And(
1431                vs.into_iter()
1432                    .map(|v| FilterResolved::from_invalid(v, idxmeta))
1433                    .collect(),
1434                None,
1435            ),
1436            FilterComp::Inclusion(vs) => FilterResolved::Inclusion(
1437                vs.into_iter()
1438                    .map(|v| FilterResolved::from_invalid(v, idxmeta))
1439                    .collect(),
1440                None,
1441            ),
1442            FilterComp::AndNot(f) => {
1443                // TODO: pattern match box here. (AndNot(box f)).
1444                // We have to clone f into our space here because pattern matching can
1445                // not today remove the box, and we need f in our ownership. Since
1446                // AndNot currently is a rare request, cloning is not the worst thing
1447                // here ...
1448                FilterResolved::AndNot(
1449                    Box::new(FilterResolved::from_invalid((*f).clone(), idxmeta)),
1450                    None,
1451                )
1452            }
1453        }
1454    }
1455
1456    fn resolve_cacheable(fc: &FilterComp) -> bool {
1457        match fc {
1458            FilterComp::Or(vs) | FilterComp::And(vs) | FilterComp::Inclusion(vs) => {
1459                if vs.len() < 8 {
1460                    vs.iter().all(FilterResolved::resolve_cacheable)
1461                } else {
1462                    // Too lorge.
1463                    false
1464                }
1465            }
1466            FilterComp::AndNot(f) => FilterResolved::resolve_cacheable(f.as_ref()),
1467            FilterComp::Eq(..)
1468            | FilterComp::SelfUuid
1469            | FilterComp::Cnt(..)
1470            | FilterComp::Stw(..)
1471            | FilterComp::Enw(..)
1472            | FilterComp::Pres(_)
1473            | FilterComp::Invalid(_)
1474            | FilterComp::LessThan(..) => true,
1475        }
1476    }
1477
1478    fn resolve_idx(
1479        fc: FilterComp,
1480        ev: &Identity,
1481        idxmeta: &HashMap<IdxKey, IdxSlope>,
1482    ) -> Option<Self> {
1483        match fc {
1484            FilterComp::Eq(a, v) => {
1485                let idxkref = IdxKeyRef::new(&a, &IndexType::Equality);
1486                let idx = idxmeta
1487                    .get(&idxkref as &dyn IdxKeyToRef)
1488                    .copied()
1489                    .and_then(NonZeroU8::new);
1490                Some(FilterResolved::Eq(a, v, idx))
1491            }
1492            FilterComp::SelfUuid => ev.get_uuid().map(|uuid| {
1493                let idxkref = IdxKeyRef::new(Attribute::Uuid.as_ref(), &IndexType::Equality);
1494                let idx = idxmeta
1495                    .get(&idxkref as &dyn IdxKeyToRef)
1496                    .copied()
1497                    .and_then(NonZeroU8::new);
1498                FilterResolved::Eq(Attribute::Uuid, PartialValue::Uuid(uuid), idx)
1499            }),
1500            FilterComp::Cnt(a, v) => {
1501                let idxkref = IdxKeyRef::new(&a, &IndexType::SubString);
1502                let idx = idxmeta
1503                    .get(&idxkref as &dyn IdxKeyToRef)
1504                    .copied()
1505                    .and_then(NonZeroU8::new);
1506                Some(FilterResolved::Cnt(a, v, idx))
1507            }
1508            FilterComp::Stw(a, v) => {
1509                let idxkref = IdxKeyRef::new(&a, &IndexType::SubString);
1510                let idx = idxmeta
1511                    .get(&idxkref as &dyn IdxKeyToRef)
1512                    .copied()
1513                    .and_then(NonZeroU8::new);
1514                Some(FilterResolved::Stw(a, v, idx))
1515            }
1516            FilterComp::Enw(a, v) => {
1517                let idxkref = IdxKeyRef::new(&a, &IndexType::SubString);
1518                let idx = idxmeta
1519                    .get(&idxkref as &dyn IdxKeyToRef)
1520                    .copied()
1521                    .and_then(NonZeroU8::new);
1522                Some(FilterResolved::Enw(a, v, idx))
1523            }
1524            FilterComp::Pres(a) => {
1525                let idxkref = IdxKeyRef::new(&a, &IndexType::Presence);
1526                let idx = idxmeta
1527                    .get(&idxkref as &dyn IdxKeyToRef)
1528                    .copied()
1529                    .and_then(NonZeroU8::new);
1530                Some(FilterResolved::Pres(a, idx))
1531            }
1532            FilterComp::LessThan(a, v) => {
1533                // let idx = idxmeta.contains(&(&a, &IndexType::SubString));
1534                Some(FilterResolved::LessThan(a, v, None))
1535            }
1536            // We set the compound filters slope factor to "None" here, because when we do
1537            // optimise we'll actually fill in the correct slope factors after we sort those
1538            // inner terms in a more optimal way.
1539            FilterComp::Or(vs) => {
1540                let fi: Option<Vec<_>> = vs
1541                    .into_iter()
1542                    .map(|f| FilterResolved::resolve_idx(f, ev, idxmeta))
1543                    .collect();
1544                fi.map(|fi| FilterResolved::Or(fi, None))
1545            }
1546            FilterComp::And(vs) => {
1547                let fi: Option<Vec<_>> = vs
1548                    .into_iter()
1549                    .map(|f| FilterResolved::resolve_idx(f, ev, idxmeta))
1550                    .collect();
1551                fi.map(|fi| FilterResolved::And(fi, None))
1552            }
1553            FilterComp::Inclusion(vs) => {
1554                let fi: Option<Vec<_>> = vs
1555                    .into_iter()
1556                    .map(|f| FilterResolved::resolve_idx(f, ev, idxmeta))
1557                    .collect();
1558                fi.map(|fi| FilterResolved::Inclusion(fi, None))
1559            }
1560            FilterComp::AndNot(f) => {
1561                // TODO: pattern match box here. (AndNot(box f)).
1562                // We have to clone f into our space here because pattern matching can
1563                // not today remove the box, and we need f in our ownership. Since
1564                // AndNot currently is a rare request, cloning is not the worst thing
1565                // here ...
1566                FilterResolved::resolve_idx((*f).clone(), ev, idxmeta)
1567                    .map(|fi| FilterResolved::AndNot(Box::new(fi), None))
1568            }
1569            FilterComp::Invalid(attr) => Some(FilterResolved::Invalid(attr)),
1570        }
1571    }
1572
1573    fn resolve_no_idx(fc: FilterComp, ev: &Identity) -> Option<Self> {
1574        // ⚠️  ⚠️  ⚠️  ⚠️
1575        // Remember, this function means we have NO INDEX METADATA so we can only
1576        // assign slopes to values we can GUARANTEE will EXIST.
1577        match fc {
1578            FilterComp::Eq(a, v) => {
1579                // Since we have no index data, we manually configure a reasonable
1580                // slope and indicate the presence of some expected basic
1581                // indexes.
1582                let idx = matches!(a.as_str(), ATTR_NAME | ATTR_UUID);
1583                let idx = NonZeroU8::new(idx as u8);
1584                Some(FilterResolved::Eq(a, v, idx))
1585            }
1586            FilterComp::SelfUuid => ev.get_uuid().map(|uuid| {
1587                FilterResolved::Eq(
1588                    Attribute::Uuid,
1589                    PartialValue::Uuid(uuid),
1590                    NonZeroU8::new(true as u8),
1591                )
1592            }),
1593            FilterComp::Cnt(a, v) => Some(FilterResolved::Cnt(a, v, None)),
1594            FilterComp::Stw(a, v) => Some(FilterResolved::Stw(a, v, None)),
1595            FilterComp::Enw(a, v) => Some(FilterResolved::Enw(a, v, None)),
1596            FilterComp::Pres(a) => Some(FilterResolved::Pres(a, None)),
1597            FilterComp::LessThan(a, v) => Some(FilterResolved::LessThan(a, v, None)),
1598            FilterComp::Or(vs) => {
1599                let fi: Option<Vec<_>> = vs
1600                    .into_iter()
1601                    .map(|f| FilterResolved::resolve_no_idx(f, ev))
1602                    .collect();
1603                fi.map(|fi| FilterResolved::Or(fi, None))
1604            }
1605            FilterComp::And(vs) => {
1606                let fi: Option<Vec<_>> = vs
1607                    .into_iter()
1608                    .map(|f| FilterResolved::resolve_no_idx(f, ev))
1609                    .collect();
1610                fi.map(|fi| FilterResolved::And(fi, None))
1611            }
1612            FilterComp::Inclusion(vs) => {
1613                let fi: Option<Vec<_>> = vs
1614                    .into_iter()
1615                    .map(|f| FilterResolved::resolve_no_idx(f, ev))
1616                    .collect();
1617                fi.map(|fi| FilterResolved::Inclusion(fi, None))
1618            }
1619            FilterComp::AndNot(f) => {
1620                // TODO: pattern match box here. (AndNot(box f)).
1621                // We have to clone f into our space here because pattern matching can
1622                // not today remove the box, and we need f in our ownership. Since
1623                // AndNot currently is a rare request, cloning is not the worst thing
1624                // here ...
1625                FilterResolved::resolve_no_idx((*f).clone(), ev)
1626                    .map(|fi| FilterResolved::AndNot(Box::new(fi), None))
1627            }
1628            FilterComp::Invalid(attr) => Some(FilterResolved::Invalid(attr)),
1629        }
1630    }
1631
1632    // This is an optimise that only attempts to optimise the outer terms.
1633    fn fast_optimise(self) -> Self {
1634        match self {
1635            FilterResolved::Inclusion(mut f_list, _) => {
1636                f_list.sort_unstable();
1637                f_list.dedup();
1638                let sf = f_list.last().and_then(|f| f.get_slopeyness_factor());
1639                FilterResolved::Inclusion(f_list, sf)
1640            }
1641            FilterResolved::And(mut f_list, _) => {
1642                f_list.sort_unstable();
1643                f_list.dedup();
1644                let sf = f_list.first().and_then(|f| f.get_slopeyness_factor());
1645                FilterResolved::And(f_list, sf)
1646            }
1647            v => v,
1648        }
1649    }
1650
1651    fn optimise(&self) -> Self {
1652        // Most optimisations only matter around or/and terms.
1653        match self {
1654            FilterResolved::Inclusion(f_list, _) => {
1655                // first, optimise all our inner elements
1656                let (f_list_inc, mut f_list_new): (Vec<_>, Vec<_>) = f_list
1657                    .iter()
1658                    .map(|f_ref| f_ref.optimise())
1659                    .partition(|f| matches!(f, FilterResolved::Inclusion(_, _)));
1660
1661                f_list_inc.into_iter().for_each(|fc| {
1662                    if let FilterResolved::Inclusion(mut l, _) = fc {
1663                        f_list_new.append(&mut l)
1664                    }
1665                });
1666                // finally, optimise this list by sorting.
1667                f_list_new.sort_unstable();
1668                f_list_new.dedup();
1669                // Inclusions are similar to or, so what's our worst case?
1670                let sf = f_list_new.last().and_then(|f| f.get_slopeyness_factor());
1671                FilterResolved::Inclusion(f_list_new, sf)
1672            }
1673            FilterResolved::And(f_list, _) => {
1674                // first, optimise all our inner elements
1675                let (f_list_and, mut f_list_new): (Vec<_>, Vec<_>) = f_list
1676                    .iter()
1677                    .map(|f_ref| f_ref.optimise())
1678                    .partition(|f| matches!(f, FilterResolved::And(_, _)));
1679
1680                // now, iterate over this list - for each "and" term, fold
1681                // it's elements to this level.
1682                // This is one of the most important improvements because it means
1683                // that we can compare terms such that:
1684                //
1685                // (&(class=*)(&(uid=foo)))
1686                // if we did not and fold, this would remain as is. However, by and
1687                // folding, we can optimise to:
1688                // (&(uid=foo)(class=*))
1689                // Which will be faster when indexed as the uid=foo will trigger
1690                // shortcutting
1691
1692                f_list_and.into_iter().for_each(|fc| {
1693                    if let FilterResolved::And(mut l, _) = fc {
1694                        f_list_new.append(&mut l)
1695                    }
1696                });
1697
1698                // If the f_list_and only has one element, pop it and return.
1699                if f_list_new.len() == 1 {
1700                    f_list_new.remove(0)
1701                } else {
1702                    // finally, optimise this list by sorting.
1703                    f_list_new.sort_unstable();
1704                    f_list_new.dedup();
1705                    // Which ever element as the head is first must be the min SF
1706                    // so we use this in our And to represent the "best possible" value
1707                    // of how indexes will perform.
1708                    let sf = f_list_new.first().and_then(|f| f.get_slopeyness_factor());
1709                    //
1710                    // return!
1711                    FilterResolved::And(f_list_new, sf)
1712                }
1713            }
1714            FilterResolved::Or(f_list, _) => {
1715                let (f_list_or, mut f_list_new): (Vec<_>, Vec<_>) = f_list
1716                    .iter()
1717                    // Optimise all inner items.
1718                    .map(|f_ref| f_ref.optimise())
1719                    // Split out inner-or terms to fold into this term.
1720                    .partition(|f| matches!(f, FilterResolved::Or(_, _)));
1721
1722                // Append the inner terms.
1723                f_list_or.into_iter().for_each(|fc| {
1724                    if let FilterResolved::Or(mut l, _) = fc {
1725                        f_list_new.append(&mut l)
1726                    }
1727                });
1728
1729                // If the f_list_or only has one element, pop it and return.
1730                if f_list_new.len() == 1 {
1731                    f_list_new.remove(0)
1732                } else {
1733                    // sort, but reverse so that sub-optimal elements are earlier
1734                    // to promote fast-failure.
1735                    // We have to allow this on clippy, which attempts to suggest:
1736                    //   f_list_new.sort_unstable_by_key(|&b| Reverse(b))
1737                    // However, because these are references, it causes a lifetime
1738                    // issue, and fails to compile.
1739                    #[allow(clippy::unnecessary_sort_by)]
1740                    f_list_new.sort_unstable_by(|a, b| b.cmp(a));
1741                    f_list_new.dedup();
1742                    // The *last* element is the most here, and our worst case factor.
1743                    let sf = f_list_new.last().and_then(|f| f.get_slopeyness_factor());
1744                    FilterResolved::Or(f_list_new, sf)
1745                }
1746            }
1747            f => f.clone(),
1748        }
1749    }
1750
1751    pub fn is_andnot(&self) -> bool {
1752        matches!(self, FilterResolved::AndNot(_, _))
1753    }
1754
1755    #[inline(always)]
1756    fn get_slopeyness_factor(&self) -> Option<NonZeroU8> {
1757        match self {
1758            FilterResolved::Eq(_, _, sf)
1759            | FilterResolved::Cnt(_, _, sf)
1760            | FilterResolved::Stw(_, _, sf)
1761            | FilterResolved::Enw(_, _, sf)
1762            | FilterResolved::Pres(_, sf)
1763            | FilterResolved::LessThan(_, _, sf)
1764            | FilterResolved::Or(_, sf)
1765            | FilterResolved::And(_, sf)
1766            | FilterResolved::Inclusion(_, sf)
1767            | FilterResolved::AndNot(_, sf) => *sf,
1768            // We hard code 1 because there is no slope for an invlid filter
1769            FilterResolved::Invalid(_) => NonZeroU8::new(1),
1770        }
1771    }
1772}
1773
1774#[cfg(test)]
1775mod tests {
1776    use std::cmp::{Ordering, PartialOrd};
1777    use std::collections::BTreeSet;
1778    use std::time::Duration;
1779
1780    use kanidm_proto::internal::Filter as ProtoFilter;
1781    use ldap3_proto::simple::LdapFilter;
1782
1783    use crate::event::{CreateEvent, DeleteEvent};
1784    use crate::filter::{Filter, FilterInvalid, DEFAULT_LIMIT_FILTER_DEPTH_MAX};
1785    use crate::prelude::*;
1786
1787    #[test]
1788    fn test_filter_simple() {
1789        // Test construction.
1790        let _filt: Filter<FilterInvalid> = filter!(f_eq(Attribute::Class, EntryClass::User.into()));
1791
1792        // AFTER
1793        let _complex_filt: Filter<FilterInvalid> = filter!(f_and!([
1794            f_or!([
1795                f_eq(Attribute::UserId, PartialValue::new_iutf8("test_a")),
1796                f_eq(Attribute::UserId, PartialValue::new_iutf8("test_b")),
1797            ]),
1798            f_sub(Attribute::Class, EntryClass::User.into()),
1799        ]));
1800    }
1801
1802    macro_rules! filter_optimise_assert {
1803        (
1804            $init:expr,
1805            $expect:expr
1806        ) => {{
1807            #[allow(unused_imports)]
1808            use crate::filter::{f_and, f_andnot, f_eq, f_or, f_pres, f_sub};
1809            use crate::filter::{Filter, FilterInvalid};
1810            let f_init: Filter<FilterInvalid> = Filter::new($init);
1811            let f_expect: Filter<FilterInvalid> = Filter::new($expect);
1812            // Create a resolved filter, via the most unsafe means possible!
1813            let f_init_r = f_init.into_valid_resolved();
1814            let f_init_o = f_init_r.optimise();
1815            let f_init_e = f_expect.into_valid_resolved();
1816            debug!("--");
1817            debug!("init   --> {:?}", f_init_r);
1818            debug!("opt    --> {:?}", f_init_o);
1819            debug!("expect --> {:?}", f_init_e);
1820            assert_eq!(f_init_o, f_init_e);
1821        }};
1822    }
1823
1824    #[test]
1825    fn test_filter_optimise() {
1826        sketching::test_init();
1827        // Given sets of "optimisable" filters, optimise them.
1828        filter_optimise_assert!(
1829            f_and(vec![f_and(vec![f_eq(
1830                Attribute::Class,
1831                EntryClass::TestClass.into()
1832            )])]),
1833            f_eq(Attribute::Class, EntryClass::TestClass.into())
1834        );
1835
1836        filter_optimise_assert!(
1837            f_or(vec![f_or(vec![f_eq(
1838                Attribute::Class,
1839                EntryClass::TestClass.into()
1840            )])]),
1841            f_eq(Attribute::Class, EntryClass::TestClass.into())
1842        );
1843
1844        filter_optimise_assert!(
1845            f_and(vec![f_or(vec![f_and(vec![f_eq(
1846                Attribute::Class,
1847                EntryClass::TestClass.to_partialvalue()
1848            )])])]),
1849            f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue())
1850        );
1851
1852        // Later this can test duplicate filter detection.
1853        filter_optimise_assert!(
1854            f_and(vec![
1855                f_and(vec![f_eq(
1856                    Attribute::Class,
1857                    EntryClass::TestClass.to_partialvalue()
1858                )]),
1859                f_sub(Attribute::Class, PartialValue::new_iutf8("te")),
1860                f_pres(Attribute::Class),
1861                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue())
1862            ]),
1863            f_and(vec![
1864                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1865                f_pres(Attribute::Class),
1866                f_sub(Attribute::Class, PartialValue::new_iutf8("te")),
1867            ])
1868        );
1869
1870        // Test dedup removes only the correct element despite padding.
1871        filter_optimise_assert!(
1872            f_and(vec![
1873                f_and(vec![
1874                    f_eq(Attribute::Class, PartialValue::new_iutf8("foo")),
1875                    f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1876                    f_eq(Attribute::Uid, PartialValue::new_iutf8("bar")),
1877                ]),
1878                f_sub(Attribute::Class, PartialValue::new_iutf8("te")),
1879                f_pres(Attribute::Class),
1880                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue())
1881            ]),
1882            f_and(vec![
1883                f_eq(Attribute::Class, PartialValue::new_iutf8("foo")),
1884                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1885                f_pres(Attribute::Class),
1886                f_eq(Attribute::Uid, PartialValue::new_iutf8("bar")),
1887                f_sub(Attribute::Class, PartialValue::new_iutf8("te")),
1888            ])
1889        );
1890
1891        filter_optimise_assert!(
1892            f_or(vec![
1893                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1894                f_pres(Attribute::Class),
1895                f_sub(Attribute::Class, PartialValue::new_iutf8("te")),
1896                f_or(vec![f_eq(
1897                    Attribute::Class,
1898                    EntryClass::TestClass.to_partialvalue()
1899                )]),
1900            ]),
1901            f_or(vec![
1902                f_sub(Attribute::Class, PartialValue::new_iutf8("te")),
1903                f_pres(Attribute::Class),
1904                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue())
1905            ])
1906        );
1907
1908        // Test dedup doesn't affect nested items incorrectly.
1909        filter_optimise_assert!(
1910            f_or(vec![
1911                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1912                f_and(vec![
1913                    f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1914                    f_eq(Attribute::Term, EntryClass::TestClass.to_partialvalue()),
1915                    f_or(vec![f_eq(
1916                        Attribute::Class,
1917                        EntryClass::TestClass.to_partialvalue()
1918                    )])
1919                ]),
1920            ]),
1921            f_or(vec![
1922                f_and(vec![
1923                    f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1924                    f_eq(Attribute::Term, EntryClass::TestClass.to_partialvalue())
1925                ]),
1926                f_eq(Attribute::Class, EntryClass::TestClass.to_partialvalue()),
1927            ])
1928        );
1929    }
1930
1931    #[test]
1932    fn test_filter_eq() {
1933        let f_t1a = filter!(f_pres(Attribute::UserId));
1934        let f_t1b = filter!(f_pres(Attribute::UserId));
1935        let f_t1c = filter!(f_pres(Attribute::NonExist));
1936
1937        assert_eq!(f_t1a, f_t1b);
1938        assert!(f_t1a != f_t1c);
1939        assert!(f_t1b != f_t1c);
1940
1941        let f_t2a = filter!(f_and!([f_pres(Attribute::UserId)]));
1942        let f_t2b = filter!(f_and!([f_pres(Attribute::UserId)]));
1943        let f_t2c = filter!(f_and!([f_pres(Attribute::NonExist)]));
1944        assert_eq!(f_t2a, f_t2b);
1945        assert!(f_t2a != f_t2c);
1946        assert!(f_t2b != f_t2c);
1947
1948        assert!(f_t2c != f_t1a);
1949        assert!(f_t2c != f_t1c);
1950    }
1951
1952    #[test]
1953    fn test_filter_ord() {
1954        // Test that we uphold the rules of partialOrd
1955        // Basic equality
1956        // Test the two major paths here (str vs list)
1957        let f_t1a = filter_resolved!(f_pres(Attribute::UserId));
1958        let f_t1b = filter_resolved!(f_pres(Attribute::UserId));
1959
1960        assert_eq!(f_t1a.partial_cmp(&f_t1b), Some(Ordering::Equal));
1961        assert_eq!(f_t1b.partial_cmp(&f_t1a), Some(Ordering::Equal));
1962
1963        let f_t2a = filter_resolved!(f_and!([]));
1964        let f_t2b = filter_resolved!(f_and!([]));
1965        assert_eq!(f_t2a.partial_cmp(&f_t2b), Some(Ordering::Equal));
1966        assert_eq!(f_t2b.partial_cmp(&f_t2a), Some(Ordering::Equal));
1967
1968        // antisymmetry: if a < b then !(a > b), as well as a > b implying !(a < b); and
1969        // These are unindexed so we have to check them this way.
1970        let f_t3b = filter_resolved!(f_eq(Attribute::UserId, PartialValue::new_iutf8("")));
1971        assert_eq!(f_t1a.partial_cmp(&f_t3b), Some(Ordering::Greater));
1972        assert_eq!(f_t3b.partial_cmp(&f_t1a), Some(Ordering::Less));
1973
1974        // transitivity: a < b and b < c implies a < c. The same must hold for both == and >.
1975        let f_t4b = filter_resolved!(f_sub(Attribute::UserId, PartialValue::new_iutf8("")));
1976        assert_eq!(f_t1a.partial_cmp(&f_t4b), Some(Ordering::Less));
1977        assert_eq!(f_t3b.partial_cmp(&f_t4b), Some(Ordering::Less));
1978
1979        assert_eq!(f_t4b.partial_cmp(&f_t1a), Some(Ordering::Greater));
1980        assert_eq!(f_t4b.partial_cmp(&f_t3b), Some(Ordering::Greater));
1981    }
1982
1983    #[test]
1984    fn test_filter_clone() {
1985        // Test that cloning filters yields the same result regardless of
1986        // complexity.
1987        let f_t1a = filter_resolved!(f_pres(Attribute::UserId));
1988        let f_t1b = f_t1a.clone();
1989        let f_t1c = filter_resolved!(f_pres(Attribute::NonExist));
1990
1991        assert_eq!(f_t1a, f_t1b);
1992        assert!(f_t1a != f_t1c);
1993
1994        let f_t2a = filter_resolved!(f_and!([f_pres(Attribute::UserId)]));
1995        let f_t2b = f_t2a.clone();
1996        let f_t2c = filter_resolved!(f_and!([f_pres(Attribute::NonExist)]));
1997
1998        assert_eq!(f_t2a, f_t2b);
1999        assert!(f_t2a != f_t2c);
2000    }
2001
2002    #[test]
2003    fn test_lessthan_entry_filter() {
2004        let e = entry_init!(
2005            (Attribute::UserId, Value::new_iutf8("william")),
2006            (
2007                Attribute::Uuid,
2008                Value::Uuid(uuid::uuid!("db237e8a-0079-4b8c-8a56-593b22aa44d1"))
2009            ),
2010            (Attribute::GidNumber, Value::Uint32(1000))
2011        )
2012        .into_sealed_new();
2013
2014        let f_t1a = filter_resolved!(f_lt(Attribute::GidNumber, PartialValue::new_uint32(500)));
2015        assert!(!e.entry_match_no_index(&f_t1a));
2016
2017        let f_t1b = filter_resolved!(f_lt(Attribute::GidNumber, PartialValue::new_uint32(1000)));
2018        assert!(!e.entry_match_no_index(&f_t1b));
2019
2020        let f_t1c = filter_resolved!(f_lt(Attribute::GidNumber, PartialValue::new_uint32(1001)));
2021        assert!(e.entry_match_no_index(&f_t1c));
2022    }
2023
2024    #[test]
2025    fn test_or_entry_filter() {
2026        let e = entry_init!(
2027            (Attribute::UserId, Value::new_iutf8("william")),
2028            (
2029                Attribute::Uuid,
2030                Value::Uuid(uuid::uuid!("db237e8a-0079-4b8c-8a56-593b22aa44d1"))
2031            ),
2032            (Attribute::GidNumber, Value::Uint32(1000))
2033        )
2034        .into_sealed_new();
2035
2036        let f_t1a = filter_resolved!(f_or!([
2037            f_eq(Attribute::UserId, PartialValue::new_iutf8("william")),
2038            f_eq(Attribute::GidNumber, PartialValue::Uint32(1000)),
2039        ]));
2040        assert!(e.entry_match_no_index(&f_t1a));
2041
2042        let f_t2a = filter_resolved!(f_or!([
2043            f_eq(Attribute::UserId, PartialValue::new_iutf8("william")),
2044            f_eq(Attribute::GidNumber, PartialValue::Uint32(1000)),
2045        ]));
2046        assert!(e.entry_match_no_index(&f_t2a));
2047
2048        let f_t3a = filter_resolved!(f_or!([
2049            f_eq(Attribute::UserId, PartialValue::new_iutf8("alice")),
2050            f_eq(Attribute::GidNumber, PartialValue::Uint32(1000)),
2051        ]));
2052        assert!(e.entry_match_no_index(&f_t3a));
2053
2054        let f_t4a = filter_resolved!(f_or!([
2055            f_eq(Attribute::UserId, PartialValue::new_iutf8("alice")),
2056            f_eq(Attribute::GidNumber, PartialValue::Uint32(1001)),
2057        ]));
2058        assert!(!e.entry_match_no_index(&f_t4a));
2059    }
2060
2061    #[test]
2062    fn test_and_entry_filter() {
2063        let e = entry_init!(
2064            (Attribute::UserId, Value::new_iutf8("william")),
2065            (
2066                Attribute::Uuid,
2067                Value::Uuid(uuid::uuid!("db237e8a-0079-4b8c-8a56-593b22aa44d1"))
2068            ),
2069            (Attribute::GidNumber, Value::Uint32(1000))
2070        )
2071        .into_sealed_new();
2072
2073        let f_t1a = filter_resolved!(f_and!([
2074            f_eq(Attribute::UserId, PartialValue::new_iutf8("william")),
2075            f_eq(Attribute::GidNumber, PartialValue::Uint32(1000)),
2076        ]));
2077        assert!(e.entry_match_no_index(&f_t1a));
2078
2079        let f_t2a = filter_resolved!(f_and!([
2080            f_eq(Attribute::UserId, PartialValue::new_iutf8("william")),
2081            f_eq(Attribute::GidNumber, PartialValue::Uint32(1001)),
2082        ]));
2083        assert!(!e.entry_match_no_index(&f_t2a));
2084
2085        let f_t3a = filter_resolved!(f_and!([
2086            f_eq(Attribute::UserId, PartialValue::new_iutf8("alice")),
2087            f_eq(Attribute::GidNumber, PartialValue::Uint32(1000)),
2088        ]));
2089        assert!(!e.entry_match_no_index(&f_t3a));
2090
2091        let f_t4a = filter_resolved!(f_and!([
2092            f_eq(Attribute::UserId, PartialValue::new_iutf8("alice")),
2093            f_eq(Attribute::GidNumber, PartialValue::Uint32(1001)),
2094        ]));
2095        assert!(!e.entry_match_no_index(&f_t4a));
2096    }
2097
2098    #[test]
2099    fn test_not_entry_filter() {
2100        let e1 = entry_init!(
2101            (Attribute::UserId, Value::new_iutf8("william")),
2102            (
2103                Attribute::Uuid,
2104                Value::Uuid(uuid::uuid!("db237e8a-0079-4b8c-8a56-593b22aa44d1"))
2105            ),
2106            (Attribute::GidNumber, Value::Uint32(1000))
2107        )
2108        .into_sealed_new();
2109
2110        let f_t1a = filter_resolved!(f_andnot(f_eq(
2111            Attribute::UserId,
2112            PartialValue::new_iutf8("alice")
2113        )));
2114        assert!(e1.entry_match_no_index(&f_t1a));
2115
2116        let f_t2a = filter_resolved!(f_andnot(f_eq(
2117            Attribute::UserId,
2118            PartialValue::new_iutf8("william")
2119        )));
2120        assert!(!e1.entry_match_no_index(&f_t2a));
2121    }
2122
2123    #[test]
2124    fn test_nested_entry_filter() {
2125        let e1 = entry_init!(
2126            (Attribute::Class, EntryClass::Person.to_value().clone()),
2127            (
2128                Attribute::Uuid,
2129                Value::Uuid(uuid::uuid!("db237e8a-0079-4b8c-8a56-593b22aa44d1"))
2130            ),
2131            (Attribute::GidNumber, Value::Uint32(1000))
2132        )
2133        .into_sealed_new();
2134
2135        let e2 = entry_init!(
2136            (Attribute::Class, EntryClass::Person.to_value().clone()),
2137            (
2138                Attribute::Uuid,
2139                Value::Uuid(uuid::uuid!("4b6228ab-1dbe-42a4-a9f5-f6368222438e"))
2140            ),
2141            (Attribute::GidNumber, Value::Uint32(1001))
2142        )
2143        .into_sealed_new();
2144
2145        let e3 = entry_init!(
2146            (Attribute::Class, EntryClass::Person.to_value()),
2147            (
2148                Attribute::Uuid,
2149                Value::Uuid(uuid::uuid!("7b23c99d-c06b-4a9a-a958-3afa56383e1d"))
2150            ),
2151            (Attribute::GidNumber, Value::Uint32(1002))
2152        )
2153        .into_sealed_new();
2154
2155        let e4 = entry_init!(
2156            (Attribute::Class, EntryClass::Group.to_value()),
2157            (
2158                Attribute::Uuid,
2159                Value::Uuid(uuid::uuid!("21d816b5-1f6a-4696-b7c1-6ed06d22ed81"))
2160            ),
2161            (Attribute::GidNumber, Value::Uint32(1000))
2162        )
2163        .into_sealed_new();
2164
2165        let f_t1a = filter_resolved!(f_and!([
2166            f_eq(Attribute::Class, EntryClass::Person.into()),
2167            f_or!([
2168                f_eq(Attribute::GidNumber, PartialValue::Uint32(1001)),
2169                f_eq(Attribute::GidNumber, PartialValue::Uint32(1000))
2170            ])
2171        ]));
2172
2173        assert!(e1.entry_match_no_index(&f_t1a));
2174        assert!(e2.entry_match_no_index(&f_t1a));
2175        assert!(!e3.entry_match_no_index(&f_t1a));
2176        assert!(!e4.entry_match_no_index(&f_t1a));
2177    }
2178
2179    #[test]
2180    fn test_attr_set_filter() {
2181        let mut f_expect = BTreeSet::new();
2182        f_expect.insert(Attribute::from("userid"));
2183        f_expect.insert(Attribute::Class);
2184        // Given filters, get their expected attribute sets - this is used by access control profiles
2185        // to determine what attrs we are requesting regardless of the partialvalue.
2186        let f_t1a = filter_valid!(f_and!([
2187            f_eq(Attribute::UserId, PartialValue::new_iutf8("alice")),
2188            f_eq(Attribute::Class, PartialValue::new_iutf8("1001")),
2189        ]));
2190
2191        assert_eq!(f_t1a.get_attr_set(), f_expect);
2192
2193        let f_t2a = filter_valid!(f_and!([
2194            f_eq(Attribute::UserId, PartialValue::new_iutf8("alice")),
2195            f_eq(Attribute::Class, PartialValue::new_iutf8("1001")),
2196            f_eq(Attribute::UserId, PartialValue::new_iutf8("claire")),
2197        ]));
2198
2199        assert_eq!(f_t2a.get_attr_set(), f_expect);
2200    }
2201
2202    #[qs_test]
2203    async fn test_filter_resolve_value(server: &QueryServer) {
2204        let time_p1 = duration_from_epoch_now();
2205        let time_p2 = time_p1 + Duration::from_secs(CHANGELOG_MAX_AGE * 2);
2206        let time_p3 = time_p2 + Duration::from_secs(CHANGELOG_MAX_AGE * 2);
2207
2208        let mut server_txn = server.write(time_p1).await.expect("txn");
2209
2210        let e1 = entry_init!(
2211            (Attribute::Class, EntryClass::Object.to_value()),
2212            (Attribute::Class, EntryClass::Account.to_value()),
2213            (Attribute::Class, EntryClass::Person.to_value()),
2214            (Attribute::Name, Value::new_iname("testperson1")),
2215            (
2216                Attribute::Uuid,
2217                Value::Uuid(uuid::uuid!("cc8e95b4-c24f-4d68-ba54-8bed76f63930"))
2218            ),
2219            (Attribute::Description, Value::new_utf8s("testperson1")),
2220            (Attribute::DisplayName, Value::new_utf8s("testperson1"))
2221        );
2222
2223        let e2 = entry_init!(
2224            (Attribute::Class, EntryClass::Object.to_value()),
2225            (Attribute::Class, EntryClass::Account.to_value()),
2226            (Attribute::Class, EntryClass::Person.to_value()),
2227            (Attribute::Name, Value::new_iname("testperson2")),
2228            (
2229                Attribute::Uuid,
2230                Value::Uuid(uuid::uuid!("a67c0c71-0b35-4218-a6b0-22d23d131d27"))
2231            ),
2232            (Attribute::Description, Value::new_utf8s("testperson2")),
2233            (Attribute::DisplayName, Value::new_utf8s("testperson2"))
2234        );
2235
2236        // We need to add these and then push through the state machine.
2237        let e_ts = entry_init!(
2238            (Attribute::Class, EntryClass::Object.to_value()),
2239            (Attribute::Class, EntryClass::Account.to_value()),
2240            (Attribute::Class, EntryClass::Person.to_value()),
2241            (Attribute::Name, Value::new_iname("testperson3")),
2242            (
2243                Attribute::Uuid,
2244                Value::Uuid(uuid!("9557f49c-97a5-4277-a9a5-097d17eb8317"))
2245            ),
2246            (Attribute::Description, Value::new_utf8s("testperson3")),
2247            (Attribute::DisplayName, Value::new_utf8s("testperson3"))
2248        );
2249
2250        let ce = CreateEvent::new_internal(vec![e1, e2, e_ts]);
2251        let cr = server_txn.create(&ce);
2252        assert!(cr.is_ok());
2253
2254        let de_sin = DeleteEvent::new_internal_invalid(filter!(f_or!([f_eq(
2255            Attribute::Name,
2256            PartialValue::new_iname("testperson3")
2257        )])));
2258        assert!(server_txn.delete(&de_sin).is_ok());
2259
2260        // Commit
2261        assert!(server_txn.commit().is_ok());
2262
2263        // Now, establish enough time for the recycled items to be purged.
2264        let mut server_txn = server.write(time_p2).await.expect("txn");
2265        assert!(server_txn.purge_recycled().is_ok());
2266        assert!(server_txn.commit().is_ok());
2267
2268        let mut server_txn = server.write(time_p3).await.expect("txn");
2269        assert!(server_txn.purge_tombstones().is_ok());
2270
2271        // ===== ✅ now ready to test!
2272
2273        // Resolving most times should yield expected results
2274        let t1 = vs_utf8!["teststring".to_string()] as _;
2275        let r1 = server_txn.resolve_valueset(&t1);
2276        assert_eq!(r1, Ok(vec!["teststring".to_string()]));
2277
2278        // Resolve UUID with matching spn
2279        let t_uuid = vs_refer![uuid!("cc8e95b4-c24f-4d68-ba54-8bed76f63930")] as _;
2280        let r_uuid = server_txn.resolve_valueset(&t_uuid);
2281        debug!("{:?}", r_uuid);
2282        assert_eq!(r_uuid, Ok(vec!["testperson1@example.com".to_string()]));
2283
2284        // Resolve UUID with matching name
2285        let t_uuid = vs_refer![uuid!("a67c0c71-0b35-4218-a6b0-22d23d131d27")] as _;
2286        let r_uuid = server_txn.resolve_valueset(&t_uuid);
2287        debug!("{:?}", r_uuid);
2288        assert_eq!(r_uuid, Ok(vec!["testperson2@example.com".to_string()]));
2289
2290        // Resolve UUID non-exist
2291        let t_uuid_non = vs_refer![uuid!("b83e98f0-3d2e-41d2-9796-d8d993289c86")] as _;
2292        let r_uuid_non = server_txn.resolve_valueset(&t_uuid_non);
2293        debug!("{:?}", r_uuid_non);
2294        assert_eq!(
2295            r_uuid_non,
2296            Ok(vec!["b83e98f0-3d2e-41d2-9796-d8d993289c86".to_string()])
2297        );
2298
2299        // Resolve UUID to tombstone/recycled (same an non-exst)
2300        let t_uuid_ts = vs_refer![uuid!("9557f49c-97a5-4277-a9a5-097d17eb8317")] as _;
2301        let r_uuid_ts = server_txn.resolve_valueset(&t_uuid_ts);
2302        debug!("{:?}", r_uuid_ts);
2303        assert_eq!(
2304            r_uuid_ts,
2305            Ok(vec!["9557f49c-97a5-4277-a9a5-097d17eb8317".to_string()])
2306        );
2307    }
2308
2309    #[qs_test]
2310    async fn test_filter_depth_limits(server: &QueryServer) {
2311        let mut r_txn = server.read().await.unwrap();
2312
2313        let mut inv_proto = ProtoFilter::Pres(Attribute::Class.to_string());
2314        for _i in 0..(DEFAULT_LIMIT_FILTER_DEPTH_MAX + 1) {
2315            inv_proto = ProtoFilter::And(vec![inv_proto]);
2316        }
2317
2318        let mut inv_ldap = LdapFilter::Present(Attribute::Class.to_string());
2319        for _i in 0..(DEFAULT_LIMIT_FILTER_DEPTH_MAX + 1) {
2320            inv_ldap = LdapFilter::And(vec![inv_ldap]);
2321        }
2322
2323        let ev = Identity::from_internal();
2324
2325        // Test proto + read
2326        let res = Filter::from_ro(&ev, &inv_proto, &mut r_txn);
2327        assert_eq!(res, Err(OperationError::ResourceLimit));
2328
2329        // ldap
2330        let res = Filter::from_ldap_ro(&ev, &inv_ldap, &mut r_txn);
2331        assert_eq!(res, Err(OperationError::ResourceLimit));
2332
2333        // Can only have one db conn at a time.
2334        std::mem::drop(r_txn);
2335
2336        // proto + write
2337        let mut wr_txn = server.write(duration_from_epoch_now()).await.expect("txn");
2338        let res = Filter::from_rw(&ev, &inv_proto, &mut wr_txn);
2339        assert_eq!(res, Err(OperationError::ResourceLimit));
2340    }
2341
2342    #[qs_test]
2343    async fn test_filter_max_element_limits(server: &QueryServer) {
2344        const LIMIT: usize = 4;
2345        let mut r_txn = server.read().await.unwrap();
2346
2347        let inv_proto = ProtoFilter::And(
2348            (0..(LIMIT * 2))
2349                .map(|_| ProtoFilter::Pres(Attribute::Class.to_string()))
2350                .collect(),
2351        );
2352
2353        let inv_ldap = LdapFilter::And(
2354            (0..(LIMIT * 2))
2355                .map(|_| LdapFilter::Present(Attribute::Class.to_string()))
2356                .collect(),
2357        );
2358
2359        let mut ev = Identity::from_internal();
2360        ev.limits_mut().filter_max_elements = LIMIT;
2361
2362        // Test proto + read
2363        let res = Filter::from_ro(&ev, &inv_proto, &mut r_txn);
2364        assert_eq!(res, Err(OperationError::ResourceLimit));
2365
2366        // ldap
2367        let res = Filter::from_ldap_ro(&ev, &inv_ldap, &mut r_txn);
2368        assert_eq!(res, Err(OperationError::ResourceLimit));
2369
2370        // Can only have one db conn at a time.
2371        std::mem::drop(r_txn);
2372
2373        // proto + write
2374        let mut wr_txn = server.write(duration_from_epoch_now()).await.expect("txn");
2375        let res = Filter::from_rw(&ev, &inv_proto, &mut wr_txn);
2376        assert_eq!(res, Err(OperationError::ResourceLimit));
2377    }
2378}