1 /*****************************************************************************/
5 /* Symbol table for the ca65 macroassembler */
9 /* (C) 1998-2011, 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 /* Leave the scope */
270 CurrentScope = CurrentScope->Parent;
275 SymTable* SymFindScope (SymTable* Parent, const StrBuf* Name, int AllocNew)
276 /* Find a scope in the given enclosing scope */
278 SymTable** T = &Parent->Childs;
280 int Cmp = SB_Compare (Name, GetStrBuf ((*T)->Name));
283 } else if (Cmp > 0) {
286 /* Found the scope */
291 /* Create a new scope if requested and we didn't find one */
292 if (*T == 0 && AllocNew) {
293 *T = NewSymTable (Parent, Name);
296 /* Return the scope */
302 SymTable* SymFindAnyScope (SymTable* Parent, const StrBuf* Name)
303 /* Find a scope in the given or any of its parent scopes. The function will
304 * never create a new symbol, since this can only be done in one specific
310 /* Search in the current table */
311 Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
313 /* Not found, search in the parent scope, if we have one */
314 Parent = Parent->Parent;
316 } while (Scope == 0 && Parent != 0);
323 SymEntry* SymFindLocal (SymEntry* Parent, const StrBuf* Name, int AllocNew)
324 /* Find a cheap local symbol. If AllocNew is given and the entry is not
325 * found, create a new one. Return the entry found, or the new entry created,
326 * or - in case AllocNew is zero - return 0.
332 /* Local symbol, get the table */
334 /* No last global, so there's no local table */
335 Error ("No preceeding global symbol");
337 return NewSymEntry (Name, SF_LOCAL);
343 /* Search for the symbol if we have a table */
344 Cmp = SymSearchTree (Parent->Locals, Name, &S);
346 /* If we found an entry, return it */
353 /* Otherwise create a new entry, insert and return it */
354 SymEntry* N = NewSymEntry (Name, SF_LOCAL);
355 N->Sym.Entry = Parent;
358 } else if (Cmp < 0) {
366 /* We did not find the entry and AllocNew is false. */
372 SymEntry* SymFind (SymTable* Scope, const StrBuf* Name, int AllocNew)
373 /* Find a new symbol table entry in the given table. If AllocNew is given and
374 * the entry is not found, create a new one. Return the entry found, or the
375 * new entry created, or - in case AllocNew is zero - return 0.
380 /* Global symbol: Get the hash value for the name */
381 unsigned Hash = HashBuf (Name) % Scope->TableSlots;
383 /* Search for the entry */
384 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
386 /* If we found an entry, return it */
393 /* Otherwise create a new entry, insert and return it */
394 SymEntry* N = NewSymEntry (Name, SF_NONE);
397 Scope->Table[Hash] = N;
398 } else if (Cmp < 0) {
403 ++Scope->TableEntries;
408 /* We did not find the entry and AllocNew is false. */
414 SymEntry* SymFindAny (SymTable* Scope, const StrBuf* Name)
415 /* Find a symbol in the given or any of its parent scopes. The function will
416 * never create a new symbol, since this can only be done in one specific
422 /* Search in the current table. Ignore entries flagged with SF_UNUSED,
423 * because for such symbols there is a real entry in one of the parent
426 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
428 if (Sym->Flags & SF_UNUSED) {
431 /* Found, return it */
436 /* Not found, search in the parent scope, if we have one */
437 Scope = Scope->Parent;
439 } while (Sym == 0 && Scope != 0);
441 /* Return the result */
447 static void SymCheckUndefined (SymEntry* S)
448 /* Handle an undefined symbol */
450 /* Undefined symbol. It may be...
452 * - An undefined symbol in a nested lexical level. In this
453 * case, search for the symbol in the higher levels and
454 * make the entry a trampoline entry if we find one.
456 * - If the symbol is not found, it is a real undefined symbol.
457 * If the AutoImport flag is set, make it an import. If the
458 * AutoImport flag is not set, it's an error.
461 SymTable* Tab = GetSymParentScope (S);
463 Sym = SymFind (Tab, GetStrBuf (S->Name), SYM_FIND_EXISTING);
464 if (Sym && (Sym->Flags & (SF_DEFINED | SF_IMPORT)) != 0) {
465 /* We've found a symbol in a higher level that is
466 * either defined in the source, or an import.
470 /* No matching symbol found in this level. Look further */
476 /* We found the symbol in a higher level. Transfer the flags and
477 * address size from the local symbol to that in the higher level
478 * and check for problems.
480 if (S->Flags & SF_EXPORT) {
481 if (Sym->Flags & SF_IMPORT) {
482 /* The symbol is already marked as import */
483 LIError (&S->RefLines,
484 "Symbol `%s' is already an import",
485 GetString (Sym->Name));
487 if (Sym->Flags & SF_EXPORT) {
488 /* The symbol is already marked as an export. */
489 if (Sym->AddrSize > S->ExportSize) {
490 /* We're exporting a symbol smaller than it actually is */
491 LIWarning (&S->DefLines, 1,
492 "Symbol `%m%p' is %s but exported %s",
494 AddrSizeToStr (Sym->AddrSize),
495 AddrSizeToStr (S->ExportSize));
498 /* Mark the symbol as an export */
499 Sym->Flags |= SF_EXPORT;
500 Sym->ExportSize = S->ExportSize;
501 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
502 /* Use the actual size of the symbol */
503 Sym->ExportSize = Sym->AddrSize;
505 if (Sym->AddrSize > Sym->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 (Sym->ExportSize));
515 if (S->Flags & SF_REFERENCED) {
516 /* Mark as referenced and move the line info */
517 Sym->Flags |= SF_REFERENCED;
518 CollTransfer (&Sym->RefLines, &S->RefLines);
519 CollDeleteAll (&S->RefLines);
522 /* Transfer all expression references */
523 SymTransferExprRefs (S, Sym);
525 /* Mark the symbol as unused removing all other flags */
526 S->Flags = SF_UNUSED;
529 /* The symbol is definitely undefined */
530 if (S->Flags & SF_EXPORT) {
531 /* We will not auto-import an export */
532 LIError (&S->RefLines,
533 "Exported symbol `%m%p' was never defined",
537 /* Mark as import, will be indexed later */
538 S->Flags |= SF_IMPORT;
539 /* Use the address size for code */
540 S->AddrSize = CodeAddrSize;
541 /* Mark point of import */
542 GetFullLineInfo (&S->DefLines);
545 LIError (&S->RefLines,
546 "Symbol `%m%p' is undefined",
556 /* Run through all symbols and check for anomalies and errors */
560 /* Check for open scopes */
561 if (CurrentScope->Parent != 0) {
562 Error ("Local scope was not closed");
565 /* First pass: Walk through all symbols, checking for undefined's and
566 * changing them to trampoline symbols or make them imports.
570 /* If the symbol is marked as global, mark it as export, if it is
571 * already defined, otherwise mark it as import.
573 if (S->Flags & SF_GLOBAL) {
574 if (S->Flags & SF_DEFINED) {
575 SymExportFromGlobal (S);
577 SymImportFromGlobal (S);
581 /* Handle undefined symbols */
582 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
583 /* This is an undefined symbol. Handle it. */
584 SymCheckUndefined (S);
591 /* Second pass: Walk again through the symbols. Count exports and imports
592 * and set address sizes where this has not happened before. Ignore
593 * undefined's, since we handled them in the last pass, and ignore unused
594 * symbols, since we handled them in the last pass, too.
598 if ((S->Flags & SF_UNUSED) == 0 &&
599 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
601 /* Check for defined symbols that were never referenced */
602 if (IsSizeOfSymbol (S)) {
603 /* Remove line infos, we don't need them any longer */
604 ReleaseFullLineInfo (&S->DefLines);
605 ReleaseFullLineInfo (&S->RefLines);
606 } else if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
607 LIWarning (&S->DefLines, 2,
608 "Symbol `%m%p' is defined but never used",
612 /* Assign an index to all imports */
613 if (S->Flags & SF_IMPORT) {
614 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
615 /* Imported symbol is not referenced */
616 LIWarning (&S->DefLines, 2,
617 "Symbol `%m%p' is imported but never used",
620 /* Give the import an id, count imports */
621 S->ImportId = ImportCount++;
625 /* Count exports, assign the export ID */
626 if (S->Flags & SF_EXPORT) {
627 S->ExportId = ExportCount++;
630 /* If the symbol is defined but has an unknown address size,
633 if (SymHasExpr (S) && S->AddrSize == ADDR_SIZE_DEFAULT) {
636 StudyExpr (S->Expr, &ED);
637 S->AddrSize = ED.AddrSize;
638 if (SymIsExport (S)) {
639 if (S->ExportSize == ADDR_SIZE_DEFAULT) {
640 /* Use the real export size */
641 S->ExportSize = S->AddrSize;
642 } else if (S->AddrSize > S->ExportSize) {
643 /* We're exporting a symbol smaller than it actually is */
644 LIWarning (&S->DefLines, 1,
645 "Symbol `%m%p' is %s but exported %s",
647 AddrSizeToStr (S->AddrSize),
648 AddrSizeToStr (S->ExportSize));
654 /* If the address size of the symbol was guessed, check the guess
655 * against the actual address size and print a warning if the two
658 if (S->AddrSize != ADDR_SIZE_DEFAULT) {
659 /* Do we have data for this address size? */
660 if (S->AddrSize <= sizeof (S->GuessedUse) / sizeof (S->GuessedUse[0])) {
661 /* Get the file position where the symbol was used */
662 const FilePos* P = S->GuessedUse[S->AddrSize - 1];
665 "Didn't use %s addressing for `%m%p'",
666 AddrSizeToStr (S->AddrSize),
681 void SymDump (FILE* F)
682 /* Dump the symbol table */
684 SymEntry* S = SymList;
687 /* Ignore unused symbols */
688 if ((S->Flags & SF_UNUSED) != 0) {
690 "%m%-24p %s %s %s %s %s\n",
692 (S->Flags & SF_DEFINED)? "DEF" : "---",
693 (S->Flags & SF_REFERENCED)? "REF" : "---",
694 (S->Flags & SF_IMPORT)? "IMP" : "---",
695 (S->Flags & SF_EXPORT)? "EXP" : "---",
696 AddrSizeToStr (S->AddrSize));
705 void WriteImports (void)
706 /* Write the imports list to the object file */
710 /* Tell the object file module that we're about to start the imports */
713 /* Write the import count to the list */
714 ObjWriteVar (ImportCount);
716 /* Walk throught list and write all valid imports to the file. An import
717 * is considered valid, if it is either referenced, or the forced bit is
718 * set. Otherwise, the import is ignored (no need to link in something
723 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
724 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
726 ObjWrite8 (S->AddrSize);
727 ObjWriteVar (S->Name);
728 WriteLineInfo (&S->DefLines);
729 WriteLineInfo (&S->RefLines);
734 /* Done writing imports */
740 void WriteExports (void)
741 /* Write the exports list to the object file */
746 /* Tell the object file module that we're about to start the exports */
749 /* Write the export count to the list */
750 ObjWriteVar (ExportCount);
752 /* Walk throught list and write all exports to the file */
755 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
757 /* Get the expression bits and the value */
759 unsigned SymFlags = GetSymInfoFlags (S, &ConstVal);
761 /* Check if this symbol has a size. If so, remember it in the
765 SymEntry* SizeSym = FindSizeOfSymbol (S);
766 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
767 SymFlags |= SYM_SIZE;
770 /* Count the number of ConDes types */
771 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
772 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
773 SYM_INC_CONDES_COUNT (SymFlags);
777 /* Write the type and the export size */
778 ObjWriteVar (SymFlags);
779 ObjWrite8 (S->ExportSize);
781 /* Write any ConDes declarations */
782 if (SYM_GET_CONDES_COUNT (SymFlags) > 0) {
783 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
784 unsigned char Prio = S->ConDesPrio[Type];
785 if (Prio != CD_PRIO_NONE) {
786 ObjWrite8 (CD_BUILD (Type, Prio));
792 ObjWriteVar (S->Name);
794 /* Write the value */
795 if (SYM_IS_CONST (SymFlags)) {
797 ObjWrite32 (ConstVal);
799 /* Expression involved */
803 /* If the symbol has a size, write it to the file */
804 if (SYM_HAS_SIZE (SymFlags)) {
808 /* Write the line infos */
809 WriteLineInfo (&S->DefLines);
810 WriteLineInfo (&S->RefLines);
815 /* Done writing exports */
821 void WriteDbgSyms (void)
822 /* Write a list of all symbols to the object file */
827 /* Tell the object file module that we're about to start the debug info */
830 /* Check if debug info is requested */
833 /* Walk through the list, give each symbol an id and count them */
838 S->DebugSymId = Count++;
843 /* Write the symbol count to the list */
846 /* Walk through list and write all symbols to the file. Ignore size
853 /* Get the expression bits and the value */
855 unsigned SymFlags = GetSymInfoFlags (S, &ConstVal);
857 /* Check if this symbol has a size. If so, remember it in the
861 SymEntry* SizeSym = FindSizeOfSymbol (S);
862 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
863 SymFlags |= SYM_SIZE;
867 ObjWriteVar (SymFlags);
869 /* Write the address size */
870 ObjWrite8 (S->AddrSize);
872 /* Write the id of the parent. For normal symbols, this is a
873 * scope (symbol table), for cheap locals, it's a symbol.
875 if (SYM_IS_STD (SymFlags)) {
876 ObjWriteVar (S->Sym.Tab->Id);
878 ObjWriteVar (S->Sym.Entry->DebugSymId);
882 ObjWriteVar (S->Name);
884 /* Write the value */
885 if (SYM_IS_CONST (SymFlags)) {
887 ObjWrite32 (ConstVal);
889 /* Expression involved */
893 /* If the symbol has a size, write it to the file */
894 if (SYM_HAS_SIZE (SymFlags)) {
898 /* If the symbol is an im- or export, write out the ids */
899 if (SYM_IS_IMPORT (SymFlags)) {
900 ObjWriteVar (GetSymImportId (S));
902 if (SYM_IS_EXPORT (SymFlags)) {
903 ObjWriteVar (GetSymExportId (S));
906 /* Write the line infos */
907 WriteLineInfo (&S->DefLines);
908 WriteLineInfo (&S->RefLines);
915 /* No debug symbols */
920 /* Write the high level symbols */
923 /* Done writing debug symbols */
929 void WriteScopes (void)
930 /* Write the scope table to the object file */
932 /* Tell the object file module that we're about to start the scopes */
935 /* We will write scopes only if debug symbols are requested */
938 /* Get head of list */
939 SymTable* S = RootScope;
941 /* Write the scope count to the file */
942 ObjWriteVar (ScopeCount);
944 /* Walk through all scopes and write them to the file */
947 /* Flags for this scope */
950 /* Check if this scope has a size. If so, remember it in the
954 SymEntry* SizeSym = FindSizeOfScope (S);
955 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
959 /* Check if the scope has a label */
961 Flags |= SCOPE_LABELED;
964 /* Scope must be defined */
965 CHECK (S->Type != SCOPE_UNDEF);
967 /* Id of parent scope */
969 ObjWriteVar (S->Parent->Id);
975 ObjWriteVar (S->Level);
981 ObjWriteVar (S->Type);
983 /* Name of the scope */
984 ObjWriteVar (S->Name);
986 /* If the scope has a size, write it to the file */
987 if (SCOPE_HAS_SIZE (Flags)) {
991 /* If the scope has a label, write its id to the file */
992 if (SCOPE_HAS_LABEL (Flags)) {
993 ObjWriteVar (S->Label->DebugSymId);
996 /* Spans for this scope */
997 WriteSpanList (&S->Spans);
1005 /* No debug info requested */
1010 /* Done writing the scopes */