1. rcrnstn/fzy
  2. deps
  3. theft
  4. theft_types.h
Browse code

Add theft

John Hawthorn authored on 03/04/2017 09:11:20
Showing 1 changed files
deps/theft/theft_types.h
History View file @ dfe82eb
1 1 
new file mode 100644
... ... 
@@ -0,0 +1,197 @@
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