mz_expr/scalar/
reduce.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10//! Rewrite-rule-driven simplification of `MirScalarExpr`.
11//!
12//! `reduce` repeatedly applies a fixed set of local rewrite rules to an
13//! expression until reaching a fixed point. The per-variant rules live in
14//! sibling modules (`unary`, `binary`, `variadic`, `if_then`); this file
15//! owns the fixed-point loop and the pre/post-pass dispatch.
16//!
17//! Behavioral parity with the prior imperative implementation is a goal:
18//! rule order and the pre-/post-pass split are preserved.
19
20use mz_repr::{ReprColumnType, RowArena};
21
22use crate::MirScalarExpr;
23use crate::scalar::func::UnaryFunc;
24use crate::visit::Visit;
25
26mod binary;
27mod if_then;
28mod unary;
29mod variadic;
30
31/// Reduce `expr` to a simpler equivalent form by repeatedly applying local
32/// rewrite rules until reaching a fixed point.
33pub fn reduce(expr: &mut MirScalarExpr, column_types: &[ReprColumnType]) {
34    let temp_storage = &RowArena::new();
35
36    // Simplifications run in a loop until `expr` no longer changes.
37    let mut old = MirScalarExpr::column(0);
38    while old != *expr {
39        old = expr.clone();
40        #[allow(deprecated)]
41        expr.visit_mut_pre_post_nolimit(
42            &mut |e| {
43                reduce_pre(e, column_types);
44                None
45            },
46            &mut |e| reduce_post(e, column_types, temp_storage),
47        );
48    }
49}
50
51/// Pre-order rewrites, applied before children are visited.
52///
53/// `IsNull` and `Not` need to fire pre-order: if they push themselves inward
54/// (e.g. `Not(Not(x)) → x`), the result is the new node at this position,
55/// which the visitor will then descend into for normal post-order handling.
56fn reduce_pre(e: &mut MirScalarExpr, column_types: &[ReprColumnType]) {
57    match e {
58        MirScalarExpr::CallUnary { func, expr } => match func {
59            UnaryFunc::IsNull(_) => {
60                if !expr.typ(column_types).nullable {
61                    *e = MirScalarExpr::literal_false();
62                } else if let Some(rewritten) = expr.decompose_is_null() {
63                    // Try to at least decompose IsNull into a disjunction of
64                    // simpler IsNull subexpressions.
65                    *e = rewritten;
66                }
67            }
68            UnaryFunc::Not(_) => match &mut **expr {
69                // Push down not expressions
70                // Two negates cancel each other out.
71                MirScalarExpr::CallUnary {
72                    expr: inner_expr,
73                    func: UnaryFunc::Not(_),
74                } => {
75                    *e = inner_expr.take();
76                }
77                // Transforms `NOT(a <op> b)` to `a negate(<op>) b` if a
78                // negation exists.
79                MirScalarExpr::CallBinary {
80                    expr1,
81                    expr2,
82                    func: bf,
83                } => {
84                    if let Some(negated) = bf.negate() {
85                        *e = MirScalarExpr::CallBinary {
86                            expr1: Box::new(expr1.take()),
87                            expr2: Box::new(expr2.take()),
88                            func: negated,
89                        };
90                    }
91                }
92                MirScalarExpr::CallVariadic { .. } => e.demorgans(),
93                _ => {}
94            },
95            _ => {}
96        },
97        _ => {}
98    }
99}
100
101/// Post-order rewrites, applied after children have been reduced.
102fn reduce_post(e: &mut MirScalarExpr, column_types: &[ReprColumnType], temp_storage: &RowArena) {
103    match e {
104        // Evaluate and pull up constants
105        MirScalarExpr::Column(_, _)
106        | MirScalarExpr::Literal(_, _)
107        | MirScalarExpr::CallUnmaterializable(_) => {}
108        MirScalarExpr::CallUnary { .. } => unary::reduce_call_unary(e, column_types, temp_storage),
109        MirScalarExpr::CallBinary { .. } => {
110            binary::reduce_call_binary(e, column_types, temp_storage)
111        }
112        MirScalarExpr::CallVariadic { .. } => {
113            variadic::reduce_call_variadic(e, column_types, temp_storage)
114        }
115        MirScalarExpr::If { .. } => if_then::reduce_if(e, column_types),
116    }
117}
mz_expr/scalar/reduce.rs

mz_expr/scalar/
reduce.rs
