//! 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]

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
	}};
}

/// 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>);


/// 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 zero-length buffer that pretended to store items"
		);
		assert!(
			N == self.offset || N != 0,
			"tried to extract partially filled buffer"
		);
		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()))
	}

	/// 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")
		}
	}
}

#[test]
fn try_construe() {
	const fn multiply<const N: usize, T: Copy>(mut slice: &[T], times: usize)
		-> Construe<T, N>
	{
		let mut c = Construe::new();
		while let [item, rest @ ..] = slice {
			slice = rest;
			let mut i = 0;
			while i < times {
				c = c.push(*item).0;
				i += 1;
			}
		}
		c
	}
	const fn concat<const N: usize>(mut slice: &[&str], times: usize)
		-> StrConstrue<N>
	{
		let mut sc = StrConstrue::new();
		while let [s, rest @ ..] = slice {
			slice = rest;
			let mut i = 0;
			while i < times {
				sc = sc.push_str(s);
				i += 1;
			}
		}
		sc
	}

	const WORDS: &[&str] = &{
		const LEN: usize = multiply(&["hey", "you"], 2).needs_len();
		const ARRAY: [&str; LEN] = multiply(&["hey", "you"], 2).finish();
		ARRAY
	};

	assert_eq!(WORDS, &["hey", "hey", "you", "you"]);

	const WORDS2: &[&str] = construe!(&[&str] => multiply(&["hey", "you"], 2));
	assert_eq!(WORDS, WORDS2);

	construe!(const WORDS3: &[&str] = multiply(&["hey", "you"], 2));
	assert_eq!(WORDS, WORDS3);

	construe!(const WORDS4: [&str; _] = multiply(&["hey", "you"], 2));
	assert_eq!(WORDS, &WORDS4);

	construe!(const ONE_WORD: &str = concat(&["hey", "you"], 2));
	assert_eq!(ONE_WORD, "heyheyyouyou");

	// since traits require `&'static` for some reason...
	trait Trait {
		const STR: &'static str;
		const ARR: &'static [u8];
	}
	impl Trait for () {
		construe!(const STR: &'static str = concat(&["a", "b"], 10));
		construe!(const ARR: &'static [u8] = multiply(&[1, 2, 3], 9));
	}
}