Home | History | Annotate | Line # | Download | only in AST 
      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::isDeclToBeProcessed(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 (isDeclToBeProcessed(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 (isDeclToBeProcessed(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 (isDeclToBeProcessed(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