clang  11.0.0git
ASTStructuralEquivalence.cpp
Go to the documentation of this file.
1 //===- ASTStructuralEquivalence.cpp ---------------------------------------===//
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 // This file implement StructuralEquivalenceContext class and helper functions
10 // for layout matching.
11 //
12 // The structural equivalence check could have been implemented as a parallel
13 // BFS on a pair of graphs. That must have been the original approach at the
14 // beginning.
15 // Let's consider this simple BFS algorithm from the `s` source:
16 // ```
17 // void bfs(Graph G, int s)
18 // {
19 // Queue<Integer> queue = new Queue<Integer>();
20 // marked[s] = true; // Mark the source
21 // queue.enqueue(s); // and put it on the queue.
22 // while (!q.isEmpty()) {
23 // int v = queue.dequeue(); // Remove next vertex from the queue.
24 // for (int w : G.adj(v))
25 // if (!marked[w]) // For every unmarked adjacent vertex,
26 // {
27 // marked[w] = true;
28 // queue.enqueue(w);
29 // }
30 // }
31 // }
32 // ```
33 // Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
34 // this is the `DeclsToCheck` member. `VisitedDecls` plays the role of the
35 // marking (`marked`) functionality above, we use it to check whether we've
36 // already seen a pair of nodes.
37 //
38 // We put in the elements into the queue only in the toplevel decl check
39 // function:
40 // ```
41 // static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
42 // Decl *D1, Decl *D2);
43 // ```
44 // The `while` loop where we iterate over the children is implemented in
45 // `Finish()`. And `Finish` is called only from the two **member** functions
46 // which check the equivalency of two Decls or two Types. ASTImporter (and
47 // other clients) call only these functions.
48 //
49 // The `static` implementation functions are called from `Finish`, these push
50 // the children nodes to the queue via `static bool
51 // IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
52 // Decl *D2)`. So far so good, this is almost like the BFS. However, if we
53 // let a static implementation function to call `Finish` via another **member**
54 // function that means we end up with two nested while loops each of them
55 // working on the same queue. This is wrong and nobody can reason about it's
56 // doing. Thus, static implementation functions must not call the **member**
57 // functions.
58 //
59 //===----------------------------------------------------------------------===//
60 
62 #include "clang/AST/ASTContext.h"
64 #include "clang/AST/Decl.h"
65 #include "clang/AST/DeclBase.h"
66 #include "clang/AST/DeclCXX.h"
67 #include "clang/AST/DeclFriend.h"
68 #include "clang/AST/DeclObjC.h"
69 #include "clang/AST/DeclTemplate.h"
70 #include "clang/AST/ExprCXX.h"
72 #include "clang/AST/TemplateBase.h"
73 #include "clang/AST/TemplateName.h"
74 #include "clang/AST/Type.h"
77 #include "clang/Basic/LLVM.h"
79 #include "llvm/ADT/APInt.h"
80 #include "llvm/ADT/APSInt.h"
81 #include "llvm/ADT/None.h"
82 #include "llvm/ADT/Optional.h"
83 #include "llvm/Support/Casting.h"
84 #include "llvm/Support/Compiler.h"
85 #include "llvm/Support/ErrorHandling.h"
86 #include <cassert>
87 #include <utility>
88 
89 using namespace clang;
90 
92  QualType T1, QualType T2);
94  Decl *D1, Decl *D2);
96  const TemplateArgument &Arg1,
97  const TemplateArgument &Arg2);
99  NestedNameSpecifier *NNS1,
100  NestedNameSpecifier *NNS2);
101 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
102  const IdentifierInfo *Name2);
103 
105  const DeclarationName Name1,
106  const DeclarationName Name2) {
107  if (Name1.getNameKind() != Name2.getNameKind())
108  return false;
109 
110  switch (Name1.getNameKind()) {
111 
114  Name2.getAsIdentifierInfo());
115 
119  return IsStructurallyEquivalent(Context, Name1.getCXXNameType(),
120  Name2.getCXXNameType());
121 
124  Context, Name1.getCXXDeductionGuideTemplate()->getDeclName(),
126  return false;
127  return IsStructurallyEquivalent(Context,
130  }
131 
133  return Name1.getCXXOverloadedOperator() == Name2.getCXXOverloadedOperator();
134 
137  Name2.getCXXLiteralIdentifier());
138 
140  return true; // FIXME When do we consider two using directives equal?
141 
145  return true; // FIXME
146  }
147 
148  llvm_unreachable("Unhandled kind of DeclarationName");
149  return true;
150 }
151 
152 /// Determine structural equivalence of two expressions.
154  const Expr *E1, const Expr *E2) {
155  if (!E1 || !E2)
156  return E1 == E2;
157 
158  if (auto *DE1 = dyn_cast<DependentScopeDeclRefExpr>(E1)) {
159  auto *DE2 = dyn_cast<DependentScopeDeclRefExpr>(E2);
160  if (!DE2)
161  return false;
162  if (!IsStructurallyEquivalent(Context, DE1->getDeclName(),
163  DE2->getDeclName()))
164  return false;
165  return IsStructurallyEquivalent(Context, DE1->getQualifier(),
166  DE2->getQualifier());
167  } else if (auto CastE1 = dyn_cast<ImplicitCastExpr>(E1)) {
168  auto *CastE2 = dyn_cast<ImplicitCastExpr>(E2);
169  if (!CastE2)
170  return false;
171  if (!IsStructurallyEquivalent(Context, CastE1->getType(),
172  CastE2->getType()))
173  return false;
174  return IsStructurallyEquivalent(Context, CastE1->getSubExpr(),
175  CastE2->getSubExpr());
176  }
177  // FIXME: Handle other kind of expressions!
178  return true;
179 }
180 
181 /// Determine whether two identifiers are equivalent.
182 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
183  const IdentifierInfo *Name2) {
184  if (!Name1 || !Name2)
185  return Name1 == Name2;
186 
187  return Name1->getName() == Name2->getName();
188 }
189 
190 /// Determine whether two nested-name-specifiers are equivalent.
192  NestedNameSpecifier *NNS1,
193  NestedNameSpecifier *NNS2) {
194  if (NNS1->getKind() != NNS2->getKind())
195  return false;
196 
197  NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
198  *Prefix2 = NNS2->getPrefix();
199  if ((bool)Prefix1 != (bool)Prefix2)
200  return false;
201 
202  if (Prefix1)
203  if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
204  return false;
205 
206  switch (NNS1->getKind()) {
209  NNS2->getAsIdentifier());
211  return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
212  NNS2->getAsNamespace());
214  return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
215  NNS2->getAsNamespaceAlias());
218  return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
219  QualType(NNS2->getAsType(), 0));
221  return true;
223  return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
224  NNS2->getAsRecordDecl());
225  }
226  return false;
227 }
228 
230  const TemplateName &N1,
231  const TemplateName &N2) {
232  TemplateDecl *TemplateDeclN1 = N1.getAsTemplateDecl();
233  TemplateDecl *TemplateDeclN2 = N2.getAsTemplateDecl();
234  if (TemplateDeclN1 && TemplateDeclN2) {
235  if (!IsStructurallyEquivalent(Context, TemplateDeclN1, TemplateDeclN2))
236  return false;
237  // If the kind is different we compare only the template decl.
238  if (N1.getKind() != N2.getKind())
239  return true;
240  } else if (TemplateDeclN1 || TemplateDeclN2)
241  return false;
242  else if (N1.getKind() != N2.getKind())
243  return false;
244 
245  // Check for special case incompatibilities.
246  switch (N1.getKind()) {
247 
250  *OS2 = N2.getAsOverloadedTemplate();
251  OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
252  E1 = OS1->end(), E2 = OS2->end();
253  for (; I1 != E1 && I2 != E2; ++I1, ++I2)
254  if (!IsStructurallyEquivalent(Context, *I1, *I2))
255  return false;
256  return I1 == E1 && I2 == E2;
257  }
258 
261  *TN2 = N1.getAsAssumedTemplateName();
262  return TN1->getDeclName() == TN2->getDeclName();
263  }
264 
267  *DN2 = N2.getAsDependentTemplateName();
268  if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
269  DN2->getQualifier()))
270  return false;
271  if (DN1->isIdentifier() && DN2->isIdentifier())
273  DN2->getIdentifier());
274  else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
275  return DN1->getOperator() == DN2->getOperator();
276  return false;
277  }
278 
283  return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
284  P2->getArgumentPack()) &&
286  P2->getParameterPack());
287  }
288 
292  // It is sufficient to check value of getAsTemplateDecl.
293  break;
294 
295  }
296 
297  return true;
298 }
299 
300 /// Determine whether two template arguments are equivalent.
302  const TemplateArgument &Arg1,
303  const TemplateArgument &Arg2) {
304  if (Arg1.getKind() != Arg2.getKind())
305  return false;
306 
307  switch (Arg1.getKind()) {
309  return true;
310 
312  return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
313 
315  if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
316  Arg2.getIntegralType()))
317  return false;
318 
319  return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
320  Arg2.getAsIntegral());
321 
323  return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
324 
326  return true; // FIXME: Is this correct?
327 
329  return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
330  Arg2.getAsTemplate());
331 
333  return IsStructurallyEquivalent(Context,
336 
338  return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
339  Arg2.getAsExpr());
340 
342  if (Arg1.pack_size() != Arg2.pack_size())
343  return false;
344 
345  for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
346  if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
347  Arg2.pack_begin()[I]))
348  return false;
349 
350  return true;
351  }
352 
353  llvm_unreachable("Invalid template argument kind");
354 }
355 
356 /// Determine structural equivalence for the common part of array
357 /// types.
359  const ArrayType *Array1,
360  const ArrayType *Array2) {
361  if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
362  Array2->getElementType()))
363  return false;
364  if (Array1->getSizeModifier() != Array2->getSizeModifier())
365  return false;
366  if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
367  return false;
368 
369  return true;
370 }
371 
372 /// Determine structural equivalence based on the ExtInfo of functions. This
373 /// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
374 /// conventions bits but must not compare some other bits.
377  FunctionType::ExtInfo EI2) {
378  // Compatible functions must have compatible calling conventions.
379  if (EI1.getCC() != EI2.getCC())
380  return false;
381 
382  // Regparm is part of the calling convention.
383  if (EI1.getHasRegParm() != EI2.getHasRegParm())
384  return false;
385  if (EI1.getRegParm() != EI2.getRegParm())
386  return false;
387 
388  if (EI1.getProducesResult() != EI2.getProducesResult())
389  return false;
390  if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
391  return false;
392  if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
393  return false;
394 
395  return true;
396 }
397 
398 /// Check the equivalence of exception specifications.
400  const FunctionProtoType *Proto1,
401  const FunctionProtoType *Proto2) {
402 
403  auto Spec1 = Proto1->getExceptionSpecType();
404  auto Spec2 = Proto2->getExceptionSpecType();
405 
407  return true;
408 
409  if (Spec1 != Spec2)
410  return false;
411  if (Spec1 == EST_Dynamic) {
412  if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
413  return false;
414  for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
415  if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
416  Proto2->getExceptionType(I)))
417  return false;
418  }
419  } else if (isComputedNoexcept(Spec1)) {
420  if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
421  Proto2->getNoexceptExpr()))
422  return false;
423  }
424 
425  return true;
426 }
427 
428 /// Determine structural equivalence of two types.
430  QualType T1, QualType T2) {
431  if (T1.isNull() || T2.isNull())
432  return T1.isNull() && T2.isNull();
433 
434  QualType OrigT1 = T1;
435  QualType OrigT2 = T2;
436 
437  if (!Context.StrictTypeSpelling) {
438  // We aren't being strict about token-to-token equivalence of types,
439  // so map down to the canonical type.
440  T1 = Context.FromCtx.getCanonicalType(T1);
441  T2 = Context.ToCtx.getCanonicalType(T2);
442  }
443 
444  if (T1.getQualifiers() != T2.getQualifiers())
445  return false;
446 
447  Type::TypeClass TC = T1->getTypeClass();
448 
449  if (T1->getTypeClass() != T2->getTypeClass()) {
450  // Compare function types with prototypes vs. without prototypes as if
451  // both did not have prototypes.
452  if (T1->getTypeClass() == Type::FunctionProto &&
453  T2->getTypeClass() == Type::FunctionNoProto)
454  TC = Type::FunctionNoProto;
455  else if (T1->getTypeClass() == Type::FunctionNoProto &&
456  T2->getTypeClass() == Type::FunctionProto)
457  TC = Type::FunctionNoProto;
458  else
459  return false;
460  }
461 
462  switch (TC) {
463  case Type::Builtin:
464  // FIXME: Deal with Char_S/Char_U.
465  if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
466  return false;
467  break;
468 
469  case Type::Complex:
470  if (!IsStructurallyEquivalent(Context,
471  cast<ComplexType>(T1)->getElementType(),
472  cast<ComplexType>(T2)->getElementType()))
473  return false;
474  break;
475 
476  case Type::Adjusted:
477  case Type::Decayed:
478  if (!IsStructurallyEquivalent(Context,
479  cast<AdjustedType>(T1)->getOriginalType(),
480  cast<AdjustedType>(T2)->getOriginalType()))
481  return false;
482  break;
483 
484  case Type::Pointer:
485  if (!IsStructurallyEquivalent(Context,
486  cast<PointerType>(T1)->getPointeeType(),
487  cast<PointerType>(T2)->getPointeeType()))
488  return false;
489  break;
490 
491  case Type::BlockPointer:
492  if (!IsStructurallyEquivalent(Context,
493  cast<BlockPointerType>(T1)->getPointeeType(),
494  cast<BlockPointerType>(T2)->getPointeeType()))
495  return false;
496  break;
497 
498  case Type::LValueReference:
499  case Type::RValueReference: {
500  const auto *Ref1 = cast<ReferenceType>(T1);
501  const auto *Ref2 = cast<ReferenceType>(T2);
502  if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
503  return false;
504  if (Ref1->isInnerRef() != Ref2->isInnerRef())
505  return false;
506  if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
507  Ref2->getPointeeTypeAsWritten()))
508  return false;
509  break;
510  }
511 
512  case Type::MemberPointer: {
513  const auto *MemPtr1 = cast<MemberPointerType>(T1);
514  const auto *MemPtr2 = cast<MemberPointerType>(T2);
515  if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
516  MemPtr2->getPointeeType()))
517  return false;
518  if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
519  QualType(MemPtr2->getClass(), 0)))
520  return false;
521  break;
522  }
523 
524  case Type::ConstantArray: {
525  const auto *Array1 = cast<ConstantArrayType>(T1);
526  const auto *Array2 = cast<ConstantArrayType>(T2);
527  if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
528  return false;
529 
530  if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
531  return false;
532  break;
533  }
534 
535  case Type::IncompleteArray:
536  if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
537  cast<ArrayType>(T2)))
538  return false;
539  break;
540 
541  case Type::VariableArray: {
542  const auto *Array1 = cast<VariableArrayType>(T1);
543  const auto *Array2 = cast<VariableArrayType>(T2);
544  if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
545  Array2->getSizeExpr()))
546  return false;
547 
548  if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
549  return false;
550 
551  break;
552  }
553 
554  case Type::DependentSizedArray: {
555  const auto *Array1 = cast<DependentSizedArrayType>(T1);
556  const auto *Array2 = cast<DependentSizedArrayType>(T2);
557  if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
558  Array2->getSizeExpr()))
559  return false;
560 
561  if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
562  return false;
563 
564  break;
565  }
566 
567  case Type::DependentAddressSpace: {
568  const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
569  const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
570  if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
571  DepAddressSpace2->getAddrSpaceExpr()))
572  return false;
573  if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
574  DepAddressSpace2->getPointeeType()))
575  return false;
576 
577  break;
578  }
579 
580  case Type::DependentSizedExtVector: {
581  const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
582  const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
583  if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
584  Vec2->getSizeExpr()))
585  return false;
586  if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
587  Vec2->getElementType()))
588  return false;
589  break;
590  }
591 
592  case Type::DependentVector: {
593  const auto *Vec1 = cast<DependentVectorType>(T1);
594  const auto *Vec2 = cast<DependentVectorType>(T2);
595  if (Vec1->getVectorKind() != Vec2->getVectorKind())
596  return false;
597  if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
598  Vec2->getSizeExpr()))
599  return false;
600  if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
601  Vec2->getElementType()))
602  return false;
603  break;
604  }
605 
606  case Type::Vector:
607  case Type::ExtVector: {
608  const auto *Vec1 = cast<VectorType>(T1);
609  const auto *Vec2 = cast<VectorType>(T2);
610  if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
611  Vec2->getElementType()))
612  return false;
613  if (Vec1->getNumElements() != Vec2->getNumElements())
614  return false;
615  if (Vec1->getVectorKind() != Vec2->getVectorKind())
616  return false;
617  break;
618  }
619 
620  case Type::DependentSizedMatrix: {
621  const DependentSizedMatrixType *Mat1 = cast<DependentSizedMatrixType>(T1);
622  const DependentSizedMatrixType *Mat2 = cast<DependentSizedMatrixType>(T2);
623  // The element types, row and column expressions must be structurally
624  // equivalent.
625  if (!IsStructurallyEquivalent(Context, Mat1->getRowExpr(),
626  Mat2->getRowExpr()) ||
627  !IsStructurallyEquivalent(Context, Mat1->getColumnExpr(),
628  Mat2->getColumnExpr()) ||
629  !IsStructurallyEquivalent(Context, Mat1->getElementType(),
630  Mat2->getElementType()))
631  return false;
632  break;
633  }
634 
635  case Type::ConstantMatrix: {
636  const ConstantMatrixType *Mat1 = cast<ConstantMatrixType>(T1);
637  const ConstantMatrixType *Mat2 = cast<ConstantMatrixType>(T2);
638  // The element types must be structurally equivalent and the number of rows
639  // and columns must match.
640  if (!IsStructurallyEquivalent(Context, Mat1->getElementType(),
641  Mat2->getElementType()) ||
642  Mat1->getNumRows() != Mat2->getNumRows() ||
643  Mat1->getNumColumns() != Mat2->getNumColumns())
644  return false;
645  break;
646  }
647 
648  case Type::FunctionProto: {
649  const auto *Proto1 = cast<FunctionProtoType>(T1);
650  const auto *Proto2 = cast<FunctionProtoType>(T2);
651 
652  if (Proto1->getNumParams() != Proto2->getNumParams())
653  return false;
654  for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
655  if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
656  Proto2->getParamType(I)))
657  return false;
658  }
659  if (Proto1->isVariadic() != Proto2->isVariadic())
660  return false;
661 
662  if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
663  return false;
664 
665  // Check exceptions, this information is lost in canonical type.
666  const auto *OrigProto1 =
667  cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));
668  const auto *OrigProto2 =
669  cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));
670  if (!IsEquivalentExceptionSpec(Context, OrigProto1, OrigProto2))
671  return false;
672 
673  // Fall through to check the bits common with FunctionNoProtoType.
674  LLVM_FALLTHROUGH;
675  }
676 
677  case Type::FunctionNoProto: {
678  const auto *Function1 = cast<FunctionType>(T1);
679  const auto *Function2 = cast<FunctionType>(T2);
680  if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
681  Function2->getReturnType()))
682  return false;
683  if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
684  Function2->getExtInfo()))
685  return false;
686  break;
687  }
688 
689  case Type::UnresolvedUsing:
690  if (!IsStructurallyEquivalent(Context,
691  cast<UnresolvedUsingType>(T1)->getDecl(),
692  cast<UnresolvedUsingType>(T2)->getDecl()))
693  return false;
694  break;
695 
696  case Type::Attributed:
697  if (!IsStructurallyEquivalent(Context,
698  cast<AttributedType>(T1)->getModifiedType(),
699  cast<AttributedType>(T2)->getModifiedType()))
700  return false;
702  Context, cast<AttributedType>(T1)->getEquivalentType(),
703  cast<AttributedType>(T2)->getEquivalentType()))
704  return false;
705  break;
706 
707  case Type::Paren:
708  if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
709  cast<ParenType>(T2)->getInnerType()))
710  return false;
711  break;
712 
713  case Type::MacroQualified:
715  Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),
716  cast<MacroQualifiedType>(T2)->getUnderlyingType()))
717  return false;
718  break;
719 
720  case Type::Typedef:
721  if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
722  cast<TypedefType>(T2)->getDecl()))
723  return false;
724  break;
725 
726  case Type::TypeOfExpr:
728  Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
729  cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
730  return false;
731  break;
732 
733  case Type::TypeOf:
734  if (!IsStructurallyEquivalent(Context,
735  cast<TypeOfType>(T1)->getUnderlyingType(),
736  cast<TypeOfType>(T2)->getUnderlyingType()))
737  return false;
738  break;
739 
740  case Type::UnaryTransform:
742  Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
743  cast<UnaryTransformType>(T2)->getUnderlyingType()))
744  return false;
745  break;
746 
747  case Type::Decltype:
748  if (!IsStructurallyEquivalent(Context,
749  cast<DecltypeType>(T1)->getUnderlyingExpr(),
750  cast<DecltypeType>(T2)->getUnderlyingExpr()))
751  return false;
752  break;
753 
754  case Type::Auto: {
755  auto *Auto1 = cast<AutoType>(T1);
756  auto *Auto2 = cast<AutoType>(T2);
757  if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
758  Auto2->getDeducedType()))
759  return false;
760  if (Auto1->isConstrained() != Auto2->isConstrained())
761  return false;
762  if (Auto1->isConstrained()) {
763  if (Auto1->getTypeConstraintConcept() !=
764  Auto2->getTypeConstraintConcept())
765  return false;
766  ArrayRef<TemplateArgument> Auto1Args =
767  Auto1->getTypeConstraintArguments();
768  ArrayRef<TemplateArgument> Auto2Args =
769  Auto2->getTypeConstraintArguments();
770  if (Auto1Args.size() != Auto2Args.size())
771  return false;
772  for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
773  if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
774  return false;
775  }
776  }
777  break;
778  }
779 
780  case Type::DeducedTemplateSpecialization: {
781  const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
782  const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
783  if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
784  DT2->getTemplateName()))
785  return false;
786  if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
787  DT2->getDeducedType()))
788  return false;
789  break;
790  }
791 
792  case Type::Record:
793  case Type::Enum:
794  if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
795  cast<TagType>(T2)->getDecl()))
796  return false;
797  break;
798 
799  case Type::TemplateTypeParm: {
800  const auto *Parm1 = cast<TemplateTypeParmType>(T1);
801  const auto *Parm2 = cast<TemplateTypeParmType>(T2);
802  if (Parm1->getDepth() != Parm2->getDepth())
803  return false;
804  if (Parm1->getIndex() != Parm2->getIndex())
805  return false;
806  if (Parm1->isParameterPack() != Parm2->isParameterPack())
807  return false;
808 
809  // Names of template type parameters are never significant.
810  break;
811  }
812 
813  case Type::SubstTemplateTypeParm: {
814  const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
815  const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
816  if (!IsStructurallyEquivalent(Context,
817  QualType(Subst1->getReplacedParameter(), 0),
818  QualType(Subst2->getReplacedParameter(), 0)))
819  return false;
820  if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
821  Subst2->getReplacementType()))
822  return false;
823  break;
824  }
825 
826  case Type::SubstTemplateTypeParmPack: {
827  const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
828  const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
829  if (!IsStructurallyEquivalent(Context,
830  QualType(Subst1->getReplacedParameter(), 0),
831  QualType(Subst2->getReplacedParameter(), 0)))
832  return false;
833  if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
834  Subst2->getArgumentPack()))
835  return false;
836  break;
837  }
838 
839  case Type::TemplateSpecialization: {
840  const auto *Spec1 = cast<TemplateSpecializationType>(T1);
841  const auto *Spec2 = cast<TemplateSpecializationType>(T2);
842  if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
843  Spec2->getTemplateName()))
844  return false;
845  if (Spec1->getNumArgs() != Spec2->getNumArgs())
846  return false;
847  for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
848  if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
849  Spec2->getArg(I)))
850  return false;
851  }
852  break;
853  }
854 
855  case Type::Elaborated: {
856  const auto *Elab1 = cast<ElaboratedType>(T1);
857  const auto *Elab2 = cast<ElaboratedType>(T2);
858  // CHECKME: what if a keyword is ETK_None or ETK_typename ?
859  if (Elab1->getKeyword() != Elab2->getKeyword())
860  return false;
861  if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
862  Elab2->getQualifier()))
863  return false;
864  if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
865  Elab2->getNamedType()))
866  return false;
867  break;
868  }
869 
870  case Type::InjectedClassName: {
871  const auto *Inj1 = cast<InjectedClassNameType>(T1);
872  const auto *Inj2 = cast<InjectedClassNameType>(T2);
873  if (!IsStructurallyEquivalent(Context,
874  Inj1->getInjectedSpecializationType(),
875  Inj2->getInjectedSpecializationType()))
876  return false;
877  break;
878  }
879 
880  case Type::DependentName: {
881  const auto *Typename1 = cast<DependentNameType>(T1);
882  const auto *Typename2 = cast<DependentNameType>(T2);
883  if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
884  Typename2->getQualifier()))
885  return false;
886  if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
887  Typename2->getIdentifier()))
888  return false;
889 
890  break;
891  }
892 
893  case Type::DependentTemplateSpecialization: {
894  const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
895  const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
896  if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
897  Spec2->getQualifier()))
898  return false;
899  if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
900  Spec2->getIdentifier()))
901  return false;
902  if (Spec1->getNumArgs() != Spec2->getNumArgs())
903  return false;
904  for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
905  if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
906  Spec2->getArg(I)))
907  return false;
908  }
909  break;
910  }
911 
912  case Type::PackExpansion:
913  if (!IsStructurallyEquivalent(Context,
914  cast<PackExpansionType>(T1)->getPattern(),
915  cast<PackExpansionType>(T2)->getPattern()))
916  return false;
917  break;
918 
919  case Type::ObjCInterface: {
920  const auto *Iface1 = cast<ObjCInterfaceType>(T1);
921  const auto *Iface2 = cast<ObjCInterfaceType>(T2);
922  if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
923  Iface2->getDecl()))
924  return false;
925  break;
926  }
927 
928  case Type::ObjCTypeParam: {
929  const auto *Obj1 = cast<ObjCTypeParamType>(T1);
930  const auto *Obj2 = cast<ObjCTypeParamType>(T2);
931  if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
932  return false;
933 
934  if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
935  return false;
936  for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
937  if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
938  Obj2->getProtocol(I)))
939  return false;
940  }
941  break;
942  }
943 
944  case Type::ObjCObject: {
945  const auto *Obj1 = cast<ObjCObjectType>(T1);
946  const auto *Obj2 = cast<ObjCObjectType>(T2);
947  if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
948  Obj2->getBaseType()))
949  return false;
950  if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
951  return false;
952  for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
953  if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
954  Obj2->getProtocol(I)))
955  return false;
956  }
957  break;
958  }
959 
960  case Type::ObjCObjectPointer: {
961  const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
962  const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
963  if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
964  Ptr2->getPointeeType()))
965  return false;
966  break;
967  }
968 
969  case Type::Atomic:
970  if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
971  cast<AtomicType>(T2)->getValueType()))
972  return false;
973  break;
974 
975  case Type::Pipe:
976  if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
977  cast<PipeType>(T2)->getElementType()))
978  return false;
979  break;
980  case Type::ExtInt: {
981  const auto *Int1 = cast<ExtIntType>(T1);
982  const auto *Int2 = cast<ExtIntType>(T2);
983 
984  if (Int1->isUnsigned() != Int2->isUnsigned() ||
985  Int1->getNumBits() != Int2->getNumBits())
986  return false;
987  break;
988  }
989  case Type::DependentExtInt: {
990  const auto *Int1 = cast<DependentExtIntType>(T1);
991  const auto *Int2 = cast<DependentExtIntType>(T2);
992 
993  if (Int1->isUnsigned() != Int2->isUnsigned() ||
994  !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(),
995  Int2->getNumBitsExpr()))
996  return false;
997  }
998  } // end switch
999 
1000  return true;
1001 }
1002 
1003 /// Determine structural equivalence of two fields.
1005  FieldDecl *Field1, FieldDecl *Field2) {
1006  const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
1007 
1008  // For anonymous structs/unions, match up the anonymous struct/union type
1009  // declarations directly, so that we don't go off searching for anonymous
1010  // types
1011  if (Field1->isAnonymousStructOrUnion() &&
1012  Field2->isAnonymousStructOrUnion()) {
1013  RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
1014  RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
1015  return IsStructurallyEquivalent(Context, D1, D2);
1016  }
1017 
1018  // Check for equivalent field names.
1019  IdentifierInfo *Name1 = Field1->getIdentifier();
1020  IdentifierInfo *Name2 = Field2->getIdentifier();
1021  if (!::IsStructurallyEquivalent(Name1, Name2)) {
1022  if (Context.Complain) {
1023  Context.Diag2(
1024  Owner2->getLocation(),
1025  Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1026  << Context.ToCtx.getTypeDeclType(Owner2);
1027  Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
1028  << Field2->getDeclName();
1029  Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
1030  << Field1->getDeclName();
1031  }
1032  return false;
1033  }
1034 
1035  if (!IsStructurallyEquivalent(Context, Field1->getType(),
1036  Field2->getType())) {
1037  if (Context.Complain) {
1038  Context.Diag2(
1039  Owner2->getLocation(),
1040  Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1041  << Context.ToCtx.getTypeDeclType(Owner2);
1042  Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1043  << Field2->getDeclName() << Field2->getType();
1044  Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1045  << Field1->getDeclName() << Field1->getType();
1046  }
1047  return false;
1048  }
1049 
1050  if (Field1->isBitField() != Field2->isBitField()) {
1051  if (Context.Complain) {
1052  Context.Diag2(
1053  Owner2->getLocation(),
1054  Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1055  << Context.ToCtx.getTypeDeclType(Owner2);
1056  if (Field1->isBitField()) {
1057  Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1058  << Field1->getDeclName() << Field1->getType()
1059  << Field1->getBitWidthValue(Context.FromCtx);
1060  Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
1061  << Field2->getDeclName();
1062  } else {
1063  Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1064  << Field2->getDeclName() << Field2->getType()
1065  << Field2->getBitWidthValue(Context.ToCtx);
1066  Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
1067  << Field1->getDeclName();
1068  }
1069  }
1070  return false;
1071  }
1072 
1073  if (Field1->isBitField()) {
1074  // Make sure that the bit-fields are the same length.
1075  unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
1076  unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
1077 
1078  if (Bits1 != Bits2) {
1079  if (Context.Complain) {
1080  Context.Diag2(Owner2->getLocation(),
1081  Context.getApplicableDiagnostic(
1082  diag::err_odr_tag_type_inconsistent))
1083  << Context.ToCtx.getTypeDeclType(Owner2);
1084  Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1085  << Field2->getDeclName() << Field2->getType() << Bits2;
1086  Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1087  << Field1->getDeclName() << Field1->getType() << Bits1;
1088  }
1089  return false;
1090  }
1091  }
1092 
1093  return true;
1094 }
1095 
1096 /// Determine structural equivalence of two methods.
1098  CXXMethodDecl *Method1,
1099  CXXMethodDecl *Method2) {
1100  bool PropertiesEqual =
1101  Method1->getDeclKind() == Method2->getDeclKind() &&
1102  Method1->getRefQualifier() == Method2->getRefQualifier() &&
1103  Method1->getAccess() == Method2->getAccess() &&
1104  Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1105  Method1->isStatic() == Method2->isStatic() &&
1106  Method1->isConst() == Method2->isConst() &&
1107  Method1->isVolatile() == Method2->isVolatile() &&
1108  Method1->isVirtual() == Method2->isVirtual() &&
1109  Method1->isPure() == Method2->isPure() &&
1110  Method1->isDefaulted() == Method2->isDefaulted() &&
1111  Method1->isDeleted() == Method2->isDeleted();
1112  if (!PropertiesEqual)
1113  return false;
1114  // FIXME: Check for 'final'.
1115 
1116  if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1117  auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1118  if (!Constructor1->getExplicitSpecifier().isEquivalent(
1119  Constructor2->getExplicitSpecifier()))
1120  return false;
1121  }
1122 
1123  if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1124  auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1125  if (!Conversion1->getExplicitSpecifier().isEquivalent(
1126  Conversion2->getExplicitSpecifier()))
1127  return false;
1128  if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1129  Conversion2->getConversionType()))
1130  return false;
1131  }
1132 
1133  const IdentifierInfo *Name1 = Method1->getIdentifier();
1134  const IdentifierInfo *Name2 = Method2->getIdentifier();
1135  if (!::IsStructurallyEquivalent(Name1, Name2)) {
1136  return false;
1137  // TODO: Names do not match, add warning like at check for FieldDecl.
1138  }
1139 
1140  // Check the prototypes.
1141  if (!::IsStructurallyEquivalent(Context,
1142  Method1->getType(), Method2->getType()))
1143  return false;
1144 
1145  return true;
1146 }
1147 
1148 /// Determine structural equivalence of two lambda classes.
1149 static bool
1151  CXXRecordDecl *D1, CXXRecordDecl *D2) {
1152  assert(D1->isLambda() && D2->isLambda() &&
1153  "Must be called on lambda classes");
1154  if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1155  D2->getLambdaCallOperator()))
1156  return false;
1157 
1158  return true;
1159 }
1160 
1161 /// Determine structural equivalence of two records.
1163  RecordDecl *D1, RecordDecl *D2) {
1164  if (D1->isUnion() != D2->isUnion()) {
1165  if (Context.Complain) {
1166  Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1167  diag::err_odr_tag_type_inconsistent))
1168  << Context.ToCtx.getTypeDeclType(D2);
1169  Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1170  << D1->getDeclName() << (unsigned)D1->getTagKind();
1171  }
1172  return false;
1173  }
1174 
1175  if (!D1->getDeclName() && !D2->getDeclName()) {
1176  // If both anonymous structs/unions are in a record context, make sure
1177  // they occur in the same location in the context records.
1178  if (Optional<unsigned> Index1 =
1180  if (Optional<unsigned> Index2 =
1182  D2)) {
1183  if (*Index1 != *Index2)
1184  return false;
1185  }
1186  }
1187  }
1188 
1189  // If both declarations are class template specializations, we know
1190  // the ODR applies, so check the template and template arguments.
1191  const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1192  const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1193  if (Spec1 && Spec2) {
1194  // Check that the specialized templates are the same.
1195  if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1196  Spec2->getSpecializedTemplate()))
1197  return false;
1198 
1199  // Check that the template arguments are the same.
1200  if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1201  return false;
1202 
1203  for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1204  if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1205  Spec2->getTemplateArgs().get(I)))
1206  return false;
1207  }
1208  // If one is a class template specialization and the other is not, these
1209  // structures are different.
1210  else if (Spec1 || Spec2)
1211  return false;
1212 
1213  // Compare the definitions of these two records. If either or both are
1214  // incomplete (i.e. it is a forward decl), we assume that they are
1215  // equivalent.
1216  D1 = D1->getDefinition();
1217  D2 = D2->getDefinition();
1218  if (!D1 || !D2)
1219  return true;
1220 
1221  // If any of the records has external storage and we do a minimal check (or
1222  // AST import) we assume they are equivalent. (If we didn't have this
1223  // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1224  // another AST import which in turn would call the structural equivalency
1225  // check again and finally we'd have an improper result.)
1228  return true;
1229 
1230  // If one definition is currently being defined, we do not compare for
1231  // equality and we assume that the decls are equal.
1232  if (D1->isBeingDefined() || D2->isBeingDefined())
1233  return true;
1234 
1235  if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1236  if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1237  if (D1CXX->hasExternalLexicalStorage() &&
1238  !D1CXX->isCompleteDefinition()) {
1239  D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1240  }
1241 
1242  if (D1CXX->isLambda() != D2CXX->isLambda())
1243  return false;
1244  if (D1CXX->isLambda()) {
1245  if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1246  return false;
1247  }
1248 
1249  if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1250  if (Context.Complain) {
1251  Context.Diag2(D2->getLocation(),
1252  Context.getApplicableDiagnostic(
1253  diag::err_odr_tag_type_inconsistent))
1254  << Context.ToCtx.getTypeDeclType(D2);
1255  Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1256  << D2CXX->getNumBases();
1257  Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1258  << D1CXX->getNumBases();
1259  }
1260  return false;
1261  }
1262 
1263  // Check the base classes.
1264  for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1265  BaseEnd1 = D1CXX->bases_end(),
1266  Base2 = D2CXX->bases_begin();
1267  Base1 != BaseEnd1; ++Base1, ++Base2) {
1268  if (!IsStructurallyEquivalent(Context, Base1->getType(),
1269  Base2->getType())) {
1270  if (Context.Complain) {
1271  Context.Diag2(D2->getLocation(),
1272  Context.getApplicableDiagnostic(
1273  diag::err_odr_tag_type_inconsistent))
1274  << Context.ToCtx.getTypeDeclType(D2);
1275  Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1276  << Base2->getType() << Base2->getSourceRange();
1277  Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1278  << Base1->getType() << Base1->getSourceRange();
1279  }
1280  return false;
1281  }
1282 
1283  // Check virtual vs. non-virtual inheritance mismatch.
1284  if (Base1->isVirtual() != Base2->isVirtual()) {
1285  if (Context.Complain) {
1286  Context.Diag2(D2->getLocation(),
1287  Context.getApplicableDiagnostic(
1288  diag::err_odr_tag_type_inconsistent))
1289  << Context.ToCtx.getTypeDeclType(D2);
1290  Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1291  << Base2->isVirtual() << Base2->getSourceRange();
1292  Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1293  << Base1->isVirtual() << Base1->getSourceRange();
1294  }
1295  return false;
1296  }
1297  }
1298 
1299  // Check the friends for consistency.
1300  CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1301  Friend2End = D2CXX->friend_end();
1302  for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1303  Friend1End = D1CXX->friend_end();
1304  Friend1 != Friend1End; ++Friend1, ++Friend2) {
1305  if (Friend2 == Friend2End) {
1306  if (Context.Complain) {
1307  Context.Diag2(D2->getLocation(),
1308  Context.getApplicableDiagnostic(
1309  diag::err_odr_tag_type_inconsistent))
1310  << Context.ToCtx.getTypeDeclType(D2CXX);
1311  Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1312  Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1313  }
1314  return false;
1315  }
1316 
1317  if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1318  if (Context.Complain) {
1319  Context.Diag2(D2->getLocation(),
1320  Context.getApplicableDiagnostic(
1321  diag::err_odr_tag_type_inconsistent))
1322  << Context.ToCtx.getTypeDeclType(D2CXX);
1323  Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1324  Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1325  }
1326  return false;
1327  }
1328  }
1329 
1330  if (Friend2 != Friend2End) {
1331  if (Context.Complain) {
1332  Context.Diag2(D2->getLocation(),
1333  Context.getApplicableDiagnostic(
1334  diag::err_odr_tag_type_inconsistent))
1335  << Context.ToCtx.getTypeDeclType(D2);
1336  Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1337  Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1338  }
1339  return false;
1340  }
1341  } else if (D1CXX->getNumBases() > 0) {
1342  if (Context.Complain) {
1343  Context.Diag2(D2->getLocation(),
1344  Context.getApplicableDiagnostic(
1345  diag::err_odr_tag_type_inconsistent))
1346  << Context.ToCtx.getTypeDeclType(D2);
1347  const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1348  Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1349  << Base1->getType() << Base1->getSourceRange();
1350  Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1351  }
1352  return false;
1353  }
1354  }
1355 
1356  // Check the fields for consistency.
1357  RecordDecl::field_iterator Field2 = D2->field_begin(),
1358  Field2End = D2->field_end();
1359  for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1360  Field1End = D1->field_end();
1361  Field1 != Field1End; ++Field1, ++Field2) {
1362  if (Field2 == Field2End) {
1363  if (Context.Complain) {
1364  Context.Diag2(D2->getLocation(),
1365  Context.getApplicableDiagnostic(
1366  diag::err_odr_tag_type_inconsistent))
1367  << Context.ToCtx.getTypeDeclType(D2);
1368  Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1369  << Field1->getDeclName() << Field1->getType();
1370  Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1371  }
1372  return false;
1373  }
1374 
1375  if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1376  return false;
1377  }
1378 
1379  if (Field2 != Field2End) {
1380  if (Context.Complain) {
1381  Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1382  diag::err_odr_tag_type_inconsistent))
1383  << Context.ToCtx.getTypeDeclType(D2);
1384  Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1385  << Field2->getDeclName() << Field2->getType();
1386  Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1387  }
1388  return false;
1389  }
1390 
1391  return true;
1392 }
1393 
1394 /// Determine structural equivalence of two enums.
1396  EnumDecl *D1, EnumDecl *D2) {
1397 
1398  // Compare the definitions of these two enums. If either or both are
1399  // incomplete (i.e. forward declared), we assume that they are equivalent.
1400  D1 = D1->getDefinition();
1401  D2 = D2->getDefinition();
1402  if (!D1 || !D2)
1403  return true;
1404 
1406  EC2End = D2->enumerator_end();
1408  EC1End = D1->enumerator_end();
1409  EC1 != EC1End; ++EC1, ++EC2) {
1410  if (EC2 == EC2End) {
1411  if (Context.Complain) {
1412  Context.Diag2(D2->getLocation(),
1413  Context.getApplicableDiagnostic(
1414  diag::err_odr_tag_type_inconsistent))
1415  << Context.ToCtx.getTypeDeclType(D2);
1416  Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1417  << EC1->getDeclName() << EC1->getInitVal().toString(10);
1418  Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1419  }
1420  return false;
1421  }
1422 
1423  llvm::APSInt Val1 = EC1->getInitVal();
1424  llvm::APSInt Val2 = EC2->getInitVal();
1425  if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1426  !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1427  if (Context.Complain) {
1428  Context.Diag2(D2->getLocation(),
1429  Context.getApplicableDiagnostic(
1430  diag::err_odr_tag_type_inconsistent))
1431  << Context.ToCtx.getTypeDeclType(D2);
1432  Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1433  << EC2->getDeclName() << EC2->getInitVal().toString(10);
1434  Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1435  << EC1->getDeclName() << EC1->getInitVal().toString(10);
1436  }
1437  return false;
1438  }
1439  }
1440 
1441  if (EC2 != EC2End) {
1442  if (Context.Complain) {
1443  Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1444  diag::err_odr_tag_type_inconsistent))
1445  << Context.ToCtx.getTypeDeclType(D2);
1446  Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1447  << EC2->getDeclName() << EC2->getInitVal().toString(10);
1448  Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1449  }
1450  return false;
1451  }
1452 
1453  return true;
1454 }
1455 
1457  TemplateParameterList *Params1,
1458  TemplateParameterList *Params2) {
1459  if (Params1->size() != Params2->size()) {
1460  if (Context.Complain) {
1461  Context.Diag2(Params2->getTemplateLoc(),
1462  Context.getApplicableDiagnostic(
1463  diag::err_odr_different_num_template_parameters))
1464  << Params1->size() << Params2->size();
1465  Context.Diag1(Params1->getTemplateLoc(),
1466  diag::note_odr_template_parameter_list);
1467  }
1468  return false;
1469  }
1470 
1471  for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1472  if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1473  if (Context.Complain) {
1474  Context.Diag2(Params2->getParam(I)->getLocation(),
1475  Context.getApplicableDiagnostic(
1476  diag::err_odr_different_template_parameter_kind));
1477  Context.Diag1(Params1->getParam(I)->getLocation(),
1478  diag::note_odr_template_parameter_here);
1479  }
1480  return false;
1481  }
1482 
1483  if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1484  Params2->getParam(I)))
1485  return false;
1486  }
1487 
1488  return true;
1489 }
1490 
1493  TemplateTypeParmDecl *D2) {
1494  if (D1->isParameterPack() != D2->isParameterPack()) {
1495  if (Context.Complain) {
1496  Context.Diag2(D2->getLocation(),
1497  Context.getApplicableDiagnostic(
1498  diag::err_odr_parameter_pack_non_pack))
1499  << D2->isParameterPack();
1500  Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1501  << D1->isParameterPack();
1502  }
1503  return false;
1504  }
1505 
1506  return true;
1507 }
1508 
1512  if (D1->isParameterPack() != D2->isParameterPack()) {
1513  if (Context.Complain) {
1514  Context.Diag2(D2->getLocation(),
1515  Context.getApplicableDiagnostic(
1516  diag::err_odr_parameter_pack_non_pack))
1517  << D2->isParameterPack();
1518  Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1519  << D1->isParameterPack();
1520  }
1521  return false;
1522  }
1523 
1524  // Check types.
1525  if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1526  if (Context.Complain) {
1527  Context.Diag2(D2->getLocation(),
1528  Context.getApplicableDiagnostic(
1529  diag::err_odr_non_type_parameter_type_inconsistent))
1530  << D2->getType() << D1->getType();
1531  Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1532  << D1->getType();
1533  }
1534  return false;
1535  }
1536 
1537  return true;
1538 }
1539 
1543  if (D1->isParameterPack() != D2->isParameterPack()) {
1544  if (Context.Complain) {
1545  Context.Diag2(D2->getLocation(),
1546  Context.getApplicableDiagnostic(
1547  diag::err_odr_parameter_pack_non_pack))
1548  << D2->isParameterPack();
1549  Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1550  << D1->isParameterPack();
1551  }
1552  return false;
1553  }
1554 
1555  // Check template parameter lists.
1556  return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1557  D2->getTemplateParameters());
1558 }
1559 
1563  return false;
1564  if (!D1->getIdentifier()) // Special name
1565  if (D1->getNameAsString() != D2->getNameAsString())
1566  return false;
1568  D2->getTemplateParameters());
1569 }
1570 
1572  ClassTemplateDecl *D1,
1573  ClassTemplateDecl *D2) {
1574  // Check template parameters.
1575  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1576  return false;
1577 
1578  // Check the templated declaration.
1579  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1580  D2->getTemplatedDecl());
1581 }
1582 
1585  FunctionTemplateDecl *D2) {
1586  // Check template parameters.
1587  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1588  return false;
1589 
1590  // Check the templated declaration.
1591  return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1592  D2->getTemplatedDecl()->getType());
1593 }
1594 
1596  ConceptDecl *D1,
1597  ConceptDecl *D2) {
1598  // Check template parameters.
1599  if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1600  return false;
1601 
1602  // Check the constraint expression.
1603  return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1604  D2->getConstraintExpr());
1605 }
1606 
1608  FriendDecl *D1, FriendDecl *D2) {
1609  if ((D1->getFriendType() && D2->getFriendDecl()) ||
1610  (D1->getFriendDecl() && D2->getFriendType())) {
1611  return false;
1612  }
1613  if (D1->getFriendType() && D2->getFriendType())
1614  return IsStructurallyEquivalent(Context,
1615  D1->getFriendType()->getType(),
1616  D2->getFriendType()->getType());
1617  if (D1->getFriendDecl() && D2->getFriendDecl())
1618  return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1619  D2->getFriendDecl());
1620  return false;
1621 }
1622 
1624  FunctionDecl *D1, FunctionDecl *D2) {
1625  // FIXME: Consider checking for function attributes as well.
1626  if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1627  return false;
1628 
1629  return true;
1630 }
1631 
1632 /// Determine structural equivalence of two declarations.
1634  Decl *D1, Decl *D2) {
1635  // FIXME: Check for known structural equivalences via a callback of some sort.
1636 
1637  D1 = D1->getCanonicalDecl();
1638  D2 = D2->getCanonicalDecl();
1639  std::pair<Decl *, Decl *> P{D1, D2};
1640 
1641  // Check whether we already know that these two declarations are not
1642  // structurally equivalent.
1643  if (Context.NonEquivalentDecls.count(P))
1644  return false;
1645 
1646  // Check if a check for these declarations is already pending.
1647  // If yes D1 and D2 will be checked later (from DeclsToCheck),
1648  // or these are already checked (and equivalent).
1649  bool Inserted = Context.VisitedDecls.insert(P).second;
1650  if (!Inserted)
1651  return true;
1652 
1653  Context.DeclsToCheck.push(P);
1654 
1655  return true;
1656 }
1657 
1659  unsigned DiagID) {
1660  assert(Complain && "Not allowed to complain");
1661  if (LastDiagFromC2)
1663  LastDiagFromC2 = false;
1664  return FromCtx.getDiagnostics().Report(Loc, DiagID);
1665 }
1666 
1668  unsigned DiagID) {
1669  assert(Complain && "Not allowed to complain");
1670  if (!LastDiagFromC2)
1672  LastDiagFromC2 = true;
1673  return ToCtx.getDiagnostics().Report(Loc, DiagID);
1674 }
1675 
1678  ASTContext &Context = Anon->getASTContext();
1679  QualType AnonTy = Context.getRecordType(Anon);
1680 
1681  const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1682  if (!Owner)
1683  return None;
1684 
1685  unsigned Index = 0;
1686  for (const auto *D : Owner->noload_decls()) {
1687  const auto *F = dyn_cast<FieldDecl>(D);
1688  if (!F)
1689  continue;
1690 
1691  if (F->isAnonymousStructOrUnion()) {
1692  if (Context.hasSameType(F->getType(), AnonTy))
1693  break;
1694  ++Index;
1695  continue;
1696  }
1697 
1698  // If the field looks like this:
1699  // struct { ... } A;
1700  QualType FieldType = F->getType();
1701  // In case of nested structs.
1702  while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1703  FieldType = ElabType->getNamedType();
1704 
1705  if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1706  const RecordDecl *RecDecl = RecType->getDecl();
1707  if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1708  if (Context.hasSameType(FieldType, AnonTy))
1709  break;
1710  ++Index;
1711  continue;
1712  }
1713  }
1714  }
1715 
1716  return Index;
1717 }
1718 
1720  unsigned ErrorDiagnostic) {
1722  return ErrorDiagnostic;
1723 
1724  switch (ErrorDiagnostic) {
1725  case diag::err_odr_variable_type_inconsistent:
1726  return diag::warn_odr_variable_type_inconsistent;
1727  case diag::err_odr_variable_multiple_def:
1728  return diag::warn_odr_variable_multiple_def;
1729  case diag::err_odr_function_type_inconsistent:
1730  return diag::warn_odr_function_type_inconsistent;
1731  case diag::err_odr_tag_type_inconsistent:
1732  return diag::warn_odr_tag_type_inconsistent;
1733  case diag::err_odr_field_type_inconsistent:
1734  return diag::warn_odr_field_type_inconsistent;
1735  case diag::err_odr_ivar_type_inconsistent:
1736  return diag::warn_odr_ivar_type_inconsistent;
1737  case diag::err_odr_objc_superclass_inconsistent:
1738  return diag::warn_odr_objc_superclass_inconsistent;
1739  case diag::err_odr_objc_method_result_type_inconsistent:
1740  return diag::warn_odr_objc_method_result_type_inconsistent;
1741  case diag::err_odr_objc_method_num_params_inconsistent:
1742  return diag::warn_odr_objc_method_num_params_inconsistent;
1743  case diag::err_odr_objc_method_param_type_inconsistent:
1744  return diag::warn_odr_objc_method_param_type_inconsistent;
1745  case diag::err_odr_objc_method_variadic_inconsistent:
1746  return diag::warn_odr_objc_method_variadic_inconsistent;
1747  case diag::err_odr_objc_property_type_inconsistent:
1748  return diag::warn_odr_objc_property_type_inconsistent;
1749  case diag::err_odr_objc_property_impl_kind_inconsistent:
1750  return diag::warn_odr_objc_property_impl_kind_inconsistent;
1751  case diag::err_odr_objc_synthesize_ivar_inconsistent:
1752  return diag::warn_odr_objc_synthesize_ivar_inconsistent;
1753  case diag::err_odr_different_num_template_parameters:
1754  return diag::warn_odr_different_num_template_parameters;
1755  case diag::err_odr_different_template_parameter_kind:
1756  return diag::warn_odr_different_template_parameter_kind;
1757  case diag::err_odr_parameter_pack_non_pack:
1758  return diag::warn_odr_parameter_pack_non_pack;
1759  case diag::err_odr_non_type_parameter_type_inconsistent:
1760  return diag::warn_odr_non_type_parameter_type_inconsistent;
1761  }
1762  llvm_unreachable("Diagnostic kind not handled in preceding switch");
1763 }
1764 
1766 
1767  // Ensure that the implementation functions (all static functions in this TU)
1768  // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1769  // because that will wreak havoc the internal state (DeclsToCheck and
1770  // VisitedDecls members) and can cause faulty behaviour.
1771  // In other words: Do not start a graph search from a new node with the
1772  // internal data of another search in progress.
1773  // FIXME: Better encapsulation and separation of internal and public
1774  // functionality.
1775  assert(DeclsToCheck.empty());
1776  assert(VisitedDecls.empty());
1777 
1778  if (!::IsStructurallyEquivalent(*this, D1, D2))
1779  return false;
1780 
1781  return !Finish();
1782 }
1783 
1785  assert(DeclsToCheck.empty());
1786  assert(VisitedDecls.empty());
1787  if (!::IsStructurallyEquivalent(*this, T1, T2))
1788  return false;
1789 
1790  return !Finish();
1791 }
1792 
1793 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
1794  // Check for equivalent described template.
1795  TemplateDecl *Template1 = D1->getDescribedTemplate();
1796  TemplateDecl *Template2 = D2->getDescribedTemplate();
1797  if ((Template1 != nullptr) != (Template2 != nullptr))
1798  return false;
1799  if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
1800  return false;
1801 
1802  // FIXME: Move check for identifier names into this function.
1803 
1804  return true;
1805 }
1806 
1807 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
1808  Decl *D1, Decl *D2) {
1809  // FIXME: Switch on all declaration kinds. For now, we're just going to
1810  // check the obvious ones.
1811  if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1812  if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1813  // Check for equivalent structure names.
1814  IdentifierInfo *Name1 = Record1->getIdentifier();
1815  if (!Name1 && Record1->getTypedefNameForAnonDecl())
1816  Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1817  IdentifierInfo *Name2 = Record2->getIdentifier();
1818  if (!Name2 && Record2->getTypedefNameForAnonDecl())
1819  Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1820  if (!::IsStructurallyEquivalent(Name1, Name2) ||
1821  !::IsStructurallyEquivalent(*this, Record1, Record2))
1822  return false;
1823  } else {
1824  // Record/non-record mismatch.
1825  return false;
1826  }
1827  } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1828  if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1829  // Check for equivalent enum names.
1830  IdentifierInfo *Name1 = Enum1->getIdentifier();
1831  if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1832  Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1833  IdentifierInfo *Name2 = Enum2->getIdentifier();
1834  if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1835  Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1836  if (!::IsStructurallyEquivalent(Name1, Name2) ||
1837  !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1838  return false;
1839  } else {
1840  // Enum/non-enum mismatch
1841  return false;
1842  }
1843  } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1844  if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1845  if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1846  Typedef2->getIdentifier()) ||
1847  !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1848  Typedef2->getUnderlyingType()))
1849  return false;
1850  } else {
1851  // Typedef/non-typedef mismatch.
1852  return false;
1853  }
1854  } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1855  if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1856  if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1857  ClassTemplate2))
1858  return false;
1859  } else {
1860  // Class template/non-class-template mismatch.
1861  return false;
1862  }
1863  } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1864  if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1865  if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1866  FunctionTemplate2))
1867  return false;
1868  } else {
1869  // Class template/non-class-template mismatch.
1870  return false;
1871  }
1872  } else if (auto *ConceptDecl1 = dyn_cast<ConceptDecl>(D1)) {
1873  if (auto *ConceptDecl2 = dyn_cast<ConceptDecl>(D2)) {
1874  if (!::IsStructurallyEquivalent(*this, ConceptDecl1, ConceptDecl2))
1875  return false;
1876  } else {
1877  // Concept/non-concept mismatch.
1878  return false;
1879  }
1880  } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1881  if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1882  if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1883  return false;
1884  } else {
1885  // Kind mismatch.
1886  return false;
1887  }
1888  } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1889  if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1890  if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1891  return false;
1892  } else {
1893  // Kind mismatch.
1894  return false;
1895  }
1896  } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1897  if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1898  if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1899  return false;
1900  } else {
1901  // Kind mismatch.
1902  return false;
1903  }
1904  } else if (auto *MD1 = dyn_cast<CXXMethodDecl>(D1)) {
1905  if (auto *MD2 = dyn_cast<CXXMethodDecl>(D2)) {
1906  if (!::IsStructurallyEquivalent(*this, MD1, MD2))
1907  return false;
1908  } else {
1909  // Kind mismatch.
1910  return false;
1911  }
1912  } else if (FunctionDecl *FD1 = dyn_cast<FunctionDecl>(D1)) {
1913  if (FunctionDecl *FD2 = dyn_cast<FunctionDecl>(D2)) {
1914  if (FD1->isOverloadedOperator()) {
1915  if (!FD2->isOverloadedOperator())
1916  return false;
1917  if (FD1->getOverloadedOperator() != FD2->getOverloadedOperator())
1918  return false;
1919  }
1920  if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1921  FD2->getIdentifier()))
1922  return false;
1923  if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1924  return false;
1925  } else {
1926  // Kind mismatch.
1927  return false;
1928  }
1929  } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1930  if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1931  if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1932  return false;
1933  } else {
1934  // Kind mismatch.
1935  return false;
1936  }
1937  }
1938 
1939  return true;
1940 }
1941 
1942 bool StructuralEquivalenceContext::Finish() {
1943  while (!DeclsToCheck.empty()) {
1944  // Check the next declaration.
1945  std::pair<Decl *, Decl *> P = DeclsToCheck.front();
1946  DeclsToCheck.pop();
1947 
1948  Decl *D1 = P.first;
1949  Decl *D2 = P.second;
1950 
1951  bool Equivalent =
1952  CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
1953 
1954  if (!Equivalent) {
1955  // Note that these two declarations are not equivalent (and we already
1956  // know about it).
1957  NonEquivalentDecls.insert(P);
1958 
1959  return true;
1960  }
1961  }
1962 
1963  return false;
1964 }
TemplateTemplateParmDecl * getParameterPack() const
Retrieve the template template parameter pack being substituted.
Definition: TemplateName.h:149
Defines the clang::ASTContext interface.
enumerator_iterator enumerator_end() const
Definition: Decl.h:3635
Represents a function declaration or definition.
Definition: Decl.h:1783
A (possibly-)qualified type.
Definition: Type.h:655
static llvm::Optional< unsigned > findUntaggedStructOrUnionIndex(RecordDecl *Anon)
Find the index of the given anonymous struct/union within its context.
OverloadedOperatorKind getOperator() const
Return the overloaded operator to which this template name refers.
Definition: TemplateName.h:521
bool getNoCfCheck() const
Definition: Type.h:3710
NestedNameSpecifier * getQualifier() const
Return the nested name specifier that qualifies this name.
Definition: TemplateName.h:505
unsigned getNumExceptions() const
Return the number of types in the exception specification.
Definition: Type.h:4164
QualType getDesugaredType(const ASTContext &Context) const
Return the specified type with any "sugar" removed from the type.
Definition: Type.h:961
static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context, const FunctionProtoType *Proto1, const FunctionProtoType *Proto2)
Check the equivalence of exception specifications.
C Language Family Type Representation.
Microsoft&#39;s &#39;__super&#39; specifier, stored as a CXXRecordDecl* of the class it appeared in...
The template argument is an expression, and we&#39;ve not resolved it to one of the other forms yet...
Definition: TemplateBase.h:86
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
bool isVirtual() const
Definition: DeclCXX.h:2005
Represents a matrix type where the type and the number of rows and columns is dependent on a template...
Definition: Type.h:3511
NestedNameSpecifier * getPrefix() const
Return the prefix of this nested name specifier.
Defines the C++ template declaration subclasses.
StringRef P
OverloadedOperatorKind getCXXOverloadedOperator() const
If this name is the name of an overloadable operator in C++ (e.g., operator+), retrieve the kind of o...
DiagnosticsEngine & getDiagnostics() const
DiagnosticBuilder Report(SourceLocation Loc, unsigned DiagID)
Issue the message to the client.
Definition: Diagnostic.h:1330
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:2888
The template argument is a declaration that was provided for a pointer, reference, or pointer to member non-type template parameter.
Definition: TemplateBase.h:64
DeclarationName getDeclName() const
Get the name of the template.
NamedDecl * getParam(unsigned Idx)
Definition: DeclTemplate.h:138
A template template parameter that has been substituted for some other template name.
Definition: TemplateName.h:224
QualType getElementType() const
Definition: Type.h:2909
Expr * getColumnExpr() const
Definition: Type.h:3527
const IdentifierInfo * getIdentifier() const
Returns the identifier to which this template name refers.
Definition: TemplateName.h:511
An identifier, stored as an IdentifierInfo*.
FriendDecl - Represents the declaration of a friend entity, which can be a function, a type, or a templated function or type.
Definition: DeclFriend.h:53
Represents an empty template argument, e.g., one that has not been deduced.
Definition: TemplateBase.h:57
ASTContext & FromCtx
AST contexts for which we are checking structural equivalence.
A namespace, stored as a NamespaceDecl*.
Stores a list of template parameters for a TemplateDecl and its derived classes.
Definition: DeclTemplate.h:69
SpecifierKind getKind() const
Determine what kind of nested name specifier is stored.
bool isStatic() const
Definition: DeclCXX.cpp:2033
Defines the clang::Expr interface and subclasses for C++ expressions.
QualType getIntegralType() const
Retrieve the type of the integral value.
Definition: TemplateBase.h:316
DiagnosticBuilder Diag1(SourceLocation Loc, unsigned DiagID)
bool isAnonymousStructOrUnion() const
Determines whether this field is a representative for an anonymous struct or union.
Definition: Decl.cpp:4035
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:244
Represents a struct/union/class.
Definition: Decl.h:3764
An iterator over the friend declarations of a class.
Definition: DeclFriend.h:187
DeclarationName getDeclName() const
Get the actual, stored name of the declaration, which may be a special name.
Definition: Decl.h:272
Represents a class template specialization, which refers to a class template with a given set of temp...
One of these records is kept for each identifier that is lexed.
TypeSourceInfo * getFriendType() const
If this friend declaration names an (untemplated but possibly dependent) type, return the type; other...
Definition: DeclFriend.h:123
bool isConst() const
Definition: DeclCXX.h:2002
unsigned getRegParm() const
Definition: Type.h:3713
Expr * getAsExpr() const
Retrieve the template argument as an expression.
Definition: TemplateBase.h:331
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:174
Represents a dependent template name that cannot be resolved prior to template instantiation.
Definition: TemplateName.h:449
The template argument is an integral value stored in an llvm::APSInt that was provided for an integra...
Definition: TemplateBase.h:72
TemplateDecl * getAsTemplateDecl() const
Retrieve the underlying template declaration that this template name refers to, if known...
RecordDecl * getDefinition() const
Returns the RecordDecl that actually defines this struct/union/class.
Definition: Decl.h:3969
NameKind getNameKind() const
Determine what kind of name this is.
bool ErrorOnTagTypeMismatch
Whether warn or error on tag type mismatches.
Represents a member of a struct/union/class.
Definition: Decl.h:2740
bool isVolatile() const
Definition: DeclCXX.h:2003
const Type * getAsType() const
Retrieve the type stored in this nested name specifier.
SubstTemplateTemplateParmPackStorage * getAsSubstTemplateTemplateParmPack() const
Retrieve the substituted template template parameter pack, if known.
Defines the ExceptionSpecificationType enumeration and various utility functions. ...
DiagnosticBuilder Diag2(SourceLocation Loc, unsigned DiagID)
NamedDecl * getFriendDecl() const
If this friend declaration doesn&#39;t name a type, return the inner declaration.
Definition: DeclFriend.h:138
SourceLocation getTemplateLoc() const
Definition: DeclTemplate.h:195
bool getProducesResult() const
Definition: Type.h:3707
bool StrictTypeSpelling
Whether we&#39;re being strict about the spelling of types when unifying two types.
CXXRecordDecl * getAsRecordDecl() const
Retrieve the record declaration stored in this nested name specifier.
bool isBitField() const
Determines whether this field is a bitfield.
Definition: Decl.h:2818
IdentifierInfo * getAsIdentifier() const
Retrieve the identifier stored in this nested name specifier.
A qualified template name, where the qualification is kept to describe the source code as written...
Definition: TemplateName.h:216
RefQualifierKind getRefQualifier() const
Retrieve the ref-qualifier associated with this method.
Definition: DeclCXX.h:2121
Expr * getRowExpr() const
Definition: Type.h:3526
TagKind getTagKind() const
Definition: Decl.h:3412
QualType getExceptionType(unsigned i) const
Return the ith exception type, where 0 <= i < getNumExceptions().
Definition: Type.h:4172
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
An unqualified-id that has been assumed to name a function template that will be found by ADL...
Definition: TemplateName.h:212
NamespaceAliasDecl * getAsNamespaceAlias() const
Retrieve the namespace alias stored in this nested name specifier.
bool isLambda() const
Determine whether this class describes a lambda function object.
Definition: DeclCXX.h:986
field_iterator field_begin() const
Definition: Decl.cpp:4454
unsigned getBitWidthValue(const ASTContext &Ctx) const
Definition: Decl.cpp:4045
CXXRecordDecl * getTemplatedDecl() const
Get the underlying class declarations of the template.
bool isParameterPack() const
Whether this template template parameter is a template parameter pack.
bool getNoCallerSavedRegs() const
Definition: Type.h:3709
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:897
QualType getElementType() const
Returns type of the elements being stored in the matrix.
Definition: Type.h:3432
A little helper class used to produce diagnostics.
Definition: Diagnostic.h:1062
Represents a prototype with parameter type info, e.g.
Definition: Type.h:3886
Represents a concrete matrix type with constant number of rows and columns.
Definition: Type.h:3454
unsigned getNumRows() const
Returns the number of rows in the matrix.
Definition: Type.h:3469
OverloadedOperatorKind getOverloadedOperator() const
getOverloadedOperator - Which C++ overloaded operator this function represents, if any...
Definition: Decl.cpp:3515
A dependent template name that has not been resolved to a template (or set of templates).
Definition: TemplateName.h:220
bool isParameterPack() const
Whether this parameter is a non-type template parameter pack.
ValueDecl * getAsDecl() const
Retrieve the declaration for a declaration non-type template argument.
Definition: TemplateBase.h:265
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: DeclCXX.h:190
static bool IsTemplateDeclCommonStructurallyEquivalent(StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2)
TemplateParameterList * getTemplateParameters() const
Get the list of template parameters.
Definition: DeclTemplate.h:421
QualType getCXXNameType() const
If this name is one of the C++ names (of a constructor, destructor, or conversion function)...
NamespaceDecl * getAsNamespace() const
Retrieve the namespace stored in this nested name specifier.
This represents one expression.
Definition: Expr.h:110
bool isDefaulted() const
Whether this function is defaulted.
Definition: Decl.h:2130
Declaration of a template type parameter.
bool LastDiagFromC2
true if the last diagnostic came from ToCtx.
bool getHasRegParm() const
Definition: Type.h:3711
const T * castAs() const
Member-template castAs<specific type>.
Definition: Type.h:7218
The template argument is a null pointer or null pointer to member that was provided for a non-type te...
Definition: TemplateBase.h:68
std::queue< std::pair< Decl *, Decl * > > DeclsToCheck
unsigned getNumColumns() const
Returns the number of columns in the matrix.
Definition: Type.h:3472
field_iterator field_end() const
Definition: Decl.h:3987
DeclContext * getDeclContext()
Definition: DeclBase.h:439
unsigned getApplicableDiagnostic(unsigned ErrorDiagnostic)
NonTypeTemplateParmDecl - Declares a non-type template parameter, e.g., "Size" in.
Represents a C++ template name within the type system.
Definition: TemplateName.h:192
EnumDecl * getDefinition() const
Definition: Decl.h:3598
bool isIdentifier() const
Determine whether this template name refers to an identifier.
Definition: TemplateName.h:508
A namespace alias, stored as a NamespaceAliasDecl*.
IdentifierInfo * getAsIdentifierInfo() const
Retrieve the IdentifierInfo * stored in this declaration name, or null if this declaration name isn&#39;t...
static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context, const ArrayType *Array1, const ArrayType *Array2)
Determine structural equivalence for the common part of array types.
Defines the clang::IdentifierInfo, clang::IdentifierTable, and clang::Selector interfaces.
enumerator_iterator enumerator_begin() const
Definition: Decl.h:3628
QualType getRecordType(const RecordDecl *Decl) const
ArraySizeModifier getSizeModifier() const
Definition: Type.h:2911
TemplateTemplateParmDecl - Declares a template template parameter, e.g., "T" in.
QualType getTypeDeclType(const TypeDecl *Decl, const TypeDecl *PrevDecl=nullptr) const
Return the unique reference to the type for the specified type declaration.
Definition: ASTContext.h:1376
bool isNull() const
Return true if this QualType doesn&#39;t point to a type yet.
Definition: Type.h:720
A template template parameter pack that has been substituted for a template template argument pack...
Definition: TemplateName.h:229
bool isComputedNoexcept(ExceptionSpecificationType ESpecType)
Decl::Kind getDeclKind() const
Definition: DeclBase.h:1805
OverloadedTemplateStorage * getAsOverloadedTemplate() const
Retrieve the underlying, overloaded function template declarations that this template name refers to...
bool isParameterPack() const
Returns whether this is a parameter pack.
Encodes a location in the source.
FunctionDecl * getTemplatedDecl() const
Get the underlying function declaration of the template.
bool isPure() const
Whether this virtual function is pure, i.e.
Definition: Decl.h:2105
llvm::APSInt APSInt
static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, QualType T1, QualType T2)
Determine structural equivalence of two types.
A structure for storing an already-substituted template template parameter pack.
Definition: TemplateName.h:135
std::string getNameAsString() const
Get a human-readable name for the declaration, even if it is one of the special kinds of names (C++ c...
Definition: Decl.h:266
ASTContext & getASTContext() const LLVM_READONLY
Definition: DeclBase.cpp:412
CallingConv getCC() const
Definition: Type.h:3720
static QualType getUnderlyingType(const SubRegion *R)
Represents a static or instance method of a struct/union/class.
Definition: DeclCXX.h:1960
Represents a C++ nested name specifier, such as "\::std::vector<int>::".
bool isOverloadedOperator() const
Determine whether this template name refers to an overloaded operator.
Definition: TemplateName.h:518
unsigned pack_size() const
The number of template arguments in the given template argument pack.
Definition: TemplateBase.h:361
Expr * getNoexceptExpr() const
Return the expression inside noexcept(expression), or a null pointer if there is none (because the ex...
Definition: Type.h:4179
bool hasExternalLexicalStorage() const
Whether this DeclContext has external storage containing additional declarations that are lexically i...
Definition: DeclBase.h:2376
ImplicitCastExpr - Allows us to explicitly represent implicit type conversions, which have no direct ...
Definition: Expr.h:3472
Qualifiers getIndexTypeQualifiers() const
Definition: Type.h:2915
TypeClass getTypeClass() const
Definition: Type.h:1884
llvm::APSInt getAsIntegral() const
Retrieve the template argument as an integral value.
Definition: TemplateBase.h:302
DependentTemplateName * getAsDependentTemplateName() const
Retrieve the underlying dependent template name structure, if any.
ExceptionSpecificationType getExceptionSpecType() const
Get the kind of exception specification on this function.
Definition: Type.h:4121
A qualified reference to a name whose declaration cannot yet be resolved.
Definition: ExprCXX.h:3144
StringRef getName() const
Return the actual identifier string.
Represents a template argument.
Definition: TemplateBase.h:51
Dataflow Directional Tag Classes.
CXXMethodDecl * getLambdaCallOperator() const
Retrieve the lambda call operator of the closure type if this is a closure type.
Definition: DeclCXX.cpp:1465
The base class of all kinds of template declarations (e.g., class, function, etc.).
Definition: DeclTemplate.h:402
The template argument is a pack expansion of a template name that was provided for a template templat...
Definition: TemplateBase.h:80
AccessSpecifier getAccess() const
Definition: DeclBase.h:478
The name of a declaration.
Kind getKind() const
Definition: DeclBase.h:433
Represents an enum.
Definition: Decl.h:3495
ExternalASTSource * getExternalSource() const
Retrieve a pointer to the external AST source associated with this AST context, if any...
Definition: ASTContext.h:1017
A type that was preceded by the &#39;template&#39; keyword, stored as a Type*.
pack_iterator pack_begin() const
Iterator referencing the first argument of a template argument pack.
Definition: TemplateBase.h:341
specific_decl_iterator - Iterates over a subrange of declarations stored in a DeclContext, providing only those that are of type SpecificDecl (or a class derived from it).
Definition: DeclBase.h:2081
bool IsEquivalent(Decl *D1, Decl *D2)
Determine whether the two declarations are structurally equivalent.
static bool IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context, CXXRecordDecl *D1, CXXRecordDecl *D2)
Determine structural equivalence of two lambda classes.
llvm::DenseSet< std::pair< Decl *, Decl * > > & NonEquivalentDecls
Declaration (from, to) pairs that are known not to be equivalent (which we have already complained ab...
A helper class that allows the use of isa/cast/dyncast to detect TagType objects of structs/unions/cl...
Definition: Type.h:4617
QualType getElementType() const
Definition: Type.h:3525
virtual void CompleteType(TagDecl *Tag)
Gives the external AST source an opportunity to complete an incomplete type.
bool hasSameType(QualType T1, QualType T2) const
Determine whether the given types T1 and T2 are equivalent.
Definition: ASTContext.h:2275
The template argument is a type.
Definition: TemplateBase.h:60
AssumedTemplateStorage * getAsAssumedTemplateName() const
Retrieve information on a name that has been assumed to be a template-name in order to permit a call ...
The template argument is actually a parameter pack.
Definition: TemplateBase.h:90
llvm::DenseSet< std::pair< Decl *, Decl * > > VisitedDecls
Represents a base class of a C++ class.
Definition: DeclCXX.h:146
CanQualType getCanonicalType(QualType T) const
Return the canonical (structural) type corresponding to the specified potentially non-canonical type ...
Definition: ASTContext.h:2259
ArgKind getKind() const
Return the kind of stored template argument.
Definition: TemplateBase.h:234
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate.h) and friends (in DeclFriend.h).
TemplateDecl * getCXXDeductionGuideTemplate() const
If this name is the name of a C++ deduction guide, return the template associated with that name...
Defines the clang::SourceLocation class and associated facilities.
Represents a C++ struct/union/class.
Definition: DeclCXX.h:254
The template argument is a template name that was provided for a template template parameter...
Definition: TemplateBase.h:76
Qualifiers getQualifiers() const
Retrieve the set of qualifiers applied to this type.
Definition: Type.h:6429
A structure for storing the information associated with an overloaded template name.
Definition: TemplateName.h:105
A structure for storing the information associated with a name that has been assumed to be a template...
Declaration of a class template.
NameKind getKind() const
static Decl::Kind getKind(const Decl *D)
Definition: DeclBase.cpp:994
QualType getAsType() const
Retrieve the type for a type template argument.
Definition: TemplateBase.h:258
bool isUnion() const
Definition: Decl.h:3421
bool isDeleted() const
Whether this function has been deleted.
Definition: Decl.h:2257
bool Complain
Whether to complain about failures.
IdentifierInfo * getCXXLiteralIdentifier() const
If this name is the name of a literal operator, retrieve the identifier associated with it...
QualType getType() const
Definition: Decl.h:630
TemplateArgument getArgumentPack() const
Retrieve the template template argument pack with which this parameter was substituted.
bool isUnresolvedExceptionSpec(ExceptionSpecificationType ESpecType)
A set of overloaded template declarations.
Definition: TemplateName.h:208
TemplateDecl * getDescribedTemplate() const
If this is a declaration that describes some template, this method returns that template declaration...
Definition: DeclBase.cpp:230
SourceRange getSourceRange() const LLVM_READONLY
Retrieves the source range that contains the entire base specifier.
Definition: DeclCXX.h:189
TemplateName getAsTemplate() const
Retrieve the template name for a template name argument.
Definition: TemplateBase.h:282
Expr * getConstraintExpr() const
The global specifier &#39;::&#39;. There is no stored value.
TemplateName getAsTemplateOrTemplatePattern() const
Retrieve the template argument as a template name; if the argument is a pack expansion, return the pattern as a template name.
Definition: TemplateBase.h:289
Declaration of a template function.
Definition: DeclTemplate.h:977
A class which abstracts out some details necessary for making a call.
Definition: Type.h:3658
SourceLocation getLocation() const
Definition: DeclBase.h:430
QualType getType() const
Return the type wrapped by this type source info.
Definition: Type.h:6384
A single template declaration.
Definition: TemplateName.h:205
bool isBeingDefined() const
Return true if this decl is currently being defined.
Definition: Decl.h:3358
QualType getType() const
Retrieves the type of the base class.
Definition: DeclCXX.h:245
void notePriorDiagnosticFrom(const DiagnosticsEngine &Other)
Note that the prior diagnostic was emitted by some other DiagnosticsEngine, and we may be attaching a...
Definition: Diagnostic.h:809