MultiSource/Applications/d/symtab.c

/*
  Copyright 2002-2003 John Plevyak, All Rights Reserved
*/
#include "d.h"

#define INITIAL_SYMHASH_SIZE 	3137

typedef struct D_SymHash {
  int		index;
  int		grow;
  Vec(D_Sym*)	syms;
} D_SymHash;

/*
  How this works.  In a normal symbol table there is simply
  a stack of scopes representing the scoping structure of
  the program.  Because of speculative parsing, this symbol table
  also has a tree of all 'updates' representing different
  views of the state of scoped variables by each speculative
  parse state.  Periodically, when the parse state collapses
  to a single state (we are nolonger speculating), these changes
  are can be 'committed' and the changes pushed into the top
  level hash table.
 
  All D_Scope's except the top level just have a 'll' of symbols, the
  top level has a 'hash'.
 
  'updates' is a list of changes to symbols in other scopes.  It is
  searched to find the current version of a symbol with respect to the
  speculative parse path represented by D_Scope.

  'up' points to the enclosing scope, it isn't used much.

  'up_updates' is the prior scope in speculative parsing, it is used find
   the next D_Scope to look in for 'updates' after the current one has been
   searched.

   'down' and 'down_next' are used to hold enclosing scopes, or in the
   case of the top level, sibling scopes (created by commmit).
*/
  

static void
symhash_add(D_SymHash *sh, D_Sym *s) {
  uint i, h = s->hash % sh->syms.n, n;
  D_Sym **v = sh->syms.v, *x;
  Vec(D_Sym*) vv, tv;

  sh->index++;
  s->next = v[h];
  v[h] = s;

  if (sh->index > sh->grow) {
    vv.v = sh->syms.v;
    vv.n = sh->syms.n;
    sh->syms.n = sh->grow;
    sh->grow = sh->grow * 2 + 1;
    sh->syms.v = MALLOC(sh->syms.n * sizeof(void *));
    memset(sh->syms.v, 0, sh->syms.n * sizeof(void *));
    v = sh->syms.v;
    n = sh->syms.n;
    vec_clear(&tv);
    for (i = 0; i < vv.n; i++)
      /* use temporary to preserve order */
      while (vv.v[i]) {
	x = vv.v[i];
	vv.v[i] = x->next;
	vec_add(&tv, x);
      }
      while (tv.v[i]) {
	x = tv.v[i];
	tv.v[i] = x->next;
	h = x->hash % n;
	x->next = v[h];
	v[h] = x;
      }
    FREE(vv.v);
  }
}

static D_SymHash * 
new_D_SymHash() {
  D_SymHash *sh = MALLOC(sizeof(D_SymHash));
  memset(sh, 0, sizeof(D_SymHash));
  sh->grow = INITIAL_SYMHASH_SIZE * 2 + 1;
  sh->syms.n = INITIAL_SYMHASH_SIZE;
  sh->syms.v = MALLOC(sh->syms.n * sizeof(void *));
  memset(sh->syms.v, 0, sh->syms.n * sizeof(void *));
  return sh;
}

static void
free_D_SymHash(D_SymHash *sh) {
  int i;
  D_Sym *sym;
  for (i = 0; i < sh->syms.n; i++)
    for (; sh->syms.v[i]; sh->syms.v[i] = sym) {
      sym = sh->syms.v[i]->next; 
      free_D_Sym(sh->syms.v[i]);
    }
  FREE(sh->syms.v);
  FREE(sh);
}

D_Scope *
new_D_Scope(D_Scope *parent) {
  D_Scope *st = MALLOC(sizeof(D_Scope));
  memset(st, 0, sizeof(D_Scope));
  if (parent) {
    st->kind = parent->kind;
    st->search = parent;
    st->up = parent;
    st->up_updates = parent;
    st->down_next = parent->down;
    parent->down = st;
  } else 
    st->hash = new_D_SymHash();
  return st;
}

D_Scope *
enter_D_Scope(D_Scope *current, D_Scope *scope) {
  D_Scope *st = MALLOC(sizeof(D_Scope)), *parent = scope->up;
  memset(st, 0, sizeof(D_Scope));
  st->up = parent;
  st->kind = scope->kind;
  st->search = scope;
  st->up_updates = current;
  st->down_next = current->down;
  current->down = st;
  return st;
}

void
free_D_Scope(D_Scope *st, int force) {
  D_Scope *s;
  D_Sym *sym;
  for (; st->down; st->down = s) {
    s = st->down->down_next;
    free_D_Scope(st->down, 0);
  }
  if (st->owned_by_user && !force)
    return;
  if (st->hash)
    free_D_SymHash(st->hash);
  else
    for (; st->ll; st->ll = sym) {
      sym = st->ll->next;
      free_D_Sym(st->ll);
    }
  for (; st->updates; st->updates = sym) {
    sym = st->updates->next;
    free_D_Sym(st->updates);
  }
  FREE(st);
}

static void 
commit_ll(D_Scope *st, D_SymHash *sh) {
  D_Sym *sym;
  if (st->search) {
    commit_ll(st->search, sh);
    for (; st->ll; st->ll = sym) {
      sym = st->ll->next;
      symhash_add(sh, st->ll);
    }
  }
}

/* make direct links to the latest update */
static void 
commit_update(D_Scope *st, D_SymHash *sh) {
  int i;
  D_Sym *s;

  for (i = 0; i < sh->syms.n; i++)
    for (s = sh->syms.v[i]; s; s = s->next) 
      s->update_of = current_D_Sym(st, s);
}

/* currently only commit the top level scope */
D_Scope *
commit_D_Scope(D_Scope *st) {
  D_Scope *x = st;
  if (st->up)
    return st;
  while (x->search) x = x->search;
  commit_ll(st, x->hash);
  commit_update(st, x->hash);
  return x;
}

D_Sym *
new_D_Sym(D_Scope *st, char *name, char *end, int sizeof_D_Sym) {
  int len = end - name;
  D_Sym *s = MALLOC(sizeof_D_Sym);
  memset(s, 0, sizeof_D_Sym);
  s->name = name;
  s->len = len;
  s->hash = strhashl(name, len);
  if (st->hash) {
    symhash_add(st->hash, s);
  } else {
    s->next = st->ll;
    st->ll = s;
  }
  return s;
}

void
free_D_Sym(D_Sym *s) {
  FREE(s);
}

D_Sym *
current_D_Sym(D_Scope *st, D_Sym *sym) {
  D_Scope *sc;
  D_Sym *uu;

  if (sym->update_of) sym = sym->update_of;
  /* return the last update */
  for (sc = st; sc; sc = sc->up_updates) {
    for (uu = sc->updates; uu; uu = uu->next)
      if (uu->update_of == sym)
	return uu;
  }
  return sym;
}

D_Sym *
find_sym_internal(D_Scope *top, D_Scope *cur, char *name, int len, uint h) {
  D_Sym *ll;

  if (!cur)
    return NULL;
  if (cur->hash) 
    ll = cur->hash->syms.v[h % cur->hash->syms.n];
  else
    ll = cur->ll;
  while (ll) {
    if (ll->hash == h && ll->len == len && !strncmp(ll->name, name, len))
      break;
    ll = ll->next;
  }
  if (!ll) { 
    if (cur->search)
      return find_sym_internal(top, cur->search, name, len, h);
    return ll;
  }
  return current_D_Sym(top, ll);
}

D_Sym *
find_D_Sym(D_Scope *st, char *name, char *end) {
  int len = end - name;
  uint h = strhashl(name, len);
  return find_sym_internal(st, st, name, len, h);
}

D_Sym *
find_D_Sym_in_Scope(D_Scope *st, char *name, char *end) {
  D_Sym *ll;
  int len = end - name;
  uint h = strhashl(name, len);
  for (;st ; st = st->search) {
    if (st->hash) 
      ll = st->hash->syms.v[h % st->hash->syms.n];
    else
      ll = st->ll;
    while (ll) {
      if (ll->hash == h && ll->len == len && !strncmp(ll->name, name, len))
	return ll;
      ll = ll->next;
    }
    if (!st->search || st->search->up != st->up)
      break;
  }
  return NULL;
}

D_Sym *
update_D_Sym(D_Scope *st, D_Sym *sym, int sizeof_D_Sym) {
  D_Sym *s;

  sym = current_D_Sym(st, sym);
  s = MALLOC(sizeof_D_Sym);
  memcpy(s, sym, sizeof(D_Sym));
  if (sym->update_of) sym = sym->update_of;
  s->update_of = sym;
  s->next = st->updates;
  st->updates = s;
  return s;
}

void
print_sym(D_Sym *s) {
  char *c = (char*)MALLOC(s->len + 1);
  memcpy(c, s->name, s->len);
  s->name[s->len] = 0;
  printf("%s, ", c);
  FREE(c);
}

void
print_scope(D_Scope *st) {
  printf("SCOPE %X: ", (long)st);
  printf("  owned: %d, kind: %d, ", st->owned_by_user, st->kind);
  if (st->ll) printf("  LL\n");
  if (st->hash) printf("  HASH\n");
  if (st->hash) {
    int i;
    for (i = 0; i < st->hash->syms.n; i++)
      if (st->hash->syms.v[i])
	print_sym(st->hash->syms.v[i]);
  } else {
    D_Sym *ll = st->ll;
    while (ll) {
      print_sym(ll);
      ll = ll->next;
    }
  }
  printf("\n\n");
  if (st->search) print_scope(st->search);
}