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