| //===--- IndexRecordHasher.cpp - Index record hashing ---------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "IndexRecordHasher.h" |
| #include "FileIndexRecord.h" |
| #include "clang/AST/ASTContext.h" |
| #include "clang/AST/Decl.h" |
| #include "clang/AST/DeclVisitor.h" |
| #include "llvm/Support/Path.h" |
| |
| #define INITIAL_HASH 5381 |
| #define COMBINE_HASH(...) (Hash = hash_combine(Hash, __VA_ARGS__)) |
| |
| using namespace clang; |
| using namespace clang::index; |
| using namespace llvm; |
| |
| static hash_code computeHash(const TemplateArgument &Arg, |
| IndexRecordHasher &Hasher); |
| |
| namespace { |
| class DeclHashVisitor : public ConstDeclVisitor<DeclHashVisitor, hash_code> { |
| IndexRecordHasher &Hasher; |
| |
| public: |
| DeclHashVisitor(IndexRecordHasher &Hasher) : Hasher(Hasher) {} |
| |
| hash_code VisitDecl(const Decl *D) { |
| return VisitDeclContext(D->getDeclContext()); |
| } |
| |
| hash_code VisitNamedDecl(const NamedDecl *D) { |
| hash_code Hash = VisitDecl(D); |
| if (auto *attr = D->getExternalSourceSymbolAttr()) { |
| COMBINE_HASH(hash_value(attr->getDefinedIn())); |
| } |
| return COMBINE_HASH(Hasher.hash(D->getDeclName())); |
| } |
| |
| hash_code VisitTagDecl(const TagDecl *D) { |
| if (D->getDeclName().isEmpty()) { |
| if (const TypedefNameDecl *TD = D->getTypedefNameForAnonDecl()) |
| return Visit(TD); |
| |
| hash_code Hash = VisitDeclContext(D->getDeclContext()); |
| if (D->isEmbeddedInDeclarator() && !D->isFreeStanding()) { |
| COMBINE_HASH(hashLoc(D->getLocation(), /*IncludeOffset=*/true)); |
| } else |
| COMBINE_HASH('a'); |
| return Hash; |
| } |
| |
| hash_code Hash = VisitTypeDecl(D); |
| return COMBINE_HASH('T'); |
| } |
| |
| hash_code VisitClassTemplateSpecializationDecl(const ClassTemplateSpecializationDecl *D) { |
| hash_code Hash = VisitCXXRecordDecl(D); |
| const TemplateArgumentList &Args = D->getTemplateArgs(); |
| COMBINE_HASH('>'); |
| for (unsigned I = 0, N = Args.size(); I != N; ++I) { |
| COMBINE_HASH(computeHash(Args.get(I), Hasher)); |
| } |
| return Hash; |
| } |
| |
| hash_code VisitObjCContainerDecl(const ObjCContainerDecl *D) { |
| hash_code Hash = VisitNamedDecl(D); |
| return COMBINE_HASH('I'); |
| } |
| |
| hash_code VisitObjCImplDecl(const ObjCImplDecl *D) { |
| if (auto *ID = D->getClassInterface()) |
| return VisitObjCInterfaceDecl(ID); |
| else |
| return 0; |
| } |
| |
| hash_code VisitObjCCategoryDecl(const ObjCCategoryDecl *D) { |
| // FIXME: Differentiate between category and the interface ? |
| if (auto *ID = D->getClassInterface()) |
| return VisitObjCInterfaceDecl(ID); |
| else |
| return 0; |
| } |
| |
| hash_code VisitFunctionDecl(const FunctionDecl *D) { |
| hash_code Hash = VisitNamedDecl(D); |
| ASTContext &Ctx = Hasher.getASTContext(); |
| if ((!Ctx.getLangOpts().CPlusPlus && !D->hasAttr<OverloadableAttr>()) |
| || D->isExternC()) |
| return Hash; |
| |
| for (auto param : D->parameters()) { |
| COMBINE_HASH(Hasher.hash(param->getType())); |
| } |
| return Hash; |
| } |
| |
| hash_code VisitUnresolvedUsingTypenameDecl(const UnresolvedUsingTypenameDecl *D) { |
| hash_code Hash = VisitNamedDecl(D); |
| COMBINE_HASH(Hasher.hash(D->getQualifier())); |
| return Hash; |
| } |
| |
| hash_code VisitUnresolvedUsingValueDecl(const UnresolvedUsingValueDecl *D) { |
| hash_code Hash = VisitNamedDecl(D); |
| COMBINE_HASH(Hasher.hash(D->getQualifier())); |
| return Hash; |
| } |
| |
| hash_code VisitDeclContext(const DeclContext *DC) { |
| // FIXME: Add location if this is anonymous namespace ? |
| DC = DC->getRedeclContext(); |
| const Decl *D = cast<Decl>(DC)->getCanonicalDecl(); |
| if (auto *ND = dyn_cast<NamedDecl>(D)) |
| return Hasher.hash(ND); |
| else |
| return 0; |
| } |
| |
| hash_code hashLoc(SourceLocation Loc, bool IncludeOffset) { |
| if (Loc.isInvalid()) { |
| return 0; |
| } |
| hash_code Hash = INITIAL_HASH; |
| const SourceManager &SM = Hasher.getASTContext().getSourceManager(); |
| Loc = SM.getFileLoc(Loc); |
| const std::pair<FileID, unsigned> &Decomposed = SM.getDecomposedLoc(Loc); |
| const FileEntry *FE = SM.getFileEntryForID(Decomposed.first); |
| if (FE) { |
| COMBINE_HASH(llvm::sys::path::filename(FE->getName())); |
| } else { |
| // This case really isn't interesting. |
| return 0; |
| } |
| if (IncludeOffset) { |
| // Use the offest into the FileID to represent the location. Using |
| // a line/column can cause us to look back at the original source file, |
| // which is expensive. |
| COMBINE_HASH(Decomposed.second); |
| } |
| return Hash; |
| } |
| }; |
| } |
| |
| hash_code IndexRecordHasher::hashRecord(const FileIndexRecord &Record) { |
| hash_code Hash = INITIAL_HASH; |
| for (auto &Info : Record.getDeclOccurrences()) { |
| COMBINE_HASH(Info.Roles, Info.Offset, hash(Info.Dcl)); |
| for (auto &Rel : Info.Relations) { |
| COMBINE_HASH(hash(Rel.RelatedSymbol)); |
| } |
| } |
| return Hash; |
| } |
| |
| hash_code IndexRecordHasher::hash(const Decl *D) { |
| assert(D->isCanonicalDecl()); |
| |
| if (isa<TagDecl>(D) || isa<ObjCContainerDecl>(D)) { |
| return tryCache(D, D); |
| } else if (auto *NS = dyn_cast<NamespaceDecl>(D)) { |
| if (NS->isAnonymousNamespace()) |
| return hash_value(StringRef("@aN")); |
| return tryCache(D, D); |
| } else { |
| // There's a balance between caching results and not growing the cache too |
| // much. Measurements showed that avoiding caching all decls is beneficial |
| // particularly when including all of Cocoa. |
| return hashImpl(D); |
| } |
| } |
| |
| hash_code IndexRecordHasher::hash(QualType NonCanTy) { |
| CanQualType CanTy = Ctx.getCanonicalType(NonCanTy); |
| return hash(CanTy); |
| } |
| |
| hash_code IndexRecordHasher::hash(CanQualType CT) { |
| // Do some hashing without going to the cache, for example we can avoid |
| // storing the hash for both the type and its const-qualified version. |
| hash_code Hash = INITIAL_HASH; |
| |
| auto asCanon = [](QualType Ty) -> CanQualType { |
| return CanQualType::CreateUnsafe(Ty); |
| }; |
| |
| while (true) { |
| Qualifiers Q = CT.getQualifiers(); |
| CT = CT.getUnqualifiedType(); |
| const Type *T = CT.getTypePtr(); |
| unsigned qVal = 0; |
| if (Q.hasConst()) |
| qVal |= 0x1; |
| if (Q.hasVolatile()) |
| qVal |= 0x2; |
| if (Q.hasRestrict()) |
| qVal |= 0x4; |
| if(qVal) |
| COMBINE_HASH(qVal); |
| |
| // Hash in ObjC GC qualifiers? |
| |
| if (const BuiltinType *BT = dyn_cast<BuiltinType>(T)) { |
| return COMBINE_HASH(BT->getKind()); |
| } |
| if (const PointerType *PT = dyn_cast<PointerType>(T)) { |
| COMBINE_HASH('*'); |
| CT = asCanon(PT->getPointeeType()); |
| continue; |
| } |
| if (const ReferenceType *RT = dyn_cast<ReferenceType>(T)) { |
| COMBINE_HASH('&'); |
| CT = asCanon(RT->getPointeeType()); |
| continue; |
| } |
| if (const BlockPointerType *BT = dyn_cast<BlockPointerType>(T)) { |
| COMBINE_HASH('B'); |
| CT = asCanon(BT->getPointeeType()); |
| continue; |
| } |
| if (const ObjCObjectPointerType *OPT = dyn_cast<ObjCObjectPointerType>(T)) { |
| COMBINE_HASH('*'); |
| CT = asCanon(OPT->getPointeeType()); |
| continue; |
| } |
| if (const TagType *TT = dyn_cast<TagType>(T)) { |
| return COMBINE_HASH('$', hash(TT->getDecl()->getCanonicalDecl())); |
| } |
| if (const ObjCInterfaceType *OIT = dyn_cast<ObjCInterfaceType>(T)) { |
| return COMBINE_HASH('$', hash(OIT->getDecl()->getCanonicalDecl())); |
| } |
| if (const ObjCObjectType *OIT = dyn_cast<ObjCObjectType>(T)) { |
| for (auto *Prot : OIT->getProtocols()) |
| COMBINE_HASH(hash(Prot)); |
| CT = asCanon(OIT->getBaseType()); |
| continue; |
| } |
| if (const TemplateTypeParmType *TTP = dyn_cast<TemplateTypeParmType>(T)) { |
| return COMBINE_HASH('t', TTP->getDepth(), TTP->getIndex()); |
| } |
| if (const InjectedClassNameType *InjT = dyn_cast<InjectedClassNameType>(T)) { |
| CT = asCanon(InjT->getInjectedSpecializationType().getCanonicalType()); |
| continue; |
| } |
| |
| break; |
| } |
| |
| return COMBINE_HASH(tryCache(CT.getAsOpaquePtr(), CT)); |
| } |
| |
| hash_code IndexRecordHasher::hash(DeclarationName Name) { |
| assert(!Name.isEmpty()); |
| // Measurements for using cache or not here, showed significant slowdown when |
| // using the cache for all DeclarationNames when parsing Cocoa, and minor |
| // improvement or no difference for a couple of C++ single translation unit |
| // files. So we avoid caching DeclarationNames. |
| return hashImpl(Name); |
| } |
| |
| hash_code IndexRecordHasher::hash(const NestedNameSpecifier *NNS) { |
| assert(NNS); |
| // Measurements for the C++ single translation unit files did not show much |
| // difference here; choosing to cache them currently. |
| return tryCache(NNS, NNS); |
| } |
| |
| template <typename T> |
| hash_code IndexRecordHasher::tryCache(const void *Ptr, T Obj) { |
| auto It = HashByPtr.find(Ptr); |
| if (It != HashByPtr.end()) |
| return It->second; |
| |
| hash_code Hash = hashImpl(Obj); |
| // hashImpl() may call into tryCache recursively and mutate |
| // HashByPtr, so we use find() earlier and insert the hash with another |
| // lookup here instead of calling insert() earlier and utilizing the iterator |
| // that insert() returns. |
| HashByPtr[Ptr] = Hash; |
| return Hash; |
| } |
| |
| hash_code IndexRecordHasher::hashImpl(const Decl *D) { |
| return DeclHashVisitor(*this).Visit(D); |
| } |
| |
| static hash_code computeHash(const IdentifierInfo *II) { |
| return hash_value(II->getName()); |
| } |
| |
| static hash_code computeHash(Selector Sel) { |
| unsigned N = Sel.getNumArgs(); |
| if (N == 0) |
| ++N; |
| hash_code Hash = INITIAL_HASH; |
| for (unsigned I = 0; I != N; ++I) |
| if (IdentifierInfo *II = Sel.getIdentifierInfoForSlot(I)) |
| COMBINE_HASH(computeHash(II)); |
| return Hash; |
| } |
| |
| static hash_code computeHash(TemplateName Name, IndexRecordHasher &Hasher) { |
| hash_code Hash = INITIAL_HASH; |
| if (TemplateDecl *Template = Name.getAsTemplateDecl()) { |
| if (TemplateTemplateParmDecl *TTP |
| = dyn_cast<TemplateTemplateParmDecl>(Template)) { |
| return COMBINE_HASH('t', TTP->getDepth(), TTP->getIndex()); |
| } |
| |
| return COMBINE_HASH(Hasher.hash(Template->getCanonicalDecl())); |
| } |
| |
| // FIXME: Hash dependent template names. |
| return Hash; |
| } |
| |
| static hash_code computeHash(const TemplateArgument &Arg, |
| IndexRecordHasher &Hasher) { |
| hash_code Hash = INITIAL_HASH; |
| |
| switch (Arg.getKind()) { |
| case TemplateArgument::Null: |
| break; |
| |
| case TemplateArgument::Declaration: |
| COMBINE_HASH(Hasher.hash(Arg.getAsDecl())); |
| break; |
| |
| case TemplateArgument::NullPtr: |
| break; |
| |
| case TemplateArgument::TemplateExpansion: |
| COMBINE_HASH('P'); // pack expansion of... |
| // Fall through |
| case TemplateArgument::Template: |
| COMBINE_HASH(computeHash(Arg.getAsTemplateOrTemplatePattern(), Hasher)); |
| break; |
| |
| case TemplateArgument::Expression: |
| // FIXME: Hash expressions. |
| break; |
| |
| case TemplateArgument::Pack: |
| COMBINE_HASH('p'); |
| for (const auto &P : Arg.pack_elements()) |
| COMBINE_HASH(computeHash(P, Hasher)); |
| break; |
| |
| case TemplateArgument::Type: |
| COMBINE_HASH(Hasher.hash(Arg.getAsType())); |
| break; |
| |
| case TemplateArgument::Integral: |
| COMBINE_HASH('V', Hasher.hash(Arg.getIntegralType()), Arg.getAsIntegral()); |
| break; |
| } |
| |
| return Hash; |
| } |
| |
| hash_code IndexRecordHasher::hashImpl(CanQualType CQT) { |
| hash_code Hash = INITIAL_HASH; |
| |
| auto asCanon = [](QualType Ty) -> CanQualType { |
| return CanQualType::CreateUnsafe(Ty); |
| }; |
| |
| const Type *T = CQT.getTypePtr(); |
| |
| if (const PackExpansionType *Expansion = dyn_cast<PackExpansionType>(T)) { |
| return COMBINE_HASH('P', hash(asCanon(Expansion->getPattern()))); |
| } |
| if (const RValueReferenceType *RT = dyn_cast<RValueReferenceType>(T)) { |
| return COMBINE_HASH('%', hash(asCanon(RT->getPointeeType()))); |
| } |
| if (const FunctionProtoType *FT = dyn_cast<FunctionProtoType>(T)) { |
| COMBINE_HASH('F', hash(asCanon(FT->getReturnType()))); |
| for (const auto &I : FT->param_types()) |
| COMBINE_HASH(hash(asCanon(I))); |
| return COMBINE_HASH(FT->isVariadic()); |
| } |
| if (const ComplexType *CT = dyn_cast<ComplexType>(T)) { |
| return COMBINE_HASH('<', hash(asCanon(CT->getElementType()))); |
| } |
| if (const TemplateSpecializationType *Spec |
| = dyn_cast<TemplateSpecializationType>(T)) { |
| COMBINE_HASH('>', computeHash(Spec->getTemplateName(), *this)); |
| for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I) |
| COMBINE_HASH(computeHash(Spec->getArg(I), *this)); |
| return Hash; |
| } |
| if (const DependentNameType *DNT = dyn_cast<DependentNameType>(T)) { |
| COMBINE_HASH('^'); |
| if (const NestedNameSpecifier *NNS = DNT->getQualifier()) |
| COMBINE_HASH(hash(NNS)); |
| return COMBINE_HASH(computeHash(DNT->getIdentifier())); |
| } |
| |
| // Unhandled type. |
| return Hash; |
| } |
| |
| hash_code IndexRecordHasher::hashImpl(DeclarationName Name) { |
| hash_code Hash = INITIAL_HASH; |
| COMBINE_HASH(Name.getNameKind()); |
| |
| switch (Name.getNameKind()) { |
| case DeclarationName::Identifier: |
| COMBINE_HASH(computeHash(Name.getAsIdentifierInfo())); |
| break; |
| case DeclarationName::ObjCZeroArgSelector: |
| case DeclarationName::ObjCOneArgSelector: |
| case DeclarationName::ObjCMultiArgSelector: |
| COMBINE_HASH(computeHash(Name.getObjCSelector())); |
| break; |
| case DeclarationName::CXXConstructorName: |
| case DeclarationName::CXXDestructorName: |
| case DeclarationName::CXXConversionFunctionName: |
| break; |
| case DeclarationName::CXXOperatorName: |
| COMBINE_HASH(Name.getCXXOverloadedOperator()); |
| break; |
| case DeclarationName::CXXLiteralOperatorName: |
| COMBINE_HASH(computeHash(Name.getCXXLiteralIdentifier())); |
| case DeclarationName::CXXUsingDirective: |
| break; |
| case DeclarationName::CXXDeductionGuideName: |
| COMBINE_HASH(computeHash(Name.getCXXDeductionGuideTemplate() |
| ->getDeclName().getAsIdentifierInfo())); |
| break; |
| } |
| |
| return Hash; |
| } |
| |
| hash_code IndexRecordHasher::hashImpl(const NestedNameSpecifier *NNS) { |
| hash_code Hash = INITIAL_HASH; |
| if (auto *Pre = NNS->getPrefix()) |
| COMBINE_HASH(hash(Pre)); |
| |
| COMBINE_HASH(NNS->getKind()); |
| |
| switch (NNS->getKind()) { |
| case NestedNameSpecifier::Identifier: |
| COMBINE_HASH(computeHash(NNS->getAsIdentifier())); |
| break; |
| |
| case NestedNameSpecifier::Namespace: |
| COMBINE_HASH(hash(NNS->getAsNamespace()->getCanonicalDecl())); |
| break; |
| |
| case NestedNameSpecifier::NamespaceAlias: |
| COMBINE_HASH(hash(NNS->getAsNamespaceAlias()->getCanonicalDecl())); |
| break; |
| |
| case NestedNameSpecifier::Global: |
| break; |
| |
| case NestedNameSpecifier::Super: |
| break; |
| |
| case NestedNameSpecifier::TypeSpecWithTemplate: |
| // Fall through to hash the type. |
| |
| case NestedNameSpecifier::TypeSpec: |
| COMBINE_HASH(hash(QualType(NNS->getAsType(), 0))); |
| break; |
| } |
| |
| return Hash; |
| } |