commonware_utils/bitmap/

prunable.rs

//! A prunable wrapper around BitMap that tracks pruned chunks.

use super::BitMap;
use bytes::BufMut;
use commonware_codec::{Buf, EncodeSize, Error as CodecError, RangeCfg, Read, ReadExt, Write};
use thiserror::Error;

/// Errors that can occur when working with a prunable bitmap.
#[derive(Debug, Error, Clone, PartialEq, Eq)]
pub enum Error {
    /// The provided pruned_chunks value would overflow.
    #[error("pruned_chunks * CHUNK_SIZE_BITS overflows u64")]
    PrunedChunksOverflow,
}

/// A prunable bitmap that stores data in chunks of N bytes.
///
/// # Panics
///
/// Operations panic if `bit / CHUNK_SIZE_BITS > usize::MAX`. On 32-bit systems
/// with N=32, this occurs at bit >= 1,099,511,627,776.
#[derive(Clone, Debug)]
pub struct Prunable<const N: usize> {
    /// The underlying BitMap storing the actual bits.
    bitmap: BitMap<N>,

    /// The number of bitmap chunks that have been pruned.
    ///
    /// # Invariant
    ///
    /// Must satisfy: `pruned_chunks as u64 * CHUNK_SIZE_BITS + bitmap.len() <= u64::MAX`
    pruned_chunks: usize,
}

impl<const N: usize> Prunable<N> {
    /// The size of a chunk in bits.
    pub const CHUNK_SIZE_BITS: u64 = BitMap::<N>::CHUNK_SIZE_BITS;

    /* Constructors */

    /// Create a new empty prunable bitmap.
    pub const fn new() -> Self {
        Self {
            bitmap: BitMap::new(),
            pruned_chunks: 0,
        }
    }

    /// Create a new empty prunable bitmap with the given number of pruned chunks.
    ///
    /// # Errors
    ///
    /// Returns an error if `pruned_chunks` violates the invariant that
    /// `pruned_chunks as u64 * CHUNK_SIZE_BITS` must not overflow u64.
    pub fn new_with_pruned_chunks(pruned_chunks: usize) -> Result<Self, Error> {
        // Validate the invariant: pruned_chunks * CHUNK_SIZE_BITS must fit in u64
        let pruned_chunks_u64 = pruned_chunks as u64;
        pruned_chunks_u64
            .checked_mul(Self::CHUNK_SIZE_BITS)
            .ok_or(Error::PrunedChunksOverflow)?;

        Ok(Self {
            bitmap: BitMap::new(),
            pruned_chunks,
        })
    }

    /* Length */

    /// Return the number of bits in the bitmap, irrespective of any pruning.
    #[inline]
    pub const fn len(&self) -> u64 {
        let pruned_bits = (self.pruned_chunks as u64)
            .checked_mul(Self::CHUNK_SIZE_BITS)
            .expect("invariant violated: pruned_chunks * CHUNK_SIZE_BITS overflows u64");

        pruned_bits
            .checked_add(self.bitmap.len())
            .expect("invariant violated: pruned_bits + bitmap.len() overflows u64")
    }

    /// Return true if the bitmap is empty.
    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns true if the bitmap length is aligned to a chunk boundary.
    #[inline]
    pub const fn is_chunk_aligned(&self) -> bool {
        self.len().is_multiple_of(Self::CHUNK_SIZE_BITS)
    }

    /// Return the number of chunks, including pruned chunks.
    #[inline]
    pub fn chunks_len(&self) -> usize {
        self.pruned_chunks + self.bitmap.chunks_len()
    }

    /// Return the number of pruned chunks.
    #[inline]
    pub const fn pruned_chunks(&self) -> usize {
        self.pruned_chunks
    }

    /// Return the number of complete (fully filled) chunks in the bitmap, accounting
    /// for pruning. A chunk is complete when all CHUNK_SIZE_BITS bits have been written.
    #[inline]
    pub fn complete_chunks(&self) -> usize {
        self.pruned_chunks
            + self
                .bitmap
                .chunks_len()
                .saturating_sub(if self.is_chunk_aligned() { 0 } else { 1 })
    }

    /// Return the number of pruned bits.
    #[inline]
    pub const fn pruned_bits(&self) -> u64 {
        (self.pruned_chunks as u64)
            .checked_mul(Self::CHUNK_SIZE_BITS)
            .expect("invariant violated: pruned_chunks * CHUNK_SIZE_BITS overflows u64")
    }

    /* Getters */

    /// Get the value of a bit.
    ///
    /// # Warning
    ///
    /// Panics if the bit doesn't exist or has been pruned.
    #[inline]
    pub fn get_bit(&self, bit: u64) -> bool {
        let chunk_num = Self::to_chunk_index(bit);
        assert!(chunk_num >= self.pruned_chunks, "bit pruned: {bit}");

        // Adjust bit to account for pruning
        self.bitmap.get(bit - self.pruned_bits())
    }

    /// Returns the bitmap chunk containing the specified bit.
    ///
    /// # Warning
    ///
    /// Panics if the bit doesn't exist or has been pruned.
    #[inline]
    pub fn get_chunk_containing(&self, bit: u64) -> &[u8; N] {
        let chunk_num = Self::to_chunk_index(bit);
        assert!(chunk_num >= self.pruned_chunks, "bit pruned: {bit}");

        // Adjust bit to account for pruning
        self.bitmap.get_chunk_containing(bit - self.pruned_bits())
    }

    /// Get the value of a bit from its chunk.
    /// `bit` is an index into the entire bitmap, not just the chunk.
    #[inline]
    pub const fn get_bit_from_chunk(chunk: &[u8; N], bit: u64) -> bool {
        BitMap::<N>::get_bit_from_chunk(chunk, bit)
    }

    /// Return the last chunk of the bitmap and its size in bits.
    #[inline]
    pub fn last_chunk(&self) -> (&[u8; N], u64) {
        self.bitmap.last_chunk()
    }

    /* Setters */

    /// Set the value of the given bit.
    ///
    /// # Warning
    ///
    /// Panics if the bit doesn't exist or has been pruned.
    pub fn set_bit(&mut self, bit: u64, value: bool) {
        let chunk_num = Self::to_chunk_index(bit);
        assert!(chunk_num >= self.pruned_chunks, "bit pruned: {bit}");

        // Adjust bit to account for pruning
        self.bitmap.set(bit - self.pruned_bits(), value);
    }

    /// Add a single bit to the end of the bitmap.
    pub fn push(&mut self, bit: bool) {
        self.bitmap.push(bit);
    }

    /// Extend the bitmap to `new_len` total bits (including pruned bits), filling new positions
    /// with zero. No-op if `new_len <= self.len()`.
    pub fn extend_to(&mut self, new_len: u64) {
        let current = self.len();
        if new_len > current {
            self.bitmap.extend_to(new_len - self.pruned_bits());
        }
    }

    /// Remove and return the last bit from the bitmap.
    ///
    /// # Warning
    ///
    /// Panics if the bitmap is empty.
    pub fn pop(&mut self) -> bool {
        self.bitmap.pop()
    }

    /// Shrink the bitmap to `new_len` total bits (including pruned bits).
    ///
    /// # Panics
    ///
    /// Panics if `new_len > self.len()` or `new_len < self.pruned_bits()`.
    pub fn truncate(&mut self, new_len: u64) {
        assert!(
            new_len >= self.pruned_bits(),
            "cannot truncate into pruned region"
        );
        self.bitmap.truncate(new_len - self.pruned_bits());
    }

    /// Add a byte to the bitmap.
    ///
    /// # Warning
    ///
    /// Panics if self.next_bit is not byte aligned.
    pub fn push_byte(&mut self, byte: u8) {
        self.bitmap.push_byte(byte);
    }

    /// Add a chunk of bits to the bitmap.
    ///
    /// # Warning
    ///
    /// Panics if self.next_bit is not chunk aligned.
    pub fn push_chunk(&mut self, chunk: &[u8; N]) {
        self.bitmap.push_chunk(chunk);
    }

    /// Append every bit of `other`, in order. See [`BitMap::extend_from_bitmap`].
    pub fn extend_from_bitmap<const M: usize>(&mut self, other: &BitMap<M>) {
        self.bitmap.extend_from_bitmap(other);
    }

    /// Remove and return the last complete chunk from the bitmap.
    ///
    /// # Warning
    ///
    /// Panics if the bitmap has fewer than `CHUNK_SIZE_BITS` bits or if not chunk-aligned.
    pub fn pop_chunk(&mut self) -> [u8; N] {
        self.bitmap.pop_chunk()
    }

    /* Pruning */

    /// Prune all complete chunks before the chunk containing the given bit.
    ///
    /// The chunk containing `bit` and all subsequent chunks are retained. All chunks
    /// before it are pruned.
    ///
    /// If `bit` equals the bitmap length, this prunes all complete chunks while retaining
    /// the empty trailing chunk, preparing the bitmap for appending new data.
    ///
    /// # Warning
    ///
    /// Panics if `bit` is greater than the bitmap length.
    pub fn prune_to_bit(&mut self, bit: u64) {
        assert!(
            bit <= self.len(),
            "bit {} out of bounds (len: {})",
            bit,
            self.len()
        );

        let chunk = Self::to_chunk_index(bit);
        if chunk < self.pruned_chunks {
            return;
        }

        let chunks_to_prune = chunk - self.pruned_chunks;
        self.bitmap.prune_chunks(chunks_to_prune);
        self.pruned_chunks = chunk;
    }

    /* Indexing Helpers */

    /// Convert a bit into a bitmask for the byte containing that bit.
    #[inline]
    pub const fn chunk_byte_bitmask(bit: u64) -> u8 {
        BitMap::<N>::chunk_byte_bitmask(bit)
    }

    /// Convert a bit into the index of the byte within a chunk containing the bit.
    #[inline]
    pub const fn chunk_byte_offset(bit: u64) -> usize {
        BitMap::<N>::chunk_byte_offset(bit)
    }

    /// Convert a bit into the index of the chunk it belongs to.
    ///
    /// # Panics
    ///
    /// Panics if `bit / CHUNK_SIZE_BITS > usize::MAX`.
    #[inline]
    pub fn to_chunk_index(bit: u64) -> usize {
        BitMap::<N>::to_chunk_index(bit)
    }

    /// Get a reference to a chunk by its absolute index (includes pruned chunks).
    ///
    /// # Panics
    ///
    /// Panics if the chunk has been pruned or is out of bounds.
    #[inline]
    pub fn get_chunk(&self, chunk: usize) -> &[u8; N] {
        assert!(
            chunk >= self.pruned_chunks,
            "chunk {chunk} is pruned (pruned_chunks: {})",
            self.pruned_chunks
        );
        self.bitmap.get_chunk(chunk - self.pruned_chunks)
    }

    /// Overwrite a chunk's data by its absolute chunk index.
    ///
    /// # Panics
    ///
    /// Panics if the chunk is pruned or out of bounds, or if this is the last partial
    /// chunk and `chunk_data` has non-zero bits beyond `len()`.
    pub fn set_chunk_by_index(&mut self, chunk_index: usize, chunk_data: &[u8; N]) {
        assert!(
            chunk_index >= self.pruned_chunks,
            "cannot set pruned chunk {chunk_index} (pruned_chunks: {})",
            self.pruned_chunks
        );
        let bitmap_chunk_idx = chunk_index - self.pruned_chunks;

        // Reject non-zero trailing bits in the last partial chunk to maintain the
        // canonicalization invariant required by the codec.
        if bitmap_chunk_idx + 1 == self.bitmap.chunks_len() {
            let trailing = self.bitmap.len() % Self::CHUNK_SIZE_BITS;
            if trailing != 0 {
                let last_byte = ((trailing - 1) / 8) as usize;
                let bits_in_last_byte = (trailing % 8) as u32;
                let byte_mask = if bits_in_last_byte != 0 {
                    !((1u8 << bits_in_last_byte) - 1)
                } else {
                    0
                };
                assert!(
                    chunk_data[last_byte] & byte_mask == 0
                        && chunk_data[last_byte + 1..] == [0u8; N][last_byte + 1..],
                    "non-zero bits beyond bitmap length"
                );
            }
        }

        self.bitmap.set_chunk_by_index(bitmap_chunk_idx, chunk_data);
    }

    /// Unprune chunks by prepending them back to the front of the bitmap.
    ///
    /// The caller must provide chunks in **reverse** order: to restore chunks with
    /// indices [0, 1, 2], pass them as [2, 1, 0]. This is necessary because each chunk
    /// is prepended to the front, so the last chunk provided becomes the first chunk
    /// in the bitmap.
    ///
    /// # Panics
    ///
    /// Panics if chunks.len() > self.pruned_chunks.
    pub(super) fn unprune_chunks(&mut self, chunks: &[[u8; N]]) {
        assert!(
            chunks.len() <= self.pruned_chunks,
            "cannot unprune {} chunks (only {} pruned)",
            chunks.len(),
            self.pruned_chunks
        );

        for chunk in chunks.iter() {
            self.bitmap.prepend_chunk(chunk);
        }

        self.pruned_chunks -= chunks.len();
    }
}

impl<const N: usize> super::Readable<N> for Prunable<N> {
    fn complete_chunks(&self) -> usize {
        Self::complete_chunks(self)
    }
    fn get_chunk(&self, chunk: usize) -> [u8; N] {
        *Self::get_chunk(self, chunk)
    }
    fn last_chunk(&self) -> ([u8; N], u64) {
        let (c, n) = Self::last_chunk(self);
        (*c, n)
    }
    fn pruned_chunks(&self) -> usize {
        self.pruned_chunks
    }
    fn len(&self) -> u64 {
        Self::len(self)
    }
}

impl<const N: usize> Default for Prunable<N> {
    fn default() -> Self {
        Self::new()
    }
}

impl<const N: usize> Write for Prunable<N> {
    fn write(&self, buf: &mut impl BufMut) {
        (self.pruned_chunks as u64).write(buf);
        self.bitmap.write(buf);
    }
}

impl<const N: usize> Read for Prunable<N> {
    /// Accepted range for the number of retained (unpruned) bits.
    /// [Self::len] also counts pruned bits.
    type Cfg = RangeCfg<u64>;

    fn read_cfg(buf: &mut impl Buf, range: &Self::Cfg) -> Result<Self, CodecError> {
        let pruned_chunks_u64 = u64::read(buf)?;

        // Validate that pruned_chunks * CHUNK_SIZE_BITS doesn't overflow u64
        let pruned_bits =
            pruned_chunks_u64
                .checked_mul(Self::CHUNK_SIZE_BITS)
                .ok_or(CodecError::Invalid(
                    "Prunable",
                    "pruned_chunks would overflow when computing pruned_bits",
                ))?;

        let pruned_chunks = usize::try_from(pruned_chunks_u64)
            .map_err(|_| CodecError::Invalid("Prunable", "pruned_chunks doesn't fit in usize"))?;

        let bitmap = BitMap::<N>::read_cfg(buf, range)?;

        // Validate that total length (pruned_bits + bitmap.len()) doesn't overflow u64
        pruned_bits
            .checked_add(bitmap.len())
            .ok_or(CodecError::Invalid(
                "Prunable",
                "total bitmap length (pruned + unpruned) would overflow u64",
            ))?;

        Ok(Self {
            bitmap,
            pruned_chunks,
        })
    }
}

impl<const N: usize> EncodeSize for Prunable<N> {
    fn encode_size(&self) -> usize {
        (self.pruned_chunks as u64).encode_size() + self.bitmap.encode_size()
    }
}

#[cfg(feature = "arbitrary")]
impl<const N: usize> arbitrary::Arbitrary<'_> for Prunable<N> {
    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
        let mut bitmap = Self {
            bitmap: BitMap::<N>::arbitrary(u)?,
            pruned_chunks: 0,
        };
        let prune_to = u.int_in_range(0..=bitmap.len())?;
        bitmap.prune_to_bit(prune_to);
        Ok(bitmap)
    }
}

#[cfg(test)]
mod tests {
    use super::{super::Readable, *};
    use bytes::BytesMut;
    use commonware_codec::Encode;
    use commonware_formatting::hex;

    #[test]
    fn test_new() {
        let prunable: Prunable<32> = Prunable::new();
        assert_eq!(prunable.len(), 0);
        assert_eq!(prunable.pruned_bits(), 0);
        assert_eq!(prunable.pruned_chunks(), 0);
        assert!(prunable.is_empty());
        assert_eq!(prunable.chunks_len(), 0); // No chunks when empty
    }

    #[test]
    fn test_new_with_pruned_chunks() {
        let prunable: Prunable<2> = Prunable::new_with_pruned_chunks(1).unwrap();
        assert_eq!(prunable.len(), 16);
        assert_eq!(prunable.pruned_bits(), 16);
        assert_eq!(prunable.pruned_chunks(), 1);
        assert_eq!(prunable.chunks_len(), 1);
    }

    #[test]
    fn test_new_with_pruned_chunks_overflow() {
        // Try to create a Prunable with pruned_chunks that would overflow
        let overflowing_pruned_chunks = (u64::MAX / Prunable::<4>::CHUNK_SIZE_BITS) as usize + 1;
        let result = Prunable::<4>::new_with_pruned_chunks(overflowing_pruned_chunks);

        assert!(matches!(result, Err(Error::PrunedChunksOverflow)));
    }

    #[test]
    fn test_push_and_get_bits() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add some bits
        prunable.push(true);
        prunable.push(false);
        prunable.push(true);

        assert_eq!(prunable.len(), 3);
        assert!(!prunable.is_empty());
        assert!(prunable.get_bit(0));
        assert!(!prunable.get_bit(1));
        assert!(prunable.get_bit(2));
    }

    #[test]
    fn test_push_byte() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add a byte
        prunable.push_byte(0xFF);
        assert_eq!(prunable.len(), 8);

        // All bits should be set
        for i in 0..8 {
            assert!(prunable.get_bit(i as u64));
        }

        prunable.push_byte(0x00);
        assert_eq!(prunable.len(), 16);

        // Next 8 bits should be clear
        for i in 8..16 {
            assert!(!prunable.get_bit(i as u64));
        }
    }

    #[test]
    fn test_push_chunk() {
        let mut prunable: Prunable<4> = Prunable::new();
        let chunk = hex!("0xAABBCCDD");

        prunable.push_chunk(&chunk);
        assert_eq!(prunable.len(), 32); // 4 bytes * 8 bits

        let retrieved_chunk = prunable.get_chunk_containing(0);
        assert_eq!(retrieved_chunk, &chunk);
    }

    #[test]
    fn test_extend_from_bitmap_after_pruning_matches_push() {
        // Appending after pruned chunks and a zero-filled gap matches pushing bit by bit.
        let mut src: BitMap = BitMap::new();
        for i in 0..1000u64 {
            src.push(i % 3 == 0 || i % 7 == 0);
        }
        for floor in [128, 129, 191, 255, 256, 300] {
            let mut actual = Prunable::<16>::new();
            actual.extend_to(128);
            actual.prune_to_bit(128);
            actual.extend_to(floor);
            let mut expected = actual.clone();
            for bit in src.iter() {
                expected.push(bit);
            }
            actual.extend_from_bitmap(&src);
            assert_eq!(actual.len(), expected.len());
            assert_eq!(actual.pruned_bits(), expected.pruned_bits());
            for bit in actual.pruned_bits()..actual.len() {
                assert_eq!(
                    actual.get_bit(bit),
                    expected.get_bit(bit),
                    "floor={floor} bit={bit}"
                );
            }
        }
    }

    #[test]
    fn test_set_bit() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add some bits
        prunable.push(false);
        prunable.push(false);
        prunable.push(false);

        assert!(!prunable.get_bit(1));

        // Set a bit
        prunable.set_bit(1, true);
        assert!(prunable.get_bit(1));

        // Set it back
        prunable.set_bit(1, false);
        assert!(!prunable.get_bit(1));
    }

    #[test]
    fn test_pruning_basic() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add multiple chunks (4 bytes each)
        let chunk1 = hex!("0x01020304");
        let chunk2 = hex!("0x05060708");
        let chunk3 = hex!("0x090A0B0C");

        prunable.push_chunk(&chunk1);
        prunable.push_chunk(&chunk2);
        prunable.push_chunk(&chunk3);

        assert_eq!(prunable.len(), 96); // 3 chunks * 32 bits
        assert_eq!(prunable.pruned_chunks(), 0);

        // Prune to second chunk (bit 32 is start of second chunk)
        prunable.prune_to_bit(32);
        assert_eq!(prunable.pruned_chunks(), 1);
        assert_eq!(prunable.pruned_bits(), 32);
        assert_eq!(prunable.len(), 96); // Total count unchanged

        // Can still access non-pruned bits
        assert_eq!(prunable.get_chunk_containing(32), &chunk2);
        assert_eq!(prunable.get_chunk_containing(64), &chunk3);

        // Prune to third chunk
        prunable.prune_to_bit(64);
        assert_eq!(prunable.pruned_chunks(), 2);
        assert_eq!(prunable.pruned_bits(), 64);
        assert_eq!(prunable.len(), 96);

        // Can still access the third chunk
        assert_eq!(prunable.get_chunk_containing(64), &chunk3);
    }

    #[test]
    #[should_panic(expected = "bit pruned")]
    fn test_get_pruned_bit_panics() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add two chunks
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);

        // Prune first chunk
        prunable.prune_to_bit(32);

        // Try to access pruned bit - should panic
        prunable.get_bit(0);
    }

    #[test]
    #[should_panic(expected = "bit pruned")]
    fn test_get_pruned_chunk_panics() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add two chunks
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);

        // Prune first chunk
        prunable.prune_to_bit(32);

        // Try to access pruned chunk - should panic
        prunable.get_chunk_containing(0);
    }

    #[test]
    #[should_panic(expected = "bit pruned")]
    fn test_set_pruned_bit_panics() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add two chunks
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);

        // Prune first chunk
        prunable.prune_to_bit(32);

        // Try to set pruned bit - should panic
        prunable.set_bit(0, true);
    }

    #[test]
    #[should_panic(expected = "bit 25 out of bounds (len: 24)")]
    fn test_prune_to_bit_out_of_bounds() {
        let mut prunable: Prunable<1> = Prunable::new();

        // Add 3 bytes (24 bits total)
        prunable.push_byte(1);
        prunable.push_byte(2);
        prunable.push_byte(3);

        // Try to prune to a bit beyond the bitmap
        prunable.prune_to_bit(25);
    }

    #[test]
    fn test_pruning_with_partial_chunk() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add two full chunks and some partial bits
        prunable.push_chunk(&[0xFF; 4]);
        prunable.push_chunk(&[0xAA; 4]);
        prunable.push(true);
        prunable.push(false);
        prunable.push(true);

        assert_eq!(prunable.len(), 67); // 64 + 3 bits

        // Prune to second chunk
        prunable.prune_to_bit(32);
        assert_eq!(prunable.pruned_chunks(), 1);
        assert_eq!(prunable.len(), 67);

        // Can still access the partial bits
        assert!(prunable.get_bit(64));
        assert!(!prunable.get_bit(65));
        assert!(prunable.get_bit(66));
    }

    #[test]
    fn test_prune_idempotent() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add chunks
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);

        // Prune to bit 32
        prunable.prune_to_bit(32);
        assert_eq!(prunable.pruned_chunks(), 1);

        // Pruning to same or earlier point should be no-op
        prunable.prune_to_bit(32);
        assert_eq!(prunable.pruned_chunks(), 1);

        prunable.prune_to_bit(16);
        assert_eq!(prunable.pruned_chunks(), 1);
    }

    #[test]
    fn test_push_after_pruning() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add initial chunks
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);

        // Prune first chunk
        prunable.prune_to_bit(32);
        assert_eq!(prunable.len(), 64);
        assert_eq!(prunable.pruned_chunks(), 1);

        // Add more data
        prunable.push_chunk(&[9, 10, 11, 12]);
        assert_eq!(prunable.len(), 96); // 32 pruned + 64 active

        // New chunk should be accessible
        assert_eq!(prunable.get_chunk_containing(64), &[9, 10, 11, 12]);
    }

    #[test]
    fn test_chunk_calculations() {
        // Test chunk_num calculation
        assert_eq!(Prunable::<4>::to_chunk_index(0), 0);
        assert_eq!(Prunable::<4>::to_chunk_index(31), 0);
        assert_eq!(Prunable::<4>::to_chunk_index(32), 1);
        assert_eq!(Prunable::<4>::to_chunk_index(63), 1);
        assert_eq!(Prunable::<4>::to_chunk_index(64), 2);

        // Test chunk_byte_offset
        assert_eq!(Prunable::<4>::chunk_byte_offset(0), 0);
        assert_eq!(Prunable::<4>::chunk_byte_offset(8), 1);
        assert_eq!(Prunable::<4>::chunk_byte_offset(16), 2);
        assert_eq!(Prunable::<4>::chunk_byte_offset(24), 3);
        assert_eq!(Prunable::<4>::chunk_byte_offset(32), 0); // Wraps to next chunk

        // Test chunk_byte_bitmask
        assert_eq!(Prunable::<4>::chunk_byte_bitmask(0), 0b00000001);
        assert_eq!(Prunable::<4>::chunk_byte_bitmask(1), 0b00000010);
        assert_eq!(Prunable::<4>::chunk_byte_bitmask(7), 0b10000000);
        assert_eq!(Prunable::<4>::chunk_byte_bitmask(8), 0b00000001); // Next byte
    }

    #[test]
    fn test_last_chunk_with_pruning() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Add chunks
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);
        prunable.push(true);
        prunable.push(false);

        let (_, next_bit) = prunable.last_chunk();
        assert_eq!(next_bit, 2);

        // Store the chunk data for comparison
        let chunk_data = *prunable.last_chunk().0;

        // Pruning shouldn't affect last_chunk
        prunable.prune_to_bit(32);
        let (chunk2, next_bit2) = prunable.last_chunk();
        assert_eq!(next_bit2, 2);
        assert_eq!(&chunk_data, chunk2);
    }

    #[test]
    fn test_different_chunk_sizes() {
        // Test with different chunk sizes
        let mut p8: Prunable<8> = Prunable::new();
        let mut p16: Prunable<16> = Prunable::new();
        let mut p32: Prunable<32> = Prunable::new();

        // Add same pattern to each
        for i in 0..10 {
            p8.push(i % 2 == 0);
            p16.push(i % 2 == 0);
            p32.push(i % 2 == 0);
        }

        // All should have same bit count
        assert_eq!(p8.len(), 10);
        assert_eq!(p16.len(), 10);
        assert_eq!(p32.len(), 10);

        // All should have same bit values
        for i in 0..10 {
            let expected = i % 2 == 0;
            if expected {
                assert!(p8.get_bit(i));
                assert!(p16.get_bit(i));
                assert!(p32.get_bit(i));
            } else {
                assert!(!p8.get_bit(i));
                assert!(!p16.get_bit(i));
                assert!(!p32.get_bit(i));
            }
        }
    }

    #[test]
    fn test_get_bit_from_chunk() {
        let chunk: [u8; 4] = [0b10101010, 0b11001100, 0b11110000, 0b00001111];

        // Test first byte
        assert!(!Prunable::<4>::get_bit_from_chunk(&chunk, 0));
        assert!(Prunable::<4>::get_bit_from_chunk(&chunk, 1));
        assert!(!Prunable::<4>::get_bit_from_chunk(&chunk, 2));
        assert!(Prunable::<4>::get_bit_from_chunk(&chunk, 3));

        // Test second byte
        assert!(!Prunable::<4>::get_bit_from_chunk(&chunk, 8));
        assert!(!Prunable::<4>::get_bit_from_chunk(&chunk, 9));
        assert!(Prunable::<4>::get_bit_from_chunk(&chunk, 10));
        assert!(Prunable::<4>::get_bit_from_chunk(&chunk, 11));
    }

    #[test]
    fn test_get_chunk() {
        let mut prunable: Prunable<4> = Prunable::new();
        let chunk1 = hex!("0x11223344");
        let chunk2 = hex!("0x55667788");
        let chunk3 = hex!("0x99AABBCC");

        prunable.push_chunk(&chunk1);
        prunable.push_chunk(&chunk2);
        prunable.push_chunk(&chunk3);

        // Before pruning
        assert_eq!(prunable.get_chunk(0), &chunk1);
        assert_eq!(prunable.get_chunk(1), &chunk2);
        assert_eq!(prunable.get_chunk(2), &chunk3);

        // After pruning
        prunable.prune_to_bit(32);
        assert_eq!(prunable.get_chunk(1), &chunk2);
        assert_eq!(prunable.get_chunk(2), &chunk3);
    }

    #[test]
    fn test_pop() {
        let mut prunable: Prunable<4> = Prunable::new();

        prunable.push(true);
        prunable.push(false);
        prunable.push(true);
        assert_eq!(prunable.len(), 3);

        assert!(prunable.pop());
        assert_eq!(prunable.len(), 2);

        assert!(!prunable.pop());
        assert_eq!(prunable.len(), 1);

        assert!(prunable.pop());
        assert_eq!(prunable.len(), 0);
        assert!(prunable.is_empty());

        for i in 0..100 {
            prunable.push(i % 3 == 0);
        }
        assert_eq!(prunable.len(), 100);

        for i in (0..100).rev() {
            let expected = i % 3 == 0;
            assert_eq!(prunable.pop(), expected);
            assert_eq!(prunable.len(), i);
        }

        assert!(prunable.is_empty());
    }

    #[test]
    fn test_truncate() {
        let mut prunable: Prunable<4> = Prunable::new();
        let expected: Vec<bool> = (0..96).map(|i| i % 3 == 0).collect();
        for &bit in &expected {
            prunable.push(bit);
        }

        prunable.truncate(65);
        assert_eq!(prunable.len(), 65);
        for i in 0..65 {
            assert_eq!(prunable.get_bit(i), expected[i as usize]);
        }

        prunable.prune_to_bit(32);
        assert_eq!(prunable.pruned_bits(), 32);

        prunable.truncate(64);
        assert_eq!(prunable.len(), 64);
        for i in 32..64 {
            assert_eq!(prunable.get_bit(i), expected[i as usize]);
        }
    }

    #[test]
    #[should_panic(expected = "cannot truncate into pruned region")]
    fn test_truncate_into_pruned_region_panics() {
        let mut prunable: Prunable<4> = Prunable::new();
        prunable.push_chunk(&[0xFF; 4]);
        prunable.push_chunk(&[0xFF; 4]);
        prunable.prune_to_bit(32);
        prunable.truncate(31);
    }

    #[test]
    fn test_pop_chunk() {
        let mut prunable: Prunable<4> = Prunable::new();
        const CHUNK_SIZE: u64 = Prunable::<4>::CHUNK_SIZE_BITS;

        // Test 1: Pop a single chunk and verify it returns the correct data
        let chunk1 = hex!("0xAABBCCDD");
        prunable.push_chunk(&chunk1);
        assert_eq!(prunable.len(), CHUNK_SIZE);
        let popped = prunable.pop_chunk();
        assert_eq!(popped, chunk1);
        assert_eq!(prunable.len(), 0);
        assert!(prunable.is_empty());

        // Test 2: Pop multiple chunks in reverse order
        let chunk2 = hex!("0x11223344");
        let chunk3 = hex!("0x55667788");
        let chunk4 = hex!("0x99AABBCC");

        prunable.push_chunk(&chunk2);
        prunable.push_chunk(&chunk3);
        prunable.push_chunk(&chunk4);
        assert_eq!(prunable.len(), CHUNK_SIZE * 3);

        assert_eq!(prunable.pop_chunk(), chunk4);
        assert_eq!(prunable.len(), CHUNK_SIZE * 2);

        assert_eq!(prunable.pop_chunk(), chunk3);
        assert_eq!(prunable.len(), CHUNK_SIZE);

        assert_eq!(prunable.pop_chunk(), chunk2);
        assert_eq!(prunable.len(), 0);

        // Test 3: Verify data integrity when popping chunks
        prunable = Prunable::new();
        let first_chunk = hex!("0xAABBCCDD");
        let second_chunk = hex!("0x11223344");
        prunable.push_chunk(&first_chunk);
        prunable.push_chunk(&second_chunk);

        // Pop the second chunk, verify it and that first chunk is intact
        assert_eq!(prunable.pop_chunk(), second_chunk);
        assert_eq!(prunable.len(), CHUNK_SIZE);

        for i in 0..CHUNK_SIZE {
            let byte_idx = (i / 8) as usize;
            let bit_idx = i % 8;
            let expected = (first_chunk[byte_idx] >> bit_idx) & 1 == 1;
            assert_eq!(prunable.get_bit(i), expected);
        }

        assert_eq!(prunable.pop_chunk(), first_chunk);
        assert_eq!(prunable.len(), 0);
    }

    #[test]
    #[should_panic(expected = "cannot pop chunk when not chunk aligned")]
    fn test_pop_chunk_not_aligned() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Push a full chunk plus one bit
        prunable.push_chunk(&[0xFF; 4]);
        prunable.push(true);

        // Should panic because not chunk-aligned
        prunable.pop_chunk();
    }

    #[test]
    #[should_panic(expected = "cannot pop chunk: bitmap has fewer than CHUNK_SIZE_BITS bits")]
    fn test_pop_chunk_insufficient_bits() {
        let mut prunable: Prunable<4> = Prunable::new();

        // Push only a few bits (less than a full chunk)
        prunable.push(true);
        prunable.push(false);

        // Should panic because we don't have a full chunk to pop
        prunable.pop_chunk();
    }

    #[test]
    fn test_write_read_empty() {
        let original: Prunable<4> = Prunable::new();
        let mut encoded = original.encode();

        let decoded = Prunable::<4>::read_cfg(&mut encoded, &(..).into()).unwrap();
        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded.pruned_chunks(), original.pruned_chunks());
        assert!(decoded.is_empty());
    }

    #[test]
    fn test_write_read_non_empty() {
        let mut original: Prunable<4> = Prunable::new();
        original.push_chunk(&hex!("0xAABBCCDD"));
        original.push_chunk(&hex!("0x11223344"));
        original.push(true);
        original.push(false);
        original.push(true);

        let mut encoded = original.encode();
        let decoded = Prunable::<4>::read_cfg(&mut encoded, &(..).into()).unwrap();

        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded.pruned_chunks(), original.pruned_chunks());
        assert_eq!(decoded.len(), 67);

        // Verify all bits match
        for i in 0..original.len() {
            assert_eq!(decoded.get_bit(i), original.get_bit(i));
        }
    }

    #[test]
    fn test_write_read_with_pruning() {
        let mut original: Prunable<4> = Prunable::new();
        original.push_chunk(&hex!("0x01020304"));
        original.push_chunk(&hex!("0x05060708"));
        original.push_chunk(&hex!("0x090A0B0C"));

        // Prune first chunk
        original.prune_to_bit(32);
        assert_eq!(original.pruned_chunks(), 1);
        assert_eq!(original.len(), 96);

        let mut encoded = original.encode();
        let decoded = Prunable::<4>::read_cfg(&mut encoded, &(..).into()).unwrap();

        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded.pruned_chunks(), original.pruned_chunks());
        assert_eq!(decoded.pruned_chunks(), 1);
        assert_eq!(decoded.len(), 96);

        // Verify remaining chunks match
        assert_eq!(decoded.get_chunk_containing(32), &hex!("0x05060708"));
        assert_eq!(decoded.get_chunk_containing(64), &hex!("0x090A0B0C"));
    }

    #[test]
    fn test_write_read_with_pruning_2() {
        let mut original: Prunable<4> = Prunable::new();

        // Add several chunks
        for i in 0..5 {
            let chunk = [
                (i * 4) as u8,
                (i * 4 + 1) as u8,
                (i * 4 + 2) as u8,
                (i * 4 + 3) as u8,
            ];
            original.push_chunk(&chunk);
        }

        // Keep only last two chunks
        original.prune_to_bit(96); // Prune first 3 chunks
        assert_eq!(original.pruned_chunks(), 3);
        assert_eq!(original.len(), 160);

        let mut encoded = original.encode();
        let decoded = Prunable::<4>::read_cfg(&mut encoded, &(..).into()).unwrap();

        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded.pruned_chunks(), 3);

        // Verify remaining accessible bits match
        for i in 96..original.len() {
            assert_eq!(decoded.get_bit(i), original.get_bit(i));
        }
    }

    #[test]
    fn test_encode_size_matches() {
        let mut prunable: Prunable<4> = Prunable::new();
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);
        prunable.push(true);

        let size = prunable.encode_size();
        let encoded = prunable.encode();

        assert_eq!(size, encoded.len());
    }

    #[test]
    fn test_encode_size_with_pruning() {
        let mut prunable: Prunable<4> = Prunable::new();
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);
        prunable.push_chunk(&[9, 10, 11, 12]);

        prunable.prune_to_bit(32);

        let size = prunable.encode_size();
        let encoded = prunable.encode();

        assert_eq!(size, encoded.len());
    }

    #[test]
    fn test_read_max_len_validation() {
        let mut original: Prunable<4> = Prunable::new();
        for _ in 0..10 {
            original.push(true);
        }

        let mut encoded = original.encode();

        // Should succeed with sufficient max_len
        assert!(Prunable::<4>::read_cfg(&mut encoded.clone(), &(..=100).into()).is_ok());

        // Should fail with insufficient max_len
        let result = Prunable::<4>::read_cfg(&mut encoded, &(..=5).into());
        assert!(result.is_err());
    }

    #[test]
    fn test_read_range_bounds_retained_bits() {
        // 100 bits with the first two chunks (64 bits) pruned leaves 36 retained bits.
        let mut original: Prunable<4> = Prunable::new();
        for i in 0..100 {
            original.push(i % 3 == 0);
        }
        original.prune_to_bit(64);
        let mut encoded = original.encode();

        let decoded = Prunable::<4>::read_cfg(&mut encoded.clone(), &RangeCfg::exact(36)).unwrap();
        assert_eq!(decoded.len(), 100);
        assert_eq!(decoded.pruned_bits(), 64);
        let result = Prunable::<4>::read_cfg(&mut encoded.clone(), &RangeCfg::exact(100));
        assert!(matches!(result, Err(CodecError::InvalidLength(36))));
        let result = Prunable::<4>::read_cfg(&mut encoded, &(37..).into());
        assert!(matches!(result, Err(CodecError::InvalidLength(36))));

        // Pruning every chunk leaves zero retained bits.
        let mut original: Prunable<4> = Prunable::new();
        for _ in 0..96 {
            original.push(true);
        }
        original.prune_to_bit(96);
        let mut encoded = original.encode();
        let decoded = Prunable::<4>::read_cfg(&mut encoded, &RangeCfg::exact(0)).unwrap();
        assert_eq!(decoded.len(), 96);
        assert_eq!(decoded.pruned_bits(), 96);
    }

    #[test]
    fn test_codec_roundtrip_different_chunk_sizes() {
        // Test with different chunk sizes
        let mut p8: Prunable<8> = Prunable::new();
        let mut p16: Prunable<16> = Prunable::new();
        let mut p32: Prunable<32> = Prunable::new();

        for i in 0..100 {
            let bit = i % 3 == 0;
            p8.push(bit);
            p16.push(bit);
            p32.push(bit);
        }

        // Roundtrip each
        let mut encoded8 = p8.encode();
        let decoded8 = Prunable::<8>::read_cfg(&mut encoded8, &(..).into()).unwrap();
        assert_eq!(decoded8.len(), p8.len());

        let mut encoded16 = p16.encode();
        let decoded16 = Prunable::<16>::read_cfg(&mut encoded16, &(..).into()).unwrap();
        assert_eq!(decoded16.len(), p16.len());

        let mut encoded32 = p32.encode();
        let decoded32 = Prunable::<32>::read_cfg(&mut encoded32, &(..).into()).unwrap();
        assert_eq!(decoded32.len(), p32.len());
    }

    #[test]
    fn test_read_pruned_chunks_overflow() {
        let mut buf = BytesMut::new();

        // Write a pruned_chunks value that would overflow when multiplied by CHUNK_SIZE_BITS
        let overflowing_pruned_chunks = (u64::MAX / Prunable::<4>::CHUNK_SIZE_BITS) + 1;
        overflowing_pruned_chunks.write(&mut buf);

        // Write a valid bitmap (empty)
        0u64.write(&mut buf); // len = 0

        // Try to read - should fail with overflow error
        let result = Prunable::<4>::read_cfg(&mut buf, &(..).into());
        match result {
            Err(CodecError::Invalid(type_name, msg)) => {
                assert_eq!(type_name, "Prunable");
                assert_eq!(
                    msg,
                    "pruned_chunks would overflow when computing pruned_bits"
                );
            }
            Ok(_) => panic!("Expected error but got Ok"),
            Err(e) => panic!("Expected Invalid error for pruned_bits overflow, got: {e:?}"),
        }
    }

    #[test]
    fn test_read_total_length_overflow() {
        let mut buf = BytesMut::new();

        // Make pruned_bits as large as possible without overflowing
        let max_safe_pruned_chunks = u64::MAX / Prunable::<4>::CHUNK_SIZE_BITS;
        let pruned_bits = max_safe_pruned_chunks * Prunable::<4>::CHUNK_SIZE_BITS;

        // Make bitmap_len large enough that adding it overflows
        let remaining_space = u64::MAX - pruned_bits;
        let bitmap_len = remaining_space + 1; // Go over by 1 to trigger overflow

        // Write the serialized data
        max_safe_pruned_chunks.write(&mut buf);
        bitmap_len.write(&mut buf);

        // Write bitmap chunk data
        let num_chunks = bitmap_len.div_ceil(Prunable::<4>::CHUNK_SIZE_BITS);
        for _ in 0..(num_chunks * 4) {
            0u8.write(&mut buf);
        }

        // Try to read - should fail because pruned_bits + bitmap_len overflows u64
        let result = Prunable::<4>::read_cfg(&mut buf, &(..).into());
        match result {
            Err(CodecError::Invalid(type_name, msg)) => {
                assert_eq!(type_name, "Prunable");
                assert_eq!(
                    msg,
                    "total bitmap length (pruned + unpruned) would overflow u64"
                );
            }
            Ok(_) => panic!("Expected error but got Ok"),
            Err(e) => panic!("Expected Invalid error for total length overflow, got: {e:?}"),
        }
    }

    #[test]
    fn test_is_chunk_aligned() {
        // Empty bitmap is chunk aligned
        let prunable: Prunable<4> = Prunable::new();
        assert!(prunable.is_chunk_aligned());

        // Add bits one at a time and check alignment
        let mut prunable: Prunable<4> = Prunable::new();
        for i in 1..=32 {
            prunable.push(i % 2 == 0);
            if i == 32 {
                assert!(prunable.is_chunk_aligned()); // Exactly one chunk
            } else {
                assert!(!prunable.is_chunk_aligned()); // Partial chunk
            }
        }

        // Add another full chunk
        for i in 33..=64 {
            prunable.push(i % 2 == 0);
            if i == 64 {
                assert!(prunable.is_chunk_aligned()); // Exactly two chunks
            } else {
                assert!(!prunable.is_chunk_aligned()); // Partial chunk
            }
        }

        // Test with push_chunk
        let mut prunable: Prunable<4> = Prunable::new();
        assert!(prunable.is_chunk_aligned());
        prunable.push_chunk(&[1, 2, 3, 4]);
        assert!(prunable.is_chunk_aligned()); // 32 bits = 1 chunk
        prunable.push_chunk(&[5, 6, 7, 8]);
        assert!(prunable.is_chunk_aligned()); // 64 bits = 2 chunks
        prunable.push(true);
        assert!(!prunable.is_chunk_aligned()); // 65 bits = partial chunk

        // Test alignment with pruning
        let mut prunable: Prunable<4> = Prunable::new();
        prunable.push_chunk(&[1, 2, 3, 4]);
        prunable.push_chunk(&[5, 6, 7, 8]);
        prunable.push_chunk(&[9, 10, 11, 12]);
        assert!(prunable.is_chunk_aligned()); // 96 bits = 3 chunks

        // Prune first chunk - still aligned (64 bits remaining)
        prunable.prune_to_bit(32);
        assert!(prunable.is_chunk_aligned());
        assert_eq!(prunable.len(), 96);

        // Add a partial chunk
        prunable.push(true);
        prunable.push(false);
        assert!(!prunable.is_chunk_aligned()); // 98 bits total

        // Prune to align again
        prunable.prune_to_bit(64);
        assert!(!prunable.is_chunk_aligned()); // 98 bits total (34 bits remaining)

        // Test with new_with_pruned_chunks
        let prunable: Prunable<4> = Prunable::new_with_pruned_chunks(2).unwrap();
        assert!(prunable.is_chunk_aligned()); // 64 bits pruned, 0 bits in bitmap

        let mut prunable: Prunable<4> = Prunable::new_with_pruned_chunks(1).unwrap();
        assert!(prunable.is_chunk_aligned()); // 32 bits pruned, 0 bits in bitmap
        prunable.push(true);
        assert!(!prunable.is_chunk_aligned()); // 33 bits total

        // Test with push_byte
        let mut prunable: Prunable<4> = Prunable::new();
        for _ in 0..4 {
            prunable.push_byte(0xFF);
        }
        assert!(prunable.is_chunk_aligned()); // 32 bits = 1 chunk

        // Test after pop
        prunable.pop();
        assert!(!prunable.is_chunk_aligned()); // 31 bits

        // Pop back to alignment
        for _ in 0..31 {
            prunable.pop();
        }
        assert!(prunable.is_chunk_aligned()); // 0 bits
    }

    /// Compare the first bit `ones_iter_range` yields with a bit-by-bit scan for ranges over a
    /// bitmap of `N`-byte chunks, with and without a pruned chunk.
    fn check_ones_iter_ranges<const N: usize>() {
        let len = 3 * Prunable::<N>::CHUNK_SIZE_BITS + 3;
        for stride in [1, 7, 63, 65, len + 1] {
            let mut bitmap = Prunable::<N>::new();
            bitmap.extend_to(len);
            for bit in (0..len).filter(|bit| bit % stride == 0) {
                bitmap.set_bit(bit, true);
            }
            for pruned in [false, true] {
                if pruned {
                    bitmap.prune_to_bit(Prunable::<N>::CHUNK_SIZE_BITS);
                }

                // Wide chunks sample range bounds beside byte boundaries to bound the runtime.
                for from in (0..=len + 1).filter(|bit| N <= 9 || bit % 8 <= 1 || bit % 8 == 7) {
                    for end in (from..=len + 1).filter(|bit| N <= 9 || bit % 8 <= 1 || bit % 8 == 7)
                    {
                        let expected = (from.max(bitmap.pruned_bits())..end.min(len))
                            .find(|&bit| bitmap.get_bit(bit));
                        assert_eq!(
                            bitmap.ones_iter_range(from..end).next(),
                            expected,
                            "N={N}, {from}..{end}"
                        );
                    }
                    assert_eq!(
                        bitmap.ones_iter_range(from..u64::MAX).next(),
                        (from.max(bitmap.pruned_bits())..len).find(|&bit| bitmap.get_bit(bit))
                    );
                }
            }
        }
    }

    /// [`check_ones_iter_ranges`] for chunks narrower than, equal to, and wider than eight bytes.
    #[test]
    fn test_ones_iter_range_matches_bit_scan() {
        check_ones_iter_ranges::<1>();
        check_ones_iter_ranges::<7>();
        check_ones_iter_ranges::<8>();
        check_ones_iter_ranges::<9>();
        check_ones_iter_ranges::<32>();
        check_ones_iter_ranges::<64>();
    }

    /// Ranges ending at or just below `u64::MAX` stop at their end without overflowing.
    #[test]
    fn test_ones_iter_range_near_max() {
        let mut bitmap = Prunable::<8>::new_with_pruned_chunks((u64::MAX / 64) as usize).unwrap();
        let from = bitmap.pruned_bits();
        bitmap.extend_to(u64::MAX);
        assert_eq!(bitmap.ones_iter_range(from..u64::MAX).next(), None);
        bitmap.set_bit(u64::MAX - 1, true);
        assert_eq!(bitmap.ones_iter_range(from..u64::MAX - 1).next(), None);
        assert_eq!(
            bitmap.ones_iter_range(from..u64::MAX).next(),
            Some(u64::MAX - 1)
        );
    }

    #[test]
    fn test_ones_iter_with_pruning() {
        // 3 chunks of 32 bits each = 96 bits total.
        let mut p = Prunable::<4>::new();
        for _ in 0..96 {
            p.push(false);
        }
        // Set bits in chunks 1 and 2 (absolute indices 40, 55, 64, 90).
        p.set_bit(40, true);
        p.set_bit(55, true);
        p.set_bit(64, true);
        p.set_bit(90, true);

        // Prune first chunk (32 bits).
        p.prune_to_bit(32);
        assert_eq!(p.pruned_chunks(), 1);
        assert_eq!(p.pruned_bits(), 32);

        let ones: Vec<u64> = Readable::ones_iter_from(&p, p.pruned_bits()).collect();
        assert_eq!(ones, vec![40, 55, 64, 90]);
    }

    #[test]
    fn test_ones_iter_pruned_bits_near_max() {
        // The largest pruned offset accepted for 8-byte chunks places pruned_bits at
        // u64::MAX - 63, so word advances near the top of the range must not wrap.
        const PRUNED_CHUNKS: usize = (u64::MAX / 64) as usize;

        // Fully pruned and empty: iteration is exhausted at construction.
        let p = Prunable::<8>::new_with_pruned_chunks(PRUNED_CHUNKS).unwrap();
        assert_eq!(p.len(), u64::MAX - 63);
        assert!(Readable::ones_iter_from(&p, 0).next().is_none());

        // Bits in the last representable chunk: iteration must terminate after them.
        let mut p = Prunable::<8>::new_with_pruned_chunks(PRUNED_CHUNKS).unwrap();
        let start = p.pruned_bits();
        for i in 0..32 {
            p.push(i == 0 || i == 31);
        }
        let ones: Vec<u64> = Readable::ones_iter_from(&p, 0).collect();
        assert_eq!(ones, vec![start, start + 31]);
    }

    #[test]
    fn test_ones_iter_from_midway_with_pruning() {
        let mut p = Prunable::<4>::new();
        for _ in 0..96 {
            p.push(false);
        }
        p.set_bit(40, true);
        p.set_bit(55, true);
        p.set_bit(64, true);
        p.set_bit(90, true);

        p.prune_to_bit(32);

        // Start past the first set bit in the unpruned region.
        let ones: Vec<u64> = Readable::ones_iter_from(&p, 50).collect();
        assert_eq!(ones, vec![55, 64, 90]);

        // Start past all set bits.
        let ones: Vec<u64> = Readable::ones_iter_from(&p, 91).collect();
        assert!(ones.is_empty());
    }

    #[test]
    fn test_ones_iter_all_ones_with_pruning() {
        let mut p = Prunable::<4>::new();
        for _ in 0..96 {
            p.push(true);
        }

        // Prune 2 chunks (64 bits).
        p.prune_to_bit(64);
        assert_eq!(p.pruned_chunks(), 2);

        let ones: Vec<u64> = Readable::ones_iter_from(&p, p.pruned_bits()).collect();
        let expected: Vec<u64> = (64..96).collect();
        assert_eq!(ones, expected);
    }

    #[test]
    fn test_ones_iter_empty_after_pruning() {
        let mut p = Prunable::<4>::new();
        for _ in 0..64 {
            p.push(false);
        }

        // Prune first chunk, leaving 32 zero bits.
        p.prune_to_bit(32);
        assert_eq!(p.pruned_chunks(), 1);

        let ones: Vec<u64> = Readable::ones_iter_from(&p, p.pruned_bits()).collect();
        assert!(ones.is_empty());
    }

    #[test]
    fn test_ones_iter_from_pruned_region_fast_forwards() {
        let mut p = Prunable::<4>::new();
        for _ in 0..64 {
            p.push(true);
        }
        p.prune_to_bit(32);

        // Starting in the pruned region fast-forwards past it.
        let ones: Vec<u64> = Readable::ones_iter_from(&p, 0).collect();
        let expected: Vec<u64> = (32..64).collect();
        assert_eq!(ones, expected);
    }

    #[test]
    fn test_extend_to() {
        let mut p = Prunable::<4>::new();
        for i in 0..30u64 {
            p.push(i % 2 == 0);
        }

        // No-op when target is smaller.
        p.extend_to(5);
        assert_eq!(p.len(), 30);

        // Extends across a chunk boundary, new bits are zero.
        p.extend_to(65);
        assert_eq!(p.len(), 65);
        for i in 0..30 {
            assert_eq!(p.get_bit(i), i % 2 == 0, "original bit {i}");
        }
        for i in 30..65 {
            assert!(!p.get_bit(i), "extended bit {i} should be false");
        }

        // Works correctly with a pruned prefix.
        p.prune_to_bit(32);
        p.extend_to(100);
        assert_eq!(p.len(), 100);
        assert_eq!(p.pruned_bits(), 32);
        for i in 65..100 {
            assert!(!p.get_bit(i), "extended bit {i} should be false");
        }
    }

    // set_chunk_by_index must reject non-zero bits beyond len() in the last partial chunk.

    #[test]
    fn test_set_chunk_by_index_accepts_valid_partial_chunk() {
        let mut p = Prunable::<4>::new();
        p.extend_to(35); // 1 full chunk + 3 bits in chunk 1
        // Only the low 3 bits of byte 0 are valid; rest must be zero.
        p.set_chunk_by_index(1, &[0b0000_0111, 0, 0, 0]);
        assert_eq!(p.get_chunk(1), &[0b0000_0111, 0, 0, 0]);
    }

    #[test]
    fn test_set_chunk_by_index_accepts_full_chunk() {
        let mut p = Prunable::<4>::new();
        p.extend_to(64); // 2 full chunks
        // Full chunk: any byte pattern is valid.
        p.set_chunk_by_index(1, &[0xFF; 4]);
        assert_eq!(p.get_chunk(1), &[0xFF; 4]);
    }

    #[test]
    #[should_panic(expected = "non-zero bits beyond bitmap length")]
    fn test_set_chunk_by_index_rejects_high_bits_in_last_byte() {
        let mut p = Prunable::<4>::new();
        p.extend_to(35); // 3 valid bits in chunk 1
        // Bit 3 (0b0000_1000) is beyond len.
        p.set_chunk_by_index(1, &[0b0000_1000, 0, 0, 0]);
    }

    #[test]
    #[should_panic(expected = "non-zero bits beyond bitmap length")]
    fn test_set_chunk_by_index_rejects_nonzero_trailing_bytes() {
        let mut p = Prunable::<4>::new();
        p.extend_to(35); // 3 valid bits in chunk 1
        // Byte 1 is entirely beyond len.
        p.set_chunk_by_index(1, &[0, 0xFF, 0, 0]);
    }

    #[test]
    #[should_panic(expected = "non-zero bits beyond bitmap length")]
    fn test_set_chunk_by_index_rejects_nonzero_final_byte() {
        let mut p = Prunable::<4>::new();
        p.extend_to(35); // 3 valid bits in chunk 1
        p.set_chunk_by_index(1, &[0, 0, 0, 1]);
    }

    #[test]
    fn test_set_chunk_by_index_roundtrips_codec() {
        let mut p = Prunable::<4>::new();
        p.extend_to(35);
        p.set_chunk_by_index(1, &[0b0000_0101, 0, 0, 0]);

        let mut encoded = p.encode();
        let decoded = Prunable::<4>::read_cfg(&mut encoded, &(..).into())
            .expect("valid chunk should round-trip");
        assert_eq!(decoded.len(), 35);
        assert_eq!(decoded.get_chunk(1), &[0b0000_0101, 0, 0, 0]);
    }

    #[cfg(feature = "arbitrary")]
    mod conformance {
        use super::*;
        use commonware_codec::conformance::CodecConformance;

        commonware_conformance::conformance_tests! {
            CodecConformance<Prunable<16>>,
        }
    }
}