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    pub fn new() -> Self {
134        Self {
135            nodes: Vec::new(),
136            branches: std::collections::HashMap::new(),
137        }
138    }
139
140    /// Create the genesis node (no parent).
141    pub fn genesis_node(
142        &mut self,
143        quins: &[NQuin],
144        author_did: u64,
145        timestamp_ms: u64,
146        message: &str,
147    ) -> [u8; 32] {
148        let node = DagNode {
149            parent_hash: [0u8; 32],
150            quins_merkle: quins_merkle(quins),
151            author_did,
152            timestamp: timestamp_ms,
153            message_hash: q_hash(message) as u32,
154            flags: GENESIS,
155        };
156        let hash = node.digest();
157        self.nodes.push((node, hash));
158        hash
159    }
160
161    /// Create a regular commit node chained from `parent_hash`.
162    pub fn commit_node(
163        &mut self,
164        parent_hash: [u8; 32],
165        quins: &[NQuin],
166        author_did: u64,
167        timestamp_ms: u64,
168        message: &str,
169    ) -> [u8; 32] {
170        let node = DagNode {
171            parent_hash,
172            quins_merkle: quins_merkle(quins),
173            author_did,
174            timestamp: timestamp_ms,
175            message_hash: q_hash(message) as u32,
176            flags: 0,
177        };
178        let hash = node.digest();
179        self.nodes.push((node, hash));
180        hash
181    }
182
183    /// Create a contestability fork from `disputed_hash`.
184    /// Marks the new node with `FORK_DISPUTED`.
185    pub fn fork_node(
186        &mut self,
187        disputed_hash: [u8; 32],
188        quins: &[NQuin],
189        author_did: u64,
190        timestamp_ms: u64,
191        message: &str,
192    ) -> [u8; 32] {
193        let node = DagNode {
194            parent_hash: disputed_hash,
195            quins_merkle: quins_merkle(quins),
196            author_did,
197            timestamp: timestamp_ms,
198            message_hash: q_hash(message) as u32,
199            flags: FORK_DISPUTED,
200        };
201        let hash = node.digest();
202        self.nodes.push((node, hash));
203        hash
204    }
205
206    /// Point `branch_name` at `tip_hash`.  Returns an NQuin encoding the pointer
207    /// for storage in BRANCHES_CONTEXT.
208    pub fn write_branch_pointer(&mut self, branch_name: &str, tip_hash: [u8; 32]) -> NQuin {
209        let name_hash = q_hash(branch_name);
210        self.branches.insert(name_hash, tip_hash);
211        // Encode the tip hash as two u64s XOR-folded into the object field.
212        let tip_lo = u64::from_le_bytes(tip_hash[0..8].try_into().unwrap());
213        let tip_hi = u64::from_le_bytes(tip_hash[8..16].try_into().unwrap());
214        let folded = tip_lo ^ tip_hi;
215        NQuin {
216            subject: name_hash,
217            predicate: P_BRANCH_TIP,
218            object: folded,
219            context: BRANCHES_CONTEXT,
220            metadata: 0,
221            parity: 0,
222        }
223    }
224
225    /// Create a merge node spanning two parent branches.
226    ///
227    /// Returns `(primary_hash, secondary_hash)`:
228    /// - `primary_hash`: the merge commit itself (`parent_hash = primary_parent`)
229    /// - `secondary_hash`: a MERGE_SECONDARY back-link node whose `quins_merkle`
230    ///   encodes `primary_hash` so the two branches stay bidirectionally linked
231    ///
232    /// Any conflict quins should be written to `crate::provenance::CONTEST_CONTEXT`
233    /// before or after calling this function.
234    pub fn merge_node(
235        &mut self,
236        primary_parent: [u8; 32],
237        secondary_parent: [u8; 32],
238        quins: &[NQuin],
239        author_did: u64,
240        timestamp_ms: u64,
241        message: &str,
242    ) -> ([u8; 32], [u8; 32]) {
243        let msg_hash = q_hash(message) as u32;
244        let merkle = quins_merkle(quins);
245
246        let primary = DagNode {
247            parent_hash: primary_parent,
248            quins_merkle: merkle,
249            author_did,
250            timestamp: timestamp_ms,
251            message_hash: msg_hash,
252            flags: 0,
253        };
254        let primary_hash = primary.digest();
255        self.nodes.push((primary, primary_hash));
256
257        // Secondary back-link: parent = secondary branch tip; quins_merkle = primary_hash.
258        let secondary = DagNode {
259            parent_hash: secondary_parent,
260            quins_merkle: primary_hash,
261            author_did,
262            timestamp: timestamp_ms,
263            message_hash: msg_hash,
264            flags: MERGE_SECONDARY,
265        };
266        let secondary_hash = secondary.digest();
267        self.nodes.push((secondary, secondary_hash));
268
269        (primary_hash, secondary_hash)
270    }
271
272    /// Return all node hashes with `timestamp ≤ as_of_ms` (assertion-time snapshot).
273    ///
274    /// Used by the SPARQL AS OF executor to reconstruct which DAG commits existed
275    /// at a given point in time.
276    pub fn nodes_as_of(&self, as_of_ms: u64) -> Vec<[u8; 32]> {
277        self.nodes
278            .iter()
279            .filter(|(n, _)| n.timestamp <= as_of_ms)
280            .map(|(_, h)| *h)
281            .collect()
282    }
283
284    /// Return the current tip hash for `branch_name`, if set.
285    pub fn branch_tip(&self, branch_name: &str) -> Option<[u8; 32]> {
286        self.branches.get(&q_hash(branch_name)).copied()
287    }
288
289    /// Iterate nodes in insertion order.
290    pub fn nodes(&self) -> &[(DagNode, [u8; 32])] {
291        &self.nodes
292    }
293
294    /// Serialize the store to bytes for embedding in a Q42 volume.
295    /// Format: `[u64 node_count] ([u8;88] node_bytes)*`
296    pub fn serialize(&self) -> Vec<u8> {
297        let mut out = Vec::with_capacity(8 + self.nodes.len() * 88);
298        out.extend_from_slice(&(self.nodes.len() as u64).to_le_bytes());
299        for (node, _hash) in &self.nodes {
300            out.extend_from_slice(&node.to_bytes());
301        }
302        out
303    }
304
305    /// Deserialize from bytes previously written by `serialize`.
306    pub fn deserialize(bytes: &[u8]) -> Option<Self> {
307        if bytes.len() < 8 {
308            return None;
309        }
310        let count = u64::from_le_bytes(bytes[0..8].try_into().ok()?) as usize;
311        if bytes.len() < 8 + count * 88 {
312            return None;
313        }
314        let mut nodes = Vec::with_capacity(count);
315        for i in 0..count {
316            let off = 8 + i * 88;
317            let b: &[u8; 88] = bytes[off..off + 88].try_into().ok()?;
318            let node = DagNode::from_bytes(b);
319            let hash = node.digest();
320            nodes.push((node, hash));
321        }
322        Some(Self {
323            nodes,
324            branches: std::collections::HashMap::new(),
325        })
326    }
327}
328
329impl Default for DagStore {
330    fn default() -> Self {
331        Self::new()
332    }
333}
334
335// ── git fast-export compatibility ─────────────────────────────────────────────
336
337/// Generate a `git fast-export` compatible text stream from the DAG store.
338///
339/// Called with a `DagStore` populated from the volume's `dag_root_offset` section.
340/// Falls back to a single placeholder commit when the store is empty (legacy behaviour).
341pub fn generate_fast_export_stream(store: &DagStore) -> String {
342    if store.nodes.is_empty() {
343        return legacy_fast_export();
344    }
345
346    let mut stream = String::new();
347    for (idx, (node, hash)) in store.nodes.iter().enumerate() {
348        let mark = idx + 1;
349        let hash_hex = hex::encode(hash);
350        let ts_secs = node.timestamp / 1000;
351        stream.push_str(&format!("commit refs/heads/main\nmark :{mark}\n"));
352        stream.push_str(&format!(
353            "committer unknown <did:key:{hash_hex}> {ts_secs} +0000\n"
354        ));
355        let msg = format!("quin commit {}\n", hex::encode(&node.quins_merkle[..8]));
356        stream.push_str(&format!("data {}\n{msg}", msg.len()));
357        if node.flags & FORK_DISPUTED != 0 {
358            stream.push_str("# flags: FORK_DISPUTED\n");
359        }
360        let blob = format!(
361            "{{\"quins_merkle\":\"{}\",\"author_did\":{},\"flags\":{}}}",
362            hex::encode(node.quins_merkle),
363            node.author_did,
364            node.flags,
365        );
366        stream.push_str(&format!(
367            "M 100644 inline dag_node_{mark}.json\ndata {}\n{blob}\n",
368            blob.len()
369        ));
370    }
371    stream
372}
373
374fn legacy_fast_export() -> String {
375    let blob = "{\"financial\": 1200.00, \"labor_hours\": 45}";
376    format!(
377        "commit refs/heads/main\nmark :1\n\
378         committer Alice <alice@did.key> 1717286400 +0000\n\
379         data 36\nLog 4 hours of design obligation\n\
380         M 100644 inline obligation_matrix.json\ndata {}\n{blob}\n",
381        blob.len()
382    )
383}
384
385/// Convenience wrapper: generate fast-export from a bare project ID string.
386/// Creates an empty store and produces the legacy stream (backward-compatible shim).
387pub fn generate_fast_export_stream_for_project(_project_id: &str) -> String {
388    generate_fast_export_stream(&DagStore::new())
389}
390
391#[cfg(test)]
392mod tests {
393    use super::*;
394
395    #[test]
396    fn genesis_commit_roundtrip() {
397        let mut store = DagStore::new();
398        let quins: Vec<NQuin> = Vec::new();
399        let hash = store.genesis_node(&quins, 0xDEAD_BEEF, 1_717_286_400_000, "genesis");
400        assert_ne!(hash, [0u8; 32]);
401        assert_eq!(store.nodes().len(), 1);
402        assert_eq!(store.nodes()[0].0.flags, GENESIS);
403    }
404
405    #[test]
406    fn chain_commit_and_fork() {
407        let mut store = DagStore::new();
408        let genesis = store.genesis_node(&[], 1, 1000, "init");
409        let c1 = store.commit_node(genesis, &[], 1, 2000, "add data");
410        let fork = store.fork_node(c1, &[], 2, 3000, "contested");
411        assert_eq!(store.nodes().len(), 3);
412        assert_eq!(store.nodes()[2].0.flags, FORK_DISPUTED);
413        assert_eq!(store.nodes()[2].0.parent_hash, c1);
414        let _ = fork;
415    }
416
417    #[test]
418    fn branch_pointer_is_retrievable() {
419        let mut store = DagStore::new();
420        let genesis = store.genesis_node(&[], 1, 1000, "init");
421        let quin = store.write_branch_pointer("main", genesis);
422        assert_eq!(quin.context, BRANCHES_CONTEXT);
423        assert!(store.branch_tip("main").is_some());
424    }
425
426    #[test]
427    fn serialize_deserialize_roundtrip() {
428        let mut store = DagStore::new();
429        store.genesis_node(&[], 42, 999, "first");
430        let bytes = store.serialize();
431        let restored = DagStore::deserialize(&bytes).expect("deser failed");
432        assert_eq!(restored.nodes().len(), 1);
433        assert_eq!(restored.nodes()[0].1, store.nodes()[0].1);
434    }
435
436    #[test]
437    fn merge_node_produces_two_linked_nodes() {
438        let mut store = DagStore::new();
439        let branch_a = store.genesis_node(&[], 1, 1000, "branch-a init");
440        let branch_b = store.genesis_node(&[], 2, 2000, "branch-b init");
441
442        let (primary, secondary) = store.merge_node(branch_a, branch_b, &[], 1, 3000, "merge");
443
444        assert_ne!(primary, secondary);
445        assert_ne!(primary, [0u8; 32]);
446        assert_ne!(secondary, [0u8; 32]);
447
448        // Primary node must have branch_a as its parent.
449        let primary_node = store.nodes().iter().find(|(_, h)| *h == primary).unwrap().0;
450        assert_eq!(primary_node.parent_hash, branch_a);
451        assert_eq!(primary_node.flags, 0);
452
453        // Secondary node must have branch_b as parent and encode primary_hash in quins_merkle.
454        let secondary_node = store
455            .nodes()
456            .iter()
457            .find(|(_, h)| *h == secondary)
458            .unwrap()
459            .0;
460        assert_eq!(secondary_node.parent_hash, branch_b);
461        assert_eq!(secondary_node.flags, MERGE_SECONDARY);
462        assert_eq!(secondary_node.quins_merkle, primary);
463    }
464
465    #[test]
466    fn nodes_as_of_filters_by_timestamp() {
467        let mut store = DagStore::new();
468        store.genesis_node(&[], 1, 1000, "t=1000");
469        store.commit_node([0u8; 32], &[], 1, 5000, "t=5000");
470        store.commit_node([0u8; 32], &[], 1, 9000, "t=9000");
471
472        let snapshot = store.nodes_as_of(5000);
473        assert_eq!(snapshot.len(), 2, "should include nodes at t≤5000");
474
475        let full = store.nodes_as_of(u64::MAX);
476        assert_eq!(full.len(), 3);
477    }
478
479    #[test]
480    fn dag_node_size() {
481        assert_eq!(std::mem::size_of::<DagNode>(), 88);
482    }
483
484    #[test]
485    fn fast_export_uses_real_nodes() {
486        let mut store = DagStore::new();
487        store.genesis_node(&[], 7, 1_000_000, "test commit");
488        let export = generate_fast_export_stream(&store);
489        assert!(export.contains("commit refs/heads/main"));
490        assert!(export.contains("quins_merkle"));
491    }
492}
qualia_core_db/platform/git_bridge.rs

qualia_core_db/platform/
git_bridge.rs
