fzy
terminal fuzzy finder picker
git clone https://9o.is/git/fzy.git
theft.c
(15642B)
1 #include <string.h>
2
3 #include "theft.h"
4 #include "theft_types_internal.h"
5 #include "theft_bloom.h"
6 #include "theft_mt.h"
7
8 /* Initialize a theft test runner.
9 * BLOOM_BITS sets the size of the table used for detecting
10 * combinations of arguments that have already been tested.
11 * If 0, a default size will be chosen based on trial count.
12 * (This will only be used if all property types have hash
13 * callbacks defined.) The bloom filter can also be disabled
14 * by setting BLOOM_BITS to THEFT_BLOOM_DISABLE.
15 *
16 * Returns a NULL if malloc fails or BLOOM_BITS is out of bounds. */
17 struct theft *theft_init(uint8_t bloom_bits) {
18 if ((bloom_bits != 0 && (bloom_bits < THEFT_BLOOM_BITS_MIN))
19 || ((bloom_bits > THEFT_BLOOM_BITS_MAX) &&
20 bloom_bits != THEFT_BLOOM_DISABLE)) {
21 return NULL;
22 }
23
24 theft *t = malloc(sizeof(*t));
25 if (t == NULL) { return NULL; }
26 memset(t, 0, sizeof(*t));
27
28 t->mt = theft_mt_init(DEFAULT_THEFT_SEED);
29 if (t->mt == NULL) {
30 free(t);
31 return NULL;
32 } else {
33 t->out = stdout;
34 t->requested_bloom_bits = bloom_bits;
35 return t;
36 }
37 }
38
39 /* (Re-)initialize the random number generator with a specific seed. */
40 void theft_set_seed(struct theft *t, uint64_t seed) {
41 t->seed = seed;
42 theft_mt_reset(t->mt, seed);
43 }
44
45 /* Get a random 64-bit integer from the test runner's PRNG. */
46 theft_seed theft_random(struct theft *t) {
47 theft_seed ns = (theft_seed)theft_mt_random(t->mt);
48 return ns;
49 }
50
51 /* Get a random double from the test runner's PRNG. */
52 double theft_random_double(struct theft *t) {
53 return theft_mt_random_double(t->mt);
54 }
55
56 /* Change T's output stream handle to OUT. (Default: stdout.) */
57 void theft_set_output_stream(struct theft *t, FILE *out) { t->out = out; }
58
59 /* Check if all argument info structs have all required callbacks. */
60 static bool
61 check_all_args(struct theft_propfun_info *info, bool *all_hashable) {
62 bool ah = true;
63 for (int i = 0; i < info->arity; i++) {
64 struct theft_type_info *ti = info->type_info[i];
65 if (ti->alloc == NULL) { return false; }
66 if (ti->hash == NULL) { ah = false; }
67 }
68 *all_hashable = ah;
69 return true;
70 }
71
72 static theft_progress_callback_res
73 default_progress_cb(struct theft_trial_info *info, void *env) {
74 (void)info;
75 (void)env;
76 return THEFT_PROGRESS_CONTINUE;
77 }
78
79 static void infer_arity(struct theft_propfun_info *info) {
80 for (int i = 0; i < THEFT_MAX_ARITY; i++) {
81 if (info->type_info[i] == NULL) {
82 info->arity = i;
83 break;
84 }
85 }
86 }
87
88 /* Run a series of randomized trials of a property function.
89 *
90 * Configuration is specified in CFG; many fields are optional.
91 * See the type definition in `theft_types.h`. */
92 theft_run_res
93 theft_run(struct theft *t, struct theft_cfg *cfg) {
94 if (t == NULL || cfg == NULL) {
95 return THEFT_RUN_ERROR_BAD_ARGS;
96 }
97
98 struct theft_propfun_info info;
99 memset(&info, 0, sizeof(info));
100 info.name = cfg->name;
101 info.fun = cfg->fun;
102 memcpy(info.type_info, cfg->type_info, sizeof(info.type_info));
103 info.always_seed_count = cfg->always_seed_count;
104 info.always_seeds = cfg->always_seeds;
105
106 if (cfg->seed) {
107 theft_set_seed(t, cfg->seed);
108 } else {
109 theft_set_seed(t, DEFAULT_THEFT_SEED);
110 }
111
112 if (cfg->trials == 0) { cfg->trials = THEFT_DEF_TRIALS; }
113
114 return theft_run_internal(t, &info, cfg->trials, cfg->progress_cb,
115 cfg->env, cfg->report);
116 }
117
118 /* Actually run the trials, with all arguments made explicit. */
119 static theft_run_res
120 theft_run_internal(struct theft *t, struct theft_propfun_info *info,
121 int trials, theft_progress_cb *cb, void *env,
122 struct theft_trial_report *r) {
123
124 struct theft_trial_report fake_report;
125 if (r == NULL) { r = &fake_report; }
126 memset(r, 0, sizeof(*r));
127
128 infer_arity(info);
129 if (info->arity == 0) {
130 return THEFT_RUN_ERROR_BAD_ARGS;
131 }
132
133 if (t == NULL || info == NULL || info->fun == NULL
134 || info->arity == 0) {
135 return THEFT_RUN_ERROR_BAD_ARGS;
136 }
137
138 bool all_hashable = false;
139 if (!check_all_args(info, &all_hashable)) {
140 return THEFT_RUN_ERROR_MISSING_CALLBACK;
141 }
142
143 if (cb == NULL) { cb = default_progress_cb; }
144
145 /* If all arguments are hashable, then attempt to use
146 * a bloom filter to avoid redundant checking. */
147 if (all_hashable) {
148 if (t->requested_bloom_bits == 0) {
149 t->requested_bloom_bits = theft_bloom_recommendation(trials);
150 }
151 if (t->requested_bloom_bits != THEFT_BLOOM_DISABLE) {
152 t->bloom = theft_bloom_init(t->requested_bloom_bits);
153 }
154 }
155
156 theft_seed seed = t->seed;
157 theft_seed initial_seed = t->seed;
158 int always_seeds = info->always_seed_count;
159 if (info->always_seeds == NULL) { always_seeds = 0; }
160
161 void *args[THEFT_MAX_ARITY];
162
163 theft_progress_callback_res cres = THEFT_PROGRESS_CONTINUE;
164
165 for (int trial = 0; trial < trials; trial++) {
166 memset(args, 0xFF, sizeof(args));
167 if (cres == THEFT_PROGRESS_HALT) { break; }
168
169 /* If any seeds to always run were specified, use those before
170 * reverting to the specified starting seed. */
171 if (trial < always_seeds) {
172 seed = info->always_seeds[trial];
173 } else if ((always_seeds > 0) && (trial == always_seeds)) {
174 seed = initial_seed;
175 }
176
177 struct theft_trial_info ti = {
178 .name = info->name,
179 .trial = trial,
180 .seed = seed,
181 .arity = info->arity,
182 .args = args
183 };
184
185 theft_set_seed(t, seed);
186 all_gen_res_t gres = gen_all_args(t, info, seed, args, env);
187 switch (gres) {
188 case ALL_GEN_SKIP:
189 /* skip generating these args */
190 ti.status = THEFT_TRIAL_SKIP;
191 r->skip++;
192 cres = cb(&ti, env);
193 break;
194 case ALL_GEN_DUP:
195 /* skip these args -- probably already tried */
196 ti.status = THEFT_TRIAL_DUP;
197 r->dup++;
198 cres = cb(&ti, env);
199 break;
200 default:
201 case ALL_GEN_ERROR:
202 /* Error while generating args */
203 ti.status = THEFT_TRIAL_ERROR;
204 cres = cb(&ti, env);
205 return THEFT_RUN_ERROR;
206 case ALL_GEN_OK:
207 /* (Extracted function to avoid deep nesting here.) */
208 if (!run_trial(t, info, args, cb, env, r, &ti, &cres)) {
209 return THEFT_RUN_ERROR;
210 }
211 }
212
213 free_args(info, args, env);
214
215 /* Restore last known seed and generate next. */
216 theft_set_seed(t, seed);
217 seed = theft_random(t);
218 }
219
220 if (r->fail > 0) {
221 return THEFT_RUN_FAIL;
222 } else {
223 return THEFT_RUN_PASS;
224 }
225 }
226
227 /* Now that arguments have been generated, run the trial and update
228 * counters, call cb with results, etc. */
229 static bool run_trial(struct theft *t, struct theft_propfun_info *info,
230 void **args, theft_progress_cb *cb, void *env,
231 struct theft_trial_report *r, struct theft_trial_info *ti,
232 theft_progress_callback_res *cres) {
233 if (t->bloom) { mark_called(t, info, args, env); }
234 theft_trial_res tres = call_fun(info, args);
235 ti->status = tres;
236 switch (tres) {
237 case THEFT_TRIAL_PASS:
238 r->pass++;
239 *cres = cb(ti, env);
240 break;
241 case THEFT_TRIAL_FAIL:
242 if (!attempt_to_shrink(t, info, args, env)) {
243 ti->status = THEFT_TRIAL_ERROR;
244 *cres = cb(ti, env);
245 return false;
246 }
247 r->fail++;
248 *cres = report_on_failure(t, info, ti, cb, env);
249 break;
250 case THEFT_TRIAL_SKIP:
251 *cres = cb(ti, env);
252 r->skip++;
253 break;
254 case THEFT_TRIAL_DUP:
255 /* user callback should not return this; fall through */
256 case THEFT_TRIAL_ERROR:
257 *cres = cb(ti, env);
258 free_args(info, args, env);
259 return false;
260 }
261 return true;
262 }
263
264 static void free_args(struct theft_propfun_info *info,
265 void **args, void *env) {
266 for (int i = 0; i < info->arity; i++) {
267 theft_free_cb *fcb = info->type_info[i]->free;
268 if (fcb && args[i] != THEFT_SKIP) {
269 fcb(args[i], env);
270 }
271 }
272 }
273
274 void theft_free(struct theft *t) {
275 if (t->bloom) {
276 theft_bloom_dump(t->bloom);
277 theft_bloom_free(t->bloom);
278 t->bloom = NULL;
279 }
280 theft_mt_free(t->mt);
281 free(t);
282 }
283
284 /* Actually call the property function. Its number of arguments is not
285 * constrained by the typedef, but will be defined at the call site
286 * here. (If info->arity is wrong, it will probably crash.) */
287 static theft_trial_res
288 call_fun(struct theft_propfun_info *info, void **args) {
289 theft_trial_res res = THEFT_TRIAL_ERROR;
290 switch (info->arity) {
291 case 1:
292 res = info->fun(args[0]);
293 break;
294 case 2:
295 res = info->fun(args[0], args[1]);
296 break;
297 case 3:
298 res = info->fun(args[0], args[1], args[2]);
299 break;
300 case 4:
301 res = info->fun(args[0], args[1], args[2], args[3]);
302 break;
303 case 5:
304 res = info->fun(args[0], args[1], args[2], args[3], args[4]);
305 break;
306 case 6:
307 res = info->fun(args[0], args[1], args[2], args[3], args[4],
308 args[5]);
309 break;
310 case 7:
311 res = info->fun(args[0], args[1], args[2], args[3], args[4],
312 args[5], args[6]);
313 break;
314 case 8:
315 res = info->fun(args[0], args[1], args[2], args[3], args[4],
316 args[5], args[6], args[7]);
317 break;
318 case 9:
319 res = info->fun(args[0], args[1], args[2], args[3], args[4],
320 args[5], args[6], args[7], args[8]);
321 break;
322 case 10:
323 res = info->fun(args[0], args[1], args[2], args[3], args[4],
324 args[5], args[6], args[7], args[8], args[9]);
325 break;
326 /* ... */
327 default:
328 return THEFT_TRIAL_ERROR;
329 }
330 return res;
331 }
332
333 /* Attempt to instantiate arguments, starting with the current seed. */
334 static all_gen_res_t
335 gen_all_args(theft *t, struct theft_propfun_info *info,
336 theft_seed seed, void *args[THEFT_MAX_ARITY], void *env) {
337 for (int i = 0; i < info->arity; i++) {
338 struct theft_type_info *ti = info->type_info[i];
339 void *p = ti->alloc(t, seed, env);
340 if (p == THEFT_SKIP || p == THEFT_ERROR) {
341 for (int j = 0; j < i; j++) {
342 ti->free(args[j], env);
343 }
344 if (p == THEFT_SKIP) {
345 return ALL_GEN_SKIP;
346 } else {
347 return ALL_GEN_ERROR;
348 }
349 } else {
350 args[i] = p;
351 }
352 seed = theft_random(t);
353 }
354
355 /* check bloom filter */
356 if (t->bloom && check_called(t, info, args, env)) {
357 return ALL_GEN_DUP;
358 }
359
360 return ALL_GEN_OK;
361 }
362
363 /* Attempt to simplify all arguments, breadth first. Continue as long as
364 * progress is made, i.e., until a local minima is reached. */
365 static bool
366 attempt_to_shrink(theft *t, struct theft_propfun_info *info,
367 void *args[], void *env) {
368 bool progress = false;
369 do {
370 progress = false;
371 for (int ai = 0; ai < info->arity; ai++) {
372 struct theft_type_info *ti = info->type_info[ai];
373 if (ti->shrink) {
374 /* attempt to simplify this argument by one step */
375 shrink_res rres = attempt_to_shrink_arg(t, info, args, env, ai);
376 switch (rres) {
377 case SHRINK_OK:
378 progress = true;
379 break;
380 case SHRINK_DEAD_END:
381 break;
382 default:
383 case SHRINK_ERROR:
384 return false;
385 }
386 }
387 }
388 } while (progress);
389
390 return true;
391 }
392
393 /* Simplify an argument by trying all of its simplification tactics, in
394 * order, and checking whether the property still fails. If it passes,
395 * then revert the simplification and try another tactic.
396 *
397 * If the bloom filter is being used (i.e., if all arguments have hash
398 * callbacks defined), then use it to skip over areas of the state
399 * space that have probably already been tried. */
400 static shrink_res
401 attempt_to_shrink_arg(theft *t, struct theft_propfun_info *info,
402 void *args[], void *env, int ai) {
403 struct theft_type_info *ti = info->type_info[ai];
404
405 for (uint32_t tactic = 0; tactic < THEFT_MAX_TACTICS; tactic++) {
406 void *cur = args[ai];
407 void *nv = ti->shrink(cur, tactic, env);
408 if (nv == THEFT_NO_MORE_TACTICS) {
409 return SHRINK_DEAD_END;
410 } else if (nv == THEFT_ERROR) {
411 return SHRINK_ERROR;
412 } else if (nv == THEFT_DEAD_END) {
413 continue; /* try next tactic */
414 }
415
416 args[ai] = nv;
417 if (t->bloom) {
418 if (check_called(t, info, args, env)) {
419 /* probably redundant */
420 if (ti->free) { ti->free(nv, env); }
421 args[ai] = cur;
422 continue;
423 } else {
424 mark_called(t, info, args, env);
425 }
426 }
427 theft_trial_res res = call_fun(info, args);
428
429 switch (res) {
430 case THEFT_TRIAL_PASS:
431 case THEFT_TRIAL_SKIP:
432 /* revert */
433 args[ai] = cur;
434 if (ti->free) { ti->free(nv, env); }
435 break;
436 case THEFT_TRIAL_FAIL:
437 if (ti->free) { ti->free(cur, env); }
438 return SHRINK_OK;
439 case THEFT_TRIAL_DUP: /* user callback should not return this */
440 case THEFT_TRIAL_ERROR:
441 return SHRINK_ERROR;
442 }
443 }
444 (void)t;
445 return SHRINK_DEAD_END;
446 }
447
448 /* Populate a buffer with hashes of all the arguments. */
449 static void get_arg_hash_buffer(theft_hash *buffer,
450 struct theft_propfun_info *info, void **args, void *env) {
451 for (int i = 0; i < info->arity; i++) {
452 buffer[i] = info->type_info[i]->hash(args[i], env);
453 }
454 }
455
456 /* Mark the tuple of argument instances as called in the bloom filter. */
457 static void mark_called(theft *t, struct theft_propfun_info *info,
458 void **args, void *env) {
459 theft_hash buffer[THEFT_MAX_ARITY];
460 get_arg_hash_buffer(buffer, info, args, env);
461 theft_bloom_mark(t->bloom, (uint8_t *)buffer,
462 info->arity * sizeof(theft_hash));
463 }
464
465 /* Check if this combination of argument instances has been called. */
466 static bool check_called(theft *t, struct theft_propfun_info *info,
467 void **args, void *env) {
468 theft_hash buffer[THEFT_MAX_ARITY];
469 get_arg_hash_buffer(buffer, info, args, env);
470 return theft_bloom_check(t->bloom, (uint8_t *)buffer,
471 info->arity * sizeof(theft_hash));
472 }
473
474 /* Print info about a failure. */
475 static theft_progress_callback_res report_on_failure(theft *t,
476 struct theft_propfun_info *info,
477 struct theft_trial_info *ti, theft_progress_cb *cb, void *env) {
478 static theft_progress_callback_res cres;
479
480 int arity = info->arity;
481 fprintf(t->out, "\n\n -- Counter-Example: %s\n",
482 info->name ? info-> name : "");
483 fprintf(t->out, " Trial %u, Seed 0x%016llx\n", ti->trial,
484 (uint64_t)ti->seed);
485 for (int i = 0; i < arity; i++) {
486 theft_print_cb *print = info->type_info[i]->print;
487 if (print) {
488 fprintf(t->out, " Argument %d:\n", i);
489 print(t->out, ti->args[i], env);
490 fprintf(t->out, "\n");
491 }
492 }
493
494 cres = cb(ti, env);
495 return cres;
496 }