fzy
terminal fuzzy finder picker
git clone https://9o.is/git/fzy.git
theft_types.h
(7220B)
1 #ifndef THEFT_TYPES_H
2 #define THEFT_TYPES_H
3
4 /* A pseudo-random number/seed, used to generate instances. */
5 typedef uint64_t theft_seed;
6
7 /* A hash of an instance. */
8 typedef uint64_t theft_hash;
9
10 /* These are opaque, as far as the API is concerned. */
11 struct theft_bloom; /* bloom filter */
12 struct theft_mt; /* mersenne twister PRNG */
13
14 /* Struct for property-testing state. */
15 struct theft {
16 FILE *out;
17 theft_seed seed;
18 uint8_t requested_bloom_bits;
19 struct theft_bloom *bloom; /* bloom filter */
20 struct theft_mt *mt; /* random number generator */
21 };
22
23 /* Special sentinel values returned instead of instance pointers. */
24 #define THEFT_SKIP ((void *)-1)
25 #define THEFT_ERROR ((void *)-2)
26 #define THEFT_DEAD_END ((void *)-1)
27 #define THEFT_NO_MORE_TACTICS ((void *)-3)
28
29 /* Explicitly disable using the bloom filter.
30 * Note that if you do this, you must be sure your simplify function
31 * *always* returns a simpler value, or it will loop forever. */
32 #define THEFT_BLOOM_DISABLE ((uint8_t)-1)
33
34 /* Allocate and return an instance of the type, based on a known
35 * pseudo-random number seed. To get additional seeds, use
36 * theft_random(t); this stream of numbers will be deterministic, so if
37 * the alloc callback is constructed appropriately, an identical
38 * instance can be constructed later from the same initial seed.
39 *
40 * Returns a pointer to the instance, THEFT_ERROR, or THEFT_SKIP. */
41 typedef void *(theft_alloc_cb)(struct theft *t, theft_seed seed, void *env);
42
43 /* Free an instance. */
44 typedef void (theft_free_cb)(void *instance, void *env);
45
46 /* Hash an instance. Used to skip combinations of arguments which
47 * have probably already been checked. */
48 typedef theft_hash (theft_hash_cb)(void *instance, void *env);
49
50 /* Attempt to shrink an instance to a simpler instance.
51 *
52 * For a given INSTANCE, there are likely to be multiple ways in which
53 * it can be simplified. For example, a list of unsigned ints could have
54 * the first element decremented, divided by 2, or dropped. This
55 * callback should return a pointer to a freshly allocated, simplified
56 * instance, or should return THEFT_DEAD_END to indicate that the
57 * instance cannot be simplified further by this method.
58 *
59 * These tactics will be lazily explored breadth-first, to
60 * try to find simpler versions of arguments that cause the
61 * property to no longer hold.
62 *
63 * If this callback is NULL, it is equivalent to always returning
64 * THEFT_NO_MORE_TACTICS. */
65 typedef void *(theft_shrink_cb)(void *instance, uint32_t tactic, void *env);
66
67 /* Print INSTANCE to output stream F.
68 * Used for displaying counter-examples. Can be NULL. */
69 typedef void (theft_print_cb)(FILE *f, void *instance, void *env);
70
71 /* Result from a single trial. */
72 typedef enum {
73 THEFT_TRIAL_PASS, /* property held */
74 THEFT_TRIAL_FAIL, /* property contradicted */
75 THEFT_TRIAL_SKIP, /* user requested skip; N/A */
76 THEFT_TRIAL_DUP, /* args probably already tried */
77 THEFT_TRIAL_ERROR, /* unrecoverable error, halt */
78 } theft_trial_res;
79
80 /* A test property function. Arguments must match the types specified by
81 * theft_cfg.type_info, or the result will be undefined. For example, a
82 * propfun `prop_foo(A x, B y, C z)` must have a type_info array of
83 * `{ info_A, info_B, info_C }`.
84 *
85 * Should return:
86 * THEFT_TRIAL_PASS if the property holds,
87 * THEFT_TRIAL_FAIL if a counter-example is found,
88 * THEFT_TRIAL_SKIP if the combination of args isn't applicable,
89 * or THEFT_TRIAL_ERROR if the whole run should be halted. */
90 typedef theft_trial_res (theft_propfun)( /* arguments unconstrained */ );
91
92 /* Callbacks used for testing with random instances of a type.
93 * For more information, see comments on their typedefs. */
94 struct theft_type_info {
95 /* Required: */
96 theft_alloc_cb *alloc; /* gen random instance from seed */
97
98 /* Optional, but recommended: */
99 theft_free_cb *free; /* free instance */
100 theft_hash_cb *hash; /* instance -> hash */
101 theft_shrink_cb *shrink; /* shrink instance */
102 theft_print_cb *print; /* fprintf instance */
103 };
104
105 /* Result from an individual trial. */
106 struct theft_trial_info {
107 const char *name; /* property name */
108 int trial; /* N'th trial */
109 theft_seed seed; /* Seed used */
110 theft_trial_res status; /* Run status */
111 uint8_t arity; /* Number of arguments */
112 void **args; /* Arguments used */
113 };
114
115 /* Whether to keep running trials after N failures/skips/etc. */
116 typedef enum {
117 THEFT_PROGRESS_CONTINUE, /* keep running trials */
118 THEFT_PROGRESS_HALT, /* no need to continue */
119 } theft_progress_callback_res;
120
121 /* Handle test results.
122 * Can be used to halt after too many failures, print '.' after
123 * every N trials, etc. */
124 typedef theft_progress_callback_res
125 (theft_progress_cb)(struct theft_trial_info *info, void *env);
126
127 /* Result from a trial run. */
128 typedef enum {
129 THEFT_RUN_PASS = 0, /* no failures */
130 THEFT_RUN_FAIL = 1, /* 1 or more failures */
131 THEFT_RUN_ERROR = 2, /* an error occurred */
132 THEFT_RUN_ERROR_BAD_ARGS = -1, /* API misuse */
133 /* Missing required callback for 1 or more types */
134 THEFT_RUN_ERROR_MISSING_CALLBACK = -2,
135 } theft_run_res;
136
137 /* Optional report from a trial run; same meanings as theft_trial_res. */
138 struct theft_trial_report {
139 size_t pass;
140 size_t fail;
141 size_t skip;
142 size_t dup;
143 };
144
145 /* Configuration struct for a theft test.
146 * In C99, this struct can be specified as a literal, like this:
147 *
148 * struct theft_cfg cfg = {
149 * .name = "example",
150 * .fun = prop_fun,
151 * .type_info = { type_arg_a, type_arg_b },
152 * .seed = 0x7he5eed,
153 * };
154 *
155 * and omitted fields will be set to defaults.
156 * */
157 struct theft_cfg {
158 /* Property function under test, and info about its arguments.
159 * The function is called with as many arguments are there
160 * are values in TYPE_INFO, so it can crash if that is wrong. */
161 theft_propfun *fun;
162 struct theft_type_info *type_info[THEFT_MAX_ARITY];
163
164 /* -- All fields after this point are optional. -- */
165
166 /* Property name, displayed in test runner output. */
167 const char *name;
168
169 /* Array of seeds to always run, and its length.
170 * Can be used for regression tests. */
171 int always_seed_count; /* number of seeds */
172 theft_seed *always_seeds; /* seeds to always run */
173
174 /* Number of trials to run. Defaults to THEFT_DEF_TRIALS. */
175 int trials;
176
177 /* Progress callback, used to display progress in
178 * slow-running tests, halt early under certain conditions, etc. */
179 theft_progress_cb *progress_cb;
180
181 /* Environment pointer. This is completely opaque to theft itself,
182 * but will be passed along to all callbacks. */
183 void *env;
184
185 /* Struct to populate with more detailed test results. */
186 struct theft_trial_report *report;
187
188 /* Seed for the random number generator. */
189 theft_seed seed;
190 };
191
192 /* Internal state for incremental hashing. */
193 struct theft_hasher {
194 theft_hash accum;
195 };
196
197 #endif