ODRHash.cpp revision 320970 
1137587Snik//===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
2137587Snik//
3137587Snik//                     The LLVM Compiler Infrastructure
4137587Snik//
5137587Snik// This file is distributed under the University of Illinois Open Source
6137587Snik// License. See LICENSE.TXT for details.
7137587Snik//
8137587Snik//===----------------------------------------------------------------------===//
9137587Snik///
10137587Snik/// \file
11137587Snik/// This file implements the ODRHash class, which calculates a hash based
12137587Snik/// on AST nodes, which is stable across different runs.
13137587Snik///
14137587Snik//===----------------------------------------------------------------------===//
15137587Snik
16137587Snik#include "clang/AST/ODRHash.h"
17137587Snik
18137587Snik#include "clang/AST/DeclVisitor.h"
19137587Snik#include "clang/AST/NestedNameSpecifier.h"
20137587Snik#include "clang/AST/StmtVisitor.h"
21137587Snik#include "clang/AST/TypeVisitor.h"
22137587Snik
23137587Snikusing namespace clang;
24137587Snik
25137587Snikvoid ODRHash::AddStmt(const Stmt *S) {
26137587Snik  assert(S && "Expecting non-null pointer.");
27137587Snik  S->ProcessODRHash(ID, *this);
28137587Snik}
29137587Snik
30137587Snikvoid ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
31137587Snik  assert(II && "Expecting non-null pointer.");
32137587Snik  ID.AddString(II->getName());
33137587Snik}
34137587Snik
35137587Snikvoid ODRHash::AddDeclarationName(DeclarationName Name) {
36137587Snik  AddBoolean(Name.isEmpty());
37137587Snik  if (Name.isEmpty())
38137587Snik    return;
39137587Snik
40137587Snik  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
84void 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
113void 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
131void 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
161void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {}
162
163void ODRHash::clear() {
164  DeclMap.clear();
165  TypeMap.clear();
166  Bools.clear();
167  ID.clear();
168}
169
170unsigned 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// Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
203// methods process the relevant parts of the Decl.
204class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
205  typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
206  llvm::FoldingSetNodeID &ID;
207  ODRHash &Hash;
208
209public:
210  ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
211      : ID(ID), Hash(Hash) {}
212
213  void AddStmt(const Stmt *S) {
214    Hash.AddBoolean(S);
215    if (S) {
216      Hash.AddStmt(S);
217    }
218  }
219
220  void AddIdentifierInfo(const IdentifierInfo *II) {
221    Hash.AddBoolean(II);
222    if (II) {
223      Hash.AddIdentifierInfo(II);
224    }
225  }
226
227  void AddQualType(QualType T) {
228    Hash.AddQualType(T);
229  }
230
231  void AddDecl(const Decl *D) {
232    Hash.AddBoolean(D);
233    if (D) {
234      Hash.AddDecl(D);
235    }
236  }
237
238  void Visit(const Decl *D) {
239    ID.AddInteger(D->getKind());
240    Inherited::Visit(D);
241  }
242
243  void VisitNamedDecl(const NamedDecl *D) {
244    Hash.AddDeclarationName(D->getDeclName());
245    Inherited::VisitNamedDecl(D);
246  }
247
248  void VisitValueDecl(const ValueDecl *D) {
249    AddQualType(D->getType());
250    Inherited::VisitValueDecl(D);
251  }
252
253  void VisitVarDecl(const VarDecl *D) {
254    Hash.AddBoolean(D->isStaticLocal());
255    Hash.AddBoolean(D->isConstexpr());
256    const bool HasInit = D->hasInit();
257    Hash.AddBoolean(HasInit);
258    if (HasInit) {
259      AddStmt(D->getInit());
260    }
261    Inherited::VisitVarDecl(D);
262  }
263
264  void VisitParmVarDecl(const ParmVarDecl *D) {
265    // TODO: Handle default arguments.
266    Inherited::VisitParmVarDecl(D);
267  }
268
269  void VisitAccessSpecDecl(const AccessSpecDecl *D) {
270    ID.AddInteger(D->getAccess());
271    Inherited::VisitAccessSpecDecl(D);
272  }
273
274  void VisitStaticAssertDecl(const StaticAssertDecl *D) {
275    AddStmt(D->getAssertExpr());
276    AddStmt(D->getMessage());
277
278    Inherited::VisitStaticAssertDecl(D);
279  }
280
281  void VisitFieldDecl(const FieldDecl *D) {
282    const bool IsBitfield = D->isBitField();
283    Hash.AddBoolean(IsBitfield);
284
285    if (IsBitfield) {
286      AddStmt(D->getBitWidth());
287    }
288
289    Hash.AddBoolean(D->isMutable());
290    AddStmt(D->getInClassInitializer());
291
292    Inherited::VisitFieldDecl(D);
293  }
294
295  void VisitFunctionDecl(const FunctionDecl *D) {
296    ID.AddInteger(D->getStorageClass());
297    Hash.AddBoolean(D->isInlineSpecified());
298    Hash.AddBoolean(D->isVirtualAsWritten());
299    Hash.AddBoolean(D->isPure());
300    Hash.AddBoolean(D->isDeletedAsWritten());
301
302    ID.AddInteger(D->param_size());
303
304    for (auto *Param : D->parameters()) {
305      Hash.AddSubDecl(Param);
306    }
307
308    Inherited::VisitFunctionDecl(D);
309  }
310
311  void VisitCXXMethodDecl(const CXXMethodDecl *D) {
312    Hash.AddBoolean(D->isConst());
313    Hash.AddBoolean(D->isVolatile());
314
315    Inherited::VisitCXXMethodDecl(D);
316  }
317
318  void VisitTypedefNameDecl(const TypedefNameDecl *D) {
319    AddQualType(D->getUnderlyingType());
320
321    Inherited::VisitTypedefNameDecl(D);
322  }
323
324  void VisitTypedefDecl(const TypedefDecl *D) {
325    Inherited::VisitTypedefDecl(D);
326  }
327
328  void VisitTypeAliasDecl(const TypeAliasDecl *D) {
329    Inherited::VisitTypeAliasDecl(D);
330  }
331
332  void VisitFriendDecl(const FriendDecl *D) {
333    TypeSourceInfo *TSI = D->getFriendType();
334    Hash.AddBoolean(TSI);
335    if (TSI) {
336      AddQualType(TSI->getType());
337    } else {
338      AddDecl(D->getFriendDecl());
339    }
340  }
341};
342
343// Only allow a small portion of Decl's to be processed.  Remove this once
344// all Decl's can be handled.
345bool ODRHash::isWhitelistedDecl(const Decl *D, const CXXRecordDecl *Parent) {
346  if (D->isImplicit()) return false;
347  if (D->getDeclContext() != Parent) return false;
348
349  switch (D->getKind()) {
350    default:
351      return false;
352    case Decl::AccessSpec:
353    case Decl::CXXMethod:
354    case Decl::Field:
355    case Decl::Friend:
356    case Decl::StaticAssert:
357    case Decl::TypeAlias:
358    case Decl::Typedef:
359    case Decl::Var:
360      return true;
361  }
362}
363
364void ODRHash::AddSubDecl(const Decl *D) {
365  assert(D && "Expecting non-null pointer.");
366  AddDecl(D);
367
368  ODRDeclVisitor(ID, *this).Visit(D);
369}
370
371void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
372  assert(Record && Record->hasDefinition() &&
373         "Expected non-null record to be a definition.");
374
375  if (isa<ClassTemplateSpecializationDecl>(Record)) {
376    return;
377  }
378
379  AddDecl(Record);
380
381  // Filter out sub-Decls which will not be processed in order to get an
382  // accurate count of Decl's.
383  llvm::SmallVector<const Decl *, 16> Decls;
384  for (const Decl *SubDecl : Record->decls()) {
385    if (isWhitelistedDecl(SubDecl, Record)) {
386      Decls.push_back(SubDecl);
387    }
388  }
389
390  ID.AddInteger(Decls.size());
391  for (auto SubDecl : Decls) {
392    AddSubDecl(SubDecl);
393  }
394}
395
396void ODRHash::AddDecl(const Decl *D) {
397  assert(D && "Expecting non-null pointer.");
398  auto Result = DeclMap.insert(std::make_pair(D, DeclMap.size()));
399  ID.AddInteger(Result.first->second);
400  // On first encounter of a Decl pointer, process it.  Every time afterwards,
401  // only the index value is needed.
402  if (!Result.second) {
403    return;
404  }
405
406  ID.AddInteger(D->getKind());
407
408  if (const NamedDecl *ND = dyn_cast<NamedDecl>(D)) {
409    AddDeclarationName(ND->getDeclName());
410  }
411}
412
413// Process a Type pointer.  Add* methods call back into ODRHash while Visit*
414// methods process the relevant parts of the Type.
415class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
416  typedef TypeVisitor<ODRTypeVisitor> Inherited;
417  llvm::FoldingSetNodeID &ID;
418  ODRHash &Hash;
419
420public:
421  ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
422      : ID(ID), Hash(Hash) {}
423
424  void AddStmt(Stmt *S) {
425    Hash.AddBoolean(S);
426    if (S) {
427      Hash.AddStmt(S);
428    }
429  }
430
431  void AddDecl(Decl *D) {
432    Hash.AddBoolean(D);
433    if (D) {
434      Hash.AddDecl(D);
435    }
436  }
437
438  void AddQualType(QualType T) {
439    Hash.AddQualType(T);
440  }
441
442  void AddType(const Type *T) {
443    Hash.AddBoolean(T);
444    if (T) {
445      Hash.AddType(T);
446    }
447  }
448
449  void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
450    Hash.AddBoolean(NNS);
451    if (NNS) {
452      Hash.AddNestedNameSpecifier(NNS);
453    }
454  }
455
456  void AddIdentifierInfo(const IdentifierInfo *II) {
457    Hash.AddBoolean(II);
458    if (II) {
459      Hash.AddIdentifierInfo(II);
460    }
461  }
462
463  void VisitQualifiers(Qualifiers Quals) {
464    ID.AddInteger(Quals.getAsOpaqueValue());
465  }
466
467  void Visit(const Type *T) {
468    ID.AddInteger(T->getTypeClass());
469    Inherited::Visit(T);
470  }
471
472  void VisitType(const Type *T) {}
473
474  void VisitAdjustedType(const AdjustedType *T) {
475    AddQualType(T->getOriginalType());
476    AddQualType(T->getAdjustedType());
477    VisitType(T);
478  }
479
480  void VisitDecayedType(const DecayedType *T) {
481    AddQualType(T->getDecayedType());
482    AddQualType(T->getPointeeType());
483    VisitAdjustedType(T);
484  }
485
486  void VisitArrayType(const ArrayType *T) {
487    AddQualType(T->getElementType());
488    ID.AddInteger(T->getSizeModifier());
489    VisitQualifiers(T->getIndexTypeQualifiers());
490    VisitType(T);
491  }
492  void VisitConstantArrayType(const ConstantArrayType *T) {
493    T->getSize().Profile(ID);
494    VisitArrayType(T);
495  }
496
497  void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
498    AddStmt(T->getSizeExpr());
499    VisitArrayType(T);
500  }
501
502  void VisitIncompleteArrayType(const IncompleteArrayType *T) {
503    VisitArrayType(T);
504  }
505
506  void VisitVariableArrayType(const VariableArrayType *T) {
507    AddStmt(T->getSizeExpr());
508    VisitArrayType(T);
509  }
510
511  void VisitBuiltinType(const BuiltinType *T) {
512    ID.AddInteger(T->getKind());
513    VisitType(T);
514  }
515
516  void VisitFunctionType(const FunctionType *T) {
517    AddQualType(T->getReturnType());
518    T->getExtInfo().Profile(ID);
519    Hash.AddBoolean(T->isConst());
520    Hash.AddBoolean(T->isVolatile());
521    Hash.AddBoolean(T->isRestrict());
522    VisitType(T);
523  }
524
525  void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
526    VisitFunctionType(T);
527  }
528
529  void VisitFunctionProtoType(const FunctionProtoType *T) {
530    ID.AddInteger(T->getNumParams());
531    for (auto ParamType : T->getParamTypes())
532      AddQualType(ParamType);
533
534    VisitFunctionType(T);
535  }
536
537  void VisitTypedefType(const TypedefType *T) {
538    AddDecl(T->getDecl());
539    QualType UnderlyingType = T->getDecl()->getUnderlyingType();
540    VisitQualifiers(UnderlyingType.getQualifiers());
541    while (const TypedefType *Underlying =
542               dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
543      UnderlyingType = Underlying->getDecl()->getUnderlyingType();
544    }
545    AddType(UnderlyingType.getTypePtr());
546    VisitType(T);
547  }
548
549  void VisitTagType(const TagType *T) {
550    AddDecl(T->getDecl());
551    VisitType(T);
552  }
553
554  void VisitRecordType(const RecordType *T) { VisitTagType(T); }
555  void VisitEnumType(const EnumType *T) { VisitTagType(T); }
556
557  void VisitTypeWithKeyword(const TypeWithKeyword *T) {
558    ID.AddInteger(T->getKeyword());
559    VisitType(T);
560  };
561
562  void VisitDependentNameType(const DependentNameType *T) {
563    AddNestedNameSpecifier(T->getQualifier());
564    AddIdentifierInfo(T->getIdentifier());
565    VisitTypeWithKeyword(T);
566  }
567
568  void VisitDependentTemplateSpecializationType(
569      const DependentTemplateSpecializationType *T) {
570    AddIdentifierInfo(T->getIdentifier());
571    AddNestedNameSpecifier(T->getQualifier());
572    ID.AddInteger(T->getNumArgs());
573    for (const auto &TA : T->template_arguments()) {
574      Hash.AddTemplateArgument(TA);
575    }
576    VisitTypeWithKeyword(T);
577  }
578
579  void VisitElaboratedType(const ElaboratedType *T) {
580    AddNestedNameSpecifier(T->getQualifier());
581    AddQualType(T->getNamedType());
582    VisitTypeWithKeyword(T);
583  }
584
585  void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
586    ID.AddInteger(T->getNumArgs());
587    for (const auto &TA : T->template_arguments()) {
588      Hash.AddTemplateArgument(TA);
589    }
590    Hash.AddTemplateName(T->getTemplateName());
591    VisitType(T);
592  }
593
594  void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
595    ID.AddInteger(T->getDepth());
596    ID.AddInteger(T->getIndex());
597    Hash.AddBoolean(T->isParameterPack());
598    AddDecl(T->getDecl());
599  }
600};
601
602void ODRHash::AddType(const Type *T) {
603  assert(T && "Expecting non-null pointer.");
604  auto Result = TypeMap.insert(std::make_pair(T, TypeMap.size()));
605  ID.AddInteger(Result.first->second);
606  // On first encounter of a Type pointer, process it.  Every time afterwards,
607  // only the index value is needed.
608  if (!Result.second) {
609    return;
610  }
611
612  ODRTypeVisitor(ID, *this).Visit(T);
613}
614
615void ODRHash::AddQualType(QualType T) {
616  AddBoolean(T.isNull());
617  if (T.isNull())
618    return;
619  SplitQualType split = T.split();
620  ID.AddInteger(split.Quals.getAsOpaqueValue());
621  AddType(split.Ty);
622}
623
624void ODRHash::AddBoolean(bool Value) {
625  Bools.push_back(Value);
626}
627