mz_expr/
scalar.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
10use std::collections::{BTreeMap, BTreeSet};
11use std::ops::BitOrAssign;
12use std::sync::Arc;
13use std::{fmt, mem};
14
15use itertools::Itertools;
16use mz_lowertest::MzReflect;
17use mz_ore::cast::CastFrom;
18use mz_ore::collections::CollectionExt;
19use mz_ore::iter::IteratorExt;
20use mz_ore::stack::RecursionLimitError;
21use mz_ore::str::StrExt;
22use mz_ore::treat_as_equal::TreatAsEqual;
23use mz_ore::vec::swap_remove_multiple;
24use mz_pgrepr::TypeFromOidError;
25use mz_pgtz::timezone::TimezoneSpec;
26use mz_proto::{IntoRustIfSome, ProtoType, RustType, TryFromProtoError};
27use mz_repr::adt::array::InvalidArrayError;
28use mz_repr::adt::date::DateError;
29use mz_repr::adt::datetime::DateTimeUnits;
30use mz_repr::adt::range::InvalidRangeError;
31use mz_repr::adt::regex::Regex;
32use mz_repr::adt::timestamp::TimestampError;
33use mz_repr::strconv::{ParseError, ParseHexError};
34use mz_repr::{ColumnType, Datum, Row, RowArena, ScalarType, arb_datum};
35use proptest::prelude::*;
36use proptest_derive::Arbitrary;
37use serde::{Deserialize, Serialize};
38
39use crate::scalar::func::format::DateTimeFormat;
40use crate::scalar::func::{
41    BinaryFunc, UnaryFunc, UnmaterializableFunc, VariadicFunc, parse_timezone,
42    regexp_replace_parse_flags,
43};
44use crate::scalar::proto_eval_error::proto_incompatible_array_dimensions::ProtoDims;
45use crate::scalar::proto_mir_scalar_expr::*;
46use crate::visit::{Visit, VisitChildren};
47
48pub mod func;
49pub mod like_pattern;
50
51include!(concat!(env!("OUT_DIR"), "/mz_expr.scalar.rs"));
52
53#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize, MzReflect)]
54pub enum MirScalarExpr {
55    /// A column of the input row
56    Column(usize, TreatAsEqual<Option<Arc<str>>>),
57    /// A literal value.
58    /// (Stored as a row, because we can't own a Datum)
59    Literal(Result<Row, EvalError>, ColumnType),
60    /// A call to an unmaterializable function.
61    ///
62    /// These functions cannot be evaluated by `MirScalarExpr::eval`. They must
63    /// be transformed away by a higher layer.
64    CallUnmaterializable(UnmaterializableFunc),
65    /// A function call that takes one expression as an argument.
66    CallUnary {
67        func: UnaryFunc,
68        expr: Box<MirScalarExpr>,
69    },
70    /// A function call that takes two expressions as arguments.
71    CallBinary {
72        func: BinaryFunc,
73        expr1: Box<MirScalarExpr>,
74        expr2: Box<MirScalarExpr>,
75    },
76    /// A function call that takes an arbitrary number of arguments.
77    CallVariadic {
78        func: VariadicFunc,
79        exprs: Vec<MirScalarExpr>,
80    },
81    /// Conditionally evaluated expressions.
82    ///
83    /// It is important that `then` and `els` only be evaluated if
84    /// `cond` is true or not, respectively. This is the only way
85    /// users can guard execution (other logical operator do not
86    /// short-circuit) and we need to preserve that.
87    If {
88        cond: Box<MirScalarExpr>,
89        then: Box<MirScalarExpr>,
90        els: Box<MirScalarExpr>,
91    },
92}
93
94// We need a custom Debug because we don't want to show `None` for name information.
95// Sadly, the `derivative` crate doesn't support this use case.
96impl std::fmt::Debug for MirScalarExpr {
97    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
98        match self {
99            MirScalarExpr::Column(i, TreatAsEqual(Some(name))) => {
100                write!(f, "Column({i}, {name:?})")
101            }
102            MirScalarExpr::Column(i, TreatAsEqual(None)) => write!(f, "Column({i})"),
103            MirScalarExpr::Literal(lit, typ) => write!(f, "Literal({lit:?}, {typ:?})"),
104            MirScalarExpr::CallUnmaterializable(func) => {
105                write!(f, "CallUnmaterializable({func:?})")
106            }
107            MirScalarExpr::CallUnary { func, expr } => {
108                write!(f, "CallUnary({func:?}, {expr:?})")
109            }
110            MirScalarExpr::CallBinary { func, expr1, expr2 } => {
111                write!(f, "CallBinary({func:?}, {expr1:?}, {expr2:?})")
112            }
113            MirScalarExpr::CallVariadic { func, exprs } => {
114                write!(f, "CallVariadic({func:?}, {exprs:?})")
115            }
116            MirScalarExpr::If { cond, then, els } => {
117                write!(f, "If({cond:?}, {then:?}, {els:?})")
118            }
119        }
120    }
121}
122
123impl Arbitrary for MirScalarExpr {
124    type Parameters = ();
125    type Strategy = BoxedStrategy<MirScalarExpr>;
126
127    fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
128        let leaf = prop::strategy::Union::new(vec![
129            (0..10_usize).prop_map(MirScalarExpr::column).boxed(),
130            (arb_datum(), any::<ScalarType>())
131                .prop_map(|(datum, typ)| MirScalarExpr::literal(Ok((&datum).into()), typ))
132                .boxed(),
133            (any::<EvalError>(), any::<ScalarType>())
134                .prop_map(|(err, typ)| MirScalarExpr::literal(Err(err), typ))
135                .boxed(),
136            any::<UnmaterializableFunc>()
137                .prop_map(MirScalarExpr::CallUnmaterializable)
138                .boxed(),
139        ]);
140        leaf.prop_recursive(3, 6, 7, |inner| {
141            prop::strategy::Union::new(vec![
142                (
143                    any::<VariadicFunc>(),
144                    prop::collection::vec(inner.clone(), 1..5),
145                )
146                    .prop_map(|(func, exprs)| MirScalarExpr::CallVariadic { func, exprs })
147                    .boxed(),
148                (any::<BinaryFunc>(), inner.clone(), inner.clone())
149                    .prop_map(|(func, expr1, expr2)| MirScalarExpr::CallBinary {
150                        func,
151                        expr1: Box::new(expr1),
152                        expr2: Box::new(expr2),
153                    })
154                    .boxed(),
155                (inner.clone(), inner.clone(), inner.clone())
156                    .prop_map(|(cond, then, els)| MirScalarExpr::If {
157                        cond: Box::new(cond),
158                        then: Box::new(then),
159                        els: Box::new(els),
160                    })
161                    .boxed(),
162                (any::<UnaryFunc>(), inner)
163                    .prop_map(|(func, expr)| MirScalarExpr::CallUnary {
164                        func,
165                        expr: Box::new(expr),
166                    })
167                    .boxed(),
168            ])
169        })
170        .boxed()
171    }
172}
173
174impl RustType<ProtoMirScalarExpr> for MirScalarExpr {
175    fn into_proto(&self) -> ProtoMirScalarExpr {
176        use proto_mir_scalar_expr::Kind::*;
177        ProtoMirScalarExpr {
178            kind: Some(match self {
179                MirScalarExpr::Column(index, name) => Column(ProtoColumn {
180                    index: index.into_proto(),
181                    name: name.0.as_ref().map(ToString::to_string),
182                }),
183                MirScalarExpr::Literal(lit, typ) => Literal(ProtoLiteral {
184                    lit: Some(lit.into_proto()),
185                    typ: Some(typ.into_proto()),
186                }),
187                MirScalarExpr::CallUnmaterializable(func) => {
188                    CallUnmaterializable(func.into_proto())
189                }
190                MirScalarExpr::CallUnary { func, expr } => CallUnary(Box::new(ProtoCallUnary {
191                    func: Some(Box::new(func.into_proto())),
192                    expr: Some(expr.into_proto()),
193                })),
194                MirScalarExpr::CallBinary { func, expr1, expr2 } => {
195                    CallBinary(Box::new(ProtoCallBinary {
196                        func: Some(func.into_proto()),
197                        expr1: Some(expr1.into_proto()),
198                        expr2: Some(expr2.into_proto()),
199                    }))
200                }
201                MirScalarExpr::CallVariadic { func, exprs } => CallVariadic(ProtoCallVariadic {
202                    func: Some(func.into_proto()),
203                    exprs: exprs.into_proto(),
204                }),
205                MirScalarExpr::If { cond, then, els } => If(Box::new(ProtoIf {
206                    cond: Some(cond.into_proto()),
207                    then: Some(then.into_proto()),
208                    els: Some(els.into_proto()),
209                })),
210            }),
211        }
212    }
213
214    fn from_proto(proto: ProtoMirScalarExpr) -> Result<Self, TryFromProtoError> {
215        use proto_mir_scalar_expr::Kind::*;
216        let kind = proto
217            .kind
218            .ok_or_else(|| TryFromProtoError::missing_field("ProtoMirScalarExpr::kind"))?;
219        Ok(match kind {
220            Column(ProtoColumn { index, name }) => {
221                let index = usize::from_proto(index)?;
222                match name {
223                    Some(name) => MirScalarExpr::named_column(index, name.into()),
224                    None => MirScalarExpr::column(index),
225                }
226            }
227            Literal(ProtoLiteral { lit, typ }) => MirScalarExpr::Literal(
228                lit.into_rust_if_some("ProtoLiteral::lit")?,
229                typ.into_rust_if_some("ProtoLiteral::typ")?,
230            ),
231            CallUnmaterializable(func) => MirScalarExpr::CallUnmaterializable(func.into_rust()?),
232            CallUnary(call_unary) => MirScalarExpr::CallUnary {
233                func: call_unary.func.into_rust_if_some("ProtoCallUnary::func")?,
234                expr: call_unary.expr.into_rust_if_some("ProtoCallUnary::expr")?,
235            },
236            CallBinary(call_binary) => MirScalarExpr::CallBinary {
237                func: call_binary
238                    .func
239                    .into_rust_if_some("ProtoCallBinary::func")?,
240                expr1: call_binary
241                    .expr1
242                    .into_rust_if_some("ProtoCallBinary::expr1")?,
243                expr2: call_binary
244                    .expr2
245                    .into_rust_if_some("ProtoCallBinary::expr2")?,
246            },
247            CallVariadic(ProtoCallVariadic { func, exprs }) => MirScalarExpr::CallVariadic {
248                func: func.into_rust_if_some("ProtoCallVariadic::func")?,
249                exprs: exprs.into_rust()?,
250            },
251            If(if_struct) => MirScalarExpr::If {
252                cond: if_struct.cond.into_rust_if_some("ProtoIf::cond")?,
253                then: if_struct.then.into_rust_if_some("ProtoIf::then")?,
254                els: if_struct.els.into_rust_if_some("ProtoIf::els")?,
255            },
256        })
257    }
258}
259
260impl RustType<proto_literal::ProtoLiteralData> for Result<Row, EvalError> {
261    fn into_proto(&self) -> proto_literal::ProtoLiteralData {
262        use proto_literal::proto_literal_data::Result::*;
263        proto_literal::ProtoLiteralData {
264            result: Some(match self {
265                Result::Ok(row) => Ok(row.into_proto()),
266                Result::Err(err) => Err(err.into_proto()),
267            }),
268        }
269    }
270
271    fn from_proto(proto: proto_literal::ProtoLiteralData) -> Result<Self, TryFromProtoError> {
272        use proto_literal::proto_literal_data::Result::*;
273        match proto.result {
274            Some(Ok(row)) => Result::Ok(Result::Ok(
275                (&row)
276                    .try_into()
277                    .map_err(TryFromProtoError::RowConversionError)?,
278            )),
279            Some(Err(err)) => Result::Ok(Result::Err(err.into_rust()?)),
280            None => Result::Err(TryFromProtoError::missing_field("ProtoLiteralData::result")),
281        }
282    }
283}
284
285impl MirScalarExpr {
286    pub fn columns(is: &[usize]) -> Vec<MirScalarExpr> {
287        is.iter().map(|i| MirScalarExpr::column(*i)).collect()
288    }
289
290    pub fn column(column: usize) -> Self {
291        MirScalarExpr::Column(column, TreatAsEqual(None))
292    }
293
294    pub fn named_column(column: usize, name: Arc<str>) -> Self {
295        MirScalarExpr::Column(column, TreatAsEqual(Some(name)))
296    }
297
298    pub fn literal(res: Result<Datum, EvalError>, typ: ScalarType) -> Self {
299        let typ = typ.nullable(matches!(res, Ok(Datum::Null)));
300        let row = res.map(|datum| Row::pack_slice(&[datum]));
301        MirScalarExpr::Literal(row, typ)
302    }
303
304    pub fn literal_ok(datum: Datum, typ: ScalarType) -> Self {
305        MirScalarExpr::literal(Ok(datum), typ)
306    }
307
308    pub fn literal_null(typ: ScalarType) -> Self {
309        MirScalarExpr::literal_ok(Datum::Null, typ)
310    }
311
312    pub fn literal_false() -> Self {
313        MirScalarExpr::literal_ok(Datum::False, ScalarType::Bool)
314    }
315
316    pub fn literal_true() -> Self {
317        MirScalarExpr::literal_ok(Datum::True, ScalarType::Bool)
318    }
319
320    pub fn call_unary(self, func: UnaryFunc) -> Self {
321        MirScalarExpr::CallUnary {
322            func,
323            expr: Box::new(self),
324        }
325    }
326
327    pub fn call_binary(self, other: Self, func: BinaryFunc) -> Self {
328        MirScalarExpr::CallBinary {
329            func,
330            expr1: Box::new(self),
331            expr2: Box::new(other),
332        }
333    }
334
335    pub fn if_then_else(self, t: Self, f: Self) -> Self {
336        MirScalarExpr::If {
337            cond: Box::new(self),
338            then: Box::new(t),
339            els: Box::new(f),
340        }
341    }
342
343    pub fn or(self, other: Self) -> Self {
344        MirScalarExpr::CallVariadic {
345            func: VariadicFunc::Or,
346            exprs: vec![self, other],
347        }
348    }
349
350    pub fn and(self, other: Self) -> Self {
351        MirScalarExpr::CallVariadic {
352            func: VariadicFunc::And,
353            exprs: vec![self, other],
354        }
355    }
356
357    pub fn not(self) -> Self {
358        self.call_unary(UnaryFunc::Not(func::Not))
359    }
360
361    pub fn call_is_null(self) -> Self {
362        self.call_unary(UnaryFunc::IsNull(func::IsNull))
363    }
364
365    /// Match AND or OR on self and get the args. If no match, then interpret self as if it were
366    /// wrapped in a 1-arg AND/OR.
367    pub fn and_or_args(&self, func_to_match: VariadicFunc) -> Vec<MirScalarExpr> {
368        assert!(func_to_match == VariadicFunc::Or || func_to_match == VariadicFunc::And);
369        match self {
370            MirScalarExpr::CallVariadic { func, exprs } if *func == func_to_match => exprs.clone(),
371            _ => vec![self.clone()],
372        }
373    }
374
375    /// Try to match a literal equality involving the given expression on one side.
376    /// Return the (non-null) literal and a bool that indicates whether an inversion was needed.
377    ///
378    /// More specifically:
379    /// If `self` is an equality with a `null` literal on any side, then the match fails!
380    /// Otherwise: for a given `expr`, if `self` is `<expr> = <literal>` or `<literal> = <expr>`
381    /// then return `Some((<literal>, false))`. In addition to just trying to match `<expr>` as it
382    /// is, we also try to remove an invertible function call (such as a cast). If the match
383    /// succeeds with the inversion, then return `Some((<inverted-literal>, true))`. For more
384    /// details on the inversion, see `invert_casts_on_expr_eq_literal_inner`.
385    pub fn expr_eq_literal(&self, expr: &MirScalarExpr) -> Option<(Row, bool)> {
386        if let MirScalarExpr::CallBinary {
387            func: BinaryFunc::Eq,
388            expr1,
389            expr2,
390        } = self
391        {
392            if expr1.is_literal_null() || expr2.is_literal_null() {
393                return None;
394            }
395            if let Some(Ok(lit)) = expr1.as_literal_owned() {
396                return Self::expr_eq_literal_inner(expr, lit, expr1, expr2);
397            }
398            if let Some(Ok(lit)) = expr2.as_literal_owned() {
399                return Self::expr_eq_literal_inner(expr, lit, expr2, expr1);
400            }
401        }
402        None
403    }
404
405    fn expr_eq_literal_inner(
406        expr_to_match: &MirScalarExpr,
407        literal: Row,
408        literal_expr: &MirScalarExpr,
409        other_side: &MirScalarExpr,
410    ) -> Option<(Row, bool)> {
411        if other_side == expr_to_match {
412            return Some((literal, false));
413        } else {
414            // expr didn't exactly match. See if we can match it by inverse-casting.
415            let (cast_removed, inv_cast_lit) =
416                Self::invert_casts_on_expr_eq_literal_inner(other_side, literal_expr);
417            if &cast_removed == expr_to_match {
418                if let Some(Ok(inv_cast_lit_row)) = inv_cast_lit.as_literal_owned() {
419                    return Some((inv_cast_lit_row, true));
420                }
421            }
422        }
423        None
424    }
425
426    /// If `self` is `<expr> = <literal>` or `<literal> = <expr>` then
427    /// return `<expr>`. It also tries to remove a cast (or other invertible function call) from
428    /// `<expr>` before returning it, see `invert_casts_on_expr_eq_literal_inner`.
429    pub fn any_expr_eq_literal(&self) -> Option<MirScalarExpr> {
430        if let MirScalarExpr::CallBinary {
431            func: BinaryFunc::Eq,
432            expr1,
433            expr2,
434        } = self
435        {
436            if expr1.is_literal() {
437                let (expr, _literal) = Self::invert_casts_on_expr_eq_literal_inner(expr2, expr1);
438                return Some(expr);
439            }
440            if expr2.is_literal() {
441                let (expr, _literal) = Self::invert_casts_on_expr_eq_literal_inner(expr1, expr2);
442                return Some(expr);
443            }
444        }
445        None
446    }
447
448    /// If the given `MirScalarExpr` is a literal equality where one side is an invertible function
449    /// call, then calls the inverse function on both sides of the equality and returns the modified
450    /// version of the given `MirScalarExpr`. Otherwise, it returns the original expression.
451    /// For more details, see `invert_casts_on_expr_eq_literal_inner`.
452    pub fn invert_casts_on_expr_eq_literal(&self) -> MirScalarExpr {
453        if let MirScalarExpr::CallBinary {
454            func: BinaryFunc::Eq,
455            expr1,
456            expr2,
457        } = self
458        {
459            if expr1.is_literal() {
460                let (expr, literal) = Self::invert_casts_on_expr_eq_literal_inner(expr2, expr1);
461                return MirScalarExpr::CallBinary {
462                    func: BinaryFunc::Eq,
463                    expr1: Box::new(literal),
464                    expr2: Box::new(expr),
465                };
466            }
467            if expr2.is_literal() {
468                let (expr, literal) = Self::invert_casts_on_expr_eq_literal_inner(expr1, expr2);
469                return MirScalarExpr::CallBinary {
470                    func: BinaryFunc::Eq,
471                    expr1: Box::new(literal),
472                    expr2: Box::new(expr),
473                };
474            }
475            // Note: The above return statements should be consistent in whether they put the
476            // literal in expr1 or expr2, for the deduplication in CanonicalizeMfp to work.
477        }
478        self.clone()
479    }
480
481    /// Given an `<expr>` and a `<literal>` that were taken out from `<expr> = <literal>` or
482    /// `<literal> = <expr>`, it tries to simplify the equality by applying the inverse function of
483    /// the outermost function call of `<expr>` (if exists):
484    ///
485    /// `<literal> = func(<inner_expr>)`, where `func` is invertible
486    ///  -->
487    /// `<func^-1(literal)> = <inner_expr>`
488    /// if `func^-1(literal)` doesn't error out, and both `func` and `func^-1` preserve uniqueness.
489    ///
490    /// The return value is the `<inner_expr>` and the literal value that we get by applying the
491    /// inverse function.
492    fn invert_casts_on_expr_eq_literal_inner(
493        expr: &MirScalarExpr,
494        literal: &MirScalarExpr,
495    ) -> (MirScalarExpr, MirScalarExpr) {
496        assert!(matches!(literal, MirScalarExpr::Literal(..)));
497
498        let temp_storage = &RowArena::new();
499        let eval = |e: &MirScalarExpr| {
500            MirScalarExpr::literal(e.eval(&[], temp_storage), e.typ(&[]).scalar_type)
501        };
502
503        if let MirScalarExpr::CallUnary {
504            func,
505            expr: inner_expr,
506        } = expr
507        {
508            if let Some(inverse_func) = func.inverse() {
509                // We don't want to remove a function call that doesn't preserve uniqueness, e.g.,
510                // if `f` is a float, we don't want to inverse-cast `f::INT = 0`, because the
511                // inserted int-to-float cast wouldn't be able to invert the rounding.
512                // Also, we don't want to insert a function call that doesn't preserve
513                // uniqueness. E.g., if `a` has an integer type, we don't want to do
514                // a surprise rounding for `WHERE a = 3.14`.
515                if func.preserves_uniqueness() && inverse_func.preserves_uniqueness() {
516                    let lit_inv = eval(&MirScalarExpr::CallUnary {
517                        func: inverse_func,
518                        expr: Box::new(literal.clone()),
519                    });
520                    // The evaluation can error out, e.g., when casting a too large int32 to int16.
521                    // This case is handled by `impossible_literal_equality_because_types`.
522                    if !lit_inv.is_literal_err() {
523                        return (*inner_expr.clone(), lit_inv);
524                    }
525                }
526            }
527        }
528        (expr.clone(), literal.clone())
529    }
530
531    /// Tries to remove a cast (or other invertible function) in the same way as
532    /// `invert_casts_on_expr_eq_literal`, but if calling the inverse function fails on the literal,
533    /// then it deems the equality to be impossible. For example if `a` is a smallint column, then
534    /// it catches `a::integer = 1000000` to be an always false predicate (where the `::integer`
535    /// could have been inserted implicitly).
536    pub fn impossible_literal_equality_because_types(&self) -> bool {
537        if let MirScalarExpr::CallBinary {
538            func: BinaryFunc::Eq,
539            expr1,
540            expr2,
541        } = self
542        {
543            if expr1.is_literal() {
544                return Self::impossible_literal_equality_because_types_inner(expr1, expr2);
545            }
546            if expr2.is_literal() {
547                return Self::impossible_literal_equality_because_types_inner(expr2, expr1);
548            }
549        }
550        false
551    }
552
553    fn impossible_literal_equality_because_types_inner(
554        literal: &MirScalarExpr,
555        other_side: &MirScalarExpr,
556    ) -> bool {
557        assert!(matches!(literal, MirScalarExpr::Literal(..)));
558
559        let temp_storage = &RowArena::new();
560        let eval = |e: &MirScalarExpr| {
561            MirScalarExpr::literal(e.eval(&[], temp_storage), e.typ(&[]).scalar_type)
562        };
563
564        if let MirScalarExpr::CallUnary { func, .. } = other_side {
565            if let Some(inverse_func) = func.inverse() {
566                if inverse_func.preserves_uniqueness()
567                    && eval(&MirScalarExpr::CallUnary {
568                        func: inverse_func,
569                        expr: Box::new(literal.clone()),
570                    })
571                    .is_literal_err()
572                {
573                    return true;
574                }
575            }
576        }
577
578        false
579    }
580
581    /// Determines if `self` is
582    /// `<expr> < <literal>` or
583    /// `<expr> > <literal>` or
584    /// `<literal> < <expr>` or
585    /// `<literal> > <expr>` or
586    /// `<expr> <= <literal>` or
587    /// `<expr> >= <literal>` or
588    /// `<literal> <= <expr>` or
589    /// `<literal> >= <expr>`.
590    pub fn any_expr_ineq_literal(&self) -> bool {
591        match self {
592            MirScalarExpr::CallBinary {
593                func: BinaryFunc::Lt | BinaryFunc::Lte | BinaryFunc::Gt | BinaryFunc::Gte,
594                expr1,
595                expr2,
596            } => expr1.is_literal() || expr2.is_literal(),
597            _ => false,
598        }
599    }
600
601    /// Rewrites column indices with their value in `permutation`.
602    ///
603    /// This method is applicable even when `permutation` is not a
604    /// strict permutation, and it only needs to have entries for
605    /// each column referenced in `self`.
606    pub fn permute(&mut self, permutation: &[usize]) {
607        self.visit_columns(|c| *c = permutation[*c]);
608    }
609
610    /// Rewrites column indices with their value in `permutation`.
611    ///
612    /// This method is applicable even when `permutation` is not a
613    /// strict permutation, and it only needs to have entries for
614    /// each column referenced in `self`.
615    pub fn permute_map(&mut self, permutation: &BTreeMap<usize, usize>) {
616        self.visit_columns(|c| *c = permutation[c]);
617    }
618
619    /// Visits each column reference and applies `action` to the column.
620    ///
621    /// Useful for remapping columns, or for collecting expression support.
622    pub fn visit_columns<F>(&mut self, mut action: F)
623    where
624        F: FnMut(&mut usize),
625    {
626        self.visit_pre_mut(|e| {
627            if let MirScalarExpr::Column(col, _) = e {
628                action(col);
629            }
630        });
631    }
632
633    pub fn support(&self) -> BTreeSet<usize> {
634        let mut support = BTreeSet::new();
635        self.support_into(&mut support);
636        support
637    }
638
639    pub fn support_into(&self, support: &mut BTreeSet<usize>) {
640        self.visit_pre(|e| {
641            if let MirScalarExpr::Column(i, _) = e {
642                support.insert(*i);
643            }
644        });
645    }
646
647    pub fn take(&mut self) -> Self {
648        mem::replace(self, MirScalarExpr::literal_null(ScalarType::String))
649    }
650
651    /// If the expression is a literal, this returns the literal's Datum or the literal's EvalError.
652    /// Otherwise, it returns None.
653    pub fn as_literal(&self) -> Option<Result<Datum<'_>, &EvalError>> {
654        if let MirScalarExpr::Literal(lit, _column_type) = self {
655            Some(lit.as_ref().map(|row| row.unpack_first()))
656        } else {
657            None
658        }
659    }
660
661    /// Flattens the two failure modes of `as_literal` into one layer of Option: returns the
662    /// literal's Datum only if the expression is a literal, and it's not a literal error.
663    pub fn as_literal_non_error(&self) -> Option<Datum<'_>> {
664        self.as_literal().map(|eval_err| eval_err.ok()).flatten()
665    }
666
667    pub fn as_literal_owned(&self) -> Option<Result<Row, EvalError>> {
668        if let MirScalarExpr::Literal(lit, _column_type) = self {
669            Some(lit.clone())
670        } else {
671            None
672        }
673    }
674
675    pub fn as_literal_str(&self) -> Option<&str> {
676        match self.as_literal() {
677            Some(Ok(Datum::String(s))) => Some(s),
678            _ => None,
679        }
680    }
681
682    pub fn as_literal_int64(&self) -> Option<i64> {
683        match self.as_literal() {
684            Some(Ok(Datum::Int64(i))) => Some(i),
685            _ => None,
686        }
687    }
688
689    pub fn as_literal_err(&self) -> Option<&EvalError> {
690        self.as_literal().and_then(|lit| lit.err())
691    }
692
693    pub fn is_literal(&self) -> bool {
694        matches!(self, MirScalarExpr::Literal(_, _))
695    }
696
697    pub fn is_literal_true(&self) -> bool {
698        Some(Ok(Datum::True)) == self.as_literal()
699    }
700
701    pub fn is_literal_false(&self) -> bool {
702        Some(Ok(Datum::False)) == self.as_literal()
703    }
704
705    pub fn is_literal_null(&self) -> bool {
706        Some(Ok(Datum::Null)) == self.as_literal()
707    }
708
709    pub fn is_literal_ok(&self) -> bool {
710        matches!(self, MirScalarExpr::Literal(Ok(_), _typ))
711    }
712
713    pub fn is_literal_err(&self) -> bool {
714        matches!(self, MirScalarExpr::Literal(Err(_), _typ))
715    }
716
717    pub fn is_column(&self) -> bool {
718        matches!(self, MirScalarExpr::Column(_col, _name))
719    }
720
721    pub fn is_error_if_null(&self) -> bool {
722        matches!(
723            self,
724            Self::CallVariadic {
725                func: VariadicFunc::ErrorIfNull,
726                ..
727            }
728        )
729    }
730
731    #[deprecated = "Use `might_error` instead"]
732    pub fn contains_error_if_null(&self) -> bool {
733        let mut worklist = vec![self];
734        while let Some(expr) = worklist.pop() {
735            if expr.is_error_if_null() {
736                return true;
737            }
738            worklist.extend(expr.children());
739        }
740        false
741    }
742
743    pub fn contains_err(&self) -> bool {
744        let mut worklist = vec![self];
745        while let Some(expr) = worklist.pop() {
746            if expr.is_literal_err() {
747                return true;
748            }
749            worklist.extend(expr.children());
750        }
751        false
752    }
753
754    /// A very crude approximation for scalar expressions that might produce an
755    /// error.
756    ///
757    /// Currently, this is restricted only to expressions that either contain a
758    /// literal error or a [`VariadicFunc::ErrorIfNull`] call.
759    pub fn might_error(&self) -> bool {
760        let mut worklist = vec![self];
761        while let Some(expr) = worklist.pop() {
762            if expr.is_literal_err() || expr.is_error_if_null() {
763                return true;
764            }
765            worklist.extend(expr.children());
766        }
767        false
768    }
769
770    /// If self is a column, return the column index, otherwise `None`.
771    pub fn as_column(&self) -> Option<usize> {
772        if let MirScalarExpr::Column(c, _) = self {
773            Some(*c)
774        } else {
775            None
776        }
777    }
778
779    /// Reduces a complex expression where possible.
780    ///
781    /// This function uses nullability information present in `column_types`,
782    /// and the result may only continue to be a correct transformation as
783    /// long as this information continues to hold (nullability may not hold
784    /// as expressions migrate around).
785    ///
786    /// (If you'd like to not use nullability information here, then you can
787    /// tweak the nullabilities in `column_types` before passing it to this
788    /// function, see e.g. in `EquivalenceClasses::minimize`.)
789    ///
790    /// Also performs partial canonicalization on the expression.
791    ///
792    /// ```rust
793    /// use mz_expr::MirScalarExpr;
794    /// use mz_repr::{ColumnType, Datum, ScalarType};
795    ///
796    /// let expr_0 = MirScalarExpr::column(0);
797    /// let expr_t = MirScalarExpr::literal_true();
798    /// let expr_f = MirScalarExpr::literal_false();
799    ///
800    /// let mut test =
801    /// expr_t
802    ///     .clone()
803    ///     .and(expr_f.clone())
804    ///     .if_then_else(expr_0, expr_t.clone());
805    ///
806    /// let input_type = vec![ScalarType::Int32.nullable(false)];
807    /// test.reduce(&input_type);
808    /// assert_eq!(test, expr_t);
809    /// ```
810    pub fn reduce(&mut self, column_types: &[ColumnType]) {
811        let temp_storage = &RowArena::new();
812        let eval = |e: &MirScalarExpr| {
813            MirScalarExpr::literal(e.eval(&[], temp_storage), e.typ(column_types).scalar_type)
814        };
815
816        // Simplifications run in a loop until `self` no longer changes.
817        let mut old_self = MirScalarExpr::column(0);
818        while old_self != *self {
819            old_self = self.clone();
820            #[allow(deprecated)]
821            self.visit_mut_pre_post_nolimit(
822                &mut |e| {
823                    match e {
824                        MirScalarExpr::CallUnary { func, expr } => {
825                            if *func == UnaryFunc::IsNull(func::IsNull) {
826                                if !expr.typ(column_types).nullable {
827                                    *e = MirScalarExpr::literal_false();
828                                } else {
829                                    // Try to at least decompose IsNull into a disjunction
830                                    // of simpler IsNull subexpressions.
831                                    if let Some(expr) = expr.decompose_is_null() {
832                                        *e = expr
833                                    }
834                                }
835                            } else if *func == UnaryFunc::Not(func::Not) {
836                                // Push down not expressions
837                                match &mut **expr {
838                                    // Two negates cancel each other out.
839                                    MirScalarExpr::CallUnary {
840                                        expr: inner_expr,
841                                        func: UnaryFunc::Not(func::Not),
842                                    } => *e = inner_expr.take(),
843                                    // Transforms `NOT(a <op> b)` to `a negate(<op>) b`
844                                    // if a negation exists.
845                                    MirScalarExpr::CallBinary { expr1, expr2, func } => {
846                                        if let Some(negated_func) = func.negate() {
847                                            *e = MirScalarExpr::CallBinary {
848                                                expr1: Box::new(expr1.take()),
849                                                expr2: Box::new(expr2.take()),
850                                                func: negated_func,
851                                            }
852                                        }
853                                    }
854                                    MirScalarExpr::CallVariadic { .. } => {
855                                        e.demorgans();
856                                    }
857                                    _ => {}
858                                }
859                            }
860                        }
861                        _ => {}
862                    };
863                    None
864                },
865                &mut |e| match e {
866                    // Evaluate and pull up constants
867                    MirScalarExpr::Column(_, _)
868                    | MirScalarExpr::Literal(_, _)
869                    | MirScalarExpr::CallUnmaterializable(_) => (),
870                    MirScalarExpr::CallUnary { func, expr } => {
871                        if expr.is_literal() && *func != UnaryFunc::Panic(func::Panic) {
872                            *e = eval(e);
873                        } else if let UnaryFunc::RecordGet(func::RecordGet(i)) = *func {
874                            if let MirScalarExpr::CallVariadic {
875                                func: VariadicFunc::RecordCreate { .. },
876                                exprs,
877                            } = &mut **expr
878                            {
879                                *e = exprs.swap_remove(i);
880                            }
881                        }
882                    }
883                    MirScalarExpr::CallBinary { func, expr1, expr2 } => {
884                        if expr1.is_literal() && expr2.is_literal() {
885                            *e = eval(e);
886                        } else if (expr1.is_literal_null() || expr2.is_literal_null())
887                            && func.propagates_nulls()
888                        {
889                            *e = MirScalarExpr::literal_null(e.typ(column_types).scalar_type);
890                        } else if let Some(err) = expr1.as_literal_err() {
891                            *e = MirScalarExpr::literal(
892                                Err(err.clone()),
893                                e.typ(column_types).scalar_type,
894                            );
895                        } else if let Some(err) = expr2.as_literal_err() {
896                            *e = MirScalarExpr::literal(
897                                Err(err.clone()),
898                                e.typ(column_types).scalar_type,
899                            );
900                        } else if let BinaryFunc::IsLikeMatch { case_insensitive } = func {
901                            if expr2.is_literal() {
902                                // We can at least precompile the regex.
903                                let pattern = expr2.as_literal_str().unwrap();
904                                *e = match like_pattern::compile(pattern, *case_insensitive) {
905                                    Ok(matcher) => expr1.take().call_unary(UnaryFunc::IsLikeMatch(
906                                        func::IsLikeMatch(matcher),
907                                    )),
908                                    Err(err) => MirScalarExpr::literal(
909                                        Err(err),
910                                        e.typ(column_types).scalar_type,
911                                    ),
912                                };
913                            }
914                        } else if let BinaryFunc::IsRegexpMatch { case_insensitive } = func {
915                            if let MirScalarExpr::Literal(Ok(row), _) = &**expr2 {
916                                *e = match Regex::new(
917                                    row.unpack_first().unwrap_str(),
918                                    *case_insensitive,
919                                ) {
920                                    Ok(regex) => expr1.take().call_unary(UnaryFunc::IsRegexpMatch(
921                                        func::IsRegexpMatch(regex),
922                                    )),
923                                    Err(err) => MirScalarExpr::literal(
924                                        Err(err.into()),
925                                        e.typ(column_types).scalar_type,
926                                    ),
927                                };
928                            }
929                        } else if *func == BinaryFunc::ExtractInterval && expr1.is_literal() {
930                            let units = expr1.as_literal_str().unwrap();
931                            *e = match units.parse::<DateTimeUnits>() {
932                                Ok(units) => MirScalarExpr::CallUnary {
933                                    func: UnaryFunc::ExtractInterval(func::ExtractInterval(units)),
934                                    expr: Box::new(expr2.take()),
935                                },
936                                Err(_) => MirScalarExpr::literal(
937                                    Err(EvalError::UnknownUnits(units.into())),
938                                    e.typ(column_types).scalar_type,
939                                ),
940                            }
941                        } else if *func == BinaryFunc::ExtractTime && expr1.is_literal() {
942                            let units = expr1.as_literal_str().unwrap();
943                            *e = match units.parse::<DateTimeUnits>() {
944                                Ok(units) => MirScalarExpr::CallUnary {
945                                    func: UnaryFunc::ExtractTime(func::ExtractTime(units)),
946                                    expr: Box::new(expr2.take()),
947                                },
948                                Err(_) => MirScalarExpr::literal(
949                                    Err(EvalError::UnknownUnits(units.into())),
950                                    e.typ(column_types).scalar_type,
951                                ),
952                            }
953                        } else if *func == BinaryFunc::ExtractTimestamp && expr1.is_literal() {
954                            let units = expr1.as_literal_str().unwrap();
955                            *e = match units.parse::<DateTimeUnits>() {
956                                Ok(units) => MirScalarExpr::CallUnary {
957                                    func: UnaryFunc::ExtractTimestamp(func::ExtractTimestamp(
958                                        units,
959                                    )),
960                                    expr: Box::new(expr2.take()),
961                                },
962                                Err(_) => MirScalarExpr::literal(
963                                    Err(EvalError::UnknownUnits(units.into())),
964                                    e.typ(column_types).scalar_type,
965                                ),
966                            }
967                        } else if *func == BinaryFunc::ExtractTimestampTz && expr1.is_literal() {
968                            let units = expr1.as_literal_str().unwrap();
969                            *e = match units.parse::<DateTimeUnits>() {
970                                Ok(units) => MirScalarExpr::CallUnary {
971                                    func: UnaryFunc::ExtractTimestampTz(func::ExtractTimestampTz(
972                                        units,
973                                    )),
974                                    expr: Box::new(expr2.take()),
975                                },
976                                Err(_) => MirScalarExpr::literal(
977                                    Err(EvalError::UnknownUnits(units.into())),
978                                    e.typ(column_types).scalar_type,
979                                ),
980                            }
981                        } else if *func == BinaryFunc::ExtractDate && expr1.is_literal() {
982                            let units = expr1.as_literal_str().unwrap();
983                            *e = match units.parse::<DateTimeUnits>() {
984                                Ok(units) => MirScalarExpr::CallUnary {
985                                    func: UnaryFunc::ExtractDate(func::ExtractDate(units)),
986                                    expr: Box::new(expr2.take()),
987                                },
988                                Err(_) => MirScalarExpr::literal(
989                                    Err(EvalError::UnknownUnits(units.into())),
990                                    e.typ(column_types).scalar_type,
991                                ),
992                            }
993                        } else if *func == BinaryFunc::DatePartInterval && expr1.is_literal() {
994                            let units = expr1.as_literal_str().unwrap();
995                            *e = match units.parse::<DateTimeUnits>() {
996                                Ok(units) => MirScalarExpr::CallUnary {
997                                    func: UnaryFunc::DatePartInterval(func::DatePartInterval(
998                                        units,
999                                    )),
1000                                    expr: Box::new(expr2.take()),
1001                                },
1002                                Err(_) => MirScalarExpr::literal(
1003                                    Err(EvalError::UnknownUnits(units.into())),
1004                                    e.typ(column_types).scalar_type,
1005                                ),
1006                            }
1007                        } else if *func == BinaryFunc::DatePartTime && expr1.is_literal() {
1008                            let units = expr1.as_literal_str().unwrap();
1009                            *e = match units.parse::<DateTimeUnits>() {
1010                                Ok(units) => MirScalarExpr::CallUnary {
1011                                    func: UnaryFunc::DatePartTime(func::DatePartTime(units)),
1012                                    expr: Box::new(expr2.take()),
1013                                },
1014                                Err(_) => MirScalarExpr::literal(
1015                                    Err(EvalError::UnknownUnits(units.into())),
1016                                    e.typ(column_types).scalar_type,
1017                                ),
1018                            }
1019                        } else if *func == BinaryFunc::DatePartTimestamp && expr1.is_literal() {
1020                            let units = expr1.as_literal_str().unwrap();
1021                            *e = match units.parse::<DateTimeUnits>() {
1022                                Ok(units) => MirScalarExpr::CallUnary {
1023                                    func: UnaryFunc::DatePartTimestamp(func::DatePartTimestamp(
1024                                        units,
1025                                    )),
1026                                    expr: Box::new(expr2.take()),
1027                                },
1028                                Err(_) => MirScalarExpr::literal(
1029                                    Err(EvalError::UnknownUnits(units.into())),
1030                                    e.typ(column_types).scalar_type,
1031                                ),
1032                            }
1033                        } else if *func == BinaryFunc::DatePartTimestampTz && expr1.is_literal() {
1034                            let units = expr1.as_literal_str().unwrap();
1035                            *e = match units.parse::<DateTimeUnits>() {
1036                                Ok(units) => MirScalarExpr::CallUnary {
1037                                    func: UnaryFunc::DatePartTimestampTz(
1038                                        func::DatePartTimestampTz(units),
1039                                    ),
1040                                    expr: Box::new(expr2.take()),
1041                                },
1042                                Err(_) => MirScalarExpr::literal(
1043                                    Err(EvalError::UnknownUnits(units.into())),
1044                                    e.typ(column_types).scalar_type,
1045                                ),
1046                            }
1047                        } else if *func == BinaryFunc::DateTruncTimestamp && expr1.is_literal() {
1048                            let units = expr1.as_literal_str().unwrap();
1049                            *e = match units.parse::<DateTimeUnits>() {
1050                                Ok(units) => MirScalarExpr::CallUnary {
1051                                    func: UnaryFunc::DateTruncTimestamp(func::DateTruncTimestamp(
1052                                        units,
1053                                    )),
1054                                    expr: Box::new(expr2.take()),
1055                                },
1056                                Err(_) => MirScalarExpr::literal(
1057                                    Err(EvalError::UnknownUnits(units.into())),
1058                                    e.typ(column_types).scalar_type,
1059                                ),
1060                            }
1061                        } else if *func == BinaryFunc::DateTruncTimestampTz && expr1.is_literal() {
1062                            let units = expr1.as_literal_str().unwrap();
1063                            *e = match units.parse::<DateTimeUnits>() {
1064                                Ok(units) => MirScalarExpr::CallUnary {
1065                                    func: UnaryFunc::DateTruncTimestampTz(
1066                                        func::DateTruncTimestampTz(units),
1067                                    ),
1068                                    expr: Box::new(expr2.take()),
1069                                },
1070                                Err(_) => MirScalarExpr::literal(
1071                                    Err(EvalError::UnknownUnits(units.into())),
1072                                    e.typ(column_types).scalar_type,
1073                                ),
1074                            }
1075                        } else if *func == BinaryFunc::TimezoneTimestamp && expr1.is_literal() {
1076                            // If the timezone argument is a literal, and we're applying the function on many rows at the same
1077                            // time we really don't want to parse it again and again, so we parse it once and embed it into the
1078                            // UnaryFunc enum. The memory footprint of Timezone is small (8 bytes).
1079                            let tz = expr1.as_literal_str().unwrap();
1080                            *e = match parse_timezone(tz, TimezoneSpec::Posix) {
1081                                Ok(tz) => MirScalarExpr::CallUnary {
1082                                    func: UnaryFunc::TimezoneTimestamp(func::TimezoneTimestamp(tz)),
1083                                    expr: Box::new(expr2.take()),
1084                                },
1085                                Err(err) => MirScalarExpr::literal(
1086                                    Err(err),
1087                                    e.typ(column_types).scalar_type,
1088                                ),
1089                            }
1090                        } else if *func == BinaryFunc::TimezoneTimestampTz && expr1.is_literal() {
1091                            let tz = expr1.as_literal_str().unwrap();
1092                            *e = match parse_timezone(tz, TimezoneSpec::Posix) {
1093                                Ok(tz) => MirScalarExpr::CallUnary {
1094                                    func: UnaryFunc::TimezoneTimestampTz(
1095                                        func::TimezoneTimestampTz(tz),
1096                                    ),
1097                                    expr: Box::new(expr2.take()),
1098                                },
1099                                Err(err) => MirScalarExpr::literal(
1100                                    Err(err),
1101                                    e.typ(column_types).scalar_type,
1102                                ),
1103                            }
1104                        } else if *func == BinaryFunc::ToCharTimestamp && expr2.is_literal() {
1105                            let format_str = expr2.as_literal_str().unwrap();
1106                            *e = MirScalarExpr::CallUnary {
1107                                func: UnaryFunc::ToCharTimestamp(func::ToCharTimestamp {
1108                                    format_string: format_str.to_string(),
1109                                    format: DateTimeFormat::compile(format_str),
1110                                }),
1111                                expr: Box::new(expr1.take()),
1112                            };
1113                        } else if *func == BinaryFunc::ToCharTimestampTz && expr2.is_literal() {
1114                            let format_str = expr2.as_literal_str().unwrap();
1115                            *e = MirScalarExpr::CallUnary {
1116                                func: UnaryFunc::ToCharTimestampTz(func::ToCharTimestampTz {
1117                                    format_string: format_str.to_string(),
1118                                    format: DateTimeFormat::compile(format_str),
1119                                }),
1120                                expr: Box::new(expr1.take()),
1121                            };
1122                        } else if matches!(*func, BinaryFunc::Eq | BinaryFunc::NotEq)
1123                            && expr2 < expr1
1124                        {
1125                            // Canonically order elements so that deduplication works better.
1126                            // Also, the below `Literal([c1, c2]) = record_create(e1, e2)` matching
1127                            // relies on this canonical ordering.
1128                            mem::swap(expr1, expr2);
1129                        } else if let (
1130                            BinaryFunc::Eq,
1131                            MirScalarExpr::Literal(
1132                                Ok(lit_row),
1133                                ColumnType {
1134                                    scalar_type:
1135                                        ScalarType::Record {
1136                                            fields: field_types,
1137                                            ..
1138                                        },
1139                                    ..
1140                                },
1141                            ),
1142                            MirScalarExpr::CallVariadic {
1143                                func: VariadicFunc::RecordCreate { .. },
1144                                exprs: rec_create_args,
1145                            },
1146                        ) = (&*func, &**expr1, &**expr2)
1147                        {
1148                            // Literal([c1, c2]) = record_create(e1, e2)
1149                            //  -->
1150                            // c1 = e1 AND c2 = e2
1151                            //
1152                            // (Records are represented as lists.)
1153                            //
1154                            // `MapFilterProject::literal_constraints` relies on this transform,
1155                            // because `(e1,e2) IN ((1,2))` is desugared using `record_create`.
1156                            match lit_row.unpack_first() {
1157                                Datum::List(datum_list) => {
1158                                    *e = MirScalarExpr::CallVariadic {
1159                                        func: VariadicFunc::And,
1160                                        exprs: itertools::izip!(
1161                                            datum_list.iter(),
1162                                            field_types,
1163                                            rec_create_args
1164                                        )
1165                                        .map(|(d, (_, typ), a)| MirScalarExpr::CallBinary {
1166                                            func: BinaryFunc::Eq,
1167                                            expr1: Box::new(MirScalarExpr::Literal(
1168                                                Ok(Row::pack_slice(&[d])),
1169                                                typ.clone(),
1170                                            )),
1171                                            expr2: Box::new(a.clone()),
1172                                        })
1173                                        .collect(),
1174                                    };
1175                                }
1176                                _ => {}
1177                            }
1178                        } else if let (
1179                            BinaryFunc::Eq,
1180                            MirScalarExpr::CallVariadic {
1181                                func: VariadicFunc::RecordCreate { .. },
1182                                exprs: rec_create_args1,
1183                            },
1184                            MirScalarExpr::CallVariadic {
1185                                func: VariadicFunc::RecordCreate { .. },
1186                                exprs: rec_create_args2,
1187                            },
1188                        ) = (&*func, &**expr1, &**expr2)
1189                        {
1190                            // record_create(a1, a2, ...) = record_create(b1, b2, ...)
1191                            //  -->
1192                            // a1 = b1 AND a2 = b2 AND ...
1193                            //
1194                            // This is similar to the previous reduction, but this one kicks in also
1195                            // when only some (or none) of the record fields are literals. This
1196                            // enables the discovery of literal constraints for those fields.
1197                            //
1198                            // Note that there is a similar decomposition in
1199                            // `mz_sql::plan::transform_ast::Desugarer`, but that is earlier in the
1200                            // pipeline than the compilation of IN lists to `record_create`.
1201                            *e = MirScalarExpr::CallVariadic {
1202                                func: VariadicFunc::And,
1203                                exprs: rec_create_args1
1204                                    .into_iter()
1205                                    .zip(rec_create_args2)
1206                                    .map(|(a, b)| MirScalarExpr::CallBinary {
1207                                        func: BinaryFunc::Eq,
1208                                        expr1: Box::new(a.clone()),
1209                                        expr2: Box::new(b.clone()),
1210                                    })
1211                                    .collect(),
1212                            }
1213                        }
1214                    }
1215                    MirScalarExpr::CallVariadic { .. } => {
1216                        e.flatten_associative();
1217                        let (func, exprs) = match e {
1218                            MirScalarExpr::CallVariadic { func, exprs } => (func, exprs),
1219                            _ => unreachable!("`flatten_associative` shouldn't change node type"),
1220                        };
1221                        if *func == VariadicFunc::Coalesce {
1222                            // If all inputs are null, output is null. This check must
1223                            // be done before `exprs.retain...` because `e.typ` requires
1224                            // > 0 `exprs` remain.
1225                            if exprs.iter().all(|expr| expr.is_literal_null()) {
1226                                *e = MirScalarExpr::literal_null(e.typ(column_types).scalar_type);
1227                                return;
1228                            }
1229
1230                            // Remove any null values if not all values are null.
1231                            exprs.retain(|e| !e.is_literal_null());
1232
1233                            // Find the first argument that is a literal or non-nullable
1234                            // column. All arguments after it get ignored, so throw them
1235                            // away. This intentionally throws away errors that can
1236                            // never happen.
1237                            if let Some(i) = exprs
1238                                .iter()
1239                                .position(|e| e.is_literal() || !e.typ(column_types).nullable)
1240                            {
1241                                exprs.truncate(i + 1);
1242                            }
1243
1244                            // Deduplicate arguments in cases like `coalesce(#0, #0)`.
1245                            let mut prior_exprs = BTreeSet::new();
1246                            exprs.retain(|e| prior_exprs.insert(e.clone()));
1247
1248                            if exprs.len() == 1 {
1249                                // Only one argument, so the coalesce is a no-op.
1250                                *e = exprs[0].take();
1251                            }
1252                        } else if exprs.iter().all(|e| e.is_literal()) {
1253                            *e = eval(e);
1254                        } else if func.propagates_nulls()
1255                            && exprs.iter().any(|e| e.is_literal_null())
1256                        {
1257                            *e = MirScalarExpr::literal_null(e.typ(column_types).scalar_type);
1258                        } else if let Some(err) = exprs.iter().find_map(|e| e.as_literal_err()) {
1259                            *e = MirScalarExpr::literal(
1260                                Err(err.clone()),
1261                                e.typ(column_types).scalar_type,
1262                            );
1263                        } else if *func == VariadicFunc::RegexpMatch
1264                            && exprs[1].is_literal()
1265                            && exprs.get(2).map_or(true, |e| e.is_literal())
1266                        {
1267                            let needle = exprs[1].as_literal_str().unwrap();
1268                            let flags = match exprs.len() {
1269                                3 => exprs[2].as_literal_str().unwrap(),
1270                                _ => "",
1271                            };
1272                            *e = match func::build_regex(needle, flags) {
1273                                Ok(regex) => mem::take(exprs)
1274                                    .into_first()
1275                                    .call_unary(UnaryFunc::RegexpMatch(func::RegexpMatch(regex))),
1276                                Err(err) => MirScalarExpr::literal(
1277                                    Err(err),
1278                                    e.typ(column_types).scalar_type,
1279                                ),
1280                            };
1281                        } else if *func == VariadicFunc::RegexpReplace
1282                            && exprs[1].is_literal()
1283                            && exprs.get(3).map_or(true, |e| e.is_literal())
1284                        {
1285                            let pattern = exprs[1].as_literal_str().unwrap();
1286                            let flags = exprs
1287                                .get(3)
1288                                .map_or("", |expr| expr.as_literal_str().unwrap());
1289                            let (limit, flags) = regexp_replace_parse_flags(flags);
1290
1291                            // The behavior of `regexp_replace` is that if the data is `NULL`, the
1292                            // function returns `NULL`, independently of whether the pattern or
1293                            // flags are correct. We need to check for this case and introduce an
1294                            // if-then-else on the error path to only surface the error if the first
1295                            // input is non-NULL.
1296                            *e = match func::build_regex(pattern, &flags) {
1297                                Ok(regex) => {
1298                                    let mut exprs = mem::take(exprs);
1299                                    let replacement = exprs.swap_remove(2);
1300                                    let source = exprs.swap_remove(0);
1301                                    source.call_binary(
1302                                        replacement,
1303                                        BinaryFunc::RegexpReplace { regex, limit },
1304                                    )
1305                                }
1306                                Err(err) => {
1307                                    let mut exprs = mem::take(exprs);
1308                                    let source = exprs.swap_remove(0);
1309                                    let scalar_type = e.typ(column_types).scalar_type;
1310                                    // We need to return `NULL` on `NULL` input, and error otherwise.
1311                                    source.call_is_null().if_then_else(
1312                                        MirScalarExpr::literal_null(scalar_type.clone()),
1313                                        MirScalarExpr::literal(Err(err), scalar_type),
1314                                    )
1315                                }
1316                            };
1317                        } else if *func == VariadicFunc::RegexpSplitToArray
1318                            && exprs[1].is_literal()
1319                            && exprs.get(2).map_or(true, |e| e.is_literal())
1320                        {
1321                            let needle = exprs[1].as_literal_str().unwrap();
1322                            let flags = match exprs.len() {
1323                                3 => exprs[2].as_literal_str().unwrap(),
1324                                _ => "",
1325                            };
1326                            *e = match func::build_regex(needle, flags) {
1327                                Ok(regex) => mem::take(exprs).into_first().call_unary(
1328                                    UnaryFunc::RegexpSplitToArray(func::RegexpSplitToArray(regex)),
1329                                ),
1330                                Err(err) => MirScalarExpr::literal(
1331                                    Err(err),
1332                                    e.typ(column_types).scalar_type,
1333                                ),
1334                            };
1335                        } else if *func == VariadicFunc::ListIndex && is_list_create_call(&exprs[0])
1336                        {
1337                            // We are looking for ListIndex(ListCreate, literal), and eliminate
1338                            // both the ListIndex and the ListCreate. E.g.: `LIST[f1,f2][2]` --> `f2`
1339                            let ind_exprs = exprs.split_off(1);
1340                            let top_list_create = exprs.swap_remove(0);
1341                            *e = reduce_list_create_list_index_literal(top_list_create, ind_exprs);
1342                        } else if *func == VariadicFunc::Or || *func == VariadicFunc::And {
1343                            // Note: It's important that we have called `flatten_associative` above.
1344                            e.undistribute_and_or();
1345                            e.reduce_and_canonicalize_and_or();
1346                        } else if let VariadicFunc::TimezoneTime = func {
1347                            if exprs[0].is_literal() && exprs[2].is_literal_ok() {
1348                                let tz = exprs[0].as_literal_str().unwrap();
1349                                *e = match parse_timezone(tz, TimezoneSpec::Posix) {
1350                                    Ok(tz) => MirScalarExpr::CallUnary {
1351                                        func: UnaryFunc::TimezoneTime(func::TimezoneTime {
1352                                            tz,
1353                                            wall_time: exprs[2]
1354                                                .as_literal()
1355                                                .unwrap()
1356                                                .unwrap()
1357                                                .unwrap_timestamptz()
1358                                                .naive_utc(),
1359                                        }),
1360                                        expr: Box::new(exprs[1].take()),
1361                                    },
1362                                    Err(err) => MirScalarExpr::literal(
1363                                        Err(err),
1364                                        e.typ(column_types).scalar_type,
1365                                    ),
1366                                }
1367                            }
1368                        }
1369                    }
1370                    MirScalarExpr::If { cond, then, els } => {
1371                        if let Some(literal) = cond.as_literal() {
1372                            match literal {
1373                                Ok(Datum::True) => *e = then.take(),
1374                                Ok(Datum::False) | Ok(Datum::Null) => *e = els.take(),
1375                                Err(err) => {
1376                                    *e = MirScalarExpr::Literal(
1377                                        Err(err.clone()),
1378                                        then.typ(column_types)
1379                                            .union(&els.typ(column_types))
1380                                            .unwrap(),
1381                                    )
1382                                }
1383                                _ => unreachable!(),
1384                            }
1385                        } else if then == els {
1386                            *e = then.take();
1387                        } else if then.is_literal_ok()
1388                            && els.is_literal_ok()
1389                            && then.typ(column_types).scalar_type == ScalarType::Bool
1390                            && els.typ(column_types).scalar_type == ScalarType::Bool
1391                        {
1392                            match (then.as_literal(), els.as_literal()) {
1393                                // Note: NULLs from the condition should not be propagated to the result
1394                                // of the expression.
1395                                (Some(Ok(Datum::True)), _) => {
1396                                    // Rewritten as ((<cond> IS NOT NULL) AND (<cond>)) OR (<els>)
1397                                    // NULL <cond> results in: (FALSE AND NULL) OR (<els>) => (<els>)
1398                                    *e = cond
1399                                        .clone()
1400                                        .call_is_null()
1401                                        .not()
1402                                        .and(cond.take())
1403                                        .or(els.take());
1404                                }
1405                                (Some(Ok(Datum::False)), _) => {
1406                                    // Rewritten as ((NOT <cond>) OR (<cond> IS NULL)) AND (<els>)
1407                                    // NULL <cond> results in: (NULL OR TRUE) AND (<els>) => TRUE AND (<els>) => (<els>)
1408                                    *e = cond
1409                                        .clone()
1410                                        .not()
1411                                        .or(cond.take().call_is_null())
1412                                        .and(els.take());
1413                                }
1414                                (_, Some(Ok(Datum::True))) => {
1415                                    // Rewritten as (NOT <cond>) OR (<cond> IS NULL) OR (<then>)
1416                                    // NULL <cond> results in: NULL OR TRUE OR (<then>) => TRUE
1417                                    *e = cond
1418                                        .clone()
1419                                        .not()
1420                                        .or(cond.take().call_is_null())
1421                                        .or(then.take());
1422                                }
1423                                (_, Some(Ok(Datum::False))) => {
1424                                    // Rewritten as (<cond> IS NOT NULL) AND (<cond>) AND (<then>)
1425                                    // NULL <cond> results in: FALSE AND NULL AND (<then>) => FALSE
1426                                    *e = cond
1427                                        .clone()
1428                                        .call_is_null()
1429                                        .not()
1430                                        .and(cond.take())
1431                                        .and(then.take());
1432                                }
1433                                _ => {}
1434                            }
1435                        } else {
1436                            // Equivalent expression structure would allow us to push the `If` into the expression.
1437                            // For example, `IF <cond> THEN x = y ELSE x = z` becomes `x = IF <cond> THEN y ELSE z`.
1438                            //
1439                            // We have to also make sure that the expressions that will end up in
1440                            // the two `If` branches have unionable types. Otherwise, the `If` could
1441                            // not be typed by `typ`. An example where this could cause an issue is
1442                            // when pulling out `cast_jsonbable_to_jsonb`, which accepts a wide
1443                            // range of input types. (In theory, we could still do the optimization
1444                            // in this case by inserting appropriate casts, but this corner case is
1445                            // not worth the complication for now.)
1446                            // See https://github.com/MaterializeInc/database-issues/issues/9182
1447                            match (&mut **then, &mut **els) {
1448                                (
1449                                    MirScalarExpr::CallUnary { func: f1, expr: e1 },
1450                                    MirScalarExpr::CallUnary { func: f2, expr: e2 },
1451                                ) if f1 == f2
1452                                    && e1
1453                                        .typ(column_types)
1454                                        .union(&e2.typ(column_types))
1455                                        .is_ok() =>
1456                                {
1457                                    *e = cond
1458                                        .take()
1459                                        .if_then_else(e1.take(), e2.take())
1460                                        .call_unary(f1.clone());
1461                                }
1462                                (
1463                                    MirScalarExpr::CallBinary {
1464                                        func: f1,
1465                                        expr1: e1a,
1466                                        expr2: e2a,
1467                                    },
1468                                    MirScalarExpr::CallBinary {
1469                                        func: f2,
1470                                        expr1: e1b,
1471                                        expr2: e2b,
1472                                    },
1473                                ) if f1 == f2
1474                                    && e1a == e1b
1475                                    && e2a
1476                                        .typ(column_types)
1477                                        .union(&e2b.typ(column_types))
1478                                        .is_ok() =>
1479                                {
1480                                    *e = e1a.take().call_binary(
1481                                        cond.take().if_then_else(e2a.take(), e2b.take()),
1482                                        f1.clone(),
1483                                    );
1484                                }
1485                                (
1486                                    MirScalarExpr::CallBinary {
1487                                        func: f1,
1488                                        expr1: e1a,
1489                                        expr2: e2a,
1490                                    },
1491                                    MirScalarExpr::CallBinary {
1492                                        func: f2,
1493                                        expr1: e1b,
1494                                        expr2: e2b,
1495                                    },
1496                                ) if f1 == f2
1497                                    && e2a == e2b
1498                                    && e1a
1499                                        .typ(column_types)
1500                                        .union(&e1b.typ(column_types))
1501                                        .is_ok() =>
1502                                {
1503                                    *e = cond
1504                                        .take()
1505                                        .if_then_else(e1a.take(), e1b.take())
1506                                        .call_binary(e2a.take(), f1.clone());
1507                                }
1508                                _ => {}
1509                            }
1510                        }
1511                    }
1512                },
1513            );
1514        }
1515
1516        /* #region `reduce_list_create_list_index_literal` and helper functions */
1517
1518        fn list_create_type(list_create: &MirScalarExpr) -> ScalarType {
1519            if let MirScalarExpr::CallVariadic {
1520                func: VariadicFunc::ListCreate { elem_type: typ },
1521                ..
1522            } = list_create
1523            {
1524                (*typ).clone()
1525            } else {
1526                unreachable!()
1527            }
1528        }
1529
1530        fn is_list_create_call(expr: &MirScalarExpr) -> bool {
1531            matches!(
1532                expr,
1533                MirScalarExpr::CallVariadic {
1534                    func: VariadicFunc::ListCreate { .. },
1535                    ..
1536                }
1537            )
1538        }
1539
1540        /// Partial-evaluates a list indexing with a literal directly after a list creation.
1541        ///
1542        /// Multi-dimensional lists are handled by a single call to this function, with multiple
1543        /// elements in index_exprs (of which not all need to be literals), and nested ListCreates
1544        /// in list_create_to_reduce.
1545        ///
1546        /// # Examples
1547        ///
1548        /// `LIST[f1,f2][2]` --> `f2`.
1549        ///
1550        /// A multi-dimensional list, with only some of the indexes being literals:
1551        /// `LIST[[[f1, f2], [f3, f4]], [[f5, f6], [f7, f8]]] [2][n][2]` --> `LIST[f6, f8] [n]`
1552        ///
1553        /// See more examples in list.slt.
1554        fn reduce_list_create_list_index_literal(
1555            mut list_create_to_reduce: MirScalarExpr,
1556            mut index_exprs: Vec<MirScalarExpr>,
1557        ) -> MirScalarExpr {
1558            // We iterate over the index_exprs and remove literals, but keep non-literals.
1559            // When we encounter a non-literal, we need to dig into the nested ListCreates:
1560            // `list_create_mut_refs` will contain all the ListCreates of the current level. If an
1561            // element of `list_create_mut_refs` is not actually a ListCreate, then we break out of
1562            // the loop. When we remove a literal, we need to partial-evaluate all ListCreates
1563            // that are at the current level (except those that disappeared due to
1564            // literals at earlier levels), index into them with the literal, and change each
1565            // element in `list_create_mut_refs` to the result.
1566            // We also record mut refs to all the earlier `element_type` references that we have
1567            // seen in ListCreate calls, because when we process a literal index, we need to remove
1568            // one layer of list type from all these earlier ListCreate `element_type`s.
1569            let mut list_create_mut_refs = vec![&mut list_create_to_reduce];
1570            let mut earlier_list_create_types: Vec<&mut ScalarType> = vec![];
1571            let mut i = 0;
1572            while i < index_exprs.len()
1573                && list_create_mut_refs
1574                    .iter()
1575                    .all(|lc| is_list_create_call(lc))
1576            {
1577                if index_exprs[i].is_literal_ok() {
1578                    // We can remove this index.
1579                    let removed_index = index_exprs.remove(i);
1580                    let index_i64 = match removed_index.as_literal().unwrap().unwrap() {
1581                        Datum::Int64(sql_index_i64) => sql_index_i64 - 1,
1582                        _ => unreachable!(), // always an Int64, see plan_index_list
1583                    };
1584                    // For each list_create referenced by list_create_mut_refs, substitute it by its
1585                    // `index`th argument (or null).
1586                    for list_create in &mut list_create_mut_refs {
1587                        let list_create_args = match list_create {
1588                            MirScalarExpr::CallVariadic {
1589                                func: VariadicFunc::ListCreate { elem_type: _ },
1590                                exprs,
1591                            } => exprs,
1592                            _ => unreachable!(), // func cannot be anything else than a ListCreate
1593                        };
1594                        // ListIndex gives null on an out-of-bounds index
1595                        if index_i64 >= 0 && index_i64 < list_create_args.len().try_into().unwrap()
1596                        {
1597                            let index: usize = index_i64.try_into().unwrap();
1598                            **list_create = list_create_args.swap_remove(index);
1599                        } else {
1600                            let typ = list_create_type(list_create);
1601                            **list_create = MirScalarExpr::literal_null(typ);
1602                        }
1603                    }
1604                    // Peel one layer off of each of the earlier element types.
1605                    for t in earlier_list_create_types.iter_mut() {
1606                        if let ScalarType::List {
1607                            element_type,
1608                            custom_id: _,
1609                        } = t
1610                        {
1611                            **t = *element_type.clone();
1612                            // These are not the same types anymore, so remove custom_ids all the
1613                            // way down.
1614                            let mut u = &mut **t;
1615                            while let ScalarType::List {
1616                                element_type,
1617                                custom_id,
1618                            } = u
1619                            {
1620                                *custom_id = None;
1621                                u = &mut **element_type;
1622                            }
1623                        } else {
1624                            unreachable!("already matched below");
1625                        }
1626                    }
1627                } else {
1628                    // We can't remove this index, so we can't reduce any of the ListCreates at this
1629                    // level. So we change list_create_mut_refs to refer to all the arguments of all
1630                    // the ListCreates currently referenced by list_create_mut_refs.
1631                    list_create_mut_refs = list_create_mut_refs
1632                        .into_iter()
1633                        .flat_map(|list_create| match list_create {
1634                            MirScalarExpr::CallVariadic {
1635                                func: VariadicFunc::ListCreate { elem_type },
1636                                exprs: list_create_args,
1637                            } => {
1638                                earlier_list_create_types.push(elem_type);
1639                                list_create_args
1640                            }
1641                            // func cannot be anything else than a ListCreate
1642                            _ => unreachable!(),
1643                        })
1644                        .collect();
1645                    i += 1; // next index_expr
1646                }
1647            }
1648            // If all list indexes have been evaluated, return the reduced expression.
1649            // Otherwise, rebuild the ListIndex call with the remaining ListCreates and indexes.
1650            if index_exprs.is_empty() {
1651                assert_eq!(list_create_mut_refs.len(), 1);
1652                list_create_to_reduce
1653            } else {
1654                let mut exprs: Vec<MirScalarExpr> = vec![list_create_to_reduce];
1655                exprs.append(&mut index_exprs);
1656                MirScalarExpr::CallVariadic {
1657                    func: VariadicFunc::ListIndex,
1658                    exprs,
1659                }
1660            }
1661        }
1662
1663        /* #endregion */
1664    }
1665
1666    /// Decompose an IsNull expression into a disjunction of
1667    /// simpler expressions.
1668    ///
1669    /// Assumes that `self` is the expression inside of an IsNull.
1670    /// Returns `Some(expressions)` if the outer IsNull is to be
1671    /// replaced by some other expression. Note: if it returns
1672    /// None, it might still have mutated *self.
1673    fn decompose_is_null(&mut self) -> Option<MirScalarExpr> {
1674        // TODO: allow simplification of unmaterializable functions
1675
1676        match self {
1677            MirScalarExpr::CallUnary {
1678                func,
1679                expr: inner_expr,
1680            } => {
1681                if !func.introduces_nulls() {
1682                    if func.propagates_nulls() {
1683                        *self = inner_expr.take();
1684                        return self.decompose_is_null();
1685                    } else {
1686                        // Different from CallBinary and CallVariadic, because of determinism. See
1687                        // https://materializeinc.slack.com/archives/C01BE3RN82F/p1657644478517709
1688                        return Some(MirScalarExpr::literal_false());
1689                    }
1690                }
1691            }
1692            MirScalarExpr::CallBinary { func, expr1, expr2 } => {
1693                // (<expr1> <op> <expr2>) IS NULL can often be simplified to
1694                // (<expr1> IS NULL) OR (<expr2> IS NULL).
1695                if func.propagates_nulls() && !func.introduces_nulls() {
1696                    let expr1 = expr1.take().call_is_null();
1697                    let expr2 = expr2.take().call_is_null();
1698                    return Some(expr1.or(expr2));
1699                }
1700            }
1701            MirScalarExpr::CallVariadic { func, exprs } => {
1702                if func.propagates_nulls() && !func.introduces_nulls() {
1703                    let exprs = exprs.into_iter().map(|e| e.take().call_is_null()).collect();
1704                    return Some(MirScalarExpr::CallVariadic {
1705                        func: VariadicFunc::Or,
1706                        exprs,
1707                    });
1708                }
1709            }
1710            _ => {}
1711        }
1712
1713        None
1714    }
1715
1716    /// Flattens a chain of calls to associative variadic functions
1717    /// (For example: ORs or ANDs)
1718    pub fn flatten_associative(&mut self) {
1719        match self {
1720            MirScalarExpr::CallVariadic {
1721                exprs: outer_operands,
1722                func: outer_func,
1723            } if outer_func.is_associative() => {
1724                *outer_operands = outer_operands
1725                    .into_iter()
1726                    .flat_map(|o| {
1727                        if let MirScalarExpr::CallVariadic {
1728                            exprs: inner_operands,
1729                            func: inner_func,
1730                        } = o
1731                        {
1732                            if *inner_func == *outer_func {
1733                                mem::take(inner_operands)
1734                            } else {
1735                                vec![o.take()]
1736                            }
1737                        } else {
1738                            vec![o.take()]
1739                        }
1740                    })
1741                    .collect();
1742            }
1743            _ => {}
1744        }
1745    }
1746
1747    /* #region AND/OR canonicalization and transformations  */
1748
1749    /// Canonicalizes AND/OR, and does some straightforward simplifications
1750    fn reduce_and_canonicalize_and_or(&mut self) {
1751        // We do this until fixed point, because after undistribute_and_or calls us, it relies on
1752        // the property that self is not an 1-arg AND/OR. Just one application of our loop body
1753        // can't ensure this, because the application itself might create a 1-arg AND/OR.
1754        let mut old_self = MirScalarExpr::column(0);
1755        while old_self != *self {
1756            old_self = self.clone();
1757            match self {
1758                MirScalarExpr::CallVariadic {
1759                    func: func @ (VariadicFunc::And | VariadicFunc::Or),
1760                    exprs,
1761                } => {
1762                    // Canonically order elements so that various deduplications work better,
1763                    // e.g., in undistribute_and_or.
1764                    // Also, extract_equal_or_both_null_inner depends on the args being sorted.
1765                    exprs.sort();
1766
1767                    // x AND/OR x --> x
1768                    exprs.dedup(); // this also needs the above sorting
1769
1770                    if exprs.len() == 1 {
1771                        // AND/OR of 1 argument evaluates to that argument
1772                        *self = exprs.swap_remove(0);
1773                    } else if exprs.len() == 0 {
1774                        // AND/OR of 0 arguments evaluates to true/false
1775                        *self = func.unit_of_and_or();
1776                    } else if exprs.iter().any(|e| *e == func.zero_of_and_or()) {
1777                        // short-circuiting
1778                        *self = func.zero_of_and_or();
1779                    } else {
1780                        // a AND true --> a
1781                        // a OR false --> a
1782                        exprs.retain(|e| *e != func.unit_of_and_or());
1783                    }
1784                }
1785                _ => {}
1786            }
1787        }
1788    }
1789
1790    /// Transforms !(a && b) into !a || !b, and !(a || b) into !a && !b
1791    fn demorgans(&mut self) {
1792        if let MirScalarExpr::CallUnary {
1793            expr: inner,
1794            func: UnaryFunc::Not(func::Not),
1795        } = self
1796        {
1797            inner.flatten_associative();
1798            match &mut **inner {
1799                MirScalarExpr::CallVariadic {
1800                    func: inner_func @ (VariadicFunc::And | VariadicFunc::Or),
1801                    exprs,
1802                } => {
1803                    *inner_func = inner_func.switch_and_or();
1804                    *exprs = exprs.into_iter().map(|e| e.take().not()).collect();
1805                    *self = (*inner).take(); // Removes the outer not
1806                }
1807                _ => {}
1808            }
1809        }
1810    }
1811
1812    /// AND/OR undistribution (factoring out) to apply at each `MirScalarExpr`.
1813    ///
1814    /// This method attempts to apply one of the [distribution laws][distributivity]
1815    /// (in a direction opposite to the their name):
1816    /// ```text
1817    /// (a && b) || (a && c) --> a && (b || c)  // Undistribute-OR
1818    /// (a || b) && (a || c) --> a || (b && c)  // Undistribute-AND
1819    /// ```
1820    /// or one of their corresponding two [absorption law][absorption] special
1821    /// cases:
1822    /// ```text
1823    /// a || (a && c)  -->  a  // Absorb-OR
1824    /// a && (a || c)  -->  a  // Absorb-AND
1825    /// ```
1826    ///
1827    /// The method also works with more than 2 arguments at the top, e.g.
1828    /// ```text
1829    /// (a && b) || (a && c) || (a && d)  -->  a && (b || c || d)
1830    /// ```
1831    /// It can also factor out only a subset of the top arguments, e.g.
1832    /// ```text
1833    /// (a && b) || (a && c) || (d && e)  -->  (a && (b || c)) || (d && e)
1834    /// ```
1835    ///
1836    /// Note that sometimes there are two overlapping possibilities to factor
1837    /// out from, e.g.
1838    /// ```text
1839    /// (a && b) || (a && c) || (d && c)
1840    /// ```
1841    /// Here we can factor out `a` from from the 1. and 2. terms, or we can
1842    /// factor out `c` from the 2. and 3. terms. One of these might lead to
1843    /// more/better undistribution opportunities later, but we just pick one
1844    /// locally, because recursively trying out all of them would lead to
1845    /// exponential run time.
1846    ///
1847    /// The local heuristic is that we prefer a candidate that leads to an
1848    /// absorption, or if there is no such one then we simply pick the first. In
1849    /// case of multiple absorption candidates, it doesn't matter which one we
1850    /// pick, because applying an absorption cannot adversely effect the
1851    /// possibility of applying other absorptions.
1852    ///
1853    /// # Assumption
1854    ///
1855    /// Assumes that nested chains of AND/OR applications are flattened (this
1856    /// can be enforced with [`Self::flatten_associative`]).
1857    ///
1858    /// # Examples
1859    ///
1860    /// Absorb-OR:
1861    /// ```text
1862    /// a || (a && c) || (a && d)
1863    /// -->
1864    /// a && (true || c || d)
1865    /// -->
1866    /// a && true
1867    /// -->
1868    /// a
1869    /// ```
1870    /// Here only the first step is performed by this method. The rest is done
1871    /// by [`Self::reduce_and_canonicalize_and_or`] called after us in
1872    /// `reduce()`.
1873    ///
1874    /// [distributivity]: https://en.wikipedia.org/wiki/Distributive_property
1875    /// [absorption]: https://en.wikipedia.org/wiki/Absorption_law
1876    fn undistribute_and_or(&mut self) {
1877        // It wouldn't be strictly necessary to wrap this fn in this loop, because `reduce()` calls
1878        // us in a loop anyway. However, `reduce()` tries to do many other things, so the loop here
1879        // improves performance when there are several undistributions to apply in sequence, which
1880        // can occur in `CanonicalizeMfp` when undoing the DNF.
1881        let mut old_self = MirScalarExpr::column(0);
1882        while old_self != *self {
1883            old_self = self.clone();
1884            self.reduce_and_canonicalize_and_or(); // We don't want to deal with 1-arg AND/OR at the top
1885            if let MirScalarExpr::CallVariadic {
1886                exprs: outer_operands,
1887                func: outer_func @ (VariadicFunc::Or | VariadicFunc::And),
1888            } = self
1889            {
1890                let inner_func = outer_func.switch_and_or();
1891
1892                // Make sure that each outer operand is a call to inner_func, by wrapping in a 1-arg
1893                // call if necessary.
1894                outer_operands.iter_mut().for_each(|o| {
1895                    if !matches!(o, MirScalarExpr::CallVariadic {func: f, ..} if *f == inner_func) {
1896                        *o = MirScalarExpr::CallVariadic {
1897                            func: inner_func.clone(),
1898                            exprs: vec![o.take()],
1899                        };
1900                    }
1901                });
1902
1903                let mut inner_operands_refs: Vec<&mut Vec<MirScalarExpr>> = outer_operands
1904                    .iter_mut()
1905                    .map(|o| match o {
1906                        MirScalarExpr::CallVariadic { func: f, exprs } if *f == inner_func => exprs,
1907                        _ => unreachable!(), // the wrapping made sure that we'll get a match
1908                    })
1909                    .collect();
1910
1911                // Find inner operands to undistribute, i.e., which are in _all_ of the outer operands.
1912                let mut intersection = inner_operands_refs
1913                    .iter()
1914                    .map(|v| (*v).clone())
1915                    .reduce(|ops1, ops2| ops1.into_iter().filter(|e| ops2.contains(e)).collect())
1916                    .unwrap();
1917                intersection.sort();
1918                intersection.dedup();
1919
1920                if !intersection.is_empty() {
1921                    // Factor out the intersection from all the top-level args.
1922
1923                    // Remove the intersection from each inner operand vector.
1924                    inner_operands_refs
1925                        .iter_mut()
1926                        .for_each(|ops| (**ops).retain(|o| !intersection.contains(o)));
1927
1928                    // Simplify terms that now have only 0 or 1 args due to removing the intersection.
1929                    outer_operands
1930                        .iter_mut()
1931                        .for_each(|o| o.reduce_and_canonicalize_and_or());
1932
1933                    // Add the intersection at the beginning
1934                    *self = MirScalarExpr::CallVariadic {
1935                        func: inner_func,
1936                        exprs: intersection.into_iter().chain_one(self.clone()).collect(),
1937                    };
1938                } else {
1939                    // If the intersection was empty, that means that there is nothing we can factor out
1940                    // from _all_ the top-level args. However, we might still find something to factor
1941                    // out from a subset of the top-level args. To find such an opportunity, we look for
1942                    // duplicates across all inner args, e.g. if we have
1943                    // `(...) OR (... AND `a` AND ...) OR (...) OR (... AND `a` AND ...)`
1944                    // then we'll find that `a` occurs in more than one top-level arg, so
1945                    // `indexes_to_undistribute` will point us to the 2. and 4. top-level args.
1946
1947                    // Create (inner_operand, index) pairs, where the index is the position in
1948                    // outer_operands
1949                    let all_inner_operands = inner_operands_refs
1950                        .iter()
1951                        .enumerate()
1952                        .flat_map(|(i, inner_vec)| inner_vec.iter().map(move |a| ((*a).clone(), i)))
1953                        .sorted()
1954                        .collect_vec();
1955
1956                    // Find inner operand expressions that occur in more than one top-level arg.
1957                    // Each inner vector in `undistribution_opportunities` will belong to one such inner
1958                    // operand expression, and it is a set of indexes pointing to top-level args where
1959                    // that inner operand occurs.
1960                    let undistribution_opportunities = all_inner_operands
1961                        .iter()
1962                        .chunk_by(|(a, _i)| a)
1963                        .into_iter()
1964                        .map(|(_a, g)| g.map(|(_a, i)| *i).sorted().dedup().collect_vec())
1965                        .filter(|g| g.len() > 1)
1966                        .collect_vec();
1967
1968                    // Choose one of the inner vectors from `undistribution_opportunities`.
1969                    let indexes_to_undistribute = undistribution_opportunities
1970                        .iter()
1971                        // Let's prefer index sets that directly lead to an absorption.
1972                        .find(|index_set| {
1973                            index_set
1974                                .iter()
1975                                .any(|i| inner_operands_refs.get(*i).unwrap().len() == 1)
1976                        })
1977                        // If we didn't find any absorption, then any index set will do.
1978                        .or_else(|| undistribution_opportunities.first())
1979                        .cloned();
1980
1981                    // In any case, undo the 1-arg wrapping that we did at the beginning.
1982                    outer_operands
1983                        .iter_mut()
1984                        .for_each(|o| o.reduce_and_canonicalize_and_or());
1985
1986                    if let Some(indexes_to_undistribute) = indexes_to_undistribute {
1987                        // Found something to undistribute from a subset of the outer operands.
1988                        // We temporarily remove these from outer_operands, call ourselves on it, and
1989                        // then push back the result.
1990                        let mut undistribute_from = MirScalarExpr::CallVariadic {
1991                            func: outer_func.clone(),
1992                            exprs: swap_remove_multiple(outer_operands, indexes_to_undistribute),
1993                        };
1994                        // By construction, the recursive call is guaranteed to hit
1995                        // the `!intersection.is_empty()` branch.
1996                        undistribute_from.undistribute_and_or();
1997                        // Append the undistributed result to outer operands that were not included in
1998                        // indexes_to_undistribute.
1999                        outer_operands.push(undistribute_from);
2000                    }
2001                }
2002            }
2003        }
2004    }
2005
2006    /* #endregion */
2007
2008    /// Adds any columns that *must* be non-Null for `self` to be non-Null.
2009    pub fn non_null_requirements(&self, columns: &mut BTreeSet<usize>) {
2010        match self {
2011            MirScalarExpr::Column(col, _name) => {
2012                columns.insert(*col);
2013            }
2014            MirScalarExpr::Literal(..) => {}
2015            MirScalarExpr::CallUnmaterializable(_) => (),
2016            MirScalarExpr::CallUnary { func, expr } => {
2017                if func.propagates_nulls() {
2018                    expr.non_null_requirements(columns);
2019                }
2020            }
2021            MirScalarExpr::CallBinary { func, expr1, expr2 } => {
2022                if func.propagates_nulls() {
2023                    expr1.non_null_requirements(columns);
2024                    expr2.non_null_requirements(columns);
2025                }
2026            }
2027            MirScalarExpr::CallVariadic { func, exprs } => {
2028                if func.propagates_nulls() {
2029                    for expr in exprs {
2030                        expr.non_null_requirements(columns);
2031                    }
2032                }
2033            }
2034            MirScalarExpr::If { .. } => (),
2035        }
2036    }
2037
2038    pub fn typ(&self, column_types: &[ColumnType]) -> ColumnType {
2039        match self {
2040            MirScalarExpr::Column(i, _name) => column_types[*i].clone(),
2041            MirScalarExpr::Literal(_, typ) => typ.clone(),
2042            MirScalarExpr::CallUnmaterializable(func) => func.output_type(),
2043            MirScalarExpr::CallUnary { expr, func } => func.output_type(expr.typ(column_types)),
2044            MirScalarExpr::CallBinary { expr1, expr2, func } => {
2045                func.output_type(expr1.typ(column_types), expr2.typ(column_types))
2046            }
2047            MirScalarExpr::CallVariadic { exprs, func } => {
2048                func.output_type(exprs.iter().map(|e| e.typ(column_types)).collect())
2049            }
2050            MirScalarExpr::If { cond: _, then, els } => {
2051                let then_type = then.typ(column_types);
2052                let else_type = els.typ(column_types);
2053                then_type.union(&else_type).unwrap()
2054            }
2055        }
2056    }
2057
2058    pub fn eval<'a>(
2059        &'a self,
2060        datums: &[Datum<'a>],
2061        temp_storage: &'a RowArena,
2062    ) -> Result<Datum<'a>, EvalError> {
2063        match self {
2064            MirScalarExpr::Column(index, _name) => Ok(datums[*index].clone()),
2065            MirScalarExpr::Literal(res, _column_type) => match res {
2066                Ok(row) => Ok(row.unpack_first()),
2067                Err(e) => Err(e.clone()),
2068            },
2069            // Unmaterializable functions must be transformed away before
2070            // evaluation. Their purpose is as a placeholder for data that is
2071            // not known at plan time but can be inlined before runtime.
2072            MirScalarExpr::CallUnmaterializable(x) => Err(EvalError::Internal(
2073                format!("cannot evaluate unmaterializable function: {:?}", x).into(),
2074            )),
2075            MirScalarExpr::CallUnary { func, expr } => func.eval(datums, temp_storage, expr),
2076            MirScalarExpr::CallBinary { func, expr1, expr2 } => {
2077                func.eval(datums, temp_storage, expr1, expr2)
2078            }
2079            MirScalarExpr::CallVariadic { func, exprs } => func.eval(datums, temp_storage, exprs),
2080            MirScalarExpr::If { cond, then, els } => match cond.eval(datums, temp_storage)? {
2081                Datum::True => then.eval(datums, temp_storage),
2082                Datum::False | Datum::Null => els.eval(datums, temp_storage),
2083                d => Err(EvalError::Internal(
2084                    format!("if condition evaluated to non-boolean datum: {:?}", d).into(),
2085                )),
2086            },
2087        }
2088    }
2089
2090    /// True iff the expression contains
2091    /// `UnmaterializableFunc::MzNow`.
2092    pub fn contains_temporal(&self) -> bool {
2093        let mut contains = false;
2094        self.visit_pre(|e| {
2095            if let MirScalarExpr::CallUnmaterializable(UnmaterializableFunc::MzNow) = e {
2096                contains = true;
2097            }
2098        });
2099        contains
2100    }
2101
2102    /// True iff the expression contains an `UnmaterializableFunc`.
2103    pub fn contains_unmaterializable(&self) -> bool {
2104        let mut contains = false;
2105        self.visit_pre(|e| {
2106            if let MirScalarExpr::CallUnmaterializable(_) = e {
2107                contains = true;
2108            }
2109        });
2110        contains
2111    }
2112
2113    /// True iff the expression contains an `UnmaterializableFunc` that is not in the `exceptions`
2114    /// list.
2115    pub fn contains_unmaterializable_except(&self, exceptions: &[UnmaterializableFunc]) -> bool {
2116        let mut contains = false;
2117        self.visit_pre(|e| match e {
2118            MirScalarExpr::CallUnmaterializable(f) if !exceptions.contains(f) => contains = true,
2119            _ => (),
2120        });
2121        contains
2122    }
2123
2124    /// True iff the expression contains a `Column`.
2125    pub fn contains_column(&self) -> bool {
2126        let mut contains = false;
2127        self.visit_pre(|e| {
2128            if let MirScalarExpr::Column(_col, _name) = e {
2129                contains = true;
2130            }
2131        });
2132        contains
2133    }
2134
2135    /// True iff the expression contains a `Dummy`.
2136    pub fn contains_dummy(&self) -> bool {
2137        let mut contains = false;
2138        self.visit_pre(|e| {
2139            if let MirScalarExpr::Literal(row, _) = e {
2140                if let Ok(row) = row {
2141                    contains |= row.iter().any(|d| d == Datum::Dummy);
2142                }
2143            }
2144        });
2145        contains
2146    }
2147
2148    /// The size of the expression as a tree.
2149    pub fn size(&self) -> usize {
2150        let mut size = 0;
2151        self.visit_pre(&mut |_: &MirScalarExpr| {
2152            size += 1;
2153        });
2154        size
2155    }
2156}
2157
2158impl MirScalarExpr {
2159    /// True iff evaluation could possibly error on non-error input `Datum`.
2160    pub fn could_error(&self) -> bool {
2161        match self {
2162            MirScalarExpr::Column(_col, _name) => false,
2163            MirScalarExpr::Literal(row, ..) => row.is_err(),
2164            MirScalarExpr::CallUnmaterializable(_) => true,
2165            MirScalarExpr::CallUnary { func, expr } => func.could_error() || expr.could_error(),
2166            MirScalarExpr::CallBinary { func, expr1, expr2 } => {
2167                func.could_error() || expr1.could_error() || expr2.could_error()
2168            }
2169            MirScalarExpr::CallVariadic { func, exprs } => {
2170                func.could_error() || exprs.iter().any(|e| e.could_error())
2171            }
2172            MirScalarExpr::If { cond, then, els } => {
2173                cond.could_error() || then.could_error() || els.could_error()
2174            }
2175        }
2176    }
2177}
2178
2179impl VisitChildren<Self> for MirScalarExpr {
2180    fn visit_children<F>(&self, mut f: F)
2181    where
2182        F: FnMut(&Self),
2183    {
2184        use MirScalarExpr::*;
2185        match self {
2186            Column(_, _) | Literal(_, _) | CallUnmaterializable(_) => (),
2187            CallUnary { expr, .. } => {
2188                f(expr);
2189            }
2190            CallBinary { expr1, expr2, .. } => {
2191                f(expr1);
2192                f(expr2);
2193            }
2194            CallVariadic { exprs, .. } => {
2195                for expr in exprs {
2196                    f(expr);
2197                }
2198            }
2199            If { cond, then, els } => {
2200                f(cond);
2201                f(then);
2202                f(els);
2203            }
2204        }
2205    }
2206
2207    fn visit_mut_children<F>(&mut self, mut f: F)
2208    where
2209        F: FnMut(&mut Self),
2210    {
2211        use MirScalarExpr::*;
2212        match self {
2213            Column(_, _) | Literal(_, _) | CallUnmaterializable(_) => (),
2214            CallUnary { expr, .. } => {
2215                f(expr);
2216            }
2217            CallBinary { expr1, expr2, .. } => {
2218                f(expr1);
2219                f(expr2);
2220            }
2221            CallVariadic { exprs, .. } => {
2222                for expr in exprs {
2223                    f(expr);
2224                }
2225            }
2226            If { cond, then, els } => {
2227                f(cond);
2228                f(then);
2229                f(els);
2230            }
2231        }
2232    }
2233
2234    fn try_visit_children<F, E>(&self, mut f: F) -> Result<(), E>
2235    where
2236        F: FnMut(&Self) -> Result<(), E>,
2237        E: From<RecursionLimitError>,
2238    {
2239        use MirScalarExpr::*;
2240        match self {
2241            Column(_, _) | Literal(_, _) | CallUnmaterializable(_) => (),
2242            CallUnary { expr, .. } => {
2243                f(expr)?;
2244            }
2245            CallBinary { expr1, expr2, .. } => {
2246                f(expr1)?;
2247                f(expr2)?;
2248            }
2249            CallVariadic { exprs, .. } => {
2250                for expr in exprs {
2251                    f(expr)?;
2252                }
2253            }
2254            If { cond, then, els } => {
2255                f(cond)?;
2256                f(then)?;
2257                f(els)?;
2258            }
2259        }
2260        Ok(())
2261    }
2262
2263    fn try_visit_mut_children<F, E>(&mut self, mut f: F) -> Result<(), E>
2264    where
2265        F: FnMut(&mut Self) -> Result<(), E>,
2266        E: From<RecursionLimitError>,
2267    {
2268        use MirScalarExpr::*;
2269        match self {
2270            Column(_, _) | Literal(_, _) | CallUnmaterializable(_) => (),
2271            CallUnary { expr, .. } => {
2272                f(expr)?;
2273            }
2274            CallBinary { expr1, expr2, .. } => {
2275                f(expr1)?;
2276                f(expr2)?;
2277            }
2278            CallVariadic { exprs, .. } => {
2279                for expr in exprs {
2280                    f(expr)?;
2281                }
2282            }
2283            If { cond, then, els } => {
2284                f(cond)?;
2285                f(then)?;
2286                f(els)?;
2287            }
2288        }
2289        Ok(())
2290    }
2291}
2292
2293impl MirScalarExpr {
2294    /// Iterates through references to child expressions.
2295    pub fn children(&self) -> impl DoubleEndedIterator<Item = &Self> {
2296        let mut first = None;
2297        let mut second = None;
2298        let mut third = None;
2299        let mut variadic = None;
2300
2301        use MirScalarExpr::*;
2302        match self {
2303            Column(_, _) | Literal(_, _) | CallUnmaterializable(_) => (),
2304            CallUnary { expr, .. } => {
2305                first = Some(&**expr);
2306            }
2307            CallBinary { expr1, expr2, .. } => {
2308                first = Some(&**expr1);
2309                second = Some(&**expr2);
2310            }
2311            CallVariadic { exprs, .. } => {
2312                variadic = Some(exprs);
2313            }
2314            If { cond, then, els } => {
2315                first = Some(&**cond);
2316                second = Some(&**then);
2317                third = Some(&**els);
2318            }
2319        }
2320
2321        first
2322            .into_iter()
2323            .chain(second)
2324            .chain(third)
2325            .chain(variadic.into_iter().flatten())
2326    }
2327
2328    /// Iterates through mutable references to child expressions.
2329    pub fn children_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut Self> {
2330        let mut first = None;
2331        let mut second = None;
2332        let mut third = None;
2333        let mut variadic = None;
2334
2335        use MirScalarExpr::*;
2336        match self {
2337            Column(_, _) | Literal(_, _) | CallUnmaterializable(_) => (),
2338            CallUnary { expr, .. } => {
2339                first = Some(&mut **expr);
2340            }
2341            CallBinary { expr1, expr2, .. } => {
2342                first = Some(&mut **expr1);
2343                second = Some(&mut **expr2);
2344            }
2345            CallVariadic { exprs, .. } => {
2346                variadic = Some(exprs);
2347            }
2348            If { cond, then, els } => {
2349                first = Some(&mut **cond);
2350                second = Some(&mut **then);
2351                third = Some(&mut **els);
2352            }
2353        }
2354
2355        first
2356            .into_iter()
2357            .chain(second)
2358            .chain(third)
2359            .chain(variadic.into_iter().flatten())
2360    }
2361
2362    /// Visits all subexpressions in DFS preorder.
2363    pub fn visit_pre<F>(&self, mut f: F)
2364    where
2365        F: FnMut(&Self),
2366    {
2367        let mut worklist = vec![self];
2368        while let Some(e) = worklist.pop() {
2369            f(e);
2370            worklist.extend(e.children().rev());
2371        }
2372    }
2373
2374    /// Iterative pre-order visitor.
2375    pub fn visit_pre_mut<F: FnMut(&mut Self)>(&mut self, mut f: F) {
2376        let mut worklist = vec![self];
2377        while let Some(expr) = worklist.pop() {
2378            f(expr);
2379            worklist.extend(expr.children_mut().rev());
2380        }
2381    }
2382}
2383
2384/// Filter characteristics that are used for ordering join inputs.
2385/// This can be created for a `Vec<MirScalarExpr>`, which represents an AND of predicates.
2386///
2387/// The fields are ordered based on heuristic assumptions about their typical selectivity, so that
2388/// Ord gives the right ordering for join inputs. Bigger is better, i.e., will tend to come earlier
2389/// than other inputs.
2390#[derive(
2391    Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Serialize, Deserialize, Hash, MzReflect, Arbitrary,
2392)]
2393pub struct FilterCharacteristics {
2394    // `<expr> = <literal>` appears in the filter.
2395    // Excludes cases where NOT appears anywhere above the literal equality.
2396    literal_equality: bool,
2397    // (Assuming a random string of lower-case characters, `LIKE 'a%'` has a selectivity of 1/26.)
2398    like: bool,
2399    is_null: bool,
2400    // Number of Vec elements that involve inequality predicates. (A BETWEEN is represented as two
2401    // inequality predicates.)
2402    // Excludes cases where NOT appears around the literal inequality.
2403    // Note that for inequality predicates, some databases assume 1/3 selectivity in the absence of
2404    // concrete statistics.
2405    literal_inequality: usize,
2406    /// Any filter, except ones involving `IS NOT NULL`, because those are too common.
2407    /// Can be true by itself, or any other field being true can also make this true.
2408    /// `NOT LIKE` is only in this category.
2409    /// `!=` is only in this category.
2410    /// `NOT (a = b)` is turned into `!=` by `reduce` before us!
2411    any_filter: bool,
2412}
2413
2414impl BitOrAssign for FilterCharacteristics {
2415    fn bitor_assign(&mut self, rhs: Self) {
2416        self.literal_equality |= rhs.literal_equality;
2417        self.like |= rhs.like;
2418        self.is_null |= rhs.is_null;
2419        self.literal_inequality += rhs.literal_inequality;
2420        self.any_filter |= rhs.any_filter;
2421    }
2422}
2423
2424impl FilterCharacteristics {
2425    pub fn none() -> FilterCharacteristics {
2426        FilterCharacteristics {
2427            literal_equality: false,
2428            like: false,
2429            is_null: false,
2430            literal_inequality: 0,
2431            any_filter: false,
2432        }
2433    }
2434
2435    pub fn explain(&self) -> String {
2436        let mut e = "".to_owned();
2437        if self.literal_equality {
2438            e.push_str("e");
2439        }
2440        if self.like {
2441            e.push_str("l");
2442        }
2443        if self.is_null {
2444            e.push_str("n");
2445        }
2446        for _ in 0..self.literal_inequality {
2447            e.push_str("i");
2448        }
2449        if self.any_filter {
2450            e.push_str("f");
2451        }
2452        e
2453    }
2454
2455    pub fn filter_characteristics(
2456        filters: &Vec<MirScalarExpr>,
2457    ) -> Result<FilterCharacteristics, RecursionLimitError> {
2458        let mut literal_equality = false;
2459        let mut like = false;
2460        let mut is_null = false;
2461        let mut literal_inequality = 0;
2462        let mut any_filter = false;
2463        filters.iter().try_for_each(|f| {
2464            let mut literal_inequality_in_current_filter = false;
2465            let mut is_not_null_in_current_filter = false;
2466            f.visit_pre_with_context(
2467                false,
2468                &mut |not_in_parent_chain, expr| {
2469                    not_in_parent_chain
2470                        || matches!(
2471                            expr,
2472                            MirScalarExpr::CallUnary {
2473                                func: UnaryFunc::Not(func::Not),
2474                                ..
2475                            }
2476                        )
2477                },
2478                &mut |not_in_parent_chain, expr| {
2479                    if !not_in_parent_chain {
2480                        if expr.any_expr_eq_literal().is_some() {
2481                            literal_equality = true;
2482                        }
2483                        if expr.any_expr_ineq_literal() {
2484                            literal_inequality_in_current_filter = true;
2485                        }
2486                        if matches!(
2487                            expr,
2488                            MirScalarExpr::CallUnary {
2489                                func: UnaryFunc::IsLikeMatch(_),
2490                                ..
2491                            }
2492                        ) {
2493                            like = true;
2494                        }
2495                    };
2496                    if matches!(
2497                        expr,
2498                        MirScalarExpr::CallUnary {
2499                            func: UnaryFunc::IsNull(crate::func::IsNull),
2500                            ..
2501                        }
2502                    ) {
2503                        if *not_in_parent_chain {
2504                            is_not_null_in_current_filter = true;
2505                        } else {
2506                            is_null = true;
2507                        }
2508                    }
2509                },
2510            )?;
2511            if literal_inequality_in_current_filter {
2512                literal_inequality += 1;
2513            }
2514            if !is_not_null_in_current_filter {
2515                // We want to ignore `IS NOT NULL` for `any_filter`.
2516                any_filter = true;
2517            }
2518            Ok(())
2519        })?;
2520        Ok(FilterCharacteristics {
2521            literal_equality,
2522            like,
2523            is_null,
2524            literal_inequality,
2525            any_filter,
2526        })
2527    }
2528
2529    pub fn add_literal_equality(&mut self) {
2530        self.literal_equality = true;
2531    }
2532
2533    pub fn worst_case_scaling_factor(&self) -> f64 {
2534        let mut factor = 1.0;
2535
2536        if self.literal_equality {
2537            factor *= 0.1;
2538        }
2539
2540        if self.is_null {
2541            factor *= 0.1;
2542        }
2543
2544        if self.literal_inequality >= 2 {
2545            factor *= 0.25;
2546        } else if self.literal_inequality == 1 {
2547            factor *= 0.33;
2548        }
2549
2550        // catch various negated filters, treat them pessimistically
2551        if !(self.literal_equality || self.is_null || self.literal_inequality > 0)
2552            && self.any_filter
2553        {
2554            factor *= 0.9;
2555        }
2556
2557        factor
2558    }
2559}
2560
2561#[derive(
2562    Arbitrary,
2563    Ord,
2564    PartialOrd,
2565    Copy,
2566    Clone,
2567    Debug,
2568    Eq,
2569    PartialEq,
2570    Serialize,
2571    Deserialize,
2572    Hash,
2573    MzReflect,
2574)]
2575pub enum DomainLimit {
2576    None,
2577    Inclusive(i64),
2578    Exclusive(i64),
2579}
2580
2581impl RustType<ProtoDomainLimit> for DomainLimit {
2582    fn into_proto(&self) -> ProtoDomainLimit {
2583        use proto_domain_limit::Kind::*;
2584        let kind = match self {
2585            DomainLimit::None => None(()),
2586            DomainLimit::Inclusive(v) => Inclusive(*v),
2587            DomainLimit::Exclusive(v) => Exclusive(*v),
2588        };
2589        ProtoDomainLimit { kind: Some(kind) }
2590    }
2591
2592    fn from_proto(proto: ProtoDomainLimit) -> Result<Self, TryFromProtoError> {
2593        use proto_domain_limit::Kind::*;
2594        if let Some(kind) = proto.kind {
2595            match kind {
2596                None(()) => Ok(DomainLimit::None),
2597                Inclusive(v) => Ok(DomainLimit::Inclusive(v)),
2598                Exclusive(v) => Ok(DomainLimit::Exclusive(v)),
2599            }
2600        } else {
2601            Err(TryFromProtoError::missing_field("ProtoDomainLimit::kind"))
2602        }
2603    }
2604}
2605
2606#[derive(
2607    Arbitrary, Ord, PartialOrd, Clone, Debug, Eq, PartialEq, Serialize, Deserialize, Hash, MzReflect,
2608)]
2609pub enum EvalError {
2610    CharacterNotValidForEncoding(i32),
2611    CharacterTooLargeForEncoding(i32),
2612    DateBinOutOfRange(Box<str>),
2613    DivisionByZero,
2614    Unsupported {
2615        feature: Box<str>,
2616        discussion_no: Option<usize>,
2617    },
2618    FloatOverflow,
2619    FloatUnderflow,
2620    NumericFieldOverflow,
2621    Float32OutOfRange(Box<str>),
2622    Float64OutOfRange(Box<str>),
2623    Int16OutOfRange(Box<str>),
2624    Int32OutOfRange(Box<str>),
2625    Int64OutOfRange(Box<str>),
2626    UInt16OutOfRange(Box<str>),
2627    UInt32OutOfRange(Box<str>),
2628    UInt64OutOfRange(Box<str>),
2629    MzTimestampOutOfRange(Box<str>),
2630    MzTimestampStepOverflow,
2631    OidOutOfRange(Box<str>),
2632    IntervalOutOfRange(Box<str>),
2633    TimestampCannotBeNan,
2634    TimestampOutOfRange,
2635    DateOutOfRange,
2636    CharOutOfRange,
2637    IndexOutOfRange {
2638        provided: i32,
2639        // The last valid index position, i.e. `v.len() - 1`
2640        valid_end: i32,
2641    },
2642    InvalidBase64Equals,
2643    InvalidBase64Symbol(char),
2644    InvalidBase64EndSequence,
2645    InvalidTimezone(Box<str>),
2646    InvalidTimezoneInterval,
2647    InvalidTimezoneConversion,
2648    InvalidIanaTimezoneId(Box<str>),
2649    InvalidLayer {
2650        max_layer: usize,
2651        val: i64,
2652    },
2653    InvalidArray(InvalidArrayError),
2654    InvalidEncodingName(Box<str>),
2655    InvalidHashAlgorithm(Box<str>),
2656    InvalidByteSequence {
2657        byte_sequence: Box<str>,
2658        encoding_name: Box<str>,
2659    },
2660    InvalidJsonbCast {
2661        from: Box<str>,
2662        to: Box<str>,
2663    },
2664    InvalidRegex(Box<str>),
2665    InvalidRegexFlag(char),
2666    InvalidParameterValue(Box<str>),
2667    InvalidDatePart(Box<str>),
2668    KeyCannotBeNull,
2669    NegSqrt,
2670    NegLimit,
2671    NullCharacterNotPermitted,
2672    UnknownUnits(Box<str>),
2673    UnsupportedUnits(Box<str>, Box<str>),
2674    UnterminatedLikeEscapeSequence,
2675    Parse(ParseError),
2676    ParseHex(ParseHexError),
2677    Internal(Box<str>),
2678    InfinityOutOfDomain(Box<str>),
2679    NegativeOutOfDomain(Box<str>),
2680    ZeroOutOfDomain(Box<str>),
2681    OutOfDomain(DomainLimit, DomainLimit, Box<str>),
2682    ComplexOutOfRange(Box<str>),
2683    MultipleRowsFromSubquery,
2684    Undefined(Box<str>),
2685    LikePatternTooLong,
2686    LikeEscapeTooLong,
2687    StringValueTooLong {
2688        target_type: Box<str>,
2689        length: usize,
2690    },
2691    MultidimensionalArrayRemovalNotSupported,
2692    IncompatibleArrayDimensions {
2693        dims: Option<(usize, usize)>,
2694    },
2695    TypeFromOid(Box<str>),
2696    InvalidRange(InvalidRangeError),
2697    InvalidRoleId(Box<str>),
2698    InvalidPrivileges(Box<str>),
2699    LetRecLimitExceeded(Box<str>),
2700    MultiDimensionalArraySearch,
2701    MustNotBeNull(Box<str>),
2702    InvalidIdentifier {
2703        ident: Box<str>,
2704        detail: Option<Box<str>>,
2705    },
2706    ArrayFillWrongArraySubscripts,
2707    // TODO: propagate this check more widely throughout the expr crate
2708    MaxArraySizeExceeded(usize),
2709    DateDiffOverflow {
2710        unit: Box<str>,
2711        a: Box<str>,
2712        b: Box<str>,
2713    },
2714    // The error for ErrorIfNull; this should not be used in other contexts as a generic error
2715    // printer.
2716    IfNullError(Box<str>),
2717    LengthTooLarge,
2718    AclArrayNullElement,
2719    MzAclArrayNullElement,
2720    PrettyError(Box<str>),
2721}
2722
2723impl fmt::Display for EvalError {
2724    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2725        match self {
2726            EvalError::CharacterNotValidForEncoding(v) => {
2727                write!(f, "requested character not valid for encoding: {v}")
2728            }
2729            EvalError::CharacterTooLargeForEncoding(v) => {
2730                write!(f, "requested character too large for encoding: {v}")
2731            }
2732            EvalError::DateBinOutOfRange(message) => f.write_str(message),
2733            EvalError::DivisionByZero => f.write_str("division by zero"),
2734            EvalError::Unsupported {
2735                feature,
2736                discussion_no,
2737            } => {
2738                write!(f, "{} not yet supported", feature)?;
2739                if let Some(discussion_no) = discussion_no {
2740                    write!(
2741                        f,
2742                        ", see https://github.com/MaterializeInc/materialize/discussions/{} for more details",
2743                        discussion_no
2744                    )?;
2745                }
2746                Ok(())
2747            }
2748            EvalError::FloatOverflow => f.write_str("value out of range: overflow"),
2749            EvalError::FloatUnderflow => f.write_str("value out of range: underflow"),
2750            EvalError::NumericFieldOverflow => f.write_str("numeric field overflow"),
2751            EvalError::Float32OutOfRange(val) => write!(f, "{} real out of range", val.quoted()),
2752            EvalError::Float64OutOfRange(val) => {
2753                write!(f, "{} double precision out of range", val.quoted())
2754            }
2755            EvalError::Int16OutOfRange(val) => write!(f, "{} smallint out of range", val.quoted()),
2756            EvalError::Int32OutOfRange(val) => write!(f, "{} integer out of range", val.quoted()),
2757            EvalError::Int64OutOfRange(val) => write!(f, "{} bigint out of range", val.quoted()),
2758            EvalError::UInt16OutOfRange(val) => write!(f, "{} uint2 out of range", val.quoted()),
2759            EvalError::UInt32OutOfRange(val) => write!(f, "{} uint4 out of range", val.quoted()),
2760            EvalError::UInt64OutOfRange(val) => write!(f, "{} uint8 out of range", val.quoted()),
2761            EvalError::MzTimestampOutOfRange(val) => {
2762                write!(f, "{} mz_timestamp out of range", val.quoted())
2763            }
2764            EvalError::MzTimestampStepOverflow => f.write_str("step mz_timestamp overflow"),
2765            EvalError::OidOutOfRange(val) => write!(f, "{} OID out of range", val.quoted()),
2766            EvalError::IntervalOutOfRange(val) => {
2767                write!(f, "{} interval out of range", val.quoted())
2768            }
2769            EvalError::TimestampCannotBeNan => f.write_str("timestamp cannot be NaN"),
2770            EvalError::TimestampOutOfRange => f.write_str("timestamp out of range"),
2771            EvalError::DateOutOfRange => f.write_str("date out of range"),
2772            EvalError::CharOutOfRange => f.write_str("\"char\" out of range"),
2773            EvalError::IndexOutOfRange {
2774                provided,
2775                valid_end,
2776            } => write!(f, "index {provided} out of valid range, 0..{valid_end}",),
2777            EvalError::InvalidBase64Equals => {
2778                f.write_str("unexpected \"=\" while decoding base64 sequence")
2779            }
2780            EvalError::InvalidBase64Symbol(c) => write!(
2781                f,
2782                "invalid symbol \"{}\" found while decoding base64 sequence",
2783                c.escape_default()
2784            ),
2785            EvalError::InvalidBase64EndSequence => f.write_str("invalid base64 end sequence"),
2786            EvalError::InvalidJsonbCast { from, to } => {
2787                write!(f, "cannot cast jsonb {} to type {}", from, to)
2788            }
2789            EvalError::InvalidTimezone(tz) => write!(f, "invalid time zone '{}'", tz),
2790            EvalError::InvalidTimezoneInterval => {
2791                f.write_str("timezone interval must not contain months or years")
2792            }
2793            EvalError::InvalidTimezoneConversion => f.write_str("invalid timezone conversion"),
2794            EvalError::InvalidIanaTimezoneId(tz) => {
2795                write!(f, "invalid IANA Time Zone Database identifier: '{}'", tz)
2796            }
2797            EvalError::InvalidLayer { max_layer, val } => write!(
2798                f,
2799                "invalid layer: {}; must use value within [1, {}]",
2800                val, max_layer
2801            ),
2802            EvalError::InvalidArray(e) => e.fmt(f),
2803            EvalError::InvalidEncodingName(name) => write!(f, "invalid encoding name '{}'", name),
2804            EvalError::InvalidHashAlgorithm(alg) => write!(f, "invalid hash algorithm '{}'", alg),
2805            EvalError::InvalidByteSequence {
2806                byte_sequence,
2807                encoding_name,
2808            } => write!(
2809                f,
2810                "invalid byte sequence '{}' for encoding '{}'",
2811                byte_sequence, encoding_name
2812            ),
2813            EvalError::InvalidDatePart(part) => write!(f, "invalid datepart {}", part.quoted()),
2814            EvalError::KeyCannotBeNull => f.write_str("key cannot be null"),
2815            EvalError::NegSqrt => f.write_str("cannot take square root of a negative number"),
2816            EvalError::NegLimit => f.write_str("LIMIT must not be negative"),
2817            EvalError::NullCharacterNotPermitted => f.write_str("null character not permitted"),
2818            EvalError::InvalidRegex(e) => write!(f, "invalid regular expression: {}", e),
2819            EvalError::InvalidRegexFlag(c) => write!(f, "invalid regular expression flag: {}", c),
2820            EvalError::InvalidParameterValue(s) => f.write_str(s),
2821            EvalError::UnknownUnits(units) => write!(f, "unit '{}' not recognized", units),
2822            EvalError::UnsupportedUnits(units, typ) => {
2823                write!(f, "unit '{}' not supported for type {}", units, typ)
2824            }
2825            EvalError::UnterminatedLikeEscapeSequence => {
2826                f.write_str("unterminated escape sequence in LIKE")
2827            }
2828            EvalError::Parse(e) => e.fmt(f),
2829            EvalError::PrettyError(e) => e.fmt(f),
2830            EvalError::ParseHex(e) => e.fmt(f),
2831            EvalError::Internal(s) => write!(f, "internal error: {}", s),
2832            EvalError::InfinityOutOfDomain(s) => {
2833                write!(f, "function {} is only defined for finite arguments", s)
2834            }
2835            EvalError::NegativeOutOfDomain(s) => {
2836                write!(f, "function {} is not defined for negative numbers", s)
2837            }
2838            EvalError::ZeroOutOfDomain(s) => {
2839                write!(f, "function {} is not defined for zero", s)
2840            }
2841            EvalError::OutOfDomain(lower, upper, s) => {
2842                use DomainLimit::*;
2843                write!(f, "function {s} is defined for numbers ")?;
2844                match (lower, upper) {
2845                    (Inclusive(n), None) => write!(f, "greater than or equal to {n}"),
2846                    (Exclusive(n), None) => write!(f, "greater than {n}"),
2847                    (None, Inclusive(n)) => write!(f, "less than or equal to {n}"),
2848                    (None, Exclusive(n)) => write!(f, "less than {n}"),
2849                    (Inclusive(lo), Inclusive(hi)) => write!(f, "between {lo} and {hi} inclusive"),
2850                    (Exclusive(lo), Exclusive(hi)) => write!(f, "between {lo} and {hi} exclusive"),
2851                    (Inclusive(lo), Exclusive(hi)) => {
2852                        write!(f, "between {lo} inclusive and {hi} exclusive")
2853                    }
2854                    (Exclusive(lo), Inclusive(hi)) => {
2855                        write!(f, "between {lo} exclusive and {hi} inclusive")
2856                    }
2857                    (None, None) => panic!("invalid domain error"),
2858                }
2859            }
2860            EvalError::ComplexOutOfRange(s) => {
2861                write!(f, "function {} cannot return complex numbers", s)
2862            }
2863            EvalError::MultipleRowsFromSubquery => {
2864                write!(f, "more than one record produced in subquery")
2865            }
2866            EvalError::Undefined(s) => {
2867                write!(f, "{} is undefined", s)
2868            }
2869            EvalError::LikePatternTooLong => {
2870                write!(f, "LIKE pattern exceeds maximum length")
2871            }
2872            EvalError::LikeEscapeTooLong => {
2873                write!(f, "invalid escape string")
2874            }
2875            EvalError::StringValueTooLong {
2876                target_type,
2877                length,
2878            } => {
2879                write!(f, "value too long for type {}({})", target_type, length)
2880            }
2881            EvalError::MultidimensionalArrayRemovalNotSupported => {
2882                write!(
2883                    f,
2884                    "removing elements from multidimensional arrays is not supported"
2885                )
2886            }
2887            EvalError::IncompatibleArrayDimensions { dims: _ } => {
2888                write!(f, "cannot concatenate incompatible arrays")
2889            }
2890            EvalError::TypeFromOid(msg) => write!(f, "{msg}"),
2891            EvalError::InvalidRange(e) => e.fmt(f),
2892            EvalError::InvalidRoleId(msg) => write!(f, "{msg}"),
2893            EvalError::InvalidPrivileges(privilege) => {
2894                write!(f, "unrecognized privilege type: {privilege}")
2895            }
2896            EvalError::LetRecLimitExceeded(max_iters) => {
2897                write!(
2898                    f,
2899                    "Recursive query exceeded the recursion limit {}. (Use RETURN AT RECURSION LIMIT to not error, but return the current state as the final result when reaching the limit.)",
2900                    max_iters
2901                )
2902            }
2903            EvalError::MultiDimensionalArraySearch => write!(
2904                f,
2905                "searching for elements in multidimensional arrays is not supported"
2906            ),
2907            EvalError::MustNotBeNull(v) => write!(f, "{v} must not be null"),
2908            EvalError::InvalidIdentifier { ident, .. } => {
2909                write!(f, "string is not a valid identifier: {}", ident.quoted())
2910            }
2911            EvalError::ArrayFillWrongArraySubscripts => {
2912                f.write_str("wrong number of array subscripts")
2913            }
2914            EvalError::MaxArraySizeExceeded(max_size) => {
2915                write!(
2916                    f,
2917                    "array size exceeds the maximum allowed ({max_size} bytes)"
2918                )
2919            }
2920            EvalError::DateDiffOverflow { unit, a, b } => {
2921                write!(f, "datediff overflow, {unit} of {a}, {b}")
2922            }
2923            EvalError::IfNullError(s) => f.write_str(s),
2924            EvalError::LengthTooLarge => write!(f, "requested length too large"),
2925            EvalError::AclArrayNullElement => write!(f, "ACL arrays must not contain null values"),
2926            EvalError::MzAclArrayNullElement => {
2927                write!(f, "MZ_ACL arrays must not contain null values")
2928            }
2929        }
2930    }
2931}
2932
2933impl EvalError {
2934    pub fn detail(&self) -> Option<String> {
2935        match self {
2936            EvalError::IncompatibleArrayDimensions { dims: None } => Some(
2937                "Arrays with differing dimensions are not compatible for concatenation.".into(),
2938            ),
2939            EvalError::IncompatibleArrayDimensions {
2940                dims: Some((a_dims, b_dims)),
2941            } => Some(format!(
2942                "Arrays of {} and {} dimensions are not compatible for concatenation.",
2943                a_dims, b_dims
2944            )),
2945            EvalError::InvalidIdentifier { detail, .. } => detail.as_deref().map(Into::into),
2946            EvalError::ArrayFillWrongArraySubscripts => {
2947                Some("Low bound array has different size than dimensions array.".into())
2948            }
2949            _ => None,
2950        }
2951    }
2952
2953    pub fn hint(&self) -> Option<String> {
2954        match self {
2955            EvalError::InvalidBase64EndSequence => Some(
2956                "Input data is missing padding, is truncated, or is otherwise corrupted.".into(),
2957            ),
2958            EvalError::LikeEscapeTooLong => {
2959                Some("Escape string must be empty or one character.".into())
2960            }
2961            EvalError::MzTimestampOutOfRange(_) => Some(
2962                "Integer, numeric, and text casts to mz_timestamp must be in the form of whole \
2963                milliseconds since the Unix epoch. Values with fractional parts cannot be \
2964                converted to mz_timestamp."
2965                    .into(),
2966            ),
2967            _ => None,
2968        }
2969    }
2970}
2971
2972impl std::error::Error for EvalError {}
2973
2974impl From<ParseError> for EvalError {
2975    fn from(e: ParseError) -> EvalError {
2976        EvalError::Parse(e)
2977    }
2978}
2979
2980impl From<ParseHexError> for EvalError {
2981    fn from(e: ParseHexError) -> EvalError {
2982        EvalError::ParseHex(e)
2983    }
2984}
2985
2986impl From<InvalidArrayError> for EvalError {
2987    fn from(e: InvalidArrayError) -> EvalError {
2988        EvalError::InvalidArray(e)
2989    }
2990}
2991
2992impl From<regex::Error> for EvalError {
2993    fn from(e: regex::Error) -> EvalError {
2994        EvalError::InvalidRegex(e.to_string().into())
2995    }
2996}
2997
2998impl From<TypeFromOidError> for EvalError {
2999    fn from(e: TypeFromOidError) -> EvalError {
3000        EvalError::TypeFromOid(e.to_string().into())
3001    }
3002}
3003
3004impl From<DateError> for EvalError {
3005    fn from(e: DateError) -> EvalError {
3006        match e {
3007            DateError::OutOfRange => EvalError::DateOutOfRange,
3008        }
3009    }
3010}
3011
3012impl From<TimestampError> for EvalError {
3013    fn from(e: TimestampError) -> EvalError {
3014        match e {
3015            TimestampError::OutOfRange => EvalError::TimestampOutOfRange,
3016        }
3017    }
3018}
3019
3020impl From<InvalidRangeError> for EvalError {
3021    fn from(e: InvalidRangeError) -> EvalError {
3022        EvalError::InvalidRange(e)
3023    }
3024}
3025
3026impl RustType<ProtoEvalError> for EvalError {
3027    fn into_proto(&self) -> ProtoEvalError {
3028        use proto_eval_error::Kind::*;
3029        use proto_eval_error::*;
3030        let kind = match self {
3031            EvalError::CharacterNotValidForEncoding(v) => CharacterNotValidForEncoding(*v),
3032            EvalError::CharacterTooLargeForEncoding(v) => CharacterTooLargeForEncoding(*v),
3033            EvalError::DateBinOutOfRange(v) => DateBinOutOfRange(v.into_proto()),
3034            EvalError::DivisionByZero => DivisionByZero(()),
3035            EvalError::Unsupported {
3036                feature,
3037                discussion_no,
3038            } => Unsupported(ProtoUnsupported {
3039                feature: feature.into_proto(),
3040                discussion_no: discussion_no.into_proto(),
3041            }),
3042            EvalError::FloatOverflow => FloatOverflow(()),
3043            EvalError::FloatUnderflow => FloatUnderflow(()),
3044            EvalError::NumericFieldOverflow => NumericFieldOverflow(()),
3045            EvalError::Float32OutOfRange(val) => Float32OutOfRange(ProtoValueOutOfRange {
3046                value: val.to_string(),
3047            }),
3048            EvalError::Float64OutOfRange(val) => Float64OutOfRange(ProtoValueOutOfRange {
3049                value: val.to_string(),
3050            }),
3051            EvalError::Int16OutOfRange(val) => Int16OutOfRange(ProtoValueOutOfRange {
3052                value: val.to_string(),
3053            }),
3054            EvalError::Int32OutOfRange(val) => Int32OutOfRange(ProtoValueOutOfRange {
3055                value: val.to_string(),
3056            }),
3057            EvalError::Int64OutOfRange(val) => Int64OutOfRange(ProtoValueOutOfRange {
3058                value: val.to_string(),
3059            }),
3060            EvalError::UInt16OutOfRange(val) => Uint16OutOfRange(ProtoValueOutOfRange {
3061                value: val.to_string(),
3062            }),
3063            EvalError::UInt32OutOfRange(val) => Uint32OutOfRange(ProtoValueOutOfRange {
3064                value: val.to_string(),
3065            }),
3066            EvalError::UInt64OutOfRange(val) => Uint64OutOfRange(ProtoValueOutOfRange {
3067                value: val.to_string(),
3068            }),
3069            EvalError::MzTimestampOutOfRange(val) => MzTimestampOutOfRange(ProtoValueOutOfRange {
3070                value: val.to_string(),
3071            }),
3072            EvalError::MzTimestampStepOverflow => MzTimestampStepOverflow(()),
3073            EvalError::OidOutOfRange(val) => OidOutOfRange(ProtoValueOutOfRange {
3074                value: val.to_string(),
3075            }),
3076            EvalError::IntervalOutOfRange(val) => IntervalOutOfRange(ProtoValueOutOfRange {
3077                value: val.to_string(),
3078            }),
3079            EvalError::TimestampCannotBeNan => TimestampCannotBeNan(()),
3080            EvalError::TimestampOutOfRange => TimestampOutOfRange(()),
3081            EvalError::DateOutOfRange => DateOutOfRange(()),
3082            EvalError::CharOutOfRange => CharOutOfRange(()),
3083            EvalError::IndexOutOfRange {
3084                provided,
3085                valid_end,
3086            } => IndexOutOfRange(ProtoIndexOutOfRange {
3087                provided: *provided,
3088                valid_end: *valid_end,
3089            }),
3090            EvalError::InvalidBase64Equals => InvalidBase64Equals(()),
3091            EvalError::InvalidBase64Symbol(sym) => InvalidBase64Symbol(sym.into_proto()),
3092            EvalError::InvalidBase64EndSequence => InvalidBase64EndSequence(()),
3093            EvalError::InvalidTimezone(tz) => InvalidTimezone(tz.into_proto()),
3094            EvalError::InvalidTimezoneInterval => InvalidTimezoneInterval(()),
3095            EvalError::InvalidTimezoneConversion => InvalidTimezoneConversion(()),
3096            EvalError::InvalidLayer { max_layer, val } => InvalidLayer(ProtoInvalidLayer {
3097                max_layer: max_layer.into_proto(),
3098                val: *val,
3099            }),
3100            EvalError::InvalidArray(error) => InvalidArray(error.into_proto()),
3101            EvalError::InvalidEncodingName(v) => InvalidEncodingName(v.into_proto()),
3102            EvalError::InvalidHashAlgorithm(v) => InvalidHashAlgorithm(v.into_proto()),
3103            EvalError::InvalidByteSequence {
3104                byte_sequence,
3105                encoding_name,
3106            } => InvalidByteSequence(ProtoInvalidByteSequence {
3107                byte_sequence: byte_sequence.into_proto(),
3108                encoding_name: encoding_name.into_proto(),
3109            }),
3110            EvalError::InvalidJsonbCast { from, to } => InvalidJsonbCast(ProtoInvalidJsonbCast {
3111                from: from.into_proto(),
3112                to: to.into_proto(),
3113            }),
3114            EvalError::InvalidRegex(v) => InvalidRegex(v.into_proto()),
3115            EvalError::InvalidRegexFlag(v) => InvalidRegexFlag(v.into_proto()),
3116            EvalError::InvalidParameterValue(v) => InvalidParameterValue(v.into_proto()),
3117            EvalError::InvalidDatePart(part) => InvalidDatePart(part.into_proto()),
3118            EvalError::KeyCannotBeNull => KeyCannotBeNull(()),
3119            EvalError::NegSqrt => NegSqrt(()),
3120            EvalError::NegLimit => NegLimit(()),
3121            EvalError::NullCharacterNotPermitted => NullCharacterNotPermitted(()),
3122            EvalError::UnknownUnits(v) => UnknownUnits(v.into_proto()),
3123            EvalError::UnsupportedUnits(units, typ) => UnsupportedUnits(ProtoUnsupportedUnits {
3124                units: units.into_proto(),
3125                typ: typ.into_proto(),
3126            }),
3127            EvalError::UnterminatedLikeEscapeSequence => UnterminatedLikeEscapeSequence(()),
3128            EvalError::Parse(error) => Parse(error.into_proto()),
3129            EvalError::PrettyError(error) => PrettyError(error.into_proto()),
3130            EvalError::ParseHex(error) => ParseHex(error.into_proto()),
3131            EvalError::Internal(v) => Internal(v.into_proto()),
3132            EvalError::InfinityOutOfDomain(v) => InfinityOutOfDomain(v.into_proto()),
3133            EvalError::NegativeOutOfDomain(v) => NegativeOutOfDomain(v.into_proto()),
3134            EvalError::ZeroOutOfDomain(v) => ZeroOutOfDomain(v.into_proto()),
3135            EvalError::OutOfDomain(lower, upper, id) => OutOfDomain(ProtoOutOfDomain {
3136                lower: Some(lower.into_proto()),
3137                upper: Some(upper.into_proto()),
3138                id: id.into_proto(),
3139            }),
3140            EvalError::ComplexOutOfRange(v) => ComplexOutOfRange(v.into_proto()),
3141            EvalError::MultipleRowsFromSubquery => MultipleRowsFromSubquery(()),
3142            EvalError::Undefined(v) => Undefined(v.into_proto()),
3143            EvalError::LikePatternTooLong => LikePatternTooLong(()),
3144            EvalError::LikeEscapeTooLong => LikeEscapeTooLong(()),
3145            EvalError::StringValueTooLong {
3146                target_type,
3147                length,
3148            } => StringValueTooLong(ProtoStringValueTooLong {
3149                target_type: target_type.into_proto(),
3150                length: length.into_proto(),
3151            }),
3152            EvalError::MultidimensionalArrayRemovalNotSupported => {
3153                MultidimensionalArrayRemovalNotSupported(())
3154            }
3155            EvalError::IncompatibleArrayDimensions { dims } => {
3156                IncompatibleArrayDimensions(ProtoIncompatibleArrayDimensions {
3157                    dims: dims.into_proto(),
3158                })
3159            }
3160            EvalError::TypeFromOid(v) => TypeFromOid(v.into_proto()),
3161            EvalError::InvalidRange(error) => InvalidRange(error.into_proto()),
3162            EvalError::InvalidRoleId(v) => InvalidRoleId(v.into_proto()),
3163            EvalError::InvalidPrivileges(v) => InvalidPrivileges(v.into_proto()),
3164            EvalError::LetRecLimitExceeded(v) => WmrRecursionLimitExceeded(v.into_proto()),
3165            EvalError::MultiDimensionalArraySearch => MultiDimensionalArraySearch(()),
3166            EvalError::MustNotBeNull(v) => MustNotBeNull(v.into_proto()),
3167            EvalError::InvalidIdentifier { ident, detail } => {
3168                InvalidIdentifier(ProtoInvalidIdentifier {
3169                    ident: ident.into_proto(),
3170                    detail: detail.into_proto(),
3171                })
3172            }
3173            EvalError::ArrayFillWrongArraySubscripts => ArrayFillWrongArraySubscripts(()),
3174            EvalError::MaxArraySizeExceeded(max_size) => {
3175                MaxArraySizeExceeded(u64::cast_from(*max_size))
3176            }
3177            EvalError::DateDiffOverflow { unit, a, b } => DateDiffOverflow(ProtoDateDiffOverflow {
3178                unit: unit.into_proto(),
3179                a: a.into_proto(),
3180                b: b.into_proto(),
3181            }),
3182            EvalError::IfNullError(s) => IfNullError(s.into_proto()),
3183            EvalError::LengthTooLarge => LengthTooLarge(()),
3184            EvalError::AclArrayNullElement => AclArrayNullElement(()),
3185            EvalError::MzAclArrayNullElement => MzAclArrayNullElement(()),
3186            EvalError::InvalidIanaTimezoneId(s) => InvalidIanaTimezoneId(s.into_proto()),
3187        };
3188        ProtoEvalError { kind: Some(kind) }
3189    }
3190
3191    fn from_proto(proto: ProtoEvalError) -> Result<Self, TryFromProtoError> {
3192        use proto_eval_error::Kind::*;
3193        match proto.kind {
3194            Some(kind) => match kind {
3195                CharacterNotValidForEncoding(v) => Ok(EvalError::CharacterNotValidForEncoding(v)),
3196                CharacterTooLargeForEncoding(v) => Ok(EvalError::CharacterTooLargeForEncoding(v)),
3197                DateBinOutOfRange(v) => Ok(EvalError::DateBinOutOfRange(v.into())),
3198                DivisionByZero(()) => Ok(EvalError::DivisionByZero),
3199                Unsupported(v) => Ok(EvalError::Unsupported {
3200                    feature: v.feature.into(),
3201                    discussion_no: v.discussion_no.into_rust()?,
3202                }),
3203                FloatOverflow(()) => Ok(EvalError::FloatOverflow),
3204                FloatUnderflow(()) => Ok(EvalError::FloatUnderflow),
3205                NumericFieldOverflow(()) => Ok(EvalError::NumericFieldOverflow),
3206                Float32OutOfRange(val) => Ok(EvalError::Float32OutOfRange(val.value.into())),
3207                Float64OutOfRange(val) => Ok(EvalError::Float64OutOfRange(val.value.into())),
3208                Int16OutOfRange(val) => Ok(EvalError::Int16OutOfRange(val.value.into())),
3209                Int32OutOfRange(val) => Ok(EvalError::Int32OutOfRange(val.value.into())),
3210                Int64OutOfRange(val) => Ok(EvalError::Int64OutOfRange(val.value.into())),
3211                Uint16OutOfRange(val) => Ok(EvalError::UInt16OutOfRange(val.value.into())),
3212                Uint32OutOfRange(val) => Ok(EvalError::UInt32OutOfRange(val.value.into())),
3213                Uint64OutOfRange(val) => Ok(EvalError::UInt64OutOfRange(val.value.into())),
3214                MzTimestampOutOfRange(val) => {
3215                    Ok(EvalError::MzTimestampOutOfRange(val.value.into()))
3216                }
3217                MzTimestampStepOverflow(()) => Ok(EvalError::MzTimestampStepOverflow),
3218                OidOutOfRange(val) => Ok(EvalError::OidOutOfRange(val.value.into())),
3219                IntervalOutOfRange(val) => Ok(EvalError::IntervalOutOfRange(val.value.into())),
3220                TimestampCannotBeNan(()) => Ok(EvalError::TimestampCannotBeNan),
3221                TimestampOutOfRange(()) => Ok(EvalError::TimestampOutOfRange),
3222                DateOutOfRange(()) => Ok(EvalError::DateOutOfRange),
3223                CharOutOfRange(()) => Ok(EvalError::CharOutOfRange),
3224                IndexOutOfRange(v) => Ok(EvalError::IndexOutOfRange {
3225                    provided: v.provided,
3226                    valid_end: v.valid_end,
3227                }),
3228                InvalidBase64Equals(()) => Ok(EvalError::InvalidBase64Equals),
3229                InvalidBase64Symbol(v) => char::from_proto(v).map(EvalError::InvalidBase64Symbol),
3230                InvalidBase64EndSequence(()) => Ok(EvalError::InvalidBase64EndSequence),
3231                InvalidTimezone(v) => Ok(EvalError::InvalidTimezone(v.into())),
3232                InvalidTimezoneInterval(()) => Ok(EvalError::InvalidTimezoneInterval),
3233                InvalidTimezoneConversion(()) => Ok(EvalError::InvalidTimezoneConversion),
3234                InvalidLayer(v) => Ok(EvalError::InvalidLayer {
3235                    max_layer: usize::from_proto(v.max_layer)?,
3236                    val: v.val,
3237                }),
3238                InvalidArray(error) => Ok(EvalError::InvalidArray(error.into_rust()?)),
3239                InvalidEncodingName(v) => Ok(EvalError::InvalidEncodingName(v.into())),
3240                InvalidHashAlgorithm(v) => Ok(EvalError::InvalidHashAlgorithm(v.into())),
3241                InvalidByteSequence(v) => Ok(EvalError::InvalidByteSequence {
3242                    byte_sequence: v.byte_sequence.into(),
3243                    encoding_name: v.encoding_name.into(),
3244                }),
3245                InvalidJsonbCast(v) => Ok(EvalError::InvalidJsonbCast {
3246                    from: v.from.into(),
3247                    to: v.to.into(),
3248                }),
3249                InvalidRegex(v) => Ok(EvalError::InvalidRegex(v.into())),
3250                InvalidRegexFlag(v) => Ok(EvalError::InvalidRegexFlag(char::from_proto(v)?)),
3251                InvalidParameterValue(v) => Ok(EvalError::InvalidParameterValue(v.into())),
3252                InvalidDatePart(part) => Ok(EvalError::InvalidDatePart(part.into())),
3253                KeyCannotBeNull(()) => Ok(EvalError::KeyCannotBeNull),
3254                NegSqrt(()) => Ok(EvalError::NegSqrt),
3255                NegLimit(()) => Ok(EvalError::NegLimit),
3256                NullCharacterNotPermitted(()) => Ok(EvalError::NullCharacterNotPermitted),
3257                UnknownUnits(v) => Ok(EvalError::UnknownUnits(v.into())),
3258                UnsupportedUnits(v) => {
3259                    Ok(EvalError::UnsupportedUnits(v.units.into(), v.typ.into()))
3260                }
3261                UnterminatedLikeEscapeSequence(()) => Ok(EvalError::UnterminatedLikeEscapeSequence),
3262                Parse(error) => Ok(EvalError::Parse(error.into_rust()?)),
3263                ParseHex(error) => Ok(EvalError::ParseHex(error.into_rust()?)),
3264                Internal(v) => Ok(EvalError::Internal(v.into())),
3265                InfinityOutOfDomain(v) => Ok(EvalError::InfinityOutOfDomain(v.into())),
3266                NegativeOutOfDomain(v) => Ok(EvalError::NegativeOutOfDomain(v.into())),
3267                ZeroOutOfDomain(v) => Ok(EvalError::ZeroOutOfDomain(v.into())),
3268                OutOfDomain(v) => Ok(EvalError::OutOfDomain(
3269                    v.lower.into_rust_if_some("ProtoDomainLimit::lower")?,
3270                    v.upper.into_rust_if_some("ProtoDomainLimit::upper")?,
3271                    v.id.into(),
3272                )),
3273                ComplexOutOfRange(v) => Ok(EvalError::ComplexOutOfRange(v.into())),
3274                MultipleRowsFromSubquery(()) => Ok(EvalError::MultipleRowsFromSubquery),
3275                Undefined(v) => Ok(EvalError::Undefined(v.into())),
3276                LikePatternTooLong(()) => Ok(EvalError::LikePatternTooLong),
3277                LikeEscapeTooLong(()) => Ok(EvalError::LikeEscapeTooLong),
3278                StringValueTooLong(v) => Ok(EvalError::StringValueTooLong {
3279                    target_type: v.target_type.into(),
3280                    length: usize::from_proto(v.length)?,
3281                }),
3282                MultidimensionalArrayRemovalNotSupported(()) => {
3283                    Ok(EvalError::MultidimensionalArrayRemovalNotSupported)
3284                }
3285                IncompatibleArrayDimensions(v) => Ok(EvalError::IncompatibleArrayDimensions {
3286                    dims: v.dims.into_rust()?,
3287                }),
3288                TypeFromOid(v) => Ok(EvalError::TypeFromOid(v.into())),
3289                InvalidRange(e) => Ok(EvalError::InvalidRange(e.into_rust()?)),
3290                InvalidRoleId(v) => Ok(EvalError::InvalidRoleId(v.into())),
3291                InvalidPrivileges(v) => Ok(EvalError::InvalidPrivileges(v.into())),
3292                WmrRecursionLimitExceeded(v) => Ok(EvalError::LetRecLimitExceeded(v.into())),
3293                MultiDimensionalArraySearch(()) => Ok(EvalError::MultiDimensionalArraySearch),
3294                MustNotBeNull(v) => Ok(EvalError::MustNotBeNull(v.into())),
3295                InvalidIdentifier(v) => Ok(EvalError::InvalidIdentifier {
3296                    ident: v.ident.into(),
3297                    detail: v.detail.into_rust()?,
3298                }),
3299                ArrayFillWrongArraySubscripts(()) => Ok(EvalError::ArrayFillWrongArraySubscripts),
3300                MaxArraySizeExceeded(max_size) => {
3301                    Ok(EvalError::MaxArraySizeExceeded(usize::cast_from(max_size)))
3302                }
3303                DateDiffOverflow(v) => Ok(EvalError::DateDiffOverflow {
3304                    unit: v.unit.into(),
3305                    a: v.a.into(),
3306                    b: v.b.into(),
3307                }),
3308                IfNullError(v) => Ok(EvalError::IfNullError(v.into())),
3309                LengthTooLarge(()) => Ok(EvalError::LengthTooLarge),
3310                AclArrayNullElement(()) => Ok(EvalError::AclArrayNullElement),
3311                MzAclArrayNullElement(()) => Ok(EvalError::MzAclArrayNullElement),
3312                InvalidIanaTimezoneId(s) => Ok(EvalError::InvalidIanaTimezoneId(s.into())),
3313                PrettyError(s) => Ok(EvalError::PrettyError(s.into())),
3314            },
3315            None => Err(TryFromProtoError::missing_field("ProtoEvalError::kind")),
3316        }
3317    }
3318}
3319
3320impl RustType<ProtoDims> for (usize, usize) {
3321    fn into_proto(&self) -> ProtoDims {
3322        ProtoDims {
3323            f0: self.0.into_proto(),
3324            f1: self.1.into_proto(),
3325        }
3326    }
3327
3328    fn from_proto(proto: ProtoDims) -> Result<Self, TryFromProtoError> {
3329        Ok((proto.f0.into_rust()?, proto.f1.into_rust()?))
3330    }
3331}
3332
3333#[cfg(test)]
3334mod tests {
3335    use mz_ore::assert_ok;
3336    use mz_proto::protobuf_roundtrip;
3337
3338    use super::*;
3339
3340    #[mz_ore::test]
3341    #[cfg_attr(miri, ignore)] // error: unsupported operation: can't call foreign function `rust_psm_stack_pointer` on OS `linux`
3342    fn test_reduce() {
3343        let relation_type = vec![
3344            ScalarType::Int64.nullable(true),
3345            ScalarType::Int64.nullable(true),
3346            ScalarType::Int64.nullable(false),
3347        ];
3348        let col = MirScalarExpr::column;
3349        let err = |e| MirScalarExpr::literal(Err(e), ScalarType::Int64);
3350        let lit = |i| MirScalarExpr::literal_ok(Datum::Int64(i), ScalarType::Int64);
3351        let null = || MirScalarExpr::literal_null(ScalarType::Int64);
3352
3353        struct TestCase {
3354            input: MirScalarExpr,
3355            output: MirScalarExpr,
3356        }
3357
3358        let test_cases = vec![
3359            TestCase {
3360                input: MirScalarExpr::CallVariadic {
3361                    func: VariadicFunc::Coalesce,
3362                    exprs: vec![lit(1)],
3363                },
3364                output: lit(1),
3365            },
3366            TestCase {
3367                input: MirScalarExpr::CallVariadic {
3368                    func: VariadicFunc::Coalesce,
3369                    exprs: vec![lit(1), lit(2)],
3370                },
3371                output: lit(1),
3372            },
3373            TestCase {
3374                input: MirScalarExpr::CallVariadic {
3375                    func: VariadicFunc::Coalesce,
3376                    exprs: vec![null(), lit(2), null()],
3377                },
3378                output: lit(2),
3379            },
3380            TestCase {
3381                input: MirScalarExpr::CallVariadic {
3382                    func: VariadicFunc::Coalesce,
3383                    exprs: vec![null(), col(0), null(), col(1), lit(2), lit(3)],
3384                },
3385                output: MirScalarExpr::CallVariadic {
3386                    func: VariadicFunc::Coalesce,
3387                    exprs: vec![col(0), col(1), lit(2)],
3388                },
3389            },
3390            TestCase {
3391                input: MirScalarExpr::CallVariadic {
3392                    func: VariadicFunc::Coalesce,
3393                    exprs: vec![col(0), col(2), col(1)],
3394                },
3395                output: MirScalarExpr::CallVariadic {
3396                    func: VariadicFunc::Coalesce,
3397                    exprs: vec![col(0), col(2)],
3398                },
3399            },
3400            TestCase {
3401                input: MirScalarExpr::CallVariadic {
3402                    func: VariadicFunc::Coalesce,
3403                    exprs: vec![lit(1), err(EvalError::DivisionByZero)],
3404                },
3405                output: lit(1),
3406            },
3407            TestCase {
3408                input: MirScalarExpr::CallVariadic {
3409                    func: VariadicFunc::Coalesce,
3410                    exprs: vec![
3411                        null(),
3412                        err(EvalError::DivisionByZero),
3413                        err(EvalError::NumericFieldOverflow),
3414                    ],
3415                },
3416                output: err(EvalError::DivisionByZero),
3417            },
3418        ];
3419
3420        for tc in test_cases {
3421            let mut actual = tc.input.clone();
3422            actual.reduce(&relation_type);
3423            assert!(
3424                actual == tc.output,
3425                "input: {}\nactual: {}\nexpected: {}",
3426                tc.input,
3427                actual,
3428                tc.output
3429            );
3430        }
3431    }
3432
3433    proptest! {
3434        #[mz_ore::test]
3435        #[cfg_attr(miri, ignore)] // error: unsupported operation: can't call foreign function `decContextDefault` on OS `linux`
3436        fn mir_scalar_expr_protobuf_roundtrip(expect in any::<MirScalarExpr>()) {
3437            let actual = protobuf_roundtrip::<_, ProtoMirScalarExpr>(&expect);
3438            assert_ok!(actual);
3439            assert_eq!(actual.unwrap(), expect);
3440        }
3441    }
3442
3443    proptest! {
3444        #[mz_ore::test]
3445        fn domain_limit_protobuf_roundtrip(expect in any::<DomainLimit>()) {
3446            let actual = protobuf_roundtrip::<_, ProtoDomainLimit>(&expect);
3447            assert_ok!(actual);
3448            assert_eq!(actual.unwrap(), expect);
3449        }
3450    }
3451
3452    proptest! {
3453        #[mz_ore::test]
3454        #[cfg_attr(miri, ignore)] // too slow
3455        fn eval_error_protobuf_roundtrip(expect in any::<EvalError>()) {
3456            let actual = protobuf_roundtrip::<_, ProtoEvalError>(&expect);
3457            assert_ok!(actual);
3458            assert_eq!(actual.unwrap(), expect);
3459        }
3460    }
3461}