Skip to main content

arrow_data/transform/
mod.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//! Low-level array data abstractions.
6//!
7//! Provides utilities for creating, manipulating, and converting Arrow arrays
8//! made of primitive types, strings, and nested types.
9
10use super::{ArrayData, ArrayDataBuilder, MAX_INLINE_VIEW_LEN, data::new_buffers};
11use crate::bit_mask::set_bits;
12use arrow_buffer::buffer::{BooleanBuffer, NullBuffer};
13use arrow_buffer::{
14    ArrowNativeType, Buffer, IntervalDayTime, IntervalMonthDayNano, MutableBuffer, bit_util, i256,
15};
16use arrow_schema::{ArrowError, DataType, IntervalUnit, UnionMode};
17use half::f16;
18use num_integer::Integer;
19use std::mem;
20
21mod boolean;
22mod fixed_binary;
23mod fixed_size_list;
24mod list;
25mod list_view;
26mod null;
27mod primitive;
28mod run;
29mod structure;
30mod union;
31mod utils;
32mod variable_size;
33
34type ExtendNullBits<'a> = Box<dyn Fn(&mut _MutableArrayData, usize, usize) + 'a>;
35// function that extends `[start..start+len]` to the mutable array.
36// this is dynamic because different data_types influence how buffers and children are extended.
37type Extend<'a> =
38    Box<dyn Fn(&mut _MutableArrayData, usize, usize, usize) -> Result<(), ArrowError> + 'a>;
39
40type ExtendNulls = Box<dyn Fn(&mut _MutableArrayData, usize) -> Result<(), ArrowError>>;
41
42/// A mutable [ArrayData] that knows how to freeze itself into an [ArrayData].
43/// This is just a data container.
44#[derive(Debug)]
45struct _MutableArrayData<'a> {
46    pub data_type: DataType,
47    pub null_count: usize,
48
49    pub len: usize,
50    pub null_buffer: Option<MutableBuffer>,
51
52    // arrow specification only allows up to 3 buffers (2 ignoring the nulls above).
53    // Thus, we place them in the stack to avoid bound checks and greater data locality.
54    pub buffer1: MutableBuffer,
55    pub buffer2: MutableBuffer,
56    pub child_data: Vec<MutableArrayData<'a>>,
57}
58
59impl _MutableArrayData<'_> {
60    fn null_buffer(&mut self) -> &mut MutableBuffer {
61        self.null_buffer
62            .as_mut()
63            .expect("MutableArrayData not nullable")
64    }
65}
66
67fn build_extend_null_bits(array: &ArrayData, use_nulls: bool) -> ExtendNullBits<'_> {
68    if let Some(nulls) = array.nulls() {
69        let bytes = nulls.validity();
70        Box::new(move |mutable, start, len| {
71            let mutable_len = mutable.len;
72            let out = mutable.null_buffer();
73            utils::resize_for_bits(out, mutable_len + len);
74            mutable.null_count += set_bits(
75                out.as_slice_mut(),
76                bytes,
77                mutable_len,
78                nulls.offset() + start,
79                len,
80            );
81        })
82    } else if use_nulls {
83        Box::new(|mutable, _, len| {
84            let mutable_len = mutable.len;
85            let out = mutable.null_buffer();
86            utils::resize_for_bits(out, mutable_len + len);
87            let write_data = out.as_slice_mut();
88            (0..len).for_each(|i| {
89                bit_util::set_bit(write_data, mutable_len + i);
90            });
91        })
92    } else {
93        Box::new(|_, _, _| {})
94    }
95}
96
97/// Efficiently create an [ArrayData] from one or more existing [ArrayData]s by
98/// copying chunks.
99///
100/// The main use case of this struct is to perform unary operations to arrays of
101/// arbitrary types, such as `filter` and `take`.
102///
103/// # Example
104/// ```
105/// use arrow_buffer::Buffer;
106/// use arrow_data::ArrayData;
107/// use arrow_data::transform::MutableArrayData;
108/// use arrow_schema::DataType;
109/// fn i32_array(values: &[i32]) -> ArrayData {
110///   ArrayData::try_new(DataType::Int32, values.len(), None, 0, vec![Buffer::from_slice_ref(values)], vec![]).unwrap()
111/// }
112/// let arr1  = i32_array(&[1, 2, 3, 4, 5]);
113/// let arr2  = i32_array(&[6, 7, 8, 9, 10]);
114/// // Create a mutable array for copying values from arr1 and arr2, with a capacity for 6 elements
115/// let capacity = 3 * std::mem::size_of::<i32>();
116/// let mut mutable = MutableArrayData::new(vec![&arr1, &arr2], false, 10);
117/// // Copy the first 3 elements from arr1
118/// mutable.extend(0, 0, 3);
119/// // Copy the last 3 elements from arr2
120/// mutable.extend(1, 2, 5);
121/// // Complete the MutableArrayData into a new ArrayData
122/// let frozen = mutable.freeze();
123/// assert_eq!(frozen, i32_array(&[1, 2, 3, 8, 9, 10]));
124/// ```
125pub struct MutableArrayData<'a> {
126    /// Input arrays: the data being read FROM.
127    ///
128    /// Note all actual reads of the arrays go through the closures for extending
129    /// values and nulls; these references are only kept for bounds checking.
130    arrays: Vec<&'a ArrayData>,
131
132    /// In progress output array: The data being written TO
133    ///
134    /// Note these fields are in a separate struct, [_MutableArrayData], as they
135    /// cannot be in [MutableArrayData] itself due to mutability invariants (interior
136    /// mutability): [MutableArrayData] contains a function that can only mutate
137    /// [_MutableArrayData], not [MutableArrayData] itself
138    data: _MutableArrayData<'a>,
139
140    /// The child data of the `Array` in Dictionary arrays.
141    ///
142    /// This is not stored in `_MutableArrayData` because these values are
143    /// constant and only needed at the end, when freezing [_MutableArrayData].
144    dictionary: Option<ArrayData>,
145
146    /// Variadic data buffers referenced by views.
147    ///
148    /// Note this is not stored in `_MutableArrayData` because these values
149    /// are constant and only needed at the end, when freezing
150    /// [_MutableArrayData]
151    variadic_data_buffers: Vec<Buffer>,
152
153    /// function used to extend output array with values from input arrays.
154    ///
155    /// This function's lifetime is bound to the input arrays because it reads
156    /// values from them.
157    extend_values: Vec<Extend<'a>>,
158
159    /// function used to extend the output array with nulls from input arrays.
160    ///
161    /// This function's lifetime is bound to the input arrays because it reads
162    /// nulls from it.
163    extend_null_bits: Vec<ExtendNullBits<'a>>,
164
165    /// function used to extend the output array with null elements.
166    ///
167    /// This function is independent of the arrays and therefore has no lifetime.
168    extend_nulls: ExtendNulls,
169}
170
171impl std::fmt::Debug for MutableArrayData<'_> {
172    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
173        // ignores the closures.
174        f.debug_struct("MutableArrayData")
175            .field("data", &self.data)
176            .finish()
177    }
178}
179
180/// Builds an extend that adds `offset` to the source primitive
181/// Additionally validates that `max` fits into the
182/// the underlying primitive returning None if not
183fn build_extend_dictionary(array: &ArrayData, offset: usize, max: usize) -> Option<Extend<'_>> {
184    macro_rules! validate_and_build {
185        ($dt: ty) => {{
186            // `max` is the merged dictionary length; the largest key index is
187            // `max - 1`, so the key type only needs to hold `max - 1` (e.g. 256
188            // values use keys 0..=255, which fit in u8).
189            let _: $dt = max.saturating_sub(1).try_into().ok()?;
190            let offset: $dt = offset.try_into().ok()?;
191            Some(primitive::build_extend_with_offset(array, offset))
192        }};
193    }
194    match array.data_type() {
195        DataType::Dictionary(child_data_type, _) => match child_data_type.as_ref() {
196            DataType::UInt8 => validate_and_build!(u8),
197            DataType::UInt16 => validate_and_build!(u16),
198            DataType::UInt32 => validate_and_build!(u32),
199            DataType::UInt64 => validate_and_build!(u64),
200            DataType::Int8 => validate_and_build!(i8),
201            DataType::Int16 => validate_and_build!(i16),
202            DataType::Int32 => validate_and_build!(i32),
203            DataType::Int64 => validate_and_build!(i64),
204            _ => unreachable!(),
205        },
206        _ => None,
207    }
208}
209
210/// Builds an extend that adds `buffer_offset` to any buffer indices encountered
211fn build_extend_view(array: &ArrayData, buffer_offset: u32) -> Extend<'_> {
212    let views = array.buffer::<u128>(0);
213    Box::new(
214        move |mutable: &mut _MutableArrayData, _, start: usize, len: usize| {
215            mutable
216                .buffer1
217                .extend(views[start..start + len].iter().map(|v| {
218                    // A view of a string of 12 bytes or fewer stores the
219                    // string inline and has no buffer index, so adding 0
220                    // leaves it unchanged.
221                    let offset = if *v as u32 > MAX_INLINE_VIEW_LEN {
222                        buffer_offset
223                    } else {
224                        0
225                    };
226                    // The buffer index is bits 64 to 95 of a view. Adding
227                    // `buffer_offset` gives the string's buffer index in the
228                    // output, which fits in 32 bits, so the sum never carries
229                    // into bit 96.
230                    v + ((offset as u128) << 64)
231                }));
232            Ok(())
233        },
234    )
235}
236
237fn build_extend(array: &ArrayData) -> Extend<'_> {
238    match array.data_type() {
239        DataType::Null => null::build_extend(array),
240        DataType::Boolean => boolean::build_extend(array),
241        DataType::UInt8 => primitive::build_extend::<u8>(array),
242        DataType::UInt16 => primitive::build_extend::<u16>(array),
243        DataType::UInt32 => primitive::build_extend::<u32>(array),
244        DataType::UInt64 => primitive::build_extend::<u64>(array),
245        DataType::Int8 => primitive::build_extend::<i8>(array),
246        DataType::Int16 => primitive::build_extend::<i16>(array),
247        DataType::Int32 => primitive::build_extend::<i32>(array),
248        DataType::Int64 => primitive::build_extend::<i64>(array),
249        DataType::Float32 => primitive::build_extend::<f32>(array),
250        DataType::Float64 => primitive::build_extend::<f64>(array),
251        DataType::Date32 | DataType::Time32(_) | DataType::Interval(IntervalUnit::YearMonth) => {
252            primitive::build_extend::<i32>(array)
253        }
254        DataType::Date64
255        | DataType::Time64(_)
256        | DataType::Timestamp(_, _)
257        | DataType::Duration(_) => primitive::build_extend::<i64>(array),
258        // `IntervalDayTime` is two `i32`s, so its buffers need only be 4-byte aligned
259        DataType::Interval(IntervalUnit::DayTime) => {
260            primitive::build_extend::<IntervalDayTime>(array)
261        }
262        DataType::Interval(IntervalUnit::MonthDayNano) => {
263            primitive::build_extend::<IntervalMonthDayNano>(array)
264        }
265        DataType::Decimal32(_, _) => primitive::build_extend::<i32>(array),
266        DataType::Decimal64(_, _) => primitive::build_extend::<i64>(array),
267        DataType::Decimal128(_, _) => primitive::build_extend::<i128>(array),
268        DataType::Decimal256(_, _) => primitive::build_extend::<i256>(array),
269        DataType::Utf8 | DataType::Binary => variable_size::build_extend::<i32>(array),
270        DataType::LargeUtf8 | DataType::LargeBinary => variable_size::build_extend::<i64>(array),
271        DataType::BinaryView | DataType::Utf8View => unreachable!("should use build_extend_view"),
272        DataType::Map(_, _) | DataType::List(_) => list::build_extend::<i32>(array),
273        DataType::LargeList(_) => list::build_extend::<i64>(array),
274        DataType::ListView(_) => list_view::build_extend::<i32>(array),
275        DataType::LargeListView(_) => list_view::build_extend::<i64>(array),
276        DataType::Dictionary(_, _) => unreachable!("should use build_extend_dictionary"),
277        DataType::Struct(_) => structure::build_extend(array),
278        DataType::FixedSizeBinary(_) => fixed_binary::build_extend(array),
279        DataType::Float16 => primitive::build_extend::<f16>(array),
280        DataType::FixedSizeList(_, _) => fixed_size_list::build_extend(array),
281        DataType::Union(_, mode) => match mode {
282            UnionMode::Sparse => union::build_extend_sparse(array),
283            UnionMode::Dense => union::build_extend_dense(array),
284        },
285        DataType::RunEndEncoded(_, _) => run::build_extend(array),
286    }
287}
288
289fn build_extend_nulls(data_type: &DataType) -> ExtendNulls {
290    Box::new(match data_type {
291        DataType::Null => null::extend_nulls,
292        DataType::Boolean => boolean::extend_nulls,
293        DataType::UInt8 => primitive::extend_nulls::<u8>,
294        DataType::UInt16 => primitive::extend_nulls::<u16>,
295        DataType::UInt32 => primitive::extend_nulls::<u32>,
296        DataType::UInt64 => primitive::extend_nulls::<u64>,
297        DataType::Int8 => primitive::extend_nulls::<i8>,
298        DataType::Int16 => primitive::extend_nulls::<i16>,
299        DataType::Int32 => primitive::extend_nulls::<i32>,
300        DataType::Int64 => primitive::extend_nulls::<i64>,
301        DataType::Float32 => primitive::extend_nulls::<f32>,
302        DataType::Float64 => primitive::extend_nulls::<f64>,
303        DataType::Date32 | DataType::Time32(_) | DataType::Interval(IntervalUnit::YearMonth) => {
304            primitive::extend_nulls::<i32>
305        }
306        DataType::Date64
307        | DataType::Time64(_)
308        | DataType::Timestamp(_, _)
309        | DataType::Duration(_) => primitive::extend_nulls::<i64>,
310        DataType::Interval(IntervalUnit::DayTime) => primitive::extend_nulls::<IntervalDayTime>,
311        DataType::Interval(IntervalUnit::MonthDayNano) => {
312            primitive::extend_nulls::<IntervalMonthDayNano>
313        }
314        DataType::Decimal32(_, _) => primitive::extend_nulls::<i32>,
315        DataType::Decimal64(_, _) => primitive::extend_nulls::<i64>,
316        DataType::Decimal128(_, _) => primitive::extend_nulls::<i128>,
317        DataType::Decimal256(_, _) => primitive::extend_nulls::<i256>,
318        DataType::Utf8 | DataType::Binary => variable_size::extend_nulls::<i32>,
319        DataType::LargeUtf8 | DataType::LargeBinary => variable_size::extend_nulls::<i64>,
320        DataType::BinaryView | DataType::Utf8View => primitive::extend_nulls::<u128>,
321        DataType::Map(_, _) | DataType::List(_) => list::extend_nulls::<i32>,
322        DataType::LargeList(_) => list::extend_nulls::<i64>,
323        DataType::ListView(_) => list_view::extend_nulls::<i32>,
324        DataType::LargeListView(_) => list_view::extend_nulls::<i64>,
325        DataType::Dictionary(child_data_type, _) => match child_data_type.as_ref() {
326            DataType::UInt8 => primitive::extend_nulls::<u8>,
327            DataType::UInt16 => primitive::extend_nulls::<u16>,
328            DataType::UInt32 => primitive::extend_nulls::<u32>,
329            DataType::UInt64 => primitive::extend_nulls::<u64>,
330            DataType::Int8 => primitive::extend_nulls::<i8>,
331            DataType::Int16 => primitive::extend_nulls::<i16>,
332            DataType::Int32 => primitive::extend_nulls::<i32>,
333            DataType::Int64 => primitive::extend_nulls::<i64>,
334            _ => unreachable!(),
335        },
336        DataType::Struct(_) => structure::extend_nulls,
337        DataType::FixedSizeBinary(_) => fixed_binary::extend_nulls,
338        DataType::Float16 => primitive::extend_nulls::<f16>,
339        DataType::FixedSizeList(_, _) => fixed_size_list::extend_nulls,
340        DataType::Union(_, mode) => match mode {
341            UnionMode::Sparse => union::extend_nulls_sparse,
342            UnionMode::Dense => union::extend_nulls_dense,
343        },
344        DataType::RunEndEncoded(_, _) => run::extend_nulls,
345    })
346}
347
348fn preallocate_offset_and_binary_buffer<Offset: ArrowNativeType + Integer>(
349    capacity: usize,
350    binary_size: usize,
351) -> Result<[MutableBuffer; 2], ArrowError> {
352    // offsets
353    let offset_capacity = capacity
354        .checked_add(1)
355        .and_then(|len| len.checked_mul(mem::size_of::<Offset>()))
356        .ok_or_else(|| ArrowError::MemoryError("offset buffer size overflow".into()))?;
357    let mut buffer = MutableBuffer::try_with_capacity(offset_capacity)
358        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
359    // safety: `unsafe` code assumes that this buffer is initialized with one element
360    buffer
361        .try_extend_from_slice(&[Offset::zero()])
362        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
363
364    Ok([
365        buffer,
366        MutableBuffer::try_with_capacity(binary_size)
367            .map_err(|e| ArrowError::MemoryError(e.to_string()))?,
368    ])
369}
370
371/// Define capacities to pre-allocate for child data or data buffers.
372#[derive(Debug, Clone)]
373pub enum Capacities {
374    /// Binary, Utf8 and LargeUtf8 data types
375    ///
376    /// Defines
377    /// * the capacity of the array offsets
378    /// * the capacity of the binary/ str buffer
379    Binary(usize, Option<usize>),
380    /// List, LargeList and Map data types
381    ///
382    /// Defines
383    /// * the capacity of the array offsets
384    /// * the capacity of the child data
385    ///
386    /// For Map the child data is the entries [`DataType::Struct`], so the child
387    /// capacity is a [`Capacities::Struct`] holding the key and value capacities.
388    List(usize, Option<Box<Capacities>>),
389    /// Struct type
390    ///
391    /// Defines
392    /// * the capacity of the array
393    /// * the capacities of the fields
394    Struct(usize, Option<Vec<Capacities>>),
395    /// Dictionary type
396    ///
397    /// Defines
398    /// * the capacity of the array/keys
399    /// * the capacity of the values
400    Dictionary(usize, Option<Box<Capacities>>),
401    /// Don't preallocate inner buffers and rely on array growth strategy
402    Array(usize),
403}
404
405impl<'a> MutableArrayData<'a> {
406    /// Returns a new [MutableArrayData] with capacity to `capacity` slots and
407    /// specialized to create an [ArrayData] from multiple `arrays`.
408    ///
409    /// # Arguments
410    /// * `arrays` - the source arrays to copy from
411    /// * `use_nulls` - a flag indicating whether the caller intends to call `extend_nulls`.
412    ///   Note: null-handling is enabled automatically if any source array contains nulls.
413    /// * `capacity` - the preallocated capacity of the output array, in slots (number of elements)
414    ///
415    /// If `use_nulls` is `false` and no source array contains nulls, calling
416    /// [MutableArrayData::extend_nulls] will panic and
417    /// [MutableArrayData::try_extend_nulls] will return an error.
418    ///
419    /// # Panics
420    ///
421    /// Panics if a buffer cannot be allocated or if merged dictionary values overflow the
422    /// dictionary key type. See [MutableArrayData::try_new] for a fallible variant.
423    pub fn new(arrays: Vec<&'a ArrayData>, use_nulls: bool, capacity: usize) -> Self {
424        Self::with_capacities(arrays, use_nulls, Capacities::Array(capacity))
425    }
426
427    /// Fallible variant of [MutableArrayData::new].
428    ///
429    /// Unlike [MutableArrayData::new], this returns an error if a buffer cannot be allocated or
430    /// merged dictionary values overflow the dictionary key type.
431    pub fn try_new(
432        arrays: Vec<&'a ArrayData>,
433        use_nulls: bool,
434        capacity: usize,
435    ) -> Result<Self, ArrowError> {
436        Self::try_with_capacities(arrays, use_nulls, Capacities::Array(capacity))
437    }
438
439    /// Similar to [MutableArrayData::new], but lets users define the
440    /// preallocated capacities of the array with more granularity.
441    ///
442    /// See [MutableArrayData::new] for more information on the arguments.
443    ///
444    /// # Panics
445    ///
446    /// * if the given `capacities` don't match the data type of `arrays`
447    /// * if a [Capacities] variant is not yet supported
448    /// * when merging dictionary arrays whose combined values overflow the
449    ///   dictionary key type — see [MutableArrayData::try_with_capacities] for a
450    ///   fallible variant
451    /// * if a buffer cannot be allocated
452    pub fn with_capacities(
453        arrays: Vec<&'a ArrayData>,
454        use_nulls: bool,
455        capacities: Capacities,
456    ) -> Self {
457        Self::try_with_capacities(arrays, use_nulls, capacities)
458            .expect("MutableArrayData construction failed")
459    }
460
461    /// Fallible variant of [MutableArrayData::with_capacities].
462    ///
463    /// Returns an error instead of panicking when allocating buffers or merging
464    /// dictionary arrays whose combined values would overflow the dictionary key
465    /// type. Still panics for other unsupported combinations (inconsistent input
466    /// types, unsupported `Capacities` variants) as documented on
467    /// [MutableArrayData::with_capacities].
468    pub fn try_with_capacities(
469        arrays: Vec<&'a ArrayData>,
470        use_nulls: bool,
471        capacities: Capacities,
472    ) -> Result<Self, ArrowError> {
473        let data_type = arrays[0].data_type();
474
475        for a in arrays.iter().skip(1) {
476            assert_eq!(
477                data_type,
478                a.data_type(),
479                "Arrays with inconsistent types passed to MutableArrayData"
480            )
481        }
482
483        // if any of the arrays has nulls, insertions from any array requires setting bits
484        // as there is at least one array with nulls.
485        let use_nulls = use_nulls | arrays.iter().any(|array| array.null_count() > 0);
486
487        let mut array_capacity;
488
489        let [buffer1, buffer2] = match (data_type, &capacities) {
490            (
491                DataType::LargeUtf8 | DataType::LargeBinary,
492                Capacities::Binary(capacity, Some(value_cap)),
493            ) => {
494                array_capacity = *capacity;
495                preallocate_offset_and_binary_buffer::<i64>(*capacity, *value_cap)?
496            }
497            (DataType::Utf8 | DataType::Binary, Capacities::Binary(capacity, Some(value_cap))) => {
498                array_capacity = *capacity;
499                preallocate_offset_and_binary_buffer::<i32>(*capacity, *value_cap)?
500            }
501            (_, Capacities::Array(capacity)) => {
502                array_capacity = *capacity;
503                new_buffers(data_type, *capacity)?
504            }
505            (
506                DataType::List(_)
507                | DataType::LargeList(_)
508                | DataType::ListView(_)
509                | DataType::LargeListView(_)
510                | DataType::FixedSizeList(_, _)
511                | DataType::Map(_, _),
512                Capacities::List(capacity, _),
513            ) => {
514                array_capacity = *capacity;
515                new_buffers(data_type, *capacity)?
516            }
517            (DataType::Struct(_), Capacities::Struct(capacity, _)) => {
518                array_capacity = *capacity;
519                new_buffers(data_type, *capacity)?
520            }
521            _ => panic!("Capacities: {capacities:?} not yet supported"),
522        };
523
524        let child_data = match &data_type {
525            DataType::Decimal32(_, _)
526            | DataType::Decimal64(_, _)
527            | DataType::Decimal128(_, _)
528            | DataType::Decimal256(_, _)
529            | DataType::Null
530            | DataType::Boolean
531            | DataType::UInt8
532            | DataType::UInt16
533            | DataType::UInt32
534            | DataType::UInt64
535            | DataType::Int8
536            | DataType::Int16
537            | DataType::Int32
538            | DataType::Int64
539            | DataType::Float16
540            | DataType::Float32
541            | DataType::Float64
542            | DataType::Date32
543            | DataType::Date64
544            | DataType::Time32(_)
545            | DataType::Time64(_)
546            | DataType::Duration(_)
547            | DataType::Timestamp(_, _)
548            | DataType::Utf8
549            | DataType::Binary
550            | DataType::LargeUtf8
551            | DataType::LargeBinary
552            | DataType::BinaryView
553            | DataType::Utf8View
554            | DataType::Interval(_)
555            | DataType::FixedSizeBinary(_) => vec![],
556            DataType::Map(_, _)
557            | DataType::List(_)
558            | DataType::LargeList(_)
559            | DataType::ListView(_)
560            | DataType::LargeListView(_) => {
561                let children = arrays
562                    .iter()
563                    .map(|array| &array.child_data()[0])
564                    .collect::<Vec<_>>();
565
566                let capacities =
567                    if let Capacities::List(capacity, ref child_capacities) = capacities {
568                        child_capacities
569                            .clone()
570                            .map(|c| *c)
571                            .unwrap_or(Capacities::Array(capacity))
572                    } else {
573                        Capacities::Array(array_capacity)
574                    };
575
576                vec![MutableArrayData::try_with_capacities(
577                    children, use_nulls, capacities,
578                )?]
579            }
580            // the dictionary type just appends keys and clones the values.
581            DataType::Dictionary(_, _) => vec![],
582            DataType::Struct(fields) => match capacities {
583                Capacities::Struct(capacity, Some(ref child_capacities)) => {
584                    array_capacity = capacity;
585                    (0..fields.len())
586                        .zip(child_capacities)
587                        .map(|(i, child_cap)| {
588                            let child_arrays = arrays
589                                .iter()
590                                .map(|array| &array.child_data()[i])
591                                .collect::<Vec<_>>();
592                            MutableArrayData::try_with_capacities(
593                                child_arrays,
594                                use_nulls,
595                                child_cap.clone(),
596                            )
597                        })
598                        .collect::<Result<Vec<_>, _>>()?
599                }
600                Capacities::Struct(capacity, None) => {
601                    array_capacity = capacity;
602                    (0..fields.len())
603                        .map(|i| {
604                            let child_arrays = arrays
605                                .iter()
606                                .map(|array| &array.child_data()[i])
607                                .collect::<Vec<_>>();
608                            MutableArrayData::try_new(child_arrays, use_nulls, capacity)
609                        })
610                        .collect::<Result<Vec<_>, _>>()?
611                }
612                _ => (0..fields.len())
613                    .map(|i| {
614                        let child_arrays = arrays
615                            .iter()
616                            .map(|array| &array.child_data()[i])
617                            .collect::<Vec<_>>();
618                        MutableArrayData::try_new(child_arrays, use_nulls, array_capacity)
619                    })
620                    .collect::<Result<Vec<_>, _>>()?,
621            },
622            DataType::RunEndEncoded(_, _) => {
623                let run_ends_child = arrays
624                    .iter()
625                    .map(|array| &array.child_data()[0])
626                    .collect::<Vec<_>>();
627                let value_child = arrays
628                    .iter()
629                    .map(|array| &array.child_data()[1])
630                    .collect::<Vec<_>>();
631                vec![
632                    MutableArrayData::try_new(run_ends_child, false, array_capacity)?,
633                    MutableArrayData::try_new(value_child, use_nulls, array_capacity)?,
634                ]
635            }
636            DataType::FixedSizeList(_, size) => {
637                let children = arrays
638                    .iter()
639                    .map(|array| &array.child_data()[0])
640                    .collect::<Vec<_>>();
641                let capacities = if let Capacities::List(capacity, ref child_capacities) =
642                    capacities
643                {
644                    match child_capacities.clone() {
645                        Some(capacity) => *capacity,
646                        None => Capacities::Array(
647                            capacity.checked_mul(*size as usize).ok_or_else(|| {
648                                ArrowError::MemoryError("fixed-size list capacity overflow".into())
649                            })?,
650                        ),
651                    }
652                } else {
653                    Capacities::Array(array_capacity.checked_mul(*size as usize).ok_or_else(
654                        || ArrowError::MemoryError("fixed-size list capacity overflow".into()),
655                    )?)
656                };
657                vec![MutableArrayData::try_with_capacities(
658                    children, use_nulls, capacities,
659                )?]
660            }
661            DataType::Union(fields, _) => (0..fields.len())
662                .map(|i| {
663                    let child_arrays = arrays
664                        .iter()
665                        .map(|array| &array.child_data()[i])
666                        .collect::<Vec<_>>();
667                    MutableArrayData::try_new(child_arrays, use_nulls, array_capacity)
668                })
669                .collect::<Result<Vec<_>, _>>()?,
670        };
671
672        // Get the dictionary if any, and if it is a concatenation of multiple
673        let (dictionary, dict_concat) = match &data_type {
674            DataType::Dictionary(_, _) => {
675                // If more than one dictionary, concatenate dictionaries together
676                let dict_concat = !arrays
677                    .windows(2)
678                    .all(|a| a[0].child_data()[0].ptr_eq(&a[1].child_data()[0]));
679
680                match dict_concat {
681                    false => (Some(arrays[0].child_data()[0].clone()), false),
682                    true => {
683                        if let Capacities::Dictionary(_, _) = capacities {
684                            panic!("dictionary capacity not yet supported")
685                        }
686                        let dictionaries: Vec<_> =
687                            arrays.iter().map(|array| &array.child_data()[0]).collect();
688                        let lengths: Vec<_> = dictionaries
689                            .iter()
690                            .map(|dictionary| dictionary.len())
691                            .collect();
692                        let capacity = lengths.iter().try_fold(0usize, |acc, len| {
693                            acc.checked_add(*len).ok_or_else(|| {
694                                ArrowError::MemoryError("dictionary size overflow".into())
695                            })
696                        })?;
697
698                        let mut mutable = MutableArrayData::try_new(dictionaries, false, capacity)?;
699
700                        for (i, len) in lengths.iter().enumerate() {
701                            mutable.try_extend(i, 0, *len)?;
702                        }
703
704                        (Some(mutable.freeze()), true)
705                    }
706                }
707            }
708            _ => (None, false),
709        };
710
711        let variadic_data_buffers = match &data_type {
712            DataType::BinaryView | DataType::Utf8View => arrays
713                .iter()
714                .flat_map(|x| x.buffers().iter().skip(1))
715                .map(Buffer::clone)
716                .collect(),
717            _ => vec![],
718        };
719
720        let extend_nulls = build_extend_nulls(data_type);
721
722        let extend_null_bits = arrays
723            .iter()
724            .map(|array| build_extend_null_bits(array, use_nulls))
725            .collect();
726
727        let null_buffer = use_nulls
728            .then(|| {
729                let null_bytes = bit_util::ceil(array_capacity, 8);
730                MutableBuffer::try_from_len_zeroed(null_bytes)
731                    .map_err(|e| ArrowError::MemoryError(e.to_string()))
732            })
733            .transpose()?;
734
735        let extend_values = match &data_type {
736            DataType::Dictionary(_, _) => {
737                let mut next_offset = 0;
738                let extend_values: Result<Vec<_>, _> = arrays
739                    .iter()
740                    .map(|array| {
741                        let offset = next_offset;
742                        let dict_len = array.child_data()[0].len();
743
744                        if dict_concat {
745                            next_offset += dict_len;
746                        }
747
748                        build_extend_dictionary(array, offset, offset + dict_len)
749                            .ok_or(ArrowError::DictionaryKeyOverflowError)
750                    })
751                    .collect();
752
753                extend_values?
754            }
755            DataType::BinaryView | DataType::Utf8View => {
756                let mut next_offset = 0u32;
757                arrays
758                    .iter()
759                    .map(|arr| {
760                        let num_data_buffers = (arr.buffers().len() - 1) as u32;
761                        let offset = next_offset;
762                        next_offset = next_offset
763                            .checked_add(num_data_buffers)
764                            .expect("view buffer index overflow");
765                        build_extend_view(arr, offset)
766                    })
767                    .collect()
768            }
769            _ => arrays.iter().map(|array| build_extend(array)).collect(),
770        };
771
772        let data = _MutableArrayData {
773            data_type: data_type.clone(),
774            len: 0,
775            null_count: 0,
776            null_buffer,
777            buffer1,
778            buffer2,
779            child_data,
780        };
781        Ok(Self {
782            arrays,
783            data,
784            dictionary,
785            variadic_data_buffers,
786            extend_values,
787            extend_null_bits,
788            extend_nulls,
789        })
790    }
791
792    /// Extends the in progress array with a region of the input arrays, returning an error on
793    /// overflow.
794    ///
795    /// # Arguments
796    /// * `index` - the index of array that you want to copy values from
797    /// * `start` - the start index of the chunk (inclusive)
798    /// * `end` - the end index of the chunk (exclusive)
799    ///
800    /// # Errors
801    /// Returns an error if
802    /// * `index` >= the number of source arrays,
803    /// * `start..end` is not a valid range within the `index`th array, or
804    /// * offset arithmetic overflows the underlying integer type.
805    pub fn try_extend(&mut self, index: usize, start: usize, end: usize) -> Result<(), ArrowError> {
806        let Some(array_len) = self.arrays.get(index).map(|array| array.len()) else {
807            return Err(ArrowError::InvalidArgumentError(format!(
808                "Source array index {index} is out of bounds: there are {} source arrays",
809                self.arrays.len()
810            )));
811        };
812        if end < start || array_len < end {
813            return Err(ArrowError::InvalidArgumentError(format!(
814                "Invalid range {start}..{end} for source array {index} of length {array_len}"
815            )));
816        }
817
818        let len = end - start;
819        (self.extend_null_bits[index])(&mut self.data, start, len);
820        // Snapshot buffer lengths before attempting the extend so we can roll
821        // back to a consistent state if it fails.
822        let buf1_len = self.data.buffer1.len();
823        let buf2_len = self.data.buffer2.len();
824        if let Err(e) = (self.extend_values[index])(&mut self.data, index, start, len) {
825            // Restore buffers to their pre-call lengths so the array remains
826            // in a valid state for the caller to inspect or retry.
827            self.data.buffer1.truncate(buf1_len);
828            self.data.buffer2.truncate(buf2_len);
829            return Err(e);
830        }
831        self.data.len += len;
832        Ok(())
833    }
834
835    /// Extends the in progress array with a region of the input arrays.
836    ///
837    /// # Panics
838    /// This function panics if
839    /// * `index` >= the number of source arrays,
840    /// * `start..end` is not a valid range within the `index`th array, or
841    /// * the offset type overflows (e.g. more than 2 GiB in a `StringArray`).
842    #[deprecated(
843        since = "59.0.0",
844        note = "Use `try_extend` which returns an error on overflow instead of panicking"
845    )]
846    pub fn extend(&mut self, index: usize, start: usize, end: usize) {
847        self.try_extend(index, start, end).expect("extend failed")
848    }
849
850    /// Extends the in progress array with null elements, ignoring the input arrays, returning an
851    /// error on overflow.
852    ///
853    /// Prefer this over [`extend_nulls`](Self::extend_nulls) to handle cases where the run-end
854    /// counter overflows (relevant for `RunEndEncoded` arrays).
855    ///
856    /// # Errors
857    ///
858    /// Returns an error if this [`MutableArrayData`] was not created with `use_nulls` and none
859    /// of the source arrays are nullable, or if the run-end counter overflows.
860    pub fn try_extend_nulls(&mut self, len: usize) -> Result<(), ArrowError> {
861        if self.data.null_buffer.is_none() {
862            return Err(ArrowError::InvalidArgumentError(
863                "MutableArrayData cannot be extended with nulls: it was created with `use_nulls` \
864                 set to false and no source array is nullable"
865                    .to_owned(),
866            ));
867        }
868
869        if len == 0 {
870            return Ok(());
871        }
872
873        (self.extend_nulls)(&mut self.data, len)?;
874
875        self.data.len += len;
876        let bit_len = bit_util::ceil(self.data.len, 8);
877        let nulls = self.data.null_buffer();
878        nulls
879            .try_resize(bit_len, 0)
880            .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
881        self.data.null_count += len;
882        Ok(())
883    }
884
885    /// Extends the in progress array with null elements, ignoring the input arrays.
886    ///
887    /// # Panics
888    ///
889    /// Panics if this [`MutableArrayData`] was not created with `use_nulls` and none of the
890    /// source arrays are nullable, or if the run-end counter overflows.
891    #[deprecated(
892        since = "59.0.0",
893        note = "Use `try_extend_nulls` which returns an error on overflow instead of panicking"
894    )]
895    pub fn extend_nulls(&mut self, len: usize) {
896        self.try_extend_nulls(len).expect("extend_nulls failed")
897    }
898
899    /// Returns the current length
900    #[inline]
901    pub fn len(&self) -> usize {
902        self.data.len
903    }
904
905    /// Returns true if len is 0
906    #[inline]
907    pub fn is_empty(&self) -> bool {
908        self.data.len == 0
909    }
910
911    /// Returns the current null count
912    #[inline]
913    pub fn null_count(&self) -> usize {
914        self.data.null_count
915    }
916
917    /// Creates a [ArrayData] from the in progress array, consuming `self`.
918    pub fn freeze(self) -> ArrayData {
919        unsafe { self.into_builder().build_unchecked() }
920    }
921
922    /// Consume self and returns the in progress array as [`ArrayDataBuilder`].
923    ///
924    /// This is useful for extending the default behavior of MutableArrayData.
925    pub fn into_builder(self) -> ArrayDataBuilder {
926        let data = self.data;
927
928        let buffers = match data.data_type {
929            DataType::Null
930            | DataType::Struct(_)
931            | DataType::FixedSizeList(_, _)
932            | DataType::RunEndEncoded(_, _) => {
933                vec![]
934            }
935            DataType::BinaryView | DataType::Utf8View => {
936                let mut b = self.variadic_data_buffers;
937                b.insert(0, data.buffer1.into());
938                b
939            }
940            DataType::Utf8
941            | DataType::Binary
942            | DataType::LargeUtf8
943            | DataType::LargeBinary
944            | DataType::ListView(_)
945            | DataType::LargeListView(_) => {
946                vec![data.buffer1.into(), data.buffer2.into()]
947            }
948            DataType::Union(_, mode) => {
949                match mode {
950                    // Based on Union's DataTypeLayout
951                    UnionMode::Sparse => vec![data.buffer1.into()],
952                    UnionMode::Dense => vec![data.buffer1.into(), data.buffer2.into()],
953                }
954            }
955            _ => vec![data.buffer1.into()],
956        };
957
958        let child_data = match data.data_type {
959            DataType::Dictionary(_, _) => vec![self.dictionary.unwrap()],
960            _ => data.child_data.into_iter().map(|x| x.freeze()).collect(),
961        };
962
963        let nulls = match data.data_type {
964            // RunEndEncoded, Null, and Union arrays cannot have top-level null bitmasks
965            DataType::RunEndEncoded(_, _) | DataType::Null | DataType::Union(_, _) => None,
966            _ => data
967                .null_buffer
968                .map(|nulls| {
969                    let bools = BooleanBuffer::new(nulls.into(), 0, data.len);
970                    unsafe { NullBuffer::new_unchecked(bools, data.null_count) }
971                })
972                .filter(|n| n.null_count() > 0),
973        };
974
975        ArrayDataBuilder::new(data.data_type)
976            .offset(0)
977            .len(data.len)
978            .nulls(nulls)
979            .buffers(buffers)
980            .child_data(child_data)
981    }
982}
983
984// See arrow/tests/array_transform.rs for tests of transform functionality
985
986#[cfg(test)]
987mod test {
988    use super::*;
989    use arrow_schema::Field;
990    use std::sync::Arc;
991
992    fn int64_array_data(values: Vec<i64>) -> ArrayData {
993        let len = values.len();
994        ArrayData::try_new(
995            DataType::Int64,
996            len,
997            None,
998            0,
999            vec![arrow_buffer::Buffer::from_slice_ref(&values)],
1000            vec![],
1001        )
1002        .unwrap()
1003    }
1004
1005    #[test]
1006    fn test_try_with_capacities_buffer_size_overflow() {
1007        let int64 = ArrayData::new_empty(&DataType::Int64);
1008        let err = MutableArrayData::try_new(vec![&int64], false, usize::MAX).unwrap_err();
1009        assert!(matches!(err, ArrowError::MemoryError(_)));
1010
1011        let binary = ArrayData::new_empty(&DataType::Binary);
1012        let err = MutableArrayData::try_with_capacities(
1013            vec![&binary],
1014            false,
1015            Capacities::Binary(usize::MAX, Some(0)),
1016        )
1017        .unwrap_err();
1018        assert!(matches!(err, ArrowError::MemoryError(_)));
1019    }
1020
1021    #[test]
1022    fn test_try_extend_invalid_index_and_range() {
1023        let array = int64_array_data(vec![1, 2, 3]);
1024        let mut mutable = MutableArrayData::new(vec![&array], false, 3);
1025
1026        let err = mutable.try_extend(1, 0, 1).unwrap_err();
1027        assert_eq!(
1028            err.to_string(),
1029            "Invalid argument error: Source array index 1 is out of bounds: there are 1 source arrays"
1030        );
1031
1032        let err = mutable.try_extend(0, 0, 4).unwrap_err();
1033        assert_eq!(
1034            err.to_string(),
1035            "Invalid argument error: Invalid range 0..4 for source array 0 of length 3"
1036        );
1037
1038        // `end < start` used to underflow:
1039        let err = mutable.try_extend(0, 2, 1).unwrap_err();
1040        assert_eq!(
1041            err.to_string(),
1042            "Invalid argument error: Invalid range 2..1 for source array 0 of length 3"
1043        );
1044
1045        // The bounds are inclusive of the full array:
1046        mutable.try_extend(0, 3, 3).unwrap();
1047        mutable.try_extend(0, 0, 3).unwrap();
1048        assert_eq!(mutable.len(), 3);
1049    }
1050
1051    #[test]
1052    fn test_try_extend_nulls_without_null_buffer() {
1053        let array = int64_array_data(vec![1, 2, 3]);
1054        let mut mutable = MutableArrayData::new(vec![&array], false, 3);
1055        let err = mutable.try_extend_nulls(1).unwrap_err();
1056        assert!(
1057            err.to_string().contains("cannot be extended with nulls"),
1058            "unexpected error: {err}"
1059        );
1060
1061        let mut mutable = MutableArrayData::new(vec![&array], true, 3);
1062        mutable.try_extend_nulls(1).unwrap();
1063        assert_eq!(mutable.len(), 1);
1064    }
1065
1066    #[test]
1067    fn test_try_extend_nulls_empty_union() {
1068        use arrow_schema::{UnionFields, UnionMode};
1069
1070        for mode in [UnionMode::Sparse, UnionMode::Dense] {
1071            let mut builder = ArrayData::builder(DataType::Union(UnionFields::empty(), mode))
1072                .len(0)
1073                .add_buffer(Buffer::from_vec(Vec::<i8>::new()));
1074
1075            if mode == UnionMode::Dense {
1076                builder = builder.add_buffer(Buffer::from_vec(Vec::<i32>::new()));
1077            }
1078
1079            let source = builder.build().unwrap();
1080            let mut mutable = MutableArrayData::new(vec![&source], true, 0);
1081
1082            mutable.try_extend_nulls(0).unwrap();
1083            assert_eq!(mutable.len(), 0);
1084
1085            let err = mutable.try_extend_nulls(1).unwrap_err();
1086            assert_eq!(
1087                err.to_string(),
1088                "Invalid argument error: Cannot extend a union with no fields with nulls"
1089            );
1090            assert_eq!(mutable.len(), 0);
1091        }
1092    }
1093
1094    #[test]
1095    fn test_try_extend_nulls_union_uses_nullable_field() {
1096        use arrow_schema::{Field, UnionFields};
1097
1098        let fields = UnionFields::try_new(
1099            vec![0, 1],
1100            vec![
1101                Field::new("non_nullable", DataType::Int32, false),
1102                Field::new("nullable", DataType::Int32, true),
1103            ],
1104        )
1105        .unwrap();
1106
1107        for mode in [UnionMode::Sparse, UnionMode::Dense] {
1108            let mut builder = ArrayData::builder(DataType::Union(fields.clone(), mode))
1109                .len(0)
1110                .add_buffer(Buffer::from_vec(Vec::<i8>::new()));
1111
1112            if mode == UnionMode::Dense {
1113                builder = builder.add_buffer(Buffer::from_vec(Vec::<i32>::new()));
1114            }
1115
1116            let source = builder
1117                .child_data(vec![
1118                    ArrayData::new_empty(&DataType::Int32),
1119                    ArrayData::new_empty(&DataType::Int32),
1120                ])
1121                .build()
1122                .unwrap();
1123            let mut mutable = MutableArrayData::new(vec![&source], true, 1);
1124
1125            mutable.try_extend_nulls(1).unwrap();
1126            let result = mutable.freeze();
1127
1128            assert_eq!(result.buffer::<i8>(0), &[1]);
1129            assert_eq!(result.child_data()[1].null_count(), 1);
1130            assert_eq!(result.child_data()[1].len(), 1);
1131            if mode == UnionMode::Dense {
1132                assert_eq!(result.buffer::<i32>(1), &[0]);
1133                assert_eq!(result.child_data()[0].len(), 0);
1134            } else {
1135                assert_eq!(result.child_data()[0].len(), 1);
1136            }
1137        }
1138    }
1139
1140    #[test]
1141    fn test_try_extend_nulls_union_without_nullable_fields() {
1142        use arrow_schema::{Field, UnionFields};
1143
1144        let fields = UnionFields::try_new(
1145            vec![0],
1146            vec![Field::new("non_nullable", DataType::Int32, false)],
1147        )
1148        .unwrap();
1149        let source = ArrayData::builder(DataType::Union(fields, UnionMode::Sparse))
1150            .len(0)
1151            .add_buffer(Buffer::from_vec(Vec::<i8>::new()))
1152            .child_data(vec![ArrayData::new_empty(&DataType::Int32)])
1153            .build()
1154            .unwrap();
1155        let mut mutable = MutableArrayData::new(vec![&source], true, 0);
1156
1157        let err = mutable.try_extend_nulls(1).unwrap_err();
1158        assert_eq!(
1159            err.to_string(),
1160            "Invalid argument error: Cannot extend a union with no nullable fields with nulls"
1161        );
1162        assert_eq!(mutable.len(), 0);
1163    }
1164
1165    #[test]
1166    fn test_list_append_with_capacities() {
1167        let array = ArrayData::new_empty(&DataType::List(Arc::new(Field::new(
1168            "element",
1169            DataType::Int64,
1170            false,
1171        ))));
1172
1173        let mutable = MutableArrayData::with_capacities(
1174            vec![&array],
1175            false,
1176            Capacities::List(6, Some(Box::new(Capacities::Array(17)))),
1177        );
1178
1179        // capacities are rounded up to multiples of 64 by MutableBuffer
1180        assert_eq!(mutable.data.buffer1.capacity(), 64);
1181        assert_eq!(mutable.data.child_data[0].data.buffer1.capacity(), 192);
1182    }
1183
1184    #[test]
1185    fn test_map_append_with_capacities() {
1186        let entries = Arc::new(Field::new(
1187            "entries",
1188            DataType::Struct(
1189                vec![
1190                    Field::new("keys", DataType::Int64, false),
1191                    Field::new("values", DataType::Int64, true),
1192                ]
1193                .into(),
1194            ),
1195            false,
1196        ));
1197        let array = ArrayData::new_empty(&DataType::Map(entries, false));
1198
1199        let mutable = MutableArrayData::with_capacities(
1200            vec![&array],
1201            false,
1202            Capacities::List(
1203                6,
1204                Some(Box::new(Capacities::Struct(
1205                    17,
1206                    Some(vec![Capacities::Array(17), Capacities::Array(17)]),
1207                ))),
1208            ),
1209        );
1210
1211        // capacities are rounded up to multiples of 64 by MutableBuffer
1212        // the map offsets buffer holds `1 + 6` i32s
1213        assert_eq!(mutable.data.buffer1.capacity(), 64);
1214
1215        // the entries struct itself has no buffers of its own
1216        let entries = &mutable.data.child_data[0];
1217        assert_eq!(entries.data.buffer1.capacity(), 0);
1218
1219        // both key and value buffers hold 17 i64s
1220        assert_eq!(entries.data.child_data[0].data.buffer1.capacity(), 192);
1221        assert_eq!(entries.data.child_data[1].data.buffer1.capacity(), 192);
1222    }
1223}