1 /*****************************************************************************/
5 /* Symbol table management for the cc65 C compiler */
9 /* (C) 2000-2001 Ullrich von Bassewitz */
11 /* D-70597 Stuttgart */
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 /*****************************************************************************/
61 /*****************************************************************************/
63 /*****************************************************************************/
67 /* An empty symbol table */
68 SymTable EmptySymTab = {
77 /* Symbol table sizes */
78 #define SYMTAB_SIZE_GLOBAL 211U
79 #define SYMTAB_SIZE_FUNCTION 29U
80 #define SYMTAB_SIZE_BLOCK 13U
81 #define SYMTAB_SIZE_STRUCT 19U
82 #define SYMTAB_SIZE_LABEL 7U
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 (SymIsDef (Entry) && !SymIsRef (Entry)) {
164 if (Flags & SC_PARAM) {
165 Warning ("Parameter `%s' is never used", Entry->Name);
167 Warning ("`%s' is defined but never used", Entry->Name);
172 /* If the entry is a label, check if it was defined in the function */
173 if (Flags & SC_LABEL) {
174 if (!SymIsDef (Entry)) {
175 /* Undefined label */
176 Error ("Undefined label: `%s'", Entry->Name);
177 } else if (!SymIsRef (Entry)) {
178 /* Defined but not used */
179 Warning ("`%s' is defined but never used", Entry->Name);
186 Entry = Entry->NextSym;
192 /*****************************************************************************/
193 /* Handling of lexical levels */
194 /*****************************************************************************/
198 unsigned GetLexicalLevel (void)
199 /* Return the current lexical level */
206 void EnterGlobalLevel (void)
207 /* Enter the program global lexical level */
210 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
212 /* Create and assign the symbol table */
213 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
215 /* Create and assign the tag table */
216 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
221 void LeaveGlobalLevel (void)
222 /* Leave the program global lexical level */
225 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
227 /* Check the tables */
228 CheckSymTable (SymTab0);
230 /* Dump the tables if requested */
232 PrintSymTable (SymTab0, stdout, "Global symbol table");
233 PrintSymTable (TagTab0, stdout, "Global tag table");
236 /* Don't delete the symbol and struct tables! */
243 void EnterFunctionLevel (void)
244 /* Enter function lexical level */
248 /* New lexical level */
251 /* Get a new symbol table and make it current */
252 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
256 /* Get a new tag table and make it current */
257 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
261 /* Create and assign a new label table */
262 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
267 void RememberFunctionLevel (struct FuncDesc* F)
268 /* Remember the symbol tables for the level and leave the level without checks */
270 /* Leave the lexical level */
273 /* Remember the tables */
277 /* Don't delete the tables */
278 SymTab = SymTab->PrevTab;
279 TagTab = TagTab->PrevTab;
284 void ReenterFunctionLevel (struct FuncDesc* F)
285 /* Reenter the function lexical level using the existing tables from F */
287 /* New lexical level */
290 /* Make the tables current again */
291 F->SymTab->PrevTab = SymTab;
294 F->TagTab->PrevTab = TagTab;
297 /* Create and assign a new label table */
298 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
303 void LeaveFunctionLevel (void)
304 /* Leave function lexical level */
306 /* Leave the lexical level */
309 /* Check the tables */
310 CheckSymTable (SymTab);
311 CheckSymTable (LabelTab);
313 /* Drop the label table if it is empty */
314 if (LabelTab->SymCount == 0) {
315 FreeSymTable (LabelTab);
318 /* Don't delete the tables */
319 SymTab = SymTab->PrevTab;
320 TagTab = TagTab->PrevTab;
326 void EnterBlockLevel (void)
327 /* Enter a nested block in a function */
331 /* New lexical level */
334 /* Get a new symbol table and make it current */
335 S = NewSymTable (SYMTAB_SIZE_BLOCK);
339 /* Get a new tag table and make it current */
340 S = NewSymTable (SYMTAB_SIZE_BLOCK);
347 void LeaveBlockLevel (void)
348 /* Leave a nested block in a function */
350 /* Leave the lexical level */
353 /* Check the tables */
354 CheckSymTable (SymTab);
356 /* Don't delete the tables */
357 SymTab = SymTab->PrevTab;
358 TagTab = TagTab->PrevTab;
363 void EnterStructLevel (void)
364 /* Enter a nested block for a struct definition */
368 /* Get a new symbol table and make it current. Note: Structs and enums
369 * nested in struct scope are NOT local to the struct but visible in the
370 * outside scope. So we will NOT create a new struct or enum table.
372 S = NewSymTable (SYMTAB_SIZE_BLOCK);
379 void LeaveStructLevel (void)
380 /* Leave a nested block for a struct definition */
382 /* Don't delete the table */
383 SymTab = SymTab->PrevTab;
388 /*****************************************************************************/
390 /*****************************************************************************/
394 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
395 /* Search for an entry in one table */
397 /* Get the start of the hash chain */
398 SymEntry* E = T->Tab [Hash % T->Size];
400 /* Compare the name */
401 if (strcmp (E->Name, Name) == 0) {
405 /* Not found, next entry in hash chain */
415 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
416 /* Find the symbol with the given name in the table tree that starts with T */
418 /* Get the hash over the name */
419 unsigned Hash = HashStr (Name);
421 /* Check all symbol tables for the symbol */
423 /* Try to find the symbol in this table */
424 SymEntry* E = FindSymInTable (Tab, Name, Hash);
426 /* Bail out if we found it */
431 /* Repeat the search in the next higher lexical level */
441 SymEntry* FindSym (const char* Name)
442 /* Find the symbol with the given name */
444 return FindSymInTree (SymTab, Name);
449 SymEntry* FindGlobalSym (const char* Name)
450 /* Find the symbol with the given name in the global symbol table only */
452 return FindSymInTable (SymTab0, Name, HashStr (Name));
457 SymEntry* FindLocalSym (const char* Name)
458 /* Find the symbol with the given name in the current symbol table only */
460 return FindSymInTable (SymTab, Name, HashStr (Name));
465 SymEntry* FindTagSym (const char* Name)
466 /* Find the symbol with the given name in the tag table */
468 return FindSymInTree (TagTab, Name);
473 SymEntry* FindStructField (const type* Type, const char* Name)
474 /* Find a struct field in the fields list */
478 /* The given type may actually be a pointer to struct */
479 if (Type[0] == T_PTR) {
483 /* Non-structs do not have any struct fields... */
484 if (IsClassStruct (Type)) {
488 /* Get a pointer to the struct/union type */
489 const SymEntry* Struct = (const SymEntry*) Decode (Type+1);
492 /* Get the field symbol table from the struct entry.
493 * Beware: The table may not exist.
495 Tab = Struct->V.S.SymTab;
497 /* Now search in the struct symbol table */
499 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
508 /*****************************************************************************/
509 /* Add stuff to the symbol table */
510 /*****************************************************************************/
514 static void AddSymEntry (SymTable* T, SymEntry* S)
515 /* Add a symbol to a symbol table */
517 /* Get the hash value for the name */
518 unsigned Hash = HashStr (S->Name) % T->Size;
520 /* Insert the symbol into the list of all symbols in this level */
522 T->SymTail->NextSym = S;
524 S->PrevSym = T->SymTail;
526 if (T->SymHead == 0) {
532 /* Insert the symbol into the hash chain */
533 S->NextHash = T->Tab[Hash];
536 /* Tell the symbol in which table it is */
542 SymEntry* AddStructSym (const char* Name, unsigned Size, SymTable* Tab)
543 /* Add a struct/union entry and return it */
545 /* Do we have an entry with this name already? */
546 SymEntry* Entry = FindSymInTable (TagTab, Name, HashStr (Name));
549 /* We do have an entry. This may be a forward, so check it. */
550 if ((Entry->Flags & SC_STRUCT) == 0) {
551 /* Existing symbol is not a struct */
552 Error ("Symbol `%s' is already different kind", Name);
553 } else if (Size > 0 && Entry->V.S.Size > 0) {
554 /* Both structs are definitions. */
555 Error ("Multiple definition for `%s'", Name);
557 /* Define the struct size if it is given */
559 Entry->V.S.SymTab = Tab;
560 Entry->V.S.Size = Size;
566 /* Create a new entry */
567 Entry = NewSymEntry (Name, SC_STRUCT);
569 /* Set the struct data */
570 Entry->V.S.SymTab = Tab;
571 Entry->V.S.Size = Size;
573 /* Add it to the current table */
574 AddSymEntry (TagTab, Entry);
577 /* Return the entry */
583 SymEntry* AddConstSym (const char* Name, const type* Type, unsigned Flags, long Val)
584 /* Add an constant symbol to the symbol table and return it */
586 /* Do we have an entry with this name already? */
587 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
589 if ((Entry->Flags & SC_CONST) != SC_CONST) {
590 Error ("Symbol `%s' is already different kind", Name);
592 Error ("Multiple definition for `%s'", Name);
597 /* Create a new entry */
598 Entry = NewSymEntry (Name, Flags);
600 /* Enum values are ints */
601 Entry->Type = TypeDup (Type);
603 /* Set the enum data */
604 Entry->V.ConstVal = Val;
606 /* Add the entry to the symbol table */
607 AddSymEntry (SymTab, Entry);
609 /* Return the entry */
615 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
616 /* Add a goto label to the label table */
618 /* Do we have an entry with this name already? */
619 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
622 if (SymIsDef (Entry) && (Flags & SC_DEF) != 0) {
623 /* Trying to define the label more than once */
624 Error ("Label `%s' is defined more than once", Name);
626 Entry->Flags |= Flags;
630 /* Create a new entry */
631 Entry = NewSymEntry (Name, SC_LABEL | Flags);
633 /* Set a new label number */
634 Entry->V.Label = GetLocalLabel ();
636 /* Add the entry to the label table */
637 AddSymEntry (LabelTab, Entry);
641 /* Return the entry */
647 SymEntry* AddLocalSym (const char* Name, const type* Type, unsigned Flags, int Offs)
648 /* Add a local symbol and return the symbol entry */
650 /* Do we have an entry with this name already? */
651 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
654 /* We have a symbol with this name already */
655 Error ("Multiple definition for `%s'", Name);
659 /* Create a new entry */
660 Entry = NewSymEntry (Name, Flags);
662 /* Set the symbol attributes */
663 Entry->Type = TypeDup (Type);
664 if ((Flags & SC_AUTO) == SC_AUTO) {
665 Entry->V.Offs = Offs;
666 } else if ((Flags & SC_REGISTER) == SC_REGISTER) {
667 Entry->V.R.RegOffs = Offs;
668 Entry->V.R.SaveOffs = oursp; /* ### Cleaner! */
669 } else if ((Flags & SC_STATIC) == SC_STATIC) {
670 Entry->V.Label = Offs;
671 } else if ((Flags & SC_STRUCTFIELD) == SC_STRUCTFIELD) {
672 Entry->V.Offs = Offs;
674 Internal ("Invalid flags in AddLocalSym: %04X", Flags);
677 /* Add the entry to the symbol table */
678 AddSymEntry (SymTab, Entry);
682 /* Return the entry */
688 SymEntry* AddGlobalSym (const char* Name, const type* Type, unsigned Flags)
689 /* Add an external or global symbol to the symbol table and return the entry */
691 /* There is some special handling for functions, so check if it is one */
692 int IsFunc = IsTypeFunc (Type);
694 /* Functions must be inserted in the global symbol table */
695 SymTable* Tab = IsFunc? SymTab0 : SymTab;
697 /* Do we have an entry with this name already? */
698 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
703 /* We have a symbol with this name already */
704 if (Entry->Flags & SC_TYPE) {
705 Error ("Multiple definition for `%s'", Name);
709 /* Get the type string of the existing symbol */
712 /* If we are handling arrays, the old entry or the new entry may be an
713 * incomplete declaration. Accept this, and if the exsting entry is
714 * incomplete, complete it.
716 if (IsTypeArray (Type) && IsTypeArray (EType)) {
718 /* Get the array sizes */
719 unsigned Size = Decode (Type + 1);
720 unsigned ESize = Decode (EType + 1);
722 if ((Size != 0 && ESize != 0 && Size != ESize) ||
723 TypeCmp (Type+DECODE_SIZE+1, EType+DECODE_SIZE+1) < TC_EQUAL) {
724 /* Types not identical: Conflicting types */
725 Error ("Conflicting types for `%s'", Name);
728 /* Check if we have a size in the existing definition */
730 /* Existing, size not given, use size from new def */
731 Encode (EType + 1, Size);
736 /* New type must be identical */
737 if (TypeCmp (EType, Type) < TC_EQUAL) {
738 Error ("Conflicting types for `%s'", Name);
742 /* In case of a function, use the new type descriptor, since it
743 * contains pointers to the new symbol tables that are needed if
744 * an actual function definition follows.
747 /* Get the function descriptor from the new type */
748 FuncDesc* F = GetFuncDesc (Type);
749 /* Use this new function descriptor */
751 EncodePtr (EType+1, F);
755 /* Add the new flags */
756 Entry->Flags |= Flags;
760 /* Create a new entry */
761 Entry = NewSymEntry (Name, Flags);
763 /* Set the symbol attributes */
764 Entry->Type = TypeDup (Type);
766 /* If this is a function, set the function descriptor and clear
770 Entry->V.F.Func = GetFuncDesc (Entry->Type);
774 /* Add the entry to the symbol table */
775 AddSymEntry (Tab, Entry);
778 /* Return the entry */
784 /*****************************************************************************/
786 /*****************************************************************************/
790 SymTable* GetSymTab (void)
791 /* Return the current symbol table */
798 SymTable* GetGlobalSymTab (void)
799 /* Return the global symbol table */
806 int SymIsLocal (SymEntry* Sym)
807 /* Return true if the symbol is defined in the highest lexical level */
809 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
814 void MakeZPSym (const char* Name)
815 /* Mark the given symbol as zero page symbol */
817 /* Get the symbol table entry */
818 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
820 /* Mark the symbol as zeropage */
822 Entry->Flags |= SC_ZEROPAGE;
824 Error ("Undefined symbol: `%s'", Name);
830 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
831 /* Write the symbol table to the given file */
834 const SymEntry* Entry;
836 /* Print the header */
838 va_start (ap, Header);
840 Len = vfprintf (F, Header, ap);
844 /* Underline the header */
851 Entry = Tab->SymHead;
853 fprintf (F, "(empty)\n");
856 DumpSymEntry (F, Entry);
857 Entry = Entry->NextSym;
860 fprintf (F, "\n\n\n");
865 void EmitExternals (void)
866 /* Write import/export statements for external symbols */
870 Entry = SymTab->SymHead;
872 unsigned Flags = Entry->Flags;
873 if (Flags & SC_EXTERN) {
874 /* Only defined or referenced externs */
875 if (SymIsRef (Entry) && !SymIsDef (Entry)) {
877 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
878 } else if (SymIsDef (Entry)) {
880 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
883 Entry = Entry->NextSym;