1 //===--- IdentifierTable.cpp - Hash table for identifier lookup -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the IdentifierInfo, IdentifierVisitor, and
11 // IdentifierTable interfaces.
13 //===----------------------------------------------------------------------===//
15 #include "clang/Basic/IdentifierTable.h"
16 #include "clang/Basic/LangOptions.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Support/raw_ostream.h"
23 using namespace clang
;
25 //===----------------------------------------------------------------------===//
26 // IdentifierInfo Implementation
27 //===----------------------------------------------------------------------===//
29 IdentifierInfo::IdentifierInfo() {
30 TokenID
= tok::identifier
;
35 IsCPPOperatorKeyword
= false;
36 NeedsHandleIdentifier
= false;
38 RevertedTokenID
= false;
43 //===----------------------------------------------------------------------===//
44 // IdentifierTable Implementation
45 //===----------------------------------------------------------------------===//
47 IdentifierIterator::~IdentifierIterator() { }
49 IdentifierInfoLookup::~IdentifierInfoLookup() {}
52 /// \brief A simple identifier lookup iterator that represents an
53 /// empty sequence of identifiers.
54 class EmptyLookupIterator
: public IdentifierIterator
57 virtual llvm::StringRef
Next() { return llvm::StringRef(); }
61 IdentifierIterator
*IdentifierInfoLookup::getIdentifiers() const {
62 return new EmptyLookupIterator();
65 ExternalIdentifierLookup::~ExternalIdentifierLookup() {}
67 IdentifierTable::IdentifierTable(const LangOptions
&LangOpts
,
68 IdentifierInfoLookup
* externalLookup
)
69 : HashTable(8192), // Start with space for 8K identifiers.
70 ExternalLookup(externalLookup
) {
72 // Populate the identifier table with info about keywords for the current
74 AddKeywords(LangOpts
);
77 //===----------------------------------------------------------------------===//
78 // Language Keyword Implementation
79 //===----------------------------------------------------------------------===//
81 // Constants for TokenKinds.def
98 /// AddKeyword - This method is used to associate a token ID with specific
99 /// identifiers because they are language keywords. This causes the lexer to
100 /// automatically map matching identifiers to specialized token codes.
102 /// The C90/C99/CPP/CPP0x flags are set to 2 if the token should be
103 /// enabled in the specified langauge, set to 1 if it is an extension
104 /// in the specified language, and set to 0 if disabled in the
105 /// specified language.
106 static void AddKeyword(llvm::StringRef Keyword
,
107 tok::TokenKind TokenCode
, unsigned Flags
,
108 const LangOptions
&LangOpts
, IdentifierTable
&Table
) {
109 unsigned AddResult
= 0;
110 if (Flags
& KEYALL
) AddResult
= 2;
111 else if (LangOpts
.CPlusPlus
&& (Flags
& KEYCXX
)) AddResult
= 2;
112 else if (LangOpts
.CPlusPlus0x
&& (Flags
& KEYCXX0X
)) AddResult
= 2;
113 else if (LangOpts
.C99
&& (Flags
& KEYC99
)) AddResult
= 2;
114 else if (LangOpts
.GNUKeywords
&& (Flags
& KEYGNU
)) AddResult
= 1;
115 else if (LangOpts
.Microsoft
&& (Flags
& KEYMS
)) AddResult
= 1;
116 else if (LangOpts
.Borland
&& (Flags
& KEYBORLAND
)) AddResult
= 1;
117 else if (LangOpts
.Bool
&& (Flags
& BOOLSUPPORT
)) AddResult
= 2;
118 else if (LangOpts
.AltiVec
&& (Flags
& KEYALTIVEC
)) AddResult
= 2;
119 else if (LangOpts
.OpenCL
&& (Flags
& KEYOPENCL
)) AddResult
= 2;
120 else if (!LangOpts
.CPlusPlus
&& (Flags
& KEYNOCXX
)) AddResult
= 2;
122 // Don't add this keyword if disabled in this language.
123 if (AddResult
== 0) return;
125 IdentifierInfo
&Info
= Table
.get(Keyword
, TokenCode
);
126 Info
.setIsExtensionToken(AddResult
== 1);
129 /// AddCXXOperatorKeyword - Register a C++ operator keyword alternative
131 static void AddCXXOperatorKeyword(llvm::StringRef Keyword
,
132 tok::TokenKind TokenCode
,
133 IdentifierTable
&Table
) {
134 IdentifierInfo
&Info
= Table
.get(Keyword
, TokenCode
);
135 Info
.setIsCPlusPlusOperatorKeyword();
138 /// AddObjCKeyword - Register an Objective-C @keyword like "class" "selector" or
140 static void AddObjCKeyword(llvm::StringRef Name
,
141 tok::ObjCKeywordKind ObjCID
,
142 IdentifierTable
&Table
) {
143 Table
.get(Name
).setObjCKeywordID(ObjCID
);
146 /// AddKeywords - Add all keywords to the symbol table.
148 void IdentifierTable::AddKeywords(const LangOptions
&LangOpts
) {
149 // Add keywords and tokens for the current language.
150 #define KEYWORD(NAME, FLAGS) \
151 AddKeyword(llvm::StringRef(#NAME), tok::kw_ ## NAME, \
152 FLAGS, LangOpts, *this);
153 #define ALIAS(NAME, TOK, FLAGS) \
154 AddKeyword(llvm::StringRef(NAME), tok::kw_ ## TOK, \
155 FLAGS, LangOpts, *this);
156 #define CXX_KEYWORD_OPERATOR(NAME, ALIAS) \
157 if (LangOpts.CXXOperatorNames) \
158 AddCXXOperatorKeyword(llvm::StringRef(#NAME), tok::ALIAS, *this);
159 #define OBJC1_AT_KEYWORD(NAME) \
160 if (LangOpts.ObjC1) \
161 AddObjCKeyword(llvm::StringRef(#NAME), tok::objc_##NAME, *this);
162 #define OBJC2_AT_KEYWORD(NAME) \
163 if (LangOpts.ObjC2) \
164 AddObjCKeyword(llvm::StringRef(#NAME), tok::objc_##NAME, *this);
165 #include "clang/Basic/TokenKinds.def"
168 tok::PPKeywordKind
IdentifierInfo::getPPKeywordID() const {
169 // We use a perfect hash function here involving the length of the keyword,
170 // the first and third character. For preprocessor ID's there are no
171 // collisions (if there were, the switch below would complain about duplicate
172 // case values). Note that this depends on 'if' being null terminated.
174 #define HASH(LEN, FIRST, THIRD) \
175 (LEN << 5) + (((FIRST-'a') + (THIRD-'a')) & 31)
176 #define CASE(LEN, FIRST, THIRD, NAME) \
177 case HASH(LEN, FIRST, THIRD): \
178 return memcmp(Name, #NAME, LEN) ? tok::pp_not_keyword : tok::pp_ ## NAME
180 unsigned Len
= getLength();
181 if (Len
< 2) return tok::pp_not_keyword
;
182 const char *Name
= getNameStart();
183 switch (HASH(Len
, Name
[0], Name
[2])) {
184 default: return tok::pp_not_keyword
;
185 CASE( 2, 'i', '\0', if);
186 CASE( 4, 'e', 'i', elif
);
187 CASE( 4, 'e', 's', else);
188 CASE( 4, 'l', 'n', line
);
189 CASE( 4, 's', 'c', sccs
);
190 CASE( 5, 'e', 'd', endif
);
191 CASE( 5, 'e', 'r', error
);
192 CASE( 5, 'i', 'e', ident
);
193 CASE( 5, 'i', 'd', ifdef
);
194 CASE( 5, 'u', 'd', undef
);
196 CASE( 6, 'a', 's', assert);
197 CASE( 6, 'd', 'f', define
);
198 CASE( 6, 'i', 'n', ifndef
);
199 CASE( 6, 'i', 'p', import
);
200 CASE( 6, 'p', 'a', pragma
);
202 CASE( 7, 'd', 'f', defined
);
203 CASE( 7, 'i', 'c', include
);
204 CASE( 7, 'w', 'r', warning
);
206 CASE( 8, 'u', 'a', unassert
);
207 CASE(12, 'i', 'c', include_next
);
209 CASE(16, '_', 'i', __include_macros
);
215 //===----------------------------------------------------------------------===//
216 // Stats Implementation
217 //===----------------------------------------------------------------------===//
219 /// PrintStats - Print statistics about how well the identifier table is doing
220 /// at hashing identifiers.
221 void IdentifierTable::PrintStats() const {
222 unsigned NumBuckets
= HashTable
.getNumBuckets();
223 unsigned NumIdentifiers
= HashTable
.getNumItems();
224 unsigned NumEmptyBuckets
= NumBuckets
-NumIdentifiers
;
225 unsigned AverageIdentifierSize
= 0;
226 unsigned MaxIdentifierLength
= 0;
228 // TODO: Figure out maximum times an identifier had to probe for -stats.
229 for (llvm::StringMap
<IdentifierInfo
*, llvm::BumpPtrAllocator
>::const_iterator
230 I
= HashTable
.begin(), E
= HashTable
.end(); I
!= E
; ++I
) {
231 unsigned IdLen
= I
->getKeyLength();
232 AverageIdentifierSize
+= IdLen
;
233 if (MaxIdentifierLength
< IdLen
)
234 MaxIdentifierLength
= IdLen
;
237 fprintf(stderr
, "\n*** Identifier Table Stats:\n");
238 fprintf(stderr
, "# Identifiers: %d\n", NumIdentifiers
);
239 fprintf(stderr
, "# Empty Buckets: %d\n", NumEmptyBuckets
);
240 fprintf(stderr
, "Hash density (#identifiers per bucket): %f\n",
241 NumIdentifiers
/(double)NumBuckets
);
242 fprintf(stderr
, "Ave identifier length: %f\n",
243 (AverageIdentifierSize
/(double)NumIdentifiers
));
244 fprintf(stderr
, "Max identifier length: %d\n", MaxIdentifierLength
);
246 // Compute statistics about the memory allocated for identifiers.
247 HashTable
.getAllocator().PrintStats();
250 //===----------------------------------------------------------------------===//
251 // SelectorTable Implementation
252 //===----------------------------------------------------------------------===//
254 unsigned llvm::DenseMapInfo
<clang::Selector
>::getHashValue(clang::Selector S
) {
255 return DenseMapInfo
<void*>::getHashValue(S
.getAsOpaquePtr());
259 /// MultiKeywordSelector - One of these variable length records is kept for each
260 /// selector containing more than one keyword. We use a folding set
261 /// to unique aggregate names (keyword selectors in ObjC parlance). Access to
262 /// this class is provided strictly through Selector.
263 class MultiKeywordSelector
264 : public DeclarationNameExtra
, public llvm::FoldingSetNode
{
265 MultiKeywordSelector(unsigned nKeys
) {
266 ExtraKindOrNumArgs
= NUM_EXTRA_KINDS
+ nKeys
;
269 // Constructor for keyword selectors.
270 MultiKeywordSelector(unsigned nKeys
, IdentifierInfo
**IIV
) {
271 assert((nKeys
> 1) && "not a multi-keyword selector");
272 ExtraKindOrNumArgs
= NUM_EXTRA_KINDS
+ nKeys
;
274 // Fill in the trailing keyword array.
275 IdentifierInfo
**KeyInfo
= reinterpret_cast<IdentifierInfo
**>(this+1);
276 for (unsigned i
= 0; i
!= nKeys
; ++i
)
280 // getName - Derive the full selector name and return it.
281 std::string
getName() const;
283 unsigned getNumArgs() const { return ExtraKindOrNumArgs
- NUM_EXTRA_KINDS
; }
285 typedef IdentifierInfo
*const *keyword_iterator
;
286 keyword_iterator
keyword_begin() const {
287 return reinterpret_cast<keyword_iterator
>(this+1);
289 keyword_iterator
keyword_end() const {
290 return keyword_begin()+getNumArgs();
292 IdentifierInfo
*getIdentifierInfoForSlot(unsigned i
) const {
293 assert(i
< getNumArgs() && "getIdentifierInfoForSlot(): illegal index");
294 return keyword_begin()[i
];
296 static void Profile(llvm::FoldingSetNodeID
&ID
,
297 keyword_iterator ArgTys
, unsigned NumArgs
) {
298 ID
.AddInteger(NumArgs
);
299 for (unsigned i
= 0; i
!= NumArgs
; ++i
)
300 ID
.AddPointer(ArgTys
[i
]);
302 void Profile(llvm::FoldingSetNodeID
&ID
) {
303 Profile(ID
, keyword_begin(), getNumArgs());
306 } // end namespace clang.
308 unsigned Selector::getNumArgs() const {
309 unsigned IIF
= getIdentifierInfoFlag();
314 // We point to a MultiKeywordSelector (pointer doesn't contain any flags).
315 MultiKeywordSelector
*SI
= reinterpret_cast<MultiKeywordSelector
*>(InfoPtr
);
316 return SI
->getNumArgs();
319 IdentifierInfo
*Selector::getIdentifierInfoForSlot(unsigned argIndex
) const {
320 if (getIdentifierInfoFlag()) {
321 assert(argIndex
== 0 && "illegal keyword index");
322 return getAsIdentifierInfo();
324 // We point to a MultiKeywordSelector (pointer doesn't contain any flags).
325 MultiKeywordSelector
*SI
= reinterpret_cast<MultiKeywordSelector
*>(InfoPtr
);
326 return SI
->getIdentifierInfoForSlot(argIndex
);
329 std::string
MultiKeywordSelector::getName() const {
330 llvm::SmallString
<256> Str
;
331 llvm::raw_svector_ostream
OS(Str
);
332 for (keyword_iterator I
= keyword_begin(), E
= keyword_end(); I
!= E
; ++I
) {
334 OS
<< (*I
)->getName();
341 std::string
Selector::getAsString() const {
343 return "<null selector>";
345 if (InfoPtr
& ArgFlags
) {
346 IdentifierInfo
*II
= getAsIdentifierInfo();
348 // If the number of arguments is 0 then II is guaranteed to not be null.
349 if (getNumArgs() == 0)
350 return II
->getName();
355 return II
->getName().str() + ":";
358 // We have a multiple keyword selector (no embedded flags).
359 return reinterpret_cast<MultiKeywordSelector
*>(InfoPtr
)->getName();
364 struct SelectorTableImpl
{
365 llvm::FoldingSet
<MultiKeywordSelector
> Table
;
366 llvm::BumpPtrAllocator Allocator
;
368 } // end anonymous namespace.
370 static SelectorTableImpl
&getSelectorTableImpl(void *P
) {
371 return *static_cast<SelectorTableImpl
*>(P
);
375 Selector
SelectorTable::getSelector(unsigned nKeys
, IdentifierInfo
**IIV
) {
377 return Selector(IIV
[0], nKeys
);
379 SelectorTableImpl
&SelTabImpl
= getSelectorTableImpl(Impl
);
381 // Unique selector, to guarantee there is one per name.
382 llvm::FoldingSetNodeID ID
;
383 MultiKeywordSelector::Profile(ID
, IIV
, nKeys
);
386 if (MultiKeywordSelector
*SI
=
387 SelTabImpl
.Table
.FindNodeOrInsertPos(ID
, InsertPos
))
390 // MultiKeywordSelector objects are not allocated with new because they have a
391 // variable size array (for parameter types) at the end of them.
392 unsigned Size
= sizeof(MultiKeywordSelector
) + nKeys
*sizeof(IdentifierInfo
*);
393 MultiKeywordSelector
*SI
=
394 (MultiKeywordSelector
*)SelTabImpl
.Allocator
.Allocate(Size
,
395 llvm::alignOf
<MultiKeywordSelector
>());
396 new (SI
) MultiKeywordSelector(nKeys
, IIV
);
397 SelTabImpl
.Table
.InsertNode(SI
, InsertPos
);
401 SelectorTable::SelectorTable() {
402 Impl
= new SelectorTableImpl();
405 SelectorTable::~SelectorTable() {
406 delete &getSelectorTableImpl(Impl
);
409 const char *clang::getOperatorSpelling(OverloadedOperatorKind Operator
) {
412 case NUM_OVERLOADED_OPERATORS
:
415 #define OVERLOADED_OPERATOR(Name,Spelling,Token,Unary,Binary,MemberOnly) \
416 case OO_##Name: return Spelling;
417 #include "clang/Basic/OperatorKinds.def"