nvec 0.10.0

// Copyright 2025-2026 Gabriel Bjørnager Jensen.
//
// SPDX: MIT OR Apache-2.0

//! The [`NVec`] type.

mod convert;
mod cmp;
mod fmt;
mod iter;
mod oct;
mod ops;
mod serde;
mod test;

use core::borrow::{Borrow, BorrowMut};
use core::hash::{Hash, Hasher};
use core::hint::assert_unchecked;
use core::mem::MaybeUninit;
use core::ptr::drop_in_place;
use core::slice;
use nvec::n_vec::TryReserveError;

#[cfg(feature = "std")]
use std::io::{self, Write};

/// An N-vector.
pub struct NVec<T, const N: usize> {
	/// The length of the vector.
	len: usize,

	/// The raw vector data.
	data: [MaybeUninit<T>; N],
}

impl<T, const N: usize> NVec<T, N> {
	/// The maximum, possible length of the N-vector.
	const MAX_LEN: usize = {
		if size_of::<T>() > 0 {
			let max_size = isize::MAX as usize;
			max_size / size_of::<T>()
		} else {
			usize::MAX
		}
	};

	/// Constructs a new, empty N-vector.
	#[inline]
	#[must_use]
	pub const fn new() -> Self {
		let data = [const { MaybeUninit::uninit() }; N];

		// SAFETY: A length of `0` is always valid.
		unsafe { Self::from_raw_parts(data, 0) }
	}

	/// Attempts to construct a new N-vector with a
	/// minimum capacity.
	///
	/// # Errors
	///
	/// As all N-vector are capacity-constrained by `N`,
	/// this constructer merely tests if the provided
	/// capacity is within the bounds of the specific
	/// `NVec` instance.
	#[inline]
	pub const fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
		if capacity <= N {
			Ok(Self::new())
		} else {
			Err(TryReserveError)
		}
	}

	/// Attempts to reserve capacity for additional
	/// elements.
	///
	/// # Errors
	///
	/// As the total capacity of the vector cannot be
	/// grown, this method will simply test if the
	/// remaining capacity is sufficient to store the
	/// specific element count: If the space is
	/// insufficient, this method will return an [`Err`]
	/// instance.
	pub const fn try_reserve(&self, extra: usize) -> Result<(), TryReserveError> {
		if extra <= self.remaining_capacity() {
			Ok(())
		} else {
			Err(TryReserveError)
		}
	}

	/// Attempts to push an element into the vector.
	///
	/// # Errors
	///
	/// This method will return an [`Err`] instance if
	/// there isn't any capacity left for the pushed
	/// object.
	pub fn try_push(&mut self, elem: T) -> Result<(), TryReserveError> {
		self.try_push_mut(elem).map(|_| ())
	}

	/// Attempts to push an element into the vector,
	/// returning a mutable reference to its slot.
	///
	/// # Errors
	///
	/// This method will return an [`Err`] instance if
	/// there isn't any capacity left for the pushed
	/// object.
	pub fn try_push_mut(&mut self, elem: T) -> Result<&mut T, TryReserveError> {
		if self.remaining_capacity() < 1 {
			return Err(TryReserveError);
		}

		let slot = unsafe { self.push_unchecked_mut(elem) };
		Ok(slot)
	}

	/// Unsafely pushes an element into the vector,
	/// returning a mutable reference to its slot.
	///
	/// # Safety
	///
	/// The vector must have enough remaining capacity
	/// for at least one more element.
	#[inline]
	pub const unsafe fn push_unchecked_mut(&mut self, elem: T) -> &mut T {
		debug_assert!(self.remaining_capacity() >= 1);

		// SAFETY: Caller guarantees that there is suffi-
		// cient capacity, in which case this offset is
		// within bounds (and not even one past the end:)
		let slot = unsafe { self.as_mut_ptr().add(self.len()) };

		// SAFETY: We have already guaranteed that the
		// pointer is within bounds, which itself implies:
		//
		// * The pointer is valid for writes.
		//
		// * The pointer is aligned.
		unsafe { slot.write(elem) };

		// SAFETY: The above slot is allocated in the spare
		// capacity, guaranteeing that this capacity is at
		// least one.
		self.len += 1;

		// SAFETY: The pointer was initially derived from a
		// mutable `MaybeUninit` reference, with
		// `MaybeUninit<T>` being guaranteed transparent to
		// `T`. The following invariants are thus kept
		// thanks to the pointer being unmodified:
		//
		// * The pointer is aligned.
		//
		// * The pointer is non-null.
		//
		// * The pointer is dereferenceable (i.e. is has
		//   both read and write provenance and points to a
		//   single allocation.)
		//
		// * The pointer is exclusive.
		//
		// We have just now made sure that:
		//
		// * The destination is a valid instance of `T`.
		unsafe { &mut *slot }
	}

	/// Attempts to resize the vector.
	///
	/// # Errors
	///
	/// This method will return an [`Err`] instance if
	/// the provided length is longer than the capacity
	/// of the vector.
	pub fn try_resize(&mut self, len: usize, value: T) -> Result<(), TryReserveError>
	where
		T: Clone,
	{
		if len > self.len() {
			let diff = self.len().abs_diff(len);

			let slots = self.spare_capacity_mut()
				.get_mut(..diff)
				.ok_or(TryReserveError)?;

			for slot in slots {
				slot.write(value.clone());
			}

			// SAFETY: We have made sure to initialise the ad-
			// ditional elements with the padding value.
			unsafe { self.set_len(len) };
		} else if len < self.len() {
			self.truncate(len);
		}

		Ok(())
	}

	/// Truncates the vector.
	///
	/// If the provided length is greater than or equal
	/// to the vector's current length, the vector
	/// remains unchanged.
	#[inline]
	pub fn truncate(&mut self, len: usize) {
		if len >= self.len() {
			return;
		}

		// SAFETY: We have above tested that the new length
		// is less than the current length.
		let to_drop: *mut _ = unsafe { self.get_unchecked_mut(len..) };

		// SAFETY: We have above tested that the new length
		// is less than the current length, so we can also
		// not expose invalid elements.
		self.len = len;

		// SAFETY: The following are guaranteed due to the
		// pointer being coerced from a mutable reference:
		//
		// * The pointer is valid for both reads and
		//   writes.
		//
		// * The pointer is aligned.
		//
		// * The pointer is non-null.
		//
		// * The destination is a valid instance of `[T]`.
		//
		// * The pointer is exclusive for the duration of
		//   the `drop_in_place` call.
		//
		// The vector length has already been reset, so we
		// can assume that these elements are not reused
		// again after the drop (unless reinitialised.)
		unsafe { drop_in_place(to_drop) };
	}

	/// Clears the vector.
	#[inline]
	pub fn clear(&mut self) {
		self.truncate(0)
	}

	/// Retrieves the total capacity of the vector.
	#[inline(always)]
	#[must_use]
	pub const fn capacity(&self) -> usize {
		N
	}

	/// Computes the amount of remaining capacity in the
	/// vector.
	#[inline]
	#[must_use]
	pub const fn remaining_capacity(&self) -> usize {
		// SAFETY: This can never underflow due to our ex-
		// istential requirement of `len() <= capacity()`.
		unsafe{ self.capacity().unchecked_sub(self.len()) }
	}

	/// Overwrites the length of the vector.
	///
	/// When decreasing the vector length, destructors
	/// are not run for the shadowed elements.
	///
	/// # Safety
	///
	/// The following prerequisites must be met when
	/// calling this method:
	///
	/// * `len` may not be greater than the capacity of
	///   the vector (i.e. `N`).
	/// * The first `len` elements of the vector must
	///   already be valid instances of `T`.
	///
	/// Behaviour is undefined if any of these
	/// conditions are violated.
	#[inline(always)]
	#[track_caller]
	pub const unsafe fn set_len(&mut self, len: usize) {
		debug_assert!(len <= self.capacity());

		self.len = len;
	}

	/// Retrieves the length of the vector.
	#[inline(always)]
	#[must_use]
	pub const fn len(&self) -> usize {
		let len = self.len;

		// SAFETY: This is always a precondition.
		unsafe { assert_unchecked(len <= N) };

		// SAFETY: This is guaranteed simply by the fact
		// that we can't allocate a buffer that is bigger
		// than this.
		unsafe { assert_unchecked(len <= Self::MAX_LEN) };

		len
	}

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

	/// Gets a slice over the inactive elements.
	#[inline]
	pub const fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
		let len = self.remaining_capacity();

		let data = {
			let base = self.as_mut_ptr().cast::<MaybeUninit<T>>();

			// SAFETY: `Self::len` always guarantees an index
			// that is at most one past the end of the alloca-
			// tion.
			unsafe { base.add(self.len()) }
		};

		// SAFETY:
		//
		// * The pointer, deriving from a reference, is
		//   guaranteed to be non-null, valid for both
		//   reads and writes, and aligned.
		//
		// * `Self::len` guarantees that all elements up to
		//   (exclusive) the returned index exist.
		//   `MaybeUninit` has no requirements for the
		//   state of these elements.
		//
		// * The lifetime of this returned reference is in-
		//   herited from `self`.
		//
		// * The total size of the slice cannot be greater
		//   than `isize::MAX` as the containing buffer
		//   object is a Rust object itself.
		unsafe { slice::from_raw_parts_mut(data, len) }
	}

	/// Copies the N-vector.
	///
	/// [`NVec`] can't implement [`Copy`] due to it also
	/// implementing [`Drop`]. This method does the op-
	/// eration one would expect from a copy.
	#[inline]
	#[must_use]
	pub const fn copied(&self) -> Self
	where
		T: Copy,
	{
		let len  = self.len;
		let data = self.data;

		// SAFETY: These parts are directly from an exist-
		// ing N-vector.
		unsafe { Self::from_raw_parts(data, len) }
	}

	/// Maps the vector elements
	#[inline]
	#[must_use]
	pub fn map<F: FnMut(T) -> U, U>(self, mut op: F) -> NVec<U, N> {
		let len = self.len();

		let mut data = [const { MaybeUninit::<U>::uninit() }; N];

		for (index, value) in self.into_iter().enumerate() {
			let slot = &mut data[index];

			let value = op(value);
			slot.write(value);
		}

		// SAFETY:
		//
		// * Each active element has been properly ini-
		//   tialised from a result of `op`.
		//
		// * The length `len` comes from an existing N-vec-
		//   tor and is therefore guaranteed to be within bounds.
		unsafe { NVec::from_raw_parts(data, len) }
	}
}

impl<T, const N: usize> Borrow<[T]> for NVec<T, N> {
	#[inline]
	fn borrow(&self) -> &[T] {
		self
	}
}

impl<T, const N: usize> BorrowMut<[T]> for NVec<T, N> {
	#[inline]
	fn borrow_mut(&mut self) -> &mut [T] {
		self
	}
}

impl<T: Clone, const N: usize> Clone for NVec<T, N> {
	#[inline]
	fn clone(&self) -> Self {
		let mut new = Self::new();

		for i in 0..self.len() {
			new.data[i].write(self[i].clone());
		}

		// SAFETY: We have just initialised all of these
		// elements.
		unsafe { new.set_len(self.len()) };

		new
	}
}
impl<T, const N: usize> Default for NVec<T, N> {
	#[inline]
	fn default() -> Self {
		Self::new()
	}
}

impl<T, const N: usize> Drop for NVec<T, N> {
	#[inline]
	fn drop(&mut self) {
		let to_drop = self.as_mut_slice();

		// SAFETY: The following are guaranteed due to our
		// passing a mutable reference:
		//
		// * The pointer is valid for both reads and
		//   writes.
		//
		// * The pointer is aligned.
		//
		// * The pointer is non-null.
		//
		// * The destination is a valid instance (slice
		//   hereof) of `T`.
		//
		// * The pointer is exclusive for the duration of
		//   the `drop_in_place` call.
		//
		// The mutable slice does not exist after this
		// call, and we guarantee that the elements are not
		// used afterwards in no other context.
		unsafe { drop_in_place(to_drop) };
	}
}

impl<T: Hash, const N: usize> Hash for NVec<T, N> {
	#[inline]
	fn hash<H: Hasher>(&self, state: &mut H) {
		self.as_slice().hash(state);
	}
}

#[cfg(feature = "std")]
impl<const N: usize> Write for NVec<u8, N> {
	#[inline]
	fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
		let len = self.remaining_capacity().min(buf.len());

		let buf = &buf[..len];
		self.write_all(buf)?;

		Ok(len)
	}

	#[inline(always)]
	fn flush(&mut self) -> io::Result<()> {
		// NOTE: We never cache anything at all.
		Ok(())
	}

	#[inline]
	fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
		let slot = self.spare_capacity_mut()
			.get_mut(..buf.len())
			.ok_or(TryReserveError)?;

		{
			let len            = buf.len();
			let dst: *mut u8   = slot.as_mut_ptr().cast::<u8>();
			let src: *const u8 = buf.as_ptr();

			// SAFETY: todo :(
			unsafe { dst.copy_from_nonoverlapping(src, len) };
		}

		Ok(())
	}
}