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