Skip to content

Commit 993ac37

Browse files
committed
body centric fix
1 parent 31198ba commit 993ac37

2 files changed

Lines changed: 247 additions & 45 deletions

File tree

‎datafusion/expr/src/higher_order_function.rs‎

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ use crate::expr::{
2424
use crate::type_coercion::functions::value_fields_with_higher_order_udf;
2525
use crate::udf_eq::UdfEq;
2626
use crate::{ColumnarValue, Documentation, Expr, ExprSchemable};
27-
use arrow::array::{ArrayRef, RecordBatch};
27+
use arrow::array::{ArrayRef, RecordBatch, RecordBatchOptions};
2828
use arrow::datatypes::{DataType, FieldRef, Schema};
2929
use arrow_schema::SchemaRef;
3030
use datafusion_common::config::ConfigOptions;
@@ -382,6 +382,21 @@ fn merge_captures_with_variables(
382382
.collect::<Result<_>>()?,
383383
};
384384

385+
if columns.is_empty() {
386+
// Constant body with no captures and no used params — derive row count
387+
// from the first available variable closure so the batch has the right
388+
// number of rows even with zero columns.
389+
let row_count = match variables.first() {
390+
Some(first) => first()?.len(),
391+
None => 0,
392+
};
393+
return Ok(RecordBatch::try_new_with_options(
394+
schema,
395+
vec![],
396+
&RecordBatchOptions::new().with_row_count(Some(row_count)),
397+
)?);
398+
}
399+
385400
Ok(RecordBatch::try_new(schema, columns)?)
386401
}
387402

‎datafusion/physical-expr/src/expressions/lambda.rs‎

Lines changed: 231 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,7 @@ use arrow::{
3131
};
3232
use datafusion_common::{
3333
HashMap, plan_err,
34-
tree_node::{Transformed, TreeNode, TreeNodeRecursion},
34+
tree_node::{Transformed, TreeNode, TreeNodeRecursion, TreeNodeVisitor},
3535
};
3636
use datafusion_common::{HashSet, Result, internal_err};
3737
use datafusion_expr::ColumnarValue;
@@ -75,54 +75,84 @@ impl LambdaExpr {
7575
}
7676

7777
fn new(params: Vec<String>, body: Arc<dyn PhysicalExpr>) -> Self {
78-
let mut used_column_indices = HashSet::new();
79-
80-
body.apply(|node| {
81-
if let Some(col) = node.downcast_ref::<Column>() {
82-
used_column_indices.insert(col.index());
83-
} else if let Some(var) = node.downcast_ref::<LambdaVariable>() {
84-
used_column_indices.insert(var.index());
85-
}
86-
87-
Ok(TreeNodeRecursion::Continue)
88-
})
89-
.expect("closure should be infallible");
90-
91-
let mut projection = used_column_indices.into_iter().collect::<Vec<_>>();
78+
let own_params: HashSet<String> = params.iter().cloned().collect();
79+
80+
// Walk the body once to collect:
81+
// - used outer Column indices (for the captures projection)
82+
// - used own parameter names (with nested-lambda shadowing)
83+
let mut visitor = CollectUsedVisitor {
84+
own_params: &own_params,
85+
used_column_indices: HashSet::new(),
86+
used_param_names: HashSet::new(),
87+
shadow_stack: Vec::new(),
88+
};
89+
body.visit(&mut visitor).expect("visitor is infallible");
90+
let CollectUsedVisitor {
91+
used_column_indices,
92+
..
93+
} = visitor;
9294

95+
let mut projection: Vec<usize> = used_column_indices.into_iter().collect();
9396
projection.sort();
9497

95-
let column_index_map = projection
98+
// Map original outer-column indices → dense positions in the captures batch.
99+
let col_index_map: HashMap<usize, usize> = projection
96100
.iter()
101+
.copied()
97102
.enumerate()
98-
.map(|(projected, original)| (*original, projected))
99-
.collect::<HashMap<_, _>>();
100-
101-
let projected_body = Arc::clone(&body)
102-
.transform_down(|e| {
103-
if let Some(column) = e.downcast_ref::<Column>() {
104-
let original = column.index();
105-
let projected = *column_index_map.get(&original).unwrap();
106-
if projected != original {
107-
return Ok(Transformed::yes(Arc::new(Column::new(
108-
column.name(),
109-
projected,
110-
))));
103+
.map(|(new_idx, original)| (original, new_idx))
104+
.collect();
105+
106+
// Map each *declared* param name → its slot in the merged evaluation batch.
107+
// Captures occupy 0..projection.len(); then all declared params follow in
108+
// declaration order (HOF passes all declared param closures in that order).
109+
// Unused params still occupy a slot — they're just never read by the body.
110+
let projected_body = {
111+
let captures_len = projection.len();
112+
let param_slot_map: HashMap<&str, usize> = params
113+
.iter()
114+
.enumerate()
115+
.map(|(i, name)| (name.as_str(), captures_len + i))
116+
.collect();
117+
118+
Arc::clone(&body)
119+
.transform_down(|e| {
120+
// Don't descend into nested lambdas — they are
121+
// self-contained and were already rewritten by their own
122+
// LambdaExpr::new call with their own param_slot_map.
123+
if e.downcast_ref::<LambdaExpr>().is_some() {
124+
return Ok(Transformed::new(e, false, TreeNodeRecursion::Jump));
111125
}
112-
} else if let Some(lambda_variable) = e.downcast_ref::<LambdaVariable>() {
113-
let original = lambda_variable.index();
114-
let projected = *column_index_map.get(&original).unwrap();
115-
if projected != original {
116-
return Ok(Transformed::yes(Arc::new(LambdaVariable::new(
117-
projected,
118-
Arc::clone(lambda_variable.field()),
119-
))));
126+
if let Some(column) = e.downcast_ref::<Column>() {
127+
let original = column.index();
128+
let projected = *col_index_map.get(&original).unwrap();
129+
if projected != original {
130+
return Ok(Transformed::yes(Arc::new(Column::new(
131+
column.name(),
132+
projected,
133+
))));
134+
}
135+
} else if let Some(var) = e.downcast_ref::<LambdaVariable>() {
136+
if let Some(&slot) = param_slot_map.get(var.name()) {
137+
if slot != var.index() {
138+
return Ok(Transformed::yes(Arc::new(
139+
LambdaVariable::new(slot, Arc::clone(var.field())),
140+
)));
141+
}
142+
} else if let Some(&new_idx) = col_index_map.get(&var.index())
143+
&& new_idx != var.index()
144+
{
145+
return Ok(Transformed::yes(Arc::new(LambdaVariable::new(
146+
new_idx,
147+
Arc::clone(var.field()),
148+
))));
149+
}
120150
}
121-
}
122-
Ok(Transformed::no(e))
123-
})
124-
.expect("closure should be infallible")
125-
.data;
151+
Ok(Transformed::no(e))
152+
})
153+
.expect("closure should be infallible")
154+
.data
155+
};
126156

127157
Self {
128158
params,
@@ -151,6 +181,48 @@ impl LambdaExpr {
151181
}
152182
}
153183

184+
/// Walks a lambda body once and collects:
185+
/// - `used_column_indices`: every outer `Column` index referenced anywhere in
186+
/// the tree (drives the captures projection).
187+
/// - `used_param_names`: the subset of *this* lambda's own params referenced
188+
/// by the body, accounting for nested-lambda shadowing (an inner lambda that
189+
/// re-declares a param name shadows the outer one).
190+
struct CollectUsedVisitor<'a> {
191+
own_params: &'a HashSet<String>,
192+
used_column_indices: HashSet<usize>,
193+
used_param_names: HashSet<String>,
194+
shadow_stack: Vec<HashSet<String>>,
195+
}
196+
197+
impl TreeNodeVisitor<'_> for CollectUsedVisitor<'_> {
198+
type Node = Arc<dyn PhysicalExpr>;
199+
200+
fn f_down(&mut self, node: &Self::Node) -> Result<TreeNodeRecursion> {
201+
if let Some(col) = node.downcast_ref::<Column>() {
202+
self.used_column_indices.insert(col.index());
203+
} else if let Some(var) = node.downcast_ref::<LambdaVariable>() {
204+
let name = var.name();
205+
let shadowed = self.shadow_stack.iter().any(|frame| frame.contains(name));
206+
if !shadowed && self.own_params.contains(name) {
207+
self.used_param_names.insert(name.to_string());
208+
} else {
209+
self.used_column_indices.insert(var.index());
210+
}
211+
} else if let Some(nested) = node.downcast_ref::<LambdaExpr>() {
212+
self.shadow_stack
213+
.push(nested.params.iter().cloned().collect());
214+
}
215+
Ok(TreeNodeRecursion::Continue)
216+
}
217+
218+
fn f_up(&mut self, node: &Self::Node) -> Result<TreeNodeRecursion> {
219+
if node.downcast_ref::<LambdaExpr>().is_some() {
220+
self.shadow_stack.pop();
221+
}
222+
Ok(TreeNodeRecursion::Continue)
223+
}
224+
}
225+
154226
impl std::fmt::Display for LambdaExpr {
155227
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
156228
write!(f, "({}) -> {}", self.params.join(", "), self.body)
@@ -234,10 +306,18 @@ fn check_async_udf(body: &Arc<dyn PhysicalExpr>) -> Result<()> {
234306

235307
#[cfg(test)]
236308
mod tests {
237-
use crate::expressions::{NoOp, lambda::lambda};
238-
use arrow::{array::RecordBatch, datatypes::Schema};
309+
use crate::expressions::{Column, LambdaVariable, NoOp, lambda::lambda};
310+
use arrow::{
311+
array::{Int32Array, RecordBatch},
312+
datatypes::{DataType, Field, Schema},
313+
};
314+
use datafusion_common::tree_node::{TreeNode, TreeNodeRecursion};
315+
use datafusion_expr::ColumnarValue;
316+
use datafusion_expr::LambdaArgument;
239317
use std::sync::Arc;
240318

319+
use super::LambdaExpr;
320+
241321
#[test]
242322
fn test_lambda_evaluate() {
243323
let lambda = lambda(["a"], Arc::new(NoOp::new())).unwrap();
@@ -249,4 +329,111 @@ mod tests {
249329
fn test_lambda_duplicate_name() {
250330
assert!(lambda(["a", "a"], Arc::new(NoOp::new())).is_err());
251331
}
332+
333+
/// `(k, v) -> v`: only `v` (index 1) is referenced. The projection should
334+
/// contain only index 1, and `used_params` should be `["v"]` only.
335+
#[test]
336+
fn test_unused_first_param_projection() {
337+
let v_field = Arc::new(Field::new("v", DataType::Int32, true));
338+
// LambdaVariable index 1 = "v" as declared
339+
let body = Arc::new(LambdaVariable::new(1, Arc::clone(&v_field)));
340+
let lambda =
341+
LambdaExpr::try_new(vec!["k".to_string(), "v".to_string()], body).unwrap();
342+
343+
// No outer columns captured — projection is empty.
344+
assert_eq!(lambda.projection(), &[] as &[usize]);
345+
// projected_body's LambdaVariable for `v` must be at slot 1
346+
// (captures_len=0 + declaration index 1), not compressed to slot 0.
347+
let mut found_slot = None;
348+
lambda
349+
.projected_body()
350+
.apply(|e| {
351+
if let Some(var) = e.downcast_ref::<LambdaVariable>()
352+
&& var.name() == "v"
353+
{
354+
found_slot = Some(var.index());
355+
}
356+
Ok(TreeNodeRecursion::Continue)
357+
})
358+
.unwrap();
359+
assert_eq!(found_slot, Some(1), "v must remain at declaration slot 1");
360+
}
361+
362+
/// `(k, v) -> v` evaluated end-to-end: LambdaArgument must return the `v`
363+
/// column, not `k`. This is the exact runtime bug this fix addresses.
364+
#[test]
365+
fn test_unused_first_param_evaluates_correctly() {
366+
let k_field = Arc::new(Field::new("k", DataType::Int32, true));
367+
let v_field = Arc::new(Field::new("v", DataType::Int32, true));
368+
369+
let body = Arc::new(LambdaVariable::new(1, Arc::clone(&v_field)));
370+
let lambda_expr =
371+
LambdaExpr::try_new(vec!["k".to_string(), "v".to_string()], body).unwrap();
372+
373+
// HOF passes all declared params to LambdaArgument::new.
374+
// The fix is in projected_body: `v`'s LambdaVariable is remapped to
375+
// slot captures_len + 1 (its declaration position), not slot 0.
376+
let params = vec![k_field, v_field];
377+
let arg =
378+
LambdaArgument::new(params, Arc::clone(lambda_expr.projected_body()), None);
379+
380+
let k_array = Arc::new(Int32Array::from(vec![1, 2, 3])) as _;
381+
let v_array = Arc::new(Int32Array::from(vec![10, 20, 30])) as _;
382+
383+
// HOF passes all declared param closures in declaration order.
384+
// The projected body already maps `v`'s LambdaVariable to slot
385+
// captures_len + 1, so it reads `v`'s array, not `k`'s.
386+
let k_fn: &dyn Fn() -> datafusion_common::Result<arrow::array::ArrayRef> =
387+
&|| Ok(Arc::clone(&k_array));
388+
let v_fn: &dyn Fn() -> datafusion_common::Result<arrow::array::ArrayRef> =
389+
&|| Ok(Arc::clone(&v_array));
390+
let result = arg
391+
.evaluate(&[k_fn, v_fn], |_| unreachable!("no captures"))
392+
.unwrap();
393+
394+
let ColumnarValue::Array(result_arr) = result else {
395+
panic!("expected array result");
396+
};
397+
let result_i32 = result_arr.as_any().downcast_ref::<Int32Array>().unwrap();
398+
assert_eq!(result_i32.values(), &[10, 20, 30]);
399+
}
400+
401+
/// Nested-lambda shadowing: `(k, v) -> col + (k, v2) -> k + v2 + v`.
402+
/// The inner lambda re-declares `k`, shadowing the outer one. The outer
403+
/// lambda's `CollectUsedVisitor` must not treat the inner `k` as a
404+
/// reference to the outer `k` — only outer `v` is actually used by the
405+
/// outer lambda's own body. This test verifies construction succeeds and
406+
/// the outer lambda's projected body is built correctly (no panic).
407+
#[test]
408+
fn test_shadowed_param_construction_succeeds() {
409+
let outer_k = Arc::new(Field::new("k", DataType::Int32, true));
410+
let outer_v = Arc::new(Field::new("v", DataType::Int32, true));
411+
let inner_v2 = Arc::new(Field::new("v2", DataType::Int32, true));
412+
413+
let inner_body: Arc<dyn crate::PhysicalExpr> =
414+
Arc::new(crate::expressions::BinaryExpr::new(
415+
Arc::new(crate::expressions::BinaryExpr::new(
416+
Arc::new(LambdaVariable::new(1, Arc::clone(&outer_k))),
417+
datafusion_expr::Operator::Plus,
418+
Arc::new(LambdaVariable::new(2, Arc::clone(&inner_v2))),
419+
)),
420+
datafusion_expr::Operator::Plus,
421+
Arc::new(LambdaVariable::new(0, Arc::clone(&outer_v))),
422+
));
423+
let inner_lambda = Arc::new(
424+
LambdaExpr::try_new(vec!["k".to_string(), "v2".to_string()], inner_body)
425+
.unwrap(),
426+
);
427+
428+
let outer_body: Arc<dyn crate::PhysicalExpr> =
429+
Arc::new(crate::expressions::BinaryExpr::new(
430+
Arc::new(Column::new("col", 0)),
431+
datafusion_expr::Operator::Plus,
432+
inner_lambda,
433+
));
434+
435+
// Must not panic — shadowing means outer's `k` is NOT flagged as used
436+
// and its param slot is assigned by declaration position correctly.
437+
LambdaExpr::try_new(vec!["k".to_string(), "v".to_string()], outer_body).unwrap();
438+
}
252439
}

0 commit comments

Comments
 (0)