didbot_data/dag_cbor/

mod.rs

//! The DAG-CBOR encoding, which is the canonical form a record is hashed in.
//!
//! CBOR by itself has many encodings of the same value: an integer can be
//! written in five widths, an array can be indefinite-length, a map can be in
//! any order. DAG-CBOR is the profile that removes all of that, and a record's
//! identity is the sha-256 of these bytes, so "several encodings" would mean
//! "several identities for one record".
//!
//! The rules, all of which are enforced here rather than left to a caller:
//!
//! * **Shortest-form counts.** A length or an integer is written in the
//!   smallest of the five widths that holds it. 23 is one byte, never two.
//! * **Definite lengths only.** Every string, list and map declares its length
//!   up front. The indefinite-length forms are not emitted.
//! * **Map keys are sorted length-first**, then bytewise within a length. This
//!   is the ordering the atproto fixtures use and it is *not* the ordering a
//!   `BTreeMap<String, _>` iterates in — `integer` sorts before `unicode`
//!   either way, but `bool` sorts before `array` only under this rule. Sorting
//!   is done here, at the encoder, so that no caller can hold a map in the
//!   wrong order to begin with.
//! * **No floats.** [`Value`] has no float variant; see its documentation.
//! * **Links are tag 42**, carrying a byte string that is a zero byte — the
//!   identity multibase prefix — followed by the CID's binary form.
//!
//! Encoding cannot fail. Everything that could go wrong went wrong earlier, in
//! [`Value::from_json`], and a [`Value`] that exists has an encoding by
//! construction.
//!
//! # The other direction
//!
//! [`decode`] reads a block back, and it is the harder half: an encoder has
//! to emit the canonical form, while a decoder has to refuse every other one.
//! It exists because a Merkle search tree that arrived from somewhere else —
//! in a CAR file, in a firehose frame — is a pile of blocks, and reading it
//! means reading them. See [`decode`] for what it refuses and why each
//! refusal matters.

mod read;

pub use read::{decode, CborError, MAX_DEPTH};

use crate::cid::Cid;
use crate::value::Value;

/// CBOR major type 0: a non-negative integer.
const MAJOR_UNSIGNED: u8 = 0;
/// CBOR major type 1: a negative integer, stored as `-1 - n`.
const MAJOR_NEGATIVE: u8 = 1;
/// CBOR major type 2: a byte string.
const MAJOR_BYTES: u8 = 2;
/// CBOR major type 3: a UTF-8 string.
const MAJOR_TEXT: u8 = 3;
/// CBOR major type 4: a list.
const MAJOR_LIST: u8 = 4;
/// CBOR major type 5: a map.
const MAJOR_MAP: u8 = 5;
/// CBOR major type 6: a tag.
const MAJOR_TAG: u8 = 6;
/// CBOR major type 7: the simple values, of which DAG-CBOR uses three.
const MAJOR_SIMPLE: u8 = 7;

/// The tag that marks a link. 42 is the IPLD CID tag, and it is the only tag
/// DAG-CBOR permits.
const TAG_LINK: u64 = 42;

/// The multibase prefix inside a link's byte string: identity, meaning the
/// bytes are the CID itself and not a text encoding of it.
const IDENTITY_MULTIBASE: u8 = 0x00;

/// Encodes a value into its one DAG-CBOR form.
///
/// ```
/// use didbot_data::{dag_cbor, Value};
/// let value = Value::from_json(&serde_json::json!({})).unwrap();
/// assert_eq!(dag_cbor::encode(&value), vec![0xa0]);
/// ```
pub fn encode(value: &Value) -> Vec<u8> {
    let mut out = Vec::new();
    write(value, &mut out);
    out
}

/// Encodes a value and returns the CID naming that block.
///
/// This is the pairing the rest of atproto is built on, and keeping it in one
/// function is deliberate: a CID over anything but the canonical encoding is
/// a number that looks like an identity and is not one.
pub fn cid(value: &Value) -> Cid {
    Cid::of_dag_cbor(&encode(value))
}

/// Writes one value.
fn write(value: &Value, out: &mut Vec<u8>) {
    match value {
        Value::Null => out.push(header_byte(MAJOR_SIMPLE, 22)),
        Value::Bool(false) => out.push(header_byte(MAJOR_SIMPLE, 20)),
        Value::Bool(true) => out.push(header_byte(MAJOR_SIMPLE, 21)),
        Value::Integer(number) if *number >= 0 => {
            header(MAJOR_UNSIGNED, *number as u64, out);
        }
        // A negative integer is stored as its magnitude minus one, so that
        // -1 costs one byte rather than the eight a sign bit would.
        Value::Integer(number) => header(MAJOR_NEGATIVE, (-1 - *number) as u64, out),
        Value::String(text) => {
            header(MAJOR_TEXT, text.len() as u64, out);
            out.extend_from_slice(text.as_bytes());
        }
        Value::Bytes(bytes) => {
            header(MAJOR_BYTES, bytes.len() as u64, out);
            out.extend_from_slice(bytes);
        }
        Value::Link(cid) => {
            header(MAJOR_TAG, TAG_LINK, out);
            header(MAJOR_BYTES, cid.as_bytes().len() as u64 + 1, out);
            out.push(IDENTITY_MULTIBASE);
            out.extend_from_slice(cid.as_bytes());
        }
        Value::List(items) => {
            header(MAJOR_LIST, items.len() as u64, out);
            for item in items {
                write(item, out);
            }
        }
        Value::Map(entries) => {
            header(MAJOR_MAP, entries.len() as u64, out);
            let mut keys: Vec<&String> = entries.keys().collect();
            keys.sort_unstable_by(|left, right| key_order(left, right));
            for key in keys {
                header(MAJOR_TEXT, key.len() as u64, out);
                out.extend_from_slice(key.as_bytes());
                write(&entries[key], out);
            }
        }
    }
}

/// The DAG-CBOR map key ordering: shorter keys first, then bytewise.
///
/// Plain bytewise ordering — what `BTreeMap<String, _>` gives — is a
/// different order and a different set of bytes, and a suite that compared an
/// encoder against itself would never notice.
fn key_order(left: &str, right: &str) -> std::cmp::Ordering {
    left.len()
        .cmp(&right.len())
        .then_with(|| left.as_bytes().cmp(right.as_bytes()))
}

/// A major type and a small argument in one byte.
fn header_byte(major: u8, argument: u8) -> u8 {
    (major << 5) | argument
}

/// Writes a major type and its argument in the shortest form that holds it.
///
/// The five widths are the whole of CBOR's ambiguity about numbers: 23 can be
/// written inline, or in one, two, four or eight following bytes, and all five
/// decode to 23. Only the first is DAG-CBOR.
fn header(major: u8, argument: u64, out: &mut Vec<u8>) {
    if argument < 24 {
        out.push(header_byte(major, argument as u8));
    } else if let Ok(byte) = u8::try_from(argument) {
        out.push(header_byte(major, 24));
        out.push(byte);
    } else if let Ok(short) = u16::try_from(argument) {
        out.push(header_byte(major, 25));
        out.extend_from_slice(&short.to_be_bytes());
    } else if let Ok(word) = u32::try_from(argument) {
        out.push(header_byte(major, 26));
        out.extend_from_slice(&word.to_be_bytes());
    } else {
        out.push(header_byte(major, 27));
        out.extend_from_slice(&argument.to_be_bytes());
    }
}

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

    fn encode_json(json: serde_json::Value) -> Vec<u8> {
        encode(&Value::object_from_json(&json).expect("a valid data-model object"))
    }

    #[test]
    fn integers_are_written_in_the_shortest_width_that_holds_them() {
        let cases: [(i64, &[u8]); 8] = [
            (0, &[0x00]),
            (23, &[0x17]),
            (24, &[0x18, 0x18]),
            (255, &[0x18, 0xff]),
            (256, &[0x19, 0x01, 0x00]),
            (65536, &[0x1a, 0x00, 0x01, 0x00, 0x00]),
            (-1, &[0x20]),
            (-500, &[0x39, 0x01, 0xf3]),
        ];
        for (number, expected) in cases {
            assert_eq!(encode(&Value::Integer(number)), expected, "{number}");
        }
    }

    #[test]
    fn the_widest_integers_still_round_trip() {
        assert_eq!(
            encode(&Value::Integer(i64::MAX)),
            [0x1b, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]
        );
        assert_eq!(
            encode(&Value::Integer(i64::MIN)),
            [0x3b, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]
        );
    }

    #[test]
    fn map_keys_are_sorted_by_length_before_they_are_sorted_by_bytes() {
        // `b` sorts after `aa` bytewise and before it here. This is the rule
        // most easily got wrong, because a BTreeMap looks like it has already
        // done the sorting.
        let bytes = encode_json(json!({"aa": 1, "b": 2}));
        assert_eq!(bytes, [0xa2, 0x61, b'b', 0x02, 0x62, b'a', b'a', 0x01]);
    }

    #[test]
    fn simple_values_are_the_three_the_profile_allows() {
        assert_eq!(encode(&Value::Null), [0xf6]);
        assert_eq!(encode(&Value::Bool(false)), [0xf4]);
        assert_eq!(encode(&Value::Bool(true)), [0xf5]);
    }

    #[test]
    fn a_text_length_is_bytes_and_not_characters() {
        // A length counted in characters would leave the far side reading a
        // truncated string and then everything after it as garbage.
        let text = "a~öñ©⽘";
        assert_ne!(text.len(), text.chars().count());
        let bytes = encode(&Value::String(text.to_owned()));
        assert_eq!(bytes[0], header_byte(MAJOR_TEXT, text.len() as u8));
        assert_eq!(bytes.len(), text.len() + 1);
    }

    #[test]
    fn a_link_is_tag_42_over_an_identity_prefixed_cid() {
        let cid =
            Cid::parse("bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a").unwrap();
        let bytes = encode(&Value::Link(cid.clone()));
        assert_eq!(&bytes[..4], &[0xd8, 0x2a, 0x58, 0x25]);
        assert_eq!(bytes[4], 0x00);
        assert_eq!(&bytes[5..], cid.as_bytes());
    }

    #[test]
    fn an_empty_list_and_an_empty_map_are_one_byte_each() {
        assert_eq!(encode(&Value::List(Vec::new())), [0x80]);
        assert_eq!(encode_json(json!({})), [0xa0]);
    }
}