nx_entity_store.nx source

1// nx_entity_store.nx -- the SOVEREIGN ENTITY STORE. nx_gamebench gap-queue rank 1 after save/load and rpg-stats 2// landed: entity-component-sim was PARTIAL and blocks 7 of 12 benchmarked titles (Doom actors, OpenXcom 3// units, Diablo monsters, Cataclysm, Veloren, Freeciv, NetHack). 4// 5// THE HAZARD THIS PART EXISTS TO KILL -- the stale handle. Every naive entity store hands out a raw slot 6// index. An entity dies, its slot is recycled for a new entity, and any handle still held by old code now 7// silently addresses a DIFFERENT entity: a homing missile retargets onto a random unit, a dead unit's buff 8// lands on its replacement. It is one of the nastiest bug classes in game code because it is invisible 9// until it is a bug report. Here every handle carries a GENERATION stamped into it, bumped on destroy, so a 10// stale handle is DETECTABLY invalid -- rejection is by construction, not by discipline. 11// 12// Other certified properties (each a gate tooth): 13// - O(1) spawn and destroy (free-list + swap-remove), no scanning 14// - DENSE iteration: visiting the alive set never walks holes 15// - REPLAY-DETERMINISTIC: the same operation sequence yields the same handles and the same iteration 16// order, so recorded input replays identically (the determinism exceed carried into simulation) 17// - CAPACITY-BOUNDED: spawning past capacity returns the null handle, never corrupts the arena 18// - Component values are plain i64 so entity state drops straight into gs_save/gs_load (nx_gamesave). 19// 20// Arena layout follows the nx_swgpu base+offset idiom: one mmap block, all offsets derived from cap/ncomp. 21// LIB ONLY -- no main() by ecosystem convention. 22// license_tier: ORIGINAL expect_exit: 0 23import "nx_syscalls.nx" 24 25const EN_GENMOD: i64 = 1048576 // 2^20 generations per slot before wrap 26const EN_NULL: i64 = 0 // the null handle; a real handle is always > 0 27const EN_HDR: i64 = 4 // cap, ncomp, alive_count, fresh_next 28 29// ---- header accessors ---- 30func en_cap(a: *i64) -> i64 { return a[0] } 31func en_ncomp(a: *i64) -> i64 { return a[1] } 32func en_count(a: *i64) -> i64 { return a[2] } 33 34// ---- array bases (in i64 words) ---- 35func en_o_gen(a: *i64) -> i64 { return EN_HDR } 36func en_o_alive(a: *i64) -> i64 { return EN_HDR + en_cap(a) } 37func en_o_free(a: *i64) -> i64 { return EN_HDR + 2*en_cap(a) } 38func en_o_dense(a: *i64) -> i64 { return EN_HDR + 3*en_cap(a) } 39func en_o_pos(a: *i64) -> i64 { return EN_HDR + 4*en_cap(a) } 40func en_o_comp(a: *i64) -> i64 { return EN_HDR + 5*en_cap(a) } 41 42// total words an arena needs 43func en_words(cap: i64, ncomp: i64) -> i64 { return EN_HDR + 5*cap + ncomp*cap + 8 } 44func en_bytes(cap: i64, ncomp: i64) -> i64 { return en_words(cap, ncomp) * 8 } 45 46// free list is a stack; free_top lives at a[3+...]? keep it in the header slot 3 alongside fresh_next 47// slot 3 packs: fresh_next (how many slots ever handed out) ; the free stack length is derived 48func en_init(a: *i64, cap: i64, ncomp: i64) -> i64 { 49 a[0] = cap 50 a[1] = ncomp 51 a[2] = 0 // alive_count 52 a[3] = 0 // fresh_next 53 var i: i64 = 0 54 while i < cap { 55 a[en_o_gen(a) + i] = 1 // generations start at 1 so a zeroed handle is never valid 56 a[en_o_alive(a) + i] = 0 57 a[en_o_dense(a) + i] = 0 58 a[en_o_pos(a) + i] = 0-1 59 i = i + 1 60 } 61 a[en_o_free(a)] = 0 // free stack length stored at index 0 of the free region 62 return 0 63} 64 65func en_freelen(a: *i64) -> i64 { return a[en_o_free(a)] } 66 67func en_make_handle(idx: i64, gen: i64) -> i64 { return (idx + 1) * EN_GENMOD + gen } 68func en_handle_idx(h: i64) -> i64 { return (h / EN_GENMOD) - 1 } 69func en_handle_gen(h: i64) -> i64 { return h % EN_GENMOD } 70 71// ---- validity: the stale-handle killer ---- 72func en_valid(a: *i64, h: i64) -> i64 { 73 if h <= EN_NULL { return 0 } 74 let idx: i64 = en_handle_idx(h) 75 if idx < 0 { return 0 } 76 if idx >= en_cap(a) { return 0 } 77 if a[en_o_alive(a) + idx] != 1 { return 0 } 78 if a[en_o_gen(a) + idx] != en_handle_gen(h) { return 0 } 79 return 1 80} 81 82// ---- spawn: reuse a freed slot if any, else take a fresh one ---- 83func en_spawn(a: *i64) -> i64 { 84 var idx: i64 = 0-1 85 let fl: i64 = en_freelen(a) 86 if fl > 0 { 87 idx = a[en_o_free(a) + fl] // stack grows at +1..+fl 88 a[en_o_free(a)] = fl - 1 89 } else { 90 let fresh: i64 = a[3] 91 if fresh >= en_cap(a) { return EN_NULL } 92 idx = fresh 93 a[3] = fresh + 1 94 } 95 a[en_o_alive(a) + idx] = 1 96 // clear components so a recycled slot never leaks the previous entity's data 97 var c: i64 = 0 98 while c < en_ncomp(a) { a[en_o_comp(a) + c*en_cap(a) + idx] = 0; c = c + 1 } 99 // append to the dense list 100 let n: i64 = a[2] 101 a[en_o_dense(a) + n] = idx 102 a[en_o_pos(a) + idx] = n 103 a[2] = n + 1 104 return en_make_handle(idx, a[en_o_gen(a) + idx]) 105} 106 107// ---- destroy: bump generation (invalidating every outstanding handle), swap-remove from dense ---- 108func en_destroy(a: *i64, h: i64) -> i64 { 109 if en_valid(a, h) == 0 { return 0 } 110 let idx: i64 = en_handle_idx(h) 111 a[en_o_alive(a) + idx] = 0 112 var g: i64 = a[en_o_gen(a) + idx] + 1 113 if g >= EN_GENMOD { g = 1 } 114 a[en_o_gen(a) + idx] = g 115 // swap-remove keeps the dense list hole-free 116 let p: i64 = a[en_o_pos(a) + idx] 117 let n: i64 = a[2] 118 let last: i64 = a[en_o_dense(a) + n - 1] 119 a[en_o_dense(a) + p] = last 120 a[en_o_pos(a) + last] = p 121 a[en_o_pos(a) + idx] = 0-1 122 a[2] = n - 1 123 // push the slot onto the free stack 124 let fl: i64 = en_freelen(a) + 1 125 a[en_o_free(a) + fl] = idx 126 a[en_o_free(a)] = fl 127 return 1 128} 129 130// ---- components ---- 131func en_set(a: *i64, h: i64, comp: i64, val: i64) -> i64 { 132 if en_valid(a, h) == 0 { return 0 } 133 if comp < 0 { return 0 } 134 if comp >= en_ncomp(a) { return 0 } 135 a[en_o_comp(a) + comp*en_cap(a) + en_handle_idx(h)] = val 136 return 1 137} 138func en_get(a: *i64, h: i64, comp: i64) -> i64 { 139 if en_valid(a, h) == 0 { return 0 } 140 if comp < 0 { return 0 } 141 if comp >= en_ncomp(a) { return 0 } 142 return a[en_o_comp(a) + comp*en_cap(a) + en_handle_idx(h)] 143} 144 145// ---- deterministic dense iteration: en_nth(k) for k in 0..en_count-1 ---- 146func en_nth(a: *i64, k: i64) -> i64 { 147 if k < 0 { return EN_NULL } 148 if k >= a[2] { return EN_NULL } 149 let idx: i64 = a[en_o_dense(a) + k] 150 return en_make_handle(idx, a[en_o_gen(a) + idx]) 151}