tobogganSe connecter

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.

321 lignes · 8450 octetsBrut · Historique
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
10import gen
11import std/list
12import std/random.{type random}
13import std/string
14import std/test.{assert, assert_equal}
15import 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.
19fn 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
29fn 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
52fn oracle_find :: s: String needle: String -> Option<Int>
53{
54 scan s needle 0 1
55}
56
57fn 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.)
67fn 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)`.
89fn 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
95fn 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
116fn 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
131fn 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
149fn 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
164fn 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
182fn 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
207fn 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
245fn 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
264fn 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
280fn 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
294fn 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
315fn 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}