serde_describe 0.2.5

use std::fmt::Debug;

use crate::{
    indices::{
        FieldNameIndex, FieldNameListIndex, MemberIndex, MemberListIndex, SchemaNodeIndex,
        SchemaNodeListIndex, TraceIndex, TypeName, TypeNameIndex, VariantNameIndex,
    },
    pool::{NonEmptyPool, Pool},
    schema::{Schema, SchemaNode},
    trace::{Trace, TraceNodeKind},
};
use serde::{
    Deserialize, Serialize,
    ser::{
        SerializeMap, SerializeSeq, SerializeStruct, SerializeStructVariant, SerializeTuple,
        SerializeTupleStruct, SerializeTupleVariant, Serializer,
    },
};

/// An in-progress schema built by successive calls to [`SchemaBuilder::trace`].
///
/// For simple use-cases, where the schema gets serialized together with data, you can use
/// [`SelfDescribed`][`crate::SelfDescribed`]. If instead, you're serializing many values with
/// similar schemas, you can use a [`SchemaBuilder`].
///
/// Example
/// -------
/// ```rust
/// use serde::{Serialize, Deserialize, de::DeserializeSeed};
/// use serde_describe::{SchemaBuilder, Schema, Trace, DescribedBy};
///
/// #[derive(Debug, PartialEq, Serialize, Deserialize)]
/// struct Type1 {
///     a: u32,
///     b: Type3,
/// }
///
/// #[derive(Debug, PartialEq, Serialize, Deserialize)]
/// struct Type2 {
///     x: Vec<f32>,
///     y: Type3,
/// }
///
/// #[derive(Debug, PartialEq, Serialize, Deserialize)]
/// struct Type3 {
///     m: u32,
///     n: Option<u32>,
/// }
///
/// // Create some sample data to serialize
/// let original1 = Type1 { a: 10, b: Type3 { m: 100, n: Some(200) }};
/// let original2 = Type1 { a: 20, b: Type3 { m: 500, n: None }};
/// let original3 = Type2 { x: vec![1.0, 2.0], y: Type3 { m: 1, n: Some(2) } };
///
/// // Serialize the three values, then build the schema.
/// let mut builder = SchemaBuilder::new();
/// let trace1: Trace = builder.trace(&original1)?;
/// let trace2 = builder.trace(&original2)?;
/// let trace3 = builder.trace(&original3)?;
/// let schema = builder.build()?;
///
/// // Write different files using the same builder, then serialize the schema to its own file.
/// std::fs::write("file1.type1", &postcard::to_stdvec(&schema.describe_trace(trace1))?)?;
/// std::fs::write("file2.type1", &postcard::to_stdvec(&schema.describe_trace(trace2))?)?;
/// std::fs::write("file3.type2", &postcard::to_stdvec(&schema.describe_trace(trace3))?)?;
/// std::fs::write("schema", &postcard::to_stdvec(&schema)?)?;
///
/// // Load the schema, then read the values back.
/// let schema: Schema = postcard::from_bytes(&std::fs::read("schema")?)?;
/// let DescribedBy(roundtripped_value1, _) = schema.describe_type::<Type1>()
///     .deserialize(&mut postcard::Deserializer::from_bytes(&std::fs::read("file1.type1")?))?;
/// let DescribedBy(roundtripped_value2,_) = schema.describe_type::<Type1>()
///     .deserialize(&mut postcard::Deserializer::from_bytes(&std::fs::read("file2.type1")?))?;
/// let DescribedBy(roundtripped_value3,_) = schema.describe_type::<Type2>()
///     .deserialize(&mut postcard::Deserializer::from_bytes(&std::fs::read("file3.type2")?))?;
///
/// assert_eq!(roundtripped_value1, original1);
/// assert_eq!(roundtripped_value2, original2);
/// assert_eq!(roundtripped_value3, original3);
///
/// # std::fs::remove_file("file1.type1")?;
/// # std::fs::remove_file("file2.type1")?;
/// # std::fs::remove_file("file3.type2")?;
/// # std::fs::remove_file("schema")?;
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Default, Clone)]
pub struct SchemaBuilder {
    root: SchemaBuilderNode,
    nodes: Pool<SchemaNode, SchemaNodeIndex>,
    node_lists: Pool<Box<[SchemaNodeIndex]>, SchemaNodeListIndex>,
    member_lists: Pool<Box<[MemberIndex]>, MemberListIndex>,
    field_name_lists: NonEmptyPool<Box<[FieldNameIndex]>, FieldNameListIndex>,
    field_names: NonEmptyPool<&'static str, FieldNameIndex>,
    variant_names: NonEmptyPool<&'static str, VariantNameIndex>,
    type_names: NonEmptyPool<&'static str, TypeNameIndex>,
}

impl SchemaBuilder {
    /// Creates a new, empty [`SchemaBuilder`].
    pub fn new() -> Self {
        Self::default()
    }

    /// Converts a type that supports [`serde::Serialize`] into a [`Trace`] and records its type
    /// into the schema.
    ///
    /// See the top-level [`SchemaBuilder`] documentation for an example.
    pub fn trace<ValueT>(&mut self, value: &ValueT) -> Result<Trace, TraceError>
    where
        ValueT: Serialize,
    {
        let mut data = Vec::new();
        let new_root = value.serialize(RootSerializer {
            data: &mut data,
            nodes: &mut self.nodes,
            node_lists: &mut self.node_lists,
            member_lists: &mut self.member_lists,
            field_name_lists: &mut self.field_name_lists,
            field_names: &mut self.field_names,
            variant_names: &mut self.variant_names,
            type_names: &mut self.type_names,
        })?;
        self.root.union(new_root);
        Ok(Trace(data))
    }

    /// Converts all the recorded value types into a schema that can be used to serialize the
    /// [`Trace`]-s returned by [`trace`][`Self::trace`].
    ///
    /// See the top-level [`SchemaBuilder`] documentation for an example.
    pub fn build(mut self) -> Result<Schema, TraceError> {
        let schema = Schema {
            root_index: std::mem::take(&mut self.root).build(&mut self)?,
            nodes: self.nodes.into(),
            node_lists: self.node_lists.into(),
            member_lists: self.member_lists.into(),
            field_name_lists: self.field_name_lists.into(),
            field_names: self.field_names.into(),
            variant_names: self.variant_names.into(),
            type_names: self.type_names.into(),
        };
        Ok(schema)
    }
}

/// Errors returned by tracing values.
#[derive(Debug)]
#[non_exhaustive]
pub enum TraceError {
    /// The value is in some way too large, and built-in limits were exceeded.
    Limit(TraceLimitError),

    /// A `Serialize` implementation serialized a different number of struct fields or tuple
    /// elements than the length it declared.
    LengthMismatch,

    /// Custom serde serialization error.
    Custom(Box<str>),
}

impl std::fmt::Display for TraceError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "tracing error: ")?;
        match self {
            Self::Limit(limit) => write!(f, "{limit}"),
            Self::LengthMismatch => {
                write!(f, "serialized a different number of elements than declared")
            }
            Self::Custom(custom) => write!(f, "custom serialization error: {custom}"),
        }
    }
}

impl From<TraceLimitErrorKind> for TraceError {
    #[inline]
    fn from(kind: TraceLimitErrorKind) -> Self {
        Self::Limit(kind.into())
    }
}

impl std::error::Error for TraceError {
    #[inline]
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            Self::Limit(limit) => Some(limit),
            Self::LengthMismatch | Self::Custom(_) => None,
        }
    }
}

/// Errors caused by tracing a value that is in some way too large.
#[derive(Debug)]
pub struct TraceLimitError(TraceLimitErrorKind);

impl From<TraceLimitErrorKind> for TraceLimitError {
    #[inline]
    fn from(value: TraceLimitErrorKind) -> Self {
        Self(value)
    }
}

impl std::fmt::Display for TraceLimitError {
    #[inline]
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        std::fmt::Display::fmt(&self.0, f)
    }
}

impl std::error::Error for TraceLimitError {
    #[inline]
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        Some(&self.0)
    }
}

impl serde::ser::Error for TraceError {
    #[inline]
    fn custom<T>(msg: T) -> Self
    where
        T: std::fmt::Display,
    {
        TraceError::Custom(msg.to_string().into())
    }
}

pub(crate) const MAX_SKIPPABLE_FIELDS: usize = 64;

#[derive(Debug)]
pub(crate) enum TraceLimitErrorKind {
    SchemaNodes,
    SchemaNodeLists,
    Members,
    MemberLists,
    Names,
    FieldNameLists,
    Values,
    UnionVariants,
    SkippableFields,
}

impl std::fmt::Display for TraceLimitErrorKind {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let message = match self {
            Self::SchemaNodes => "too many schema nodes for u32",
            Self::SchemaNodeLists => "too many schema node lists for u32",
            Self::Members => "too many struct members for u32",
            Self::MemberLists => "too many struct member lists for u32",
            Self::Names => "too many struct/variant/field names for u32",
            Self::FieldNameLists => "too many field lists for u32",
            Self::Values => "too many values for u32",
            Self::UnionVariants => "too many variants",
            Self::SkippableFields => "too many skippable fields",
        };
        f.write_str(message)
    }
}

impl std::error::Error for TraceLimitErrorKind {}

pub(crate) struct RootSerializer<'a> {
    data: &'a mut Vec<u8>,
    nodes: &'a mut Pool<SchemaNode, SchemaNodeIndex>,
    node_lists: &'a mut Pool<Box<[SchemaNodeIndex]>, SchemaNodeListIndex>,
    member_lists: &'a mut Pool<Box<[MemberIndex]>, MemberListIndex>,
    field_name_lists: &'a mut NonEmptyPool<Box<[FieldNameIndex]>, FieldNameListIndex>,
    field_names: &'a mut NonEmptyPool<&'static str, FieldNameIndex>,
    variant_names: &'a mut NonEmptyPool<&'static str, VariantNameIndex>,
    type_names: &'a mut NonEmptyPool<&'static str, TypeNameIndex>,
}

impl RootSerializer<'_> {
    #[inline]
    fn reborrow<'b>(&'b mut self) -> RootSerializer<'b> {
        RootSerializer {
            data: self.data,
            nodes: self.nodes,
            field_name_lists: self.field_name_lists,
            node_lists: self.node_lists,
            member_lists: self.member_lists,
            field_names: self.field_names,
            variant_names: self.variant_names,
            type_names: self.type_names,
        }
    }

    #[inline]
    fn push_struct_name(&mut self, name: &'static str) -> Result<TypeName, TraceLimitErrorKind> {
        let name = self.type_names.intern(name)?;
        self.push_u32(name.into());
        Ok(TypeName(name, None))
    }

    #[inline]
    fn push_variant_name(
        &mut self,
        name: &'static str,
        variant: &'static str,
    ) -> Result<TypeName, TraceLimitErrorKind> {
        let name = self.type_names.intern(name)?;
        let variant = self.variant_names.intern(variant)?;
        self.push_u32(name.into());
        self.push_u32(variant.into());
        Ok(TypeName(name, Some(variant)))
    }

    #[inline]
    fn intern_field_name(
        &mut self,
        name: &'static str,
    ) -> Result<FieldNameIndex, TraceLimitErrorKind> {
        self.field_names.intern(name)
    }

    #[inline]
    fn fill_reserved_field_name_list(
        &mut self,
        index: TraceIndex,
        names: Vec<FieldNameIndex>,
    ) -> Result<FieldNameListIndex, TraceLimitErrorKind> {
        let names = self.field_name_lists.intern_from(names)?;
        self.fill_reserved_bytes(index, &u32::from(names).to_le_bytes());
        Ok(names)
    }

    #[inline]
    fn push_u32(&mut self, integer: u32) {
        self.data.extend(integer.to_le_bytes());
    }

    #[inline]
    fn push_u32_length(&mut self, length: usize) -> Result<(), TraceLimitErrorKind> {
        self.data.extend(
            u32::try_from(length)
                .map_err(|_| TraceLimitErrorKind::Values)?
                .to_le_bytes(),
        );
        Ok(())
    }

    #[inline]
    fn push_trace(&mut self, trace: TraceNodeKind) {
        self.data.push(trace.into());
    }

    #[inline]
    fn reserve_u32(&mut self) -> Result<TraceIndex, TraceLimitErrorKind> {
        self.reserve_bytes(std::mem::size_of::<u32>())
    }

    #[inline]
    fn reserve_field_presence(&mut self, length: usize) -> Result<TraceIndex, TraceLimitErrorKind> {
        self.reserve_bytes(std::mem::size_of::<u32>() * length)
    }

    #[inline]
    fn reserve_bytes(&mut self, size: usize) -> Result<TraceIndex, TraceLimitErrorKind> {
        let index = TraceIndex::try_from(self.data.len())?;
        self.data.extend(std::iter::repeat_n(!0, size));
        Ok(index)
    }

    #[inline]
    fn push_length_bytes(&mut self, bytes: &[u8]) -> Result<(), TraceLimitErrorKind> {
        self.push_u32_length(bytes.len())?;
        self.data.extend(bytes);
        Ok(())
    }

    #[inline]
    fn fill_reserved_bytes(&mut self, index: TraceIndex, data: &[u8]) {
        self.data[index.into()..][..data.len()].copy_from_slice(data);
    }

    #[inline]
    fn write_field_presence(
        &mut self,
        index: TraceIndex,
        field: MemberIndex,
    ) -> Result<TraceIndex, TraceLimitErrorKind> {
        self.fill_reserved_bytes(index, &u32::from(field).to_le_bytes());
        TraceIndex::try_from(usize::from(index) + std::mem::size_of::<u32>())
    }
}

#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
pub(crate) enum SchemaBuilderNode {
    Bool,

    I8,
    I16,
    I32,
    I64,
    I128,

    U8,
    U16,
    U32,
    U64,
    U128,

    F32,
    F64,
    Char,

    String,
    Bytes,

    OptionNone,
    OptionSome(Box<SchemaBuilderNode>),

    Unit(Option<TypeName>),
    Newtype(TypeName, Box<SchemaBuilderNode>),

    Map(Box<SchemaBuilderNode>, Box<SchemaBuilderNode>),
    Sequence(Box<SchemaBuilderNode>),

    Union(Vec<SchemaBuilderNode>),

    /// Tuple, tuple struct, tuple variant, struct or struct variant.
    Record {
        name: Option<TypeName>,
        field_names: Option<FieldNameListIndex>,
        field_types: Vec<SchemaBuilderNode>,
        skippable: Vec<MemberIndex>,
    },
}

impl SchemaBuilderNode {
    fn unify(&mut self, other: Self) -> Result<(), Self> {
        match (&mut *self, other) {
            (SchemaBuilderNode::Union(lefts), right) => {
                if lefts.is_empty() {
                    *self = right;
                } else {
                    right.add_to_nonempty_union(lefts);
                }
                Ok(())
            }
            (left, mut right @ SchemaBuilderNode::Union(_)) => {
                std::mem::swap(left, &mut right);
                left.unify(right)
            }
            (
                SchemaBuilderNode::Newtype(left_name, left_inner),
                SchemaBuilderNode::Newtype(right_name, right_inner),
            ) => {
                if *left_name == right_name {
                    left_inner.union(*right_inner);
                    Ok(())
                } else {
                    Err(SchemaBuilderNode::Newtype(right_name, right_inner))
                }
            }
            (SchemaBuilderNode::OptionSome(left), SchemaBuilderNode::OptionSome(right)) => {
                left.union(*right);
                Ok(())
            }
            (
                SchemaBuilderNode::Record {
                    name: left_name,
                    field_names: left_field_names,
                    field_types: left_field_types,
                    skippable: left_skippable,
                },
                SchemaBuilderNode::Record {
                    name: right_name,
                    field_names: right_field_names,
                    field_types: right_field_types,
                    skippable: right_skippable,
                },
            ) => {
                if (*left_name, *left_field_names, left_field_types.len())
                    == (right_name, right_field_names, right_field_types.len())
                {
                    left_field_types
                        .iter_mut()
                        .zip(right_field_types)
                        .for_each(|(left, right)| left.union(right));
                    left_skippable.extend(right_skippable);
                    left_skippable.sort_unstable();
                    left_skippable.dedup();
                    Ok(())
                } else {
                    Err(SchemaBuilderNode::Record {
                        name: right_name,
                        field_names: right_field_names,
                        field_types: right_field_types,
                        skippable: right_skippable,
                    })
                }
            }
            (
                SchemaBuilderNode::Map(left_keys, left_values),
                SchemaBuilderNode::Map(right_keys, right_values),
            ) => {
                left_keys.union(*right_keys);
                left_values.union(*right_values);
                Ok(())
            }
            (SchemaBuilderNode::Sequence(left), SchemaBuilderNode::Sequence(right)) => {
                left.union(*right);
                Ok(())
            }
            (left, right) => {
                if *left == right {
                    Ok(())
                } else {
                    Err(right)
                }
            }
        }
    }

    #[inline]
    fn union(&mut self, other: Self) {
        if let Err(other) = self.unify(other) {
            let left = std::mem::take(self);
            match self {
                SchemaBuilderNode::Union(schemas) => *schemas = vec![left, other],
                _ => unreachable!(),
            }
        }
    }

    fn add_to_nonempty_union(self, lefts: &mut Vec<SchemaBuilderNode>) {
        assert!(!lefts.is_empty());
        match self {
            SchemaBuilderNode::Union(rights) => {
                rights
                    .into_iter()
                    .for_each(|right| right.add_to_nonempty_union(lefts));
            }
            right => {
                let right = lefts
                    .iter_mut()
                    .try_fold(right, |right, left| match left.unify(right) {
                        Ok(()) => Err(()),
                        Err(recovered) => Ok(recovered),
                    })
                    .ok();
                lefts.extend(right);
            }
        }
    }
}

impl Default for SchemaBuilderNode {
    #[inline]
    fn default() -> Self {
        Self::Union(Vec::new())
    }
}

impl SchemaBuilderNode {
    fn build(self, builder: &mut SchemaBuilder) -> Result<SchemaNodeIndex, TraceError> {
        let built = match self {
            SchemaBuilderNode::Bool => SchemaNode::Bool,
            SchemaBuilderNode::I8 => SchemaNode::I8,
            SchemaBuilderNode::I16 => SchemaNode::I16,
            SchemaBuilderNode::I32 => SchemaNode::I32,
            SchemaBuilderNode::I64 => SchemaNode::I64,
            SchemaBuilderNode::I128 => SchemaNode::I128,

            SchemaBuilderNode::U8 => SchemaNode::U8,
            SchemaBuilderNode::U16 => SchemaNode::U16,
            SchemaBuilderNode::U32 => SchemaNode::U32,
            SchemaBuilderNode::U64 => SchemaNode::U64,
            SchemaBuilderNode::U128 => SchemaNode::U128,

            SchemaBuilderNode::F32 => SchemaNode::F32,
            SchemaBuilderNode::F64 => SchemaNode::F64,
            SchemaBuilderNode::Char => SchemaNode::Char,

            SchemaBuilderNode::String => SchemaNode::String,
            SchemaBuilderNode::Bytes => SchemaNode::Bytes,

            SchemaBuilderNode::OptionNone => SchemaNode::OptionNone,
            SchemaBuilderNode::OptionSome(inner) => {
                let inner = inner.build(builder)?;
                SchemaNode::OptionSome(inner)
            }
            SchemaBuilderNode::Unit(None) => SchemaNode::Unit,
            SchemaBuilderNode::Unit(Some(TypeName(name, None))) => SchemaNode::UnitStruct(name),
            SchemaBuilderNode::Unit(Some(TypeName(name, Some(variant)))) => {
                SchemaNode::UnitVariant(name, variant)
            }
            SchemaBuilderNode::Newtype(type_name, inner) => {
                let inner = inner.build(builder)?;
                match type_name {
                    TypeName(name, None) => SchemaNode::NewtypeStruct(name, inner),
                    TypeName(name, Some(variant)) => {
                        SchemaNode::NewtypeVariant(name, variant, inner)
                    }
                }
            }
            SchemaBuilderNode::Map(key, value) => {
                SchemaNode::Map(key.build(builder)?, value.build(builder)?)
            }
            SchemaBuilderNode::Sequence(item) => SchemaNode::Sequence(item.build(builder)?),
            SchemaBuilderNode::Union(variants) => {
                let mut variants = variants
                    .into_iter()
                    .map(|variant| variant.build(builder))
                    .collect::<Result<Vec<_>, _>>()?;
                variants.sort_unstable();
                variants.dedup();
                if variants.len()
                    > usize::try_from(u32::MAX).expect("usize must be at least 32 bits")
                {
                    return Err(TraceError::from(TraceLimitErrorKind::UnionVariants));
                }
                SchemaNode::Union(builder.node_lists.intern_from(variants)?)
            }
            SchemaBuilderNode::Record {
                name,
                field_names,
                field_types,
                mut skippable,
            } => {
                // Filter out fields whose type is an empty union (bottom-typed) from the skippable
                // list. These are fields that are ALWAYS skipped, and therefore not considered
                // skippABLE.
                //
                // Struct fields are split into three categories:
                // 1. Fields that are never skipped (type != Union[], not in skip list). Do not
                //    require discriminant bits.
                // 2. Fields that are always skipped (type == Union[], not in skip list). Do not
                //    require discriminant bits.
                // 3. Fields that are sometimes skipped (type != Union[], present in skip list).
                //    Require discriminant bits.
                skippable.retain(|&index| {
                    !matches!(
                        &field_types[usize::from(index)],
                        SchemaBuilderNode::Union(variants) if variants.is_empty()
                    )
                });
                if skippable.len() > MAX_SKIPPABLE_FIELDS {
                    return Err(TraceError::from(TraceLimitErrorKind::SkippableFields));
                }
                let field_types = field_types
                    .into_iter()
                    .map(|field_type| field_type.build(builder))
                    .collect::<Result<Vec<_>, _>>()?;
                let field_types = builder.node_lists.intern_from(field_types)?;
                match (name, field_names) {
                    (None, None) => SchemaNode::Tuple(field_types),
                    (Some(TypeName(name, None)), None) => {
                        SchemaNode::TupleStruct(name, field_types)
                    }
                    (Some(TypeName(name, Some(variant))), None) => {
                        SchemaNode::TupleVariant(name, variant, field_types)
                    }
                    (None, Some(_field_names)) => {
                        unreachable!("anonymous structs don't exist in rust!")
                    }
                    (Some(TypeName(name, None)), Some(field_names)) => {
                        let skip_list = builder.member_lists.intern_from(skippable)?;
                        SchemaNode::Struct(name, field_names, skip_list, field_types)
                    }
                    (Some(TypeName(name, Some(variant))), Some(field_names)) => {
                        let skip_list = builder.member_lists.intern_from(skippable)?;
                        SchemaNode::StructVariant(
                            name,
                            variant,
                            field_names,
                            skip_list,
                            field_types,
                        )
                    }
                }
            }
        };
        builder.nodes.intern(built).map_err(Into::into)
    }
}

macro_rules! fn_serialize_as_u8 {
    ($(($fn_name:ident, $value_type:ty, $node:ident),)+) => {
        $(
            #[inline]
            fn $fn_name(mut self, value: $value_type) -> Result<Self::Ok, Self::Error> {
                self.push_trace(TraceNodeKind::$node);
                self.data.push(value as u8);
                Ok(SchemaBuilderNode::$node)
            }
        )+
    };
}

macro_rules! fn_serialize_as_le_bytes {
    ($(($fn_name:ident, $value_type:ty, $node:ident ),)+) => {
        $(
            #[inline]
            fn $fn_name(mut self, value: $value_type) -> Result<Self::Ok, Self::Error> {

                self.push_trace(TraceNodeKind::$node);
                self.data.extend_from_slice(&value.to_le_bytes());
                Ok(SchemaBuilderNode::$node)
            }
        )+
    };
}

impl<'a> Serializer for RootSerializer<'a> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    type SerializeSeq = SequenceSchemaBuilder<'a>;
    type SerializeTuple = TupleSchemaBuilder<'a>;
    type SerializeTupleStruct = TupleSchemaBuilder<'a>;
    type SerializeTupleVariant = TupleSchemaBuilder<'a>;
    type SerializeMap = MapSchemaBuilder<'a>;
    type SerializeStruct = StructSchemaBuilder<'a>;
    type SerializeStructVariant = StructSchemaBuilder<'a>;

    fn_serialize_as_u8! {
        (serialize_bool, bool, Bool),
        (serialize_i8, i8, I8),
        (serialize_u8, u8, U8),
    }

    fn_serialize_as_le_bytes! {
        (serialize_i16, i16, I16),
        (serialize_i32, i32, I32),
        (serialize_i64, i64, I64),
        (serialize_i128, i128, I128),
        (serialize_u16, u16, U16),
        (serialize_u32, u32, U32),
        (serialize_u64, u64, U64),
        (serialize_u128, u128, U128),
        (serialize_f32, f32, F32),
        (serialize_f64, f64, F64),
    }

    #[inline]
    fn serialize_char(mut self, value: char) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::Char);
        self.push_u32(u32::from(value));
        Ok(SchemaBuilderNode::Char)
    }

    #[inline]
    fn serialize_str(mut self, value: &str) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::String);
        self.push_length_bytes(value.as_bytes())?;
        Ok(SchemaBuilderNode::String)
    }

    #[inline]
    fn serialize_bytes(mut self, value: &[u8]) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::Bytes);
        self.push_length_bytes(value)?;
        Ok(SchemaBuilderNode::Bytes)
    }

    #[inline]
    fn serialize_none(mut self) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::OptionNone);
        Ok(SchemaBuilderNode::OptionNone)
    }

    #[inline]
    fn serialize_some<T>(mut self, value: &T) -> Result<Self::Ok, Self::Error>
    where
        T: ?Sized + Serialize,
    {
        self.push_trace(TraceNodeKind::OptionSome);
        T::serialize(value, self).map(|inner| SchemaBuilderNode::OptionSome(Box::new(inner)))
    }

    #[inline]
    fn serialize_unit(mut self) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::Unit);
        Ok(SchemaBuilderNode::Unit(None))
    }

    #[inline]
    fn serialize_unit_struct(mut self, name: &'static str) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::UnitStruct);
        Ok(SchemaBuilderNode::Unit(Some(self.push_struct_name(name)?)))
    }

    #[inline]
    fn serialize_unit_variant(
        mut self,
        name: &'static str,
        _variant_index: u32,
        variant: &'static str,
    ) -> Result<Self::Ok, Self::Error> {
        self.push_trace(TraceNodeKind::UnitVariant);
        Ok(SchemaBuilderNode::Unit(Some(
            self.push_variant_name(name, variant)?,
        )))
    }

    #[inline]
    fn serialize_newtype_struct<T>(
        mut self,
        name: &'static str,
        value: &T,
    ) -> Result<Self::Ok, Self::Error>
    where
        T: ?Sized + Serialize,
    {
        self.push_trace(TraceNodeKind::NewtypeStruct);
        Ok(SchemaBuilderNode::Newtype(
            self.push_struct_name(name)?,
            Box::new(T::serialize(value, self)?),
        ))
    }

    #[inline]
    fn serialize_newtype_variant<T>(
        mut self,
        name: &'static str,
        _variant_index: u32,
        variant: &'static str,
        value: &T,
    ) -> Result<Self::Ok, Self::Error>
    where
        T: ?Sized + Serialize,
    {
        self.push_trace(TraceNodeKind::NewtypeVariant);
        Ok(SchemaBuilderNode::Newtype(
            self.push_variant_name(name, variant)?,
            Box::new(T::serialize(value, self)?),
        ))
    }

    #[inline]
    fn serialize_seq(mut self, _len: Option<usize>) -> Result<Self::SerializeSeq, Self::Error> {
        self.push_trace(TraceNodeKind::Sequence);
        Ok(SequenceSchemaBuilder {
            reserved_length: self.reserve_u32()?,
            item: SchemaBuilderNode::default(),
            length: 0,
            parent: self,
        })
    }

    #[inline]
    fn serialize_tuple(mut self, len: usize) -> Result<Self::SerializeTuple, Self::Error> {
        self.push_trace(TraceNodeKind::Tuple);
        self.push_u32_length(len)?;
        Ok(TupleSchemaBuilder {
            name: None,
            schemas: Vec::with_capacity(len),
            length: len,
            parent: self,
        })
    }

    #[inline]
    fn serialize_tuple_struct(
        mut self,
        name: &'static str,
        len: usize,
    ) -> Result<Self::SerializeTupleStruct, Self::Error> {
        self.push_trace(TraceNodeKind::TupleStruct);
        self.push_u32_length(len)?;
        Ok(TupleSchemaBuilder {
            name: Some(self.push_struct_name(name)?),
            schemas: Vec::with_capacity(len),
            length: len,
            parent: self,
        })
    }

    #[inline]
    fn serialize_tuple_variant(
        mut self,
        name: &'static str,
        _variant_index: u32,
        variant: &'static str,
        len: usize,
    ) -> Result<Self::SerializeTupleVariant, Self::Error> {
        self.push_trace(TraceNodeKind::TupleVariant);
        self.push_u32_length(len)?;
        Ok(TupleSchemaBuilder {
            name: Some(self.push_variant_name(name, variant)?),
            schemas: Vec::with_capacity(len),
            length: len,
            parent: self,
        })
    }

    #[inline]
    fn serialize_map(mut self, _len: Option<usize>) -> Result<Self::SerializeMap, Self::Error> {
        self.push_trace(TraceNodeKind::Map);
        Ok(MapSchemaBuilder {
            reserved_length: self.reserve_u32()?,
            key_schema: SchemaBuilderNode::default(),
            value_schema: SchemaBuilderNode::default(),
            length: 0,
            parent: self,
        })
    }

    #[inline]
    fn serialize_struct(
        mut self,
        name: &'static str,
        len: usize,
    ) -> Result<Self::SerializeStruct, Self::Error> {
        self.push_trace(TraceNodeKind::Struct);
        StructSchemaBuilder::new(self.push_struct_name(name)?, len, self)
    }

    #[inline]
    fn serialize_struct_variant(
        mut self,
        name: &'static str,
        _variant_index: u32,
        variant: &'static str,
        len: usize,
    ) -> Result<Self::SerializeStructVariant, Self::Error> {
        self.push_trace(TraceNodeKind::StructVariant);
        StructSchemaBuilder::new(self.push_variant_name(name, variant)?, len, self)
    }

    #[inline]
    fn is_human_readable(&self) -> bool {
        false
    }
}

pub(crate) struct SequenceSchemaBuilder<'a> {
    parent: RootSerializer<'a>,
    reserved_length: TraceIndex,
    item: SchemaBuilderNode,
    length: usize,
}

impl<'a> SerializeSeq for SequenceSchemaBuilder<'a> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_element<T>(&mut self, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        self.length += 1;
        self.item
            .union(T::serialize(value, self.parent.reborrow())?);
        Ok(())
    }

    #[inline]
    fn end(mut self) -> Result<Self::Ok, Self::Error> {
        self.parent.fill_reserved_bytes(
            self.reserved_length,
            &u32::try_from(self.length)
                .map_err(|_| TraceLimitErrorKind::Values)?
                .to_le_bytes(),
        );
        Ok(SchemaBuilderNode::Sequence(Box::new(self.item)))
    }
}

pub(crate) struct MapSchemaBuilder<'a> {
    parent: RootSerializer<'a>,
    reserved_length: TraceIndex,
    key_schema: SchemaBuilderNode,
    value_schema: SchemaBuilderNode,
    length: usize,
}

impl SerializeMap for MapSchemaBuilder<'_> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_key<T>(&mut self, key: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        self.length += 1;
        self.key_schema
            .union(T::serialize(key, self.parent.reborrow())?);
        Ok(())
    }

    #[inline]
    fn serialize_value<T>(&mut self, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        self.value_schema
            .union(T::serialize(value, self.parent.reborrow())?);
        Ok(())
    }

    #[inline]
    fn end(mut self) -> Result<Self::Ok, Self::Error> {
        self.parent.fill_reserved_bytes(
            self.reserved_length,
            &u32::try_from(self.length)
                .map_err(|_| TraceLimitErrorKind::Values)?
                .to_le_bytes(),
        );
        Ok(SchemaBuilderNode::Map(
            Box::new(self.key_schema),
            Box::new(self.value_schema),
        ))
    }
}

pub(crate) struct TupleSchemaBuilder<'a> {
    parent: RootSerializer<'a>,
    name: Option<TypeName>,
    schemas: Vec<SchemaBuilderNode>,
    length: usize,
}

impl SerializeTuple for TupleSchemaBuilder<'_> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_element<T>(&mut self, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        self.schemas
            .push(T::serialize(value, self.parent.reborrow())?);
        Ok(())
    }

    #[inline]
    fn end(self) -> Result<Self::Ok, Self::Error> {
        if self.schemas.len() != self.length {
            return Err(TraceError::LengthMismatch);
        }
        Ok(SchemaBuilderNode::Record {
            name: self.name,
            field_names: None,
            field_types: self.schemas,
            skippable: Vec::new(),
        })
    }
}

impl SerializeTupleStruct for TupleSchemaBuilder<'_> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_field<T>(&mut self, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        <Self as SerializeTuple>::serialize_element(self, value)
    }

    #[inline]
    fn end(self) -> Result<Self::Ok, Self::Error> {
        <Self as SerializeTuple>::end(self)
    }
}

impl SerializeTupleVariant for TupleSchemaBuilder<'_> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_field<T>(&mut self, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        <Self as SerializeTuple>::serialize_element(self, value)
    }

    #[inline]
    fn end(self) -> Result<Self::Ok, Self::Error> {
        <Self as SerializeTuple>::end(self)
    }
}

pub(crate) struct StructSchemaBuilder<'a> {
    parent: RootSerializer<'a>,
    name: TypeName,
    reserved_field_name_list: TraceIndex,
    reserved_field_presence: TraceIndex,
    field_names: Vec<FieldNameIndex>,
    field_types: Vec<SchemaBuilderNode>,
    skipped: Vec<MemberIndex>,
    length: usize,
}

impl<'a> StructSchemaBuilder<'a> {
    pub fn new(
        name: TypeName,
        length: usize,
        mut parent: RootSerializer<'a>,
    ) -> Result<Self, TraceError> {
        let reserved_field_name_list = parent.reserve_u32()?;
        // Note that, maybe counter-intuitively, this `length` does NOT include skipped fields.
        // This explicitly documented by `serde`.
        //
        // So we're reserving precisely as much data as we're going to serialize. This is important
        // for the whole "skippable" field logic to work.
        parent.push_u32_length(length)?;
        Ok(Self {
            name,
            reserved_field_name_list,
            reserved_field_presence: parent.reserve_field_presence(length)?,
            field_names: Vec::with_capacity(length),
            field_types: Vec::with_capacity(length),
            skipped: Vec::new(),
            length,
            parent,
        })
    }
}

impl SerializeStruct for StructSchemaBuilder<'_> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_field<T>(&mut self, key: &'static str, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        if self.field_names.len() - self.skipped.len() >= self.length {
            return Err(TraceError::LengthMismatch);
        }
        self.reserved_field_presence = self.parent.write_field_presence(
            self.reserved_field_presence,
            MemberIndex::try_from(self.field_names.len())?,
        )?;
        self.field_names.push(self.parent.intern_field_name(key)?);
        self.field_types
            .push(T::serialize(value, self.parent.reborrow())?);
        Ok(())
    }

    #[inline]
    fn skip_field(&mut self, key: &'static str) -> Result<(), Self::Error> {
        let skipped = self.field_names.len().try_into()?;
        self.field_names.push(self.parent.intern_field_name(key)?);
        self.field_types.push(SchemaBuilderNode::default());
        // Push to `skipped` last, so that early returns cannot break
        // `skipped.len() <= field_names.len()`.
        self.skipped.push(skipped);
        Ok(())
    }

    #[inline]
    fn end(mut self) -> Result<Self::Ok, Self::Error> {
        // The second condition can only trigger if a `Serialize` implementation ignored an error
        // returned by `serialize_field` and carried on, leaving names and types out of sync.
        if self.field_names.len() - self.skipped.len() != self.length
            || self.field_names.len() != self.field_types.len()
        {
            return Err(TraceError::LengthMismatch);
        }
        let field_names = Some(
            self.parent
                .fill_reserved_field_name_list(self.reserved_field_name_list, self.field_names)?,
        );
        Ok(SchemaBuilderNode::Record {
            name: Some(self.name),
            field_names,
            field_types: self.field_types,
            skippable: self.skipped,
        })
    }
}

impl SerializeStructVariant for StructSchemaBuilder<'_> {
    type Ok = SchemaBuilderNode;
    type Error = TraceError;

    #[inline]
    fn serialize_field<T>(&mut self, key: &'static str, value: &T) -> Result<(), Self::Error>
    where
        T: ?Sized + serde::Serialize,
    {
        <Self as SerializeStruct>::serialize_field(self, key, value)
    }

    #[inline]
    fn skip_field(&mut self, key: &'static str) -> Result<(), Self::Error> {
        <Self as SerializeStruct>::skip_field(self, key)
    }

    #[inline]
    fn end(self) -> Result<Self::Ok, Self::Error> {
        <Self as SerializeStruct>::end(self)
    }
}