//! Traits allowing to [use types as key](crate::DbOptions::key_type) or
//! [value](crate::DbOptions::value_type)
//!
//! Any type that implements [`Storable`] can be used as a key or value in a
//! [`Db`](crate::Db). Implementation is `unsafe` and must be correct and not
//! change between (re-)opening environments.
//!
//! Types that have a fixed-length byte representation should additionally
//! implement [`StorableConstBytesLen`].
//!
//! When values are retrieved from a database, e.g. with
//! [`Txn::get`](crate::Txn::get), they are returned as a pointer of type
//! [`Storable::AlignedRef`], which may be an ordinary shared reference or a
//! smart-pointer holding a copy for the purpose of memory alignment. These
//! references may be used directly (via [dereferencing](Deref)) or be
//! converted into an owned value using
//! [`PointerIntoOwned::into_owned`](crate::owning_pointer::PointerIntoOwned)
//! (alternatively, method [`Txn::get_owned`](crate::Txn::get_owned) may be used
//! to retrieve an owned value, which isn't provided for the cursor methods
//! though).
//!
//! When storing values, e.g. with [`Txn::put`](crate::TxnRw::put), a reference
//! to the `Storable` value must be provided. Alternatively, a reference-like
//! value can be provided if it implements [`StorableRef`]. For example,
//! `(&'a i32, &'a str)` implements `StorableRef<'a, (i32, String)>` and may be
//! passed instead of `&'a (i32, String)` to avoid unnecessary cloning to
//! construct the tuple.

use super::helpers::IsType;
use super::{Owned, OwnedPointer, PointerIntoOwned};

// TODO: When stable, use `std::ffi` instead of `core::ffi`
// see: https://github.com/rust-lang/rust/commit/07ea143f96929ac7f0b7af0f025be48a472273e5
use core::ffi::{c_size_t, c_uint};
use std::borrow::Borrow;
use std::cmp::Ordering;
use std::mem::{size_of, size_of_val};
use std::ops::Deref;
use std::ptr::{copy_nonoverlapping, read_unaligned};
use std::slice;
use std::str;

/// Types that can be stored
///
/// Any type that implements `Storable` can be used as a key or value in a
/// [`Db`](crate::Db). Implementation is `unsafe` and must be correct and not
/// change between (re-)opening environments.
///
/// Types that have a fixed-length byte representation should additionally
/// implement [`StorableConstBytesLen`].
///
/// The generic associated type [`AlignedRef`](Storable::AlignedRef) is an
/// ordinary shared reference or a smart-pointer holding a copy for the
/// purpose of memory alignment. The generic associated type
/// [`BytesRef`](Storable::BytesRef) is usually `&[u8]` (where bytes can be
/// read directly from memory) or `Vec<u8>` (where bytes need to be copied).
///
/// Several constants must be set correctly to enable various optimizations.
pub unsafe trait Storable: Ord {
    /// Does byte representation have fixed length?
    const CONST_BYTES_LEN: bool;
    /// Is type equivalent to [`c_uint`] or [`c_size_t`]?
    const OPTIMIZE_INT: bool = false;
    /// Is [`Ord`] consistent with lexicographical sorting of binary representation?
    const TRIVIAL_CMP: bool = false;
    /// Pointer to aligned version of Self
    type AlignedRef<'a>: Deref<Target = Self> + PointerIntoOwned;
    /// Pointer to byte representation
    type BytesRef<'a>: Deref<Target = [u8]>
    where
        Self: 'a;
    /// Converts to byte slice
    fn to_bytes(&self) -> Self::BytesRef<'_>;
    /// Length of byte representation
    fn bytes_len(&self) -> usize {
        self.to_bytes().len()
    }
    /// Converts from byte slice
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_>;
    /// Compares byte representation
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
        Self::from_bytes_unchecked(a).cmp(&Self::from_bytes_unchecked(b))
    }
}

/// Types that can be stored with a fixed-length byte representation
///
/// This trait should be implemented when [`Storable::CONST_BYTES_LEN`] is
/// true.
pub unsafe trait StorableConstBytesLen: Storable {
    /// Length of byte representation as constant
    const BYTES_LEN: usize;
}

/// Implement [`Storable`] for variable-sized types that do not require
/// alignment and can be simply transmuted
macro_rules! impl_storable_transmute_varsize_trivial_cmp {
    ($type:ty) => {
        unsafe impl Storable for [$type] {
            const CONST_BYTES_LEN: bool = false;
            const TRIVIAL_CMP: bool = true;
            type AlignedRef<'a> = &'a Self;
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of_val(self))
                }
            }
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                slice::from_raw_parts(
                    bytes as *const [u8] as *const $type,
                    bytes.len() / size_of::<$type>(),
                )
            }
        }
    };
}

impl_storable_transmute_varsize_trivial_cmp!(bool);
impl_storable_transmute_varsize_trivial_cmp!(i8);
impl_storable_transmute_varsize_trivial_cmp!(u8);

unsafe impl Storable for str {
    const CONST_BYTES_LEN: bool = false;
    const TRIVIAL_CMP: bool = true;
    type AlignedRef<'a> = &'a Self;
    type BytesRef<'a> = &'a [u8];
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        self.as_bytes()
    }
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        str::from_utf8_unchecked(bytes)
    }
}

/// Implement [`Storable`] and [`StorableConstBytesLen`] for fixed-sized types
/// that do not require alignment and are stored like their memory
/// representation
macro_rules! impl_storable_fixed_size_always_aligned {
    ($type:ty, $optimize_int:expr) => {
        unsafe impl Storable for $type {
            const CONST_BYTES_LEN: bool = true;
            const OPTIMIZE_INT: bool = $optimize_int;
            type AlignedRef<'a> = &'a Self;
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of::<Self>())
                }
            }
            fn bytes_len(&self) -> usize {
                Self::BYTES_LEN
            }
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                &*(bytes as *const _ as *const Self)
            }
        }
        unsafe impl StorableConstBytesLen for $type {
            const BYTES_LEN: usize = size_of::<Self>();
        }
    };
}

/// Implement [`Storable`] and [`StorableConstBytesLen`] for fixed-sized types
/// that need to be aligned but are otherwise stored like their memory
/// representation
macro_rules! impl_storable_fixed_size_force_align {
    ($type:ty, $optimize_int:expr) => {
        unsafe impl Storable for $type {
            const CONST_BYTES_LEN: bool = true;
            const OPTIMIZE_INT: bool = $optimize_int;
            type AlignedRef<'a> = Owned<Self>;
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of::<Self>())
                }
            }
            fn bytes_len(&self) -> usize {
                Self::BYTES_LEN
            }
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                Owned(read_unaligned(bytes.as_ptr() as *const Self))
            }
        }
        unsafe impl StorableConstBytesLen for $type {
            const BYTES_LEN: usize = size_of::<Self>();
        }
    };
}

/// Implement [`Storable`] and [`StorableConstBytesLen`] for unsigned primitive
/// integers that do not require alignment
macro_rules! impl_storable_unsigned_always_aligned {
    ($type:ty) => {
        impl_storable_fixed_size_always_aligned!(
            $type,
            size_of::<Self>() == size_of::<c_uint>() || size_of::<Self>() == size_of::<c_size_t>()
        );
    };
}

/// Implement [`Storable`] and [`StorableConstBytesLen`] for signed primitive
/// integers that do not require alignment
macro_rules! impl_storable_signed_always_aligned {
    ($type:ty) => {
        impl_storable_fixed_size_always_aligned!($type, false);
    };
}

/// Implement [`Storable`] and [`StorableConstBytesLen`] for unsigned primitive
/// integers that need to be (re-)aligned
macro_rules! impl_storable_unsigned_force_align {
    ($type:ty) => {
        impl_storable_fixed_size_force_align!(
            $type,
            size_of::<Self>() == size_of::<c_uint>() || size_of::<Self>() == size_of::<c_size_t>()
        );
    };
}

/// Implement [`Storable`] and [`StorableConstBytesLen`] for signed primitive
/// integers that need to be (re-)aligned
macro_rules! impl_storable_signed_force_align {
    ($type:ty) => {
        impl_storable_fixed_size_force_align!($type, false);
    };
}

// NOTE: `bool` is guaranteed to have a size of 1 and thus is always aligned
impl_storable_unsigned_always_aligned!(bool);
impl_storable_unsigned_always_aligned!(u8);
impl_storable_unsigned_force_align!(u16);
impl_storable_unsigned_force_align!(u32);
impl_storable_unsigned_force_align!(u64);
impl_storable_unsigned_force_align!(u128);
impl_storable_unsigned_force_align!(usize);
impl_storable_signed_always_aligned!(i8);
impl_storable_signed_force_align!(i16);
impl_storable_signed_force_align!(i32);
impl_storable_signed_force_align!(i64);
impl_storable_signed_force_align!(i128);
impl_storable_signed_force_align!(isize);

/// Implement [`Storable`] for slices of primitive integers that need to be
/// (re-)aligned
macro_rules! impl_storable_intslice_force_align {
    ($type:ty) => {
        unsafe impl Storable for [$type] {
            const CONST_BYTES_LEN: bool = false;
            type AlignedRef<'a> = OwnedPointer<Vec<$type>>;
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                unsafe {
                    slice::from_raw_parts(self as *const [$type] as *const u8, self.bytes_len())
                }
            }
            fn bytes_len(&self) -> usize {
                self.len() * size_of::<$type>()
            }
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                let len = bytes.len() / size_of::<$type>();
                let mut vec: Vec<$type> = Vec::with_capacity(len);
                copy_nonoverlapping(bytes.as_ptr(), vec.as_mut_ptr() as *mut u8, bytes.len());
                vec.set_len(len);
                OwnedPointer(vec)
            }
        }
    };
}

impl_storable_intslice_force_align!(u16);
impl_storable_intslice_force_align!(u32);
impl_storable_intslice_force_align!(u64);
impl_storable_intslice_force_align!(u128);
impl_storable_intslice_force_align!(usize);
impl_storable_intslice_force_align!(i16);
impl_storable_intslice_force_align!(i32);
impl_storable_intslice_force_align!(i64);
impl_storable_intslice_force_align!(i128);
impl_storable_intslice_force_align!(isize);

/// [`Storable`] types where the [owning type](PointerIntoOwned::Owned) of the
/// [pointed-to restored value](Storable::AlignedRef) is a certain type
pub trait StorableWithOwned<T>: Storable {
    /// Converts from byte slice into (owned) `Self`
    unsafe fn owned_from_bytes_unchecked(bytes: &[u8]) -> T;
}

impl<T, O> StorableWithOwned<O> for T
where
    T: ?Sized + Storable,
    for<'a> <<T as Storable>::AlignedRef<'a> as PointerIntoOwned>::Owned: IsType<O>,
{
    unsafe fn owned_from_bytes_unchecked(bytes: &[u8]) -> O {
        Self::from_bytes_unchecked(bytes).into_owned().identity()
    }
}

/// Types that can be borrowed as a type that is [`Storable`]
///
/// Automatically implemented for:
///
/// * `Storable` types whose [owning type](PointerIntoOwned::Owned) of the
///   [pointed-to restored value](Storable::AlignedRef) is the same `Storable`
///   type (e.g. `i32` implements `BorrowStorable<Stored=i32>`)
/// * [`Vec<T>`](Vec), where `T` is `Storable` and the
///   [owning type](PointerIntoOwned::Owned) of the
///   [pointed-to restored value](Storable::AlignedRef) is `Vec<T>`, (e.g.
///   `Vec<u8>` implements `BorrowStorable<Stored=[u8]>`)
/// * `String` (with [`BorrowStorable::Stored`] being [`str`](prim@str))
pub unsafe trait BorrowStorable
where
    Self: Sized + Borrow<Self::Stored> + Ord,
{
    /// Borrowed [`Storable`] type
    type Stored: ?Sized + StorableWithOwned<Self>;
    /// Borrows as [`BorrowStorable::Stored`]
    ///
    /// Does the same as [`Borrow::borrow`], but aids type inference
    fn borrow_storable(&self) -> &Self::Stored {
        self.borrow()
    }
}

unsafe impl<T> BorrowStorable for T
where
    T: StorableWithOwned<T>,
{
    type Stored = Self;
}

unsafe impl<T> BorrowStorable for Vec<T>
where
    T: Ord,
    [T]: StorableWithOwned<Vec<T>>,
{
    type Stored = [T];
}

unsafe impl BorrowStorable for String {
    type Stored = str;
}

/// Reference-like types which can be used to store a [`Storable`] type
///
/// Type parameter `T` is the `Storable` type and `'a` is the lifetime used for
/// the reference-like type.
///
/// For example, `(&'a i32, &'a str)` implements
/// `StorableRef<'a, (i32, String)>` and may thus be passed to
/// [`TxnRw::put`](crate::TxnRw::put) instead of `&'a (i32, String)`.
/// This avoids unnecessary cloning when constructing the tuple.
pub unsafe trait StorableRef<'a, T>
where
    Self: Sized + Copy,
    T: ?Sized + Storable + 'a,
{
    /// Converts reference to byte slice
    fn ref_to_bytes(self) -> T::BytesRef<'a>;
    /// Length of byte representation
    fn ref_bytes_len(self) -> usize {
        self.ref_to_bytes().len()
    }
}

unsafe impl<'a, T, U> StorableRef<'a, T> for &'a U
where
    T: ?Sized + Storable + 'a,
    U: ?Sized + Borrow<T>,
{
    fn ref_to_bytes(self) -> T::BytesRef<'a> {
        self.borrow().to_bytes()
    }
    fn ref_bytes_len(self) -> usize {
        self.borrow().bytes_len()
    }
}

unsafe impl<'a, T1, T2> StorableRef<'a, (T1, T2)>
    for (
        &'a <T1 as BorrowStorable>::Stored,
        &'a <T2 as BorrowStorable>::Stored,
    )
where
    T1: BorrowStorable + 'a,
    T2: BorrowStorable + 'a,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    fn ref_to_bytes(self) -> <(T1, T2) as Storable>::BytesRef<'a> {
        let mut bytes = Vec::with_capacity(self.0.bytes_len() + self.1.bytes_len());
        bytes.extend_from_slice(&self.0.to_bytes());
        bytes.extend_from_slice(&self.1.to_bytes());
        bytes
    }
}

unsafe impl<T1, T2> Storable for (T1, T2)
where
    T1: BorrowStorable,
    T2: BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const CONST_BYTES_LEN: bool = <T2 as BorrowStorable>::Stored::CONST_BYTES_LEN;
    type AlignedRef<'a> = Owned<Self>;
    type BytesRef<'a> = Vec<u8>
    where
        T1: 'a,
        T2: 'a;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        StorableRef::<(T1, T2)>::ref_to_bytes((self.0.borrow_storable(), self.1.borrow_storable()))
    }
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        let idx1 = <T1 as BorrowStorable>::Stored::BYTES_LEN;
        let v1: T1 = <T1 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[0..idx1]);
        let v2: T2 = <T2 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[idx1..]);
        Owned((v1, v2))
    }
}

unsafe impl<T1, T2> StorableConstBytesLen for (T1, T2)
where
    T1: BorrowStorable,
    T2: BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const BYTES_LEN: usize =
        <T1 as BorrowStorable>::Stored::BYTES_LEN + <T2 as BorrowStorable>::Stored::BYTES_LEN;
}

unsafe impl<'a, T1, T2, T3> StorableRef<'a, (T1, T2, T3)>
    for (
        &'a <T1 as BorrowStorable>::Stored,
        &'a <T2 as BorrowStorable>::Stored,
        &'a <T3 as BorrowStorable>::Stored,
    )
where
    T1: BorrowStorable + 'a,
    T2: BorrowStorable + 'a,
    T3: BorrowStorable + 'a,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    fn ref_to_bytes(self) -> <(T1, T2, T3) as Storable>::BytesRef<'a> {
        let mut bytes =
            Vec::with_capacity(self.0.bytes_len() + self.1.bytes_len() + self.2.bytes_len());
        bytes.extend_from_slice(&self.0.to_bytes());
        bytes.extend_from_slice(&self.1.to_bytes());
        bytes.extend_from_slice(&self.2.to_bytes());
        bytes
    }
}

unsafe impl<T1, T2, T3> Storable for (T1, T2, T3)
where
    T1: BorrowStorable,
    T2: BorrowStorable,
    T3: BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const CONST_BYTES_LEN: bool = <T3 as BorrowStorable>::Stored::CONST_BYTES_LEN;
    type AlignedRef<'a> = Owned<Self>;
    type BytesRef<'a> = Vec<u8>
    where
        T1: 'a,
        T2: 'a,
        T3: 'a;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        StorableRef::<(T1, T2, T3)>::ref_to_bytes((
            self.0.borrow_storable(),
            self.1.borrow_storable(),
            self.2.borrow_storable(),
        ))
    }
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        let idx1 = <T1 as BorrowStorable>::Stored::BYTES_LEN;
        let idx2 = idx1 + <T2 as BorrowStorable>::Stored::BYTES_LEN;
        let v1: T1 = <T1 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[0..idx1]);
        let v2: T2 = <T2 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[idx1..idx2]);
        let v3: T3 = <T3 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[idx2..]);
        Owned((v1, v2, v3))
    }
}

unsafe impl<T1, T2, T3> StorableConstBytesLen for (T1, T2, T3)
where
    T1: BorrowStorable,
    T2: BorrowStorable,
    T3: BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T3 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const BYTES_LEN: usize = <T1 as BorrowStorable>::Stored::BYTES_LEN
        + <T2 as BorrowStorable>::Stored::BYTES_LEN
        + <T3 as BorrowStorable>::Stored::BYTES_LEN;
}

unsafe impl<'a, T1, T2, T3, T4> StorableRef<'a, (T1, T2, T3, T4)>
    for (
        &'a <T1 as BorrowStorable>::Stored,
        &'a <T2 as BorrowStorable>::Stored,
        &'a <T3 as BorrowStorable>::Stored,
        &'a <T4 as BorrowStorable>::Stored,
    )
where
    T1: BorrowStorable + 'a,
    T2: BorrowStorable + 'a,
    T3: BorrowStorable + 'a,
    T4: BorrowStorable + 'a,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T3 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    fn ref_to_bytes(self) -> <(T1, T2, T3, T4) as Storable>::BytesRef<'a> {
        let mut bytes = Vec::with_capacity(
            self.0.bytes_len() + self.1.bytes_len() + self.2.bytes_len() + self.3.bytes_len(),
        );
        bytes.extend_from_slice(&self.0.to_bytes());
        bytes.extend_from_slice(&self.1.to_bytes());
        bytes.extend_from_slice(&self.2.to_bytes());
        bytes.extend_from_slice(&self.3.to_bytes());
        bytes
    }
}

unsafe impl<T1, T2, T3, T4> Storable for (T1, T2, T3, T4)
where
    T1: BorrowStorable,
    T2: BorrowStorable,
    T3: BorrowStorable,
    T4: BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T3 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const CONST_BYTES_LEN: bool = <T4 as BorrowStorable>::Stored::CONST_BYTES_LEN;
    type AlignedRef<'a> = Owned<Self>;
    type BytesRef<'a> = Vec<u8>
    where
        T1: 'a,
        T2: 'a,
        T3: 'a,
        T4: 'a;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        StorableRef::<(T1, T2, T3, T4)>::ref_to_bytes((
            self.0.borrow_storable(),
            self.1.borrow_storable(),
            self.2.borrow_storable(),
            self.3.borrow_storable(),
        ))
    }
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        let idx1 = <T1 as BorrowStorable>::Stored::BYTES_LEN;
        let idx2 = idx1 + <T2 as BorrowStorable>::Stored::BYTES_LEN;
        let idx3 = idx2 + <T3 as BorrowStorable>::Stored::BYTES_LEN;
        let v1: T1 = <T1 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[0..idx1]);
        let v2: T2 = <T2 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[idx1..idx2]);
        let v3: T3 = <T3 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[idx2..idx3]);
        let v4: T4 = <T4 as BorrowStorable>::Stored::owned_from_bytes_unchecked(&bytes[idx3..]);
        Owned((v1, v2, v3, v4))
    }
}

unsafe impl<T1, T2, T3, T4> StorableConstBytesLen for (T1, T2, T3, T4)
where
    T1: BorrowStorable,
    T2: BorrowStorable,
    T3: BorrowStorable,
    T4: BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T3 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T4 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const BYTES_LEN: usize = <T1 as BorrowStorable>::Stored::BYTES_LEN
        + <T2 as BorrowStorable>::Stored::BYTES_LEN
        + <T3 as BorrowStorable>::Stored::BYTES_LEN
        + <T4 as BorrowStorable>::Stored::BYTES_LEN;
}