1use crate::filter::{SlicesIterator, prep_null_mask_filter};
8use crate::zip::zip;
9use arrow_array::{
10 Array, ArrayRef, BooleanArray, Datum, make_array, new_empty_array, new_null_array,
11};
12use arrow_data::ArrayData;
13use arrow_data::transform::MutableArrayData;
14use arrow_schema::ArrowError;
15
16pub trait MergeIndex: PartialEq + Eq + Copy {
25 fn index(&self) -> Option<usize>;
30}
31
32impl MergeIndex for usize {
33 fn index(&self) -> Option<usize> {
34 Some(*self)
35 }
36}
37
38impl MergeIndex for Option<usize> {
39 fn index(&self) -> Option<usize> {
40 *self
41 }
42}
43
44pub fn merge_n(values: &[&dyn Array], indices: &[impl MergeIndex]) -> Result<ArrayRef, ArrowError> {
99 if values.is_empty() {
100 return Err(ArrowError::InvalidArgumentError(
101 "merge_n requires at least one value array".to_string(),
102 ));
103 }
104
105 let data_type = values[0].data_type();
106
107 for array in values.iter().skip(1) {
108 if array.data_type() != data_type {
109 return Err(ArrowError::InvalidArgumentError(format!(
110 "It is not possible to merge arrays of different data types ({} and {})",
111 data_type,
112 array.data_type()
113 )));
114 }
115 }
116
117 if indices.is_empty() {
118 return Ok(new_empty_array(data_type));
119 }
120
121 #[cfg(debug_assertions)]
122 for ix in indices {
123 if let Some(index) = ix.index() {
124 assert!(
125 index < values.len(),
126 "Index out of bounds: {} >= {}",
127 index,
128 values.len()
129 );
130 }
131 }
132
133 let data: Vec<ArrayData> = values.iter().map(|a| a.to_data()).collect();
134 let data_refs = data.iter().collect();
135
136 let mut mutable = match MutableArrayData::try_new(data_refs, true, indices.len()) {
137 Ok(mutable) => mutable,
138 Err(ArrowError::DictionaryKeyOverflowError) => {
142 return merge_n_with_interleave(values, indices);
143 }
144 Err(e) => return Err(e),
145 };
146
147 let mut take_offsets = vec![0; values.len() + 1];
151 let mut start_row_ix = 0;
152 loop {
153 let array_ix = indices[start_row_ix];
154
155 let mut end_row_ix = start_row_ix + 1;
157 while end_row_ix < indices.len() && indices[end_row_ix] == array_ix {
158 end_row_ix += 1;
159 }
160 let slice_length = end_row_ix - start_row_ix;
161
162 match array_ix.index() {
164 None => mutable.try_extend_nulls(slice_length)?,
165 Some(index) => {
166 let start_offset = take_offsets[index];
167 let end_offset = start_offset + slice_length;
168 mutable.try_extend(index, start_offset, end_offset)?;
169 take_offsets[index] = end_offset;
170 }
171 }
172
173 if end_row_ix == indices.len() {
174 break;
175 }
176 start_row_ix = end_row_ix;
178 }
179
180 Ok(make_array(mutable.freeze()))
181}
182
183fn merge_n_with_interleave(
186 values: &[&dyn Array],
187 indices: &[impl MergeIndex],
188) -> Result<ArrayRef, ArrowError> {
189 let nulls = new_null_array(values[0].data_type(), 1);
192 let mut arrays = values.to_vec();
193 arrays.push(nulls.as_ref());
194
195 let mut take_offsets = vec![0; values.len()];
196 let interleave_indices: Vec<_> = indices
197 .iter()
198 .map(|ix| match ix.index() {
199 None => (values.len(), 0),
200 Some(index) => {
201 let offset = take_offsets[index];
202 take_offsets[index] += 1;
203 (index, offset)
204 }
205 })
206 .collect();
207 crate::interleave::interleave(&arrays, &interleave_indices)
208}
209
210fn merge_with_interleave(
213 mask: &BooleanArray,
214 truthy: &dyn Array,
215 truthy_is_scalar: bool,
216 falsy: &dyn Array,
217 falsy_is_scalar: bool,
218) -> Result<ArrayRef, ArrowError> {
219 let mut truthy_offset = 0;
220 let mut falsy_offset = 0;
221 let indices: Vec<_> = (0..mask.len())
222 .map(|idx| {
223 if mask.is_valid(idx) && mask.value(idx) {
225 let offset = if truthy_is_scalar { 0 } else { truthy_offset };
226 truthy_offset += 1;
227 (0, offset)
228 } else {
229 let offset = if falsy_is_scalar { 0 } else { falsy_offset };
230 falsy_offset += 1;
231 (1, offset)
232 }
233 })
234 .collect();
235 crate::interleave::interleave(&[truthy, falsy], &indices)
236}
237
238pub fn merge(
267 mask: &BooleanArray,
268 truthy: &dyn Datum,
269 falsy: &dyn Datum,
270) -> Result<ArrayRef, ArrowError> {
271 let (truthy_array, truthy_is_scalar) = truthy.get();
272 let (falsy_array, falsy_is_scalar) = falsy.get();
273
274 if truthy_is_scalar && falsy_is_scalar {
275 return zip(mask, truthy, falsy);
278 }
279
280 if truthy_array.data_type() != falsy_array.data_type() {
281 return Err(ArrowError::InvalidArgumentError(
282 "arguments need to have the same data type".into(),
283 ));
284 }
285
286 if truthy_is_scalar && truthy_array.len() != 1 {
287 return Err(ArrowError::InvalidArgumentError(
288 "scalar arrays must have 1 element".into(),
289 ));
290 }
291 if falsy_is_scalar && falsy_array.len() != 1 {
292 return Err(ArrowError::InvalidArgumentError(
293 "scalar arrays must have 1 element".into(),
294 ));
295 }
296
297 let falsy = falsy_array.to_data();
298 let truthy = truthy_array.to_data();
299
300 let mut mutable = match MutableArrayData::try_new(vec![&truthy, &falsy], false, mask.len()) {
301 Ok(mutable) => mutable,
302 Err(ArrowError::DictionaryKeyOverflowError) => {
304 return merge_with_interleave(
305 mask,
306 truthy_array,
307 truthy_is_scalar,
308 falsy_array,
309 falsy_is_scalar,
310 );
311 }
312 Err(e) => return Err(e),
313 };
314
315 let mut filled = 0;
320 let mut falsy_offset = 0;
321 let mut truthy_offset = 0;
322
323 let mask_buffer = match mask.null_count() {
325 0 => mask.values().clone(),
326 _ => prep_null_mask_filter(mask).into_parts().0,
327 };
328
329 for (start, end) in SlicesIterator::from(&mask_buffer) {
330 if start > filled {
332 if falsy_is_scalar {
333 for _ in filled..start {
334 mutable.try_extend(1, 0, 1)?;
336 }
337 } else {
338 let falsy_length = start - filled;
339 let falsy_end = falsy_offset + falsy_length;
340 mutable.try_extend(1, falsy_offset, falsy_end)?;
341 falsy_offset = falsy_end;
342 }
343 }
344 if truthy_is_scalar {
346 for _ in start..end {
347 mutable.try_extend(0, 0, 1)?;
349 }
350 } else {
351 let truthy_length = end - start;
352 let truthy_end = truthy_offset + truthy_length;
353 mutable.try_extend(0, truthy_offset, truthy_end)?;
354 truthy_offset = truthy_end;
355 }
356 filled = end;
357 }
358 if filled < mask.len() {
360 if falsy_is_scalar {
361 for _ in filled..mask.len() {
362 mutable.try_extend(1, 0, 1)?;
364 }
365 } else {
366 let falsy_length = mask.len() - filled;
367 let falsy_end = falsy_offset + falsy_length;
368 mutable.try_extend(1, falsy_offset, falsy_end)?;
369 }
370 }
371
372 let data = mutable.freeze();
373 Ok(make_array(data))
374}
375
376#[cfg(test)]
377mod tests {
378 use crate::merge::{MergeIndex, merge, merge_n};
379 use arrow_array::cast::AsArray;
380 use arrow_array::types::Int8Type;
381 use arrow_array::{
382 Array, ArrayRef, BooleanArray, Datum, DictionaryArray, Int8Array, Int32Array, Scalar,
383 StringArray, UInt64Array,
384 };
385 use arrow_schema::ArrowError::InvalidArgumentError;
386 use std::sync::Arc;
387
388 #[derive(PartialEq, Eq, Copy, Clone)]
389 struct CompactMergeIndex {
390 index: u8,
391 }
392
393 impl MergeIndex for CompactMergeIndex {
394 fn index(&self) -> Option<usize> {
395 if self.index == u8::MAX {
396 None
397 } else {
398 Some(self.index as usize)
399 }
400 }
401 }
402
403 #[test]
404 fn test_merge() {
405 let a1 = StringArray::from(vec![Some("A"), Some("B"), Some("E"), None]);
406 let a2 = StringArray::from(vec![Some("C"), Some("D")]);
407
408 let indices = BooleanArray::from(vec![true, false, true, false, true, true]);
409
410 let merged = merge(&indices, &a1, &a2).unwrap();
411 let merged = merged.as_string::<i32>();
412
413 assert_eq!(merged.len(), indices.len());
414 assert!(merged.is_valid(0));
415 assert_eq!(merged.value(0), "A");
416 assert!(merged.is_valid(1));
417 assert_eq!(merged.value(1), "C");
418 assert!(merged.is_valid(2));
419 assert_eq!(merged.value(2), "B");
420 assert!(merged.is_valid(3));
421 assert_eq!(merged.value(3), "D");
422 assert!(merged.is_valid(4));
423 assert_eq!(merged.value(4), "E");
424 assert!(!merged.is_valid(5));
425 }
426
427 #[test]
428 fn test_merge_null_is_false() {
429 let a1 = StringArray::from(vec![Some("A"), Some("B"), Some("E"), None]);
430 let a2 = StringArray::from(vec![Some("C"), Some("D")]);
431
432 let indices = BooleanArray::from(vec![
433 Some(true),
434 None,
435 Some(true),
436 None,
437 Some(true),
438 Some(true),
439 ]);
440
441 let merged = merge(&indices, &a1, &a2).unwrap();
442 let merged = merged.as_string::<i32>();
443
444 assert_eq!(merged.len(), indices.len());
445 assert!(merged.is_valid(0));
446 assert_eq!(merged.value(0), "A");
447 assert!(merged.is_valid(1));
448 assert_eq!(merged.value(1), "C");
449 assert!(merged.is_valid(2));
450 assert_eq!(merged.value(2), "B");
451 assert!(merged.is_valid(3));
452 assert_eq!(merged.value(3), "D");
453 assert!(merged.is_valid(4));
454 assert_eq!(merged.value(4), "E");
455 assert!(!merged.is_valid(5));
456 }
457
458 #[test]
459 fn test_merge_false_tail() {
460 let a1 = StringArray::from(vec![Some("A"), Some("B"), Some("E"), None]);
461 let a2 = StringArray::from(vec![Some("C"), Some("D"), None, Some("F")]);
462
463 let indices = BooleanArray::from(vec![true, false, true, false, true, true, false, false]);
464
465 let merged = merge(&indices, &a1, &a2).unwrap();
466 let merged = merged.as_string::<i32>();
467
468 assert_eq!(merged.len(), indices.len());
469 assert!(merged.is_valid(0));
470 assert_eq!(merged.value(0), "A");
471 assert!(merged.is_valid(1));
472 assert_eq!(merged.value(1), "C");
473 assert!(merged.is_valid(2));
474 assert_eq!(merged.value(2), "B");
475 assert!(merged.is_valid(3));
476 assert_eq!(merged.value(3), "D");
477 assert!(merged.is_valid(4));
478 assert_eq!(merged.value(4), "E");
479 assert!(!merged.is_valid(5));
480 assert!(!merged.is_valid(6));
481 assert!(merged.is_valid(7));
482 assert_eq!(merged.value(7), "F");
483 }
484
485 #[test]
486 fn test_merge_scalars() {
487 let truthy = Scalar::new(StringArray::from(vec![Some("A")]));
488 let falsy = Scalar::new(StringArray::from(vec![Some("B")]));
489
490 let mask = BooleanArray::from(vec![true, false, false, true]);
491
492 let merged = merge(&mask, &truthy, &falsy).unwrap();
493 let merged = merged.as_string::<i32>();
494
495 assert_eq!(merged.len(), mask.len());
496 assert!(merged.is_valid(0));
497 assert_eq!(merged.value(0), "A");
498 assert!(merged.is_valid(1));
499 assert_eq!(merged.value(1), "B");
500 assert!(merged.is_valid(2));
501 assert_eq!(merged.value(2), "B");
502 assert!(merged.is_valid(3));
503 assert_eq!(merged.value(3), "A");
504 }
505
506 #[test]
507 fn test_merge_scalar_and_array() {
508 let truthy = Scalar::new(StringArray::from(vec![Some("A")]));
509 let falsy = StringArray::from(vec![Some("B"), Some("C")]);
510
511 let mask = BooleanArray::from(vec![true, false, false, true]);
512
513 let merged = merge(&mask, &truthy, &falsy).unwrap();
514 let merged = merged.as_string::<i32>();
515
516 assert_eq!(merged.len(), mask.len());
517 assert!(merged.is_valid(0));
518 assert_eq!(merged.value(0), "A");
519 assert!(merged.is_valid(1));
520 assert_eq!(merged.value(1), "B");
521 assert!(merged.is_valid(2));
522 assert_eq!(merged.value(2), "C");
523 assert!(merged.is_valid(3));
524 assert_eq!(merged.value(3), "A");
525 }
526
527 #[test]
528 fn test_merge_array_and_scalar() {
529 let truthy = StringArray::from(vec![Some("B"), Some("C")]);
530 let falsy = Scalar::new(StringArray::from(vec![Some("A")]));
531
532 let mask = BooleanArray::from(vec![true, false, false, true, false, false]);
533
534 let merged = merge(&mask, &truthy, &falsy).unwrap();
535 let merged = merged.as_string::<i32>();
536
537 assert_eq!(merged.len(), mask.len());
538 assert!(merged.is_valid(0));
539 assert_eq!(merged.value(0), "B");
540 assert!(merged.is_valid(1));
541 assert_eq!(merged.value(1), "A");
542 assert!(merged.is_valid(2));
543 assert_eq!(merged.value(2), "A");
544 assert!(merged.is_valid(3));
545 assert_eq!(merged.value(3), "C");
546 assert!(merged.is_valid(4));
547 assert_eq!(merged.value(4), "A");
548 assert!(merged.is_valid(5));
549 assert_eq!(merged.value(5), "A");
550 }
551
552 #[test]
553 fn test_merge_empty_mask() {
554 let a1 = StringArray::from(vec![Some("A")]);
555 let a2 = StringArray::from(vec![Some("B")]);
556 let mask: Vec<bool> = vec![];
557 let mask = BooleanArray::from(mask);
558 let result = merge(&mask, &a1, &a2).unwrap();
559 assert_eq!(result.len(), 0);
560 }
561
562 #[derive(Debug, Copy, Clone)]
563 pub struct UnsafeScalar<T: Array>(T);
564
565 impl<T: Array> Datum for UnsafeScalar<T> {
566 fn get(&self) -> (&dyn Array, bool) {
567 (&self.0, true)
568 }
569 }
570
571 #[test]
572 fn test_merge_invalid_truthy_scalar() {
573 let truthy = UnsafeScalar(StringArray::from(vec![Some("A"), Some("C")]));
574 let falsy = StringArray::from(vec![Some("B"), Some("D")]);
575 let mask = BooleanArray::from(vec![true, false, true, false]);
576 let merged = merge(&mask, &truthy, &falsy);
577 assert!(matches!(merged, Err(InvalidArgumentError { .. })));
578 }
579
580 #[test]
581 fn test_merge_invalid_falsy_scalar() {
582 let truthy = StringArray::from(vec![Some("A"), Some("C")]);
583 let falsy = UnsafeScalar(StringArray::from(vec![Some("B"), Some("D")]));
584 let mask = vec![true, false, true, false];
585 let mask = BooleanArray::from(mask);
586 let merged = merge(&mask, &truthy, &falsy);
587 assert!(matches!(merged, Err(InvalidArgumentError { .. })));
588 }
589
590 #[test]
591 fn test_merge_incompatible_arrays() {
592 let truthy = StringArray::from(vec![Some("A"), Some("B")]);
593 let falsy = Int32Array::from(vec![1, 2]);
594 let mask = BooleanArray::from(vec![true, false, true, false]);
595 let merged = merge(&mask, &truthy, &falsy);
596 assert!(matches!(merged, Err(InvalidArgumentError { .. })));
597 }
598
599 #[test]
600 fn test_merge_n() {
601 let a1 = StringArray::from(vec![Some("A")]);
602 let a2 = StringArray::from(vec![Some("B"), None, None]);
603 let a3 = StringArray::from(vec![Some("C"), Some("D")]);
604
605 let indices = vec![
606 CompactMergeIndex { index: u8::MAX },
607 CompactMergeIndex { index: 1 },
608 CompactMergeIndex { index: 0 },
609 CompactMergeIndex { index: u8::MAX },
610 CompactMergeIndex { index: 2 },
611 CompactMergeIndex { index: 2 },
612 CompactMergeIndex { index: 1 },
613 CompactMergeIndex { index: 1 },
614 ];
615
616 let arrays = [a1, a2, a3];
617 let array_refs = arrays.iter().map(|a| a as &dyn Array).collect::<Vec<_>>();
618 let merged = merge_n(&array_refs, &indices).unwrap();
619 let merged = merged.as_string::<i32>();
620
621 assert_eq!(merged.len(), indices.len());
622 assert!(!merged.is_valid(0));
623 assert!(merged.is_valid(1));
624 assert_eq!(merged.value(1), "B");
625 assert!(merged.is_valid(2));
626 assert_eq!(merged.value(2), "A");
627 assert!(!merged.is_valid(3));
628 assert!(merged.is_valid(4));
629 assert_eq!(merged.value(4), "C");
630 assert!(merged.is_valid(5));
631 assert_eq!(merged.value(5), "D");
632 assert!(!merged.is_valid(6));
633 assert!(!merged.is_valid(7));
634 }
635
636 #[test]
637 #[should_panic(expected = "out of bounds")]
641 fn test_merge_n_invalid_indices() {
642 let a1 = StringArray::from(vec![Some("A")]);
643
644 let indices = vec![CompactMergeIndex { index: 99 }];
645
646 let arrays = [a1];
647 let array_refs = arrays.iter().map(|a| a as &dyn Array).collect::<Vec<_>>();
648 let _ = merge_n(&array_refs, &indices);
649 }
650
651 #[test]
652 fn test_merge_n_empty_indices() {
653 let a1 = StringArray::from(vec![Some("A")]);
654 let a2 = StringArray::from(vec![Some("B"), None, None]);
655 let a3 = StringArray::from(vec![Some("C"), Some("D")]);
656
657 let indices: Vec<CompactMergeIndex> = vec![];
658
659 let arrays = [a1, a2, a3];
660 let array_refs = arrays.iter().map(|a| a as &dyn Array).collect::<Vec<_>>();
661 let merged = merge_n(&array_refs, &indices).unwrap();
662
663 assert_eq!(merged.len(), indices.len());
664 }
665
666 #[test]
667 fn test_merge_n_empty_values() {
668 let indices: Vec<CompactMergeIndex> = vec![];
669
670 let arrays: Vec<&dyn Array> = vec![];
671 let merged = merge_n(&arrays, &indices);
672
673 assert!(matches!(merged, Err(InvalidArgumentError { .. })));
674 }
675
676 #[test]
677 fn test_merge_n_incompatible_arrays() {
678 let a1: Box<dyn Array> = Box::new(StringArray::from(vec![Some("A")]));
679 let a2: Box<dyn Array> = Box::new(Int32Array::from(vec![1, 2, 3]));
680 let a3: Box<dyn Array> = Box::new(UInt64Array::from(vec![42, 314]));
681
682 let indices: Vec<CompactMergeIndex> = vec![];
683
684 let arrays = [a1.as_ref(), a2.as_ref(), a3.as_ref()];
685 let merged = merge_n(&arrays, &indices);
686
687 assert!(matches!(merged, Err(InvalidArgumentError { .. })));
688 }
689
690 fn overflowing_dictionary(keys: Vec<Option<i8>>) -> ArrayRef {
693 let values: Vec<String> = (0..100).map(|i| format!("v{i}")).collect();
694 Arc::new(
695 DictionaryArray::<Int8Type>::try_new(
696 Int8Array::from(keys),
697 Arc::new(StringArray::from(values)),
698 )
699 .unwrap(),
700 )
701 }
702
703 fn dictionary_strings(array: &dyn Array) -> Vec<Option<&str>> {
704 array
705 .as_dictionary::<Int8Type>()
706 .downcast_dict::<StringArray>()
707 .unwrap()
708 .into_iter()
709 .collect()
710 }
711
712 #[test]
713 fn test_merge_dictionaries_whose_combined_values_overflow_the_key_type() {
714 let mask = BooleanArray::from(vec![Some(true), Some(false), None, Some(true), Some(false)]);
715 let truthy = overflowing_dictionary(vec![Some(0), None, Some(2)]);
716 let falsy = overflowing_dictionary(vec![Some(10), Some(20), Some(30)]);
717 let truthy_scalar = Scalar::new(overflowing_dictionary(vec![Some(7)]));
718 let falsy_scalar = Scalar::new(overflowing_dictionary(vec![Some(5)]));
719
720 let check =
721 |truthy_datum: &dyn Datum, falsy_datum: &dyn Datum, expected: [Option<&str>; 5]| {
722 let merged = merge(&mask, truthy_datum, falsy_datum).unwrap();
723 assert_eq!(merged.data_type(), truthy.data_type());
724 assert_eq!(dictionary_strings(merged.as_ref()), expected);
725 };
726 check(
727 &truthy,
728 &falsy,
729 [Some("v0"), Some("v10"), Some("v20"), None, Some("v30")],
730 );
731 check(
732 &truthy,
733 &falsy_scalar,
734 [Some("v0"), Some("v5"), Some("v5"), None, Some("v5")],
735 );
736 check(
737 &truthy_scalar,
738 &falsy,
739 [
740 Some("v7"),
741 Some("v10"),
742 Some("v20"),
743 Some("v7"),
744 Some("v30"),
745 ],
746 );
747 }
748
749 #[test]
750 fn test_merge_n_dictionaries_whose_combined_values_overflow_the_key_type() {
751 let a = overflowing_dictionary(vec![Some(0), Some(1)]);
752 let b = overflowing_dictionary(vec![Some(50), None]);
753 let indices = vec![Some(1), None, Some(0), Some(0), Some(1), None];
754
755 let merged = merge_n(&[a.as_ref(), b.as_ref()], &indices).unwrap();
756
757 assert_eq!(merged.data_type(), a.data_type());
758 assert_eq!(
759 dictionary_strings(merged.as_ref()),
760 [Some("v50"), None, Some("v0"), Some("v1"), None, None]
761 );
762 }
763}