rustbinary 0.1.7

//! # Compact schema-guided binary profile
//!
//! The **self-describing** profile (see `crate::ser` / `crate::decoder`)
//! trades compactness for dynamic flexibility: every value carries a one-byte
//! type tag, struct fields are written as named object keys, and containers
//! are `0xff`-terminated. For statically known types that overhead dominates:
//! a `Vec<u8>` becomes `array tag, element tag, byte, element tag, byte, …,
//! end tag`, and numeric arrays pay one tag per element.
//!
//! This module provides the complementary **compact** profile for statically
//! typed values. The encoder knows the schema at compile time, so the wire
//! carries **no type tags and no field names**; containers use length prefixes
//! instead of terminators; `Option<T>` is a single presence byte; enums write
//! only a compact variant discriminant. Dynamic `Value`s, untagged enums and
//! `FormatEncoder`-driven types stay on the self-describing profile and never
//! drag down the static path.
//!
//! The two layers are separate by design:
//!
//! - [`CompactEncode`] / [`CompactDecode`] — a hot path generated by the
//!   `#[derive(rustbinary::CompactBinary)]` macro (or hand-written) that
//!   encodes/decodes straight into the wire with no nextjson event dispatch,
//!   no field-name handling and no per-value tag match.
//! - [`nextjson::FormatEncoder`] / [`nextjson::FormatDecoder`] — the existing
//!   generic path, kept for dynamic and framework-neutral values.
//!
//! # Wire layout
//!
//! The compact profile is a **headerless**, length-prefixed stream. Integer
//! widths and byte order are fixed (canonical little-endian marker-varints,
//! little-endian floats) and do **not** follow the base [`crate::Config`]
//! `Endian` / `IntEncoding` knobs — this keeps the format stable and the fast
//! paths allocation-free. The base config's *resource* knobs still apply:
//! `limit`, `collection_limit`, `depth_limit` and `trailing`.
//!
//! ```text
//! unit ()            : (nothing)
//! bool               : 1 byte 0x00 | 0x01
//! u8 / i8            : 1 raw byte
//! u16..u128          : canonical marker varint (little endian)
//! i16..i128          : ZigZag marker varint (little endian)
//! f32 / f64          : 4 / 8 bytes, little endian
//! char               : varint code point
//! str / String       : varint byte_len + UTF-8 bytes
//! &[u8] / Vec<u8>    : varint len + raw bytes          (memcpy fast path)
//! Vec<u16/u32/u64>   : varint len + tight varint loop
//! Vec<i16/i32/i64>   : varint len + tight ZigZag loop
//! Vec<f32/f64>       : varint len + bulk little-endian payload
//! Option<T>          : 1 byte 0x00 (None) | 0x01 (Some) + T
//! Vec<T> / &[T]      : varint len + elements
//! [T; N]             : N elements (no length prefix)
//! tuple              : elements in declaration order
//! map<K, V>          : varint len + (K V) pairs
//! enum               : varint discriminant + variant payload
//! ```
//!
//! Struct fields are written in declaration order with no names; both sides
//! must share the same schema. For cross-version evolution use
//! [`crate::Config::with_schema_evolution`] (stable numeric field IDs) and for
//! schema-identity verification use [`crate::Config::with_fingerprint`] — both
//! compose with this profile through `with_compact_format()`.
//!
//! # Example
//!
//! ```
//! use nextjson::{NsonDeserialize, NsonSerialize};
//!
//! #[derive(Debug, PartialEq, NsonSerialize, NsonDeserialize, rustbinary::CompactBinary)]
//! struct Packet {
//!     sequence: u64,
//!     payload: Vec<u8>,
//! }
//!
//! let packet = Packet { sequence: 42, payload: b"hello".to_vec() };
//! // Compact path (schema-known direct codec).
//! let bytes = rustbinary::options().with_compact_format().serialize(&packet)?;
//! let decoded: Packet = rustbinary::options().with_compact_format().deserialize(&bytes)?;
//! assert_eq!(decoded, packet);
//! // The self-describing path still round-trips the same value.
//! let sdes = rustbinary::options().serialize(&packet)?;
//! assert_eq!(rustbinary::options().deserialize::<Packet>(&sdes)?, packet);
//! # Ok::<(), rustbinary::Error>(())
//! ```
//!
//! # Safety model
//!
//! The bulk fast paths reinterpret byte slices as `f64`/`f32`/`i8` slices only
//! after a compile-time-eliminated `type_equal` check and (on decode) an
//! alignment check, exactly like bincode 3's slice fast path. Every cast is
//! documented at its site and is read-only. The **general** `repr(Rust)`
//! object-to-bytes cast remains unsupported: users must keep that boundary.

use alloc::{
    collections::{BTreeMap, VecDeque},
    string::String,
    vec::Vec,
};

#[cfg(feature = "std")]
use std::collections::HashMap;

use crate::{
    canonical::{decode_varint_le, encode_varint_le, zigzag_decode, zigzag_encode},
    config::{Config, TrailingBytes},
    error::{Error, Result},
    tags::{MARKER_U128, MARKER_U16, MARKER_U32, MARKER_U64},
    writer::{CountWriter, EncodeWriter, SliceWriter},
};

// ---------------------------------------------------------------------------
// Public contracts
// ---------------------------------------------------------------------------

/// Schema-known compact encoder (hot path).
///
/// Generated by `#[derive(rustbinary::CompactBinary)]` for structs and enums
/// and implemented for all supported standard types. The encoding is driven by
/// the static type — no type tags, no field names, length-prefixed containers.
pub trait CompactEncode {
    /// Writes this value's compact wire form into `writer`.
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()>;
}

/// Schema-known compact decoder (hot path).
///
/// Implementations read from `cursor`, which owns the input lifetime `'de`, so
/// borrowed targets (`&'de str`, `&'de [u8]`) point directly into the input.
pub trait CompactDecode<'de>: Sized {
    /// Reads one value of this type from `cursor`.
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self>;
}

/// Compact-profile configuration, produced by [`Config::with_compact_format`].
///
/// Carries over the base config's resource policies (`limit`,
/// `collection_limit`, `depth_limit`, `trailing`) and ignores its byte-order /
/// integer-width knobs: the compact wire is always little-endian
/// marker-varint.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct CompactConfig {
    base: Config,
}

impl CompactConfig {
    pub(crate) const fn new(base: Config) -> Self {
        Self { base }
    }

    /// Returns the underlying resource-policy configuration.
    pub const fn base_config(self) -> Config {
        self.base
    }

    /// Always [`crate::BinaryProfile::CompactSchema`].
    pub const fn profile(self) -> crate::BinaryProfile {
        crate::BinaryProfile::CompactSchema
    }

    /// Serializes `value` into a fresh vector using the compact profile.
    pub fn serialize<T: CompactEncode + ?Sized>(self, value: &T) -> Result<Vec<u8>> {
        let mut output = Vec::new();
        {
            let mut writer = BoundedWriter::new(&mut output, self.base);
            value.encode_compact(&mut writer)?;
        }
        Ok(output)
    }

    /// Serializes into a caller-owned slice.
    ///
    /// On undersized output the written prefix is preserved and the error
    /// reports the exact required capacity.
    pub fn serialize_into_slice<T: CompactEncode + ?Sized>(
        self,
        output: &mut [u8],
        value: &T,
    ) -> Result<usize> {
        let mut writer = SliceWriter::new(output);
        {
            let mut bounded = BoundedWriter::new(&mut writer, self.base);
            value.encode_compact(&mut bounded)?;
        }
        writer.finish()
    }

    /// Computes the exact compact byte count without retaining output.
    pub fn serialized_size<T: CompactEncode + ?Sized>(self, value: &T) -> Result<u64> {
        let mut writer = CountWriter::new();
        value.encode_compact(&mut writer)?;
        Ok(writer.written())
    }

    /// Deserializes one compact value that may borrow from `input`.
    pub fn deserialize<'de, T: CompactDecode<'de>>(self, input: &'de [u8]) -> Result<T> {
        let mut cursor = CompactCursor::new(input, self.base);
        let value = T::decode_compact(&mut cursor)?;
        if self.base.trailing == TrailingBytes::Reject && cursor.position() != input.len() {
            return Err(Error::TrailingBytes {
                remaining: input.len() - cursor.position(),
            });
        }
        Ok(value)
    }
}

/// Bounded encoder sink used by [`CompactConfig`].
///
/// Enforces the base config's byte limit per write and its depth limit per
/// container, so hostile in-memory values cannot grow output past the policy.
struct BoundedWriter<W> {
    inner: W,
    limit: Option<u64>,
    depth_limit: usize,
    written: u64,
    depth: usize,
}

impl<W: EncodeWriter> BoundedWriter<W> {
    fn new(inner: W, config: Config) -> Self {
        Self {
            inner,
            limit: config.limit,
            depth_limit: config.depth_limit,
            written: 0,
            depth: 0,
        }
    }
}

impl<W: EncodeWriter> EncodeWriter for BoundedWriter<W> {
    fn write_all(&mut self, bytes: &[u8]) -> Result<()> {
        let amount =
            u64::try_from(bytes.len()).map_err(|_| Error::IntegerOverflow { target: "u64" })?;
        let next = self
            .written
            .checked_add(amount)
            .ok_or(Error::SizeLimit { limit: u64::MAX })?;
        if let Some(limit) = self.limit {
            if next > limit {
                return Err(Error::SizeLimit { limit });
            }
        }
        self.inner.write_all(bytes)?;
        self.written = next;
        Ok(())
    }

    fn enter_container(&mut self) -> Result<()> {
        if self.depth >= self.depth_limit {
            return Err(Error::Custom(
                "compact encode nesting depth limit exceeded".into(),
            ));
        }
        self.depth += 1;
        Ok(())
    }

    fn exit_container(&mut self) {
        debug_assert!(self.depth > 0);
        self.depth -= 1;
    }
}

// ---------------------------------------------------------------------------
// Compile-time type equality (dtolnay's non-static TypeId trick)
// ---------------------------------------------------------------------------

/// Compile-time type equality used to select bulk fast paths inside generic
/// container impls. The branch is constant after inlining and is eliminated at
/// monomorphization. `Target` must be a `'static` primitive; comparing against
/// lifetime-parameterized types is deliberately unsupported (see `unty`).
///
/// This is the same construction shipped in `unty` and used by bincode 3.
#[doc(hidden)]
pub fn __type_equal<Src: ?Sized, Target: ?Sized>() -> bool {
    non_static_type_id::<Src>() == non_static_type_id::<Target>()
}

fn non_static_type_id<T: ?Sized>() -> core::any::TypeId {
    trait NonStaticAny {
        fn get_type_id(&self) -> core::any::TypeId
        where
            Self: 'static;
    }

    impl<T: ?Sized> NonStaticAny for core::marker::PhantomData<T> {
        fn get_type_id(&self) -> core::any::TypeId
        where
            Self: 'static,
        {
            core::any::TypeId::of::<T>()
        }
    }

    // SAFETY: `get_type_id` never touches the (zero-sized) value — it only
    // reads `TypeId::of::<T>()`, a compile-time constant. Erasing the
    // (irrelevant) lifetime through the well-known dtolnay trick therefore
    // cannot cause any aliasing or value access; the reference is only used
    // to select the `'static`-bounded method. Identical to `unty`'s
    // `non_static_type_id`.
    let phantom = core::marker::PhantomData::<T>;
    unsafe {
        core::mem::transmute::<&dyn NonStaticAny, &(dyn NonStaticAny + 'static)>(&phantom)
            .get_type_id()
    }
}

// ---------------------------------------------------------------------------
// Encoding primitives
// ---------------------------------------------------------------------------

/// Writes a canonical little-endian marker-varint (`u64`).
#[inline]
pub(crate) fn encode_varint<W: EncodeWriter + ?Sized>(writer: &mut W, value: u64) -> Result<()> {
    let (bytes, len) = encode_varint_le(value as u128);
    writer.write_all(&bytes[..len])
}

/// Writes a canonical little-endian marker-varint (`u128`).
#[inline]
pub(crate) fn encode_varint_u128<W: EncodeWriter + ?Sized>(
    writer: &mut W,
    value: u128,
) -> Result<()> {
    let (bytes, len) = encode_varint_le(value);
    writer.write_all(&bytes[..len])
}

/// Writes a ZigZag marker-varint (`i64`).
#[inline]
pub(crate) fn encode_zigzag<W: EncodeWriter + ?Sized>(writer: &mut W, value: i64) -> Result<()> {
    encode_varint_u128(writer, zigzag_encode(value as i128))
}

/// Writes a single presence/boolean byte.
#[inline]
pub(crate) fn encode_bool<W: EncodeWriter + ?Sized>(writer: &mut W, value: bool) -> Result<()> {
    writer.write_all(&[value as u8])
}

/// Writes a collection/string length prefix.
#[inline]
pub(crate) fn encode_length<W: EncodeWriter + ?Sized>(writer: &mut W, len: usize) -> Result<()> {
    let len = u64::try_from(len).map_err(|_| Error::IntegerOverflow { target: "u64" })?;
    encode_varint(writer, len)
}

/// Writes a length-prefixed byte string (length + raw bytes).
#[inline]
pub(crate) fn encode_bytes<W: EncodeWriter + ?Sized>(writer: &mut W, bytes: &[u8]) -> Result<()> {
    encode_length(writer, bytes.len())?;
    writer.write_all(bytes)
}

/// Writes a length-prefixed element slice, selecting the memcpy / bulk
/// endianness fast paths for byte and float elements.
pub(crate) fn encode_slice<W: EncodeWriter + ?Sized, T: CompactEncode>(
    writer: &mut W,
    values: &[T],
) -> Result<()> {
    encode_length(writer, values.len())?;
    writer.enter_container()?;
    let outcome = encode_elements(writer, values);
    writer.exit_container();
    outcome
}

fn encode_elements<W: EncodeWriter + ?Sized, T: CompactEncode>(
    writer: &mut W,
    values: &[T],
) -> Result<()> {
    if __type_equal::<T, u8>() || __type_equal::<T, i8>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T` is `u8`
        // or `i8`, both 1-byte plain-data types whose in-memory bytes are the
        // wire form (little endian is irrelevant at 8 bits). This is exactly
        // bincode 3's slice fast path and is read-only.
        let bytes =
            unsafe { core::slice::from_raw_parts(values.as_ptr().cast::<u8>(), values.len()) };
        return writer.write_all(bytes);
    }
    if __type_equal::<T, f64>() {
        // SAFETY: this branch only runs when `T == f64`; `&[T]` and `&[f64]`
        // are both fat pointers of identical layout, so the transmute is an
        // identity on the reference itself.
        let values: &[f64] = unsafe { core::mem::transmute(values) };
        return write_f64_slice_le(writer, values);
    }
    if __type_equal::<T, f32>() {
        // SAFETY: see the `f64` branch; `T == f32` here.
        let values: &[f32] = unsafe { core::mem::transmute(values) };
        return write_f32_slice_le(writer, values);
    }
    if __type_equal::<T, u64>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T == u64`.
        let values: &[u64] = unsafe { core::mem::transmute(values) };
        return encode_varints_bulk(writer, values.iter().copied());
    }
    if __type_equal::<T, i64>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T == i64`.
        let values: &[i64] = unsafe { core::mem::transmute(values) };
        return encode_varints_bulk(
            writer,
            values.iter().map(|&v| zigzag_encode(v as i128) as u64),
        );
    }
    if __type_equal::<T, u32>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T == u32`.
        let values: &[u32] = unsafe { core::mem::transmute(values) };
        return encode_varints_bulk(writer, values.iter().map(|&v| v as u64));
    }
    if __type_equal::<T, i32>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T == i32`.
        let values: &[i32] = unsafe { core::mem::transmute(values) };
        return encode_varints_bulk(
            writer,
            values.iter().map(|&v| zigzag_encode(v as i128) as u64),
        );
    }
    if __type_equal::<T, u16>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T == u16`.
        let values: &[u16] = unsafe { core::mem::transmute(values) };
        return encode_varints_bulk(writer, values.iter().map(|&v| v as u64));
    }
    if __type_equal::<T, i16>() {
        // SAFETY: the compile-time-eliminated branch guarantees `T == i16`.
        let values: &[i16] = unsafe { core::mem::transmute(values) };
        return encode_varints_bulk(
            writer,
            values.iter().map(|&v| zigzag_encode(v as i128) as u64),
        );
    }
    for value in values {
        value.encode_compact(writer)?;
    }
    Ok(())
}

/// Encodes an iterator of `u64` values as canonical marker-varints, batching
/// them through a small stack buffer.
///
/// The writer (and its per-write limit and growth checks) is called once per
/// batch instead of once per element, which is the dominant cost for numeric
/// arrays. Batches never overshoot the byte limit: the writer still rejects a
/// batch that would cross it.
fn encode_varints_bulk<W: EncodeWriter + ?Sized>(
    writer: &mut W,
    values: impl Iterator<Item = u64>,
) -> Result<()> {
    let mut buffer = [0u8; 64];
    let mut used = 0usize;
    for value in values {
        // Every varint needs at most 17 bytes; flush when the next one would
        // not fit so `write_varint_into` can index the buffer directly.
        if used + 17 > buffer.len() {
            writer.write_all(&buffer[..used])?;
            used = 0;
        }
        used += write_varint_into(&mut buffer[used..], value);
    }
    if used > 0 {
        writer.write_all(&buffer[..used])?;
    }
    Ok(())
}

/// Writes a `f64` slice as one bulk little-endian payload when the target is
/// little-endian; otherwise per-value byte swaps.
fn write_f64_slice_le<W: EncodeWriter + ?Sized>(writer: &mut W, values: &[f64]) -> Result<()> {
    if cfg!(target_endian = "little") {
        let byte_len = values
            .len()
            .checked_mul(core::mem::size_of::<f64>())
            .ok_or(Error::IntegerOverflow { target: "usize" })?;
        // SAFETY: `f64` is a plain-data type (no padding, no invalid bit
        // patterns); on a little-endian target its in-memory representation
        // already is the wire form. The cast is read-only.
        let bytes = unsafe { core::slice::from_raw_parts(values.as_ptr().cast::<u8>(), byte_len) };
        writer.write_all(bytes)
    } else {
        for value in values {
            writer.write_all(&value.to_le_bytes())?;
        }
        Ok(())
    }
}

/// Writes a `f32` slice as one bulk little-endian payload when the target is
/// little-endian; otherwise per-value byte swaps.
fn write_f32_slice_le<W: EncodeWriter + ?Sized>(writer: &mut W, values: &[f32]) -> Result<()> {
    if cfg!(target_endian = "little") {
        let byte_len = values
            .len()
            .checked_mul(core::mem::size_of::<f32>())
            .ok_or(Error::IntegerOverflow { target: "usize" })?;
        // SAFETY: `f32` is a plain-data type (no padding, no invalid bit
        // patterns); on a little-endian target its in-memory representation
        // already is the wire form. The cast is read-only.
        let bytes = unsafe { core::slice::from_raw_parts(values.as_ptr().cast::<u8>(), byte_len) };
        writer.write_all(bytes)
    } else {
        for value in values {
            writer.write_all(&value.to_le_bytes())?;
        }
        Ok(())
    }
}

/// Writes a `u128`-backed ZigZag value (used by the `i128` implementation).
fn encode_zigzag_i128<W: EncodeWriter + ?Sized>(writer: &mut W, value: i128) -> Result<()> {
    encode_varint_u128(writer, zigzag_encode(value))
}

/// Length of the leading run of single-byte varints (`byte ≤ 250`) in `input`.
///
/// Lets the bulk decoders consume numeric arrays as contiguous byte runs with
/// one bounds check per run instead of per element.
fn plain_varint_prefix(input: &[u8]) -> usize {
    #[cfg(feature = "simd")]
    return crate::simd::plain_varint_prefix(input);
    #[cfg(not(feature = "simd"))]
    input.iter().take_while(|&&byte| byte <= 250).count()
}

/// Writes one canonical marker-varint into `buffer`, which must have at least
/// 17 bytes free, and returns the number of bytes written.
///
/// Mirrors [`crate::canonical::encode_varint_le`] without materializing the
/// 17-byte temporary array; the drift-guard tests prove byte-identical output.
#[inline]
fn write_varint_into(buffer: &mut [u8], value: u64) -> usize {
    if value <= 250 {
        buffer[0] = value as u8;
        1
    } else if value <= 0xffff {
        buffer[0] = MARKER_U16;
        buffer[1..3].copy_from_slice(&(value as u16).to_le_bytes());
        3
    } else if value <= 0xffff_ffff {
        buffer[0] = MARKER_U32;
        buffer[1..5].copy_from_slice(&(value as u32).to_le_bytes());
        5
    } else {
        // `value` is a `u64`, so the widest reachable form is the 8-byte
        // payload; the 16-byte form is only produced by the `u128` writer.
        buffer[0] = MARKER_U64;
        buffer[1..9].copy_from_slice(&value.to_le_bytes());
        9
    }
}

// ---------------------------------------------------------------------------
// Decoder cursor
// ---------------------------------------------------------------------------

/// Bounded cursor over the compact wire input.
///
/// Owns the input lifetime `'de` so borrowed targets can point directly into
/// the input. All reads enforce the byte limit; collection lengths are checked
/// against the collection limit and nesting against the depth limit.
pub struct CompactCursor<'de> {
    input: &'de [u8],
    position: usize,
    /// Hard byte boundary for reads, when a per-read check is required.
    ///
    /// `None` when the input is no larger than the configured limit (or no
    /// limit is set): plain slice bounds then already enforce the byte limit,
    /// so the hot loops carry a loop-invariant branch that the compiler
    /// hoists away instead of a per-element limit check.
    limit_end: Option<usize>,
    collection_limit: Option<u64>,
    depth_limit: usize,
    depth: usize,
}

impl<'de> CompactCursor<'de> {
    pub(crate) fn new(input: &'de [u8], config: Config) -> Self {
        let limit_end = config.limit.and_then(|limit| {
            usize::try_from(limit)
                .ok()
                .filter(|&limit| input.len() > limit)
        });
        Self {
            input,
            position: 0,
            limit_end,
            collection_limit: config.collection_limit,
            depth_limit: config.depth_limit,
            depth: 0,
        }
    }

    /// Enforces the byte limit at `end`, returning the configured limit on
    /// overflow. `limit_end` is `None` in the common case, so this inlines to
    /// nothing after the compiler hoists the invariant branch.
    #[inline(always)]
    fn enforce_limit(&self, end: usize) -> Result<()> {
        if let Some(end_limit) = self.limit_end {
            if end > end_limit {
                return Err(Error::SizeLimit {
                    limit: end_limit as u64,
                });
            }
        }
        Ok(())
    }

    /// The number of bytes consumed so far.
    pub const fn position(&self) -> usize {
        self.position
    }

    /// The number of bytes remaining.
    pub const fn remaining(&self) -> usize {
        self.input.len() - self.position
    }

    /// Takes `len` bytes, enforcing the byte limit.
    #[inline]
    fn take(&mut self, len: usize) -> Result<&'de [u8]> {
        let end = self.position.checked_add(len).ok_or(Error::UnexpectedEnd)?;
        self.enforce_limit(end)?;
        let bytes = self
            .input
            .get(self.position..end)
            .ok_or(Error::UnexpectedEnd)?;
        self.position = end;
        Ok(bytes)
    }

    /// Advances past one byte that `self.input[position]` is known to hold.
    ///
    /// Inlined into the single-byte decode fast paths so the dominant case
    /// (values ≤ 250, booleans, bytes) never builds a range slice.
    #[inline]
    fn advance_one(&mut self, position: usize) -> Result<()> {
        let end = position + 1;
        self.enforce_limit(end)?;
        self.position = end;
        Ok(())
    }

    /// Reads one raw byte.
    #[inline]
    pub(crate) fn byte(&mut self) -> Result<u8> {
        let position = self.position;
        match self.input.get(position) {
            Some(&byte) => {
                self.advance_one(position)?;
                Ok(byte)
            }
            None => Err(Error::UnexpectedEnd),
        }
    }

    /// Reads a canonical marker-varint as `u64`.
    ///
    /// The single-byte case (`value ≤ 250`) is inlined so numeric-array hot
    /// loops pay one bounds check and one branch per element, not the full
    /// `take` machinery.
    #[inline]
    pub(crate) fn read_varint(&mut self) -> Result<u64> {
        let position = self.position;
        match self.input.get(position) {
            None => Err(Error::UnexpectedEnd),
            Some(&marker) if marker <= 250 => {
                self.advance_one(position)?;
                Ok(marker as u64)
            }
            Some(&marker) => {
                // `position < input.len()` and the widths are ≤ 17, so the
                // sum cannot overflow (slices are capped at `isize::MAX`).
                let end = position
                    + match marker {
                        MARKER_U16 => 3,
                        MARKER_U32 => 5,
                        MARKER_U64 => 9,
                        MARKER_U128 => 17,
                        other => return Err(Error::InvalidVarintMarker(other)),
                    };
                self.enforce_limit(end)?;
                let bytes = self
                    .input
                    .get(position + 1..end)
                    .ok_or(Error::UnexpectedEnd)?;
                self.position = end;
                let value = decode_varint_le(marker, bytes).ok_or(Error::NonCanonicalVarint)?;
                u64::try_from(value).map_err(|_| Error::IntegerOverflow { target: "u64" })
            }
        }
    }

    /// Reads a canonical marker-varint as `u128`.
    #[inline]
    pub(crate) fn read_varint_u128(&mut self) -> Result<u128> {
        let position = self.position;
        match self.input.get(position) {
            None => Err(Error::UnexpectedEnd),
            Some(&marker) if marker <= 250 => {
                self.advance_one(position)?;
                Ok(marker as u128)
            }
            Some(&marker) => {
                // `position < input.len()` and the widths are ≤ 17, so the
                // sum cannot overflow (slices are capped at `isize::MAX`).
                let end = position
                    + match marker {
                        MARKER_U16 => 3,
                        MARKER_U32 => 5,
                        MARKER_U64 => 9,
                        MARKER_U128 => 17,
                        other => return Err(Error::InvalidVarintMarker(other)),
                    };
                self.enforce_limit(end)?;
                let bytes = self
                    .input
                    .get(position + 1..end)
                    .ok_or(Error::UnexpectedEnd)?;
                self.position = end;
                decode_varint_le(marker, bytes).ok_or(Error::NonCanonicalVarint)
            }
        }
    }

    /// Reads a ZigZag marker-varint as `i64` (range-checked).
    #[inline]
    pub(crate) fn read_zigzag(&mut self) -> Result<i64> {
        let encoded = self.read_varint_u128()?;
        let value = zigzag_decode(encoded);
        i64::try_from(value).map_err(|_| Error::IntegerOverflow { target: "i64" })
    }

    /// Reads a ZigZag marker-varint as `i128`.
    #[inline]
    pub(crate) fn read_zigzag_i128(&mut self) -> Result<i128> {
        Ok(zigzag_decode(self.read_varint_u128()?))
    }

    /// Reads a one-byte boolean.
    #[inline]
    pub(crate) fn read_bool(&mut self) -> Result<bool> {
        match self.byte()? {
            0 => Ok(false),
            1 => Ok(true),
            other => Err(Error::InvalidBool(other)),
        }
    }

    /// Reads a little-endian `f32`.
    #[inline]
    pub(crate) fn read_f32(&mut self) -> Result<f32> {
        let bytes = self.take(4)?;
        Ok(f32::from_le_bytes(bytes.try_into().expect("fixed width")))
    }

    /// Reads a little-endian `f64`.
    #[inline]
    pub(crate) fn read_f64(&mut self) -> Result<f64> {
        let bytes = self.take(8)?;
        Ok(f64::from_le_bytes(bytes.try_into().expect("fixed width")))
    }

    /// Reads a collection length as `usize`.
    #[inline]
    pub(crate) fn read_length(&mut self) -> Result<usize> {
        let value = self.read_varint()?;
        usize::try_from(value).map_err(|_| Error::IntegerOverflow { target: "usize" })
    }

    /// Reads `len` raw bytes (bounded by the byte limit).
    #[inline]
    pub(crate) fn read_bytes(&mut self, len: usize) -> Result<&'de [u8]> {
        self.take(len)
    }

    /// Reads a length-prefixed UTF-8 string, borrowing the input.
    #[inline]
    pub(crate) fn read_str(&mut self) -> Result<&'de str> {
        let len = self.read_length()?;
        let bytes = self.take(len)?;
        core::str::from_utf8(bytes).map_err(Error::InvalidUtf8)
    }

    /// Validates and books a length-prefixed container.
    ///
    /// Applies the collection limit to `len` and increments the nesting depth
    /// (guarding against adversarial deep nesting). The matching
    /// [`exit_container`](CompactCursor::exit_container) must be called after
    /// the element loop.
    #[inline]
    pub(crate) fn enter_container(&mut self, len: usize) -> Result<()> {
        if let Some(limit) = self.collection_limit {
            if len as u64 > limit {
                return Err(Error::CollectionLimit { limit });
            }
        }
        if self.depth >= self.depth_limit {
            return Err(Error::Custom(
                "compact decode nesting depth limit exceeded".into(),
            ));
        }
        self.depth += 1;
        Ok(())
    }

    /// Bulk-decodes `len` marker-varints into a fresh vector.
    ///
    /// Contiguous runs of single-byte varints (`value ≤ 250`) are consumed as
    /// a contiguous byte run — one bounds check per run instead of per
    /// element — which is the dominant shape of numeric arrays in practice.
    /// Multi-byte varints are decoded with the marker fetched exactly once, so
    /// all-multi-byte data costs the same as the per-element reader.
    pub(crate) fn read_varints_bulk(&mut self, len: usize) -> Result<Vec<u64>> {
        let mut out = Vec::new();
        out.try_reserve_exact(len)
            .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
        let mut remaining = len;
        while remaining > 0 {
            let position = self.position;
            match self.input.get(position) {
                None => return Err(Error::UnexpectedEnd),
                Some(&marker) if marker <= 250 => {
                    // Consume the whole plain run (at least this byte).
                    let available = &self.input[position + 1..];
                    let window = &available[..(remaining - 1).min(available.len())];
                    let extra = plain_varint_prefix(window).min(remaining - 1);
                    let end = position + 1 + extra;
                    self.enforce_limit(end)?;
                    for &byte in &self.input[position..end] {
                        out.push(byte as u64);
                    }
                    self.position = end;
                    remaining -= 1 + extra;
                }
                Some(&marker) => {
                    // `position < input.len()` and the widths are ≤ 17, so the
                    // sum cannot overflow (slices are capped at `isize::MAX`).
                    let end = position
                        + match marker {
                            MARKER_U16 => 3,
                            MARKER_U32 => 5,
                            MARKER_U64 => 9,
                            MARKER_U128 => 17,
                            other => return Err(Error::InvalidVarintMarker(other)),
                        };
                    self.enforce_limit(end)?;
                    let bytes = self
                        .input
                        .get(position + 1..end)
                        .ok_or(Error::UnexpectedEnd)?;
                    let value = decode_varint_le(marker, bytes).ok_or(Error::NonCanonicalVarint)?;
                    out.push(
                        u64::try_from(value)
                            .map_err(|_| Error::IntegerOverflow { target: "u64" })?,
                    );
                    self.position = end;
                    remaining -= 1;
                }
            }
        }
        Ok(out)
    }

    /// Leaves the innermost length-prefixed container.
    #[inline]
    pub(crate) fn exit_container(&mut self) {
        debug_assert!(self.depth > 0);
        self.depth -= 1;
    }
}

/// Bulk `f64` conversion honoring alignment; falls back to per-value
/// `from_le_bytes` when the input slice is not 8-byte aligned.
fn read_f64_vec(cursor: &mut CompactCursor<'_>, len: usize) -> Result<Vec<f64>> {
    let byte_len = len
        .checked_mul(core::mem::size_of::<f64>())
        .ok_or(Error::IntegerOverflow { target: "usize" })?;
    let bytes = cursor.read_bytes(byte_len)?;
    let mut out = Vec::new();
    out.try_reserve_exact(len)
        .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
    if cfg!(target_endian = "little")
        && (bytes.as_ptr() as usize).is_multiple_of(core::mem::align_of::<f64>())
    {
        // SAFETY: `f64` has no invalid bit patterns and no padding; the
        // alignment check above makes the cast sound, and the target is
        // little-endian so the bytes already are the values. Read-only.
        let values = unsafe { core::slice::from_raw_parts(bytes.as_ptr().cast::<f64>(), len) };
        out.copy_from_slice(values);
    } else {
        for chunk in bytes.chunks_exact(core::mem::size_of::<f64>()) {
            out.push(f64::from_le_bytes(
                chunk.try_into().expect("chunks_exact yields 8 bytes"),
            ));
        }
    }
    Ok(out)
}

/// Bulk `f32` conversion honoring alignment; falls back to per-value
/// `from_le_bytes` when the input slice is not 4-byte aligned.
fn read_f32_vec(cursor: &mut CompactCursor<'_>, len: usize) -> Result<Vec<f32>> {
    let byte_len = len
        .checked_mul(core::mem::size_of::<f32>())
        .ok_or(Error::IntegerOverflow { target: "usize" })?;
    let bytes = cursor.read_bytes(byte_len)?;
    let mut out = Vec::new();
    out.try_reserve_exact(len)
        .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
    if cfg!(target_endian = "little")
        && (bytes.as_ptr() as usize).is_multiple_of(core::mem::align_of::<f32>())
    {
        // SAFETY: `f32` has no invalid bit patterns and no padding; the
        // alignment check above makes the cast sound, and the target is
        // little-endian so the bytes already are the values. Read-only.
        let values = unsafe { core::slice::from_raw_parts(bytes.as_ptr().cast::<f32>(), len) };
        out.copy_from_slice(values);
    } else {
        for chunk in bytes.chunks_exact(core::mem::size_of::<f32>()) {
            out.push(f32::from_le_bytes(
                chunk.try_into().expect("chunks_exact yields 4 bytes"),
            ));
        }
    }
    Ok(out)
}

// ---------------------------------------------------------------------------
// Hidden helpers for macro-generated code
// ---------------------------------------------------------------------------

/// Writes an enum variant discriminant (macro-generated code).
#[doc(hidden)]
pub fn encode_variant_index<W: EncodeWriter + ?Sized>(writer: &mut W, index: u32) -> Result<()> {
    encode_varint(writer, index as u64)
}

/// Reads an enum variant discriminant (macro-generated code).
#[doc(hidden)]
pub fn decode_variant_index(cursor: &mut CompactCursor<'_>) -> Result<u32> {
    let index = cursor.read_varint()?;
    u32::try_from(index).map_err(|_| Error::IntegerOverflow { target: "u32" })
}

/// Builds an `Error::Custom` from a static message (macro-generated code).
#[doc(hidden)]
pub fn __err_static(message: &'static str) -> Error {
    Error::Custom(crate::error::__custom_message(message))
}

// ---------------------------------------------------------------------------
// Primitive implementations
// ---------------------------------------------------------------------------

impl CompactEncode for () {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, _writer: &mut W) -> Result<()> {
        Ok(())
    }
}

impl<'de> CompactDecode<'de> for () {
    #[inline]
    fn decode_compact(_cursor: &mut CompactCursor<'de>) -> Result<Self> {
        Ok(())
    }
}

impl CompactEncode for bool {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_bool(writer, *self)
    }
}

impl<'de> CompactDecode<'de> for bool {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        cursor.read_bool()
    }
}

impl CompactEncode for u8 {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        writer.write_all(&[*self])
    }
}

impl<'de> CompactDecode<'de> for u8 {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        cursor.byte()
    }
}

impl CompactEncode for i8 {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        writer.write_all(&[*self as u8])
    }
}

impl<'de> CompactDecode<'de> for i8 {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        Ok(cursor.byte()? as i8)
    }
}

macro_rules! impl_unsigned_varint {
    ($($ty:ty => $name:literal),+ $(,)?) => {$(
        impl CompactEncode for $ty {
            #[inline]
            fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
                encode_varint(writer, *self as u64)
            }
        }
        impl<'de> CompactDecode<'de> for $ty {
            #[inline]
            fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
                let value = cursor.read_varint()?;
                <$ty>::try_from(value)
                    .map_err(|_| Error::IntegerOverflow { target: $name })
            }
        }
    )+};
}

impl_unsigned_varint!(u16 => "u16", u32 => "u32", u64 => "u64");

impl CompactEncode for u128 {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_varint_u128(writer, *self)
    }
}

impl<'de> CompactDecode<'de> for u128 {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        cursor.read_varint_u128()
    }
}

macro_rules! impl_signed_zigzag {
    ($($ty:ty => $name:literal),+ $(,)?) => {$(
        impl CompactEncode for $ty {
            #[inline]
            fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
                encode_zigzag(writer, *self as i64)
            }
        }
        impl<'de> CompactDecode<'de> for $ty {
            #[inline]
            fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
                let value = cursor.read_zigzag()?;
                <$ty>::try_from(value)
                    .map_err(|_| Error::IntegerOverflow { target: $name })
            }
        }
    )+};
}

impl_signed_zigzag!(i16 => "i16", i32 => "i32", i64 => "i64");

impl CompactEncode for i128 {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_zigzag_i128(writer, *self)
    }
}

impl<'de> CompactDecode<'de> for i128 {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        cursor.read_zigzag_i128()
    }
}

impl CompactEncode for f32 {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        writer.write_all(&self.to_le_bytes())
    }
}

impl<'de> CompactDecode<'de> for f32 {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        cursor.read_f32()
    }
}

impl CompactEncode for f64 {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        writer.write_all(&self.to_le_bytes())
    }
}

impl<'de> CompactDecode<'de> for f64 {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        cursor.read_f64()
    }
}

impl CompactEncode for char {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_varint(writer, *self as u32 as u64)
    }
}

impl<'de> CompactDecode<'de> for char {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
        let value = u32::try_from(cursor.read_varint()?)
            .map_err(|_| Error::IntegerOverflow { target: "u32" })?;
        char::from_u32(value).ok_or(Error::InvalidChar)
    }
}

// ---------------------------------------------------------------------------
// Strings and byte strings
// ---------------------------------------------------------------------------

impl CompactEncode for str {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_bytes(writer, self.as_bytes())
    }
}

impl CompactEncode for &str {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_bytes(writer, self.as_bytes())
    }
}

impl CompactEncode for String {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_bytes(writer, self.as_bytes())
    }
}

impl<'de, 'a> CompactDecode<'de> for &'a str
where
    'de: 'a,
{
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<&'a str> {
        cursor.read_str()
    }
}

impl<'de> CompactDecode<'de> for String {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<String> {
        Ok(cursor.read_str()?.into())
    }
}

impl<'de, 'a> CompactDecode<'de> for &'a [u8]
where
    'de: 'a,
{
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<&'a [u8]> {
        let len = cursor.read_length()?;
        cursor.read_bytes(len)
    }
}

// ---------------------------------------------------------------------------
// Sequences and mappings
// ---------------------------------------------------------------------------

impl<T: CompactEncode> CompactEncode for [T] {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_slice(writer, self)
    }
}

impl<T: CompactEncode> CompactEncode for Vec<T> {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_slice(writer, self.as_slice())
    }
}

impl<T: CompactEncode> CompactEncode for &[T] {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_slice(writer, self)
    }
}

impl<'de, T: CompactDecode<'de>> CompactDecode<'de> for Vec<T> {
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Vec<T>> {
        let len = cursor.read_length()?;
        cursor.enter_container(len)?;
        let outcome: Result<Vec<T>> = (|| {
            if __type_equal::<T, u8>() {
                let bytes = cursor.read_bytes(len)?;
                let mut out = Vec::new();
                out.try_reserve_exact(len)
                    .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
                out.extend_from_slice(bytes);
                // SAFETY: this branch is compile-time eliminated unless
                // `T == u8`; `Vec<u8>` and `Vec<T>` then share layout.
                return Ok(unsafe { core::mem::transmute::<Vec<u8>, Vec<T>>(out) });
            }
            if __type_equal::<T, i8>() {
                let bytes = cursor.read_bytes(len)?;
                // SAFETY: `T == i8` (eliminated branch); `i8` has no invalid
                // bit patterns and 1-byte alignment.
                let values = unsafe {
                    core::slice::from_raw_parts(bytes.as_ptr().cast::<i8>(), bytes.len())
                };
                let mut out = Vec::new();
                out.try_reserve_exact(len)
                    .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
                out.copy_from_slice(values);
                return Ok(unsafe { core::mem::transmute::<Vec<i8>, Vec<T>>(out) });
            }
            if __type_equal::<T, f64>() {
                let values = read_f64_vec(cursor, len)?;
                return Ok(unsafe { core::mem::transmute::<Vec<f64>, Vec<T>>(values) });
            }
            if __type_equal::<T, f32>() {
                let values = read_f32_vec(cursor, len)?;
                return Ok(unsafe { core::mem::transmute::<Vec<f32>, Vec<T>>(values) });
            }
            if __type_equal::<T, u64>() {
                let values = cursor.read_varints_bulk(len)?;
                return Ok(unsafe { core::mem::transmute::<Vec<u64>, Vec<T>>(values) });
            }
            // Signed integers stay on the single-pass generic loop: ZigZag
            // reconstruction must happen inline, so a bulk pass followed by a
            // conversion pass would only add overhead.
            let mut out = Vec::new();
            out.try_reserve_exact(len)
                .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
            for _ in 0..len {
                out.push(T::decode_compact(cursor)?);
            }
            Ok(out)
        })();
        cursor.exit_container();
        outcome
    }
}

impl<T: CompactEncode, const N: usize> CompactEncode for [T; N] {
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        // No length prefix (the width is part of the type); the bulk element
        // encoder gives byte/float/numeric arrays the same fast paths as
        // `Vec<T>`.
        encode_elements(writer, self)
    }
}

impl<'de, T: CompactDecode<'de>, const N: usize> CompactDecode<'de> for [T; N] {
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<[T; N]> {
        // Avoid a heap allocation for fixed-size arrays: fill a MaybeUninit
        // array and move it out once every slot is initialized.
        let mut slots: [core::mem::MaybeUninit<T>; N] =
            core::array::from_fn(|_| core::mem::MaybeUninit::uninit());
        for slot in &mut slots {
            slot.write(T::decode_compact(cursor)?);
        }
        // SAFETY: every slot was written by the loop above, which either
        // completed (all initialized) or returned early (cursor dropped, the
        // partially initialized slots are dropped with the array).
        Ok(unsafe { core::mem::transmute_copy(&slots) })
    }
}

impl<T: CompactEncode> CompactEncode for Option<T> {
    #[inline]
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        match self {
            None => encode_bool(writer, false),
            Some(value) => {
                encode_bool(writer, true)?;
                value.encode_compact(writer)
            }
        }
    }
}

impl<'de, T: CompactDecode<'de>> CompactDecode<'de> for Option<T> {
    #[inline]
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Option<T>> {
        if cursor.read_bool()? {
            Ok(Some(T::decode_compact(cursor)?))
        } else {
            Ok(None)
        }
    }
}

impl<T: CompactEncode> CompactEncode for VecDeque<T> {
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_length(writer, self.len())?;
        writer.enter_container()?;
        let outcome = (|| {
            // `VecDeque` stores its elements in up to two contiguous slices;
            // route both through the bulk element encoder for the byte,
            // float, and numeric fast paths.
            let (head, tail) = self.as_slices();
            encode_elements(writer, head)?;
            encode_elements(writer, tail)
        })();
        writer.exit_container();
        outcome
    }
}

impl<'de, T: CompactDecode<'de>> CompactDecode<'de> for VecDeque<T> {
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<VecDeque<T>> {
        let len = cursor.read_length()?;
        cursor.enter_container(len)?;
        let outcome = (|| {
            let mut out = VecDeque::new();
            out.try_reserve(len)
                .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
            for _ in 0..len {
                out.push_back(T::decode_compact(cursor)?);
            }
            Ok(out)
        })();
        cursor.exit_container();
        outcome
    }
}

impl<K: CompactEncode, V: CompactEncode> CompactEncode for BTreeMap<K, V> {
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_length(writer, self.len())?;
        writer.enter_container()?;
        let outcome = (|| {
            for (key, value) in self {
                key.encode_compact(writer)?;
                value.encode_compact(writer)?;
            }
            Ok(())
        })();
        writer.exit_container();
        outcome
    }
}

impl<'de, K: CompactDecode<'de> + Ord, V: CompactDecode<'de>> CompactDecode<'de>
    for BTreeMap<K, V>
{
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<BTreeMap<K, V>> {
        let len = cursor.read_length()?;
        cursor.enter_container(len)?;
        let outcome = (|| {
            let mut out = BTreeMap::new();
            for _ in 0..len {
                let key = K::decode_compact(cursor)?;
                let value = V::decode_compact(cursor)?;
                // Duplicate keys would make the frame ambiguous; reject them.
                if out.insert(key, value).is_some() {
                    return Err(Error::Custom("duplicate map key".into()));
                }
            }
            Ok(out)
        })();
        cursor.exit_container();
        outcome
    }
}

#[cfg(feature = "std")]
impl<K: CompactEncode, V: CompactEncode> CompactEncode for HashMap<K, V> {
    fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
        encode_length(writer, self.len())?;
        writer.enter_container()?;
        let outcome = (|| {
            for (key, value) in self {
                key.encode_compact(writer)?;
                value.encode_compact(writer)?;
            }
            Ok(())
        })();
        writer.exit_container();
        outcome
    }
}

#[cfg(feature = "std")]
impl<'de, K: CompactDecode<'de> + Eq + core::hash::Hash, V: CompactDecode<'de>> CompactDecode<'de>
    for HashMap<K, V>
{
    fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<HashMap<K, V>> {
        let len = cursor.read_length()?;
        cursor.enter_container(len)?;
        let outcome = (|| {
            let mut out = HashMap::new();
            out.try_reserve(len)
                .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
            for _ in 0..len {
                let key = K::decode_compact(cursor)?;
                let value = V::decode_compact(cursor)?;
                if out.insert(key, value).is_some() {
                    return Err(Error::Custom("duplicate map key".into()));
                }
            }
            Ok(out)
        })();
        cursor.exit_container();
        outcome
    }
}

macro_rules! impl_tuple {
    ($($name:ident),+ $(,)?) => {
        impl<$($name: CompactEncode),+> CompactEncode for ($($name,)+) {
            #[allow(non_snake_case)]
            #[inline]
            fn encode_compact<W: EncodeWriter + ?Sized>(&self, writer: &mut W) -> Result<()> {
                let ($($name,)+) = self;
                $( $name.encode_compact(writer)?; )+
                Ok(())
            }
        }
        impl<'de, $($name: CompactDecode<'de>),+> CompactDecode<'de> for ($($name,)+) {
            #[allow(non_snake_case)]
            #[inline]
            fn decode_compact(cursor: &mut CompactCursor<'de>) -> Result<Self> {
                Ok(($( $name::decode_compact(cursor)?, )+))
            }
        }
    };
}

impl_tuple!(A);
impl_tuple!(A, B);
impl_tuple!(A, B, C);
impl_tuple!(A, B, C, D);
impl_tuple!(A, B, C, D, E);
impl_tuple!(A, B, C, D, E, F);
impl_tuple!(A, B, C, D, E, F, G);
impl_tuple!(A, B, C, D, E, F, G, H);

#[cfg(test)]
mod tests {
    use super::*;
    // The `vec!` macro is not in the prelude under `no_std`; the module's own
    // `use alloc::vec::Vec` only imports the type.
    use alloc::string::ToString;
    use alloc::vec;

    fn roundtrip<T>(value: &T) -> Vec<u8>
    where
        T: CompactEncode + for<'de> CompactDecode<'de> + PartialEq + core::fmt::Debug,
    {
        let config = Config::standard();
        let compact = CompactConfig::new(config);
        let bytes = compact.serialize(value).unwrap();
        let decoded: T = compact.deserialize(&bytes).unwrap();
        assert_eq!(decoded, *value);
        bytes
    }

    // The hand-inlined hot-path encode must never drift from the canonical
    // `encode_varint_le` that the single-value writer shares.
    #[test]
    fn inline_varint_write_matches_canonical() {
        let cases = [
            0u64,
            1,
            250,
            251,
            0xffff,
            0x1_0000,
            0xffff_ffff,
            0x1_0000_0000,
            u64::MAX,
        ];
        for value in cases {
            let mut buffer = [0u8; 32];
            let len = write_varint_into(&mut buffer, value);
            let (canonical, canonical_len) = crate::canonical::encode_varint_le(value as u128);
            assert_eq!(&buffer[..len], &canonical[..canonical_len], "value {value}");
            assert_eq!(len, canonical_len);
        }
    }

    // The batched writer and reader must agree with the single-value paths on
    // a dense value sweep (covers every varint width and the flush boundaries).
    #[test]
    fn bulk_paths_agree_with_single_value_paths() {
        let mut values = Vec::new();
        values.extend(0..300); // plain run
        values.push(251);
        values.push(0xffff);
        values.push(0x1_0000);
        values.push(0xffff_ffff);
        values.push(0x1_0000_0000);
        values.push(u64::MAX);
        // A sweep that forces many flush boundaries (5-byte values).
        values.extend((0..300).map(|i| 0x1_0000 + i));
        let config = Config::standard();
        let compact = CompactConfig::new(config);
        let bytes = compact.serialize(&values).unwrap();
        assert_eq!(compact.deserialize::<Vec<u64>>(&bytes).unwrap(), values);
    }

    #[test]
    fn primitives_roundtrip() {
        roundtrip(&true);
        roundtrip(&false);
        roundtrip(&0u8);
        roundtrip(&250u8);
        roundtrip(&251u8);
        roundtrip(&255u8);
        roundtrip(&u16::MAX);
        roundtrip(&u32::MAX);
        roundtrip(&u64::MAX);
        roundtrip(&u128::MAX);
        roundtrip(&i8::MIN);
        roundtrip(&i16::MIN);
        roundtrip(&i32::MIN);
        roundtrip(&i64::MIN);
        roundtrip(&i128::MIN);
        roundtrip(&-1i64);
        roundtrip(&0i64);
        roundtrip(&f32::MIN);
        roundtrip(&f32::MAX);
        roundtrip(&f64::MIN);
        roundtrip(&f64::MAX);
        roundtrip(&-0.0f64);
        roundtrip(&'a');
        roundtrip(&'中');
        roundtrip(&());
    }

    #[test]
    fn u8_is_single_raw_byte() {
        // A `u8` above 250 must still encode as exactly one byte (fixed
        // 8-bit), never a 3-byte varint.
        let bytes = CompactConfig::new(Config::standard())
            .serialize(&255u8)
            .unwrap();
        assert_eq!(bytes, &[255]);
        let bytes = CompactConfig::new(Config::standard())
            .serialize(&0u8)
            .unwrap();
        assert_eq!(bytes, &[0]);
    }

    #[test]
    fn string_and_bytes_roundtrip() {
        let bytes = roundtrip(&"hello".to_string());
        assert_eq!(bytes, &[5, b'h', b'e', b'l', b'l', b'o']);
        // Borrowed decode points into the input.
        let config = CompactConfig::new(Config::standard());
        let encoded = config.serialize(&b"raw bytes".as_slice()).unwrap();
        let decoded: &[u8] = config.deserialize(&encoded).unwrap();
        assert_eq!(decoded, b"raw bytes");
        let encoded = config.serialize(&"borrowed").unwrap();
        let decoded: &str = config.deserialize(&encoded).unwrap();
        assert_eq!(decoded, "borrowed");
        roundtrip(&Vec::from(b"raw bytes".as_slice()));
    }

    #[test]
    fn byte_vec_is_length_plus_memcpy() {
        let config = CompactConfig::new(Config::standard());
        let value = vec![0u8, 251, 252, 255, 7, 0, 128];
        let bytes = config.serialize(&value).unwrap();
        // varint len (7) followed by the raw bytes — no per-element tags.
        assert_eq!(bytes, &[7, 0, 251, 252, 255, 7, 0, 128]);
        let decoded: Vec<u8> = config.deserialize(&bytes).unwrap();
        assert_eq!(decoded, value);
    }

    #[test]
    fn option_roundtrip() {
        let config = CompactConfig::new(Config::standard());
        let none: Option<u64> = None;
        let none_bytes = config.serialize(&none).unwrap();
        assert_eq!(none_bytes, &[0]);
        assert_eq!(
            config.deserialize::<Option<u64>>(&none_bytes).unwrap(),
            None
        );
        let some_bytes = config.serialize(&Some(7u64)).unwrap();
        assert_eq!(some_bytes, &[1, 7]);
        assert_eq!(
            config.deserialize::<Option<u64>>(&some_bytes).unwrap(),
            Some(7)
        );
    }

    #[test]
    fn numeric_vecs_roundtrip() {
        roundtrip(&(0..300u16).collect::<Vec<_>>());
        roundtrip(&(0..300u32).collect::<Vec<_>>());
        roundtrip(&(0..300u64).collect::<Vec<_>>());
        roundtrip(&(-150..150i16).collect::<Vec<_>>());
        roundtrip(&(-150..150i32).collect::<Vec<_>>());
        roundtrip(&(-150..150i64).collect::<Vec<_>>());
        roundtrip(&(0..100).map(|i| i as f32 * 0.5).collect::<Vec<_>>());
        roundtrip(&(0..100).map(|i| i as f64 * 0.25).collect::<Vec<_>>());
    }

    #[test]
    fn vec_encodes_with_single_length_prefix() {
        let config = CompactConfig::new(Config::standard());
        let values = vec![1u64, 2, 3, 4];
        let bytes = config.serialize(&values).unwrap();
        // [len=4, 1, 2, 3, 4] — one length prefix, no tags.
        assert_eq!(bytes, &[4, 1, 2, 3, 4]);
    }

    #[test]
    fn float_vec_is_compact_payload() {
        let config = CompactConfig::new(Config::standard());
        let values = vec![1.0f64, -2.0, 3.5];
        let bytes = config.serialize(&values).unwrap();
        assert_eq!(bytes.len(), 1 + 3 * 8);
        let decoded: Vec<f64> = config.deserialize(&bytes).unwrap();
        assert_eq!(decoded, values);
    }

    #[test]
    fn arrays_and_tuples_roundtrip() {
        roundtrip(&[1u64, 2, 3, 4]);
        roundtrip(&[0u8, 255, 1, 2]);
        roundtrip(&(true, 1i16, 2u64, 3.0f64, 'x', ()));
        // Tuples containing borrowed strings decode in place.
        let config = CompactConfig::new(Config::standard());
        let value = (7u32, "seven", 1.5f32);
        let bytes = config.serialize(&value).unwrap();
        let decoded: (u32, &str, f32) = config.deserialize(&bytes).unwrap();
        assert_eq!(decoded, value);
    }

    #[test]
    fn maps_roundtrip() {
        let config = CompactConfig::new(Config::standard());
        let mut map = BTreeMap::new();
        map.insert(3u32, "three");
        map.insert(1u32, "one");
        let bytes = config.serialize(&map).unwrap();
        let decoded: BTreeMap<u32, &str> = config.deserialize(&bytes).unwrap();
        assert_eq!(decoded, map);
        // Sorted keys: [len=2, 1, "one", 3, "three"].
        assert_eq!(
            bytes,
            &[2, 1, 3, b'o', b'n', b'e', 3, 5, b't', b'h', b'r', b'e', b'e']
        );
    }

    #[test]
    fn nested_containers_roundtrip() {
        roundtrip(&vec![vec![1u8, 2], vec![3, 4, 5]]);
        roundtrip(&vec![Some(1u64), None, Some(3)]);
        roundtrip(&vec!["a".to_string(), "bb".to_string(), "ccc".to_string()]);
    }

    #[test]
    fn collections_are_bounded_by_limits() {
        let config = CompactConfig::new(Config::standard().with_collection_limit(2));
        let encoded = config.serialize(&vec![1u64, 2, 3]).unwrap();
        let error = config.deserialize::<Vec<u64>>(&encoded).unwrap_err();
        assert!(matches!(error, Error::CollectionLimit { limit: 2 }));

        // vec![1u64, 2] is 3 bytes ([2, 1, 2]); a 2-byte cap rejects the decode.
        let encoded = CompactConfig::new(Config::standard())
            .serialize(&vec![1u64, 2])
            .unwrap();
        let config = CompactConfig::new(Config::standard().with_limit(2));
        let error = config.deserialize::<Vec<u64>>(&encoded).unwrap_err();
        assert!(matches!(error, Error::SizeLimit { limit: 2 }));
    }

    #[test]
    fn depth_limit_rejects_deep_nesting() {
        // Statically typed frames cannot nest beyond their type; the guard is
        // exercised directly at the cursor level (recursive enum types are
        // covered by the integration tests).
        let mut cursor = CompactCursor::new(&[0u8; 1], Config::standard().with_depth_limit(4));
        for _ in 0..4 {
            cursor.enter_container(0).unwrap();
        }
        let error = cursor.enter_container(0).unwrap_err();
        assert!(matches!(error, Error::Custom(_)));
    }

    #[test]
    fn trailing_bytes_are_rejected() {
        let config = CompactConfig::new(Config::standard());
        let mut encoded = config.serialize(&1u64).unwrap();
        encoded.push(0xff);
        let error = config.deserialize::<u64>(&encoded).unwrap_err();
        assert!(matches!(error, Error::TrailingBytes { remaining: 1 }));
    }

    #[test]
    fn truncated_input_fails_cleanly() {
        let config = CompactConfig::new(Config::standard());
        let encoded = config.serialize(&"hello").unwrap();
        for cut in 0..encoded.len() {
            let error = config.deserialize::<String>(&encoded[..cut]).unwrap_err();
            assert!(matches!(
                error,
                Error::UnexpectedEnd | Error::InvalidUtf8(_)
            ));
        }
    }

    #[test]
    fn non_canonical_varints_are_rejected() {
        // 0xfb (251) then a 16-bit payload of 5 — non-canonical (5 < 251).
        let config = CompactConfig::new(Config::standard());
        let error = config.deserialize::<u64>(&[MARKER_U16, 5, 0]).unwrap_err();
        assert!(matches!(error, Error::NonCanonicalVarint));
    }

    #[test]
    fn invalid_bool_and_option_tags_are_rejected() {
        let config = CompactConfig::new(Config::standard());
        assert!(matches!(
            config.deserialize::<bool>(&[2]).unwrap_err(),
            Error::InvalidBool(2)
        ));
        // `Option` uses the same one-byte presence tag as `bool`.
        assert!(matches!(
            config.deserialize::<Option<u64>>(&[2]).unwrap_err(),
            Error::InvalidBool(2)
        ));
    }

    #[test]
    fn serialized_size_matches_output() {
        let config = CompactConfig::new(Config::standard());
        let value = vec!["alpha".to_string(), "beta".to_string()];
        let bytes = config.serialize(&value).unwrap();
        assert_eq!(
            config.serialized_size(&value).unwrap() as usize,
            bytes.len()
        );
    }

    #[test]
    fn slice_serialize_into_slice() {
        let config = CompactConfig::new(Config::standard());
        let value = vec![1u64, 2, 3];
        let bytes = config.serialize(&value).unwrap();
        let mut output = [0u8; 16];
        let written = config.serialize_into_slice(&mut output, &value).unwrap();
        assert_eq!(&output[..written], &bytes[..]);
        let mut tiny = [0u8; 2];
        let error = config.serialize_into_slice(&mut tiny, &value).unwrap_err();
        assert!(matches!(error, Error::BufferTooSmall { .. }));
    }

    #[test]
    fn encode_depth_is_bounded() {
        // Three nested containers through a bounded writer with a shallow cap.
        let value = vec![vec![vec![1u64]]];
        let error = CompactConfig::new(Config::standard().with_depth_limit(1))
            .serialize(&value)
            .unwrap_err();
        assert!(matches!(error, Error::Custom(_)));
    }

    #[test]
    fn tuple_members_follow_declaration_order() {
        let config = CompactConfig::new(Config::standard());
        let bytes = config.serialize(&(1u8, 2u16, 3u32)).unwrap();
        assert_eq!(bytes, &[1, 2, 3]);
    }

    #[test]
    fn empty_values_encode_minimally() {
        let config = CompactConfig::new(Config::standard());
        assert_eq!(config.serialize(&()).unwrap(), &[]);
        assert_eq!(config.serialize(&Vec::<u64>::new()).unwrap(), &[0]);
        assert_eq!(config.serialize(&String::new()).unwrap(), &[0]);
        assert_eq!(config.serialize(&[0u64; 0]).unwrap(), &[]);
    }
}