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