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   void VisitEnumConstantDecl(const EnumConstantDecl *D) {
412     AddStmt(D->getInitExpr());
413     Inherited::VisitEnumConstantDecl(D);
414   }
415 };
416 } // namespace
417 
418 // Only allow a small portion of Decl's to be processed.  Remove this once
419 // all Decl's can be handled.
420 bool ODRHash::isWhitelistedDecl(const Decl *D, const DeclContext *Parent) {
421   if (D->isImplicit()) return false;
422   if (D->getDeclContext() != Parent) return false;
423 
424   switch (D->getKind()) {
425     default:
426       return false;
427     case Decl::AccessSpec:
428     case Decl::CXXConstructor:
429     case Decl::CXXDestructor:
430     case Decl::CXXMethod:
431     case Decl::EnumConstant: // Only found in EnumDecl's.
432     case Decl::Field:
433     case Decl::Friend:
434     case Decl::FunctionTemplate:
435     case Decl::StaticAssert:
436     case Decl::TypeAlias:
437     case Decl::Typedef:
438     case Decl::Var:
439       return true;
440   }
441 }
442 
443 void ODRHash::AddSubDecl(const Decl *D) {
444   assert(D && "Expecting non-null pointer.");
445 
446   ODRDeclVisitor(ID, *this).Visit(D);
447 }
448 
449 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
450   assert(Record && Record->hasDefinition() &&
451          "Expected non-null record to be a definition.");
452 
453   const DeclContext *DC = Record;
454   while (DC) {
455     if (isa<ClassTemplateSpecializationDecl>(DC)) {
456       return;
457     }
458     DC = DC->getParent();
459   }
460 
461   AddDecl(Record);
462 
463   // Filter out sub-Decls which will not be processed in order to get an
464   // accurate count of Decl's.
465   llvm::SmallVector<const Decl *, 16> Decls;
466   for (Decl *SubDecl : Record->decls()) {
467     if (isWhitelistedDecl(SubDecl, Record)) {
468       Decls.push_back(SubDecl);
469       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
470         // Compute/Preload ODRHash into FunctionDecl.
471         Function->getODRHash();
472       }
473     }
474   }
475 
476   ID.AddInteger(Decls.size());
477   for (auto SubDecl : Decls) {
478     AddSubDecl(SubDecl);
479   }
480 
481   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
482   AddBoolean(TD);
483   if (TD) {
484     AddTemplateParameterList(TD->getTemplateParameters());
485   }
486 
487   ID.AddInteger(Record->getNumBases());
488   auto Bases = Record->bases();
489   for (auto Base : Bases) {
490     AddQualType(Base.getType());
491     ID.AddInteger(Base.isVirtual());
492     ID.AddInteger(Base.getAccessSpecifierAsWritten());
493   }
494 }
495 
496 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
497                               bool SkipBody) {
498   assert(Function && "Expecting non-null pointer.");
499 
500   // Skip functions that are specializations or in specialization context.
501   const DeclContext *DC = Function;
502   while (DC) {
503     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
504     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
505       if (F->isFunctionTemplateSpecialization()) {
506         if (!isa<CXXMethodDecl>(DC)) return;
507         if (DC->getLexicalParent()->isFileContext()) return;
508         // Inline method specializations are the only supported
509         // specialization for now.
510       }
511     }
512     DC = DC->getParent();
513   }
514 
515   ID.AddInteger(Function->getDeclKind());
516 
517   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
518   AddBoolean(SpecializationArgs);
519   if (SpecializationArgs) {
520     ID.AddInteger(SpecializationArgs->size());
521     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
522       AddTemplateArgument(TA);
523     }
524   }
525 
526   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
527     AddBoolean(Method->isConst());
528     AddBoolean(Method->isVolatile());
529   }
530 
531   ID.AddInteger(Function->getStorageClass());
532   AddBoolean(Function->isInlineSpecified());
533   AddBoolean(Function->isVirtualAsWritten());
534   AddBoolean(Function->isPure());
535   AddBoolean(Function->isDeletedAsWritten());
536   AddBoolean(Function->isExplicitlyDefaulted());
537 
538   AddDecl(Function);
539 
540   AddQualType(Function->getReturnType());
541 
542   ID.AddInteger(Function->param_size());
543   for (auto Param : Function->parameters())
544     AddSubDecl(Param);
545 
546   if (SkipBody) {
547     AddBoolean(false);
548     return;
549   }
550 
551   const bool HasBody = Function->isThisDeclarationADefinition() &&
552                        !Function->isDefaulted() && !Function->isDeleted() &&
553                        !Function->isLateTemplateParsed();
554   AddBoolean(HasBody);
555   if (HasBody) {
556     auto *Body = Function->getBody();
557     AddBoolean(Body);
558     if (Body)
559       AddStmt(Body);
560   }
561 }
562 
563 void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
564   assert(Enum);
565   AddDeclarationName(Enum->getDeclName());
566 
567   AddBoolean(Enum->isScoped());
568   if (Enum->isScoped())
569     AddBoolean(Enum->isScopedUsingClassTag());
570 
571   if (Enum->getIntegerTypeSourceInfo())
572     AddQualType(Enum->getIntegerType());
573 
574   // Filter out sub-Decls which will not be processed in order to get an
575   // accurate count of Decl's.
576   llvm::SmallVector<const Decl *, 16> Decls;
577   for (Decl *SubDecl : Enum->decls()) {
578     if (isWhitelistedDecl(SubDecl, Enum)) {
579       assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
580       Decls.push_back(SubDecl);
581     }
582   }
583 
584   ID.AddInteger(Decls.size());
585   for (auto SubDecl : Decls) {
586     AddSubDecl(SubDecl);
587   }
588 
589 }
590 
591 void ODRHash::AddDecl(const Decl *D) {
592   assert(D && "Expecting non-null pointer.");
593   D = D->getCanonicalDecl();
594 
595   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
596     AddDeclarationName(ND->getDeclName());
597     return;
598   }
599 
600   ID.AddInteger(D->getKind());
601   // TODO: Handle non-NamedDecl here.
602 }
603 
604 namespace {
605 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
606 // methods process the relevant parts of the Type.
607 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
608   typedef TypeVisitor<ODRTypeVisitor> Inherited;
609   llvm::FoldingSetNodeID &ID;
610   ODRHash &Hash;
611 
612 public:
613   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
614       : ID(ID), Hash(Hash) {}
615 
616   void AddStmt(Stmt *S) {
617     Hash.AddBoolean(S);
618     if (S) {
619       Hash.AddStmt(S);
620     }
621   }
622 
623   void AddDecl(Decl *D) {
624     Hash.AddBoolean(D);
625     if (D) {
626       Hash.AddDecl(D);
627     }
628   }
629 
630   void AddQualType(QualType T) {
631     Hash.AddQualType(T);
632   }
633 
634   void AddType(const Type *T) {
635     Hash.AddBoolean(T);
636     if (T) {
637       Hash.AddType(T);
638     }
639   }
640 
641   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
642     Hash.AddBoolean(NNS);
643     if (NNS) {
644       Hash.AddNestedNameSpecifier(NNS);
645     }
646   }
647 
648   void AddIdentifierInfo(const IdentifierInfo *II) {
649     Hash.AddBoolean(II);
650     if (II) {
651       Hash.AddIdentifierInfo(II);
652     }
653   }
654 
655   void VisitQualifiers(Qualifiers Quals) {
656     ID.AddInteger(Quals.getAsOpaqueValue());
657   }
658 
659   void Visit(const Type *T) {
660     ID.AddInteger(T->getTypeClass());
661     Inherited::Visit(T);
662   }
663 
664   void VisitType(const Type *T) {}
665 
666   void VisitAdjustedType(const AdjustedType *T) {
667     AddQualType(T->getOriginalType());
668     AddQualType(T->getAdjustedType());
669     VisitType(T);
670   }
671 
672   void VisitDecayedType(const DecayedType *T) {
673     AddQualType(T->getDecayedType());
674     AddQualType(T->getPointeeType());
675     VisitAdjustedType(T);
676   }
677 
678   void VisitArrayType(const ArrayType *T) {
679     AddQualType(T->getElementType());
680     ID.AddInteger(T->getSizeModifier());
681     VisitQualifiers(T->getIndexTypeQualifiers());
682     VisitType(T);
683   }
684   void VisitConstantArrayType(const ConstantArrayType *T) {
685     T->getSize().Profile(ID);
686     VisitArrayType(T);
687   }
688 
689   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
690     AddStmt(T->getSizeExpr());
691     VisitArrayType(T);
692   }
693 
694   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
695     VisitArrayType(T);
696   }
697 
698   void VisitVariableArrayType(const VariableArrayType *T) {
699     AddStmt(T->getSizeExpr());
700     VisitArrayType(T);
701   }
702 
703   void VisitBuiltinType(const BuiltinType *T) {
704     ID.AddInteger(T->getKind());
705     VisitType(T);
706   }
707 
708   void VisitFunctionType(const FunctionType *T) {
709     AddQualType(T->getReturnType());
710     T->getExtInfo().Profile(ID);
711     Hash.AddBoolean(T->isConst());
712     Hash.AddBoolean(T->isVolatile());
713     Hash.AddBoolean(T->isRestrict());
714     VisitType(T);
715   }
716 
717   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
718     VisitFunctionType(T);
719   }
720 
721   void VisitFunctionProtoType(const FunctionProtoType *T) {
722     ID.AddInteger(T->getNumParams());
723     for (auto ParamType : T->getParamTypes())
724       AddQualType(ParamType);
725 
726     VisitFunctionType(T);
727   }
728 
729   void VisitPointerType(const PointerType *T) {
730     AddQualType(T->getPointeeType());
731     VisitType(T);
732   }
733 
734   void VisitReferenceType(const ReferenceType *T) {
735     AddQualType(T->getPointeeTypeAsWritten());
736     VisitType(T);
737   }
738 
739   void VisitLValueReferenceType(const LValueReferenceType *T) {
740     VisitReferenceType(T);
741   }
742 
743   void VisitRValueReferenceType(const RValueReferenceType *T) {
744     VisitReferenceType(T);
745   }
746 
747   void VisitTypedefType(const TypedefType *T) {
748     AddDecl(T->getDecl());
749     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
750     VisitQualifiers(UnderlyingType.getQualifiers());
751     while (true) {
752       if (const TypedefType *Underlying =
753               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
754         UnderlyingType = Underlying->getDecl()->getUnderlyingType();
755         continue;
756       }
757       if (const ElaboratedType *Underlying =
758               dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
759         UnderlyingType = Underlying->getNamedType();
760         continue;
761       }
762 
763       break;
764     }
765     AddType(UnderlyingType.getTypePtr());
766     VisitType(T);
767   }
768 
769   void VisitTagType(const TagType *T) {
770     AddDecl(T->getDecl());
771     VisitType(T);
772   }
773 
774   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
775   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
776 
777   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
778     ID.AddInteger(T->getKeyword());
779     VisitType(T);
780   };
781 
782   void VisitDependentNameType(const DependentNameType *T) {
783     AddNestedNameSpecifier(T->getQualifier());
784     AddIdentifierInfo(T->getIdentifier());
785     VisitTypeWithKeyword(T);
786   }
787 
788   void VisitDependentTemplateSpecializationType(
789       const DependentTemplateSpecializationType *T) {
790     AddIdentifierInfo(T->getIdentifier());
791     AddNestedNameSpecifier(T->getQualifier());
792     ID.AddInteger(T->getNumArgs());
793     for (const auto &TA : T->template_arguments()) {
794       Hash.AddTemplateArgument(TA);
795     }
796     VisitTypeWithKeyword(T);
797   }
798 
799   void VisitElaboratedType(const ElaboratedType *T) {
800     AddNestedNameSpecifier(T->getQualifier());
801     AddQualType(T->getNamedType());
802     VisitTypeWithKeyword(T);
803   }
804 
805   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
806     ID.AddInteger(T->getNumArgs());
807     for (const auto &TA : T->template_arguments()) {
808       Hash.AddTemplateArgument(TA);
809     }
810     Hash.AddTemplateName(T->getTemplateName());
811     VisitType(T);
812   }
813 
814   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
815     ID.AddInteger(T->getDepth());
816     ID.AddInteger(T->getIndex());
817     Hash.AddBoolean(T->isParameterPack());
818     AddDecl(T->getDecl());
819   }
820 };
821 } // namespace
822 
823 void ODRHash::AddType(const Type *T) {
824   assert(T && "Expecting non-null pointer.");
825   ODRTypeVisitor(ID, *this).Visit(T);
826 }
827 
828 void ODRHash::AddQualType(QualType T) {
829   AddBoolean(T.isNull());
830   if (T.isNull())
831     return;
832   SplitQualType split = T.split();
833   ID.AddInteger(split.Quals.getAsOpaqueValue());
834   AddType(split.Ty);
835 }
836 
837 void ODRHash::AddBoolean(bool Value) {
838   Bools.push_back(Value);
839 }
840