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 /* Predefined lexical levels */
85 #define LEX_LEVEL_GLOBAL 1U
87 /* The current and root symbol tables */
88 static unsigned LexicalLevel = 0; /* For safety checks */
89 static SymTable* SymTab0 = 0;
90 static SymTable* SymTab = 0;
91 static SymTable* TagTab0 = 0;
92 static SymTable* TagTab = 0;
93 static SymTable* LabelTab = 0;
97 /*****************************************************************************/
99 /*****************************************************************************/
103 static SymTable* NewSymTable (unsigned Size)
104 /* Create and return a symbol table for the given lexical level */
108 /* Allocate memory for the table */
109 SymTable* S = xmalloc (sizeof (SymTable) + (Size-1) * sizeof (SymEntry*));
111 /* Initialize the symbol table structure */
117 for (I = 0; I < Size; ++I) {
121 /* Return the symbol table */
127 static void FreeSymTable (SymTable* S)
128 /* Free the given symbo table including all symbols */
130 /* Free all symbols */
131 SymEntry* Sym = S->SymHead;
133 SymEntry* NextSym = Sym->NextSym;
138 /* Free the table itself */
144 /*****************************************************************************/
145 /* Check symbols in a table */
146 /*****************************************************************************/
150 static void CheckSymTable (SymTable* Tab)
151 /* Check a symbol table for open references, unused symbols ... */
153 SymEntry* Entry = Tab->SymHead;
156 /* Get the storage flags for tne entry */
157 unsigned Flags = Entry->Flags;
159 /* Ignore typedef entries */
160 if ((Flags & SC_TYPEDEF) != SC_TYPEDEF) {
162 /* Check if the symbol is one with storage, and it if it was
163 * defined but not used.
165 if (((Flags & SC_AUTO) || (Flags & SC_STATIC)) && (Flags & SC_EXTERN) == 0) {
166 if ((Flags & SC_DEF) && !(Flags & SC_REF)) {
167 if (Flags & SC_PARAM) {
168 Warning ("Parameter `%s' is never used", Entry->Name);
170 Warning ("`%s' is defined but never used", Entry->Name);
175 /* If the entry is a label, check if it was defined in the function */
176 if (Flags & SC_LABEL) {
177 if ((Flags & SC_DEF) == 0) {
178 /* Undefined label */
179 Error ("Undefined label: `%s'", Entry->Name);
180 } else if ((Flags & SC_REF) == 0) {
181 /* Defined but not used */
182 Warning ("`%s' is defined but never used", Entry->Name);
189 Entry = Entry->NextSym;
195 /*****************************************************************************/
196 /* Handling of lexical levels */
197 /*****************************************************************************/
201 void EnterGlobalLevel (void)
202 /* Enter the program global lexical level */
205 PRECONDITION (++LexicalLevel == LEX_LEVEL_GLOBAL);
207 /* Create and assign the symbol table */
208 SymTab0 = SymTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
210 /* Create and assign the tag table */
211 TagTab0 = TagTab = NewSymTable (SYMTAB_SIZE_GLOBAL);
216 void LeaveGlobalLevel (void)
217 /* Leave the program global lexical level */
220 PRECONDITION (LexicalLevel-- == LEX_LEVEL_GLOBAL);
222 /* Check the tables */
223 CheckSymTable (SymTab0);
225 /* Dump the tables if requested */
227 PrintSymTable (SymTab0, stdout, "Global symbol table");
228 PrintSymTable (TagTab0, stdout, "Global tag table");
231 /* Don't delete the symbol and struct tables! */
238 void EnterFunctionLevel (void)
239 /* Enter function lexical level */
243 /* New lexical level */
246 /* Get a new symbol table and make it current */
247 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
251 /* Get a new tag table and make it current */
252 S = NewSymTable (SYMTAB_SIZE_FUNCTION);
256 /* Create and assign a new label table */
257 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
262 void RememberFunctionLevel (struct FuncDesc* F)
263 /* Remember the symbol tables for the level and leave the level without checks */
265 /* Leave the lexical level */
268 /* Remember the tables */
272 /* Don't delete the tables */
273 SymTab = SymTab->PrevTab;
274 TagTab = TagTab->PrevTab;
279 void ReenterFunctionLevel (struct FuncDesc* F)
280 /* Reenter the function lexical level using the existing tables from F */
282 /* New lexical level */
285 /* Make the tables current again */
286 F->SymTab->PrevTab = SymTab;
289 F->TagTab->PrevTab = TagTab;
292 /* Create and assign a new label table */
293 LabelTab = NewSymTable (SYMTAB_SIZE_LABEL);
298 void LeaveFunctionLevel (void)
299 /* Leave function lexical level */
301 /* Leave the lexical level */
304 /* Check the tables */
305 CheckSymTable (SymTab);
306 CheckSymTable (LabelTab);
308 /* Drop the label table if it is empty */
309 if (LabelTab->SymCount == 0) {
310 FreeSymTable (LabelTab);
313 /* Don't delete the tables */
314 SymTab = SymTab->PrevTab;
315 TagTab = TagTab->PrevTab;
321 void EnterBlockLevel (void)
322 /* Enter a nested block in a function */
326 /* New lexical level */
329 /* Get a new symbol table and make it current */
330 S = NewSymTable (SYMTAB_SIZE_BLOCK);
334 /* Get a new tag table and make it current */
335 S = NewSymTable (SYMTAB_SIZE_BLOCK);
342 void LeaveBlockLevel (void)
343 /* Leave a nested block in a function */
345 /* Leave the lexical level */
348 /* Check the tables */
349 CheckSymTable (SymTab);
351 /* Don't delete the tables */
352 SymTab = SymTab->PrevTab;
353 TagTab = TagTab->PrevTab;
358 void EnterStructLevel (void)
359 /* Enter a nested block for a struct definition */
363 /* Get a new symbol table and make it current. Note: Structs and enums
364 * nested in struct scope are NOT local to the struct but visible in the
365 * outside scope. So we will NOT create a new struct or enum table.
367 S = NewSymTable (SYMTAB_SIZE_BLOCK);
374 void LeaveStructLevel (void)
375 /* Leave a nested block for a struct definition */
377 /* Don't delete the table */
378 SymTab = SymTab->PrevTab;
383 /*****************************************************************************/
385 /*****************************************************************************/
389 static SymEntry* FindSymInTable (const SymTable* T, const char* Name, unsigned Hash)
390 /* Search for an entry in one table */
392 /* Get the start of the hash chain */
393 SymEntry* E = T->Tab [Hash % T->Size];
395 /* Compare the name */
396 if (strcmp (E->Name, Name) == 0) {
400 /* Not found, next entry in hash chain */
410 static SymEntry* FindSymInTree (const SymTable* Tab, const char* Name)
411 /* Find the symbol with the given name in the table tree that starts with T */
413 /* Get the hash over the name */
414 unsigned Hash = HashStr (Name);
416 /* Check all symbol tables for the symbol */
418 /* Try to find the symbol in this table */
419 SymEntry* E = FindSymInTable (Tab, Name, Hash);
421 /* Bail out if we found it */
426 /* Repeat the search in the next higher lexical level */
436 SymEntry* FindSym (const char* Name)
437 /* Find the symbol with the given name */
439 return FindSymInTree (SymTab, Name);
444 SymEntry* FindGlobalSym (const char* Name)
445 /* Find the symbol with the given name in the global symbol table only */
447 return FindSymInTable (SymTab0, Name, HashStr (Name));
452 SymEntry* FindLocalSym (const char* Name)
453 /* Find the symbol with the given name in the current symbol table only */
455 return FindSymInTable (SymTab, Name, HashStr (Name));
460 SymEntry* FindTagSym (const char* Name)
461 /* Find the symbol with the given name in the tag table */
463 return FindSymInTree (TagTab, Name);
468 SymEntry* FindStructField (const type* Type, const char* Name)
469 /* Find a struct field in the fields list */
473 /* The given type may actually be a pointer to struct */
474 if (Type[0] == T_PTR) {
478 /* Non-structs do not have any struct fields... */
479 if (IsClassStruct (Type)) {
483 /* Get a pointer to the struct/union type */
484 const SymEntry* Struct = (const SymEntry*) Decode (Type+1);
487 /* Get the field symbol table from the struct entry.
488 * Beware: The table may not exist.
490 Tab = Struct->V.S.SymTab;
492 /* Now search in the struct symbol table */
494 Field = FindSymInTable (Struct->V.S.SymTab, Name, HashStr (Name));
503 /*****************************************************************************/
504 /* Add stuff to the symbol table */
505 /*****************************************************************************/
509 static void AddSymEntry (SymTable* T, SymEntry* S)
510 /* Add a symbol to a symbol table */
512 /* Get the hash value for the name */
513 unsigned Hash = HashStr (S->Name) % T->Size;
515 /* Insert the symbol into the list of all symbols in this level */
517 T->SymTail->NextSym = S;
519 S->PrevSym = T->SymTail;
521 if (T->SymHead == 0) {
527 /* Insert the symbol into the hash chain */
528 S->NextHash = T->Tab[Hash];
531 /* Tell the symbol in which table it is */
537 SymEntry* AddStructSym (const char* Name, unsigned Size, SymTable* Tab)
538 /* Add a struct/union entry and return it */
540 /* Do we have an entry with this name already? */
541 SymEntry* Entry = FindSymInTable (TagTab, Name, HashStr (Name));
544 /* We do have an entry. This may be a forward, so check it. */
545 if ((Entry->Flags & SC_STRUCT) == 0) {
546 /* Existing symbol is not a struct */
547 Error ("Symbol `%s' is already different kind", Name);
548 } else if (Size > 0 && Entry->V.S.Size > 0) {
549 /* Both structs are definitions. */
550 Error ("Multiple definition for `%s'", Name);
552 /* Define the struct size if it is given */
554 Entry->V.S.SymTab = Tab;
555 Entry->V.S.Size = Size;
561 /* Create a new entry */
562 Entry = NewSymEntry (Name, SC_STRUCT);
564 /* Set the struct data */
565 Entry->V.S.SymTab = Tab;
566 Entry->V.S.Size = Size;
568 /* Add it to the current table */
569 AddSymEntry (TagTab, Entry);
572 /* Return the entry */
578 SymEntry* AddConstSym (const char* Name, const type* Type, unsigned Flags, long Val)
579 /* Add an constant symbol to the symbol table and return it */
581 /* Do we have an entry with this name already? */
582 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
584 if ((Entry->Flags & SC_CONST) != SC_CONST) {
585 Error ("Symbol `%s' is already different kind", Name);
587 Error ("Multiple definition for `%s'", Name);
592 /* Create a new entry */
593 Entry = NewSymEntry (Name, Flags);
595 /* Enum values are ints */
596 Entry->Type = TypeDup (Type);
598 /* Set the enum data */
599 Entry->V.ConstVal = Val;
601 /* Add the entry to the symbol table */
602 AddSymEntry (SymTab, Entry);
604 /* Return the entry */
610 SymEntry* AddLabelSym (const char* Name, unsigned Flags)
611 /* Add a goto label to the label table */
613 /* Do we have an entry with this name already? */
614 SymEntry* Entry = FindSymInTable (LabelTab, Name, HashStr (Name));
617 if ((Entry->Flags & SC_DEF) != 0 && (Flags & SC_DEF) != 0) {
618 /* Trying to define the label more than once */
619 Error ("Label `%s' is defined more than once", Name);
621 Entry->Flags |= Flags;
625 /* Create a new entry */
626 Entry = NewSymEntry (Name, SC_LABEL | Flags);
628 /* Set a new label number */
629 Entry->V.Label = GetLocalLabel ();
631 /* Add the entry to the label table */
632 AddSymEntry (LabelTab, Entry);
636 /* Return the entry */
642 SymEntry* AddLocalSym (const char* Name, const type* Type, unsigned Flags, int Offs)
643 /* Add a local symbol and return the symbol entry */
645 /* Do we have an entry with this name already? */
646 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
649 /* We have a symbol with this name already */
650 Error ("Multiple definition for `%s'", 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, const type* Type, unsigned Flags)
673 /* Add an external or global symbol to the symbol table and return the entry */
675 /* There is some special handling for functions, so check if it is one */
676 int IsFunc = IsTypeFunc (Type);
678 /* Functions must be inserted in the global symbol table */
679 SymTable* Tab = IsFunc? SymTab0 : SymTab;
681 /* Do we have an entry with this name already? */
682 SymEntry* Entry = FindSymInTable (Tab, Name, HashStr (Name));
687 /* We have a symbol with this name already */
688 if (Entry->Flags & SC_TYPE) {
689 Error ("Multiple definition for `%s'", Name);
693 /* Get the type string of the existing symbol */
696 /* If we are handling arrays, the old entry or the new entry may be an
697 * incomplete declaration. Accept this, and if the exsting entry is
698 * incomplete, complete it.
700 if (IsTypeArray (Type) && IsTypeArray (EType)) {
702 /* Get the array sizes */
703 unsigned Size = Decode (Type + 1);
704 unsigned ESize = Decode (EType + 1);
706 if ((Size != 0 && ESize != 0 && Size != ESize) ||
707 TypeCmp (Type+DECODE_SIZE+1, EType+DECODE_SIZE+1) < TC_EQUAL) {
708 /* Types not identical: Conflicting types */
709 Error ("Conflicting types for `%s'", Name);
712 /* Check if we have a size in the existing definition */
714 /* Existing, size not given, use size from new def */
715 Encode (EType + 1, Size);
720 /* New type must be identical */
721 if (TypeCmp (EType, Type) < TC_EQUAL) {
722 Error ("Conflicting types for `%s'", Name);
726 /* In case of a function, use the new type descriptor, since it
727 * contains pointers to the new symbol tables that are needed if
728 * an actual function definition follows.
731 /* Get the function descriptor from the new type */
732 FuncDesc* F = GetFuncDesc (Type);
733 /* Use this new function descriptor */
735 EncodePtr (EType+1, F);
739 /* Add the new flags */
740 Entry->Flags |= Flags;
744 /* Create a new entry */
745 Entry = NewSymEntry (Name, Flags);
747 /* Set the symbol attributes */
748 Entry->Type = TypeDup (Type);
750 /* If this is a function, set the function descriptor and clear
754 Entry->V.F.Func = GetFuncDesc (Entry->Type);
758 /* Add the entry to the symbol table */
759 AddSymEntry (Tab, Entry);
762 /* Return the entry */
768 /*****************************************************************************/
770 /*****************************************************************************/
774 SymTable* GetSymTab (void)
775 /* Return the current symbol table */
782 SymTable* GetGlobalSymTab (void)
783 /* Return the global symbol table */
790 int SymIsLocal (SymEntry* Sym)
791 /* Return true if the symbol is defined in the highest lexical level */
793 return (Sym->Owner == SymTab || Sym->Owner == TagTab);
798 void MakeZPSym (const char* Name)
799 /* Mark the given symbol as zero page symbol */
801 /* Get the symbol table entry */
802 SymEntry* Entry = FindSymInTable (SymTab, Name, HashStr (Name));
804 /* Mark the symbol as zeropage */
806 Entry->Flags |= SC_ZEROPAGE;
808 Error ("Undefined symbol: `%s'", Name);
814 void PrintSymTable (const SymTable* Tab, FILE* F, const char* Header, ...)
815 /* Write the symbol table to the given file */
818 const SymEntry* Entry;
820 /* Print the header */
822 va_start (ap, Header);
824 Len = vfprintf (F, Header, ap);
828 /* Underline the header */
835 Entry = Tab->SymHead;
837 fprintf (F, "(empty)\n");
840 DumpSymEntry (F, Entry);
841 Entry = Entry->NextSym;
844 fprintf (F, "\n\n\n");
849 void EmitExternals (void)
850 /* Write import/export statements for external symbols */
854 Entry = SymTab->SymHead;
856 unsigned Flags = Entry->Flags;
857 if (Flags & SC_EXTERN) {
858 /* Only defined or referenced externs */
859 if ((Flags & SC_REF) != 0 && (Flags & SC_DEF) == 0) {
861 g_defimport (Entry->Name, Flags & SC_ZEROPAGE);
862 } else if (Flags & SC_DEF) {
864 g_defexport (Entry->Name, Flags & SC_ZEROPAGE);
867 Entry = Entry->NextSym;