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 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
 133
 134 void ODRHash::clear() {
 135   DeclMap.clear();
 136   TypeMap.clear();
 137   Bools.clear();
 138   ID.clear();
 139 }
 140
 141 unsigned ODRHash::CalculateHash() {
 142   // Append the bools to the end of the data segment backwards.  This allows
 143   // for the bools data to be compressed 32 times smaller compared to using
 144   // ID.AddBoolean
 145   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
 146   const unsigned size = Bools.size();
 147   const unsigned remainder = size % unsigned_bits;
 148   const unsigned loops = size / unsigned_bits;
 149   auto I = Bools.rbegin();
 150   unsigned value = 0;
 151   for (unsigned i = 0; i < remainder; ++i) {
 152     value <<= 1;
 153     value |= *I;
 154     ++I;
 155   }
 156   ID.AddInteger(value);
 157
 158   for (unsigned i = 0; i < loops; ++i) {
 159     value = 0;
 160     for (unsigned j = 0; j < unsigned_bits; ++j) {
 161       value <<= 1;
 162       value |= *I;
 163       ++I;
 164     }
 165     ID.AddInteger(value);
 166   }
 167
 168   assert(I == Bools.rend());
 169   Bools.clear();
 170   return ID.ComputeHash();
 171 }
 172
 173 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
 174 // methods process the relevant parts of the Decl.
 175 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
 176   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
 177   llvm::FoldingSetNodeID &ID;
 178   ODRHash &Hash;
 179
 180 public:
 181   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 182       : ID(ID), Hash(Hash) {}
 183
 184   void AddStmt(const Stmt *S) {
 185     Hash.AddBoolean(S);
 186     if (S) {
 187       Hash.AddStmt(S);
 188     }
 189   }
 190
 191   void AddIdentifierInfo(const IdentifierInfo *II) {
 192     Hash.AddBoolean(II);
 193     if (II) {
 194       Hash.AddIdentifierInfo(II);
 195     }
 196   }
 197
 198   void AddQualType(QualType T) {
 199     Hash.AddQualType(T);
 200   }
 201
 202   void Visit(const Decl *D) {
 203     ID.AddInteger(D->getKind());
 204     Inherited::Visit(D);
 205   }
 206
 207   void VisitNamedDecl(const NamedDecl *D) {
 208     Hash.AddDeclarationName(D->getDeclName());
 209     Inherited::VisitNamedDecl(D);
 210   }
 211
 212   void VisitValueDecl(const ValueDecl *D) {
 213     AddQualType(D->getType());
 214     Inherited::VisitValueDecl(D);
 215   }
 216
 217   void VisitParmVarDecl(const ParmVarDecl *D) {
 218     // TODO: Handle default arguments.
 219     Inherited::VisitParmVarDecl(D);
 220   }
 221
 222   void VisitAccessSpecDecl(const AccessSpecDecl *D) {
 223     ID.AddInteger(D->getAccess());
 224     Inherited::VisitAccessSpecDecl(D);
 225   }
 226
 227   void VisitStaticAssertDecl(const StaticAssertDecl *D) {
 228     AddStmt(D->getAssertExpr());
 229     AddStmt(D->getMessage());
 230
 231     Inherited::VisitStaticAssertDecl(D);
 232   }
 233
 234   void VisitFieldDecl(const FieldDecl *D) {
 235     const bool IsBitfield = D->isBitField();
 236     Hash.AddBoolean(IsBitfield);
 237
 238     if (IsBitfield) {
 239       AddStmt(D->getBitWidth());
 240     }
 241
 242     Hash.AddBoolean(D->isMutable());
 243     AddStmt(D->getInClassInitializer());
 244
 245     Inherited::VisitFieldDecl(D);
 246   }
 247
 248   void VisitFunctionDecl(const FunctionDecl *D) {
 249     ID.AddInteger(D->getStorageClass());
 250     Hash.AddBoolean(D->isInlineSpecified());
 251     Hash.AddBoolean(D->isVirtualAsWritten());
 252     Hash.AddBoolean(D->isPure());
 253     Hash.AddBoolean(D->isDeletedAsWritten());
 254
 255     ID.AddInteger(D->param_size());
 256
 257     for (auto *Param : D->parameters()) {
 258       Hash.AddSubDecl(Param);
 259     }
 260
 261     Inherited::VisitFunctionDecl(D);
 262   }
 263
 264   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
 265     Hash.AddBoolean(D->isConst());
 266     Hash.AddBoolean(D->isVolatile());
 267
 268     Inherited::VisitCXXMethodDecl(D);
 269   }
 270
 271   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
 272     AddQualType(D->getUnderlyingType());
 273
 274     Inherited::VisitTypedefNameDecl(D);
 275   }
 276
 277   void VisitTypedefDecl(const TypedefDecl *D) {
 278     Inherited::VisitTypedefDecl(D);
 279   }
 280
 281   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
 282     Inherited::VisitTypeAliasDecl(D);
 283   }
 284 };
 285
 286 // Only allow a small portion of Decl's to be processed.  Remove this once
 287 // all Decl's can be handled.
 288 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
 289   if (D->isImplicit()) return false;
 290   if (D->getDeclContext() != Parent) return false;
 291
 292   switch (D->getKind()) {
 293     default:
 294       return false;
 295     case Decl::AccessSpec:
 296     case Decl::CXXMethod:
 297     case Decl::Field:
 298     case Decl::StaticAssert:
 299     case Decl::TypeAlias:
 300     case Decl::Typedef:
 301       return true;
 302   }
 303 }
 304
 305 void ODRHash::AddSubDecl(const Decl *D) {
 306   assert(D && "Expecting non-null pointer.");
 307   AddDecl(D);
 308
 309   ODRDeclVisitor(ID, *this).Visit(D);
 310 }
 311
 312 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
 313   assert(Record && Record->hasDefinition() &&
 314          "Expected non-null record to be a definition.");
 315
 316   if (isa<ClassTemplateSpecializationDecl>(Record)) {
 317     return;
 318   }
 319
 320   AddDecl(Record);
 321
 322   // Filter out sub-Decls which will not be processed in order to get an
 323   // accurate count of Decl's.
 324   llvm::SmallVector<const Decl *, 16> Decls;
 325   for (const Decl *SubDecl : Record->decls()) {
 326     if (isWhitelistedDecl(SubDecl, Record)) {
 327       Decls.push_back(SubDecl);
 328     }
 329   }
 330
 331   ID.AddInteger(Decls.size());
 332   for (auto SubDecl : Decls) {
 333     AddSubDecl(SubDecl);
 334   }
 335 }
 336
 337 void ODRHash::AddDecl(const Decl *D) {
 338   assert(D && "Expecting non-null pointer.");
 339   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
 340   ID.AddInteger(Result.first->second);
 341   // On first encounter of a Decl pointer, process it.  Every time afterwards,
 342   // only the index value is needed.
 343   if (!Result.second) {
 344     return;
 345   }
 346
 347   ID.AddInteger(D->getKind());
 348
 349   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
 350     AddDeclarationName(ND->getDeclName());
 351   }
 352 }
 353
 354 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
 355 // methods process the relevant parts of the Type.
 356 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
 357   typedef TypeVisitor<ODRTypeVisitor> Inherited;
 358   llvm::FoldingSetNodeID &ID;
 359   ODRHash &Hash;
 360
 361 public:
 362   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
 363       : ID(ID), Hash(Hash) {}
 364
 365   void AddStmt(Stmt *S) {
 366     Hash.AddBoolean(S);
 367     if (S) {
 368       Hash.AddStmt(S);
 369     }
 370   }
 371
 372   void AddDecl(Decl *D) {
 373     Hash.AddBoolean(D);
 374     if (D) {
 375       Hash.AddDecl(D);
 376     }
 377   }
 378
 379   void AddQualType(QualType T) {
 380     Hash.AddQualType(T);
 381   }
 382
 383   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
 384     Hash.AddBoolean(NNS);
 385     if (NNS) {
 386       Hash.AddNestedNameSpecifier(NNS);
 387     }
 388   }
 389
 390   void AddIdentifierInfo(const IdentifierInfo *II) {
 391     Hash.AddBoolean(II);
 392     if (II) {
 393       Hash.AddIdentifierInfo(II);
 394     }
 395   }
 396
 397   void VisitQualifiers(Qualifiers Quals) {
 398     ID.AddInteger(Quals.getAsOpaqueValue());
 399   }
 400
 401   void Visit(const Type *T) {
 402     ID.AddInteger(T->getTypeClass());
 403     Inherited::Visit(T);
 404   }
 405
 406   void VisitType(const Type *T) {}
 407
 408   void VisitAdjustedType(const AdjustedType *T) {
 409     AddQualType(T->getOriginalType());
 410     AddQualType(T->getAdjustedType());
 411     VisitType(T);
 412   }
 413
 414   void VisitDecayedType(const DecayedType *T) {
 415     AddQualType(T->getDecayedType());
 416     AddQualType(T->getPointeeType());
 417     VisitAdjustedType(T);
 418   }
 419
 420   void VisitArrayType(const ArrayType *T) {
 421     AddQualType(T->getElementType());
 422     ID.AddInteger(T->getSizeModifier());
 423     VisitQualifiers(T->getIndexTypeQualifiers());
 424     VisitType(T);
 425   }
 426   void VisitConstantArrayType(const ConstantArrayType *T) {
 427     T->getSize().Profile(ID);
 428     VisitArrayType(T);
 429   }
 430
 431   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
 432     AddStmt(T->getSizeExpr());
 433     VisitArrayType(T);
 434   }
 435
 436   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
 437     VisitArrayType(T);
 438   }
 439
 440   void VisitVariableArrayType(const VariableArrayType *T) {
 441     AddStmt(T->getSizeExpr());
 442     VisitArrayType(T);
 443   }
 444
 445   void VisitBuiltinType(const BuiltinType *T) {
 446     ID.AddInteger(T->getKind());
 447     VisitType(T);
 448   }
 449
 450   void VisitFunctionType(const FunctionType *T) {
 451     AddQualType(T->getReturnType());
 452     T->getExtInfo().Profile(ID);
 453     Hash.AddBoolean(T->isConst());
 454     Hash.AddBoolean(T->isVolatile());
 455     Hash.AddBoolean(T->isRestrict());
 456     VisitType(T);
 457   }
 458
 459   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
 460     VisitFunctionType(T);
 461   }
 462
 463   void VisitFunctionProtoType(const FunctionProtoType *T) {
 464     ID.AddInteger(T->getNumParams());
 465     for (auto ParamType : T->getParamTypes())
 466       AddQualType(ParamType);
 467
 468     VisitFunctionType(T);
 469   }
 470
 471   void VisitTypedefType(const TypedefType *T) {
 472     AddDecl(T->getDecl());
 473     AddQualType(T->getDecl()->getUnderlyingType().getCanonicalType());
 474     VisitType(T);
 475   }
 476
 477   void VisitTagType(const TagType *T) {
 478     AddDecl(T->getDecl());
 479     VisitType(T);
 480   }
 481
 482   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
 483   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
 484
 485   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
 486     ID.AddInteger(T->getKeyword());
 487     VisitType(T);
 488   };
 489
 490   void VisitDependentNameType(const DependentNameType *T) {
 491     AddNestedNameSpecifier(T->getQualifier());
 492     AddIdentifierInfo(T->getIdentifier());
 493     VisitTypeWithKeyword(T);
 494   }
 495
 496   void VisitDependentTemplateSpecializationType(
 497       const DependentTemplateSpecializationType *T) {
 498     AddIdentifierInfo(T->getIdentifier());
 499     AddNestedNameSpecifier(T->getQualifier());
 500     ID.AddInteger(T->getNumArgs());
 501     for (const auto &TA : T->template_arguments()) {
 502       Hash.AddTemplateArgument(TA);
 503     }
 504     VisitTypeWithKeyword(T);
 505   }
 506
 507   void VisitElaboratedType(const ElaboratedType *T) {
 508     AddNestedNameSpecifier(T->getQualifier());
 509     AddQualType(T->getNamedType());
 510     VisitTypeWithKeyword(T);
 511   }
 512
 513   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
 514     ID.AddInteger(T->getNumArgs());
 515     for (const auto &TA : T->template_arguments()) {
 516       Hash.AddTemplateArgument(TA);
 517     }
 518     Hash.AddTemplateName(T->getTemplateName());
 519     VisitType(T);
 520   }
 521 };
 522
 523 void ODRHash::AddType(const Type *T) {
 524   assert(T && "Expecting non-null pointer.");
 525   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
 526   ID.AddInteger(Result.first->second);
 527   // On first encounter of a Type pointer, process it.  Every time afterwards,
 528   // only the index value is needed.
 529   if (!Result.second) {
 530     return;
 531   }
 532
 533   ODRTypeVisitor(ID, *this).Visit(T);
 534 }
 535
 536 void ODRHash::AddQualType(QualType T) {
 537   AddBoolean(T.isNull());
 538   if (T.isNull())
 539     return;
 540   SplitQualType split = T.split();
 541   ID.AddInteger(split.Quals.getAsOpaqueValue());
 542   AddType(split.Ty);
 543 }
 544
 545 void ODRHash::AddBoolean(bool Value) {
 546   Bools.push_back(Value);
 547 }