 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
64.8% |
129 / 199 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
71.4% |
142 / 199 |
| |
|
Line Coverage: |
96.6% |
168 / 174 |
| |
 |
|
 |
1 : //===--- IdentifierTable.cpp - Hash table for identifier lookup -----------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the IdentifierInfo, IdentifierVisitor, and
11 : // IdentifierTable interfaces.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
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/Support/raw_ostream.h"
20 : #include <cstdio>
21 :
22 : using namespace clang;
23 :
24 : //===----------------------------------------------------------------------===//
25 : // IdentifierInfo Implementation
26 : //===----------------------------------------------------------------------===//
27 :
28 2323033: IdentifierInfo::IdentifierInfo() {
29 2323033: TokenID = tok::identifier;
30 2323033: ObjCOrBuiltinID = 0;
31 2323033: HasMacro = false;
32 2323033: IsExtension = false;
33 2323033: IsPoisoned = false;
34 2323033: IsCPPOperatorKeyword = false;
35 2323033: NeedsHandleIdentifier = false;
36 2323033: FETokenInfo = 0;
37 2323033: Entry = 0;
38 2323033: }
39 :
40 : //===----------------------------------------------------------------------===//
41 : // IdentifierTable Implementation
42 : //===----------------------------------------------------------------------===//
43 :
45: branch 0 taken
45: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
45: branch 7 taken
44 45: IdentifierInfoLookup::~IdentifierInfoLookup() {}
45 :
44: branch 0 taken
44: branch 1 taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 6 not taken
44: branch 7 taken
46 44: ExternalIdentifierLookup::~ExternalIdentifierLookup() {}
47 :
48 : IdentifierTable::IdentifierTable(const LangOptions &LangOpts,
49 2533: IdentifierInfoLookup* externalLookup)
50 : : HashTable(8192), // Start with space for 8K identifiers.
51 2533: ExternalLookup(externalLookup) {
52 :
53 : // Populate the identifier table with info about keywords for the current
54 : // language.
55 2533: AddKeywords(LangOpts);
56 2533: }
57 :
58 : //===----------------------------------------------------------------------===//
59 : // Language Keyword Implementation
60 : //===----------------------------------------------------------------------===//
61 :
62 : // Constants for TokenKinds.def
63 : namespace {
64 : enum {
65 : KEYALL = 1,
66 : KEYC99 = 2,
67 : KEYCXX = 4,
68 : KEYCXX0X = 8,
69 : KEYGNU = 16,
70 : KEYMS = 32,
71 : BOOLSUPPORT = 64,
72 : KEYALTIVEC = 128
73 : };
74 : }
75 :
76 : /// AddKeyword - This method is used to associate a token ID with specific
77 : /// identifiers because they are language keywords. This causes the lexer to
78 : /// automatically map matching identifiers to specialized token codes.
79 : ///
80 : /// The C90/C99/CPP/CPP0x flags are set to 0 if the token should be
81 : /// enabled in the specified langauge, set to 1 if it is an extension
82 : /// in the specified language, and set to 2 if disabled in the
83 : /// specified language.
84 : static void AddKeyword(const char *Keyword, unsigned KWLen,
85 : tok::TokenKind TokenCode, unsigned Flags,
86 379950: const LangOptions &LangOpts, IdentifierTable &Table) {
87 379950: unsigned AddResult = 0;
202640: branch 0 taken
177310: branch 1 taken
88 379950: if (Flags & KEYALL) AddResult = 2;
62510: branch 0 taken
114800: branch 1 taken
41078: branch 2 taken
21432: branch 3 taken
89 177310: else if (LangOpts.CPlusPlus && (Flags & KEYCXX)) AddResult = 2;
2400: branch 0 taken
133832: branch 1 taken
1300: branch 2 taken
1100: branch 3 taken
90 136232: else if (LangOpts.CPlusPlus0x && (Flags & KEYCXX0X)) AddResult = 2;
112840: branch 0 taken
22092: branch 1 taken
3224: branch 2 taken
109616: branch 3 taken
91 134932: else if (LangOpts.C99 && (Flags & KEYC99)) AddResult = 2;
127622: branch 0 taken
4086: branch 1 taken
3988: branch 2 taken
123634: branch 3 taken
92 131708: else if (LangOpts.GNUMode && (Flags & KEYGNU)) AddResult = 1;
893: branch 0 taken
126827: branch 1 taken
88: branch 2 taken
805: branch 3 taken
93 127720: else if (LangOpts.Microsoft && (Flags & KEYMS)) AddResult = 1;
19503: branch 0 taken
108129: branch 1 taken
2688: branch 2 taken
16815: branch 3 taken
94 127632: else if (LangOpts.Bool && (Flags & BOOLSUPPORT)) AddResult = 2;
347: branch 0 taken
124597: branch 1 taken
18: branch 2 taken
329: branch 3 taken
95 124944: else if (LangOpts.AltiVec && (Flags & KEYALTIVEC)) AddResult = 2;
96 :
97 : // Don't add this keyword if disabled in this language.
255024: branch 0 taken
124926: branch 1 taken
98 379950: if (AddResult == 0) return;
99 :
100 255024: IdentifierInfo &Info = Table.get(Keyword, Keyword+KWLen);
101 255024: Info.setTokenID(TokenCode);
102 255024: Info.setIsExtensionToken(AddResult == 1);
103 : }
104 :
105 : /// AddCXXOperatorKeyword - Register a C++ operator keyword alternative
106 : /// representations.
107 : static void AddCXXOperatorKeyword(const char *Keyword, unsigned KWLen,
108 : tok::TokenKind TokenCode,
109 9845: IdentifierTable &Table) {
110 9845: IdentifierInfo &Info = Table.get(Keyword, Keyword + KWLen);
111 9845: Info.setTokenID(TokenCode);
112 9845: Info.setIsCPlusPlusOperatorKeyword();
113 9845: }
114 :
115 : /// AddObjCKeyword - Register an Objective-C @keyword like "class" "selector" or
116 : /// "property".
117 : static void AddObjCKeyword(tok::ObjCKeywordKind ObjCID,
118 : const char *Name, unsigned NameLen,
119 15624: IdentifierTable &Table) {
120 15624: Table.get(Name, Name+NameLen).setObjCKeywordID(ObjCID);
121 15624: }
122 :
123 : /// AddKeywords - Add all keywords to the symbol table.
124 : ///
125 2533: void IdentifierTable::AddKeywords(const LangOptions &LangOpts) {
126 : // Add keywords and tokens for the current language.
127 : #define KEYWORD(NAME, FLAGS) \
128 : AddKeyword(#NAME, strlen(#NAME), tok::kw_ ## NAME, \
129 : FLAGS, LangOpts, *this);
130 : #define ALIAS(NAME, TOK, FLAGS) \
131 : AddKeyword(NAME, strlen(NAME), tok::kw_ ## TOK, \
132 : FLAGS, LangOpts, *this);
133 : #define CXX_KEYWORD_OPERATOR(NAME, ALIAS) \
134 : if (LangOpts.CXXOperatorNames) \
135 : AddCXXOperatorKeyword(#NAME, strlen(#NAME), tok::ALIAS, *this);
136 : #define OBJC1_AT_KEYWORD(NAME) \
137 : if (LangOpts.ObjC1) \
138 : AddObjCKeyword(tok::objc_##NAME, #NAME, strlen(#NAME), *this);
139 : #define OBJC2_AT_KEYWORD(NAME) \
140 : if (LangOpts.ObjC2) \
141 : AddObjCKeyword(tok::objc_##NAME, #NAME, strlen(#NAME), *this);
142 : #include "clang/Basic/TokenKinds.def"
143 2533: }
144 :
145 551465: tok::PPKeywordKind IdentifierInfo::getPPKeywordID() const {
146 : // We use a perfect hash function here involving the length of the keyword,
147 : // the first and third character. For preprocessor ID's there are no
148 : // collisions (if there were, the switch below would complain about duplicate
149 : // case values). Note that this depends on 'if' being null terminated.
150 :
151 : #define HASH(LEN, FIRST, THIRD) \
152 : (LEN << 5) + (((FIRST-'a') + (THIRD-'a')) & 31)
153 : #define CASE(LEN, FIRST, THIRD, NAME) \
154 : case HASH(LEN, FIRST, THIRD): \
155 : return memcmp(Name, #NAME, LEN) ? tok::pp_not_keyword : tok::pp_ ## NAME
156 :
157 551465: unsigned Len = getLength();
289: branch 0 taken
551176: branch 1 taken
158 551465: if (Len < 2) return tok::pp_not_keyword;
159 551176: const char *Name = getNameStart();
262922: branch 0 taken
2307: branch 1 taken
43: branch 2 taken
609: branch 3 taken
80: branch 4 taken
0: branch 5 not taken
2980: branch 6 taken
23: branch 7 taken
6: branch 8 taken
1568: branch 9 taken
1040: branch 10 taken
2116: branch 11 taken
269954: branch 12 taken
1069: branch 13 taken
10: branch 14 taken
198: branch 15 taken
10: branch 16 taken
1007: branch 17 taken
16: branch 18 taken
2: branch 19 taken
39: branch 20 taken
5177: branch 21 taken
160 551176: switch (HASH(Len, Name[0], Name[2])) {
161 262922: default: return tok::pp_not_keyword;
2307: branch 1 taken
0: branch 2 not taken
162 2307: CASE( 2, 'i', '\0', if);
0: branch 1 not taken
43: branch 2 taken
163 43: CASE( 4, 'e', 'i', elif);
0: branch 1 not taken
609: branch 2 taken
164 609: CASE( 4, 'e', 's', else);
29: branch 1 taken
51: branch 2 taken
165 80: CASE( 4, 'l', 'n', line);
0: branch 1 not taken
0: branch 2 not taken
166 0: CASE( 4, 's', 'c', sccs);
7: branch 1 taken
2973: branch 2 taken
167 2980: CASE( 5, 'e', 'd', endif);
17: branch 1 taken
6: branch 2 taken
168 23: CASE( 5, 'e', 'r', error);
6: branch 1 taken
0: branch 2 not taken
169 6: CASE( 5, 'i', 'e', ident);
26: branch 1 taken
1542: branch 2 taken
170 1568: CASE( 5, 'i', 'd', ifdef);
1: branch 1 taken
1039: branch 2 taken
171 1040: CASE( 5, 'u', 'd', undef);
172 :
2111: branch 1 taken
5: branch 2 taken
173 2116: CASE( 6, 'a', 's', assert);
2: branch 1 taken
269952: branch 2 taken
174 269954: CASE( 6, 'd', 'f', define);
15: branch 1 taken
1054: branch 2 taken
175 1069: CASE( 6, 'i', 'n', ifndef);
6: branch 1 taken
4: branch 2 taken
176 10: CASE( 6, 'i', 'p', import);
9: branch 1 taken
189: branch 2 taken
177 198: CASE( 6, 'p', 'a', pragma);
178 :
10: branch 1 taken
0: branch 2 not taken
179 10: CASE( 7, 'd', 'f', defined);
339: branch 1 taken
668: branch 2 taken
180 1007: CASE( 7, 'i', 'c', include);
0: branch 1 not taken
16: branch 2 taken
181 16: CASE( 7, 'w', 'r', warning);
182 :
2: branch 1 taken
0: branch 2 not taken
183 2: CASE( 8, 'u', 'a', unassert);
22: branch 1 taken
17: branch 2 taken
184 39: CASE(12, 'i', 'c', include_next);
185 :
5176: branch 1 taken
1: branch 2 taken
186 5177: CASE(16, '_', 'i', __include_macros);
187 : #undef CASE
188 : #undef HASH
189 : }
190 : }
191 :
192 : //===----------------------------------------------------------------------===//
193 : // Stats Implementation
194 : //===----------------------------------------------------------------------===//
195 :
196 : /// PrintStats - Print statistics about how well the identifier table is doing
197 : /// at hashing identifiers.
198 2: void IdentifierTable::PrintStats() const {
199 2: unsigned NumBuckets = HashTable.getNumBuckets();
200 2: unsigned NumIdentifiers = HashTable.getNumItems();
201 2: unsigned NumEmptyBuckets = NumBuckets-NumIdentifiers;
202 2: unsigned AverageIdentifierSize = 0;
203 2: unsigned MaxIdentifierLength = 0;
204 :
205 : // TODO: Figure out maximum times an identifier had to probe for -stats.
1804: branch 2 taken
2: branch 3 taken
206 1806: for (llvm::StringMap<IdentifierInfo*, llvm::BumpPtrAllocator>::const_iterator
207 2: I = HashTable.begin(), E = HashTable.end(); I != E; ++I) {
208 1804: unsigned IdLen = I->getKeyLength();
209 1804: AverageIdentifierSize += IdLen;
16: branch 0 taken
1788: branch 1 taken
210 1804: if (MaxIdentifierLength < IdLen)
211 16: MaxIdentifierLength = IdLen;
212 : }
213 :
214 2: fprintf(stderr, "\n*** Identifier Table Stats:\n");
215 2: fprintf(stderr, "# Identifiers: %d\n", NumIdentifiers);
216 2: fprintf(stderr, "# Empty Buckets: %d\n", NumEmptyBuckets);
217 : fprintf(stderr, "Hash density (#identifiers per bucket): %f\n",
218 2: NumIdentifiers/(double)NumBuckets);
219 : fprintf(stderr, "Ave identifier length: %f\n",
220 2: (AverageIdentifierSize/(double)NumIdentifiers));
221 2: fprintf(stderr, "Max identifier length: %d\n", MaxIdentifierLength);
222 :
223 : // Compute statistics about the memory allocated for identifiers.
224 2: HashTable.getAllocator().PrintStats();
225 2: }
226 :
227 : //===----------------------------------------------------------------------===//
228 : // SelectorTable Implementation
229 : //===----------------------------------------------------------------------===//
230 :
231 98051: unsigned llvm::DenseMapInfo<clang::Selector>::getHashValue(clang::Selector S) {
232 98051: return DenseMapInfo<void*>::getHashValue(S.getAsOpaquePtr());
233 : }
234 :
235 : namespace clang {
236 : /// MultiKeywordSelector - One of these variable length records is kept for each
237 : /// selector containing more than one keyword. We use a folding set
238 : /// to unique aggregate names (keyword selectors in ObjC parlance). Access to
239 : /// this class is provided strictly through Selector.
240 : class MultiKeywordSelector
241 : : public DeclarationNameExtra, public llvm::FoldingSetNode {
242 : MultiKeywordSelector(unsigned nKeys) {
243 : ExtraKindOrNumArgs = NUM_EXTRA_KINDS + nKeys;
244 : }
245 : public:
246 : // Constructor for keyword selectors.
247 2661: MultiKeywordSelector(unsigned nKeys, IdentifierInfo **IIV) {
0: branch 0 not taken
2661: branch 1 taken
248 2661: assert((nKeys > 1) && "not a multi-keyword selector");
249 2661: ExtraKindOrNumArgs = NUM_EXTRA_KINDS + nKeys;
250 :
251 : // Fill in the trailing keyword array.
252 2661: IdentifierInfo **KeyInfo = reinterpret_cast<IdentifierInfo **>(this+1);
8794: branch 0 taken
2661: branch 1 taken
253 11455: for (unsigned i = 0; i != nKeys; ++i)
254 8794: KeyInfo[i] = IIV[i];
255 2661: }
256 :
257 : // getName - Derive the full selector name and return it.
258 : std::string getName() const;
259 :
260 32163: unsigned getNumArgs() const { return ExtraKindOrNumArgs - NUM_EXTRA_KINDS; }
261 :
262 : typedef IdentifierInfo *const *keyword_iterator;
263 30642: keyword_iterator keyword_begin() const {
264 30642: return reinterpret_cast<keyword_iterator>(this+1);
265 : }
266 193: keyword_iterator keyword_end() const {
267 193: return keyword_begin()+getNumArgs();
268 : }
269 117: IdentifierInfo *getIdentifierInfoForSlot(unsigned i) const {
117: branch 1 taken
0: branch 2 not taken
270 117: assert(i < getNumArgs() && "getIdentifierInfoForSlot(): illegal index");
271 117: return keyword_begin()[i];
272 : }
273 : static void Profile(llvm::FoldingSetNodeID &ID,
274 60540: keyword_iterator ArgTys, unsigned NumArgs) {
275 60540: ID.AddInteger(NumArgs);
201941: branch 0 taken
60540: branch 1 taken
276 262481: for (unsigned i = 0; i != NumArgs; ++i)
277 201941: ID.AddPointer(ArgTys[i]);
278 60540: }
279 30139: void Profile(llvm::FoldingSetNodeID &ID) {
280 30139: Profile(ID, keyword_begin(), getNumArgs());
281 30139: }
282 : };
283 : } // end namespace clang.
284 :
285 25481: unsigned Selector::getNumArgs() const {
286 25481: unsigned IIF = getIdentifierInfoFlag();
16211: branch 0 taken
9270: branch 1 taken
287 25481: if (IIF == ZeroArg)
288 16211: return 0;
7556: branch 0 taken
1714: branch 1 taken
289 9270: if (IIF == OneArg)
290 7556: return 1;
291 : // We point to a MultiKeywordSelector (pointer doesn't contain any flags).
292 1714: MultiKeywordSelector *SI = reinterpret_cast<MultiKeywordSelector *>(InfoPtr);
293 1714: return SI->getNumArgs();
294 : }
295 :
296 662: IdentifierInfo *Selector::getIdentifierInfoForSlot(unsigned argIndex) const {
545: branch 1 taken
117: branch 2 taken
297 662: if (getIdentifierInfoFlag()) {
0: branch 0 not taken
545: branch 1 taken
298 545: assert(argIndex == 0 && "illegal keyword index");
299 545: return getAsIdentifierInfo();
300 : }
301 : // We point to a MultiKeywordSelector (pointer doesn't contain any flags).
302 117: MultiKeywordSelector *SI = reinterpret_cast<MultiKeywordSelector *>(InfoPtr);
303 117: return SI->getIdentifierInfoForSlot(argIndex);
304 : }
305 :
306 193: std::string MultiKeywordSelector::getName() const {
307 193: llvm::SmallString<256> Str;
308 193: llvm::raw_svector_ostream OS(Str);
510: branch 2 taken
193: branch 3 taken
309 703: for (keyword_iterator I = keyword_begin(), E = keyword_end(); I != E; ++I) {
483: branch 0 taken
27: branch 1 taken
310 510: if (*I)
311 483: OS << (*I)->getName();
312 510: OS << ':';
313 : }
314 :
315 193: return OS.str();
316 : }
317 :
318 1836: std::string Selector::getAsString() const {
0: branch 0 not taken
1836: branch 1 taken
319 1836: if (InfoPtr == 0)
320 0: return "<null selector>";
321 :
1643: branch 0 taken
193: branch 1 taken
322 1836: if (InfoPtr & ArgFlags) {
323 1643: IdentifierInfo *II = getAsIdentifierInfo();
324 :
325 : // If the number of arguments is 0 then II is guaranteed to not be null.
1114: branch 1 taken
529: branch 2 taken
326 1643: if (getNumArgs() == 0)
327 1114: return II->getName();
328 :
4: branch 0 taken
525: branch 1 taken
329 529: if (!II)
330 4: return ":";
331 :
332 525: return II->getName().str() + ":";
333 : }
334 :
335 : // We have a multiple keyword selector (no embedded flags).
336 193: return reinterpret_cast<MultiKeywordSelector *>(InfoPtr)->getName();
337 : }
338 :
339 :
340 : namespace {
341 5063: struct SelectorTableImpl {
342 : llvm::FoldingSet<MultiKeywordSelector> Table;
343 : llvm::BumpPtrAllocator Allocator;
344 : };
345 : } // end anonymous namespace.
346 :
347 32931: static SelectorTableImpl &getSelectorTableImpl(void *P) {
348 32931: return *static_cast<SelectorTableImpl*>(P);
349 : }
350 :
351 :
352 89269: Selector SelectorTable::getSelector(unsigned nKeys, IdentifierInfo **IIV) {
58868: branch 0 taken
30401: branch 1 taken
353 89269: if (nKeys < 2)
354 58868: return Selector(IIV[0], nKeys);
355 :
356 30401: SelectorTableImpl &SelTabImpl = getSelectorTableImpl(Impl);
357 :
358 : // Unique selector, to guarantee there is one per name.
359 30401: llvm::FoldingSetNodeID ID;
360 30401: MultiKeywordSelector::Profile(ID, IIV, nKeys);
361 :
362 30401: void *InsertPos = 0;
27740: branch 0 taken
2661: branch 1 taken
363 30401: if (MultiKeywordSelector *SI =
364 30401: SelTabImpl.Table.FindNodeOrInsertPos(ID, InsertPos))
365 27740: return Selector(SI);
366 :
367 : // MultiKeywordSelector objects are not allocated with new because they have a
368 : // variable size array (for parameter types) at the end of them.
369 2661: unsigned Size = sizeof(MultiKeywordSelector) + nKeys*sizeof(IdentifierInfo *);
370 : MultiKeywordSelector *SI =
371 : (MultiKeywordSelector*)SelTabImpl.Allocator.Allocate(Size,
372 2661: llvm::alignof<MultiKeywordSelector>());
2661: branch 1 taken
0: branch 2 not taken
373 2661: new (SI) MultiKeywordSelector(nKeys, IIV);
2661: branch 0 taken
0: branch 1 not taken
374 2661: SelTabImpl.Table.InsertNode(SI, InsertPos);
375 2661: return Selector(SI);
376 : }
377 :
378 2533: SelectorTable::SelectorTable() {
379 2533: Impl = new SelectorTableImpl();
380 2533: }
381 :
382 2530: SelectorTable::~SelectorTable() {
2530: branch 1 taken
0: branch 2 not taken
0: branch 6 not taken
0: branch 7 not taken
383 2530: delete &getSelectorTableImpl(Impl);
384 2530: }
385 :
386 0: const char *clang::getOperatorSpelling(OverloadedOperatorKind Operator) {
0: branch 0 not taken
0: branch 1 not taken
0: branch 2 not taken
0: branch 3 not taken
0: branch 4 not taken
0: branch 5 not taken
0: branch 6 not taken
0: branch 7 not taken
0: branch 8 not taken
0: branch 9 not taken
0: branch 10 not taken
0: branch 11 not taken
0: branch 12 not taken
0: branch 13 not taken
0: branch 14 not taken
0: branch 15 not taken
0: branch 16 not taken
0: branch 17 not taken
0: branch 18 not taken
0: branch 19 not taken
0: branch 20 not taken
0: branch 21 not taken
0: branch 22 not taken
0: branch 23 not taken
0: branch 24 not taken
0: branch 25 not taken
0: branch 26 not taken
0: branch 27 not taken
0: branch 28 not taken
0: branch 29 not taken
0: branch 30 not taken
0: branch 31 not taken
0: branch 32 not taken
0: branch 33 not taken
0: branch 34 not taken
0: branch 35 not taken
0: branch 36 not taken
0: branch 37 not taken
0: branch 38 not taken
0: branch 39 not taken
0: branch 40 not taken
0: branch 41 not taken
0: branch 42 not taken
0: branch 43 not taken
0: branch 44 not taken
387 0: switch (Operator) {
388 : case OO_None:
389 : case NUM_OVERLOADED_OPERATORS:
390 0: return 0;
391 :
392 : #define OVERLOADED_OPERATOR(Name,Spelling,Token,Unary,Binary,MemberOnly) \
393 : case OO_##Name: return Spelling;
394 : #include "clang/Basic/OperatorKinds.def"
395 : }
396 :
397 0: return 0;
398 : }
399 :
Generated: 2010-02-10 01:31 by zcov