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 char Type, unsigned char 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.
220 /* Search for the scope, create a new one */
221 CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
223 /* Check if the scope has been defined before */
224 if (CurrentScope->Flags & ST_DEFINED) {
225 Error ("Duplicate scope `%s'", ScopeName);
229 CurrentScope = RootScope = NewSymTable (0, ScopeName);
232 /* Mark the scope as defined and set type and address size */
233 CurrentScope->Flags |= ST_DEFINED;
234 CurrentScope->AddrSize = AddrSize;
235 CurrentScope->Type = Type;
240 void SymLeaveLevel (void)
241 /* Leave the current lexical level */
243 CurrentScope = CurrentScope->Parent;
248 SymTable* SymFindScope (SymTable* Parent, const char* Name, int AllocNew)
249 /* Find a scope in the given enclosing scope */
251 SymTable** T = &Parent->Childs;
253 int Cmp = strcmp (Name, GetString ((*T)->Name));
256 } else if (Cmp > 0) {
259 /* Found the scope */
264 /* Create a new scope if requested and we didn't find one */
265 if (*T == 0 && AllocNew) {
266 *T = NewSymTable (Parent, Name);
269 /* Return the scope */
275 SymEntry* SymFind (SymTable* Scope, const char* Name, int AllocNew)
276 /* Find a new symbol table entry in the given table. If AllocNew is given and
277 * the entry is not found, create a new one. Return the entry found, or the
278 * new entry created, or - in case AllocNew is zero - return 0.
284 if (IsLocalName (Name)) {
286 /* Local symbol, get the table */
288 /* No last global, so there's no local table */
289 Error ("No preceeding global symbol");
291 return NewSymEntry (Name);
297 /* Search for the symbol if we have a table */
298 Cmp = SearchSymTree (SymLast->Locals, Name, &S);
300 /* If we found an entry, return it */
307 /* Otherwise create a new entry, insert and return it */
308 SymEntry* N = NewSymEntry (Name);
311 } else if (Cmp < 0) {
321 /* Global symbol: Get the hash value for the name */
322 unsigned Hash = HashStr (Name) % Scope->TableSlots;
324 /* Search for the entry */
325 Cmp = SearchSymTree (Scope->Table[Hash], Name, &S);
327 /* If we found an entry, return it */
329 /* Check for a trampoline entry, in this case return the real
332 while (S->Flags & SF_TRAMPOLINE) {
340 /* Otherwise create a new entry, insert and return it */
341 SymEntry* N = NewSymEntry (Name);
343 Scope->Table[Hash] = N;
344 } else if (Cmp < 0) {
350 ++Scope->TableEntries;
356 /* We did not find the entry and AllocNew is false. */
362 static SymEntry* SymFindAny (SymTable* Scope, const char* Name)
363 /* Find a symbol in the given or any of its parent scopes. The function will
364 * never create a new symbol, since this can only be done in one specific
370 /* Search in the current table */
371 Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
373 /* Found, return it */
376 /* Not found, search in the parent scope, if we have one */
377 Scope = Scope->Parent;
379 } while (Sym == 0 && Scope != 0);
387 int SymIsZP (SymEntry* S)
388 /* Return true if the symbol is explicitly marked as zeropage symbol */
390 /* Resolve trampoline entries */
391 if (S->Flags & SF_TRAMPOLINE) {
395 /* If the symbol is not a global symbol, was not defined before, check the
396 * enclosing scope for a symbol with the same name, and return the ZP
397 * attribute of this symbol if we find one.
399 if (!IsLocalNameId (S->Name) && (S->Flags & (SF_DEFINED | SF_IMPORT)) == 0 &&
400 S->SymTab->Parent != 0) {
402 /* Try to find a symbol with the same name in the enclosing scope */
403 SymEntry* E = SymFindAny (S->SymTab->Parent, GetString (S->Name));
405 /* If we found one, use the ZP flag */
406 if (E && E->AddrSize == ADDR_SIZE_ZP) {
407 S->AddrSize = ADDR_SIZE_ZP;
411 /* Check the ZP flag */
412 return (S->AddrSize == ADDR_SIZE_ZP);
417 unsigned char GetCurrentSymTabType ()
418 /* Return the type of the current symbol table */
420 CHECK (CurrentScope != 0);
421 return CurrentScope->Type;
426 static void SymCheckUndefined (SymEntry* S)
427 /* Handle an undefined symbol */
429 /* Undefined symbol. It may be...
431 * - An undefined symbol in a nested lexical level. In this
432 * case, search for the symbol in the higher levels and
433 * make the entry a trampoline entry if we find one.
435 * - If the symbol is not found, it is a real undefined symbol.
436 * If the AutoImport flag is set, make it an import. If the
437 * AutoImport flag is not set, it's an error.
441 /* It's a global symbol, get the higher level table */
442 SymTable* Tab = S->SymTab->Parent;
444 Sym = SymFindAny (Tab, GetString (S->Name));
446 if (Sym->Flags & (SF_DEFINED | SF_IMPORT)) {
447 /* We've found a symbol in a higher level that is
448 * either defined in the source, or an import.
452 /* The symbol found is undefined itself. Look further */
453 Tab = Sym->SymTab->Parent;
456 /* No symbol found */
462 /* We found the symbol in a higher level. Make S a trampoline
463 * symbol. Beware: We have to transfer the symbol attributes to
464 * the real symbol and check for any conflicts.
466 S->Flags |= SF_TRAMPOLINE;
469 /* Transfer the flags. Note: S may not be imported, since in that
470 * case it wouldn't be undefined.
472 if (S->Flags & SF_EXPORT) {
473 if (Sym->Flags & SF_IMPORT) {
474 /* The symbol is already marked as imported external symbol */
475 PError (&S->Pos, "Symbol `%s' is already an import", GetString (S->Name));
477 Sym->Flags |= (S->Flags & SF_EXPORT);
478 Sym->ExportSize = S->ExportSize;
481 /* Transfer the referenced flag */
482 Sym->Flags |= (S->Flags & SF_REFERENCED);
485 /* The symbol is definitely undefined */
486 if (S->Flags & SF_EXPORT) {
487 /* We will not auto-import an export */
488 PError (&S->Pos, "Exported symbol `%s' was never defined",
489 GetString (S->Name));
492 /* Mark as import, will be indexed later */
493 S->Flags |= SF_IMPORT;
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 S->Flags &= ~SF_GLOBAL;
524 if (S->Flags & SF_DEFINED) {
525 S->Flags |= SF_EXPORT;
527 S->Flags |= SF_IMPORT;
531 /* Handle undefined symbols */
532 if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
533 /* This is an undefined symbol. Handle it. */
534 SymCheckUndefined (S);
541 /* Second pass: Walk again through the symbols. Ignore undefined's, since
542 * we handled them in the last pass, and ignore trampoline symbols, since
543 * we handled them in the last pass, too.
547 if ((S->Flags & SF_TRAMPOLINE) == 0 &&
548 (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
549 if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
550 /* Symbol was defined but never referenced */
551 PWarning (&S->Pos, 2,
552 "Symbol `%s' is defined but never used",
553 GetString (S->Name));
555 if (S->Flags & SF_IMPORT) {
556 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
557 /* Imported symbol is not referenced */
558 PWarning (&S->Pos, 2,
559 "Symbol `%s' is imported but never used",
560 GetString (S->Name));
562 /* Give the import an index, count imports */
563 S->Index = ImportCount++;
564 S->Flags |= SF_INDEXED;
567 if (S->Flags & SF_EXPORT) {
568 /* Give the export an index, count exports */
569 S->Index = ExportCount++;
570 S->Flags |= SF_INDEXED;
581 void SymDump (FILE* F)
582 /* Dump the symbol table */
584 SymEntry* S = SymList;
587 /* Ignore trampoline symbols */
588 if ((S->Flags & SF_TRAMPOLINE) != 0) {
590 "%-24s %s %s %s %s %s\n",
592 (S->Flags & SF_DEFINED)? "DEF" : "---",
593 (S->Flags & SF_REFERENCED)? "REF" : "---",
594 (S->Flags & SF_IMPORT)? "IMP" : "---",
595 (S->Flags & SF_EXPORT)? "EXP" : "---",
596 AddrSizeToStr (S->AddrSize));
605 void WriteImports (void)
606 /* Write the imports list to the object file */
610 /* Tell the object file module that we're about to start the imports */
613 /* Write the import count to the list */
614 ObjWriteVar (ImportCount);
616 /* Walk throught list and write all valid imports to the file. An import
617 * is considered valid, if it is either referenced, or the forced bit is
618 * set. Otherwise, the import is ignored (no need to link in something
623 if ((S->Flags & (SF_TRAMPOLINE | SF_IMPORT)) == SF_IMPORT &&
624 (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
626 if (S->AddrSize == ADDR_SIZE_ZP) {
631 ObjWriteVar (S->Name);
632 ObjWritePos (&S->Pos);
637 /* Done writing imports */
643 void WriteExports (void)
644 /* Write the exports list to the object file */
649 /* Tell the object file module that we're about to start the exports */
652 /* Write the export count to the list */
653 ObjWriteVar (ExportCount);
655 /* Walk throught list and write all exports to the file */
658 if ((S->Flags & SF_EXPMASK) == SF_EXPVAL) {
662 /* Get the expression bits */
663 unsigned char ExprMask = SymIsConst (S, &ConstVal)? EXP_CONST : EXP_EXPR;
664 ExprMask |= (S->ExportSize == ADDR_SIZE_ZP)? EXP_ZP : EXP_ABS;
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);
675 ObjWrite8 (ExprMask);
677 /* Write any ConDes declarations */
678 if (GET_EXP_CONDES_COUNT (ExprMask) > 0) {
679 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
680 unsigned char Prio = S->ConDesPrio[Type];
681 if (Prio != CD_PRIO_NONE) {
682 ObjWrite8 (CD_BUILD (Type, Prio));
688 ObjWriteVar (S->Name);
690 /* Write the value */
691 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
693 ObjWrite32 (ConstVal);
695 /* Expression involved */
696 WriteExpr (S->V.Expr);
699 /* Write the source file position */
700 ObjWritePos (&S->Pos);
705 /* Done writing exports */
711 void WriteDbgSyms (void)
712 /* Write a list of all symbols to the object file */
717 /* Tell the object file module that we're about to start the debug info */
720 /* Check if debug info is requested */
723 /* Walk through the list and count the symbols */
727 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
733 /* Write the symbol count to the list */
736 /* Walk through list and write all symbols to the file */
739 if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
743 /* Get the expression bits */
744 unsigned char ExprMask = (SymIsConst (S, &ConstVal))? EXP_CONST : EXP_EXPR;
745 ExprMask |= (S->AddrSize == ADDR_SIZE_ZP)? EXP_ZP : EXP_ABS;
746 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
749 ObjWrite8 (ExprMask);
752 ObjWriteVar (S->Name);
754 /* Write the value */
755 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
757 ObjWrite32 (ConstVal);
759 /* Expression involved */
760 WriteExpr (S->V.Expr);
763 /* Write the source file position */
764 ObjWritePos (&S->Pos);
771 /* No debug symbols */
776 /* Done writing debug symbols */