prop_test.nx source

1// prop_test.nx -- property-based testing infrastructure. 2// 3// Verify that a property holds across a LARGE random sample of 4// inputs instead of enumerating hand-picked cases. Catches bugs 5// that manual test cases miss. Inspired by QuickCheck (Haskell, 6// 2000), Hypothesis (Python), proptest (Rust). 7// 8// Pattern: 9// 1. Define a property P(x) that should be true for all x of 10// some type T. 11// 2. Write a generator that produces random T values from a 12// seeded PRNG. 13// 3. Run P(gen()) for N iterations (default 1000). 14// 4. On failure, record the first counter-example + shrink it 15// to a minimal case. 16// 17// This scaffold ships the GENERATOR + RUNNER primitives. Each 18// property test lives in its own .nx file (see prop_*_test.nx). 19// 20// Reference: Claessen & Hughes 2000 "QuickCheck: A Lightweight 21// Tool for Random Testing of Haskell Programs"; MacIver 2019 22// "Hypothesis: A new approach to property-based testing" 23// (particularly the shrinking algorithm). 24 25import "syscalls.nx" 26import "nx_assert.nx" 27 28// ---- PRNG --------------------------------------------------------- 29// 30// xorshift64 -- seeded, reproducible, passes most tests in the 31// TestU01 SmallCrush suite. Wider mixing via xorshift*. We don't 32// need cryptographic randomness; we need REPRODUCIBILITY across 33// machines so prop failures can be replayed by seed. 34 35struct PropGen { 36 state: i64, 37 iter: i64, 38 max: i64, 39} 40 41const PROP_GEN_BYTES: i64 = 32 42 43func prop_gen_new(seed: i64) -> *PropGen { 44 let g_raw: *u8 = sys_mmap(PROP_GEN_BYTES) 45 let g: *PropGen = g_raw as *PropGen 46 // Non-zero state required for xorshift; mix in a prime if 47 // caller passes 0. 48 if seed == 0 { 49 g.state = 0x9E3779B97F4A7C15 // golden ratio mix 50 } 51 if seed != 0 { 52 g.state = seed 53 } 54 g.iter = 0 55 g.max = 1000 56 return g 57} 58 59// xorshift64 next step -- returns a pseudorandom i64. Advances 60// internal state; each call is independent. 61func prop_gen_i64(g: *PropGen) -> i64 { 62 var s: i64 = g.state 63 s = s ^ (s << 13) 64 s = s ^ (s >> 7) 65 s = s ^ (s << 17) 66 g.state = s 67 return s 68} 69 70// Generate an i64 in [lo, hi] inclusive. Uses modulo which has 71// tiny bias for non-power-of-2 ranges; fine for property tests. 72func prop_gen_range(g: *PropGen, lo: i64, hi: i64) -> i64 { 73 if hi <= lo { return lo } 74 let span: i64 = hi - lo + 1 75 let raw: i64 = prop_gen_i64(g) 76 // Make positive; xorshift can produce negative i64. 77 var r: i64 = raw 78 if r < 0 { r = 0 - r } 79 if r < 0 { r = 0 } // handle INT64_MIN edge case 80 return lo + (r - (r / span) * span) 81} 82 83// Generate a "small" i64 -- biased toward 0. Good for edge-case 84// discovery (shrinking is effectively free if most generated 85// values are tiny). 86func prop_gen_small(g: *PropGen) -> i64 { 87 let r: i64 = prop_gen_i64(g) & 0xFF // 0..255 mostly 88 let sign: i64 = prop_gen_i64(g) & 1 89 if sign == 1 { return r } 90 return 0 - r 91} 92 93// Fill `buf` with `n` pseudorandom bytes. Used to generate input 94// for parsers, lexers, deserializers. 95func prop_gen_bytes(g: *PropGen, buf: *u8, n: i64) -> i64 { 96 var i: i64 = 0 97 while i < n { 98 buf[i] = prop_gen_i64(g) & 0xFF 99 i = i + 1 100 } 101 return 0 102} 103 104// Generate a printable ASCII byte (0x20..0x7E). Skips control 105// chars + DEL. 106func prop_gen_printable(g: *PropGen) -> i64 { 107 let r: i64 = prop_gen_i64(g) & 0x3F // 0..63 108 return 0x20 + r // 0x20..0x5F (subset) 109} 110 111// ---- property runner ---------------------------------------------- 112// 113// Since NishiLang doesn't have first-class function pointers used 114// as arbitrary callbacks, each property gets its own top-level 115// `main()` in a dedicated .nx file that: 116// 1. Creates a PropGen with a fixed seed (reproducibility). 117// 2. Loops `iters` times generating + checking. 118// 3. On failure: nx_assert fires + exits 200, reporting the 119// iteration index + seed. 120// 4. On success: exits 0. 121// 122// prop_test.nx itself just ships the generators above. The 123// pattern is visible in each prop_*_test.nx consumer. 124 125// Helper: emit 'prop_test: iter=N seed=S\n' on failure so the 126// reporter knows how to replay. Call before any nx_assert call 127// inside a property body. 128func prop_report(g: *PropGen, tag: *u8) -> i64 { 129 sys_write(2, "\nprop_test: ITER=" as *u8, 17) 130 nx_puti_err(g.iter) 131 sys_write(2, "prop_test: SEED=" as *u8, 16) 132 nx_putx_err(g.state) 133 sys_write(2, "\nprop_test: TAG=" as *u8, 16) 134 nx_puts_err(tag) 135 sys_write(2, "\n" as *u8, 1) 136 return 0 137} 138 139// ---- self-test ---------------------------------------------------- 140// 141// Minimal property: i64 addition is commutative. Generates 1000 142// pairs (a, b) and checks a+b == b+a. Success => exit 0. 143// 144// Also sanity-checks PRNG output: consecutive calls produce 145// different values (seed isn't stuck). 146 147func main() -> i64 { 148 let g: *PropGen = prop_gen_new(42) 149 150 // PRNG liveness -- 10 consecutive calls produce 10 distinct values. 151 let prev_raw: *u8 = sys_mmap(128) 152 let prev: *i64 = prev_raw as *i64 153 var i: i64 = 0 154 while i < 10 { 155 prev[i] = prop_gen_i64(g) 156 i = i + 1 157 } 158 i = 0 159 while i < 10 { 160 var j: i64 = i + 1 161 while j < 10 { 162 if prev[i] == prev[j] { 163 return __syscall(93, 10, 0, 0, 0, 0, 0) 164 } 165 j = j + 1 166 } 167 i = i + 1 168 } 169 170 // Commutativity of i64 addition. 171 var iter: i64 = 0 172 while iter < 1000 { 173 g.iter = iter 174 let a: i64 = prop_gen_i64(g) 175 let b: i64 = prop_gen_i64(g) 176 if a + b != b + a { 177 prop_report(g, "i64 + commutes" as *u8) 178 return __syscall(93, 20, 0, 0, 0, 0, 0) 179 } 180 iter = iter + 1 181 } 182 183 // Range bounds -- prop_gen_range stays within [lo, hi]. 184 iter = 0 185 while iter < 100 { 186 let r: i64 = prop_gen_range(g, -50, 50) 187 if r < -50 { 188 return __syscall(93, 30, 0, 0, 0, 0, 0) 189 } 190 if r > 50 { 191 return __syscall(93, 31, 0, 0, 0, 0, 0) 192 } 193 iter = iter + 1 194 } 195 196 // prop_gen_bytes fills the buffer without going past. Can't 197 // detect an off-by-one write past the end without a canary -- 198 // add a sentinel byte and verify it's untouched. 199 let buf: *u8 = sys_mmap(40) 200 buf[32] = 0xFF // canary 201 prop_gen_bytes(g, buf, 32) 202 if buf[32] != 0xFF { 203 return __syscall(93, 40, 0, 0, 0, 0, 0) 204 } 205 206 return 0 207}