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     case TemplateArgument::Type:
150     case TemplateArgument::Declaration:
151     case TemplateArgument::NullPtr:
152     case TemplateArgument::Integral:
153       break;
154     case TemplateArgument::Template:
155     case TemplateArgument::TemplateExpansion:
156       AddTemplateName(TA.getAsTemplateOrTemplatePattern());
157       break;
158     case TemplateArgument::Expression:
159       AddStmt(TA.getAsExpr());
160       break;
161     case TemplateArgument::Pack:
162       ID.AddInteger(TA.pack_size());
163       for (auto SubTA : TA.pack_elements()) {
164         AddTemplateArgument(SubTA);
165       }
166       break;
167   }
168 }
169 
170 void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
171 
172 void ODRHash::clear() {
173   DeclMap.clear();
174   TypeMap.clear();
175   Bools.clear();
176   ID.clear();
177 }
178 
179 unsigned ODRHash::CalculateHash() {
180   // Append the bools to the end of the data segment backwards.  This allows
181   // for the bools data to be compressed 32 times smaller compared to using
182   // ID.AddBoolean
183   const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
184   const unsigned size = Bools.size();
185   const unsigned remainder = size % unsigned_bits;
186   const unsigned loops = size / unsigned_bits;
187   auto I = Bools.rbegin();
188   unsigned value = 0;
189   for (unsigned i = 0; i < remainder; ++i) {
190     value <<= 1;
191     value |= *I;
192     ++I;
193   }
194   ID.AddInteger(value);
195 
196   for (unsigned i = 0; i < loops; ++i) {
197     value = 0;
198     for (unsigned j = 0; j < unsigned_bits; ++j) {
199       value <<= 1;
200       value |= *I;
201       ++I;
202     }
203     ID.AddInteger(value);
204   }
205 
206   assert(I == Bools.rend());
207   Bools.clear();
208   return ID.ComputeHash();
209 }
210 
211 // Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
212 // methods process the relevant parts of the Decl.
213 class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
214   typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
215   llvm::FoldingSetNodeID &ID;
216   ODRHash &Hash;
217 
218 public:
219   ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
220       : ID(ID), Hash(Hash) {}
221 
222   void AddStmt(const Stmt *S) {
223     Hash.AddBoolean(S);
224     if (S) {
225       Hash.AddStmt(S);
226     }
227   }
228 
229   void AddIdentifierInfo(const IdentifierInfo *II) {
230     Hash.AddBoolean(II);
231     if (II) {
232       Hash.AddIdentifierInfo(II);
233     }
234   }
235 
236   void AddQualType(QualType T) {
237     Hash.AddQualType(T);
238   }
239 
240   void Visit(const Decl *D) {
241     ID.AddInteger(D->getKind());
242     Inherited::Visit(D);
243   }
244 
245   void VisitNamedDecl(const NamedDecl *D) {
246     Hash.AddDeclarationName(D->getDeclName());
247     Inherited::VisitNamedDecl(D);
248   }
249 
250   void VisitValueDecl(const ValueDecl *D) {
251     AddQualType(D->getType());
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     Inherited::VisitFunctionDecl(D);
311   }
312 
313   void VisitCXXMethodDecl(const CXXMethodDecl *D) {
314     Hash.AddBoolean(D->isConst());
315     Hash.AddBoolean(D->isVolatile());
316 
317     Inherited::VisitCXXMethodDecl(D);
318   }
319 
320   void VisitTypedefNameDecl(const TypedefNameDecl *D) {
321     AddQualType(D->getUnderlyingType());
322 
323     Inherited::VisitTypedefNameDecl(D);
324   }
325 
326   void VisitTypedefDecl(const TypedefDecl *D) {
327     Inherited::VisitTypedefDecl(D);
328   }
329 
330   void VisitTypeAliasDecl(const TypeAliasDecl *D) {
331     Inherited::VisitTypeAliasDecl(D);
332   }
333 };
334 
335 // Only allow a small portion of Decl's to be processed.  Remove this once
336 // all Decl's can be handled.
337 bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
338   if (D->isImplicit()) return false;
339   if (D->getDeclContext() != Parent) return false;
340 
341   switch (D->getKind()) {
342     default:
343       return false;
344     case Decl::AccessSpec:
345     case Decl::CXXMethod:
346     case Decl::Field:
347     case Decl::StaticAssert:
348     case Decl::TypeAlias:
349     case Decl::Typedef:
350     case Decl::Var:
351       return true;
352   }
353 }
354 
355 void ODRHash::AddSubDecl(const Decl *D) {
356   assert(D && "Expecting non-null pointer.");
357   AddDecl(D);
358 
359   ODRDeclVisitor(ID, *this).Visit(D);
360 }
361 
362 void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
363   assert(Record && Record->hasDefinition() &&
364          "Expected non-null record to be a definition.");
365 
366   if (isa<ClassTemplateSpecializationDecl>(Record)) {
367     return;
368   }
369 
370   AddDecl(Record);
371 
372   // Filter out sub-Decls which will not be processed in order to get an
373   // accurate count of Decl's.
374   llvm::SmallVector<const Decl *, 16> Decls;
375   for (const Decl *SubDecl : Record->decls()) {
376     if (isWhitelistedDecl(SubDecl, Record)) {
377       Decls.push_back(SubDecl);
378     }
379   }
380 
381   ID.AddInteger(Decls.size());
382   for (auto SubDecl : Decls) {
383     AddSubDecl(SubDecl);
384   }
385 }
386 
387 void ODRHash::AddDecl(const Decl *D) {
388   assert(D && "Expecting non-null pointer.");
389   auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
390   ID.AddInteger(Result.first->second);
391   // On first encounter of a Decl pointer, process it.  Every time afterwards,
392   // only the index value is needed.
393   if (!Result.second) {
394     return;
395   }
396 
397   ID.AddInteger(D->getKind());
398 
399   if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
400     AddDeclarationName(ND->getDeclName());
401   }
402 }
403 
404 // Process a Type pointer.  Add* methods call back into ODRHash while Visit*
405 // methods process the relevant parts of the Type.
406 class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
407   typedef TypeVisitor<ODRTypeVisitor> Inherited;
408   llvm::FoldingSetNodeID &ID;
409   ODRHash &Hash;
410 
411 public:
412   ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
413       : ID(ID), Hash(Hash) {}
414 
415   void AddStmt(Stmt *S) {
416     Hash.AddBoolean(S);
417     if (S) {
418       Hash.AddStmt(S);
419     }
420   }
421 
422   void AddDecl(Decl *D) {
423     Hash.AddBoolean(D);
424     if (D) {
425       Hash.AddDecl(D);
426     }
427   }
428 
429   void AddQualType(QualType T) {
430     Hash.AddQualType(T);
431   }
432 
433   void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
434     Hash.AddNestedNameSpecifier(NNS);
435   }
436 
437   void AddIdentifierInfo(const IdentifierInfo *II) {
438     Hash.AddBoolean(II);
439     if (II) {
440       Hash.AddIdentifierInfo(II);
441     }
442   }
443 
444   void VisitQualifiers(Qualifiers Quals) {
445     ID.AddInteger(Quals.getAsOpaqueValue());
446   }
447 
448   void Visit(const Type *T) {
449     ID.AddInteger(T->getTypeClass());
450     Inherited::Visit(T);
451   }
452 
453   void VisitType(const Type *T) {}
454 
455   void VisitAdjustedType(const AdjustedType *T) {
456     AddQualType(T->getOriginalType());
457     AddQualType(T->getAdjustedType());
458     VisitType(T);
459   }
460 
461   void VisitDecayedType(const DecayedType *T) {
462     AddQualType(T->getDecayedType());
463     AddQualType(T->getPointeeType());
464     VisitAdjustedType(T);
465   }
466 
467   void VisitArrayType(const ArrayType *T) {
468     AddQualType(T->getElementType());
469     ID.AddInteger(T->getSizeModifier());
470     VisitQualifiers(T->getIndexTypeQualifiers());
471     VisitType(T);
472   }
473   void VisitConstantArrayType(const ConstantArrayType *T) {
474     T->getSize().Profile(ID);
475     VisitArrayType(T);
476   }
477 
478   void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
479     AddStmt(T->getSizeExpr());
480     VisitArrayType(T);
481   }
482 
483   void VisitIncompleteArrayType(const IncompleteArrayType *T) {
484     VisitArrayType(T);
485   }
486 
487   void VisitVariableArrayType(const VariableArrayType *T) {
488     AddStmt(T->getSizeExpr());
489     VisitArrayType(T);
490   }
491 
492   void VisitBuiltinType(const BuiltinType *T) {
493     ID.AddInteger(T->getKind());
494     VisitType(T);
495   }
496 
497   void VisitFunctionType(const FunctionType *T) {
498     AddQualType(T->getReturnType());
499     T->getExtInfo().Profile(ID);
500     Hash.AddBoolean(T->isConst());
501     Hash.AddBoolean(T->isVolatile());
502     Hash.AddBoolean(T->isRestrict());
503     VisitType(T);
504   }
505 
506   void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
507     VisitFunctionType(T);
508   }
509 
510   void VisitFunctionProtoType(const FunctionProtoType *T) {
511     ID.AddInteger(T->getNumParams());
512     for (auto ParamType : T->getParamTypes())
513       AddQualType(ParamType);
514 
515     VisitFunctionType(T);
516   }
517 
518   void VisitTypedefType(const TypedefType *T) {
519     AddDecl(T->getDecl());
520     AddQualType(T->getDecl()->getUnderlyingType().getCanonicalType());
521     VisitType(T);
522   }
523 
524   void VisitTagType(const TagType *T) {
525     AddDecl(T->getDecl());
526     VisitType(T);
527   }
528 
529   void VisitRecordType(const RecordType *T) { VisitTagType(T); }
530   void VisitEnumType(const EnumType *T) { VisitTagType(T); }
531 
532   void VisitTypeWithKeyword(const TypeWithKeyword *T) {
533     ID.AddInteger(T->getKeyword());
534     VisitType(T);
535   };
536 
537   void VisitDependentNameType(const DependentNameType *T) {
538     AddNestedNameSpecifier(T->getQualifier());
539     AddIdentifierInfo(T->getIdentifier());
540     VisitTypeWithKeyword(T);
541   }
542 
543   void VisitDependentTemplateSpecializationType(
544       const DependentTemplateSpecializationType *T) {
545     AddIdentifierInfo(T->getIdentifier());
546     AddNestedNameSpecifier(T->getQualifier());
547     ID.AddInteger(T->getNumArgs());
548     for (const auto &TA : T->template_arguments()) {
549       Hash.AddTemplateArgument(TA);
550     }
551     VisitTypeWithKeyword(T);
552   }
553 
554   void VisitElaboratedType(const ElaboratedType *T) {
555     AddNestedNameSpecifier(T->getQualifier());
556     AddQualType(T->getNamedType());
557     VisitTypeWithKeyword(T);
558   }
559 
560   void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
561     ID.AddInteger(T->getNumArgs());
562     for (const auto &TA : T->template_arguments()) {
563       Hash.AddTemplateArgument(TA);
564     }
565     Hash.AddTemplateName(T->getTemplateName());
566     VisitType(T);
567   }
568 
569   void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
570     ID.AddInteger(T->getDepth());
571     ID.AddInteger(T->getIndex());
572     Hash.AddBoolean(T->isParameterPack());
573     AddDecl(T->getDecl());
574   }
575 };
576 
577 void ODRHash::AddType(const Type *T) {
578   assert(T && "Expecting non-null pointer.");
579   auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
580   ID.AddInteger(Result.first->second);
581   // On first encounter of a Type pointer, process it.  Every time afterwards,
582   // only the index value is needed.
583   if (!Result.second) {
584     return;
585   }
586 
587   ODRTypeVisitor(ID, *this).Visit(T);
588 }
589 
590 void ODRHash::AddQualType(QualType T) {
591   AddBoolean(T.isNull());
592   if (T.isNull())
593     return;
594   SplitQualType split = T.split();
595   ID.AddInteger(split.Quals.getAsOpaqueValue());
596   AddType(split.Ty);
597 }
598 
599 void ODRHash::AddBoolean(bool Value) {
600   Bools.push_back(Value);
601 }
602