trait-obj-list 0.1.2

#![allow(rustdoc::redundant_explicit_links)] // needed for cargo-rdme
//! A list of objects that all implement a trait, stored in one buffer.
//!
//! Provides the [`DynList`](crate::DynList) data structure. This can be thought
//! of a `Vec<T>` where `T` is some `dyn Trait`. Different implementors of the
//! trait can be added to the vec, and iterating the vector will return `dyn Trait`
//! references.
//!
//! Unlike, for example, a `Vec<Box<dyn Trait>>`, a `DynList` will store all of
//! the values in one flat array, allowing for more efficient allocation and
//! iteration.
//!
//! The tradeoff is that a `DynList` is not as flexible as a `Vec` in how it can
//! be accessed. Because items in the list take up a variable amount of size,
//! random access is not as efficient, and items can only be pushed onto the end
//! of the list.
//!
//! ```
//! # use trait_obj_list::DynList;
//! # use std::any::Any;
//! let mut list = DynList::<dyn Any>::new();
//! list.push(123i32);
//! list.push(String::from("Hello world!"));
//! list.push(true);
//!
//! for item in list.iter() {
//!     if let Some(item) = item.downcast_ref::<i32>() {
//!         println!("{}", *item + 7);
//!     } else if let Some(item) = item.downcast_ref::<String>() {
//!         println!("Text: {item}");
//!     } else if let Some(item) = item.downcast_ref::<bool>() {
//!         println!("{}", !*item);
//!     }
//! }
//! ```
//!
//! # List Types
//!
//! The second generic argument to `DynList` is the internal structure, to select
//! the tradeoffs between storage size and access. The following types are available:
//!
//! * [`DoubleLinked`](crate::types::DoubleLinked): The default. Stores the trait metadata, trait data, and a
//!   length at the end. Allows iterating the list in both directions, but has slightly more
//!   overhead than `SingleLinked`.
//! * [`SingleLinked`](crate::types::SingleLinked): Stores the trait metadata and data, and nothing else. This
//!   is the most comapact representation, but only allows iteration in list order.
//!
//! # Stable Rust Limitations
//!
//! On stable Rust, the `ptr_meta` feature is required. This uses the [`ptr_meta`](::ptr_meta)
//! crate to get the metadata of wide pointers, and so only works with traits that
//! implement [`ptr_meta::Pointee`](::ptr_meta::Pointee). `ptr_meta` provides an implementation for `Any`
//! and `Error` (plus their `Send` and `Sync` variants), but others will need to
//! use the `ptr_meta::pointee` attribute.
//!
//! Additionally, [`DynList::push`](crate::DynList::push) requires that the pushed type implement
//! [`FromImpl`](crate::FromImpl). The trait can be implemented for all sized types implementing
//! a certain trait via the [`impl_from_impl`](crate::impl_from_impl) macro.
//!
//! On nightly Rust, the `ptr_meta` feature can be omitted, in which case the
//! `ptr_metadata` and `unsize` unstable features are used to lift these limitations.
//! In this case, `DynList` will work with any trait and type.
//!
//! # Safety
//!
//! This crate uses `unsafe` a lot, due to having to manage allocations manually and work
//! with dynamically sized types. To help ensure soundness, the test suite is checked with
//! miri, so that any unsound accesses are caught and fixed.

#![no_std]
#![cfg_attr(not(feature = "ptr_meta"), feature(ptr_metadata))]
#![cfg_attr(not(feature = "ptr_meta"), feature(unsize))]
extern crate alloc;

pub mod iters;
#[cfg_attr(feature = "ptr_meta", path = "ptr.stable.rs")]
#[cfg_attr(not(feature = "ptr_meta"), path = "ptr.nightly.rs")]
mod ptr;
pub mod types;

use core::alloc::Layout;
use core::mem::MaybeUninit;
use core::ptr::NonNull;

#[cfg(feature = "ptr_meta")]
pub use ::ptr_meta;

use crate::types::ListType;
use crate::types::ListTypeRev;

/// Trait for converting a sized type to an unsized one.
///
/// On stable Rust (with the `ptr_meta` crate feature), it can
/// be implemented via the [`impl_from_impl`]
/// macro. On nightly, it is implemented for all [`Unsize`](core::marker::Unsize),
/// and the `impl_from_impl` macro does nothing.
///
/// # Safety
///
/// `from_impl` and `from_impl_mut` must return the argument, coerced to the unsized type.
pub unsafe trait FromImpl<T> {
	fn from_impl(value: &T) -> &Self;
	fn from_impl_mut(value: &mut T) -> &mut Self;
}

/// A list of objects that all implement a trait.
///
/// See the crate documentation for more info.
pub struct DynList<T, Typ = types::DoubleLinked>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + ?Sized,
	Typ: ListType<T>,
{
	/// Pointer to the vector
	data: NonNull<MaybeUninit<u8>>,
	/// End of the valid region of the vector, in bytes
	end: usize,
	/// Capacity of the vector, in bytes
	capacity: usize,
	typ: Typ,
	_pd: core::marker::PhantomData<(T::Metadata, T)>,
}

impl<T, Typ> DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + ?Sized,
	Typ: ListType<T>,
{
	/// Creates an empty list.
	///
	/// Does not allocate.
	pub fn new() -> Self {
		let typ = Typ::default();
		Self {
			data: NonNull::without_provenance(typ.starting_align().try_into().unwrap()),
			end: 0,
			capacity: 0,
			typ: Typ::default(),
			_pd: Default::default(),
		}
	}

	/// Gets the number of items in the list.
	pub fn len(&self) -> usize {
		self.typ.num_items()
	}

	/// Checks if the list is empty.
	pub fn is_empty(&self) -> bool {
		self.end == 0
	}

	unsafe fn realloc_to(&mut self, new_capacity: usize) {
		let old_layout =
			Layout::from_size_align(self.capacity, Layout::new::<T::Metadata>().align()).unwrap();
		let new_layout =
			Layout::from_size_align(new_capacity, Layout::new::<T::Metadata>().align())
				.expect("allocation too large");

		let new_ptr = if new_capacity == 0 {
			if self.capacity != 0 {
				unsafe {
					alloc::alloc::dealloc(self.data.cast().as_ptr(), old_layout);
				}
			}
			core::ptr::without_provenance_mut(self.typ.starting_align())
		} else if self.capacity == 0 {
			unsafe { alloc::alloc::alloc(new_layout) }
		} else {
			unsafe { alloc::alloc::realloc(self.data.cast().as_ptr(), old_layout, new_capacity) }
		};

		self.data = NonNull::new(new_ptr as *mut _)
			.unwrap_or_else(|| alloc::alloc::handle_alloc_error(new_layout));
		self.capacity = new_capacity;
	}

	fn ensure_capacity(&mut self, additional: usize) {
		if self.end + additional > self.capacity {
			let new_cap = self
				.end
				.checked_add(additional)
				.and_then(|v| v.checked_mul(2))
				.expect("Allocation too large");
			unsafe { self.realloc_to(new_cap) };
		}
		debug_assert!(self.end + additional <= self.capacity);
	}

	/// Moves a dyn trait from a pointer and pushes it to the end of the list.
	///
	/// This moves the data out of the passed-in pointer, rendering it no longer
	/// dereferenceable.
	///
	/// # Safety
	///
	/// The pointer must be dereferenceable.
	pub unsafe fn push_ptr(&mut self, value: *mut T) {
		unsafe {
			let size = self.typ.entry_size(Layout::for_value(&*value));
			self.ensure_capacity(size);
			self.typ.write_entry(self.data.as_ptr(), self.end, value);
			self.end += size;
		}
	}

	/// Moves a dyn trait out of a box and pushes it to the end of the list.
	///
	/// In addition to adding items from boxes, it also does not require the
	/// dyn trait object to implement [`FromImpl`].
	pub fn push_boxed(&mut self, value: alloc::boxed::Box<T>) {
		unsafe {
			let layout = Layout::for_value(&*value);
			let ptr = alloc::boxed::Box::into_raw(value);
			self.push_ptr(ptr);
			alloc::alloc::dealloc(ptr as *mut _, layout);
		}
	}

	/// Pushes an element onto the list.
	///
	/// This requires that the trait object implements [`FromImpl`] for `U`.
	/// On nightly, it is implemented for all trait implementations, but on stable requires
	/// using the [`impl_from_impl`] macro on the trait.
	///
	/// See also [`Self::push_boxed`] and [`Self::push_ptr`].
	pub fn push<U>(&mut self, value: U)
	where
		T: FromImpl<U>,
	{
		unsafe {
			let mut value = MaybeUninit::new(value);
			let ptr = FromImpl::from_impl_mut(value.assume_init_mut()) as *mut T;
			self.push_ptr(ptr);
		}
	}

	/// Moves all items from another `DynList` into this one, adding them to the end in order.
	pub fn extend_from_other<Typ2>(&mut self, other: DynList<T, Typ2>)
	where
		Typ2: ListType<T>,
	{
		for p in other.into_ptrs_iter() {
			unsafe {
				self.push_ptr(p);
			}
		}
	}

	/// Clears the list, removing all elements.
	///
	/// The list capacity is retained.
	pub fn clear(&mut self) {
		if let Some(c) = self.cursor() {
			c.drop_after();
		}
	}

	/// Shrinks the capacity to hold exactly what is stored in the list.
	pub fn shrink_to_fit(&mut self) {
		unsafe {
			self.realloc_to(self.end);
		}
	}

	/// Iterates through items in this list
	pub fn iter<'a>(&'a self) -> iters::Iter<'a, T, Typ> {
		iters::Iter {
			offset: 0,
			index: 0,
			rev_index: self.typ.num_items(),
			rev_offset: self.end,
			list: self,
		}
	}

	/// Iterates through items in this list mutably.
	///
	/// Note: if using with `dyn Any`, review [Rust's advice about calling its methods][1]!
	/// You will need to derference the item before calling a method from `Any`.
	///
	/// [1]: https://doc.rust-lang.org/std/any/index.html#smart-pointers-and-dyn-any
	pub fn iter_mut<'a>(&'a mut self) -> iters::IterMut<'a, T, Typ> {
		iters::IterMut {
			offset: 0,
			index: 0,
			rev_index: self.typ.num_items(),
			rev_offset: self.end,
			list: self,
		}
	}

	/// Move elements out of the list, yielding pointers to them.
	///
	/// The pointers are valid until the iterator is dropped, at which point they
	/// are all deallocated.
	///
	/// Yielded pointers will not have their contents dropped, so it is safe to
	/// move the data out of them. Any remaining unyielded pointers will have their
	/// contents dropped once the iterator is dropped.
	pub fn into_ptrs_iter(self) -> iters::IntoPtrsIter<T, Typ> {
		iters::IntoPtrsIter {
			list: self,
			offset: 0,
			index: 0,
		}
	}

	/// Moves elements out of the list, moving them into boxes.
	pub fn into_box_iter(self) -> iters::IntoBoxedIter<T, Typ> {
		iters::IntoBoxedIter {
			inner: self.into_ptrs_iter(),
		}
	}

	/// Creates a cursor located at the beginning of the list.
	///
	/// Unlike an iterator, the `Cursor` is lending, but provides the [`iters::Cursor::drop_after`]
	/// method for dropping a section of the list.
	///
	/// Returns `None` if the list is empty.
	pub fn cursor<'a>(&'a mut self) -> Option<iters::Cursor<'a, T, Typ>> {
		if self.is_empty() {
			return None;
		}
		Some(iters::Cursor {
			offset: 0,
			index: 0,
			list: self,
		})
	}
}

impl<T, Typ> DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + ?Sized,
	Typ: ListTypeRev<T>,
{
	/// Creates a cursor located at the end of the list.
	///
	/// Returns `None` if the list is empty.
	pub fn cursor_end<'a>(&'a mut self) -> Option<iters::Cursor<'a, T, Typ>> {
		if self.is_empty() {
			return None;
		}
		let mut cursor = iters::Cursor {
			offset: self.end,
			index: self.typ.num_items(),
			list: self,
		};
		cursor.move_prev();
		Some(cursor)
	}
}

unsafe impl<T, Typ> Send for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + Send + ?Sized,
	Typ: ListType<T> + Send,
{
}
unsafe impl<T, Typ> Sync for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + Sync + ?Sized,
	Typ: ListType<T> + Sync,
{
}

impl<T, Typ> core::ops::Drop for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + ?Sized,
	Typ: ListType<T>,
{
	fn drop(&mut self) {
		self.clear();
		unsafe {
			self.realloc_to(0);
		}
	}
}

impl<T, Typ> Default for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + ?Sized,
	Typ: ListType<T>,
{
	fn default() -> Self {
		Self::new()
	}
}

impl<U, T, Typ> Extend<U> for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + FromImpl<U> + ?Sized,
	Typ: ListType<T>,
{
	fn extend<I: IntoIterator<Item = U>>(&mut self, iter: I) {
		let iter = iter.into_iter();
		// preallocate
		let single_size = self.typ.entry_size(Layout::new::<U>());
		self.ensure_capacity(iter.size_hint().0.saturating_mul(single_size));
		// push
		for v in iter {
			self.push(v);
		}
	}
}

impl<T, Typ> core::fmt::Debug for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + core::fmt::Debug + ?Sized,
	Typ: ListType<T>,
{
	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
		f.debug_list().entries(self.iter()).finish()
	}
}

impl<T, Typ1, U, Typ2> PartialEq<DynList<U, Typ2>> for DynList<T, Typ1>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + PartialEq<U> + ?Sized,
	U: ptr::Pointee<Metadata = ptr::DynMetadata<U>> + ?Sized,
	Typ1: ListType<T>,
	Typ2: ListType<U>,
{
	fn eq(&self, other: &DynList<U, Typ2>) -> bool {
		let mut i1 = self.iter();
		let mut i2 = other.iter();
		while let Some(v1) = i1.next() {
			let Some(v2) = i2.next() else { return false };
			if *v1 != *v2 {
				return false;
			}
		}
		i2.next().is_none()
	}
}

impl<T, Typ> Eq for DynList<T, Typ>
where
	T: ptr::Pointee<Metadata = ptr::DynMetadata<T>> + Eq + ?Sized,
	Typ: ListType<T>,
{
}