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