alkblobs 0.1.0

//! The key side of the content-address layer (ADR-002 §Key encoding;
//! hashing-and-keys.md §Key encoding): the typed [`Key`] wrapper and
//! its physical byte encoding — the crate's declared one-way door.
//!
//! **One-way door.** Key bytes persist in backend rows and `local`
//! engine filenames with no migration story; the encoding is frozen
//! once a backend ships data (AGENTS.md convention 5, ADR-002). It is
//! implemented byte-exactly to the ADR and reviewed line-by-line at
//! the wave gate. Backends are opaque to all of it: they store
//! `&[u8]` keys, and [`Key::as_bytes`]/[`Key::from_bytes`] are the
//! only conversions across the backend boundary; only the store core
//! constructs and interprets typed keys (ADR-003).
//!
//! Physical layout: `key := <algorithm byte> <digest bytes>` —
//! `0x01` = git-blob-sha-256 (32-byte digest; total 33), `0x02` =
//! git-blob-sha-1 (20-byte digest; total 21), `0x03`/`0x04` =
//! git-object-sha-1/sha-256 (ADR-018's git-object derivation family,
//! digests 20/32 — see hashing.rs); fixed length per
//! algorithm so enum-tagged keys sort in total order (required for
//! the sweep's live-set diffs; the family sorts after the blob
//! members). Validation is rejects-never-guesses:
//! truncated keys, unknown algorithm bytes (reserved `0x00` included)
//! and wrong digest lengths are [`Error::KeyInvalid`] — never a
//! guess (POC #1 finding 5's length-checking standard).

use std::cmp::Ordering;
use std::hash::{Hash, Hasher};
use std::ops::Deref;

use crate::hashing::{Algorithm, Digest};
use crate::Error;

/// The physical encoding's fixed capacity: the tag byte plus the
/// widest registered digest (32 — the sha-256 members; ADR-002 §Key
/// encoding). A new wider algorithm is a new registry byte (a new
/// ADR) and revisits this ceiling with it.
const KEY_BYTES_CAP: usize = 1 + 32;

/// The typed content-address wrapper: a [`Digest`] that converts to
/// the physical key encoding where it crosses the backend boundary.
///
/// Ordering is the keys' total order — registry byte first, then
/// digest bytes — matching [`Key::as_bytes`] ordering byte-for-byte.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Key(Digest);

impl Key {
    /// The known-length canonical derivation, wrapped —
    /// `H("blob <len>\0" + content)` (see [`Digest::derive`]).
    pub fn derive(content: &[u8], len: u64) -> Key {
        Digest::derive(content, len).into()
    }

    /// The digest the key carries.
    pub const fn digest(&self) -> &Digest {
        &self.0
    }

    /// The key's algorithm.
    pub const fn algorithm(&self) -> Algorithm {
        self.0.algorithm()
    }

    /// The physical encoding: `1 algorithm byte + digest bytes` —
    /// total 33 (`0x01`/`0x04`) or 21 (`0x02`/`0x03`).
    pub fn as_bytes(&self) -> Vec<u8> {
        self.key_bytes().as_slice().to_vec()
    }

    /// The borrowed form of the physical encoding — the same bytes
    /// [`Key::as_bytes`] produces, built into a fixed-capacity
    /// [`KeyBytes`] on the caller's stack instead of the heap. The
    /// borrowed overload for the serving paths that re-encode per
    /// object lookup: a `&KeyBytes` deref-coerces to `&[u8]`, so the
    /// `as_bytes`-shaped borrow temporary (`&key.as_bytes()`) becomes
    /// `&key.key_bytes()` with nothing else moved.
    pub fn key_bytes(&self) -> KeyBytes {
        let digest = self.0.bytes();
        debug_assert!(
            digest.len() < KEY_BYTES_CAP,
            "digest length exceeds the fixed key-bytes capacity"
        );
        let mut bytes = [0u8; KEY_BYTES_CAP];
        let len = 1 + digest.len();
        bytes[0] = self.0.algorithm().byte();
        bytes[1..len].copy_from_slice(digest);
        KeyBytes {
            bytes,
            len: len as u8,
        }
    }

    /// The backend-boundary decode. The exact inverse of
    /// [`Key::as_bytes`]: anything else — empty input, truncated
    /// keys, short/long digests for the algorithm, unknown algorithm
    /// bytes (`0x00`… reserved, `0x05`, `0xff`, …) — is
    /// [`Error::KeyInvalid`]. Rejects, never guesses.
    pub fn from_bytes(bytes: &[u8]) -> Result<Key, Error> {
        let (&tag, digest_bytes) = bytes.split_first().ok_or(Error::KeyInvalid)?;
        let algorithm = Algorithm::try_from_byte(tag).ok_or(Error::KeyInvalid)?;
        if digest_bytes.len() != algorithm.digest_len() {
            return Err(Error::KeyInvalid);
        }
        Ok(Key(Digest::from_parts(algorithm, digest_bytes.to_vec())))
    }
}

/// The borrowed physical encoding of a [`Key`]: fixed-capacity key
/// bytes on the stack (`[u8; 33]` — tag + digest at the widest),
/// deref-coercing to `&[u8]`, `Copy` so borrow temporaries cost
/// nothing. Not a conversion across the backend boundary —
/// [`Key::as_bytes`]/[`Key::key_bytes`] mint it, the written prefix
/// is byte-identical to the allocated form.
///
/// Ordering is the keys' total order (registry byte first, then
/// digest bytes — comparing the written prefix gives exactly that,
/// the tag deciding first at every unequal pair since tag order is
/// the registry order): equal to [`Key`]'s derived ordering.
#[derive(Clone, Copy, Debug)]
pub struct KeyBytes {
    bytes: [u8; KEY_BYTES_CAP],
    len: u8,
}

impl KeyBytes {
    /// The written prefix — the physical encoding, tag first.
    pub fn as_slice(&self) -> &[u8] {
        &self.bytes[..self.len as usize]
    }
}

impl Deref for KeyBytes {
    type Target = [u8];

    fn deref(&self) -> &[u8] {
        self.as_slice()
    }
}

impl PartialEq for KeyBytes {
    fn eq(&self, other: &Self) -> bool {
        self.as_slice() == other.as_slice()
    }
}

impl Eq for KeyBytes {}

impl Hash for KeyBytes {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.as_slice().hash(state)
    }
}

impl PartialOrd for KeyBytes {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for KeyBytes {
    fn cmp(&self, other: &Self) -> Ordering {
        self.as_slice().cmp(other.as_slice())
    }
}

impl From<Digest> for Key {
    fn from(digest: Digest) -> Key {
        Key(digest)
    }
}

impl From<Key> for Digest {
    fn from(key: Key) -> Digest {
        key.0
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hashing::Algorithm as A;
    use std::collections::BTreeSet;

    /// Encoding byte-exactness (ADR-002 §Key encoding): 33/21 total
    /// lengths, 0x01/0x02 tags, digest bytes following untouched.
    #[test]
    fn encoding_is_byte_exact() {
        let content = b"hello";
        let sha256 = Digest::derive(content, content.len() as u64);
        let sha1 = A::GitBlobSha1.derive(content, content.len() as u64);

        let k256: Key = sha256.clone().into();
        let k1: Key = sha1.clone().into();

        let b256 = k256.as_bytes();
        assert_eq!(b256.len(), 33);
        assert_eq!(b256[0], 0x01);
        assert_eq!(&b256[1..], sha256.bytes());

        let b1 = k1.as_bytes();
        assert_eq!(b1.len(), 21);
        assert_eq!(b1[0], 0x02);
        assert_eq!(&b1[1..], sha1.bytes());
    }

    /// Round-trip: `from_bytes` inverts `as_bytes` exactly.
    #[test]
    fn as_bytes_from_bytes_round_trip() {
        let content = b"round trip";
        for algorithm in [
            Algorithm::GitBlobSha256,
            Algorithm::GitBlobSha1,
            Algorithm::GitObjectSha1,
            Algorithm::GitObjectSha256,
        ] {
            let key: Key = algorithm.derive(content, content.len() as u64).into();
            assert_eq!(Key::from_bytes(&key.as_bytes()), Ok(key));
        }
    }

    /// The borrowed overload (`key_bytes`): byte-identical to the
    /// allocated form, fixed-capacity and `Copy` (no heap), and the
    /// encoding's round-trip invariant holds across the deref to
    /// `&[u8]` (`from_bytes` inverts `key_bytes`).
    #[test]
    fn key_bytes_borrowed_overload_round_trips() {
        let content = b"borrowed overload";
        for algorithm in [
            Algorithm::GitBlobSha256,
            Algorithm::GitBlobSha1,
            Algorithm::GitObjectSha1,
            Algorithm::GitObjectSha256,
        ] {
            let key: Key = algorithm.derive(content, content.len() as u64).into();
            let borrowed = key.key_bytes();
            assert_eq!(borrowed.as_slice(), key.as_bytes(), "byte-identical");
            assert_eq!(borrowed.len(), key.as_bytes().len(), "written prefix");
            assert_eq!(Key::from_bytes(&borrowed), Ok(key), "deref round-trip");
        }
    }

    /// The borrowed form's ordering agrees with the typed keys' total
    /// order (the slice view's tag-first compare vs [`Key`]'s derived
    /// registry-then-digest order).
    #[test]
    fn key_bytes_ordering_matches_the_typed_order() {
        let contents: &[&[u8]] = &[b"a", b"bb", b"ccc", b"dddd"];
        let keys: Vec<Key> = contents
            .iter()
            .flat_map(|c| {
                [
                    Key::from(Digest::derive(c, c.len() as u64)),
                    Key::from(Algorithm::GitBlobSha1.derive(c, c.len() as u64)),
                    Key::from(Algorithm::GitObjectSha1.derive(c, c.len() as u64)),
                    Key::from(Algorithm::GitObjectSha256.derive(c, c.len() as u64)),
                ]
            })
            .collect();

        let typed_sorted: Vec<Key> = {
            let mut sorted = keys.clone();
            sorted.sort();
            sorted
        };
        let borrowed_sorted: Vec<KeyBytes> = {
            let mut borrowed: Vec<KeyBytes> = keys.iter().map(|k| k.key_bytes()).collect();
            borrowed.sort();
            borrowed
        };

        let expected: Vec<KeyBytes> = typed_sorted.iter().map(|k| k.key_bytes()).collect();
        assert_eq!(borrowed_sorted, expected, "borrowed order == typed order");
    }

    /// Rejects, never guesses (POC finding 5): empty, truncated,
    /// over-long, unknown algorithm bytes (incl. reserved 0x00, 0x05,
    /// 0xFF — 0x03/0x04 are the ADR-018 family, not unknowns), and
    /// tag/digest-length mismatches are all
    /// [`Error::KeyInvalid`].
    #[test]
    fn malformed_keys_are_rejected() {
        let key: Key = Digest::derive(b"rejects", 7).into();

        assert_eq!(Key::from_bytes(&[]), Err(Error::KeyInvalid), "empty");
        assert_eq!(
            Key::from_bytes(&key.as_bytes()[..key.as_bytes().len() - 1]),
            Err(Error::KeyInvalid),
            "truncated"
        );
        assert_eq!(
            Key::from_bytes(&key.as_bytes()[..32]),
            Err(Error::KeyInvalid),
            "digest truncated"
        );
        assert_eq!(
            Key::from_bytes(&[&key.as_bytes()[..], &[0u8][..]].concat()),
            Err(Error::KeyInvalid),
            "over-long"
        );
        assert_eq!(Key::from_bytes(&[0x00]), Err(Error::KeyInvalid), "reserved");
        assert_eq!(
            Key::from_bytes(&[0x00; 33]),
            Err(Error::KeyInvalid),
            "reserved full-width"
        );
        assert_eq!(
            Key::from_bytes(&[0x05; 33]),
            Err(Error::KeyInvalid),
            "unknown (0x03/0x04 are the ADR-018 git-object family)"
        );
        assert_eq!(
            Key::from_bytes(&[0xFF; 33]),
            Err(Error::KeyInvalid),
            "unknown top"
        );
        assert_eq!(Key::from_bytes(&[0xFF; 21]), Err(Error::KeyInvalid));
        // The family's tags decode, but validation stays per-member
        // exact: the sha-1 member's total width is 21 and the sha-256
        // member's is 33 — tag/digest-width mismatches are rejects
        // (the rejects-never-guesses posture holds per member).
        assert_eq!(
            Key::from_bytes(&[0x03]),
            Err(Error::KeyInvalid),
            "git-object tag alone is truncated"
        );
        assert_eq!(
            Key::from_bytes(&[0x03; 33]),
            Err(Error::KeyInvalid),
            "git-object sha-1 tag with sha-256-width digest"
        );
        assert_eq!(
            Key::from_bytes(&[0x04; 21]),
            Err(Error::KeyInvalid),
            "git-object sha-256 tag with sha-1-width digest"
        );
    }

    /// The ADR-018 git-object keys round-trip through the physical
    /// encoding, order after the blob family, and decode to their own
    /// algorithms (the keys.rs doc's extended layout).
    #[test]
    fn git_object_keys_round_trip_in_total_order() {
        let sha1_key: Key = Algorithm::GitObjectSha1.derive(b"tree 0\0", 7).into();
        let sha256_key: Key = Algorithm::GitObjectSha256.derive(b"tree 0\0", 7).into();

        let b1 = sha1_key.as_bytes();
        assert_eq!(b1.len(), 21);
        assert_eq!(b1[0], 0x03);
        assert_eq!(Key::from_bytes(&b1), Ok(sha1_key.clone()));

        let b256 = sha256_key.as_bytes();
        assert_eq!(b256.len(), 33);
        assert_eq!(b256[0], 0x04);
        assert_eq!(Key::from_bytes(&b256), Ok(sha256_key.clone()));

        assert!(
            sha1_key < sha256_key,
            "the extended family keeps the total order"
        );
    }

    /// Total-order sort stability (ADR-002 / hashing-and-keys.md
    /// §Key encoding): a mixed-algorithm flat collection sorts
    /// deterministically, and the derived order equals the physical
    /// byte order.
    #[test]
    fn mixed_algorithms_sort_in_total_order() {
        let contents: &[&[u8]] = &[b"a", b"bb", b"ccc", b"dddd"];
        let mut keys: Vec<Key> = contents
            .iter()
            .flat_map(|c| {
                [
                    Key::from(Digest::derive(c, c.len() as u64)),
                    Key::from(Algorithm::GitBlobSha1.derive(c, c.len() as u64)),
                    Key::from(Algorithm::GitObjectSha1.derive(c, c.len() as u64)),
                    Key::from(Algorithm::GitObjectSha256.derive(c, c.len() as u64)),
                ]
            })
            .collect();
        keys.push(Key::from(Algorithm::GitBlobSha1.derive(b"b", 1)));
        keys.sort();

        let encoded: Vec<Vec<u8>> = keys.iter().map(|k| k.as_bytes()).collect();
        let mut sorted_encoded = encoded.clone();
        sorted_encoded.sort();

        assert_eq!(encoded, sorted_encoded, "derived order == byte order");

        let mut set = BTreeSet::new();
        for key in &keys {
            set.insert(key.as_bytes());
        }
        assert_eq!(set.len(), keys.len(), "all keys addressable, none collide");
    }

    /// Tagged-key coexistence (POC finding 5, the simplification's
    /// evidence): both algorithms' keys are disjoint in one flat
    /// collection with zero mapping.
    #[test]
    fn both_algorithms_coexist_in_one_collection() {
        let content = b"coexist";
        let mut set = BTreeSet::new();
        set.insert(Key::from(Digest::derive(content, content.len() as u64)));
        set.insert(Key::from(
            Algorithm::GitBlobSha1.derive(content, content.len() as u64),
        ));
        assert_eq!(set.len(), 2);
    }
}