1 /*****************************************************************************/
5 /* Symbol table for the ca65 macroassembler */
9 /* (C) 1998-2012, Ullrich von Bassewitz */
10 /* Roemerstrasse 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 "scopedefs.h"
58 #include "studyexpr.h"
63 /*****************************************************************************/
65 /*****************************************************************************/
69 /* Combined symbol entry flags used within this module */
70 #define SF_UNDEFMASK (SF_REFERENCED | SF_DEFINED | SF_IMPORT)
71 #define SF_UNDEFVAL (SF_REFERENCED)
74 SymTable* CurrentScope = 0; /* Pointer to current symbol table */
75 SymTable* RootScope = 0; /* Root symbol table */
76 static SymTable* LastScope = 0; /* Pointer to last scope in list */
77 static unsigned ScopeCount = 0; /* Number of scopes */
79 /* Symbol table variables */
80 static unsigned ImportCount = 0; /* Counter for import symbols */
81 static unsigned ExportCount = 0; /* Counter for export symbols */
85 /*****************************************************************************/
86 /* Internally used functions */
87 /*****************************************************************************/
91 static int IsDbgSym (const SymEntry* S)
92 /* Return true if this is a debug symbol */
94 if ((S->Flags & (SF_DEFINED | SF_UNUSED)) == SF_DEFINED) {
95 /* Defined symbols are debug symbols if they aren't sizes */
96 return !IsSizeOfSymbol (S);
98 /* Others are debug symbols if they're referenced imports */
99 return ((S->Flags & SF_REFIMP) == SF_REFIMP);
105 static unsigned ScopeTableSize (unsigned Level)
106 /* Get the size of a table for the given lexical level */
117 static SymTable* NewSymTable (SymTable* Parent, const StrBuf* Name)
118 /* Allocate a symbol table on the heap and return it */
120 /* Determine the lexical level and the number of table slots */
121 unsigned Level = Parent? Parent->Level + 1 : 0;
122 unsigned Slots = ScopeTableSize (Level);
124 /* Allocate memory */
125 SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
127 /* Set variables and clear hash table entries */
133 S->Spans = AUTO_COLLECTION_INITIALIZER;
134 S->Id = ScopeCount++;
136 S->AddrSize = ADDR_SIZE_DEFAULT;
137 S->Type = SCOPE_UNDEF;
139 S->TableSlots = Slots;
142 S->Name = GetStrBufId (Name);
147 /* Insert the symbol table into the list of all symbol tables */
148 if (RootScope == 0) {
155 /* Insert the symbol table into the child tree of the parent */
157 SymTable* T = Parent->Childs;
163 /* Choose next entry */
164 int Cmp = SB_Compare (Name, GetStrBuf (T->Name));
172 } else if (Cmp > 0) {
180 /* Duplicate scope name */
181 Internal ("Duplicate scope name: `%m%p'", Name);
187 /* Return the prepared struct */
193 /*****************************************************************************/
195 /*****************************************************************************/
199 void SymEnterLevel (const StrBuf* ScopeName, unsigned char Type,
200 unsigned char AddrSize, SymEntry* ScopeLabel)
201 /* Enter a new lexical level */
203 /* Map a default address size to something real */
204 if (AddrSize == ADDR_SIZE_DEFAULT) {
205 /* Use the segment address size */
206 AddrSize = GetCurrentSegAddrSize ();
209 /* If we have a current scope, search for the given name and create a
210 * new one if it doesn't exist. If this is the root scope, just create it.
214 /* Search for the scope, create a new one */
215 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
217 /* Check if the scope has been defined before */
218 if (CurrentScope->Flags & ST_DEFINED) {
219 Error ("Duplicate scope `%m%p'", ScopeName);
223 CurrentScope = RootScope = NewSymTable (0, ScopeName);
226 /* Mark the scope as defined and set type, address size and owner symbol */
227 CurrentScope->Flags |= ST_DEFINED;
228 CurrentScope->AddrSize = AddrSize;
229 CurrentScope->Type = Type;
230 CurrentScope->Label = ScopeLabel;
232 /* If this is a scope that allows to emit data into segments, add spans
233 * for all currently existing segments. Doing this for just a few scope
234 * types is not really necessary but an optimization, because it does not
235 * allocate memory for useless data (unhandled types here don't occupy
236 * space in any segment).
238 if (CurrentScope->Type <= SCOPE_HAS_DATA) {
239 OpenSpanList (&CurrentScope->Spans);
245 void SymLeaveLevel (void)
246 /* Leave the current lexical level */
248 /* If this is a scope that allows to emit data into segments, close the
251 if (CurrentScope->Type <= SCOPE_HAS_DATA) {
252 CloseSpanList (&CurrentScope->Spans);
255 /* If we have spans, the first one is the segment that was active, when the
256 * scope was opened. Set the size of the scope to the number of data bytes
257 * emitted into this segment. If we have an owner symbol set the size of
260 if (CollCount (&CurrentScope->Spans) > 0) {
261 const Span* S = CollAtUnchecked (&CurrentScope->Spans, 0);
262 unsigned long Size = GetSpanSize (S);
263 DefSizeOfScope (CurrentScope, Size);
264 if (CurrentScope->Label) {
265 DefSizeOfSymbol (CurrentScope->Label, Size);
269 /* Mark the scope as closed */
270 CurrentScope->Flags |= ST_CLOSED;
272 /* Leave the scope */
273 CurrentScope = CurrentScope->Parent;
278 SymTable* SymFindScope (SymTable* Parent, const StrBuf* Name, int AllocNew)
279 /* Find a scope in the given enclosing scope */
281 SymTable** T = &Parent->Childs;
283 int Cmp = SB_Compare (Name, GetStrBuf ((*T)->Name));
286 } else if (Cmp > 0) {
289 /* Found the scope */
294 /* Create a new scope if requested and we didn't find one */
295 if (*T == 0 && AllocNew) {
296 *T = NewSymTable (Parent, Name);
299 /* Return the scope */
305 SymTable* SymFindAnyScope (SymTable* Parent, const StrBuf* Name)
306 /* Find a scope in the given or any of its parent scopes. The function will
307 * never create a new symbol, since this can only be done in one specific
313 /* Search in the current table */
314 Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
316 /* Not found, search in the parent scope, if we have one */
317 Parent = Parent->Parent;
319 } while (Scope == 0 && Parent != 0);
326 SymEntry* SymFindLocal (SymEntry* Parent, const StrBuf* Name, int AllocNew)
327 /* Find a cheap local symbol. If AllocNew is given and the entry is not
328 * found, create a new one. Return the entry found, or the new entry created,
329 * or - in case AllocNew is zero - return 0.
335 /* Local symbol, get the table */
337 /* No last global, so there's no local table */
338 Error ("No preceeding global symbol");
340 return NewSymEntry (Name, SF_LOCAL);
346 /* Search for the symbol if we have a table */
347 Cmp = SymSearchTree (Parent->Locals, Name, &S);
349 /* If we found an entry, return it */
356 /* Otherwise create a new entry, insert and return it */
357 SymEntry* N = NewSymEntry (Name, SF_LOCAL);
358 N->Sym.Entry = Parent;
361 } else if (Cmp < 0) {
369 /* We did not find the entry and AllocNew is false. */
375 SymEntry* SymFind (SymTable* Scope, const StrBuf* Name, int AllocNew)
376 /* Find a new symbol table entry in the given table. If AllocNew is given and
377 * the entry is not found, create a new one. Return the entry found, or the
378 * new entry created, or - in case AllocNew is zero - return 0.
383 /* Global symbol: Get the hash value for the name */
384 unsigned Hash = HashBuf (Name) % Scope->TableSlots;
386 /* Search for the entry */
387 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
389 /* If we found an entry, return it */
391 if (SymTabIsClosed (Scope)) {
392 S->Flags |= SF_FIXED;
399 /* Otherwise create a new entry, insert and return it. If the scope is
400 * already closed, mark the symbol as fixed so it won't be resolved
401 * by a symbol in the enclosing scopes later.
403 SymEntry* N = NewSymEntry (Name, SF_NONE);
404 if (SymTabIsClosed (Scope)) {
405 N->Flags |= SF_FIXED;
409 Scope->Table[Hash] = N;
410 } else if (Cmp < 0) {
415 ++Scope->TableEntries;
420 /* We did not find the entry and AllocNew is false. */
426 SymEntry* SymFindAny (SymTable* Scope, const StrBuf* Name)
427 /* Find a symbol in the given or any of its parent scopes. The function will
428 * never create a new symbol, since this can only be done in one specific
434 /* Search in the current table. Ignore entries flagged with SF_UNUSED,
435 * because for such symbols there is a real entry in one of the parent
438 unsigned Hash = HashBuf (Name) % Scope->TableSlots;
439 if (SymSearchTree (Scope->Table[Hash], Name, &Sym) == 0) {
440 if (Sym->Flags & SF_UNUSED) {
443 /* Found, return it */
450 /* Not found, search in the parent scope, if we have one */
451 Scope = Scope->Parent;
453 } while (Sym == 0 && Scope != 0);
455 /* Return the result */
461 static void SymCheckUndefined (SymEntry* S)
462 /* Handle an undefined symbol */
464 /* Undefined symbol. It may be...
466 * - An undefined symbol in a nested lexical level. If the symbol is not
467 * fixed to this level, search for the symbol in the higher levels and
468 * make the entry a trampoline entry if we find one.
470 * - If the symbol is not found, it is a real undefined symbol. If the
471 * AutoImport flag is set, make it an import. If the AutoImport flag is
472 * not set, it's an error.
475 if ((S->Flags & SF_FIXED) == 0) {
476 SymTable* Tab = GetSymParentScope (S);
478 Sym = SymFind (Tab, GetStrBuf (S->Name), SYM_FIND_EXISTING);
479 if (Sym && (Sym->Flags & (SF_DEFINED | SF_IMPORT)) != 0) {
480 /* We've found a symbol in a higher level that is
481 * either defined in the source, or an import.
485 /* No matching symbol found in this level. Look further */
492 /* We found the symbol in a higher level. Transfer the flags and
493 * address size from the local symbol to that in the higher level
494 * and check for problems.
496 if (S->Flags & SF_EXPORT) {
497 if (Sym->Flags & SF_IMPORT) {
498 /* The symbol is already marked as import */
499 LIError (&S->RefLines,
500 "Symbol `%s' is already an import",
501 GetString (Sym->Name));
503 if (Sym->Flags & SF_EXPORT) {
504 /* The symbol is already marked as an export. */
505 if (Sym->AddrSize > S->ExportSize) {
506 /* We're exporting a symbol smaller than it actually is */
507 LIWarning (&S->DefLines, 1,
508 "Symbol `%m%p' is %s but exported %s",
510 AddrSizeToStr (Sym->AddrSize),
511 AddrSizeToStr (S->ExportSize));
514 /* Mark the symbol as an export */
515 Sym->Flags |= SF_EXPORT;
516 Sym->ExportSize = S->ExportSize;
517 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
518 /* Use the actual size of the symbol */
519 Sym->ExportSize = Sym->AddrSize;
521 if (Sym->AddrSize > Sym->ExportSize) {
522 /* We're exporting a symbol smaller than it actually is */
523 LIWarning (&S->DefLines, 1,
524 "Symbol `%m%p' is %s but exported %s",
526 AddrSizeToStr (Sym->AddrSize),
527 AddrSizeToStr (Sym->ExportSize));
531 if (S->Flags & SF_REFERENCED) {
532 /* Mark as referenced and move the line info */
533 Sym->Flags |= SF_REFERENCED;
534 CollTransfer (&Sym->RefLines, &S->RefLines);
535 CollDeleteAll (&S->RefLines);
538 /* Transfer all expression references */
539 SymTransferExprRefs (S, Sym);
541 /* Mark the symbol as unused removing all other flags */
542 S->Flags = SF_UNUSED;
545 /* The symbol is definitely undefined */
546 if (S->Flags & SF_EXPORT) {
547 /* We will not auto-import an export */
548 LIError (&S->RefLines,
549 "Exported symbol `%m%p' was never defined",
553 /* Mark as import, will be indexed later */
554 S->Flags |= SF_IMPORT;
555 /* Use the address size for code */
556 S->AddrSize = CodeAddrSize;
557 /* Mark point of import */
558 GetFullLineInfo (&S->DefLines);
561 LIError (&S->RefLines,
562 "Symbol `%m%p' is undefined",
572 /* Run through all symbols and check for anomalies and errors */
576 /* Check for open scopes */
577 if (CurrentScope->Parent != 0) {
578 Error ("Local scope was not closed");
581 /* First pass: Walk through all symbols, checking for undefined's and
582 * changing them to trampoline symbols or make them imports.
586 /* If the symbol is marked as global, mark it as export, if it is
587 * already defined, otherwise mark it as import.
589 if (S->Flags & SF_GLOBAL) {
590 if (S->Flags & SF_DEFINED) {
591 SymExportFromGlobal (S);
593 SymImportFromGlobal (S);
597 /* Handle undefined symbols */
598 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
599 /* This is an undefined symbol. Handle it. */
600 SymCheckUndefined (S);
607 /* Second pass: Walk again through the symbols. Count exports and imports
608 * and set address sizes where this has not happened before. Ignore
609 * undefined's, since we handled them in the last pass, and ignore unused
610 * symbols, since we handled them in the last pass, too.
614 if ((S->Flags & SF_UNUSED) == 0 &&
615 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
617 /* Check for defined symbols that were never referenced */
618 if (IsSizeOfSymbol (S)) {
619 /* Remove line infos, we don't need them any longer */
620 ReleaseFullLineInfo (&S->DefLines);
621 ReleaseFullLineInfo (&S->RefLines);
622 } else if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
623 LIWarning (&S->DefLines, 2,
624 "Symbol `%m%p' is defined but never used",
628 /* Assign an index to all imports */
629 if (S->Flags & SF_IMPORT) {
630 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
631 /* Imported symbol is not referenced */
632 LIWarning (&S->DefLines, 2,
633 "Symbol `%m%p' is imported but never used",
636 /* Give the import an id, count imports */
637 S->ImportId = ImportCount++;
641 /* Count exports, assign the export ID */
642 if (S->Flags & SF_EXPORT) {
643 S->ExportId = ExportCount++;
646 /* If the symbol is defined but has an unknown address size,
649 if (SymHasExpr (S) && S->AddrSize == ADDR_SIZE_DEFAULT) {
652 StudyExpr (S->Expr, &ED);
653 S->AddrSize = ED.AddrSize;
654 if (SymIsExport (S)) {
655 if (S->ExportSize == ADDR_SIZE_DEFAULT) {
656 /* Use the real export size */
657 S->ExportSize = S->AddrSize;
658 } else if (S->AddrSize > S->ExportSize) {
659 /* We're exporting a symbol smaller than it actually is */
660 LIWarning (&S->DefLines, 1,
661 "Symbol `%m%p' is %s but exported %s",
663 AddrSizeToStr (S->AddrSize),
664 AddrSizeToStr (S->ExportSize));
670 /* If the address size of the symbol was guessed, check the guess
671 * against the actual address size and print a warning if the two
674 if (S->AddrSize != ADDR_SIZE_DEFAULT) {
675 /* Do we have data for this address size? */
676 if (S->AddrSize <= sizeof (S->GuessedUse) / sizeof (S->GuessedUse[0])) {
677 /* Get the file position where the symbol was used */
678 const FilePos* P = S->GuessedUse[S->AddrSize - 1];
681 "Didn't use %s addressing for `%m%p'",
682 AddrSizeToStr (S->AddrSize),
697 void SymDump (FILE* F)
698 /* Dump the symbol table */
700 SymEntry* S = SymList;
703 /* Ignore unused symbols */
704 if ((S->Flags & SF_UNUSED) != 0) {
706 "%m%-24p %s %s %s %s %s\n",
708 (S->Flags & SF_DEFINED)? "DEF" : "---",
709 (S->Flags & SF_REFERENCED)? "REF" : "---",
710 (S->Flags & SF_IMPORT)? "IMP" : "---",
711 (S->Flags & SF_EXPORT)? "EXP" : "---",
712 AddrSizeToStr (S->AddrSize));
721 void WriteImports (void)
722 /* Write the imports list to the object file */
726 /* Tell the object file module that we're about to start the imports */
729 /* Write the import count to the list */
730 ObjWriteVar (ImportCount);
732 /* Walk throught list and write all valid imports to the file. An import
733 * is considered valid, if it is either referenced, or the forced bit is
734 * set. Otherwise, the import is ignored (no need to link in something
739 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
740 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
742 ObjWrite8 (S->AddrSize);
743 ObjWriteVar (S->Name);
744 WriteLineInfo (&S->DefLines);
745 WriteLineInfo (&S->RefLines);
750 /* Done writing imports */
756 void WriteExports (void)
757 /* Write the exports list to the object file */
762 /* Tell the object file module that we're about to start the exports */
765 /* Write the export count to the list */
766 ObjWriteVar (ExportCount);
768 /* Walk throught list and write all exports to the file */
771 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
773 /* Get the expression bits and the value */
775 unsigned SymFlags = GetSymInfoFlags (S, &ConstVal);
777 /* Check if this symbol has a size. If so, remember it in the
781 SymEntry* SizeSym = FindSizeOfSymbol (S);
782 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
783 SymFlags |= SYM_SIZE;
786 /* Count the number of ConDes types */
787 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
788 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
789 SYM_INC_CONDES_COUNT (SymFlags);
793 /* Write the type and the export size */
794 ObjWriteVar (SymFlags);
795 ObjWrite8 (S->ExportSize);
797 /* Write any ConDes declarations */
798 if (SYM_GET_CONDES_COUNT (SymFlags) > 0) {
799 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
800 unsigned char Prio = S->ConDesPrio[Type];
801 if (Prio != CD_PRIO_NONE) {
802 ObjWrite8 (CD_BUILD (Type, Prio));
808 ObjWriteVar (S->Name);
810 /* Write the value */
811 if (SYM_IS_CONST (SymFlags)) {
813 ObjWrite32 (ConstVal);
815 /* Expression involved */
819 /* If the symbol has a size, write it to the file */
820 if (SYM_HAS_SIZE (SymFlags)) {
824 /* Write the line infos */
825 WriteLineInfo (&S->DefLines);
826 WriteLineInfo (&S->RefLines);
831 /* Done writing exports */
837 void WriteDbgSyms (void)
838 /* Write a list of all symbols to the object file */
843 /* Tell the object file module that we're about to start the debug info */
846 /* Check if debug info is requested */
849 /* Walk through the list, give each symbol an id and count them */
854 S->DebugSymId = Count++;
859 /* Write the symbol count to the list */
862 /* Walk through list and write all symbols to the file. Ignore size
869 /* Get the expression bits and the value */
871 unsigned SymFlags = GetSymInfoFlags (S, &ConstVal);
873 /* Check if this symbol has a size. If so, remember it in the
877 SymEntry* SizeSym = FindSizeOfSymbol (S);
878 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
879 SymFlags |= SYM_SIZE;
883 ObjWriteVar (SymFlags);
885 /* Write the address size */
886 ObjWrite8 (S->AddrSize);
888 /* Write the id of the parent. For normal symbols, this is a
889 * scope (symbol table), for cheap locals, it's a symbol.
891 if (SYM_IS_STD (SymFlags)) {
892 ObjWriteVar (S->Sym.Tab->Id);
894 ObjWriteVar (S->Sym.Entry->DebugSymId);
898 ObjWriteVar (S->Name);
900 /* Write the value */
901 if (SYM_IS_CONST (SymFlags)) {
903 ObjWrite32 (ConstVal);
905 /* Expression involved */
909 /* If the symbol has a size, write it to the file */
910 if (SYM_HAS_SIZE (SymFlags)) {
914 /* If the symbol is an im- or export, write out the ids */
915 if (SYM_IS_IMPORT (SymFlags)) {
916 ObjWriteVar (GetSymImportId (S));
918 if (SYM_IS_EXPORT (SymFlags)) {
919 ObjWriteVar (GetSymExportId (S));
922 /* Write the line infos */
923 WriteLineInfo (&S->DefLines);
924 WriteLineInfo (&S->RefLines);
931 /* No debug symbols */
936 /* Write the high level symbols */
939 /* Done writing debug symbols */
945 void WriteScopes (void)
946 /* Write the scope table to the object file */
948 /* Tell the object file module that we're about to start the scopes */
951 /* We will write scopes only if debug symbols are requested */
954 /* Get head of list */
955 SymTable* S = RootScope;
957 /* Write the scope count to the file */
958 ObjWriteVar (ScopeCount);
960 /* Walk through all scopes and write them to the file */
963 /* Flags for this scope */
966 /* Check if this scope has a size. If so, remember it in the
970 SymEntry* SizeSym = FindSizeOfScope (S);
971 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
975 /* Check if the scope has a label */
977 Flags |= SCOPE_LABELED;
980 /* Scope must be defined */
981 CHECK (S->Type != SCOPE_UNDEF);
983 /* Id of parent scope */
985 ObjWriteVar (S->Parent->Id);
991 ObjWriteVar (S->Level);
997 ObjWriteVar (S->Type);
999 /* Name of the scope */
1000 ObjWriteVar (S->Name);
1002 /* If the scope has a size, write it to the file */
1003 if (SCOPE_HAS_SIZE (Flags)) {
1007 /* If the scope has a label, write its id to the file */
1008 if (SCOPE_HAS_LABEL (Flags)) {
1009 ObjWriteVar (S->Label->DebugSymId);
1012 /* Spans for this scope */
1013 WriteSpanList (&S->Spans);
1021 /* No debug info requested */
1026 /* Done writing the scopes */