1 /*****************************************************************************/
5 /* Symbol table for the ca65 macroassembler */
9 /* (C) 1998-2003 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 /*****************************************************************************/
58 /*****************************************************************************/
60 /*****************************************************************************/
64 /* Combined symbol entry flags used within this module */
65 #define SF_UNDEFMASK (SF_REFERENCED | SF_DEFINED | SF_IMPORT)
66 #define SF_UNDEFVAL (SF_REFERENCED)
67 #define SF_DBGINFOMASK (SF_UNUSED | SF_DEFINED | SF_EXPORT | SF_IMPORT)
68 #define SF_DBGINFOVAL (SF_DEFINED)
71 SymTable* CurrentScope = 0; /* Pointer to current symbol table */
72 SymTable* RootScope = 0; /* Root symbol table */
74 /* Symbol table variables */
75 static unsigned ImportCount = 0; /* Counter for import symbols */
76 static unsigned ExportCount = 0; /* Counter for export symbols */
80 /*****************************************************************************/
81 /* Internally used functions */
82 /*****************************************************************************/
86 static unsigned ScopeTableSize (unsigned Level)
87 /* Get the size of a table for the given lexical level */
98 static SymTable* NewSymTable (SymTable* Parent, const char* Name)
99 /* Allocate a symbol table on the heap and return it */
101 /* Determine the lexical level and the number of table slots */
102 unsigned Level = Parent? Parent->Level + 1 : 0;
103 unsigned Slots = ScopeTableSize (Level);
105 /* Allocate memory */
106 SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
108 /* Set variables and clear hash table entries */
113 S->AddrSize = ADDR_SIZE_DEFAULT;
116 S->TableSlots = Slots;
119 S->Name = GetStringId (Name);
124 /* Insert the symbol table into the child tree of the parent */
126 SymTable* T = Parent->Childs;
132 /* Choose next entry */
133 int Cmp = strcmp (Name, GetString (T->Name));
141 } else if (Cmp > 0) {
149 /* Duplicate scope name */
150 Internal ("Duplicate scope name: `%s'", Name);
156 /* Return the prepared struct */
162 /*****************************************************************************/
164 /*****************************************************************************/
168 void SymEnterLevel (const char* ScopeName, unsigned char Type, unsigned char AddrSize)
169 /* Enter a new lexical level */
171 /* Map a default address size to something real */
172 if (AddrSize == ADDR_SIZE_DEFAULT) {
173 /* Use the segment address size */
174 AddrSize = GetCurrentSegAddrSize ();
177 /* If we have a current scope, search for the given name and create a
178 * new one if it doesn't exist. If this is the root scope, just create it.
182 /* Search for the scope, create a new one */
183 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
185 /* Check if the scope has been defined before */
186 if (CurrentScope->Flags & ST_DEFINED) {
187 Error ("Duplicate scope `%s'", ScopeName);
191 CurrentScope = RootScope = NewSymTable (0, ScopeName);
194 /* Mark the scope as defined and set type and address size */
195 CurrentScope->Flags |= ST_DEFINED;
196 CurrentScope->AddrSize = AddrSize;
197 CurrentScope->Type = Type;
202 void SymLeaveLevel (void)
203 /* Leave the current lexical level */
205 CurrentScope = CurrentScope->Parent;
210 SymTable* SymFindScope (SymTable* Parent, const char* Name, int AllocNew)
211 /* Find a scope in the given enclosing scope */
213 SymTable** T = &Parent->Childs;
215 int Cmp = strcmp (Name, GetString ((*T)->Name));
218 } else if (Cmp > 0) {
221 /* Found the scope */
226 /* Create a new scope if requested and we didn't find one */
227 if (*T == 0 && AllocNew) {
228 *T = NewSymTable (Parent, Name);
231 /* Return the scope */
237 SymTable* SymFindAnyScope (SymTable* Parent, const char* Name)
238 /* Find a scope in the given or any of its parent scopes. The function will
239 * never create a new symbol, since this can only be done in one specific
245 /* Search in the current table */
246 Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
248 /* Not found, search in the parent scope, if we have one */
249 Parent = Parent->Parent;
251 } while (Scope == 0 && Parent != 0);
258 SymEntry* SymFindLocal (SymEntry* Parent, const char* Name, int AllocNew)
259 /* Find a cheap local symbol. If AllocNew is given and the entry is not
260 * found, create a new one. Return the entry found, or the new entry created,
261 * or - in case AllocNew is zero - return 0.
267 /* Local symbol, get the table */
269 /* No last global, so there's no local table */
270 Error ("No preceeding global symbol");
272 return NewSymEntry (Name);
278 /* Search for the symbol if we have a table */
279 Cmp = SymSearchTree (Parent->Locals, Name, &S);
281 /* If we found an entry, return it */
288 /* Otherwise create a new entry, insert and return it */
289 SymEntry* N = NewSymEntry (Name);
292 } else if (Cmp < 0) {
300 /* We did not find the entry and AllocNew is false. */
306 SymEntry* SymFind (SymTable* Scope, const char* Name, int AllocNew)
307 /* Find a new symbol table entry in the given table. If AllocNew is given and
308 * the entry is not found, create a new one. Return the entry found, or the
309 * new entry created, or - in case AllocNew is zero - return 0.
314 /* Global symbol: Get the hash value for the name */
315 unsigned Hash = HashStr (Name) % Scope->TableSlots;
317 /* Search for the entry */
318 int Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
320 /* If we found an entry, return it */
327 /* Otherwise create a new entry, insert and return it */
328 SymEntry* N = NewSymEntry (Name);
330 Scope->Table[Hash] = N;
331 } else if (Cmp < 0) {
337 ++Scope->TableEntries;
342 /* We did not find the entry and AllocNew is false. */
348 static SymEntry* SymFindAny (SymTable* Scope, const char* Name)
349 /* Find a symbol in the given or any of its parent scopes. The function will
350 * never create a new symbol, since this can only be done in one specific
356 /* Search in the current table */
357 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
359 /* Found, return it */
362 /* Not found, search in the parent scope, if we have one */
363 Scope = Scope->Parent;
365 } while (Sym == 0 && Scope != 0);
373 int SymIsZP (SymEntry* S)
374 /* Return true if the symbol is explicitly marked as zeropage symbol */
376 /* If the symbol is not a global symbol, was not defined before, check the
377 * enclosing scope for a symbol with the same name, and return the ZP
378 * attribute of this symbol if we find one.
380 if (!IsLocalNameId (S->Name) && (S->Flags & (SF_DEFINED | SF_IMPORT)) == 0 &&
381 S->SymTab->Parent != 0) {
383 /* Try to find a symbol with the same name in the enclosing scope */
384 SymEntry* E = SymFindAny (S->SymTab->Parent, GetString (S->Name));
386 /* If we found one, use the ZP flag */
387 if (E && E->AddrSize == ADDR_SIZE_ZP) {
388 S->AddrSize = ADDR_SIZE_ZP;
392 /* Check the ZP flag */
393 return (S->AddrSize == ADDR_SIZE_ZP);
398 unsigned char GetCurrentSymTabType ()
399 /* Return the type of the current symbol table */
401 CHECK (CurrentScope != 0);
402 return CurrentScope->Type;
407 static void SymCheckUndefined (SymEntry* S)
408 /* Handle an undefined symbol */
410 /* Undefined symbol. It may be...
412 * - An undefined symbol in a nested lexical level. In this
413 * case, search for the symbol in the higher levels and
414 * make the entry a trampoline entry if we find one.
416 * - If the symbol is not found, it is a real undefined symbol.
417 * If the AutoImport flag is set, make it an import. If the
418 * AutoImport flag is not set, it's an error.
422 /* It's a global symbol, get the higher level table */
423 SymTable* Tab = S->SymTab->Parent;
425 Sym = SymFindAny (Tab, GetString (S->Name));
427 if (Sym->Flags & (SF_DEFINED | SF_IMPORT)) {
428 /* We've found a symbol in a higher level that is
429 * either defined in the source, or an import.
433 /* The symbol found is undefined itself. Look further */
434 Tab = Sym->SymTab->Parent;
437 /* No symbol found */
445 /* We found the symbol in a higher level. Transfer the flags and
446 * address size from the local symbol to that in the higher level
447 * and check for problems.
449 if (S->Flags & SF_EXPORT) {
450 if (Sym->Flags & SF_IMPORT) {
451 /* The symbol is already marked as import */
452 PError (&S->Pos, "Symbol `%s' is already an import",
453 GetString (Sym->Name));
455 if (Sym->Flags & SF_EXPORT) {
456 /* The symbol is already marked as an export. */
457 if (Sym->AddrSize > S->ExportSize) {
458 /* We're exporting a symbol smaller than it actually is */
459 PWarning (&S->Pos, 1, "Symbol `%s' is %s but exported %s",
460 GetSymName (Sym), AddrSizeToStr (Sym->AddrSize),
461 AddrSizeToStr (S->ExportSize));
464 /* Mark the symbol as an export */
465 Sym->Flags |= SF_EXPORT;
466 Sym->ExportSize = S->ExportSize;
467 if (Sym->ExportSize == ADDR_SIZE_DEFAULT) {
468 /* Use the actual size of the symbol */
469 Sym->ExportSize = Sym->AddrSize;
471 if (Sym->AddrSize > Sym->ExportSize) {
472 /* We're exporting a symbol smaller than it actually is */
473 PWarning (&S->Pos, 1, "Symbol `%s' is %s but exported %s",
474 GetSymName (Sym), AddrSizeToStr (Sym->AddrSize),
475 AddrSizeToStr (Sym->ExportSize));
479 Sym->Flags |= (S->Flags & SF_REFERENCED);
481 /* Transfer all expression references */
482 SymTransferExprRefs (S, Sym);
484 /* Mark the symbol as unused removing all other flags */
485 S->Flags = SF_UNUSED;
488 /* The symbol is definitely undefined */
489 if (S->Flags & SF_EXPORT) {
490 /* We will not auto-import an export */
491 PError (&S->Pos, "Exported symbol `%s' was never defined",
492 GetString (S->Name));
495 /* Mark as import, will be indexed later */
496 S->Flags |= SF_IMPORT;
497 /* Use the address size for code */
498 S->AddrSize = CodeAddrSize;
501 PError (&S->Pos, "Symbol `%s' is undefined", GetString (S->Name));
510 /* Run through all symbols and check for anomalies and errors */
514 /* Check for open scopes */
515 if (CurrentScope->Parent != 0) {
516 Error ("Local scope was not closed");
519 /* First pass: Walk through all symbols, checking for undefined's and
520 * changing them to trampoline symbols or make them imports.
524 /* If the symbol is marked as global, mark it as export, if it is
525 * already defined, otherwise mark it as import.
527 if (S->Flags & SF_GLOBAL) {
528 S->Flags &= ~SF_GLOBAL;
529 if (S->Flags & SF_DEFINED) {
530 S->Flags |= SF_EXPORT;
532 S->Flags |= SF_IMPORT;
536 /* Handle undefined symbols */
537 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
538 /* This is an undefined symbol. Handle it. */
539 SymCheckUndefined (S);
546 /* Second pass: Walk again through the symbols. Ignore undefined's, since
547 * we handled them in the last pass, and ignore unused symbols, since
548 * we handled them in the last pass, too.
552 if ((S->Flags & SF_UNUSED) == 0 &&
553 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
554 if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
555 /* Symbol was defined but never referenced */
556 PWarning (&S->Pos, 2,
557 "Symbol `%s' is defined but never used",
558 GetString (S->Name));
560 if (S->Flags & SF_IMPORT) {
561 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
562 /* Imported symbol is not referenced */
563 PWarning (&S->Pos, 2,
564 "Symbol `%s' is imported but never used",
565 GetString (S->Name));
567 /* Give the import an index, count imports */
568 S->Index = ImportCount++;
569 S->Flags |= SF_INDEXED;
572 if (S->Flags & SF_EXPORT) {
573 /* Give the export an index, count exports */
574 S->Index = ExportCount++;
575 S->Flags |= SF_INDEXED;
586 void SymDump (FILE* F)
587 /* Dump the symbol table */
589 SymEntry* S = SymList;
592 /* Ignore unused symbols */
593 if ((S->Flags & SF_UNUSED) != 0) {
595 "%-24s %s %s %s %s %s\n",
597 (S->Flags & SF_DEFINED)? "DEF" : "---",
598 (S->Flags & SF_REFERENCED)? "REF" : "---",
599 (S->Flags & SF_IMPORT)? "IMP" : "---",
600 (S->Flags & SF_EXPORT)? "EXP" : "---",
601 AddrSizeToStr (S->AddrSize));
610 void WriteImports (void)
611 /* Write the imports list to the object file */
615 /* Tell the object file module that we're about to start the imports */
618 /* Write the import count to the list */
619 ObjWriteVar (ImportCount);
621 /* Walk throught list and write all valid imports to the file. An import
622 * is considered valid, if it is either referenced, or the forced bit is
623 * set. Otherwise, the import is ignored (no need to link in something
628 if ((S->Flags & (SF_UNUSED | SF_IMPORT)) == SF_IMPORT &&
629 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
631 ObjWrite8 (S->AddrSize);
632 ObjWriteVar (S->Name);
633 ObjWritePos (&S->Pos);
638 /* Done writing imports */
644 void WriteExports (void)
645 /* Write the exports list to the object file */
650 /* Tell the object file module that we're about to start the exports */
653 /* Write the export count to the list */
654 ObjWriteVar (ExportCount);
656 /* Walk throught list and write all exports to the file */
659 if ((S->Flags & (SF_UNUSED | SF_EXPORT)) == SF_EXPORT) {
663 /* Get the expression bits */
664 unsigned char ExprMask = SymIsConst (S, &ConstVal)? EXP_CONST : EXP_EXPR;
665 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
667 /* Count the number of ConDes types */
668 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
669 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
670 INC_EXP_CONDES_COUNT (ExprMask);
674 /* Write the type and the export size */
675 ObjWrite8 (ExprMask);
676 ObjWrite8 (S->ExportSize);
678 /* Write any ConDes declarations */
679 if (GET_EXP_CONDES_COUNT (ExprMask) > 0) {
680 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
681 unsigned char Prio = S->ConDesPrio[Type];
682 if (Prio != CD_PRIO_NONE) {
683 ObjWrite8 (CD_BUILD (Type, Prio));
689 ObjWriteVar (S->Name);
691 /* Write the value */
692 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
694 ObjWrite32 (ConstVal);
696 /* Expression involved */
697 WriteExpr (S->V.Expr);
700 /* Write the source file position */
701 ObjWritePos (&S->Pos);
706 /* Done writing exports */
712 void WriteDbgSyms (void)
713 /* Write a list of all symbols to the object file */
718 /* Tell the object file module that we're about to start the debug info */
721 /* Check if debug info is requested */
724 /* Walk through the list and count the symbols */
728 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
734 /* Write the symbol count to the list */
737 /* Walk through list and write all symbols to the file */
740 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
744 /* Get the expression bits */
745 unsigned char ExprMask = (SymIsConst (S, &ConstVal))? EXP_CONST : EXP_EXPR;
746 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
749 ObjWrite8 (ExprMask);
751 /* Write the address size */
752 ObjWrite8 (S->AddrSize);
755 ObjWriteVar (S->Name);
757 /* Write the value */
758 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
760 ObjWrite32 (ConstVal);
762 /* Expression involved */
763 WriteExpr (S->V.Expr);
766 /* Write the source file position */
767 ObjWritePos (&S->Pos);
774 /* No debug symbols */
779 /* Done writing debug symbols */
785 void WriteScopes (void)
786 /* Write the scope table to the object file */
788 /* Tell the object file module that we're about to start the scopes */
794 /* Done writing the scopes */