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