1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define N_FIELDS 7
5 #define N_FUNCS 128
6 #define FUNCSPACING 20
7 #define N_STRUCTS 180 /* 1280 */
8 #define N_BASES 6
9 #define COVARIANT 0
10
11 const char *simple_types[] = { "bool", "char", "short", "int", "float",
12 "double", "long double", "wchar_t", "void *",
13 "char *"
14 };
15
gl(const char * c)16 void gl(const char *c) {
17 printf("%s\n", c);
18 }
19
g(const char * c)20 void g(const char *c) {
21 printf("%s", c);
22 }
23
g(int i)24 void g(int i) {
25 printf("%d", i);
26 }
27
28 int uuid = 0;
29 char base_present[N_STRUCTS][N_STRUCTS];
30
31 // The return type for each function when doing covariant testcase generation.
32 short ret_types[N_STRUCTS][N_FUNCS*FUNCSPACING];
33
is_ambiguous(int s,int base)34 bool is_ambiguous(int s, int base) {
35 for (int i = 0; i < N_STRUCTS; ++i) {
36 if ((base_present[base][i] & base_present[s][i]) == 1)
37 return true;
38 }
39 return false;
40 }
41
add_bases(int s,int base)42 void add_bases(int s, int base) {
43 for (int i = 0; i < N_STRUCTS; ++i)
44 base_present[s][i] |= base_present[base][i];
45 if (!COVARIANT)
46 return;
47 for (int i = 0; i < N_FUNCS*FUNCSPACING; ++i) {
48 if (!ret_types[base][i])
49 continue;
50 if (!ret_types[s][i]) {
51 ret_types[s][i] = ret_types[base][i];
52 continue;
53 }
54 if (base_present[ret_types[base][i]][ret_types[s][i]])
55 // If the return type of the function from this base dominates
56 ret_types[s][i] = ret_types[base][i];
57 if (base_present[ret_types[s][i]][ret_types[base][i]])
58 // If a previous base dominates
59 continue;
60 // If neither dominates, we'll use this class.
61 ret_types[s][i] = s;
62 }
63 }
64
65 // This contains the class that has the final override for
66 // each class, for each function.
67 short final_override[N_STRUCTS][N_FUNCS*FUNCSPACING];
68
gs(int s)69 void gs(int s) {
70 bool polymorphic = false;
71
72 static int bases[N_BASES];
73 int i_bases = random() % (N_BASES*2);
74 if (i_bases >= N_BASES)
75 // PARAM: 1/2 of all clases should have no bases
76 i_bases = 0;
77 int n_bases = 0;
78 bool first_base = true;
79
80 // PARAM: 3/4 of all should be class, the rest are structs
81 if (random() % 4 == 0)
82 g("struct s");
83 else
84 g("class s");
85 g(s);
86 int old_base = -1;
87 if (s == 0 || s == 1)
88 i_bases = 0;
89 while (i_bases) {
90 --i_bases;
91 int base = random() % (s-1) + 1;
92 if (!base_present[s][base]) {
93 if (is_ambiguous(s, base))
94 continue;
95 if (first_base) {
96 first_base = false;
97 g(": ");
98 } else
99 g(", ");
100 int base_type = 1;
101 if (random()%8 == 0) {
102 // PARAM: 1/8th the bases are virtual
103 g("virtual ");
104 // We have a vtable and rtti, but technically we're not polymorphic
105 // polymorphic = true;
106 base_type = 3;
107 }
108 // PARAM: 1/4 are public, 1/8 are privare, 1/8 are protected, the reset, default
109 int base_protection = 0;
110 if (!COVARIANT)
111 base_protection = random()%8;
112 switch (base_protection) {
113 case 0:
114 case 1:
115 g("public "); break;
116 case 2:
117 case 3:
118 case 4:
119 case 5:
120 break;
121 case 6:
122 g("private "); break;
123 case 7:
124 g("protected "); break;
125 }
126 g("s");
127 add_bases(s, base);
128 bases[n_bases] = base;
129 base_present[s][base] = base_type;
130 ++n_bases;
131 g(base);
132 old_base = base;
133 }
134 }
135 gl(" {");
136
137 /* Fields */
138 int n_fields = N_FIELDS == 0 ? 0 : random() % (N_FIELDS*4);
139 // PARAM: 3/4 of all structs should have no members
140 if (n_fields >= N_FIELDS)
141 n_fields = 0;
142 for (int i = 0; i < n_fields; ++i) {
143 int t = random() % (sizeof(simple_types) / sizeof(simple_types[0]));
144 g(" "); g(simple_types[t]); g(" field"); g(i); gl(";");
145 }
146
147 /* Virtual functions */
148 static int funcs[N_FUNCS*FUNCSPACING];
149 // PARAM: 1/2 of all structs should have no virtual functions
150 int n_funcs = random() % (N_FUNCS*2);
151 if (n_funcs > N_FUNCS)
152 n_funcs = 0;
153 int old_func = -1;
154 for (int i = 0; i < n_funcs; ++i) {
155 int fn = old_func + random() % FUNCSPACING + 1;
156 funcs[i] = fn;
157 int ret_type = 0;
158 if (COVARIANT) {
159 ret_type = random() % s + 1;
160 if (!base_present[s][ret_type]
161 || !base_present[ret_type][ret_types[s][fn]])
162 if (ret_types[s][fn]) {
163 printf(" // Found one for s%d for s%d* fun%d.\n", s,
164 ret_types[s][fn], fn);
165 ret_type = ret_types[s][fn];
166 } else
167 ret_type = s;
168 else
169 printf(" // Wow found one for s%d for fun%d.\n", s, fn);
170 ret_types[s][fn] = ret_type;
171 }
172 if (ret_type) {
173 g(" virtual s"); g(ret_type); g("* fun");
174 } else
175 g(" virtual void fun");
176 g(fn); g("(char *t) { mix(\"vfn this offset\", (char *)this - t); mix(\"vfn uuid\", "); g(++uuid);
177 if (ret_type)
178 gl("); return 0; }");
179 else
180 gl("); }");
181 final_override[s][fn] = s;
182 old_func = fn;
183 }
184
185 // Add required overriders for correctness
186 for (int i = 0; i < n_bases; ++i) {
187 // For each base
188 int base = bases[i];
189 for (int fn = 0; fn < N_FUNCS*FUNCSPACING; ++fn) {
190 // For each possible function
191 int new_base = final_override[base][fn];
192 if (new_base == 0)
193 // If the base didn't have a final overrider, skip
194 continue;
195
196 int prev_base = final_override[s][fn];
197 if (prev_base == s)
198 // Skip functions defined in this class
199 continue;
200
201 // If we don't want to change the info, skip
202 if (prev_base == new_base)
203 continue;
204
205 if (prev_base == 0) {
206 // record the final override
207 final_override[s][fn] = new_base;
208 continue;
209 }
210
211 if (base_present[prev_base][new_base]) {
212 // The previous base dominates the new base, no update necessary
213 printf(" // No override for fun%d in s%d as s%d dominates s%d.\n",
214 fn, s, prev_base, new_base);
215 continue;
216 }
217
218 if (base_present[new_base][prev_base]) {
219 // The new base dominates the old base, no override necessary
220 printf(" // No override for fun%d in s%d as s%d dominates s%d.\n",
221 fn, s, new_base, prev_base);
222 // record the final override
223 final_override[s][fn] = new_base;
224 continue;
225 }
226
227 printf(" // Found we needed override for fun%d in s%d.\n", fn, s);
228
229 // record the final override
230 funcs[n_funcs++] = fn;
231 if (n_funcs == (N_FUNCS*FUNCSPACING-1))
232 abort();
233 int ret_type = 0;
234 if (COVARIANT) {
235 if (!ret_types[s][fn]) {
236 ret_types[s][fn] = ret_type = s;
237 } else {
238 ret_type = ret_types[s][fn];
239 if (ret_type != s)
240 printf(" // Calculated return type in s%d as s%d* fun%d.\n",
241 s, ret_type, fn);
242 }
243 }
244 if (ret_type) {
245 g(" virtual s"); g(ret_type); g("* fun");
246 } else
247 g(" virtual void fun");
248 g(fn); g("(char *t) { mix(\"vfn this offset\", (char *)this - t); mix(\"vfn uuid\", "); g(++uuid);
249 if (ret_type)
250 gl("); return 0; }");
251 else
252 gl("); }");
253 final_override[s][fn] = s;
254 }
255 }
256
257 gl("public:");
258 gl(" void calc(char *t) {");
259
260 // mix in the type number
261 g(" mix(\"type num\", "); g(s); gl(");");
262 // mix in the size
263 g(" mix(\"type size\", sizeof (s"); g(s); gl("));");
264 // mix in the this offset
265 gl(" mix(\"subobject offset\", (char *)this - t);");
266 if (n_funcs)
267 polymorphic = true;
268 if (polymorphic) {
269 // mix in offset to the complete object under construction
270 gl(" mix(\"real top v current top\", t - (char *)dynamic_cast<void*>(this));");
271 }
272
273 /* check base layout and overrides */
274 for (int i = 0; i < n_bases; ++i) {
275 g(" calc_s"); g(bases[i]); gl("(t);");
276 }
277
278 if (polymorphic) {
279 /* check dynamic_cast to each direct base */
280 for (int i = 0; i < n_bases; ++i) {
281 g(" if ((char *)dynamic_cast<s"); g(bases[i]); gl("*>(this))");
282 g(" mix(\"base dyn cast\", t - (char *)dynamic_cast<s"); g(bases[i]); gl("*>(this));");
283 g(" else mix(\"no dyncast\", "); g(++uuid); gl(");");
284 }
285 }
286
287 /* check field layout */
288 for (int i = 0; i < n_fields; ++i) {
289 g(" mix(\"field offset\", (char *)&field"); g(i); gl(" - (char *)this);");
290 }
291 if (n_fields == 0) {
292 g(" mix(\"no fields\", "); g(++uuid); gl(");");
293 }
294
295 /* check functions */
296 for (int i = 0; i < n_funcs; ++i) {
297 g(" fun"); g(funcs[i]); gl("(t);");
298 }
299 if (n_funcs == 0) {
300 g(" mix(\"no funcs\", "); g(++uuid); gl(");");
301 }
302
303 gl(" }");
304
305 // default ctor
306 g(" s"); g(s); g("() ");
307 first_base = true;
308 for (int i = 0; i < n_bases; ++i) {
309 if (first_base) {
310 g(": ");
311 first_base = false;
312 } else
313 g(", ");
314 g("s"); g(bases[i]); g("((char *)this)");
315 }
316 gl(" { calc((char *)this); }");
317 g(" ~s"); g(s); gl("() { calc((char *)this); }");
318
319 // ctor with this to the complete object
320 g(" s"); g(s); gl("(char *t) { calc(t); }");
321 g(" void calc_s"); g(s); gl("(char *t) { calc(t); }");
322 g("} a"); g(s); gl(";");
323 }
324
main(int argc,char ** argv)325 main(int argc, char **argv) {
326 unsigned seed = 0;
327 char state[16];
328 if (argc > 1)
329 seed = atol(argv[1]);
330
331 initstate(seed, state, sizeof(state));
332 gl("extern \"C\" int printf(const char *...);");
333 gl("");
334 gl("long long sum;");
335 gl("void mix(const char *desc, long long i) {");
336 // If this ever becomes too slow, we can remove this after we improve the
337 // mixing function
338 gl(" printf(\"%s: %lld\\n\", desc, i);");
339 gl(" sum += ((sum ^ i) << 3) + (sum<<1) - i;");
340 gl("}");
341 gl("");
342 // PARAM: Randomly size testcases or large testcases?
343 int n_structs = /* random() % */ N_STRUCTS;
344 for (int i = 1; i < n_structs; ++i)
345 gs(i);
346 gl("int main() {");
347 gl(" printf(\"%llx\\n\", sum);");
348 gl("}");
349 return 0;
350 }
351