Logo Search packages:      
Sourcecode: fauhdlc version File versions

lookup_symbols.c

/* $Id: lookup_symbols.c 4321 2009-01-27 13:02: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 "libfauhdli.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;
};

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;
            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 = 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 = 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;
            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) {
            faum_log(FAUM_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;
      }
      
#if 0 /* obsolete, rather align everything to 64bit 
         -> cf. kernel/create_basic_data
              kernel/eval_offset
*/
      switch (data->storage) {
      case STORAGE_VARIABLE:
            basic_size = sizeof(union fauhdli_value);
            break;

      case STORAGE_SIGNAL:
            basic_size = sizeof(struct signal *);
            break;
      
      case STORAGE_DRIVER:
            basic_size = sizeof(struct driver *);
            break;
      }
#else
      basic_size = sizeof(union fauhdli_value);
#endif /* obsolete code */

      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 declaration_element *decl = 
                  (struct declaration_element *)i->data;

            switch (decl->kind) {
            case DECLARATION_TYPE:
                  /* not interesting */
                  break;

            case DECLARATION_DATA:
                  decl->bytype.data_def.offset = offset;
                  sz = symtab_get_data_size(&decl->bytype.data_def);
                  decl->bytype.data_def.storage_size = sz;
                  offset += sz;
                  break;
            }

      }

      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;
            }
      }

      faum_log(FAUM_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];
            }
      }

      faum_log(FAUM_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;
            }
      }

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

static void
symtab_resolve_transfer(
      const struct code_container *container,
      struct operand *tref
)
{
      struct slist_entry *i;
      struct declaration_element *decl;

      assert(tref->kind == OPERAND_REFERENCE);

      if (container->transfer_segment == NULL) {
            faum_log(FAUM_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) {
            decl = (struct declaration_element *)i->data;

            switch (decl->kind) {
            case DECLARATION_TYPE:
                  /* not interesting */
                  break;

            case DECLARATION_DATA:
                  if (strcmp(
                        decl->bytype.data_def.name, 
                        tref->bytype.data.name) == 0) {

                        /* matching entry */
                        tref->bytype.data.ref = &decl->bytype.data_def;
                        tref->bytype.data.container = NULL;
                        return;
                  }
                  break;

            }
      }

      faum_log(FAUM_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);
            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);
            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 declaration_element *e;

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

            switch (e->kind) {
            case DECLARATION_TYPE:
                  symbol_type_add(symtab, &e->bytype.type_decl);
                  symbol_resolve_type_elements(symtab, 
                                    &e->bytype.type_decl);
                  break;

            case DECLARATION_DATA:
                  e->bytype.data_def.nesting_level = nesting_level;
                  e->bytype.data_def.loc = loc;
                  symtab_register_data_ref(symtab, &e->bytype.data_def,
                                    nesting_level);

                  symbol_resolve_type_element(
                                    symtab, 
                                    e->bytype.data_def.type,
                                    0);
                  break;

            }
      }
}

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->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);

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

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

      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;

      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);
}

Generated by  Doxygen 1.6.0   Back to index