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