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 /*****************************************************************************/
55 #include "studyexpr.h"
60 /*****************************************************************************/
62 /*****************************************************************************/
66 /* Combined symbol entry flags used within this module */
67 #define SF_UNDEFMASK (SF_REFERENCED | SF_DEFINED | SF_IMPORT)
68 #define SF_UNDEFVAL (SF_REFERENCED)
69 #define SF_DBGINFOMASK (SF_UNUSED | SF_DEFINED | SF_IMPORT)
70 #define SF_DBGINFOVAL (SF_DEFINED)
73 SymTable* CurrentScope = 0; /* Pointer to current symbol table */
74 SymTable* RootScope = 0; /* Root symbol table */
75 static SymTable* LastScope = 0; /* Pointer to last scope in list */
77 /* Symbol table variables */
78 static unsigned ImportCount = 0; /* Counter for import symbols */
79 static unsigned ExportCount = 0; /* Counter for export symbols */
83 /*****************************************************************************/
84 /* Internally used functions */
85 /*****************************************************************************/
89 static unsigned ScopeTableSize (unsigned Level)
90 /* Get the size of a table for the given lexical level */
101 static SymTable* NewSymTable (SymTable* Parent, const StrBuf* Name)
102 /* Allocate a symbol table on the heap and return it */
104 /* Determine the lexical level and the number of table slots */
105 unsigned Level = Parent? Parent->Level + 1 : 0;
106 unsigned Slots = ScopeTableSize (Level);
108 /* Allocate memory */
109 SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
111 /* Set variables and clear hash table entries */
115 S->SegRanges = AUTO_COLLECTION_INITIALIZER;
117 S->AddrSize = ADDR_SIZE_DEFAULT;
120 S->TableSlots = Slots;
123 S->Name = GetStrBufId (Name);
128 /* Insert the symbol table into the list of all symbol tables and maintain
129 * a unqiue id for each scope.
132 if (RootScope == 0) {
136 S->Id = LastScope->Id + 1;
140 /* Insert the symbol table into the child tree of the parent */
142 SymTable* T = Parent->Childs;
148 /* Choose next entry */
149 int Cmp = SB_Compare (Name, GetStrBuf (T->Name));
157 } else if (Cmp > 0) {
165 /* Duplicate scope name */
166 Internal ("Duplicate scope name: `%m%p'", Name);
172 /* Return the prepared struct */
178 /*****************************************************************************/
180 /*****************************************************************************/
184 void SymEnterLevel (const StrBuf* ScopeName, unsigned char Type, unsigned char AddrSize)
185 /* Enter a new lexical level */
187 /* Map a default address size to something real */
188 if (AddrSize == ADDR_SIZE_DEFAULT) {
189 /* Use the segment address size */
190 AddrSize = GetCurrentSegAddrSize ();
193 /* If we have a current scope, search for the given name and create a
194 * new one if it doesn't exist. If this is the root scope, just create it.
198 /* Search for the scope, create a new one */
199 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
201 /* Check if the scope has been defined before */
202 if (CurrentScope->Flags & ST_DEFINED) {
203 Error ("Duplicate scope `%m%p'", ScopeName);
207 CurrentScope = RootScope = NewSymTable (0, ScopeName);
210 /* Mark the scope as defined and set type and address size */
211 CurrentScope->Flags |= ST_DEFINED;
212 CurrentScope->AddrSize = AddrSize;
213 CurrentScope->Type = Type;
215 /* If this is a scope that allows to emit data into segments, add segment
216 * ranges for all currently existing segments. Doing this for just a few
217 * scope types is not really necessary but an optimization, because it
218 * does not allocate memory for useless data (unhandled types here don't
219 * occupy space in any segment).
221 if (CurrentScope->Type <= ST_SCOPE_HAS_DATA) {
222 AddSegRanges (&CurrentScope->SegRanges);
228 void SymLeaveLevel (void)
229 /* Leave the current lexical level */
231 /* Close the segment ranges. We don't care about the scope type here,
232 * since types without segment ranges will just have an empty list.
234 CloseSegRanges (&CurrentScope->SegRanges);
236 /* If we have segment ranges, the first one is the segment that was
237 * active, when the scope was opened. Set the size of the scope to the
238 * number of data bytes emitted into this segment.
240 if (CollCount (&CurrentScope->SegRanges) > 0) {
241 const SegRange* R = CollAtUnchecked (&CurrentScope->SegRanges, 0);
242 DefSizeOfScope (CurrentScope, GetSegRangeSize (R));
245 /* Leave the scope */
246 CurrentScope = CurrentScope->Parent;
251 SymTable* SymFindScope (SymTable* Parent, const StrBuf* Name, int AllocNew)
252 /* Find a scope in the given enclosing scope */
254 SymTable** T = &Parent->Childs;
256 int Cmp = SB_Compare (Name, GetStrBuf ((*T)->Name));
259 } else if (Cmp > 0) {
262 /* Found the scope */
267 /* Create a new scope if requested and we didn't find one */
268 if (*T == 0 && AllocNew) {
269 *T = NewSymTable (Parent, Name);
272 /* Return the scope */
278 SymTable* SymFindAnyScope (SymTable* Parent, const StrBuf* Name)
279 /* Find a scope in the given or any of its parent scopes. The function will
280 * never create a new symbol, since this can only be done in one specific
286 /* Search in the current table */
287 Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
289 /* Not found, search in the parent scope, if we have one */
290 Parent = Parent->Parent;
292 } while (Scope == 0 && Parent != 0);
299 SymEntry* SymFindLocal (SymEntry* Parent, const StrBuf* Name, int AllocNew)
300 /* Find a cheap local symbol. If AllocNew is given and the entry is not
301 * found, create a new one. Return the entry found, or the new entry created,
302 * or - in case AllocNew is zero - return 0.
308 /* Local symbol, get the table */
310 /* No last global, so there's no local table */
311 Error ("No preceeding global symbol");
313 return NewSymEntry (Name, SF_LOCAL);
319 /* Search for the symbol if we have a table */
320 Cmp = SymSearchTree (Parent->Locals, Name, &S);
322 /* If we found an entry, return it */
329 /* Otherwise create a new entry, insert and return it */
330 SymEntry* N = NewSymEntry (Name, SF_LOCAL);
331 N->Sym.Entry = Parent;
334 } else if (Cmp < 0) {
342 /* We did not find the entry and AllocNew is false. */
348 SymEntry* SymFind (SymTable* Scope, const StrBuf* Name, int AllocNew)
349 /* Find a new symbol table entry in the given table. If AllocNew is given and
350 * the entry is not found, create a new one. Return the entry found, or the
351 * new entry created, or - in case AllocNew is zero - return 0.
356 /* Global symbol: Get the hash value for the name */
357 unsigned Hash = HashBuf (Name) % Scope->TableSlots;
359 /* Search for the entry */
360 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
362 /* If we found an entry, return it */
369 /* Otherwise create a new entry, insert and return it */
370 SymEntry* N = NewSymEntry (Name, SF_NONE);
373 Scope->Table[Hash] = N;
374 } else if (Cmp < 0) {
379 ++Scope->TableEntries;
384 /* We did not find the entry and AllocNew is false. */
390 SymEntry* SymFindAny (SymTable* Scope, const StrBuf* Name)
391 /* Find a symbol in the given or any of its parent scopes. The function will
392 * never create a new symbol, since this can only be done in one specific
398 /* Search in the current table */
399 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
401 /* Found, return it */
405 /* Not found, search in the parent scope, if we have one */
406 Scope = Scope->Parent;
408 } while (Sym == 0 && Scope != 0);
410 /* Return the result */
416 unsigned char GetCurrentSymTabType ()
417 /* Return the type of the current symbol table */
419 CHECK (CurrentScope != 0);
420 return CurrentScope->Type;
425 static void SymCheckUndefined (SymEntry* S)
426 /* Handle an undefined symbol */
428 /* Undefined symbol. It may be...
430 * - An undefined symbol in a nested lexical level. In this
431 * case, search for the symbol in the higher levels and
432 * make the entry a trampoline entry if we find one.
434 * - If the symbol is not found, it is a real undefined symbol.
435 * If the AutoImport flag is set, make it an import. If the
436 * AutoImport flag is not set, it's an error.
439 SymTable* Tab = GetSymParentScope (S);
441 Sym = SymFind (Tab, GetStrBuf (S->Name), SYM_FIND_EXISTING);
442 if (Sym && (Sym->Flags & (SF_DEFINED | SF_IMPORT)) != 0) {
443 /* We've found a symbol in a higher level that is
444 * either defined in the source, or an import.
448 /* No matching symbol found in this level. Look further */
454 /* We found the symbol in a higher level. Transfer the flags and
455 * address size from the local symbol to that in the higher level
456 * and check for problems.
458 if (S->Flags & SF_EXPORT) {
459 if (Sym->Flags & SF_IMPORT) {
460 /* The symbol is already marked as import */
461 LIError (&S->LineInfos,
462 "Symbol `%s' is already an import",
463 GetString (Sym->Name));
465 if (Sym->Flags & SF_EXPORT) {
466 /* The symbol is already marked as an export. */
467 if (Sym->AddrSize > S->ExportSize) {
468 /* We're exporting a symbol smaller than it actually is */
469 LIWarning (&S->LineInfos, 1,
470 "Symbol `%m%p' is %s but exported %s",
472 AddrSizeToStr (Sym->AddrSize),
473 AddrSizeToStr (S->ExportSize));
476 /* Mark the symbol as an export */
477 Sym->Flags |= SF_EXPORT;
478 Sym->ExportSize = S->ExportSize;
479 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
480 /* Use the actual size of the symbol */
481 Sym->ExportSize = Sym->AddrSize;
483 if (Sym->AddrSize > Sym->ExportSize) {
484 /* We're exporting a symbol smaller than it actually is */
485 LIWarning (&S->LineInfos, 1,
486 "Symbol `%m%p' is %s but exported %s",
488 AddrSizeToStr (Sym->AddrSize),
489 AddrSizeToStr (Sym->ExportSize));
493 Sym->Flags |= (S->Flags & SF_REFERENCED);
495 /* Transfer all expression references */
496 SymTransferExprRefs (S, Sym);
498 /* Mark the symbol as unused removing all other flags */
499 S->Flags = SF_UNUSED;
502 /* The symbol is definitely undefined */
503 if (S->Flags & SF_EXPORT) {
504 /* We will not auto-import an export */
505 LIError (&S->LineInfos,
506 "Exported symbol `%m%p' was never defined",
510 /* Mark as import, will be indexed later */
511 S->Flags |= SF_IMPORT;
512 /* Use the address size for code */
513 S->AddrSize = CodeAddrSize;
516 LIError (&S->LineInfos,
517 "Symbol `%m%p' is undefined",
527 /* Run through all symbols and check for anomalies and errors */
531 /* Check for open scopes */
532 if (CurrentScope->Parent != 0) {
533 Error ("Local scope was not closed");
536 /* First pass: Walk through all symbols, checking for undefined's and
537 * changing them to trampoline symbols or make them imports.
541 /* If the symbol is marked as global, mark it as export, if it is
542 * already defined, otherwise mark it as import.
544 if (S->Flags & SF_GLOBAL) {
545 if (S->Flags & SF_DEFINED) {
546 SymExportFromGlobal (S);
548 SymImportFromGlobal (S);
552 /* Handle undefined symbols */
553 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
554 /* This is an undefined symbol. Handle it. */
555 SymCheckUndefined (S);
562 /* Second pass: Walk again through the symbols. Count exports and imports
563 * and set address sizes where this has not happened before. Ignore
564 * undefined's, since we handled them in the last pass, and ignore unused
565 * symbols, since we handled them in the last pass, too.
569 if ((S->Flags & SF_UNUSED) == 0 &&
570 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
572 /* Check for defined symbols that were never referenced */
573 if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
574 const StrBuf* Name = GetStrBuf (S->Name);
575 if (SB_At (Name, 0) != '.') { /* Ignore internals */
576 LIWarning (&S->LineInfos, 2,
577 "Symbol `%m%p' is defined but never used",
582 /* Assign an index to all imports */
583 if (S->Flags & SF_IMPORT) {
584 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
585 /* Imported symbol is not referenced */
586 LIWarning (&S->LineInfos, 2,
587 "Symbol `%m%p' is imported but never used",
590 /* Give the import an id, count imports */
591 S->ImportId = ImportCount++;
596 if (S->Flags & SF_EXPORT) {
600 /* If the symbol is defined but has an unknown address size,
603 if (SymHasExpr (S) && S->AddrSize == ADDR_SIZE_DEFAULT) {
606 StudyExpr (S->Expr, &ED);
607 S->AddrSize = ED.AddrSize;
608 if (SymIsExport (S)) {
609 if (S->ExportSize == ADDR_SIZE_DEFAULT) {
610 /* Use the real export size */
611 S->ExportSize = S->AddrSize;
612 } else if (S->AddrSize > S->ExportSize) {
613 /* We're exporting a symbol smaller than it actually is */
614 LIWarning (&S->LineInfos, 1,
615 "Symbol `%m%p' is %s but exported %s",
617 AddrSizeToStr (S->AddrSize),
618 AddrSizeToStr (S->ExportSize));
624 /* If the address size of the symbol was guessed, check the guess
625 * against the actual address size and print a warning if the two
628 if (S->AddrSize != ADDR_SIZE_DEFAULT) {
629 /* Do we have data for this address size? */
630 if (S->AddrSize <= sizeof (S->GuessedUse) / sizeof (S->GuessedUse[0])) {
631 /* Get the file position where the symbol was used */
632 const FilePos* P = S->GuessedUse[S->AddrSize - 1];
635 "Didn't use %s addressing for `%m%p'",
636 AddrSizeToStr (S->AddrSize),
651 void SymDump (FILE* F)
652 /* Dump the symbol table */
654 SymEntry* S = SymList;
657 /* Ignore unused symbols */
658 if ((S->Flags & SF_UNUSED) != 0) {
660 "%m%-24p %s %s %s %s %s\n",
662 (S->Flags & SF_DEFINED)? "DEF" : "---",
663 (S->Flags & SF_REFERENCED)? "REF" : "---",
664 (S->Flags & SF_IMPORT)? "IMP" : "---",
665 (S->Flags & SF_EXPORT)? "EXP" : "---",
666 AddrSizeToStr (S->AddrSize));
675 void WriteImports (void)
676 /* Write the imports list to the object file */
680 /* Tell the object file module that we're about to start the imports */
683 /* Write the import count to the list */
684 ObjWriteVar (ImportCount);
686 /* Walk throught list and write all valid imports to the file. An import
687 * is considered valid, if it is either referenced, or the forced bit is
688 * set. Otherwise, the import is ignored (no need to link in something
693 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
694 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
696 ObjWrite8 (S->AddrSize);
697 ObjWriteVar (S->Name);
698 WriteLineInfo (&S->LineInfos);
703 /* Done writing imports */
709 void WriteExports (void)
710 /* Write the exports list to the object file */
715 /* Tell the object file module that we're about to start the exports */
718 /* Write the export count to the list */
719 ObjWriteVar (ExportCount);
721 /* Walk throught list and write all exports to the file */
724 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
726 /* Get the expression bits and the value */
728 unsigned ExprMask = GetSymInfoFlags (S, &ConstVal);
730 /* Count the number of ConDes types */
731 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
732 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
733 SYM_INC_CONDES_COUNT (ExprMask);
737 /* Write the type and the export size */
738 ObjWriteVar (ExprMask);
739 ObjWrite8 (S->ExportSize);
741 /* Write any ConDes declarations */
742 if (SYM_GET_CONDES_COUNT (ExprMask) > 0) {
743 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
744 unsigned char Prio = S->ConDesPrio[Type];
745 if (Prio != CD_PRIO_NONE) {
746 ObjWrite8 (CD_BUILD (Type, Prio));
752 ObjWriteVar (S->Name);
754 /* Write the value */
755 if (SYM_IS_CONST (ExprMask)) {
757 ObjWrite32 (ConstVal);
759 /* Expression involved */
763 /* Write the line infos */
764 WriteLineInfo (&S->LineInfos);
769 /* Done writing exports */
775 void WriteDbgSyms (void)
776 /* Write a list of all symbols to the object file */
781 /* Tell the object file module that we're about to start the debug info */
784 /* Check if debug info is requested */
787 /* Walk through the list, give each symbol an id and count them */
791 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
792 S->DebugSymId = Count++;
797 /* Write the symbol count to the list */
800 /* Walk through list and write all symbols to the file */
803 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
805 /* Get the expression bits and the value */
807 unsigned ExprMask = GetSymInfoFlags (S, &ConstVal);
810 ObjWriteVar (ExprMask);
812 /* Write the address size */
813 ObjWrite8 (S->AddrSize);
816 ObjWriteVar (S->Name);
818 /* Write the value */
819 if (SYM_IS_CONST (ExprMask)) {
821 ObjWrite32 (ConstVal);
823 /* Expression involved */
827 /* Write the line infos */
828 WriteLineInfo (&S->LineInfos);
835 /* No debug symbols */
840 /* Done writing debug symbols */
846 void WriteScopes (void)
847 /* Write the scope table to the object file */
849 /* Tell the object file module that we're about to start the scopes */
852 /* No debug info requested */
855 /* Done writing the scopes */