1 /*****************************************************************************/
5 /* Symbol table management for the cc65 C compiler */
9 /* (C) 2000-2006 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"
63 /*****************************************************************************/
65 /*****************************************************************************/
69 /* An empty symbol table */
70 SymTable EmptySymTab = {
79 /* Symbol table sizes */
80 #define SYMTAB_SIZE_GLOBAL 211U
81 #define SYMTAB_SIZE_FUNCTION 29U
82 #define SYMTAB_SIZE_BLOCK 13U
83 #define SYMTAB_SIZE_STRUCT 19U
84 #define SYMTAB_SIZE_LABEL 7U
86 /* The current and root symbol tables */
87 static unsigned LexicalLevel = 0; /* For safety checks */
88 static SymTable* SymTab0 = 0;
89 static SymTable* SymTab = 0;
90 static SymTable* TagTab0 = 0;
91 static SymTable* TagTab = 0;
92 static SymTable* LabelTab = 0;
96 /*****************************************************************************/
98 /*****************************************************************************/
102 static SymTable* NewSymTable (unsigned Size)
103 /* Create and return a symbol table for the given lexical level */
107 /* Allocate memory for the table */
108 SymTable* S = xmalloc (sizeof (SymTable) + (Size-1) * sizeof (SymEntry*));
110 /* Initialize the symbol table structure */
116 for (I = 0; I < Size; ++I) {
120 /* Return the symbol table */
126 static void FreeSymTable (SymTable* S)
127 /* Free the given symbo table including all symbols */
129 /* Free all symbols */
130 SymEntry* Sym = S->SymHead;
132 SymEntry* NextSym = Sym->NextSym;
137 /* Free the table itself */
143 /*****************************************************************************/
144 /* Check symbols in a table */
145 /*****************************************************************************/
149 static void CheckSymTable (SymTable* Tab)
150 /* Check a symbol table for open references, unused symbols ... */
152 SymEntry* Entry = Tab->SymHead;
155 /* Get the storage flags for tne entry */
156 unsigned Flags = Entry->Flags;
158 /* Ignore typedef entries */
159 if ((Flags & SC_TYPEDEF) != SC_TYPEDEF) {
161 /* Check if the symbol is one with storage, and it if it was
162 * defined but not used.
164 if (((Flags & SC_AUTO) || (Flags & SC_STATIC)) && (Flags & SC_EXTERN) == 0) {
165 if (SymIsDef (Entry) && !SymIsRef (Entry)) {
166 if (Flags & SC_PARAM) {
167 Warning ("Parameter `%s' is never used", Entry->Name);
169 Warning ("`%s' is defined but never used", Entry->Name);
174 /* If the entry is a label, check if it was defined in the function */
175 if (Flags & SC_LABEL) {
176 if (!SymIsDef (Entry)) {
177 /* Undefined label */
178 Error ("Undefined label: `%s'", Entry->Name);
179 } else if (!SymIsRef (Entry)) {
180 /* Defined but not used */
181 Warning ("`%s' is defined but never used", Entry->Name);
188 Entry = Entry->NextSym;
194 /*****************************************************************************/
195 /* Handling of lexical levels */
196 /*****************************************************************************/
200 unsigned GetLexicalLevel (void)
201 /* Return the current lexical level */
208 void EnterGlobalLevel (void)
209 /* Enter the program global lexical level */
212 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
214 /* Create and assign the symbol table */
215 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
217 /* Create and assign the tag table */
218 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
223 void LeaveGlobalLevel (void)
224 /* Leave the program global lexical level */
227 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
229 /* Check the tables */
230 CheckSymTable (SymTab0);
232 /* Dump the tables if requested */
234 PrintSymTable (SymTab0, stdout, "Global symbol table");
235 PrintSymTable (TagTab0, stdout, "Global tag table");
238 /* Don't delete the symbol and struct tables! */
245 void EnterFunctionLevel (void)
246 /* Enter function lexical level */
250 /* New lexical level */
253 /* Get a new symbol table and make it current */
254 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
258 /* Get a new tag table and make it current */
259 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
263 /* Create and assign a new label table */
264 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
269 void RememberFunctionLevel (struct FuncDesc* F)
270 /* Remember the symbol tables for the level and leave the level without checks */
272 /* Leave the lexical level */
275 /* Remember the tables */
279 /* Don't delete the tables */
280 SymTab = SymTab->PrevTab;
281 TagTab = TagTab->PrevTab;
286 void ReenterFunctionLevel (struct FuncDesc* F)
287 /* Reenter the function lexical level using the existing tables from F */
289 /* New lexical level */
292 /* Make the tables current again */
293 F->SymTab->PrevTab = SymTab;
296 F->TagTab->PrevTab = TagTab;
299 /* Create and assign a new label table */
300 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
305 void LeaveFunctionLevel (void)
306 /* Leave function lexical level */
308 /* Leave the lexical level */
311 /* Check the tables */
312 CheckSymTable (SymTab);
313 CheckSymTable (LabelTab);
315 /* Drop the label table if it is empty */
316 if (LabelTab->SymCount == 0) {
317 FreeSymTable (LabelTab);
320 /* Don't delete the tables */
321 SymTab = SymTab->PrevTab;
322 TagTab = TagTab->PrevTab;
328 void EnterBlockLevel (void)
329 /* Enter a nested block in a function */
333 /* New lexical level */
336 /* Get a new symbol table and make it current */
337 S = NewSymTable (SYMTAB_SIZE_BLOCK);
341 /* Get a new tag table and make it current */
342 S = NewSymTable (SYMTAB_SIZE_BLOCK);
349 void LeaveBlockLevel (void)
350 /* Leave a nested block in a function */
352 /* Leave the lexical level */
355 /* Check the tables */
356 CheckSymTable (SymTab);
358 /* Don't delete the tables */
359 SymTab = SymTab->PrevTab;
360 TagTab = TagTab->PrevTab;
365 void EnterStructLevel (void)
366 /* Enter a nested block for a struct definition */
370 /* Get a new symbol table and make it current. Note: Structs and enums
371 * nested in struct scope are NOT local to the struct but visible in the
372 * outside scope. So we will NOT create a new struct or enum table.
374 S = NewSymTable (SYMTAB_SIZE_BLOCK);
381 void LeaveStructLevel (void)
382 /* Leave a nested block for a struct definition */
384 /* Don't delete the table */
385 SymTab = SymTab->PrevTab;
390 /*****************************************************************************/
392 /*****************************************************************************/
396 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
397 /* Search for an entry in one table */
399 /* Get the start of the hash chain */
400 SymEntry* E = T->Tab [Hash % T->Size];
402 /* Compare the name */
403 if (strcmp (E->Name, Name) == 0) {
407 /* Not found, next entry in hash chain */
417 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
418 /* Find the symbol with the given name in the table tree that starts with T */
420 /* Get the hash over the name */
421 unsigned Hash = HashStr (Name);
423 /* Check all symbol tables for the symbol */
425 /* Try to find the symbol in this table */
426 SymEntry* E = FindSymInTable (Tab, Name, Hash);
428 /* Bail out if we found it */
433 /* Repeat the search in the next higher lexical level */
443 SymEntry* FindSym (const char* Name)
444 /* Find the symbol with the given name */
446 return FindSymInTree (SymTab, Name);
451 SymEntry* FindGlobalSym (const char* Name)
452 /* Find the symbol with the given name in the global symbol table only */
454 return FindSymInTable (SymTab0, Name, HashStr (Name));
459 SymEntry* FindLocalSym (const char* Name)
460 /* Find the symbol with the given name in the current symbol table only */
462 return FindSymInTable (SymTab, Name, HashStr (Name));
467 SymEntry* FindTagSym (const char* Name)
468 /* Find the symbol with the given name in the tag table */
470 return FindSymInTree (TagTab, Name);
475 SymEntry* FindStructField (const Type* T, const char* Name)
476 /* Find a struct field in the fields list */
480 /* The given type may actually be a pointer to struct */
485 /* Non-structs do not have any struct fields... */
486 if (IsClassStruct (T)) {
490 /* Get a pointer to the struct/union type */
491 const SymEntry* Struct = GetSymEntry (T);
494 /* Get the field symbol table from the struct entry.
495 * Beware: The table may not exist.
497 Tab = Struct->V.S.SymTab;
499 /* Now search in the struct symbol table */
501 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
510 /*****************************************************************************/
511 /* Add stuff to the symbol table */
512 /*****************************************************************************/
516 static void AddSymEntry (SymTable* T, SymEntry* S)
517 /* Add a symbol to a symbol table */
519 /* Get the hash value for the name */
520 unsigned Hash = HashStr (S->Name) % T->Size;
522 /* Insert the symbol into the list of all symbols in this level */
524 T->SymTail->NextSym = S;
526 S->PrevSym = T->SymTail;
528 if (T->SymHead == 0) {
534 /* Insert the symbol into the hash chain */
535 S->NextHash = T->Tab[Hash];
538 /* Tell the symbol in which table it is */
544 SymEntry* AddStructSym (const char* Name, unsigned Size, SymTable* Tab)
545 /* Add a struct/union entry and return it */
547 /* Do we have an entry with this name already? */
548 SymEntry* Entry = FindSymInTable (TagTab, Name, HashStr (Name));
551 /* We do have an entry. This may be a forward, so check it. */
552 if ((Entry->Flags & SC_STRUCT) == 0) {
553 /* Existing symbol is not a struct */
554 Error ("Symbol `%s' is already different kind", Name);
555 } else if (Size > 0 && Entry->V.S.Size > 0) {
556 /* Both structs are definitions. */
557 Error ("Multiple definition for `%s'", Name);
559 /* Define the struct size if it is given */
561 Entry->V.S.SymTab = Tab;
562 Entry->V.S.Size = Size;
568 /* Create a new entry */
569 Entry = NewSymEntry (Name, SC_STRUCT);
571 /* Set the struct data */
572 Entry->V.S.SymTab = Tab;
573 Entry->V.S.Size = Size;
575 /* Add it to the current table */
576 AddSymEntry (TagTab, Entry);
579 /* Return the entry */
585 SymEntry* AddConstSym (const char* Name, const Type* T, unsigned Flags, long Val)
586 /* Add an constant symbol to the symbol table and return it */
588 /* Enums must be inserted in the global symbol table */
589 SymTable* Tab = ((Flags & SC_ENUM) == SC_ENUM)? SymTab0 : SymTab;
591 /* Do we have an entry with this name already? */
592 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
594 if ((Entry->Flags & SC_CONST) != SC_CONST) {
595 Error ("Symbol `%s' is already different kind", Name);
597 Error ("Multiple definition for `%s'", Name);
602 /* Create a new entry */
603 Entry = NewSymEntry (Name, Flags);
605 /* Enum values are ints */
606 Entry->Type = TypeDup (T);
608 /* Set the enum data */
609 Entry->V.ConstVal = Val;
611 /* Add the entry to the symbol table */
612 AddSymEntry (Tab, Entry);
614 /* Return the entry */
620 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
621 /* Add a goto label to the label table */
623 /* Do we have an entry with this name already? */
624 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
627 if (SymIsDef (Entry) && (Flags & SC_DEF) != 0) {
628 /* Trying to define the label more than once */
629 Error ("Label `%s' is defined more than once", Name);
631 Entry->Flags |= Flags;
635 /* Create a new entry */
636 Entry = NewSymEntry (Name, SC_LABEL | Flags);
638 /* Set a new label number */
639 Entry->V.Label = GetLocalLabel ();
641 /* Generate the assembler name of the label */
642 Entry->AsmName = xstrdup (LocalLabelName (Entry->V.Label));
644 /* Add the entry to the label table */
645 AddSymEntry (LabelTab, Entry);
649 /* Return the entry */
655 SymEntry* AddLocalSym (const char* Name, const Type* T, unsigned Flags, int Offs)
656 /* Add a local symbol and return the symbol entry */
658 /* Do we have an entry with this name already? */
659 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
662 /* We have a symbol with this name already */
663 Error ("Multiple definition for `%s'", Name);
667 /* Create a new entry */
668 Entry = NewSymEntry (Name, Flags);
670 /* Set the symbol attributes */
671 Entry->Type = TypeDup (T);
672 if ((Flags & SC_AUTO) == SC_AUTO) {
673 Entry->V.Offs = Offs;
674 } else if ((Flags & SC_REGISTER) == SC_REGISTER) {
675 Entry->V.R.RegOffs = Offs;
676 Entry->V.R.SaveOffs = StackPtr;
677 } else if ((Flags & SC_STATIC) == SC_STATIC) {
678 /* Generate the assembler name from the label number */
679 Entry->V.Label = Offs;
680 Entry->AsmName = xstrdup (LocalLabelName (Entry->V.Label));
681 } else if ((Flags & SC_STRUCTFIELD) == SC_STRUCTFIELD) {
682 Entry->V.Offs = Offs;
684 Internal ("Invalid flags in AddLocalSym: %04X", Flags);
687 /* Add the entry to the symbol table */
688 AddSymEntry (SymTab, Entry);
692 /* Return the entry */
698 SymEntry* AddGlobalSym (const char* Name, const Type* T, unsigned Flags)
699 /* Add an external or global symbol to the symbol table and return the entry */
701 /* There is some special handling for functions, so check if it is one */
702 int IsFunc = IsTypeFunc (T);
704 /* Functions must be inserted in the global symbol table */
705 SymTable* Tab = IsFunc? SymTab0 : SymTab;
707 /* Do we have an entry with this name already? */
708 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
713 /* We have a symbol with this name already */
714 if (Entry->Flags & SC_TYPE) {
715 Error ("Multiple definition for `%s'", Name);
719 /* Get the type string of the existing symbol */
722 /* If we are handling arrays, the old entry or the new entry may be an
723 * incomplete declaration. Accept this, and if the exsting entry is
724 * incomplete, complete it.
726 if (IsTypeArray (T) && IsTypeArray (EType)) {
728 /* Get the array sizes */
729 long Size = GetElementCount (T);
730 long ESize = GetElementCount (EType);
732 if ((Size != UNSPECIFIED && ESize != UNSPECIFIED && Size != ESize) ||
733 TypeCmp (T + 1, EType + 1) < TC_EQUAL) {
734 /* Types not identical: Conflicting types */
735 Error ("Conflicting types for `%s'", Name);
738 /* Check if we have a size in the existing definition */
739 if (ESize == UNSPECIFIED) {
740 /* Existing, size not given, use size from new def */
741 SetElementCount (EType, Size);
746 /* New type must be identical */
747 if (TypeCmp (EType, T) < TC_EQUAL) {
748 Error ("Conflicting types for `%s'", Name);
752 /* In case of a function, use the new type descriptor, since it
753 * contains pointers to the new symbol tables that are needed if
754 * an actual function definition follows.
757 /* Get the function descriptor from the new type */
758 FuncDesc* F = GetFuncDesc (T);
759 /* Use this new function descriptor */
761 SetFuncDesc (EType, F);
765 /* Add the new flags */
766 Entry->Flags |= Flags;
772 /* Create a new entry */
773 Entry = NewSymEntry (Name, Flags);
775 /* Set the symbol attributes */
776 Entry->Type = TypeDup (T);
778 /* If this is a function, set the function descriptor and clear
782 Entry->V.F.Func = GetFuncDesc (Entry->Type);
786 /* Add the assembler name of the symbol */
788 Entry->AsmName = xmalloc (Len + 2);
789 Entry->AsmName[0] = '_';
790 memcpy (Entry->AsmName+1, Name, Len+1);
792 /* Add the entry to the symbol table */
793 AddSymEntry (Tab, Entry);
796 /* Return the entry */
802 /*****************************************************************************/
804 /*****************************************************************************/
808 SymTable* GetSymTab (void)
809 /* Return the current symbol table */
816 SymTable* GetGlobalSymTab (void)
817 /* Return the global symbol table */
824 int SymIsLocal (SymEntry* Sym)
825 /* Return true if the symbol is defined in the highest lexical level */
827 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
832 void MakeZPSym (const char* Name)
833 /* Mark the given symbol as zero page symbol */
835 /* Get the symbol table entry */
836 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
838 /* Mark the symbol as zeropage */
840 Entry->Flags |= SC_ZEROPAGE;
842 Error ("Undefined symbol: `%s'", Name);
848 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
849 /* Write the symbol table to the given file */
852 const SymEntry* Entry;
854 /* Print the header */
856 va_start (ap, Header);
858 Len = vfprintf (F, Header, ap);
862 /* Underline the header */
869 Entry = Tab->SymHead;
871 fprintf (F, "(empty)\n");
874 DumpSymEntry (F, Entry);
875 Entry = Entry->NextSym;
878 fprintf (F, "\n\n\n");
883 void EmitExternals (void)
884 /* Write import/export statements for external symbols */
888 Entry = SymTab->SymHead;
890 unsigned Flags = Entry->Flags;
891 if (Flags & SC_EXTERN) {
892 /* Only defined or referenced externs */
893 if (SymIsRef (Entry) && !SymIsDef (Entry)) {
895 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
896 } else if (SymIsDef (Entry)) {
898 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
901 Entry = Entry->NextSym;