Skip to main content

arrow_array/array/
union_array.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#![allow(clippy::enum_clike_unportable_variant)]
6
7use crate::{Array, ArrayRef, make_array};
8use arrow_buffer::bit_chunk_iterator::{BitChunkIterator, BitChunks};
9use arrow_buffer::buffer::NullBuffer;
10use arrow_buffer::{BooleanBuffer, Buffer, MutableBuffer, ScalarBuffer};
11use arrow_data::{ArrayData, ArrayDataBuilder};
12use arrow_schema::{ArrowError, DataType, UnionFields, UnionMode};
13/// Contains the `UnionArray` type.
14///
15use std::any::Any;
16use std::collections::HashSet;
17use std::sync::Arc;
18
19/// An array of [values of varying types](https://arrow.apache.org/docs/format/Columnar.html#union-layout)
20///
21/// Each slot in a [UnionArray] can have a value chosen from a number
22/// of types.  Each of the possible types are named like the fields of
23/// a [`StructArray`](crate::StructArray).  A `UnionArray` can
24/// have two possible memory layouts, "dense" or "sparse".  For more
25/// information on please see the
26/// [specification](https://arrow.apache.org/docs/format/Columnar.html#union-layout).
27///
28/// [UnionBuilder](crate::builder::UnionBuilder) can be used to
29/// create [UnionArray]'s of primitive types. `UnionArray`'s of nested
30/// types are also supported but not via `UnionBuilder`, see the tests
31/// for examples.
32///
33/// # Examples
34/// ## Create a dense UnionArray `[1, 3.2, 34]`
35/// ```
36/// use arrow_buffer::ScalarBuffer;
37/// use arrow_schema::*;
38/// use std::sync::Arc;
39/// use arrow_array::{Array, Int32Array, Float64Array, UnionArray};
40///
41/// let int_array = Int32Array::from(vec![1, 34]);
42/// let float_array = Float64Array::from(vec![3.2]);
43/// let type_ids = [0, 1, 0].into_iter().collect::<ScalarBuffer<i8>>();
44/// let offsets = [0, 0, 1].into_iter().collect::<ScalarBuffer<i32>>();
45///
46/// let union_fields = [
47///     (0, Arc::new(Field::new("A", DataType::Int32, false))),
48///     (1, Arc::new(Field::new("B", DataType::Float64, false))),
49/// ].into_iter().collect::<UnionFields>();
50///
51/// let children = vec![
52///     Arc::new(int_array) as Arc<dyn Array>,
53///     Arc::new(float_array),
54/// ];
55///
56/// let array = UnionArray::try_new(
57///     union_fields,
58///     type_ids,
59///     Some(offsets),
60///     children,
61/// ).unwrap();
62///
63/// let value = array.value(0).as_any().downcast_ref::<Int32Array>().unwrap().value(0);
64/// assert_eq!(1, value);
65///
66/// let value = array.value(1).as_any().downcast_ref::<Float64Array>().unwrap().value(0);
67/// assert!(3.2 - value < f64::EPSILON);
68///
69/// let value = array.value(2).as_any().downcast_ref::<Int32Array>().unwrap().value(0);
70/// assert_eq!(34, value);
71/// ```
72///
73/// ## Create a sparse UnionArray `[1, 3.2, 34]`
74/// ```
75/// use arrow_buffer::ScalarBuffer;
76/// use arrow_schema::*;
77/// use std::sync::Arc;
78/// use arrow_array::{Array, Int32Array, Float64Array, UnionArray};
79///
80/// let int_array = Int32Array::from(vec![Some(1), None, Some(34)]);
81/// let float_array = Float64Array::from(vec![None, Some(3.2), None]);
82/// let type_ids = [0_i8, 1, 0].into_iter().collect::<ScalarBuffer<i8>>();
83///
84/// let union_fields = [
85///     (0, Arc::new(Field::new("A", DataType::Int32, false))),
86///     (1, Arc::new(Field::new("B", DataType::Float64, false))),
87/// ].into_iter().collect::<UnionFields>();
88///
89/// let children = vec![
90///     Arc::new(int_array) as Arc<dyn Array>,
91///     Arc::new(float_array),
92/// ];
93///
94/// let array = UnionArray::try_new(
95///     union_fields,
96///     type_ids,
97///     None,
98///     children,
99/// ).unwrap();
100///
101/// let value = array.value(0).as_any().downcast_ref::<Int32Array>().unwrap().value(0);
102/// assert_eq!(1, value);
103///
104/// let value = array.value(1).as_any().downcast_ref::<Float64Array>().unwrap().value(0);
105/// assert!(3.2 - value < f64::EPSILON);
106///
107/// let value = array.value(2).as_any().downcast_ref::<Int32Array>().unwrap().value(0);
108/// assert_eq!(34, value);
109/// ```
110#[derive(Clone)]
111pub struct UnionArray {
112    data_type: DataType,
113    type_ids: ScalarBuffer<i8>,
114    offsets: Option<ScalarBuffer<i32>>,
115    fields: Vec<Option<ArrayRef>>,
116}
117
118impl UnionArray {
119    /// Creates a new `UnionArray`.
120    ///
121    /// Accepts type ids, child arrays and optionally offsets (for dense unions) to create
122    /// a new `UnionArray`.  This method makes no attempt to validate the data provided by the
123    /// caller and assumes that each of the components are correct and consistent with each other.
124    /// See `try_new` for an alternative that validates the data provided.
125    ///
126    /// # Safety
127    ///
128    /// The `type_ids` values should be non-negative and must match one of the type ids of the fields provided in `fields`.
129    /// These values are used to index into the `children` arrays.
130    ///
131    /// The `offsets` is provided in the case of a dense union, sparse unions should use `None`.
132    /// If provided the `offsets` values should be non-negative and must be less than the length of the
133    /// corresponding array.
134    ///
135    /// In both cases above we use signed integer types to maintain compatibility with other
136    /// Arrow implementations.
137    pub unsafe fn new_unchecked(
138        fields: UnionFields,
139        type_ids: ScalarBuffer<i8>,
140        offsets: Option<ScalarBuffer<i32>>,
141        children: Vec<ArrayRef>,
142    ) -> Self {
143        let mode = if offsets.is_some() {
144            UnionMode::Dense
145        } else {
146            UnionMode::Sparse
147        };
148
149        let len = type_ids.len();
150        let builder = ArrayData::builder(DataType::Union(fields, mode))
151            .add_buffer(type_ids.into_inner())
152            .child_data(children.into_iter().map(Array::into_data).collect())
153            .len(len);
154
155        let data = match offsets {
156            Some(offsets) => unsafe { builder.add_buffer(offsets.into_inner()).build_unchecked() },
157            None => unsafe { builder.build_unchecked() },
158        };
159        Self::from(data)
160    }
161
162    /// Attempts to create a new `UnionArray`, validating the inputs provided.
163    ///
164    /// The order of child arrays child array order must match the fields order
165    pub fn try_new(
166        fields: UnionFields,
167        type_ids: ScalarBuffer<i8>,
168        offsets: Option<ScalarBuffer<i32>>,
169        children: Vec<ArrayRef>,
170    ) -> Result<Self, ArrowError> {
171        // There must be a child array for every field.
172        if fields.len() != children.len() {
173            return Err(ArrowError::InvalidArgumentError(
174                "Union fields length must match child arrays length".to_string(),
175            ));
176        }
177
178        if let Some(offsets) = &offsets {
179            // There must be an offset value for every type id value.
180            if offsets.len() != type_ids.len() {
181                return Err(ArrowError::InvalidArgumentError(
182                    "Type Ids and Offsets lengths must match".to_string(),
183                ));
184            }
185        } else {
186            // Sparse union child arrays must be equal in length to the length of the union
187            for child in &children {
188                if child.len() != type_ids.len() {
189                    return Err(ArrowError::InvalidArgumentError(
190                        "Sparse union child arrays must be equal in length to the length of the union".to_string(),
191                    ));
192                }
193            }
194        }
195
196        // Create mapping from type id to array lengths.
197        let max_id = fields.iter().map(|(i, _)| i).max().unwrap_or_default() as usize;
198        let mut array_lens = vec![None; max_id + 1];
199        for (cd, (field_id, _)) in children.iter().zip(fields.iter()) {
200            array_lens[field_id as usize] = Some(cd.len());
201        }
202
203        // Type id values must match one of the fields.
204        for id in &type_ids {
205            match array_lens.get(*id as usize) {
206                Some(Some(_)) => {}
207                _ => {
208                    return Err(ArrowError::InvalidArgumentError(
209                        "Type Ids values must match one of the field type ids".to_owned(),
210                    ));
211                }
212            }
213        }
214
215        // Check the value offsets are in bounds.
216        if let Some(offsets) = &offsets {
217            let mut iter = type_ids.iter().zip(offsets.iter());
218            if iter.any(|(type_id, &offset)| {
219                offset < 0 || offset as usize >= array_lens[*type_id as usize].unwrap()
220            }) {
221                return Err(ArrowError::InvalidArgumentError(
222                    "Offsets must be non-negative and within the length of the Array".to_owned(),
223                ));
224            }
225        }
226
227        // Safety:
228        // - Arguments validated above.
229        let union_array = unsafe { Self::new_unchecked(fields, type_ids, offsets, children) };
230        Ok(union_array)
231    }
232
233    /// Accesses the child array for `type_id`.
234    ///
235    /// # Panics
236    ///
237    /// Panics if the `type_id` provided is not present in the array's DataType
238    /// in the `Union`.
239    pub fn child(&self, type_id: i8) -> &ArrayRef {
240        assert!((type_id as usize) < self.fields.len());
241        let boxed = &self.fields[type_id as usize];
242        boxed.as_ref().expect("invalid type id")
243    }
244
245    /// Returns the `type_id` for the array slot at `index`.
246    ///
247    /// # Panics
248    ///
249    /// Panics if `index` is greater than or equal to the number of child arrays
250    pub fn type_id(&self, index: usize) -> i8 {
251        assert!(index < self.type_ids.len());
252        self.type_ids[index]
253    }
254
255    /// Returns the `type_ids` buffer for this array
256    pub fn type_ids(&self) -> &ScalarBuffer<i8> {
257        &self.type_ids
258    }
259
260    /// Returns the `offsets` buffer if this is a dense array
261    pub fn offsets(&self) -> Option<&ScalarBuffer<i32>> {
262        self.offsets.as_ref()
263    }
264
265    /// Returns the offset into the underlying values array for the array slot at `index`.
266    ///
267    /// # Panics
268    ///
269    /// Panics if `index` is greater than or equal the length of the array.
270    pub fn value_offset(&self, index: usize) -> usize {
271        assert!(index < self.len());
272        match &self.offsets {
273            Some(offsets) => offsets[index] as usize,
274            None => self.offset() + index,
275        }
276    }
277
278    /// Returns the array's value at index `i`.
279    ///
280    /// Note: This method does not check for nulls and the value is arbitrary
281    /// (but still well-defined) if [`is_null`](Self::is_null) returns true for the index.
282    ///
283    /// # Panics
284    /// Panics if index `i` is out of bounds
285    pub fn value(&self, i: usize) -> ArrayRef {
286        let type_id = self.type_id(i);
287        let value_offset = self.value_offset(i);
288        let child = self.child(type_id);
289        child.slice(value_offset, 1)
290    }
291
292    /// Returns the names of the types in the union.
293    pub fn type_names(&self) -> Vec<&str> {
294        match self.data_type() {
295            DataType::Union(fields, _) => fields
296                .iter()
297                .map(|(_, f)| f.name().as_str())
298                .collect::<Vec<&str>>(),
299            _ => unreachable!("Union array's data type is not a union!"),
300        }
301    }
302
303    /// Returns the [`UnionFields`] for the union.
304    pub fn fields(&self) -> &UnionFields {
305        match self.data_type() {
306            DataType::Union(fields, _) => fields,
307            _ => unreachable!("Union array's data type is not a union!"),
308        }
309    }
310
311    /// Returns whether the `UnionArray` is dense (or sparse if `false`).
312    pub fn is_dense(&self) -> bool {
313        match self.data_type() {
314            DataType::Union(_, mode) => mode == &UnionMode::Dense,
315            _ => unreachable!("Union array's data type is not a union!"),
316        }
317    }
318
319    /// Returns a zero-copy slice of this array with the indicated offset and length.
320    ///
321    /// # Panics
322    /// Panics if `offset + length > self.len()`
323    pub fn slice(&self, offset: usize, length: usize) -> Self {
324        let (offsets, fields) = match self.offsets.as_ref() {
325            // If dense union, slice offsets
326            Some(offsets) => (Some(offsets.slice(offset, length)), self.fields.clone()),
327            // Otherwise need to slice sparse children
328            None => {
329                let fields = self
330                    .fields
331                    .iter()
332                    .map(|x| x.as_ref().map(|x| x.slice(offset, length)))
333                    .collect();
334                (None, fields)
335            }
336        };
337
338        Self {
339            data_type: self.data_type.clone(),
340            type_ids: self.type_ids.slice(offset, length),
341            offsets,
342            fields,
343        }
344    }
345
346    /// Deconstruct this array into its constituent parts
347    ///
348    /// # Example
349    ///
350    /// ```
351    /// # use arrow_array::array::UnionArray;
352    /// # use arrow_array::types::Int32Type;
353    /// # use arrow_array::builder::UnionBuilder;
354    /// # use arrow_buffer::ScalarBuffer;
355    /// # fn main() -> Result<(), arrow_schema::ArrowError> {
356    /// let mut builder = UnionBuilder::new_dense();
357    /// builder.append::<Int32Type>("a", 1).unwrap();
358    /// let union_array = builder.build()?;
359    ///
360    /// // Deconstruct into parts
361    /// let (union_fields, type_ids, offsets, children) = union_array.into_parts();
362    ///
363    /// // Reconstruct from parts
364    /// let union_array = UnionArray::try_new(
365    ///     union_fields,
366    ///     type_ids,
367    ///     offsets,
368    ///     children,
369    /// );
370    /// # Ok(())
371    /// # }
372    /// ```
373    pub fn into_parts(
374        self,
375    ) -> (
376        UnionFields,
377        ScalarBuffer<i8>,
378        Option<ScalarBuffer<i32>>,
379        Vec<ArrayRef>,
380    ) {
381        let Self {
382            data_type,
383            type_ids,
384            offsets,
385            mut fields,
386        } = self;
387        match data_type {
388            DataType::Union(union_fields, _) => {
389                let children = union_fields
390                    .iter()
391                    .map(|(type_id, _)| fields[type_id as usize].take().unwrap())
392                    .collect();
393                (union_fields, type_ids, offsets, children)
394            }
395            _ => unreachable!(),
396        }
397    }
398
399    /// Computes the logical nulls for a sparse union, optimized for when there's a lot of fields without nulls
400    fn mask_sparse_skip_without_nulls(&self, nulls: Vec<(i8, NullBuffer)>) -> BooleanBuffer {
401        // Example logic for a union with 5 fields, a, b & c with nulls, d & e without nulls:
402        // let [a_nulls, b_nulls, c_nulls] = nulls;
403        // let [is_a, is_b, is_c] = masks;
404        // let is_d_or_e = !(is_a | is_b | is_c)
405        // let union_chunk_nulls = is_d_or_e  | (is_a & a_nulls) | (is_b & b_nulls) | (is_c & c_nulls)
406        let fold = |(with_nulls_selected, union_nulls), (is_field, field_nulls)| {
407            (
408                with_nulls_selected | is_field,
409                union_nulls | (is_field & field_nulls),
410            )
411        };
412
413        self.mask_sparse_helper(
414            nulls,
415            |type_ids_chunk_array, nulls_masks_iters| {
416                let (with_nulls_selected, union_nulls) = nulls_masks_iters
417                    .iter_mut()
418                    .map(|(field_type_id, field_nulls)| {
419                        let field_nulls = field_nulls.next().unwrap();
420                        let is_field = selection_mask(type_ids_chunk_array, *field_type_id);
421
422                        (is_field, field_nulls)
423                    })
424                    .fold((0, 0), fold);
425
426                // In the example above, this is the is_d_or_e = !(is_a | is_b) part
427                let without_nulls_selected = !with_nulls_selected;
428
429                // if a field without nulls is selected, the value is always true(set bit)
430                // otherwise, the true/set bits have been computed above
431                without_nulls_selected | union_nulls
432            },
433            |type_ids_remainder, bit_chunks| {
434                let (with_nulls_selected, union_nulls) = bit_chunks
435                    .iter()
436                    .map(|(field_type_id, field_bit_chunks)| {
437                        let field_nulls = field_bit_chunks.remainder_bits();
438                        let is_field = selection_mask(type_ids_remainder, *field_type_id);
439
440                        (is_field, field_nulls)
441                    })
442                    .fold((0, 0), fold);
443
444                let without_nulls_selected = !with_nulls_selected;
445
446                without_nulls_selected | union_nulls
447            },
448        )
449    }
450
451    /// Computes the logical nulls for a sparse union, optimized for when there's a lot of fields fully null
452    fn mask_sparse_skip_fully_null(&self, mut nulls: Vec<(i8, NullBuffer)>) -> BooleanBuffer {
453        let DataType::Union(fields, _) = self.data_type() else {
454            unreachable!("Union array's data type is not a union!")
455        };
456
457        let type_ids = fields.iter().map(|(id, _)| id).collect::<HashSet<_>>();
458        let with_nulls = nulls.iter().map(|(id, _)| *id).collect::<HashSet<_>>();
459
460        let without_nulls_ids = type_ids
461            .difference(&with_nulls)
462            .copied()
463            .collect::<Vec<_>>();
464
465        nulls.retain(|(_, nulls)| nulls.null_count() < nulls.len());
466
467        // Example logic for a union with 6 fields, a, b & c with nulls, d & e without nulls, and f fully_null:
468        // let [a_nulls, b_nulls, c_nulls] = nulls;
469        // let [is_a, is_b, is_c, is_d, is_e] = masks;
470        // let union_chunk_nulls = is_d | is_e | (is_a & a_nulls) | (is_b & b_nulls) | (is_c & c_nulls)
471        self.mask_sparse_helper(
472            nulls,
473            |type_ids_chunk_array, nulls_masks_iters| {
474                let union_nulls = nulls_masks_iters.iter_mut().fold(
475                    0,
476                    |union_nulls, (field_type_id, nulls_iter)| {
477                        let field_nulls = nulls_iter.next().unwrap();
478
479                        if field_nulls == 0 {
480                            union_nulls
481                        } else {
482                            let is_field = selection_mask(type_ids_chunk_array, *field_type_id);
483
484                            union_nulls | (is_field & field_nulls)
485                        }
486                    },
487                );
488
489                // Given the example above, this is the is_d_or_e = (is_d | is_e) part
490                let without_nulls_selected =
491                    without_nulls_selected(type_ids_chunk_array, &without_nulls_ids);
492
493                // if a field without nulls is selected, the value is always true(set bit)
494                // otherwise, the true/set bits have been computed above
495                union_nulls | without_nulls_selected
496            },
497            |type_ids_remainder, bit_chunks| {
498                let union_nulls =
499                    bit_chunks
500                        .iter()
501                        .fold(0, |union_nulls, (field_type_id, field_bit_chunks)| {
502                            let is_field = selection_mask(type_ids_remainder, *field_type_id);
503                            let field_nulls = field_bit_chunks.remainder_bits();
504
505                            union_nulls | is_field & field_nulls
506                        });
507
508                union_nulls | without_nulls_selected(type_ids_remainder, &without_nulls_ids)
509            },
510        )
511    }
512
513    /// Computes the logical nulls for a sparse union, optimized for when all fields contains nulls
514    fn mask_sparse_all_with_nulls_skip_one(&self, nulls: Vec<(i8, NullBuffer)>) -> BooleanBuffer {
515        // Example logic for a union with 3 fields, a, b & c, all containing nulls:
516        // let [a_nulls, b_nulls, c_nulls] = nulls;
517        // We can skip the first field: it's selection mask is the negation of all others selection mask
518        // let [is_b, is_c] = selection_masks;
519        // let is_a = !(is_b | is_c)
520        // let union_chunk_nulls = (is_a & a_nulls) | (is_b & b_nulls) | (is_c & c_nulls)
521        self.mask_sparse_helper(
522            nulls,
523            |type_ids_chunk_array, nulls_masks_iters| {
524                let (is_not_first, union_nulls) = nulls_masks_iters[1..] // skip first
525                    .iter_mut()
526                    .fold(
527                        (0, 0),
528                        |(is_not_first, union_nulls), (field_type_id, nulls_iter)| {
529                            let field_nulls = nulls_iter.next().unwrap();
530                            let is_field = selection_mask(type_ids_chunk_array, *field_type_id);
531
532                            (
533                                is_not_first | is_field,
534                                union_nulls | (is_field & field_nulls),
535                            )
536                        },
537                    );
538
539                let is_first = !is_not_first;
540                let first_nulls = nulls_masks_iters[0].1.next().unwrap();
541
542                (is_first & first_nulls) | union_nulls
543            },
544            |type_ids_remainder, bit_chunks| {
545                bit_chunks
546                    .iter()
547                    .fold(0, |union_nulls, (field_type_id, field_bit_chunks)| {
548                        let field_nulls = field_bit_chunks.remainder_bits();
549                        // The same logic as above, except that since this runs at most once,
550                        // it doesn't make difference to speed-up the first selection mask
551                        let is_field = selection_mask(type_ids_remainder, *field_type_id);
552
553                        union_nulls | (is_field & field_nulls)
554                    })
555            },
556        )
557    }
558
559    /// Maps `nulls` to `BitChunk's` and then to `BitChunkIterator's`, then divides `self.type_ids` into exact chunks of 64 values,
560    /// calling `mask_chunk` for every exact chunk, and `mask_remainder` for the remainder, if any, collecting the result in a `BooleanBuffer`
561    fn mask_sparse_helper(
562        &self,
563        nulls: Vec<(i8, NullBuffer)>,
564        mut mask_chunk: impl FnMut(&[i8; 64], &mut [(i8, BitChunkIterator)]) -> u64,
565        mask_remainder: impl FnOnce(&[i8], &[(i8, BitChunks)]) -> u64,
566    ) -> BooleanBuffer {
567        let bit_chunks = nulls
568            .iter()
569            .map(|(type_id, nulls)| (*type_id, nulls.inner().bit_chunks()))
570            .collect::<Vec<_>>();
571
572        let mut nulls_masks_iter = bit_chunks
573            .iter()
574            .map(|(type_id, bit_chunks)| (*type_id, bit_chunks.iter()))
575            .collect::<Vec<_>>();
576
577        let (chunks_exact, remainder) = self.type_ids.as_chunks::<64>();
578
579        let chunks = chunks_exact
580            .iter()
581            .map(|type_ids_chunk| mask_chunk(type_ids_chunk, &mut nulls_masks_iter));
582
583        // SAFETY:
584        // chunks is a ChunksExact iterator, which implements TrustedLen, and correctly reports its length
585        let mut buffer = unsafe { MutableBuffer::from_trusted_len_iter(chunks) };
586
587        if !remainder.is_empty() {
588            buffer.push(mask_remainder(remainder, &bit_chunks));
589        }
590
591        BooleanBuffer::new(buffer.into(), 0, self.type_ids.len())
592    }
593
594    /// Computes the logical nulls for a sparse or dense union, by gathering individual bits from the null buffer of the selected field
595    fn gather_nulls(&self, nulls: Vec<(i8, NullBuffer)>) -> BooleanBuffer {
596        let one_null = NullBuffer::new_null(1);
597        let one_valid = NullBuffer::new_valid(1);
598
599        // Unsafe code below depend on it:
600        // To remove one branch from the loop, if the a type_id is not utilized, or it's logical_nulls is None/all set,
601        // we use a null buffer of len 1 and a index_mask of 0, or the true null buffer and usize::MAX otherwise.
602        // We then unconditionally access the null buffer with index & index_mask,
603        // which always return 0 for the 1-len buffer, or the true index unchanged otherwise
604        // We also use a 256 array, so llvm knows that `type_id as u8 as usize` is always in bounds
605        let mut logical_nulls_array = [(&one_valid, Mask::Zero); 256];
606
607        for (type_id, nulls) in &nulls {
608            if nulls.null_count() == nulls.len() {
609                // Similarly, if all values are null, use a 1-null null-buffer to reduce cache pressure a bit
610                logical_nulls_array[*type_id as u8 as usize] = (&one_null, Mask::Zero);
611            } else {
612                logical_nulls_array[*type_id as u8 as usize] = (nulls, Mask::Max);
613            }
614        }
615
616        match &self.offsets {
617            Some(offsets) => {
618                assert_eq!(self.type_ids.len(), offsets.len());
619
620                BooleanBuffer::collect_bool(self.type_ids.len(), |i| unsafe {
621                    // SAFETY: BooleanBuffer::collect_bool calls us 0..self.type_ids.len()
622                    let type_id = *self.type_ids.get_unchecked(i);
623                    // SAFETY: We asserted that offsets len and self.type_ids len are equal
624                    let offset = *offsets.get_unchecked(i);
625
626                    let (nulls, offset_mask) = &logical_nulls_array[type_id as u8 as usize];
627
628                    // SAFETY:
629                    // If offset_mask is Max
630                    // 1. Offset validity is checked at union creation
631                    // 2. If the null buffer len equals it's array len is checked at array creation
632                    // If offset_mask is Zero, the null buffer len is 1
633                    nulls
634                        .inner()
635                        .value_unchecked(offset as usize & *offset_mask as usize)
636                })
637            }
638            None => {
639                BooleanBuffer::collect_bool(self.type_ids.len(), |index| unsafe {
640                    // SAFETY: BooleanBuffer::collect_bool calls us 0..self.type_ids.len()
641                    let type_id = *self.type_ids.get_unchecked(index);
642
643                    let (nulls, index_mask) = &logical_nulls_array[type_id as u8 as usize];
644
645                    // SAFETY:
646                    // If index_mask is Max
647                    // 1. On sparse union, every child len match it's parent, this is checked at union creation
648                    // 2. If the null buffer len equals it's array len is checked at array creation
649                    // If index_mask is Zero, the null buffer len is 1
650                    nulls.inner().value_unchecked(index & *index_mask as usize)
651                })
652            }
653        }
654    }
655
656    /// Returns a vector of tuples containing each field's type_id and its logical null buffer.
657    /// Only fields with non-zero null counts are included.
658    fn fields_logical_nulls(&self) -> Vec<(i8, NullBuffer)> {
659        self.fields
660            .iter()
661            .enumerate()
662            .filter_map(|(type_id, field)| Some((type_id as i8, field.as_ref()?.logical_nulls()?)))
663            .filter(|(_, nulls)| nulls.null_count() > 0)
664            .collect()
665    }
666}
667
668impl From<ArrayData> for UnionArray {
669    fn from(data: ArrayData) -> Self {
670        let (data_type, len, _nulls, offset, buffers, child_data) = data.into_parts();
671
672        let (fields, mode) = match &data_type {
673            DataType::Union(fields, mode) => (fields, mode),
674            d => panic!("UnionArray expected ArrayData with type Union got {d}"),
675        };
676
677        let (type_ids, offsets) = match mode {
678            UnionMode::Sparse => {
679                let [buffer]: [Buffer; 1] = buffers.try_into().expect("1 buffer for type_ids");
680                (ScalarBuffer::new(buffer, offset, len), None)
681            }
682            UnionMode::Dense => {
683                let [type_ids_buffer, offsets_buffer]: [Buffer; 2] = buffers
684                    .try_into()
685                    .expect("2 buffers for type_ids and offsets");
686                (
687                    ScalarBuffer::new(type_ids_buffer, offset, len),
688                    Some(ScalarBuffer::new(offsets_buffer, offset, len)),
689                )
690            }
691        };
692
693        let max_id = fields.iter().map(|(i, _)| i).max().unwrap_or_default() as usize;
694        let mut boxed_fields = vec![None; max_id + 1];
695        for (cd, (field_id, _)) in child_data.into_iter().zip(fields.iter()) {
696            let cd = match mode {
697                UnionMode::Sparse => cd.sliced(offset, len),
698                UnionMode::Dense => cd,
699            };
700            boxed_fields[field_id as usize] = Some(make_array(cd));
701        }
702        Self {
703            data_type,
704            type_ids,
705            offsets,
706            fields: boxed_fields,
707        }
708    }
709}
710
711impl From<UnionArray> for ArrayData {
712    fn from(array: UnionArray) -> Self {
713        let len = array.len();
714        let DataType::Union(f, _) = &array.data_type else {
715            unreachable!()
716        };
717        let buffers = match array.offsets {
718            Some(o) => vec![array.type_ids.into_inner(), o.into_inner()],
719            None => vec![array.type_ids.into_inner()],
720        };
721
722        let child = f
723            .iter()
724            .map(|(i, _)| array.fields[i as usize].as_ref().unwrap().to_data())
725            .collect();
726
727        let builder = ArrayDataBuilder::new(array.data_type)
728            .len(len)
729            .buffers(buffers)
730            .child_data(child);
731        unsafe { builder.build_unchecked() }
732    }
733}
734
735/// SAFETY: Correctly implements the contract of Arrow Arrays
736unsafe impl Array for UnionArray {
737    fn as_any(&self) -> &dyn Any {
738        self
739    }
740
741    fn to_data(&self) -> ArrayData {
742        self.clone().into()
743    }
744
745    fn into_data(self) -> ArrayData {
746        self.into()
747    }
748
749    fn data_type(&self) -> &DataType {
750        &self.data_type
751    }
752
753    fn slice(&self, offset: usize, length: usize) -> ArrayRef {
754        Arc::new(self.slice(offset, length))
755    }
756
757    fn len(&self) -> usize {
758        self.type_ids.len()
759    }
760
761    fn is_empty(&self) -> bool {
762        self.type_ids.is_empty()
763    }
764
765    fn shrink_to_fit(&mut self) {
766        self.type_ids.shrink_to_fit();
767        if let Some(offsets) = &mut self.offsets {
768            offsets.shrink_to_fit();
769        }
770        for array in self.fields.iter_mut().flatten() {
771            array.shrink_to_fit();
772        }
773        self.fields.shrink_to_fit();
774    }
775
776    fn offset(&self) -> usize {
777        0
778    }
779
780    fn nulls(&self) -> Option<&NullBuffer> {
781        None
782    }
783
784    fn logical_nulls(&self) -> Option<NullBuffer> {
785        let DataType::Union(fields, _) = self.data_type() else {
786            unreachable!()
787        };
788
789        if fields.len() <= 1 {
790            return self
791                .fields
792                .iter()
793                .enumerate()
794                .find_map(|(type_id, field_opt)| {
795                    field_opt
796                        .as_ref()
797                        .and_then(|field| field.logical_nulls())
798                        .map(|logical_nulls| {
799                            if self.is_dense() {
800                                self.gather_nulls(vec![(type_id as i8, logical_nulls)])
801                                    .into()
802                            } else {
803                                logical_nulls
804                            }
805                        })
806                });
807        }
808
809        let logical_nulls = self.fields_logical_nulls();
810
811        if logical_nulls.is_empty() {
812            return None;
813        }
814
815        let fully_null_count = logical_nulls
816            .iter()
817            .filter(|(_, nulls)| nulls.null_count() == nulls.len())
818            .count();
819
820        if fully_null_count == fields.len() {
821            if let Some((_, exactly_sized)) = logical_nulls
822                .iter()
823                .find(|(_, nulls)| nulls.len() == self.len())
824            {
825                return Some(exactly_sized.clone());
826            }
827
828            if let Some((_, bigger)) = logical_nulls
829                .iter()
830                .find(|(_, nulls)| nulls.len() > self.len())
831            {
832                return Some(bigger.slice(0, self.len()));
833            }
834
835            return Some(NullBuffer::new_null(self.len()));
836        }
837
838        let boolean_buffer = match &self.offsets {
839            Some(_) => self.gather_nulls(logical_nulls),
840            None => {
841                // Choose the fastest way to compute the logical nulls
842                // Gather computes one null per iteration, while the others work on 64 nulls chunks,
843                // but must also compute selection masks, which is expensive,
844                // so it's cost is the number of selection masks computed per chunk
845                // Since computing the selection mask gets auto-vectorized, it's performance depends on which simd feature is enabled
846                // For gather, the cost is the threshold where masking becomes slower than gather, which is determined with benchmarks
847                // TODO: bench on avx512f(feature is still unstable)
848                let gather_relative_cost = if cfg!(target_feature = "avx2") {
849                    10
850                } else if cfg!(target_feature = "sse4.1") {
851                    3
852                } else if cfg!(target_arch = "x86") || cfg!(target_arch = "x86_64") {
853                    // x86 baseline includes sse2
854                    2
855                } else {
856                    // TODO: bench on non x86
857                    // Always use gather on non benchmarked archs because even though it may slower on some cases,
858                    // it's performance depends only on the union length, without being affected by the number of fields
859                    0
860                };
861
862                let strategies = [
863                    (SparseStrategy::Gather, gather_relative_cost, true),
864                    (
865                        SparseStrategy::MaskAllFieldsWithNullsSkipOne,
866                        fields.len() - 1,
867                        fields.len() == logical_nulls.len(),
868                    ),
869                    (
870                        SparseStrategy::MaskSkipWithoutNulls,
871                        logical_nulls.len(),
872                        true,
873                    ),
874                    (
875                        SparseStrategy::MaskSkipFullyNull,
876                        fields.len() - fully_null_count,
877                        true,
878                    ),
879                ];
880
881                let (strategy, _, _) = strategies
882                    .iter()
883                    .filter(|(_, _, applicable)| *applicable)
884                    .min_by_key(|(_, cost, _)| cost)
885                    .unwrap();
886
887                match strategy {
888                    SparseStrategy::Gather => self.gather_nulls(logical_nulls),
889                    SparseStrategy::MaskAllFieldsWithNullsSkipOne => {
890                        self.mask_sparse_all_with_nulls_skip_one(logical_nulls)
891                    }
892                    SparseStrategy::MaskSkipWithoutNulls => {
893                        self.mask_sparse_skip_without_nulls(logical_nulls)
894                    }
895                    SparseStrategy::MaskSkipFullyNull => {
896                        self.mask_sparse_skip_fully_null(logical_nulls)
897                    }
898                }
899            }
900        };
901
902        let null_buffer = NullBuffer::from(boolean_buffer);
903
904        if null_buffer.null_count() > 0 {
905            Some(null_buffer)
906        } else {
907            None
908        }
909    }
910
911    fn is_nullable(&self) -> bool {
912        self.fields
913            .iter()
914            .flatten()
915            .any(|field| field.is_nullable())
916    }
917
918    fn get_buffer_memory_size(&self) -> usize {
919        let mut sum = self.type_ids.inner().capacity();
920        if let Some(o) = self.offsets.as_ref() {
921            sum += o.inner().capacity()
922        }
923        self.fields
924            .iter()
925            .filter_map(|x| x.as_ref().map(|x| x.get_buffer_memory_size()))
926            .sum::<usize>()
927            + sum
928    }
929
930    fn get_array_memory_size(&self) -> usize {
931        let mut sum = self.type_ids.inner().capacity();
932        if let Some(o) = self.offsets.as_ref() {
933            sum += o.inner().capacity()
934        }
935        std::mem::size_of::<Self>()
936            + self
937                .fields
938                .iter()
939                .filter_map(|x| x.as_ref().map(|x| x.get_array_memory_size()))
940                .sum::<usize>()
941            + sum
942    }
943
944    #[cfg(feature = "pool")]
945    fn claim(&self, pool: &dyn arrow_buffer::MemoryPool) {
946        self.type_ids.claim(pool);
947        if let Some(offsets) = &self.offsets {
948            offsets.claim(pool);
949        }
950        for field in self.fields.iter().flatten() {
951            field.claim(pool);
952        }
953    }
954}
955
956impl std::fmt::Debug for UnionArray {
957    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
958        let header = if self.is_dense() {
959            "UnionArray(Dense)\n["
960        } else {
961            "UnionArray(Sparse)\n["
962        };
963        writeln!(f, "{header}")?;
964
965        writeln!(f, "-- type id buffer:")?;
966        writeln!(f, "{:?}", self.type_ids)?;
967
968        if let Some(offsets) = &self.offsets {
969            writeln!(f, "-- offsets buffer:")?;
970            writeln!(f, "{offsets:?}")?;
971        }
972
973        let DataType::Union(fields, _) = self.data_type() else {
974            unreachable!()
975        };
976
977        for (type_id, field) in fields.iter() {
978            let child = self.child(type_id);
979            writeln!(
980                f,
981                "-- child {}: \"{}\" ({:?})",
982                type_id,
983                field.name(),
984                field.data_type()
985            )?;
986            std::fmt::Debug::fmt(child, f)?;
987            writeln!(f)?;
988        }
989        writeln!(f, "]")
990    }
991}
992
993/// How to compute the logical nulls of a sparse union. All strategies return the same result.
994/// Those starting with Mask perform bitwise masking for each chunk of 64 values, including
995/// computing expensive selection masks of fields: which fields masks must be computed is the
996/// difference between them
997enum SparseStrategy {
998    /// Gather individual bits from the null buffer of the selected field
999    Gather,
1000    /// All fields contains nulls, so we can skip the selection mask computation of one field by negating the others
1001    MaskAllFieldsWithNullsSkipOne,
1002    /// Skip the selection mask computation of the fields without nulls
1003    MaskSkipWithoutNulls,
1004    /// Skip the selection mask computation of the fully nulls fields
1005    MaskSkipFullyNull,
1006}
1007
1008#[derive(Copy, Clone)]
1009#[repr(usize)]
1010enum Mask {
1011    Zero = 0,
1012    Max = usize::MAX,
1013}
1014
1015fn selection_mask(type_ids_chunk: &[i8], type_id: i8) -> u64 {
1016    type_ids_chunk
1017        .iter()
1018        .copied()
1019        .enumerate()
1020        .fold(0, |packed, (bit_idx, v)| {
1021            packed | (((v == type_id) as u64) << bit_idx)
1022        })
1023}
1024
1025/// Returns a bitmask where bits indicate if any id from `without_nulls_ids` exist in `type_ids_chunk`.
1026fn without_nulls_selected(type_ids_chunk: &[i8], without_nulls_ids: &[i8]) -> u64 {
1027    without_nulls_ids
1028        .iter()
1029        .fold(0, |fully_valid_selected, field_type_id| {
1030            fully_valid_selected | selection_mask(type_ids_chunk, *field_type_id)
1031        })
1032}
1033
1034#[cfg(test)]
1035mod tests {
1036    use super::*;
1037    use std::collections::HashSet;
1038
1039    use crate::array::Int8Type;
1040    use crate::builder::UnionBuilder;
1041    use crate::cast::AsArray;
1042    use crate::types::{Float32Type, Float64Type, Int32Type, Int64Type};
1043    use crate::{Float64Array, Int32Array, Int64Array, NullArray, StringArray};
1044    use crate::{Int8Array, RecordBatch};
1045    use arrow_buffer::Buffer;
1046    use arrow_schema::{Field, Schema};
1047
1048    #[test]
1049    fn test_dense_i32() {
1050        let mut builder = UnionBuilder::new_dense();
1051        builder.append::<Int32Type>("a", 1).unwrap();
1052        builder.append::<Int32Type>("b", 2).unwrap();
1053        builder.append::<Int32Type>("c", 3).unwrap();
1054        builder.append::<Int32Type>("a", 4).unwrap();
1055        builder.append::<Int32Type>("c", 5).unwrap();
1056        builder.append::<Int32Type>("a", 6).unwrap();
1057        builder.append::<Int32Type>("b", 7).unwrap();
1058        let union = builder.build().unwrap();
1059
1060        let expected_type_ids = vec![0_i8, 1, 2, 0, 2, 0, 1];
1061        let expected_offsets = vec![0_i32, 0, 0, 1, 1, 2, 1];
1062        let expected_array_values = [1_i32, 2, 3, 4, 5, 6, 7];
1063
1064        // Check type ids
1065        assert_eq!(*union.type_ids(), expected_type_ids);
1066        for (i, id) in expected_type_ids.iter().enumerate() {
1067            assert_eq!(id, &union.type_id(i));
1068        }
1069
1070        // Check offsets
1071        assert_eq!(*union.offsets().unwrap(), expected_offsets);
1072        for (i, id) in expected_offsets.iter().enumerate() {
1073            assert_eq!(union.value_offset(i), *id as usize);
1074        }
1075
1076        // Check data
1077        assert_eq!(
1078            *union.child(0).as_primitive::<Int32Type>().values(),
1079            [1_i32, 4, 6]
1080        );
1081        assert_eq!(
1082            *union.child(1).as_primitive::<Int32Type>().values(),
1083            [2_i32, 7]
1084        );
1085        assert_eq!(
1086            *union.child(2).as_primitive::<Int32Type>().values(),
1087            [3_i32, 5]
1088        );
1089
1090        assert_eq!(expected_array_values.len(), union.len());
1091        for (i, expected_value) in expected_array_values.iter().enumerate() {
1092            assert!(!union.is_null(i));
1093            let slot = union.value(i);
1094            let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1095            assert_eq!(slot.len(), 1);
1096            let value = slot.value(0);
1097            assert_eq!(expected_value, &value);
1098        }
1099    }
1100
1101    #[test]
1102    fn slice_union_array_single_field() {
1103        // Dense Union
1104        // [1, null, 3, null, 4]
1105        let union_array = {
1106            let mut builder = UnionBuilder::new_dense();
1107            builder.append::<Int32Type>("a", 1).unwrap();
1108            builder.append_null::<Int32Type>("a").unwrap();
1109            builder.append::<Int32Type>("a", 3).unwrap();
1110            builder.append_null::<Int32Type>("a").unwrap();
1111            builder.append::<Int32Type>("a", 4).unwrap();
1112            builder.build().unwrap()
1113        };
1114
1115        // [null, 3, null]
1116        let union_slice = union_array.slice(1, 3);
1117        let logical_nulls = union_slice.logical_nulls().unwrap();
1118
1119        assert_eq!(logical_nulls.len(), 3);
1120        assert!(logical_nulls.is_null(0));
1121        assert!(logical_nulls.is_valid(1));
1122        assert!(logical_nulls.is_null(2));
1123    }
1124
1125    #[test]
1126    fn test_dense_i32_large() {
1127        let mut builder = UnionBuilder::new_dense();
1128
1129        let expected_type_ids = vec![0_i8; 1024];
1130        let expected_offsets: Vec<_> = (0..1024).collect();
1131        let expected_array_values: Vec<_> = (1..=1024).collect();
1132
1133        expected_array_values
1134            .iter()
1135            .for_each(|v| builder.append::<Int32Type>("a", *v).unwrap());
1136
1137        let union = builder.build().unwrap();
1138
1139        // Check type ids
1140        assert_eq!(*union.type_ids(), expected_type_ids);
1141        for (i, id) in expected_type_ids.iter().enumerate() {
1142            assert_eq!(id, &union.type_id(i));
1143        }
1144
1145        // Check offsets
1146        assert_eq!(*union.offsets().unwrap(), expected_offsets);
1147        for (i, id) in expected_offsets.iter().enumerate() {
1148            assert_eq!(union.value_offset(i), *id as usize);
1149        }
1150
1151        for (i, expected_value) in expected_array_values.iter().enumerate() {
1152            assert!(!union.is_null(i));
1153            let slot = union.value(i);
1154            let slot = slot.as_primitive::<Int32Type>();
1155            assert_eq!(slot.len(), 1);
1156            let value = slot.value(0);
1157            assert_eq!(expected_value, &value);
1158        }
1159    }
1160
1161    #[test]
1162    fn test_dense_mixed() {
1163        let mut builder = UnionBuilder::new_dense();
1164        builder.append::<Int32Type>("a", 1).unwrap();
1165        builder.append::<Int64Type>("c", 3).unwrap();
1166        builder.append::<Int32Type>("a", 4).unwrap();
1167        builder.append::<Int64Type>("c", 5).unwrap();
1168        builder.append::<Int32Type>("a", 6).unwrap();
1169        let union = builder.build().unwrap();
1170
1171        assert_eq!(5, union.len());
1172        for i in 0..union.len() {
1173            let slot = union.value(i);
1174            assert!(!union.is_null(i));
1175            match i {
1176                0 => {
1177                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1178                    assert_eq!(slot.len(), 1);
1179                    let value = slot.value(0);
1180                    assert_eq!(1_i32, value);
1181                }
1182                1 => {
1183                    let slot = slot.as_any().downcast_ref::<Int64Array>().unwrap();
1184                    assert_eq!(slot.len(), 1);
1185                    let value = slot.value(0);
1186                    assert_eq!(3_i64, value);
1187                }
1188                2 => {
1189                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1190                    assert_eq!(slot.len(), 1);
1191                    let value = slot.value(0);
1192                    assert_eq!(4_i32, value);
1193                }
1194                3 => {
1195                    let slot = slot.as_any().downcast_ref::<Int64Array>().unwrap();
1196                    assert_eq!(slot.len(), 1);
1197                    let value = slot.value(0);
1198                    assert_eq!(5_i64, value);
1199                }
1200                4 => {
1201                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1202                    assert_eq!(slot.len(), 1);
1203                    let value = slot.value(0);
1204                    assert_eq!(6_i32, value);
1205                }
1206                _ => unreachable!(),
1207            }
1208        }
1209    }
1210
1211    #[test]
1212    fn test_dense_mixed_with_nulls() {
1213        let mut builder = UnionBuilder::new_dense();
1214        builder.append::<Int32Type>("a", 1).unwrap();
1215        builder.append::<Int64Type>("c", 3).unwrap();
1216        builder.append::<Int32Type>("a", 10).unwrap();
1217        builder.append_null::<Int32Type>("a").unwrap();
1218        builder.append::<Int32Type>("a", 6).unwrap();
1219        let union = builder.build().unwrap();
1220
1221        assert_eq!(5, union.len());
1222        for i in 0..union.len() {
1223            let slot = union.value(i);
1224            match i {
1225                0 => {
1226                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1227                    assert!(!slot.is_null(0));
1228                    assert_eq!(slot.len(), 1);
1229                    let value = slot.value(0);
1230                    assert_eq!(1_i32, value);
1231                }
1232                1 => {
1233                    let slot = slot.as_any().downcast_ref::<Int64Array>().unwrap();
1234                    assert!(!slot.is_null(0));
1235                    assert_eq!(slot.len(), 1);
1236                    let value = slot.value(0);
1237                    assert_eq!(3_i64, value);
1238                }
1239                2 => {
1240                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1241                    assert!(!slot.is_null(0));
1242                    assert_eq!(slot.len(), 1);
1243                    let value = slot.value(0);
1244                    assert_eq!(10_i32, value);
1245                }
1246                3 => assert!(slot.is_null(0)),
1247                4 => {
1248                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1249                    assert!(!slot.is_null(0));
1250                    assert_eq!(slot.len(), 1);
1251                    let value = slot.value(0);
1252                    assert_eq!(6_i32, value);
1253                }
1254                _ => unreachable!(),
1255            }
1256        }
1257    }
1258
1259    #[test]
1260    fn test_dense_mixed_with_nulls_and_offset() {
1261        let mut builder = UnionBuilder::new_dense();
1262        builder.append::<Int32Type>("a", 1).unwrap();
1263        builder.append::<Int64Type>("c", 3).unwrap();
1264        builder.append::<Int32Type>("a", 10).unwrap();
1265        builder.append_null::<Int32Type>("a").unwrap();
1266        builder.append::<Int32Type>("a", 6).unwrap();
1267        let union = builder.build().unwrap();
1268
1269        let slice = union.slice(2, 3);
1270        let new_union = slice.as_any().downcast_ref::<UnionArray>().unwrap();
1271
1272        assert_eq!(3, new_union.len());
1273        for i in 0..new_union.len() {
1274            let slot = new_union.value(i);
1275            match i {
1276                0 => {
1277                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1278                    assert!(!slot.is_null(0));
1279                    assert_eq!(slot.len(), 1);
1280                    let value = slot.value(0);
1281                    assert_eq!(10_i32, value);
1282                }
1283                1 => assert!(slot.is_null(0)),
1284                2 => {
1285                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1286                    assert!(!slot.is_null(0));
1287                    assert_eq!(slot.len(), 1);
1288                    let value = slot.value(0);
1289                    assert_eq!(6_i32, value);
1290                }
1291                _ => unreachable!(),
1292            }
1293        }
1294    }
1295
1296    #[test]
1297    fn test_dense_mixed_with_str() {
1298        let string_array = StringArray::from(vec!["foo", "bar", "baz"]);
1299        let int_array = Int32Array::from(vec![5, 6]);
1300        let float_array = Float64Array::from(vec![10.0]);
1301
1302        let type_ids = [1, 0, 0, 2, 0, 1].into_iter().collect::<ScalarBuffer<i8>>();
1303        let offsets = [0, 0, 1, 0, 2, 1]
1304            .into_iter()
1305            .collect::<ScalarBuffer<i32>>();
1306
1307        let fields = [
1308            (0, Arc::new(Field::new("A", DataType::Utf8, false))),
1309            (1, Arc::new(Field::new("B", DataType::Int32, false))),
1310            (2, Arc::new(Field::new("C", DataType::Float64, false))),
1311        ]
1312        .into_iter()
1313        .collect::<UnionFields>();
1314        let children = [
1315            Arc::new(string_array) as Arc<dyn Array>,
1316            Arc::new(int_array),
1317            Arc::new(float_array),
1318        ]
1319        .into_iter()
1320        .collect();
1321        let array =
1322            UnionArray::try_new(fields, type_ids.clone(), Some(offsets.clone()), children).unwrap();
1323
1324        // Check type ids
1325        assert_eq!(*array.type_ids(), type_ids);
1326        for (i, id) in type_ids.iter().enumerate() {
1327            assert_eq!(id, &array.type_id(i));
1328        }
1329
1330        // Check offsets
1331        assert_eq!(*array.offsets().unwrap(), offsets);
1332        for (i, id) in offsets.iter().enumerate() {
1333            assert_eq!(*id as usize, array.value_offset(i));
1334        }
1335
1336        // Check values
1337        assert_eq!(6, array.len());
1338
1339        let slot = array.value(0);
1340        let value = slot.as_any().downcast_ref::<Int32Array>().unwrap().value(0);
1341        assert_eq!(5, value);
1342
1343        let slot = array.value(1);
1344        let value = slot
1345            .as_any()
1346            .downcast_ref::<StringArray>()
1347            .unwrap()
1348            .value(0);
1349        assert_eq!("foo", value);
1350
1351        let slot = array.value(2);
1352        let value = slot
1353            .as_any()
1354            .downcast_ref::<StringArray>()
1355            .unwrap()
1356            .value(0);
1357        assert_eq!("bar", value);
1358
1359        let slot = array.value(3);
1360        let value = slot
1361            .as_any()
1362            .downcast_ref::<Float64Array>()
1363            .unwrap()
1364            .value(0);
1365        assert_eq!(10.0, value);
1366
1367        let slot = array.value(4);
1368        let value = slot
1369            .as_any()
1370            .downcast_ref::<StringArray>()
1371            .unwrap()
1372            .value(0);
1373        assert_eq!("baz", value);
1374
1375        let slot = array.value(5);
1376        let value = slot.as_any().downcast_ref::<Int32Array>().unwrap().value(0);
1377        assert_eq!(6, value);
1378    }
1379
1380    #[test]
1381    fn test_sparse_i32() {
1382        let mut builder = UnionBuilder::new_sparse();
1383        builder.append::<Int32Type>("a", 1).unwrap();
1384        builder.append::<Int32Type>("b", 2).unwrap();
1385        builder.append::<Int32Type>("c", 3).unwrap();
1386        builder.append::<Int32Type>("a", 4).unwrap();
1387        builder.append::<Int32Type>("c", 5).unwrap();
1388        builder.append::<Int32Type>("a", 6).unwrap();
1389        builder.append::<Int32Type>("b", 7).unwrap();
1390        let union = builder.build().unwrap();
1391
1392        let expected_type_ids = vec![0_i8, 1, 2, 0, 2, 0, 1];
1393        let expected_array_values = [1_i32, 2, 3, 4, 5, 6, 7];
1394
1395        // Check type ids
1396        assert_eq!(*union.type_ids(), expected_type_ids);
1397        for (i, id) in expected_type_ids.iter().enumerate() {
1398            assert_eq!(id, &union.type_id(i));
1399        }
1400
1401        // Check offsets, sparse union should only have a single buffer
1402        assert!(union.offsets().is_none());
1403
1404        // Check data
1405        assert_eq!(
1406            *union.child(0).as_primitive::<Int32Type>().values(),
1407            [1_i32, 0, 0, 4, 0, 6, 0],
1408        );
1409        assert_eq!(
1410            *union.child(1).as_primitive::<Int32Type>().values(),
1411            [0_i32, 2_i32, 0, 0, 0, 0, 7]
1412        );
1413        assert_eq!(
1414            *union.child(2).as_primitive::<Int32Type>().values(),
1415            [0_i32, 0, 3_i32, 0, 5, 0, 0]
1416        );
1417
1418        assert_eq!(expected_array_values.len(), union.len());
1419        for (i, expected_value) in expected_array_values.iter().enumerate() {
1420            assert!(!union.is_null(i));
1421            let slot = union.value(i);
1422            let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1423            assert_eq!(slot.len(), 1);
1424            let value = slot.value(0);
1425            assert_eq!(expected_value, &value);
1426        }
1427    }
1428
1429    #[test]
1430    fn test_sparse_mixed() {
1431        let mut builder = UnionBuilder::new_sparse();
1432        builder.append::<Int32Type>("a", 1).unwrap();
1433        builder.append::<Float64Type>("c", 3.0).unwrap();
1434        builder.append::<Int32Type>("a", 4).unwrap();
1435        builder.append::<Float64Type>("c", 5.0).unwrap();
1436        builder.append::<Int32Type>("a", 6).unwrap();
1437        let union = builder.build().unwrap();
1438
1439        let expected_type_ids = vec![0_i8, 1, 0, 1, 0];
1440
1441        // Check type ids
1442        assert_eq!(*union.type_ids(), expected_type_ids);
1443        for (i, id) in expected_type_ids.iter().enumerate() {
1444            assert_eq!(id, &union.type_id(i));
1445        }
1446
1447        // Check offsets, sparse union should only have a single buffer, i.e. no offsets
1448        assert!(union.offsets().is_none());
1449
1450        for i in 0..union.len() {
1451            let slot = union.value(i);
1452            assert!(!union.is_null(i));
1453            match i {
1454                0 => {
1455                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1456                    assert_eq!(slot.len(), 1);
1457                    let value = slot.value(0);
1458                    assert_eq!(1_i32, value);
1459                }
1460                1 => {
1461                    let slot = slot.as_any().downcast_ref::<Float64Array>().unwrap();
1462                    assert_eq!(slot.len(), 1);
1463                    let value = slot.value(0);
1464                    assert_eq!(value, 3_f64);
1465                }
1466                2 => {
1467                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1468                    assert_eq!(slot.len(), 1);
1469                    let value = slot.value(0);
1470                    assert_eq!(4_i32, value);
1471                }
1472                3 => {
1473                    let slot = slot.as_any().downcast_ref::<Float64Array>().unwrap();
1474                    assert_eq!(slot.len(), 1);
1475                    let value = slot.value(0);
1476                    assert_eq!(5_f64, value);
1477                }
1478                4 => {
1479                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1480                    assert_eq!(slot.len(), 1);
1481                    let value = slot.value(0);
1482                    assert_eq!(6_i32, value);
1483                }
1484                _ => unreachable!(),
1485            }
1486        }
1487    }
1488
1489    #[test]
1490    fn test_sparse_mixed_with_nulls() {
1491        let mut builder = UnionBuilder::new_sparse();
1492        builder.append::<Int32Type>("a", 1).unwrap();
1493        builder.append_null::<Int32Type>("a").unwrap();
1494        builder.append::<Float64Type>("c", 3.0).unwrap();
1495        builder.append::<Int32Type>("a", 4).unwrap();
1496        let union = builder.build().unwrap();
1497
1498        let expected_type_ids = vec![0_i8, 0, 1, 0];
1499
1500        // Check type ids
1501        assert_eq!(*union.type_ids(), expected_type_ids);
1502        for (i, id) in expected_type_ids.iter().enumerate() {
1503            assert_eq!(id, &union.type_id(i));
1504        }
1505
1506        // Check offsets, sparse union should only have a single buffer, i.e. no offsets
1507        assert!(union.offsets().is_none());
1508
1509        for i in 0..union.len() {
1510            let slot = union.value(i);
1511            match i {
1512                0 => {
1513                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1514                    assert!(!slot.is_null(0));
1515                    assert_eq!(slot.len(), 1);
1516                    let value = slot.value(0);
1517                    assert_eq!(1_i32, value);
1518                }
1519                1 => assert!(slot.is_null(0)),
1520                2 => {
1521                    let slot = slot.as_any().downcast_ref::<Float64Array>().unwrap();
1522                    assert!(!slot.is_null(0));
1523                    assert_eq!(slot.len(), 1);
1524                    let value = slot.value(0);
1525                    assert_eq!(value, 3_f64);
1526                }
1527                3 => {
1528                    let slot = slot.as_any().downcast_ref::<Int32Array>().unwrap();
1529                    assert!(!slot.is_null(0));
1530                    assert_eq!(slot.len(), 1);
1531                    let value = slot.value(0);
1532                    assert_eq!(4_i32, value);
1533                }
1534                _ => unreachable!(),
1535            }
1536        }
1537    }
1538
1539    #[test]
1540    fn test_sparse_mixed_with_nulls_and_offset() {
1541        let mut builder = UnionBuilder::new_sparse();
1542        builder.append::<Int32Type>("a", 1).unwrap();
1543        builder.append_null::<Int32Type>("a").unwrap();
1544        builder.append::<Float64Type>("c", 3.0).unwrap();
1545        builder.append_null::<Float64Type>("c").unwrap();
1546        builder.append::<Int32Type>("a", 4).unwrap();
1547        let union = builder.build().unwrap();
1548
1549        let slice = union.slice(1, 4);
1550        let new_union = slice.as_any().downcast_ref::<UnionArray>().unwrap();
1551
1552        assert_eq!(4, new_union.len());
1553        for i in 0..new_union.len() {
1554            let slot = new_union.value(i);
1555            match i {
1556                0 => assert!(slot.is_null(0)),
1557                1 => {
1558                    let slot = slot.as_primitive::<Float64Type>();
1559                    assert!(!slot.is_null(0));
1560                    assert_eq!(slot.len(), 1);
1561                    let value = slot.value(0);
1562                    assert_eq!(value, 3_f64);
1563                }
1564                2 => assert!(slot.is_null(0)),
1565                3 => {
1566                    let slot = slot.as_primitive::<Int32Type>();
1567                    assert!(!slot.is_null(0));
1568                    assert_eq!(slot.len(), 1);
1569                    let value = slot.value(0);
1570                    assert_eq!(4_i32, value);
1571                }
1572                _ => unreachable!(),
1573            }
1574        }
1575    }
1576
1577    fn test_union_validity(union_array: &UnionArray) {
1578        assert_eq!(union_array.null_count(), 0);
1579
1580        for i in 0..union_array.len() {
1581            assert!(!union_array.is_null(i));
1582            assert!(union_array.is_valid(i));
1583        }
1584    }
1585
1586    #[test]
1587    fn test_union_array_validity() {
1588        let mut builder = UnionBuilder::new_sparse();
1589        builder.append::<Int32Type>("a", 1).unwrap();
1590        builder.append_null::<Int32Type>("a").unwrap();
1591        builder.append::<Float64Type>("c", 3.0).unwrap();
1592        builder.append_null::<Float64Type>("c").unwrap();
1593        builder.append::<Int32Type>("a", 4).unwrap();
1594        let union = builder.build().unwrap();
1595
1596        test_union_validity(&union);
1597
1598        let mut builder = UnionBuilder::new_dense();
1599        builder.append::<Int32Type>("a", 1).unwrap();
1600        builder.append_null::<Int32Type>("a").unwrap();
1601        builder.append::<Float64Type>("c", 3.0).unwrap();
1602        builder.append_null::<Float64Type>("c").unwrap();
1603        builder.append::<Int32Type>("a", 4).unwrap();
1604        let union = builder.build().unwrap();
1605
1606        test_union_validity(&union);
1607    }
1608
1609    #[test]
1610    fn test_type_check() {
1611        let mut builder = UnionBuilder::new_sparse();
1612        builder.append::<Float32Type>("a", 1.0).unwrap();
1613        let err = builder.append::<Int32Type>("a", 1).unwrap_err().to_string();
1614        assert!(
1615            err.contains(
1616                "Attempt to write col \"a\" with type Int32 doesn't match existing type Float32"
1617            ),
1618            "{}",
1619            err
1620        );
1621    }
1622
1623    #[test]
1624    fn slice_union_array() {
1625        // [1, null, 3.0, null, 4]
1626        fn create_union(mut builder: UnionBuilder) -> UnionArray {
1627            builder.append::<Int32Type>("a", 1).unwrap();
1628            builder.append_null::<Int32Type>("a").unwrap();
1629            builder.append::<Float64Type>("c", 3.0).unwrap();
1630            builder.append_null::<Float64Type>("c").unwrap();
1631            builder.append::<Int32Type>("a", 4).unwrap();
1632            builder.build().unwrap()
1633        }
1634
1635        fn create_batch(union: UnionArray) -> RecordBatch {
1636            let schema = Schema::new(vec![Field::new(
1637                "struct_array",
1638                union.data_type().clone(),
1639                true,
1640            )]);
1641
1642            RecordBatch::try_new(Arc::new(schema), vec![Arc::new(union)]).unwrap()
1643        }
1644
1645        fn test_slice_union(record_batch_slice: RecordBatch) {
1646            let union_slice = record_batch_slice
1647                .column(0)
1648                .as_any()
1649                .downcast_ref::<UnionArray>()
1650                .unwrap();
1651
1652            assert_eq!(union_slice.type_id(0), 0);
1653            assert_eq!(union_slice.type_id(1), 1);
1654            assert_eq!(union_slice.type_id(2), 1);
1655
1656            let slot = union_slice.value(0);
1657            let array = slot.as_primitive::<Int32Type>();
1658            assert_eq!(array.len(), 1);
1659            assert!(array.is_null(0));
1660
1661            let slot = union_slice.value(1);
1662            let array = slot.as_primitive::<Float64Type>();
1663            assert_eq!(array.len(), 1);
1664            assert!(array.is_valid(0));
1665            assert_eq!(array.value(0), 3.0);
1666
1667            let slot = union_slice.value(2);
1668            let array = slot.as_primitive::<Float64Type>();
1669            assert_eq!(array.len(), 1);
1670            assert!(array.is_null(0));
1671        }
1672
1673        // Sparse Union
1674        let builder = UnionBuilder::new_sparse();
1675        let record_batch = create_batch(create_union(builder));
1676        // [null, 3.0, null]
1677        let record_batch_slice = record_batch.slice(1, 3);
1678        test_slice_union(record_batch_slice);
1679
1680        // Dense Union
1681        let builder = UnionBuilder::new_dense();
1682        let record_batch = create_batch(create_union(builder));
1683        // [null, 3.0, null]
1684        let record_batch_slice = record_batch.slice(1, 3);
1685        test_slice_union(record_batch_slice);
1686    }
1687
1688    #[test]
1689    fn test_union_from_sliced_array_data() {
1690        for mode in [UnionMode::Sparse, UnionMode::Dense] {
1691            let fields = UnionFields::try_new(
1692                [3, 7],
1693                [
1694                    Field::new("ints", DataType::Int32, false),
1695                    Field::new("floats", DataType::Float64, false),
1696                ],
1697            )
1698            .unwrap();
1699            let offsets = (mode == UnionMode::Dense).then(|| vec![0, 1, 2, 3].into());
1700            let array = UnionArray::try_new(
1701                fields,
1702                vec![3, 7, 3, 7].into(),
1703                offsets,
1704                vec![
1705                    Arc::new(Int32Array::from(vec![10, 20, 30, 40])),
1706                    Arc::new(Float64Array::from(vec![1.0, 2.0, 3.0, 4.0])),
1707                ],
1708            )
1709            .unwrap();
1710            for (offset, len) in [(1, 2), (0, 2), (4, 0), (0, 4)] {
1711                let expected = array.slice(offset, len);
1712                let actual = make_array(array.to_data().slice(offset, len));
1713                let actual = actual.as_any().downcast_ref::<UnionArray>().unwrap();
1714                for i in 0..len {
1715                    assert_eq!(actual.value(i).to_data(), expected.value(i).to_data());
1716                }
1717                assert_eq!(actual.to_data(), expected.to_data());
1718            }
1719        }
1720    }
1721
1722    #[test]
1723    fn test_sparse_union_from_sliced_array_data_logical_nulls() {
1724        let child = Int32Array::from(vec![Some(10), None, Some(30)]);
1725        let fields =
1726            UnionFields::try_new([0], [Field::new("ints", DataType::Int32, true)]).unwrap();
1727        let array =
1728            UnionArray::try_new(fields, vec![0, 0, 0].into(), None, vec![Arc::new(child)]).unwrap();
1729        for (offset, len) in [(0, 1), (1, 1), (2, 1), (3, 0)] {
1730            let expected = array.slice(offset, len);
1731            let actual = make_array(array.to_data().slice(offset, len));
1732            assert_eq!(actual.logical_nulls(), expected.logical_nulls());
1733            assert_eq!(actual.to_data(), expected.to_data());
1734        }
1735    }
1736
1737    #[test]
1738    fn test_custom_type_ids() {
1739        let data_type = DataType::Union(
1740            UnionFields::try_new(
1741                vec![8, 4, 9],
1742                vec![
1743                    Field::new("strings", DataType::Utf8, false),
1744                    Field::new("integers", DataType::Int32, false),
1745                    Field::new("floats", DataType::Float64, false),
1746                ],
1747            )
1748            .unwrap(),
1749            UnionMode::Dense,
1750        );
1751
1752        let string_array = StringArray::from(vec!["foo", "bar", "baz"]);
1753        let int_array = Int32Array::from(vec![5, 6, 4]);
1754        let float_array = Float64Array::from(vec![10.0]);
1755
1756        let type_ids = Buffer::from_vec(vec![4_i8, 8, 4, 8, 9, 4, 8]);
1757        let value_offsets = Buffer::from_vec(vec![0_i32, 0, 1, 1, 0, 2, 2]);
1758
1759        let data = ArrayData::builder(data_type)
1760            .len(7)
1761            .buffers(vec![type_ids, value_offsets])
1762            .child_data(vec![
1763                string_array.into_data(),
1764                int_array.into_data(),
1765                float_array.into_data(),
1766            ])
1767            .build()
1768            .unwrap();
1769
1770        let array = UnionArray::from(data);
1771
1772        let v = array.value(0);
1773        assert_eq!(v.data_type(), &DataType::Int32);
1774        assert_eq!(v.len(), 1);
1775        assert_eq!(v.as_primitive::<Int32Type>().value(0), 5);
1776
1777        let v = array.value(1);
1778        assert_eq!(v.data_type(), &DataType::Utf8);
1779        assert_eq!(v.len(), 1);
1780        assert_eq!(v.as_string::<i32>().value(0), "foo");
1781
1782        let v = array.value(2);
1783        assert_eq!(v.data_type(), &DataType::Int32);
1784        assert_eq!(v.len(), 1);
1785        assert_eq!(v.as_primitive::<Int32Type>().value(0), 6);
1786
1787        let v = array.value(3);
1788        assert_eq!(v.data_type(), &DataType::Utf8);
1789        assert_eq!(v.len(), 1);
1790        assert_eq!(v.as_string::<i32>().value(0), "bar");
1791
1792        let v = array.value(4);
1793        assert_eq!(v.data_type(), &DataType::Float64);
1794        assert_eq!(v.len(), 1);
1795        assert_eq!(v.as_primitive::<Float64Type>().value(0), 10.0);
1796
1797        let v = array.value(5);
1798        assert_eq!(v.data_type(), &DataType::Int32);
1799        assert_eq!(v.len(), 1);
1800        assert_eq!(v.as_primitive::<Int32Type>().value(0), 4);
1801
1802        let v = array.value(6);
1803        assert_eq!(v.data_type(), &DataType::Utf8);
1804        assert_eq!(v.len(), 1);
1805        assert_eq!(v.as_string::<i32>().value(0), "baz");
1806    }
1807
1808    #[test]
1809    fn into_parts() {
1810        let mut builder = UnionBuilder::new_dense();
1811        builder.append::<Int32Type>("a", 1).unwrap();
1812        builder.append::<Int8Type>("b", 2).unwrap();
1813        builder.append::<Int32Type>("a", 3).unwrap();
1814        let dense_union = builder.build().unwrap();
1815
1816        let field = [
1817            &Arc::new(Field::new("a", DataType::Int32, false)),
1818            &Arc::new(Field::new("b", DataType::Int8, false)),
1819        ];
1820        let (union_fields, type_ids, offsets, children) = dense_union.into_parts();
1821        assert_eq!(
1822            union_fields
1823                .iter()
1824                .map(|(_, field)| field)
1825                .collect::<Vec<_>>(),
1826            field
1827        );
1828        assert_eq!(type_ids, [0, 1, 0]);
1829        assert!(offsets.is_some());
1830        assert_eq!(offsets.as_ref().unwrap(), &[0, 0, 1]);
1831
1832        let result = UnionArray::try_new(union_fields, type_ids, offsets, children);
1833        assert!(result.is_ok());
1834        assert_eq!(result.unwrap().len(), 3);
1835
1836        let mut builder = UnionBuilder::new_sparse();
1837        builder.append::<Int32Type>("a", 1).unwrap();
1838        builder.append::<Int8Type>("b", 2).unwrap();
1839        builder.append::<Int32Type>("a", 3).unwrap();
1840        let sparse_union = builder.build().unwrap();
1841
1842        let (union_fields, type_ids, offsets, children) = sparse_union.into_parts();
1843        assert_eq!(type_ids, [0, 1, 0]);
1844        assert!(offsets.is_none());
1845
1846        let result = UnionArray::try_new(union_fields, type_ids, offsets, children);
1847        assert!(result.is_ok());
1848        assert_eq!(result.unwrap().len(), 3);
1849    }
1850
1851    #[test]
1852    fn into_parts_custom_type_ids() {
1853        let set_field_type_ids: [i8; 3] = [8, 4, 9];
1854        let data_type = DataType::Union(
1855            UnionFields::try_new(
1856                set_field_type_ids,
1857                [
1858                    Field::new("strings", DataType::Utf8, false),
1859                    Field::new("integers", DataType::Int32, false),
1860                    Field::new("floats", DataType::Float64, false),
1861                ],
1862            )
1863            .unwrap(),
1864            UnionMode::Dense,
1865        );
1866        let string_array = StringArray::from(vec!["foo", "bar", "baz"]);
1867        let int_array = Int32Array::from(vec![5, 6, 4]);
1868        let float_array = Float64Array::from(vec![10.0]);
1869        let type_ids = Buffer::from_vec(vec![4_i8, 8, 4, 8, 9, 4, 8]);
1870        let value_offsets = Buffer::from_vec(vec![0_i32, 0, 1, 1, 0, 2, 2]);
1871        let data = ArrayData::builder(data_type)
1872            .len(7)
1873            .buffers(vec![type_ids, value_offsets])
1874            .child_data(vec![
1875                string_array.into_data(),
1876                int_array.into_data(),
1877                float_array.into_data(),
1878            ])
1879            .build()
1880            .unwrap();
1881        let array = UnionArray::from(data);
1882
1883        let (union_fields, type_ids, offsets, children) = array.into_parts();
1884        assert_eq!(
1885            type_ids.iter().collect::<HashSet<_>>(),
1886            set_field_type_ids.iter().collect::<HashSet<_>>()
1887        );
1888        let result = UnionArray::try_new(union_fields, type_ids, offsets, children);
1889        assert!(result.is_ok());
1890        let array = result.unwrap();
1891        assert_eq!(array.len(), 7);
1892    }
1893
1894    #[test]
1895    fn test_dense_union_large_child() {
1896        let fields =
1897            UnionFields::try_new([3], [Field::new("nulls", DataType::Null, true)]).unwrap();
1898
1899        // NullArray represents these lengths without allocating a values buffer.
1900        for child_len in [i32::MAX as usize + 1, i32::MAX as usize + 2] {
1901            let array = UnionArray::try_new(
1902                fields.clone(),
1903                vec![3, 3].into(),
1904                Some(vec![0, i32::MAX].into()),
1905                vec![Arc::new(NullArray::new(child_len))],
1906            )
1907            .unwrap();
1908
1909            assert_eq!(array.child(3).len(), child_len);
1910            assert_eq!(array.value(1).len(), 1);
1911            array.to_data().validate_full().unwrap();
1912        }
1913    }
1914
1915    #[test]
1916    fn test_invalid() {
1917        let fields = UnionFields::try_new(
1918            [3, 2],
1919            [
1920                Field::new("a", DataType::Utf8, false),
1921                Field::new("b", DataType::Utf8, false),
1922            ],
1923        )
1924        .unwrap();
1925        let children = vec![
1926            Arc::new(StringArray::from_iter_values(["a", "b"])) as _,
1927            Arc::new(StringArray::from_iter_values(["c", "d"])) as _,
1928        ];
1929
1930        let type_ids = vec![3, 3, 2].into();
1931        let err =
1932            UnionArray::try_new(fields.clone(), type_ids, None, children.clone()).unwrap_err();
1933        assert_eq!(
1934            err.to_string(),
1935            "Invalid argument error: Sparse union child arrays must be equal in length to the length of the union"
1936        );
1937
1938        let type_ids = vec![1, 2].into();
1939        let err =
1940            UnionArray::try_new(fields.clone(), type_ids, None, children.clone()).unwrap_err();
1941        assert_eq!(
1942            err.to_string(),
1943            "Invalid argument error: Type Ids values must match one of the field type ids"
1944        );
1945
1946        let type_ids = vec![7, 2].into();
1947        let err = UnionArray::try_new(fields.clone(), type_ids, None, children).unwrap_err();
1948        assert_eq!(
1949            err.to_string(),
1950            "Invalid argument error: Type Ids values must match one of the field type ids"
1951        );
1952
1953        let children = vec![
1954            Arc::new(StringArray::from_iter_values(["a", "b"])) as _,
1955            Arc::new(StringArray::from_iter_values(["c"])) as _,
1956        ];
1957        let type_ids = ScalarBuffer::from(vec![3_i8, 3, 2]);
1958        let offsets = Some(vec![0, 1, 0].into());
1959        UnionArray::try_new(fields.clone(), type_ids.clone(), offsets, children.clone()).unwrap();
1960
1961        let offsets = Some(vec![0, 1, 1].into());
1962        let err = UnionArray::try_new(fields.clone(), type_ids.clone(), offsets, children.clone())
1963            .unwrap_err();
1964
1965        assert_eq!(
1966            err.to_string(),
1967            "Invalid argument error: Offsets must be non-negative and within the length of the Array"
1968        );
1969
1970        let offsets = Some(vec![0, -1, 0].into());
1971        let err = UnionArray::try_new(fields.clone(), type_ids.clone(), offsets, children.clone())
1972            .unwrap_err();
1973
1974        assert_eq!(
1975            err.to_string(),
1976            "Invalid argument error: Offsets must be non-negative and within the length of the Array"
1977        );
1978
1979        let offsets = Some(vec![0, 1].into());
1980        let err =
1981            UnionArray::try_new(fields.clone(), type_ids.clone(), offsets, children).unwrap_err();
1982
1983        assert_eq!(
1984            err.to_string(),
1985            "Invalid argument error: Type Ids and Offsets lengths must match"
1986        );
1987
1988        let err = UnionArray::try_new(fields.clone(), type_ids, None, vec![]).unwrap_err();
1989
1990        assert_eq!(
1991            err.to_string(),
1992            "Invalid argument error: Union fields length must match child arrays length"
1993        );
1994    }
1995
1996    #[test]
1997    fn test_logical_nulls_fast_paths() {
1998        // fields.len() <= 1
1999        let array = UnionArray::try_new(UnionFields::empty(), vec![].into(), None, vec![]).unwrap();
2000
2001        assert_eq!(array.logical_nulls(), None);
2002
2003        let fields = UnionFields::try_new(
2004            [1, 3],
2005            [
2006                Field::new("a", DataType::Int8, false), // non nullable
2007                Field::new("b", DataType::Int8, false), // non nullable
2008            ],
2009        )
2010        .unwrap();
2011        let array = UnionArray::try_new(
2012            fields,
2013            vec![1].into(),
2014            None,
2015            vec![
2016                Arc::new(Int8Array::from_value(5, 1)),
2017                Arc::new(Int8Array::from_value(5, 1)),
2018            ],
2019        )
2020        .unwrap();
2021
2022        assert_eq!(array.logical_nulls(), None);
2023
2024        let nullable_fields = UnionFields::try_new(
2025            [1, 3],
2026            [
2027                Field::new("a", DataType::Int8, true), // nullable but without nulls
2028                Field::new("b", DataType::Int8, true), // nullable but without nulls
2029            ],
2030        )
2031        .unwrap();
2032        let array = UnionArray::try_new(
2033            nullable_fields.clone(),
2034            vec![1, 1].into(),
2035            None,
2036            vec![
2037                Arc::new(Int8Array::from_value(-5, 2)), // nullable but without nulls
2038                Arc::new(Int8Array::from_value(-5, 2)), // nullable but without nulls
2039            ],
2040        )
2041        .unwrap();
2042
2043        assert_eq!(array.logical_nulls(), None);
2044
2045        let array = UnionArray::try_new(
2046            nullable_fields.clone(),
2047            vec![1, 1].into(),
2048            None,
2049            vec![
2050                // every child is completely null
2051                Arc::new(Int8Array::new_null(2)), // all null, same len as it's parent
2052                Arc::new(Int8Array::new_null(2)), // all null, same len as it's parent
2053            ],
2054        )
2055        .unwrap();
2056
2057        assert_eq!(array.logical_nulls(), Some(NullBuffer::new_null(2)));
2058
2059        let array = UnionArray::try_new(
2060            nullable_fields.clone(),
2061            vec![1, 1].into(),
2062            Some(vec![0, 1].into()),
2063            vec![
2064                // every child is completely null
2065                Arc::new(Int8Array::new_null(3)), // bigger that parent
2066                Arc::new(Int8Array::new_null(3)), // bigger that parent
2067            ],
2068        )
2069        .unwrap();
2070
2071        assert_eq!(array.logical_nulls(), Some(NullBuffer::new_null(2)));
2072    }
2073
2074    #[test]
2075    fn test_dense_union_logical_nulls_gather() {
2076        // union of [{A=1}, {A=2}, {B=3.2}, {B=}, {C=}, {C=}]
2077        let int_array = Int32Array::from(vec![1, 2]);
2078        let float_array = Float64Array::from(vec![Some(3.2), None]);
2079        let str_array = StringArray::new_null(1);
2080        let type_ids = [1, 1, 3, 3, 4, 4].into_iter().collect::<ScalarBuffer<i8>>();
2081        let offsets = [0, 1, 0, 1, 0, 0]
2082            .into_iter()
2083            .collect::<ScalarBuffer<i32>>();
2084
2085        let children = vec![
2086            Arc::new(int_array) as Arc<dyn Array>,
2087            Arc::new(float_array),
2088            Arc::new(str_array),
2089        ];
2090
2091        let array = UnionArray::try_new(union_fields(), type_ids, Some(offsets), children).unwrap();
2092
2093        let expected = BooleanBuffer::from(vec![true, true, true, false, false, false]);
2094
2095        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2096        assert_eq!(expected, array.gather_nulls(array.fields_logical_nulls()));
2097    }
2098
2099    #[test]
2100    fn test_dense_union_one_field_nonzero_type_id_logical_nulls() {
2101        let fields = UnionFields::try_new([5], [Field::new("a", DataType::Int32, true)]).unwrap();
2102        let child = Arc::new(Int32Array::from(vec![None, Some(1)]));
2103        let array = UnionArray::try_new(
2104            fields,
2105            vec![5, 5, 5].into(),
2106            Some(vec![1, 0, 1].into()),
2107            vec![child],
2108        )
2109        .unwrap();
2110
2111        let expected = NullBuffer::from(vec![true, false, true]);
2112        assert_eq!(array.logical_nulls(), Some(expected));
2113        assert_eq!(array.logical_null_count(), 1);
2114    }
2115
2116    #[test]
2117    fn test_sparse_union_logical_nulls_mask_all_nulls_skip_one() {
2118        let fields: UnionFields = [
2119            (1, Arc::new(Field::new("A", DataType::Int32, true))),
2120            (3, Arc::new(Field::new("B", DataType::Float64, true))),
2121        ]
2122        .into_iter()
2123        .collect();
2124
2125        // union of [{A=}, {A=}, {B=3.2}, {B=}]
2126        let int_array = Int32Array::new_null(4);
2127        let float_array = Float64Array::from(vec![None, None, Some(3.2), None]);
2128        let type_ids = [1, 1, 3, 3].into_iter().collect::<ScalarBuffer<i8>>();
2129
2130        let children = vec![Arc::new(int_array) as Arc<dyn Array>, Arc::new(float_array)];
2131
2132        let array = UnionArray::try_new(fields.clone(), type_ids, None, children).unwrap();
2133
2134        let expected = BooleanBuffer::from(vec![false, false, true, false]);
2135
2136        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2137        assert_eq!(
2138            expected,
2139            array.mask_sparse_all_with_nulls_skip_one(array.fields_logical_nulls())
2140        );
2141
2142        //like above, but repeated to generate two exact bitmasks and a non empty remainder
2143        let len = 2 * 64 + 32;
2144
2145        let int_array = Int32Array::new_null(len);
2146        let float_array = Float64Array::from_iter([Some(3.2), None].into_iter().cycle().take(len));
2147        let type_ids = ScalarBuffer::from_iter([1, 1, 3, 3].into_iter().cycle().take(len));
2148
2149        let array = UnionArray::try_new(
2150            fields,
2151            type_ids,
2152            None,
2153            vec![Arc::new(int_array), Arc::new(float_array)],
2154        )
2155        .unwrap();
2156
2157        let expected =
2158            BooleanBuffer::from_iter([false, false, true, false].into_iter().cycle().take(len));
2159
2160        assert_eq!(array.len(), len);
2161        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2162        assert_eq!(
2163            expected,
2164            array.mask_sparse_all_with_nulls_skip_one(array.fields_logical_nulls())
2165        );
2166    }
2167
2168    #[test]
2169    fn test_sparse_union_logical_mask_mixed_nulls_skip_fully_valid() {
2170        // union of [{A=2}, {A=2}, {B=3.2}, {B=}, {C=}, {C=}]
2171        let int_array = Int32Array::from_value(2, 6);
2172        let float_array = Float64Array::from_value(4.2, 6);
2173        let str_array = StringArray::new_null(6);
2174        let type_ids = [1, 1, 3, 3, 4, 4].into_iter().collect::<ScalarBuffer<i8>>();
2175
2176        let children = vec![
2177            Arc::new(int_array) as Arc<dyn Array>,
2178            Arc::new(float_array),
2179            Arc::new(str_array),
2180        ];
2181
2182        let array = UnionArray::try_new(union_fields(), type_ids, None, children).unwrap();
2183
2184        let expected = BooleanBuffer::from(vec![true, true, true, true, false, false]);
2185
2186        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2187        assert_eq!(
2188            expected,
2189            array.mask_sparse_skip_without_nulls(array.fields_logical_nulls())
2190        );
2191
2192        //like above, but repeated to generate two exact bitmasks and a non empty remainder
2193        let len = 2 * 64 + 32;
2194
2195        let int_array = Int32Array::from_value(2, len);
2196        let float_array = Float64Array::from_value(4.2, len);
2197        let str_array = StringArray::from_iter([None, Some("a")].into_iter().cycle().take(len));
2198        let type_ids = ScalarBuffer::from_iter([1, 1, 3, 3, 4, 4].into_iter().cycle().take(len));
2199
2200        let children = vec![
2201            Arc::new(int_array) as Arc<dyn Array>,
2202            Arc::new(float_array),
2203            Arc::new(str_array),
2204        ];
2205
2206        let array = UnionArray::try_new(union_fields(), type_ids, None, children).unwrap();
2207
2208        let expected = BooleanBuffer::from_iter(
2209            [true, true, true, true, false, true]
2210                .into_iter()
2211                .cycle()
2212                .take(len),
2213        );
2214
2215        assert_eq!(array.len(), len);
2216        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2217        assert_eq!(
2218            expected,
2219            array.mask_sparse_skip_without_nulls(array.fields_logical_nulls())
2220        );
2221    }
2222
2223    #[test]
2224    fn test_sparse_union_logical_mask_mixed_nulls_skip_fully_null() {
2225        // union of [{A=}, {A=}, {B=4.2}, {B=4.2}, {C=}, {C=}]
2226        let int_array = Int32Array::new_null(6);
2227        let float_array = Float64Array::from_value(4.2, 6);
2228        let str_array = StringArray::new_null(6);
2229        let type_ids = [1, 1, 3, 3, 4, 4].into_iter().collect::<ScalarBuffer<i8>>();
2230
2231        let children = vec![
2232            Arc::new(int_array) as Arc<dyn Array>,
2233            Arc::new(float_array),
2234            Arc::new(str_array),
2235        ];
2236
2237        let array = UnionArray::try_new(union_fields(), type_ids, None, children).unwrap();
2238
2239        let expected = BooleanBuffer::from(vec![false, false, true, true, false, false]);
2240
2241        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2242        assert_eq!(
2243            expected,
2244            array.mask_sparse_skip_fully_null(array.fields_logical_nulls())
2245        );
2246
2247        //like above, but repeated to generate two exact bitmasks and a non empty remainder
2248        let len = 2 * 64 + 32;
2249
2250        let int_array = Int32Array::new_null(len);
2251        let float_array = Float64Array::from_value(4.2, len);
2252        let str_array = StringArray::new_null(len);
2253        let type_ids = ScalarBuffer::from_iter([1, 1, 3, 3, 4, 4].into_iter().cycle().take(len));
2254
2255        let children = vec![
2256            Arc::new(int_array) as Arc<dyn Array>,
2257            Arc::new(float_array),
2258            Arc::new(str_array),
2259        ];
2260
2261        let array = UnionArray::try_new(union_fields(), type_ids, None, children).unwrap();
2262
2263        let expected = BooleanBuffer::from_iter(
2264            [false, false, true, true, false, false]
2265                .into_iter()
2266                .cycle()
2267                .take(len),
2268        );
2269
2270        assert_eq!(array.len(), len);
2271        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2272        assert_eq!(
2273            expected,
2274            array.mask_sparse_skip_fully_null(array.fields_logical_nulls())
2275        );
2276    }
2277
2278    #[test]
2279    fn test_sparse_union_logical_nulls_gather() {
2280        let n_fields = 50;
2281
2282        let non_null = Int32Array::from_value(2, 4);
2283        let mixed = Int32Array::from(vec![None, None, Some(1), None]);
2284        let fully_null = Int32Array::new_null(4);
2285
2286        let array = UnionArray::try_new(
2287            (1..)
2288                .step_by(2)
2289                .map(|i| {
2290                    (
2291                        i,
2292                        Arc::new(Field::new(format!("f{i}"), DataType::Int32, true)),
2293                    )
2294                })
2295                .take(n_fields)
2296                .collect(),
2297            vec![1, 3, 3, 5].into(),
2298            None,
2299            [
2300                Arc::new(non_null) as ArrayRef,
2301                Arc::new(mixed),
2302                Arc::new(fully_null),
2303            ]
2304            .into_iter()
2305            .cycle()
2306            .take(n_fields)
2307            .collect(),
2308        )
2309        .unwrap();
2310
2311        let expected = BooleanBuffer::from(vec![true, false, true, false]);
2312
2313        assert_eq!(expected, array.logical_nulls().unwrap().into_inner());
2314        assert_eq!(expected, array.gather_nulls(array.fields_logical_nulls()));
2315    }
2316
2317    fn union_fields() -> UnionFields {
2318        [
2319            (1, Arc::new(Field::new("A", DataType::Int32, true))),
2320            (3, Arc::new(Field::new("B", DataType::Float64, true))),
2321            (4, Arc::new(Field::new("C", DataType::Utf8, true))),
2322        ]
2323        .into_iter()
2324        .collect()
2325    }
2326
2327    #[test]
2328    fn test_is_nullable() {
2329        assert!(!create_union_array(false, false).is_nullable());
2330        assert!(create_union_array(true, false).is_nullable());
2331        assert!(create_union_array(false, true).is_nullable());
2332        assert!(create_union_array(true, true).is_nullable());
2333    }
2334
2335    /// Create a union array with a float and integer field
2336    ///
2337    /// If the `int_nullable` is true, the integer field will have nulls
2338    /// If the `float_nullable` is true, the float field will have nulls
2339    ///
2340    /// Note the `Field` definitions are always declared to be nullable
2341    fn create_union_array(int_nullable: bool, float_nullable: bool) -> UnionArray {
2342        let int_array = if int_nullable {
2343            Int32Array::from(vec![Some(1), None, Some(3)])
2344        } else {
2345            Int32Array::from(vec![1, 2, 3])
2346        };
2347        let float_array = if float_nullable {
2348            Float64Array::from(vec![Some(3.2), None, Some(4.2)])
2349        } else {
2350            Float64Array::from(vec![3.2, 4.2, 5.2])
2351        };
2352        let type_ids = [0, 1, 0].into_iter().collect::<ScalarBuffer<i8>>();
2353        let offsets = [0, 0, 0].into_iter().collect::<ScalarBuffer<i32>>();
2354        let union_fields = [
2355            (0, Arc::new(Field::new("A", DataType::Int32, true))),
2356            (1, Arc::new(Field::new("B", DataType::Float64, true))),
2357        ]
2358        .into_iter()
2359        .collect::<UnionFields>();
2360
2361        let children = vec![Arc::new(int_array) as Arc<dyn Array>, Arc::new(float_array)];
2362
2363        UnionArray::try_new(union_fields, type_ids, Some(offsets), children).unwrap()
2364    }
2365}