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