Skip to main content

arrow_select/
merge.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! [`merge`] and [`merge_n`]: Combine values from two or more arrays
6
7use 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
16/// An index for the [merge_n] function.
17///
18/// This trait allows the indices argument for [merge_n] to be stored using a more
19/// compact representation than `usize` when the input arrays are small.
20/// If the number of input arrays is less than 256 for instance, the indices can be stored as `u8`.
21///
22/// Implementation must ensure that all values which return `None` from [MergeIndex::index] are
23/// considered equal by the [PartialEq] and [Eq] implementations.
24pub trait MergeIndex: PartialEq + Eq + Copy {
25    /// Returns the index value as an `Option<usize>`.
26    ///
27    /// `None` values returned by this function indicate holes in the index array and will result
28    /// in null values in the array created by [merge].
29    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
44/// Merges elements by index from a list of [`Array`], creating a new [`Array`] from
45/// those values.
46///
47/// Each element in `indices` is the index of an array in `values`. The `indices` array is processed
48/// sequentially. The first occurrence of index value `n` will be mapped to the first
49/// value of the array at index `n`. The second occurrence to the second value, and so on.
50/// An index value where `MergeIndex::index` returns `None` is interpreted as a null value.
51///
52/// # Implementation notes
53///
54/// This algorithm is similar in nature to both [zip] and
55/// [interleave](crate::interleave::interleave), but there are some important differences.
56///
57/// In contrast to [zip], this function supports multiple input arrays. Instead of
58/// a boolean selection vector, an index array is to take values from the input arrays, and a special
59/// marker values can be used to indicate null values.
60///
61/// In contrast to [interleave](crate::interleave::interleave), this function does not use pairs of
62/// indices. The values in `indices` serve the same purpose as the first value in the pairs passed
63/// to `interleave`.
64/// The index in the array is implicit and is derived from the number of times a particular array
65/// index occurs.
66/// The more constrained indexing mechanism used by this algorithm makes it easier to copy values
67/// in contiguous slices. In the example below, the two subsequent elements from array `2` can be
68/// copied in a single operation from the source array instead of copying them one by one.
69/// Long spans of null values are also especially cheap because they do not need to be represented
70/// in an input array.
71///
72/// # Panics
73///
74/// This function does not check that the number of occurrences of any particular array index matches
75/// the length of the corresponding input array. If an array contains more values than required, the
76/// spurious values will be ignored. If an array contains fewer values than necessary, this function
77/// will panic.
78///
79/// # Example
80///
81/// ```text
82/// ┌───────────┐  ┌─────────┐                             ┌─────────┐
83/// │┌─────────┐│  │   None  │                             │   NULL  │
84/// ││    A    ││  ├─────────┤                             ├─────────┤
85/// │└─────────┘│  │    1    │                             │    B    │
86/// │┌─────────┐│  ├─────────┤                             ├─────────┤
87/// ││    B    ││  │    0    │    merge(values, indices)   │    A    │
88/// │└─────────┘│  ├─────────┤  ─────────────────────────▶ ├─────────┤
89/// │┌─────────┐│  │   None  │                             │   NULL  │
90/// ││    C    ││  ├─────────┤                             ├─────────┤
91/// │├─────────┤│  │    2    │                             │    C    │
92/// ││    D    ││  ├─────────┤                             ├─────────┤
93/// │└─────────┘│  │    2    │                             │    D    │
94/// └───────────┘  └─────────┘                             └─────────┘
95///    values        indices                                  result
96///
97/// ```
98pub 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        // `MutableArrayData` concatenates the dictionaries, which can overflow
139        // the key type even when their merged values fit, so let `interleave`
140        // merge them instead
141        Err(ArrowError::DictionaryKeyOverflowError) => {
142            return merge_n_with_interleave(values, indices);
143        }
144        Err(e) => return Err(e),
145    };
146
147    // This loop extends the mutable array by taking slices from the partial results.
148    //
149    // take_offsets keeps track of how many values have been taken from each array.
150    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        // Determine the length of the slice to take.
156        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        // Extend mutable with either nulls or with values from the array.
163        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        // Set the start_row_ix for the next slice.
177        start_row_ix = end_row_ix;
178    }
179
180    Ok(make_array(mutable.freeze()))
181}
182
183/// [merge_n] through [interleave](crate::interleave::interleave), which merges
184/// dictionaries instead of concatenating them
185fn merge_n_with_interleave(
186    values: &[&dyn Array],
187    indices: &[impl MergeIndex],
188) -> Result<ArrayRef, ArrowError> {
189    // `interleave` has no null index, so null rows read from an extra
190    // single null array
191    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
210/// [merge] through [interleave](crate::interleave::interleave), which merges
211/// dictionaries instead of concatenating them
212fn 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            // Nulls in the mask are treated as false
224            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
238/// Merges two arrays in the order specified by a boolean mask.
239///
240/// This algorithm is a variant of [zip] that does not require the truthy and
241/// falsy arrays to have the same length.
242///
243/// When truthy of falsy are [Scalar](arrow_array::Scalar), the single
244/// scalar value is repeated whenever the mask array contains true or false respectively.
245///
246/// # Example
247///
248/// ```text
249///  truthy
250/// ┌─────────┐  mask
251/// │    A    │  ┌─────────┐                             ┌─────────┐
252/// ├─────────┤  │  true   │                             │    A    │
253/// │    C    │  ├─────────┤                             ├─────────┤
254/// ├─────────┤  │  true   │                             │    C    │
255/// │   NULL  │  ├─────────┤                             ├─────────┤
256/// ├─────────┤  │  false  │  merge(mask, truthy, falsy) │    B    │
257/// │    D    │  ├─────────┤  ─────────────────────────▶ ├─────────┤
258/// └─────────┘  │  true   │                             │   NULL  │
259///  falsy       ├─────────┤                             ├─────────┤
260/// ┌─────────┐  │  false  │                             │    E    │
261/// │    B    │  ├─────────┤                             ├─────────┤
262/// ├─────────┤  │  true   │                             │    D    │
263/// │    E    │  └─────────┘                             └─────────┘
264/// └─────────┘
265/// ```
266pub 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        // When both truthy and falsy are scalars, we can use `zip` since the result is the same
276        // and zip has optimized code for scalars.
277        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        // See `merge_n`: let `interleave` merge the dictionaries
303        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    // the SlicesIterator slices only the true values. So the gaps left by this iterator we need to
316    // fill with falsy values
317
318    // keep track of how much is filled
319    let mut filled = 0;
320    let mut falsy_offset = 0;
321    let mut truthy_offset = 0;
322
323    // Ensure nulls are treated as false
324    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        // the gap needs to be filled with falsy values
331        if start > filled {
332            if falsy_is_scalar {
333                for _ in filled..start {
334                    // Copy the first item from the 'falsy' array into the output buffer.
335                    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        // fill with truthy values
345        if truthy_is_scalar {
346            for _ in start..end {
347                // Copy the first item from the 'truthy' array into the output buffer.
348                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    // the remaining part is falsy
359    if filled < mask.len() {
360        if falsy_is_scalar {
361            for _ in filled..mask.len() {
362                // Copy the first item from the 'falsy' array into the output buffer.
363                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    // The message differs between debug and release: in release the
638    // `cfg(debug_assertions)` bounds check in `merge_n` is compiled out and the
639    // slice index panics instead.
640    #[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    /// Two dictionaries of 100 values, the same in both. Concatenating them
691    /// overflows Int8 keys, but the merged dictionary fits
692    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}