iceberg/expr/visitors/
bound_predicate_visitor.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
18use fnv::FnvHashSet;
19
20use crate::Result;
21use crate::expr::{BoundPredicate, BoundReference, PredicateOperator};
22use crate::spec::Datum;
23
24/// A visitor for [`BoundPredicate`]s. Visits in post-order.
25pub trait BoundPredicateVisitor {
26    /// The return type of this visitor
27    type T;
28
29    /// Called after an `AlwaysTrue` predicate is visited
30    fn always_true(&mut self) -> Result<Self::T>;
31
32    /// Called after an `AlwaysFalse` predicate is visited
33    fn always_false(&mut self) -> Result<Self::T>;
34
35    /// Called after an `And` predicate is visited
36    fn and(&mut self, lhs: Self::T, rhs: Self::T) -> Result<Self::T>;
37
38    /// Called after an `Or` predicate is visited
39    fn or(&mut self, lhs: Self::T, rhs: Self::T) -> Result<Self::T>;
40
41    /// Called after a `Not` predicate is visited
42    fn not(&mut self, inner: Self::T) -> Result<Self::T>;
43
44    /// Called after a predicate with an `IsNull` operator is visited
45    fn is_null(
46        &mut self,
47        reference: &BoundReference,
48        predicate: &BoundPredicate,
49    ) -> Result<Self::T>;
50
51    /// Called after a predicate with a `NotNull` operator is visited
52    fn not_null(
53        &mut self,
54        reference: &BoundReference,
55        predicate: &BoundPredicate,
56    ) -> Result<Self::T>;
57
58    /// Called after a predicate with an `IsNan` operator is visited
59    fn is_nan(&mut self, reference: &BoundReference, predicate: &BoundPredicate)
60    -> Result<Self::T>;
61
62    /// Called after a predicate with a `NotNan` operator is visited
63    fn not_nan(
64        &mut self,
65        reference: &BoundReference,
66        predicate: &BoundPredicate,
67    ) -> Result<Self::T>;
68
69    /// Called after a predicate with a `LessThan` operator is visited
70    fn less_than(
71        &mut self,
72        reference: &BoundReference,
73        literal: &Datum,
74        predicate: &BoundPredicate,
75    ) -> Result<Self::T>;
76
77    /// Called after a predicate with a `LessThanOrEq` operator is visited
78    fn less_than_or_eq(
79        &mut self,
80        reference: &BoundReference,
81        literal: &Datum,
82        predicate: &BoundPredicate,
83    ) -> Result<Self::T>;
84
85    /// Called after a predicate with a `GreaterThan` operator is visited
86    fn greater_than(
87        &mut self,
88        reference: &BoundReference,
89        literal: &Datum,
90        predicate: &BoundPredicate,
91    ) -> Result<Self::T>;
92
93    /// Called after a predicate with a `GreaterThanOrEq` operator is visited
94    fn greater_than_or_eq(
95        &mut self,
96        reference: &BoundReference,
97        literal: &Datum,
98        predicate: &BoundPredicate,
99    ) -> Result<Self::T>;
100
101    /// Called after a predicate with an `Eq` operator is visited
102    fn eq(
103        &mut self,
104        reference: &BoundReference,
105        literal: &Datum,
106        predicate: &BoundPredicate,
107    ) -> Result<Self::T>;
108
109    /// Called after a predicate with a `NotEq` operator is visited
110    fn not_eq(
111        &mut self,
112        reference: &BoundReference,
113        literal: &Datum,
114        predicate: &BoundPredicate,
115    ) -> Result<Self::T>;
116
117    /// Called after a predicate with a `StartsWith` operator is visited
118    fn starts_with(
119        &mut self,
120        reference: &BoundReference,
121        literal: &Datum,
122        predicate: &BoundPredicate,
123    ) -> Result<Self::T>;
124
125    /// Called after a predicate with a `NotStartsWith` operator is visited
126    fn not_starts_with(
127        &mut self,
128        reference: &BoundReference,
129        literal: &Datum,
130        predicate: &BoundPredicate,
131    ) -> Result<Self::T>;
132
133    /// Called after a predicate with an `In` operator is visited
134    fn r#in(
135        &mut self,
136        reference: &BoundReference,
137        literals: &FnvHashSet<Datum>,
138        predicate: &BoundPredicate,
139    ) -> Result<Self::T>;
140
141    /// Called after a predicate with a `NotIn` operator is visited
142    fn not_in(
143        &mut self,
144        reference: &BoundReference,
145        literals: &FnvHashSet<Datum>,
146        predicate: &BoundPredicate,
147    ) -> Result<Self::T>;
148}
149
150/// Visits a [`BoundPredicate`] with the provided visitor,
151/// in post-order
152pub(crate) fn visit<V: BoundPredicateVisitor>(
153    visitor: &mut V,
154    predicate: &BoundPredicate,
155) -> Result<V::T> {
156    match predicate {
157        BoundPredicate::AlwaysTrue => visitor.always_true(),
158        BoundPredicate::AlwaysFalse => visitor.always_false(),
159        BoundPredicate::And(expr) => {
160            let [left_pred, right_pred] = expr.inputs();
161
162            let left_result = visit(visitor, left_pred)?;
163            let right_result = visit(visitor, right_pred)?;
164
165            visitor.and(left_result, right_result)
166        }
167        BoundPredicate::Or(expr) => {
168            let [left_pred, right_pred] = expr.inputs();
169
170            let left_result = visit(visitor, left_pred)?;
171            let right_result = visit(visitor, right_pred)?;
172
173            visitor.or(left_result, right_result)
174        }
175        BoundPredicate::Not(expr) => {
176            let [inner_pred] = expr.inputs();
177
178            let inner_result = visit(visitor, inner_pred)?;
179
180            visitor.not(inner_result)
181        }
182        BoundPredicate::Unary(expr) => match expr.op() {
183            PredicateOperator::IsNull => visitor.is_null(expr.term(), predicate),
184            PredicateOperator::NotNull => visitor.not_null(expr.term(), predicate),
185            PredicateOperator::IsNan => visitor.is_nan(expr.term(), predicate),
186            PredicateOperator::NotNan => visitor.not_nan(expr.term(), predicate),
187            op => {
188                panic!("Unexpected op for unary predicate: {}", &op)
189            }
190        },
191        BoundPredicate::Binary(expr) => {
192            let reference = expr.term();
193            let literal = expr.literal();
194            match expr.op() {
195                PredicateOperator::LessThan => visitor.less_than(reference, literal, predicate),
196                PredicateOperator::LessThanOrEq => {
197                    visitor.less_than_or_eq(reference, literal, predicate)
198                }
199                PredicateOperator::GreaterThan => {
200                    visitor.greater_than(reference, literal, predicate)
201                }
202                PredicateOperator::GreaterThanOrEq => {
203                    visitor.greater_than_or_eq(reference, literal, predicate)
204                }
205                PredicateOperator::Eq => visitor.eq(reference, literal, predicate),
206                PredicateOperator::NotEq => visitor.not_eq(reference, literal, predicate),
207                PredicateOperator::StartsWith => visitor.starts_with(reference, literal, predicate),
208                PredicateOperator::NotStartsWith => {
209                    visitor.not_starts_with(reference, literal, predicate)
210                }
211                op => {
212                    panic!("Unexpected op for binary predicate: {}", &op)
213                }
214            }
215        }
216        BoundPredicate::Set(expr) => {
217            let reference = expr.term();
218            let literals = expr.literals();
219            match expr.op() {
220                PredicateOperator::In => visitor.r#in(reference, literals, predicate),
221                PredicateOperator::NotIn => visitor.not_in(reference, literals, predicate),
222                op => {
223                    panic!("Unexpected op for set predicate: {}", &op)
224                }
225            }
226        }
227    }
228}
229
230#[cfg(test)]
231mod tests {
232    use std::ops::Not;
233    use std::sync::Arc;
234
235    use fnv::FnvHashSet;
236
237    use crate::expr::visitors::bound_predicate_visitor::{BoundPredicateVisitor, visit};
238    use crate::expr::{
239        BinaryExpression, Bind, BoundPredicate, BoundReference, Predicate, PredicateOperator,
240        Reference, SetExpression, UnaryExpression,
241    };
242    use crate::spec::{Datum, NestedField, PrimitiveType, Schema, SchemaRef, Type};
243
244    struct TestEvaluator {}
245    impl BoundPredicateVisitor for TestEvaluator {
246        type T = bool;
247
248        fn always_true(&mut self) -> crate::Result<Self::T> {
249            Ok(true)
250        }
251
252        fn always_false(&mut self) -> crate::Result<Self::T> {
253            Ok(false)
254        }
255
256        fn and(&mut self, lhs: Self::T, rhs: Self::T) -> crate::Result<Self::T> {
257            Ok(lhs && rhs)
258        }
259
260        fn or(&mut self, lhs: Self::T, rhs: Self::T) -> crate::Result<Self::T> {
261            Ok(lhs || rhs)
262        }
263
264        fn not(&mut self, inner: Self::T) -> crate::Result<Self::T> {
265            Ok(!inner)
266        }
267
268        fn is_null(
269            &mut self,
270            _reference: &BoundReference,
271            _predicate: &BoundPredicate,
272        ) -> crate::Result<bool> {
273            Ok(true)
274        }
275
276        fn not_null(
277            &mut self,
278            _reference: &BoundReference,
279            _predicate: &BoundPredicate,
280        ) -> crate::Result<bool> {
281            Ok(false)
282        }
283
284        fn is_nan(
285            &mut self,
286            _reference: &BoundReference,
287            _predicate: &BoundPredicate,
288        ) -> crate::Result<bool> {
289            Ok(true)
290        }
291
292        fn not_nan(
293            &mut self,
294            _reference: &BoundReference,
295            _predicate: &BoundPredicate,
296        ) -> crate::Result<bool> {
297            Ok(false)
298        }
299
300        fn less_than(
301            &mut self,
302            _reference: &BoundReference,
303            _literal: &Datum,
304            _predicate: &BoundPredicate,
305        ) -> crate::Result<bool> {
306            Ok(true)
307        }
308
309        fn less_than_or_eq(
310            &mut self,
311            _reference: &BoundReference,
312            _literal: &Datum,
313            _predicate: &BoundPredicate,
314        ) -> crate::Result<bool> {
315            Ok(false)
316        }
317
318        fn greater_than(
319            &mut self,
320            _reference: &BoundReference,
321            _literal: &Datum,
322            _predicate: &BoundPredicate,
323        ) -> crate::Result<bool> {
324            Ok(true)
325        }
326
327        fn greater_than_or_eq(
328            &mut self,
329            _reference: &BoundReference,
330            _literal: &Datum,
331            _predicate: &BoundPredicate,
332        ) -> crate::Result<bool> {
333            Ok(false)
334        }
335
336        fn eq(
337            &mut self,
338            _reference: &BoundReference,
339            _literal: &Datum,
340            _predicate: &BoundPredicate,
341        ) -> crate::Result<bool> {
342            Ok(true)
343        }
344
345        fn not_eq(
346            &mut self,
347            _reference: &BoundReference,
348            _literal: &Datum,
349            _predicate: &BoundPredicate,
350        ) -> crate::Result<bool> {
351            Ok(false)
352        }
353
354        fn starts_with(
355            &mut self,
356            _reference: &BoundReference,
357            _literal: &Datum,
358            _predicate: &BoundPredicate,
359        ) -> crate::Result<bool> {
360            Ok(true)
361        }
362
363        fn not_starts_with(
364            &mut self,
365            _reference: &BoundReference,
366            _literal: &Datum,
367            _predicate: &BoundPredicate,
368        ) -> crate::Result<bool> {
369            Ok(false)
370        }
371
372        fn r#in(
373            &mut self,
374            _reference: &BoundReference,
375            _literals: &FnvHashSet<Datum>,
376            _predicate: &BoundPredicate,
377        ) -> crate::Result<bool> {
378            Ok(true)
379        }
380
381        fn not_in(
382            &mut self,
383            _reference: &BoundReference,
384            _literals: &FnvHashSet<Datum>,
385            _predicate: &BoundPredicate,
386        ) -> crate::Result<bool> {
387            Ok(false)
388        }
389    }
390
391    fn create_test_schema() -> SchemaRef {
392        let schema = Schema::builder()
393            .with_fields(vec![
394                Arc::new(NestedField::required(
395                    1,
396                    "a",
397                    Type::Primitive(PrimitiveType::Int),
398                )),
399                Arc::new(NestedField::required(
400                    2,
401                    "b",
402                    Type::Primitive(PrimitiveType::Float),
403                )),
404                Arc::new(NestedField::optional(
405                    3,
406                    "c",
407                    Type::Primitive(PrimitiveType::Float),
408                )),
409            ])
410            .build()
411            .unwrap();
412
413        let schema_arc = Arc::new(schema);
414        schema_arc.clone()
415    }
416
417    #[test]
418    fn test_always_true() {
419        let predicate = Predicate::AlwaysTrue;
420        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
421
422        let mut test_evaluator = TestEvaluator {};
423
424        let result = visit(&mut test_evaluator, &bound_predicate);
425
426        assert!(result.unwrap());
427    }
428
429    #[test]
430    fn test_always_false() {
431        let predicate = Predicate::AlwaysFalse;
432        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
433
434        let mut test_evaluator = TestEvaluator {};
435
436        let result = visit(&mut test_evaluator, &bound_predicate);
437
438        assert!(!result.unwrap());
439    }
440
441    #[test]
442    fn test_logical_and() {
443        let predicate = Predicate::AlwaysTrue.and(Predicate::AlwaysFalse);
444        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
445
446        let mut test_evaluator = TestEvaluator {};
447
448        let result = visit(&mut test_evaluator, &bound_predicate);
449
450        assert!(!result.unwrap());
451
452        let predicate = Predicate::AlwaysFalse.and(Predicate::AlwaysFalse);
453        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
454
455        let mut test_evaluator = TestEvaluator {};
456
457        let result = visit(&mut test_evaluator, &bound_predicate);
458
459        assert!(!result.unwrap());
460
461        let predicate = Predicate::AlwaysTrue.and(Predicate::AlwaysTrue);
462        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
463
464        let mut test_evaluator = TestEvaluator {};
465
466        let result = visit(&mut test_evaluator, &bound_predicate);
467
468        assert!(result.unwrap());
469    }
470
471    #[test]
472    fn test_logical_or() {
473        let predicate = Predicate::AlwaysTrue.or(Predicate::AlwaysFalse);
474        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
475
476        let mut test_evaluator = TestEvaluator {};
477
478        let result = visit(&mut test_evaluator, &bound_predicate);
479
480        assert!(result.unwrap());
481
482        let predicate = Predicate::AlwaysFalse.or(Predicate::AlwaysFalse);
483        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
484
485        let mut test_evaluator = TestEvaluator {};
486
487        let result = visit(&mut test_evaluator, &bound_predicate);
488
489        assert!(!result.unwrap());
490
491        let predicate = Predicate::AlwaysTrue.or(Predicate::AlwaysTrue);
492        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
493
494        let mut test_evaluator = TestEvaluator {};
495
496        let result = visit(&mut test_evaluator, &bound_predicate);
497
498        assert!(result.unwrap());
499    }
500
501    #[test]
502    fn test_not() {
503        let predicate = Predicate::AlwaysFalse.not();
504        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
505
506        let mut test_evaluator = TestEvaluator {};
507
508        let result = visit(&mut test_evaluator, &bound_predicate);
509
510        assert!(result.unwrap());
511
512        let predicate = Predicate::AlwaysTrue.not();
513        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
514
515        let mut test_evaluator = TestEvaluator {};
516
517        let result = visit(&mut test_evaluator, &bound_predicate);
518
519        assert!(!result.unwrap());
520    }
521
522    #[test]
523    fn test_is_null() {
524        let predicate = Predicate::Unary(UnaryExpression::new(
525            PredicateOperator::IsNull,
526            Reference::new("c"),
527        ));
528        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
529
530        let mut test_evaluator = TestEvaluator {};
531
532        let result = visit(&mut test_evaluator, &bound_predicate);
533
534        assert!(result.unwrap());
535    }
536
537    #[test]
538    fn test_not_null() {
539        let predicate = Predicate::Unary(UnaryExpression::new(
540            PredicateOperator::NotNull,
541            Reference::new("a"),
542        ));
543        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
544
545        let mut test_evaluator = TestEvaluator {};
546
547        let result = visit(&mut test_evaluator, &bound_predicate);
548
549        assert!(result.unwrap());
550    }
551
552    #[test]
553    fn test_is_nan() {
554        let predicate = Predicate::Unary(UnaryExpression::new(
555            PredicateOperator::IsNan,
556            Reference::new("b"),
557        ));
558        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
559
560        let mut test_evaluator = TestEvaluator {};
561
562        let result = visit(&mut test_evaluator, &bound_predicate);
563
564        assert!(result.unwrap());
565    }
566
567    #[test]
568    fn test_not_nan() {
569        let predicate = Predicate::Unary(UnaryExpression::new(
570            PredicateOperator::NotNan,
571            Reference::new("b"),
572        ));
573        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
574
575        let mut test_evaluator = TestEvaluator {};
576
577        let result = visit(&mut test_evaluator, &bound_predicate);
578
579        assert!(!result.unwrap());
580    }
581
582    #[test]
583    fn test_less_than() {
584        let predicate = Predicate::Binary(BinaryExpression::new(
585            PredicateOperator::LessThan,
586            Reference::new("a"),
587            Datum::int(10),
588        ));
589        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
590
591        let mut test_evaluator = TestEvaluator {};
592
593        let result = visit(&mut test_evaluator, &bound_predicate);
594
595        assert!(result.unwrap());
596    }
597
598    #[test]
599    fn test_less_than_or_eq() {
600        let predicate = Predicate::Binary(BinaryExpression::new(
601            PredicateOperator::LessThanOrEq,
602            Reference::new("a"),
603            Datum::int(10),
604        ));
605        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
606
607        let mut test_evaluator = TestEvaluator {};
608
609        let result = visit(&mut test_evaluator, &bound_predicate);
610
611        assert!(!result.unwrap());
612    }
613
614    #[test]
615    fn test_greater_than() {
616        let predicate = Predicate::Binary(BinaryExpression::new(
617            PredicateOperator::GreaterThan,
618            Reference::new("a"),
619            Datum::int(10),
620        ));
621        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
622
623        let mut test_evaluator = TestEvaluator {};
624
625        let result = visit(&mut test_evaluator, &bound_predicate);
626
627        assert!(result.unwrap());
628    }
629
630    #[test]
631    fn test_greater_than_or_eq() {
632        let predicate = Predicate::Binary(BinaryExpression::new(
633            PredicateOperator::GreaterThanOrEq,
634            Reference::new("a"),
635            Datum::int(10),
636        ));
637        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
638
639        let mut test_evaluator = TestEvaluator {};
640
641        let result = visit(&mut test_evaluator, &bound_predicate);
642
643        assert!(!result.unwrap());
644    }
645
646    #[test]
647    fn test_eq() {
648        let predicate = Predicate::Binary(BinaryExpression::new(
649            PredicateOperator::Eq,
650            Reference::new("a"),
651            Datum::int(10),
652        ));
653        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
654
655        let mut test_evaluator = TestEvaluator {};
656
657        let result = visit(&mut test_evaluator, &bound_predicate);
658
659        assert!(result.unwrap());
660    }
661
662    #[test]
663    fn test_not_eq() {
664        let predicate = Predicate::Binary(BinaryExpression::new(
665            PredicateOperator::NotEq,
666            Reference::new("a"),
667            Datum::int(10),
668        ));
669        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
670
671        let mut test_evaluator = TestEvaluator {};
672
673        let result = visit(&mut test_evaluator, &bound_predicate);
674
675        assert!(!result.unwrap());
676    }
677
678    #[test]
679    fn test_starts_with() {
680        let predicate = Predicate::Binary(BinaryExpression::new(
681            PredicateOperator::StartsWith,
682            Reference::new("a"),
683            Datum::int(10),
684        ));
685        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
686
687        let mut test_evaluator = TestEvaluator {};
688
689        let result = visit(&mut test_evaluator, &bound_predicate);
690
691        assert!(result.unwrap());
692    }
693
694    #[test]
695    fn test_not_starts_with() {
696        let predicate = Predicate::Binary(BinaryExpression::new(
697            PredicateOperator::NotStartsWith,
698            Reference::new("a"),
699            Datum::int(10),
700        ));
701        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
702
703        let mut test_evaluator = TestEvaluator {};
704
705        let result = visit(&mut test_evaluator, &bound_predicate);
706
707        assert!(!result.unwrap());
708    }
709
710    #[test]
711    fn test_in() {
712        let predicate = Predicate::Set(SetExpression::new(
713            PredicateOperator::In,
714            Reference::new("a"),
715            FnvHashSet::from_iter(vec![Datum::int(1)]),
716        ));
717        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
718
719        let mut test_evaluator = TestEvaluator {};
720
721        let result = visit(&mut test_evaluator, &bound_predicate);
722
723        assert!(result.unwrap());
724    }
725
726    #[test]
727    fn test_not_in() {
728        let predicate = Predicate::Set(SetExpression::new(
729            PredicateOperator::NotIn,
730            Reference::new("a"),
731            FnvHashSet::from_iter(vec![Datum::int(1)]),
732        ));
733        let bound_predicate = predicate.bind(create_test_schema(), false).unwrap();
734
735        let mut test_evaluator = TestEvaluator {};
736
737        let result = visit(&mut test_evaluator, &bound_predicate);
738
739        assert!(!result.unwrap());
740    }
741}
iceberg/expr/visitors/bound_predicate_visitor.rs

iceberg/expr/visitors/
bound_predicate_visitor.rs
