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