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 
25 void ODRHash::AddStmt(const Stmt *S) {
26   assert(S && "Expecting non-null pointer.");
27   S->ProcessODRHash(ID, *this);
28 }
29 
30 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
31   assert(II && "Expecting non-null pointer.");
32   ID.AddString(II->getName());
33 }
34 
35 void ODRHash::AddDeclarationName(DeclarationName Name) {
36   // Index all DeclarationName and use index numbers to refer to them.
37   auto Result = DeclNameMap.insert(std::make_pair(Name, DeclNameMap.size()));
38   ID.AddInteger(Result.first->second);
39   if (!Result.second) {
40     // If found in map, the the DeclarationName has previously been processed.
41     return;
42   }
43 
44   // First time processing each DeclarationName, also process its details.
45   AddBoolean(Name.isEmpty());
46   if (Name.isEmpty())
47     return;
48 
49   auto Kind = Name.getNameKind();
50   ID.AddInteger(Kind);
51   switch (Kind) {
52   case DeclarationName::Identifier:
53     AddIdentifierInfo(Name.getAsIdentifierInfo());
54     break;
55   case DeclarationName::ObjCZeroArgSelector:
56   case DeclarationName::ObjCOneArgSelector:
57   case DeclarationName::ObjCMultiArgSelector: {
58     Selector S = Name.getObjCSelector();
59     AddBoolean(S.isNull());
60     AddBoolean(S.isKeywordSelector());
61     AddBoolean(S.isUnarySelector());
62     unsigned NumArgs = S.getNumArgs();
63     for (unsigned i = 0; i < NumArgs; ++i) {
64       AddIdentifierInfo(S.getIdentifierInfoForSlot(i));
65     }
66     break;
67   }
68   case DeclarationName::CXXConstructorName:
69   case DeclarationName::CXXDestructorName:
70     AddQualType(Name.getCXXNameType());
71     break;
72   case DeclarationName::CXXOperatorName:
73     ID.AddInteger(Name.getCXXOverloadedOperator());
74     break;
75   case DeclarationName::CXXLiteralOperatorName:
76     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
77     break;
78   case DeclarationName::CXXConversionFunctionName:
79     AddQualType(Name.getCXXNameType());
80     break;
81   case DeclarationName::CXXUsingDirective:
82     break;
83   case DeclarationName::CXXDeductionGuideName: {
84     auto *Template = Name.getCXXDeductionGuideTemplate();
85     AddBoolean(Template);
86     if (Template) {
87       AddDecl(Template);
88     }
89   }
90   }
91 }
92 
93 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
94   assert(NNS && "Expecting non-null pointer.");
95   const auto *Prefix = NNS->getPrefix();
96   AddBoolean(Prefix);
97   if (Prefix) {
98     AddNestedNameSpecifier(Prefix);
99   }
100   auto Kind = NNS->getKind();
101   ID.AddInteger(Kind);
102   switch (Kind) {
103   case NestedNameSpecifier::Identifier:
104     AddIdentifierInfo(NNS->getAsIdentifier());
105     break;
106   case NestedNameSpecifier::Namespace:
107     AddDecl(NNS->getAsNamespace());
108     break;
109   case NestedNameSpecifier::NamespaceAlias:
110     AddDecl(NNS->getAsNamespaceAlias());
111     break;
112   case NestedNameSpecifier::TypeSpec:
113   case NestedNameSpecifier::TypeSpecWithTemplate:
114     AddType(NNS->getAsType());
115     break;
116   case NestedNameSpecifier::Global:
117   case NestedNameSpecifier::Super:
118     break;
119   }
120 }
121 
122 void ODRHash::AddTemplateName(TemplateName Name) {
123   auto Kind = Name.getKind();
124   ID.AddInteger(Kind);
125 
126   switch (Kind) {
127   case TemplateName::Template:
128     AddDecl(Name.getAsTemplateDecl());
129     break;
130   // TODO: Support these cases.
131   case TemplateName::OverloadedTemplate:
132   case TemplateName::QualifiedTemplate:
133   case TemplateName::DependentTemplate:
134   case TemplateName::SubstTemplateTemplateParm:
135   case TemplateName::SubstTemplateTemplateParmPack:
136     break;
137   }
138 }
139 
140 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
141   const auto Kind = TA.getKind();
142   ID.AddInteger(Kind);
143 
144   switch (Kind) {
145     case TemplateArgument::Null:
146       llvm_unreachable("Expected valid TemplateArgument");
147     case TemplateArgument::Type:
148       AddQualType(TA.getAsType());
149       break;
150     case TemplateArgument::Declaration:
151       AddDecl(TA.getAsDecl());
152       break;
153     case TemplateArgument::NullPtr:
154     case TemplateArgument::Integral:
155       break;
156     case TemplateArgument::Template:
157     case TemplateArgument::TemplateExpansion:
158       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
159       break;
160     case TemplateArgument::Expression:
161       AddStmt(TA.getAsExpr());
162       break;
163     case TemplateArgument::Pack:
164       ID.AddInteger(TA.pack_size());
165       for (auto SubTA : TA.pack_elements()) {
166         AddTemplateArgument(SubTA);
167       }
168       break;
169   }
170 }
171 
172 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
173   assert(TPL && "Expecting non-null pointer.");
174 
175   ID.AddInteger(TPL->size());
176   for (auto *ND : TPL->asArray()) {
177     AddSubDecl(ND);
178   }
179 }
180 
181 void ODRHash::clear() {
182   DeclNameMap.clear();
183   TypeMap.clear();
184   Bools.clear();
185   ID.clear();
186 }
187 
188 unsigned ODRHash::CalculateHash() {
189   // Append the bools to the end of the data segment backwards.  This allows
190   // for the bools data to be compressed 32 times smaller compared to using
191   // ID.AddBoolean
192   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
193   const unsigned size = Bools.size();
194   const unsigned remainder = size % unsigned_bits;
195   const unsigned loops = size / unsigned_bits;
196   auto I = Bools.rbegin();
197   unsigned value = 0;
198   for (unsigned i = 0; i < remainder; ++i) {
199     value <<= 1;
200     value |= *I;
201     ++I;
202   }
203   ID.AddInteger(value);
204 
205   for (unsigned i = 0; i < loops; ++i) {
206     value = 0;
207     for (unsigned j = 0; j < unsigned_bits; ++j) {
208       value <<= 1;
209       value |= *I;
210       ++I;
211     }
212     ID.AddInteger(value);
213   }
214 
215   assert(I == Bools.rend());
216   Bools.clear();
217   return ID.ComputeHash();
218 }
219 
220 namespace {
221 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
222 // methods process the relevant parts of the Decl.
223 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
224   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
225   llvm::FoldingSetNodeID &ID;
226   ODRHash &Hash;
227 
228 public:
229   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
230       : ID(ID), Hash(Hash) {}
231 
232   void AddStmt(const Stmt *S) {
233     Hash.AddBoolean(S);
234     if (S) {
235       Hash.AddStmt(S);
236     }
237   }
238 
239   void AddIdentifierInfo(const IdentifierInfo *II) {
240     Hash.AddBoolean(II);
241     if (II) {
242       Hash.AddIdentifierInfo(II);
243     }
244   }
245 
246   void AddQualType(QualType T) {
247     Hash.AddQualType(T);
248   }
249 
250   void AddDecl(const Decl *D) {
251     Hash.AddBoolean(D);
252     if (D) {
253       Hash.AddDecl(D);
254     }
255   }
256 
257   void AddTemplateArgument(TemplateArgument TA) {
258     Hash.AddTemplateArgument(TA);
259   }
260 
261   void Visit(const Decl *D) {
262     ID.AddInteger(D->getKind());
263     Inherited::Visit(D);
264   }
265 
266   void VisitNamedDecl(const NamedDecl *D) {
267     Hash.AddDeclarationName(D->getDeclName());
268     Inherited::VisitNamedDecl(D);
269   }
270 
271   void VisitValueDecl(const ValueDecl *D) {
272     if (!isa<FunctionDecl>(D)) {
273       AddQualType(D->getType());
274     }
275     Inherited::VisitValueDecl(D);
276   }
277 
278   void VisitVarDecl(const VarDecl *D) {
279     Hash.AddBoolean(D->isStaticLocal());
280     Hash.AddBoolean(D->isConstexpr());
281     const bool HasInit = D->hasInit();
282     Hash.AddBoolean(HasInit);
283     if (HasInit) {
284       AddStmt(D->getInit());
285     }
286     Inherited::VisitVarDecl(D);
287   }
288 
289   void VisitParmVarDecl(const ParmVarDecl *D) {
290     // TODO: Handle default arguments.
291     Inherited::VisitParmVarDecl(D);
292   }
293 
294   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
295     ID.AddInteger(D->getAccess());
296     Inherited::VisitAccessSpecDecl(D);
297   }
298 
299   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
300     AddStmt(D->getAssertExpr());
301     AddStmt(D->getMessage());
302 
303     Inherited::VisitStaticAssertDecl(D);
304   }
305 
306   void VisitFieldDecl(const FieldDecl *D) {
307     const bool IsBitfield = D->isBitField();
308     Hash.AddBoolean(IsBitfield);
309 
310     if (IsBitfield) {
311       AddStmt(D->getBitWidth());
312     }
313 
314     Hash.AddBoolean(D->isMutable());
315     AddStmt(D->getInClassInitializer());
316 
317     Inherited::VisitFieldDecl(D);
318   }
319 
320   void VisitFunctionDecl(const FunctionDecl *D) {
321     ID.AddInteger(D->getStorageClass());
322     Hash.AddBoolean(D->isInlineSpecified());
323     Hash.AddBoolean(D->isVirtualAsWritten());
324     Hash.AddBoolean(D->isPure());
325     Hash.AddBoolean(D->isDeletedAsWritten());
326 
327     ID.AddInteger(D->param_size());
328 
329     for (auto *Param : D->parameters()) {
330       Hash.AddSubDecl(Param);
331     }
332 
333     AddQualType(D->getReturnType());
334 
335     const auto* SpecializationArgs = D->getTemplateSpecializationArgs();
336     Hash.AddBoolean(SpecializationArgs);
337     if (SpecializationArgs) {
338       ID.AddInteger(SpecializationArgs->size());
339       for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
340         Hash.AddTemplateArgument(TA);
341       }
342     }
343 
344     Inherited::VisitFunctionDecl(D);
345   }
346 
347   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
348     Hash.AddBoolean(D->isConst());
349     Hash.AddBoolean(D->isVolatile());
350 
351     Inherited::VisitCXXMethodDecl(D);
352   }
353 
354   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
355     AddQualType(D->getUnderlyingType());
356 
357     Inherited::VisitTypedefNameDecl(D);
358   }
359 
360   void VisitTypedefDecl(const TypedefDecl *D) {
361     Inherited::VisitTypedefDecl(D);
362   }
363 
364   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
365     Inherited::VisitTypeAliasDecl(D);
366   }
367 
368   void VisitFriendDecl(const FriendDecl *D) {
369     TypeSourceInfo *TSI = D->getFriendType();
370     Hash.AddBoolean(TSI);
371     if (TSI) {
372       AddQualType(TSI->getType());
373     } else {
374       AddDecl(D->getFriendDecl());
375     }
376   }
377 
378   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
379     // Only care about default arguments as part of the definition.
380     const bool hasDefaultArgument =
381         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
382     Hash.AddBoolean(hasDefaultArgument);
383     if (hasDefaultArgument) {
384       AddTemplateArgument(D->getDefaultArgument());
385     }
386     Hash.AddBoolean(D->isParameterPack());
387 
388     Inherited::VisitTemplateTypeParmDecl(D);
389   }
390 
391   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
392     // Only care about default arguments as part of the definition.
393     const bool hasDefaultArgument =
394         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
395     Hash.AddBoolean(hasDefaultArgument);
396     if (hasDefaultArgument) {
397       AddStmt(D->getDefaultArgument());
398     }
399     Hash.AddBoolean(D->isParameterPack());
400 
401     Inherited::VisitNonTypeTemplateParmDecl(D);
402   }
403 
404   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
405     // Only care about default arguments as part of the definition.
406     const bool hasDefaultArgument =
407         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
408     Hash.AddBoolean(hasDefaultArgument);
409     if (hasDefaultArgument) {
410       AddTemplateArgument(D->getDefaultArgument().getArgument());
411     }
412     Hash.AddBoolean(D->isParameterPack());
413 
414     Inherited::VisitTemplateTemplateParmDecl(D);
415   }
416 
417   void VisitTemplateDecl(const TemplateDecl *D) {
418     Hash.AddTemplateParameterList(D->getTemplateParameters());
419 
420     Inherited::VisitTemplateDecl(D);
421   }
422 
423   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
424     Hash.AddBoolean(D->isMemberSpecialization());
425     Inherited::VisitRedeclarableTemplateDecl(D);
426   }
427 
428   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
429     Visit(D->getTemplatedDecl());
430     AddDecl(D->getTemplatedDecl());
431     Inherited::VisitFunctionTemplateDecl(D);
432   }
433 };
434 } // namespace
435 
436 // Only allow a small portion of Decl's to be processed.  Remove this once
437 // all Decl's can be handled.
438 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
439   if (D->isImplicit()) return false;
440   if (D->getDeclContext() != Parent) return false;
441 
442   switch (D->getKind()) {
443     default:
444       return false;
445     case Decl::AccessSpec:
446     case Decl::CXXConstructor:
447     case Decl::CXXDestructor:
448     case Decl::CXXMethod:
449     case Decl::Field:
450     case Decl::Friend:
451     case Decl::FunctionTemplate:
452     case Decl::StaticAssert:
453     case Decl::TypeAlias:
454     case Decl::Typedef:
455     case Decl::Var:
456       return true;
457   }
458 }
459 
460 void ODRHash::AddSubDecl(const Decl *D) {
461   assert(D && "Expecting non-null pointer.");
462 
463   ODRDeclVisitor(ID, *this).Visit(D);
464 }
465 
466 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
467   assert(Record && Record->hasDefinition() &&
468          "Expected non-null record to be a definition.");
469 
470   const DeclContext *DC = Record;
471   while (DC) {
472     if (isa<ClassTemplateSpecializationDecl>(DC)) {
473       return;
474     }
475     DC = DC->getParent();
476   }
477 
478   AddDecl(Record);
479 
480   // Filter out sub-Decls which will not be processed in order to get an
481   // accurate count of Decl's.
482   llvm::SmallVector<const Decl *, 16> Decls;
483   for (const Decl *SubDecl : Record->decls()) {
484     if (isWhitelistedDecl(SubDecl, Record)) {
485       Decls.push_back(SubDecl);
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 
509 void ODRHash::AddFunctionDecl(const FunctionDecl *Function) {
510   assert(Function && "Expecting non-null pointer.");
511 
512   // Skip hashing these kinds of function.
513   if (Function->isImplicit()) return;
514   if (Function->isDefaulted()) return;
515   if (Function->isDeleted()) return;
516   if (!Function->hasBody()) return;
517   if (!Function->getBody()) return;
518 
519   // Skip functions that are specializations or in specialization context.
520   const DeclContext *DC = Function;
521   while (DC) {
522     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
523     if (auto *F = dyn_cast<FunctionDecl>(DC))
524       if (F->isFunctionTemplateSpecialization()) return;
525     DC = DC->getParent();
526   }
527 
528   AddDecl(Function);
529 
530   AddQualType(Function->getReturnType());
531 
532   ID.AddInteger(Function->param_size());
533   for (auto Param : Function->parameters())
534     AddSubDecl(Param);
535 
536   AddStmt(Function->getBody());
537 }
538 
539 void ODRHash::AddDecl(const Decl *D) {
540   assert(D && "Expecting non-null pointer.");
541   D = D->getCanonicalDecl();
542 
543   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
544     AddDeclarationName(ND->getDeclName());
545     return;
546   }
547 
548   ID.AddInteger(D->getKind());
549   // TODO: Handle non-NamedDecl here.
550 }
551 
552 namespace {
553 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
554 // methods process the relevant parts of the Type.
555 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
556   typedef TypeVisitor<ODRTypeVisitor> Inherited;
557   llvm::FoldingSetNodeID &ID;
558   ODRHash &Hash;
559 
560 public:
561   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
562       : ID(ID), Hash(Hash) {}
563 
564   void AddStmt(Stmt *S) {
565     Hash.AddBoolean(S);
566     if (S) {
567       Hash.AddStmt(S);
568     }
569   }
570 
571   void AddDecl(Decl *D) {
572     Hash.AddBoolean(D);
573     if (D) {
574       Hash.AddDecl(D);
575     }
576   }
577 
578   void AddQualType(QualType T) {
579     Hash.AddQualType(T);
580   }
581 
582   void AddType(const Type *T) {
583     Hash.AddBoolean(T);
584     if (T) {
585       Hash.AddType(T);
586     }
587   }
588 
589   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
590     Hash.AddBoolean(NNS);
591     if (NNS) {
592       Hash.AddNestedNameSpecifier(NNS);
593     }
594   }
595 
596   void AddIdentifierInfo(const IdentifierInfo *II) {
597     Hash.AddBoolean(II);
598     if (II) {
599       Hash.AddIdentifierInfo(II);
600     }
601   }
602 
603   void VisitQualifiers(Qualifiers Quals) {
604     ID.AddInteger(Quals.getAsOpaqueValue());
605   }
606 
607   void Visit(const Type *T) {
608     ID.AddInteger(T->getTypeClass());
609     Inherited::Visit(T);
610   }
611 
612   void VisitType(const Type *T) {}
613 
614   void VisitAdjustedType(const AdjustedType *T) {
615     AddQualType(T->getOriginalType());
616     AddQualType(T->getAdjustedType());
617     VisitType(T);
618   }
619 
620   void VisitDecayedType(const DecayedType *T) {
621     AddQualType(T->getDecayedType());
622     AddQualType(T->getPointeeType());
623     VisitAdjustedType(T);
624   }
625 
626   void VisitArrayType(const ArrayType *T) {
627     AddQualType(T->getElementType());
628     ID.AddInteger(T->getSizeModifier());
629     VisitQualifiers(T->getIndexTypeQualifiers());
630     VisitType(T);
631   }
632   void VisitConstantArrayType(const ConstantArrayType *T) {
633     T->getSize().Profile(ID);
634     VisitArrayType(T);
635   }
636 
637   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
638     AddStmt(T->getSizeExpr());
639     VisitArrayType(T);
640   }
641 
642   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
643     VisitArrayType(T);
644   }
645 
646   void VisitVariableArrayType(const VariableArrayType *T) {
647     AddStmt(T->getSizeExpr());
648     VisitArrayType(T);
649   }
650 
651   void VisitBuiltinType(const BuiltinType *T) {
652     ID.AddInteger(T->getKind());
653     VisitType(T);
654   }
655 
656   void VisitFunctionType(const FunctionType *T) {
657     AddQualType(T->getReturnType());
658     T->getExtInfo().Profile(ID);
659     Hash.AddBoolean(T->isConst());
660     Hash.AddBoolean(T->isVolatile());
661     Hash.AddBoolean(T->isRestrict());
662     VisitType(T);
663   }
664 
665   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
666     VisitFunctionType(T);
667   }
668 
669   void VisitFunctionProtoType(const FunctionProtoType *T) {
670     ID.AddInteger(T->getNumParams());
671     for (auto ParamType : T->getParamTypes())
672       AddQualType(ParamType);
673 
674     VisitFunctionType(T);
675   }
676 
677   void VisitPointerType(const PointerType *T) {
678     AddQualType(T->getPointeeType());
679     VisitType(T);
680   }
681 
682   void VisitReferenceType(const ReferenceType *T) {
683     AddQualType(T->getPointeeTypeAsWritten());
684     VisitType(T);
685   }
686 
687   void VisitLValueReferenceType(const LValueReferenceType *T) {
688     VisitReferenceType(T);
689   }
690 
691   void VisitRValueReferenceType(const RValueReferenceType *T) {
692     VisitReferenceType(T);
693   }
694 
695   void VisitTypedefType(const TypedefType *T) {
696     AddDecl(T->getDecl());
697     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
698     VisitQualifiers(UnderlyingType.getQualifiers());
699     while (true) {
700       if (const TypedefType *Underlying =
701               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
702         UnderlyingType = Underlying->getDecl()->getUnderlyingType();
703         continue;
704       }
705       if (const ElaboratedType *Underlying =
706               dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
707         UnderlyingType = Underlying->getNamedType();
708         continue;
709       }
710 
711       break;
712     }
713     AddType(UnderlyingType.getTypePtr());
714     VisitType(T);
715   }
716 
717   void VisitTagType(const TagType *T) {
718     AddDecl(T->getDecl());
719     VisitType(T);
720   }
721 
722   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
723   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
724 
725   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
726     ID.AddInteger(T->getKeyword());
727     VisitType(T);
728   };
729 
730   void VisitDependentNameType(const DependentNameType *T) {
731     AddNestedNameSpecifier(T->getQualifier());
732     AddIdentifierInfo(T->getIdentifier());
733     VisitTypeWithKeyword(T);
734   }
735 
736   void VisitDependentTemplateSpecializationType(
737       const DependentTemplateSpecializationType *T) {
738     AddIdentifierInfo(T->getIdentifier());
739     AddNestedNameSpecifier(T->getQualifier());
740     ID.AddInteger(T->getNumArgs());
741     for (const auto &TA : T->template_arguments()) {
742       Hash.AddTemplateArgument(TA);
743     }
744     VisitTypeWithKeyword(T);
745   }
746 
747   void VisitElaboratedType(const ElaboratedType *T) {
748     AddNestedNameSpecifier(T->getQualifier());
749     AddQualType(T->getNamedType());
750     VisitTypeWithKeyword(T);
751   }
752 
753   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
754     ID.AddInteger(T->getNumArgs());
755     for (const auto &TA : T->template_arguments()) {
756       Hash.AddTemplateArgument(TA);
757     }
758     Hash.AddTemplateName(T->getTemplateName());
759     VisitType(T);
760   }
761 
762   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
763     ID.AddInteger(T->getDepth());
764     ID.AddInteger(T->getIndex());
765     Hash.AddBoolean(T->isParameterPack());
766     AddDecl(T->getDecl());
767   }
768 };
769 } // namespace
770 
771 void ODRHash::AddType(const Type *T) {
772   assert(T && "Expecting non-null pointer.");
773   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
774   ID.AddInteger(Result.first->second);
775   // On first encounter of a Type pointer, process it.  Every time afterwards,
776   // only the index value is needed.
777   if (!Result.second) {
778     return;
779   }
780 
781   ODRTypeVisitor(ID, *this).Visit(T);
782 }
783 
784 void ODRHash::AddQualType(QualType T) {
785   AddBoolean(T.isNull());
786   if (T.isNull())
787     return;
788   SplitQualType split = T.split();
789   ID.AddInteger(split.Quals.getAsOpaqueValue());
790   AddType(split.Ty);
791 }
792 
793 void ODRHash::AddBoolean(bool Value) {
794   Bools.push_back(Value);
795 }
796