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