1use 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#[derive(Clone, Debug, PartialEq, Eq, Hash)]
40pub enum BoundExpression {
41 Scalar {
43 dtype: DType,
45 scalar_fn: ScalarFnRef,
47 children: Arc<Vec<BoundExpression>>,
52 },
53 Root {
55 dtype: DType,
57 },
58}
59
60#[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 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 pub fn new_root(dtype: DType) -> Self {
116 Self::Root { dtype }
117 }
118
119 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 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 pub fn dtype(&self) -> &DType {
169 match self {
170 Self::Scalar { dtype, .. } | Self::Root { dtype } => dtype,
171 }
172 }
173
174 pub fn children(&self) -> &[BoundExpression] {
176 match self {
177 Self::Scalar { children, .. } => children.as_slice(),
178 Self::Root { .. } => &[],
179 }
180 }
181
182 pub fn child(&self, index: usize) -> &BoundExpression {
184 &self.children()[index]
185 }
186
187 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 pub fn is<V: ScalarFnVTable>(&self) -> bool {
197 self.as_scalar().is_some_and(ScalarFnRef::is::<V>)
198 }
199
200 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 pub fn as_opt<V: ScalarFnVTable>(&self) -> Option<&V::Options> {
215 self.as_scalar().and_then(ScalarFnRef::as_opt::<V>)
216 }
217
218 pub fn as_<V: ScalarFnVTable>(&self) -> &V::Options {
224 self.as_opt::<V>()
225 .vortex_expect("Bound expression options type mismatch")
226 }
227
228 pub fn is_root(&self) -> bool {
230 matches!(self, Self::Root { .. })
231 }
232
233 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 pub fn validity(&self) -> VortexResult<BoundExpression> {
255 match self {
256 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 ReduceNodeValidity::Irreducible => {
265 IsNotNull.try_new_bound_expr(EmptyOptions, [self.clone()])?
266 }
267 })
268 }
269 }
270 }
271
272 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 pub fn bind(&self, dtype: &DType) -> VortexResult<BoundExpression> {
294 self.bind_scope(&Scope::new(dtype.clone()))
295 }
296
297 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
318impl 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}