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   Bools.clear();
184   ID.clear();
185 }
186 
187 unsigned ODRHash::CalculateHash() {
188   // Append the bools to the end of the data segment backwards.  This allows
189   // for the bools data to be compressed 32 times smaller compared to using
190   // ID.AddBoolean
191   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
192   const unsigned size = Bools.size();
193   const unsigned remainder = size % unsigned_bits;
194   const unsigned loops = size / unsigned_bits;
195   auto I = Bools.rbegin();
196   unsigned value = 0;
197   for (unsigned i = 0; i < remainder; ++i) {
198     value <<= 1;
199     value |= *I;
200     ++I;
201   }
202   ID.AddInteger(value);
203 
204   for (unsigned i = 0; i < loops; ++i) {
205     value = 0;
206     for (unsigned j = 0; j < unsigned_bits; ++j) {
207       value <<= 1;
208       value |= *I;
209       ++I;
210     }
211     ID.AddInteger(value);
212   }
213 
214   assert(I == Bools.rend());
215   Bools.clear();
216   return ID.ComputeHash();
217 }
218 
219 namespace {
220 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
221 // methods process the relevant parts of the Decl.
222 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
223   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
224   llvm::FoldingSetNodeID &ID;
225   ODRHash &Hash;
226 
227 public:
228   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
229       : ID(ID), Hash(Hash) {}
230 
231   void AddStmt(const Stmt *S) {
232     Hash.AddBoolean(S);
233     if (S) {
234       Hash.AddStmt(S);
235     }
236   }
237 
238   void AddIdentifierInfo(const IdentifierInfo *II) {
239     Hash.AddBoolean(II);
240     if (II) {
241       Hash.AddIdentifierInfo(II);
242     }
243   }
244 
245   void AddQualType(QualType T) {
246     Hash.AddQualType(T);
247   }
248 
249   void AddDecl(const Decl *D) {
250     Hash.AddBoolean(D);
251     if (D) {
252       Hash.AddDecl(D);
253     }
254   }
255 
256   void AddTemplateArgument(TemplateArgument TA) {
257     Hash.AddTemplateArgument(TA);
258   }
259 
260   void Visit(const Decl *D) {
261     ID.AddInteger(D->getKind());
262     Inherited::Visit(D);
263   }
264 
265   void VisitNamedDecl(const NamedDecl *D) {
266     Hash.AddDeclarationName(D->getDeclName());
267     Inherited::VisitNamedDecl(D);
268   }
269 
270   void VisitValueDecl(const ValueDecl *D) {
271     if (!isa<FunctionDecl>(D)) {
272       AddQualType(D->getType());
273     }
274     Inherited::VisitValueDecl(D);
275   }
276 
277   void VisitVarDecl(const VarDecl *D) {
278     Hash.AddBoolean(D->isStaticLocal());
279     Hash.AddBoolean(D->isConstexpr());
280     const bool HasInit = D->hasInit();
281     Hash.AddBoolean(HasInit);
282     if (HasInit) {
283       AddStmt(D->getInit());
284     }
285     Inherited::VisitVarDecl(D);
286   }
287 
288   void VisitParmVarDecl(const ParmVarDecl *D) {
289     // TODO: Handle default arguments.
290     Inherited::VisitParmVarDecl(D);
291   }
292 
293   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
294     ID.AddInteger(D->getAccess());
295     Inherited::VisitAccessSpecDecl(D);
296   }
297 
298   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
299     AddStmt(D->getAssertExpr());
300     AddStmt(D->getMessage());
301 
302     Inherited::VisitStaticAssertDecl(D);
303   }
304 
305   void VisitFieldDecl(const FieldDecl *D) {
306     const bool IsBitfield = D->isBitField();
307     Hash.AddBoolean(IsBitfield);
308 
309     if (IsBitfield) {
310       AddStmt(D->getBitWidth());
311     }
312 
313     Hash.AddBoolean(D->isMutable());
314     AddStmt(D->getInClassInitializer());
315 
316     Inherited::VisitFieldDecl(D);
317   }
318 
319   void VisitFunctionDecl(const FunctionDecl *D) {
320     // Handled by the ODRHash for FunctionDecl
321     ID.AddInteger(D->getODRHash());
322 
323     Inherited::VisitFunctionDecl(D);
324   }
325 
326   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
327     // Handled by the ODRHash for FunctionDecl
328 
329     Inherited::VisitCXXMethodDecl(D);
330   }
331 
332   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
333     AddQualType(D->getUnderlyingType());
334 
335     Inherited::VisitTypedefNameDecl(D);
336   }
337 
338   void VisitTypedefDecl(const TypedefDecl *D) {
339     Inherited::VisitTypedefDecl(D);
340   }
341 
342   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
343     Inherited::VisitTypeAliasDecl(D);
344   }
345 
346   void VisitFriendDecl(const FriendDecl *D) {
347     TypeSourceInfo *TSI = D->getFriendType();
348     Hash.AddBoolean(TSI);
349     if (TSI) {
350       AddQualType(TSI->getType());
351     } else {
352       AddDecl(D->getFriendDecl());
353     }
354   }
355 
356   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
357     // Only care about default arguments as part of the definition.
358     const bool hasDefaultArgument =
359         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
360     Hash.AddBoolean(hasDefaultArgument);
361     if (hasDefaultArgument) {
362       AddTemplateArgument(D->getDefaultArgument());
363     }
364     Hash.AddBoolean(D->isParameterPack());
365 
366     Inherited::VisitTemplateTypeParmDecl(D);
367   }
368 
369   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
370     // Only care about default arguments as part of the definition.
371     const bool hasDefaultArgument =
372         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
373     Hash.AddBoolean(hasDefaultArgument);
374     if (hasDefaultArgument) {
375       AddStmt(D->getDefaultArgument());
376     }
377     Hash.AddBoolean(D->isParameterPack());
378 
379     Inherited::VisitNonTypeTemplateParmDecl(D);
380   }
381 
382   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
383     // Only care about default arguments as part of the definition.
384     const bool hasDefaultArgument =
385         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
386     Hash.AddBoolean(hasDefaultArgument);
387     if (hasDefaultArgument) {
388       AddTemplateArgument(D->getDefaultArgument().getArgument());
389     }
390     Hash.AddBoolean(D->isParameterPack());
391 
392     Inherited::VisitTemplateTemplateParmDecl(D);
393   }
394 
395   void VisitTemplateDecl(const TemplateDecl *D) {
396     Hash.AddTemplateParameterList(D->getTemplateParameters());
397 
398     Inherited::VisitTemplateDecl(D);
399   }
400 
401   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
402     Hash.AddBoolean(D->isMemberSpecialization());
403     Inherited::VisitRedeclarableTemplateDecl(D);
404   }
405 
406   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
407     AddDecl(D->getTemplatedDecl());
408     Inherited::VisitFunctionTemplateDecl(D);
409   }
410 };
411 } // namespace
412 
413 // Only allow a small portion of Decl's to be processed.  Remove this once
414 // all Decl's can be handled.
415 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
416   if (D->isImplicit()) return false;
417   if (D->getDeclContext() != Parent) return false;
418 
419   switch (D->getKind()) {
420     default:
421       return false;
422     case Decl::AccessSpec:
423     case Decl::CXXConstructor:
424     case Decl::CXXDestructor:
425     case Decl::CXXMethod:
426     case Decl::Field:
427     case Decl::Friend:
428     case Decl::FunctionTemplate:
429     case Decl::StaticAssert:
430     case Decl::TypeAlias:
431     case Decl::Typedef:
432     case Decl::Var:
433       return true;
434   }
435 }
436 
437 void ODRHash::AddSubDecl(const Decl *D) {
438   assert(D && "Expecting non-null pointer.");
439 
440   ODRDeclVisitor(ID, *this).Visit(D);
441 }
442 
443 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
444   assert(Record && Record->hasDefinition() &&
445          "Expected non-null record to be a definition.");
446 
447   const DeclContext *DC = Record;
448   while (DC) {
449     if (isa<ClassTemplateSpecializationDecl>(DC)) {
450       return;
451     }
452     DC = DC->getParent();
453   }
454 
455   AddDecl(Record);
456 
457   // Filter out sub-Decls which will not be processed in order to get an
458   // accurate count of Decl's.
459   llvm::SmallVector<const Decl *, 16> Decls;
460   for (Decl *SubDecl : Record->decls()) {
461     if (isWhitelistedDecl(SubDecl, Record)) {
462       Decls.push_back(SubDecl);
463       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
464         // Compute/Preload ODRHash into FunctionDecl.
465         Function->getODRHash();
466       }
467     }
468   }
469 
470   ID.AddInteger(Decls.size());
471   for (auto SubDecl : Decls) {
472     AddSubDecl(SubDecl);
473   }
474 
475   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
476   AddBoolean(TD);
477   if (TD) {
478     AddTemplateParameterList(TD->getTemplateParameters());
479   }
480 
481   ID.AddInteger(Record->getNumBases());
482   auto Bases = Record->bases();
483   for (auto Base : Bases) {
484     AddQualType(Base.getType());
485     ID.AddInteger(Base.isVirtual());
486     ID.AddInteger(Base.getAccessSpecifierAsWritten());
487   }
488 }
489 
490 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
491                               bool SkipBody) {
492   assert(Function && "Expecting non-null pointer.");
493 
494   // Skip functions that are specializations or in specialization context.
495   const DeclContext *DC = Function;
496   while (DC) {
497     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
498     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
499       if (F->isFunctionTemplateSpecialization()) {
500         if (!isa<CXXMethodDecl>(DC)) return;
501         if (DC->getLexicalParent()->isFileContext()) return;
502         // Inline method specializations are the only supported
503         // specialization for now.
504       }
505     }
506     DC = DC->getParent();
507   }
508 
509   ID.AddInteger(Function->getDeclKind());
510 
511   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
512   AddBoolean(SpecializationArgs);
513   if (SpecializationArgs) {
514     ID.AddInteger(SpecializationArgs->size());
515     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
516       AddTemplateArgument(TA);
517     }
518   }
519 
520   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
521     AddBoolean(Method->isConst());
522     AddBoolean(Method->isVolatile());
523   }
524 
525   ID.AddInteger(Function->getStorageClass());
526   AddBoolean(Function->isInlineSpecified());
527   AddBoolean(Function->isVirtualAsWritten());
528   AddBoolean(Function->isPure());
529   AddBoolean(Function->isDeletedAsWritten());
530   AddBoolean(Function->isExplicitlyDefaulted());
531 
532   AddDecl(Function);
533 
534   AddQualType(Function->getReturnType());
535 
536   ID.AddInteger(Function->param_size());
537   for (auto Param : Function->parameters())
538     AddSubDecl(Param);
539 
540   if (SkipBody) {
541     AddBoolean(false);
542     return;
543   }
544 
545   const bool HasBody = Function->isThisDeclarationADefinition() &&
546                        !Function->isDefaulted() && !Function->isDeleted() &&
547                        !Function->isLateTemplateParsed();
548   AddBoolean(HasBody);
549   if (HasBody) {
550     auto *Body = Function->getBody();
551     AddBoolean(Body);
552     if (Body)
553       AddStmt(Body);
554   }
555 }
556 
557 void ODRHash::AddDecl(const Decl *D) {
558   assert(D && "Expecting non-null pointer.");
559   D = D->getCanonicalDecl();
560 
561   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
562     AddDeclarationName(ND->getDeclName());
563     return;
564   }
565 
566   ID.AddInteger(D->getKind());
567   // TODO: Handle non-NamedDecl here.
568 }
569 
570 namespace {
571 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
572 // methods process the relevant parts of the Type.
573 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
574   typedef TypeVisitor<ODRTypeVisitor> Inherited;
575   llvm::FoldingSetNodeID &ID;
576   ODRHash &Hash;
577 
578 public:
579   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
580       : ID(ID), Hash(Hash) {}
581 
582   void AddStmt(Stmt *S) {
583     Hash.AddBoolean(S);
584     if (S) {
585       Hash.AddStmt(S);
586     }
587   }
588 
589   void AddDecl(Decl *D) {
590     Hash.AddBoolean(D);
591     if (D) {
592       Hash.AddDecl(D);
593     }
594   }
595 
596   void AddQualType(QualType T) {
597     Hash.AddQualType(T);
598   }
599 
600   void AddType(const Type *T) {
601     Hash.AddBoolean(T);
602     if (T) {
603       Hash.AddType(T);
604     }
605   }
606 
607   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
608     Hash.AddBoolean(NNS);
609     if (NNS) {
610       Hash.AddNestedNameSpecifier(NNS);
611     }
612   }
613 
614   void AddIdentifierInfo(const IdentifierInfo *II) {
615     Hash.AddBoolean(II);
616     if (II) {
617       Hash.AddIdentifierInfo(II);
618     }
619   }
620 
621   void VisitQualifiers(Qualifiers Quals) {
622     ID.AddInteger(Quals.getAsOpaqueValue());
623   }
624 
625   void Visit(const Type *T) {
626     ID.AddInteger(T->getTypeClass());
627     Inherited::Visit(T);
628   }
629 
630   void VisitType(const Type *T) {}
631 
632   void VisitAdjustedType(const AdjustedType *T) {
633     AddQualType(T->getOriginalType());
634     AddQualType(T->getAdjustedType());
635     VisitType(T);
636   }
637 
638   void VisitDecayedType(const DecayedType *T) {
639     AddQualType(T->getDecayedType());
640     AddQualType(T->getPointeeType());
641     VisitAdjustedType(T);
642   }
643 
644   void VisitArrayType(const ArrayType *T) {
645     AddQualType(T->getElementType());
646     ID.AddInteger(T->getSizeModifier());
647     VisitQualifiers(T->getIndexTypeQualifiers());
648     VisitType(T);
649   }
650   void VisitConstantArrayType(const ConstantArrayType *T) {
651     T->getSize().Profile(ID);
652     VisitArrayType(T);
653   }
654 
655   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
656     AddStmt(T->getSizeExpr());
657     VisitArrayType(T);
658   }
659 
660   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
661     VisitArrayType(T);
662   }
663 
664   void VisitVariableArrayType(const VariableArrayType *T) {
665     AddStmt(T->getSizeExpr());
666     VisitArrayType(T);
667   }
668 
669   void VisitBuiltinType(const BuiltinType *T) {
670     ID.AddInteger(T->getKind());
671     VisitType(T);
672   }
673 
674   void VisitFunctionType(const FunctionType *T) {
675     AddQualType(T->getReturnType());
676     T->getExtInfo().Profile(ID);
677     Hash.AddBoolean(T->isConst());
678     Hash.AddBoolean(T->isVolatile());
679     Hash.AddBoolean(T->isRestrict());
680     VisitType(T);
681   }
682 
683   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
684     VisitFunctionType(T);
685   }
686 
687   void VisitFunctionProtoType(const FunctionProtoType *T) {
688     ID.AddInteger(T->getNumParams());
689     for (auto ParamType : T->getParamTypes())
690       AddQualType(ParamType);
691 
692     VisitFunctionType(T);
693   }
694 
695   void VisitPointerType(const PointerType *T) {
696     AddQualType(T->getPointeeType());
697     VisitType(T);
698   }
699 
700   void VisitReferenceType(const ReferenceType *T) {
701     AddQualType(T->getPointeeTypeAsWritten());
702     VisitType(T);
703   }
704 
705   void VisitLValueReferenceType(const LValueReferenceType *T) {
706     VisitReferenceType(T);
707   }
708 
709   void VisitRValueReferenceType(const RValueReferenceType *T) {
710     VisitReferenceType(T);
711   }
712 
713   void VisitTypedefType(const TypedefType *T) {
714     AddDecl(T->getDecl());
715     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
716     VisitQualifiers(UnderlyingType.getQualifiers());
717     while (true) {
718       if (const TypedefType *Underlying =
719               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
720         UnderlyingType = Underlying->getDecl()->getUnderlyingType();
721         continue;
722       }
723       if (const ElaboratedType *Underlying =
724               dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
725         UnderlyingType = Underlying->getNamedType();
726         continue;
727       }
728 
729       break;
730     }
731     AddType(UnderlyingType.getTypePtr());
732     VisitType(T);
733   }
734 
735   void VisitTagType(const TagType *T) {
736     AddDecl(T->getDecl());
737     VisitType(T);
738   }
739 
740   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
741   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
742 
743   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
744     ID.AddInteger(T->getKeyword());
745     VisitType(T);
746   };
747 
748   void VisitDependentNameType(const DependentNameType *T) {
749     AddNestedNameSpecifier(T->getQualifier());
750     AddIdentifierInfo(T->getIdentifier());
751     VisitTypeWithKeyword(T);
752   }
753 
754   void VisitDependentTemplateSpecializationType(
755       const DependentTemplateSpecializationType *T) {
756     AddIdentifierInfo(T->getIdentifier());
757     AddNestedNameSpecifier(T->getQualifier());
758     ID.AddInteger(T->getNumArgs());
759     for (const auto &TA : T->template_arguments()) {
760       Hash.AddTemplateArgument(TA);
761     }
762     VisitTypeWithKeyword(T);
763   }
764 
765   void VisitElaboratedType(const ElaboratedType *T) {
766     AddNestedNameSpecifier(T->getQualifier());
767     AddQualType(T->getNamedType());
768     VisitTypeWithKeyword(T);
769   }
770 
771   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
772     ID.AddInteger(T->getNumArgs());
773     for (const auto &TA : T->template_arguments()) {
774       Hash.AddTemplateArgument(TA);
775     }
776     Hash.AddTemplateName(T->getTemplateName());
777     VisitType(T);
778   }
779 
780   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
781     ID.AddInteger(T->getDepth());
782     ID.AddInteger(T->getIndex());
783     Hash.AddBoolean(T->isParameterPack());
784     AddDecl(T->getDecl());
785   }
786 };
787 } // namespace
788 
789 void ODRHash::AddType(const Type *T) {
790   assert(T && "Expecting non-null pointer.");
791   ODRTypeVisitor(ID, *this).Visit(T);
792 }
793 
794 void ODRHash::AddQualType(QualType T) {
795   AddBoolean(T.isNull());
796   if (T.isNull())
797     return;
798   SplitQualType split = T.split();
799   ID.AddInteger(split.Quals.getAsOpaqueValue());
800   AddType(split.Ty);
801 }
802 
803 void ODRHash::AddBoolean(bool Value) {
804   Bools.push_back(Value);
805 }
806