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   AddBoolean(Name.isEmpty());
  37   if (Name.isEmpty())
  38     return;
  39
  40   auto Kind = Name.getNameKind();
  41   ID.AddInteger(Kind);
  42   switch (Kind) {
  43   case DeclarationName::Identifier:
  44     AddIdentifierInfo(Name.getAsIdentifierInfo());
  45     break;
  46   case DeclarationName::ObjCZeroArgSelector:
  47   case DeclarationName::ObjCOneArgSelector:
  48   case DeclarationName::ObjCMultiArgSelector: {
  49     Selector S = Name.getObjCSelector();
  50     AddBoolean(S.isNull());
  51     AddBoolean(S.isKeywordSelector());
  52     AddBoolean(S.isUnarySelector());
  53     unsigned NumArgs = S.getNumArgs();
  54     for (unsigned i = 0; i < NumArgs; ++i) {
  55       AddIdentifierInfo(S.getIdentifierInfoForSlot(i));
  56     }
  57     break;
  58   }
  59   case DeclarationName::CXXConstructorName:
  60   case DeclarationName::CXXDestructorName:
  61     AddQualType(Name.getCXXNameType());
  62     break;
  63   case DeclarationName::CXXOperatorName:
  64     ID.AddInteger(Name.getCXXOverloadedOperator());
  65     break;
  66   case DeclarationName::CXXLiteralOperatorName:
  67     AddIdentifierInfo(Name.getCXXLiteralIdentifier());
  68     break;
  69   case DeclarationName::CXXConversionFunctionName:
  70     AddQualType(Name.getCXXNameType());
  71     break;
  72   case DeclarationName::CXXUsingDirective:
  73     break;
  74   case DeclarationName::CXXDeductionGuideName: {
  75     auto *Template = Name.getCXXDeductionGuideTemplate();
  76     AddBoolean(Template);
  77     if (Template) {
  78       AddDecl(Template);
  79     }
  80   }
  81   }
  82 }
  83
  84 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
  85   assert(NNS && "Expecting non-null pointer.");
  86   const auto *Prefix = NNS->getPrefix();
  87   AddBoolean(Prefix);
  88   if (Prefix) {
  89     AddNestedNameSpecifier(Prefix);
  90   }
  91   auto Kind = NNS->getKind();
  92   ID.AddInteger(Kind);
  93   switch (Kind) {
  94   case NestedNameSpecifier::Identifier:
  95     AddIdentifierInfo(NNS->getAsIdentifier());
  96     break;
  97   case NestedNameSpecifier::Namespace:
  98     AddDecl(NNS->getAsNamespace());
  99     break;
 100   case NestedNameSpecifier::NamespaceAlias:
 101     AddDecl(NNS->getAsNamespaceAlias());
 102     break;
 103   case NestedNameSpecifier::TypeSpec:
 104   case NestedNameSpecifier::TypeSpecWithTemplate:
 105     AddType(NNS->getAsType());
 106     break;
 107   case NestedNameSpecifier::Global:
 108   case NestedNameSpecifier::Super:
 109     break;
 110   }
 111 }
 112
 113 void ODRHash::AddTemplateName(TemplateName Name) {
 114   auto Kind = Name.getKind();
 115   ID.AddInteger(Kind);
 116
 117   switch (Kind) {
 118   case TemplateName::Template:
 119     AddDecl(Name.getAsTemplateDecl());
 120     break;
 121   // TODO: Support these cases.
 122   case TemplateName::OverloadedTemplate:
 123   case TemplateName::QualifiedTemplate:
 124   case TemplateName::DependentTemplate:
 125   case TemplateName::SubstTemplateTemplateParm:
 126   case TemplateName::SubstTemplateTemplateParmPack:
 127     break;
 128   }
 129 }
 130
 131 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
 132   const auto Kind = TA.getKind();
 133   ID.AddInteger(Kind);
 134
 135   switch (Kind) {
 136     case TemplateArgument::Null:
 137       llvm_unreachable("Expected valid TemplateArgument");
 138     case TemplateArgument::Type:
 139       AddQualType(TA.getAsType());
 140       break;
 141     case TemplateArgument::Declaration:
 142     case TemplateArgument::NullPtr:
 143     case TemplateArgument::Integral:
 144       break;
 145     case TemplateArgument::Template:
 146     case TemplateArgument::TemplateExpansion:
 147       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
 148       break;
 149     case TemplateArgument::Expression:
 150       AddStmt(TA.getAsExpr());
 151       break;
 152     case TemplateArgument::Pack:
 153       ID.AddInteger(TA.pack_size());
 154       for (auto SubTA : TA.pack_elements()) {
 155         AddTemplateArgument(SubTA);
 156       }
 157       break;
 158   }
 159 }
 160
 161 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
 162
 163 void ODRHash::clear() {
 164   DeclMap.clear();
 165   TypeMap.clear();
 166   Bools.clear();
 167   ID.clear();
 168 }
 169
 170 unsigned ODRHash::CalculateHash() {
 171   // Append the bools to the end of the data segment backwards.  This allows
 172   // for the bools data to be compressed 32 times smaller compared to using
 173   // ID.AddBoolean
 174   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 175   const unsigned size = Bools.size();
 176   const unsigned remainder = size % unsigned_bits;
 177   const unsigned loops = size / unsigned_bits;
 178   auto I = Bools.rbegin();
 179   unsigned value = 0;
 180   for (unsigned i = 0; i < remainder; ++i) {
 181     value <<= 1;
 182     value |= *I;
 183     ++I;
 184   }
 185   ID.AddInteger(value);
 186
 187   for (unsigned i = 0; i < loops; ++i) {
 188     value = 0;
 189     for (unsigned j = 0; j < unsigned_bits; ++j) {
 190       value <<= 1;
 191       value |= *I;
 192       ++I;
 193     }
 194     ID.AddInteger(value);
 195   }
 196
 197   assert(I == Bools.rend());
 198   Bools.clear();
 199   return ID.ComputeHash();
 200 }
 201
 202 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 203 // methods process the relevant parts of the Decl.
 204 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 205   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 206   llvm::FoldingSetNodeID &ID;
 207   ODRHash &Hash;
 208
 209 public:
 210   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 211       : ID(ID), Hash(Hash) {}
 212
 213   void AddStmt(const Stmt *S) {
 214     Hash.AddBoolean(S);
 215     if (S) {
 216       Hash.AddStmt(S);
 217     }
 218   }
 219
 220   void AddIdentifierInfo(const IdentifierInfo *II) {
 221     Hash.AddBoolean(II);
 222     if (II) {
 223       Hash.AddIdentifierInfo(II);
 224     }
 225   }
 226
 227   void AddQualType(QualType T) {
 228     Hash.AddQualType(T);
 229   }
 230
 231   void AddDecl(const Decl *D) {
 232     Hash.AddBoolean(D);
 233     if (D) {
 234       Hash.AddDecl(D);
 235     }
 236   }
 237
 238   void Visit(const Decl *D) {
 239     ID.AddInteger(D->getKind());
 240     Inherited::Visit(D);
 241   }
 242
 243   void VisitNamedDecl(const NamedDecl *D) {
 244     Hash.AddDeclarationName(D->getDeclName());
 245     Inherited::VisitNamedDecl(D);
 246   }
 247
 248   void VisitValueDecl(const ValueDecl *D) {
 249     if (!isa<FunctionDecl>(D)) {
 250       AddQualType(D->getType());
 251     }
 252     Inherited::VisitValueDecl(D);
 253   }
 254
 255   void VisitVarDecl(const VarDecl *D) {
 256     Hash.AddBoolean(D->isStaticLocal());
 257     Hash.AddBoolean(D->isConstexpr());
 258     const bool HasInit = D->hasInit();
 259     Hash.AddBoolean(HasInit);
 260     if (HasInit) {
 261       AddStmt(D->getInit());
 262     }
 263     Inherited::VisitVarDecl(D);
 264   }
 265
 266   void VisitParmVarDecl(const ParmVarDecl *D) {
 267     // TODO: Handle default arguments.
 268     Inherited::VisitParmVarDecl(D);
 269   }
 270
 271   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 272     ID.AddInteger(D->getAccess());
 273     Inherited::VisitAccessSpecDecl(D);
 274   }
 275
 276   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 277     AddStmt(D->getAssertExpr());
 278     AddStmt(D->getMessage());
 279
 280     Inherited::VisitStaticAssertDecl(D);
 281   }
 282
 283   void VisitFieldDecl(const FieldDecl *D) {
 284     const bool IsBitfield = D->isBitField();
 285     Hash.AddBoolean(IsBitfield);
 286
 287     if (IsBitfield) {
 288       AddStmt(D->getBitWidth());
 289     }
 290
 291     Hash.AddBoolean(D->isMutable());
 292     AddStmt(D->getInClassInitializer());
 293
 294     Inherited::VisitFieldDecl(D);
 295   }
 296
 297   void VisitFunctionDecl(const FunctionDecl *D) {
 298     ID.AddInteger(D->getStorageClass());
 299     Hash.AddBoolean(D->isInlineSpecified());
 300     Hash.AddBoolean(D->isVirtualAsWritten());
 301     Hash.AddBoolean(D->isPure());
 302     Hash.AddBoolean(D->isDeletedAsWritten());
 303
 304     ID.AddInteger(D->param_size());
 305
 306     for (auto *Param : D->parameters()) {
 307       Hash.AddSubDecl(Param);
 308     }
 309
 310     AddQualType(D->getReturnType());
 311
 312     Inherited::VisitFunctionDecl(D);
 313   }
 314
 315   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 316     Hash.AddBoolean(D->isConst());
 317     Hash.AddBoolean(D->isVolatile());
 318
 319     Inherited::VisitCXXMethodDecl(D);
 320   }
 321
 322   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 323     AddQualType(D->getUnderlyingType());
 324
 325     Inherited::VisitTypedefNameDecl(D);
 326   }
 327
 328   void VisitTypedefDecl(const TypedefDecl *D) {
 329     Inherited::VisitTypedefDecl(D);
 330   }
 331
 332   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 333     Inherited::VisitTypeAliasDecl(D);
 334   }
 335
 336   void VisitFriendDecl(const FriendDecl *D) {
 337     TypeSourceInfo *TSI = D->getFriendType();
 338     Hash.AddBoolean(TSI);
 339     if (TSI) {
 340       AddQualType(TSI->getType());
 341     } else {
 342       AddDecl(D->getFriendDecl());
 343     }
 344   }
 345 };
 346
 347 // Only allow a small portion of Decl's to be processed.  Remove this once
 348 // all Decl's can be handled.
 349 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
 350   if (D->isImplicit()) return false;
 351   if (D->getDeclContext() != Parent) return false;
 352
 353   switch (D->getKind()) {
 354     default:
 355       return false;
 356     case Decl::AccessSpec:
 357     case Decl::CXXConstructor:
 358     case Decl::CXXDestructor:
 359     case Decl::CXXMethod:
 360     case Decl::Field:
 361     case Decl::Friend:
 362     case Decl::StaticAssert:
 363     case Decl::TypeAlias:
 364     case Decl::Typedef:
 365     case Decl::Var:
 366       return true;
 367   }
 368 }
 369
 370 void ODRHash::AddSubDecl(const Decl *D) {
 371   assert(D && "Expecting non-null pointer.");
 372   AddDecl(D);
 373
 374   ODRDeclVisitor(ID, *this).Visit(D);
 375 }
 376
 377 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 378   assert(Record && Record->hasDefinition() &&
 379          "Expected non-null record to be a definition.");
 380
 381   if (isa<ClassTemplateSpecializationDecl>(Record)) {
 382     return;
 383   }
 384
 385   AddDecl(Record);
 386
 387   // Filter out sub-Decls which will not be processed in order to get an
 388   // accurate count of Decl's.
 389   llvm::SmallVector<const Decl *, 16> Decls;
 390   for (const Decl *SubDecl : Record->decls()) {
 391     if (isWhitelistedDecl(SubDecl, Record)) {
 392       Decls.push_back(SubDecl);
 393     }
 394   }
 395
 396   ID.AddInteger(Decls.size());
 397   for (auto SubDecl : Decls) {
 398     AddSubDecl(SubDecl);
 399   }
 400 }
 401
 402 void ODRHash::AddDecl(const Decl *D) {
 403   assert(D && "Expecting non-null pointer.");
 404   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
 405   ID.AddInteger(Result.first->second);
 406   // On first encounter of a Decl pointer, process it.  Every time afterwards,
 407   // only the index value is needed.
 408   if (!Result.second) {
 409     return;
 410   }
 411
 412   ID.AddInteger(D->getKind());
 413
 414   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
 415     AddDeclarationName(ND->getDeclName());
 416   }
 417 }
 418
 419 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 420 // methods process the relevant parts of the Type.
 421 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 422   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 423   llvm::FoldingSetNodeID &ID;
 424   ODRHash &Hash;
 425
 426 public:
 427   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 428       : ID(ID), Hash(Hash) {}
 429
 430   void AddStmt(Stmt *S) {
 431     Hash.AddBoolean(S);
 432     if (S) {
 433       Hash.AddStmt(S);
 434     }
 435   }
 436
 437   void AddDecl(Decl *D) {
 438     Hash.AddBoolean(D);
 439     if (D) {
 440       Hash.AddDecl(D);
 441     }
 442   }
 443
 444   void AddQualType(QualType T) {
 445     Hash.AddQualType(T);
 446   }
 447
 448   void AddType(const Type *T) {
 449     Hash.AddBoolean(T);
 450     if (T) {
 451       Hash.AddType(T);
 452     }
 453   }
 454
 455   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 456     Hash.AddBoolean(NNS);
 457     if (NNS) {
 458       Hash.AddNestedNameSpecifier(NNS);
 459     }
 460   }
 461
 462   void AddIdentifierInfo(const IdentifierInfo *II) {
 463     Hash.AddBoolean(II);
 464     if (II) {
 465       Hash.AddIdentifierInfo(II);
 466     }
 467   }
 468
 469   void VisitQualifiers(Qualifiers Quals) {
 470     ID.AddInteger(Quals.getAsOpaqueValue());
 471   }
 472
 473   void Visit(const Type *T) {
 474     ID.AddInteger(T->getTypeClass());
 475     Inherited::Visit(T);
 476   }
 477
 478   void VisitType(const Type *T) {}
 479
 480   void VisitAdjustedType(const AdjustedType *T) {
 481     AddQualType(T->getOriginalType());
 482     AddQualType(T->getAdjustedType());
 483     VisitType(T);
 484   }
 485
 486   void VisitDecayedType(const DecayedType *T) {
 487     AddQualType(T->getDecayedType());
 488     AddQualType(T->getPointeeType());
 489     VisitAdjustedType(T);
 490   }
 491
 492   void VisitArrayType(const ArrayType *T) {
 493     AddQualType(T->getElementType());
 494     ID.AddInteger(T->getSizeModifier());
 495     VisitQualifiers(T->getIndexTypeQualifiers());
 496     VisitType(T);
 497   }
 498   void VisitConstantArrayType(const ConstantArrayType *T) {
 499     T->getSize().Profile(ID);
 500     VisitArrayType(T);
 501   }
 502
 503   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 504     AddStmt(T->getSizeExpr());
 505     VisitArrayType(T);
 506   }
 507
 508   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 509     VisitArrayType(T);
 510   }
 511
 512   void VisitVariableArrayType(const VariableArrayType *T) {
 513     AddStmt(T->getSizeExpr());
 514     VisitArrayType(T);
 515   }
 516
 517   void VisitBuiltinType(const BuiltinType *T) {
 518     ID.AddInteger(T->getKind());
 519     VisitType(T);
 520   }
 521
 522   void VisitFunctionType(const FunctionType *T) {
 523     AddQualType(T->getReturnType());
 524     T->getExtInfo().Profile(ID);
 525     Hash.AddBoolean(T->isConst());
 526     Hash.AddBoolean(T->isVolatile());
 527     Hash.AddBoolean(T->isRestrict());
 528     VisitType(T);
 529   }
 530
 531   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 532     VisitFunctionType(T);
 533   }
 534
 535   void VisitFunctionProtoType(const FunctionProtoType *T) {
 536     ID.AddInteger(T->getNumParams());
 537     for (auto ParamType : T->getParamTypes())
 538       AddQualType(ParamType);
 539
 540     VisitFunctionType(T);
 541   }
 542
 543   void VisitTypedefType(const TypedefType *T) {
 544     AddDecl(T->getDecl());
 545     QualType UnderlyingType = T->getDecl()->getUnderlyingType();
 546     VisitQualifiers(UnderlyingType.getQualifiers());
 547     while (const TypedefType *Underlying =
 548                dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
 549       UnderlyingType = Underlying->getDecl()->getUnderlyingType();
 550     }
 551     AddType(UnderlyingType.getTypePtr());
 552     VisitType(T);
 553   }
 554
 555   void VisitTagType(const TagType *T) {
 556     AddDecl(T->getDecl());
 557     VisitType(T);
 558   }
 559
 560   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
 561   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
 562
 563   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
 564     ID.AddInteger(T->getKeyword());
 565     VisitType(T);
 566   };
 567
 568   void VisitDependentNameType(const DependentNameType *T) {
 569     AddNestedNameSpecifier(T->getQualifier());
 570     AddIdentifierInfo(T->getIdentifier());
 571     VisitTypeWithKeyword(T);
 572   }
 573
 574   void VisitDependentTemplateSpecializationType(
 575       const DependentTemplateSpecializationType *T) {
 576     AddIdentifierInfo(T->getIdentifier());
 577     AddNestedNameSpecifier(T->getQualifier());
 578     ID.AddInteger(T->getNumArgs());
 579     for (const auto &TA : T->template_arguments()) {
 580       Hash.AddTemplateArgument(TA);
 581     }
 582     VisitTypeWithKeyword(T);
 583   }
 584
 585   void VisitElaboratedType(const ElaboratedType *T) {
 586     AddNestedNameSpecifier(T->getQualifier());
 587     AddQualType(T->getNamedType());
 588     VisitTypeWithKeyword(T);
 589   }
 590
 591   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
 592     ID.AddInteger(T->getNumArgs());
 593     for (const auto &TA : T->template_arguments()) {
 594       Hash.AddTemplateArgument(TA);
 595     }
 596     Hash.AddTemplateName(T->getTemplateName());
 597     VisitType(T);
 598   }
 599
 600   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
 601     ID.AddInteger(T->getDepth());
 602     ID.AddInteger(T->getIndex());
 603     Hash.AddBoolean(T->isParameterPack());
 604     AddDecl(T->getDecl());
 605   }
 606 };
 607
 608 void ODRHash::AddType(const Type *T) {
 609   assert(T && "Expecting non-null pointer.");
 610   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
 611   ID.AddInteger(Result.first->second);
 612   // On first encounter of a Type pointer, process it.  Every time afterwards,
 613   // only the index value is needed.
 614   if (!Result.second) {
 615     return;
 616   }
 617
 618   ODRTypeVisitor(ID, *this).Visit(T);
 619 }
 620
 621 void ODRHash::AddQualType(QualType T) {
 622   AddBoolean(T.isNull());
 623   if (T.isNull())
 624     return;
 625   SplitQualType split = T.split();
 626   ID.AddInteger(split.Quals.getAsOpaqueValue());
 627   AddType(split.Ty);
 628 }
 629
 630 void ODRHash::AddBoolean(bool Value) {
 631   Bools.push_back(Value);
 632 }