//! Traits allowing to [use types as key](crate::DbBuilder::key_type) or
//! [value](crate::DbBuilder::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 (e.g. [`Owned`]) holding a copy for the purpose of memory
//! alignment. These references may be used directly (via
//! [dereferencing](std::ops::Deref)) or be converted into an owned value using
//! [`GenericCow::into_owned`] (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 crate::cow::{GenericCow, Owned};

// TODO: use std::ffi::c_size_t if stabilized
use crate::c_size_t;

use std::borrow::Borrow;
use std::cmp::Ordering;
use std::ffi::c_uint;
use std::mem::{size_of, size_of_val};
use std::ptr::{copy_nonoverlapping, read_unaligned};
use std::slice;
use std::str;

/// Unit type denoting no key
/// (for databases which only contain a single value)
#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct NoKey;

/// Unit type denoting no value
/// (for databases which only contain keys but no values)
#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct NoValue;

/// Types that can be stored
///
/// Any type that implements `Storable` can be used as a key or value in a
/// [`Db`](crate::Db).
/// Types that have a fixed-length byte representation should additionally
/// implement [`StorableConstBytesLen`].
/// Several constants must be set correctly to enable various optimizations.
///
/// # Safety
///
/// * [`CONST_BYTES_LEN`] must only be `true` if [`to_bytes`] always returns a
///   pointer to a byte slice with the same length.
/// * [`TRIVIAL_CMP`] must only be `true` if [`cmp_bytes_unchecked`], when
///   receiving two arguments which have been returned by the [`to_bytes`]
///   method of the same type, performs a lexicographical comparison of those
///   two byte slices.
/// * [`OPTIMIZE_INT`] must only be true if the type is equivalent to
///   [`c_uint`] or the C type `size_t` and the byte representation is in
///   native byte order.
/// * [`to_bytes`] must return a byte representation that can be safely passed
///   to [`from_bytes_unchecked`] (of the same type).
/// * [`cmp_bytes_unchecked`] must be stable, i.e. always return the same
///   result for the same input (for the same type).
/// * [`cmp_bytes_unchecked`] must never unwind.
///
/// [`CONST_BYTES_LEN`]: Storable::CONST_BYTES_LEN
/// [`TRIVIAL_CMP`]: Storable::TRIVIAL_CMP
/// [`OPTIMIZE_INT`]: Storable::OPTIMIZE_INT
/// [`to_bytes`]: Storable::to_bytes
/// [`from_bytes_unchecked`]: Storable::from_bytes_unchecked
/// [`cmp_bytes_unchecked`]: Storable::cmp_bytes_unchecked
pub unsafe trait Storable {
    /// Does byte representation have fixed length?
    ///
    /// If this constant is `true`, then trait [`StorableConstBytesLen`] should
    /// also be implemented.
    const CONST_BYTES_LEN: bool;
    /// Does [`Storable::cmp_bytes_unchecked`] perform a trivial (byte wise)
    /// lexicographical comparison?
    const TRIVIAL_CMP: bool = false;
    // TODO: link `c_size_t` in documentation comment here and "Safety" section
    // above, if stabilized
    /// Is type equivalent to [`c_uint`] or the C type `size_t`, and is its
    /// byte representation in native byte order?
    const OPTIMIZE_INT: bool = false;
    /// Byte representation as [`GenericCow`]
    ///
    /// This can be a simple reference ([`&'a Self`](prim@reference)) or a
    /// a smart-pointer (like [`Owned<[u8]>`](Owned)) which drops the byte
    /// representation when the smart-pointer is dropped.
    type BytesRef<'a>: GenericCow<Borrowed = [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()
    }
    /// Aligned version of `Self` as [`GenericCow`]
    ///
    /// This can be a simple reference ([`&'a Self`](prim@reference)) if there
    /// are no requirements for memory alignment, or can be a smart-pointer
    /// (like [`Owned<Self>`](Owned)) which drops the re-aligned copy when the
    /// smart-pointer is dropped.
    type AlignedRef<'a>: GenericCow<Borrowed = Self>;
    /// Converts from byte slice
    ///
    /// # Safety
    ///
    /// The passed byte representation (`bytes`) must have been created with
    /// [`<Self as Storable>::to_bytes`](Storable::to_bytes) on the same
    /// platform (same endianess / word size).
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_>;
    /// Compares byte representation using [`Ord`]
    ///
    /// This function is provided for convenient implementation of
    /// [`Storable::cmp_bytes_unchecked`] where desired.
    ///
    /// # Safety
    ///
    /// The passed byte representations (`a` and `b`) must have been created
    /// with [`<Self as Storable>::to_bytes`](Storable::to_bytes) on the same
    /// platform (same endianess / word size).
    unsafe fn cmp_bytes_by_ord_unchecked(a: &[u8], b: &[u8]) -> Ordering
    where
        Self: Ord,
    {
        if Self::TRIVIAL_CMP {
            a.cmp(b)
        } else {
            // SAFETY: requirements of `Storable::from_bytes_unchecked` are
            // demanded by documentation of `Storable::from_bytes_unchecked`
            // for both `a` and `b`
            unsafe { Self::from_bytes_unchecked(a).cmp(&Self::from_bytes_unchecked(b)) }
        }
    }
    /// Compares byte representation
    ///
    /// # Safety
    ///
    /// The passed byte representations (`a` and `b`) must have been created
    /// with [`<Self as Storable>::to_bytes`](Storable::to_bytes) on the same
    /// platform (same endianess / word size).
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering;
}

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

// SAFETY:
//  *  `cmp_bytes_unchecked` is allowed to always return `Ordering::Equal`
//     because there is only one byte representation returned by `to_bytes`.
//  *  All other requirements documented for `Storable` are also fulfilled.
unsafe impl Storable for NoKey {
    const CONST_BYTES_LEN: bool = true;
    const TRIVIAL_CMP: bool = true;
    type BytesRef<'a> = &'static [u8];
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        b"\x00"
    }
    fn bytes_len(&self) -> usize {
        Self::BYTES_LEN
    }
    type AlignedRef<'a> = &'static Self;
    unsafe fn from_bytes_unchecked(_bytes: &[u8]) -> Self::AlignedRef<'_> {
        &Self
    }
    unsafe fn cmp_bytes_unchecked(_a: &[u8], _b: &[u8]) -> Ordering {
        Ordering::Equal
    }
}

// SAFETY: `NoKey::CONST_BYTES_LEN` is `true`
unsafe impl StorableConstBytesLen for NoKey {
    const BYTES_LEN: usize = 1;
}

// SAFETY:
//  *  `cmp_bytes_unchecked` is allowed to always return `Ordering::Equal`
//     because there is only one byte representation returned by `to_bytes`.
//  *  All other requirements documented for `Storable` are also fulfilled.
unsafe impl Storable for NoValue {
    const CONST_BYTES_LEN: bool = true;
    const TRIVIAL_CMP: bool = true;
    type BytesRef<'a> = &'static [u8];
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        b""
    }
    fn bytes_len(&self) -> usize {
        Self::BYTES_LEN
    }
    type AlignedRef<'a> = &'static Self;
    unsafe fn from_bytes_unchecked(_bytes: &[u8]) -> Self::AlignedRef<'_> {
        &Self
    }
    unsafe fn cmp_bytes_unchecked(_a: &[u8], _b: &[u8]) -> Ordering {
        Ordering::Equal
    }
}

// SAFETY: `NoValue::CONST_BYTES_LEN` is `true`
unsafe impl StorableConstBytesLen for NoValue {
    const BYTES_LEN: usize = 0;
}

trait Signedness {
    const SIGNED: bool;
}

impl Signedness for bool {
    const SIGNED: bool = false;
}
impl Signedness for u8 {
    const SIGNED: bool = false;
}
impl Signedness for u16 {
    const SIGNED: bool = false;
}
impl Signedness for u32 {
    const SIGNED: bool = false;
}
impl Signedness for u64 {
    const SIGNED: bool = false;
}
impl Signedness for u128 {
    const SIGNED: bool = false;
}
impl Signedness for usize {
    const SIGNED: bool = false;
}
impl Signedness for i8 {
    const SIGNED: bool = true;
}
impl Signedness for i16 {
    const SIGNED: bool = true;
}
impl Signedness for i32 {
    const SIGNED: bool = true;
}
impl Signedness for i64 {
    const SIGNED: bool = true;
}
impl Signedness for i128 {
    const SIGNED: bool = true;
}
impl Signedness for isize {
    const SIGNED: bool = true;
}

// SAFETY: must not be exported and only used as below
macro_rules! impl_kv_fixed_size_always_aligned {
    ($type:ty) => {
        // SAFETY: macro only called with primitive integer types or `bool`
        // such that all documented requirements of `Storable` are fulfilled by
        // the following implementation
        unsafe impl Storable for $type {
            const CONST_BYTES_LEN: bool = true;
            #[cfg(target_endian = "big")]
            const TRIVIAL_CMP: bool = !<Self as Signedness>::SIGNED;
            #[cfg(target_endian = "little")]
            const TRIVIAL_CMP: bool = !<Self as Signedness>::SIGNED && size_of::<Self>() == 1;
            const OPTIMIZE_INT: bool = !<Self as Signedness>::SIGNED
                && (size_of::<Self>() == size_of::<c_uint>()
                    || size_of::<Self>() == size_of::<c_size_t>());
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                // SAFETY:
                //  *  The pointer passed to `from_raw_parts` will be valid for
                //     reads for the lifetime given in `&self` and that
                //     lifetime is also passed to `from_raw_parts` through type
                //     inference because of the return type. The data
                //     pointed-to will not be mutated during that lifetime.
                //  *  The element count passed to `from_raw_parts` (equal to
                //     bytes because an `u8` slice is returned) matches the
                //     actual length of `Self` in bytes.
                //  *  The element count (multiplied by `size_of::<u8>()`) is
                //     not larger than `isize::MAX` because the macro is only
                //     invoked for primitive integer types and `bool`.
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of::<Self>())
                }
            }
            fn bytes_len(&self) -> usize {
                Self::BYTES_LEN
            }
            type AlignedRef<'a> = &'a Self;
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                // SAFETY:
                //  *  According to safety requirements, the passed byte
                //     representation (`bytes`) must have been created with
                //     `Storable::to_bytes` on the same platform (same
                //     endianess / word size). In combination with the
                //     requirement for `to_bytes` in the unsafe trait
                //     `Storable`, this means that `bytes.as_ptr().cast()`
                //     results in a valid pointer to `Self` which is safe to
                //     read for the lifetime of the `bytes` reference.
                //  *  `Self` doesn't require any alignment because this macro
                //     is only used for types `bool`, `u8`, and `i8`.
                unsafe { &*bytes.as_ptr().cast() }
            }
            unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
                // SAFETY: requirements of `cmp_bytes_by_ord_unchecked` are
                // demanded by the documentation of `cmp_bytes_unchecked`
                unsafe { Self::cmp_bytes_by_ord_unchecked(a, b) }
            }
        }
        // SAFETY: `CONST_BYTES_LEN` is true, see implementation above
        unsafe impl StorableConstBytesLen for $type {
            const BYTES_LEN: usize = size_of::<Self>();
        }
    };
}

// SAFETY: must not be exported and only used as below
macro_rules! impl_kv_fixed_size_force_align {
    ($type:ty) => {
        // SAFETY: macro only called with primitive integer types or `bool`
        // such that all documented requirements of `Storable` are fulfilled by
        // the following implementation
        unsafe impl Storable for $type {
            const CONST_BYTES_LEN: bool = true;
            #[cfg(target_endian = "big")]
            const TRIVIAL_CMP: bool = !<Self as Signedness>::SIGNED;
            #[cfg(target_endian = "little")]
            const TRIVIAL_CMP: bool = !<Self as Signedness>::SIGNED && size_of::<Self>() == 1;
            const OPTIMIZE_INT: bool = !<Self as Signedness>::SIGNED
                && (size_of::<Self>() == size_of::<c_uint>()
                    || size_of::<Self>() == size_of::<c_size_t>());
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                // SAFETY: same as in macro `impl_kv_fixed_size_always_aligned`
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of::<Self>())
                }
            }
            fn bytes_len(&self) -> usize {
                Self::BYTES_LEN
            }
            type AlignedRef<'a> = Owned<Self>;
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                // SAFETY: According to safety requirements, the passed byte
                // representation (`bytes`) must have been created with
                // `Storable::to_bytes` on the same platform (same endianess /
                // word size). In combination with the requirement for
                // `to_bytes` in the unsafe trait `Storable`, this means that
                // `bytes.as_ptr().cast()` points to a properly initialized
                // value of `Self` being safe for reads while being possibly
                // unaligned.
                Owned(unsafe { read_unaligned(bytes.as_ptr().cast()) })
            }
            unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
                // SAFETY: requirements of `cmp_bytes_by_ord_unchecked` are
                // demanded by the documentation of `cmp_bytes_unchecked`
                unsafe { Self::cmp_bytes_by_ord_unchecked(a, b) }
            }
        }
        // SAFETY: `CONST_BYTES_LEN` is true, see implementation above
        unsafe impl StorableConstBytesLen for $type {
            const BYTES_LEN: usize = size_of::<Self>();
        }
    };
}

impl_kv_fixed_size_always_aligned!(bool);
impl_kv_fixed_size_always_aligned!(u8);
impl_kv_fixed_size_force_align!(u16);
impl_kv_fixed_size_force_align!(u32);
impl_kv_fixed_size_force_align!(u64);
impl_kv_fixed_size_force_align!(u128);
impl_kv_fixed_size_force_align!(usize);
impl_kv_fixed_size_always_aligned!(i8);
impl_kv_fixed_size_force_align!(i16);
impl_kv_fixed_size_force_align!(i32);
impl_kv_fixed_size_force_align!(i64);
impl_kv_fixed_size_force_align!(i128);
impl_kv_fixed_size_force_align!(isize);

// SAFETY: all requirements documented for `Storable` are fulfilled
unsafe impl<const N: usize> Storable for [u8; N] {
    const CONST_BYTES_LEN: bool = true;
    const TRIVIAL_CMP: bool = true;
    const OPTIMIZE_INT: bool = false;
    type BytesRef<'a> = &'a [u8];
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        self
    }
    fn bytes_len(&self) -> usize {
        N
    }
    type AlignedRef<'a> = &'a Self;
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        // SAFETY:
        //  *  According to safety requirements, the passed byte
        //     representation (`bytes`) must have been created with
        //     `Storable::to_bytes`. In combination with the requirement for
        //     `to_bytes` in the unsafe trait `Storable`, this means that
        //     `bytes.as_ptr().cast()` results in a valid pointer to `N` bytes
        //     which are safe to read for the lifetime of the `bytes`
        //     reference.
        //  *  `[u8; N]` doesn't require any alignment.
        unsafe { &*bytes.as_ptr().cast() }
    }
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
        a.cmp(b)
    }
}

// SAFETY: `CONST_BYTES_LEN` is true, see implementation above
unsafe impl<const N: usize> StorableConstBytesLen for [u8; N] {
    const BYTES_LEN: usize = N;
}

unsafe impl Storable for str {
    const CONST_BYTES_LEN: bool = false;
    const TRIVIAL_CMP: bool = true;
    type BytesRef<'a> = &'a [u8];
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        self.as_bytes()
    }
    type AlignedRef<'a> = &'a Self;
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        // SAFETY: According to safety requirements, the passed byte
        // representation (`bytes`) must have been created with
        // `Storable::to_bytes`. In combination with the requirement for
        // `to_bytes` in the unsafe trait `Storable`, this means that `bytes`
        // contains valid UTF-8.
        unsafe { str::from_utf8_unchecked(bytes) }
    }
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
        a.cmp(b)
    }
}

// SAFETY: must not be exported and only used as below
macro_rules! impl_kv_slice_always_aligned {
    ($type:ty) => {
        // SAFETY:
        //   *  The macro is only called with primitive integer types or `bool`
        //      such that all documented requirements of `Storable` are
        //      fulfilled by the following implementation.
        //   *  For unsigned types of size `1`, the implementation of
        //      `cmp_bytes_by_ord_unchecked` will result in a lexicographical
        //      comparison of the arguments (`TRIVIAL_CMP` can be set to `true`
        //      in that case).
        unsafe impl Storable for [$type] {
            const CONST_BYTES_LEN: bool = false;
            #[cfg(target_endian = "big")]
            const TRIVIAL_CMP: bool = !<$type as Signedness>::SIGNED;
            #[cfg(target_endian = "little")]
            const TRIVIAL_CMP: bool = !<$type as Signedness>::SIGNED && size_of::<$type>() == 1;
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                // SAFETY:
                //  *  The pointer passed to `from_raw_parts` will be valid for
                //     reads for the lifetime given in `&self` and that
                //     lifetime is also passed to `from_raw_parts` through type
                //     inference because of the return type. The data
                //     pointed-to will not be mutated during that lifetime.
                //  *  The element count passed to `from_raw_parts` (equal to
                //     bytes because an `u8` slice is returned) matches the
                //     actual length of `Self` in bytes.
                //  *  The element count (multiplied by `size_of::<u8>()`) is
                //     not expected to be larger than `isize::MAX` because the
                //     Rust reference states that the theoretical upper bound
                //     on object and array size is the maximum `isize` value.
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of_val(self))
                }
            }
            type AlignedRef<'a> = &'a Self;
            unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
                // SAFETY:
                //  *  According to safety requirements, the passed byte
                //     representation (`bytes`) must have been created with
                //     `Storable::to_bytes` on the same platform (same
                //     endianess / word size). In combination with the
                //     requirement for `to_bytes` in the unsafe trait
                //     `Storable`, this means that `bytes.as_ptr().cast()`
                //     points to a properly initialized value of `Self`.
                //  *  The return type `Self::AlignedRef<'_>` captures the
                //     lifetime of the `bytes` reference. This lifetime is also
                //     passed to `std::slice::from_raw_parts`. It is safe to
                //     read `bytes.len() / size_of::<$type>()` elements of size
                //     `size_of::<$type>()` from `bytes.as_ptr().cast()` during
                //     that lifetime and that memory will not be modified
                //     during that lifetime either.
                //  *  This macro is only called for `$type`s where alignment
                //     is `1`, i.e. where the pointer will be always aligned.
                //  *  The element count multiplied by `size_of::<$type>()`,
                //     which is equal to `bytes.len()` is not expected to be
                //     larger than `isize::MAX` because the Rust reference
                //     states that the theoretical upper bound on object and
                //     array size is the maximum `isize` value.
                unsafe {
                    slice::from_raw_parts(bytes.as_ptr().cast(), bytes.len() / size_of::<$type>())
                }
            }
            // SAFETY: requirements of `cmp_bytes_by_ord_unchecked` are
            // demanded by the documentation of `cmp_bytes_unchecked`
            unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
                unsafe { Self::cmp_bytes_by_ord_unchecked(a, b) }
            }
        }
    };
}

// SAFETY: must not be exported and only used as below
macro_rules! impl_kv_slice_force_align {
    ($type:ty) => {
        // SAFETY: macro only called with primitive integer types or `bool`
        // such that all documented requirements of `Storable` are fulfilled by
        // the following implementation
        unsafe impl Storable for [$type] {
            const CONST_BYTES_LEN: bool = false;
            #[cfg(target_endian = "big")]
            const TRIVIAL_CMP: bool = !<$type as Signedness>::SIGNED;
            #[cfg(target_endian = "little")]
            const TRIVIAL_CMP: bool = !<$type as Signedness>::SIGNED && size_of::<$type>() == 1;
            type BytesRef<'a> = &'a [u8];
            fn to_bytes(&self) -> Self::BytesRef<'_> {
                // SAFETY: same as in macro `impl_kv_fixed_size_force_align`
                unsafe {
                    slice::from_raw_parts(self as *const Self as *const u8, size_of_val(self))
                }
            }
            type AlignedRef<'a> = Owned<[$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);
                // SAFETY:
                //  *  According to safety requirements, the passed byte
                //     representation (`bytes`) must have been created with
                //     `Storable::to_bytes` on the same platform (same
                //     endianess / word size). In combination with the
                //     requirement for `to_bytes` in the unsafe trait
                //     `Storable`, this means that `bytes.as_ptr().cast()`
                //     points to a properly initialized value of `Self` being
                //     safe for reads while being possibly unaligned.
                //  *  `Vec::as_mut_ptr` points to `bytes.len()` bytes of
                //     memory that can be written to, because `vec` has a
                //     capacity of `bytes.len() / size_of::<$type>()` where
                //     each element has a size of `size_of::<$type>()`.
                //  *  Because `bytes.as_ptr()` points to a (possibly
                //     unaligned) properly initialized value of `Self`, the
                //     elements of `vec` at `0..len` will be initialized. Thus
                //     it is safe to call `vec.set_len(len)`.
                unsafe {
                    copy_nonoverlapping(bytes.as_ptr(), vec.as_mut_ptr() as *mut u8, bytes.len());
                    vec.set_len(len);
                }
                Owned(vec)
            }
            // SAFETY: requirements of `cmp_bytes_by_ord_unchecked` are
            // demanded by the documentation of `cmp_bytes_unchecked`
            unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
                unsafe { Self::cmp_bytes_by_ord_unchecked(a, b) }
            }
        }
    };
}

impl_kv_slice_always_aligned!(bool);
impl_kv_slice_always_aligned!(u8);
impl_kv_slice_force_align!(u16);
impl_kv_slice_force_align!(u32);
impl_kv_slice_force_align!(u64);
impl_kv_slice_force_align!(u128);
impl_kv_slice_force_align!(usize);
impl_kv_slice_always_aligned!(i8);
impl_kv_slice_force_align!(i16);
impl_kv_slice_force_align!(i32);
impl_kv_slice_force_align!(i64);
impl_kv_slice_force_align!(i128);
impl_kv_slice_force_align!(isize);

/// Types that can be borrowed as a type that is [`Storable`]
///
/// Automatically implemented for:
///
/// * `Storable` types whose [owning type](ToOwned::Owned) is the same
///   `Storable` type (e.g. `i32` implements `BorrowStorable<Stored=i32>`)
/// * [`Vec<T>`](Vec), where [`[T]`](prim@slice) is `Storable` and the
///   [owning type](ToOwned::Owned) is `Vec<T>`, (e.g. `Vec<u8>` implements
///   `BorrowStorable<Stored=[u8]>`)
/// * `String` (with [`BorrowStorable::Stored`] being [`str`](prim@str))
pub trait BorrowStorable: Borrow<Self::Stored> {
    /// Borrowed [`Storable`] type
    type Stored: ?Sized + Storable + ToOwned<Owned = Self>;
}

impl<T> BorrowStorable for T
where
    T: Storable + ToOwned<Owned = Self>,
{
    type Stored = Self;
}

impl<T> BorrowStorable for Vec<T>
where
    [T]: Storable + ToOwned<Owned = Self>,
{
    type Stored = [T];
}

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.
///
/// # Safety
///
/// * [`ref_to_bytes`](StorableRef::ref_to_bytes) must return a byte
///   representation that can be safely passed to
///   [`Storable::from_bytes_unchecked`] (of the same type).
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()
    }
}

// SAFETY: `Borrow::borrow`'s implementation for shared references will just
// dereference one indirection and result in a reference to a `T`. Because `T`
// implements the unsafe trait `Storable`, it must be ensured that
// `Storable::to_bytes` fulfills the requirements for
// `StorableRef::ref_to_bytes`.
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()
    }
}

// SAFETY: representation returned by `ref_to_bytes` can be safely passed to
// `<Self as Storable>::from_bytes_unchecked`
unsafe impl<'a, T1, T2, U1, U2> StorableRef<'a, (T1, T2)> for (U1, U2)
where
    T1: Clone + BorrowStorable + 'a,
    T2: Clone + BorrowStorable + 'a,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    U1: StorableRef<'a, <T1 as BorrowStorable>::Stored>,
    U2: StorableRef<'a, <T2 as BorrowStorable>::Stored>,
{
    fn ref_to_bytes(self) -> <(T1, T2) as Storable>::BytesRef<'a> {
        let mut bytes = Vec::with_capacity(self.0.ref_bytes_len() + self.1.ref_bytes_len());
        bytes.extend_from_slice(&self.0.ref_to_bytes());
        bytes.extend_from_slice(&self.1.ref_to_bytes());
        Owned(bytes)
    }
}

// SAFETY:
//  *  `CONST_BYTES_LEN` is `true` only if
//     `<T2 as BorrowStorable>::Stored::CONST_BYTES_LEN` is `true`. This means
//     that `<&Self as StorableRef>::ref_to_bytes` always returns a pointer to
//     a byte slice with the same length. The same holds for
//     `<Self as Storable>::to_bytes` then.
//  *  `TRIVIAL_CMP` is `true` only if `Storable::cmp_bytes_unchecked` performs
//     a lexicographical comparison of the two byte slices passed as arguments.
//     This is because `<T1 as BorrowStorable>::Stored::cmp_bytes_unchecked`
//     and `<T2 as BorrowStorable>::Stored::cmp_bytes_unchecked` both compare
//     lexicographically and these methods are chained using
//     `std::cmp::Ordering::then_with`.
//  *  `OPTIMIZE_INT` is set to the default of `false.
//  *  `to_bytes` returns a byte representation that can be safely passed to
//     `from_bytes_unchecked`.
//  *  `cmp_bytes_unchecked` always return the same result for the same input
//     because the same method implemented for `<T1 as BorrowStorable>::Stored`
//     and `<T2 as BorrowStorable>::Stored` must guarantee the same and their
//     output is chained using `std::cmp::Ordering::then_with`.
unsafe impl<T1, T2> Storable for (T1, T2)
where
    T1: Clone + BorrowStorable,
    T2: Clone + BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const CONST_BYTES_LEN: bool = <T2 as BorrowStorable>::Stored::CONST_BYTES_LEN;
    const TRIVIAL_CMP: bool =
        <T1 as BorrowStorable>::Stored::TRIVIAL_CMP && <T2 as BorrowStorable>::Stored::TRIVIAL_CMP;
    type AlignedRef<'a> = Owned<Self>;
    type BytesRef<'a> = Owned<[u8]>
    where
        Self: 'a;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        StorableRef::<(T1, T2)>::ref_to_bytes((&self.0, &self.1))
    }
    unsafe fn from_bytes_unchecked(bytes: &[u8]) -> Self::AlignedRef<'_> {
        let idx1 = <T1 as BorrowStorable>::Stored::BYTES_LEN;
        unsafe {
            let v1: T1 =
                <T1 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[0..idx1]).into_owned();
            let v2: T2 =
                <T2 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[idx1..]).into_owned();
            Owned((v1, v2))
        }
    }
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
        let idx1 = <T1 as BorrowStorable>::Stored::BYTES_LEN;
        unsafe {
            <T1 as BorrowStorable>::Stored::cmp_bytes_unchecked(&a[0..idx1], &b[0..idx1]).then_with(
                || <T2 as BorrowStorable>::Stored::cmp_bytes_unchecked(&a[idx1..], &b[idx1..]),
            )
        }
    }
}

// SAFETY: Due to the implementation of `Storable` for `Self` and the bounds of
// this implementation, `<Self as Storable>::CONST_BYTES_LEN` is true.
unsafe impl<T1, T2> StorableConstBytesLen for (T1, T2)
where
    T1: Clone + BorrowStorable,
    T2: Clone + 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;
}

// SAFETY: representation returned by `ref_to_bytes` can be safely passed to
// `<Self as Storable>::from_bytes_unchecked`
unsafe impl<'a, T1, T2, T3, U1, U2, U3> StorableRef<'a, (T1, T2, T3)> for (U1, U2, U3)
where
    T1: Clone + BorrowStorable + 'a,
    T2: Clone + BorrowStorable + 'a,
    T3: Clone + BorrowStorable + 'a,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
    U1: StorableRef<'a, <T1 as BorrowStorable>::Stored>,
    U2: StorableRef<'a, <T2 as BorrowStorable>::Stored>,
    U3: StorableRef<'a, <T3 as BorrowStorable>::Stored>,
{
    fn ref_to_bytes(self) -> <(T1, T2, T3) as Storable>::BytesRef<'a> {
        let mut bytes = Vec::with_capacity(
            self.0.ref_bytes_len() + self.1.ref_bytes_len() + self.2.ref_bytes_len(),
        );
        bytes.extend_from_slice(&self.0.ref_to_bytes());
        bytes.extend_from_slice(&self.1.ref_to_bytes());
        bytes.extend_from_slice(&self.2.ref_to_bytes());
        Owned(bytes)
    }
}

// SAFETY: see comment `Storable` for `(T1, T2)` which can be applied here
// accordingly
unsafe impl<T1, T2, T3> Storable for (T1, T2, T3)
where
    T1: Clone + BorrowStorable,
    T2: Clone + BorrowStorable,
    T3: Clone + BorrowStorable,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
{
    const CONST_BYTES_LEN: bool = <T3 as BorrowStorable>::Stored::CONST_BYTES_LEN;
    const TRIVIAL_CMP: bool = <T1 as BorrowStorable>::Stored::TRIVIAL_CMP
        && <T2 as BorrowStorable>::Stored::TRIVIAL_CMP
        && <T3 as BorrowStorable>::Stored::TRIVIAL_CMP;
    type AlignedRef<'a> = Owned<Self>;
    type BytesRef<'a> = Owned<[u8]>
    where
        Self: 'a;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        StorableRef::<(T1, T2, T3)>::ref_to_bytes((&self.0, &self.1, &self.2))
    }
    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;
        unsafe {
            let v1: T1 =
                <T1 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[0..idx1]).into_owned();
            let v2: T2 = <T2 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[idx1..idx2])
                .into_owned();
            let v3: T3 =
                <T3 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[idx2..]).into_owned();
            Owned((v1, v2, v3))
        }
    }
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
        let idx1 = <T1 as BorrowStorable>::Stored::BYTES_LEN;
        let idx2 = idx1 + <T2 as BorrowStorable>::Stored::BYTES_LEN;
        unsafe {
            <T1 as BorrowStorable>::Stored::cmp_bytes_unchecked(&a[0..idx1], &b[0..idx1])
                .then_with(|| {
                    <T2 as BorrowStorable>::Stored::cmp_bytes_unchecked(
                        &a[idx1..idx2],
                        &b[idx1..idx2],
                    )
                })
                .then_with(|| {
                    <T3 as BorrowStorable>::Stored::cmp_bytes_unchecked(&a[idx2..], &b[idx2..])
                })
        }
    }
}

// SAFETY: Due to the implementation of `Storable` for `Self` and the bounds of
// this implementation, `<Self as Storable>::CONST_BYTES_LEN` is true.
unsafe impl<T1, T2, T3> StorableConstBytesLen for (T1, T2, T3)
where
    T1: Clone + BorrowStorable,
    T2: Clone + BorrowStorable,
    T3: Clone + 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;
}

// SAFETY: representation returned by `ref_to_bytes` can be safely passed to
// `<Self as Storable>::from_bytes_unchecked`
unsafe impl<'a, T1, T2, T3, T4, U1, U2, U3, U4> StorableRef<'a, (T1, T2, T3, T4)>
    for (U1, U2, U3, U4)
where
    T1: Clone + BorrowStorable + 'a,
    T2: Clone + BorrowStorable + 'a,
    T3: Clone + BorrowStorable + 'a,
    T4: Clone + BorrowStorable + 'a,
    <T1 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T2 as BorrowStorable>::Stored: StorableConstBytesLen,
    <T3 as BorrowStorable>::Stored: StorableConstBytesLen,
    U1: StorableRef<'a, <T1 as BorrowStorable>::Stored>,
    U2: StorableRef<'a, <T2 as BorrowStorable>::Stored>,
    U3: StorableRef<'a, <T3 as BorrowStorable>::Stored>,
    U4: StorableRef<'a, <T4 as BorrowStorable>::Stored>,
{
    fn ref_to_bytes(self) -> <(T1, T2, T3, T4) as Storable>::BytesRef<'a> {
        let mut bytes = Vec::with_capacity(
            self.0.ref_bytes_len()
                + self.1.ref_bytes_len()
                + self.2.ref_bytes_len()
                + self.3.ref_bytes_len(),
        );
        bytes.extend_from_slice(&self.0.ref_to_bytes());
        bytes.extend_from_slice(&self.1.ref_to_bytes());
        bytes.extend_from_slice(&self.2.ref_to_bytes());
        bytes.extend_from_slice(&self.3.ref_to_bytes());
        Owned(bytes)
    }
}

// SAFETY: see comment `Storable` for `(T1, T2, T3)` which can be applied here
// accordingly
unsafe impl<T1, T2, T3, T4> Storable for (T1, T2, T3, T4)
where
    T1: Clone + BorrowStorable,
    T2: Clone + BorrowStorable,
    T3: Clone + BorrowStorable,
    T4: Clone + 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;
    const TRIVIAL_CMP: bool = <T1 as BorrowStorable>::Stored::TRIVIAL_CMP
        && <T2 as BorrowStorable>::Stored::TRIVIAL_CMP
        && <T3 as BorrowStorable>::Stored::TRIVIAL_CMP
        && <T4 as BorrowStorable>::Stored::TRIVIAL_CMP;
    type AlignedRef<'a> = Owned<Self>;
    type BytesRef<'a> = Owned<[u8]>
    where
        Self: 'a;
    fn to_bytes(&self) -> Self::BytesRef<'_> {
        StorableRef::<(T1, T2, T3, T4)>::ref_to_bytes((&self.0, &self.1, &self.2, &self.3))
    }
    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;
        unsafe {
            let v1: T1 =
                <T1 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[0..idx1]).into_owned();
            let v2: T2 = <T2 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[idx1..idx2])
                .into_owned();
            let v3: T3 = <T3 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[idx2..idx3])
                .into_owned();
            let v4: T4 =
                <T4 as BorrowStorable>::Stored::from_bytes_unchecked(&bytes[idx3..]).into_owned();
            Owned((v1, v2, v3, v4))
        }
    }
    unsafe fn cmp_bytes_unchecked(a: &[u8], b: &[u8]) -> Ordering {
        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;
        unsafe {
            <T1 as BorrowStorable>::Stored::cmp_bytes_unchecked(&a[0..idx1], &b[0..idx1])
                .then_with(|| {
                    <T2 as BorrowStorable>::Stored::cmp_bytes_unchecked(
                        &a[idx1..idx2],
                        &b[idx1..idx2],
                    )
                })
                .then_with(|| {
                    <T3 as BorrowStorable>::Stored::cmp_bytes_unchecked(
                        &a[idx2..idx3],
                        &b[idx2..idx3],
                    )
                })
                .then_with(|| {
                    <T4 as BorrowStorable>::Stored::cmp_bytes_unchecked(&a[idx3..], &b[idx3..])
                })
        }
    }
}

// SAFETY: Due to the implementation of `Storable` for `Self` and the bounds of
// this implementation, `<Self as Storable>::CONST_BYTES_LEN` is true.
unsafe impl<T1, T2, T3, T4> StorableConstBytesLen for (T1, T2, T3, T4)
where
    T1: Clone + BorrowStorable,
    T2: Clone + BorrowStorable,
    T3: Clone + BorrowStorable,
    T4: Clone + 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;
}