doubleentry 0.7.0

//! Canonical binary encoding.
//!
//! Hashes are only meaningful if the bytes fed to them are reproducible. This
//! module defines a fixed, field-ordered, length-prefixed encoding with exactly
//! one representation per value.
//!
//! The rules:
//!
//! - Integers are little-endian, fixed width. No varints, no leading-zero
//!   ambiguity.
//! - Variable-length data carries a `u64` byte-length prefix, so no concatenation
//!   of two fields can be reinterpreted as a different split.
//! - `Option` is a `0x00` / `0x01` discriminant followed by the payload when set.
//! - Sequences carry a `u64` element count and are written in the order the
//!   producer chose; the producer is responsible for that order being canonical.
//!
//! Lengths and counts are 64-bit rather than 32-bit so that no input can make
//! one saturate. A saturating prefix is worse than no prefix: it makes two
//! distinct values encode to the same bytes, which is exactly the collision the
//! prefix is there to rule out.
//!
//! General-purpose serialisation formats are deliberately not used here. Their
//! map ordering, integer widths, and string escaping are free to change between
//! versions, which would silently change every hash in a ledger.

/// Appends canonically encoded values to a byte buffer.
#[derive(Debug, Default)]
pub struct CanonicalWriter {
    buf: Vec<u8>,
}

impl CanonicalWriter {
    /// Creates an empty writer.
    #[must_use]
    pub fn new() -> Self {
        Self { buf: Vec::new() }
    }

    /// Creates a writer with room for `cap` bytes.
    #[must_use]
    pub fn with_capacity(cap: usize) -> Self {
        Self {
            buf: Vec::with_capacity(cap),
        }
    }

    /// Writes a single byte, typically a discriminant.
    pub fn u8(&mut self, v: u8) -> &mut Self {
        self.buf.push(v);
        self
    }

    /// Writes a `u16`.
    pub fn u16(&mut self, v: u16) -> &mut Self {
        self.buf.extend_from_slice(&v.to_le_bytes());
        self
    }

    /// Writes a `u32`.
    pub fn u32(&mut self, v: u32) -> &mut Self {
        self.buf.extend_from_slice(&v.to_le_bytes());
        self
    }

    /// Writes a `u64`.
    pub fn u64(&mut self, v: u64) -> &mut Self {
        self.buf.extend_from_slice(&v.to_le_bytes());
        self
    }

    /// Writes an `i32`.
    pub fn i32(&mut self, v: i32) -> &mut Self {
        self.buf.extend_from_slice(&v.to_le_bytes());
        self
    }

    /// Writes an `i64`.
    pub fn i64(&mut self, v: i64) -> &mut Self {
        self.buf.extend_from_slice(&v.to_le_bytes());
        self
    }

    /// Writes a `u128`.
    pub fn u128(&mut self, v: u128) -> &mut Self {
        self.buf.extend_from_slice(&v.to_le_bytes());
        self
    }

    /// Writes a bool as `0x00` or `0x01`.
    pub fn bool(&mut self, v: bool) -> &mut Self {
        self.buf.push(u8::from(v));
        self
    }

    /// Writes a length-prefixed byte string.
    ///
    /// The prefix is a `u64`, so it is exact for any slice that can exist on a
    /// 64-bit address space. A narrower prefix would have to decide what to do
    /// when a length does not fit, and every answer to that is wrong: truncating
    /// makes two different values encode identically, which is precisely the
    /// collision a length prefix exists to prevent.
    pub fn bytes(&mut self, v: &[u8]) -> &mut Self {
        self.u64(v.len() as u64);
        self.buf.extend_from_slice(v);
        self
    }

    /// Writes a length-prefixed UTF-8 string.
    pub fn str(&mut self, v: &str) -> &mut Self {
        self.bytes(v.as_bytes())
    }

    /// Writes a fixed-width byte array without a length prefix.
    ///
    /// Only valid for widths fixed by the schema, such as a digest or a UUID.
    pub fn fixed(&mut self, v: &[u8]) -> &mut Self {
        self.buf.extend_from_slice(v);
        self
    }

    /// Writes an optional value: `0x00`, or `0x01` followed by `f`.
    pub fn option<T: ?Sized>(&mut self, v: Option<&T>, f: impl FnOnce(&mut Self, &T)) -> &mut Self {
        match v {
            None => {
                self.u8(0);
            }
            Some(inner) => {
                self.u8(1);
                f(self, inner);
            }
        }
        self
    }

    /// Writes a counted sequence.
    ///
    /// The count is a `u64` for the same reason [`CanonicalWriter::bytes`] uses
    /// one: a count that saturates would let two sequences of different lengths
    /// encode identically.
    pub fn seq<T>(
        &mut self,
        items: impl ExactSizeIterator<Item = T>,
        mut f: impl FnMut(&mut Self, T),
    ) -> &mut Self {
        self.u64(items.len() as u64);
        for item in items {
            f(self, item);
        }
        self
    }

    /// Consumes the writer and returns the encoded bytes.
    #[must_use]
    pub fn finish(self) -> Vec<u8> {
        self.buf
    }

    /// The bytes written so far.
    #[must_use]
    pub fn as_slice(&self) -> &[u8] {
        &self.buf
    }
}

/// Reads back what [`CanonicalWriter`] wrote.
///
/// Only as much of the format as the crate actually decodes. Most canonical
/// encodings here are write-only — they exist to be hashed, and the value they
/// came from is the thing that is kept — so a full symmetric decoder would be
/// code with no caller and no test that could tell it had rotted.
///
/// The one value that genuinely round-trips is a
/// [`ConsistencyProof`](crate::ConsistencyProof), which a
/// [`Seal`](crate::Seal) carries and a backend therefore has to store and read
/// back.
///
/// Every read is fallible and every read is bounds-checked. A short buffer
/// yields `None` rather than a truncated value, and [`Self::is_exhausted`] is
/// what a caller uses to refuse trailing bytes — without which two different
/// buffers could decode to the same value, undoing exactly the unambiguity the
/// writer exists to provide.
#[derive(Debug, Clone)]
pub struct CanonicalReader<'a> {
    buf: &'a [u8],
    at: usize,
}

impl<'a> CanonicalReader<'a> {
    /// Starts reading at the beginning of `buf`.
    #[must_use]
    pub fn new(buf: &'a [u8]) -> Self {
        Self { buf, at: 0 }
    }

    /// How many bytes are left unread.
    #[must_use]
    pub fn remaining(&self) -> usize {
        self.buf.len().saturating_sub(self.at)
    }

    /// True when every byte has been consumed.
    ///
    /// Check this before accepting a decoded value: trailing bytes mean the
    /// buffer is not exactly one encoding of it.
    #[must_use]
    pub fn is_exhausted(&self) -> bool {
        self.remaining() == 0
    }

    /// Reads a fixed-width byte array.
    #[must_use]
    pub fn array<const N: usize>(&mut self) -> Option<[u8; N]> {
        let end = self.at.checked_add(N)?;
        let slice = self.buf.get(self.at..end)?;
        let out: [u8; N] = slice.try_into().ok()?;
        self.at = end;
        Some(out)
    }

    /// Reads a little-endian `u64`.
    #[must_use]
    pub fn u64(&mut self) -> Option<u64> {
        self.array::<8>().map(u64::from_le_bytes)
    }
}

/// A value with a canonical byte encoding.
pub trait Canonical {
    /// Appends this value's canonical encoding to `w`.
    fn encode(&self, w: &mut CanonicalWriter);

    /// Returns this value's canonical encoding as a fresh buffer.
    #[must_use]
    fn to_canonical_bytes(&self) -> Vec<u8> {
        let mut w = CanonicalWriter::new();
        self.encode(&mut w);
        w.finish()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn integers_are_little_endian_fixed_width() {
        let mut w = CanonicalWriter::new();
        w.u32(1);
        assert_eq!(w.finish(), vec![1, 0, 0, 0]);
    }

    #[test]
    fn length_prefix_disambiguates_concatenation() {
        let mut a = CanonicalWriter::new();
        a.str("ab").str("c");

        let mut b = CanonicalWriter::new();
        b.str("a").str("bc");

        assert_ne!(a.finish(), b.finish());
    }

    #[test]
    fn none_and_empty_are_distinct() {
        let mut none = CanonicalWriter::new();
        none.option(Option::<&str>::None, |w, v: &str| {
            w.str(v);
        });

        let mut empty = CanonicalWriter::new();
        empty.option(Some(""), |w, v: &str| {
            w.str(v);
        });

        assert_ne!(none.finish(), empty.finish());
    }

    #[test]
    fn sequence_counts_are_written() {
        let mut w = CanonicalWriter::new();
        w.seq([1u8, 2, 3].into_iter(), |w, v| {
            w.u8(v);
        });
        assert_eq!(w.finish(), vec![3, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3]);
    }

    #[test]
    fn empty_sequence_encodes_as_zero_count() {
        let mut w = CanonicalWriter::new();
        w.seq(core::iter::empty::<u8>(), |w, v| {
            w.u8(v);
        });
        assert_eq!(w.finish(), vec![0; 8]);
    }

    #[test]
    fn encoding_is_deterministic() {
        let build = || {
            let mut w = CanonicalWriter::new();
            w.u64(42)
                .str("hello")
                .bool(true)
                .option(Some(&7u8), |w, v| {
                    w.u8(*v);
                });
            w.finish()
        };
        assert_eq!(build(), build());
    }
}