path: root/bootstrap/types.c

#include "all.h"

// set of interned types
static struct {
   int size, nbuckets;
   struct typesnode {
      struct typesnode *next;
      u32 hash;
      const struct type ty;
   } **buckets;
   char *tags;
} types;
static vec_t(const struct type *) typesvec; // insertion order

void
inittypes() {
   for (int i = 0; i < types.nbuckets; ++i) {
      for (struct typesnode *n = types.buckets[i], *next; n; n = next) {
         next = n->next;
         free(n);
      }
   }
   if (types.buckets)
      free(types.buckets);

   types.size = 0;
   types.buckets = calloc(types.nbuckets = 16, sizeof(struct typesnode *));
}

static u32
hashtype(const struct type *ty) {
   u32 h = FNV1A_INI; 

   h = fnv1ai(h, ty->t);
   h = fnv1ai(h, ty->konst);
   if (ty->t == TYfn)
      epri("");

   switch (ty->t) {
   case TYvoid: case TYbool: case TYvalist:
      break;
   case TYint: case TYfloat:
      h = fnv1az(h, ty->size);
      h = fnv1az(h, ty->align);
      h = fnv1ai(h, ty->int_signed);
      break;
   case TYptr:
   case TYslice:
      h = fnv1ai(h, ty->child->_id);
      break;
   case TYarr:
      assert(ty->child->size || ty->align == 1);
      h = fnv1ai(h, ty->child->_id);
      h = fnv1aI(h, ty->length);
      break;
   case TYfn:
      h = fnv1ai(h, ty->fn.retty->_id);
      h = fnv1ai(h, ty->fn.params.n);
      for (int i = 0; i < ty->fn.params.n; ++i)
         h = fnv1ai(h, ty->fn.params.d[i]->_id);
      break;
   case TYenum:
      h = fnv1ai(h, ty->enu.id);
      break;
   case TYstruct: case TYunion: case TYeunion:
      h = fnv1ai(h, ty->agg.id);
      break;
   }
   return h;
}

bool
typeeql(const struct type *lhs, const struct type *rhs) {
   if (lhs == rhs)
      return 1;
   if (lhs->t != rhs->t || lhs->konst != rhs->konst)
      return 0;
   switch (lhs->t) {
   case TYvoid: case TYbool: case TYvalist:
      return 1;
   case TYfloat:
      return lhs->size == rhs->size;
   case TYint:
      return lhs->size == rhs->size && lhs->int_signed == rhs->int_signed;
   case TYptr:
   case TYslice:
      return typeeql(lhs->child, rhs->child);
   case TYarr:
      return lhs->length == rhs->length && typeeql(lhs->child, rhs->child);
   case TYfn:
      if (lhs->fn.params.n != rhs->fn.params.n)
         return 0;
      if (lhs->fn.variadic != rhs->fn.variadic)
         return 0;
      for (int i = 0; i < lhs->fn.params.n; ++i)
         if (!typeeql(lhs->fn.params.d[i], rhs->fn.params.d[i]))
            return 0;
      return 1;
   case TYenum:
      return lhs->enu.id == rhs->enu.id;
   case TYstruct: case TYunion: case TYeunion:
      return lhs->agg.id == rhs->agg.id;
   }
   assert(0 && "unreachable");
}

static const struct type *
typesfind(const struct type *key) {
   u32 hash = hashtype(key);
   size_t idx = hash & (types.nbuckets - 1);
   for (struct typesnode *n = types.buckets[idx]; n; n = n->next) {
      if (n->hash == hash && typeeql(key, &n->ty))
         return &n->ty;
   }
   return NULL;
}

// !!Invariant: type should not be in the types set!
static const struct type *
typesput(const struct type *key) {
   u32 hash = hashtype(key);
   size_t idx = hash & (types.nbuckets - 1);
   struct typesnode *n = xmalloc(sizeof *n);
   types.size++;
   n->hash = hash;
   *(struct type *)&n->ty = *key;

   if (++types.size > types.nbuckets) {
      // rehash
      struct typesnode *nodes = NULL;
      for (int i = 0; i < types.nbuckets; ++i) {
         for (struct typesnode *n = types.buckets[i], *next; n; n = next) {
            next = n->next;
            n->next = nodes;
            nodes = n;
         }
      }
      types.buckets = xrealloc(types.buckets,
                              (types.nbuckets *= 2) * sizeof(struct typesnode));
      memset(types.buckets, 0, types.nbuckets * sizeof(struct typesnode));

      for (struct typesnode *next; nodes; nodes = next) {
         u32 idx = nodes->hash & (types.nbuckets - 1);
         next = nodes->next;
         nodes->next = types.buckets[idx];
         types.buckets[idx] = nodes;
      }
      idx = hash & (types.nbuckets - 1);
   }

   n->next = types.buckets[idx];
   types.buckets[idx] = n;
   return &n->ty;
}

const struct type *
interntype(struct type ty) {
   static int id;
   if (!ty.align)
      ty.align = ty.size ? ty.size : 1;
   const struct type *ty2 = typesfind(&ty);
   if (ty2)
      return ty2;
   ty._id = id++;
   ty2 = typesput(&ty);
   assert(ty2);
   vec_push(&typesvec, ty2);
   return ty2;
}

void
uninterntype(const struct type *key) {
   u32 hash = hashtype(key);
   size_t idx = hash & (types.nbuckets - 1);
   types.size--;
   for (struct typesnode *n = types.buckets[idx], *prev = NULL; n; n = n->next) {
      if (key == &n->ty) {
         if (prev) {
            prev->next = n->next;
         } else {
            types.buckets[idx] = n->next;
         }
         typesvec.data[key->_id] = NULL;
         free(n);
         break;
      }
      prev = n;
   }
}

bool
completetype(const struct type *ty) {
   if (ty->konst) return completetype(unconstify(ty));
   if (ty->t == TYvoid)
      return 0;
   if (ty->t == TYfn)
      return 0;
   if (ty->t == TYarr && ty->length < 0)
      return 0;
   if (ty->t == TYstruct || ty->t == TYunion || ty->t == TYeunion)
      return !ty->agg.fwd;
   return 1;
}

const struct type
   *ty_void, *ty_bool, *ty_f32, *ty_f64,
   *ty_i8, *ty_u8, *ty_i16, *ty_u16,
   *ty_i32, *ty_u32, *ty_i64, *ty_u64,
   *ty_int, *ty_uint, *ty_isize, *ty_usize,
   *ty_iptrint, *ty_uptrint, *ty_c_int, *ty_c_uint,
   *ty_c_char, *ty_c_schar, *ty_c_uchar, *ty_c_short,
   *ty_c_ushort, *ty_c_long, *ty_c_ulong, *ty_c_llong,
   *ty_c_ullong, *ty_valist;

void
putprimtypes(struct env *env) {
   const struct targ t = g_targ;
   const struct {
     const char *name;
     const struct type **gty;
     struct type ty;
   } types[] = {
      /* name, t, size, align (0 -> = size), ... */
      {"void", &ty_void, {TYvoid, 0, 1}},
      {"bool", &ty_bool, {TYbool, 1}},
      {"f32", &ty_f32, {TYfloat, 4, t.f32align}},
      {"f64", &ty_f64, {TYfloat, 8, t.f64align}},
#define IS .int_signed = 1
#define IU .int_signed = 0
#define A(t) _Alignof(t)
      {"i8", &ty_i8, {TYint, 1, 1, IS}},
      {"u8", &ty_u8, {TYint, 1, 1, IU}},
      {"i16", &ty_i16, {TYint, 2, 2, IS}},
      {"u16", &ty_u16, {TYint, 2, 2, IU}},
      {"i32", &ty_i32, {TYint, 4, t.i32align, IS}},
      {"u32", &ty_u32, {TYint, 4, t.i32align, IU}},
      {"i64", &ty_i64, {TYint, 8, t.i64align, IS}},
      {"u64", &ty_u64, {TYint, 8, t.i64align, IU}},
      {"int", &ty_int, {TYint, t.intsize, IS}},
      {"uint", &ty_uint, {TYint, t.intsize, IU}},
      {"isize", &ty_isize, {TYint, t.sizesize, IS}},
      {"usize", &ty_usize, {TYint, t.sizesize, IU}},
      {"iptrint", &ty_iptrint, {TYint, t.ptrsize, IS}},
      {"uptrint", &ty_uptrint, {TYint, t.ptrsize, IU}},
      {"c_char", &ty_c_char, {TYint, 1, .int_signed = t.charsigned}},
      {"c_long", &ty_c_long, {TYint, t.longsize, t.longalign, IS}},
      {"c_ulong", &ty_c_ulong, {TYint, t.longsize, t.longalign, IU}},
      {"c_llong", &ty_c_llong, {TYint, t.llongsize, t.llongalign, IS}},
      {"c_ullong", &ty_c_ullong, {TYint, t.llongsize, t.llongalign, IU}},
      {"va_list", &ty_valist, {TYvalist, t.valistsize, t.valistalign}},
#undef IS
#undef IU
   };
   
   for (int i = 0; i < ARRAY_LENGTH(types); ++i) {
      struct decl decl = {
         Dtype,
         types[i].name,
         .ty = interntype(types[i].ty),
      };
      bool ok = envput(env, &decl);
      *types[i].gty = decl.ty;
      assert(ok && "envput prim type");
   }
}

void
visittypes(void (*visitor)(const struct type *, void *), void *arg) {
   int i; const struct type *ty;
   vec_foreach(&typesvec, ty, i) {
      if (ty)
         visitor(ty, arg);
   }
}

const struct type *
constify(const struct type *ty) {
   struct type ty2 = *ty;
   if (ty->konst)
      return ty;
   if (ty2.t != TYfn)
      ty2.konst = 1;
   return interntype(ty2);
}

const struct type *
unconstify(const struct type *ty) {
   struct type ty2 = *ty;
   if (!ty->konst)
      return ty;
   ty2.konst = 0;
   return interntype(ty2);
}

const struct type *
constifychild(const struct type *ty) {
   struct type ty2 = *ty;
   const struct type *child = constify(ty->child);
   if (child == ty->child)
      return ty;
   ty2.child = child;
   return interntype(ty2);
}

const struct type *
unconstifychild(const struct type *ty) {
   struct type ty2 = *ty;
   const struct type *child = unconstify(ty->child);
   if (child == ty->child)
      return ty;
   ty2.child = child;
   return interntype(ty2);
}

static const struct type *
arraydecay(const struct type *ty) {
   struct type ty2 = *ty;

   if (ty->t != TYarr)
      return ty;
   
   ty2.t = TYptr;
   return interntype(ty2);
}

int
numtype2rank(const struct type *a) {
   a = unconstify(a);
   if (a->t == TYenum) {
      assert(a->enu.lax);
      a = a->enu.intty;
   }
   if (a->t == TYint) {
      if (a->size < g_targ.intsize || a == ty_int)
         return 0;
      if (a == ty_uint) return 1;
      if (a == ty_i32) return 2;
      if (a == ty_u32) return 3;
      if (a == ty_i64) return 4;
      if (a == ty_u64) return 5;
   }
   if (a == ty_f32) return 6;
   if (a == ty_f64) return 7;
   return -1;
}

const struct type *
rank2numtype(int r) {
   static const struct type **types[] = {
      &ty_int, &ty_uint, &ty_i32, &ty_u32,
      &ty_i64, &ty_u64, &ty_f32, &ty_f64,
   };
   assert(r >= 0 && r < ARRAY_LENGTH(types));
   return *types[r];
}

bool
isnumtype(const struct type *a) {
   return a->t == TYint || a->t == TYfloat || (a->t == TYenum && a->enu.lax);
}

// peer type resolution
const struct type *
typeof2(const struct type *a, const struct type *b) {
   if (isnumtype(a) && isnumtype(b)) {
      int ra = numtype2rank(a), rb = numtype2rank(b);
      return rank2numtype(MAX(ra, rb));
   }
   if (a == b)
      return a;
   if (unconstify(a) == b)
      return a;
   if (a == unconstify(b))
      return b;
   if (a->t == TYarr && b->t == TYarr)
      a = arraydecay(a);
   if (a->t == TYptr && b->t == TYarr)
      b = arraydecay(b);
   if (a->t == TYarr && b->t == TYptr)
      a = arraydecay(a);
   if (a->t == b->t && (a->t == TYptr || a->t == TYslice)) {
      bool akonst = a->child->konst,
           bkonst = b->child->konst;
      const struct type *uac = unconstify(a->child),
                        *ubc = unconstify(b->child);
      if (uac == ubc)
         return akonst ? a : b;
      if (uac == ty_void) {
         if (bkonst && !akonst)
            return constifychild(a);
         return a;
      }
      if (ubc == ty_void) {
         if (akonst && !bkonst)
            return constifychild(b);
         return b;
      }
      if (uac == ty_u8) {
         if (bkonst && !akonst)
            return constifychild(a);
         return a;
      }
      if (ubc == ty_u8) {
         if (akonst && !bkonst)
            return constifychild(b);
         return b;
      }

   }

   return NULL;
}


void
prialltypes(void) {
   for (int i = 0; i < types.nbuckets; ++i) {
      epri("bkt %d:\n", i);
      for (struct typesnode *n = types.buckets[i]; n; n = n->next) {
         epri("   %t : %d\n", &n->ty, hashtype(&n->ty));
      }
   }
}