]> git.sur5r.net Git - cc65/blob - src/ca65/symtab.c
d21d0e1eb73f5833d326b7b677a72a98a3ca77ea
[cc65] / src / ca65 / symtab.c
1 /*****************************************************************************/
2 /*                                                                           */
3 /*                                 symtab.c                                  */
4 /*                                                                           */
5 /*                 Symbol table for the ca65 macroassembler                  */
6 /*                                                                           */
7 /*                                                                           */
8 /*                                                                           */
9 /* (C) 1998-2003 Ullrich von Bassewitz                                       */
10 /*               Römerstraße 52                                              */
11 /*               D-70794 Filderstadt                                         */
12 /* EMail:        uz@cc65.org                                                 */
13 /*                                                                           */
14 /*                                                                           */
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.                                    */
18 /*                                                                           */
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:                            */
22 /*                                                                           */
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              */
30 /*    distribution.                                                          */
31 /*                                                                           */
32 /*****************************************************************************/
33
34
35
36 #include <string.h>
37
38 /* common */
39 #include "addrsize.h"
40 #include "check.h"
41 #include "hashstr.h"
42 #include "symdefs.h"
43 #include "xmalloc.h"
44
45 /* ca65 */
46 #include "global.h"
47 #include "error.h"
48 #include "expr.h"
49 #include "objfile.h"
50 #include "scanner.h"
51 #include "segment.h"
52 #include "spool.h"
53 #include "symtab.h"
54
55
56
57 /*****************************************************************************/
58 /*                                   Data                                    */
59 /*****************************************************************************/
60
61
62
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)
70
71 /* Symbol tables */
72 SymTable*       CurrentScope = 0;       /* Pointer to current symbol table */
73 SymTable*       RootScope    = 0;       /* Root symbol table */
74
75 /* Symbol table variables */
76 static unsigned         ImportCount = 0;/* Counter for import symbols */
77 static unsigned         ExportCount = 0;/* Counter for export symbols */
78
79
80
81 /*****************************************************************************/
82 /*                         Internally used functions                         */
83 /*****************************************************************************/
84
85
86
87 static unsigned ScopeTableSize (unsigned Level)
88 /* Get the size of a table for the given lexical level */
89 {
90     switch (Level) {
91         case 0:         return 213;
92         case 1:         return  53;
93         default:        return  29;
94     }
95 }
96
97
98
99 static SymTable* NewSymTable (SymTable* Parent, const char* Name)
100 /* Allocate a symbol table on the heap and return it */
101 {
102     /* Determine the lexical level and the number of table slots */
103     unsigned Level = Parent? Parent->Level + 1 : 0;
104     unsigned Slots = ScopeTableSize (Level);
105
106     /* Allocate memory */
107     SymTable* S = xmalloc (sizeof (SymTable) + (Slots-1) * sizeof (SymEntry*));
108
109     /* Set variables and clear hash table entries */
110     S->Left         = 0;
111     S->Right        = 0;
112     S->Childs       = 0;
113     S->Flags        = ST_NONE;
114     S->AddrSize     = ADDR_SIZE_DEFAULT;
115     S->Type         = ST_UNDEF;
116     S->Level        = Level;
117     S->TableSlots   = Slots;
118     S->TableEntries = 0;
119     S->Parent       = Parent;
120     S->Name         = GetStringId (Name);
121     while (Slots--) {
122         S->Table[Slots] = 0;
123     }
124
125     /* Insert the symbol table into the child tree of the parent */
126     if (Parent) {
127         SymTable* T = Parent->Childs;
128         if (T == 0) {
129             /* First entry */
130             Parent->Childs = S;
131         } else {
132             while (1) {
133                 /* Choose next entry */
134                 int Cmp = strcmp (Name, GetString (T->Name));
135                 if (Cmp < 0) {
136                     if (T->Left) {
137                         T = T->Left;
138                     } else {
139                         T->Left = S;
140                         break;
141                     }
142                 } else if (Cmp > 0) {
143                     if (T->Right) {
144                         T = T->Right;
145                     } else {
146                         T->Right = S;
147                         break;
148                     }
149                 } else {
150                     /* Duplicate scope name */
151                     Internal ("Duplicate scope name: `%s'", Name);
152                 }
153             }
154         }
155     }
156
157     /* Return the prepared struct */
158     return S;
159 }
160
161
162
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.
170  */
171 {
172     /* Is there a tree? */
173     if (T == 0) {
174         *E = 0;
175         return 1;
176     }
177
178     /* We have a table, search it */
179     while (1) {
180
181         /* Get the symbol name */
182         const char* SymName = GetString (T->Name);
183
184         /* Choose next entry */
185         int Cmp = strcmp (Name, SymName);
186         if (Cmp < 0 && T->Left) {
187             T = T->Left;
188         } else if (Cmp > 0&& T->Right) {
189             T = T->Right;
190         } else {
191             /* Found or end of search, return the result */
192             *E = T;
193             return Cmp;
194         }
195     }
196 }
197
198
199
200 /*****************************************************************************/
201 /*                                   Code                                    */
202 /*****************************************************************************/
203
204
205
206 void SymEnterLevel (const char* ScopeName, unsigned char Type, unsigned char AddrSize)
207 /* Enter a new lexical level */
208 {
209     /* Map a default address size to something real */
210     if (AddrSize == ADDR_SIZE_DEFAULT) {
211         /* Use the segment address size */
212         AddrSize = GetCurrentSegAddrSize ();
213     }
214
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.
217      */
218     if (CurrentScope) {
219
220         /* Search for the scope, create a new one */
221         CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
222
223         /* Check if the scope has been defined before */
224         if (CurrentScope->Flags & ST_DEFINED) {
225             Error ("Duplicate scope `%s'", ScopeName);
226         }
227
228     } else {
229         CurrentScope = RootScope = NewSymTable (0, ScopeName);
230     }
231
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;
236 }
237
238
239
240 void SymLeaveLevel (void)
241 /* Leave the current lexical level */
242 {
243     CurrentScope = CurrentScope->Parent;
244 }
245
246
247
248 SymTable* SymFindScope (SymTable* Parent, const char* Name, int AllocNew)
249 /* Find a scope in the given enclosing scope */
250 {
251     SymTable** T = &Parent->Childs;
252     while (*T) {
253         int Cmp = strcmp (Name, GetString ((*T)->Name));
254         if (Cmp < 0) {
255             T = &(*T)->Left;
256         } else if (Cmp > 0) {
257             T = &(*T)->Right;
258         } else {
259             /* Found the scope */
260             return *T;
261         }
262     }
263
264     /* Create a new scope if requested and we didn't find one */
265     if (*T == 0 && AllocNew) {
266         *T = NewSymTable (Parent, Name);
267     }
268
269     /* Return the scope */
270     return *T;
271 }
272
273
274
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.
279  */
280 {
281     SymEntry* S;
282     int Cmp;
283
284     if (IsLocalName (Name)) {
285
286         /* Local symbol, get the table */
287         if (!SymLast) {
288             /* No last global, so there's no local table */
289             Error ("No preceeding global symbol");
290             if (AllocNew) {
291                 return NewSymEntry (Name);
292             } else {
293                 return 0;
294             }
295         }
296
297         /* Search for the symbol if we have a table */
298         Cmp = SearchSymTree (SymLast->Locals, Name, &S);
299
300         /* If we found an entry, return it */
301         if (Cmp == 0) {
302             return S;
303         }
304
305         if (AllocNew) {
306
307             /* Otherwise create a new entry, insert and return it */
308             SymEntry* N = NewSymEntry (Name);
309             if (S == 0) {
310                 SymLast->Locals = N;
311             } else if (Cmp < 0) {
312                 S->Left = N;
313             } else {
314                 S->Right = N;
315             }
316             return N;
317         }
318
319     } else {
320
321         /* Global symbol: Get the hash value for the name */
322         unsigned Hash = HashStr (Name) % Scope->TableSlots;
323
324         /* Search for the entry */
325         Cmp = SearchSymTree (Scope->Table[Hash], Name, &S);
326
327         /* If we found an entry, return it */
328         if (Cmp == 0) {
329             /* Check for a trampoline entry, in this case return the real
330              * symbol.
331              */
332             while (S->Flags & SF_TRAMPOLINE) {
333                 S = S->V.Sym;
334             }
335             return S;
336         }
337
338         if (AllocNew) {
339
340             /* Otherwise create a new entry, insert and return it */
341             SymEntry* N = NewSymEntry (Name);
342             if (S == 0) {
343                 Scope->Table[Hash] = N;
344             } else if (Cmp < 0) {
345                 S->Left = N;
346             } else {
347                 S->Right = N;
348             }
349             N->SymTab = Scope;
350             ++Scope->TableEntries;
351             return N;
352
353         }
354     }
355
356     /* We did not find the entry and AllocNew is false. */
357     return 0;
358 }
359
360
361
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
365  * scope.
366  */
367 {
368     SymEntry* Sym;
369     do {
370         /* Search in the current table */
371         Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
372         if (Sym) {
373             /* Found, return it */
374             return Sym;
375         } else {
376             /* Not found, search in the parent scope, if we have one */
377             Scope = Scope->Parent;
378         }
379     } while (Sym == 0 && Scope != 0);
380
381     /* Not found */
382     return 0;
383 }
384
385
386
387 int SymIsZP (SymEntry* S)
388 /* Return true if the symbol is explicitly marked as zeropage symbol */
389 {
390     /* Resolve trampoline entries */
391     if (S->Flags & SF_TRAMPOLINE) {
392         S = S->V.Sym;
393     }
394
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.
398      */
399     if (!IsLocalNameId (S->Name) && (S->Flags & (SF_DEFINED | SF_IMPORT)) == 0 &&
400         S->SymTab->Parent != 0) {
401
402         /* Try to find a symbol with the same name in the enclosing scope */
403         SymEntry* E = SymFindAny (S->SymTab->Parent, GetString (S->Name));
404
405         /* If we found one, use the ZP flag */
406         if (E && E->AddrSize == ADDR_SIZE_ZP) {
407             S->AddrSize = ADDR_SIZE_ZP;
408         }
409     }
410
411     /* Check the ZP flag */
412     return (S->AddrSize == ADDR_SIZE_ZP);
413 }
414
415
416
417 unsigned char GetCurrentSymTabType ()
418 /* Return the type of the current symbol table */
419 {
420     CHECK (CurrentScope != 0);
421     return CurrentScope->Type;
422 }
423
424
425
426 static void SymCheckUndefined (SymEntry* S)
427 /* Handle an undefined symbol */
428 {
429     /* Undefined symbol. It may be...
430      *
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.
434      *
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.
438      */
439     SymEntry* Sym = 0;
440     if (S->SymTab) {
441         /* It's a global symbol, get the higher level table */
442         SymTable* Tab = S->SymTab->Parent;
443         while (Tab) {
444             Sym = SymFindAny (Tab, GetString (S->Name));
445             if (Sym) {
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.
449                      */
450                      break;
451                 } else {
452                     /* The symbol found is undefined itself. Look further */
453                     Tab = Sym->SymTab->Parent;
454                 }
455             } else {
456                 /* No symbol found */
457                 break;
458             }
459         }
460     }
461     if (Sym) {
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.
465          */
466         S->Flags |= SF_TRAMPOLINE;
467         S->V.Sym = Sym;
468
469         /* Transfer the flags. Note: S may not be imported, since in that
470          * case it wouldn't be undefined.
471          */
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));
476             }
477             Sym->Flags |= (S->Flags & SF_EXPORT);
478             Sym->ExportSize = S->ExportSize;
479         }
480
481         /* Transfer the referenced flag */
482         Sym->Flags |= (S->Flags & SF_REFERENCED);
483
484     } else {
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));
490         } else {
491             if (AutoImport) {
492                 /* Mark as import, will be indexed later */
493                 S->Flags |= SF_IMPORT;
494             } else {
495                 /* Error */
496                 PError (&S->Pos, "Symbol `%s' is undefined", GetString (S->Name));
497             }
498         }
499     }
500 }
501
502
503
504 void SymCheck (void)
505 /* Run through all symbols and check for anomalies and errors */
506 {
507     SymEntry* S;
508
509     /* Check for open scopes */
510     if (CurrentScope->Parent != 0) {
511         Error ("Local scope was not closed");
512     }
513
514     /* First pass: Walk through all symbols, checking for undefined's and
515      * changing them to trampoline symbols or make them imports.
516      */
517     S = SymList;
518     while (S) {
519         /* If the symbol is marked as global, mark it as export, if it is
520          * already defined, otherwise mark it as import.
521          */
522         if (S->Flags & SF_GLOBAL) {
523             S->Flags &= ~SF_GLOBAL;
524             if (S->Flags & SF_DEFINED) {
525                 S->Flags |= SF_EXPORT;
526             } else {
527                 S->Flags |= SF_IMPORT;
528             }
529         }
530
531         /* Handle undefined symbols */
532         if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
533             /* This is an undefined symbol. Handle it. */
534             SymCheckUndefined (S);
535         }
536
537         /* Next symbol */
538         S = S->List;
539     }
540
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.
544      */
545     S = SymList;
546     while (S) {
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));
554             }
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));
561                 } else {
562                     /* Give the import an index, count imports */
563                     S->Index = ImportCount++;
564                     S->Flags |= SF_INDEXED;
565                 }
566             }
567             if (S->Flags & SF_EXPORT) {
568                 /* Give the export an index, count exports */
569                 S->Index = ExportCount++;
570                 S->Flags |= SF_INDEXED;
571             }
572         }
573
574         /* Next symbol */
575         S = S->List;
576     }
577 }
578
579
580
581 void SymDump (FILE* F)
582 /* Dump the symbol table */
583 {
584     SymEntry* S = SymList;
585
586     while (S) {
587         /* Ignore trampoline symbols */
588         if ((S->Flags & SF_TRAMPOLINE) != 0) {
589             fprintf (F,
590                      "%-24s %s %s %s %s %s\n",
591                      GetString (S->Name),
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));
597         }
598         /* Next symbol */
599         S = S->List;
600     }
601 }
602
603
604
605 void WriteImports (void)
606 /* Write the imports list to the object file */
607 {
608     SymEntry* S;
609
610     /* Tell the object file module that we're about to start the imports */
611     ObjStartImports ();
612
613     /* Write the import count to the list */
614     ObjWriteVar (ImportCount);
615
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
619      * that isn't used).
620      */
621     S = SymList;
622     while (S) {
623         if ((S->Flags & (SF_TRAMPOLINE | SF_IMPORT)) == SF_IMPORT &&
624             (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
625
626             if (S->AddrSize == ADDR_SIZE_ZP) {
627                 ObjWrite8 (IMP_ZP);
628             } else {
629                 ObjWrite8 (IMP_ABS);
630             }
631             ObjWriteVar (S->Name);
632             ObjWritePos (&S->Pos);
633         }
634         S = S->List;
635     }
636
637     /* Done writing imports */
638     ObjEndImports ();
639 }
640
641
642
643 void WriteExports (void)
644 /* Write the exports list to the object file */
645 {
646     SymEntry* S;
647     unsigned Type;
648
649     /* Tell the object file module that we're about to start the exports */
650     ObjStartExports ();
651
652     /* Write the export count to the list */
653     ObjWriteVar (ExportCount);
654
655     /* Walk throught list and write all exports to the file */
656     S = SymList;
657     while (S) {
658         if ((S->Flags & SF_EXPMASK) == SF_EXPVAL) {
659
660             long ConstVal;
661
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;
666
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);
671                 }
672             }
673
674             /* Write the type */
675             ObjWrite8 (ExprMask);
676
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));
683                     }
684                 }
685             }
686
687             /* Write the name */
688             ObjWriteVar (S->Name);
689
690             /* Write the value */
691             if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
692                 /* Constant value */
693                 ObjWrite32 (ConstVal);
694             } else {
695                 /* Expression involved */
696                 WriteExpr (S->V.Expr);
697             }
698
699             /* Write the source file position */
700             ObjWritePos (&S->Pos);
701         }
702         S = S->List;
703     }
704
705     /* Done writing exports */
706     ObjEndExports ();
707 }
708
709
710
711 void WriteDbgSyms (void)
712 /* Write a list of all symbols to the object file */
713 {
714     unsigned Count;
715     SymEntry* S;
716
717     /* Tell the object file module that we're about to start the debug info */
718     ObjStartDbgSyms ();
719
720     /* Check if debug info is requested */
721     if (DbgSyms) {
722
723         /* Walk through the list and count the symbols */
724         Count = 0;
725         S = SymList;
726         while (S) {
727             if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
728                 ++Count;
729             }
730             S = S->List;
731         }
732
733         /* Write the symbol count to the list */
734         ObjWriteVar (Count);
735
736         /* Walk through list and write all symbols to the file */
737         S = SymList;
738         while (S) {
739             if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
740
741                 long ConstVal;
742
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;
747
748                 /* Write the type */
749                 ObjWrite8 (ExprMask);
750
751                 /* Write the name */
752                 ObjWriteVar (S->Name);
753
754                 /* Write the value */
755                 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
756                     /* Constant value */
757                     ObjWrite32 (ConstVal);
758                 } else {
759                     /* Expression involved */
760                     WriteExpr (S->V.Expr);
761                 }
762
763                 /* Write the source file position */
764                 ObjWritePos (&S->Pos);
765             }
766             S = S->List;
767         }
768
769     } else {
770
771         /* No debug symbols */
772         ObjWriteVar (0);
773
774     }
775
776     /* Done writing debug symbols */
777     ObjEndDbgSyms ();
778 }
779
780
781
782
783