bitvec 1.0.1

#![cfg(feature = "alloc")]
#![doc = include_str!("../doc/boxed.md")]

use alloc::boxed::Box;
use core::{
	mem::ManuallyDrop,
	slice,
};

use tap::{
	Pipe,
	Tap,
};
use wyz::comu::Mut;

use crate::{
	index::BitIdx,
	mem,
	order::{
		BitOrder,
		Lsb0,
	},
	ptr::{
		BitPtr,
		BitSpan,
	},
	slice::BitSlice,
	store::BitStore,
	vec::BitVec,
	view::BitView,
};

mod api;
mod iter;
mod ops;
mod tests;
mod traits;

pub use self::iter::IntoIter;

#[repr(transparent)]
#[doc = include_str!("../doc/boxed/BitBox.md")]
pub struct BitBox<T = usize, O = Lsb0>
where
	T: BitStore,
	O: BitOrder,
{
	/// Describes the region that the box owns.
	bitspan: BitSpan<Mut, T, O>,
}

impl<T, O> BitBox<T, O>
where
	T: BitStore,
	O: BitOrder,
{
	/// Copies a bit-slice region into a new bit-box allocation.
	///
	/// The referent memory is `memcpy`d into the heap, exactly preserving the
	/// original bit-slice’s memory layout and contents. This allows the
	/// function to run as fast as possible, but misaligned source bit-slices
	/// may result in decreased performance or unexpected layout behavior during
	/// use. You can use [`.force_align()`] to ensure that the referent
	/// bit-slice is aligned in memory.
	///
	/// ## Notes
	///
	/// Bits in the allocation of the source bit-slice, but outside its own
	/// description of that memory, have an **unspecified**, but initialized,
	/// value. You may not rely on their contents in any way, and you *should*
	/// call [`.force_align()`] and/or [`.fill_uninitialized()`] if you are
	/// going to inspect the underlying memory of the new allocation.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let data = 0b0101_1011u8;
	/// let bits = data.view_bits::<Msb0>();
	/// let bb = BitBox::from_bitslice(&bits[2 ..]);
	/// assert_eq!(bb, bits[2 ..]);
	/// ```
	///
	/// [`.fill_uninitialized()`]: Self::fill_uninitialized
	/// [`.force_align()`]: Self::force_align
	#[inline]
	pub fn from_bitslice(slice: &BitSlice<T, O>) -> Self {
		BitVec::from_bitslice(slice).into_boxed_bitslice()
	}

	/// Converts a `Box<[T]>` into a `BitBox<T, O>`, in place.
	///
	/// This does not affect the referent buffer, and only transforms the
	/// handle.
	///
	/// ## Panics
	///
	/// This panics if the provided `boxed` slice is too long to view as a
	/// bit-slice region.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let boxed: Box<[u8]> = Box::new([0; 40]);
	/// let addr = boxed.as_ptr();
	/// let bb = BitBox::<u8>::from_boxed_slice(boxed);
	/// assert_eq!(bb, bits![0; 320]);
	/// assert_eq!(addr, bb.as_raw_slice().as_ptr());
	/// ```
	#[inline]
	pub fn from_boxed_slice(boxed: Box<[T]>) -> Self {
		Self::try_from_boxed_slice(boxed)
			.expect("slice was too long to be converted into a `BitBox`")
	}

	/// Attempts to convert an ordinary boxed slice into a boxed bit-slice.
	///
	/// This does not perform a copy or reällocation; it only attempts to
	/// transform the handle. Because `Box<[T]>` can be longer than `BitBox`es,
	/// it may fail, and will return the original handle if it does.
	///
	/// It is unlikely that you have a single `Box<[_]>` that is too large to
	/// convert into a bit-box. You can find the length restrictions as the
	/// bit-slice associated constants [`MAX_BITS`] and [`MAX_ELTS`].
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let boxed: Box<[u8]> = Box::new([0u8; 40]);
	/// let addr = boxed.as_ptr();
	/// let bb = BitBox::<u8>::try_from_boxed_slice(boxed).unwrap();
	/// assert_eq!(bb, bits![0; 320]);
	/// assert_eq!(addr, bb.as_raw_slice().as_ptr());
	/// ```
	///
	/// [`MAX_BITS`]: crate::slice::BitSlice::MAX_BITS
	/// [`MAX_ELTS`]: crate::slice::BitSlice::MAX_ELTS
	#[inline]
	pub fn try_from_boxed_slice(boxed: Box<[T]>) -> Result<Self, Box<[T]>> {
		let mut boxed = ManuallyDrop::new(boxed);

		BitPtr::from_mut_slice(boxed.as_mut())
			.span(boxed.len() * mem::bits_of::<T::Mem>())
			.map(|bitspan| Self { bitspan })
			.map_err(|_| ManuallyDrop::into_inner(boxed))
	}

	/// Converts the bit-box back into an ordinary boxed element slice.
	///
	/// This does not touch the allocator or the buffer contents; it is purely a
	/// handle transform.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bb = bitbox![0; 5];
	/// let addr = bb.as_raw_slice().as_ptr();
	/// let boxed = bb.into_boxed_slice();
	/// assert_eq!(boxed[..], [0][..]);
	/// assert_eq!(addr, boxed.as_ptr());
	/// ```
	#[inline]
	pub fn into_boxed_slice(self) -> Box<[T]> {
		self.pipe(ManuallyDrop::new)
			.as_raw_mut_slice()
			.pipe(|slice| unsafe { Box::from_raw(slice) })
	}

	/// Converts the bit-box into a bit-vector.
	///
	/// This uses the Rust allocator API, and does not guarantee whether or not
	/// a reällocation occurs internally.
	///
	/// The resulting bit-vector can be converted back into a bit-box via
	/// [`BitBox::into_boxed_bitslice`][0].
	///
	/// ## Original
	///
	/// [`slice::into_vec`](https://doc.rust-lang.org/std/primitive.slice.html#method.into_vec)
	///
	/// ## API Differences
	///
	/// The original function is implemented in an `impl<T> [T]` block, despite
	/// taking a `Box<[T]>` receiver. Since `BitBox` cannot be used as an
	/// explicit receiver outside its own `impl` blocks, the method is relocated
	/// here.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bb = bitbox![0, 1, 0, 0, 1];
	/// let bv = bb.into_bitvec();
	///
	/// assert_eq!(bv, bitvec![0, 1, 0, 0, 1]);
	/// ```
	///
	/// [0]: crate::vec::BitVec::into_boxed_bitslice
	#[inline]
	pub fn into_bitvec(self) -> BitVec<T, O> {
		let bitspan = self.bitspan;
		/* This pipeline converts the underlying `Box<[T]>` into a `Vec<T>`,
		 * then converts that into a `BitVec`. This handles any changes that
		 * may occur in the allocator. Once done, the original head/span
		 * values need to be written into the `BitVec`, since the conversion
		 * from `Vec` always fully spans the live elements.
		 */
		self.pipe(ManuallyDrop::new)
			.with_box(|b| unsafe { ManuallyDrop::take(b) })
			.into_vec()
			.pipe(BitVec::from_vec)
			.tap_mut(|bv| unsafe {
				// len first! Otherwise, the descriptor might briefly go out of
				// bounds.
				bv.set_len_unchecked(bitspan.len());
				bv.set_head(bitspan.head());
			})
	}

	/// Explicitly views the bit-box as a bit-slice.
	#[inline]
	pub fn as_bitslice(&self) -> &BitSlice<T, O> {
		unsafe { self.bitspan.into_bitslice_ref() }
	}

	/// Explicitly views the bit-box as a mutable bit-slice.
	#[inline]
	pub fn as_mut_bitslice(&mut self) -> &mut BitSlice<T, O> {
		unsafe { self.bitspan.into_bitslice_mut() }
	}

	/// Views the bit-box as a slice of its underlying memory elements.
	///
	/// Because bit-boxes uniquely own their buffer, they can safely view the
	/// underlying buffer without dealing with contending neighbors.
	#[inline]
	pub fn as_raw_slice(&self) -> &[T] {
		let (data, len) =
			(self.bitspan.address().to_const(), self.bitspan.elements());
		unsafe { slice::from_raw_parts(data, len) }
	}

	/// Views the bit-box as a mutable slice of its underlying memory elements.
	///
	/// Because bit-boxes uniquely own their buffer, they can safely view the
	/// underlying buffer without dealing with contending neighbors.
	#[inline]
	pub fn as_raw_mut_slice(&mut self) -> &mut [T] {
		let (data, len) =
			(self.bitspan.address().to_mut(), self.bitspan.elements());
		unsafe { slice::from_raw_parts_mut(data, len) }
	}

	/// Sets the unused bits outside the `BitBox` buffer to a fixed value.
	///
	/// This method modifies all bits that the allocated buffer owns but which
	/// are outside the `self.as_bitslice()` view. `bitvec` guarantees that all
	/// owned bits are initialized to *some* value, but does not guarantee
	/// *which* value. This method can be used to make all such unused bits have
	/// a known value after the call, so that viewing the underlying memory
	/// directly has consistent results.
	///
	/// Note that the crate implementation guarantees that all bits owned by its
	/// handles are stably initialized according to the language and compiler
	/// rules! `bitvec` will never cause UB by using uninitialized memory.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bits = 0b1011_0101u8.view_bits::<Msb0>();
	/// let mut bb = BitBox::from_bitslice(&bits[2 .. 6]);
	/// assert_eq!(bb.count_ones(), 3);
	/// // Remember, the two bits on each edge are unspecified, and cannot be
	/// // observed! They must be masked away for the test to be meaningful.
	/// assert_eq!(bb.as_raw_slice()[0] & 0x3C, 0b00_1101_00u8);
	///
	/// bb.fill_uninitialized(false);
	/// assert_eq!(bb.as_raw_slice(), &[0b00_1101_00u8]);
	///
	/// bb.fill_uninitialized(true);
	/// assert_eq!(bb.as_raw_slice(), &[0b11_1101_11u8]);
	/// ```
	#[inline]
	pub fn fill_uninitialized(&mut self, value: bool) {
		let (_, head, bits) = self.bitspan.raw_parts();
		let head = head.into_inner() as usize;
		let tail = head + bits;
		let all = self.as_raw_mut_slice().view_bits_mut::<O>();
		unsafe {
			all.get_unchecked_mut(.. head).fill(value);
			all.get_unchecked_mut(tail ..).fill(value);
		}
	}

	/// Ensures that the allocated buffer has no dead bits between the start of
	/// the buffer and the start of the live bit-slice.
	///
	/// This is useful for ensuring a consistent memory layout in bit-boxes
	/// created by cloning an arbitrary bit-slice into the heap. As bit-slices
	/// can begin and end anywhere in memory, the [`::from_bitslice()`] function
	/// does not attempt to normalize them and only does a fast element-wise
	/// copy when creating the bit-box.
	///
	/// The value of dead bits that are in the allocation but not in the live
	/// region are *initialized*, but do not have a *specified* value. After
	/// calling this method, you should use [`.fill_uninitialized()`] to set the
	/// excess bits in the buffer to a fixed value.
	///
	/// ## Examples
	///
	/// ```rust
	/// use bitvec::prelude::*;
	///
	/// let bits = &0b10_1101_01u8.view_bits::<Msb0>()[2 .. 6];
	/// let mut bb = BitBox::from_bitslice(bits);
	/// // Remember, the two bits on each edge are unspecified, and cannot be
	/// // observed! They must be masked away for the test to be meaningful.
	/// assert_eq!(bb.as_raw_slice()[0] & 0x3C, 0b00_1101_00u8);
	///
	/// bb.force_align();
	/// bb.fill_uninitialized(false);
	/// assert_eq!(bb.as_raw_slice(), &[0b1101_0000u8]);
	/// ```
	///
	/// [`::from_bitslice()`]: Self::from_bitslice
	/// [`.fill_uninitialized()`]: Self::fill_uninitialized
	#[inline]
	pub fn force_align(&mut self) {
		let head = self.bitspan.head();
		if head == BitIdx::MIN {
			return;
		}
		let head = head.into_inner() as usize;
		let last = self.len() + head;
		unsafe {
			self.bitspan.set_head(BitIdx::MIN);
			self.copy_within_unchecked(head .. last, 0);
		}
	}

	/// Permits a function to modify the `Box` backing storage of a `BitBox`
	/// handle.
	///
	/// This produces a temporary `Box` view of the bit-box’s buffer and allows
	/// a function to have mutable access to it. After the callback returns, the
	/// `Box` is written back into `self` and forgotten.
	#[inline]
	fn with_box<F, R>(&mut self, func: F) -> R
	where F: FnOnce(&mut ManuallyDrop<Box<[T]>>) -> R {
		self.as_raw_mut_slice()
			.pipe(|raw| unsafe { Box::from_raw(raw) })
			.pipe(ManuallyDrop::new)
			.pipe_ref_mut(func)
	}
}