src/mesa/program/symbol_table.c

   1 /*
   2  * Copyright © 2008 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 #include "util/imports.h"
  25 #include "main/errors.h"
  26 #include "symbol_table.h"
  27 #include "../../util/hash_table.h"
  28 #include "util/u_string.h"
  29
  30 struct symbol {
  31    /** Symbol name. */
  32    char *name;
  33
  34     /**
  35      * Link to the next symbol in the table with the same name
  36      *
  37      * The linked list of symbols with the same name is ordered by scope
  38      * from inner-most to outer-most.
  39      */
  40     struct symbol *next_with_same_name;
  41
  42     /**
  43      * Link to the next symbol in the table with the same scope
  44      *
  45      * The linked list of symbols with the same scope is unordered.  Symbols
  46      * in this list my have unique names.
  47      */
  48     struct symbol *next_with_same_scope;
  49
  50     /** Scope depth where this symbol was defined. */
  51     unsigned depth;
  52
  53     /**
  54      * Arbitrary user supplied data.
  55      */
  56     void *data;
  57 };
  58
  59
  60 /**
  61  * Element of the scope stack.
  62  */
  63 struct scope_level {
  64     /** Link to next (inner) scope level. */
  65     struct scope_level *next;
  66
  67     /** Linked list of symbols with the same scope. */
  68     struct symbol *symbols;
  69 };
  70
  71
  72 /**
  73  *
  74  */
  75 struct _mesa_symbol_table {
  76     /** Hash table containing all symbols in the symbol table. */
  77     struct hash_table *ht;
  78
  79     /** Top of scope stack. */
  80     struct scope_level *current_scope;
  81
  82     /** Current scope depth. */
  83     unsigned depth;
  84 };
  85
  86 void
  87 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
  88 {
  89     struct scope_level *const scope = table->current_scope;
  90     struct symbol *sym = scope->symbols;
  91
  92     table->current_scope = scope->next;
  93     table->depth--;
  94
  95     free(scope);
  96
  97     while (sym != NULL) {
  98         struct symbol *const next = sym->next_with_same_scope;
  99         struct hash_entry *hte = _mesa_hash_table_search(table->ht,
 100                                                          sym->name);
 101         if (sym->next_with_same_name) {
 102            /* If there is a symbol with this name in an outer scope update
 103             * the hash table to point to it.
 104             */
 105            hte->key = sym->next_with_same_name->name;
 106            hte->data = sym->next_with_same_name;
 107         } else {
 108            _mesa_hash_table_remove(table->ht, hte);
 109            free(sym->name);
 110         }
 111
 112         free(sym);
 113         sym = next;
 114     }
 115 }
 116
 117
 118 void
 119 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 120 {
 121     struct scope_level *const scope = calloc(1, sizeof(*scope));
 122     if (scope == NULL) {
 123        _mesa_error_no_memory(__func__);
 124        return;
 125     }
 126
 127     scope->next = table->current_scope;
 128     table->current_scope = scope;
 129     table->depth++;
 130 }
 131
 132
 133 static struct symbol *
 134 find_symbol(struct _mesa_symbol_table *table, const char *name)
 135 {
 136    struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
 137    return entry ? (struct symbol *) entry->data : NULL;
 138 }
 139
 140
 141 /**
 142  * Determine the scope "distance" of a symbol from the current scope
 143  *
 144  * \return
 145  * A non-negative number for the number of scopes between the current scope
 146  * and the scope where a symbol was defined.  A value of zero means the current
 147  * scope.  A negative number if the symbol does not exist.
 148  */
 149 int
 150 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
 151                                 const char *name)
 152 {
 153    struct symbol *const sym = find_symbol(table, name);
 154
 155    if (sym) {
 156       assert(sym->depth <= table->depth);
 157       return sym->depth - table->depth;
 158    }
 159
 160    return -1;
 161 }
 162
 163
 164 void *
 165 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
 166                                const char *name)
 167 {
 168    struct symbol *const sym = find_symbol(table, name);
 169    if (sym)
 170       return sym->data;
 171
 172    return NULL;
 173 }
 174
 175
 176 int
 177 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
 178                               const char *name, void *declaration)
 179 {
 180    struct symbol *new_sym;
 181    struct symbol *sym = find_symbol(table, name);
 182
 183    if (sym && sym->depth == table->depth)
 184       return -1;
 185
 186    new_sym = calloc(1, sizeof(*sym));
 187    if (new_sym == NULL) {
 188       _mesa_error_no_memory(__func__);
 189       return -1;
 190    }
 191
 192    if (sym) {
 193       /* Store link to symbol in outer scope with the same name */
 194       new_sym->next_with_same_name = sym;
 195       new_sym->name = sym->name;
 196    } else {
 197       new_sym->name = strdup(name);
 198       if (new_sym->name == NULL) {
 199          free(new_sym);
 200          _mesa_error_no_memory(__func__);
 201          return -1;
 202       }
 203    }
 204
 205    new_sym->next_with_same_scope = table->current_scope->symbols;
 206    new_sym->data = declaration;
 207    new_sym->depth = table->depth;
 208
 209    table->current_scope->symbols = new_sym;
 210
 211    _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
 212
 213    return 0;
 214 }
 215
 216 int
 217 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
 218                                   const char *name,
 219                                   void *declaration)
 220 {
 221     struct symbol *sym = find_symbol(table, name);
 222
 223     /* If the symbol doesn't exist, it cannot be replaced. */
 224     if (sym == NULL)
 225        return -1;
 226
 227     sym->data = declaration;
 228     return 0;
 229 }
 230
 231 int
 232 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
 233                                      const char *name, void *declaration)
 234 {
 235    struct scope_level *top_scope;
 236    struct symbol *inner_sym = NULL;
 237    struct symbol *sym = find_symbol(table, name);
 238
 239    while (sym) {
 240       if (sym->depth == 0)
 241          return -1;
 242
 243       inner_sym = sym;
 244
 245       /* Get symbol from the outer scope with the same name */
 246       sym = sym->next_with_same_name;
 247    }
 248
 249    /* Find the top-level scope */
 250    for (top_scope = table->current_scope; top_scope->next != NULL;
 251         top_scope = top_scope->next) {
 252       /* empty */
 253    }
 254
 255    sym = calloc(1, sizeof(*sym));
 256    if (sym == NULL) {
 257       _mesa_error_no_memory(__func__);
 258       return -1;
 259    }
 260
 261    if (inner_sym) {
 262       /* In case we add the global out of order store a link to the global
 263        * symbol in global.
 264        */
 265       inner_sym->next_with_same_name = sym;
 266
 267       sym->name = inner_sym->name;
 268    } else {
 269       sym->name = strdup(name);
 270       if (sym->name == NULL) {
 271          free(sym);
 272          _mesa_error_no_memory(__func__);
 273          return -1;
 274       }
 275    }
 276
 277    sym->next_with_same_scope = top_scope->symbols;
 278    sym->data = declaration;
 279
 280    top_scope->symbols = sym;
 281
 282    _mesa_hash_table_insert(table->ht, sym->name, sym);
 283
 284    return 0;
 285 }
 286
 287
 288
 289 struct _mesa_symbol_table *
 290 _mesa_symbol_table_ctor(void)
 291 {
 292     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
 293
 294     if (table != NULL) {
 295        table->ht = _mesa_hash_table_create(NULL, _mesa_hash_string,
 296                                            _mesa_key_string_equal);
 297
 298        _mesa_symbol_table_push_scope(table);
 299     }
 300
 301     return table;
 302 }
 303
 304
 305 void
 306 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
 307 {
 308    while (table->current_scope != NULL) {
 309       _mesa_symbol_table_pop_scope(table);
 310    }
 311
 312    _mesa_hash_table_destroy(table->ht, NULL);
 313    free(table);
 314 }