Skip to main content

qualia_core_db/platform/
git_bridge.rs

1//! Minimal Merkle-DAG for Q42 volume history (Phase 1 — §4.5 Option B).
2//!
3//! `DagNode` (88 bytes, `#[repr(C)]`) is the atomic commit unit.
4//! Branches are stored as BRANCHES_CONTEXT quins keyed on `q_hash(branch_name)`.
5//! Contestability forks create a new node with the `FORK_DISPUTED` flag.
6//!
7//! The fast-export stream produced by `generate_fast_export_stream` now iterates
8//! real DagNodes rather than returning a hardcoded stub.
9
10use sha2::{Digest, Sha256};
11
12use crate::{q_hash, NQuin};
13
14// ── Constants ─────────────────────────────────────────────────────────────────
15
16/// Named-graph context for branch pointer quins.
17pub const BRANCHES_CONTEXT: u64 = q_hash("urn:qualia:context:branches");
18/// Predicate: "this subject is the tip of branch X"
19const P_BRANCH_TIP: u64 = q_hash("urn:qualia:dag:branchTip");
20/// Predicate: "this subject has parent DAG node Y" — reserved for Phase 2 graph traversal.
21#[allow(dead_code)]
22const P_PARENT: u64 = q_hash("urn:qualia:dag:parent");
23
24/// Node flag: this node was created via a contestability fork.
25pub const FORK_DISPUTED: u32 = 0x0001;
26/// Node flag: genesis node (no parent).
27pub const GENESIS: u32 = 0x0002;
28/// Node flag: secondary-parent back-link in a merge commit.
29///
30/// A merge creates two nodes: the primary merge commit (`flags = 0`) and a
31/// secondary back-link node (`flags = MERGE_SECONDARY`), whose `quins_merkle`
32/// encodes the primary commit hash for bidirectional DAG traversal.
33/// Conflict quins should be written to `crate::provenance::CONTEST_CONTEXT`.
34pub const MERGE_SECONDARY: u32 = 0x0008;
35
36// ── DagNode ───────────────────────────────────────────────────────────────────
37
38/// 88-byte Merkle-DAG commit node.
39///
40/// Layout (32+32+8+8+4+4 = 88 bytes, all fields little-endian):
41/// ```text
42/// [0..32)   parent_hash     — SHA-256 of parent DagNode bytes; all-zero = genesis
43/// [32..64)  quins_merkle    — SHA-256 of the NQuin slice committed here
44/// [64..72)  author_did      — q_hash of the author's DID string (u64)
45/// [72..80)  timestamp       — ms since Unix epoch (u64)
46/// [80..84)  message_hash    — low 32 bits of q_hash of the commit message
47/// [84..88)  flags           — GENESIS | FORK_DISPUTED | ...
48/// ```
49#[repr(C)]
50#[derive(Clone, Copy, Debug, PartialEq, Eq)]
51pub struct DagNode {
52    /// SHA-256 of the parent node's bytes; `[0u8; 32]` for genesis.
53    pub parent_hash: [u8; 32],
54    /// SHA-256 of the quins slice this commit adds/removes.
55    pub quins_merkle: [u8; 32],
56    /// `q_hash` of the author's DID string.
57    pub author_did: u64,
58    /// Milliseconds since Unix epoch.
59    pub timestamp: u64,
60    /// Low 32 bits of `q_hash(message)` — enough for dedup/indexing.
61    pub message_hash: u32,
62    /// Node flags (`GENESIS`, `FORK_DISPUTED`, …).
63    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    /// Compute the SHA-256 digest of this node's canonical byte representation.
73    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    /// Serialize to 88 bytes (little-endian for numeric fields).
85    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    /// Deserialize from 88 bytes.
97    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
109// ── quins_merkle helper ───────────────────────────────────────────────────────
110
111/// Compute the SHA-256 Merkle root over a sorted slice of NQuins.
112pub 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
123// ── DagStore ─────────────────────────────────────────────────────────────────
124
125/// In-memory DAG node store.  Persisted to `dag_root_offset`/`dag_root_length`
126/// in the Q42 v3 volume header.
127pub struct DagStore {
128    nodes: Vec<(DagNode, [u8; 32])>,                    // (node, hash)
129    branches: std::collections::HashMap<u64, [u8; 32]>, // branch_name_hash → tip_hash
130}
131
132impl DagStore {
133    /// Creates a default `DagStore`.
134    pub fn new() -> Self {
135        Self {
136            nodes: Vec::new(),
137            branches: std::collections::HashMap::new(),
138        }
139    }
140
141    /// Create the genesis node (no parent).
142    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    /// Create a regular commit node chained from `parent_hash`.
163    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    /// Create a contestability fork from `disputed_hash`.
185    /// Marks the new node with `FORK_DISPUTED`.
186    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    /// Point `branch_name` at `tip_hash`.  Returns an NQuin encoding the pointer
208    /// for storage in BRANCHES_CONTEXT.
209    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        // Encode the tip hash as two u64s XOR-folded into the object field.
213        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    /// Create a merge node spanning two parent branches.
227    ///
228    /// Returns `(primary_hash, secondary_hash)`:
229    /// - `primary_hash`: the merge commit itself (`parent_hash = primary_parent`)
230    /// - `secondary_hash`: a MERGE_SECONDARY back-link node whose `quins_merkle`
231    ///   encodes `primary_hash` so the two branches stay bidirectionally linked
232    ///
233    /// Any conflict quins should be written to `crate::provenance::CONTEST_CONTEXT`
234    /// before or after calling this function.
235    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        // Secondary back-link: parent = secondary branch tip; quins_merkle = primary_hash.
259        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    /// Return all node hashes with `timestamp ≤ as_of_ms` (assertion-time snapshot).
274    ///
275    /// Used by the SPARQL AS OF executor to reconstruct which DAG commits existed
276    /// at a given point in time.
277    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    /// Return the current tip hash for `branch_name`, if set.
286    pub fn branch_tip(&self, branch_name: &str) -> Option<[u8; 32]> {
287        self.branches.get(&q_hash(branch_name)).copied()
288    }
289
290    /// Iterate nodes in insertion order.
291    pub fn nodes(&self) -> &[(DagNode, [u8; 32])] {
292        &self.nodes
293    }
294
295    /// Serialize the store to bytes for embedding in a Q42 volume.
296    /// Format: `[u64 node_count] ([u8;88] node_bytes)*`
297    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    /// Deserialize from bytes previously written by `serialize`.
307    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
336// ── git fast-export compatibility ─────────────────────────────────────────────
337
338/// Generate a `git fast-export` compatible text stream from the DAG store.
339///
340/// Called with a `DagStore` populated from the volume's `dag_root_offset` section.
341/// Falls back to a single placeholder commit when the store is empty (legacy behaviour).
342pub 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
386/// Convenience wrapper: generate fast-export from a bare project ID string.
387/// Creates an empty store and produces the legacy stream (backward-compatible shim).
388pub 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        // Primary node must have branch_a as its parent.
450        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        // Secondary node must have branch_b as parent and encode primary_hash in quins_merkle.
455        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}