Skip to main content

vortex_array/expr/
expression.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::cell::Cell;
5use std::fmt;
6use std::fmt::Debug;
7use std::fmt::Display;
8use std::fmt::Formatter;
9use std::hash::Hash;
10use std::sync::Arc;
11
12use itertools::Itertools;
13use vortex_error::VortexError;
14use vortex_error::VortexExpect;
15use vortex_error::VortexResult;
16use vortex_error::vortex_ensure;
17use vortex_error::vortex_err;
18
19use crate::dtype::DType;
20use crate::dtype::FieldName;
21use crate::expr::display::DisplayTreeExpr;
22use crate::expr::traversal::TraversalOrder;
23use crate::expr::traversal::pre_order_visit_down;
24use crate::scalar_fn::ScalarFnRef;
25use crate::scalar_fn::ScalarFnVTable;
26
27/// An empty child slice, returned by [`Expression::children`] for childless variants.
28const NO_CHILDREN: &[Expression] = &[];
29
30/// A node in a Vortex expression tree.
31///
32/// Most nodes are a scalar function applied to child expressions. The other two are leaves that
33/// name a value rather than compute one: [`Expression::Root`], the scope itself, and
34/// [`Expression::Variable`], a parameter of an enclosing lambda. They are language primitives
35/// rather than registered functions, because their dtype comes from where they appear rather than
36/// from children and they are not executable. A [`ScalarFnVTable`] can answer neither of those, so
37/// they are variants instead.
38#[derive(Clone, Debug, PartialEq, Eq, Hash)]
39pub enum Expression {
40    /// A scalar function applied to child expressions.
41    Scalar {
42        /// The scalar fn for this node.
43        scalar_fn: ScalarFnRef,
44        /// Any children of this expression.
45        children: Arc<Vec<Expression>>,
46    },
47    /// The full scope of the expression evaluation.
48    Root,
49    /// A parameter of the enclosing lambda, read by name.
50    ///
51    /// Binding a [`Lambda`](crate::expr::Lambda) turns its variables into reads of the struct of
52    /// its inputs. Anywhere else a variable fails to bind, and it is not serializable yet.
53    Variable(FieldName),
54}
55
56impl Expression {
57    /// Create a new expression node from a scalar_fn expression and its children.
58    pub fn try_new(
59        scalar_fn: ScalarFnRef,
60        children: impl IntoIterator<Item = Expression>,
61    ) -> VortexResult<Self> {
62        let children = Vec::from_iter(children);
63
64        vortex_ensure!(
65            scalar_fn.signature().arity().matches(children.len()),
66            "Expression arity mismatch: expected {} children but got {}",
67            scalar_fn.signature().arity(),
68            children.len()
69        );
70
71        Ok(Self::Scalar {
72            scalar_fn,
73            children: children.into(),
74        })
75    }
76
77    /// Whether this expression is the scope root.
78    pub fn is_root(&self) -> bool {
79        matches!(self, Self::Root)
80    }
81
82    /// Returns the scalar fn for this expression, or `None` if it is not a scalar node.
83    pub fn as_scalar(&self) -> Option<&ScalarFnRef> {
84        match self {
85            Self::Scalar { scalar_fn, .. } => Some(scalar_fn),
86            Self::Root | Self::Variable(_) => None,
87        }
88    }
89
90    /// Whether this expression's scalar fn is of the given vtable type.
91    pub fn is<V: ScalarFnVTable>(&self) -> bool {
92        self.as_scalar().is_some_and(|sf| sf.is::<V>())
93    }
94
95    /// The typed options for this expression if its scalar fn matches the given vtable type.
96    pub fn as_opt<V: ScalarFnVTable>(&self) -> Option<&V::Options> {
97        self.as_scalar().and_then(|sf| sf.as_opt::<V>())
98    }
99
100    /// The typed options for this expression.
101    ///
102    /// # Panics
103    ///
104    /// Panics if the vtable type does not match.
105    pub fn as_<V: ScalarFnVTable>(&self) -> &V::Options {
106        self.as_opt::<V>()
107            .vortex_expect("Expression options type mismatch")
108    }
109
110    /// Returns the children of this expression.
111    pub fn children(&self) -> &[Expression] {
112        match self {
113            Self::Scalar { children, .. } => children.as_slice(),
114            Self::Root | Self::Variable(_) => NO_CHILDREN,
115        }
116    }
117
118    /// Returns the n'th child of this expression.
119    pub fn child(&self, n: usize) -> &Expression {
120        &self.children()[n]
121    }
122
123    /// Replace the children of this expression with the provided new children.
124    pub fn with_children(
125        self,
126        children: impl IntoIterator<Item = Expression>,
127    ) -> VortexResult<Self> {
128        let children = Vec::from_iter(children);
129        match &self {
130            Self::Root => {
131                vortex_ensure!(
132                    children.is_empty(),
133                    "Expression arity mismatch: root expects 0 children but got {}",
134                    children.len()
135                );
136                Ok(Self::Root)
137            }
138            Self::Variable(name) => {
139                vortex_ensure!(
140                    children.is_empty(),
141                    "Expression arity mismatch: variable expects 0 children but got {}",
142                    children.len()
143                );
144                Ok(Self::Variable(name.clone()))
145            }
146            Self::Scalar { scalar_fn, .. } => {
147                vortex_ensure!(
148                    scalar_fn.signature().arity().matches(children.len()),
149                    "Expression arity mismatch: expected {} children but got {}",
150                    scalar_fn.signature().arity(),
151                    children.len()
152                );
153                Ok(Self::Scalar {
154                    scalar_fn: scalar_fn.clone(),
155                    children: children.into(),
156                })
157            }
158        }
159    }
160
161    /// Computes the return dtype of this expression given the input dtype.
162    pub fn return_dtype(&self, scope: &DType) -> VortexResult<DType> {
163        match self {
164            Self::Root => Ok(scope.clone()),
165            Self::Variable(name) => Err(unbound_variable(name)),
166            Self::Scalar {
167                scalar_fn,
168                children,
169            } => {
170                let dtypes: Vec<_> = children
171                    .iter()
172                    .map(|c| c.return_dtype(scope))
173                    .try_collect()?;
174                scalar_fn.return_dtype(&dtypes)
175            }
176        }
177    }
178
179    /// Format the expression as a compact string.
180    ///
181    /// Since this is a recursive formatter, it is exposed on the public Expression type.
182    /// See fmt_data that is only implemented on the vtable trait.
183    pub fn fmt_sql(&self, f: &mut Formatter<'_>) -> fmt::Result {
184        match self {
185            Self::Root => write!(f, "$"),
186            Self::Variable(name) => write!(f, "@{name}"),
187            Self::Scalar { scalar_fn, .. } => scalar_fn.fmt_sql(self, f),
188        }
189    }
190
191    /// Display the expression as a formatted tree structure.
192    ///
193    /// This provides a hierarchical view of the expression that shows the relationships
194    /// between parent and child expressions, making complex nested expressions easier
195    /// to understand and debug.
196    ///
197    /// # Example
198    ///
199    /// ```rust
200    /// # use vortex_array::dtype::{DType, Nullability, PType};
201    /// # use vortex_array::scalar_fn::fns::like::{Like, LikeOptions};
202    /// # use vortex_array::scalar_fn::ScalarFnVTableExt;
203    /// # use vortex_array::expr::{and, cast, eq, get_item, gt, lit, not, root, select};
204    /// // Build a complex nested expression
205    /// let complex_expr = select(
206    ///     ["result"],
207    ///     and(
208    ///         not(eq(get_item("status", root()), lit("inactive"))),
209    ///         and(
210    ///             Like.new_expr(LikeOptions::default(), [get_item("name", root()), lit("%admin%")]),
211    ///             gt(
212    ///                 cast(get_item("score", root()), DType::Primitive(PType::F64, Nullability::NonNullable)),
213    ///                 lit(75.0)
214    ///             )
215    ///         )
216    ///     )
217    /// );
218    ///
219    /// println!("{}", complex_expr.display_tree());
220    /// ```
221    ///
222    /// This produces output like:
223    ///
224    /// ```text
225    /// Select(include): {result}
226    /// └── Binary(and)
227    ///     ├── lhs: Not
228    ///     │   └── Binary(=)
229    ///     │       ├── lhs: GetItem(status)
230    ///     │       │   └── Root
231    ///     │       └── rhs: Literal(value: "inactive", dtype: utf8)
232    ///     └── rhs: Binary(and)
233    ///         ├── lhs: Like
234    ///         │   ├── child: GetItem(name)
235    ///         │   │   └── Root
236    ///         │   └── pattern: Literal(value: "%admin%", dtype: utf8)
237    ///         └── rhs: Binary(>)
238    ///             ├── lhs: Cast(target: f64)
239    ///             │   └── GetItem(score)
240    ///             │       └── Root
241    ///             └── rhs: Literal(value: 75f64, dtype: f64)
242    /// ```
243    pub fn display_tree(&self) -> impl Display {
244        DisplayTreeExpr(self)
245    }
246
247    /// Returns true if this expression contains expression E inside.
248    ///
249    /// # Example
250    ///
251    /// ```rust
252    /// # use vortex_array::scalar_fn::fns::literal::Literal;
253    /// # use vortex_array::expr::{eq, lit, root};
254    /// let expression = &eq(root(), lit(3u64));
255    /// assert!(expression.contains::<Literal>().unwrap());
256    /// let expression = root();
257    /// assert!(!expression.contains::<Literal>().unwrap());
258    /// ```
259    pub fn contains<E: ScalarFnVTable>(&self) -> VortexResult<bool> {
260        let mut contains = false;
261        pre_order_visit_down(self, |node| {
262            if node.is::<E>() {
263                contains = true;
264                return Ok(TraversalOrder::Stop);
265            }
266            Ok(TraversalOrder::Continue)
267        })?;
268        Ok(contains)
269    }
270}
271
272/// The error for a variable that no enclosing lambda declares.
273pub(crate) fn unbound_variable(name: &FieldName) -> VortexError {
274    vortex_err!("variable @{name} is not a parameter of an enclosing lambda")
275}
276
277/// The default display implementation for expressions uses the 'SQL'-style format.
278impl Display for Expression {
279    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
280        self.fmt_sql(f)
281    }
282}
283
284// Switch to iterative cleanup after this many recursive drops.
285const MAX_DROP_DEPTH: u32 = 32;
286
287thread_local! {
288    static DROP_DEPTH: Cell<u32> = const { Cell::new(0) };
289}
290
291// Increments the thread-local drop depth until the guard is dropped.
292struct DropDepthGuard;
293
294impl DropDepthGuard {
295    fn enter() -> Option<Self> {
296        DROP_DEPTH.with(|depth| {
297            let current = depth.get();
298            (current < MAX_DROP_DEPTH).then(|| {
299                depth.set(current + 1);
300                Self
301            })
302        })
303    }
304}
305
306impl Drop for DropDepthGuard {
307    fn drop(&mut self) {
308        DROP_DEPTH.with(|depth| depth.set(depth.get() - 1));
309    }
310}
311
312impl Drop for Expression {
313    fn drop(&mut self) {
314        let Self::Scalar { children, .. } = self else {
315            return;
316        };
317        let Some(children) = Arc::get_mut(children) else {
318            return;
319        };
320        if children.is_empty() {
321            return;
322        }
323
324        let mut children_to_drop = std::mem::take(children);
325
326        match DropDepthGuard::enter() {
327            Some(_guard) => drop(children_to_drop),
328            None => {
329                while let Some(mut child) = children_to_drop.pop() {
330                    if let Self::Scalar { children, .. } = &mut child
331                        && let Some(expr_children) = Arc::get_mut(children)
332                    {
333                        children_to_drop.append(expr_children);
334                    }
335                }
336            }
337        }
338    }
339}
340
341#[cfg(test)]
342mod tests {
343    use std::thread;
344
345    use super::*;
346    use crate::expr::lit;
347    use crate::expr::not;
348
349    fn deep_expression(depth: usize) -> Expression {
350        let mut expr = lit(true);
351        for _ in 0..depth {
352            expr = not(expr);
353        }
354        expr
355    }
356
357    #[test]
358    fn deep_expression_drops_within_a_small_stack() -> VortexResult<()> {
359        const DEPTH: usize = 100_000;
360        const STACK_SIZE: usize = 256 * 1024;
361
362        let dropper = thread::Builder::new()
363            .stack_size(STACK_SIZE)
364            .spawn(|| drop(deep_expression(DEPTH)))?;
365
366        assert!(
367            dropper.join().is_ok(),
368            "dropping a tree of depth {DEPTH} exhausted a {STACK_SIZE} byte stack"
369        );
370
371        Ok(())
372    }
373
374    #[test]
375    fn shallow_expression_keeps_shared_children() {
376        let expr = not(lit(true));
377        let shared = expr.clone();
378
379        drop(expr);
380
381        assert_eq!(shared.children(), &[lit(true)]);
382    }
383}