17040114484

Committed 18 Aug 2025 12:07PM UTC coverage: 86.042% (-1.9%) from 87.913%

Build # 17040114484

Build Type

Pull #4215

github

Committed by

web-flow

Commit Message

Merge 4600ca5c4 into cb1a92920

Pull Request Pull Request #4215: Ji/vectors

Run Details

132 of 1817 new or added lines in 42 files covered. (7.26%)

125 existing lines in 26 files now uncovered.

56932 of 66168 relevant lines covered (86.04%)

611735.65 hits per line

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

0.0

/vortex-vector/src/bits/view.rs

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

use std::fmt::{Debug, Formatter};

use bitvec::prelude::*;
use vortex_error::{VortexError, vortex_err};

use crate::PIPELINE_STEP_COUNT;

/// A borrowed fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
///
/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
/// it up for use within Vortex.
#[derive(Clone, Copy)]
pub struct BitView<'a> {
    bits: &'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>,
    true_count: usize,
}

impl Debug for BitView<'_> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("BitView")
            .field("true_count", &self.true_count)
            .field("bits", &self.as_raw())
            .finish()
    }
}

impl BitView<'static> {
    pub fn all_true() -> Self {
        unsafe {
            BitView::new_unchecked(
                std::mem::transmute(&[u64::MAX; PIPELINE_STEP_COUNT / 64]),
                PIPELINE_STEP_COUNT,
            )
        }
    }

    pub fn all_false() -> Self {
        unsafe { BitView::new_unchecked(std::mem::transmute(&[0; PIPELINE_STEP_COUNT / 64]), 0) }
    }
}

impl<'a> BitView<'a> {
    pub fn new(bits: &[u64; PIPELINE_STEP_COUNT / 64]) -> Self {
        let true_count = bits.iter().map(|&word| word.count_ones() as usize).sum();
        let bits: &BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0> =
            unsafe { std::mem::transmute(bits) };
        BitView { bits, true_count }
    }

    pub(crate) unsafe fn new_unchecked(
        bits: &'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>,
        true_count: usize,
    ) -> Self {
        BitView {
            bits: unsafe { std::mem::transmute(bits) },
            true_count,
        }
    }

    /// Returns the number of `true` bits in the view.
    pub fn true_count(&self) -> usize {
        self.true_count
    }

    /// Runs the provided function `f` for each index of a `true` bit in the view.
    pub fn iter_ones<F>(&self, mut f: F)
    where
        F: FnMut(usize),
    {
        match self.true_count {
            0 => {}
            PIPELINE_STEP_COUNT => (0..PIPELINE_STEP_COUNT).for_each(&mut f),
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    while raw != 0 {
                        let bit_pos = raw.trailing_zeros();
                        f(bit_idx + bit_pos as usize);
                        raw &= raw - 1; // Clear the bit at `bit_pos`
                    }
                    bit_idx += 64;
                }
            }
        }
    }

    /// Runs the provided function `f` for each index of a `true` bit in the view.
    pub fn iter_zeros<F>(&self, mut f: F)
    where
        F: FnMut(usize),
    {
        match self.true_count {
            0 => (0..PIPELINE_STEP_COUNT).for_each(&mut f),
            PIPELINE_STEP_COUNT => {}
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    while raw != u64::MAX {
                        let bit_pos = raw.trailing_ones();
                        f(bit_idx + bit_pos as usize);
                        raw |= 1u64 << bit_pos; // Set the zero bit to 1
                    }
                    bit_idx += 64;
                }
            }
        }
    }

    /// Runs the provided function `f` for each range of `true` bits in the view.
    ///
    /// The function `f` receives a tuple `(start, len)` where `start` is the index of the first
    /// `true` bit and `len` is the number of consecutive `true` bits.
    pub fn iter_slices<F>(&self, mut f: F)
    where
        F: FnMut((usize, usize)),
    {
        match self.true_count {
            0 => {}
            PIPELINE_STEP_COUNT => f((0, PIPELINE_STEP_COUNT)),
            _ => {
                let mut bit_idx = 0;
                for mut raw in self.bits.into_inner() {
                    let mut offset = 0;
                    while raw != 0 {
                        // Skip leading zeros first
                        let zeros = raw.leading_zeros();
                        offset += zeros;
                        raw <<= zeros;

                        if offset >= 64 {
                            break;
                        }

                        // Count leading ones
                        let ones = raw.leading_ones();
                        if ones > 0 {
                            f((bit_idx + offset as usize, ones as usize));
                            offset += ones;
                            raw <<= ones;
                        }
                    }
                    bit_idx += 64; // Move to next word
                }
            }
        }
    }

    pub fn as_raw(&self) -> &[u64; PIPELINE_STEP_COUNT / 64] {
        // It's actually remarkably hard to get a reference to the underlying array!
        let raw = self.bits.as_raw_slice();
        unsafe { &*(raw.as_ptr() as *const [u64; PIPELINE_STEP_COUNT / 64]) }
    }
}

impl<'a> From<&'a [u64; PIPELINE_STEP_COUNT / 64]> for BitView<'a> {
    fn from(value: &'a [u64; PIPELINE_STEP_COUNT / 64]) -> Self {
        Self::new(value)
    }
}

impl<'a> From<&'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>> for BitView<'a> {
    fn from(bits: &'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>) -> Self {
        BitView::new(unsafe { std::mem::transmute(bits) })
    }
}

impl<'a> TryFrom<&'a BitSlice<u64, Lsb0>> for BitView<'a> {
    type Error = VortexError;

    fn try_from(value: &'a BitSlice<u64, Lsb0>) -> Result<Self, Self::Error> {
        let bits: &BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0> = value
            .try_into()
            .map_err(|e| vortex_err!("Failed to convert BitSlice to BitArray: {}", e))?;
        Ok(BitView::new(unsafe { std::mem::transmute(bits) }))
    }
}

#[cfg(test)]
mod tests {
    use vortex_mask::Mask;

    use super::*;
    use crate::bits::BitVector;

    #[test]
    fn test_iter_ones_empty() {
        let bits = [0u64; PIPELINE_STEP_COUNT / 64];
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, Vec::<usize>::new());
        assert_eq!(view.true_count(), 0);
    }

    #[test]
    fn test_iter_ones_all_set() {
        let view = BitView::all_true();

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones.len(), PIPELINE_STEP_COUNT);
        assert_eq!(ones, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
        assert_eq!(view.true_count(), PIPELINE_STEP_COUNT);
    }

    #[test]
    fn test_iter_zeros_empty() {
        let bits = [0u64; PIPELINE_STEP_COUNT / 64];
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros.len(), PIPELINE_STEP_COUNT);
        assert_eq!(zeros, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
    }

    #[test]
    fn test_iter_zeros_all_set() {
        let view = BitView::all_true();

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, Vec::<usize>::new());
    }

    #[test]
    fn test_iter_ones_single_bit() {
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 1; // Set bit 0 (LSB)
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![0]);
        assert_eq!(view.true_count(), 1);
    }

    #[test]
    fn test_iter_zeros_single_bit_unset() {
        let mut bits = [u64::MAX; PIPELINE_STEP_COUNT / 64];
        bits[0] = u64::MAX ^ 1; // Clear bit 0 (LSB)
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, vec![0]);
    }

    #[test]
    fn test_iter_ones_multiple_bits_first_word() {
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 0b1010101; // Set bits 0, 2, 4, 6
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![0, 2, 4, 6]);
        assert_eq!(view.true_count(), 4);
    }

    #[test]
    fn test_iter_zeros_multiple_bits_first_word() {
        let mut bits = [u64::MAX; PIPELINE_STEP_COUNT / 64];
        bits[0] = !0b1010101; // Clear bits 0, 2, 4, 6
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, vec![0, 2, 4, 6]);
    }

    #[test]
    fn test_iter_ones_across_words() {
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 1 << 63; // Set bit 63 of first word
        bits[1] = 1; // Set bit 0 of second word (bit 64 overall)
        bits[2] = 1 << 31; // Set bit 31 of third word (bit 159 overall)
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![63, 64, 159]);
        assert_eq!(view.true_count(), 3);
    }

    #[test]
    fn test_iter_zeros_across_words() {
        let mut bits = [u64::MAX; PIPELINE_STEP_COUNT / 64];
        bits[0] = !(1 << 63); // Clear bit 63 of first word
        bits[1] = !1; // Clear bit 0 of second word (bit 64 overall)
        bits[2] = !(1 << 31); // Clear bit 31 of third word (bit 159 overall)
        let view = BitView::new(&bits);

        let mut zeros = Vec::new();
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(zeros, vec![63, 64, 159]);
    }

    #[test]
    fn test_lsb_bit_ordering() {
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 0b11111111; // Set bits 0-7 (LSB ordering)
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        view.iter_ones(|idx| ones.push(idx));

        assert_eq!(ones, vec![0, 1, 2, 3, 4, 5, 6, 7]);
        assert_eq!(view.true_count(), 8);
    }

    #[test]
    fn test_iter_ones_and_zeros_complement() {
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating pattern
        let view = BitView::new(&bits);

        let mut ones = Vec::new();
        let mut zeros = Vec::new();
        view.iter_ones(|idx| ones.push(idx));
        view.iter_zeros(|idx| zeros.push(idx));

        // Check that ones and zeros together cover all indices
        let mut all_indices = ones.clone();
        all_indices.extend(&zeros);
        all_indices.sort_unstable();

        assert_eq!(all_indices, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());

        // Check they don't overlap
        for one_idx in &ones {
            assert!(!zeros.contains(one_idx));
        }
    }

    #[test]
    fn test_all_false_static() {
        let view = BitView::all_false();

        let mut ones = Vec::new();
        let mut zeros = Vec::new();
        view.iter_ones(|idx| ones.push(idx));
        view.iter_zeros(|idx| zeros.push(idx));

        assert_eq!(ones, Vec::<usize>::new());
        assert_eq!(zeros, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
        assert_eq!(view.true_count(), 0);
    }

    #[test]
    fn test_compatibility_with_mask_all_true() {
        // Create a Mask with all bits set
        let mask = Mask::new_true(PIPELINE_STEP_COUNT);

        // Create corresponding BitView
        let view = BitView::all_true();

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Get indices from Mask (all indices for all_true mask)
        let expected_indices: Vec<usize> = (0..PIPELINE_STEP_COUNT).collect();

        assert_eq!(bitview_ones, expected_indices);
        assert_eq!(view.true_count(), PIPELINE_STEP_COUNT);
    }

    #[test]
    fn test_compatibility_with_mask_all_false() {
        // Create a Mask with no bits set
        let mask = Mask::new_false(PIPELINE_STEP_COUNT);

        // Create corresponding BitView
        let view = BitView::all_false();

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Collect zeros from BitView
        let mut bitview_zeros = Vec::new();
        view.iter_zeros(|idx| bitview_zeros.push(idx));

        assert_eq!(bitview_ones, Vec::<usize>::new());
        assert_eq!(bitview_zeros, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
        assert_eq!(view.true_count(), 0);
    }

    #[test]
    fn test_compatibility_with_mask_from_indices() {
        // Create a Mask from specific indices
        let indices = vec![0, 10, 20, 63, 64, 100, 500, 1023];
        let mask = Mask::from_indices(PIPELINE_STEP_COUNT, indices.clone());

        // Create corresponding BitView
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        for idx in &indices {
            let word_idx = idx / 64;
            let bit_idx = idx % 64;
            bits[word_idx] |= 1u64 << bit_idx;
        }
        let view = BitView::new(&bits);

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        assert_eq!(bitview_ones, indices);
        assert_eq!(view.true_count(), indices.len());
    }

    #[test]
    fn test_compatibility_with_mask_slices() {
        // Create a Mask from slices (ranges)
        let slices = vec![(0, 10), (100, 110), (500, 510)];
        let mask = Mask::from_slices(PIPELINE_STEP_COUNT, slices.clone());

        // Create corresponding BitView
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        for (start, end) in &slices {
            for idx in *start..*end {
                let word_idx = idx / 64;
                let bit_idx = idx % 64;
                bits[word_idx] |= 1u64 << bit_idx;
            }
        }
        let view = BitView::new(&bits);

        // Collect ones from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Expected indices from slices
        let mut expected_indices = Vec::new();
        for (start, end) in &slices {
            expected_indices.extend(*start..*end);
        }

        assert_eq!(bitview_ones, expected_indices);
        assert_eq!(view.true_count(), expected_indices.len());
    }

    #[test]
    fn test_mask_and_bitview_iter_match() {
        // Create a pattern with alternating bits in first word
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating 1s and 0s
        bits[1] = 0xFF00FF00FF00FF00; // Alternating bytes

        let view = BitView::new(&bits);

        // Collect indices from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Create Mask from the same indices
        let mask = Mask::from_indices(PIPELINE_STEP_COUNT, bitview_ones.clone());

        // Verify the mask returns the same indices
        mask.iter_bools(|iter| {
            let mask_bools: Vec<bool> = iter.collect();

            // Check each bit matches
            for i in 0..PIPELINE_STEP_COUNT {
                let expected = bitview_ones.contains(&i);
                assert_eq!(mask_bools[i], expected, "Mismatch at index {}", i);
            }
        });
    }

    #[test]
    fn test_mask_and_bitview_all_true() {
        let mask = Mask::AllTrue(5);

        let vector = BitVector::true_until(5);

        let view = vector.as_view();

        // Collect indices from BitView
        let mut bitview_ones = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));

        // Collect indices from BitView
        let mask_ones = mask.iter_bools(|iter| {
            iter.enumerate()
                .filter(|(_, b)| *b)
                .map(|(i, _)| i)
                .collect::<Vec<_>>()
        });

        assert_eq!(bitview_ones, mask_ones);
    }

    #[test]
    fn test_bitview_zeros_complement_mask() {
        // Create a pattern
        let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
        bits[0] = 0b11110000111100001111000011110000;

        let view = BitView::new(&bits);

        // Collect ones and zeros from BitView
        let mut bitview_ones = Vec::new();
        let mut bitview_zeros = Vec::new();
        view.iter_ones(|idx| bitview_ones.push(idx));
        view.iter_zeros(|idx| bitview_zeros.push(idx));

        // Create masks for ones and zeros
        let ones_mask = Mask::from_indices(PIPELINE_STEP_COUNT, bitview_ones);
        let zeros_mask = Mask::from_indices(PIPELINE_STEP_COUNT, bitview_zeros);

        // Verify they are complements
        ones_mask.iter_bools(|ones_iter| {
            zeros_mask.iter_bools(|zeros_iter| {
                let ones_bools: Vec<bool> = ones_iter.collect();
                let zeros_bools: Vec<bool> = zeros_iter.collect();

                for i in 0..PIPELINE_STEP_COUNT {
                    // Each index should be either in ones or zeros, but not both
                    assert_ne!(
                        ones_bools[i], zeros_bools[i],
                        "Index {} should be in exactly one set",
                        i
                    );
                }
            });
        });
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::fmt::{Debug, Formatter};
5
6	use bitvec::prelude::*;
7	use vortex_error::{VortexError, vortex_err};
8
9	use crate::PIPELINE_STEP_COUNT;
10
11	/// A borrowed fixed-size bit vector of length `N` bits, represented as an array of 64-bit words.
12	///
13	/// Internally, it uses a [`BitArray`] to store the bits, but this crate has some
14	/// performance foot-guns in cases where we can lean on better assumptions, and therefore we wrap
15	/// it up for use within Vortex.
16	#[derive(Clone, Copy)]
17	pub struct BitView<'a> {
18	bits: &'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>,
19	true_count: usize,
20	}
21
22	impl Debug for BitView<'_> {
NEW 23	fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {	×
NEW 24	f.debug_struct("BitView")	×
NEW 25	.field("true_count", &self.true_count)	×
NEW 26	.field("bits", &self.as_raw())	×
NEW 27	.finish()	×
NEW 28	}	×
29	}
30
31	impl BitView<'static> {
NEW 32	pub fn all_true() -> Self {	×
33	unsafe {
NEW 34	BitView::new_unchecked(	×
NEW 35	std::mem::transmute(&[u64::MAX; PIPELINE_STEP_COUNT / 64]),	×
36	PIPELINE_STEP_COUNT,
37	)
38	}
NEW 39	}	×
40
NEW 41	pub fn all_false() -> Self {	×
NEW 42	unsafe { BitView::new_unchecked(std::mem::transmute(&[0; PIPELINE_STEP_COUNT / 64]), 0) }	×
NEW 43	}	×
44	}
45
46	impl<'a> BitView<'a> {
NEW 47	pub fn new(bits: &[u64; PIPELINE_STEP_COUNT / 64]) -> Self {	×
NEW 48	let true_count = bits.iter().map(\|&word\| word.count_ones() as usize).sum();	×
NEW 49	let bits: &BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0> =	×
NEW 50	unsafe { std::mem::transmute(bits) };	×
NEW 51	BitView { bits, true_count }	×
NEW 52	}	×
53
NEW 54	pub(crate) unsafe fn new_unchecked(	×
NEW 55	bits: &'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>,	×
NEW 56	true_count: usize,	×
NEW 57	) -> Self {	×
NEW 58	BitView {	×
NEW 59	bits: unsafe { std::mem::transmute(bits) },	×
NEW 60	true_count,	×
NEW 61	}	×
NEW 62	}	×
63
64	/// Returns the number of `true` bits in the view.
NEW 65	pub fn true_count(&self) -> usize {	×
NEW 66	self.true_count	×
NEW 67	}	×
68
69	/// Runs the provided function `f` for each index of a `true` bit in the view.
NEW 70	pub fn iter_ones<F>(&self, mut f: F)	×
NEW 71	where	×
NEW 72	F: FnMut(usize),	×
73	{
NEW 74	match self.true_count {	×
NEW 75	0 => {}	×
NEW 76	PIPELINE_STEP_COUNT => (0..PIPELINE_STEP_COUNT).for_each(&mut f),	×
77	_ => {
NEW 78	let mut bit_idx = 0;	×
NEW 79	for mut raw in self.bits.into_inner() {	×
NEW 80	while raw != 0 {	×
NEW 81	let bit_pos = raw.trailing_zeros();	×
NEW 82	f(bit_idx + bit_pos as usize);	×
NEW 83	raw &= raw - 1; // Clear the bit at `bit_pos`	×
NEW 84	}	×
NEW 85	bit_idx += 64;	×
86	}
87	}
88	}
NEW 89	}	×
90
91	/// Runs the provided function `f` for each index of a `true` bit in the view.
NEW 92	pub fn iter_zeros<F>(&self, mut f: F)	×
NEW 93	where	×
NEW 94	F: FnMut(usize),	×
95	{
NEW 96	match self.true_count {	×
NEW 97	0 => (0..PIPELINE_STEP_COUNT).for_each(&mut f),	×
NEW 98	PIPELINE_STEP_COUNT => {}	×
99	_ => {
NEW 100	let mut bit_idx = 0;	×
NEW 101	for mut raw in self.bits.into_inner() {	×
NEW 102	while raw != u64::MAX {	×
NEW 103	let bit_pos = raw.trailing_ones();	×
NEW 104	f(bit_idx + bit_pos as usize);	×
NEW 105	raw \|= 1u64 << bit_pos; // Set the zero bit to 1	×
NEW 106	}	×
NEW 107	bit_idx += 64;	×
108	}
109	}
110	}
NEW 111	}	×
112
113	/// Runs the provided function `f` for each range of `true` bits in the view.
114	///
115	/// The function `f` receives a tuple `(start, len)` where `start` is the index of the first
116	/// `true` bit and `len` is the number of consecutive `true` bits.
NEW 117	pub fn iter_slices<F>(&self, mut f: F)	×
NEW 118	where	×
NEW 119	F: FnMut((usize, usize)),	×
120	{
NEW 121	match self.true_count {	×
NEW 122	0 => {}	×
NEW 123	PIPELINE_STEP_COUNT => f((0, PIPELINE_STEP_COUNT)),	×
124	_ => {
NEW 125	let mut bit_idx = 0;	×
NEW 126	for mut raw in self.bits.into_inner() {	×
NEW 127	let mut offset = 0;	×
NEW 128	while raw != 0 {	×
129	// Skip leading zeros first
NEW 130	let zeros = raw.leading_zeros();	×
NEW 131	offset += zeros;	×
NEW 132	raw <<= zeros;	×
133
NEW 134	if offset >= 64 {	×
NEW 135	break;	×
NEW 136	}	×
137
138	// Count leading ones
NEW 139	let ones = raw.leading_ones();	×
NEW 140	if ones > 0 {	×
NEW 141	f((bit_idx + offset as usize, ones as usize));	×
NEW 142	offset += ones;	×
NEW 143	raw <<= ones;	×
NEW 144	}	×
145	}
NEW 146	bit_idx += 64; // Move to next word	×
147	}
148	}
149	}
NEW 150	}	×
151
NEW 152	pub fn as_raw(&self) -> &[u64; PIPELINE_STEP_COUNT / 64] {	×
153	// It's actually remarkably hard to get a reference to the underlying array!
NEW 154	let raw = self.bits.as_raw_slice();	×
NEW 155	unsafe { &(raw.as_ptr() as const [u64; PIPELINE_STEP_COUNT / 64]) }	×
NEW 156	}	×
157	}
158
159	impl<'a> From<&'a [u64; PIPELINE_STEP_COUNT / 64]> for BitView<'a> {
NEW 160	fn from(value: &'a [u64; PIPELINE_STEP_COUNT / 64]) -> Self {	×
NEW 161	Self::new(value)	×
NEW 162	}	×
163	}
164
165	impl<'a> From<&'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>> for BitView<'a> {
NEW 166	fn from(bits: &'a BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0>) -> Self {	×
NEW 167	BitView::new(unsafe { std::mem::transmute(bits) })	×
NEW 168	}	×
169	}
170
171	impl<'a> TryFrom<&'a BitSlice<u64, Lsb0>> for BitView<'a> {
172	type Error = VortexError;
173
NEW 174	fn try_from(value: &'a BitSlice<u64, Lsb0>) -> Result<Self, Self::Error> {	×
NEW 175	let bits: &BitArray<[u64; PIPELINE_STEP_COUNT / 64], Lsb0> = value	×
NEW 176	.try_into()	×
NEW 177	.map_err(\|e\| vortex_err!("Failed to convert BitSlice to BitArray: {}", e))?;	×
NEW 178	Ok(BitView::new(unsafe { std::mem::transmute(bits) }))	×
NEW 179	}	×
180	}
181
182	#[cfg(test)]
183	mod tests {
184	use vortex_mask::Mask;
185
186	use super::*;
187	use crate::bits::BitVector;
188
189	#[test]
190	fn test_iter_ones_empty() {
191	let bits = [0u64; PIPELINE_STEP_COUNT / 64];
192	let view = BitView::new(&bits);
193
194	let mut ones = Vec::new();
195	view.iter_ones(\|idx\| ones.push(idx));
196
197	assert_eq!(ones, Vec::<usize>::new());
198	assert_eq!(view.true_count(), 0);
199	}
200
201	#[test]
202	fn test_iter_ones_all_set() {
203	let view = BitView::all_true();
204
205	let mut ones = Vec::new();
206	view.iter_ones(\|idx\| ones.push(idx));
207
208	assert_eq!(ones.len(), PIPELINE_STEP_COUNT);
209	assert_eq!(ones, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
210	assert_eq!(view.true_count(), PIPELINE_STEP_COUNT);
211	}
212
213	#[test]
214	fn test_iter_zeros_empty() {
215	let bits = [0u64; PIPELINE_STEP_COUNT / 64];
216	let view = BitView::new(&bits);
217
218	let mut zeros = Vec::new();
219	view.iter_zeros(\|idx\| zeros.push(idx));
220
221	assert_eq!(zeros.len(), PIPELINE_STEP_COUNT);
222	assert_eq!(zeros, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
223	}
224
225	#[test]
226	fn test_iter_zeros_all_set() {
227	let view = BitView::all_true();
228
229	let mut zeros = Vec::new();
230	view.iter_zeros(\|idx\| zeros.push(idx));
231
232	assert_eq!(zeros, Vec::<usize>::new());
233	}
234
235	#[test]
236	fn test_iter_ones_single_bit() {
237	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
238	bits[0] = 1; // Set bit 0 (LSB)
239	let view = BitView::new(&bits);
240
241	let mut ones = Vec::new();
242	view.iter_ones(\|idx\| ones.push(idx));
243
244	assert_eq!(ones, vec![0]);
245	assert_eq!(view.true_count(), 1);
246	}
247
248	#[test]
249	fn test_iter_zeros_single_bit_unset() {
250	let mut bits = [u64::MAX; PIPELINE_STEP_COUNT / 64];
251	bits[0] = u64::MAX ^ 1; // Clear bit 0 (LSB)
252	let view = BitView::new(&bits);
253
254	let mut zeros = Vec::new();
255	view.iter_zeros(\|idx\| zeros.push(idx));
256
257	assert_eq!(zeros, vec![0]);
258	}
259
260	#[test]
261	fn test_iter_ones_multiple_bits_first_word() {
262	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
263	bits[0] = 0b1010101; // Set bits 0, 2, 4, 6
264	let view = BitView::new(&bits);
265
266	let mut ones = Vec::new();
267	view.iter_ones(\|idx\| ones.push(idx));
268
269	assert_eq!(ones, vec![0, 2, 4, 6]);
270	assert_eq!(view.true_count(), 4);
271	}
272
273	#[test]
274	fn test_iter_zeros_multiple_bits_first_word() {
275	let mut bits = [u64::MAX; PIPELINE_STEP_COUNT / 64];
276	bits[0] = !0b1010101; // Clear bits 0, 2, 4, 6
277	let view = BitView::new(&bits);
278
279	let mut zeros = Vec::new();
280	view.iter_zeros(\|idx\| zeros.push(idx));
281
282	assert_eq!(zeros, vec![0, 2, 4, 6]);
283	}
284
285	#[test]
286	fn test_iter_ones_across_words() {
287	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
288	bits[0] = 1 << 63; // Set bit 63 of first word
289	bits[1] = 1; // Set bit 0 of second word (bit 64 overall)
290	bits[2] = 1 << 31; // Set bit 31 of third word (bit 159 overall)
291	let view = BitView::new(&bits);
292
293	let mut ones = Vec::new();
294	view.iter_ones(\|idx\| ones.push(idx));
295
296	assert_eq!(ones, vec![63, 64, 159]);
297	assert_eq!(view.true_count(), 3);
298	}
299
300	#[test]
301	fn test_iter_zeros_across_words() {
302	let mut bits = [u64::MAX; PIPELINE_STEP_COUNT / 64];
303	bits[0] = !(1 << 63); // Clear bit 63 of first word
304	bits[1] = !1; // Clear bit 0 of second word (bit 64 overall)
305	bits[2] = !(1 << 31); // Clear bit 31 of third word (bit 159 overall)
306	let view = BitView::new(&bits);
307
308	let mut zeros = Vec::new();
309	view.iter_zeros(\|idx\| zeros.push(idx));
310
311	assert_eq!(zeros, vec![63, 64, 159]);
312	}
313
314	#[test]
315	fn test_lsb_bit_ordering() {
316	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
317	bits[0] = 0b11111111; // Set bits 0-7 (LSB ordering)
318	let view = BitView::new(&bits);
319
320	let mut ones = Vec::new();
321	view.iter_ones(\|idx\| ones.push(idx));
322
323	assert_eq!(ones, vec![0, 1, 2, 3, 4, 5, 6, 7]);
324	assert_eq!(view.true_count(), 8);
325	}
326
327	#[test]
328	fn test_iter_ones_and_zeros_complement() {
329	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
330	bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating pattern
331	let view = BitView::new(&bits);
332
333	let mut ones = Vec::new();
334	let mut zeros = Vec::new();
335	view.iter_ones(\|idx\| ones.push(idx));
336	view.iter_zeros(\|idx\| zeros.push(idx));
337
338	// Check that ones and zeros together cover all indices
339	let mut all_indices = ones.clone();
340	all_indices.extend(&zeros);
341	all_indices.sort_unstable();
342
343	assert_eq!(all_indices, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
344
345	// Check they don't overlap
346	for one_idx in &ones {
347	assert!(!zeros.contains(one_idx));
348	}
349	}
350
351	#[test]
352	fn test_all_false_static() {
353	let view = BitView::all_false();
354
355	let mut ones = Vec::new();
356	let mut zeros = Vec::new();
357	view.iter_ones(\|idx\| ones.push(idx));
358	view.iter_zeros(\|idx\| zeros.push(idx));
359
360	assert_eq!(ones, Vec::<usize>::new());
361	assert_eq!(zeros, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
362	assert_eq!(view.true_count(), 0);
363	}
364
365	#[test]
366	fn test_compatibility_with_mask_all_true() {
367	// Create a Mask with all bits set
368	let mask = Mask::new_true(PIPELINE_STEP_COUNT);
369
370	// Create corresponding BitView
371	let view = BitView::all_true();
372
373	// Collect ones from BitView
374	let mut bitview_ones = Vec::new();
375	view.iter_ones(\|idx\| bitview_ones.push(idx));
376
377	// Get indices from Mask (all indices for all_true mask)
378	let expected_indices: Vec<usize> = (0..PIPELINE_STEP_COUNT).collect();
379
380	assert_eq!(bitview_ones, expected_indices);
381	assert_eq!(view.true_count(), PIPELINE_STEP_COUNT);
382	}
383
384	#[test]
385	fn test_compatibility_with_mask_all_false() {
386	// Create a Mask with no bits set
387	let mask = Mask::new_false(PIPELINE_STEP_COUNT);
388
389	// Create corresponding BitView
390	let view = BitView::all_false();
391
392	// Collect ones from BitView
393	let mut bitview_ones = Vec::new();
394	view.iter_ones(\|idx\| bitview_ones.push(idx));
395
396	// Collect zeros from BitView
397	let mut bitview_zeros = Vec::new();
398	view.iter_zeros(\|idx\| bitview_zeros.push(idx));
399
400	assert_eq!(bitview_ones, Vec::<usize>::new());
401	assert_eq!(bitview_zeros, (0..PIPELINE_STEP_COUNT).collect::<Vec<_>>());
402	assert_eq!(view.true_count(), 0);
403	}
404
405	#[test]
406	fn test_compatibility_with_mask_from_indices() {
407	// Create a Mask from specific indices
408	let indices = vec![0, 10, 20, 63, 64, 100, 500, 1023];
409	let mask = Mask::from_indices(PIPELINE_STEP_COUNT, indices.clone());
410
411	// Create corresponding BitView
412	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
413	for idx in &indices {
414	let word_idx = idx / 64;
415	let bit_idx = idx % 64;
416	bits[word_idx] \|= 1u64 << bit_idx;
417	}
418	let view = BitView::new(&bits);
419
420	// Collect ones from BitView
421	let mut bitview_ones = Vec::new();
422	view.iter_ones(\|idx\| bitview_ones.push(idx));
423
424	assert_eq!(bitview_ones, indices);
425	assert_eq!(view.true_count(), indices.len());
426	}
427
428	#[test]
429	fn test_compatibility_with_mask_slices() {
430	// Create a Mask from slices (ranges)
431	let slices = vec![(0, 10), (100, 110), (500, 510)];
432	let mask = Mask::from_slices(PIPELINE_STEP_COUNT, slices.clone());
433
434	// Create corresponding BitView
435	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
436	for (start, end) in &slices {
437	for idx in start..end {
438	let word_idx = idx / 64;
439	let bit_idx = idx % 64;
440	bits[word_idx] \|= 1u64 << bit_idx;
441	}
442	}
443	let view = BitView::new(&bits);
444
445	// Collect ones from BitView
446	let mut bitview_ones = Vec::new();
447	view.iter_ones(\|idx\| bitview_ones.push(idx));
448
449	// Expected indices from slices
450	let mut expected_indices = Vec::new();
451	for (start, end) in &slices {
452	expected_indices.extend(start..end);
453	}
454
455	assert_eq!(bitview_ones, expected_indices);
456	assert_eq!(view.true_count(), expected_indices.len());
457	}
458
459	#[test]
460	fn test_mask_and_bitview_iter_match() {
461	// Create a pattern with alternating bits in first word
462	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
463	bits[0] = 0xAAAAAAAAAAAAAAAA; // Alternating 1s and 0s
464	bits[1] = 0xFF00FF00FF00FF00; // Alternating bytes
465
466	let view = BitView::new(&bits);
467
468	// Collect indices from BitView
469	let mut bitview_ones = Vec::new();
470	view.iter_ones(\|idx\| bitview_ones.push(idx));
471
472	// Create Mask from the same indices
473	let mask = Mask::from_indices(PIPELINE_STEP_COUNT, bitview_ones.clone());
474
475	// Verify the mask returns the same indices
476	mask.iter_bools(\|iter\| {
477	let mask_bools: Vec<bool> = iter.collect();
478
479	// Check each bit matches
480	for i in 0..PIPELINE_STEP_COUNT {
481	let expected = bitview_ones.contains(&i);
482	assert_eq!(mask_bools[i], expected, "Mismatch at index {}", i);
483	}
484	});
485	}
486
487	#[test]
488	fn test_mask_and_bitview_all_true() {
489	let mask = Mask::AllTrue(5);
490
491	let vector = BitVector::true_until(5);
492
493	let view = vector.as_view();
494
495	// Collect indices from BitView
496	let mut bitview_ones = Vec::new();
497	view.iter_ones(\|idx\| bitview_ones.push(idx));
498
499	// Collect indices from BitView
500	let mask_ones = mask.iter_bools(\|iter\| {
501	iter.enumerate()
502	.filter(\|(_, b)\| *b)
503	.map(\|(i, _)\| i)
504	.collect::<Vec<_>>()
505	});
506
507	assert_eq!(bitview_ones, mask_ones);
508	}
509
510	#[test]
511	fn test_bitview_zeros_complement_mask() {
512	// Create a pattern
513	let mut bits = [0u64; PIPELINE_STEP_COUNT / 64];
514	bits[0] = 0b11110000111100001111000011110000;
515
516	let view = BitView::new(&bits);
517
518	// Collect ones and zeros from BitView
519	let mut bitview_ones = Vec::new();
520	let mut bitview_zeros = Vec::new();
521	view.iter_ones(\|idx\| bitview_ones.push(idx));
522	view.iter_zeros(\|idx\| bitview_zeros.push(idx));
523
524	// Create masks for ones and zeros
525	let ones_mask = Mask::from_indices(PIPELINE_STEP_COUNT, bitview_ones);
526	let zeros_mask = Mask::from_indices(PIPELINE_STEP_COUNT, bitview_zeros);
527
528	// Verify they are complements
529	ones_mask.iter_bools(\|ones_iter\| {
530	zeros_mask.iter_bools(\|zeros_iter\| {
531	let ones_bools: Vec<bool> = ones_iter.collect();
532	let zeros_bools: Vec<bool> = zeros_iter.collect();
533
534	for i in 0..PIPELINE_STEP_COUNT {
535	// Each index should be either in ones or zeros, but not both
536	assert_ne!(
537	ones_bools[i], zeros_bools[i],
538	"Index {} should be in exactly one set",
539	i
540	);
541	}
542	});
543	});
544	}
545	}

vortex-data / vortex / 17040114484

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