1 /*****************************************************************************/
5 /* Symbol table for the ca65 macroassembler */
9 /* (C) 1998-2006 Ullrich von Bassewitz */
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 */
76 /* Symbol table variables */
77 static unsigned ImportCount = 0; /* Counter for import symbols */
78 static unsigned ExportCount = 0; /* Counter for export symbols */
82 /*****************************************************************************/
83 /* Internally used functions */
84 /*****************************************************************************/
88 static unsigned ScopeTableSize (unsigned Level)
89 /* Get the size of a table for the given lexical level */
100 static SymTable* NewSymTable (SymTable* Parent, const char* Name)
101 /* Allocate a symbol table on the heap and return it */
103 /* Determine the lexical level and the number of table slots */
104 unsigned Level = Parent? Parent->Level + 1 : 0;
105 unsigned Slots = ScopeTableSize (Level);
107 /* Allocate memory */
108 SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
110 /* Set variables and clear hash table entries */
114 S->SegRanges = AUTO_COLLECTION_INITIALIZER;
116 S->AddrSize = ADDR_SIZE_DEFAULT;
119 S->TableSlots = Slots;
122 S->Name = GetStringId (Name);
127 /* Insert the symbol table into the child tree of the parent */
129 SymTable* T = Parent->Childs;
135 /* Choose next entry */
136 int Cmp = strcmp (Name, GetString (T->Name));
144 } else if (Cmp > 0) {
152 /* Duplicate scope name */
153 Internal ("Duplicate scope name: `%s'", Name);
159 /* Return the prepared struct */
165 /*****************************************************************************/
167 /*****************************************************************************/
171 void SymEnterLevel (const char* ScopeName, unsigned char Type, unsigned char AddrSize)
172 /* Enter a new lexical level */
174 /* Map a default address size to something real */
175 if (AddrSize == ADDR_SIZE_DEFAULT) {
176 /* Use the segment address size */
177 AddrSize = GetCurrentSegAddrSize ();
180 /* If we have a current scope, search for the given name and create a
181 * new one if it doesn't exist. If this is the root scope, just create it.
185 /* Search for the scope, create a new one */
186 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
188 /* Check if the scope has been defined before */
189 if (CurrentScope->Flags & ST_DEFINED) {
190 Error ("Duplicate scope `%s'", ScopeName);
194 CurrentScope = RootScope = NewSymTable (0, ScopeName);
197 /* Mark the scope as defined and set type and address size */
198 CurrentScope->Flags |= ST_DEFINED;
199 CurrentScope->AddrSize = AddrSize;
200 CurrentScope->Type = Type;
202 /* If this is a scope that allows to emit data into segments, add segment
203 * ranges for all currently existing segments. Doing this for just a few
204 * scope types is not really necessary but an optimization, because it
205 * does not allocate memory for useless data (unhandled types here don't
206 * occupy space in any segment).
208 if (CurrentScope->Type <= ST_SCOPE_HAS_DATA) {
209 AddSegRanges (&CurrentScope->SegRanges);
215 void SymLeaveLevel (void)
216 /* Leave the current lexical level */
218 /* Close the segment ranges. We don't care about the scope type here,
219 * since types without segment ranges will just have an empty list.
221 CloseSegRanges (&CurrentScope->SegRanges);
223 /* If we have segment ranges, the first one is the segment that was
224 * active, when the scope was opened. Set the size of the scope to the
225 * number of data bytes emitted into this segment.
227 if (CollCount (&CurrentScope->SegRanges) > 0) {
228 const SegRange* R = CollAtUnchecked (&CurrentScope->SegRanges, 0);
229 DefSizeOfScope (CurrentScope, GetSegRangeSize (R));
232 /* Leave the scope */
233 CurrentScope = CurrentScope->Parent;
238 SymTable* SymFindScope (SymTable* Parent, const char* Name, int AllocNew)
239 /* Find a scope in the given enclosing scope */
241 SymTable** T = &Parent->Childs;
243 int Cmp = strcmp (Name, GetString ((*T)->Name));
246 } else if (Cmp > 0) {
249 /* Found the scope */
254 /* Create a new scope if requested and we didn't find one */
255 if (*T == 0 && AllocNew) {
256 *T = NewSymTable (Parent, Name);
259 /* Return the scope */
265 SymTable* SymFindAnyScope (SymTable* Parent, const char* Name)
266 /* Find a scope in the given or any of its parent scopes. The function will
267 * never create a new symbol, since this can only be done in one specific
273 /* Search in the current table */
274 Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
276 /* Not found, search in the parent scope, if we have one */
277 Parent = Parent->Parent;
279 } while (Scope == 0 && Parent != 0);
286 SymEntry* SymFindLocal (SymEntry* Parent, const char* Name, int AllocNew)
287 /* Find a cheap local symbol. If AllocNew is given and the entry is not
288 * found, create a new one. Return the entry found, or the new entry created,
289 * or - in case AllocNew is zero - return 0.
295 /* Local symbol, get the table */
297 /* No last global, so there's no local table */
298 Error ("No preceeding global symbol");
300 return NewSymEntry (Name, SF_LOCAL);
306 /* Search for the symbol if we have a table */
307 Cmp = SymSearchTree (Parent->Locals, Name, &S);
309 /* If we found an entry, return it */
316 /* Otherwise create a new entry, insert and return it */
317 SymEntry* N = NewSymEntry (Name, SF_LOCAL);
320 } else if (Cmp < 0) {
328 /* We did not find the entry and AllocNew is false. */
334 SymEntry* SymFind (SymTable* Scope, const char* Name, int AllocNew)
335 /* Find a new symbol table entry in the given table. If AllocNew is given and
336 * the entry is not found, create a new one. Return the entry found, or the
337 * new entry created, or - in case AllocNew is zero - return 0.
342 /* Global symbol: Get the hash value for the name */
343 unsigned Hash = HashStr (Name) % Scope->TableSlots;
345 /* Search for the entry */
346 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
348 /* If we found an entry, return it */
355 /* Otherwise create a new entry, insert and return it */
356 SymEntry* N = NewSymEntry (Name, SF_NONE);
358 Scope->Table[Hash] = N;
359 } else if (Cmp < 0) {
365 ++Scope->TableEntries;
370 /* We did not find the entry and AllocNew is false. */
376 SymEntry* SymFindAny (SymTable* Scope, const char* Name)
377 /* Find a symbol in the given or any of its parent scopes. The function will
378 * never create a new symbol, since this can only be done in one specific
384 /* Search in the current table */
385 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
387 /* Found, return it */
391 /* Not found, search in the parent scope, if we have one */
392 Scope = Scope->Parent;
394 } while (Sym == 0 && Scope != 0);
396 /* Return the result */
402 unsigned char GetCurrentSymTabType ()
403 /* Return the type of the current symbol table */
405 CHECK (CurrentScope != 0);
406 return CurrentScope->Type;
411 static void SymCheckUndefined (SymEntry* S)
412 /* Handle an undefined symbol */
414 /* Undefined symbol. It may be...
416 * - An undefined symbol in a nested lexical level. In this
417 * case, search for the symbol in the higher levels and
418 * make the entry a trampoline entry if we find one.
420 * - If the symbol is not found, it is a real undefined symbol.
421 * If the AutoImport flag is set, make it an import. If the
422 * AutoImport flag is not set, it's an error.
425 SymTable* Tab = GetSymParentScope (S);
427 Sym = SymFind (Tab, GetString (S->Name), SYM_FIND_EXISTING);
428 if (Sym && (Sym->Flags & (SF_DEFINED | SF_IMPORT)) != 0) {
429 /* We've found a symbol in a higher level that is
430 * either defined in the source, or an import.
434 /* No matching symbol found in this level. Look further */
440 /* We found the symbol in a higher level. Transfer the flags and
441 * address size from the local symbol to that in the higher level
442 * and check for problems.
444 if (S->Flags & SF_EXPORT) {
445 if (Sym->Flags & SF_IMPORT) {
446 /* The symbol is already marked as import */
447 PError (&S->Pos, "Symbol `%s' is already an import",
448 GetString (Sym->Name));
450 if (Sym->Flags & SF_EXPORT) {
451 /* The symbol is already marked as an export. */
452 if (Sym->AddrSize > S->ExportSize) {
453 /* We're exporting a symbol smaller than it actually is */
454 PWarning (&S->Pos, 1, "Symbol `%s' is %s but exported %s",
455 GetSymName (Sym), AddrSizeToStr (Sym->AddrSize),
456 AddrSizeToStr (S->ExportSize));
459 /* Mark the symbol as an export */
460 Sym->Flags |= SF_EXPORT;
461 Sym->ExportSize = S->ExportSize;
462 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
463 /* Use the actual size of the symbol */
464 Sym->ExportSize = Sym->AddrSize;
466 if (Sym->AddrSize > Sym->ExportSize) {
467 /* We're exporting a symbol smaller than it actually is */
468 PWarning (&S->Pos, 1, "Symbol `%s' is %s but exported %s",
469 GetSymName (Sym), AddrSizeToStr (Sym->AddrSize),
470 AddrSizeToStr (Sym->ExportSize));
474 Sym->Flags |= (S->Flags & SF_REFERENCED);
476 /* Transfer all expression references */
477 SymTransferExprRefs (S, Sym);
479 /* Mark the symbol as unused removing all other flags */
480 S->Flags = SF_UNUSED;
483 /* The symbol is definitely undefined */
484 if (S->Flags & SF_EXPORT) {
485 /* We will not auto-import an export */
486 PError (&S->Pos, "Exported symbol `%s' was never defined",
487 GetString (S->Name));
490 /* Mark as import, will be indexed later */
491 S->Flags |= SF_IMPORT;
492 /* Use the address size for code */
493 S->AddrSize = CodeAddrSize;
496 PError (&S->Pos, "Symbol `%s' is undefined", GetString (S->Name));
505 /* Run through all symbols and check for anomalies and errors */
509 /* Check for open scopes */
510 if (CurrentScope->Parent != 0) {
511 Error ("Local scope was not closed");
514 /* First pass: Walk through all symbols, checking for undefined's and
515 * changing them to trampoline symbols or make them imports.
519 /* If the symbol is marked as global, mark it as export, if it is
520 * already defined, otherwise mark it as import.
522 if (S->Flags & SF_GLOBAL) {
523 if (S->Flags & SF_DEFINED) {
524 SymExportFromGlobal (S);
526 SymImportFromGlobal (S);
530 /* Handle undefined symbols */
531 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
532 /* This is an undefined symbol. Handle it. */
533 SymCheckUndefined (S);
540 /* Second pass: Walk again through the symbols. Count exports and imports
541 * and set address sizes where this has not happened before. Ignore
542 * undefined's, since we handled them in the last pass, and ignore unused
543 * symbols, since we handled them in the last pass, too.
547 if ((S->Flags & SF_UNUSED) == 0 &&
548 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
550 /* Check for defined symbols that were never referenced */
551 if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
552 const char* Name = GetString (S->Name);
553 if (Name[0] != '.') { /* Ignore internals */
554 PWarning (&S->Pos, 2,
555 "Symbol `%s' is defined but never used",
556 GetString (S->Name));
560 /* Assign an index to all imports */
561 if (S->Flags & SF_IMPORT) {
562 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
563 /* Imported symbol is not referenced */
564 PWarning (&S->Pos, 2,
565 "Symbol `%s' is imported but never used",
566 GetString (S->Name));
568 /* Give the import an index, count imports */
569 S->Index = ImportCount++;
570 S->Flags |= SF_INDEXED;
574 /* Assign an index to all exports */
575 if (S->Flags & SF_EXPORT) {
576 /* Give the export an index, count exports */
577 S->Index = ExportCount++;
578 S->Flags |= SF_INDEXED;
581 /* If the symbol is defined but has an unknown address size,
584 if (SymHasExpr (S) && S->AddrSize == ADDR_SIZE_DEFAULT) {
587 StudyExpr (S->Expr, &ED);
588 S->AddrSize = ED.AddrSize;
589 if (SymIsExport (S)) {
590 if (S->ExportSize == ADDR_SIZE_DEFAULT) {
591 /* Use the real export size */
592 S->ExportSize = S->AddrSize;
593 } else if (S->AddrSize > S->ExportSize) {
594 /* We're exporting a symbol smaller than it actually is */
595 PWarning (&S->Pos, 1,
596 "Symbol `%s' is %s but exported %s",
597 GetSymName (S), AddrSizeToStr (S->AddrSize),
598 AddrSizeToStr (S->ExportSize));
604 /* If the address size of the symbol was guessed, check the guess
605 * against the actual address size and print a warning if the two
608 if (S->AddrSize != ADDR_SIZE_DEFAULT) {
609 /* Do we have data for this address size? */
610 if (S->AddrSize <= sizeof (S->GuessedUse) / sizeof (S->GuessedUse[0])) {
611 /* Get the file position where the symbol was used */
612 const FilePos* P = S->GuessedUse[S->AddrSize - 1];
615 "Didn't use %s addressing for `%s'",
616 AddrSizeToStr (S->AddrSize),
631 void SymDump (FILE* F)
632 /* Dump the symbol table */
634 SymEntry* S = SymList;
637 /* Ignore unused symbols */
638 if ((S->Flags & SF_UNUSED) != 0) {
640 "%-24s %s %s %s %s %s\n",
642 (S->Flags & SF_DEFINED)? "DEF" : "---",
643 (S->Flags & SF_REFERENCED)? "REF" : "---",
644 (S->Flags & SF_IMPORT)? "IMP" : "---",
645 (S->Flags & SF_EXPORT)? "EXP" : "---",
646 AddrSizeToStr (S->AddrSize));
655 void WriteImports (void)
656 /* Write the imports list to the object file */
660 /* Tell the object file module that we're about to start the imports */
663 /* Write the import count to the list */
664 ObjWriteVar (ImportCount);
666 /* Walk throught list and write all valid imports to the file. An import
667 * is considered valid, if it is either referenced, or the forced bit is
668 * set. Otherwise, the import is ignored (no need to link in something
673 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
674 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
676 ObjWrite8 (S->AddrSize);
677 ObjWriteVar (S->Name);
678 ObjWritePos (&S->Pos);
683 /* Done writing imports */
689 void WriteExports (void)
690 /* Write the exports list to the object file */
695 /* Tell the object file module that we're about to start the exports */
698 /* Write the export count to the list */
699 ObjWriteVar (ExportCount);
701 /* Walk throught list and write all exports to the file */
704 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
708 /* Get the expression bits */
709 unsigned char ExprMask = SymIsConst (S, &ConstVal)? EXP_CONST : EXP_EXPR;
710 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
712 /* Count the number of ConDes types */
713 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
714 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
715 INC_EXP_CONDES_COUNT (ExprMask);
719 /* Write the type and the export size */
720 ObjWrite8 (ExprMask);
721 ObjWrite8 (S->ExportSize);
723 /* Write any ConDes declarations */
724 if (GET_EXP_CONDES_COUNT (ExprMask) > 0) {
725 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
726 unsigned char Prio = S->ConDesPrio[Type];
727 if (Prio != CD_PRIO_NONE) {
728 ObjWrite8 (CD_BUILD (Type, Prio));
734 ObjWriteVar (S->Name);
736 /* Write the value */
737 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
739 ObjWrite32 (ConstVal);
741 /* Expression involved */
745 /* Write the source file position */
746 ObjWritePos (&S->Pos);
751 /* Done writing exports */
757 void WriteDbgSyms (void)
758 /* Write a list of all symbols to the object file */
763 /* Tell the object file module that we're about to start the debug info */
766 /* Check if debug info is requested */
769 /* Walk through the list and count the symbols */
773 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
779 /* Write the symbol count to the list */
782 /* Walk through list and write all symbols to the file */
785 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
789 /* Get the expression bits */
790 unsigned char ExprMask = (SymIsConst (S, &ConstVal))? EXP_CONST : EXP_EXPR;
791 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
794 ObjWrite8 (ExprMask);
796 /* Write the address size */
797 ObjWrite8 (S->AddrSize);
800 ObjWriteVar (S->Name);
802 /* Write the value */
803 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
805 ObjWrite32 (ConstVal);
807 /* Expression involved */
811 /* Write the source file position */
812 ObjWritePos (&S->Pos);
819 /* No debug symbols */
824 /* Done writing debug symbols */
830 void WriteScopes (void)
831 /* Write the scope table to the object file */
833 /* Tell the object file module that we're about to start the scopes */
839 /* Done writing the scopes */