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}