]> git.sur5r.net Git - cc65/blob - src/ca65/symtab.c
ca3966867c01fa75351c1cd79fc2464a592423eb
[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 /*****************************************************************************/
164 /*                                   Code                                    */
165 /*****************************************************************************/
166
167
168
169 void SymEnterLevel (const char* ScopeName, unsigned char Type, unsigned char AddrSize)
170 /* Enter a new lexical level */
171 {
172     /* Map a default address size to something real */
173     if (AddrSize == ADDR_SIZE_DEFAULT) {
174         /* Use the segment address size */
175         AddrSize = GetCurrentSegAddrSize ();
176     }
177
178     /* If we have a current scope, search for the given name and create a
179      * new one if it doesn't exist. If this is the root scope, just create it.
180      */
181     if (CurrentScope) {
182
183         /* Search for the scope, create a new one */
184         CurrentScope = SymFindScope (CurrentScope, ScopeName, SYM_ALLOC_NEW);
185
186         /* Check if the scope has been defined before */
187         if (CurrentScope->Flags & ST_DEFINED) {
188             Error ("Duplicate scope `%s'", ScopeName);
189         }
190
191     } else {
192         CurrentScope = RootScope = NewSymTable (0, ScopeName);
193     }
194
195     /* Mark the scope as defined and set type and address size */
196     CurrentScope->Flags    |= ST_DEFINED;
197     CurrentScope->AddrSize = AddrSize;
198     CurrentScope->Type     = Type;
199 }
200
201
202
203 void SymLeaveLevel (void)
204 /* Leave the current lexical level */
205 {
206     CurrentScope = CurrentScope->Parent;
207 }
208
209
210
211 SymTable* SymFindScope (SymTable* Parent, const char* Name, int AllocNew)
212 /* Find a scope in the given enclosing scope */
213 {
214     SymTable** T = &Parent->Childs;
215     while (*T) {
216         int Cmp = strcmp (Name, GetString ((*T)->Name));
217         if (Cmp < 0) {
218             T = &(*T)->Left;
219         } else if (Cmp > 0) {
220             T = &(*T)->Right;
221         } else {
222             /* Found the scope */
223             return *T;
224         }
225     }
226
227     /* Create a new scope if requested and we didn't find one */
228     if (*T == 0 && AllocNew) {
229         *T = NewSymTable (Parent, Name);
230     }
231
232     /* Return the scope */
233     return *T;
234 }
235
236
237
238 SymTable* SymFindAnyScope (SymTable* Parent, const char* Name)
239 /* Find a scope in the given or any of its parent scopes. The function will
240  * never create a new symbol, since this can only be done in one specific
241  * scope.
242  */
243 {
244     SymTable* Scope;
245     do {
246         /* Search in the current table */
247         Scope = SymFindScope (Parent, Name, SYM_FIND_EXISTING);
248         if (Scope == 0) {
249             /* Not found, search in the parent scope, if we have one */
250             Parent = Parent->Parent;
251         }
252     } while (Scope == 0 && Parent != 0);
253
254     return Scope;
255 }
256
257
258
259 SymEntry* SymFind (SymTable* Scope, const char* Name, int AllocNew)
260 /* Find a new symbol table entry in the given table. If AllocNew is given and
261  * the entry is not found, create a new one. Return the entry found, or the
262  * new entry created, or - in case AllocNew is zero - return 0.
263  */
264 {
265     SymEntry* S;
266     int Cmp;
267
268     if (IsLocalName (Name)) {
269
270         /* Local symbol, get the table */
271         if (!SymLast) {
272             /* No last global, so there's no local table */
273             Error ("No preceeding global symbol");
274             if (AllocNew) {
275                 return NewSymEntry (Name);
276             } else {
277                 return 0;
278             }
279         }
280
281         /* Search for the symbol if we have a table */
282         Cmp = SymSearchTree (SymLast->Locals, Name, &S);
283
284         /* If we found an entry, return it */
285         if (Cmp == 0) {
286             return S;
287         }
288
289         if (AllocNew) {
290
291             /* Otherwise create a new entry, insert and return it */
292             SymEntry* N = NewSymEntry (Name);
293             if (S == 0) {
294                 SymLast->Locals = N;
295             } else if (Cmp < 0) {
296                 S->Left = N;
297             } else {
298                 S->Right = N;
299             }
300             return N;
301         }
302
303     } else {
304
305         /* Global symbol: Get the hash value for the name */
306         unsigned Hash = HashStr (Name) % Scope->TableSlots;
307
308         /* Search for the entry */
309         Cmp = SymSearchTree (Scope->Table[Hash], Name, &S);
310
311         /* If we found an entry, return it */
312         if (Cmp == 0) {
313             /* Check for a trampoline entry, in this case return the real
314              * symbol.
315              */
316             while (S->Flags & SF_TRAMPOLINE) {
317                 S = S->V.Sym;
318             }
319             return S;
320         }
321
322         if (AllocNew) {
323
324             /* Otherwise create a new entry, insert and return it */
325             SymEntry* N = NewSymEntry (Name);
326             if (S == 0) {
327                 Scope->Table[Hash] = N;
328             } else if (Cmp < 0) {
329                 S->Left = N;
330             } else {
331                 S->Right = N;
332             }
333             N->SymTab = Scope;
334             ++Scope->TableEntries;
335             return N;
336
337         }
338     }
339
340     /* We did not find the entry and AllocNew is false. */
341     return 0;
342 }
343
344
345
346 static SymEntry* SymFindAny (SymTable* Scope, const char* Name)
347 /* Find a symbol in the given or any of its parent scopes. The function will
348  * never create a new symbol, since this can only be done in one specific
349  * scope.
350  */
351 {
352     SymEntry* Sym;
353     do {
354         /* Search in the current table */
355         Sym = SymFind (Scope, Name, SYM_FIND_EXISTING);
356         if (Sym) {
357             /* Found, return it */
358             return Sym;
359         } else {
360             /* Not found, search in the parent scope, if we have one */
361             Scope = Scope->Parent;
362         }
363     } while (Sym == 0 && Scope != 0);
364
365     /* Not found */
366     return 0;
367 }
368
369
370
371 int SymIsZP (SymEntry* S)
372 /* Return true if the symbol is explicitly marked as zeropage symbol */
373 {
374     /* Resolve trampoline entries */
375     if (S->Flags & SF_TRAMPOLINE) {
376         S = S->V.Sym;
377     }
378
379     /* If the symbol is not a global symbol, was not defined before, check the
380      * enclosing scope for a symbol with the same name, and return the ZP
381      * attribute of this symbol if we find one.
382      */
383     if (!IsLocalNameId (S->Name) && (S->Flags & (SF_DEFINED | SF_IMPORT)) == 0 &&
384         S->SymTab->Parent != 0) {
385
386         /* Try to find a symbol with the same name in the enclosing scope */
387         SymEntry* E = SymFindAny (S->SymTab->Parent, GetString (S->Name));
388
389         /* If we found one, use the ZP flag */
390         if (E && E->AddrSize == ADDR_SIZE_ZP) {
391             S->AddrSize = ADDR_SIZE_ZP;
392         }
393     }
394
395     /* Check the ZP flag */
396     return (S->AddrSize == ADDR_SIZE_ZP);
397 }
398
399
400
401 unsigned char GetCurrentSymTabType ()
402 /* Return the type of the current symbol table */
403 {
404     CHECK (CurrentScope != 0);
405     return CurrentScope->Type;
406 }
407
408
409
410 static void SymCheckUndefined (SymEntry* S)
411 /* Handle an undefined symbol */
412 {
413     /* Undefined symbol. It may be...
414      *
415      *   - An undefined symbol in a nested lexical level. In this
416      *     case, search for the symbol in the higher levels and
417      *     make the entry a trampoline entry if we find one.
418      *
419      *   - If the symbol is not found, it is a real undefined symbol.
420      *     If the AutoImport flag is set, make it an import. If the
421      *     AutoImport flag is not set, it's an error.
422      */
423     SymEntry* Sym = 0;
424     if (S->SymTab) {
425         /* It's a global symbol, get the higher level table */
426         SymTable* Tab = S->SymTab->Parent;
427         while (Tab) {
428             Sym = SymFindAny (Tab, GetString (S->Name));
429             if (Sym) {
430                 if (Sym->Flags & (SF_DEFINED | SF_IMPORT)) {
431                     /* We've found a symbol in a higher level that is
432                      * either defined in the source, or an import.
433                      */
434                      break;
435                 } else {
436                     /* The symbol found is undefined itself. Look further */
437                     Tab = Sym->SymTab->Parent;
438                 }
439             } else {
440                 /* No symbol found */
441                 break;
442             }
443         }
444     }
445     if (Sym) {
446         /* We found the symbol in a higher level. Make S a trampoline
447          * symbol. Beware: We have to transfer the symbol attributes to
448          * the real symbol and check for any conflicts.
449          */
450         S->Flags |= SF_TRAMPOLINE;
451         S->V.Sym = Sym;
452
453         /* Transfer the flags. Note: S may not be imported, since in that
454          * case it wouldn't be undefined.
455          */
456         if (S->Flags & SF_EXPORT) {
457             if (Sym->Flags & SF_IMPORT) {
458                 /* The symbol is already marked as imported external symbol */
459                 PError (&S->Pos, "Symbol `%s' is already an import", GetString (S->Name));
460             }
461             Sym->Flags |= (S->Flags & SF_EXPORT);
462             Sym->ExportSize = S->ExportSize;
463         }
464
465         /* Transfer the referenced flag */
466         Sym->Flags |= (S->Flags & SF_REFERENCED);
467
468     } else {
469         /* The symbol is definitely undefined */
470         if (S->Flags & SF_EXPORT) {
471             /* We will not auto-import an export */
472             PError (&S->Pos, "Exported symbol `%s' was never defined",
473                     GetString (S->Name));
474         } else {
475             if (AutoImport) {
476                 /* Mark as import, will be indexed later */
477                 S->Flags |= SF_IMPORT;
478             } else {
479                 /* Error */
480                 PError (&S->Pos, "Symbol `%s' is undefined", GetString (S->Name));
481             }
482         }
483     }
484 }
485
486
487
488 void SymCheck (void)
489 /* Run through all symbols and check for anomalies and errors */
490 {
491     SymEntry* S;
492
493     /* Check for open scopes */
494     if (CurrentScope->Parent != 0) {
495         Error ("Local scope was not closed");
496     }
497
498     /* First pass: Walk through all symbols, checking for undefined's and
499      * changing them to trampoline symbols or make them imports.
500      */
501     S = SymList;
502     while (S) {
503         /* If the symbol is marked as global, mark it as export, if it is
504          * already defined, otherwise mark it as import.
505          */
506         if (S->Flags & SF_GLOBAL) {
507             S->Flags &= ~SF_GLOBAL;
508             if (S->Flags & SF_DEFINED) {
509                 S->Flags |= SF_EXPORT;
510             } else {
511                 S->Flags |= SF_IMPORT;
512             }
513         }
514
515         /* Handle undefined symbols */
516         if ((S->Flags & SF_UNDEFMASK) == SF_UNDEFVAL) {
517             /* This is an undefined symbol. Handle it. */
518             SymCheckUndefined (S);
519         }
520
521         /* Next symbol */
522         S = S->List;
523     }
524
525     /* Second pass: Walk again through the symbols. Ignore undefined's, since
526      * we handled them in the last pass, and ignore trampoline symbols, since
527      * we handled them in the last pass, too.
528      */
529     S = SymList;
530     while (S) {
531         if ((S->Flags & SF_TRAMPOLINE) == 0 &&
532             (S->Flags & SF_UNDEFMASK) != SF_UNDEFVAL) {
533             if ((S->Flags & SF_DEFINED) != 0 && (S->Flags & SF_REFERENCED) == 0) {
534                 /* Symbol was defined but never referenced */
535                 PWarning (&S->Pos, 2,
536                           "Symbol `%s' is defined but never used",
537                           GetString (S->Name));
538             }
539             if (S->Flags & SF_IMPORT) {
540                 if ((S->Flags & (SF_REFERENCED | SF_FORCED)) == SF_NONE) {
541                     /* Imported symbol is not referenced */
542                     PWarning (&S->Pos, 2,
543                               "Symbol `%s' is imported but never used",
544                               GetString (S->Name));
545                 } else {
546                     /* Give the import an index, count imports */
547                     S->Index = ImportCount++;
548                     S->Flags |= SF_INDEXED;
549                 }
550             }
551             if (S->Flags & SF_EXPORT) {
552                 /* Give the export an index, count exports */
553                 S->Index = ExportCount++;
554                 S->Flags |= SF_INDEXED;
555             }
556         }
557
558         /* Next symbol */
559         S = S->List;
560     }
561 }
562
563
564
565 void SymDump (FILE* F)
566 /* Dump the symbol table */
567 {
568     SymEntry* S = SymList;
569
570     while (S) {
571         /* Ignore trampoline symbols */
572         if ((S->Flags & SF_TRAMPOLINE) != 0) {
573             fprintf (F,
574                      "%-24s %s %s %s %s %s\n",
575                      GetString (S->Name),
576                      (S->Flags & SF_DEFINED)? "DEF" : "---",
577                      (S->Flags & SF_REFERENCED)? "REF" : "---",
578                      (S->Flags & SF_IMPORT)? "IMP" : "---",
579                      (S->Flags & SF_EXPORT)? "EXP" : "---",
580                      AddrSizeToStr (S->AddrSize));
581         }
582         /* Next symbol */
583         S = S->List;
584     }
585 }
586
587
588
589 void WriteImports (void)
590 /* Write the imports list to the object file */
591 {
592     SymEntry* S;
593
594     /* Tell the object file module that we're about to start the imports */
595     ObjStartImports ();
596
597     /* Write the import count to the list */
598     ObjWriteVar (ImportCount);
599
600     /* Walk throught list and write all valid imports to the file. An import
601      * is considered valid, if it is either referenced, or the forced bit is
602      * set. Otherwise, the import is ignored (no need to link in something
603      * that isn't used).
604      */
605     S = SymList;
606     while (S) {
607         if ((S->Flags & (SF_TRAMPOLINE | SF_IMPORT)) == SF_IMPORT &&
608             (S->Flags & (SF_REFERENCED | SF_FORCED)) != 0) {
609
610             if (S->AddrSize == ADDR_SIZE_ZP) {
611                 ObjWrite8 (IMP_ZP);
612             } else {
613                 ObjWrite8 (IMP_ABS);
614             }
615             ObjWriteVar (S->Name);
616             ObjWritePos (&S->Pos);
617         }
618         S = S->List;
619     }
620
621     /* Done writing imports */
622     ObjEndImports ();
623 }
624
625
626
627 void WriteExports (void)
628 /* Write the exports list to the object file */
629 {
630     SymEntry* S;
631     unsigned Type;
632
633     /* Tell the object file module that we're about to start the exports */
634     ObjStartExports ();
635
636     /* Write the export count to the list */
637     ObjWriteVar (ExportCount);
638
639     /* Walk throught list and write all exports to the file */
640     S = SymList;
641     while (S) {
642         if ((S->Flags & SF_EXPMASK) == SF_EXPVAL) {
643
644             long ConstVal;
645
646             /* Get the expression bits */
647             unsigned char ExprMask = SymIsConst (S, &ConstVal)? EXP_CONST : EXP_EXPR;
648             ExprMask |= (S->ExportSize == ADDR_SIZE_ZP)? EXP_ZP : EXP_ABS;
649             ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
650
651             /* Count the number of ConDes types */
652             for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
653                 if (S->ConDesPrio[Type] != CD_PRIO_NONE) {
654                     INC_EXP_CONDES_COUNT (ExprMask);
655                 }
656             }
657
658             /* Write the type */
659             ObjWrite8 (ExprMask);
660
661             /* Write any ConDes declarations */
662             if (GET_EXP_CONDES_COUNT (ExprMask) > 0) {
663                 for (Type = 0; Type < CD_TYPE_COUNT; ++Type) {
664                     unsigned char Prio = S->ConDesPrio[Type];
665                     if (Prio != CD_PRIO_NONE) {
666                         ObjWrite8 (CD_BUILD (Type, Prio));
667                     }
668                 }
669             }
670
671             /* Write the name */
672             ObjWriteVar (S->Name);
673
674             /* Write the value */
675             if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
676                 /* Constant value */
677                 ObjWrite32 (ConstVal);
678             } else {
679                 /* Expression involved */
680                 WriteExpr (S->V.Expr);
681             }
682
683             /* Write the source file position */
684             ObjWritePos (&S->Pos);
685         }
686         S = S->List;
687     }
688
689     /* Done writing exports */
690     ObjEndExports ();
691 }
692
693
694
695 void WriteDbgSyms (void)
696 /* Write a list of all symbols to the object file */
697 {
698     unsigned Count;
699     SymEntry* S;
700
701     /* Tell the object file module that we're about to start the debug info */
702     ObjStartDbgSyms ();
703
704     /* Check if debug info is requested */
705     if (DbgSyms) {
706
707         /* Walk through the list and count the symbols */
708         Count = 0;
709         S = SymList;
710         while (S) {
711             if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
712                 ++Count;
713             }
714             S = S->List;
715         }
716
717         /* Write the symbol count to the list */
718         ObjWriteVar (Count);
719
720         /* Walk through list and write all symbols to the file */
721         S = SymList;
722         while (S) {
723             if ((S->Flags & SF_DBGINFOMASK) == SF_DBGINFOVAL) {
724
725                 long ConstVal;
726
727                 /* Get the expression bits */
728                 unsigned char ExprMask = (SymIsConst (S, &ConstVal))? EXP_CONST : EXP_EXPR;
729                 ExprMask |= (S->AddrSize == ADDR_SIZE_ZP)? EXP_ZP : EXP_ABS;
730                 ExprMask |= (S->Flags & SF_LABEL)? EXP_LABEL : EXP_EQUATE;
731
732                 /* Write the type */
733                 ObjWrite8 (ExprMask);
734
735                 /* Write the name */
736                 ObjWriteVar (S->Name);
737
738                 /* Write the value */
739                 if ((ExprMask & EXP_MASK_VAL) == EXP_CONST) {
740                     /* Constant value */
741                     ObjWrite32 (ConstVal);
742                 } else {
743                     /* Expression involved */
744                     WriteExpr (S->V.Expr);
745                 }
746
747                 /* Write the source file position */
748                 ObjWritePos (&S->Pos);
749             }
750             S = S->List;
751         }
752
753     } else {
754
755         /* No debug symbols */
756         ObjWriteVar (0);
757
758     }
759
760     /* Done writing debug symbols */
761     ObjEndDbgSyms ();
762 }
763
764
765
766
767