arrow_data/transform/
mod.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18//! Low-level array data abstractions.
19//!
20//! Provides utilities for creating, manipulating, and converting Arrow arrays
21//! made of primitive types, strings, and nested types.
22
23use super::{data::new_buffers, ArrayData, ArrayDataBuilder, ByteView};
24use crate::bit_mask::set_bits;
25use arrow_buffer::buffer::{BooleanBuffer, NullBuffer};
26use arrow_buffer::{bit_util, i256, ArrowNativeType, Buffer, MutableBuffer};
27use arrow_schema::{ArrowError, DataType, IntervalUnit, UnionMode};
28use half::f16;
29use num::Integer;
30use std::mem;
31
32mod boolean;
33mod fixed_binary;
34mod fixed_size_list;
35mod list;
36mod null;
37mod primitive;
38mod run;
39mod structure;
40mod union;
41mod utils;
42mod variable_size;
43
44type ExtendNullBits<'a> = Box<dyn Fn(&mut _MutableArrayData, usize, usize) + 'a>;
45// function that extends `[start..start+len]` to the mutable array.
46// this is dynamic because different data_types influence how buffers and children are extended.
47type Extend<'a> = Box<dyn Fn(&mut _MutableArrayData, usize, usize, usize) + 'a>;
48
49type ExtendNulls = Box<dyn Fn(&mut _MutableArrayData, usize)>;
50
51/// A mutable [ArrayData] that knows how to freeze itself into an [ArrayData].
52/// This is just a data container.
53#[derive(Debug)]
54struct _MutableArrayData<'a> {
55    pub data_type: DataType,
56    pub null_count: usize,
57
58    pub len: usize,
59    pub null_buffer: Option<MutableBuffer>,
60
61    // arrow specification only allows up to 3 buffers (2 ignoring the nulls above).
62    // Thus, we place them in the stack to avoid bound checks and greater data locality.
63    pub buffer1: MutableBuffer,
64    pub buffer2: MutableBuffer,
65    pub child_data: Vec<MutableArrayData<'a>>,
66}
67
68impl _MutableArrayData<'_> {
69    fn null_buffer(&mut self) -> &mut MutableBuffer {
70        self.null_buffer
71            .as_mut()
72            .expect("MutableArrayData not nullable")
73    }
74}
75
76fn build_extend_null_bits(array: &ArrayData, use_nulls: bool) -> ExtendNullBits {
77    if let Some(nulls) = array.nulls() {
78        let bytes = nulls.validity();
79        Box::new(move |mutable, start, len| {
80            let mutable_len = mutable.len;
81            let out = mutable.null_buffer();
82            utils::resize_for_bits(out, mutable_len + len);
83            mutable.null_count += set_bits(
84                out.as_slice_mut(),
85                bytes,
86                mutable_len,
87                nulls.offset() + start,
88                len,
89            );
90        })
91    } else if use_nulls {
92        Box::new(|mutable, _, len| {
93            let mutable_len = mutable.len;
94            let out = mutable.null_buffer();
95            utils::resize_for_bits(out, mutable_len + len);
96            let write_data = out.as_slice_mut();
97            (0..len).for_each(|i| {
98                bit_util::set_bit(write_data, mutable_len + i);
99            });
100        })
101    } else {
102        Box::new(|_, _, _| {})
103    }
104}
105
106/// Efficiently create an [ArrayData] from one or more existing [ArrayData]s by
107/// copying chunks.
108///
109/// The main use case of this struct is to perform unary operations to arrays of
110/// arbitrary types, such as `filter` and `take`.
111///
112/// # Example
113/// ```
114/// use arrow_buffer::Buffer;
115/// use arrow_data::ArrayData;
116/// use arrow_data::transform::MutableArrayData;
117/// use arrow_schema::DataType;
118/// fn i32_array(values: &[i32]) -> ArrayData {
119///   ArrayData::try_new(DataType::Int32, 5, None, 0, vec![Buffer::from_slice_ref(values)], vec![]).unwrap()
120/// }
121/// let arr1  = i32_array(&[1, 2, 3, 4, 5]);
122/// let arr2  = i32_array(&[6, 7, 8, 9, 10]);
123/// // Create a mutable array for copying values from arr1 and arr2, with a capacity for 6 elements
124/// let capacity = 3 * std::mem::size_of::<i32>();
125/// let mut mutable = MutableArrayData::new(vec![&arr1, &arr2], false, 10);
126/// // Copy the first 3 elements from arr1
127/// mutable.extend(0, 0, 3);
128/// // Copy the last 3 elements from arr2
129/// mutable.extend(1, 2, 4);
130/// // Complete the MutableArrayData into a new ArrayData
131/// let frozen = mutable.freeze();
132/// assert_eq!(frozen, i32_array(&[1, 2, 3, 8, 9, 10]));
133/// ```
134pub struct MutableArrayData<'a> {
135    /// Input arrays: the data being read FROM.
136    ///
137    /// Note this is "dead code" because all actual references to the arrays are
138    /// stored in closures for extending values and nulls.
139    #[allow(dead_code)]
140    arrays: Vec<&'a ArrayData>,
141
142    /// In progress output array: The data being written TO
143    ///
144    /// Note these fields are in a separate struct, [_MutableArrayData], as they
145    /// cannot be in [MutableArrayData] itself due to mutability invariants (interior
146    /// mutability): [MutableArrayData] contains a function that can only mutate
147    /// [_MutableArrayData], not [MutableArrayData] itself
148    data: _MutableArrayData<'a>,
149
150    /// The child data of the `Array` in Dictionary arrays.
151    ///
152    /// This is not stored in `_MutableArrayData` because these values are
153    /// constant and only needed at the end, when freezing [_MutableArrayData].
154    dictionary: Option<ArrayData>,
155
156    /// Variadic data buffers referenced by views.
157    ///
158    /// Note this this is not stored in `_MutableArrayData` because these values
159    /// are constant and only needed at the end, when freezing
160    /// [_MutableArrayData]
161    variadic_data_buffers: Vec<Buffer>,
162
163    /// function used to extend output array with values from input arrays.
164    ///
165    /// This function's lifetime is bound to the input arrays because it reads
166    /// values from them.
167    extend_values: Vec<Extend<'a>>,
168
169    /// function used to extend the output array with nulls from input arrays.
170    ///
171    /// This function's lifetime is bound to the input arrays because it reads
172    /// nulls from it.
173    extend_null_bits: Vec<ExtendNullBits<'a>>,
174
175    /// function used to extend the output array with null elements.
176    ///
177    /// This function is independent of the arrays and therefore has no lifetime.
178    extend_nulls: ExtendNulls,
179}
180
181impl std::fmt::Debug for MutableArrayData<'_> {
182    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
183        // ignores the closures.
184        f.debug_struct("MutableArrayData")
185            .field("data", &self.data)
186            .finish()
187    }
188}
189
190/// Builds an extend that adds `offset` to the source primitive
191/// Additionally validates that `max` fits into the
192/// the underlying primitive returning None if not
193fn build_extend_dictionary(array: &ArrayData, offset: usize, max: usize) -> Option<Extend> {
194    macro_rules! validate_and_build {
195        ($dt: ty) => {{
196            let _: $dt = max.try_into().ok()?;
197            let offset: $dt = offset.try_into().ok()?;
198            Some(primitive::build_extend_with_offset(array, offset))
199        }};
200    }
201    match array.data_type() {
202        DataType::Dictionary(child_data_type, _) => match child_data_type.as_ref() {
203            DataType::UInt8 => validate_and_build!(u8),
204            DataType::UInt16 => validate_and_build!(u16),
205            DataType::UInt32 => validate_and_build!(u32),
206            DataType::UInt64 => validate_and_build!(u64),
207            DataType::Int8 => validate_and_build!(i8),
208            DataType::Int16 => validate_and_build!(i16),
209            DataType::Int32 => validate_and_build!(i32),
210            DataType::Int64 => validate_and_build!(i64),
211            _ => unreachable!(),
212        },
213        _ => None,
214    }
215}
216
217/// Builds an extend that adds `buffer_offset` to any buffer indices encountered
218fn build_extend_view(array: &ArrayData, buffer_offset: u32) -> Extend {
219    let views = array.buffer::<u128>(0);
220    Box::new(
221        move |mutable: &mut _MutableArrayData, _, start: usize, len: usize| {
222            mutable
223                .buffer1
224                .extend(views[start..start + len].iter().map(|v| {
225                    let len = *v as u32;
226                    if len <= 12 {
227                        return *v; // Stored inline
228                    }
229                    let mut view = ByteView::from(*v);
230                    view.buffer_index += buffer_offset;
231                    view.into()
232                }))
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(_)
258        | DataType::Interval(IntervalUnit::DayTime) => primitive::build_extend::<i64>(array),
259        DataType::Interval(IntervalUnit::MonthDayNano) => primitive::build_extend::<i128>(array),
260        DataType::Decimal128(_, _) => primitive::build_extend::<i128>(array),
261        DataType::Decimal256(_, _) => primitive::build_extend::<i256>(array),
262        DataType::Utf8 | DataType::Binary => variable_size::build_extend::<i32>(array),
263        DataType::LargeUtf8 | DataType::LargeBinary => variable_size::build_extend::<i64>(array),
264        DataType::BinaryView | DataType::Utf8View => unreachable!("should use build_extend_view"),
265        DataType::Map(_, _) | DataType::List(_) => list::build_extend::<i32>(array),
266        DataType::ListView(_) | DataType::LargeListView(_) => {
267            unimplemented!("ListView/LargeListView not implemented")
268        }
269        DataType::LargeList(_) => list::build_extend::<i64>(array),
270        DataType::Dictionary(_, _) => unreachable!("should use build_extend_dictionary"),
271        DataType::Struct(_) => structure::build_extend(array),
272        DataType::FixedSizeBinary(_) => fixed_binary::build_extend(array),
273        DataType::Float16 => primitive::build_extend::<f16>(array),
274        DataType::FixedSizeList(_, _) => fixed_size_list::build_extend(array),
275        DataType::Union(_, mode) => match mode {
276            UnionMode::Sparse => union::build_extend_sparse(array),
277            UnionMode::Dense => union::build_extend_dense(array),
278        },
279        DataType::RunEndEncoded(_, _) => run::build_extend(array),
280    }
281}
282
283fn build_extend_nulls(data_type: &DataType) -> ExtendNulls {
284    Box::new(match data_type {
285        DataType::Null => null::extend_nulls,
286        DataType::Boolean => boolean::extend_nulls,
287        DataType::UInt8 => primitive::extend_nulls::<u8>,
288        DataType::UInt16 => primitive::extend_nulls::<u16>,
289        DataType::UInt32 => primitive::extend_nulls::<u32>,
290        DataType::UInt64 => primitive::extend_nulls::<u64>,
291        DataType::Int8 => primitive::extend_nulls::<i8>,
292        DataType::Int16 => primitive::extend_nulls::<i16>,
293        DataType::Int32 => primitive::extend_nulls::<i32>,
294        DataType::Int64 => primitive::extend_nulls::<i64>,
295        DataType::Float32 => primitive::extend_nulls::<f32>,
296        DataType::Float64 => primitive::extend_nulls::<f64>,
297        DataType::Date32 | DataType::Time32(_) | DataType::Interval(IntervalUnit::YearMonth) => {
298            primitive::extend_nulls::<i32>
299        }
300        DataType::Date64
301        | DataType::Time64(_)
302        | DataType::Timestamp(_, _)
303        | DataType::Duration(_)
304        | DataType::Interval(IntervalUnit::DayTime) => primitive::extend_nulls::<i64>,
305        DataType::Interval(IntervalUnit::MonthDayNano) => primitive::extend_nulls::<i128>,
306        DataType::Decimal128(_, _) => primitive::extend_nulls::<i128>,
307        DataType::Decimal256(_, _) => primitive::extend_nulls::<i256>,
308        DataType::Utf8 | DataType::Binary => variable_size::extend_nulls::<i32>,
309        DataType::LargeUtf8 | DataType::LargeBinary => variable_size::extend_nulls::<i64>,
310        DataType::BinaryView | DataType::Utf8View => primitive::extend_nulls::<u128>,
311        DataType::Map(_, _) | DataType::List(_) => list::extend_nulls::<i32>,
312        DataType::ListView(_) | DataType::LargeListView(_) => {
313            unimplemented!("ListView/LargeListView not implemented")
314        }
315        DataType::LargeList(_) => list::extend_nulls::<i64>,
316        DataType::Dictionary(child_data_type, _) => match child_data_type.as_ref() {
317            DataType::UInt8 => primitive::extend_nulls::<u8>,
318            DataType::UInt16 => primitive::extend_nulls::<u16>,
319            DataType::UInt32 => primitive::extend_nulls::<u32>,
320            DataType::UInt64 => primitive::extend_nulls::<u64>,
321            DataType::Int8 => primitive::extend_nulls::<i8>,
322            DataType::Int16 => primitive::extend_nulls::<i16>,
323            DataType::Int32 => primitive::extend_nulls::<i32>,
324            DataType::Int64 => primitive::extend_nulls::<i64>,
325            _ => unreachable!(),
326        },
327        DataType::Struct(_) => structure::extend_nulls,
328        DataType::FixedSizeBinary(_) => fixed_binary::extend_nulls,
329        DataType::Float16 => primitive::extend_nulls::<f16>,
330        DataType::FixedSizeList(_, _) => fixed_size_list::extend_nulls,
331        DataType::Union(_, mode) => match mode {
332            UnionMode::Sparse => union::extend_nulls_sparse,
333            UnionMode::Dense => union::extend_nulls_dense,
334        },
335        DataType::RunEndEncoded(_, _) => run::extend_nulls,
336    })
337}
338
339fn preallocate_offset_and_binary_buffer<Offset: ArrowNativeType + Integer>(
340    capacity: usize,
341    binary_size: usize,
342) -> [MutableBuffer; 2] {
343    // offsets
344    let mut buffer = MutableBuffer::new((1 + capacity) * mem::size_of::<Offset>());
345    // safety: `unsafe` code assumes that this buffer is initialized with one element
346    buffer.push(Offset::zero());
347
348    [
349        buffer,
350        MutableBuffer::new(binary_size * mem::size_of::<u8>()),
351    ]
352}
353
354/// Define capacities to pre-allocate for child data or data buffers.
355#[derive(Debug, Clone)]
356pub enum Capacities {
357    /// Binary, Utf8 and LargeUtf8 data types
358    ///
359    /// Defines
360    /// * the capacity of the array offsets
361    /// * the capacity of the binary/ str buffer
362    Binary(usize, Option<usize>),
363    /// List and LargeList data types
364    ///
365    /// Defines
366    /// * the capacity of the array offsets
367    /// * the capacity of the child data
368    List(usize, Option<Box<Capacities>>),
369    /// Struct type
370    ///
371    /// Defines
372    /// * the capacity of the array
373    /// * the capacities of the fields
374    Struct(usize, Option<Vec<Capacities>>),
375    /// Dictionary type
376    ///
377    /// Defines
378    /// * the capacity of the array/keys
379    /// * the capacity of the values
380    Dictionary(usize, Option<Box<Capacities>>),
381    /// Don't preallocate inner buffers and rely on array growth strategy
382    Array(usize),
383}
384
385impl<'a> MutableArrayData<'a> {
386    /// Returns a new [MutableArrayData] with capacity to `capacity` slots and
387    /// specialized to create an [ArrayData] from multiple `arrays`.
388    ///
389    /// # Arguments
390    /// * `arrays` - the source arrays to copy from
391    /// * `use_nulls` - a flag used to optimize insertions
392    ///   - `false` if the only source of nulls are the arrays themselves
393    ///   - `true` if the user plans to call [MutableArrayData::extend_nulls].
394    /// * capacity - the preallocated capacity of the output array, in bytes
395    ///
396    /// Thus, if `use_nulls` is `false`, calling
397    /// [MutableArrayData::extend_nulls] should not be used.
398    pub fn new(arrays: Vec<&'a ArrayData>, use_nulls: bool, capacity: usize) -> Self {
399        Self::with_capacities(arrays, use_nulls, Capacities::Array(capacity))
400    }
401
402    /// Similar to [MutableArrayData::new], but lets users define the
403    /// preallocated capacities of the array with more granularity.
404    ///
405    /// See [MutableArrayData::new] for more information on the arguments.
406    ///
407    /// # Panics
408    ///
409    /// This function panics if the given `capacities` don't match the data type
410    /// of `arrays`. Or when a [Capacities] variant is not yet supported.
411    pub fn with_capacities(
412        arrays: Vec<&'a ArrayData>,
413        use_nulls: bool,
414        capacities: Capacities,
415    ) -> Self {
416        let data_type = arrays[0].data_type();
417
418        for a in arrays.iter().skip(1) {
419            assert_eq!(
420                data_type,
421                a.data_type(),
422                "Arrays with inconsistent types passed to MutableArrayData"
423            )
424        }
425
426        // if any of the arrays has nulls, insertions from any array requires setting bits
427        // as there is at least one array with nulls.
428        let use_nulls = use_nulls | arrays.iter().any(|array| array.null_count() > 0);
429
430        let mut array_capacity;
431
432        let [buffer1, buffer2] = match (data_type, &capacities) {
433            (
434                DataType::LargeUtf8 | DataType::LargeBinary,
435                Capacities::Binary(capacity, Some(value_cap)),
436            ) => {
437                array_capacity = *capacity;
438                preallocate_offset_and_binary_buffer::<i64>(*capacity, *value_cap)
439            }
440            (DataType::Utf8 | DataType::Binary, Capacities::Binary(capacity, Some(value_cap))) => {
441                array_capacity = *capacity;
442                preallocate_offset_and_binary_buffer::<i32>(*capacity, *value_cap)
443            }
444            (_, Capacities::Array(capacity)) => {
445                array_capacity = *capacity;
446                new_buffers(data_type, *capacity)
447            }
448            (
449                DataType::List(_) | DataType::LargeList(_) | DataType::FixedSizeList(_, _),
450                Capacities::List(capacity, _),
451            ) => {
452                array_capacity = *capacity;
453                new_buffers(data_type, *capacity)
454            }
455            _ => panic!("Capacities: {capacities:?} not yet supported"),
456        };
457
458        let child_data = match &data_type {
459            DataType::Decimal128(_, _)
460            | DataType::Decimal256(_, _)
461            | DataType::Null
462            | DataType::Boolean
463            | DataType::UInt8
464            | DataType::UInt16
465            | DataType::UInt32
466            | DataType::UInt64
467            | DataType::Int8
468            | DataType::Int16
469            | DataType::Int32
470            | DataType::Int64
471            | DataType::Float16
472            | DataType::Float32
473            | DataType::Float64
474            | DataType::Date32
475            | DataType::Date64
476            | DataType::Time32(_)
477            | DataType::Time64(_)
478            | DataType::Duration(_)
479            | DataType::Timestamp(_, _)
480            | DataType::Utf8
481            | DataType::Binary
482            | DataType::LargeUtf8
483            | DataType::LargeBinary
484            | DataType::BinaryView
485            | DataType::Utf8View
486            | DataType::Interval(_)
487            | DataType::FixedSizeBinary(_) => vec![],
488            DataType::ListView(_) | DataType::LargeListView(_) => {
489                unimplemented!("ListView/LargeListView not implemented")
490            }
491            DataType::Map(_, _) | DataType::List(_) | DataType::LargeList(_) => {
492                let children = arrays
493                    .iter()
494                    .map(|array| &array.child_data()[0])
495                    .collect::<Vec<_>>();
496
497                let capacities =
498                    if let Capacities::List(capacity, ref child_capacities) = capacities {
499                        child_capacities
500                            .clone()
501                            .map(|c| *c)
502                            .unwrap_or(Capacities::Array(capacity))
503                    } else {
504                        Capacities::Array(array_capacity)
505                    };
506
507                vec![MutableArrayData::with_capacities(
508                    children, use_nulls, capacities,
509                )]
510            }
511            // the dictionary type just appends keys and clones the values.
512            DataType::Dictionary(_, _) => vec![],
513            DataType::Struct(fields) => match capacities {
514                Capacities::Struct(capacity, Some(ref child_capacities)) => {
515                    array_capacity = capacity;
516                    (0..fields.len())
517                        .zip(child_capacities)
518                        .map(|(i, child_cap)| {
519                            let child_arrays = arrays
520                                .iter()
521                                .map(|array| &array.child_data()[i])
522                                .collect::<Vec<_>>();
523                            MutableArrayData::with_capacities(
524                                child_arrays,
525                                use_nulls,
526                                child_cap.clone(),
527                            )
528                        })
529                        .collect::<Vec<_>>()
530                }
531                Capacities::Struct(capacity, None) => {
532                    array_capacity = capacity;
533                    (0..fields.len())
534                        .map(|i| {
535                            let child_arrays = arrays
536                                .iter()
537                                .map(|array| &array.child_data()[i])
538                                .collect::<Vec<_>>();
539                            MutableArrayData::new(child_arrays, use_nulls, capacity)
540                        })
541                        .collect::<Vec<_>>()
542                }
543                _ => (0..fields.len())
544                    .map(|i| {
545                        let child_arrays = arrays
546                            .iter()
547                            .map(|array| &array.child_data()[i])
548                            .collect::<Vec<_>>();
549                        MutableArrayData::new(child_arrays, use_nulls, array_capacity)
550                    })
551                    .collect::<Vec<_>>(),
552            },
553            DataType::RunEndEncoded(_, _) => {
554                let run_ends_child = arrays
555                    .iter()
556                    .map(|array| &array.child_data()[0])
557                    .collect::<Vec<_>>();
558                let value_child = arrays
559                    .iter()
560                    .map(|array| &array.child_data()[1])
561                    .collect::<Vec<_>>();
562                vec![
563                    MutableArrayData::new(run_ends_child, false, array_capacity),
564                    MutableArrayData::new(value_child, use_nulls, array_capacity),
565                ]
566            }
567            DataType::FixedSizeList(_, size) => {
568                let children = arrays
569                    .iter()
570                    .map(|array| &array.child_data()[0])
571                    .collect::<Vec<_>>();
572                let capacities =
573                    if let Capacities::List(capacity, ref child_capacities) = capacities {
574                        child_capacities
575                            .clone()
576                            .map(|c| *c)
577                            .unwrap_or(Capacities::Array(capacity * *size as usize))
578                    } else {
579                        Capacities::Array(array_capacity * *size as usize)
580                    };
581                vec![MutableArrayData::with_capacities(
582                    children, use_nulls, capacities,
583                )]
584            }
585            DataType::Union(fields, _) => (0..fields.len())
586                .map(|i| {
587                    let child_arrays = arrays
588                        .iter()
589                        .map(|array| &array.child_data()[i])
590                        .collect::<Vec<_>>();
591                    MutableArrayData::new(child_arrays, use_nulls, array_capacity)
592                })
593                .collect::<Vec<_>>(),
594        };
595
596        // Get the dictionary if any, and if it is a concatenation of multiple
597        let (dictionary, dict_concat) = match &data_type {
598            DataType::Dictionary(_, _) => {
599                // If more than one dictionary, concatenate dictionaries together
600                let dict_concat = !arrays
601                    .windows(2)
602                    .all(|a| a[0].child_data()[0].ptr_eq(&a[1].child_data()[0]));
603
604                match dict_concat {
605                    false => (Some(arrays[0].child_data()[0].clone()), false),
606                    true => {
607                        if let Capacities::Dictionary(_, _) = capacities {
608                            panic!("dictionary capacity not yet supported")
609                        }
610                        let dictionaries: Vec<_> =
611                            arrays.iter().map(|array| &array.child_data()[0]).collect();
612                        let lengths: Vec<_> = dictionaries
613                            .iter()
614                            .map(|dictionary| dictionary.len())
615                            .collect();
616                        let capacity = lengths.iter().sum();
617
618                        let mut mutable = MutableArrayData::new(dictionaries, false, capacity);
619
620                        for (i, len) in lengths.iter().enumerate() {
621                            mutable.extend(i, 0, *len)
622                        }
623
624                        (Some(mutable.freeze()), true)
625                    }
626                }
627            }
628            _ => (None, false),
629        };
630
631        let variadic_data_buffers = match &data_type {
632            DataType::BinaryView | DataType::Utf8View => arrays
633                .iter()
634                .flat_map(|x| x.buffers().iter().skip(1))
635                .map(Buffer::clone)
636                .collect(),
637            _ => vec![],
638        };
639
640        let extend_nulls = build_extend_nulls(data_type);
641
642        let extend_null_bits = arrays
643            .iter()
644            .map(|array| build_extend_null_bits(array, use_nulls))
645            .collect();
646
647        let null_buffer = use_nulls.then(|| {
648            let null_bytes = bit_util::ceil(array_capacity, 8);
649            MutableBuffer::from_len_zeroed(null_bytes)
650        });
651
652        let extend_values = match &data_type {
653            DataType::Dictionary(_, _) => {
654                let mut next_offset = 0;
655                let extend_values: Result<Vec<_>, _> = arrays
656                    .iter()
657                    .map(|array| {
658                        let offset = next_offset;
659                        let dict_len = array.child_data()[0].len();
660
661                        if dict_concat {
662                            next_offset += dict_len;
663                        }
664
665                        build_extend_dictionary(array, offset, offset + dict_len)
666                            .ok_or(ArrowError::DictionaryKeyOverflowError)
667                    })
668                    .collect();
669
670                extend_values.expect("MutableArrayData::new is infallible")
671            }
672            DataType::BinaryView | DataType::Utf8View => {
673                let mut next_offset = 0u32;
674                arrays
675                    .iter()
676                    .map(|arr| {
677                        let num_data_buffers = (arr.buffers().len() - 1) as u32;
678                        let offset = next_offset;
679                        next_offset = next_offset
680                            .checked_add(num_data_buffers)
681                            .expect("view buffer index overflow");
682                        build_extend_view(arr, offset)
683                    })
684                    .collect()
685            }
686            _ => arrays.iter().map(|array| build_extend(array)).collect(),
687        };
688
689        let data = _MutableArrayData {
690            data_type: data_type.clone(),
691            len: 0,
692            null_count: 0,
693            null_buffer,
694            buffer1,
695            buffer2,
696            child_data,
697        };
698        Self {
699            arrays,
700            data,
701            dictionary,
702            variadic_data_buffers,
703            extend_values,
704            extend_null_bits,
705            extend_nulls,
706        }
707    }
708
709    /// Extends the in progress array with a region of the input arrays
710    ///
711    /// # Arguments
712    /// * `index` - the index of array that you what to copy values from
713    /// * `start` - the start index of the chunk (inclusive)
714    /// * `end` - the end index of the chunk (exclusive)
715    ///
716    /// # Panic
717    /// This function panics if there is an invalid index,
718    /// i.e. `index` >= the number of source arrays
719    /// or `end` > the length of the `index`th array
720    pub fn extend(&mut self, index: usize, start: usize, end: usize) {
721        let len = end - start;
722        (self.extend_null_bits[index])(&mut self.data, start, len);
723        (self.extend_values[index])(&mut self.data, index, start, len);
724        self.data.len += len;
725    }
726
727    /// Extends the in progress array with null elements, ignoring the input arrays.
728    ///
729    /// # Panics
730    ///
731    /// Panics if [`MutableArrayData`] not created with `use_nulls` or nullable source arrays
732    pub fn extend_nulls(&mut self, len: usize) {
733        self.data.len += len;
734        let bit_len = bit_util::ceil(self.data.len, 8);
735        let nulls = self.data.null_buffer();
736        nulls.resize(bit_len, 0);
737        self.data.null_count += len;
738        (self.extend_nulls)(&mut self.data, len);
739    }
740
741    /// Returns the current length
742    #[inline]
743    pub fn len(&self) -> usize {
744        self.data.len
745    }
746
747    /// Returns true if len is 0
748    #[inline]
749    pub fn is_empty(&self) -> bool {
750        self.data.len == 0
751    }
752
753    /// Returns the current null count
754    #[inline]
755    pub fn null_count(&self) -> usize {
756        self.data.null_count
757    }
758
759    /// Creates a [ArrayData] from the in progress array, consuming `self`.
760    pub fn freeze(self) -> ArrayData {
761        unsafe { self.into_builder().build_unchecked() }
762    }
763
764    /// Consume self and returns the in progress array as [`ArrayDataBuilder`].
765    ///
766    /// This is useful for extending the default behavior of MutableArrayData.
767    pub fn into_builder(self) -> ArrayDataBuilder {
768        let data = self.data;
769
770        let buffers = match data.data_type {
771            DataType::Null
772            | DataType::Struct(_)
773            | DataType::FixedSizeList(_, _)
774            | DataType::RunEndEncoded(_, _) => {
775                vec![]
776            }
777            DataType::BinaryView | DataType::Utf8View => {
778                let mut b = self.variadic_data_buffers;
779                b.insert(0, data.buffer1.into());
780                b
781            }
782            DataType::Utf8 | DataType::Binary | DataType::LargeUtf8 | DataType::LargeBinary => {
783                vec![data.buffer1.into(), data.buffer2.into()]
784            }
785            DataType::Union(_, mode) => {
786                match mode {
787                    // Based on Union's DataTypeLayout
788                    UnionMode::Sparse => vec![data.buffer1.into()],
789                    UnionMode::Dense => vec![data.buffer1.into(), data.buffer2.into()],
790                }
791            }
792            _ => vec![data.buffer1.into()],
793        };
794
795        let child_data = match data.data_type {
796            DataType::Dictionary(_, _) => vec![self.dictionary.unwrap()],
797            _ => data.child_data.into_iter().map(|x| x.freeze()).collect(),
798        };
799
800        let nulls = match data.data_type {
801            // RunEndEncoded and Null arrays cannot have top-level null bitmasks
802            DataType::RunEndEncoded(_, _) | DataType::Null => None,
803            _ => data
804                .null_buffer
805                .map(|nulls| {
806                    let bools = BooleanBuffer::new(nulls.into(), 0, data.len);
807                    unsafe { NullBuffer::new_unchecked(bools, data.null_count) }
808                })
809                .filter(|n| n.null_count() > 0),
810        };
811
812        ArrayDataBuilder::new(data.data_type)
813            .offset(0)
814            .len(data.len)
815            .nulls(nulls)
816            .buffers(buffers)
817            .child_data(child_data)
818    }
819}
820
821// See arrow/tests/array_transform.rs for tests of transform functionality
822
823#[cfg(test)]
824mod test {
825    use super::*;
826    use arrow_schema::Field;
827    use std::sync::Arc;
828
829    #[test]
830    fn test_list_append_with_capacities() {
831        let array = ArrayData::new_empty(&DataType::List(Arc::new(Field::new(
832            "element",
833            DataType::Int64,
834            false,
835        ))));
836
837        let mutable = MutableArrayData::with_capacities(
838            vec![&array],
839            false,
840            Capacities::List(6, Some(Box::new(Capacities::Array(17)))),
841        );
842
843        // capacities are rounded up to multiples of 64 by MutableBuffer
844        assert_eq!(mutable.data.buffer1.capacity(), 64);
845        assert_eq!(mutable.data.child_data[0].data.buffer1.capacity(), 192);
846    }
847}
arrow_data/transform/mod.rs

arrow_data/transform/
mod.rs
