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
AddInteger(unsigned V)43 void AddInteger(unsigned V) { ID.AddInteger(V); }
44
getValue()45 unsigned getValue() {
46 if (BailedOut)
47 return BailedOutValue;
48
49 return ID.computeStableHash();
50 }
51
setBailedOut()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
AddTemplateArgument(TemplateArgument TA)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
AddStructuralValue(const APValue & Value)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
AddTemplateName(TemplateName Name)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
AddIdentifierInfo(const IdentifierInfo * II)157 void TemplateArgumentHasher::AddIdentifierInfo(const IdentifierInfo *II) {
158 assert(II && "Expecting non-null pointer.");
159 ID.AddString(II->getName());
160 }
161
AddDeclarationName(DeclarationName Name)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
AddDecl(const Decl * D)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
AddQualType(QualType T)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:
TypeVisitorHelper(llvm::FoldingSetNodeID & ID,TemplateArgumentHasher & Hash)226 TypeVisitorHelper(llvm::FoldingSetNodeID &ID, TemplateArgumentHasher &Hash)
227 : ID(ID), Hash(Hash) {}
228
AddDecl(const Decl * D)229 void AddDecl(const Decl *D) {
230 if (D)
231 Hash.AddDecl(D);
232 else
233 Hash.AddInteger(0);
234 }
235
AddQualType(QualType T)236 void AddQualType(QualType T) { Hash.AddQualType(T); }
237
AddType(const Type * T)238 void AddType(const Type *T) {
239 if (T)
240 Hash.AddType(T);
241 else
242 Hash.AddInteger(0);
243 }
244
VisitQualifiers(Qualifiers Quals)245 void VisitQualifiers(Qualifiers Quals) {
246 Hash.AddInteger(Quals.getAsOpaqueValue());
247 }
248
Visit(const Type * T)249 void Visit(const Type *T) { Inherited::Visit(T); }
250
251 // Unhandled types. Bail out simply.
VisitType(const Type * T)252 void VisitType(const Type *T) { Hash.setBailedOut(); }
253
VisitAdjustedType(const AdjustedType * T)254 void VisitAdjustedType(const AdjustedType *T) {
255 AddQualType(T->getOriginalType());
256 }
257
VisitDecayedType(const DecayedType * T)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
VisitArrayType(const ArrayType * T)264 void VisitArrayType(const ArrayType *T) {
265 AddQualType(T->getElementType());
266 Hash.AddInteger(llvm::to_underlying(T->getSizeModifier()));
267 VisitQualifiers(T->getIndexTypeQualifiers());
268 }
VisitConstantArrayType(const ConstantArrayType * T)269 void VisitConstantArrayType(const ConstantArrayType *T) {
270 T->getSize().Profile(ID);
271 VisitArrayType(T);
272 }
273
VisitAttributedType(const AttributedType * T)274 void VisitAttributedType(const AttributedType *T) {
275 Hash.AddInteger(T->getAttrKind());
276 AddQualType(T->getModifiedType());
277 }
278
VisitBuiltinType(const BuiltinType * T)279 void VisitBuiltinType(const BuiltinType *T) { Hash.AddInteger(T->getKind()); }
280
VisitComplexType(const ComplexType * T)281 void VisitComplexType(const ComplexType *T) {
282 AddQualType(T->getElementType());
283 }
284
VisitDecltypeType(const DecltypeType * T)285 void VisitDecltypeType(const DecltypeType *T) {
286 AddQualType(T->getUnderlyingType());
287 }
288
VisitDeducedType(const DeducedType * T)289 void VisitDeducedType(const DeducedType *T) {
290 AddQualType(T->getDeducedType());
291 }
292
VisitAutoType(const AutoType * T)293 void VisitAutoType(const AutoType *T) { VisitDeducedType(T); }
294
VisitDeducedTemplateSpecializationType(const DeducedTemplateSpecializationType * T)295 void VisitDeducedTemplateSpecializationType(
296 const DeducedTemplateSpecializationType *T) {
297 Hash.AddTemplateName(T->getTemplateName());
298 VisitDeducedType(T);
299 }
300
VisitFunctionType(const FunctionType * T)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
VisitFunctionNoProtoType(const FunctionNoProtoType * T)309 void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
310 VisitFunctionType(T);
311 }
312
VisitFunctionProtoType(const FunctionProtoType * T)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
VisitMemberPointerType(const MemberPointerType * T)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
VisitPackExpansionType(const PackExpansionType * T)328 void VisitPackExpansionType(const PackExpansionType *T) {
329 AddQualType(T->getPattern());
330 }
331
VisitParenType(const ParenType * T)332 void VisitParenType(const ParenType *T) { AddQualType(T->getInnerType()); }
333
VisitPointerType(const PointerType * T)334 void VisitPointerType(const PointerType *T) {
335 AddQualType(T->getPointeeType());
336 }
337
VisitReferenceType(const ReferenceType * T)338 void VisitReferenceType(const ReferenceType *T) {
339 AddQualType(T->getPointeeTypeAsWritten());
340 }
341
VisitLValueReferenceType(const LValueReferenceType * T)342 void VisitLValueReferenceType(const LValueReferenceType *T) {
343 VisitReferenceType(T);
344 }
345
VisitRValueReferenceType(const RValueReferenceType * T)346 void VisitRValueReferenceType(const RValueReferenceType *T) {
347 VisitReferenceType(T);
348 }
349
350 void
VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType * T)351 VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {
352 AddDecl(T->getAssociatedDecl());
353 Hash.AddTemplateArgument(T->getArgumentPack());
354 }
355
VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType * T)356 void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
357 AddDecl(T->getAssociatedDecl());
358 AddQualType(T->getReplacementType());
359 }
360
VisitTagType(const TagType * T)361 void VisitTagType(const TagType *T) { AddDecl(T->getDecl()); }
362
VisitRecordType(const RecordType * T)363 void VisitRecordType(const RecordType *T) { VisitTagType(T); }
VisitEnumType(const EnumType * T)364 void VisitEnumType(const EnumType *T) { VisitTagType(T); }
365
VisitTemplateSpecializationType(const TemplateSpecializationType * T)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
VisitTemplateTypeParmType(const TemplateTypeParmType * T)374 void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
375 Hash.AddInteger(T->getDepth());
376 Hash.AddInteger(T->getIndex());
377 Hash.AddInteger(T->isParameterPack());
378 }
379
VisitTypedefType(const TypedefType * T)380 void VisitTypedefType(const TypedefType *T) { AddDecl(T->getDecl()); }
381
VisitElaboratedType(const ElaboratedType * T)382 void VisitElaboratedType(const ElaboratedType *T) {
383 AddQualType(T->getNamedType());
384 }
385
VisitUnaryTransformType(const UnaryTransformType * T)386 void VisitUnaryTransformType(const UnaryTransformType *T) {
387 AddQualType(T->getUnderlyingType());
388 AddQualType(T->getBaseType());
389 }
390
VisitVectorType(const VectorType * T)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
VisitExtVectorType(const ExtVectorType * T)397 void VisitExtVectorType(const ExtVectorType *T) { VisitVectorType(T); }
398 };
399
AddType(const Type * T)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
StableHashForTemplateArguments(llvm::ArrayRef<TemplateArgument> Args)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