repo_stream/
mst.rs

1//! Low-level types for parsing raw atproto MST CARs
2//!
3//! The primary aim is to work through the **tree** structure. Non-node blocks
4//! are left as raw bytes, for upper levels to parse into DAG-CBOR or whatever.
5
6use ipld_core::cid::Cid;
7use serde::Deserialize;
8
9/// The top-level data object in a repository's tree is a signed commit.
10#[derive(Debug, Deserialize)]
11// #[serde(deny_unknown_fields)]
12pub struct Commit {
13    /// the account DID associated with the repo, in strictly normalized form
14    /// (eg, lowercase as appropriate)
15    pub did: String,
16    /// fixed value of 3 for this repo format version
17    pub version: u64,
18    /// pointer to the top of the repo contents tree structure (MST)
19    pub data: Cid,
20    /// revision of the repo, used as a logical clock.
21    ///
22    /// TID format. Must increase monotonically. Recommend using current
23    /// timestamp as TID; rev values in the "future" (beyond a fudge factor)
24    /// should be ignored and not processed
25    pub rev: String,
26    /// pointer (by hash) to a previous commit object for this repository.
27    ///
28    /// Could be used to create a chain of history, but largely unused (included
29    /// for v2 backwards compatibility). In version 3 repos, this field must
30    /// exist in the CBOR object, but is virtually always null. NOTE: previously
31    /// specified as nullable and optional, but this caused interoperability
32    /// issues.
33    pub prev: Option<Cid>,
34    /// cryptographic signature of this commit, as raw bytes
35    #[serde(with = "serde_bytes")]
36    pub sig: Vec<u8>,
37}
38
39/// MST node data schema
40#[derive(Debug, Deserialize, PartialEq)]
41#[serde(deny_unknown_fields)]
42pub(crate) struct Node {
43    /// link to sub-tree Node on a lower level and with all keys sorting before
44    /// keys at this node
45    #[serde(rename = "l")]
46    pub left: Option<Cid>,
47    /// ordered list of TreeEntry objects
48    ///
49    /// atproto MSTs have a fanout of 4, so there can be max 4 entries.
50    #[serde(rename = "e")]
51    pub entries: Vec<Entry>, // maybe we can do [Option<Entry>; 4]?
52}
53
54impl Node {
55    /// test if a block could possibly be a node
56    ///
57    /// we can't eagerly decode records except where we're *sure* they cannot be
58    /// an mst node (and even then we can only attempt) because you can't know
59    /// with certainty what a block is supposed to be without actually walking
60    /// the tree.
61    ///
62    /// so if a block *could be* a node, any record converter must postpone
63    /// processing. if it turns out it happens to be a very node-looking record,
64    /// well, sorry, it just has to only be processed later when that's known.
65    pub(crate) fn could_be(bytes: impl AsRef<[u8]>) -> bool {
66        const NODE_FINGERPRINT: [u8; 3] = [
67            0xA2, // map length 2 (for "l" and "e" keys)
68            0x61, // text length 1
69            b'e', // "e" before "l" because map keys have to be lex-sorted
70                  // 0x8?: "e" has array (0x100 upper 3 bits) of some length
71        ];
72        let bytes = bytes.as_ref();
73        bytes.starts_with(&NODE_FINGERPRINT)
74            && bytes
75                .get(3)
76                .map(|b| b & 0b1110_0000 == 0x80)
77                .unwrap_or(false)
78    }
79
80    /// Check if a node has any entries
81    ///
82    /// An empty repository with no records is represented as a single MST node
83    /// with an empty array of entries. This is the only situation in which a
84    /// tree may contain an empty leaf node which does not either contain keys
85    /// ("entries") or point to a sub-tree containing entries.
86    pub(crate) fn is_empty(&self) -> bool {
87        self.left.is_none() && self.entries.is_empty()
88    }
89}
90
91/// TreeEntry object
92#[derive(Debug, Deserialize, PartialEq)]
93#[serde(deny_unknown_fields)]
94pub(crate) struct Entry {
95    /// count of bytes shared with previous TreeEntry in this Node (if any)
96    #[serde(rename = "p")]
97    pub prefix_len: usize,
98    /// remainder of key for this TreeEntry, after "prefixlen" have been removed
99    #[serde(rename = "k", with = "serde_bytes")]
100    pub keysuffix: Vec<u8>, // can we String this here?
101    /// link to the record data (CBOR) for this entry
102    #[serde(rename = "v")]
103    pub value: Cid,
104    /// link to a sub-tree Node at a lower level
105    ///
106    /// the lower level must have keys sorting after this TreeEntry's key (to
107    /// the "right"), but before the next TreeEntry's key in this Node (if any)
108    #[serde(rename = "t")]
109    pub tree: Option<Cid>,
110}
repo_stream/mst.rs

repo_stream/
mst.rs
