• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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