boundgraph_core/

digest.rs

//! Content-addressed digests.

use std::fmt;
use std::str::FromStr;

use serde::{Deserialize, Serialize};

/// Width of a [`Digest`] in bytes.
pub const DIGEST_LEN: usize = 32;

/// A `blake3` digest of some canonical encoding.
///
/// This is the identity of every immutable primitive in BoundGraph. It is what makes
/// the ledger verifiable by a third party and what makes the content-addressed
/// store able to deduplicate: equal digests mean equal bytes, with no further
/// comparison needed.
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
#[serde(transparent)]
pub struct Digest(#[serde(with = "serde_bytes_32")] [u8; DIGEST_LEN]);

impl Digest {
    /// Hash raw bytes.
    ///
    /// Prefer [`Canonical::digest`](crate::Canonical::digest) for typed values;
    /// this is for bytes that are already in their final form, such as a raw
    /// tool output on its way into the content-addressed store.
    pub fn of(bytes: &[u8]) -> Self {
        Self(*blake3::hash(bytes).as_bytes())
    }

    /// Wrap an already-computed digest.
    pub const fn from_bytes(bytes: [u8; DIGEST_LEN]) -> Self {
        Self(bytes)
    }

    /// The raw digest bytes.
    pub const fn as_bytes(&self) -> &[u8; DIGEST_LEN] {
        &self.0
    }

    /// Lowercase hex, 64 characters.
    pub fn to_hex(&self) -> String {
        use fmt::Write as _;
        self.0.iter().fold(String::with_capacity(64), |mut s, b| {
            let _ = write!(s, "{b:02x}");
            s
        })
    }

    /// The first `n` hex characters, for logs and diagnostics.
    ///
    /// Never use an abbreviated digest for identity or comparison.
    pub fn short(&self, n: usize) -> String {
        let hex = self.to_hex();
        hex[..n.min(hex.len())].to_string()
    }
}

/// A digest was not valid lowercase hex of the right length.
#[derive(Debug, thiserror::Error)]
pub enum DigestParseError {
    /// Wrong number of characters.
    #[error("expected {expected} hex characters, found {found}")]
    Length {
        /// Characters required.
        expected: usize,
        /// Characters supplied.
        found: usize,
    },

    /// A character was not a hex digit.
    #[error("invalid hex character {ch:?} at position {index}")]
    Char {
        /// The offending character.
        ch: char,
        /// Its index in the input.
        index: usize,
    },
}

impl FromStr for Digest {
    type Err = DigestParseError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        if s.len() != DIGEST_LEN * 2 {
            return Err(DigestParseError::Length {
                expected: DIGEST_LEN * 2,
                found: s.len(),
            });
        }
        let mut out = [0u8; DIGEST_LEN];
        for (i, byte) in out.iter_mut().enumerate() {
            let pair = &s[i * 2..i * 2 + 2];
            *byte = u8::from_str_radix(pair, 16).map_err(|_| {
                let (index, ch) = pair
                    .char_indices()
                    .find(|(_, c)| !c.is_ascii_hexdigit())
                    .map(|(j, c)| (i * 2 + j, c))
                    .unwrap_or((i * 2, pair.chars().next().unwrap_or('?')));
                DigestParseError::Char { ch, index }
            })?;
        }
        Ok(Self(out))
    }
}

impl fmt::Display for Digest {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(&self.to_hex())
    }
}

impl fmt::Debug for Digest {
    /// Abbreviated, so debug output of a struct full of digests stays readable.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Digest({}…)", self.short(12))
    }
}

/// Fixed-width byte arrays are not `serde`-native, and the right encoding
/// differs by format.
///
/// **Binary formats get a byte string.** CBOR is what [`Canonical`] uses, and a
/// byte string rather than an array of 32 integers is what keeps the ledger a
/// quarter of the size. This encoding is part of the digest's *identity*: change
/// it and every content address in the system changes, so
/// `the_canonical_encoding_of_a_digest_is_fixed` pins it.
///
/// **Human-readable formats get hex.** A digest in a JSONL ledger has to be
/// greppable, comparable by eye, and the same 64 characters that
/// [`Display`](fmt::Display) prints — US-1002 requires the file to be readable
/// with `jq` and standard line tools, and `[229,197,127,…]` is readable by a
/// parser rather than by a person.
///
/// `serde` reports which kind of format it is talking to, so both are served
/// without either compromising.
mod serde_bytes_32 {
    use super::DIGEST_LEN;
    use serde::de::{Error as _, Unexpected};
    use serde::{Deserialize, Deserializer, Serializer};

    pub(super) fn serialize<S: Serializer>(
        bytes: &[u8; DIGEST_LEN],
        s: S,
    ) -> Result<S::Ok, S::Error> {
        if s.is_human_readable() {
            return s.serialize_str(&super::Digest(*bytes).to_hex());
        }
        s.serialize_bytes(bytes)
    }

    pub(super) fn deserialize<'de, D: Deserializer<'de>>(
        d: D,
    ) -> Result<[u8; DIGEST_LEN], D::Error> {
        if d.is_human_readable() {
            // The same parser `FromStr` uses, so a digest read back from a
            // ledger and one parsed from a command line cannot disagree.
            let hex = String::deserialize(d)?;
            return hex
                .parse::<super::Digest>()
                .map(|digest| *digest.as_bytes())
                .map_err(|_| D::Error::invalid_value(Unexpected::Str(&hex), &"64 hex characters"));
        }

        let raw = serde_bytes_helper::ByteBuf::deserialize(d)?;
        <[u8; DIGEST_LEN]>::try_from(raw.0.as_slice())
            .map_err(|_| D::Error::invalid_value(Unexpected::Bytes(&raw.0), &"exactly 32 bytes"))
    }

    /// Minimal stand-in for `serde_bytes`, to avoid the extra dependency.
    mod serde_bytes_helper {
        use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
        use std::fmt;

        pub(super) struct ByteBuf(pub(super) Vec<u8>);

        impl<'de> Deserialize<'de> for ByteBuf {
            fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
                struct V;
                impl<'de> Visitor<'de> for V {
                    type Value = ByteBuf;
                    fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                        f.write_str("a byte string")
                    }
                    fn visit_bytes<E: serde::de::Error>(self, v: &[u8]) -> Result<ByteBuf, E> {
                        Ok(ByteBuf(v.to_vec()))
                    }
                    fn visit_byte_buf<E: serde::de::Error>(self, v: Vec<u8>) -> Result<ByteBuf, E> {
                        Ok(ByteBuf(v))
                    }
                    fn visit_seq<A: SeqAccess<'de>>(self, mut seq: A) -> Result<ByteBuf, A::Error> {
                        let mut out = Vec::with_capacity(seq.size_hint().unwrap_or(32));
                        while let Some(b) = seq.next_element::<u8>()? {
                            out.push(b);
                        }
                        Ok(ByteBuf(out))
                    }
                    fn visit_str<E: serde::de::Error>(self, v: &str) -> Result<ByteBuf, E> {
                        Err(E::custom(format!("expected bytes, found string {v:?}")))
                    }
                }
                d.deserialize_bytes(V)
            }
        }
    }
}

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

    #[test]
    fn hex_is_lowercase_and_64_chars() {
        let d = Digest::of(b"boundgraph");
        let hex = d.to_hex();
        assert_eq!(hex.len(), 64);
        assert_eq!(hex, hex.to_lowercase());
        assert!(hex.chars().all(|c| c.is_ascii_hexdigit()));
    }

    #[test]
    fn hex_round_trips() {
        let d = Digest::of(b"boundgraph");
        assert_eq!(Digest::from_str(&d.to_hex()).unwrap(), d);
    }

    /// A digest's canonical encoding *is* part of its identity: change it and
    /// every content address in the system changes, silently and everywhere.
    /// So the bytes are pinned rather than merely round-tripped.
    ///
    /// CBOR major type 2 (byte string), one-byte length: `0x58 0x20`, then the
    /// 32 bytes themselves.
    #[test]
    fn the_canonical_encoding_of_a_digest_is_fixed() {
        let digest = Digest::of(b"boundgraph");
        let encoded = crate::to_canonical_cbor(&digest).unwrap();

        assert_eq!(encoded.len(), 34, "a two-byte header and 32 bytes");
        assert_eq!(encoded[0], 0x58, "byte string, one-byte length");
        assert_eq!(encoded[1], 0x20, "32 bytes long");
        assert_eq!(&encoded[2..], digest.as_bytes());

        let back: Digest = crate::from_canonical_cbor(&encoded).unwrap();
        assert_eq!(back, digest);
    }

    /// The criterion behind US-1002: a ledger has to be greppable. In a
    /// human-readable format a digest is the same 64 characters `Display`
    /// prints, not an array of 32 numbers.
    #[test]
    fn a_digest_reads_as_hex_in_a_human_readable_format() {
        let digest = Digest::of(b"boundgraph");
        let json = serde_json::to_string(&digest).unwrap();

        assert_eq!(json, format!("\"{}\"", digest.to_hex()));
        assert!(
            json.contains(&digest.to_hex()),
            "so `grep <digest>` finds the line that mentions it"
        );

        let back: Digest = serde_json::from_str(&json).unwrap();
        assert_eq!(back, digest);
    }

    #[test]
    fn a_malformed_hex_digest_is_refused_rather_than_truncated() {
        for bad in ["\"\"", "\"nothex\"", "\"ab\"", "\"zz00\""] {
            assert!(
                serde_json::from_str::<Digest>(bad).is_err(),
                "{bad} must not parse as a digest"
            );
        }
    }

    #[test]
    fn hashing_is_stable_and_input_sensitive() {
        assert_eq!(Digest::of(b"a"), Digest::of(b"a"));
        assert_ne!(Digest::of(b"a"), Digest::of(b"b"));
    }

    #[test]
    fn rejects_bad_hex() {
        assert!(matches!(
            Digest::from_str("abc"),
            Err(DigestParseError::Length { .. })
        ));
        let bad = "z".repeat(64);
        assert!(matches!(
            Digest::from_str(&bad),
            Err(DigestParseError::Char { .. })
        ));
    }

    #[test]
    fn debug_is_abbreviated_but_display_is_not() {
        let d = Digest::of(b"boundgraph");
        assert!(format!("{d:?}").len() < d.to_string().len());
        assert_eq!(d.to_string(), d.to_hex());
    }
}