From eff4692a082ea96a0cf48d82fbd16658cbf52a72 Mon Sep 17 00:00:00 2001
From: bryan newbold <bnewbold@robocracy.org>
Date: Thu, 16 Feb 2023 13:36:34 -0800
Subject: mst: doc comment; another test; consistent struct ordering

---
 adenosine-pds/src/mst.rs | 38 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 37 insertions(+), 1 deletion(-)

(limited to 'adenosine-pds/src/mst.rs')

diff --git a/adenosine-pds/src/mst.rs b/adenosine-pds/src/mst.rs
index 8a28117..1d75da1 100644
--- a/adenosine-pds/src/mst.rs
+++ b/adenosine-pds/src/mst.rs
@@ -1,3 +1,15 @@
+/// This is a simple immutable implemenation of of a Merkle Search Tree (MST) for atproto.
+///
+/// Mutations on the data structure are not implemented; instead the entire tree is read into a
+/// BTreeMap, that is mutated, and then the entire tree is regenerated. This makes implementation
+/// much simpler, at the obvious cost of performance in some situations.
+///
+/// The MST is basically a sorted key/value store where the key is a string and the value is a CID.
+/// Tree nodes are stored as DAG-CBOG IPLD blocks, with references as CIDs.
+///
+/// In the atproto MST implementation, SHA-256 is the hashing algorithm, and "leading zeros" are
+/// counted in blocks of 4 bits (so a leading zero byte counts as two zeros). This happens to match
+/// simple hex encoding of the SHA-256 hash.
 use anyhow::{anyhow, Context, Result};
 use ipfs_sqlite_block_store::BlockStore;
 use libipld::cbor::DagCborCodec;
@@ -34,8 +46,8 @@ pub struct MetadataNode {
 
 #[derive(Debug, DagCbor, PartialEq, Eq)]
 struct MstEntry {
-    k: String,
     p: u32,
+    k: String,
     v: Cid,
     t: Option<Cid>,
 }
@@ -361,3 +373,27 @@ fn serialize_wip_tree(
     db.put_block(block, None)?;
     Ok(cid)
 }
+
+#[test]
+fn test_mst_node_cbor() {
+    use std::str::FromStr;
+    let cid1 =
+        Cid::from_str("bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454").unwrap();
+    let node = MstNode {
+        l: None,
+        e: vec![MstEntry {
+            k: "asdf".to_string(),
+            p: 0,
+            v: cid1,
+            t: None,
+        }],
+    };
+    let block = Block::<DefaultParams>::encode(DagCborCodec, Code::Sha2_256, &node).unwrap();
+    println!("{:?}", block);
+    //assert_eq!(1, 2);
+    let cid = *block.cid();
+    assert_eq!(
+        cid.to_string(),
+        "bafyreidaftbr35xhh4lzmv5jcoeufqjh75ohzmz6u56v7n2ippbtxdgqqe"
+    );
+}
-- 
cgit v1.2.3