16970635821

Committed 14 Aug 2025 04:13PM UTC coverage: 85.882% (-1.8%) from 87.693%

Build # 16970635821

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 5182504a6 into f547cbca5

Pull Request Pull Request #4215: Ji/vectors

Run Details

80 of 1729 new or added lines in 38 files covered. (4.63%)

117 existing lines in 25 files now uncovered.

56994 of 66363 relevant lines covered (85.88%)

609331.7 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.01

/vortex-array/src/arrays/varbinview/mod.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::fmt::{Debug, Formatter};
use std::ops::Range;
use std::sync::Arc;

use static_assertions::{assert_eq_align, assert_eq_size};
use vortex_buffer::{Alignment, Buffer, ByteBuffer};
use vortex_dtype::{DType, Nullability};
use vortex_error::{VortexResult, VortexUnwrap, vortex_bail, vortex_panic};

use crate::builders::{ArrayBuilder, VarBinViewBuilder};
use crate::stats::{ArrayStats, StatsSetRef};
use crate::validity::Validity;
use crate::vtable::{
    ArrayVTable, CanonicalVTable, NotSupported, VTable, ValidityHelper,
    ValidityVTableFromValidityHelper,
};
use crate::{Canonical, EncodingId, EncodingRef, vtable};

mod accessor;
mod compact;
mod compute;
mod ops;
mod serde;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[repr(C, align(8))]
pub struct Inlined {
    size: u32,
    data: [u8; BinaryView::MAX_INLINED_SIZE],
}

impl Inlined {
    fn new<const N: usize>(value: &[u8]) -> Self {
        let mut inlined = Self {
            size: N.try_into().vortex_unwrap(),
            data: [0u8; BinaryView::MAX_INLINED_SIZE],
        };
        inlined.data[..N].copy_from_slice(&value[..N]);
        inlined
    }

    #[inline]
    pub fn value(&self) -> &[u8] {
        &self.data[0..(self.size as usize)]
    }
}

#[derive(Clone, Copy, Debug)]
#[repr(C, align(8))]
pub struct Ref {
    size: u32,
    prefix: [u8; 4],
    buffer_index: u32,
    offset: u32,
}

impl Ref {
    pub fn new(size: u32, prefix: [u8; 4], buffer_index: u32, offset: u32) -> Self {
        Self {
            size,
            prefix,
            buffer_index,
            offset,
        }
    }

    #[inline]
    pub fn buffer_index(&self) -> u32 {
        self.buffer_index
    }

    #[inline]
    pub fn offset(&self) -> u32 {
        self.offset
    }

    #[inline]
    pub fn prefix(&self) -> &[u8; 4] {
        &self.prefix
    }

    #[inline]
    pub fn to_range(&self) -> Range<usize> {
        self.offset as usize..(self.offset + self.size) as usize
    }
}

#[derive(Clone, Copy)]
#[repr(C, align(16))]
pub union BinaryView {
    // Numeric representation. This is logically `u128`, but we split it into the high and low
    // bits to preserve the alignment.
    le_bytes: [u8; 16],

    // Inlined representation: strings <= 12 bytes
    inlined: Inlined,

    // Reference type: strings > 12 bytes.
    _ref: Ref,
}

assert_eq_size!(BinaryView, [u8; 16]);
assert_eq_size!(Inlined, [u8; 16]);
assert_eq_size!(Ref, [u8; 16]);
assert_eq_align!(BinaryView, u128);

impl BinaryView {
    pub const MAX_INLINED_SIZE: usize = 12;

    /// Create a view from a value, block and offset
    ///
    /// Depending on the length of the provided value either a new inlined
    /// or a reference view will be constructed.
    ///
    /// Adapted from arrow-rs <https://github.com/apache/arrow-rs/blob/f4fde769ab6e1a9b75f890b7f8b47bc22800830b/arrow-array/src/builder/generic_bytes_view_builder.rs#L524>
    /// Explicitly enumerating inlined view produces code that avoids calling generic `ptr::copy_non_interleave` that's slower than explicit stores
    #[inline(never)]
    pub fn make_view(value: &[u8], block: u32, offset: u32) -> Self {
        match value.len() {
            0 => Self {
                inlined: Inlined::new::<0>(value),
            },
            1 => Self {
                inlined: Inlined::new::<1>(value),
            },
            2 => Self {
                inlined: Inlined::new::<2>(value),
            },
            3 => Self {
                inlined: Inlined::new::<3>(value),
            },
            4 => Self {
                inlined: Inlined::new::<4>(value),
            },
            5 => Self {
                inlined: Inlined::new::<5>(value),
            },
            6 => Self {
                inlined: Inlined::new::<6>(value),
            },
            7 => Self {
                inlined: Inlined::new::<7>(value),
            },
            8 => Self {
                inlined: Inlined::new::<8>(value),
            },
            9 => Self {
                inlined: Inlined::new::<9>(value),
            },
            10 => Self {
                inlined: Inlined::new::<10>(value),
            },
            11 => Self {
                inlined: Inlined::new::<11>(value),
            },
            12 => Self {
                inlined: Inlined::new::<12>(value),
            },
            _ => Self {
                _ref: Ref::new(
                    u32::try_from(value.len()).vortex_unwrap(),
                    value[0..4].try_into().vortex_unwrap(),
                    block,
                    offset,
                ),
            },
        }
    }

    /// Create a new empty view
    #[inline]
    pub fn empty_view() -> Self {
        Self::new_inlined(&[])
    }

    /// Create a new inlined binary view
    #[inline]
    pub fn new_inlined(value: &[u8]) -> Self {
        assert!(
            value.len() <= Self::MAX_INLINED_SIZE,
            "expected inlined value to be <= 12 bytes, was {}",
            value.len()
        );

        Self::make_view(value, 0, 0)
    }

    #[inline]
    pub fn len(&self) -> u32 {
        unsafe { self.inlined.size }
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() > 0
    }

    #[inline]
    #[allow(clippy::cast_possible_truncation)]
    pub fn is_inlined(&self) -> bool {
        self.len() <= (Self::MAX_INLINED_SIZE as u32)
    }

    pub fn as_inlined(&self) -> &Inlined {
        unsafe { &self.inlined }
    }

    pub fn as_view(&self) -> &Ref {
        unsafe { &self._ref }
    }

    pub fn as_u128(&self) -> u128 {
        // SAFETY: binary view always safe to read as u128 LE bytes
        unsafe { u128::from_le_bytes(self.le_bytes) }
    }

    /// Override the buffer reference with the given buffer_idx, only if this view is not inlined.
    #[inline(always)]
    pub fn with_buffer_idx(self, buffer_idx: u32) -> Self {
        if self.is_inlined() {
            self
        } else {
            // Referencing views must have their buffer_index adjusted with new offsets
            let view_ref = self.as_view();
            Self {
                _ref: Ref::new(
                    self.len(),
                    *view_ref.prefix(),
                    buffer_idx,
                    view_ref.offset(),
                ),
            }
        }
    }

    /// Shifts the buffer reference by the view by a given offset, useful when merging many
    /// varbinview arrays into one.
    #[inline(always)]
    pub fn offset_view(self, offset: u32) -> Self {
        if self.is_inlined() {
            self
        } else {
            // Referencing views must have their buffer_index adjusted with new offsets
            let view_ref = self.as_view();
            Self {
                _ref: Ref::new(
                    self.len(),
                    *view_ref.prefix(),
                    offset + view_ref.buffer_index(),
                    view_ref.offset(),
                ),
            }
        }
    }
}

impl From<u128> for BinaryView {
    fn from(value: u128) -> Self {
        BinaryView {
            le_bytes: value.to_le_bytes(),
        }
    }
}

impl Debug for BinaryView {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        let mut s = f.debug_struct("BinaryView");
        if self.is_inlined() {
            s.field("inline", &"i".to_string());
        } else {
            s.field("ref", &"r".to_string());
        }
        s.finish()
    }
}

vtable!(VarBinView);

impl VTable for VarBinViewVTable {
    type Array = VarBinViewArray;
    type Encoding = VarBinViewEncoding;

    type ArrayVTable = Self;
    type CanonicalVTable = Self;
    type OperationsVTable = Self;
    type ValidityVTable = ValidityVTableFromValidityHelper;
    type VisitorVTable = Self;
    type ComputeVTable = NotSupported;
    type EncodeVTable = NotSupported;
    type SerdeVTable = Self;

    fn id(_encoding: &Self::Encoding) -> EncodingId {
        EncodingId::new_ref("vortex.varbinview")
    }

    fn encoding(_array: &Self::Array) -> EncodingRef {
        EncodingRef::new_ref(VarBinViewEncoding.as_ref())
    }
}

/// A variable-length binary view array that stores strings and binary data efficiently.
///
/// This mirrors the Apache Arrow StringView/BinaryView array encoding and provides
/// an optimized representation for variable-length data with excellent performance
/// characteristics for both short and long strings.
///
/// ## Data Layout
///
/// The array uses a hybrid storage approach with two main components:
/// - **Views buffer**: Array of 16-byte `BinaryView` entries (one per logical element)
/// - **Data buffers**: Shared backing storage for strings longer than 12 bytes
///
/// ## View Structure
///
/// Commonly referred to as "German Strings", each 16-byte view entry contains either:
/// - **Inlined data**: For strings ≤ 12 bytes, the entire string is stored directly in the view
/// - **Reference data**: For strings > 12 bytes, contains:
///   - String length (4 bytes)
///   - First 4 bytes of string as prefix (4 bytes)
///   - Buffer index and offset (8 bytes total)
///
/// The following ASCII graphic is reproduced verbatim from the Arrow documentation:
///
/// ```text
///                         ┌──────┬────────────────────────┐
///                         │length│      string value      │
///    Strings (len <= 12)  │      │    (padded with 0)     │
///                         └──────┴────────────────────────┘
///                          0    31                      127
///
///                         ┌───────┬───────┬───────┬───────┐
///                         │length │prefix │  buf  │offset │
///    Strings (len > 12)   │       │       │ index │       │
///                         └───────┴───────┴───────┴───────┘
///                          0    31       63      95    127
/// ```
///
/// # Examples
///
/// ```
/// use vortex_array::arrays::VarBinViewArray;
/// use vortex_dtype::{DType, Nullability};
/// use vortex_array::IntoArray;
///
/// // Create from an Iterator<Item = &str>
/// let array = VarBinViewArray::from_iter_str([
///         "inlined",
///         "this string is outlined"
/// ]);
///
/// assert_eq!(array.len(), 2);
///
/// // Access individual strings
/// let first = array.bytes_at(0);
/// assert_eq!(first.as_slice(), b"inlined"); // "short"
///
/// let second = array.bytes_at(1);
/// assert_eq!(second.as_slice(), b"this string is outlined"); // Long string
/// ```
#[derive(Clone, Debug)]
pub struct VarBinViewArray {
    dtype: DType,
    buffers: Arc<[ByteBuffer]>,
    views: Buffer<BinaryView>,
    validity: Validity,
    stats_set: ArrayStats,
}

#[derive(Clone, Debug)]
pub struct VarBinViewEncoding;

impl VarBinViewArray {
    pub fn try_new(
        views: Buffer<BinaryView>,
        buffers: Arc<[ByteBuffer]>,
        dtype: DType,
        validity: Validity,
    ) -> VortexResult<Self> {
        if views.alignment() != Alignment::of::<BinaryView>() {
            vortex_bail!("Views must be aligned to a 128 bits");
        }

        if !matches!(dtype, DType::Binary(_) | DType::Utf8(_)) {
            vortex_bail!(MismatchedTypes: "utf8 or binary", dtype);
        }

        if dtype.is_nullable() == (validity == Validity::NonNullable) {
            vortex_bail!("incorrect validity {:?}", validity);
        }

        Ok(Self {
            dtype,
            buffers,
            views,
            validity,
            stats_set: Default::default(),
        })
    }

    /// Number of raw string data buffers held by this array.
    pub fn nbuffers(&self) -> usize {
        self.buffers.len()
    }

    /// Access to the primitive views buffer.
    ///
    /// Variable-sized binary view buffer contain a "view" child array, with 16-byte entries that
    /// contain either a pointer into one of the array's owned `buffer`s OR an inlined copy of
    /// the string (if the string has 12 bytes or fewer).
    #[inline]
    pub fn views(&self) -> &Buffer<BinaryView> {
        &self.views
    }

    /// Access value bytes at a given index
    ///
    /// Will return a bytebuffer pointing to the underlying data without performing a copy
    #[inline]
    pub fn bytes_at(&self, index: usize) -> ByteBuffer {
        let views = self.views();
        let view = &views[index];
        // Expect this to be the common case: strings > 12 bytes.
        if !view.is_inlined() {
            let view_ref = view.as_view();
            self.buffer(view_ref.buffer_index() as usize)
                .slice(view_ref.to_range())
        } else {
            // Return access to the range of bytes around it.
            views
                .clone()
                .into_byte_buffer()
                .slice_ref(view.as_inlined().value())
        }
    }

    /// Access one of the backing data buffers.
    ///
    /// # Panics
    ///
    /// This method panics if the provided index is out of bounds for the set of buffers provided
    /// at construction time.
    #[inline]
    pub fn buffer(&self, idx: usize) -> &ByteBuffer {
        if idx >= self.nbuffers() {
            vortex_panic!(
                "{idx} buffer index out of bounds, there are {} buffers",
                self.nbuffers()
            );
        }
        &self.buffers[idx]
    }

    /// Iterate over the underlying raw data buffers, not including the views buffer.
    #[inline]
    pub fn buffers(&self) -> &Arc<[ByteBuffer]> {
        &self.buffers
    }

    /// Accumulate an iterable set of values into our type here.
    #[allow(clippy::same_name_method)]
    pub fn from_iter<T: AsRef<[u8]>, I: IntoIterator<Item = Option<T>>>(
        iter: I,
        dtype: DType,
    ) -> Self {
        let iter = iter.into_iter();
        let mut builder = VarBinViewBuilder::with_capacity(dtype, iter.size_hint().0);

        for item in iter {
            match item {
                None => builder.append_null(),
                Some(v) => builder.append_value(v),
            }
        }

        builder.finish_into_varbinview()
    }

    pub fn from_iter_str<T: AsRef<str>, I: IntoIterator<Item = T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let mut builder = VarBinViewBuilder::with_capacity(
            DType::Utf8(Nullability::NonNullable),
            iter.size_hint().0,
        );

        for item in iter {
            builder.append_value(item.as_ref());
        }

        builder.finish_into_varbinview()
    }

    pub fn from_iter_nullable_str<T: AsRef<str>, I: IntoIterator<Item = Option<T>>>(
        iter: I,
    ) -> Self {
        let iter = iter.into_iter();
        let mut builder = VarBinViewBuilder::with_capacity(
            DType::Utf8(Nullability::Nullable),
            iter.size_hint().0,
        );

        for item in iter {
            match item {
                None => builder.append_null(),
                Some(v) => builder.append_value(v.as_ref()),
            }
        }

        builder.finish_into_varbinview()
    }

    pub fn from_iter_bin<T: AsRef<[u8]>, I: IntoIterator<Item = T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let mut builder = VarBinViewBuilder::with_capacity(
            DType::Binary(Nullability::NonNullable),
            iter.size_hint().0,
        );

        for item in iter {
            builder.append_value(item.as_ref());
        }

        builder.finish_into_varbinview()
    }

    pub fn from_iter_nullable_bin<T: AsRef<[u8]>, I: IntoIterator<Item = Option<T>>>(
        iter: I,
    ) -> Self {
        let iter = iter.into_iter();
        let mut builder = VarBinViewBuilder::with_capacity(
            DType::Binary(Nullability::Nullable),
            iter.size_hint().0,
        );

        for item in iter {
            match item {
                None => builder.append_null(),
                Some(v) => builder.append_value(v.as_ref()),
            }
        }

        builder.finish_into_varbinview()
    }
}

impl ArrayVTable<VarBinViewVTable> for VarBinViewVTable {
    fn len(array: &VarBinViewArray) -> usize {
        array.views.len()
    }

    fn dtype(array: &VarBinViewArray) -> &DType {
        &array.dtype
    }

    fn stats(array: &VarBinViewArray) -> StatsSetRef<'_> {
        array.stats_set.to_ref(array.as_ref())
    }
}

impl ValidityHelper for VarBinViewArray {
    fn validity(&self) -> &Validity {
        &self.validity
    }
}

impl CanonicalVTable<VarBinViewVTable> for VarBinViewVTable {
    fn canonicalize(array: &VarBinViewArray) -> VortexResult<Canonical> {
        Ok(Canonical::VarBinView(array.clone()))
    }

    fn append_to_builder(
        array: &VarBinViewArray,
        builder: &mut dyn ArrayBuilder,
    ) -> VortexResult<()> {
        builder.extend_from_array(array.as_ref())
    }
}

impl<'a> FromIterator<Option<&'a [u8]>> for VarBinViewArray {
    fn from_iter<T: IntoIterator<Item = Option<&'a [u8]>>>(iter: T) -> Self {
        Self::from_iter_nullable_bin(iter)
    }
}

impl FromIterator<Option<Vec<u8>>> for VarBinViewArray {
    fn from_iter<T: IntoIterator<Item = Option<Vec<u8>>>>(iter: T) -> Self {
        Self::from_iter_nullable_bin(iter)
    }
}

impl FromIterator<Option<String>> for VarBinViewArray {
    fn from_iter<T: IntoIterator<Item = Option<String>>>(iter: T) -> Self {
        Self::from_iter_nullable_str(iter)
    }
}

impl<'a> FromIterator<Option<&'a str>> for VarBinViewArray {
    fn from_iter<T: IntoIterator<Item = Option<&'a str>>>(iter: T) -> Self {
        Self::from_iter_nullable_str(iter)
    }
}

#[cfg(test)]
mod test {
    use vortex_scalar::Scalar;

    use crate::arrays::varbinview::{BinaryView, VarBinViewArray};
    use crate::{Array, Canonical, IntoArray};

    #[test]
    pub fn varbin_view() {
        let binary_arr =
            VarBinViewArray::from_iter_str(["hello world", "hello world this is a long string"]);
        assert_eq!(binary_arr.len(), 2);
        assert_eq!(
            binary_arr.scalar_at(0).unwrap(),
            Scalar::from("hello world")
        );
        assert_eq!(
            binary_arr.scalar_at(1).unwrap(),
            Scalar::from("hello world this is a long string")
        );
    }

    #[test]
    pub fn slice_array() {
        let binary_arr =
            VarBinViewArray::from_iter_str(["hello world", "hello world this is a long string"])
                .slice(1, 2)
                .unwrap();
        assert_eq!(
            binary_arr.scalar_at(0).unwrap(),
            Scalar::from("hello world this is a long string")
        );
    }

    #[test]
    pub fn flatten_array() {
        let binary_arr = VarBinViewArray::from_iter_str(["string1", "string2"]);

        let flattened = binary_arr.to_canonical().unwrap();
        assert!(matches!(flattened, Canonical::VarBinView(_)));

        let var_bin = flattened.into_varbinview().unwrap().into_array();
        assert_eq!(var_bin.scalar_at(0).unwrap(), Scalar::from("string1"));
        assert_eq!(var_bin.scalar_at(1).unwrap(), Scalar::from("string2"));
    }

    #[test]
    pub fn binary_view_size_and_alignment() {
        assert_eq!(size_of::<BinaryView>(), 16);
        assert_eq!(align_of::<BinaryView>(), 16);
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::fmt::{Debug, Formatter};
5	use std::ops::Range;
6	use std::sync::Arc;
7
8	use static_assertions::{assert_eq_align, assert_eq_size};
9	use vortex_buffer::{Alignment, Buffer, ByteBuffer};
10	use vortex_dtype::{DType, Nullability};
11	use vortex_error::{VortexResult, VortexUnwrap, vortex_bail, vortex_panic};
12
13	use crate::builders::{ArrayBuilder, VarBinViewBuilder};
14	use crate::stats::{ArrayStats, StatsSetRef};
15	use crate::validity::Validity;
16	use crate::vtable::{
17	ArrayVTable, CanonicalVTable, NotSupported, VTable, ValidityHelper,
18	ValidityVTableFromValidityHelper,
19	};
20	use crate::{Canonical, EncodingId, EncodingRef, vtable};
21
22	mod accessor;
23	mod compact;
24	mod compute;
25	mod ops;
26	mod serde;
27
28	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
29	#[repr(C, align(8))]
30	pub struct Inlined {
31	size: u32,
32	data: [u8; BinaryView::MAX_INLINED_SIZE],
33	}
34
35	impl Inlined {
36	fn new<const N: usize>(value: &[u8]) -> Self {	1,042,830✔
37	let mut inlined = Self {	1,042,830✔
38	size: N.try_into().vortex_unwrap(),	1,042,830✔
39	data: [0u8; BinaryView::MAX_INLINED_SIZE],	1,042,830✔
40	};	1,042,830✔
41	inlined.data[..N].copy_from_slice(&value[..N]);	1,042,830✔
42	inlined	1,042,830✔
43	}	1,042,830✔
44
45	#[inline]
46	pub fn value(&self) -> &[u8] {	30,944,197✔
47	&self.data[0..(self.size as usize)]	30,944,197✔
48	}	30,944,197✔
49	}
50
51	#[derive(Clone, Copy, Debug)]
52	#[repr(C, align(8))]
53	pub struct Ref {
54	size: u32,
55	prefix: [u8; 4],
56	buffer_index: u32,
57	offset: u32,
58	}
59
60	impl Ref {
61	pub fn new(size: u32, prefix: [u8; 4], buffer_index: u32, offset: u32) -> Self {	6,617,700✔
62	Self {	6,617,700✔
63	size,	6,617,700✔
64	prefix,	6,617,700✔
65	buffer_index,	6,617,700✔
66	offset,	6,617,700✔
67	}	6,617,700✔
68	}	6,617,700✔
69
70	#[inline]
71	pub fn buffer_index(&self) -> u32 {	25,018,870✔
72	self.buffer_index	25,018,870✔
73	}	25,018,870✔
74
75	#[inline]
76	pub fn offset(&self) -> u32 {	1,372,941✔
77	self.offset	1,372,941✔
78	}	1,372,941✔
79
80	#[inline]
81	pub fn prefix(&self) -> &[u8; 4] {	1,372,941✔
82	&self.prefix	1,372,941✔
83	}	1,372,941✔
84
85	#[inline]
86	pub fn to_range(&self) -> Range<usize> {	24,993,565✔
87	self.offset as usize..(self.offset + self.size) as usize	24,993,565✔
88	}	24,993,565✔
89	}
90
91	#[derive(Clone, Copy)]
92	#[repr(C, align(16))]
93	pub union BinaryView {
94	// Numeric representation. This is logically `u128`, but we split it into the high and low
95	// bits to preserve the alignment.
96	le_bytes: [u8; 16],
97
98	// Inlined representation: strings <= 12 bytes
99	inlined: Inlined,
100
101	// Reference type: strings > 12 bytes.
102	_ref: Ref,
103	}
104
105	assert_eq_size!(BinaryView, [u8; 16]);
106	assert_eq_size!(Inlined, [u8; 16]);
107	assert_eq_size!(Ref, [u8; 16]);
108	assert_eq_align!(BinaryView, u128);
109
110	impl BinaryView {
111	pub const MAX_INLINED_SIZE: usize = 12;
112
113	/// Create a view from a value, block and offset
114	///
115	/// Depending on the length of the provided value either a new inlined
116	/// or a reference view will be constructed.
117	///
118	/// Adapted from arrow-rs <https://github.com/apache/arrow-rs/blob/f4fde769ab6e1a9b75f890b7f8b47bc22800830b/arrow-array/src/builder/generic_bytes_view_builder.rs#L524>
119	/// Explicitly enumerating inlined view produces code that avoids calling generic `ptr::copy_non_interleave` that's slower than explicit stores
120	#[inline(never)]
121	pub fn make_view(value: &[u8], block: u32, offset: u32) -> Self {	7,056,747✔
122	match value.len() {	7,056,747✔
123	0 => Self {	705,509✔
124	inlined: Inlined::new::<0>(value),	705,509✔
125	},	705,509✔
126	1 => Self {	3,630✔
127	inlined: Inlined::new::<1>(value),	3,630✔
128	},	3,630✔
129	2 => Self {	3,706✔
130	inlined: Inlined::new::<2>(value),	3,706✔
131	},	3,706✔
132	3 => Self {	10,961✔
133	inlined: Inlined::new::<3>(value),	10,961✔
134	},	10,961✔
135	4 => Self {	7,198✔
136	inlined: Inlined::new::<4>(value),	7,198✔
137	},	7,198✔
138	5 => Self {	21,552✔
139	inlined: Inlined::new::<5>(value),	21,552✔
140	},	21,552✔
141	6 => Self {	18,592✔
142	inlined: Inlined::new::<6>(value),	18,592✔
143	},	18,592✔
144	7 => Self {	14,958✔
145	inlined: Inlined::new::<7>(value),	14,958✔
146	},	14,958✔
147	8 => Self {	20,068✔
148	inlined: Inlined::new::<8>(value),	20,068✔
149	},	20,068✔
150	9 => Self {	12,907✔
151	inlined: Inlined::new::<9>(value),	12,907✔
152	},	12,907✔
153	10 => Self {	76,242✔
154	inlined: Inlined::new::<10>(value),	76,242✔
155	},	76,242✔
156	11 => Self {	76,919✔
157	inlined: Inlined::new::<11>(value),	76,919✔
158	},	76,919✔
159	12 => Self {	70,588✔
160	inlined: Inlined::new::<12>(value),	70,588✔
161	},	70,588✔
162	_ => Self {	6,013,917✔
163	_ref: Ref::new(	6,013,917✔
164	u32::try_from(value.len()).vortex_unwrap(),	6,013,917✔
165	value[0..4].try_into().vortex_unwrap(),	6,013,917✔
166	block,	6,013,917✔
167	offset,	6,013,917✔
168	),	6,013,917✔
169	},	6,013,917✔
170	}
171	}	7,056,747✔
172
173	/// Create a new empty view
174	#[inline]
175	pub fn empty_view() -> Self {	2,209✔
176	Self::new_inlined(&[])	2,209✔
177	}	2,209✔
178
179	/// Create a new inlined binary view
180	#[inline]
181	pub fn new_inlined(value: &[u8]) -> Self {	2,209✔
182	assert!(	2,209✔
183	value.len() <= Self::MAX_INLINED_SIZE,	2,209✔
UNCOV 184	"expected inlined value to be <= 12 bytes, was {}",	×
185	value.len()
186	);
187
188	Self::make_view(value, 0, 0)	2,209✔
189	}	2,209✔
190
191	#[inline]
192	pub fn len(&self) -> u32 {	65,890,307✔
193	unsafe { self.inlined.size }	65,890,307✔
194	}	65,890,307✔
195
196	#[inline]
197	pub fn is_empty(&self) -> bool {
198	self.len() > 0
UNCOV 199	}	×
200
201	#[inline]
202	#[allow(clippy::cast_possible_truncation)]
203	pub fn is_inlined(&self) -> bool {	61,141,410✔
204	self.len() <= (Self::MAX_INLINED_SIZE as u32)	61,141,410✔
205	}	61,141,410✔
206
207	pub fn as_inlined(&self) -> &Inlined {	31,039,935✔
208	unsafe { &self.inlined }	31,039,935✔
209	}	31,039,935✔
210
211	pub fn as_view(&self) -> &Ref {	46,788,483✔
212	unsafe { &self._ref }	46,788,483✔
213	}	46,788,483✔
214
215	pub fn as_u128(&self) -> u128 {	4,343,619✔
216	// SAFETY: binary view always safe to read as u128 LE bytes
217	unsafe { u128::from_le_bytes(self.le_bytes) }	4,343,619✔
218	}	4,343,619✔
219
220	/// Override the buffer reference with the given buffer_idx, only if this view is not inlined.
221	#[inline(always)]
222	pub fn with_buffer_idx(self, buffer_idx: u32) -> Self {	105✔
223	if self.is_inlined() {	105✔
UNCOV 224	self	×
225	} else {
226	// Referencing views must have their buffer_index adjusted with new offsets
227	let view_ref = self.as_view();	105✔
228	Self {	105✔
229	_ref: Ref::new(	105✔
230	self.len(),	105✔
231	*view_ref.prefix(),	105✔
232	buffer_idx,	105✔
233	view_ref.offset(),	105✔
234	),	105✔
235	}	105✔
236	}
237	}	105✔
238
239	/// Shifts the buffer reference by the view by a given offset, useful when merging many
240	/// varbinview arrays into one.
241	#[inline(always)]
242	pub fn offset_view(self, offset: u32) -> Self {	689,372✔
243	if self.is_inlined() {	689,372✔
244	self	85,694✔
245	} else {
246	// Referencing views must have their buffer_index adjusted with new offsets
247	let view_ref = self.as_view();	603,678✔
248	Self {	603,678✔
249	_ref: Ref::new(	603,678✔
250	self.len(),	603,678✔
251	*view_ref.prefix(),	603,678✔
252	offset + view_ref.buffer_index(),	603,678✔
253	view_ref.offset(),	603,678✔
254	),	603,678✔
255	}	603,678✔
256	}
257	}	689,372✔
258	}
259
260	impl From<u128> for BinaryView {
UNCOV 261	fn from(value: u128) -> Self {	×
UNCOV 262	BinaryView {	×
263	le_bytes: value.to_le_bytes(),
UNCOV 264	}	×
265	}
266	}
267
268	impl Debug for BinaryView {
269	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
270	let mut s = f.debug_struct("BinaryView");	×
271	if self.is_inlined() {	×
272	s.field("inline", &"i".to_string());	×
273	} else {
274	s.field("ref", &"r".to_string());
275	}
276	s.finish()	×
277	}	×
278	}
279
280	vtable!(VarBinView);
281
282	impl VTable for VarBinViewVTable {
283	type Array = VarBinViewArray;
284	type Encoding = VarBinViewEncoding;
285
286	type ArrayVTable = Self;
287	type CanonicalVTable = Self;
288	type OperationsVTable = Self;
289	type ValidityVTable = ValidityVTableFromValidityHelper;
290	type VisitorVTable = Self;
291	type ComputeVTable = NotSupported;
292	type EncodeVTable = NotSupported;
293	type SerdeVTable = Self;
294
295	fn id(_encoding: &Self::Encoding) -> EncodingId {	628,093✔
296	EncodingId::new_ref("vortex.varbinview")	628,093✔
297	}	628,093✔
298
299	fn encoding(_array: &Self::Array) -> EncodingRef {	60,107✔
300	EncodingRef::new_ref(VarBinViewEncoding.as_ref())	60,107✔
301	}	60,107✔
302	}
303		2✔
304	/// A variable-length binary view array that stores strings and binary data efficiently.	2✔
305	///	2✔
306	/// This mirrors the Apache Arrow StringView/BinaryView array encoding and provides
307	/// an optimized representation for variable-length data with excellent performance
308	/// characteristics for both short and long strings.
309	///
310	/// ## Data Layout
311	///
312	/// The array uses a hybrid storage approach with two main components:
313	/// - Views buffer: Array of 16-byte `BinaryView` entries (one per logical element)
314	/// - Data buffers: Shared backing storage for strings longer than 12 bytes
315	///
316	/// ## View Structure
317	///
318	/// Commonly referred to as "German Strings", each 16-byte view entry contains either:
319	/// - Inlined data: For strings ≤ 12 bytes, the entire string is stored directly in the view
320	/// - Reference data: For strings > 12 bytes, contains:
321	/// - String length (4 bytes)
322	/// - First 4 bytes of string as prefix (4 bytes)
323	/// - Buffer index and offset (8 bytes total)
324	///
325	/// The following ASCII graphic is reproduced verbatim from the Arrow documentation:
326	///
327	/// ```text
328	/// ┌──────┬────────────────────────┐
329	/// │length│ string value │
330	/// Strings (len <= 12) │ │ (padded with 0) │
331	/// └──────┴────────────────────────┘
332	/// 0 31 127
333	///
334	/// ┌───────┬───────┬───────┬───────┐
335	/// │length │prefix │ buf │offset │
336	/// Strings (len > 12) │ │ │ index │ │
337	/// └───────┴───────┴───────┴───────┘
338	/// 0 31 63 95 127
339	/// ```
340	///
341	/// # Examples
342	///
343	/// ```
344	/// use vortex_array::arrays::VarBinViewArray;
345	/// use vortex_dtype::{DType, Nullability};
346	/// use vortex_array::IntoArray;
347	///
348	/// // Create from an Iterator<Item = &str>
349	/// let array = VarBinViewArray::from_iter_str([
350	/// "inlined",
351	/// "this string is outlined"
352	/// ]);
353	///
354	/// assert_eq!(array.len(), 2);
355	///
356	/// // Access individual strings
357	/// let first = array.bytes_at(0);
358	/// assert_eq!(first.as_slice(), b"inlined"); // "short"
359	///
360	/// let second = array.bytes_at(1);
361	/// assert_eq!(second.as_slice(), b"this string is outlined"); // Long string
362	/// ```
363	#[derive(Clone, Debug)]
364	pub struct VarBinViewArray {
365	dtype: DType,
366	buffers: Arc<[ByteBuffer]>,
367	views: Buffer<BinaryView>,
368	validity: Validity,
369	stats_set: ArrayStats,
370	}
371
372	#[derive(Clone, Debug)]
373	pub struct VarBinViewEncoding;
374
375	impl VarBinViewArray {
376	pub fn try_new(	33,109✔
377	views: Buffer<BinaryView>,	33,109✔
378	buffers: Arc<[ByteBuffer]>,	33,109✔
379	dtype: DType,	33,109✔
380	validity: Validity,	33,109✔
381	) -> VortexResult<Self> {	33,109✔
382	if views.alignment() != Alignment::of::<BinaryView>() {	33,109✔
383	vortex_bail!("Views must be aligned to a 128 bits");
384	}	33,109✔
385
386	if !matches!(dtype, DType::Binary(_) \| DType::Utf8(_)) {	33,109✔
UNCOV 387	vortex_bail!(MismatchedTypes: "utf8 or binary", dtype);	×
388	}	33,109✔
389
390	if dtype.is_nullable() == (validity == Validity::NonNullable) {	33,109✔
391	vortex_bail!("incorrect validity {:?}", validity);	×
392	}	33,109✔
393
394	Ok(Self {	33,109✔
395	dtype,	33,109✔
396	buffers,	33,109✔
397	views,	33,109✔
398	validity,	33,109✔
399	stats_set: Default::default(),	33,109✔
400	})	33,109✔
401	}	33,109✔
402
403	/// Number of raw string data buffers held by this array.
404	pub fn nbuffers(&self) -> usize {	3,531,679✔
405	self.buffers.len()	3,531,679✔
406	}	3,531,679✔
407
408	/// Access to the primitive views buffer.
409	///
410	/// Variable-sized binary view buffer contain a "view" child array, with 16-byte entries that
411	/// contain either a pointer into one of the array's owned `buffer`s OR an inlined copy of
412	/// the string (if the string has 12 bytes or fewer).
413	#[inline]
414	pub fn views(&self) -> &Buffer<BinaryView> {	3,759,377✔
415	&self.views	3,759,377✔
416	}	3,759,377✔
417
418	/// Access value bytes at a given index
419	///
420	/// Will return a bytebuffer pointing to the underlying data without performing a copy
421	#[inline]
422	pub fn bytes_at(&self, index: usize) -> ByteBuffer {	3,674,688✔
423	let views = self.views();	3,674,688✔
424	let view = &views[index];	3,674,688✔
425	// Expect this to be the common case: strings > 12 bytes.
426	if !view.is_inlined() {	3,674,688✔
427	let view_ref = view.as_view();	3,418,171✔
428	self.buffer(view_ref.buffer_index() as usize)	3,418,171✔
429	.slice(view_ref.to_range())	3,418,171✔
430	} else {
431	// Return access to the range of bytes around it.
432	views	256,517✔
433	.clone()	256,517✔
434	.into_byte_buffer()	256,517✔
435	.slice_ref(view.as_inlined().value())	256,517✔
436	}
437	}	3,674,688✔
438
439	/// Access one of the backing data buffers.
440	///
441	/// # Panics
442	///
443	/// This method panics if the provided index is out of bounds for the set of buffers provided
444	/// at construction time.
445	#[inline]
446	pub fn buffer(&self, idx: usize) -> &ByteBuffer {	3,497,983✔
447	if idx >= self.nbuffers() {	3,497,983✔
448	vortex_panic!(
449	"{idx} buffer index out of bounds, there are {} buffers",
450	self.nbuffers()
451	);
452	}	3,497,983✔
453	&self.buffers[idx]	3,497,983✔
454	}	3,497,983✔
455
456	/// Iterate over the underlying raw data buffers, not including the views buffer.
457	#[inline]
458	pub fn buffers(&self) -> &Arc<[ByteBuffer]> {	54,995✔
459	&self.buffers	54,995✔
460	}	54,995✔
461
462	/// Accumulate an iterable set of values into our type here.
463	#[allow(clippy::same_name_method)]
464	pub fn from_iter<T: AsRef<[u8]>, I: IntoIterator<Item = Option<T>>>(	25✔
465	iter: I,	25✔
466	dtype: DType,	25✔
467	) -> Self {	25✔
468	let iter = iter.into_iter();	25✔
469	let mut builder = VarBinViewBuilder::with_capacity(dtype, iter.size_hint().0);	25✔
470
471	for item in iter {	2,149✔
472	match item {	2,124✔
473	None => builder.append_null(),	9✔
474	Some(v) => builder.append_value(v),	2,115✔
475	}
476	}
477
478	builder.finish_into_varbinview()	25✔
479	}	25✔
480
481	pub fn from_iter_str<T: AsRef<str>, I: IntoIterator<Item = T>>(iter: I) -> Self {	13✔
482	let iter = iter.into_iter();	13✔
483	let mut builder = VarBinViewBuilder::with_capacity(	13✔
484	DType::Utf8(Nullability::NonNullable),	13✔
485	iter.size_hint().0,	13✔
486	);
487
488	for item in iter {	56✔
489	builder.append_value(item.as_ref());	43✔
490	}	43✔
491
492	builder.finish_into_varbinview()	13✔
493	}	13✔
494
495	pub fn from_iter_nullable_str<T: AsRef<str>, I: IntoIterator<Item = Option<T>>>(	20✔
496	iter: I,	20✔
497	) -> Self {	20✔
498	let iter = iter.into_iter();	20✔
499	let mut builder = VarBinViewBuilder::with_capacity(	20✔
500	DType::Utf8(Nullability::Nullable),	20✔
501	iter.size_hint().0,	20✔
502	);
503
504	for item in iter {	141✔
505	match item {	121✔
506	None => builder.append_null(),	37✔
507	Some(v) => builder.append_value(v.as_ref()),	84✔
508	}
509	}
510
511	builder.finish_into_varbinview()	20✔
512	}	20✔
513
514	pub fn from_iter_bin<T: AsRef<[u8]>, I: IntoIterator<Item = T>>(iter: I) -> Self {	2✔
515	let iter = iter.into_iter();	2✔
516	let mut builder = VarBinViewBuilder::with_capacity(	2✔
517	DType::Binary(Nullability::NonNullable),	2✔
518	iter.size_hint().0,	2✔
519	);
520
521	for item in iter {	6✔
522	builder.append_value(item.as_ref());	4✔
523	}	4✔
524
525	builder.finish_into_varbinview()	2✔
526	}	2✔
527
528	pub fn from_iter_nullable_bin<T: AsRef<[u8]>, I: IntoIterator<Item = Option<T>>>(	3✔
529	iter: I,	3✔
530	) -> Self {	3✔
531	let iter = iter.into_iter();	3✔
532	let mut builder = VarBinViewBuilder::with_capacity(	3✔
533	DType::Binary(Nullability::Nullable),	3✔
534	iter.size_hint().0,	3✔
535	);
536
537	for item in iter {	34✔
538	match item {	31✔
539	None => builder.append_null(),	11✔
540	Some(v) => builder.append_value(v.as_ref()),	20✔
541	}
542	}
543
544	builder.finish_into_varbinview()	3✔
545	}	3✔
546	}
547
548	impl ArrayVTable<VarBinViewVTable> for VarBinViewVTable {
549	fn len(array: &VarBinViewArray) -> usize {	4,297,713✔
550	array.views.len()	4,297,713✔
551	}	4,297,713✔
552
553	fn dtype(array: &VarBinViewArray) -> &DType {	641,015✔
554	&array.dtype	641,015✔
555	}	641,015✔
556
557	fn stats(array: &VarBinViewArray) -> StatsSetRef<'_> {	199,948✔
558	array.stats_set.to_ref(array.as_ref())	199,948✔
559	}	199,948✔
560	}
561
562	impl ValidityHelper for VarBinViewArray {
563	fn validity(&self) -> &Validity {	3,902,599✔
564	&self.validity	3,902,599✔
565	}	3,902,599✔
566	}
567
568	impl CanonicalVTable<VarBinViewVTable> for VarBinViewVTable {
569	fn canonicalize(array: &VarBinViewArray) -> VortexResult<Canonical> {	38,406✔
570	Ok(Canonical::VarBinView(array.clone()))	38,406✔
571	}	38,406✔
572
573	fn append_to_builder(	7,230✔
574	array: &VarBinViewArray,	7,230✔
575	builder: &mut dyn ArrayBuilder,	7,230✔
576	) -> VortexResult<()> {	7,230✔
577	builder.extend_from_array(array.as_ref())	7,230✔
578	}	7,230✔
579	}
580
581	impl<'a> FromIterator<Option<&'a [u8]>> for VarBinViewArray {
UNCOV 582	fn from_iter<T: IntoIterator<Item = Option<&'a [u8]>>>(iter: T) -> Self {	×
UNCOV 583	Self::from_iter_nullable_bin(iter)	×
UNCOV 584	}	×
585	}
586
587	impl FromIterator<Option<Vec<u8>>> for VarBinViewArray {
588	fn from_iter<T: IntoIterator<Item = Option<Vec<u8>>>>(iter: T) -> Self {
589	Self::from_iter_nullable_bin(iter)
590	}	×
591	}
592
593	impl FromIterator<Option<String>> for VarBinViewArray {
594	fn from_iter<T: IntoIterator<Item = Option<String>>>(iter: T) -> Self {
595	Self::from_iter_nullable_str(iter)
596	}	×
597	}
598
599	impl<'a> FromIterator<Option<&'a str>> for VarBinViewArray {
600	fn from_iter<T: IntoIterator<Item = Option<&'a str>>>(iter: T) -> Self {	6✔
601	Self::from_iter_nullable_str(iter)	6✔
602	}	6✔
603	}
604
605	#[cfg(test)]
606	mod test {
607	use vortex_scalar::Scalar;
608
609	use crate::arrays::varbinview::{BinaryView, VarBinViewArray};
610	use crate::{Array, Canonical, IntoArray};
611
612	#[test]
613	pub fn varbin_view() {	1✔
614	let binary_arr =	1✔
615	VarBinViewArray::from_iter_str(["hello world", "hello world this is a long string"]);	1✔
616	assert_eq!(binary_arr.len(), 2);	1✔
617	assert_eq!(	1✔
618	binary_arr.scalar_at(0).unwrap(),	1✔
619	Scalar::from("hello world")	1✔
620	);
621	assert_eq!(	1✔
622	binary_arr.scalar_at(1).unwrap(),	1✔
623	Scalar::from("hello world this is a long string")	1✔
624	);
625	}	1✔
626
627	#[test]
628	pub fn slice_array() {	1✔
629	let binary_arr =	1✔
630	VarBinViewArray::from_iter_str(["hello world", "hello world this is a long string"])	1✔
631	.slice(1, 2)	1✔
632	.unwrap();	1✔
633	assert_eq!(	1✔
634	binary_arr.scalar_at(0).unwrap(),	1✔
635	Scalar::from("hello world this is a long string")	1✔
636	);
637	}	1✔
638
639	#[test]
640	pub fn flatten_array() {	1✔
641	let binary_arr = VarBinViewArray::from_iter_str(["string1", "string2"]);	1✔
642
643	let flattened = binary_arr.to_canonical().unwrap();	1✔
644	assert!(matches!(flattened, Canonical::VarBinView(_)));	1✔
645
646	let var_bin = flattened.into_varbinview().unwrap().into_array();	1✔
647	assert_eq!(var_bin.scalar_at(0).unwrap(), Scalar::from("string1"));	1✔
648	assert_eq!(var_bin.scalar_at(1).unwrap(), Scalar::from("string2"));	1✔
649	}	1✔
650
651	#[test]
652	pub fn binary_view_size_and_alignment() {	1✔
653	assert_eq!(size_of::<BinaryView>(), 16);	1✔
654	assert_eq!(align_of::<BinaryView>(), 16);	1✔
655	}	1✔
656	}

vortex-data / vortex / 16970635821

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous