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 "main/imports.h"
  25 #include "symbol_table.h"
  26 #include "../../util/hash_table.h"
  27
  28 struct symbol {
  29     /**
  30      * Link to the next symbol in the table with the same name
  31      *
  32      * The linked list of symbols with the same name is ordered by scope
  33      * from inner-most to outer-most.
  34      */
  35     struct symbol *next_with_same_name;
  36
  37
  38     /**
  39      * Link to the next symbol in the table with the same scope
  40      *
  41      * The linked list of symbols with the same scope is unordered.  Symbols
  42      * in this list my have unique names.
  43      */
  44     struct symbol *next_with_same_scope;
  45
  46
  47     /**
  48      * Header information for the list of symbols with the same name.
  49      */
  50     struct symbol_header *hdr;
  51
  52
  53     /**
  54      * Name space of the symbol
  55      *
  56      * Name space are arbitrary user assigned integers.  No two symbols can
  57      * exist in the same name space at the same scope level.
  58      */
  59     int name_space;
  60
  61     /** Scope depth where this symbol was defined. */
  62     unsigned depth;
  63
  64     /**
  65      * Arbitrary user supplied data.
  66      */
  67     void *data;
  68 };
  69
  70
  71 /**
  72  */
  73 struct symbol_header {
  74     /** Linkage in list of all headers in a given symbol table. */
  75     struct symbol_header *next;
  76
  77     /** Symbol name. */
  78     char *name;
  79
  80     /** Linked list of symbols with the same name. */
  81     struct symbol *symbols;
  82 };
  83
  84
  85 /**
  86  * Element of the scope stack.
  87  */
  88 struct scope_level {
  89     /** Link to next (inner) scope level. */
  90     struct scope_level *next;
  91
  92     /** Linked list of symbols with the same scope. */
  93     struct symbol *symbols;
  94 };
  95
  96
  97 /**
  98  *
  99  */
 100 struct _mesa_symbol_table {
 101     /** Hash table containing all symbols in the symbol table. */
 102     struct hash_table *ht;
 103
 104     /** Top of scope stack. */
 105     struct scope_level *current_scope;
 106
 107     /** List of all symbol headers in the table. */
 108     struct symbol_header *hdr;
 109
 110     /** Current scope depth. */
 111     unsigned depth;
 112 };
 113
 114
 115 static void
 116 check_symbol_table(struct _mesa_symbol_table *table)
 117 {
 118 #if !defined(NDEBUG)
 119     struct scope_level *scope;
 120
 121     for (scope = table->current_scope; scope != NULL; scope = scope->next) {
 122         struct symbol *sym;
 123
 124         for (sym = scope->symbols
 125              ; sym != NULL
 126              ; sym = sym->next_with_same_name) {
 127             const struct symbol_header *const hdr = sym->hdr;
 128             struct symbol *sym2;
 129
 130             for (sym2 = hdr->symbols
 131                  ; sym2 != NULL
 132                  ; sym2 = sym2->next_with_same_name) {
 133                 assert(sym2->hdr == hdr);
 134             }
 135         }
 136     }
 137 #else
 138     (void) table;
 139 #endif /* !defined(NDEBUG) */
 140 }
 141
 142 void
 143 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
 144 {
 145     struct scope_level *const scope = table->current_scope;
 146     struct symbol *sym = scope->symbols;
 147
 148     table->current_scope = scope->next;
 149     table->depth--;
 150
 151     free(scope);
 152
 153     while (sym != NULL) {
 154         struct symbol *const next = sym->next_with_same_scope;
 155         struct symbol_header *const hdr = sym->hdr;
 156
 157         assert(hdr->symbols == sym);
 158
 159         hdr->symbols = sym->next_with_same_name;
 160
 161         free(sym);
 162
 163         sym = next;
 164     }
 165
 166     check_symbol_table(table);
 167 }
 168
 169
 170 void
 171 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 172 {
 173     struct scope_level *const scope = calloc(1, sizeof(*scope));
 174
 175     if (scope == NULL) {
 176        _mesa_error_no_memory(__func__);
 177        return;
 178     }
 179
 180     scope->next = table->current_scope;
 181     table->current_scope = scope;
 182     table->depth++;
 183 }
 184
 185
 186 static struct symbol_header *
 187 find_symbol(struct _mesa_symbol_table *table, const char *name)
 188 {
 189    struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
 190    return entry ? (struct symbol_header *) entry->data : NULL;
 191 }
 192
 193
 194 /**
 195  * Determine the scope "distance" of a symbol from the current scope
 196  *
 197  * \return
 198  * A non-negative number for the number of scopes between the current scope
 199  * and the scope where a symbol was defined.  A value of zero means the current
 200  * scope.  A negative number if the symbol does not exist.
 201  */
 202 int
 203 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
 204                                 int name_space, const char *name)
 205 {
 206     struct symbol_header *const hdr = find_symbol(table, name);
 207     struct symbol *sym;
 208
 209     if (hdr != NULL) {
 210        for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 211           assert(sym->hdr == hdr);
 212
 213           if ((name_space == -1) || (sym->name_space == name_space)) {
 214              assert(sym->depth <= table->depth);
 215              return sym->depth - table->depth;
 216           }
 217        }
 218     }
 219
 220     return -1;
 221 }
 222
 223
 224 void *
 225 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
 226                                int name_space, const char *name)
 227 {
 228     struct symbol_header *const hdr = find_symbol(table, name);
 229
 230     if (hdr != NULL) {
 231         struct symbol *sym;
 232
 233
 234         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 235             assert(sym->hdr == hdr);
 236
 237             if ((name_space == -1) || (sym->name_space == name_space)) {
 238                 return sym->data;
 239             }
 240         }
 241     }
 242
 243     return NULL;
 244 }
 245
 246
 247 int
 248 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
 249                               int name_space, const char *name,
 250                               void *declaration)
 251 {
 252     struct symbol_header *hdr;
 253     struct symbol *sym;
 254
 255     check_symbol_table(table);
 256
 257     hdr = find_symbol(table, name);
 258
 259     check_symbol_table(table);
 260
 261     if (hdr == NULL) {
 262        hdr = calloc(1, sizeof(*hdr));
 263        if (hdr == NULL) {
 264           _mesa_error_no_memory(__func__);
 265           return -1;
 266        }
 267
 268        hdr->name = strdup(name);
 269        if (hdr->name == NULL) {
 270           free(hdr);
 271           _mesa_error_no_memory(__func__);
 272           return -1;
 273        }
 274
 275        _mesa_hash_table_insert(table->ht, hdr->name, hdr);
 276        hdr->next = table->hdr;
 277        table->hdr = hdr;
 278     }
 279
 280     check_symbol_table(table);
 281
 282     /* If the symbol already exists in this namespace at this scope, it cannot
 283      * be added to the table.
 284      */
 285     for (sym = hdr->symbols
 286          ; (sym != NULL) && (sym->name_space != name_space)
 287          ; sym = sym->next_with_same_name) {
 288        /* empty */
 289     }
 290
 291     if (sym && (sym->depth == table->depth))
 292        return -1;
 293
 294     sym = calloc(1, sizeof(*sym));
 295     if (sym == NULL) {
 296        _mesa_error_no_memory(__func__);
 297        return -1;
 298     }
 299
 300     sym->next_with_same_name = hdr->symbols;
 301     sym->next_with_same_scope = table->current_scope->symbols;
 302     sym->hdr = hdr;
 303     sym->name_space = name_space;
 304     sym->data = declaration;
 305     sym->depth = table->depth;
 306
 307     assert(sym->hdr == hdr);
 308
 309     hdr->symbols = sym;
 310     table->current_scope->symbols = sym;
 311
 312     check_symbol_table(table);
 313     return 0;
 314 }
 315
 316
 317 int
 318 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
 319                                      int name_space, const char *name,
 320                                      void *declaration)
 321 {
 322     struct symbol_header *hdr;
 323     struct symbol *sym;
 324     struct symbol *curr;
 325     struct scope_level *top_scope;
 326
 327     check_symbol_table(table);
 328
 329     hdr = find_symbol(table, name);
 330
 331     check_symbol_table(table);
 332
 333     if (hdr == NULL) {
 334         hdr = calloc(1, sizeof(*hdr));
 335         if (hdr == NULL) {
 336            _mesa_error_no_memory(__func__);
 337            return -1;
 338         }
 339
 340         hdr->name = strdup(name);
 341
 342         _mesa_hash_table_insert(table->ht, hdr->name, hdr);
 343         hdr->next = table->hdr;
 344         table->hdr = hdr;
 345     }
 346
 347     check_symbol_table(table);
 348
 349     /* If the symbol already exists in this namespace at this scope, it cannot
 350      * be added to the table.
 351      */
 352     for (sym = hdr->symbols
 353          ; (sym != NULL) && (sym->name_space != name_space)
 354          ; sym = sym->next_with_same_name) {
 355        /* empty */
 356     }
 357
 358     if (sym && sym->depth == 0)
 359        return -1;
 360
 361     /* Find the top-level scope */
 362     for (top_scope = table->current_scope
 363          ; top_scope->next != NULL
 364          ; top_scope = top_scope->next) {
 365        /* empty */
 366     }
 367
 368     sym = calloc(1, sizeof(*sym));
 369     if (sym == NULL) {
 370        _mesa_error_no_memory(__func__);
 371        return -1;
 372     }
 373
 374     sym->next_with_same_scope = top_scope->symbols;
 375     sym->hdr = hdr;
 376     sym->name_space = name_space;
 377     sym->data = declaration;
 378
 379     assert(sym->hdr == hdr);
 380
 381     /* Since next_with_same_name is ordered by scope, we need to append the
 382      * new symbol to the _end_ of the list.
 383      */
 384     if (hdr->symbols == NULL) {
 385        hdr->symbols = sym;
 386     } else {
 387        for (curr = hdr->symbols
 388             ; curr->next_with_same_name != NULL
 389             ; curr = curr->next_with_same_name) {
 390           /* empty */
 391        }
 392        curr->next_with_same_name = sym;
 393     }
 394     top_scope->symbols = sym;
 395
 396     check_symbol_table(table);
 397     return 0;
 398 }
 399
 400
 401
 402 struct _mesa_symbol_table *
 403 _mesa_symbol_table_ctor(void)
 404 {
 405     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
 406
 407     if (table != NULL) {
 408        table->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
 409                                            _mesa_key_string_equal);
 410
 411        _mesa_symbol_table_push_scope(table);
 412     }
 413
 414     return table;
 415 }
 416
 417
 418 void
 419 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
 420 {
 421    struct symbol_header *hdr;
 422    struct symbol_header *next;
 423
 424    while (table->current_scope != NULL) {
 425       _mesa_symbol_table_pop_scope(table);
 426    }
 427
 428    for (hdr = table->hdr; hdr != NULL; hdr = next) {
 429        next = hdr->next;
 430        free(hdr->name);
 431        free(hdr);
 432    }
 433
 434    _mesa_hash_table_destroy(table->ht, NULL);
 435    free(table);
 436 }