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/CharInfo.h" 16 #include "clang/Basic/IdentifierTable.h" 17 #include "clang/Basic/LangOptions.h" 18 #include "clang/Basic/OperatorKinds.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/FoldingSet.h" 21 #include "llvm/ADT/SmallString.h" 22 #include "llvm/Support/ErrorHandling.h" 23 #include "llvm/Support/raw_ostream.h" 24 #include <cstdio> 25 26 using namespace clang; 27 28 //===----------------------------------------------------------------------===// 29 // IdentifierInfo Implementation 30 //===----------------------------------------------------------------------===// 31 32 IdentifierInfo::IdentifierInfo() { 33 TokenID = tok::identifier; 34 ObjCOrBuiltinID = 0; 35 HasMacro = false; 36 HadMacro = false; 37 IsExtension = false; 38 IsCXX11CompatKeyword = false; 39 IsPoisoned = false; 40 IsCPPOperatorKeyword = false; 41 NeedsHandleIdentifier = false; 42 IsFromAST = false; 43 ChangedAfterLoad = false; 44 RevertedTokenID = false; 45 OutOfDate = false; 46 IsModulesImport = false; 47 FETokenInfo = nullptr; 48 Entry = nullptr; 49 } 50 51 //===----------------------------------------------------------------------===// 52 // IdentifierTable Implementation 53 //===----------------------------------------------------------------------===// 54 55 IdentifierIterator::~IdentifierIterator() { } 56 57 IdentifierInfoLookup::~IdentifierInfoLookup() {} 58 59 namespace { 60 /// \brief A simple identifier lookup iterator that represents an 61 /// empty sequence of identifiers. 62 class EmptyLookupIterator : public IdentifierIterator 63 { 64 public: 65 StringRef Next() override { return StringRef(); } 66 }; 67 } 68 69 IdentifierIterator *IdentifierInfoLookup::getIdentifiers() { 70 return new EmptyLookupIterator(); 71 } 72 73 ExternalIdentifierLookup::~ExternalIdentifierLookup() {} 74 75 IdentifierTable::IdentifierTable(const LangOptions &LangOpts, 76 IdentifierInfoLookup* externalLookup) 77 : HashTable(8192), // Start with space for 8K identifiers. 78 ExternalLookup(externalLookup) { 79 80 // Populate the identifier table with info about keywords for the current 81 // language. 82 AddKeywords(LangOpts); 83 84 85 // Add the '_experimental_modules_import' contextual keyword. 86 get("import").setModulesImport(true); 87 } 88 89 //===----------------------------------------------------------------------===// 90 // Language Keyword Implementation 91 //===----------------------------------------------------------------------===// 92 93 // Constants for TokenKinds.def 94 namespace { 95 enum { 96 KEYC99 = 0x1, 97 KEYCXX = 0x2, 98 KEYCXX11 = 0x4, 99 KEYGNU = 0x8, 100 KEYMS = 0x10, 101 BOOLSUPPORT = 0x20, 102 KEYALTIVEC = 0x40, 103 KEYNOCXX = 0x80, 104 KEYBORLAND = 0x100, 105 KEYOPENCL = 0x200, 106 KEYC11 = 0x400, 107 KEYARC = 0x800, 108 KEYNOMS = 0x01000, 109 WCHARSUPPORT = 0x02000, 110 HALFSUPPORT = 0x04000, 111 KEYALL = (0xffff & ~KEYNOMS) // Because KEYNOMS is used to exclude. 112 }; 113 } 114 115 /// AddKeyword - This method is used to associate a token ID with specific 116 /// identifiers because they are language keywords. This causes the lexer to 117 /// automatically map matching identifiers to specialized token codes. 118 /// 119 /// The C90/C99/CPP/CPP0x flags are set to 3 if the token is a keyword in a 120 /// future language standard, set to 2 if the token should be enabled in the 121 /// specified language, set to 1 if it is an extension in the specified 122 /// language, and set to 0 if disabled in the specified language. 123 static void AddKeyword(StringRef Keyword, 124 tok::TokenKind TokenCode, unsigned Flags, 125 const LangOptions &LangOpts, IdentifierTable &Table) { 126 unsigned AddResult = 0; 127 if (Flags == KEYALL) AddResult = 2; 128 else if (LangOpts.CPlusPlus && (Flags & KEYCXX)) AddResult = 2; 129 else if (LangOpts.CPlusPlus11 && (Flags & KEYCXX11)) AddResult = 2; 130 else if (LangOpts.C99 && (Flags & KEYC99)) AddResult = 2; 131 else if (LangOpts.GNUKeywords && (Flags & KEYGNU)) AddResult = 1; 132 else if (LangOpts.MicrosoftExt && (Flags & KEYMS)) AddResult = 1; 133 else if (LangOpts.Borland && (Flags & KEYBORLAND)) AddResult = 1; 134 else if (LangOpts.Bool && (Flags & BOOLSUPPORT)) AddResult = 2; 135 else if (LangOpts.Half && (Flags & HALFSUPPORT)) AddResult = 2; 136 else if (LangOpts.WChar && (Flags & WCHARSUPPORT)) AddResult = 2; 137 else if (LangOpts.AltiVec && (Flags & KEYALTIVEC)) AddResult = 2; 138 else if (LangOpts.OpenCL && (Flags & KEYOPENCL)) AddResult = 2; 139 else if (!LangOpts.CPlusPlus && (Flags & KEYNOCXX)) AddResult = 2; 140 else if (LangOpts.C11 && (Flags & KEYC11)) AddResult = 2; 141 // We treat bridge casts as objective-C keywords so we can warn on them 142 // in non-arc mode. 143 else if (LangOpts.ObjC2 && (Flags & KEYARC)) AddResult = 2; 144 else if (LangOpts.CPlusPlus && (Flags & KEYCXX11)) AddResult = 3; 145 146 // Don't add this keyword under MSVCCompat. 147 if (LangOpts.MSVCCompat && (Flags & KEYNOMS)) 148 return; 149 // Don't add this keyword if disabled in this language. 150 if (AddResult == 0) return; 151 152 IdentifierInfo &Info = 153 Table.get(Keyword, AddResult == 3 ? tok::identifier : TokenCode); 154 Info.setIsExtensionToken(AddResult == 1); 155 Info.setIsCXX11CompatKeyword(AddResult == 3); 156 } 157 158 /// AddCXXOperatorKeyword - Register a C++ operator keyword alternative 159 /// representations. 160 static void AddCXXOperatorKeyword(StringRef Keyword, 161 tok::TokenKind TokenCode, 162 IdentifierTable &Table) { 163 IdentifierInfo &Info = Table.get(Keyword, TokenCode); 164 Info.setIsCPlusPlusOperatorKeyword(); 165 } 166 167 /// AddObjCKeyword - Register an Objective-C \@keyword like "class" "selector" 168 /// or "property". 169 static void AddObjCKeyword(StringRef Name, 170 tok::ObjCKeywordKind ObjCID, 171 IdentifierTable &Table) { 172 Table.get(Name).setObjCKeywordID(ObjCID); 173 } 174 175 /// AddKeywords - Add all keywords to the symbol table. 176 /// 177 void IdentifierTable::AddKeywords(const LangOptions &LangOpts) { 178 // Add keywords and tokens for the current language. 179 #define KEYWORD(NAME, FLAGS) \ 180 AddKeyword(StringRef(#NAME), tok::kw_ ## NAME, \ 181 FLAGS, LangOpts, *this); 182 #define ALIAS(NAME, TOK, FLAGS) \ 183 AddKeyword(StringRef(NAME), tok::kw_ ## TOK, \ 184 FLAGS, LangOpts, *this); 185 #define CXX_KEYWORD_OPERATOR(NAME, ALIAS) \ 186 if (LangOpts.CXXOperatorNames) \ 187 AddCXXOperatorKeyword(StringRef(#NAME), tok::ALIAS, *this); 188 #define OBJC1_AT_KEYWORD(NAME) \ 189 if (LangOpts.ObjC1) \ 190 AddObjCKeyword(StringRef(#NAME), tok::objc_##NAME, *this); 191 #define OBJC2_AT_KEYWORD(NAME) \ 192 if (LangOpts.ObjC2) \ 193 AddObjCKeyword(StringRef(#NAME), tok::objc_##NAME, *this); 194 #define TESTING_KEYWORD(NAME, FLAGS) 195 #include "clang/Basic/TokenKinds.def" 196 197 if (LangOpts.ParseUnknownAnytype) 198 AddKeyword("__unknown_anytype", tok::kw___unknown_anytype, KEYALL, 199 LangOpts, *this); 200 } 201 202 tok::PPKeywordKind IdentifierInfo::getPPKeywordID() const { 203 // We use a perfect hash function here involving the length of the keyword, 204 // the first and third character. For preprocessor ID's there are no 205 // collisions (if there were, the switch below would complain about duplicate 206 // case values). Note that this depends on 'if' being null terminated. 207 208 #define HASH(LEN, FIRST, THIRD) \ 209 (LEN << 5) + (((FIRST-'a') + (THIRD-'a')) & 31) 210 #define CASE(LEN, FIRST, THIRD, NAME) \ 211 case HASH(LEN, FIRST, THIRD): \ 212 return memcmp(Name, #NAME, LEN) ? tok::pp_not_keyword : tok::pp_ ## NAME 213 214 unsigned Len = getLength(); 215 if (Len < 2) return tok::pp_not_keyword; 216 const char *Name = getNameStart(); 217 switch (HASH(Len, Name[0], Name[2])) { 218 default: return tok::pp_not_keyword; 219 CASE( 2, 'i', '\0', if); 220 CASE( 4, 'e', 'i', elif); 221 CASE( 4, 'e', 's', else); 222 CASE( 4, 'l', 'n', line); 223 CASE( 4, 's', 'c', sccs); 224 CASE( 5, 'e', 'd', endif); 225 CASE( 5, 'e', 'r', error); 226 CASE( 5, 'i', 'e', ident); 227 CASE( 5, 'i', 'd', ifdef); 228 CASE( 5, 'u', 'd', undef); 229 230 CASE( 6, 'a', 's', assert); 231 CASE( 6, 'd', 'f', define); 232 CASE( 6, 'i', 'n', ifndef); 233 CASE( 6, 'i', 'p', import); 234 CASE( 6, 'p', 'a', pragma); 235 236 CASE( 7, 'd', 'f', defined); 237 CASE( 7, 'i', 'c', include); 238 CASE( 7, 'w', 'r', warning); 239 240 CASE( 8, 'u', 'a', unassert); 241 CASE(12, 'i', 'c', include_next); 242 243 CASE(14, '_', 'p', __public_macro); 244 245 CASE(15, '_', 'p', __private_macro); 246 247 CASE(16, '_', 'i', __include_macros); 248 #undef CASE 249 #undef HASH 250 } 251 } 252 253 //===----------------------------------------------------------------------===// 254 // Stats Implementation 255 //===----------------------------------------------------------------------===// 256 257 /// PrintStats - Print statistics about how well the identifier table is doing 258 /// at hashing identifiers. 259 void IdentifierTable::PrintStats() const { 260 unsigned NumBuckets = HashTable.getNumBuckets(); 261 unsigned NumIdentifiers = HashTable.getNumItems(); 262 unsigned NumEmptyBuckets = NumBuckets-NumIdentifiers; 263 unsigned AverageIdentifierSize = 0; 264 unsigned MaxIdentifierLength = 0; 265 266 // TODO: Figure out maximum times an identifier had to probe for -stats. 267 for (llvm::StringMap<IdentifierInfo*, llvm::BumpPtrAllocator>::const_iterator 268 I = HashTable.begin(), E = HashTable.end(); I != E; ++I) { 269 unsigned IdLen = I->getKeyLength(); 270 AverageIdentifierSize += IdLen; 271 if (MaxIdentifierLength < IdLen) 272 MaxIdentifierLength = IdLen; 273 } 274 275 fprintf(stderr, "\n*** Identifier Table Stats:\n"); 276 fprintf(stderr, "# Identifiers: %d\n", NumIdentifiers); 277 fprintf(stderr, "# Empty Buckets: %d\n", NumEmptyBuckets); 278 fprintf(stderr, "Hash density (#identifiers per bucket): %f\n", 279 NumIdentifiers/(double)NumBuckets); 280 fprintf(stderr, "Ave identifier length: %f\n", 281 (AverageIdentifierSize/(double)NumIdentifiers)); 282 fprintf(stderr, "Max identifier length: %d\n", MaxIdentifierLength); 283 284 // Compute statistics about the memory allocated for identifiers. 285 HashTable.getAllocator().PrintStats(); 286 } 287 288 //===----------------------------------------------------------------------===// 289 // SelectorTable Implementation 290 //===----------------------------------------------------------------------===// 291 292 unsigned llvm::DenseMapInfo<clang::Selector>::getHashValue(clang::Selector S) { 293 return DenseMapInfo<void*>::getHashValue(S.getAsOpaquePtr()); 294 } 295 296 namespace clang { 297 /// MultiKeywordSelector - One of these variable length records is kept for each 298 /// selector containing more than one keyword. We use a folding set 299 /// to unique aggregate names (keyword selectors in ObjC parlance). Access to 300 /// this class is provided strictly through Selector. 301 class MultiKeywordSelector 302 : public DeclarationNameExtra, public llvm::FoldingSetNode { 303 MultiKeywordSelector(unsigned nKeys) { 304 ExtraKindOrNumArgs = NUM_EXTRA_KINDS + nKeys; 305 } 306 public: 307 // Constructor for keyword selectors. 308 MultiKeywordSelector(unsigned nKeys, IdentifierInfo **IIV) { 309 assert((nKeys > 1) && "not a multi-keyword selector"); 310 ExtraKindOrNumArgs = NUM_EXTRA_KINDS + nKeys; 311 312 // Fill in the trailing keyword array. 313 IdentifierInfo **KeyInfo = reinterpret_cast<IdentifierInfo **>(this+1); 314 for (unsigned i = 0; i != nKeys; ++i) 315 KeyInfo[i] = IIV[i]; 316 } 317 318 // getName - Derive the full selector name and return it. 319 std::string getName() const; 320 321 unsigned getNumArgs() const { return ExtraKindOrNumArgs - NUM_EXTRA_KINDS; } 322 323 typedef IdentifierInfo *const *keyword_iterator; 324 keyword_iterator keyword_begin() const { 325 return reinterpret_cast<keyword_iterator>(this+1); 326 } 327 keyword_iterator keyword_end() const { 328 return keyword_begin()+getNumArgs(); 329 } 330 IdentifierInfo *getIdentifierInfoForSlot(unsigned i) const { 331 assert(i < getNumArgs() && "getIdentifierInfoForSlot(): illegal index"); 332 return keyword_begin()[i]; 333 } 334 static void Profile(llvm::FoldingSetNodeID &ID, 335 keyword_iterator ArgTys, unsigned NumArgs) { 336 ID.AddInteger(NumArgs); 337 for (unsigned i = 0; i != NumArgs; ++i) 338 ID.AddPointer(ArgTys[i]); 339 } 340 void Profile(llvm::FoldingSetNodeID &ID) { 341 Profile(ID, keyword_begin(), getNumArgs()); 342 } 343 }; 344 } // end namespace clang. 345 346 unsigned Selector::getNumArgs() const { 347 unsigned IIF = getIdentifierInfoFlag(); 348 if (IIF <= ZeroArg) 349 return 0; 350 if (IIF == OneArg) 351 return 1; 352 // We point to a MultiKeywordSelector. 353 MultiKeywordSelector *SI = getMultiKeywordSelector(); 354 return SI->getNumArgs(); 355 } 356 357 IdentifierInfo *Selector::getIdentifierInfoForSlot(unsigned argIndex) const { 358 if (getIdentifierInfoFlag() < MultiArg) { 359 assert(argIndex == 0 && "illegal keyword index"); 360 return getAsIdentifierInfo(); 361 } 362 // We point to a MultiKeywordSelector. 363 MultiKeywordSelector *SI = getMultiKeywordSelector(); 364 return SI->getIdentifierInfoForSlot(argIndex); 365 } 366 367 StringRef Selector::getNameForSlot(unsigned int argIndex) const { 368 IdentifierInfo *II = getIdentifierInfoForSlot(argIndex); 369 return II? II->getName() : StringRef(); 370 } 371 372 std::string MultiKeywordSelector::getName() const { 373 SmallString<256> Str; 374 llvm::raw_svector_ostream OS(Str); 375 for (keyword_iterator I = keyword_begin(), E = keyword_end(); I != E; ++I) { 376 if (*I) 377 OS << (*I)->getName(); 378 OS << ':'; 379 } 380 381 return OS.str(); 382 } 383 384 std::string Selector::getAsString() const { 385 if (InfoPtr == 0) 386 return "<null selector>"; 387 388 if (getIdentifierInfoFlag() < MultiArg) { 389 IdentifierInfo *II = getAsIdentifierInfo(); 390 391 // If the number of arguments is 0 then II is guaranteed to not be null. 392 if (getNumArgs() == 0) 393 return II->getName(); 394 395 if (!II) 396 return ":"; 397 398 return II->getName().str() + ":"; 399 } 400 401 // We have a multiple keyword selector. 402 return getMultiKeywordSelector()->getName(); 403 } 404 405 void Selector::print(llvm::raw_ostream &OS) const { 406 OS << getAsString(); 407 } 408 409 /// Interpreting the given string using the normal CamelCase 410 /// conventions, determine whether the given string starts with the 411 /// given "word", which is assumed to end in a lowercase letter. 412 static bool startsWithWord(StringRef name, StringRef word) { 413 if (name.size() < word.size()) return false; 414 return ((name.size() == word.size() || !isLowercase(name[word.size()])) && 415 name.startswith(word)); 416 } 417 418 ObjCMethodFamily Selector::getMethodFamilyImpl(Selector sel) { 419 IdentifierInfo *first = sel.getIdentifierInfoForSlot(0); 420 if (!first) return OMF_None; 421 422 StringRef name = first->getName(); 423 if (sel.isUnarySelector()) { 424 if (name == "autorelease") return OMF_autorelease; 425 if (name == "dealloc") return OMF_dealloc; 426 if (name == "finalize") return OMF_finalize; 427 if (name == "release") return OMF_release; 428 if (name == "retain") return OMF_retain; 429 if (name == "retainCount") return OMF_retainCount; 430 if (name == "self") return OMF_self; 431 } 432 433 if (name == "performSelector") return OMF_performSelector; 434 435 // The other method families may begin with a prefix of underscores. 436 while (!name.empty() && name.front() == '_') 437 name = name.substr(1); 438 439 if (name.empty()) return OMF_None; 440 switch (name.front()) { 441 case 'a': 442 if (startsWithWord(name, "alloc")) return OMF_alloc; 443 break; 444 case 'c': 445 if (startsWithWord(name, "copy")) return OMF_copy; 446 break; 447 case 'i': 448 if (startsWithWord(name, "init")) return OMF_init; 449 break; 450 case 'm': 451 if (startsWithWord(name, "mutableCopy")) return OMF_mutableCopy; 452 break; 453 case 'n': 454 if (startsWithWord(name, "new")) return OMF_new; 455 break; 456 default: 457 break; 458 } 459 460 return OMF_None; 461 } 462 463 ObjCInstanceTypeFamily Selector::getInstTypeMethodFamily(Selector sel) { 464 IdentifierInfo *first = sel.getIdentifierInfoForSlot(0); 465 if (!first) return OIT_None; 466 467 StringRef name = first->getName(); 468 469 if (name.empty()) return OIT_None; 470 switch (name.front()) { 471 case 'a': 472 if (startsWithWord(name, "array")) return OIT_Array; 473 break; 474 case 'd': 475 if (startsWithWord(name, "default")) return OIT_ReturnsSelf; 476 if (startsWithWord(name, "dictionary")) return OIT_Dictionary; 477 break; 478 case 's': 479 if (startsWithWord(name, "shared")) return OIT_ReturnsSelf; 480 if (startsWithWord(name, "standard")) return OIT_Singleton; 481 case 'i': 482 if (startsWithWord(name, "init")) return OIT_Init; 483 default: 484 break; 485 } 486 return OIT_None; 487 } 488 489 namespace { 490 struct SelectorTableImpl { 491 llvm::FoldingSet<MultiKeywordSelector> Table; 492 llvm::BumpPtrAllocator Allocator; 493 }; 494 } // end anonymous namespace. 495 496 static SelectorTableImpl &getSelectorTableImpl(void *P) { 497 return *static_cast<SelectorTableImpl*>(P); 498 } 499 500 SmallString<64> 501 SelectorTable::constructSetterName(StringRef Name) { 502 SmallString<64> SetterName("set"); 503 SetterName += Name; 504 SetterName[3] = toUppercase(SetterName[3]); 505 return SetterName; 506 } 507 508 Selector 509 SelectorTable::constructSetterSelector(IdentifierTable &Idents, 510 SelectorTable &SelTable, 511 const IdentifierInfo *Name) { 512 IdentifierInfo *SetterName = 513 &Idents.get(constructSetterName(Name->getName())); 514 return SelTable.getUnarySelector(SetterName); 515 } 516 517 size_t SelectorTable::getTotalMemory() const { 518 SelectorTableImpl &SelTabImpl = getSelectorTableImpl(Impl); 519 return SelTabImpl.Allocator.getTotalMemory(); 520 } 521 522 Selector SelectorTable::getSelector(unsigned nKeys, IdentifierInfo **IIV) { 523 if (nKeys < 2) 524 return Selector(IIV[0], nKeys); 525 526 SelectorTableImpl &SelTabImpl = getSelectorTableImpl(Impl); 527 528 // Unique selector, to guarantee there is one per name. 529 llvm::FoldingSetNodeID ID; 530 MultiKeywordSelector::Profile(ID, IIV, nKeys); 531 532 void *InsertPos = nullptr; 533 if (MultiKeywordSelector *SI = 534 SelTabImpl.Table.FindNodeOrInsertPos(ID, InsertPos)) 535 return Selector(SI); 536 537 // MultiKeywordSelector objects are not allocated with new because they have a 538 // variable size array (for parameter types) at the end of them. 539 unsigned Size = sizeof(MultiKeywordSelector) + nKeys*sizeof(IdentifierInfo *); 540 MultiKeywordSelector *SI = 541 (MultiKeywordSelector*)SelTabImpl.Allocator.Allocate(Size, 542 llvm::alignOf<MultiKeywordSelector>()); 543 new (SI) MultiKeywordSelector(nKeys, IIV); 544 SelTabImpl.Table.InsertNode(SI, InsertPos); 545 return Selector(SI); 546 } 547 548 SelectorTable::SelectorTable() { 549 Impl = new SelectorTableImpl(); 550 } 551 552 SelectorTable::~SelectorTable() { 553 delete &getSelectorTableImpl(Impl); 554 } 555 556 const char *clang::getOperatorSpelling(OverloadedOperatorKind Operator) { 557 switch (Operator) { 558 case OO_None: 559 case NUM_OVERLOADED_OPERATORS: 560 return nullptr; 561 562 #define OVERLOADED_OPERATOR(Name,Spelling,Token,Unary,Binary,MemberOnly) \ 563 case OO_##Name: return Spelling; 564 #include "clang/Basic/OperatorKinds.def" 565 } 566 567 llvm_unreachable("Invalid OverloadedOperatorKind!"); 568 } 569