packages
The Louise packages, each released on its own
Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.
Dernier runRéussi#28 · main · 3 min 34 s
0Étoiles
0Forks
3Issues
| 1 | // Tests for packages/stringzilla. **Native-only**: the interpreter cannot |
| 2 | // call C externs, so run them with `louise test --native` (the argon2 |
| 3 | // package's pattern; ci.sh runs it the same way). |
| 4 | // |
| 5 | // `gen/check.property` cannot help here: its `holds` is pure, and every |
| 6 | // function of this package performs `<ffi>`. `for_all` below is its |
| 7 | // shrunk-less stand-in: cases come from a seeded generator, the seed is |
| 8 | // drawn from `random` (fresh cases each run) and reported on a failure. |
| 9 | |
| 10 | import gen |
| 11 | import std/list |
| 12 | import std/random.{type random} |
| 13 | import std/string |
| 14 | import std/test.{assert, assert_equal} |
| 15 | import stringzilla |
| 16 | |
| 17 | /// Runs `holds` on `runs` cases of `generate`, from a seed drawn once |
| 18 | /// per run and named in the failure message for replay. |
| 19 | fn for_all :: |
| 20 | runs: Int |
| 21 | generate: fn() -> a / <random> |
| 22 | holds: fn(a) -> Bool / <ffi> |
| 23 | -> () / <ffi, random> |
| 24 | { |
| 25 | let seed = random.int 1000000000 |
| 26 | random.with_seed seed fn { each_case seed runs 0 generate holds } |
| 27 | } |
| 28 | |
| 29 | fn each_case :: |
| 30 | seed: Int |
| 31 | runs: Int |
| 32 | i: Int |
| 33 | generate: fn() -> a / <random> |
| 34 | holds: fn(a) -> Bool / <ffi> |
| 35 | -> () / <ffi, random> |
| 36 | { |
| 37 | if i >= runs |
| 38 | { |
| 39 | () |
| 40 | } |
| 41 | else |
| 42 | { |
| 43 | assert (holds (generate ())) "case {i + 1} failed (replay: seed {seed})" |
| 44 | each_case seed runs (i + 1) generate holds |
| 45 | } |
| 46 | } |
| 47 | |
| 48 | // Oracles: naive character scans over `string.slice`/`string.length`. |
| 49 | // The generators use ASCII alphabets, so character offsets are byte |
| 50 | // offsets. |
| 51 | |
| 52 | fn oracle_find :: s: String needle: String -> Option<Int> |
| 53 | { |
| 54 | scan s needle 0 1 |
| 55 | } |
| 56 | |
| 57 | fn oracle_find_last :: s: String needle: String -> Option<Int> |
| 58 | { |
| 59 | scan s needle (string.length s - string.length needle) (-1) |
| 60 | } |
| 61 | |
| 62 | /// `Some(i)` if `needle` is `slice(s, i, i + length(needle))`: a naive |
| 63 | /// character scan from `i` by `step`. (The `split`-based oracle is wrong |
| 64 | /// for `find_last`: split matches non-overlapping left to right, but the |
| 65 | /// last occurrence may overlap the last match — "abaabbaaabbbaabaa" |
| 66 | /// ends in "bb" at 10.) |
| 67 | fn scan :: s: String needle: String i: Int step: Int -> Option<Int> |
| 68 | { |
| 69 | let past = string.length s - string.length needle |
| 70 | if i < 0 || i > past |
| 71 | { |
| 72 | None |
| 73 | } |
| 74 | else |
| 75 | { |
| 76 | if string.slice s i (i + string.length needle) == needle |
| 77 | { |
| 78 | Some(i) |
| 79 | } |
| 80 | else |
| 81 | { |
| 82 | scan s needle (i + step) step |
| 83 | } |
| 84 | } |
| 85 | } |
| 86 | |
| 87 | /// Non-overlapping occurrences: on a match at `i`, continue at |
| 88 | /// `i + length(needle)`. |
| 89 | fn oracle_count :: s: String needle: String -> Int |
| 90 | { |
| 91 | let step = if needle == "" { 1 } else { string.length needle } |
| 92 | count_from s needle 0 step 0 |
| 93 | } |
| 94 | |
| 95 | fn count_from :: s: String needle: String i: Int step: Int found: Int -> Int |
| 96 | { |
| 97 | let past = string.length s - string.length needle |
| 98 | if i > past |
| 99 | { |
| 100 | found |
| 101 | } |
| 102 | else |
| 103 | { |
| 104 | if string.slice s i (i + string.length needle) == needle |
| 105 | { |
| 106 | count_from s needle (i + step) step (found + 1) |
| 107 | } |
| 108 | else |
| 109 | { |
| 110 | count_from s needle (i + 1) step found |
| 111 | } |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | @test |
| 116 | fn find_matches_a_naive_scan :: -> () / <ffi, random> |
| 117 | { |
| 118 | for_all |
| 119 | 300 |
| 120 | ( fn |
| 121 | { |
| 122 | ( gen.string ~alphabet: "ab" ~min: 0 ~max: 60 |
| 123 | , gen.string ~alphabet: "ab" ~min: 0 ~max: 6 |
| 124 | ) |
| 125 | } |
| 126 | ) |
| 127 | fn case { stringzilla.find case.0 case.1 == oracle_find case.0 case.1 } |
| 128 | } |
| 129 | |
| 130 | @test |
| 131 | fn find_last_matches_a_naive_scan :: -> () / <ffi, random> |
| 132 | { |
| 133 | for_all |
| 134 | 300 |
| 135 | ( fn |
| 136 | { |
| 137 | ( gen.string ~alphabet: "ab" ~min: 0 ~max: 60 |
| 138 | , gen.string ~alphabet: "ab" ~min: 0 ~max: 6 |
| 139 | ) |
| 140 | } |
| 141 | ) |
| 142 | fn case |
| 143 | { |
| 144 | stringzilla.find_last case.0 case.1 == oracle_find_last case.0 case.1 |
| 145 | } |
| 146 | } |
| 147 | |
| 148 | @test |
| 149 | fn count_matches_a_naive_scan :: -> () / <ffi, random> |
| 150 | { |
| 151 | for_all |
| 152 | 300 |
| 153 | ( fn |
| 154 | { |
| 155 | ( gen.string ~alphabet: "ab" ~min: 0 ~max: 60 |
| 156 | , gen.string ~alphabet: "ab" ~min: 0 ~max: 6 |
| 157 | ) |
| 158 | } |
| 159 | ) |
| 160 | fn case { stringzilla.count case.0 case.1 == oracle_count case.0 case.1 } |
| 161 | } |
| 162 | |
| 163 | @test |
| 164 | fn finds_agree_with_contains :: -> () / <ffi, random> |
| 165 | { |
| 166 | for_all |
| 167 | 300 |
| 168 | ( fn |
| 169 | { |
| 170 | ( gen.string ~alphabet: "ab" ~min: 0 ~max: 60 |
| 171 | , gen.string ~alphabet: "ab" ~min: 0 ~max: 6 |
| 172 | ) |
| 173 | } |
| 174 | ) |
| 175 | fn case |
| 176 | { |
| 177 | (stringzilla.find case.0 case.1 != None) == string.contains case.0 case.1 |
| 178 | } |
| 179 | } |
| 180 | |
| 181 | @test |
| 182 | fn find_byte_finds_the_byte :: -> () / <ffi, random> |
| 183 | { |
| 184 | let alphabet = "abcde" |
| 185 | for_all |
| 186 | 300 |
| 187 | ( fn |
| 188 | { |
| 189 | ( gen.string ~alphabet: alphabet ~min: 0 ~max: 60 |
| 190 | , gen.int ~low: 0 ~high: 4 |
| 191 | ) |
| 192 | } |
| 193 | ) |
| 194 | fn case |
| 195 | { |
| 196 | // Byte `i` of the alphabet as a one-character string; ASCII, so |
| 197 | // byte offsets are character offsets. |
| 198 | let needle = string.slice alphabet case.1 (case.1 + 1) |
| 199 | let byte = 97 + case.1 |
| 200 | stringzilla.find_byte case.0 byte == stringzilla.find case.0 needle |
| 201 | && stringzilla.find_byte_last case.0 byte |
| 202 | == stringzilla.find_last case.0 needle |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | @test |
| 207 | fn compare_matches_std :: -> () / <ffi, random> |
| 208 | { |
| 209 | // "é" and "ä" are two-byte UTF-8 starting at 0xC3: byte order beyond |
| 210 | // ASCII is exactly what this checks (StringZilla v4.6.3 ordered bytes |
| 211 | // signed there; the vendored copy carries the v5 fix — PATCHES.md). |
| 212 | for_all |
| 213 | 300 |
| 214 | ( fn |
| 215 | { |
| 216 | ( gen.string ~alphabet: "abczéä" ~min: 0 ~max: 12 |
| 217 | , gen.string ~alphabet: "abczéä" ~min: 0 ~max: 12 |
| 218 | ) |
| 219 | } |
| 220 | ) |
| 221 | fn case |
| 222 | { |
| 223 | let std = if case.0 < case.1 |
| 224 | { |
| 225 | -1 |
| 226 | } |
| 227 | else |
| 228 | { |
| 229 | if case.0 > case.1 |
| 230 | { |
| 231 | 1 |
| 232 | } |
| 233 | else |
| 234 | { |
| 235 | 0 |
| 236 | } |
| 237 | } |
| 238 | let sz = match stringzilla.compare case.0 case.1 |
| 239 | { Lt -> -1, Eq -> 0, Gt -> 1 } |
| 240 | std == sz |
| 241 | } |
| 242 | } |
| 243 | |
| 244 | @test |
| 245 | fn sort_matches_list_sort :: -> () / <ffi, random> |
| 246 | { |
| 247 | // Short lists take the argsort's insertion path, long ones its radix |
| 248 | // path; both must agree with `list.sort`, past 32 strings too, with |
| 249 | // non-ASCII bytes in the mix. |
| 250 | for_all |
| 251 | 100 |
| 252 | ( fn |
| 253 | { |
| 254 | gen.list |
| 255 | ~min: 0 |
| 256 | ~max: 70 |
| 257 | (fn { gen.string ~alphabet: "abczéä" ~min: 0 ~max: 12 }) |
| 258 | } |
| 259 | ) |
| 260 | fn xs { stringzilla.sort xs == Ok(list.sort xs) } |
| 261 | } |
| 262 | |
| 263 | @test |
| 264 | fn fixed_cases :: -> () / <ffi> |
| 265 | { |
| 266 | // Needle longer than the haystack; overlapping occurrences; Unicode. |
| 267 | assert_equal (stringzilla.find "ab" "abab") None |
| 268 | assert_equal (stringzilla.count "aaaa" "aa") 2 |
| 269 | assert_equal (stringzilla.find "日本語日本語" "本") (Some(3)) |
| 270 | assert_equal (stringzilla.find_last "日本語日本語" "本") (Some(12)) |
| 271 | assert_equal (stringzilla.count "日本語日本語" "日本") 2 |
| 272 | // "é" is 0xC3 0xA9: a byte search finds a continuation byte too. |
| 273 | assert_equal (stringzilla.find_byte "héllo" 0xA9) (Some(2)) |
| 274 | assert_equal (stringzilla.find_byte "banana" 97) (Some(1)) |
| 275 | assert_equal (stringzilla.find_byte_last "banana" 97) (Some(5)) |
| 276 | assert_equal (stringzilla.find_byte "" 97) None |
| 277 | } |
| 278 | |
| 279 | @test |
| 280 | fn sort_on_fixed_lists :: -> () / <ffi> |
| 281 | { |
| 282 | assert_equal (stringzilla.sort []) (Ok([])) |
| 283 | assert_equal (stringzilla.sort ["b", "a", "c"]) (Ok(["a", "b", "c"])) |
| 284 | assert_equal |
| 285 | (stringzilla.sort ["bb", "b", "ba", "a", ""]) |
| 286 | (Ok(["", "a", "b", "ba", "bb"])) |
| 287 | assert_equal (stringzilla.sort ["x", "x", "x"]) (Ok(["x", "x", "x"])) |
| 288 | assert_equal (stringzilla.sort ["é", "z", "ä"]) (Ok(["z", "ä", "é"])) |
| 289 | let down = list.map (list.reverse (list.range 1 1000)) fn i { "k{i}" } |
| 290 | assert_equal (stringzilla.sort down) (Ok(list.sort down)) |
| 291 | } |
| 292 | |
| 293 | @test |
| 294 | fn hashes_are_deterministic_and_seeded :: -> () / <ffi> |
| 295 | { |
| 296 | assert_equal (stringzilla.hash "hello" 0) (stringzilla.hash "hello" 0) |
| 297 | assert_equal (stringzilla.bytesum "hello") (stringzilla.bytesum "hello") |
| 298 | assert |
| 299 | (stringzilla.hash "hello" 0 != stringzilla.hash "hello" 1) |
| 300 | "the seed matters" |
| 301 | assert |
| 302 | (stringzilla.hash "hello" 0 != stringzilla.hash "hellp" 0) |
| 303 | "the text matters" |
| 304 | // Known answers, recorded from the vendored StringZilla v4.6.3: the |
| 305 | // low 62 bits of its 64-bit hash. Its kernels agree across SIMD tiers |
| 306 | // (checked serial through haswell). |
| 307 | assert_equal (stringzilla.hash "" 0) 463414023684379206 |
| 308 | assert_equal (stringzilla.hash "hello" 0) 2641555913580541882 |
| 309 | assert_equal (stringzilla.hash "hello" 42) 551789246955265504 |
| 310 | assert_equal (stringzilla.bytesum "hello") 532 |
| 311 | assert_equal (stringzilla.bytesum "") 0 |
| 312 | } |
| 313 | |
| 314 | @test |
| 315 | fn version_and_capabilities :: -> () / <ffi> |
| 316 | { |
| 317 | assert_equal (stringzilla.version ()) "4.6.3" |
| 318 | assert |
| 319 | (string.contains (stringzilla.capabilities ()) "serial") |
| 320 | (stringzilla.capabilities ()) |
| 321 | } |