construe 0.0.3

//! Compile-Time Growable Array: `Vec` & `String` for `const`!
//!
//! [`Construe`] & [`StrConstrue`] allow you to write `const` functions that behave as though though they can collect items into a `Vec` or `&str`s into a `String`, returning an array or `&str`, whose length does *not* need to be known before the function is called.
//!
//! The one caveat is that this is only possible for deterministic functions which, given the same inputs, will always return the same *amount* of items.
//! This is because they will be invoked twice: once to determine the size of the buffer needed and once to collect its contents.
//!
//! Some other restrictions (currently) apply:
//! - can't overwrite previous items or assign directly to an index
//! - items can only be added to the end (only `.push()`)
//! - can't remove items from the buffer (e.g. no `.pop()`)
//! - it's not possible to inspect the buffer during construction
//! - no fallback mode for use outside of `const` contexts
//!
//! # Examples
//!
//! Simple compile-time [`&str`] concatenation using [`StrConstrue`]:
//! ```
//! use construe::{StrConstrue, construe};
//!
//! /// Concatenate all `&str`s into a single `&str`
//! const fn concat<const N: usize>(mut slice: &[&str]) -> StrConstrue<N> {
//!     let mut strc = StrConstrue::new();
//!     // no `for` in const
//!     while let [s, rest @ ..] = slice {
//!         slice = rest;
//!         // by-value since there's no `&mut` in const
//!         strc = strc.push_str(s);
//!     }
//!     strc
//! }
//!
//! construe!(const HELLO_WORLD: &str = concat(&["Hello", " ", "World", "!"]));
//!
//! assert_eq!(HELLO_WORLD, "Hello World!");
//! ```
//!
//! And a slightly more complicated example, using [`Construe`]:
//! ```
//! use construe::{Construe, construe};
//!
//! /// Multiply each item in `slice` `x` times
//! const fn multiply<const N: usize, T: Copy>(mut slice: &[T], x: usize)
//!     -> Construe<T, N>
//! {
//!     let mut c = Construe::new();
//!     while let [item, rest @ ..] = slice {
//!         slice = rest;
//!         let mut i = 0;
//!         while i < x {
//!             // see Construe::push docs on why we need `.0` at the end
//!             c = c.push(*item).0;
//!             i += 1;
//!         }
//!     }
//!     c
//! }
//!
//! // as slice:
//! construe!(const NUMBERS: &[u8] = multiply(&[1, 2, 3], 2));
//! assert_eq!(NUMBERS, [1, 1, 2, 2, 3, 3]);
//!
//! // as array:
//! construe!(const NUMBERS_ARRAY: [u8; _] = multiply(&[1, 2, 3], 2));
//! assert_eq!(NUMBERS, &NUMBERS_ARRAY);
//!
//! // or with `&str`s:
//! construe!(const WORDS: &[&str] = multiply(&["hey", "you"], 2));
//! assert_eq!(WORDS, &["hey", "hey", "you", "you"]);
//! ```
//!
//! # Possible Improvements
//!
//! Some of the restrictions mentioned above may or may not be remedied in future versions (roughly in the order given).
//!
//! However, if a specialized version of these types is required, it would be easiest for you to just write it yourself.
//! For instance, if your function will need to inspect, say, the last 4 items of the buffer during construction, it would be fairly easy to write a [`Construe`] that holds a buffer of size 4 for the first run too.  
//! Implementing `pop()` where you don't need the result would be trivial, and if you do, it would be analogous to the previous case, as long as you can guarantee that a buffer of size `N` can keep up (e.g. "`pop()` won't be called more than once between `push()`es").
//! If you can't make this guarantee it might still be possible to implement: you could run your function thrice, once to determine the size of the look-back buffer, then twice like a normal [`Construe`].
//!
//! Generally, I think the method used by this crate can be extended to make any computation work, given that you could implement an allocator: it would abort the computation prematurely if it runs out of space and ask for twice as much.
//! Then you need to invoke the computation at most log<sub>2</sub>(available_memory) times.  
//! Probably better to just wait until `const` support is better though.

#![no_std]

#[cfg(test)]
mod tests;

use core::mem::{
	ManuallyDrop,
	MaybeUninit
};

/// Invoke a function returning [`Construe`] or [`StrConstrue`]
///
/// This will invoke the function (or any expression) twice: once to determine the size of the buffer needed, and once to collect its contents.
///
/// In case this is not already obvious to you: the expression must be a [constant expression](https://doc.rust-lang.org/reference/const_eval.html).
/// Even if you're not using the form of the macro that defines a constant for you, the macro still needs to store the results of the expression, which means it must have a size known at compile time, which, because we use the expression itself to determine that size, means it must be evaluable at compile time.
///
/// Can be used in 2 different ways: either to define a `const` item or as an (anonymous) expression.
/// Both require you to specify the type of the array/slice/`&str`, but in the former it is simply part of the constant item definition, so you don't need to repeat yourself.
///
/// In both cases, the type you specify may be:
/// - `&str` for expressions that return [`StrConstrue`]
/// - `[T; _]` if you want an array, where `T` is your type and `_` will be replaced by the macro
/// - `&[T]` if you want a slice of `T`
///
/// It's a very simple macro, so you can easily implement your own version if you need it to be slightly different.
/// But you most likely will want to use *a* macro since otherwise you need to write the entire expression (i.e. the function you call) twice, which would be pretty bad if there's any arguments to it.
#[macro_export]
macro_rules! construe {
	($v:vis const $name:ident: & $($l:lifetime)? str = $f:expr) => {
		$v const $name: &$($l)? str = $crate::construe!(&str => $f);
	};
	($v:vis const $name:ident: & $($l:lifetime)? [$t:ty] = $f:expr) => {
		$v const $name: & $($l)? [$t] = &$crate::construe!([$t; _] => $f);
	};
	($v:vis const $name:ident: [$t:ty; _] = $f:expr) => {
		$v const $name: [$t; {$f.needs_len()}] = $f.finish();
	};
	(&str => $f:expr) => {{
		const ARRAY: [u8; {$f.needs_len()}] = $f.store_bytes();
		$crate::StrConstrue::borrow_str(&ARRAY)
	}};
	(&[$t:ty] => $f:expr) => {{
		const ARRAY: [$t; {$f.needs_len()}] = $f.finish();
		&ARRAY
	}};
	([$t:ty; _] => $f:expr) => {{
		const ARRAY: [$t; {$f.needs_len()}] = $f.finish();
		ARRAY
	}};
}

/// Write various types into a [`StrConstrue`]
///
/// Convenience macro for using [`Display`].
///
/// ```
/// use construe::{StrConstrue, construe, write};
///
/// struct Task {
///     done: bool,
///     task: &'static str
/// }
/// const TASKS: &[Task] = &[
///     Task {done: true, task: "write macro"},
///     Task {done: false, task: "document macro"},
///     Task {done: false, task: "test macro"}
/// ];
///
/// /// Write to-do list
/// const fn list<const N: usize>(mut tasks: &[Task]) -> StrConstrue<N> {
///     let mut strc = StrConstrue::new();
///     write!(strc, tasks.len(), " tasks:\n");
///     // no `for` in const
///     while let [task, rest @ ..] = tasks {
///         tasks = rest;
///         write!(
///             strc,
///             if task.done {"[x]"} else {"[ ]"},
///             " ",
///             task.task,
///             "\n"
///         );
///     }
///     strc
/// }
///
/// construe!(const TODO_LIST: &str = list(TASKS));
///
/// let expected = "\
/// 3 tasks:
/// [x] write macro
/// [ ] document macro
/// [ ] test macro
/// ";
/// assert_eq!(TODO_LIST, expected);
/// ```
#[macro_export]
macro_rules! write {
	($sc:ident, $( $v:expr ),* $(,)?) => {
		$( $sc = $crate::Display($v).write($sc); )*
	};
}

/// Alternative to `Vec` for `const`
///
/// Used to write `const` functions as though they have a dynamically sized buffer (i.e. a `Vec`).
/// It requires calling the function twice: on the first run, which uses `N = 0`, the [`Construe`] just pretends to store the items it is given, and it only tracks how many there are.
/// Then wherever this function is invoked can use [`Construe::needs_len`] to determine the size of the buffer (i.e. the correct `N`) that is needed and invoke the same function again, but with a "real" buffer instead.
pub struct Construe<T, const N: usize> {
	offset: usize,
	buffer: [MaybeUninit<T>; N]
}

/// Alternative to `String` for `const`
///
/// This is just a [`Construe<u8, N>`] with a few additional methods, see the [`Construe`] documentation for a little more info.
/// ```
/// use construe::{StrConstrue, construe};
///
/// const fn hello_world<const N: usize>() -> StrConstrue<N> {
///     let strc = StrConstrue::new();
///     strc.push_str("Hello")
///         .push_str(" ")
///         .push_str("World")
///         .push_str("!")
/// }
///
/// construe!(const HELLO_WORLD: &str = hello_world());
///
/// // or manually:
/// const HELLO_WORLD_2: &str = {
///     const LEN: usize = hello_world().needs_len();
///     const ARRAY: [u8; LEN] = hello_world().store_bytes();
///     StrConstrue::borrow_str(&ARRAY)
/// };
///
/// assert_eq!(HELLO_WORLD, "Hello World!");
/// assert_eq!(HELLO_WORLD, HELLO_WORLD_2);
/// ```
pub struct StrConstrue<const N: usize>(Construe<u8, N>);

/// [`fmt::Display`](core::fmt::Display) alternative for a few types
///
/// Unfortunately it's not currently possible to implement this as a trait, at least not in a way that could be used in `const` contexts.
/// Instead, this is implemented as a generic type with only one method: `write`.
///
/// Doing it this way spares us from needing a differently named method for each integer (e.g `write_usize`, `write_u8` and so on).
/// It's just `sc = Display(thing).write(sc);` for all supported types, and the correct method gets picked automatically.
/// This only fails when the type isn't known, which might happen with `sc = Display(123).write(sc);`.
/// In this case, you can disambiguate with `Display(123u8)`, and if it's not an integer literal, `Display::<u8>(123)` always works.
///
/// Additionally, having the same syntax for all "implementors" allows writing a very simple macro to simplify this.
/// (It would also be possible to write a macro like `format!()`, but that would be a proc-macro, and not very simple).
pub struct Display<T>(pub T);

/// Transpose between [`MaybeUninit<[T; N]>`] and [`[MaybeUninit<T>; N]`]
///
/// There are several ways to do this in the standard library but all of them are either unstable, not `const` or not stable in `const` contexts.
/// Simply using [`core::mem::transmute`] doesn't work either.
union ArrayTranspose<T, const N: usize> {
	complete: ManuallyDrop<MaybeUninit<[T; N]>>,
	elements: ManuallyDrop<[MaybeUninit<T>; N]>
}
impl<T, const N: usize> ArrayTranspose<T, N> {
	const fn elements(array: MaybeUninit<[T; N]>) -> [MaybeUninit<T>; N] {
		let transpose = Self {
			complete: ManuallyDrop::new(array)
		};
		unsafe {ManuallyDrop::into_inner(transpose.elements)}
	}
	const fn complete(array: [MaybeUninit<T>; N]) -> MaybeUninit<[T; N]> {
		let transpose = Self {
			elements: ManuallyDrop::new(array)
		};
		unsafe {ManuallyDrop::into_inner(transpose.complete)}
	}
}

impl<T> Construe<T, 0> {
	/// Create a [`Construe`] instance *without the buffer*
	///
	/// This instance will behave (almost) exactly the same as the instance that has the buffer.
	/// Crucially, it is *used* exactly the same, allowing you to write `const` functions that collect items into it as though it were a variably-sized buffer.
	/// Then, you simply *call those functions twice*: the first run (`N = 0`, using this constructor) determines the amount of space you need for the second run (where you use [`Construe::new`] with `N = `[`Construe::needs_len`] from before), which actually stores the collected items.
	/// Obviously, this requires that the functions are deterministic (though it will just panic if not).
	pub const fn start() -> Self {
		Self { offset: 0, buffer: [] }
	}
	/// Amount of items supposed to be stored in the buffer
	///
	/// This is the same as [`Construe::len`], but it exists as a separate method that's only implemented for `N = 0` so that the `const N: usize` generic parameter on functions returning this can be inferred as `0` for the first run.
	pub const fn needs_len(&self) -> usize {
		self.offset
	}
}

impl<T, const N: usize> Construe<T, N> {
	/// Create a [`Construe`] instance (with or without the buffer)
	///
	/// Like [`Construe::start`] but for any `N`, allowing you to write functions that create their own [`Construe`].
	/// They'll need a `const N` generic, which the call site will use to indicate whether this is the first or second run.
	pub const fn new() -> Self {
		Self {
			offset: 0,
			buffer: ArrayTranspose::elements(MaybeUninit::uninit())
		}
	}
	/// Amount of items stored (or supposed to be stored) in the buffer
	pub const fn len(&self) -> usize {
		self.offset
	}
	/// Whether there are no items (supposed to be) stored in the buffer
	pub const fn is_empty(&self) -> bool {
		self.len() == 0
	}

	/// Add item to the buffer
	///
	/// Note that this takes `self` by-value: since `&mut` references aren't yet stable in `const` contexts, we have to keep reassigning the output of the function to the variable.
	///
	/// On the first run, when the buffer isn't available yet, this returns the item inside the [`Option`].
	/// This is necessary because there's no way to restrict `T` to *not* have a destructor (which can't be used by `const` functions).
	/// By giving back the `T` in case we can't store it, we avoid taking on the responsibility to drop it.
	///
	/// ```
	/// use construe::Construe;
	/// // `mut` because we pass it by-value
	/// let mut construe = Construe::start();
	/// // `.0` to ignore (i.e. drop) the `Option<&str>`
	/// construe = construe.push("something").0;
	/// ```
	#[must_use]
	pub const fn push(mut self, item: T) -> (Self, Option<T>) {
		let item = match N {
			0 => Some(item),
			_ => {
				self.buffer[self.offset] = MaybeUninit::new(item);
				None
			}
		};
		self.offset += 1;
		(self, item)
	}

	/// Perform a bitwise copy of the slice contents into the buffer
	///
	/// This function is **untested**.
	/// If at all possible, loop over the slice and use [`Construe::push`] instead.
	///
	/// For [`Copy`] types, use [`copy_from`](Self::copy_from) instead.
	//7
	/// # Safety
	///
	/// Essentially, this function takes ownership of the contents of the slice.
	/// For several reasons, it is not currently possible to accept (and use) a `[T; M]` array by value.
	/// Because of this, the caller must pass in a slice of **an array it owns**, and then **drop/forget the array immediately after** this function returns.
	///
	/// This function may not be called outside of `const` contexts or with a `T` that needs to be dropped.
	pub const unsafe fn steal_from_slice(mut self, slice: &[T]) -> Self {
		assert!(
			!core::mem::needs_drop::<T>(),
			"may not steal from slices of types that need to be dropped"
		);
		if N == 0 {
			self.offset += slice.len();
		}
		else {
			assert!(self.offset + slice.len() < N, "buffer overflow");
			let mut i = 0;
			let len = slice.len();
			let item_ptr = slice.as_ptr();
			while i < len {
				let item = unsafe { item_ptr.add(i).read() };
				self.buffer[self.offset + i] = MaybeUninit::new(item);
				i += 1;
			}
			self.offset += i;
		}
		self
	}

	/// Return the filled buffer, consuming the struct
	///
	/// Panics if the buffer is not filled or if this is a zero-length buffer that was supposed to store items.
	pub const fn finish(self) -> [T; N] {
		assert!(
			N == self.offset || N == 0,
			"tried to extract partially filled buffer"
		);
		assert!(
			N == self.offset || N != 0,
			"tried to extract zero-length buffer that pretended to store items"
		);
		unsafe {ArrayTranspose::complete(self.buffer).assume_init()}
	}
}

impl<T: Copy, const N: usize> Construe<T, N> {
	/// [`Copy`] all items from `slice` into the buffer
	///
	/// If the buffer has length zero, the offset is incremented all the same, the contents of the slice are just not stored.
	pub const fn copy_from(mut self, mut slice: &[T]) -> Self {
		if N == 0 {
			self.offset += slice.len();
		}
		else {
			while let [byte, rest @ ..] = slice {
				slice = rest;
				self.buffer[self.offset] = MaybeUninit::new(*byte);
				self.offset += 1;
			}
		}
		self
	}
}


impl<const N: usize> StrConstrue<N> {
	/// Create a [`StrConstrue`] instance (with or without the buffer)
	pub const fn new() -> Self {Self(Construe::new())}

	/// Amount of bytes stored (or supposed to be stored) in the buffer
	pub const fn len(&self) -> usize {self.0.len()}
	/// Whether there are no bytes (supposed to be) stored in the buffer
	pub const fn is_empty(&self) -> bool {self.0.is_empty()}

	/// Push a [`&str`] into the buffer
	///
	/// Note that this takes `self` by-value: since `&mut` references aren't yet stable in `const` contexts, we have to keep reassigning the output of the function to the variable.
	/// ```
	/// // `mut` because we reassign to it
	/// let mut sc = construe::StrConstrue::<0>::new();
	/// sc = sc.push_str("Test");
	/// // method chaining can save space
	/// sc = sc.push_str("123").push_str(" ").push_str(":^)");
	/// ```
	#[must_use]
	pub const fn push_str(self, s: &str) -> Self {
		Self(self.0.copy_from(s.as_bytes()))
	}

	/// Push a single byte into the buffer
	///
	/// The byte must be valid UTF-8 on its own.
	const fn push_byte(self, byte: u8) -> Self {
		match core::str::from_utf8(&[byte]) {
			Ok(as_str) => self.push_str(as_str),
			Err(_e) => panic!("byte is invalid UTF-8")
		}
	}

	/// Return the assembled byte buffer, consuming the struct
	///
	/// Panics if the buffer is not filled or if this is a zero-length buffer that was supposed to store bytes.
	///
	/// Use [`StrConstrue::borrow_str`] to obtain a [`&str`] from the buffer.
	pub const fn store_bytes(self) -> [u8; N] {
		self.0.finish()
	}
}

impl StrConstrue<0> {
	/// Amount of bytes needed to store the string
	///
	/// This is the same as [`StrConstrue::len`], but it exists as a separate method that's only implemented for `N = 0` so that the `const N: usize` generic parameter on functions returning this can be inferred as `0` for the first run.
	pub const fn needs_len(&self) -> usize {self.0.needs_len()}
	/// Borrow a [`&str`] from a byte slice
	///
	/// See the example at the top for how to use this, the buffer returned by [`StrConstrue::store_bytes`] needs to be stored in a constant to be able to borrow a `&'static str` from it.
	///
	/// This just calls [`core::str::from_utf8`] and panics if the byte slice contains invalid UTF-8.
	pub const fn borrow_str(byte_slice: &[u8]) -> &str {
		match core::str::from_utf8(byte_slice) {
			Ok(slice_as_str) => slice_as_str,
			Err(_e) => panic!("assembled byte slice contains invalid UTF-8")
		}
	}
}

macro_rules! impl_write_unsigned_int {
	($i:ty) => {
		impl Display<$i> {
			/// Writes the number into the [`StrConstrue`] (in base 10)
			pub const fn write<const N: usize>(self, mut sc: StrConstrue<N>)
				-> StrConstrue<N>
			{
				let int = self.0;
				let mut digits = match int.checked_ilog10() {
					Some(d) => d,
					None => 0
				};
				loop {
					let digit = (int / <$i>::pow(10, digits)) % 10;
					sc = sc.push_byte(b'0' + digit as u8);
					digits = match digits.checked_sub(1) {
						Some(d) => d,
						None => break
					};
				}
				sc
			}
		}
	};
	( $($i:ty),* ) => {
		$( impl_write_unsigned_int!($i); )*
	};
}
macro_rules! impl_write_signed_int {
	($i:ty) => {
		impl Display<$i> {
			/// Writes the number into the [`StrConstrue`] (in base 10)
			pub const fn write<const N: usize>(self, mut sc: StrConstrue<N>)
				-> StrConstrue<N>
			{
				let int = self.0;
				if int < 0 {
					sc = sc.push_str("-");
				}
				let mut digits = match int.checked_ilog10() {
					Some(d) => d,
					None if int == 0 => 0,
					// can't negate MIN, but MAX always has the same amount of digits
					None if int == <$i>::MIN => <$i>::MAX.ilog10(),
					None => int.abs().ilog10()
				};
				loop {
					let digit = (int / <$i>::pow(10, digits)) % 10;
					sc = sc.push_byte(b'0' + digit.abs() as u8);
					digits = match digits.checked_sub(1) {
						Some(d) => d,
						None => break
					};
				}
				sc
			}
		}
	};
	( $($i:ty),* ) => {
		$( impl_write_signed_int!($i); )*
	};
}

impl_write_unsigned_int!(u8, u16, u32, u64, u128, usize);
impl_write_signed_int!(i8, i16, i32, i64, i128, isize);

macro_rules! impl_write_nonzero_int {
	($i:ty) => {
		impl Display<$i> {
			/// Writes the number into the [`StrConstrue`] (in base 10)
			pub const fn write<const N: usize>(self, sc: StrConstrue<N>)
				-> StrConstrue<N>
			{
				Display(self.0.get()).write(sc)
			}
		}
	};
	( $($i:ty),* ) => {
		$( impl_write_nonzero_int!($i); )*
	};
}

impl_write_nonzero_int!(
	core::num::NonZeroI8,
	core::num::NonZeroI16,
	core::num::NonZeroI32,
	core::num::NonZeroI64,
	core::num::NonZeroI128,
	core::num::NonZeroIsize,
	core::num::NonZeroU8,
	core::num::NonZeroU16,
	core::num::NonZeroU32,
	core::num::NonZeroU64,
	core::num::NonZeroU128,
	core::num::NonZeroUsize
);

impl Display<char> {
	/// Writes the [`char`] into the [`StrConstrue`]
	pub const fn write<const N: usize>(self, sc: StrConstrue<N>)
		-> StrConstrue<N>
	{
		let (array, len) = encode_utf8_raw(self.0);
		let slice = array.as_slice().split_at(4 - len).1;
		let Ok(s) = core::str::from_utf8(slice) else {unreachable!()};
		sc.push_str(s)
	}
}

impl Display<&str> {
	/// Writes the [`&str`] into the [`StrConstrue`]
	///
	/// Equivalent to [`StrConstrue::push_str`].
	pub const fn write<const N: usize>(self, sc: StrConstrue<N>)
		-> StrConstrue<N>
	{
		sc.push_str(self.0)
	}
}

// taken from core/char/methods.rs & adapted for const + returning len as well
// https://doc.rust-lang.org/1.71.0/src/core/char/methods.rs.html#1717
const fn encode_utf8_raw(ch: char) -> ([u8; 4], usize) {
	// UTF-8 ranges and tags for encoding characters
	const TAG_CONT: u8 = 0b1000_0000;
	const TAG_TWO_B: u8 = 0b1100_0000;
	const TAG_THREE_B: u8 = 0b1110_0000;
	const TAG_FOUR_B: u8 = 0b1111_0000;
	//const MAX_ONE_B: u32 = 0x80;
	//const MAX_TWO_B: u32 = 0x800;
	//const MAX_THREE_B: u32 = 0x10000;

	let len = ch.len_utf8();
	let code = ch as u32;
	let array = match len {
		1 => [0, 0, 0, code as u8],
		2 => [
			0,
			0,
			(code >> 6 & 0x1F) as u8 | TAG_TWO_B,
			(code & 0x3F) as u8 | TAG_CONT,
		],
		3 => [
			0,
			(code >> 12 & 0x0F) as u8 | TAG_THREE_B,
			(code >> 6 & 0x3F) as u8 | TAG_CONT,
			(code & 0x3F) as u8 | TAG_CONT,
		],
		4 => [
			(code >> 18 & 0x07) as u8 | TAG_FOUR_B,
			(code >> 12 & 0x3F) as u8 | TAG_CONT,
			(code >> 6 & 0x3F) as u8 | TAG_CONT,
			(code & 0x3F) as u8 | TAG_CONT,
		],
		_ => unreachable!()
	};
	(array, len)
}