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