Skip to main content

vortex_array/arrays/varbin/
builder.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::any::Any;
5use std::mem::MaybeUninit;
6
7use num_traits::AsPrimitive;
8use vortex_buffer::Alignment;
9use vortex_buffer::BitBufferMut;
10use vortex_buffer::BufferAllocatorRef;
11use vortex_buffer::BufferMut;
12use vortex_buffer::ByteBuffer;
13use vortex_buffer::ByteBufferMut;
14use vortex_error::VortexExpect;
15use vortex_error::VortexResult;
16use vortex_error::vortex_bail;
17use vortex_error::vortex_ensure;
18use vortex_error::vortex_ensure_eq;
19use vortex_error::vortex_panic;
20use vortex_mask::AllOr;
21use vortex_mask::Mask;
22
23use crate::ArrayRef;
24use crate::ArrayView;
25use crate::Canonical;
26use crate::ExecutionCtx;
27use crate::IntoArray;
28use crate::arrays::PrimitiveArray;
29use crate::arrays::VarBin;
30use crate::arrays::VarBinArray;
31use crate::arrays::VarBinView;
32use crate::arrays::varbin::VarBinArrayExt;
33use crate::arrays::varbin::VarBinArraySlotsExt;
34use crate::arrays::varbinview::VarBinViewArrayExt;
35use crate::builders::ArrayBuilder;
36use crate::dtype::DType;
37use crate::dtype::OffsetBuilderPType;
38use crate::expr::stats::Precision;
39use crate::expr::stats::Stat;
40use crate::match_each_integer_ptype;
41use crate::scalar::Scalar;
42use crate::validity::Validity;
43
44/// Builder for [`VarBinArray`] values with `O`-typed offsets.
45///
46/// This is the offset-based counterpart to
47/// [`VarBinViewBuilder`](crate::builders::VarBinViewBuilder): values are laid out contiguously in
48/// a single byte buffer described by a monotonically increasing offsets buffer. An `i32` or `i64`
49/// builder can therefore be handed straight to Arrow as a `Utf8`/`LargeUtf8`/`Binary`/
50/// `LargeBinary` array without re-laying out the bytes.
51///
52/// Encodings that can decode into this layout should specialize
53/// [`append_to_builder`](crate::vtable::VTable::append_to_builder) with
54/// [`match_each_varbin_builder!`](crate::match_each_varbin_builder), which recovers the concrete
55/// offset type from a `&mut dyn ArrayBuilder` so the decode loop is monomorphized over it.
56pub struct VarBinBuilder<O: OffsetBuilderPType> {
57    dtype: DType,
58    offsets: BufferMut<O>,
59    data: ByteBufferMut,
60    validity: BitBufferMut,
61}
62
63impl<O: OffsetBuilderPType> VarBinBuilder<O> {
64    /// Creates an empty builder for `dtype`.
65    #[deprecated(note = "use `new_in` with an explicit allocator")]
66    pub fn new(dtype: DType) -> Self {
67        Self::new_in(dtype, BufferAllocatorRef::static_ref())
68    }
69
70    /// Creates an empty builder for `dtype` using `allocator`.
71    pub fn new_in(dtype: DType, allocator: &BufferAllocatorRef) -> Self {
72        Self::with_capacity_in(dtype, 0, allocator)
73    }
74
75    /// Creates a builder for `dtype` with room for `capacity` values.
76    #[deprecated(note = "use `with_capacity_in` with an explicit allocator")]
77    pub fn with_capacity(dtype: DType, capacity: usize) -> Self {
78        Self::with_capacity_in(dtype, capacity, BufferAllocatorRef::static_ref())
79    }
80
81    /// Creates a builder for `dtype` with room for `capacity` values using `allocator`.
82    pub fn with_capacity_in(dtype: DType, capacity: usize, allocator: &BufferAllocatorRef) -> Self {
83        assert!(
84            matches!(dtype, DType::Utf8(_) | DType::Binary(_)),
85            "VarBinBuilder dtype must be Utf8 or Binary, got {dtype}"
86        );
87        let mut offsets = BufferMut::with_capacity_in(capacity + 1, allocator.clone());
88        offsets.push(O::zero());
89        Self {
90            dtype,
91            offsets,
92            data: BufferMut::empty_aligned_in(Alignment::of::<u8>(), allocator.clone()),
93            validity: BitBufferMut::with_capacity_in(capacity, allocator.clone()),
94        }
95    }
96
97    /// Creates a builder for `dtype` with room for `capacity` values totalling `bytes` bytes.
98    #[deprecated(note = "use `with_capacity_bytes_in` with an explicit allocator")]
99    pub fn with_capacity_bytes(dtype: DType, capacity: usize, bytes: usize) -> Self {
100        Self::with_capacity_bytes_in(dtype, capacity, bytes, BufferAllocatorRef::static_ref())
101    }
102
103    /// Creates a builder using `allocator` with room for `capacity` values and `bytes` bytes.
104    pub fn with_capacity_bytes_in(
105        dtype: DType,
106        capacity: usize,
107        bytes: usize,
108        allocator: &BufferAllocatorRef,
109    ) -> Self {
110        let mut builder = Self::with_capacity_in(dtype, capacity, allocator);
111        builder.reserve_data(bytes);
112        builder
113    }
114
115    /// Reserves room for `additional` value bytes.
116    ///
117    /// [`reserve_exact`](ArrayBuilder::reserve_exact) takes a row count and so cannot size the
118    /// value bytes; callers that know the byte total should use this to size the buffer once
119    /// instead of letting it grow.
120    pub fn reserve_data(&mut self, additional: usize) {
121        self.data.reserve(additional);
122    }
123
124    /// Appends one value, or a null when it is `None`.
125    ///
126    /// # Panics
127    ///
128    /// Panics if the resulting end offset does not fit in `O`. See
129    /// [`append_value`](Self::append_value).
130    #[inline]
131    pub fn append(&mut self, value: Option<&[u8]>) {
132        match value {
133            Some(v) => self.append_value(v),
134            None => self.push_null(),
135        }
136    }
137
138    /// Appends one non-null value.
139    ///
140    /// # Panics
141    ///
142    /// Panics if the resulting end offset does not fit in `O`. The bulk appends report that as an
143    /// error instead; use [`append_n_values`](Self::append_n_values) for a fallible single append,
144    /// or an `i64` builder for byte totals past `i32::MAX`.
145    #[inline]
146    pub fn append_value(&mut self, value: impl AsRef<[u8]>) {
147        self.push_value(value.as_ref());
148        self.validity.append_true();
149    }
150
151    /// Appends the same non-null value `n` times.
152    ///
153    /// # Errors
154    ///
155    /// Returns an error, leaving the builder unchanged, if the resulting end offsets do not fit
156    /// in `O`.
157    pub fn append_n_values(&mut self, value: impl AsRef<[u8]>, n: usize) -> VortexResult<()> {
158        let value = value.as_ref();
159        let Some(num_bytes) = value.len().checked_mul(n) else {
160            vortex_bail!("Byte count overflow: {} values of {} bytes", n, value.len());
161        };
162        // Checking the total up front is what keeps `push_value` below from panicking.
163        self.check_offset_limit(self.data.len(), num_bytes)?;
164        self.offsets.reserve(n);
165        self.data.reserve(num_bytes);
166        for _ in 0..n {
167            self.push_value(value);
168        }
169        self.validity.append_n(true, n);
170        Ok(())
171    }
172
173    /// Appends a null value.
174    ///
175    /// Unlike [`append_null`](ArrayBuilder::append_null) this does not check that the builder is
176    /// nullable; the offsets and validity stay consistent either way, and a non-nullable `dtype`
177    /// discards the validity bits on [`finish_into_varbin`](Self::finish_into_varbin).
178    #[inline]
179    pub fn push_null(&mut self) {
180        self.push_nulls(1)
181    }
182
183    /// Appends `n` null values. See [`push_null`](Self::push_null).
184    #[inline]
185    pub fn push_nulls(&mut self, n: usize) {
186        self.offsets.push_n(self.last_offset(), n);
187        self.validity.append_n(false, n);
188    }
189
190    /// Appends the same UTF-8 or binary scalar `n` times.
191    ///
192    /// # Errors
193    ///
194    /// Returns an error if `scalar` has a different dtype than the builder, or if the resulting
195    /// end offsets do not fit in `O`.
196    pub fn append_scalar_repeated(&mut self, scalar: &Scalar, n: usize) -> VortexResult<()> {
197        vortex_ensure_eq!(
198            scalar.dtype(),
199            &self.dtype,
200            "VarBinBuilder scalar dtype does not match builder dtype",
201        );
202        match &self.dtype {
203            DType::Utf8(_) => match scalar.as_utf8().value() {
204                Some(value) => self.append_n_values(value, n)?,
205                None => self.push_nulls(n),
206            },
207            DType::Binary(_) => match scalar.as_binary().value() {
208                Some(value) => self.append_n_values(value, n)?,
209                None => self.push_nulls(n),
210            },
211            dtype => {
212                vortex_bail!("VarBinBuilder cannot append scalar of dtype {dtype}")
213            }
214        }
215        Ok(())
216    }
217
218    /// Appends values from one contiguous byte buffer described by relative end offsets.
219    ///
220    /// Each entry of `end_offsets` marks the end of one value relative to the start of `values`,
221    /// and there must be exactly one per entry in `validity`.
222    #[inline]
223    pub fn append_values<P>(
224        &mut self,
225        values: &[u8],
226        end_offsets: impl Iterator<Item = P>,
227        validity: &Mask,
228    ) -> VortexResult<()>
229    where
230        P: AsPrimitive<usize>,
231        usize: AsPrimitive<O>,
232    {
233        // Offsets are committed first: they are the only fallible part, and failing before the
234        // bytes are appended leaves the builder untouched.
235        self.extend_offsets(values.len(), validity.len(), end_offsets)?;
236        self.data.extend_from_slice(values);
237        self.append_validity(validity);
238        Ok(())
239    }
240
241    /// Appends values whose bytes `decode` writes straight into the builder's byte storage.
242    ///
243    /// `decode` is handed at least `num_bytes + slack` bytes of uninitialized storage and returns
244    /// the number of bytes it initialized, which must be exactly `num_bytes`. Each entry of
245    /// `lengths` is the byte length of one value — including nulls, which are zero-length — so
246    /// there must be one per entry in `validity`.
247    ///
248    /// `slack` is spare headroom past the values themselves. It exists so that a decoder which
249    /// stores in wide fixed-size chunks can keep using them through the final value instead of
250    /// dropping into a byte-at-a-time tail; a decoder must still never write past the slice it is
251    /// handed, so `0` is correct for one that is already exact.
252    ///
253    /// Decoding in place saves staging the decoded heap in a temporary buffer and copying it in.
254    ///
255    /// `decode` is taken as a `dyn` reference so a caller that resolves the `lengths` type with
256    /// [`match_each_integer_ptype!`](crate::match_each_integer_ptype) can build the closure once
257    /// outside that match rather than inlining a whole decoder into each of its arms.
258    ///
259    /// # Errors
260    ///
261    /// Returns an error, leaving the builder unchanged, if `num_bytes` would push an offset past
262    /// what `O` can hold — checked before `decode` runs — or if `decode` reports a different byte
263    /// count than `num_bytes`, or if `lengths` does not describe those bytes.
264    ///
265    /// # Safety
266    ///
267    /// `decode` must initialize the first `n` bytes of the slice it is passed, where `n` is the
268    /// value it returns. Those bytes are published as initialized without ever being read first,
269    /// so a `decode` that over-reports leaves the builder holding uninitialized memory.
270    pub unsafe fn append_decoded<P>(
271        &mut self,
272        num_bytes: usize,
273        slack: usize,
274        lengths: &[P],
275        validity: &Mask,
276        decode: &mut dyn FnMut(&mut [MaybeUninit<u8>]) -> VortexResult<usize>,
277    ) -> VortexResult<()>
278    where
279        P: AsPrimitive<usize>,
280        usize: AsPrimitive<O>,
281    {
282        let Some(capacity) = num_bytes.checked_add(slack) else {
283            vortex_bail!("Decoded size overflow: {num_bytes} + {slack}");
284        };
285        // Checked before decoding: an `i32` builder that the decoded bytes would overflow should
286        // not pay for the decompression first.
287        self.check_offset_limit(self.data.len(), num_bytes)?;
288        self.data.reserve(capacity);
289
290        let data_len = self.data.len();
291        let written = decode(self.data.spare_capacity_mut())?;
292        vortex_ensure_eq!(
293            written,
294            num_bytes,
295            "Decoded byte count does not match expected byte count",
296        );
297
298        // The decoded bytes live in spare capacity until `set_len` below, so an invalid `lengths`
299        // still leaves the builder unchanged.
300        self.extend_offsets(num_bytes, validity.len(), prefix_sums(lengths))?;
301
302        // SAFETY: `decode` reported initializing `written` spare bytes, and the caller guarantees
303        // that report is accurate; `written == num_bytes` was checked above.
304        unsafe { self.data.set_len(data_len + num_bytes) };
305        self.append_validity(validity);
306        Ok(())
307    }
308
309    /// Appends `validity.len()` values, taking each valid row's bytes from `value`.
310    ///
311    /// `value` is called once per valid row in ascending row order and the slices it returns must
312    /// total `num_bytes` bytes. Null rows consume no bytes and repeat the preceding offset.
313    ///
314    /// The valid rows are walked a `u64` word at a time rather than pulled one at a time through
315    /// an iterator, and both buffers are sized once up front, so the copy loop costs one offset
316    /// store plus one `memcpy` per value. A caller whose values only exist as a stream can still
317    /// use this by pulling from the stream inside `value`: the rows are visited in ascending
318    /// order.
319    pub fn append_valid_slices<'a, F>(
320        &mut self,
321        num_bytes: usize,
322        validity: &Mask,
323        value: F,
324    ) -> VortexResult<()>
325    where
326        F: FnMut(usize) -> &'a [u8],
327        usize: AsPrimitive<O>,
328    {
329        let data_start = self.data.len();
330        match self.gather_valid_slices(num_bytes, validity, value) {
331            Ok(()) => {
332                self.append_validity(validity);
333                Ok(())
334            }
335            Err(error) => {
336                // The offsets are never committed on failure, so only the copied bytes need to go.
337                self.data.truncate(data_start);
338                Err(error)
339            }
340        }
341    }
342
343    /// Appends a [`VarBinArray`], reusing its offsets instead of walking its values.
344    pub fn append_varbin(
345        &mut self,
346        array: ArrayView<'_, VarBin>,
347        ctx: &mut ExecutionCtx,
348    ) -> VortexResult<()>
349    where
350        usize: AsPrimitive<O>,
351    {
352        let offsets = array.offsets().clone().execute::<PrimitiveArray>(ctx)?;
353        let bytes: ByteBuffer = array.sliced_bytes(ctx);
354        let validity = array
355            .varbin_validity()
356            .execute_mask(array.as_ref().len(), ctx)?;
357        match_each_integer_ptype!(offsets.ptype(), |P| {
358            let offsets = offsets.as_slice::<P>();
359            let first: usize = offsets[0].as_();
360            self.append_values(
361                bytes.as_slice(),
362                // Wrapping keeps a corrupt offsets child from panicking here; `append_values`
363                // rejects the resulting non-monotonic offsets.
364                offsets[1..]
365                    .iter()
366                    .map(|offset| AsPrimitive::<usize>::as_(*offset).wrapping_sub(first)),
367                &validity,
368            )
369        })
370    }
371
372    /// Appends a [`VarBinViewArray`](crate::arrays::VarBinViewArray), compacting its values.
373    pub fn append_varbinview(
374        &mut self,
375        array: ArrayView<'_, VarBinView>,
376        ctx: &mut ExecutionCtx,
377    ) -> VortexResult<()>
378    where
379        usize: AsPrimitive<O>,
380    {
381        let len = array.as_ref().len();
382        let validity = array.varbinview_validity().execute_mask(len, ctx)?;
383
384        // Resolve the views slice and the data buffers once. Reading them per row costs a buffer
385        // handle clone, and the byte total needs only the fixed-width view headers.
386        let views = array.views();
387        let buffers = array
388            .data_buffers()
389            .iter()
390            .map(|buffer| buffer.as_host().as_slice())
391            .collect::<Vec<_>>();
392
393        let num_bytes = match validity.bit_buffer() {
394            AllOr::All => views.iter().map(|view| view.len() as usize).sum(),
395            AllOr::None => 0,
396            AllOr::Some(bits) => {
397                let mut total = 0;
398                bits.for_each_set_index(|index| total += views[index].len() as usize);
399                total
400            }
401        };
402
403        self.append_valid_slices(num_bytes, &validity, |index| views[index].bytes(&buffers))
404    }
405
406    /// Finishes the appended values into a [`VarBinArray`] and resets the builder.
407    pub fn finish_into_varbin(&mut self) -> VarBinArray {
408        assert_eq!(
409            self.offsets.len() - 1,
410            self.validity.len(),
411            "The offset count must be one more than the validity length"
412        );
413
414        let offsets = self.offsets.take();
415        self.offsets.push(O::zero());
416        let offsets = PrimitiveArray::new(offsets.freeze(), Validity::NonNullable);
417        let data = self.data.take();
418        let nulls = self.validity.take().freeze();
419
420        let validity = Validity::from_bit_buffer(nulls, self.dtype.nullability());
421
422        // The builder adds offsets in monotonically increasing order. Store this statistic to
423        // prevent VarBinArray::validate from recomputing it after deserialization.
424        debug_assert!(
425            offsets.as_slice::<O>().is_sorted(),
426            "VarBinBuilder offsets must be sorted"
427        );
428        offsets
429            .statistics()
430            .set(Stat::IsSorted, Precision::Exact(true.into()));
431
432        // SAFETY: The builder maintains all invariants:
433        // - Offsets are monotonically increasing starting from 0 (guaranteed by builder logic).
434        // - Bytes buffer contains exactly the data referenced by offsets.
435        // - Validity matches the dtype nullability.
436        // - UTF-8 validity is ensured by the caller when using DType::Utf8.
437        unsafe {
438            VarBinArray::new_unchecked(
439                offsets.into_array(),
440                data.freeze(),
441                self.dtype.clone(),
442                validity,
443            )
444        }
445    }
446
447    #[inline]
448    fn last_offset(&self) -> O {
449        self.offsets[self.offsets.len() - 1]
450    }
451
452    /// Appends `value`'s bytes and its end offset, leaving the validity bits to the caller.
453    #[inline]
454    fn push_value(&mut self, value: &[u8]) {
455        self.offsets
456            .push(O::from(self.data.len() + value.len()).unwrap_or_else(|| {
457                offset_overflow(self.data.len(), value.len(), std::any::type_name::<O>())
458            }));
459        self.data.extend_from_slice(value);
460    }
461
462    fn append_validity(&mut self, validity: &Mask) {
463        match validity {
464            Mask::AllTrue(len) => self.validity.append_n(true, *len),
465            Mask::AllFalse(len) => self.validity.append_n(false, *len),
466            Mask::Values(values) => self.validity.append_buffer(values.bit_buffer()),
467        }
468    }
469
470    /// Appends `count` end offsets derived from `end_offsets`, shifted past the current data end.
471    ///
472    /// `end_offsets` must be monotonically non-decreasing and end at exactly `num_bytes`. Offsets
473    /// are written through the reserved spare capacity and committed with a single `set_len`, so a
474    /// rejected input leaves the buffer untouched and the caller can propagate the error.
475    fn extend_offsets<P>(
476        &mut self,
477        num_bytes: usize,
478        count: usize,
479        end_offsets: impl Iterator<Item = P>,
480    ) -> VortexResult<()>
481    where
482        P: AsPrimitive<usize>,
483        usize: AsPrimitive<O>,
484    {
485        let data_start = self.data.len();
486        let offsets_len = self.offsets.len();
487        self.check_offset_limit(data_start, num_bytes)?;
488        self.offsets.reserve(count);
489
490        // Writing into the spare capacity keeps the output cursor in a register: `push` rewrites
491        // the buffer length on every value, which the optimizer cannot hoist out of the loop.
492        let spare = &mut self.offsets.spare_capacity_mut()[..count];
493        let mut end_offsets = end_offsets;
494        let mut previous = 0usize;
495        for slot in spare.iter_mut() {
496            let Some(end) = end_offsets.next() else {
497                vortex_bail!("End offset count is less than the validity length {count}");
498            };
499            let end = end.as_();
500            vortex_ensure!(
501                end >= previous && end <= num_bytes,
502                "End offsets must be monotonically increasing within {num_bytes} bytes, \
503                 got {end} after {previous}"
504            );
505            slot.write((data_start + end).as_());
506            previous = end;
507        }
508        vortex_ensure!(
509            end_offsets.next().is_none(),
510            "End offset count exceeds the validity length {count}"
511        );
512        vortex_ensure_eq!(
513            previous,
514            num_bytes,
515            "Final end offset does not match the value byte count",
516        );
517
518        // SAFETY: the loop initialized the first `count` spare slots.
519        unsafe { self.offsets.set_len(offsets_len + count) };
520        Ok(())
521    }
522
523    /// Copies each valid row's bytes from `value` into the byte storage and records the offsets.
524    /// See [`append_valid_slices`](Self::append_valid_slices); the validity bits are the caller's
525    /// job so that a failure here can be unwound.
526    fn gather_valid_slices<'a, F>(
527        &mut self,
528        num_bytes: usize,
529        validity: &Mask,
530        mut value: F,
531    ) -> VortexResult<()>
532    where
533        F: FnMut(usize) -> &'a [u8],
534        usize: AsPrimitive<O>,
535    {
536        let count = validity.len();
537        let data_start = self.data.len();
538        let offsets_len = self.offsets.len();
539        self.check_offset_limit(data_start, num_bytes)?;
540        self.offsets.reserve(count);
541        self.data.reserve(num_bytes);
542
543        // Disjoint field borrows: the offsets spare capacity stays valid while the byte buffer
544        // grows, since the two are separate allocations.
545        let Self { offsets, data, .. } = self;
546        let spare = &mut offsets.spare_capacity_mut()[..count];
547
548        match validity.bit_buffer() {
549            AllOr::All => {
550                for (row, slot) in spare.iter_mut().enumerate() {
551                    data.extend_from_slice(value(row));
552                    slot.write(data.len().as_());
553                }
554            }
555            AllOr::None => {
556                spare.fill(MaybeUninit::new(data_start.as_()));
557            }
558            AllOr::Some(bits) => {
559                let mut row = 0;
560                bits.for_each_set_index(|index| {
561                    // Null rows between the previous valid row and this one repeat its end offset.
562                    spare[row..index].fill(MaybeUninit::new(data.len().as_()));
563                    data.extend_from_slice(value(index));
564                    spare[index].write(data.len().as_());
565                    row = index + 1;
566                });
567                spare[row..].fill(MaybeUninit::new(data.len().as_()));
568            }
569        }
570
571        // A caller whose slices overrun `num_bytes` only grows the byte buffer past the reservation,
572        // so the overrun is caught here rather than per value. The offsets are still uncommitted, so
573        // rejecting it now leaves them untouched.
574        vortex_ensure_eq!(
575            data.len(),
576            data_start + num_bytes,
577            "Value slices byte count does not match expected byte count",
578        );
579
580        // SAFETY: every branch above initialized all `count` spare slots.
581        unsafe { self.offsets.set_len(offsets_len + count) };
582        Ok(())
583    }
584
585    /// Checks that an offset past `num_bytes` more bytes is representable as an `O`.
586    fn check_offset_limit(&self, data_start: usize, num_bytes: usize) -> VortexResult<()> {
587        let Some(limit) = data_start.checked_add(num_bytes) else {
588            vortex_bail!("Byte offset overflow: {data_start} + {num_bytes}");
589        };
590        vortex_ensure!(
591            u64::try_from(limit).is_ok_and(|limit| limit <= O::max_value_as_u64()),
592            "Byte offset {limit} does not fit in {}",
593            std::any::type_name::<O>()
594        );
595        Ok(())
596    }
597}
598
599impl<O: OffsetBuilderPType> ArrayBuilder for VarBinBuilder<O> {
600    fn as_any(&self) -> &dyn Any {
601        self
602    }
603
604    fn as_any_mut(&mut self) -> &mut dyn Any {
605        self
606    }
607
608    fn dtype(&self) -> &DType {
609        &self.dtype
610    }
611
612    fn len(&self) -> usize {
613        self.validity.len()
614    }
615
616    fn append_zeros(&mut self, n: usize) {
617        self.offsets.push_n(self.last_offset(), n);
618        self.validity.append_n(true, n);
619    }
620
621    unsafe fn append_nulls_unchecked(&mut self, n: usize) {
622        self.push_nulls(n);
623    }
624
625    fn append_scalar(&mut self, scalar: &Scalar) -> VortexResult<()> {
626        self.append_scalar_repeated(scalar, 1)
627    }
628
629    fn reserve_exact(&mut self, additional: usize) {
630        self.offsets.reserve(additional);
631        self.validity.reserve(additional);
632    }
633
634    fn finish(&mut self) -> ArrayRef {
635        self.finish_into_varbin().into_array()
636    }
637
638    fn finish_into_canonical(&mut self, ctx: &mut ExecutionCtx) -> Canonical {
639        self.finish()
640            .execute::<Canonical>(ctx)
641            .vortex_expect("varbin builder should canonicalize")
642    }
643}
644
645/// Recovers a concrete [`VarBinBuilder`] from a `&mut dyn ArrayBuilder`.
646///
647/// Evaluates to `Some($body)` with `$typed` bound to the `&mut VarBinBuilder<O>` when the builder
648/// is one, and `None` otherwise, so an encoding can fall through to its other output paths:
649///
650/// ```ignore
651/// if let Some(result) = match_each_varbin_builder!(builder, |builder| {
652///     append_my_encoding(array, builder, ctx)
653/// }) {
654///     return result;
655/// }
656/// ```
657#[macro_export]
658macro_rules! match_each_varbin_builder {
659    ($builder:expr, | $typed:ident | $body:expr) => {
660        $crate::__match_varbin_builder_widths!($builder, |$typed| $body, [u32, u64, i32, i64])
661    };
662}
663
664/// Expands `$body` once per listed offset width, guarded by a downcast. See
665/// [`match_each_varbin_builder!`].
666#[doc(hidden)]
667#[macro_export]
668macro_rules! __match_varbin_builder_widths {
669    ($builder:expr, | $typed:ident | $body:expr, [$($width:ty),+ $(,)?]) => {{
670        let __varbin_builder: &mut dyn $crate::builders::ArrayBuilder = $builder;
671        $crate::__match_varbin_builder_arms!(__varbin_builder, |$typed| $body, [$($width),+])
672    }};
673}
674
675/// The `if`/`else if` chain behind [`__match_varbin_builder_widths!`], one arm per width.
676#[doc(hidden)]
677#[macro_export]
678macro_rules! __match_varbin_builder_arms {
679    ($builder:expr, | $typed:ident | $body:expr, []) => {
680        None
681    };
682    ($builder:expr, | $typed:ident | $body:expr, [$head:ty $(, $tail:ty)*]) => {
683        if $builder
684            .as_any()
685            .is::<$crate::builders::VarBinBuilder<$head>>()
686        {
687            let $typed = match $builder
688                .as_any_mut()
689                .downcast_mut::<$crate::builders::VarBinBuilder<$head>>()
690            {
691                Some(typed) => typed,
692                None => unreachable!("builder type checked above"),
693            };
694            Some($body)
695        } else {
696            $crate::__match_varbin_builder_arms!($builder, |$typed| $body, [$($tail),*])
697        }
698    };
699}
700
701#[cold]
702#[inline(never)]
703fn offset_overflow(data_len: usize, value_len: usize, offset_type: &'static str) -> ! {
704    vortex_panic!(
705        "Failed to convert sum of {data_len} and {value_len} to offset of type {offset_type}"
706    )
707}
708
709/// Running totals of `lengths`, wrapping so a corrupt lengths child is rejected rather than
710/// panicking; [`VarBinBuilder::extend_offsets`] catches the resulting non-monotonic offsets.
711#[inline]
712fn prefix_sums<P: AsPrimitive<usize>>(lengths: &[P]) -> impl Iterator<Item = usize> {
713    lengths.iter().scan(0usize, |end, length| {
714        *end = end.wrapping_add(length.as_());
715        Some(*end)
716    })
717}
718
719#[cfg(test)]
720mod tests {
721    use std::mem::MaybeUninit;
722    use std::sync::LazyLock;
723
724    use rstest::rstest;
725    use vortex_error::VortexResult;
726    use vortex_mask::Mask;
727    use vortex_session::VortexSession;
728
729    use crate::IntoArray;
730    use crate::VortexSessionExecute;
731    use crate::arrays::ConstantArray;
732    use crate::arrays::VarBinArray;
733    use crate::arrays::VarBinViewArray;
734    use crate::arrays::varbin::VarBinArraySlotsExt;
735    use crate::arrays::varbin::builder::VarBinBuilder;
736    use crate::assert_arrays_eq;
737    use crate::builders::ArrayBuilder;
738    use crate::dtype::DType;
739    use crate::dtype::Nullability::Nullable;
740    use crate::expr::stats::Precision;
741    use crate::expr::stats::Stat;
742    use crate::expr::stats::StatsProviderExt;
743    use crate::scalar::Scalar;
744
745    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
746
747    #[test]
748    fn test_builder() {
749        let mut builder = VarBinBuilder::<i32>::with_capacity_in(
750            DType::Utf8(Nullable),
751            0,
752            vortex_buffer::BufferAllocatorRef::static_ref(),
753        );
754        builder.append(Some(b"hello"));
755        builder.append(None);
756        builder.append(Some(b"world"));
757        let array = builder.finish_into_varbin();
758
759        assert_eq!(array.len(), 3);
760        assert_eq!(array.dtype().nullability(), Nullable);
761        assert_eq!(
762            array
763                .execute_scalar(0, &mut SESSION.create_execution_ctx())
764                .unwrap(),
765            Scalar::utf8("hello".to_string(), Nullable)
766        );
767        assert!(
768            array
769                .execute_scalar(1, &mut SESSION.create_execution_ctx())
770                .unwrap()
771                .is_null()
772        );
773        assert_arrays_eq!(
774            array,
775            VarBinViewArray::from_iter_nullable_str([Some("hello"), None, Some("world")]),
776            &mut SESSION.create_execution_ctx()
777        );
778    }
779
780    #[rstest]
781    #[case(false)]
782    #[case(true)]
783    fn test_append_varbin_to_builder(#[case] large_offsets: bool) -> VortexResult<()> {
784        let source = VarBinArray::from_iter(
785            [
786                Some("prefix"),
787                Some("hello"),
788                None,
789                Some("world"),
790                Some("suffix"),
791            ],
792            DType::Utf8(Nullable),
793        )
794        .into_array()
795        .slice(1..4)?;
796        let mut ctx = SESSION.create_execution_ctx();
797
798        let actual = with_offsets(large_offsets, source.dtype().clone(), |builder| {
799            source.append_to_builder(builder, &mut ctx)
800        })?;
801
802        assert_arrays_eq!(
803            actual,
804            VarBinViewArray::from_iter_nullable_str([Some("hello"), None, Some("world")]),
805            &mut ctx
806        );
807        Ok(())
808    }
809
810    #[test]
811    fn append_n_values_offset_overflow_returns_error() {
812        let mut builder = VarBinBuilder::<i32>::new_in(
813            DType::Utf8(Nullable),
814            vortex_buffer::BufferAllocatorRef::static_ref(),
815        );
816
817        // The limit is checked before anything is reserved, so the huge byte total is free.
818        let result = builder.append_n_values(b"hello", i32::MAX as usize / 5 + 1);
819
820        assert!(result.is_err());
821        assert_eq!(builder.offsets.len(), 1);
822        assert!(builder.data.is_empty());
823        assert_eq!(builder.validity.len(), 0);
824    }
825
826    #[test]
827    fn append_values_rejects_a_short_offset_count() {
828        let mut builder = VarBinBuilder::<i32>::new_in(
829            DType::Utf8(Nullable),
830            vortex_buffer::BufferAllocatorRef::static_ref(),
831        );
832
833        let result = builder.append_values(b"ab", [1usize, 2].into_iter(), &Mask::new_true(3));
834
835        assert!(result.is_err());
836        assert_eq!(builder.offsets.len(), 1);
837        assert!(builder.data.is_empty());
838    }
839
840    #[test]
841    fn append_values_rejects_non_monotonic_offsets() {
842        let mut builder = VarBinBuilder::<i32>::new_in(
843            DType::Utf8(Nullable),
844            vortex_buffer::BufferAllocatorRef::static_ref(),
845        );
846
847        let result = builder.append_values(b"ab", [2usize, 1].into_iter(), &Mask::new_true(2));
848
849        assert!(result.is_err());
850        assert_eq!(builder.offsets.len(), 1);
851    }
852
853    #[test]
854    fn append_decoded_writes_into_the_builder_storage() -> VortexResult<()> {
855        let mut ctx = SESSION.create_execution_ctx();
856        let mut builder = VarBinBuilder::<i32>::new_in(
857            DType::Utf8(Nullable),
858            vortex_buffer::BufferAllocatorRef::static_ref(),
859        );
860
861        // SAFETY: the closure initializes exactly the 6 bytes it reports.
862        unsafe {
863            builder.append_decoded(
864                6,
865                4,
866                &[3usize, 0, 3],
867                &Mask::from_iter([true, false, true]),
868                &mut |spare: &mut [MaybeUninit<u8>]| {
869                    for (slot, byte) in spare.iter_mut().zip(b"foobar") {
870                        slot.write(*byte);
871                    }
872                    Ok(6)
873                },
874            )?;
875        }
876
877        let expected =
878            VarBinViewArray::from_iter([Some("foo"), None, Some("bar")], DType::Utf8(Nullable));
879        assert_arrays_eq!(builder.finish_into_varbin(), expected, &mut ctx);
880        Ok(())
881    }
882
883    /// The offset width has to be checked before `decode` runs: an overflowing `i32` builder
884    /// should not pay for a full decompression first.
885    #[test]
886    fn append_decoded_rejects_an_offset_overflow_without_decoding() {
887        let mut builder = VarBinBuilder::<i32>::new_in(
888            DType::Utf8(Nullable),
889            vortex_buffer::BufferAllocatorRef::static_ref(),
890        );
891        let num_bytes = i32::MAX as usize + 1;
892        let mut decoded = false;
893
894        // SAFETY: the closure is never called, and reports only what it initializes if it were.
895        let result = unsafe {
896            builder.append_decoded(num_bytes, 0, &[num_bytes], &Mask::new_true(1), &mut |_| {
897                decoded = true;
898                Ok(0)
899            })
900        };
901
902        assert!(result.is_err());
903        assert!(!decoded, "decode ran before the offset width was checked");
904        assert_eq!(builder.offsets.len(), 1);
905        assert_eq!(builder.validity.len(), 0);
906    }
907
908    /// `append_scalar_repeated` reports an offset overflow rather than panicking, so a constant
909    /// column wider than the offset type errors like the bulk appends do.
910    #[test]
911    fn append_scalar_repeated_rejects_an_offset_overflow() {
912        let mut builder = VarBinBuilder::<i32>::new_in(
913            DType::Utf8(Nullable),
914            vortex_buffer::BufferAllocatorRef::static_ref(),
915        );
916
917        let result = builder
918            .append_scalar_repeated(&Scalar::utf8("hello", Nullable), i32::MAX as usize / 5 + 1);
919
920        assert!(result.is_err());
921        assert_eq!(builder.offsets.len(), 1);
922        assert!(builder.data.is_empty());
923        assert_eq!(builder.validity.len(), 0);
924    }
925
926    #[test]
927    fn append_decoded_rejects_a_short_decode() {
928        let mut builder = VarBinBuilder::<i32>::new_in(
929            DType::Utf8(Nullable),
930            vortex_buffer::BufferAllocatorRef::static_ref(),
931        );
932
933        // SAFETY: the closure initializes the 3 bytes it reports (none, and it reports 3 — but the
934        // length mismatch is rejected before anything is published).
935        let result = unsafe {
936            builder.append_decoded(6, 0, &[3usize, 3], &Mask::new_true(2), &mut |spare| {
937                spare[..3].fill(MaybeUninit::new(b'x'));
938                Ok(3)
939            })
940        };
941
942        assert!(result.is_err());
943        assert_eq!(builder.offsets.len(), 1);
944        assert_eq!(builder.validity.len(), 0);
945    }
946
947    /// Slices that overrun the declared byte count are rejected, and the builder is left exactly
948    /// as it was — the overrun bytes are copied before the total can be checked, so the unwind has
949    /// to put them back.
950    #[rstest]
951    #[case::all_valid(Mask::new_true(2))]
952    #[case::some_valid(Mask::from_iter([true, false, true]))]
953    fn append_valid_slices_rejects_a_byte_count_mismatch(#[case] validity: Mask) {
954        let mut builder = VarBinBuilder::<i32>::new_in(
955            DType::Utf8(Nullable),
956            vortex_buffer::BufferAllocatorRef::static_ref(),
957        );
958        let values = [b"foo".as_slice(), b"quux".as_slice()];
959
960        let mut next = 0;
961        let result = builder.append_valid_slices(6, &validity, |_| {
962            next += 1;
963            values[next - 1]
964        });
965
966        assert!(result.is_err());
967        assert_eq!(builder.offsets.len(), 1);
968        assert!(builder.data.is_empty());
969        assert_eq!(builder.validity.len(), 0);
970    }
971
972    #[test]
973    #[should_panic(expected = "The offset count must be one more than the validity length")]
974    fn finish_rejects_mismatched_validity() {
975        let mut builder = VarBinBuilder::<i32>::new_in(
976            DType::Utf8(Nullable),
977            vortex_buffer::BufferAllocatorRef::static_ref(),
978        );
979        builder.validity.append_true();
980        drop(builder.finish_into_varbin());
981    }
982
983    #[rstest]
984    #[case(false)]
985    #[case(true)]
986    fn test_array_builder_methods(#[case] large_offsets: bool) -> VortexResult<()> {
987        let mut ctx = SESSION.create_execution_ctx();
988        let result = with_offsets(large_offsets, DType::Utf8(Nullable), |builder| {
989            builder.reserve_exact(3);
990            builder.append_zero();
991            builder.append_scalar(&Scalar::utf8("hello", Nullable))?;
992            builder.append_null();
993            assert_eq!(builder.len(), 3);
994            Ok(())
995        })?;
996
997        assert_eq!(
998            result.validity()?.execute_mask(3, &mut ctx)?,
999            Mask::from_iter([true, true, false])
1000        );
1001        assert_arrays_eq!(
1002            result,
1003            VarBinViewArray::from_iter_nullable_str([Some(""), Some("hello"), None]),
1004            &mut ctx
1005        );
1006        Ok(())
1007    }
1008
1009    #[rstest]
1010    #[case(false)]
1011    #[case(true)]
1012    fn test_append_varbinview_validity_to_builder(#[case] large_offsets: bool) -> VortexResult<()> {
1013        let long = "a value that does not fit inline";
1014        let all_null = VarBinViewArray::from_iter([None::<&str>, None], DType::Utf8(Nullable));
1015        let mixed =
1016            VarBinViewArray::from_iter([Some("hello"), None, Some(long)], DType::Utf8(Nullable));
1017        let expected = VarBinViewArray::from_iter(
1018            [None, None, Some("hello"), None, Some(long)],
1019            DType::Utf8(Nullable),
1020        );
1021        let mut ctx = SESSION.create_execution_ctx();
1022
1023        let actual = with_offsets(large_offsets, expected.dtype().clone(), |builder| {
1024            all_null
1025                .clone()
1026                .into_array()
1027                .append_to_builder(builder, &mut ctx)?;
1028            mixed
1029                .clone()
1030                .into_array()
1031                .append_to_builder(builder, &mut ctx)
1032        })?;
1033
1034        assert_arrays_eq!(actual, expected, &mut ctx);
1035        Ok(())
1036    }
1037
1038    /// `match_each_varbin_builder!` covers every offset width a `VarBinBuilder` can be built with,
1039    /// so both canonical appends must reach their specialization for all of them. A macro that
1040    /// only matched the signed pair would send an unsigned builder down a downcast that assumes
1041    /// `VarBinViewBuilder` and panic.
1042    #[rstest]
1043    #[case::u32(VarBinBuilder::<u32>::new_in(DType::Utf8(Nullable), vortex_buffer::BufferAllocatorRef::static_ref()))]
1044    #[case::u64(VarBinBuilder::<u64>::new_in(DType::Utf8(Nullable), vortex_buffer::BufferAllocatorRef::static_ref()))]
1045    #[case::i32(VarBinBuilder::<i32>::new_in(DType::Utf8(Nullable), vortex_buffer::BufferAllocatorRef::static_ref()))]
1046    #[case::i64(VarBinBuilder::<i64>::new_in(DType::Utf8(Nullable), vortex_buffer::BufferAllocatorRef::static_ref()))]
1047    fn append_to_every_offset_width(#[case] mut builder: impl ArrayBuilder) -> VortexResult<()> {
1048        let mut ctx = SESSION.create_execution_ctx();
1049        let long = "a string that is far too long to be inlined in a view";
1050        let values = [Some("hello"), None, Some(long), Some("")];
1051
1052        let view = VarBinViewArray::from_iter(values, DType::Utf8(Nullable)).into_array();
1053        let varbin = VarBinArray::from_iter(values, DType::Utf8(Nullable)).into_array();
1054        let constant = ConstantArray::new(Scalar::from("hello").into_nullable(), 2).into_array();
1055
1056        for chunk in [&view, &varbin, &constant] {
1057            chunk.append_to_builder(&mut builder, &mut ctx)?;
1058        }
1059
1060        let expected = VarBinViewArray::from_iter_nullable_str([
1061            Some("hello"),
1062            None,
1063            Some(long),
1064            Some(""),
1065            Some("hello"),
1066            None,
1067            Some(long),
1068            Some(""),
1069            Some("hello"),
1070            Some("hello"),
1071        ]);
1072        assert_arrays_eq!(builder.finish(), expected, &mut ctx);
1073        Ok(())
1074    }
1075
1076    #[test]
1077    fn offsets_have_is_sorted_stat() -> VortexResult<()> {
1078        let mut builder = VarBinBuilder::<i32>::with_capacity_in(
1079            DType::Utf8(Nullable),
1080            0,
1081            vortex_buffer::BufferAllocatorRef::static_ref(),
1082        );
1083        builder.append_value(b"aaa");
1084        builder.push_null();
1085        builder.append_value(b"bbb");
1086        let array = builder.finish_into_varbin();
1087
1088        let is_sorted = array
1089            .offsets()
1090            .statistics()
1091            .with_typed_stats_set(|s| s.get_as::<bool>(Stat::IsSorted));
1092        assert_eq!(is_sorted, Precision::Exact(true));
1093        Ok(())
1094    }
1095
1096    #[test]
1097    fn empty_builder_offsets_have_is_sorted_stat() -> VortexResult<()> {
1098        let mut builder = VarBinBuilder::<i32>::new_in(
1099            DType::Utf8(Nullable),
1100            vortex_buffer::BufferAllocatorRef::static_ref(),
1101        );
1102        let array = builder.finish_into_varbin();
1103
1104        let is_sorted = array
1105            .offsets()
1106            .statistics()
1107            .with_typed_stats_set(|s| s.get_as::<bool>(Stat::IsSorted));
1108        assert_eq!(is_sorted, Precision::Exact(true));
1109        Ok(())
1110    }
1111
1112    /// Runs `f` against an `i32` or `i64` builder and returns the finished array.
1113    fn with_offsets(
1114        large_offsets: bool,
1115        dtype: DType,
1116        f: impl FnOnce(&mut dyn ArrayBuilder) -> VortexResult<()>,
1117    ) -> VortexResult<VarBinArray> {
1118        if large_offsets {
1119            let mut builder = VarBinBuilder::<i64>::with_capacity_in(
1120                dtype,
1121                8,
1122                vortex_buffer::BufferAllocatorRef::static_ref(),
1123            );
1124            f(&mut builder)?;
1125            Ok(builder.finish_into_varbin())
1126        } else {
1127            let mut builder = VarBinBuilder::<i32>::with_capacity_in(
1128                dtype,
1129                8,
1130                vortex_buffer::BufferAllocatorRef::static_ref(),
1131            );
1132            f(&mut builder)?;
1133            Ok(builder.finish_into_varbin())
1134        }
1135    }
1136}