xref: /llvm-project/clang/lib/AST/ODRHash.cpp (revision 20e904950967c125abc1e91f57e5a373987ff016) 
1 //===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- 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 /// \file
10 /// This file implements the ODRHash class, which calculates a hash based
11 /// on AST nodes, which is stable across different runs.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/AST/ODRHash.h"
16 
17 #include "clang/AST/DeclVisitor.h"
18 #include "clang/AST/NestedNameSpecifier.h"
19 #include "clang/AST/TypeVisitor.h"
20 
21 using namespace clang;
22 
23 void ODRHash::AddStmt(const Stmt *S) {
24   assert(S && "Expecting non-null pointer.");
25   S->ProcessODRHash(ID, *this);
26 }
27 
28 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
29   assert(II && "Expecting non-null pointer.");
30   ID.AddString(II->getName());
31 }
32 
33 void ODRHash::AddDeclarationName(DeclarationName Name, bool TreatAsDecl) {
34   if (TreatAsDecl)
35     // Matches the NamedDecl check in AddDecl
36     AddBoolean(true);
37 
38   AddDeclarationNameImpl(Name);
39 
40   if (TreatAsDecl)
41     // Matches the ClassTemplateSpecializationDecl check in AddDecl
42     AddBoolean(false);
43 }
44 
45 void ODRHash::AddDeclarationNameImpl(DeclarationName Name) {
46   // Index all DeclarationName and use index numbers to refer to them.
47   auto Result = DeclNameMap.insert(std::make_pair(Name, DeclNameMap.size()));
48   ID.AddInteger(Result.first->second);
49   if (!Result.second) {
50     // If found in map, the DeclarationName has previously been processed.
51     return;
52   }
53 
54   // First time processing each DeclarationName, also process its details.
55   AddBoolean(Name.isEmpty());
56   if (Name.isEmpty())
57     return;
58 
59   auto Kind = Name.getNameKind();
60   ID.AddInteger(Kind);
61   switch (Kind) {
62   case DeclarationName::Identifier:
63     AddIdentifierInfo(Name.getAsIdentifierInfo());
64     break;
65   case DeclarationName::ObjCZeroArgSelector:
66   case DeclarationName::ObjCOneArgSelector:
67   case DeclarationName::ObjCMultiArgSelector: {
68     Selector S = Name.getObjCSelector();
69     AddBoolean(S.isNull());
70     AddBoolean(S.isKeywordSelector());
71     AddBoolean(S.isUnarySelector());
72     unsigned NumArgs = S.getNumArgs();
73     ID.AddInteger(NumArgs);
74     // Compare all selector slots. For selectors with arguments it means all arg
75     // slots. And if there are no arguments, compare the first-and-only slot.
76     unsigned SlotsToCheck = NumArgs > 0 ? NumArgs : 1;
77     for (unsigned i = 0; i < SlotsToCheck; ++i) {
78       const IdentifierInfo *II = S.getIdentifierInfoForSlot(i);
79       AddBoolean(II);
80       if (II) {
81         AddIdentifierInfo(II);
82       }
83     }
84     break;
85   }
86   case DeclarationName::CXXConstructorName:
87   case DeclarationName::CXXDestructorName:
88     AddQualType(Name.getCXXNameType());
89     break;
90   case DeclarationName::CXXOperatorName:
91     ID.AddInteger(Name.getCXXOverloadedOperator());
92     break;
93   case DeclarationName::CXXLiteralOperatorName:
94     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
95     break;
96   case DeclarationName::CXXConversionFunctionName:
97     AddQualType(Name.getCXXNameType());
98     break;
99   case DeclarationName::CXXUsingDirective:
100     break;
101   case DeclarationName::CXXDeductionGuideName: {
102     auto *Template = Name.getCXXDeductionGuideTemplate();
103     AddBoolean(Template);
104     if (Template) {
105       AddDecl(Template);
106     }
107   }
108   }
109 }
110 
111 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
112   assert(NNS && "Expecting non-null pointer.");
113   const auto *Prefix = NNS->getPrefix();
114   AddBoolean(Prefix);
115   if (Prefix) {
116     AddNestedNameSpecifier(Prefix);
117   }
118   auto Kind = NNS->getKind();
119   ID.AddInteger(Kind);
120   switch (Kind) {
121   case NestedNameSpecifier::Identifier:
122     AddIdentifierInfo(NNS->getAsIdentifier());
123     break;
124   case NestedNameSpecifier::Namespace:
125     AddDecl(NNS->getAsNamespace());
126     break;
127   case NestedNameSpecifier::NamespaceAlias:
128     AddDecl(NNS->getAsNamespaceAlias());
129     break;
130   case NestedNameSpecifier::TypeSpec:
131   case NestedNameSpecifier::TypeSpecWithTemplate:
132     AddType(NNS->getAsType());
133     break;
134   case NestedNameSpecifier::Global:
135   case NestedNameSpecifier::Super:
136     break;
137   }
138 }
139 
140 void ODRHash::AddTemplateName(TemplateName Name) {
141   auto Kind = Name.getKind();
142   ID.AddInteger(Kind);
143 
144   switch (Kind) {
145   case TemplateName::Template:
146     AddDecl(Name.getAsTemplateDecl());
147     break;
148   case TemplateName::QualifiedTemplate: {
149     QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName();
150     if (NestedNameSpecifier *NNS = QTN->getQualifier())
151       AddNestedNameSpecifier(NNS);
152     AddBoolean(QTN->hasTemplateKeyword());
153     AddTemplateName(QTN->getUnderlyingTemplate());
154     break;
155   }
156   // TODO: Support these cases.
157   case TemplateName::OverloadedTemplate:
158   case TemplateName::AssumedTemplate:
159   case TemplateName::DependentTemplate:
160   case TemplateName::SubstTemplateTemplateParm:
161   case TemplateName::SubstTemplateTemplateParmPack:
162   case TemplateName::UsingTemplate:
163     break;
164   case TemplateName::DeducedTemplate:
165     llvm_unreachable("Unexpected DeducedTemplate");
166   }
167 }
168 
169 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
170   const auto Kind = TA.getKind();
171   ID.AddInteger(Kind);
172 
173   switch (Kind) {
174     case TemplateArgument::Null:
175       llvm_unreachable("Expected valid TemplateArgument");
176     case TemplateArgument::Type:
177       AddQualType(TA.getAsType());
178       break;
179     case TemplateArgument::Declaration:
180       AddDecl(TA.getAsDecl());
181       break;
182     case TemplateArgument::NullPtr:
183       ID.AddPointer(nullptr);
184       break;
185     case TemplateArgument::Integral: {
186       // There are integrals (e.g.: _BitInt(128)) that cannot be represented as
187       // any builtin integral type, so we use the hash of APSInt instead.
188       TA.getAsIntegral().Profile(ID);
189       break;
190     }
191     case TemplateArgument::StructuralValue:
192       AddQualType(TA.getStructuralValueType());
193       AddStructuralValue(TA.getAsStructuralValue());
194       break;
195     case TemplateArgument::Template:
196     case TemplateArgument::TemplateExpansion:
197       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
198       break;
199     case TemplateArgument::Expression:
200       AddStmt(TA.getAsExpr());
201       break;
202     case TemplateArgument::Pack:
203       ID.AddInteger(TA.pack_size());
204       for (auto SubTA : TA.pack_elements()) {
205         AddTemplateArgument(SubTA);
206       }
207       break;
208   }
209 }
210 
211 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
212   assert(TPL && "Expecting non-null pointer.");
213 
214   ID.AddInteger(TPL->size());
215   for (auto *ND : TPL->asArray()) {
216     AddSubDecl(ND);
217   }
218 }
219 
220 void ODRHash::clear() {
221   DeclNameMap.clear();
222   Bools.clear();
223   ID.clear();
224 }
225 
226 unsigned ODRHash::CalculateHash() {
227   // Append the bools to the end of the data segment backwards.  This allows
228   // for the bools data to be compressed 32 times smaller compared to using
229   // ID.AddBoolean
230   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
231   const unsigned size = Bools.size();
232   const unsigned remainder = size % unsigned_bits;
233   const unsigned loops = size / unsigned_bits;
234   auto I = Bools.rbegin();
235   unsigned value = 0;
236   for (unsigned i = 0; i < remainder; ++i) {
237     value <<= 1;
238     value |= *I;
239     ++I;
240   }
241   ID.AddInteger(value);
242 
243   for (unsigned i = 0; i < loops; ++i) {
244     value = 0;
245     for (unsigned j = 0; j < unsigned_bits; ++j) {
246       value <<= 1;
247       value |= *I;
248       ++I;
249     }
250     ID.AddInteger(value);
251   }
252 
253   assert(I == Bools.rend());
254   Bools.clear();
255   return ID.computeStableHash();
256 }
257 
258 namespace {
259 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
260 // methods process the relevant parts of the Decl.
261 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
262   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
263   llvm::FoldingSetNodeID &ID;
264   ODRHash &Hash;
265 
266 public:
267   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
268       : ID(ID), Hash(Hash) {}
269 
270   void AddStmt(const Stmt *S) {
271     Hash.AddBoolean(S);
272     if (S) {
273       Hash.AddStmt(S);
274     }
275   }
276 
277   void AddIdentifierInfo(const IdentifierInfo *II) {
278     Hash.AddBoolean(II);
279     if (II) {
280       Hash.AddIdentifierInfo(II);
281     }
282   }
283 
284   void AddQualType(QualType T) {
285     Hash.AddQualType(T);
286   }
287 
288   void AddDecl(const Decl *D) {
289     Hash.AddBoolean(D);
290     if (D) {
291       Hash.AddDecl(D);
292     }
293   }
294 
295   void AddTemplateArgument(TemplateArgument TA) {
296     Hash.AddTemplateArgument(TA);
297   }
298 
299   void Visit(const Decl *D) {
300     ID.AddInteger(D->getKind());
301     Inherited::Visit(D);
302   }
303 
304   void VisitNamedDecl(const NamedDecl *D) {
305     Hash.AddDeclarationName(D->getDeclName());
306     Inherited::VisitNamedDecl(D);
307   }
308 
309   void VisitValueDecl(const ValueDecl *D) {
310     if (auto *DD = dyn_cast<DeclaratorDecl>(D); DD && DD->getTypeSourceInfo())
311       AddQualType(DD->getTypeSourceInfo()->getType());
312 
313     Inherited::VisitValueDecl(D);
314   }
315 
316   void VisitVarDecl(const VarDecl *D) {
317     Hash.AddBoolean(D->isStaticLocal());
318     Hash.AddBoolean(D->isConstexpr());
319     const bool HasInit = D->hasInit();
320     Hash.AddBoolean(HasInit);
321     if (HasInit) {
322       AddStmt(D->getInit());
323     }
324     Inherited::VisitVarDecl(D);
325   }
326 
327   void VisitParmVarDecl(const ParmVarDecl *D) {
328     // TODO: Handle default arguments.
329     Inherited::VisitParmVarDecl(D);
330   }
331 
332   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
333     ID.AddInteger(D->getAccess());
334     Inherited::VisitAccessSpecDecl(D);
335   }
336 
337   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
338     AddStmt(D->getAssertExpr());
339     AddStmt(D->getMessage());
340 
341     Inherited::VisitStaticAssertDecl(D);
342   }
343 
344   void VisitFieldDecl(const FieldDecl *D) {
345     const bool IsBitfield = D->isBitField();
346     Hash.AddBoolean(IsBitfield);
347 
348     if (IsBitfield) {
349       AddStmt(D->getBitWidth());
350     }
351 
352     Hash.AddBoolean(D->isMutable());
353     AddStmt(D->getInClassInitializer());
354 
355     Inherited::VisitFieldDecl(D);
356   }
357 
358   void VisitObjCIvarDecl(const ObjCIvarDecl *D) {
359     ID.AddInteger(D->getCanonicalAccessControl());
360     Inherited::VisitObjCIvarDecl(D);
361   }
362 
363   void VisitObjCPropertyDecl(const ObjCPropertyDecl *D) {
364     ID.AddInteger(D->getPropertyAttributes());
365     ID.AddInteger(D->getPropertyImplementation());
366     AddQualType(D->getTypeSourceInfo()->getType());
367     AddDecl(D);
368 
369     Inherited::VisitObjCPropertyDecl(D);
370   }
371 
372   void VisitFunctionDecl(const FunctionDecl *D) {
373     // Handled by the ODRHash for FunctionDecl
374     ID.AddInteger(D->getODRHash());
375 
376     Inherited::VisitFunctionDecl(D);
377   }
378 
379   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
380     // Handled by the ODRHash for FunctionDecl
381 
382     Inherited::VisitCXXMethodDecl(D);
383   }
384 
385   void VisitObjCMethodDecl(const ObjCMethodDecl *Method) {
386     ID.AddInteger(Method->getDeclKind());
387     Hash.AddBoolean(Method->isInstanceMethod()); // false if class method
388     Hash.AddBoolean(Method->isVariadic());
389     Hash.AddBoolean(Method->isSynthesizedAccessorStub());
390     Hash.AddBoolean(Method->isDefined());
391     Hash.AddBoolean(Method->isDirectMethod());
392     Hash.AddBoolean(Method->isThisDeclarationADesignatedInitializer());
393     Hash.AddBoolean(Method->hasSkippedBody());
394 
395     ID.AddInteger(llvm::to_underlying(Method->getImplementationControl()));
396     ID.AddInteger(Method->getMethodFamily());
397     ImplicitParamDecl *Cmd = Method->getCmdDecl();
398     Hash.AddBoolean(Cmd);
399     if (Cmd)
400       ID.AddInteger(llvm::to_underlying(Cmd->getParameterKind()));
401 
402     ImplicitParamDecl *Self = Method->getSelfDecl();
403     Hash.AddBoolean(Self);
404     if (Self)
405       ID.AddInteger(llvm::to_underlying(Self->getParameterKind()));
406 
407     AddDecl(Method);
408 
409     if (Method->getReturnTypeSourceInfo())
410       AddQualType(Method->getReturnTypeSourceInfo()->getType());
411 
412     ID.AddInteger(Method->param_size());
413     for (auto Param : Method->parameters())
414       Hash.AddSubDecl(Param);
415 
416     if (Method->hasBody()) {
417       const bool IsDefinition = Method->isThisDeclarationADefinition();
418       Hash.AddBoolean(IsDefinition);
419       if (IsDefinition) {
420         Stmt *Body = Method->getBody();
421         Hash.AddBoolean(Body);
422         if (Body)
423           AddStmt(Body);
424 
425         // Filter out sub-Decls which will not be processed in order to get an
426         // accurate count of Decl's.
427         llvm::SmallVector<const Decl *, 16> Decls;
428         for (Decl *SubDecl : Method->decls())
429           if (ODRHash::isSubDeclToBeProcessed(SubDecl, Method))
430             Decls.push_back(SubDecl);
431 
432         ID.AddInteger(Decls.size());
433         for (auto SubDecl : Decls)
434           Hash.AddSubDecl(SubDecl);
435       }
436     } else {
437       Hash.AddBoolean(false);
438     }
439 
440     Inherited::VisitObjCMethodDecl(Method);
441   }
442 
443   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
444     AddQualType(D->getUnderlyingType());
445 
446     Inherited::VisitTypedefNameDecl(D);
447   }
448 
449   void VisitTypedefDecl(const TypedefDecl *D) {
450     Inherited::VisitTypedefDecl(D);
451   }
452 
453   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
454     Inherited::VisitTypeAliasDecl(D);
455   }
456 
457   void VisitFriendDecl(const FriendDecl *D) {
458     TypeSourceInfo *TSI = D->getFriendType();
459     Hash.AddBoolean(TSI);
460     if (TSI) {
461       AddQualType(TSI->getType());
462     } else {
463       AddDecl(D->getFriendDecl());
464     }
465     Hash.AddBoolean(D->isPackExpansion());
466   }
467 
468   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
469     // Only care about default arguments as part of the definition.
470     const bool hasDefaultArgument =
471         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
472     Hash.AddBoolean(hasDefaultArgument);
473     if (hasDefaultArgument) {
474       AddTemplateArgument(D->getDefaultArgument().getArgument());
475     }
476     Hash.AddBoolean(D->isParameterPack());
477 
478     const TypeConstraint *TC = D->getTypeConstraint();
479     Hash.AddBoolean(TC != nullptr);
480     if (TC)
481       AddStmt(TC->getImmediatelyDeclaredConstraint());
482 
483     Inherited::VisitTemplateTypeParmDecl(D);
484   }
485 
486   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
487     // Only care about default arguments as part of the definition.
488     const bool hasDefaultArgument =
489         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
490     Hash.AddBoolean(hasDefaultArgument);
491     if (hasDefaultArgument) {
492       AddTemplateArgument(D->getDefaultArgument().getArgument());
493     }
494     Hash.AddBoolean(D->isParameterPack());
495 
496     Inherited::VisitNonTypeTemplateParmDecl(D);
497   }
498 
499   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
500     // Only care about default arguments as part of the definition.
501     const bool hasDefaultArgument =
502         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
503     Hash.AddBoolean(hasDefaultArgument);
504     if (hasDefaultArgument) {
505       AddTemplateArgument(D->getDefaultArgument().getArgument());
506     }
507     Hash.AddBoolean(D->isParameterPack());
508 
509     Inherited::VisitTemplateTemplateParmDecl(D);
510   }
511 
512   void VisitTemplateDecl(const TemplateDecl *D) {
513     Hash.AddTemplateParameterList(D->getTemplateParameters());
514 
515     Inherited::VisitTemplateDecl(D);
516   }
517 
518   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
519     Hash.AddBoolean(D->isMemberSpecialization());
520     Inherited::VisitRedeclarableTemplateDecl(D);
521   }
522 
523   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
524     AddDecl(D->getTemplatedDecl());
525     ID.AddInteger(D->getTemplatedDecl()->getODRHash());
526     Inherited::VisitFunctionTemplateDecl(D);
527   }
528 
529   void VisitEnumConstantDecl(const EnumConstantDecl *D) {
530     AddStmt(D->getInitExpr());
531     Inherited::VisitEnumConstantDecl(D);
532   }
533 };
534 } // namespace
535 
536 // Only allow a small portion of Decl's to be processed.  Remove this once
537 // all Decl's can be handled.
538 bool ODRHash::isSubDeclToBeProcessed(const Decl *D, const DeclContext *Parent) {
539   if (D->isImplicit()) return false;
540   if (D->getDeclContext() != Parent) return false;
541 
542   switch (D->getKind()) {
543     default:
544       return false;
545     case Decl::AccessSpec:
546     case Decl::CXXConstructor:
547     case Decl::CXXDestructor:
548     case Decl::CXXMethod:
549     case Decl::EnumConstant: // Only found in EnumDecl's.
550     case Decl::Field:
551     case Decl::Friend:
552     case Decl::FunctionTemplate:
553     case Decl::StaticAssert:
554     case Decl::TypeAlias:
555     case Decl::Typedef:
556     case Decl::Var:
557     case Decl::ObjCMethod:
558     case Decl::ObjCIvar:
559     case Decl::ObjCProperty:
560       return true;
561   }
562 }
563 
564 void ODRHash::AddSubDecl(const Decl *D) {
565   assert(D && "Expecting non-null pointer.");
566 
567   ODRDeclVisitor(ID, *this).Visit(D);
568 }
569 
570 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
571   assert(Record && Record->hasDefinition() &&
572          "Expected non-null record to be a definition.");
573 
574   const DeclContext *DC = Record;
575   while (DC) {
576     if (isa<ClassTemplateSpecializationDecl>(DC)) {
577       return;
578     }
579     DC = DC->getParent();
580   }
581 
582   AddDecl(Record);
583 
584   // Filter out sub-Decls which will not be processed in order to get an
585   // accurate count of Decl's.
586   llvm::SmallVector<const Decl *, 16> Decls;
587   for (Decl *SubDecl : Record->decls()) {
588     if (isSubDeclToBeProcessed(SubDecl, Record)) {
589       Decls.push_back(SubDecl);
590       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
591         // Compute/Preload ODRHash into FunctionDecl.
592         Function->getODRHash();
593       }
594     }
595   }
596 
597   ID.AddInteger(Decls.size());
598   for (auto SubDecl : Decls) {
599     AddSubDecl(SubDecl);
600   }
601 
602   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
603   AddBoolean(TD);
604   if (TD) {
605     AddTemplateParameterList(TD->getTemplateParameters());
606   }
607 
608   ID.AddInteger(Record->getNumBases());
609   auto Bases = Record->bases();
610   for (const auto &Base : Bases) {
611     AddQualType(Base.getTypeSourceInfo()->getType());
612     ID.AddInteger(Base.isVirtual());
613     ID.AddInteger(Base.getAccessSpecifierAsWritten());
614   }
615 }
616 
617 void ODRHash::AddRecordDecl(const RecordDecl *Record) {
618   assert(!isa<CXXRecordDecl>(Record) &&
619          "For CXXRecordDecl should call AddCXXRecordDecl.");
620   AddDecl(Record);
621 
622   // Filter out sub-Decls which will not be processed in order to get an
623   // accurate count of Decl's.
624   llvm::SmallVector<const Decl *, 16> Decls;
625   for (Decl *SubDecl : Record->decls()) {
626     if (isSubDeclToBeProcessed(SubDecl, Record))
627       Decls.push_back(SubDecl);
628   }
629 
630   ID.AddInteger(Decls.size());
631   for (const Decl *SubDecl : Decls)
632     AddSubDecl(SubDecl);
633 }
634 
635 void ODRHash::AddObjCInterfaceDecl(const ObjCInterfaceDecl *IF) {
636   AddDecl(IF);
637 
638   auto *SuperClass = IF->getSuperClass();
639   AddBoolean(SuperClass);
640   if (SuperClass)
641     ID.AddInteger(SuperClass->getODRHash());
642 
643   // Hash referenced protocols.
644   ID.AddInteger(IF->getReferencedProtocols().size());
645   for (const ObjCProtocolDecl *RefP : IF->protocols()) {
646     // Hash the name only as a referenced protocol can be a forward declaration.
647     AddDeclarationName(RefP->getDeclName());
648   }
649 
650   // Filter out sub-Decls which will not be processed in order to get an
651   // accurate count of Decl's.
652   llvm::SmallVector<const Decl *, 16> Decls;
653   for (Decl *SubDecl : IF->decls())
654     if (isSubDeclToBeProcessed(SubDecl, IF))
655       Decls.push_back(SubDecl);
656 
657   ID.AddInteger(Decls.size());
658   for (auto *SubDecl : Decls)
659     AddSubDecl(SubDecl);
660 }
661 
662 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
663                               bool SkipBody) {
664   assert(Function && "Expecting non-null pointer.");
665 
666   // Skip functions that are specializations or in specialization context.
667   const DeclContext *DC = Function;
668   while (DC) {
669     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
670     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
671       if (F->isFunctionTemplateSpecialization()) {
672         if (!isa<CXXMethodDecl>(DC)) return;
673         if (DC->getLexicalParent()->isFileContext()) return;
674         // Skip class scope explicit function template specializations,
675         // as they have not yet been instantiated.
676         if (F->getDependentSpecializationInfo())
677           return;
678         // Inline method specializations are the only supported
679         // specialization for now.
680       }
681     }
682     DC = DC->getParent();
683   }
684 
685   ID.AddInteger(Function->getDeclKind());
686 
687   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
688   AddBoolean(SpecializationArgs);
689   if (SpecializationArgs) {
690     ID.AddInteger(SpecializationArgs->size());
691     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
692       AddTemplateArgument(TA);
693     }
694   }
695 
696   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
697     AddBoolean(Method->isConst());
698     AddBoolean(Method->isVolatile());
699   }
700 
701   ID.AddInteger(Function->getStorageClass());
702   AddBoolean(Function->isInlineSpecified());
703   AddBoolean(Function->isVirtualAsWritten());
704   AddBoolean(Function->isPureVirtual());
705   AddBoolean(Function->isDeletedAsWritten());
706   AddBoolean(Function->isExplicitlyDefaulted());
707 
708   StringLiteral *DeletedMessage = Function->getDeletedMessage();
709   AddBoolean(DeletedMessage);
710 
711   if (DeletedMessage)
712     ID.AddString(DeletedMessage->getBytes());
713 
714   AddDecl(Function);
715 
716   AddQualType(Function->getReturnType());
717 
718   ID.AddInteger(Function->param_size());
719   for (auto *Param : Function->parameters())
720     AddSubDecl(Param);
721 
722   if (SkipBody) {
723     AddBoolean(false);
724     return;
725   }
726 
727   const bool HasBody = Function->isThisDeclarationADefinition() &&
728                        !Function->isDefaulted() && !Function->isDeleted() &&
729                        !Function->isLateTemplateParsed();
730   AddBoolean(HasBody);
731   if (!HasBody) {
732     return;
733   }
734 
735   auto *Body = Function->getBody();
736   AddBoolean(Body);
737   if (Body)
738     AddStmt(Body);
739 
740   // Filter out sub-Decls which will not be processed in order to get an
741   // accurate count of Decl's.
742   llvm::SmallVector<const Decl *, 16> Decls;
743   for (Decl *SubDecl : Function->decls()) {
744     if (isSubDeclToBeProcessed(SubDecl, Function)) {
745       Decls.push_back(SubDecl);
746     }
747   }
748 
749   ID.AddInteger(Decls.size());
750   for (auto SubDecl : Decls) {
751     AddSubDecl(SubDecl);
752   }
753 }
754 
755 void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
756   assert(Enum);
757   AddDeclarationName(Enum->getDeclName());
758 
759   AddBoolean(Enum->isScoped());
760   if (Enum->isScoped())
761     AddBoolean(Enum->isScopedUsingClassTag());
762 
763   if (Enum->getIntegerTypeSourceInfo())
764     AddQualType(Enum->getIntegerType().getCanonicalType());
765 
766   // Filter out sub-Decls which will not be processed in order to get an
767   // accurate count of Decl's.
768   llvm::SmallVector<const Decl *, 16> Decls;
769   for (Decl *SubDecl : Enum->decls()) {
770     if (isSubDeclToBeProcessed(SubDecl, Enum)) {
771       assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
772       Decls.push_back(SubDecl);
773     }
774   }
775 
776   ID.AddInteger(Decls.size());
777   for (auto SubDecl : Decls) {
778     AddSubDecl(SubDecl);
779   }
780 
781 }
782 
783 void ODRHash::AddObjCProtocolDecl(const ObjCProtocolDecl *P) {
784   AddDecl(P);
785 
786   // Hash referenced protocols.
787   ID.AddInteger(P->getReferencedProtocols().size());
788   for (const ObjCProtocolDecl *RefP : P->protocols()) {
789     // Hash the name only as a referenced protocol can be a forward declaration.
790     AddDeclarationName(RefP->getDeclName());
791   }
792 
793   // Filter out sub-Decls which will not be processed in order to get an
794   // accurate count of Decl's.
795   llvm::SmallVector<const Decl *, 16> Decls;
796   for (Decl *SubDecl : P->decls()) {
797     if (isSubDeclToBeProcessed(SubDecl, P)) {
798       Decls.push_back(SubDecl);
799     }
800   }
801 
802   ID.AddInteger(Decls.size());
803   for (auto *SubDecl : Decls) {
804     AddSubDecl(SubDecl);
805   }
806 }
807 
808 void ODRHash::AddDecl(const Decl *D) {
809   assert(D && "Expecting non-null pointer.");
810   D = D->getCanonicalDecl();
811 
812   const NamedDecl *ND = dyn_cast<NamedDecl>(D);
813   AddBoolean(ND);
814   if (!ND) {
815     ID.AddInteger(D->getKind());
816     return;
817   }
818 
819   AddDeclarationName(ND->getDeclName());
820 
821   // If this was a specialization we should take into account its template
822   // arguments. This helps to reduce collisions coming when visiting template
823   // specialization types (eg. when processing type template arguments).
824   ArrayRef<TemplateArgument> Args;
825   if (auto *CTSD = dyn_cast<ClassTemplateSpecializationDecl>(D))
826     Args = CTSD->getTemplateArgs().asArray();
827   else if (auto *VTSD = dyn_cast<VarTemplateSpecializationDecl>(D))
828     Args = VTSD->getTemplateArgs().asArray();
829   else if (auto *FD = dyn_cast<FunctionDecl>(D))
830     if (FD->getTemplateSpecializationArgs())
831       Args = FD->getTemplateSpecializationArgs()->asArray();
832 
833   for (auto &TA : Args)
834     AddTemplateArgument(TA);
835 }
836 
837 namespace {
838 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
839 // methods process the relevant parts of the Type.
840 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
841   typedef TypeVisitor<ODRTypeVisitor> Inherited;
842   llvm::FoldingSetNodeID &ID;
843   ODRHash &Hash;
844 
845 public:
846   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
847       : ID(ID), Hash(Hash) {}
848 
849   void AddStmt(Stmt *S) {
850     Hash.AddBoolean(S);
851     if (S) {
852       Hash.AddStmt(S);
853     }
854   }
855 
856   void AddDecl(const Decl *D) {
857     Hash.AddBoolean(D);
858     if (D) {
859       Hash.AddDecl(D);
860     }
861   }
862 
863   void AddQualType(QualType T) {
864     Hash.AddQualType(T);
865   }
866 
867   void AddType(const Type *T) {
868     Hash.AddBoolean(T);
869     if (T) {
870       Hash.AddType(T);
871     }
872   }
873 
874   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
875     Hash.AddBoolean(NNS);
876     if (NNS) {
877       Hash.AddNestedNameSpecifier(NNS);
878     }
879   }
880 
881   void AddIdentifierInfo(const IdentifierInfo *II) {
882     Hash.AddBoolean(II);
883     if (II) {
884       Hash.AddIdentifierInfo(II);
885     }
886   }
887 
888   void VisitQualifiers(Qualifiers Quals) {
889     ID.AddInteger(Quals.getAsOpaqueValue());
890   }
891 
892   // Return the RecordType if the typedef only strips away a keyword.
893   // Otherwise, return the original type.
894   static const Type *RemoveTypedef(const Type *T) {
895     const auto *TypedefT = dyn_cast<TypedefType>(T);
896     if (!TypedefT) {
897       return T;
898     }
899 
900     const TypedefNameDecl *D = TypedefT->getDecl();
901     QualType UnderlyingType = D->getUnderlyingType();
902 
903     if (UnderlyingType.hasLocalQualifiers()) {
904       return T;
905     }
906 
907     const auto *ElaboratedT = dyn_cast<ElaboratedType>(UnderlyingType);
908     if (!ElaboratedT) {
909       return T;
910     }
911 
912     if (ElaboratedT->getQualifier() != nullptr) {
913       return T;
914     }
915 
916     QualType NamedType = ElaboratedT->getNamedType();
917     if (NamedType.hasLocalQualifiers()) {
918       return T;
919     }
920 
921     const auto *RecordT = dyn_cast<RecordType>(NamedType);
922     if (!RecordT) {
923       return T;
924     }
925 
926     const IdentifierInfo *TypedefII = TypedefT->getDecl()->getIdentifier();
927     const IdentifierInfo *RecordII = RecordT->getDecl()->getIdentifier();
928     if (!TypedefII || !RecordII ||
929         TypedefII->getName() != RecordII->getName()) {
930       return T;
931     }
932 
933     return RecordT;
934   }
935 
936   void Visit(const Type *T) {
937     T = RemoveTypedef(T);
938     ID.AddInteger(T->getTypeClass());
939     Inherited::Visit(T);
940   }
941 
942   void VisitType(const Type *T) {}
943 
944   void VisitAdjustedType(const AdjustedType *T) {
945     AddQualType(T->getOriginalType());
946 
947     VisitType(T);
948   }
949 
950   void VisitDecayedType(const DecayedType *T) {
951     // getDecayedType and getPointeeType are derived from getAdjustedType
952     // and don't need to be separately processed.
953     VisitAdjustedType(T);
954   }
955 
956   void VisitArrayType(const ArrayType *T) {
957     AddQualType(T->getElementType());
958     ID.AddInteger(llvm::to_underlying(T->getSizeModifier()));
959     VisitQualifiers(T->getIndexTypeQualifiers());
960     VisitType(T);
961   }
962   void VisitConstantArrayType(const ConstantArrayType *T) {
963     T->getSize().Profile(ID);
964     VisitArrayType(T);
965   }
966 
967   void VisitArrayParameterType(const ArrayParameterType *T) {
968     VisitConstantArrayType(T);
969   }
970 
971   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
972     AddStmt(T->getSizeExpr());
973     VisitArrayType(T);
974   }
975 
976   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
977     VisitArrayType(T);
978   }
979 
980   void VisitVariableArrayType(const VariableArrayType *T) {
981     AddStmt(T->getSizeExpr());
982     VisitArrayType(T);
983   }
984 
985   void VisitAttributedType(const AttributedType *T) {
986     ID.AddInteger(T->getAttrKind());
987     AddQualType(T->getModifiedType());
988 
989     VisitType(T);
990   }
991 
992   void VisitBlockPointerType(const BlockPointerType *T) {
993     AddQualType(T->getPointeeType());
994     VisitType(T);
995   }
996 
997   void VisitBuiltinType(const BuiltinType *T) {
998     ID.AddInteger(T->getKind());
999     VisitType(T);
1000   }
1001 
1002   void VisitComplexType(const ComplexType *T) {
1003     AddQualType(T->getElementType());
1004     VisitType(T);
1005   }
1006 
1007   void VisitDecltypeType(const DecltypeType *T) {
1008     AddStmt(T->getUnderlyingExpr());
1009     VisitType(T);
1010   }
1011 
1012   void VisitDependentDecltypeType(const DependentDecltypeType *T) {
1013     VisitDecltypeType(T);
1014   }
1015 
1016   void VisitDeducedType(const DeducedType *T) {
1017     AddQualType(T->getDeducedType());
1018     VisitType(T);
1019   }
1020 
1021   void VisitAutoType(const AutoType *T) {
1022     ID.AddInteger((unsigned)T->getKeyword());
1023     ID.AddInteger(T->isConstrained());
1024     if (T->isConstrained()) {
1025       AddDecl(T->getTypeConstraintConcept());
1026       ID.AddInteger(T->getTypeConstraintArguments().size());
1027       for (const auto &TA : T->getTypeConstraintArguments())
1028         Hash.AddTemplateArgument(TA);
1029     }
1030     VisitDeducedType(T);
1031   }
1032 
1033   void VisitDeducedTemplateSpecializationType(
1034       const DeducedTemplateSpecializationType *T) {
1035     Hash.AddTemplateName(T->getTemplateName());
1036     VisitDeducedType(T);
1037   }
1038 
1039   void VisitDependentAddressSpaceType(const DependentAddressSpaceType *T) {
1040     AddQualType(T->getPointeeType());
1041     AddStmt(T->getAddrSpaceExpr());
1042     VisitType(T);
1043   }
1044 
1045   void VisitDependentSizedExtVectorType(const DependentSizedExtVectorType *T) {
1046     AddQualType(T->getElementType());
1047     AddStmt(T->getSizeExpr());
1048     VisitType(T);
1049   }
1050 
1051   void VisitFunctionType(const FunctionType *T) {
1052     AddQualType(T->getReturnType());
1053     T->getExtInfo().Profile(ID);
1054     Hash.AddBoolean(T->isConst());
1055     Hash.AddBoolean(T->isVolatile());
1056     Hash.AddBoolean(T->isRestrict());
1057     VisitType(T);
1058   }
1059 
1060   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
1061     VisitFunctionType(T);
1062   }
1063 
1064   void VisitFunctionProtoType(const FunctionProtoType *T) {
1065     ID.AddInteger(T->getNumParams());
1066     for (auto ParamType : T->getParamTypes())
1067       AddQualType(ParamType);
1068 
1069     VisitFunctionType(T);
1070   }
1071 
1072   void VisitInjectedClassNameType(const InjectedClassNameType *T) {
1073     AddDecl(T->getDecl());
1074     VisitType(T);
1075   }
1076 
1077   void VisitMemberPointerType(const MemberPointerType *T) {
1078     AddQualType(T->getPointeeType());
1079     AddType(T->getClass());
1080     VisitType(T);
1081   }
1082 
1083   void VisitObjCObjectPointerType(const ObjCObjectPointerType *T) {
1084     AddQualType(T->getPointeeType());
1085     VisitType(T);
1086   }
1087 
1088   void VisitObjCObjectType(const ObjCObjectType *T) {
1089     AddDecl(T->getInterface());
1090 
1091     auto TypeArgs = T->getTypeArgsAsWritten();
1092     ID.AddInteger(TypeArgs.size());
1093     for (auto Arg : TypeArgs) {
1094       AddQualType(Arg);
1095     }
1096 
1097     auto Protocols = T->getProtocols();
1098     ID.AddInteger(Protocols.size());
1099     for (auto *Protocol : Protocols) {
1100       AddDecl(Protocol);
1101     }
1102 
1103     Hash.AddBoolean(T->isKindOfType());
1104 
1105     VisitType(T);
1106   }
1107 
1108   void VisitObjCInterfaceType(const ObjCInterfaceType *T) {
1109     // This type is handled by the parent type ObjCObjectType.
1110     VisitObjCObjectType(T);
1111   }
1112 
1113   void VisitObjCTypeParamType(const ObjCTypeParamType *T) {
1114     AddDecl(T->getDecl());
1115     auto Protocols = T->getProtocols();
1116     ID.AddInteger(Protocols.size());
1117     for (auto *Protocol : Protocols) {
1118       AddDecl(Protocol);
1119     }
1120 
1121     VisitType(T);
1122   }
1123 
1124   void VisitPackExpansionType(const PackExpansionType *T) {
1125     AddQualType(T->getPattern());
1126     VisitType(T);
1127   }
1128 
1129   void VisitParenType(const ParenType *T) {
1130     AddQualType(T->getInnerType());
1131     VisitType(T);
1132   }
1133 
1134   void VisitPipeType(const PipeType *T) {
1135     AddQualType(T->getElementType());
1136     Hash.AddBoolean(T->isReadOnly());
1137     VisitType(T);
1138   }
1139 
1140   void VisitPointerType(const PointerType *T) {
1141     AddQualType(T->getPointeeType());
1142     VisitType(T);
1143   }
1144 
1145   void VisitReferenceType(const ReferenceType *T) {
1146     AddQualType(T->getPointeeTypeAsWritten());
1147     VisitType(T);
1148   }
1149 
1150   void VisitLValueReferenceType(const LValueReferenceType *T) {
1151     VisitReferenceType(T);
1152   }
1153 
1154   void VisitRValueReferenceType(const RValueReferenceType *T) {
1155     VisitReferenceType(T);
1156   }
1157 
1158   void
1159   VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {
1160     AddDecl(T->getAssociatedDecl());
1161     Hash.AddTemplateArgument(T->getArgumentPack());
1162     VisitType(T);
1163   }
1164 
1165   void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
1166     AddDecl(T->getAssociatedDecl());
1167     AddQualType(T->getReplacementType());
1168     VisitType(T);
1169   }
1170 
1171   void VisitTagType(const TagType *T) {
1172     AddDecl(T->getDecl());
1173     VisitType(T);
1174   }
1175 
1176   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
1177   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
1178 
1179   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
1180     ID.AddInteger(T->template_arguments().size());
1181     for (const auto &TA : T->template_arguments()) {
1182       Hash.AddTemplateArgument(TA);
1183     }
1184     Hash.AddTemplateName(T->getTemplateName());
1185     VisitType(T);
1186   }
1187 
1188   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
1189     ID.AddInteger(T->getDepth());
1190     ID.AddInteger(T->getIndex());
1191     Hash.AddBoolean(T->isParameterPack());
1192     AddDecl(T->getDecl());
1193   }
1194 
1195   void VisitTypedefType(const TypedefType *T) {
1196     AddDecl(T->getDecl());
1197     VisitType(T);
1198   }
1199 
1200   void VisitTypeOfExprType(const TypeOfExprType *T) {
1201     AddStmt(T->getUnderlyingExpr());
1202     Hash.AddBoolean(T->isSugared());
1203 
1204     VisitType(T);
1205   }
1206   void VisitTypeOfType(const TypeOfType *T) {
1207     AddQualType(T->getUnmodifiedType());
1208     VisitType(T);
1209   }
1210 
1211   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
1212     ID.AddInteger(llvm::to_underlying(T->getKeyword()));
1213     VisitType(T);
1214   };
1215 
1216   void VisitDependentNameType(const DependentNameType *T) {
1217     AddNestedNameSpecifier(T->getQualifier());
1218     AddIdentifierInfo(T->getIdentifier());
1219     VisitTypeWithKeyword(T);
1220   }
1221 
1222   void VisitDependentTemplateSpecializationType(
1223       const DependentTemplateSpecializationType *T) {
1224     AddIdentifierInfo(T->getIdentifier());
1225     AddNestedNameSpecifier(T->getQualifier());
1226     ID.AddInteger(T->template_arguments().size());
1227     for (const auto &TA : T->template_arguments()) {
1228       Hash.AddTemplateArgument(TA);
1229     }
1230     VisitTypeWithKeyword(T);
1231   }
1232 
1233   void VisitElaboratedType(const ElaboratedType *T) {
1234     AddNestedNameSpecifier(T->getQualifier());
1235     AddQualType(T->getNamedType());
1236     VisitTypeWithKeyword(T);
1237   }
1238 
1239   void VisitUnaryTransformType(const UnaryTransformType *T) {
1240     AddQualType(T->getUnderlyingType());
1241     AddQualType(T->getBaseType());
1242     VisitType(T);
1243   }
1244 
1245   void VisitUnresolvedUsingType(const UnresolvedUsingType *T) {
1246     AddDecl(T->getDecl());
1247     VisitType(T);
1248   }
1249 
1250   void VisitVectorType(const VectorType *T) {
1251     AddQualType(T->getElementType());
1252     ID.AddInteger(T->getNumElements());
1253     ID.AddInteger(llvm::to_underlying(T->getVectorKind()));
1254     VisitType(T);
1255   }
1256 
1257   void VisitExtVectorType(const ExtVectorType * T) {
1258     VisitVectorType(T);
1259   }
1260 };
1261 } // namespace
1262 
1263 void ODRHash::AddType(const Type *T) {
1264   assert(T && "Expecting non-null pointer.");
1265   ODRTypeVisitor(ID, *this).Visit(T);
1266 }
1267 
1268 void ODRHash::AddQualType(QualType T) {
1269   AddBoolean(T.isNull());
1270   if (T.isNull())
1271     return;
1272   SplitQualType split = T.split();
1273   ID.AddInteger(split.Quals.getAsOpaqueValue());
1274   AddType(split.Ty);
1275 }
1276 
1277 void ODRHash::AddBoolean(bool Value) {
1278   Bools.push_back(Value);
1279 }
1280 
1281 void ODRHash::AddStructuralValue(const APValue &Value) {
1282   ID.AddInteger(Value.getKind());
1283 
1284   // 'APValue::Profile' uses pointer values to make hash for LValue and
1285   // MemberPointer, but they differ from one compiler invocation to another.
1286   // So, handle them explicitly here.
1287 
1288   switch (Value.getKind()) {
1289   case APValue::LValue: {
1290     const APValue::LValueBase &Base = Value.getLValueBase();
1291     if (!Base) {
1292       ID.AddInteger(Value.getLValueOffset().getQuantity());
1293       break;
1294     }
1295 
1296     assert(Base.is<const ValueDecl *>());
1297     AddDecl(Base.get<const ValueDecl *>());
1298     ID.AddInteger(Value.getLValueOffset().getQuantity());
1299 
1300     bool OnePastTheEnd = Value.isLValueOnePastTheEnd();
1301     if (Value.hasLValuePath()) {
1302       QualType TypeSoFar = Base.getType();
1303       for (APValue::LValuePathEntry E : Value.getLValuePath()) {
1304         if (const auto *AT = TypeSoFar->getAsArrayTypeUnsafe()) {
1305           if (const auto *CAT = dyn_cast<ConstantArrayType>(AT))
1306             OnePastTheEnd |= CAT->getSize() == E.getAsArrayIndex();
1307           TypeSoFar = AT->getElementType();
1308         } else {
1309           const Decl *D = E.getAsBaseOrMember().getPointer();
1310           if (const auto *FD = dyn_cast<FieldDecl>(D)) {
1311             if (FD->getParent()->isUnion())
1312               ID.AddInteger(FD->getFieldIndex());
1313             TypeSoFar = FD->getType();
1314           } else {
1315             TypeSoFar =
1316                 D->getASTContext().getRecordType(cast<CXXRecordDecl>(D));
1317           }
1318         }
1319       }
1320     }
1321     unsigned Val = 0;
1322     if (Value.isNullPointer())
1323       Val |= 1 << 0;
1324     if (OnePastTheEnd)
1325       Val |= 1 << 1;
1326     if (Value.hasLValuePath())
1327       Val |= 1 << 2;
1328     ID.AddInteger(Val);
1329     break;
1330   }
1331   case APValue::MemberPointer: {
1332     const ValueDecl *D = Value.getMemberPointerDecl();
1333     assert(D);
1334     AddDecl(D);
1335     ID.AddInteger(
1336         D->getASTContext().getMemberPointerPathAdjustment(Value).getQuantity());
1337     break;
1338   }
1339   default:
1340     Value.Profile(ID);
1341   }
1342 }
1343