Skip to main content

vortex_array/arrays/bool/
array.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Display;
5use std::fmt::Formatter;
6
7use smallvec::smallvec;
8use vortex_buffer::BitBuffer;
9use vortex_buffer::BitBufferMeta;
10use vortex_buffer::BitBufferMut;
11use vortex_buffer::BitBufferView;
12use vortex_error::VortexExpect;
13use vortex_error::VortexResult;
14use vortex_error::vortex_ensure;
15use vortex_error::vortex_ensure_eq;
16use vortex_mask::Mask;
17
18use crate::ArrayRef;
19use crate::ArraySlots;
20use crate::ExecutionCtx;
21use crate::IntoArray;
22use crate::array::Array;
23use crate::array::ArrayParts;
24use crate::array::TypedArrayRef;
25use crate::array::child_to_validity;
26use crate::array::validity_to_child;
27use crate::array_slots;
28use crate::arrays::Bool;
29use crate::arrays::BoolArray;
30use crate::buffer::BufferHandle;
31use crate::dtype::DType;
32use crate::validity::Validity;
33
34#[array_slots(Bool)]
35pub struct BoolSlots {
36    /// The validity bitmap indicating which elements are non-null.
37    #[slot(0)]
38    pub validity: Option<ArrayRef>,
39}
40
41/// Inner data for a boolean array that stores true/false values in a compact bit-packed format.
42///
43/// This mirrors the Apache Arrow Boolean array encoding, where each boolean value
44/// is stored as a single bit rather than a full byte.
45///
46/// The data layout uses:
47/// - A bit-packed buffer where each bit represents one boolean value (0 = false, 1 = true)
48/// - An optional validity child array, which must be of type `Bool(NonNullable)`, where true values
49///   indicate valid and false indicates null. if the i-th value is null in the validity child,
50///   the i-th packed bit in the buffer may be 0 or 1, i.e. it is undefined.
51/// - Bit-level slicing is supported with minimal overhead
52///
53/// # Examples
54///
55/// ```
56/// # fn main() -> vortex_error::VortexResult<()> {
57/// use vortex_array::arrays::BoolArray;
58/// use vortex_array::{IntoArray, VortexSessionExecute};
59/// use vortex_session::VortexSession;
60///
61/// // Create from iterator using FromIterator impl
62/// let array: BoolArray = [true, false, true, false].into_iter().collect();
63///
64/// // Slice the array
65/// let sliced = array.slice(1..3)?;
66/// assert_eq!(sliced.len(), 2);
67///
68/// // Access individual values
69/// let mut ctx = VortexSession::empty().create_execution_ctx();
70/// let value = array.execute_scalar(0, &mut ctx).unwrap();
71/// assert_eq!(value, true.into());
72/// # Ok(())
73/// # }
74/// ```
75#[derive(Clone, Debug)]
76pub struct BoolData {
77    pub(super) bits: BufferHandle,
78    pub(super) meta: BitBufferMeta,
79}
80
81impl Display for BoolData {
82    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
83        write!(f, "offset: {}", self.meta.offset())
84    }
85}
86
87pub struct BoolDataParts {
88    pub bits: BufferHandle,
89    pub meta: BitBufferMeta,
90}
91
92pub trait BoolArrayExt: TypedArrayRef<Bool> {
93    fn nullability(&self) -> crate::dtype::Nullability {
94        match self.dtype() {
95            DType::Bool(nullability) => *nullability,
96            _ => unreachable!("BoolArrayExt requires a bool dtype"),
97        }
98    }
99
100    fn validity(&self) -> Validity {
101        child_to_validity(
102            self.slots()[BoolSlots::VALIDITY].as_ref(),
103            self.nullability(),
104        )
105    }
106
107    fn to_bit_buffer(&self) -> BitBuffer {
108        let buffer = self.bits.as_host().clone();
109        BitBuffer::new_with_offset(buffer, self.meta.len(), self.meta.offset())
110    }
111
112    /// Borrow the array's packed bits as a [`BitBufferView`] without cloning the backing buffer.
113    fn bit_buffer_view(&self) -> BitBufferView<'_> {
114        BitBufferView::from_meta(self.bits.as_host().as_slice(), self.meta)
115    }
116
117    fn maybe_execute_mask(&self, ctx: &mut ExecutionCtx) -> VortexResult<Option<Mask>> {
118        let all_valid = match &BoolArrayExt::validity(self) {
119            Validity::NonNullable | Validity::AllValid => true,
120            Validity::AllInvalid => false,
121            Validity::Array(a) => a.statistics().compute_min::<bool>(ctx).unwrap_or(false),
122        };
123        Ok(all_valid.then(|| Mask::from_buffer(self.to_bit_buffer())))
124    }
125
126    fn execute_mask(&self, ctx: &mut ExecutionCtx) -> Mask {
127        self.maybe_execute_mask(ctx)
128            .vortex_expect("failed to check validity")
129            .vortex_expect("cannot convert nullable boolean array to mask")
130    }
131
132    fn to_mask_fill_null_false(&self, ctx: &mut ExecutionCtx) -> Mask {
133        let validity_mask = BoolArrayExt::validity(self)
134            .execute_mask(self.len(), ctx)
135            .vortex_expect("Failed to compute validity mask");
136        let buffer = match validity_mask {
137            Mask::AllTrue(_) => self.to_bit_buffer(),
138            Mask::AllFalse(_) => return Mask::new_false(self.len()),
139            Mask::Values(validity) => validity.bit_buffer() & self.to_bit_buffer(),
140        };
141        Mask::from_buffer(buffer)
142    }
143}
144impl<T: TypedArrayRef<Bool>> BoolArrayExt for T {}
145
146/// Field accessors and non-consuming methods on the inner bool data.
147impl BoolData {
148    /// Splits into owned parts
149    #[inline]
150    pub fn into_parts(self, len: usize) -> BoolDataParts {
151        BoolDataParts {
152            bits: self.bits,
153            meta: BitBufferMeta::new(self.meta.offset(), len),
154        }
155    }
156
157    pub(crate) fn make_slots(validity: &Validity, len: usize) -> ArraySlots {
158        smallvec![validity_to_child(validity, len)]
159    }
160}
161
162/// Constructors and consuming methods for [`BoolArray`].
163impl Array<Bool> {
164    /// Constructs a new [`BoolArray`].
165    ///
166    /// # Panics
167    ///
168    /// Panics if the validity length is not equal to the bit buffer length.
169    pub fn new(bits: BitBuffer, validity: Validity) -> Self {
170        Self::try_new(bits, validity).vortex_expect("Failed to create BoolArray")
171    }
172
173    /// Constructs a new [`BoolArray`] from a [`BufferHandle`].
174    ///
175    /// # Panics
176    ///
177    /// Panics if the validity length is not equal to the bit buffer length.
178    pub fn new_handle(handle: BufferHandle, offset: usize, len: usize, validity: Validity) -> Self {
179        Self::try_new_from_handle(handle, offset, len, validity)
180            .vortex_expect("Failed to create BoolArray from BufferHandle")
181    }
182
183    /// Constructs a new `BoolArray`.
184    ///
185    /// # Errors
186    ///
187    /// Returns an error if the provided components do not satisfy the invariants.
188    pub fn try_new(bits: BitBuffer, validity: Validity) -> VortexResult<Self> {
189        let dtype = DType::Bool(validity.nullability());
190        let len = bits.len();
191        let slots = BoolData::make_slots(&validity, len);
192        let data = BoolData::try_new(bits, validity)?;
193        Ok(unsafe { Array::from_parts_unchecked(ArrayParts::new(Bool, dtype, len, data, slots)) })
194    }
195
196    /// Build a new bool array from a `BufferHandle`, returning an error if the offset is
197    /// too large or the buffer is not large enough to hold the values.
198    pub fn try_new_from_handle(
199        bits: BufferHandle,
200        offset: usize,
201        len: usize,
202        validity: Validity,
203    ) -> VortexResult<Self> {
204        let dtype = DType::Bool(validity.nullability());
205        let slots = BoolData::make_slots(&validity, len);
206        let data = BoolData::try_new_from_handle(bits, offset, len, validity)?;
207        Ok(unsafe { Array::from_parts_unchecked(ArrayParts::new(Bool, dtype, len, data, slots)) })
208    }
209
210    /// Creates a new [`BoolArray`] without validation.
211    ///
212    /// # Safety
213    ///
214    /// The caller must ensure that the validity length is equal to the bit buffer length.
215    pub unsafe fn new_unchecked(bits: BitBuffer, validity: Validity) -> Self {
216        let dtype = DType::Bool(validity.nullability());
217        let len = bits.len();
218        let slots = BoolData::make_slots(&validity, len);
219        // SAFETY: caller guarantees validity length equals bit buffer length.
220        let data = unsafe { BoolData::new_unchecked(bits, validity) };
221        unsafe { Array::from_parts_unchecked(ArrayParts::new(Bool, dtype, len, data, slots)) }
222    }
223
224    /// Validates the components that would be used to create a [`BoolArray`].
225    pub fn validate(bits: &BitBuffer, validity: &Validity) -> VortexResult<()> {
226        BoolData::validate(bits, validity)
227    }
228
229    /// Create a new BoolArray from a set of indices and a length.
230    ///
231    /// All indices must be less than the length.
232    pub fn from_indices<I: IntoIterator<Item = usize>>(
233        length: usize,
234        indices: I,
235        validity: Validity,
236    ) -> Self {
237        let mut buffer = BitBufferMut::new_unset(length);
238        indices.into_iter().for_each(|idx| buffer.set(idx));
239        Self::new(buffer.freeze(), validity)
240    }
241
242    /// Returns the underlying [`BitBuffer`] of the array, consuming self.
243    pub fn into_bit_buffer(self) -> BitBuffer {
244        let len = self.len();
245        let data = self.into_data();
246        let buffer = data.bits.unwrap_host();
247        BitBuffer::new_with_offset(buffer, len, data.meta.offset())
248    }
249}
250
251// Internal constructors on BoolData (used by [`BoolArray`] constructors and [`VTable::build`]).
252impl BoolData {
253    pub(super) fn try_new(bits: BitBuffer, validity: Validity) -> VortexResult<Self> {
254        let bits = bits.shrink_offset();
255        Self::validate(&bits, &validity)?;
256
257        let (offset, len, buffer) = bits.into_inner();
258
259        Ok(Self {
260            bits: BufferHandle::new_host(buffer),
261            meta: BitBufferMeta::new(offset, len),
262        })
263    }
264
265    pub(super) fn try_new_from_handle(
266        bits: BufferHandle,
267        offset: usize,
268        len: usize,
269        validity: Validity,
270    ) -> VortexResult<Self> {
271        vortex_ensure!(offset < 8, "BitBuffer offset must be <8, got {}", offset);
272        if let Some(validity_len) = validity.maybe_len() {
273            vortex_ensure_eq!(
274                validity_len,
275                len,
276                "BoolArray validity length does not match array length",
277            );
278        }
279
280        vortex_ensure!(
281            bits.len() * 8 >= (len + offset),
282            "provided BufferHandle with offset {offset} len {len} had size {} bits",
283            bits.len() * 8,
284        );
285
286        Ok(Self {
287            bits,
288            meta: BitBufferMeta::new(offset, len),
289        })
290    }
291
292    pub(super) unsafe fn new_unchecked(bits: BitBuffer, validity: Validity) -> Self {
293        if cfg!(debug_assertions) {
294            Self::try_new(bits, validity).vortex_expect("Failed to create BoolData")
295        } else {
296            let (offset, len, buffer) = bits.into_inner();
297
298            Self {
299                bits: BufferHandle::new_host(buffer),
300                meta: BitBufferMeta::new(offset, len),
301            }
302        }
303    }
304
305    pub(super) fn validate(bits: &BitBuffer, validity: &Validity) -> VortexResult<()> {
306        vortex_ensure!(
307            bits.offset() < 8,
308            "BitBuffer offset must be <8, got {}",
309            bits.offset()
310        );
311
312        if let Some(validity_len) = validity.maybe_len() {
313            vortex_ensure_eq!(
314                validity_len,
315                bits.len(),
316                "BoolArray validity length does not match array length",
317            );
318        }
319
320        Ok(())
321    }
322}
323
324impl From<BitBuffer> for BoolArray {
325    fn from(value: BitBuffer) -> Self {
326        BoolArray::new(value, Validity::NonNullable)
327    }
328}
329
330impl FromIterator<bool> for BoolArray {
331    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
332        BoolArray::from(BitBuffer::from_iter(iter))
333    }
334}
335
336impl FromIterator<Option<bool>> for BoolArray {
337    fn from_iter<I: IntoIterator<Item = Option<bool>>>(iter: I) -> Self {
338        let iter = iter.into_iter();
339        let capacity = iter.size_hint().0;
340        let mut bits = BitBufferMut::with_capacity(capacity);
341        let mut validity = BitBufferMut::with_capacity(capacity);
342        for value in iter {
343            bits.append(value.unwrap_or_default());
344            validity.append(value.is_some());
345        }
346
347        BoolArray::new(bits.freeze(), Validity::from(validity.freeze()))
348    }
349}
350
351impl IntoArray for BitBuffer {
352    fn into_array(self) -> ArrayRef {
353        BoolArray::new(self, Validity::NonNullable).into_array()
354    }
355}
356
357impl IntoArray for BitBufferMut {
358    fn into_array(self) -> ArrayRef {
359        self.freeze().into_array()
360    }
361}
362
363#[cfg(test)]
364mod tests {
365    use std::iter::once;
366    use std::iter::repeat_n;
367    use std::sync::LazyLock;
368
369    use vortex_buffer::Alignment;
370    use vortex_buffer::BitBuffer;
371    use vortex_buffer::BitBufferMut;
372    use vortex_buffer::ByteBuffer;
373    use vortex_buffer::buffer;
374    use vortex_error::VortexResult;
375    use vortex_session::VortexSession;
376
377    use crate::IntoArray;
378    use crate::VortexSessionExecute;
379    use crate::arrays::BoolArray;
380    use crate::arrays::PrimitiveArray;
381    use crate::arrays::bool::BoolArrayExt;
382    use crate::assert_arrays_eq;
383    use crate::buffer::BufferHandle;
384    use crate::patches::Patches;
385    use crate::validity::Validity;
386
387    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
388
389    #[test]
390    fn bool_array() {
391        let mut ctx = SESSION.create_execution_ctx();
392
393        let arr = BoolArray::from_iter([true, false, true]);
394        let scalar = bool::try_from(&arr.execute_scalar(0, &mut ctx).unwrap()).unwrap();
395        assert!(scalar);
396    }
397
398    #[test]
399    fn test_all_some_iter() {
400        let mut ctx = SESSION.create_execution_ctx();
401
402        let arr = BoolArray::from_iter([Some(true), Some(false)]);
403
404        assert!(matches!(arr.validity(), Ok(Validity::AllValid)));
405
406        let scalar = bool::try_from(&arr.execute_scalar(0, &mut ctx).unwrap()).unwrap();
407        assert!(scalar);
408        let scalar = bool::try_from(&arr.execute_scalar(1, &mut ctx).unwrap()).unwrap();
409        assert!(!scalar);
410    }
411
412    #[test]
413    fn test_bool_from_iter() {
414        let mut ctx = SESSION.create_execution_ctx();
415        let arr = BoolArray::from_iter([Some(true), Some(true), None, Some(false), None]);
416
417        let scalar = bool::try_from(&arr.execute_scalar(0, &mut ctx).unwrap()).unwrap();
418        assert!(scalar);
419
420        let scalar = bool::try_from(&arr.execute_scalar(1, &mut ctx).unwrap()).unwrap();
421        assert!(scalar);
422
423        let scalar = arr.execute_scalar(2, &mut ctx).unwrap();
424        assert!(scalar.is_null());
425
426        let scalar = bool::try_from(&arr.execute_scalar(3, &mut ctx).unwrap()).unwrap();
427        assert!(!scalar);
428
429        let scalar = arr.execute_scalar(4, &mut ctx).unwrap();
430        assert!(scalar.is_null());
431    }
432
433    #[test]
434    fn patch_sliced_bools() {
435        let mut ctx = SESSION.create_execution_ctx();
436        let arr = BoolArray::from(BitBuffer::new_set(12));
437        let sliced = arr.slice(4..12).unwrap();
438        assert_arrays_eq!(sliced, BoolArray::from_iter([true; 8]), &mut ctx);
439
440        let arr = {
441            let mut builder = BitBufferMut::new_unset(12);
442            (1..12).for_each(|i| builder.set(i));
443            BoolArray::from(builder.freeze())
444        };
445        let sliced = arr.slice(4..12).unwrap();
446        let expected_slice: Vec<bool> = (4..12).map(|i| (1..12).contains(&i)).collect();
447        assert_arrays_eq!(
448            sliced,
449            BoolArray::from_iter(expected_slice.clone()),
450            &mut ctx
451        );
452
453        // patch the underlying array at index 4 to false
454        let patches = Patches::new(
455            arr.len(),
456            0,
457            buffer![4u32].into_array(),
458            BoolArray::from(BitBuffer::new_unset(1)).into_array(),
459            None,
460            &mut ctx,
461        )
462        .unwrap();
463        let arr = arr.patch(&patches, &mut ctx).unwrap();
464        // After patching index 4 to false: indices 1-3 and 5-11 are true, index 0 and 4 are false
465        let expected_patched: Vec<bool> = (0..12).map(|i| (1..12).contains(&i) && i != 4).collect();
466        assert_arrays_eq!(arr, BoolArray::from_iter(expected_patched), &mut ctx);
467
468        // the slice should be unchanged (still has original values before patch)
469        assert_arrays_eq!(sliced, BoolArray::from_iter(expected_slice), &mut ctx);
470    }
471
472    #[test]
473    fn slice_array_in_middle() {
474        let mut ctx = SESSION.create_execution_ctx();
475        let arr = BoolArray::from(BitBuffer::new_set(16));
476        let sliced = arr.slice(4..12).unwrap();
477        assert_arrays_eq!(sliced, BoolArray::from_iter([true; 8]), &mut ctx);
478    }
479
480    #[test]
481    fn slice_aligned_host_handle_at_unaligned_byte() -> VortexResult<()> {
482        let bits: ByteBuffer = buffer![0b1010_1100_u8, 0b0110_1001, 0];
483        let bits = bits.aligned(Alignment::of::<u64>());
484        let array =
485            BoolArray::new_handle(BufferHandle::new_host(bits), 0, 16, Validity::NonNullable)
486                .into_array();
487
488        let sliced = array.slice(9..15)?;
489
490        let mut ctx = SESSION.create_execution_ctx();
491        assert_arrays_eq!(
492            sliced,
493            BoolArray::from_iter([false, false, true, false, true, true]),
494            &mut ctx
495        );
496        Ok(())
497    }
498
499    #[test]
500    fn patch_bools_owned() {
501        let mut ctx = SESSION.create_execution_ctx();
502        let arr = BoolArray::from(BitBuffer::new_set(16));
503        let buf_ptr = arr.to_bit_buffer().inner().as_ptr();
504
505        let patches = Patches::new(
506            arr.len(),
507            0,
508            PrimitiveArray::new(buffer![0u32], Validity::NonNullable).into_array(),
509            BoolArray::from(BitBuffer::new_unset(1)).into_array(),
510            None,
511            &mut ctx,
512        )
513        .unwrap();
514        let arr = arr.patch(&patches, &mut ctx).unwrap();
515        // Verify buffer was reused in place
516        assert_eq!(arr.to_bit_buffer().inner().as_ptr(), buf_ptr);
517
518        // After patching index 0 to false: [false, true, true, ..., true] (16 values)
519        let expected: BoolArray = once(false).chain(repeat_n(true, 15)).collect();
520        assert_arrays_eq!(arr, expected, &mut ctx);
521    }
522
523    #[test]
524    fn patch_sliced_bools_offset() {
525        let mut ctx = SESSION.create_execution_ctx();
526        let arr = BoolArray::from(BitBuffer::new_set(15));
527        let sliced = arr.slice(4..15).unwrap();
528        assert_arrays_eq!(sliced, BoolArray::from_iter([true; 11]), &mut ctx);
529    }
530}