arrow_array/array/
byte_view_array.rs

1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements.  See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership.  The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License.  You may obtain a copy of the License at
8//
9//   http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied.  See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use crate::array::print_long_array;
19use crate::builder::{ArrayBuilder, GenericByteViewBuilder};
20use crate::iterator::ArrayIter;
21use crate::types::bytes::ByteArrayNativeType;
22use crate::types::{BinaryViewType, ByteViewType, StringViewType};
23use crate::{Array, ArrayAccessor, ArrayRef, GenericByteArray, OffsetSizeTrait, Scalar};
24use arrow_buffer::{ArrowNativeType, Buffer, NullBuffer, ScalarBuffer};
25use arrow_data::{ArrayData, ArrayDataBuilder, ByteView, MAX_INLINE_VIEW_LEN};
26use arrow_schema::{ArrowError, DataType};
27use core::str;
28use num_traits::ToPrimitive;
29use std::any::Any;
30use std::cmp::Ordering;
31use std::fmt::Debug;
32use std::marker::PhantomData;
33use std::sync::Arc;
34
35use super::ByteArrayType;
36
37/// [Variable-size Binary View Layout]: An array of variable length bytes views.
38///
39/// This array type is used to store variable length byte data (e.g. Strings, Binary)
40/// and has efficient operations such as `take`, `filter`, and comparison.
41///
42/// [Variable-size Binary View Layout]: https://arrow.apache.org/docs/format/Columnar.html#variable-size-binary-view-layout
43///
44/// This is different from [`GenericByteArray`], which also stores variable
45/// length byte data, as it represents strings with an offset and length. `take`
46/// and `filter` like operations are implemented by manipulating the "views"
47/// (`u128`) without modifying the bytes. Each view also stores an inlined
48/// prefix which speed up comparisons.
49///
50/// # See Also
51///
52/// * [`StringViewArray`] for storing utf8 encoded string data
53/// * [`BinaryViewArray`] for storing bytes
54/// * [`ByteView`] to interpret `u128`s layout of the views.
55///
56/// [`ByteView`]: arrow_data::ByteView
57///
58/// # Layout: "views" and buffers
59///
60/// A `GenericByteViewArray` stores variable length byte strings. An array of
61/// `N` elements is stored as `N` fixed length "views" and a variable number
62/// of variable length "buffers".
63///
64/// Each view is a `u128` value whose layout is different depending on the
65/// length of the string stored at that location:
66///
67/// ```text
68///                         ┌──────┬────────────────────────┐
69///                         │length│      string value      │
70///    Strings (len <= 12)  │      │    (padded with 0)     │
71///                         └──────┴────────────────────────┘
72///                          0    31                      127
73///
74///                         ┌───────┬───────┬───────┬───────┐
75///                         │length │prefix │  buf  │offset │
76///    Strings (len > 12)   │       │       │ index │       │
77///                         └───────┴───────┴───────┴───────┘
78///                          0    31       63      95    127
79/// ```
80///
81/// * Strings with length <= 12 ([`MAX_INLINE_VIEW_LEN`]) are stored directly in
82///   the view. See [`Self::inline_value`] to access the inlined prefix from a
83///   short view.
84///
85/// * Strings with length > 12: The first four bytes are stored inline in the
86///   view and the entire string is stored in one of the buffers. See [`ByteView`]
87///   to access the fields of the these views.
88///
89/// As with other arrays, the optimized kernels in [`arrow_compute`] are likely
90/// the easiest and fastest way to work with this data. However, it is possible
91/// to access the views and buffers directly for more control.
92///
93/// For example
94///
95/// ```rust
96/// # use arrow_array::StringViewArray;
97/// # use arrow_array::Array;
98/// use arrow_data::ByteView;
99/// let array = StringViewArray::from(vec![
100///   "hello",
101///   "this string is longer than 12 bytes",
102///   "this string is also longer than 12 bytes"
103/// ]);
104///
105/// // ** Examine the first view (short string) **
106/// assert!(array.is_valid(0)); // Check for nulls
107/// let short_view: u128 = array.views()[0]; // "hello"
108/// // get length of the string
109/// let len = short_view as u32;
110/// assert_eq!(len, 5); // strings less than 12 bytes are stored in the view
111/// // SAFETY: `view` is a valid view
112/// let value = unsafe {
113///   StringViewArray::inline_value(&short_view, len as usize)
114/// };
115/// assert_eq!(value, b"hello");
116///
117/// // ** Examine the third view (long string) **
118/// assert!(array.is_valid(12)); // Check for nulls
119/// let long_view: u128 = array.views()[2]; // "this string is also longer than 12 bytes"
120/// let len = long_view as u32;
121/// assert_eq!(len, 40); // strings longer than 12 bytes are stored in the buffer
122/// let view = ByteView::from(long_view); // use ByteView to access the fields
123/// assert_eq!(view.length, 40);
124/// assert_eq!(view.buffer_index, 0);
125/// assert_eq!(view.offset, 35); // data starts after the first long string
126/// // Views for long strings store a 4 byte prefix
127/// let prefix = view.prefix.to_le_bytes();
128/// assert_eq!(&prefix, b"this");
129/// let value = array.value(2); // get the string value (see `value` implementation for how to access the bytes directly)
130/// assert_eq!(value, "this string is also longer than 12 bytes");
131/// ```
132///
133/// [`MAX_INLINE_VIEW_LEN`]: arrow_data::MAX_INLINE_VIEW_LEN
134/// [`arrow_compute`]: https://docs.rs/arrow/latest/arrow/compute/index.html
135///
136/// Unlike [`GenericByteArray`], there are no constraints on the offsets other
137/// than they must point into a valid buffer. However, they can be out of order,
138/// non continuous and overlapping.
139///
140/// For example, in the following diagram, the strings "FishWasInTownToday" and
141/// "CrumpleFacedFish" are both longer than 12 bytes and thus are stored in a
142/// separate buffer while the string "LavaMonster" is stored inlined in the
143/// view. In this case, the same bytes for "Fish" are used to store both strings.
144///
145/// [`ByteView`]: arrow_data::ByteView
146///
147/// ```text
148///                                                                            ┌───┐
149///                         ┌──────┬──────┬──────┬──────┐               offset │...│
150/// "FishWasInTownTodayYay" │  21  │ Fish │  0   │ 115  │─ ─              103  │Mr.│
151///                         └──────┴──────┴──────┴──────┘   │      ┌ ─ ─ ─ ─ ▶ │Cru│
152///                         ┌──────┬──────┬──────┬──────┐                      │mpl│
153/// "CrumpleFacedFish"      │  16  │ Crum │  0   │ 103  │─ ─│─ ─ ─ ┘           │eFa│
154///                         └──────┴──────┴──────┴──────┘                      │ced│
155///                         ┌──────┬────────────────────┐   └ ─ ─ ─ ─ ─ ─ ─ ─ ▶│Fis│
156/// "LavaMonster"           │  11  │   LavaMonster      │                      │hWa│
157///                         └──────┴────────────────────┘               offset │sIn│
158///                                                                       115  │Tow│
159///                                                                            │nTo│
160///                                                                            │day│
161///                                  u128 "views"                              │Yay│
162///                                                                   buffer 0 │...│
163///                                                                            └───┘
164/// ```
165pub struct GenericByteViewArray<T: ByteViewType + ?Sized> {
166    data_type: DataType,
167    views: ScalarBuffer<u128>,
168    buffers: Vec<Buffer>,
169    phantom: PhantomData<T>,
170    nulls: Option<NullBuffer>,
171}
172
173impl<T: ByteViewType + ?Sized> Clone for GenericByteViewArray<T> {
174    fn clone(&self) -> Self {
175        Self {
176            data_type: T::DATA_TYPE,
177            views: self.views.clone(),
178            buffers: self.buffers.clone(),
179            nulls: self.nulls.clone(),
180            phantom: Default::default(),
181        }
182    }
183}
184
185impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
186    /// Create a new [`GenericByteViewArray`] from the provided parts, panicking on failure
187    ///
188    /// # Panics
189    ///
190    /// Panics if [`GenericByteViewArray::try_new`] returns an error
191    pub fn new(views: ScalarBuffer<u128>, buffers: Vec<Buffer>, nulls: Option<NullBuffer>) -> Self {
192        Self::try_new(views, buffers, nulls).unwrap()
193    }
194
195    /// Create a new [`GenericByteViewArray`] from the provided parts, returning an error on failure
196    ///
197    /// # Errors
198    ///
199    /// * `views.len() != nulls.len()`
200    /// * [ByteViewType::validate] fails
201    pub fn try_new(
202        views: ScalarBuffer<u128>,
203        buffers: Vec<Buffer>,
204        nulls: Option<NullBuffer>,
205    ) -> Result<Self, ArrowError> {
206        T::validate(&views, &buffers)?;
207
208        if let Some(n) = nulls.as_ref() {
209            if n.len() != views.len() {
210                return Err(ArrowError::InvalidArgumentError(format!(
211                    "Incorrect length of null buffer for {}ViewArray, expected {} got {}",
212                    T::PREFIX,
213                    views.len(),
214                    n.len(),
215                )));
216            }
217        }
218
219        Ok(Self {
220            data_type: T::DATA_TYPE,
221            views,
222            buffers,
223            nulls,
224            phantom: Default::default(),
225        })
226    }
227
228    /// Create a new [`GenericByteViewArray`] from the provided parts, without validation
229    ///
230    /// # Safety
231    ///
232    /// Safe if [`Self::try_new`] would not error
233    pub unsafe fn new_unchecked(
234        views: ScalarBuffer<u128>,
235        buffers: Vec<Buffer>,
236        nulls: Option<NullBuffer>,
237    ) -> Self {
238        if cfg!(feature = "force_validate") {
239            return Self::new(views, buffers, nulls);
240        }
241
242        Self {
243            data_type: T::DATA_TYPE,
244            phantom: Default::default(),
245            views,
246            buffers,
247            nulls,
248        }
249    }
250
251    /// Create a new [`GenericByteViewArray`] of length `len` where all values are null
252    pub fn new_null(len: usize) -> Self {
253        Self {
254            data_type: T::DATA_TYPE,
255            views: vec![0; len].into(),
256            buffers: vec![],
257            nulls: Some(NullBuffer::new_null(len)),
258            phantom: Default::default(),
259        }
260    }
261
262    /// Create a new [`Scalar`] from `value`
263    pub fn new_scalar(value: impl AsRef<T::Native>) -> Scalar<Self> {
264        Scalar::new(Self::from_iter_values(std::iter::once(value)))
265    }
266
267    /// Creates a [`GenericByteViewArray`] based on an iterator of values without nulls
268    pub fn from_iter_values<Ptr, I>(iter: I) -> Self
269    where
270        Ptr: AsRef<T::Native>,
271        I: IntoIterator<Item = Ptr>,
272    {
273        let iter = iter.into_iter();
274        let mut builder = GenericByteViewBuilder::<T>::with_capacity(iter.size_hint().0);
275        for v in iter {
276            builder.append_value(v);
277        }
278        builder.finish()
279    }
280
281    /// Deconstruct this array into its constituent parts
282    pub fn into_parts(self) -> (ScalarBuffer<u128>, Vec<Buffer>, Option<NullBuffer>) {
283        (self.views, self.buffers, self.nulls)
284    }
285
286    /// Returns the views buffer
287    #[inline]
288    pub fn views(&self) -> &ScalarBuffer<u128> {
289        &self.views
290    }
291
292    /// Returns the buffers storing string data
293    #[inline]
294    pub fn data_buffers(&self) -> &[Buffer] {
295        &self.buffers
296    }
297
298    /// Returns the element at index `i`
299    ///
300    /// Note: This method does not check for nulls and the value is arbitrary
301    /// (but still well-defined) if [`is_null`](Self::is_null) returns true for the index.
302    ///
303    /// # Panics
304    /// Panics if index `i` is out of bounds.
305    pub fn value(&self, i: usize) -> &T::Native {
306        assert!(
307            i < self.len(),
308            "Trying to access an element at index {} from a {}ViewArray of length {}",
309            i,
310            T::PREFIX,
311            self.len()
312        );
313
314        unsafe { self.value_unchecked(i) }
315    }
316
317    /// Returns the element at index `i` without bounds checking
318    ///
319    /// Note: This method does not check for nulls and the value is arbitrary
320    /// if [`is_null`](Self::is_null) returns true for the index.
321    ///
322    /// # Safety
323    ///
324    /// Caller is responsible for ensuring that the index is within the bounds
325    /// of the array
326    pub unsafe fn value_unchecked(&self, idx: usize) -> &T::Native {
327        let v = unsafe { self.views.get_unchecked(idx) };
328        let len = *v as u32;
329        let b = if len <= MAX_INLINE_VIEW_LEN {
330            unsafe { Self::inline_value(v, len as usize) }
331        } else {
332            let view = ByteView::from(*v);
333            let data = unsafe { self.buffers.get_unchecked(view.buffer_index as usize) };
334            let offset = view.offset as usize;
335            unsafe { data.get_unchecked(offset..offset + len as usize) }
336        };
337        unsafe { T::Native::from_bytes_unchecked(b) }
338    }
339
340    /// Returns the first `len` bytes the inline value of the view.
341    ///
342    /// # Safety
343    /// - The `view` must be a valid element from `Self::views()` that adheres to the view layout.
344    /// - The `len` must be the length of the inlined value. It should never be larger than [`MAX_INLINE_VIEW_LEN`].
345    #[inline(always)]
346    pub unsafe fn inline_value(view: &u128, len: usize) -> &[u8] {
347        debug_assert!(len <= MAX_INLINE_VIEW_LEN as usize);
348        unsafe {
349            std::slice::from_raw_parts((view as *const u128 as *const u8).wrapping_add(4), len)
350        }
351    }
352
353    /// Constructs a new iterator for iterating over the values of this array
354    pub fn iter(&self) -> ArrayIter<&Self> {
355        ArrayIter::new(self)
356    }
357
358    /// Returns an iterator over the bytes of this array, including null values
359    pub fn bytes_iter(&self) -> impl Iterator<Item = &[u8]> {
360        self.views.iter().map(move |v| {
361            let len = *v as u32;
362            if len <= MAX_INLINE_VIEW_LEN {
363                unsafe { Self::inline_value(v, len as usize) }
364            } else {
365                let view = ByteView::from(*v);
366                let data = &self.buffers[view.buffer_index as usize];
367                let offset = view.offset as usize;
368                unsafe { data.get_unchecked(offset..offset + len as usize) }
369            }
370        })
371    }
372
373    /// Returns an iterator over the first `prefix_len` bytes of each array
374    /// element, including null values.
375    ///
376    /// If `prefix_len` is larger than the element's length, the iterator will
377    /// return an empty slice (`&[]`).
378    pub fn prefix_bytes_iter(&self, prefix_len: usize) -> impl Iterator<Item = &[u8]> {
379        self.views().into_iter().map(move |v| {
380            let len = (*v as u32) as usize;
381
382            if len < prefix_len {
383                return &[] as &[u8];
384            }
385
386            if prefix_len <= 4 || len as u32 <= MAX_INLINE_VIEW_LEN {
387                unsafe { StringViewArray::inline_value(v, prefix_len) }
388            } else {
389                let view = ByteView::from(*v);
390                let data = unsafe {
391                    self.data_buffers()
392                        .get_unchecked(view.buffer_index as usize)
393                };
394                let offset = view.offset as usize;
395                unsafe { data.get_unchecked(offset..offset + prefix_len) }
396            }
397        })
398    }
399
400    /// Returns an iterator over the last `suffix_len` bytes of each array
401    /// element, including null values.
402    ///
403    /// Note that for [`StringViewArray`] the last bytes may start in the middle
404    /// of a UTF-8 codepoint, and thus may not be a valid `&str`.
405    ///
406    /// If `suffix_len` is larger than the element's length, the iterator will
407    /// return an empty slice (`&[]`).
408    pub fn suffix_bytes_iter(&self, suffix_len: usize) -> impl Iterator<Item = &[u8]> {
409        self.views().into_iter().map(move |v| {
410            let len = (*v as u32) as usize;
411
412            if len < suffix_len {
413                return &[] as &[u8];
414            }
415
416            if len as u32 <= MAX_INLINE_VIEW_LEN {
417                unsafe { &StringViewArray::inline_value(v, len)[len - suffix_len..] }
418            } else {
419                let view = ByteView::from(*v);
420                let data = unsafe {
421                    self.data_buffers()
422                        .get_unchecked(view.buffer_index as usize)
423                };
424                let offset = view.offset as usize;
425                unsafe { data.get_unchecked(offset + len - suffix_len..offset + len) }
426            }
427        })
428    }
429
430    /// Returns a zero-copy slice of this array with the indicated offset and length.
431    pub fn slice(&self, offset: usize, length: usize) -> Self {
432        Self {
433            data_type: T::DATA_TYPE,
434            views: self.views.slice(offset, length),
435            buffers: self.buffers.clone(),
436            nulls: self.nulls.as_ref().map(|n| n.slice(offset, length)),
437            phantom: Default::default(),
438        }
439    }
440
441    /// Returns a "compacted" version of this array
442    ///
443    /// The original array will *not* be modified
444    ///
445    /// # Garbage Collection
446    ///
447    /// Before GC:
448    /// ```text
449    ///                                        ┌──────┐
450    ///                                        │......│
451    ///                                        │......│
452    /// ┌────────────────────┐       ┌ ─ ─ ─ ▶ │Data1 │   Large buffer
453    /// │       View 1       │─ ─ ─ ─          │......│  with data that
454    /// ├────────────────────┤                 │......│ is not referred
455    /// │       View 2       │─ ─ ─ ─ ─ ─ ─ ─▶ │Data2 │ to by View 1 or
456    /// └────────────────────┘                 │......│      View 2
457    ///                                        │......│
458    ///    2 views, refer to                   │......│
459    ///   small portions of a                  └──────┘
460    ///      large buffer
461    /// ```
462    ///
463    /// After GC:
464    ///
465    /// ```text
466    /// ┌────────────────────┐                 ┌─────┐    After gc, only
467    /// │       View 1       │─ ─ ─ ─ ─ ─ ─ ─▶ │Data1│     data that is
468    /// ├────────────────────┤       ┌ ─ ─ ─ ▶ │Data2│    pointed to by
469    /// │       View 2       │─ ─ ─ ─          └─────┘     the views is
470    /// └────────────────────┘                                 left
471    ///
472    ///
473    ///         2 views
474    /// ```
475    /// This method will compact the data buffers by recreating the view array and only include the data
476    /// that is pointed to by the views.
477    ///
478    /// Note that it will copy the array regardless of whether the original array is compact.
479    /// Use with caution as this can be an expensive operation, only use it when you are sure that the view
480    /// array is significantly smaller than when it is originally created, e.g., after filtering or slicing.
481    ///
482    /// Note: this function does not attempt to canonicalize / deduplicate values. For this
483    /// feature see  [`GenericByteViewBuilder::with_deduplicate_strings`].
484    pub fn gc(&self) -> Self {
485        // 1) Read basic properties once
486        let len = self.len(); // number of elements
487        let nulls = self.nulls().cloned(); // reuse & clone existing null bitmap
488
489        // 1.5) Fast path: if there are no buffers, just reuse original views and no data blocks
490        if self.data_buffers().is_empty() {
491            return unsafe {
492                GenericByteViewArray::new_unchecked(
493                    self.views().clone(),
494                    vec![], // empty data blocks
495                    nulls,
496                )
497            };
498        }
499
500        // 2) Calculate total size of all non-inline data and detect if any exists
501        let total_large = self.total_buffer_bytes_used();
502
503        // 2.5) Fast path: if there is no non-inline data, avoid buffer allocation & processing
504        if total_large == 0 {
505            // Views are inline-only or all null; just reuse original views and no data blocks
506            return unsafe {
507                GenericByteViewArray::new_unchecked(
508                    self.views().clone(),
509                    vec![], // empty data blocks
510                    nulls,
511                )
512            };
513        }
514
515        // 3) Allocate exactly capacity for all non-inline data
516        let mut data_buf = Vec::with_capacity(total_large);
517
518        // 4) Iterate over views and process each inline/non-inline view
519        let views_buf: Vec<u128> = (0..len)
520            .map(|i| unsafe { self.copy_view_to_buffer(i, &mut data_buf) })
521            .collect();
522
523        // 5) Wrap up buffers
524        let data_block = Buffer::from_vec(data_buf);
525        let views_scalar = ScalarBuffer::from(views_buf);
526        let data_blocks = vec![data_block];
527
528        // SAFETY: views_scalar, data_blocks, and nulls are correctly aligned and sized
529        unsafe { GenericByteViewArray::new_unchecked(views_scalar, data_blocks, nulls) }
530    }
531
532    /// Copy the i‑th view into `data_buf` if it refers to an out‑of‑line buffer.
533    ///
534    /// # Safety
535    ///
536    /// - `i < self.len()`.
537    /// - Every element in `self.views()` must currently refer to a valid slice
538    ///   inside one of `self.buffers`.
539    /// - `data_buf` must be ready to have additional bytes appended.
540    /// - After this call, the returned view will have its
541    ///   `buffer_index` reset to `0` and its `offset` updated so that it points
542    ///   into the bytes just appended at the end of `data_buf`.
543    #[inline(always)]
544    unsafe fn copy_view_to_buffer(&self, i: usize, data_buf: &mut Vec<u8>) -> u128 {
545        // SAFETY: `i < self.len()` ensures this is in‑bounds.
546        let raw_view = unsafe { *self.views().get_unchecked(i) };
547        let mut bv = ByteView::from(raw_view);
548
549        // Inline‑small views stay as‑is.
550        if bv.length <= MAX_INLINE_VIEW_LEN {
551            raw_view
552        } else {
553            // SAFETY: `bv.buffer_index` and `bv.offset..bv.offset+bv.length`
554            // must both lie within valid ranges for `self.buffers`.
555            let buffer = unsafe { self.buffers.get_unchecked(bv.buffer_index as usize) };
556            let start = bv.offset as usize;
557            let end = start + bv.length as usize;
558            let slice = unsafe { buffer.get_unchecked(start..end) };
559
560            // Copy out‑of‑line data into our single “0” buffer.
561            let new_offset = data_buf.len() as u32;
562            data_buf.extend_from_slice(slice);
563
564            bv.buffer_index = 0;
565            bv.offset = new_offset;
566            bv.into()
567        }
568    }
569
570    /// Returns the total number of bytes used by all non inlined views in all
571    /// buffers.
572    ///
573    /// Note this does not account for views that point at the same underlying
574    /// data in buffers
575    ///
576    /// For example, if the array has three strings views:
577    /// * View with length = 9 (inlined)
578    /// * View with length = 32 (non inlined)
579    /// * View with length = 16 (non inlined)
580    ///
581    /// Then this method would report 48
582    pub fn total_buffer_bytes_used(&self) -> usize {
583        self.views()
584            .iter()
585            .map(|v| {
586                let len = *v as u32;
587                if len > MAX_INLINE_VIEW_LEN {
588                    len as usize
589                } else {
590                    0
591                }
592            })
593            .sum()
594    }
595
596    /// Compare two [`GenericByteViewArray`] at index `left_idx` and `right_idx`
597    ///
598    /// Comparing two ByteView types are non-trivial.
599    /// It takes a bit of patience to understand why we don't just compare two &[u8] directly.
600    ///
601    /// ByteView types give us the following two advantages, and we need to be careful not to lose them:
602    /// (1) For string/byte smaller than [`MAX_INLINE_VIEW_LEN`] bytes, the entire data is inlined in the view.
603    ///     Meaning that reading one array element requires only one memory access
604    ///     (two memory access required for StringArray, one for offset buffer, the other for value buffer).
605    ///
606    /// (2) For string/byte larger than [`MAX_INLINE_VIEW_LEN`] bytes, we can still be faster than (for certain operations) StringArray/ByteArray,
607    ///     thanks to the inlined 4 bytes.
608    ///     Consider equality check:
609    ///     If the first four bytes of the two strings are different, we can return false immediately (with just one memory access).
610    ///
611    /// If we directly compare two &[u8], we materialize the entire string (i.e., make multiple memory accesses), which might be unnecessary.
612    /// - Most of the time (eq, ord), we only need to look at the first 4 bytes to know the answer,
613    ///   e.g., if the inlined 4 bytes are different, we can directly return unequal without looking at the full string.
614    ///
615    /// # Order check flow
616    /// (1) if both string are smaller than [`MAX_INLINE_VIEW_LEN`] bytes, we can directly compare the data inlined to the view.
617    /// (2) if any of the string is larger than [`MAX_INLINE_VIEW_LEN`] bytes, we need to compare the full string.
618    ///     (2.1) if the inlined 4 bytes are different, we can return the result immediately.
619    ///     (2.2) o.w., we need to compare the full string.
620    ///
621    /// # Safety
622    /// The left/right_idx must within range of each array
623    pub unsafe fn compare_unchecked(
624        left: &GenericByteViewArray<T>,
625        left_idx: usize,
626        right: &GenericByteViewArray<T>,
627        right_idx: usize,
628    ) -> Ordering {
629        let l_view = unsafe { left.views().get_unchecked(left_idx) };
630        let l_byte_view = ByteView::from(*l_view);
631
632        let r_view = unsafe { right.views().get_unchecked(right_idx) };
633        let r_byte_view = ByteView::from(*r_view);
634
635        let l_len = l_byte_view.length;
636        let r_len = r_byte_view.length;
637
638        if l_len <= 12 && r_len <= 12 {
639            return Self::inline_key_fast(*l_view).cmp(&Self::inline_key_fast(*r_view));
640        }
641
642        // one of the string is larger than 12 bytes,
643        // we then try to compare the inlined data first
644
645        // Note: In theory, ByteView is only used for string which is larger than 12 bytes,
646        // but we can still use it to get the inlined prefix for shorter strings.
647        // The prefix is always the first 4 bytes of the view, for both short and long strings.
648        let l_inlined_be = l_byte_view.prefix.swap_bytes();
649        let r_inlined_be = r_byte_view.prefix.swap_bytes();
650        if l_inlined_be != r_inlined_be {
651            return l_inlined_be.cmp(&r_inlined_be);
652        }
653
654        // unfortunately, we need to compare the full data
655        let l_full_data: &[u8] = unsafe { left.value_unchecked(left_idx).as_ref() };
656        let r_full_data: &[u8] = unsafe { right.value_unchecked(right_idx).as_ref() };
657
658        l_full_data.cmp(r_full_data)
659    }
660
661    /// Builds a 128-bit composite key for an inline value:
662    ///
663    /// - High 96 bits: the inline data in big-endian byte order (for correct lexicographical sorting).
664    /// - Low  32 bits: the length in big-endian byte order, acting as a tiebreaker so shorter strings
665    ///   (or those with fewer meaningful bytes) always numerically sort before longer ones.
666    ///
667    /// This function extracts the length and the 12-byte inline string data from the raw
668    /// little-endian `u128` representation, converts them to big-endian ordering, and packs them
669    /// into a single `u128` value suitable for fast, branchless comparisons.
670    ///
671    /// # Why include length?
672    ///
673    /// A pure 96-bit content comparison can’t distinguish between two values whose inline bytes
674    /// compare equal—either because one is a true prefix of the other or because zero-padding
675    /// hides extra bytes. By tucking the 32-bit length into the lower bits, a single `u128` compare
676    /// handles both content and length in one go.
677    ///
678    /// Example: comparing "bar" (3 bytes) vs "bar\0" (4 bytes)
679    ///
680    /// | String     | Bytes 0–4 (length LE) | Bytes 4–16 (data + padding)    |
681    /// |------------|-----------------------|---------------------------------|
682    /// | `"bar"`   | `03 00 00 00`         | `62 61 72` + 9 × `00`           |
683    /// | `"bar\0"`| `04 00 00 00`         | `62 61 72 00` + 8 × `00`        |
684    ///
685    /// Both inline parts become `62 61 72 00…00`, so they tie on content. The length field
686    /// then differentiates:
687    ///
688    /// ```text
689    /// key("bar")   = 0x0000000000000000000062617200000003
690    /// key("bar\0") = 0x0000000000000000000062617200000004
691    /// ⇒ key("bar") < key("bar\0")
692    /// ```
693    /// # Inlining and Endianness
694    ///
695    /// - We start by calling `.to_le_bytes()` on the `raw` `u128`, because Rust’s native in‑memory
696    ///   representation is little‑endian on x86/ARM.
697    /// - We extract the low 32 bits numerically (`raw as u32`)—this step is endianness‑free.
698    /// - We copy the 12 bytes of inline data (original order) into `buf[0..12]`.
699    /// - We serialize `length` as big‑endian into `buf[12..16]`.
700    /// - Finally, `u128::from_be_bytes(buf)` treats `buf[0]` as the most significant byte
701    ///   and `buf[15]` as the least significant, producing a `u128` whose integer value
702    ///   directly encodes “inline data then length” in big‑endian form.
703    ///
704    /// This ensures that a simple `u128` comparison is equivalent to the desired
705    /// lexicographical comparison of the inline bytes followed by length.
706    #[inline(always)]
707    pub fn inline_key_fast(raw: u128) -> u128 {
708        // 1. Decompose `raw` into little‑endian bytes:
709        //    - raw_bytes[0..4]  = length in LE
710        //    - raw_bytes[4..16] = inline string data
711        let raw_bytes = raw.to_le_bytes();
712
713        // 2. Numerically truncate to get the low 32‑bit length (endianness‑free).
714        let length = raw as u32;
715
716        // 3. Build a 16‑byte buffer in big‑endian order:
717        //    - buf[0..12]  = inline string bytes (in original order)
718        //    - buf[12..16] = length.to_be_bytes() (BE)
719        let mut buf = [0u8; 16];
720        buf[0..12].copy_from_slice(&raw_bytes[4..16]); // inline data
721
722        // Why convert length to big-endian for comparison?
723        //
724        // Rust (on most platforms) stores integers in little-endian format,
725        // meaning the least significant byte is at the lowest memory address.
726        // For example, an u32 value like 0x22345677 is stored in memory as:
727        //
728        //   [0x77, 0x56, 0x34, 0x22]  // little-endian layout
729        //    ^     ^     ^     ^
730        //  LSB   ↑↑↑           MSB
731        //
732        // This layout is efficient for arithmetic but *not* suitable for
733        // lexicographic (dictionary-style) comparison of byte arrays.
734        //
735        // To compare values by byte order—e.g., for sorted keys or binary trees—
736        // we must convert them to **big-endian**, where:
737        //
738        //   - The most significant byte (MSB) comes first (index 0)
739        //   - The least significant byte (LSB) comes last (index N-1)
740        //
741        // In big-endian, the same u32 = 0x22345677 would be represented as:
742        //
743        //   [0x22, 0x34, 0x56, 0x77]
744        //
745        // This ordering aligns with natural string/byte sorting, so calling
746        // `.to_be_bytes()` allows us to construct
747        // keys where standard numeric comparison (e.g., `<`, `>`) behaves
748        // like lexicographic byte comparison.
749        buf[12..16].copy_from_slice(&length.to_be_bytes()); // length in BE
750
751        // 4. Deserialize the buffer as a big‑endian u128:
752        //    buf[0] is MSB, buf[15] is LSB.
753        // Details:
754        // Note on endianness and layout:
755        //
756        // Although `buf[0]` is stored at the lowest memory address,
757        // calling `u128::from_be_bytes(buf)` interprets it as the **most significant byte (MSB)**,
758        // and `buf[15]` as the **least significant byte (LSB)**.
759        //
760        // This is the core principle of **big-endian decoding**:
761        //   - Byte at index 0 maps to bits 127..120 (highest)
762        //   - Byte at index 1 maps to bits 119..112
763        //   - ...
764        //   - Byte at index 15 maps to bits 7..0 (lowest)
765        //
766        // So even though memory layout goes from low to high (left to right),
767        // big-endian treats the **first byte** as highest in value.
768        //
769        // This guarantees that comparing two `u128` keys is equivalent to lexicographically
770        // comparing the original inline bytes, followed by length.
771        u128::from_be_bytes(buf)
772    }
773}
774
775impl<T: ByteViewType + ?Sized> Debug for GenericByteViewArray<T> {
776    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
777        write!(f, "{}ViewArray\n[\n", T::PREFIX)?;
778        print_long_array(self, f, |array, index, f| {
779            std::fmt::Debug::fmt(&array.value(index), f)
780        })?;
781        write!(f, "]")
782    }
783}
784
785impl<T: ByteViewType + ?Sized> Array for GenericByteViewArray<T> {
786    fn as_any(&self) -> &dyn Any {
787        self
788    }
789
790    fn to_data(&self) -> ArrayData {
791        self.clone().into()
792    }
793
794    fn into_data(self) -> ArrayData {
795        self.into()
796    }
797
798    fn data_type(&self) -> &DataType {
799        &self.data_type
800    }
801
802    fn slice(&self, offset: usize, length: usize) -> ArrayRef {
803        Arc::new(self.slice(offset, length))
804    }
805
806    fn len(&self) -> usize {
807        self.views.len()
808    }
809
810    fn is_empty(&self) -> bool {
811        self.views.is_empty()
812    }
813
814    fn shrink_to_fit(&mut self) {
815        self.views.shrink_to_fit();
816        self.buffers.iter_mut().for_each(|b| b.shrink_to_fit());
817        self.buffers.shrink_to_fit();
818        if let Some(nulls) = &mut self.nulls {
819            nulls.shrink_to_fit();
820        }
821    }
822
823    fn offset(&self) -> usize {
824        0
825    }
826
827    fn nulls(&self) -> Option<&NullBuffer> {
828        self.nulls.as_ref()
829    }
830
831    fn logical_null_count(&self) -> usize {
832        // More efficient that the default implementation
833        self.null_count()
834    }
835
836    fn get_buffer_memory_size(&self) -> usize {
837        let mut sum = self.buffers.iter().map(|b| b.capacity()).sum::<usize>();
838        sum += self.views.inner().capacity();
839        if let Some(x) = &self.nulls {
840            sum += x.buffer().capacity()
841        }
842        sum
843    }
844
845    fn get_array_memory_size(&self) -> usize {
846        std::mem::size_of::<Self>() + self.get_buffer_memory_size()
847    }
848}
849
850impl<'a, T: ByteViewType + ?Sized> ArrayAccessor for &'a GenericByteViewArray<T> {
851    type Item = &'a T::Native;
852
853    fn value(&self, index: usize) -> Self::Item {
854        GenericByteViewArray::value(self, index)
855    }
856
857    unsafe fn value_unchecked(&self, index: usize) -> Self::Item {
858        unsafe { GenericByteViewArray::value_unchecked(self, index) }
859    }
860}
861
862impl<'a, T: ByteViewType + ?Sized> IntoIterator for &'a GenericByteViewArray<T> {
863    type Item = Option<&'a T::Native>;
864    type IntoIter = ArrayIter<Self>;
865
866    fn into_iter(self) -> Self::IntoIter {
867        ArrayIter::new(self)
868    }
869}
870
871impl<T: ByteViewType + ?Sized> From<ArrayData> for GenericByteViewArray<T> {
872    fn from(value: ArrayData) -> Self {
873        let views = value.buffers()[0].clone();
874        let views = ScalarBuffer::new(views, value.offset(), value.len());
875        let buffers = value.buffers()[1..].to_vec();
876        Self {
877            data_type: T::DATA_TYPE,
878            views,
879            buffers,
880            nulls: value.nulls().cloned(),
881            phantom: Default::default(),
882        }
883    }
884}
885
886/// Efficiently convert a [`GenericByteArray`] to a [`GenericByteViewArray`]
887///
888/// For example this method can convert a [`StringArray`] to a
889/// [`StringViewArray`].
890///
891/// If the offsets are all less than u32::MAX, the new [`GenericByteViewArray`]
892/// is built without copying the underlying string data (views are created
893/// directly into the existing buffer)
894///
895/// [`StringArray`]: crate::StringArray
896impl<FROM, V> From<&GenericByteArray<FROM>> for GenericByteViewArray<V>
897where
898    FROM: ByteArrayType,
899    FROM::Offset: OffsetSizeTrait + ToPrimitive,
900    V: ByteViewType<Native = FROM::Native>,
901{
902    fn from(byte_array: &GenericByteArray<FROM>) -> Self {
903        let offsets = byte_array.offsets();
904
905        let can_reuse_buffer = match offsets.last() {
906            Some(offset) => offset.as_usize() < u32::MAX as usize,
907            None => true,
908        };
909
910        if can_reuse_buffer {
911            // build views directly pointing to the existing buffer
912            let len = byte_array.len();
913            let mut views_builder = GenericByteViewBuilder::<V>::with_capacity(len);
914            let str_values_buf = byte_array.values().clone();
915            let block = views_builder.append_block(str_values_buf);
916            for (i, w) in offsets.windows(2).enumerate() {
917                let offset = w[0].as_usize();
918                let end = w[1].as_usize();
919                let length = end - offset;
920
921                if byte_array.is_null(i) {
922                    views_builder.append_null();
923                } else {
924                    // Safety: the input was a valid array so it valid UTF8 (if string). And
925                    // all offsets were valid
926                    unsafe {
927                        views_builder.append_view_unchecked(block, offset as u32, length as u32)
928                    }
929                }
930            }
931            assert_eq!(views_builder.len(), len);
932            views_builder.finish()
933        } else {
934            // Otherwise, create a new buffer for large strings
935            // TODO: the original buffer could still be used
936            // by making multiple slices of u32::MAX length
937            GenericByteViewArray::<V>::from_iter(byte_array.iter())
938        }
939    }
940}
941
942impl<T: ByteViewType + ?Sized> From<GenericByteViewArray<T>> for ArrayData {
943    fn from(mut array: GenericByteViewArray<T>) -> Self {
944        let len = array.len();
945        array.buffers.insert(0, array.views.into_inner());
946        let builder = ArrayDataBuilder::new(T::DATA_TYPE)
947            .len(len)
948            .buffers(array.buffers)
949            .nulls(array.nulls);
950
951        unsafe { builder.build_unchecked() }
952    }
953}
954
955impl<'a, Ptr, T> FromIterator<&'a Option<Ptr>> for GenericByteViewArray<T>
956where
957    Ptr: AsRef<T::Native> + 'a,
958    T: ByteViewType + ?Sized,
959{
960    fn from_iter<I: IntoIterator<Item = &'a Option<Ptr>>>(iter: I) -> Self {
961        iter.into_iter()
962            .map(|o| o.as_ref().map(|p| p.as_ref()))
963            .collect()
964    }
965}
966
967impl<Ptr, T: ByteViewType + ?Sized> FromIterator<Option<Ptr>> for GenericByteViewArray<T>
968where
969    Ptr: AsRef<T::Native>,
970{
971    fn from_iter<I: IntoIterator<Item = Option<Ptr>>>(iter: I) -> Self {
972        let iter = iter.into_iter();
973        let mut builder = GenericByteViewBuilder::<T>::with_capacity(iter.size_hint().0);
974        builder.extend(iter);
975        builder.finish()
976    }
977}
978
979/// A [`GenericByteViewArray`] of `[u8]`
980///
981/// See [`GenericByteViewArray`] for format and layout details.
982///
983/// # Example
984/// ```
985/// use arrow_array::BinaryViewArray;
986/// let array = BinaryViewArray::from_iter_values(vec![b"hello" as &[u8], b"world", b"lulu", b"large payload over 12 bytes"]);
987/// assert_eq!(array.value(0), b"hello");
988/// assert_eq!(array.value(3), b"large payload over 12 bytes");
989/// ```
990pub type BinaryViewArray = GenericByteViewArray<BinaryViewType>;
991
992impl BinaryViewArray {
993    /// Convert the [`BinaryViewArray`] to [`StringViewArray`]
994    /// If items not utf8 data, validate will fail and error returned.
995    pub fn to_string_view(self) -> Result<StringViewArray, ArrowError> {
996        StringViewType::validate(self.views(), self.data_buffers())?;
997        unsafe { Ok(self.to_string_view_unchecked()) }
998    }
999
1000    /// Convert the [`BinaryViewArray`] to [`StringViewArray`]
1001    /// # Safety
1002    /// Caller is responsible for ensuring that items in array are utf8 data.
1003    pub unsafe fn to_string_view_unchecked(self) -> StringViewArray {
1004        unsafe { StringViewArray::new_unchecked(self.views, self.buffers, self.nulls) }
1005    }
1006}
1007
1008impl From<Vec<&[u8]>> for BinaryViewArray {
1009    fn from(v: Vec<&[u8]>) -> Self {
1010        Self::from_iter_values(v)
1011    }
1012}
1013
1014impl From<Vec<Option<&[u8]>>> for BinaryViewArray {
1015    fn from(v: Vec<Option<&[u8]>>) -> Self {
1016        v.into_iter().collect()
1017    }
1018}
1019
1020/// A [`GenericByteViewArray`] that stores utf8 data
1021///
1022/// See [`GenericByteViewArray`] for format and layout details.
1023///
1024/// # Example
1025/// ```
1026/// use arrow_array::StringViewArray;
1027/// let array = StringViewArray::from_iter_values(vec!["hello", "world", "lulu", "large payload over 12 bytes"]);
1028/// assert_eq!(array.value(0), "hello");
1029/// assert_eq!(array.value(3), "large payload over 12 bytes");
1030/// ```
1031pub type StringViewArray = GenericByteViewArray<StringViewType>;
1032
1033impl StringViewArray {
1034    /// Convert the [`StringViewArray`] to [`BinaryViewArray`]
1035    pub fn to_binary_view(self) -> BinaryViewArray {
1036        unsafe { BinaryViewArray::new_unchecked(self.views, self.buffers, self.nulls) }
1037    }
1038
1039    /// Returns true if all data within this array is ASCII
1040    pub fn is_ascii(&self) -> bool {
1041        // Alternative (but incorrect): directly check the underlying buffers
1042        // (1) Our string view might be sparse, i.e., a subset of the buffers,
1043        //      so even if the buffer is not ascii, we can still be ascii.
1044        // (2) It is quite difficult to know the range of each buffer (unlike StringArray)
1045        // This means that this operation is quite expensive, shall we cache the result?
1046        //  i.e. track `is_ascii` in the builder.
1047        self.iter().all(|v| match v {
1048            Some(v) => v.is_ascii(),
1049            None => true,
1050        })
1051    }
1052}
1053
1054impl From<Vec<&str>> for StringViewArray {
1055    fn from(v: Vec<&str>) -> Self {
1056        Self::from_iter_values(v)
1057    }
1058}
1059
1060impl From<Vec<Option<&str>>> for StringViewArray {
1061    fn from(v: Vec<Option<&str>>) -> Self {
1062        v.into_iter().collect()
1063    }
1064}
1065
1066impl From<Vec<String>> for StringViewArray {
1067    fn from(v: Vec<String>) -> Self {
1068        Self::from_iter_values(v)
1069    }
1070}
1071
1072impl From<Vec<Option<String>>> for StringViewArray {
1073    fn from(v: Vec<Option<String>>) -> Self {
1074        v.into_iter().collect()
1075    }
1076}
1077
1078#[cfg(test)]
1079mod tests {
1080    use crate::builder::{BinaryViewBuilder, StringViewBuilder};
1081    use crate::types::BinaryViewType;
1082    use crate::{
1083        Array, BinaryViewArray, GenericBinaryArray, GenericByteViewArray, StringViewArray,
1084    };
1085    use arrow_buffer::{Buffer, ScalarBuffer};
1086    use arrow_data::{ByteView, MAX_INLINE_VIEW_LEN};
1087    use rand::prelude::StdRng;
1088    use rand::{Rng, SeedableRng};
1089
1090    const BLOCK_SIZE: u32 = 8;
1091
1092    #[test]
1093    fn try_new_string() {
1094        let array = StringViewArray::from_iter_values(vec![
1095            "hello",
1096            "world",
1097            "lulu",
1098            "large payload over 12 bytes",
1099        ]);
1100        assert_eq!(array.value(0), "hello");
1101        assert_eq!(array.value(3), "large payload over 12 bytes");
1102    }
1103
1104    #[test]
1105    fn try_new_binary() {
1106        let array = BinaryViewArray::from_iter_values(vec![
1107            b"hello".as_slice(),
1108            b"world".as_slice(),
1109            b"lulu".as_slice(),
1110            b"large payload over 12 bytes".as_slice(),
1111        ]);
1112        assert_eq!(array.value(0), b"hello");
1113        assert_eq!(array.value(3), b"large payload over 12 bytes");
1114    }
1115
1116    #[test]
1117    fn try_new_empty_string() {
1118        // test empty array
1119        let array = {
1120            let mut builder = StringViewBuilder::new();
1121            builder.finish()
1122        };
1123        assert!(array.is_empty());
1124    }
1125
1126    #[test]
1127    fn try_new_empty_binary() {
1128        // test empty array
1129        let array = {
1130            let mut builder = BinaryViewBuilder::new();
1131            builder.finish()
1132        };
1133        assert!(array.is_empty());
1134    }
1135
1136    #[test]
1137    fn test_append_string() {
1138        // test builder append
1139        let array = {
1140            let mut builder = StringViewBuilder::new();
1141            builder.append_value("hello");
1142            builder.append_null();
1143            builder.append_option(Some("large payload over 12 bytes"));
1144            builder.finish()
1145        };
1146        assert_eq!(array.value(0), "hello");
1147        assert!(array.is_null(1));
1148        assert_eq!(array.value(2), "large payload over 12 bytes");
1149    }
1150
1151    #[test]
1152    fn test_append_binary() {
1153        // test builder append
1154        let array = {
1155            let mut builder = BinaryViewBuilder::new();
1156            builder.append_value(b"hello");
1157            builder.append_null();
1158            builder.append_option(Some(b"large payload over 12 bytes"));
1159            builder.finish()
1160        };
1161        assert_eq!(array.value(0), b"hello");
1162        assert!(array.is_null(1));
1163        assert_eq!(array.value(2), b"large payload over 12 bytes");
1164    }
1165
1166    #[test]
1167    fn test_in_progress_recreation() {
1168        let array = {
1169            // make a builder with small block size.
1170            let mut builder = StringViewBuilder::new().with_fixed_block_size(14);
1171            builder.append_value("large payload over 12 bytes");
1172            builder.append_option(Some("another large payload over 12 bytes that double than the first one, so that we can trigger the in_progress in builder re-created"));
1173            builder.finish()
1174        };
1175        assert_eq!(array.value(0), "large payload over 12 bytes");
1176        assert_eq!(
1177            array.value(1),
1178            "another large payload over 12 bytes that double than the first one, so that we can trigger the in_progress in builder re-created"
1179        );
1180        assert_eq!(2, array.buffers.len());
1181    }
1182
1183    #[test]
1184    #[should_panic(expected = "Invalid buffer index at 0: got index 3 but only has 1 buffers")]
1185    fn new_with_invalid_view_data() {
1186        let v = "large payload over 12 bytes";
1187        let view = ByteView::new(13, &v.as_bytes()[0..4])
1188            .with_buffer_index(3)
1189            .with_offset(1);
1190        let views = ScalarBuffer::from(vec![view.into()]);
1191        let buffers = vec![Buffer::from_slice_ref(v)];
1192        StringViewArray::new(views, buffers, None);
1193    }
1194
1195    #[test]
1196    #[should_panic(
1197        expected = "Encountered non-UTF-8 data at index 0: invalid utf-8 sequence of 1 bytes from index 0"
1198    )]
1199    fn new_with_invalid_utf8_data() {
1200        let v: Vec<u8> = vec![
1201            // invalid UTF8
1202            0xf0, 0x80, 0x80, 0x80, // more bytes to make it larger than 12
1203            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1204        ];
1205        let view = ByteView::new(v.len() as u32, &v[0..4]);
1206        let views = ScalarBuffer::from(vec![view.into()]);
1207        let buffers = vec![Buffer::from_slice_ref(v)];
1208        StringViewArray::new(views, buffers, None);
1209    }
1210
1211    #[test]
1212    #[should_panic(expected = "View at index 0 contained non-zero padding for string of length 1")]
1213    fn new_with_invalid_zero_padding() {
1214        let mut data = [0; 12];
1215        data[0] = b'H';
1216        data[11] = 1; // no zero padding
1217
1218        let mut view_buffer = [0; 16];
1219        view_buffer[0..4].copy_from_slice(&1u32.to_le_bytes());
1220        view_buffer[4..].copy_from_slice(&data);
1221
1222        let view = ByteView::from(u128::from_le_bytes(view_buffer));
1223        let views = ScalarBuffer::from(vec![view.into()]);
1224        let buffers = vec![];
1225        StringViewArray::new(views, buffers, None);
1226    }
1227
1228    #[test]
1229    #[should_panic(expected = "Mismatch between embedded prefix and data")]
1230    fn test_mismatch_between_embedded_prefix_and_data() {
1231        let input_str_1 = "Hello, Rustaceans!";
1232        let input_str_2 = "Hallo, Rustaceans!";
1233        let length = input_str_1.len() as u32;
1234        assert!(input_str_1.len() > 12);
1235
1236        let mut view_buffer = [0; 16];
1237        view_buffer[0..4].copy_from_slice(&length.to_le_bytes());
1238        view_buffer[4..8].copy_from_slice(&input_str_1.as_bytes()[0..4]);
1239        view_buffer[8..12].copy_from_slice(&0u32.to_le_bytes());
1240        view_buffer[12..].copy_from_slice(&0u32.to_le_bytes());
1241        let view = ByteView::from(u128::from_le_bytes(view_buffer));
1242        let views = ScalarBuffer::from(vec![view.into()]);
1243        let buffers = vec![Buffer::from_slice_ref(input_str_2.as_bytes())];
1244
1245        StringViewArray::new(views, buffers, None);
1246    }
1247
1248    #[test]
1249    fn test_gc() {
1250        let test_data = [
1251            Some("longer than 12 bytes"),
1252            Some("short"),
1253            Some("t"),
1254            Some("longer than 12 bytes"),
1255            None,
1256            Some("short"),
1257        ];
1258
1259        let array = {
1260            let mut builder = StringViewBuilder::new().with_fixed_block_size(8); // create multiple buffers
1261            test_data.into_iter().for_each(|v| builder.append_option(v));
1262            builder.finish()
1263        };
1264        assert!(array.buffers.len() > 1);
1265
1266        fn check_gc(to_test: &StringViewArray) {
1267            let gc = to_test.gc();
1268            assert_ne!(to_test.data_buffers().len(), gc.data_buffers().len());
1269
1270            to_test.iter().zip(gc.iter()).for_each(|(a, b)| {
1271                assert_eq!(a, b);
1272            });
1273            assert_eq!(to_test.len(), gc.len());
1274        }
1275
1276        check_gc(&array);
1277        check_gc(&array.slice(1, 3));
1278        check_gc(&array.slice(2, 1));
1279        check_gc(&array.slice(2, 2));
1280        check_gc(&array.slice(3, 1));
1281    }
1282
1283    /// 1) Empty array: no elements, expect gc to return empty with no data buffers
1284    #[test]
1285    fn test_gc_empty_array() {
1286        let array = StringViewBuilder::new()
1287            .with_fixed_block_size(BLOCK_SIZE)
1288            .finish();
1289        let gced = array.gc();
1290        // length and null count remain zero
1291        assert_eq!(gced.len(), 0);
1292        assert_eq!(gced.null_count(), 0);
1293        // no underlying data buffers should be allocated
1294        assert!(
1295            gced.data_buffers().is_empty(),
1296            "Expected no data buffers for empty array"
1297        );
1298    }
1299
1300    /// 2) All inline values (<= INLINE_LEN): capacity-only data buffer, same values
1301    #[test]
1302    fn test_gc_all_inline() {
1303        let mut builder = StringViewBuilder::new().with_fixed_block_size(BLOCK_SIZE);
1304        // append many short strings, each exactly INLINE_LEN long
1305        for _ in 0..100 {
1306            let s = "A".repeat(MAX_INLINE_VIEW_LEN as usize);
1307            builder.append_option(Some(&s));
1308        }
1309        let array = builder.finish();
1310        let gced = array.gc();
1311        // Since all views fit inline, data buffer is empty
1312        assert_eq!(
1313            gced.data_buffers().len(),
1314            0,
1315            "Should have no data buffers for inline values"
1316        );
1317        assert_eq!(gced.len(), 100);
1318        // verify element-wise equality
1319        array.iter().zip(gced.iter()).for_each(|(orig, got)| {
1320            assert_eq!(orig, got, "Inline value mismatch after gc");
1321        });
1322    }
1323
1324    /// 3) All large values (> INLINE_LEN): each must be copied into the new data buffer
1325    #[test]
1326    fn test_gc_all_large() {
1327        let mut builder = StringViewBuilder::new().with_fixed_block_size(BLOCK_SIZE);
1328        let large_str = "X".repeat(MAX_INLINE_VIEW_LEN as usize + 5);
1329        // append multiple large strings
1330        for _ in 0..50 {
1331            builder.append_option(Some(&large_str));
1332        }
1333        let array = builder.finish();
1334        let gced = array.gc();
1335        // New data buffers should be populated (one or more blocks)
1336        assert!(
1337            !gced.data_buffers().is_empty(),
1338            "Expected data buffers for large values"
1339        );
1340        assert_eq!(gced.len(), 50);
1341        // verify that every large string emerges unchanged
1342        array.iter().zip(gced.iter()).for_each(|(orig, got)| {
1343            assert_eq!(orig, got, "Large view mismatch after gc");
1344        });
1345    }
1346
1347    /// 4) All null elements: ensure null bitmap handling path is correct
1348    #[test]
1349    fn test_gc_all_nulls() {
1350        let mut builder = StringViewBuilder::new().with_fixed_block_size(BLOCK_SIZE);
1351        for _ in 0..20 {
1352            builder.append_null();
1353        }
1354        let array = builder.finish();
1355        let gced = array.gc();
1356        // length and null count match
1357        assert_eq!(gced.len(), 20);
1358        assert_eq!(gced.null_count(), 20);
1359        // data buffers remain empty for null-only array
1360        assert!(
1361            gced.data_buffers().is_empty(),
1362            "No data should be stored for nulls"
1363        );
1364    }
1365
1366    /// 5) Random mix of inline, large, and null values with slicing tests
1367    #[test]
1368    fn test_gc_random_mixed_and_slices() {
1369        let mut rng = StdRng::seed_from_u64(42);
1370        let mut builder = StringViewBuilder::new().with_fixed_block_size(BLOCK_SIZE);
1371        // Keep a Vec of original Option<String> for later comparison
1372        let mut original: Vec<Option<String>> = Vec::new();
1373
1374        for _ in 0..200 {
1375            if rng.random_bool(0.1) {
1376                // 10% nulls
1377                builder.append_null();
1378                original.push(None);
1379            } else {
1380                // random length between 0 and twice the inline limit
1381                let len = rng.random_range(0..(MAX_INLINE_VIEW_LEN * 2));
1382                let s: String = "A".repeat(len as usize);
1383                builder.append_option(Some(&s));
1384                original.push(Some(s));
1385            }
1386        }
1387
1388        let array = builder.finish();
1389        // Test multiple slice ranges to ensure offset logic is correct
1390        for (offset, slice_len) in &[(0, 50), (10, 100), (150, 30)] {
1391            let sliced = array.slice(*offset, *slice_len);
1392            let gced = sliced.gc();
1393            // Build expected slice of Option<&str>
1394            let expected: Vec<Option<&str>> = original[*offset..(*offset + *slice_len)]
1395                .iter()
1396                .map(|opt| opt.as_deref())
1397                .collect();
1398
1399            assert_eq!(gced.len(), *slice_len, "Slice length mismatch");
1400            // Compare element-wise
1401            gced.iter().zip(expected.iter()).for_each(|(got, expect)| {
1402                assert_eq!(got, *expect, "Value mismatch in mixed slice after gc");
1403            });
1404        }
1405    }
1406
1407    #[test]
1408    fn test_eq() {
1409        let test_data = [
1410            Some("longer than 12 bytes"),
1411            None,
1412            Some("short"),
1413            Some("again, this is longer than 12 bytes"),
1414        ];
1415
1416        let array1 = {
1417            let mut builder = StringViewBuilder::new().with_fixed_block_size(8);
1418            test_data.into_iter().for_each(|v| builder.append_option(v));
1419            builder.finish()
1420        };
1421        let array2 = {
1422            // create a new array with the same data but different layout
1423            let mut builder = StringViewBuilder::new().with_fixed_block_size(100);
1424            test_data.into_iter().for_each(|v| builder.append_option(v));
1425            builder.finish()
1426        };
1427        assert_eq!(array1, array1.clone());
1428        assert_eq!(array2, array2.clone());
1429        assert_eq!(array1, array2);
1430    }
1431
1432    /// Integration tests for `inline_key_fast` covering:
1433    ///
1434    /// 1. Monotonic ordering across increasing lengths and lexical variations.
1435    /// 2. Cross-check against `GenericBinaryArray` comparison to ensure semantic equivalence.
1436    ///
1437    /// This also includes a specific test for the “bar” vs. “bar\0” case, demonstrating why
1438    /// the length field is required even when all inline bytes fit in 12 bytes.
1439    ///
1440    /// The test includes strings that verify correct byte order (prevent reversal bugs),
1441    /// and length-based tie-breaking in the composite key.
1442    ///
1443    /// The test confirms that `inline_key_fast` produces keys which sort consistently
1444    /// with the expected lexicographical order of the raw byte arrays.
1445    #[test]
1446    fn test_inline_key_fast_various_lengths_and_lexical() {
1447        /// Helper to create a raw u128 value representing an inline ByteView:
1448        /// - `length`: number of meaningful bytes (must be ≤ 12)
1449        /// - `data`: the actual inline data bytes
1450        ///
1451        /// The first 4 bytes encode length in little-endian,
1452        /// the following 12 bytes contain the inline string data (unpadded).
1453        fn make_raw_inline(length: u32, data: &[u8]) -> u128 {
1454            assert!(length as usize <= 12, "Inline length must be ≤ 12");
1455            assert!(
1456                data.len() == length as usize,
1457                "Data length must match `length`"
1458            );
1459
1460            let mut raw_bytes = [0u8; 16];
1461            raw_bytes[0..4].copy_from_slice(&length.to_le_bytes()); // length stored little-endian
1462            raw_bytes[4..(4 + data.len())].copy_from_slice(data); // inline data
1463            u128::from_le_bytes(raw_bytes)
1464        }
1465
1466        // Test inputs: various lengths and lexical orders,
1467        // plus special cases for byte order and length tie-breaking
1468        let test_inputs: Vec<&[u8]> = vec![
1469            b"a",
1470            b"aa",
1471            b"aaa",
1472            b"aab",
1473            b"abcd",
1474            b"abcde",
1475            b"abcdef",
1476            b"abcdefg",
1477            b"abcdefgh",
1478            b"abcdefghi",
1479            b"abcdefghij",
1480            b"abcdefghijk",
1481            b"abcdefghijkl",
1482            // Tests for byte-order reversal bug:
1483            // Without the fix, "backend one" would compare as "eno dnekcab",
1484            // causing incorrect sort order relative to "backend two".
1485            b"backend one",
1486            b"backend two",
1487            // Tests length-tiebreaker logic:
1488            // "bar" (3 bytes) and "bar\0" (4 bytes) have identical inline data,
1489            // so only the length differentiates their ordering.
1490            b"bar",
1491            b"bar\0",
1492            // Additional lexical and length tie-breaking cases with same prefix, in correct lex order:
1493            b"than12Byt",
1494            b"than12Bytes",
1495            b"than12Bytes\0",
1496            b"than12Bytesx",
1497            b"than12Bytex",
1498            b"than12Bytez",
1499            // Additional lexical tests
1500            b"xyy",
1501            b"xyz",
1502            b"xza",
1503        ];
1504
1505        // Create a GenericBinaryArray for cross-comparison of lex order
1506        let array: GenericBinaryArray<i32> =
1507            GenericBinaryArray::from(test_inputs.iter().map(|s| Some(*s)).collect::<Vec<_>>());
1508
1509        for i in 0..array.len() - 1 {
1510            let v1 = array.value(i);
1511            let v2 = array.value(i + 1);
1512
1513            // Assert the array's natural lexical ordering is correct
1514            assert!(v1 < v2, "Array compare failed: {v1:?} !< {v2:?}");
1515
1516            // Assert the keys produced by inline_key_fast reflect the same ordering
1517            let key1 = GenericByteViewArray::<BinaryViewType>::inline_key_fast(make_raw_inline(
1518                v1.len() as u32,
1519                v1,
1520            ));
1521            let key2 = GenericByteViewArray::<BinaryViewType>::inline_key_fast(make_raw_inline(
1522                v2.len() as u32,
1523                v2,
1524            ));
1525
1526            assert!(
1527                key1 < key2,
1528                "Key compare failed: key({v1:?})=0x{key1:032x} !< key({v2:?})=0x{key2:032x}",
1529            );
1530        }
1531    }
1532}