1 //===- ASTStructuralEquivalence.cpp ---------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implement StructuralEquivalenceContext class and helper functions
10 // for layout matching.
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
15 // Let's consider this simple BFS algorithm from the `s` source:
17 // void bfs(Graph G, int s)
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,
33 // Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
34 // this is the `DeclsToCheck` and it's pair is in `TentativeEquivalences`.
35 // `TentativeEquivalences` also plays the role of the marking (`marked`)
36 // functionality above, we use it to check whether we've already seen a pair of
39 // We put in the elements into the queue only in the toplevel decl check
42 // static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
43 // Decl *D1, Decl *D2);
45 // The `while` loop where we iterate over the children is implemented in
46 // `Finish()`. And `Finish` is called only from the two **member** functions
47 // which check the equivalency of two Decls or two Types. ASTImporter (and
48 // other clients) call only these functions.
50 // The `static` implementation functions are called from `Finish`, these push
51 // the children nodes to the queue via `static bool
52 // IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
53 // Decl *D2)`. So far so good, this is almost like the BFS. However, if we
54 // let a static implementation function to call `Finish` via another **member**
55 // function that means we end up with two nested while loops each of them
56 // working on the same queue. This is wrong and nobody can reason about it's
57 // doing. Thus, static implementation functions must not call the **member**
60 // So, now `TentativeEquivalences` plays two roles. It is used to store the
61 // second half of the decls which we want to compare, plus it plays a role in
62 // closing the recursion. On a long term, we could refactor structural
63 // equivalency to be more alike to the traditional BFS.
65 //===----------------------------------------------------------------------===//
67 #include "clang/AST/ASTStructuralEquivalence.h"
68 #include "clang/AST/ASTContext.h"
69 #include "clang/AST/ASTDiagnostic.h"
70 #include "clang/AST/Decl.h"
71 #include "clang/AST/DeclBase.h"
72 #include "clang/AST/DeclCXX.h"
73 #include "clang/AST/DeclFriend.h"
74 #include "clang/AST/DeclObjC.h"
75 #include "clang/AST/DeclTemplate.h"
76 #include "clang/AST/ExprCXX.h"
77 #include "clang/AST/NestedNameSpecifier.h"
78 #include "clang/AST/TemplateBase.h"
79 #include "clang/AST/TemplateName.h"
80 #include "clang/AST/Type.h"
81 #include "clang/Basic/ExceptionSpecificationType.h"
82 #include "clang/Basic/IdentifierTable.h"
83 #include "clang/Basic/LLVM.h"
84 #include "clang/Basic/SourceLocation.h"
85 #include "llvm/ADT/APInt.h"
86 #include "llvm/ADT/APSInt.h"
87 #include "llvm/ADT/None.h"
88 #include "llvm/ADT/Optional.h"
89 #include "llvm/Support/Casting.h"
90 #include "llvm/Support/Compiler.h"
91 #include "llvm/Support/ErrorHandling.h"
95 using namespace clang;
97 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
98 QualType T1, QualType T2);
99 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
101 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
102 const TemplateArgument &Arg1,
103 const TemplateArgument &Arg2);
104 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
105 NestedNameSpecifier *NNS1,
106 NestedNameSpecifier *NNS2);
107 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
108 const IdentifierInfo *Name2);
110 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
111 const DeclarationName Name1,
112 const DeclarationName Name2) {
113 if (Name1.getNameKind() != Name2.getNameKind())
116 switch (Name1.getNameKind()) {
118 case DeclarationName::Identifier:
119 return IsStructurallyEquivalent(Name1.getAsIdentifierInfo(),
120 Name2.getAsIdentifierInfo());
122 case DeclarationName::CXXConstructorName:
123 case DeclarationName::CXXDestructorName:
124 case DeclarationName::CXXConversionFunctionName:
125 return IsStructurallyEquivalent(Context, Name1.getCXXNameType(),
126 Name2.getCXXNameType());
128 case DeclarationName::CXXDeductionGuideName: {
129 if (!IsStructurallyEquivalent(
130 Context, Name1.getCXXDeductionGuideTemplate()->getDeclName(),
131 Name2.getCXXDeductionGuideTemplate()->getDeclName()))
133 return IsStructurallyEquivalent(Context,
134 Name1.getCXXDeductionGuideTemplate(),
135 Name2.getCXXDeductionGuideTemplate());
138 case DeclarationName::CXXOperatorName:
139 return Name1.getCXXOverloadedOperator() == Name2.getCXXOverloadedOperator();
141 case DeclarationName::CXXLiteralOperatorName:
142 return IsStructurallyEquivalent(Name1.getCXXLiteralIdentifier(),
143 Name2.getCXXLiteralIdentifier());
145 case DeclarationName::CXXUsingDirective:
146 return true; // FIXME When do we consider two using directives equal?
148 case DeclarationName::ObjCZeroArgSelector:
149 case DeclarationName::ObjCOneArgSelector:
150 case DeclarationName::ObjCMultiArgSelector:
151 return true; // FIXME
154 llvm_unreachable("Unhandled kind of DeclarationName");
158 /// Determine structural equivalence of two expressions.
159 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
160 const Expr *E1, const Expr *E2) {
164 if (auto *DE1 = dyn_cast<DependentScopeDeclRefExpr>(E1)) {
165 auto *DE2 = dyn_cast<DependentScopeDeclRefExpr>(E2);
168 if (!IsStructurallyEquivalent(Context, DE1->getDeclName(),
171 return IsStructurallyEquivalent(Context, DE1->getQualifier(),
172 DE2->getQualifier());
173 } else if (auto CastE1 = dyn_cast<ImplicitCastExpr>(E1)) {
174 auto *CastE2 = dyn_cast<ImplicitCastExpr>(E2);
177 if (!IsStructurallyEquivalent(Context, CastE1->getType(),
180 return IsStructurallyEquivalent(Context, CastE1->getSubExpr(),
181 CastE2->getSubExpr());
183 // FIXME: Handle other kind of expressions!
187 /// Determine whether two identifiers are equivalent.
188 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
189 const IdentifierInfo *Name2) {
190 if (!Name1 || !Name2)
191 return Name1 == Name2;
193 return Name1->getName() == Name2->getName();
196 /// Determine whether two nested-name-specifiers are equivalent.
197 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
198 NestedNameSpecifier *NNS1,
199 NestedNameSpecifier *NNS2) {
200 if (NNS1->getKind() != NNS2->getKind())
203 NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
204 *Prefix2 = NNS2->getPrefix();
205 if ((bool)Prefix1 != (bool)Prefix2)
209 if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
212 switch (NNS1->getKind()) {
213 case NestedNameSpecifier::Identifier:
214 return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
215 NNS2->getAsIdentifier());
216 case NestedNameSpecifier::Namespace:
217 return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
218 NNS2->getAsNamespace());
219 case NestedNameSpecifier::NamespaceAlias:
220 return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
221 NNS2->getAsNamespaceAlias());
222 case NestedNameSpecifier::TypeSpec:
223 case NestedNameSpecifier::TypeSpecWithTemplate:
224 return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
225 QualType(NNS2->getAsType(), 0));
226 case NestedNameSpecifier::Global:
228 case NestedNameSpecifier::Super:
229 return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
230 NNS2->getAsRecordDecl());
235 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
236 const TemplateName &N1,
237 const TemplateName &N2) {
238 TemplateDecl *TemplateDeclN1 = N1.getAsTemplateDecl();
239 TemplateDecl *TemplateDeclN2 = N2.getAsTemplateDecl();
240 if (TemplateDeclN1 && TemplateDeclN2) {
241 if (!IsStructurallyEquivalent(Context, TemplateDeclN1, TemplateDeclN2))
243 // If the kind is different we compare only the template decl.
244 if (N1.getKind() != N2.getKind())
246 } else if (TemplateDeclN1 || TemplateDeclN2)
248 else if (N1.getKind() != N2.getKind())
251 // Check for special case incompatibilities.
252 switch (N1.getKind()) {
254 case TemplateName::OverloadedTemplate: {
255 OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
256 *OS2 = N2.getAsOverloadedTemplate();
257 OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
258 E1 = OS1->end(), E2 = OS2->end();
259 for (; I1 != E1 && I2 != E2; ++I1, ++I2)
260 if (!IsStructurallyEquivalent(Context, *I1, *I2))
262 return I1 == E1 && I2 == E2;
265 case TemplateName::AssumedTemplate: {
266 AssumedTemplateStorage *TN1 = N1.getAsAssumedTemplateName(),
267 *TN2 = N1.getAsAssumedTemplateName();
268 return TN1->getDeclName() == TN2->getDeclName();
271 case TemplateName::DependentTemplate: {
272 DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
273 *DN2 = N2.getAsDependentTemplateName();
274 if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
275 DN2->getQualifier()))
277 if (DN1->isIdentifier() && DN2->isIdentifier())
278 return IsStructurallyEquivalent(DN1->getIdentifier(),
279 DN2->getIdentifier());
280 else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
281 return DN1->getOperator() == DN2->getOperator();
285 case TemplateName::SubstTemplateTemplateParmPack: {
286 SubstTemplateTemplateParmPackStorage
287 *P1 = N1.getAsSubstTemplateTemplateParmPack(),
288 *P2 = N2.getAsSubstTemplateTemplateParmPack();
289 return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
290 P2->getArgumentPack()) &&
291 IsStructurallyEquivalent(Context, P1->getParameterPack(),
292 P2->getParameterPack());
295 case TemplateName::Template:
296 case TemplateName::QualifiedTemplate:
297 case TemplateName::SubstTemplateTemplateParm:
298 // It is sufficient to check value of getAsTemplateDecl.
306 /// Determine whether two template arguments are equivalent.
307 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
308 const TemplateArgument &Arg1,
309 const TemplateArgument &Arg2) {
310 if (Arg1.getKind() != Arg2.getKind())
313 switch (Arg1.getKind()) {
314 case TemplateArgument::Null:
317 case TemplateArgument::Type:
318 return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
320 case TemplateArgument::Integral:
321 if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
322 Arg2.getIntegralType()))
325 return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
326 Arg2.getAsIntegral());
328 case TemplateArgument::Declaration:
329 return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
331 case TemplateArgument::NullPtr:
332 return true; // FIXME: Is this correct?
334 case TemplateArgument::Template:
335 return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
336 Arg2.getAsTemplate());
338 case TemplateArgument::TemplateExpansion:
339 return IsStructurallyEquivalent(Context,
340 Arg1.getAsTemplateOrTemplatePattern(),
341 Arg2.getAsTemplateOrTemplatePattern());
343 case TemplateArgument::Expression:
344 return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
347 case TemplateArgument::Pack:
348 if (Arg1.pack_size() != Arg2.pack_size())
351 for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
352 if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
353 Arg2.pack_begin()[I]))
359 llvm_unreachable("Invalid template argument kind");
362 /// Determine structural equivalence for the common part of array
364 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
365 const ArrayType *Array1,
366 const ArrayType *Array2) {
367 if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
368 Array2->getElementType()))
370 if (Array1->getSizeModifier() != Array2->getSizeModifier())
372 if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
378 /// Determine structural equivalence based on the ExtInfo of functions. This
379 /// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
380 /// conventions bits but must not compare some other bits.
381 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
382 FunctionType::ExtInfo EI1,
383 FunctionType::ExtInfo EI2) {
384 // Compatible functions must have compatible calling conventions.
385 if (EI1.getCC() != EI2.getCC())
388 // Regparm is part of the calling convention.
389 if (EI1.getHasRegParm() != EI2.getHasRegParm())
391 if (EI1.getRegParm() != EI2.getRegParm())
394 if (EI1.getProducesResult() != EI2.getProducesResult())
396 if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
398 if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
404 /// Check the equivalence of exception specifications.
405 static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,
406 const FunctionProtoType *Proto1,
407 const FunctionProtoType *Proto2) {
409 auto Spec1 = Proto1->getExceptionSpecType();
410 auto Spec2 = Proto2->getExceptionSpecType();
412 if (isUnresolvedExceptionSpec(Spec1) || isUnresolvedExceptionSpec(Spec2))
417 if (Spec1 == EST_Dynamic) {
418 if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
420 for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
421 if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
422 Proto2->getExceptionType(I)))
425 } else if (isComputedNoexcept(Spec1)) {
426 if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
427 Proto2->getNoexceptExpr()))
434 /// Determine structural equivalence of two types.
435 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
436 QualType T1, QualType T2) {
437 if (T1.isNull() || T2.isNull())
438 return T1.isNull() && T2.isNull();
440 QualType OrigT1 = T1;
441 QualType OrigT2 = T2;
443 if (!Context.StrictTypeSpelling) {
444 // We aren't being strict about token-to-token equivalence of types,
445 // so map down to the canonical type.
446 T1 = Context.FromCtx.getCanonicalType(T1);
447 T2 = Context.ToCtx.getCanonicalType(T2);
450 if (T1.getQualifiers() != T2.getQualifiers())
453 Type::TypeClass TC = T1->getTypeClass();
455 if (T1->getTypeClass() != T2->getTypeClass()) {
456 // Compare function types with prototypes vs. without prototypes as if
457 // both did not have prototypes.
458 if (T1->getTypeClass() == Type::FunctionProto &&
459 T2->getTypeClass() == Type::FunctionNoProto)
460 TC = Type::FunctionNoProto;
461 else if (T1->getTypeClass() == Type::FunctionNoProto &&
462 T2->getTypeClass() == Type::FunctionProto)
463 TC = Type::FunctionNoProto;
470 // FIXME: Deal with Char_S/Char_U.
471 if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
476 if (!IsStructurallyEquivalent(Context,
477 cast<ComplexType>(T1)->getElementType(),
478 cast<ComplexType>(T2)->getElementType()))
484 if (!IsStructurallyEquivalent(Context,
485 cast<AdjustedType>(T1)->getOriginalType(),
486 cast<AdjustedType>(T2)->getOriginalType()))
491 if (!IsStructurallyEquivalent(Context,
492 cast<PointerType>(T1)->getPointeeType(),
493 cast<PointerType>(T2)->getPointeeType()))
497 case Type::BlockPointer:
498 if (!IsStructurallyEquivalent(Context,
499 cast<BlockPointerType>(T1)->getPointeeType(),
500 cast<BlockPointerType>(T2)->getPointeeType()))
504 case Type::LValueReference:
505 case Type::RValueReference: {
506 const auto *Ref1 = cast<ReferenceType>(T1);
507 const auto *Ref2 = cast<ReferenceType>(T2);
508 if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
510 if (Ref1->isInnerRef() != Ref2->isInnerRef())
512 if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
513 Ref2->getPointeeTypeAsWritten()))
518 case Type::MemberPointer: {
519 const auto *MemPtr1 = cast<MemberPointerType>(T1);
520 const auto *MemPtr2 = cast<MemberPointerType>(T2);
521 if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
522 MemPtr2->getPointeeType()))
524 if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
525 QualType(MemPtr2->getClass(), 0)))
530 case Type::ConstantArray: {
531 const auto *Array1 = cast<ConstantArrayType>(T1);
532 const auto *Array2 = cast<ConstantArrayType>(T2);
533 if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
536 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
541 case Type::IncompleteArray:
542 if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
543 cast<ArrayType>(T2)))
547 case Type::VariableArray: {
548 const auto *Array1 = cast<VariableArrayType>(T1);
549 const auto *Array2 = cast<VariableArrayType>(T2);
550 if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
551 Array2->getSizeExpr()))
554 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
560 case Type::DependentSizedArray: {
561 const auto *Array1 = cast<DependentSizedArrayType>(T1);
562 const auto *Array2 = cast<DependentSizedArrayType>(T2);
563 if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
564 Array2->getSizeExpr()))
567 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
573 case Type::DependentAddressSpace: {
574 const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
575 const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
576 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
577 DepAddressSpace2->getAddrSpaceExpr()))
579 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
580 DepAddressSpace2->getPointeeType()))
586 case Type::DependentSizedExtVector: {
587 const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
588 const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
589 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
590 Vec2->getSizeExpr()))
592 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
593 Vec2->getElementType()))
598 case Type::DependentVector: {
599 const auto *Vec1 = cast<DependentVectorType>(T1);
600 const auto *Vec2 = cast<DependentVectorType>(T2);
601 if (Vec1->getVectorKind() != Vec2->getVectorKind())
603 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
604 Vec2->getSizeExpr()))
606 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
607 Vec2->getElementType()))
613 case Type::ExtVector: {
614 const auto *Vec1 = cast<VectorType>(T1);
615 const auto *Vec2 = cast<VectorType>(T2);
616 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
617 Vec2->getElementType()))
619 if (Vec1->getNumElements() != Vec2->getNumElements())
621 if (Vec1->getVectorKind() != Vec2->getVectorKind())
626 case Type::FunctionProto: {
627 const auto *Proto1 = cast<FunctionProtoType>(T1);
628 const auto *Proto2 = cast<FunctionProtoType>(T2);
630 if (Proto1->getNumParams() != Proto2->getNumParams())
632 for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
633 if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
634 Proto2->getParamType(I)))
637 if (Proto1->isVariadic() != Proto2->isVariadic())
640 if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
643 // Check exceptions, this information is lost in canonical type.
644 const auto *OrigProto1 =
645 cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));
646 const auto *OrigProto2 =
647 cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));
648 if (!IsEquivalentExceptionSpec(Context, OrigProto1, OrigProto2))
651 // Fall through to check the bits common with FunctionNoProtoType.
655 case Type::FunctionNoProto: {
656 const auto *Function1 = cast<FunctionType>(T1);
657 const auto *Function2 = cast<FunctionType>(T2);
658 if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
659 Function2->getReturnType()))
661 if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
662 Function2->getExtInfo()))
667 case Type::UnresolvedUsing:
668 if (!IsStructurallyEquivalent(Context,
669 cast<UnresolvedUsingType>(T1)->getDecl(),
670 cast<UnresolvedUsingType>(T2)->getDecl()))
674 case Type::Attributed:
675 if (!IsStructurallyEquivalent(Context,
676 cast<AttributedType>(T1)->getModifiedType(),
677 cast<AttributedType>(T2)->getModifiedType()))
679 if (!IsStructurallyEquivalent(
680 Context, cast<AttributedType>(T1)->getEquivalentType(),
681 cast<AttributedType>(T2)->getEquivalentType()))
686 if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
687 cast<ParenType>(T2)->getInnerType()))
691 case Type::MacroQualified:
692 if (!IsStructurallyEquivalent(
693 Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),
694 cast<MacroQualifiedType>(T2)->getUnderlyingType()))
699 if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
700 cast<TypedefType>(T2)->getDecl()))
704 case Type::TypeOfExpr:
705 if (!IsStructurallyEquivalent(
706 Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
707 cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
712 if (!IsStructurallyEquivalent(Context,
713 cast<TypeOfType>(T1)->getUnderlyingType(),
714 cast<TypeOfType>(T2)->getUnderlyingType()))
718 case Type::UnaryTransform:
719 if (!IsStructurallyEquivalent(
720 Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
721 cast<UnaryTransformType>(T2)->getUnderlyingType()))
726 if (!IsStructurallyEquivalent(Context,
727 cast<DecltypeType>(T1)->getUnderlyingExpr(),
728 cast<DecltypeType>(T2)->getUnderlyingExpr()))
733 auto *Auto1 = cast<AutoType>(T1);
734 auto *Auto2 = cast<AutoType>(T2);
735 if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
736 Auto2->getDeducedType()))
738 if (Auto1->isConstrained() != Auto2->isConstrained())
740 if (Auto1->isConstrained()) {
741 if (Auto1->getTypeConstraintConcept() !=
742 Auto2->getTypeConstraintConcept())
744 ArrayRef<TemplateArgument> Auto1Args =
745 Auto1->getTypeConstraintArguments();
746 ArrayRef<TemplateArgument> Auto2Args =
747 Auto2->getTypeConstraintArguments();
748 if (Auto1Args.size() != Auto2Args.size())
750 for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
751 if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
758 case Type::DeducedTemplateSpecialization: {
759 const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
760 const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
761 if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
762 DT2->getTemplateName()))
764 if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
765 DT2->getDeducedType()))
772 if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
773 cast<TagType>(T2)->getDecl()))
777 case Type::TemplateTypeParm: {
778 const auto *Parm1 = cast<TemplateTypeParmType>(T1);
779 const auto *Parm2 = cast<TemplateTypeParmType>(T2);
780 if (Parm1->getDepth() != Parm2->getDepth())
782 if (Parm1->getIndex() != Parm2->getIndex())
784 if (Parm1->isParameterPack() != Parm2->isParameterPack())
787 // Names of template type parameters are never significant.
791 case Type::SubstTemplateTypeParm: {
792 const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
793 const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
794 if (!IsStructurallyEquivalent(Context,
795 QualType(Subst1->getReplacedParameter(), 0),
796 QualType(Subst2->getReplacedParameter(), 0)))
798 if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
799 Subst2->getReplacementType()))
804 case Type::SubstTemplateTypeParmPack: {
805 const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
806 const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
807 if (!IsStructurallyEquivalent(Context,
808 QualType(Subst1->getReplacedParameter(), 0),
809 QualType(Subst2->getReplacedParameter(), 0)))
811 if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
812 Subst2->getArgumentPack()))
817 case Type::TemplateSpecialization: {
818 const auto *Spec1 = cast<TemplateSpecializationType>(T1);
819 const auto *Spec2 = cast<TemplateSpecializationType>(T2);
820 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
821 Spec2->getTemplateName()))
823 if (Spec1->getNumArgs() != Spec2->getNumArgs())
825 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
826 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
833 case Type::Elaborated: {
834 const auto *Elab1 = cast<ElaboratedType>(T1);
835 const auto *Elab2 = cast<ElaboratedType>(T2);
836 // CHECKME: what if a keyword is ETK_None or ETK_typename ?
837 if (Elab1->getKeyword() != Elab2->getKeyword())
839 if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
840 Elab2->getQualifier()))
842 if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
843 Elab2->getNamedType()))
848 case Type::InjectedClassName: {
849 const auto *Inj1 = cast<InjectedClassNameType>(T1);
850 const auto *Inj2 = cast<InjectedClassNameType>(T2);
851 if (!IsStructurallyEquivalent(Context,
852 Inj1->getInjectedSpecializationType(),
853 Inj2->getInjectedSpecializationType()))
858 case Type::DependentName: {
859 const auto *Typename1 = cast<DependentNameType>(T1);
860 const auto *Typename2 = cast<DependentNameType>(T2);
861 if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
862 Typename2->getQualifier()))
864 if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
865 Typename2->getIdentifier()))
871 case Type::DependentTemplateSpecialization: {
872 const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
873 const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
874 if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
875 Spec2->getQualifier()))
877 if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
878 Spec2->getIdentifier()))
880 if (Spec1->getNumArgs() != Spec2->getNumArgs())
882 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
883 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
890 case Type::PackExpansion:
891 if (!IsStructurallyEquivalent(Context,
892 cast<PackExpansionType>(T1)->getPattern(),
893 cast<PackExpansionType>(T2)->getPattern()))
897 case Type::ObjCInterface: {
898 const auto *Iface1 = cast<ObjCInterfaceType>(T1);
899 const auto *Iface2 = cast<ObjCInterfaceType>(T2);
900 if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
906 case Type::ObjCTypeParam: {
907 const auto *Obj1 = cast<ObjCTypeParamType>(T1);
908 const auto *Obj2 = cast<ObjCTypeParamType>(T2);
909 if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
912 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
914 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
915 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
916 Obj2->getProtocol(I)))
922 case Type::ObjCObject: {
923 const auto *Obj1 = cast<ObjCObjectType>(T1);
924 const auto *Obj2 = cast<ObjCObjectType>(T2);
925 if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
926 Obj2->getBaseType()))
928 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
930 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
931 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
932 Obj2->getProtocol(I)))
938 case Type::ObjCObjectPointer: {
939 const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
940 const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
941 if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
942 Ptr2->getPointeeType()))
948 if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
949 cast<AtomicType>(T2)->getValueType()))
954 if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
955 cast<PipeType>(T2)->getElementType()))
963 /// Determine structural equivalence of two fields.
964 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
965 FieldDecl *Field1, FieldDecl *Field2) {
966 const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
968 // For anonymous structs/unions, match up the anonymous struct/union type
969 // declarations directly, so that we don't go off searching for anonymous
971 if (Field1->isAnonymousStructOrUnion() &&
972 Field2->isAnonymousStructOrUnion()) {
973 RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
974 RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
975 return IsStructurallyEquivalent(Context, D1, D2);
978 // Check for equivalent field names.
979 IdentifierInfo *Name1 = Field1->getIdentifier();
980 IdentifierInfo *Name2 = Field2->getIdentifier();
981 if (!::IsStructurallyEquivalent(Name1, Name2)) {
982 if (Context.Complain) {
984 Owner2->getLocation(),
985 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
986 << Context.ToCtx.getTypeDeclType(Owner2);
987 Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
988 << Field2->getDeclName();
989 Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
990 << Field1->getDeclName();
995 if (!IsStructurallyEquivalent(Context, Field1->getType(),
996 Field2->getType())) {
997 if (Context.Complain) {
999 Owner2->getLocation(),
1000 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1001 << Context.ToCtx.getTypeDeclType(Owner2);
1002 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1003 << Field2->getDeclName() << Field2->getType();
1004 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1005 << Field1->getDeclName() << Field1->getType();
1010 if (Field1->isBitField() != Field2->isBitField()) {
1011 if (Context.Complain) {
1013 Owner2->getLocation(),
1014 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1015 << Context.ToCtx.getTypeDeclType(Owner2);
1016 if (Field1->isBitField()) {
1017 Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1018 << Field1->getDeclName() << Field1->getType()
1019 << Field1->getBitWidthValue(Context.FromCtx);
1020 Context.Diag2(Field2->getLocation(), diag::note_odr_not_bit_field)
1021 << Field2->getDeclName();
1023 Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1024 << Field2->getDeclName() << Field2->getType()
1025 << Field2->getBitWidthValue(Context.ToCtx);
1026 Context.Diag1(Field1->getLocation(), diag::note_odr_not_bit_field)
1027 << Field1->getDeclName();
1033 if (Field1->isBitField()) {
1034 // Make sure that the bit-fields are the same length.
1035 unsigned Bits1 = Field1->getBitWidthValue(Context.FromCtx);
1036 unsigned Bits2 = Field2->getBitWidthValue(Context.ToCtx);
1038 if (Bits1 != Bits2) {
1039 if (Context.Complain) {
1040 Context.Diag2(Owner2->getLocation(),
1041 Context.getApplicableDiagnostic(
1042 diag::err_odr_tag_type_inconsistent))
1043 << Context.ToCtx.getTypeDeclType(Owner2);
1044 Context.Diag2(Field2->getLocation(), diag::note_odr_bit_field)
1045 << Field2->getDeclName() << Field2->getType() << Bits2;
1046 Context.Diag1(Field1->getLocation(), diag::note_odr_bit_field)
1047 << Field1->getDeclName() << Field1->getType() << Bits1;
1056 /// Determine structural equivalence of two methods.
1057 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1058 CXXMethodDecl *Method1,
1059 CXXMethodDecl *Method2) {
1060 bool PropertiesEqual =
1061 Method1->getDeclKind() == Method2->getDeclKind() &&
1062 Method1->getRefQualifier() == Method2->getRefQualifier() &&
1063 Method1->getAccess() == Method2->getAccess() &&
1064 Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1065 Method1->isStatic() == Method2->isStatic() &&
1066 Method1->isConst() == Method2->isConst() &&
1067 Method1->isVolatile() == Method2->isVolatile() &&
1068 Method1->isVirtual() == Method2->isVirtual() &&
1069 Method1->isPure() == Method2->isPure() &&
1070 Method1->isDefaulted() == Method2->isDefaulted() &&
1071 Method1->isDeleted() == Method2->isDeleted();
1072 if (!PropertiesEqual)
1074 // FIXME: Check for 'final'.
1076 if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1077 auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1078 if (!Constructor1->getExplicitSpecifier().isEquivalent(
1079 Constructor2->getExplicitSpecifier()))
1083 if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1084 auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1085 if (!Conversion1->getExplicitSpecifier().isEquivalent(
1086 Conversion2->getExplicitSpecifier()))
1088 if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1089 Conversion2->getConversionType()))
1093 const IdentifierInfo *Name1 = Method1->getIdentifier();
1094 const IdentifierInfo *Name2 = Method2->getIdentifier();
1095 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1097 // TODO: Names do not match, add warning like at check for FieldDecl.
1100 // Check the prototypes.
1101 if (!::IsStructurallyEquivalent(Context,
1102 Method1->getType(), Method2->getType()))
1108 /// Determine structural equivalence of two lambda classes.
1110 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1111 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1112 assert(D1->isLambda() && D2->isLambda() &&
1113 "Must be called on lambda classes");
1114 if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1115 D2->getLambdaCallOperator()))
1121 /// Determine structural equivalence of two records.
1122 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1123 RecordDecl *D1, RecordDecl *D2) {
1124 if (D1->isUnion() != D2->isUnion()) {
1125 if (Context.Complain) {
1126 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1127 diag::err_odr_tag_type_inconsistent))
1128 << Context.ToCtx.getTypeDeclType(D2);
1129 Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1130 << D1->getDeclName() << (unsigned)D1->getTagKind();
1135 if (!D1->getDeclName() && !D2->getDeclName()) {
1136 // If both anonymous structs/unions are in a record context, make sure
1137 // they occur in the same location in the context records.
1138 if (Optional<unsigned> Index1 =
1139 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1140 if (Optional<unsigned> Index2 =
1141 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1143 if (*Index1 != *Index2)
1149 // If both declarations are class template specializations, we know
1150 // the ODR applies, so check the template and template arguments.
1151 const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1152 const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1153 if (Spec1 && Spec2) {
1154 // Check that the specialized templates are the same.
1155 if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1156 Spec2->getSpecializedTemplate()))
1159 // Check that the template arguments are the same.
1160 if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1163 for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1164 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1165 Spec2->getTemplateArgs().get(I)))
1168 // If one is a class template specialization and the other is not, these
1169 // structures are different.
1170 else if (Spec1 || Spec2)
1173 // Compare the definitions of these two records. If either or both are
1174 // incomplete (i.e. it is a forward decl), we assume that they are
1176 D1 = D1->getDefinition();
1177 D2 = D2->getDefinition();
1181 // If any of the records has external storage and we do a minimal check (or
1182 // AST import) we assume they are equivalent. (If we didn't have this
1183 // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1184 // another AST import which in turn would call the structural equivalency
1185 // check again and finally we'd have an improper result.)
1186 if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1187 if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1190 // If one definition is currently being defined, we do not compare for
1191 // equality and we assume that the decls are equal.
1192 if (D1->isBeingDefined() || D2->isBeingDefined())
1195 if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1196 if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1197 if (D1CXX->hasExternalLexicalStorage() &&
1198 !D1CXX->isCompleteDefinition()) {
1199 D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1202 if (D1CXX->isLambda() != D2CXX->isLambda())
1204 if (D1CXX->isLambda()) {
1205 if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1209 if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1210 if (Context.Complain) {
1211 Context.Diag2(D2->getLocation(),
1212 Context.getApplicableDiagnostic(
1213 diag::err_odr_tag_type_inconsistent))
1214 << Context.ToCtx.getTypeDeclType(D2);
1215 Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1216 << D2CXX->getNumBases();
1217 Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1218 << D1CXX->getNumBases();
1223 // Check the base classes.
1224 for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1225 BaseEnd1 = D1CXX->bases_end(),
1226 Base2 = D2CXX->bases_begin();
1227 Base1 != BaseEnd1; ++Base1, ++Base2) {
1228 if (!IsStructurallyEquivalent(Context, Base1->getType(),
1229 Base2->getType())) {
1230 if (Context.Complain) {
1231 Context.Diag2(D2->getLocation(),
1232 Context.getApplicableDiagnostic(
1233 diag::err_odr_tag_type_inconsistent))
1234 << Context.ToCtx.getTypeDeclType(D2);
1235 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1236 << Base2->getType() << Base2->getSourceRange();
1237 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1238 << Base1->getType() << Base1->getSourceRange();
1243 // Check virtual vs. non-virtual inheritance mismatch.
1244 if (Base1->isVirtual() != Base2->isVirtual()) {
1245 if (Context.Complain) {
1246 Context.Diag2(D2->getLocation(),
1247 Context.getApplicableDiagnostic(
1248 diag::err_odr_tag_type_inconsistent))
1249 << Context.ToCtx.getTypeDeclType(D2);
1250 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1251 << Base2->isVirtual() << Base2->getSourceRange();
1252 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1253 << Base1->isVirtual() << Base1->getSourceRange();
1259 // Check the friends for consistency.
1260 CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1261 Friend2End = D2CXX->friend_end();
1262 for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1263 Friend1End = D1CXX->friend_end();
1264 Friend1 != Friend1End; ++Friend1, ++Friend2) {
1265 if (Friend2 == Friend2End) {
1266 if (Context.Complain) {
1267 Context.Diag2(D2->getLocation(),
1268 Context.getApplicableDiagnostic(
1269 diag::err_odr_tag_type_inconsistent))
1270 << Context.ToCtx.getTypeDeclType(D2CXX);
1271 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1272 Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1277 if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1278 if (Context.Complain) {
1279 Context.Diag2(D2->getLocation(),
1280 Context.getApplicableDiagnostic(
1281 diag::err_odr_tag_type_inconsistent))
1282 << Context.ToCtx.getTypeDeclType(D2CXX);
1283 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1284 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1290 if (Friend2 != Friend2End) {
1291 if (Context.Complain) {
1292 Context.Diag2(D2->getLocation(),
1293 Context.getApplicableDiagnostic(
1294 diag::err_odr_tag_type_inconsistent))
1295 << Context.ToCtx.getTypeDeclType(D2);
1296 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1297 Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1301 } else if (D1CXX->getNumBases() > 0) {
1302 if (Context.Complain) {
1303 Context.Diag2(D2->getLocation(),
1304 Context.getApplicableDiagnostic(
1305 diag::err_odr_tag_type_inconsistent))
1306 << Context.ToCtx.getTypeDeclType(D2);
1307 const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1308 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1309 << Base1->getType() << Base1->getSourceRange();
1310 Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1316 // Check the fields for consistency.
1317 RecordDecl::field_iterator Field2 = D2->field_begin(),
1318 Field2End = D2->field_end();
1319 for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1320 Field1End = D1->field_end();
1321 Field1 != Field1End; ++Field1, ++Field2) {
1322 if (Field2 == Field2End) {
1323 if (Context.Complain) {
1324 Context.Diag2(D2->getLocation(),
1325 Context.getApplicableDiagnostic(
1326 diag::err_odr_tag_type_inconsistent))
1327 << Context.ToCtx.getTypeDeclType(D2);
1328 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1329 << Field1->getDeclName() << Field1->getType();
1330 Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1335 if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1339 if (Field2 != Field2End) {
1340 if (Context.Complain) {
1341 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1342 diag::err_odr_tag_type_inconsistent))
1343 << Context.ToCtx.getTypeDeclType(D2);
1344 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1345 << Field2->getDeclName() << Field2->getType();
1346 Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1354 /// Determine structural equivalence of two enums.
1355 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1356 EnumDecl *D1, EnumDecl *D2) {
1358 // Compare the definitions of these two enums. If either or both are
1359 // incomplete (i.e. forward declared), we assume that they are equivalent.
1360 D1 = D1->getDefinition();
1361 D2 = D2->getDefinition();
1365 EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1366 EC2End = D2->enumerator_end();
1367 for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1368 EC1End = D1->enumerator_end();
1369 EC1 != EC1End; ++EC1, ++EC2) {
1370 if (EC2 == EC2End) {
1371 if (Context.Complain) {
1372 Context.Diag2(D2->getLocation(),
1373 Context.getApplicableDiagnostic(
1374 diag::err_odr_tag_type_inconsistent))
1375 << Context.ToCtx.getTypeDeclType(D2);
1376 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1377 << EC1->getDeclName() << EC1->getInitVal().toString(10);
1378 Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1383 llvm::APSInt Val1 = EC1->getInitVal();
1384 llvm::APSInt Val2 = EC2->getInitVal();
1385 if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1386 !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1387 if (Context.Complain) {
1388 Context.Diag2(D2->getLocation(),
1389 Context.getApplicableDiagnostic(
1390 diag::err_odr_tag_type_inconsistent))
1391 << Context.ToCtx.getTypeDeclType(D2);
1392 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1393 << EC2->getDeclName() << EC2->getInitVal().toString(10);
1394 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1395 << EC1->getDeclName() << EC1->getInitVal().toString(10);
1401 if (EC2 != EC2End) {
1402 if (Context.Complain) {
1403 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1404 diag::err_odr_tag_type_inconsistent))
1405 << Context.ToCtx.getTypeDeclType(D2);
1406 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1407 << EC2->getDeclName() << EC2->getInitVal().toString(10);
1408 Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1416 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1417 TemplateParameterList *Params1,
1418 TemplateParameterList *Params2) {
1419 if (Params1->size() != Params2->size()) {
1420 if (Context.Complain) {
1421 Context.Diag2(Params2->getTemplateLoc(),
1422 Context.getApplicableDiagnostic(
1423 diag::err_odr_different_num_template_parameters))
1424 << Params1->size() << Params2->size();
1425 Context.Diag1(Params1->getTemplateLoc(),
1426 diag::note_odr_template_parameter_list);
1431 for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1432 if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1433 if (Context.Complain) {
1434 Context.Diag2(Params2->getParam(I)->getLocation(),
1435 Context.getApplicableDiagnostic(
1436 diag::err_odr_different_template_parameter_kind));
1437 Context.Diag1(Params1->getParam(I)->getLocation(),
1438 diag::note_odr_template_parameter_here);
1443 if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1444 Params2->getParam(I)))
1451 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1452 TemplateTypeParmDecl *D1,
1453 TemplateTypeParmDecl *D2) {
1454 if (D1->isParameterPack() != D2->isParameterPack()) {
1455 if (Context.Complain) {
1456 Context.Diag2(D2->getLocation(),
1457 Context.getApplicableDiagnostic(
1458 diag::err_odr_parameter_pack_non_pack))
1459 << D2->isParameterPack();
1460 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1461 << D1->isParameterPack();
1469 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1470 NonTypeTemplateParmDecl *D1,
1471 NonTypeTemplateParmDecl *D2) {
1472 if (D1->isParameterPack() != D2->isParameterPack()) {
1473 if (Context.Complain) {
1474 Context.Diag2(D2->getLocation(),
1475 Context.getApplicableDiagnostic(
1476 diag::err_odr_parameter_pack_non_pack))
1477 << D2->isParameterPack();
1478 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1479 << D1->isParameterPack();
1485 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1486 if (Context.Complain) {
1487 Context.Diag2(D2->getLocation(),
1488 Context.getApplicableDiagnostic(
1489 diag::err_odr_non_type_parameter_type_inconsistent))
1490 << D2->getType() << D1->getType();
1491 Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1500 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1501 TemplateTemplateParmDecl *D1,
1502 TemplateTemplateParmDecl *D2) {
1503 if (D1->isParameterPack() != D2->isParameterPack()) {
1504 if (Context.Complain) {
1505 Context.Diag2(D2->getLocation(),
1506 Context.getApplicableDiagnostic(
1507 diag::err_odr_parameter_pack_non_pack))
1508 << D2->isParameterPack();
1509 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1510 << D1->isParameterPack();
1515 // Check template parameter lists.
1516 return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1517 D2->getTemplateParameters());
1520 static bool IsTemplateDeclCommonStructurallyEquivalent(
1521 StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1522 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1524 if (!D1->getIdentifier()) // Special name
1525 if (D1->getNameAsString() != D2->getNameAsString())
1527 return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1528 D2->getTemplateParameters());
1531 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1532 ClassTemplateDecl *D1,
1533 ClassTemplateDecl *D2) {
1534 // Check template parameters.
1535 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1538 // Check the templated declaration.
1539 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1540 D2->getTemplatedDecl());
1543 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1544 FunctionTemplateDecl *D1,
1545 FunctionTemplateDecl *D2) {
1546 // Check template parameters.
1547 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1550 // Check the templated declaration.
1551 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1552 D2->getTemplatedDecl()->getType());
1555 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1558 // Check template parameters.
1559 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1562 // Check the constraint expression.
1563 return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1564 D2->getConstraintExpr());
1567 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1568 FriendDecl *D1, FriendDecl *D2) {
1569 if ((D1->getFriendType() && D2->getFriendDecl()) ||
1570 (D1->getFriendDecl() && D2->getFriendType())) {
1573 if (D1->getFriendType() && D2->getFriendType())
1574 return IsStructurallyEquivalent(Context,
1575 D1->getFriendType()->getType(),
1576 D2->getFriendType()->getType());
1577 if (D1->getFriendDecl() && D2->getFriendDecl())
1578 return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1579 D2->getFriendDecl());
1583 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1584 FunctionDecl *D1, FunctionDecl *D2) {
1585 // FIXME: Consider checking for function attributes as well.
1586 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1592 /// Determine structural equivalence of two declarations.
1593 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1594 Decl *D1, Decl *D2) {
1595 // FIXME: Check for known structural equivalences via a callback of some sort.
1597 D1 = D1->getCanonicalDecl();
1598 D2 = D2->getCanonicalDecl();
1599 std::pair<Decl *, Decl *> P{D1, D2};
1601 // Check whether we already know that these two declarations are not
1602 // structurally equivalent.
1603 if (Context.NonEquivalentDecls.count(P))
1606 // Check if a check for these declarations is already pending.
1607 // If yes D1 and D2 will be checked later (from DeclsToCheck),
1608 // or these are already checked (and equivalent).
1609 bool Inserted = Context.VisitedDecls.insert(P).second;
1613 Context.DeclsToCheck.push(P);
1618 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1620 assert(Complain && "Not allowed to complain");
1622 FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1623 LastDiagFromC2 = false;
1624 return FromCtx.getDiagnostics().Report(Loc, DiagID);
1627 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1629 assert(Complain && "Not allowed to complain");
1630 if (!LastDiagFromC2)
1631 ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1632 LastDiagFromC2 = true;
1633 return ToCtx.getDiagnostics().Report(Loc, DiagID);
1637 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1638 ASTContext &Context = Anon->getASTContext();
1639 QualType AnonTy = Context.getRecordType(Anon);
1641 const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1646 for (const auto *D : Owner->noload_decls()) {
1647 const auto *F = dyn_cast<FieldDecl>(D);
1651 if (F->isAnonymousStructOrUnion()) {
1652 if (Context.hasSameType(F->getType(), AnonTy))
1658 // If the field looks like this:
1659 // struct { ... } A;
1660 QualType FieldType = F->getType();
1661 // In case of nested structs.
1662 while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1663 FieldType = ElabType->getNamedType();
1665 if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1666 const RecordDecl *RecDecl = RecType->getDecl();
1667 if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1668 if (Context.hasSameType(FieldType, AnonTy))
1679 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
1680 unsigned ErrorDiagnostic) {
1681 if (ErrorOnTagTypeMismatch)
1682 return ErrorDiagnostic;
1684 switch (ErrorDiagnostic) {
1685 case diag::err_odr_variable_type_inconsistent:
1686 return diag::warn_odr_variable_type_inconsistent;
1687 case diag::err_odr_variable_multiple_def:
1688 return diag::warn_odr_variable_multiple_def;
1689 case diag::err_odr_function_type_inconsistent:
1690 return diag::warn_odr_function_type_inconsistent;
1691 case diag::err_odr_tag_type_inconsistent:
1692 return diag::warn_odr_tag_type_inconsistent;
1693 case diag::err_odr_field_type_inconsistent:
1694 return diag::warn_odr_field_type_inconsistent;
1695 case diag::err_odr_ivar_type_inconsistent:
1696 return diag::warn_odr_ivar_type_inconsistent;
1697 case diag::err_odr_objc_superclass_inconsistent:
1698 return diag::warn_odr_objc_superclass_inconsistent;
1699 case diag::err_odr_objc_method_result_type_inconsistent:
1700 return diag::warn_odr_objc_method_result_type_inconsistent;
1701 case diag::err_odr_objc_method_num_params_inconsistent:
1702 return diag::warn_odr_objc_method_num_params_inconsistent;
1703 case diag::err_odr_objc_method_param_type_inconsistent:
1704 return diag::warn_odr_objc_method_param_type_inconsistent;
1705 case diag::err_odr_objc_method_variadic_inconsistent:
1706 return diag::warn_odr_objc_method_variadic_inconsistent;
1707 case diag::err_odr_objc_property_type_inconsistent:
1708 return diag::warn_odr_objc_property_type_inconsistent;
1709 case diag::err_odr_objc_property_impl_kind_inconsistent:
1710 return diag::warn_odr_objc_property_impl_kind_inconsistent;
1711 case diag::err_odr_objc_synthesize_ivar_inconsistent:
1712 return diag::warn_odr_objc_synthesize_ivar_inconsistent;
1713 case diag::err_odr_different_num_template_parameters:
1714 return diag::warn_odr_different_num_template_parameters;
1715 case diag::err_odr_different_template_parameter_kind:
1716 return diag::warn_odr_different_template_parameter_kind;
1717 case diag::err_odr_parameter_pack_non_pack:
1718 return diag::warn_odr_parameter_pack_non_pack;
1719 case diag::err_odr_non_type_parameter_type_inconsistent:
1720 return diag::warn_odr_non_type_parameter_type_inconsistent;
1722 llvm_unreachable("Diagnostic kind not handled in preceding switch");
1725 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
1727 // Ensure that the implementation functions (all static functions in this TU)
1728 // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1729 // because that will wreak havoc the internal state (DeclsToCheck and
1730 // VisitedDecls members) and can cause faulty behaviour.
1731 // In other words: Do not start a graph search from a new node with the
1732 // internal data of another search in progress.
1733 // FIXME: Better encapsulation and separation of internal and public
1735 assert(DeclsToCheck.empty());
1736 assert(VisitedDecls.empty());
1738 if (!::IsStructurallyEquivalent(*this, D1, D2))
1744 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
1745 assert(DeclsToCheck.empty());
1746 assert(VisitedDecls.empty());
1747 if (!::IsStructurallyEquivalent(*this, T1, T2))
1753 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
1754 // Check for equivalent described template.
1755 TemplateDecl *Template1 = D1->getDescribedTemplate();
1756 TemplateDecl *Template2 = D2->getDescribedTemplate();
1757 if ((Template1 != nullptr) != (Template2 != nullptr))
1759 if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
1762 // FIXME: Move check for identifier names into this function.
1767 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
1768 Decl *D1, Decl *D2) {
1769 // FIXME: Switch on all declaration kinds. For now, we're just going to
1770 // check the obvious ones.
1771 if (auto *Record1 = dyn_cast<RecordDecl>(D1)) {
1772 if (auto *Record2 = dyn_cast<RecordDecl>(D2)) {
1773 // Check for equivalent structure names.
1774 IdentifierInfo *Name1 = Record1->getIdentifier();
1775 if (!Name1 && Record1->getTypedefNameForAnonDecl())
1776 Name1 = Record1->getTypedefNameForAnonDecl()->getIdentifier();
1777 IdentifierInfo *Name2 = Record2->getIdentifier();
1778 if (!Name2 && Record2->getTypedefNameForAnonDecl())
1779 Name2 = Record2->getTypedefNameForAnonDecl()->getIdentifier();
1780 if (!::IsStructurallyEquivalent(Name1, Name2) ||
1781 !::IsStructurallyEquivalent(*this, Record1, Record2))
1784 // Record/non-record mismatch.
1787 } else if (auto *Enum1 = dyn_cast<EnumDecl>(D1)) {
1788 if (auto *Enum2 = dyn_cast<EnumDecl>(D2)) {
1789 // Check for equivalent enum names.
1790 IdentifierInfo *Name1 = Enum1->getIdentifier();
1791 if (!Name1 && Enum1->getTypedefNameForAnonDecl())
1792 Name1 = Enum1->getTypedefNameForAnonDecl()->getIdentifier();
1793 IdentifierInfo *Name2 = Enum2->getIdentifier();
1794 if (!Name2 && Enum2->getTypedefNameForAnonDecl())
1795 Name2 = Enum2->getTypedefNameForAnonDecl()->getIdentifier();
1796 if (!::IsStructurallyEquivalent(Name1, Name2) ||
1797 !::IsStructurallyEquivalent(*this, Enum1, Enum2))
1800 // Enum/non-enum mismatch
1803 } else if (const auto *Typedef1 = dyn_cast<TypedefNameDecl>(D1)) {
1804 if (const auto *Typedef2 = dyn_cast<TypedefNameDecl>(D2)) {
1805 if (!::IsStructurallyEquivalent(Typedef1->getIdentifier(),
1806 Typedef2->getIdentifier()) ||
1807 !::IsStructurallyEquivalent(*this, Typedef1->getUnderlyingType(),
1808 Typedef2->getUnderlyingType()))
1811 // Typedef/non-typedef mismatch.
1814 } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1815 if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1816 if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1820 // Class template/non-class-template mismatch.
1823 } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1824 if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1825 if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1829 // Class template/non-class-template mismatch.
1832 } else if (auto *ConceptDecl1 = dyn_cast<ConceptDecl>(D1)) {
1833 if (auto *ConceptDecl2 = dyn_cast<ConceptDecl>(D2)) {
1834 if (!::IsStructurallyEquivalent(*this, ConceptDecl1, ConceptDecl2))
1837 // Concept/non-concept mismatch.
1840 } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1841 if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1842 if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1848 } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1849 if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1850 if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1856 } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1857 if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1858 if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1864 } else if (auto *MD1 = dyn_cast<CXXMethodDecl>(D1)) {
1865 if (auto *MD2 = dyn_cast<CXXMethodDecl>(D2)) {
1866 if (!::IsStructurallyEquivalent(*this, MD1, MD2))
1872 } else if (FunctionDecl *FD1 = dyn_cast<FunctionDecl>(D1)) {
1873 if (FunctionDecl *FD2 = dyn_cast<FunctionDecl>(D2)) {
1874 if (FD1->isOverloadedOperator()) {
1875 if (!FD2->isOverloadedOperator())
1877 if (FD1->getOverloadedOperator() != FD2->getOverloadedOperator())
1880 if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1881 FD2->getIdentifier()))
1883 if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1889 } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1890 if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1891 if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1902 bool StructuralEquivalenceContext::Finish() {
1903 while (!DeclsToCheck.empty()) {
1904 // Check the next declaration.
1905 std::pair<Decl *, Decl *> P = DeclsToCheck.front();
1909 Decl *D2 = P.second;
1912 CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
1915 // Note that these two declarations are not equivalent (and we already
1917 NonEquivalentDecls.insert(P);