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