1 // $Id: lookup.h,v 1.37 2004/01/26 06:07:16 cabbey Exp $ -*- c++ -*-
2 //
3 // This software is subject to the terms of the IBM Jikes Compiler
4 // License Agreement available at the following URL:
5 // http://ibm.com/developerworks/opensource/jikes.
6 // Copyright (C) 1996, 2004 IBM Corporation and others.  All Rights Reserved.
7 // You must accept the terms of that agreement to use this software.
8 //
9 
10 #ifndef lookup_INCLUDED
11 #define lookup_INCLUDED
12 
13 #include "platform.h"
14 #include "tuple.h"
15 #include "long.h"
16 #include "double.h"
17 
18 #ifdef HAVE_JIKES_NAMESPACE
19 namespace Jikes { // Open namespace Jikes block
20 #endif
21 
22 class Control;
23 class Symbol;
24 class PackageSymbol;
25 class TypeSymbol;
26 class MethodSymbol;
27 class MethodShadowSymbol;
28 class BlockSymbol;
29 class VariableSymbol;
30 class VariableShadowSymbol;
31 class LabelSymbol;
32 class LiteralSymbol;
33 class NameSymbol;
34 
35 class PathSymbol;
36 class DirectorySymbol;
37 class FileSymbol;
38 
39 class ShadowSymbol;
40 
41 class LiteralValue;
42 class IntLiteralValue;
43 class LongLiteralValue;
44 class FloatLiteralValue;
45 class DoubleLiteralValue;
46 class Utf8LiteralValue;
47 
48 class Utf8LiteralTable;
49 class NameLookupTable;
50 class TypeLookupTable;
51 class LiteralLookupTable;
52 
53 class AstBinaryExpression;
54 class AstExpression;
55 
56 class Hash
57 {
58 public:
59     //
60     // HASH takes as argument a pointer to a character string
61     // and its length which it hashes it into a location in the name
62     // hash table.
63     //
Function(const wchar_t * head,int len)64     inline static unsigned Function(const wchar_t* head, int len)
65     {
66         unsigned hash_value = 0;
67         while (--len >= 0)
68             hash_value = (hash_value << 5) - hash_value + *head++;
69         return hash_value;
70     }
71 
72     //
73     // Same as above function for a regular "char" string.
74     //
Function(const char * head,int len)75     inline static unsigned Function(const char* head, int len)
76     {
77         unsigned hash_value = 0;
78         while (--len >= 0)
79             hash_value = (hash_value << 5) - hash_value + *head++;
80         return hash_value;
81     }
82 
Function(LongInt value)83     inline static unsigned Function(LongInt value)
84     {
85         return value.hashCode();
86     }
87 
Function(IEEEfloat value)88     inline static unsigned Function(IEEEfloat value)
89     {
90         return value.hashCode();
91     }
92 
Function(IEEEdouble value)93     inline static unsigned Function(IEEEdouble value)
94     {
95         return value.hashCode();
96     }
97 };
98 
99 
100 class DirectoryEntry
101 {
102 public:
103     DirectoryEntry* next;
104     char* name;
105     int length;
106 
DirectoryEntry()107     DirectoryEntry()
108         : next(NULL),
109           name(NULL),
110           length(0),
111           directory(NULL),
112           mtime_(0)
113     {
114         image = this;
115     }
116 
~DirectoryEntry()117     virtual ~DirectoryEntry()
118     {
119         delete [] name;
120     }
121 
122 
Initialize(DirectorySymbol * directory_,char * name_,int length_)123     inline void Initialize(DirectorySymbol* directory_, char* name_,
124                            int length_)
125     {
126         directory = directory_;
127         length = length_;
128         name = new char[length + 1];
129         memcpy(name, name_, length * sizeof(char));
130         name[length] = U_NULL;
131     }
132 
Initialize(DirectoryEntry * entry,char * name_,int length_)133     inline void Initialize(DirectoryEntry* entry, char* name_, int length_)
134     {
135         Initialize(entry -> directory, name_, length_);
136     }
137 
138     time_t Mtime();
139 
IsDummy()140     bool IsDummy() { return this != image; }
141 
142     //
143     // See FoldedDirectoryEntry for an explanation of the use of this function
144     //
Image()145     virtual DirectoryEntry* Image() { return this; }
146 
147 protected:
148     DirectorySymbol* directory;
149     DirectoryEntry* image;
150     time_t mtime_;
151 };
152 
153 
154 #ifdef WIN32_FILE_SYSTEM
155 //
156 // This object is needed only for systems such as Windows NT/95/98 that
157 // treat filenames in a case-insensitive fashion.
158 //
159 class FoldedDirectoryEntry : public DirectoryEntry
160 {
161 public:
FoldedDirectoryEntry(DirectoryEntry * image_)162     FoldedDirectoryEntry(DirectoryEntry* image_)
163     {
164         DirectoryEntry::image = image_;
165     }
~FoldedDirectoryEntry()166     virtual ~FoldedDirectoryEntry() {}
167 
Image()168     virtual DirectoryEntry* Image() { return image; }
169 };
170 #endif // WIN32_FILE_SYSTEM
171 
172 
173 class SystemTable
174 {
175     enum
176     {
177         DEFAULT_HASH_SIZE = 13,
178         MAX_HASH_SIZE = 1021
179     };
180 
181 public:
182 
183     SystemTable(unsigned = DEFAULT_HASH_SIZE);
184     virtual ~SystemTable();
185 
186     DirectorySymbol* FindDirectorySymbol(dev_t, ino_t);
187     void InsertDirectorySymbol(dev_t, ino_t, DirectorySymbol*);
188 
189 private:
190     class Element
191     {
192     public:
Element(dev_t device_,ino_t inode_,DirectorySymbol * directory_symbol_)193         Element(dev_t device_, ino_t inode_,
194                 DirectorySymbol* directory_symbol_)
195             : device(device_),
196               inode(inode_),
197               directory_symbol(directory_symbol_)
198         {}
199 
200         Element* next;
201         dev_t device;
202         ino_t inode;
203         DirectorySymbol* directory_symbol;
204     };
205 
206     Tuple<Element*> directories;
207 
208     Element** base;
209     unsigned hash_size;
210 
211     static unsigned primes[];
212     int prime_index;
213 
hash(dev_t device,ino_t inode)214     unsigned hash(dev_t device, ino_t inode)
215     {
216         return (device + inode) % hash_size;
217     }
218 
219     void Rehash();
220 };
221 
222 
223 class DirectoryTable
224 {
225 public:
226     Tuple<DirectoryEntry*> entry_pool;
227 
228     DirectoryTable(int estimate = 1024);
229     ~DirectoryTable();
230 
231     DirectoryEntry* FindEntry(char*, int);
232     DirectoryEntry* InsertEntry(DirectorySymbol*, char*, int);
233 
234 #ifdef WIN32_FILE_SYSTEM
235     //
236     // See FoldedDirectoryEntry for an explanation of the use of this function
237     //
238     DirectoryEntry* FindCaseInsensitiveEntry(char*, int);
239     void InsertCaseInsensitiveEntry(DirectoryEntry*);
240 #endif
241 
242 private:
243     enum
244     {
245         DEFAULT_HASH_SIZE = 1021,
246         MAX_HASH_SIZE = 8191
247     };
248 
249     DirectoryEntry** base;
250     unsigned hash_size;
251 
252     static unsigned primes[];
253     int prime_index;
254 
Hash(const char * head,int len)255     inline static unsigned Hash(const char* head, int len)
256     {
257         return Hash::Function(head, len);
258     }
259 
260     void Rehash();
261 };
262 
263 
264 class Symbol
265 {
266 public:
267     Symbol* next;
268 
269     enum SymbolKind
270     {
271          NONE,
272          NAME,
273          PACKAGE,
274          TYPE, // class or interface
275          METHOD,
276          BLOCK,
277          VARIABLE,
278          LABEL,
279          LITERAL,
280 
281          PATH,
282          _DIRECTORY,
283          _FILE,
284 
285          _num_kinds
286     };
287 
Kind()288     SymbolKind Kind() const { return _kind; }
Name()289     virtual const wchar_t* Name() const { return NULL; }
NameLength()290     virtual unsigned NameLength() const { return 0; }
Identity()291     virtual const NameSymbol* Identity() const { return NULL; }
292     inline unsigned HashCode() const;
293 
294     //
295     // These cannot be inline without including symbol.h, because they
296     // would cast to incomplete types.
297     //
298     PackageSymbol* PackageCast();
299     const PackageSymbol* PackageCast() const;
300     TypeSymbol* TypeCast();
301     const TypeSymbol* TypeCast() const;
302     MethodSymbol* MethodCast();
303     const MethodSymbol* MethodCast() const;
304     BlockSymbol* BlockCast();
305     const BlockSymbol* BlockCast() const;
306     VariableSymbol* VariableCast();
307     const VariableSymbol* VariableCast() const;
308     LabelSymbol* LabelCast();
309     const LabelSymbol* LabelCast() const;
310     LiteralSymbol* LiteralCast();
311     const LiteralSymbol* LiteralCast() const;
312     NameSymbol* NameCast();
313     const NameSymbol* NameCast() const;
314 
315     PathSymbol* PathCast();
316     const PathSymbol* PathCast() const;
317     DirectorySymbol* DirectoryCast();
318     const DirectorySymbol* DirectoryCast() const;
319     FileSymbol* FileCast();
320     const FileSymbol* FileCast() const;
321 
~Symbol()322     virtual ~Symbol() {}
323 
324 protected:
325     SymbolKind _kind;
326 };
327 
328 
329 class LiteralValue
330 {
331 public:
332     LiteralValue* next;
333     int index;
334 
~LiteralValue()335     virtual ~LiteralValue() {}
336 };
337 
338 
339 class IntLiteralValue : public LiteralValue
340 {
341 public:
342     i4 value;
343 
~IntLiteralValue()344     virtual ~IntLiteralValue() {}
345 
Initialize(int value_,int index_)346     void Initialize(int value_, int index_)
347     {
348         value = value_;
349         index = index_;
350     }
351 };
352 
353 
354 class LongLiteralValue : public LiteralValue
355 {
356 public:
357     LongInt value;
358 
~LongLiteralValue()359     virtual ~LongLiteralValue() {}
360 
Initialize(LongInt value_,int index_)361     void Initialize(LongInt value_, int index_)
362     {
363         value = value_;
364         index = index_;
365     }
366 };
367 
368 
369 class FloatLiteralValue : public LiteralValue
370 {
371 public:
372     IEEEfloat value;
373 
~FloatLiteralValue()374     virtual ~FloatLiteralValue() {}
375 
Initialize(IEEEfloat value_,int index_)376     void Initialize(IEEEfloat value_, int index_)
377     {
378         value = value_;
379         index = index_;
380     }
381 };
382 
383 
384 class DoubleLiteralValue : public LiteralValue
385 {
386 public:
387     IEEEdouble value;
388 
~DoubleLiteralValue()389     virtual ~DoubleLiteralValue() {}
390 
Initialize(IEEEdouble value_,int index_)391     void Initialize(IEEEdouble value_, int index_)
392     {
393         value = value_;
394         index = index_;
395     }
396 };
397 
398 
399 class Utf8LiteralValue : public LiteralValue
400 {
401 public:
402     char* value;
403     int  length;
404 
Utf8LiteralValue()405     Utf8LiteralValue() : value(NULL)
406     {}
407 
~Utf8LiteralValue()408     virtual ~Utf8LiteralValue()
409     {
410         delete [] value;
411     }
412 
Initialize(const char * value_,int length_,unsigned hash_address_,int index_)413     void Initialize(const char* value_, int length_, unsigned hash_address_,
414                     int index_)
415     {
416         length = length_;
417         value = new char[length + 1];
418         memcpy(value, value_, length * sizeof(char));
419         value[length] = U_NULL;
420 
421         hash_address = hash_address_;
422         index = index_;
423     }
424 
425 private:
426 
427     friend class Utf8LiteralTable;
428 
429     unsigned hash_address;
430 };
431 
432 
433 class NameSymbol : public Symbol
434 {
435 public:
436     int index;
437     Utf8LiteralValue* Utf8_literal;
438 
Name()439     virtual const wchar_t* Name() const { return name_; }
NameLength()440     virtual unsigned NameLength() const { return length; }
Identity()441     virtual const NameSymbol* Identity() const { return this; }
Utf8Name()442     const char* Utf8Name() const
443     {
444         return Utf8_literal ? Utf8_literal -> value : (char*) NULL;
445     }
Utf8NameLength()446     unsigned Utf8NameLength() const
447     {
448         return Utf8_literal ? Utf8_literal -> length : 0;
449     }
450 
451     bool IsBadStyleForClass() const;
452     bool IsBadStyleForConstantField() const;
453     bool IsBadStyleForField() const;
454     bool IsBadStyleForMethod() const;
455     bool IsBadStyleForVariable() const;
456 
NameSymbol()457     NameSymbol() : name_(NULL) {}
~NameSymbol()458     virtual ~NameSymbol() { delete [] name_; }
459 
Initialize(const wchar_t * str,unsigned length_,unsigned hash_address_,int index_)460     inline void Initialize(const wchar_t* str, unsigned length_,
461                            unsigned hash_address_, int index_)
462     {
463         Symbol::_kind = NAME;
464 
465         hash_address = hash_address_;
466         index = index_;
467 
468         length = length_;
469         name_ = new wchar_t[length + 1];
470         memcpy(name_, str, length * sizeof(wchar_t));
471         name_[length] = U_NULL;
472 
473         Utf8_literal = NULL;
474     }
475 
476 private:
477     bool Contains(wchar_t character) const;
478 
479     friend class NameLookupTable;
480 
481     wchar_t* name_;
482     unsigned length;
483     unsigned hash_address;
484 };
485 
486 
487 class NameLookupTable
488 {
489 public:
490     Tuple<NameSymbol*> symbol_pool;
491 
492     NameLookupTable(int estimate = 16384);
493     ~NameLookupTable();
494 
495     NameSymbol* FindOrInsertName(const wchar_t*, unsigned);
496 
497 private:
498     enum
499     {
500         DEFAULT_HASH_SIZE = 4093,
501         MAX_HASH_SIZE = 32771
502     };
503 
504     NameSymbol** base;
505     unsigned hash_size;
506 
507     static unsigned primes[];
508     int prime_index;
509 
Hash(const wchar_t * head,int len)510     inline static unsigned Hash(const wchar_t* head, int len)
511     {
512         return Hash::Function(head, len);
513     }
514 
515     void Rehash();
516 };
517 
518 
519 class TypeLookupTable
520 {
521 public:
522     TypeLookupTable(int estimate = 16384);
523     ~TypeLookupTable();
524 
525     TypeSymbol* FindType(const char*, int);
526     void InsertType(TypeSymbol*);
527     void SetEmpty();
528 
529 private:
530     Tuple<TypeSymbol*> symbol_pool;
531 
532     enum
533     {
534         DEFAULT_HASH_SIZE = 4093,
535         MAX_HASH_SIZE = 32771
536     };
537 
538     TypeSymbol** base;
539     unsigned hash_size;
540 
541     static unsigned primes[];
542     int prime_index;
543 
Hash(const char * head,int len)544     inline static unsigned Hash(const char* head, int len)
545     {
546         return Hash::Function(head, len);
547     }
548 
549     void Rehash();
550 };
551 
552 
553 class LiteralSymbol : public Symbol
554 {
555 public:
556     LiteralValue* value;
557 
Name()558     virtual const wchar_t* Name() const { return name_; }
NameLength()559     virtual unsigned NameLength() const { return length; }
Identity()560     virtual const NameSymbol* Identity() const { return NULL; }
561 
LiteralSymbol()562     LiteralSymbol() : name_(NULL) {}
~LiteralSymbol()563     virtual ~LiteralSymbol() { delete [] name_; }
564 
Initialize(const wchar_t * str,unsigned hash_address_,int length_)565     void Initialize(const wchar_t* str, unsigned hash_address_, int length_)
566     {
567         Symbol::_kind = LITERAL;
568 
569         hash_address = hash_address_;
570 
571         length = length_;
572         name_ = new wchar_t[length + 1];
573         memcpy(name_, str, length * sizeof(wchar_t));
574         name_[length] = U_NULL;
575 
576         value = NULL;
577     }
578 
579 private:
580 
581     friend class LiteralLookupTable;
582 
583     wchar_t* name_;
584     int length;
585     unsigned hash_address;
586 };
587 
588 
589 class LiteralLookupTable
590 {
591 public:
592     Tuple<LiteralSymbol*> symbol_pool;
593 
594     LiteralLookupTable();
595     ~LiteralLookupTable();
596 
597     LiteralSymbol* FindOrInsertLiteral(const wchar_t*, unsigned);
598 
599 private:
600     enum
601     {
602         DEFAULT_HASH_SIZE = 1021,
603         MAX_HASH_SIZE = 8191
604     };
605 
606     LiteralSymbol** base;
607     unsigned hash_size;
608 
609     static unsigned primes[];
610     int prime_index;
611 
Hash(const wchar_t * head,int len)612     inline static unsigned Hash(const wchar_t* head, int len)
613     {
614         return Hash::Function(head, len);
615     }
616 
617     void Rehash();
618 };
619 
620 
621 class IntLiteralTable
622 {
623 public:
624     Tuple<IntLiteralValue*> symbol_pool;
625 
626     IntLiteralTable(LiteralValue*);
627     ~IntLiteralTable();
628 
FindOrInsertNull()629     LiteralValue* FindOrInsertNull()
630     {
631         return FindOrInsert(0);
632     }
633 
634     LiteralValue* FindOrInsertChar(LiteralSymbol*);
635     LiteralValue* FindOrInsertInt(LiteralSymbol*);
636     LiteralValue* FindOrInsertHexInt(LiteralSymbol*);
637     LiteralValue* FindOrInsertOctalInt(LiteralSymbol*);
638     LiteralValue* FindOrInsertNegativeInt(LiteralSymbol*);
639 
640     IntLiteralValue* FindOrInsert(i4);
641     IntLiteralValue* Find(i4);
642     // Forwarding methods, if needed, so that Find(0) works.
643 #ifndef TYPE_I4_IS_INT
FindOrInsert(int i)644     inline IntLiteralValue* FindOrInsert(int i)
645     {
646         return FindOrInsert((i4) i);
647     }
Find(int i)648     inline IntLiteralValue* Find(int i) { return Find((i4) i); }
649 #endif // TYPE_I4_IS_INT
650 
651 #ifdef JIKES_DEBUG
652     //
653     // To prevent arithmetic conversion to allow illegal calls inadvertently.
654     // Since the return type is wrong, compilation will fail !
655     //
FindOrInsert(LongInt)656     void FindOrInsert(LongInt) {}
FindOrInsert(float)657     void FindOrInsert(float) {}
FindOrInsert(double)658     void FindOrInsert(double) {}
659 #endif
660 
661 private:
662     enum
663     {
664         DEFAULT_HASH_SIZE = 4093,
665         MAX_HASH_SIZE = 32771
666     };
667 
668     IntLiteralValue** base;
669     unsigned hash_size;
670 
671     static unsigned primes[];
672     int prime_index;
673 
674     static int int32_limit;
675 
676     LiteralValue* bad_value;
677 
678     void Rehash();
679 };
680 
681 
682 class LongLiteralTable
683 {
684 public:
685     Tuple<LongLiteralValue*> symbol_pool;
686 
687     LongLiteralTable(LiteralValue*);
688     ~LongLiteralTable();
689 
690     LiteralValue* FindOrInsertLong(LiteralSymbol*);
691     LiteralValue* FindOrInsertHexLong(LiteralSymbol*);
692     LiteralValue* FindOrInsertOctalLong(LiteralSymbol*);
693     LiteralValue* FindOrInsertNegativeLong(LiteralSymbol*);
694 
695     LongLiteralValue* FindOrInsert(LongInt);
696 
697 #ifdef JIKES_DEBUG
698     //
699     // To prevent arithmetic conversion to allow illegal calls inadvertently.
700     //
FindOrInsert(int)701     void FindOrInsert(int) {}
FindOrInsert(float)702     void FindOrInsert(float) {}
FindOrInsert(double)703     void FindOrInsert(double) {}
704 #endif
705 
706 private:
707 
708     enum
709     {
710         DEFAULT_HASH_SIZE = 1021,
711         MAX_HASH_SIZE = 8191
712     };
713 
714     LongLiteralValue** base;
715     unsigned hash_size;
716 
717     static unsigned primes[];
718     int prime_index;
719 
720     static LongInt int64_limit;
721 
722     LiteralValue* bad_value;
723 
Hash(LongInt value)724     inline static unsigned Hash(LongInt value)
725     {
726         return Hash::Function(value);
727     }
728 
729     void Rehash();
730 };
731 
732 
733 class FloatLiteralTable
734 {
735 public:
736     Tuple<FloatLiteralValue*> symbol_pool;
737 
738     FloatLiteralTable(LiteralValue*);
739     ~FloatLiteralTable();
740 
741     LiteralValue* FindOrInsertFloat(LiteralSymbol*);
742 
743     FloatLiteralValue* FindOrInsert(IEEEfloat);
744 
745 #ifdef JIKES_DEBUG
746     //
747     // To prevent arithmetic conversion to allow illegal calls inadvertently.
748     //
FindOrInsert(int)749     void FindOrInsert(int) {}
FindOrInsert(LongInt)750     void FindOrInsert(LongInt) {}
FindOrInsert(double)751     void FindOrInsert(double) {}
752 #endif
753 
754 private:
755 
756     enum
757     {
758         DEFAULT_HASH_SIZE = 1021,
759         MAX_HASH_SIZE = 8191
760     };
761 
762     FloatLiteralValue** base;
763     unsigned hash_size;
764 
765     static unsigned primes[];
766     int prime_index;
767 
768     LiteralValue* bad_value;
769 
Hash(IEEEfloat value)770     inline static unsigned Hash(IEEEfloat value)
771     {
772         return Hash::Function(value);
773     }
774 
775     void Rehash();
776 };
777 
778 
779 class DoubleLiteralTable
780 {
781 public:
782     Tuple<DoubleLiteralValue*> symbol_pool;
783 
784     DoubleLiteralTable(LiteralValue*);
785     ~DoubleLiteralTable();
786 
787     LiteralValue* FindOrInsertDouble(LiteralSymbol*);
788 
789     DoubleLiteralValue* FindOrInsert(IEEEdouble);
790 
791 #ifdef JIKES_DEBUG
792     //
793     // To prevent arithmetic conversion to allow illegal calls inadvertently.
794     //
FindOrInsert(int)795     void FindOrInsert(int) {}
FindOrInsert(LongInt)796     void FindOrInsert(LongInt) {}
FindOrInsert(float)797     void FindOrInsert(float) {}
798 #endif
799 
800 private:
801 
802     enum
803     {
804         DEFAULT_HASH_SIZE = 1021,
805         MAX_HASH_SIZE = 8191
806     };
807 
808     DoubleLiteralValue** base;
809     unsigned hash_size;
810 
811     static unsigned primes[];
812     int prime_index;
813 
814     LiteralValue* bad_value;
815 
Hash(IEEEdouble value)816     inline static unsigned Hash(IEEEdouble value)
817     {
818         return Hash::Function(value);
819     }
820 
821     void Rehash();
822 };
823 
824 
825 class Utf8LiteralTable
826 {
827 public:
828     Tuple<Utf8LiteralValue*> symbol_pool;
829 
830     Utf8LiteralTable(LiteralValue*);
831     ~Utf8LiteralTable();
832 
833     LiteralValue* FindOrInsertString(LiteralSymbol*);
834 
835     Utf8LiteralValue* FindOrInsert(const char*, int);
836     Utf8LiteralValue* FindOrInsert(wchar_t);
837 
838     void CheckStringConstant(AstExpression* expr);
839 
840 private:
841 
842     Tuple<Utf8LiteralValue*>* utf8_literals;
843     AstExpression* leftmost_constant_expr;
844     void CollectStrings();
845     bool EndsInKnownString(AstExpression*);
846 
847     enum
848     {
849         DEFAULT_HASH_SIZE = 4093,
850         MAX_HASH_SIZE = 32771
851     };
852 
853     Utf8LiteralValue** base;
854     unsigned hash_size;
855 
856     static unsigned primes[];
857     int prime_index;
858 
859     LiteralValue* bad_value;
860 
Hash(const char * head,int len)861     inline static unsigned Hash(const char* head, int len)
862     {
863         return Hash::Function(head, len);
864     }
865 
866     void Rehash();
867 };
868 
869 
HashCode()870 inline unsigned Symbol::HashCode() const
871 {
872     return (unsigned) Identity() -> index;
873 }
874 
875 #ifdef HAVE_JIKES_NAMESPACE
876 } // Close namespace Jikes block
877 #endif
878 
879 #endif // lookup_INCLUDED
880