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, SymFindAction Action)
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 && (Action & SYM_ALLOC_NEW) != 0) {
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, SymFindAction Action)
327 /* Find a cheap local symbol. If Action contains SYM_ALLOC_NEW and the entry is
328 * not found, create a new one. Return the entry found, or the new entry
329 * created, or - in case Action is SYM_FIND_EXISTING - return 0.
336 /* Local symbol, get the table */
338 /* No last global, so there's no local table */
339 Error ("No preceeding global symbol");
340 if (Action & SYM_ALLOC_NEW) {
341 return NewSymEntry (Name, SF_LOCAL);
347 /* Search for the symbol if we have a table */
348 Cmp = SymSearchTree (Parent->Locals, Name, &S);
350 /* If we found an entry, return it */
355 if (Action & SYM_ALLOC_NEW) {
357 /* Otherwise create a new entry, insert and return it */
358 SymEntry* N = NewSymEntry (Name, SF_LOCAL);
359 N->Sym.Entry = Parent;
362 } else if (Cmp < 0) {
370 /* We did not find the entry and AllocNew is false. */
376 SymEntry* SymFind (SymTable* Scope, const StrBuf* Name, SymFindAction Action)
377 /* Find a new symbol table entry in the given table. If Action contains
378 * SYM_ALLOC_NEW and the entry is not found, create a new one. Return the
379 * entry found, or the new entry created, or - in case Action is
380 * SYM_FIND_EXISTING - return 0.
385 /* Global symbol: Get the hash value for the name */
386 unsigned Hash = HashBuf (Name) % Scope->TableSlots;
388 /* Search for the entry */
389 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
391 /* If we found an entry, return it */
393 if ((Action & SYM_CHECK_ONLY) == 0 && SymTabIsClosed (Scope)) {
394 S->Flags |= SF_FIXED;
399 if (Action & SYM_ALLOC_NEW) {
401 /* Otherwise create a new entry, insert and return it. If the scope is
402 * already closed, mark the symbol as fixed so it won't be resolved
403 * by a symbol in the enclosing scopes later.
405 SymEntry* N = NewSymEntry (Name, SF_NONE);
406 if (SymTabIsClosed (Scope)) {
407 N->Flags |= SF_FIXED;
411 Scope->Table[Hash] = N;
412 } else if (Cmp < 0) {
417 ++Scope->TableEntries;
422 /* We did not find the entry and AllocNew is false. */
428 SymEntry* SymFindAny (SymTable* Scope, const StrBuf* Name)
429 /* Find a symbol in the given or any of its parent scopes. The function will
430 * never create a new symbol, since this can only be done in one specific
434 /* Generate the name hash */
435 unsigned Hash = HashBuf (Name);
437 /* Search for the symbol */
440 /* Search in the current table. Ignore entries flagged with SF_UNUSED,
441 * because for such symbols there is a real entry in one of the parent
444 if (SymSearchTree (Scope->Table[Hash % Scope->TableSlots], Name, &Sym) == 0) {
445 if (Sym->Flags & SF_UNUSED) {
448 /* Found, return it */
455 /* Not found, search in the parent scope, if we have one */
456 Scope = Scope->Parent;
458 } while (Sym == 0 && Scope != 0);
460 /* Return the result */
466 static void SymCheckUndefined (SymEntry* S)
467 /* Handle an undefined symbol */
469 /* Undefined symbol. It may be...
471 * - An undefined symbol in a nested lexical level. If the symbol is not
472 * fixed to this level, search for the symbol in the higher levels and
473 * make the entry a trampoline entry if we find one.
475 * - If the symbol is not found, it is a real undefined symbol. If the
476 * AutoImport flag is set, make it an import. If the AutoImport flag is
477 * not set, it's an error.
480 if ((S->Flags & SF_FIXED) == 0) {
481 SymTable* Tab = GetSymParentScope (S);
483 Sym = SymFind (Tab, GetStrBuf (S->Name), SYM_FIND_EXISTING | SYM_CHECK_ONLY);
484 if (Sym && (Sym->Flags & (SF_DEFINED | SF_IMPORT)) != 0) {
485 /* We've found a symbol in a higher level that is
486 * either defined in the source, or an import.
490 /* No matching symbol found in this level. Look further */
497 /* We found the symbol in a higher level. Transfer the flags and
498 * address size from the local symbol to that in the higher level
499 * and check for problems.
501 if (S->Flags & SF_EXPORT) {
502 if (Sym->Flags & SF_IMPORT) {
503 /* The symbol is already marked as import */
504 LIError (&S->RefLines,
505 "Symbol `%s' is already an import",
506 GetString (Sym->Name));
508 if (Sym->Flags & SF_EXPORT) {
509 /* The symbol is already marked as an export. */
510 if (Sym->AddrSize > S->ExportSize) {
511 /* We're exporting a symbol smaller than it actually is */
512 LIWarning (&S->DefLines, 1,
513 "Symbol `%m%p' is %s but exported %s",
515 AddrSizeToStr (Sym->AddrSize),
516 AddrSizeToStr (S->ExportSize));
519 /* Mark the symbol as an export */
520 Sym->Flags |= SF_EXPORT;
521 Sym->ExportSize = S->ExportSize;
522 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
523 /* Use the actual size of the symbol */
524 Sym->ExportSize = Sym->AddrSize;
526 if (Sym->AddrSize > Sym->ExportSize) {
527 /* We're exporting a symbol smaller than it actually is */
528 LIWarning (&S->DefLines, 1,
529 "Symbol `%m%p' is %s but exported %s",
531 AddrSizeToStr (Sym->AddrSize),
532 AddrSizeToStr (Sym->ExportSize));
536 if (S->Flags & SF_REFERENCED) {
537 /* Mark as referenced and move the line info */
538 Sym->Flags |= SF_REFERENCED;
539 CollTransfer (&Sym->RefLines, &S->RefLines);
540 CollDeleteAll (&S->RefLines);
543 /* Transfer all expression references */
544 SymTransferExprRefs (S, Sym);
546 /* Mark the symbol as unused removing all other flags */
547 S->Flags = SF_UNUSED;
550 /* The symbol is definitely undefined */
551 if (S->Flags & SF_EXPORT) {
552 /* We will not auto-import an export */
553 LIError (&S->RefLines,
554 "Exported symbol `%m%p' was never defined",
558 /* Mark as import, will be indexed later */
559 S->Flags |= SF_IMPORT;
560 /* Use the address size for code */
561 S->AddrSize = CodeAddrSize;
562 /* Mark point of import */
563 GetFullLineInfo (&S->DefLines);
566 LIError (&S->RefLines,
567 "Symbol `%m%p' is undefined",
577 /* Run through all symbols and check for anomalies and errors */
581 /* Check for open scopes */
582 if (CurrentScope->Parent != 0) {
583 Error ("Local scope was not closed");
586 /* First pass: Walk through all symbols, checking for undefined's and
587 * changing them to trampoline symbols or make them imports.
591 /* If the symbol is marked as global, mark it as export, if it is
592 * already defined, otherwise mark it as import.
594 if (S->Flags & SF_GLOBAL) {
595 if (S->Flags & SF_DEFINED) {
596 SymExportFromGlobal (S);
598 SymImportFromGlobal (S);
602 /* Handle undefined symbols */
603 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
604 /* This is an undefined symbol. Handle it. */
605 SymCheckUndefined (S);
612 /* Second pass: Walk again through the symbols. Count exports and imports
613 * and set address sizes where this has not happened before. Ignore
614 * undefined's, since we handled them in the last pass, and ignore unused
615 * symbols, since we handled them in the last pass, too.
619 if ((S->Flags & SF_UNUSED) == 0 &&
620 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
622 /* Check for defined symbols that were never referenced */
623 if (IsSizeOfSymbol (S)) {
624 /* Remove line infos, we don't need them any longer */
625 ReleaseFullLineInfo (&S->DefLines);
626 ReleaseFullLineInfo (&S->RefLines);
627 } else if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
628 LIWarning (&S->DefLines, 2,
629 "Symbol `%m%p' is defined but never used",
633 /* Assign an index to all imports */
634 if (S->Flags & SF_IMPORT) {
635 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
636 /* Imported symbol is not referenced */
637 LIWarning (&S->DefLines, 2,
638 "Symbol `%m%p' is imported but never used",
641 /* Give the import an id, count imports */
642 S->ImportId = ImportCount++;
646 /* Count exports, assign the export ID */
647 if (S->Flags & SF_EXPORT) {
648 S->ExportId = ExportCount++;
651 /* If the symbol is defined but has an unknown address size,
654 if (SymHasExpr (S) && S->AddrSize == ADDR_SIZE_DEFAULT) {
657 StudyExpr (S->Expr, &ED);
658 S->AddrSize = ED.AddrSize;
659 if (SymIsExport (S)) {
660 if (S->ExportSize == ADDR_SIZE_DEFAULT) {
661 /* Use the real export size */
662 S->ExportSize = S->AddrSize;
663 } else if (S->AddrSize > S->ExportSize) {
664 /* We're exporting a symbol smaller than it actually is */
665 LIWarning (&S->DefLines, 1,
666 "Symbol `%m%p' is %s but exported %s",
668 AddrSizeToStr (S->AddrSize),
669 AddrSizeToStr (S->ExportSize));
675 /* If the address size of the symbol was guessed, check the guess
676 * against the actual address size and print a warning if the two
679 if (S->AddrSize != ADDR_SIZE_DEFAULT) {
680 /* Do we have data for this address size? */
681 if (S->AddrSize <= sizeof (S->GuessedUse) / sizeof (S->GuessedUse[0])) {
682 /* Get the file position where the symbol was used */
683 const FilePos* P = S->GuessedUse[S->AddrSize - 1];
686 "Didn't use %s addressing for `%m%p'",
687 AddrSizeToStr (S->AddrSize),
702 void SymDump (FILE* F)
703 /* Dump the symbol table */
705 SymEntry* S = SymList;
708 /* Ignore unused symbols */
709 if ((S->Flags & SF_UNUSED) != 0) {
711 "%m%-24p %s %s %s %s %s\n",
713 (S->Flags & SF_DEFINED)? "DEF" : "---",
714 (S->Flags & SF_REFERENCED)? "REF" : "---",
715 (S->Flags & SF_IMPORT)? "IMP" : "---",
716 (S->Flags & SF_EXPORT)? "EXP" : "---",
717 AddrSizeToStr (S->AddrSize));
726 void WriteImports (void)
727 /* Write the imports list to the object file */
731 /* Tell the object file module that we're about to start the imports */
734 /* Write the import count to the list */
735 ObjWriteVar (ImportCount);
737 /* Walk throught list and write all valid imports to the file. An import
738 * is considered valid, if it is either referenced, or the forced bit is
739 * set. Otherwise, the import is ignored (no need to link in something
744 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
745 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
747 ObjWrite8 (S->AddrSize);
748 ObjWriteVar (S->Name);
749 WriteLineInfo (&S->DefLines);
750 WriteLineInfo (&S->RefLines);
755 /* Done writing imports */
761 void WriteExports (void)
762 /* Write the exports list to the object file */
767 /* Tell the object file module that we're about to start the exports */
770 /* Write the export count to the list */
771 ObjWriteVar (ExportCount);
773 /* Walk throught list and write all exports to the file */
776 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
778 /* Get the expression bits and the value */
780 unsigned SymFlags = GetSymInfoFlags (S, &ConstVal);
782 /* Check if this symbol has a size. If so, remember it in the
786 SymEntry* SizeSym = FindSizeOfSymbol (S);
787 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
788 SymFlags |= SYM_SIZE;
791 /* Count the number of ConDes types */
792 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
793 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
794 SYM_INC_CONDES_COUNT (SymFlags);
798 /* Write the type and the export size */
799 ObjWriteVar (SymFlags);
800 ObjWrite8 (S->ExportSize);
802 /* Write any ConDes declarations */
803 if (SYM_GET_CONDES_COUNT (SymFlags) > 0) {
804 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
805 unsigned char Prio = S->ConDesPrio[Type];
806 if (Prio != CD_PRIO_NONE) {
807 ObjWrite8 (CD_BUILD (Type, Prio));
813 ObjWriteVar (S->Name);
815 /* Write the value */
816 if (SYM_IS_CONST (SymFlags)) {
818 ObjWrite32 (ConstVal);
820 /* Expression involved */
824 /* If the symbol has a size, write it to the file */
825 if (SYM_HAS_SIZE (SymFlags)) {
829 /* Write the line infos */
830 WriteLineInfo (&S->DefLines);
831 WriteLineInfo (&S->RefLines);
836 /* Done writing exports */
842 void WriteDbgSyms (void)
843 /* Write a list of all symbols to the object file */
848 /* Tell the object file module that we're about to start the debug info */
851 /* Check if debug info is requested */
854 /* Walk through the list, give each symbol an id and count them */
859 S->DebugSymId = Count++;
864 /* Write the symbol count to the list */
867 /* Walk through list and write all symbols to the file. Ignore size
874 /* Get the expression bits and the value */
876 unsigned SymFlags = GetSymInfoFlags (S, &ConstVal);
878 /* Check if this symbol has a size. If so, remember it in the
882 SymEntry* SizeSym = FindSizeOfSymbol (S);
883 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
884 SymFlags |= SYM_SIZE;
888 ObjWriteVar (SymFlags);
890 /* Write the address size */
891 ObjWrite8 (S->AddrSize);
893 /* Write the id of the parent. For normal symbols, this is a
894 * scope (symbol table), for cheap locals, it's a symbol.
896 if (SYM_IS_STD (SymFlags)) {
897 ObjWriteVar (S->Sym.Tab->Id);
899 ObjWriteVar (S->Sym.Entry->DebugSymId);
903 ObjWriteVar (S->Name);
905 /* Write the value */
906 if (SYM_IS_CONST (SymFlags)) {
908 ObjWrite32 (ConstVal);
910 /* Expression involved */
914 /* If the symbol has a size, write it to the file */
915 if (SYM_HAS_SIZE (SymFlags)) {
919 /* If the symbol is an im- or export, write out the ids */
920 if (SYM_IS_IMPORT (SymFlags)) {
921 ObjWriteVar (GetSymImportId (S));
923 if (SYM_IS_EXPORT (SymFlags)) {
924 ObjWriteVar (GetSymExportId (S));
927 /* Write the line infos */
928 WriteLineInfo (&S->DefLines);
929 WriteLineInfo (&S->RefLines);
936 /* No debug symbols */
941 /* Write the high level symbols */
944 /* Done writing debug symbols */
950 void WriteScopes (void)
951 /* Write the scope table to the object file */
953 /* Tell the object file module that we're about to start the scopes */
956 /* We will write scopes only if debug symbols are requested */
959 /* Get head of list */
960 SymTable* S = RootScope;
962 /* Write the scope count to the file */
963 ObjWriteVar (ScopeCount);
965 /* Walk through all scopes and write them to the file */
968 /* Flags for this scope */
971 /* Check if this scope has a size. If so, remember it in the
975 SymEntry* SizeSym = FindSizeOfScope (S);
976 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
980 /* Check if the scope has a label */
982 Flags |= SCOPE_LABELED;
985 /* Scope must be defined */
986 CHECK (S->Type != SCOPE_UNDEF);
988 /* Id of parent scope */
990 ObjWriteVar (S->Parent->Id);
996 ObjWriteVar (S->Level);
1002 ObjWriteVar (S->Type);
1004 /* Name of the scope */
1005 ObjWriteVar (S->Name);
1007 /* If the scope has a size, write it to the file */
1008 if (SCOPE_HAS_SIZE (Flags)) {
1012 /* If the scope has a label, write its id to the file */
1013 if (SCOPE_HAS_LABEL (Flags)) {
1014 ObjWriteVar (S->Label->DebugSymId);
1017 /* Spans for this scope */
1018 WriteSpanList (&S->Spans);
1026 /* No debug info requested */
1031 /* Done writing the scopes */