1 //===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file implements the ODRHash class, which calculates a hash based
12 /// on AST nodes, which is stable across different runs.
14 //===----------------------------------------------------------------------===//
16 #include "clang/AST/ODRHash.h"
18 #include "clang/AST/DeclVisitor.h"
19 #include "clang/AST/NestedNameSpecifier.h"
20 #include "clang/AST/StmtVisitor.h"
21 #include "clang/AST/TypeVisitor.h"
23 using namespace clang;
25 void ODRHash::AddStmt(const Stmt *S) {
26 assert(S && "Expecting non-null pointer.");
27 S->ProcessODRHash(ID, *this);
30 void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
31 assert(II && "Expecting non-null pointer.");
32 ID.AddString(II->getName());
35 void ODRHash::AddDeclarationName(DeclarationName Name) {
36 AddBoolean(Name.isEmpty());
40 auto Kind = Name.getNameKind();
43 case DeclarationName::Identifier:
44 AddIdentifierInfo(Name.getAsIdentifierInfo());
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));
59 case DeclarationName::CXXConstructorName:
60 case DeclarationName::CXXDestructorName:
61 AddQualType(Name.getCXXNameType());
63 case DeclarationName::CXXOperatorName:
64 ID.AddInteger(Name.getCXXOverloadedOperator());
66 case DeclarationName::CXXLiteralOperatorName:
67 AddIdentifierInfo(Name.getCXXLiteralIdentifier());
69 case DeclarationName::CXXConversionFunctionName:
70 AddQualType(Name.getCXXNameType());
72 case DeclarationName::CXXUsingDirective:
74 case DeclarationName::CXXDeductionGuideName: {
75 auto *Template = Name.getCXXDeductionGuideTemplate();
84 void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
85 assert(NNS && "Expecting non-null pointer.");
86 const auto *Prefix = NNS->getPrefix();
89 AddNestedNameSpecifier(Prefix);
91 auto Kind = NNS->getKind();
94 case NestedNameSpecifier::Identifier:
95 AddIdentifierInfo(NNS->getAsIdentifier());
97 case NestedNameSpecifier::Namespace:
98 AddDecl(NNS->getAsNamespace());
100 case NestedNameSpecifier::NamespaceAlias:
101 AddDecl(NNS->getAsNamespaceAlias());
103 case NestedNameSpecifier::TypeSpec:
104 case NestedNameSpecifier::TypeSpecWithTemplate:
105 AddType(NNS->getAsType());
107 case NestedNameSpecifier::Global:
108 case NestedNameSpecifier::Super:
113 void ODRHash::AddTemplateName(TemplateName Name) {
114 auto Kind = Name.getKind();
118 case TemplateName::Template:
119 AddDecl(Name.getAsTemplateDecl());
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:
131 void ODRHash::AddTemplateArgument(TemplateArgument TA) {
132 const auto Kind = TA.getKind();
136 case TemplateArgument::Null:
137 llvm_unreachable("Expected valid TemplateArgument");
138 case TemplateArgument::Type:
139 AddQualType(TA.getAsType());
141 case TemplateArgument::Declaration:
142 case TemplateArgument::NullPtr:
143 case TemplateArgument::Integral:
145 case TemplateArgument::Template:
146 case TemplateArgument::TemplateExpansion:
147 AddTemplateName(TA.getAsTemplateOrTemplatePattern());
149 case TemplateArgument::Expression:
150 AddStmt(TA.getAsExpr());
152 case TemplateArgument::Pack:
153 ID.AddInteger(TA.pack_size());
154 for (auto SubTA : TA.pack_elements()) {
155 AddTemplateArgument(SubTA);
161 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
162 assert(TPL && "Expecting non-null pointer.");
164 ID.AddInteger(TPL->size());
165 for (auto *ND : TPL->asArray()) {
170 void ODRHash::clear() {
177 unsigned ODRHash::CalculateHash() {
178 // Append the bools to the end of the data segment backwards. This allows
179 // for the bools data to be compressed 32 times smaller compared to using
181 const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
182 const unsigned size = Bools.size();
183 const unsigned remainder = size % unsigned_bits;
184 const unsigned loops = size / unsigned_bits;
185 auto I = Bools.rbegin();
187 for (unsigned i = 0; i < remainder; ++i) {
192 ID.AddInteger(value);
194 for (unsigned i = 0; i < loops; ++i) {
196 for (unsigned j = 0; j < unsigned_bits; ++j) {
201 ID.AddInteger(value);
204 assert(I == Bools.rend());
206 return ID.ComputeHash();
210 // Process a Decl pointer. Add* methods call back into ODRHash while Visit*
211 // methods process the relevant parts of the Decl.
212 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
213 typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
214 llvm::FoldingSetNodeID &ID;
218 ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
219 : ID(ID), Hash(Hash) {}
221 void AddStmt(const Stmt *S) {
228 void AddIdentifierInfo(const IdentifierInfo *II) {
231 Hash.AddIdentifierInfo(II);
235 void AddQualType(QualType T) {
239 void AddDecl(const Decl *D) {
246 void AddTemplateArgument(TemplateArgument TA) {
247 Hash.AddTemplateArgument(TA);
250 void Visit(const Decl *D) {
251 ID.AddInteger(D->getKind());
255 void VisitNamedDecl(const NamedDecl *D) {
256 Hash.AddDeclarationName(D->getDeclName());
257 Inherited::VisitNamedDecl(D);
260 void VisitValueDecl(const ValueDecl *D) {
261 if (!isa<FunctionDecl>(D)) {
262 AddQualType(D->getType());
264 Inherited::VisitValueDecl(D);
267 void VisitVarDecl(const VarDecl *D) {
268 Hash.AddBoolean(D->isStaticLocal());
269 Hash.AddBoolean(D->isConstexpr());
270 const bool HasInit = D->hasInit();
271 Hash.AddBoolean(HasInit);
273 AddStmt(D->getInit());
275 Inherited::VisitVarDecl(D);
278 void VisitParmVarDecl(const ParmVarDecl *D) {
279 // TODO: Handle default arguments.
280 Inherited::VisitParmVarDecl(D);
283 void VisitAccessSpecDecl(const AccessSpecDecl *D) {
284 ID.AddInteger(D->getAccess());
285 Inherited::VisitAccessSpecDecl(D);
288 void VisitStaticAssertDecl(const StaticAssertDecl *D) {
289 AddStmt(D->getAssertExpr());
290 AddStmt(D->getMessage());
292 Inherited::VisitStaticAssertDecl(D);
295 void VisitFieldDecl(const FieldDecl *D) {
296 const bool IsBitfield = D->isBitField();
297 Hash.AddBoolean(IsBitfield);
300 AddStmt(D->getBitWidth());
303 Hash.AddBoolean(D->isMutable());
304 AddStmt(D->getInClassInitializer());
306 Inherited::VisitFieldDecl(D);
309 void VisitFunctionDecl(const FunctionDecl *D) {
310 ID.AddInteger(D->getStorageClass());
311 Hash.AddBoolean(D->isInlineSpecified());
312 Hash.AddBoolean(D->isVirtualAsWritten());
313 Hash.AddBoolean(D->isPure());
314 Hash.AddBoolean(D->isDeletedAsWritten());
316 ID.AddInteger(D->param_size());
318 for (auto *Param : D->parameters()) {
319 Hash.AddSubDecl(Param);
322 AddQualType(D->getReturnType());
324 Inherited::VisitFunctionDecl(D);
327 void VisitCXXMethodDecl(const CXXMethodDecl *D) {
328 Hash.AddBoolean(D->isConst());
329 Hash.AddBoolean(D->isVolatile());
331 Inherited::VisitCXXMethodDecl(D);
334 void VisitTypedefNameDecl(const TypedefNameDecl *D) {
335 AddQualType(D->getUnderlyingType());
337 Inherited::VisitTypedefNameDecl(D);
340 void VisitTypedefDecl(const TypedefDecl *D) {
341 Inherited::VisitTypedefDecl(D);
344 void VisitTypeAliasDecl(const TypeAliasDecl *D) {
345 Inherited::VisitTypeAliasDecl(D);
348 void VisitFriendDecl(const FriendDecl *D) {
349 TypeSourceInfo *TSI = D->getFriendType();
350 Hash.AddBoolean(TSI);
352 AddQualType(TSI->getType());
354 AddDecl(D->getFriendDecl());
358 void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
359 // Only care about default arguments as part of the definition.
360 const bool hasDefaultArgument =
361 D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
362 Hash.AddBoolean(hasDefaultArgument);
363 if (hasDefaultArgument) {
364 AddTemplateArgument(D->getDefaultArgument());
367 Inherited::VisitTemplateTypeParmDecl(D);
370 void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
371 // Only care about default arguments as part of the definition.
372 const bool hasDefaultArgument =
373 D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
374 Hash.AddBoolean(hasDefaultArgument);
375 if (hasDefaultArgument) {
376 AddStmt(D->getDefaultArgument());
379 Inherited::VisitNonTypeTemplateParmDecl(D);
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());
391 Inherited::VisitTemplateTemplateParmDecl(D);
396 // Only allow a small portion of Decl's to be processed. Remove this once
397 // all Decl's can be handled.
398 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
399 if (D->isImplicit()) return false;
400 if (D->getDeclContext() != Parent) return false;
402 switch (D->getKind()) {
405 case Decl::AccessSpec:
406 case Decl::CXXConstructor:
407 case Decl::CXXDestructor:
408 case Decl::CXXMethod:
411 case Decl::StaticAssert:
412 case Decl::TypeAlias:
419 void ODRHash::AddSubDecl(const Decl *D) {
420 assert(D && "Expecting non-null pointer.");
423 ODRDeclVisitor(ID, *this).Visit(D);
426 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
427 assert(Record && Record->hasDefinition() &&
428 "Expected non-null record to be a definition.");
430 const DeclContext *DC = Record;
432 if (isa<ClassTemplateSpecializationDecl>(DC)) {
435 DC = DC->getParent();
440 // Filter out sub-Decls which will not be processed in order to get an
441 // accurate count of Decl's.
442 llvm::SmallVector<const Decl *, 16> Decls;
443 for (const Decl *SubDecl : Record->decls()) {
444 if (isWhitelistedDecl(SubDecl, Record)) {
445 Decls.push_back(SubDecl);
449 ID.AddInteger(Decls.size());
450 for (auto SubDecl : Decls) {
454 const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
457 AddTemplateParameterList(TD->getTemplateParameters());
460 ID.AddInteger(Record->getNumBases());
461 auto Bases = Record->bases();
462 for (auto Base : Bases) {
463 AddQualType(Base.getType());
464 ID.AddInteger(Base.isVirtual());
465 ID.AddInteger(Base.getAccessSpecifierAsWritten());
469 void ODRHash::AddFunctionDecl(const FunctionDecl *Function) {
470 assert(Function && "Expecting non-null pointer.");
472 // Skip hashing these kinds of function.
473 if (Function->isImplicit()) return;
474 if (Function->isDefaulted()) return;
475 if (Function->isDeleted()) return;
476 if (!Function->hasBody()) return;
477 if (!Function->getBody()) return;
479 // TODO: Fix hashing for class methods.
480 if (isa<CXXMethodDecl>(Function)) return;
481 // And friend functions.
482 if (Function->getFriendObjectKind()) return;
484 // Skip functions that are specializations or in specialization context.
485 const DeclContext *DC = Function;
487 if (isa<ClassTemplateSpecializationDecl>(DC)) return;
488 if (auto *F = dyn_cast<FunctionDecl>(DC))
489 if (F->isFunctionTemplateSpecialization()) return;
490 DC = DC->getParent();
495 AddQualType(Function->getReturnType());
497 ID.AddInteger(Function->param_size());
498 for (auto Param : Function->parameters())
501 AddStmt(Function->getBody());
504 void ODRHash::AddDecl(const Decl *D) {
505 assert(D && "Expecting non-null pointer.");
506 D = D->getCanonicalDecl();
507 auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
508 ID.AddInteger(Result.first->second);
509 // On first encounter of a Decl pointer, process it. Every time afterwards,
510 // only the index value is needed.
511 if (!Result.second) {
515 ID.AddInteger(D->getKind());
517 if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
518 AddDeclarationName(ND->getDeclName());
523 // Process a Type pointer. Add* methods call back into ODRHash while Visit*
524 // methods process the relevant parts of the Type.
525 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
526 typedef TypeVisitor<ODRTypeVisitor> Inherited;
527 llvm::FoldingSetNodeID &ID;
531 ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
532 : ID(ID), Hash(Hash) {}
534 void AddStmt(Stmt *S) {
541 void AddDecl(Decl *D) {
548 void AddQualType(QualType T) {
552 void AddType(const Type *T) {
559 void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
560 Hash.AddBoolean(NNS);
562 Hash.AddNestedNameSpecifier(NNS);
566 void AddIdentifierInfo(const IdentifierInfo *II) {
569 Hash.AddIdentifierInfo(II);
573 void VisitQualifiers(Qualifiers Quals) {
574 ID.AddInteger(Quals.getAsOpaqueValue());
577 void Visit(const Type *T) {
578 ID.AddInteger(T->getTypeClass());
582 void VisitType(const Type *T) {}
584 void VisitAdjustedType(const AdjustedType *T) {
585 AddQualType(T->getOriginalType());
586 AddQualType(T->getAdjustedType());
590 void VisitDecayedType(const DecayedType *T) {
591 AddQualType(T->getDecayedType());
592 AddQualType(T->getPointeeType());
593 VisitAdjustedType(T);
596 void VisitArrayType(const ArrayType *T) {
597 AddQualType(T->getElementType());
598 ID.AddInteger(T->getSizeModifier());
599 VisitQualifiers(T->getIndexTypeQualifiers());
602 void VisitConstantArrayType(const ConstantArrayType *T) {
603 T->getSize().Profile(ID);
607 void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
608 AddStmt(T->getSizeExpr());
612 void VisitIncompleteArrayType(const IncompleteArrayType *T) {
616 void VisitVariableArrayType(const VariableArrayType *T) {
617 AddStmt(T->getSizeExpr());
621 void VisitBuiltinType(const BuiltinType *T) {
622 ID.AddInteger(T->getKind());
626 void VisitFunctionType(const FunctionType *T) {
627 AddQualType(T->getReturnType());
628 T->getExtInfo().Profile(ID);
629 Hash.AddBoolean(T->isConst());
630 Hash.AddBoolean(T->isVolatile());
631 Hash.AddBoolean(T->isRestrict());
635 void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
636 VisitFunctionType(T);
639 void VisitFunctionProtoType(const FunctionProtoType *T) {
640 ID.AddInteger(T->getNumParams());
641 for (auto ParamType : T->getParamTypes())
642 AddQualType(ParamType);
644 VisitFunctionType(T);
647 void VisitTypedefType(const TypedefType *T) {
648 AddDecl(T->getDecl());
649 QualType UnderlyingType = T->getDecl()->getUnderlyingType();
650 VisitQualifiers(UnderlyingType.getQualifiers());
651 while (const TypedefType *Underlying =
652 dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
653 UnderlyingType = Underlying->getDecl()->getUnderlyingType();
655 AddType(UnderlyingType.getTypePtr());
659 void VisitTagType(const TagType *T) {
660 AddDecl(T->getDecl());
664 void VisitRecordType(const RecordType *T) { VisitTagType(T); }
665 void VisitEnumType(const EnumType *T) { VisitTagType(T); }
667 void VisitTypeWithKeyword(const TypeWithKeyword *T) {
668 ID.AddInteger(T->getKeyword());
672 void VisitDependentNameType(const DependentNameType *T) {
673 AddNestedNameSpecifier(T->getQualifier());
674 AddIdentifierInfo(T->getIdentifier());
675 VisitTypeWithKeyword(T);
678 void VisitDependentTemplateSpecializationType(
679 const DependentTemplateSpecializationType *T) {
680 AddIdentifierInfo(T->getIdentifier());
681 AddNestedNameSpecifier(T->getQualifier());
682 ID.AddInteger(T->getNumArgs());
683 for (const auto &TA : T->template_arguments()) {
684 Hash.AddTemplateArgument(TA);
686 VisitTypeWithKeyword(T);
689 void VisitElaboratedType(const ElaboratedType *T) {
690 AddNestedNameSpecifier(T->getQualifier());
691 AddQualType(T->getNamedType());
692 VisitTypeWithKeyword(T);
695 void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
696 ID.AddInteger(T->getNumArgs());
697 for (const auto &TA : T->template_arguments()) {
698 Hash.AddTemplateArgument(TA);
700 Hash.AddTemplateName(T->getTemplateName());
704 void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
705 ID.AddInteger(T->getDepth());
706 ID.AddInteger(T->getIndex());
707 Hash.AddBoolean(T->isParameterPack());
708 AddDecl(T->getDecl());
713 void ODRHash::AddType(const Type *T) {
714 assert(T && "Expecting non-null pointer.");
715 auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
716 ID.AddInteger(Result.first->second);
717 // On first encounter of a Type pointer, process it. Every time afterwards,
718 // only the index value is needed.
719 if (!Result.second) {
723 ODRTypeVisitor(ID, *this).Visit(T);
726 void ODRHash::AddQualType(QualType T) {
727 AddBoolean(T.isNull());
730 SplitQualType split = T.split();
731 ID.AddInteger(split.Quals.getAsOpaqueValue());
735 void ODRHash::AddBoolean(bool Value) {
736 Bools.push_back(Value);