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
28struct symbol {
29   /** Symbol name. */
30   char *name;
31
32    /**
33     * Link to the next symbol in the table with the same name
34     *
35     * The linked list of symbols with the same name is ordered by scope
36     * from inner-most to outer-most.
37     */
38    struct symbol *next_with_same_name;
39
40    /**
41     * Link to the next symbol in the table with the same scope
42     *
43     * The linked list of symbols with the same scope is unordered.  Symbols
44     * in this list my have unique names.
45     */
46    struct symbol *next_with_same_scope;
47
48    /** Scope depth where this symbol was defined. */
49    unsigned depth;
50
51    /**
52     * Arbitrary user supplied data.
53     */
54    void *data;
55};
56
57
58/**
59 * Element of the scope stack.
60 */
61struct scope_level {
62    /** Link to next (inner) scope level. */
63    struct scope_level *next;
64
65    /** Linked list of symbols with the same scope. */
66    struct symbol *symbols;
67};
68
69
70/**
71 *
72 */
73struct _mesa_symbol_table {
74    /** Hash table containing all symbols in the symbol table. */
75    struct hash_table *ht;
76
77    /** Top of scope stack. */
78    struct scope_level *current_scope;
79
80    /** Current scope depth. */
81    unsigned depth;
82};
83
84void
85_mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
86{
87    struct scope_level *const scope = table->current_scope;
88    struct symbol *sym = scope->symbols;
89
90    table->current_scope = scope->next;
91    table->depth--;
92
93    free(scope);
94
95    while (sym != NULL) {
96        struct symbol *const next = sym->next_with_same_scope;
97        struct hash_entry *hte = _mesa_hash_table_search(table->ht,
98                                                         sym->name);
99        if (sym->next_with_same_name) {
100           /* If there is a symbol with this name in an outer scope update
101            * the hash table to point to it.
102            */
103           hte->key = sym->next_with_same_name->name;
104           hte->data = sym->next_with_same_name;
105        } else {
106           _mesa_hash_table_remove(table->ht, hte);
107           free(sym->name);
108        }
109
110        free(sym);
111        sym = next;
112    }
113}
114
115
116void
117_mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
118{
119    struct scope_level *const scope = calloc(1, sizeof(*scope));
120    if (scope == NULL) {
121       _mesa_error_no_memory(__func__);
122       return;
123    }
124
125    scope->next = table->current_scope;
126    table->current_scope = scope;
127    table->depth++;
128}
129
130
131static struct symbol *
132find_symbol(struct _mesa_symbol_table *table, const char *name)
133{
134   struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
135   return entry ? (struct symbol *) entry->data : NULL;
136}
137
138
139/**
140 * Determine the scope "distance" of a symbol from the current scope
141 *
142 * \return
143 * A non-negative number for the number of scopes between the current scope
144 * and the scope where a symbol was defined.  A value of zero means the current
145 * scope.  A negative number if the symbol does not exist.
146 */
147int
148_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
149                                const char *name)
150{
151   struct symbol *const sym = find_symbol(table, name);
152
153   if (sym) {
154      assert(sym->depth <= table->depth);
155      return sym->depth - table->depth;
156   }
157
158   return -1;
159}
160
161
162void *
163_mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
164                               const char *name)
165{
166   struct symbol *const sym = find_symbol(table, name);
167   if (sym)
168      return sym->data;
169
170   return NULL;
171}
172
173
174int
175_mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
176                              const char *name, void *declaration)
177{
178   struct symbol *new_sym;
179   struct symbol *sym = find_symbol(table, name);
180
181   if (sym && sym->depth == table->depth)
182      return -1;
183
184   new_sym = calloc(1, sizeof(*sym));
185   if (new_sym == NULL) {
186      _mesa_error_no_memory(__func__);
187      return -1;
188   }
189
190   if (sym) {
191      /* Store link to symbol in outer scope with the same name */
192      new_sym->next_with_same_name = sym;
193      new_sym->name = sym->name;
194   } else {
195      new_sym->name = strdup(name);
196      if (new_sym->name == NULL) {
197         free(new_sym);
198         _mesa_error_no_memory(__func__);
199         return -1;
200      }
201   }
202
203   new_sym->next_with_same_scope = table->current_scope->symbols;
204   new_sym->data = declaration;
205   new_sym->depth = table->depth;
206
207   table->current_scope->symbols = new_sym;
208
209   _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
210
211   return 0;
212}
213
214int
215_mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
216                                  const char *name,
217                                  void *declaration)
218{
219    struct symbol *sym = find_symbol(table, name);
220
221    /* If the symbol doesn't exist, it cannot be replaced. */
222    if (sym == NULL)
223       return -1;
224
225    sym->data = declaration;
226    return 0;
227}
228
229int
230_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
231                                     const char *name, void *declaration)
232{
233   struct scope_level *top_scope;
234   struct symbol *inner_sym = NULL;
235   struct symbol *sym = find_symbol(table, name);
236
237   while (sym) {
238      if (sym->depth == 0)
239         return -1;
240
241      inner_sym = sym;
242
243      /* Get symbol from the outer scope with the same name */
244      sym = sym->next_with_same_name;
245   }
246
247   /* Find the top-level scope */
248   for (top_scope = table->current_scope; top_scope->next != NULL;
249        top_scope = top_scope->next) {
250      /* empty */
251   }
252
253   sym = calloc(1, sizeof(*sym));
254   if (sym == NULL) {
255      _mesa_error_no_memory(__func__);
256      return -1;
257   }
258
259   if (inner_sym) {
260      /* In case we add the global out of order store a link to the global
261       * symbol in global.
262       */
263      inner_sym->next_with_same_name = sym;
264
265      sym->name = inner_sym->name;
266   } else {
267      sym->name = strdup(name);
268      if (sym->name == NULL) {
269         free(sym);
270         _mesa_error_no_memory(__func__);
271         return -1;
272      }
273   }
274
275   sym->next_with_same_scope = top_scope->symbols;
276   sym->data = declaration;
277
278   top_scope->symbols = sym;
279
280   _mesa_hash_table_insert(table->ht, sym->name, sym);
281
282   return 0;
283}
284
285
286
287struct _mesa_symbol_table *
288_mesa_symbol_table_ctor(void)
289{
290    struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
291
292    if (table != NULL) {
293       table->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
294                                           _mesa_key_string_equal);
295
296       _mesa_symbol_table_push_scope(table);
297    }
298
299    return table;
300}
301
302
303void
304_mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
305{
306   while (table->current_scope != NULL) {
307      _mesa_symbol_table_pop_scope(table);
308   }
309
310   _mesa_hash_table_destroy(table->ht, NULL);
311   free(table);
312}
313