Skip to main content

vortex_array/expr/
bound_expression.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt;
5use std::fmt::Display;
6use std::fmt::Formatter;
7use std::hash::Hash;
8use std::hash::Hasher;
9use std::sync::Arc;
10
11use itertools::Itertools;
12use vortex_error::VortexExpect;
13use vortex_error::VortexResult;
14use vortex_error::vortex_ensure;
15
16use crate::dtype::DType;
17use crate::expr::Expression;
18use crate::expr::display::DisplayTreeExpr;
19use crate::expr::expression::unbound_variable;
20use crate::expr::scope::Scope;
21use crate::expr::traversal::TraversalOrder;
22use crate::expr::traversal::pre_order_visit_down;
23use crate::scalar_fn::EmptyOptions;
24use crate::scalar_fn::ExpressionReduceNode;
25use crate::scalar_fn::ReduceNode;
26use crate::scalar_fn::ReduceNodeValidity;
27use crate::scalar_fn::ScalarFnRef;
28use crate::scalar_fn::ScalarFnVTable;
29use crate::scalar_fn::ScalarFnVTableExt;
30use crate::scalar_fn::fns::is_not_null::IsNotNull;
31
32/// An [`Expression`] that has been type-checked against a [`Scope`].
33///
34/// Every node carries its own dtype, so reading one is a field access rather than a walk of the
35/// subtree. Holding a `BoundExpression` is proof that the whole tree type-checked.
36///
37/// Binding is purely logical: it deals only in [`DType`]s and never sees an array, a length, or an
38/// encoding.
39#[derive(Clone, Debug, PartialEq, Eq, Hash)]
40pub enum BoundExpression {
41    /// A scalar function applied to bound children.
42    Scalar {
43        /// The dtype this node evaluates to.
44        dtype: DType,
45        /// The scalar function for this node.
46        scalar_fn: ScalarFnRef,
47        /// The bound children, in argument order.
48        ///
49        /// Sharing keeps clones cheap even though the iterative [`Drop`] implementation prevents
50        /// consumers from destructuring a `BoundExpression` by value.
51        children: Arc<Vec<BoundExpression>>,
52    },
53    /// The scope itself. Its dtype is the scope's root dtype.
54    Root {
55        /// The dtype this node evaluates to.
56        dtype: DType,
57    },
58}
59
60/// A bound-expression wrapper that compares shared tree identity instead of structure.
61#[derive(Clone, Debug)]
62pub struct ExactBoundExpr(pub BoundExpression);
63
64impl PartialEq for ExactBoundExpr {
65    fn eq(&self, other: &Self) -> bool {
66        match (&self.0, &other.0) {
67            (
68                BoundExpression::Root { dtype: lhs_dtype },
69                BoundExpression::Root { dtype: rhs_dtype },
70            ) => lhs_dtype == rhs_dtype,
71            (
72                BoundExpression::Scalar {
73                    dtype: lhs_dtype,
74                    scalar_fn: lhs_fn,
75                    children: lhs_children,
76                },
77                BoundExpression::Scalar {
78                    dtype: rhs_dtype,
79                    scalar_fn: rhs_fn,
80                    children: rhs_children,
81                },
82            ) => {
83                lhs_fn == rhs_fn
84                    && Arc::ptr_eq(lhs_children, rhs_children)
85                    && lhs_dtype == rhs_dtype
86            }
87            _ => false,
88        }
89    }
90}
91
92impl Eq for ExactBoundExpr {}
93
94impl Hash for ExactBoundExpr {
95    fn hash<H: Hasher>(&self, state: &mut H) {
96        // DType differences are resolved by equality. Omitting the potentially lazy dtype keeps
97        // identity-keyed cache lookups from deserializing an entire schema just to compute a hash.
98        match &self.0 {
99            BoundExpression::Root { .. } => state.write_u8(0),
100            BoundExpression::Scalar {
101                scalar_fn,
102                children,
103                ..
104            } => {
105                state.write_u8(1);
106                scalar_fn.hash(state);
107                Arc::as_ptr(children).hash(state);
108            }
109        }
110    }
111}
112
113impl BoundExpression {
114    /// Create a bound root expression with the given dtype.
115    pub fn new_root(dtype: DType) -> Self {
116        Self::Root { dtype }
117    }
118
119    /// Create a bound scalar node from a scalar function and already-bound children.
120    pub fn try_new(
121        scalar_fn: ScalarFnRef,
122        children: impl IntoIterator<Item = BoundExpression>,
123    ) -> VortexResult<Self> {
124        Self::try_new_vec(scalar_fn, children.into_iter().collect())
125    }
126
127    fn try_new_vec(scalar_fn: ScalarFnRef, children: Vec<BoundExpression>) -> VortexResult<Self> {
128        vortex_ensure!(
129            scalar_fn.signature().arity().matches(children.len()),
130            "Expression arity mismatch: expected {} children but got {}",
131            scalar_fn.signature().arity(),
132            children.len()
133        );
134
135        let arg_dtypes = children
136            .iter()
137            .map(|child| child.dtype().clone())
138            .collect_vec();
139        let scalar_fn = scalar_fn.bind_options(&arg_dtypes)?;
140        let dtype = scalar_fn.return_dtype(&arg_dtypes)?;
141
142        Ok(Self::Scalar {
143            dtype,
144            scalar_fn,
145            children: children.into(),
146        })
147    }
148
149    /// Rebuild this node with new bound children, recomputing its dtype.
150    pub fn with_children(
151        self,
152        children: impl IntoIterator<Item = BoundExpression>,
153    ) -> VortexResult<Self> {
154        let children = Vec::from_iter(children);
155        let BoundExpression::Scalar { scalar_fn, .. } = &self else {
156            vortex_ensure!(
157                children.is_empty(),
158                "Root expression cannot have {} children",
159                children.len()
160            );
161            return Ok(self);
162        };
163
164        Self::try_new_vec(scalar_fn.clone(), children)
165    }
166
167    /// The dtype this expression evaluates to.
168    pub fn dtype(&self) -> &DType {
169        match self {
170            Self::Scalar { dtype, .. } | Self::Root { dtype } => dtype,
171        }
172    }
173
174    /// The bound children of this node, in argument order. Empty for [`BoundExpression::Root`].
175    pub fn children(&self) -> &[BoundExpression] {
176        match self {
177            Self::Scalar { children, .. } => children.as_slice(),
178            Self::Root { .. } => &[],
179        }
180    }
181
182    /// Return the child at `index`.
183    pub fn child(&self, index: usize) -> &BoundExpression {
184        &self.children()[index]
185    }
186
187    /// The scalar function for this node, or `None` if it is the scope root.
188    pub fn as_scalar(&self) -> Option<&ScalarFnRef> {
189        match self {
190            Self::Scalar { scalar_fn, .. } => Some(scalar_fn),
191            Self::Root { .. } => None,
192        }
193    }
194
195    /// Return whether this node uses the given scalar-function vtable.
196    pub fn is<V: ScalarFnVTable>(&self) -> bool {
197        self.as_scalar().is_some_and(ScalarFnRef::is::<V>)
198    }
199
200    /// Return whether this expression tree contains a node using the given scalar-function vtable.
201    pub fn contains<V: ScalarFnVTable>(&self) -> VortexResult<bool> {
202        let mut contains = false;
203        pre_order_visit_down(self, |node| {
204            if node.is::<V>() {
205                contains = true;
206                return Ok(TraversalOrder::Stop);
207            }
208            Ok(TraversalOrder::Continue)
209        })?;
210        Ok(contains)
211    }
212
213    /// Return the typed scalar-function options when this node uses the given vtable.
214    pub fn as_opt<V: ScalarFnVTable>(&self) -> Option<&V::Options> {
215        self.as_scalar().and_then(ScalarFnRef::as_opt::<V>)
216    }
217
218    /// Return the typed scalar-function options for this node.
219    ///
220    /// # Panics
221    ///
222    /// Panics when this node is the scope root or uses a different scalar-function vtable.
223    pub fn as_<V: ScalarFnVTable>(&self) -> &V::Options {
224        self.as_opt::<V>()
225            .vortex_expect("Bound expression options type mismatch")
226    }
227
228    /// Whether this node is the scope root.
229    pub fn is_root(&self) -> bool {
230        matches!(self, Self::Root { .. })
231    }
232
233    /// Return whether every scope root in this expression has `dtype`.
234    ///
235    /// Expressions without a scope root, such as literals, match every dtype.
236    pub fn is_root_bound_to(&self, dtype: &DType) -> bool {
237        let mut is_bound_to = true;
238        pre_order_visit_down(self, |node| {
239            if node.is_root() && node.dtype() != dtype {
240                is_bound_to = false;
241                return Ok(TraversalOrder::Stop);
242            }
243            Ok(TraversalOrder::Continue)
244        })
245        .vortex_expect("bound expression traversal cannot not fail");
246        is_bound_to
247    }
248
249    /// Returns a new expression representing the validity mask output of this expression.
250    ///
251    /// Returned expression evaluates to a non-nullable boolean array.
252    /// When scalar function's validity is irreducible, returns
253    /// "is_not_null(self)", which requires evaluating "self".
254    pub fn validity(&self) -> VortexResult<BoundExpression> {
255        match self {
256            // The scope is exactly as valid as itself.
257            Self::Root { .. } => Ok(self.clone()),
258            Self::Scalar { .. } => {
259                let node = ExpressionReduceNode::new(self);
260                Ok(match node.validity()? {
261                    ReduceNodeValidity::Reduced(reduced) => reduced.into_expression(),
262                    // IsNotNull(x) -> x.validity() symbolic reduction rule works only
263                    // when node's.validity is Reduced to avoid infinite recursion.
264                    ReduceNodeValidity::Irreducible => {
265                        IsNotNull.try_new_bound_expr(EmptyOptions, [self.clone()])?
266                    }
267                })
268            }
269        }
270    }
271
272    /// Display the bound expression as a formatted tree structure.
273    pub fn display_tree(&self) -> impl Display {
274        DisplayTreeExpr(self)
275    }
276}
277
278impl Display for BoundExpression {
279    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
280        match self {
281            Self::Scalar { scalar_fn, .. } => scalar_fn.fmt_sql(self, f),
282            Self::Root { .. } => f.write_str("$"),
283        }
284    }
285}
286
287impl Expression {
288    /// Bind this expression against a root dtype, type-checking every node in a single walk.
289    ///
290    /// The returned tree carries a dtype on each node, so callers needing types at more than one
291    /// node should bind once and read fields rather than calling
292    /// [`return_dtype`](Expression::return_dtype) repeatedly.
293    pub fn bind(&self, dtype: &DType) -> VortexResult<BoundExpression> {
294        self.bind_scope(&Scope::new(dtype.clone()))
295    }
296
297    /// Bind this expression against an explicit [`Scope`].
298    pub fn bind_scope(&self, scope: &Scope) -> VortexResult<BoundExpression> {
299        if self.is_root() {
300            return Ok(BoundExpression::new_root(scope.root().clone()));
301        }
302        if let Expression::Variable(name) = self {
303            return Err(unbound_variable(name));
304        }
305
306        let children: Vec<_> = self
307            .children()
308            .iter()
309            .map(|child| child.bind_scope(scope))
310            .try_collect()?;
311        let scalar_fn = self
312            .as_scalar()
313            .vortex_expect("leaves were handled above, so this is a scalar node");
314        BoundExpression::try_new(scalar_fn.clone(), children)
315    }
316}
317
318/// Iterative drop to avoid stack overflows on deep trees.
319impl Drop for BoundExpression {
320    fn drop(&mut self) {
321        let Self::Scalar { children, .. } = self else {
322            return;
323        };
324        let Some(children) = Arc::get_mut(children) else {
325            return;
326        };
327
328        let mut to_drop = std::mem::take(children);
329        while let Some(mut child) = to_drop.pop() {
330            if let BoundExpression::Scalar { children, .. } = &mut child
331                && let Some(grandchildren) = Arc::get_mut(children)
332            {
333                to_drop.append(grandchildren);
334            }
335        }
336    }
337}
338
339#[cfg(test)]
340mod tests {
341    use vortex_error::VortexResult;
342
343    use super::*;
344    use crate::dtype::Nullability;
345    use crate::dtype::PType;
346    use crate::expr::col;
347    use crate::expr::eq;
348    use crate::expr::lit;
349    use crate::expr::root;
350    use crate::expr::test_harness::struct_dtype;
351    use crate::scalar_fn::fns::literal::Literal;
352
353    fn scope() -> Scope {
354        Scope::new(struct_dtype())
355    }
356
357    #[test]
358    fn root_binds_to_the_scope() -> VortexResult<()> {
359        let bound = root().bind_scope(&scope())?;
360        assert!(bound.is_root());
361        assert_eq!(bound.dtype(), &struct_dtype());
362        assert_eq!(bound, BoundExpression::new_root(struct_dtype()));
363        Ok(())
364    }
365
366    #[test]
367    fn every_node_carries_its_dtype() -> VortexResult<()> {
368        let expr = eq(col("a"), lit(1_i32));
369        let bound = expr.bind_scope(&scope())?;
370
371        assert_eq!(bound.dtype(), &DType::Bool(Nullability::NonNullable));
372
373        let lhs = &bound.children()[0];
374        assert_eq!(
375            lhs.dtype(),
376            &DType::Primitive(PType::I32, Nullability::NonNullable)
377        );
378        assert_eq!(lhs.children()[0].dtype(), &struct_dtype());
379        Ok(())
380    }
381
382    #[test]
383    fn bind_agrees_with_return_dtype() -> VortexResult<()> {
384        for (expr, expected) in [
385            (root(), struct_dtype()),
386            (
387                col("a"),
388                DType::Primitive(PType::I32, Nullability::NonNullable),
389            ),
390            (
391                eq(col("a"), lit(1_i32)),
392                DType::Bool(Nullability::NonNullable),
393            ),
394            (lit(true), DType::Bool(Nullability::NonNullable)),
395        ] {
396            assert_eq!(
397                expr.bind(&struct_dtype())?.dtype(),
398                &expected,
399                "binding {expr}"
400            );
401            assert_eq!(
402                expr.return_dtype(&struct_dtype())?,
403                expected,
404                "return dtype of {expr}"
405            );
406        }
407        Ok(())
408    }
409
410    #[test]
411    fn contains_scalar_function() -> VortexResult<()> {
412        let bound = eq(col("a"), lit(1_i32)).bind_scope(&scope())?;
413        assert!(bound.contains::<Literal>()?);
414        assert!(!root().bind_scope(&scope())?.contains::<Literal>()?);
415        Ok(())
416    }
417
418    #[test]
419    fn bound_to_checks_every_root() -> VortexResult<()> {
420        let dtype = struct_dtype();
421        let bound = eq(col("a"), col("a")).bind(&dtype)?;
422        assert!(bound.is_root_bound_to(&dtype));
423        assert!(!bound.is_root_bound_to(&DType::Bool(Nullability::NonNullable)));
424        assert!(
425            lit(true)
426                .bind(&dtype)?
427                .is_root_bound_to(&DType::Bool(Nullability::NonNullable))
428        );
429        Ok(())
430    }
431
432    #[test]
433    fn bound_display_matches_unbound() -> VortexResult<()> {
434        for expr in [root(), col("a"), eq(col("a"), lit(1_i32)), lit(true)] {
435            let bound = expr.bind_scope(&scope())?;
436            assert_eq!(bound.to_string(), expr.to_string());
437            assert_eq!(
438                bound.display_tree().to_string(),
439                expr.display_tree().to_string()
440            );
441        }
442        Ok(())
443    }
444
445    #[test]
446    fn clone_shares_children() -> VortexResult<()> {
447        let bound = eq(col("a"), lit(1_i32)).bind_scope(&scope())?;
448        let cloned = bound.clone();
449
450        let (
451            BoundExpression::Scalar { children: a, .. },
452            BoundExpression::Scalar { children: b, .. },
453        ) = (&bound, &cloned)
454        else {
455            unreachable!("eq is a scalar node")
456        };
457        assert!(Arc::ptr_eq(a, b));
458        Ok(())
459    }
460
461    #[test]
462    fn repeated_subtree_is_bound_per_occurrence() -> VortexResult<()> {
463        let shared = col("a");
464        let bound = eq(shared.clone(), shared).bind_scope(&scope())?;
465        let children = bound.children();
466        assert_eq!(children.len(), 2);
467        for child in children {
468            assert_eq!(
469                child.dtype(),
470                &DType::Primitive(PType::I32, Nullability::NonNullable)
471            );
472        }
473        Ok(())
474    }
475
476    #[test]
477    fn structural_and_exact_equality_are_distinct() -> VortexResult<()> {
478        let expr = eq(col("a"), lit(1_i32));
479        let bound = expr.bind_scope(&scope())?;
480        let independently_bound = expr.bind_scope(&scope())?;
481
482        assert_eq!(bound, independently_bound);
483        assert_eq!(ExactBoundExpr(bound.clone()), ExactBoundExpr(bound.clone()));
484        assert_ne!(ExactBoundExpr(bound), ExactBoundExpr(independently_bound));
485        Ok(())
486    }
487
488    #[test]
489    fn binding_reports_a_type_error() {
490        let expr = eq(col("a"), lit("nope"));
491        assert!(expr.bind_scope(&scope()).is_err());
492    }
493}