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};
26use arrow_schema::{ArrowError, DataType};
27use core::str;
28use num::ToPrimitive;
29use std::any::Any;
30use std::fmt::Debug;
31use std::marker::PhantomData;
32use std::sync::Arc;
33
34use super::ByteArrayType;
35
36/// [Variable-size Binary View Layout]: An array of variable length bytes views.
37///
38/// This array type is used to store variable length byte data (e.g. Strings, Binary)
39/// and has efficient operations such as `take`, `filter`, and comparison.
40///
41/// [Variable-size Binary View Layout]: https://arrow.apache.org/docs/format/Columnar.html#variable-size-binary-view-layout
42///
43/// This is different from [`GenericByteArray`], which also stores variable
44/// length byte data, as it represents strings with an offset and length. `take`
45/// and `filter` like operations are implemented by manipulating the "views"
46/// (`u128`) without modifying the bytes. Each view also stores an inlined
47/// prefix which speed up comparisons.
48///
49/// # See Also
50///
51/// * [`StringViewArray`] for storing utf8 encoded string data
52/// * [`BinaryViewArray`] for storing bytes
53/// * [`ByteView`] to interpret `u128`s layout of the views.
54///
55/// [`ByteView`]: arrow_data::ByteView
56///
57/// # Layout: "views" and buffers
58///
59/// A `GenericByteViewArray` stores variable length byte strings. An array of
60/// `N` elements is stored as `N` fixed length "views" and a variable number
61/// of variable length "buffers".
62///
63/// Each view is a `u128` value whose layout is different depending on the
64/// length of the string stored at that location:
65///
66/// ```text
67///                         ┌──────┬────────────────────────┐
68///                         │length│      string value      │
69///    Strings (len <= 12)  │      │    (padded with 0)     │
70///                         └──────┴────────────────────────┘
71///                          0    31                      127
72///
73///                         ┌───────┬───────┬───────┬───────┐
74///                         │length │prefix │  buf  │offset │
75///    Strings (len > 12)   │       │       │ index │       │
76///                         └───────┴───────┴───────┴───────┘
77///                          0    31       63      95    127
78/// ```
79///
80/// * Strings with length <= 12 are stored directly in the view. See
81///   [`Self::inline_value`] to access the inlined prefix from a short view.
82///
83/// * Strings with length > 12: The first four bytes are stored inline in the
84///   view and the entire string is stored in one of the buffers. See [`ByteView`]
85///   to access the fields of the these views.
86///
87/// As with other arrays, the optimized kernels in [`arrow_compute`] are likely
88/// the easiest and fastest way to work with this data. However, it is possible
89/// to access the views and buffers directly for more control.
90///
91/// For example
92///
93/// ```rust
94/// # use arrow_array::StringViewArray;
95/// # use arrow_array::Array;
96/// use arrow_data::ByteView;
97/// let array = StringViewArray::from(vec![
98///   "hello",
99///   "this string is longer than 12 bytes",
100///   "this string is also longer than 12 bytes"
101/// ]);
102///
103/// // ** Examine the first view (short string) **
104/// assert!(array.is_valid(0)); // Check for nulls
105/// let short_view: u128 = array.views()[0]; // "hello"
106/// // get length of the string
107/// let len = short_view as u32;
108/// assert_eq!(len, 5); // strings less than 12 bytes are stored in the view
109/// // SAFETY: `view` is a valid view
110/// let value = unsafe {
111///   StringViewArray::inline_value(&short_view, len as usize)
112/// };
113/// assert_eq!(value, b"hello");
114///
115/// // ** Examine the third view (long string) **
116/// assert!(array.is_valid(12)); // Check for nulls
117/// let long_view: u128 = array.views()[2]; // "this string is also longer than 12 bytes"
118/// let len = long_view as u32;
119/// assert_eq!(len, 40); // strings longer than 12 bytes are stored in the buffer
120/// let view = ByteView::from(long_view); // use ByteView to access the fields
121/// assert_eq!(view.length, 40);
122/// assert_eq!(view.buffer_index, 0);
123/// assert_eq!(view.offset, 35); // data starts after the first long string
124/// // Views for long strings store a 4 byte prefix
125/// let prefix = view.prefix.to_le_bytes();
126/// assert_eq!(&prefix, b"this");
127/// let value = array.value(2); // get the string value (see `value` implementation for how to access the bytes directly)
128/// assert_eq!(value, "this string is also longer than 12 bytes");
129/// ```
130///
131/// [`arrow_compute`]: https://docs.rs/arrow/latest/arrow/compute/index.html
132///
133/// Unlike [`GenericByteArray`], there are no constraints on the offsets other
134/// than they must point into a valid buffer. However, they can be out of order,
135/// non continuous and overlapping.
136///
137/// For example, in the following diagram, the strings "FishWasInTownToday" and
138/// "CrumpleFacedFish" are both longer than 12 bytes and thus are stored in a
139/// separate buffer while the string "LavaMonster" is stored inlined in the
140/// view. In this case, the same bytes for "Fish" are used to store both strings.
141///
142/// [`ByteView`]: arrow_data::ByteView
143///
144/// ```text
145///                                                                            ┌───┐
146///                         ┌──────┬──────┬──────┬──────┐               offset │...│
147/// "FishWasInTownTodayYay" │  21  │ Fish │  0   │ 115  │─ ─              103  │Mr.│
148///                         └──────┴──────┴──────┴──────┘   │      ┌ ─ ─ ─ ─ ▶ │Cru│
149///                         ┌──────┬──────┬──────┬──────┐                      │mpl│
150/// "CrumpleFacedFish"      │  16  │ Crum │  0   │ 103  │─ ─│─ ─ ─ ┘           │eFa│
151///                         └──────┴──────┴──────┴──────┘                      │ced│
152///                         ┌──────┬────────────────────┐   └ ─ ─ ─ ─ ─ ─ ─ ─ ▶│Fis│
153/// "LavaMonster"           │  11  │   LavaMonster      │                      │hWa│
154///                         └──────┴────────────────────┘               offset │sIn│
155///                                                                       115  │Tow│
156///                                                                            │nTo│
157///                                                                            │day│
158///                                  u128 "views"                              │Yay│
159///                                                                   buffer 0 │...│
160///                                                                            └───┘
161/// ```
162pub struct GenericByteViewArray<T: ByteViewType + ?Sized> {
163    data_type: DataType,
164    views: ScalarBuffer<u128>,
165    buffers: Vec<Buffer>,
166    phantom: PhantomData<T>,
167    nulls: Option<NullBuffer>,
168}
169
170impl<T: ByteViewType + ?Sized> Clone for GenericByteViewArray<T> {
171    fn clone(&self) -> Self {
172        Self {
173            data_type: T::DATA_TYPE,
174            views: self.views.clone(),
175            buffers: self.buffers.clone(),
176            nulls: self.nulls.clone(),
177            phantom: Default::default(),
178        }
179    }
180}
181
182impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
183    /// Create a new [`GenericByteViewArray`] from the provided parts, panicking on failure
184    ///
185    /// # Panics
186    ///
187    /// Panics if [`GenericByteViewArray::try_new`] returns an error
188    pub fn new(views: ScalarBuffer<u128>, buffers: Vec<Buffer>, nulls: Option<NullBuffer>) -> Self {
189        Self::try_new(views, buffers, nulls).unwrap()
190    }
191
192    /// Create a new [`GenericByteViewArray`] from the provided parts, returning an error on failure
193    ///
194    /// # Errors
195    ///
196    /// * `views.len() != nulls.len()`
197    /// * [ByteViewType::validate] fails
198    pub fn try_new(
199        views: ScalarBuffer<u128>,
200        buffers: Vec<Buffer>,
201        nulls: Option<NullBuffer>,
202    ) -> Result<Self, ArrowError> {
203        T::validate(&views, &buffers)?;
204
205        if let Some(n) = nulls.as_ref() {
206            if n.len() != views.len() {
207                return Err(ArrowError::InvalidArgumentError(format!(
208                    "Incorrect length of null buffer for {}ViewArray, expected {} got {}",
209                    T::PREFIX,
210                    views.len(),
211                    n.len(),
212                )));
213            }
214        }
215
216        Ok(Self {
217            data_type: T::DATA_TYPE,
218            views,
219            buffers,
220            nulls,
221            phantom: Default::default(),
222        })
223    }
224
225    /// Create a new [`GenericByteViewArray`] from the provided parts, without validation
226    ///
227    /// # Safety
228    ///
229    /// Safe if [`Self::try_new`] would not error
230    pub unsafe fn new_unchecked(
231        views: ScalarBuffer<u128>,
232        buffers: Vec<Buffer>,
233        nulls: Option<NullBuffer>,
234    ) -> Self {
235        if cfg!(feature = "force_validate") {
236            return Self::new(views, buffers, nulls);
237        }
238
239        Self {
240            data_type: T::DATA_TYPE,
241            phantom: Default::default(),
242            views,
243            buffers,
244            nulls,
245        }
246    }
247
248    /// Create a new [`GenericByteViewArray`] of length `len` where all values are null
249    pub fn new_null(len: usize) -> Self {
250        Self {
251            data_type: T::DATA_TYPE,
252            views: vec![0; len].into(),
253            buffers: vec![],
254            nulls: Some(NullBuffer::new_null(len)),
255            phantom: Default::default(),
256        }
257    }
258
259    /// Create a new [`Scalar`] from `value`
260    pub fn new_scalar(value: impl AsRef<T::Native>) -> Scalar<Self> {
261        Scalar::new(Self::from_iter_values(std::iter::once(value)))
262    }
263
264    /// Creates a [`GenericByteViewArray`] based on an iterator of values without nulls
265    pub fn from_iter_values<Ptr, I>(iter: I) -> Self
266    where
267        Ptr: AsRef<T::Native>,
268        I: IntoIterator<Item = Ptr>,
269    {
270        let iter = iter.into_iter();
271        let mut builder = GenericByteViewBuilder::<T>::with_capacity(iter.size_hint().0);
272        for v in iter {
273            builder.append_value(v);
274        }
275        builder.finish()
276    }
277
278    /// Deconstruct this array into its constituent parts
279    pub fn into_parts(self) -> (ScalarBuffer<u128>, Vec<Buffer>, Option<NullBuffer>) {
280        (self.views, self.buffers, self.nulls)
281    }
282
283    /// Returns the views buffer
284    #[inline]
285    pub fn views(&self) -> &ScalarBuffer<u128> {
286        &self.views
287    }
288
289    /// Returns the buffers storing string data
290    #[inline]
291    pub fn data_buffers(&self) -> &[Buffer] {
292        &self.buffers
293    }
294
295    /// Returns the element at index `i`
296    /// # Panics
297    /// Panics if index `i` is out of bounds.
298    pub fn value(&self, i: usize) -> &T::Native {
299        assert!(
300            i < self.len(),
301            "Trying to access an element at index {} from a {}ViewArray of length {}",
302            i,
303            T::PREFIX,
304            self.len()
305        );
306
307        unsafe { self.value_unchecked(i) }
308    }
309
310    /// Returns the element at index `i` without bounds checking
311    ///
312    /// # Safety
313    ///
314    /// Caller is responsible for ensuring that the index is within the bounds
315    /// of the array
316    pub unsafe fn value_unchecked(&self, idx: usize) -> &T::Native {
317        let v = self.views.get_unchecked(idx);
318        let len = *v as u32;
319        let b = if len <= 12 {
320            Self::inline_value(v, len as usize)
321        } else {
322            let view = ByteView::from(*v);
323            let data = self.buffers.get_unchecked(view.buffer_index as usize);
324            let offset = view.offset as usize;
325            data.get_unchecked(offset..offset + len as usize)
326        };
327        T::Native::from_bytes_unchecked(b)
328    }
329
330    /// Returns the first `len` bytes the inline value of the view.
331    ///
332    /// # Safety
333    /// - The `view` must be a valid element from `Self::views()` that adheres to the view layout.
334    /// - The `len` must be the length of the inlined value. It should never be larger than 12.
335    #[inline(always)]
336    pub unsafe fn inline_value(view: &u128, len: usize) -> &[u8] {
337        debug_assert!(len <= 12);
338        std::slice::from_raw_parts((view as *const u128 as *const u8).wrapping_add(4), len)
339    }
340
341    /// Constructs a new iterator for iterating over the values of this array
342    pub fn iter(&self) -> ArrayIter<&Self> {
343        ArrayIter::new(self)
344    }
345
346    /// Returns an iterator over the bytes of this array, including null values
347    pub fn bytes_iter(&self) -> impl Iterator<Item = &[u8]> {
348        self.views.iter().map(move |v| {
349            let len = *v as u32;
350            if len <= 12 {
351                unsafe { Self::inline_value(v, len as usize) }
352            } else {
353                let view = ByteView::from(*v);
354                let data = &self.buffers[view.buffer_index as usize];
355                let offset = view.offset as usize;
356                unsafe { data.get_unchecked(offset..offset + len as usize) }
357            }
358        })
359    }
360
361    /// Returns an iterator over the first `prefix_len` bytes of each array
362    /// element, including null values.
363    ///
364    /// If `prefix_len` is larger than the element's length, the iterator will
365    /// return an empty slice (`&[]`).
366    pub fn prefix_bytes_iter(&self, prefix_len: usize) -> impl Iterator<Item = &[u8]> {
367        self.views().into_iter().map(move |v| {
368            let len = (*v as u32) as usize;
369
370            if len < prefix_len {
371                return &[] as &[u8];
372            }
373
374            if prefix_len <= 4 || len <= 12 {
375                unsafe { StringViewArray::inline_value(v, prefix_len) }
376            } else {
377                let view = ByteView::from(*v);
378                let data = unsafe {
379                    self.data_buffers()
380                        .get_unchecked(view.buffer_index as usize)
381                };
382                let offset = view.offset as usize;
383                unsafe { data.get_unchecked(offset..offset + prefix_len) }
384            }
385        })
386    }
387
388    /// Returns an iterator over the last `suffix_len` bytes of each array
389    /// element, including null values.
390    ///
391    /// Note that for [`StringViewArray`] the last bytes may start in the middle
392    /// of a UTF-8 codepoint, and thus may not be a valid `&str`.
393    ///
394    /// If `suffix_len` is larger than the element's length, the iterator will
395    /// return an empty slice (`&[]`).
396    pub fn suffix_bytes_iter(&self, suffix_len: usize) -> impl Iterator<Item = &[u8]> {
397        self.views().into_iter().map(move |v| {
398            let len = (*v as u32) as usize;
399
400            if len < suffix_len {
401                return &[] as &[u8];
402            }
403
404            if len <= 12 {
405                unsafe { &StringViewArray::inline_value(v, len)[len - suffix_len..] }
406            } else {
407                let view = ByteView::from(*v);
408                let data = unsafe {
409                    self.data_buffers()
410                        .get_unchecked(view.buffer_index as usize)
411                };
412                let offset = view.offset as usize;
413                unsafe { data.get_unchecked(offset + len - suffix_len..offset + len) }
414            }
415        })
416    }
417
418    /// Returns a zero-copy slice of this array with the indicated offset and length.
419    pub fn slice(&self, offset: usize, length: usize) -> Self {
420        Self {
421            data_type: T::DATA_TYPE,
422            views: self.views.slice(offset, length),
423            buffers: self.buffers.clone(),
424            nulls: self.nulls.as_ref().map(|n| n.slice(offset, length)),
425            phantom: Default::default(),
426        }
427    }
428
429    /// Returns a "compacted" version of this array
430    ///
431    /// The original array will *not* be modified
432    ///
433    /// # Garbage Collection
434    ///
435    /// Before GC:
436    /// ```text
437    ///                                        ┌──────┐
438    ///                                        │......│
439    ///                                        │......│
440    /// ┌────────────────────┐       ┌ ─ ─ ─ ▶ │Data1 │   Large buffer
441    /// │       View 1       │─ ─ ─ ─          │......│  with data that
442    /// ├────────────────────┤                 │......│ is not referred
443    /// │       View 2       │─ ─ ─ ─ ─ ─ ─ ─▶ │Data2 │ to by View 1 or
444    /// └────────────────────┘                 │......│      View 2
445    ///                                        │......│
446    ///    2 views, refer to                   │......│
447    ///   small portions of a                  └──────┘
448    ///      large buffer
449    /// ```
450    ///
451    /// After GC:
452    ///
453    /// ```text
454    /// ┌────────────────────┐                 ┌─────┐    After gc, only
455    /// │       View 1       │─ ─ ─ ─ ─ ─ ─ ─▶ │Data1│     data that is
456    /// ├────────────────────┤       ┌ ─ ─ ─ ▶ │Data2│    pointed to by
457    /// │       View 2       │─ ─ ─ ─          └─────┘     the views is
458    /// └────────────────────┘                                 left
459    ///
460    ///
461    ///         2 views
462    /// ```
463    /// This method will compact the data buffers by recreating the view array and only include the data
464    /// that is pointed to by the views.
465    ///
466    /// Note that it will copy the array regardless of whether the original array is compact.
467    /// Use with caution as this can be an expensive operation, only use it when you are sure that the view
468    /// array is significantly smaller than when it is originally created, e.g., after filtering or slicing.
469    ///
470    /// Note: this function does not attempt to canonicalize / deduplicate values. For this
471    /// feature see  [`GenericByteViewBuilder::with_deduplicate_strings`].
472    pub fn gc(&self) -> Self {
473        let mut builder = GenericByteViewBuilder::<T>::with_capacity(self.len());
474
475        for v in self.iter() {
476            builder.append_option(v);
477        }
478
479        builder.finish()
480    }
481
482    /// Compare two [`GenericByteViewArray`] at index `left_idx` and `right_idx`
483    ///
484    /// Comparing two ByteView types are non-trivial.
485    /// It takes a bit of patience to understand why we don't just compare two &[u8] directly.
486    ///
487    /// ByteView types give us the following two advantages, and we need to be careful not to lose them:
488    /// (1) For string/byte smaller than 12 bytes, the entire data is inlined in the view.
489    ///     Meaning that reading one array element requires only one memory access
490    ///     (two memory access required for StringArray, one for offset buffer, the other for value buffer).
491    ///
492    /// (2) For string/byte larger than 12 bytes, we can still be faster than (for certain operations) StringArray/ByteArray,
493    ///     thanks to the inlined 4 bytes.
494    ///     Consider equality check:
495    ///     If the first four bytes of the two strings are different, we can return false immediately (with just one memory access).
496    ///
497    /// If we directly compare two &[u8], we materialize the entire string (i.e., make multiple memory accesses), which might be unnecessary.
498    /// - Most of the time (eq, ord), we only need to look at the first 4 bytes to know the answer,
499    ///   e.g., if the inlined 4 bytes are different, we can directly return unequal without looking at the full string.
500    ///
501    /// # Order check flow
502    /// (1) if both string are smaller than 12 bytes, we can directly compare the data inlined to the view.
503    /// (2) if any of the string is larger than 12 bytes, we need to compare the full string.
504    ///     (2.1) if the inlined 4 bytes are different, we can return the result immediately.
505    ///     (2.2) o.w., we need to compare the full string.
506    ///
507    /// # Safety
508    /// The left/right_idx must within range of each array
509    pub unsafe fn compare_unchecked(
510        left: &GenericByteViewArray<T>,
511        left_idx: usize,
512        right: &GenericByteViewArray<T>,
513        right_idx: usize,
514    ) -> std::cmp::Ordering {
515        let l_view = left.views().get_unchecked(left_idx);
516        let l_len = *l_view as u32;
517
518        let r_view = right.views().get_unchecked(right_idx);
519        let r_len = *r_view as u32;
520
521        if l_len <= 12 && r_len <= 12 {
522            let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
523            let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
524            return l_data.cmp(r_data);
525        }
526
527        // one of the string is larger than 12 bytes,
528        // we then try to compare the inlined data first
529        let l_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, 4) };
530        let r_inlined_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, 4) };
531        if r_inlined_data != l_inlined_data {
532            return l_inlined_data.cmp(r_inlined_data);
533        }
534
535        // unfortunately, we need to compare the full data
536        let l_full_data: &[u8] = unsafe { left.value_unchecked(left_idx).as_ref() };
537        let r_full_data: &[u8] = unsafe { right.value_unchecked(right_idx).as_ref() };
538
539        l_full_data.cmp(r_full_data)
540    }
541}
542
543impl<T: ByteViewType + ?Sized> Debug for GenericByteViewArray<T> {
544    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
545        write!(f, "{}ViewArray\n[\n", T::PREFIX)?;
546        print_long_array(self, f, |array, index, f| {
547            std::fmt::Debug::fmt(&array.value(index), f)
548        })?;
549        write!(f, "]")
550    }
551}
552
553impl<T: ByteViewType + ?Sized> Array for GenericByteViewArray<T> {
554    fn as_any(&self) -> &dyn Any {
555        self
556    }
557
558    fn to_data(&self) -> ArrayData {
559        self.clone().into()
560    }
561
562    fn into_data(self) -> ArrayData {
563        self.into()
564    }
565
566    fn data_type(&self) -> &DataType {
567        &self.data_type
568    }
569
570    fn slice(&self, offset: usize, length: usize) -> ArrayRef {
571        Arc::new(self.slice(offset, length))
572    }
573
574    fn len(&self) -> usize {
575        self.views.len()
576    }
577
578    fn is_empty(&self) -> bool {
579        self.views.is_empty()
580    }
581
582    fn shrink_to_fit(&mut self) {
583        self.views.shrink_to_fit();
584        self.buffers.iter_mut().for_each(|b| b.shrink_to_fit());
585        self.buffers.shrink_to_fit();
586        if let Some(nulls) = &mut self.nulls {
587            nulls.shrink_to_fit();
588        }
589    }
590
591    fn offset(&self) -> usize {
592        0
593    }
594
595    fn nulls(&self) -> Option<&NullBuffer> {
596        self.nulls.as_ref()
597    }
598
599    fn logical_null_count(&self) -> usize {
600        // More efficient that the default implementation
601        self.null_count()
602    }
603
604    fn get_buffer_memory_size(&self) -> usize {
605        let mut sum = self.buffers.iter().map(|b| b.capacity()).sum::<usize>();
606        sum += self.views.inner().capacity();
607        if let Some(x) = &self.nulls {
608            sum += x.buffer().capacity()
609        }
610        sum
611    }
612
613    fn get_array_memory_size(&self) -> usize {
614        std::mem::size_of::<Self>() + self.get_buffer_memory_size()
615    }
616}
617
618impl<'a, T: ByteViewType + ?Sized> ArrayAccessor for &'a GenericByteViewArray<T> {
619    type Item = &'a T::Native;
620
621    fn value(&self, index: usize) -> Self::Item {
622        GenericByteViewArray::value(self, index)
623    }
624
625    unsafe fn value_unchecked(&self, index: usize) -> Self::Item {
626        GenericByteViewArray::value_unchecked(self, index)
627    }
628}
629
630impl<'a, T: ByteViewType + ?Sized> IntoIterator for &'a GenericByteViewArray<T> {
631    type Item = Option<&'a T::Native>;
632    type IntoIter = ArrayIter<Self>;
633
634    fn into_iter(self) -> Self::IntoIter {
635        ArrayIter::new(self)
636    }
637}
638
639impl<T: ByteViewType + ?Sized> From<ArrayData> for GenericByteViewArray<T> {
640    fn from(value: ArrayData) -> Self {
641        let views = value.buffers()[0].clone();
642        let views = ScalarBuffer::new(views, value.offset(), value.len());
643        let buffers = value.buffers()[1..].to_vec();
644        Self {
645            data_type: T::DATA_TYPE,
646            views,
647            buffers,
648            nulls: value.nulls().cloned(),
649            phantom: Default::default(),
650        }
651    }
652}
653
654/// Efficiently convert a [`GenericByteArray`] to a [`GenericByteViewArray`]
655///
656/// For example this method can convert a [`StringArray`] to a
657/// [`StringViewArray`].
658///
659/// If the offsets are all less than u32::MAX, the new [`GenericByteViewArray`]
660/// is built without copying the underlying string data (views are created
661/// directly into the existing buffer)
662///
663/// [`StringArray`]: crate::StringArray
664impl<FROM, V> From<&GenericByteArray<FROM>> for GenericByteViewArray<V>
665where
666    FROM: ByteArrayType,
667    FROM::Offset: OffsetSizeTrait + ToPrimitive,
668    V: ByteViewType<Native = FROM::Native>,
669{
670    fn from(byte_array: &GenericByteArray<FROM>) -> Self {
671        let offsets = byte_array.offsets();
672
673        let can_reuse_buffer = match offsets.last() {
674            Some(offset) => offset.as_usize() < u32::MAX as usize,
675            None => true,
676        };
677
678        if can_reuse_buffer {
679            // build views directly pointing to the existing buffer
680            let len = byte_array.len();
681            let mut views_builder = GenericByteViewBuilder::<V>::with_capacity(len);
682            let str_values_buf = byte_array.values().clone();
683            let block = views_builder.append_block(str_values_buf);
684            for (i, w) in offsets.windows(2).enumerate() {
685                let offset = w[0].as_usize();
686                let end = w[1].as_usize();
687                let length = end - offset;
688
689                if byte_array.is_null(i) {
690                    views_builder.append_null();
691                } else {
692                    // Safety: the input was a valid array so it valid UTF8 (if string). And
693                    // all offsets were valid
694                    unsafe {
695                        views_builder.append_view_unchecked(block, offset as u32, length as u32)
696                    }
697                }
698            }
699            assert_eq!(views_builder.len(), len);
700            views_builder.finish()
701        } else {
702            // Otherwise, create a new buffer for large strings
703            // TODO: the original buffer could still be used
704            // by making multiple slices of u32::MAX length
705            GenericByteViewArray::<V>::from_iter(byte_array.iter())
706        }
707    }
708}
709
710impl<T: ByteViewType + ?Sized> From<GenericByteViewArray<T>> for ArrayData {
711    fn from(mut array: GenericByteViewArray<T>) -> Self {
712        let len = array.len();
713        array.buffers.insert(0, array.views.into_inner());
714        let builder = ArrayDataBuilder::new(T::DATA_TYPE)
715            .len(len)
716            .buffers(array.buffers)
717            .nulls(array.nulls);
718
719        unsafe { builder.build_unchecked() }
720    }
721}
722
723impl<'a, Ptr, T> FromIterator<&'a Option<Ptr>> for GenericByteViewArray<T>
724where
725    Ptr: AsRef<T::Native> + 'a,
726    T: ByteViewType + ?Sized,
727{
728    fn from_iter<I: IntoIterator<Item = &'a Option<Ptr>>>(iter: I) -> Self {
729        iter.into_iter()
730            .map(|o| o.as_ref().map(|p| p.as_ref()))
731            .collect()
732    }
733}
734
735impl<Ptr, T: ByteViewType + ?Sized> FromIterator<Option<Ptr>> for GenericByteViewArray<T>
736where
737    Ptr: AsRef<T::Native>,
738{
739    fn from_iter<I: IntoIterator<Item = Option<Ptr>>>(iter: I) -> Self {
740        let iter = iter.into_iter();
741        let mut builder = GenericByteViewBuilder::<T>::with_capacity(iter.size_hint().0);
742        builder.extend(iter);
743        builder.finish()
744    }
745}
746
747/// A [`GenericByteViewArray`] of `[u8]`
748///
749/// See [`GenericByteViewArray`] for format and layout details.
750///
751/// # Example
752/// ```
753/// use arrow_array::BinaryViewArray;
754/// let array = BinaryViewArray::from_iter_values(vec![b"hello" as &[u8], b"world", b"lulu", b"large payload over 12 bytes"]);
755/// assert_eq!(array.value(0), b"hello");
756/// assert_eq!(array.value(3), b"large payload over 12 bytes");
757/// ```
758pub type BinaryViewArray = GenericByteViewArray<BinaryViewType>;
759
760impl BinaryViewArray {
761    /// Convert the [`BinaryViewArray`] to [`StringViewArray`]
762    /// If items not utf8 data, validate will fail and error returned.
763    pub fn to_string_view(self) -> Result<StringViewArray, ArrowError> {
764        StringViewType::validate(self.views(), self.data_buffers())?;
765        unsafe { Ok(self.to_string_view_unchecked()) }
766    }
767
768    /// Convert the [`BinaryViewArray`] to [`StringViewArray`]
769    /// # Safety
770    /// Caller is responsible for ensuring that items in array are utf8 data.
771    pub unsafe fn to_string_view_unchecked(self) -> StringViewArray {
772        StringViewArray::new_unchecked(self.views, self.buffers, self.nulls)
773    }
774}
775
776impl From<Vec<&[u8]>> for BinaryViewArray {
777    fn from(v: Vec<&[u8]>) -> Self {
778        Self::from_iter_values(v)
779    }
780}
781
782impl From<Vec<Option<&[u8]>>> for BinaryViewArray {
783    fn from(v: Vec<Option<&[u8]>>) -> Self {
784        v.into_iter().collect()
785    }
786}
787
788/// A [`GenericByteViewArray`] that stores utf8 data
789///
790/// See [`GenericByteViewArray`] for format and layout details.
791///
792/// # Example
793/// ```
794/// use arrow_array::StringViewArray;
795/// let array = StringViewArray::from_iter_values(vec!["hello", "world", "lulu", "large payload over 12 bytes"]);
796/// assert_eq!(array.value(0), "hello");
797/// assert_eq!(array.value(3), "large payload over 12 bytes");
798/// ```
799pub type StringViewArray = GenericByteViewArray<StringViewType>;
800
801impl StringViewArray {
802    /// Convert the [`StringViewArray`] to [`BinaryViewArray`]
803    pub fn to_binary_view(self) -> BinaryViewArray {
804        unsafe { BinaryViewArray::new_unchecked(self.views, self.buffers, self.nulls) }
805    }
806
807    /// Returns true if all data within this array is ASCII
808    pub fn is_ascii(&self) -> bool {
809        // Alternative (but incorrect): directly check the underlying buffers
810        // (1) Our string view might be sparse, i.e., a subset of the buffers,
811        //      so even if the buffer is not ascii, we can still be ascii.
812        // (2) It is quite difficult to know the range of each buffer (unlike StringArray)
813        // This means that this operation is quite expensive, shall we cache the result?
814        //  i.e. track `is_ascii` in the builder.
815        self.iter().all(|v| match v {
816            Some(v) => v.is_ascii(),
817            None => true,
818        })
819    }
820}
821
822impl From<Vec<&str>> for StringViewArray {
823    fn from(v: Vec<&str>) -> Self {
824        Self::from_iter_values(v)
825    }
826}
827
828impl From<Vec<Option<&str>>> for StringViewArray {
829    fn from(v: Vec<Option<&str>>) -> Self {
830        v.into_iter().collect()
831    }
832}
833
834impl From<Vec<String>> for StringViewArray {
835    fn from(v: Vec<String>) -> Self {
836        Self::from_iter_values(v)
837    }
838}
839
840impl From<Vec<Option<String>>> for StringViewArray {
841    fn from(v: Vec<Option<String>>) -> Self {
842        v.into_iter().collect()
843    }
844}
845
846#[cfg(test)]
847mod tests {
848    use crate::builder::{BinaryViewBuilder, StringViewBuilder};
849    use crate::{Array, BinaryViewArray, StringViewArray};
850    use arrow_buffer::{Buffer, ScalarBuffer};
851    use arrow_data::ByteView;
852
853    #[test]
854    fn try_new_string() {
855        let array = StringViewArray::from_iter_values(vec![
856            "hello",
857            "world",
858            "lulu",
859            "large payload over 12 bytes",
860        ]);
861        assert_eq!(array.value(0), "hello");
862        assert_eq!(array.value(3), "large payload over 12 bytes");
863    }
864
865    #[test]
866    fn try_new_binary() {
867        let array = BinaryViewArray::from_iter_values(vec![
868            b"hello".as_slice(),
869            b"world".as_slice(),
870            b"lulu".as_slice(),
871            b"large payload over 12 bytes".as_slice(),
872        ]);
873        assert_eq!(array.value(0), b"hello");
874        assert_eq!(array.value(3), b"large payload over 12 bytes");
875    }
876
877    #[test]
878    fn try_new_empty_string() {
879        // test empty array
880        let array = {
881            let mut builder = StringViewBuilder::new();
882            builder.finish()
883        };
884        assert!(array.is_empty());
885    }
886
887    #[test]
888    fn try_new_empty_binary() {
889        // test empty array
890        let array = {
891            let mut builder = BinaryViewBuilder::new();
892            builder.finish()
893        };
894        assert!(array.is_empty());
895    }
896
897    #[test]
898    fn test_append_string() {
899        // test builder append
900        let array = {
901            let mut builder = StringViewBuilder::new();
902            builder.append_value("hello");
903            builder.append_null();
904            builder.append_option(Some("large payload over 12 bytes"));
905            builder.finish()
906        };
907        assert_eq!(array.value(0), "hello");
908        assert!(array.is_null(1));
909        assert_eq!(array.value(2), "large payload over 12 bytes");
910    }
911
912    #[test]
913    fn test_append_binary() {
914        // test builder append
915        let array = {
916            let mut builder = BinaryViewBuilder::new();
917            builder.append_value(b"hello");
918            builder.append_null();
919            builder.append_option(Some(b"large payload over 12 bytes"));
920            builder.finish()
921        };
922        assert_eq!(array.value(0), b"hello");
923        assert!(array.is_null(1));
924        assert_eq!(array.value(2), b"large payload over 12 bytes");
925    }
926
927    #[test]
928    fn test_in_progress_recreation() {
929        let array = {
930            // make a builder with small block size.
931            let mut builder = StringViewBuilder::new().with_fixed_block_size(14);
932            builder.append_value("large payload over 12 bytes");
933            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"));
934            builder.finish()
935        };
936        assert_eq!(array.value(0), "large payload over 12 bytes");
937        assert_eq!(array.value(1), "another large payload over 12 bytes that double than the first one, so that we can trigger the in_progress in builder re-created");
938        assert_eq!(2, array.buffers.len());
939    }
940
941    #[test]
942    #[should_panic(expected = "Invalid buffer index at 0: got index 3 but only has 1 buffers")]
943    fn new_with_invalid_view_data() {
944        let v = "large payload over 12 bytes";
945        let view = ByteView::new(13, &v.as_bytes()[0..4])
946            .with_buffer_index(3)
947            .with_offset(1);
948        let views = ScalarBuffer::from(vec![view.into()]);
949        let buffers = vec![Buffer::from_slice_ref(v)];
950        StringViewArray::new(views, buffers, None);
951    }
952
953    #[test]
954    #[should_panic(
955        expected = "Encountered non-UTF-8 data at index 0: invalid utf-8 sequence of 1 bytes from index 0"
956    )]
957    fn new_with_invalid_utf8_data() {
958        let v: Vec<u8> = vec![
959            // invalid UTF8
960            0xf0, 0x80, 0x80, 0x80, // more bytes to make it larger than 12
961            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
962        ];
963        let view = ByteView::new(v.len() as u32, &v[0..4]);
964        let views = ScalarBuffer::from(vec![view.into()]);
965        let buffers = vec![Buffer::from_slice_ref(v)];
966        StringViewArray::new(views, buffers, None);
967    }
968
969    #[test]
970    #[should_panic(expected = "View at index 0 contained non-zero padding for string of length 1")]
971    fn new_with_invalid_zero_padding() {
972        let mut data = [0; 12];
973        data[0] = b'H';
974        data[11] = 1; // no zero padding
975
976        let mut view_buffer = [0; 16];
977        view_buffer[0..4].copy_from_slice(&1u32.to_le_bytes());
978        view_buffer[4..].copy_from_slice(&data);
979
980        let view = ByteView::from(u128::from_le_bytes(view_buffer));
981        let views = ScalarBuffer::from(vec![view.into()]);
982        let buffers = vec![];
983        StringViewArray::new(views, buffers, None);
984    }
985
986    #[test]
987    #[should_panic(expected = "Mismatch between embedded prefix and data")]
988    fn test_mismatch_between_embedded_prefix_and_data() {
989        let input_str_1 = "Hello, Rustaceans!";
990        let input_str_2 = "Hallo, Rustaceans!";
991        let length = input_str_1.len() as u32;
992        assert!(input_str_1.len() > 12);
993
994        let mut view_buffer = [0; 16];
995        view_buffer[0..4].copy_from_slice(&length.to_le_bytes());
996        view_buffer[4..8].copy_from_slice(&input_str_1.as_bytes()[0..4]);
997        view_buffer[8..12].copy_from_slice(&0u32.to_le_bytes());
998        view_buffer[12..].copy_from_slice(&0u32.to_le_bytes());
999        let view = ByteView::from(u128::from_le_bytes(view_buffer));
1000        let views = ScalarBuffer::from(vec![view.into()]);
1001        let buffers = vec![Buffer::from_slice_ref(input_str_2.as_bytes())];
1002
1003        StringViewArray::new(views, buffers, None);
1004    }
1005
1006    #[test]
1007    fn test_gc() {
1008        let test_data = [
1009            Some("longer than 12 bytes"),
1010            Some("short"),
1011            Some("t"),
1012            Some("longer than 12 bytes"),
1013            None,
1014            Some("short"),
1015        ];
1016
1017        let array = {
1018            let mut builder = StringViewBuilder::new().with_fixed_block_size(8); // create multiple buffers
1019            test_data.into_iter().for_each(|v| builder.append_option(v));
1020            builder.finish()
1021        };
1022        assert!(array.buffers.len() > 1);
1023
1024        fn check_gc(to_test: &StringViewArray) {
1025            let gc = to_test.gc();
1026            assert_ne!(to_test.data_buffers().len(), gc.data_buffers().len());
1027
1028            to_test.iter().zip(gc.iter()).for_each(|(a, b)| {
1029                assert_eq!(a, b);
1030            });
1031            assert_eq!(to_test.len(), gc.len());
1032        }
1033
1034        check_gc(&array);
1035        check_gc(&array.slice(1, 3));
1036        check_gc(&array.slice(2, 1));
1037        check_gc(&array.slice(2, 2));
1038        check_gc(&array.slice(3, 1));
1039    }
1040
1041    #[test]
1042    fn test_eq() {
1043        let test_data = [
1044            Some("longer than 12 bytes"),
1045            None,
1046            Some("short"),
1047            Some("again, this is longer than 12 bytes"),
1048        ];
1049
1050        let array1 = {
1051            let mut builder = StringViewBuilder::new().with_fixed_block_size(8);
1052            test_data.into_iter().for_each(|v| builder.append_option(v));
1053            builder.finish()
1054        };
1055        let array2 = {
1056            // create a new array with the same data but different layout
1057            let mut builder = StringViewBuilder::new().with_fixed_block_size(100);
1058            test_data.into_iter().for_each(|v| builder.append_option(v));
1059            builder.finish()
1060        };
1061        assert_eq!(array1, array1.clone());
1062        assert_eq!(array2, array2.clone());
1063        assert_eq!(array1, array2);
1064    }
1065}