1 /*****************************************************************************/
5 /* Symbol table management for the cc65 C compiler */
9 /* (C) 2000-2003 Ullrich von Bassewitz */
10 /* Römerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
15 /* This software is provided 'as-is', without any expressed or implied */
16 /* warranty. In no event will the authors be held liable for any damages */
17 /* arising from the use of this software. */
19 /* Permission is granted to anyone to use this software for any purpose, */
20 /* including commercial applications, and to alter it and redistribute it */
21 /* freely, subject to the following restrictions: */
23 /* 1. The origin of this software must not be misrepresented; you must not */
24 /* claim that you wrote the original software. If you use this software */
25 /* in a product, an acknowledgment in the product documentation would be */
26 /* appreciated but is not required. */
27 /* 2. Altered source versions must be plainly marked as such, and must not */
28 /* be misrepresented as being the original software. */
29 /* 3. This notice may not be removed or altered from any source */
32 /*****************************************************************************/
43 #include "debugflag.h"
62 /*****************************************************************************/
64 /*****************************************************************************/
68 /* An empty symbol table */
69 SymTable EmptySymTab = {
78 /* Symbol table sizes */
79 #define SYMTAB_SIZE_GLOBAL 211U
80 #define SYMTAB_SIZE_FUNCTION 29U
81 #define SYMTAB_SIZE_BLOCK 13U
82 #define SYMTAB_SIZE_STRUCT 19U
83 #define SYMTAB_SIZE_LABEL 7U
85 /* The current and root symbol tables */
86 static unsigned LexicalLevel = 0; /* For safety checks */
87 static SymTable* SymTab0 = 0;
88 static SymTable* SymTab = 0;
89 static SymTable* TagTab0 = 0;
90 static SymTable* TagTab = 0;
91 static SymTable* LabelTab = 0;
95 /*****************************************************************************/
97 /*****************************************************************************/
101 static SymTable* NewSymTable (unsigned Size)
102 /* Create and return a symbol table for the given lexical level */
106 /* Allocate memory for the table */
107 SymTable* S = xmalloc (sizeof (SymTable) + (Size-1) * sizeof (SymEntry*));
109 /* Initialize the symbol table structure */
115 for (I = 0; I < Size; ++I) {
119 /* Return the symbol table */
125 static void FreeSymTable (SymTable* S)
126 /* Free the given symbo table including all symbols */
128 /* Free all symbols */
129 SymEntry* Sym = S->SymHead;
131 SymEntry* NextSym = Sym->NextSym;
136 /* Free the table itself */
142 /*****************************************************************************/
143 /* Check symbols in a table */
144 /*****************************************************************************/
148 static void CheckSymTable (SymTable* Tab)
149 /* Check a symbol table for open references, unused symbols ... */
151 SymEntry* Entry = Tab->SymHead;
154 /* Get the storage flags for tne entry */
155 unsigned Flags = Entry->Flags;
157 /* Ignore typedef entries */
158 if ((Flags & SC_TYPEDEF) != SC_TYPEDEF) {
160 /* Check if the symbol is one with storage, and it if it was
161 * defined but not used.
163 if (((Flags & SC_AUTO) || (Flags & SC_STATIC)) && (Flags & SC_EXTERN) == 0) {
164 if (SymIsDef (Entry) && !SymIsRef (Entry)) {
165 if (Flags & SC_PARAM) {
166 Warning ("Parameter `%s' is never used", Entry->Name);
168 Warning ("`%s' is defined but never used", Entry->Name);
173 /* If the entry is a label, check if it was defined in the function */
174 if (Flags & SC_LABEL) {
175 if (!SymIsDef (Entry)) {
176 /* Undefined label */
177 Error ("Undefined label: `%s'", Entry->Name);
178 } else if (!SymIsRef (Entry)) {
179 /* Defined but not used */
180 Warning ("`%s' is defined but never used", Entry->Name);
187 Entry = Entry->NextSym;
193 /*****************************************************************************/
194 /* Handling of lexical levels */
195 /*****************************************************************************/
199 unsigned GetLexicalLevel (void)
200 /* Return the current lexical level */
207 void EnterGlobalLevel (void)
208 /* Enter the program global lexical level */
211 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
213 /* Create and assign the symbol table */
214 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
216 /* Create and assign the tag table */
217 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
222 void LeaveGlobalLevel (void)
223 /* Leave the program global lexical level */
226 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
228 /* Check the tables */
229 CheckSymTable (SymTab0);
231 /* Dump the tables if requested */
233 PrintSymTable (SymTab0, stdout, "Global symbol table");
234 PrintSymTable (TagTab0, stdout, "Global tag table");
237 /* Don't delete the symbol and struct tables! */
244 void EnterFunctionLevel (void)
245 /* Enter function lexical level */
249 /* New lexical level */
252 /* Get a new symbol table and make it current */
253 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
257 /* Get a new tag table and make it current */
258 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
262 /* Create and assign a new label table */
263 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
268 void RememberFunctionLevel (struct FuncDesc* F)
269 /* Remember the symbol tables for the level and leave the level without checks */
271 /* Leave the lexical level */
274 /* Remember the tables */
278 /* Don't delete the tables */
279 SymTab = SymTab->PrevTab;
280 TagTab = TagTab->PrevTab;
285 void ReenterFunctionLevel (struct FuncDesc* F)
286 /* Reenter the function lexical level using the existing tables from F */
288 /* New lexical level */
291 /* Make the tables current again */
292 F->SymTab->PrevTab = SymTab;
295 F->TagTab->PrevTab = TagTab;
298 /* Create and assign a new label table */
299 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
304 void LeaveFunctionLevel (void)
305 /* Leave function lexical level */
307 /* Leave the lexical level */
310 /* Check the tables */
311 CheckSymTable (SymTab);
312 CheckSymTable (LabelTab);
314 /* Drop the label table if it is empty */
315 if (LabelTab->SymCount == 0) {
316 FreeSymTable (LabelTab);
319 /* Don't delete the tables */
320 SymTab = SymTab->PrevTab;
321 TagTab = TagTab->PrevTab;
327 void EnterBlockLevel (void)
328 /* Enter a nested block in a function */
332 /* New lexical level */
335 /* Get a new symbol table and make it current */
336 S = NewSymTable (SYMTAB_SIZE_BLOCK);
340 /* Get a new tag table and make it current */
341 S = NewSymTable (SYMTAB_SIZE_BLOCK);
348 void LeaveBlockLevel (void)
349 /* Leave a nested block in a function */
351 /* Leave the lexical level */
354 /* Check the tables */
355 CheckSymTable (SymTab);
357 /* Don't delete the tables */
358 SymTab = SymTab->PrevTab;
359 TagTab = TagTab->PrevTab;
364 void EnterStructLevel (void)
365 /* Enter a nested block for a struct definition */
369 /* Get a new symbol table and make it current. Note: Structs and enums
370 * nested in struct scope are NOT local to the struct but visible in the
371 * outside scope. So we will NOT create a new struct or enum table.
373 S = NewSymTable (SYMTAB_SIZE_BLOCK);
380 void LeaveStructLevel (void)
381 /* Leave a nested block for a struct definition */
383 /* Don't delete the table */
384 SymTab = SymTab->PrevTab;
389 /*****************************************************************************/
391 /*****************************************************************************/
395 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
396 /* Search for an entry in one table */
398 /* Get the start of the hash chain */
399 SymEntry* E = T->Tab [Hash % T->Size];
401 /* Compare the name */
402 if (strcmp (E->Name, Name) == 0) {
406 /* Not found, next entry in hash chain */
416 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
417 /* Find the symbol with the given name in the table tree that starts with T */
419 /* Get the hash over the name */
420 unsigned Hash = HashStr (Name);
422 /* Check all symbol tables for the symbol */
424 /* Try to find the symbol in this table */
425 SymEntry* E = FindSymInTable (Tab, Name, Hash);
427 /* Bail out if we found it */
432 /* Repeat the search in the next higher lexical level */
442 SymEntry* FindSym (const char* Name)
443 /* Find the symbol with the given name */
445 return FindSymInTree (SymTab, Name);
450 SymEntry* FindGlobalSym (const char* Name)
451 /* Find the symbol with the given name in the global symbol table only */
453 return FindSymInTable (SymTab0, Name, HashStr (Name));
458 SymEntry* FindLocalSym (const char* Name)
459 /* Find the symbol with the given name in the current symbol table only */
461 return FindSymInTable (SymTab, Name, HashStr (Name));
466 SymEntry* FindTagSym (const char* Name)
467 /* Find the symbol with the given name in the tag table */
469 return FindSymInTree (TagTab, Name);
474 SymEntry* FindStructField (const type* Type, const char* Name)
475 /* Find a struct field in the fields list */
479 /* The given type may actually be a pointer to struct */
480 if (Type[0] == T_PTR) {
484 /* Non-structs do not have any struct fields... */
485 if (IsClassStruct (Type)) {
489 /* Get a pointer to the struct/union type */
490 const SymEntry* Struct = (const SymEntry*) Decode (Type+1);
493 /* Get the field symbol table from the struct entry.
494 * Beware: The table may not exist.
496 Tab = Struct->V.S.SymTab;
498 /* Now search in the struct symbol table */
500 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
509 /*****************************************************************************/
510 /* Add stuff to the symbol table */
511 /*****************************************************************************/
515 static void AddSymEntry (SymTable* T, SymEntry* S)
516 /* Add a symbol to a symbol table */
518 /* Get the hash value for the name */
519 unsigned Hash = HashStr (S->Name) % T->Size;
521 /* Insert the symbol into the list of all symbols in this level */
523 T->SymTail->NextSym = S;
525 S->PrevSym = T->SymTail;
527 if (T->SymHead == 0) {
533 /* Insert the symbol into the hash chain */
534 S->NextHash = T->Tab[Hash];
537 /* Tell the symbol in which table it is */
543 SymEntry* AddStructSym (const char* Name, unsigned Size, SymTable* Tab)
544 /* Add a struct/union entry and return it */
546 /* Do we have an entry with this name already? */
547 SymEntry* Entry = FindSymInTable (TagTab, Name, HashStr (Name));
550 /* We do have an entry. This may be a forward, so check it. */
551 if ((Entry->Flags & SC_STRUCT) == 0) {
552 /* Existing symbol is not a struct */
553 Error ("Symbol `%s' is already different kind", Name);
554 } else if (Size > 0 && Entry->V.S.Size > 0) {
555 /* Both structs are definitions. */
556 Error ("Multiple definition for `%s'", Name);
558 /* Define the struct size if it is given */
560 Entry->V.S.SymTab = Tab;
561 Entry->V.S.Size = Size;
567 /* Create a new entry */
568 Entry = NewSymEntry (Name, SC_STRUCT);
570 /* Set the struct data */
571 Entry->V.S.SymTab = Tab;
572 Entry->V.S.Size = Size;
574 /* Add it to the current table */
575 AddSymEntry (TagTab, Entry);
578 /* Return the entry */
584 SymEntry* AddConstSym (const char* Name, const type* Type, unsigned Flags, long Val)
585 /* Add an constant symbol to the symbol table and return it */
587 /* Enums must be inserted in the global symbol table */
588 SymTable* Tab = ((Flags & SC_ENUM) == SC_ENUM)? SymTab0 : SymTab;
590 /* Do we have an entry with this name already? */
591 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
593 if ((Entry->Flags & SC_CONST) != SC_CONST) {
594 Error ("Symbol `%s' is already different kind", Name);
596 Error ("Multiple definition for `%s'", Name);
601 /* Create a new entry */
602 Entry = NewSymEntry (Name, Flags);
604 /* Enum values are ints */
605 Entry->Type = TypeDup (Type);
607 /* Set the enum data */
608 Entry->V.ConstVal = Val;
610 /* Add the entry to the symbol table */
611 AddSymEntry (Tab, Entry);
613 /* Return the entry */
619 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
620 /* Add a goto label to the label table */
622 /* Do we have an entry with this name already? */
623 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
626 if (SymIsDef (Entry) && (Flags & SC_DEF) != 0) {
627 /* Trying to define the label more than once */
628 Error ("Label `%s' is defined more than once", Name);
630 Entry->Flags |= Flags;
634 /* Create a new entry */
635 Entry = NewSymEntry (Name, SC_LABEL | Flags);
637 /* Set a new label number */
638 Entry->V.Label = GetLocalLabel ();
640 /* Add the entry to the label table */
641 AddSymEntry (LabelTab, Entry);
645 /* Return the entry */
651 SymEntry* AddLocalSym (const char* Name, const type* Type, unsigned Flags, int Offs)
652 /* Add a local symbol and return the symbol entry */
654 /* Do we have an entry with this name already? */
655 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
658 /* We have a symbol with this name already */
659 Error ("Multiple definition for `%s'", Name);
663 /* Create a new entry */
664 Entry = NewSymEntry (Name, Flags);
666 /* Set the symbol attributes */
667 Entry->Type = TypeDup (Type);
668 if ((Flags & SC_AUTO) == SC_AUTO) {
669 Entry->V.Offs = Offs;
670 } else if ((Flags & SC_REGISTER) == SC_REGISTER) {
671 Entry->V.R.RegOffs = Offs;
672 Entry->V.R.SaveOffs = oursp; /* ### Cleaner! */
673 } else if ((Flags & SC_STATIC) == SC_STATIC) {
674 Entry->V.Label = Offs;
675 } else if ((Flags & SC_STRUCTFIELD) == SC_STRUCTFIELD) {
676 Entry->V.Offs = Offs;
678 Internal ("Invalid flags in AddLocalSym: %04X", Flags);
681 /* Add the entry to the symbol table */
682 AddSymEntry (SymTab, Entry);
686 /* Return the entry */
692 SymEntry* AddGlobalSym (const char* Name, const type* Type, unsigned Flags)
693 /* Add an external or global symbol to the symbol table and return the entry */
695 /* There is some special handling for functions, so check if it is one */
696 int IsFunc = IsTypeFunc (Type);
698 /* Functions must be inserted in the global symbol table */
699 SymTable* Tab = IsFunc? SymTab0 : SymTab;
701 /* Do we have an entry with this name already? */
702 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
707 /* We have a symbol with this name already */
708 if (Entry->Flags & SC_TYPE) {
709 Error ("Multiple definition for `%s'", Name);
713 /* Get the type string of the existing symbol */
716 /* If we are handling arrays, the old entry or the new entry may be an
717 * incomplete declaration. Accept this, and if the exsting entry is
718 * incomplete, complete it.
720 if (IsTypeArray (Type) && IsTypeArray (EType)) {
722 /* Get the array sizes */
723 long Size = GetElementCount (Type);
724 long ESize = GetElementCount (EType);
726 if ((Size != UNSPECIFIED && ESize != UNSPECIFIED && Size != ESize) ||
727 TypeCmp (Type+DECODE_SIZE+1, EType+DECODE_SIZE+1) < TC_EQUAL) {
728 /* Types not identical: Conflicting types */
729 Error ("Conflicting types for `%s'", Name);
732 /* Check if we have a size in the existing definition */
733 if (ESize == UNSPECIFIED) {
734 /* Existing, size not given, use size from new def */
735 Encode (EType + 1, Size);
740 /* New type must be identical */
741 if (TypeCmp (EType, Type) < TC_EQUAL) {
742 Error ("Conflicting types for `%s'", Name);
746 /* In case of a function, use the new type descriptor, since it
747 * contains pointers to the new symbol tables that are needed if
748 * an actual function definition follows.
751 /* Get the function descriptor from the new type */
752 FuncDesc* F = GetFuncDesc (Type);
753 /* Use this new function descriptor */
755 EncodePtr (EType+1, F);
759 /* Add the new flags */
760 Entry->Flags |= Flags;
764 /* Create a new entry */
765 Entry = NewSymEntry (Name, Flags);
767 /* Set the symbol attributes */
768 Entry->Type = TypeDup (Type);
770 /* If this is a function, set the function descriptor and clear
774 Entry->V.F.Func = GetFuncDesc (Entry->Type);
778 /* Add the entry to the symbol table */
779 AddSymEntry (Tab, Entry);
782 /* Return the entry */
788 /*****************************************************************************/
790 /*****************************************************************************/
794 SymTable* GetSymTab (void)
795 /* Return the current symbol table */
802 SymTable* GetGlobalSymTab (void)
803 /* Return the global symbol table */
810 int SymIsLocal (SymEntry* Sym)
811 /* Return true if the symbol is defined in the highest lexical level */
813 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
818 void MakeZPSym (const char* Name)
819 /* Mark the given symbol as zero page symbol */
821 /* Get the symbol table entry */
822 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
824 /* Mark the symbol as zeropage */
826 Entry->Flags |= SC_ZEROPAGE;
828 Error ("Undefined symbol: `%s'", Name);
834 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
835 /* Write the symbol table to the given file */
838 const SymEntry* Entry;
840 /* Print the header */
842 va_start (ap, Header);
844 Len = vfprintf (F, Header, ap);
848 /* Underline the header */
855 Entry = Tab->SymHead;
857 fprintf (F, "(empty)\n");
860 DumpSymEntry (F, Entry);
861 Entry = Entry->NextSym;
864 fprintf (F, "\n\n\n");
869 void EmitExternals (void)
870 /* Write import/export statements for external symbols */
874 Entry = SymTab->SymHead;
876 unsigned Flags = Entry->Flags;
877 if (Flags & SC_EXTERN) {
878 /* Only defined or referenced externs */
879 if (SymIsRef (Entry) && !SymIsDef (Entry)) {
881 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
882 } else if (SymIsDef (Entry)) {
884 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
887 Entry = Entry->NextSym;