path: root/interpreter/lookup_symbols.c

/* $Id: lookup_symbols.c 4974 2010-10-18 17:10:52Z potyra $
 * Interpreter library: resolve labels/references.
 *
 * Copyright (C) 2008-2009 FAUmachine Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */

#include "lookup_symbols.h"
#include "kernel.h" /* for driver/signal struct */
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
#include "glue-log.h"

#define ARRAY_SIZE(t)	(sizeof t / sizeof(t[0]))

struct symbol_table_label {
	const char *name;
	struct slist_entry *target;
};

struct symbol_table_type {
	const char *name;
	struct type_declaration *type;
};

struct symbol_table_container_ref {
	const char *name;
	unsigned int nesting;
	struct code_container *container;
	struct symbol_table_container_ref *next;
	struct symbol_table_container_ref *prev;
};

struct symbol_table_data_ref {
	const char *name;
	unsigned int nesting;
	const struct data_definition *definition;
	struct symbol_table_data_ref *next;
	struct symbol_table_data_ref *prev;
};

struct symbol_table {
	unsigned int nlabels;
	unsigned int ntypes;
	/* labels are only valid in one container's text segment,
	 * so these will just be stuffed into one array */
	struct symbol_table_label labels[10000];
	struct symbol_table_type type[1000];
	/* container head and tail pointer */
	struct symbol_table_container_ref *container_head;
	struct symbol_table_container_ref *container_tail;
	/* data head and tail pointer */
	struct symbol_table_data_ref *data_head;
	struct symbol_table_data_ref *data_tail;
	/* hacky store the callbacks there for logging */
	const struct glue_vhdl_cb *callbacks;
};

static void
symbol_resolve_type_elements(
	const struct symbol_table *symtab,
	struct type_declaration *type_decl
);


static void
symbol_label_add(
	struct symbol_table *symtab,
	const char *name,
	struct slist_entry *entry
)
{
	assert(symtab->nlabels < ARRAY_SIZE(symtab->labels));
	symtab->labels[symtab->nlabels].name = name;
	symtab->labels[symtab->nlabels].target = entry;
	symtab->nlabels++;
}

static void
symtab_clear_labels(struct symbol_table *symtab)
{
	symtab->nlabels = 0;
}

/** remove every container reference entry that has a nesting level
 *  >= nesting_level.
 *  @param symtab symbol table instance.
 *  @param nesting_level remove entries >= nesting_level.
 */
static void
symtab_remove_container_refs(
	struct symbol_table *symtab, 
	unsigned int nesting_level
)
{
	struct symbol_table_container_ref *i = symtab->container_tail;
	struct symbol_table_container_ref *j;

	while (i != NULL) {
		if (i->nesting < nesting_level) {
			break;
		}

		j = i;
		i = i->prev;
		symtab->callbacks->free(j);
	}

	if (i == NULL) {
		symtab->container_head = NULL;
		symtab->container_tail = NULL;
	} else {
		i->next = NULL;
		symtab->container_tail = i;
	}
}

static void
symtab_register_container_ref(
	struct symbol_table *symtab,
	struct code_container *container,
	unsigned int nesting_level
)
{
	struct symbol_table_container_ref *ref;

	ref = symtab->callbacks->malloc(
				sizeof(struct symbol_table_container_ref));
	assert(ref != NULL);

	ref->name = container->name;
	ref->nesting = nesting_level;
	ref->container = container;
	ref->next = NULL;
	ref->prev = symtab->container_tail;

	if (symtab->container_tail == NULL) {
		symtab->container_head = ref;
		symtab->container_tail = ref;
	} else {
		assert(symtab->container_tail->nesting <= nesting_level);
		symtab->container_tail->next = ref;
		symtab->container_tail = ref;
	}
}

static void
symtab_register_data_ref(
	struct symbol_table *symtab,
	const struct data_definition *data,
	unsigned int nesting_level
)
{
	struct symbol_table_data_ref *ref;

	ref = symtab->callbacks->malloc(sizeof(struct symbol_table_data_ref));
	assert(ref != NULL);
	assert(data->nesting_level == nesting_level);

	ref->name = data->name;
	ref->nesting = nesting_level;
	ref->next = NULL;
	ref->prev = symtab->data_tail;
	ref->definition = data;

	if (symtab->data_tail == NULL) {
		symtab->data_tail = ref;
		symtab->data_head = ref;
	} else {
		assert(symtab->data_tail->nesting <= nesting_level);
		symtab->data_tail->next = ref;
		symtab->data_tail = ref;
	}
}

static void
symtab_remove_data_refs(
	struct symbol_table *symtab, 
	unsigned int nesting_level
)
{
	struct symbol_table_data_ref *i = symtab->data_tail;
	struct symbol_table_data_ref *j;

	while (i != NULL) {
		if (i->nesting < nesting_level) {
			break;
		}

		j = i;
		i = i->prev;
		symtab->callbacks->free(j);
	}

	if (i == NULL) {
		symtab->data_tail = NULL;
		symtab->data_head = NULL;
	} else {
		symtab->data_tail = i;
		i->next = NULL;
	}
}

static void
symbol_type_add(
	struct symbol_table *symtab,
	struct type_declaration *type
)
{
	assert(symtab->ntypes < ARRAY_SIZE(symtab->type));
	symtab->type[symtab->ntypes].name = type->name;
	symtab->type[symtab->ntypes].type = type;
	symtab->ntypes++;
}

static struct type_declaration *
symbol_lookup_type(
	const struct symbol_table *symtab,
	const char *name
)
{
	unsigned int i;
	for (i = 0; i < symtab->ntypes; i++) {
		if (strcmp(name, symtab->type[i].name) == 0) {
			return symtab->type[i].type;
		}
	}

	return NULL;
}

/** resolve one type element
 *  @param symtab symbol table instance.
 *  @param elem element to resolve
 *  @param offset number of basic element before this type element.
 *  @return number of basic elements of this type element.
 */
static int
symbol_resolve_type_element(
	const struct symbol_table *symtab,
	struct type_element *elem,
	int offset
)
{
	struct type_declaration *type_decl;

	assert(elem != NULL);
	elem->offset = offset;
	type_decl = symbol_lookup_type(symtab, elem->name);
	
	if (type_decl == NULL) {
		symtab->callbacks->log(
			FAUHDLI_LOG_ERROR, "fauhdli", "symboltable",
			"Cannot lookup type %s\n", elem->name);
		return 0;
	}

	/* type already seen? */
	if (type_decl->elem_count == -1) {
		symbol_resolve_type_elements(symtab, type_decl);
		assert(type_decl->elem_count != -1); 
	}

	elem->elem_count = elem->elements * type_decl->elem_count;
	elem->type = type_decl;
	return elem->elem_count;
}

static void
symbol_resolve_type_elements(
	const struct symbol_table *symtab,
	struct type_declaration *type_decl
)
{
	struct slist_entry *i;
	int offset = 0;
	
	if (type_decl->elements == NULL) {
		/* must be a builtin type. */
		assert(type_decl->elem_count != -1);
		return;
	}

	for (i = type_decl->elements->first; i != NULL; i = i->next) {
		struct type_element *elem = (struct type_element *)i->data;

		offset += symbol_resolve_type_element(symtab, elem, offset);
	}
	type_decl->elem_count = offset;
}

static size_t
symtab_get_data_size(const struct data_definition *data)
{
	size_t basic_size = 0;

	if (data->type->elem_count < 0) {
		/* can only happen, if resolution failed before */
		assert(0);
		return 0;
	}
	
	basic_size = sizeof(union fauhdli_value);
	return basic_size * data->type->elem_count;
}

/** determine the complete storage size of one segment.
 *  @param seg data or transfer segmenet
 *  @return storage size of the segment in bytes.
 */
static size_t
symtab_get_seg_size(struct slist *seg)
{
	struct slist_entry *i;
	size_t offset = 0;
	size_t sz;

	for (i = seg->first; i != NULL; i = i->next) {
		struct data_definition *d = 
			(struct data_definition *)i->data;

		d->offset = offset;
		sz = symtab_get_data_size(d);
		d->storage_size = sz;
		offset += sz;
	}

	return offset;
}

static const struct data_definition *
symbol_data_reference_resolve(
	const struct symbol_table *symtab,
	const char *name
)
{
	struct symbol_table_data_ref *i;

	for (i = symtab->data_head; i != NULL; i = i->next) {
		if (strcmp(i->name, name) == 0) {
			assert(i->definition != NULL);
			return i->definition;
		}
	}

	symtab->callbacks->log(
		FAUHDLI_LOG_WARNING, "fauhdli", "symboltable",
		"cannot resolve reference \"%s\"\n", name);
	return NULL;
}

static const struct symbol_table_label *
symbol_label_resolve(const struct symbol_table *symtab, const char *name)
{
	unsigned int i;
	for (i = 0; i < symtab->nlabels; i++) {
		if (strcmp(name, symtab->labels[i].name) == 0) {
			return &symtab->labels[i];
		}
	}

	symtab->callbacks->log(
		FAUHDLI_LOG_ERROR, "fauhdli", "symboltable", 
		"cannot resolve label \"%s\"\n", name);
	return NULL;
}

static void
symtab_operand_container_resolve(
	const struct symbol_table *symtab, 
	struct operand *op
)
{
	struct symbol_table_container_ref *i;
	const char *name;

	assert(op->kind == OPERAND_REFERENCE);
	name = op->bytype.data.name;

	for (i = symtab->container_head; i != NULL; i = i->next) {
		if (strcmp(i->name, name) == 0) {
			op->bytype.data.container = i->container;
			op->bytype.data.ref = NULL;
			return;
		}
	}

	symtab->callbacks->log(FAUHDLI_LOG_ERROR, "fauhdli", "symbol_table",
		"could not resolve function/container %s\n", name);
	op->bytype.data.container = NULL;
}

static void
symtab_resolver_resolve(
	const struct symbol_table *symtab,
	struct data_definition *data
)
{
	struct symbol_table_container_ref *i;

	if (data->resolver.name == NULL) {
		return;
	}

	for (i = symtab->container_head; i != NULL; i = i->next) {
		if (strcmp(i->name, data->resolver.name) == 0) {
			data->resolver.container = i->container;
			symtab->callbacks->free(data->resolver.name);
			return;
		}
	}

	symtab->callbacks->log(FAUHDLI_LOG_ERROR, "fauhdli", "symbol_table",
		"could not resolver resolution function %s\n",
		data->resolver.name);
}


static void
symtab_resolve_transfer(
	const struct code_container *container,
	struct operand *tref,
	const struct glue_vhdl_cb *callbacks
)
{
	struct slist_entry *i;
	struct data_definition *d;

	assert(tref->kind == OPERAND_REFERENCE);

	if (container->transfer_segment == NULL) {
		callbacks->log(FAUHDLI_LOG_ERROR, "fauhdli", "symboltable",
			"Cannot resolve transfer reference \"%s\", since "
			"\"%s\" has no transfer paremeters.\n",
			tref->bytype.data.name, container->name);
		return;
	}

	for (i = container->transfer_segment->first; i != NULL; i = i->next) {
		d = (struct data_definition *)i->data;

		if (strcmp(d->name, tref->bytype.data.name) == 0) {
			/* matching entry */
			tref->bytype.data.ref = d;
			tref->bytype.data.container = NULL;
			return;
		}
	}

	callbacks->log(FAUHDLI_LOG_ERROR, "fauhdli", "symboltable",
		"cannot resolve transfer element \"%s\" in "
		"container \"%s\"\n", tref->bytype.data.name, 
		container->name);
}


static void
symtab_operand_resolve(
	struct symbol_table *symtab, 
	struct operand *op
)
{
	const struct symbol_table_label *entry;
	const struct data_definition *ref;

	switch (op->kind) {
	case OPERAND_TARGET:
		entry = symbol_label_resolve(symtab, 
					op->bytype.target.name);
		op->bytype.target.ref = entry->target;
		break;

	case OPERAND_REFERENCE:
		ref = symbol_data_reference_resolve(symtab,
					op->bytype.data.name);
		op->bytype.data.ref = ref;
		op->bytype.data.container = NULL;
		break;

	default:
		break;
	}
}

static void
symtab_opcode_resolve(
	struct symbol_table *symtab, 
	struct opcode *opcode
)
{
	const struct annotation_spec *spec = 
		fauhdli_find_annotation("foreign", opcode->annotations);

	/* special handling for opcodes that have container references */
	switch (opcode->kind) {
	case OPCODE_BEGINTRANS:
	case OPCODE_ENDTRANS:
	case OPCODE_CALL:
	case OPCODE_PROC:
		/* op1: container */
		assert(opcode->op1 != NULL);
		if (spec != NULL) {
			/* don't resolve the container for foreign 
			 * function call opcodes */
			return;
		}
		symtab_operand_container_resolve(symtab, opcode->op1);
		return;

	case OPCODE_SETPARAM:
		/* op2: container, op3: transfer element of container op2 */
		assert(opcode->op1 != NULL);
		assert(opcode->op2 != NULL);
		assert(opcode->op3 != NULL);

		symtab_operand_resolve(symtab, opcode->op1);

		if (spec != NULL) {
			/* don't resolve containers of foreign setparam */
			return;
		}
		symtab_operand_container_resolve(symtab, opcode->op2);

		assert(opcode->op2->kind == OPERAND_REFERENCE);
		assert(opcode->op2->bytype.data.container != NULL);

		symtab_resolve_transfer(
				opcode->op2->bytype.data.container,
				opcode->op3,
				symtab->callbacks);
		return;
	
	case OPCODE_GETPARAM:
		/* op2: container, op1: transfer element of container op2 */
		assert(opcode->op1 != NULL);
		assert(opcode->op2 != NULL);
		assert(opcode->op3 != NULL);

		symtab_operand_resolve(symtab, opcode->op3);
		if (spec != NULL) {
			/* don't resolve containers of foreign setparam */
			return;
		}
		symtab_operand_container_resolve(symtab, opcode->op2);

		assert(opcode->op2->kind == OPERAND_REFERENCE);
		assert(opcode->op2->bytype.data.container != NULL);

		symtab_resolve_transfer(
				opcode->op2->bytype.data.container,
				opcode->op1,
				symtab->callbacks);
		return;

	case OPCODE_AOFFSET:
	case OPCODE_ROFFSET:
		assert(opcode->indexed_type != NULL);
		symbol_resolve_type_element(symtab, opcode->indexed_type, 0);
		break;

	default:
		break;
	}

	if (opcode->op1 != NULL) {
		symtab_operand_resolve(symtab, opcode->op1);
	}

	if (opcode->op2 != NULL) {
		symtab_operand_resolve(symtab, opcode->op2);
	}

	if (opcode->op3 != NULL) {
		symtab_operand_resolve(symtab, opcode->op3);
	}
}

static void
symtab_register_labels(
	struct symbol_table *symtab,
	struct slist *text_seg
)
{
	struct slist_entry *i;
	struct opcode *opcode;

	for (i = text_seg->first; i != NULL; i = i->next) {
		opcode = (struct opcode*)i->data;

		switch (opcode->kind) {
		case OPCODE_LABEL:
			assert(opcode->label != NULL);
			symbol_label_add(symtab, opcode->label, i);
			break;

		default:
			break;
		}
	}
}

static void
symtab_resolve_text_seg(
	struct symbol_table *symtab,
	struct slist *seg
)
{
	struct slist_entry *i;

	for (i = seg->first; i != NULL; i = i->next) {
		symtab_opcode_resolve(
			symtab,
			(struct opcode*)i->data
		);
	}
}

static void
symtab_register_data(
	struct symbol_table *symtab,
	struct slist *seg,
	unsigned int nesting_level,
	enum segment_kind loc
)
{
	struct slist_entry *i;
	struct data_definition *d;

	for (i = seg->first; i != NULL; i = i->next) {
		d = (struct data_definition *)i->data;

		d->nesting_level = nesting_level;
		d->loc = loc;
		symtab_register_data_ref(symtab, d, nesting_level);

		symbol_resolve_type_element(symtab, d->type, 0);
		symtab_resolver_resolve(symtab,	d);
	}
}

static void
symtab_register_types(struct symbol_table *symtab, struct slist *seg)
{
	struct slist_entry *i;
	struct type_declaration *t;

	for (i = seg->first; i != NULL; i = i->next) {
		t = (struct type_declaration *)i->data;
		
		symbol_type_add(symtab, t);
		symbol_resolve_type_elements(symtab, t);
	}
}


static void
symtab_walk_container(
	struct symbol_table *symtab, 
	struct code_container *container,
	unsigned int nesting_level
)
{
	struct slist_entry *i;

	container->nesting_level = nesting_level;
	symtab_register_container_ref(symtab, container, nesting_level);

	if (container->type_definitions != NULL) {
		symtab_register_types(symtab, container->type_definitions);
	}

	if (container->transfer_segment != NULL) {
		symtab_register_data(symtab, container->transfer_segment, 
					nesting_level, SEGMENT_TRANSFER);
		container->transfer_size = 
			symtab_get_seg_size(container->transfer_segment);
	} else {
		container->transfer_size = 0;
	}

	if (container->stack_segment != NULL) {
		symtab_register_data(symtab, container->stack_segment,
					nesting_level, SEGMENT_STACK);
		container->stack_size = 
			symtab_get_seg_size(container->stack_segment);
	} else {
		container->stack_size = 0;
	}

	if (container->sub_containers != NULL) {
		for (i = container->sub_containers->first; i != NULL; 
			i = i->next) {

			symtab_walk_container(
				symtab, 
				(struct code_container*)i->data,
				nesting_level + 1
			);
		}
	}

	if (container->text_segment != NULL) {
		symtab_register_labels(
				symtab,
				container->text_segment
		);
		symtab_resolve_text_seg(symtab, container->text_segment);
		symtab_clear_labels(symtab);
	}

	symtab_remove_container_refs(symtab, nesting_level + 1);
	symtab_remove_data_refs(symtab, nesting_level);
}

static void
symbol_table_register_builtins(
	struct fauhdli *instance, 
	struct symbol_table *symtab
)
{
	/* universal_integer */
	static struct type_declaration univ_int_t = {
		.elements = NULL, /* internal */
		.elem_count = 1
	};

	/* universal_real */
	static struct type_declaration univ_real_t = {
		.elements = NULL, /* internal */
		.elem_count = 1
	};

	static struct type_declaration base_pointer_t = {
		.elements = NULL, /* internal */
		.elem_count = 1
	};

	univ_int_t.name = strdup("universal_integer");
	slset_add(
		instance->cleanup_ptrs, 
		univ_int_t.name, 
		symtab->callbacks->malloc);

	univ_real_t.name = strdup("universal_real");
	slset_add(
		instance->cleanup_ptrs, 
		univ_real_t.name,
		symtab->callbacks->malloc);

	base_pointer_t.name = strdup("__pointer__");
	slset_add(
		instance->cleanup_ptrs, 
		base_pointer_t.name,
		symtab->callbacks->malloc);

	symbol_type_add(symtab, &univ_int_t);
	symbol_type_add(symtab, &univ_real_t);
	symbol_type_add(symtab, &base_pointer_t);

	/* TODO: builtin functions */
}

static void
symbol_table_init(struct fauhdli *instance, struct symbol_table *symtab)
{
	symtab->nlabels = 0;
	symtab->ntypes = 0;
	symtab->container_head = NULL;
	symtab->container_tail = NULL;
	symtab->data_head = NULL;
	symtab->data_tail = NULL;
	symtab->callbacks = &instance->callbacks;

	symbol_table_register_builtins(instance, symtab);
}

void
fauhdli_resolve_symbols(struct fauhdli *instance)
{
	struct symbol_table symtab;

	assert(instance->container != NULL);
	symbol_table_init(instance, &symtab);

	symtab_walk_container(&symtab, instance->container, 1);
	symtab_remove_container_refs(&symtab, 0);
}