contrib/llvm/tools/clang/lib/AST/ODRHash.cpp

   1 //===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// This file implements the ODRHash class, which calculates a hash based
  12 /// on AST nodes, which is stable across different runs.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "clang/AST/ODRHash.h"
  17
  18 #include "clang/AST/DeclVisitor.h"
  19 #include "clang/AST/NestedNameSpecifier.h"
  20 #include "clang/AST/StmtVisitor.h"
  21 #include "clang/AST/TypeVisitor.h"
  22
  23 using namespace clang;
  24
  25 void ODRHash::AddStmt(const Stmt *S) {
  26   assert(S && "Expecting non-null pointer.");
  27   S->ProcessODRHash(ID, *this);
  28 }
  29
  30 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
  31   assert(II && "Expecting non-null pointer.");
  32   ID.AddString(II->getName());
  33 }
  34
  35 void ODRHash::AddDeclarationName(DeclarationName Name) {
  36   // Index all DeclarationName and use index numbers to refer to them.
  37   auto Result = DeclNameMap.insert(std::make_pair(Name, DeclNameMap.size()));
  38   ID.AddInteger(Result.first->second);
  39   if (!Result.second) {
  40     // If found in map, the the DeclarationName has previously been processed.
  41     return;
  42   }
  43
  44   // First time processing each DeclarationName, also process its details.
  45   AddBoolean(Name.isEmpty());
  46   if (Name.isEmpty())
  47     return;
  48
  49   auto Kind = Name.getNameKind();
  50   ID.AddInteger(Kind);
  51   switch (Kind) {
  52   case DeclarationName::Identifier:
  53     AddIdentifierInfo(Name.getAsIdentifierInfo());
  54     break;
  55   case DeclarationName::ObjCZeroArgSelector:
  56   case DeclarationName::ObjCOneArgSelector:
  57   case DeclarationName::ObjCMultiArgSelector: {
  58     Selector S = Name.getObjCSelector();
  59     AddBoolean(S.isNull());
  60     AddBoolean(S.isKeywordSelector());
  61     AddBoolean(S.isUnarySelector());
  62     unsigned NumArgs = S.getNumArgs();
  63     for (unsigned i = 0; i < NumArgs; ++i) {
  64       AddIdentifierInfo(S.getIdentifierInfoForSlot(i));
  65     }
  66     break;
  67   }
  68   case DeclarationName::CXXConstructorName:
  69   case DeclarationName::CXXDestructorName:
  70     AddQualType(Name.getCXXNameType());
  71     break;
  72   case DeclarationName::CXXOperatorName:
  73     ID.AddInteger(Name.getCXXOverloadedOperator());
  74     break;
  75   case DeclarationName::CXXLiteralOperatorName:
  76     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
  77     break;
  78   case DeclarationName::CXXConversionFunctionName:
  79     AddQualType(Name.getCXXNameType());
  80     break;
  81   case DeclarationName::CXXUsingDirective:
  82     break;
  83   case DeclarationName::CXXDeductionGuideName: {
  84     auto *Template = Name.getCXXDeductionGuideTemplate();
  85     AddBoolean(Template);
  86     if (Template) {
  87       AddDecl(Template);
  88     }
  89   }
  90   }
  91 }
  92
  93 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
  94   assert(NNS && "Expecting non-null pointer.");
  95   const auto *Prefix = NNS->getPrefix();
  96   AddBoolean(Prefix);
  97   if (Prefix) {
  98     AddNestedNameSpecifier(Prefix);
  99   }
 100   auto Kind = NNS->getKind();
 101   ID.AddInteger(Kind);
 102   switch (Kind) {
 103   case NestedNameSpecifier::Identifier:
 104     AddIdentifierInfo(NNS->getAsIdentifier());
 105     break;
 106   case NestedNameSpecifier::Namespace:
 107     AddDecl(NNS->getAsNamespace());
 108     break;
 109   case NestedNameSpecifier::NamespaceAlias:
 110     AddDecl(NNS->getAsNamespaceAlias());
 111     break;
 112   case NestedNameSpecifier::TypeSpec:
 113   case NestedNameSpecifier::TypeSpecWithTemplate:
 114     AddType(NNS->getAsType());
 115     break;
 116   case NestedNameSpecifier::Global:
 117   case NestedNameSpecifier::Super:
 118     break;
 119   }
 120 }
 121
 122 void ODRHash::AddTemplateName(TemplateName Name) {
 123   auto Kind = Name.getKind();
 124   ID.AddInteger(Kind);
 125
 126   switch (Kind) {
 127   case TemplateName::Template:
 128     AddDecl(Name.getAsTemplateDecl());
 129     break;
 130   // TODO: Support these cases.
 131   case TemplateName::OverloadedTemplate:
 132   case TemplateName::QualifiedTemplate:
 133   case TemplateName::DependentTemplate:
 134   case TemplateName::SubstTemplateTemplateParm:
 135   case TemplateName::SubstTemplateTemplateParmPack:
 136     break;
 137   }
 138 }
 139
 140 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
 141   const auto Kind = TA.getKind();
 142   ID.AddInteger(Kind);
 143
 144   switch (Kind) {
 145     case TemplateArgument::Null:
 146       llvm_unreachable("Expected valid TemplateArgument");
 147     case TemplateArgument::Type:
 148       AddQualType(TA.getAsType());
 149       break;
 150     case TemplateArgument::Declaration:
 151       AddDecl(TA.getAsDecl());
 152       break;
 153     case TemplateArgument::NullPtr:
 154     case TemplateArgument::Integral:
 155       break;
 156     case TemplateArgument::Template:
 157     case TemplateArgument::TemplateExpansion:
 158       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
 159       break;
 160     case TemplateArgument::Expression:
 161       AddStmt(TA.getAsExpr());
 162       break;
 163     case TemplateArgument::Pack:
 164       ID.AddInteger(TA.pack_size());
 165       for (auto SubTA : TA.pack_elements()) {
 166         AddTemplateArgument(SubTA);
 167       }
 168       break;
 169   }
 170 }
 171
 172 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
 173   assert(TPL && "Expecting non-null pointer.");
 174
 175   ID.AddInteger(TPL->size());
 176   for (auto *ND : TPL->asArray()) {
 177     AddSubDecl(ND);
 178   }
 179 }
 180
 181 void ODRHash::clear() {
 182   DeclNameMap.clear();
 183   Bools.clear();
 184   ID.clear();
 185 }
 186
 187 unsigned ODRHash::CalculateHash() {
 188   // Append the bools to the end of the data segment backwards.  This allows
 189   // for the bools data to be compressed 32 times smaller compared to using
 190   // ID.AddBoolean
 191   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 192   const unsigned size = Bools.size();
 193   const unsigned remainder = size % unsigned_bits;
 194   const unsigned loops = size / unsigned_bits;
 195   auto I = Bools.rbegin();
 196   unsigned value = 0;
 197   for (unsigned i = 0; i < remainder; ++i) {
 198     value <<= 1;
 199     value |= *I;
 200     ++I;
 201   }
 202   ID.AddInteger(value);
 203
 204   for (unsigned i = 0; i < loops; ++i) {
 205     value = 0;
 206     for (unsigned j = 0; j < unsigned_bits; ++j) {
 207       value <<= 1;
 208       value |= *I;
 209       ++I;
 210     }
 211     ID.AddInteger(value);
 212   }
 213
 214   assert(I == Bools.rend());
 215   Bools.clear();
 216   return ID.ComputeHash();
 217 }
 218
 219 namespace {
 220 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 221 // methods process the relevant parts of the Decl.
 222 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 223   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 224   llvm::FoldingSetNodeID &ID;
 225   ODRHash &Hash;
 226
 227 public:
 228   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 229       : ID(ID), Hash(Hash) {}
 230
 231   void AddStmt(const Stmt *S) {
 232     Hash.AddBoolean(S);
 233     if (S) {
 234       Hash.AddStmt(S);
 235     }
 236   }
 237
 238   void AddIdentifierInfo(const IdentifierInfo *II) {
 239     Hash.AddBoolean(II);
 240     if (II) {
 241       Hash.AddIdentifierInfo(II);
 242     }
 243   }
 244
 245   void AddQualType(QualType T) {
 246     Hash.AddQualType(T);
 247   }
 248
 249   void AddDecl(const Decl *D) {
 250     Hash.AddBoolean(D);
 251     if (D) {
 252       Hash.AddDecl(D);
 253     }
 254   }
 255
 256   void AddTemplateArgument(TemplateArgument TA) {
 257     Hash.AddTemplateArgument(TA);
 258   }
 259
 260   void Visit(const Decl *D) {
 261     ID.AddInteger(D->getKind());
 262     Inherited::Visit(D);
 263   }
 264
 265   void VisitNamedDecl(const NamedDecl *D) {
 266     Hash.AddDeclarationName(D->getDeclName());
 267     Inherited::VisitNamedDecl(D);
 268   }
 269
 270   void VisitValueDecl(const ValueDecl *D) {
 271     if (!isa<FunctionDecl>(D)) {
 272       AddQualType(D->getType());
 273     }
 274     Inherited::VisitValueDecl(D);
 275   }
 276
 277   void VisitVarDecl(const VarDecl *D) {
 278     Hash.AddBoolean(D->isStaticLocal());
 279     Hash.AddBoolean(D->isConstexpr());
 280     const bool HasInit = D->hasInit();
 281     Hash.AddBoolean(HasInit);
 282     if (HasInit) {
 283       AddStmt(D->getInit());
 284     }
 285     Inherited::VisitVarDecl(D);
 286   }
 287
 288   void VisitParmVarDecl(const ParmVarDecl *D) {
 289     // TODO: Handle default arguments.
 290     Inherited::VisitParmVarDecl(D);
 291   }
 292
 293   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 294     ID.AddInteger(D->getAccess());
 295     Inherited::VisitAccessSpecDecl(D);
 296   }
 297
 298   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 299     AddStmt(D->getAssertExpr());
 300     AddStmt(D->getMessage());
 301
 302     Inherited::VisitStaticAssertDecl(D);
 303   }
 304
 305   void VisitFieldDecl(const FieldDecl *D) {
 306     const bool IsBitfield = D->isBitField();
 307     Hash.AddBoolean(IsBitfield);
 308
 309     if (IsBitfield) {
 310       AddStmt(D->getBitWidth());
 311     }
 312
 313     Hash.AddBoolean(D->isMutable());
 314     AddStmt(D->getInClassInitializer());
 315
 316     Inherited::VisitFieldDecl(D);
 317   }
 318
 319   void VisitFunctionDecl(const FunctionDecl *D) {
 320     // Handled by the ODRHash for FunctionDecl
 321     ID.AddInteger(D->getODRHash());
 322
 323     Inherited::VisitFunctionDecl(D);
 324   }
 325
 326   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 327     // Handled by the ODRHash for FunctionDecl
 328
 329     Inherited::VisitCXXMethodDecl(D);
 330   }
 331
 332   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 333     AddQualType(D->getUnderlyingType());
 334
 335     Inherited::VisitTypedefNameDecl(D);
 336   }
 337
 338   void VisitTypedefDecl(const TypedefDecl *D) {
 339     Inherited::VisitTypedefDecl(D);
 340   }
 341
 342   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 343     Inherited::VisitTypeAliasDecl(D);
 344   }
 345
 346   void VisitFriendDecl(const FriendDecl *D) {
 347     TypeSourceInfo *TSI = D->getFriendType();
 348     Hash.AddBoolean(TSI);
 349     if (TSI) {
 350       AddQualType(TSI->getType());
 351     } else {
 352       AddDecl(D->getFriendDecl());
 353     }
 354   }
 355
 356   void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
 357     // Only care about default arguments as part of the definition.
 358     const bool hasDefaultArgument =
 359         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
 360     Hash.AddBoolean(hasDefaultArgument);
 361     if (hasDefaultArgument) {
 362       AddTemplateArgument(D->getDefaultArgument());
 363     }
 364     Hash.AddBoolean(D->isParameterPack());
 365
 366     Inherited::VisitTemplateTypeParmDecl(D);
 367   }
 368
 369   void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
 370     // Only care about default arguments as part of the definition.
 371     const bool hasDefaultArgument =
 372         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
 373     Hash.AddBoolean(hasDefaultArgument);
 374     if (hasDefaultArgument) {
 375       AddStmt(D->getDefaultArgument());
 376     }
 377     Hash.AddBoolean(D->isParameterPack());
 378
 379     Inherited::VisitNonTypeTemplateParmDecl(D);
 380   }
 381
 382   void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
 383     // Only care about default arguments as part of the definition.
 384     const bool hasDefaultArgument =
 385         D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
 386     Hash.AddBoolean(hasDefaultArgument);
 387     if (hasDefaultArgument) {
 388       AddTemplateArgument(D->getDefaultArgument().getArgument());
 389     }
 390     Hash.AddBoolean(D->isParameterPack());
 391
 392     Inherited::VisitTemplateTemplateParmDecl(D);
 393   }
 394
 395   void VisitTemplateDecl(const TemplateDecl *D) {
 396     Hash.AddTemplateParameterList(D->getTemplateParameters());
 397
 398     Inherited::VisitTemplateDecl(D);
 399   }
 400
 401   void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
 402     Hash.AddBoolean(D->isMemberSpecialization());
 403     Inherited::VisitRedeclarableTemplateDecl(D);
 404   }
 405
 406   void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
 407     AddDecl(D->getTemplatedDecl());
 408     Inherited::VisitFunctionTemplateDecl(D);
 409   }
 410
 411   void VisitEnumConstantDecl(const EnumConstantDecl *D) {
 412     AddStmt(D->getInitExpr());
 413     Inherited::VisitEnumConstantDecl(D);
 414   }
 415 };
 416 } // namespace
 417
 418 // Only allow a small portion of Decl's to be processed.  Remove this once
 419 // all Decl's can be handled.
 420 bool ODRHash::isWhitelistedDecl(const Decl *D, const DeclContext *Parent) {
 421   if (D->isImplicit()) return false;
 422   if (D->getDeclContext() != Parent) return false;
 423
 424   switch (D->getKind()) {
 425     default:
 426       return false;
 427     case Decl::AccessSpec:
 428     case Decl::CXXConstructor:
 429     case Decl::CXXDestructor:
 430     case Decl::CXXMethod:
 431     case Decl::EnumConstant: // Only found in EnumDecl's.
 432     case Decl::Field:
 433     case Decl::Friend:
 434     case Decl::FunctionTemplate:
 435     case Decl::StaticAssert:
 436     case Decl::TypeAlias:
 437     case Decl::Typedef:
 438     case Decl::Var:
 439       return true;
 440   }
 441 }
 442
 443 void ODRHash::AddSubDecl(const Decl *D) {
 444   assert(D && "Expecting non-null pointer.");
 445
 446   ODRDeclVisitor(ID, *this).Visit(D);
 447 }
 448
 449 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 450   assert(Record && Record->hasDefinition() &&
 451          "Expected non-null record to be a definition.");
 452
 453   const DeclContext *DC = Record;
 454   while (DC) {
 455     if (isa<ClassTemplateSpecializationDecl>(DC)) {
 456       return;
 457     }
 458     DC = DC->getParent();
 459   }
 460
 461   AddDecl(Record);
 462
 463   // Filter out sub-Decls which will not be processed in order to get an
 464   // accurate count of Decl's.
 465   llvm::SmallVector<const Decl *, 16> Decls;
 466   for (Decl *SubDecl : Record->decls()) {
 467     if (isWhitelistedDecl(SubDecl, Record)) {
 468       Decls.push_back(SubDecl);
 469       if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
 470         // Compute/Preload ODRHash into FunctionDecl.
 471         Function->getODRHash();
 472       }
 473     }
 474   }
 475
 476   ID.AddInteger(Decls.size());
 477   for (auto SubDecl : Decls) {
 478     AddSubDecl(SubDecl);
 479   }
 480
 481   const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
 482   AddBoolean(TD);
 483   if (TD) {
 484     AddTemplateParameterList(TD->getTemplateParameters());
 485   }
 486
 487   ID.AddInteger(Record->getNumBases());
 488   auto Bases = Record->bases();
 489   for (auto Base : Bases) {
 490     AddQualType(Base.getType());
 491     ID.AddInteger(Base.isVirtual());
 492     ID.AddInteger(Base.getAccessSpecifierAsWritten());
 493   }
 494 }
 495
 496 void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
 497                               bool SkipBody) {
 498   assert(Function && "Expecting non-null pointer.");
 499
 500   // Skip functions that are specializations or in specialization context.
 501   const DeclContext *DC = Function;
 502   while (DC) {
 503     if (isa<ClassTemplateSpecializationDecl>(DC)) return;
 504     if (auto *F = dyn_cast<FunctionDecl>(DC)) {
 505       if (F->isFunctionTemplateSpecialization()) {
 506         if (!isa<CXXMethodDecl>(DC)) return;
 507         if (DC->getLexicalParent()->isFileContext()) return;
 508         // Inline method specializations are the only supported
 509         // specialization for now.
 510       }
 511     }
 512     DC = DC->getParent();
 513   }
 514
 515   ID.AddInteger(Function->getDeclKind());
 516
 517   const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
 518   AddBoolean(SpecializationArgs);
 519   if (SpecializationArgs) {
 520     ID.AddInteger(SpecializationArgs->size());
 521     for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
 522       AddTemplateArgument(TA);
 523     }
 524   }
 525
 526   if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
 527     AddBoolean(Method->isConst());
 528     AddBoolean(Method->isVolatile());
 529   }
 530
 531   ID.AddInteger(Function->getStorageClass());
 532   AddBoolean(Function->isInlineSpecified());
 533   AddBoolean(Function->isVirtualAsWritten());
 534   AddBoolean(Function->isPure());
 535   AddBoolean(Function->isDeletedAsWritten());
 536   AddBoolean(Function->isExplicitlyDefaulted());
 537
 538   AddDecl(Function);
 539
 540   AddQualType(Function->getReturnType());
 541
 542   ID.AddInteger(Function->param_size());
 543   for (auto Param : Function->parameters())
 544     AddSubDecl(Param);
 545
 546   if (SkipBody) {
 547     AddBoolean(false);
 548     return;
 549   }
 550
 551   const bool HasBody = Function->isThisDeclarationADefinition() &&
 552                        !Function->isDefaulted() && !Function->isDeleted() &&
 553                        !Function->isLateTemplateParsed();
 554   AddBoolean(HasBody);
 555   if (HasBody) {
 556     auto *Body = Function->getBody();
 557     AddBoolean(Body);
 558     if (Body)
 559       AddStmt(Body);
 560   }
 561 }
 562
 563 void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
 564   assert(Enum);
 565   AddDeclarationName(Enum->getDeclName());
 566
 567   AddBoolean(Enum->isScoped());
 568   if (Enum->isScoped())
 569     AddBoolean(Enum->isScopedUsingClassTag());
 570
 571   if (Enum->getIntegerTypeSourceInfo())
 572     AddQualType(Enum->getIntegerType());
 573
 574   // Filter out sub-Decls which will not be processed in order to get an
 575   // accurate count of Decl's.
 576   llvm::SmallVector<const Decl *, 16> Decls;
 577   for (Decl *SubDecl : Enum->decls()) {
 578     if (isWhitelistedDecl(SubDecl, Enum)) {
 579       assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
 580       Decls.push_back(SubDecl);
 581     }
 582   }
 583
 584   ID.AddInteger(Decls.size());
 585   for (auto SubDecl : Decls) {
 586     AddSubDecl(SubDecl);
 587   }
 588
 589 }
 590
 591 void ODRHash::AddDecl(const Decl *D) {
 592   assert(D && "Expecting non-null pointer.");
 593   D = D->getCanonicalDecl();
 594
 595   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
 596     AddDeclarationName(ND->getDeclName());
 597     return;
 598   }
 599
 600   ID.AddInteger(D->getKind());
 601   // TODO: Handle non-NamedDecl here.
 602 }
 603
 604 namespace {
 605 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 606 // methods process the relevant parts of the Type.
 607 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 608   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 609   llvm::FoldingSetNodeID &ID;
 610   ODRHash &Hash;
 611
 612 public:
 613   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 614       : ID(ID), Hash(Hash) {}
 615
 616   void AddStmt(Stmt *S) {
 617     Hash.AddBoolean(S);
 618     if (S) {
 619       Hash.AddStmt(S);
 620     }
 621   }
 622
 623   void AddDecl(Decl *D) {
 624     Hash.AddBoolean(D);
 625     if (D) {
 626       Hash.AddDecl(D);
 627     }
 628   }
 629
 630   void AddQualType(QualType T) {
 631     Hash.AddQualType(T);
 632   }
 633
 634   void AddType(const Type *T) {
 635     Hash.AddBoolean(T);
 636     if (T) {
 637       Hash.AddType(T);
 638     }
 639   }
 640
 641   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 642     Hash.AddBoolean(NNS);
 643     if (NNS) {
 644       Hash.AddNestedNameSpecifier(NNS);
 645     }
 646   }
 647
 648   void AddIdentifierInfo(const IdentifierInfo *II) {
 649     Hash.AddBoolean(II);
 650     if (II) {
 651       Hash.AddIdentifierInfo(II);
 652     }
 653   }
 654
 655   void VisitQualifiers(Qualifiers Quals) {
 656     ID.AddInteger(Quals.getAsOpaqueValue());
 657   }
 658
 659   void Visit(const Type *T) {
 660     ID.AddInteger(T->getTypeClass());
 661     Inherited::Visit(T);
 662   }
 663
 664   void VisitType(const Type *T) {}
 665
 666   void VisitAdjustedType(const AdjustedType *T) {
 667     AddQualType(T->getOriginalType());
 668     AddQualType(T->getAdjustedType());
 669     VisitType(T);
 670   }
 671
 672   void VisitDecayedType(const DecayedType *T) {
 673     AddQualType(T->getDecayedType());
 674     AddQualType(T->getPointeeType());
 675     VisitAdjustedType(T);
 676   }
 677
 678   void VisitArrayType(const ArrayType *T) {
 679     AddQualType(T->getElementType());
 680     ID.AddInteger(T->getSizeModifier());
 681     VisitQualifiers(T->getIndexTypeQualifiers());
 682     VisitType(T);
 683   }
 684   void VisitConstantArrayType(const ConstantArrayType *T) {
 685     T->getSize().Profile(ID);
 686     VisitArrayType(T);
 687   }
 688
 689   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 690     AddStmt(T->getSizeExpr());
 691     VisitArrayType(T);
 692   }
 693
 694   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 695     VisitArrayType(T);
 696   }
 697
 698   void VisitVariableArrayType(const VariableArrayType *T) {
 699     AddStmt(T->getSizeExpr());
 700     VisitArrayType(T);
 701   }
 702
 703   void VisitBuiltinType(const BuiltinType *T) {
 704     ID.AddInteger(T->getKind());
 705     VisitType(T);
 706   }
 707
 708   void VisitFunctionType(const FunctionType *T) {
 709     AddQualType(T->getReturnType());
 710     T->getExtInfo().Profile(ID);
 711     Hash.AddBoolean(T->isConst());
 712     Hash.AddBoolean(T->isVolatile());
 713     Hash.AddBoolean(T->isRestrict());
 714     VisitType(T);
 715   }
 716
 717   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 718     VisitFunctionType(T);
 719   }
 720
 721   void VisitFunctionProtoType(const FunctionProtoType *T) {
 722     ID.AddInteger(T->getNumParams());
 723     for (auto ParamType : T->getParamTypes())
 724       AddQualType(ParamType);
 725
 726     VisitFunctionType(T);
 727   }
 728
 729   void VisitPointerType(const PointerType *T) {
 730     AddQualType(T->getPointeeType());
 731     VisitType(T);
 732   }
 733
 734   void VisitReferenceType(const ReferenceType *T) {
 735     AddQualType(T->getPointeeTypeAsWritten());
 736     VisitType(T);
 737   }
 738
 739   void VisitLValueReferenceType(const LValueReferenceType *T) {
 740     VisitReferenceType(T);
 741   }
 742
 743   void VisitRValueReferenceType(const RValueReferenceType *T) {
 744     VisitReferenceType(T);
 745   }
 746
 747   void VisitTypedefType(const TypedefType *T) {
 748     AddDecl(T->getDecl());
 749     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
 750     VisitQualifiers(UnderlyingType.getQualifiers());
 751     while (true) {
 752       if (const TypedefType *Underlying =
 753               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
 754         UnderlyingType = Underlying->getDecl()->getUnderlyingType();
 755         continue;
 756       }
 757       if (const ElaboratedType *Underlying =
 758               dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
 759         UnderlyingType = Underlying->getNamedType();
 760         continue;
 761       }
 762
 763       break;
 764     }
 765     AddType(UnderlyingType.getTypePtr());
 766     VisitType(T);
 767   }
 768
 769   void VisitTagType(const TagType *T) {
 770     AddDecl(T->getDecl());
 771     VisitType(T);
 772   }
 773
 774   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
 775   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
 776
 777   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
 778     ID.AddInteger(T->getKeyword());
 779     VisitType(T);
 780   };
 781
 782   void VisitDependentNameType(const DependentNameType *T) {
 783     AddNestedNameSpecifier(T->getQualifier());
 784     AddIdentifierInfo(T->getIdentifier());
 785     VisitTypeWithKeyword(T);
 786   }
 787
 788   void VisitDependentTemplateSpecializationType(
 789       const DependentTemplateSpecializationType *T) {
 790     AddIdentifierInfo(T->getIdentifier());
 791     AddNestedNameSpecifier(T->getQualifier());
 792     ID.AddInteger(T->getNumArgs());
 793     for (const auto &TA : T->template_arguments()) {
 794       Hash.AddTemplateArgument(TA);
 795     }
 796     VisitTypeWithKeyword(T);
 797   }
 798
 799   void VisitElaboratedType(const ElaboratedType *T) {
 800     AddNestedNameSpecifier(T->getQualifier());
 801     AddQualType(T->getNamedType());
 802     VisitTypeWithKeyword(T);
 803   }
 804
 805   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
 806     ID.AddInteger(T->getNumArgs());
 807     for (const auto &TA : T->template_arguments()) {
 808       Hash.AddTemplateArgument(TA);
 809     }
 810     Hash.AddTemplateName(T->getTemplateName());
 811     VisitType(T);
 812   }
 813
 814   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
 815     ID.AddInteger(T->getDepth());
 816     ID.AddInteger(T->getIndex());
 817     Hash.AddBoolean(T->isParameterPack());
 818     AddDecl(T->getDecl());
 819   }
 820 };
 821 } // namespace
 822
 823 void ODRHash::AddType(const Type *T) {
 824   assert(T && "Expecting non-null pointer.");
 825   ODRTypeVisitor(ID, *this).Visit(T);
 826 }
 827
 828 void ODRHash::AddQualType(QualType T) {
 829   AddBoolean(T.isNull());
 830   if (T.isNull())
 831     return;
 832   SplitQualType split = T.split();
 833   ID.AddInteger(split.Quals.getAsOpaqueValue());
 834   AddType(split.Ty);
 835 }
 836
 837 void ODRHash::AddBoolean(bool Value) {
 838   Bools.push_back(Value);
 839 }