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 "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 struct _mesa_symbol_table_iterator {
 116     /**
 117      * Name space of symbols returned by this iterator.
 118      */
 119     int name_space;
 120
 121
 122     /**
 123      * Currently iterated symbol
 124      *
 125      * The next call to \c _mesa_symbol_table_iterator_get will return this
 126      * value.  It will also update this value to the value that should be
 127      * returned by the next call.
 128      */
 129     struct symbol *curr;
 130 };
 131
 132
 133 static void
 134 check_symbol_table(struct _mesa_symbol_table *table)
 135 {
 136 #if 1
 137     struct scope_level *scope;
 138
 139     for (scope = table->current_scope; scope != NULL; scope = scope->next) {
 140         struct symbol *sym;
 141
 142         for (sym = scope->symbols
 143              ; sym != NULL
 144              ; sym = sym->next_with_same_name) {
 145             const struct symbol_header *const hdr = sym->hdr;
 146             struct symbol *sym2;
 147
 148             for (sym2 = hdr->symbols
 149                  ; sym2 != NULL
 150                  ; sym2 = sym2->next_with_same_name) {
 151                 assert(sym2->hdr == hdr);
 152             }
 153         }
 154     }
 155 #endif
 156 }
 157
 158 void
 159 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
 160 {
 161     struct scope_level *const scope = table->current_scope;
 162     struct symbol *sym = scope->symbols;
 163
 164     table->current_scope = scope->next;
 165     table->depth--;
 166
 167     free(scope);
 168
 169     while (sym != NULL) {
 170         struct symbol *const next = sym->next_with_same_scope;
 171         struct symbol_header *const hdr = sym->hdr;
 172
 173         assert(hdr->symbols == sym);
 174
 175         hdr->symbols = sym->next_with_same_name;
 176
 177         free(sym);
 178
 179         sym = next;
 180     }
 181
 182     check_symbol_table(table);
 183 }
 184
 185
 186 void
 187 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 188 {
 189     struct scope_level *const scope = calloc(1, sizeof(*scope));
 190
 191     scope->next = table->current_scope;
 192     table->current_scope = scope;
 193     table->depth++;
 194 }
 195
 196
 197 static struct symbol_header *
 198 find_symbol(struct _mesa_symbol_table *table, const char *name)
 199 {
 200     return (struct symbol_header *) hash_table_find(table->ht, name);
 201 }
 202
 203
 204 struct _mesa_symbol_table_iterator *
 205 _mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table,
 206                                  int name_space, const char *name)
 207 {
 208     struct _mesa_symbol_table_iterator *iter = calloc(1, sizeof(*iter));
 209     struct symbol_header *const hdr = find_symbol(table, name);
 210
 211     iter->name_space = name_space;
 212
 213     if (hdr != NULL) {
 214         struct symbol *sym;
 215
 216         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 217             assert(sym->hdr == hdr);
 218
 219             if ((name_space == -1) || (sym->name_space == name_space)) {
 220                 iter->curr = sym;
 221                 break;
 222             }
 223         }
 224     }
 225
 226     return iter;
 227 }
 228
 229
 230 void
 231 _mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter)
 232 {
 233     free(iter);
 234 }
 235
 236
 237 void *
 238 _mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter)
 239 {
 240     return (iter->curr == NULL) ? NULL : iter->curr->data;
 241 }
 242
 243
 244 int
 245 _mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter)
 246 {
 247     struct symbol_header *hdr;
 248
 249     if (iter->curr == NULL) {
 250         return 0;
 251     }
 252
 253     hdr = iter->curr->hdr;
 254     iter->curr = iter->curr->next_with_same_name;
 255
 256     while (iter->curr != NULL) {
 257         assert(iter->curr->hdr == hdr);
 258
 259         if ((iter->name_space == -1)
 260             || (iter->curr->name_space == iter->name_space)) {
 261             return 1;
 262         }
 263
 264         iter->curr = iter->curr->next_with_same_name;
 265     }
 266
 267     return 0;
 268 }
 269
 270
 271 /**
 272  * Determine the scope "distance" of a symbol from the current scope
 273  *
 274  * \return
 275  * A non-negative number for the number of scopes between the current scope
 276  * and the scope where a symbol was defined.  A value of zero means the current
 277  * scope.  A negative number if the symbol does not exist.
 278  */
 279 int
 280 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
 281                                 int name_space, const char *name)
 282 {
 283     struct symbol_header *const hdr = find_symbol(table, name);
 284     struct symbol *sym;
 285
 286     if (hdr != NULL) {
 287        for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 288           assert(sym->hdr == hdr);
 289
 290           if ((name_space == -1) || (sym->name_space == name_space)) {
 291              assert(sym->depth <= table->depth);
 292              return sym->depth - table->depth;
 293           }
 294        }
 295     }
 296
 297     return -1;
 298 }
 299
 300
 301 void *
 302 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
 303                                int name_space, const char *name)
 304 {
 305     struct symbol_header *const hdr = find_symbol(table, name);
 306
 307     if (hdr != NULL) {
 308         struct symbol *sym;
 309
 310
 311         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 312             assert(sym->hdr == hdr);
 313
 314             if ((name_space == -1) || (sym->name_space == name_space)) {
 315                 return sym->data;
 316             }
 317         }
 318     }
 319
 320     return NULL;
 321 }
 322
 323
 324 int
 325 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
 326                               int name_space, const char *name,
 327                               void *declaration)
 328 {
 329     struct symbol_header *hdr;
 330     struct symbol *sym;
 331
 332     check_symbol_table(table);
 333
 334     hdr = find_symbol(table, name);
 335
 336     check_symbol_table(table);
 337
 338     if (hdr == NULL) {
 339        hdr = calloc(1, sizeof(*hdr));
 340        hdr->name = strdup(name);
 341
 342        hash_table_insert(table->ht, hdr, hdr->name);
 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 == table->depth))
 359        return -1;
 360
 361     sym = calloc(1, sizeof(*sym));
 362     sym->next_with_same_name = hdr->symbols;
 363     sym->next_with_same_scope = table->current_scope->symbols;
 364     sym->hdr = hdr;
 365     sym->name_space = name_space;
 366     sym->data = declaration;
 367     sym->depth = table->depth;
 368
 369     assert(sym->hdr == hdr);
 370
 371     hdr->symbols = sym;
 372     table->current_scope->symbols = sym;
 373
 374     check_symbol_table(table);
 375     return 0;
 376 }
 377
 378
 379 int
 380 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
 381                                      int name_space, const char *name,
 382                                      void *declaration)
 383 {
 384     struct symbol_header *hdr;
 385     struct symbol *sym;
 386     struct symbol *curr;
 387     struct scope_level *top_scope;
 388
 389     check_symbol_table(table);
 390
 391     hdr = find_symbol(table, name);
 392
 393     check_symbol_table(table);
 394
 395     if (hdr == NULL) {
 396         hdr = calloc(1, sizeof(*hdr));
 397         hdr->name = strdup(name);
 398
 399         hash_table_insert(table->ht, hdr, hdr->name);
 400         hdr->next = table->hdr;
 401         table->hdr = hdr;
 402     }
 403
 404     check_symbol_table(table);
 405
 406     /* If the symbol already exists in this namespace at this scope, it cannot
 407      * be added to the table.
 408      */
 409     for (sym = hdr->symbols
 410          ; (sym != NULL) && (sym->name_space != name_space)
 411          ; sym = sym->next_with_same_name) {
 412        /* empty */
 413     }
 414
 415     if (sym && sym->depth == 0)
 416        return -1;
 417
 418     /* Find the top-level scope */
 419     for (top_scope = table->current_scope
 420          ; top_scope->next != NULL
 421          ; top_scope = top_scope->next) {
 422        /* empty */
 423     }
 424
 425     sym = calloc(1, sizeof(*sym));
 426     sym->next_with_same_scope = top_scope->symbols;
 427     sym->hdr = hdr;
 428     sym->name_space = name_space;
 429     sym->data = declaration;
 430
 431     assert(sym->hdr == hdr);
 432
 433     /* Since next_with_same_name is ordered by scope, we need to append the
 434      * new symbol to the _end_ of the list.
 435      */
 436     if (hdr->symbols == NULL) {
 437        hdr->symbols = sym;
 438     } else {
 439        for (curr = hdr->symbols
 440             ; curr->next_with_same_name != NULL
 441             ; curr = curr->next_with_same_name) {
 442           /* empty */
 443        }
 444        curr->next_with_same_name = sym;
 445     }
 446     top_scope->symbols = sym;
 447
 448     check_symbol_table(table);
 449     return 0;
 450 }
 451
 452
 453
 454 struct _mesa_symbol_table *
 455 _mesa_symbol_table_ctor(void)
 456 {
 457     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
 458
 459     if (table != NULL) {
 460        table->ht = hash_table_ctor(32, hash_table_string_hash,
 461                                    hash_table_string_compare);
 462
 463        _mesa_symbol_table_push_scope(table);
 464     }
 465
 466     return table;
 467 }
 468
 469
 470 void
 471 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
 472 {
 473    struct symbol_header *hdr;
 474    struct symbol_header *next;
 475
 476    while (table->current_scope != NULL) {
 477       _mesa_symbol_table_pop_scope(table);
 478    }
 479
 480    for (hdr = table->hdr; hdr != NULL; hdr = next) {
 481        next = hdr->next;
 482        free(hdr->name);
 483        free(hdr);
 484    }
 485
 486    hash_table_dtor(table->ht);
 487    free(table);
 488 }