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"
42 #include "../common/xmalloc.h"
58 /*****************************************************************************/
60 /*****************************************************************************/
64 /* An empty symbol table */
65 SymTable EmptySymTab = {
74 /* Symbol table sizes */
75 #define SYMTAB_SIZE_GLOBAL 211U
76 #define SYMTAB_SIZE_FUNCTION 29U
77 #define SYMTAB_SIZE_BLOCK 13U
78 #define SYMTAB_SIZE_STRUCT 19U
79 #define SYMTAB_SIZE_LABEL 7U
81 /* Predefined lexical levels */
82 #define LEX_LEVEL_GLOBAL 1U
84 /* The current and root symbol tables */
85 static unsigned LexicalLevel = 0; /* For safety checks */
86 static SymTable* SymTab0 = 0;
87 static SymTable* SymTab = 0;
88 static SymTable* TagTab0 = 0;
89 static SymTable* TagTab = 0;
90 static SymTable* LabelTab = 0;
94 /*****************************************************************************/
96 /*****************************************************************************/
100 static SymTable* NewSymTable (unsigned Size)
101 /* Create and return a symbol table for the given lexical level */
105 /* Allocate memory for the table */
106 SymTable* S = xmalloc (sizeof (SymTable) + (Size-1) * sizeof (SymEntry*));
108 /* Initialize the symbol table structure */
114 for (I = 0; I < Size; ++I) {
118 /* Return the symbol table */
124 static void FreeSymTable (SymTable* S)
125 /* Free the given symbo table including all symbols */
127 /* Free all symbols */
128 SymEntry* Sym = S->SymHead;
130 SymEntry* NextSym = Sym->NextSym;
135 /* Free the table itself */
141 /*****************************************************************************/
142 /* Check symbols in a table */
143 /*****************************************************************************/
147 static void CheckSymTable (SymTable* Tab)
148 /* Check a symbol table for open references, unused symbols ... */
150 SymEntry* Entry = Tab->SymHead;
153 /* Get the storage flags for tne entry */
154 unsigned Flags = Entry->Flags;
156 /* Ignore typedef entries */
157 if ((Flags & SC_TYPEDEF) != SC_TYPEDEF) {
159 /* Check if the symbol is one with storage, and it if it was
160 * defined but not used.
162 if (((Flags & SC_AUTO) || (Flags & SC_STATIC)) && (Flags & SC_EXTERN) == 0) {
163 if ((Flags & SC_DEF) && !(Flags & SC_REF)) {
164 if (Flags & SC_PARAM) {
165 Warning (WARN_UNUSED_PARM, Entry->Name);
167 Warning (WARN_UNUSED_ITEM, Entry->Name);
172 /* If the entry is a label, check if it was defined in the function */
173 if (Flags & SC_LABEL) {
174 if ((Flags & SC_DEF) == 0) {
175 /* Undefined label */
176 Error (ERR_UNDEFINED_LABEL, Entry->Name);
177 } else if ((Flags & SC_REF) == 0) {
178 /* Defined but not used */
179 Warning (WARN_UNUSED_ITEM, Entry->Name);
186 Entry = Entry->NextSym;
192 /*****************************************************************************/
193 /* Handling of lexical levels */
194 /*****************************************************************************/
198 void EnterGlobalLevel (void)
199 /* Enter the program global lexical level */
202 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
204 /* Create and assign the symbol table */
205 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
207 /* Create and assign the tag table */
208 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
213 void LeaveGlobalLevel (void)
214 /* Leave the program global lexical level */
217 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
219 /* Check the tables */
220 CheckSymTable (SymTab0);
222 /* Dump the tables if requested */
224 PrintSymTable (SymTab0, stdout, "Global symbol table");
225 PrintSymTable (TagTab0, stdout, "Global tag table");
228 /* Don't delete the symbol and struct tables! */
229 SymTab0 = SymTab = 0;
230 TagTab0 = TagTab = 0;
235 void EnterFunctionLevel (void)
236 /* Enter function lexical level */
240 /* New lexical level */
243 /* Get a new symbol table and make it current */
244 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
248 /* Get a new tag table and make it current */
249 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
253 /* Create and assign a new label table */
254 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
259 void RememberFunctionLevel (struct FuncDesc* F)
260 /* Remember the symbol tables for the level and leave the level without checks */
262 /* Leave the lexical level */
265 /* Remember the tables */
269 /* Don't delete the tables */
270 SymTab = SymTab->PrevTab;
271 TagTab = TagTab->PrevTab;
276 void ReenterFunctionLevel (struct FuncDesc* F)
277 /* Reenter the function lexical level using the existing tables from F */
279 /* New lexical level */
282 /* Make the tables current again */
283 F->SymTab->PrevTab = SymTab;
286 F->TagTab->PrevTab = TagTab;
289 /* Create and assign a new label table */
290 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
295 void LeaveFunctionLevel (void)
296 /* Leave function lexical level */
298 /* Leave the lexical level */
301 /* Check the tables */
302 CheckSymTable (SymTab);
303 CheckSymTable (LabelTab);
305 /* Drop the label table if it is empty */
306 if (LabelTab->SymCount == 0) {
307 FreeSymTable (LabelTab);
310 /* Don't delete the tables */
311 SymTab = SymTab->PrevTab;
312 TagTab = TagTab->PrevTab;
318 void EnterBlockLevel (void)
319 /* Enter a nested block in a function */
323 /* New lexical level */
326 /* Get a new symbol table and make it current */
327 S = NewSymTable (SYMTAB_SIZE_BLOCK);
331 /* Get a new tag table and make it current */
332 S = NewSymTable (SYMTAB_SIZE_BLOCK);
339 void LeaveBlockLevel (void)
340 /* Leave a nested block in a function */
342 /* Leave the lexical level */
345 /* Check the tables */
346 CheckSymTable (SymTab);
348 /* Don't delete the tables */
349 SymTab = SymTab->PrevTab;
350 TagTab = TagTab->PrevTab;
355 void EnterStructLevel (void)
356 /* Enter a nested block for a struct definition */
360 /* Get a new symbol table and make it current. Note: Structs and enums
361 * nested in struct scope are NOT local to the struct but visible in the
362 * outside scope. So we will NOT create a new struct or enum table.
364 S = NewSymTable (SYMTAB_SIZE_BLOCK);
371 void LeaveStructLevel (void)
372 /* Leave a nested block for a struct definition */
374 /* Don't delete the table */
375 SymTab = SymTab->PrevTab;
380 /*****************************************************************************/
382 /*****************************************************************************/
386 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
387 /* Search for an entry in one table */
389 /* Get the start of the hash chain */
390 SymEntry* E = T->Tab [Hash % T->Size];
392 /* Compare the name */
393 if (strcmp (E->Name, Name) == 0) {
397 /* Not found, next entry in hash chain */
407 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
408 /* Find the symbol with the given name in the table tree that starts with T */
410 /* Get the hash over the name */
411 unsigned Hash = HashStr (Name);
413 /* Check all symbol tables for the symbol */
415 /* Try to find the symbol in this table */
416 SymEntry* E = FindSymInTable (Tab, Name, Hash);
418 /* Bail out if we found it */
423 /* Repeat the search in the next higher lexical level */
433 SymEntry* FindSym (const char* Name)
434 /* Find the symbol with the given name */
436 return FindSymInTree (SymTab, Name);
441 SymEntry* FindLocalSym (const char* Name)
442 /* Find the symbol with the given name in the current symbol table only */
444 return FindSymInTable (SymTab, Name, HashStr (Name));
449 SymEntry* FindTagSym (const char* Name)
450 /* Find the symbol with the given name in the tag table */
452 return FindSymInTree (TagTab, Name);
457 SymEntry* FindStructField (const type* Type, const char* Name)
458 /* Find a struct field in the fields list */
462 /* The given type may actually be a pointer to struct */
463 if (Type[0] == T_PTR) {
467 /* Non-structs do not have any struct fields... */
468 if (IsStruct (Type)) {
472 /* Get a pointer to the struct/union type */
473 const SymEntry* Struct = (const SymEntry*) Decode (Type+1);
476 /* Get the field symbol table from the struct entry.
477 * Beware: The table may not exist.
479 Tab = Struct->V.S.SymTab;
481 /* Now search in the struct symbol table */
483 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
492 /*****************************************************************************/
493 /* Add stuff to the symbol table */
494 /*****************************************************************************/
498 static void AddSymEntry (SymTable* T, SymEntry* S)
499 /* Add a symbol to a symbol table */
501 /* Get the hash value for the name */
502 unsigned Hash = HashStr (S->Name) % T->Size;
504 /* Insert the symbol into the list of all symbols in this level */
506 T->SymTail->NextSym = S;
508 S->PrevSym = T->SymTail;
510 if (T->SymHead == 0) {
516 /* Insert the symbol into the hash chain */
517 S->NextHash = T->Tab[Hash];
520 /* Tell the symbol in which table it is */
526 SymEntry* AddStructSym (const char* Name, unsigned Size, SymTable* Tab)
527 /* Add a struct/union entry and return it */
529 /* Do we have an entry with this name already? */
530 SymEntry* Entry = FindSymInTable (TagTab, Name, HashStr (Name));
533 /* We do have an entry. This may be a forward, so check it. */
534 if ((Entry->Flags & SC_STRUCT) == 0) {
535 /* Existing symbol is not a struct */
536 Error (ERR_SYMBOL_KIND);
537 } else if (Size > 0 && Entry->V.S.Size > 0) {
538 /* Both structs are definitions. */
539 Error (ERR_MULTIPLE_DEFINITION, Name);
541 /* Define the struct size if it is given */
543 Entry->V.S.SymTab = Tab;
544 Entry->V.S.Size = Size;
550 /* Create a new entry */
551 Entry = NewSymEntry (Name, SC_STRUCT);
553 /* Set the struct data */
554 Entry->V.S.SymTab = Tab;
555 Entry->V.S.Size = Size;
557 /* Add it to the current table */
558 AddSymEntry (TagTab, Entry);
561 /* Return the entry */
567 SymEntry* AddEnumSym (const char* Name, int Val)
568 /* Add an enum symbol to the symbol table and return it */
570 /* Do we have an entry with this name already? */
571 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
573 if (Entry->Flags != SC_ENUM) {
574 Error (ERR_SYMBOL_KIND);
576 Error (ERR_MULTIPLE_DEFINITION, Name);
581 /* Create a new entry */
582 Entry = NewSymEntry (Name, SC_ENUM);
584 /* Enum values are ints */
585 Entry->Type = TypeDup (type_int);
587 /* Set the enum data */
588 Entry->V.EnumVal = Val;
590 /* Add the entry to the symbol table */
591 AddSymEntry (SymTab, Entry);
593 /* Return the entry */
599 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
600 /* Add a goto label to the label table */
602 /* Do we have an entry with this name already? */
603 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
606 if ((Entry->Flags & SC_DEF) != 0 && (Flags & SC_DEF) != 0) {
607 /* Trying to define the label more than once */
608 Error (ERR_MULTIPLE_DEFINITION, Name);
610 Entry->Flags |= Flags;
614 /* Create a new entry */
615 Entry = NewSymEntry (Name, SC_LABEL | Flags);
617 /* Set a new label number */
618 Entry->V.Label = GetLabel ();
620 /* Add the entry to the label table */
621 AddSymEntry (LabelTab, Entry);
625 /* Return the entry */
631 SymEntry* AddLocalSym (const char* Name, type* Type, unsigned Flags, int Offs)
632 /* Add a local symbol and return the symbol entry */
634 /* Do we have an entry with this name already? */
635 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
638 /* We have a symbol with this name already */
639 Error (ERR_MULTIPLE_DEFINITION, Name);
643 /* Create a new entry */
644 Entry = NewSymEntry (Name, Flags);
646 /* Set the symbol attributes */
647 Entry->Type = TypeDup (Type);
648 Entry->V.Offs = Offs;
650 /* Add the entry to the symbol table */
651 AddSymEntry (SymTab, Entry);
655 /* Return the entry */
661 SymEntry* AddGlobalSym (const char* Name, type* Type, unsigned Flags)
662 /* Add an external or global symbol to the symbol table and return the entry */
664 /* Functions must be inserted in the global symbol table */
665 SymTable* Tab = IsFunc (Type)? SymTab0 : SymTab;
667 /* Do we have an entry with this name already? */
668 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
673 /* We have a symbol with this name already */
674 if (Entry->Flags & SC_TYPE) {
675 Error (ERR_MULTIPLE_DEFINITION, Name);
679 /* Get the type string of the existing symbol */
682 /* If we are handling arrays, the old entry or the new entry may be an
683 * incomplete declaration. Accept this, and if the exsting entry is
684 * incomplete, complete it.
686 if (IsArray (Type) && IsArray (EType)) {
688 /* Get the array sizes */
689 unsigned Size = Decode (Type + 1);
690 unsigned ESize = Decode (EType + 1);
692 if ((Size != 0 && ESize != 0) ||
693 TypeCmp (Type+DECODE_SIZE+1, EType+DECODE_SIZE+1) != 0) {
694 /* Types not identical: Duplicate definition */
695 Error (ERR_MULTIPLE_DEFINITION, Name);
697 /* Check if we have a size in the existing definition */
699 /* Existing, size not given, use size from new def */
700 Encode (EType + 1, Size);
705 /* New type must be identical */
706 if (!EqualTypes (EType, Type) != 0) {
707 Error (ERR_MULTIPLE_DEFINITION, Name);
710 /* In case of a function, use the new type descriptor, since it
711 * contains pointers to the new symbol tables that are needed if
712 * an actual function definition follows.
715 CopyEncode (Type+1, EType+1);
719 /* Add the new flags */
720 Entry->Flags |= Flags;
724 /* Create a new entry */
725 Entry = NewSymEntry (Name, Flags);
727 /* Set the symbol attributes */
728 Entry->Type = TypeDup (Type);
730 /* Add the entry to the symbol table */
731 AddSymEntry (Tab, Entry);
734 /* Return the entry */
740 /*****************************************************************************/
742 /*****************************************************************************/
746 SymTable* GetSymTab (void)
747 /* Return the current symbol table */
754 int SymIsLocal (SymEntry* Sym)
755 /* Return true if the symbol is defined in the highest lexical level */
757 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
762 static int EqualSymTables (SymTable* Tab1, SymTable* Tab2)
763 /* Compare two symbol tables. Return 1 if they are equal and 0 otherwise */
765 /* Compare the parameter lists */
766 SymEntry* Sym1 = Tab1->SymHead;
767 SymEntry* Sym2 = Tab2->SymHead;
769 /* Compare the fields */
770 while (Sym1 && Sym2) {
772 /* Compare this field */
773 if (!EqualTypes (Sym1->Type, Sym2->Type)) {
774 /* Field types not equal */
778 /* Get the pointers to the next fields */
779 Sym1 = Sym1->NextSym;
780 Sym2 = Sym2->NextSym;
783 /* Check both pointers against NULL to compare the field count */
784 return (Sym1 == 0 && Sym2 == 0);
789 int EqualTypes (const type* Type1, const type* Type2)
790 /* Recursively compare two types. Return 1 if the types match, return 0
804 /* Shortcut here: If the pointers are identical, the types are identical */
805 if (Type1 == Type2) {
809 /* Compare two types. Determine, where they differ */
810 while (*Type1 == *Type2 && *Type1 != T_END) {
815 /* Compare the function descriptors */
816 F1 = DecodePtr (Type1+1);
817 F2 = DecodePtr (Type2+1);
819 /* If one of the functions is implicitly declared, both
820 * functions are considered equal. If one of the functions is
821 * old style, and the other is empty, the functions are
824 if ((F1->Flags & FD_IMPLICIT) != 0 || (F2->Flags & FD_IMPLICIT) != 0) {
826 } else if ((F1->Flags & FD_OLDSTYLE) != 0 && (F2->Flags & FD_EMPTY) != 0) {
828 } else if ((F1->Flags & FD_EMPTY) != 0 && (F2->Flags & FD_OLDSTYLE) != 0) {
836 /* Check the remaining flags */
837 if ((F1->Flags & ~FD_IGNORE) != (F2->Flags & ~FD_IGNORE)) {
842 /* Compare the parameter lists */
843 if (EqualSymTables (F1->SymTab, F2->SymTab) == 0 ||
844 EqualSymTables (F1->TagTab, F2->TagTab) == 0) {
845 /* One of the tables is not identical */
850 /* Skip the FuncDesc pointers to compare the return type */
851 Type1 += DECODE_SIZE;
852 Type2 += DECODE_SIZE;
856 /* Check member count */
857 v1 = Decode (Type1+1);
858 v2 = Decode (Type2+1);
859 if (v1 != 0 && v2 != 0 && v1 != v2) {
860 /* Member count given but different */
863 Type1 += DECODE_SIZE;
864 Type2 += DECODE_SIZE;
869 /* Compare the fields recursively. To do that, we fetch the
870 * pointer to the struct definition from the type, and compare
873 Sym1 = DecodePtr (Type1+1);
874 Sym2 = DecodePtr (Type2+1);
876 /* Get the field tables from the struct entry */
877 Tab1 = Sym1->V.S.SymTab;
878 Tab2 = Sym2->V.S.SymTab;
880 /* One or both structs may be forward definitions. In this case,
881 * the symbol tables are both non existant. Assume that the
882 * structs are equal in this case.
884 if (Tab1 != 0 && Tab2 != 0) {
886 if (EqualSymTables (Tab1, Tab2) == 0) {
887 /* Field lists are not equal */
893 /* Structs are equal */
894 Type1 += DECODE_SIZE;
895 Type2 += DECODE_SIZE;
902 /* Done, types are equal */
908 void MakeZPSym (const char* Name)
909 /* Mark the given symbol as zero page symbol */
911 /* Get the symbol table entry */
912 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
914 /* Mark the symbol as zeropage */
916 Entry->Flags |= SC_ZEROPAGE;
918 Error (ERR_UNDEFINED_SYMBOL, Name);
924 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
925 /* Write the symbol table to the given file */
928 const SymEntry* Entry;
930 /* Print the header */
932 va_start (ap, Header);
934 Len = vfprintf (F, Header, ap);
938 /* Underline the header */
945 Entry = Tab->SymHead;
947 fprintf (F, "(empty)\n");
950 DumpSymEntry (F, Entry);
951 Entry = Entry->NextSym;
954 fprintf (F, "\n\n\n");
959 void EmitExternals (void)
960 /* Write import/export statements for external symbols */
966 Entry = SymTab->SymHead;
968 unsigned Flags = Entry->Flags;
969 if (Flags & SC_EXTERN) {
970 /* Only defined or referenced externs */
971 if ((Flags & SC_REF) != 0 && (Flags & SC_DEF) == 0) {
973 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
974 } else if (Flags & SC_DEF) {
976 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
979 Entry = Entry->NextSym;