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        expr.visit_mut_pre_post(
41            &mut |e| {
42                reduce_pre(e, column_types);
43                None
44            },
45            &mut |e| reduce_post(e, column_types, temp_storage),
46        );
47    }
48}
49
50/// Pre-order rewrites, applied before children are visited.
51///
52/// `IsNull` and `Not` need to fire pre-order: if they push themselves inward
53/// (e.g. `Not(Not(x)) → x`), the result is the new node at this position,
54/// which the visitor will then descend into for normal post-order handling.
55fn reduce_pre(e: &mut MirScalarExpr, column_types: &[ReprColumnType]) {
56    match e {
57        MirScalarExpr::CallUnary { func, expr } => match func {
58            UnaryFunc::IsNull(_) => {
59                if !expr.typ(column_types).nullable {
60                    *e = MirScalarExpr::literal_false();
61                } else if let Some(rewritten) = expr.decompose_is_null() {
62                    // Try to at least decompose IsNull into a disjunction of
63                    // simpler IsNull subexpressions.
64                    *e = rewritten;
65                }
66            }
67            UnaryFunc::Not(_) => match &mut **expr {
68                // Push down not expressions
69                // Two negates cancel each other out.
70                MirScalarExpr::CallUnary {
71                    expr: inner_expr,
72                    func: UnaryFunc::Not(_),
73                } => {
74                    *e = inner_expr.take();
75                }
76                // Transforms `NOT(a <op> b)` to `a negate(<op>) b` if a
77                // negation exists.
78                MirScalarExpr::CallBinary {
79                    expr1,
80                    expr2,
81                    func: bf,
82                } => {
83                    if let Some(negated) = bf.negate() {
84                        *e = MirScalarExpr::CallBinary {
85                            expr1: Box::new(expr1.take()),
86                            expr2: Box::new(expr2.take()),
87                            func: negated,
88                        };
89                    }
90                }
91                MirScalarExpr::CallVariadic { .. } => e.demorgans(),
92                _ => {}
93            },
94            _ => {}
95        },
96        _ => {}
97    }
98}
99
100/// Post-order rewrites, applied after children have been reduced.
101fn reduce_post(e: &mut MirScalarExpr, column_types: &[ReprColumnType], temp_storage: &RowArena) {
102    match e {
103        // Evaluate and pull up constants
104        MirScalarExpr::Column(_, _)
105        | MirScalarExpr::Literal(_, _)
106        | MirScalarExpr::CallUnmaterializable(_) => {}
107        MirScalarExpr::CallUnary { .. } => unary::reduce_call_unary(e, column_types, temp_storage),
108        MirScalarExpr::CallBinary { .. } => {
109            binary::reduce_call_binary(e, column_types, temp_storage)
110        }
111        MirScalarExpr::CallVariadic { .. } => {
112            variadic::reduce_call_variadic(e, column_types, temp_storage)
113        }
114        MirScalarExpr::If { .. } => if_then::reduce_if(e, column_types),
115    }
116}
mz_expr/scalar/reduce.rs

mz_expr/scalar/
reduce.rs
