didbot_repo/

car.rs

//! CARv1: the file a repository is handed over as.
//!
//! A CAR file is a header and then a pile of blocks, each one prefixed by its
//! own length. It carries no index, no ordering rule and no compression — it
//! is a way of putting content-addressed blocks in a stream and nothing more,
//! and what makes it usable is that every block names itself, so a reader can
//! start from the root the header declares and follow links.
//!
//! # The framing, in full
//!
//! ```text
//! varint(len(header))  header                 header is DAG-CBOR
//! varint(len(cid) + len(block))  cid  block   repeated, in any order
//! ```
//!
//! The varint is unsigned LEB128, the same one multiformats uses everywhere
//! else. The header is `{"roots": [<link>], "version": 1}` — `version` is the
//! CAR format's own version and has nothing to do with the repository version
//! in a commit, which is 3. Two different numbers called version in one file
//! is a genuine trap and the reason this is spelled out here.
//!
//! # Reading one back
//!
//! [`read`] is the other direction, and it arrived with the Merkle search
//! tree conformance suite: the trees those vectors describe are handed over
//! as CAR files, so checking a diff against them means reading one. It hands
//! back the roots the header declares and the blocks as they were framed,
//! and it checks the one thing a CAR file can be checked for from the inside
//! — that every block hashes to the CID it is filed under. Nothing above it
//! has to trust the sender's labelling.
//!
//! What it does not do is walk. A CAR is a bag of blocks in no required
//! order, and which of them matter depends on what the root is — a commit, a
//! tree node, a record — so following links is the caller's job.

use std::collections::BTreeMap;

use didbot_data::dag_cbor::CborError;
use didbot_data::{dag_cbor, Cid, CidError, Value};

/// The CAR container format version this writes. Not a repository version.
const CAR_VERSION: i64 = 1;

/// Writes a CARv1 stream with one root.
///
/// See [`write_roots`] for the general form; this is the shape a repository
/// export takes, where the one root is the signed commit.
///
/// Blocks are written in the order the iterator hands them over. Nothing in
/// the format cares — a reader indexes by CID as it goes — but a caller that
/// wants a byte-identical export from identical state should hand over a
/// stable order, which is what an ordered map gives for free.
///
/// A block whose CID does not name it is not detected here. The writer is
/// handed pairs and trusts them; the check belongs where the pair is made,
/// and every producer in this crate makes it by hashing.
///
/// ```
/// use didbot_data::Cid;
/// use didbot_repo::car;
///
/// let block = b"not a real block".to_vec();
/// let cid = Cid::of_raw(&block);
/// let car = car::write(&cid, [(cid.clone(), block)]);
/// assert!(car.len() > 60);
/// ```
#[must_use]
pub fn write(root: &Cid, blocks: impl IntoIterator<Item = (Cid, Vec<u8>)>) -> Vec<u8> {
    write_roots(std::slice::from_ref(root), blocks)
}

/// Writes a CARv1 stream with however many roots it has, including none.
///
/// A file with no roots is a bag of blocks and says so: it declares nothing to
/// start walking from, because the caller asked for particular blocks by name
/// rather than for a structure. That is what `com.atproto.sync.getBlocks`
/// returns and it is what the reference implementation writes for it, so it is
/// what this writes rather than inventing a root the caller did not ask for.
#[must_use]
pub fn write_roots(roots: &[Cid], blocks: impl IntoIterator<Item = (Cid, Vec<u8>)>) -> Vec<u8> {
    let mut out = Vec::new();
    write_section(&mut out, &header(roots));
    for (cid, block) in blocks {
        let mut section = Vec::with_capacity(cid.as_bytes().len() + block.len());
        section.extend_from_slice(cid.as_bytes());
        section.extend_from_slice(&block);
        write_section(&mut out, &section);
    }
    out
}

/// How many bytes a block of `len` bytes filed under `cid` takes in a CAR
/// file: its length prefix, its CID and the block itself.
///
/// What a caller sizing a file before writing it counts, section by section.
#[must_use]
pub fn section_len(cid: &Cid, len: usize) -> usize {
    let payload = cid.as_bytes().len() + len;
    let mut prefix = Vec::with_capacity(10);
    write_varint(&mut prefix, payload as u64);
    prefix.len() + payload
}

/// Why a byte sequence is not a CAR file this crate can read.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum CarError {
    /// A varint that ran off the end, or one too long to be a `u64`.
    #[error("truncated or oversized varint at byte {0}")]
    BadVarint(usize),
    /// A section that claims more bytes than the file has left.
    #[error("the section at byte {at} claims {claimed} bytes and {left} remain")]
    Truncated {
        /// Where the section's length prefix was.
        at: usize,
        /// How long it said it was.
        claimed: u64,
        /// How much file was left after the prefix.
        left: usize,
    },
    /// The file is empty, so it has not even a header.
    #[error("a car file cannot be empty")]
    Empty,
    /// The header block did not decode as DAG-CBOR.
    #[error("the car header is not dag-cbor: {0}")]
    Header(#[from] CborError),
    /// The header decoded and was not the map a CAR header is.
    #[error("the car header is not a v1 header: {0}")]
    NotAHeader(String),
    /// A block's CID did not parse.
    #[error("the block at byte {at} is filed under something that is not a cid: {err}")]
    BlockCid {
        /// Where the section began.
        at: usize,
        /// Why the CID was refused.
        err: CidError,
    },
    /// A block that does not hash to the CID it is filed under.
    #[error("the block filed under {claimed} at byte {at} hashes to {actual}")]
    Mislabelled {
        /// Where the section began.
        at: usize,
        /// The CID the file claimed.
        claimed: Box<Cid>,
        /// The CID the bytes actually have.
        actual: Box<Cid>,
    },
    /// The same CID filed twice with different bytes, which cannot happen to
    /// a hash and means one of the two is not what it says.
    #[error("{0} appears twice in the file")]
    Duplicate(Box<Cid>),
}

/// A CAR file, read apart.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Car {
    /// The roots the header declares, in the order it declares them.
    ///
    /// A file may declare none, and one that declares several is legal. What
    /// a root *means* is the caller's to know: a repository export roots at a
    /// commit, and the Merkle search tree vectors root at a tree node.
    pub roots: Vec<Cid>,
    /// Every block in the file, by CID.
    ///
    /// Ordered, because a `BTreeMap` keyed by CID is the order
    /// [`write()`] wants to hand them back in, so a file that is read and
    /// rewritten comes out canonically ordered whatever order it arrived in.
    pub blocks: BTreeMap<Cid, Vec<u8>>,
}

/// Reads a CARv1 file.
///
/// Every block is hashed and checked against the CID it is filed under. That
/// is not an optional strictness: a CAR file is a claim that these bytes are
/// those names, and a reader that skips the check turns a corrupted download
/// into a repository that verifies against itself and against nothing else.
/// The cost is one sha-256 per block, which is the same hash the sender paid
/// to name it.
///
/// The version field is checked to be 1. There is no CARv2 support here and
/// the failure for one is a header that says so rather than a parse that
/// wanders into the index.
///
/// ```
/// use didbot_data::Cid;
/// use didbot_repo::car;
///
/// let block = b"not a real block".to_vec();
/// let cid = Cid::of_raw(&block);
/// let bytes = car::write(&cid, [(cid.clone(), block.clone())]);
/// let read = car::read(&bytes).expect("a car this crate wrote");
/// assert_eq!(read.roots, vec![cid.clone()]);
/// assert_eq!(read.blocks[&cid], block);
/// ```
pub fn read(bytes: &[u8]) -> Result<Car, CarError> {
    let mut reader = Reader {
        bytes,
        at: 0,
        section_start: 0,
    };
    let header = reader.section()?.ok_or(CarError::Empty)?;
    let roots = parse_header(&dag_cbor::decode(header)?)?;

    let mut blocks = BTreeMap::new();
    while let Some((at, section)) = reader.section()?.map(|s| (reader.section_start, s)) {
        let (cid, block) = split_block(at, section)?;
        let actual = Cid::of_block_under(cid.codec(), block);
        if actual != cid {
            return Err(CarError::Mislabelled {
                at,
                claimed: Box::new(cid),
                actual: Box::new(actual),
            });
        }
        if blocks.insert(cid.clone(), block.to_vec()).is_some() {
            return Err(CarError::Duplicate(Box::new(cid)));
        }
    }
    Ok(Car { roots, blocks })
}

/// Splits one block section into the CID it is filed under and its bytes.
///
/// The CID is not length-prefixed: it is self-describing, and where it ends
/// is where the block begins. [`Cid::read`] is what knows that.
fn split_block(at: usize, section: &[u8]) -> Result<(Cid, &[u8]), CarError> {
    let mut rest = section;
    let cid = Cid::read(&mut rest).map_err(|err| CarError::BlockCid { at, err })?;
    Ok((cid, rest))
}

/// Reads the roots out of a decoded header, and refuses everything else.
fn parse_header(header: &Value) -> Result<Vec<Cid>, CarError> {
    let refuse = |why: &str| CarError::NotAHeader(why.to_owned());
    let Value::Map(fields) = header else {
        return Err(refuse("it is not a map"));
    };
    match fields.get("version") {
        Some(Value::Integer(CAR_VERSION)) => {}
        Some(Value::Integer(other)) => {
            return Err(CarError::NotAHeader(format!(
                "it declares version {other}, and this reads version 1"
            )))
        }
        _ => return Err(refuse("it declares no version")),
    }
    let Some(Value::List(roots)) = fields.get("roots") else {
        return Err(refuse("it has no roots list"));
    };
    roots
        .iter()
        .map(|root| match root {
            Value::Link(cid) => Ok(cid.clone()),
            _ => Err(refuse("a root is not a link")),
        })
        .collect()
}

/// A cursor over the length-prefixed sections a CAR file is made of.
struct Reader<'a> {
    /// The whole file.
    bytes: &'a [u8],
    /// How far in the cursor is.
    at: usize,
    /// Where the section most recently returned began, for error messages.
    section_start: usize,
}

impl<'a> Reader<'a> {
    /// Reads the next section, or `None` at the end of the file.
    fn section(&mut self) -> Result<Option<&'a [u8]>, CarError> {
        if self.at >= self.bytes.len() {
            return Ok(None);
        }
        self.section_start = self.at;
        let length = self.varint()?;
        let left = self.bytes.len() - self.at;
        let claimed = usize::try_from(length).unwrap_or(usize::MAX);
        if claimed > left {
            return Err(CarError::Truncated {
                at: self.section_start,
                claimed: length,
                left,
            });
        }
        let section = &self.bytes[self.at..self.at + claimed];
        self.at += claimed;
        Ok(Some(section))
    }

    /// Reads an unsigned LEB128 varint, the inverse of [`write_varint`].
    fn varint(&mut self) -> Result<u64, CarError> {
        let mut value: u64 = 0;
        let mut shift = 0;
        loop {
            let byte = *self
                .bytes
                .get(self.at)
                .ok_or(CarError::BadVarint(self.section_start))?;
            self.at += 1;
            // 64 bits is ten seven-bit groups, and the tenth may only carry
            // the one bit that is left. Anything else is a varint that does
            // not fit in what it is being read into.
            if shift > 63 || (shift == 63 && byte > 1) {
                return Err(CarError::BadVarint(self.section_start));
            }
            value |= u64::from(byte & 0x7f) << shift;
            if byte & 0x80 == 0 {
                return Ok(value);
            }
            shift += 7;
        }
    }
}

/// The DAG-CBOR header block: which roots, and which CAR version.
fn header(roots: &[Cid]) -> Vec<u8> {
    dag_cbor::encode(&Value::Map(std::collections::BTreeMap::from([
        (
            "roots".to_owned(),
            Value::List(roots.iter().cloned().map(Value::Link).collect()),
        ),
        ("version".to_owned(), Value::Integer(CAR_VERSION)),
    ])))
}

/// Appends one length-prefixed section.
fn write_section(out: &mut Vec<u8>, payload: &[u8]) {
    write_varint(out, payload.len() as u64);
    out.extend_from_slice(payload);
}

/// Appends an unsigned LEB128 varint.
///
/// The same encoding `didbot_data::Cid` uses inside a CID, written
/// again here rather than shared, because the two are the same shape for
/// unrelated reasons: multiformats chose it for CIDs and CAR chose it for
/// section lengths, and a change to either must not move the other.
fn write_varint(out: &mut Vec<u8>, mut value: u64) {
    while value >= 0x80 {
        out.push((value as u8) | 0x80);
        value >>= 7;
    }
    out.push(value as u8);
}

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

    #[test]
    fn a_varint_is_shortest_form() {
        let mut out = Vec::new();
        write_varint(&mut out, 0);
        assert_eq!(out, vec![0x00]);
        out.clear();
        write_varint(&mut out, 127);
        assert_eq!(out, vec![0x7f]);
        out.clear();
        write_varint(&mut out, 128);
        assert_eq!(out, vec![0x80, 0x01]);
        out.clear();
        write_varint(&mut out, 300);
        assert_eq!(out, vec![0xac, 0x02]);
    }

    /// A section's size, counted before writing, is what writing it adds:
    /// across the one-byte and two-byte length prefixes, and a large block.
    #[test]
    fn a_section_len_is_what_the_section_adds_to_the_file() {
        let root = Cid::of_dag_cbor(b"a commit");
        let empty = write(&root, []).len();
        for len in [0, 1, 91, 92, 5_000, 2_000_000] {
            let block = vec![7u8; len];
            let cid = Cid::of_raw(&block);
            let file = write(&root, [(cid.clone(), block)]);
            assert_eq!(
                file.len() - empty,
                section_len(&cid, len),
                "a {len}-byte block"
            );
        }
    }

    /// The header is the same six-key-free map every CAR file starts with, so
    /// its bytes are fixed except for the root. Asserting the prefix catches a
    /// map that lost its ordering or grew a field.
    #[test]
    fn the_header_declares_one_root_and_version_one() {
        let root = Cid::of_dag_cbor(b"a commit");
        let bytes = header(std::slice::from_ref(&root));
        // {"roots": [...], "version": 1}: a two-key map, "roots" first.
        assert_eq!(&bytes[..7], &[0xa2, 0x65, b'r', b'o', b'o', b't', b's']);
        assert_eq!(&bytes[bytes.len() - 9..], b"\x67version\x01".as_slice());
    }

    #[test]
    fn a_car_with_no_blocks_is_a_header_alone() {
        let root = Cid::of_dag_cbor(b"a commit");
        let bytes = write(&root, []);
        assert_eq!(bytes.len(), header(std::slice::from_ref(&root)).len() + 1);
    }

    /// A rootless header is the same map with an empty list, which is a
    /// different length and therefore a different file. Asserted so that a
    /// change to `write_roots` cannot quietly start naming a root.
    #[test]
    fn a_rootless_car_declares_no_roots() {
        let block = b"a block somebody asked for by name".to_vec();
        let cid = Cid::of_raw(&block);
        let bytes = write_roots(&[], [(cid, block)]);
        // 0x80 is an empty CBOR array, where a one-element one is 0x81.
        assert_eq!(&bytes[1..8], &[0xa2, 0x65, b'r', b'o', b'o', b't', b's']);
        assert_eq!(bytes[8], 0x80);
    }
}