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 }
548