symbolsTable.c

/*
 * symbolsTable.c : Implementation to manage the symbols table
 * Part of the compiler project for LSD10 language
 * Gaudry Stéphane
 * More information on http://www.gaudry.be/langages-table-des-symboles.html
 * **********************************************************
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#if(VERBOSE_LEVEL<=DEB_E)
	#include <errno.h>
#endif
#include "symbolsTableDataRepresentation.h"
#include "scopeStack.h"
#include "scopeHelper.h"
#include "common.h"
#include "hashCode.h"
 
/*
 * **********************************************************
 * Internal business implementations
 * **********************************************************
 */
 
int symbolsTableAvailable=0;
/**
 * Memory location of the last declaration
 */
int memoryUpperBound=INITIAL_INT;
 
/**
 * Creates a new SymTableEntry instance.
 */
SymTableEntry* createSymTableEntry(AstNode *declarationNode)
{
	SymTableEntry *entry=(SymTableEntry*)malloc(sizeof(SymTableEntry));
	if(!(entry))
	{
		if(VERBOSE_LEVEL<=DEB_E)
		{
			printMsg(DEB_E,"Allocation Error(SymTableEntry)", __FILE__, __LINE__);
			printMsg(DEB_E, (char *)strerror(errno), __FILE__, __LINE__);
		}
		//Failure of the compiler behavior, independent of the parsed code
		exit(EXIT_FAILURE);
	}
	entry->next = NULL;
 
	ScopeStack *scopeStack = createScopeStack();
	scopeStack->declarationNode = declarationNode;
	scopeStack->parentPtr = NULL;
	declarationNode->info->memoryLocation=memoryUpperBound;
	scopeStack->functionNode = (AstNode *)scopeHelperGetCurrentFunction();
	if(declarationNode==getMain())
	{
		scopeStack->usage=VAR_USAGE_ALWAYS;
	}
	entry->scopeStack = scopeStack;
	#if(VERBOSE_LEVEL<=DEB_SYM)
		printf(
			"\n;\tCreation of an entry for %s on scope %d (compiler %s, %d)....main=%s\n",
			declarationNode->info->name,
			getScopeDepth(scopeStack),
			__FILE__,
			__LINE__,
			getMain()==NULL?"null":"ok"
		);
	#endif
	return entry;
}
void finalizeSymTableEntry(SymTableEntry *entry)
{
	if(entry!=NULL)
	{
		finalizeSymTableEntry(entry->next);
		free(entry);
	}
}
/**
 * Search only on a given scope stack for a declaration
 * Pre-condition: the scope stack matches the identifier
 * @param astNode, pointer to the node for witch we search the declaration
 * @param scopeId
 * @param scopeStack, pointer to the stack where to search
 */
ScopeStack* searchDeclarationOnStack(AstNode *astNode, int scopeId, ScopeStack *scopeStack)
{
	if(scopeStack==NULL)
	{
		return NULL;
	}
	int foundScopeId=getScopeDepth(scopeStack);
	#if(VERBOSE_LEVEL<=DEB_SYM)
		printf(
			"\n;------Search for %s [%p, scope %d] on scope %d (compiler %s,%d)\n",
			astNode->info->name,
			astNode,
			foundScopeId,
			scopeId,
			__FILE__,
			__LINE__
			);
	#endif
	// there is a scopeStackPtr for this identifier
	if(foundScopeId!=ERROR_INT && foundScopeId<=scopeId)
	{
		return scopeStack;
	}
	#if(VERBOSE_LEVEL<=DEB_SYM)
		printf(
			"\n;  Nothing found for %s (%p) on scope %d (compiler %s,%d)\n",
			astNode->info->name,
			astNode,
			scopeId,
			__FILE__,
			__LINE__
			);
	#endif
	// search into the wrapper scope
	ScopeStack *parentScope = scopeStack->parentPtr;
	if(parentScope!=NULL)
	{
		#if(VERBOSE_LEVEL<=DEB_SYM)
			printf(
				"\n;------Try to search on parent scope [%p] for %s [%p] (compiler %s,%d)\n",
				parentScope,
				astNode->info->name,
				astNode,
				__FILE__,
				__LINE__
				);
		#endif
		return searchDeclarationOnStack(astNode, scopeId, parentScope);
	}
	else
	{
		#if(VERBOSE_LEVEL<=DEB_SYM)
			printf(
				"\n;------Scope %d, No parent scope where to search for %s (compiler %s,%d)\n",
				foundScopeId,
				astNode->info->name,
				__FILE__,
				__LINE__
				);
		#endif
	}
	return NULL;
}
/**
 * Search on all of the linked list of given scope stack for a declaration
 * @param currentNode, pointer to the node for witch we search the declaration
 * @param scopeId, scope where to search
 * @param scopeStack, pointer to the stack where to start search
 */
ScopeStack* searchDeclaration(AstNode *currentNode, int scopeId, SymTableEntry *entry)
{
	if(entry==NULL || entry->scopeStack==NULL)
	{
		return NULL;
	}
//	if(currentNode==NULL)
//	{
//		return NULL;
//	}
//	if(currentNode->info==NULL)
//	{
//		return NULL;
//	}
	// test name to detect hashcode collisions
	if(strcmp(getEntryName(entry), currentNode->info->name)!=0)
	{
//		printf(
//			"\n; collision: %s searched, %s found, %s next\n",
//			currentNode->info->name,
//			entry->scopeStack->declarationNode->info->name,
//			entry->next==NULL?"null":entry->next->scopeStack->declarationNode->info->name
//			);
		// if there is collision of hashcodes, search into the next identifier stack
		return searchDeclaration(currentNode, scopeId, entry->next)	;
	}
//	printf(
//		"\nOK : %s searched, %s found\n",
//		currentNode->info->name,
//		entry->scopeStack->declarationNode->info->name
//		);
	// the scope stack matches the identifier
	return searchDeclarationOnStack(currentNode, scopeId, entry->scopeStack);
}
/**
 * Search into the symbols table for a declaration of a given AST node for the current scope.
 * If no backward declaration exists, the program exits with an error message
 * pre-condition: astNode not NULL
 */
ScopeStack* getScopeDeclaration(AstNode* astNode)
{
	int hash = getASTHashCode(astNode);
 
	ScopeStack* foundStack = NULL;
	#if(VERBOSE_LEVEL<=DEB_SYM)
		printf(
			"\n;------Search for %s; current scope=%d, Table[%d] %s (compiler %s,%d)",
			astNode->info->name,
			astNode->info->scopeId,
			hash,
			declarations[hash]==NULL?"empty":"not empty",
			__FILE__,
			__LINE__
			);
	#endif
	if(declarations[hash]!=NULL)
	{
		foundStack = searchDeclaration(astNode, scopeHelperGetCurrentScope(), declarations[hash]);
//		printf(
//			"\n;\tnode=%s; founstack=%s\n",
//			astNode->info->name,
//			foundStack==NULL?"null":foundStack->declarationNode->info->name
//			);
		if(foundStack!=NULL && isBefore(astNode, foundStack->declarationNode)==AST_CMP_BEFORE)
		{
			#if(VERBOSE_LEVEL<=DEB_E)
			printf(
				";\n;\tForward declaration detected for %s line %d col %d, declaration line %d col%d",
				astNode->info->name,
				astNode->debug->line,
				astNode->debug->linePsn,
				foundStack->declarationNode->debug->line,
				foundStack->declarationNode->debug->linePsn
				);
			#endif
			foundStack=NULL;
		}
	}
	//else printf("\nentry null (%s,%d)",__FILE__, __LINE__);
	if(foundStack==NULL)
	{
		char errorStr[1024];//todo: minimize length
		sprintf(
			errorStr,
			"No previous declaration found for %s line %d col %d (compiler %s,%d)",
			astNode->info->name,
			astNode->debug->line,
			astNode->debug->linePsn,
			__FILE__,
			__LINE__
			);
		onError(errorStr, __FILE__, __LINE__, astNode);
	}
	#if(VERBOSE_LEVEL<=DEB_SYM)
		printf("\n;------Found %s (%p)",astNode->info->name, astNode);
	#endif
	return foundStack;
}
/**
 * Adds a declaration into the symbols table
 * @param entry pointer to an existing item of linked list (to solve hash collisions)
 * @param declarationNode declaration to add into the symbols table
 * @param hash index of the item on the symbols table
 * pre-condition: entry not null
 */
void addSafeDeclaration(SymTableEntry *entry, AstNode* declarationNode, int hash)
{
	if(strcmp( getEntryName(entry), declarationNode->info->name )!=0)
	{
		// hash collision detected;
		#if(VERBOSE_LEVEL<=DEB_SYM)
			printf(
				"\n;------Collision detected for %s hash=%d [%s found on %p] (compiler %s,%d)",
				declarationNode->info->name,
				hash,
				getEntryName(entry),
				entry,
				__FILE__,
				__LINE__
				);
		#endif
		SymTableEntry *nextEntry = entry->next;
		if(nextEntry==NULL)
		{
			SymTableEntry *tempEntry = createSymTableEntry(declarationNode);
			tempEntry->next=entry;
			// we add the new entry as first item of the linked list(proximity possible usage)
			declarations[hash]=tempEntry;
		}
		else
		{
			addSafeDeclaration(nextEntry, declarationNode, hash);
		}
	}
	else
	{
		#if(VERBOSE_LEVEL<=DEB_SYM)
			printf(
				"\n;------A scope exists for %s [%s] (compiler %s,%d)",
				declarationNode->info->name,
				getEntryName(entry),
				__FILE__,
				__LINE__
				);
		#endif
		int curScope = scopeHelperGetCurrentScope();
		int foundScope = getScopeDepth(entry->scopeStack);
		if(foundScope==curScope)
		{
			AstNode* foundNode = entry->scopeStack->declarationNode;
			char errorStr[1024];//todo: minimize length
			sprintf(
				errorStr,
				"A previous declaration for %s (scope %d line %d col %d) has been detected (scope %d line %d col %d) by compiler %s,%d",
				declarationNode->info->name,
				curScope,
				declarationNode->debug->line,
				declarationNode->debug->linePsn,
				foundScope,
				foundNode->debug->line,
				foundNode->debug->linePsn,
				__FILE__,
				__LINE__
				);
			onError(errorStr, __FILE__, __LINE__, declarationNode);
		}
		pushScopesStack(&(entry->scopeStack), scopeHelperGetCurrentScope(), declarationNode);
		entry->scopeStack->declarationNode->info->memoryLocation=memoryUpperBound;
	}
}
/**
 * Parses nodes from variable usage node to root to detect if we are on a conditional bloc
 */
void checkUsage(ScopeStack* scopeStack, AstNode *node)
{
	if(scopeStack==NULL)
	{
		scopeStack = getScopeDeclaration(node);
	}
	if(scopeStack!=NULL && scopeStack->usage!=VAR_USAGE_ALWAYS)
	{
		while(node->parent!=NULL)
		{
//			printf(
//				"\n; Check usage for %s line %d col %d, parent=%s (compiler(%s, %d)",
//				node->info->name,
//				node->debug->line,
//				node->debug->linePsn,
//				node->parent==NULL?"NULL":node->parent->info->name,
//				__FILE__,
//				__LINE__
//				);
			switch(node->parent->subtype)
			{
				case LEXICAL_IF_STMT:
				case AST_IF_ELSE_STMT:
					scopeStack->usage = VAR_USAGE_SOMETIMES;
					return;
			}
			node=node->parent;
		}
		scopeStack->usage=VAR_USAGE_ALWAYS;
	}
}
/*
 * **********************************************************
 * Implementation of the header exposed items
 * See symbolsTable.h for these functions comments
 * **********************************************************
 */
 
int setUsage(AstNode *currentVarNode, VariableUsage usage)
{
	switch(currentVarNode->type)
	{
		case NODE_TYPE_ID:
		case NODE_TYPE_FUNCTION_CALL:
			break;
		default:return EXIT_FAILURE;
	}
	ScopeStack* foundStack = getScopeDeclaration(currentVarNode);
	if(foundStack==NULL)
	{
		return EXIT_FAILURE;
	}
	foundStack->usage = usage;
}
 
char *getEntryName(SymTableEntry *entry)
{
	if(entry==NULL)return "NULL entry";
//	if(entry->scopeStack==NULL)return "NULL entry stack";
//	if(entry->scopeStack->declarationNode==NULL)return "NULL entry declaration node";
//	if(entry->scopeStack->declarationNode->info==NULL)return "NULL entry declaration node info";
	return entry->scopeStack->declarationNode->info->name;
}
 
int isSymbolsTableAvailable()
{
	return symbolsTableAvailable;
}
 
void initializeSymbolsTable()
{
	setHashUpperBoundary(TABLES_SIZE);
	initializeScopeHelper();
	//declare i before ‘for’ statement because ‘for’ loop initial declarations are only allowed in C99 mode
	int i;
	for(i=0;i<TABLES_SIZE;i++)
	{
		declarations[i]=NULL;//createSymTableEntry(NULL);
	}
	symbolsTableAvailable=1;
}
void finalizeSymbolsTable()
{
	//printScopeUsage();
	int i;
	for(i=0;i<TABLES_SIZE;i++)
	{
		finalizeSymTableEntry(declarations[i]);
	}
	symbolsTableAvailable=0;
	finalizeScopeHelper();
}
void enterScope()
{
	scopeHelperEnterScope();
}
void exitScope()
{
	scopeHelperExitScope();
}
int enterFunctionScope(AstNode* functionNode)
{
	scopeHelperEnterScope();
	scopeHelperSetCurrentFunction(functionNode);
}
void addDeclaration(AstNode* declarationNode)
{
	switch(declarationNode->type)
	{
		case NODE_TYPE_VAR_DECL:
			++memoryUpperBound;
		case NODE_TYPE_PARAM_DECL:
		case NODE_TYPE_FUNCTION:
		{
			int hash = getASTHashCode(declarationNode);
			if(declarations[hash]==NULL)
			{
				#if(VERBOSE_LEVEL<=DEB_SYM)
					printf(";\n; Adding %s declaration into symbols table[new entry], scope=%d (compiler %s, line %d)",
						declarationNode->info->name,
						scopeHelperGetCurrentScope(),
						__FILE__,
						__LINE__
						);
				#endif
				declarations[hash]=createSymTableEntry(declarationNode);
			}
			else
			{
			#if(VERBOSE_LEVEL<=DEB_SYM)
				printf(";\n; Adding %s declaration into symbols table[existing entry], scope=%d (compiler %s, line %d)",
					declarationNode->info->name,
					scopeHelperGetCurrentScope(),
					__FILE__,
					__LINE__
					);
			#endif
				addSafeDeclaration(declarations[hash], declarationNode, hash);
			}
			#if(VERBOSE_LEVEL<=DEB_SYM)
				printSymbolsTableDebug(__FILE__, __LINE__);
			#endif
		}
		break;
	}
	// A declaration node is his own declaration
	declarationNode->info->declarationNode=declarationNode;
}
 
AstNode* getDeclaration(AstNode *node)
{
	if(node==NULL)
	{
		#if(VERBOSE_LEVEL<=DEB_E)
		{
			printMsg(DEB_E,"Illegal argument (NULL)", __FILE__, __LINE__);
		}
		#endif
		//Failure of the compiler behavior, independent of the parsed code
		exit(EXIT_FAILURE);
	}
	#if(VERBOSE_LEVEL<=DEB_SYM)
		printf(";\n; Get %s declaration from symbols table[bypass=%s] (compiler %s, line %d)",
			node->info->name,
			node->info->declarationNode==NULL?"no":"yes",
			__FILE__,
			__LINE__
			);
	#endif
	if(node->info->declarationNode!=NULL)
	{
		return node->info->declarationNode;
	}
	//node->info->scopeDepth=scopeHelperGetCurrentDepth();
	ScopeStack* foundStack = NULL;
	switch(node->type)
	{
		case NODE_TYPE_VAR_DECL:
			return node;
		case NODE_TYPE_FUNCTION:
		case NODE_TYPE_PARAM:
			#if(VAR_USAGE_REPORT_REQUESTED)
				checkUsage(foundStack, node);
			#endif
			return node;
		case NODE_TYPE_ID:
		case NODE_TYPE_FUNCTION_CALL:
//			if(node->info->declarationNode==NULL)
//			{
				#if(VERBOSE_LEVEL<=DEB_SYM)
					printf(
						";\n; Declaration not yet found for %s line %d col %d, must search into table (compiler %s, line %d)",
						node->info->name,
						node->debug->line,
						node->debug->linePsn,
						__FILE__,
						__LINE__
						);
				#endif
				foundStack = getScopeDeclaration(node);
				node->info->declarationNode = foundStack==NULL?NULL:foundStack->declarationNode;
//			}
			#if(VAR_USAGE_REPORT_REQUESTED)
				checkUsage(foundStack, node);
			#endif
			return node->info->declarationNode;
	}
	#if(VERBOSE_LEVEL<=DEB_E)
	{
		printf(
			";\n; Error : Illegal argument (%s is not an id or a function call) On %s, Line%d",
			node->info->name,
			__FILE__,
			__LINE__
			);
	}
	#endif
	//Failure of the compiler behavior, independent of the parsed code
	exit(EXIT_FAILURE);
}
int getDeclarationsMemoryUpperBound()
{
	return memoryUpperBound;
}
int getDeclarationMemoryLocation(AstNode *node)
{
	AstNode *declarationNode = getDeclaration(node);
	return declarationNode==NULL?INITIAL_INT:declarationNode->info->memoryLocation;
}