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 16 void gl(const char *c) { 17 printf("%s\n", c); 18 } 19 20 void g(const char *c) { 21 printf("%s", c); 22 } 23 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 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 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 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 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
