MultiSource/Applications/d/symtab.c

   1 /*
   2   Copyright 2002-2003 John Plevyak, All Rights Reserved
   3 */
   4 #include "d.h"
   5
   6 #define INITIAL_SYMHASH_SIZE    3137
   7
   8 typedef struct D_SymHash {
   9   int           index;
  10   int           grow;
  11   Vec(D_Sym*)   syms;
  12 } D_SymHash;
  13
  14 /*
  15   How this works.  In a normal symbol table there is simply
  16   a stack of scopes representing the scoping structure of
  17   the program.  Because of speculative parsing, this symbol table
  18   also has a tree of all 'updates' representing different
  19   views of the state of scoped variables by each speculative
  20   parse state.  Periodically, when the parse state collapses
  21   to a single state (we are nolonger speculating), these changes
  22   are can be 'committed' and the changes pushed into the top
  23   level hash table.
  24
  25   All D_Scope's except the top level just have a 'll' of symbols, the
  26   top level has a 'hash'.
  27
  28   'updates' is a list of changes to symbols in other scopes.  It is
  29   searched to find the current version of a symbol with respect to the
  30   speculative parse path represented by D_Scope.
  31
  32   'up' points to the enclosing scope, it isn't used much.
  33
  34   'up_updates' is the prior scope in speculative parsing, it is used find
  35    the next D_Scope to look in for 'updates' after the current one has been
  36    searched.
  37
  38    'down' and 'down_next' are used to hold enclosing scopes, or in the
  39    case of the top level, sibling scopes (created by commmit).
  40 */
  41
  42
  43 static void
  44 symhash_add(D_SymHash *sh, D_Sym *s) {
  45   uint i, h = s->hash % sh->syms.n, n;
  46   D_Sym **v = sh->syms.v, *x;
  47   Vec(D_Sym*) vv, tv;
  48
  49   sh->index++;
  50   s->next = v[h];
  51   v[h] = s;
  52
  53   if (sh->index > sh->grow) {
  54     vv.v = sh->syms.v;
  55     vv.n = sh->syms.n;
  56     sh->syms.n = sh->grow;
  57     sh->grow = sh->grow * 2 + 1;
  58     sh->syms.v = MALLOC(sh->syms.n * sizeof(void *));
  59     memset(sh->syms.v, 0, sh->syms.n * sizeof(void *));
  60     v = sh->syms.v;
  61     n = sh->syms.n;
  62     vec_clear(&tv);
  63     for (i = 0; i < vv.n; i++)
  64       /* use temporary to preserve order */
  65       while (vv.v[i]) {
  66         x = vv.v[i];
  67         vv.v[i] = x->next;
  68         vec_add(&tv, x);
  69       }
  70       while (tv.v[i]) {
  71         x = tv.v[i];
  72         tv.v[i] = x->next;
  73         h = x->hash % n;
  74         x->next = v[h];
  75         v[h] = x;
  76       }
  77     FREE(vv.v);
  78   }
  79 }
  80
  81 static D_SymHash *
  82 new_D_SymHash() {
  83   D_SymHash *sh = MALLOC(sizeof(D_SymHash));
  84   memset(sh, 0, sizeof(D_SymHash));
  85   sh->grow = INITIAL_SYMHASH_SIZE * 2 + 1;
  86   sh->syms.n = INITIAL_SYMHASH_SIZE;
  87   sh->syms.v = MALLOC(sh->syms.n * sizeof(void *));
  88   memset(sh->syms.v, 0, sh->syms.n * sizeof(void *));
  89   return sh;
  90 }
  91
  92 static void
  93 free_D_SymHash(D_SymHash *sh) {
  94   int i;
  95   D_Sym *sym;
  96   for (i = 0; i < sh->syms.n; i++)
  97     for (; sh->syms.v[i]; sh->syms.v[i] = sym) {
  98       sym = sh->syms.v[i]->next;
  99       free_D_Sym(sh->syms.v[i]);
 100     }
 101   FREE(sh->syms.v);
 102   FREE(sh);
 103 }
 104
 105 D_Scope *
 106 new_D_Scope(D_Scope *parent) {
 107   D_Scope *st = MALLOC(sizeof(D_Scope));
 108   memset(st, 0, sizeof(D_Scope));
 109   if (parent) {
 110     st->kind = parent->kind;
 111     st->search = parent;
 112     st->up = parent;
 113     st->up_updates = parent;
 114     st->down_next = parent->down;
 115     parent->down = st;
 116   } else
 117     st->hash = new_D_SymHash();
 118   return st;
 119 }
 120
 121 D_Scope *
 122 enter_D_Scope(D_Scope *current, D_Scope *scope) {
 123   D_Scope *st = MALLOC(sizeof(D_Scope)), *parent = scope->up;
 124   memset(st, 0, sizeof(D_Scope));
 125   st->up = parent;
 126   st->kind = scope->kind;
 127   st->search = scope;
 128   st->up_updates = current;
 129   st->down_next = current->down;
 130   current->down = st;
 131   return st;
 132 }
 133
 134 void
 135 free_D_Scope(D_Scope *st, int force) {
 136   D_Scope *s;
 137   D_Sym *sym;
 138   for (; st->down; st->down = s) {
 139     s = st->down->down_next;
 140     free_D_Scope(st->down, 0);
 141   }
 142   if (st->owned_by_user && !force)
 143     return;
 144   if (st->hash)
 145     free_D_SymHash(st->hash);
 146   else
 147     for (; st->ll; st->ll = sym) {
 148       sym = st->ll->next;
 149       free_D_Sym(st->ll);
 150     }
 151   for (; st->updates; st->updates = sym) {
 152     sym = st->updates->next;
 153     free_D_Sym(st->updates);
 154   }
 155   FREE(st);
 156 }
 157
 158 static void
 159 commit_ll(D_Scope *st, D_SymHash *sh) {
 160   D_Sym *sym;
 161   if (st->search) {
 162     commit_ll(st->search, sh);
 163     for (; st->ll; st->ll = sym) {
 164       sym = st->ll->next;
 165       symhash_add(sh, st->ll);
 166     }
 167   }
 168 }
 169
 170 /* make direct links to the latest update */
 171 static void
 172 commit_update(D_Scope *st, D_SymHash *sh) {
 173   int i;
 174   D_Sym *s;
 175
 176   for (i = 0; i < sh->syms.n; i++)
 177     for (s = sh->syms.v[i]; s; s = s->next)
 178       s->update_of = current_D_Sym(st, s);
 179 }
 180
 181 /* currently only commit the top level scope */
 182 D_Scope *
 183 commit_D_Scope(D_Scope *st) {
 184   D_Scope *x = st;
 185   if (st->up)
 186     return st;
 187   while (x->search) x = x->search;
 188   commit_ll(st, x->hash);
 189   commit_update(st, x->hash);
 190   return x;
 191 }
 192
 193 D_Sym *
 194 new_D_Sym(D_Scope *st, char *name, char *end, int sizeof_D_Sym) {
 195   int len = end - name;
 196   D_Sym *s = MALLOC(sizeof_D_Sym);
 197   memset(s, 0, sizeof_D_Sym);
 198   s->name = name;
 199   s->len = len;
 200   s->hash = strhashl(name, len);
 201   if (st->hash) {
 202     symhash_add(st->hash, s);
 203   } else {
 204     s->next = st->ll;
 205     st->ll = s;
 206   }
 207   return s;
 208 }
 209
 210 void
 211 free_D_Sym(D_Sym *s) {
 212   FREE(s);
 213 }
 214
 215 D_Sym *
 216 current_D_Sym(D_Scope *st, D_Sym *sym) {
 217   D_Scope *sc;
 218   D_Sym *uu;
 219
 220   if (sym->update_of) sym = sym->update_of;
 221   /* return the last update */
 222   for (sc = st; sc; sc = sc->up_updates) {
 223     for (uu = sc->updates; uu; uu = uu->next)
 224       if (uu->update_of == sym)
 225         return uu;
 226   }
 227   return sym;
 228 }
 229
 230 D_Sym *
 231 find_sym_internal(D_Scope *top, D_Scope *cur, char *name, int len, uint h) {
 232   D_Sym *ll;
 233
 234   if (!cur)
 235     return NULL;
 236   if (cur->hash)
 237     ll = cur->hash->syms.v[h % cur->hash->syms.n];
 238   else
 239     ll = cur->ll;
 240   while (ll) {
 241     if (ll->hash == h && ll->len == len && !strncmp(ll->name, name, len))
 242       break;
 243     ll = ll->next;
 244   }
 245   if (!ll) {
 246     if (cur->search)
 247       return find_sym_internal(top, cur->search, name, len, h);
 248     return ll;
 249   }
 250   return current_D_Sym(top, ll);
 251 }
 252
 253 D_Sym *
 254 find_D_Sym(D_Scope *st, char *name, char *end) {
 255   int len = end - name;
 256   uint h = strhashl(name, len);
 257   return find_sym_internal(st, st, name, len, h);
 258 }
 259
 260 D_Sym *
 261 find_D_Sym_in_Scope(D_Scope *st, char *name, char *end) {
 262   D_Sym *ll;
 263   int len = end - name;
 264   uint h = strhashl(name, len);
 265   for (;st ; st = st->search) {
 266     if (st->hash)
 267       ll = st->hash->syms.v[h % st->hash->syms.n];
 268     else
 269       ll = st->ll;
 270     while (ll) {
 271       if (ll->hash == h && ll->len == len && !strncmp(ll->name, name, len))
 272         return ll;
 273       ll = ll->next;
 274     }
 275     if (!st->search || st->search->up != st->up)
 276       break;
 277   }
 278   return NULL;
 279 }
 280
 281 D_Sym *
 282 update_D_Sym(D_Scope *st, D_Sym *sym, int sizeof_D_Sym) {
 283   D_Sym *s;
 284
 285   sym = current_D_Sym(st, sym);
 286   s = MALLOC(sizeof_D_Sym);
 287   memcpy(s, sym, sizeof(D_Sym));
 288   if (sym->update_of) sym = sym->update_of;
 289   s->update_of = sym;
 290   s->next = st->updates;
 291   st->updates = s;
 292   return s;
 293 }
 294
 295 void
 296 print_sym(D_Sym *s) {
 297   char *c = (char*)MALLOC(s->len + 1);
 298   memcpy(c, s->name, s->len);
 299   s->name[s->len] = 0;
 300   printf("%s, ", c);
 301   FREE(c);
 302 }
 303
 304 void
 305 print_scope(D_Scope *st) {
 306   printf("SCOPE %X: ", (long)st);
 307   printf("  owned: %d, kind: %d, ", st->owned_by_user, st->kind);
 308   if (st->ll) printf("  LL\n");
 309   if (st->hash) printf("  HASH\n");
 310   if (st->hash) {
 311     int i;
 312     for (i = 0; i < st->hash->syms.n; i++)
 313       if (st->hash->syms.v[i])
 314         print_sym(st->hash->syms.v[i]);
 315   } else {
 316     D_Sym *ll = st->ll;
 317     while (ll) {
 318       print_sym(ll);
 319       ll = ll->next;
 320     }
 321   }
 322   printf("\n\n");
 323   if (st->search) print_scope(st->search);
 324 }