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 /*****************************************************************************/
57 /*****************************************************************************/
59 /*****************************************************************************/
63 /* Combined symbol entry flags used within this module */
64 #define SF_UNDEFMASK (SF_REFERENCED | SF_DEFINED | SF_IMPORT)
65 #define SF_UNDEFVAL (SF_REFERENCED)
66 #define SF_EXPMASK (SF_TRAMPOLINE | SF_EXPORT)
67 #define SF_EXPVAL (SF_EXPORT)
68 #define SF_DBGINFOMASK (SF_TRAMPOLINE | SF_DEFINED | SF_EXPORT | SF_IMPORT)
69 #define SF_DBGINFOVAL (SF_DEFINED)
72 SymTable* CurrentScope = 0; /* Pointer to current symbol table */
73 SymTable* RootScope = 0; /* Root symbol table */
75 /* Symbol table variables */
76 static unsigned ImportCount = 0;/* Counter for import symbols */
77 static unsigned ExportCount = 0;/* Counter for export symbols */
81 /*****************************************************************************/
82 /* Internally used functions */
83 /*****************************************************************************/
87 static unsigned ScopeTableSize (unsigned Level)
88 /* Get the size of a table for the given lexical level */
99 static SymTable* NewSymTable (SymTable* Parent, const char* Name)
100 /* Allocate a symbol table on the heap and return it */
102 /* Determine the lexical level and the number of table slots */
103 unsigned Level = Parent? Parent->Level + 1 : 0;
104 unsigned Slots = ScopeTableSize (Level);
106 /* Allocate memory */
107 SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
109 /* Set variables and clear hash table entries */
114 S->AddrSize = ADDR_SIZE_DEFAULT;
117 S->TableSlots = Slots;
120 S->Name = GetStringId (Name);
125 /* Insert the symbol table into the child tree of the parent */
127 SymTable* T = Parent->Childs;
133 /* Choose next entry */
134 int Cmp = strcmp (Name, GetString (T->Name));
142 } else if (Cmp > 0) {
150 /* Duplicate scope name */
151 Internal ("Duplicate scope name: `%s'", Name);
157 /* Return the prepared struct */
163 static int SearchSymTree (SymEntry* T, const char* Name, SymEntry** E)
164 /* Search in the given tree for a name. If we find the symbol, the function
165 * will return 0 and put the entry pointer into E. If we did not find the
166 * symbol, and the tree is empty, E is set to NULL. If the tree is not empty,
167 * E will be set to the last entry, and the result of the function is <0 if
168 * the entry should be inserted on the left side, and >0 if it should get
169 * inserted on the right side.
172 /* Is there a tree? */
178 /* We have a table, search it */
181 /* Get the symbol name */
182 const char* SymName = GetString (T->Name);
184 /* Choose next entry */
185 int Cmp = strcmp (Name, SymName);
186 if (Cmp < 0 && T->Left) {
188 } else if (Cmp > 0&& T->Right) {
191 /* Found or end of search, return the result */
200 /*****************************************************************************/
202 /*****************************************************************************/
206 void SymEnterLevel (const char* ScopeName, unsigned AddrSize)
207 /* Enter a new lexical level */
209 /* Map a default address size to something real */
210 if (AddrSize == ADDR_SIZE_DEFAULT) {
211 /* Use the segment address size */
212 AddrSize = GetCurrentSegAddrSize ();
215 /* If we have a current scope, search for the given name and create a
216 * new one if it doesn't exist. If this is the root scope, just create it.
219 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
221 /* Check if the scope has been defined before */
222 if (CurrentScope->Flags & ST_DEFINED) {
223 Error ("Duplicate scope `%s'", ScopeName);
226 CurrentScope = RootScope = NewSymTable (0, ScopeName);
229 /* Mark the scope as defined */
230 CurrentScope->Flags |= ST_DEFINED;
235 void SymLeaveLevel (void)
236 /* Leave the current lexical level */
238 CurrentScope = CurrentScope->Parent;
243 SymTable* SymFindScope (SymTable* Parent, const char* Name, int AllocNew)
244 /* Find a scope in the given enclosing scope */
246 SymTable** T = &Parent->Childs;
248 int Cmp = strcmp (Name, GetString ((*T)->Name));
251 } else if (Cmp > 0) {
254 /* Found the scope */
259 /* Create a new scope if requested and we didn't find one */
260 if (*T == 0 && AllocNew) {
261 *T = NewSymTable (Parent, Name);
264 /* Return the scope */
270 SymEntry* SymFind (SymTable* Scope, const char* Name, int AllocNew)
271 /* Find a new symbol table entry in the given table. If AllocNew is given and
272 * the entry is not found, create a new one. Return the entry found, or the
273 * new entry created, or - in case AllocNew is zero - return 0.
279 if (IsLocalName (Name)) {
281 /* Local symbol, get the table */
283 /* No last global, so there's no local table */
284 Error ("No preceeding global symbol");
286 return NewSymEntry (Name);
292 /* Search for the symbol if we have a table */
293 Cmp = SearchSymTree (SymLast->Locals, Name, &S);
295 /* If we found an entry, return it */
302 /* Otherwise create a new entry, insert and return it */
303 SymEntry* N = NewSymEntry (Name);
306 } else if (Cmp < 0) {
316 /* Global symbol: Get the hash value for the name */
317 unsigned Hash = HashStr (Name) % Scope->TableSlots;
319 /* Search for the entry */
320 Cmp = SearchSymTree (Scope->Table[Hash], Name, &S);
322 /* If we found an entry, return it */
324 /* Check for a trampoline entry, in this case return the real
327 while (S->Flags & SF_TRAMPOLINE) {
335 /* Otherwise create a new entry, insert and return it */
336 SymEntry* N = NewSymEntry (Name);
338 Scope->Table[Hash] = N;
339 } else if (Cmp < 0) {
345 ++Scope->TableEntries;
351 /* We did not find the entry and AllocNew is false. */
357 static SymEntry* SymFindAny (SymTable* Scope, const char* Name)
358 /* Find a symbol in the given or any of its parent scopes. The function will
359 * never create a new symbol, since this can only be done in one specific
365 /* Search in the current table */
366 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
368 /* Found, return it */
371 /* Not found, search in the parent scope, if we have one */
372 Scope = Scope->Parent;
374 } while (Sym == 0 && Scope != 0);
382 void SymConDes (const char* Name, unsigned Type, unsigned Prio)
383 /* Mark the given symbol as a module constructor/destructor. This will also
384 * mark the symbol as an export. Initializers may never be zero page symbols.
389 /* Check the parameters */
390 #if (CD_TYPE_MIN != 0)
391 CHECK (Type >= CD_TYPE_MIN && Type <= CD_TYPE_MAX);
393 CHECK (Type <= CD_TYPE_MAX);
395 CHECK (Prio >= CD_PRIO_MIN && Prio <= CD_PRIO_MAX);
397 /* Don't accept local symbols */
398 if (IsLocalName (Name)) {
399 Error ("Illegal use of a local symbol");
403 /* Do we have such a symbol? */
404 S = SymFind (CurrentScope, Name, SYM_ALLOC_NEW);
405 if (S->Flags & SF_IMPORT) {
406 /* The symbol is already marked as imported external symbol */
407 Error ("Symbol `%s' is already an import", Name);
411 /* If the symbol is marked as global, silently remove the global flag */
412 if (S->Flags & SF_GLOBAL) {
413 S->Flags &= ~SF_GLOBAL;
416 /* Check if the symbol was not already defined as ZP symbol */
417 if (S->AddrSize == ADDR_SIZE_ZP) {
418 Error ("Redeclaration mismatch for symbol `%s'", Name);
421 /* If the symbol was already declared as a condes, check if the new
422 * priority value is the same as the old one.
424 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
425 if (S->ConDesPrio[Type] != Prio) {
426 Error ("Redeclaration mismatch for symbol `%s'", Name);
429 S->ConDesPrio[Type] = Prio;
431 /* Set the symbol data */
432 S->Flags |= SF_EXPORT | SF_REFERENCED;
437 int SymIsConst (SymEntry* S)
438 /* Return true if the given symbol has a constant value */
440 /* Resolve trampoline entries */
441 if (S->Flags & SF_TRAMPOLINE) {
445 /* Check for constness */
446 if (S->Flags & SF_CONST) {
448 } else if ((S->Flags & SF_DEFINED) && IsConstExpr (S->V.Expr)) {
449 /* Constant expression, remember the value */
450 ExprNode* Expr = S->V.Expr;
451 S->Flags |= SF_CONST;
452 S->V.Val = GetExprVal (Expr);
461 int SymIsZP (SymEntry* S)
462 /* Return true if the symbol is explicitly marked as zeropage symbol */
464 /* Resolve trampoline entries */
465 if (S->Flags & SF_TRAMPOLINE) {
469 /* If the symbol is not a global symbol, was not defined before, check the
470 * enclosing scope for a symbol with the same name, and return the ZP
471 * attribute of this symbol if we find one.
473 if (!IsLocalNameId (S->Name) && (S->Flags & (SF_DEFINED | SF_IMPORT)) == 0 &&
474 S->SymTab->Parent != 0) {
476 /* Try to find a symbol with the same name in the enclosing scope */
477 SymEntry* E = SymFindAny (S->SymTab->Parent, GetString (S->Name));
479 /* If we found one, use the ZP flag */
480 if (E && E->AddrSize == ADDR_SIZE_ZP) {
481 S->AddrSize = ADDR_SIZE_ZP;
485 /* Check the ZP flag */
486 return (S->AddrSize == ADDR_SIZE_ZP);
491 static void SymCheckUndefined (SymEntry* S)
492 /* Handle an undefined symbol */
494 /* Undefined symbol. It may be...
496 * - An undefined symbol in a nested lexical level. In this
497 * case, search for the symbol in the higher levels and
498 * make the entry a trampoline entry if we find one.
500 * - If the symbol is not found, it is a real undefined symbol.
501 * If the AutoImport flag is set, make it an import. If the
502 * AutoImport flag is not set, it's an error.
506 /* It's a global symbol, get the higher level table */
507 SymTable* Tab = S->SymTab->Parent;
509 Sym = SymFindAny (Tab, GetString (S->Name));
511 if (Sym->Flags & (SF_DEFINED | SF_IMPORT)) {
512 /* We've found a symbol in a higher level that is
513 * either defined in the source, or an import.
517 /* The symbol found is undefined itself. Look further */
518 Tab = Sym->SymTab->Parent;
521 /* No symbol found */
527 /* We found the symbol in a higher level. Make S a trampoline
528 * symbol. Beware: We have to transfer the symbol attributes to
529 * the real symbol and check for any conflicts.
531 S->Flags |= SF_TRAMPOLINE;
534 /* Transfer the flags. Note: S may not be imported, since in that
535 * case it wouldn't be undefined.
537 if (S->Flags & SF_EXPORT) {
538 if (Sym->Flags & SF_IMPORT) {
539 /* The symbol is already marked as imported external symbol */
540 PError (&S->Pos, "Symbol `%s' is already an import", GetString (S->Name));
542 Sym->Flags |= (S->Flags & SF_EXPORT);
543 Sym->ExportSize = S->ExportSize;
546 /* Transfer the referenced flag */
547 Sym->Flags |= (S->Flags & SF_REFERENCED);
550 /* The symbol is definitely undefined */
551 if (S->Flags & SF_EXPORT) {
552 /* We will not auto-import an export */
553 PError (&S->Pos, "Exported symbol `%s' was never defined",
554 GetString (S->Name));
557 /* Mark as import, will be indexed later */
558 S->Flags |= SF_IMPORT;
561 PError (&S->Pos, "Symbol `%s' is undefined", GetString (S->Name));
570 /* Run through all symbols and check for anomalies and errors */
574 /* Check for open scopes */
575 if (CurrentScope->Parent != 0) {
576 Error ("Local scope was not closed");
579 /* First pass: Walk through all symbols, checking for undefined's and
580 * changing them to trampoline symbols or make them imports.
584 /* If the symbol is marked as global, mark it as export, if it is
585 * already defined, otherwise mark it as import.
587 if (S->Flags & SF_GLOBAL) {
588 S->Flags &= ~SF_GLOBAL;
589 if (S->Flags & SF_DEFINED) {
590 S->Flags |= SF_EXPORT;
592 S->Flags |= SF_IMPORT;
596 /* Handle undefined symbols */
597 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
598 /* This is an undefined symbol. Handle it. */
599 SymCheckUndefined (S);
606 /* Second pass: Walk again through the symbols. Ignore undefined's, since
607 * we handled them in the last pass, and ignore trampoline symbols, since
608 * we handled them in the last pass, too.
612 if ((S->Flags & SF_TRAMPOLINE) == 0 &&
613 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
614 if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
615 /* Symbol was defined but never referenced */
616 PWarning (&S->Pos, 2,
617 "Symbol `%s' is defined but never used",
618 GetString (S->Name));
620 if (S->Flags & SF_IMPORT) {
621 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
622 /* Imported symbol is not referenced */
623 PWarning (&S->Pos, 2,
624 "Symbol `%s' is imported but never used",
625 GetString (S->Name));
627 /* Give the import an index, count imports */
628 S->Index = ImportCount++;
629 S->Flags |= SF_INDEXED;
632 if (S->Flags & SF_EXPORT) {
633 /* Give the export an index, count exports */
634 S->Index = ExportCount++;
635 S->Flags |= SF_INDEXED;
646 void SymDump (FILE* F)
647 /* Dump the symbol table */
649 SymEntry* S = SymList;
652 /* Ignore trampoline symbols */
653 if ((S->Flags & SF_TRAMPOLINE) != 0) {
655 "%-24s %s %s %s %s %s\n",
657 (S->Flags & SF_DEFINED)? "DEF" : "---",
658 (S->Flags & SF_REFERENCED)? "REF" : "---",
659 (S->Flags & SF_IMPORT)? "IMP" : "---",
660 (S->Flags & SF_EXPORT)? "EXP" : "---",
661 AddrSizeToStr (S->AddrSize));
670 void WriteImports (void)
671 /* Write the imports list to the object file */
675 /* Tell the object file module that we're about to start the imports */
678 /* Write the import count to the list */
679 ObjWriteVar (ImportCount);
681 /* Walk throught list and write all valid imports to the file. An import
682 * is considered valid, if it is either referenced, or the forced bit is
683 * set. Otherwise, the import is ignored (no need to link in something
688 if ((S->Flags & (SF_TRAMPOLINE | SF_IMPORT)) == SF_IMPORT &&
689 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
691 if (S->AddrSize == ADDR_SIZE_ZP) {
696 ObjWriteVar (S->Name);
697 ObjWritePos (&S->Pos);
702 /* Done writing imports */
708 static unsigned char GetExportExprMask (SymEntry* S)
709 /* Return the expression bits for the given symbol table entry */
711 unsigned char ExprMask;
713 /* Check if the symbol is const */
714 ExprMask = (SymIsConst (S))? EXP_CONST : EXP_EXPR;
716 /* Add zeropage/abs bits */
717 ExprMask |= (S->ExportSize == ADDR_SIZE_ZP)? EXP_ZP : EXP_ABS;
719 /* Add the label/equate bits */
720 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
722 /* Return the mask */
728 void WriteExports (void)
729 /* Write the exports list to the object file */
734 /* Tell the object file module that we're about to start the exports */
737 /* Write the export count to the list */
738 ObjWriteVar (ExportCount);
740 /* Walk throught list and write all exports to the file */
743 if ((S->Flags & SF_EXPMASK) == SF_EXPVAL) {
744 unsigned char ExprMask;
746 /* Finalize an associated expression if we have one */
749 /* Get the expression bits */
750 ExprMask = GetExportExprMask (S);
752 /* Count the number of ConDes types */
753 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
754 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
755 INC_EXP_CONDES_COUNT (ExprMask);
760 ObjWrite8 (ExprMask);
762 /* Write any ConDes declarations */
763 if (GET_EXP_CONDES_COUNT (ExprMask) > 0) {
764 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
765 unsigned char Prio = S->ConDesPrio[Type];
766 if (Prio != CD_PRIO_NONE) {
767 ObjWrite8 (CD_BUILD (Type, Prio));
773 ObjWriteVar (S->Name);
775 /* Write the value */
776 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
778 ObjWrite32 (S->V.Val);
780 /* Expression involved */
781 WriteExpr (S->V.Expr);
784 /* Write the source file position */
785 ObjWritePos (&S->Pos);
790 /* Done writing exports */
796 static unsigned char GetDbgExprMask (SymEntry* S)
797 /* Return the expression bits for the given symbol table entry */
799 unsigned char ExprMask;
801 /* Check if the symbol is const */
802 ExprMask = (SymIsConst (S))? EXP_CONST : EXP_EXPR;
804 /* Add zeropage/abs bits */
805 ExprMask |= (S->AddrSize == ADDR_SIZE_ZP)? EXP_ZP : EXP_ABS;
807 /* Add the label/equate bits */
808 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
810 /* Return the mask */
816 void WriteDbgSyms (void)
817 /* Write a list of all symbols to the object file */
822 /* Tell the object file module that we're about to start the debug info */
825 /* Check if debug info is requested */
828 /* Walk through the list and count the symbols */
832 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
838 /* Write the symbol count to the list */
841 /* Walk through list and write all symbols to the file */
844 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
845 unsigned char ExprMask;
847 /* Finalize an associated expression if we have one */
850 /* Get the expression bits */
851 ExprMask = GetDbgExprMask (S);
854 ObjWrite8 (ExprMask);
857 ObjWriteVar (S->Name);
859 /* Write the value */
860 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
862 ObjWrite32 (S->V.Val);
864 /* Expression involved */
865 WriteExpr (S->V.Expr);
868 /* Write the source file position */
869 ObjWritePos (&S->Pos);
876 /* No debug symbols */
881 /* Done writing debug symbols */