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-exception 6 // 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 20 using namespace clang; 21 22 namespace { 23 24 class TemplateArgumentHasher { 25 // If we bail out during the process of calculating hash values for 26 // template arguments for any reason. We're allowed to do it since 27 // TemplateArgumentHasher are only required to give the same hash value 28 // for the same template arguments, but not required to give different 29 // hash value for different template arguments. 30 // 31 // So in the worst case, it is still a valid implementation to give all 32 // inputs the same BailedOutValue as output. 33 bool BailedOut = false; 34 static constexpr unsigned BailedOutValue = 0x12345678; 35 36 llvm::FoldingSetNodeID ID; 37 38 public: 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 63 void 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 code 70 // 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 as 83 // 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 implies 97 // that the template is still dependent. It is meaningless 98 // 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 110 void 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 and 115 // 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 126 void 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 else 148 BailedOut = true; 149 break; 150 } 151 case TemplateName::DeducedTemplate: 152 AddTemplateName(Name.getAsDeducedTemplateName()->getUnderlying()); 153 break; 154 } 155 } 156 157 void TemplateArgumentHasher::AddIdentifierInfo(const IdentifierInfo *II) { 158 assert(II && "Expecting non-null pointer."); 159 ID.AddString(II->getName()); 160 } 161 162 void 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 197 void 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 207 void 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 TemplateArgumentHasher 218 // while Visit* methods process the relevant parts of the Type. 219 // Any unhandled type will make the hash computation bail out. 220 class TypeVisitorHelper : public TypeVisitor<TypeVisitorHelper> { 221 typedef TypeVisitor<TypeVisitorHelper> Inherited; 222 llvm::FoldingSetNodeID &ID; 223 TemplateArgumentHasher &Hash; 224 225 public: 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 else 233 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 else 242 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 getAdjustedType 260 // 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 void 351 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 VisitElaboratedType(const ElaboratedType *T) { 383 AddQualType(T->getNamedType()); 384 } 385 386 void VisitUnaryTransformType(const UnaryTransformType *T) { 387 AddQualType(T->getUnderlyingType()); 388 AddQualType(T->getBaseType()); 389 } 390 391 void VisitVectorType(const VectorType *T) { 392 AddQualType(T->getElementType()); 393 Hash.AddInteger(T->getNumElements()); 394 Hash.AddInteger(llvm::to_underlying(T->getVectorKind())); 395 } 396 397 void VisitExtVectorType(const ExtVectorType *T) { VisitVectorType(T); } 398 }; 399 400 void TemplateArgumentHasher::AddType(const Type *T) { 401 assert(T && "Expecting non-null pointer."); 402 TypeVisitorHelper(ID, *this).Visit(T); 403 } 404 405 } // namespace 406 407 unsigned clang::serialization::StableHashForTemplateArguments( 408 llvm::ArrayRef<TemplateArgument> Args) { 409 llvm::TimeTraceScope TimeScope("Stable Hash for Template Arguments"); 410 TemplateArgumentHasher Hasher; 411 Hasher.AddInteger(Args.size()); 412 for (TemplateArgument Arg : Args) 413 Hasher.AddTemplateArgument(Arg); 414 return Hasher.getValue(); 415 } 416