vortex_array/arrays/varbinview/view/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! The 16-byte view struct stored in variable-length binary vectors.
5
6use std::fmt;
7use std::hash::Hash;
8use std::hash::Hasher;
9use std::ops::Range;
10
11use static_assertions::assert_eq_align;
12use static_assertions::assert_eq_size;
13use vortex_error::VortexExpect;
14
15/// A view over a variable-length binary value.
16///
17/// Either an inlined representation (for values <= 12 bytes) or a reference
18/// to an external buffer (for values > 12 bytes).
19///
20/// # Comparison words
21///
22/// Every view stores the value's length and its zero-padded first four bytes, so most comparisons
23/// are answered from the view without reading the value. [`head`](Self::head) rules equality out;
24/// [`order_prefix`](Self::order_prefix) and [`order_tail`](Self::order_tail) order values. Each
25/// has an `_of` constructor for a value not held in a view.
26///
27/// Zero padding keeps the ordering exact: a lower word means the values differ at a byte both
28/// have, or the shorter is a proper prefix of the longer — and either way it orders first.
29#[derive(Clone, Copy)]
30#[repr(C, align(16))]
31pub union BinaryView {
32    /// Numeric representation. This is logically `u128`, but we split it into the high and low
33    /// bits to preserve the alignment.
34    pub(crate) le_bytes: [u8; 16],
35
36    /// Inlined representation: strings <= 12 bytes
37    pub(crate) inlined: Inlined,
38
39    /// Reference type: strings > 12 bytes.
40    pub(crate) _ref: Ref,
41}
42
43assert_eq_align!(BinaryView, u128);
44assert_eq_size!(BinaryView, [u8; 16]);
45assert_eq_size!(Inlined, [u8; 16]);
46assert_eq_size!(Ref, [u8; 16]);
47
48/// Variant of a [`BinaryView`] that holds an inlined value.
49#[derive(Clone, Copy, Debug, PartialEq, Eq)]
50#[repr(C, align(8))]
51pub struct Inlined {
52    /// The size of the full value.
53    pub size: u32,
54    /// The full inlined value.
55    pub data: [u8; BinaryView::MAX_INLINED_SIZE],
56}
57
58impl Inlined {
59    /// Creates a new inlined representation from the provided value of constant size.
60    fn new<const N: usize>(value: &[u8]) -> Self {
61        debug_assert_eq!(value.len(), N);
62        let mut inlined = Self {
63            size: N.try_into().vortex_expect("inlined size must fit in u32"),
64            data: [0u8; BinaryView::MAX_INLINED_SIZE],
65        };
66        inlined.data[..N].copy_from_slice(&value[..N]);
67        inlined
68    }
69
70    /// Returns the full inlined value.
71    #[inline]
72    pub fn value(&self) -> &[u8] {
73        &self.data[0..(self.size as usize)]
74    }
75}
76
77/// Variant of a [`BinaryView`] that holds a reference to an external buffer.
78#[derive(Clone, Copy, Debug)]
79#[repr(C, align(8))]
80pub struct Ref {
81    /// The size of the full value.
82    pub size: u32,
83    /// The prefix bytes of the value (first 4 bytes).
84    pub prefix: [u8; 4],
85    /// The index of the buffer where the full value is stored.
86    pub buffer_index: u32,
87    /// The offset within the buffer where the full value starts.
88    pub offset: u32,
89}
90
91impl Ref {
92    /// Returns the range within the buffer where the full value is stored.
93    #[inline]
94    pub fn as_range(&self) -> Range<usize> {
95        self.offset as usize..(self.offset + self.size) as usize
96    }
97
98    /// Replaces the buffer index and offset of the reference, returning a new `Ref`.
99    #[inline]
100    pub fn with_buffer_and_offset(&self, buffer_index: u32, offset: u32) -> Ref {
101        Self {
102            size: self.size,
103            prefix: self.prefix,
104            buffer_index,
105            offset,
106        }
107    }
108}
109
110impl BinaryView {
111    /// Maximum size of an inlined binary value.
112    ///
113    /// cbindgen:ignore
114    pub const MAX_INLINED_SIZE: usize = 12;
115
116    /// Create a view from a value, block and offset
117    ///
118    /// Depending on the length of the provided value either a new inlined
119    /// or a reference view will be constructed.
120    ///
121    /// Adapted from arrow-rs <https://github.com/apache/arrow-rs/blob/f4fde769ab6e1a9b75f890b7f8b47bc22800830b/arrow-array/src/builder/generic_bytes_view_builder.rs#L524>
122    /// Explicitly enumerating inlined view produces code that avoids calling generic `ptr::copy_non_interleave` that's slower than explicit stores
123    #[inline(never)]
124    pub fn make_view(value: &[u8], block: u32, offset: u32) -> Self {
125        match value.len() {
126            0 => Self {
127                inlined: Inlined::new::<0>(value),
128            },
129            1 => Self {
130                inlined: Inlined::new::<1>(value),
131            },
132            2 => Self {
133                inlined: Inlined::new::<2>(value),
134            },
135            3 => Self {
136                inlined: Inlined::new::<3>(value),
137            },
138            4 => Self {
139                inlined: Inlined::new::<4>(value),
140            },
141            5 => Self {
142                inlined: Inlined::new::<5>(value),
143            },
144            6 => Self {
145                inlined: Inlined::new::<6>(value),
146            },
147            7 => Self {
148                inlined: Inlined::new::<7>(value),
149            },
150            8 => Self {
151                inlined: Inlined::new::<8>(value),
152            },
153            9 => Self {
154                inlined: Inlined::new::<9>(value),
155            },
156            10 => Self {
157                inlined: Inlined::new::<10>(value),
158            },
159            11 => Self {
160                inlined: Inlined::new::<11>(value),
161            },
162            12 => Self {
163                inlined: Inlined::new::<12>(value),
164            },
165            _ => Self::new_ref(
166                u32::try_from(value.len()).vortex_expect("value length must fit in u32"),
167                value[0..4]
168                    .try_into()
169                    .ok()
170                    .vortex_expect("prefix must be exactly 4 bytes"),
171                block,
172                offset,
173            ),
174        }
175    }
176
177    /// Create a new empty view
178    #[inline]
179    pub fn empty_view() -> Self {
180        Self { le_bytes: [0; 16] }
181    }
182
183    /// Create a reference view directly from its components, without inspecting the value.
184    ///
185    /// `size` must be greater than [`MAX_INLINED_SIZE`], and `prefix` must hold the first four
186    /// bytes of the value. This is the fast path for bulk view construction where the caller has
187    /// already established that the value is too long to inline; it assembles the 16-byte view as a
188    /// single `u128` so the compiler can emit one wide store per view.
189    ///
190    /// [`MAX_INLINED_SIZE`]: Self::MAX_INLINED_SIZE
191    #[inline]
192    pub fn new_ref(size: u32, prefix: [u8; 4], buffer_index: u32, offset: u32) -> Self {
193        debug_assert!(size as usize > Self::MAX_INLINED_SIZE);
194        // Matches the little-endian field order of `Ref` (size, prefix, buffer_index, offset),
195        // consistent with `le_bytes` and the `From<u128>`/`as_u128` representation.
196        Self::from(
197            u128::from(size)
198                | (u128::from(u32::from_le_bytes(prefix)) << 32)
199                | (u128::from(buffer_index) << 64)
200                | (u128::from(offset) << 96),
201        )
202    }
203
204    /// Create a new inlined binary view
205    ///
206    /// # Panics
207    ///
208    /// Panics if the provided string is too long to inline.
209    #[inline]
210    pub fn new_inlined(value: &[u8]) -> Self {
211        assert!(
212            value.len() <= Self::MAX_INLINED_SIZE,
213            "expected inlined value to be <= 12 bytes, was {}",
214            value.len()
215        );
216
217        Self::make_view(value, 0, 0)
218    }
219
220    /// Returns the length of the binary value.
221    #[inline]
222    pub fn len(&self) -> u32 {
223        unsafe { self.inlined.size }
224    }
225
226    /// Returns true if the binary value is empty.
227    #[inline]
228    pub fn is_empty(&self) -> bool {
229        self.len() == 0
230    }
231
232    /// Returns true if the binary value is inlined.
233    #[inline]
234    #[expect(
235        clippy::cast_possible_truncation,
236        reason = "MAX_INLINED_SIZE is a small constant"
237    )]
238    pub fn is_inlined(&self) -> bool {
239        self.len() <= (Self::MAX_INLINED_SIZE as u32)
240    }
241
242    /// Returns the inlined representation of the binary value.
243    pub fn as_inlined(&self) -> &Inlined {
244        debug_assert!(self.is_inlined());
245        unsafe { &self.inlined }
246    }
247
248    /// Returns the reference representation of the binary value.
249    pub fn as_view(&self) -> &Ref {
250        debug_assert!(!self.is_inlined());
251        unsafe { &self._ref }
252    }
253
254    /// Returns a mutable reference to the reference representation of the binary value.
255    pub fn as_view_mut(&mut self) -> &mut Ref {
256        unsafe { &mut self._ref }
257    }
258
259    /// The bytes of this value, read out of `buffers` when it is not inlined.
260    ///
261    /// # Panics
262    ///
263    /// Panics if the view references a buffer or range not covered by `buffers`.
264    #[inline]
265    pub fn bytes<'a>(&'a self, buffers: &[&'a [u8]]) -> &'a [u8] {
266        if self.is_inlined() {
267            self.as_inlined().value()
268        } else {
269            let view = self.as_view();
270            &buffers[view.buffer_index as usize][view.as_range()]
271        }
272    }
273
274    /// The value's first four bytes, zero-padded; both view variants store them at this offset.
275    #[inline]
276    #[expect(clippy::cast_possible_truncation, reason = "intentional bit slicing")]
277    pub fn prefix(&self) -> [u8; 4] {
278        ((self.as_u128() >> 32) as u32).to_le_bytes()
279    }
280
281    /// The value's length and [`prefix`](Self::prefix) as stored. Equal values have equal heads.
282    #[inline]
283    #[expect(clippy::cast_possible_truncation, reason = "intentional bit slicing")]
284    pub fn head(&self) -> u64 {
285        self.as_u128() as u64
286    }
287
288    /// The [`prefix`](Self::prefix) as a big-endian `u32`, which orders as the values do.
289    #[inline]
290    pub fn order_prefix(&self) -> u32 {
291        u32::from_be_bytes(self.prefix())
292    }
293
294    /// Value bytes `4..12` of an inlined view as a big-endian `u64`, zero-padded. Meaningless for
295    /// a reference view, which stores its buffer index and offset there.
296    #[inline]
297    pub fn order_tail(&self) -> u64 {
298        debug_assert!(self.is_inlined(), "order_tail of a reference view");
299        ((self.as_u128() >> 64) as u64).swap_bytes()
300    }
301
302    /// The [`prefix`](Self::prefix) a view holding `value` would carry.
303    #[inline]
304    pub fn prefix_of(value: &[u8]) -> [u8; 4] {
305        let mut prefix = [0u8; 4];
306        let len = value.len().min(prefix.len());
307        prefix[..len].copy_from_slice(&value[..len]);
308        prefix
309    }
310
311    /// The [`head`](Self::head) a view holding `value` would carry; lengths over `u32::MAX`
312    /// saturate.
313    #[inline]
314    pub fn head_of(value: &[u8]) -> u64 {
315        let len = u32::try_from(value.len()).unwrap_or(u32::MAX);
316        u64::from(len) | (u64::from(u32::from_le_bytes(Self::prefix_of(value))) << 32)
317    }
318
319    /// The [`order_prefix`](Self::order_prefix) a view holding `value` would carry.
320    #[inline]
321    pub fn order_prefix_of(value: &[u8]) -> u32 {
322        u32::from_be_bytes(Self::prefix_of(value))
323    }
324
325    /// The [`order_tail`](Self::order_tail) an inlined view holding `value` would carry.
326    #[inline]
327    pub fn order_tail_of(value: &[u8]) -> u64 {
328        let mut tail = [0u8; 8];
329        let value = value.get(4..).unwrap_or_default();
330        let len = value.len().min(tail.len());
331        tail[..len].copy_from_slice(&value[..len]);
332        u64::from_be_bytes(tail)
333    }
334
335    /// Returns the binary view as u128 representation.
336    pub fn as_u128(&self) -> u128 {
337        // SAFETY: binary view always safe to read as u128 LE bytes
338        unsafe { u128::from_le_bytes(self.le_bytes) }
339    }
340}
341
342impl From<u128> for BinaryView {
343    fn from(value: u128) -> Self {
344        BinaryView {
345            le_bytes: value.to_le_bytes(),
346        }
347    }
348}
349
350impl From<Ref> for BinaryView {
351    fn from(value: Ref) -> Self {
352        BinaryView { _ref: value }
353    }
354}
355
356impl PartialEq for BinaryView {
357    fn eq(&self, other: &Self) -> bool {
358        let a = unsafe { std::mem::transmute::<&BinaryView, &u128>(self) };
359        let b = unsafe { std::mem::transmute::<&BinaryView, &u128>(other) };
360        a == b
361    }
362}
363impl Eq for BinaryView {}
364
365impl Hash for BinaryView {
366    fn hash<H: Hasher>(&self, state: &mut H) {
367        unsafe { std::mem::transmute::<&BinaryView, &u128>(self) }.hash(state);
368    }
369}
370
371impl Default for BinaryView {
372    fn default() -> Self {
373        Self::make_view(&[], 0, 0)
374    }
375}
376
377impl fmt::Debug for BinaryView {
378    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
379        let mut s = f.debug_struct("BinaryView");
380        if self.is_inlined() {
381            s.field("inline", &self.as_inlined());
382        } else {
383            s.field("ref", &self.as_view());
384        }
385        s.finish()
386    }
387}
388
389#[cfg(test)]
390mod tests;
vortex_array/arrays/varbinview/view/mod.rs

vortex_array/arrays/varbinview/view/
mod.rs
