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

source code of clang/lib/Serialization/TemplateArgumentHasher.cpp