source: trunk/third/libIDL/ns.c @ 18251

Revision 18251, 14.3 KB checked in by ghudson, 22 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r18250, which included commits to RCS files with non-trunk default branches.
Line 
1/***************************************************************************
2
3    ns.c (libIDL namespace functions)
4
5    Copyright (C) 1998, 1999 Andrew T. Veliath
6
7    This library is free software; you can redistribute it and/or
8    modify it under the terms of the GNU Library General Public
9    License as published by the Free Software Foundation; either
10    version 2 of the License, or (at your option) any later version.
11
12    This library is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15    Library General Public License for more details.
16
17    You should have received a copy of the GNU Library General Public
18    License along with this library; if not, write to the Free
19    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20
21    $Id: ns.c,v 1.1.1.1 2002-12-26 17:11:03 ghudson Exp $
22
23***************************************************************************/
24#include <assert.h>
25#include <stdarg.h>
26#include <stdio.h>
27#include <stdlib.h>
28#include <ctype.h>
29#include <string.h>
30#include <errno.h>
31#include "rename.h"
32#include "util.h"
33
34static int is_inheritance_conflict (IDL_tree p);
35
36IDL_ns IDL_ns_new (void)
37{
38        IDL_ns ns;
39
40        ns = g_new0 (struct _IDL_ns, 1);
41        if (ns == NULL) {
42                yyerror ("IDL_ns_new: memory exhausted");
43                return NULL;
44        }
45
46        IDL_NS (ns).global = IDL_gentree_new (IDL_ident_hash,
47                                              IDL_ident_equal,
48                                              IDL_ident_new (""));
49        IDL_NS (ns).file =  IDL_NS (ns).current = IDL_NS (ns).global;
50        IDL_NS (ns).inhibits = g_hash_table_new (g_direct_hash, g_direct_equal);
51        IDL_NS (ns).filename_hash = g_hash_table_new (g_str_hash, g_str_equal);
52
53        return ns;
54}
55
56static void filename_hash_free (char *filename, IDL_fileinfo *fi)
57{
58        g_free (fi->name);
59        g_free (fi);
60}
61
62void IDL_ns_free (IDL_ns ns)
63{
64        assert (ns != NULL);
65
66        g_hash_table_foreach (IDL_NS (ns).inhibits, (GHFunc)IDL_tree_free, NULL);
67        g_hash_table_destroy (IDL_NS (ns).inhibits);
68        g_hash_table_foreach (IDL_NS (ns).filename_hash, (GHFunc) filename_hash_free, NULL);
69        g_hash_table_destroy (IDL_NS (ns).filename_hash);
70        IDL_tree_free (IDL_NS (ns).global);
71
72        g_free (ns);
73}
74
75#define IDL_NS_ASSERTS          do {                                            \
76        assert (ns != NULL);                                                    \
77        if (__IDL_is_parsing) {                                                 \
78                assert (IDL_NS (ns).global != NULL);                            \
79                assert (IDL_NS (ns).file != NULL);                              \
80                assert (IDL_NS (ns).current != NULL);                           \
81                assert (IDL_NODE_TYPE (IDL_NS (ns).global) == IDLN_GENTREE);    \
82                assert (IDL_NODE_TYPE (IDL_NS (ns).file) == IDLN_GENTREE);      \
83                assert (IDL_NODE_TYPE (IDL_NS (ns).current) == IDLN_GENTREE);   \
84        }                                                                       \
85} while (0)
86
87int IDL_ns_prefix (IDL_ns ns, const char *s)
88{
89        char *r;
90        int l;
91
92        IDL_NS_ASSERTS;
93
94        if (s == NULL)
95                return FALSE;
96
97        if (*s == '"')
98                r = g_strdup (s + 1);
99        else
100                r = g_strdup (s);
101
102        l = strlen (r);
103        if (l && r[l - 1] == '"')
104                r[l - 1] = 0;
105
106        if (IDL_GENTREE (IDL_NS (ns).current)._cur_prefix)
107                g_free (IDL_GENTREE (IDL_NS (ns).current)._cur_prefix);
108
109        IDL_GENTREE (IDL_NS (ns).current)._cur_prefix = r;
110
111        return TRUE;
112}
113
114IDL_tree IDL_ns_resolve_this_scope_ident (IDL_ns ns, IDL_tree scope, IDL_tree ident)
115{
116        IDL_tree p, q;
117
118        IDL_NS_ASSERTS;
119
120        p = scope;
121
122        while (p != NULL) {
123                q = IDL_ns_lookup_this_scope (ns, p, ident, NULL);
124                if (q != NULL)
125                        return q;
126                p = IDL_NODE_UP (p);
127        }
128
129        return p;
130}
131
132IDL_tree IDL_ns_resolve_ident (IDL_ns ns, IDL_tree ident)
133{
134        return IDL_ns_resolve_this_scope_ident (ns, IDL_NS (ns).current, ident);
135}
136
137IDL_tree IDL_ns_lookup_this_scope (IDL_ns ns, IDL_tree scope, IDL_tree ident, gboolean *conflict)
138{
139        IDL_tree p, q;
140
141        IDL_NS_ASSERTS;
142
143        if (conflict)
144                *conflict = TRUE;
145
146        if (scope == NULL)
147                return NULL;
148
149        assert (IDL_NODE_TYPE (scope) == IDLN_GENTREE);
150
151        /* Search this namespace */
152        if (g_hash_table_lookup_extended (
153                IDL_GENTREE (scope).children, ident, NULL, (gpointer)&p)) {
154                assert (IDL_GENTREE (p).data != NULL);
155                assert (IDL_NODE_TYPE (IDL_GENTREE (p).data) == IDLN_IDENT);
156                return p;
157        }
158
159        /* If there are inherited namespaces, look in those before giving up */
160        q = IDL_GENTREE (scope)._import;
161        if (!q)
162                return NULL;
163
164        assert (IDL_NODE_TYPE (q) == IDLN_LIST);
165        for (; q != NULL; q = IDL_LIST (q).next) {
166                IDL_tree r;
167
168                assert (IDL_LIST (q).data != NULL);
169                assert (IDL_NODE_TYPE (IDL_LIST (q).data) == IDLN_IDENT);
170                assert (IDL_IDENT_TO_NS (IDL_LIST (q).data) != NULL);
171                assert (IDL_NODE_TYPE (IDL_IDENT_TO_NS (IDL_LIST (q).data)) == IDLN_GENTREE);
172
173                /* Search imported namespace scope q */
174                if (g_hash_table_lookup_extended (
175                        IDL_GENTREE (IDL_IDENT_TO_NS (IDL_LIST (q).data)).children,
176                        ident, NULL, (gpointer)&p)) {
177                        assert (IDL_GENTREE (p).data != NULL);
178                        assert (IDL_NODE_TYPE (IDL_GENTREE (p).data) == IDLN_IDENT);
179
180                        /* This needs more work, it won't do full ambiguity detection */
181                        if (conflict && !is_inheritance_conflict (p))
182                                *conflict = FALSE;
183
184                        return p;
185                }
186
187                /* Search up one level */
188                if (IDL_NODE_TYPE (IDL_NODE_UP (IDL_LIST (q).data)) == IDLN_INTERFACE &&
189                    (r = IDL_ns_lookup_this_scope (
190                            ns, IDL_IDENT_TO_NS (IDL_LIST (q).data), ident, conflict)))
191                        return r;
192        }
193
194        return NULL;
195}
196
197IDL_tree IDL_ns_lookup_cur_scope (IDL_ns ns, IDL_tree ident, gboolean *conflict)
198{
199        return IDL_ns_lookup_this_scope (ns, IDL_NS (ns).current, ident, conflict);
200}
201
202IDL_tree IDL_ns_place_new (IDL_ns ns, IDL_tree ident)
203{
204        IDL_tree p, up_save;
205        gboolean does_conflict;
206
207        IDL_NS_ASSERTS;
208
209        p = IDL_ns_lookup_cur_scope (ns, ident, &does_conflict);
210        if (p != NULL && does_conflict)
211                return NULL;
212
213        /* The namespace tree is separate from the primary parse tree,
214           so keep the primary tree node's parent the same */
215        up_save = IDL_NODE_UP (ident);
216        p = IDL_gentree_chain_child (IDL_NS (ns).current, ident);
217        IDL_NODE_UP (ident) = up_save;
218
219        if (p == NULL)
220                return NULL;
221
222        assert (IDL_NODE_TYPE (p) == IDLN_GENTREE);
223
224        IDL_IDENT_TO_NS (ident) = p;
225
226        assert (IDL_NODE_UP (IDL_IDENT_TO_NS (ident)) == IDL_NS (ns).current);
227
228        /* Generate default repository ID */
229        IDL_IDENT_REPO_ID (ident) =
230                IDL_ns_ident_make_repo_id (__IDL_root_ns, p, NULL, NULL, NULL);
231
232        return p;
233}
234
235void IDL_ns_push_scope (IDL_ns ns, IDL_tree ns_ident)
236{
237        IDL_NS_ASSERTS;
238
239        assert (IDL_NODE_TYPE (ns_ident) == IDLN_GENTREE);
240        assert (IDL_NODE_TYPE (IDL_GENTREE (ns_ident).data) == IDLN_IDENT);
241        assert (IDL_NS (ns).current == IDL_NODE_UP (ns_ident));
242
243        IDL_NS (ns).current = ns_ident;
244}
245
246void IDL_ns_pop_scope (IDL_ns ns)
247{
248        IDL_NS_ASSERTS;
249
250        if (IDL_NODE_UP (IDL_NS (ns).current) != NULL)
251                IDL_NS (ns).current = IDL_NODE_UP (IDL_NS (ns).current);
252}
253
254IDL_tree IDL_ns_qualified_ident_new (IDL_tree nsid)
255{
256        IDL_tree l = NULL, item;
257
258        while (nsid != NULL) {
259                if (IDL_GENTREE (nsid).data == NULL) {
260                        nsid = IDL_NODE_UP (nsid);
261                        continue;
262                }
263                assert (IDL_GENTREE (nsid).data != NULL);
264                assert (IDL_NODE_TYPE (IDL_GENTREE (nsid).data) == IDLN_IDENT);
265                item = IDL_list_new (IDL_ident_new (
266                        g_strdup (IDL_IDENT (IDL_GENTREE (nsid).data).str)));
267                l = IDL_list_concat (item, l);
268                nsid = IDL_NODE_UP (nsid);
269        }
270
271        return l;
272}
273
274gchar *IDL_ns_ident_to_qstring (IDL_tree ns_ident, const char *join, int levels)
275{
276        IDL_tree l, q;
277        int len, joinlen;
278        char *s;
279        int count = 0, start_level;
280
281        if (levels < 0 || levels > 64)
282                return NULL;
283
284        if (ns_ident == NULL)
285                return NULL;
286
287        if (IDL_NODE_TYPE (ns_ident) == IDLN_IDENT)
288                ns_ident = IDL_IDENT_TO_NS (ns_ident);
289
290        assert (IDL_NODE_TYPE (ns_ident) == IDLN_GENTREE);
291
292        l = IDL_ns_qualified_ident_new (ns_ident);
293
294        if (l == NULL)
295                return NULL;
296
297        if (join == NULL)
298                join = "";
299
300        joinlen = strlen (join);
301        for (len = 0, q = l; q != NULL; q = IDL_LIST (q).next) {
302                IDL_tree i = IDL_LIST (q).data;
303                assert (IDL_NODE_TYPE (q) == IDLN_LIST);
304                assert (IDL_NODE_TYPE (i) == IDLN_IDENT);
305                if (IDL_IDENT (i).str != NULL)
306                        len += strlen (IDL_IDENT (i).str) + joinlen;
307                ++count;
308        }
309
310        if (levels == 0)
311                start_level = 0;
312        else
313                start_level = count - levels;
314
315        assert (start_level >= 0 && start_level < count);
316
317        s = g_malloc (len + 1);
318        if (s == NULL) {
319                IDL_tree_free (l);
320                return NULL;
321        }
322        s[0] = '\0';
323        for (q = l; q != NULL; q = IDL_LIST (q).next) {
324                IDL_tree i = IDL_LIST (q).data;
325                if (start_level > 0) {
326                        --start_level;
327                        continue;
328                }
329                if (s[0] != '\0')
330                        strcat (s, join);
331                strcat (s, IDL_IDENT (i).str);
332        }
333
334        IDL_tree_free (l);
335
336        return s;
337}
338
339int IDL_ns_scope_levels_from_here (IDL_ns ns, IDL_tree ident, IDL_tree parent)
340{
341        IDL_tree p, scope_here, scope_ident;
342        int levels;
343
344        g_return_val_if_fail (ns != NULL, 1);
345        g_return_val_if_fail (ident != NULL, 1);
346
347        while (parent && !IDL_NODE_IS_SCOPED (parent))
348                parent = IDL_NODE_UP (parent);
349
350        if (parent == NULL)
351                return 1;
352
353        if ((scope_here = IDL_tree_get_scope (parent)) == NULL ||
354            (scope_ident = IDL_tree_get_scope (ident)) == NULL)
355                return 1;
356
357        assert (IDL_NODE_TYPE (scope_here) == IDLN_GENTREE);
358        assert (IDL_NODE_TYPE (scope_ident) == IDLN_GENTREE);
359
360        for (levels = 1; scope_ident;
361             ++levels, scope_ident = IDL_NODE_UP (scope_ident)) {
362                p = IDL_ns_resolve_this_scope_ident (
363                        ns, scope_here, IDL_GENTREE (scope_ident).data);
364                if (p == scope_ident)
365                        return levels;
366        }
367
368        return 1;
369}
370
371/* If insertion was made, return true, else there was a collision */
372static gboolean heap_insert_ident (IDL_tree interface_ident, GTree *heap, IDL_tree any)
373{
374        IDL_tree p;
375
376        assert (any != NULL);
377        assert (heap != NULL);
378
379        if ((p = g_tree_lookup (heap, any))) {
380                char *newi;
381                char *i1, *i2;
382                char *what1 = "identifier", *what2 = what1;
383                char *who1, *who2;
384                IDL_tree q;
385
386                assert (IDL_NODE_TYPE (p) == IDLN_IDENT);
387
388                newi = IDL_ns_ident_to_qstring (IDL_IDENT_TO_NS (interface_ident), "::", 0);
389                i1 = IDL_ns_ident_to_qstring (IDL_IDENT_TO_NS (p), "::", 0);
390                i2 = IDL_ns_ident_to_qstring (IDL_IDENT_TO_NS (any), "::", 0);
391
392                q = p;
393                while (q && (IDL_NODE_TYPE (q) == IDLN_IDENT || IDL_NODE_TYPE (q) == IDLN_LIST))
394                        q = IDL_NODE_UP (q);
395                assert (q != NULL);
396                IDL_tree_get_node_info (q, &what1, &who1);
397
398                q = any;
399                while (q && (IDL_NODE_TYPE (q) == IDLN_IDENT || IDL_NODE_TYPE (q) == IDLN_LIST))
400                        q = IDL_NODE_UP (q);
401                assert (q != NULL);
402                IDL_tree_get_node_info (q, &what2, &who2);
403
404                yyerrorv ("Ambiguous inheritance in interface `%s' from %s `%s' and %s `%s'",
405                          newi, what1, i1, what2, i2);
406                IDL_tree_error (p, "%s `%s' conflicts with", what1, i1);
407                IDL_tree_error (any, "%s `%s'", what2, i2);
408
409                g_free (newi); g_free (i1); g_free (i2);
410
411                return FALSE;
412        }
413
414        g_tree_insert (heap, any, any);
415
416        return TRUE;
417}
418
419static int is_visited_interface (GHashTable *visited_interfaces, IDL_tree scope)
420{
421        assert (scope != NULL);
422        assert (IDL_NODE_TYPE (scope) == IDLN_GENTREE);
423        /* If already visited, do not visit again */
424        return g_hash_table_lookup_extended (visited_interfaces, scope, NULL, NULL);
425}
426
427static void mark_visited_interface (GHashTable *visited_interfaces, IDL_tree scope)
428{
429        assert (scope != NULL);
430        assert (IDL_NODE_TYPE (scope) == IDLN_GENTREE);
431        g_hash_table_insert (visited_interfaces, scope, scope);
432}
433
434static int is_inheritance_conflict (IDL_tree p)
435{
436        if (IDL_GENTREE (p).data == NULL)
437                return FALSE;
438
439        assert (IDL_NODE_TYPE (IDL_GENTREE (p).data) == IDLN_IDENT);
440
441        if (IDL_NODE_UP (IDL_GENTREE (p).data) == NULL)
442                return FALSE;
443
444        if (!(IDL_NODE_TYPE (IDL_NODE_UP (IDL_GENTREE (p).data)) == IDLN_OP_DCL ||
445              (IDL_NODE_UP (IDL_GENTREE (p).data) &&
446               IDL_NODE_TYPE (IDL_NODE_UP (IDL_NODE_UP (IDL_GENTREE (p).data))) == IDLN_ATTR_DCL)))
447                return FALSE;
448
449        return TRUE;
450}
451
452typedef struct {
453        IDL_tree interface_ident;
454        GTree *ident_heap;
455        int insert_conflict;
456} InsertHeapData;
457
458static void insert_heap_cb (IDL_tree ident, IDL_tree p, InsertHeapData *data)
459{
460        if (!is_inheritance_conflict (p))
461                return;
462
463        if (!heap_insert_ident (
464                data->interface_ident, data->ident_heap, IDL_GENTREE (p).data))
465                data->insert_conflict = 1;
466}
467
468/* Return true if adds went okay */
469static int IDL_ns_load_idents_to_tables (IDL_tree interface_ident, IDL_tree ident_scope,
470                                         GTree *ident_heap, GHashTable *visited_interfaces)
471{
472        IDL_tree q, scope;
473        InsertHeapData data;
474
475        assert (ident_scope != NULL);
476        assert (IDL_NODE_TYPE (ident_scope) == IDLN_IDENT);
477
478        scope = IDL_IDENT_TO_NS (ident_scope);
479
480        if (!scope)
481                return TRUE;
482
483        assert (IDL_NODE_TYPE (scope) == IDLN_GENTREE);
484        assert (IDL_GENTREE (scope).data != NULL);
485        assert (IDL_NODE_TYPE (IDL_GENTREE (scope).data) == IDLN_IDENT);
486        assert (IDL_NODE_UP (IDL_GENTREE (scope).data) != NULL);
487        assert (IDL_NODE_TYPE (IDL_NODE_UP (IDL_GENTREE (scope).data)) == IDLN_INTERFACE);
488
489        if (is_visited_interface (visited_interfaces, scope))
490                return TRUE;
491
492        /* Search this namespace */
493        data.interface_ident = interface_ident;
494        data.ident_heap = ident_heap;
495        data.insert_conflict = 0;
496        g_hash_table_foreach (IDL_GENTREE (scope).children, (GHFunc)insert_heap_cb, &data);
497
498        /* If there are inherited namespaces, look in those before giving up */
499        q = IDL_GENTREE (scope)._import;
500        if (!q)
501                data.insert_conflict = 0;
502        else
503                assert (IDL_NODE_TYPE (q) == IDLN_LIST);
504
505        /* Add inherited namespace identifiers into heap */
506        for (; q != NULL; q = IDL_LIST (q).next) {
507                int r;
508
509                assert (IDL_LIST (q).data != NULL);
510                assert (IDL_NODE_TYPE (IDL_LIST (q).data) == IDLN_IDENT);
511                assert (IDL_IDENT_TO_NS (IDL_LIST (q).data) != NULL);
512                assert (IDL_NODE_TYPE (IDL_IDENT_TO_NS (IDL_LIST (q).data)) == IDLN_GENTREE);
513                assert (IDL_NODE_TYPE (IDL_NODE_UP (IDL_LIST (q).data)) == IDLN_INTERFACE);
514
515                if (!(r = IDL_ns_load_idents_to_tables (interface_ident, IDL_LIST (q).data,
516                                                        ident_heap, visited_interfaces)))
517                        data.insert_conflict = 1;
518        }
519
520        mark_visited_interface (visited_interfaces, scope);
521
522        return data.insert_conflict == 0;
523}
524
525int IDL_ns_check_for_ambiguous_inheritance (IDL_tree interface_ident, IDL_tree p)
526{
527        /* We use a sorted heap to check for namespace collisions,
528           since we must do case-insensitive collision checks.
529           visited_interfaces is a hash of visited interface nodes, so
530           we only visit common ancestors once. */
531        GTree *ident_heap;
532        GHashTable *visited_interfaces;
533        int is_ambiguous = 0;
534
535        if (!p)
536                return 0;
537
538        ident_heap = g_tree_new (IDL_ident_cmp);
539        visited_interfaces = g_hash_table_new (g_direct_hash, g_direct_equal);
540
541        assert (IDL_NODE_TYPE (p) == IDLN_LIST);
542        for (; p;  p = IDL_LIST (p).next) {
543                if (!IDL_ns_load_idents_to_tables (interface_ident, IDL_LIST (p).data,
544                                                   ident_heap, visited_interfaces))
545                        is_ambiguous = 1;
546        }
547
548        g_tree_destroy (ident_heap);
549        g_hash_table_destroy (visited_interfaces);
550
551        return is_ambiguous;
552}
553
554/*
555 * Local variables:
556 * mode: C
557 * c-basic-offset: 8
558 * tab-width: 8
559 * indent-tabs-mode: t
560 * End:
561 */
Note: See TracBrowser for help on using the repository browser.