@@ -31,7 +31,7 @@ use arrow::{
3131} ;
3232use datafusion_common:: {
3333 HashMap , plan_err,
34- tree_node:: { Transformed , TreeNode , TreeNodeRecursion } ,
34+ tree_node:: { Transformed , TreeNode , TreeNodeRecursion , TreeNodeVisitor } ,
3535} ;
3636use datafusion_common:: { HashSet , Result , internal_err} ;
3737use 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+
154226impl 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) ]
236308mod 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