diff options
Diffstat (limited to 'clang/Basic/IdentifierTable.cpp')
| -rw-r--r-- | clang/Basic/IdentifierTable.cpp | 551 |
1 files changed, 0 insertions, 551 deletions
diff --git a/clang/Basic/IdentifierTable.cpp b/clang/Basic/IdentifierTable.cpp deleted file mode 100644 index 65e984a0f78..00000000000 --- a/clang/Basic/IdentifierTable.cpp +++ /dev/null @@ -1,551 +0,0 @@ -//===--- IdentifierTable.cpp - Hash table for identifier lookup -----------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the IdentifierInfo, IdentifierVisitor, and -// IdentifierTable interfaces. -// -//===----------------------------------------------------------------------===// - -#include "clang/Basic/IdentifierTable.h" -#include "clang/Basic/LangOptions.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/Bitcode/Serialize.h" -#include "llvm/Bitcode/Deserialize.h" - -using namespace clang; - -//===----------------------------------------------------------------------===// -// IdentifierInfo Implementation -//===----------------------------------------------------------------------===// - -IdentifierInfo::IdentifierInfo() { - TokenID = tok::identifier; - ObjCID = tok::objc_not_keyword; - BuiltinID = 0; - HasMacro = false; - IsExtension = false; - IsPoisoned = false; - IsCPPOperatorKeyword = false; - FETokenInfo = 0; -} - -//===----------------------------------------------------------------------===// -// IdentifierTable Implementation -//===----------------------------------------------------------------------===// - -IdentifierTable::IdentifierTable(const LangOptions &LangOpts) - // Start with space for 8K identifiers. - : HashTable(8192) { - - // Populate the identifier table with info about keywords for the current - // language. - AddKeywords(LangOpts); -} - -// This cstor is intended to be used only for serialization. -IdentifierTable::IdentifierTable() : HashTable(8192) {} - -//===----------------------------------------------------------------------===// -// Language Keyword Implementation -//===----------------------------------------------------------------------===// - -/// AddKeyword - This method is used to associate a token ID with specific -/// identifiers because they are language keywords. This causes the lexer to -/// automatically map matching identifiers to specialized token codes. -/// -/// The C90/C99/CPP/CPP0x flags are set to 0 if the token should be -/// enabled in the specified langauge, set to 1 if it is an extension -/// in the specified language, and set to 2 if disabled in the -/// specified language. -static void AddKeyword(const char *Keyword, unsigned KWLen, - tok::TokenKind TokenCode, - int C90, int C99, int CXX, int CXX0x, int BoolSupport, - const LangOptions &LangOpts, IdentifierTable &Table) { - int Flags = 0; - if (BoolSupport != 0) { - Flags = LangOpts.Boolean ? BoolSupport : 2; - } else if (LangOpts.CPlusPlus) { - Flags = LangOpts.CPlusPlus0x ? CXX0x : CXX; - } else if (LangOpts.C99) { - Flags = C99; - } else { - Flags = C90; - } - - // Don't add this keyword if disabled in this language or if an extension - // and extensions are disabled. - if (Flags + LangOpts.NoExtensions >= 2) return; - - IdentifierInfo &Info = Table.get(Keyword, Keyword+KWLen); - Info.setTokenID(TokenCode); - Info.setIsExtensionToken(Flags == 1); -} - -static void AddAlias(const char *Keyword, unsigned KWLen, - tok::TokenKind AliaseeID, - const char *AliaseeKeyword, unsigned AliaseeKWLen, - const LangOptions &LangOpts, IdentifierTable &Table) { - IdentifierInfo &AliasInfo = Table.get(Keyword, Keyword+KWLen); - IdentifierInfo &AliaseeInfo = Table.get(AliaseeKeyword, - AliaseeKeyword+AliaseeKWLen); - AliasInfo.setTokenID(AliaseeID); - AliasInfo.setIsExtensionToken(AliaseeInfo.isExtensionToken()); -} - -/// AddCXXOperatorKeyword - Register a C++ operator keyword alternative -/// representations. -static void AddCXXOperatorKeyword(const char *Keyword, unsigned KWLen, - tok::TokenKind TokenCode, - IdentifierTable &Table) { - IdentifierInfo &Info = Table.get(Keyword, Keyword + KWLen); - Info.setTokenID(TokenCode); - Info.setIsCPlusPlusOperatorKeyword(); -} - -/// AddObjCKeyword - Register an Objective-C @keyword like "class" "selector" or -/// "property". -static void AddObjCKeyword(tok::ObjCKeywordKind ObjCID, - const char *Name, unsigned NameLen, - IdentifierTable &Table) { - Table.get(Name, Name+NameLen).setObjCKeywordID(ObjCID); -} - -/// AddKeywords - Add all keywords to the symbol table. -/// -void IdentifierTable::AddKeywords(const LangOptions &LangOpts) { - enum { - C90Shift = 0, - EXTC90 = 1 << C90Shift, - NOTC90 = 2 << C90Shift, - C99Shift = 2, - EXTC99 = 1 << C99Shift, - NOTC99 = 2 << C99Shift, - CPPShift = 4, - EXTCPP = 1 << CPPShift, - NOTCPP = 2 << CPPShift, - CPP0xShift = 6, - EXTCPP0x = 1 << CPP0xShift, - NOTCPP0x = 2 << CPP0xShift, - BoolShift = 8, - BOOLSUPPORT = 1 << BoolShift, - Mask = 3 - }; - - // Add keywords and tokens for the current language. -#define KEYWORD(NAME, FLAGS) \ - AddKeyword(#NAME, strlen(#NAME), tok::kw_ ## NAME, \ - ((FLAGS) >> C90Shift) & Mask, \ - ((FLAGS) >> C99Shift) & Mask, \ - ((FLAGS) >> CPPShift) & Mask, \ - ((FLAGS) >> CPP0xShift) & Mask, \ - ((FLAGS) >> BoolShift) & Mask, LangOpts, *this); -#define ALIAS(NAME, TOK) \ - AddAlias(NAME, strlen(NAME), tok::kw_ ## TOK, #TOK, strlen(#TOK), \ - LangOpts, *this); -#define CXX_KEYWORD_OPERATOR(NAME, ALIAS) \ - if (LangOpts.CXXOperatorNames) \ - AddCXXOperatorKeyword(#NAME, strlen(#NAME), tok::ALIAS, *this); -#define OBJC1_AT_KEYWORD(NAME) \ - if (LangOpts.ObjC1) \ - AddObjCKeyword(tok::objc_##NAME, #NAME, strlen(#NAME), *this); -#define OBJC2_AT_KEYWORD(NAME) \ - if (LangOpts.ObjC2) \ - AddObjCKeyword(tok::objc_##NAME, #NAME, strlen(#NAME), *this); -#include "clang/Basic/TokenKinds.def" -} - -tok::PPKeywordKind IdentifierInfo::getPPKeywordID() const { - // We use a perfect hash function here involving the length of the keyword, - // the first and third character. For preprocessor ID's there are no - // collisions (if there were, the switch below would complain about duplicate - // case values). Note that this depends on 'if' being null terminated. - -#define HASH(LEN, FIRST, THIRD) \ - (LEN << 5) + (((FIRST-'a') + (THIRD-'a')) & 31) -#define CASE(LEN, FIRST, THIRD, NAME) \ - case HASH(LEN, FIRST, THIRD): \ - return memcmp(Name, #NAME, LEN) ? tok::pp_not_keyword : tok::pp_ ## NAME - - unsigned Len = getLength(); - if (Len < 2) return tok::pp_not_keyword; - const char *Name = getName(); - switch (HASH(Len, Name[0], Name[2])) { - default: return tok::pp_not_keyword; - CASE( 2, 'i', '\0', if); - CASE( 4, 'e', 'i', elif); - CASE( 4, 'e', 's', else); - CASE( 4, 'l', 'n', line); - CASE( 4, 's', 'c', sccs); - CASE( 5, 'e', 'd', endif); - CASE( 5, 'e', 'r', error); - CASE( 5, 'i', 'e', ident); - CASE( 5, 'i', 'd', ifdef); - CASE( 5, 'u', 'd', undef); - - CASE( 6, 'a', 's', assert); - CASE( 6, 'd', 'f', define); - CASE( 6, 'i', 'n', ifndef); - CASE( 6, 'i', 'p', import); - CASE( 6, 'p', 'a', pragma); - - CASE( 7, 'd', 'f', defined); - CASE( 7, 'i', 'c', include); - CASE( 7, 'w', 'r', warning); - - CASE( 8, 'u', 'a', unassert); - CASE(12, 'i', 'c', include_next); -#undef CASE -#undef HASH - } -} - -//===----------------------------------------------------------------------===// -// Stats Implementation -//===----------------------------------------------------------------------===// - -/// PrintStats - Print statistics about how well the identifier table is doing -/// at hashing identifiers. -void IdentifierTable::PrintStats() const { - unsigned NumBuckets = HashTable.getNumBuckets(); - unsigned NumIdentifiers = HashTable.getNumItems(); - unsigned NumEmptyBuckets = NumBuckets-NumIdentifiers; - unsigned AverageIdentifierSize = 0; - unsigned MaxIdentifierLength = 0; - - // TODO: Figure out maximum times an identifier had to probe for -stats. - for (llvm::StringMap<IdentifierInfo, llvm::BumpPtrAllocator>::const_iterator - I = HashTable.begin(), E = HashTable.end(); I != E; ++I) { - unsigned IdLen = I->getKeyLength(); - AverageIdentifierSize += IdLen; - if (MaxIdentifierLength < IdLen) - MaxIdentifierLength = IdLen; - } - - fprintf(stderr, "\n*** Identifier Table Stats:\n"); - fprintf(stderr, "# Identifiers: %d\n", NumIdentifiers); - fprintf(stderr, "# Empty Buckets: %d\n", NumEmptyBuckets); - fprintf(stderr, "Hash density (#identifiers per bucket): %f\n", - NumIdentifiers/(double)NumBuckets); - fprintf(stderr, "Ave identifier length: %f\n", - (AverageIdentifierSize/(double)NumIdentifiers)); - fprintf(stderr, "Max identifier length: %d\n", MaxIdentifierLength); - - // Compute statistics about the memory allocated for identifiers. - HashTable.getAllocator().PrintStats(); -} - -//===----------------------------------------------------------------------===// -// SelectorTable Implementation -//===----------------------------------------------------------------------===// - -unsigned llvm::DenseMapInfo<clang::Selector>::getHashValue(clang::Selector S) { - return DenseMapInfo<void*>::getHashValue(S.getAsOpaquePtr()); -} - - -/// MultiKeywordSelector - One of these variable length records is kept for each -/// selector containing more than one keyword. We use a folding set -/// to unique aggregate names (keyword selectors in ObjC parlance). Access to -/// this class is provided strictly through Selector. -namespace clang { -class MultiKeywordSelector : public llvm::FoldingSetNode { - friend SelectorTable* SelectorTable::CreateAndRegister(llvm::Deserializer&); - MultiKeywordSelector(unsigned nKeys) : NumArgs(nKeys) {} -public: - unsigned NumArgs; - - // Constructor for keyword selectors. - MultiKeywordSelector(unsigned nKeys, IdentifierInfo **IIV) { - assert((nKeys > 1) && "not a multi-keyword selector"); - NumArgs = nKeys; - - // Fill in the trailing keyword array. - IdentifierInfo **KeyInfo = reinterpret_cast<IdentifierInfo **>(this+1); - for (unsigned i = 0; i != nKeys; ++i) - KeyInfo[i] = IIV[i]; - } - - // getName - Derive the full selector name and return it. - std::string getName() const; - - unsigned getNumArgs() const { return NumArgs; } - - typedef IdentifierInfo *const *keyword_iterator; - keyword_iterator keyword_begin() const { - return reinterpret_cast<keyword_iterator>(this+1); - } - keyword_iterator keyword_end() const { - return keyword_begin()+NumArgs; - } - IdentifierInfo *getIdentifierInfoForSlot(unsigned i) const { - assert(i < NumArgs && "getIdentifierInfoForSlot(): illegal index"); - return keyword_begin()[i]; - } - static void Profile(llvm::FoldingSetNodeID &ID, - keyword_iterator ArgTys, unsigned NumArgs) { - ID.AddInteger(NumArgs); - for (unsigned i = 0; i != NumArgs; ++i) - ID.AddPointer(ArgTys[i]); - } - void Profile(llvm::FoldingSetNodeID &ID) { - Profile(ID, keyword_begin(), NumArgs); - } -}; -} // end namespace clang. - -unsigned Selector::getNumArgs() const { - unsigned IIF = getIdentifierInfoFlag(); - if (IIF == ZeroArg) - return 0; - if (IIF == OneArg) - return 1; - // We point to a MultiKeywordSelector (pointer doesn't contain any flags). - MultiKeywordSelector *SI = reinterpret_cast<MultiKeywordSelector *>(InfoPtr); - return SI->getNumArgs(); -} - -IdentifierInfo *Selector::getIdentifierInfoForSlot(unsigned argIndex) const { - if (IdentifierInfo *II = getAsIdentifierInfo()) { - assert(argIndex == 0 && "illegal keyword index"); - return II; - } - // We point to a MultiKeywordSelector (pointer doesn't contain any flags). - MultiKeywordSelector *SI = reinterpret_cast<MultiKeywordSelector *>(InfoPtr); - return SI->getIdentifierInfoForSlot(argIndex); -} - -std::string MultiKeywordSelector::getName() const { - std::string Result; - unsigned Length = 0; - for (keyword_iterator I = keyword_begin(), E = keyword_end(); I != E; ++I) { - if (*I) - Length += (*I)->getLength(); - ++Length; // : - } - - Result.reserve(Length); - - for (keyword_iterator I = keyword_begin(), E = keyword_end(); I != E; ++I) { - if (*I) - Result.insert(Result.end(), (*I)->getName(), - (*I)->getName()+(*I)->getLength()); - Result.push_back(':'); - } - - return Result; -} - -std::string Selector::getName() const { - if (IdentifierInfo *II = getAsIdentifierInfo()) { - if (getNumArgs() == 0) - return II->getName(); - - std::string Res = II->getName(); - Res += ":"; - return Res; - } - - // We have a multiple keyword selector (no embedded flags). - return reinterpret_cast<MultiKeywordSelector *>(InfoPtr)->getName(); -} - - -Selector SelectorTable::getSelector(unsigned nKeys, IdentifierInfo **IIV) { - if (nKeys < 2) - return Selector(IIV[0], nKeys); - - llvm::FoldingSet<MultiKeywordSelector> *SelTab; - - SelTab = static_cast<llvm::FoldingSet<MultiKeywordSelector> *>(Impl); - - // Unique selector, to guarantee there is one per name. - llvm::FoldingSetNodeID ID; - MultiKeywordSelector::Profile(ID, IIV, nKeys); - - void *InsertPos = 0; - if (MultiKeywordSelector *SI = SelTab->FindNodeOrInsertPos(ID, InsertPos)) - return Selector(SI); - - // MultiKeywordSelector objects are not allocated with new because they have a - // variable size array (for parameter types) at the end of them. - MultiKeywordSelector *SI = - (MultiKeywordSelector*)malloc(sizeof(MultiKeywordSelector) + - nKeys*sizeof(IdentifierInfo *)); - new (SI) MultiKeywordSelector(nKeys, IIV); - SelTab->InsertNode(SI, InsertPos); - return Selector(SI); -} - -SelectorTable::SelectorTable() { - Impl = new llvm::FoldingSet<MultiKeywordSelector>; -} - -SelectorTable::~SelectorTable() { - delete static_cast<llvm::FoldingSet<MultiKeywordSelector> *>(Impl); -} - -//===----------------------------------------------------------------------===// -// Serialization for IdentifierInfo and IdentifierTable. -//===----------------------------------------------------------------------===// - -void IdentifierInfo::Emit(llvm::Serializer& S) const { - S.EmitInt(getTokenID()); - S.EmitInt(getBuiltinID()); - S.EmitInt(getObjCKeywordID()); - S.EmitBool(hasMacroDefinition()); - S.EmitBool(isExtensionToken()); - S.EmitBool(isPoisoned()); - S.EmitBool(isCPlusPlusOperatorKeyword()); - // FIXME: FETokenInfo -} - -void IdentifierInfo::Read(llvm::Deserializer& D) { - setTokenID((tok::TokenKind) D.ReadInt()); - setBuiltinID(D.ReadInt()); - setObjCKeywordID((tok::ObjCKeywordKind) D.ReadInt()); - setHasMacroDefinition(D.ReadBool()); - setIsExtensionToken(D.ReadBool()); - setIsPoisoned(D.ReadBool()); - setIsCPlusPlusOperatorKeyword(D.ReadBool()); - // FIXME: FETokenInfo -} - -void IdentifierTable::Emit(llvm::Serializer& S) const { - S.EnterBlock(); - - S.EmitPtr(this); - - for (iterator I=begin(), E=end(); I != E; ++I) { - const char* Key = I->getKeyData(); - const IdentifierInfo* Info = &I->getValue(); - - bool KeyRegistered = S.isRegistered(Key); - bool InfoRegistered = S.isRegistered(Info); - - if (KeyRegistered || InfoRegistered) { - // These acrobatics are so that we don't incur the cost of registering - // a pointer with the backpatcher during deserialization if nobody - // references the object. - S.EmitPtr(InfoRegistered ? Info : NULL); - S.EmitPtr(KeyRegistered ? Key : NULL); - S.EmitCStr(Key); - S.Emit(*Info); - } - } - - S.ExitBlock(); -} - -IdentifierTable* IdentifierTable::CreateAndRegister(llvm::Deserializer& D) { - llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation(); - - std::vector<char> buff; - buff.reserve(200); - - IdentifierTable* t = new IdentifierTable(); - D.RegisterPtr(t); - - while (!D.FinishedBlock(BLoc)) { - llvm::SerializedPtrID InfoPtrID = D.ReadPtrID(); - llvm::SerializedPtrID KeyPtrID = D.ReadPtrID(); - - D.ReadCStr(buff); - - llvm::StringMapEntry<IdentifierInfo>& Entry = - t->HashTable.GetOrCreateValue(&buff[0],&buff[0]+buff.size()); - - D.Read(Entry.getValue()); - - if (InfoPtrID) - D.RegisterRef(InfoPtrID,Entry.getValue()); - - if (KeyPtrID) - D.RegisterPtr(KeyPtrID,Entry.getKeyData()); - } - - return t; -} - -//===----------------------------------------------------------------------===// -// Serialization for Selector and SelectorTable. -//===----------------------------------------------------------------------===// - -void Selector::Emit(llvm::Serializer& S) const { - S.EmitInt(getIdentifierInfoFlag()); - S.EmitPtr(reinterpret_cast<void*>(InfoPtr & ~ArgFlags)); -} - -Selector Selector::ReadVal(llvm::Deserializer& D) { - unsigned flag = D.ReadInt(); - - uintptr_t ptr; - D.ReadUIntPtr(ptr,false); // No backpatching. - - return Selector(ptr | flag); -} - -void SelectorTable::Emit(llvm::Serializer& S) const { - typedef llvm::FoldingSet<MultiKeywordSelector>::iterator iterator; - llvm::FoldingSet<MultiKeywordSelector> *SelTab; - SelTab = static_cast<llvm::FoldingSet<MultiKeywordSelector> *>(Impl); - - S.EnterBlock(); - - S.EmitPtr(this); - - for (iterator I=SelTab->begin(), E=SelTab->end(); I != E; ++I) { - if (!S.isRegistered(&*I)) - continue; - - S.FlushRecord(); // Start a new record. - - S.EmitPtr(&*I); - S.EmitInt(I->getNumArgs()); - - for (MultiKeywordSelector::keyword_iterator KI = I->keyword_begin(), - KE = I->keyword_end(); KI != KE; ++KI) - S.EmitPtr(*KI); - } - - S.ExitBlock(); -} - -SelectorTable* SelectorTable::CreateAndRegister(llvm::Deserializer& D) { - llvm::Deserializer::Location BLoc = D.getCurrentBlockLocation(); - - SelectorTable* t = new SelectorTable(); - D.RegisterPtr(t); - - llvm::FoldingSet<MultiKeywordSelector>& SelTab = - *static_cast<llvm::FoldingSet<MultiKeywordSelector>*>(t->Impl); - - while (!D.FinishedBlock(BLoc)) { - - llvm::SerializedPtrID PtrID = D.ReadPtrID(); - unsigned nKeys = D.ReadInt(); - - MultiKeywordSelector *SI = - (MultiKeywordSelector*)malloc(sizeof(MultiKeywordSelector) + - nKeys*sizeof(IdentifierInfo *)); - - new (SI) MultiKeywordSelector(nKeys); - - D.RegisterPtr(PtrID,SI); - - IdentifierInfo **KeyInfo = reinterpret_cast<IdentifierInfo **>(SI+1); - - for (unsigned i = 0; i != nKeys; ++i) - D.ReadPtr(KeyInfo[i],false); - - SelTab.GetOrInsertNode(SI); - } - - return t; -} |
