1 /*****************************************************************************/
5 /* Symbol table management for the cc65 C compiler */
9 /* (C) 2000 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
12 /* EMail: uz@musoftware.de */
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 /*****************************************************************************/
41 #include "../common/hashstr.h"
59 /*****************************************************************************/
61 /*****************************************************************************/
65 /* An empty symbol table */
66 SymTable EmptySymTab = {
75 /* Symbol table sizes */
76 #define SYMTAB_SIZE_GLOBAL 211U
77 #define SYMTAB_SIZE_FUNCTION 29U
78 #define SYMTAB_SIZE_BLOCK 13U
79 #define SYMTAB_SIZE_STRUCT 19U
80 #define SYMTAB_SIZE_LABEL 7U
82 /* Predefined lexical levels */
83 #define LEX_LEVEL_GLOBAL 1U
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 ((Flags & SC_DEF) && !(Flags & SC_REF)) {
165 if (Flags & SC_PARAM) {
166 Warning (WARN_UNUSED_PARM, Entry->Name);
168 Warning (WARN_UNUSED_ITEM, Entry->Name);
173 /* If the entry is a label, check if it was defined in the function */
174 if (Flags & SC_LABEL) {
175 if ((Flags & SC_DEF) == 0) {
176 /* Undefined label */
177 Error (ERR_UNDEFINED_LABEL, Entry->Name);
178 } else if ((Flags & SC_REF) == 0) {
179 /* Defined but not used */
180 Warning (WARN_UNUSED_ITEM, Entry->Name);
187 Entry = Entry->NextSym;
193 /*****************************************************************************/
194 /* Handling of lexical levels */
195 /*****************************************************************************/
199 void EnterGlobalLevel (void)
200 /* Enter the program global lexical level */
203 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
205 /* Create and assign the symbol table */
206 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
208 /* Create and assign the tag table */
209 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
214 void LeaveGlobalLevel (void)
215 /* Leave the program global lexical level */
218 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
220 /* Check the tables */
221 CheckSymTable (SymTab0);
223 /* Dump the tables if requested */
225 PrintSymTable (SymTab0, stdout, "Global symbol table");
226 PrintSymTable (TagTab0, stdout, "Global tag table");
229 /* Don't delete the symbol and struct tables! */
230 SymTab0 = SymTab = 0;
231 TagTab0 = TagTab = 0;
236 void EnterFunctionLevel (void)
237 /* Enter function lexical level */
241 /* New lexical level */
244 /* Get a new symbol table and make it current */
245 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
249 /* Get a new tag table and make it current */
250 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
254 /* Create and assign a new label table */
255 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
260 void RememberFunctionLevel (struct FuncDesc* F)
261 /* Remember the symbol tables for the level and leave the level without checks */
263 /* Leave the lexical level */
266 /* Remember the tables */
270 /* Don't delete the tables */
271 SymTab = SymTab->PrevTab;
272 TagTab = TagTab->PrevTab;
277 void ReenterFunctionLevel (struct FuncDesc* F)
278 /* Reenter the function lexical level using the existing tables from F */
280 /* New lexical level */
283 /* Make the tables current again */
284 F->SymTab->PrevTab = SymTab;
287 F->TagTab->PrevTab = TagTab;
290 /* Create and assign a new label table */
291 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
296 void LeaveFunctionLevel (void)
297 /* Leave function lexical level */
299 /* Leave the lexical level */
302 /* Check the tables */
303 CheckSymTable (SymTab);
304 CheckSymTable (LabelTab);
306 /* Drop the label table if it is empty */
307 if (LabelTab->SymCount == 0) {
308 FreeSymTable (LabelTab);
311 /* Don't delete the tables */
312 SymTab = SymTab->PrevTab;
313 TagTab = TagTab->PrevTab;
319 void EnterBlockLevel (void)
320 /* Enter a nested block in a function */
324 /* New lexical level */
327 /* Get a new symbol table and make it current */
328 S = NewSymTable (SYMTAB_SIZE_BLOCK);
332 /* Get a new tag table and make it current */
333 S = NewSymTable (SYMTAB_SIZE_BLOCK);
340 void LeaveBlockLevel (void)
341 /* Leave a nested block in a function */
343 /* Leave the lexical level */
346 /* Check the tables */
347 CheckSymTable (SymTab);
349 /* Don't delete the tables */
350 SymTab = SymTab->PrevTab;
351 TagTab = TagTab->PrevTab;
356 void EnterStructLevel (void)
357 /* Enter a nested block for a struct definition */
361 /* Get a new symbol table and make it current. Note: Structs and enums
362 * nested in struct scope are NOT local to the struct but visible in the
363 * outside scope. So we will NOT create a new struct or enum table.
365 S = NewSymTable (SYMTAB_SIZE_BLOCK);
372 void LeaveStructLevel (void)
373 /* Leave a nested block for a struct definition */
375 /* Don't delete the table */
376 SymTab = SymTab->PrevTab;
381 /*****************************************************************************/
383 /*****************************************************************************/
387 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
388 /* Search for an entry in one table */
390 /* Get the start of the hash chain */
391 SymEntry* E = T->Tab [Hash % T->Size];
393 /* Compare the name */
394 if (strcmp (E->Name, Name) == 0) {
398 /* Not found, next entry in hash chain */
408 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
409 /* Find the symbol with the given name in the table tree that starts with T */
411 /* Get the hash over the name */
412 unsigned Hash = HashStr (Name);
414 /* Check all symbol tables for the symbol */
416 /* Try to find the symbol in this table */
417 SymEntry* E = FindSymInTable (Tab, Name, Hash);
419 /* Bail out if we found it */
424 /* Repeat the search in the next higher lexical level */
434 SymEntry* FindSym (const char* Name)
435 /* Find the symbol with the given name */
437 return FindSymInTree (SymTab, Name);
442 SymEntry* FindLocalSym (const char* Name)
443 /* Find the symbol with the given name in the current symbol table only */
445 return FindSymInTable (SymTab, Name, HashStr (Name));
450 SymEntry* FindTagSym (const char* Name)
451 /* Find the symbol with the given name in the tag table */
453 return FindSymInTree (TagTab, Name);
458 SymEntry* FindStructField (const type* Type, const char* Name)
459 /* Find a struct field in the fields list */
463 /* The given type may actually be a pointer to struct */
464 if (Type[0] == T_PTR) {
468 /* Non-structs do not have any struct fields... */
469 if (IsStruct (Type)) {
473 /* Get a pointer to the struct/union type */
474 const SymEntry* Struct = (const SymEntry*) Decode (Type+1);
477 /* Get the field symbol table from the struct entry.
478 * Beware: The table may not exist.
480 Tab = Struct->V.S.SymTab;
482 /* Now search in the struct symbol table */
484 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
493 /*****************************************************************************/
494 /* Add stuff to the symbol table */
495 /*****************************************************************************/
499 static void AddSymEntry (SymTable* T, SymEntry* S)
500 /* Add a symbol to a symbol table */
502 /* Get the hash value for the name */
503 unsigned Hash = HashStr (S->Name) % T->Size;
505 /* Insert the symbol into the list of all symbols in this level */
507 T->SymTail->NextSym = S;
509 S->PrevSym = T->SymTail;
511 if (T->SymHead == 0) {
517 /* Insert the symbol into the hash chain */
518 S->NextHash = T->Tab[Hash];
521 /* Tell the symbol in which table it is */
527 SymEntry* AddStructSym (const char* Name, unsigned Size, SymTable* Tab)
528 /* Add a struct/union entry and return it */
530 /* Do we have an entry with this name already? */
531 SymEntry* Entry = FindSymInTable (TagTab, Name, HashStr (Name));
534 /* We do have an entry. This may be a forward, so check it. */
535 if ((Entry->Flags & SC_STRUCT) == 0) {
536 /* Existing symbol is not a struct */
537 Error (ERR_SYMBOL_KIND);
538 } else if (Size > 0 && Entry->V.S.Size > 0) {
539 /* Both structs are definitions. */
540 Error (ERR_MULTIPLE_DEFINITION, Name);
542 /* Define the struct size if it is given */
544 Entry->V.S.SymTab = Tab;
545 Entry->V.S.Size = Size;
551 /* Create a new entry */
552 Entry = NewSymEntry (Name, SC_STRUCT);
554 /* Set the struct data */
555 Entry->V.S.SymTab = Tab;
556 Entry->V.S.Size = Size;
558 /* Add it to the current table */
559 AddSymEntry (TagTab, Entry);
562 /* Return the entry */
568 SymEntry* AddEnumSym (const char* Name, int Val)
569 /* Add an enum symbol to the symbol table and return it */
571 /* Do we have an entry with this name already? */
572 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
574 if (Entry->Flags != SC_ENUM) {
575 Error (ERR_SYMBOL_KIND);
577 Error (ERR_MULTIPLE_DEFINITION, Name);
582 /* Create a new entry */
583 Entry = NewSymEntry (Name, SC_ENUM);
585 /* Enum values are ints */
586 Entry->Type = TypeDup (type_int);
588 /* Set the enum data */
589 Entry->V.EnumVal = Val;
591 /* Add the entry to the symbol table */
592 AddSymEntry (SymTab, Entry);
594 /* Return the entry */
600 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
601 /* Add a goto label to the label table */
603 /* Do we have an entry with this name already? */
604 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
607 if ((Entry->Flags & SC_DEF) != 0 && (Flags & SC_DEF) != 0) {
608 /* Trying to define the label more than once */
609 Error (ERR_MULTIPLE_DEFINITION, Name);
611 Entry->Flags |= Flags;
615 /* Create a new entry */
616 Entry = NewSymEntry (Name, SC_LABEL | Flags);
618 /* Set a new label number */
619 Entry->V.Label = GetLabel ();
621 /* Add the entry to the label table */
622 AddSymEntry (LabelTab, Entry);
626 /* Return the entry */
632 SymEntry* AddLocalSym (const char* Name, type* Type, unsigned Flags, int Offs)
633 /* Add a local symbol and return the symbol entry */
637 /* Functions declared inside of functions do always have external linkage */
638 if (Type != 0 && IsFunc (Type)) {
639 if ((Flags & (SC_DEFAULT | SC_EXTERN)) == 0) {
640 Warning (WARN_FUNC_MUST_BE_EXTERN);
645 /* Do we have an entry with this name already? */
646 Entry = FindSymInTable (SymTab, Name, HashStr (Name));
649 /* We have a symbol with this name already */
650 Error (ERR_MULTIPLE_DEFINITION, Name);
654 /* Create a new entry */
655 Entry = NewSymEntry (Name, Flags);
657 /* Set the symbol attributes */
658 Entry->Type = TypeDup (Type);
659 Entry->V.Offs = Offs;
661 /* Add the entry to the symbol table */
662 AddSymEntry (SymTab, Entry);
666 /* Return the entry */
672 SymEntry* AddGlobalSym (const char* Name, type* Type, unsigned Flags)
673 /* Add an external or global symbol to the symbol table and return the entry */
675 /* Functions must be inserted in the global symbol table */
676 SymTable* Tab = IsFunc (Type)? SymTab0 : SymTab;
678 /* Do we have an entry with this name already? */
679 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
684 /* We have a symbol with this name already */
685 if (Entry->Flags & SC_TYPE) {
686 Error (ERR_MULTIPLE_DEFINITION, Name);
690 /* Get the type string of the existing symbol */
693 /* If we are handling arrays, the old entry or the new entry may be an
694 * incomplete declaration. Accept this, and if the exsting entry is
695 * incomplete, complete it.
697 if (IsArray (Type) && IsArray (EType)) {
699 /* Get the array sizes */
700 unsigned Size = Decode (Type + 1);
701 unsigned ESize = Decode (EType + 1);
703 if ((Size != 0 && ESize != 0) ||
704 TypeCmp (Type+DECODE_SIZE+1, EType+DECODE_SIZE+1) != 0) {
705 /* Types not identical: Duplicate definition */
706 Error (ERR_MULTIPLE_DEFINITION, Name);
708 /* Check if we have a size in the existing definition */
710 /* Existing, size not given, use size from new def */
711 Encode (EType + 1, Size);
716 /* New type must be identical */
717 if (!EqualTypes (EType, Type) != 0) {
718 Error (ERR_MULTIPLE_DEFINITION, Name);
721 /* In case of a function, use the new type descriptor, since it
722 * contains pointers to the new symbol tables that are needed if
723 * an actual function definition follows.
726 CopyEncode (Type+1, EType+1);
730 /* Add the new flags */
731 Entry->Flags |= Flags;
735 /* Create a new entry */
736 Entry = NewSymEntry (Name, Flags);
738 /* Set the symbol attributes */
739 Entry->Type = TypeDup (Type);
741 /* Add the entry to the symbol table */
742 AddSymEntry (Tab, Entry);
745 /* Return the entry */
751 /*****************************************************************************/
753 /*****************************************************************************/
757 SymTable* GetSymTab (void)
758 /* Return the current symbol table */
765 int SymIsLocal (SymEntry* Sym)
766 /* Return true if the symbol is defined in the highest lexical level */
768 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
773 static int EqualSymTables (SymTable* Tab1, SymTable* Tab2)
774 /* Compare two symbol tables. Return 1 if they are equal and 0 otherwise */
776 /* Compare the parameter lists */
777 SymEntry* Sym1 = Tab1->SymHead;
778 SymEntry* Sym2 = Tab2->SymHead;
780 /* Compare the fields */
781 while (Sym1 && Sym2) {
783 /* Compare this field */
784 if (!EqualTypes (Sym1->Type, Sym2->Type)) {
785 /* Field types not equal */
789 /* Get the pointers to the next fields */
790 Sym1 = Sym1->NextSym;
791 Sym2 = Sym2->NextSym;
794 /* Check both pointers against NULL to compare the field count */
795 return (Sym1 == 0 && Sym2 == 0);
800 int EqualTypes (const type* Type1, const type* Type2)
801 /* Recursively compare two types. Return 1 if the types match, return 0
815 /* Shortcut here: If the pointers are identical, the types are identical */
816 if (Type1 == Type2) {
820 /* Compare two types. Determine, where they differ */
821 while (*Type1 == *Type2 && *Type1 != T_END) {
826 /* Compare the function descriptors */
827 F1 = DecodePtr (Type1+1);
828 F2 = DecodePtr (Type2+1);
830 /* If one of the functions is implicitly declared, both
831 * functions are considered equal. If one of the functions is
832 * old style, and the other is empty, the functions are
835 if ((F1->Flags & FD_IMPLICIT) != 0 || (F2->Flags & FD_IMPLICIT) != 0) {
837 } else if ((F1->Flags & FD_OLDSTYLE) != 0 && (F2->Flags & FD_EMPTY) != 0) {
839 } else if ((F1->Flags & FD_EMPTY) != 0 && (F2->Flags & FD_OLDSTYLE) != 0) {
847 /* Check the remaining flags */
848 if ((F1->Flags & ~FD_IGNORE) != (F2->Flags & ~FD_IGNORE)) {
853 /* Compare the parameter lists */
854 if (EqualSymTables (F1->SymTab, F2->SymTab) == 0 ||
855 EqualSymTables (F1->TagTab, F2->TagTab) == 0) {
856 /* One of the tables is not identical */
861 /* Skip the FuncDesc pointers to compare the return type */
862 Type1 += DECODE_SIZE;
863 Type2 += DECODE_SIZE;
867 /* Check member count */
868 v1 = Decode (Type1+1);
869 v2 = Decode (Type2+1);
870 if (v1 != 0 && v2 != 0 && v1 != v2) {
871 /* Member count given but different */
874 Type1 += DECODE_SIZE;
875 Type2 += DECODE_SIZE;
880 /* Compare the fields recursively. To do that, we fetch the
881 * pointer to the struct definition from the type, and compare
884 Sym1 = DecodePtr (Type1+1);
885 Sym2 = DecodePtr (Type2+1);
887 /* Get the field tables from the struct entry */
888 Tab1 = Sym1->V.S.SymTab;
889 Tab2 = Sym2->V.S.SymTab;
891 /* One or both structs may be forward definitions. In this case,
892 * the symbol tables are both non existant. Assume that the
893 * structs are equal in this case.
895 if (Tab1 != 0 && Tab2 != 0) {
897 if (EqualSymTables (Tab1, Tab2) == 0) {
898 /* Field lists are not equal */
904 /* Structs are equal */
905 Type1 += DECODE_SIZE;
906 Type2 += DECODE_SIZE;
913 /* Done, types are equal */
919 void MakeZPSym (const char* Name)
920 /* Mark the given symbol as zero page symbol */
922 /* Get the symbol table entry */
923 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
925 /* Mark the symbol as zeropage */
927 Entry->Flags |= SC_ZEROPAGE;
929 Error (ERR_UNDEFINED_SYMBOL, Name);
935 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
936 /* Write the symbol table to the given file */
939 const SymEntry* Entry;
941 /* Print the header */
943 va_start (ap, Header);
945 Len = vfprintf (F, Header, ap);
949 /* Underline the header */
956 Entry = Tab->SymHead;
958 fprintf (F, "(empty)\n");
961 DumpSymEntry (F, Entry);
962 Entry = Entry->NextSym;
965 fprintf (F, "\n\n\n");
970 void EmitExternals (void)
971 /* Write import/export statements for external symbols */
977 Entry = SymTab->SymHead;
979 unsigned Flags = Entry->Flags;
980 if (Flags & SC_EXTERN) {
981 /* Only defined or referenced externs */
982 if ((Flags & SC_REF) != 0 && (Flags & SC_DEF) == 0) {
984 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
985 } else if (Flags & SC_DEF) {
987 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
990 Entry = Entry->NextSym;