1use sha2::{Digest, Sha256};
11
12use crate::{q_hash, NQuin};
13
14pub const BRANCHES_CONTEXT: u64 = q_hash("urn:qualia:context:branches");
18const P_BRANCH_TIP: u64 = q_hash("urn:qualia:dag:branchTip");
20#[allow(dead_code)]
22const P_PARENT: u64 = q_hash("urn:qualia:dag:parent");
23
24pub const FORK_DISPUTED: u32 = 0x0001;
26pub const GENESIS: u32 = 0x0002;
28pub const MERGE_SECONDARY: u32 = 0x0008;
35
36#[repr(C)]
50#[derive(Clone, Copy, Debug, PartialEq, Eq)]
51pub struct DagNode {
52 pub parent_hash: [u8; 32],
54 pub quins_merkle: [u8; 32],
56 pub author_did: u64,
58 pub timestamp: u64,
60 pub message_hash: u32,
62 pub flags: u32,
64}
65
66const _: () = assert!(
67 std::mem::size_of::<DagNode>() == 88,
68 "DagNode must be exactly 88 bytes"
69);
70
71impl DagNode {
72 pub fn digest(&self) -> [u8; 32] {
74 let mut h = Sha256::new();
75 h.update(self.parent_hash);
76 h.update(self.quins_merkle);
77 h.update(self.author_did.to_le_bytes());
78 h.update(self.timestamp.to_le_bytes());
79 h.update(self.message_hash.to_le_bytes());
80 h.update(self.flags.to_le_bytes());
81 h.finalize().into()
82 }
83
84 pub fn to_bytes(&self) -> [u8; 88] {
86 let mut b = [0u8; 88];
87 b[0..32].copy_from_slice(&self.parent_hash);
88 b[32..64].copy_from_slice(&self.quins_merkle);
89 b[64..72].copy_from_slice(&self.author_did.to_le_bytes());
90 b[72..80].copy_from_slice(&self.timestamp.to_le_bytes());
91 b[80..84].copy_from_slice(&self.message_hash.to_le_bytes());
92 b[84..88].copy_from_slice(&self.flags.to_le_bytes());
93 b
94 }
95
96 pub fn from_bytes(b: &[u8; 88]) -> Self {
98 DagNode {
99 parent_hash: b[0..32].try_into().unwrap(),
100 quins_merkle: b[32..64].try_into().unwrap(),
101 author_did: u64::from_le_bytes(b[64..72].try_into().unwrap()),
102 timestamp: u64::from_le_bytes(b[72..80].try_into().unwrap()),
103 message_hash: u32::from_le_bytes(b[80..84].try_into().unwrap()),
104 flags: u32::from_le_bytes(b[84..88].try_into().unwrap()),
105 }
106 }
107}
108
109pub fn quins_merkle(quins: &[NQuin]) -> [u8; 32] {
113 let mut h = Sha256::new();
114 for q in quins {
115 h.update(q.subject.to_le_bytes());
116 h.update(q.predicate.to_le_bytes());
117 h.update(q.object.to_le_bytes());
118 h.update(q.context.to_le_bytes());
119 }
120 h.finalize().into()
121}
122
123pub struct DagStore {
128 nodes: Vec<(DagNode, [u8; 32])>, branches: std::collections::HashMap<u64, [u8; 32]>, }
131
132impl DagStore {
133 pub fn new() -> Self {
135 Self {
136 nodes: Vec::new(),
137 branches: std::collections::HashMap::new(),
138 }
139 }
140
141 pub fn genesis_node(
143 &mut self,
144 quins: &[NQuin],
145 author_did: u64,
146 timestamp_ms: u64,
147 message: &str,
148 ) -> [u8; 32] {
149 let node = DagNode {
150 parent_hash: [0u8; 32],
151 quins_merkle: quins_merkle(quins),
152 author_did,
153 timestamp: timestamp_ms,
154 message_hash: q_hash(message) as u32,
155 flags: GENESIS,
156 };
157 let hash = node.digest();
158 self.nodes.push((node, hash));
159 hash
160 }
161
162 pub fn commit_node(
164 &mut self,
165 parent_hash: [u8; 32],
166 quins: &[NQuin],
167 author_did: u64,
168 timestamp_ms: u64,
169 message: &str,
170 ) -> [u8; 32] {
171 let node = DagNode {
172 parent_hash,
173 quins_merkle: quins_merkle(quins),
174 author_did,
175 timestamp: timestamp_ms,
176 message_hash: q_hash(message) as u32,
177 flags: 0,
178 };
179 let hash = node.digest();
180 self.nodes.push((node, hash));
181 hash
182 }
183
184 pub fn fork_node(
187 &mut self,
188 disputed_hash: [u8; 32],
189 quins: &[NQuin],
190 author_did: u64,
191 timestamp_ms: u64,
192 message: &str,
193 ) -> [u8; 32] {
194 let node = DagNode {
195 parent_hash: disputed_hash,
196 quins_merkle: quins_merkle(quins),
197 author_did,
198 timestamp: timestamp_ms,
199 message_hash: q_hash(message) as u32,
200 flags: FORK_DISPUTED,
201 };
202 let hash = node.digest();
203 self.nodes.push((node, hash));
204 hash
205 }
206
207 pub fn write_branch_pointer(&mut self, branch_name: &str, tip_hash: [u8; 32]) -> NQuin {
210 let name_hash = q_hash(branch_name);
211 self.branches.insert(name_hash, tip_hash);
212 let tip_lo = u64::from_le_bytes(tip_hash[0..8].try_into().unwrap());
214 let tip_hi = u64::from_le_bytes(tip_hash[8..16].try_into().unwrap());
215 let folded = tip_lo ^ tip_hi;
216 NQuin {
217 subject: name_hash,
218 predicate: P_BRANCH_TIP,
219 object: folded,
220 context: BRANCHES_CONTEXT,
221 metadata: 0,
222 parity: 0,
223 }
224 }
225
226 pub fn merge_node(
236 &mut self,
237 primary_parent: [u8; 32],
238 secondary_parent: [u8; 32],
239 quins: &[NQuin],
240 author_did: u64,
241 timestamp_ms: u64,
242 message: &str,
243 ) -> ([u8; 32], [u8; 32]) {
244 let msg_hash = q_hash(message) as u32;
245 let merkle = quins_merkle(quins);
246
247 let primary = DagNode {
248 parent_hash: primary_parent,
249 quins_merkle: merkle,
250 author_did,
251 timestamp: timestamp_ms,
252 message_hash: msg_hash,
253 flags: 0,
254 };
255 let primary_hash = primary.digest();
256 self.nodes.push((primary, primary_hash));
257
258 let secondary = DagNode {
260 parent_hash: secondary_parent,
261 quins_merkle: primary_hash,
262 author_did,
263 timestamp: timestamp_ms,
264 message_hash: msg_hash,
265 flags: MERGE_SECONDARY,
266 };
267 let secondary_hash = secondary.digest();
268 self.nodes.push((secondary, secondary_hash));
269
270 (primary_hash, secondary_hash)
271 }
272
273 pub fn nodes_as_of(&self, as_of_ms: u64) -> Vec<[u8; 32]> {
278 self.nodes
279 .iter()
280 .filter(|(n, _)| n.timestamp <= as_of_ms)
281 .map(|(_, h)| *h)
282 .collect()
283 }
284
285 pub fn branch_tip(&self, branch_name: &str) -> Option<[u8; 32]> {
287 self.branches.get(&q_hash(branch_name)).copied()
288 }
289
290 pub fn nodes(&self) -> &[(DagNode, [u8; 32])] {
292 &self.nodes
293 }
294
295 pub fn serialize(&self) -> Vec<u8> {
298 let mut out = Vec::with_capacity(8 + self.nodes.len() * 88);
299 out.extend_from_slice(&(self.nodes.len() as u64).to_le_bytes());
300 for (node, _hash) in &self.nodes {
301 out.extend_from_slice(&node.to_bytes());
302 }
303 out
304 }
305
306 pub fn deserialize(bytes: &[u8]) -> Option<Self> {
308 if bytes.len() < 8 {
309 return None;
310 }
311 let count = u64::from_le_bytes(bytes[0..8].try_into().ok()?) as usize;
312 if bytes.len() < 8 + count * 88 {
313 return None;
314 }
315 let mut nodes = Vec::with_capacity(count);
316 for i in 0..count {
317 let off = 8 + i * 88;
318 let b: &[u8; 88] = bytes[off..off + 88].try_into().ok()?;
319 let node = DagNode::from_bytes(b);
320 let hash = node.digest();
321 nodes.push((node, hash));
322 }
323 Some(Self {
324 nodes,
325 branches: std::collections::HashMap::new(),
326 })
327 }
328}
329
330impl Default for DagStore {
331 fn default() -> Self {
332 Self::new()
333 }
334}
335
336pub fn generate_fast_export_stream(store: &DagStore) -> String {
343 if store.nodes.is_empty() {
344 return legacy_fast_export();
345 }
346
347 let mut stream = String::new();
348 for (idx, (node, hash)) in store.nodes.iter().enumerate() {
349 let mark = idx + 1;
350 let hash_hex = hex::encode(hash);
351 let ts_secs = node.timestamp / 1000;
352 stream.push_str(&format!("commit refs/heads/main\nmark :{mark}\n"));
353 stream.push_str(&format!(
354 "committer unknown <did:key:{hash_hex}> {ts_secs} +0000\n"
355 ));
356 let msg = format!("quin commit {}\n", hex::encode(&node.quins_merkle[..8]));
357 stream.push_str(&format!("data {}\n{msg}", msg.len()));
358 if node.flags & FORK_DISPUTED != 0 {
359 stream.push_str("# flags: FORK_DISPUTED\n");
360 }
361 let blob = format!(
362 "{{\"quins_merkle\":\"{}\",\"author_did\":{},\"flags\":{}}}",
363 hex::encode(node.quins_merkle),
364 node.author_did,
365 node.flags,
366 );
367 stream.push_str(&format!(
368 "M 100644 inline dag_node_{mark}.json\ndata {}\n{blob}\n",
369 blob.len()
370 ));
371 }
372 stream
373}
374
375fn legacy_fast_export() -> String {
376 let blob = "{\"financial\": 1200.00, \"labor_hours\": 45}";
377 format!(
378 "commit refs/heads/main\nmark :1\n\
379 committer Alice <alice@did.key> 1717286400 +0000\n\
380 data 36\nLog 4 hours of design obligation\n\
381 M 100644 inline obligation_matrix.json\ndata {}\n{blob}\n",
382 blob.len()
383 )
384}
385
386pub fn generate_fast_export_stream_for_project(_project_id: &str) -> String {
389 generate_fast_export_stream(&DagStore::new())
390}
391
392#[cfg(test)]
393mod tests {
394 use super::*;
395
396 #[test]
397 fn genesis_commit_roundtrip() {
398 let mut store = DagStore::new();
399 let quins: Vec<NQuin> = Vec::new();
400 let hash = store.genesis_node(&quins, 0xDEAD_BEEF, 1_717_286_400_000, "genesis");
401 assert_ne!(hash, [0u8; 32]);
402 assert_eq!(store.nodes().len(), 1);
403 assert_eq!(store.nodes()[0].0.flags, GENESIS);
404 }
405
406 #[test]
407 fn chain_commit_and_fork() {
408 let mut store = DagStore::new();
409 let genesis = store.genesis_node(&[], 1, 1000, "init");
410 let c1 = store.commit_node(genesis, &[], 1, 2000, "add data");
411 let fork = store.fork_node(c1, &[], 2, 3000, "contested");
412 assert_eq!(store.nodes().len(), 3);
413 assert_eq!(store.nodes()[2].0.flags, FORK_DISPUTED);
414 assert_eq!(store.nodes()[2].0.parent_hash, c1);
415 let _ = fork;
416 }
417
418 #[test]
419 fn branch_pointer_is_retrievable() {
420 let mut store = DagStore::new();
421 let genesis = store.genesis_node(&[], 1, 1000, "init");
422 let quin = store.write_branch_pointer("main", genesis);
423 assert_eq!(quin.context, BRANCHES_CONTEXT);
424 assert!(store.branch_tip("main").is_some());
425 }
426
427 #[test]
428 fn serialize_deserialize_roundtrip() {
429 let mut store = DagStore::new();
430 store.genesis_node(&[], 42, 999, "first");
431 let bytes = store.serialize();
432 let restored = DagStore::deserialize(&bytes).expect("deser failed");
433 assert_eq!(restored.nodes().len(), 1);
434 assert_eq!(restored.nodes()[0].1, store.nodes()[0].1);
435 }
436
437 #[test]
438 fn merge_node_produces_two_linked_nodes() {
439 let mut store = DagStore::new();
440 let branch_a = store.genesis_node(&[], 1, 1000, "branch-a init");
441 let branch_b = store.genesis_node(&[], 2, 2000, "branch-b init");
442
443 let (primary, secondary) = store.merge_node(branch_a, branch_b, &[], 1, 3000, "merge");
444
445 assert_ne!(primary, secondary);
446 assert_ne!(primary, [0u8; 32]);
447 assert_ne!(secondary, [0u8; 32]);
448
449 let primary_node = store.nodes().iter().find(|(_, h)| *h == primary).unwrap().0;
451 assert_eq!(primary_node.parent_hash, branch_a);
452 assert_eq!(primary_node.flags, 0);
453
454 let secondary_node = store
456 .nodes()
457 .iter()
458 .find(|(_, h)| *h == secondary)
459 .unwrap()
460 .0;
461 assert_eq!(secondary_node.parent_hash, branch_b);
462 assert_eq!(secondary_node.flags, MERGE_SECONDARY);
463 assert_eq!(secondary_node.quins_merkle, primary);
464 }
465
466 #[test]
467 fn nodes_as_of_filters_by_timestamp() {
468 let mut store = DagStore::new();
469 store.genesis_node(&[], 1, 1000, "t=1000");
470 store.commit_node([0u8; 32], &[], 1, 5000, "t=5000");
471 store.commit_node([0u8; 32], &[], 1, 9000, "t=9000");
472
473 let snapshot = store.nodes_as_of(5000);
474 assert_eq!(snapshot.len(), 2, "should include nodes at t≤5000");
475
476 let full = store.nodes_as_of(u64::MAX);
477 assert_eq!(full.len(), 3);
478 }
479
480 #[test]
481 fn dag_node_size() {
482 assert_eq!(std::mem::size_of::<DagNode>(), 88);
483 }
484
485 #[test]
486 fn fast_export_uses_real_nodes() {
487 let mut store = DagStore::new();
488 store.genesis_node(&[], 7, 1_000_000, "test commit");
489 let export = generate_fast_export_stream(&store);
490 assert!(export.contains("commit refs/heads/main"));
491 assert!(export.contains("quins_merkle"));
492 }
493}