/*
 * Symbol table functions, comprising the operations for the Symtab data
 * abstraction.  See 450 Notes 11 and 12 for further details.
 *
 * Here is a summary of the operations:
 *

	RETURN TYPE	NAME		DESCIRIP

	void		InitSymtab	Builds a level 0 symtab and
					initializes built-in constants and
					types.  Call this function once at
					overall system init time, it sets
					CurSymtab to an inital top-level table.

	Symtab *	AllocSymtab	Builds a new symtab; call for each
					new named scope.

	void		NewLevel	Call AllocSymtab to create a new symtab
					level.  Set CurSymtab to the new level.

	void		LeaveLevel	Set CurSymtab its parent.

	SymtabEntry *	AllocSymtab	Allocs a new entry for a symbol and
			  Entry		returns a pointer to it; call with
					already hashed symbol.

	SymtabEntry *	HashAlloc	Same as AllocSymtabEntry, but hashes
			SymtabEntry	string argument; call with unhashed
					string.

	int		Enter		Enters a SymtabEntry into CurSymtab.

	int		EnterIn		Enters a SymtabEntry into a symtab
					specfied as an argument.

	SymtabEntry *	Lookup		Looks up a (already hashed) symbol in
					CurSymtab.

	SymtabEntry *	LookupIn	Looks up a (already hashed) symbol in
					a symtab specified as an argument.

	SymtabEntry *	LookupString	Look up an unhashed symbol.

	SymtabEntry *	NextEntry()	Generate entires in hased order.

	void		ResetNext()	Reset generator back to 1st entry.

	int		Delete()	Deletes a symbol.

	int		DeleteIn()	Deletes a symbol in a specific symtab.

	SymtabEntry *	SymCopy		Copy a SymtabEntry.

	char *		hash		Find a symbol in the string hash tab.
					(This is actually a macro that calls
					hash1; see decl at end of sym.h.)

	char *		hashsave	Put a symbol in the string hash tab.

	int		hash2		Hash a symbol for insertion in the
				 	Entries field of CurSymtab.  hash2 is
					a Mask-way hash on the low order bits
					of a char pointer.

	char **		hash1		Hackers version of hash
						-- enter at own risk!
 *
 */

#include "std-macros.h"
#include "parse-tree.h"
#include "parser.h"
#include "tokens.h"
#include "sym.h"
#include "parser-aux.h"
#include "token-mapping.h"
#include <string.h>
#include <stdlib.h>
#include <stdint.h>


/*
 * Initialize the top-level symtab and make it current.
 */
void InitSymtab()
{
    inithash();
    ResetNext();
    symtos = SymtabStack;
    SymtabStackSize = STACKSIZE;
    Level0Symtab = CurSymtab = AllocSymtab(LEVEL0SIZE);
    Level0Symtab->Level = 0;
    Level0Symtab->ParentEntry =
	HashAllocSymtabEntry("LEVEL0", C_Module, null, 0);
    Level0Symtab->Offset = 0;
    InstallBuiltInSyms();
    SetErrorCounter(&(CurSymtab->Errors));
    MaxNest = CurNest = 0;
}


Symtab *AllocSymtab (siz)
	int		 siz;
{
	Symtab		*st;
	register int	 i;
	register int	 mask;
	
	if ((st = (Symtab *) calloc(1, sizeof (Symtab))) == NIL) {
	    error("Ran out of memory (AllocSymtab/Symtab)");
	    exit(0);
	}
	st -> Size = siz;
	mask = 1;
	while (mask < (siz - 1))
		mask = (mask << 1) | 1;
	st->Mask = mask;
	if ((st->Entries = (SymtabEntry	**)
	    calloc (1, siz * sizeof(SymtabEntry*))) == NIL) {
		error("Ran out of memory (AllocSymtab/Entries)");
		exit(0);
	}
	st->DeclThread = null;
	st->DeclOrderList = NewCppList();
	return (st);
}
	

/*
 * The following is an idea we might want to try sometime, but it is presently
 * unimplemented:
 *
 * The LevelCounter var is used for error correction in the following manner.
 * Upon each descent via NewLevel, the counter is bumped by one, and upon each
 * matching ascent via LeaveLevel, the counter is decremented by one.  This
 * means that whenever the counter is > 0, we're in a descent that has had no
 * matching ascent.
 */
static int LevelCounter = 0;

void NewLevel (Entry, Size, Line, ScopeType)
	SymtabEntry	*Entry;
	int		 Size;
	nodep		 Line;	/* only needed for rare error message */
	TokenType	 ScopeType; /* YDEF, etc.  NULL if proc scope */
{
	Symtab		*st;

	st = AllocSymtab (Size);
	if (Entry != NILSYM) {
	    switch (Entry->Class) {
		case C_Proc:
		    Entry->Info.Proc.Symtab = st;
		    break;
		case C_Module:
		    Entry->Info.Module.Symtab = st;
		    break;
#ifdef RSL
		case C_Obj:
		    Entry->Info.Obj.Symtab = st;
		    break;
		case C_Op:
		    Entry->Info.Op.Symtab = st;
		    break;
#endif
#ifdef DEMO
		case C_SROp:
		    Entry->Info.SROp.Symtab = st;
		    break;
#endif
	    }
	}
	st->ParentTab = CurSymtab;
	st->ParentEntry = Entry;
	st->Level = CurSymtab == (Symtab *)0 ? 0 : CurSymtab->Level + 1;
	st->Type = ScopeType;
	CurSymtab = st;

	/*
	 * Do the nesting level computation.  This is only needed to make sure
	 * we dont overflow the max display size, which is almost unimagineable
	 * (i.e., someone would have to write a program with lexical nesting
	 * level > 50).  It would however be embarassing not to catch it!
	 */
	CurNest++;
	if (CurNest > MaxNest) {
	    MaxNest = CurNest;
	    if (MaxNest > DISPLAYSIZE)
		lerror(Line, "Maximum lexical nesting depth is %d\n",
				DISPLAYSIZE);
	}
}


LeaveLevel()
{
    if (CurSymtab->ParentTab) {
	CurSymtab = CurSymtab->ParentTab;
	CurNest--;
    }
}


SymtabEntry *AllocSymtabEntry (sym, class, type, level)
	char *sym;		/* Symbol name */
	SymClasses class;	/* Symbol's class */
	TypeStruct type;	/* Symbol's type */
	int level;		/* Symbol's lexical block level */
{
	register SymtabEntry *p;
	register int *q;
	register int i;

	/* 
	 *Alloc the new entry.
	 */
	if ((p = (SymtabEntry *) malloc(sizeof(SymtabEntry))) == NILSYM) {
		error("Ran out of memory (AllocSymtabEntry)");
		exit(0);
	}

	/*
	 * Zero out the entry.
	 */
	q = (int *) p;
	i = (sizeof *p)/(sizeof (int));
	do
		*q++ = 0;
	while (--i);

	/*
	 * Insert the values
	 */
	p->Symbol = sym;
	p->Class = class;
	p->Type = type;
	p->Level = level;

	return (p);
}


SymtabEntry *HashAllocSymtabEntry (name, class, type, level)
	register char *name;
	SymClasses class;
	TypeStruct type;
	int level;
{
	char *hname;

	if (name)
	    hname = hashsave (name);

	return AllocSymtabEntry (hname, class, type, level);
}


/*
 * Enter a symbol into the current symbol table.  Return false if symbol is
 * a new entry, true if duplicate entry.  Duplicate symbols *are* entered --
 * use Lookup before Enter to avoid duplicate entries if desired.
 *
 * Symbols are hashed CurSymtab->size ways based on low ceiling(log2(size))
 * bits of the character pointer into the string hash table.
 *
 */
bool Enter(e)
    SymtabEntry *e;
{
    int i;
    register SymtabEntry *hp, *rp;

    /*
     * Do the hashing.
     */
    i = hash2(e->Symbol, CurSymtab);
    /* Macro expansion is:
         i = (((intptr_t) e->Symbol & CurSymtab->Mask) % CurSymtab->Size);
     */

    /*
     * Grab current entry, if any.
     */
    hp = CurSymtab->Entries[i];

    /*
     * Splice in new entry at front of bucket.
     */
    e->Next = hp;
    CurSymtab->Entries[i] = e;

    /*
     * Add sym to end of decl-order thread.
     */ 
    e->DeclNext = null;
    if (CurSymtab->DeclThread == null) {
	CurSymtab->DeclThread = CurSymtab->DeclLast = e;
    }
    else {
	CurSymtab->DeclLast->DeclNext = e;
	CurSymtab->DeclLast = e;
    }

    /*
     * Compute proper return val by checking each entry in old bucket for
     * match of symbol of new entry.
     */
    for (rp = hp; rp; rp=rp->Next)
	if (e->Symbol == rp->Symbol) /* Note: == works instead of streq */
	    return true;	     /* because syms are hashed */
    return false;
}


/*
 * Enter a symbol in a specific symtab, i.e., a symtab other than CurSymtab.
 */
bool EnterIn(s, st)
    SymtabEntry *s;
    Symtab *st;
{
    bool ret;

    PushSymtab();
    CurSymtab = st;
    ret = Enter(s);
    PopSymtab();
    return ret;
}


/*
 * Lookup is called to find a symbol in the block structured symbol table and
 * returns a pointer to its SymtabEntry, or null if not found.  Lookup assumes
 * that the global var CurSymtab is properly set.  Given this Lookup searches
 * for a symbol in the following order:
 *
 *   (1) Look in the hashed Entries of CurSymtab
 *   (2) If CurSymtab is a closed scope, look in Level 0 Symtab
 *   (3) If CurSymtab is an open scope, iteratively follow the Parent link of
 *	 CurSymtab until Parent is null, applying steps (1) and (2) at each
 *       level.
 *
 * IMPORTANT NOTE: Call Lookup with already hashed symbols.  Use LookupString
 * (defined below) to call with an unhashed string name.
 *
 */
SymtabEntry *Lookup(s)
	register char *s;
{
    register SymtabEntry *e;
    register int i;
    register Symtab *st;

#define isClosed(st) (st->ParentEntry and (st->ParentEntry->Class == C_Module))

    /*
     * Outta here if symbol is null.
     */
    if (not s)
	return null;

    /*
     * Protect against ill-formed symtab, which can happen when there's a
     * syntax error, but this function is called from the lexer for
     * indentifying attribute names.
     */
    if ((not CurSymtab) or CurSymtab->ParentTab == CurSymtab)
	return null;

    /*
     * The following was an ill-considered attempt to deal with the circularity
     * in the symtab parent chain.  It's left for posterity, and possible later
     * removal.
     *
     * Also outta here if there's a parse error current.  The reason for this
     * was discovered during transition to the new parser, when a parse error
     * led to a circularity being created in the symtab parent chain.  Whether
     * or not this problem should be fixed independently is not thep point
     * here.  Rather, if there's any kind of parse error working, then Lookup
     * can be expected to fail.
     *
     if (PARSE_ERROR)
	return null;
     */

    /*
     * Starting in this scope, look in Entries and move out to Parent scopes as
     * appropriate.
     */
    for (st = CurSymtab; st; st = st->ParentTab) {

        /*
	 * Further protection against syntax-error-induced malformed symtab
	 * hierarchy.
	 */
	if (st->ParentTab == st)
	    return null;

	/*
	 * A symtab with a null mask is just a temp being used to count record
	 * fields.  Ignore it.
         */
	if (not st->Mask)
	    continue;

	/*
	 * Hash s and look up in Entries.
	 */
	i = hash2(s, st);
	for (e = st->Entries[i]; e != null; e = e->Next)
	    if (e->Symbol == s) {
		/*
		 * Return found symbol, indirectly so if it's an import.
		 */
		while (ChkSymFlag(e, isImport))
		    e = e->Chain;
		return e;
	    }

	/*
	 * If current scope is closed (i.e., a module), look immediately in
	 * Level 0.  Otherwise, just continue looking out into parent scopes.
	 */
	if (isClosed(st)) {
	    st = Level0Symtab;
	    i = hash2(s, st);
	    for (e = st->Entries[i]; e != null; e = e->Next)
		if (e->Symbol == s) {
		    /*
		     * Return found symbol, indirectly so if it's an import.
		     */
		    while (ChkSymFlag(e, isImport))
			e = e->Chain;
		    return e;
		}
	    return null;
	}
    }

    /*
     * Didnt find s anywhere.
     */
    return null;
}


/*
 * Lookup a symbol in a specific symtab, i.e., a symtab other than CurSymtab.
 */
SymtabEntry *LookupIn(s, st)
    char *s;
    Symtab *st;
{
    SymtabEntry *ret;

    PushSymtab();
    CurSymtab = st;
    ret = Lookup(s);
    PopSymtab();
    return ret;
}


/* 
 * Version of lookup that looks up a regular (unhashed) string.
 */
SymtabEntry *LookupString(s)
    char *s;
{
    return Lookup(hash(s));
}


/*
 * Lookup a string in a specific symtab, i.e., a symtab other than CurSymtab.
 */
SymtabEntry *LookupStringIn(s, st)
    char *s;
    Symtab *st;
{
    return LookupIn(hash(s), st);
}


/*
 * The next module locals are in entry generator.
 */
static int nexti = 0;		  /* Generator Entries index. */
static SymtabEntry *nexte = null; /* Generator bucket pointer */

/*
 * Generate the next symtab entry, in hash order.  When end of table is
 * reached, return null.
 *
 * pre: ((nexti >= 0) and (nexti <= CurSymtab->Size)) and
 *	(if (nexte) then typeof(nexte) == SymtabEntry)
 *
 */
SymtabEntry *NextEntry()
{
    SymtabEntry *e;

    /*
     * If we're already in a bucket, return the next bucket entry and advance.
     */
    if (nexte) {
	e = nexte;
	nexte = nexte->Next;
	return e;
    }

    /*
     * Skip over empty entries.
     */
    for (; (not (e=CurSymtab->Entries[nexti]))
		and (nexti < CurSymtab->Size); nexti++)
	;

    /*
     * If we're at the end of the entries, reset back to the beginning, and
     * return null.
     */
    if (nexti >= CurSymtab->Size) {
	nexti = 0;
	return null;
    }

    /*
     * OK, we're at a non-empty entry.  Return the first in the bucket, and
     * advance the bucket pointer.
     */
    e = CurSymtab->Entries[nexti];
    nexti++;
    nexte = e->Next;
    return e;
}

/*
 * Reset the next entry generator to the beginning of the table.
 */
void ResetNext()
{
    nexti = 0;
    nexte = null;
}


/*
 * Delete a symbol from the current symbol table, this scope only.  If a symbol
 * of the given name is not found, Delete does nothing.  If duplicate symbols
 * of the given name have been entered, Delete removes only the first such
 * symbol in hash order.  Delete returns no status information.  Use Lookup
 * before or after each Delete to determine if a symbol exists.
 */
void Delete(s)
    char *s;
{
    register SymtabEntry *e;
    register SymtabEntry **preve;
    int i;

    /*
     * Do like Lookup.  We cant just call Lookup, since it doesnt give us a
     * complete handle on the bucket.
     */
    i = hash2(s, CurSymtab);
    
    /*
     * Surgically remove found symbol from its bucket.
     */
    for (e = CurSymtab->Entries[i], preve = &(CurSymtab->Entries[i]);
	    e; preve = &(e->Next), e = e->Next) {
	if (e->Symbol == s) {
	    *preve = e->Next;
	    return;
	}
    }
}

/*
 * Delete a symbol in a specific symtab, i.e., a symtab other than CurSymtab.
 */
void DeleteIn(s, st)
    char *s;
    Symtab* st;
{
    PushSymtab();
    CurSymtab = st;
    Delete(s);
    PopSymtab();
}


/*
 * The definition for the segmented hash tables.
 */
static struct ht {
	intptr_t	*ht_low;
	intptr_t	*ht_high;
	intptr_t	ht_used;
} htab[MAXHASH];

/*
 * For 450, an empty keyword table that you can try to figure out if you like.
 */
struct kwtab {
	char	*kw_str;
	int	kw_val1;
	int	kw_val2;
	int	kw_val3;
} yykey[1];
char	*lastkey = (char *) yykey;
char	*token;

/*
 * Inithash initializes the hash table routines
 * by allocating the first hash table segment using
 * an already existing memory slot.
 */

static void inithash()

{
	register intptr_t *ip;
	static intptr_t hshtab[HASHINC];

	htab[0].ht_low = hshtab;
	htab[0].ht_high = &hshtab[HASHINC];
	for (ip = (intptr_t *) yykey; *ip; ip += 2)
		hash1(ip[0], 0)[0] = (char *) ip;
}

/*
 * Hash1 looks up the s(ymbol) argument in the string table, entering it if it
 * is not found.  If save is false, then the argument string is already in a
 * safe place.  Otherwise, if hash1 is entering the symbol for the first time,
 * it will save the symbol in the string table using savestr.
 *
 * NOTE WELL: hash1 is a particularly ugly (but efficient) piece of work
 * inside.  It's best treated as a black box.
 */
char **hash1(s, save)
	char *s;
	bool save;
{
	register intptr_t *h;
	register i;
	register char *cp;
	intptr_t *sym;
	struct ht *htp;
	int sh;
	char *savestr();
	char *symc;

	/*
	 * The hash function is a modular hash of
	 * the sum of the characters with the sum
	 * doubled before each successive character
	 * is added.
	 */
	cp = s;
	if (cp == NIL)
		cp = token;	/* default symbol to be hashed */
	i = 0;
	while (*cp)
		i = i*2 + *cp++;
	sh = (i&077777) % HASHINC;
	cp = s;
	if (cp == NIL)
		cp = token;
	/*
	 * There are as many as MAXHASH active
	 * hash tables at any given point in time.
	 * The search starts with the first table
	 * and continues through the active tables
	 * as necessary.
	 */
	for (htp = htab; htp < &htab[MAXHASH]; htp++) {
		if (htp->ht_low == NIL) {
			cp = (char *) calloc(sizeof ( int * ), HASHINC);
			if (cp == 0) {
				error("Ran out of memory (hash)");
				exit(0);
			}
			htp->ht_low = (intptr_t *) cp;
			htp->ht_high = htp->ht_low + HASHINC;
			cp = s;
			if (cp == NIL)
				cp = token;
		}
		h = htp->ht_low + sh;
		/*
		 * quadratic rehash increment
		 * starts at 1 and incremented
		 * by two each rehash.
		 */
		i = 1;
		do {
			if (*h == 0) {
				if (htp->ht_used > (HASHINC * 3)/4)
					break;
				htp->ht_used++;
				if (save != 0) {
					*h = (intptr_t) savestr(cp);
				} else
					*h = (intptr_t) s;
				return (char **) h;
			}
			sym = (intptr_t *) *h;
			if (sym < (intptr_t *) lastkey && sym >= (intptr_t *) yykey)
				sym = (intptr_t *) *sym;
			symc = (char*) sym;
			if (*symc == *cp && strcmp((char *) sym, cp) == 0)
				return (char **) h;
			h += i;
			i += 2;
			if (h >= htp->ht_high)
				h -= HASHINC;
		} while (i < HASHINC);
	}
	error("Ran out of hash tables");
	exit(0);
}

/* Separate string-space management functions for use with functions
 * functions above.
 *
 * Strng is the base of the current string space and strngp the
 * base of the free area therein.   Strp is the array of string
 * descriptors (not to be confused with Icon descriptors).
 */

static	char strings[STRINC];
static	char *strng = strings;
static	char *strngp = strings;

/*
 * Copy a string into the string area.
 */
char *savestr(cp)
	register char *cp;
{
	register int i;

	if (cp == NIL)
		return (NIL);
	i = strlen(cp) + 1;
	if (strngp + i >= strng + STRINC) {
		strngp = (char *) malloc(STRINC);
		if (strngp == 0) {
			error("Ran out of memory (string)");
			exit(0);
		}
		strng = strngp;
	}
	strcpy(strngp, cp);
	cp = strngp;
	strngp = cp + i;
	return (cp);
}

char *esavestr(cp)
	char *cp;
{
	strngp = ( (char *) ( ( (intptr_t) (strngp + 1) ) &~ 1 ) );
	return (savestr(cp));
}

/*
 * Generate parm names and types from a proc symtab entry.  Assume that given
 * entry is in fact that of a proc.  Two steps:
 *
 *   (1) Start generator with StartParmNameAndTypeGen(SymtabEnty *sym)
 *
 *   (2) Get each successive parm name and type with
 * 		char* NextParmNameAndType()
 *
 */
static SymtabEntry* nextp = null;	/* Generator parm pointer */
static int nextptoggle = 0;		/* Toggles between name and type */

void StartParmNameAndTypeGen(SymtabEntry *sym) {
     nextptoggle = 0;
     nextp =  sym->Info.Proc.Parms;
}

char* NextParmNameAndType() {
    char* rtn;

    if (not nextp)
	return null;

    if (nextptoggle == 0) {
	nextptoggle++;
	return nextp->Symbol;
    }
    else {
	nextptoggle = 0;
	rtn = nextp->Info.Parm.TypeName;
	nextp = nextp->Info.Parm.Link;
	return rtn;
   }
}

nodep GetWhereClause(SymtabEntry *sym) {
    return FindAttr(sym->Info.Obj.attrs, YWHERE);
}

int GetSymtabLevel(Symtab* st) {
    return st->Level;
}

Symtab* CopySymtab(Symtab* st) {
    Symtab* rtn = AllocSymtab(st->Size);

    memcpy(rtn, st, sizeof(Symtab));
    memcpy(rtn->Entries, st->Entries, st->Size * sizeof(SymtabEntry*));

    return rtn;
}