412 lines · cpp
1//===- TemplateArgumentHasher.cpp - Hash Template Arguments -----*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "TemplateArgumentHasher.h"10#include "clang/AST/APValue.h"11#include "clang/AST/Decl.h"12#include "clang/AST/DeclCXX.h"13#include "clang/AST/DeclTemplate.h"14#include "clang/AST/DeclarationName.h"15#include "clang/AST/TypeVisitor.h"16#include "clang/Basic/IdentifierTable.h"17#include "llvm/ADT/FoldingSet.h"18#include "llvm/Support/TimeProfiler.h"19 20using namespace clang;21 22namespace {23 24class TemplateArgumentHasher {25 // If we bail out during the process of calculating hash values for26 // template arguments for any reason. We're allowed to do it since27 // TemplateArgumentHasher are only required to give the same hash value28 // for the same template arguments, but not required to give different29 // hash value for different template arguments.30 //31 // So in the worst case, it is still a valid implementation to give all32 // inputs the same BailedOutValue as output.33 bool BailedOut = false;34 static constexpr unsigned BailedOutValue = 0x12345678;35 36 llvm::FoldingSetNodeID ID;37 38public:39 TemplateArgumentHasher() = default;40 41 void AddTemplateArgument(TemplateArgument TA);42 43 void AddInteger(unsigned V) { ID.AddInteger(V); }44 45 unsigned getValue() {46 if (BailedOut)47 return BailedOutValue;48 49 return ID.computeStableHash();50 }51 52 void setBailedOut() { BailedOut = true; }53 54 void AddType(const Type *T);55 void AddQualType(QualType T);56 void AddDecl(const Decl *D);57 void AddStructuralValue(const APValue &);58 void AddTemplateName(TemplateName Name);59 void AddDeclarationName(DeclarationName Name);60 void AddIdentifierInfo(const IdentifierInfo *II);61};62 63void TemplateArgumentHasher::AddTemplateArgument(TemplateArgument TA) {64 const auto Kind = TA.getKind();65 AddInteger(Kind);66 67 switch (Kind) {68 case TemplateArgument::Null:69 // These can occur in incomplete substitutions performed with code70 // completion (see PartialOverloading).71 break;72 case TemplateArgument::Type:73 AddQualType(TA.getAsType());74 break;75 case TemplateArgument::Declaration:76 AddDecl(TA.getAsDecl());77 break;78 case TemplateArgument::NullPtr:79 ID.AddPointer(nullptr);80 break;81 case TemplateArgument::Integral: {82 // There are integrals (e.g.: _BitInt(128)) that cannot be represented as83 // any builtin integral type, so we use the hash of APSInt instead.84 TA.getAsIntegral().Profile(ID);85 break;86 }87 case TemplateArgument::StructuralValue:88 AddQualType(TA.getStructuralValueType());89 AddStructuralValue(TA.getAsStructuralValue());90 break;91 case TemplateArgument::Template:92 case TemplateArgument::TemplateExpansion:93 AddTemplateName(TA.getAsTemplateOrTemplatePattern());94 break;95 case TemplateArgument::Expression:96 // If we meet expression in template argument, it implies97 // that the template is still dependent. It is meaningless98 // to get a stable hash for the template. Bail out simply.99 BailedOut = true;100 break;101 case TemplateArgument::Pack:102 AddInteger(TA.pack_size());103 for (auto SubTA : TA.pack_elements()) {104 AddTemplateArgument(SubTA);105 }106 break;107 }108}109 110void TemplateArgumentHasher::AddStructuralValue(const APValue &Value) {111 auto Kind = Value.getKind();112 AddInteger(Kind);113 114 // 'APValue::Profile' uses pointer values to make hash for LValue and115 // MemberPointer, but they differ from one compiler invocation to another.116 // It may be difficult to handle such cases. Bail out simply.117 118 if (Kind == APValue::LValue || Kind == APValue::MemberPointer) {119 BailedOut = true;120 return;121 }122 123 Value.Profile(ID);124}125 126void TemplateArgumentHasher::AddTemplateName(TemplateName Name) {127 switch (Name.getKind()) {128 case TemplateName::Template:129 AddDecl(Name.getAsTemplateDecl());130 break;131 case TemplateName::QualifiedTemplate: {132 QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName();133 AddTemplateName(QTN->getUnderlyingTemplate());134 break;135 }136 case TemplateName::OverloadedTemplate:137 case TemplateName::AssumedTemplate:138 case TemplateName::DependentTemplate:139 case TemplateName::SubstTemplateTemplateParm:140 case TemplateName::SubstTemplateTemplateParmPack:141 BailedOut = true;142 break;143 case TemplateName::UsingTemplate: {144 UsingShadowDecl *USD = Name.getAsUsingShadowDecl();145 if (USD)146 AddDecl(USD->getTargetDecl());147 else148 BailedOut = true;149 break;150 }151 case TemplateName::DeducedTemplate:152 AddTemplateName(Name.getAsDeducedTemplateName()->getUnderlying());153 break;154 }155}156 157void TemplateArgumentHasher::AddIdentifierInfo(const IdentifierInfo *II) {158 assert(II && "Expecting non-null pointer.");159 ID.AddString(II->getName());160}161 162void TemplateArgumentHasher::AddDeclarationName(DeclarationName Name) {163 if (Name.isEmpty())164 return;165 166 switch (Name.getNameKind()) {167 case DeclarationName::Identifier:168 AddIdentifierInfo(Name.getAsIdentifierInfo());169 break;170 case DeclarationName::ObjCZeroArgSelector:171 case DeclarationName::ObjCOneArgSelector:172 case DeclarationName::ObjCMultiArgSelector:173 BailedOut = true;174 break;175 case DeclarationName::CXXConstructorName:176 case DeclarationName::CXXDestructorName:177 AddQualType(Name.getCXXNameType());178 break;179 case DeclarationName::CXXOperatorName:180 AddInteger(Name.getCXXOverloadedOperator());181 break;182 case DeclarationName::CXXLiteralOperatorName:183 AddIdentifierInfo(Name.getCXXLiteralIdentifier());184 break;185 case DeclarationName::CXXConversionFunctionName:186 AddQualType(Name.getCXXNameType());187 break;188 case DeclarationName::CXXUsingDirective:189 break;190 case DeclarationName::CXXDeductionGuideName: {191 if (auto *Template = Name.getCXXDeductionGuideTemplate())192 AddDecl(Template);193 }194 }195}196 197void TemplateArgumentHasher::AddDecl(const Decl *D) {198 const NamedDecl *ND = dyn_cast<NamedDecl>(D);199 if (!ND) {200 BailedOut = true;201 return;202 }203 204 AddDeclarationName(ND->getDeclName());205}206 207void TemplateArgumentHasher::AddQualType(QualType T) {208 if (T.isNull()) {209 BailedOut = true;210 return;211 }212 SplitQualType split = T.split();213 AddInteger(split.Quals.getAsOpaqueValue());214 AddType(split.Ty);215}216 217// Process a Type pointer. Add* methods call back into TemplateArgumentHasher218// while Visit* methods process the relevant parts of the Type.219// Any unhandled type will make the hash computation bail out.220class TypeVisitorHelper : public TypeVisitor<TypeVisitorHelper> {221 typedef TypeVisitor<TypeVisitorHelper> Inherited;222 llvm::FoldingSetNodeID &ID;223 TemplateArgumentHasher &Hash;224 225public:226 TypeVisitorHelper(llvm::FoldingSetNodeID &ID, TemplateArgumentHasher &Hash)227 : ID(ID), Hash(Hash) {}228 229 void AddDecl(const Decl *D) {230 if (D)231 Hash.AddDecl(D);232 else233 Hash.AddInteger(0);234 }235 236 void AddQualType(QualType T) { Hash.AddQualType(T); }237 238 void AddType(const Type *T) {239 if (T)240 Hash.AddType(T);241 else242 Hash.AddInteger(0);243 }244 245 void VisitQualifiers(Qualifiers Quals) {246 Hash.AddInteger(Quals.getAsOpaqueValue());247 }248 249 void Visit(const Type *T) { Inherited::Visit(T); }250 251 // Unhandled types. Bail out simply.252 void VisitType(const Type *T) { Hash.setBailedOut(); }253 254 void VisitAdjustedType(const AdjustedType *T) {255 AddQualType(T->getOriginalType());256 }257 258 void VisitDecayedType(const DecayedType *T) {259 // getDecayedType and getPointeeType are derived from getAdjustedType260 // and don't need to be separately processed.261 VisitAdjustedType(T);262 }263 264 void VisitArrayType(const ArrayType *T) {265 AddQualType(T->getElementType());266 Hash.AddInteger(llvm::to_underlying(T->getSizeModifier()));267 VisitQualifiers(T->getIndexTypeQualifiers());268 }269 void VisitConstantArrayType(const ConstantArrayType *T) {270 T->getSize().Profile(ID);271 VisitArrayType(T);272 }273 274 void VisitAttributedType(const AttributedType *T) {275 Hash.AddInteger(T->getAttrKind());276 AddQualType(T->getModifiedType());277 }278 279 void VisitBuiltinType(const BuiltinType *T) { Hash.AddInteger(T->getKind()); }280 281 void VisitComplexType(const ComplexType *T) {282 AddQualType(T->getElementType());283 }284 285 void VisitDecltypeType(const DecltypeType *T) {286 AddQualType(T->getUnderlyingType());287 }288 289 void VisitDeducedType(const DeducedType *T) {290 AddQualType(T->getDeducedType());291 }292 293 void VisitAutoType(const AutoType *T) { VisitDeducedType(T); }294 295 void VisitDeducedTemplateSpecializationType(296 const DeducedTemplateSpecializationType *T) {297 Hash.AddTemplateName(T->getTemplateName());298 VisitDeducedType(T);299 }300 301 void VisitFunctionType(const FunctionType *T) {302 AddQualType(T->getReturnType());303 T->getExtInfo().Profile(ID);304 Hash.AddInteger(T->isConst());305 Hash.AddInteger(T->isVolatile());306 Hash.AddInteger(T->isRestrict());307 }308 309 void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {310 VisitFunctionType(T);311 }312 313 void VisitFunctionProtoType(const FunctionProtoType *T) {314 Hash.AddInteger(T->getNumParams());315 for (auto ParamType : T->getParamTypes())316 AddQualType(ParamType);317 318 VisitFunctionType(T);319 }320 321 void VisitMemberPointerType(const MemberPointerType *T) {322 AddQualType(T->getPointeeType());323 AddType(T->getQualifier().getAsType());324 if (auto *RD = T->getMostRecentCXXRecordDecl())325 AddDecl(RD->getCanonicalDecl());326 }327 328 void VisitPackExpansionType(const PackExpansionType *T) {329 AddQualType(T->getPattern());330 }331 332 void VisitParenType(const ParenType *T) { AddQualType(T->getInnerType()); }333 334 void VisitPointerType(const PointerType *T) {335 AddQualType(T->getPointeeType());336 }337 338 void VisitReferenceType(const ReferenceType *T) {339 AddQualType(T->getPointeeTypeAsWritten());340 }341 342 void VisitLValueReferenceType(const LValueReferenceType *T) {343 VisitReferenceType(T);344 }345 346 void VisitRValueReferenceType(const RValueReferenceType *T) {347 VisitReferenceType(T);348 }349 350 void351 VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {352 AddDecl(T->getAssociatedDecl());353 Hash.AddTemplateArgument(T->getArgumentPack());354 }355 356 void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {357 AddDecl(T->getAssociatedDecl());358 AddQualType(T->getReplacementType());359 }360 361 void VisitTagType(const TagType *T) { AddDecl(T->getDecl()); }362 363 void VisitRecordType(const RecordType *T) { VisitTagType(T); }364 void VisitEnumType(const EnumType *T) { VisitTagType(T); }365 366 void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {367 Hash.AddInteger(T->template_arguments().size());368 for (const auto &TA : T->template_arguments()) {369 Hash.AddTemplateArgument(TA);370 }371 Hash.AddTemplateName(T->getTemplateName());372 }373 374 void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {375 Hash.AddInteger(T->getDepth());376 Hash.AddInteger(T->getIndex());377 Hash.AddInteger(T->isParameterPack());378 }379 380 void VisitTypedefType(const TypedefType *T) { AddDecl(T->getDecl()); }381 382 void VisitUnaryTransformType(const UnaryTransformType *T) {383 AddQualType(T->getUnderlyingType());384 AddQualType(T->getBaseType());385 }386 387 void VisitVectorType(const VectorType *T) {388 AddQualType(T->getElementType());389 Hash.AddInteger(T->getNumElements());390 Hash.AddInteger(llvm::to_underlying(T->getVectorKind()));391 }392 393 void VisitExtVectorType(const ExtVectorType *T) { VisitVectorType(T); }394};395 396void TemplateArgumentHasher::AddType(const Type *T) {397 assert(T && "Expecting non-null pointer.");398 TypeVisitorHelper(ID, *this).Visit(T);399}400 401} // namespace402 403unsigned clang::serialization::StableHashForTemplateArguments(404 llvm::ArrayRef<TemplateArgument> Args) {405 llvm::TimeTraceScope TimeScope("Stable Hash for Template Arguments");406 TemplateArgumentHasher Hasher;407 Hasher.AddInteger(Args.size());408 for (TemplateArgument Arg : Args)409 Hasher.AddTemplateArgument(Arg);410 return Hasher.getValue();411}412