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
11const char *simple_types[] = { "bool", "char", "short", "int", "float",
12 "double", "long double", "wchar_t", "void *",
13 "char *"
14};
15
16void gl(const char *c) {
17 printf(format: "%s\n", c);
18}
19
20void g(const char *c) {
21 printf(format: "%s", c);
22}
23
24void g(int i) {
25 printf(format: "%d", i);
26}
27
28int uuid = 0;
29char base_present[N_STRUCTS][N_STRUCTS];
30
31// The return type for each function when doing covariant testcase generation.
32short ret_types[N_STRUCTS][N_FUNCS*FUNCSPACING];
33
34bool 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
42void 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.
67short final_override[N_STRUCTS][N_FUNCS*FUNCSPACING];
68
69void 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(c: "struct s");
83 else
84 g(c: "class s");
85 g(i: 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(c: ": ");
98 } else
99 g(c: ", ");
100 int base_type = 1;
101 if (random()%8 == 0) {
102 // PARAM: 1/8th the bases are virtual
103 g(c: "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(c: "public "); break;
116 case 2:
117 case 3:
118 case 4:
119 case 5:
120 break;
121 case 6:
122 g(c: "private "); break;
123 case 7:
124 g(c: "protected "); break;
125 }
126 g(c: "s");
127 add_bases(s, base);
128 bases[n_bases] = base;
129 base_present[s][base] = base_type;
130 ++n_bases;
131 g(i: base);
132 old_base = base;
133 }
134 }
135 gl(c: " {");
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(c: " "); g(c: simple_types[t]); g(c: " field"); g(i); gl(c: ";");
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(format: " // 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(format: " // 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(c: " virtual s"); g(i: ret_type); g(c: "* fun");
174 } else
175 g(c: " virtual void fun");
176 g(i: fn); g(c: "(char *t) { mix(\"vfn this offset\", (char *)this - t); mix(\"vfn uuid\", "); g(i: ++uuid);
177 if (ret_type)
178 gl(c: "); return 0; }");
179 else
180 gl(c: "); }");
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(format: " // 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(format: " // 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(format: " // 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(format: " // 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(c: " virtual s"); g(i: ret_type); g(c: "* fun");
246 } else
247 g(c: " virtual void fun");
248 g(i: fn); g(c: "(char *t) { mix(\"vfn this offset\", (char *)this - t); mix(\"vfn uuid\", "); g(i: ++uuid);
249 if (ret_type)
250 gl(c: "); return 0; }");
251 else
252 gl(c: "); }");
253 final_override[s][fn] = s;
254 }
255 }
256
257 gl(c: "public:");
258 gl(c: " void calc(char *t) {");
259
260 // mix in the type number
261 g(c: " mix(\"type num\", "); g(i: s); gl(c: ");");
262 // mix in the size
263 g(c: " mix(\"type size\", sizeof (s"); g(i: s); gl(c: "));");
264 // mix in the this offset
265 gl(c: " 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(c: " 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(c: " calc_s"); g(i: bases[i]); gl(c: "(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(c: " if ((char *)dynamic_cast<s"); g(i: bases[i]); gl(c: "*>(this))");
282 g(c: " mix(\"base dyn cast\", t - (char *)dynamic_cast<s"); g(i: bases[i]); gl(c: "*>(this));");
283 g(c: " else mix(\"no dyncast\", "); g(i: ++uuid); gl(c: ");");
284 }
285 }
286
287 /* check field layout */
288 for (int i = 0; i < n_fields; ++i) {
289 g(c: " mix(\"field offset\", (char *)&field"); g(i); gl(c: " - (char *)this);");
290 }
291 if (n_fields == 0) {
292 g(c: " mix(\"no fields\", "); g(i: ++uuid); gl(c: ");");
293 }
294
295 /* check functions */
296 for (int i = 0; i < n_funcs; ++i) {
297 g(c: " fun"); g(i: funcs[i]); gl(c: "(t);");
298 }
299 if (n_funcs == 0) {
300 g(c: " mix(\"no funcs\", "); g(i: ++uuid); gl(c: ");");
301 }
302
303 gl(c: " }");
304
305 // default ctor
306 g(c: " s"); g(i: s); g(c: "() ");
307 first_base = true;
308 for (int i = 0; i < n_bases; ++i) {
309 if (first_base) {
310 g(c: ": ");
311 first_base = false;
312 } else
313 g(c: ", ");
314 g(c: "s"); g(i: bases[i]); g(c: "((char *)this)");
315 }
316 gl(c: " { calc((char *)this); }");
317 g(c: " ~s"); g(i: s); gl(c: "() { calc((char *)this); }");
318
319 // ctor with this to the complete object
320 g(c: " s"); g(i: s); gl(c: "(char *t) { calc(t); }");
321 g(c: " void calc_s"); g(i: s); gl(c: "(char *t) { calc(t); }");
322 g(c: "} a"); g(i: s); gl(c: ";");
323}
324
325main(int argc, char **argv) {
326 unsigned seed = 0;
327 char state[16];
328 if (argc > 1)
329 seed = atol(nptr: argv[1]);
330
331 initstate(seed: seed, statebuf: state, statelen: sizeof(state));
332 gl(c: "extern \"C\" int printf(const char *...);");
333 gl(c: "");
334 gl(c: "long long sum;");
335 gl(c: "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(c: " printf(\"%s: %lld\\n\", desc, i);");
339 gl(c: " sum += ((sum ^ i) << 3) + (sum<<1) - i;");
340 gl(c: "}");
341 gl(c: "");
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(s: i);
346 gl(c: "int main() {");
347 gl(c: " printf(\"%llx\\n\", sum);");
348 gl(c: "}");
349 return 0;
350}
351

source code of clang/utils/VtableTest/gen.cc