utils/VtableTest/gen.cc

#include <stdio.h>
#include <stdlib.h>

#define N_FIELDS 7
#define N_FUNCS 128
#define FUNCSPACING 20
#define N_STRUCTS 180 /* 1280 */
#define N_BASES 6
#define COVARIANT 0

const char *simple_types[] = { "bool", "char", "short", "int", "float",
			       "double", "long double", "wchar_t", "void *",
			       "char *"
};

void gl(const char *c) {
  printf("%s\n", c);
}

void g(const char *c) {
  printf("%s", c);
}

void g(int i) {
  printf("%d", i);
}

int uuid = 0;
char base_present[N_STRUCTS][N_STRUCTS];
char funcs_present[N_STRUCTS][N_FUNCS*FUNCSPACING];

// The return type for each function when doing covariant testcase generation.
short ret_types[N_STRUCTS][N_FUNCS*FUNCSPACING];

bool is_ambiguous(int s, int base) {
  for (int i = 0; i < N_STRUCTS; ++i) {
    if ((base_present[base][i] & base_present[s][i]) == 1)
      return true;
  }
  return false;
}

void add_bases(int s, int base) {
  for (int i = 0; i < N_STRUCTS; ++i)
    base_present[s][i] |= base_present[base][i];
  if (!COVARIANT)
    return;
  for (int i = 0; i < N_FUNCS*FUNCSPACING; ++i) {
    if (!ret_types[base][i])
      continue;
    if (!ret_types[s][i]) {
      ret_types[s][i] = ret_types[base][i];
      continue;
    }
    if (base_present[ret_types[base][i]][ret_types[s][i]])
      // If the return type of the function from this base dominates
      ret_types[s][i] = ret_types[base][i];
    if (base_present[ret_types[s][i]][ret_types[base][i]])
      // If a previous base dominates
      continue;
    // If neither dominates, we'll use this class.
    ret_types[s][i] = s;
  }
}

// This contains the class that has the final override for
// each class, for each function.
short final_override[N_STRUCTS][N_FUNCS*FUNCSPACING];

void gs(int s) {
  bool polymorphic = false;

  static int bases[N_BASES];
  int i_bases = random() % (N_BASES*2);
  if (i_bases >= N_BASES)
    // PARAM: 1/2 of all clases should have no bases
    i_bases = 0;
  int n_bases = 0;
  bool first_base = true;
  
  // PARAM: 3/4 of all should be class, the rest are structs
  if (random() % 4 == 0)
    g("struct s");
  else
    g("class s");
  g(s);
  int old_base = -1;
  if (s == 0 || s == 1)
    i_bases = 0;
  while (i_bases) {
    --i_bases;
    int base = random() % (s-1) + 1;
    if (!base_present[s][base]) {
      if (is_ambiguous(s, base))
	continue;
      if (first_base) {
	first_base = false;
	g(": ");
      } else
	g(", ");
      int base_type = 1;
      if (random()%8 == 0) {
	// PARAM: 1/8th the bases are virtual
	g("virtual ");
        // We have a vtable and rtti, but technically we're not polymorphic
	// polymorphic = true;
	base_type = 3;
      }
      // PARAM: 1/4 are public, 1/8 are privare, 1/8 are protected, the reset, default
      int base_protection = 0;
      if (!COVARIANT)
        base_protection = random()%8;
      switch (base_protection) {
      case 0:
      case 1:
	g("public "); break;
      case 2:
      case 3:
      case 4:
      case 5:
	break;
      case 6:
	g("private "); break;
      case 7:
	g("protected "); break;
      }
      g("s");
      add_bases(s, base);
      bases[n_bases] = base;
      base_present[s][base] = base_type;
      ++n_bases;
      g(base);
      old_base = base;
    }
  }
  gl(" {");

  /* Fields */
  int n_fields = N_FIELDS == 0 ? 0 : random() % (N_FIELDS*4);
  // PARAM: 3/4 of all structs should have no members
  if (n_fields >= N_FIELDS)
    n_fields = 0;
  for (int i = 0; i < n_fields; ++i) {
    int t = random() % (sizeof(simple_types) / sizeof(simple_types[0]));
    g("  "); g(simple_types[t]); g(" field"); g(i); gl(";");
  }

  /* Virtual functions */
  static int funcs[N_FUNCS*FUNCSPACING];
  // PARAM: 1/2 of all structs should have no virtual functions
  int n_funcs = random() % (N_FUNCS*2);
  if (n_funcs > N_FUNCS)
    n_funcs = 0;
  int old_func = -1;
  for (int i = 0; i < n_funcs; ++i) {
    int fn = old_func + random() % FUNCSPACING + 1;
    funcs[i] = fn;
    int ret_type = 0;
    if (COVARIANT) {
      ret_type = random() % s + 1;
      if (!base_present[s][ret_type]
          || !base_present[ret_type][ret_types[s][fn]])
        if (ret_types[s][fn]) {
          printf("  // Found one for s%d for s%d* fun%d.\n", s,
                 ret_types[s][fn], fn);
          ret_type = ret_types[s][fn];
        } else
          ret_type = s;
      else
        printf("  // Wow found one for s%d for fun%d.\n", s, fn);
      ret_types[s][fn] = ret_type;
    }
    if (ret_type) {
      g("  virtual s"); g(ret_type); g("* fun");
    } else
      g("  virtual void fun");
    g(fn); g("(char *t) { mix(\"vfn this offset\", (char *)this - t); mix(\"vfn uuid\", "); g(++uuid);
    if (ret_type)
      gl("); return 0; }");
    else
      gl("); }");
    funcs_present[s][fn] = 1;
    final_override[s][fn] = s;
    old_func = fn;
  }

  // Add required overriders for correctness
  for (int i = 0; i < n_bases; ++i) {
    // For each base
    int base = bases[i];
    for (int fn = 0; fn < N_FUNCS*FUNCSPACING; ++fn) {
      // For each possible function
      int new_base = final_override[base][fn];
      if (new_base == 0)
        // If the base didn't have a final overrider, skip
        continue;

      int prev_base = final_override[s][fn];
      if (prev_base == s)
        // Skip functions defined in this class
        continue;

      // If we don't want to change the info, skip
      if (prev_base == new_base)
        continue;
      
      if (prev_base == 0) {
        // record the final override
        final_override[s][fn] = new_base;
        continue;
      }
        
      if (base_present[prev_base][new_base]) {
        // The previous base dominates the new base, no update necessary
        printf("  // No override for fun%d in s%d as s%d dominates s%d.\n",
               fn, s, prev_base, new_base);
        continue;
      }

      if (base_present[new_base][prev_base]) {
        // The new base dominates the old base, no override necessary
        printf("  // No override for fun%d in s%d as s%d dominates s%d.\n",
               fn, s, new_base, prev_base);
        // record the final override
        final_override[s][fn] = new_base;
        continue;
      }

      printf("  // Found we needed override for fun%d in s%d.\n", fn, s);

      // record the final override
      funcs[n_funcs++] = fn;
      if (n_funcs == (N_FUNCS*FUNCSPACING-1))
        abort();
      int ret_type = 0;
      if (COVARIANT) {
        if (!ret_types[s][fn]) {
          ret_types[s][fn] = ret_type = s;
        } else {
          ret_type = ret_types[s][fn];
          if (ret_type != s)
            printf("  // Calculated return type in s%d as s%d* fun%d.\n",
                   s, ret_type, fn);
        }
      }
      if (ret_type) {
        g("  virtual s"); g(ret_type); g("* fun");
      } else
        g("  virtual void fun");
      g(fn); g("(char *t) { mix(\"vfn this offset\", (char *)this - t); mix(\"vfn uuid\", "); g(++uuid);
      if (ret_type)
        gl("); return 0; }");
      else
        gl("); }");
      funcs_present[s][fn] = 1;
      final_override[s][fn] = s;
    }
  }

  gl("public:");
  gl("  void calc(char *t) {");

  // mix in the type number
  g("    mix(\"type num\", "); g(s); gl(");");
  // mix in the size
  g("    mix(\"type size\", sizeof (s"); g(s); gl("));");
  // mix in the this offset
  gl("    mix(\"subobject offset\", (char *)this - t);");
  if (n_funcs)
    polymorphic = true;
  if (polymorphic) {
    // mix in offset to the complete object under construction
    gl("    mix(\"real top v current top\", t - (char *)dynamic_cast<void*>(this));");
  }

  /* check base layout and overrides */
  for (int i = 0; i < n_bases; ++i) {
    g("    calc_s"); g(bases[i]); gl("(t);");
  }

  if (polymorphic) {
    /* check dynamic_cast to each direct base */
    for (int i = 0; i < n_bases; ++i) {
      g("    if ((char *)dynamic_cast<s"); g(bases[i]); gl("*>(this))");
      g("      mix(\"base dyn cast\", t - (char *)dynamic_cast<s"); g(bases[i]); gl("*>(this));");
      g("    else mix(\"no dyncast\", "); g(++uuid); gl(");");
    }
  }

  /* check field layout */
  for (int i = 0; i < n_fields; ++i) {
    g("    mix(\"field offset\", (char *)&field"); g(i); gl(" - (char *)this);");
  }
  if (n_fields == 0) {
    g("    mix(\"no fields\", "); g(++uuid); gl(");");
  }

  /* check functions */
  for (int i = 0; i < n_funcs; ++i) {
    g("    fun"); g(funcs[i]); gl("(t);");
  }
  if (n_funcs == 0) {
    g("    mix(\"no funcs\", "); g(++uuid); gl(");");
  }

  gl("  }");

  // default ctor
  g("  s"); g(s); g("() ");
  first_base = true;
  for (int i = 0; i < n_bases; ++i) {
    if (first_base) {
      g(": ");
      first_base = false;
    } else
      g(", ");
    g("s"); g(bases[i]); g("((char *)this)");
  }
  gl(" { calc((char *)this); }");
  g("  ~s"); g(s); gl("() { calc((char *)this); }");

 // ctor with this to the complete object
  g("  s"); g(s); gl("(char *t) { calc(t); }");
  g("  void calc_s"); g(s); gl("(char *t) { calc(t); }");
  g("} a"); g(s); gl(";");
}

main(int argc, char **argv) {
  unsigned seed = 0;
  char state[16];
  if (argc > 1)
    seed = atol(argv[1]);

  initstate(seed, state, sizeof(state));
  gl("extern \"C\" int printf(const char *...);");
  gl("");
  gl("long long sum;");
  gl("void mix(const char *desc, long long i) {");
  // If this ever becomes too slow, we can remove this after we improve the
  // mixing function
  gl("  printf(\"%s: %lld\\n\", desc, i);");
  gl("  sum += ((sum ^ i) << 3) + (sum<<1) - i;");
  gl("}");
  gl("");
  // PARAM: Randomly size testcases or large testcases?
  int n_structs = /* random() % */ N_STRUCTS;
  for (int i = 1; i < n_structs; ++i)
    gs(i);
  gl("int main() {");
  gl("  printf(\"%llx\\n\", sum);");
  gl("}");
  return 0;
}