didbot_data/dag_cbor/

read.rs

//! Reading a block back, which is a stricter job than writing one.
//!
//! An encoder has to produce the one canonical form. A decoder has to *refuse*
//! every other form, and that asymmetry is the whole of this file. Plain CBOR
//! has five widths for the same integer, two lengths forms for every string,
//! any order for a map's keys and a tag space of thousands; all of it decodes
//! to something. A decoder that accepted the lot would hand back values whose
//! re-encoding is a different block with a different CID — which is to say it
//! would let a peer hand this server two spellings of one record and get two
//! identities for it.
//!
//! So the rule here is: a block that does not re-encode to itself is not a
//! block. Every non-canonical form is an error rather than a value, and
//! [`decode`]'s own tests assert the round trip rather than trusting the
//! reading.
//!
//! What this refuses that CBOR allows, in the order a parser meets it:
//!
//! * an argument written wider than it needs — `0x18 0x05` for 5;
//! * an indefinite length, on a string, a list or a map;
//! * a float, a half float included, and the `undefined` simple value;
//! * a simple value below 32 written in the one-byte form — `f8 14` is a
//!   second spelling of `f4`, and a decoder that read it would re-encode the
//!   block to a different CID;
//! * a tag other than 42, and a tag 42 over anything but an
//!   identity-prefixed CID;
//! * a map key that is not a text string, and a map whose keys are not in
//!   ascending DAG-CBOR order — which also rules out a duplicate key;
//! * a CID this crate cannot re-encode: see [`Cid::from_bytes`].
//!
//! Nesting is bounded by [`MAX_DEPTH`]. A block arrives from a peer, and a
//! recursive descent parser over a few kilobytes of nested arrays is a stack
//! overflow — which aborts the process rather than unwinding, so it cannot be
//! caught anywhere upstream.

use std::collections::BTreeMap;

use super::{
    key_order, IDENTITY_MULTIBASE, MAJOR_BYTES, MAJOR_LIST, MAJOR_MAP, MAJOR_NEGATIVE,
    MAJOR_SIMPLE, MAJOR_TAG, MAJOR_TEXT, MAJOR_UNSIGNED, TAG_LINK,
};
use crate::cid::{Cid, CidError};
use crate::value::Value;

/// How deep a value may nest before it is refused.
///
/// Records nest a handful of levels — an embed inside a post, images inside
/// the embed — and a Merkle search tree node nests two. A hundred is far past
/// anything the protocol produces and far below the depth that would trouble
/// the stack.
pub const MAX_DEPTH: usize = 100;

/// Why a block is not a value in this data model.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum CborError {
    /// The block ended in the middle of a value.
    #[error("the block ends inside a value: {0} more bytes were needed")]
    Truncated(usize),
    /// A value was complete and bytes followed it. A block is one value.
    #[error("{0} bytes follow the end of the value")]
    Trailing(usize),
    /// An argument written in a wider form than the shortest that holds it.
    #[error("{argument} is written in a {width}-byte form, which is not the shortest")]
    NonCanonicalArgument {
        /// The number that was written.
        argument: u64,
        /// How many bytes it was written in.
        width: usize,
    },
    /// One of the indefinite-length forms, which DAG-CBOR does not have.
    #[error("indefinite lengths are not part of dag-cbor")]
    IndefiniteLength,
    /// A reserved additional-information value: 28, 29 or 30.
    #[error("additional information {0} is reserved")]
    ReservedArgument(u8),
    /// A float, of any width. The data model has no float; see [`Value`].
    #[error("the data model has no floats")]
    Float,
    /// A simple value other than `false`, `true` and `null`.
    #[error("simple value {0} is not one of false, true and null")]
    Simple(u8),
    /// An integer past what an `i64` holds, which the data model's one number
    /// type cannot carry.
    #[error("{0} is outside the integers the data model holds")]
    IntegerRange(u64),
    /// A text string, or a map key, that is not UTF-8.
    #[error("a text string is not valid utf-8")]
    NotUtf8,
    /// A tag other than 42.
    #[error("tag {0} is not the link tag, which is the only tag dag-cbor has")]
    Tag(u64),
    /// Tag 42 over something that is not a byte string.
    #[error("a link tag must carry a byte string")]
    LinkNotBytes,
    /// A link's byte string without the identity multibase prefix.
    #[error("a link's bytes must begin with the identity multibase prefix")]
    LinkPrefix,
    /// A link whose bytes are not a CID this crate can re-encode.
    #[error("a link is not a usable cid: {0}")]
    Link(#[from] CidError),
    /// A map key that is not a text string.
    #[error("a map key must be a text string")]
    KeyNotText,
    /// Map keys out of order, which includes a repeated key.
    #[error("map key {found:?} does not sort after {previous:?}")]
    KeyOrder {
        /// The key that was read.
        found: String,
        /// The key before it.
        previous: String,
    },
    /// More nesting than [`MAX_DEPTH`].
    #[error("the value nests deeper than {MAX_DEPTH} levels")]
    TooDeep,
}

/// Decodes one block into the data model.
///
/// The block is one value and nothing after it, which is what a
/// content-addressed block is: bytes that hash to a name. Trailing bytes are
/// an error rather than an ignored tail, because they change the hash while
/// leaving the value alone.
///
/// ```
/// use didbot_data::{dag_cbor, Value};
///
/// let value = Value::from_json(&serde_json::json!({"a": 1})).unwrap();
/// let block = dag_cbor::encode(&value);
/// assert_eq!(dag_cbor::decode(&block).unwrap(), value);
///
/// // 5 written in two bytes rather than one is not a block.
/// assert!(dag_cbor::decode(&[0x18, 0x05]).is_err());
/// ```
pub fn decode(block: &[u8]) -> Result<Value, CborError> {
    let mut reader = Reader { rest: block };
    let value = reader.value(0)?;
    if !reader.rest.is_empty() {
        return Err(CborError::Trailing(reader.rest.len()));
    }
    Ok(value)
}

/// A cursor over the block being read.
struct Reader<'a> {
    /// What has not been read yet.
    rest: &'a [u8],
}

/// A major type and the argument that followed it.
struct Header {
    /// The major type, 0 to 7.
    major: u8,
    /// The argument, whatever width it was written in.
    argument: u64,
    /// How many bytes the argument was written in, 0 for the inline form.
    ///
    /// Kept because major type 7 reads it as a *kind* rather than a width:
    /// two, four and eight bytes are a half, single and double float, and one
    /// byte is a simple value in the extended range.
    width: usize,
}

impl<'a> Reader<'a> {
    /// Takes `count` bytes, or says how many were missing.
    fn take(&mut self, count: usize) -> Result<&'a [u8], CborError> {
        if self.rest.len() < count {
            return Err(CborError::Truncated(count - self.rest.len()));
        }
        let (taken, rest) = self.rest.split_at(count);
        self.rest = rest;
        Ok(taken)
    }

    /// Reads a header, refusing every non-shortest and indefinite form.
    fn header(&mut self) -> Result<Header, CborError> {
        let initial = self.take(1)?[0];
        let major = initial >> 5;
        let information = initial & 0x1f;
        let (argument, width) = match information {
            0..=23 => (u64::from(information), 0),
            24 => (u64::from(self.take(1)?[0]), 1),
            25 => {
                let bytes: [u8; 2] = self.take(2)?.try_into().unwrap_or_default();
                (u64::from(u16::from_be_bytes(bytes)), 2)
            }
            26 => {
                let bytes: [u8; 4] = self.take(4)?.try_into().unwrap_or_default();
                (u64::from(u32::from_be_bytes(bytes)), 4)
            }
            27 => {
                let bytes: [u8; 8] = self.take(8)?.try_into().unwrap_or_default();
                (u64::from_be_bytes(bytes), 8)
            }
            31 => return Err(CborError::IndefiniteLength),
            reserved => return Err(CborError::ReservedArgument(reserved)),
        };
        // A float is a major type 7 argument and is caught below, where the
        // simple values are read: the widths overlap, and 25, 26 and 27 mean
        // "half, single, double" there rather than "a wider integer".
        //
        // Major type 7's one-byte form is not a width either, and it has its
        // own shortest rule: it carries a simple value in the extended range,
        // 32 to 255, and a value below 32 written in it is a second spelling
        // of a byte that already exists. `f8 14` and `f4` would both be
        // `false`, and only one of them is the block that value hashes as.
        let non_canonical = if major == MAJOR_SIMPLE {
            width == 1 && argument < 32
        } else {
            !shortest(argument, width)
        };
        if non_canonical {
            return Err(CborError::NonCanonicalArgument { argument, width });
        }
        Ok(Header {
            major,
            argument,
            width,
        })
    }

    /// Reads one value at `depth`.
    fn value(&mut self, depth: usize) -> Result<Value, CborError> {
        if depth > MAX_DEPTH {
            return Err(CborError::TooDeep);
        }
        let header = self.header()?;
        match header.major {
            MAJOR_UNSIGNED => Ok(Value::Integer(integer(header.argument)?)),
            // A negative integer is stored as -1 - n, so the representable
            // magnitude is one larger than the positive side. `-1 - n` on the
            // i64 the argument fits is exactly that.
            MAJOR_NEGATIVE => Ok(Value::Integer(-1 - integer(header.argument)?)),
            MAJOR_BYTES => self
                .bytes(header.argument)
                .map(<[u8]>::to_vec)
                .map(Value::Bytes),
            MAJOR_TEXT => self.text(header.argument).map(Value::String),
            MAJOR_LIST => self.list(header.argument, depth),
            MAJOR_MAP => self.map(header.argument, depth),
            MAJOR_TAG => self.link(header.argument, depth),
            // 7 by elimination: three bits hold nothing else. The wider
            // forms are the floats; the inline and one-byte forms are simple
            // values.
            _ if header.width >= 2 => Err(CborError::Float),
            _ => simple(header.argument),
        }
    }

    /// Reads a byte string's contents.
    fn bytes(&mut self, length: u64) -> Result<&'a [u8], CborError> {
        let length = usize::try_from(length).map_err(|_| CborError::Truncated(0))?;
        self.take(length)
    }

    /// Reads a text string's contents, which must be UTF-8.
    fn text(&mut self, length: u64) -> Result<String, CborError> {
        let bytes = self.bytes(length)?;
        std::str::from_utf8(bytes)
            .map(str::to_owned)
            .map_err(|_| CborError::NotUtf8)
    }

    /// Reads a list's items.
    fn list(&mut self, count: u64, depth: usize) -> Result<Value, CborError> {
        let mut items = Vec::new();
        for _ in 0..count {
            // The count is a claim by the block and is not trusted as a
            // capacity: a two-byte block can claim four billion items.
            items.push(self.value(depth + 1)?);
        }
        Ok(Value::List(items))
    }

    /// Reads a map's entries, which must be text-keyed and in order.
    ///
    /// The ordering check is what makes decoding the inverse of encoding: a
    /// `BTreeMap` would happily hold keys read in any order and re-encode
    /// them sorted, so the block that arrived and the block that leaves would
    /// differ while every value in them matched.
    fn map(&mut self, count: u64, depth: usize) -> Result<Value, CborError> {
        let mut entries = BTreeMap::new();
        let mut previous: Option<String> = None;
        for _ in 0..count {
            let header = self.header()?;
            if header.major != MAJOR_TEXT {
                return Err(CborError::KeyNotText);
            }
            let key = self.text(header.argument)?;
            if let Some(previous) = &previous {
                if key_order(previous, &key) != std::cmp::Ordering::Less {
                    return Err(CborError::KeyOrder {
                        found: key,
                        previous: previous.clone(),
                    });
                }
            }
            let value = self.value(depth + 1)?;
            previous = Some(key.clone());
            entries.insert(key, value);
        }
        Ok(Value::Map(entries))
    }

    /// Reads a tagged value, which in DAG-CBOR is a link and nothing else.
    fn link(&mut self, tag: u64, depth: usize) -> Result<Value, CborError> {
        if tag != TAG_LINK {
            return Err(CborError::Tag(tag));
        }
        if depth > MAX_DEPTH {
            return Err(CborError::TooDeep);
        }
        let header = self.header()?;
        if header.major != MAJOR_BYTES {
            return Err(CborError::LinkNotBytes);
        }
        let bytes = self.bytes(header.argument)?;
        match bytes.split_first() {
            Some((&IDENTITY_MULTIBASE, cid)) => Ok(Value::Link(Cid::from_bytes(cid)?)),
            _ => Err(CborError::LinkPrefix),
        }
    }
}

/// Whether an argument is written in the narrowest form that holds it.
fn shortest(argument: u64, width: usize) -> bool {
    match width {
        0 => argument < 24,
        1 => argument >= 24 && u8::try_from(argument).is_ok(),
        2 => argument > u64::from(u8::MAX) && u16::try_from(argument).is_ok(),
        4 => argument > u64::from(u16::MAX) && u32::try_from(argument).is_ok(),
        _ => argument > u64::from(u32::MAX),
    }
}

/// An argument as the data model's one number type.
fn integer(argument: u64) -> Result<i64, CborError> {
    i64::try_from(argument).map_err(|_| CborError::IntegerRange(argument))
}

/// The three simple values the profile has, and the refusal of everything else.
///
/// Only the inline and one-byte forms reach here, so the argument is a simple
/// value and never a float's payload; the floats are refused by width in
/// [`Reader::value`]. 23 is `undefined`, which the data model does not have,
/// and 32 upwards is the unassigned extended range.
fn simple(argument: u64) -> Result<Value, CborError> {
    match argument {
        20 => Ok(Value::Bool(false)),
        21 => Ok(Value::Bool(true)),
        22 => Ok(Value::Null),
        other => Err(CborError::Simple(u8::try_from(other).unwrap_or(u8::MAX))),
    }
}

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

    /// Every value this crate encodes reads back as itself. This is the whole
    /// claim the decoder makes, so it is made over a value with one of
    /// everything in it.
    #[test]
    fn a_block_decodes_to_the_value_it_was_encoded_from() {
        let mut value = Value::object_from_json(&json!({
            "text": "quernstone",
            "count": 23,
            "wide": 65536,
            "negative": -500,
            "flag": true,
            "missing": null,
            "list": [1, 2, {"nested": []}],
            "bytes": {"$bytes": "aGVsbG8"},
            "link": {"$link": "bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a"},
        }))
        .expect("a data-model object");
        // The map key ordering is the encoder's, so a value whose keys are
        // both short and long exercises the length-first rule on the way back.
        if let Value::Map(entries) = &mut value {
            entries.insert("aa".to_owned(), Value::Integer(1));
            entries.insert("b".to_owned(), Value::Integer(2));
        }
        assert_eq!(decode(&encode(&value)).unwrap(), value);
    }

    /// The widths a number can be written in are exactly one per number, and
    /// the other four are errors rather than the same number again.
    #[test]
    fn a_wider_form_of_a_number_is_not_the_number() {
        assert_eq!(decode(&[0x05]).unwrap(), Value::Integer(5));
        for wider in [
            vec![0x18, 0x05],
            vec![0x19, 0x00, 0x05],
            vec![0x1a, 0x00, 0x00, 0x00, 0x05],
            vec![0x1b, 0, 0, 0, 0, 0, 0, 0, 5],
        ] {
            assert!(
                matches!(
                    decode(&wider),
                    Err(CborError::NonCanonicalArgument { argument: 5, .. })
                ),
                "{wider:02x?} decoded"
            );
        }
    }

    /// The boundary of each width is canonical in the narrower form and not
    /// in the wider one, which is where an off-by-one in `shortest` lands.
    #[test]
    fn each_width_holds_exactly_its_own_range() {
        assert_eq!(decode(&[0x17]).unwrap(), Value::Integer(23));
        assert_eq!(decode(&[0x18, 0x18]).unwrap(), Value::Integer(24));
        assert_eq!(decode(&[0x18, 0xff]).unwrap(), Value::Integer(255));
        assert_eq!(decode(&[0x19, 0x01, 0x00]).unwrap(), Value::Integer(256));
        assert!(decode(&[0x19, 0x00, 0xff]).is_err());
        assert!(decode(&[0x1a, 0x00, 0x00, 0xff, 0xff]).is_err());
    }

    /// An indefinite-length string is the form a streaming encoder reaches
    /// for and the form a content-addressed block may never have.
    #[test]
    fn indefinite_lengths_are_refused() {
        // 0x5f: an indefinite-length byte string, then a chunk, then a break.
        assert_eq!(
            decode(&[0x5f, 0x41, 0x61, 0xff]),
            Err(CborError::IndefiniteLength)
        );
    }

    /// `f8` carries a simple value in the extended range, 32 to 255. A value
    /// below 32 written in it is a second spelling of a one-byte form, and
    /// accepting it would mean two blocks — two CIDs — for one value.
    ///
    /// This is the sharpest form of the round-trip rule in this file, so it
    /// is asserted as the round trip: whatever `decode` accepts must
    /// re-encode to the bytes it came from.
    #[test]
    fn a_simple_value_below_the_extended_range_is_not_written_in_two_bytes() {
        for value in 0..32u8 {
            let block = [0xf8, value];
            let Ok(decoded) = decode(&block) else {
                continue;
            };
            assert_eq!(
                encode(&decoded),
                block,
                "f8 {value:02x} decoded to {decoded:?}, which re-encodes to other bytes"
            );
        }
        // The three that used to come back as values, named so the failure
        // says which spelling was accepted rather than only that one was.
        assert_eq!(
            decode(&[0xf8, 20]),
            Err(CborError::NonCanonicalArgument {
                argument: 20,
                width: 1
            })
        );
        assert_eq!(
            decode(&[0xf8, 21]),
            Err(CborError::NonCanonicalArgument {
                argument: 21,
                width: 1
            })
        );
        assert_eq!(
            decode(&[0xf8, 22]),
            Err(CborError::NonCanonicalArgument {
                argument: 22,
                width: 1
            })
        );
        // 32 upwards is the range the form is for; it is unassigned rather
        // than non-canonical, and refused for being a simple value the data
        // model has no room for.
        assert_eq!(decode(&[0xf8, 32]), Err(CborError::Simple(32)));
    }

    /// Floats decode to nothing, at every width.
    #[test]
    fn floats_are_refused_at_every_width() {
        for float in [
            vec![0xf9, 0x3c, 0x00],
            vec![0xfa, 0x3f, 0x80, 0x00, 0x00],
            vec![0xfb, 0x3f, 0xf0, 0, 0, 0, 0, 0, 0],
        ] {
            assert_eq!(decode(&float), Err(CborError::Float), "{float:02x?}");
        }
        assert_eq!(decode(&[0xf7]), Err(CborError::Simple(23)), "undefined");
    }

    /// Map keys arrive sorted or the block is not canonical. `b` before `aa`
    /// is the encoder's order; `aa` before `b` is bytewise order, and a
    /// decoder that accepted it would round-trip to different bytes.
    #[test]
    fn map_keys_must_arrive_in_the_order_the_encoder_writes_them() {
        let sorted = [0xa2, 0x61, b'b', 0x02, 0x62, b'a', b'a', 0x01];
        assert!(decode(&sorted).is_ok());
        let bytewise = [0xa2, 0x62, b'a', b'a', 0x01, 0x61, b'b', 0x02];
        assert!(matches!(decode(&bytewise), Err(CborError::KeyOrder { .. })));
        let repeated = [0xa2, 0x61, b'b', 0x02, 0x61, b'b', 0x01];
        assert!(matches!(decode(&repeated), Err(CborError::KeyOrder { .. })));
    }

    /// A tag that is not 42 is not a link, and a link that is not an
    /// identity-prefixed CID is not a link either.
    #[test]
    fn only_the_link_tag_over_a_cid_decodes() {
        let cid =
            Cid::parse("bafyreidfayvfuwqa7qlnopdjiqrxzs6blmoeu4rujcjtnci5beludirz2a").unwrap();
        let block = encode(&Value::Link(cid.clone()));
        assert_eq!(decode(&block).unwrap(), Value::Link(cid));

        // Tag 41 over the same bytes.
        let mut wrong_tag = block.clone();
        wrong_tag[1] = 41;
        assert_eq!(decode(&wrong_tag), Err(CborError::Tag(41)));

        // Tag 42 over a byte string with no multibase prefix.
        let mut no_prefix = block.clone();
        no_prefix.remove(4);
        no_prefix[3] -= 1;
        assert!(decode(&no_prefix).is_err());

        // Tag 42 over an integer.
        assert_eq!(decode(&[0xd8, 0x2a, 0x01]), Err(CborError::LinkNotBytes));
    }

    /// A block is one value. Bytes after it change the CID and mean the
    /// sender and the receiver disagree about what was hashed.
    #[test]
    fn a_block_is_one_value_and_not_a_stream() {
        assert_eq!(decode(&[0x01, 0x02]), Err(CborError::Trailing(1)));
    }

    /// A truncated block says how much was missing rather than reading past
    /// the end of the buffer.
    #[test]
    fn a_truncated_block_is_an_error_and_not_a_panic() {
        assert_eq!(decode(&[0x43, 0x61]), Err(CborError::Truncated(2)));
        // A byte string claiming the whole address space and holding none.
        // The length is a claim and is checked against the input before any
        // of it is copied out.
        assert!(matches!(
            decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
            Err(CborError::Truncated(_))
        ));
        assert_eq!(decode(&[]), Err(CborError::Truncated(1)));
        // A list that claims four billion items and holds none.
        assert!(matches!(
            decode(&[0x9a, 0xff, 0xff, 0xff, 0xff]),
            Err(CborError::Truncated(_))
        ));
    }

    /// Nesting is bounded, because a recursive descent parser that runs out
    /// of stack aborts the process rather than returning an error.
    #[test]
    fn nesting_is_bounded() {
        let deep: Vec<u8> = std::iter::repeat_n(0x81, MAX_DEPTH + 2)
            .chain(std::iter::once(0x01))
            .collect();
        assert_eq!(decode(&deep), Err(CborError::TooDeep));
        let shallow: Vec<u8> = std::iter::repeat_n(0x81, MAX_DEPTH - 1)
            .chain(std::iter::once(0x01))
            .collect();
        assert!(decode(&shallow).is_ok());
    }

    /// A text string that is not UTF-8 is refused rather than repaired.
    ///
    /// The repair is the danger: `from_utf8_lossy` would substitute a
    /// replacement character, and the value would then re-encode to bytes
    /// longer than the ones that arrived, under a CID that is not the one the
    /// block came in under. A lone surrogate is the case a checker written
    /// against UTF-16 lets through.
    #[test]
    fn a_text_string_that_is_not_utf8_is_refused_rather_than_repaired() {
        // `ed a0 80` is the lone surrogate U+D800 in UTF-8's forbidden range.
        assert_eq!(decode(&[0x63, 0xed, 0xa0, 0x80]), Err(CborError::NotUtf8));
        // A bare continuation byte, which no scanner mistakes for anything.
        assert_eq!(decode(&[0x61, 0x80]), Err(CborError::NotUtf8));
        // The same rule reaches a map key, which is read through the same
        // path and would otherwise name an entry nothing could look up.
        assert_eq!(
            decode(&[0xa1, 0x61, 0x80, 0x01]),
            Err(CborError::NotUtf8),
            "a map key is a text string and is held to the same rule"
        );
    }

    /// An integer past `i64` has nowhere to live in the data model, and is
    /// refused rather than wrapped.
    #[test]
    fn an_integer_past_the_model_is_refused() {
        let huge = [0x1b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
        assert_eq!(decode(&huge), Err(CborError::IntegerRange(u64::MAX)));
        assert_eq!(
            decode(&[0x1b, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]).unwrap(),
            Value::Integer(i64::MAX)
        );
        // -1 - n, so the negative side reaches one further.
        assert_eq!(
            decode(&[0x3b, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]).unwrap(),
            Value::Integer(i64::MIN)
        );
    }
}