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"
56 #include "studyexpr.h"
61 /*****************************************************************************/
63 /*****************************************************************************/
67 /* Combined symbol entry flags used within this module */
68 #define SF_UNDEFMASK (SF_REFERENCED | SF_DEFINED | SF_IMPORT)
69 #define SF_UNDEFVAL (SF_REFERENCED)
70 #define SF_DBGINFOMASK (SF_UNUSED | SF_DEFINED | SF_IMPORT)
71 #define SF_DBGINFOVAL (SF_DEFINED)
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 unsigned ScopeTableSize (unsigned Level)
92 /* Get the size of a table for the given lexical level */
103 static SymTable* NewSymTable (SymTable* Parent, const StrBuf* Name)
104 /* Allocate a symbol table on the heap and return it */
106 /* Determine the lexical level and the number of table slots */
107 unsigned Level = Parent? Parent->Level + 1 : 0;
108 unsigned Slots = ScopeTableSize (Level);
110 /* Allocate memory */
111 SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
113 /* Set variables and clear hash table entries */
118 S->SegRanges = AUTO_COLLECTION_INITIALIZER;
120 S->AddrSize = ADDR_SIZE_DEFAULT;
121 S->Type = SCOPETYPE_UNDEF;
123 S->TableSlots = Slots;
126 S->Name = GetStrBufId (Name);
131 /* Insert the symbol table into the list of all symbol tables and maintain
132 * a unqiue id for each scope. Count the number of scopes.
135 if (RootScope == 0) {
139 S->Id = LastScope->Id + 1;
144 /* Insert the symbol table into the child tree of the parent */
146 SymTable* T = Parent->Childs;
152 /* Choose next entry */
153 int Cmp = SB_Compare (Name, GetStrBuf (T->Name));
161 } else if (Cmp > 0) {
169 /* Duplicate scope name */
170 Internal ("Duplicate scope name: `%m%p'", Name);
176 /* Return the prepared struct */
182 /*****************************************************************************/
184 /*****************************************************************************/
188 void SymEnterLevel (const StrBuf* ScopeName, unsigned char Type,
189 unsigned char AddrSize, SymEntry* OwnerSym)
190 /* Enter a new lexical level */
192 /* Map a default address size to something real */
193 if (AddrSize == ADDR_SIZE_DEFAULT) {
194 /* Use the segment address size */
195 AddrSize = GetCurrentSegAddrSize ();
198 /* If we have a current scope, search for the given name and create a
199 * new one if it doesn't exist. If this is the root scope, just create it.
203 /* Search for the scope, create a new one */
204 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
206 /* Check if the scope has been defined before */
207 if (CurrentScope->Flags & ST_DEFINED) {
208 Error ("Duplicate scope `%m%p'", ScopeName);
212 CurrentScope = RootScope = NewSymTable (0, ScopeName);
215 /* Mark the scope as defined and set type, address size and owner symbol */
216 CurrentScope->Flags |= ST_DEFINED;
217 CurrentScope->AddrSize = AddrSize;
218 CurrentScope->Type = Type;
219 CurrentScope->OwnerSym = OwnerSym;
221 /* If this is a scope that allows to emit data into segments, add segment
222 * ranges for all currently existing segments. Doing this for just a few
223 * scope types is not really necessary but an optimization, because it
224 * does not allocate memory for useless data (unhandled types here don't
225 * occupy space in any segment).
227 if (CurrentScope->Type <= SCOPETYPE_HAS_DATA) {
228 AddSegRanges (&CurrentScope->SegRanges);
234 void SymLeaveLevel (void)
235 /* Leave the current lexical level */
237 /* Close the segment ranges. We don't care about the scope type here,
238 * since types without segment ranges will just have an empty list.
240 CloseSegRanges (&CurrentScope->SegRanges);
242 /* If we have segment ranges, the first one is the segment that was
243 * active, when the scope was opened. Set the size of the scope to the
244 * number of data bytes emitted into this segment. If we have an owner
245 * symbol set the size of this symbol, too.
247 if (CollCount (&CurrentScope->SegRanges) > 0) {
248 const SegRange* R = CollAtUnchecked (&CurrentScope->SegRanges, 0);
249 unsigned long Size = GetSegRangeSize (R);
250 DefSizeOfScope (CurrentScope, Size);
251 if (CurrentScope->OwnerSym) {
252 DefSizeOfSymbol (CurrentScope->OwnerSym, Size);
256 /* Leave the scope */
257 CurrentScope = CurrentScope->Parent;
262 SymTable* SymFindScope (SymTable* Parent, const StrBuf* Name, int AllocNew)
263 /* Find a scope in the given enclosing scope */
265 SymTable** T = &Parent->Childs;
267 int Cmp = SB_Compare (Name, GetStrBuf ((*T)->Name));
270 } else if (Cmp > 0) {
273 /* Found the scope */
278 /* Create a new scope if requested and we didn't find one */
279 if (*T == 0 && AllocNew) {
280 *T = NewSymTable (Parent, Name);
283 /* Return the scope */
289 SymTable* SymFindAnyScope (SymTable* Parent, const StrBuf* Name)
290 /* Find a scope in the given or any of its parent scopes. The function will
291 * never create a new symbol, since this can only be done in one specific
297 /* Search in the current table */
298 Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
300 /* Not found, search in the parent scope, if we have one */
301 Parent = Parent->Parent;
303 } while (Scope == 0 && Parent != 0);
310 SymEntry* SymFindLocal (SymEntry* Parent, const StrBuf* Name, int AllocNew)
311 /* Find a cheap local symbol. If AllocNew is given and the entry is not
312 * found, create a new one. Return the entry found, or the new entry created,
313 * or - in case AllocNew is zero - return 0.
319 /* Local symbol, get the table */
321 /* No last global, so there's no local table */
322 Error ("No preceeding global symbol");
324 return NewSymEntry (Name, SF_LOCAL);
330 /* Search for the symbol if we have a table */
331 Cmp = SymSearchTree (Parent->Locals, Name, &S);
333 /* If we found an entry, return it */
340 /* Otherwise create a new entry, insert and return it */
341 SymEntry* N = NewSymEntry (Name, SF_LOCAL);
342 N->Sym.Entry = Parent;
345 } else if (Cmp < 0) {
353 /* We did not find the entry and AllocNew is false. */
359 SymEntry* SymFind (SymTable* Scope, const StrBuf* Name, int AllocNew)
360 /* Find a new symbol table entry in the given table. If AllocNew is given and
361 * the entry is not found, create a new one. Return the entry found, or the
362 * new entry created, or - in case AllocNew is zero - return 0.
367 /* Global symbol: Get the hash value for the name */
368 unsigned Hash = HashBuf (Name) % Scope->TableSlots;
370 /* Search for the entry */
371 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
373 /* If we found an entry, return it */
380 /* Otherwise create a new entry, insert and return it */
381 SymEntry* N = NewSymEntry (Name, SF_NONE);
384 Scope->Table[Hash] = N;
385 } else if (Cmp < 0) {
390 ++Scope->TableEntries;
395 /* We did not find the entry and AllocNew is false. */
401 SymEntry* SymFindAny (SymTable* Scope, const StrBuf* Name)
402 /* Find a symbol in the given or any of its parent scopes. The function will
403 * never create a new symbol, since this can only be done in one specific
409 /* Search in the current table */
410 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
412 /* Found, return it */
416 /* Not found, search in the parent scope, if we have one */
417 Scope = Scope->Parent;
419 } while (Sym == 0 && Scope != 0);
421 /* Return the result */
427 unsigned char GetCurrentSymTabType ()
428 /* Return the type of the current symbol table */
430 CHECK (CurrentScope != 0);
431 return CurrentScope->Type;
436 static void SymCheckUndefined (SymEntry* S)
437 /* Handle an undefined symbol */
439 /* Undefined symbol. It may be...
441 * - An undefined symbol in a nested lexical level. In this
442 * case, search for the symbol in the higher levels and
443 * make the entry a trampoline entry if we find one.
445 * - If the symbol is not found, it is a real undefined symbol.
446 * If the AutoImport flag is set, make it an import. If the
447 * AutoImport flag is not set, it's an error.
450 SymTable* Tab = GetSymParentScope (S);
452 Sym = SymFind (Tab, GetStrBuf (S->Name), SYM_FIND_EXISTING);
453 if (Sym && (Sym->Flags & (SF_DEFINED | SF_IMPORT)) != 0) {
454 /* We've found a symbol in a higher level that is
455 * either defined in the source, or an import.
459 /* No matching symbol found in this level. Look further */
465 /* We found the symbol in a higher level. Transfer the flags and
466 * address size from the local symbol to that in the higher level
467 * and check for problems.
469 if (S->Flags & SF_EXPORT) {
470 if (Sym->Flags & SF_IMPORT) {
471 /* The symbol is already marked as import */
472 LIError (&S->LineInfos,
473 "Symbol `%s' is already an import",
474 GetString (Sym->Name));
476 if (Sym->Flags & SF_EXPORT) {
477 /* The symbol is already marked as an export. */
478 if (Sym->AddrSize > S->ExportSize) {
479 /* We're exporting a symbol smaller than it actually is */
480 LIWarning (&S->LineInfos, 1,
481 "Symbol `%m%p' is %s but exported %s",
483 AddrSizeToStr (Sym->AddrSize),
484 AddrSizeToStr (S->ExportSize));
487 /* Mark the symbol as an export */
488 Sym->Flags |= SF_EXPORT;
489 Sym->ExportSize = S->ExportSize;
490 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
491 /* Use the actual size of the symbol */
492 Sym->ExportSize = Sym->AddrSize;
494 if (Sym->AddrSize > Sym->ExportSize) {
495 /* We're exporting a symbol smaller than it actually is */
496 LIWarning (&S->LineInfos, 1,
497 "Symbol `%m%p' is %s but exported %s",
499 AddrSizeToStr (Sym->AddrSize),
500 AddrSizeToStr (Sym->ExportSize));
504 Sym->Flags |= (S->Flags & SF_REFERENCED);
506 /* Transfer all expression references */
507 SymTransferExprRefs (S, Sym);
509 /* Mark the symbol as unused removing all other flags */
510 S->Flags = SF_UNUSED;
513 /* The symbol is definitely undefined */
514 if (S->Flags & SF_EXPORT) {
515 /* We will not auto-import an export */
516 LIError (&S->LineInfos,
517 "Exported symbol `%m%p' was never defined",
521 /* Mark as import, will be indexed later */
522 S->Flags |= SF_IMPORT;
523 /* Use the address size for code */
524 S->AddrSize = CodeAddrSize;
527 LIError (&S->LineInfos,
528 "Symbol `%m%p' is undefined",
538 /* Run through all symbols and check for anomalies and errors */
542 /* Check for open scopes */
543 if (CurrentScope->Parent != 0) {
544 Error ("Local scope was not closed");
547 /* First pass: Walk through all symbols, checking for undefined's and
548 * changing them to trampoline symbols or make them imports.
552 /* If the symbol is marked as global, mark it as export, if it is
553 * already defined, otherwise mark it as import.
555 if (S->Flags & SF_GLOBAL) {
556 if (S->Flags & SF_DEFINED) {
557 SymExportFromGlobal (S);
559 SymImportFromGlobal (S);
563 /* Handle undefined symbols */
564 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
565 /* This is an undefined symbol. Handle it. */
566 SymCheckUndefined (S);
573 /* Second pass: Walk again through the symbols. Count exports and imports
574 * and set address sizes where this has not happened before. Ignore
575 * undefined's, since we handled them in the last pass, and ignore unused
576 * symbols, since we handled them in the last pass, too.
580 if ((S->Flags & SF_UNUSED) == 0 &&
581 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
583 /* Check for defined symbols that were never referenced */
584 if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
585 const StrBuf* Name = GetStrBuf (S->Name);
586 if (SB_At (Name, 0) != '.') { /* Ignore internals */
587 LIWarning (&S->LineInfos, 2,
588 "Symbol `%m%p' is defined but never used",
593 /* Assign an index to all imports */
594 if (S->Flags & SF_IMPORT) {
595 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
596 /* Imported symbol is not referenced */
597 LIWarning (&S->LineInfos, 2,
598 "Symbol `%m%p' is imported but never used",
601 /* Give the import an id, count imports */
602 S->ImportId = ImportCount++;
607 if (S->Flags & SF_EXPORT) {
611 /* If the symbol is defined but has an unknown address size,
614 if (SymHasExpr (S) && S->AddrSize == ADDR_SIZE_DEFAULT) {
617 StudyExpr (S->Expr, &ED);
618 S->AddrSize = ED.AddrSize;
619 if (SymIsExport (S)) {
620 if (S->ExportSize == ADDR_SIZE_DEFAULT) {
621 /* Use the real export size */
622 S->ExportSize = S->AddrSize;
623 } else if (S->AddrSize > S->ExportSize) {
624 /* We're exporting a symbol smaller than it actually is */
625 LIWarning (&S->LineInfos, 1,
626 "Symbol `%m%p' is %s but exported %s",
628 AddrSizeToStr (S->AddrSize),
629 AddrSizeToStr (S->ExportSize));
635 /* If the address size of the symbol was guessed, check the guess
636 * against the actual address size and print a warning if the two
639 if (S->AddrSize != ADDR_SIZE_DEFAULT) {
640 /* Do we have data for this address size? */
641 if (S->AddrSize <= sizeof (S->GuessedUse) / sizeof (S->GuessedUse[0])) {
642 /* Get the file position where the symbol was used */
643 const FilePos* P = S->GuessedUse[S->AddrSize - 1];
646 "Didn't use %s addressing for `%m%p'",
647 AddrSizeToStr (S->AddrSize),
662 void SymDump (FILE* F)
663 /* Dump the symbol table */
665 SymEntry* S = SymList;
668 /* Ignore unused symbols */
669 if ((S->Flags & SF_UNUSED) != 0) {
671 "%m%-24p %s %s %s %s %s\n",
673 (S->Flags & SF_DEFINED)? "DEF" : "---",
674 (S->Flags & SF_REFERENCED)? "REF" : "---",
675 (S->Flags & SF_IMPORT)? "IMP" : "---",
676 (S->Flags & SF_EXPORT)? "EXP" : "---",
677 AddrSizeToStr (S->AddrSize));
686 void WriteImports (void)
687 /* Write the imports list to the object file */
691 /* Tell the object file module that we're about to start the imports */
694 /* Write the import count to the list */
695 ObjWriteVar (ImportCount);
697 /* Walk throught list and write all valid imports to the file. An import
698 * is considered valid, if it is either referenced, or the forced bit is
699 * set. Otherwise, the import is ignored (no need to link in something
704 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
705 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
707 ObjWrite8 (S->AddrSize);
708 ObjWriteVar (S->Name);
709 WriteLineInfo (&S->LineInfos);
714 /* Done writing imports */
720 void WriteExports (void)
721 /* Write the exports list to the object file */
726 /* Tell the object file module that we're about to start the exports */
729 /* Write the export count to the list */
730 ObjWriteVar (ExportCount);
732 /* Walk throught list and write all exports to the file */
735 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
737 /* Get the expression bits and the value */
739 unsigned ExprMask = GetSymInfoFlags (S, &ConstVal);
741 /* Check if this symbol has a size. If so, remember it in the
745 SymEntry* SizeSym = FindSizeOfSymbol (S);
746 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
747 ExprMask |= SYM_SIZE;
750 /* Count the number of ConDes types */
751 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
752 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
753 SYM_INC_CONDES_COUNT (ExprMask);
757 /* Write the type and the export size */
758 ObjWriteVar (ExprMask);
759 ObjWrite8 (S->ExportSize);
761 /* Write any ConDes declarations */
762 if (SYM_GET_CONDES_COUNT (ExprMask) > 0) {
763 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
764 unsigned char Prio = S->ConDesPrio[Type];
765 if (Prio != CD_PRIO_NONE) {
766 ObjWrite8 (CD_BUILD (Type, Prio));
772 ObjWriteVar (S->Name);
774 /* Write the value */
775 if (SYM_IS_CONST (ExprMask)) {
777 ObjWrite32 (ConstVal);
779 /* Expression involved */
783 /* If the symbol has a size, write it to the file */
784 if (SYM_HAS_SIZE (ExprMask)) {
788 /* Write the line infos */
789 WriteLineInfo (&S->LineInfos);
794 /* Done writing exports */
800 void WriteDbgSyms (void)
801 /* Write a list of all symbols to the object file */
806 /* Tell the object file module that we're about to start the debug info */
809 /* Check if debug info is requested */
812 /* Walk through the list, give each symbol an id and count them */
816 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL &&
817 !IsSizeOfSymbol (S)) {
818 S->DebugSymId = Count++;
823 /* Write the symbol count to the list */
826 /* Walk through list and write all symbols to the file. Ignore size
831 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL &&
832 !IsSizeOfSymbol (S)) {
834 /* Get the expression bits and the value */
836 unsigned ExprMask = GetSymInfoFlags (S, &ConstVal);
838 /* Check if this symbol has a size. If so, remember it in the
842 SymEntry* SizeSym = FindSizeOfSymbol (S);
843 if (SizeSym != 0 && SymIsConst (SizeSym, &Size)) {
844 ExprMask |= SYM_SIZE;
848 ObjWriteVar (ExprMask);
850 /* Write the address size */
851 ObjWrite8 (S->AddrSize);
853 /* Write the id of the parent. For normal symbols, this is a
854 * scope (symbol table), for cheap locals, it's a symbol.
856 if (SYM_IS_STD (ExprMask)) {
857 ObjWriteVar (S->Sym.Tab->Id);
859 ObjWriteVar (S->Sym.Entry->DebugSymId);
863 ObjWriteVar (S->Name);
865 /* Write the value */
866 if (SYM_IS_CONST (ExprMask)) {
868 ObjWrite32 (ConstVal);
870 /* Expression involved */
874 /* If the symbol has a size, write it to the file */
875 if (SYM_HAS_SIZE (ExprMask)) {
879 /* Write the line infos */
880 WriteLineInfo (&S->LineInfos);
887 /* No debug symbols */
892 /* Done writing debug symbols */
898 void WriteScopes (void)
899 /* Write the scope table to the object file */
901 /* Tell the object file module that we're about to start the scopes */
904 /* We will write scopes only if debug symbols are requested */
907 /* Get head of list */
908 const SymTable* S = LastScope;
910 /* Write the scope count to the file */
911 ObjWriteVar (ScopeCount);
913 /* Walk through all scopes and write them to the file */
916 /* Type must be defined */
917 CHECK (S->Type != SCOPETYPE_UNDEF);
922 /* Id of parent scope */
924 ObjWriteVar (S->Parent->Id);
930 ObjWriteVar (S->Level);
932 /* Scope flags (currently always zero) */
936 ObjWriteVar (S->Type);
938 /* Name of the scope */
939 ObjWriteVar (S->Name);
941 /* Segment ranges for this scope */
942 WriteSegRanges (&S->SegRanges);
950 /* No debug info requested */
955 /* Done writing the scopes */