serde_buf 0.1.3

/*!
A flat binary encoding for buffered values.

The encoding is an optimized `Vec<Part>`, where `Part` is an enum of each
possible value in `serde`'s data model. The reason we don't just do that is
because Rust's enums are sized to fit their largest member, and every nested
value costs a separate boxing allocation. Instead, parts are packed end-to-end
into a single byte buffer:

```text
    +------+---------+
    | kind | payload |
    +------+---------+
```

The `kind` is a single byte that determines the size and shape of the payload
that follows. Payloads are written unaligned, and come in three classes:

Length-prefixed payloads start with a `len: usize` counting every byte
that follows it in the part, making the buffer a skip-list that can be
walked without recursing into containers:

```text
    +------+------------+~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~+
    | kind | len: usize |  body: `len` bytes  |
    +------+------------+~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~+
```
*/

use core::{fmt, marker::PhantomData, mem, ptr, str};

use alloc::{boxed::Box, vec::Vec};

use zerocopy::{try_transmute, FromBytes, Immutable, IntoBytes, KnownLayout, TryFromBytes};

const MIN_CAP: usize = 256;

#[derive(Clone, Copy, PartialEq, Eq, Debug, TryFromBytes, Immutable, KnownLayout)]
#[repr(u8)]
enum PartKind {
    Unit = 0,
    Bool,
    U8,
    U16,
    U32,
    U64,
    U128,
    I8,
    I16,
    I32,
    I64,
    I128,
    F32,
    F64,
    Char,
    Str,
    BorrowedStr,
    Bytes,
    BorrowedBytes,
    None,
    Some,
    UnitStruct,
    NewtypeStruct,
    UnitVariant,
    NewtypeVariant,
    Seq,
    Tuple,
    Map,
    TupleStruct,
    Struct,
    TupleVariant,
    StructVariant,
}

impl PartKind {
    #[inline]
    fn from_byte(b: u8) -> PartKind {
        try_transmute!(b).expect("kind byte holds an invalid kind")
    }
}

#[repr(C)]
#[derive(Clone, Copy, FromBytes, IntoBytes, Immutable, KnownLayout)]
struct EncodedContainerHeader {
    len: usize,
    num: usize,
}

#[repr(C)]
#[derive(Clone, Copy)]
struct EncodedVariantHeader {
    name: &'static str,
    variant: &'static str,
    variant_index: usize,
}

#[repr(C)]
#[derive(Clone, Copy)]
pub(crate) struct VariantHeader {
    pub(crate) name: &'static str,
    pub(crate) variant_index: u32,
    pub(crate) variant: &'static str,
}

#[derive(Clone, Copy)]
pub(crate) struct SeqHeader {
    pub(crate) num: usize,
}

#[derive(Clone, Copy)]
pub(crate) struct TupleHeader {
    pub(crate) num: usize,
}

#[derive(Clone, Copy)]
pub(crate) struct MapHeader {
    pub(crate) num: usize,
}

#[derive(Clone, Copy)]
pub(crate) struct TupleStructHeader {
    pub(crate) name: &'static str,
    pub(crate) num: usize,
}

#[derive(Clone, Copy)]
pub(crate) struct StructHeader {
    pub(crate) name: &'static str,
    pub(crate) num: usize,
}

#[derive(Clone, Copy)]
pub(crate) struct TupleVariantHeader {
    pub(crate) name: &'static str,
    pub(crate) variant_index: u32,
    pub(crate) variant: &'static str,
    pub(crate) num: usize,
}

#[derive(Clone, Copy)]
pub(crate) struct StructVariantHeader {
    pub(crate) name: &'static str,
    pub(crate) variant_index: u32,
    pub(crate) variant: &'static str,
    pub(crate) num: usize,
}

pub(crate) trait PartVisitor<'i, 'de>: Sized {
    type Output;

    fn visit_unit(self) -> Self::Output;
    fn visit_bool(self, v: bool) -> Self::Output;
    fn visit_u8(self, v: u8) -> Self::Output;
    fn visit_u16(self, v: u16) -> Self::Output;
    fn visit_u32(self, v: u32) -> Self::Output;
    fn visit_u64(self, v: u64) -> Self::Output;
    fn visit_u128(self, v: u128) -> Self::Output;
    fn visit_i8(self, v: i8) -> Self::Output;
    fn visit_i16(self, v: i16) -> Self::Output;
    fn visit_i32(self, v: i32) -> Self::Output;
    fn visit_i64(self, v: i64) -> Self::Output;
    fn visit_i128(self, v: i128) -> Self::Output;
    fn visit_f32(self, v: f32) -> Self::Output;
    fn visit_f64(self, v: f64) -> Self::Output;
    fn visit_char(self, v: char) -> Self::Output;
    fn visit_str(self, v: &'i str) -> Self::Output;
    fn visit_borrowed_str(self, v: &'de str) -> Self::Output;
    fn visit_bytes(self, v: &'i [u8]) -> Self::Output;
    fn visit_borrowed_bytes(self, v: &'de [u8]) -> Self::Output;
    fn visit_none(self) -> Self::Output;
    fn visit_some(self, cursor: &mut Cursor<'i, 'de>) -> Self::Output;
    fn visit_unit_struct(self, name: &'static str) -> Self::Output;
    fn visit_newtype_struct(self, name: &'static str, cursor: &mut Cursor<'i, 'de>)
        -> Self::Output;
    fn visit_unit_variant(
        self,
        header: VariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> Self::Output;
    fn visit_newtype_variant(
        self,
        header: VariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> Self::Output;
    fn visit_seq(self, header: SeqHeader, cursor: &mut Cursor<'i, 'de>) -> Self::Output;
    fn visit_tuple(self, header: TupleHeader, cursor: &mut Cursor<'i, 'de>) -> Self::Output;
    fn visit_map(self, header: MapHeader, cursor: &mut Cursor<'i, 'de>) -> Self::Output;
    fn visit_tuple_struct(
        self,
        header: TupleStructHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> Self::Output;
    fn visit_struct(self, header: StructHeader, cursor: &mut Cursor<'i, 'de>) -> Self::Output;
    fn visit_tuple_variant(
        self,
        header: TupleVariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> Self::Output;
    fn visit_struct_variant(
        self,
        header: StructVariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> Self::Output;
}

#[derive(Clone)]
#[cfg_attr(test, derive(PartialEq))]
pub(crate) struct PartBuf<'a, T> {
    bytes: T,
    _marker: PhantomData<&'a ()>,
}

pub(crate) struct Frame {
    // Offset of the container header's `len` field
    len_at: usize,
    // The number of entries written so far
    pub(crate) num: usize,
    // Whether a map key has been written without its value yet
    pub(crate) expect_value: bool,
}

macro_rules! encode_pod {
    ($($fn_name:ident: $ty:ty => $kind:ident,)*) => {
        $(
            #[inline]
            pub(crate) fn $fn_name(&mut self, v: $ty) {
                self.reserve(1 + mem::size_of::<$ty>());
                self.bytes.push(PartKind::$kind as u8);
                self.bytes.extend_from_slice(v.as_bytes());
            }
        )*
    };
}

impl<'a> PartBuf<'a, Vec<u8>> {
    pub(crate) fn new() -> Self {
        PartBuf {
            bytes: Vec::new(),
            _marker: PhantomData,
        }
    }

    #[inline]
    pub(crate) fn into_boxed_slice(self) -> PartBuf<'a, Box<[u8]>> {
        PartBuf {
            bytes: self.bytes.into_boxed_slice(),
            _marker: PhantomData,
        }
    }

    #[inline]
    fn reserve(&mut self, n: usize) {
        if self.bytes.capacity() - self.bytes.len() < n {
            let grown = n.max(self.bytes.capacity().saturating_mul(3)).max(MIN_CAP);

            self.bytes.reserve(grown);
        }
    }

    #[inline]
    fn push_kind(&mut self, kind: PartKind) {
        self.reserve(1);
        self.bytes.push(kind as u8);
    }

    #[inline]
    fn push_slice(&mut self, v: &[u8]) {
        self.reserve(v.len());
        self.bytes.extend_from_slice(v);
    }

    #[inline]
    fn push_native<T: Copy>(&mut self, v: T) {
        let size = mem::size_of::<T>();

        self.reserve(size);

        let len = self.bytes.len();

        debug_assert!(self.bytes.capacity() - len >= size);

        // SAFETY: `reserve` guarantees `size` bytes of spare capacity, and
        // `T` has no padding, so every byte up to the new length is
        // initialized before the length is advanced
        unsafe {
            ptr::write_unaligned(self.bytes.as_mut_ptr().add(len) as *mut T, v);
            self.bytes.set_len(len + size);
        }
    }

    #[inline]
    fn push_variant(&mut self, name: &'static str, variant_index: u32, variant: &'static str) {
        self.push_native(EncodedVariantHeader {
            name,
            variant,
            variant_index: variant_index as usize,
        });
    }

    #[inline]
    fn begin_container(&mut self, kind: PartKind) -> Frame {
        self.reserve(1 + mem::size_of::<EncodedContainerHeader>());
        self.bytes.push(kind as u8);

        let len_at = self.bytes.len();

        self.bytes
            .extend_from_slice(EncodedContainerHeader { len: 0, num: 0 }.as_bytes());

        Frame {
            len_at,
            num: 0,
            expect_value: false,
        }
    }

    encode_pod!(
        encode_u8: u8 => U8,
        encode_u16: u16 => U16,
        encode_u32: u32 => U32,
        encode_u64: u64 => U64,
        encode_u128: u128 => U128,
        encode_i8: i8 => I8,
        encode_i16: i16 => I16,
        encode_i32: i32 => I32,
        encode_i64: i64 => I64,
        encode_i128: i128 => I128,
        encode_f32: f32 => F32,
        encode_f64: f64 => F64,
    );

    pub(crate) fn encode_unit(&mut self) {
        self.push_kind(PartKind::Unit);
    }

    pub(crate) fn encode_bool(&mut self, v: bool) {
        self.reserve(2);
        self.bytes.push(PartKind::Bool as u8);
        self.bytes.push(v as u8);
    }

    pub(crate) fn encode_char(&mut self, v: char) {
        self.reserve(1 + mem::size_of::<char>());
        self.bytes.push(PartKind::Char as u8);
        self.bytes.extend_from_slice(v.as_bytes());
    }

    pub(crate) fn encode_str(&mut self, v: &str) {
        self.reserve(1 + mem::size_of::<usize>() + v.len());
        self.bytes.push(PartKind::Str as u8);
        self.bytes.extend_from_slice(v.len().as_bytes());
        self.bytes.extend_from_slice(v.as_bytes());
    }

    pub(crate) fn encode_borrowed_str(&mut self, v: &'a str) {
        self.reserve(1 + mem::size_of::<&str>());
        self.bytes.push(PartKind::BorrowedStr as u8);
        self.push_native(v);
    }

    pub(crate) fn encode_bytes(&mut self, v: &[u8]) {
        self.reserve(1 + mem::size_of::<usize>() + v.len());
        self.bytes.push(PartKind::Bytes as u8);
        self.bytes.extend_from_slice(v.len().as_bytes());
        self.bytes.extend_from_slice(v);
    }

    pub(crate) fn encode_borrowed_bytes(&mut self, v: &'a [u8]) {
        self.reserve(1 + mem::size_of::<&str>());
        self.bytes.push(PartKind::BorrowedBytes as u8);
        self.push_native(v);
    }

    pub(crate) fn encode_none(&mut self) {
        self.push_kind(PartKind::None);
    }

    #[inline]
    pub(crate) fn encode_some(&mut self) {
        self.push_kind(PartKind::Some);
    }

    #[inline]
    pub(crate) fn encode_unit_struct(&mut self, name: &'static str) {
        self.push_kind(PartKind::UnitStruct);
        self.push_native(name);
    }

    #[inline]
    pub(crate) fn encode_newtype_struct(&mut self, name: &'static str) {
        self.push_kind(PartKind::NewtypeStruct);
        self.push_native(name);
    }

    #[inline]
    pub(crate) fn encode_unit_variant(
        &mut self,
        name: &'static str,
        variant_index: u32,
        variant: &'static str,
    ) {
        self.push_kind(PartKind::UnitVariant);
        self.push_variant(name, variant_index, variant);
    }

    #[inline]
    pub(crate) fn encode_newtype_variant(
        &mut self,
        name: &'static str,
        variant_index: u32,
        variant: &'static str,
    ) {
        self.push_kind(PartKind::NewtypeVariant);
        self.push_variant(name, variant_index, variant);
    }

    #[inline]
    pub(crate) fn begin_seq(&mut self) -> Frame {
        self.begin_container(PartKind::Seq)
    }

    #[inline]
    pub(crate) fn begin_tuple(&mut self) -> Frame {
        self.begin_container(PartKind::Tuple)
    }

    #[inline]
    pub(crate) fn begin_map(&mut self) -> Frame {
        self.begin_container(PartKind::Map)
    }

    #[inline]
    pub(crate) fn begin_tuple_struct(&mut self, name: &'static str) -> Frame {
        let frame = self.begin_container(PartKind::TupleStruct);
        self.push_native(name);

        frame
    }

    #[inline]
    pub(crate) fn begin_struct(&mut self, name: &'static str) -> Frame {
        let frame = self.begin_container(PartKind::Struct);
        self.push_native(name);

        frame
    }

    #[inline]
    pub(crate) fn begin_tuple_variant(
        &mut self,
        name: &'static str,
        variant_index: u32,
        variant: &'static str,
    ) -> Frame {
        let frame = self.begin_container(PartKind::TupleVariant);
        self.push_variant(name, variant_index, variant);

        frame
    }

    #[inline]
    pub(crate) fn begin_struct_variant(
        &mut self,
        name: &'static str,
        variant_index: u32,
        variant: &'static str,
    ) -> Frame {
        let frame = self.begin_container(PartKind::StructVariant);
        self.push_variant(name, variant_index, variant);

        frame
    }

    #[inline]
    pub(crate) fn push_field_key(&mut self, key: &'static str) {
        self.push_native(key);
    }

    #[inline]
    pub(crate) fn end_seq(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    #[inline]
    pub(crate) fn end_tuple(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    #[inline]
    pub(crate) fn end_map(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    #[inline]
    pub(crate) fn end_tuple_struct(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    #[inline]
    pub(crate) fn end_struct(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    #[inline]
    pub(crate) fn end_tuple_variant(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    #[inline]
    pub(crate) fn end_struct_variant(&mut self, frame: &Frame) {
        self.end_container(frame)
    }

    fn end_container(&mut self, frame: &Frame) {
        let header = EncodedContainerHeader {
            len: self.bytes.len() - (frame.len_at + mem::size_of::<usize>()),
            num: frame.num,
        };

        header
            .write_to(
                &mut self.bytes
                    [frame.len_at..frame.len_at + mem::size_of::<EncodedContainerHeader>()],
            )
            .expect("attempt to patch a header past the end of the buffer");
    }

    pub(crate) fn extend_value(&mut self, v: &PartBuf<'a, Vec<u8>>) {
        self.push_slice(&v.bytes);
    }
}

impl<'a, T: AsRef<[u8]>> PartBuf<'a, T> {
    #[inline]
    pub(crate) fn bytes(&self) -> &[u8] {
        self.bytes.as_ref()
    }

    pub(crate) fn cursor(&self) -> Cursor<'_, 'a> {
        Cursor {
            bytes: self.bytes.as_ref(),
            pos: 0,
            _marker: PhantomData,
        }
    }
}

impl<'a, T: Into<Vec<u8>>> PartBuf<'a, T> {
    pub(crate) fn into_vec(self) -> PartBuf<'a, Vec<u8>> {
        PartBuf {
            bytes: self.bytes.into(),
            _marker: PhantomData,
        }
    }
}

#[inline(always)]
fn read_pod_at<T: FromBytes>(bytes: &[u8], at: usize) -> T {
    // Slicing to the exact size lets the size check inside
    // `read_from_bytes` fold away, leaving a single bounds check
    T::read_from_bytes(&bytes[at..at + mem::size_of::<T>()])
        .expect("attempt to read a part payload past the end of the buffer")
}

pub(crate) fn skip(bytes: &[u8], pos: usize) -> usize {
    let kind = PartKind::from_byte(bytes[pos]);
    let at = pos + 1;

    match kind {
        PartKind::Unit | PartKind::None => at,
        PartKind::Bool | PartKind::U8 | PartKind::I8 => at + 1,
        PartKind::U16 | PartKind::I16 => at + 2,
        PartKind::U32 | PartKind::I32 | PartKind::F32 | PartKind::Char => at + 4,
        PartKind::U64 | PartKind::I64 | PartKind::F64 => at + 8,
        PartKind::U128 | PartKind::I128 => at + 16,
        PartKind::BorrowedStr | PartKind::BorrowedBytes | PartKind::UnitStruct => {
            at + mem::size_of::<&str>()
        }
        PartKind::UnitVariant => at + mem::size_of::<EncodedVariantHeader>(),
        PartKind::Some => skip(bytes, at),
        PartKind::NewtypeStruct => skip(bytes, at + mem::size_of::<&str>()),
        PartKind::NewtypeVariant => skip(bytes, at + mem::size_of::<EncodedVariantHeader>()),
        PartKind::Str
        | PartKind::Bytes
        | PartKind::Seq
        | PartKind::Tuple
        | PartKind::Map
        | PartKind::TupleStruct
        | PartKind::Struct
        | PartKind::TupleVariant
        | PartKind::StructVariant => at + mem::size_of::<usize>() + read_pod_at::<usize>(bytes, at),
    }
}

pub(crate) struct Cursor<'i, 'de> {
    bytes: &'i [u8],
    pos: usize,
    _marker: PhantomData<&'de ()>,
}

impl<'i, 'de> Cursor<'i, 'de> {
    // SAFETY: The caller must ensure that `pos` is a part boundary
    #[inline]
    pub(crate) unsafe fn at(bytes: &'i [u8], pos: usize) -> Self {
        Cursor {
            bytes,
            pos,
            _marker: PhantomData,
        }
    }

    pub(crate) fn empty() -> Self {
        Cursor {
            bytes: &[],
            pos: 0,
            _marker: PhantomData,
        }
    }

    #[inline]
    pub(crate) fn bytes(&self) -> &'i [u8] {
        self.bytes
    }

    #[inline]
    pub(crate) fn pos(&self) -> usize {
        self.pos
    }

    // SAFETY: The caller must ensure that `pos` is a part boundary
    #[inline]
    pub(crate) unsafe fn set_pos(&mut self, pos: usize) {
        self.pos = pos;
    }

    // Whether the part at the cursor is a `Unit`.
    //
    // The result is only meaningful when the cursor is at a part boundary,
    // but calling this anywhere is safe: it only compares a byte
    #[inline]
    pub(crate) fn is_unit(&self) -> bool {
        self.bytes[self.pos] == PartKind::Unit as u8
    }

    #[inline(always)]
    fn kind(&mut self) -> PartKind {
        let kind = PartKind::from_byte(self.bytes[self.pos]);
        self.pos += 1;

        kind
    }

    #[inline(always)]
    fn read_pod<T: FromBytes>(&mut self) -> T {
        let v = read_pod_at::<T>(self.bytes, self.pos);

        self.pos += mem::size_of::<T>();
        v
    }

    // SAFETY: The caller must ensure a valid `T` is encoded at the cursor
    #[inline(always)]
    unsafe fn read_native<T: Copy>(&mut self) -> T {
        debug_assert!(
            self.pos + mem::size_of::<T>() <= self.bytes.len(),
            "attempt to read a part payload past the end of the buffer"
        );

        // SAFETY: Upheld by this function's contract
        let v = unsafe { ptr::read_unaligned(self.bytes.as_ptr().add(self.pos) as *const T) };

        self.pos += mem::size_of::<T>();
        v
    }

    // SAFETY: The caller must ensure the cursor is at the variant header of
    // a variant part
    #[inline]
    unsafe fn read_variant(&mut self) -> VariantHeader {
        // SAFETY: Upheld by this function's contract
        let v = unsafe { self.read_native::<EncodedVariantHeader>() };

        VariantHeader {
            name: v.name,
            variant_index: v.variant_index as u32,
            variant: v.variant,
        }
    }

    #[inline]
    fn slice(&mut self, len: usize) -> &'i [u8] {
        let v = &self.bytes[self.pos..self.pos + len];

        self.pos += len;
        v
    }

    // SAFETY: The caller must ensure the cursor is at a `Str` part's payload
    #[inline]
    unsafe fn read_str(&mut self) -> &'i str {
        let len = self.read_pod::<usize>();
        let v = self.slice(len);

        debug_assert!(str::from_utf8(v).is_ok(), "inline text is not valid UTF-8");

        // SAFETY: Inline text bytes are only ever copied out of `str`s, so
        // they're valid UTF-8
        unsafe { str::from_utf8_unchecked(v) }
    }

    // Read an inline `Bytes` payload (its `len` and data).
    #[inline]
    fn read_bytes(&mut self) -> &'i [u8] {
        let len = self.read_pod::<usize>();

        self.slice(len)
    }

    // SAFETY: The caller must ensure that the cursor is at the start of a field key
    #[inline]
    pub(crate) unsafe fn read_field_key(&mut self) -> &'static str {
        // SAFETY: A field key is a `&'static str`, guaranteed valid by this
        // method's contract
        unsafe { self.read_native::<&'static str>() }
    }

    // SAFETY: The caller must ensure that the cursor is at a part boundary
    #[inline(always)]
    pub(crate) unsafe fn visit_part<V: PartVisitor<'i, 'de>>(&mut self, visitor: V) -> V::Output {
        match self.kind() {
            PartKind::Unit => visitor.visit_unit(),
            PartKind::Bool => visitor.visit_bool(self.read_pod::<u8>() != 0),
            PartKind::U8 => visitor.visit_u8(self.read_pod()),
            PartKind::U16 => visitor.visit_u16(self.read_pod()),
            PartKind::U32 => visitor.visit_u32(self.read_pod()),
            PartKind::U64 => visitor.visit_u64(self.read_pod()),
            PartKind::U128 => visitor.visit_u128(self.read_pod()),
            PartKind::I8 => visitor.visit_i8(self.read_pod()),
            PartKind::I16 => visitor.visit_i16(self.read_pod()),
            PartKind::I32 => visitor.visit_i32(self.read_pod()),
            PartKind::I64 => visitor.visit_i64(self.read_pod()),
            PartKind::I128 => visitor.visit_i128(self.read_pod()),
            PartKind::F32 => visitor.visit_f32(self.read_pod()),
            PartKind::F64 => visitor.visit_f64(self.read_pod()),
            PartKind::Char => visitor.visit_char(
                char::from_u32(self.read_pod()).expect("part payload holds an invalid char"),
            ),
            PartKind::Str => {
                // SAFETY: The kind byte says a `Str` payload follows, and
                // the cursor was at a part boundary by this method's
                // contract
                let v = unsafe { self.read_str() };

                visitor.visit_str(v)
            }
            PartKind::BorrowedStr => {
                // SAFETY: A `BorrowedStr` payload is a `&str` valid for
                // `'de`, guaranteed by the `Value` this cursor was created
                // from
                let v = unsafe { self.read_native::<&'de str>() };

                visitor.visit_borrowed_str(v)
            }
            PartKind::Bytes => {
                let v = self.read_bytes();

                visitor.visit_bytes(v)
            }
            PartKind::BorrowedBytes => {
                // SAFETY: A `BorrowedBytes` payload is a `&[u8]` valid for
                // `'de`, guaranteed by the `Value` this cursor was created
                // from
                let v = unsafe { self.read_native::<&'de [u8]>() };

                visitor.visit_borrowed_bytes(v)
            }
            PartKind::None => visitor.visit_none(),
            PartKind::Some => visitor.visit_some(self),
            PartKind::UnitStruct => {
                // SAFETY: A `UnitStruct` payload is a `&'static str` name,
                // guaranteed by the `Value` this cursor was created from
                let name = unsafe { self.read_native::<&'static str>() };

                visitor.visit_unit_struct(name)
            }
            PartKind::NewtypeStruct => {
                // SAFETY: As for `UnitStruct`
                let name = unsafe { self.read_native::<&'static str>() };

                visitor.visit_newtype_struct(name, self)
            }
            PartKind::UnitVariant => {
                // SAFETY: A valid variant header is encoded in every
                // variant part, guaranteed by the `Value` this cursor was
                // created from
                let header = unsafe { self.read_variant() };

                visitor.visit_unit_variant(header, self)
            }
            PartKind::NewtypeVariant => {
                // SAFETY: As for `UnitVariant`
                let header = unsafe { self.read_variant() };

                visitor.visit_newtype_variant(header, self)
            }
            PartKind::Seq => {
                let num = self.read_pod::<EncodedContainerHeader>().num;

                visitor.visit_seq(SeqHeader { num }, self)
            }
            PartKind::Tuple => {
                let num = self.read_pod::<EncodedContainerHeader>().num;

                visitor.visit_tuple(TupleHeader { num }, self)
            }
            PartKind::Map => {
                let num = self.read_pod::<EncodedContainerHeader>().num;

                visitor.visit_map(MapHeader { num }, self)
            }
            PartKind::TupleStruct => {
                let num = self.read_pod::<EncodedContainerHeader>().num;
                // SAFETY: A `TupleStruct` header carries a `&'static str`
                // name after its container header, guaranteed by the
                // `Value` this cursor was created from
                let name = unsafe { self.read_native::<&'static str>() };

                visitor.visit_tuple_struct(TupleStructHeader { name, num }, self)
            }
            PartKind::Struct => {
                let num = self.read_pod::<EncodedContainerHeader>().num;
                // SAFETY: As for `TupleStruct`
                let name = unsafe { self.read_native::<&'static str>() };

                visitor.visit_struct(StructHeader { name, num }, self)
            }
            PartKind::TupleVariant => {
                let num = self.read_pod::<EncodedContainerHeader>().num;
                // SAFETY: A `TupleVariant` header carries a variant header
                // after its container header, guaranteed by the `Value`
                // this cursor was created from
                let variant = unsafe { self.read_variant() };

                visitor.visit_tuple_variant(
                    TupleVariantHeader {
                        name: variant.name,
                        variant_index: variant.variant_index,
                        variant: variant.variant,
                        num,
                    },
                    self,
                )
            }
            PartKind::StructVariant => {
                let num = self.read_pod::<EncodedContainerHeader>().num;
                // SAFETY: As for `TupleVariant`
                let variant = unsafe { self.read_variant() };

                visitor.visit_struct_variant(
                    StructVariantHeader {
                        name: variant.name,
                        variant_index: variant.variant_index,
                        variant: variant.variant,
                        num,
                    },
                    self,
                )
            }
        }
    }
}

/**
A single-part value small enough to hold outside a buffer.
*/
#[derive(Clone, Copy)]
pub(crate) enum Leaf<'a> {
    Unit,
    Bool(bool),
    U8(u8),
    U16(u16),
    U32(u32),
    U64(u64),
    U128(u128),
    I8(i8),
    I16(i16),
    I32(i32),
    I64(i64),
    I128(i128),
    F32(f32),
    F64(f64),
    Char(char),
    Str(&'a str),
    Bytes(&'a [u8]),
    None,
    UnitStruct(&'static str),
    UnitVariant {
        name: &'static str,
        variant_index: u32,
        variant: &'static str,
    },
}

impl<'a> Leaf<'a> {
    pub(crate) fn encode_into(&self, value: &mut PartBuf<'a, Vec<u8>>) {
        match *self {
            Leaf::Unit => value.encode_unit(),
            Leaf::Bool(v) => value.encode_bool(v),
            Leaf::U8(v) => value.encode_u8(v),
            Leaf::U16(v) => value.encode_u16(v),
            Leaf::U32(v) => value.encode_u32(v),
            Leaf::U64(v) => value.encode_u64(v),
            Leaf::U128(v) => value.encode_u128(v),
            Leaf::I8(v) => value.encode_i8(v),
            Leaf::I16(v) => value.encode_i16(v),
            Leaf::I32(v) => value.encode_i32(v),
            Leaf::I64(v) => value.encode_i64(v),
            Leaf::I128(v) => value.encode_i128(v),
            Leaf::F32(v) => value.encode_f32(v),
            Leaf::F64(v) => value.encode_f64(v),
            Leaf::Char(v) => value.encode_char(v),
            Leaf::Str(v) => value.encode_borrowed_str(v),
            Leaf::Bytes(v) => value.encode_borrowed_bytes(v),
            Leaf::None => value.encode_none(),
            Leaf::UnitStruct(name) => value.encode_unit_struct(name),
            Leaf::UnitVariant {
                name,
                variant_index,
                variant,
            } => value.encode_unit_variant(name, variant_index, variant),
        }
    }

    pub(crate) fn into_value(self) -> PartBuf<'a, Vec<u8>> {
        let mut value = PartBuf::new();
        self.encode_into(&mut value);

        value
    }
}

impl<'a> fmt::Debug for Leaf<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Leaf::Unit => f.write_str("()"),
            Leaf::Bool(v) => v.fmt(f),
            Leaf::U8(v) => v.fmt(f),
            Leaf::U16(v) => v.fmt(f),
            Leaf::U32(v) => v.fmt(f),
            Leaf::U64(v) => v.fmt(f),
            Leaf::U128(v) => v.fmt(f),
            Leaf::I8(v) => v.fmt(f),
            Leaf::I16(v) => v.fmt(f),
            Leaf::I32(v) => v.fmt(f),
            Leaf::I64(v) => v.fmt(f),
            Leaf::I128(v) => v.fmt(f),
            Leaf::F32(v) => v.fmt(f),
            Leaf::F64(v) => v.fmt(f),
            Leaf::Char(v) => v.fmt(f),
            Leaf::Str(v) => v.fmt(f),
            Leaf::Bytes(v) => v.fmt(f),
            Leaf::None => f.write_str("None"),
            Leaf::UnitStruct(name) => f.write_str(name),
            Leaf::UnitVariant { variant, .. } => f.write_str(variant),
        }
    }
}

impl<'a, T: AsRef<[u8]>> fmt::Debug for PartBuf<'a, T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.bytes.as_ref().is_empty() {
            return f.write_str("<empty>");
        }

        DebugPart {
            bytes: self.bytes.as_ref(),
            pos: 0,
        }
        .fmt(f)
    }
}

struct DebugPart<'i> {
    bytes: &'i [u8],
    pos: usize,
}

impl<'i> fmt::Debug for DebugPart<'i> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // SAFETY: `self.pos` is a part boundary, an invariant of `DebugPart`
        let mut c = unsafe { Cursor::at(self.bytes, self.pos) };

        // SAFETY: The cursor is at a part boundary
        unsafe { c.visit_part(DebugVisitor { f }) }
    }
}

struct DebugVisitor<'a, 'f> {
    f: &'a mut fmt::Formatter<'f>,
}

impl<'a, 'f> DebugVisitor<'a, 'f> {
    fn fmt_tuple(self, name: &str, num: usize, bytes: &[u8], mut pos: usize) -> fmt::Result {
        let mut d = self.f.debug_tuple(name);
        for _ in 0..num {
            d.field(&DebugPart { bytes, pos });
            pos = skip(bytes, pos);
        }
        d.finish()
    }

    fn fmt_struct(self, name: &str, num: usize, bytes: &[u8], mut pos: usize) -> fmt::Result {
        let mut d = self.f.debug_struct(name);
        for _ in 0..num {
            // SAFETY: `pos` is at a field key: the decoded struct header
            // leaves the cursor at the first key, and each `skip` past a
            // field's value lands on the next
            let key = unsafe { Cursor::at(bytes, pos).read_field_key() };
            let value = pos + mem::size_of::<&str>();

            d.field(key, &DebugPart { bytes, pos: value });
            pos = skip(bytes, value);
        }
        d.finish()
    }
}

impl<'a, 'f, 'i, 'de> PartVisitor<'i, 'de> for DebugVisitor<'a, 'f> {
    type Output = fmt::Result;

    fn visit_unit(self) -> fmt::Result {
        self.f.write_str("()")
    }

    fn visit_bool(self, v: bool) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_u8(self, v: u8) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_u16(self, v: u16) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_u32(self, v: u32) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_u64(self, v: u64) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_u128(self, v: u128) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_i8(self, v: i8) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_i16(self, v: i16) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_i32(self, v: i32) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_i64(self, v: i64) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_i128(self, v: i128) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_f32(self, v: f32) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_f64(self, v: f64) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_char(self, v: char) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_str(self, v: &'i str) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_borrowed_str(self, v: &'de str) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_bytes(self, v: &'i [u8]) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_borrowed_bytes(self, v: &'de [u8]) -> fmt::Result {
        fmt::Debug::fmt(&v, self.f)
    }

    fn visit_none(self) -> fmt::Result {
        self.f.write_str("None")
    }

    fn visit_some(self, cursor: &mut Cursor<'i, 'de>) -> fmt::Result {
        self.f
            .debug_tuple("Some")
            .field(&DebugPart {
                bytes: cursor.bytes(),
                pos: cursor.pos(),
            })
            .finish()
    }

    fn visit_unit_struct(self, name: &'static str) -> fmt::Result {
        self.f.write_str(name)
    }

    fn visit_newtype_struct(self, name: &'static str, cursor: &mut Cursor<'i, 'de>) -> fmt::Result {
        self.f
            .debug_tuple(name)
            .field(&DebugPart {
                bytes: cursor.bytes(),
                pos: cursor.pos(),
            })
            .finish()
    }

    fn visit_unit_variant(self, header: VariantHeader, _: &mut Cursor<'i, 'de>) -> fmt::Result {
        self.f.write_str(header.variant)
    }

    fn visit_newtype_variant(
        self,
        header: VariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> fmt::Result {
        self.f
            .debug_tuple(header.variant)
            .field(&DebugPart {
                bytes: cursor.bytes(),
                pos: cursor.pos(),
            })
            .finish()
    }

    fn visit_seq(self, header: SeqHeader, cursor: &mut Cursor<'i, 'de>) -> fmt::Result {
        let bytes = cursor.bytes();

        let mut d = self.f.debug_list();
        let mut pos = cursor.pos();
        for _ in 0..header.num {
            d.entry(&DebugPart { bytes, pos });
            pos = skip(bytes, pos);
        }
        d.finish()
    }

    fn visit_tuple(self, header: TupleHeader, cursor: &mut Cursor<'i, 'de>) -> fmt::Result {
        self.fmt_tuple("", header.num, cursor.bytes(), cursor.pos())
    }

    fn visit_map(self, header: MapHeader, cursor: &mut Cursor<'i, 'de>) -> fmt::Result {
        let bytes = cursor.bytes();

        let mut d = self.f.debug_map();
        let mut pos = cursor.pos();
        for _ in 0..header.num {
            let value = skip(bytes, pos);

            d.entry(&DebugPart { bytes, pos }, &DebugPart { bytes, pos: value });
            pos = skip(bytes, value);
        }
        d.finish()
    }

    fn visit_tuple_struct(
        self,
        header: TupleStructHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> fmt::Result {
        self.fmt_tuple(header.name, header.num, cursor.bytes(), cursor.pos())
    }

    fn visit_struct(self, header: StructHeader, cursor: &mut Cursor<'i, 'de>) -> fmt::Result {
        self.fmt_struct(header.name, header.num, cursor.bytes(), cursor.pos())
    }

    fn visit_tuple_variant(
        self,
        header: TupleVariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> fmt::Result {
        self.fmt_tuple(header.variant, header.num, cursor.bytes(), cursor.pos())
    }

    fn visit_struct_variant(
        self,
        header: StructVariantHeader,
        cursor: &mut Cursor<'i, 'de>,
    ) -> fmt::Result {
        self.fmt_struct(header.variant, header.num, cursor.bytes(), cursor.pos())
    }
}