`nx_crdt_seq.nx` source

↩ module page · 106 lines · 4377 B
1// nx_crdt_seq.nx -- SOVEREIGN SEQUENCE CRDT (RGA: Replicated Growable Array, Roh et al. 2011). The V-COLLAB rung-1
2// fix for the recurring multi-agent EDIT COLLISION (two Claude sessions "file modified since read" = the git/gitea
3// collision the operator asked to KILL 2026-05-27). Each element has a unique id (lamport clock, actor) + the id of
4// the element it was inserted AFTER (its RGA reference/parent). Concurrent inserts after the same reference are
5// ordered by a DETERMINISTIC total order on ids (descending) that every replica computes identically -> ALL replicas
6// converge to the SAME sequence regardless of op arrival order, and NO concurrent edit is ever lost (unlike a lock/
7// last-writer-wins, which drops one). 100% integer, deterministic. license_tier: ORIGINAL
8import "nx_syscalls.nx"
9
10const SEQ_MAX: i64 = 512          // max elements
11const SEQ_INF: i64 = 1000000000   // id-ceiling sentinel (> any real clock)
12
13// element layout (6 i64 slots): [0]=id_clock [1]=id_actor [2]=value [3]=ref_clock [4]=ref_actor [5]=deleted
14func seq_item(doc: *i64, i: i64) -> *i64 { return (doc as i64 + (1 + i*6)*8) as *i64 }
15
16func seq_new() -> *i64 {
17    let d: *i64 = sys_mmap((1 + SEQ_MAX*6)*8) as *i64
18    d[0] = 0
19    return d
20}
21func seq_count(doc: *i64) -> i64 { return doc[0] }
22
23// total order on ids: clock first, then actor. returns 1 if a<b, else 0.
24func id_lt(ac: i64, aa: i64, bc: i64, ba: i64) -> i64 {
25    if ac < bc { return 1 }
26    if ac > bc { return 0 }
27    if aa < ba { return 1 }
28    return 0
29}
30
31func seq_find(doc: *i64, idc: i64, ida: i64) -> i64 {
32    let n: i64 = doc[0]
33    var i: i64 = 0
34    while i < n {
35        let it: *i64 = seq_item(doc, i)
36        if it[0] == idc { if it[1] == ida { return i } }
37        i = i + 1
38    }
39    return 0 - 1
40}
41
42// integrate an insert op. IDEMPOTENT (re-applying the same id is a no-op) -> safe under at-least-once delivery.
43// ref = the id of the element this was inserted after; (-1,-1) = inserted at the start. returns element index.
44func seq_add(doc: *i64, idc: i64, ida: i64, value: i64, refc: i64, refa: i64) -> i64 {
45    let ex: i64 = seq_find(doc, idc, ida)
46    if ex >= 0 { return ex }
47    let n: i64 = doc[0]
48    if n >= SEQ_MAX { return 0 - 1 }
49    let it: *i64 = seq_item(doc, n)
50    it[0] = idc; it[1] = ida; it[2] = value; it[3] = refc; it[4] = refa; it[5] = 0
51    doc[0] = n + 1
52    return n
53}
54
55// tombstone delete (history-preserving; the element stays for causal reference, hidden from materialization)
56func seq_delete(doc: *i64, idc: i64, ida: i64) -> i64 {
57    let i: i64 = seq_find(doc, idc, ida)
58    if i >= 0 { let it: *i64 = seq_item(doc, i); it[5] = 1 }
59    return 0
60}
61
62// emit the children of reference (refc,refa) with id < (pc,pa), in DESCENDING id order, each followed by its own
63// subtree. This deterministic traversal is what makes every replica converge to the identical sequence.
64func seq_emit_children(doc: *i64, refc: i64, refa: i64, out: *u8, olen: *i64, prevc: i64, preva: i64) -> i64 {
65    var pc: i64 = prevc
66    var pa: i64 = preva
67    var go: i64 = 1
68    while go == 1 {
69        let n: i64 = doc[0]
70        var besti: i64 = 0 - 1
71        var bestc: i64 = 0
72        var besta: i64 = 0
73        var i: i64 = 0
74        while i < n {
75            let it: *i64 = seq_item(doc, i)
76            if it[3] == refc {
77                if it[4] == refa {
78                    if id_lt(it[0], it[1], pc, pa) == 1 {
79                        var take: i64 = 0
80                        if besti < 0 { take = 1 }
81                        if besti >= 0 { if id_lt(bestc, besta, it[0], it[1]) == 1 { take = 1 } }
82                        if take == 1 { besti = i; bestc = it[0]; besta = it[1] }
83                    }
84                }
85            }
86            i = i + 1
87        }
88        if besti < 0 { go = 0 }
89        if besti >= 0 {
90            let bit: *i64 = seq_item(doc, besti)
91            if bit[5] == 0 { out[olen[0]] = bit[2] as u8; olen[0] = olen[0] + 1 }
92            seq_emit_children(doc, bestc, besta, out, olen, SEQ_INF, SEQ_INF)
93            pc = bestc
94            pa = besta
95        }
96    }
97    return 0
98}
99
100// materialize the visible sequence into out (bytes); returns length.
101func seq_materialize(doc: *i64, out: *u8) -> i64 {
102    let olen: *i64 = sys_mmap(16) as *i64
103    olen[0] = 0
104    seq_emit_children(doc, 0 - 1, 0 - 1, out, olen, SEQ_INF, SEQ_INF)
105    return olen[0]
106}
nx_crdt_seq.nx source

`nx_crdt_seq.nx` source
