1 //===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This file implements the ODRHash class, which calculates a hash based
12 /// on AST nodes, which is stable across different runs.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #include "clang/AST/ODRHash.h"
17 
18 #include "clang/AST/DeclVisitor.h"
19 #include "clang/AST/NestedNameSpecifier.h"
20 #include "clang/AST/StmtVisitor.h"
21 #include "clang/AST/TypeVisitor.h"
22 
23 using namespace clang;
24 
AddStmt(const Stmt * S)25 void ODRHash::AddStmt(const Stmt *S) {
26   assert(S && "Expecting non-null pointer.");
27   S->ProcessODRHash(ID, *this);
28 }
29 
AddIdentifierInfo(const IdentifierInfo * II)30 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
31   assert(II && "Expecting non-null pointer.");
32   ID.AddString(II->getName());
33 }
34 
AddDeclarationName(DeclarationName Name,bool TreatAsDecl)35 void ODRHash::AddDeclarationName(DeclarationName Name, bool TreatAsDecl) {
36   if (TreatAsDecl)
37     // Matches the NamedDecl check in AddDecl
38     AddBoolean(true);
39 
40   AddDeclarationNameImpl(Name);
41 
42   if (TreatAsDecl)
43     // Matches the ClassTemplateSpecializationDecl check in AddDecl
44     AddBoolean(false);
45 }
46 
AddDeclarationNameImpl(DeclarationName Name)47 void ODRHash::AddDeclarationNameImpl(DeclarationName Name) {
48   // Index all DeclarationName and use index numbers to refer to them.
49   auto Result = DeclNameMap.insert(std::make_pair(Name, DeclNameMap.size()));
50   ID.AddInteger(Result.first->second);
51   if (!Result.second) {
52     // If found in map, the DeclarationName has previously been processed.
53     return;
54   }
55 
56   // First time processing each DeclarationName, also process its details.
57   AddBoolean(Name.isEmpty());
58   if (Name.isEmpty())
59     return;
60 
61   auto Kind = Name.getNameKind();
62   ID.AddInteger(Kind);
63   switch (Kind) {
64   case DeclarationName::Identifier:
65     AddIdentifierInfo(Name.getAsIdentifierInfo());
66     break;
67   case DeclarationName::ObjCZeroArgSelector:
68   case DeclarationName::ObjCOneArgSelector:
69   case DeclarationName::ObjCMultiArgSelector: {
70     Selector S = Name.getObjCSelector();
71     AddBoolean(S.isNull());
72     AddBoolean(S.isKeywordSelector());
73     AddBoolean(S.isUnarySelector());
74     unsigned NumArgs = S.getNumArgs();
75     for (unsigned i = 0; i < NumArgs; ++i) {
76       AddIdentifierInfo(S.getIdentifierInfoForSlot(i));
77     }
78     break;
79   }
80   case DeclarationName::CXXConstructorName:
81   case DeclarationName::CXXDestructorName:
82     AddQualType(Name.getCXXNameType());
83     break;
84   case DeclarationName::CXXOperatorName:
85     ID.AddInteger(Name.getCXXOverloadedOperator());
86     break;
87   case DeclarationName::CXXLiteralOperatorName:
88     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
89     break;
90   case DeclarationName::CXXConversionFunctionName:
91     AddQualType(Name.getCXXNameType());
92     break;
93   case DeclarationName::CXXUsingDirective:
94     break;
95   case DeclarationName::CXXDeductionGuideName: {
96     auto *Template = Name.getCXXDeductionGuideTemplate();
97     AddBoolean(Template);
98     if (Template) {
99       AddDecl(Template);
100     }
101   }
102   }
103 }
104 
AddNestedNameSpecifier(const NestedNameSpecifier * NNS)105 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
106   assert(NNS && "Expecting non-null pointer.");
107   const auto *Prefix = NNS->getPrefix();
108   AddBoolean(Prefix);
109   if (Prefix) {
110     AddNestedNameSpecifier(Prefix);
111   }
112   auto Kind = NNS->getKind();
113   ID.AddInteger(Kind);
114   switch (Kind) {
115   case NestedNameSpecifier::Identifier:
116     AddIdentifierInfo(NNS->getAsIdentifier());
117     break;
118   case NestedNameSpecifier::Namespace:
119     AddDecl(NNS->getAsNamespace());
120     break;
121   case NestedNameSpecifier::NamespaceAlias:
122     AddDecl(NNS->getAsNamespaceAlias());
123     break;
124   case NestedNameSpecifier::TypeSpec:
125   case NestedNameSpecifier::TypeSpecWithTemplate:
126     AddType(NNS->getAsType());
127     break;
128   case NestedNameSpecifier::Global:
129   case NestedNameSpecifier::Super:
130     break;
131   }
132 }
133 
AddTemplateName(TemplateName Name)134 void ODRHash::AddTemplateName(TemplateName Name) {
135   auto Kind = Name.getKind();
136   ID.AddInteger(Kind);
137 
138   switch (Kind) {
139   case TemplateName::Template:
140     AddDecl(Name.getAsTemplateDecl());
141     break;
142   // TODO: Support these cases.
143   case TemplateName::OverloadedTemplate:
144   case TemplateName::QualifiedTemplate:
145   case TemplateName::DependentTemplate:
146   case TemplateName::SubstTemplateTemplateParm:
147   case TemplateName::SubstTemplateTemplateParmPack:
148     break;
149   }
150 }
151 
AddTemplateArgument(TemplateArgument TA)152 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
153   const auto Kind = TA.getKind();
154   ID.AddInteger(Kind);
155 
156   switch (Kind) {
157     case TemplateArgument::Null:
158       llvm_unreachable("Expected valid TemplateArgument");
159     case TemplateArgument::Type:
160       AddQualType(TA.getAsType());
161       break;
162     case TemplateArgument::Declaration:
163       AddDecl(TA.getAsDecl());
164       break;
165     case TemplateArgument::NullPtr:
166     case TemplateArgument::Integral:
167       break;
168     case TemplateArgument::Template:
169     case TemplateArgument::TemplateExpansion:
170       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
171       break;
172     case TemplateArgument::Expression:
173       AddStmt(TA.getAsExpr());
174       break;
175     case TemplateArgument::Pack:
176       ID.AddInteger(TA.pack_size());
177       for (auto SubTA : TA.pack_elements()) {
178         AddTemplateArgument(SubTA);
179       }
180       break;
181   }
182 }
183 
AddTemplateParameterList(const TemplateParameterList * TPL)184 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
185   assert(TPL && "Expecting non-null pointer.");
186 
187   ID.AddInteger(TPL->size());
188   for (auto *ND : TPL->asArray()) {
189     AddSubDecl(ND);
190   }
191 }
192 
clear()193 void ODRHash::clear() {
194   DeclNameMap.clear();
195   Bools.clear();
196   ID.clear();
197 }
198 
CalculateHash()199 unsigned ODRHash::CalculateHash() {
200   // Append the bools to the end of the data segment backwards.  This allows
201   // for the bools data to be compressed 32 times smaller compared to using
202   // ID.AddBoolean
203   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
204   const unsigned size = Bools.size();
205   const unsigned remainder = size % unsigned_bits;
206   const unsigned loops = size / unsigned_bits;
207   auto I = Bools.rbegin();
208   unsigned value = 0;
209   for (unsigned i = 0; i < remainder; ++i) {
210     value <<= 1;
211     value |= *I;
212     ++I;
213   }
214   ID.AddInteger(value);
215 
216   for (unsigned i = 0; i < loops; ++i) {
217     value = 0;
218     for (unsigned j = 0; j < unsigned_bits; ++j) {
219       value <<= 1;
220       value |= *I;
221       ++I;
222     }
223     ID.AddInteger(value);
224   }
225 
226   assert(I == Bools.rend());
227   Bools.clear();
228   return ID.ComputeHash();
229 }
230 
231 namespace {
232 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
233 // methods process the relevant parts of the Decl.
234 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
235   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
236   llvm::FoldingSetNodeID &ID;
237   ODRHash &Hash;
238 
239 public:
ODRDeclVisitor(llvm::FoldingSetNodeID & ID,ODRHash & Hash)240   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
241       : ID(ID), Hash(Hash) {}
242 
AddStmt(const Stmt * S)243   void AddStmt(const Stmt *S) {
244     Hash.AddBoolean(S);
245     if (S) {
246       Hash.AddStmt(S);
247     }
248   }
249 
AddIdentifierInfo(const IdentifierInfo * II)250   void AddIdentifierInfo(const IdentifierInfo *II) {
251     Hash.AddBoolean(II);
252     if (II) {
253       Hash.AddIdentifierInfo(II);
254     }
255   }
256 
AddQualType(QualType T)257   void AddQualType(QualType T) {
258     Hash.AddQualType(T);
259   }
260 
AddDecl(const Decl * D)261   void AddDecl(const Decl *D) {
262     Hash.AddBoolean(D);
263     if (D) {
264       Hash.AddDecl(D);
265     }
266   }
267 
AddTemplateArgument(TemplateArgument TA)268   void AddTemplateArgument(TemplateArgument TA) {
269     Hash.AddTemplateArgument(TA);
270   }
271 
Visit(const Decl * D)272   void Visit(const Decl *D) {
273     ID.AddInteger(D->getKind());
274     Inherited::Visit(D);
275   }
276 
VisitNamedDecl(const NamedDecl * D)277   void VisitNamedDecl(const NamedDecl *D) {
278     Hash.AddDeclarationName(D->getDeclName());
279     Inherited::VisitNamedDecl(D);
280   }
281 
VisitValueDecl(const ValueDecl * D)282   void VisitValueDecl(const ValueDecl *D) {
283     if (!isa<FunctionDecl>(D)) {
284       AddQualType(D->getType());
285     }
286     Inherited::VisitValueDecl(D);
287   }
288 
VisitVarDecl(const VarDecl * D)289   void VisitVarDecl(const VarDecl *D) {
290     Hash.AddBoolean(D->isStaticLocal());
291     Hash.AddBoolean(D->isConstexpr());
292     const bool HasInit = D->hasInit();
293     Hash.AddBoolean(HasInit);
294     if (HasInit) {
295       AddStmt(D->getInit());
296     }
297     Inherited::VisitVarDecl(D);
298   }
299 
VisitParmVarDecl(const ParmVarDecl * D)300   void VisitParmVarDecl(const ParmVarDecl *D) {
301     // TODO: Handle default arguments.
302     Inherited::VisitParmVarDecl(D);
303   }
304 
VisitAccessSpecDecl(const AccessSpecDecl * D)305   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
306     ID.AddInteger(D->getAccess());
307     Inherited::VisitAccessSpecDecl(D);
308   }
309 
VisitStaticAssertDecl(const StaticAssertDecl * D)310   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
311     AddStmt(D->getAssertExpr());
312     AddStmt(D->getMessage());
313 
314     Inherited::VisitStaticAssertDecl(D);
315   }
316 
VisitFieldDecl(const FieldDecl * D)317   void VisitFieldDecl(const FieldDecl *D) {
318     const bool IsBitfield = D->isBitField();
319     Hash.AddBoolean(IsBitfield);
320 
321     if (IsBitfield) {
322       AddStmt(D->getBitWidth());
323     }
324 
325     Hash.AddBoolean(D->isMutable());
326     AddStmt(D->getInClassInitializer());
327 
328     Inherited::VisitFieldDecl(D);
329   }
330 
VisitFunctionDecl(const FunctionDecl * D)331   void VisitFunctionDecl(const FunctionDecl *D) {
332     // Handled by the ODRHash for FunctionDecl
333     ID.AddInteger(D->getODRHash());
334 
335     Inherited::VisitFunctionDecl(D);
336   }
337 
VisitCXXMethodDecl(const CXXMethodDecl * D)338   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
339     // Handled by the ODRHash for FunctionDecl
340 
341     Inherited::VisitCXXMethodDecl(D);
342   }
343 
VisitTypedefNameDecl(const TypedefNameDecl * D)344   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
345     AddQualType(D->getUnderlyingType());
346 
347     Inherited::VisitTypedefNameDecl(D);
348   }
349 
VisitTypedefDecl(const TypedefDecl * D)350   void VisitTypedefDecl(const TypedefDecl *D) {
351     Inherited::VisitTypedefDecl(D);
352   }
353 
VisitTypeAliasDecl(const TypeAliasDecl * D)354   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
355     Inherited::VisitTypeAliasDecl(D);
356   }
357 
VisitFriendDecl(const FriendDecl * D)358   void VisitFriendDecl(const FriendDecl *D) {
359     TypeSourceInfo *TSI = D->getFriendType();
360     Hash.AddBoolean(TSI);
361     if (TSI) {
362       AddQualType(TSI->getType());
363     } else {
364       AddDecl(D->getFriendDecl());
365     }
366   }
367 
VisitTemplateTypeParmDecl(const TemplateTypeParmDecl * D)368   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
369     // Only care about default arguments as part of the definition.
370     const bool hasDefaultArgument =
371         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
372     Hash.AddBoolean(hasDefaultArgument);
373     if (hasDefaultArgument) {
374       AddTemplateArgument(D->getDefaultArgument());
375     }
376     Hash.AddBoolean(D->isParameterPack());
377 
378     Inherited::VisitTemplateTypeParmDecl(D);
379   }
380 
VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl * D)381   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
382     // Only care about default arguments as part of the definition.
383     const bool hasDefaultArgument =
384         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
385     Hash.AddBoolean(hasDefaultArgument);
386     if (hasDefaultArgument) {
387       AddStmt(D->getDefaultArgument());
388     }
389     Hash.AddBoolean(D->isParameterPack());
390 
391     Inherited::VisitNonTypeTemplateParmDecl(D);
392   }
393 
VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl * D)394   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
395     // Only care about default arguments as part of the definition.
396     const bool hasDefaultArgument =
397         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
398     Hash.AddBoolean(hasDefaultArgument);
399     if (hasDefaultArgument) {
400       AddTemplateArgument(D->getDefaultArgument().getArgument());
401     }
402     Hash.AddBoolean(D->isParameterPack());
403 
404     Inherited::VisitTemplateTemplateParmDecl(D);
405   }
406 
VisitTemplateDecl(const TemplateDecl * D)407   void VisitTemplateDecl(const TemplateDecl *D) {
408     Hash.AddTemplateParameterList(D->getTemplateParameters());
409 
410     Inherited::VisitTemplateDecl(D);
411   }
412 
VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl * D)413   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
414     Hash.AddBoolean(D->isMemberSpecialization());
415     Inherited::VisitRedeclarableTemplateDecl(D);
416   }
417 
VisitFunctionTemplateDecl(const FunctionTemplateDecl * D)418   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
419     AddDecl(D->getTemplatedDecl());
420     ID.AddInteger(D->getTemplatedDecl()->getODRHash());
421     Inherited::VisitFunctionTemplateDecl(D);
422   }
423 
VisitEnumConstantDecl(const EnumConstantDecl * D)424   void VisitEnumConstantDecl(const EnumConstantDecl *D) {
425     AddStmt(D->getInitExpr());
426     Inherited::VisitEnumConstantDecl(D);
427   }
428 };
429 } // namespace
430 
431 // Only allow a small portion of Decl's to be processed.  Remove this once
432 // all Decl's can be handled.
isWhitelistedDecl(const Decl * D,const DeclContext * Parent)433 bool ODRHash::isWhitelistedDecl(const Decl *D, const DeclContext *Parent) {
434   if (D->isImplicit()) return false;
435   if (D->getDeclContext() != Parent) return false;
436 
437   switch (D->getKind()) {
438     default:
439       return false;
440     case Decl::AccessSpec:
441     case Decl::CXXConstructor:
442     case Decl::CXXDestructor:
443     case Decl::CXXMethod:
444     case Decl::EnumConstant: // Only found in EnumDecl's.
445     case Decl::Field:
446     case Decl::Friend:
447     case Decl::FunctionTemplate:
448     case Decl::StaticAssert:
449     case Decl::TypeAlias:
450     case Decl::Typedef:
451     case Decl::Var:
452       return true;
453   }
454 }
455 
AddSubDecl(const Decl * D)456 void ODRHash::AddSubDecl(const Decl *D) {
457   assert(D && "Expecting non-null pointer.");
458 
459   ODRDeclVisitor(ID, *this).Visit(D);
460 }
461 
AddCXXRecordDecl(const CXXRecordDecl * Record)462 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
463   assert(Record && Record->hasDefinition() &&
464          "Expected non-null record to be a definition.");
465 
466   const DeclContext *DC = Record;
467   while (DC) {
468     if (isa<ClassTemplateSpecializationDecl>(DC)) {
469       return;
470     }
471     DC = DC->getParent();
472   }
473 
474   AddDecl(Record);
475 
476   // Filter out sub-Decls which will not be processed in order to get an
477   // accurate count of Decl's.
478   llvm::SmallVector<const Decl *, 16> Decls;
479   for (Decl *SubDecl : Record->decls()) {
480     if (isWhitelistedDecl(SubDecl, Record)) {
481       Decls.push_back(SubDecl);
482       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
483         // Compute/Preload ODRHash into FunctionDecl.
484         Function->getODRHash();
485       }
486     }
487   }
488 
489   ID.AddInteger(Decls.size());
490   for (auto SubDecl : Decls) {
491     AddSubDecl(SubDecl);
492   }
493 
494   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
495   AddBoolean(TD);
496   if (TD) {
497     AddTemplateParameterList(TD->getTemplateParameters());
498   }
499 
500   ID.AddInteger(Record->getNumBases());
501   auto Bases = Record->bases();
502   for (auto Base : Bases) {
503     AddQualType(Base.getType());
504     ID.AddInteger(Base.isVirtual());
505     ID.AddInteger(Base.getAccessSpecifierAsWritten());
506   }
507 }
508 
AddFunctionDecl(const FunctionDecl * Function,bool SkipBody)509 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
510                               bool SkipBody) {
511   assert(Function && "Expecting non-null pointer.");
512 
513   // Skip functions that are specializations or in specialization context.
514   const DeclContext *DC = Function;
515   while (DC) {
516     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
517     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
518       if (F->isFunctionTemplateSpecialization()) {
519         if (!isa<CXXMethodDecl>(DC)) return;
520         if (DC->getLexicalParent()->isFileContext()) return;
521         // Inline method specializations are the only supported
522         // specialization for now.
523       }
524     }
525     DC = DC->getParent();
526   }
527 
528   ID.AddInteger(Function->getDeclKind());
529 
530   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
531   AddBoolean(SpecializationArgs);
532   if (SpecializationArgs) {
533     ID.AddInteger(SpecializationArgs->size());
534     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
535       AddTemplateArgument(TA);
536     }
537   }
538 
539   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
540     AddBoolean(Method->isConst());
541     AddBoolean(Method->isVolatile());
542   }
543 
544   ID.AddInteger(Function->getStorageClass());
545   AddBoolean(Function->isInlineSpecified());
546   AddBoolean(Function->isVirtualAsWritten());
547   AddBoolean(Function->isPure());
548   AddBoolean(Function->isDeletedAsWritten());
549   AddBoolean(Function->isExplicitlyDefaulted());
550 
551   AddDecl(Function);
552 
553   AddQualType(Function->getReturnType());
554 
555   ID.AddInteger(Function->param_size());
556   for (auto Param : Function->parameters())
557     AddSubDecl(Param);
558 
559   if (SkipBody) {
560     AddBoolean(false);
561     return;
562   }
563 
564   const bool HasBody = Function->isThisDeclarationADefinition() &&
565                        !Function->isDefaulted() && !Function->isDeleted() &&
566                        !Function->isLateTemplateParsed();
567   AddBoolean(HasBody);
568   if (!HasBody) {
569     return;
570   }
571 
572   auto *Body = Function->getBody();
573   AddBoolean(Body);
574   if (Body)
575     AddStmt(Body);
576 
577   // Filter out sub-Decls which will not be processed in order to get an
578   // accurate count of Decl's.
579   llvm::SmallVector<const Decl *, 16> Decls;
580   for (Decl *SubDecl : Function->decls()) {
581     if (isWhitelistedDecl(SubDecl, Function)) {
582       Decls.push_back(SubDecl);
583     }
584   }
585 
586   ID.AddInteger(Decls.size());
587   for (auto SubDecl : Decls) {
588     AddSubDecl(SubDecl);
589   }
590 }
591 
AddEnumDecl(const EnumDecl * Enum)592 void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
593   assert(Enum);
594   AddDeclarationName(Enum->getDeclName());
595 
596   AddBoolean(Enum->isScoped());
597   if (Enum->isScoped())
598     AddBoolean(Enum->isScopedUsingClassTag());
599 
600   if (Enum->getIntegerTypeSourceInfo())
601     AddQualType(Enum->getIntegerType());
602 
603   // Filter out sub-Decls which will not be processed in order to get an
604   // accurate count of Decl's.
605   llvm::SmallVector<const Decl *, 16> Decls;
606   for (Decl *SubDecl : Enum->decls()) {
607     if (isWhitelistedDecl(SubDecl, Enum)) {
608       assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
609       Decls.push_back(SubDecl);
610     }
611   }
612 
613   ID.AddInteger(Decls.size());
614   for (auto SubDecl : Decls) {
615     AddSubDecl(SubDecl);
616   }
617 
618 }
619 
AddDecl(const Decl * D)620 void ODRHash::AddDecl(const Decl *D) {
621   assert(D && "Expecting non-null pointer.");
622   D = D->getCanonicalDecl();
623 
624   const NamedDecl *ND = dyn_cast<NamedDecl>(D);
625   AddBoolean(ND);
626   if (!ND) {
627     ID.AddInteger(D->getKind());
628     return;
629   }
630 
631   AddDeclarationName(ND->getDeclName());
632 
633   const auto *Specialization =
634             dyn_cast<ClassTemplateSpecializationDecl>(D);
635   AddBoolean(Specialization);
636   if (Specialization) {
637     const TemplateArgumentList &List = Specialization->getTemplateArgs();
638     ID.AddInteger(List.size());
639     for (const TemplateArgument &TA : List.asArray())
640       AddTemplateArgument(TA);
641   }
642 }
643 
644 namespace {
645 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
646 // methods process the relevant parts of the Type.
647 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
648   typedef TypeVisitor<ODRTypeVisitor> Inherited;
649   llvm::FoldingSetNodeID &ID;
650   ODRHash &Hash;
651 
652 public:
ODRTypeVisitor(llvm::FoldingSetNodeID & ID,ODRHash & Hash)653   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
654       : ID(ID), Hash(Hash) {}
655 
AddStmt(Stmt * S)656   void AddStmt(Stmt *S) {
657     Hash.AddBoolean(S);
658     if (S) {
659       Hash.AddStmt(S);
660     }
661   }
662 
AddDecl(Decl * D)663   void AddDecl(Decl *D) {
664     Hash.AddBoolean(D);
665     if (D) {
666       Hash.AddDecl(D);
667     }
668   }
669 
AddQualType(QualType T)670   void AddQualType(QualType T) {
671     Hash.AddQualType(T);
672   }
673 
AddType(const Type * T)674   void AddType(const Type *T) {
675     Hash.AddBoolean(T);
676     if (T) {
677       Hash.AddType(T);
678     }
679   }
680 
AddNestedNameSpecifier(const NestedNameSpecifier * NNS)681   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
682     Hash.AddBoolean(NNS);
683     if (NNS) {
684       Hash.AddNestedNameSpecifier(NNS);
685     }
686   }
687 
AddIdentifierInfo(const IdentifierInfo * II)688   void AddIdentifierInfo(const IdentifierInfo *II) {
689     Hash.AddBoolean(II);
690     if (II) {
691       Hash.AddIdentifierInfo(II);
692     }
693   }
694 
VisitQualifiers(Qualifiers Quals)695   void VisitQualifiers(Qualifiers Quals) {
696     ID.AddInteger(Quals.getAsOpaqueValue());
697   }
698 
Visit(const Type * T)699   void Visit(const Type *T) {
700     ID.AddInteger(T->getTypeClass());
701     Inherited::Visit(T);
702   }
703 
VisitType(const Type * T)704   void VisitType(const Type *T) {}
705 
VisitAdjustedType(const AdjustedType * T)706   void VisitAdjustedType(const AdjustedType *T) {
707     AddQualType(T->getOriginalType());
708     AddQualType(T->getAdjustedType());
709     VisitType(T);
710   }
711 
VisitDecayedType(const DecayedType * T)712   void VisitDecayedType(const DecayedType *T) {
713     AddQualType(T->getDecayedType());
714     AddQualType(T->getPointeeType());
715     VisitAdjustedType(T);
716   }
717 
VisitArrayType(const ArrayType * T)718   void VisitArrayType(const ArrayType *T) {
719     AddQualType(T->getElementType());
720     ID.AddInteger(T->getSizeModifier());
721     VisitQualifiers(T->getIndexTypeQualifiers());
722     VisitType(T);
723   }
VisitConstantArrayType(const ConstantArrayType * T)724   void VisitConstantArrayType(const ConstantArrayType *T) {
725     T->getSize().Profile(ID);
726     VisitArrayType(T);
727   }
728 
VisitDependentSizedArrayType(const DependentSizedArrayType * T)729   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
730     AddStmt(T->getSizeExpr());
731     VisitArrayType(T);
732   }
733 
VisitIncompleteArrayType(const IncompleteArrayType * T)734   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
735     VisitArrayType(T);
736   }
737 
VisitVariableArrayType(const VariableArrayType * T)738   void VisitVariableArrayType(const VariableArrayType *T) {
739     AddStmt(T->getSizeExpr());
740     VisitArrayType(T);
741   }
742 
VisitAttributedType(const AttributedType * T)743   void VisitAttributedType(const AttributedType *T) {
744     ID.AddInteger(T->getAttrKind());
745     AddQualType(T->getModifiedType());
746     AddQualType(T->getEquivalentType());
747 
748     VisitType(T);
749   }
750 
VisitBlockPointerType(const BlockPointerType * T)751   void VisitBlockPointerType(const BlockPointerType *T) {
752     AddQualType(T->getPointeeType());
753     VisitType(T);
754   }
755 
VisitBuiltinType(const BuiltinType * T)756   void VisitBuiltinType(const BuiltinType *T) {
757     ID.AddInteger(T->getKind());
758     VisitType(T);
759   }
760 
VisitComplexType(const ComplexType * T)761   void VisitComplexType(const ComplexType *T) {
762     AddQualType(T->getElementType());
763     VisitType(T);
764   }
765 
VisitDecltypeType(const DecltypeType * T)766   void VisitDecltypeType(const DecltypeType *T) {
767     AddStmt(T->getUnderlyingExpr());
768     AddQualType(T->getUnderlyingType());
769     VisitType(T);
770   }
771 
VisitDependentDecltypeType(const DependentDecltypeType * T)772   void VisitDependentDecltypeType(const DependentDecltypeType *T) {
773     VisitDecltypeType(T);
774   }
775 
VisitDeducedType(const DeducedType * T)776   void VisitDeducedType(const DeducedType *T) {
777     AddQualType(T->getDeducedType());
778     VisitType(T);
779   }
780 
VisitAutoType(const AutoType * T)781   void VisitAutoType(const AutoType *T) {
782     ID.AddInteger((unsigned)T->getKeyword());
783     VisitDeducedType(T);
784   }
785 
VisitDeducedTemplateSpecializationType(const DeducedTemplateSpecializationType * T)786   void VisitDeducedTemplateSpecializationType(
787       const DeducedTemplateSpecializationType *T) {
788     Hash.AddTemplateName(T->getTemplateName());
789     VisitDeducedType(T);
790   }
791 
VisitDependentAddressSpaceType(const DependentAddressSpaceType * T)792   void VisitDependentAddressSpaceType(const DependentAddressSpaceType *T) {
793     AddQualType(T->getPointeeType());
794     AddStmt(T->getAddrSpaceExpr());
795     VisitType(T);
796   }
797 
VisitDependentSizedExtVectorType(const DependentSizedExtVectorType * T)798   void VisitDependentSizedExtVectorType(const DependentSizedExtVectorType *T) {
799     AddQualType(T->getElementType());
800     AddStmt(T->getSizeExpr());
801     VisitType(T);
802   }
803 
VisitFunctionType(const FunctionType * T)804   void VisitFunctionType(const FunctionType *T) {
805     AddQualType(T->getReturnType());
806     T->getExtInfo().Profile(ID);
807     Hash.AddBoolean(T->isConst());
808     Hash.AddBoolean(T->isVolatile());
809     Hash.AddBoolean(T->isRestrict());
810     VisitType(T);
811   }
812 
VisitFunctionNoProtoType(const FunctionNoProtoType * T)813   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
814     VisitFunctionType(T);
815   }
816 
VisitFunctionProtoType(const FunctionProtoType * T)817   void VisitFunctionProtoType(const FunctionProtoType *T) {
818     ID.AddInteger(T->getNumParams());
819     for (auto ParamType : T->getParamTypes())
820       AddQualType(ParamType);
821 
822     VisitFunctionType(T);
823   }
824 
VisitInjectedClassNameType(const InjectedClassNameType * T)825   void VisitInjectedClassNameType(const InjectedClassNameType *T) {
826     AddDecl(T->getDecl());
827     VisitType(T);
828   }
829 
VisitMemberPointerType(const MemberPointerType * T)830   void VisitMemberPointerType(const MemberPointerType *T) {
831     AddQualType(T->getPointeeType());
832     AddType(T->getClass());
833     VisitType(T);
834   }
835 
VisitObjCObjectPointerType(const ObjCObjectPointerType * T)836   void VisitObjCObjectPointerType(const ObjCObjectPointerType *T) {
837     AddQualType(T->getPointeeType());
838     VisitType(T);
839   }
840 
VisitObjCObjectType(const ObjCObjectType * T)841   void VisitObjCObjectType(const ObjCObjectType *T) {
842     AddDecl(T->getInterface());
843 
844     auto TypeArgs = T->getTypeArgsAsWritten();
845     ID.AddInteger(TypeArgs.size());
846     for (auto Arg : TypeArgs) {
847       AddQualType(Arg);
848     }
849 
850     auto Protocols = T->getProtocols();
851     ID.AddInteger(Protocols.size());
852     for (auto Protocol : Protocols) {
853       AddDecl(Protocol);
854     }
855 
856     Hash.AddBoolean(T->isKindOfType());
857 
858     VisitType(T);
859   }
860 
VisitObjCInterfaceType(const ObjCInterfaceType * T)861   void VisitObjCInterfaceType(const ObjCInterfaceType *T) {
862     // This type is handled by the parent type ObjCObjectType.
863     VisitObjCObjectType(T);
864   }
865 
VisitObjCTypeParamType(const ObjCTypeParamType * T)866   void VisitObjCTypeParamType(const ObjCTypeParamType *T) {
867     AddDecl(T->getDecl());
868     auto Protocols = T->getProtocols();
869     ID.AddInteger(Protocols.size());
870     for (auto Protocol : Protocols) {
871       AddDecl(Protocol);
872     }
873 
874     VisitType(T);
875   }
876 
VisitPackExpansionType(const PackExpansionType * T)877   void VisitPackExpansionType(const PackExpansionType *T) {
878     AddQualType(T->getPattern());
879     VisitType(T);
880   }
881 
VisitParenType(const ParenType * T)882   void VisitParenType(const ParenType *T) {
883     AddQualType(T->getInnerType());
884     VisitType(T);
885   }
886 
VisitPipeType(const PipeType * T)887   void VisitPipeType(const PipeType *T) {
888     AddQualType(T->getElementType());
889     Hash.AddBoolean(T->isReadOnly());
890     VisitType(T);
891   }
892 
VisitPointerType(const PointerType * T)893   void VisitPointerType(const PointerType *T) {
894     AddQualType(T->getPointeeType());
895     VisitType(T);
896   }
897 
VisitReferenceType(const ReferenceType * T)898   void VisitReferenceType(const ReferenceType *T) {
899     AddQualType(T->getPointeeTypeAsWritten());
900     VisitType(T);
901   }
902 
VisitLValueReferenceType(const LValueReferenceType * T)903   void VisitLValueReferenceType(const LValueReferenceType *T) {
904     VisitReferenceType(T);
905   }
906 
VisitRValueReferenceType(const RValueReferenceType * T)907   void VisitRValueReferenceType(const RValueReferenceType *T) {
908     VisitReferenceType(T);
909   }
910 
911   void
VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType * T)912   VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {
913     AddType(T->getReplacedParameter());
914     Hash.AddTemplateArgument(T->getArgumentPack());
915     VisitType(T);
916   }
917 
VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType * T)918   void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
919     AddType(T->getReplacedParameter());
920     AddQualType(T->getReplacementType());
921     VisitType(T);
922   }
923 
VisitTagType(const TagType * T)924   void VisitTagType(const TagType *T) {
925     AddDecl(T->getDecl());
926     VisitType(T);
927   }
928 
VisitRecordType(const RecordType * T)929   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
VisitEnumType(const EnumType * T)930   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
931 
VisitTemplateSpecializationType(const TemplateSpecializationType * T)932   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
933     ID.AddInteger(T->getNumArgs());
934     for (const auto &TA : T->template_arguments()) {
935       Hash.AddTemplateArgument(TA);
936     }
937     Hash.AddTemplateName(T->getTemplateName());
938     VisitType(T);
939   }
940 
VisitTemplateTypeParmType(const TemplateTypeParmType * T)941   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
942     ID.AddInteger(T->getDepth());
943     ID.AddInteger(T->getIndex());
944     Hash.AddBoolean(T->isParameterPack());
945     AddDecl(T->getDecl());
946   }
947 
VisitTypedefType(const TypedefType * T)948   void VisitTypedefType(const TypedefType *T) {
949     AddDecl(T->getDecl());
950     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
951     VisitQualifiers(UnderlyingType.getQualifiers());
952     while (true) {
953       if (const TypedefType *Underlying =
954               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
955         UnderlyingType = Underlying->getDecl()->getUnderlyingType();
956         continue;
957       }
958       if (const ElaboratedType *Underlying =
959               dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
960         UnderlyingType = Underlying->getNamedType();
961         continue;
962       }
963 
964       break;
965     }
966     AddType(UnderlyingType.getTypePtr());
967     VisitType(T);
968   }
969 
VisitTypeOfExprType(const TypeOfExprType * T)970   void VisitTypeOfExprType(const TypeOfExprType *T) {
971     AddStmt(T->getUnderlyingExpr());
972     Hash.AddBoolean(T->isSugared());
973     if (T->isSugared())
974       AddQualType(T->desugar());
975 
976     VisitType(T);
977   }
VisitTypeOfType(const TypeOfType * T)978   void VisitTypeOfType(const TypeOfType *T) {
979     AddQualType(T->getUnderlyingType());
980     VisitType(T);
981   }
982 
VisitTypeWithKeyword(const TypeWithKeyword * T)983   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
984     ID.AddInteger(T->getKeyword());
985     VisitType(T);
986   };
987 
VisitDependentNameType(const DependentNameType * T)988   void VisitDependentNameType(const DependentNameType *T) {
989     AddNestedNameSpecifier(T->getQualifier());
990     AddIdentifierInfo(T->getIdentifier());
991     VisitTypeWithKeyword(T);
992   }
993 
VisitDependentTemplateSpecializationType(const DependentTemplateSpecializationType * T)994   void VisitDependentTemplateSpecializationType(
995       const DependentTemplateSpecializationType *T) {
996     AddIdentifierInfo(T->getIdentifier());
997     AddNestedNameSpecifier(T->getQualifier());
998     ID.AddInteger(T->getNumArgs());
999     for (const auto &TA : T->template_arguments()) {
1000       Hash.AddTemplateArgument(TA);
1001     }
1002     VisitTypeWithKeyword(T);
1003   }
1004 
VisitElaboratedType(const ElaboratedType * T)1005   void VisitElaboratedType(const ElaboratedType *T) {
1006     AddNestedNameSpecifier(T->getQualifier());
1007     AddQualType(T->getNamedType());
1008     VisitTypeWithKeyword(T);
1009   }
1010 
VisitUnaryTransformType(const UnaryTransformType * T)1011   void VisitUnaryTransformType(const UnaryTransformType *T) {
1012     AddQualType(T->getUnderlyingType());
1013     AddQualType(T->getBaseType());
1014     VisitType(T);
1015   }
1016 
VisitUnresolvedUsingType(const UnresolvedUsingType * T)1017   void VisitUnresolvedUsingType(const UnresolvedUsingType *T) {
1018     AddDecl(T->getDecl());
1019     VisitType(T);
1020   }
1021 
VisitVectorType(const VectorType * T)1022   void VisitVectorType(const VectorType *T) {
1023     AddQualType(T->getElementType());
1024     ID.AddInteger(T->getNumElements());
1025     ID.AddInteger(T->getVectorKind());
1026     VisitType(T);
1027   }
1028 
VisitExtVectorType(const ExtVectorType * T)1029   void VisitExtVectorType(const ExtVectorType * T) {
1030     VisitVectorType(T);
1031   }
1032 };
1033 } // namespace
1034 
AddType(const Type * T)1035 void ODRHash::AddType(const Type *T) {
1036   assert(T && "Expecting non-null pointer.");
1037   ODRTypeVisitor(ID, *this).Visit(T);
1038 }
1039 
AddQualType(QualType T)1040 void ODRHash::AddQualType(QualType T) {
1041   AddBoolean(T.isNull());
1042   if (T.isNull())
1043     return;
1044   SplitQualType split = T.split();
1045   ID.AddInteger(split.Quals.getAsOpaqueValue());
1046   AddType(split.Ty);
1047 }
1048 
AddBoolean(bool Value)1049 void ODRHash::AddBoolean(bool Value) {
1050   Bools.push_back(Value);
1051 }
1052