lib/Index/IndexRecordHasher.cpp - third_party/swift-clang - Git at Google

 //===--- 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;
 }
	//===--- 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;
	}