Skip to main content

didbot_repo/
repository.rs

1//! A repository: records, the tree over them, and the commit that signs it.
2
3use std::collections::{BTreeMap, BTreeSet};
4use std::ops::Bound;
5
6use didbot_data::mst::{Rewritten, Tree};
7use didbot_data::{dag_cbor, Cid, DataError, Value};
8use didbot_key::SigningKey;
9
10use crate::car;
11use crate::commit::{Commit, SignedCommit, REPO_VERSION};
12
13/// The key a record sits at in the tree.
14///
15/// atproto keys a repository by `<collection>/<rkey>` and nothing else — not
16/// by the DID, which the commit already carries, and not by anything the
17/// server chooses. It is one line, and it is here rather than inlined at both
18/// call sites because a repository whose keys are built two ways is a
19/// repository with two roots.
20#[must_use]
21pub fn tree_key(collection: &str, rkey: &str) -> String {
22    format!("{collection}/{rkey}")
23}
24
25/// Why a repository could not be assembled.
26#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
27pub enum RepoError {
28    /// A record held something the data model has no encoding for.
29    ///
30    /// Reachable only for a record that reached storage without going through
31    /// the write path's validation — the lexicon check refuses floats and
32    /// malformed blobs long before this. It is an error rather than a panic
33    /// because an export must be able to say *which* record it could not
34    /// name, so somebody can go and look at it.
35    #[error("`{key}` cannot be encoded: {source}")]
36    Record {
37        /// The tree key of the offending record.
38        key: String,
39        /// What the data model refused.
40        source: DataError,
41    },
42}
43
44/// A repository under construction.
45///
46/// Records go in, and a signature turns the result into something a stranger
47/// can check. This builds the whole tree from every record at once. A
48/// repository already signed is changed one record at a time through
49/// [`Repository::draft`] instead, which lands on the same tree.
50#[derive(Debug, Default)]
51pub struct Builder {
52    leaves: BTreeMap<String, Cid>,
53    blocks: BTreeMap<Cid, Vec<u8>>,
54}
55
56impl Builder {
57    /// A repository with no records in it.
58    #[must_use]
59    pub fn new() -> Self {
60        Self::default()
61    }
62
63    /// Adds one record, returning the CID that now names it.
64    ///
65    /// This is where a record stops being JSON a server happens to hold and
66    /// becomes a block with an identity: the CID is the sha-256 of the one
67    /// canonical DAG-CBOR encoding of it, and it is the value the tree
68    /// keys on and the commit ultimately signs over.
69    pub fn insert(
70        &mut self,
71        collection: &str,
72        rkey: &str,
73        record: &serde_json::Value,
74    ) -> Result<Cid, RepoError> {
75        let (key, cid, block) = encode(collection, rkey, record)?;
76        self.blocks.insert(cid.clone(), block);
77        self.leaves.insert(key, cid.clone());
78        Ok(cid)
79    }
80
81    /// How many records are in it.
82    #[must_use]
83    pub fn len(&self) -> usize {
84        self.leaves.len()
85    }
86
87    /// Whether it holds no records. An empty repository is a real one.
88    #[must_use]
89    pub fn is_empty(&self) -> bool {
90        self.leaves.is_empty()
91    }
92
93    /// Builds the tree, writes the commit and signs it.
94    ///
95    /// `rev` is the caller's, because this crate has no clock and no TID
96    /// minter; `prev` is the commit this replaces, which is `None` for a
97    /// server that does not keep a commit history.
98    #[must_use]
99    pub fn commit(self, did: &str, rev: &str, prev: Option<Cid>, key: &SigningKey) -> Repository {
100        let tree = Tree::build(&self.leaves);
101        let commit = sign(did, &tree, rev, prev, key);
102        let mut records: BTreeMap<Cid, Held> = BTreeMap::new();
103        for cid in self.leaves.values() {
104            if let Some(held) = records.get_mut(cid) {
105                held.keys += 1;
106            } else if let Some(bytes) = self.blocks.get(cid) {
107                records.insert(
108                    cid.clone(),
109                    Held {
110                        bytes: bytes.clone(),
111                        keys: 1,
112                    },
113                );
114            }
115        }
116        Repository {
117            commit,
118            tree,
119            records,
120            leaves: self.leaves,
121        }
122    }
123}
124
125/// Encodes a record, answering its tree key, its CID and its block.
126///
127/// This is where a record stops being JSON a server happens to hold and
128/// becomes a block with an identity: the CID is the sha-256 of the one
129/// canonical DAG-CBOR encoding of it.
130fn encode(
131    collection: &str,
132    rkey: &str,
133    record: &serde_json::Value,
134) -> Result<(String, Cid, Vec<u8>), RepoError> {
135    let key = tree_key(collection, rkey);
136    let value = Value::object_from_json(record).map_err(|source| RepoError::Record {
137        key: key.clone(),
138        source,
139    })?;
140    let block = dag_cbor::encode(&value);
141    let cid = Cid::of_dag_cbor(&block);
142    Ok((key, cid, block))
143}
144
145/// Writes and signs the commit over a tree.
146fn sign(did: &str, tree: &Tree, rev: &str, prev: Option<Cid>, key: &SigningKey) -> SignedCommit {
147    Commit {
148        did: did.to_owned(),
149        version: REPO_VERSION,
150        data: tree.root().clone(),
151        rev: rev.to_owned(),
152        prev,
153    }
154    .sign(key)
155}
156
157/// A record block, and how many keys name it.
158///
159/// Two keys holding the same record name one block. Counting them is what
160/// lets a removal tell whether the block goes with the key.
161#[derive(Debug, Clone)]
162struct Held {
163    bytes: Vec<u8>,
164    keys: usize,
165}
166
167/// A signed repository, ready to be handed to somebody who does not trust us.
168#[derive(Debug, Clone)]
169pub struct Repository {
170    commit: SignedCommit,
171    /// The tree, kept rather than flattened into blocks, because a proof is a
172    /// walk through it and a walk needs the nodes.
173    tree: Tree,
174    /// The record blocks, keyed by CID. Tree nodes are the tree's.
175    records: BTreeMap<Cid, Held>,
176    /// Every record's tree key and the CID it names.
177    leaves: BTreeMap<String, Cid>,
178}
179
180/// The blocks that prove what a repository says about one key.
181///
182/// A commit block, the Merkle search tree nodes from the root down to where
183/// the key sits, and the record itself when there is one. That is all, and
184/// the "that is all" is the point: a verifier that is handed every block in
185/// the repository has been given an export, and an export is not a proof of
186/// anything in particular.
187///
188/// # What a verifier does with it
189///
190/// 1. Resolves the DID and takes the public key out of its document.
191/// 2. Checks the commit block's signature with it, which fixes `data` — the
192///    root of the tree the account signed over — as a fact rather than as
193///    this server's word.
194/// 3. Walks: hashes the first node block, requires it to be `data`, decodes
195///    it, finds which entry range `<collection>/<rkey>` falls in, and follows
196///    that link to the next block. A block that hashes to something the
197///    parent did not name is not on the path.
198/// 4. At the end, either the key is an entry — and its `v` is the CID of a
199///    record block that is also in the file — or it is not, and the key is
200///    provably not in the repository.
201///
202/// Every one of those steps fails closed. A missing node breaks step 3, a
203/// node lifted from another tree fails the hash comparison in step 3, and a
204/// substituted record fails the CID comparison in step 4.
205#[derive(Debug, Clone)]
206pub struct Proof {
207    root: Cid,
208    key: String,
209    value: Option<Cid>,
210    blocks: BTreeMap<Cid, Vec<u8>>,
211    nodes: Vec<Cid>,
212}
213
214impl Proof {
215    /// The commit this proof is against, which is the CAR export's root.
216    #[must_use]
217    pub fn root(&self) -> &Cid {
218        &self.root
219    }
220
221    /// The tree key the proof is about, `<collection>/<rkey>`.
222    #[must_use]
223    pub fn key(&self) -> &str {
224        &self.key
225    }
226
227    /// The record the key names, or `None` when the proof is of absence.
228    #[must_use]
229    pub fn record(&self) -> Option<&Cid> {
230        self.value.as_ref()
231    }
232
233    /// The tree nodes walked, root first.
234    #[must_use]
235    pub fn nodes(&self) -> &[Cid] {
236        &self.nodes
237    }
238
239    /// Every block in the proof, keyed by CID.
240    #[must_use]
241    pub fn blocks(&self) -> &BTreeMap<Cid, Vec<u8>> {
242        &self.blocks
243    }
244
245    /// The proof as a CARv1 file, rooted at the commit.
246    ///
247    /// The same container `com.atproto.sync.getRepo` returns, holding a
248    /// different set of blocks — which is exactly what upstream's
249    /// `getRecord` does, and why a client can point one CAR reader at both.
250    #[must_use]
251    pub fn to_car(&self) -> Vec<u8> {
252        car::write(
253            &self.root,
254            self.blocks
255                .iter()
256                .map(|(cid, block)| (cid.clone(), block.clone())),
257        )
258    }
259}
260
261impl Repository {
262    /// The signed commit at the top of it.
263    #[must_use]
264    pub fn commit(&self) -> &SignedCommit {
265        &self.commit
266    }
267
268    /// The CID of the commit, which is a CAR export's root.
269    #[must_use]
270    pub fn root(&self) -> Cid {
271        self.commit.cid()
272    }
273
274    /// The revision this repository committed at.
275    #[must_use]
276    pub fn rev(&self) -> &str {
277        &self.commit.commit().rev
278    }
279
280    /// How many records it holds.
281    #[must_use]
282    pub fn records(&self) -> usize {
283        self.leaves.len()
284    }
285
286    /// The CID a record is filed under, if the repository holds it.
287    #[must_use]
288    pub fn record_cid(&self, collection: &str, rkey: &str) -> Option<&Cid> {
289        self.leaves.get(&tree_key(collection, rkey))
290    }
291
292    /// One block by CID: the commit, a tree node, or a record.
293    ///
294    /// The three are searched in that order, which is arbitrary — a CID names
295    /// exactly one of them or none.
296    #[must_use]
297    pub fn block(&self, cid: &Cid) -> Option<Vec<u8>> {
298        if cid == &self.root() {
299            return Some(self.commit.block());
300        }
301        self.stored(cid).cloned()
302    }
303
304    /// A tree node or a record block by CID, without the commit.
305    fn stored(&self, cid: &Cid) -> Option<&Vec<u8>> {
306        self.tree
307            .blocks()
308            .get(cid)
309            .or_else(|| self.records.get(cid).map(|held| &held.bytes))
310    }
311
312    /// The blocks that prove what this repository says about one record.
313    ///
314    /// Answers for a key the repository does not hold too: see [`Proof`],
315    /// where the difference between the two answers is one field.
316    #[must_use]
317    pub fn proof(&self, collection: &str, rkey: &str) -> Proof {
318        let key = tree_key(collection, rkey);
319        let path = self.tree.path(&key);
320        let mut blocks = BTreeMap::new();
321        let root = self.root();
322        blocks.insert(root.clone(), self.commit.block());
323        for cid in &path.nodes {
324            if let Some(block) = self.tree.blocks().get(cid) {
325                blocks.insert(cid.clone(), block.clone());
326            }
327        }
328        if let Some(value) = &path.value {
329            if let Some(held) = self.records.get(value) {
330                blocks.insert(value.clone(), held.bytes.clone());
331            }
332        }
333        Proof {
334            root,
335            key,
336            value: path.value,
337            blocks,
338            nodes: path.nodes,
339        }
340    }
341
342    /// The Merkle search tree blocks that cover every key in `keys`, over the
343    /// tree as this repository now stands.
344    ///
345    /// The union of [`Tree::covering_proof`] over each key — not just its
346    /// own path, but the paths to its neighbours either side, because a
347    /// split or merge moves nodes on both. A caller that touched several
348    /// keys in one commit (`com.atproto.repo.applyWrites`) unions their
349    /// proofs here rather than calling the tree once per key and merging
350    /// itself.
351    ///
352    /// This is what a `com.atproto.sync.subscribeRepos#commit` frame's
353    /// blocks are built from: a relay holds no previous state to walk a
354    /// created-only diff against, so it needs enough of the tree to invert
355    /// the operations back to `prevData` starting from nothing. See
356    /// `docs/conformance.md`.
357    ///
358    /// Each key's neighbours are found in the repository's own index of
359    /// keys, so this walks three paths per key and nothing else.
360    #[must_use]
361    pub fn covering_proof(&self, keys: &BTreeSet<String>) -> BTreeMap<Cid, Vec<u8>> {
362        let mut proof = BTreeMap::new();
363        for key in keys {
364            let before = self
365                .leaves
366                .range::<str, _>((Bound::Unbounded, Bound::Excluded(key.as_str())))
367                .next_back()
368                .map(|(held, _)| held.as_str());
369            let after = self
370                .leaves
371                .range::<str, _>((Bound::Excluded(key.as_str()), Bound::Unbounded))
372                .next()
373                .map(|(held, _)| held.as_str());
374            proof.extend(self.tree.covering_proof_between(key, before, after));
375        }
376        proof
377    }
378
379    /// How many Merkle search tree nodes it took to key them.
380    ///
381    /// An operator-facing number, and the cheapest signal that the tree is
382    /// doing something: a repository whose node count tracks its record count
383    /// one for one has a broken height function.
384    #[must_use]
385    pub fn nodes(&self) -> usize {
386        self.tree.len()
387    }
388
389    /// Every block in the repository, named.
390    ///
391    /// The commit, every tree node and every record, which is exactly what
392    /// [`Self::to_car`] writes. It exists for a caller keeping a history: the
393    /// difference between two repositories' block sets is the set a commit
394    /// created, and a caller that has one repository and the CIDs another one
395    /// held can work out what to send without either party holding both.
396    #[must_use]
397    pub fn block_cids(&self) -> BTreeSet<Cid> {
398        std::iter::once(self.root())
399            .chain(self.tree.blocks().keys().cloned())
400            .chain(self.records.keys().cloned())
401            .collect()
402    }
403
404    /// The whole repository as a CARv1 file.
405    ///
406    /// Commit first, then the tree nodes and the records in CID order. The
407    /// order carries no meaning to a reader — it walks from the root by
408    /// following links — but it is fixed, so two exports of the same state
409    /// are byte-identical.
410    #[must_use]
411    pub fn to_car(&self) -> Vec<u8> {
412        self.car(|_| true)
413    }
414
415    /// The repository as a CARv1 file carrying only the blocks a reader lacks.
416    ///
417    /// `held` is what the reader is known to have already. The root is the
418    /// current commit either way, so a reader walks from the same place; what
419    /// changes is how much of the walk it can do out of the file alone.
420    ///
421    /// The commit block is always written, even when `held` names it. A CAR
422    /// whose root is not in it is legal and every reader here can follow one,
423    /// but a file that declares a root and then omits it is the kind of
424    /// answer that makes a caller wonder whether the transfer failed, and one
425    /// block is not worth the doubt.
426    ///
427    /// Ordering matches [`Self::to_car`]'s, so a diff and a full export agree
428    /// about the blocks they have in common.
429    #[must_use]
430    pub fn to_car_without(&self, held: &BTreeSet<Cid>) -> Vec<u8> {
431        self.car(|cid| !held.contains(cid))
432    }
433
434    /// The repository as a CARv1 file carrying the commit and the blocks in
435    /// `wanted` that it holds.
436    ///
437    /// The same file [`Self::to_car_without`] writes when `held` is every
438    /// other block. This looks each wanted block up rather than walking every
439    /// block the repository holds, which is what makes it the one a firehose
440    /// frame is written with.
441    #[must_use]
442    pub fn to_car_with(&self, wanted: &BTreeSet<Cid>) -> Vec<u8> {
443        let commit_block = self.commit.block();
444        let root = Cid::of_dag_cbor(&commit_block);
445        let blocks = wanted
446            .iter()
447            .filter(|cid| **cid != root)
448            .filter_map(|cid| Some((cid.clone(), self.stored(cid)?.clone())));
449        car::write(
450            &root,
451            std::iter::once((root.clone(), commit_block)).chain(blocks),
452        )
453    }
454
455    /// Opens this repository to be changed one record at a time.
456    ///
457    /// See [`Draft`]. The repository is moved into the draft, so a caller
458    /// sharing it clones it first.
459    #[must_use]
460    pub fn draft(self) -> Draft {
461        Draft {
462            repository: self,
463            rewritten: Rewritten::default(),
464        }
465    }
466
467    /// Writes a CAR of the blocks `wanted` accepts, plus the commit.
468    fn car(&self, wanted: impl Fn(&Cid) -> bool) -> Vec<u8> {
469        let commit_block = self.commit.block();
470        let root = Cid::of_dag_cbor(&commit_block);
471        let mut blocks: BTreeMap<Cid, Vec<u8>> = self.tree.blocks().clone();
472        blocks.extend(
473            self.records
474                .iter()
475                .map(|(cid, held)| (cid.clone(), held.bytes.clone())),
476        );
477        let blocks = std::iter::once((root.clone(), commit_block))
478            .chain(blocks.into_iter().filter(|(cid, _)| wanted(cid)));
479        car::write(&root, blocks)
480    }
481}
482
483/// A signed repository being changed, one record at a time, into its next
484/// commit.
485///
486/// Each change edits the tree in place with [`Tree::insert`] or
487/// [`Tree::remove`], and [`Draft::commit`] signs the result. The repository
488/// that comes out is the one a [`Builder`] makes from the same records under
489/// the same revision: the same tree, the same record blocks and the same
490/// signed commit.
491///
492/// Alongside it comes what the commit changed about the blocks the
493/// repository holds, measured against the commit the draft was opened at.
494/// That is what a firehose frame and a `since` diff are made of, and working
495/// it out here costs only the blocks that moved.
496#[derive(Debug)]
497pub struct Draft {
498    repository: Repository,
499    rewritten: Rewritten,
500}
501
502impl Draft {
503    /// Puts a record at `collection`/`rkey`, replacing whatever was there,
504    /// and answers the CID that now names it.
505    ///
506    /// Fails for a record the data model cannot encode, as
507    /// [`Builder::insert`] does. The draft is then left part way through a
508    /// change, and the caller drops it.
509    pub fn insert(
510        &mut self,
511        collection: &str,
512        rkey: &str,
513        record: &serde_json::Value,
514    ) -> Result<Cid, RepoError> {
515        let (key, cid, block) = encode(collection, rkey, record)?;
516        match self.repository.leaves.insert(key.clone(), cid.clone()) {
517            Some(old) if old == cid => return Ok(cid),
518            Some(old) => self.release(&old),
519            None => {}
520        }
521        if let Some(held) = self.repository.records.get_mut(&cid) {
522            held.keys += 1;
523        } else {
524            self.repository.records.insert(
525                cid.clone(),
526                Held {
527                    bytes: block,
528                    keys: 1,
529                },
530            );
531            self.rewritten.then(Rewritten {
532                created: BTreeSet::from([cid.clone()]),
533                removed: BTreeSet::new(),
534            });
535        }
536        let rewritten = self.repository.tree.insert(&key, cid.clone());
537        self.rewritten.then(rewritten);
538        Ok(cid)
539    }
540
541    /// Takes the record at `collection`/`rkey` out, answering the CID it was
542    /// named by, or `None` if the key held nothing.
543    pub fn remove(&mut self, collection: &str, rkey: &str) -> Option<Cid> {
544        let key = tree_key(collection, rkey);
545        let old = self.repository.leaves.remove(&key)?;
546        self.release(&old);
547        let rewritten = self.repository.tree.remove(&key);
548        self.rewritten.then(rewritten);
549        Some(old)
550    }
551
552    /// Signs the draft as the commit at `rev` following `prev`.
553    ///
554    /// Answers the repository and the blocks it holds now and did not at the
555    /// commit the draft was opened at, and the reverse. The commit blocks are
556    /// among them: the new one is created and the old one removed.
557    #[must_use]
558    pub fn commit(self, rev: &str, prev: Option<Cid>, key: &SigningKey) -> (Repository, Rewritten) {
559        let Self {
560            mut repository,
561            mut rewritten,
562        } = self;
563        let before = repository.root();
564        let did = repository.commit.commit().did.clone();
565        repository.commit = sign(&did, &repository.tree, rev, prev, key);
566        rewritten.then(Rewritten {
567            created: BTreeSet::from([repository.root()]),
568            removed: BTreeSet::from([before]),
569        });
570        (repository, rewritten)
571    }
572
573    /// Drops one key's hold on a record block, and the block with the last.
574    fn release(&mut self, cid: &Cid) {
575        let Some(held) = self.repository.records.get_mut(cid) else {
576            return;
577        };
578        held.keys -= 1;
579        if held.keys == 0 {
580            self.repository.records.remove(cid);
581            self.rewritten.then(Rewritten {
582                created: BTreeSet::new(),
583                removed: BTreeSet::from([cid.clone()]),
584            });
585        }
586    }
587}
588
589#[cfg(test)]
590mod tests {
591    use super::*;
592
593    fn thing(text: &str) -> serde_json::Value {
594        serde_json::json!({
595            "$type": "com.example.thing",
596            "text": text,
597            "emoji": "🜁",
598            "createdAt": "2026-08-26T00:00:00Z",
599        })
600    }
601
602    /// Two revisions of one repository, so a test can talk about what the
603    /// second added.
604    fn pair() -> (Repository, Repository) {
605        let key = SigningKey::generate();
606        let mut one = Builder::new();
607        one.insert("com.example.thing", "3lqma", &thing("quernstone"))
608            .expect("valid");
609        let mut two = Builder::new();
610        two.insert("com.example.thing", "3lqma", &thing("quernstone"))
611            .expect("valid");
612        two.insert("com.example.thing", "3lqmb", &thing("farthingale"))
613            .expect("valid");
614        let one = one.commit("did:web:a.example", "3lqma", None, &key);
615        let two = two.commit("did:web:a.example", "3lqmb", Some(one.root()), &key);
616        (one, two)
617    }
618
619    /// Everything a full export carries is named, and everything named can be
620    /// fetched. A history keeping these CIDs is keeping the export's own
621    /// vocabulary and not a second one beside it.
622    #[test]
623    fn the_block_names_are_the_blocks_the_export_holds() {
624        let (_, repo) = pair();
625        let named = repo.block_cids();
626        assert!(named.contains(&repo.root()));
627        for cid in &named {
628            assert!(
629                repo.block(cid).is_some(),
630                "{cid} is named and cannot be fetched"
631            );
632        }
633        let read = car::read(&repo.to_car()).expect("a CAR this crate wrote");
634        assert_eq!(read.blocks.keys().cloned().collect::<BTreeSet<_>>(), named);
635    }
636
637    /// The point of the whole exercise: a reader holding the earlier revision
638    /// is sent the new record and the nodes that reach it, and not the record
639    /// it already had.
640    #[test]
641    fn a_diff_leaves_out_what_the_reader_already_holds() {
642        let (one, two) = pair();
643        let held = one.block_cids();
644        let diff = two.to_car_without(&held);
645        assert!(diff.len() < two.to_car().len());
646
647        let read = car::read(&diff).expect("a CAR this crate wrote");
648        assert_eq!(read.roots, vec![two.root()]);
649        let carried: BTreeSet<Cid> = read.blocks.keys().cloned().collect();
650        for cid in &two.block_cids() {
651            let expected = cid == &two.root() || !held.contains(cid);
652            assert_eq!(
653                carried.contains(cid),
654                expected,
655                "{cid} is on the wrong side of the diff"
656            );
657        }
658    }
659
660    /// A reader already at the head is told so with a file holding the commit
661    /// and nothing else, rather than with the whole repository.
662    #[test]
663    fn a_reader_at_the_head_is_sent_only_the_commit() {
664        let (_, repo) = pair();
665        let read =
666            car::read(&repo.to_car_without(&repo.block_cids())).expect("a CAR this crate wrote");
667        assert_eq!(read.blocks.len(), 1);
668        assert!(read.blocks.contains_key(&repo.root()));
669    }
670
671    /// A diff against nothing is the export, byte for byte. Two ways of
672    /// writing one repository that disagreed would be a reader's problem
673    /// rather than ours.
674    #[test]
675    fn a_diff_against_nothing_is_the_whole_export() {
676        let (_, repo) = pair();
677        assert_eq!(repo.to_car_without(&BTreeSet::new()), repo.to_car());
678    }
679
680    #[test]
681    fn an_empty_repository_still_commits() {
682        let key = SigningKey::generate();
683        let repo = Builder::new().commit("did:web:a.example", "3lqmnopqrstuv", None, &key);
684        assert_eq!(repo.records(), 0);
685        assert_eq!(repo.nodes(), 1);
686        assert!(repo.commit().verify(&key.verifying_key()).is_ok());
687    }
688
689    /// The same records under the same key give the same file, which is what
690    /// makes an export cacheable and a test able to compare two of them.
691    #[test]
692    fn the_same_state_exports_the_same_bytes() {
693        let key = SigningKey::generate();
694        let build = || {
695            let mut builder = Builder::new();
696            for (rkey, text) in [("3lqma", "quernstone"), ("3lqmb", "farthingale")] {
697                builder
698                    .insert("com.example.thing", rkey, &thing(text))
699                    .expect("a valid record");
700            }
701            builder.commit("did:web:a.example", "3lqmnopqrstuv", None, &key)
702        };
703        assert_eq!(build().to_car(), build().to_car());
704    }
705
706    /// Adding a record moves the tree root, which moves the signed bytes,
707    /// which moves the commit. If any link in that chain were missing an
708    /// export would keep verifying after the repository changed.
709    #[test]
710    fn a_new_record_moves_the_commit() {
711        let key = SigningKey::generate();
712        let mut one = Builder::new();
713        one.insert("com.example.thing", "3lqma", &thing("quernstone"))
714            .expect("valid");
715        let mut two = Builder::new();
716        two.insert("com.example.thing", "3lqma", &thing("quernstone"))
717            .expect("valid");
718        two.insert("com.example.thing", "3lqmb", &thing("farthingale"))
719            .expect("valid");
720
721        let one = one.commit("did:web:a.example", "3lqma", None, &key);
722        let two = two.commit("did:web:a.example", "3lqma", None, &key);
723        assert_ne!(one.commit().commit().data, two.commit().commit().data);
724        assert_ne!(one.root(), two.root());
725    }
726
727    /// A record is keyed by collection and rkey together, so the same rkey in
728    /// two collections is two records — as in atproto.
729    #[test]
730    fn one_rkey_in_two_collections_is_two_records() {
731        let mut builder = Builder::new();
732        builder
733            .insert("com.example.thing", "self", &thing("one"))
734            .expect("valid");
735        builder
736            .insert("app.bsky.actor.profile", "self", &thing("two"))
737            .expect("valid");
738        assert_eq!(builder.len(), 2);
739    }
740
741    #[test]
742    fn a_record_the_data_model_cannot_hold_names_itself() {
743        let mut builder = Builder::new();
744        let error = builder
745            .insert(
746                "com.example.thing",
747                "3lqma",
748                &serde_json::json!({"ratio": 1.5}),
749            )
750            .expect_err("a float has no encoding");
751        assert!(
752            matches!(&error, RepoError::Record { key, .. } if key == "com.example.thing/3lqma"),
753            "{error}"
754        );
755    }
756}