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("%s\n", c);
18}
19
20void g(const char *c) {
21  printf("%s", c);
22}
23
24void g(int i) {
25  printf("%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("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
325main(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