qubit_metadata/filter/
filter_expression.rs

1// =============================================================================
2//    Copyright (c) 2025 - 2026 Haixing Hu.
3//
4//    SPDX-License-Identifier: Apache-2.0
5//
6//    Licensed under the Apache License, Version 2.0.
7// =============================================================================
8//! Immutable filter expressions and their read-only views.
9
10use std::fmt;
11
12use crate::Condition;
13use crate::FilterExpressionBuilder;
14use crate::FilterExpressionView;
15use crate::FilterLimitKind;
16use crate::FilterLimits;
17use crate::FilterMatchOptions;
18use crate::Metadata;
19use crate::MetadataError;
20use crate::MetadataResult;
21use crate::filter::internal::FilterExpressionNode;
22use crate::filter::internal::MatchOutcome;
23
24/// An immutable Boolean expression in a [`crate::MetadataFilter`].
25///
26/// Expressions are constructed by [`FilterExpressionBuilder`] and can be
27/// inspected without allocation through [`FilterExpression::view`]. Their
28/// private representation prevents callers from constructing structurally
29/// invalid expression trees. The structure is Boolean, while evaluation uses
30/// a private three-valued outcome so missing data stays unknown through NOT,
31/// AND, and OR.
32///
33/// # Examples
34///
35/// ```
36/// use qubit_metadata::FilterExpression;
37///
38/// # fn main() -> qubit_metadata::MetadataResult<()> {
39/// let expression = FilterExpression::builder()
40///     .eq("tenant", "acme")
41///     .build()?;
42/// assert!(matches!(
43///     expression.view(),
44///     qubit_metadata::FilterExpressionView::Condition(_)
45/// ));
46/// # Ok(())
47/// # }
48/// ```
49#[derive(Clone, PartialEq)]
50#[must_use]
51pub struct FilterExpression {
52    /// Private expression node.
53    node: FilterExpressionNode,
54    /// Total number of nodes after logical-group flattening.
55    node_count: usize,
56    /// Maximum node depth after logical-group flattening.
57    max_depth: usize,
58}
59
60impl fmt::Debug for FilterExpression {
61    /// Formats the expression without exposing its cached implementation
62    /// metrics.
63    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
64        formatter
65            .debug_struct("FilterExpression")
66            .field("node", &self.node)
67            .finish()
68    }
69}
70
71impl FilterExpression {
72    /// Creates a builder for a non-empty filter expression.
73    #[inline(always)]
74    #[must_use]
75    pub const fn builder() -> FilterExpressionBuilder {
76        FilterExpressionBuilder::new()
77    }
78
79    /// Creates an expression that matches every metadata object.
80    #[inline(always)]
81    #[must_use = "the constructed all-matching expression should be used"]
82    pub const fn match_all() -> Self {
83        Self::true_expression()
84    }
85
86    /// Creates an expression that matches no metadata object.
87    #[inline(always)]
88    #[must_use = "the constructed no-match expression should be used"]
89    pub const fn match_none() -> Self {
90        Self::false_expression()
91    }
92
93    /// Combines this expression with `other` using logical AND.
94    ///
95    /// # Errors
96    ///
97    /// Returns [`MetadataError::FilterLimitExceeded`] when the resulting
98    /// expression exceeds library hard limits.
99    #[inline]
100    pub fn try_and(self, other: Self) -> MetadataResult<Self> {
101        let expression = Self::and_unchecked(self, other);
102        expression.validate_limits(FilterLimits::MAX)?;
103        Ok(expression)
104    }
105
106    /// Combines this expression with `other` using logical OR.
107    ///
108    /// # Errors
109    ///
110    /// Returns [`MetadataError::FilterLimitExceeded`] when the resulting
111    /// expression exceeds library hard limits.
112    #[inline]
113    pub fn try_or(self, other: Self) -> MetadataResult<Self> {
114        let expression = Self::or_unchecked(self, other);
115        expression.validate_limits(FilterLimits::MAX)?;
116        Ok(expression)
117    }
118
119    /// Negates this expression.
120    ///
121    /// # Errors
122    ///
123    /// Returns [`MetadataError::FilterLimitExceeded`] when the resulting
124    /// expression exceeds library hard limits.
125    #[inline]
126    pub fn try_not(self) -> MetadataResult<Self> {
127        let expression = self.negated_unchecked();
128        expression.validate_limits(FilterLimits::MAX)?;
129        Ok(expression)
130    }
131
132    /// Returns a borrowed view of this expression node.
133    ///
134    /// # Returns
135    ///
136    /// A zero-copy view preserving the node's Boolean structure.
137    #[inline(always)]
138    #[must_use = "the expression view should be inspected"]
139    pub fn view(&self) -> FilterExpressionView<'_> {
140        match &self.node {
141            FilterExpressionNode::Condition(condition) => FilterExpressionView::Condition(condition),
142            FilterExpressionNode::And(children) => FilterExpressionView::And(children),
143            FilterExpressionNode::Or(children) => FilterExpressionView::Or(children),
144            FilterExpressionNode::Not(inner) => FilterExpressionView::Not(inner),
145            FilterExpressionNode::True => FilterExpressionView::True,
146            FilterExpressionNode::False => FilterExpressionView::False,
147        }
148    }
149
150    /// Creates a condition expression.
151    ///
152    /// # Parameters
153    ///
154    /// * `condition` - Leaf condition to store.
155    ///
156    /// # Returns
157    ///
158    /// A new condition expression.
159    #[inline]
160    pub(crate) fn condition(condition: Condition) -> MetadataResult<Self> {
161        condition.validate_operands()?;
162        Ok(Self {
163            node: FilterExpressionNode::Condition(condition),
164            node_count: 1,
165            max_depth: 1,
166        })
167    }
168
169    /// Creates a constant true expression.
170    ///
171    /// # Returns
172    ///
173    /// A new constant true expression.
174    #[inline]
175    pub(crate) const fn true_expression() -> Self {
176        Self {
177            node: FilterExpressionNode::True,
178            node_count: 1,
179            max_depth: 1,
180        }
181    }
182
183    /// Creates a constant false expression.
184    ///
185    /// # Returns
186    ///
187    /// A new constant false expression.
188    #[inline]
189    pub(crate) const fn false_expression() -> Self {
190        Self {
191            node: FilterExpressionNode::False,
192            node_count: 1,
193            max_depth: 1,
194        }
195    }
196
197    /// Combines two expressions with logical AND.
198    ///
199    /// # Parameters
200    ///
201    /// * `left` - Left child expression.
202    /// * `right` - Right child expression.
203    ///
204    /// # Returns
205    ///
206    /// A simplified AND expression.
207    pub(crate) fn and_unchecked(left: Self, right: Self) -> Self {
208        if left.is_false() || right.is_false() {
209            return Self::false_expression();
210        }
211        if left.is_true() {
212            return right;
213        }
214        if right.is_true() {
215            return left;
216        }
217        Self::combine_and(left, right)
218    }
219
220    /// Combines two expressions with logical OR.
221    ///
222    /// # Parameters
223    ///
224    /// * `left` - Left child expression.
225    /// * `right` - Right child expression.
226    ///
227    /// # Returns
228    ///
229    /// A simplified OR expression.
230    pub(crate) fn or_unchecked(left: Self, right: Self) -> Self {
231        if left.is_true() || right.is_true() {
232            return Self::true_expression();
233        }
234        if left.is_false() {
235            return right;
236        }
237        if right.is_false() {
238            return left;
239        }
240        Self::combine_or(left, right)
241    }
242
243    /// Creates a NOT expression without simplifying its child.
244    ///
245    /// # Parameters
246    ///
247    /// * `expression` - Child expression to negate.
248    ///
249    /// # Returns
250    ///
251    /// A NOT expression containing the supplied child.
252    #[inline]
253    pub(crate) fn not_expression(expression: Self) -> Self {
254        let node_count = expression.node_count + 1;
255        let max_depth = expression.max_depth + 1;
256        Self {
257            node: FilterExpressionNode::Not(Box::new(expression)),
258            node_count,
259            max_depth,
260        }
261    }
262
263    /// Returns the three-valued logical negation of this expression.
264    ///
265    /// # Returns
266    ///
267    /// A simplified negated expression.
268    pub(crate) fn negated_unchecked(self) -> Self {
269        match self {
270            Self {
271                node: FilterExpressionNode::True,
272                ..
273            } => Self::false_expression(),
274            Self {
275                node: FilterExpressionNode::False,
276                ..
277            } => Self::true_expression(),
278            Self {
279                node: FilterExpressionNode::Not(inner),
280                ..
281            } => *inner,
282            expression => Self::not_expression(expression),
283        }
284    }
285
286    /// Reports whether this is a constant true expression.
287    ///
288    /// # Returns
289    ///
290    /// `true` only for the constant true node.
291    #[inline]
292    pub(crate) const fn is_true(&self) -> bool {
293        matches!(&self.node, FilterExpressionNode::True)
294    }
295
296    /// Reports whether this is a constant false expression.
297    ///
298    /// # Returns
299    ///
300    /// `true` only for the constant false node.
301    #[inline]
302    pub(crate) const fn is_false(&self) -> bool {
303        matches!(&self.node, FilterExpressionNode::False)
304    }
305
306    /// Evaluates this expression against one metadata object.
307    ///
308    /// # Parameters
309    ///
310    /// * `metadata` - Metadata object being matched.
311    /// * `options` - Match options to apply.
312    ///
313    /// # Returns
314    ///
315    /// The three-valued expression outcome.
316    pub(crate) fn evaluate(&self, metadata: &Metadata, options: FilterMatchOptions) -> MatchOutcome {
317        match &self.node {
318            FilterExpressionNode::Condition(condition) => {
319                condition.evaluate(metadata, options.numeric_comparison_policy())
320            }
321            FilterExpressionNode::And(children) => {
322                MatchOutcome::and(children.iter().map(|child| child.evaluate(metadata, options)))
323            }
324            FilterExpressionNode::Or(children) => {
325                MatchOutcome::or(children.iter().map(|child| child.evaluate(metadata, options)))
326            }
327            FilterExpressionNode::Not(inner) => inner.evaluate(metadata, options).not(),
328            FilterExpressionNode::True => MatchOutcome::True,
329            FilterExpressionNode::False => MatchOutcome::False,
330        }
331    }
332
333    /// Visits every leaf condition in this expression.
334    ///
335    /// # Parameters
336    ///
337    /// * `visitor` - Callback invoked for each condition.
338    ///
339    /// # Returns
340    ///
341    /// `Ok(())` after all conditions have been visited.
342    ///
343    /// # Errors
344    ///
345    /// Returns the first error produced by `visitor`.
346    #[cfg(feature = "schema")]
347    pub(crate) fn visit_conditions<F>(&self, visitor: &mut F) -> MetadataResult<()>
348    where
349        F: FnMut(&Condition) -> MetadataResult<()>,
350    {
351        match &self.node {
352            FilterExpressionNode::Condition(condition) => visitor(condition),
353            FilterExpressionNode::And(children) | FilterExpressionNode::Or(children) => {
354                for child in children {
355                    child.visit_conditions(visitor)?;
356                }
357                Ok(())
358            }
359            FilterExpressionNode::Not(inner) => inner.visit_conditions(visitor),
360            FilterExpressionNode::True | FilterExpressionNode::False => Ok(()),
361        }
362    }
363
364    /// Validates this expression against resource limits.
365    ///
366    /// # Parameters
367    ///
368    /// * `limits` - Bounds to enforce.
369    ///
370    /// # Returns
371    ///
372    /// `Ok(())` when every node and condition fits within `limits`.
373    ///
374    /// # Errors
375    ///
376    /// Returns [`MetadataError::FilterLimitExceeded`] when depth, node count,
377    /// key length, or membership values exceed a configured bound.
378    pub(crate) fn validate_limits(&self, limits: FilterLimits) -> MetadataResult<()> {
379        let mut node_count = 0;
380        self.validate_limits_at(limits, 1, &mut node_count)
381    }
382
383    /// Validates cached structural metrics against resource limits in O(1).
384    ///
385    /// # Parameters
386    ///
387    /// * `limits` - Structural bounds to enforce.
388    ///
389    /// # Errors
390    ///
391    /// Returns [`MetadataError::FilterLimitExceeded`] when the cached maximum
392    /// depth or total node count exceeds `limits`. The reported value is the
393    /// first value beyond the configured maximum, matching recursive
394    /// validation semantics.
395    pub(crate) fn validate_structure_limits(&self, limits: FilterLimits) -> MetadataResult<()> {
396        if self.max_depth > limits.max_depth() {
397            return Err(MetadataError::FilterLimitExceeded {
398                kind: FilterLimitKind::Depth,
399                value: limits.max_depth() + 1,
400                maximum: limits.max_depth(),
401            });
402        }
403        if self.node_count > limits.max_nodes() {
404            return Err(MetadataError::FilterLimitExceeded {
405                kind: FilterLimitKind::Nodes,
406                value: limits.max_nodes() + 1,
407                maximum: limits.max_nodes(),
408            });
409        }
410        Ok(())
411    }
412
413    /// Recursively validates one expression node in depth-first order.
414    ///
415    /// # Parameters
416    ///
417    /// * `limits` - Bounds to enforce.
418    /// * `depth` - Root-inclusive depth of this node.
419    /// * `node_count` - Number of nodes visited before this node.
420    ///
421    /// # Errors
422    ///
423    /// Returns the first depth, node-count, or condition-limit error reached
424    /// by the depth-first traversal.
425    fn validate_limits_at(&self, limits: FilterLimits, depth: usize, node_count: &mut usize) -> MetadataResult<()> {
426        if depth > limits.max_depth() {
427            return Err(MetadataError::FilterLimitExceeded {
428                kind: FilterLimitKind::Depth,
429                value: depth,
430                maximum: limits.max_depth(),
431            });
432        }
433        *node_count += 1;
434        if *node_count > limits.max_nodes() {
435            return Err(MetadataError::FilterLimitExceeded {
436                kind: FilterLimitKind::Nodes,
437                value: *node_count,
438                maximum: limits.max_nodes(),
439            });
440        }
441        match &self.node {
442            FilterExpressionNode::Condition(condition) => condition.validate_limits(limits),
443            FilterExpressionNode::And(children) | FilterExpressionNode::Or(children) => {
444                for child in children {
445                    child.validate_limits_at(limits, depth + 1, node_count)?;
446                }
447                Ok(())
448            }
449            FilterExpressionNode::Not(inner) => inner.validate_limits_at(limits, depth + 1, node_count),
450            FilterExpressionNode::True | FilterExpressionNode::False => Ok(()),
451        }
452    }
453
454    /// Asserts that cached structural metrics equal recursively computed
455    /// metrics.
456    #[cfg(test)]
457    fn assert_cached_metrics_consistent(&self) {
458        match &self.node {
459            FilterExpressionNode::And(children) | FilterExpressionNode::Or(children) => {
460                for child in children {
461                    child.assert_cached_metrics_consistent();
462                }
463            }
464            FilterExpressionNode::Not(inner) => inner.assert_cached_metrics_consistent(),
465            FilterExpressionNode::Condition(_) | FilterExpressionNode::True | FilterExpressionNode::False => {}
466        }
467        let (node_count, max_depth) = self.recursive_metrics();
468        assert_eq!(
469            self.node_count, node_count,
470            "cached node count differs from the expression tree"
471        );
472        assert_eq!(
473            self.max_depth, max_depth,
474            "cached maximum depth differs from the expression tree"
475        );
476    }
477
478    /// Recursively computes the node count and maximum depth for tests.
479    #[cfg(test)]
480    fn recursive_metrics(&self) -> (usize, usize) {
481        match &self.node {
482            FilterExpressionNode::Condition(_) | FilterExpressionNode::True | FilterExpressionNode::False => (1, 1),
483            FilterExpressionNode::And(children) | FilterExpressionNode::Or(children) => {
484                let mut node_count = 1;
485                let mut max_child_depth = 0;
486                for child in children {
487                    let (child_node_count, child_max_depth) = child.recursive_metrics();
488                    node_count += child_node_count;
489                    max_child_depth = max_child_depth.max(child_max_depth);
490                }
491                (node_count, max_child_depth + 1)
492            }
493            FilterExpressionNode::Not(inner) => {
494                let (node_count, max_depth) = inner.recursive_metrics();
495                (node_count + 1, max_depth + 1)
496            }
497        }
498    }
499
500    /// Combines two non-constant expressions with logical AND while reusing a
501    /// left AND group.
502    fn combine_and(left: Self, right: Self) -> Self {
503        let left_same_kind = matches!(&left.node, FilterExpressionNode::And(_));
504        let right_same_kind = matches!(&right.node, FilterExpressionNode::And(_));
505        let (node_count, max_depth) = Self::combined_metrics(&left, &right, left_same_kind, right_same_kind);
506        let mut children = match left {
507            Self {
508                node: FilterExpressionNode::And(children),
509                ..
510            } => children,
511            expression => vec![expression],
512        };
513        match right {
514            Self {
515                node: FilterExpressionNode::And(mut nested),
516                ..
517            } => children.append(&mut nested),
518            expression => children.push(expression),
519        }
520        Self {
521            node: FilterExpressionNode::And(children),
522            node_count,
523            max_depth,
524        }
525    }
526
527    /// Combines two non-constant expressions with logical OR while reusing a
528    /// left OR group.
529    fn combine_or(left: Self, right: Self) -> Self {
530        let left_same_kind = matches!(&left.node, FilterExpressionNode::Or(_));
531        let right_same_kind = matches!(&right.node, FilterExpressionNode::Or(_));
532        let (node_count, max_depth) = Self::combined_metrics(&left, &right, left_same_kind, right_same_kind);
533        let mut children = match left {
534            Self {
535                node: FilterExpressionNode::Or(children),
536                ..
537            } => children,
538            expression => vec![expression],
539        };
540        match right {
541            Self {
542                node: FilterExpressionNode::Or(mut nested),
543                ..
544            } => children.append(&mut nested),
545            expression => children.push(expression),
546        }
547        Self {
548            node: FilterExpressionNode::Or(children),
549            node_count,
550            max_depth,
551        }
552    }
553
554    /// Calculates metrics for two expressions combined under one logical
555    /// operator, accounting for same-kind root flattening.
556    ///
557    /// # Parameters
558    ///
559    /// * `left` - Left expression before flattening.
560    /// * `right` - Right expression before flattening.
561    /// * `left_same_kind` - Whether the left root is flattened into the result.
562    /// * `right_same_kind` - Whether the right root is flattened into the
563    ///   result.
564    ///
565    /// # Returns
566    ///
567    /// The result's total node count and maximum depth.
568    fn combined_metrics(left: &Self, right: &Self, left_same_kind: bool, right_same_kind: bool) -> (usize, usize) {
569        let node_count = match (left_same_kind, right_same_kind) {
570            (true, true) => left.node_count + right.node_count - 1,
571            (true, false) | (false, true) => left.node_count + right.node_count,
572            (false, false) => left.node_count + right.node_count + 1,
573        };
574        let max_depth = match (left_same_kind, right_same_kind) {
575            (true, true) => left.max_depth.max(right.max_depth),
576            (true, false) => left.max_depth.max(right.max_depth + 1),
577            (false, true) => (left.max_depth + 1).max(right.max_depth),
578            (false, false) => left.max_depth.max(right.max_depth) + 1,
579        };
580        (node_count, max_depth)
581    }
582}
583
584#[cfg(test)]
585mod tests {
586    use super::FilterExpression;
587
588    /// Verifies that cached metrics agree with a recursive traversal for
589    /// representative simplified and nested expression shapes.
590    #[test]
591    fn test_cached_metrics_match_recursive_metrics() {
592        let leaf = FilterExpression::builder()
593            .exists("leaf")
594            .build()
595            .expect("leaf expression should build");
596        leaf.assert_cached_metrics_consistent();
597
598        let left = FilterExpression::builder()
599            .exists("left_1")
600            .exists("left_2")
601            .build()
602            .expect("left expression should build");
603        let right = FilterExpression::builder()
604            .exists("right_1")
605            .exists("right_2")
606            .build()
607            .expect("right expression should build");
608        let flattened = left.try_and(right).expect("flattened AND should build");
609        flattened.assert_cached_metrics_consistent();
610
611        let nested = flattened
612            .try_or(
613                FilterExpression::builder()
614                    .exists("alternative")
615                    .build()
616                    .expect("alternative expression should build"),
617            )
618            .expect("nested OR should build")
619            .try_not()
620            .expect("negated expression should build");
621        nested.assert_cached_metrics_consistent();
622
623        FilterExpression::match_all()
624            .try_and(nested.clone())
625            .expect("true AND expression should simplify")
626            .assert_cached_metrics_consistent();
627        FilterExpression::match_none()
628            .try_or(nested)
629            .expect("false OR expression should simplify")
630            .assert_cached_metrics_consistent();
631        FilterExpression::match_all()
632            .try_not()
633            .expect("constant negation should simplify")
634            .assert_cached_metrics_consistent();
635    }
636}
qubit_metadata/filter/filter_expression.rs

qubit_metadata/filter/
filter_expression.rs
