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->isPropertyAccessor());
377     Hash.AddBoolean(Method->isVariadic());
378     Hash.AddBoolean(Method->isSynthesizedAccessorStub());
379     Hash.AddBoolean(Method->isDefined());
380     Hash.AddBoolean(Method->isOverriding());
381     Hash.AddBoolean(Method->isDirectMethod());
382     Hash.AddBoolean(Method->isThisDeclarationADesignatedInitializer());
383     Hash.AddBoolean(Method->hasSkippedBody());
384 
385     ID.AddInteger(Method->getImplementationControl());
386     ID.AddInteger(Method->getMethodFamily());
387     ImplicitParamDecl *Cmd = Method->getCmdDecl();
388     Hash.AddBoolean(Cmd);
389     if (Cmd)
390       ID.AddInteger(Cmd->getParameterKind());
391 
392     ImplicitParamDecl *Self = Method->getSelfDecl();
393     Hash.AddBoolean(Self);
394     if (Self)
395       ID.AddInteger(Self->getParameterKind());
396 
397     AddDecl(Method);
398 
399     AddQualType(Method->getReturnType());
400     ID.AddInteger(Method->param_size());
401     for (auto Param : Method->parameters())
402       Hash.AddSubDecl(Param);
403 
404     if (Method->hasBody()) {
405       const bool IsDefinition = Method->isThisDeclarationADefinition();
406       Hash.AddBoolean(IsDefinition);
407       if (IsDefinition) {
408         Stmt *Body = Method->getBody();
409         Hash.AddBoolean(Body);
410         if (Body)
411           AddStmt(Body);
412 
413         // Filter out sub-Decls which will not be processed in order to get an
414         // accurate count of Decl's.
415         llvm::SmallVector<const Decl *, 16> Decls;
416         for (Decl *SubDecl : Method->decls())
417           if (ODRHash::isSubDeclToBeProcessed(SubDecl, Method))
418             Decls.push_back(SubDecl);
419 
420         ID.AddInteger(Decls.size());
421         for (auto SubDecl : Decls)
422           Hash.AddSubDecl(SubDecl);
423       }
424     } else {
425       Hash.AddBoolean(false);
426     }
427 
428     Inherited::VisitObjCMethodDecl(Method);
429   }
430 
431   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
432     AddQualType(D->getUnderlyingType());
433 
434     Inherited::VisitTypedefNameDecl(D);
435   }
436 
437   void VisitTypedefDecl(const TypedefDecl *D) {
438     Inherited::VisitTypedefDecl(D);
439   }
440 
441   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
442     Inherited::VisitTypeAliasDecl(D);
443   }
444 
445   void VisitFriendDecl(const FriendDecl *D) {
446     TypeSourceInfo *TSI = D->getFriendType();
447     Hash.AddBoolean(TSI);
448     if (TSI) {
449       AddQualType(TSI->getType());
450     } else {
451       AddDecl(D->getFriendDecl());
452     }
453   }
454 
455   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
456     // Only care about default arguments as part of the definition.
457     const bool hasDefaultArgument =
458         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
459     Hash.AddBoolean(hasDefaultArgument);
460     if (hasDefaultArgument) {
461       AddTemplateArgument(D->getDefaultArgument());
462     }
463     Hash.AddBoolean(D->isParameterPack());
464 
465     const TypeConstraint *TC = D->getTypeConstraint();
466     Hash.AddBoolean(TC != nullptr);
467     if (TC)
468       AddStmt(TC->getImmediatelyDeclaredConstraint());
469 
470     Inherited::VisitTemplateTypeParmDecl(D);
471   }
472 
473   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
474     // Only care about default arguments as part of the definition.
475     const bool hasDefaultArgument =
476         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
477     Hash.AddBoolean(hasDefaultArgument);
478     if (hasDefaultArgument) {
479       AddStmt(D->getDefaultArgument());
480     }
481     Hash.AddBoolean(D->isParameterPack());
482 
483     Inherited::VisitNonTypeTemplateParmDecl(D);
484   }
485 
486   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *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::VisitTemplateTemplateParmDecl(D);
497   }
498 
499   void VisitTemplateDecl(const TemplateDecl *D) {
500     Hash.AddTemplateParameterList(D->getTemplateParameters());
501 
502     Inherited::VisitTemplateDecl(D);
503   }
504 
505   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
506     Hash.AddBoolean(D->isMemberSpecialization());
507     Inherited::VisitRedeclarableTemplateDecl(D);
508   }
509 
510   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
511     AddDecl(D->getTemplatedDecl());
512     ID.AddInteger(D->getTemplatedDecl()->getODRHash());
513     Inherited::VisitFunctionTemplateDecl(D);
514   }
515 
516   void VisitEnumConstantDecl(const EnumConstantDecl *D) {
517     AddStmt(D->getInitExpr());
518     Inherited::VisitEnumConstantDecl(D);
519   }
520 };
521 } // namespace
522 
523 // Only allow a small portion of Decl's to be processed.  Remove this once
524 // all Decl's can be handled.
525 bool ODRHash::isSubDeclToBeProcessed(const Decl *D, const DeclContext *Parent) {
526   if (D->isImplicit()) return false;
527   if (D->getDeclContext() != Parent) return false;
528 
529   switch (D->getKind()) {
530     default:
531       return false;
532     case Decl::AccessSpec:
533     case Decl::CXXConstructor:
534     case Decl::CXXDestructor:
535     case Decl::CXXMethod:
536     case Decl::EnumConstant: // Only found in EnumDecl's.
537     case Decl::Field:
538     case Decl::Friend:
539     case Decl::FunctionTemplate:
540     case Decl::StaticAssert:
541     case Decl::TypeAlias:
542     case Decl::Typedef:
543     case Decl::Var:
544     case Decl::ObjCMethod:
545     case Decl::ObjCIvar:
546     case Decl::ObjCProperty:
547       return true;
548   }
549 }
550 
551 void ODRHash::AddSubDecl(const Decl *D) {
552   assert(D && "Expecting non-null pointer.");
553 
554   ODRDeclVisitor(ID, *this).Visit(D);
555 }
556 
557 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
558   assert(Record && Record->hasDefinition() &&
559          "Expected non-null record to be a definition.");
560 
561   const DeclContext *DC = Record;
562   while (DC) {
563     if (isa<ClassTemplateSpecializationDecl>(DC)) {
564       return;
565     }
566     DC = DC->getParent();
567   }
568 
569   AddDecl(Record);
570 
571   // Filter out sub-Decls which will not be processed in order to get an
572   // accurate count of Decl's.
573   llvm::SmallVector<const Decl *, 16> Decls;
574   for (Decl *SubDecl : Record->decls()) {
575     if (isSubDeclToBeProcessed(SubDecl, Record)) {
576       Decls.push_back(SubDecl);
577       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
578         // Compute/Preload ODRHash into FunctionDecl.
579         Function->getODRHash();
580       }
581     }
582   }
583 
584   ID.AddInteger(Decls.size());
585   for (auto SubDecl : Decls) {
586     AddSubDecl(SubDecl);
587   }
588 
589   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
590   AddBoolean(TD);
591   if (TD) {
592     AddTemplateParameterList(TD->getTemplateParameters());
593   }
594 
595   ID.AddInteger(Record->getNumBases());
596   auto Bases = Record->bases();
597   for (auto Base : Bases) {
598     AddQualType(Base.getType());
599     ID.AddInteger(Base.isVirtual());
600     ID.AddInteger(Base.getAccessSpecifierAsWritten());
601   }
602 }
603 
604 void ODRHash::AddRecordDecl(const RecordDecl *Record) {
605   assert(!isa<CXXRecordDecl>(Record) &&
606          "For CXXRecordDecl should call AddCXXRecordDecl.");
607   AddDecl(Record);
608 
609   // Filter out sub-Decls which will not be processed in order to get an
610   // accurate count of Decl's.
611   llvm::SmallVector<const Decl *, 16> Decls;
612   for (Decl *SubDecl : Record->decls()) {
613     if (isSubDeclToBeProcessed(SubDecl, Record))
614       Decls.push_back(SubDecl);
615   }
616 
617   ID.AddInteger(Decls.size());
618   for (const Decl *SubDecl : Decls)
619     AddSubDecl(SubDecl);
620 }
621 
622 void ODRHash::AddObjCInterfaceDecl(const ObjCInterfaceDecl *IF) {
623   AddDecl(IF);
624 
625   auto *SuperClass = IF->getSuperClass();
626   AddBoolean(SuperClass);
627   if (SuperClass)
628     ID.AddInteger(SuperClass->getODRHash());
629 
630   // Hash referenced protocols.
631   ID.AddInteger(IF->getReferencedProtocols().size());
632   for (const ObjCProtocolDecl *RefP : IF->protocols()) {
633     // Hash the name only as a referenced protocol can be a forward declaration.
634     AddDeclarationName(RefP->getDeclName());
635   }
636 
637   // Filter out sub-Decls which will not be processed in order to get an
638   // accurate count of Decl's.
639   llvm::SmallVector<const Decl *, 16> Decls;
640   for (Decl *SubDecl : IF->decls())
641     if (isSubDeclToBeProcessed(SubDecl, IF))
642       Decls.push_back(SubDecl);
643 
644   ID.AddInteger(Decls.size());
645   for (auto *SubDecl : Decls)
646     AddSubDecl(SubDecl);
647 }
648 
649 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
650                               bool SkipBody) {
651   assert(Function && "Expecting non-null pointer.");
652 
653   // Skip functions that are specializations or in specialization context.
654   const DeclContext *DC = Function;
655   while (DC) {
656     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
657     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
658       if (F->isFunctionTemplateSpecialization()) {
659         if (!isa<CXXMethodDecl>(DC)) return;
660         if (DC->getLexicalParent()->isFileContext()) return;
661         // Inline method specializations are the only supported
662         // specialization for now.
663       }
664     }
665     DC = DC->getParent();
666   }
667 
668   ID.AddInteger(Function->getDeclKind());
669 
670   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
671   AddBoolean(SpecializationArgs);
672   if (SpecializationArgs) {
673     ID.AddInteger(SpecializationArgs->size());
674     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
675       AddTemplateArgument(TA);
676     }
677   }
678 
679   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
680     AddBoolean(Method->isConst());
681     AddBoolean(Method->isVolatile());
682   }
683 
684   ID.AddInteger(Function->getStorageClass());
685   AddBoolean(Function->isInlineSpecified());
686   AddBoolean(Function->isVirtualAsWritten());
687   AddBoolean(Function->isPure());
688   AddBoolean(Function->isDeletedAsWritten());
689   AddBoolean(Function->isExplicitlyDefaulted());
690 
691   AddDecl(Function);
692 
693   AddQualType(Function->getReturnType());
694 
695   ID.AddInteger(Function->param_size());
696   for (auto *Param : Function->parameters())
697     AddSubDecl(Param);
698 
699   if (SkipBody) {
700     AddBoolean(false);
701     return;
702   }
703 
704   const bool HasBody = Function->isThisDeclarationADefinition() &&
705                        !Function->isDefaulted() && !Function->isDeleted() &&
706                        !Function->isLateTemplateParsed();
707   AddBoolean(HasBody);
708   if (!HasBody) {
709     return;
710   }
711 
712   auto *Body = Function->getBody();
713   AddBoolean(Body);
714   if (Body)
715     AddStmt(Body);
716 
717   // Filter out sub-Decls which will not be processed in order to get an
718   // accurate count of Decl's.
719   llvm::SmallVector<const Decl *, 16> Decls;
720   for (Decl *SubDecl : Function->decls()) {
721     if (isSubDeclToBeProcessed(SubDecl, Function)) {
722       Decls.push_back(SubDecl);
723     }
724   }
725 
726   ID.AddInteger(Decls.size());
727   for (auto SubDecl : Decls) {
728     AddSubDecl(SubDecl);
729   }
730 }
731 
732 void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
733   assert(Enum);
734   AddDeclarationName(Enum->getDeclName());
735 
736   AddBoolean(Enum->isScoped());
737   if (Enum->isScoped())
738     AddBoolean(Enum->isScopedUsingClassTag());
739 
740   if (Enum->getIntegerTypeSourceInfo())
741     AddQualType(Enum->getIntegerType());
742 
743   // Filter out sub-Decls which will not be processed in order to get an
744   // accurate count of Decl's.
745   llvm::SmallVector<const Decl *, 16> Decls;
746   for (Decl *SubDecl : Enum->decls()) {
747     if (isSubDeclToBeProcessed(SubDecl, Enum)) {
748       assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
749       Decls.push_back(SubDecl);
750     }
751   }
752 
753   ID.AddInteger(Decls.size());
754   for (auto SubDecl : Decls) {
755     AddSubDecl(SubDecl);
756   }
757 
758 }
759 
760 void ODRHash::AddObjCProtocolDecl(const ObjCProtocolDecl *P) {
761   AddDecl(P);
762 
763   // Hash referenced protocols.
764   ID.AddInteger(P->getReferencedProtocols().size());
765   for (const ObjCProtocolDecl *RefP : P->protocols()) {
766     // Hash the name only as a referenced protocol can be a forward declaration.
767     AddDeclarationName(RefP->getDeclName());
768   }
769 
770   // Filter out sub-Decls which will not be processed in order to get an
771   // accurate count of Decl's.
772   llvm::SmallVector<const Decl *, 16> Decls;
773   for (Decl *SubDecl : P->decls()) {
774     if (isSubDeclToBeProcessed(SubDecl, P)) {
775       Decls.push_back(SubDecl);
776     }
777   }
778 
779   ID.AddInteger(Decls.size());
780   for (auto *SubDecl : Decls) {
781     AddSubDecl(SubDecl);
782   }
783 }
784 
785 void ODRHash::AddDecl(const Decl *D) {
786   assert(D && "Expecting non-null pointer.");
787   D = D->getCanonicalDecl();
788 
789   const NamedDecl *ND = dyn_cast<NamedDecl>(D);
790   AddBoolean(ND);
791   if (!ND) {
792     ID.AddInteger(D->getKind());
793     return;
794   }
795 
796   AddDeclarationName(ND->getDeclName());
797 
798   const auto *Specialization =
799             dyn_cast<ClassTemplateSpecializationDecl>(D);
800   AddBoolean(Specialization);
801   if (Specialization) {
802     const TemplateArgumentList &List = Specialization->getTemplateArgs();
803     ID.AddInteger(List.size());
804     for (const TemplateArgument &TA : List.asArray())
805       AddTemplateArgument(TA);
806   }
807 }
808 
809 namespace {
810 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
811 // methods process the relevant parts of the Type.
812 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
813   typedef TypeVisitor<ODRTypeVisitor> Inherited;
814   llvm::FoldingSetNodeID &ID;
815   ODRHash &Hash;
816 
817 public:
818   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
819       : ID(ID), Hash(Hash) {}
820 
821   void AddStmt(Stmt *S) {
822     Hash.AddBoolean(S);
823     if (S) {
824       Hash.AddStmt(S);
825     }
826   }
827 
828   void AddDecl(const Decl *D) {
829     Hash.AddBoolean(D);
830     if (D) {
831       Hash.AddDecl(D);
832     }
833   }
834 
835   void AddQualType(QualType T) {
836     Hash.AddQualType(T);
837   }
838 
839   void AddType(const Type *T) {
840     Hash.AddBoolean(T);
841     if (T) {
842       Hash.AddType(T);
843     }
844   }
845 
846   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
847     Hash.AddBoolean(NNS);
848     if (NNS) {
849       Hash.AddNestedNameSpecifier(NNS);
850     }
851   }
852 
853   void AddIdentifierInfo(const IdentifierInfo *II) {
854     Hash.AddBoolean(II);
855     if (II) {
856       Hash.AddIdentifierInfo(II);
857     }
858   }
859 
860   void VisitQualifiers(Qualifiers Quals) {
861     ID.AddInteger(Quals.getAsOpaqueValue());
862   }
863 
864   // Return the RecordType if the typedef only strips away a keyword.
865   // Otherwise, return the original type.
866   static const Type *RemoveTypedef(const Type *T) {
867     const auto *TypedefT = dyn_cast<TypedefType>(T);
868     if (!TypedefT) {
869       return T;
870     }
871 
872     const TypedefNameDecl *D = TypedefT->getDecl();
873     QualType UnderlyingType = D->getUnderlyingType();
874 
875     if (UnderlyingType.hasLocalQualifiers()) {
876       return T;
877     }
878 
879     const auto *ElaboratedT = dyn_cast<ElaboratedType>(UnderlyingType);
880     if (!ElaboratedT) {
881       return T;
882     }
883 
884     if (ElaboratedT->getQualifier() != nullptr) {
885       return T;
886     }
887 
888     QualType NamedType = ElaboratedT->getNamedType();
889     if (NamedType.hasLocalQualifiers()) {
890       return T;
891     }
892 
893     const auto *RecordT = dyn_cast<RecordType>(NamedType);
894     if (!RecordT) {
895       return T;
896     }
897 
898     const IdentifierInfo *TypedefII = TypedefT->getDecl()->getIdentifier();
899     const IdentifierInfo *RecordII = RecordT->getDecl()->getIdentifier();
900     if (!TypedefII || !RecordII ||
901         TypedefII->getName() != RecordII->getName()) {
902       return T;
903     }
904 
905     return RecordT;
906   }
907 
908   void Visit(const Type *T) {
909     T = RemoveTypedef(T);
910     ID.AddInteger(T->getTypeClass());
911     Inherited::Visit(T);
912   }
913 
914   void VisitType(const Type *T) {}
915 
916   void VisitAdjustedType(const AdjustedType *T) {
917     QualType Original = T->getOriginalType();
918     QualType Adjusted = T->getAdjustedType();
919 
920     // The original type and pointee type can be the same, as in the case of
921     // function pointers decaying to themselves.  Set a bool and only process
922     // the type once, to prevent doubling the work.
923     SplitQualType split = Adjusted.split();
924     if (auto Pointer = dyn_cast<PointerType>(split.Ty)) {
925       if (Pointer->getPointeeType() == Original) {
926         Hash.AddBoolean(true);
927         ID.AddInteger(split.Quals.getAsOpaqueValue());
928         AddQualType(Original);
929         VisitType(T);
930         return;
931       }
932     }
933 
934     // The original type and pointee type are different, such as in the case
935     // of a array decaying to an element pointer.  Set a bool to false and
936     // process both types.
937     Hash.AddBoolean(false);
938     AddQualType(Original);
939     AddQualType(Adjusted);
940 
941     VisitType(T);
942   }
943 
944   void VisitDecayedType(const DecayedType *T) {
945     // getDecayedType and getPointeeType are derived from getAdjustedType
946     // and don't need to be separately processed.
947     VisitAdjustedType(T);
948   }
949 
950   void VisitArrayType(const ArrayType *T) {
951     AddQualType(T->getElementType());
952     ID.AddInteger(T->getSizeModifier());
953     VisitQualifiers(T->getIndexTypeQualifiers());
954     VisitType(T);
955   }
956   void VisitConstantArrayType(const ConstantArrayType *T) {
957     T->getSize().Profile(ID);
958     VisitArrayType(T);
959   }
960 
961   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
962     AddStmt(T->getSizeExpr());
963     VisitArrayType(T);
964   }
965 
966   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
967     VisitArrayType(T);
968   }
969 
970   void VisitVariableArrayType(const VariableArrayType *T) {
971     AddStmt(T->getSizeExpr());
972     VisitArrayType(T);
973   }
974 
975   void VisitAttributedType(const AttributedType *T) {
976     ID.AddInteger(T->getAttrKind());
977     AddQualType(T->getModifiedType());
978     AddQualType(T->getEquivalentType());
979 
980     VisitType(T);
981   }
982 
983   void VisitBlockPointerType(const BlockPointerType *T) {
984     AddQualType(T->getPointeeType());
985     VisitType(T);
986   }
987 
988   void VisitBuiltinType(const BuiltinType *T) {
989     ID.AddInteger(T->getKind());
990     VisitType(T);
991   }
992 
993   void VisitComplexType(const ComplexType *T) {
994     AddQualType(T->getElementType());
995     VisitType(T);
996   }
997 
998   void VisitDecltypeType(const DecltypeType *T) {
999     AddStmt(T->getUnderlyingExpr());
1000     AddQualType(T->getUnderlyingType());
1001     VisitType(T);
1002   }
1003 
1004   void VisitDependentDecltypeType(const DependentDecltypeType *T) {
1005     VisitDecltypeType(T);
1006   }
1007 
1008   void VisitDeducedType(const DeducedType *T) {
1009     AddQualType(T->getDeducedType());
1010     VisitType(T);
1011   }
1012 
1013   void VisitAutoType(const AutoType *T) {
1014     ID.AddInteger((unsigned)T->getKeyword());
1015     ID.AddInteger(T->isConstrained());
1016     if (T->isConstrained()) {
1017       AddDecl(T->getTypeConstraintConcept());
1018       ID.AddInteger(T->getTypeConstraintArguments().size());
1019       for (const auto &TA : T->getTypeConstraintArguments())
1020         Hash.AddTemplateArgument(TA);
1021     }
1022     VisitDeducedType(T);
1023   }
1024 
1025   void VisitDeducedTemplateSpecializationType(
1026       const DeducedTemplateSpecializationType *T) {
1027     Hash.AddTemplateName(T->getTemplateName());
1028     VisitDeducedType(T);
1029   }
1030 
1031   void VisitDependentAddressSpaceType(const DependentAddressSpaceType *T) {
1032     AddQualType(T->getPointeeType());
1033     AddStmt(T->getAddrSpaceExpr());
1034     VisitType(T);
1035   }
1036 
1037   void VisitDependentSizedExtVectorType(const DependentSizedExtVectorType *T) {
1038     AddQualType(T->getElementType());
1039     AddStmt(T->getSizeExpr());
1040     VisitType(T);
1041   }
1042 
1043   void VisitFunctionType(const FunctionType *T) {
1044     AddQualType(T->getReturnType());
1045     T->getExtInfo().Profile(ID);
1046     Hash.AddBoolean(T->isConst());
1047     Hash.AddBoolean(T->isVolatile());
1048     Hash.AddBoolean(T->isRestrict());
1049     VisitType(T);
1050   }
1051 
1052   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
1053     VisitFunctionType(T);
1054   }
1055 
1056   void VisitFunctionProtoType(const FunctionProtoType *T) {
1057     ID.AddInteger(T->getNumParams());
1058     for (auto ParamType : T->getParamTypes())
1059       AddQualType(ParamType);
1060 
1061     VisitFunctionType(T);
1062   }
1063 
1064   void VisitInjectedClassNameType(const InjectedClassNameType *T) {
1065     AddDecl(T->getDecl());
1066     VisitType(T);
1067   }
1068 
1069   void VisitMemberPointerType(const MemberPointerType *T) {
1070     AddQualType(T->getPointeeType());
1071     AddType(T->getClass());
1072     VisitType(T);
1073   }
1074 
1075   void VisitObjCObjectPointerType(const ObjCObjectPointerType *T) {
1076     AddQualType(T->getPointeeType());
1077     VisitType(T);
1078   }
1079 
1080   void VisitObjCObjectType(const ObjCObjectType *T) {
1081     AddDecl(T->getInterface());
1082 
1083     auto TypeArgs = T->getTypeArgsAsWritten();
1084     ID.AddInteger(TypeArgs.size());
1085     for (auto Arg : TypeArgs) {
1086       AddQualType(Arg);
1087     }
1088 
1089     auto Protocols = T->getProtocols();
1090     ID.AddInteger(Protocols.size());
1091     for (auto *Protocol : Protocols) {
1092       AddDecl(Protocol);
1093     }
1094 
1095     Hash.AddBoolean(T->isKindOfType());
1096 
1097     VisitType(T);
1098   }
1099 
1100   void VisitObjCInterfaceType(const ObjCInterfaceType *T) {
1101     // This type is handled by the parent type ObjCObjectType.
1102     VisitObjCObjectType(T);
1103   }
1104 
1105   void VisitObjCTypeParamType(const ObjCTypeParamType *T) {
1106     AddDecl(T->getDecl());
1107     auto Protocols = T->getProtocols();
1108     ID.AddInteger(Protocols.size());
1109     for (auto *Protocol : Protocols) {
1110       AddDecl(Protocol);
1111     }
1112 
1113     VisitType(T);
1114   }
1115 
1116   void VisitPackExpansionType(const PackExpansionType *T) {
1117     AddQualType(T->getPattern());
1118     VisitType(T);
1119   }
1120 
1121   void VisitParenType(const ParenType *T) {
1122     AddQualType(T->getInnerType());
1123     VisitType(T);
1124   }
1125 
1126   void VisitPipeType(const PipeType *T) {
1127     AddQualType(T->getElementType());
1128     Hash.AddBoolean(T->isReadOnly());
1129     VisitType(T);
1130   }
1131 
1132   void VisitPointerType(const PointerType *T) {
1133     AddQualType(T->getPointeeType());
1134     VisitType(T);
1135   }
1136 
1137   void VisitReferenceType(const ReferenceType *T) {
1138     AddQualType(T->getPointeeTypeAsWritten());
1139     VisitType(T);
1140   }
1141 
1142   void VisitLValueReferenceType(const LValueReferenceType *T) {
1143     VisitReferenceType(T);
1144   }
1145 
1146   void VisitRValueReferenceType(const RValueReferenceType *T) {
1147     VisitReferenceType(T);
1148   }
1149 
1150   void
1151   VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {
1152     AddDecl(T->getAssociatedDecl());
1153     Hash.AddTemplateArgument(T->getArgumentPack());
1154     VisitType(T);
1155   }
1156 
1157   void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
1158     AddDecl(T->getAssociatedDecl());
1159     AddQualType(T->getReplacementType());
1160     VisitType(T);
1161   }
1162 
1163   void VisitTagType(const TagType *T) {
1164     AddDecl(T->getDecl());
1165     VisitType(T);
1166   }
1167 
1168   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
1169   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
1170 
1171   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
1172     ID.AddInteger(T->template_arguments().size());
1173     for (const auto &TA : T->template_arguments()) {
1174       Hash.AddTemplateArgument(TA);
1175     }
1176     Hash.AddTemplateName(T->getTemplateName());
1177     VisitType(T);
1178   }
1179 
1180   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
1181     ID.AddInteger(T->getDepth());
1182     ID.AddInteger(T->getIndex());
1183     Hash.AddBoolean(T->isParameterPack());
1184     AddDecl(T->getDecl());
1185   }
1186 
1187   void VisitTypedefType(const TypedefType *T) {
1188     AddDecl(T->getDecl());
1189     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
1190     VisitQualifiers(UnderlyingType.getQualifiers());
1191     while (true) {
1192       if (const TypedefType *Underlying =
1193               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
1194         UnderlyingType = Underlying->getDecl()->getUnderlyingType();
1195         continue;
1196       }
1197       if (const ElaboratedType *Underlying =
1198               dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
1199         UnderlyingType = Underlying->getNamedType();
1200         continue;
1201       }
1202 
1203       break;
1204     }
1205     AddType(UnderlyingType.getTypePtr());
1206     VisitType(T);
1207   }
1208 
1209   void VisitTypeOfExprType(const TypeOfExprType *T) {
1210     AddStmt(T->getUnderlyingExpr());
1211     Hash.AddBoolean(T->isSugared());
1212     if (T->isSugared())
1213       AddQualType(T->desugar());
1214 
1215     VisitType(T);
1216   }
1217   void VisitTypeOfType(const TypeOfType *T) {
1218     AddQualType(T->getUnmodifiedType());
1219     VisitType(T);
1220   }
1221 
1222   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
1223     ID.AddInteger(T->getKeyword());
1224     VisitType(T);
1225   };
1226 
1227   void VisitDependentNameType(const DependentNameType *T) {
1228     AddNestedNameSpecifier(T->getQualifier());
1229     AddIdentifierInfo(T->getIdentifier());
1230     VisitTypeWithKeyword(T);
1231   }
1232 
1233   void VisitDependentTemplateSpecializationType(
1234       const DependentTemplateSpecializationType *T) {
1235     AddIdentifierInfo(T->getIdentifier());
1236     AddNestedNameSpecifier(T->getQualifier());
1237     ID.AddInteger(T->template_arguments().size());
1238     for (const auto &TA : T->template_arguments()) {
1239       Hash.AddTemplateArgument(TA);
1240     }
1241     VisitTypeWithKeyword(T);
1242   }
1243 
1244   void VisitElaboratedType(const ElaboratedType *T) {
1245     AddNestedNameSpecifier(T->getQualifier());
1246     AddQualType(T->getNamedType());
1247     VisitTypeWithKeyword(T);
1248   }
1249 
1250   void VisitUnaryTransformType(const UnaryTransformType *T) {
1251     AddQualType(T->getUnderlyingType());
1252     AddQualType(T->getBaseType());
1253     VisitType(T);
1254   }
1255 
1256   void VisitUnresolvedUsingType(const UnresolvedUsingType *T) {
1257     AddDecl(T->getDecl());
1258     VisitType(T);
1259   }
1260 
1261   void VisitVectorType(const VectorType *T) {
1262     AddQualType(T->getElementType());
1263     ID.AddInteger(T->getNumElements());
1264     ID.AddInteger(T->getVectorKind());
1265     VisitType(T);
1266   }
1267 
1268   void VisitExtVectorType(const ExtVectorType * T) {
1269     VisitVectorType(T);
1270   }
1271 };
1272 } // namespace
1273 
1274 void ODRHash::AddType(const Type *T) {
1275   assert(T && "Expecting non-null pointer.");
1276   ODRTypeVisitor(ID, *this).Visit(T);
1277 }
1278 
1279 void ODRHash::AddQualType(QualType T) {
1280   AddBoolean(T.isNull());
1281   if (T.isNull())
1282     return;
1283   SplitQualType split = T.split();
1284   ID.AddInteger(split.Quals.getAsOpaqueValue());
1285   AddType(split.Ty);
1286 }
1287 
1288 void ODRHash::AddBoolean(bool Value) {
1289   Bools.push_back(Value);
1290 }
1291