neodyn_xc 0.3.0

//! Serializing into the machine-readable, compact binary format.

use std::mem;
use std::io::{ Write, BufWriter };
use std::iter::FromIterator;
use std::convert::{ TryFrom, TryInto };
use std::fmt::Display;
use std::ops::Range;
use std::collections::BTreeMap;
use serde::ser::{
    Serialize, Serializer, Error as SerError,
    SerializeSeq, SerializeTuple, SerializeTupleStruct,
    SerializeMap, SerializeStruct,
    SerializeTupleVariant, SerializeStructVariant,
};
use byteorder::{ ByteOrder, LittleEndian };
use crate::error::{ Error, ResultExt };
use crate::format::*;

/// Serializes a value to a writer as the Neodyn Exchange binary representation.
///
/// Does not perform any buffering.
pub fn to_writer<W, T>(writer: W, value: &T) -> Result<(), Error>
    where
        W: Write,
        T: ?Sized + Serialize,
{
    let mut serializer = BinarySerializer::new();
    value.serialize(&mut serializer)?;
    serializer.finalize(writer)
}

/// Serializes a value to a writer as the Neodyn Exchange binary representation.
///
/// Performs buffering by internally wrapping the `writer` in a buffered writer.
pub fn to_writer_buffered<W, T>(writer: W, value: &T) -> Result<(), Error>
    where
        W: Write,
        T: ?Sized + Serialize,
{
    to_writer(BufWriter::new(writer), value)
}

/// Serializes a value in-memory as the Neodyn Exchange binary representation.
pub fn to_bytes<T>(value: &T) -> Result<Vec<u8>, Error>
    where
        T: ?Sized + Serialize,
{
    // For the rationale behind an initial capacity of 4k, see the relevant
    // comment in the implementation of the text serializer.
    let mut buf = Vec::with_capacity(4096);
    to_writer(&mut buf, value)?;
    buf.shrink_to_fit();
    Ok(buf)
}

/// Encodes a `u64` with as many bytes as needed, then returns
/// the base-2 logarithm of the number of bytes as well as the
/// subslice of the encoding buffer actually used.
fn encode_uint(x: u64, buf: &mut [u8; 8]) -> (u8, &[u8]) {
    if let Ok(x) = u8::try_from(x) {
        buf[0] = x;
        (0b0000_0000, &buf[..1])
    } else if let Ok(x) = u16::try_from(x) {
        LittleEndian::write_u16(buf, x);
        (0b0000_0001, &buf[..2])
    } else if let Ok(x) = u32::try_from(x) {
        LittleEndian::write_u32(buf, x);
        (0b0000_0010, &buf[..4])
    } else {
        LittleEndian::write_u64(buf, x);
        (0b0000_0011, &buf[..8])
    }
}

/// Encodes an `i64` with as many bytes as needed, then returns
/// the base-2 logarithm of the number of bytes as well as the
/// subslice of the encoding buffer actually used.
///
/// This assumes 2's complement representation, which is how signed
/// integers work on every platform Rust currently supports.
/// However, regardless of future changes to Rust, the specification
/// of this crate will always be to use 2's complement.
#[allow(clippy::cast_sign_loss)]
fn encode_int(x: i64, buf: &mut [u8; 8]) -> (u8, &[u8]) {
    if let Ok(x) = i8::try_from(x) {
        buf[0] = x as u8;
        (0b0000_0000, &buf[..1])
    } else if let Ok(x) = i16::try_from(x) {
        LittleEndian::write_u16(buf, x as u16);
        (0b0000_0001, &buf[..2])
    } else if let Ok(x) = i32::try_from(x) {
        LittleEndian::write_u32(buf, x as u32);
        (0b0000_0010, &buf[..4])
    } else {
        LittleEndian::write_u64(buf, x as u64);
        (0b0000_0011, &buf[..8])
    }
}

/// Writes length data to an arbitrary writer. The major and minor type tags
/// of the value written will be taken from the respective arguments.
///
/// This either writes a "small" value, or invokes `encode_uint()`.
fn write_length_or_index<W: Write>(
    mut writer: W,
    len: usize,
    small_major: Option<u8>, // `None` if no small/compact representation exists
    big_major: u8,
    big_minor: u8,
) -> Result<(), Error> {
    if big_major & MAJOR_TYPE_MASK != big_major {
        return Err(Error::new("bug: major type for big representation exceeds mask"));
    }
    if big_minor & MINOR_TYPE_MASK != big_minor {
        return Err(Error::new("bug: minor type for big representation exceeds mask"));
    }

    // When the value has a small/compact representation, use it if possible.
    if let Some(major) = small_major {
        if major & MAJOR_TYPE_MASK != major {
            return Err(Error::new("bug: major type for small representation exceeds mask"));
        }

        if let Ok(u) = SmallUint::try_from(len) {
            let byte = u.encode(major);
            return writer.write_all(&[byte]).conv_err();
        }
    }

    // Otherwise, use the big representation.
    let mut tmp_buf = [0; 8];
    let (log_len_len, buf) = encode_uint(len.try_into()?, &mut tmp_buf);
    let marker = big_major | big_minor | (log_len_len & LOG_LENGTH_MASK);

    if log_len_len & LOG_LENGTH_MASK != log_len_len {
        return Err(Error::new("bug: log length exceeds mask"));
    }

    writer.write_all(&[marker])?;
    writer.write_all(buf).conv_err()
}

/// Determines the amount of memory required for encoding a `usize` that
/// is the number of items in an array or the number of entries in a map.
fn complex_type_count_buf_size(count: usize) -> Result<usize, Error> {
    if SmallUint::try_from(count).is_ok() {
        Ok(1) // 1-byte (3 + 5 bits) inline compact encoding
    } else {
        let (log_len, _) = encode_uint(count.try_into()?, &mut [0; 8]);
        Ok(1 + (1 << log_len)) // +1 byte for type tag
    }
}

/// Attempt to write the given count into the provided buffer.
///
/// If the count is too large to fit into the buffer, return the error.
///
/// If the count is too small so that it doesn't require a buffer as big as
/// specified, still write it in little-endian format, padded with trailing
/// zeroes in the most significant bytes, so that the whole buffer is used.
fn write_complex_type_count_exact(
    buf: &mut [u8],
    count: usize,
    small_major: u8,
    big_minor: u8,
) -> Result<(), Error> {
    let buf_len = buf.len();
    let err = || Err(Error::custom(format_args!(
        "can't encode count {} into buffer of size {}; \
         incorrect size hint from array/tuple/map/struct",
        count, buf_len
    )));
    let (tag, bytes) = buf.split_first_mut().expect("empty count buffer");

    #[allow(clippy::identity_op)]
    match bytes.len() {
        0 => if let Ok(u) = SmallUint::try_from(count) {
            // inline "small uint" encoding, tag only
            *tag = u.encode(small_major);
        } else {
            err()?
        },
        1 => if let Ok(n) = u8::try_from(count) {
            // tag + 1 byte (log2(length) = 0)
            *tag = MAJOR_TYPE_BIG_VALUE | big_minor | 0x00;
            bytes[0] = n;
        } else {
            err()?
        },
        2 => if let Ok(n) = u16::try_from(count) {
            // tag + 2 bytes (log2(length) = 1)
            *tag = MAJOR_TYPE_BIG_VALUE | big_minor | 0x01;
            LittleEndian::write_u16(bytes, n);
        } else {
            err()?
        },
        4 => if let Ok(n) = u32::try_from(count) {
            // tag + 4 bytes (log2(length) = 2)
            *tag = MAJOR_TYPE_BIG_VALUE | big_minor | 0x02;
            LittleEndian::write_u32(bytes, n);
        } else {
            err()?
        },
        8 => if let Ok(n) = u64::try_from(count) {
            // tag + 8 bytes (log2(length) = 3)
            *tag = MAJOR_TYPE_BIG_VALUE | big_minor | 0x03;
            LittleEndian::write_u64(bytes, n);
        } else {
            err()?
        },
        _ => err()?
    }

    Ok(())
}

/// Represents a type storable in the symbol table after encoding.
trait Internable: AsRef<[u8]> + Into<Vec<u8>> {
    /// The type needed for interpreting this symbol appropriately.
    const SYMBOL_TYPE: SymbolType;
}

impl Internable for &[u8] {
    const SYMBOL_TYPE: SymbolType = SymbolType::Blob;
}

impl Internable for &str {
    const SYMBOL_TYPE: SymbolType = SymbolType::Str;
}

impl Internable for String {
    const SYMBOL_TYPE: SymbolType = SymbolType::Str;
}

/// Indicates how a symbol in the symbol table may be used.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum SymbolType {
    /// The symbol is only ever used as an opaque blob of bytes.
    Blob,
    /// The symbol may be used as a string too.
    Str,
}

impl SymbolType {
    /// Returns the value major type for this symbol type as a raw byte.
    /// This will be written to the **body,** not in the symbol table.
    const fn value_major(self) -> u8 {
        match self {
            SymbolType::Blob => MAJOR_TYPE_SMALL_BLOB,
            SymbolType::Str  => MAJOR_TYPE_SMALL_STRING,
        }
    }

    /// Returns the value minor type for this symbol type as a raw byte.
    /// This will be written to the **body,** not in the symbol table.
    const fn value_minor(self) -> u8 {
        match self {
            SymbolType::Blob => MINOR_TYPE_BLOB,
            SymbolType::Str  => MINOR_TYPE_STRING,
        }
    }

    /// Returns the marker byte for empty instances of this type.
    /// This will be written to the **body,** not in the symbol table.
    const fn empty_tag(self) -> u8 {
        match self {
            SymbolType::Blob => VALUE_BYTE_EMPTY_BLOB,
            SymbolType::Str  => VALUE_BYTE_EMPTY_STRING,
        }
    }
}

/// Metadata for an interned symbol. This contains all information about a
/// symbol (blob or string) in the symbol table, except the actual payload.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct SymbolMeta {
    /// The index of the symbol in the table.
    index: usize,
    /// The number of times the symbol is referenced in the body.
    use_count: usize,
    /// The type of the payload, either blob or string.
    ty: SymbolType,
}

impl SymbolMeta {
    /// Create a new symbol metadata for the symbol with the specified
    /// index and type.
    fn new<T: Internable>(index: usize) -> Self {
        SymbolMeta {
            index: index,
            use_count: 1,
            ty: T::SYMBOL_TYPE,
        }
    }

    /// Increment the use count of the symbol, and if necessary, change its
    /// symbol type to string.
    fn use_as<T: Internable>(&mut self) {
        self.use_count += 1;

        // Upgrade own type to string if necessary, that is if we have,
        // at least once, been used as a string.
        match T::SYMBOL_TYPE {
            SymbolType::Blob => {} // do nothing if we're being used as a blob
            SymbolType::Str => {
                // if we're being used as a string, change own type to string
                self.ty = SymbolType::Str;
            }
        }
    }

    /// Returns whether this symbol is referenced in the body more than once.
    const fn is_multi_use(&self) -> bool {
        self.use_count > 1
    }

    /// The major type that will be written to the symbol table.
    ///
    /// It depends on the `ty`pe of the symbol as well as its `use_count`.
    const fn symtab_major(&self) -> u8 {
        match self.ty {
            SymbolType::Blob => if self.is_multi_use() {
                MAJOR_TYPE_SMALL_BLOB_MULTI
            } else {
                MAJOR_TYPE_SMALL_BLOB_ONCE
            },
            SymbolType::Str => if self.is_multi_use() {
                MAJOR_TYPE_SMALL_STRING_MULTI
            } else {
                MAJOR_TYPE_SMALL_STRING_ONCE
            },
        }
    }

    /// The minor type that will be written to the symbol table.
    ///
    /// It depends on the `ty`pe of the symbol as well as its `use_count`.
    const fn symtab_minor(&self) -> u8 {
        match self.ty {
            SymbolType::Blob => if self.is_multi_use() {
                MINOR_TYPE_BLOB_MULTI
            } else {
                MINOR_TYPE_BLOB_ONCE
            },
            SymbolType::Str => if self.is_multi_use() {
                MINOR_TYPE_STRING_MULTI
            } else {
                MINOR_TYPE_STRING_ONCE
            },
        }
    }
}

/// Serializer for the machine-readable compact binary format.
///
/// **The serializer must always be `finalize()`d explicitly
/// after the value is serialized!**
#[derive(Debug, Clone)]
pub struct BinarySerializer {
    /// The buffer for the body, which needs to be serialized after the header.
    body: Vec<u8>,
    /// String and blob interner, mapping unique bytes to indices.
    /// This is a `BTreeMap` instead of a `HashMap` because hashing large
    /// blobs always requires traversing them from start to end, whereas
    /// deciding lexicographical ordering between two blobs may finish much
    /// earlier, specifically, upon encountering the first differing byte.
    bytes_to_meta: BTreeMap<Box<[u8]>, SymbolMeta>,
}

impl BinarySerializer {
    /// Create a new empty binary serializer.
    ///
    /// **The serializer must always be `finalize()`d explicitly
    /// after the value is serialized!**
    #[must_use]
    pub fn new() -> Self {
        BinarySerializer {
            body: Vec::with_capacity(4096),
            bytes_to_meta: BTreeMap::new(),
        }
    }

    /// Writes the header based on the interned strings and blobs,
    /// then writes the body as well.
    pub fn finalize<W: Write>(mut self, mut writer: W) -> Result<(), Error> {
        self.write_header(&mut writer)?;
        writer.write_all(&self.body)?;
        writer.flush().conv_err()
    }

    /// Writes the header, i.e. the "symbol table" of interned strings and
    /// blobs, in the correct order (order of insertion).
    fn write_header<W: Write>(&mut self, mut writer: W) -> Result<(), Error> {
        // An empty symbol table is never written. There's no ambiguity
        // because if the data doesn't start with a byte 000_000_NN,
        // then there's no symbol table and the value follows directly.
        if self.bytes_to_meta.is_empty() {
            return Ok(());
        }

        // First, write the length of the symbol table.
        write_length_or_index(&mut writer,
                              self.bytes_to_meta.len(),
                              None,
                              MAJOR_TYPE_SIMPLE,
                              MINOR_TYPE_SYMTAB)?;

        // Sort entries by index.
        // It's too bad that `BTreeMap` doesn't have `.drain()` yet.
        let sorted_by_index = {
            let map = mem::take(&mut self.bytes_to_meta);
            let mut v = Vec::from_iter(map);
            v.sort_by_key(|&(_, meta)| meta.index);
            v
        };

        // Now write the interned symbols. Iterate by value because this way
        // each buffer will be dropped immediately after having been written.
        // Therefore, we save memory when there are many large buffers, since
        // as the header grows, the buffers written free up memory accordingly.
        // (This applies only when the writer writes to memory.)
        for (i, (buf, meta)) in sorted_by_index.into_iter().enumerate() {
            if i != meta.index {
                return Err(Error::new("bug: non-bijective string interning"));
            }

            // First, write the length of the buffer.
            write_length_or_index(&mut writer,
                                  buf.len(),
                                  Some(meta.symtab_major()),
                                  MAJOR_TYPE_BIG_SYMBOL,
                                  meta.symtab_minor())?;

            // Then, if needed, write the use count of the symbol.
            // It is always written as an unsigned integer.
            if meta.is_multi_use() {
                write_length_or_index(&mut writer,
                                      meta.use_count,
                                      Some(MAJOR_TYPE_SMALL_UINT),
                                      MAJOR_TYPE_BIG_VALUE,
                                      MINOR_TYPE_UINT)?;
            }

            // Finally, write the actual symbol data.
            writer.write_all(&*buf)?;
        }

        Ok(())
    }

    /// Interns the byte buffer the value derefs to, then writes its unique
    /// index with the appropriate (given) type to the body buffer.
    fn write_interned_symbol<T>(&mut self, value: T) -> Result<(), Error>
        where
            T: Internable,
    {
        let byte_slice = value.as_ref();

        // Do not actually intern empty strings and blobs
        if byte_slice.is_empty() {
            self.body.push(T::SYMBOL_TYPE.empty_tag());
            return Ok(());
        }

        let index = match self.bytes_to_meta.get_mut(byte_slice) {
            Some(meta) => {
                // String or blob already interned. Do two things:
                //   1. Increment the use count.
                //   2. If latest use is a string, change the type to string.
                // Both of these tasks are performed by `use_as()`.
                meta.use_as::<T>();
                meta.index
            }
            None => {
                // Otherwise, intern now.
                let index = self.bytes_to_meta.len();
                let meta = SymbolMeta::new::<T>(index);
                let byte_buf = value.into().into();
                self.bytes_to_meta.insert(byte_buf, meta);
                index
            }
        };

        write_length_or_index(&mut self.body,
                              index,
                              Some(T::SYMBOL_TYPE.value_major()),
                              MAJOR_TYPE_BIG_VALUE,
                              T::SYMBOL_TYPE.value_minor())
    }
}

impl Default for BinarySerializer {
    fn default() -> Self {
        BinarySerializer::new()
    }
}

impl<'a> Serializer for &'a mut BinarySerializer {
    type Ok = ();
    type Error = Error;

    type SerializeSeq = BinaryComplexSerializer<'a>;
    type SerializeTuple = BinaryComplexSerializer<'a>;
    type SerializeTupleStruct = BinaryComplexSerializer<'a>;
    type SerializeTupleVariant = BinaryComplexSerializer<'a>;
    type SerializeMap = BinaryComplexSerializer<'a>;
    type SerializeStruct = BinaryComplexSerializer<'a>;
    type SerializeStructVariant = BinaryComplexSerializer<'a>;

    fn is_human_readable(&self) -> bool {
        false
    }

    fn serialize_bool(self, v: bool) -> Result<Self::Ok, Self::Error> {
        self.body.push(if v {
            VALUE_BYTE_TRUE
        } else {
            VALUE_BYTE_FALSE
        });
        Ok(())
    }

    fn serialize_i8(self, v: i8) -> Result<Self::Ok, Self::Error> {
        self.serialize_i64(v.into())
    }

    fn serialize_i16(self, v: i16) -> Result<Self::Ok, Self::Error> {
        self.serialize_i64(v.into())
    }

    fn serialize_i32(self, v: i32) -> Result<Self::Ok, Self::Error> {
        self.serialize_i64(v.into())
    }

    fn serialize_i64(self, v: i64) -> Result<Self::Ok, Self::Error> {
        if let Ok(i) = SmallInt::try_from(v) {
            self.body.push(i.encode());
        } else {
            let mut tmp_buf = [0; 8];
            let (log_len, buf) = encode_int(v, &mut tmp_buf);
            let major_minor = MAJOR_TYPE_BIG_VALUE | MINOR_TYPE_INT;
            let tag = major_minor | (log_len & LOG_LENGTH_MASK);
            self.body.push(tag);
            self.body.extend(buf);
        }

        Ok(())
    }

    fn serialize_i128(self, v: i128) -> Result<Self::Ok, Self::Error> {
        self.serialize_i64(v.try_into()?)
    }

    fn serialize_u8(self, v: u8) -> Result<Self::Ok, Self::Error> {
        self.serialize_u64(v.into())
    }

    fn serialize_u16(self, v: u16) -> Result<Self::Ok, Self::Error> {
        self.serialize_u64(v.into())
    }

    fn serialize_u32(self, v: u32) -> Result<Self::Ok, Self::Error> {
        self.serialize_u64(v.into())
    }

    fn serialize_u64(self, v: u64) -> Result<Self::Ok, Self::Error> {
        if let Ok(u) = SmallUint::try_from(v) {
            let byte = u.encode(MAJOR_TYPE_SMALL_UINT);
            self.body.push(byte);
        } else {
            let mut tmp_buf = [0; 8];
            let (log_len, buf) = encode_uint(v, &mut tmp_buf);
            let major_minor = MAJOR_TYPE_BIG_VALUE | MINOR_TYPE_UINT;
            let tag = major_minor | (log_len & LOG_LENGTH_MASK);
            self.body.push(tag);
            self.body.extend(buf);
        }

        Ok(())
    }

    fn serialize_u128(self, v: u128) -> Result<Self::Ok, Self::Error> {
        self.serialize_u64(v.try_into()?)
    }

    fn serialize_f32(self, v: f32) -> Result<Self::Ok, Self::Error> {
        if v.is_nan() {
            self.serialize_none()
        } else {
            // an `f32` is always 4 bytes long and log2(4) = 2
            let tag = MAJOR_TYPE_BIG_VALUE | MINOR_TYPE_FLOAT | 0b0000_0010;
            // see the official Rust docs on why `f32::to_bits()` is portable:
            // https://doc.rust-lang.org/std/primitive.f32.html#method.from_bits
            let mut buf = [0; 4];
            LittleEndian::write_u32(&mut buf, v.to_bits());
            self.body.push(tag);
            self.body.extend(&buf);
            Ok(())
        }
    }

    fn serialize_f64(self, v: f64) -> Result<Self::Ok, Self::Error> {
        if v.is_nan() {
            self.serialize_none()
        } else {
            // an `f64` is always 8 bytes long and log2(8) = 3
            let tag = MAJOR_TYPE_BIG_VALUE | MINOR_TYPE_FLOAT | 0b0000_0011;
            // see the official Rust docs on why `f64::to_bits()` is portable:
            // https://doc.rust-lang.org/std/primitive.f64.html#method.from_bits
            let mut buf = [0; 8];
            LittleEndian::write_u64(&mut buf, v.to_bits());
            self.body.push(tag);
            self.body.extend(&buf);
            Ok(())
        }
    }

    fn serialize_char(self, v: char) -> Result<Self::Ok, Self::Error> {
        self.serialize_str(v.encode_utf8(&mut [0; 4]))
    }

    fn serialize_str(self, v: &str) -> Result<Self::Ok, Self::Error> {
        self.write_interned_symbol(v)
    }

    fn serialize_bytes(self, v: &[u8]) -> Result<Self::Ok, Self::Error> {
        self.write_interned_symbol(v)
    }

    /// This method is implemented manually for efficiency. Since we need to
    /// store the heap-allocated byte buffer of the string anyway, we want
    /// to avoid cloning it when we actually insert it for the first time.
    /// For this, using `Into<Vec<u8>>` (instead of calling `to_vec()` on the
    /// byte slice of the `String`) is perfect, and that is exactly what the
    /// `Internable` bound allows us to do.
    fn collect_str<T: ?Sized + Display>(self, v: &T) -> Result<Self::Ok, Self::Error> {
        self.write_interned_symbol(v.to_string())
    }

    fn serialize_none(self) -> Result<Self::Ok, Self::Error> {
        self.body.push(VALUE_BYTE_NULL);
        Ok(())
    }

    fn serialize_some<T: ?Sized + Serialize>(self, value: &T) -> Result<Self::Ok, Self::Error> {
        self.body.push(VALUE_BYTE_OPT);
        value.serialize(self)
    }

    fn serialize_unit(self) -> Result<Self::Ok, Self::Error> {
        self.serialize_none()
    }

    fn serialize_unit_struct(self, _name: &'static str) -> Result<Self::Ok, Self::Error> {
        self.serialize_unit()
    }

    fn serialize_unit_variant(
        self,
        _name: &'static str,
        _variant_index: u32,
        variant: &'static str,
    ) -> Result<Self::Ok, Self::Error> {
        self.serialize_str(variant)
    }

    fn serialize_newtype_struct<T: ?Sized + Serialize>(
        self,
        _name: &'static str,
        value: &T,
    ) -> Result<Self::Ok, Self::Error> {
        value.serialize(self)
    }

    fn serialize_newtype_variant<T: ?Sized + Serialize>(
        self,
        _name: &'static str,
        _variant_index: u32,
        variant: &'static str,
        value: &T,
    ) -> Result<Self::Ok, Self::Error> {
        // First, introduce a singleton map, i.e. one of size 1.
        // Then, serialize the variant as its key.
        // Finally, serialize the value.
        self.body.push(MAJOR_TYPE_SMALL_MAP | 0x01);
        variant.serialize(&mut *self)?;
        value.serialize(self)
    }

    fn serialize_seq(self, len: Option<usize>) -> Result<Self::SerializeSeq, Self::Error> {
        BinaryComplexSerializer::new(self, len)
    }

    fn serialize_tuple(self, len: usize) -> Result<Self::SerializeTuple, Self::Error> {
        self.serialize_seq(len.into())
    }

    fn serialize_tuple_struct(
        self,
        _name: &'static str,
        len: usize,
    ) -> Result<Self::SerializeTupleStruct, Self::Error> {
        self.serialize_tuple(len)
    }

    fn serialize_tuple_variant(
        self,
        _name: &'static str,
        _variant_index: u32,
        variant: &'static str,
        len: usize,
    ) -> Result<Self::SerializeTupleVariant, Self::Error> {
        BinaryComplexSerializer::new_enum(self, variant, len)
    }

    fn serialize_map(self, len: Option<usize>) -> Result<Self::SerializeMap, Self::Error> {
        BinaryComplexSerializer::new(self, len)
    }

    fn serialize_struct(
        self,
        _name: &'static str,
        len: usize,
    ) -> Result<Self::SerializeStruct, Self::Error> {
        self.serialize_map(len.into())
    }

    fn serialize_struct_variant(
        self,
        _name: &'static str,
        _variant_index: u32,
        variant: &'static str,
        len: usize,
    ) -> Result<Self::SerializeStructVariant, Self::Error> {
        BinaryComplexSerializer::new_enum(self, variant, len)
    }
}

/// Helper for serializing sequences, maps, and enums.
#[derive(Debug)]
pub struct BinaryComplexSerializer<'a> {
    /// The main serializer that the data structure will be serialized to.
    serializer: &'a mut BinarySerializer,
    /// The number of items or entries actually written so far.
    count_so_far: usize,
    /// The subslice of `self.serializer.body` where the count will be written.
    count_range: Range<usize>,
}

impl<'a> BinaryComplexSerializer<'a> {
    /// Internal helper for `new()` and `new_enum()`.
    fn new_priv(ser: &'a mut BinarySerializer, length: usize) -> Result<Self, Error> {
        let buf_size = complex_type_count_buf_size(length)?;
        let body_size_before = ser.body.len();
        let body_size_after = body_size_before + buf_size;

        // make room for the length of the data structure to be serialized
        ser.body.resize(body_size_after, 0x00);

        Ok(BinaryComplexSerializer {
            serializer: ser,
            count_so_far: 0,
            count_range: body_size_before..body_size_after,
        })
    }

    /// Creates a complex type serializer that writes a sequence or a map
    /// to the wrapped serializer. If the sequence doesn't provide a size
    /// hint, then we'll assume the maximal possible length.
    fn new(ser: &'a mut BinarySerializer, length: Option<usize>) -> Result<Self, Error> {
        Self::new_priv(ser, length.unwrap_or(usize::MAX))
    }

    /// Creates a complex type serializer that writes a tuple variant or
    /// a struct variant to the wrapped serializer.
    fn new_enum(
        ser: &'a mut BinarySerializer,
        variant: &str,
        length: usize,
    ) -> Result<Self, Error> {
        // First, introduce a singleton map, i.e. one of size 1.
        // Then, serialize the variant as its key.
        // Finally, prepare for serializing the value.
        ser.body.push(MAJOR_TYPE_SMALL_MAP | 0x01);
        variant.serialize(&mut *ser)?;
        Self::new_priv(ser, length)
    }
}

impl<'a> SerializeSeq for BinaryComplexSerializer<'a> {
    type Ok = ();
    type Error = Error;

    fn serialize_element<T: ?Sized + Serialize>(&mut self, value: &T) -> Result<(), Self::Error> {
        self.count_so_far += 1;
        value.serialize(&mut *self.serializer)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        write_complex_type_count_exact(
            &mut self.serializer.body[self.count_range],
            self.count_so_far,
            MAJOR_TYPE_SMALL_ARRAY,
            MINOR_TYPE_ARRAY,
        )
    }
}

impl<'a> SerializeTuple for BinaryComplexSerializer<'a> {
    type Ok = <Self as SerializeSeq>::Ok;
    type Error = <Self as SerializeSeq>::Error;

    fn serialize_element<T: ?Sized + Serialize>(&mut self, value: &T) -> Result<(), Self::Error> {
        SerializeSeq::serialize_element(self, value)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        SerializeSeq::end(self)
    }
}

impl<'a> SerializeTupleStruct for BinaryComplexSerializer<'a> {
    type Ok = <Self as SerializeTuple>::Ok;
    type Error = <Self as SerializeTuple>::Error;

    fn serialize_field<T: ?Sized + Serialize>(&mut self, value: &T) -> Result<(), Self::Error> {
        SerializeTuple::serialize_element(self, value)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        SerializeTuple::end(self)
    }
}

impl<'a> SerializeMap for BinaryComplexSerializer<'a> {
    type Ok = ();
    type Error = Error;

    fn serialize_key<T: ?Sized + Serialize>(&mut self, key: &T) -> Result<(), Self::Error> {
        self.count_so_far += 1;
        key.serialize(&mut *self.serializer)
    }

    fn serialize_value<T: ?Sized + Serialize>(&mut self, value: &T) -> Result<(), Self::Error> {
        value.serialize(&mut *self.serializer)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        write_complex_type_count_exact(
            &mut self.serializer.body[self.count_range],
            self.count_so_far,
            MAJOR_TYPE_SMALL_MAP,
            MINOR_TYPE_MAP,
        )
    }
}

impl<'a> SerializeStruct for BinaryComplexSerializer<'a> {
    type Ok = <Self as SerializeMap>::Ok;
    type Error = <Self as SerializeMap>::Error;

    fn serialize_field<T: ?Sized + Serialize>(
        &mut self,
        key: &'static str,
        value: &T
    ) -> Result<(), Self::Error> {
        self.serialize_entry(key, value)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        SerializeMap::end(self)
    }
}

impl<'a> SerializeTupleVariant for BinaryComplexSerializer<'a> {
    type Ok = <Self as SerializeTuple>::Ok;
    type Error = <Self as SerializeTuple>::Error;

    fn serialize_field<T: ?Sized + Serialize>(&mut self, value: &T) -> Result<(), Self::Error> {
        SerializeTuple::serialize_element(self, value)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        SerializeTuple::end(self)
    }
}

impl<'a> SerializeStructVariant for BinaryComplexSerializer<'a> {
    type Ok = <Self as SerializeStruct>::Ok;
    type Error = <Self as SerializeStruct>::Error;

    fn serialize_field<T: ?Sized + Serialize>(
        &mut self,
        key: &'static str,
        value: &T
    ) -> Result<(), Self::Error> {
        self.serialize_entry(key, value)
    }

    fn end(self) -> Result<Self::Ok, Self::Error> {
        SerializeStruct::end(self)
    }
}

#[cfg(test)]
mod tests {
    use crate::error::Result;
    use super::complex_type_count_buf_size;

    /// This is only here in a module-level test because the
    /// function is private so there's no other way to test it.
    #[test]
    fn complex_type_count_buf_size_works() -> Result<()> {
        assert_eq!(complex_type_count_buf_size(0)?, 1);
        assert_eq!(complex_type_count_buf_size(31)?, 1);
        assert_eq!(complex_type_count_buf_size(32)?, 2);
        assert_eq!(complex_type_count_buf_size(255)?, 2);
        assert_eq!(complex_type_count_buf_size(256)?, 3);
        assert_eq!(complex_type_count_buf_size(65535)?, 3);

        #[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
        {
            assert_eq!(complex_type_count_buf_size(65536)?, 5);
            assert_eq!(complex_type_count_buf_size(4294967295)?, 5);
        }

        #[cfg(target_pointer_width = "64")]
        {
            assert_eq!(complex_type_count_buf_size(4294967296)?, 9);
            assert_eq!(complex_type_count_buf_size(18446744073709551615)?, 9);
        }

        Ok(())
    }
}