1use std::fmt::Display;
5use std::fmt::Formatter;
6use std::hash::Hash;
7use std::sync::Arc;
8
9use itertools::Itertools as _;
10use vortex_error::VortexExpect;
11use vortex_error::VortexResult;
12use vortex_error::vortex_bail;
13use vortex_session::VortexSession;
14use vortex_session::registry::CachedId;
15use vortex_utils::aliases::hash_set::HashSet;
16
17use crate::ArrayRef;
18use crate::ExecutionCtx;
19use crate::IntoArray as _;
20use crate::arrays::StructArray;
21use crate::arrays::struct_::StructArrayExt;
22use crate::dtype::DType;
23use crate::dtype::FieldNames;
24use crate::dtype::Nullability;
25use crate::dtype::StructFields;
26use crate::scalar_fn::Arity;
27use crate::scalar_fn::ChildName;
28use crate::scalar_fn::ExecutionArgs;
29use crate::scalar_fn::ReduceNode;
30use crate::scalar_fn::ScalarFnId;
31use crate::scalar_fn::ScalarFnVTable;
32use crate::scalar_fn::ScalarFnVTableExt;
33use crate::scalar_fn::fns::get_item::GetItem;
34use crate::scalar_fn::fns::pack::Pack;
35use crate::scalar_fn::fns::pack::PackOptions;
36use crate::validity::Validity;
37
38#[derive(Clone)]
45pub struct Merge;
46
47impl ScalarFnVTable for Merge {
48 type Options = DuplicateHandling;
49
50 fn id(&self) -> ScalarFnId {
51 static ID: CachedId = CachedId::new("vortex.merge");
52 *ID
53 }
54
55 fn serialize(&self, instance: &Self::Options) -> VortexResult<Option<Vec<u8>>> {
56 Ok(Some(match instance {
57 DuplicateHandling::RightMost => vec![0x00],
58 DuplicateHandling::Error => vec![0x01],
59 }))
60 }
61
62 fn deserialize(
63 &self,
64 _metadata: &[u8],
65 _session: &VortexSession,
66 ) -> VortexResult<Self::Options> {
67 let instance = match _metadata {
68 [0x00] => DuplicateHandling::RightMost,
69 [0x01] => DuplicateHandling::Error,
70 _ => {
71 vortex_bail!("invalid metadata for Merge expression");
72 }
73 };
74 Ok(instance)
75 }
76
77 fn arity(&self, _options: &Self::Options) -> Arity {
78 Arity::Variadic { min: 0, max: None }
79 }
80
81 fn child_name(&self, _instance: &Self::Options, child_idx: usize) -> ChildName {
82 ChildName::from(Arc::from(format!("{}", child_idx)))
83 }
84
85 fn return_dtype(&self, options: &Self::Options, arg_dtypes: &[DType]) -> VortexResult<DType> {
86 let mut field_names = Vec::new();
87 let mut arrays = Vec::new();
88 let mut merge_nullability = Nullability::NonNullable;
89 let mut duplicate_names = HashSet::<_>::new();
90
91 for dtype in arg_dtypes {
92 let Some(fields) = dtype.as_struct_fields_opt() else {
93 vortex_bail!("merge expects struct input");
94 };
95 if dtype.is_nullable() {
96 vortex_bail!("merge expects non-nullable input");
97 }
98
99 merge_nullability |= dtype.nullability();
100
101 for (field_name, field_dtype) in fields.names().iter().zip_eq(fields.fields()) {
102 if let Some(idx) = field_names.iter().position(|name| name == field_name) {
103 duplicate_names.insert(field_name.clone());
104 arrays[idx] = field_dtype;
105 } else {
106 field_names.push(field_name.clone());
107 arrays.push(field_dtype);
108 }
109 }
110 }
111
112 if options == &DuplicateHandling::Error && !duplicate_names.is_empty() {
113 vortex_bail!(
114 "merge: duplicate fields in children: {}",
115 duplicate_names.into_iter().format(", ")
116 )
117 }
118
119 Ok(DType::Struct(
120 StructFields::new(FieldNames::from(field_names), arrays),
121 merge_nullability,
122 ))
123 }
124
125 fn execute(
126 &self,
127 options: &Self::Options,
128 args: &dyn ExecutionArgs,
129 ctx: &mut ExecutionCtx,
130 ) -> VortexResult<ArrayRef> {
131 let mut field_names = Vec::new();
133 let mut arrays = Vec::new();
134 let mut duplicate_names = HashSet::<_>::new();
135
136 for i in 0..args.num_inputs() {
137 let array = args.get(i)?.execute::<StructArray>(ctx)?;
138 if array.dtype().is_nullable() {
139 vortex_bail!("merge expects non-nullable input");
140 }
141
142 for (field_name, field_array) in array
143 .names()
144 .iter()
145 .zip_eq(array.iter_unmasked_fields().cloned())
146 {
147 if let Some(idx) = field_names.iter().position(|name| name == field_name) {
149 duplicate_names.insert(field_name.clone());
150 arrays[idx] = field_array;
151 } else {
152 field_names.push(field_name.clone());
153 arrays.push(field_array);
154 }
155 }
156 }
157
158 if options == &DuplicateHandling::Error && !duplicate_names.is_empty() {
159 vortex_bail!(
160 "merge: duplicate fields in children: {}",
161 duplicate_names.into_iter().format(", ")
162 )
163 }
164
165 let validity = Validity::NonNullable;
167 let len = args.row_count();
168 Ok(
169 StructArray::try_new(FieldNames::from(field_names), arrays, len, validity)?
170 .into_array(),
171 )
172 }
173
174 fn reduce<T: ReduceNode>(&self, options: &Self::Options, node: &T) -> VortexResult<Option<T>> {
175 let mut names = Vec::with_capacity(node.child_count() * 2);
176 let mut fields: Vec<T> = Vec::with_capacity(node.child_count() * 2);
177 let mut duplicate_names = HashSet::<_>::new();
178
179 for child in (0..node.child_count()).map(|i| node.child(i)) {
180 let child_dtype = child.node_dtype()?;
181 if !child_dtype.is_struct() || child_dtype.is_nullable() {
182 vortex_bail!(
183 "Merge child must return a non-nullable struct dtype, got {}",
184 child_dtype
185 )
186 }
187
188 let child_dtype = child_dtype
189 .as_struct_fields_opt()
190 .vortex_expect("expected struct");
191
192 for name in child_dtype.names().iter() {
193 let field = GetItem::apply_now(&child, name)?;
198
199 if let Some(idx) = names.iter().position(|n| n == name) {
200 duplicate_names.insert(name.clone());
201 fields[idx] = field;
202 } else {
203 names.push(name.clone());
204 fields.push(field);
205 }
206 }
207
208 if options == &DuplicateHandling::Error && !duplicate_names.is_empty() {
209 vortex_bail!(
210 "merge: duplicate fields in children: {}",
211 duplicate_names.into_iter().format(", ")
212 )
213 }
214 }
215
216 let pack_expr = node.new_node(
217 Pack.bind(PackOptions {
218 names: FieldNames::from(names),
219 nullability: node.node_dtype()?.nullability(),
220 }),
221 &fields,
222 )?;
223
224 Ok(Some(pack_expr))
225 }
226
227 fn is_strict(&self, _options: &Self::Options) -> bool {
228 true
229 }
230
231 fn is_infallible(&self, instance: &Self::Options) -> bool {
232 !matches!(instance, DuplicateHandling::Error)
233 }
234}
235
236#[derive(Default, Debug, Copy, Clone, PartialEq, Eq, Hash)]
238pub enum DuplicateHandling {
239 RightMost,
241 #[default]
243 Error,
244}
245
246impl Display for DuplicateHandling {
247 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
248 match self {
249 DuplicateHandling::RightMost => write!(f, "RightMost"),
250 DuplicateHandling::Error => write!(f, "Error"),
251 }
252 }
253}
254
255#[cfg(test)]
256mod tests {
257 use std::sync::LazyLock;
258
259 use vortex_buffer::buffer;
260 use vortex_error::VortexResult;
261 use vortex_error::vortex_bail;
262 use vortex_session::VortexSession;
263
264 use crate::ArrayRef;
265 use crate::IntoArray;
266 use crate::VortexSessionExecute;
267 use crate::arrays::PrimitiveArray;
268 use crate::arrays::struct_::StructArrayExt;
269 use crate::assert_arrays_eq;
270 use crate::dtype::DType;
271 use crate::dtype::Nullability::NonNullable;
272 use crate::dtype::PType::I32;
273 use crate::dtype::PType::I64;
274 use crate::dtype::PType::U32;
275 use crate::dtype::PType::U64;
276 use crate::expr::Expression;
277 use crate::expr::get_item;
278 use crate::expr::merge;
279 use crate::expr::merge_opts;
280 use crate::expr::root;
281 use crate::scalar_fn::fns::merge::DuplicateHandling;
282 use crate::scalar_fn::fns::merge::StructArray;
283 use crate::scalar_fn::fns::pack::Pack;
284
285 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
286
287 fn field_array(array: &ArrayRef, field_path: &[&str]) -> VortexResult<ArrayRef> {
288 let mut ctx = SESSION.create_execution_ctx();
289 let mut field_path = field_path.iter();
290
291 let Some(field) = field_path.next() else {
292 vortex_bail!("empty field path");
293 };
294
295 let mut array = array
296 .clone()
297 .execute::<StructArray>(&mut ctx)?
298 .unmasked_field_by_name(field)?
299 .clone();
300 for field in field_path {
301 let next = array
302 .clone()
303 .execute::<StructArray>(&mut ctx)?
304 .unmasked_field_by_name(field)?
305 .clone();
306 array = next;
307 }
308 Ok(array)
309 }
310
311 #[test]
312 pub fn test_merge_right_most() {
313 let mut ctx = SESSION.create_execution_ctx();
314 let expr = merge_opts(
315 vec![
316 get_item("0", root()),
317 get_item("1", root()),
318 get_item("2", root()),
319 ],
320 DuplicateHandling::RightMost,
321 );
322
323 let test_array = StructArray::from_fields(&[
324 (
325 "0",
326 StructArray::from_fields(&[
327 ("a", buffer![0, 0, 0].into_array()),
328 ("b", buffer![1, 1, 1].into_array()),
329 ])
330 .unwrap()
331 .into_array(),
332 ),
333 (
334 "1",
335 StructArray::from_fields(&[
336 ("b", buffer![2, 2, 2].into_array()),
337 ("c", buffer![3, 3, 3].into_array()),
338 ])
339 .unwrap()
340 .into_array(),
341 ),
342 (
343 "2",
344 StructArray::from_fields(&[
345 ("d", buffer![4, 4, 4].into_array()),
346 ("e", buffer![5, 5, 5].into_array()),
347 ])
348 .unwrap()
349 .into_array(),
350 ),
351 ])
352 .unwrap()
353 .into_array();
354 let actual_array = test_array.apply(&expr).unwrap();
355
356 assert_eq!(
357 actual_array.dtype().as_struct_fields().names(),
358 ["a", "b", "c", "d", "e"]
359 );
360
361 assert_arrays_eq!(
362 field_array(&actual_array, &["a"]).unwrap(),
363 PrimitiveArray::from_iter([0i32, 0, 0]),
364 &mut ctx
365 );
366 assert_arrays_eq!(
367 field_array(&actual_array, &["b"]).unwrap(),
368 PrimitiveArray::from_iter([2i32, 2, 2]),
369 &mut ctx
370 );
371 assert_arrays_eq!(
372 field_array(&actual_array, &["c"]).unwrap(),
373 PrimitiveArray::from_iter([3i32, 3, 3]),
374 &mut ctx
375 );
376 assert_arrays_eq!(
377 field_array(&actual_array, &["d"]).unwrap(),
378 PrimitiveArray::from_iter([4i32, 4, 4]),
379 &mut ctx
380 );
381 assert_arrays_eq!(
382 field_array(&actual_array, &["e"]).unwrap(),
383 PrimitiveArray::from_iter([5i32, 5, 5]),
384 &mut ctx
385 );
386 }
387
388 #[test]
389 #[should_panic(expected = "merge: duplicate fields in children")]
390 pub fn test_merge_error_on_dupe_return_dtype() {
391 let expr = merge_opts(
392 vec![get_item("0", root()), get_item("1", root())],
393 DuplicateHandling::Error,
394 );
395 let test_array = StructArray::try_from_iter([
396 (
397 "0",
398 StructArray::try_from_iter([("a", buffer![1]), ("b", buffer![1])]).unwrap(),
399 ),
400 (
401 "1",
402 StructArray::try_from_iter([("c", buffer![1]), ("b", buffer![1])]).unwrap(),
403 ),
404 ])
405 .unwrap()
406 .into_array();
407
408 expr.return_dtype(test_array.dtype()).unwrap();
409 }
410
411 #[test]
412 #[should_panic(expected = "merge: duplicate fields in children")]
413 pub fn test_merge_error_on_dupe_evaluate() {
414 let expr = merge_opts(
415 vec![get_item("0", root()), get_item("1", root())],
416 DuplicateHandling::Error,
417 );
418 let test_array = StructArray::try_from_iter([
419 (
420 "0",
421 StructArray::try_from_iter([("a", buffer![1]), ("b", buffer![1])]).unwrap(),
422 ),
423 (
424 "1",
425 StructArray::try_from_iter([("c", buffer![1]), ("b", buffer![1])]).unwrap(),
426 ),
427 ])
428 .unwrap()
429 .into_array();
430
431 test_array.apply(&expr).unwrap();
432 }
433
434 #[test]
435 pub fn test_empty_merge() {
436 let expr = merge(Vec::<Expression>::new());
437
438 let test_array = StructArray::from_fields(&[("a", buffer![0, 1, 2].into_array())])
439 .unwrap()
440 .into_array();
441 let actual_array = test_array.clone().apply(&expr).unwrap();
442 assert_eq!(actual_array.len(), test_array.len());
443 let expected = StructArray::try_new(
444 Default::default(),
445 vec![],
446 3,
447 crate::validity::Validity::NonNullable,
448 )
449 .unwrap();
450 assert_arrays_eq!(actual_array, expected, &mut SESSION.create_execution_ctx());
451 }
452
453 #[test]
454 pub fn test_nested_merge() {
455 let expr = merge_opts(
458 vec![get_item("0", root()), get_item("1", root())],
459 DuplicateHandling::RightMost,
460 );
461
462 let test_array = StructArray::from_fields(&[
463 (
464 "0",
465 StructArray::from_fields(&[(
466 "a",
467 StructArray::from_fields(&[
468 ("x", buffer![0, 0, 0].into_array()),
469 ("y", buffer![1, 1, 1].into_array()),
470 ])
471 .unwrap()
472 .into_array(),
473 )])
474 .unwrap()
475 .into_array(),
476 ),
477 (
478 "1",
479 StructArray::from_fields(&[(
480 "a",
481 StructArray::from_fields(&[("x", buffer![0, 0, 0].into_array())])
482 .unwrap()
483 .into_array(),
484 )])
485 .unwrap()
486 .into_array(),
487 ),
488 ])
489 .unwrap()
490 .into_array();
491 let mut ctx = SESSION.create_execution_ctx();
492 let actual_array = test_array
493 .apply(&expr)
494 .unwrap()
495 .execute::<StructArray>(&mut ctx)
496 .unwrap();
497
498 let inner_struct = actual_array.unmasked_field_by_name("a").unwrap();
499 assert_eq!(
500 inner_struct
501 .dtype()
502 .as_struct_fields()
503 .names()
504 .iter()
505 .map(|name| name.as_ref())
506 .collect::<Vec<_>>(),
507 vec!["x"]
508 );
509 assert_arrays_eq!(
510 inner_struct,
511 StructArray::from_fields(&[("x", buffer![0i32, 0, 0].into_array())]).unwrap(),
512 &mut ctx
513 );
514 }
515
516 #[test]
517 pub fn test_merge_order() {
518 let mut ctx = SESSION.create_execution_ctx();
519 let expr = merge(vec![get_item("0", root()), get_item("1", root())]);
520
521 let test_array = StructArray::from_fields(&[
522 (
523 "0",
524 StructArray::from_fields(&[
525 ("a", buffer![0, 0, 0].into_array()),
526 ("c", buffer![1, 1, 1].into_array()),
527 ])
528 .unwrap()
529 .into_array(),
530 ),
531 (
532 "1",
533 StructArray::from_fields(&[
534 ("b", buffer![2, 2, 2].into_array()),
535 ("d", buffer![3, 3, 3].into_array()),
536 ])
537 .unwrap()
538 .into_array(),
539 ),
540 ])
541 .unwrap()
542 .into_array();
543 let actual_array = test_array.apply(&expr).unwrap();
544
545 assert_eq!(
546 actual_array.dtype().as_struct_fields().names(),
547 ["a", "c", "b", "d"]
548 );
549 let expected = StructArray::from_fields(&[
550 ("a", buffer![0i32, 0, 0].into_array()),
551 ("c", buffer![1i32, 1, 1].into_array()),
552 ("b", buffer![2i32, 2, 2].into_array()),
553 ("d", buffer![3i32, 3, 3].into_array()),
554 ])
555 .unwrap();
556 assert_arrays_eq!(actual_array, expected, &mut ctx);
557 }
558
559 #[test]
560 pub fn test_display() {
561 let expr = merge([get_item("struct1", root()), get_item("struct2", root())]);
562 assert_eq!(
563 expr.to_string(),
564 "vortex.merge($.struct1, $.struct2, opts=Error)"
565 );
566
567 let expr2 = merge(vec![get_item("a", root())]);
568 assert_eq!(expr2.to_string(), "vortex.merge($.a, opts=Error)");
569 }
570
571 #[test]
572 fn test_remove_merge() {
573 let dtype = DType::struct_(
574 [
575 ("0", DType::struct_([("a", I32), ("b", I64)], NonNullable)),
576 ("1", DType::struct_([("b", U32), ("c", U64)], NonNullable)),
577 ],
578 NonNullable,
579 );
580
581 let e = merge_opts(
582 [get_item("0", root()), get_item("1", root())],
583 DuplicateHandling::RightMost,
584 );
585
586 let result = e.bind(&dtype).unwrap().optimize().unwrap();
587
588 assert!(result.is::<Pack>());
589 assert_eq!(
590 result.dtype(),
591 &DType::struct_([("a", I32), ("b", U32), ("c", U64)], NonNullable)
592 );
593 }
594}