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