ODRHash.cpp revision 360784 
1//===-- ODRHash.cpp - Hashing to diagnose ODR failures ----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements the ODRHash class, which calculates a hash based
11/// on AST nodes, which is stable across different runs.
12///
13//===----------------------------------------------------------------------===//
14
15#include "clang/AST/ODRHash.h"
16
17#include "clang/AST/DeclVisitor.h"
18#include "clang/AST/NestedNameSpecifier.h"
19#include "clang/AST/StmtVisitor.h"
20#include "clang/AST/TypeVisitor.h"
21
22using namespace clang;
23
24void ODRHash::AddStmt(const Stmt *S) {
25  assert(S && "Expecting non-null pointer.");
26  S->ProcessODRHash(ID, *this);
27}
28
29void ODRHash::AddIdentifierInfo(const IdentifierInfo *II) {
30  assert(II && "Expecting non-null pointer.");
31  ID.AddString(II->getName());
32}
33
34void ODRHash::AddDeclarationName(DeclarationName Name, bool TreatAsDecl) {
35  if (TreatAsDecl)
36    // Matches the NamedDecl check in AddDecl
37    AddBoolean(true);
38
39  AddDeclarationNameImpl(Name);
40
41  if (TreatAsDecl)
42    // Matches the ClassTemplateSpecializationDecl check in AddDecl
43    AddBoolean(false);
44}
45
46void ODRHash::AddDeclarationNameImpl(DeclarationName Name) {
47  // Index all DeclarationName and use index numbers to refer to them.
48  auto Result = DeclNameMap.insert(std::make_pair(Name, DeclNameMap.size()));
49  ID.AddInteger(Result.first->second);
50  if (!Result.second) {
51    // If found in map, the DeclarationName has previously been processed.
52    return;
53  }
54
55  // First time processing each DeclarationName, also process its details.
56  AddBoolean(Name.isEmpty());
57  if (Name.isEmpty())
58    return;
59
60  auto Kind = Name.getNameKind();
61  ID.AddInteger(Kind);
62  switch (Kind) {
63  case DeclarationName::Identifier:
64    AddIdentifierInfo(Name.getAsIdentifierInfo());
65    break;
66  case DeclarationName::ObjCZeroArgSelector:
67  case DeclarationName::ObjCOneArgSelector:
68  case DeclarationName::ObjCMultiArgSelector: {
69    Selector S = Name.getObjCSelector();
70    AddBoolean(S.isNull());
71    AddBoolean(S.isKeywordSelector());
72    AddBoolean(S.isUnarySelector());
73    unsigned NumArgs = S.getNumArgs();
74    ID.AddInteger(NumArgs);
75    for (unsigned i = 0; i < NumArgs; ++i) {
76      const IdentifierInfo *II = S.getIdentifierInfoForSlot(i);
77      AddBoolean(II);
78      if (II) {
79        AddIdentifierInfo(II);
80      }
81    }
82    break;
83  }
84  case DeclarationName::CXXConstructorName:
85  case DeclarationName::CXXDestructorName:
86    AddQualType(Name.getCXXNameType());
87    break;
88  case DeclarationName::CXXOperatorName:
89    ID.AddInteger(Name.getCXXOverloadedOperator());
90    break;
91  case DeclarationName::CXXLiteralOperatorName:
92    AddIdentifierInfo(Name.getCXXLiteralIdentifier());
93    break;
94  case DeclarationName::CXXConversionFunctionName:
95    AddQualType(Name.getCXXNameType());
96    break;
97  case DeclarationName::CXXUsingDirective:
98    break;
99  case DeclarationName::CXXDeductionGuideName: {
100    auto *Template = Name.getCXXDeductionGuideTemplate();
101    AddBoolean(Template);
102    if (Template) {
103      AddDecl(Template);
104    }
105  }
106  }
107}
108
109void ODRHash::AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
110  assert(NNS && "Expecting non-null pointer.");
111  const auto *Prefix = NNS->getPrefix();
112  AddBoolean(Prefix);
113  if (Prefix) {
114    AddNestedNameSpecifier(Prefix);
115  }
116  auto Kind = NNS->getKind();
117  ID.AddInteger(Kind);
118  switch (Kind) {
119  case NestedNameSpecifier::Identifier:
120    AddIdentifierInfo(NNS->getAsIdentifier());
121    break;
122  case NestedNameSpecifier::Namespace:
123    AddDecl(NNS->getAsNamespace());
124    break;
125  case NestedNameSpecifier::NamespaceAlias:
126    AddDecl(NNS->getAsNamespaceAlias());
127    break;
128  case NestedNameSpecifier::TypeSpec:
129  case NestedNameSpecifier::TypeSpecWithTemplate:
130    AddType(NNS->getAsType());
131    break;
132  case NestedNameSpecifier::Global:
133  case NestedNameSpecifier::Super:
134    break;
135  }
136}
137
138void ODRHash::AddTemplateName(TemplateName Name) {
139  auto Kind = Name.getKind();
140  ID.AddInteger(Kind);
141
142  switch (Kind) {
143  case TemplateName::Template:
144    AddDecl(Name.getAsTemplateDecl());
145    break;
146  // TODO: Support these cases.
147  case TemplateName::OverloadedTemplate:
148  case TemplateName::AssumedTemplate:
149  case TemplateName::QualifiedTemplate:
150  case TemplateName::DependentTemplate:
151  case TemplateName::SubstTemplateTemplateParm:
152  case TemplateName::SubstTemplateTemplateParmPack:
153    break;
154  }
155}
156
157void ODRHash::AddTemplateArgument(TemplateArgument TA) {
158  const auto Kind = TA.getKind();
159  ID.AddInteger(Kind);
160
161  switch (Kind) {
162    case TemplateArgument::Null:
163      llvm_unreachable("Expected valid TemplateArgument");
164    case TemplateArgument::Type:
165      AddQualType(TA.getAsType());
166      break;
167    case TemplateArgument::Declaration:
168      AddDecl(TA.getAsDecl());
169      break;
170    case TemplateArgument::NullPtr:
171    case TemplateArgument::Integral:
172      break;
173    case TemplateArgument::Template:
174    case TemplateArgument::TemplateExpansion:
175      AddTemplateName(TA.getAsTemplateOrTemplatePattern());
176      break;
177    case TemplateArgument::Expression:
178      AddStmt(TA.getAsExpr());
179      break;
180    case TemplateArgument::Pack:
181      ID.AddInteger(TA.pack_size());
182      for (auto SubTA : TA.pack_elements()) {
183        AddTemplateArgument(SubTA);
184      }
185      break;
186  }
187}
188
189void ODRHash::AddTemplateParameterList(const TemplateParameterList *TPL) {
190  assert(TPL && "Expecting non-null pointer.");
191
192  ID.AddInteger(TPL->size());
193  for (auto *ND : TPL->asArray()) {
194    AddSubDecl(ND);
195  }
196}
197
198void ODRHash::clear() {
199  DeclNameMap.clear();
200  Bools.clear();
201  ID.clear();
202}
203
204unsigned ODRHash::CalculateHash() {
205  // Append the bools to the end of the data segment backwards.  This allows
206  // for the bools data to be compressed 32 times smaller compared to using
207  // ID.AddBoolean
208  const unsigned unsigned_bits = sizeof(unsigned) * CHAR_BIT;
209  const unsigned size = Bools.size();
210  const unsigned remainder = size % unsigned_bits;
211  const unsigned loops = size / unsigned_bits;
212  auto I = Bools.rbegin();
213  unsigned value = 0;
214  for (unsigned i = 0; i < remainder; ++i) {
215    value <<= 1;
216    value |= *I;
217    ++I;
218  }
219  ID.AddInteger(value);
220
221  for (unsigned i = 0; i < loops; ++i) {
222    value = 0;
223    for (unsigned j = 0; j < unsigned_bits; ++j) {
224      value <<= 1;
225      value |= *I;
226      ++I;
227    }
228    ID.AddInteger(value);
229  }
230
231  assert(I == Bools.rend());
232  Bools.clear();
233  return ID.ComputeHash();
234}
235
236namespace {
237// Process a Decl pointer.  Add* methods call back into ODRHash while Visit*
238// methods process the relevant parts of the Decl.
239class ODRDeclVisitor : public ConstDeclVisitor<ODRDeclVisitor> {
240  typedef ConstDeclVisitor<ODRDeclVisitor> Inherited;
241  llvm::FoldingSetNodeID &ID;
242  ODRHash &Hash;
243
244public:
245  ODRDeclVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
246      : ID(ID), Hash(Hash) {}
247
248  void AddStmt(const Stmt *S) {
249    Hash.AddBoolean(S);
250    if (S) {
251      Hash.AddStmt(S);
252    }
253  }
254
255  void AddIdentifierInfo(const IdentifierInfo *II) {
256    Hash.AddBoolean(II);
257    if (II) {
258      Hash.AddIdentifierInfo(II);
259    }
260  }
261
262  void AddQualType(QualType T) {
263    Hash.AddQualType(T);
264  }
265
266  void AddDecl(const Decl *D) {
267    Hash.AddBoolean(D);
268    if (D) {
269      Hash.AddDecl(D);
270    }
271  }
272
273  void AddTemplateArgument(TemplateArgument TA) {
274    Hash.AddTemplateArgument(TA);
275  }
276
277  void Visit(const Decl *D) {
278    ID.AddInteger(D->getKind());
279    Inherited::Visit(D);
280  }
281
282  void VisitNamedDecl(const NamedDecl *D) {
283    Hash.AddDeclarationName(D->getDeclName());
284    Inherited::VisitNamedDecl(D);
285  }
286
287  void VisitValueDecl(const ValueDecl *D) {
288    if (!isa<FunctionDecl>(D)) {
289      AddQualType(D->getType());
290    }
291    Inherited::VisitValueDecl(D);
292  }
293
294  void VisitVarDecl(const VarDecl *D) {
295    Hash.AddBoolean(D->isStaticLocal());
296    Hash.AddBoolean(D->isConstexpr());
297    const bool HasInit = D->hasInit();
298    Hash.AddBoolean(HasInit);
299    if (HasInit) {
300      AddStmt(D->getInit());
301    }
302    Inherited::VisitVarDecl(D);
303  }
304
305  void VisitParmVarDecl(const ParmVarDecl *D) {
306    // TODO: Handle default arguments.
307    Inherited::VisitParmVarDecl(D);
308  }
309
310  void VisitAccessSpecDecl(const AccessSpecDecl *D) {
311    ID.AddInteger(D->getAccess());
312    Inherited::VisitAccessSpecDecl(D);
313  }
314
315  void VisitStaticAssertDecl(const StaticAssertDecl *D) {
316    AddStmt(D->getAssertExpr());
317    AddStmt(D->getMessage());
318
319    Inherited::VisitStaticAssertDecl(D);
320  }
321
322  void VisitFieldDecl(const FieldDecl *D) {
323    const bool IsBitfield = D->isBitField();
324    Hash.AddBoolean(IsBitfield);
325
326    if (IsBitfield) {
327      AddStmt(D->getBitWidth());
328    }
329
330    Hash.AddBoolean(D->isMutable());
331    AddStmt(D->getInClassInitializer());
332
333    Inherited::VisitFieldDecl(D);
334  }
335
336  void VisitFunctionDecl(const FunctionDecl *D) {
337    // Handled by the ODRHash for FunctionDecl
338    ID.AddInteger(D->getODRHash());
339
340    Inherited::VisitFunctionDecl(D);
341  }
342
343  void VisitCXXMethodDecl(const CXXMethodDecl *D) {
344    // Handled by the ODRHash for FunctionDecl
345
346    Inherited::VisitCXXMethodDecl(D);
347  }
348
349  void VisitTypedefNameDecl(const TypedefNameDecl *D) {
350    AddQualType(D->getUnderlyingType());
351
352    Inherited::VisitTypedefNameDecl(D);
353  }
354
355  void VisitTypedefDecl(const TypedefDecl *D) {
356    Inherited::VisitTypedefDecl(D);
357  }
358
359  void VisitTypeAliasDecl(const TypeAliasDecl *D) {
360    Inherited::VisitTypeAliasDecl(D);
361  }
362
363  void VisitFriendDecl(const FriendDecl *D) {
364    TypeSourceInfo *TSI = D->getFriendType();
365    Hash.AddBoolean(TSI);
366    if (TSI) {
367      AddQualType(TSI->getType());
368    } else {
369      AddDecl(D->getFriendDecl());
370    }
371  }
372
373  void VisitTemplateTypeParmDecl(const TemplateTypeParmDecl *D) {
374    // Only care about default arguments as part of the definition.
375    const bool hasDefaultArgument =
376        D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
377    Hash.AddBoolean(hasDefaultArgument);
378    if (hasDefaultArgument) {
379      AddTemplateArgument(D->getDefaultArgument());
380    }
381    Hash.AddBoolean(D->isParameterPack());
382
383    const TypeConstraint *TC = D->getTypeConstraint();
384    Hash.AddBoolean(TC != nullptr);
385    if (TC)
386      AddStmt(TC->getImmediatelyDeclaredConstraint());
387
388    Inherited::VisitTemplateTypeParmDecl(D);
389  }
390
391  void VisitNonTypeTemplateParmDecl(const NonTypeTemplateParmDecl *D) {
392    // Only care about default arguments as part of the definition.
393    const bool hasDefaultArgument =
394        D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
395    Hash.AddBoolean(hasDefaultArgument);
396    if (hasDefaultArgument) {
397      AddStmt(D->getDefaultArgument());
398    }
399    Hash.AddBoolean(D->isParameterPack());
400
401    Inherited::VisitNonTypeTemplateParmDecl(D);
402  }
403
404  void VisitTemplateTemplateParmDecl(const TemplateTemplateParmDecl *D) {
405    // Only care about default arguments as part of the definition.
406    const bool hasDefaultArgument =
407        D->hasDefaultArgument() && !D->defaultArgumentWasInherited();
408    Hash.AddBoolean(hasDefaultArgument);
409    if (hasDefaultArgument) {
410      AddTemplateArgument(D->getDefaultArgument().getArgument());
411    }
412    Hash.AddBoolean(D->isParameterPack());
413
414    Inherited::VisitTemplateTemplateParmDecl(D);
415  }
416
417  void VisitTemplateDecl(const TemplateDecl *D) {
418    Hash.AddTemplateParameterList(D->getTemplateParameters());
419
420    Inherited::VisitTemplateDecl(D);
421  }
422
423  void VisitRedeclarableTemplateDecl(const RedeclarableTemplateDecl *D) {
424    Hash.AddBoolean(D->isMemberSpecialization());
425    Inherited::VisitRedeclarableTemplateDecl(D);
426  }
427
428  void VisitFunctionTemplateDecl(const FunctionTemplateDecl *D) {
429    AddDecl(D->getTemplatedDecl());
430    ID.AddInteger(D->getTemplatedDecl()->getODRHash());
431    Inherited::VisitFunctionTemplateDecl(D);
432  }
433
434  void VisitEnumConstantDecl(const EnumConstantDecl *D) {
435    AddStmt(D->getInitExpr());
436    Inherited::VisitEnumConstantDecl(D);
437  }
438};
439} // namespace
440
441// Only allow a small portion of Decl's to be processed.  Remove this once
442// all Decl's can be handled.
443bool ODRHash::isWhitelistedDecl(const Decl *D, const DeclContext *Parent) {
444  if (D->isImplicit()) return false;
445  if (D->getDeclContext() != Parent) return false;
446
447  switch (D->getKind()) {
448    default:
449      return false;
450    case Decl::AccessSpec:
451    case Decl::CXXConstructor:
452    case Decl::CXXDestructor:
453    case Decl::CXXMethod:
454    case Decl::EnumConstant: // Only found in EnumDecl's.
455    case Decl::Field:
456    case Decl::Friend:
457    case Decl::FunctionTemplate:
458    case Decl::StaticAssert:
459    case Decl::TypeAlias:
460    case Decl::Typedef:
461    case Decl::Var:
462      return true;
463  }
464}
465
466void ODRHash::AddSubDecl(const Decl *D) {
467  assert(D && "Expecting non-null pointer.");
468
469  ODRDeclVisitor(ID, *this).Visit(D);
470}
471
472void ODRHash::AddCXXRecordDecl(const CXXRecordDecl *Record) {
473  assert(Record && Record->hasDefinition() &&
474         "Expected non-null record to be a definition.");
475
476  const DeclContext *DC = Record;
477  while (DC) {
478    if (isa<ClassTemplateSpecializationDecl>(DC)) {
479      return;
480    }
481    DC = DC->getParent();
482  }
483
484  AddDecl(Record);
485
486  // Filter out sub-Decls which will not be processed in order to get an
487  // accurate count of Decl's.
488  llvm::SmallVector<const Decl *, 16> Decls;
489  for (Decl *SubDecl : Record->decls()) {
490    if (isWhitelistedDecl(SubDecl, Record)) {
491      Decls.push_back(SubDecl);
492      if (auto *Function = dyn_cast<FunctionDecl>(SubDecl)) {
493        // Compute/Preload ODRHash into FunctionDecl.
494        Function->getODRHash();
495      }
496    }
497  }
498
499  ID.AddInteger(Decls.size());
500  for (auto SubDecl : Decls) {
501    AddSubDecl(SubDecl);
502  }
503
504  const ClassTemplateDecl *TD = Record->getDescribedClassTemplate();
505  AddBoolean(TD);
506  if (TD) {
507    AddTemplateParameterList(TD->getTemplateParameters());
508  }
509
510  ID.AddInteger(Record->getNumBases());
511  auto Bases = Record->bases();
512  for (auto Base : Bases) {
513    AddQualType(Base.getType());
514    ID.AddInteger(Base.isVirtual());
515    ID.AddInteger(Base.getAccessSpecifierAsWritten());
516  }
517}
518
519void ODRHash::AddFunctionDecl(const FunctionDecl *Function,
520                              bool SkipBody) {
521  assert(Function && "Expecting non-null pointer.");
522
523  // Skip functions that are specializations or in specialization context.
524  const DeclContext *DC = Function;
525  while (DC) {
526    if (isa<ClassTemplateSpecializationDecl>(DC)) return;
527    if (auto *F = dyn_cast<FunctionDecl>(DC)) {
528      if (F->isFunctionTemplateSpecialization()) {
529        if (!isa<CXXMethodDecl>(DC)) return;
530        if (DC->getLexicalParent()->isFileContext()) return;
531        // Inline method specializations are the only supported
532        // specialization for now.
533      }
534    }
535    DC = DC->getParent();
536  }
537
538  ID.AddInteger(Function->getDeclKind());
539
540  const auto *SpecializationArgs = Function->getTemplateSpecializationArgs();
541  AddBoolean(SpecializationArgs);
542  if (SpecializationArgs) {
543    ID.AddInteger(SpecializationArgs->size());
544    for (const TemplateArgument &TA : SpecializationArgs->asArray()) {
545      AddTemplateArgument(TA);
546    }
547  }
548
549  if (const auto *Method = dyn_cast<CXXMethodDecl>(Function)) {
550    AddBoolean(Method->isConst());
551    AddBoolean(Method->isVolatile());
552  }
553
554  ID.AddInteger(Function->getStorageClass());
555  AddBoolean(Function->isInlineSpecified());
556  AddBoolean(Function->isVirtualAsWritten());
557  AddBoolean(Function->isPure());
558  AddBoolean(Function->isDeletedAsWritten());
559  AddBoolean(Function->isExplicitlyDefaulted());
560
561  AddDecl(Function);
562
563  AddQualType(Function->getReturnType());
564
565  ID.AddInteger(Function->param_size());
566  for (auto Param : Function->parameters())
567    AddSubDecl(Param);
568
569  if (SkipBody) {
570    AddBoolean(false);
571    return;
572  }
573
574  const bool HasBody = Function->isThisDeclarationADefinition() &&
575                       !Function->isDefaulted() && !Function->isDeleted() &&
576                       !Function->isLateTemplateParsed();
577  AddBoolean(HasBody);
578  if (!HasBody) {
579    return;
580  }
581
582  auto *Body = Function->getBody();
583  AddBoolean(Body);
584  if (Body)
585    AddStmt(Body);
586
587  // Filter out sub-Decls which will not be processed in order to get an
588  // accurate count of Decl's.
589  llvm::SmallVector<const Decl *, 16> Decls;
590  for (Decl *SubDecl : Function->decls()) {
591    if (isWhitelistedDecl(SubDecl, Function)) {
592      Decls.push_back(SubDecl);
593    }
594  }
595
596  ID.AddInteger(Decls.size());
597  for (auto SubDecl : Decls) {
598    AddSubDecl(SubDecl);
599  }
600}
601
602void ODRHash::AddEnumDecl(const EnumDecl *Enum) {
603  assert(Enum);
604  AddDeclarationName(Enum->getDeclName());
605
606  AddBoolean(Enum->isScoped());
607  if (Enum->isScoped())
608    AddBoolean(Enum->isScopedUsingClassTag());
609
610  if (Enum->getIntegerTypeSourceInfo())
611    AddQualType(Enum->getIntegerType());
612
613  // Filter out sub-Decls which will not be processed in order to get an
614  // accurate count of Decl's.
615  llvm::SmallVector<const Decl *, 16> Decls;
616  for (Decl *SubDecl : Enum->decls()) {
617    if (isWhitelistedDecl(SubDecl, Enum)) {
618      assert(isa<EnumConstantDecl>(SubDecl) && "Unexpected Decl");
619      Decls.push_back(SubDecl);
620    }
621  }
622
623  ID.AddInteger(Decls.size());
624  for (auto SubDecl : Decls) {
625    AddSubDecl(SubDecl);
626  }
627
628}
629
630void ODRHash::AddDecl(const Decl *D) {
631  assert(D && "Expecting non-null pointer.");
632  D = D->getCanonicalDecl();
633
634  const NamedDecl *ND = dyn_cast<NamedDecl>(D);
635  AddBoolean(ND);
636  if (!ND) {
637    ID.AddInteger(D->getKind());
638    return;
639  }
640
641  AddDeclarationName(ND->getDeclName());
642
643  const auto *Specialization =
644            dyn_cast<ClassTemplateSpecializationDecl>(D);
645  AddBoolean(Specialization);
646  if (Specialization) {
647    const TemplateArgumentList &List = Specialization->getTemplateArgs();
648    ID.AddInteger(List.size());
649    for (const TemplateArgument &TA : List.asArray())
650      AddTemplateArgument(TA);
651  }
652}
653
654namespace {
655// Process a Type pointer.  Add* methods call back into ODRHash while Visit*
656// methods process the relevant parts of the Type.
657class ODRTypeVisitor : public TypeVisitor<ODRTypeVisitor> {
658  typedef TypeVisitor<ODRTypeVisitor> Inherited;
659  llvm::FoldingSetNodeID &ID;
660  ODRHash &Hash;
661
662public:
663  ODRTypeVisitor(llvm::FoldingSetNodeID &ID, ODRHash &Hash)
664      : ID(ID), Hash(Hash) {}
665
666  void AddStmt(Stmt *S) {
667    Hash.AddBoolean(S);
668    if (S) {
669      Hash.AddStmt(S);
670    }
671  }
672
673  void AddDecl(Decl *D) {
674    Hash.AddBoolean(D);
675    if (D) {
676      Hash.AddDecl(D);
677    }
678  }
679
680  void AddQualType(QualType T) {
681    Hash.AddQualType(T);
682  }
683
684  void AddType(const Type *T) {
685    Hash.AddBoolean(T);
686    if (T) {
687      Hash.AddType(T);
688    }
689  }
690
691  void AddNestedNameSpecifier(const NestedNameSpecifier *NNS) {
692    Hash.AddBoolean(NNS);
693    if (NNS) {
694      Hash.AddNestedNameSpecifier(NNS);
695    }
696  }
697
698  void AddIdentifierInfo(const IdentifierInfo *II) {
699    Hash.AddBoolean(II);
700    if (II) {
701      Hash.AddIdentifierInfo(II);
702    }
703  }
704
705  void VisitQualifiers(Qualifiers Quals) {
706    ID.AddInteger(Quals.getAsOpaqueValue());
707  }
708
709  // Return the RecordType if the typedef only strips away a keyword.
710  // Otherwise, return the original type.
711  static const Type *RemoveTypedef(const Type *T) {
712    const auto *TypedefT = dyn_cast<TypedefType>(T);
713    if (!TypedefT) {
714      return T;
715    }
716
717    const TypedefNameDecl *D = TypedefT->getDecl();
718    QualType UnderlyingType = D->getUnderlyingType();
719
720    if (UnderlyingType.hasLocalQualifiers()) {
721      return T;
722    }
723
724    const auto *ElaboratedT = dyn_cast<ElaboratedType>(UnderlyingType);
725    if (!ElaboratedT) {
726      return T;
727    }
728
729    if (ElaboratedT->getQualifier() != nullptr) {
730      return T;
731    }
732
733    QualType NamedType = ElaboratedT->getNamedType();
734    if (NamedType.hasLocalQualifiers()) {
735      return T;
736    }
737
738    const auto *RecordT = dyn_cast<RecordType>(NamedType);
739    if (!RecordT) {
740      return T;
741    }
742
743    const IdentifierInfo *TypedefII = TypedefT->getDecl()->getIdentifier();
744    const IdentifierInfo *RecordII = RecordT->getDecl()->getIdentifier();
745    if (!TypedefII || !RecordII ||
746        TypedefII->getName() != RecordII->getName()) {
747      return T;
748    }
749
750    return RecordT;
751  }
752
753  void Visit(const Type *T) {
754    T = RemoveTypedef(T);
755    ID.AddInteger(T->getTypeClass());
756    Inherited::Visit(T);
757  }
758
759  void VisitType(const Type *T) {}
760
761  void VisitAdjustedType(const AdjustedType *T) {
762    QualType Original = T->getOriginalType();
763    QualType Adjusted = T->getAdjustedType();
764
765    // The original type and pointee type can be the same, as in the case of
766    // function pointers decaying to themselves.  Set a bool and only process
767    // the type once, to prevent doubling the work.
768    SplitQualType split = Adjusted.split();
769    if (auto Pointer = dyn_cast<PointerType>(split.Ty)) {
770      if (Pointer->getPointeeType() == Original) {
771        Hash.AddBoolean(true);
772        ID.AddInteger(split.Quals.getAsOpaqueValue());
773        AddQualType(Original);
774        VisitType(T);
775        return;
776      }
777    }
778
779    // The original type and pointee type are different, such as in the case
780    // of a array decaying to an element pointer.  Set a bool to false and
781    // process both types.
782    Hash.AddBoolean(false);
783    AddQualType(Original);
784    AddQualType(Adjusted);
785
786    VisitType(T);
787  }
788
789  void VisitDecayedType(const DecayedType *T) {
790    // getDecayedType and getPointeeType are derived from getAdjustedType
791    // and don't need to be separately processed.
792    VisitAdjustedType(T);
793  }
794
795  void VisitArrayType(const ArrayType *T) {
796    AddQualType(T->getElementType());
797    ID.AddInteger(T->getSizeModifier());
798    VisitQualifiers(T->getIndexTypeQualifiers());
799    VisitType(T);
800  }
801  void VisitConstantArrayType(const ConstantArrayType *T) {
802    T->getSize().Profile(ID);
803    VisitArrayType(T);
804  }
805
806  void VisitDependentSizedArrayType(const DependentSizedArrayType *T) {
807    AddStmt(T->getSizeExpr());
808    VisitArrayType(T);
809  }
810
811  void VisitIncompleteArrayType(const IncompleteArrayType *T) {
812    VisitArrayType(T);
813  }
814
815  void VisitVariableArrayType(const VariableArrayType *T) {
816    AddStmt(T->getSizeExpr());
817    VisitArrayType(T);
818  }
819
820  void VisitAttributedType(const AttributedType *T) {
821    ID.AddInteger(T->getAttrKind());
822    AddQualType(T->getModifiedType());
823    AddQualType(T->getEquivalentType());
824
825    VisitType(T);
826  }
827
828  void VisitBlockPointerType(const BlockPointerType *T) {
829    AddQualType(T->getPointeeType());
830    VisitType(T);
831  }
832
833  void VisitBuiltinType(const BuiltinType *T) {
834    ID.AddInteger(T->getKind());
835    VisitType(T);
836  }
837
838  void VisitComplexType(const ComplexType *T) {
839    AddQualType(T->getElementType());
840    VisitType(T);
841  }
842
843  void VisitDecltypeType(const DecltypeType *T) {
844    AddStmt(T->getUnderlyingExpr());
845    AddQualType(T->getUnderlyingType());
846    VisitType(T);
847  }
848
849  void VisitDependentDecltypeType(const DependentDecltypeType *T) {
850    VisitDecltypeType(T);
851  }
852
853  void VisitDeducedType(const DeducedType *T) {
854    AddQualType(T->getDeducedType());
855    VisitType(T);
856  }
857
858  void VisitAutoType(const AutoType *T) {
859    ID.AddInteger((unsigned)T->getKeyword());
860    ID.AddInteger(T->isConstrained());
861    if (T->isConstrained()) {
862      AddDecl(T->getTypeConstraintConcept());
863      ID.AddInteger(T->getNumArgs());
864      for (const auto &TA : T->getTypeConstraintArguments())
865        Hash.AddTemplateArgument(TA);
866    }
867    VisitDeducedType(T);
868  }
869
870  void VisitDeducedTemplateSpecializationType(
871      const DeducedTemplateSpecializationType *T) {
872    Hash.AddTemplateName(T->getTemplateName());
873    VisitDeducedType(T);
874  }
875
876  void VisitDependentAddressSpaceType(const DependentAddressSpaceType *T) {
877    AddQualType(T->getPointeeType());
878    AddStmt(T->getAddrSpaceExpr());
879    VisitType(T);
880  }
881
882  void VisitDependentSizedExtVectorType(const DependentSizedExtVectorType *T) {
883    AddQualType(T->getElementType());
884    AddStmt(T->getSizeExpr());
885    VisitType(T);
886  }
887
888  void VisitFunctionType(const FunctionType *T) {
889    AddQualType(T->getReturnType());
890    T->getExtInfo().Profile(ID);
891    Hash.AddBoolean(T->isConst());
892    Hash.AddBoolean(T->isVolatile());
893    Hash.AddBoolean(T->isRestrict());
894    VisitType(T);
895  }
896
897  void VisitFunctionNoProtoType(const FunctionNoProtoType *T) {
898    VisitFunctionType(T);
899  }
900
901  void VisitFunctionProtoType(const FunctionProtoType *T) {
902    ID.AddInteger(T->getNumParams());
903    for (auto ParamType : T->getParamTypes())
904      AddQualType(ParamType);
905
906    VisitFunctionType(T);
907  }
908
909  void VisitInjectedClassNameType(const InjectedClassNameType *T) {
910    AddDecl(T->getDecl());
911    VisitType(T);
912  }
913
914  void VisitMemberPointerType(const MemberPointerType *T) {
915    AddQualType(T->getPointeeType());
916    AddType(T->getClass());
917    VisitType(T);
918  }
919
920  void VisitObjCObjectPointerType(const ObjCObjectPointerType *T) {
921    AddQualType(T->getPointeeType());
922    VisitType(T);
923  }
924
925  void VisitObjCObjectType(const ObjCObjectType *T) {
926    AddDecl(T->getInterface());
927
928    auto TypeArgs = T->getTypeArgsAsWritten();
929    ID.AddInteger(TypeArgs.size());
930    for (auto Arg : TypeArgs) {
931      AddQualType(Arg);
932    }
933
934    auto Protocols = T->getProtocols();
935    ID.AddInteger(Protocols.size());
936    for (auto Protocol : Protocols) {
937      AddDecl(Protocol);
938    }
939
940    Hash.AddBoolean(T->isKindOfType());
941
942    VisitType(T);
943  }
944
945  void VisitObjCInterfaceType(const ObjCInterfaceType *T) {
946    // This type is handled by the parent type ObjCObjectType.
947    VisitObjCObjectType(T);
948  }
949
950  void VisitObjCTypeParamType(const ObjCTypeParamType *T) {
951    AddDecl(T->getDecl());
952    auto Protocols = T->getProtocols();
953    ID.AddInteger(Protocols.size());
954    for (auto Protocol : Protocols) {
955      AddDecl(Protocol);
956    }
957
958    VisitType(T);
959  }
960
961  void VisitPackExpansionType(const PackExpansionType *T) {
962    AddQualType(T->getPattern());
963    VisitType(T);
964  }
965
966  void VisitParenType(const ParenType *T) {
967    AddQualType(T->getInnerType());
968    VisitType(T);
969  }
970
971  void VisitPipeType(const PipeType *T) {
972    AddQualType(T->getElementType());
973    Hash.AddBoolean(T->isReadOnly());
974    VisitType(T);
975  }
976
977  void VisitPointerType(const PointerType *T) {
978    AddQualType(T->getPointeeType());
979    VisitType(T);
980  }
981
982  void VisitReferenceType(const ReferenceType *T) {
983    AddQualType(T->getPointeeTypeAsWritten());
984    VisitType(T);
985  }
986
987  void VisitLValueReferenceType(const LValueReferenceType *T) {
988    VisitReferenceType(T);
989  }
990
991  void VisitRValueReferenceType(const RValueReferenceType *T) {
992    VisitReferenceType(T);
993  }
994
995  void
996  VisitSubstTemplateTypeParmPackType(const SubstTemplateTypeParmPackType *T) {
997    AddType(T->getReplacedParameter());
998    Hash.AddTemplateArgument(T->getArgumentPack());
999    VisitType(T);
1000  }
1001
1002  void VisitSubstTemplateTypeParmType(const SubstTemplateTypeParmType *T) {
1003    AddType(T->getReplacedParameter());
1004    AddQualType(T->getReplacementType());
1005    VisitType(T);
1006  }
1007
1008  void VisitTagType(const TagType *T) {
1009    AddDecl(T->getDecl());
1010    VisitType(T);
1011  }
1012
1013  void VisitRecordType(const RecordType *T) { VisitTagType(T); }
1014  void VisitEnumType(const EnumType *T) { VisitTagType(T); }
1015
1016  void VisitTemplateSpecializationType(const TemplateSpecializationType *T) {
1017    ID.AddInteger(T->getNumArgs());
1018    for (const auto &TA : T->template_arguments()) {
1019      Hash.AddTemplateArgument(TA);
1020    }
1021    Hash.AddTemplateName(T->getTemplateName());
1022    VisitType(T);
1023  }
1024
1025  void VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
1026    ID.AddInteger(T->getDepth());
1027    ID.AddInteger(T->getIndex());
1028    Hash.AddBoolean(T->isParameterPack());
1029    AddDecl(T->getDecl());
1030  }
1031
1032  void VisitTypedefType(const TypedefType *T) {
1033    AddDecl(T->getDecl());
1034    QualType UnderlyingType = T->getDecl()->getUnderlyingType();
1035    VisitQualifiers(UnderlyingType.getQualifiers());
1036    while (true) {
1037      if (const TypedefType *Underlying =
1038              dyn_cast<TypedefType>(UnderlyingType.getTypePtr())) {
1039        UnderlyingType = Underlying->getDecl()->getUnderlyingType();
1040        continue;
1041      }
1042      if (const ElaboratedType *Underlying =
1043              dyn_cast<ElaboratedType>(UnderlyingType.getTypePtr())) {
1044        UnderlyingType = Underlying->getNamedType();
1045        continue;
1046      }
1047
1048      break;
1049    }
1050    AddType(UnderlyingType.getTypePtr());
1051    VisitType(T);
1052  }
1053
1054  void VisitTypeOfExprType(const TypeOfExprType *T) {
1055    AddStmt(T->getUnderlyingExpr());
1056    Hash.AddBoolean(T->isSugared());
1057    if (T->isSugared())
1058      AddQualType(T->desugar());
1059
1060    VisitType(T);
1061  }
1062  void VisitTypeOfType(const TypeOfType *T) {
1063    AddQualType(T->getUnderlyingType());
1064    VisitType(T);
1065  }
1066
1067  void VisitTypeWithKeyword(const TypeWithKeyword *T) {
1068    ID.AddInteger(T->getKeyword());
1069    VisitType(T);
1070  };
1071
1072  void VisitDependentNameType(const DependentNameType *T) {
1073    AddNestedNameSpecifier(T->getQualifier());
1074    AddIdentifierInfo(T->getIdentifier());
1075    VisitTypeWithKeyword(T);
1076  }
1077
1078  void VisitDependentTemplateSpecializationType(
1079      const DependentTemplateSpecializationType *T) {
1080    AddIdentifierInfo(T->getIdentifier());
1081    AddNestedNameSpecifier(T->getQualifier());
1082    ID.AddInteger(T->getNumArgs());
1083    for (const auto &TA : T->template_arguments()) {
1084      Hash.AddTemplateArgument(TA);
1085    }
1086    VisitTypeWithKeyword(T);
1087  }
1088
1089  void VisitElaboratedType(const ElaboratedType *T) {
1090    AddNestedNameSpecifier(T->getQualifier());
1091    AddQualType(T->getNamedType());
1092    VisitTypeWithKeyword(T);
1093  }
1094
1095  void VisitUnaryTransformType(const UnaryTransformType *T) {
1096    AddQualType(T->getUnderlyingType());
1097    AddQualType(T->getBaseType());
1098    VisitType(T);
1099  }
1100
1101  void VisitUnresolvedUsingType(const UnresolvedUsingType *T) {
1102    AddDecl(T->getDecl());
1103    VisitType(T);
1104  }
1105
1106  void VisitVectorType(const VectorType *T) {
1107    AddQualType(T->getElementType());
1108    ID.AddInteger(T->getNumElements());
1109    ID.AddInteger(T->getVectorKind());
1110    VisitType(T);
1111  }
1112
1113  void VisitExtVectorType(const ExtVectorType * T) {
1114    VisitVectorType(T);
1115  }
1116};
1117} // namespace
1118
1119void ODRHash::AddType(const Type *T) {
1120  assert(T && "Expecting non-null pointer.");
1121  ODRTypeVisitor(ID, *this).Visit(T);
1122}
1123
1124void ODRHash::AddQualType(QualType T) {
1125  AddBoolean(T.isNull());
1126  if (T.isNull())
1127    return;
1128  SplitQualType split = T.split();
1129  ID.AddInteger(split.Quals.getAsOpaqueValue());
1130  AddType(split.Ty);
1131}
1132
1133void ODRHash::AddBoolean(bool Value) {
1134  Bools.push_back(Value);
1135}
1136