Skip to main content

arrow_data/
data.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//! Contains [`ArrayData`], a generic representation of Arrow array data which encapsulates
6//! common attributes and operations for Arrow array.
7
8use crate::bit_iterator::BitSliceIterator;
9use arrow_buffer::buffer::{BooleanBuffer, NullBuffer};
10use arrow_buffer::{
11    ArrowNativeType, Buffer, IntervalDayTime, IntervalMonthDayNano, MutableBuffer, bit_util, i256,
12};
13use arrow_schema::{ArrowError, DataType, UnionMode};
14use std::mem;
15use std::ops::Range;
16use std::sync::Arc;
17
18use crate::{equal, validate_binary_view, validate_string_view};
19
20#[inline]
21pub(crate) fn contains_nulls(
22    null_bit_buffer: Option<&NullBuffer>,
23    offset: usize,
24    len: usize,
25) -> bool {
26    match null_bit_buffer {
27        Some(buffer) => {
28            match BitSliceIterator::new(buffer.validity(), buffer.offset() + offset, len).next() {
29                Some((start, end)) => start != 0 || end != len,
30                None => len != 0, // No non-null values
31            }
32        }
33        None => false, // No null buffer
34    }
35}
36
37#[inline]
38pub(crate) fn count_nulls(
39    null_bit_buffer: Option<&NullBuffer>,
40    offset: usize,
41    len: usize,
42) -> usize {
43    if let Some(buf) = null_bit_buffer {
44        let buffer = buf.buffer();
45        len - buffer.count_set_bits_offset(offset + buf.offset(), len)
46    } else {
47        0
48    }
49}
50
51/// Creates 2 [`MutableBuffer`]s with a given `capacity` (in slots).
52#[inline]
53pub(crate) fn new_buffers(
54    data_type: &DataType,
55    capacity: usize,
56) -> Result<[MutableBuffer; 2], ArrowError> {
57    let new_buffer = |len| {
58        MutableBuffer::try_with_capacity(len).map_err(|e| ArrowError::MemoryError(e.to_string()))
59    };
60    let sized_buffer = |width: usize| {
61        let len = capacity
62            .checked_mul(width)
63            .ok_or_else(|| ArrowError::MemoryError("buffer size overflow".into()))?;
64        new_buffer(len)
65    };
66
67    Ok(match data_type {
68        DataType::Null => [MutableBuffer::default(), MutableBuffer::default()],
69        DataType::Boolean => {
70            let bytes = bit_util::ceil(capacity, 8);
71            [new_buffer(bytes)?, MutableBuffer::default()]
72        }
73        DataType::UInt8
74        | DataType::UInt16
75        | DataType::UInt32
76        | DataType::UInt64
77        | DataType::Int8
78        | DataType::Int16
79        | DataType::Int32
80        | DataType::Int64
81        | DataType::Float16
82        | DataType::Float32
83        | DataType::Float64
84        | DataType::Decimal32(_, _)
85        | DataType::Decimal64(_, _)
86        | DataType::Decimal128(_, _)
87        | DataType::Decimal256(_, _)
88        | DataType::Date32
89        | DataType::Time32(_)
90        | DataType::Date64
91        | DataType::Time64(_)
92        | DataType::Duration(_)
93        | DataType::Timestamp(_, _)
94        | DataType::Interval(_) => [
95            sized_buffer(data_type.primitive_width().unwrap())?,
96            MutableBuffer::default(),
97        ],
98        DataType::Utf8 | DataType::Binary => {
99            let offset_capacity = capacity
100                .checked_add(1)
101                .and_then(|len| len.checked_mul(mem::size_of::<i32>()))
102                .ok_or_else(|| ArrowError::MemoryError("offset buffer size overflow".into()))?;
103            let mut buffer = new_buffer(offset_capacity)?;
104            // safety: `unsafe` code assumes that this buffer is initialized with one element
105            buffer
106                .try_extend_from_slice(&[0i32])
107                .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
108            [buffer, sized_buffer(mem::size_of::<u8>())?]
109        }
110        DataType::LargeUtf8 | DataType::LargeBinary => {
111            let offset_capacity = capacity
112                .checked_add(1)
113                .and_then(|len| len.checked_mul(mem::size_of::<i64>()))
114                .ok_or_else(|| ArrowError::MemoryError("offset buffer size overflow".into()))?;
115            let mut buffer = new_buffer(offset_capacity)?;
116            // safety: `unsafe` code assumes that this buffer is initialized with one element
117            buffer
118                .try_extend_from_slice(&[0i64])
119                .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
120            [buffer, sized_buffer(mem::size_of::<u8>())?]
121        }
122        DataType::BinaryView | DataType::Utf8View => [
123            sized_buffer(mem::size_of::<u128>())?,
124            MutableBuffer::default(),
125        ],
126        DataType::List(_) | DataType::Map(_, _) => {
127            // offset buffer always starts with a zero
128            let offset_capacity = capacity
129                .checked_add(1)
130                .and_then(|len| len.checked_mul(mem::size_of::<i32>()))
131                .ok_or_else(|| ArrowError::MemoryError("offset buffer size overflow".into()))?;
132            let mut buffer = new_buffer(offset_capacity)?;
133            buffer
134                .try_extend_from_slice(&[0i32])
135                .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
136            [buffer, MutableBuffer::default()]
137        }
138        DataType::ListView(_) => [
139            sized_buffer(mem::size_of::<i32>())?,
140            sized_buffer(mem::size_of::<i32>())?,
141        ],
142        DataType::LargeList(_) => {
143            // offset buffer always starts with a zero
144            let offset_capacity = capacity
145                .checked_add(1)
146                .and_then(|len| len.checked_mul(mem::size_of::<i64>()))
147                .ok_or_else(|| ArrowError::MemoryError("offset buffer size overflow".into()))?;
148            let mut buffer = new_buffer(offset_capacity)?;
149            buffer
150                .try_extend_from_slice(&[0i64])
151                .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
152            [buffer, MutableBuffer::default()]
153        }
154        DataType::LargeListView(_) => [
155            sized_buffer(mem::size_of::<i64>())?,
156            sized_buffer(mem::size_of::<i64>())?,
157        ],
158        DataType::FixedSizeBinary(size) => {
159            if *size < 0 {
160                panic!("cannot construct buffers from FixedSizeBinary({size})");
161            }
162            [sized_buffer(*size as usize)?, MutableBuffer::default()]
163        }
164        DataType::Dictionary(k, _) => [
165            sized_buffer(k.primitive_width().unwrap())?,
166            MutableBuffer::default(),
167        ],
168        DataType::FixedSizeList(_, _) | DataType::Struct(_) | DataType::RunEndEncoded(_, _) => {
169            [MutableBuffer::default(), MutableBuffer::default()]
170        }
171        DataType::Union(_, mode) => {
172            let type_ids = sized_buffer(mem::size_of::<i8>())?;
173            match mode {
174                UnionMode::Sparse => [type_ids, MutableBuffer::default()],
175                UnionMode::Dense => {
176                    let offsets = sized_buffer(mem::size_of::<i32>())?;
177                    [type_ids, offsets]
178                }
179            }
180        }
181    })
182}
183
184/// A generic representation of Arrow array data which encapsulates common attributes
185/// and operations for Arrow array.
186///
187/// Specific operations for different arrays types (e.g., primitive, list, struct)
188/// are implemented in `Array`.
189///
190/// # Memory Layout
191///
192/// `ArrayData` has references to one or more underlying data buffers
193/// and optional child ArrayData, depending on type as illustrated
194/// below. Bitmaps are not shown for simplicity but they are stored
195/// similarly to the buffers.
196///
197/// ```text
198///                        offset
199///                       points to
200/// ┌───────────────────┐ start of  ┌───────┐       Different
201/// │                   │   data    │       │     ArrayData may
202/// │ArrayData {        │           │....   │     also refers to
203/// │  data_type: ...   │   ─ ─ ─ ─▶│1234   │  ┌ ─  the same
204/// │  offset: ... ─ ─ ─│─ ┘        │4372   │      underlying
205/// │  len: ...    ─ ─ ─│─ ┐        │4888   │  │     buffer with different offset/len
206/// │  buffers: [       │           │5882   │◀─
207/// │    ...            │  │        │4323   │
208/// │  ]                │   ─ ─ ─ ─▶│4859   │
209/// │  child_data: [    │           │....   │
210/// │    ...            │           │       │
211/// │  ]                │           └───────┘
212/// │}                  │
213/// │                   │            Shared Buffer uses
214/// │               │   │            bytes::Bytes to hold
215/// └───────────────────┘            actual data values
216///           ┌ ─ ─ ┘
217///
218///           ▼
219/// ┌───────────────────┐
220/// │ArrayData {        │
221/// │  ...              │
222/// │}                  │
223/// │                   │
224/// └───────────────────┘
225///
226/// Child ArrayData may also have its own buffers and children
227/// ```
228
229#[derive(Debug, Clone)]
230pub struct ArrayData {
231    /// The data type
232    data_type: DataType,
233
234    /// The number of elements
235    len: usize,
236
237    /// The offset in number of items (not bytes).
238    ///
239    /// The offset applies to [`Self::child_data`] and [`Self::buffers`]. It
240    /// does NOT apply to [`Self::nulls`].
241    ///
242    /// See [`Self::offset()`] for details and diagrams.
243    offset: usize,
244
245    /// The buffers that store the actual data for this array, as defined
246    /// in the [Arrow Spec].
247    ///
248    /// Depending on the array types, [`Self::buffers`] can hold different
249    /// kinds of buffers (e.g., value buffer, value offset buffer) at different
250    /// positions.
251    ///
252    /// The buffer may be larger than needed.  Some items at the beginning may be skipped if
253    /// there is an `offset`.  Some items at the end may be skipped if the buffer is longer than
254    /// we need to satisfy `len`.
255    ///
256    /// [Arrow Spec](https://arrow.apache.org/docs/format/Columnar.html#physical-memory-layout)
257    buffers: Vec<Buffer>,
258
259    /// The child(ren) of this array.
260    ///
261    /// Only non-empty for nested types, such as `ListArray` and
262    /// `StructArray`.
263    ///
264    /// The first logical element in each child element begins at `offset`.
265    ///
266    /// If the child element also has an offset then these offsets are
267    /// cumulative.
268    ///
269    /// See [`Self::child_data()`] and [`Self::offset()`] for details.
270    child_data: Vec<ArrayData>,
271
272    /// The null bitmap.
273    ///
274    /// `None` indicates all values are non-null in this array.
275    ///
276    /// [`Self::offset()`] does not apply to the null bitmap. While the
277    /// BooleanBuffer may be sliced (have its own offset) internally, this
278    /// `NullBuffer` always represents exactly `len` elements.
279    nulls: Option<NullBuffer>,
280}
281
282/// A thread-safe, shared reference to the Arrow array data.
283pub type ArrayDataRef = Arc<ArrayData>;
284
285fn checked_len_plus_offset(
286    data_type: &DataType,
287    len: usize,
288    offset: usize,
289) -> Result<usize, ArrowError> {
290    len.checked_add(offset).ok_or_else(|| {
291        ArrowError::InvalidArgumentError(format!(
292            "Length {len} with offset {offset} overflows usize for {data_type}"
293        ))
294    })
295}
296
297/// Returns the first and last of `offsets`, and the bytes of `values` between
298/// them as a `str`. Returns `None` if the offsets are not valid indexes into
299/// `values` or those bytes are not valid UTF-8.
300fn utf8_span<'a, T: ArrowNativeType>(
301    offsets: &[T],
302    values: &'a [u8],
303) -> Option<(usize, usize, &'a str)> {
304    let first = offsets.first()?.to_usize()?;
305    let last = offsets.last()?.to_usize()?;
306    let values_str = std::str::from_utf8(values.get(first..last)?).ok()?;
307    Some((first, last, values_str))
308}
309
310impl ArrayData {
311    /// Create a new ArrayData instance;
312    ///
313    /// If `null_count` is not specified, the number of nulls in
314    /// null_bit_buffer is calculated.
315    ///
316    /// If the number of nulls is 0 then the null_bit_buffer
317    /// is set to `None`.
318    ///
319    /// # Safety
320    ///
321    /// The input values *must* form a valid Arrow array for
322    /// `data_type`, or undefined behavior can result.
323    ///
324    /// Note: This is a low level API and most users of the arrow
325    /// crate should create arrays using the methods in the `array`
326    /// module.
327    pub unsafe fn new_unchecked(
328        data_type: DataType,
329        len: usize,
330        null_count: Option<usize>,
331        null_bit_buffer: Option<Buffer>,
332        offset: usize,
333        buffers: Vec<Buffer>,
334        child_data: Vec<ArrayData>,
335    ) -> Self {
336        let builder = Self::inner_new_builder(
337            data_type,
338            len,
339            null_count,
340            null_bit_buffer,
341            offset,
342            buffers,
343            child_data,
344        );
345
346        // SAFETY: caller responsible for ensuring data is valid
347        unsafe { builder.build_unchecked() }
348    }
349
350    /// Create a new ArrayData, validating that the provided buffers form a valid
351    /// Arrow array of the specified data type.
352    ///
353    /// If the number of nulls in `null_bit_buffer` is 0 then the null_bit_buffer
354    /// is set to `None`.
355    ///
356    /// Internally this calls through to [`Self::validate_data`]
357    ///
358    /// Note: This is a low level API and most users of the arrow crate should create
359    /// arrays using the builders found in [arrow_array](https://docs.rs/arrow-array)
360    /// or [`ArrayDataBuilder`].
361    ///
362    /// See also [`Self::into_parts`] to recover the fields
363    pub fn try_new(
364        data_type: DataType,
365        len: usize,
366        null_bit_buffer: Option<Buffer>,
367        offset: usize,
368        buffers: Vec<Buffer>,
369        child_data: Vec<ArrayData>,
370    ) -> Result<Self, ArrowError> {
371        let builder = Self::inner_new_builder(
372            data_type,
373            len,
374            None,
375            null_bit_buffer,
376            offset,
377            buffers,
378            child_data,
379        );
380
381        assert!(!builder.skip_validation.get());
382
383        // As the data is not trusted, do a full validation of its contents
384        // We don't need to validate children as we can assume that the
385        // [`ArrayData`] in `child_data` have already been validated through
386        // a call to `ArrayData::try_new` or created using unsafe
387        builder.build()
388    }
389
390    fn inner_new_builder(
391        data_type: DataType,
392        len: usize,
393        null_count: Option<usize>,
394        null_bit_buffer: Option<Buffer>,
395        offset: usize,
396        buffers: Vec<Buffer>,
397        child_data: Vec<ArrayData>,
398    ) -> ArrayDataBuilder {
399        ArrayDataBuilder {
400            data_type,
401            len,
402            null_count,
403            null_bit_buffer,
404            nulls: None,
405            offset,
406            buffers,
407            child_data,
408            align_buffers: false,
409            skip_validation: UnsafeFlag::new(),
410        }
411    }
412
413    /// Return the constituent parts of this ArrayData
414    ///
415    /// This is the inverse of [`ArrayData::try_new`].
416    ///
417    /// Returns `(data_type, len, nulls, offset, buffers, child_data)`
418    pub fn into_parts(
419        self,
420    ) -> (
421        DataType,
422        usize,
423        Option<NullBuffer>,
424        usize,
425        Vec<Buffer>,
426        Vec<ArrayData>,
427    ) {
428        let Self {
429            data_type,
430            len,
431            nulls,
432            offset,
433            buffers,
434            child_data,
435        } = self;
436
437        (data_type, len, nulls, offset, buffers, child_data)
438    }
439
440    /// Returns a builder to construct a [`ArrayData`] instance of the same [`DataType`]
441    #[inline]
442    pub const fn builder(data_type: DataType) -> ArrayDataBuilder {
443        ArrayDataBuilder::new(data_type)
444    }
445
446    /// Returns a reference to the [`DataType`] of this [`ArrayData`]
447    #[inline]
448    pub const fn data_type(&self) -> &DataType {
449        &self.data_type
450    }
451
452    /// Returns the [`Buffer`] storing data for this [`ArrayData`]
453    pub fn buffers(&self) -> &[Buffer] {
454        &self.buffers
455    }
456
457    /// Returns a slice of children [`ArrayData`]. This will be non
458    /// empty for type such as lists and structs.
459    ///
460    /// Note: For nested types where the parent element `i` corresponds directly
461    /// to child element `i` (such as structs), both the parent's offset and
462    /// each child's own offset apply when locating child values — see
463    /// [`Self::offset`] for details.
464    pub fn child_data(&self) -> &[ArrayData] {
465        &self.child_data[..]
466    }
467
468    /// Returns whether the element at index `i` is null
469    #[inline]
470    pub fn is_null(&self, i: usize) -> bool {
471        match &self.nulls {
472            Some(v) => v.is_null(i),
473            None => false,
474        }
475    }
476
477    /// Returns a reference to the null buffer of this [`ArrayData`] if any
478    ///
479    /// Note: [`ArrayData::offset`] does NOT apply to the returned [`NullBuffer`]
480    #[inline]
481    pub fn nulls(&self) -> Option<&NullBuffer> {
482        self.nulls.as_ref()
483    }
484
485    /// Returns whether the element at index `i` is not null
486    #[inline]
487    pub fn is_valid(&self, i: usize) -> bool {
488        !self.is_null(i)
489    }
490
491    /// Returns the length (i.e., number of elements) of this [`ArrayData`].
492    #[inline]
493    pub const fn len(&self) -> usize {
494        self.len
495    }
496
497    /// Returns whether this [`ArrayData`] is empty
498    #[inline]
499    pub const fn is_empty(&self) -> bool {
500        self.len == 0
501    }
502
503    /// Returns the offset in elements of this [`ArrayData`]
504    ///
505    /// The offset applies to [`Self::buffers`] and [`Self::child_data`],
506    /// but does NOT apply to [`Self::nulls`], which always represents exactly
507    /// [`Self::len`] elements.
508    ///
509    /// # Offsets for Non-nested types
510    ///
511    /// For non-nested types, the offset skips leading elements in the buffers.
512    /// Logical element `i` is stored at physical position `offset + i`.
513    ///
514    /// For example, with `offset = 2` and `len = 3` the following array
515    /// represents elements `[C, D, E]`:
516    ///
517    /// ```text
518    ///                     offset: 2        len: 3
519    ///                   ◀───────────▶◀────────────────▶
520    ///                   ┌─────┬─────┬─────┬─────┬─────┬─────┐
521    ///    values buffer  │  A  │  B  │  C  │  D  │  E  │  F  │
522    ///                   └─────┴─────┴─────┴─────┴─────┴─────┘
523    ///    physical index    0     1     2     3     4     5
524    ///    logical index                 0     1     2
525    /// ```
526    ///
527    /// # Offsets for Struct types
528    ///
529    /// For [struct]s, logical element `i` of the parent corresponds directly to
530    /// element `i` of each child, with no indirection in between. Since a
531    /// struct has no buffers of its own, its offset applies to each child,
532    /// composing cumulatively with any child offset. Logical element `i` of the
533    /// struct corresponds to element `offset + i` of each child.
534    ///
535    /// For example, a struct with `offset = 2` and `len = 3` whose children
536    /// `c1` and `c2` themselves each have an offset of `1` represents the
537    /// elements `{c1: D, c2: d}`, `{c1: E, c2: e}`, `{c1: F, c2: f}`:
538    ///
539    /// ```text
540    ///                        struct offset: 2    len: 3
541    ///                          ◀───────────▶◀────────────────▶
542    ///    child offset: 1 ◀─────▶
543    ///                    ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
544    ///    child c1        │  A  │  B  │  C  │  D  │  E  │  F  │  G  │
545    ///                    ├─────┼─────┼─────┼─────┼─────┼─────┼─────┤
546    ///    child c2        │  a  │  b  │  c  │  d  │  e  │  f  │  g  │
547    ///                    └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
548    ///    physical index     0     1     2     3     4     5     6
549    ///    child index              0     1     2     3     4     5
550    ///    struct index                         0     1     2
551    /// ```
552    ///
553    /// [struct]: https://arrow.apache.org/docs/format/Columnar.html#struct-layout
554    #[inline]
555    pub const fn offset(&self) -> usize {
556        self.offset
557    }
558
559    /// Returns the total number of nulls in this array
560    #[inline]
561    pub fn null_count(&self) -> usize {
562        self.nulls
563            .as_ref()
564            .map(|x| x.null_count())
565            .unwrap_or_default()
566    }
567
568    /// Returns the total number of bytes of memory occupied by the
569    /// buffers owned by this [`ArrayData`] and all of its
570    /// children. (See also diagram on [`ArrayData`]).
571    ///
572    /// Note that this [`ArrayData`] may only refer to a subset of the
573    /// data in the underlying [`Buffer`]s (due to `offset` and
574    /// `length`), but the size returned includes the entire size of
575    /// the buffers.
576    ///
577    /// If multiple [`ArrayData`]s refer to the same underlying
578    /// [`Buffer`]s they will both report the same size.
579    pub fn get_buffer_memory_size(&self) -> usize {
580        let mut size = 0;
581        for buffer in &self.buffers {
582            size += buffer.capacity();
583        }
584        if let Some(bitmap) = &self.nulls {
585            size += bitmap.buffer().capacity()
586        }
587        for child in &self.child_data {
588            size += child.get_buffer_memory_size();
589        }
590        size
591    }
592
593    /// Returns the total number of the bytes of memory occupied by
594    /// the buffers by this slice of [`ArrayData`] (See also diagram on [`ArrayData`]).
595    ///
596    /// This is approximately the number of bytes if a new
597    /// [`ArrayData`] was formed by creating new [`Buffer`]s with
598    /// exactly the data needed. For variadic layouts, this includes the full
599    /// capacity of every variadic buffer retained by a zero-copy slice, without
600    /// inspecting which buffers or ranges are referenced by the slice.
601    ///
602    /// For example, a [`DataType::Int64`] with `100` elements,
603    /// [`Self::get_slice_memory_size`] would return `100 * 8 = 800`. If
604    /// the [`ArrayData`] was then [`Self::slice`]ed to refer to its
605    /// first `20` elements, then [`Self::get_slice_memory_size`] on the
606    /// sliced [`ArrayData`] would return `20 * 8 = 160`.
607    pub fn get_slice_memory_size(&self) -> Result<usize, ArrowError> {
608        let mut result: usize = 0;
609        let layout = layout(&self.data_type);
610
611        for spec in &layout.buffers {
612            match spec {
613                BufferSpec::FixedWidth { byte_width, .. } => {
614                    // Offset buffers contain len+1 elements: one boundary per element
615                    // plus a final boundary marking the end of the last element.
616                    let len = match self.data_type {
617                        DataType::Utf8
618                        | DataType::LargeUtf8
619                        | DataType::Binary
620                        | DataType::LargeBinary
621                        | DataType::List(_)
622                        | DataType::LargeList(_)
623                        | DataType::Map(_, _) => self.len + 1,
624                        _ => self.len,
625                    };
626                    let buffer_size = len.checked_mul(*byte_width).ok_or_else(|| {
627                        ArrowError::ComputeError(
628                            "Integer overflow computing buffer size".to_string(),
629                        )
630                    })?;
631                    result += buffer_size;
632                }
633                BufferSpec::VariableWidth => {
634                    let buffer_len = match self.data_type {
635                        DataType::Utf8 | DataType::Binary => {
636                            let offsets = self.typed_offsets::<i32>()?;
637                            (offsets[self.len] - offsets[0]) as usize
638                        }
639                        DataType::LargeUtf8 | DataType::LargeBinary => {
640                            let offsets = self.typed_offsets::<i64>()?;
641                            (offsets[self.len] - offsets[0]) as usize
642                        }
643                        _ => {
644                            return Err(ArrowError::NotYetImplemented(format!(
645                                "Invalid data type for VariableWidth buffer. Expected Utf8, LargeUtf8, Binary or LargeBinary. Got {}",
646                                self.data_type
647                            )));
648                        }
649                    };
650                    result += buffer_len;
651                }
652                BufferSpec::BitMap => {
653                    let buffer_size = bit_util::ceil(self.len, 8);
654                    result += buffer_size;
655                }
656                BufferSpec::AlwaysNull => {
657                    // Nothing to do
658                }
659            }
660        }
661
662        if layout.variadic {
663            // Slicing view arrays retains all variadic data buffers unchanged.
664            for buffer in self.buffers.iter().skip(layout.buffers.len()) {
665                result += buffer.capacity();
666            }
667        }
668
669        if self.nulls().is_some() {
670            result += bit_util::ceil(self.len, 8);
671        }
672
673        for child in &self.child_data {
674            result += child.get_slice_memory_size()?;
675        }
676        Ok(result)
677    }
678
679    /// Returns the total number of bytes of memory occupied
680    /// physically by this [`ArrayData`] and all its [`Buffer`]s and
681    /// children. (See also diagram on [`ArrayData`]).
682    ///
683    /// Equivalent to:
684    ///  `size_of_val(self)` +
685    ///  [`Self::get_buffer_memory_size`] +
686    ///  `size_of_val(child)` for all children
687    pub fn get_array_memory_size(&self) -> usize {
688        let mut size = mem::size_of_val(self);
689
690        // Calculate rest of the fields top down which contain actual data
691        for buffer in &self.buffers {
692            size += mem::size_of::<Buffer>();
693            size += buffer.capacity();
694        }
695        if let Some(nulls) = &self.nulls {
696            size += nulls.buffer().capacity();
697        }
698        for child in &self.child_data {
699            size += child.get_array_memory_size();
700        }
701
702        size
703    }
704
705    /// Creates a zero-copy slice of itself. This creates a new
706    /// [`ArrayData`] pointing at the same underlying [`Buffer`]s with a
707    /// different offset and len
708    ///
709    /// # Panics
710    ///
711    /// Panics if `offset + length` overflows or is greater than `self.len()`.
712    pub fn slice(&self, offset: usize, length: usize) -> ArrayData {
713        self.clone().sliced(offset, length)
714    }
715
716    /// Creates a zero-copy slice of this array, reusing its buffer and child allocations.
717    ///
718    /// This is equivalent to [`Self::slice`], but consumes `self`.
719    ///
720    /// # Panics
721    ///
722    /// Panics if `offset + length` overflows or is greater than `self.len()`.
723    pub fn sliced(mut self, offset: usize, length: usize) -> Self {
724        self.slice_in_place(offset, length);
725        self
726    }
727
728    fn slice_in_place(&mut self, offset: usize, length: usize) {
729        let end = offset
730            .checked_add(length)
731            .expect("offset + length overflow");
732        assert!(end <= self.len());
733
734        if let DataType::Struct(_) = self.data_type() {
735            // A struct has no buffers of its own, and reading child element `i`
736            // combines this array's offset with the child's own offset. Applying
737            // the slice to both would count it twice, so the cumulative offset
738            // goes to the children and this array's offset is reset to 0.
739            let child_offset = self.offset + offset;
740            for child in &mut self.child_data {
741                child.slice_in_place(child_offset, length);
742            }
743            self.offset = 0;
744        } else {
745            self.offset += offset;
746        }
747        self.len = length;
748        // `nulls` belongs to this array rather than to the children, so
749        // it is sliced by `offset` alone.
750        self.nulls = self.nulls.as_ref().map(|x| x.slice(offset, length));
751    }
752
753    /// Returns the `buffer` as a slice of type `T` starting at self.offset
754    ///
755    /// # Panics
756    /// This function panics if:
757    /// * the buffer is not byte-aligned with type T, or
758    /// * the datatype is `Boolean` (it corresponds to a bit-packed buffer where the offset is not applicable)
759    pub fn buffer<T: ArrowNativeType>(&self, buffer: usize) -> &[T] {
760        &self.buffers()[buffer].typed_data()[self.offset..]
761    }
762
763    /// Returns a new [`ArrayData`] valid for `data_type` containing `len` null values
764    ///
765    /// # Panics
766    /// This function panics if:
767    /// * the datatype `data_type` has incorrect layout
768    pub fn new_null(data_type: &DataType, len: usize) -> Self {
769        let bit_len = bit_util::ceil(len, 8);
770        let zeroed = |len: usize| Buffer::from(MutableBuffer::from_len_zeroed(len));
771
772        let (buffers, child_data, has_nulls) = match data_type.primitive_width() {
773            Some(width) => (vec![zeroed(width * len)], vec![], true),
774            None => match data_type {
775                DataType::Null => (vec![], vec![], false),
776                DataType::Boolean => (vec![zeroed(bit_len)], vec![], true),
777                DataType::Binary | DataType::Utf8 => {
778                    (vec![zeroed((len + 1) * 4), zeroed(0)], vec![], true)
779                }
780                DataType::BinaryView | DataType::Utf8View => (vec![zeroed(len * 16)], vec![], true),
781                DataType::LargeBinary | DataType::LargeUtf8 => {
782                    (vec![zeroed((len + 1) * 8), zeroed(0)], vec![], true)
783                }
784                DataType::FixedSizeBinary(i) => {
785                    if *i < 0 {
786                        panic!("cannot construct null data from FixedSizeBinary({i})");
787                    }
788                    (vec![zeroed(*i as usize * len)], vec![], true)
789                }
790                DataType::List(f) | DataType::Map(f, _) => (
791                    vec![zeroed((len + 1) * 4)],
792                    vec![ArrayData::new_empty(f.data_type())],
793                    true,
794                ),
795                DataType::LargeList(f) => (
796                    vec![zeroed((len + 1) * 8)],
797                    vec![ArrayData::new_empty(f.data_type())],
798                    true,
799                ),
800                DataType::ListView(f) => (
801                    vec![zeroed(len * 4), zeroed(len * 4)],
802                    vec![ArrayData::new_empty(f.data_type())],
803                    true,
804                ),
805                DataType::LargeListView(f) => (
806                    vec![zeroed(len * 8), zeroed(len * 8)],
807                    vec![ArrayData::new_empty(f.data_type())],
808                    true,
809                ),
810                DataType::FixedSizeList(f, list_len) => (
811                    vec![],
812                    vec![ArrayData::new_null(f.data_type(), *list_len as usize * len)],
813                    true,
814                ),
815                DataType::Struct(fields) => (
816                    vec![],
817                    fields
818                        .iter()
819                        .map(|f| Self::new_null(f.data_type(), len))
820                        .collect(),
821                    true,
822                ),
823                DataType::Dictionary(k, v) => (
824                    vec![zeroed(k.primitive_width().unwrap() * len)],
825                    vec![ArrayData::new_empty(v.as_ref())],
826                    true,
827                ),
828                DataType::Union(f, mode) => match f.iter().next() {
829                    // Every slot carries a type id naming one of the children,
830                    // so an empty union has nothing to put in a slot and can
831                    // only be the empty array.
832                    None => {
833                        assert_eq!(
834                            len, 0,
835                            "cannot construct null data from an empty union of length {len}, a slot has no type id to carry"
836                        );
837                        let buffers = match mode {
838                            UnionMode::Sparse => vec![zeroed(0)],
839                            UnionMode::Dense => vec![zeroed(0), zeroed(0)],
840                        };
841                        (buffers, vec![], false)
842                    }
843                    Some((id, _)) => {
844                        let ids = Buffer::from_iter(std::iter::repeat_n(id, len));
845                        let buffers = match mode {
846                            UnionMode::Sparse => vec![ids],
847                            UnionMode::Dense => {
848                                let end_offset = i32::from_usize(len).unwrap();
849                                vec![ids, Buffer::from_iter(0_i32..end_offset)]
850                            }
851                        };
852
853                        let children = f
854                            .iter()
855                            .enumerate()
856                            .map(|(idx, (_, f))| {
857                                if idx == 0 || *mode == UnionMode::Sparse {
858                                    Self::new_null(f.data_type(), len)
859                                } else {
860                                    Self::new_empty(f.data_type())
861                                }
862                            })
863                            .collect();
864
865                        (buffers, children, false)
866                    }
867                },
868                DataType::RunEndEncoded(r, v) => {
869                    if len == 0 {
870                        // For empty arrays, create zero-length child arrays.
871                        let runs = ArrayData::new_empty(r.data_type());
872                        let values = ArrayData::new_empty(v.data_type());
873                        (vec![], vec![runs, values], false)
874                    } else {
875                        let runs = match r.data_type() {
876                            DataType::Int16 => {
877                                let i = i16::from_usize(len).expect("run overflow");
878                                Buffer::from_slice_ref([i])
879                            }
880                            DataType::Int32 => {
881                                let i = i32::from_usize(len).expect("run overflow");
882                                Buffer::from_slice_ref([i])
883                            }
884                            DataType::Int64 => {
885                                let i = i64::from_usize(len).expect("run overflow");
886                                Buffer::from_slice_ref([i])
887                            }
888                            dt => unreachable!("Invalid run ends data type {dt}"),
889                        };
890
891                        let builder = ArrayData::builder(r.data_type().clone())
892                            .len(1)
893                            .buffers(vec![runs]);
894
895                        // SAFETY:
896                        // Valid by construction
897                        let runs = unsafe { builder.build_unchecked() };
898                        (
899                            vec![],
900                            vec![runs, ArrayData::new_null(v.data_type(), 1)],
901                            false,
902                        )
903                    }
904                }
905                // Handled by Some(width) branch above
906                DataType::Int8
907                | DataType::Int16
908                | DataType::Int32
909                | DataType::Int64
910                | DataType::UInt8
911                | DataType::UInt16
912                | DataType::UInt32
913                | DataType::UInt64
914                | DataType::Float16
915                | DataType::Float32
916                | DataType::Float64
917                | DataType::Timestamp(_, _)
918                | DataType::Date32
919                | DataType::Date64
920                | DataType::Time32(_)
921                | DataType::Time64(_)
922                | DataType::Duration(_)
923                | DataType::Interval(_)
924                | DataType::Decimal32(_, _)
925                | DataType::Decimal64(_, _)
926                | DataType::Decimal128(_, _)
927                | DataType::Decimal256(_, _) => unreachable!("{data_type}"),
928            },
929        };
930
931        let mut builder = ArrayDataBuilder::new(data_type.clone())
932            .len(len)
933            .buffers(buffers)
934            .child_data(child_data);
935
936        if has_nulls {
937            builder = builder.nulls(Some(NullBuffer::new_null(len)))
938        }
939
940        // SAFETY:
941        // Data valid by construction
942        unsafe { builder.build_unchecked() }
943    }
944
945    /// Returns a new empty [ArrayData] valid for `data_type`.
946    pub fn new_empty(data_type: &DataType) -> Self {
947        Self::new_null(data_type, 0)
948    }
949
950    /// Verifies that the buffers meet the minimum alignment requirements for the data type
951    ///
952    /// Buffers that are not adequately aligned will be copied to a new aligned allocation
953    ///
954    /// This can be useful for when interacting with data sent over IPC or FFI, that may
955    /// not meet the minimum alignment requirements
956    ///
957    /// This also aligns buffers of children data
958    pub fn align_buffers(&mut self) {
959        let layout = layout(&self.data_type);
960        for (buffer, spec) in self.buffers.iter_mut().zip(&layout.buffers) {
961            if let BufferSpec::FixedWidth { alignment, .. } = spec
962                && buffer.as_ptr().align_offset(*alignment) != 0
963            {
964                *buffer = Buffer::from_slice_ref(buffer.as_ref());
965            }
966        }
967        // align children data recursively
968        for data in &mut self.child_data {
969            data.align_buffers()
970        }
971    }
972
973    /// "cheap" validation of an `ArrayData`. Ensures buffers are
974    /// sufficiently sized to store `len` + `offset` total elements of
975    /// `data_type` and performs other inexpensive consistency checks.
976    ///
977    /// This check is "cheap" in the sense that it does not validate the
978    /// contents of the buffers (e.g. that all offsets for UTF8 arrays
979    /// are within the bounds of the values buffer).
980    ///
981    /// See [ArrayData::validate_data] to validate fully the offset content
982    /// and the validity of utf8 data
983    pub fn validate(&self) -> Result<(), ArrowError> {
984        // Need at least this much space in each buffer
985        let len_plus_offset = checked_len_plus_offset(&self.data_type, self.len, self.offset)?;
986
987        // Check that the data layout conforms to the spec
988        let layout = layout(&self.data_type);
989
990        if !layout.can_contain_null_mask && self.nulls.is_some() {
991            return Err(ArrowError::InvalidArgumentError(format!(
992                "Arrays of type {:?} cannot contain a null bitmask",
993                self.data_type,
994            )));
995        }
996
997        // Check data buffers length for view types and other types
998        if self.buffers.len() < layout.buffers.len()
999            || (!layout.variadic && self.buffers.len() != layout.buffers.len())
1000        {
1001            return Err(ArrowError::InvalidArgumentError(format!(
1002                "Expected {} buffers in array of type {:?}, got {}",
1003                layout.buffers.len(),
1004                self.data_type,
1005                self.buffers.len(),
1006            )));
1007        }
1008
1009        for (i, (buffer, spec)) in self.buffers.iter().zip(layout.buffers.iter()).enumerate() {
1010            match spec {
1011                BufferSpec::FixedWidth {
1012                    byte_width,
1013                    alignment,
1014                } => {
1015                    let min_buffer_size = len_plus_offset.saturating_mul(*byte_width);
1016
1017                    if buffer.len() < min_buffer_size {
1018                        return Err(ArrowError::InvalidArgumentError(format!(
1019                            "Need at least {} bytes in buffers[{}] in array of type {:?}, but got {}",
1020                            min_buffer_size,
1021                            i,
1022                            self.data_type,
1023                            buffer.len()
1024                        )));
1025                    }
1026
1027                    let align_offset = buffer.as_ptr().align_offset(*alignment);
1028                    if align_offset != 0 {
1029                        return Err(ArrowError::InvalidArgumentError(format!(
1030                            "Misaligned buffers[{i}] in array of type {:?}, offset from expected alignment of {alignment} by {}",
1031                            self.data_type,
1032                            align_offset.min(alignment - align_offset)
1033                        )));
1034                    }
1035                }
1036                BufferSpec::VariableWidth => {
1037                    // not cheap to validate (need to look at the
1038                    // data). Partially checked in validate_offsets
1039                    // called below. Can check with `validate_full`
1040                }
1041                BufferSpec::BitMap => {
1042                    let min_buffer_size = bit_util::ceil(len_plus_offset, 8);
1043                    if buffer.len() < min_buffer_size {
1044                        return Err(ArrowError::InvalidArgumentError(format!(
1045                            "Need at least {} bytes for bitmap in buffers[{}] in array of type {:?}, but got {}",
1046                            min_buffer_size,
1047                            i,
1048                            self.data_type,
1049                            buffer.len()
1050                        )));
1051                    }
1052                }
1053                BufferSpec::AlwaysNull => {
1054                    // Nothing to validate
1055                }
1056            }
1057        }
1058
1059        // check null bit buffer size
1060        if let Some(nulls) = self.nulls() {
1061            if nulls.null_count() > self.len {
1062                return Err(ArrowError::InvalidArgumentError(format!(
1063                    "null_count {} for an array exceeds length of {} elements",
1064                    nulls.null_count(),
1065                    self.len
1066                )));
1067            }
1068
1069            if nulls.len() != self.len {
1070                return Err(ArrowError::InvalidArgumentError(format!(
1071                    "null buffer incorrect size. got {} expected {}",
1072                    nulls.len(),
1073                    self.len
1074                )));
1075            }
1076        }
1077
1078        self.validate_child_data()?;
1079
1080        // Additional Type specific checks
1081        match &self.data_type {
1082            DataType::Utf8 | DataType::Binary => {
1083                self.validate_offsets::<i32>(self.buffers[1].len())?;
1084            }
1085            DataType::LargeUtf8 | DataType::LargeBinary => {
1086                self.validate_offsets::<i64>(self.buffers[1].len())?;
1087            }
1088            DataType::Dictionary(key_type, _value_type) => {
1089                // At the moment, constructing a DictionaryArray will also check this
1090                if !DataType::is_dictionary_key_type(key_type) {
1091                    return Err(ArrowError::InvalidArgumentError(format!(
1092                        "Dictionary key type must be integer, but was {key_type}"
1093                    )));
1094                }
1095            }
1096            DataType::RunEndEncoded(run_ends_type, _) => {
1097                if run_ends_type.is_nullable() {
1098                    return Err(ArrowError::InvalidArgumentError(
1099                        "The nullable should be set to false for the field defining run_ends array.".to_string()
1100                    ));
1101                }
1102                if !DataType::is_run_ends_type(run_ends_type.data_type()) {
1103                    return Err(ArrowError::InvalidArgumentError(format!(
1104                        "RunArray run_ends types must be Int16, Int32 or Int64, but was {}",
1105                        run_ends_type.data_type()
1106                    )));
1107                }
1108            }
1109            DataType::Map(f, _) if f.is_nullable() => {
1110                return Err(ArrowError::InvalidArgumentError(
1111                    "The nullable should be set to false for the map entries field.".to_string(),
1112                ));
1113            }
1114            _ => {}
1115        }
1116
1117        Ok(())
1118    }
1119
1120    /// Returns a reference to the data in `buffer` as a typed slice
1121    /// (typically `&[i32]` or `&[i64]`) after validating. The
1122    /// returned slice is guaranteed to have at least `self.len + 1`
1123    /// entries.
1124    ///
1125    /// For an empty array, the `buffer` can also be empty.
1126    fn typed_offsets<T: ArrowNativeType + num_traits::Num>(&self) -> Result<&[T], ArrowError> {
1127        // An empty list-like array can have 0 offsets
1128        if self.len == 0 && self.buffer_at(0)?.is_empty() {
1129            return Ok(&[]);
1130        }
1131
1132        let len = checked_len_plus_offset(&self.data_type, self.len, 1)?;
1133
1134        self.typed_buffer(0, len)
1135    }
1136
1137    /// Returns a reference to the data in `buffers[idx]` as a typed slice after validating
1138    fn typed_buffer<T: ArrowNativeType + num_traits::Num>(
1139        &self,
1140        idx: usize,
1141        len: usize,
1142    ) -> Result<&[T], ArrowError> {
1143        let buffer = self.buffer_at(idx)?;
1144
1145        let required_elements = checked_len_plus_offset(&self.data_type, len, self.offset)?;
1146        let byte_width = mem::size_of::<T>();
1147        let required_len = required_elements.checked_mul(byte_width).ok_or_else(|| {
1148            ArrowError::InvalidArgumentError(format!(
1149                "Buffer {idx} of {} byte length overflow: {} elements of {} bytes exceeds usize",
1150                self.data_type, required_elements, byte_width
1151            ))
1152        })?;
1153
1154        if buffer.len() < required_len {
1155            return Err(ArrowError::InvalidArgumentError(format!(
1156                "Buffer {} of {} isn't large enough. Expected {} bytes got {}",
1157                idx,
1158                self.data_type,
1159                required_len,
1160                buffer.len()
1161            )));
1162        }
1163
1164        // Only the bytes in use are typed: the buffer may be longer than
1165        // `required_len` by a number of bytes that is not a multiple of
1166        // `byte_width`, which `Buffer::typed_data` would assert on.
1167        let bytes = &buffer.as_slice()[..required_len];
1168        // SAFETY: ArrowNativeType is trivially transmutable and sealed (as in
1169        // `Buffer::typed_data`); alignment is checked below
1170        let (prefix, values, suffix) = unsafe { bytes.align_to::<T>() };
1171        if !prefix.is_empty() || !suffix.is_empty() {
1172            return Err(ArrowError::InvalidArgumentError(format!(
1173                "Buffer {idx} of {} is not aligned to {} bytes",
1174                self.data_type,
1175                mem::align_of::<T>()
1176            )));
1177        }
1178        Ok(&values[self.offset..])
1179    }
1180
1181    /// Does a cheap sanity check that the `self.len` values in `buffer` are valid
1182    /// offsets (of type T) into some other buffer of `values_length` bytes long
1183    fn validate_offsets<T: ArrowNativeType + num_traits::Num + std::fmt::Display>(
1184        &self,
1185        values_length: usize,
1186    ) -> Result<(), ArrowError> {
1187        // Justification: buffer size was validated above
1188        let offsets = self.typed_offsets::<T>()?;
1189        if offsets.is_empty() {
1190            return Ok(());
1191        }
1192
1193        let first_offset = offsets[0].to_usize().ok_or_else(|| {
1194            ArrowError::InvalidArgumentError(format!(
1195                "Error converting offset[0] ({}) to usize for {}",
1196                offsets[0], self.data_type
1197            ))
1198        })?;
1199
1200        let last_offset = offsets[self.len].to_usize().ok_or_else(|| {
1201            ArrowError::InvalidArgumentError(format!(
1202                "Error converting offset[{}] ({}) to usize for {}",
1203                self.len, offsets[self.len], self.data_type
1204            ))
1205        })?;
1206
1207        if first_offset > values_length {
1208            return Err(ArrowError::InvalidArgumentError(format!(
1209                "First offset {} of {} is larger than values length {}",
1210                first_offset, self.data_type, values_length,
1211            )));
1212        }
1213
1214        if last_offset > values_length {
1215            return Err(ArrowError::InvalidArgumentError(format!(
1216                "Last offset {} of {} is larger than values length {}",
1217                last_offset, self.data_type, values_length,
1218            )));
1219        }
1220
1221        if first_offset > last_offset {
1222            return Err(ArrowError::InvalidArgumentError(format!(
1223                "First offset {} in {} is smaller than last offset {}",
1224                first_offset, self.data_type, last_offset,
1225            )));
1226        }
1227
1228        Ok(())
1229    }
1230
1231    /// Does a cheap sanity check that the `self.len` values in `buffer` are valid
1232    /// offsets and sizes (of type T) into some other buffer of `values_length` bytes long
1233    fn validate_offsets_and_sizes<T: ArrowNativeType + num_traits::Num + std::fmt::Display>(
1234        &self,
1235        values_length: usize,
1236    ) -> Result<(), ArrowError> {
1237        let offsets: &[T] = self.typed_buffer(0, self.len)?;
1238        let sizes: &[T] = self.typed_buffer(1, self.len)?;
1239        if offsets.len() != sizes.len() {
1240            return Err(ArrowError::ComputeError(format!(
1241                "ListView offsets len {} does not match sizes len {}",
1242                offsets.len(),
1243                sizes.len()
1244            )));
1245        }
1246
1247        for i in 0..sizes.len() {
1248            let size = sizes[i].to_usize().ok_or_else(|| {
1249                ArrowError::InvalidArgumentError(format!(
1250                    "Error converting size[{}] ({}) to usize for {}",
1251                    i, sizes[i], self.data_type
1252                ))
1253            })?;
1254            let offset = offsets[i].to_usize().ok_or_else(|| {
1255                ArrowError::InvalidArgumentError(format!(
1256                    "Error converting offset[{}] ({}) to usize for {}",
1257                    i, offsets[i], self.data_type
1258                ))
1259            })?;
1260            if size
1261                .checked_add(offset)
1262                .expect("Offset and size have exceeded the usize boundary")
1263                > values_length
1264            {
1265                return Err(ArrowError::InvalidArgumentError(format!(
1266                    "Size {} at index {} is larger than the remaining values for {}",
1267                    size, i, self.data_type
1268                )));
1269            }
1270        }
1271        Ok(())
1272    }
1273
1274    /// Validates the layout of `child_data` ArrayData structures
1275    fn validate_child_data(&self) -> Result<(), ArrowError> {
1276        match &self.data_type {
1277            DataType::List(field) => {
1278                let values_data = self.get_single_valid_child_data(field.data_type())?;
1279                self.validate_offsets::<i32>(values_data.len)?;
1280            }
1281            DataType::LargeList(field) => {
1282                let values_data = self.get_single_valid_child_data(field.data_type())?;
1283                self.validate_offsets::<i64>(values_data.len)?;
1284            }
1285            DataType::Map(field, _) => {
1286                let DataType::Struct(entries_fields) = field.data_type() else {
1287                    return Err(ArrowError::InvalidArgumentError(format!(
1288                        "Map field should be a entries struct data type, got {:?} instead",
1289                        field.data_type()
1290                    )));
1291                };
1292                if entries_fields.len() != 2 {
1293                    return Err(ArrowError::InvalidArgumentError(format!(
1294                        "Map entries data type should be a struct containing 2 fields, got {} fields",
1295                        entries_fields.len()
1296                    )));
1297                }
1298
1299                // Key field
1300                if entries_fields[0].is_nullable() {
1301                    return Err(ArrowError::InvalidArgumentError(
1302                        "Map key field must not be nullable".to_string(),
1303                    ));
1304                }
1305                let values_data = self.get_single_valid_child_data(field.data_type())?;
1306                self.validate_offsets::<i32>(values_data.len)?;
1307            }
1308            DataType::ListView(field) => {
1309                let values_data = self.get_single_valid_child_data(field.data_type())?;
1310                self.validate_offsets_and_sizes::<i32>(values_data.len)?;
1311            }
1312            DataType::LargeListView(field) => {
1313                let values_data = self.get_single_valid_child_data(field.data_type())?;
1314                self.validate_offsets_and_sizes::<i64>(values_data.len)?;
1315            }
1316            DataType::FixedSizeList(field, list_size) => {
1317                let values_data = self.get_single_valid_child_data(field.data_type())?;
1318
1319                let list_size: usize = (*list_size).try_into().map_err(|_| {
1320                    ArrowError::InvalidArgumentError(format!(
1321                        "{} has a negative list_size {}",
1322                        self.data_type, list_size
1323                    ))
1324                })?;
1325
1326                let len_plus_offset =
1327                    checked_len_plus_offset(&self.data_type, self.len, self.offset)?;
1328                let expected_values_len = len_plus_offset.checked_mul(list_size).ok_or_else(|| {
1329                    ArrowError::InvalidArgumentError(format!(
1330                        "Integer overflow computing expected number of values in {}: length + offset ({}) multiplied by list size ({}) exceeds usize",
1331                        self.data_type, len_plus_offset, list_size
1332                    ))
1333                })?;
1334
1335                if values_data.len < expected_values_len {
1336                    return Err(ArrowError::InvalidArgumentError(format!(
1337                        "Values length {} is less than the length + offset ({}) multiplied by the value size ({}) for {}",
1338                        values_data.len, len_plus_offset, list_size, self.data_type
1339                    )));
1340                }
1341            }
1342            DataType::Struct(fields) => {
1343                self.validate_num_child_data(fields.len())?;
1344                let len_plus_offset =
1345                    checked_len_plus_offset(&self.data_type, self.len, self.offset)?;
1346                for (i, field) in fields.iter().enumerate() {
1347                    let field_data = self.get_valid_child_data(i, field.data_type())?;
1348
1349                    // Ensure child field has sufficient size
1350                    if field_data.len < len_plus_offset {
1351                        return Err(ArrowError::InvalidArgumentError(format!(
1352                            "{} child array #{} for field {} has length smaller than expected for struct array ({} < {})",
1353                            self.data_type,
1354                            i,
1355                            field.name(),
1356                            field_data.len,
1357                            len_plus_offset
1358                        )));
1359                    }
1360                }
1361            }
1362            DataType::RunEndEncoded(run_ends_field, values_field) => {
1363                // See the `RunArray` invariants for the rules enforced here and
1364                // in `check_run_ends`:
1365                // https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len
1366                self.validate_num_child_data(2)?;
1367                let run_ends_data = self.get_valid_child_data(0, run_ends_field.data_type())?;
1368                let values_data = self.get_valid_child_data(1, values_field.data_type())?;
1369                if run_ends_data.len != values_data.len {
1370                    return Err(ArrowError::InvalidArgumentError(format!(
1371                        "The run_ends array length should be the same as values array length. Run_ends array length is {}, values array length is {}",
1372                        run_ends_data.len, values_data.len
1373                    )));
1374                }
1375                if run_ends_data.nulls.is_some() {
1376                    return Err(ArrowError::InvalidArgumentError(
1377                        "Found null values in run_ends array. The run_ends array should not have null values.".to_string(),
1378                    ));
1379                }
1380            }
1381            DataType::Union(fields, mode) => {
1382                self.validate_num_child_data(fields.len())?;
1383
1384                for (i, (_, field)) in fields.iter().enumerate() {
1385                    let field_data = self.get_valid_child_data(i, field.data_type())?;
1386
1387                    if mode == &UnionMode::Sparse {
1388                        let len_plus_offset =
1389                            checked_len_plus_offset(&self.data_type, self.len, self.offset)?;
1390                        if field_data.len < len_plus_offset {
1391                            return Err(ArrowError::InvalidArgumentError(format!(
1392                                "Sparse union child array #{} has length smaller than expected for union array ({} < {})",
1393                                i, field_data.len, len_plus_offset
1394                            )));
1395                        }
1396                    }
1397                }
1398            }
1399            DataType::Dictionary(_key_type, value_type) => {
1400                self.get_single_valid_child_data(value_type)?;
1401            }
1402            _ => {
1403                // other types do not have child data
1404                if !self.child_data.is_empty() {
1405                    return Err(ArrowError::InvalidArgumentError(format!(
1406                        "Expected no child arrays for type {} but got {}",
1407                        self.data_type,
1408                        self.child_data.len()
1409                    )));
1410                }
1411            }
1412        }
1413        Ok(())
1414    }
1415
1416    /// Ensures that this array data has a single child_data with the
1417    /// expected type, and calls `validate()` on it. Returns a
1418    /// reference to that child_data
1419    fn get_single_valid_child_data(
1420        &self,
1421        expected_type: &DataType,
1422    ) -> Result<&ArrayData, ArrowError> {
1423        self.validate_num_child_data(1)?;
1424        self.get_valid_child_data(0, expected_type)
1425    }
1426
1427    /// Returns `buffers[idx]`, or an error if there is no such buffer.
1428    ///
1429    /// [`Self::validate_values`] can be called on its own, without the buffer counts
1430    /// having been checked by [`Self::validate`] first, so the index may be missing.
1431    fn buffer_at(&self, idx: usize) -> Result<&Buffer, ArrowError> {
1432        self.buffers.get(idx).ok_or_else(|| {
1433            ArrowError::InvalidArgumentError(format!(
1434                "{} should contain at least {} buffer(s), had {}",
1435                self.data_type,
1436                idx + 1,
1437                self.buffers.len()
1438            ))
1439        })
1440    }
1441
1442    /// Returns `child_data[idx]`, or an error if there is no such child.
1443    ///
1444    /// [`Self::validate_values`] can be called on its own, without the child counts
1445    /// having been checked by [`Self::validate`] first, so the index may be missing.
1446    fn child_at(&self, idx: usize) -> Result<&ArrayData, ArrowError> {
1447        self.child_data.get(idx).ok_or_else(|| {
1448            ArrowError::InvalidArgumentError(format!(
1449                "{} should contain at least {} child data array(s), had {}",
1450                self.data_type,
1451                idx + 1,
1452                self.child_data.len()
1453            ))
1454        })
1455    }
1456
1457    /// Returns `Err` if self.child_data does not have exactly `expected_len` elements
1458    fn validate_num_child_data(&self, expected_len: usize) -> Result<(), ArrowError> {
1459        if self.child_data.len() != expected_len {
1460            Err(ArrowError::InvalidArgumentError(format!(
1461                "Value data for {} should contain {} child data array(s), had {}",
1462                self.data_type,
1463                expected_len,
1464                self.child_data.len()
1465            )))
1466        } else {
1467            Ok(())
1468        }
1469    }
1470
1471    /// Ensures that `child_data[i]` has the expected type, calls
1472    /// `validate()` on it, and returns a reference to that child_data
1473    fn get_valid_child_data(
1474        &self,
1475        i: usize,
1476        expected_type: &DataType,
1477    ) -> Result<&ArrayData, ArrowError> {
1478        let values_data = self.child_data.get(i).ok_or_else(|| {
1479            ArrowError::InvalidArgumentError(format!(
1480                "{} did not have enough child arrays. Expected at least {} but had only {}",
1481                self.data_type,
1482                i + 1,
1483                self.child_data.len()
1484            ))
1485        })?;
1486
1487        if expected_type != &values_data.data_type {
1488            return Err(ArrowError::InvalidArgumentError(format!(
1489                "Child type mismatch for {}. Expected {} but child data had {}",
1490                self.data_type, expected_type, values_data.data_type
1491            )));
1492        }
1493
1494        values_data.validate()?;
1495        Ok(values_data)
1496    }
1497
1498    /// Validate that the data contained within this [`ArrayData`] is valid
1499    ///
1500    /// 1. Null count is correct
1501    /// 2. All offsets are valid
1502    /// 3. All String data is valid UTF-8
1503    /// 4. All dictionary offsets are valid
1504    ///
1505    /// Internally this calls:
1506    ///
1507    /// * [`Self::validate`]
1508    /// * [`Self::validate_nulls`]
1509    /// * [`Self::validate_values`]
1510    ///
1511    /// Note: this does not recurse into children, for a recursive variant
1512    /// see [`Self::validate_full`]
1513    pub fn validate_data(&self) -> Result<(), ArrowError> {
1514        self.validate()?;
1515
1516        self.validate_nulls()?;
1517        self.validate_values()?;
1518        Ok(())
1519    }
1520
1521    /// Performs a full recursive validation of this [`ArrayData`] and all its children
1522    ///
1523    /// This is equivalent to calling [`Self::validate_data`] on this [`ArrayData`]
1524    /// and all its children recursively
1525    pub fn validate_full(&self) -> Result<(), ArrowError> {
1526        self.validate_data()?;
1527        // validate all children recursively
1528        self.child_data
1529            .iter()
1530            .enumerate()
1531            .try_for_each(|(i, child_data)| {
1532                child_data.validate_full().map_err(|e| {
1533                    ArrowError::InvalidArgumentError(format!(
1534                        "{} child #{} invalid: {}",
1535                        self.data_type, i, e
1536                    ))
1537                })
1538            })?;
1539        Ok(())
1540    }
1541
1542    /// Validates the values stored within this [`ArrayData`] are valid
1543    /// without recursing into child [`ArrayData`]
1544    ///
1545    /// Does not (yet) check
1546    /// 1. Union type_ids are valid see [#85](https://github.com/apache/arrow-rs/issues/85)
1547    /// 2. the null count is correct and that any
1548    /// 3. nullability requirements of its children are correct
1549    ///
1550    /// [#85]: https://github.com/apache/arrow-rs/issues/85
1551    pub fn validate_nulls(&self) -> Result<(), ArrowError> {
1552        if let Some(nulls) = &self.nulls {
1553            let actual = nulls.len() - nulls.inner().count_set_bits();
1554            if actual != nulls.null_count() {
1555                return Err(ArrowError::InvalidArgumentError(format!(
1556                    "null_count value ({}) doesn't match actual number of nulls in array ({})",
1557                    nulls.null_count(),
1558                    actual
1559                )));
1560            }
1561        }
1562
1563        // In general non-nullable children should not contain nulls, however, for certain
1564        // types, such as StructArray and FixedSizeList, nulls in the parent take up
1565        // space in the child. As such we permit nulls in the children in the corresponding
1566        // positions for such types
1567        match &self.data_type {
1568            DataType::List(f) | DataType::LargeList(f) | DataType::Map(f, _) => {
1569                if !f.is_nullable() {
1570                    let child = &self.child_data[0];
1571                    self.validate_non_nullable(None, child, child.nulls())?
1572                }
1573            }
1574            DataType::FixedSizeList(field, len) => {
1575                let child = &self.child_data[0];
1576                if !field.is_nullable() {
1577                    let element_len = *len as usize;
1578                    let child_nulls = child.nulls().map(|nulls| {
1579                        nulls.slice(self.offset * element_len, self.len * element_len)
1580                    });
1581                    let expanded = self.nulls.as_ref().map(|nulls| nulls.expand(element_len));
1582                    self.validate_non_nullable(expanded.as_ref(), child, child_nulls.as_ref())?;
1583                }
1584            }
1585            DataType::Struct(fields) => {
1586                for (field, child) in fields.iter().zip(&self.child_data) {
1587                    if !field.is_nullable() {
1588                        let child_nulls = child
1589                            .nulls()
1590                            .map(|nulls| nulls.slice(self.offset, self.len));
1591                        self.validate_non_nullable(self.nulls(), child, child_nulls.as_ref())?
1592                    }
1593                }
1594            }
1595            _ => {}
1596        }
1597
1598        Ok(())
1599    }
1600
1601    /// Verifies that `child` contains no nulls not present in `mask`
1602    fn validate_non_nullable(
1603        &self,
1604        mask: Option<&NullBuffer>,
1605        child: &ArrayData,
1606        child_nulls: Option<&NullBuffer>,
1607    ) -> Result<(), ArrowError> {
1608        let Some(mask) = mask else {
1609            return match child_nulls.map(NullBuffer::null_count).unwrap_or_default() {
1610                0 => Ok(()),
1611                _ => Err(ArrowError::InvalidArgumentError(format!(
1612                    "non-nullable child of type {} contains nulls not present in parent {}",
1613                    child.data_type, self.data_type
1614                ))),
1615            };
1616        };
1617
1618        match child_nulls {
1619            Some(nulls) if !mask.contains(nulls) => Err(ArrowError::InvalidArgumentError(format!(
1620                "non-nullable child of type {} contains nulls not present in parent",
1621                child.data_type
1622            ))),
1623            _ => Ok(()),
1624        }
1625    }
1626
1627    /// Validates the values stored within this [`ArrayData`] are valid
1628    /// without recursing into child [`ArrayData`]
1629    ///
1630    /// Does not (yet) check
1631    /// 1. Union type_ids are valid see [#85](https://github.com/apache/arrow-rs/issues/85)
1632    pub fn validate_values(&self) -> Result<(), ArrowError> {
1633        match &self.data_type {
1634            DataType::Utf8 => self.validate_utf8::<i32>(),
1635            DataType::LargeUtf8 => self.validate_utf8::<i64>(),
1636            DataType::Binary => self.validate_offsets_full::<i32>(self.buffer_at(1)?.len()),
1637            DataType::LargeBinary => self.validate_offsets_full::<i64>(self.buffer_at(1)?.len()),
1638            DataType::BinaryView => {
1639                let views = self.typed_buffer::<u128>(0, self.len)?;
1640                validate_binary_view(views, &self.buffers[1..])
1641            }
1642            DataType::Utf8View => {
1643                let views = self.typed_buffer::<u128>(0, self.len)?;
1644                validate_string_view(views, &self.buffers[1..])
1645            }
1646            DataType::List(_) | DataType::Map(_, _) => {
1647                let child = self.child_at(0)?;
1648                self.validate_offsets_full::<i32>(child.len)
1649            }
1650            DataType::LargeList(_) => {
1651                let child = self.child_at(0)?;
1652                self.validate_offsets_full::<i64>(child.len)
1653            }
1654            DataType::Union(fields, mode) => {
1655                let mut child_lens: Vec<Option<usize>> = vec![None; 128];
1656                for (index, (type_id, _)) in fields.iter().enumerate() {
1657                    let child = self.child_at(index)?;
1658                    child_lens[type_id as usize] = Some(child.len());
1659                }
1660
1661                // Type id values must match one of the fields.
1662                let type_ids = self.typed_buffer::<i8>(0, self.len)?;
1663                for (index, &type_id) in type_ids.iter().enumerate() {
1664                    if type_id < 0 {
1665                        return Err(ArrowError::InvalidArgumentError(format!(
1666                            "Type id values cannot be negative, got {type_id} at index {index}"
1667                        )));
1668                    }
1669                    let type_id = type_id as usize;
1670                    if child_lens[type_id].is_none() {
1671                        return Err(ArrowError::InvalidArgumentError(format!(
1672                            "Type id values must match one of the field type ids, got {type_id} at index {index}"
1673                        )));
1674                    }
1675                }
1676
1677                // Check the value offsets are in bounds.
1678                if mode == &UnionMode::Dense {
1679                    let offsets = self.typed_buffer::<i32>(1, self.len)?;
1680
1681                    if type_ids
1682                        .iter()
1683                        .zip(offsets.iter())
1684                        .any(|(&type_id, &offset)| {
1685                            offset < 0 || offset as usize >= child_lens[type_id as usize].unwrap()
1686                        })
1687                    {
1688                        return Err(ArrowError::InvalidArgumentError(
1689                            "Offsets must be non-negative and within the length of the child array"
1690                                .to_string(),
1691                        ));
1692                    }
1693                }
1694
1695                Ok(())
1696            }
1697            DataType::Dictionary(key_type, _value_type) => {
1698                let dictionary_length = self.child_at(0)?.len;
1699                let dictionary_length = i64::try_from(dictionary_length).map_err(|_| {
1700                    ArrowError::InvalidArgumentError(format!(
1701                        "Dictionary of {dictionary_length} values is too long for an i64"
1702                    ))
1703                })?;
1704                let max_value = dictionary_length - 1;
1705                match key_type.as_ref() {
1706                    DataType::UInt8 => self.check_bounds::<u8>(max_value),
1707                    DataType::UInt16 => self.check_bounds::<u16>(max_value),
1708                    DataType::UInt32 => self.check_bounds::<u32>(max_value),
1709                    DataType::UInt64 => self.check_bounds::<u64>(max_value),
1710                    DataType::Int8 => self.check_bounds::<i8>(max_value),
1711                    DataType::Int16 => self.check_bounds::<i16>(max_value),
1712                    DataType::Int32 => self.check_bounds::<i32>(max_value),
1713                    DataType::Int64 => self.check_bounds::<i64>(max_value),
1714                    _ => Err(ArrowError::InvalidArgumentError(format!(
1715                        "Dictionary key type must be an integer, got {key_type}"
1716                    ))),
1717                }
1718            }
1719            DataType::RunEndEncoded(run_ends, _values) => {
1720                let len_plus_offset =
1721                    checked_len_plus_offset(&self.data_type, self.len, self.offset)?;
1722                let run_ends_data = self.child_at(0)?;
1723                match run_ends.data_type() {
1724                    DataType::Int16 => {
1725                        run_ends_data.check_run_ends::<i16>(self.len, len_plus_offset)
1726                    }
1727                    DataType::Int32 => {
1728                        run_ends_data.check_run_ends::<i32>(self.len, len_plus_offset)
1729                    }
1730                    DataType::Int64 => {
1731                        run_ends_data.check_run_ends::<i64>(self.len, len_plus_offset)
1732                    }
1733                    data_type => Err(ArrowError::InvalidArgumentError(format!(
1734                        "Run end type must be Int16, Int32 or Int64, got {data_type}"
1735                    ))),
1736                }
1737            }
1738            _ => {
1739                // No extra validation check required for other types
1740                Ok(())
1741            }
1742        }
1743    }
1744
1745    /// Calls the `validate(item_index, range)` function for each of
1746    /// the ranges specified in the arrow offsets buffer of type
1747    /// `T`. Also validates that each offset is smaller than
1748    /// `offset_limit`
1749    ///
1750    /// For an empty array, the offsets buffer can either be empty
1751    /// or contain a single `0`.
1752    ///
1753    /// For example, the offsets buffer contained `[1, 2, 4]`, this
1754    /// function would call `validate([1,2])`, and `validate([2,4])`
1755    fn validate_each_offset<T, V>(&self, offset_limit: usize, validate: V) -> Result<(), ArrowError>
1756    where
1757        T: ArrowNativeType + TryInto<usize> + num_traits::Num + std::fmt::Display,
1758        V: Fn(usize, Range<usize>) -> Result<(), ArrowError>,
1759    {
1760        self.typed_offsets::<T>()?
1761            .iter()
1762            .enumerate()
1763            .map(|(i, x)| {
1764                // check if the offset can be converted to usize
1765                let r = x.to_usize().ok_or_else(|| {
1766                    ArrowError::InvalidArgumentError(format!(
1767                        "Offset invariant failure: Could not convert offset {x} to usize at position {i}"))}
1768                    );
1769                // check if the offset exceeds the limit
1770                match r {
1771                    Ok(n) if n <= offset_limit => Ok((i, n)),
1772                    Ok(_) => Err(ArrowError::InvalidArgumentError(format!(
1773                        "Offset invariant failure: offset at position {i} out of bounds: {x} > {offset_limit}"))
1774                    ),
1775                    Err(e) => Err(e),
1776                }
1777            })
1778            .scan(0_usize, |start, end| {
1779                // check offsets are monotonically increasing
1780                match end {
1781                    Ok((i, end)) if *start <= end => {
1782                        let range = Some(Ok((i, *start..end)));
1783                        *start = end;
1784                        range
1785                    }
1786                    Ok((i, end)) => Some(Err(ArrowError::InvalidArgumentError(format!(
1787                        "Offset invariant failure: non-monotonic offset at slot {}: {} > {}",
1788                        i - 1, start, end))
1789                    )),
1790                    Err(err) => Some(Err(err)),
1791                }
1792            })
1793            .skip(1) // the first element is meaningless
1794            .try_for_each(|res: Result<(usize, Range<usize>), ArrowError>| {
1795                let (item_index, range) = res?;
1796                validate(item_index-1, range)
1797            })
1798    }
1799
1800    /// Ensures that all strings formed by the offsets in `buffers[0]`
1801    /// into `buffers[1]` are valid utf8 sequences. Bytes of `buffers[1]`
1802    /// outside the range of the offsets are not checked.
1803    fn validate_utf8<T>(&self) -> Result<(), ArrowError>
1804    where
1805        T: ArrowNativeType + TryInto<usize> + num_traits::Num + std::fmt::Display,
1806    {
1807        let values_buffer = &self.buffer_at(1)?.as_slice();
1808        let offsets = self.typed_offsets::<T>()?;
1809        if let Some((first, last, values_str)) = utf8_span(offsets, values_buffer) {
1810            self.validate_each_offset::<T, _>(values_buffer.len(), |string_index, range| {
1811                // `values_str` ends at the last offset. Checking each pair of offsets doesn't
1812                // show that `range.end <= last`: a later offset can still be smaller, which
1813                // `validate_each_offset` reports when it gets there.
1814                if range.end > last {
1815                    return Ok(());
1816                }
1817                let (start, end) = (range.start - first, range.end - first);
1818                if !values_str.is_char_boundary(start) || !values_str.is_char_boundary(end) {
1819                    return Err(ArrowError::InvalidArgumentError(format!(
1820                        "incomplete utf-8 byte sequence from index {string_index}"
1821                    )));
1822                }
1823                Ok(())
1824            })
1825        } else {
1826            // Find specific offset that failed utf8 validation
1827            self.validate_each_offset::<T, _>(values_buffer.len(), |string_index, range| {
1828                std::str::from_utf8(&values_buffer[range.clone()]).map_err(|e| {
1829                    ArrowError::InvalidArgumentError(format!(
1830                        "Invalid UTF8 sequence at string index {string_index} ({range:?}): {e}"
1831                    ))
1832                })?;
1833                Ok(())
1834            })
1835        }
1836    }
1837
1838    /// Ensures that all offsets in `buffers[0]` into `buffers[1]` are
1839    /// between `0` and `offset_limit`
1840    fn validate_offsets_full<T>(&self, offset_limit: usize) -> Result<(), ArrowError>
1841    where
1842        T: ArrowNativeType + TryInto<usize> + num_traits::Num + std::fmt::Display,
1843    {
1844        self.validate_each_offset::<T, _>(offset_limit, |_string_index, _range| {
1845            // No validation applied to each value, but the iteration
1846            // itself applies bounds checking to each range
1847            Ok(())
1848        })
1849    }
1850
1851    /// Validates that each value in self.buffers (typed as T)
1852    /// is within the range [0, max_value], inclusive
1853    fn check_bounds<T>(&self, max_value: i64) -> Result<(), ArrowError>
1854    where
1855        T: ArrowNativeType + TryInto<i64> + num_traits::Num + std::fmt::Display,
1856    {
1857        // `validate()` checks the buffer size too, but `validate_values()` can be called
1858        // on its own, so do not assume it has run.
1859        let indexes: &[T] = self.typed_buffer::<T>(0, self.len)?;
1860
1861        indexes.iter().enumerate().try_for_each(|(i, &dict_index)| {
1862            // Do not check the value is null (value can be arbitrary)
1863            if self.is_null(i) {
1864                return Ok(());
1865            }
1866            let dict_index: i64 = dict_index.try_into().map_err(|_| {
1867                ArrowError::InvalidArgumentError(format!(
1868                    "Value at position {i} out of bounds: {dict_index} (can not convert to i64)"
1869                ))
1870            })?;
1871
1872            if dict_index < 0 || dict_index > max_value {
1873                return Err(ArrowError::InvalidArgumentError(format!(
1874                    "Value at position {i} out of bounds: {dict_index} (should be in [0, {max_value}])"
1875                )));
1876            }
1877            Ok(())
1878        })
1879    }
1880
1881    /// Validates that each value in run_ends array is positive and strictly
1882    /// increasing, and that the last value covers the parent's `offset + len`
1883    /// (when the parent is non-empty), as required by the [`RunArray` invariants].
1884    ///
1885    /// [`RunArray` invariants]: https://docs.rs/arrow/latest/arrow/array/struct.RunArray.html#offset-and-len
1886    fn check_run_ends<T>(
1887        &self,
1888        parent_len: usize,
1889        parent_len_plus_offset: usize,
1890    ) -> Result<(), ArrowError>
1891    where
1892        T: ArrowNativeType + TryInto<i64> + num_traits::Num + std::fmt::Display,
1893    {
1894        let values = self.typed_buffer::<T>(0, self.len)?;
1895        let mut prev_value = 0_i64;
1896        values.iter().enumerate().try_for_each(|(ix, &inp_value)| {
1897            let value: i64 = inp_value.try_into().map_err(|_| {
1898                ArrowError::InvalidArgumentError(format!(
1899                    "Value at position {ix} out of bounds: {inp_value} (can not convert to i64)"
1900                ))
1901            })?;
1902            if value <= 0_i64 {
1903                return Err(ArrowError::InvalidArgumentError(format!(
1904                    "The values in run_ends array should be strictly positive. Found value {value} at index {ix} that does not match the criteria."
1905                )));
1906            }
1907            if ix > 0 && value <= prev_value {
1908                return Err(ArrowError::InvalidArgumentError(format!(
1909                    "The values in run_ends array should be strictly increasing. Found value {value} at index {ix} with previous value {prev_value} that does not match the criteria."
1910                )));
1911            }
1912
1913            prev_value = value;
1914            Ok(())
1915        })?;
1916
1917        if parent_len > 0 && prev_value.as_usize() < parent_len_plus_offset {
1918            return Err(ArrowError::InvalidArgumentError(format!(
1919                "The offset + length of array should be less or equal to last value in the run_ends array. The last value of run_ends array is {prev_value} and offset + length of array is {parent_len_plus_offset}."
1920            )));
1921        }
1922        Ok(())
1923    }
1924
1925    /// Returns true if this `ArrayData` is equal to `other`, using pointer comparisons
1926    /// to determine buffer equality. This is cheaper than `PartialEq::eq` but may
1927    /// return false when the arrays are logically equal
1928    pub fn ptr_eq(&self, other: &Self) -> bool {
1929        if self.offset != other.offset
1930            || self.len != other.len
1931            || self.data_type != other.data_type
1932            || self.buffers.len() != other.buffers.len()
1933            || self.child_data.len() != other.child_data.len()
1934        {
1935            return false;
1936        }
1937
1938        match (&self.nulls, &other.nulls) {
1939            (Some(a), Some(b)) if !a.inner().ptr_eq(b.inner()) => return false,
1940            (Some(_), None) | (None, Some(_)) => return false,
1941            _ => {}
1942        }
1943
1944        if !self
1945            .buffers
1946            .iter()
1947            .zip(other.buffers.iter())
1948            .all(|(a, b)| a.as_ptr() == b.as_ptr())
1949        {
1950            return false;
1951        }
1952
1953        self.child_data
1954            .iter()
1955            .zip(other.child_data.iter())
1956            .all(|(a, b)| a.ptr_eq(b))
1957    }
1958
1959    /// Converts this [`ArrayData`] into an [`ArrayDataBuilder`]
1960    pub fn into_builder(self) -> ArrayDataBuilder {
1961        self.into()
1962    }
1963
1964    /// Claim memory used by this ArrayData in the provided memory pool.
1965    ///
1966    /// This claims memory for:
1967    /// - All buffers in self.buffers
1968    /// - All child ArrayData recursively
1969    /// - The null buffer if present
1970    #[cfg(feature = "pool")]
1971    pub fn claim(&self, pool: &dyn arrow_buffer::MemoryPool) {
1972        // Claim all data buffers
1973        for buffer in &self.buffers {
1974            buffer.claim(pool);
1975        }
1976
1977        // Claim null buffer if present
1978        if let Some(nulls) = &self.nulls {
1979            nulls.claim(pool);
1980        }
1981
1982        // Recursively claim child data
1983        for child in &self.child_data {
1984            child.claim(pool);
1985        }
1986    }
1987}
1988
1989/// Return the expected [`DataTypeLayout`] Arrays of this data
1990/// type are expected to have
1991pub fn layout(data_type: &DataType) -> DataTypeLayout {
1992    // based on C/C++ implementation in
1993    // https://github.com/apache/arrow/blob/661c7d749150905a63dd3b52e0a04dac39030d95/cpp/src/arrow/type.h (and .cc)
1994    use arrow_schema::IntervalUnit::*;
1995
1996    match data_type {
1997        DataType::Null => DataTypeLayout {
1998            buffers: vec![],
1999            can_contain_null_mask: false,
2000            variadic: false,
2001        },
2002        DataType::Boolean => DataTypeLayout {
2003            buffers: vec![BufferSpec::BitMap],
2004            can_contain_null_mask: true,
2005            variadic: false,
2006        },
2007        DataType::Int8 => DataTypeLayout::new_fixed_width::<i8>(),
2008        DataType::Int16 => DataTypeLayout::new_fixed_width::<i16>(),
2009        DataType::Int32 => DataTypeLayout::new_fixed_width::<i32>(),
2010        DataType::Int64 => DataTypeLayout::new_fixed_width::<i64>(),
2011        DataType::UInt8 => DataTypeLayout::new_fixed_width::<u8>(),
2012        DataType::UInt16 => DataTypeLayout::new_fixed_width::<u16>(),
2013        DataType::UInt32 => DataTypeLayout::new_fixed_width::<u32>(),
2014        DataType::UInt64 => DataTypeLayout::new_fixed_width::<u64>(),
2015        DataType::Float16 => DataTypeLayout::new_fixed_width::<half::f16>(),
2016        DataType::Float32 => DataTypeLayout::new_fixed_width::<f32>(),
2017        DataType::Float64 => DataTypeLayout::new_fixed_width::<f64>(),
2018        DataType::Timestamp(_, _) => DataTypeLayout::new_fixed_width::<i64>(),
2019        DataType::Date32 => DataTypeLayout::new_fixed_width::<i32>(),
2020        DataType::Date64 => DataTypeLayout::new_fixed_width::<i64>(),
2021        DataType::Time32(_) => DataTypeLayout::new_fixed_width::<i32>(),
2022        DataType::Time64(_) => DataTypeLayout::new_fixed_width::<i64>(),
2023        DataType::Interval(YearMonth) => DataTypeLayout::new_fixed_width::<i32>(),
2024        DataType::Interval(DayTime) => DataTypeLayout::new_fixed_width::<IntervalDayTime>(),
2025        DataType::Interval(MonthDayNano) => {
2026            DataTypeLayout::new_fixed_width::<IntervalMonthDayNano>()
2027        }
2028        DataType::Duration(_) => DataTypeLayout::new_fixed_width::<i64>(),
2029        DataType::Decimal32(_, _) => DataTypeLayout::new_fixed_width::<i32>(),
2030        DataType::Decimal64(_, _) => DataTypeLayout::new_fixed_width::<i64>(),
2031        DataType::Decimal128(_, _) => DataTypeLayout::new_fixed_width::<i128>(),
2032        DataType::Decimal256(_, _) => DataTypeLayout::new_fixed_width::<i256>(),
2033        DataType::FixedSizeBinary(size) => {
2034            let spec = BufferSpec::FixedWidth {
2035                byte_width: (*size).try_into().unwrap(),
2036                alignment: mem::align_of::<u8>(),
2037            };
2038            DataTypeLayout {
2039                buffers: vec![spec],
2040                can_contain_null_mask: true,
2041                variadic: false,
2042            }
2043        }
2044        DataType::Binary => DataTypeLayout::new_binary::<i32>(),
2045        DataType::LargeBinary => DataTypeLayout::new_binary::<i64>(),
2046        DataType::Utf8 => DataTypeLayout::new_binary::<i32>(),
2047        DataType::LargeUtf8 => DataTypeLayout::new_binary::<i64>(),
2048        DataType::BinaryView | DataType::Utf8View => DataTypeLayout::new_view(),
2049        DataType::FixedSizeList(_, _) => DataTypeLayout::new_nullable_empty(), // all in child data
2050        DataType::List(_) => DataTypeLayout::new_fixed_width::<i32>(),
2051        DataType::ListView(_) => DataTypeLayout::new_list_view::<i32>(),
2052        DataType::LargeListView(_) => DataTypeLayout::new_list_view::<i64>(),
2053        DataType::LargeList(_) => DataTypeLayout::new_fixed_width::<i64>(),
2054        DataType::Map(_, _) => DataTypeLayout::new_fixed_width::<i32>(),
2055        DataType::Struct(_) => DataTypeLayout::new_nullable_empty(), // all in child data,
2056        DataType::RunEndEncoded(_, _) => DataTypeLayout::new_empty(), // all in child data,
2057        DataType::Union(_, mode) => {
2058            let type_ids = BufferSpec::FixedWidth {
2059                byte_width: mem::size_of::<i8>(),
2060                alignment: mem::align_of::<i8>(),
2061            };
2062
2063            DataTypeLayout {
2064                buffers: match mode {
2065                    UnionMode::Sparse => {
2066                        vec![type_ids]
2067                    }
2068                    UnionMode::Dense => {
2069                        vec![
2070                            type_ids,
2071                            BufferSpec::FixedWidth {
2072                                byte_width: mem::size_of::<i32>(),
2073                                alignment: mem::align_of::<i32>(),
2074                            },
2075                        ]
2076                    }
2077                },
2078                can_contain_null_mask: false,
2079                variadic: false,
2080            }
2081        }
2082        DataType::Dictionary(key_type, _value_type) => layout(key_type),
2083    }
2084}
2085
2086/// Layout specification for a data type
2087#[derive(Debug, PartialEq, Eq)]
2088// Note: Follows structure from C++: https://github.com/apache/arrow/blob/master/cpp/src/arrow/type.h#L91
2089pub struct DataTypeLayout {
2090    /// A vector of buffer layout specifications, one for each expected buffer
2091    pub buffers: Vec<BufferSpec>,
2092
2093    /// Can contain a null bitmask
2094    pub can_contain_null_mask: bool,
2095
2096    /// This field only applies to the view type [`DataType::BinaryView`] and [`DataType::Utf8View`]
2097    /// If `variadic` is true, the number of buffers expected is only lower-bounded by
2098    /// buffers.len(). Buffers that exceed the lower bound are legal.
2099    pub variadic: bool,
2100}
2101
2102impl DataTypeLayout {
2103    /// Describes a basic numeric array where each element has type `T`
2104    pub fn new_fixed_width<T>() -> Self {
2105        Self {
2106            buffers: vec![BufferSpec::FixedWidth {
2107                byte_width: mem::size_of::<T>(),
2108                alignment: mem::align_of::<T>(),
2109            }],
2110            can_contain_null_mask: true,
2111            variadic: false,
2112        }
2113    }
2114
2115    /// Describes arrays which have no data of their own
2116    /// but may still have a Null Bitmap (e.g. FixedSizeList)
2117    pub fn new_nullable_empty() -> Self {
2118        Self {
2119            buffers: vec![],
2120            can_contain_null_mask: true,
2121            variadic: false,
2122        }
2123    }
2124
2125    /// Describes arrays which have no data of their own
2126    /// (e.g. RunEndEncoded).
2127    pub fn new_empty() -> Self {
2128        Self {
2129            buffers: vec![],
2130            can_contain_null_mask: false,
2131            variadic: false,
2132        }
2133    }
2134
2135    /// Describes a basic numeric array where each element has a fixed
2136    /// with offset buffer of type `T`, followed by a
2137    /// variable width data buffer
2138    pub fn new_binary<T>() -> Self {
2139        Self {
2140            buffers: vec![
2141                // offsets
2142                BufferSpec::FixedWidth {
2143                    byte_width: mem::size_of::<T>(),
2144                    alignment: mem::align_of::<T>(),
2145                },
2146                // values
2147                BufferSpec::VariableWidth,
2148            ],
2149            can_contain_null_mask: true,
2150            variadic: false,
2151        }
2152    }
2153
2154    /// Describes a view type
2155    pub fn new_view() -> Self {
2156        Self {
2157            buffers: vec![BufferSpec::FixedWidth {
2158                byte_width: mem::size_of::<u128>(),
2159                alignment: mem::align_of::<u128>(),
2160            }],
2161            can_contain_null_mask: true,
2162            variadic: true,
2163        }
2164    }
2165
2166    /// Describes a list view type
2167    pub fn new_list_view<T>() -> Self {
2168        Self {
2169            buffers: vec![
2170                BufferSpec::FixedWidth {
2171                    byte_width: mem::size_of::<T>(),
2172                    alignment: mem::align_of::<T>(),
2173                },
2174                BufferSpec::FixedWidth {
2175                    byte_width: mem::size_of::<T>(),
2176                    alignment: mem::align_of::<T>(),
2177                },
2178            ],
2179            can_contain_null_mask: true,
2180            variadic: false,
2181        }
2182    }
2183}
2184
2185/// Layout specification for a single data type buffer
2186#[derive(Debug, PartialEq, Eq)]
2187pub enum BufferSpec {
2188    /// Each element is a fixed width primitive, with the given `byte_width` and `alignment`
2189    ///
2190    /// `alignment` is the alignment required by Rust for an array of the corresponding primitive,
2191    /// see [`Layout::array`](std::alloc::Layout::array) and [`std::mem::align_of`].
2192    ///
2193    /// Arrow-rs requires that all buffers have at least this alignment, to allow for
2194    /// [slice](std::slice) based APIs. Alignment in excess of this is not required to allow
2195    /// for array slicing and interoperability with `Vec`, which cannot be over-aligned.
2196    ///
2197    /// Note that these alignment requirements will vary between architectures
2198    FixedWidth {
2199        /// The width of each element in bytes
2200        byte_width: usize,
2201        /// The alignment required by Rust for an array of the corresponding primitive
2202        alignment: usize,
2203    },
2204    /// Variable width, such as string data for utf8 data
2205    VariableWidth,
2206    /// Buffer holds a bitmap.
2207    ///
2208    /// Note: Unlike the C++ implementation, the null/validity buffer
2209    /// is handled specially rather than as another of the buffers in
2210    /// the spec, so this variant is only used for the Boolean type.
2211    BitMap,
2212    /// Buffer is always null. Unused currently in Rust implementation,
2213    /// (used in C++ for Union type)
2214    AlwaysNull,
2215}
2216
2217impl PartialEq for ArrayData {
2218    fn eq(&self, other: &Self) -> bool {
2219        equal::equal(self, other)
2220    }
2221}
2222
2223/// A boolean flag that cannot be mutated outside of unsafe code.
2224///
2225/// Defaults to a value of false.
2226///
2227/// This structure is used to enforce safety in the [`ArrayDataBuilder`]
2228///
2229/// [`ArrayDataBuilder`]: super::ArrayDataBuilder
2230///
2231/// # Example
2232/// ```rust
2233/// use arrow_data::UnsafeFlag;
2234/// assert!(!UnsafeFlag::default().get()); // default is false
2235/// let mut flag = UnsafeFlag::new();
2236/// assert!(!flag.get()); // defaults to false
2237/// // can only set it to true in unsafe code
2238/// unsafe { flag.set(true) };
2239/// assert!(flag.get()); // now true
2240/// ```
2241#[derive(Debug, Clone)]
2242#[doc(hidden)]
2243pub struct UnsafeFlag(bool);
2244
2245impl UnsafeFlag {
2246    /// Creates a new `UnsafeFlag` with the value set to `false`.
2247    ///
2248    /// See examples on [`Self::new`]
2249    #[inline]
2250    pub const fn new() -> Self {
2251        Self(false)
2252    }
2253
2254    /// Sets the value of the flag to the given value
2255    ///
2256    /// Note this can purposely only be done in `unsafe` code
2257    ///
2258    /// # Safety
2259    ///
2260    /// If set, the flag will be set to the given value. There is nothing
2261    /// immediately unsafe about doing so, however, the flag can be used to
2262    /// subsequently bypass safety checks in the [`ArrayDataBuilder`].
2263    #[inline]
2264    pub unsafe fn set(&mut self, val: bool) {
2265        self.0 = val;
2266    }
2267
2268    /// Returns the value of the flag
2269    #[inline]
2270    pub fn get(&self) -> bool {
2271        self.0
2272    }
2273}
2274
2275// Manual impl to make it clear you can not construct unsafe with true
2276impl Default for UnsafeFlag {
2277    fn default() -> Self {
2278        Self::new()
2279    }
2280}
2281
2282/// Builder for [`ArrayData`] type
2283#[derive(Debug)]
2284pub struct ArrayDataBuilder {
2285    data_type: DataType,
2286    len: usize,
2287    null_count: Option<usize>,
2288    null_bit_buffer: Option<Buffer>,
2289    nulls: Option<NullBuffer>,
2290    offset: usize,
2291    buffers: Vec<Buffer>,
2292    child_data: Vec<ArrayData>,
2293    /// Should buffers be realigned (copying if necessary)?
2294    ///
2295    /// Defaults to false.
2296    align_buffers: bool,
2297    /// Should data validation be skipped for this [`ArrayData`]?
2298    ///
2299    /// Defaults to false.
2300    ///
2301    /// # Safety
2302    ///
2303    /// This flag can only be set to true using `unsafe` APIs. However, once true
2304    /// subsequent calls to `build()` may result in undefined behavior if the data
2305    /// is not valid.
2306    skip_validation: UnsafeFlag,
2307}
2308
2309impl ArrayDataBuilder {
2310    #[inline]
2311    /// Creates a new array data builder
2312    pub const fn new(data_type: DataType) -> Self {
2313        Self {
2314            data_type,
2315            len: 0,
2316            null_count: None,
2317            null_bit_buffer: None,
2318            nulls: None,
2319            offset: 0,
2320            buffers: vec![],
2321            child_data: vec![],
2322            align_buffers: false,
2323            skip_validation: UnsafeFlag::new(),
2324        }
2325    }
2326
2327    /// Creates a new array data builder from an existing one, changing the data type
2328    pub fn data_type(self, data_type: DataType) -> Self {
2329        Self { data_type, ..self }
2330    }
2331
2332    #[inline]
2333    /// Sets the length of the [ArrayData]
2334    pub const fn len(mut self, n: usize) -> Self {
2335        self.len = n;
2336        self
2337    }
2338
2339    /// Sets the null buffer of the [ArrayData]
2340    pub fn nulls(mut self, nulls: Option<NullBuffer>) -> Self {
2341        self.nulls = nulls;
2342        self.null_count = None;
2343        self.null_bit_buffer = None;
2344        self
2345    }
2346
2347    /// Sets the null count of the [ArrayData]
2348    pub fn null_count(mut self, null_count: usize) -> Self {
2349        self.null_count = Some(null_count);
2350        self
2351    }
2352
2353    /// Sets the `null_bit_buffer` of the [ArrayData]
2354    pub fn null_bit_buffer(mut self, buf: Option<Buffer>) -> Self {
2355        self.nulls = None;
2356        self.null_bit_buffer = buf;
2357        self
2358    }
2359
2360    /// Sets the offset of the [ArrayData]
2361    #[inline]
2362    pub const fn offset(mut self, n: usize) -> Self {
2363        self.offset = n;
2364        self
2365    }
2366
2367    /// Sets the buffers of the [ArrayData]
2368    pub fn buffers(mut self, v: Vec<Buffer>) -> Self {
2369        self.buffers = v;
2370        self
2371    }
2372
2373    /// Adds a single buffer to the [ArrayData]'s buffers
2374    pub fn add_buffer(mut self, b: Buffer) -> Self {
2375        self.buffers.push(b);
2376        self
2377    }
2378
2379    /// Adds multiple buffers to the [ArrayData]'s buffers
2380    pub fn add_buffers<I: IntoIterator<Item = Buffer>>(mut self, bs: I) -> Self {
2381        self.buffers.extend(bs);
2382        self
2383    }
2384
2385    /// Sets the child data of the [ArrayData]
2386    pub fn child_data(mut self, v: Vec<ArrayData>) -> Self {
2387        self.child_data = v;
2388        self
2389    }
2390
2391    /// Adds a single child data to the [ArrayData]'s child data
2392    pub fn add_child_data(mut self, r: ArrayData) -> Self {
2393        self.child_data.push(r);
2394        self
2395    }
2396
2397    /// Creates an array data, without any validation
2398    ///
2399    /// Note: This is shorthand for
2400    /// ```rust
2401    /// # #[expect(unsafe_op_in_unsafe_fn)]
2402    /// # let mut builder = arrow_data::ArrayDataBuilder::new(arrow_schema::DataType::Null);
2403    /// # let _ = unsafe {
2404    /// builder.skip_validation(true).build().unwrap()
2405    /// # };
2406    /// ```
2407    ///
2408    /// # Safety
2409    ///
2410    /// The same caveats as [`ArrayData::new_unchecked`]
2411    /// apply.
2412    pub unsafe fn build_unchecked(self) -> ArrayData {
2413        unsafe { self.skip_validation(true) }.build().unwrap()
2414    }
2415
2416    /// Creates an `ArrayData`, consuming `self`
2417    ///
2418    /// # Undefined behavior
2419    ///
2420    /// By default the underlying buffers are checked to ensure they are valid
2421    /// Arrow data. However, if the [`Self::skip_validation`] flag has been set
2422    /// to true (by the `unsafe` API) this validation is skipped. If the data is
2423    /// not valid, undefined behavior will result.
2424    pub fn build(self) -> Result<ArrayData, ArrowError> {
2425        let Self {
2426            data_type,
2427            len,
2428            null_count,
2429            null_bit_buffer,
2430            nulls,
2431            offset,
2432            buffers,
2433            child_data,
2434            align_buffers,
2435            skip_validation,
2436        } = self;
2437
2438        // SAFETY: `skip_validation` is only set to true using `unsafe` APIs.
2439        let validate = !skip_validation.get() || cfg!(feature = "force_validate");
2440        if validate && let Some(buffer) = null_bit_buffer.as_ref() {
2441            // Check before constructing the BooleanBuffer, which would otherwise panic.
2442            let len_plus_offset = checked_len_plus_offset(&data_type, len, offset)?;
2443            let needed_len = bit_util::ceil(len_plus_offset, 8);
2444            if buffer.len() < needed_len {
2445                return Err(ArrowError::InvalidArgumentError(format!(
2446                    "null_bit_buffer size too small. got {} needed {}",
2447                    buffer.len(),
2448                    needed_len
2449                )));
2450            }
2451        }
2452
2453        let nulls = nulls
2454            .or_else(|| {
2455                let buffer = null_bit_buffer?;
2456                let buffer = BooleanBuffer::new(buffer, offset, len);
2457                Some(match null_count {
2458                    Some(n) => {
2459                        // SAFETY: call to `data.validate_data()` below validates the null buffer is valid
2460                        unsafe { NullBuffer::new_unchecked(buffer, n) }
2461                    }
2462                    None => NullBuffer::new(buffer),
2463                })
2464            })
2465            .filter(|b| b.null_count() != 0);
2466
2467        let mut data = ArrayData {
2468            data_type,
2469            len,
2470            offset,
2471            buffers,
2472            child_data,
2473            nulls,
2474        };
2475
2476        if align_buffers {
2477            data.align_buffers();
2478        }
2479
2480        if validate {
2481            data.validate_data()?;
2482        }
2483        Ok(data)
2484    }
2485
2486    /// Ensure that all buffers are aligned, copying data if necessary
2487    ///
2488    /// Rust requires that arrays are aligned to their corresponding primitive,
2489    /// see [`Layout::array`](std::alloc::Layout::array) and [`std::mem::align_of`].
2490    ///
2491    /// [`ArrayData`] therefore requires that all buffers have at least this alignment,
2492    /// to allow for [slice](std::slice) based APIs. See [`BufferSpec::FixedWidth`].
2493    ///
2494    /// As this alignment is architecture specific, and not guaranteed by all arrow implementations,
2495    /// this flag is provided to automatically copy buffers to a new correctly aligned allocation
2496    /// when necessary, making it useful when interacting with buffers produced by other systems,
2497    /// e.g. IPC or FFI.
2498    ///
2499    /// If this flag is not enabled, `[Self::build`] return an error on encountering
2500    /// insufficiently aligned buffers.
2501    pub fn align_buffers(mut self, align_buffers: bool) -> Self {
2502        self.align_buffers = align_buffers;
2503        self
2504    }
2505
2506    /// Skips validation of the data.
2507    ///
2508    /// If this flag is enabled, `[Self::build`] will skip validation of the
2509    /// data
2510    ///
2511    /// If this flag is not enabled, `[Self::build`] will validate that all
2512    /// buffers are valid and will return an error if any data is invalid.
2513    /// Validation can be expensive.
2514    ///
2515    /// # Safety
2516    ///
2517    /// If validation is skipped, the buffers must form a valid Arrow array,
2518    /// otherwise undefined behavior will result
2519    pub unsafe fn skip_validation(mut self, skip_validation: bool) -> Self {
2520        unsafe {
2521            self.skip_validation.set(skip_validation);
2522        }
2523        self
2524    }
2525}
2526
2527impl From<ArrayData> for ArrayDataBuilder {
2528    fn from(d: ArrayData) -> Self {
2529        Self {
2530            data_type: d.data_type,
2531            len: d.len,
2532            offset: d.offset,
2533            buffers: d.buffers,
2534            child_data: d.child_data,
2535            nulls: d.nulls,
2536            null_bit_buffer: None,
2537            null_count: None,
2538            align_buffers: false,
2539            skip_validation: UnsafeFlag::new(),
2540        }
2541    }
2542}
2543
2544/// Get byte width of FixedSizeBinary size
2545/// # Panics:
2546/// - Panics if the `data_type` is not FixedSizeBinary
2547/// - Panics if byte width is negative
2548pub(crate) fn get_fixed_size_binary_width(data_type: &DataType) -> usize {
2549    match data_type {
2550        DataType::FixedSizeBinary(i) => {
2551            if *i < 0 {
2552                panic!("cannot compare FixedSizeBinary({})", *i);
2553            }
2554            *i as usize
2555        }
2556        _ => unreachable!(),
2557    }
2558}
2559
2560#[cfg(test)]
2561mod tests {
2562    use arrow_schema::UnionFields;
2563
2564    use super::*;
2565    use crate::ByteView;
2566    use crate::transform::MutableArrayData;
2567    use arrow_buffer::{OffsetBuffer, ScalarBuffer};
2568    use arrow_schema::{Field, Fields};
2569
2570    // See arrow/tests/array_data_validation.rs for test of array validation
2571
2572    /// returns a buffer initialized with some constant value for tests
2573    fn make_i32_buffer(n: usize) -> Buffer {
2574        Buffer::from_slice_ref(vec![42i32; n])
2575    }
2576
2577    /// returns a buffer initialized with some constant value for tests
2578    fn make_f32_buffer(n: usize) -> Buffer {
2579        Buffer::from_slice_ref(vec![42f32; n])
2580    }
2581
2582    #[test]
2583    fn test_builder() {
2584        // Buffer needs to be at least 25 long
2585        let v = (0..25).collect::<Vec<i32>>();
2586        let b1 = Buffer::from_slice_ref(&v);
2587        let arr_data = ArrayData::builder(DataType::Int32)
2588            .len(20)
2589            .offset(5)
2590            .add_buffer(b1)
2591            .null_bit_buffer(Some(Buffer::from([
2592                0b01011111, 0b10110101, 0b01100011, 0b00011110,
2593            ])))
2594            .build()
2595            .unwrap();
2596
2597        assert_eq!(20, arr_data.len());
2598        assert_eq!(10, arr_data.null_count());
2599        assert_eq!(5, arr_data.offset());
2600        assert_eq!(1, arr_data.buffers().len());
2601        assert_eq!(
2602            Buffer::from_slice_ref(&v).as_slice(),
2603            arr_data.buffers()[0].as_slice()
2604        );
2605    }
2606
2607    #[test]
2608    fn test_builder_with_child_data() {
2609        let child_arr_data = ArrayData::try_new(
2610            DataType::Int32,
2611            5,
2612            None,
2613            0,
2614            vec![Buffer::from_slice_ref([1i32, 2, 3, 4, 5])],
2615            vec![],
2616        )
2617        .unwrap();
2618
2619        let field = Arc::new(Field::new("x", DataType::Int32, true));
2620        let data_type = DataType::Struct(vec![field].into());
2621
2622        let arr_data = ArrayData::builder(data_type)
2623            .len(5)
2624            .offset(0)
2625            .add_child_data(child_arr_data.clone())
2626            .build()
2627            .unwrap();
2628
2629        assert_eq!(5, arr_data.len());
2630        assert_eq!(1, arr_data.child_data().len());
2631        assert_eq!(child_arr_data, arr_data.child_data()[0]);
2632    }
2633
2634    #[test]
2635    fn test_struct_validation_accounts_for_parent_offset() {
2636        let data_type =
2637            DataType::Struct(Fields::from(vec![Field::new("x", DataType::Int32, false)]));
2638        let child = ArrayData::builder(DataType::Int32)
2639            .len(5)
2640            .add_buffer(Buffer::from_slice_ref([0, 1, 2, 3, 4]))
2641            .build()
2642            .unwrap();
2643
2644        // The parent needs child elements 1..6, but the child only has five.
2645        let err = ArrayData::builder(data_type)
2646            .len(5)
2647            .offset(1)
2648            .add_child_data(child)
2649            .build()
2650            .unwrap_err()
2651            .to_string();
2652
2653        assert!(err.contains(
2654            "child array #0 for field x has length smaller than expected for struct array (5 < 6)"
2655        ));
2656    }
2657
2658    #[test]
2659    fn test_struct_non_nullable_child_nulls_account_for_parent_offset() {
2660        let build = |parent_nulls| {
2661            let child = ArrayData::builder(DataType::Int32)
2662                .len(5)
2663                .add_buffer(Buffer::from_slice_ref([0, 1, 2, 3, 4]))
2664                .nulls(Some(NullBuffer::new(BooleanBuffer::from(vec![
2665                    true, true, false, true, true,
2666                ]))))
2667                .build()
2668                .unwrap();
2669
2670            ArrayData::builder(DataType::Struct(Fields::from(vec![Field::new(
2671                "x",
2672                DataType::Int32,
2673                false,
2674            )])))
2675            .len(4)
2676            .offset(1)
2677            .nulls(Some(NullBuffer::new(BooleanBuffer::from(parent_nulls))))
2678            .add_child_data(child)
2679            .build()
2680        };
2681
2682        assert!(build(vec![true, false, true, true]).is_ok());
2683        assert!(build(vec![true, true, false, true]).is_err());
2684    }
2685
2686    #[test]
2687    fn test_fixed_size_list_non_nullable_child_nulls_account_for_parent_offset() {
2688        for child_offset in [0, 1] {
2689            let child = ArrayData::builder(DataType::Int32)
2690                .len(6)
2691                .offset(child_offset)
2692                .add_buffer(Buffer::from_slice_ref([0i32; 7]))
2693                .nulls(Some(NullBuffer::from(vec![
2694                    true, true, false, false, true, true,
2695                ])))
2696                .build()
2697                .unwrap();
2698            let build = |parent_nulls| {
2699                ArrayData::builder(DataType::FixedSizeList(
2700                    Arc::new(Field::new("item", DataType::Int32, false)),
2701                    2,
2702                ))
2703                .offset(1)
2704                .len(2)
2705                .nulls(Some(NullBuffer::from(parent_nulls)))
2706                .add_child_data(child.clone())
2707                .build()
2708            };
2709
2710            // The first visible list contains both child nulls.
2711            assert!(build(vec![false, true]).is_ok());
2712            assert!(build(vec![true, false]).is_err());
2713        }
2714    }
2715
2716    #[test]
2717    fn test_fixed_size_list_non_nullable_child_nulls_without_parent_nulls() {
2718        let child = ArrayData::builder(DataType::Int32)
2719            .len(6)
2720            .add_buffer(Buffer::from_slice_ref([0i32; 6]))
2721            .nulls(Some(NullBuffer::from(vec![
2722                false, false, true, true, false, false,
2723            ])))
2724            .build()
2725            .unwrap();
2726        let build = |offset, len, size| {
2727            ArrayData::builder(DataType::FixedSizeList(
2728                Arc::new(Field::new("item", DataType::Int32, false)),
2729                size,
2730            ))
2731            .offset(offset)
2732            .len(len)
2733            .add_child_data(child.clone())
2734            .build()
2735        };
2736
2737        // Nulls before and after the visible child range are irrelevant.
2738        assert!(build(1, 1, 2).is_ok());
2739        assert!(build(0, 1, 2).is_err());
2740        assert!(build(2, 1, 2).is_err());
2741        assert!(build(3, 0, 2).is_ok());
2742        assert!(build(1, 2, 0).is_ok());
2743    }
2744
2745    #[test]
2746    fn test_fixed_size_list_validation_accounts_for_parent_offset() {
2747        for nulls in [None, Some(NullBuffer::new_null(4))] {
2748            let child = ArrayData::builder(DataType::Int32)
2749                .len(4)
2750                .add_buffer(Buffer::from_slice_ref([0i32; 4]))
2751                .nulls(nulls)
2752                .build()
2753                .unwrap();
2754            let err = ArrayData::builder(DataType::FixedSizeList(
2755                Arc::new(Field::new("item", DataType::Int32, false)),
2756                2,
2757            ))
2758            .offset(1)
2759            .len(2)
2760            .add_child_data(child)
2761            .build()
2762            .unwrap_err()
2763            .to_string();
2764            assert!(err.contains("Values length 4 is less than"));
2765        }
2766    }
2767
2768    #[test]
2769    fn test_fixed_size_list_validation_child_len_mul_overflow() {
2770        // Empty child and no parent null buffer: huge logical lengths allocate nothing.
2771        let child = ArrayData::builder(DataType::Int32)
2772            .len(0)
2773            .add_buffer(Buffer::from_slice_ref([0i32; 0]))
2774            .build()
2775            .unwrap();
2776        let list_size = 2i32;
2777        let data_type = DataType::FixedSizeList(
2778            Arc::new(Field::new("item", DataType::Int32, true)),
2779            list_size,
2780        );
2781        // `(len + offset) * list_size` overflows; the addition itself does not.
2782        let len_plus_offset = (usize::MAX / 2) + 1;
2783        let overflow_cases = [(len_plus_offset, 0usize), (usize::MAX / 2, 1)];
2784
2785        for (len, offset) in overflow_cases {
2786            let err = ArrayData::builder(data_type.clone())
2787                .len(len)
2788                .offset(offset)
2789                .add_child_data(child.clone())
2790                .build()
2791                .unwrap_err();
2792
2793            match err {
2794                ArrowError::InvalidArgumentError(msg) => assert_eq!(
2795                    msg,
2796                    format!(
2797                        "Integer overflow computing expected number of values in {data_type}: length + offset ({len_plus_offset}) multiplied by list size ({list_size}) exceeds usize"
2798                    )
2799                ),
2800                other => panic!("unexpected error type {other}"),
2801            }
2802        }
2803
2804        // Same product is representable here, so validation reports a short child.
2805        let err = ArrayData::builder(data_type.clone())
2806            .len(usize::MAX / 2)
2807            .offset(0)
2808            .add_child_data(child)
2809            .build()
2810            .unwrap_err();
2811
2812        match err {
2813            ArrowError::InvalidArgumentError(msg) => assert_eq!(
2814                msg,
2815                format!(
2816                    "Values length 0 is less than the length + offset ({}) multiplied by the value size ({list_size}) for {data_type}",
2817                    usize::MAX / 2
2818                )
2819            ),
2820            other => panic!("unexpected error type {other}"),
2821        }
2822    }
2823
2824    #[test]
2825    fn test_struct_equal_accounts_for_parent_offset() {
2826        let data_type =
2827            DataType::Struct(Fields::from(vec![Field::new("x", DataType::Int32, false)]));
2828
2829        let child1 = ArrayData::builder(DataType::Int32)
2830            .len(5)
2831            .add_buffer(Buffer::from_slice_ref([0, 1, 2, 3, 4]))
2832            .build()
2833            .unwrap();
2834        let child2 = child1.slice(1, 4);
2835
2836        // data1 has offset at parent level; data2 has offset at child level.
2837        let data1 = ArrayData::builder(data_type.clone())
2838            .len(4)
2839            .offset(1)
2840            .add_child_data(child1)
2841            .build()
2842            .unwrap();
2843        let data2 = ArrayData::builder(data_type)
2844            .len(4)
2845            .add_child_data(child2)
2846            .build()
2847            .unwrap();
2848
2849        assert_eq!(data1, data2);
2850    }
2851
2852    #[test]
2853    fn test_extend_struct_accounts_for_parent_offset() {
2854        let data_type =
2855            DataType::Struct(Fields::from(vec![Field::new("x", DataType::Int32, false)]));
2856        let child = ArrayData::builder(DataType::Int32)
2857            .len(5)
2858            .add_buffer(Buffer::from_slice_ref([0, 1, 2, 3, 4]))
2859            .build()
2860            .unwrap();
2861
2862        let data = ArrayData::builder(data_type)
2863            .len(4)
2864            .offset(1)
2865            .add_child_data(child)
2866            .build()
2867            .unwrap();
2868
2869        let mut mutable = MutableArrayData::new(vec![&data], false, data.len());
2870        mutable.try_extend(0, 0, data.len()).unwrap();
2871        let output = mutable.freeze();
2872
2873        assert_eq!(output.child_data()[0].buffer::<i32>(0), &[1, 2, 3, 4]);
2874    }
2875
2876    #[test]
2877    fn test_extend_fixed_size_list_accounts_for_parent_offset() {
2878        let field = Arc::new(Field::new("item", DataType::Int32, false));
2879        let child = ArrayData::builder(DataType::Int32)
2880            .len(6)
2881            .add_buffer(Buffer::from_slice_ref([0, 1, 2, 3, 4, 5]))
2882            .build()
2883            .unwrap();
2884
2885        let data = ArrayData::builder(DataType::FixedSizeList(field, 2))
2886            .len(2)
2887            .offset(1)
2888            .add_child_data(child)
2889            .build()
2890            .unwrap();
2891
2892        let mut mutable = MutableArrayData::new(vec![&data], false, data.len());
2893        mutable.try_extend(0, 0, data.len()).unwrap();
2894        let output = mutable.freeze();
2895
2896        assert_eq!(output.child_data()[0].buffer::<i32>(0), &[2, 3, 4, 5]);
2897    }
2898
2899    #[test]
2900    fn test_extend_sparse_union_accounts_for_parent_offset() {
2901        let fields = UnionFields::try_new(
2902            [0, 1],
2903            [
2904                Field::new("a", DataType::Int32, false),
2905                Field::new("b", DataType::Int32, false),
2906            ],
2907        )
2908        .unwrap();
2909        let child_a = ArrayData::builder(DataType::Int32)
2910            .len(3)
2911            .add_buffer(Buffer::from_slice_ref([10, 20, 30]))
2912            .build()
2913            .unwrap();
2914        let child_b = ArrayData::builder(DataType::Int32)
2915            .len(3)
2916            .add_buffer(Buffer::from_slice_ref([100, 200, 300]))
2917            .build()
2918            .unwrap();
2919
2920        // The children are left whole, as `ArrayData::slice` and C Data
2921        // Interface producers leave them for a sparse union
2922        let data = ArrayData::builder(DataType::Union(fields, UnionMode::Sparse))
2923            .len(2)
2924            .offset(1)
2925            .add_buffer(Buffer::from_slice_ref([0i8, 1, 0]))
2926            .add_child_data(child_a)
2927            .add_child_data(child_b)
2928            .build()
2929            .unwrap();
2930
2931        let mut mutable = MutableArrayData::new(vec![&data], false, data.len());
2932        mutable.try_extend(0, 0, data.len()).unwrap();
2933        let output = mutable.freeze();
2934
2935        assert_eq!(output.buffer::<i8>(0), &[1, 0]);
2936        assert_eq!(output.child_data()[0].buffer::<i32>(0), &[20, 30]);
2937        assert_eq!(output.child_data()[1].buffer::<i32>(0), &[200, 300]);
2938    }
2939
2940    #[test]
2941    fn test_null_count() {
2942        let mut bit_v: [u8; 2] = [0; 2];
2943        bit_util::set_bit(&mut bit_v, 0);
2944        bit_util::set_bit(&mut bit_v, 3);
2945        bit_util::set_bit(&mut bit_v, 10);
2946        let arr_data = ArrayData::builder(DataType::Int32)
2947            .len(16)
2948            .add_buffer(make_i32_buffer(16))
2949            .null_bit_buffer(Some(Buffer::from(bit_v)))
2950            .build()
2951            .unwrap();
2952        assert_eq!(13, arr_data.null_count());
2953
2954        // Test with offset
2955        let mut bit_v: [u8; 2] = [0; 2];
2956        bit_util::set_bit(&mut bit_v, 0);
2957        bit_util::set_bit(&mut bit_v, 3);
2958        bit_util::set_bit(&mut bit_v, 10);
2959        let arr_data = ArrayData::builder(DataType::Int32)
2960            .len(12)
2961            .offset(2)
2962            .add_buffer(make_i32_buffer(14)) // requires at least 14 bytes of space,
2963            .null_bit_buffer(Some(Buffer::from(bit_v)))
2964            .build()
2965            .unwrap();
2966        assert_eq!(10, arr_data.null_count());
2967    }
2968
2969    #[test]
2970    fn test_null_buffer_ref() {
2971        let mut bit_v: [u8; 2] = [0; 2];
2972        bit_util::set_bit(&mut bit_v, 0);
2973        bit_util::set_bit(&mut bit_v, 3);
2974        bit_util::set_bit(&mut bit_v, 10);
2975        let arr_data = ArrayData::builder(DataType::Int32)
2976            .len(16)
2977            .add_buffer(make_i32_buffer(16))
2978            .null_bit_buffer(Some(Buffer::from(bit_v)))
2979            .build()
2980            .unwrap();
2981        assert!(arr_data.nulls().is_some());
2982        assert_eq!(&bit_v, arr_data.nulls().unwrap().validity());
2983    }
2984
2985    #[test]
2986    fn test_slice() {
2987        let mut bit_v: [u8; 2] = [0; 2];
2988        bit_util::set_bit(&mut bit_v, 0);
2989        bit_util::set_bit(&mut bit_v, 3);
2990        bit_util::set_bit(&mut bit_v, 10);
2991        let data = ArrayData::builder(DataType::Int32)
2992            .len(16)
2993            .add_buffer(make_i32_buffer(16))
2994            .null_bit_buffer(Some(Buffer::from(bit_v)))
2995            .build()
2996            .unwrap();
2997        let new_data = data.slice(1, 15);
2998        assert_eq!(data.len() - 1, new_data.len());
2999        assert_eq!(1, new_data.offset());
3000        assert_eq!(data.null_count(), new_data.null_count());
3001
3002        // slice of a slice (removes one null)
3003        let new_data = new_data.slice(1, 14);
3004        assert_eq!(data.len() - 2, new_data.len());
3005        assert_eq!(2, new_data.offset());
3006        assert_eq!(data.null_count() - 1, new_data.null_count());
3007    }
3008
3009    #[test]
3010    #[should_panic(expected = "offset + length overflow")]
3011    fn test_slice_panics_on_offset_length_overflow() {
3012        let data = ArrayData::builder(DataType::Int32)
3013            .len(4)
3014            .add_buffer(make_i32_buffer(4))
3015            .build()
3016            .unwrap();
3017        let sliced = data.slice(1, 3);
3018
3019        sliced.slice(1, usize::MAX);
3020    }
3021
3022    #[test]
3023    fn test_sliced() {
3024        for nulls in [
3025            None,
3026            Some(NullBuffer::from(vec![true, false, true, false, true])),
3027        ] {
3028            let data = ArrayData::builder(DataType::Int32)
3029                .len(5)
3030                .offset(1)
3031                .add_buffer(make_i32_buffer(6))
3032                .nulls(nulls)
3033                .build()
3034                .unwrap();
3035
3036            for offset in 0..=data.len() {
3037                for length in 0..=data.len() - offset {
3038                    let owned = data.clone();
3039                    let buffers = owned.buffers().as_ptr();
3040                    let sliced = owned.sliced(offset, length);
3041                    assert_eq!(sliced, data.slice(offset, length));
3042                    assert_eq!(sliced.len(), length);
3043                    assert_eq!(sliced.offset(), 1 + offset);
3044                    assert_eq!(sliced.buffers().as_ptr(), buffers);
3045                    assert_eq!(sliced.buffers()[0].as_ptr(), data.buffers()[0].as_ptr());
3046                    if let Some(nulls) = data.nulls() {
3047                        assert_eq!(
3048                            sliced.nulls().unwrap().iter().collect::<Vec<_>>(),
3049                            nulls.iter().skip(offset).take(length).collect::<Vec<_>>()
3050                        );
3051                    }
3052                    sliced.validate_full().unwrap();
3053                }
3054            }
3055        }
3056
3057        let empty = ArrayData::new_empty(&DataType::Int32);
3058        assert_eq!(empty.clone().sliced(0, 0), empty);
3059    }
3060
3061    #[test]
3062    fn test_sliced_nested_struct() {
3063        let child = ArrayData::builder(DataType::Int32)
3064            .len(8)
3065            .offset(1)
3066            .add_buffer(make_i32_buffer(9))
3067            .nulls(Some(NullBuffer::from(vec![
3068                true, false, true, false, true, true, false, true,
3069            ])))
3070            .build()
3071            .unwrap();
3072        let inner = ArrayData::builder(DataType::Struct(Fields::from(vec![Field::new(
3073            "x",
3074            DataType::Int32,
3075            true,
3076        )])))
3077        .len(6)
3078        .offset(1)
3079        .nulls(Some(NullBuffer::from(vec![
3080            true, false, true, true, false, true,
3081        ])))
3082        .add_child_data(child)
3083        .build()
3084        .unwrap();
3085        let data = ArrayData::builder(DataType::Struct(Fields::from(vec![Field::new(
3086            "inner",
3087            inner.data_type().clone(),
3088            true,
3089        )])))
3090        .len(4)
3091        .offset(1)
3092        .nulls(Some(NullBuffer::from(vec![false, true, false, true])))
3093        .add_child_data(inner)
3094        .build()
3095        .unwrap();
3096
3097        for (offset, length) in [(0, 4), (1, 2), (4, 0), (0, 0)] {
3098            let owned = data.clone();
3099            let children = owned.child_data().as_ptr();
3100            let grandchildren = owned.child_data()[0].child_data().as_ptr();
3101            let buffers = owned.child_data()[0].child_data()[0].buffers().as_ptr();
3102            let sliced = owned.sliced(offset, length);
3103            let inner = &sliced.child_data()[0];
3104            let child = &inner.child_data()[0];
3105            assert_eq!(sliced, data.slice(offset, length));
3106            assert_eq!(sliced.offset(), 0);
3107            assert_eq!(inner.offset(), 0);
3108            assert_eq!(child.offset(), 3 + offset);
3109            assert_eq!(sliced.child_data().as_ptr(), children);
3110            assert_eq!(inner.child_data().as_ptr(), grandchildren);
3111            assert_eq!(child.buffers().as_ptr(), buffers);
3112            sliced.validate_full().unwrap();
3113        }
3114
3115        let sliced = data.sliced(1, 2).sliced(1, 1);
3116        assert_eq!(sliced.null_count(), 1);
3117        assert_eq!(sliced.child_data()[0].null_count(), 0);
3118        assert_eq!(sliced.child_data()[0].child_data()[0].offset(), 5);
3119        assert_eq!(sliced.child_data()[0].child_data()[0].null_count(), 0);
3120    }
3121
3122    #[test]
3123    fn test_sliced_list_preserves_children() {
3124        let child = ArrayData::builder(DataType::Int32)
3125            .len(6)
3126            .offset(1)
3127            .add_buffer(make_i32_buffer(7))
3128            .nulls(Some(NullBuffer::from(vec![
3129                true, false, true, false, true, true,
3130            ])))
3131            .build()
3132            .unwrap();
3133        let data = ArrayData::builder(DataType::List(Arc::new(Field::new(
3134            "item",
3135            DataType::Int32,
3136            true,
3137        ))))
3138        .len(4)
3139        .offset(1)
3140        .add_buffer(Buffer::from_slice_ref([0i32, 1, 2, 3, 4, 5]))
3141        .nulls(Some(NullBuffer::from(vec![false, true, false, true])))
3142        .add_child_data(child)
3143        .build()
3144        .unwrap();
3145        let buffers = data.buffers().as_ptr();
3146        let children = data.child_data().as_ptr();
3147        let child_buffers = data.child_data()[0].buffers().as_ptr();
3148        let expected = data.slice(1, 2);
3149        let sliced = data.sliced(1, 2);
3150        assert_eq!(sliced, expected);
3151        assert_eq!(sliced.offset(), 2);
3152        assert_eq!(sliced.child_data()[0].len(), 6);
3153        assert_eq!(sliced.child_data()[0].offset(), 1);
3154        assert_eq!(sliced.buffers().as_ptr(), buffers);
3155        assert_eq!(sliced.child_data().as_ptr(), children);
3156        assert_eq!(sliced.child_data()[0].buffers().as_ptr(), child_buffers);
3157        sliced.validate_full().unwrap();
3158    }
3159
3160    #[test]
3161    #[should_panic(expected = "offset + length overflow")]
3162    fn test_sliced_panics_on_offset_length_overflow() {
3163        ArrayData::new_null(&DataType::Int32, 4).sliced(1, usize::MAX);
3164    }
3165
3166    #[test]
3167    #[should_panic(expected = "end <= self.len()")]
3168    fn test_sliced_panics_on_offset_out_of_bounds() {
3169        ArrayData::new_null(&DataType::Int32, 4).sliced(5, 0);
3170    }
3171
3172    #[test]
3173    #[should_panic(expected = "end <= self.len()")]
3174    fn test_sliced_panics_on_length_out_of_bounds() {
3175        ArrayData::new_null(&DataType::Int32, 4).sliced(3, 2);
3176    }
3177
3178    #[test]
3179    fn test_typed_offsets_length_overflow() {
3180        let data = ArrayData {
3181            data_type: DataType::Binary,
3182            len: usize::MAX,
3183            offset: 0,
3184            buffers: vec![Buffer::from_slice_ref([0_i32])],
3185            child_data: vec![],
3186            nulls: None,
3187        };
3188        let err = data.typed_offsets::<i32>().unwrap_err();
3189
3190        assert_eq!(
3191            err.to_string(),
3192            format!(
3193                "Invalid argument error: Length {} with offset 1 overflows usize for Binary",
3194                usize::MAX
3195            )
3196        );
3197    }
3198
3199    #[test]
3200    fn test_validate_typed_buffer_length_overflow() {
3201        let data = ArrayData {
3202            data_type: DataType::Binary,
3203            len: 0,
3204            offset: 2,
3205            buffers: vec![Buffer::from_slice_ref([0_i32])],
3206            child_data: vec![],
3207            nulls: None,
3208        };
3209        let err = data.typed_buffer::<i32>(0, usize::MAX).unwrap_err();
3210
3211        assert_eq!(
3212            err.to_string(),
3213            format!(
3214                "Invalid argument error: Length {} with offset 2 overflows usize for Binary",
3215                usize::MAX
3216            )
3217        );
3218    }
3219
3220    // Exercises ArrayData::try_new with len + offset overflowing
3221    fn try_new_binary_length_offset_overflow() -> Result<ArrayData, ArrowError> {
3222        ArrayData::try_new(
3223            DataType::Binary,
3224            usize::MAX,
3225            None,
3226            1,
3227            vec![
3228                Buffer::from_slice_ref([0_i32]),
3229                Buffer::from_iter(std::iter::empty::<u8>()),
3230            ],
3231            vec![],
3232        )
3233    }
3234
3235    #[cfg(not(feature = "force_validate"))]
3236    #[test]
3237    fn test_try_new_length_offset_overflow() {
3238        let err = try_new_binary_length_offset_overflow().unwrap_err();
3239
3240        assert_eq!(
3241            err.to_string(),
3242            format!(
3243                "Invalid argument error: Length {} with offset 1 overflows usize for Binary",
3244                usize::MAX
3245            )
3246        );
3247    }
3248
3249    #[cfg(feature = "force_validate")]
3250    #[test]
3251    #[should_panic(
3252        expected = "Length 18446744073709551615 with offset 1 overflows usize for Binary"
3253    )]
3254    fn test_try_new_length_offset_overflow_force_validate() {
3255        try_new_binary_length_offset_overflow().unwrap();
3256    }
3257
3258    #[test]
3259    fn test_equality() {
3260        let int_data = ArrayData::builder(DataType::Int32)
3261            .len(1)
3262            .add_buffer(make_i32_buffer(1))
3263            .build()
3264            .unwrap();
3265
3266        let float_data = ArrayData::builder(DataType::Float32)
3267            .len(1)
3268            .add_buffer(make_f32_buffer(1))
3269            .build()
3270            .unwrap();
3271        assert_ne!(int_data, float_data);
3272        assert!(!int_data.ptr_eq(&float_data));
3273        assert!(int_data.ptr_eq(&int_data));
3274
3275        let int_data_clone = int_data.clone();
3276        assert_eq!(int_data, int_data_clone);
3277        assert!(int_data.ptr_eq(&int_data_clone));
3278        assert!(int_data_clone.ptr_eq(&int_data));
3279
3280        let int_data_slice = int_data_clone.slice(1, 0);
3281        assert!(int_data_slice.ptr_eq(&int_data_slice));
3282        assert!(!int_data.ptr_eq(&int_data_slice));
3283        assert!(!int_data_slice.ptr_eq(&int_data));
3284
3285        let data_buffer = Buffer::from_slice_ref(b"abcdef");
3286        let offsets_buffer = Buffer::from_slice_ref([0_i32, 2_i32, 2_i32, 5_i32]);
3287        let string_data = ArrayData::try_new(
3288            DataType::Utf8,
3289            3,
3290            Some(Buffer::from_iter(vec![true, false, true])),
3291            0,
3292            vec![offsets_buffer, data_buffer],
3293            vec![],
3294        )
3295        .unwrap();
3296
3297        assert_ne!(float_data, string_data);
3298        assert!(!float_data.ptr_eq(&string_data));
3299
3300        assert!(string_data.ptr_eq(&string_data));
3301
3302        let string_data_cloned = string_data.clone();
3303        assert!(string_data_cloned.ptr_eq(&string_data));
3304        assert!(string_data.ptr_eq(&string_data_cloned));
3305
3306        let string_data_slice = string_data.slice(1, 2);
3307        assert!(string_data_slice.ptr_eq(&string_data_slice));
3308        assert!(!string_data_slice.ptr_eq(&string_data))
3309    }
3310
3311    #[test]
3312    fn test_slice_memory_size_view_payload_buffers() {
3313        for data_type in [DataType::Utf8View, DataType::BinaryView] {
3314            let inline_only = ArrayData::builder(data_type.clone())
3315                .len(2)
3316                .add_buffer(Buffer::from_vec(vec![0_u128; 2]))
3317                .build()
3318                .unwrap();
3319            assert_eq!(
3320                inline_only.get_slice_memory_size().unwrap(),
3321                2 * mem::size_of::<u128>()
3322            );
3323
3324            let mut first_payload = Vec::with_capacity(32);
3325            first_payload.extend_from_slice(b"first payload");
3326            let first_view =
3327                ByteView::new(first_payload.len().try_into().unwrap(), &first_payload[..4])
3328                    .as_u128();
3329            let first_payload = Buffer::from_vec(first_payload);
3330            assert!(first_payload.capacity() > first_payload.len());
3331            let first_payload_capacity = first_payload.capacity();
3332
3333            let mut second_payload = Vec::with_capacity(64);
3334            second_payload.extend_from_slice(b"second payload");
3335            let second_view = ByteView::new(
3336                second_payload.len().try_into().unwrap(),
3337                &second_payload[..4],
3338            )
3339            .with_buffer_index(1)
3340            .as_u128();
3341            let second_payload = Buffer::from_vec(second_payload);
3342            assert!(second_payload.capacity() > second_payload.len());
3343            let second_payload_capacity = second_payload.capacity();
3344
3345            let data = ArrayData::builder(data_type)
3346                .len(3)
3347                .add_buffer(Buffer::from_vec(vec![first_view, 0_u128, second_view]))
3348                .add_buffer(first_payload)
3349                .add_buffer(second_payload)
3350                .build()
3351                .unwrap();
3352            let sliced = data.slice(1, 1);
3353
3354            assert_eq!(
3355                sliced.get_slice_memory_size().unwrap(),
3356                mem::size_of::<u128>() + first_payload_capacity + second_payload_capacity
3357            );
3358        }
3359    }
3360
3361    #[test]
3362    fn test_slice_memory_size_utf8_offset_buffer_len_plus_one() {
3363        // 2-element array ["hello", "world"]: array len = 2, 10 bytes
3364        let data_buffer = Buffer::from_slice_ref(b"helloworld");
3365        // offsets need array_len+1 entries to mark the end of every string:
3366        //   [0, 5, 10] -> 3 i32s = 12 bytes
3367        let offsets_buffer = Buffer::from_slice_ref([0_i32, 5_i32, 10_i32]);
3368        let array = ArrayData::try_new(
3369            DataType::Utf8,
3370            2,
3371            None,
3372            0,
3373            vec![offsets_buffer, data_buffer],
3374            vec![],
3375        )
3376        .unwrap();
3377        assert_eq!(array.get_slice_memory_size().unwrap(), 22); // 12 + 10
3378    }
3379
3380    #[test]
3381    fn test_slice_memory_size_binary_offset_buffer_len_plus_one() {
3382        // 2-element array: array len = 2, not 3
3383        // values: 5 bytes
3384        let data_buffer = Buffer::from_slice_ref([0u8, 1, 2, 3, 4]);
3385        // offsets need array_len+1 entries to mark the end of every element:
3386        let offsets_buffer = Buffer::from_slice_ref([0_i32, 2_i32, 5_i32]);
3387        let array = ArrayData::try_new(
3388            DataType::Binary,
3389            2,
3390            None,
3391            0,
3392            vec![offsets_buffer, data_buffer],
3393            vec![],
3394        )
3395        .unwrap();
3396        assert_eq!(array.get_slice_memory_size().unwrap(), 17); // 12 + 5
3397    }
3398
3399    #[test]
3400    fn test_slice_memory_size() {
3401        let mut bit_v: [u8; 2] = [0; 2];
3402        bit_util::set_bit(&mut bit_v, 0);
3403        bit_util::set_bit(&mut bit_v, 3);
3404        bit_util::set_bit(&mut bit_v, 10);
3405        let data = ArrayData::builder(DataType::Int32)
3406            .len(16)
3407            .add_buffer(make_i32_buffer(16))
3408            .null_bit_buffer(Some(Buffer::from(bit_v)))
3409            .build()
3410            .unwrap();
3411        let new_data = data.slice(1, 14);
3412        assert_eq!(
3413            data.get_slice_memory_size().unwrap() - 8,
3414            new_data.get_slice_memory_size().unwrap()
3415        );
3416        let data_buffer = Buffer::from_slice_ref(b"abcdef");
3417        let offsets_buffer = Buffer::from_slice_ref([0_i32, 2_i32, 2_i32, 5_i32]);
3418        let string_data = ArrayData::try_new(
3419            DataType::Utf8,
3420            3,
3421            Some(Buffer::from_iter(vec![true, false, true])),
3422            0,
3423            vec![offsets_buffer, data_buffer],
3424            vec![],
3425        )
3426        .unwrap();
3427        let string_data_slice = string_data.slice(1, 2);
3428        //4 bytes of offset and 2 bytes of data reduced by slicing.
3429        assert_eq!(
3430            string_data.get_slice_memory_size().unwrap() - 6,
3431            string_data_slice.get_slice_memory_size().unwrap()
3432        );
3433    }
3434
3435    #[test]
3436    fn test_builder_rejects_short_null_bit_buffer() {
3437        for (len, offset) in [(8000, 0), (8, 1)] {
3438            let err = ArrayData::builder(DataType::Int32)
3439                .len(len)
3440                .offset(offset)
3441                .add_buffer(make_i32_buffer(len + offset))
3442                .null_bit_buffer(Some(Buffer::from([0_u8])))
3443                .build()
3444                .unwrap_err();
3445            assert_eq!(
3446                err.to_string(),
3447                format!(
3448                    "Invalid argument error: null_bit_buffer size too small. got 1 needed {}",
3449                    bit_util::ceil(len + offset, 8)
3450                )
3451            );
3452        }
3453    }
3454
3455    #[test]
3456    fn test_builder_null_bit_buffer_length_overflow() {
3457        let err = ArrayData::builder(DataType::Int32)
3458            .len(usize::MAX)
3459            .offset(1)
3460            .null_bit_buffer(Some(Buffer::default()))
3461            .build()
3462            .unwrap_err();
3463        assert_eq!(
3464            err.to_string(),
3465            format!(
3466                "Invalid argument error: Length {} with offset 1 overflows usize for Int32",
3467                usize::MAX
3468            )
3469        );
3470    }
3471
3472    #[test]
3473    fn test_builder_accepts_valid_null_bit_buffer() {
3474        for (len, offset) in [(8, 0), (7, 1)] {
3475            let data = ArrayData::builder(DataType::Int32)
3476                .len(len)
3477                .offset(offset)
3478                .add_buffer(make_i32_buffer(len + offset))
3479                .null_bit_buffer(Some(Buffer::from([0_u8])))
3480                .build()
3481                .unwrap();
3482            assert_eq!(data.len(), len);
3483            assert_eq!(data.offset(), offset);
3484            assert_eq!(data.null_count(), len);
3485        }
3486    }
3487
3488    #[test]
3489    fn test_count_nulls() {
3490        let buffer = Buffer::from([0b00010110, 0b10011111]);
3491        let buffer = NullBuffer::new(BooleanBuffer::new(buffer, 0, 16));
3492        let count = count_nulls(Some(&buffer), 0, 16);
3493        assert_eq!(count, 7);
3494
3495        let count = count_nulls(Some(&buffer), 4, 8);
3496        assert_eq!(count, 3);
3497    }
3498
3499    #[test]
3500    fn test_contains_nulls() {
3501        let buffer: Buffer =
3502            MutableBuffer::from_iter([false, false, false, true, true, false]).into();
3503        let buffer = NullBuffer::new(BooleanBuffer::new(buffer, 0, 6));
3504        assert!(contains_nulls(Some(&buffer), 0, 6));
3505        assert!(contains_nulls(Some(&buffer), 0, 3));
3506        assert!(!contains_nulls(Some(&buffer), 3, 2));
3507        assert!(!contains_nulls(Some(&buffer), 0, 0));
3508    }
3509
3510    #[test]
3511    fn test_alignment() {
3512        let buffer = Buffer::from_vec(vec![1_i32, 2_i32, 3_i32]);
3513        let sliced = buffer.slice(1);
3514
3515        let mut data = ArrayData {
3516            data_type: DataType::Int32,
3517            len: 0,
3518            offset: 0,
3519            buffers: vec![buffer],
3520            child_data: vec![],
3521            nulls: None,
3522        };
3523        data.validate_full().unwrap();
3524
3525        // break alignment in data
3526        data.buffers[0] = sliced;
3527        let err = data.validate().unwrap_err();
3528
3529        assert_eq!(
3530            err.to_string(),
3531            "Invalid argument error: Misaligned buffers[0] in array of type Int32, offset from expected alignment of 4 by 1"
3532        );
3533
3534        data.align_buffers();
3535        data.validate_full().unwrap();
3536    }
3537
3538    #[test]
3539    fn test_alignment_struct() {
3540        let buffer = Buffer::from_vec(vec![1_i32, 2_i32, 3_i32]);
3541        let sliced = buffer.slice(1);
3542
3543        let child_data = ArrayData {
3544            data_type: DataType::Int32,
3545            len: 0,
3546            offset: 0,
3547            buffers: vec![buffer],
3548            child_data: vec![],
3549            nulls: None,
3550        };
3551
3552        let schema = DataType::Struct(Fields::from(vec![Field::new("a", DataType::Int32, false)]));
3553        let mut data = ArrayData {
3554            data_type: schema,
3555            len: 0,
3556            offset: 0,
3557            buffers: vec![],
3558            child_data: vec![child_data],
3559            nulls: None,
3560        };
3561        data.validate_full().unwrap();
3562
3563        // break alignment in child data
3564        data.child_data[0].buffers[0] = sliced;
3565        let err = data.validate().unwrap_err();
3566
3567        assert_eq!(
3568            err.to_string(),
3569            "Invalid argument error: Misaligned buffers[0] in array of type Int32, offset from expected alignment of 4 by 1"
3570        );
3571
3572        data.align_buffers();
3573        data.validate_full().unwrap();
3574    }
3575
3576    #[test]
3577    fn test_null_view_types() {
3578        let array_len = 32;
3579        let array = ArrayData::new_null(&DataType::BinaryView, array_len);
3580        assert_eq!(array.len(), array_len);
3581        for i in 0..array.len() {
3582            assert!(array.is_null(i));
3583        }
3584
3585        let array = ArrayData::new_null(&DataType::Utf8View, array_len);
3586        assert_eq!(array.len(), array_len);
3587        for i in 0..array.len() {
3588            assert!(array.is_null(i));
3589        }
3590
3591        let array = ArrayData::new_null(
3592            &DataType::ListView(Arc::new(Field::new_list_field(DataType::Int32, true))),
3593            array_len,
3594        );
3595        assert_eq!(array.len(), array_len);
3596        for i in 0..array.len() {
3597            assert!(array.is_null(i));
3598        }
3599
3600        let array = ArrayData::new_null(
3601            &DataType::LargeListView(Arc::new(Field::new_list_field(DataType::Int32, true))),
3602            array_len,
3603        );
3604        assert_eq!(array.len(), array_len);
3605        for i in 0..array.len() {
3606            assert!(array.is_null(i));
3607        }
3608    }
3609
3610    // Even when `force_validate` feature is on
3611    #[test]
3612    fn test_dont_panic_on_bad_input_when_using_try_new() {
3613        let empty_bytes = Buffer::default();
3614
3615        let array_data = ArrayData::try_new(
3616            DataType::Utf8,
3617            1, // len
3618            None,
3619            0,
3620            // the offsets says that we have 2 bytes but the buffer is empty
3621            vec![Buffer::from_vec(vec![0i32, 2i32]), empty_bytes],
3622            vec![],
3623        );
3624
3625        let res = array_data.expect_err("should get error");
3626
3627        assert_eq!(
3628            res.to_string(),
3629            "Invalid argument error: Last offset 2 of Utf8 is larger than values length 0"
3630        );
3631    }
3632
3633    /// Without `force_validate`, `build_unchecked` skips validation, so these can
3634    /// reach `validate_values` with a data type that has an invalid child type.
3635    #[test]
3636    #[cfg(not(feature = "force_validate"))]
3637    fn test_validate_values_rejects_a_non_integer_dictionary_key() {
3638        let values = valid_non_nullable_int32_array_data(2);
3639        let data_type = DataType::Dictionary(Box::new(DataType::Utf8), Box::new(DataType::Int32));
3640        let dictionary = unsafe {
3641            ArrayData::builder(data_type)
3642                .len(1)
3643                .add_child_data(values)
3644                .build_unchecked()
3645        };
3646
3647        let err = dictionary.validate_values().expect_err("should get error");
3648        assert_eq!(
3649            err.to_string(),
3650            "Invalid argument error: Dictionary key type must be an integer, got Utf8"
3651        );
3652    }
3653
3654    #[test]
3655    #[cfg(not(feature = "force_validate"))]
3656    fn test_validate_values_rejects_a_non_integer_run_end() {
3657        let data_type = DataType::RunEndEncoded(
3658            Arc::new(Field::new(
3659                Field::REE_RUN_ENDS_FIELD_DEFAULT_NAME,
3660                DataType::Utf8,
3661                false,
3662            )),
3663            Arc::new(Field::new(
3664                Field::REE_VALUES_FIELD_DEFAULT_NAME,
3665                DataType::Int32,
3666                true,
3667            )),
3668        );
3669        let run_end_encoded = unsafe {
3670            ArrayData::builder(data_type)
3671                .len(1)
3672                .add_child_data(valid_non_nullable_int32_array_data(1))
3673                .add_child_data(valid_non_nullable_int32_array_data(1))
3674                .build_unchecked()
3675        };
3676
3677        let err = run_end_encoded
3678            .validate_values()
3679            .expect_err("should get error");
3680        assert_eq!(
3681            err.to_string(),
3682            "Invalid argument error: Run end type must be Int16, Int32 or Int64, got Utf8"
3683        );
3684    }
3685
3686    /// Returns a `RunEndEncoded<Int32, Float32>` data type and run ends / values
3687    /// children whose runs end at `[1, 3]`, i.e. a logical length of 3.
3688    fn run_array_test_children() -> (DataType, Vec<ArrayData>) {
3689        let dt = DataType::RunEndEncoded(
3690            Arc::new(Field::new(
3691                Field::REE_RUN_ENDS_FIELD_DEFAULT_NAME,
3692                DataType::Int32,
3693                false,
3694            )),
3695            Arc::new(Field::new(
3696                Field::REE_VALUES_FIELD_DEFAULT_NAME,
3697                DataType::Float32,
3698                true,
3699            )),
3700        );
3701
3702        let runs = ArrayData::builder(DataType::Int32)
3703            .len(2)
3704            .add_buffer(vec![1_i32, 3].into())
3705            .build()
3706            .unwrap();
3707        let values = ArrayData::builder(DataType::Float32)
3708            .len(2)
3709            .add_buffer(vec![1.5_f32, 2.5].into())
3710            .build()
3711            .unwrap();
3712
3713        (dt, vec![runs, values])
3714    }
3715
3716    #[test]
3717    fn test_run_array_validates_last_run() {
3718        let (dt, children) = run_array_test_children();
3719
3720        let err = ArrayDataBuilder::new(dt)
3721            .len(4)
3722            .offset(0)
3723            .child_data(children)
3724            .build()
3725            .unwrap_err();
3726        assert_eq!(
3727            err.to_string(),
3728            "Invalid argument error: The offset + length of array should be less or equal to last value in the run_ends array. The last value of run_ends array is 3 and offset + length of array is 4."
3729        );
3730    }
3731
3732    #[test]
3733    fn test_run_array_empty_validates() {
3734        let (dt, children) = run_array_test_children();
3735
3736        let data = ArrayDataBuilder::new(dt)
3737            .len(0)
3738            .offset(4)
3739            .child_data(children)
3740            .build()
3741            .unwrap();
3742        assert_eq!(data.len(), 0);
3743    }
3744
3745    /// The parent's offset must be included when checking the last run end:
3746    /// offset 2 + length 2 = 4 exceeds the last run end of 3.
3747    #[test]
3748    fn test_run_array_validates_last_run_with_offset() {
3749        let (dt, children) = run_array_test_children();
3750
3751        let err = ArrayDataBuilder::new(dt)
3752            .len(2)
3753            .offset(2)
3754            .child_data(children)
3755            .build()
3756            .unwrap_err();
3757        assert_eq!(
3758            err.to_string(),
3759            "Invalid argument error: The offset + length of array should be less or equal to last value in the run_ends array. The last value of run_ends array is 3 and offset + length of array is 4."
3760        );
3761    }
3762
3763    /// A slice that stays within the last run end is valid:
3764    /// offset 1 + length 2 = 3 equals the last run end of 3.
3765    #[test]
3766    fn test_run_array_sliced_validates() {
3767        let (dt, children) = run_array_test_children();
3768
3769        let data = ArrayDataBuilder::new(dt)
3770            .len(2)
3771            .offset(1)
3772            .child_data(children)
3773            .build()
3774            .unwrap();
3775        assert_eq!(data.len(), 2);
3776        assert_eq!(data.offset(), 1);
3777    }
3778
3779    /// `validate_values` must report missing children rather than index out of bounds.
3780    #[test]
3781    #[cfg(not(feature = "force_validate"))]
3782    fn test_validate_values_rejects_missing_child_data() {
3783        let int32 = Box::new(DataType::Int32);
3784        let field = || Arc::new(Field::new("f", DataType::Int32, true));
3785        let data_types = [
3786            DataType::Dictionary(int32.clone(), int32.clone()),
3787            DataType::List(field()),
3788            DataType::LargeList(field()),
3789            DataType::RunEndEncoded(field(), field()),
3790        ];
3791
3792        for data_type in data_types {
3793            let data = unsafe {
3794                ArrayData::builder(data_type.clone())
3795                    .len(1)
3796                    .build_unchecked()
3797            };
3798            let err = data.validate_values().expect_err("should get error");
3799            assert_eq!(
3800                err.to_string(),
3801                format!(
3802                    "Invalid argument error: {data_type} should contain at least 1 child data array(s), had 0"
3803                )
3804            );
3805        }
3806    }
3807
3808    /// `validate_values` must report missing buffers rather than index out of bounds.
3809    #[test]
3810    #[cfg(not(feature = "force_validate"))]
3811    fn test_validate_values_rejects_missing_buffers() {
3812        // (data type, index of the first missing buffer)
3813        let cases = [
3814            (DataType::Utf8, 1),
3815            (DataType::LargeUtf8, 1),
3816            (DataType::Binary, 1),
3817            (DataType::LargeBinary, 1),
3818            (DataType::BinaryView, 0),
3819            (DataType::Utf8View, 0),
3820        ];
3821
3822        for (data_type, missing) in cases {
3823            let data = unsafe {
3824                ArrayData::builder(data_type.clone())
3825                    .len(1)
3826                    .build_unchecked()
3827            };
3828            let err = data.validate_values().expect_err("should get error");
3829            assert_eq!(
3830                err.to_string(),
3831                format!(
3832                    "Invalid argument error: {data_type} should contain at least {} buffer(s), had 0",
3833                    missing + 1
3834                )
3835            );
3836        }
3837    }
3838
3839    /// A dictionary whose keys buffer is too small must be reported, not asserted on.
3840    #[test]
3841    #[cfg(not(feature = "force_validate"))]
3842    fn test_validate_values_rejects_a_short_dictionary_keys_buffer() {
3843        let data_type = DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Int32));
3844        let dictionary = unsafe {
3845            ArrayData::builder(data_type)
3846                .len(4)
3847                .add_buffer(Buffer::from_slice_ref([1_i32, 0]))
3848                .add_child_data(valid_non_nullable_int32_array_data(2))
3849                .build_unchecked()
3850        };
3851
3852        let err = dictionary.validate_values().expect_err("should get error");
3853        assert_eq!(
3854            err.to_string(),
3855            "Invalid argument error: Buffer 0 of Dictionary(Int32, Int32) isn't large enough. Expected 16 bytes got 8"
3856        );
3857    }
3858
3859    /// `validate` only requires a minimum buffer size, so an offsets buffer
3860    /// may carry trailing bytes that are not a whole number of offsets.
3861    #[test]
3862    fn test_validate_offsets_buffer_with_trailing_bytes() {
3863        let mut offsets = Buffer::from_slice_ref([0_i32, 2, 5]).as_slice().to_vec();
3864        offsets.extend_from_slice(&[0, 0]);
3865        let data = ArrayData::builder(DataType::Utf8)
3866            .len(2)
3867            .add_buffer(Buffer::from_slice_ref(&offsets))
3868            .add_buffer(Buffer::from_slice_ref(b"hello"))
3869            .build()
3870            .unwrap();
3871        data.validate_full().unwrap();
3872    }
3873
3874    #[test]
3875    fn should_fail_validation_when_having_map_field_type_is_not_struct() {
3876        let map_field = Field::new("key", DataType::Int32, false);
3877
3878        let map_field_data = valid_non_nullable_int32_array_data(2);
3879
3880        let results = test_both_builder_and_array_data(
3881            DataType::Map(map_field.into(), false),
3882            1,
3883            None,
3884            0,
3885            vec![
3886                OffsetBuffer::<i32>::from_lengths(vec![2])
3887                    .into_inner()
3888                    .into(),
3889            ],
3890            vec![map_field_data],
3891        );
3892
3893        for result in results {
3894            let array_data_err = result.expect_err("should fail for non struct field");
3895
3896            match array_data_err {
3897                ArrowError::InvalidArgumentError(msg) => {
3898                    assert_eq!(
3899                        msg,
3900                        "Map field should be a entries struct data type, got Int32 instead"
3901                    )
3902                }
3903                _ => panic!("unexpected error type {array_data_err}"),
3904            }
3905        }
3906    }
3907
3908    #[test]
3909    fn should_fail_validation_when_having_map_entries_only_have_1_field() {
3910        let struct_data_type = DataType::Struct(Fields::from(vec![Field::new(
3911            Field::MAP_KEY_FIELD_DEFAULT_NAME,
3912            DataType::Int32,
3913            false,
3914        )]));
3915
3916        let key_array_data = valid_non_nullable_int32_array_data(2);
3917
3918        let struct_data = {
3919            let builder = ArrayDataBuilder::new(struct_data_type.clone())
3920                .len(2)
3921                .nulls(None)
3922                .child_data(vec![key_array_data]);
3923
3924            builder.build().unwrap()
3925        };
3926
3927        let results = test_both_builder_and_array_data(
3928            DataType::Map(
3929                Field::new(
3930                    Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
3931                    struct_data_type,
3932                    false,
3933                )
3934                .into(),
3935                false,
3936            ),
3937            1,
3938            None,
3939            0,
3940            vec![
3941                OffsetBuffer::<i32>::from_lengths(vec![2])
3942                    .into_inner()
3943                    .into(),
3944            ],
3945            vec![struct_data],
3946        );
3947
3948        for result in results {
3949            let array_data_err = result.expect_err("should fail for nullable key");
3950
3951            match array_data_err {
3952                ArrowError::InvalidArgumentError(msg) => {
3953                    assert_eq!(
3954                        msg,
3955                        "Map entries data type should be a struct containing 2 fields, got 1 fields"
3956                    )
3957                }
3958                _ => panic!("unexpected error type {array_data_err}"),
3959            }
3960        }
3961    }
3962
3963    #[test]
3964    fn should_fail_validation_when_having_map_entries_have_3_fields() {
3965        let struct_data_type = DataType::Struct(Fields::from(vec![
3966            Field::new(Field::MAP_KEY_FIELD_DEFAULT_NAME, DataType::Int32, false),
3967            Field::new(Field::MAP_VALUE_FIELD_DEFAULT_NAME, DataType::Utf8, true),
3968            Field::new("other", DataType::Int32, true),
3969        ]));
3970
3971        let key_array_data = valid_non_nullable_int32_array_data(2);
3972
3973        let values_array_data = valid_string_array_data(2);
3974
3975        let other_array_data = key_array_data.clone();
3976
3977        let struct_data = {
3978            let builder = ArrayDataBuilder::new(struct_data_type.clone())
3979                .len(2)
3980                .nulls(None)
3981                .child_data(vec![key_array_data, values_array_data, other_array_data]);
3982
3983            builder.build().unwrap()
3984        };
3985
3986        let results = test_both_builder_and_array_data(
3987            DataType::Map(
3988                Field::new(
3989                    Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
3990                    struct_data_type,
3991                    false,
3992                )
3993                .into(),
3994                false,
3995            ),
3996            1,
3997            None,
3998            0,
3999            vec![
4000                OffsetBuffer::<i32>::from_lengths(vec![2])
4001                    .into_inner()
4002                    .into(),
4003            ],
4004            vec![struct_data],
4005        );
4006
4007        for result in results {
4008            let array_data_err = result.expect_err("should fail for nullable key");
4009
4010            match array_data_err {
4011                ArrowError::InvalidArgumentError(msg) => {
4012                    assert_eq!(
4013                        msg,
4014                        "Map entries data type should be a struct containing 2 fields, got 3 fields"
4015                    )
4016                }
4017                _ => panic!("unexpected error type {array_data_err}"),
4018            }
4019        }
4020    }
4021
4022    #[test]
4023    fn should_fail_validation_when_having_nullable_map_keys() {
4024        let struct_data_type = DataType::Struct(Fields::from(vec![
4025            Field::new(Field::MAP_KEY_FIELD_DEFAULT_NAME, DataType::Int32, true),
4026            Field::new(Field::MAP_VALUE_FIELD_DEFAULT_NAME, DataType::Utf8, true),
4027        ]));
4028
4029        let key_array_data = valid_non_nullable_int32_array_data(2);
4030        let values_array_data = valid_string_array_data(2);
4031
4032        let struct_data = {
4033            let builder = ArrayDataBuilder::new(struct_data_type.clone())
4034                .len(2)
4035                .nulls(None)
4036                .child_data(vec![key_array_data, values_array_data]);
4037
4038            builder.build().unwrap()
4039        };
4040
4041        let results = test_both_builder_and_array_data(
4042            DataType::Map(
4043                Field::new(
4044                    Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
4045                    struct_data_type,
4046                    false,
4047                )
4048                .into(),
4049                false,
4050            ),
4051            1,
4052            None,
4053            0,
4054            vec![
4055                OffsetBuffer::<i32>::from_lengths(vec![2])
4056                    .into_inner()
4057                    .into(),
4058            ],
4059            vec![struct_data],
4060        );
4061
4062        for result in results {
4063            let array_data_err = result.expect_err("should fail for nullable key");
4064
4065            match array_data_err {
4066                ArrowError::InvalidArgumentError(msg) => {
4067                    assert_eq!(msg, "Map key field must not be nullable")
4068                }
4069                _ => panic!("unexpected error type {array_data_err}"),
4070            }
4071        }
4072    }
4073
4074    #[test]
4075    fn should_fail_validation_when_having_entries_is_nullable_for_map() {
4076        let struct_data_type = DataType::Struct(Fields::from(vec![
4077            Field::new(Field::MAP_KEY_FIELD_DEFAULT_NAME, DataType::Int32, false),
4078            Field::new(Field::MAP_VALUE_FIELD_DEFAULT_NAME, DataType::Utf8, true),
4079        ]));
4080
4081        let key_array_data = valid_non_nullable_int32_array_data(2);
4082
4083        let values_array_data = valid_string_array_data(2);
4084
4085        let struct_data = {
4086            let builder = ArrayDataBuilder::new(struct_data_type.clone())
4087                .len(2)
4088                .nulls(None)
4089                .child_data(vec![key_array_data, values_array_data]);
4090
4091            builder.build().unwrap()
4092        };
4093
4094        let results = test_both_builder_and_array_data(
4095            DataType::Map(
4096                Field::new(
4097                    Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
4098                    struct_data_type,
4099                    true,
4100                )
4101                .into(),
4102                false,
4103            ),
4104            1,
4105            None,
4106            0,
4107            vec![
4108                OffsetBuffer::<i32>::from_lengths(vec![2])
4109                    .into_inner()
4110                    .into(),
4111            ],
4112            vec![struct_data],
4113        );
4114
4115        for result in results {
4116            let array_data_err = result.expect_err("should fail for nullable entries");
4117
4118            match array_data_err {
4119                ArrowError::InvalidArgumentError(msg) => assert_eq!(
4120                    msg,
4121                    "The nullable should be set to false for the map entries field."
4122                ),
4123                _ => panic!("unexpected error type {array_data_err}"),
4124            }
4125        }
4126    }
4127
4128    #[test]
4129    fn should_allow_to_create_map_from_data() {
4130        let struct_data_type = DataType::Struct(Fields::from(vec![
4131            Field::new(Field::MAP_KEY_FIELD_DEFAULT_NAME, DataType::Int32, false),
4132            Field::new(Field::MAP_VALUE_FIELD_DEFAULT_NAME, DataType::Utf8, true),
4133        ]));
4134
4135        let key_array_data = valid_non_nullable_int32_array_data(2);
4136        let values_array_data = valid_string_array_data(2);
4137
4138        let struct_data = {
4139            let builder = ArrayDataBuilder::new(struct_data_type.clone())
4140                .len(2)
4141                .nulls(None)
4142                .child_data(vec![key_array_data, values_array_data]);
4143
4144            builder.build().unwrap()
4145        };
4146
4147        let results = test_both_builder_and_array_data(
4148            DataType::Map(
4149                Field::new(
4150                    Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
4151                    struct_data_type,
4152                    false,
4153                )
4154                .into(),
4155                false,
4156            ),
4157            1,
4158            None,
4159            0,
4160            vec![
4161                OffsetBuffer::<i32>::from_lengths(vec![2])
4162                    .into_inner()
4163                    .into(),
4164            ],
4165            vec![struct_data],
4166        );
4167
4168        for result in results {
4169            result.expect("should be able to create map ArrayData");
4170        }
4171    }
4172
4173    fn valid_string_array_data(length: usize) -> ArrayData {
4174        let offsets = OffsetBuffer::<i32>::from_lengths(vec![0; length])
4175            .into_inner()
4176            .into_inner();
4177        let empty_bytes = Buffer::default();
4178
4179        let builder = ArrayDataBuilder::new(DataType::Utf8)
4180            .len(length)
4181            .buffers(vec![offsets, empty_bytes])
4182            .nulls(None);
4183
4184        builder.build().unwrap()
4185    }
4186
4187    fn valid_non_nullable_int32_array_data(length: usize) -> ArrayData {
4188        let builder = ArrayDataBuilder::new(DataType::Int32)
4189            .len(length)
4190            .nulls(None)
4191            .buffers(vec![
4192                ScalarBuffer::<i32>::from(vec![1; length]).into_inner(),
4193            ]);
4194
4195        builder.build().unwrap()
4196    }
4197
4198    #[test]
4199    fn empty_and_null_map_array_should_pass_validation() {
4200        let dt = DataType::Map(
4201            Field::new(
4202                Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
4203                DataType::Struct(Fields::from(vec![
4204                    Field::new(Field::MAP_KEY_FIELD_DEFAULT_NAME, DataType::Int32, false),
4205                    Field::new(Field::MAP_VALUE_FIELD_DEFAULT_NAME, DataType::Utf8, true),
4206                ])),
4207                false,
4208            )
4209            .into(),
4210            false,
4211        );
4212
4213        ArrayData::new_empty(&dt).validate_full().unwrap();
4214        ArrayData::new_null(&dt, 1).validate_full().unwrap();
4215    }
4216
4217    #[test]
4218    fn null_buffer_offset_is_independent_of_data_offset() {
4219        // 100 values sliced down to the last 50, so the data has offset 50.
4220        let int_data = ArrayData::builder(DataType::UInt32)
4221            .offset(50)
4222            .len(50)
4223            .add_buffer(Buffer::from_vec(vec![0_u32; 100]))
4224            .build()
4225            .unwrap();
4226        int_data.validate().unwrap();
4227
4228        // A null buffer that happens to share the data's offset.
4229        let nulls = NullBuffer::new(BooleanBuffer::from(vec![false; 100]).slice(0, 50));
4230        let with_sliced_nulls = int_data
4231            .clone()
4232            .into_builder()
4233            .nulls(Some(nulls))
4234            .build()
4235            .unwrap();
4236        with_sliced_nulls.validate().unwrap();
4237
4238        // The same 50 nulls at offset 0. ArrayData::offset does not apply to the
4239        // null buffer, so this is just as valid and must not be rejected.
4240        let nulls = NullBuffer::new(BooleanBuffer::from(vec![false; 50]));
4241        let with_unsliced_nulls = int_data.into_builder().nulls(Some(nulls)).build().unwrap();
4242        with_unsliced_nulls.validate().unwrap();
4243        assert_eq!(with_unsliced_nulls.null_count(), 50);
4244    }
4245
4246    fn test_both_builder_and_array_data(
4247        data_type: DataType,
4248        len: usize,
4249        null_bit_buffer: Option<Buffer>,
4250        offset: usize,
4251        buffers: Vec<Buffer>,
4252        child_data: Vec<ArrayData>,
4253    ) -> [Result<ArrayData, ArrowError>; 2] {
4254        let from_builder_res = ArrayData::builder(data_type.clone())
4255            .len(len)
4256            .add_buffers(buffers.clone())
4257            .null_bit_buffer(null_bit_buffer.clone())
4258            .offset(offset)
4259            .child_data(child_data.clone())
4260            .build();
4261
4262        let from_try_new_res =
4263            ArrayData::try_new(data_type, len, null_bit_buffer, offset, buffers, child_data);
4264
4265        [from_builder_res, from_try_new_res]
4266    }
4267
4268    #[test]
4269    fn test_new_null_empty_union() {
4270        for mode in [UnionMode::Sparse, UnionMode::Dense] {
4271            let data_type = DataType::Union(UnionFields::empty(), mode);
4272            let data = ArrayData::new_null(&data_type, 0);
4273            data.validate_full()
4274                .expect("an empty union of length zero is valid");
4275            assert_eq!(data.len(), 0);
4276            assert!(data.child_data().is_empty());
4277        }
4278    }
4279
4280    #[test]
4281    #[should_panic(expected = "cannot construct null data from an empty union")]
4282    fn test_new_null_empty_union_with_slots() {
4283        let data_type = DataType::Union(UnionFields::empty(), UnionMode::Dense);
4284        let _ = ArrayData::new_null(&data_type, 1);
4285    }
4286
4287    #[test]
4288    fn test_union_validate_type_ids() {
4289        let dt = DataType::Union(
4290            UnionFields::try_new(
4291                vec![5],
4292                vec![Arc::new(Field::new("a", DataType::Int32, true))],
4293            )
4294            .unwrap(),
4295            UnionMode::Sparse,
4296        );
4297
4298        let child = ArrayData::builder(DataType::Int32)
4299            .len(2)
4300            .add_buffer(make_i32_buffer(2))
4301            .build()
4302            .unwrap();
4303
4304        let err = ArrayDataBuilder::new(dt)
4305            .len(2)
4306            .offset(0)
4307            .buffers(vec![vec![5_i8, 2].into()])
4308            .child_data(vec![child])
4309            .build()
4310            .unwrap_err();
4311        assert_eq!(
4312            err.to_string(),
4313            "Invalid argument error: Type id values must match one of the field type ids, got 2 at index 1"
4314        );
4315    }
4316
4317    #[test]
4318    fn test_union_validate_dense_offsets() {
4319        let dt = DataType::Union(
4320            UnionFields::try_new(
4321                vec![5],
4322                vec![Arc::new(Field::new("a", DataType::Int32, true))],
4323            )
4324            .unwrap(),
4325            UnionMode::Dense,
4326        );
4327
4328        let child = ArrayData::builder(DataType::Int32)
4329            .len(2)
4330            .add_buffer(make_i32_buffer(2))
4331            .build()
4332            .unwrap();
4333
4334        let err = ArrayDataBuilder::new(dt.clone())
4335            .len(2)
4336            // 2nd offset '10' is out of bounds
4337            .buffers(vec![vec![5_i8, 5].into(), vec![0_i32, 10].into()])
4338            .child_data(vec![child.clone()])
4339            .build()
4340            .unwrap_err();
4341        assert_eq!(
4342            err.to_string(),
4343            "Invalid argument error: Offsets must be non-negative and within the length of the child array"
4344        );
4345
4346        let err = ArrayDataBuilder::new(dt)
4347            .len(2)
4348            // 2nd offset is negative
4349            .buffers(vec![vec![5_i8, 5].into(), vec![0_i32, -1].into()])
4350            .child_data(vec![child])
4351            .build()
4352            .unwrap_err();
4353        assert_eq!(
4354            err.to_string(),
4355            "Invalid argument error: Offsets must be non-negative and within the length of the child array"
4356        );
4357    }
4358}