mesa/program/symbol_table.c

/*
 * Copyright © 2008 Intel Corporation
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */

#include "main/imports.h"
#include "symbol_table.h"
#include "hash_table.h"

struct symbol {
    /**
     * Link to the next symbol in the table with the same name
     *
     * The linked list of symbols with the same name is ordered by scope
     * from inner-most to outer-most.
     */
    struct symbol *next_with_same_name;


    /**
     * Link to the next symbol in the table with the same scope
     *
     * The linked list of symbols with the same scope is unordered.  Symbols
     * in this list my have unique names.
     */
    struct symbol *next_with_same_scope;


    /**
     * Header information for the list of symbols with the same name.
     */
    struct symbol_header *hdr;


    /**
     * Name space of the symbol
     *
     * Name space are arbitrary user assigned integers.  No two symbols can
     * exist in the same name space at the same scope level.
     */
    int name_space;

    /** Scope depth where this symbol was defined. */
    unsigned depth;

    /**
     * Arbitrary user supplied data.
     */
    void *data;
};


/**
 */
struct symbol_header {
    /** Linkage in list of all headers in a given symbol table. */
    struct symbol_header *next;

    /** Symbol name. */
    char *name;

    /** Linked list of symbols with the same name. */
    struct symbol *symbols;
};


/**
 * Element of the scope stack.
 */
struct scope_level {
    /** Link to next (inner) scope level. */
    struct scope_level *next;

    /** Linked list of symbols with the same scope. */
    struct symbol *symbols;
};


/**
 *
 */
struct _mesa_symbol_table {
    /** Hash table containing all symbols in the symbol table. */
    struct hash_table *ht;

    /** Top of scope stack. */
    struct scope_level *current_scope;

    /** List of all symbol headers in the table. */
    struct symbol_header *hdr;

    /** Current scope depth. */
    unsigned depth;
};


struct _mesa_symbol_table_iterator {
    /**
     * Name space of symbols returned by this iterator.
     */
    int name_space;


    /**
     * Currently iterated symbol
     *
     * The next call to \c _mesa_symbol_table_iterator_get will return this
     * value.  It will also update this value to the value that should be
     * returned by the next call.
     */
    struct symbol *curr;
};


static void
check_symbol_table(struct _mesa_symbol_table *table)
{
#if 1
    struct scope_level *scope;

    for (scope = table->current_scope; scope != NULL; scope = scope->next) {
        struct symbol *sym;

        for (sym = scope->symbols
             ; sym != NULL
             ; sym = sym->next_with_same_name) {
            const struct symbol_header *const hdr = sym->hdr;
            struct symbol *sym2;

            for (sym2 = hdr->symbols
                 ; sym2 != NULL
                 ; sym2 = sym2->next_with_same_name) {
                assert(sym2->hdr == hdr);
            }
        }
    }
#endif
}

void
_mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
{
    struct scope_level *const scope = table->current_scope;
    struct symbol *sym = scope->symbols;

    table->current_scope = scope->next;
    table->depth--;

    free(scope);

    while (sym != NULL) {
        struct symbol *const next = sym->next_with_same_scope;
        struct symbol_header *const hdr = sym->hdr;

        assert(hdr->symbols == sym);

        hdr->symbols = sym->next_with_same_name;

        free(sym);

        sym = next;
    }

    check_symbol_table(table);
}


void
_mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
{
    struct scope_level *const scope = calloc(1, sizeof(*scope));

    scope->next = table->current_scope;
    table->current_scope = scope;
    table->depth++;
}


static struct symbol_header *
find_symbol(struct _mesa_symbol_table *table, const char *name)
{
    return (struct symbol_header *) hash_table_find(table->ht, name);
}


struct _mesa_symbol_table_iterator *
_mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table,
                                 int name_space, const char *name)
{
    struct _mesa_symbol_table_iterator *iter = calloc(1, sizeof(*iter));
    struct symbol_header *const hdr = find_symbol(table, name);

    iter->name_space = name_space;

    if (hdr != NULL) {
        struct symbol *sym;

        for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
            assert(sym->hdr == hdr);

            if ((name_space == -1) || (sym->name_space == name_space)) {
                iter->curr = sym;
                break;
            }
        }
    }

    return iter;
}


void
_mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter)
{
    free(iter);
}


void *
_mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter)
{
    return (iter->curr == NULL) ? NULL : iter->curr->data;
}


int
_mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter)
{
    struct symbol_header *hdr;

    if (iter->curr == NULL) {
        return 0;
    }

    hdr = iter->curr->hdr;
    iter->curr = iter->curr->next_with_same_name;

    while (iter->curr != NULL) {
        assert(iter->curr->hdr == hdr);

        if ((iter->name_space == -1)
            || (iter->curr->name_space == iter->name_space)) {
            return 1;
        }

        iter->curr = iter->curr->next_with_same_name;
    }

    return 0;
}


/**
 * Determine the scope "distance" of a symbol from the current scope
 *
 * \return
 * A non-negative number for the number of scopes between the current scope
 * and the scope where a symbol was defined.  A value of zero means the current
 * scope.  A negative number if the symbol does not exist.
 */
int
_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
				int name_space, const char *name)
{
    struct symbol_header *const hdr = find_symbol(table, name);
    struct symbol *sym;

    if (hdr != NULL) {
       for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
	  assert(sym->hdr == hdr);

	  if ((name_space == -1) || (sym->name_space == name_space)) {
	     assert(sym->depth <= table->depth);
	     return sym->depth - table->depth;
	  }
       }
    }

    return -1;
}


void *
_mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
                               int name_space, const char *name)
{
    struct symbol_header *const hdr = find_symbol(table, name);

    if (hdr != NULL) {
        struct symbol *sym;


        for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
            assert(sym->hdr == hdr);

            if ((name_space == -1) || (sym->name_space == name_space)) {
                return sym->data;
            }
        }
    }

    return NULL;
}


int
_mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
                              int name_space, const char *name,
                              void *declaration)
{
    struct symbol_header *hdr;
    struct symbol *sym;

    check_symbol_table(table);

    hdr = find_symbol(table, name);

    check_symbol_table(table);

    if (hdr == NULL) {
       hdr = calloc(1, sizeof(*hdr));
       hdr->name = strdup(name);

       hash_table_insert(table->ht, hdr, hdr->name);
       hdr->next = table->hdr;
       table->hdr = hdr;
    }

    check_symbol_table(table);

    /* If the symbol already exists in this namespace at this scope, it cannot
     * be added to the table.
     */
    for (sym = hdr->symbols
	 ; (sym != NULL) && (sym->name_space != name_space)
	 ; sym = sym->next_with_same_name) {
       /* empty */
    }

    if (sym && (sym->depth == table->depth))
       return -1;

    sym = calloc(1, sizeof(*sym));
    sym->next_with_same_name = hdr->symbols;
    sym->next_with_same_scope = table->current_scope->symbols;
    sym->hdr = hdr;
    sym->name_space = name_space;
    sym->data = declaration;
    sym->depth = table->depth;

    assert(sym->hdr == hdr);

    hdr->symbols = sym;
    table->current_scope->symbols = sym;

    check_symbol_table(table);
    return 0;
}


int
_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
				     int name_space, const char *name,
				     void *declaration)
{
    struct symbol_header *hdr;
    struct symbol *sym;
    struct symbol *curr;
    struct scope_level *top_scope;

    check_symbol_table(table);

    hdr = find_symbol(table, name);

    check_symbol_table(table);

    if (hdr == NULL) {
        hdr = calloc(1, sizeof(*hdr));
        hdr->name = strdup(name);

        hash_table_insert(table->ht, hdr, hdr->name);
        hdr->next = table->hdr;
        table->hdr = hdr;
    }

    check_symbol_table(table);

    /* If the symbol already exists in this namespace at this scope, it cannot
     * be added to the table.
     */
    for (sym = hdr->symbols
	 ; (sym != NULL) && (sym->name_space != name_space)
	 ; sym = sym->next_with_same_name) {
       /* empty */
    }

    if (sym && sym->depth == 0)
       return -1;

    /* Find the top-level scope */
    for (top_scope = table->current_scope
	 ; top_scope->next != NULL
	 ; top_scope = top_scope->next) {
       /* empty */
    }

    sym = calloc(1, sizeof(*sym));
    sym->next_with_same_scope = top_scope->symbols;
    sym->hdr = hdr;
    sym->name_space = name_space;
    sym->data = declaration;

    assert(sym->hdr == hdr);

    /* Since next_with_same_name is ordered by scope, we need to append the
     * new symbol to the _end_ of the list.
     */
    if (hdr->symbols == NULL) {
       hdr->symbols = sym;
    } else {
       for (curr = hdr->symbols
	    ; curr->next_with_same_name != NULL
	    ; curr = curr->next_with_same_name) {
	  /* empty */
       }
       curr->next_with_same_name = sym;
    }
    top_scope->symbols = sym;

    check_symbol_table(table);
    return 0;
}


struct _mesa_symbol_table *
_mesa_symbol_table_ctor(void)
{
    struct _mesa_symbol_table *table = calloc(1, sizeof(*table));

    if (table != NULL) {
       table->ht = hash_table_ctor(32, hash_table_string_hash,
				   hash_table_string_compare);

       _mesa_symbol_table_push_scope(table);
    }

    return table;
}


void
_mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
{
   struct symbol_header *hdr;
   struct symbol_header *next;

   while (table->current_scope != NULL) {
      _mesa_symbol_table_pop_scope(table);
   }

   for (hdr = table->hdr; hdr != NULL; hdr = next) {
       next = hdr->next;
       free(hdr->name);
       free(hdr);
   }

   hash_table_dtor(table->ht);
   free(table);
}