iceberg/expr/
predicate.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18//! This module contains predicate expressions.
19//! Predicate expressions are used to filter data, and evaluates to a boolean value. For example,
20//! `a > 10` is a predicate expression, and it evaluates to `true` if `a` is greater than `10`,
21
22use std::fmt::{Debug, Display, Formatter};
23use std::ops::Not;
24
25use array_init::array_init;
26use fnv::FnvHashSet;
27use itertools::Itertools;
28use serde::{Deserialize, Serialize};
29
30use crate::error::{Result, invalid_data};
31use crate::expr::visitors::bound_predicate_visitor::visit as visit_bound;
32use crate::expr::visitors::predicate_visitor::visit;
33use crate::expr::visitors::rewrite_not::RewriteNotVisitor;
34use crate::expr::{Bind, BoundReference, PredicateOperator, Reference};
35use crate::spec::{Datum, PrimitiveLiteral, SchemaRef};
36use crate::{Error, ErrorKind};
37
38/// Logical expression, such as `AND`, `OR`, `NOT`.
39#[derive(PartialEq, Clone)]
40pub struct LogicalExpression<T, const N: usize> {
41    inputs: [Box<T>; N],
42}
43
44impl<T: Serialize, const N: usize> Serialize for LogicalExpression<T, N> {
45    fn serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error>
46    where S: serde::Serializer {
47        self.inputs.serialize(serializer)
48    }
49}
50
51impl<'de, T: Deserialize<'de>, const N: usize> Deserialize<'de> for LogicalExpression<T, N> {
52    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
53    where D: serde::Deserializer<'de> {
54        let inputs = Vec::<Box<T>>::deserialize(deserializer)?;
55        Ok(LogicalExpression::new(
56            array_init::from_iter(inputs).ok_or_else(|| {
57                serde::de::Error::custom(format!("Failed to deserialize LogicalExpression: the len of inputs is not match with the len of LogicalExpression {N}"))
58            })?,
59        ))
60    }
61}
62
63impl<T: Debug, const N: usize> Debug for LogicalExpression<T, N> {
64    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
65        f.debug_struct("LogicalExpression")
66            .field("inputs", &self.inputs)
67            .finish()
68    }
69}
70
71impl<T, const N: usize> LogicalExpression<T, N> {
72    fn new(inputs: [Box<T>; N]) -> Self {
73        Self { inputs }
74    }
75
76    /// Return inputs of this logical expression.
77    pub fn inputs(&self) -> [&T; N] {
78        let mut ret: [&T; N] = [self.inputs[0].as_ref(); N];
79        for (i, item) in ret.iter_mut().enumerate() {
80            *item = &self.inputs[i];
81        }
82        ret
83    }
84}
85
86impl<T: Bind, const N: usize> Bind for LogicalExpression<T, N>
87where T::Bound: Sized
88{
89    type Bound = LogicalExpression<T::Bound, N>;
90
91    fn bind(&self, schema: SchemaRef, case_sensitive: bool) -> Result<Self::Bound> {
92        let mut outputs: [Option<Box<T::Bound>>; N] = array_init(|_| None);
93        for (i, input) in self.inputs.iter().enumerate() {
94            outputs[i] = Some(Box::new(input.bind(schema.clone(), case_sensitive)?));
95        }
96
97        // It's safe to use `unwrap` here since they are all `Some`.
98        let bound_inputs = array_init::from_iter(outputs.into_iter().map(Option::unwrap)).unwrap();
99        Ok(LogicalExpression::new(bound_inputs))
100    }
101}
102
103/// Unary predicate, for example, `a IS NULL`.
104#[derive(PartialEq, Clone, Serialize, Deserialize)]
105pub struct UnaryExpression<T> {
106    /// Operator of this predicate, must be single operand operator.
107    op: PredicateOperator,
108    /// Term of this predicate, for example, `a` in `a IS NULL`.
109    #[serde(bound(serialize = "T: Serialize", deserialize = "T: Deserialize<'de>"))]
110    term: T,
111}
112
113impl<T: Debug> Debug for UnaryExpression<T> {
114    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
115        f.debug_struct("UnaryExpression")
116            .field("op", &self.op)
117            .field("term", &self.term)
118            .finish()
119    }
120}
121
122impl<T: Display> Display for UnaryExpression<T> {
123    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
124        write!(f, "{} {}", self.term, self.op)
125    }
126}
127
128impl<T: Bind> Bind for UnaryExpression<T> {
129    type Bound = UnaryExpression<T::Bound>;
130
131    fn bind(&self, schema: SchemaRef, case_sensitive: bool) -> Result<Self::Bound> {
132        let bound_term = self.term.bind(schema, case_sensitive)?;
133        Ok(UnaryExpression::new(self.op, bound_term))
134    }
135}
136
137impl<T> UnaryExpression<T> {
138    /// Creates a unary expression with the given operator and term.
139    ///
140    /// # Example
141    ///
142    /// ```rust
143    /// use iceberg::expr::{PredicateOperator, Reference, UnaryExpression};
144    ///
145    /// UnaryExpression::new(PredicateOperator::IsNull, Reference::new("c"));
146    /// ```
147    pub fn new(op: PredicateOperator, term: T) -> Self {
148        debug_assert!(op.is_unary());
149        Self { op, term }
150    }
151
152    /// Return the operator of this predicate.
153    pub fn op(&self) -> PredicateOperator {
154        self.op
155    }
156
157    /// Return the term of this predicate.
158    pub fn term(&self) -> &T {
159        &self.term
160    }
161}
162
163/// Binary predicate, for example, `a > 10`.
164#[derive(PartialEq, Clone, Serialize, Deserialize)]
165pub struct BinaryExpression<T> {
166    /// Operator of this predicate, must be binary operator, such as `=`, `>`, `<`, etc.
167    op: PredicateOperator,
168    /// Term of this predicate, for example, `a` in `a > 10`.
169    #[serde(bound(serialize = "T: Serialize", deserialize = "T: Deserialize<'de>"))]
170    term: T,
171    /// Literal of this predicate, for example, `10` in `a > 10`.
172    literal: Datum,
173}
174
175impl<T: Debug> Debug for BinaryExpression<T> {
176    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
177        f.debug_struct("BinaryExpression")
178            .field("op", &self.op)
179            .field("term", &self.term)
180            .field("literal", &self.literal)
181            .finish()
182    }
183}
184
185impl<T> BinaryExpression<T> {
186    /// Creates a binary expression with the given operator, term and literal.
187    ///
188    /// # Example
189    ///
190    /// ```rust
191    /// use iceberg::expr::{BinaryExpression, PredicateOperator, Reference};
192    /// use iceberg::spec::Datum;
193    ///
194    /// BinaryExpression::new(
195    ///     PredicateOperator::LessThanOrEq,
196    ///     Reference::new("a"),
197    ///     Datum::int(10),
198    /// );
199    /// ```
200    pub fn new(op: PredicateOperator, term: T, literal: Datum) -> Self {
201        debug_assert!(op.is_binary());
202        Self { op, term, literal }
203    }
204
205    /// Return the operator used by this predicate expression.
206    pub fn op(&self) -> PredicateOperator {
207        self.op
208    }
209
210    /// Return the literal of this predicate.
211    pub fn literal(&self) -> &Datum {
212        &self.literal
213    }
214
215    /// Return the term of this predicate.
216    pub fn term(&self) -> &T {
217        &self.term
218    }
219}
220
221impl<T: Display> Display for BinaryExpression<T> {
222    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
223        write!(f, "{} {} {}", self.term, self.op, self.literal)
224    }
225}
226
227impl<T: Bind> Bind for BinaryExpression<T> {
228    type Bound = BinaryExpression<T::Bound>;
229
230    fn bind(&self, schema: SchemaRef, case_sensitive: bool) -> Result<Self::Bound> {
231        let bound_term = self.term.bind(schema.clone(), case_sensitive)?;
232        Ok(BinaryExpression::new(
233            self.op,
234            bound_term,
235            self.literal.clone(),
236        ))
237    }
238}
239
240/// Set predicates, for example, `a in (1, 2, 3)`.
241#[derive(PartialEq, Clone, Serialize, Deserialize)]
242pub struct SetExpression<T> {
243    /// Operator of this predicate, must be set operator, such as `IN`, `NOT IN`, etc.
244    op: PredicateOperator,
245    /// Term of this predicate, for example, `a` in `a in (1, 2, 3)`.
246    term: T,
247    /// Literals of this predicate, for example, `(1, 2, 3)` in `a in (1, 2, 3)`.
248    literals: FnvHashSet<Datum>,
249}
250
251impl<T: Debug> Debug for SetExpression<T> {
252    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
253        f.debug_struct("SetExpression")
254            .field("op", &self.op)
255            .field("term", &self.term)
256            .field("literal", &self.literals)
257            .finish()
258    }
259}
260
261impl<T> SetExpression<T> {
262    /// Creates a set expression with the given operator, term and literal.
263    ///
264    /// # Example
265    ///
266    /// ```rust
267    /// use fnv::FnvHashSet;
268    /// use iceberg::expr::{PredicateOperator, Reference, SetExpression};
269    /// use iceberg::spec::Datum;
270    ///
271    /// SetExpression::new(
272    ///     PredicateOperator::In,
273    ///     Reference::new("a"),
274    ///     FnvHashSet::from_iter(vec![Datum::int(1)]),
275    /// );
276    /// ```
277    pub fn new(op: PredicateOperator, term: T, literals: FnvHashSet<Datum>) -> Self {
278        debug_assert!(op.is_set());
279        Self { op, term, literals }
280    }
281
282    /// Return the operator of this predicate.
283    pub fn op(&self) -> PredicateOperator {
284        self.op
285    }
286
287    /// Return the hash set of values compared against the term in this expression.
288    pub fn literals(&self) -> &FnvHashSet<Datum> {
289        &self.literals
290    }
291
292    /// Return the term of this predicate.
293    pub fn term(&self) -> &T {
294        &self.term
295    }
296}
297
298impl<T: Bind> Bind for SetExpression<T> {
299    type Bound = SetExpression<T::Bound>;
300
301    fn bind(&self, schema: SchemaRef, case_sensitive: bool) -> Result<Self::Bound> {
302        let bound_term = self.term.bind(schema.clone(), case_sensitive)?;
303        Ok(SetExpression::new(
304            self.op,
305            bound_term,
306            self.literals.clone(),
307        ))
308    }
309}
310
311impl<T: Display + Debug> Display for SetExpression<T> {
312    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
313        let mut literal_strs = self.literals.iter().map(|l| format!("{l}"));
314
315        write!(f, "{} {} ({})", self.term, self.op, literal_strs.join(", "))
316    }
317}
318
319/// Unbound predicate expression before binding to a schema.
320#[derive(Debug, PartialEq, Serialize, Deserialize, Clone)]
321pub enum Predicate {
322    /// AlwaysTrue predicate, for example, `TRUE`.
323    AlwaysTrue,
324    /// AlwaysFalse predicate, for example, `FALSE`.
325    AlwaysFalse,
326    /// And predicate, for example, `a > 10 AND b < 20`.
327    And(LogicalExpression<Predicate, 2>),
328    /// Or predicate, for example, `a > 10 OR b < 20`.
329    Or(LogicalExpression<Predicate, 2>),
330    /// Not predicate, for example, `NOT (a > 10)`.
331    Not(LogicalExpression<Predicate, 1>),
332    /// Unary expression, for example, `a IS NULL`.
333    Unary(UnaryExpression<Reference>),
334    /// Binary expression, for example, `a > 10`.
335    Binary(BinaryExpression<Reference>),
336    /// Set predicates, for example, `a in (1, 2, 3)`.
337    Set(SetExpression<Reference>),
338}
339
340impl Bind for Predicate {
341    type Bound = BoundPredicate;
342
343    fn bind(&self, schema: SchemaRef, case_sensitive: bool) -> Result<BoundPredicate> {
344        match self {
345            Predicate::And(expr) => {
346                let bound_expr = expr.bind(schema, case_sensitive)?;
347
348                let [left, right] = bound_expr.inputs;
349                Ok(match (left, right) {
350                    (_, r) if matches!(&*r, &BoundPredicate::AlwaysFalse) => {
351                        BoundPredicate::AlwaysFalse
352                    }
353                    (l, _) if matches!(&*l, &BoundPredicate::AlwaysFalse) => {
354                        BoundPredicate::AlwaysFalse
355                    }
356                    (left, r) if matches!(&*r, &BoundPredicate::AlwaysTrue) => *left,
357                    (l, right) if matches!(&*l, &BoundPredicate::AlwaysTrue) => *right,
358                    (left, right) => BoundPredicate::And(LogicalExpression::new([left, right])),
359                })
360            }
361            Predicate::Not(expr) => {
362                let bound_expr = expr.bind(schema, case_sensitive)?;
363                let [inner] = bound_expr.inputs;
364                Ok(match inner {
365                    e if matches!(&*e, &BoundPredicate::AlwaysTrue) => BoundPredicate::AlwaysFalse,
366                    e if matches!(&*e, &BoundPredicate::AlwaysFalse) => BoundPredicate::AlwaysTrue,
367                    e => BoundPredicate::Not(LogicalExpression::new([e])),
368                })
369            }
370            Predicate::Or(expr) => {
371                let bound_expr = expr.bind(schema, case_sensitive)?;
372                let [left, right] = bound_expr.inputs;
373                Ok(match (left, right) {
374                    (l, r)
375                        if matches!(&*r, &BoundPredicate::AlwaysTrue)
376                            || matches!(&*l, &BoundPredicate::AlwaysTrue) =>
377                    {
378                        BoundPredicate::AlwaysTrue
379                    }
380                    (left, r) if matches!(&*r, &BoundPredicate::AlwaysFalse) => *left,
381                    (l, right) if matches!(&*l, &BoundPredicate::AlwaysFalse) => *right,
382                    (left, right) => BoundPredicate::Or(LogicalExpression::new([left, right])),
383                })
384            }
385            Predicate::Unary(expr) => {
386                let bound_expr = expr.bind(schema, case_sensitive)?;
387
388                match &bound_expr.op {
389                    &PredicateOperator::IsNull => {
390                        if bound_expr.term.field().required {
391                            return Ok(BoundPredicate::AlwaysFalse);
392                        }
393                    }
394                    &PredicateOperator::NotNull => {
395                        if bound_expr.term.field().required {
396                            return Ok(BoundPredicate::AlwaysTrue);
397                        }
398                    }
399                    &PredicateOperator::IsNan | &PredicateOperator::NotNan => {
400                        if !bound_expr.term.field().field_type.is_floating_type() {
401                            return Err(invalid_data!(
402                                "Expecting floating point type, but found {}",
403                                bound_expr.term.field().field_type
404                            ));
405                        }
406                    }
407                    op => {
408                        return Err(Error::new(
409                            ErrorKind::Unexpected,
410                            format!("Expecting unary operator, but found {op}"),
411                        ));
412                    }
413                }
414
415                Ok(BoundPredicate::Unary(bound_expr))
416            }
417            Predicate::Binary(expr) => {
418                let bound_expr = expr.bind(schema, case_sensitive)?;
419                let bound_literal = bound_expr.literal.to(&bound_expr.term.field().field_type)?;
420
421                match bound_literal.literal() {
422                    PrimitiveLiteral::AboveMax => match &bound_expr.op {
423                        &PredicateOperator::LessThan
424                        | &PredicateOperator::LessThanOrEq
425                        | &PredicateOperator::NotEq => {
426                            return Ok(BoundPredicate::AlwaysTrue);
427                        }
428                        &PredicateOperator::GreaterThan
429                        | &PredicateOperator::GreaterThanOrEq
430                        | &PredicateOperator::Eq => {
431                            return Ok(BoundPredicate::AlwaysFalse);
432                        }
433                        _ => {}
434                    },
435                    PrimitiveLiteral::BelowMin => match &bound_expr.op {
436                        &PredicateOperator::GreaterThan
437                        | &PredicateOperator::GreaterThanOrEq
438                        | &PredicateOperator::NotEq => {
439                            return Ok(BoundPredicate::AlwaysTrue);
440                        }
441                        &PredicateOperator::LessThan
442                        | &PredicateOperator::LessThanOrEq
443                        | &PredicateOperator::Eq => {
444                            return Ok(BoundPredicate::AlwaysFalse);
445                        }
446                        _ => {}
447                    },
448                    _ => {}
449                }
450
451                Ok(BoundPredicate::Binary(BinaryExpression::new(
452                    bound_expr.op,
453                    bound_expr.term,
454                    bound_literal,
455                )))
456            }
457            Predicate::Set(expr) => {
458                let bound_expr = expr.bind(schema, case_sensitive)?;
459                let bound_literals = bound_expr
460                    .literals
461                    .into_iter()
462                    .map(|l| l.to(&bound_expr.term.field().field_type))
463                    .collect::<Result<FnvHashSet<Datum>>>()?;
464
465                match &bound_expr.op {
466                    &PredicateOperator::In => {
467                        if bound_literals.is_empty() {
468                            return Ok(BoundPredicate::AlwaysFalse);
469                        }
470                        if bound_literals.len() == 1 {
471                            return Ok(BoundPredicate::Binary(BinaryExpression::new(
472                                PredicateOperator::Eq,
473                                bound_expr.term,
474                                bound_literals.into_iter().next().unwrap(),
475                            )));
476                        }
477                    }
478                    &PredicateOperator::NotIn => {
479                        if bound_literals.is_empty() {
480                            return Ok(BoundPredicate::AlwaysTrue);
481                        }
482                        if bound_literals.len() == 1 {
483                            return Ok(BoundPredicate::Binary(BinaryExpression::new(
484                                PredicateOperator::NotEq,
485                                bound_expr.term,
486                                bound_literals.into_iter().next().unwrap(),
487                            )));
488                        }
489                    }
490                    op => {
491                        return Err(Error::new(
492                            ErrorKind::Unexpected,
493                            format!("Expecting unary operator,but found {op}"),
494                        ));
495                    }
496                }
497
498                Ok(BoundPredicate::Set(SetExpression::new(
499                    bound_expr.op,
500                    bound_expr.term,
501                    bound_literals,
502                )))
503            }
504            Predicate::AlwaysTrue => Ok(BoundPredicate::AlwaysTrue),
505            Predicate::AlwaysFalse => Ok(BoundPredicate::AlwaysFalse),
506        }
507    }
508}
509
510impl Display for Predicate {
511    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
512        match self {
513            Predicate::AlwaysTrue => {
514                write!(f, "TRUE")
515            }
516            Predicate::AlwaysFalse => {
517                write!(f, "FALSE")
518            }
519            Predicate::And(expr) => {
520                write!(f, "({}) AND ({})", expr.inputs()[0], expr.inputs()[1])
521            }
522            Predicate::Or(expr) => {
523                write!(f, "({}) OR ({})", expr.inputs()[0], expr.inputs()[1])
524            }
525            Predicate::Not(expr) => {
526                write!(f, "NOT ({})", expr.inputs()[0])
527            }
528            Predicate::Unary(expr) => {
529                write!(f, "{expr}")
530            }
531            Predicate::Binary(expr) => {
532                write!(f, "{expr}")
533            }
534            Predicate::Set(expr) => {
535                write!(f, "{expr}")
536            }
537        }
538    }
539}
540
541impl Predicate {
542    /// Combines two predicates with `AND`.
543    ///
544    /// # Example
545    ///
546    /// ```rust
547    /// use std::ops::Bound::Unbounded;
548    ///
549    /// use iceberg::expr::BoundPredicate::Unary;
550    /// use iceberg::expr::Reference;
551    /// use iceberg::spec::Datum;
552    /// let expr1 = Reference::new("a").less_than(Datum::long(10));
553    ///
554    /// let expr2 = Reference::new("b").less_than(Datum::long(20));
555    ///
556    /// let expr = expr1.and(expr2);
557    ///
558    /// assert_eq!(&format!("{expr}"), "(a < 10) AND (b < 20)");
559    /// ```
560    pub fn and(self, other: Predicate) -> Predicate {
561        match (self, other) {
562            (Predicate::AlwaysFalse, _) => Predicate::AlwaysFalse,
563            (_, Predicate::AlwaysFalse) => Predicate::AlwaysFalse,
564            (Predicate::AlwaysTrue, rhs) => rhs,
565            (lhs, Predicate::AlwaysTrue) => lhs,
566            (lhs, rhs) => Predicate::And(LogicalExpression::new([Box::new(lhs), Box::new(rhs)])),
567        }
568    }
569
570    /// Combines two predicates with `OR`.
571    ///
572    /// # Example
573    ///
574    /// ```rust
575    /// use std::ops::Bound::Unbounded;
576    ///
577    /// use iceberg::expr::BoundPredicate::Unary;
578    /// use iceberg::expr::Reference;
579    /// use iceberg::spec::Datum;
580    /// let expr1 = Reference::new("a").less_than(Datum::long(10));
581    ///
582    /// let expr2 = Reference::new("b").less_than(Datum::long(20));
583    ///
584    /// let expr = expr1.or(expr2);
585    ///
586    /// assert_eq!(&format!("{expr}"), "(a < 10) OR (b < 20)");
587    /// ```
588    pub fn or(self, other: Predicate) -> Predicate {
589        match (self, other) {
590            (Predicate::AlwaysTrue, _) => Predicate::AlwaysTrue,
591            (_, Predicate::AlwaysTrue) => Predicate::AlwaysTrue,
592            (Predicate::AlwaysFalse, rhs) => rhs,
593            (lhs, Predicate::AlwaysFalse) => lhs,
594            (lhs, rhs) => Predicate::Or(LogicalExpression::new([Box::new(lhs), Box::new(rhs)])),
595        }
596    }
597
598    /// Returns a predicate representing the negation ('NOT') of this one,
599    /// by using inverse predicates rather than wrapping in a `NOT`.
600    /// Used for `NOT` elimination.
601    ///
602    /// # Example
603    ///
604    /// ```rust
605    /// use std::ops::Bound::Unbounded;
606    ///
607    /// use iceberg::expr::BoundPredicate::Unary;
608    /// use iceberg::expr::{LogicalExpression, Predicate, Reference};
609    /// use iceberg::spec::Datum;
610    /// let expr1 = Reference::new("a").less_than(Datum::long(10));
611    /// let expr2 = Reference::new("b")
612    ///     .less_than(Datum::long(5))
613    ///     .and(Reference::new("c").less_than(Datum::long(10)));
614    ///
615    /// let result = expr1.negate();
616    /// assert_eq!(&format!("{result}"), "a >= 10");
617    ///
618    /// let result = expr2.negate();
619    /// assert_eq!(&format!("{result}"), "(b >= 5) OR (c >= 10)");
620    /// ```
621    pub fn negate(self) -> Predicate {
622        match self {
623            Predicate::AlwaysTrue => Predicate::AlwaysFalse,
624            Predicate::AlwaysFalse => Predicate::AlwaysTrue,
625            Predicate::And(expr) => Predicate::Or(LogicalExpression::new(
626                expr.inputs.map(|expr| Box::new(expr.negate())),
627            )),
628            Predicate::Or(expr) => Predicate::And(LogicalExpression::new(
629                expr.inputs.map(|expr| Box::new(expr.negate())),
630            )),
631            Predicate::Not(expr) => {
632                let LogicalExpression { inputs: [input_0] } = expr;
633                *input_0
634            }
635            Predicate::Unary(expr) => {
636                Predicate::Unary(UnaryExpression::new(expr.op.negate(), expr.term))
637            }
638            Predicate::Binary(expr) => Predicate::Binary(BinaryExpression::new(
639                expr.op.negate(),
640                expr.term,
641                expr.literal,
642            )),
643            Predicate::Set(expr) => Predicate::Set(SetExpression::new(
644                expr.op.negate(),
645                expr.term,
646                expr.literals,
647            )),
648        }
649    }
650    /// Simplifies the expression by removing `NOT` predicates,
651    /// directly negating the inner expressions instead. The transformation
652    /// applies logical laws (such as De Morgan's laws) to
653    /// recursively negate and simplify inner expressions within `NOT`
654    /// predicates.
655    ///
656    /// # Example
657    ///
658    /// ```rust
659    /// use std::ops::Not;
660    ///
661    /// use iceberg::expr::{LogicalExpression, Predicate, Reference};
662    /// use iceberg::spec::Datum;
663    ///
664    /// let expression = Reference::new("a").less_than(Datum::long(5)).not();
665    /// let result = expression.rewrite_not();
666    ///
667    /// assert_eq!(&format!("{result}"), "a >= 5");
668    /// ```
669    pub fn rewrite_not(self) -> Predicate {
670        visit(&mut RewriteNotVisitor::new(), &self)
671            .expect("RewriteNotVisitor guarantees always success")
672    }
673}
674
675impl Not for Predicate {
676    type Output = Predicate;
677
678    /// Create a predicate which is the reverse of this predicate. For example: `NOT (a > 10)`.
679    ///
680    /// This is different from [`Predicate::negate()`] since it doesn't rewrite expression, but
681    /// just adds a `NOT` operator.
682    ///
683    /// # Example
684    ///     
685    ///```rust
686    /// use std::ops::Bound::Unbounded;
687    ///
688    /// use iceberg::expr::BoundPredicate::Unary;
689    /// use iceberg::expr::Reference;
690    /// use iceberg::spec::Datum;
691    /// let expr1 = Reference::new("a").less_than(Datum::long(10));
692    ///
693    /// let expr = !expr1;
694    ///
695    /// assert_eq!(&format!("{expr}"), "NOT (a < 10)");
696    /// ```
697    fn not(self) -> Self::Output {
698        Predicate::Not(LogicalExpression::new([Box::new(self)]))
699    }
700}
701
702/// Bound predicate expression after binding to a schema.
703#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
704pub enum BoundPredicate {
705    /// An expression always evaluates to true.
706    AlwaysTrue,
707    /// An expression always evaluates to false.
708    AlwaysFalse,
709    /// An expression combined by `AND`, for example, `a > 10 AND b < 20`.
710    And(LogicalExpression<BoundPredicate, 2>),
711    /// An expression combined by `OR`, for example, `a > 10 OR b < 20`.
712    Or(LogicalExpression<BoundPredicate, 2>),
713    /// An expression combined by `NOT`, for example, `NOT (a > 10)`.
714    Not(LogicalExpression<BoundPredicate, 1>),
715    /// Unary expression, for example, `a IS NULL`.
716    Unary(UnaryExpression<BoundReference>),
717    /// Binary expression, for example, `a > 10`.
718    Binary(BinaryExpression<BoundReference>),
719    /// Set predicates, for example, `a IN (1, 2, 3)`.
720    Set(SetExpression<BoundReference>),
721}
722
723impl BoundPredicate {
724    pub(crate) fn and(self, other: BoundPredicate) -> BoundPredicate {
725        BoundPredicate::And(LogicalExpression::new([Box::new(self), Box::new(other)]))
726    }
727
728    pub(crate) fn or(self, other: BoundPredicate) -> BoundPredicate {
729        BoundPredicate::Or(LogicalExpression::new([Box::new(self), Box::new(other)]))
730    }
731
732    pub(crate) fn negate(self) -> BoundPredicate {
733        match self {
734            BoundPredicate::AlwaysTrue => BoundPredicate::AlwaysFalse,
735            BoundPredicate::AlwaysFalse => BoundPredicate::AlwaysTrue,
736            BoundPredicate::And(expr) => BoundPredicate::Or(LogicalExpression::new(
737                expr.inputs.map(|expr| Box::new(expr.negate())),
738            )),
739            BoundPredicate::Or(expr) => BoundPredicate::And(LogicalExpression::new(
740                expr.inputs.map(|expr| Box::new(expr.negate())),
741            )),
742            BoundPredicate::Not(expr) => {
743                let LogicalExpression { inputs: [input_0] } = expr;
744                *input_0
745            }
746            BoundPredicate::Unary(expr) => {
747                BoundPredicate::Unary(UnaryExpression::new(expr.op.negate(), expr.term))
748            }
749            BoundPredicate::Binary(expr) => BoundPredicate::Binary(BinaryExpression::new(
750                expr.op.negate(),
751                expr.term,
752                expr.literal,
753            )),
754            BoundPredicate::Set(expr) => BoundPredicate::Set(SetExpression::new(
755                expr.op.negate(),
756                expr.term,
757                expr.literals,
758            )),
759        }
760    }
761
762    /// Simplifies the expression by removing `NOT` predicates,
763    /// directly negating the inner expressions instead. The transformation
764    /// applies logical laws (such as De Morgan's laws) to
765    /// recursively negate and simplify inner expressions within `NOT`
766    /// predicates.
767    ///
768    /// # Example
769    ///
770    /// ```rust
771    /// use std::ops::Not;
772    ///
773    /// use iceberg::expr::{Bind, BoundPredicate, Reference};
774    /// use iceberg::spec::Datum;
775    ///
776    /// // This would need to be bound first, but the concept is:
777    /// // let expression = bound_predicate.not();
778    /// // let result = expression.rewrite_not();
779    /// ```
780    pub fn rewrite_not(self) -> BoundPredicate {
781        visit_bound(&mut RewriteNotVisitor::new(), &self)
782            .expect("RewriteNotVisitor guarantees always success")
783    }
784}
785
786impl Display for BoundPredicate {
787    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
788        match self {
789            BoundPredicate::AlwaysTrue => {
790                write!(f, "True")
791            }
792            BoundPredicate::AlwaysFalse => {
793                write!(f, "False")
794            }
795            BoundPredicate::And(expr) => {
796                write!(f, "({}) AND ({})", expr.inputs()[0], expr.inputs()[1])
797            }
798            BoundPredicate::Or(expr) => {
799                write!(f, "({}) OR ({})", expr.inputs()[0], expr.inputs()[1])
800            }
801            BoundPredicate::Not(expr) => {
802                write!(f, "NOT ({})", expr.inputs()[0])
803            }
804            BoundPredicate::Unary(expr) => {
805                write!(f, "{expr}")
806            }
807            BoundPredicate::Binary(expr) => {
808                write!(f, "{expr}")
809            }
810            BoundPredicate::Set(expr) => {
811                write!(f, "{expr}")
812            }
813        }
814    }
815}
816
817#[cfg(test)]
818mod tests {
819    use std::ops::Not;
820    use std::sync::Arc;
821
822    use crate::expr::Predicate::{AlwaysFalse, AlwaysTrue};
823    use crate::expr::{Bind, BoundPredicate, Reference};
824    use crate::spec::{Datum, NestedField, PrimitiveType, Schema, SchemaRef, Type};
825
826    #[test]
827    fn test_logical_or_rewrite_not() {
828        let expression = Reference::new("b")
829            .less_than(Datum::long(5))
830            .or(Reference::new("c").less_than(Datum::long(10)))
831            .not();
832
833        let expected = Reference::new("b")
834            .greater_than_or_equal_to(Datum::long(5))
835            .and(Reference::new("c").greater_than_or_equal_to(Datum::long(10)));
836
837        let result = expression.rewrite_not();
838
839        assert_eq!(result, expected);
840    }
841
842    #[test]
843    fn test_logical_and_rewrite_not() {
844        let expression = Reference::new("b")
845            .less_than(Datum::long(5))
846            .and(Reference::new("c").less_than(Datum::long(10)))
847            .not();
848
849        let expected = Reference::new("b")
850            .greater_than_or_equal_to(Datum::long(5))
851            .or(Reference::new("c").greater_than_or_equal_to(Datum::long(10)));
852
853        let result = expression.rewrite_not();
854
855        assert_eq!(result, expected);
856    }
857
858    #[test]
859    fn test_set_rewrite_not() {
860        let expression = Reference::new("a")
861            .is_in([Datum::int(5), Datum::int(6)])
862            .not();
863
864        let expected = Reference::new("a").is_not_in([Datum::int(5), Datum::int(6)]);
865
866        let result = expression.rewrite_not();
867
868        assert_eq!(result, expected);
869    }
870
871    #[test]
872    fn test_binary_rewrite_not() {
873        let expression = Reference::new("a").less_than(Datum::long(5)).not();
874
875        let expected = Reference::new("a").greater_than_or_equal_to(Datum::long(5));
876
877        let result = expression.rewrite_not();
878
879        assert_eq!(result, expected);
880    }
881
882    #[test]
883    fn test_unary_rewrite_not() {
884        let expression = Reference::new("a").is_null().not();
885
886        let expected = Reference::new("a").is_not_null();
887
888        let result = expression.rewrite_not();
889
890        assert_eq!(result, expected);
891    }
892
893    #[test]
894    fn test_predicate_and_reduce_always_true_false() {
895        let true_or_expr = AlwaysTrue.and(Reference::new("b").less_than(Datum::long(5)));
896        assert_eq!(&format!("{true_or_expr}"), "b < 5");
897
898        let expr_or_true = Reference::new("b")
899            .less_than(Datum::long(5))
900            .and(AlwaysTrue);
901        assert_eq!(&format!("{expr_or_true}"), "b < 5");
902
903        let false_or_expr = AlwaysFalse.and(Reference::new("b").less_than(Datum::long(5)));
904        assert_eq!(&format!("{false_or_expr}"), "FALSE");
905
906        let expr_or_false = Reference::new("b")
907            .less_than(Datum::long(5))
908            .and(AlwaysFalse);
909        assert_eq!(&format!("{expr_or_false}"), "FALSE");
910    }
911
912    #[test]
913    fn test_predicate_or_reduce_always_true_false() {
914        let true_or_expr = AlwaysTrue.or(Reference::new("b").less_than(Datum::long(5)));
915        assert_eq!(&format!("{true_or_expr}"), "TRUE");
916
917        let expr_or_true = Reference::new("b").less_than(Datum::long(5)).or(AlwaysTrue);
918        assert_eq!(&format!("{expr_or_true}"), "TRUE");
919
920        let false_or_expr = AlwaysFalse.or(Reference::new("b").less_than(Datum::long(5)));
921        assert_eq!(&format!("{false_or_expr}"), "b < 5");
922
923        let expr_or_false = Reference::new("b")
924            .less_than(Datum::long(5))
925            .or(AlwaysFalse);
926        assert_eq!(&format!("{expr_or_false}"), "b < 5");
927    }
928
929    #[test]
930    fn test_predicate_negate_and() {
931        let expression = Reference::new("b")
932            .less_than(Datum::long(5))
933            .and(Reference::new("c").less_than(Datum::long(10)));
934
935        let expected = Reference::new("b")
936            .greater_than_or_equal_to(Datum::long(5))
937            .or(Reference::new("c").greater_than_or_equal_to(Datum::long(10)));
938
939        let result = expression.negate();
940
941        assert_eq!(result, expected);
942    }
943
944    #[test]
945    fn test_predicate_negate_or() {
946        let expression = Reference::new("b")
947            .greater_than_or_equal_to(Datum::long(5))
948            .or(Reference::new("c").greater_than_or_equal_to(Datum::long(10)));
949
950        let expected = Reference::new("b")
951            .less_than(Datum::long(5))
952            .and(Reference::new("c").less_than(Datum::long(10)));
953
954        let result = expression.negate();
955
956        assert_eq!(result, expected);
957    }
958
959    #[test]
960    fn test_predicate_negate_not() {
961        let expression = Reference::new("b")
962            .greater_than_or_equal_to(Datum::long(5))
963            .not();
964
965        let expected = Reference::new("b").greater_than_or_equal_to(Datum::long(5));
966
967        let result = expression.negate();
968
969        assert_eq!(result, expected);
970    }
971
972    #[test]
973    fn test_predicate_negate_unary() {
974        let expression = Reference::new("b").is_not_null();
975
976        let expected = Reference::new("b").is_null();
977
978        let result = expression.negate();
979
980        assert_eq!(result, expected);
981    }
982
983    #[test]
984    fn test_predicate_negate_binary() {
985        let expression = Reference::new("a").less_than(Datum::long(5));
986
987        let expected = Reference::new("a").greater_than_or_equal_to(Datum::long(5));
988
989        let result = expression.negate();
990
991        assert_eq!(result, expected);
992    }
993
994    #[test]
995    fn test_predicate_negate_set() {
996        let expression = Reference::new("a").is_in([Datum::long(5), Datum::long(6)]);
997
998        let expected = Reference::new("a").is_not_in([Datum::long(5), Datum::long(6)]);
999
1000        let result = expression.negate();
1001
1002        assert_eq!(result, expected);
1003    }
1004
1005    pub fn table_schema_simple() -> SchemaRef {
1006        Arc::new(
1007            Schema::builder()
1008                .with_schema_id(1)
1009                .with_identifier_field_ids(vec![2])
1010                .with_fields(vec![
1011                    NestedField::optional(1, "foo", Type::Primitive(PrimitiveType::String)).into(),
1012                    NestedField::required(2, "bar", Type::Primitive(PrimitiveType::Int)).into(),
1013                    NestedField::optional(3, "baz", Type::Primitive(PrimitiveType::Boolean)).into(),
1014                    NestedField::optional(4, "qux", Type::Primitive(PrimitiveType::Float)).into(),
1015                ])
1016                .build()
1017                .unwrap(),
1018        )
1019    }
1020
1021    fn test_bound_predicate_serialize_diserialize(bound_predicate: BoundPredicate) {
1022        let serialized = serde_json::to_string(&bound_predicate).unwrap();
1023        let deserialized: BoundPredicate = serde_json::from_str(&serialized).unwrap();
1024        assert_eq!(bound_predicate, deserialized);
1025    }
1026
1027    #[test]
1028    fn test_bind_is_null() {
1029        let schema = table_schema_simple();
1030        let expr = Reference::new("foo").is_null();
1031        let bound_expr = expr.bind(schema, true).unwrap();
1032        assert_eq!(&format!("{bound_expr}"), "foo IS NULL");
1033        test_bound_predicate_serialize_diserialize(bound_expr);
1034    }
1035
1036    #[test]
1037    fn test_bind_is_null_required() {
1038        let schema = table_schema_simple();
1039        let expr = Reference::new("bar").is_null();
1040        let bound_expr = expr.bind(schema, true).unwrap();
1041        assert_eq!(&format!("{bound_expr}"), "False");
1042        test_bound_predicate_serialize_diserialize(bound_expr);
1043    }
1044
1045    #[test]
1046    fn test_bind_is_not_null() {
1047        let schema = table_schema_simple();
1048        let expr = Reference::new("foo").is_not_null();
1049        let bound_expr = expr.bind(schema, true).unwrap();
1050        assert_eq!(&format!("{bound_expr}"), "foo IS NOT NULL");
1051        test_bound_predicate_serialize_diserialize(bound_expr);
1052    }
1053
1054    #[test]
1055    fn test_bind_is_not_null_required() {
1056        let schema = table_schema_simple();
1057        let expr = Reference::new("bar").is_not_null();
1058        let bound_expr = expr.bind(schema, true).unwrap();
1059        assert_eq!(&format!("{bound_expr}"), "True");
1060        test_bound_predicate_serialize_diserialize(bound_expr);
1061    }
1062
1063    #[test]
1064    fn test_bind_is_nan() {
1065        let schema = table_schema_simple();
1066        let expr = Reference::new("qux").is_nan();
1067        let bound_expr = expr.bind(schema, true).unwrap();
1068        assert_eq!(&format!("{bound_expr}"), "qux IS NAN");
1069
1070        let schema_string = table_schema_simple();
1071        let expr_string = Reference::new("foo").is_nan();
1072        let bound_expr_string = expr_string.bind(schema_string, true);
1073        assert!(bound_expr_string.is_err());
1074        test_bound_predicate_serialize_diserialize(bound_expr);
1075    }
1076
1077    #[test]
1078    fn test_bind_is_nan_wrong_type() {
1079        let schema = table_schema_simple();
1080        let expr = Reference::new("foo").is_nan();
1081        let bound_expr = expr.bind(schema, true);
1082        assert!(bound_expr.is_err());
1083    }
1084
1085    #[test]
1086    fn test_bind_is_not_nan() {
1087        let schema = table_schema_simple();
1088        let expr = Reference::new("qux").is_not_nan();
1089        let bound_expr = expr.bind(schema, true).unwrap();
1090        assert_eq!(&format!("{bound_expr}"), "qux IS NOT NAN");
1091        test_bound_predicate_serialize_diserialize(bound_expr);
1092    }
1093
1094    #[test]
1095    fn test_bind_is_not_nan_wrong_type() {
1096        let schema = table_schema_simple();
1097        let expr = Reference::new("foo").is_not_nan();
1098        let bound_expr = expr.bind(schema, true);
1099        assert!(bound_expr.is_err());
1100    }
1101
1102    #[test]
1103    fn test_bind_less_than() {
1104        let schema = table_schema_simple();
1105        let expr = Reference::new("bar").less_than(Datum::int(10));
1106        let bound_expr = expr.bind(schema, true).unwrap();
1107        assert_eq!(&format!("{bound_expr}"), "bar < 10");
1108        test_bound_predicate_serialize_diserialize(bound_expr);
1109    }
1110
1111    #[test]
1112    fn test_bind_less_than_wrong_type() {
1113        let schema = table_schema_simple();
1114        let expr = Reference::new("bar").less_than(Datum::string("abcd"));
1115        let bound_expr = expr.bind(schema, true);
1116        assert!(bound_expr.is_err());
1117    }
1118
1119    #[test]
1120    fn test_bind_less_than_or_eq() {
1121        let schema = table_schema_simple();
1122        let expr = Reference::new("bar").less_than_or_equal_to(Datum::int(10));
1123        let bound_expr = expr.bind(schema, true).unwrap();
1124        assert_eq!(&format!("{bound_expr}"), "bar <= 10");
1125        test_bound_predicate_serialize_diserialize(bound_expr);
1126    }
1127
1128    #[test]
1129    fn test_bind_less_than_or_eq_wrong_type() {
1130        let schema = table_schema_simple();
1131        let expr = Reference::new("bar").less_than_or_equal_to(Datum::string("abcd"));
1132        let bound_expr = expr.bind(schema, true);
1133        assert!(bound_expr.is_err());
1134    }
1135
1136    #[test]
1137    fn test_bind_greater_than() {
1138        let schema = table_schema_simple();
1139        let expr = Reference::new("bar").greater_than(Datum::int(10));
1140        let bound_expr = expr.bind(schema, true).unwrap();
1141        assert_eq!(&format!("{bound_expr}"), "bar > 10");
1142        test_bound_predicate_serialize_diserialize(bound_expr);
1143    }
1144
1145    #[test]
1146    fn test_bind_greater_than_wrong_type() {
1147        let schema = table_schema_simple();
1148        let expr = Reference::new("bar").greater_than(Datum::string("abcd"));
1149        let bound_expr = expr.bind(schema, true);
1150        assert!(bound_expr.is_err());
1151    }
1152
1153    #[test]
1154    fn test_bind_greater_than_or_eq() {
1155        let schema = table_schema_simple();
1156        let expr = Reference::new("bar").greater_than_or_equal_to(Datum::int(10));
1157        let bound_expr = expr.bind(schema, true).unwrap();
1158        assert_eq!(&format!("{bound_expr}"), "bar >= 10");
1159        test_bound_predicate_serialize_diserialize(bound_expr);
1160    }
1161
1162    #[test]
1163    fn test_bind_greater_than_or_eq_wrong_type() {
1164        let schema = table_schema_simple();
1165        let expr = Reference::new("bar").greater_than_or_equal_to(Datum::string("abcd"));
1166        let bound_expr = expr.bind(schema, true);
1167        assert!(bound_expr.is_err());
1168    }
1169
1170    #[test]
1171    fn test_bind_equal_to() {
1172        let schema = table_schema_simple();
1173        let expr = Reference::new("bar").equal_to(Datum::int(10));
1174        let bound_expr = expr.bind(schema, true).unwrap();
1175        assert_eq!(&format!("{bound_expr}"), "bar = 10");
1176        test_bound_predicate_serialize_diserialize(bound_expr);
1177    }
1178
1179    #[test]
1180    fn test_bind_equal_to_above_max() {
1181        let schema = table_schema_simple();
1182        // int32 can hold up to 2147483647
1183        let expr = Reference::new("bar").equal_to(Datum::long(2147483648i64));
1184        let bound_expr = expr.bind(schema, true).unwrap();
1185        assert_eq!(&format!("{bound_expr}"), "False");
1186        test_bound_predicate_serialize_diserialize(bound_expr);
1187    }
1188
1189    #[test]
1190    fn test_bind_equal_to_below_min() {
1191        let schema = table_schema_simple();
1192        // int32 can hold up to -2147483647
1193        let expr = Reference::new("bar").equal_to(Datum::long(-2147483649i64));
1194        let bound_expr = expr.bind(schema, true).unwrap();
1195        assert_eq!(&format!("{bound_expr}"), "False");
1196        test_bound_predicate_serialize_diserialize(bound_expr);
1197    }
1198
1199    #[test]
1200    fn test_bind_not_equal_to_above_max() {
1201        let schema = table_schema_simple();
1202        // int32 can hold up to 2147483647
1203        let expr = Reference::new("bar").not_equal_to(Datum::long(2147483648i64));
1204        let bound_expr = expr.bind(schema, true).unwrap();
1205        assert_eq!(&format!("{bound_expr}"), "True");
1206        test_bound_predicate_serialize_diserialize(bound_expr);
1207    }
1208
1209    #[test]
1210    fn test_bind_not_equal_to_below_min() {
1211        let schema = table_schema_simple();
1212        // int32 can hold up to -2147483647
1213        let expr = Reference::new("bar").not_equal_to(Datum::long(-2147483649i64));
1214        let bound_expr = expr.bind(schema, true).unwrap();
1215        assert_eq!(&format!("{bound_expr}"), "True");
1216        test_bound_predicate_serialize_diserialize(bound_expr);
1217    }
1218
1219    #[test]
1220    fn test_bind_less_than_above_max() {
1221        let schema = table_schema_simple();
1222        // int32 can hold up to 2147483647
1223        let expr = Reference::new("bar").less_than(Datum::long(2147483648i64));
1224        let bound_expr = expr.bind(schema, true).unwrap();
1225        assert_eq!(&format!("{bound_expr}"), "True");
1226        test_bound_predicate_serialize_diserialize(bound_expr);
1227    }
1228
1229    #[test]
1230    fn test_bind_less_than_below_min() {
1231        let schema = table_schema_simple();
1232        // int32 can hold up to -2147483647
1233        let expr = Reference::new("bar").less_than(Datum::long(-2147483649i64));
1234        let bound_expr = expr.bind(schema, true).unwrap();
1235        assert_eq!(&format!("{bound_expr}"), "False");
1236        test_bound_predicate_serialize_diserialize(bound_expr);
1237    }
1238
1239    #[test]
1240    fn test_bind_less_than_or_equal_to_above_max() {
1241        let schema = table_schema_simple();
1242        // int32 can hold up to 2147483647
1243        let expr = Reference::new("bar").less_than_or_equal_to(Datum::long(2147483648i64));
1244        let bound_expr = expr.bind(schema, true).unwrap();
1245        assert_eq!(&format!("{bound_expr}"), "True");
1246        test_bound_predicate_serialize_diserialize(bound_expr);
1247    }
1248
1249    #[test]
1250    fn test_bind_less_than_or_equal_to_below_min() {
1251        let schema = table_schema_simple();
1252        // int32 can hold up to -2147483647
1253        let expr = Reference::new("bar").less_than_or_equal_to(Datum::long(-2147483649i64));
1254        let bound_expr = expr.bind(schema, true).unwrap();
1255        assert_eq!(&format!("{bound_expr}"), "False");
1256        test_bound_predicate_serialize_diserialize(bound_expr);
1257    }
1258
1259    #[test]
1260    fn test_bind_great_than_above_max() {
1261        let schema = table_schema_simple();
1262        // int32 can hold up to 2147483647
1263        let expr = Reference::new("bar").greater_than(Datum::long(2147483648i64));
1264        let bound_expr = expr.bind(schema, true).unwrap();
1265        assert_eq!(&format!("{bound_expr}"), "False");
1266        test_bound_predicate_serialize_diserialize(bound_expr);
1267    }
1268
1269    #[test]
1270    fn test_bind_great_than_below_min() {
1271        let schema = table_schema_simple();
1272        // int32 can hold up to -2147483647
1273        let expr = Reference::new("bar").greater_than(Datum::long(-2147483649i64));
1274        let bound_expr = expr.bind(schema, true).unwrap();
1275        assert_eq!(&format!("{bound_expr}"), "True");
1276        test_bound_predicate_serialize_diserialize(bound_expr);
1277    }
1278
1279    #[test]
1280    fn test_bind_great_than_or_equal_to_above_max() {
1281        let schema = table_schema_simple();
1282        // int32 can hold up to 2147483647
1283        let expr = Reference::new("bar").greater_than_or_equal_to(Datum::long(2147483648i64));
1284        let bound_expr = expr.bind(schema, true).unwrap();
1285        assert_eq!(&format!("{bound_expr}"), "False");
1286        test_bound_predicate_serialize_diserialize(bound_expr);
1287    }
1288
1289    #[test]
1290    fn test_bind_great_than_or_equal_to_below_min() {
1291        let schema = table_schema_simple();
1292        // int32 can hold up to -2147483647
1293        let expr = Reference::new("bar").greater_than_or_equal_to(Datum::long(-2147483649i64));
1294        let bound_expr = expr.bind(schema, true).unwrap();
1295        assert_eq!(&format!("{bound_expr}"), "True");
1296        test_bound_predicate_serialize_diserialize(bound_expr);
1297    }
1298
1299    #[test]
1300    fn test_bind_equal_to_wrong_type() {
1301        let schema = table_schema_simple();
1302        let expr = Reference::new("bar").equal_to(Datum::string("abcd"));
1303        let bound_expr = expr.bind(schema, true);
1304        assert!(bound_expr.is_err());
1305    }
1306
1307    #[test]
1308    fn test_bind_not_equal_to() {
1309        let schema = table_schema_simple();
1310        let expr = Reference::new("bar").not_equal_to(Datum::int(10));
1311        let bound_expr = expr.bind(schema, true).unwrap();
1312        assert_eq!(&format!("{bound_expr}"), "bar != 10");
1313        test_bound_predicate_serialize_diserialize(bound_expr);
1314    }
1315
1316    #[test]
1317    fn test_bind_not_equal_to_wrong_type() {
1318        let schema = table_schema_simple();
1319        let expr = Reference::new("bar").not_equal_to(Datum::string("abcd"));
1320        let bound_expr = expr.bind(schema, true);
1321        assert!(bound_expr.is_err());
1322    }
1323
1324    #[test]
1325    fn test_bind_starts_with() {
1326        let schema = table_schema_simple();
1327        let expr = Reference::new("foo").starts_with(Datum::string("abcd"));
1328        let bound_expr = expr.bind(schema, true).unwrap();
1329        assert_eq!(&format!("{bound_expr}"), r#"foo STARTS WITH "abcd""#);
1330        test_bound_predicate_serialize_diserialize(bound_expr);
1331    }
1332
1333    #[test]
1334    fn test_bind_starts_with_wrong_type() {
1335        let schema = table_schema_simple();
1336        let expr = Reference::new("bar").starts_with(Datum::string("abcd"));
1337        let bound_expr = expr.bind(schema, true);
1338        assert!(bound_expr.is_err());
1339    }
1340
1341    #[test]
1342    fn test_bind_not_starts_with() {
1343        let schema = table_schema_simple();
1344        let expr = Reference::new("foo").not_starts_with(Datum::string("abcd"));
1345        let bound_expr = expr.bind(schema, true).unwrap();
1346        assert_eq!(&format!("{bound_expr}"), r#"foo NOT STARTS WITH "abcd""#);
1347        test_bound_predicate_serialize_diserialize(bound_expr);
1348    }
1349
1350    #[test]
1351    fn test_bind_not_starts_with_wrong_type() {
1352        let schema = table_schema_simple();
1353        let expr = Reference::new("bar").not_starts_with(Datum::string("abcd"));
1354        let bound_expr = expr.bind(schema, true);
1355        assert!(bound_expr.is_err());
1356    }
1357
1358    #[test]
1359    fn test_bind_in() {
1360        let schema = table_schema_simple();
1361        let expr = Reference::new("bar").is_in([Datum::int(10), Datum::int(20)]);
1362        let bound_expr = expr.bind(schema, true).unwrap();
1363        assert_eq!(&format!("{bound_expr}"), "bar IN (20, 10)");
1364        test_bound_predicate_serialize_diserialize(bound_expr);
1365    }
1366
1367    #[test]
1368    fn test_bind_in_empty() {
1369        let schema = table_schema_simple();
1370        let expr = Reference::new("bar").is_in(vec![]);
1371        let bound_expr = expr.bind(schema, true).unwrap();
1372        assert_eq!(&format!("{bound_expr}"), "False");
1373        test_bound_predicate_serialize_diserialize(bound_expr);
1374    }
1375
1376    #[test]
1377    fn test_bind_in_one_literal() {
1378        let schema = table_schema_simple();
1379        let expr = Reference::new("bar").is_in(vec![Datum::int(10)]);
1380        let bound_expr = expr.bind(schema, true).unwrap();
1381        assert_eq!(&format!("{bound_expr}"), "bar = 10");
1382        test_bound_predicate_serialize_diserialize(bound_expr);
1383    }
1384
1385    #[test]
1386    fn test_bind_in_wrong_type() {
1387        let schema = table_schema_simple();
1388        let expr = Reference::new("bar").is_in(vec![Datum::int(10), Datum::string("abcd")]);
1389        let bound_expr = expr.bind(schema, true);
1390        assert!(bound_expr.is_err());
1391    }
1392
1393    #[test]
1394    fn test_bind_not_in() {
1395        let schema = table_schema_simple();
1396        let expr = Reference::new("bar").is_not_in([Datum::int(10), Datum::int(20)]);
1397        let bound_expr = expr.bind(schema, true).unwrap();
1398        assert_eq!(&format!("{bound_expr}"), "bar NOT IN (20, 10)");
1399        test_bound_predicate_serialize_diserialize(bound_expr);
1400    }
1401
1402    #[test]
1403    fn test_bind_not_in_empty() {
1404        let schema = table_schema_simple();
1405        let expr = Reference::new("bar").is_not_in(vec![]);
1406        let bound_expr = expr.bind(schema, true).unwrap();
1407        assert_eq!(&format!("{bound_expr}"), "True");
1408        test_bound_predicate_serialize_diserialize(bound_expr);
1409    }
1410
1411    #[test]
1412    fn test_bind_not_in_one_literal() {
1413        let schema = table_schema_simple();
1414        let expr = Reference::new("bar").is_not_in(vec![Datum::int(10)]);
1415        let bound_expr = expr.bind(schema, true).unwrap();
1416        assert_eq!(&format!("{bound_expr}"), "bar != 10");
1417        test_bound_predicate_serialize_diserialize(bound_expr);
1418    }
1419
1420    #[test]
1421    fn test_bind_not_in_wrong_type() {
1422        let schema = table_schema_simple();
1423        let expr = Reference::new("bar").is_not_in([Datum::int(10), Datum::string("abcd")]);
1424        let bound_expr = expr.bind(schema, true);
1425        assert!(bound_expr.is_err());
1426    }
1427
1428    #[test]
1429    fn test_bind_and() {
1430        let schema = table_schema_simple();
1431        let expr = Reference::new("bar")
1432            .less_than(Datum::int(10))
1433            .and(Reference::new("foo").is_null());
1434        let bound_expr = expr.bind(schema, true).unwrap();
1435        assert_eq!(&format!("{bound_expr}"), "(bar < 10) AND (foo IS NULL)");
1436        test_bound_predicate_serialize_diserialize(bound_expr);
1437    }
1438
1439    #[test]
1440    fn test_bind_and_always_false() {
1441        let schema = table_schema_simple();
1442        let expr = Reference::new("foo")
1443            .less_than(Datum::string("abcd"))
1444            .and(Reference::new("bar").is_null());
1445        let bound_expr = expr.bind(schema, true).unwrap();
1446        assert_eq!(&format!("{bound_expr}"), "False");
1447        test_bound_predicate_serialize_diserialize(bound_expr);
1448    }
1449
1450    #[test]
1451    fn test_bind_and_always_true() {
1452        let schema = table_schema_simple();
1453        let expr = Reference::new("foo")
1454            .less_than(Datum::string("abcd"))
1455            .and(Reference::new("bar").is_not_null());
1456        let bound_expr = expr.bind(schema, true).unwrap();
1457        assert_eq!(&format!("{bound_expr}"), r#"foo < "abcd""#);
1458        test_bound_predicate_serialize_diserialize(bound_expr);
1459    }
1460
1461    #[test]
1462    fn test_bind_or() {
1463        let schema = table_schema_simple();
1464        let expr = Reference::new("bar")
1465            .less_than(Datum::int(10))
1466            .or(Reference::new("foo").is_null());
1467        let bound_expr = expr.bind(schema, true).unwrap();
1468        assert_eq!(&format!("{bound_expr}"), "(bar < 10) OR (foo IS NULL)");
1469        test_bound_predicate_serialize_diserialize(bound_expr);
1470    }
1471
1472    #[test]
1473    fn test_bind_or_always_true() {
1474        let schema = table_schema_simple();
1475        let expr = Reference::new("foo")
1476            .less_than(Datum::string("abcd"))
1477            .or(Reference::new("bar").is_not_null());
1478        let bound_expr = expr.bind(schema, true).unwrap();
1479        assert_eq!(&format!("{bound_expr}"), "True");
1480        test_bound_predicate_serialize_diserialize(bound_expr);
1481    }
1482
1483    #[test]
1484    fn test_bind_or_always_false() {
1485        let schema = table_schema_simple();
1486        let expr = Reference::new("foo")
1487            .less_than(Datum::string("abcd"))
1488            .or(Reference::new("bar").is_null());
1489        let bound_expr = expr.bind(schema, true).unwrap();
1490        assert_eq!(&format!("{bound_expr}"), r#"foo < "abcd""#);
1491        test_bound_predicate_serialize_diserialize(bound_expr);
1492    }
1493
1494    #[test]
1495    fn test_bind_not() {
1496        let schema = table_schema_simple();
1497        let expr = !Reference::new("bar").less_than(Datum::int(10));
1498        let bound_expr = expr.bind(schema, true).unwrap();
1499        assert_eq!(&format!("{bound_expr}"), "NOT (bar < 10)");
1500        test_bound_predicate_serialize_diserialize(bound_expr);
1501    }
1502
1503    #[test]
1504    fn test_bind_not_always_true() {
1505        let schema = table_schema_simple();
1506        let expr = !Reference::new("bar").is_not_null();
1507        let bound_expr = expr.bind(schema, true).unwrap();
1508        assert_eq!(&format!("{bound_expr}"), "False");
1509        test_bound_predicate_serialize_diserialize(bound_expr);
1510    }
1511
1512    #[test]
1513    fn test_bind_not_always_false() {
1514        let schema = table_schema_simple();
1515        let expr = !Reference::new("bar").is_null();
1516        let bound_expr = expr.bind(schema, true).unwrap();
1517        assert_eq!(&format!("{bound_expr}"), r#"True"#);
1518        test_bound_predicate_serialize_diserialize(bound_expr);
1519    }
1520
1521    #[test]
1522    fn test_bound_predicate_rewrite_not_binary() {
1523        let schema = table_schema_simple();
1524
1525        // Test NOT elimination on binary predicates: NOT(bar < 10) => bar >= 10
1526        let predicate = Reference::new("bar").less_than(Datum::int(10)).not();
1527        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1528        let result = bound_predicate.rewrite_not();
1529
1530        // The result should be bar >= 10
1531        let expected_predicate = Reference::new("bar").greater_than_or_equal_to(Datum::int(10));
1532        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1533
1534        assert_eq!(result, expected_bound);
1535        assert_eq!(&format!("{result}"), "bar >= 10");
1536    }
1537
1538    #[test]
1539    fn test_bound_predicate_rewrite_not_unary() {
1540        let schema = table_schema_simple();
1541
1542        // Test NOT elimination on unary predicates: NOT(foo IS NULL) => foo IS NOT NULL
1543        let predicate = Reference::new("foo").is_null().not();
1544        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1545        let result = bound_predicate.rewrite_not();
1546
1547        // The result should be foo IS NOT NULL
1548        let expected_predicate = Reference::new("foo").is_not_null();
1549        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1550
1551        assert_eq!(result, expected_bound);
1552        assert_eq!(&format!("{result}"), "foo IS NOT NULL");
1553    }
1554
1555    #[test]
1556    fn test_bound_predicate_rewrite_not_set() {
1557        let schema = table_schema_simple();
1558
1559        // Test NOT elimination on set predicates: NOT(bar IN (10, 20)) => bar NOT IN (10, 20)
1560        let predicate = Reference::new("bar")
1561            .is_in([Datum::int(10), Datum::int(20)])
1562            .not();
1563        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1564        let result = bound_predicate.rewrite_not();
1565
1566        // The result should be bar NOT IN (10, 20)
1567        let expected_predicate = Reference::new("bar").is_not_in([Datum::int(10), Datum::int(20)]);
1568        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1569
1570        assert_eq!(result, expected_bound);
1571        // Note: HashSet order may vary, so we check that it contains the expected format
1572        let result_str = format!("{result}");
1573        assert!(
1574            result_str.contains("bar NOT IN")
1575                && result_str.contains("10")
1576                && result_str.contains("20")
1577        );
1578    }
1579
1580    #[test]
1581    fn test_bound_predicate_rewrite_not_and_demorgan() {
1582        let schema = table_schema_simple();
1583
1584        // Test De Morgan's law: NOT(A AND B) = (NOT A) OR (NOT B)
1585        // NOT((bar < 10) AND (foo IS NULL)) => (bar >= 10) OR (foo IS NOT NULL)
1586        let predicate = Reference::new("bar")
1587            .less_than(Datum::int(10))
1588            .and(Reference::new("foo").is_null())
1589            .not();
1590
1591        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1592        let result = bound_predicate.rewrite_not();
1593
1594        // Expected: (bar >= 10) OR (foo IS NOT NULL)
1595        let expected_predicate = Reference::new("bar")
1596            .greater_than_or_equal_to(Datum::int(10))
1597            .or(Reference::new("foo").is_not_null());
1598
1599        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1600
1601        assert_eq!(result, expected_bound);
1602        assert_eq!(&format!("{result}"), "(bar >= 10) OR (foo IS NOT NULL)");
1603    }
1604
1605    #[test]
1606    fn test_bound_predicate_rewrite_not_or_demorgan() {
1607        let schema = table_schema_simple();
1608
1609        // Test De Morgan's law: NOT(A OR B) = (NOT A) AND (NOT B)
1610        // NOT((bar < 10) OR (foo IS NULL)) => (bar >= 10) AND (foo IS NOT NULL)
1611        let predicate = Reference::new("bar")
1612            .less_than(Datum::int(10))
1613            .or(Reference::new("foo").is_null())
1614            .not();
1615
1616        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1617        let result = bound_predicate.rewrite_not();
1618
1619        // Expected: (bar >= 10) AND (foo IS NOT NULL)
1620        let expected_predicate = Reference::new("bar")
1621            .greater_than_or_equal_to(Datum::int(10))
1622            .and(Reference::new("foo").is_not_null());
1623
1624        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1625
1626        assert_eq!(result, expected_bound);
1627        assert_eq!(&format!("{result}"), "(bar >= 10) AND (foo IS NOT NULL)");
1628    }
1629
1630    #[test]
1631    fn test_bound_predicate_rewrite_not_double_negative() {
1632        let schema = table_schema_simple();
1633
1634        // Test double negative elimination: NOT(NOT(bar < 10)) => bar < 10
1635        let predicate = Reference::new("bar").less_than(Datum::int(10)).not().not();
1636        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1637        let result = bound_predicate.rewrite_not();
1638
1639        // The result should be bar < 10 (original predicate)
1640        let expected_predicate = Reference::new("bar").less_than(Datum::int(10));
1641        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1642
1643        assert_eq!(result, expected_bound);
1644        assert_eq!(&format!("{result}"), "bar < 10");
1645    }
1646
1647    #[test]
1648    fn test_bound_predicate_rewrite_not_always_true_false() {
1649        let schema = table_schema_simple();
1650
1651        // Test NOT(AlwaysTrue) => AlwaysFalse
1652        let predicate = Reference::new("bar").is_not_null().not(); // This becomes NOT(AlwaysTrue) since bar is required
1653        let bound_predicate = predicate.bind(schema.clone(), true).unwrap();
1654        let result = bound_predicate.rewrite_not();
1655
1656        assert_eq!(result, BoundPredicate::AlwaysFalse);
1657        assert_eq!(&format!("{result}"), "False");
1658
1659        // Test NOT(AlwaysFalse) => AlwaysTrue
1660        let predicate2 = Reference::new("bar").is_null().not(); // This becomes NOT(AlwaysFalse) since bar is required
1661        let bound_predicate2 = predicate2.bind(schema, true).unwrap();
1662        let result2 = bound_predicate2.rewrite_not();
1663
1664        assert_eq!(result2, BoundPredicate::AlwaysTrue);
1665        assert_eq!(&format!("{result2}"), "True");
1666    }
1667
1668    #[test]
1669    fn test_bound_predicate_rewrite_not_complex_nested() {
1670        let schema = table_schema_simple();
1671
1672        // Test complex nested expression:
1673        // NOT(NOT((bar >= 10) AND (foo IS NOT NULL)) OR (bar < 5))
1674        // Should become: ((bar >= 10) AND (foo IS NOT NULL)) AND (bar >= 5)
1675        let inner_predicate = Reference::new("bar")
1676            .greater_than_or_equal_to(Datum::int(10))
1677            .and(Reference::new("foo").is_not_null())
1678            .not();
1679
1680        let complex_predicate = inner_predicate
1681            .or(Reference::new("bar").less_than(Datum::int(5)))
1682            .not();
1683
1684        let bound_predicate = complex_predicate.bind(schema.clone(), true).unwrap();
1685        let result = bound_predicate.rewrite_not();
1686
1687        // Expected: ((bar >= 10) AND (foo IS NOT NULL)) AND (bar >= 5)
1688        // This is because NOT(NOT(A) OR B) = A AND NOT(B)
1689        let expected_predicate = Reference::new("bar")
1690            .greater_than_or_equal_to(Datum::int(10))
1691            .and(Reference::new("foo").is_not_null())
1692            .and(Reference::new("bar").greater_than_or_equal_to(Datum::int(5)));
1693
1694        let expected_bound = expected_predicate.bind(schema, true).unwrap();
1695
1696        assert_eq!(result, expected_bound);
1697        assert_eq!(
1698            &format!("{result}"),
1699            "((bar >= 10) AND (foo IS NOT NULL)) AND (bar >= 5)"
1700        );
1701    }
1702}
iceberg/expr/predicate.rs

iceberg/expr/
predicate.rs
