A better Rust ATProto crate
1//! Interoperability tests using test vectors from atproto-interop-tests
2//!
3//! See: https://github.com/bluesky-social/atproto-interop-tests/tree/main/mst
4//!
5
6use std::sync::Arc;
7
8use jacquard_common::types::crypto::SHA2_256;
9use jacquard_repo::DAG_CBOR_CID_CODEC;
10use jacquard_repo::mst::tree::{Mst, VerifiedWriteOp};
11use jacquard_repo::mst::util::{common_prefix_len, layer_for_key};
12use jacquard_repo::storage::BlockStore;
13use jacquard_repo::storage::memory::MemoryBlockStore;
14use rand::Rng;
15use serde::Deserialize;
16
17/// Test helper: Generate a random key at a specific layer
18///
19/// Reimplementation of gen_keys.py from atproto-interop-tests for Rust tests.
20/// Generates keys like "A0/123456" that hash to a specific MST layer.
21fn gen_key_at_layer(letter: char, layer: usize) -> String {
22 let mut rng = rand::thread_rng();
23 loop {
24 let num: u32 = rng.gen_range(0..1_000_000);
25 let key = format!("{}{}/{:06}", letter, layer, num);
26 if layer_for_key(&key) == layer {
27 return key;
28 }
29 }
30}
31
32#[derive(Debug, Deserialize)]
33struct CommonPrefixTest {
34 left: String,
35 right: String,
36 len: usize,
37}
38
39#[derive(Debug, Deserialize)]
40struct KeyHeightTest {
41 key: String,
42 height: usize,
43}
44
45#[test]
46fn test_common_prefix_interop() {
47 let json = include_str!("fixtures/common_prefix.json");
48 let tests: Vec<CommonPrefixTest> = serde_ipld_dagjson::from_slice(json.as_bytes()).unwrap();
49
50 for test in tests {
51 let result = common_prefix_len(&test.left, &test.right);
52 assert_eq!(
53 result, test.len,
54 "common_prefix_len({:?}, {:?}) = {}, expected {}",
55 test.left, test.right, result, test.len
56 );
57 }
58}
59
60#[test]
61fn test_layer_for_key_interop() {
62 let json = include_str!("fixtures/key_heights.json");
63 let tests: Vec<KeyHeightTest> = serde_ipld_dagjson::from_slice(json.as_bytes()).unwrap();
64
65 for test in tests {
66 if test.key.is_empty() {
67 // Empty key is invalid, skip
68 continue;
69 }
70
71 let result = layer_for_key(&test.key);
72 assert_eq!(
73 result, test.height,
74 "layer_for_key({:?}) = {}, expected {}",
75 test.key, result, test.height
76 );
77 }
78}
79
80#[tokio::test]
81async fn test_example_keys_tree_ops() {
82 // Load example keys
83 let keys_txt = include_str!("fixtures/example_keys.txt");
84 let keys: Vec<&str> = keys_txt.lines().collect();
85
86 let storage = Arc::new(MemoryBlockStore::new());
87 let mut mst = Mst::new(storage);
88
89 // Helper to create test CIDs
90 fn test_cid(n: u8) -> cid::Cid {
91 let data = vec![n; 32];
92 let mh = multihash::Multihash::wrap(SHA2_256, &data).unwrap();
93 cid::Cid::new_v1(DAG_CBOR_CID_CODEC, mh)
94 }
95
96 // Add all keys
97 for (i, &key) in keys.iter().enumerate() {
98 mst = mst.add(key, test_cid(i as u8)).await.unwrap();
99 }
100
101 // Verify all keys can be retrieved
102 for (i, &key) in keys.iter().enumerate() {
103 let retrieved = mst.get(key).await.unwrap();
104 assert_eq!(
105 retrieved,
106 Some(test_cid(i as u8)),
107 "Failed to retrieve key: {}",
108 key
109 );
110 }
111
112 // Delete half the keys
113 for (i, &key) in keys.iter().enumerate() {
114 if i % 2 == 0 {
115 mst = mst.delete(key).await.unwrap();
116 }
117 }
118
119 // Verify deleted keys are gone and remaining keys still exist
120 for (i, &key) in keys.iter().enumerate() {
121 let retrieved = mst.get(key).await.unwrap();
122 if i % 2 == 0 {
123 assert_eq!(retrieved, None, "Key should be deleted: {}", key);
124 } else {
125 assert_eq!(
126 retrieved,
127 Some(test_cid(i as u8)),
128 "Key should still exist: {}",
129 key
130 );
131 }
132 }
133}
134
135#[tokio::test]
136async fn test_determinism_with_example_keys() {
137 // Tree structure should be deterministic regardless of insertion order
138 let keys_txt = include_str!("fixtures/example_keys.txt");
139 let keys: Vec<&str> = keys_txt.lines().filter(|s| !s.is_empty()).collect();
140
141 fn test_cid(n: u8) -> cid::Cid {
142 let data = vec![n; 32];
143 let mh = multihash::Multihash::wrap(SHA2_256, &data).unwrap();
144 cid::Cid::new_v1(DAG_CBOR_CID_CODEC, mh)
145 }
146
147 // Build tree in forward order
148 let storage1 = Arc::new(MemoryBlockStore::new());
149 let mut mst1 = Mst::new(storage1);
150 for (i, &key) in keys.iter().enumerate() {
151 mst1 = mst1.add(key, test_cid(i as u8)).await.unwrap();
152 }
153
154 // Build tree in reverse order
155 let storage2 = Arc::new(MemoryBlockStore::new());
156 let mut mst2 = Mst::new(storage2);
157 for (i, &key) in keys.iter().rev().enumerate() {
158 let idx = keys.len() - 1 - i;
159 mst2 = mst2.add(key, test_cid(idx as u8)).await.unwrap();
160 }
161
162 // Check if all keys are retrievable from both trees
163 let mut missing_in_1 = Vec::new();
164 let mut missing_in_2 = Vec::new();
165
166 for key in keys.iter() {
167 let v1 = mst1.get(key).await.unwrap();
168 let v2 = mst2.get(key).await.unwrap();
169
170 if v1.is_none() {
171 missing_in_1.push(key);
172 }
173 if v2.is_none() {
174 missing_in_2.push(key);
175 }
176 }
177
178 if !missing_in_1.is_empty() {
179 eprintln!("Missing in mst1 ({} keys):", missing_in_1.len());
180 for key in missing_in_1.iter().take(5) {
181 eprintln!(" {}", key);
182 }
183 }
184
185 if !missing_in_2.is_empty() {
186 eprintln!("Missing in mst2 ({} keys):", missing_in_2.len());
187 for key in missing_in_2.iter().take(5) {
188 eprintln!(" {}", key);
189 }
190 }
191
192 eprintln!("Keys missing in mst1: {}", missing_in_1.len());
193 eprintln!("Keys missing in mst2: {}", missing_in_2.len());
194
195 // Root CIDs should match
196 eprintln!("mst1 root: {:?}", mst1.root().await.unwrap());
197 eprintln!("mst2 root: {:?}", mst2.root().await.unwrap());
198
199 assert_eq!(
200 mst1.root().await.unwrap(),
201 mst2.root().await.unwrap(),
202 "Tree structure should be deterministic"
203 );
204}
205
206#[tokio::test]
207async fn test_generated_keys_at_specific_layers() {
208 // Generate keys at different layers and verify they work correctly
209 let storage = Arc::new(MemoryBlockStore::new());
210 let mut mst = Mst::new(storage);
211
212 fn test_cid(n: u8) -> cid::Cid {
213 let data = vec![n; 32];
214 let mh = multihash::Multihash::wrap(SHA2_256, &data).unwrap();
215 cid::Cid::new_v1(DAG_CBOR_CID_CODEC, mh)
216 }
217
218 // Generate keys at layers 0-5
219 let mut keys_by_layer: Vec<(String, usize)> = Vec::new();
220 for layer in 0..=5 {
221 let key = gen_key_at_layer('T', layer);
222 // Verify it's actually at the expected layer
223 assert_eq!(layer_for_key(&key), layer);
224 keys_by_layer.push((key, layer));
225 }
226
227 // Add all keys to tree
228 for (i, (key, _layer)) in keys_by_layer.iter().enumerate() {
229 mst = mst.add(key, test_cid(i as u8)).await.unwrap();
230 }
231
232 // Verify all keys can be retrieved
233 for (i, (key, _layer)) in keys_by_layer.iter().enumerate() {
234 let retrieved = mst.get(key).await.unwrap();
235 assert_eq!(retrieved, Some(test_cid(i as u8)));
236 }
237}
238
239#[derive(Debug, Deserialize)]
240struct CommitProofFixture {
241 comment: String,
242 #[serde(rename = "leafValue")]
243 leaf_value: String,
244 keys: Vec<String>,
245 adds: Vec<String>,
246 dels: Vec<String>,
247 #[serde(rename = "rootBeforeCommit")]
248 root_before_commit: String,
249 #[serde(rename = "rootAfterCommit")]
250 root_after_commit: String,
251 #[serde(rename = "blocksInProof")]
252 _blocks_in_proof: Vec<String>,
253}
254
255#[tokio::test]
256async fn test_commit_proof_fixtures() {
257 let json = include_str!("fixtures/commit_proof.json");
258 let fixtures: Vec<CommitProofFixture> =
259 serde_ipld_dagjson::from_slice(json.as_bytes()).unwrap();
260
261 for fixture in fixtures {
262 println!("\n=== Testing: {} ===", fixture.comment);
263
264 // Parse the leaf value CID
265 let leaf_cid: cid::Cid = fixture.leaf_value.parse().unwrap();
266
267 // Build initial tree from keys
268 let storage = Arc::new(MemoryBlockStore::new());
269 let mut mst = Mst::new(storage);
270
271 for key in &fixture.keys {
272 mst = mst.add(key, leaf_cid).await.unwrap();
273 }
274
275 // Verify root before commit
276 let root_before = mst.root().await.unwrap();
277 let expected_before: cid::Cid = fixture.root_before_commit.parse().unwrap();
278
279 assert_eq!(
280 root_before.to_string(),
281 expected_before.to_string(),
282 "Root CID mismatch before commit (fixture: {})",
283 fixture.comment
284 );
285
286 // Apply adds
287 for key in &fixture.adds {
288 mst = mst.add(key, leaf_cid).await.unwrap();
289 }
290
291 // Apply deletes
292 for key in &fixture.dels {
293 mst = mst.delete(key).await.unwrap();
294 }
295
296 // Verify root after commit
297 let root_after = mst.root().await.unwrap();
298 let expected_after: cid::Cid = fixture.root_after_commit.parse().unwrap();
299
300 assert_eq!(
301 root_after.to_string(),
302 expected_after.to_string(),
303 "Root CID mismatch after commit (fixture: {})",
304 fixture.comment
305 );
306
307 println!("✓ Passed: {}", fixture.comment);
308 }
309}
310
311#[tokio::test]
312async fn test_commit_proof_using_batch() {
313 // Same as above but using batch operations instead of individual add/delete
314 let json = include_str!("fixtures/commit_proof.json");
315 let fixtures: Vec<CommitProofFixture> =
316 serde_ipld_dagjson::from_slice(json.as_bytes()).unwrap();
317
318 for fixture in fixtures {
319 println!("\n=== Testing (batch): {} ===", fixture.comment);
320
321 let leaf_cid: cid::Cid = fixture.leaf_value.parse().unwrap();
322
323 // Build initial tree
324 let storage = Arc::new(MemoryBlockStore::new());
325 let mut mst = Mst::new(storage);
326
327 for key in &fixture.keys {
328 mst = mst.add(key, leaf_cid).await.unwrap();
329 }
330
331 // Verify before state
332 let root_before = mst.root().await.unwrap();
333 let expected_before: cid::Cid = fixture.root_before_commit.parse().unwrap();
334 assert_eq!(root_before.to_string(), expected_before.to_string());
335
336 // Build batch operations
337 use smol_str::SmolStr;
338
339 let mut ops = Vec::new();
340
341 // Note: adds in commit fixtures might include keys that already exist
342 // In that case we should use Update instead of Create
343 for key in &fixture.adds {
344 // Check if key already exists
345 if mst.get(key).await.unwrap().is_some() {
346 // Update existing key
347 ops.push(VerifiedWriteOp::Update {
348 key: SmolStr::new(key),
349 cid: leaf_cid,
350 prev: leaf_cid, // Same CID since we're using uniform leaf values
351 });
352 } else {
353 // Create new key
354 ops.push(VerifiedWriteOp::Create {
355 key: SmolStr::new(key),
356 cid: leaf_cid,
357 });
358 }
359 }
360
361 for key in &fixture.dels {
362 ops.push(VerifiedWriteOp::Delete {
363 key: SmolStr::new(key),
364 prev: leaf_cid, // We know the value from the fixture
365 });
366 }
367
368 // Apply batch
369 mst = mst.batch(&ops).await.unwrap();
370
371 // Verify after state
372 let root_after = mst.root().await.unwrap();
373 let expected_after: cid::Cid = fixture.root_after_commit.parse().unwrap();
374
375 assert_eq!(
376 root_after.to_string(),
377 expected_after.to_string(),
378 "Root CID mismatch after batch ops (fixture: {})",
379 fixture.comment
380 );
381
382 println!("✓ Passed (batch): {}", fixture.comment);
383 }
384}
385
386#[tokio::test]
387async fn test_commit_proof_diff_validation() {
388 // Verify that diff calculation matches the expected adds/dels from fixtures
389 let json = include_str!("fixtures/commit_proof.json");
390 let fixtures: Vec<CommitProofFixture> =
391 serde_ipld_dagjson::from_slice(json.as_bytes()).unwrap();
392
393 for fixture in fixtures {
394 println!("\n=== Testing diff: {} ===", fixture.comment);
395
396 let leaf_cid: cid::Cid = fixture.leaf_value.parse().unwrap();
397
398 // Build "before" tree
399 let storage_before = Arc::new(MemoryBlockStore::new());
400 let mut mst_before = Mst::new(storage_before);
401 for key in &fixture.keys {
402 mst_before = mst_before.add(key, leaf_cid).await.unwrap();
403 }
404
405 // Build "after" tree
406 let storage_after = Arc::new(MemoryBlockStore::new());
407 let mut mst_after = Mst::new(storage_after);
408
409 // Start with same keys
410 for key in &fixture.keys {
411 mst_after = mst_after.add(key, leaf_cid).await.unwrap();
412 }
413
414 // Apply ops to after tree
415 for key in &fixture.adds {
416 mst_after = mst_after.add(key, leaf_cid).await.unwrap();
417 }
418 for key in &fixture.dels {
419 mst_after = mst_after.delete(key).await.unwrap();
420 }
421
422 // Compute diff
423 let diff = mst_before.diff(&mst_after).await.unwrap();
424
425 // Verify diff matches expected operations
426 println!(
427 " Diff: {} creates, {} updates, {} deletes",
428 diff.creates.len(),
429 diff.updates.len(),
430 diff.deletes.len()
431 );
432 println!(
433 " Expected: {} adds, {} dels",
434 fixture.adds.len(),
435 fixture.dels.len()
436 );
437
438 // Creates should match adds (keys not in original tree)
439 let added_keys: std::collections::HashSet<_> =
440 fixture.adds.iter().map(|s| s.as_str()).collect();
441 let _deleted_keys: std::collections::HashSet<_> =
442 fixture.dels.iter().map(|s| s.as_str()).collect();
443 let original_keys: std::collections::HashSet<_> =
444 fixture.keys.iter().map(|s| s.as_str()).collect();
445
446 // Compute expected creates (adds that weren't in original)
447 let expected_creates: Vec<_> = added_keys.difference(&original_keys).map(|s| *s).collect();
448
449 // Compute expected updates (adds that WERE in original - replacing same CID)
450 let expected_updates: Vec<_> = added_keys
451 .intersection(&original_keys)
452 .map(|s| *s)
453 .collect();
454
455 println!(" Expected creates: {}", expected_creates.len());
456 println!(" Expected updates: {}", expected_updates.len());
457
458 // Total ops should match
459 let total_diff_ops = diff.creates.len() + diff.updates.len() + diff.deletes.len();
460 let total_expected_ops = fixture.adds.len() + fixture.dels.len();
461
462 assert_eq!(
463 total_diff_ops, total_expected_ops,
464 "Total operations mismatch in diff (fixture: {})",
465 fixture.comment
466 );
467
468 println!("✓ Passed diff: {}", fixture.comment);
469 }
470}
471
472#[tokio::test]
473async fn test_commit_proof_incremental_cids() {
474 // Show CID after each key insertion to find where we diverge
475 let json = include_str!("fixtures/commit_proof.json");
476 let fixtures: Vec<CommitProofFixture> =
477 serde_ipld_dagjson::from_slice(json.as_bytes()).unwrap();
478
479 let fixture = &fixtures[0]; // "two deep split"
480 println!("\n=== {} ===", fixture.comment);
481 println!("Expected final CID: {}", fixture.root_before_commit);
482
483 let leaf_cid: cid::Cid = fixture.leaf_value.parse().unwrap();
484 println!("Leaf value CID: {}", leaf_cid);
485
486 let storage = Arc::new(MemoryBlockStore::new());
487 let mut mst = Mst::new(storage);
488
489 for (i, key) in fixture.keys.iter().enumerate() {
490 mst = mst.add(key, leaf_cid).await.unwrap();
491 let root = mst.root().await.unwrap();
492 println!("After adding key {}: {} -> root CID: {}", i, key, root);
493 }
494
495 println!("\nFinal root CID: {}", mst.root().await.unwrap());
496 println!("Expected: {}", fixture.root_before_commit);
497}
498
499#[tokio::test]
500async fn test_rsky_simple_case() {
501 // From rsky's "handle_new_layers_that_are_two_higher_than_existing" test
502 // Simple case: 2 keys at layer 0
503 let cid1: cid::Cid = "bafyreie5cvv4h45feadgeuwhbcutmh6t2ceseocckahdoe6uat64zmz454"
504 .parse()
505 .unwrap();
506 let storage = Arc::new(MemoryBlockStore::new());
507 let mut mst = Mst::new(storage);
508
509 // Add A (layer 0)
510 mst = mst
511 .add("com.example.record/3jqfcqzm3ft2j", cid1)
512 .await
513 .unwrap();
514 println!("After A: {}", mst.root().await.unwrap());
515
516 // Add C (layer 0)
517 mst = mst
518 .add("com.example.record/3jqfcqzm3fz2j", cid1)
519 .await
520 .unwrap();
521
522 let root = mst.root().await.unwrap();
523 let expected = "bafyreidfcktqnfmykz2ps3dbul35pepleq7kvv526g47xahuz3rqtptmky";
524
525 println!("Our CID: {}", root);
526 println!("Expected CID: {}", expected);
527
528 assert_eq!(
529 root.to_string(),
530 expected,
531 "CID mismatch for simple 2-key tree"
532 );
533}
534
535#[tokio::test]
536async fn test_real_repo_car_roundtrip() {
537 use jacquard_repo::car::{read_car, write_car};
538 use std::path::Path;
539 use tempfile::NamedTempFile;
540
541 // Check if fixture exists (local only - not in CI)
542 let fixture_path = Path::new(concat!(
543 env!("CARGO_MANIFEST_DIR"),
544 "/tests/fixtures/repo-nonbinary.computer-2025-10-21T13_05_55.090Z.car"
545 ));
546
547 if !fixture_path.exists() {
548 eprintln!("⚠️ Skipping test_real_repo_car_roundtrip - fixture not present");
549 eprintln!(" (This is expected in CI - test only runs locally)");
550 return;
551 }
552
553 println!("✓ Found real repo CAR fixture");
554
555 // Read the CAR file
556 let blocks = read_car(fixture_path)
557 .await
558 .expect("Failed to read CAR file");
559 println!("✓ Loaded {} blocks from CAR", blocks.len());
560
561 assert!(!blocks.is_empty(), "CAR file should contain blocks");
562
563 // Write to a temp file
564 let temp_file = NamedTempFile::new().unwrap();
565
566 // Note: We can't easily extract the original roots without parsing the CAR header
567 // For now, just use the first block's CID as the root (if it exists)
568 let roots: Vec<_> = blocks.keys().take(1).copied().collect();
569
570 write_car(temp_file.path(), roots.clone(), blocks.clone())
571 .await
572 .expect("Failed to write CAR file");
573 println!("✓ Wrote CAR to temp file");
574
575 // Read it back
576 let blocks_roundtrip = read_car(temp_file.path())
577 .await
578 .expect("Failed to read roundtrip CAR");
579 println!(
580 "✓ Read {} blocks from roundtrip CAR",
581 blocks_roundtrip.len()
582 );
583
584 // Verify all blocks match
585 assert_eq!(
586 blocks.len(),
587 blocks_roundtrip.len(),
588 "Block count mismatch after roundtrip"
589 );
590
591 for (cid, data) in &blocks {
592 let roundtrip_data = blocks_roundtrip
593 .get(cid)
594 .expect(&format!("Missing block after roundtrip: {}", cid));
595 assert_eq!(data, roundtrip_data, "Block data mismatch for CID: {}", cid);
596 }
597
598 println!("✓ All {} blocks match after roundtrip", blocks.len());
599}
600
601#[tokio::test]
602async fn test_real_repo_car_streaming() {
603 use jacquard_repo::car::stream_car;
604 use std::path::Path;
605
606 let fixture_path = Path::new(concat!(
607 env!("CARGO_MANIFEST_DIR"),
608 "/tests/fixtures/repo-nonbinary.computer-2025-10-21T13_05_55.090Z.car"
609 ));
610
611 if !fixture_path.exists() {
612 eprintln!("⚠️ Skipping test_real_repo_car_streaming - fixture not present");
613 return;
614 }
615
616 let mut stream = stream_car(fixture_path)
617 .await
618 .expect("Failed to create CAR stream");
619
620 println!("✓ Created CAR stream");
621 println!(" Roots: {:?}", stream.roots());
622
623 let mut block_count = 0;
624 while let Some((cid, data)) = stream.next().await.expect("Stream error") {
625 block_count += 1;
626 if block_count <= 5 {
627 println!(" Block {}: {} ({} bytes)", block_count, cid, data.len());
628 }
629 }
630
631 println!("✓ Streamed {} blocks total", block_count);
632 assert!(block_count > 0, "Should have streamed at least one block");
633}
634
635#[tokio::test]
636async fn test_real_repo_mst_structure() {
637 use jacquard_repo::car::read_car;
638 use jacquard_repo::mst::tree::Mst;
639 use jacquard_repo::storage::memory::MemoryBlockStore;
640 use std::path::Path;
641
642 let fixture_path = Path::new(concat!(
643 env!("CARGO_MANIFEST_DIR"),
644 "/tests/fixtures/repo-nonbinary.computer-2025-10-21T13_05_55.090Z.car"
645 ));
646
647 if !fixture_path.exists() {
648 eprintln!("⚠️ Skipping test_real_repo_mst_structure - fixture not present");
649 return;
650 }
651
652 println!("✓ Loading real repo CAR file");
653
654 // Read CAR and load into storage
655 let blocks = read_car(fixture_path).await.expect("Failed to read CAR");
656 println!("✓ Loaded {} blocks", blocks.len());
657
658 let storage = Arc::new(MemoryBlockStore::new());
659
660 // Load all blocks into storage
661 let mut block_vec = Vec::new();
662 for (cid, data) in blocks.iter() {
663 block_vec.push((*cid, data.clone()));
664 }
665 storage
666 .put_many(block_vec)
667 .await
668 .expect("Failed to store blocks");
669 println!("✓ Loaded all blocks into storage");
670
671 // Get roots from CAR header
672 let roots = jacquard_repo::car::read_car_header(fixture_path)
673 .await
674 .expect("Failed to read header");
675
676 assert!(!roots.is_empty(), "CAR should have at least one root");
677 let commit_cid = roots[0];
678 println!("✓ Commit CID: {}", commit_cid);
679
680 // Parse commit to get MST root
681 #[derive(serde::Deserialize)]
682 struct Commit {
683 data: cid::Cid,
684 // We only care about the data field (MST root)
685 }
686
687 let commit_bytes = storage
688 .get(&commit_cid)
689 .await
690 .expect("Failed to get commit")
691 .expect("Commit not found");
692
693 let commit: Commit =
694 serde_ipld_dagcbor::from_slice(&commit_bytes).expect("Failed to parse commit");
695
696 let mst_root = commit.data;
697 println!("✓ MST root CID: {}", mst_root);
698
699 // Load MST
700 let mst = Mst::load(storage.clone(), mst_root, None);
701 println!("✓ Loaded MST from storage");
702
703 // Verify we can get the root CID
704 let root_cid = mst.root().await.expect("Failed to get root CID");
705 assert_eq!(root_cid, mst_root, "MST root CID should match");
706 println!("✓ MST root CID matches");
707
708 // Get all leaves to verify tree structure
709 let leaves = mst.leaves().await.expect("Failed to get leaves");
710 println!("✓ MST contains {} leaf entries", leaves.len());
711
712 assert!(!leaves.is_empty(), "MST should have at least one leaf");
713
714 // Verify leaves are in lexicographic order
715 for i in 1..leaves.len() {
716 let prev_key = &leaves[i - 1].0;
717 let curr_key = &leaves[i].0;
718 assert!(
719 prev_key < curr_key,
720 "Leaves should be in lexicographic order: {:?} >= {:?}",
721 prev_key,
722 curr_key
723 );
724 }
725 println!("✓ All leaves are in lexicographic order");
726
727 // Test get operation on first few keys
728 for (i, (key, expected_cid)) in leaves.iter().take(10).enumerate() {
729 let retrieved = mst.get(key).await.expect("Failed to get key");
730 assert_eq!(
731 retrieved,
732 Some(*expected_cid),
733 "Get operation failed for key {}: {}",
734 i,
735 key
736 );
737 }
738 println!("✓ Get operations work correctly on sampled keys");
739
740 // Verify all leaves are retrievable via get
741 println!(" Verifying all {} keys are retrievable...", leaves.len());
742 for (key, expected_cid) in &leaves {
743 let retrieved = mst.get(key).await.expect("Failed to get key");
744 assert_eq!(
745 retrieved,
746 Some(*expected_cid),
747 "Get operation failed for key: {}",
748 key
749 );
750 }
751 println!("✓ All {} keys are retrievable via get()", leaves.len());
752}
753
754#[tokio::test]
755async fn test_real_repo_mst_operations() {
756 use jacquard_repo::car::read_car;
757 use jacquard_repo::mst::tree::Mst;
758 use jacquard_repo::storage::memory::MemoryBlockStore;
759 use std::path::Path;
760
761 let fixture_path = Path::new(concat!(
762 env!("CARGO_MANIFEST_DIR"),
763 "/tests/fixtures/repo-nonbinary.computer-2025-10-21T13_05_55.090Z.car"
764 ));
765
766 if !fixture_path.exists() {
767 eprintln!("⚠️ Skipping test_real_repo_mst_operations - fixture not present");
768 return;
769 }
770
771 // Load CAR and set up storage
772 let blocks = read_car(fixture_path).await.expect("Failed to read CAR");
773 let storage = Arc::new(MemoryBlockStore::new());
774
775 let mut block_vec = Vec::new();
776 for (cid, data) in blocks.iter() {
777 block_vec.push((*cid, data.clone()));
778 }
779 storage
780 .put_many(block_vec)
781 .await
782 .expect("Failed to store blocks");
783
784 // Get MST root
785 let roots = jacquard_repo::car::read_car_header(fixture_path)
786 .await
787 .expect("Failed to read header");
788 let commit_cid = roots[0];
789
790 #[derive(serde::Deserialize)]
791 struct Commit {
792 data: cid::Cid,
793 }
794
795 let commit_bytes = storage.get(&commit_cid).await.unwrap().unwrap();
796 let commit: Commit = serde_ipld_dagcbor::from_slice(&commit_bytes).unwrap();
797 let mst_root = commit.data;
798
799 // Load original MST
800 let original_mst = Mst::load(storage.clone(), mst_root, None);
801 let original_leaves = original_mst.leaves().await.expect("Failed to get leaves");
802 println!("✓ Loaded MST with {} leaves", original_leaves.len());
803
804 // Test adding a new key
805 fn test_cid(n: u8) -> cid::Cid {
806 let data = vec![n; 32];
807 let mh = multihash::Multihash::wrap(SHA2_256, &data).unwrap();
808 cid::Cid::new_v1(DAG_CBOR_CID_CODEC, mh)
809 }
810
811 let new_key = "app.bsky.feed.post/zzztestkey123";
812 let modified_mst = original_mst
813 .add(new_key, test_cid(99))
814 .await
815 .expect("Failed to add key");
816
817 // Verify new key exists
818 assert_eq!(
819 modified_mst.get(new_key).await.unwrap(),
820 Some(test_cid(99)),
821 "New key should be retrievable"
822 );
823 println!("✓ Successfully added new key to MST");
824
825 // Verify old keys still exist
826 for (key, cid) in original_leaves.iter().take(10) {
827 assert_eq!(
828 modified_mst.get(key).await.unwrap(),
829 Some(*cid),
830 "Original keys should still be retrievable"
831 );
832 }
833 println!("✓ Original keys still retrievable after add");
834
835 // Test that modified MST has one more leaf
836 let modified_leaves = modified_mst.leaves().await.unwrap();
837 assert_eq!(
838 modified_leaves.len(),
839 original_leaves.len() + 1,
840 "Modified MST should have one more leaf"
841 );
842 println!("✓ Modified MST has correct leaf count");
843
844 // Test deleting a key
845 if let Some((key_to_delete, _)) = original_leaves.first() {
846 let mst_after_delete = modified_mst
847 .delete(key_to_delete)
848 .await
849 .expect("Failed to delete key");
850
851 assert_eq!(
852 mst_after_delete.get(key_to_delete).await.unwrap(),
853 None,
854 "Deleted key should not be retrievable"
855 );
856 println!("✓ Successfully deleted key from MST");
857
858 // Verify other keys still exist
859 for (key, cid) in original_leaves.iter().skip(1).take(10) {
860 assert_eq!(
861 mst_after_delete.get(key).await.unwrap(),
862 Some(*cid),
863 "Other keys should still be retrievable after delete"
864 );
865 }
866 println!("✓ Other keys still retrievable after delete");
867 }
868}
869
870#[tokio::test]
871async fn test_real_repo_mst_determinism() {
872 use jacquard_repo::car::read_car;
873 use jacquard_repo::mst::tree::Mst;
874 use jacquard_repo::storage::memory::MemoryBlockStore;
875 use std::path::Path;
876
877 let fixture_path = Path::new(concat!(
878 env!("CARGO_MANIFEST_DIR"),
879 "/tests/fixtures/repo-nonbinary.computer-2025-10-21T13_05_55.090Z.car"
880 ));
881
882 if !fixture_path.exists() {
883 eprintln!("⚠️ Skipping test_real_repo_mst_determinism - fixture not present");
884 return;
885 }
886
887 // Load CAR and set up storage
888 let blocks = read_car(fixture_path).await.expect("Failed to read CAR");
889 let storage = Arc::new(MemoryBlockStore::new());
890
891 storage
892 .put_many(blocks)
893 .await
894 .expect("Failed to store blocks");
895
896 // Get MST root and leaves
897 let roots = jacquard_repo::car::read_car_header(fixture_path)
898 .await
899 .expect("Failed to read header");
900 let commit_cid = roots[0];
901
902 #[derive(serde::Deserialize)]
903 struct Commit {
904 data: cid::Cid,
905 }
906
907 let commit_bytes = storage.get(&commit_cid).await.unwrap().unwrap();
908 let commit: Commit = serde_ipld_dagcbor::from_slice(&commit_bytes).unwrap();
909 let original_mst_root = commit.data;
910
911 let original_mst = Mst::load(storage.clone(), original_mst_root, None);
912 let leaves = original_mst.leaves().await.expect("Failed to get leaves");
913 println!(
914 "✓ Loaded MST with {} leaves for determinism test",
915 leaves.len()
916 );
917
918 // Take first 100 keys and rebuild tree in different order
919 let test_leaves: Vec<_> = leaves.iter().take(100).cloned().collect();
920 println!(" Testing determinism with {} keys", test_leaves.len());
921
922 // Build tree in original order
923 let storage1 = Arc::new(MemoryBlockStore::new());
924 let mut mst1 = Mst::new(storage1);
925 for (key, cid) in &test_leaves {
926 mst1 = mst1.add(key, *cid).await.unwrap();
927 }
928 let cid1 = mst1.root().await.unwrap();
929
930 // Build tree in reverse order
931 let storage2 = Arc::new(MemoryBlockStore::new());
932 let mut mst2 = Mst::new(storage2);
933 for (key, cid) in test_leaves.iter().rev() {
934 mst2 = mst2.add(key, *cid).await.unwrap();
935 }
936 let cid2 = mst2.root().await.unwrap();
937
938 println!(" MST1 root: {}", cid1);
939 println!(" MST2 root: {}", cid2);
940
941 // Verify all keys are present in both trees
942 for (key, expected_cid) in &test_leaves {
943 let v1 = mst1.get(key).await.unwrap();
944 let v2 = mst2.get(key).await.unwrap();
945
946 assert_eq!(
947 v1,
948 Some(*expected_cid),
949 "Key should be retrievable from mst1: {}",
950 key
951 );
952 assert_eq!(
953 v2,
954 Some(*expected_cid),
955 "Key should be retrievable from mst2: {}",
956 key
957 );
958 }
959 println!("✓ All keys retrievable from both trees");
960
961 // Check if root CIDs match (determinism test)
962 assert_eq!(
963 cid1, cid2,
964 "Tree structure must be deterministic - root CIDs should match"
965 );
966 println!("✓ Root CIDs match - tree structure is deterministic!");
967}