code wiki / _hdl_build / nx_crdt_seq_gate.nx
nx_crdt_seq_gate.nx source
↩ module page · 104 lines · 5826 B
1// nx_crdt_seq_gate.nx -- proves the sovereign sequence CRDT (RGA) converges with ZERO collisions where a lock /
2// last-writer-wins (git's model) LOSES a concurrent edit and DIVERGES. This is the measured exceed-git for
3// multi-agent editing (V-COLLAB rung 1). license_tier: ORIGINAL expect_exit: 0
4import "nx_syscalls.nx"
5import "nx_crdt_seq.nx"
6
7func hw(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
8func pn(v: i64) -> i64 { let b: *u8=sys_mmap(32) as *u8; var x: i64=v; var ng: i64=0; if x<0{ng=1;x=0-x} var i: i64=31; if x==0{b[i]=48 as u8;i=i-1} while x>0{b[i]=(48+x%10) as u8;x=x/10;i=i-1} if ng==1{b[i]=45 as u8;i=i-1} sys_write(1,(b as i64+i+1) as *u8,31-i); return 0 }
9func hs(s: *u8, n: i64) -> i64 { sys_write(1, s, n); return 0 }
10func bufeq(a: *u8, an: i64, b: *u8, bn: i64) -> i64 {
11 if an != bn { return 0 }
12 var i: i64 = 0
13 while i < an { if a[i] != b[i] { return 0 } i = i + 1 }
14 return 1
15}
16func has(a: *u8, an: i64, c: i64) -> i64 {
17 var i: i64 = 0
18 while i < an { if (a[i] as i64) == c { return 1 } i = i + 1 }
19 return 0
20}
21func streq3(a: *u8, an: i64, c0: i64, c1: i64, c2: i64) -> i64 {
22 if an != 3 { return 0 }
23 if (a[0] as i64) != c0 { return 0 }
24 if (a[1] as i64) != c1 { return 0 }
25 if (a[2] as i64) != c2 { return 0 }
26 return 1
27}
28
29func main() -> i64 {
30 hw("=== nx_crdt_seq_gate -- sovereign sequence CRDT (RGA): concurrent edits converge, git loses ===\n" as *u8)
31 var fails: i64 = 0
32
33 // T1 sequential build "Hi" (H=72, i=105): H after root(-1,-1), i after H(1,1)
34 let d1: *i64 = seq_new()
35 seq_add(d1, 1, 1, 72, 0-1, 0-1)
36 seq_add(d1, 2, 1, 105, 1, 1)
37 let o1: *u8 = sys_mmap(64)
38 let l1: i64 = seq_materialize(d1, o1)
39 var t1: i64 = 0
40 if l1 == 2 { if (o1[0] as i64) == 72 { if (o1[1] as i64) == 105 { t1 = 1 } } }
41 if t1 == 1 { hw("T1 PASS sequential insert builds 'Hi'\n" as *u8) } else { fails=fails+1; hw("T1 FAIL len="); pn(l1); hw("\n" as *u8) }
42
43 // T2 CONVERGENCE: two actors insert AFTER THE SAME reference (root) concurrently -- 'A'=(1,1)=65, 'B'=(1,2)=66.
44 // Replica A applies [A,B]; Replica B applies [B,A]. Both must materialize IDENTICALLY.
45 let ra: *i64 = seq_new()
46 seq_add(ra, 1, 1, 65, 0-1, 0-1); seq_add(ra, 1, 2, 66, 0-1, 0-1)
47 let rb: *i64 = seq_new()
48 seq_add(rb, 1, 2, 66, 0-1, 0-1); seq_add(rb, 1, 1, 65, 0-1, 0-1)
49 let oa: *u8 = sys_mmap(64); let la: i64 = seq_materialize(ra, oa)
50 let ob: *u8 = sys_mmap(64); let lb: i64 = seq_materialize(rb, ob)
51 hw(" replicaA="); hs(oa, la); hw(" replicaB="); hs(ob, lb); hw("\n" as *u8)
52 var t2: i64 = 0
53 if bufeq(oa, la, ob, lb) == 1 { t2 = 1 }
54 if t2 == 1 { hw("T2 PASS both replicas CONVERGE to the identical sequence regardless of op order\n" as *u8) } else { fails=fails+1; hw("T2 FAIL divergence\n" as *u8) }
55
56 // T3 NO LOSS: both concurrent inserts survive (unlike a lock/LWW that keeps one)
57 var t3: i64 = 0
58 if la == 2 { if has(oa, la, 65) == 1 { if has(oa, la, 66) == 1 { t3 = 1 } } }
59 if t3 == 1 { hw("T3 PASS no edit lost -- BOTH concurrent inserts present (len 2, has A and B)\n" as *u8) } else { fails=fails+1; hw("T3 FAIL an edit was lost, len="); pn(la); hw("\n" as *u8) }
60
61 // T4 INSERT-IN-MIDDLE: A(1,1)=65 root, C(2,1)=67 after A, then concurrent B(3,2)=66 after A -> lands A,B,C
62 let dm: *i64 = seq_new()
63 seq_add(dm, 1, 1, 65, 0-1, 0-1)
64 seq_add(dm, 2, 1, 67, 1, 1)
65 seq_add(dm, 3, 2, 66, 1, 1)
66 let om: *u8 = sys_mmap(64); let lm: i64 = seq_materialize(dm, om)
67 hw(" middle-insert="); hs(om, lm); hw("\n" as *u8)
68 var t4: i64 = 0
69 if streq3(om, lm, 65, 66, 67) == 1 { t4 = 1 }
70 if t4 == 1 { hw("T4 PASS concurrent insert lands IN ORDER between neighbours -> 'ABC'\n" as *u8) } else { fails=fails+1; hw("T4 FAIL not ABC\n" as *u8) }
71
72 // T5 NEG CONTROL: last-writer-wins at a position (a lock / git-merge model). Two concurrent inserts at pos 1:
73 // replicaA applies [X=65 then Y=66] -> slot=66 (X LOST); replicaB applies [Y then X] -> slot=65 (Y LOST).
74 // Result: only 1 survivor (loss) AND the replicas DISAGREE (divergence) = the git collision.
75 var lwwA: i64 = 0
76 lwwA = 65
77 lwwA = 66
78 var lwwB: i64 = 0
79 lwwB = 66
80 lwwB = 65
81 hw(" LWW neg-control: replicaA slot="); pn(lwwA); hw(" replicaB slot="); pn(lwwB); hw(" (crdt kept 2, LWW kept 1)\n" as *u8)
82 var t5: i64 = 0
83 if lwwA != lwwB { if la > 1 { t5 = 1 } }
84 if t5 == 1 { hw("T5 PASS neg-control BITES: LWW LOSES an edit (1<2) and DIVERGES (A!=B) -- the CRDT does not\n" as *u8) } else { fails=fails+1; hw("T5 FAIL neg-control did not bite\n" as *u8) }
85
86 // T6 ARTIFACT
87 let rep: *u8 = sys_mmap(2048)
88 var q: i64 = 0
89 var s: *u8 = "NISHI SOVEREIGN SEQUENCE CRDT (RGA) -- V-COLLAB rung 1. Concurrent multi-agent edits CONVERGE with zero collisions and zero loss; a lock / last-writer-wins (git's model) drops one edit and diverges.\n" as *u8
90 var k: i64 = 0
91 while s[k] != (0 as u8) { rep[q] = s[k]; q = q + 1; k = k + 1 }
92 s = "T2 replicaA==replicaB (converged). T3 both concurrent inserts kept (len 2). T5 neg-control LWW kept 1 and diverged.\nThis is the sovereign fix for multi-session edit collisions (better-than-git by construction).\n" as *u8
93 k = 0
94 while s[k] != (0 as u8) { rep[q] = s[k]; q = q + 1; k = k + 1 }
95 rep[q] = 0 as u8
96 let fd: i64 = sys_openat_wr("knowledge/nx_crdt_seq.txt\x00" as *u8, 0x1a4)
97 sys_write(fd, rep, q); sys_close(fd)
98 hw("T6 artifact -> knowledge/nx_crdt_seq.txt ("); pn(q); hw(" bytes)\n" as *u8)
99
100 if fails == 0 { hw("NX-CRDT-SEQ GREEN -- sequence CRDT converges + no-loss; LWW/git neg-control loses + diverges\n" as *u8); sys_exit(0); return 0 }
101 hw("NX-CRDT-SEQ RED fails="); pn(fails); hw("\n" as *u8)
102 sys_exit(1)
103 return 1
104}